Rev 3179: Update graph searchers stop_searching_any and start_searching for next_with_ghosts. in http://people.ubuntu.com/~robertc/baz2.0/breadth-first-ghosts
Robert Collins
robertc at robertcollins.net
Mon Jan 14 00:55:01 GMT 2008
At http://people.ubuntu.com/~robertc/baz2.0/breadth-first-ghosts
------------------------------------------------------------
revno: 3179
revision-id:robertc at robertcollins.net-20080114005456-d4a5iief649hmtiy
parent: robertc at robertcollins.net-20080113235717-9a1w22q93j81nd0o
committer: Robert Collins <robertc at robertcollins.net>
branch nick: breadth-first-ghosts
timestamp: Mon 2008-01-14 11:54:56 +1100
message:
Update graph searchers stop_searching_any and start_searching for next_with_ghosts.
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-13 23:57:17 +0000
+++ b/bzrlib/graph.py 2008-01-14 00:54:56 +0000
@@ -570,19 +570,28 @@
self._current_ghosts.
"""
self._iterations += 1
+ found, ghosts, next, parents = self._do_query(self._next_query)
+ self._current_present = found
+ self._current_ghosts = ghosts
+ self._next_query = next
+ self._current_parents = parents
+
+ def _do_query(self, revisions):
+ """Query for revisions.
+
+ :param revisions: Revisions to query.
+ :return: A tuple: (set(found_revisions), set(ghost_revisions),
+ set(parents_of_found_revisions), dict(found_revisions:parents)).
+ """
found_parents = set()
- new_search_revisions = set()
- parent_map = self._parents_provider.get_parent_map(
- self._next_query)
+ parents_of_found = set()
+ parent_map = self._parents_provider.get_parent_map(revisions)
for rev_id, parents in parent_map.iteritems():
found_parents.add(rev_id)
- new_search_revisions.update(p for p in parents if
- p not in self.seen)
- ghost_parents = self._next_query - found_parents
- self._next_query = new_search_revisions
- self.seen.update(self._next_query)
- self._current_present = found_parents
- self._current_ghosts = ghost_parents
+ 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):
return self
@@ -606,10 +615,56 @@
None of the specified revisions are required to be present in the
search list. In this case, the call is a no-op.
"""
- stopped = self._next_query.intersection(revisions)
- self._next_query = self._next_query.difference(revisions)
+ revisions = frozenset(revisions)
+ if self._returning == 'query':
+ stopped = self._next_query.intersection(revisions)
+ self._next_query = self._next_query.difference(revisions)
+ else:
+ stopped = set()
+ stopped.update(self._current_present.intersection(revisions))
+ stopped.update(self._current_ghosts.intersection(revisions))
+ self._current_present.difference_update(stopped)
+ self._current_ghosts.difference_update(stopped)
+ # stopping 'x' should stop returning parents of 'x', but
+ # not if 'y' always references those same parents
+ stop_rev_references = {}
+ for rev in stopped:
+ for parent_id in self._current_parents[rev]:
+ if parent_id not in stop_rev_references:
+ stop_rev_references[parent_id] = 0
+ stop_rev_references[parent_id] += 1
+ # if only the stopped revisions reference it, the ref count will be
+ # 0 after this loop
+ for rev, parents in self._current_parents.iteritems():
+ for parent_id in parents:
+ try:
+ stop_rev_references[parent_id] -= 1
+ except KeyError:
+ pass
+ stop_parents = set()
+ for rev_id, refs in stop_rev_references.iteritems():
+ if refs == 0:
+ stop_parents.add(rev_id)
+ self._next_query.difference_update(stop_parents)
return stopped
def start_searching(self, revisions):
- self._next_query.update(revisions.difference(self.seen))
- self.seen.update(revisions)
+ """Add revisions to the search.
+
+ The parents of revisions will be returned from the next call to next()
+ or next_with_ghosts(). If next_with_ghosts was the most recently used
+ next* call then the return value is the result of looking up the
+ ghost/not ghost status of revisions. (A tuple (present, ghosted)).
+ """
+ revisions = frozenset(revisions)
+ if self._returning == 'query':
+ self._next_query.update(revisions.difference(self.seen))
+ self.seen.update(revisions)
+ else:
+ # perform a query on revisions
+ revs, ghosts, query, parents = self._do_query(revisions)
+ self._current_present.update(revs)
+ self._current_ghosts.update(ghosts)
+ self._next_query.update(query)
+ self._current_parents.update(parents)
+ return revs, ghosts
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py 2008-01-13 23:57:17 +0000
+++ b/bzrlib/tests/test_graph.py 2008-01-14 00:54:56 +0000
@@ -716,6 +716,37 @@
search.next())
self.assertRaises(StopIteration, search.next_with_ghosts)
+ def test_breadth_first_change_search(self):
+ # To make the API robust, we allow changing from next() to
+ # next_with_ghosts() and vice verca.
+ parent_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())
+ self.assertEqual(set(['present']),
+ search.stop_searching_any(['present']))
+ self.assertEqual((set(['other']), set(['other_ghost'])),
+ search.start_searching(['other', 'other_ghost']))
+ self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
+ self.assertRaises(StopIteration, search.next_with_ghosts)
+ # next includes them
+ search = graph._make_breadth_first_searcher(['head'])
+ self.assertEqual(set(['head']), search.next())
+ self.assertEqual(set(['present']), search.next())
+ self.assertEqual(set(['present']),
+ search.stop_searching_any(['present']))
+ search.start_searching(['other', 'other_ghost'])
+ self.assertEqual(set(['other_2']), search.next())
+ self.assertRaises(StopIteration, search.next)
+
class TestCachingParentsProvider(tests.TestCase):
More information about the bazaar-commits
mailing list