Module stack_graphs::partial

source ·
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§

Enums§