Rev 3190: Create a SearchResult object which can be used as a replacement for sets. in http://people.ubuntu.com/~robertc/baz2.0/search-results
Robert Collins
robertc at robertcollins.net
Wed Jan 16 01:25:44 GMT 2008
At http://people.ubuntu.com/~robertc/baz2.0/search-results
------------------------------------------------------------
revno: 3190
revision-id:robertc at robertcollins.net-20080116012539-k9p8rn82m02cat2m
parent: robertc at robertcollins.net-20080116005306-4o2tny789tuo60gb
committer: Robert Collins <robertc at robertcollins.net>
branch nick: search-results
timestamp: Wed 2008-01-16 12:25:39 +1100
message:
Create a SearchResult object which can be used as a replacement for sets.
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-16 00:53:06 +0000
+++ b/bzrlib/graph.py 2008-01-16 01:25:39 +0000
@@ -526,26 +526,12 @@
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.
+ def get_result(self):
+ """Get a SearchResult for the current state of this searcher.
- The recipe allows reconstruction of the same results at a later date
- without knowing all the found keys. The essential elements are a list
- of keys to start and and to stop at. In order to give reproducible
- results when ghosts are encountered by a search they are automatically
- added to the exclude list (or else ghost filling may alter the
- results).
-
- :return: A tuple (start_keys_set, exclude_keys_set, revision_count). 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. The
- revision_count value acts as a trivial cross-check - the found
- revisions of the new search should have as many elements as
- revision_count. If it does not, then additional revisions have been
- ghosted since the search was executed the first time and the second
- time.
+ :return: A SearchResult for this search so far. The SearchResult is
+ static - the search can be advanced and the search result will not
+ be invalidated or altered.
"""
if self._returning == 'next':
# We have to know the current nodes children to be able to list the
@@ -561,8 +547,9 @@
else:
next_query = self._next_query
excludes = self._stopped_keys.union(next_query)
- return (self._started_keys, excludes,
- len(self.seen.difference(excludes)))
+ included_keys = self.seen.difference(excludes)
+ return SearchResult(self._started_keys, excludes, len(included_keys),
+ included_keys)
def next(self):
"""Return the next ancestors of this revision.
@@ -724,3 +711,56 @@
self._next_query.update(query)
self._current_parents.update(parents)
return revs, ghosts
+
+
+class SearchResult(object):
+ """The result of a breadth first search.
+
+ A SearchResult provides the ability to reconstruct the search or access a
+ set of the keys the search found.
+ """
+
+ def __init__(self, start_keys, exclude_keys, key_count, keys):
+ """Create a SearchResult.
+
+ :param start_keys: The keys the search started at.
+ :param exclude_keys: The keys the search excludes.
+ :param key_count: The total number of keys (from start to but not
+ including exclude).
+ :param keys: The keys the search found. Note that in future we may get
+ a SearchResult from a smart server, in which case the keys list is
+ not necessarily immediately available.
+ """
+ self._recipe = (start_keys, exclude_keys, key_count)
+ self._keys = frozenset(keys)
+
+ def get_recipe(self):
+ """Return a recipe that can be used to replay this search.
+
+ The recipe allows reconstruction of the same results at a later date
+ without knowing all the found keys. The essential elements are a list
+ of keys to start and and to stop at. In order to give reproducible
+ results when ghosts are encountered by a search they are automatically
+ added to the exclude list (or else ghost filling may alter the
+ results).
+
+ :return: A tuple (start_keys_set, exclude_keys_set, revision_count). 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. The
+ revision_count value acts as a trivial cross-check - the found
+ revisions of the new search should have as many elements as
+ revision_count. If it does not, then additional revisions have been
+ ghosted since the search was executed the first time and the second
+ time.
+ """
+ return self._recipe
+
+ def get_keys(self):
+ """Return the keys found in this search.
+
+ :return: A set of keys.
+ """
+ return self._keys
+
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py 2008-01-16 00:53:06 +0000
+++ b/bzrlib/tests/test_graph.py 2008-01-16 01:25:39 +0000
@@ -728,26 +728,30 @@
self.assertEqual(set(['other_2']), search.next())
self.assertRaises(StopIteration, search.next)
- def assertSeenAndRecipes(self, instructions, search, next):
- """Check the results of .seen and get_recipe() for a seach.
+ def assertSeenAndResult(self, instructions, search, next):
+ """Check the results of .seen and get_result() for a seach.
- :param instructions: A list of tuples (seen, get_recipe_result, starts,
- stops). seen and get_recipe_result are results to check. starts and
- stops are parameters to pass to start_searching and
- stop_searching_any during each iteration, if they are not None.
+ :param instructions: A list of tuples:
+ (seen, recipe, included_keys, starts, stops).
+ seen, recipe and included_keys are results to check on the search
+ and the searches get_result(). starts and stops are parameters to
+ pass to start_searching and stop_searching_any during each
+ iteration, if they are not None.
:param search: The search to use.
:param next: A callable to advance the search.
"""
- for seen, recipe, starts, stops in instructions:
+ for seen, recipe, included_keys, starts, stops in instructions:
next()
if starts is not None:
search.start_searching(starts)
if stops is not None:
search.stop_searching_any(stops)
- self.assertEqual(recipe, search.get_recipe())
+ result = search.get_result()
+ self.assertEqual(recipe, result.get_recipe())
+ self.assertEqual(set(included_keys), result.get_keys())
self.assertEqual(seen, search.seen)
- def test_breadth_first_get_recipe_excludes_current_pending(self):
+ def test_breadth_first_get_result_excludes_current_pending(self):
graph = self.make_graph({
'head':['child'],
'child':[NULL_REVISION],
@@ -755,23 +759,26 @@
})
search = graph._make_breadth_first_searcher(['head'])
# At the start, nothing has been seen, to its all excluded:
+ result = search.get_result()
self.assertEqual((set(['head']), set(['head']), 0),
- search.get_recipe())
+ result.get_recipe())
+ self.assertEqual(set(), result.get_keys())
self.assertEqual(set(), search.seen)
# using next:
expected = [
- (set(['head']), (set(['head']), set(['child']), 1), None, None),
+ (set(['head']), (set(['head']), set(['child']), 1),
+ ['head'], None, None),
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
- None, None),
+ ['head', 'child'], None, None),
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
- None, None),
+ ['head', 'child', NULL_REVISION], None, None),
]
- self.assertSeenAndRecipes(expected, search, search.next)
+ self.assertSeenAndResult(expected, search, search.next)
# using next_with_ghosts:
search = graph._make_breadth_first_searcher(['head'])
- self.assertSeenAndRecipes(expected, search, search.next_with_ghosts)
+ self.assertSeenAndResult(expected, search, search.next_with_ghosts)
- def test_breadth_first_get_recipe_starts_stops(self):
+ def test_breadth_first_get_result_starts_stops(self):
graph = self.make_graph({
'head':['child'],
'child':[NULL_REVISION],
@@ -784,8 +791,10 @@
# Starting with nothing and adding a search works:
search.start_searching(['head'])
# head has been seen:
+ result = search.get_result()
self.assertEqual((set(['head']), set(['child']), 1),
- search.get_recipe())
+ result.get_recipe())
+ self.assertEqual(set(['head']), result.get_keys())
self.assertEqual(set(['head']), search.seen)
# using next:
expected = [
@@ -794,22 +803,22 @@
# called.
(set(['head', 'child', 'otherhead']),
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
- ['otherhead'], ['child']),
+ ['head', 'otherhead'], ['otherhead'], ['child']),
(set(['head', 'child', 'otherhead', 'otherchild']),
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
- None, None),
+ ['head', 'otherhead', 'otherchild'], None, None),
# stop searching excluded now
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
- None, ['excluded']),
+ ['head', 'otherhead', 'otherchild'], None, ['excluded']),
]
- self.assertSeenAndRecipes(expected, search, search.next)
+ self.assertSeenAndResult(expected, search, search.next)
# using next_with_ghosts:
search = graph._make_breadth_first_searcher([])
search.start_searching(['head'])
- self.assertSeenAndRecipes(expected, search, search.next_with_ghosts)
+ self.assertSeenAndResult(expected, search, search.next_with_ghosts)
- def test_breadth_first_get_recipe_ghosts_are_excluded(self):
+ def test_breadth_first_get_result_ghosts_are_excluded(self):
graph = self.make_graph({
'head':['child', 'ghost'],
'child':[NULL_REVISION],
@@ -820,17 +829,17 @@
expected = [
(set(['head']),
(set(['head']), set(['ghost', 'child']), 1),
- None, None),
+ ['head'], None, None),
(set(['head', 'child', 'ghost']),
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
- None, None),
+ ['head', 'child'], None, None),
]
- self.assertSeenAndRecipes(expected, search, search.next)
+ self.assertSeenAndResult(expected, search, search.next)
# using next_with_ghosts:
search = graph._make_breadth_first_searcher(['head'])
- self.assertSeenAndRecipes(expected, search, search.next_with_ghosts)
+ self.assertSeenAndResult(expected, search, search.next_with_ghosts)
- def test_breadth_first_get_recipe_starting_a_ghost_ghost_is_excluded(self):
+ def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
graph = self.make_graph({
'head':['child'],
'child':[NULL_REVISION],
@@ -841,15 +850,15 @@
expected = [
(set(['head', 'ghost']),
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
- ['ghost'], None),
+ ['head'], ['ghost'], None),
(set(['head', 'child', 'ghost']),
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
- None, None),
+ ['head', 'child'], None, None),
]
- self.assertSeenAndRecipes(expected, search, search.next)
+ self.assertSeenAndResult(expected, search, search.next)
# using next_with_ghosts:
search = graph._make_breadth_first_searcher(['head'])
- self.assertSeenAndRecipes(expected, search, search.next_with_ghosts)
+ self.assertSeenAndResult(expected, search, search.next_with_ghosts)
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
graph = self.make_graph({
@@ -861,17 +870,17 @@
expected = [
(set(['head']),
(set(['head']), set([NULL_REVISION]), 1),
- None, None),
+ ['head'], None, None),
(set(['head', NULL_REVISION]),
(set(['head']), set([]), 2),
- None, None),
+ ['head', NULL_REVISION], None, None),
]
- self.assertSeenAndRecipes(expected, search, search.next)
+ self.assertSeenAndResult(expected, search, search.next)
# using next_with_ghosts:
search = graph._make_breadth_first_searcher(['head'])
- self.assertSeenAndRecipes(expected, search, search.next_with_ghosts)
+ self.assertSeenAndResult(expected, search, search.next_with_ghosts)
- def test_breadth_first_search_get_recipe_after_StopIteration(self):
+ def test_breadth_first_search_get_result_after_StopIteration(self):
# StopIteration should not invalid anything..
graph = self.make_graph({
'head':[NULL_REVISION],
@@ -882,24 +891,27 @@
expected = [
(set(['head']),
(set(['head']), set([NULL_REVISION]), 1),
- None, None),
+ ['head'], None, None),
(set(['head', 'ghost', NULL_REVISION]),
(set(['head', 'ghost']), set(['ghost']), 2),
- ['ghost'], None),
+ ['head', NULL_REVISION], ['ghost'], None),
]
- self.assertSeenAndRecipes(expected, search, search.next)
+ self.assertSeenAndResult(expected, search, search.next)
self.assertRaises(StopIteration, search.next)
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
+ result = search.get_result()
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
- search.get_recipe())
+ result.get_recipe())
+ self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
# using next_with_ghosts:
search = graph._make_breadth_first_searcher(['head'])
- self.assertSeenAndRecipes(expected, search, search.next_with_ghosts)
+ self.assertSeenAndResult(expected, search, search.next_with_ghosts)
self.assertRaises(StopIteration, search.next)
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
+ result = search.get_result()
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
- search.get_recipe())
-
+ result.get_recipe())
+ self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
class TestCachingParentsProvider(tests.TestCase):
More information about the bazaar-commits
mailing list