Merge lp:~vila/bzr/375898-fix-root-more into lp:bzr/2.0

[Vincent Ladeuil]

(vila) Don't crash when merging from an already merged other root

This fixes bug #375898.
The scenario was a bit complex:
- a previously unrelated branch is imported with its history,
- more changes are made to the imported branch,
- in the main branch, a file is deleted (it came from the imported branch),
- subsequent merges fail

Long story short, there were still grey areas in the interactions between merge
and transform when tree root are involved.

Yet, we have a pretty good coverage from a high level that cover all the know
use cases (I had to try numerous different approaches before getting it right
(with jam's help and then some)).

The unit tests are lacking though and we may want to revisit that later (but I'm
out of steam for that right now).

Since the fix is simple but the problem can be encountered quite easily, I've proposed
against 2.0.

The fix itself, while correct and quite small leave me a bit unsatisfied since its
aim is to fix paths that weren't introduced correctly in the first place.

But I couldn't find the right way to do that (I strongly suspect something
wrong with _merge_names, but the lack of unit tests makes it too hard to verify).

Summary: John has been involved enough to get the review token, especially
since, in the end, I didn't use all of his proposed patches :)

[John A Meinel (jameinel)]

Cut and paste of my email, since Launchpad aborted with "something wrong":

Vincent Ladeuil wrote:
> > You have been requested to review the proposed merge of lp:~vila/bzr/375898-fix-root-more into lp:bzr/2.0.
...

> >
> > Summary: John has been involved enough to get the review token, especially
> > since, in the end, I didn't use all of his proposed patches :)

If I understand correctly you now:

1) Status quo and don't record a path for the other root (didn't change
merge_names)
2) Update fix_root() to handle when other_root isn't present in this,
but there may be children of it anyway.

I still think I'd prefer to update _merge_names, but you've clearly
fixed the immediate cases. As you mentioned, the test coverage seems
sufficient.

+ present = True
         except NoSuchFile:
- return
+ # The other root hasn't been added or versioned, so we're
done for
+ # now
+ present = False

^- The comment here is certainly wrong now. Perhaps something like:

# other_root doesn't have a physical representation. We still need to
# move any references to the actual root of the tree.

+ if not present:
+ try:
+ # If the other root is not in the current tree, we
don't
+ # reparent file and dirs that are expected in the final
+ # tree. These paths where preventively introduced in
+ # _merge_names for possible conflicts. We may want
to find
+ # a better way -- vila 20100401
+ self.tt.final_kind(trans_id)
+ self.tt.final_name(trans_id)
+ continue
+ except (errors.NoFinalPath, errors.NoSuchFile), e:
+ pass

^- This section is a bit ugly. Certainly it seems to be necessary, but
it certainly feels like 'accumulating cruft'. The paragraph is a bit
hard to read. How about:

 rename "present" to "parent_is_present"

Change the block to:

if not parent_is_present:
    # 'ie' is not present in this tree. We are calling reparent so that
    # children which *want* to be present have a place to go.
    # So we check to see which children want to be present but can't,
    # and skip the rest.
    try:
      self.tt.final_kind(trans_id):
      self.tt.final_name(trans_id):
    except (errors.NoSuchFile, errors.NoFinalPath), e:
      pass # The file wants to be present, but doesn't have a location
    else:
      continue
self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)

However, in working through this logic, I'm pretty sure it is wrong.
Specifically, consider the case where "final_name" raises an exception.
You then have:

if not present:
  try:
    self.tt.final_name(trans_id) # raises exception
  except ... :
    pass:
self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)

Clearly the *second* call to 'self.tt.final_name()' is going to raise an
exception *again*.

So if the code you have is correct, then it is correct if you just
remove the 'self.tt.final_name(trans_id)' from the inner try/except.

I'm hesitant, but okay with landing the patch. You've pretty clearl...

review: Needs Fixing

[lp:~vila/bzr/375898-fix-root-more]

4749. By Vincent Ladeuil on 2010-04-02

Fixed as per John's review comments.

