Code symbol indexing

Deep dive

How it works

Parts:

• Extractor — per file, emits (symbol id, range, role): tree-sitter tags.scm queries (syntactic, no build) or a compiler run (precise, needs dependencies).
• Symbol id — string like SCIP's scheme manager name version descriptors, e.g. cargo foo 1.2.0 util/parse().; local N for file-private names.
• Hash table — file path to content hash; the invalidation key.
• Occurrence store — symbol id to (file, range, definition|reference|implementation) list, plus file to symbols for cheap removal.
• Merger — combines shards (per file, package or repo) by id equality.
• Text index — trigram posting lists for substring/regex search, reaching comments, strings and config.

1. Hash each file's bytes.
2. Hash equals stored: skip. File gone: delete its occurrences.
3. Otherwise delete its old occurrences, extract, insert the new ones, store the hash.
4. Definitions: filter the list by role. References: the rest. Implementations: relationship edges on the definition (SCIP is_implementation).
5. Cross-repo: the id carries the other package's name and version; look the same id up in that repo's index.
6. Text query: take required trigrams, intersect posting lists, verify with the real regex on the few candidate files.

 file ──hash──▶ changed? ──no──▶ keep
   │                    └yes──▶ extractor ──▶ (symbol, range, role)*
   │                                              │
 occurrence store:  "cargo foo 1.2.0 util/parse()." ─▶ [a.rs:1 def, a.rs:4 ref, b.rs:3 ref]
 text index:        "par","ars","rse"              ─▶ files containing the trigram

Binding names is name resolution; ranges follow text position encoding.

Code

Toy extractor, three tables, invariants as asserts. Compiled and run; prints ok.

use std::collections::{HashMap, HashSet};

#[derive(Clone, Debug, PartialEq)]
pub struct Occ { pub file: String, pub line: u32, pub def: bool }

#[derive(Default)]
pub struct Index {
    hashes: HashMap<String, u64>,         // file -> content hash (the cache key)
    by_file: HashMap<String, Vec<String>>, // file -> symbols it contributed (for cheap removal)
    occs: HashMap<String, Vec<Occ>>,       // symbol id -> occurrences (the inverted index)
}

fn fnv1a(s: &str) -> u64 {
    s.bytes().fold(0xcbf29ce484222325, |h, b| (h ^ b as u64).wrapping_mul(0x100000001b3))
}

// Toy extractor: "fn name" defines, "name(" references; the id is all shards must agree on.
fn extract(src: &str) -> Vec<(String, u32, bool)> {
    let mut out = Vec::new();
    for (i, line) in src.lines().enumerate() {
        let ln = i as u32 + 1;
        let mut def_name = None;
        if let Some(rest) = line.trim_start().strip_prefix("fn ") {
            let n: String = rest.chars().take_while(|c| c.is_alphanumeric() || *c == '_').collect();
            if !n.is_empty() { out.push((format!("toy . {n}()."), ln, true)); def_name = Some(n); }
        }
        let b = line.as_bytes();
        let mut j = 0;
        while j < b.len() {
            if b[j].is_ascii_alphabetic() || b[j] == b'_' {
                let s = j;
                while j < b.len() && (b[j].is_ascii_alphanumeric() || b[j] == b'_') { j += 1; }
                let w = &line[s..j];
                if b.get(j) == Some(&b'(') && Some(w) != def_name.as_deref() && w != "fn" {
                    out.push((format!("toy . {w}()."), ln, false));
                }
            } else { j += 1; }
        }
    }
    out
}

impl Index {
    fn drop_file(&mut self, f: &str) {
        for sym in self.by_file.remove(f).unwrap_or_default() {
            if let Some(v) = self.occs.get_mut(&sym) {
                v.retain(|o| o.file != f);
                if v.is_empty() { self.occs.remove(&sym); } // removed symbols disappear
            }
        }
        self.hashes.remove(f);
    }

    /// Re-index only changed files, drop vanished ones; returns files re-indexed.
    pub fn update(&mut self, files: &[(&str, &str)]) -> usize {
        let now: HashSet<&str> = files.iter().map(|f| f.0).collect();
        let gone: Vec<String> = self.hashes.keys().filter(|k| !now.contains(k.as_str())).cloned().collect();
        for g in gone { self.drop_file(&g); }
        let mut n = 0;
        for (name, src) in files {
            let h = fnv1a(src);
            if self.hashes.get(*name) == Some(&h) { continue; }
            self.drop_file(name);
            let mut syms = HashSet::new();
            for (sym, line, def) in extract(src) {
                self.occs.entry(sym.clone()).or_default().push(Occ { file: name.to_string(), line, def });
                syms.insert(sym);
            }
            self.by_file.insert(name.to_string(), syms.into_iter().collect());
            self.hashes.insert(name.to_string(), h);
            n += 1;
        }
        n
    }
    fn query(&self, name: &str, def: bool) -> Vec<&Occ> {
        let mut v: Vec<&Occ> = self.occs.get(&format!("toy . {name}().")).into_iter().flatten().filter(|o| o.def == def).collect();
        v.sort_by(|a, b| (&a.file, a.line).cmp(&(&b.file, b.line)));
        v
    }
    pub fn defs(&self, n: &str) -> Vec<&Occ> { self.query(n, true) }
    pub fn refs(&self, n: &str) -> Vec<&Occ> { self.query(n, false) }
}

