Rev 3238: Respond to abentley's review comments. in http://bzr.arbash-meinel.com/branches/bzr/1.3-dev/revision_graph
John Arbash Meinel
john at arbash-meinel.com
Mon Mar 10 15:11:42 GMT 2008
At http://bzr.arbash-meinel.com/branches/bzr/1.3-dev/revision_graph
------------------------------------------------------------
revno: 3238
revision-id:john at arbash-meinel.com-20080310151047-4vm0q4357if5q856
parent: john at arbash-meinel.com-20080226001244-t3kghacai8bri599
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: revision_graph
timestamp: Mon 2008-03-10 10:10:47 -0500
message:
Respond to abentley's review comments.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/repofmt/pack_repo.py pack_repo.py-20070813041115-gjv5ma7ktfqwsjgn-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py 2008-02-25 22:41:36 +0000
+++ b/bzrlib/graph.py 2008-03-10 15:10:47 +0000
@@ -427,20 +427,14 @@
def iter_ancestry(self, revision_ids):
"""Iterate the ancestry of this revision.
- The specific order is undefined, but children should be returned before
- parents.
-
:param revision_ids: Nodes to start the search
:return: Yield tuples mapping a revision_id to its parents for the
ancestry of revision_id.
- Ghosts will be returned with parents of the empty tuple, and nodes
+ Ghosts will be returned with None as their parents, and nodes
with no parents will have NULL_REVISION as their only parent. (As
defined by get_parent_map.)
- There also be a node for (NULL_REVISION, ())
+ There will also be a node for (NULL_REVISION, ())
"""
- # XXX: Do we want to guarantee that children will be returned before
- # parents? At present that is the order, but I don't know that it
- # is beneficial to require it.
pending = set(revision_ids)
processed = set()
while pending:
@@ -452,7 +446,7 @@
next_pending.update(p for p in item[1] if p not in processed)
ghosts = pending.difference(next_map)
for ghost in ghosts:
- yield (ghost, ())
+ yield (ghost, None)
pending = next_pending
def iter_topo_order(self, revisions):
=== modified file 'bzrlib/repofmt/pack_repo.py'
--- a/bzrlib/repofmt/pack_repo.py 2008-02-26 00:03:15 +0000
+++ b/bzrlib/repofmt/pack_repo.py 2008-03-10 15:10:47 +0000
@@ -1941,36 +1941,43 @@
# special case NULL_REVISION
if revision_id == _mod_revision.NULL_REVISION:
return {}
- a_weave = self._get_revision_vf()
if revision_id is None:
- return a_weave.get_graph()
- if revision_id not in a_weave:
+ revision_vf = self._get_revision_vf()
+ return revision_vf.get_graph()
+ g = self.get_graph()
+ first = g.get_parent_map([revision_id])
+ if revision_id not in first:
raise errors.NoSuchRevision(self, revision_id)
else:
- g = self.get_graph()
ancestry = {}
children = {}
- ghosts = set()
NULL_REVISION = _mod_revision.NULL_REVISION
+ ghosts = set([NULL_REVISION])
for rev_id, parent_ids in g.iter_ancestry([revision_id]):
- if len(parent_ids) == 0: # Ghost
- if rev_id not in children:
- continue
+ if parent_ids is None: # This is a ghost
ghosts.add(rev_id)
- for child in children[rev_id]:
- old_anc = ancestry[child]
- ancestry[child] = tuple(p for p in old_anc
- if p != rev_id)
continue
- if len(parent_ids) == 1 and parent_ids[0] == NULL_REVISION:
- parent_ids = () # No parents
- parent_ids = tuple(p for p in parent_ids if p not in ghosts)
ancestry[rev_id] = parent_ids
for p in parent_ids:
if p in children:
children[p].append(rev_id)
else:
children[p] = [rev_id]
+
+ if NULL_REVISION in ancestry:
+ del ancestry[NULL_REVISION]
+
+ # Find all nodes that reference a ghost, and filter the ghosts out
+ # of their parent lists. To preserve the order of parents, and
+ # avoid double filtering nodes, we just find all children first,
+ # and then filter.
+ children_of_ghosts = set()
+ for ghost in ghosts:
+ children_of_ghosts.update(children[ghost])
+
+ for child in children_of_ghosts:
+ ancestry[child] = tuple(p for p in ancestry[child]
+ if p not in ghosts)
return ancestry
def has_revisions(self, revision_ids):
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py 2008-02-25 22:41:36 +0000
+++ b/bzrlib/tests/test_graph.py 2008-03-10 15:10:47 +0000
@@ -250,7 +250,7 @@
# a c
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
- 'e': ['f'], 'f':[NULL_REVISION]}
+ 'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
@@ -506,18 +506,20 @@
self.assertTrue('null:' not in instrumented_provider.calls)
def test_iter_ancestry(self):
- graph = self.make_graph(boundary)
- expected = boundary.copy()
+ nodes = boundary.copy()
+ nodes[NULL_REVISION] = ()
+ graph = self.make_graph(nodes)
+ expected = nodes.copy()
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
# other nodes are
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
- self.assertEqual(boundary, dict(graph.iter_ancestry(['a', 'c'])))
+ self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
def test_iter_ancestry_with_ghost(self):
graph = self.make_graph(with_ghost)
expected = with_ghost.copy()
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
- expected['g'] = ()
+ expected['g'] = None
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
expected.pop('a')
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
More information about the bazaar-commits
mailing list