Struct ForwardPartialPathStitcher

pub struct ForwardPartialPathStitcher<H> { /* private fields */ }

Implements a phased forward partial path stitching algorithm.

Our overall goal is to start with a set of seed partial paths, and to repeatedly extend each partial path by concatenating another, compatible partial path onto the end of it. (If there are multiple compatible partial paths, we concatenate each of them separately, resulting in more than one extension for the current path.)

We perform this processing in phases. At the start of each phase, we have a current set of partial paths that need to be processed. As we extend those partial paths, we add the extensions to the set of partial paths to process in the next phase. Phases are processed one at a time, each time you invoke the process_next_phase method.

After each phase has completed, you can use the previous_phase_partial_paths method to retrieve all of the partial paths that were discovered during that phase. That gives you a chance to add to the Database all of the other partial paths that we might need to extend those partial paths with before invoking the next phase.

If you don’t care about this phasing nonsense, you can instead preload your Database with all possible partial paths, and run the forward partial path stitching algorithm all the way to completion, using the find_all_complete_partial_paths method.

Implementations

impl<H> ForwardPartialPathStitcher<H>

pub fn from_partial_paths<I>( _graph: &StackGraph, _partials: &mut PartialPaths, initial_partial_paths: I, ) -> Self

where I: IntoIterator<Item = PartialPath>,

Creates a new forward partial path stitcher that is “seeded” with a set of initial partial paths. If the sticher is used to find complete paths, it is the responsibility of the caller to ensure precondition variables are eliminated by calling PartialPath::eliminate_precondition_stack_variables.

pub fn set_similar_path_detection(&mut self, detect_similar_paths: bool)

Sets whether similar path detection should be enabled during path stitching. Paths are similar if start and end node, and pre- and postconditions are the same. The presence of similar paths can lead to exponential blow up during path stitching. Similar path detection is enabled by default.

pub fn set_check_only_join_nodes(&mut self, check_only_join_nodes: bool)

Sets whether all nodes are checked for cycles and (if enabled) similar paths, or only nodes with multiple incoming candidates. Checking only join nodes is unsafe unless the database of candidates is stable between all stitching phases. If paths are added to the database from one phase to another, for example if paths are dynamically loaded from storage, setting this to true is incorrect and might lead to non-termination!

pub fn set_max_work_per_phase(&mut self, max_work_per_phase: usize)

Sets the maximum amount of work that can be performed during each phase of the algorithm. By bounding our work this way, you can ensure that it’s not possible for our CPU-bound algorithm to starve any worker threads or processes that you might be using. If you don’t call this method, then we allow ourselves to process all of the extensions of all of the paths found in the previous phase, with no additional bound.

pub fn set_collect_stats(&mut self, collect_stats: bool)

Sets whether to collect statistics during stitching.

pub fn into_stats(self) -> Stats

impl<H: Clone> ForwardPartialPathStitcher<H>

pub fn previous_phase_partial_paths( &self, ) -> impl Iterator<Item = &PartialPath> + '_

Returns an iterator of all of the (possibly incomplete) partial paths that were encountered during the most recent phase of the algorithm.

pub fn previous_phase_partial_paths_slice(&mut self) -> &[PartialPath]

Returns a slice of all of the (possibly incomplete) partial paths that were encountered during the most recent phase of the algorithm.

pub fn previous_phase_partial_paths_slice_mut(&mut self) -> &mut [PartialPath]

Returns a mutable slice of all of the (possibly incomplete) partial paths that were encountered during the most recent phase of the algorithm.

pub fn is_complete(&self) -> bool

Returns whether the algorithm has completed.

pub fn process_next_phase<A, Db, C, E, Err>( &mut self, candidates: &mut C, extend_while: E, )

where A: Appendable, Db: ToAppendable<H, A>, C: ForwardCandidates<H, A, Db, Err>, E: Fn(&StackGraph, &mut PartialPaths, &PartialPath) -> bool,

Runs the next phase of the algorithm. We will have built up a set of incomplete partial paths during the previous phase. Before calling this function, you must ensure that db contains all of the possible appendables that we might want to extend any of those candidate partial paths with.

After this method returns, you can use previous_phase_partial_paths to retrieve a list of the (possibly incomplete) partial paths that were encountered during this phase.

The extend_while closure is used to control whether the extended paths are further extended or not. It is not called on the initial paths.

impl ForwardPartialPathStitcher<Edge>

pub fn find_minimal_partial_path_set_in_file<F>( graph: &StackGraph, partials: &mut PartialPaths, file: Handle<File>, config: StitcherConfig, cancellation_flag: &dyn CancellationFlag, visit: F, ) -> Result<Stats, CancellationError>

where F: FnMut(&StackGraph, &mut PartialPaths, &PartialPath),

Finds a minimal set of partial paths in a file, calling the visit closure for each one.

This function ensures that the set of visited partial paths (a) is minimal, no path can be constructed by stitching other paths in the set, and (b) covers all complete paths, from references to definitions, when used for path stitching

This function will not return until all reachable partial paths have been processed, so your database must already contain all partial paths that might be needed. If you have a very large stack graph stored in some other storage system, and want more control over lazily loading only the necessary pieces, then you should code up your own loop that calls process_next_phase manually.

Caveat: Edges between nodes of different files are not used. Hence the returned set of partial paths will not cover paths going through those edges.

impl<H: Clone> ForwardPartialPathStitcher<H>

pub fn find_all_complete_partial_paths<I, F, A, Db, C, Err>( candidates: &mut C, starting_nodes: I, config: StitcherConfig, cancellation_flag: &dyn CancellationFlag, visit: F, ) -> Result<Stats, Err>

where I: IntoIterator<Item = Handle<Node>>, A: Appendable, Db: ToAppendable<H, A>, C: ForwardCandidates<H, A, Db, Err>, F: FnMut(&StackGraph, &mut PartialPaths, &PartialPath), Err: From<CancellationError>,

Finds all complete partial paths that are reachable from a set of starting nodes, building them up by stitching together partial paths from this database, and calling the visit closure on each one.

This function will not return until all reachable partial paths have been processed, so your database must already contain all partial paths that might be needed. If you have a very large stack graph stored in some other storage system, and want more control over lazily loading only the necessary pieces, then you should code up your own loop that calls process_next_phase manually.