# How to Detect Dead Code by Walking Call and Reference Edges in code-graph-rag

> Learn to detect dead code by walking call and reference edges. code-graph-rag uses BFS to find unused code efficiently. Explore this powerful technique for cleaner codebases.

- Repository: [Vitali Avagyan/code-graph-rag](https://github.com/vitali87/code-graph-rag)
- Tags: how-to-guide
- Published: 2026-08-20

---

**The dead-code detector in code-graph-rag performs a multi-source BFS from entry points across CALLS and REFERENCES edges, then expands factory classes and override chains until fixed point.**

Dead code increases maintenance burden and binary bloat. The **code-graph-rag** repository provides a language-agnostic dead-code detector that identifies unreachable functions, methods, and classes by walking call-graph edges from known entry points. This guide explains exactly how the detection works and how to use it in your own projects.

## How the Dead-Code Detector Works

The implementation in [`codebase_rag/dead_code.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/dead_code.py) uses a three-stage pipeline optimized for large codebases.

### Stage 1: Identify Reachability Roots

Before walking the graph, the detector must find all **entry points** where execution can begin. Root detection (lines 12-36 of [`dead_code.py`](https://github.com/vitali87/code-graph-rag/blob/main/dead_code.py)) combines three strategies:

- **Root decorators** — patterns like `@route`, `@task`, `@fixture`, `@app.get` defined in `DEFAULT_ROOT_DECORATORS`
- **Language-specific runtime hooks** — `main`/`init` functions, Rust trait methods, Java serialization hooks, C# attributes, NestJS decorators, React lifecycle methods

- **Explicit user-supplied roots** — via `config.entry_points`

Helper predicates in [`dead_code.py`](https://github.com/vitali87/code-graph-rag/blob/main/dead_code.py) implement this logic:

| Helper Function | Purpose |
|---------------|---------|
| `_is_dunder` | Python magic methods (implicitly reachable) |
| `_is_rust_runtime_root` | `main`, `panic_handler`, `alloc_error_handler` |
| `_is_cpp_operator_root` | Operator overloads that the runtime invokes |
| `_is_nest_root` | NestJS controller, service, module decorators |
| `_is_react_root` | Component lifecycle and hook methods |

Root constants live in [`codebase_rag/constants/deadcode_roots.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/constants/deadcode_roots.py), making the framework extensible for new languages.

### Stage 2: Fetch the Complete Graph

Two Cypher queries in [`codebase_rag/cypher_queries.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/cypher_queries.py) pull the full call-graph:

```python

# CYPHER_DEAD_CODE_NODES — all symbols with project prefix

# Returns: qualified_name, path, start_line, end_line, kind

# CYPHER_DEAD_CODE_RELS — all reachability edges

# Returns: source_qualified_name, source_kind, rel_type, target_qualified_name, target_kind

```

The fetched relationships include:

- `CALLS` — direct function/method invocations
- `REFERENCES` — variable reads, attribute access
- `INSTANTIATES` — class instantiation
- `INHERITS`, `DEFINES`, `DEFINES_METHOD` — class hierarchy
- `OVERRIDES`, `IMPLEMENTS` — polymorphic dispatch

### Stage 3: Walk the Graph with BFS and Fixed-Point Expansion

The `_walk` function (lines 75-90 of [`dead_code.py`](https://github.com/vitali87/code-graph-rag/blob/main/dead_code.py)) implements a multi-source BFS:

```python
def _walk(frontier, adjacency, live):
    """Expand reachability across CALLS and REFERENCES edges."""
    queue = deque(frontier)
    while queue:
        node = queue.popleft()
        for neighbor in adjacency.get(node, []):
            if neighbor not in live:
                live.add(neighbor)
                queue.append(neighbor)

```

After the initial walk, a **fixed-point expansion** (lines 60-86) handles dynamic dispatch patterns:

1. **Decorated closures** — functions returned by decorators
2. **Factory classes** — methods on classes that instantiate other live classes
3. **Override chains** — methods that override already-live base methods

This repeats until no new nodes become live. Nodes never marked live are reported as dead code.

The algorithm avoids the original O(roots × graph) complexity by using two linear scans: one to build adjacency, one to propagate reachability.

## Running Dead-Code Detection

The public API exposes `collect_dead_code` with configurable behavior:

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

# Initialize your Neo4j-backed graph client

client = GraphQueryClient(uri="bolt://localhost:7687", auth=("neo4j", "password"))

# Configure detection behavior

config = default_dead_code_config(
    include_tests=False,           # Exclude test files from analysis

    include_classes=True,          # Treat class definitions as dead-code candidates

    exclude_patterns=("*/generated/*", "*/migrations/*")  # Skip generated code

)

# Add explicit entry points not discoverable by heuristics

config.entry_points = ("myproject.cli.main", "myproject.worker.start_worker")

# Execute detection

dead_rows = collect_dead_code(client, project_prefix="myproject", config=config)

# Report results

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

```

Each returned row contains:

- `qualified_name` — fully qualified symbol name
- `path` — source file path
- `start_line` / `end_line` — location in source
- `kind` — function, method, class, or module

## Understanding the Internal Graph Walk

For advanced customization, the core `dead_code_from_graph` function shows how reachability propagates:

```python
from collections import defaultdict
from codebase_rag.dead_code import _walk

def dead_code_from_graph(nodes, relationships, project_prefix, config):
    # ① Build adjacency list from CALLS and REFERENCES only

    adjacency = defaultdict(set)
    for src, src_kind, rel, dst, dst_kind in relationships:
        if rel in {"CALLS", "REFERENCES"}:
            adjacency[src].add(dst)
    
    # ② Initialize roots from decorators, language hooks, and config

    roots = _collect_roots(nodes, config)  # implements heuristic detection

    
    # ③ First-pass BFS from all roots

    live = set(roots)
    _walk(roots, adjacency, live)
    
    # ④ Fixed-point: expand factories and overrides

    prev_size = -1
    while len(live) != prev_size:
        prev_size = len(live)
        _expand_factories(nodes, live, adjacency)   # lines 60-72

        _expand_overrides(nodes, live)              # lines 73-86

    
    # ⑤ Return dead symbols

    all_nodes = {n['qualified_name'] for n in nodes}
    return all_nodes - live

```

## Customizing Root Detection

To add framework-specific entry points, modify [`codebase_rag/constants/deadcode_roots.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/constants/deadcode_roots.py) or pass additional patterns via config:

```python
from codebase_rag.constants.deadcode_roots import DEFAULT_ROOT_DECORATORS

# Extend for a custom Django-like framework

MY_DECORATORS = DEFAULT_ROOT_DECORATORS | {
    r"@command",      # CLI commands

    r"@signal",       # Signal handlers

    r"@admin\.register",  # Django admin hooks

}

config = default_dead_code_config()
config.root_decorator_patterns = MY_DECORATORS

```

Language-specific helpers in [`dead_code.py`](https://github.com/vitali87/code-graph-rag/blob/main/dead_code.py) follow a consistent pattern: test the node's qualified name, decorators, or parent scope against known framework conventions.

## Key Files and Their Roles

| File | Responsibility |
|------|--------------|
| [`codebase_rag/dead_code.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/dead_code.py) | **Core engine**: root detection (`_is_*` helpers), BFS walk (`_walk`), fixed-point expansion, public API (`collect_dead_code`) |
| [`codebase_rag/constants/deadcode_roots.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/constants/deadcode_roots.py) | Declarative registry of entry-point patterns by language/framework |
| [`codebase_rag/cypher_queries.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/cypher_queries.py) | Cypher query definitions: `CYPHER_DEAD_CODE_NODES`, `CYPHER_DEAD_CODE_RELS` |
| [`codebase_rag/graph_loader.py`](https://github.com/vitali87/code-graph-rag/blob/main/codebase_rag/graph_loader.py) | `GraphQueryClient` for executing Cypher against Neo4j |
| [`evals/dead_code.py`](https://github.com/vitali87/code-graph-rag/blob/main/evals/dead_code.py) | Reference implementation showing end-to-end usage |

## Summary

- **Dead-code detection** identifies unreachable symbols by walking **CALLS** and **REFERENCES** edges from known entry points
- **Root detection** combines decorator patterns, language runtime hooks, and user configuration in [`dead_code.py`](https://github.com/vitali87/code-graph-rag/blob/main/dead_code.py) lines 12-36
- **Graph walk** uses multi-source BFS in `_walk` (lines 75-90) followed by fixed-point expansion for factories and overrides
- Two **Cypher queries** fetch all nodes and edges; the algorithm then operates in-memory for performance
- The **public API** via `collect_dead_code` supports language-agnostic detection with customizable filters and explicit entry points

## Frequently Asked Questions

### How does the detector handle dynamic dispatch and virtual methods?

The detector uses a **fixed-point expansion phase** after the initial BFS. When a base method is marked live, `_expand_overrides` revives all overriding implementations. Similarly, `_expand_factories` activates methods on classes that instantiate other live classes. This process repeats until no new nodes are discovered, approximating runtime dispatch without executing code.

### Can I use this for languages other than Python?

Yes. The **code-graph-rag** architecture is language-agnostic. Language-specific logic lives in helper predicates like `_is_rust_runtime_root` and `_is_cpp_operator_root`. To add a new language, extend [`deadcode_roots.py`](https://github.com/vitali87/code-graph-rag/blob/main/deadcode_roots.py) with entry-point patterns and add a corresponding `_is_*_root` predicate in [`dead_code.py`](https://github.com/vitali87/code-graph-rag/blob/main/dead_code.py).

### Why use two linear scans instead of BFS from each root separately?

The original implementation performed **per-root BFS** with O(roots × graph) complexity, causing timeouts on large codebases. The current design fetches all nodes and edges once, builds an adjacency map, then walks from all roots simultaneously. This reduces complexity to O(nodes + edges) regardless of root count.

### What edge types are considered for reachability?

The **CALLS** and **REFERENCES** relationships directly propagate reachability during BFS. **INSTANTIATES**, **INHERITS**, **OVERRIDES**, and **IMPLEMENTS** influence reachability indirectly through the fixed-point expansion phases for factories and polymorphic dispatch.