Expand description
Partial paths are “snippets” of paths that we can precalculate for each file that we analyze.
Stack graphs are incremental, since we can produce a subgraph for each file without having to look at the contents of any other file in the repo, or in any upstream or downstream dependencies.
This is great, because it means that when we receive a new commit for a repository, we only have to examine, and generate new stack subgraphs for, the files that are changed as part of that commit.
Having done that, one possible way to find name binding paths would be to load in all of the subgraphs for the files that belong to the current commit, union them together into the combined graph for that commit, and run the path-finding algorithm on that combined graph. However, we think that this will require too much computation at query time.
Instead, we want to precompute parts of the path-finding algorithm, by calculating partial paths for each file. Because stack graphs have limited places where a path can cross from one file into another, we can calculate all of the possible partial paths that reach those “import/export” points.
At query time, we can then load in the partial paths for each file, instead of the files’ full stack graph structure. We can efficiently concatenate partial paths together, producing the original “full” path that represents a name binding.
Structs§
- Partial
Path - A portion of a name-binding path.
- Partial
Path Edge - Partial
Path Edge List - The edges in a path keep track of precedence information so that we can correctly handle shadowed definitions.
- Partial
Paths - Manages the state of a collection of partial paths built up as part of the partial-path-finding algorithm or path-stitching algorithm.
- Partial
Scope Stack - A pattern that might match against a scope stack. Consists of a (possibly empty) list of exported scopes, along with an optional scope stack variable.
- Partial
Scope Stack Bindings - Partial
Scoped Symbol - A symbol with an unknown, but possibly empty, list of exported scopes attached to it.
- Partial
Symbol Stack - A pattern that might match against a symbol stack. Consists of a (possibly empty) list of partial scoped symbols, along with an optional symbol stack variable.
- Partial
Symbol Stack Bindings - Scope
Stack Variable - Represents an unknown list of exported scopes.
- Symbol
Stack Variable - Represents an unknown list of scoped symbols.