How Dead Code Detection Works in the Knowledge Graph: Inside Instagit's Full-Graph Analysis

Instagit detects dead code by querying the complete SQLite knowledge graph for true incoming degrees, marking symbols as dead only when both call references (CALLS) and usage references (USAGE) equal zero across the entire codebase.

The DeusData/codebase-memory-mcp project (Internally referred to as Instagit) implements a robust dead code detection system that operates directly against its underlying knowledge graph store. Unlike superficial static analysis tools that might miss cross-file references or be limited by visual sampling windows, Instagit performs batch degree queries against the full graph to determine whether functions and methods are truly unreachable.

Full-Graph Degree Queries Against the SQLite Store

Dead code detection in Instagit relies on true full-graph incoming degree calculations. When the system generates a layout in src/ui/layout3d.c, it retrieves the complete reference count for every node from the SQLite store rather than relying on sampled edges that might fit only the current visual window.

The system queries two specific edge types:

• CALLS: Incoming function calls to the symbol
• USAGE: Other references or usages of the symbol

These queries execute through cbm_store_batch_count_degrees, which operates directly on the knowledge graph database.

/* True full‑graph incoming degree for dead‑code classification. This MUST
 * come from the store, not the sampled `mapped` edges built above … */
cbm_store_batch_count_degrees(store, node_ids + off, cnt,
                              "CALLS", in_calls + off, deg_dummy + off);
cbm_store_batch_count_degrees(store, node_ids + off, cnt,
                              "USAGE", in_usage + off, deg_dummy + off);

Classification Logic in layout3d.c

Located in src/ui/layout3d.c (lines 45-55, 62-75, and 84-90), the classification logic applies a priority-based status determination to every node. The renderer evaluates conditions in strict order, assigning one of seven possible statuses based on the incoming degree data and symbol metadata.

The dead code determination follows this specific logic:

Condition	Status
Not a function/method	"structural"
Test file or marked as test	"test"
Entry point or route	"entry"
Exported symbol	"exported"
Both in_calls == 0 AND in_usage == 0	"dead"
in_calls == 1	"single"
Otherwise	"normal"

The C implementation of this logic appears as:

if (!is_fn)               status = "structural";
else if (testish)         status = "test";
else if (nf.is_entry)    status = "entry";
else if (nf.is_exported) status = "exported";
else if (ic == 0 && iu == 0) status = "dead";
else if (ic == 1)         status = "single";
else                      status = "normal";

The cbm_store_batch_count_degrees Implementation

The function cbm_store_batch_count_degrees, implemented in src/store/cbm_store.c, performs the actual SQL queries against the knowledge graph. This function accepts:

• A store handle
• An array of node IDs
• The edge type to count ("CALLS" or "USAGE")
• Output arrays for incoming and outgoing degree counts

By querying the store directly, the system guarantees that dead code classification reflects the complete codebase topology, not a partial view.

Why Full-Graph Analysis Prevents False Positives

Visual layout engines often work with sampled or filtered edge sets to maintain performance when rendering large codebases. However, for dead code detection, sampling creates false positives—functions might appear unused in a subset of edges while actually being called by code outside the visual window.

Instagit solves this by executing cbm_store_batch_count_degrees directly against the persistent SQLite store, bypassing the mapped edges used for visualization. This ensures that a function is marked "dead" only when the knowledge graph contains zero incoming CALLS and USAGE edges in the complete graph structure.

Consumption via JSON Serialization

Once classified, the status propagates through src/ui/cbm_layout.h, where cbm_layout_node_t.status stores the classification. The module src/ui/cbm_layout_to_json.c serializes this field into JSON output, enabling downstream tools and IDEs to consume dead code information for refactoring decisions.

Practical Example:

/* Example: fetch full‑graph degrees for a batch of nodes */
int64_t ids[] = { 101, 102, 103 };
int calls[3], usage[3], dummy[3];
cbm_store_batch_count_degrees(store, ids, 3, "CALLS", calls, dummy);
cbm_store_batch_count_degrees(store, ids, 3, "USAGE", usage, dummy);

/* Determine dead‑code status */
for (int i = 0; i < 3; ++i) {
    const char *status = (calls[i] == 0 && usage[i] == 0) ? "dead" : "alive";
    printf("Node %lld is %s\n", (long long)ids[i], status);
}

Summary

• True full-graph analysis: Dead code detection queries the complete SQLite knowledge graph via cbm_store_batch_count_degrees, not sampled visual edges.
• Dual edge inspection: The system checks both "CALLS" and "USAGE" incoming degrees to confirm a symbol has zero references.
• Precise classification: Located in src/ui/layout3d.c, the logic marks nodes as "dead" only when both counts equal zero, after checking for entry points, exports, and test files.
• Persistent storage: The status field defined in src/ui/cbm_layout.h and serialized in src/ui/cbm_layout_to_json.c makes dead code information available to external tools.

Frequently Asked Questions

How does Instagit avoid false positives when detecting dead code?

Instagit queries the complete knowledge graph rather than visual samples. The function cbm_store_batch_count_degrees in src/store/cbm_store.c retrieves incoming edge counts directly from the SQLite store, ensuring that a function marked as dead truly has zero CALLS and USAGE references across the entire codebase, not just within the current view.

What is the difference between "dead" and "single" status?

A node receives "dead" status only when both in_calls and in_usage equal zero, indicating no references whatsoever. The "single" status applies when in_calls equals exactly one, flagging functions with minimal coupling that might be candidates for inlining or removal, but which are technically still alive in the codebase.

Why check both CALLS and USAGE edges for dead code detection?

Checking only function calls might miss references through imports, interfaces, or configuration objects. By requiring both CALLS (incoming function invocations) and USAGE (general symbol references) to equal zero, Instagit ensures that symbols used only for their side effects or type definitions—without direct invocations—are correctly classified as dead when truly unreferenced.

Where is the dead code status stored and exported?

The status is stored in the cbm_layout_node_t structure defined in src/ui/cbm_layout.h. The src/ui/cbm_layout_to_json.c module serializes this field into JSON output, allowing downstream refactoring tools and editors to consume dead code classifications programmatically without parsing the C code directly.

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