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

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 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) 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 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, making the framework extensible for new languages.

Stage 2: Fetch the Complete Graph

Two Cypher queries in codebase_rag/cypher_queries.py pull the full call-graph:

# 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) implements a multi-source BFS:

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:

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:

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 or pass additional patterns via config:

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 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	Core engine: root detection (_is_* helpers), BFS walk (_walk), fixed-point expansion, public API (collect_dead_code)
codebase_rag/constants/deadcode_roots.py	Declarative registry of entry-point patterns by language/framework
codebase_rag/cypher_queries.py	Cypher query definitions: CYPHER_DEAD_CODE_NODES, CYPHER_DEAD_CODE_RELS
codebase_rag/graph_loader.py	GraphQueryClient for executing Cypher against Neo4j
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 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 with entry-point patterns and add a corresponding _is_*_root predicate in 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.

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