Rev 3516: Handle ghost revisions in the ancestry by falling back to whole-ancestry ops. in http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/lazy_revno

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/lazy_revno

------------------------------------------------------------
revno: 3516
revision-id: john at arbash-meinel.com-20080806181613-jf965wcz4u912oiv
parent: john at arbash-meinel.com-20080806175607-po8br94kwbhnywwc
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: lazy_revno
timestamp: Wed 2008-08-06 13:16:13 -0500
message:
  Handle ghost revisions in the ancestry by falling back to whole-ancestry ops.
  It is inefficient, but hey, it works.
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2008-08-06 17:56:07 +0000
+++ b/bzrlib/graph.py	2008-08-06 18:16:13 +0000
@@ -1567,6 +1567,25 @@
         if node.dotted_revno is not None:
             return node.dotted_revno
 
+        if mainline_node is None:
+            # The revision requested does not have an ancestry which intersects
+            # ours. Unfortunately, there are 2 cases:
+            # 1) Different ancestry (like looking for a bzrtools revision in a
+            #    bzr branch)
+            # 2) Ghost, this is referenced as a parent of our ancestry, but not
+            #    as a child of our ancestry.
+            # To find ghosts, you have to start from its children and walk
+            # backwards, but we don't know where to look, so we would have to
+            # iterate the whole graph. And the numbering code doesn't like it
+            # much anyway. (We could cheat and use NULL_REVISION, which is what
+            # happens when you merge in another project.)
+            # Anyway, because we have to search a lot, for now we just punt,
+            # load the whole graph, and do a regular 'merge_sort' on the whole
+            # thing. Note that this is *very* inefficient when we already have
+            # a decent portion of the graph numbered
+            self._number_all()
+            return node.dotted_revno
+
         # Now, finish searching
         # TODO: Finish hooking this up
         interesting_ids = self._get_interesting_merged_ids(node, mainline_node)
@@ -1697,6 +1716,8 @@
         # direct information about the nodes
         # TODO: I probably don't want to do this here, but instead wait until
         #       later.
+        if mainline_node is None:
+            return None
         mainline_revno = mainline_node.mainline_revno
         next_node = node
         while next_node is not None:
@@ -2006,6 +2027,36 @@
             else:
                 node.dotted_revno = real_dotted_revno
 
+    def _number_all(self):
+        """We've decided to just fall back to merge_sort on the whole graph."""
+        # TODO: it would be nice to make use of the information we already
+        #       have, but it is easier to just switch purposes
+        g = Graph(self._parent_provider)
+        all_ancestors = dict(g.iter_ancestry([self._tip_revision_id]))
+        # Now filter out unreferenced nodes and NULL_REVISION because
+        # merge_sort doesn't like them
+        if revision.NULL_REVISION in all_ancestors:
+            del all_ancestors[revision.NULL_REVISION]
+        culled_parent_map = {}
+        for revision_id, parent_ids in all_ancestors.iteritems():
+            if parent_ids is None:
+                continue
+            culled_parent_ids = tuple([p for p in parent_ids
+                                          if p in all_ancestors])
+            culled_parent_map[revision_id] = culled_parent_ids
+        for (seq_num, rev_id, depth, dotted_revno,
+             end_of_merge) in tsort.merge_sort(culled_parent_map,
+                                               self._tip_revision_id,
+                                               None, generate_revno=True):
+            node = self._get_node(rev_id)
+            if node.dotted_revno is not None:
+                if dotted_revno != node.dotted_revno:
+                    print real_dotted_revno, node.dotted_revno
+                    import pdb; pdb.set_trace()
+            else:
+                node.dotted_revno = dotted_revno
+
+
 
 def collapse_linear_regions(parent_map):
     """Collapse regions of the graph that are 'linear'.

=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py	2008-08-06 17:56:07 +0000
+++ b/bzrlib/tests/test_graph.py	2008-08-06 18:16:13 +0000
@@ -1774,16 +1774,21 @@
         alt_with_ghost = dict(with_ghost)
         # assertAllDottedRevno expects NULL_REVISION to not be in the ancestry
         # map, as it adds another revision to everything.
-        # However, this only accidentally succeeds because we prune 'g' from
-        # the ancestry because it is a ghost. So it never gets numbered. If we
-        # fake it with 'g':(), then it fails because it cannot find a mainline.
+        # Node 'd' references 'g'. We have to insert it 'g' into the ancestry,
+        # so that our merge_sort test tries to number that revision
+        # specifically.
         alt_with_ghost.pop(NULL_REVISION)
+        alt_with_ghost['g'] = ()
         self.assertAllDottedRevno(alt_with_ghost, 'a')
         self.assertAllDottedRevno(alt_with_ghost, 'c')
 
     def test_get_dotted_revno_with_shortcut(self):
         self.assertAllDottedRevno(shortcut_extra_root, 'f')
 
+    def test_get_dotted_revno_not_in_ancestry(self):
+        mapper = self.make_mapper(ancestry_1, 'rev4')
+        self.assertIs(None, mapper.get_dotted_revno('not-an-ancestor'))
+
     def test__step_mainline_node(self):
         mapper = self.make_mapper(with_tail, 'l')
         node = mapper._get_node('l')