# How Incremental Parsing and Change Tracking Minimize Rebuild Costs in code-review-graph

> Discover how code-review-graph uses incremental parsing and change tracking to cut rebuild costs. Learn how it optimizes reparsing to O(C+D) complexity, saving significant time and resources.

- Repository: [Tirth Kanani/code-review-graph](https://github.com/tirth8205/code-review-graph)
- Tags: performance
- Published: 2026-08-15

---

**`code-review-graph` employs a four-stage incremental pipeline combining VCS diffs, SHA‑256 hash caching, and graph‑traversal dependency analysis to restrict reparsing to only changed files and their dependents, reducing rebuild complexity from O(N) to O(C + D).**

The `code-review-graph` library constructs a complete code‑dependency graph from every source file in a repository. Rebuilding this graph from scratch on every change would require parsing every file, recomputing hashes, and re‑running every language‑specific resolver—prohibitive costs for large monorepos. Instead, the library leverages **incremental parsing** and **change tracking** to limit work strictly to affected files.

## The Full Rebuild Problem

A naive full rebuild re‑processes every source file in `O(N)` time, where *N* represents the total file count. For repositories containing thousands of modules, this triggers redundant tree‑sitter parsing, hash generation, and cross‑language resolution passes on files that remain untouched. The incremental module in [`code_review_graph/incremental.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/incremental.py) eliminates this waste through selective invalidation.

## Step 1: Detect Changed Files via VCS

The pipeline begins by identifying the exact delta between the previous analysis and the current working tree. The `resolve_incremental_base` function (lines 44‑66) retrieves the last stored commit SHA, then `get_changed_files` (lines 71‑86) invokes `git diff --name-status -z` (or SVN equivalents) to capture added, modified, renamed, and deleted files.

```python
from code_review_graph.incremental import get_changed_files
from pathlib import Path

repo = Path(".")
changed_files = get_changed_files(repo)  # Returns set of Path objects

```

This VCS‑driven detection ensures the system reacts only to concrete repository mutations rather than scanning the filesystem.

## Step 2: Find Impacted Dependents

Changed files rarely exist in isolation. The `find_dependents` function (lines 86‑100) traverses graph edges—including `IMPORTS`, `CALLS`, and `INHERITS` relationships—to locate all files that might be semantically affected by the modifications. The traversal respects configurable safety limits: `_MAX_DEPENDENT_HOPS` caps the traversal depth, while `_MAX_DEPENDENT_FILES` prevents explosion on highly connected nodes.

```python
from code_review_graph.incremental import find_dependents

dependents = set()
for f in changed_files:
    dependents.update(find_dependents(store, f))

```

The union of `changed_files` and `dependents` constitutes the minimal work set for the update.

## Step 3: Skip Unchanged Files via Hash Caching

Even when a file appears in the dependent set, it may remain byte‑identical. Inside `incremental_update` (lines 44‑52), the engine calculates the current SHA‑256 hash of each candidate and compares it against the hash stored in the graph database via `store.get_nodes_by_file`. Matching hashes bypass reparsing entirely, preventing unnecessary work even when dependency chains are long.

## Step 4: Reconcile Stale Files

Files deleted from the repository or newly excluded via `.code-review-graphignore` patterns would otherwise persist as ghost nodes. The `_reconcile_stale_files` helper (lines 13‑21) removes these obsolete entries from the `GraphStore`, ensuring the graph size remains bounded and future incremental passes do not process phantom dependencies.

## Parallel Parsing and Grammar Reuse

For the restricted work set identified above, the engine utilizes the same parallel infrastructure as full builds. The `_select_executor_kind` function (lines 40‑64) chooses between process or thread pools based on workload characteristics. Crucially, `_parse_single_file` (lines 27‑34) maintains a thread‑local `CodeParser` instance, reusing the compiled tree‑sitters grammar across multiple files to eliminate startup overhead.

```python

# Thread-local parser reuse happens automatically inside _parse_single_file

from code_review_graph.incremental import incremental_update
from code_review_graph.graph import GraphStore

store = GraphStore(Path(".code-review-graph/graph.db"))
result = incremental_update(Path("."), store)
print(f"Reparsed {result['files_updated']} files")

```

After parsing, `store.store_file_nodes_edges` persists the new nodes and edges. Finally, language‑specific resolvers in `code_review_graph/resolvers/` execute only for the languages actually present in the change set—avoiding costly post‑processing on untouched languages like Python, Spring, or Rescript.

## Complexity Analysis

The incremental strategy reduces rebuild time from **O(N)** to **O(C + D)**, where *C* is the number of changed files and *D* is the number of their direct and transitive dependents. In typical monorepo workflows, *C + D* constitutes a tiny fraction of *N*, yielding orders‑of‑magnitude speedups while maintaining graph consistency.

## Summary

- **VCS Integration**: `get_changed_files` uses `git diff` to establish precise change boundaries without filesystem scanning.
- **Dependency Propagation**: `find_dependents` traverses IMPORTS/CALLS edges up to configurable limits to capture semantic impact.
- **Content‑Based Deduplication**: SHA‑256 hash comparison in `incremental_update` eliminates re‑parsing of unchanged files.
- **Graph Hygiene**: `_reconcile_stale_files` purges deleted and ignored entries to prevent ghost nodes.
- **Resource Optimization**: Thread‑local `CodeParser` instances and selective resolver execution minimize CPU and memory overhead.

## Frequently Asked Questions

### How does code-review-graph handle renames and mode changes?

The `get_changed_files` function parses `git diff --name-status -z` output, which explicitly encodes renames (R), mode changes (M), additions (A), and deletions (D). Renamed files are treated as modifications to both the old and new paths, ensuring the graph updates references while preserving node identity when hashes match.

### What happens if the dependent graph exceeds `_MAX_DEPENDENT_FILES`?

When `find_dependents` discovers more dependents than the `_MAX_DEPENDENT_FILES` threshold, it aborts early and conservatively includes all remaining files in the work set. This prevents memory explosions on densely connected graphs while ensuring correctness through over‑approximation rather than missed dependencies.

### Can incremental parsing work with repositories other than Git?

Yes. While the reference implementation emphasizes Git via `git diff`, the VCS abstraction in [`incremental.py`](https://github.com/tirth8205/code-review-graph/blob/main/incremental.py) supports SVN equivalents. Users implementing custom VCS adapters can inject changed file sets directly into `incremental_update` without modifying the core graph logic.

### Where is the incremental state persisted between runs?

The last analyzed commit SHA and per‑file hashes reside in the SQLite database managed by `GraphStore` ([`code_review_graph/graph.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/graph.py)). The `resolve_incremental_base` function queries this metadata to determine the diff base for subsequent updates, enabling persistent incremental analysis across CLI invocations.