Symbol Search and AST

Phase 11 · Document 03 · AI Coding Platforms Prev: 02 — Codebase Indexing · Up: Phase 11 Index

Table of Contents

1. Why This Matters
2. Core Concept
3. Mental Model
4. Hitchhiker's Guide
5. Warmup Readings
6. Deep Readings and External References
7. Key Terms
8. Important Facts
9. Observations from Real Systems
10. Common Misconceptions
11. Engineering Decision Framework
12. Hands-On Lab
13. Verification Questions
14. Takeaways
15. Artifact Checklist

1. Why This Matters

This is the structural half of code retrieval — and the reason a coding platform can answer questions embeddings can't: "where is parse_header defined?", "what calls this function?", "what does this class inherit?", "what breaks if I change this signature?" Code has exact, graph-structured meaning (symbols, definitions, references, call/import graphs) that semantic embeddings approximate poorly (02). Symbol search + AST analysis provide precise, exact, navigable context — the difference between an assistant that suggests code consistent with your actual APIs and types versus one that plausibly hallucinates them. It's the structural complement that makes code retrieval hybrid (Phase 9.05), and the best part: you often get it for free from the language server (01).

2. Core Concept

Plain-English primer: code is a graph, not just text

Source code parses into an Abstract Syntax Tree (AST) — a structured tree of its constructs (functions, classes, calls, imports). From the AST (across files) you derive structural artifacts that capture code's exact relationships:

• Symbol table — every defined name (function/class/variable) and where it's defined and referenced. Answers "go to definition", "find all references".
• Call graph — who calls whom. Answers "what calls this function?" / "what does this function call?".
• Import/dependency graph — which files/modules import which. Answers "what depends on this module?".
• Type information — what type something is, what a class inherits/implements (from a type checker / language server).

These are exact and complete (not approximate): the symbol table knows every reference. That's categorically different from embeddings, which guess by similarity.

Why structure beats embeddings for code questions

So they're complementary: embeddings for semantic/fuzzy ("find code that does X"), symbol/AST for exact/structural ("find this symbol / its callers / its type"). Code retrieval fuses both — this is the concrete reason code RAG is hybrid (02, Phase 9.05).

How you build it: tree-sitter and the LSP

Two practical sources:

