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

[Robert Collins]

[Robert Collins (lifeless)]

Add WorkingTree.apply_inventory_delta to the set of delta
implementations interface tested.

This implementation wasn't preventing 'parent is not a directory'
errors. Other than that the changes that are made are essentially
cosmetic - consistent exceptions and catching corruption that we're very
unlikely to cause.

-Rob

--

[Ian Clatworthy (ian-clatworthy)]

Robert Collins wrote:
> Robert Collins has proposed merging lp:~lifeless/bzr/apply-inventory-delta into lp:bzr.
>
> Requested reviews:
> bzr-core (bzr-core)
>
> Add WorkingTree.apply_inventory_delta to the set of delta
> implementations interface tested.
>
> This implementation wasn't preventing 'parent is not a directory'
> errors. Other than that the changes that are made are essentially
> cosmetic - consistent exceptions and catching corruption that we're very
> unlikely to cause.
>
> -Rob
>
>
The dirstate, doc and test changes look fine.

I'm really concerned though about the performance impact of calling
id2path for every entry in an inventory delta to do the additional
checks you've added. For chk-based inventories in particular, path
calculations *really* hurt performance.

Do you have any measurements re performance impact? I'm happy to help
here if you'd like.

Ian C.

[Robert Collins (lifeless)]

On Tue, 2009-07-14 at 04:21 +0000, Ian Clatworthy wrote:

> The dirstate, doc and test changes look fine.
>
> I'm really concerned though about the performance impact of calling
> id2path for every entry in an inventory delta to do the additional
> checks you've added. For chk-based inventories in particular, path
> calculations *really* hurt performance.
>
> Do you have any measurements re performance impact? I'm happy to help
> here if you'd like.

I don't, and I'd love some. id2path only occurs on the items being
changed, not on the full inventory so it should be tolerable (and
because its not path2id we load in the items we're changing and above
only). The effect on importers and commit should be marginal. I won't be
surprised if its visible, but even if it is I'm fairly sure that we need
this. Over the last week and a bit I've found a frighteningly large
number of ways to completely bork inventories via damaged deltas.

-Rob

[Robert Collins (lifeless)]

Ian report a test failure;
ERROR: per_repository.test_fetch.TestFetchSameRepository.test_fetch_to_rich_root_set_parent_1_parent_different_id_gone(RepositoryFormatCHK2)
#
    An inconsistent delta was supplied: [(('', ''), None, None), (None, ('', ''), 'my-root')]
#
reason: New items are already in the map [(('', ''), 'TREE_ROOT')].

This is a bogus delta new checks have uncovered; we need to fix the cause of this.

[Robert Collins (lifeless)]

also from igc
ERROR: per_inventory.basics.TestInventoryApplyDelta.test_apply_delta_delete(Inventory)
    An inconsistent delta was supplied involving 'a', None
reason: Entry with no new_path

(This indicates a broken sample delta, I suspect)

[Ian Clatworthy (ian-clatworthy)]

Running usertest on OOo comparing rev 4538 vs same+patch shows:

1. commit of a new files increasing from 1.9s to 2.1s
2. commit of a changed file increasing from 1.8s to 3.3s.

The former is probably ok; the latter needs investigation.

[Robert Collins (lifeless)]

On Thu, 2009-07-16 at 03:07 +0000, Ian Clatworthy wrote:
> Running usertest on OOo comparing rev 4538 vs same+patch shows:
>
> 1. commit of a new files increasing from 1.9s to 2.1s
> 2. commit of a changed file increasing from 1.8s to 3.3s.
>
> The former is probably ok; the latter needs investigation.

Is the commit of a changed file whole-tree or named file?

[Robert Collins (lifeless)]

On Thu, 2009-07-16 at 03:15 +0000, Robert Collins wrote:
> On Thu, 2009-07-16 at 03:07 +0000, Ian Clatworthy wrote:
> > Running usertest on OOo comparing rev 4538 vs same+patch shows:
> >
> > 1. commit of a new files increasing from 1.9s to 2.1s
> > 2. commit of a changed file increasing from 1.8s to 3.3s.
> >
> > The former is probably ok; the latter needs investigation.
>
> Is the commit of a changed file whole-tree or named file?

Ian says 'whole tree with one changed file'.

[Ian Clatworthy (ian-clatworthy)]

Robert Collins wrote:
> Robert Collins has proposed merging lp:~lifeless/bzr/apply-inventory-delta into lp:bzr.
>
>
>
Some feedback on the dirstate.py changes ...

> + try:
> + entry = self._dirblocks[block_i][1][entry_i]
> + except IndexError:
> + raise errors.InconsistentDelta(path, file_id,
> + "Wrong path for old path.")
> + if not f_present or entry[1][0][0] in 'ar':
> + raise errors.InconsistentDelta(path, file_id,
> + "Wrong path for old path.")
> + if file_id != entry[0][2]:
> + raise errors.InconsistentDelta(path, file_id,
> + "Attempt to remove wrong has wrong id - found %r."
> + % entry[0][2])
>

