Rev 3102: Add a failing test for an alternate ancestry. in http://bzr.arbash-meinel.com/branches/bzr/0.93-dev/graph_update
John Arbash Meinel
john at arbash-meinel.com
Thu Dec 13 23:01:59 GMT 2007
At http://bzr.arbash-meinel.com/branches/bzr/0.93-dev/graph_update
------------------------------------------------------------
revno: 3102
revision-id:john at arbash-meinel.com-20071213230136-urdk4t2045id09so
parent: john at arbash-meinel.com-20071212184135-kym0o1vf0jnd66s3
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_update
timestamp: Thu 2007-12-13 17:01:36 -0600
message:
Add a failing test for an alternate ancestry.
Implement _remove_simple_descedants with tests.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py 2007-12-12 18:41:35 +0000
+++ b/bzrlib/graph.py 2007-12-13 23:01:36 +0000
@@ -241,10 +241,15 @@
def find_difference(self, left_revision, right_revision):
"""Determine the graph difference between two revisions"""
- border, common, (left, right) = self._find_border_ancestors(
+ border, common, searchers = self._find_border_ancestors(
[left_revision, right_revision])
- return (left.difference(right).difference(common),
- right.difference(left).difference(common))
+ # Now that we have the superset of uncommon nodes, lets refine it with
+ # a bit more searching.
+ left = searchers[0].seen
+ right = searchers[1].seen
+ left_diff = left.difference(right).difference(common)
+ right_diff = right.difference(left).difference(common)
+ return left_diff, right_diff
def _make_breadth_first_searcher(self, revisions):
return _BreadthFirstSearcher(revisions, self)
@@ -325,8 +330,8 @@
"\nStart_nodes: %s"
"\nuncommon_nodes: %s"
% (revisions, uncommon_nodes))
- return border_ancestors, common_ancestors, [s.seen for s in
- searchers]
+ break
+ return border_ancestors, common_ancestors, searchers
def heads(self, keys):
"""Return the heads from amongst keys.
@@ -476,6 +481,26 @@
return set([candidate_descendant]) == self.heads(
[candidate_ancestor, candidate_descendant])
+ def _remove_simple_descendants(self, revisions):
+ """remove revisions which are children of other ones in the set
+
+ This doesn't do any graph searching, it just checks the immediate
+ parents to find if there are any children which can be removed.
+
+ :param revisions: A set of revision_ids
+ :return: A set of revision_ids with the children removed
+ """
+ parents = self.get_parent_map(revisions)
+ simple_ancestors = revisions.copy()
+ for revision, parent_ids in parents.iteritems():
+ for parent_id in parent_ids:
+ if parent_id in revisions:
+ # This node has a parent present in the set, so we can
+ # remove it
+ simple_ancestors.discard(revision)
+ break
+ return simple_ancestors
+
class HeadsCache(object):
"""A cache of results for graph heads calls."""
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py 2007-12-12 15:20:39 +0000
+++ b/bzrlib/tests/test_graph.py 2007-12-13 23:01:36 +0000
@@ -194,6 +194,78 @@
'i':['e', 'g'], 'j':['g'], 'k':['j'],
'l':['k'], 'm':['i', 'l'], 'n':['l', 'h']}
+# a--
+# |\ \
+# b | c
+# | | |
+# d | e
+# | | |
+# f | |
+# |\| |
+# | g |
+# | ./
+# | h
+# |/|
+# i
+# |
+# j
+# |
+# k
+
+# NULL_REVISION
+# |
+# a
+# |
+# b
+# |
+# c
+# |
+# d
+# |\
+# e f
+# |\|\
+# | g h
+# | | |
+# i j |
+# | | |
+# | k |
+# | | |
+# | l |
+# |/|/
+# m n
+complex_shortcut2 = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
+ 'e':['d'], 'f':['d'], 'g':['f', 'i'], 'h':['f'],
+ 'i':['e'], 'j':['g'], 'k':['j'],
+ 'l':['k'], 'm':['i', 'l'], 'n':['l', 'h']}
+## NULL_REVISION
+## |
+## a
+## |
+## b
+## |
+## c
+## |
+## d-.
+## |\ \
+## e f |
+## |\| |
+## | g h
+## | | |
+## i j |
+## | | |
+## | k |
+## | |/
+## | l
+## |/
+## m
+## |
+## n
+##
+##complex_shortcut2 = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
+## 'e':['d'], 'f':['d'], 'g':['e', 'f'], 'h':['d'],
+## 'i':['e'], 'j':['g'], 'k':['j'],
+## 'l':['p', 'h'], 'm':['i', 'l'], 'n':['m']}
+
# Shortcut with extra root
# We have a long history shortcut, and an extra root, which is why we can't
# stop searchers based on seeing NULL_REVISION
@@ -249,6 +321,7 @@
class TestGraph(TestCaseWithMemoryTransport):
def make_graph(self, ancestors):
+ return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
tree = self.prepare_memory_tree('.')
self.build_ancestry(tree, ancestors)
self.addCleanup(tree.unlock)
@@ -341,6 +414,27 @@
graph.find_unique_lca('rev2a', 'rev2b',
count_steps=True))
+ def test__remove_simple_descendants(self):
+ graph = self.make_graph(ancestry_1)
+ all_revisions = set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4'])
+ self.assertEqual(set(['rev1']),
+ graph._remove_simple_descendants(all_revisions))
+
+ def test__remove_simple_descendants_disjoint(self):
+ graph = self.make_graph(ancestry_1)
+ self.assertEqual(set(['rev1', 'rev3']),
+ graph._remove_simple_descendants(set(['rev1', 'rev3'])))
+
+ def test__remove_simple_descendants_chain(self):
+ graph = self.make_graph(ancestry_1)
+ self.assertEqual(set(['rev1']),
+ graph._remove_simple_descendants(set(['rev1', 'rev2a', 'rev3'])))
+
+ def test__remove_simple_descendants_siblings(self):
+ graph = self.make_graph(ancestry_1)
+ self.assertEqual(set(['rev2a', 'rev2b']),
+ graph._remove_simple_descendants(set(['rev2a', 'rev2b', 'rev3'])))
+
def test_unique_lca_criss_cross(self):
"""Ensure we don't pick non-unique lcas in a criss-cross"""
graph = self.make_graph(criss_cross)
@@ -426,6 +520,12 @@
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
graph.find_difference('m', 'n'))
+ def test_graph_difference_complex_shortcut2(self):
+ import pdb; pdb.set_trace()
+ graph = _mod_graph.Graph(_mod_graph.DictParentsProvider(complex_shortcut2))
+ self.assertEqual((set(['m', 'i']), set(['h', 'n'])),
+ graph.find_difference('m', 'n'))
+
def test_graph_difference_shortcut_extra_root(self):
graph = self.make_graph(shortcut_extra_root)
self.assertEqual((set(['e']), set(['f', 'g'])),
More information about the bazaar-commits
mailing list