# How Dead Code Detection Works in code-graph-rag by Walking CALL and REFERENCE Edges

> Discover how dead code detection in code-graph-rag works. Learn how it walks CALL and REFERENCE edges to identify and report unreachable code, optimizing your codebase.

- Repository: [Vitali Avagyan/code-graph-rag](https://github.com/vitali87/code-graph-rag)
- Tags: internals
- Published: 2026-08-16

---

**Dead code detection in code-graph-rag uses a two-pass graph traversal: first walking CALLS and REFERENCES edges from root symbols to mark live code, then expanding via DEFINES and OVERRIDES relationships to capture runtime-generated symbols, with unreachable candidates reported as dead code.**

The `vitali87/code-graph-rag` project implements a sophisticated dead code elimination system built on top of a **code graph** representation. In this graph, every symbol—functions, methods, classes, and more—becomes a node, with edges describing how symbols relate to each other. The detection engine identifies unreachable code by systematically exploring which symbols can actually be invoked from known entry points.

## Core Algorithm: The `dead_code_from_graph` Function

The entry point for detection is **`dead_code_from_graph`** in [`codebase_rag/dead_code.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/dead_code.py) [lines 92-102](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/dead_code.py#L92-L102). This function orchestrates a three-phase analysis that transforms raw graph data into actionable dead code reports.

### Phase 1: Identifying Candidates and Root Symbols

The algorithm first builds two critical sets:

- **`candidates`**: All definition nodes whose qualified names start with the project prefix [lines 29-35](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/dead_code.py#L29-L35)
- **`roots`**: Symbols that serve as known entry points into the codebase

Root discovery relies on extensive heuristics implemented in a conditional loop starting at [line 106](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/dead_code.py#L106-L110) and continuing through numerous `elif` branches. These heuristics cover:

- **Decorated functions** (e.g., `@app.route`, `@click.command`)
- **Exported symbols** (public API surface)
- **Framework-specific entry points** (Django views, Flask handlers, etc.)
- **Test symbols** (when enabled)
- **Language runtime roots** (e.g., `main()`, [`__init__.py`](https://github.com/vitali87/code-graph-rag/blob/main/__init__.py) exports)
- **Rust runtime markers** via `_is_rust_runtime_root`
- **JavaScript well-known symbols** via `_is_js_well_known_symbol_root`
- **Dunder methods** via `_is_dunder`

The breadth of root detection ensures the analysis understands each language's unique execution model.

### Phase 2: Building the Traversal Adjacency

Not all graph edges are relevant for reachability analysis. The system selectively extracts only **CALLS** and **REFERENCES** edges, which represent actual invocation and usage relationships.

These edge types are defined as constants in [`codebase_rag/constants/graph.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/constants/graph.py) [lines 165-166](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/constants/graph.py#L165-L166):

```python
_CALLS = "CALLS"
_REFERENCES = "REFERENCES"

```

During processing, any relationship matching `traversal = {_CALLS, _REFERENCES}` is stored in an `adjacency` dictionary mapping each node to its reachable neighbors [lines 107-110](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/dead_code.py#L107-L110).

### Phase 3: Depth-First Walk from Roots

The **`_walk`** helper function implements an explicit **stack-based depth-first search (DFS)** [lines 75-90](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/dead_code.py#L75-L90). This approach avoids Python's recursion limit while efficiently exploring the call graph:

```python
live = set(roots)
_walk(roots, adjacency, live)

```

The `_walk` function populates the `live` set with every symbol reachable via CALLS and REFERENCES edges from the root set.

### Phase 4: Second-Pass Expansion

Raw call-graph reachability misses important cases. The second expansion [lines 151-185](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/dead_code.py#L151-L185) iteratively revives symbols that are:

- **Defined inside live owners** (nested functions, class methods)
- **Decorated functions** that transform at runtime
- **Factory-generated classes** and their methods
- **Override implementations** via OVERRIDES relationships

This iterative loop continues until convergence—no new nodes are added—ensuring complete coverage of runtime-reachable code.

### Phase 5: Computing and Reporting Dead Code

Finally, dead symbols are calculated as the set difference:

```python
dead = candidates - live

```

Optional filtering applies exclude patterns, then results are formatted as row dictionaries with qualified names, file paths, and line numbers [lines 87-101](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/dead_code.py#L87-L101).

## Practical Usage: The `collect_dead_code` API

The public interface hides this complexity behind a clean API. Here's how to run dead code detection on your project:

```python
from codebase_rag.graph_updater import GraphQueryClient
from codebase_rag.dead_code import collect_dead_code, default_dead_code_config

# 1️⃣  Create a client connected to your Memgraph instance

client = GraphQueryClient(...)

# 2️⃣  Configure detection—exclude tests and generated files

config = default_dead_code_config(
    include_tests=False,
    include_classes=True,
    exclude_patterns=("*/generated/*",)
)

# 3️⃣  Retrieve dead code for project "my_app"

dead_rows = collect_dead_code(client, "my_app", config)

# 4️⃣  Generate a human-readable report

for row in dead_rows:
    print(f"{row['qualified_name']} – {row['path']}:{row['start_line']}")

```

The `collect_dead_code` function internally invokes `dead_code_from_graph`, translating configuration options into the root heuristics and filters used during analysis.

## Key Implementation Files

| File | Purpose |
|------|---------|
| [`codebase_rag/dead_code.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/dead_code.py) | Core engine with `dead_code_from_graph`, `_walk`, and root heuristics |
| [`codebase_rag/constants/graph.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/constants/graph.py) | Edge type constants (`CALLS`, `REFERENCES`, `DEFINES`, `OVERRIDES`) |
| [`codebase_rag/constants/deadcode_roots.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/constants/deadcode_roots.py) | Default root decorators and language-specific markers |
| [`codebase_rag/graph_updater.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/graph_updater.py) | `GraphQueryClient` for fetching graph data from Memgraph |
| [`codebase_rag/path_filters.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/path_filters.py) | Test path detection via `matches_test_path` |

## Summary

- **Graph-based foundation**: Dead code detection operates on a code graph where symbols are nodes and relationships are edges.
- **Selective edge walking**: Only `CALLS` and `REFERENCES` edges are traversed in the initial reachability pass.
- **Multi-phase analysis**: Root discovery → DFS walk → iterative expansion → dead set calculation.
- **Language-aware roots**: Extensive heuristics identify entry points across Python, Rust, JavaScript, and other supported languages.
- **Two-pass completeness**: The second expansion captures runtime-generated code that static call graphs miss.

## Frequently Asked Questions

### What's the difference between CALLS and REFERENCES edges?

**`CALLS`** edges represent direct function or method invocations, while **`REFERENCES`** edges capture symbol usage that doesn't involve execution—such as accessing a module-level variable, importing a name, or referencing a class without instantiating it. Both edge types are necessary because code can be "alive" through either direct execution or indirect access patterns.

### Why does dead code detection need a second expansion pass?

The initial walk only follows `CALLS` and `REFERENCES` edges, which captures static reachability but misses **runtime-generated code**. Decorators transform functions at import time, factories create classes dynamically, and method overrides are invoked through polymorphism. The second pass uses `DEFINES`, `OVERRIDES`, and ownership relationships to resurrect these indirectly reachable symbols.

### How does the system identify root symbols reliably?

Root identification combines **multiple heuristics** tailored to each language. For Python, it recognizes common web framework decorators, Click commands, and Celery tasks. For Rust, it detects `main`, `#[test]` functions, and public crate exports. For JavaScript, it identifies exported module members and framework lifecycle hooks. The `default_dead_code_config` function in [`constants/deadcode_roots.py`](https://github.com/vitali87/code-graph-rag/blob/main/constants/deadcode_roots.py) centralizes these patterns.

### Can the analysis include or exclude test code?

Yes, through the `include_tests` parameter in `default_dead_code_config`. When enabled, test functions and methods are treated as roots, ensuring that code only referenced by tests is marked live. When disabled, such code becomes eligible for dead code reporting—useful when tests themselves are being pruned or when measuring production-only coverage.