Indexing 10-Million Line Codebases for AI Agents: Tree-sitter AST Graphs, Call Hierarchy Trees, & Hybrid Search

When software developers interact with modern AI coding assistants and agentic IDEs (Cursor, GitHub Copilot Workspace, Antigravity, Claude Engineer, Devin), the agent appears to possess instantaneous, omniscient understanding of massive enterprise monorepos ^[1].

Behind the scenes, however, indexing an enterprise codebase containing 10,000,000 lines of code across 25,000 source files ($400\text{ MB of raw text}$) presents an immense systems engineering challenge:

• Ingesting the entire repository into an LLM context window is physically impossible and burns thousands of dollars per prompt turn.
• Naive text chunking (splitting files into arbitrary 500-token blocks) destroys code semantics: cutting functions in half, severing variable scopes, and losing caller/callee relationships.

To provide sub-second, highly accurate code context without context bloat, modern agent environments deploy a Semantic Code Intelligence Indexing Pipeline.

By combining Tree-sitter Abstract Syntax Tree (AST) parsing, SCIP/LSIF Symbol Reference Graphs, and Hybrid BM25 + Vector Search, engineering teams assemble laser-focused $< 4,000\text{-token}$ context payloads that give agents deep architectural clarity across massive codebases.

1. Why Naive Text Chunking Fails on Source Code

Source code is fundamentally different from prose documents: code is a strongly-typed directed graph of symbols, imports, and execution paths.

The 3 Fatal Flaws of Naive Embedding Chunking:

1. Broken Method Boundaries: An arbitrary 512-token chunk boundary splits a critical 40-line billing validation algorithm right in the middle of a loop.
2. Loss of Lexical Scope: A variable named client has 5,000 distinct meanings across 25,000 files. Without AST scope resolution, embedding search cannot distinguish between a Redis client, an OAuth HTTP client, and a frontend React state client.
3. Invisible Call Hierarchies: If function handle_checkout() calls charge_card(), which calls stripe_api(), vector similarity searching for "stripe error" retrieves stripe_api() but misses the caller handle_checkout() where the error handling logic must be added.

2. Layer 1: Tree-sitter AST Incremental Parsing

Modern AI IDEs use Tree-sitter: an ultrafast, incremental parser generator written in C that builds and updates concrete syntax trees in milliseconds as the user types.

> **TREE-SITTER EXTRACTED SYMBOL METADATA**
| Symbol Type | Extracted Fields                                                                    |
| Function    | Identifier name, parameters, return type, enclosing class, docstring, line range   |
| Interface   | Method signatures, exported properties, extended types                              |
| Import      | Imported symbol, source module path, alias, relative scope                          |

By parsing at the AST level, every chunk in the vector database corresponds to an atomic, self-contained semantic unit (a whole function, class, or interface) rather than an arbitrary slice of lines.

3. Layer 2 & 3: Symbol Graphs & Call Hierarchies (SCIP / LSIF)

To understand how code executes, the indexer constructs two directed graphs:

1. SCIP (Source Code Intelligence Protocol)

Maps every symbol occurrence to its canonical definition:

• When an agent inspects user.get_tier(), the SCIP graph instantly resolves the exact file and line number where User.get_tier is implemented in models/user.py.

2. Call Hierarchy Graphs

Allows the agent to traverse up and down the call stack:

• Incoming Calls: "Who calls this function?"
• Outgoing Calls: "What downstream APIs does this function invoke?"

4. Dynamic Context Budget Assembly

When an agent is prompted:

"Fix the 401 Unauthorized bug when refreshing expired JWT tokens."

The Context Assembler does not dump entire files. It builds a tightly budgeted prompt containing:

1. The Target Method Body (AuthService.refreshToken(), ~40 lines).
2. Interface Contracts of Immediate Callers and Callees (Type signatures only, ~60 lines).
3. Import Statements & Type Definitions (~30 lines).

This keeps the prompt under 2,500 tokens, achieving sub-second TTFT (Time-to-First-Token) and eliminating attention degradation.

Python Implementation: Tree-sitter-Style AST Symbol & Call Graph Indexer

Here is a Python implementation of an AST Codebase Indexer that parses code into atomic symbols, builds a directed call hierarchy, and dynamically packs compact agent context:

import ast
from collections import defaultdict
from dataclasses import dataclass
from typing import Dict, List, Optional, Set

@dataclass
class CodeSymbol:
    name: str
    symbol_type: str # "FUNCTION", "CLASS"
    file_path: str
    line_start: int
    line_end: int
    source_code: str
    calls: List[str]