• tree-sitter — a fast, incremental, multi-language parser that produces an AST you can query (it's what powers editor syntax highlighting and code-aware chunking, 02). Use it to extract functions/classes/symbols and chunk code structurally. Incremental = re-parses only changed regions (fast on every keystroke).
• The Language Server (LSP) — the language's own analyzer already computes definitions, references, symbols, types, diagnostics. As an extension you can consume these (executeDocumentSymbolProvider, definition/reference providers) instead of reimplementing a type checker (01). Don't rebuild what the LSP gives you.

# tree-sitter: extract symbols/structure (chunking + symbol table)
import tree_sitter_languages as tsl
parser = tsl.get_parser("python")
tree = parser.parse(source_bytes)
# walk the tree → function_definition / class_definition nodes → name, span → symbol table + AST chunks [02]

Using structure for retrieval and edits

• Retrieval: resolve symbols in the query/cursor context to their definitions and pull those (exact); expand to callers/callees for "how is this used?" context; combine with embeddings for fuzzy needs (02).
• Better chunking: AST gives clean function/class boundaries (no shredded code, Phase 9.02).
• Edit safety / impact analysis: before changing a signature, the reference graph tells you (and the agent) every call site that must change — turning a risky edit into a complete one (04, Phase 10.06).
• Grounding: symbol info lets you cite exact file:line (Phase 9.08) and verify the model isn't inventing APIs (a real symbol exists).

Agentic alternative: grep/LSP-on-demand

Agents often get structure on demand rather than from a maintained graph: grep for a symbol, or call LSP "find references" as a tool (Phase 10.06). For exact symbols, grep/LSP is precise and simple — which is why many agent-first tools lean on it instead of (or alongside) a built symbol index. Maintained graph = fast/global; agentic = precise/on-demand; combine.

3. Mental Model

   code parses to an AST (tree of constructs) → derive STRUCTURE: symbol table · CALL graph · import graph · types
        these are EXACT/complete (not approximate) — the opposite of embeddings

   SEMANTIC (embeddings [02]) vs STRUCTURAL (symbol/AST):
     "code that does X" → embeddings ✅      "where is parse_header / who calls it / its type" → symbol/AST ✅
   → code retrieval FUSES both (hybrid [9.05]); structure also = clean chunk boundaries [9.02] + impact analysis for edits [04]

   BUILD IT: tree-sitter (fast incremental parser → AST/symbols)  +  consume the LSP (defs/refs/symbols/types/diagnostics — FREE [01])
   AGENTIC alt: grep / LSP "find references" as a TOOL, on demand [10.06]  — combine maintained graph + on-demand

Mnemonic: code is a graph (symbols, calls, imports, types) — exact structure that embeddings can't give. Use tree-sitter + the LSP to get it (free), fuse it with embeddings (hybrid retrieval), and use the reference graph for safe, complete edits.

4. Hitchhiker's Guide

What to look for first: can the platform answer exact-symbol questions ("where defined / who calls")? If retrieval is embeddings-only, it can't — add symbol/AST (often via the LSP, which you get for free).

What to ignore at first: building a custom type checker or whole-program analyzer. Consume the LSP and use tree-sitter for parsing; only go deeper if you must.

What misleads beginners:

• Embeddings-only code retrieval. Misses exact symbols/callers/types — fuse with structural search (02, Phase 9.05).
• Reimplementing the language server. The LSP already computes defs/refs/symbols/types — consume it (01).
• Editing a signature without impact analysis. The reference graph lists every call site to update; skipping it yields incomplete, breaking edits (04).
• Fixed-size chunking. AST boundaries (function/class) make far better chunks (Phase 9.02).
• Ignoring the agentic option. For exact symbols, grep/LSP-as-a-tool is precise and simple (Phase 10.06).

How experts reason: they treat code retrieval as hybrid (embeddings for fuzzy + symbol/AST for exact), get structure from tree-sitter + the LSP (not a homegrown analyzer), use the reference/call graph for AST-clean chunking and edit impact analysis, and blend a maintained graph with agentic grep/LSP-on-demand. They use symbols to ground (verify real APIs, cite file:line).

What matters in production: exact-symbol retrieval recall, structural freshness (incremental parsing keeps up with edits), impact-analysis completeness for edits, and leveraging the LSP rather than rebuilding it.

How to debug/verify: "who calls X?" or "where is X?" failing → you lack structural retrieval; add symbol search / LSP references. Signature edits breaking call sites → no reference-graph impact analysis. Shredded chunks → not AST-chunking.

Questions to ask: does retrieval include symbol/AST (not just embeddings)? is structure from the LSP/tree-sitter (vs reinvented)? is there reference-based impact analysis for edits? incremental parsing? grep/LSP-as-a-tool for agents?

What silently gets expensive/unreliable: embeddings-only retrieval (missed symbols → hallucinated APIs), reinventing the type checker (wasted effort, bugs), incomplete signature edits (broken call sites), and stale structure.

5. Warmup Readings

6. Deep Readings and External References

7. Key Terms

8. Important Facts

• Code is a graph (symbols, call/import graphs, types) — exact, complete structure that embeddings only approximate (02).
• Structural questions ("where defined / who calls / what type / what breaks") need symbol/AST search; semantic questions ("code that does X") need embeddings — code retrieval fuses both (hybrid, Phase 9.05).
• Get structure from tree-sitter (incremental AST parsing) + the LSP (defs/refs/symbols/types/diagnostics) — don't reimplement the language server (01).
• AST gives clean chunk boundaries (function/class) for indexing (Phase 9.02).
• The reference/call graph powers edit impact analysis — every call site to update when a signature changes (04, Phase 10.06).
• Symbols enable grounding — verify a referenced API actually exists and cite file:line (Phase 9.08).
• Agents can get structure on demand via grep / LSP "find references" as a tool (Phase 10.06).
• Combine maintained graph (fast/global) + agentic grep/LSP (precise/on-demand).

9. Observations from Real Systems

• Sourcegraph is the canonical structural+semantic code search — symbol/graph + embeddings at scale.
• Cursor/Copilot consume LSP + tree-sitter for symbols and AST-aware chunking rather than rebuilding analyzers (01, 02).
• Agent-first tools (Claude Code) lean on grep + LSP-as-tools for exact symbols/references on demand (Phase 10.06).
• The classic embeddings-only failure — "find where this function is used" returning semantically-similar but wrong code — is fixed by symbol/reference search.
• Refactoring agents rely on the reference graph to update all call sites — incomplete edits trace to missing impact analysis (04).

10. Common Misconceptions

11. Engineering Decision Framework

ADD STRUCTURAL RETRIEVAL (the exact half):
 1. PARSE with tree-sitter (incremental AST) → AST-aware chunks [02] + a symbol table (defs + references).
 2. CONSUME the LSP for defs/refs/symbols/types/diagnostics — DON'T reimplement [01].
 3. FUSE with embeddings (hybrid [9.05]): symbol/keyword for EXACT ("where/who-calls/type"),
    embeddings for FUZZY ("code that does X") → rerank/pack [9.06/9.07].
 4. EDITS: use the reference/call graph for IMPACT ANALYSIS (all call sites) before changing signatures [04/10.06].
 5. GROUND: verify referenced symbols exist; cite file:line [9.08].
 6. AGENTS: expose grep + LSP "find references/definition" as TOOLS; combine with the maintained graph [10.06].

12. Hands-On Lab

Goal

Build a symbol table + call graph from ASTs and show structural retrieval answers exact-symbol questions that embeddings miss — completing the hybrid retriever from 02.

Prerequisites

• A Python repo; pip install tree_sitter_languages (or use stdlib ast); the embedding index from 02; exact-symbol queries ("where is X defined?", "what calls X?").

Steps

1. Parse + symbol table: walk each file's AST; record every function/class definition (name → file:line) and every call (caller → callee). Build a symbols map and a simple call graph.
2. Exact lookups: implement "where is X defined?" (symbol table) and "what calls X?" (call graph); confirm they return exact results.
3. Embeddings contrast: run the same exact-symbol queries against the embeddings-only retriever from 02; show it misses/garbles them.
4. Fuse (hybrid): combine symbol hits + semantic hits (RRF, Phase 9.05); show hybrid handles both exact and fuzzy queries.
5. Impact analysis: for a target function, list all references (call sites) — the set an edit to its signature must update (04).
6. (LSP option): if in an extension, call executeDocumentSymbolProvider / references to get the same data for free (01).

Expected output

A symbol table + call graph answering exact-symbol/usage questions, a demonstration that embeddings-only fails on them, a hybrid retriever that handles both, and an impact-analysis (all call sites) for a function.

Debugging tips

• Missed references → parser didn't capture all call forms (methods, aliased imports); broaden the AST walk or use the LSP.
• Hybrid no better → ensure exact symbol hits are actually fused (not overwritten by semantic).

Extension task

Add an import graph ("what depends on this module?") and use it to scope retrieval; cite file:line for grounding (Phase 9.08).

Production extension

Consume the LSP in a real extension (01) for defs/refs/types; expose find_references as an agent tool (Phase 10.06); keep parsing incremental (02).

What to measure

Exact-symbol retrieval recall (structural vs embeddings vs hybrid); impact-analysis completeness (all call sites found); parse/update latency.

Deliverables

• A symbol table + call graph with exact "where/who-calls" lookups.
• An embeddings-only vs hybrid comparison on exact-symbol queries.
• An impact-analysis (call sites) for a target function.

13. Verification Questions

Basic

1. What structural artifacts come from an AST, and what does each answer?
2. Why can't embeddings answer "where is X defined / who calls X"?
3. Where do you get symbol/structure data without building a type checker?

Applied 4. Which queries go to embeddings vs symbol/AST, and why fuse them? 5. How does the reference graph make a signature change safe/complete?

Debugging 6. "What calls this function?" returns irrelevant code. What's missing? 7. A refactor edit broke call sites it didn't update. What analysis was skipped?

System design 8. Design hybrid code retrieval: tree-sitter + LSP structure fused with embeddings, for retrieval and edit impact analysis.

Startup / product 9. Why is structural (symbol/graph) intelligence a differentiator even when competitors share the base LLM?

14. Takeaways

1. Code is a graph — symbols, call/import graphs, types — exact structure embeddings can't provide.
2. Structural questions need symbol/AST search; semantic questions need embeddings — code retrieval fuses both (hybrid, Phase 9.05).
3. Get structure from tree-sitter + the LSP — don't reimplement the language server (01).
4. AST gives clean chunks; the reference graph gives edit impact analysis (Phase 9.02/04).
5. Combine a maintained graph with agentic grep/LSP-on-demand; symbols also enable grounding (real APIs, file:line cites).

15. Artifact Checklist

• A symbol table + call graph (exact "where/who-calls" lookups).
• An embeddings-only vs hybrid comparison on exact-symbol queries.
• An impact-analysis (all call sites) for a function.
• (Optional) an import graph + file:line grounding.
• A note on consuming the LSP vs reimplementing structure.

Up: Phase 11 Index · Next: 04 — Inline Edit and Apply-Patch