The first 2 messages here are identical. Is that by design or
cut-and-paste? (Sometimes it's worth making the messages slightly
different to assist support.)

The third message needs tweaking: "wrong has wrong ..."

> + # New record. Check there isn't a entry at this path already.
> + if not fullscan:
> + low_index, _ = self._find_entry_index(key[0:2] + ('',), block)
> + while low_index < len(block):
> + entry = block[low_index]
> + if entry[0][0:2] == key[0:2]:
> + if entry[1][0][0] not in 'ar':
> + # This entry has the same path (but a different id) as
> + # the new entry we're adding, and is present in ths
> + # tree.
> + raise errors.InconsistentDelta(
> + ("%s/%s" % key[0:2]).decode('utf8'), key[2],
> + "Attempt to add item at path already occupied by "
> + "id %r" % entry[0][2])
> + else:
> + break
>
The while loop looks like it can/will loop forever. Also s/ths/this/ in
the comment.

Ian C.

[Ian Clatworthy (ian-clatworthy)]

Doc changes and tests all look fine. More code feedback: I don't think it's safe removing these few lines from inventory.py ...

         for old_path, file_id in sorted(((op, f) for op, np, f, e in delta
                                         if op is not None), reverse=True):
- if file_id not in self:
- # adds come later
- continue
             # Preserve unaltered children of file_id for later reinsertion.
             file_id_children = getattr(self[file_id], 'children', {})

[Robert Collins (lifeless)]

On Thu, 2009-07-16 at 03:28 +0000, Ian Clatworthy wrote:

> Doc changes and tests all look fine. More code feedback: I don't think
> it's safe removing these few lines from inventory.py ...

Why not?

> for old_path, file_id in sorted(((op, f) for op, np, f, e in
> delta
> if op is not None),
> reverse=True):
> - if file_id not in self:
> - # adds come later
> - continue
> # Preserve unaltered children of file_id for later
> reinsertion.
> file_id_children = getattr(self[file_id], 'children', {})

If file_id is not in self, then the old_path must be None, or the delta
is deleting a file_id that isn't present. Thats a corrupt delta and we
should not silently accomodate that.

-Rob

[Ian Clatworthy (ian-clatworthy)]

Robert Collins wrote:
> On Thu, 2009-07-16 at 03:28 +0000, Ian Clatworthy wrote:
>
>
>> Doc changes and tests all look fine. More code feedback: I don't think
>> it's safe removing these few lines from inventory.py ...
>>
>
> Why not?
>
>
>> for old_path, file_id in sorted(((op, f) for op, np, f, e in
>> delta
>> if op is not None),
>> reverse=True):
>> - if file_id not in self:
>> - # adds come later
>> - continue
>> # Preserve unaltered children of file_id for later
>> reinsertion.
>> file_id_children = getattr(self[file_id], 'children', {})
>>
>
> If file_id is not in self, then the old_path must be None, or the delta
> is deleting a file_id that isn't present. Thats a corrupt delta and we
> should not silently accomodate that.
>
> -Rob
>
>
You need to trap the KeyError self[file_id] can throw if you remove it.

Ian C.

[Robert Collins (lifeless)]

On Thu, 2009-07-16 at 03:57 +0000, Ian Clatworthy wrote:

> You need to trap the KeyError self[file_id] can throw if you remove it.

In this branch I think there are tests that deleting an absent id raises
the right error. That code is dead code ;).

-Rob

[Ian Clatworthy (ian-clatworthy)]

See linked bug for callgrind before and after attachments.

review: Needs Fixing

[Robert Collins (lifeless)]

> Robert Collins wrote:
> > Robert Collins has proposed merging lp:~lifeless/bzr/apply-inventory-delta
> into lp:bzr.
> >
> >
> >
> Some feedback on the dirstate.py changes ...
>
> > + try:
> > + entry = self._dirblocks[block_i][1][entry_i]
> > + except IndexError:
> > + raise errors.InconsistentDelta(path, file_id,
> > + "Wrong path for old path.")
> > + if not f_present or entry[1][0][0] in 'ar':
> > + raise errors.InconsistentDelta(path, file_id,
> > + "Wrong path for old path.")
> > + if file_id != entry[0][2]:
> > + raise errors.InconsistentDelta(path, file_id,
> > + "Attempt to remove wrong has wrong id - found %r."
> > + % entry[0][2])
> >
>
> The first 2 messages here are identical. Is that by design or
> cut-and-paste? (Sometimes it's worth making the messages slightly
> different to assist support.)

Deliberate - its a series of checks with the same outcome.

> The third message needs tweaking: "wrong has wrong ..."

Changed: s/wrong has wrong/path has wrong/.

> The while loop looks like it can/will loop forever. Also s/ths/this/ in
> the comment.

Thanks, was missing a low_index += 1.

=== modified file 'NEWS'
--- NEWS	2009-07-16 08:00:03 +0000
+++ NEWS	2009-07-16 16:36:05 +0000
@@ -57,6 +57,13 @@
 Internals
 *********
 
