M03 · Parsing Code into Graphs with tree-sitter

Learning objectives Intermediate

In M01 you built a graph by hand and queried it. In M02 you watched text-similarity retrieval fail on questions about structure. This module answers the obvious next question: where do real code graphs come from? The answer is not an LLM reading your files. It is a parser — and understanding that parser is what separates people who trust their graph from people who should not.

What an AST is — and why extractors start there

Here is why this matters for knowledge graphs specifically. In M01 you learned that a code graph is nodes (functions, classes, modules) plus typed edges (calls, imports, inherits). Every one of those node and edge types corresponds exactly to an AST node type. A function_definition node becomes a graph node. A call node inside it becomes an outgoing edge. An import_statement becomes an imports edge. The graph is not "derived" from the AST in some fuzzy way — it is a straightforward relabeling of things the parser already found.

Contrast that with the two alternatives you already know. grep "verify_token" finds the string verify_token — in calls, in comments, in docstrings, in a variable named verify_token_backup, with no idea which is which. An embedding search (M02) finds text that talks like verify_token. Only the AST knows the difference between defining a function, calling it, and mentioning it in a comment — because those are three different node types in the tree.

Meet tree-sitter: the parser every graph tool chose

tree-sitter is an open-source parsing library originally developed at GitHub for the Atom editorGitHub's extensible text editor (2014–2022). tree-sitter was built to give it fast, accurate syntax highlighting; the editor is gone, the parser became an industry standard., and now serving as NeovimA modern fork of the Vim editor. Its syntax highlighting and code navigation are powered by tree-sitter grammars.'s core syntax engine. Graphify runs it across 36 language grammars. CodeGraph uses it for every language it indexes. okf-rs embeds it in a native Rust core. When independently-built tools all converge on one dependency, the dependency is doing something hard well. Three things, specifically.

1. It parses incrementally

tree-sitter was designed to re-parse a file as you type, reusing the untouched parts of the previous tree. Edit one function in a 2,000-line file and it rebuilds only the subtree that changed. For an editor this means keystroke-speed highlighting. For a knowledge graph it means something better: watch mode is cheap. When CodeGraph's file watcher (M05) sees you save one file, re-indexing is proportional to the edit, not the codebase. This property is what makes "the graph stays current automatically" architecturally plausible at all.

2. It is fault-tolerant

This is the property that matters most, and the one traditional compiler frontends lack. A compiler parser meets one syntax error and gives up — that's fine for a compiler, whose job is to refuse bad programs. tree-sitter instead produces a partial AST: the broken region becomes an ERROR node island, and everything around it parses normally.

Why does a graph tool care? Because real development never happens in a permanently compilable state. At any moment in a working repository, someone's branch has a half-written function, a missing bracket, a merge-conflict marker. A parser that refused those files would leave holes in the graph exactly where the most active development is happening — the code your agent is most likely to be asked about. Fault tolerance means one broken function costs you one ERROR node, not a whole file's worth of nodes and edges.

3. It is fast

tree-sitter grammars compile to C, and parsing runs at millions of lines per minute. That matters because initial indexing is the one unavoidable full-corpus pass: CodeGraph's codegraph init -i on a 100,000-file repository takes about ten minutes — bounded by parsing speed and disk I/O — and that's a one-time cost precisely because everything after it is incremental.

Extraction queries: from tree to graph

A parse tree is not yet a graph. The second half of every extractor is a set of extraction queries — language-specific patterns that walk the tree and pull out two kinds of things:

• Symbols (graph nodes): functions, classes, methods, interfaces — anything with a name and a location worth pointing at.
• Edges (relationships): calls, imports, inheritance, interface implementations.

"Language-specific" is doing real work in that sentence. A Python function is a function_definition node; in Go it's a function_declaration; a Ruby method call can omit parentheses entirely. Every language needs its own grammar and its own extraction queries — which is why tools advertise language support as a headline number (Graphify: 36 grammars; okf-rs: 11 languages; CodeGraph: deepest coverage in TypeScript, Python, Rust, and Go). The grammar gives you the tree; the queries decide what in the tree becomes knowledge.

Here is what one extracted record actually looks like — the concrete artifact behind all this vocabulary. This is a single edge from the lab extractor you'll run later, in the exact shape Graphify's graph.json uses:

{
  "source": "function:shared.auth.verify_token",
  "target": "function:shared.auth.decode_jwt",
  "type": "calls",
  "provenance": "EXTRACTED"
}

Four fields. The first three you know from M01. The fourth — provenance — is the subject of the resolution ladder below, and it is the most honest field in the whole file.

Determinism: the structural pass cannot hallucinate

Three consequences follow, and each one shows up as a concrete, checkable property of these tools:

First: zero API cost for the structural pass. Parsing needs no LLM calls — no API key, no tokens, no rate limits. Graphify's own logs say it plainly: Re-extracting code files in . (no LLM needed).... On a pure-code repository, building the entire graph is free. Only the optional semantic pass — docs, PDFs, images — costs tokens, and only that pass can hallucinate.

