Code Navigation at GitHub Scale

Precise code navigation is now generally available for all public and private Python repositories on GitHub.com. The feature is powered by stack graphs, a new open-source framework for defining the name binding rules of a programming language through a declarative, domain-specific language (DSL). With stack graphs, GitHub can generate code navigation data for a repository without any configuration by the repository owner, and without hooking into a build process or CI job.

The Mechanics of Code Navigation

Code navigation encompasses features like "jump to definition" and "find all references." These fundamentally rely on how names work in code: languages let us define things — functions, classes, modules, variables — and reference them elsewhere. Collecting the full inventory of definitions and references in a project, and mapping every reference to its definition, is the core goal.

Within a single file, that mapping can be straightforward. But it gets harder quickly:

  • Multiple definitions with the same name may exist, and shadowing rules differ by language. In Python, a later broil definition shadows an earlier one; in Rust, top-level definitions cannot shadow each other.
  • Real code spans multiple files, packages, and repositories, with language-specific import mechanisms linking a reference in one file to a definition in another.
  • When any intermediate file changes — say, a dependency adds logging to a function you call — references elsewhere may resolve to entirely different definitions. Reanalyzing every file in every dependent repository on each change creates work that grows quadratically with the number of changed files.

At GitHub's scale, two more constraints apply. First, processing must be incremental: most commits touch a small number of files, and results for unchanged files must be reused. Second, supporting every language hosted on GitHub means the name binding rules for each must be describable with minimal effort.

Key challenges, summarized:

  • Different languages have different name binding rules.
  • Some of those rules are quite complex.
  • Results may depend on intermediate files.
  • Manual per-repository configuration is not viable.
  • Incremental processing is essential for scale.

Stack Graphs: Extracting Facts in Isolation

Stack graphs are a new framework built on the concept of scope graphs from TU Delft's research group. The critical design decision: at index time (when pushes arrive), each file is analyzed completely in isolation. The goal is to extract "facts" about each file — its definitions, references, and every possible resolution for each reference.

Consider a reference to broil in kitchen.py that actually resolves to a definition in stove.py in another package. To stay incremental, the analysis treats each file separately.

From stove.py alone, we can see it defines broil. The file name tells us this lives in a module called stove, producing a fully qualified name of stove.broil. That fact becomes part of a graph with definition nodes (each definition gets a red, double-bordered node) connected by edges that encode scoping and shadowing rules for the language.

For kitchen.py, the broil reference becomes a blue, single-bordered reference node. The import statement also appears in the graph as a gadget of nodes. At index time, we don't yet know what that import resolves to — it might resolve to stove.broil defined elsewhere, but whether that definition exists isn't determined yet.

Merging at Query Time

At query time — when you're viewing a specific commit — the graphs for all files in that commit are merged into a single graph. Within it, every valid name binding corresponds to a path from a reference node to a definition node.

Not every graph path, though, represents a valid binding. To filter out spurious results, the path-finding search maintains a symbol stack. Each blue node pushes a symbol; each red node pops one. You cannot move into a pop node if its symbol doesn't match the top of the stack.

Example: after tracing from a broil reference, the stack holds ⟨broil⟩ when reaching definition nodes for saute, broil, and bake. Only the path ending at broil has a matching pop.

Different binding semantics are expressed through different graph structures and edge annotations. For instance:

  • To handle Python shadowing, edges can be annotated with precedence values — paths with higher precedence win.
  • For Rust's conflict rule on top-level definitions, a shared node connects conflicting definitions; precedences select between showing all conflicting definitions or just the first.

With a stack graph for the merged commit, "jump to definition" works like this:

  1. The user clicks a reference.
  2. The stack graphs for each file in the commit load and merge.
  3. A path-finding search starts from the clicked reference node, respecting symbol stacks and precedences to avoid invalid paths.
  4. Any valid paths found correspond to the reference's definitions, displayed in a hover card.

Building stack graphs from source

Knowing how to query stack graphs only solves half the problem. GitHub still needs to create those graphs from the code users push. That's where Tree-sitter comes in: it's an open-source parsing framework with parsers already available for a wide range of languages, and it's already used in many places across GitHub.

Tree-sitter's parsers can efficiently produce a concrete syntax tree (CST) for uploaded code. For the stove.py example, the Python parser generates a CST like this:

$ tree-sitter parse stove.py
(module [0, 0] - [10, 0]
  (function_definition [0, 0] - [1, 8]
    name: (identifier [0, 4] - [0, 8])
    parameters: (parameters [0, 8] - [0, 10])
    body: (block [1, 4] - [1, 8]
      (pass_statement [1, 4] - [1, 8])))
  (function_definition [3, 0] - [4, 8]
    name: (identifier [3, 4] - [3, 9])
    parameters: (parameters [3, 9] - [3, 11])
    body: (block [4, 4] - [4, 8]
      (pass_statement [4, 4] - [4, 8])))
  (function_definition [6, 0] - [7, 8]
    name: (identifier [6, 4] - [6, 9])
    parameters: (parameters [6, 9] - [6, 11])
    body: (block [7, 4] - [7, 8]
      (pass_statement [7, 4] - [7, 8]))))

Tree-sitter also has its own query language for identifying patterns in the CST. The query below matches all three method definitions in the example: the @function label captures the full definition, and @name captures just the method name.

(function_definition
  name: (identifier) @name) @function

To bridge the gap between CSTs and stack graphs, we've added a graph construction language to Tree-sitter. It lets you build arbitrary graph structures — stack graphs included — from parsed CSTs, and can attach to graph content already created elsewhere. Definitions are written in stanzas, each pairing a Tree-sitter query with the graph gadget to produce for every match. This snippet, for instance, builds the stack graph definition node for a Python method definition:

(function_definition
  name: (identifier) @name) @function
{
    node @function.def
    attr (@function.def) kind = "definition"
    attr (@function.def) symbol = @name
    edge @function.containing_scope -> @function.def
}

Because the graph construction rules are the only language-specific part, this pipeline can process each file incrementally, purely from its source text, without ever invoking language-specific tools or build systems.

Open questions and next steps

What's described here is just the beginning. A few loose ends worth thinking about:

  • Full pathfinding on every "jump to definition" query sounds expensive. Can more of the work be precomputed at index time and still remain incremental?
  • The examples shown are deliberately small. Real code gets complicated. For instance, Python's dataflow rules matter when the value passed to passthrough determines what one resolves to on the final line of this file:
def passthrough(x):
  return x

class A:
  one = 1

passthrough(A).one
  • Java can require tracing inheritance and generic type parameters to learn that a call to length should point at String.length from the standard library, as in:
import java.util.HashMap;

class MyMap extends HashMap<String, String> {
  int firstLength() {
      return this.entrySet().iterator().next().getKey().length();
  }
}
  • Why not use the Language Server Protocol (LSP) or its indexing format, LSIF, instead?

For a deeper treatment, see the Strange Loop talk on this work, or explore the stack-graphs crate, our open-source Rust implementation of stack graphs.