+* ``CHKMap.apply_delta`` now raises ``InconsistentDelta`` if a delta adds
+  as new a key which was already mapped. (Robert Collins)
+
+* Inventory delta application catches more cases of corruption and can
+  prevent corrupt deltas from affecting consistency of data structures on
+  disk. (Robert Collins)
+
 
 bzr 1.17rc1 "So late it's brunch" 2009-07-13
 ############################################

=== modified file 'bzrlib/chk_map.py'
--- bzrlib/chk_map.py	2009-07-14 17:33:13 +0000
+++ bzrlib/chk_map.py	2009-07-16 16:36:05 +0000
@@ -26,9 +26,9 @@
 
 Updates to a CHKMap are done preferentially via the apply_delta method, to
 allow optimisation of the update operation; but individual map/unmap calls are
-possible and supported. All changes via map/unmap are buffered in memory until
-the _save method is called to force serialisation of the tree. apply_delta
-performs a _save implicitly.
+possible and supported. Individual changes via map/unmap are buffered in memory
+until the _save method is called to force serialisation of the tree.
+apply_delta records its changes immediately by performing an implicit _save.
 
 TODO:
 -----
@@ -41,7 +41,10 @@
 
 from bzrlib import lazy_import
 lazy_import.lazy_import(globals(), """
-from bzrlib import versionedfile
+from bzrlib import (
+    errors,
+    versionedfile,
+    )
 """)
 from bzrlib import (
     lru_cache,
@@ -105,6 +108,14 @@
             of old_key is removed.
         """
         delete_count = 0
+        # Check preconditions first.
+        new_items = set([key for (old, key, value) in delta if key is not None
+            and old is None])
+        existing_new = list(self.iteritems(key_filter=new_items))
+        if existing_new:
+            raise errors.InconsistentDeltaDelta(delta,
+                "New items are already in the map %r." % existing_new)
+        # Now apply changes.
         for old, new, value in delta:
             if old is not None and old != new:
                 self.unmap(old, check_remap=False)
@@ -482,7 +493,11 @@
         return len(self._root_node)
 
     def map(self, key, value):
-        """Map a key tuple to value."""
+        """Map a key tuple to value.
+        
+        :param key: A key to map.
+        :param value: The value to assign to key.
+        """
         # Need a root object.
         self._ensure_root()
         prefix, node_details = self._root_node.map(self._store, key, value)

=== modified file 'bzrlib/dirstate.py'
--- bzrlib/dirstate.py	2009-07-10 05:33:07 +0000
+++ bzrlib/dirstate.py	2009-07-16 16:36:05 +0000
@@ -204,6 +204,7 @@
 import bisect
 import binascii
 import errno
+import operator
 import os
 from stat import S_IEXEC
 import stat
@@ -1277,22 +1278,49 @@
     def update_by_delta(self, delta):
         """Apply an inventory delta to the dirstate for tree 0
 
+        This is the workhorse for apply_inventory_delta in dirstate based
+        trees.
+
         :param delta: An inventory delta.  See Inventory.apply_delta for
             details.
         """
         self._read_dirblocks_if_needed()
+        encode = cache_utf8.encode
         insertions = {}
         removals = {}
-        for old_path, new_path, file_id, inv_entry in sorted(delta, reverse=True):
+        # Accumulate parent references (path_utf8, id), to check for parentless
+        # items or items placed under files/links/tree-references. We get
+        # references from every item in the delta that is not a deletion and
+        # is not itself the root.
+        parents = set()
+        # Added ids must not be in the dirstate already. This set holds those
+        # ids.
+        new_ids = set()
+        # This loop transforms the delta to single atomic operations that can
+        # be executed and validated.
+        for old_path, new_path, file_id, inv_entry in sorted(
+            inventory._check_delta_unique_old_paths(
+            inventory._check_delta_unique_new_paths(
+            inventory._check_delta_ids_match_entry(
+            inventory._check_delta_new_path_entry_both_or_None(delta)))),
+            reverse=True):
             if (file_id in insertions) or (file_id in removals):
                 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
+            else:
+                new_ids.add(file_id)
             if new_path is not None:
+                if inv_entry is None:
+                    raise errors.InconsistentDelta(new_path, file_id,
+                        "new_path with no entry")
                 new_path = new_path.encode('utf-8')
                 dirname, basename = osutils.split(new_path)
+                dirname_utf8 = encode(dirname)
+                if basename:
+                    parents.add((dirname_utf8, inv_entry.parent_id))
                 key = (dirname, basename, file_id)
                 minikind = DirState._kind_to_minikind[inv_entry.kind]
                 if minikind == 't':
@@ -1321,15 +1349,39 @@
                                                   child_basename)
                     insertions[child[0][2]] = (key, minikind, executable,
                                                fingerprint, new_child_path)
-        self._apply_removals(removals.values())
-        self._apply_insertions(insertions.values())
+        self._check_delta_ids_absent(new_ids, delta, 0)
+        try:
+            self._apply_removals(removals.iteritems())
+            self._apply_insertions(insertions.values())
+            # Validate parents
+            self._after_delta_check_parents(parents, 0)
+        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.
+            self._changes_aborted = True
+            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
 
     def _apply_removals(self, removals):
-        for path in sorted(removals, reverse=True):
+        for file_id, path in sorted(removals, reverse=True,
+            key=operator.itemgetter(1)):
             dirname, basename = osutils.split(path)
             block_i, entry_i, d_present, f_present = \
                 self._get_block_entry_index(dirname, basename, 0)
-            entry = self._dirblocks[block_i][1][entry_i]
+            try:
+                entry = self._dirblocks[block_i][1][entry_i]
+            except IndexError:
+                raise errors.InconsistentDelta(path, file_id,
+                    "Wrong path for old path.")
+            if not f_present or entry[1][0][0] in 'ar':
+                raise errors.InconsistentDelta(path, file_id,
+                    "Wrong path for old path.")
+            if file_id != entry[0][2]:
+                raise errors.InconsistentDelta(path, file_id,
+                    "Attempt to remove wrong has wrong id - found %r."
+                    % entry[0][2])
             self._make_absent(entry)
             # See if we have a malformed delta: deleting a directory must not
             # leave crud behind. This increases the number of bisects needed
@@ -1348,9 +1400,13 @@
                             "not deleted.")
 
     def _apply_insertions(self, adds):
-        for key, minikind, executable, fingerprint, path_utf8 in sorted(adds):
-            self.update_minimal(key, minikind, executable, fingerprint,
-                                path_utf8=path_utf8)
+        try:
+            for key, minikind, executable, fingerprint, path_utf8 in sorted(adds):
+                self.update_minimal(key, minikind, executable, fingerprint,
+                                    path_utf8=path_utf8)
+        except errors.NotVersionedError:
+            raise errors.InconsistentDelta(path_utf8.decode('utf8'), key[2],
+                "Missing parent")
 
     def update_basis_by_delta(self, delta, new_revid):
         """Update the parents of this tree after a commit.
@@ -1400,16 +1456,22 @@
         # 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
+        # Accumulate parent references (path_utf8, id), to check for parentless
         # items or items placed under files/links/tree-references. We get
         # references from every item in the delta that is not a deletion and
         # is not itself the root.
         parents = set()
+        # Added ids must not be in the dirstate already. This set holds those
+        # ids.
+        new_ids = 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:
+                if inv_entry is None:
+                    raise errors.InconsistentDelta(new_path, file_id,
+                        "new_path with no entry")
                 new_path_utf8 = encode(new_path)
                 # note the parent for validation
                 dirname_utf8, basename_utf8 = osutils.split(new_path_utf8)
@@ -1418,6 +1480,7 @@
             if old_path is None:
                 adds.append((None, encode(new_path), file_id,
                     inv_to_entry(inv_entry), True))
+                new_ids.add(file_id)
             elif new_path is None:
                 deletes.append((encode(old_path), None, file_id, None, True))
             elif (old_path, new_path) != root_only:
@@ -1466,7 +1529,7 @@
                 # of everything.
                 changes.append((encode(old_path), encode(new_path), file_id,
                     inv_to_entry(inv_entry)))
-
+        self._check_delta_ids_absent(new_ids, delta, 1)
         try:
             # Finish expunging deletes/first half of renames.
             self._update_basis_apply_deletes(deletes)
@@ -1475,7 +1538,7 @@
             # Apply in-situ changes.
             self._update_basis_apply_changes(changes)
             # Validate parents
-            self._update_basis_check_parents(parents)
+            self._after_delta_check_parents(parents, 1)
         except errors.BzrError, e:
             if 'integrity error' not in str(e):
                 raise
@@ -1492,6 +1555,29 @@
         self._id_index = None
         return
 
+    def _check_delta_ids_absent(self, new_ids, delta, tree_index):
+        """Check that none of the file_ids in new_ids are present in a tree."""
+        if not new_ids:
+            return
+        id_index = self._get_id_index()
+        for file_id in new_ids:
+            for key in id_index.get(file_id, []):
+                block_i, entry_i, d_present, f_present = \
+                    self._get_block_entry_index(key[0], key[1], tree_index)
+                if not f_present:
+                    # In a different tree
+                    continue
+                entry = self._dirblocks[block_i][1][entry_i]
+                if entry[0][2] != file_id:
+                    # Different file_id, so not what we want.
+                    continue
+                # NB: No changes made before this helper is called, so no need
+                # to set the _changes_aborted flag.
+                raise errors.InconsistentDelta(
+                    ("%s/%s" % key[0:2]).decode('utf8'), file_id,
+                    "This file_id is new in the delta but already present in "
+                    "the target")
+
     def _update_basis_apply_adds(self, adds):
         """Apply a sequence of adds to tree 1 during update_basis_by_delta.
 
@@ -1600,18 +1686,24 @@
                     # 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."""
+    def _after_delta_check_parents(self, parents, index):
+        """Check that parents required by the delta are all intact.
+        
+        :param parents: An iterable of (path_utf8, file_id) tuples which are
+            required to be present in tree 'index' at path_utf8 with id file_id
+            and be a directory.
+        :param index: The column in the dirstate to check for parents in.
+        """
         for dirname_utf8, file_id in parents:
             # Get the entry - the ensures that file_id, dirname_utf8 exists and
             # has the right file id.
-            entry = self._get_entry(1, file_id, dirname_utf8)
+            entry = self._get_entry(index, file_id, dirname_utf8)
             if entry[1] is None:
                 self._changes_aborted = True
                 raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
                     file_id, "This parent is not present.")
             # Parents of things must be directories
