Merge lp:~lifeless/bzr/apply-inventory-delta into lp:~bzr/bzr/trunk-old

[Robert Collins]

[Robert Collins (lifeless)]

While my work on validating inventory deltas is not complete, this
particular patch is self contained and already has a number of
significant bugs fixed. In particular it catches silent corruption of
dirstate basis trees by malformed commits.

I'd like this reviewed at this point as landing it will may well improve
the user experience by turning fail-later experiences into fail-early,
making some other bugs easier to diagnose and fix. I have yet to check
that there aren't corruptions being caused unwittingly by the test suite
- however I'll do that concurrently with review.

-Rob

--

[Robert Collins (lifeless)]

It turns out there are some [small] issues. In particular adding these
guards exposes current live code exercised in the test suite that
generates inconsistent deltas. I'm fixing these now.

-Rob

[Martin Pool (mbp)]

18 + # Accumulate parent references (path and id), to check for parentless
19 + # items or items placed under files/links/tree-references.
20 + parents = set()

Please make the comment consistent with what's actually in the set, ie (path, id).

62 + except errors.BzrError, e:
63 + if 'integrity error' not in str(e):
64 + raise

I'd much rather that were an isinstance check, because people would tend to think of the string as something they can freely change in the UI without affecting the behaviour. Also it would let you make the except clause just catch that one type of error.

135 + # before starting to mutate the inventory, as there isn't a rollback
136 + # facility.
137 + list(_check_delta_unique_ids(_check_delta_unique_new_paths(
138 + _check_delta_unique_old_paths(_check_delta_ids_match_entry(
139 + delta)))))

That's very cute. It seems a bit like they should be consumers rather than pass-throughs, but I'm not sure if that would actually be any clearer, or easier to write in Python.

review: Approve

[Robert Collins (lifeless)]

I didn't realise that you'd commented when you +1'd on IRC, so these
aren't in the branch thats landing.

On Fri, 2009-07-10 at 05:14 +0000, Martin Pool wrote:
> Review: Approve
> 18 + # Accumulate parent references (path and id), to check for parentless
> 19 + # items or items placed under files/links/tree-references.
> 20 + parents = set()
>
> Please make the comment consistent with what's actually in the set, ie (path, id).

Will tweak.

> 62 + except errors.BzrError, e:
> 63 + if 'integrity error' not in str(e):
> 64 + raise
>
> I'd much rather that were an isinstance check, because people would tend to think of the string as something they can freely change in the UI without affecting the behaviour. Also it would let you make the except clause just catch that one type of error.