Second: zero hallucination in extracted edges. An EXTRACTED edge exists because a call node existed in a parse tree. There is no probability attached, nothing to "verify." This is the zero-hallucination structural extraction that Graphify's benchmark analysis identifies as one of its two real advantages (the other being ingest cost — M04 covers both honestly).

Third: reproducibility. okf-rs takes this furthest as an explicit guarantee: identical source produces byte-identical output — no timestamps, no unordered-map noise leaking into the result. That sounds like pedantry until you put a graph in CI: byte-identical output means a graph diff in a pull request shows exactly and only what the code change changed. A tool that shuffles its output every run makes graph diffs useless.

The resolution ladder: EXTRACTED → INFERRED → AMBIGUOUS

The parse tree tells you, with certainty, that some function named publish is called on line 27 of webhooks.py. It does not tell you which publish. Your project might define one in shared/events.py, another in a vendored SDK, and a third on a class. Connecting a call site to the right definition is name resolution, and it is where structural parsing stops being trivially exact.

Three forces push edges down the ladder, and you should be able to name all three:

Dynamic languages. In Python or JavaScript, "types are merely suggestions" — nothing in the tree says what type self.gateway is, so self.gateway.charge() could resolve to any class with a charge method. Extractors fall back to name matching, which is exactly the heuristic INFERRED describes.

Dynamic dispatch. A call through an interface, a callback passed as an argument, a handler registered in a table (subscribe("payment.settled", send_receipt) from orderflow is a perfect example) — the real call happens at runtime through a variable. Static extraction sees the registration but not the eventual invocation. This is a known blind spot: dynamic dispatch stays invisible, and no static tool escapes it.

Name collisions. Two modules both define execute. Bare-name matching now has two candidates. Down to AMBIGUOUS.

The middle rung nobody should skip: asking a language server

Between "cheap heuristic" and "give up" there is a third option: ask the program that already solves resolution for your editor. A language serverA background process implementing the Language Server Protocol (LSP) — the same thing that powers go-to-definition in VS Code. rust-analyzer (Rust) and pyright (Python) are the reference examples. performs full semantic analysis; okf-rs exposes this as okf-rs generate --lsp, which resolves project-wide ambiguous names by asking the real language server (rust-analyzer, pyright) via the LSP request textDocument/definition — verified end-to-end against real servers, with timeout handling and correct behavior on paths containing spaces or non-ASCII characters. The tradeoff is the ladder's whole shape: each rung up buys accuracy with startup time and complexity. Heuristics are instant; an LSP takes seconds to warm up and needs project configuration; and anything still unresolved gets the honest label instead of a confident wrong edge.

Walk it, step by step

One file, all the way from source text to call edges. The last step is the one that matters most: what the parser refuses to guess, and why an AMBIGUOUS edge is worth more than a confident wrong one.

Languages and visibility: where "public API" comes from

One more extraction detail matters for the narrative layers you'll build in Track 3: deciding which symbols are a module's public API. That sounds universal; it's actually one of the most language-specific judgments an extractor makes, because every language community encodes visibility differently:

