Module stitching

Partial paths can be “stitched together” to produce name-binding paths.

The “path stitching” algorithm defined in this module is how we take a collection of partial paths and use them to build up name-binding paths. Our conjecture is that by building paths this way, we can precompute a useful amount of work at index time (when we construct the partial paths), to reduce the amount of work that needs to be done at query time (when those partial paths are stitched together into paths).

Complicating this story is that for large codebases (especially those with many upstream and downstream dependencies), there is a very large set of partial paths available to us. We want to be able to load those in lazily, during the execution of the path-stitching algorithm.

The Database and PathStitcher types provide this functionality. Database manages a collection of partial paths that have been loaded into this process from some external data store. PathStitcher implements the path-stitching algorithm in phases. During each phase, we will process a set of (possibly incomplete) paths, looking in the Database for the set of partial paths that are compatible with those paths. It is your responsibility to make sure that the database contains all of possible extensions of the paths that we’re going to process in that phase. For the first phase, you already know which paths you’re starting the search from, and must make sure that the database starts out containing the possible extensions of those “seed” paths. For subsequent phases, you get to see which paths will be processed in the next phase as part of handling the current phase. This gives you the opporunity to load additional partial paths into the Database before allowing the next phase to proceed.

Structs

Database

Contains a “database” of partial paths.

DatabaseCandidates

ForwardPartialPathStitcher

Implements a phased forward partial path stitching algorithm.

GraphEdgeCandidates

Acts as a database of the edges in the graph.

GraphEdges

A dummy type to act as the “database” for graph edges. Its ToAppendable implementation is the identity on edges.

Stats

StitcherConfig

Configuration for partial path stitchers.

SymbolStackKey

The key type that we use to find partial paths that start from the root node and have a particular symbol stack as their precondition.

Traits

Appendable

Something that can be appended to a partial path.

ForwardCandidates

A trait to support finding candidates for partial path extension. The candidates are represented by handles H, which are mapped to appendables A using the database Db. Loading errors are reported as values of the Err type.

ToAppendable

A trait to be implemented on types such as Database that allow converting handles to appendables.