* bzrlib/merge.py:
(Merge3Merger.fix_root): Delete the useless (and bogus)
final_name() call, inline reparent_children and fix the comments.

[Vincent Ladeuil (vila)]

>>>>> "jam" == John A Meinel <email address hidden> writes:

<snip/>

    jam> If I understand correctly you now:

    jam> 1) Status quo and don't record a path for the other root (didn't change
    jam> merge_names)

Yes, funnily (?) I'm in the same position ("doesn't make sense") as you
but on different points.

_merge_names() switch the winners when this_name is None. While this is
"correct" since many tests break if you change that, I still consider it
a bug.

    jam> 2) Update fix_root() to handle when other_root isn't present in this,
    jam> but there may be children of it anyway.

    jam> I still think I'd prefer to update _merge_names, but you've
    jam> clearly fixed the immediate cases.

I reverted that because, while it was making the whole code more
coherent, it was adding cruft and blurry my understanding even more than
the let-switch-the-winners-just-because.

So, if I put back your patch to _merge_names, 6 tests are failing with
CantMoveRoot including:

^^^^[log from bzrlib.tests.per_workingtree.test_merge_from_branch.TestMergedBranch.test_file3_in_root_conflicted(WorkingTreeFormat5)]
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/vila/src/bzr/bugs/375898-new-root/bzrlib/tests/per_workingtree/test_merge_from_branch.py", line 204, in test_file3_in_root_conflicted
    nb_conflicts = outer.merge_from_branch(inner, to_revision='3')
  File "/home/vila/src/bzr/bugs/375898-new-root/bzrlib/decorators.py", line 192, in write_locked
    result = unbound(self, *args, **kwargs)
  File "/home/vila/src/bzr/bugs/375898-new-root/bzrlib/workingtree.py", line 942, in merge_from_branch
    conflicts = merger.do_merge()
  File "/home/vila/src/bzr/bugs/375898-new-root/bzrlib/merge.py", line 508, in do_merge
    self._do_merge_to(merge)
  File "/home/vila/src/bzr/bugs/375898-new-root/bzrlib/merge.py", line 480, in _do_merge_to
    merge.do_merge()
  File "/home/vila/src/bzr/bugs/375898-new-root/bzrlib/merge.py", line 620, in do_merge
    self._compute_transform()
  File "/home/vila/src/bzr/bugs/375898-new-root/bzrlib/merge.py", line 676, in _compute_transform
    lambda t, c: conflict_pass(t, c, self.other_tree))
  File "/home/vila/src/bzr/bugs/375898-new-root/bzrlib/transform.py", line 2742, in resolve_conflicts
    new_conflicts.update(pass_func(tt, conflicts))
  File "/home/vila/src/bzr/bugs/375898-new-root/bzrlib/merge.py", line 676, in <lambda>
    lambda t, c: conflict_pass(t, c, self.other_tree))
  File "/home/vila/src/bzr/bugs/375898-new-root/bzrlib/transform.py", line 2769, in conflict_pass
    tt.adjust_path(new_name, final_parent, existing_file)
  File "/home/vila/src/bzr/bugs/375898-new-root/bzrlib/transform.py", line 1135, in adjust_path
    TreeTransformBase.adjust_path(self, name, parent, trans_id)
  File "/home/vila/src/bzr/bugs/375898-new-root/bzrlib/transform.py", line 167, in adjust_path
    raise CantMoveRoot
CantMoveRoot: Moving the root directory is not supported at this time

Note that the traceback above shows that we have already called
fix_root() at this point and doing so we have tried to move the root
which is wrong. The test doesn't attempt...

[lp:~vila/bzr/375898-fix-root-more]

4750. By Vincent Ladeuil on 2010-04-02

Fix typo.

[Vincent Ladeuil (vila)]

Fed to pqm

star-merge http://bazaar.launchpad.net/~vila/bzr/375898-fix-root-more http://bazaar.launchpad.net/~bzr-pqm/bzr/2.0

=== modified file 'NEWS'
--- NEWS	2010-03-25 02:01:47 +0000
+++ NEWS	2010-04-02 12:47:23 +0000
@@ -22,6 +22,9 @@
   permissions as ``.bzr`` directory on a POSIX OS.
   (Parth Malwankar, #262450)
 
+* Additional merges after an unrelated branch has been merged with its
+  history no longer crash when deleted files are involved.
+  (Vincent Ladeuil, John Arbash Meinel, #375898)
 
 bzr 2.0.5
 #########

=== modified file 'bzrlib/merge.py'
--- bzrlib/merge.py	2009-10-27 09:45:35 +0000
+++ bzrlib/merge.py	2010-04-02 12:47:23 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2005, 2006, 2008 Canonical Ltd
+# Copyright (C) 2005-2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -901,21 +901,38 @@
         other_root = self.tt.trans_id_file_id(other_root_file_id)
         if other_root == self.tt.root:
             return
+        if self.other_tree.inventory.root.file_id in self.this_tree.inventory:
+            # the other tree's root is a non-root in the current tree (as when
+            # a previously unrelated branch is merged into another)
+            return
         try:
             self.tt.final_kind(other_root)
+            other_root_is_present = True
         except NoSuchFile:
-            return
-        if self.other_tree.inventory.root.file_id in self.this_tree.inventory:
-            # the other tree's root is a non-root in the current tree
-            return
-        self.reparent_children(self.other_tree.inventory.root, self.tt.root)
-        self.tt.cancel_creation(other_root)
-        self.tt.cancel_versioning(other_root)
-
-    def reparent_children(self, ie, target):
-        for thing, child in ie.children.iteritems():
+            # other_root doesn't have a physical representation. We still need
+            # to move any references to the actual root of the tree.
+            other_root_is_present = False
+        # 'other_tree.inventory.root' is not present in this tree. We are
+        # calling adjust_path for children which *want* to be present with a
+        # correct place to go.
+        for thing, child in self.other_tree.inventory.root.children.iteritems():
             trans_id = self.tt.trans_id_file_id(child.file_id)
-            self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)
+            if not other_root_is_present:
+                # FIXME: Make final_kind returns None instead of raising
+                # NoSuchFile to avoid the ugly construct below -- vila 20100402
+                try:
+                    self.tt.final_kind(trans_id)
+                    # The item exist in the final tree and has a defined place
+                    # to go already.
+                    continue
+                except errors.NoSuchFile, e:
+                    pass
+            # Move the item into the root
+            self.tt.adjust_path(self.tt.final_name(trans_id),
+                                self.tt.root, trans_id)
+        if other_root_is_present:
+            self.tt.cancel_creation(other_root)
+            self.tt.cancel_versioning(other_root)
 
     def write_modified(self, results):
         modified_hashes = {}

=== modified file 'bzrlib/tests/per_workingtree/test_merge_from_branch.py'
--- bzrlib/tests/per_workingtree/test_merge_from_branch.py	2009-07-10 07:14:02 +0000
+++ bzrlib/tests/per_workingtree/test_merge_from_branch.py	2010-04-02 12:47:23 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2006 Canonical Ltd
+# Copyright (C) 2006-2010 Canonical Ltd
 # Authors:  Robert Collins <[e-mail]>
 #
 # This program is free software; you can redistribute it and/or modify
@@ -20,13 +20,14 @@
 import os
 
 from bzrlib import (
+    branchbuilder,
     errors,
     merge
     )
-from bzrlib.tests.per_workingtree import TestCaseWithWorkingTree
-
-
-class TestMergeFromBranch(TestCaseWithWorkingTree):
+from bzrlib.tests import per_workingtree
+
+
+class TestMergeFromBranch(per_workingtree.TestCaseWithWorkingTree):
 
     def create_two_trees_for_merging(self):
         """Create two trees that can be merged from.
@@ -114,3 +115,103 @@
                 self.tt.create_file('qux', trans_id)
         this.merge_from_branch(other.branch, merge_type=QuxMerge)
         self.assertEqual('qux', this.get_file_text('foo-id'))
+
+
+class TestMergedBranch(per_workingtree.TestCaseWithWorkingTree):
+
+    def make_branch_builder(self, relpath, format=None):
+        if format is None:
+            format = self.bzrdir_format
+        builder = branchbuilder.BranchBuilder(self.get_transport(),
+                                              format=format)
+        return builder
+
+    def make_inner_branch(self):
+        bld_inner = self.make_branch_builder('inner')
+        bld_inner.start_series()
+        bld_inner.build_snapshot(
+            '1', None,
+            [('add', ('', 'inner-root-id', 'directory', '')),
+             ('add', ('dir', 'dir-id', 'directory', '')),
+             ('add', ('dir/file1', 'file1-id', 'file', 'file1 content\n')),
+             ('add', ('file3', 'file3-id', 'file', 'file3 content\n')),
+             ])
+        bld_inner.build_snapshot(
+            '3', ['1'], [('modify', ('file3-id', 'new file3 contents\n')),])
+        bld_inner.build_snapshot(
+            '2', ['1'],
+            [('add', ('dir/file2', 'file2-id', 'file', 'file2 content\n')),
+             ])
+        bld_inner.finish_series()
+        br = bld_inner.get_branch()
+        return br
+
+    def assertTreeLayout(self, expected, tree):
+        tree.lock_read()
+        try:
+            actual = [e[0] for e in tree.list_files()]
+            # list_files doesn't guarantee order
+            actual = sorted(actual)
+            self.assertEqual(expected, actual)
+        finally:
+            tree.unlock()
+
+    def make_outer_tree(self):
+        outer = self.make_branch_and_tree('outer')
+        self.build_tree_contents([('outer/foo', 'foo')])
+        outer.add('foo', 'foo-id')
+        outer.commit('added foo')
+        inner = self.make_inner_branch()
+        outer.merge_from_branch(inner, to_revision='1', from_revision='null:')
+        outer.commit('merge inner branch')
+        outer.mkdir('dir-outer', 'dir-outer-id')
+        outer.move(['dir', 'file3'], to_dir='dir-outer')
+        outer.commit('rename imported dir and file3 to dir-outer')
+        return outer, inner
+
+    def test_file1_deleted_in_dir(self):
+        outer, inner = self.make_outer_tree()
+        outer.remove(['dir-outer/dir/file1'], keep_files=False)
+        outer.commit('delete file1')
+        outer.merge_from_branch(inner)
+        outer.commit('merge the rest')
+        self.assertTreeLayout(['dir-outer',
+                               'dir-outer/dir',
+                               'dir-outer/dir/file2',
+                               'dir-outer/file3',
+                               'foo'],
+                              outer)
+
+    def test_file3_deleted_in_root(self):
+        # Reproduce bug #375898
+        outer, inner = self.make_outer_tree()
+        outer.remove(['dir-outer/file3'], keep_files=False)
+        outer.commit('delete file3')
+        outer.merge_from_branch(inner)
+        outer.commit('merge the rest')
+        self.assertTreeLayout(['dir-outer',
+                               'dir-outer/dir',
+                               'dir-outer/dir/file1',
+                               'dir-outer/dir/file2',
+                               'foo'],
+                              outer)
+
+
+    def test_file3_in_root_conflicted(self):
+        outer, inner = self.make_outer_tree()
+        outer.remove(['dir-outer/file3'], keep_files=False)
+        outer.commit('delete file3')
+        nb_conflicts = outer.merge_from_branch(inner, to_revision='3')
+        self.assertEqual(4, nb_conflicts)
+        self.assertTreeLayout(['dir-outer',
+                               'dir-outer/dir',
+                               'dir-outer/dir/file1',
+                               # Ideally th conflict helpers should be in
+                               # dir-outer/dir but since we can't easily find
+                               # back the file3 -> outer-dir/dir rename, root
+                               # is good enough -- vila 20100401
+                               'file3.BASE',
+                               'file3.OTHER',
+                               'foo'],
+                              outer)
+