Repository-Level Code Context & AST-Driven Retrieval

Scaling autonomous coding agents beyond single-file edits requires structural graph intelligence. How Tree-sitter abstract syntax tree parsing, call-graph DAG construction, and hybrid reciprocal rank fusion replace naive sliding-window chunking.

1. The Failure Modes of Naive Sliding-Window Chunking

Traditional retrieval-augmented generation (RAG) splits text into fixed character or token windows (e.g., 512 tokens with 50-token overlap). When applied to source code repositories, this strategy catastrophically degrades autonomous agent reasoning:

Scope Bifurcation: A function's docstring, parameter list, and opening guard clauses are severed into Chunk A, while the core loop and return statements land in Chunk B. The LLM loses contextual awareness of variable typing and pre-conditions.
Dangling Structural References: In object-oriented and functional systems, methods reference member variables, inherited traits, and utility functions declared hundreds of lines away or across module boundaries. Flat lexical embeddings capture textual proximity, not relational dependency.
Context Window Pollution: Ingesting raw entire files exhausts context budgets with boilerplate imports, comments, and uncalled utilities, displacing the precise interfaces required to formulate correct edits.

2. Concrete Syntax Trees (CST) vs. Abstract Syntax Trees (AST)

Robust code retrieval requires language-native parsing. Tree-sitter provides incremental, error-tolerant GLR (Generalized Left-to-right Rightmost) parsing, constructing structured parse trees even during active user editing when code is syntactically incomplete:

Parsing Paradigm	Structural Granularity	Error Tolerance	Agentic Utility
Concrete Syntax Tree (CST)	Complete concrete grammar (every semicolon, bracket, whitespace token).	Strict; fails on incomplete fragments.	Exact linting, auto-formatting, formatting preservation.
Abstract Syntax Tree (AST)	Hierarchical structural nodes (Functions, Classes, Call Expressions, Control Flow).	High with incremental parsing engines.	Symbol indexing, call-graph derivation, semantic chunk boundary detection.

By parsing source code into an AST, agents slice repositories along semantic node boundaries (e.g., individual `FunctionDef` or `ClassDef` blocks) rather than arbitrary byte offsets. Each extracted node carries its enclosing scope metadata, namespace lineage, and docstrings.

3. Call-Graph DAG Construction & Symbol PageRank

Once symbols (classes, methods, functions, interfaces) are isolated into nodes, the agent builds a directed acyclic graph (DAG) representing caller-callee and inheritance relationships:

G = (V, E), \quad V = \{s_1, s_2, \dots, s_n\}, \quad E = \{(s_i, s_j) \mid s_i \text{ invokes or imports } s_j\}

To prioritize which repository files must enter the prompt context when a bug report is received, the agent executes a personalized PageRank over the call graph:

PR(s_i) = \frac{1 - d}{|V|} + d \sum_{s_j \in \mathcal{M}(s_i)} \frac{PR(s_j)}{L(s_j)}

Where \(d \approx 0.85\) is the damping factor, \(\mathcal{M}(s_i)\) represents all nodes calling \(s_i\), and \(L(s_j)\) is the out-degree of node \(s_j\). High-centrality utilities and core interfaces naturally rank higher in retrieval priority than leaf test cases.

4. Hybrid Retrieval: Reciprocal Rank Fusion (RRF)

Code retrieval requires both exact token matching (for specific variable names, error constants, and function identifiers) and dense semantic embedding (for high-level behavioral queries). Combining BM25 with dense bi-encoders via Reciprocal Rank Fusion (RRF) delivers optimal recall:

RRF\_Score(d \in D) = \sum_{m \in M} \frac{1}{k + r_m(d)}

Where \(M = \{\text{BM25}, \text{Dense Vector}, \text{Call Graph Depth}\}\), \(r_m(d)\) is the rank of chunk \(d\) in ranking system \(m\), and \(k \approx 60\) is a smoothing constant that prevents top ranks from overwhelmingly dominating the composite score.

5. Production Python Implementation: AST Symbol & Dependency Indexer

The following standalone Python engine parses arbitrary Python source files, extracts function and class symbol definitions with precise line boundaries, and maps cross-function invocations:

import ast
import os
from typing import Dict, List, Any

class RepositorySymbolIndexer(ast.NodeVisitor):
    """
    Parses Python modules into structural AST nodes, extracting definitions,
    docstrings, parameter lists, and internal function invocation graphs.
    """
    def __init__(self, filepath: str):
        self.filepath = filepath
        self.current_class = None
        self.symbols: List[Dict[str, Any]] = []
        self.invocations: List[Dict[str, Any]] = []

    def visit_ClassDef(self, node: ast.ClassDef):
        prev_class = self.current_class
        self.current_class = node.name
        self.symbols.append({
            "type": "class",
            "name": node.name,
            "file": self.filepath,
            "lineno": node.lineno,
            "end_lineno": getattr(node, 'end_lineno', node.lineno),
            "docstring": ast.get_docstring(node) or "",
            "bases": [b.id for b in node.bases if isinstance(b, ast.Name)]
        })
        self.generic_visit(node)
        self.current_class = prev_class

    def visit_FunctionDef(self, node: ast.FunctionDef):
        qualname = f"{self.current_class}.{node.name}" if self.current_class else node.name
        args = [arg.arg for arg in node.args.args]
        self.symbols.append({
            "type": "function",
            "name": qualname,
            "file": self.filepath,
            "lineno": node.lineno,
            "end_lineno": getattr(node, 'end_lineno', node.lineno),
            "docstring": ast.get_docstring(node) or "",
            "args": args
        })
        self.generic_visit(node)

    def visit_Call(self, node: ast.Call):
        if isinstance(node.func, ast.Name):
            self.invocations.append({
                "callee": node.func.id,
                "lineno": node.lineno,
                "file": self.filepath
            })
        elif isinstance(node.func, ast.Attribute):
            self.invocations.append({
                "callee": node.func.attr,
                "lineno": node.lineno,
                "file": self.filepath
            })
        self.generic_visit(node)

def index_code_snippet(source_code: str, filename: str = "main.py") -> Dict[str, Any]:
    tree = ast.parse(source_code, filename=filename)
    indexer = RepositorySymbolIndexer(filename)
    indexer.visit(tree)
    return {
        "file": filename,
        "symbols": indexer.symbols,
        "invocations": indexer.invocations
    }

if __name__ == "__main__":
    sample_code = """
class AgentExecutor:
    def __init__(self, timeout: int = 30):
        self.timeout = timeout

    def execute_action(self, tool_name: str, payload: dict):
        \"\"\"Dispatches tool call to sandbox.\"\"\"
        sanitized = self.validate_payload(payload)
        return dispatch_subcall(tool_name, sanitized)

    def validate_payload(self, p: dict):
        return p
"""
    result = index_code_snippet(sample_code)
    print(f"Extracted {len(result['symbols'])} symbols:")
    for s in result["symbols"]:
        print(f"  [{s['type'].upper()}] {s['name']} (Lines {s['lineno']}-{s['end_lineno']})")
    print(f"Extracted {len(result['invocations'])} invocations:")
    for inv in result["invocations"]:
        print(f"  --> Calls '{inv['callee']}' at line {inv['lineno']}")

Next in Curriculum

Level 608: Test-Driven Agentic Code Synthesis & Self-Healing Loops

Explore automated test execution harnesses, stack trace differential parsing, and iterative self-repair loops that drive pass@k convergence in autonomous coding agents.

Proceed to Level 608 →