What Is the ast_fingerprint Property in Code-Graph-RAG?

The ast_fingerprint property in Code-Graph-RAG is a structural hash that uniquely identifies the syntactic skeleton of a function or method body, enabling fast clone detection, near-duplicate scoring, and graph consistency checks.

ast_fingerprint serves as the backbone of Code-Graph-RAG's ability to detect code similarity at scale. Developed in the vitali87/code-graph-rag repository, this property captures the essential shape of source code while abstracting away superficial details like variable names and literal values. This article examines how the fingerprint is computed, where it is stored, and why it matters for building reliable code intelligence pipelines.

How ast_fingerprint Works: Structural Skeleton Extraction

When Code-Graph-RAG parses a source file, it transforms each function body into a normalized skeleton before hashing. The skeletonization process follows four rules implemented in parsers/ast_fingerprint.py:

• Identifier-like leaves → replaced with a placeholder token
• Literal-like nodes → replaced with a different placeholder token
• Punctuation and comments → dropped entirely
• All other nodes → preserved as their tree-sitter type

This skeleton is then Merkle-hashed bottom-up using Blake2b. The resulting hex digest becomes the ast_fingerprint value stored in the graph, accompanied by ast_fingerprint_nodes (total node count) and ast_branch_fingerprints (per-branch digests).

Fingerprint Generation: compute_ast_fingerprint

The core computation happens in compute_ast_fingerprint, defined in codebase_rag/parsers/ast_fingerprint.py lines 41-74:

from codebase_rag.parsers.ast_fingerprint import compute_ast_fingerprint
from tree_sitter import Language, Parser

# Load the tree-sitter Python grammar (assumed already built)

PY_LANGUAGE = Language('build/my-languages.so', 'python')
parser = Parser()
parser.set_language(PY_LANGUAGE)

source = b"""
def add(a, b):
    # simple addition

    return a + b
"""
tree = parser.parse(source)
func_node = tree.root_node.named_children[0]   # the FunctionDefinition node

fp_result = compute_ast_fingerprint(func_node)

print(fp_result.fingerprint)          # → e.g. "a1b2c3d4..."

print(fp_result.node_count)           # → total nodes kept in the skeleton

print(fp_result.branch_fingerprints)  # → list of branch-level digests

The function returns an AstFingerprintResult containing three fields:

1. fingerprint – the root hash of the Merkle tree
2. node_count – number of nodes in the skeleton
3. branch_fingerprints – list of hashes for statement-level subtrees

Property Injection: fingerprint_props

The fingerprint_props helper (lines 29-38) converts the result into a dictionary using keys declared in codebase_rag/constants/graph.py:

# From codebase_rag/constants/graph.py lines 96-100

KEY_AST_FINGERPRINT = "ast_fingerprint"
KEY_AST_FINGERPRINT_NODES = "ast_fingerprint_nodes"
KEY_AST_BRANCH_FINGERPRINTS = "ast_branch_fingerprints"

These constants ensure consistent property naming across the ingestion pipeline and enable version-tracking for the fingerprint algorithm itself.

Core Use Cases for ast_fingerprint in Code-Graph-RAG

Clone Detection (Type-1 and Type-2 Clones)

Exact copies and renamed duplicates produce identical fingerprints. Code-Graph-RAG uses this property to group clones in a single Cypher query:

// Find all functions sharing the same AST fingerprint
MATCH (f:Function)
WITH f.ast_fingerprint AS fp, collect(f) AS funcs
WHERE size(funcs) > 1
RETURN fp, [func IN funcs | func.name] AS duplicate_names;

By filtering on ast_fingerprint IS NOT NULL, queries retrieve only functions that have been structurally hashed, discarding nodes from unsupported languages or unparsable files. This pattern appears in codebase_rag/cypher_queries.py lines 280-286.

Near-Duplicate Scoring (Type-3 Clones)

The ast_branch_fingerprints field enables statement-level similarity analysis. When two functions have different root fingerprints but share branch-level digests, evals/duplicates.py computes a similarity score based on overlapping subtrees. This handles Type-3 clones where statements are added, removed, or reordered.

The duplicate evaluation logic (lines 59-60) comments explicitly reference this branch-level comparison for scoring near-duplicates.

Graph Staleness Detection

The fingerprint algorithm version is implicitly tracked through the implementation in parsers/ast_fingerprint.py. Any change to skeletonization rules, placeholder tokens, or hashing parameters invalidates cached fingerprints, forcing a full graph rebuild. This prevents mixed-generation fingerprints—a critical consistency guarantee when iterating on the parsing pipeline.

Key Implementation Files for ast_fingerprint

File	Role
codebase_rag/parsers/ast_fingerprint.py	Implements skeleton extraction, token replacement, and Merkle-tree hashing. Contains compute_ast_fingerprint (lines 41-74) and fingerprint_props (lines 29-38).
codebase_rag/constants/graph.py	Declares property keys: KEY_AST_FINGERPRINT, KEY_AST_FINGERPRINT_NODES, KEY_AST_BRANCH_FINGERPRINTS (lines 96-100).
codebase_rag/cypher_queries.py	Demonstrates Cypher patterns for fingerprint-based filtering and duplicate detection (lines 280-286).
evals/duplicates.py	Consumes fingerprints to group clones and compute Type-3 similarity scores (lines 59-60).

Performance and Storage Characteristics

• Deterministic output – Same AST structure always yields same fingerprint, regardless of formatting or comments
• Language-agnostic – Works with any tree-sitter grammar
• Compact storage – Blake2b produces 64-character hex strings; branch fingerprints add modest overhead proportional to function complexity
• Fast comparison – String equality checks are O(1); no need to re-parse source for duplicate detection

Summary

• ast_fingerprint is a structural hash that abstracts identifiers and literals while preserving syntactic shape
• Generated via Merkle-tree hashing in parsers/ast_fingerprint.py using Blake2b
• Stored alongside node counts and branch fingerprints for multi-granularity similarity analysis
• Powers Type-1/2 clone detection through exact fingerprint matching and Type-3 scoring through branch overlap
• Enforces graph consistency by versioning the algorithm implementation and forcing rebuilds on changes

Frequently Asked Questions

How does ast_fingerprint handle renamed variables?

Identifiers are replaced with a uniform placeholder token during skeletonization, so def add(x, y) and def add(a, b) with identical bodies produce the same fingerprint. This is the defining characteristic of Type-2 clone detection.

What happens if the fingerprint algorithm changes?

The implementation in parsers/ast_fingerprint.py serves as the version anchor. Any modification to skeleton rules or hashing invalidates existing fingerprints, triggering a full graph rebuild to maintain consistency.

Can ast_fingerprint detect code moved between files?

Yes. The fingerprint depends only on the function body's syntactic structure, not its location. Functions with identical skeletons across different files share the same ast_fingerprint value.

Is ast_fingerprint available for all programming languages?

Availability depends on tree-sitter grammar support. The property is set only when parsing succeeds, so Cypher queries filtering on ast_fingerprint IS NOT NULL effectively restrict results to supported languages with successful parses.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}