b.graph : module documentation

Part of bzrlib

No module docstring
Class DictParentsProvider A parents provider for Graph objects.
Class StackedParentsProvider A parents provider which stacks (or unions) multiple providers.
Class CachingParentsProvider A parents provider which will cache the revision => parents as a dict.
Class CallableToParentsProviderAdapter A parents provider that adapts any callable to the parents provider API.
Class Graph Provide incremental access to revision graphs.
Class HeadsCache A cache of results for graph heads calls.
Class FrozenHeadsCache Cache heads() calls, assuming the caller won't modify them.
Class AbstractSearchResult The result of a search, describing a set of keys.
Class AbstractSearch A search that can be executed, producing a search result.
Class SearchResult The result of a breadth first search.
Class PendingAncestryResult A search result that will reconstruct the ancestry for some graph heads.
Class EmptySearchResult An empty search result.
Class EverythingResult A search result that simply requests everything in the repository.
Class EverythingNotInOther Find all revisions in that are in one repo but not the other.
Class NotInOtherForRevs Find all revisions missing in one repo for a some specific heads.
Function invert_parent_map Given a map from child => parents, create a map of parent=>children
Function limited_search_result_from_parent_map Transform a parent_map that is searching 'tip_keys' into an
Function search_result_from_parent_map Transform a parent_map into SearchResult information.
Function collapse_linear_regions Collapse regions of the graph that are 'linear'.
Class GraphThunkIdsToKeys Forwards calls about 'ids' to be about keys internally.
Class _BreadthFirstSearcher Parallel search breadth-first the ancestry of revisions.
Function _find_possible_heads Walk backwards (towards children) through the parent_map.
Function _run_search Given a parent map, run a _BreadthFirstSearcher on it.
def invert_parent_map(parent_map):
Given a map from child => parents, create a map of parent=>children
def _find_possible_heads(parent_map, tip_keys, depth):
Walk backwards (towards children) through the parent_map.

This finds 'heads' that will hopefully succinctly describe our search graph.

def _run_search(parent_map, heads, exclude_keys):
Given a parent map, run a _BreadthFirstSearcher on it.

Start at heads, walk until you hit exclude_keys. As a further improvement, watch for any heads that you encounter while walking, which means they were not heads of the search.

This is mostly used to generate a succinct recipe for how to walk through most of parent_map.

Returns(_BreadthFirstSearcher, set(heads_encountered_by_walking))
def limited_search_result_from_parent_map(parent_map, missing_keys, tip_keys, depth):

Transform a parent_map that is searching 'tip_keys' into an approximate SearchResult.

We should be able to generate a SearchResult from a given set of starting keys, that covers a subset of parent_map that has the last step pointing at tip_keys. This is to handle the case that really-long-searches shouldn't be started from scratch on each get_parent_map request, but we do want to filter out some of the keys that we've already seen, so we don't get information that we already know about on every request.

The server will validate the search (that starting at start_keys and stopping at stop_keys yields the exact key_count), so we have to be careful to give an exact recipe.

Basic algorithm is:
  1. Invert parent_map to get child_map (todo: have it cached and pass it in)
  2. Starting at tip_keys, walk towards children for 'depth' steps.
  3. At that point, we have the 'start' keys.
  4. Start walking parent_map from 'start' keys, counting how many keys are seen, and generating stop_keys for anything that would walk outside of the parent_map.
Parametersparent_mapA map from {child_id: (parent_ids,)}
missing_keysparent_ids that we know are unavailable
tip_keysthe revision_ids that we are searching
depthHow far back to walk.
def search_result_from_parent_map(parent_map, missing_keys):
Transform a parent_map into SearchResult information.
def collapse_linear_regions(parent_map):

Collapse regions of the graph that are 'linear'.

For example:

A:[B], B:[C]

can be collapsed by removing B and getting:

A:[C]
Parametersparent_mapA dictionary mapping children to their parents
ReturnsAnother dictionary with 'linear' chains collapsed
API Documentation for Bazaar, generated by pydoctor at 2019-07-18 00:29:27.