Rev 2657: Add Graph.is_ancestor, update code to use it in file:///home/pqm/archives/thelove/bzr/%2Btrunk/
Canonical.com Patch Queue Manager
pqm at pqm.ubuntu.com
Sat Jul 28 02:33:08 BST 2007
At file:///home/pqm/archives/thelove/bzr/%2Btrunk/
------------------------------------------------------------
revno: 2657
revision-id: pqm at pqm.ubuntu.com-20070728013305-u91kdx3px9ytdyok
parent: pqm at pqm.ubuntu.com-20070728003632-bxnvc9xfmvv9zeol
parent: abentley at panoramicfeedback.com-20070727164804-2lpkqqquk4f9u9b5
committer: Canonical.com Patch Queue Manager <pqm at pqm.ubuntu.com>
branch nick: +trunk
timestamp: Sat 2007-07-28 02:33:05 +0100
message:
Add Graph.is_ancestor, update code to use it
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
bzrlib/branch.py branch.py-20050309040759-e4baf4e0d046576e
bzrlib/builtins.py builtins.py-20050830033751-fc01482b9ca23183
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
------------------------------------------------------------
revno: 2653.2.7
merged: abentley at panoramicfeedback.com-20070727164804-2lpkqqquk4f9u9b5
parent: abentley at panoramicfeedback.com-20070727164655-6x29h59b2w5gca4h
committer: Aaron Bentley <abentley at panoramicfeedback.com>
branch nick: kill-ancestry
timestamp: Fri 2007-07-27 12:48:04 -0400
message:
Update NEWS
------------------------------------------------------------
revno: 2653.2.6
merged: abentley at panoramicfeedback.com-20070727164655-6x29h59b2w5gca4h
parent: abentley at panoramicfeedback.com-20070727164406-ijy40b32kse5mb02
parent: pqm at pqm.ubuntu.com-20070727061532-14ly852y2g2dbcb8
committer: Aaron Bentley <abentley at panoramicfeedback.com>
branch nick: kill-ancestry
timestamp: Fri 2007-07-27 12:46:55 -0400
message:
Merge bzr.dev
------------------------------------------------------------
revno: 2653.2.5
merged: abentley at panoramicfeedback.com-20070727164406-ijy40b32kse5mb02
parent: abentley at panoramicfeedback.com-20070727130200-cfi43ooto0r53xru
committer: Aaron Bentley <abentley at panoramicfeedback.com>
branch nick: kill-ancestry
timestamp: Fri 2007-07-27 12:44:06 -0400
message:
Update to clarify algorithm
------------------------------------------------------------
revno: 2653.2.4
merged: abentley at panoramicfeedback.com-20070727130200-cfi43ooto0r53xru
parent: abentley at panoramicfeedback.com-20070726195604-707eq8fs9px91yjc
committer: Aaron Bentley <abentley at panoramicfeedback.com>
branch nick: kill-ancestry
timestamp: Fri 2007-07-27 09:02:00 -0400
message:
Remove get_ancestry usage from branch
------------------------------------------------------------
revno: 2653.2.3
merged: abentley at panoramicfeedback.com-20070726195604-707eq8fs9px91yjc
parent: abentley at panoramicfeedback.com-20070726195156-9zi1ke2v6tq274f3
committer: Aaron Bentley <abentley at panoramicfeedback.com>
branch nick: kill-ancestry
timestamp: Thu 2007-07-26 15:56:04 -0400
message:
correctly handle Graph.is_ancestor(x, x)
------------------------------------------------------------
revno: 2653.2.2
merged: abentley at panoramicfeedback.com-20070726195156-9zi1ke2v6tq274f3
parent: abentley at panoramicfeedback.com-20070726194625-cxg2ocrvfsyolw16
committer: Aaron Bentley <abentley at panoramicfeedback.com>
branch nick: kill-ancestry
timestamp: Thu 2007-07-26 15:51:56 -0400
message:
Replace get_ancestry with is_ancestor
------------------------------------------------------------
revno: 2653.2.1
merged: abentley at panoramicfeedback.com-20070726194625-cxg2ocrvfsyolw16
parent: pqm at pqm.ubuntu.com-20070726134355-tlidmsn3eux09idz
committer: Aaron Bentley <abentley at panoramicfeedback.com>
branch nick: kill-ancestry
timestamp: Thu 2007-07-26 15:46:25 -0400
message:
Implement Graph.is_ancestor
=== modified file 'NEWS'
--- a/NEWS 2007-07-27 04:36:24 +0000
+++ b/NEWS 2007-07-27 16:48:04 +0000
@@ -165,6 +165,9 @@
the parents of many knit nodes at once, reducing round trips to the
underlying index. (Robert Collins)
+ * Graph now has an is_ancestor method, various bits use it.
+ (Aaron Bentley)
+
TESTING:
* Remove selftest ``--clean-output``, ``--numbered-dirs`` and
=== modified file 'bzrlib/branch.py'
--- a/bzrlib/branch.py 2007-07-15 11:24:18 +0000
+++ b/bzrlib/branch.py 2007-07-27 13:02:00 +0000
@@ -1463,10 +1463,8 @@
# we fetch here regardless of whether we need to so that we pickup
# filled in ghosts.
self.fetch(other, stop_revision)
- my_ancestry = self.repository.get_ancestry(last_rev,
- topo_sorted=False)
- if stop_revision in my_ancestry:
- # last_revision is a descendant of stop_revision
+ if self.repository.get_graph().is_ancestor(stop_revision,
+ last_rev):
return
self.generate_revision_history(stop_revision, last_rev=last_rev,
other_branch=other)
@@ -1821,11 +1819,10 @@
"""
master = self.get_master_branch()
if master is not None:
- old_tip = self.last_revision()
+ old_tip = _mod_revision.ensure_null(self.last_revision())
self.pull(master, overwrite=True)
- if old_tip in self.repository.get_ancestry(
- _mod_revision.ensure_null(self.last_revision()),
- topo_sorted=False):
+ if self.repository.get_graph().is_ancestor(old_tip,
+ _mod_revision.ensure_null(self.last_revision())):
return None
return old_tip
return None
=== modified file 'bzrlib/builtins.py'
--- a/bzrlib/builtins.py 2007-07-23 19:37:15 +0000
+++ b/bzrlib/builtins.py 2007-07-26 19:51:56 +0000
@@ -2669,8 +2669,9 @@
mergeable.install_revisions(tree.branch.repository)
base_revision_id, other_revision_id, verified =\
mergeable.get_merge_request(tree.branch.repository)
- if base_revision_id in tree.branch.repository.get_ancestry(
- tree.branch.last_revision(), topo_sorted=False):
+ if (base_revision_id != _mod_revision.NULL_REVISION and
+ tree.branch.repository.get_graph().is_ancestor(
+ base_revision_id, tree.branch.last_revision())):
base_revision_id = None
other_branch = None
path = ''
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py 2007-06-27 15:12:32 +0000
+++ b/bzrlib/graph.py 2007-07-27 16:44:06 +0000
@@ -290,6 +290,73 @@
sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
return sorter.iter_topo_order()
+ def is_ancestor(self, candidate_ancestor, candidate_descendant):
+ """Determine whether a revision is an ancestor of another.
+
+ There are two possible outcomes: True and False, but there are three
+ possible relationships:
+
+ a) candidate_ancestor is an ancestor of candidate_descendant
+ b) candidate_ancestor is an descendant of candidate_descendant
+ c) candidate_ancestor is an sibling of candidate_descendant
+
+ To check for a, we walk from candidate_descendant, looking for
+ candidate_ancestor.
+
+ To check for b, we walk from candidate_ancestor, looking for
+ candidate_descendant.
+
+ To make a and b more efficient, we can stop any searches that hit
+ common ancestors.
+
+ If we exhaust our searches, but neither a or b is true, then c is true.
+
+ In order to find c efficiently, we must avoid searching from
+ candidate_descendant or candidate_ancestor into common ancestors. But
+ if we don't search common ancestors at all, we won't know if we hit
+ common ancestors. So we have a walker for common ancestors. Note that
+ its searches are not required to terminate in order to determine c to
+ be true.
+ """
+ ancestor_walker = self._make_breadth_first_searcher(
+ [candidate_ancestor])
+ descendant_walker = self._make_breadth_first_searcher(
+ [candidate_descendant])
+ common_walker = self._make_breadth_first_searcher([])
+ active_ancestor = True
+ active_descendant = True
+ while (active_ancestor or active_descendant):
+ new_common = set()
+ if active_descendant:
+ try:
+ nodes = descendant_walker.next()
+ except StopIteration:
+ active_descendant = False
+ else:
+ if candidate_ancestor in nodes:
+ return True
+ new_common.update(nodes.intersection(ancestor_walker.seen))
+ if active_ancestor:
+ try:
+ nodes = ancestor_walker.next()
+ except StopIteration:
+ active_ancestor = False
+ else:
+ if candidate_descendant in nodes:
+ return False
+ new_common.update(nodes.intersection(
+ descendant_walker.seen))
+ try:
+ new_common.update(common_walker.next())
+ except StopIteration:
+ pass
+ for walker in (ancestor_walker, descendant_walker):
+ for node in new_common:
+ c_ancestors = walker.find_seen_ancestors(node)
+ walker.stop_searching_any(c_ancestors)
+ common_walker.start_searching(new_common)
+ return False
+
class _BreadthFirstSearcher(object):
"""Parallel search the breadth-first the ancestry of revisions.
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py 2007-06-27 15:12:32 +0000
+++ b/bzrlib/tests/test_graph.py 2007-07-26 19:56:04 +0000
@@ -16,7 +16,7 @@
from bzrlib import (
errors,
- graph,
+ graph as _mod_graph,
)
from bzrlib.revision import NULL_REVISION
from bzrlib.tests import TestCaseWithMemoryTransport
@@ -120,6 +120,30 @@
'rev2b': ['rev1'], 'rev2c': ['rev1'],
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
+# NULL_REVISION
+# |
+# f
+# |
+# e
+# / \
+# b d
+# | \ |
+# a c
+
+boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
+ 'f':[NULL_REVISION]}
+
+
+class InstrumentedParentsProvider(object):
+
+ def __init__(self, parents_provider):
+ self.calls = []
+ self._real_parents_provider = parents_provider
+
+ def get_parents(self, nodes):
+ self.calls.extend(nodes)
+ return self._real_parents_provider.get_parents(nodes)
+
class TestGraph(TestCaseWithMemoryTransport):
@@ -277,7 +301,7 @@
parents1 = ParentsProvider({'rev2': ['rev3']})
parents2 = ParentsProvider({'rev1': ['rev4']})
- stacked = graph._StackedParentsProvider([parents1, parents2])
+ stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
self.assertEqual([['rev4',], ['rev3']],
stacked.get_parents(['rev1', 'rev2']))
self.assertEqual([['rev3',], ['rev4']],
@@ -294,3 +318,31 @@
self.assertEqual(set(args), set(topo_args))
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
+
+ def test_is_ancestor(self):
+ graph = self.make_graph(ancestry_1)
+ self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
+ self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
+ self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
+ self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
+ self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
+ self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
+ self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
+ self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
+ self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
+ instrumented_provider = InstrumentedParentsProvider(graph)
+ instrumented_graph = _mod_graph.Graph(instrumented_provider)
+ instrumented_graph.is_ancestor('rev2a', 'rev2b')
+ self.assertTrue('null:' not in instrumented_provider.calls)
+
+ def test_is_ancestor_boundary(self):
+ """Ensure that we avoid searching the whole graph.
+
+ This requires searching through b as a common ancestor, so we
+ can identify that e is common.
+ """
+ graph = self.make_graph(boundary)
+ instrumented_provider = InstrumentedParentsProvider(graph)
+ graph = _mod_graph.Graph(instrumented_provider)
+ self.assertFalse(graph.is_ancestor('a', 'c'))
+ self.assertTrue('null:' not in instrumented_provider.calls)
More information about the bazaar-commits
mailing list