Merge lp:~garyvdm/bzr/bug588698-criss-cross-null-base into lp:bzr

[Gary van der Merwe]

This makes merge choose one of the lcas as the base revision when it cannot locate a unique lca, for example where there is a criss-cross merge of a new root.

It chooses the lca by taking the first lca from find_merge_order(lcas). This seems to give the most sensible for all the user tests I have run.

This has a drive-by fix to make BranchBuilder.build_snapshot accept parent_ids == ['null:']. This was done to make it easier to write a test using BranchBuilder that introduces a new root into the graph.

[John A Meinel (jameinel)]

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

On 11/17/2010 7:44 AM, Gary van der Merwe wrote:
> Gary van der Merwe has proposed merging lp:~garyvdm/bzr/bug588698-criss-cross-null-base into lp:bzr.
>
> Requested reviews:
> bzr-core (bzr-core)
> Related bugs:
> #588698 "bzr merge" fails "Branches have no common ancestor"
> https://bugs.launchpad.net/bugs/588698
>
>
> This makes merge choose one of the lcas as the base revision when it cannot locate a unique lca, for example where there is a criss-cross merge of a new root.
>
> It chooses the lca by taking the first lca from find_merge_order(lcas). This seems to give the most sensible for all the user tests I have run.
>
> This has a drive-by fix to make BranchBuilder.build_snapshot accept parent_ids == ['null:']. This was done to make it easier to write a test using BranchBuilder that introduces a new root into the graph.

- - if parent_ids is not None:
+ if parent_ids == [revision.NULL_REVISION]:

^- Are we sure parent_ids is always a list? Could it be a tuple:
(revision.NULL_REVISION,).

I think it usually is. However, you shouldn't need to pass
[NULL_REVISION] either. Just pass the empty list (I think).

+ builder.build_snapshot('B-id', [],
+ [('add', ('', None, 'directory', None))])

