Part of bzrlib.graph View In Hierarchy
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 |
This should not normally be invoked directly, because there may be specialized implementations for particular repository types. See Repository.get_graph().
Parameters | parents_provider | An object providing a get_parent_map call conforming to the behavior of StackedParentsProvider.get_parent_map. |
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:
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.
(This can also be considered the revno of a branch at target_revision_id.)
Parameters | target_revision_id | A 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. |
Parameters | keys | keys to lookup. |
Returns | A dict key->distance for all of keys. |
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.
Parameters | unique_revision | The 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_revisions | Revision_ids of ancestries to exclude. | |
Returns | A set of revisions in the ancestry of unique_revision |
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) |
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) |
If it is time, step the all_unique_searcher, and add its nodes to the result.
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.
Returns | A list of searchers that are searching unique nodes. |
This function returns when common_searcher has stopped searching for more nodes.
This implementation delegates to get_parents, for old parent_providers that do not supply get_parent_map.
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.
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.
Parameters | keys | An iterable of keys. |
Returns | A 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. |
This basically just walks backwards with a stack, and walks left-first until it finds a node to stop.
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.
Returns | The 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. |
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.
Parameters | count_steps | If 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. |
Parameters | revision_ids | Nodes to start the search |
Returns | Yield 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, ()) |
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.
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.
returns true if and only if: lower_bound_revid <= revid <= upper_bound_revid
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.
Parameters | common | A set of common nodes |
searchers | The searchers returned from _find_border_ancestors | |
Returns | None |
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.
Parameters | revisions | A set of revision_ids |
Returns | A set of revision_ids with the children removed |