Rev 3185: Add basic get_recipe to the graph breadth first searcher. in http://people.ubuntu.com/~robertc/baz2.0/search-results
Robert Collins
robertc at robertcollins.net
Tue Jan 15 22:55:01 GMT 2008
At http://people.ubuntu.com/~robertc/baz2.0/search-results
------------------------------------------------------------
revno: 3185
revision-id:robertc at robertcollins.net-20080115225449-wvrgig7f9763jtxd
parent: pqm at pqm.ubuntu.com-20080115141934-3vujw0up5rc8e0gn
committer: Robert Collins <robertc at robertcollins.net>
branch nick: search-results
timestamp: Wed 2008-01-16 09:54:49 +1100
message:
Add basic get_recipe to the graph breadth first searcher.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py 2008-01-14 23:11:45 +0000
+++ b/bzrlib/graph.py 2008-01-15 22:54:49 +0000
@@ -509,6 +509,8 @@
self._iterations = 0
self._next_query = set(revisions)
self.seen = set()
+ self._started_keys = set(self._next_query)
+ self._stopped_keys = set()
self._parents_provider = parents_provider
self._returning = 'next_with_ghosts'
@@ -521,6 +523,30 @@
return ('_BreadthFirstSearcher(iterations=%d, %s,'
' seen=%r)' % (self._iterations, search, list(self.seen)))
+ def get_recipe(self):
+ """Return a recipe that can be used to replay this search.
+
+ :return: A tuple (start_keys_set, exclude_keys_set). To recreate the
+ results of this search, create a breadth first searcher on the same
+ graph starting at start_keys. Then call next() (or
+ next_with_ghosts()) repeatedly, and on every result, call
+ stop_searching_any on any keys from the exclude_keys set.
+ """
+ if self._returning == 'next':
+ # We have to know the current nodes children to be able to list the
+ # exclude keys for them. However, while we could have a second
+ # look-ahead result buffer and shuffle things around, this method
+ # is typically only called once per search - when memoising the
+ # results of the search.
+ found, ghosts, next, parents = self._do_query(self._next_query)
+ # pretend we didn't query: perhaps we should tweak _do_query to be
+ # entirely stateless?
+ self.seen.difference_update(next)
+ next_query = next
+ else:
+ next_query = self._next_query
+ return self._started_keys, self._stopped_keys.union(next_query)
+
def next(self):
"""Return the next ancestors of this revision.
@@ -538,11 +564,13 @@
# switch to returning the query, not the results.
self._returning = 'next'
self._iterations += 1
- self.seen.update(self._next_query)
else:
self._advance()
if len(self._next_query) == 0:
raise StopIteration()
+ # We have seen what we're querying at this point as we are returning
+ # the query, not the results.
+ self.seen.update(self._next_query)
return self._next_query
def next_with_ghosts(self):
@@ -586,12 +614,14 @@
"""
found_parents = set()
parents_of_found = set()
+ # revisions may contain nodes that point to other nodes in revisions:
+ # we want to filter them out.
+ self.seen.update(revisions)
parent_map = self._parents_provider.get_parent_map(revisions)
for rev_id, parents in parent_map.iteritems():
found_parents.add(rev_id)
parents_of_found.update(p for p in parents if p not in self.seen)
ghost_parents = revisions - found_parents
- self.seen.update(parents_of_found)
return found_parents, ghost_parents, parents_of_found, parent_map
def __iter__(self):
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py 2008-01-14 23:11:45 +0000
+++ b/bzrlib/tests/test_graph.py 2008-01-15 22:54:49 +0000
@@ -252,13 +252,7 @@
class TestGraph(TestCaseWithMemoryTransport):
def make_graph(self, ancestors):
- # XXX: This seems valid, is there a reason to actually create a
- # repository and put things in it?
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
- tree = self.prepare_memory_tree('.')
- self.build_ancestry(tree, ancestors)
- self.addCleanup(tree.unlock)
- return tree.branch.repository.get_graph()
def prepare_memory_tree(self, location):
tree = self.make_branch_and_memory_tree(location)
@@ -653,10 +647,7 @@
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
def test_breadth_first_search_start_ghosts(self):
- parent_graph = {}
- parents_provider = InstrumentedParentsProvider(
- _mod_graph.DictParentsProvider(parent_graph))
- graph = _mod_graph.Graph(parents_provider)
+ graph = self.make_graph({})
# with_ghosts reports the ghosts
search = graph._make_breadth_first_searcher(['a-ghost'])
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
@@ -667,14 +658,11 @@
self.assertRaises(StopIteration, search.next)
def test_breadth_first_search_deep_ghosts(self):
- parent_graph = {
+ graph = self.make_graph({
'head':['present'],
'present':['child', 'ghost'],
'child':[],
- }
- parents_provider = InstrumentedParentsProvider(
- _mod_graph.DictParentsProvider(parent_graph))
- graph = _mod_graph.Graph(parents_provider)
+ })
# with_ghosts reports the ghosts
search = graph._make_breadth_first_searcher(['head'])
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
@@ -693,14 +681,11 @@
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
# To make the API robust, we allow calling both next() and
# next_with_ghosts() on the same searcher.
- parent_graph = {
+ graph = self.make_graph({
'head':['present'],
'present':['child', 'ghost'],
'child':[],
- }
- parents_provider = InstrumentedParentsProvider(
- _mod_graph.DictParentsProvider(parent_graph))
- graph = _mod_graph.Graph(parents_provider)
+ })
# start with next_with_ghosts
search = graph._make_breadth_first_searcher(['head'])
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
@@ -718,15 +703,12 @@
def test_breadth_first_change_search(self):
# Changing the search should work with both next and next_with_ghosts.
- parent_graph = {
+ graph = self.make_graph({
'head':['present'],
'present':['stopped'],
'other':['other_2'],
'other_2':[],
- }
- parents_provider = InstrumentedParentsProvider(
- _mod_graph.DictParentsProvider(parent_graph))
- graph = _mod_graph.Graph(parents_provider)
+ })
search = graph._make_breadth_first_searcher(['head'])
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
@@ -746,6 +728,38 @@
self.assertEqual(set(['other_2']), search.next())
self.assertRaises(StopIteration, search.next)
+ def assertSeenAndRecipes(self, results, search, next):
+ """Check the results of .seen and get_recipe() for a seach.
+
+ :param results: A list of tuples (seen, get_recipe_result).
+ :param search: The search to use.
+ :param next: A callable to advance the search.
+ """
+ for seen, recipe in results:
+ next()
+ self.assertEqual(recipe, search.get_recipe())
+ self.assertEqual(seen, search.seen)
+
+ def test_breadth_first_get_recipe_excludes_current_pending(self):
+ graph = self.make_graph({
+ 'head':['child'],
+ 'child':[NULL_REVISION],
+ })
+ search = graph._make_breadth_first_searcher(['head'])
+ # At the start, nothing has been seen, to its all excluded:
+ self.assertEqual((set(['head']), set(['head'])), search.get_recipe())
+ self.assertEqual(set(), search.seen)
+ # using next:
+ expected = [
+ (set(['head']), (set(['head']), set(['child']))),
+ (set(['head', 'child']), (set(['head']), set([NULL_REVISION]))),
+ (set(['head', 'child', NULL_REVISION]), (set(['head']), set())),
+ ]
+ self.assertSeenAndRecipes(expected, search, search.next)
+ # using next_with_ghosts:
+ search = graph._make_breadth_first_searcher(['head'])
+ self.assertSeenAndRecipes(expected, search, search.next_with_ghosts)
+
class TestCachingParentsProvider(tests.TestCase):
More information about the bazaar-commits
mailing list