-            if entry[1][1][0] != 'd':
+            if entry[1][index][0] != 'd':
                 self._changes_aborted = True
                 raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
                     file_id, "This parent is not a directory.")
@@ -2478,7 +2570,8 @@
                 # old is finished: insert current_new into the state.
                 self.update_minimal(new_entry_key, current_new_minikind,
                     executable=current_new[1].executable,
-                    path_utf8=new_path_utf8, fingerprint=fingerprint)
+                    path_utf8=new_path_utf8, fingerprint=fingerprint,
+                    fullscan=True)
                 current_new = advance(new_iterator)
             elif not current_new:
                 # new is finished
@@ -2496,7 +2589,8 @@
                     current_old[1][0][0] != current_new_minikind):
                     self.update_minimal(current_old[0], current_new_minikind,
                         executable=current_new[1].executable,
-                        path_utf8=new_path_utf8, fingerprint=fingerprint)
+                        path_utf8=new_path_utf8, fingerprint=fingerprint,
+                        fullscan=True)
                 # both sides are dealt with, move on
                 current_old = advance(old_iterator)
                 current_new = advance(new_iterator)
@@ -2507,7 +2601,8 @@
                 # add a entry for this and advance new
                 self.update_minimal(new_entry_key, current_new_minikind,
                     executable=current_new[1].executable,
-                    path_utf8=new_path_utf8, fingerprint=fingerprint)
+                    path_utf8=new_path_utf8, fingerprint=fingerprint,
+                    fullscan=True)
                 current_new = advance(new_iterator)
             else:
                 # we've advanced past the place where the old key would be,