I'm not positive if that works, but it does actually match certain bits
of code better. ('null:' isn't saved to the index files, for example).

I'd have to dig a bit deeper to sort out the rest. However, this snippet
looks worrying:

- - self._is_criss_cross = True
+ sorted_lca_keys = self.revision_graph.find_merge_order(

+ revisions[0], lcas)
+ if self.base_rev_id == _mod_revision.NULL_REVISION:
+ self.base_rev_id = sorted_lca_keys[0]
+

graph.find_merge_order is not a cheap operation, because it has to walk
the ancestry. Could we do it only in the 'if' block:

if self.base_rev_id == _mod_revision.NULL_REVISION:
    trace.mutter("hit the NULL_REVISION as the unique LCA."
                 " Picking the 'first' lca as BASE")
    sorted_lca_keys = self.revision_graph.find_merge_order(revisions[0],
lcas)
    self.base_rev_id = sorted_lca_keys[0]

...

                 interesting_revision_ids = [self.base_rev_id]
                 interesting_revision_ids.extend(lcas)
+ interesting_revision_ids =
list(set(interesting_revision_ids))

^- This doesn't preserve the ordering of interesting_revision_ids. But
since it looks like we don't need the specific order, why not just use a
set and not cast to a list in the first place?

I see that 'sorted_lca_keys' is used again right after this point. but
is it used in all possible cases?

Anyway, the basic concept seems fine. Failing down to NULL_REVISION is
bad, picking a 'best guess' LCA seems reasonable. We may want to inform
the user that we did this, in case it would be confusing why X or Y
didn't happen. At least a mutter() helps us debug it if it is happening.

John
=:->

 review: needs_information
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev....

review: Needs Information

[Gary van der Merwe (garyvdm)]

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

On 17/11/2010 23:05, John Arbash Meinel wrote:
> I think it usually is. However, you shouldn't need to pass
> [NULL_REVISION] either. Just pass the empty list (I think).
>
> + builder.build_snapshot('B-id', [],
> + [('add', ('', None, 'directory', None))])
>
> I'm not positive if that works, but it does actually match certain bits
> of code better. ('null:' isn't saved to the index files, for example).

Ok. I've updated the code to make it possible to pass [] to get a null
parent.

> graph.find_merge_order is not a cheap operation, because it has to walk
> the ancestry. Could we do it only in the 'if' block:
....
> I see that 'sorted_lca_keys' is used again right after this point. but
> is it used in all possible cases?

Previously, we always call graph.find_merge_order if we encounter a
criss-cross merge. It is used later to sort interesting_trees. I have
just moved it's execution earlier.

>
> interesting_revision_ids = [self.base_rev_id]
> interesting_revision_ids.extend(lcas)
> + interesting_revision_ids =
> list(set(interesting_revision_ids))
>
> ^- This doesn't preserve the ordering of interesting_revision_ids. But
> since it looks like we don't need the specific order, why not just use a
> set and not cast to a list in the first place?

Ah yes, when I wrote it that line, I meant to go back and change it, but
I forgot to. Fixed now.

> Anyway, the basic concept seems fine. Failing down to NULL_REVISION is
> bad, picking a 'best guess' LCA seems reasonable.

Great.

> We may want to inform the user that we did this, in case it would be
> confusing why X or Y didn't happen. At least a mutter() helps us
> debug it if it is happening.

I don't think that the behavior changes much compared to a criss-cross
merge, and so I don't think a warning is appropriate. I have added a mutter.

Regards,

Gary
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkzk5pYACgkQd/3EdwGKOh1IfACgnKiuHCi2+ra9ffOSiNgxus31
S9wAn1GtkQoM6nUyxMcGV7vbbUEKmhS/
=PvTF
-----END PGP SIGNATURE-----

=== modified file 'bzrlib/branchbuilder.py'
--- bzrlib/branchbuilder.py	2010-02-27 12:27:33 +0000
+++ bzrlib/branchbuilder.py	2010-11-18 08:27:12 +0000
@@ -21,6 +21,7 @@
     commit,
     errors,
     memorytree,
+    revision,
     )
 
 
@@ -186,7 +187,10 @@
         :return: The revision_id of the new commit
         """
         if parent_ids is not None:
-            base_id = parent_ids[0]
+            if len(parent_ids) == 0:
+                base_id = revision.NULL_REVISION
+            else:
+                base_id = parent_ids[0]
             if base_id != self._branch.last_revision():
                 self._move_branch_pointer(base_id,
                     allow_leftmost_as_ghost=allow_leftmost_as_ghost)

=== modified file 'bzrlib/merge.py'
--- bzrlib/merge.py	2010-08-25 13:02:32 +0000
+++ bzrlib/merge.py	2010-11-18 08:27:12 +0000
@@ -582,6 +582,7 @@
             elif len(lcas) == 1:
                 self.base_rev_id = list(lcas)[0]
             else: # len(lcas) > 1
+                self._is_criss_cross = True
                 if len(lcas) > 2:
                     # find_unique_lca can only handle 2 nodes, so we have to
                     # start back at the beginning. It is a shame to traverse
@@ -592,22 +593,30 @@
                 else:
                     self.base_rev_id = self.revision_graph.find_unique_lca(
                                             *lcas)
-                self._is_criss_cross = True
+                sorted_lca_keys = self.revision_graph.find_merge_order(                
+                    revisions[0], lcas)
+                if self.base_rev_id == _mod_revision.NULL_REVISION:
+                    self.base_rev_id = sorted_lca_keys[0]
+                
             if self.base_rev_id == _mod_revision.NULL_REVISION:
                 raise errors.UnrelatedBranches()
             if self._is_criss_cross:
                 trace.warning('Warning: criss-cross merge encountered.  See bzr'
                               ' help criss-cross.')
                 trace.mutter('Criss-cross lcas: %r' % lcas)
-                interesting_revision_ids = [self.base_rev_id]
-                interesting_revision_ids.extend(lcas)
+                if self.base_rev_id in lcas:
+                    trace.mutter('Unable to find unique lca. '
+                                 'Fallback %r as best option.' % self.base_rev_id)
+                interesting_revision_ids = set(lcas)
+                interesting_revision_ids.add(self.base_rev_id)
                 interesting_trees = dict((t.get_revision_id(), t)
                     for t in self.this_branch.repository.revision_trees(
                         interesting_revision_ids))
                 self._cached_trees.update(interesting_trees)
-                self.base_tree = interesting_trees.pop(self.base_rev_id)
-                sorted_lca_keys = self.revision_graph.find_merge_order(
-                    revisions[0], lcas)
+                if self.base_rev_id in lcas:
+                    self.base_tree = interesting_trees[self.base_rev_id]
+                else:
+                    self.base_tree = interesting_trees.pop(self.base_rev_id)
                 self._lca_trees = [interesting_trees[key]
                                    for key in sorted_lca_keys]
             else:

=== modified file 'bzrlib/tests/test_branchbuilder.py'
--- bzrlib/tests/test_branchbuilder.py	2010-02-27 12:27:33 +0000
+++ bzrlib/tests/test_branchbuilder.py	2010-11-18 08:27:12 +0000
@@ -324,6 +324,21 @@
         # should look like it was not modified in the merge
         self.assertEqual('C-id', d_tree.inventory['c-id'].revision)
 
+    def test_set_parent_to_null(self):
+        builder = self.build_a_rev()
+        builder.start_series()
+        self.addCleanup(builder.finish_series)
+        builder.build_snapshot('B-id', [],
+            [('add', ('', None, 'directory', None))])
+        # We should now have a graph:
+        #   A B
+        # And not A => B
+        repo = builder.get_branch().repository
+        self.assertEqual({'A-id': (_mod_revision.NULL_REVISION,),
+                          'B-id': (_mod_revision.NULL_REVISION,),},
+                         repo.get_parent_map(['A-id', 'B-id']))
+
+    
     def test_start_finish_series(self):
         builder = BranchBuilder(self.get_transport().clone('foo'))
         builder.start_series()

=== modified file 'bzrlib/tests/test_merge.py'
--- bzrlib/tests/test_merge.py	2010-07-29 04:07:27 +0000
+++ bzrlib/tests/test_merge.py	2010-11-18 08:27:12 +0000
@@ -1270,6 +1270,26 @@
         self.assertEqual(['B-id', 'C-id', 'F-id'],
                          [t.get_revision_id() for t in merger._lca_trees])
 
+    def test_find_base_new_root_criss_cross(self):
+        # A   B
+        # |\ /|
+        # | X |
+        # |/ \|
+        # C   D
+        
+        builder = self.get_builder()
+        builder.build_snapshot('A-id', None,
+            [('add', ('', None, 'directory', None))])
+        builder.build_snapshot('B-id', [],
+            [('add', ('', None, 'directory', None))])
+        builder.build_snapshot('D-id', ['A-id', 'B-id'], [])
+        builder.build_snapshot('C-id', ['A-id', 'B-id'], [])
+        merger = self.make_Merger(builder, 'D-id')
+        self.assertEqual('A-id', merger.base_rev_id)
+        self.assertTrue(merger._is_criss_cross)
+        self.assertEqual(['A-id', 'B-id'], [t.get_revision_id()
+                                            for t in merger._lca_trees])
+
     def test_no_criss_cross_passed_to_merge_type(self):
         class LCATreesMerger(LoggingMerger):
             supports_lca_trees = True

=== modified file 'doc/en/release-notes/bzr-2.3.txt'
--- doc/en/release-notes/bzr-2.3.txt	2010-11-11 23:48:07 +0000
+++ doc/en/release-notes/bzr-2.3.txt	2010-11-18 08:27:12 +0000
@@ -52,6 +52,9 @@
   is involved in a text conflict (but the conflict is still not
   resolved). (Vincent Ladeuil, #646961)
 
+* Merge will now correctly locate a lca where there is a criss-cross merge
+  of a new root. (Gary van der Merwe, #588698)
+
 * Report error if non-ASCII command option given. (Rory Yorke, #140563)
 
 Documentation
@@ -71,6 +74,9 @@
 .. Major internal changes, unlikely to be visible to users or plugin 
    developers, but interesting for bzr developers.
 
+* ``BranchBuilder.build_snapshot`` now accepts parent_ids == [].
+  This can be used to create a new root in the graph. (Gary van der Merwe)
+
 Testing
 *******