483
483
def heads(self, keys):
484
484
"""Return the heads of keys.
486
Similar to Graph.heads(). The main difference is that the return value
487
is a frozen set which cannot be mutated.
486
489
:see also: Graph.heads.
487
490
:param keys: The keys to calculate heads for.
488
:return: A set containing the heads, which may be mutated without
489
affecting future lookups.
491
:return: A frozenset containing the heads.
491
493
keys = frozenset(keys)
493
return set(self._heads[keys])
495
return self._heads[keys]
495
heads = self.graph.heads(keys)
497
heads = frozenset(self.graph.heads(keys))
496
498
self._heads[keys] = heads
501
def cache(self, keys, heads):
502
"""Store a known value."""
503
self._heads[frozenset(keys)] = frozenset(heads)
500
506
class _BreadthFirstSearcher(object):
521
532
return ('_BreadthFirstSearcher(iterations=%d, %s,'
522
533
' seen=%r)' % (self._iterations, search, list(self.seen)))
535
def get_result(self):
536
"""Get a SearchResult for the current state of this searcher.
538
:return: A SearchResult for this search so far. The SearchResult is
539
static - the search can be advanced and the search result will not
540
be invalidated or altered.
542
if self._returning == 'next':
543
# We have to know the current nodes children to be able to list the
544
# exclude keys for them. However, while we could have a second
545
# look-ahead result buffer and shuffle things around, this method
546
# is typically only called once per search - when memoising the
547
# results of the search.
548
found, ghosts, next, parents = self._do_query(self._next_query)
549
# pretend we didn't query: perhaps we should tweak _do_query to be
550
# entirely stateless?
551
self.seen.difference_update(next)
552
next_query = next.union(ghosts)
554
next_query = self._next_query
555
excludes = self._stopped_keys.union(next_query)
556
included_keys = self.seen.difference(excludes)
557
return SearchResult(self._started_keys, excludes, len(included_keys),
525
561
"""Return the next ancestors of this revision.
576
614
self._current_ghosts = ghosts
577
615
self._next_query = next
578
616
self._current_parents = parents
617
# ghosts are implicit stop points, otherwise the search cannot be
618
# repeated when ghosts are filled.
619
self._stopped_keys.update(ghosts)
580
621
def _do_query(self, revisions):
581
622
"""Query for revisions.
624
Adds revisions to the seen set.
583
626
:param revisions: Revisions to query.
584
627
:return: A tuple: (set(found_revisions), set(ghost_revisions),
585
628
set(parents_of_found_revisions), dict(found_revisions:parents)).
587
630
found_parents = set()
588
631
parents_of_found = set()
632
# revisions may contain nodes that point to other nodes in revisions:
633
# we want to filter them out.
634
self.seen.update(revisions)
589
635
parent_map = self._parents_provider.get_parent_map(revisions)
590
636
for rev_id, parents in parent_map.iteritems():
591
637
found_parents.add(rev_id)
592
638
parents_of_found.update(p for p in parents if p not in self.seen)
593
639
ghost_parents = revisions - found_parents
594
self.seen.update(parents_of_found)
595
640
return found_parents, ghost_parents, parents_of_found, parent_map
597
642
def __iter__(self):
621
666
stopped = self._next_query.intersection(revisions)
622
667
self._next_query = self._next_query.difference(revisions)
625
stopped.update(self._current_present.intersection(revisions))
626
stopped.update(self._current_ghosts.intersection(revisions))
669
stopped_present = self._current_present.intersection(revisions)
670
stopped = stopped_present.union(
671
self._current_ghosts.intersection(revisions))
627
672
self._current_present.difference_update(stopped)
628
673
self._current_ghosts.difference_update(stopped)
629
674
# stopping 'x' should stop returning parents of 'x', but
630
675
# not if 'y' always references those same parents
631
676
stop_rev_references = {}
677
for rev in stopped_present:
633
678
for parent_id in self._current_parents[rev]:
634
679
if parent_id not in stop_rev_references:
635
680
stop_rev_references[parent_id] = 0
658
704
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
660
706
revisions = frozenset(revisions)
707
self._started_keys.update(revisions)
708
new_revisions = revisions.difference(self.seen)
709
revs, ghosts, query, parents = self._do_query(revisions)
710
self._stopped_keys.update(ghosts)
661
711
if self._returning == 'next':
662
self._next_query.update(revisions.difference(self.seen))
663
self.seen.update(revisions)
712
self._next_query.update(new_revisions)
665
714
# perform a query on revisions
666
revs, ghosts, query, parents = self._do_query(revisions)
667
715
self._current_present.update(revs)
668
716
self._current_ghosts.update(ghosts)
669
717
self._next_query.update(query)
670
718
self._current_parents.update(parents)
671
719
return revs, ghosts
722
class SearchResult(object):
723
"""The result of a breadth first search.
725
A SearchResult provides the ability to reconstruct the search or access a
726
set of the keys the search found.
729
def __init__(self, start_keys, exclude_keys, key_count, keys):
730
"""Create a SearchResult.
732
:param start_keys: The keys the search started at.
733
:param exclude_keys: The keys the search excludes.
734
:param key_count: The total number of keys (from start to but not
736
:param keys: The keys the search found. Note that in future we may get
737
a SearchResult from a smart server, in which case the keys list is
738
not necessarily immediately available.
740
self._recipe = (start_keys, exclude_keys, key_count)
741
self._keys = frozenset(keys)
743
def get_recipe(self):
744
"""Return a recipe that can be used to replay this search.
746
The recipe allows reconstruction of the same results at a later date
747
without knowing all the found keys. The essential elements are a list
748
of keys to start and and to stop at. In order to give reproducible
749
results when ghosts are encountered by a search they are automatically
750
added to the exclude list (or else ghost filling may alter the
753
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
754
recreate the results of this search, create a breadth first
755
searcher on the same graph starting at start_keys. Then call next()
756
(or next_with_ghosts()) repeatedly, and on every result, call
757
stop_searching_any on any keys from the exclude_keys set. The
758
revision_count value acts as a trivial cross-check - the found
759
revisions of the new search should have as many elements as
760
revision_count. If it does not, then additional revisions have been
761
ghosted since the search was executed the first time and the second
767
"""Return the keys found in this search.
769
:return: A set of keys.
added
removed
bzrlib/graph.py