@@ -2571,7 +2666,7 @@
         return last_reference
 
     def update_minimal(self, key, minikind, executable=False, fingerprint='',
-                       packed_stat=None, size=0, path_utf8=None):
+        packed_stat=None, size=0, path_utf8=None, fullscan=False):
         """Update an entry to the state in tree 0.
 
         This will either create a new entry at 'key' or update an existing one.
@@ -2588,6 +2683,9 @@
         :param size: Size information for new entry
         :param path_utf8: key[0] + '/' + key[1], just passed in to avoid doing
                 extra computation.
+        :param fullscan: If True then a complete scan of the dirstate is being
+            done and checking for duplicate rows should not be done. This
+            should only be set by set_state_from_inventory and similar methods.
 
         If packed_stat and fingerprint are not given, they're invalidated in
         the entry.
@@ -2602,6 +2700,22 @@
         new_details = (minikind, fingerprint, size, executable, packed_stat)
         id_index = self._get_id_index()
         if not present:
+            # New record. Check there isn't a entry at this path already.
+            if not fullscan:
+                low_index, _ = self._find_entry_index(key[0:2] + ('',), block)
+                while low_index < len(block):
+                    entry = block[low_index]
+                    if entry[0][0:2] == key[0:2]:
+                        if entry[1][0][0] not in 'ar':
+                            # This entry has the same path (but a different id) as
+                            # the new entry we're adding, and is present in ths
+                            # tree.
+                            raise errors.InconsistentDelta(
+                                ("%s/%s" % key[0:2]).decode('utf8'), key[2],
+                                "Attempt to add item at path already occupied by "
+                                "id %r" % entry[0][2])
+                    else:
+                        break
             # new entry, synthesis cross reference here,
             existing_keys = id_index.setdefault(key[2], set())
             if not existing_keys:

=== modified file 'bzrlib/inventory.py'
--- bzrlib/inventory.py	2009-07-10 05:18:29 +0000
+++ bzrlib/inventory.py	2009-07-16 16:36:05 +0000
@@ -1089,6 +1089,9 @@
         See the inventory developers documentation for the theory behind
         inventory deltas.
 
+        If delta application fails the inventory is left in an indeterminate
+        state and must not be used.
+
         :param delta: A list of changes to apply. After all the changes are
             applied the final inventory must be internally consistent, but it
             is ok to supply changes which, if only half-applied would have an
@@ -1129,7 +1132,8 @@
         # facility.
         list(_check_delta_unique_ids(_check_delta_unique_new_paths(
             _check_delta_unique_old_paths(_check_delta_ids_match_entry(
-            delta)))))
+            _check_delta_new_path_entry_both_or_None(
+            delta))))))
 
         children = {}
         # Remove all affected items which were in the original inventory,
@@ -1138,13 +1142,13 @@
         # modified children remaining by the time we examine it.
         for old_path, file_id in sorted(((op, f) for op, np, f, e in delta
                                         if op is not None), reverse=True):
-            if file_id not in self:
-                # adds come later
-                continue
             # Preserve unaltered children of file_id for later reinsertion.
             file_id_children = getattr(self[file_id], 'children', {})
             if len(file_id_children):
                 children[file_id] = file_id_children
+            if self.id2path(file_id) != old_path:
+                raise errors.InconsistentDelta(old_path, file_id,
+                    "Entry was at wrong other path %r." % self.id2path(file_id))
             # Remove file_id and the unaltered children. If file_id is not
             # being deleted it will be reinserted back later.
             self.remove_recursive_id(file_id)
@@ -1153,7 +1157,7 @@
         # longest, ensuring that items which were modified and whose parents in
         # the resulting inventory were also modified, are inserted after their
         # parents.
-        for new_path, new_entry in sorted((np, e) for op, np, f, e in
+        for new_path, f, new_entry in sorted((np, f, e) for op, np, f, e in
                                           delta if np is not None):
             if new_entry.kind == 'directory':
                 # Pop the child which to allow detection of children whose
@@ -1166,9 +1170,15 @@
                 new_entry = replacement
             try:
                 self.add(new_entry)
+            except errors.DuplicateFileId:
+                raise errors.InconsistentDelta(new_path, new_entry.file_id,
+                    "New id is already present in target.")
             except AttributeError:
                 raise errors.InconsistentDelta(new_path, new_entry.file_id,
                     "Parent is not a directory.")
+            if self.id2path(new_entry.file_id) != new_path:
+                raise errors.InconsistentDelta(new_path, new_entry.file_id,
+                    "New path is not consistent with parent path.")
         if len(children):
             # Get the parent id that was deleted
             parent_id, children = children.popitem()
@@ -1254,12 +1264,11 @@
         To add  a file to a branch ready to be committed, use Branch.add,
         which calls this.
 
-        Returns the new entry object.
+        :return: entry
         """
         if entry.file_id in self._byid:
             raise errors.DuplicateFileId(entry.file_id,
                                          self._byid[entry.file_id])
