License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.EVCS.2023.8
URN: urn:nbn:de:0030-drops-177789
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17778/
Go to the corresponding OASIcs Volume Portal


Creager, Douglas A. ; van Antwerpen, Hendrik

Stack Graphs: Name Resolution at Scale

pdf-format:
OASIcs-EVCS-2023-8.pdf (0.7 MB)


Abstract

We present stack graphs, an extension of Visser et al.’s scope graphs framework. Stack graphs power Precise Code Navigation at GitHub, allowing users to navigate name binding references both within and across repositories. Like scope graphs, stack graphs encode the name binding information about a program in a graph structure, in which paths represent valid name bindings. Resolving a reference to its definition is then implemented with a simple path-finding search.
GitHub hosts millions of repositories, containing petabytes of total code, implemented in hundreds of different programming languages, and receiving thousands of pushes per minute. To support this scale, we ensure that the graph construction and path-finding judgments are file-incremental: for each source file, we create an isolated subgraph without any knowledge of, or visibility into, any other file in the program. This lets us eliminate the storage and compute costs of reanalyzing file versions that we have already seen. Since most commits change a small fraction of the files in a repository, this greatly amortizes the operational costs of indexing large, frequently changed repositories over time. To handle type-directed name lookups (which require "pausing" the current lookup to resolve another name), our name resolution algorithm maintains a stack of the currently paused (but still pending) lookups. Stack graphs can be constructed via a purely syntactic analysis of the program’s source code, using a new declarative graph construction language. This means that we can extract name binding information for every repository without any per-package configuration, and without having to invoke an arbitrary, untrusted, package-specific build process.

BibTeX - Entry

@InProceedings{creager_et_al:OASIcs.EVCS.2023.8,
  author =	{Creager, Douglas A. and van Antwerpen, Hendrik},
  title =	{{Stack Graphs: Name Resolution at Scale}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{8:1--8:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17778},
  URN =		{urn:nbn:de:0030-drops-177789},
  doi =		{10.4230/OASIcs.EVCS.2023.8},
  annote =	{Keywords: Scope graphs, name binding, code navigation}
}

Keywords: Scope graphs, name binding, code navigation
Collection: Eelco Visser Commemorative Symposium (EVCS 2023)
Issue Date: 2023
Date of publication: 21.03.2023
Supplementary Material: Software: https://github.com/github/stack-graphs/ archived at: https://archive.softwareheritage.org/swh:1:rel:06b63a06504d38c7a0e9ee03b1d21f6f3adc045a
Software: https://github.com/tree-sitter/tree-sitter-graph/ archived at: https://archive.softwareheritage.org/swh:1:rel:6877dac0c0f228f6450a2a2a6fdae178947e60ef


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI