Rev 3525: Turn ghosts into just another shortcut to NULL_REVISION in http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/lazy_revno
John Arbash Meinel
john at arbash-meinel.com
Thu Aug 7 21:45:17 BST 2008
At http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/lazy_revno
------------------------------------------------------------
revno: 3525
revision-id: john at arbash-meinel.com-20080807204509-aqe2gj5ss2s6iry4
parent: john at arbash-meinel.com-20080807183418-z59a9gjc2ivs6hyi
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: lazy_revno
timestamp: Thu 2008-08-07 15:45:09 -0500
message:
Turn ghosts into just another shortcut to NULL_REVISION
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py 2008-08-07 18:34:18 +0000
+++ b/bzrlib/graph.py 2008-08-07 20:45:09 +0000
@@ -1567,27 +1567,7 @@
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. Care would need to
- # be taken, because you don't want to change the node, but its
- # leftmost ancestor.
- # 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
- trace.note('falling back to _number_all for %s', node.revision_id)
- self._number_all()
- return node.dotted_revno
+ assert mainline_node is not None
# Now, finish searching
# TODO: Finish hooking this up
@@ -1595,6 +1575,10 @@
terminal_ids = self._walk_interesting_nodes(interesting_ids,
mainline_node)
self._propagate_descended_from(terminal_ids)
+ if node.merged_into is None:
+ # We searched for this node, and couldn't find it as an ancestor of
+ # the existing graph. Too bad, so sad.
+ return node.dotted_revno
self._number(node)
return node.dotted_revno
@@ -1679,7 +1663,16 @@
if cur_node is not None:
cur_parent_ids = parent_map.get(cur_node.revision_id, ())
next_node = None
- # If this is a ghost, we are done
+ if (not cur_parent_ids
+ and cur_node.revision_id != revision.NULL_REVISION):
+ # We walked off the graph, this is either a ghost, or
+ # NULL_REVISION. If it is a ghost, we insert a special
+ # shortcut to NULL_REVISION which unifies the handling of
+ # ghosts and roots, which is how merge_sort behaves.
+ cur_parent_ids = (revision.NULL_REVISION,)
+ null_node = self._get_node(revision.NULL_REVISION)
+ null_node.known_children.add(cur_node.revision_id)
+
cur_node.parent_ids = cur_parent_ids
if cur_parent_ids: # We haven't finished yet
next_rev_id = cur_parent_ids[0]
@@ -1693,9 +1686,7 @@
# node = self._get_node(p_id)
# node.set_merged_into(merged_into)
node_ancestors.add(next_rev_id)
- # walked_ancestors.append(next_rev_id)
- else:
- next_node = None
+
if cur_node.mainline_revno is not None:
# We have a node where we know the revno, so we will know
# the mainline revno involved.
@@ -1839,7 +1830,15 @@
# Fill out parent_ids for nodes that need them
if node.parent_ids is None:
# TODO: ghosts
- node.parent_ids = parent_map.get(node.revision_id, ())
+ next_parent_ids = parent_map.get(node.revision_id, ())
+ if (not next_parent_ids # Ghost or off the graph
+ and node.revision_id != revision.NULL_REVISION):
+ next_parent_ids = (revision.NULL_REVISION,)
+ # Fake in a link to the NULL_REVISION, just like we
+ # have to do for _find_mainline_ancestor
+ null_node = self._get_node(revision.NULL_REVISION)
+ null_node.known_children.add(node.revision_id)
+ node.parent_ids = next_parent_ids
if (not node.parent_ids or node.descended_from is not None
or (node.merged_into is not None
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py 2008-08-07 18:28:34 +0000
+++ b/bzrlib/tests/test_graph.py 2008-08-07 20:45:09 +0000
@@ -739,6 +739,26 @@
'y':['d', 'n'], 'z':['y', 'q']
}
+# A graph with multiple ghosts and paths to root.
+# NULL_REVISION
+# | |
+# a g | # g and i are ghosts
+# | | |
+# | h |
+# |/ /|
+# b r | # r and s are extra paths to NULL
+# |/ |
+# c i |
+# |/ /
+# d s
+# |/
+# e
+ghosts_and_roots = {'a':[NULL_REVISION], 'b':['a', 'h'], 'c':['b', 'r'],
+ 'd':['c', 'i'], 'e':['d', 's'],
+ 'g':[], 'h':['g'], 'i':[],
+ 'r':[NULL_REVISION], 's':[NULL_REVISION],
+}
+
class InstrumentedParentsProvider(object):
@@ -1829,6 +1849,12 @@
def test_get_dotted_revno_with_shortcut(self):
self.assertAllDottedRevno(shortcut_extra_root, 'f')
+ def test_get_dotted_revno_ghosts_and_roots(self):
+ # merge_sort treats ghosts the same as roots, they are just new
+ # entry-points into the graph, so we need to make sure we treat them
+ # the same as well
+ self.assertAllDottedRevno(ghosts_and_roots, 'e')
+
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'))
@@ -1928,6 +1954,18 @@
self.assertEqual((5,), mainline_node.dotted_revno)
self.assertEqual('e', mainline_node.revision_id)
+ def test__find_mainline_ancestor_ghosts_and_roots(self):
+ mapper = self.make_mapper(ghosts_and_roots, 'e')
+ node = mapper._get_node('g')
+ mainline_node = mapper._find_mainline_ancestor(node)
+ self.assertEqual(NULL_REVISION, mainline_node.revision_id)
+ node = mapper._get_node('r')
+ mainline_node = mapper._find_mainline_ancestor(node)
+ self.assertEqual(NULL_REVISION, mainline_node.revision_id)
+ node = mapper._get_node('h')
+ mainline_node = mapper._find_mainline_ancestor(node)
+ self.assertEqual(NULL_REVISION, mainline_node.revision_id)
+
def test__get_interesting_merged_ids_trivial(self):
mapper = self.make_mapper(with_tail, 'l', break_on=['a', 'b', 'c', 'd'])
node = mapper._get_node('k')
More information about the bazaar-commits
mailing list