b.g.Graph(object) : class documentation

Part of bzrlib.graph View In Hierarchy

Provide incremental access to revision graphs.

This is the generic implementation; it is intended to be subclassed to specialize it for other repository types.

Method __init__ Construct a Graph that uses several graphs as its input
Method __repr__ Undocumented
Method find_lca Determine the lowest common ancestors of the provided revisions
Method find_difference Determine the graph difference between two revisions
Method find_descendants Find descendants of old_key that are ancestors of new_key.
Method get_child_map Get a mapping from parents to children of the specified keys.
Method find_distance_to_null Find the left-hand distance to the NULL_REVISION.
Method find_lefthand_distances Find the distance to null for all the keys in keys.
Method find_unique_ancestors Find the unique ancestors for a revision versus others.
Method get_parent_map Get a map of key:parent_list for revisions.
Method heads Return the heads from amongst keys.
Method find_merge_order Find the order that each revision was merged into tip.
Method find_lefthand_merger Find the first lefthand ancestor of tip_key that merged merged_key.
Method find_unique_lca Find a unique LCA.
Method iter_ancestry Iterate the ancestry of this revision.
Method iter_lefthand_ancestry Undocumented
Method iter_topo_order Iterate through the input revisions in topological order.
Method is_ancestor Determine whether a revision is an ancestor of another.
Method is_between Determine whether a revision is between two others.
Method _find_descendant_ancestors Find ancestors of new_key that may be descendants of old_key.
Method _find_initial_unique_nodes Steps 1-3 of find_unique_ancestors.
Method _make_unique_searchers Create a searcher for all the unique search tips (step 4).
Method _step_unique_and_common_searchers Step all the searchers
Method _find_nodes_common_to_all_unique Find nodes that are common to all unique_tip_searchers.
Method _collapse_unique_searchers Combine searchers that are searching the same tips.
Method _refine_unique_nodes Steps 5-8 of find_unique_ancestors.
Method _make_breadth_first_searcher Undocumented
Method _find_border_ancestors Find common ancestors with at least one uncommon descendant.
Method _search_for_extra_common Make sure that unique nodes are genuinely unique.
Method _remove_simple_descendants remove revisions which are children of other ones in the set
def __init__(self, parents_provider):
Construct a Graph that uses several graphs as its input

This should not normally be invoked directly, because there may be specialized implementations for particular repository types. See Repository.get_graph().

Parametersparents_providerAn object providing a get_parent_map call conforming to the behavior of StackedParentsProvider.get_parent_map.
def __repr__(self):
Undocumented
def find_lca(self, *revisions):

Determine the lowest common ancestors of the provided revisions

A lowest common ancestor is a common ancestor none of whose descendants are common ancestors. In graphs, unlike trees, there may be multiple lowest common ancestors.

This algorithm has two phases. Phase 1 identifies border ancestors, and phase 2 filters border ancestors to determine lowest common ancestors.

In phase 1, border ancestors are identified, using a breadth-first search starting at the bottom of the graph. Searches are stopped whenever a node or one of its descendants is determined to be common

In phase 2, the border ancestors are filtered to find the least common ancestors. This is done by searching the ancestries of each border ancestor.

Phase 2 is perfomed on the principle that a border ancestor that is not an ancestor of any other border ancestor is a least common ancestor.

Searches are stopped when they find a node that is determined to be a common ancestor of all border ancestors, because this shows that it cannot be a descendant of any border ancestor.

The scaling of this operation should be proportional to:

  1. The number of uncommon ancestors
  2. The number of border ancestors
  3. The length of the shortest path between a border ancestor and an ancestor of all border ancestors.
def find_difference(self, left_revision, right_revision):
Determine the graph difference between two revisions
def find_descendants(self, old_key, new_key):
Find descendants of old_key that are ancestors of new_key.
def _find_descendant_ancestors(self, old_key, new_key):
Find ancestors of new_key that may be descendants of old_key.
def get_child_map(self, keys):
Get a mapping from parents to children of the specified keys.

This is simply the inversion of get_parent_map. Only supplied keys will be discovered as children. :return: a dict of key:child_list for keys.

def find_distance_to_null(self, target_revision_id, known_revision_ids):
Find the left-hand distance to the NULL_REVISION.

(This can also be considered the revno of a branch at target_revision_id.)

Parameterstarget_revision_idA revision_id which we would like to know the revno for.
known_revision_ids[(revision_id, revno)] A list of known revno, revision_id tuples. We'll use this to seed the search.
def find_lefthand_distances(self, keys):
Find the distance to null for all the keys in keys.
Parameterskeyskeys to lookup.
ReturnsA dict key->distance for all of keys.
def find_unique_ancestors(self, unique_revision, common_revisions):
Find the unique ancestors for a revision versus others.

This returns the ancestry of unique_revision, excluding all revisions in the ancestry of common_revisions. If unique_revision is in the ancestry, then the empty set will be returned.

Parametersunique_revisionThe revision_id whose ancestry we are interested in. (XXX: Would this API be better if we allowed multiple revisions on to be searched here?)
common_revisionsRevision_ids of ancestries to exclude.
ReturnsA set of revisions in the ancestry of unique_revision
def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
Steps 1-3 of find_unique_ancestors.

Find the maximal set of unique nodes. Some of these might actually still be common, but we are sure that there are no other unique nodes.

Returns(unique_searcher, common_searcher)
def _make_unique_searchers(self, unique_nodes, unique_searcher, common_searcher):
Create a searcher for all the unique search tips (step 4).