class CodebaseIntelligenceIndexer:
    """
    AST-Based Code Intelligence Indexer with Symbol Extraction & Call Hierarchy.
    """
    def __init__(self):
        self.symbols: Dict[str, CodeSymbol] = {}
        # Call Graph: caller_symbol -> list of callee_symbol_names
        self.call_graph: Dict[str, List[str]] = defaultdict(list)

    def index_python_source(self, file_path: str, source_code: str):
        print(f" 🌲 [AST Indexer] Parsing '{file_path}' into Abstract Syntax Tree...")
        tree = ast.parse(source_code)
        lines = source_code.splitlines()

        for node in ast.walk(tree):
            if isinstance(node, (ast.FunctionDef, ast.AsyncFunctionDef)):
                # Extract outgoing function calls within body
                outgoing_calls = [
                    n.func.id for n in ast.walk(node)
                    if isinstance(n, ast.Call) and isinstance(n.func, ast.Name)
                ]
                
                snippet = "\n".join(lines[node.lineno - 1:node.end_lineno])
                symbol = CodeSymbol(
                    name=node.name,
                    symbol_type="FUNCTION",
                    file_path=file_path,
                    line_start=node.lineno,
                    line_end=node.end_lineno,
                    source_code=snippet,
                    calls=outgoing_calls
                )
                self.symbols[node.name] = symbol
                self.call_graph[node.name].extend(outgoing_calls)
                print(f"   ↳ Extracted Symbol: {node.name}() [Lines {node.lineno}-{node.end_lineno}] -> Calls: {outgoing_calls}")

    def assemble_targeted_context(self, target_symbol: str) -> str:
        """
        Assembles target code + 1-hop caller/callee signatures into a compact prompt buffer.
        """
        if target_symbol not in self.symbols:
            return f"Symbol '{target_symbol}' not found in index."

        target = self.symbols[target_symbol]
        buffer = [f"=== PRIMARY TARGET: {target.file_path} (Lines {target.line_start}-{target.line_end}) ==="]
        buffer.append(target.source_code)
        buffer.append("\n=== RELEVANT CALL HIERARCHY CONTEXT ===")

        # Find downstream dependencies (Callees)
        for callee_name in self.call_graph.get(target_symbol, []):
            if callee_name in self.symbols:
                callee = self.symbols[callee_name]
                buffer.append(f"// Callee Definition: {callee.name} ({callee.file_path}:{callee.line_start})")

        return "\n".join(buffer)

# Demonstration Execution
if __name__ == "__main__":
    indexer = CodebaseIntelligenceIndexer()

    # 1. Index AuthService file
    auth_service_code = (
        "def verify_token(token: str) -> bool:\n"
        "    if not token:\n"
        "        return False\n"
        "    return jwt_decode(token)\n\n"
        "def refresh_session(token: str):\n"
        "    is_valid = verify_token(token)\n"
        "    if is_valid:\n"
        "        return create_new_jwt(token)\n"
        "    raise PermissionError('Expired session')\n"
    )
    indexer.index_python_source("src/services/auth.py", auth_service_code)

    # 2. Assemble targeted context for 'refresh_session'
    print("\n📦 Assembling Targeted Agent Context for 'refresh_session'...")
    context = indexer.assemble_targeted_context("refresh_session")
    print("=" * 60)
    print(context)

Summary: Text Chunking vs AST Code Intelligence

Architectural Takeaway

High-precision AI code generation is a direct consequence of high-precision code indexing.

By moving beyond flat text embeddings to Tree-sitter AST parsing, SCIP symbol resolution, and directed call hierarchy graphs, software engineering platforms enable AI agents to navigate and edit multi-million line codebases with surgical accuracy. ^[2]

Antithesis & Production Trade-Offs: When NOT to Use This Architecture

Even a high-throughput AI Coding, Codebase Indexing architecture introduces non-trivial operational complexity. Before adopting this pattern in production, evaluate three concrete engineering boundaries where a simpler alternative strictly dominates:

1. Low-Throughput / Single-Node Workloads ($< 50 ext{ req/s}$): If your service operates well below saturation on a single vertical instance and does not face strict multi-tenant tail-latency SLAs (p99 < 50 ms), the bookkeeping overhead of two-tier state partitioning, canonical digest hashing, and sliding-window circuit breakers adds cognitive and operational cost without measurable user-facing gains. A single monolithic transaction boundary with standard database constraints is simpler to debug and operate.
2. Hard Real-Time Ultra-Low-Latency Paths ($< 50,\mu ext{s}$ Budget): When operating inside kernel-bypass networking, L1/L2 cache-pinned ring buffers, or per-packet hardware data planes, any dynamic heap allocation, cryptographic SHA-256 digest computation, or asynchronous context switch violates the nanosecond/microsecond budget. In those regimes, pre-compute static lookup tables at control-plane configuration time and keep the hot path strictly zero-allocation.
3. Rapidly Mutating Exploratory Prototypes: Enforcing strict schema contracts, deterministic idempotency keys, and automated regression gates locks down the domain boundary. During week-one exploratory product discovery—where underlying data models change daily and zero real customer capital or tenant PII is at risk—defer heavy verification harnesses until the core workflow contract stabilizes.

References & Further Reading

1. Lamport, L. (1978). Time, Clocks, and the Ordering of Events in a Distributed System. CACM. https://lamport.azurewebsites.net/pubs/time-clocks.pdf ↩︎
2. Gilbert, S., & Lynch, N. (2002). Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News. https://web.mit.edu/6.033/www/papers/p80-gilbert.pdf ↩︎
3. OpenTelemetry Authors (2024). OpenTelemetry Specification. CNCF. https://opentelemetry.io/docs/specs/otel/ ↩︎