bzrlib.graph._BreadthFirstSearcher : API documentation

Parallel search breadth-first the ancestry of revisions.

This class implements the iterator protocol, but additionally 1. provides a set of seen ancestors, and 2. allows some ancestries to be unsearched, via stop_searching_any

Method	__init__	Undocumented
Method	__repr__	Undocumented
Method	get_result	Get a SearchResult for the current state of this searcher.
Method	step	Undocumented
Method	next	Return the next ancestors of this revision.
Method	next_with_ghosts	Return the next found ancestors, with ghosts split out.
Method	__iter__	Undocumented
Method	find_seen_ancestors	Find ancestors of these revisions that have already been seen.
Method	stop_searching_any	Remove any of the specified revisions from the search list.
Method	start_searching	Add revisions to the search.
Method	_advance	Advance the search.
Method	_do_query	Query for revisions.

def __init__(self, revisions, parents_provider):

Undocumented

def __repr__(self):

Undocumented

def get_result(self):

Get a SearchResult for the current state of this searcher.

Returns 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.

def step(self):

Undocumented

def next(self):

Return the next ancestors of this revision.

Ancestors are returned in the order they are seen in a breadth-first traversal. No ancestor will be returned more than once. Ancestors are returned before their parentage is queried, so ghosts and missing revisions (including the start revisions) are included in the result. This can save a round trip in LCA style calculation by allowing convergence to be detected without reading the data for the revision the convergence occurs on.

Returns A set of revision_ids.

def next_with_ghosts(self):

Return the next found ancestors, with ghosts split out.

Ancestors are returned in the order they are seen in a breadth-first traversal. No ancestor will be returned more than once. Ancestors are returned only after asking for their parents, which allows us to detect which revisions are ghosts and which are not.

Returns A tuple with (present ancestors, ghost ancestors) sets.

def _advance(self):

Advance the search.

Updates self.seen, self._next_query, self._current_present, self._current_ghosts, self._current_parents and self._iterations.

def _do_query(self, revisions):

Query for revisions.

Adds revisions to the seen set.

Parameters	revisions	Revisions to query.
Returns	A tuple: (set(found_revisions), set(ghost_revisions), set(parents_of_found_revisions), dict(found_revisions:parents)).

def __iter__(self):

Undocumented

def find_seen_ancestors(self, revisions):

Find ancestors of these revisions that have already been seen.

This function generally makes the assumption that querying for the parents of a node that has already been queried is reasonably cheap. (eg, not a round trip to a remote host).

def stop_searching_any(self, revisions):

Remove any of the specified revisions from the search list.

None of the specified revisions are required to be present in the search list.

It is okay to call stop_searching_any() for revisions which were seen in previous iterations. It is the callers responsibility to call find_seen_ancestors() to make sure that current search tips that are ancestors of those revisions are also stopped. All explicitly stopped revisions will be excluded from the search result's get_keys(), though.

def start_searching(self, 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)).

b.g._BreadthFirstSearcher(object) : class documentation