# How the AST-grep Tier Works in Code-Graph-RAG: Structural Search Architecture

> Explore the ast_grep tier in Code-Graph-RAG. Learn how it uses abstract syntax trees for structural search and replace, going beyond plain text regex for precise code pattern matching.

- Repository: [Vitali Avagyan/code-graph-rag](https://github.com/vitali87/code-graph-rag)
- Tags: architecture
- Published: 2026-09-04

---

**The AST-grep tier provides structural search-and-replace capabilities by parsing source code into abstract syntax trees using the ast-grep library, enabling pattern matching that respects language syntax rather than relying on plain text regex.**

The AST-grep tier in Code-Graph-RAG operates as an independent layer from the graph indexing system, delivering fast, ad-hoc code querying and transformation capabilities. This tier leverages the **ast-grep** library to parse supported languages into Abstract Syntax Trees (ASTs), allowing developers and AI agents to search and modify code based on structural patterns while respecting repository ignore configurations.

## Three-Stage Processing Pipeline

The implementation in [`codebase_rag/tools/ast_grep_service.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/tools/ast_grep_service.py) processes queries through three distinct logical stages, from filesystem traversal to result generation.

### Stage 1: Language Detection and File Filtering

The `AstGrepService` initiates by walking the project tree using `_iter_source_files()`, which respects the same ignore rules applied during graph ingestion, including `.gitignore` and `.cgrignore` configurations. For each candidate file, `_classify_file()` determines the programming language from the file extension using `get_language_for_extension` and filters against `cs.AST_GREP_LANGUAGES` to ensure ast-grep can parse the source.

```python

# Conceptual implementation based on AstGrepService architecture

import codebase_rag.constants as cs
from codebase_rag.tools.ast_grep_service import AstGrepService

service = AstGrepService(project_root="/path/to/repo")

# Internal iteration respects ignore patterns and language support

for file_path in service._iter_source_files():
    lang = service._classify_file(file_path)
    if lang in cs.AST_GREP_LANGUAGES:
        # File retained for AST processing

        process_file(file_path)

```

Only files that ast-grep can successfully parse proceed to the next stage, preventing runtime errors from unsupported syntax.

### Stage 2: AST Construction and Pattern Matching

For each selected file, the service reads the source code and constructs an AST root node (`SgRoot`) via the `_root()` method. The supplied structural pattern is then applied using `_find_all()`, with the public `search()` method orchestrating the operation. The tier includes defensive error handling that catches malformed patterns, converting native `RuntimeError` exceptions into user-friendly `ValueError` messages.

```python

# Pattern matching with error handling

try:
    root = service._root(source_code, language="python")
    matches = service._find_all(root, pattern="console.log($ARG)")
except ValueError as e:
    # Malformed patterns raise ValueError instead of RuntimeError

    print(f"Invalid pattern syntax: {e}")

```

### Stage 3: Result Formatting and Code Editing

Search results are collected into **`StructuralSearchMatch`** objects containing file paths, line/column positions, and matched text. The `format_matches()` function renders these in `file:line:column text` format and automatically appends a truncation notice when the result count hits the configurable limit defined by `cs.AST_GREP_MAX_RESULTS`.

For replace operations, the `structural_editor` tool processes rewrite strings containing metavariables like `$NAME` or `$$$NAME`. The `_interpolate()` method substitutes these placeholders before calling `node.replace()`, generating a unified diff returned as a **`StructuralReplaceChange`** object.

```python

# Replace operation with metavariable interpolation

rewrite_pattern = "logger.info($$$ARGS)"
change = service.replace(
    pattern="console.log($$$ARGS)",
    rewrite=rewrite_pattern,
    dry_run=True  # Returns unified diff without writing to disk

)

```

## Core Implementation Files

The AST-grep tier spans six key files within the `vitali87/code-graph-rag` repository:

- **[`codebase_rag/tools/ast_grep_service.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/tools/ast_grep_service.py)**: Core service class handling file iteration via `_iter_source_files()`, AST construction via `_root()`, pattern matching via `_find_all()`, and replacement operations.
- **[`codebase_rag/tools/structural_search.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/tools/structural_search.py)**: Agentic wrapper exposing the `structural_search` tool; formats results via `format_matches()` and records them for downstream taint-tracking using `ReadContentRecord`.
- **[`codebase_rag/tools/structural_editor.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/tools/structural_editor.py)**: Wrapper for the `structural_editor` tool that applies rewrite patterns and returns unified diffs through `StructuralReplaceChange` objects.
- **[`codebase_rag/constants.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/constants.py)**: Defines operational limits including `AST_GREP_MAX_RESULTS`, `AST_GREP_TRUNCATED`, and `AST_GREP_NOT_AVAILABLE` messages.
- **[`codebase_rag/utils/dependencies.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/utils/dependencies.py)**: Contains `has_ast_grep()` function detecting whether the optional ast-grep binary is installed on the system.
- **[`codebase_rag/types_defs.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/types_defs.py)**: Declares `StructuralSearchMatch` and `StructuralReplaceChange` dataclasses used across the tier.

## End-to-End Search Workflow

When an AI agent initiates a structural search, the execution flows through these precise steps:

1. **Tool Creation**: The agent calls `create_structural_search_tool()`, which returns a configured Tool object.
2. **Dependency Verification**: The tool invokes `has_ast_grep()` from [`codebase_rag/utils/dependencies.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/utils/dependencies.py) to verify the ast-grep binary is available; otherwise it returns the `cs.AST_GREP_NOT_AVAILABLE` message.
3. **Search Execution**: The request dispatches to `AstGrepService.search()`, which walks the filesystem, builds ASTs via `_root()`, and runs patterns through `_find_all()`.
4. **Limit Enforcement**: The service stops early if result lists reach `cs.AST_GREP_MAX_RESULTS` to prevent overwhelming output.
5. **Result Recording**: Matches are formatted and, if a `ReadContentRecord` is supplied, recorded for taint-tracking analysis downstream.

## Replace Operations and Metavariable Handling

Unlike simple text substitution, the AST-grep tier operates on AST nodes. When processing replacements:

- **Single-node metavariables** (`$NAME`) match individual AST nodes.
- **Multi-node metavariables** (`$$$NAME`) match sequences of nodes.
- The `_interpolate()` method processes these placeholders in the rewrite string before `node.replace()` applies the transformation.
- Results include unified diffs showing exact changes, with dry-run support to preview modifications before applying them.

## Summary

- The **AST-grep tier** provides structural code search independent of Code-Graph-RAG's graph indexing layer, enabling fast ad-hoc queries.
- **Three-stage pipeline**: Language filtering via `_classify_file()` → AST pattern matching via `_find_all()` → Result formatting or editing via `format_matches()` and `replace()`.
- **Key implementation** resides in [`codebase_rag/tools/ast_grep_service.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/tools/ast_grep_service.py) with agent wrappers in [`structural_search.py`](https://github.com/vitali87/code-graph-rag/blob/main/structural_search.py) and [`structural_editor.py`](https://github.com/vitali87/code-graph-rag/blob/main/structural_editor.py).
- **Metavariables** (`$NAME`, `$$$NAME`) enable sophisticated capture and replacement of code structures through `_interpolate()`.
- **Safety limits** like `AST_GREP_MAX_RESULTS` prevent resource exhaustion during large-scale searches.

## Frequently Asked Questions

### What is the difference between the AST-grep tier and the graph indexing layer?

The AST-grep tier operates independently from the graph indexing layer to provide fast, on-demand structural searching without requiring pre-built indices. While the graph layer persists relationships between entities for complex historical queries, the AST-grep tier parses files dynamically using the ast-grep library, making it ideal for immediate code transformations that do not require persistent relationship data.

### How does the tier handle unsupported programming languages?

The `AstGrepService._classify_file()` method checks file extensions against `cs.AST_GREP_LANGUAGES` using `get_language_for_extension`, silently filtering out unsupported languages during the initial file walk in `_iter_source_files()`. Only files that ast-grep can successfully parse proceed to the AST construction stage, ensuring the system never attempts pattern matching against incompatible syntax trees.

### What happens when search results exceed the configured limit?

When match counts reach `cs.AST_GREP_MAX_RESULTS`, the `format_matches()` function defined in [`structural_search.py`](https://github.com/vitali87/code-graph-rag/blob/main/structural_search.py) stops collecting new results and appends a truncation notice defined by `cs.AST_GREP_TRUNCATED` to the output. This prevents the agent from being overwhelmed by excessive matches while still delivering actionable initial results.

### Can the AST-grep tier modify source files, or is it read-only?

The tier supports both read-only searches and destructive edits. The `structural_editor` tool in [`codebase_rag/tools/structural_editor.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/tools/structural_editor.py) applies rewrite patterns through `AstGrepService.replace()`, which uses `node.replace()` to generate unified diffs returned as `StructuralReplaceChange` objects. In production deployments, this typically runs in dry-run mode to preview changes, though it can write modifications when explicitly configured to do so.