As a side effect, the common_searcher will stop searching any nodes that are ancestors of the unique searcher tips.

Returns(all_unique_searcher, unique_tip_searchers)
def _step_unique_and_common_searchers(self, common_searcher, unique_tip_searchers, unique_searcher):
Step all the searchers
def _find_nodes_common_to_all_unique(self, unique_tip_searchers, all_unique_searcher, newly_seen_unique, step_all_unique):
Find nodes that are common to all unique_tip_searchers.

If it is time, step the all_unique_searcher, and add its nodes to the result.

def _collapse_unique_searchers(self, unique_tip_searchers, common_to_all_unique_nodes):
Combine searchers that are searching the same tips.

When two searchers are searching the same tips, we can stop one of the searchers. We also know that the maximal set of common ancestors is the intersection of the two original searchers.

ReturnsA list of searchers that are searching unique nodes.
def _refine_unique_nodes(self, unique_searcher, all_unique_searcher, unique_tip_searchers, common_searcher):
Steps 5-8 of find_unique_ancestors.

This function returns when common_searcher has stopped searching for more nodes.

def get_parent_map(self, revisions):
Get a map of key:parent_list for revisions.

This implementation delegates to get_parents, for old parent_providers that do not supply get_parent_map.

def _make_breadth_first_searcher(self, revisions):
Undocumented
def _find_border_ancestors(self, revisions):
Find common ancestors with at least one uncommon descendant.

Border ancestors are identified using a breadth-first search starting at the bottom of the graph. Searches are stopped whenever a node or one of its descendants is determined to be common.

This will scale with the number of uncommon ancestors.

As well as the border ancestors, a set of seen common ancestors and a list of sets of seen ancestors for each input revision is returned. This allows calculation of graph difference from the results of this operation.

def heads(self, keys):
Return the heads from amongst keys.

This is done by searching the ancestries of each key. Any key that is reachable from another key is not returned; all the others are.

This operation scales with the relative depth between any two keys. If any two keys are completely disconnected all ancestry of both sides will be retrieved.

ParameterskeysAn iterable of keys.
ReturnsA set of the heads. Note that as a set there is no ordering information. Callers will need to filter their input to create order if they need it.
def find_merge_order(self, tip_revision_id, lca_revision_ids):
Find the order that each revision was merged into tip.

This basically just walks backwards with a stack, and walks left-first until it finds a node to stop.

def find_lefthand_merger(self, merged_key, tip_key):
Find the first lefthand ancestor of tip_key that merged merged_key.

We do this by first finding the descendants of merged_key, then walking through the lefthand ancestry of tip_key until we find a key that doesn't descend from merged_key. Its child is the key that merged merged_key.

ReturnsThe first lefthand ancestor of tip_key to merge merged_key. merged_key if it is a lefthand ancestor of tip_key. None if no ancestor of tip_key merged merged_key.
def find_unique_lca(self, left_revision, right_revision, count_steps=False):
Find a unique LCA.

Find lowest common ancestors. If there is no unique common ancestor, find the lowest common ancestors of those ancestors.

Iteration stops when a unique lowest common ancestor is found. The graph origin is necessarily a unique lowest common ancestor.

Note that None is not an acceptable substitute for NULL_REVISION. in the input for this method.

Parameterscount_stepsIf True, the return value will be a tuple of (unique_lca, steps) where steps is the number of times that find_lca was run. If False, only unique_lca is returned.
def iter_ancestry(self, revision_ids):
Iterate the ancestry of this revision.
Parametersrevision_idsNodes to start the search
ReturnsYield tuples mapping a revision_id to its parents for the ancestry of revision_id. Ghosts will be returned with None as their parents, and nodes with no parents will have NULL_REVISION as their only parent. (As defined by get_parent_map.) There will also be a node for (NULL_REVISION, ())
def iter_lefthand_ancestry(self, start_key, stop_keys=None):
Undocumented
def iter_topo_order(self, revisions):
Iterate through the input revisions in topological order.

This sorting only ensures that parents come before their children. An ancestor may sort after a descendant if the relationship is not visible in the supplied list of revisions.

def is_ancestor(self, candidate_ancestor, candidate_descendant):
Determine whether a revision is an ancestor of another.

We answer this using heads() as heads() has the logic to perform the smallest number of parent lookups to determine the ancestral relationship between N revisions.

def is_between(self, revid, lower_bound_revid, upper_bound_revid):
Determine whether a revision is between two others.

returns true if and only if: lower_bound_revid <= revid <= upper_bound_revid

def _search_for_extra_common(self, common, searchers):
Make sure that unique nodes are genuinely unique.

After _find_border_ancestors, all nodes marked "common" are indeed common. Some of the nodes considered unique are not, due to history shortcuts stopping the searches early.

We know that we have searched enough when all common search tips are descended from all unique (uncommon) nodes because we know that a node cannot be an ancestor of its own ancestor.

ParameterscommonA set of common nodes
searchersThe searchers returned from _find_border_ancestors
ReturnsNone
def _remove_simple_descendants(self, revisions, parent_map):
remove revisions which are children of other ones in the set

This doesn't do any graph searching, it just checks the immediate parent_map to find if there are any children which can be removed.

ParametersrevisionsA set of revision_ids
ReturnsA set of revision_ids with the children removed
API Documentation for Bazaar, generated by pydoctor at 2019-07-21 00:34:56.