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

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 lines 92-102. 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
• 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 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 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 lines 165-166:

_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.

Phase 3: Depth-First Walk from Roots

The _walk helper function implements an explicit stack-based depth-first search (DFS) lines 75-90. This approach avoids Python's recursion limit while efficiently exploring the call graph:

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 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:

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.

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:

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	Core engine with dead_code_from_graph, _walk, and root heuristics
codebase_rag/constants/graph.py	Edge type constants (CALLS, REFERENCES, DEFINES, OVERRIDES)
codebase_rag/constants/deadcode_roots.py	Default root decorators and language-specific markers
codebase_rag/graph_updater.py	GraphQueryClient for fetching graph data from Memgraph
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 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.

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