okf-rs implements exactly this per-language table across its 11 languages (Rust, Python, TypeScript, JavaScript, Go, Java, C#, PHP, Kotlin, C/C++, Swift). Graphify's 36 grammars and CodeGraph's coverage (deepest in TypeScript, Python, Rust, Go; Objective-C explicitly partial) each embody the same kind of judgment. The takeaway when evaluating any tool: "supports language X" is a spectrum — grammar-level parsing is the easy part; correct visibility rules, call conventions, and module-system semantics are where support is deep or shallow. Projects on less common languages should test before adopting.

Code walkthrough: a real extractor in ~60 lines

Time to hold the whole pipeline in your hands: parse shared/auth.py from orderflow with tree-sitter, walk the tree, and emit graph nodes and provenance-tagged edges. Pick your language — the two tabs implement the same logic with the official bindings.

import tree_sitter_python
from tree_sitter import Language, Parser

parser = Parser(Language(tree_sitter_python.language()))

try:
    source = open("sample-project/shared/auth.py", "rb").read()
except OSError as exc:
    raise SystemExit(f"cannot read source: {exc}")

tree = parser.parse(source)
print(tree.root_node)   # the AST as an S-expression

def node_text(node) -> str:
    return source[node.start_byte:node.end_byte].decode("utf-8", "replace")

defs = {}                        # name -> line number
stack = [tree.root_node]
while stack:
    node = stack.pop()
    if node.type == "function_definition":
        name_node = node.child_by_field_name("name")
        if name_node is not None:
            defs[node_text(name_node)] = name_node.start_point[0] + 1
    stack.extend(node.children)

print(f"definitions: {defs}")
# definitions: {'decode_jwt': 16, 'verify_token': 40}

def call_name(call_node):
    fn = call_node.child_by_field_name("function")
    if fn is None: return None
    if fn.type == "identifier": return node_text(fn)
    if fn.type == "attribute":               # obj.method(...) -> "method"
        attr = fn.child_by_field_name("attribute")
        return node_text(attr) if attr else None
    return None

edges = []
stack = [tree.root_node]
current_fn = None
def walk(node, owner):
    if node.type == "function_definition":
        name_node = node.child_by_field_name("name")
        owner = node_text(name_node) if name_node else owner
    if node.type == "call" and owner:
        target = call_name(node)
        if target in defs:                    # resolves inside this module
            edges.append((owner, target, "EXTRACTED"))
        # unknown names are stdlib/third-party: skipped, not guessed
    for child in node.children:
        walk(child, owner)

walk(tree.root_node, None)
for src, dst, prov in edges:
    print(f"{src} -> {dst}  [{prov}]")
# verify_token -> decode_jwt  [EXTRACTED]

import Parser from "tree-sitter";
import Python from "tree-sitter-python";
import { readFileSync } from "node:fs";

const parser = new Parser();
parser.setLanguage(Python);

let source;
try {
  source = readFileSync("sample-project/shared/auth.py", "utf8");
} catch (err) {
  console.error(`cannot read source: ${err.message}`);
  process.exit(1);
}
const tree = parser.parse(source);
console.log(tree.rootNode.toString());  // S-expression AST

const defs = new Map();
const stack = [tree.rootNode];
while (stack.length) {
  const node = stack.pop();
  if (node.type === "function_definition") {
    const nameNode = node.childForFieldName("name");
    if (nameNode) defs.set(nameNode.text, nameNode.startPosition.row + 1);
  }
  stack.push(...node.children);
}
console.log("definitions:", defs);
// definitions: Map { 'decode_jwt' => 16, 'verify_token' => 40 }

function callName(callNode) {
  const fn = callNode.childForFieldName("function");
  if (!fn) return null;
  if (fn.type === "identifier") return fn.text;
  if (fn.type === "attribute")
    return fn.childForFieldName("attribute")?.text ?? null;
  return null;
}

const edges = [];
function walk(node, owner) {
  if (node.type === "function_definition")
    owner = node.childForFieldName("name")?.text ?? owner;
  if (node.type === "call" && owner) {
    const target = callName(node);
    if (target && defs.has(target))
      edges.push([owner, target, "EXTRACTED"]);
  }
  for (const child of node.children) walk(child, owner);
}
walk(tree.rootNode, null);
edges.forEach(([s, d, p]) => console.log(`${s} -> ${d}  [${p}]`));
// verify_token -> decode_jwt  [EXTRACTED]

Hands-on lab

📂 Get the files: labs/M03-tree-sitter-extraction on GitHub — or clone the whole course once: git clone https://github.com/varasrinivas/knowledge-graph-course.git

The full exercise lives in labs/M03-tree-sitter-extraction/ — do it now while the walkthrough is fresh. It runs in four steps:

1. Parse one file — shared/auth.py, print the S-expression, find the function_definition nodes. (Expected: a (module ...) expression.)
2. Prove fault tolerance — delete a closing parenthesis from a copy, re-parse, and observe the ERROR node island while every other function still parses. This is the step that should permanently change how you think about "the code doesn't compile."
3. Extract defs and calls — the walkthrough code, extended with the full grading rules: same-module unique match → EXTRACTED; unique match elsewhere → INFERRED; multiple → AMBIGUOUS (emit all); zero → external, skip.
4. Compare with the fallback — run python ../shared_tools/kg_extract.py ../sample-project (the course's stdlib-ast extractor) and diff its shared.auth edges against yours. Both must agree on verify_token → decode_jwt (EXTRACTED).

Stretch goal: time both parsers on 1,000 synthetic copies of auth.py. The gap you measure is why Graphify and CodeGraph can index tens of thousands of files in minutes.

Knowledge check

Module summary

What we built on orderflow: a working tree-sitter extractor that finds decode_jwt and verify_token, grades the edge between them EXTRACTED, and agrees with the course's stdlib fallback extractor.

Next module preview: you've built a toy extractor; M04 hands you the production one. Graphify wraps everything from this module — 36 grammars, Leiden community detection, god-node identification — behind one command, and produces three artifacts you'll learn to read critically. Bring skepticism: M04 is also where we put the famous "71.5×" benchmark next to its replications.

References

• tree-sitter documentation — tree-sitter.github.io (grammars, incremental parsing, query language)
• py-tree-sitter and tree-sitter-python packages (PyPI); tree-sitter + tree-sitter-python (npm)
• Graphify repository — 36-grammar AST extraction, EXTRACTED/INFERRED tagging
• okf-rs repository — github.com/jyjeanne/okf-rs (deterministic output, LSP-backed disambiguation, per-language visibility rules)
• Course lab: labs/M03-tree-sitter-extraction/ and fallback extractor labs/shared_tools/kg_extract.py