fn main() {
    let mut ix = Index::default();
    let a = "fn parse() {\n}\nfn run() {\n  parse();\n}";
    let b = "fn main() {\n  run();\n  parse();\n}";
    assert_eq!(ix.update(&[("a.rs", a), ("b.rs", b)]), 2);
    assert_eq!(ix.defs("parse").len(), 1);
    assert_eq!(ix.refs("parse").len(), 2); // a.rs:4 and b.rs:3
    assert_eq!(ix.update(&[("a.rs", a), ("b.rs", b)]), 0); // nothing changed: no work
    let b2 = "fn main() {\n  run();\n}"; // edit b.rs only: drops its parse() ref
    assert_eq!(ix.update(&[("a.rs", a), ("b.rs", b2)]), 1);
    assert_eq!(ix.refs("parse").iter().map(|o| o.file.as_str()).collect::<Vec<_>>(), ["a.rs"]);
    let a2 = "fn run() {\n}"; // a.rs loses parse(): symbol disappears entirely
    assert_eq!(ix.update(&[("a.rs", a2), ("b.rs", b2)]), 1);
    assert!(ix.defs("parse").is_empty() && ix.refs("parse").is_empty());
    assert_eq!(ix.update(&[("a.rs", a2)]), 0); // b.rs deleted
    assert!(ix.refs("run").is_empty() && ix.defs("run").len() == 1);
    println!("ok");
}

Complexity and constants

• Update: O(bytes changed) for hashing plus extraction. Hashing every file each run is O(repo bytes); real systems compare commit trees or mtimes first.
• Query: one hash lookup, then O(hits). Cost drivers: bytes per occurrence (store file ids and delta-encoded ranges, not path strings) and the symbol-string table.
• Precise extraction needs a compiler run per project and dominates all store operations.

Efficiency

• Cost: Extraction (type-checking) is compute-bound and the expensive step; queries are memory/latency-bound lookups. Sourced size figures: a trigram index of the Linux 3.1.3 sources, 420 MB, was 77 MB (Cox). A Zoekt shard is about 3.5x the corpus size, and positional trigrams need about 1.2x corpus size of RAM (Zoekt design doc). For a diff touching k files the work is k extractions plus k removals.
• Levers:
  • Content-hash skip — unchanged files cost one hash, not an extraction — (this page's code; SCIP design doc lists file-level incrementality as a goal) — always.
  • Index in CI, upload the result — the server never builds the project — (SCIP design doc) — when precise indexing needs dependencies.
  • Parallel per-file or per-package indexers — files are independent — (SCIP design doc, monorepo goal) — large repos.
  • Typed binary format instead of ad-hoc JSON — about 8x smaller and 3x faster to process than LSIF, a single-author report (Don Stewart on Glean, quoted in the SCIP announcement) — ingestion.
  • Trigram prefilter before regex — one query narrowed to 3 files out of 2,739 (Cox) — substring and regex search.
• Naive → standard → state of the art:
  • Re-run grep/ctags over the repo each query · O(repo) per query.
  • Per-file syntactic tags with a symbol to occurrence table, rebuilt on change · O(diff), approximate.
  • Per-file semantic indexes with stable ids, shards merged on ids, plus positional trigram shards · O(diff) updates, precise answers, millisecond lookups.

Implementation notes

• Hash content bytes, not mtimes, and put the extractor version in the key so a new extractor invalidates everything. Use BLAKE3 or SHA-2 if hashes are trusted across machines; a fast hash is fine for a local skip check.
• Symbol ids: escape the separator (SCIP doubles spaces), include package name and version for exported symbols, use per-file local ids for locals.
• Keep file to symbols so removal touches only affected lists. Sort occurrences by (file, line) at write time so shards merge by k-way merge.
• Shard by file or package, not by symbol: a query then fans out and merges. Zoekt's uint32 offsets cap content at about 1 GB per shard (design doc), so big repos split.

Pitfalls

• Syntactic matching (name() cannot see overloads, shadowing, imports or macros. Show the grade to the user ("search-based" vs "precise").
• Id drift: renaming a package or bumping its version changes every id and silently breaks cross-repo links.
• Stale snapshots: an index for commit X is wrong for a dirty working tree; use a language server there.
• Deleted files left in the store show ghost hits; always diff the file list, as in the code.
• Per-file independence rules out analyses needing other files' facts, unless the extractor embeds dependency signatures (module resolution).

Variants and alternatives

In production

• Code hosting: GitHub's precise code navigation was built on stack graphs (GitHub blog, "Introducing stack graphs"); Sourcegraph's precise navigation is built on SCIP indexers (Sourcegraph docs).
• Static analysis and security scanning: CodeQL creates a database from one extraction of the code, then runs queries against it (CodeQL docs).
• Monorepo tooling: Kythe's overview targets build systems, compilers, editors and code-review tools; its use at Google is from memory, not verified here.
• Text search: Google Code Search was built on trigrams (Cox), and Zoekt (maintained by Sourcegraph) serves code search today.
• IDEs and editors: rust-analyzer can emit a SCIP file (rust-analyzer scip, per its CLI flags and Sourcegraph docs).

Implementations

Sources

• Russ Cox, Regular Expression Matching with a Trigram Index, 2012. article · code
• Sourcegraph, SCIP Code Intelligence Protocol: design rationale · schema · announcement, 2022
• Douglas Creager, Introducing stack graphs, GitHub Blog, 2021. post
• Douglas A. Creager, Hendrik van Antwerpen, Stack graphs: Name resolution at scale, arXiv 2211.01224. paper
• Zoekt, design.md (positional trigrams, shard layout). doc
• tree-sitter, Code Navigation Systems (tags queries). docs
• Microsoft, LSIF specification 0.6.0. spec
• Kythe project. site · CodeQL, About CodeQL. docs