I wish whatever interface you reviewed in would do line wrapping :(.
Could you perhaps file a bug on code-reviews about this?

I'd prefer that too, but we have this tension about exception
proliferation; the exception being raised *actually is* a BzrError :(.

> 135 + # before starting to mutate the inventory, as there isn't a rollback
> 136 + # facility.
> 137 + list(_check_delta_unique_ids(_check_delta_unique_new_paths(
> 138 + _check_delta_unique_old_paths(_check_delta_ids_match_entry(
> 139 + delta)))))
>
> That's very cute. It seems a bit like they should be consumers rather than pass-throughs, but I'm not sure if that would actually be any clearer, or easier to write in Python.

Do you mean coroutines? That needs python 2.5 Or do you mean things that
do
for item in delta:
 ....

and don't yield? - such an arrangement can't stack, and means less
locality of reference - rather than applying N tests to each item, we'd
apply one test to all items N times.

-Rob

[Martin Pool (mbp)]

2009/7/10 Robert Collins <email address hidden>:
>> 62    + except errors.BzrError, e:
>> 63    + if 'integrity error' not in str(e):
>> 64    + raise
>>
>> I'd much rather that were an isinstance check, because people would tend to think of the string as something they can freely change in the UI without affecting the behaviour.  Also it would let you make the except clause just catch that one type of error.
>
> I wish whatever interface you reviewed in would do line wrapping :(.
> Could you perhaps file a bug on code-reviews about this?

I used the web ui. It looks ok to me: it's shown wrapped in the code
review page and in my mail client. Presumably you got this as mail.
Does it behave differently to Launchpad bug reports?

> I'd prefer that too, but we have this tension about exception
> proliferation; the exception being raised *actually is* a BzrError :(.

Couldn't we change them?

>
>> 135   + # before starting to mutate the inventory, as there isn't a rollback
>> 136   + # facility.
>> 137   + list(_check_delta_unique_ids(_check_delta_unique_new_paths(
>> 138   + _check_delta_unique_old_paths(_check_delta_ids_match_entry(
>> 139   + delta)))))
>>
>> That's very cute.  It seems a bit like they should be consumers rather than pass-throughs, but I'm not sure if that would actually be any clearer, or easier to write in Python.
>
> Do you mean coroutines? That needs python 2.5 Or do you mean things that
> do
> for item in delta:
>  ....
>
> and don't yield? - such an arrangement can't stack, and means less
> locality of reference - rather than applying N tests to each item, we'd
> apply one test to all items N times.

I'd like to say this:

  multi_map([check_delta_unique_new_paths, check_delta_unique_old_paths, ...],
     delta)

and have these closures all called for side effects one-by-one through
the iterator, allowing them to accumulate internal state as they go
along, without any idea that they can modify the data or that there is
a data dependency between them.

--
Martin <http://launchpad.net/~mbp/>

[John A Meinel (jameinel)]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Martin Pool wrote:
> 2009/7/10 Robert Collins <email address hidden>:
>>> 62 + except errors.BzrError, e:
>>> 63 + if 'integrity error' not in str(e):
>>> 64 + raise
>>>
>>> I'd much rather that were an isinstance check, because people would tend to think of the string as something they can freely change in the UI without affecting the behaviour. Also it would let you make the except clause just catch that one type of error.
>> I wish whatever interface you reviewed in would do line wrapping :(.
>> Could you perhaps file a bug on code-reviews about this?
>
> I used the web ui. It looks ok to me: it's shown wrapped in the code
> review page and in my mail client. Presumably you got this as mail.
> Does it behave differently to Launchpad bug reports?

I've filed a bug on it. It *doesn't* wrap and it makes most mail clients
wrap when reading, but *unwrap* when responding. Which is pretty
annoying to try and quote.

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkpXdaoACgkQJdeBCYSNAANI0QCcDS0tIxGtVbs8BBR7PAsthmkb
kXYAn2G4kyIgiZdcO3spWas+rmf8IsE8
=AIyx
-----END PGP SIGNATURE-----

[Robert Collins (lifeless)]

On Fri, 2009-07-10 at 07:45 +0000, Martin Pool wrote:
>
> multi_map([check_delta_unique_new_paths,
> check_delta_unique_old_paths, ...],
> delta)
>
> and have these closures all called for side effects one-by-one through
> the iterator, allowing them to accumulate internal state as they go
> along, without any idea that they can modify the data or that there is
> a data dependency between them.

That would be nice. It requires considerably more code though (objects
rather than generators) and will likely be measurably slower, as
generators don't require new frames on every entrance.

-Rob

[Martin Pool (mbp)]

2009/7/13 Robert Collins <email address hidden>:
> That would be nice. It requires considerably more code though (objects
> rather than generators) and will likely be measurably slower, as
> generators don't require new frames on every entrance.

Yes that's pretty much what I concluded.

--
Martin <http://launchpad.net/~mbp/>

=== modified file 'bzrlib/dirstate.py'
--- bzrlib/dirstate.py	2009-06-22 14:32:48 +0000
+++ bzrlib/dirstate.py	2009-07-10 03:35:16 +0000
@@ -1285,7 +1285,8 @@
         removals = {}
         for old_path, new_path, file_id, inv_entry in sorted(delta, reverse=True):
             if (file_id in insertions) or (file_id in removals):
-                raise AssertionError("repeated file id in delta %r" % (file_id,))
+                raise errors.InconsistentDelta(old_path or new_path, file_id,
+                    "repeated file_id")
             if old_path is not None:
                 old_path = old_path.encode('utf-8')
                 removals[file_id] = old_path
@@ -1399,7 +1400,19 @@
         # At the same time, to reduce interface friction we convert the input
         # inventory entries to dirstate.
         root_only = ('', '')
+        # Accumulate parent references (path and id), to check for parentless
+        # items or items placed under files/links/tree-references.
+        parents = set()
         for old_path, new_path, file_id, inv_entry in delta:
+            if inv_entry is not None and file_id != inv_entry.file_id:
+                raise errors.InconsistentDelta(new_path, file_id,
+                    "mismatched entry file_id %r" % inv_entry)
+            if new_path is not None:
+                new_path_utf8 = encode(new_path)
+                # note the parent for validation
+                dirname, basename = osutils.split(new_path_utf8)
+                if basename:
+                    parents.add((dirname, inv_entry.parent_id))
             if old_path is None:
                 adds.append((None, encode(new_path), file_id,
                     inv_to_entry(inv_entry), True))
@@ -1420,7 +1433,6 @@
                 # for 'r' items on every pass.
                 self._update_basis_apply_deletes(deletes)
                 deletes = []
-                new_path_utf8 = encode(new_path)
                 # Split into an add/delete pair recursively.
                 adds.append((None, new_path_utf8, file_id,
                     inv_to_entry(inv_entry), False))
@@ -1447,18 +1459,34 @@
                         (source_path, target_path, entry[0][2], None, False))
                 deletes.append(
                     (encode(old_path), new_path, file_id, None, False))
+                # note the parent for validation
+                dirname, basename = osutils.split(new_path)
+                parents.add((dirname, inv_entry.parent_id))
             else:
                 # changes to just the root should not require remove/insertion
                 # of everything.
                 changes.append((encode(old_path), encode(new_path), file_id,
                     inv_to_entry(inv_entry)))
 
-        # Finish expunging deletes/first half of renames.
-        self._update_basis_apply_deletes(deletes)
-        # Reinstate second half of renames and new paths.
-        self._update_basis_apply_adds(adds)
-        # Apply in-situ changes.
-        self._update_basis_apply_changes(changes)
+        try:
+            # Finish expunging deletes/first half of renames.
+            self._update_basis_apply_deletes(deletes)
+            # Reinstate second half of renames and new paths.
+            self._update_basis_apply_adds(adds)
+            # Apply in-situ changes.
+            self._update_basis_apply_changes(changes)
+            # Validate parents
+            self._update_basis_check_parents(parents)
+        except errors.BzrError, e:
+            if 'integrity error' not in str(e):
+                raise
+            # _get_entry raises BzrError when a request is inconsistent; we
+            # want such errors to be shown as InconsistentDelta - and that 
+            # fits the behaviour we trigger. Partof this is driven by dirstate
+            # only supporting deltas that turn the basis into a closer fit to
+            # the active tree.
+            self._changes_aborted = True
+            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
 
         self._dirblock_state = DirState.IN_MEMORY_MODIFIED
         self._header_state = DirState.IN_MEMORY_MODIFIED
@@ -1573,6 +1601,22 @@
                     # it is being resurrected here, so blank it out temporarily.
                     self._dirblocks[block_index][1][entry_index][1][1] = null
 
+    def _update_basis_check_parents(self, parents):
+        """Check that parents required by the delta are all intact."""
+        for dirname, file_id in parents:
+            # Get the entry - the ensures that file_id, dirname exists and has
+            # the right file id.
+            entry = self._get_entry(1, file_id, dirname)
+            if entry[1] is None:
+                self._changes_aborted = True
+                raise errors.InconsistentDelta(dirname, file_id,
+                    "This parent is not present.")
+            # Parents of things must be directories
+            if entry[1][1][0] != 'd':
+                self._changes_aborted = True
+                raise errors.InconsistentDelta(dirname, file_id,
+                    "This parent is not a directory.")
+
     def _observed_sha1(self, entry, sha1, stat_value,
         _stat_to_minikind=_stat_to_minikind, _pack_stat=pack_stat):
         """Note the sha1 of a file.

=== modified file 'bzrlib/errors.py'
--- bzrlib/errors.py	2009-06-30 15:54:23 +0000
+++ bzrlib/errors.py	2009-07-10 03:35:16 +0000
@@ -2162,6 +2162,18 @@
         self.reason = reason
 
 
+class InconsistentDeltaDelta(InconsistentDelta):
+    """Used when we get a delta that is not valid."""
+
+    _fmt = ("An inconsistent delta was supplied: %(delta)r"
+            "\nreason: %(reason)s")
+
+    def __init__(self, delta, reason):
+        BzrError.__init__(self)
+        self.delta = delta
+        self.reason = reason
+
+
 class UpgradeRequired(BzrError):
 
     _fmt = "To use this feature you must upgrade your branch at %(path)s."

=== modified file 'bzrlib/inventory.py'
--- bzrlib/inventory.py	2009-07-02 23:10:53 +0000
+++ bzrlib/inventory.py	2009-07-10 03:35:16 +0000
@@ -1127,12 +1127,11 @@
         """
         # Check that the delta is legal. It would be nice if this could be
         # done within the loops below but it's safer to validate the delta
-        # before starting to mutate the inventory.
-        unique_file_ids = set([f for _, _, f, _ in delta])
-        if len(unique_file_ids) != len(delta):
-            raise AssertionError("a file-id appears multiple times in %r"
-                    % (delta,))
-        del unique_file_ids
+        # before starting to mutate the inventory, as there isn't a rollback
+        # facility.
+        list(_check_delta_unique_ids(_check_delta_unique_new_paths(
+            _check_delta_unique_old_paths(_check_delta_ids_match_entry(
+            delta)))))
 
         children = {}
         # Remove all affected items which were in the original inventory,
@@ -1167,7 +1166,11 @@
                 replacement.revision = new_entry.revision
                 replacement.children = children.pop(replacement.file_id, {})
                 new_entry = replacement
-            self.add(new_entry)
+            try:
+                self.add(new_entry)
+            except AttributeError:
+                raise errors.InconsistentDelta(new_path, new_entry.file_id,
+                    "Parent is not a directory.")
         if len(children):
             # Get the parent id that was deleted
             parent_id, children = children.popitem()
@@ -1265,13 +1268,13 @@
             try:
                 parent = self._byid[entry.parent_id]
             except KeyError:
-                raise BzrError("parent_id {%s} not in inventory" %
-                               entry.parent_id)
-
+                raise errors.InconsistentDelta("<unknown>", entry.parent_id,
+                    "Parent not in inventory.")
             if entry.name in parent.children:
-                raise BzrError("%s is already versioned" %
-                        osutils.pathjoin(self.id2path(parent.file_id),
-                        entry.name).encode('utf-8'))
+                raise errors.InconsistentDelta(
+                    self.id2path(parent.children[entry.name].file_id),
+                    entry.file_id,
+                    "Path already versioned")
             parent.children[entry.name] = entry
         return self._add_child(entry)
 
@@ -1619,6 +1622,18 @@
             result.parent_id_basename_to_file_id = None
         result.root_id = self.root_id
         id_to_entry_delta = []
+        # inventory_delta is only traversed once, so we just update the
+        # variable.
+        # Check for repeated file ids
+        inventory_delta = _check_delta_unique_ids(inventory_delta)
+        # Repeated old paths
+        inventory_delta = _check_delta_unique_old_paths(inventory_delta)
+        # Check for repeated new paths
+        inventory_delta = _check_delta_unique_new_paths(inventory_delta)
+        # Check for entries that don't match the fileid
+        inventory_delta = _check_delta_ids_match_entry(inventory_delta)
+        # All changed entries need to have their parents be directories.
+        parents = set()
         for old_path, new_path, file_id, entry in inventory_delta:
             # file id changes
             if new_path == '':
@@ -1639,6 +1654,7 @@
                 # Update caches. It's worth doing this whether
                 # we're propagating the old caches or not.
                 result._path_to_fileid_cache[new_path] = file_id
+                parents.add(entry.parent_id)
             if old_path is None:
                 old_key = None
             else:
@@ -1664,6 +1680,14 @@
         result.id_to_entry.apply_delta(id_to_entry_delta)
         if parent_id_basename_delta:
             result.parent_id_basename_to_file_id.apply_delta(parent_id_basename_delta)
+        for parent in parents:
+            try:
+                if result[parent].kind != 'directory':
+                    raise errors.InconsistentDelta(result.id2path(parent), parent,
+                        'Not a directory, but given children')
+            except errors.NoSuchId:
+                raise errors.InconsistentDelta("<unknown>", parent,
+                    "Parent is not present in resulting inventory.")
         return result
 
     @classmethod
@@ -2072,3 +2096,64 @@
         _NAME_RE = re.compile(r'^[^/\\]+$')
 
     return bool(_NAME_RE.match(name))
+
+
+def _check_delta_unique_ids(delta):
+    """Decorate a delta and check that the file ids in it are unique.
+
+    :return: A generator over delta.
+    """
+    ids = set()
+    for item in delta:
+        length = len(ids) + 1
+        ids.add(item[2])
+        if len(ids) != length:
+            raise errors.InconsistentDelta(item[0] or item[1], item[2],
+                "repeated file_id")
+        yield item
+
+
+def _check_delta_unique_new_paths(delta):
+    """Decorate a delta and check that the new paths in it are unique.
+
+    :return: A generator over delta.
+    """
+    paths = set()
+    for item in delta:
+        length = len(paths) + 1
+        path = item[1]
+        if path is not None:
+            paths.add(path)
+            if len(paths) != length:
+                raise errors.InconsistentDelta(path, item[2], "repeated path")
+        yield item
+
+
+def _check_delta_unique_old_paths(delta):
+    """Decorate a delta and check that the old paths in it are unique.
+
+    :return: A generator over delta.
+    """
+    paths = set()
+    for item in delta:
+        length = len(paths) + 1
+        path = item[0]
+        if path is not None:
+            paths.add(path)
+            if len(paths) != length:
+                raise errors.InconsistentDelta(path, item[2], "repeated path")
+        yield item
+
+
+def _check_delta_ids_match_entry(delta):
+    """Decorate a delta and check that the ids in it match the entry.file_id.
+
+    :return: A generator over delta.
+    """
+    for item in delta:
+        entry = item[3]
+        if entry is not None:
+            if entry.file_id != item[2]:
+                raise errors.InconsistentDelta(item[0] or item[1], item[2],
+                    "mismatched id with %r" % entry)
+        yield item

=== modified file 'bzrlib/tests/test_errors.py'
--- bzrlib/tests/test_errors.py	2009-06-19 00:33:36 +0000
+++ bzrlib/tests/test_errors.py	2009-07-10 03:35:16 +0000
@@ -87,6 +87,12 @@
             "reason: reason for foo",
             str(error))
 
+    def test_inconsistent_delta_delta(self):
+        error = errors.InconsistentDeltaDelta([], 'reason')
+        self.assertEqualDiff(
+            "An inconsistent delta was supplied: []\nreason: reason",
+            str(error))
+
     def test_in_process_transport(self):
         error = errors.InProcessTransport('fpp')
         self.assertEqualDiff(

=== modified file 'bzrlib/tests/test_inv.py'
--- bzrlib/tests/test_inv.py	2009-06-17 18:41:26 +0000
+++ bzrlib/tests/test_inv.py	2009-07-10 03:35:16 +0000
@@ -15,10 +15,311 @@
 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
 
-from bzrlib import errors, chk_map, inventory, osutils
+from bzrlib import (
+    chk_map,
+    bzrdir,
+    errors,
+    inventory,
+    osutils,
+    repository,
+    revision,
+    )
 from bzrlib.inventory import (CHKInventory, Inventory, ROOT_ID, InventoryFile,
     InventoryDirectory, InventoryEntry, TreeReference)
-from bzrlib.tests import TestCase, TestCaseWithTransport
+from bzrlib.tests import (
+    TestCase,
+    TestCaseWithTransport,
+    condition_isinstance,
+    multiply_tests,
+    split_suite_by_condition,
+    )
+from bzrlib.tests.workingtree_implementations import workingtree_formats
+
+
+def load_tests(standard_tests, module, loader):
+    """Parameterise some inventory tests."""
+    to_adapt, result = split_suite_by_condition(standard_tests,
+        condition_isinstance(TestDeltaApplication))
+    scenarios = [
+        ('Inventory', {'apply_delta':apply_inventory_Inventory}),
+        ]
+    # Working tree basis delta application
+    # Repository add_inv_by_delta.
+    # Reduce form of the per_repository test logic - that logic needs to be
+    # be able to get /just/ repositories whereas these tests are fine with
+    # just creating trees.
+    formats = set()
+    for _, format in repository.format_registry.iteritems():
+        scenarios.append((str(format.__name__), {
+            'apply_delta':apply_inventory_Repository_add_inventory_by_delta,
+            'format':format}))
+    for format in workingtree_formats():
+        scenarios.append((str(format.__class__.__name__), {
+            'apply_delta':apply_inventory_WT_basis,
+            'format':format}))
+    return multiply_tests(to_adapt, scenarios, result)
+
+
+def apply_inventory_Inventory(self, basis, delta):
+    """Apply delta to basis and return the result.
+    
+    :param basis: An inventory to be used as the basis.
+    :param delta: The inventory delta to apply:
+    :return: An inventory resulting from the application.
+    """
+    basis.apply_delta(delta)
+    return basis
+
+
+def apply_inventory_WT_basis(self, basis, delta):
+    """Apply delta to basis and return the result.
+
+    This sets the parent and then calls update_basis_by_delta.
+    It also puts the basis in the repository under both 'basis' and 'result' to
+    allow safety checks made by the WT to succeed, and finally ensures that all
+    items in the delta with a new path are present in the WT before calling
+    update_basis_by_delta.
+    
+    :param basis: An inventory to be used as the basis.
+    :param delta: The inventory delta to apply:
+    :return: An inventory resulting from the application.
+    """
+    control = self.make_bzrdir('tree', format=self.format._matchingbzrdir)
+    control.create_repository()
+    control.create_branch()
+    tree = self.format.initialize(control)
+    tree.lock_write()
+    try:
+        repo = tree.branch.repository
+        repo.start_write_group()
+        try:
+            rev = revision.Revision('basis', timestamp=0, timezone=None,
+                message="", committer="[e-mail]")
+            basis.revision_id = 'basis'
+            repo.add_revision('basis', rev, basis)
+            # Add a revision for the result, with the basis content - 
+            # update_basis_by_delta doesn't check that the delta results in
+            # result, and we want inconsistent deltas to get called on the
+            # tree, or else the code isn't actually checked.
+            rev = revision.Revision('result', timestamp=0, timezone=None,
+                message="", committer="[e-mail]")
+            basis.revision_id = 'result'
+            repo.add_revision('result', rev, basis)
+        except:
+            repo.abort_write_group()
+            raise
+        else:
+            repo.commit_write_group()
+        # Set the basis state as the trees current state
+        tree._write_inventory(basis)
+        # This reads basis from the repo and puts it into the tree's local
+        # cache, if it has one.
+        tree.set_parent_ids(['basis'])
+        paths = {}
+        parents = set()
+        for old, new, id, entry in delta:
+            if entry is None:
+                continue
+            paths[new] = (entry.file_id, entry.kind)
+            parents.add(osutils.dirname(new))
+        parents = osutils.minimum_path_selection(parents)
+        parents.discard('')
+        # Put place holders in the tree to permit adding the other entries.
+        for pos, parent in enumerate(parents):
+            if not tree.path2id(parent):
+                # add a synthetic directory in the tree so we can can put the
+                # tree0 entries in place for dirstate.
+                tree.add([parent], ["id%d" % pos], ["directory"])
+        if paths:
+            # Many deltas may cause this mini-apply to fail, but we want to see what
+            # the delta application code says, not the prep that we do to deal with 
+            # limitations of dirstate's update_basis code.
+            for path, (file_id, kind) in sorted(paths.items()):
+                try:
+                    tree.add([path], [file_id], [kind])
+                except (KeyboardInterrupt, SystemExit):
+                    raise
+                except:
+                    pass
+    finally:
+        tree.unlock()
+    # Fresh lock, reads disk again.
+    tree.lock_write()
+    try:
+        tree.update_basis_by_delta('result', delta)
+    finally:
+        tree.unlock()
+    # reload tree - ensure we get what was written.
+    tree = tree.bzrdir.open_workingtree()
+    basis_tree = tree.basis_tree()
+    basis_tree.lock_read()
+    self.addCleanup(basis_tree.unlock)
+    # Note, that if the tree does not have a local cache, the trick above of
+    # setting the result as the basis, will come back to bite us. That said,
+    # all the implementations in bzr do have a local cache.
+    return basis_tree.inventory
+
+
+def apply_inventory_Repository_add_inventory_by_delta(self, basis, delta):
+    """Apply delta to basis and return the result.
+    
+    This inserts basis as a whole inventory and then uses
+    add_inventory_by_delta to add delta.
+
+    :param basis: An inventory to be used as the basis.
+    :param delta: The inventory delta to apply:
+    :return: An inventory resulting from the application.
+    """
+    format = self.format()
+    control = self.make_bzrdir('tree', format=format._matchingbzrdir)
+    repo = format.initialize(control)
+    repo.lock_write()
+    try:
+        repo.start_write_group()
+        try:
+            rev = revision.Revision('basis', timestamp=0, timezone=None,
+                message="", committer="[e-mail]")
+            basis.revision_id = 'basis'
+            repo.add_revision('basis', rev, basis)
+        except:
+            repo.abort_write_group()
+            raise
+        else:
+            repo.commit_write_group()
+    finally:
+        repo.unlock()
+    repo.lock_write()
+    try:
+        repo.start_write_group()
+        try:
+            inv_sha1 = repo.add_inventory_by_delta('basis', delta,
+                'result', ['basis'])
+        except:
+            repo.abort_write_group()
+            raise
+        else:
+            repo.commit_write_group()
+    finally:
+        repo.unlock()
+    # Fresh lock, reads disk again.
+    repo = repo.bzrdir.open_repository()
+    repo.lock_read()
+    self.addCleanup(repo.unlock)
+    return repo.get_inventory('result')
+
+
+class TestDeltaApplication(TestCaseWithTransport):
+ 
+    def get_empty_inventory(self, reference_inv=None):
+        """Get an empty inventory.
+
+        Note that tests should not depend on the revision of the root for
+        setting up test conditions, as it has to be flexible to accomodate non
+        rich root repositories.
+
+        :param reference_inv: If not None, get the revision for the root from
+            this inventory. This is useful for dealing with older repositories
+            that routinely discarded the root entry data. If None, the root's
+            revision is set to 'basis'.
+        """
+        inv = inventory.Inventory()
+        if reference_inv is not None:
+            inv.root.revision = reference_inv.root.revision
+        else:
+            inv.root.revision = 'basis'
+        return inv
+
+    def test_empty_delta(self):
+        inv = self.get_empty_inventory()
+        delta = []
+        inv = self.apply_delta(self, inv, delta)
+        inv2 = self.get_empty_inventory(inv)
+        self.assertEqual([], inv2._make_delta(inv))
+
+    def test_repeated_file_id(self):
+        inv = self.get_empty_inventory()
+        file1 = inventory.InventoryFile('id', 'path1', inv.root.file_id)
+        file1.revision = 'result'
+        file1.text_size = 0
+        file1.text_sha1 = ""
+        file2 = inventory.InventoryFile('id', 'path2', inv.root.file_id)
+        file2.revision = 'result'
+        file2.text_size = 0
+        file2.text_sha1 = ""
+        delta = [(None, u'path1', 'id', file1), (None, u'path2', 'id', file2)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
+
+    def test_repeated_new_path(self):
+        inv = self.get_empty_inventory()
+        file1 = inventory.InventoryFile('id1', 'path', inv.root.file_id)
+        file1.revision = 'result'
+        file1.text_size = 0
+        file1.text_sha1 = ""
+        file2 = inventory.InventoryFile('id2', 'path', inv.root.file_id)
+        file2.revision = 'result'
+        file2.text_size = 0
+        file2.text_sha1 = ""
+        delta = [(None, u'path', 'id1', file1), (None, u'path', 'id2', file2)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
+
+    def test_repeated_old_path(self):
+        inv = self.get_empty_inventory()
+        file1 = inventory.InventoryFile('id1', 'path', inv.root.file_id)
+        file1.revision = 'result'
+        file1.text_size = 0
+        file1.text_sha1 = ""
+        # We can't *create* a source inventory with the same path, but
+        # a badly generated partial delta might claim the same source twice.
+        # This would be buggy in two ways: the path is repeated in the delta,
+        # And the path for one of the file ids doesn't match the source
+        # location. Alternatively, we could have a repeated fileid, but that
+        # is separately checked for.
+        file2 = inventory.InventoryFile('id2', 'path2', inv.root.file_id)
+        file2.revision = 'result'
+        file2.text_size = 0
+        file2.text_sha1 = ""
+        inv.add(file1)
+        inv.add(file2)
+        delta = [(u'path', None, 'id1', None), (u'path', None, 'id2', None)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
+
+    def test_mismatched_id_entry_id(self):
+        inv = self.get_empty_inventory()
+        file1 = inventory.InventoryFile('id1', 'path', inv.root.file_id)
+        file1.revision = 'result'
+        file1.text_size = 0
+        file1.text_sha1 = ""
+        delta = [(None, u'path', 'id', file1)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
+
+    def test_parent_is_not_directory(self):
+        inv = self.get_empty_inventory()
+        file1 = inventory.InventoryFile('id1', 'path', inv.root.file_id)
+        file1.revision = 'result'
+        file1.text_size = 0
+        file1.text_sha1 = ""
+        file2 = inventory.InventoryFile('id2', 'path2', 'id1')
+        file2.revision = 'result'
+        file2.text_size = 0
+        file2.text_sha1 = ""
+        inv.add(file1)
+        delta = [(None, u'path/path2', 'id2', file2)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
+
+    def test_parent_is_missing(self):
+        inv = self.get_empty_inventory()
+        file2 = inventory.InventoryFile('id2', 'path2', 'missingparent')
+        file2.revision = 'result'
+        file2.text_size = 0
+        file2.text_sha1 = ""
+        delta = [(None, u'path/path2', 'id2', file2)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
 
 
 class TestInventoryEntry(TestCase):

=== modified file 'bzrlib/tests/workingtree_implementations/__init__.py'
--- bzrlib/tests/workingtree_implementations/__init__.py	2009-07-06 21:13:30 +0000
+++ bzrlib/tests/workingtree_implementations/__init__.py	2009-07-10 03:35:16 +0000
@@ -59,6 +59,12 @@
         return self.workingtree_format.initialize(made_control)
 
 
+def workingtree_formats():
+    """The known working tree formats."""
+    return (workingtree.WorkingTreeFormat._formats.values() +
+        workingtree._legacy_formats)
+
+
 def load_tests(standard_tests, module, loader):
     test_workingtree_implementations = [
         'bzrlib.tests.workingtree_implementations.test_add_reference',
@@ -106,8 +112,8 @@
         # None here will cause a readonly decorator to be created
         # by the TestCaseWithTransport.get_readonly_transport method.
         None,
-        workingtree.WorkingTreeFormat._formats.values()
-        + workingtree._legacy_formats)
+        workingtree_formats()
+        )
 
     # add the tests for the sub modules
     return tests.multiply_tests(

=== modified file 'bzrlib/xml8.py'
--- bzrlib/xml8.py	2009-06-09 00:59:51 +0000
+++ bzrlib/xml8.py	2009-07-10 03:35:16 +0000
@@ -168,9 +168,9 @@
         :raises: AssertionError if an error has occurred.
         """
         if inv.revision_id is None:
-            raise AssertionError()
+            raise AssertionError("inv.revision_id is None")
         if inv.root.revision is None:
-            raise AssertionError()
+            raise AssertionError("inv.root.revision is None")
 
     def _check_cache_size(self, inv_size, entry_cache):
         """Check that the entry_cache is large enough.