-
         if entry.parent_id is None:
             self.root = entry
         else:
@@ -1590,6 +1599,7 @@
           copied to and updated for the result.
         :return: The new CHKInventory.
         """
+        split = osutils.split
         result = CHKInventory(self._search_key_name)
         if propagate_caches:
             # Just propagate the path-to-fileid cache for now
@@ -1630,8 +1640,18 @@
         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.
+        # Check for new_path <-> entry consistency
+        inventory_delta = _check_delta_new_path_entry_both_or_None(
+            inventory_delta)
+        # All changed entries need to have their parents be directories and be
+        # at the right path. This set contains (path, id) tuples.
         parents = set()
+        # When we delete an item, all the children of it must be either deleted
+        # or altered in their own right. As we batch process the change via
+        # CHKMap.apply_delta, we build a set of things to use to validate the
+        # delta.
+        deletes = set()
+        altered = set()
         for old_path, new_path, file_id, entry in inventory_delta:
             # file id changes
             if new_path == '':
@@ -1646,17 +1666,23 @@
                         del result._path_to_fileid_cache[old_path]
                     except KeyError:
                         pass
+                deletes.add(file_id)
             else:
                 new_key = (file_id,)
                 new_value = result._entry_to_bytes(entry)
                 # 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)
+                parents.add((split(new_path)[0], entry.parent_id))
             if old_path is None:
                 old_key = None
             else:
                 old_key = (file_id,)
+                if self.id2path(file_id) != old_path:
+                    raise errors.InconsistentDelta(old_path, file_id,
+                        "Entry was at wrong other path %r." %
+                        self.id2path(file_id))
+                altered.add(file_id)
             id_to_entry_delta.append((old_key, new_key, new_value))
             if result.parent_id_basename_to_file_id is not None:
                 # parent_id, basename changes
@@ -1675,11 +1701,23 @@
                     # If the two keys are the same, the value will be unchanged
                     # as its always the file id.
                     parent_id_basename_delta.append((old_key, new_key, new_value))
+        # validate that deletes are complete.
+        for file_id in deletes:
+            entry = self[file_id]
+            if entry.kind != 'directory':
+                continue
+            # This loop could potentially be better by using the id_basename
+            # map to just get the child file ids.
+            for child in entry.children.values():
+                if child.file_id not in altered:
+                    raise errors.InconsistentDelta(self.id2path(child.file_id),
+                        child.file_id, "Child not deleted or reparented when "
+                        "parent deleted.")
         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)
-        parents.discard(None)
-        for parent in parents:
+        parents.discard(('', None))
+        for parent_path, parent in parents:
             try:
                 if result[parent].kind != 'directory':
                     raise errors.InconsistentDelta(result.id2path(parent), parent,
@@ -1687,6 +1725,9 @@
             except errors.NoSuchId:
                 raise errors.InconsistentDelta("<unknown>", parent,
                     "Parent is not present in resulting inventory.")
+            if result.path2id(parent_path) != parent:
+                raise errors.InconsistentDelta(parent_path, parent,
+                    "Parent has wrong path %r." % result.path2id(parent_path))
         return result
 
     @classmethod
@@ -2156,3 +2197,20 @@
                 raise errors.InconsistentDelta(item[0] or item[1], item[2],
                     "mismatched id with %r" % entry)
         yield item
+
+
+def _check_delta_new_path_entry_both_or_None(delta):
+    """Decorate a delta and check that the new_path and entry are paired.
+
+    :return: A generator over delta.
+    """
+    for item in delta:
+        new_path = item[1]
+        entry = item[3]
+        if new_path is None and entry is not None:
+            raise errors.InconsistentDelta(item[0], item[1],
+                "Entry with no new_path")
+        if new_path is not None and entry is None:
+            raise errors.InconsistentDelta(new_path, item[1],
+                "new_path with no entry")
+        yield item

=== modified file 'bzrlib/tests/test_chk_map.py'
--- bzrlib/tests/test_chk_map.py	2009-07-14 17:33:13 +0000
+++ bzrlib/tests/test_chk_map.py	2009-07-16 16:36:05 +0000
@@ -20,7 +20,11 @@
 
 from bzrlib import (
     chk_map,
+<<<<<<< TREE
     groupcompress,
+=======
+    errors,
+>>>>>>> MERGE-SOURCE
     osutils,
     tests,
     )
@@ -466,6 +470,18 @@
         # updated key.
         self.assertEqual(new_root, chkmap._root_node._key)
 
+    def test_apply_new_keys_must_be_new(self):
+        # applying a delta (None, "a", "b") to a map with 'a' in it generates
+        # an error.
+        chk_bytes = self.get_chk_bytes()
+        root_key = CHKMap.from_dict(chk_bytes, {("a",):"b"})
+        chkmap = CHKMap(chk_bytes, root_key)
+        self.assertRaises(errors.InconsistentDelta, chkmap.apply_delta,
+            [(None, ("a",), "b")])
+        # As an error occured, the update should have left us without changing
+        # anything (the root should be unchanged).
+        self.assertEqual(root_key, chkmap._root_node._key)
+
     def test_apply_delta_is_deterministic(self):
         chk_bytes = self.get_chk_bytes()
         chkmap1 = CHKMap(chk_bytes, None)

=== modified file 'bzrlib/tests/test_inv.py'
--- bzrlib/tests/test_inv.py	2009-07-10 12:40:36 +0000
+++ bzrlib/tests/test_inv.py	2009-07-16 16:36:05 +0000
@@ -54,9 +54,14 @@
             'apply_delta':apply_inventory_Repository_add_inventory_by_delta,
             'format':format}))
     for format in workingtree_formats():
-        scenarios.append((str(format.__class__.__name__), {
+        scenarios.append(
+            (str(format.__class__.__name__) + ".update_basis_by_delta", {
             'apply_delta':apply_inventory_WT_basis,
             'format':format}))
+        scenarios.append(
+            (str(format.__class__.__name__) + ".apply_inventory_delta", {
+            'apply_delta':apply_inventory_WT,
+            'format':format}))
     return multiply_tests(to_adapt, scenarios, result)
 
 
@@ -71,6 +76,42 @@
     return basis
 
 
+def apply_inventory_WT(self, basis, delta):
+    """Apply delta to basis and return the result.
+
+    This sets the tree state to be basis, and then calls apply_inventory_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:
+        tree._write_inventory(basis)
+    finally:
+        tree.unlock()
+    # Fresh object, reads disk again.
+    tree = tree.bzrdir.open_workingtree()
+    tree.lock_write()
+    try:
+        tree.apply_inventory_delta(delta)
+    finally:
+        tree.unlock()
+    # reload tree - ensure we get what was written.
+    tree = tree.bzrdir.open_workingtree()
+    tree.lock_read()
+    self.addCleanup(tree.unlock)
+    # One could add 'tree._validate' here but that would cause 'early' failues 
+    # as far as higher level code is concerned. Possibly adding an
+    # expect_fail parameter to this function and if that is False then do a
+    # validate call.
+    return tree.inventory
+
+
 def apply_inventory_WT_basis(self, basis, delta):
     """Apply delta to basis and return the result.
 
@@ -118,7 +159,7 @@
         paths = {}
         parents = set()
         for old, new, id, entry in delta:
-            if entry is None:
+            if None in (new, entry):
                 continue
             paths[new] = (entry.file_id, entry.kind)
             parents.add(osutils.dirname(new))
@@ -296,6 +337,22 @@
         self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
             inv, delta)
 
+    def test_mismatched_new_path_entry_None(self):
+        inv = self.get_empty_inventory()
+        delta = [(None, u'path', 'id', None)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
+
+    def test_mismatched_new_path_None_entry(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 = [(u"path", None, 'id1', 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)
@@ -321,6 +378,106 @@
         self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
             inv, delta)
 
+    def test_new_parent_path_has_wrong_id(self):
+        inv = self.get_empty_inventory()
+        parent1 = inventory.InventoryDirectory('p-1', 'dir', inv.root.file_id)
+        parent1.revision = 'result'
+        parent2 = inventory.InventoryDirectory('p-2', 'dir2', inv.root.file_id)
+        parent2.revision = 'result'
+        file1 = inventory.InventoryFile('id', 'path', 'p-2')
+        file1.revision = 'result'
+        file1.text_size = 0
+        file1.text_sha1 = ""
+        inv.add(parent1)
+        inv.add(parent2)
+        # This delta claims that file1 is at dir/path, but actually its at
+        # dir2/path if you follow the inventory parent structure.
+        delta = [(None, u'dir/path', 'id', file1)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
+
+    def test_old_parent_path_is_wrong(self):
+        inv = self.get_empty_inventory()
+        parent1 = inventory.InventoryDirectory('p-1', 'dir', inv.root.file_id)
+        parent1.revision = 'result'
+        parent2 = inventory.InventoryDirectory('p-2', 'dir2', inv.root.file_id)
+        parent2.revision = 'result'
+        file1 = inventory.InventoryFile('id', 'path', 'p-2')
+        file1.revision = 'result'
+        file1.text_size = 0
+        file1.text_sha1 = ""
+        inv.add(parent1)
+        inv.add(parent2)
+        inv.add(file1)
+        # This delta claims that file1 was at dir/path, but actually it was at
+        # dir2/path if you follow the inventory parent structure.
+        delta = [(u'dir/path', None, 'id', None)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
+
+    def test_old_parent_path_is_for_other_id(self):
+        inv = self.get_empty_inventory()
+        parent1 = inventory.InventoryDirectory('p-1', 'dir', inv.root.file_id)
+        parent1.revision = 'result'
+        parent2 = inventory.InventoryDirectory('p-2', 'dir2', inv.root.file_id)
+        parent2.revision = 'result'
+        file1 = inventory.InventoryFile('id', 'path', 'p-2')
+        file1.revision = 'result'
+        file1.text_size = 0
+        file1.text_sha1 = ""
+        file2 = inventory.InventoryFile('id2', 'path', 'p-1')
+        file2.revision = 'result'
+        file2.text_size = 0
+        file2.text_sha1 = ""
+        inv.add(parent1)
+        inv.add(parent2)
+        inv.add(file1)
+        inv.add(file2)
+        # This delta claims that file1 was at dir/path, but actually it was at
+        # dir2/path if you follow the inventory parent structure. At dir/path
+        # is another entry we should not delete.
+        delta = [(u'dir/path', None, 'id', None)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
+
+    def test_add_existing_id_new_path(self):
+        inv = self.get_empty_inventory()
+        parent1 = inventory.InventoryDirectory('p-1', 'dir1', inv.root.file_id)
+        parent1.revision = 'result'
+        parent2 = inventory.InventoryDirectory('p-1', 'dir2', inv.root.file_id)
+        parent2.revision = 'result'
+        inv.add(parent1)
+        delta = [(None, u'dir2', 'p-1', parent2)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
+
+    def test_add_new_id_existing_path(self):
+        inv = self.get_empty_inventory()
+        parent1 = inventory.InventoryDirectory('p-1', 'dir1', inv.root.file_id)
+        parent1.revision = 'result'
+        parent2 = inventory.InventoryDirectory('p-2', 'dir1', inv.root.file_id)
+        parent2.revision = 'result'
+        inv.add(parent1)
+        delta = [(None, u'dir1', 'p-2', parent2)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
+
+    def test_remove_dir_leaving_dangling_child(self):
+        inv = self.get_empty_inventory()
+        dir1 = inventory.InventoryDirectory('p-1', 'dir1', inv.root.file_id)
+        dir1.revision = 'result'
+        dir2 = inventory.InventoryDirectory('p-2', 'child1', 'p-1')
+        dir2.revision = 'result'
+        dir3 = inventory.InventoryDirectory('p-3', 'child2', 'p-1')
+        dir3.revision = 'result'
+        inv.add(dir1)
+        inv.add(dir2)
+        inv.add(dir3)
+        delta = [(u'dir1', None, 'p-1', None),
+            (u'dir1/child2', None, 'p-3', None)]
+        self.assertRaises(errors.InconsistentDelta, self.apply_delta, self,
+            inv, delta)
+
 
 class TestInventoryEntry(TestCase):
 

=== modified file 'doc/developers/inventory.txt'
--- doc/developers/inventory.txt	2009-07-02 07:22:27 +0000
+++ doc/developers/inventory.txt	2009-07-16 16:36:05 +0000
@@ -545,6 +545,8 @@
    times.
  - has a fileid field different to the entry.fileid in the same item in the
    delta.
+ - has an entry that is in an impossible state (e.g. a directory with a text
+   size)
 
 Forms of inventory inconsistency deltas can carry/cause:
  - An entry newly introduced to a path without also removing or relocating any
@@ -554,6 +556,7 @@
    (Wrong path)
  - An entry whose parent is not a directory. (Under non-directory).
  - An entry that is internally inconsistent.
+ - An entry that is already present in the tree (Duplicate id)
 
 Known causes of inconsistency:
  - A 'new' entry which the inventory already has - when this is a directory