How trace_path Performs BFS Traversal for Call Chain Analysis in Codebase Memory MCP

The trace_path tool delegates graph traversal to cbm_store_bfs, which implements a true breadth-first search using SQLite recursive CTEs to explore inbound and outbound call chains layer by layer.

The trace_path feature in DeusData/codebase-memory-mcp enables developers to explore dependency relationships by finding who calls a function and what it calls. Unlike in-memory graph walks, this MCP tool leverages the database layer to perform efficient trace_path BFS traversal using recursive SQL queries. This approach handles large codebases while respecting directionality, depth limits, and edge type filters.

Tool Dispatch and Parameter Extraction

When the MCP server receives a request with "tool":"trace_path" defined in src/mcp/mcp.c, it extracts parameters including function_name, project, direction (inbound, outbound, or both), depth, and edge_types. The function name resolves to a node ID via cbm_store_find_node_by_name, establishing the BFS root node for the traversal.

Recursive CTE Implementation in the Store Layer

The actual BFS traversal occurs in cbm_store_bfs within src/store/store.c (lines 02552–02700). Rather than implementing a manual queue in application code, the function constructs a recursive common table expression that expands the graph frontier layer by layer using the database engine.

Building the Edge Type Filter

If the caller specifies edge_types, the helper bfs_build_types_clause (lines 02531–02550) constructs a SQLite placeholder list like ?1,?2,… for parameterized queries. When no types are supplied, the default edge type defaults to "CALLS".

Constructing the Recursive Query

The generated SQL implements the BFS logic directly:

snprintf(sql, sizeof(sql),
         "WITH RECURSIVE bfs(node_id, hop) AS ("
         "  SELECT %lld, 0"
         "  UNION"
         "  SELECT %s, bfs.hop + 1"
         "  FROM bfs"
         "  JOIN edges e ON %s"
         "  WHERE e.type IN (%s) AND bfs.hop < %d"
         ")"
         "SELECT … FROM bfs … ORDER BY bfs.hop LIMIT %d;",
         start_id,          // root node
         next_id,           // target column (source or target depending on direction)
         join_cond,         // e.source_id = bfs.node_id  or  e.target_id = bfs.node_id
         types_clause,      // placeholder list built above
         max_depth,
         max_results);

The CTE starts with the root node at hop = 0. Each iteration joins the current frontier against the edges table, incrementing the hop counter. The WHERE bfs.hop < max_depth clause enforces the depth limit, while ORDER BY bfs.hop ensures results return in true BFS order with nearest neighbors first.

Direction Handling: Inbound vs Outbound Traversal

The direction parameter determines the join condition used in the recursive query. For inbound traversal, the join matches e.target_id = bfs.node_id to find callers. For outbound, it uses e.source_id = bfs.node_id to find callees. The both direction requires the query to traverse relationships in both orientations, effectively exploring the undirected neighborhood of the root function.

Result Enrichment and Metadata Collection

After SQLite returns the rows, cbm_store_bfs packs them into a cbm_traverse_result_t struct, attaching the original root node and hop distances. The MCP layer then serializes this into a JSON array of node objects. When flags like risk_labels or include_tests are set, a second pass via bfs_collect_edges (starting at line 02565) gathers edge metadata and annotates each hop with risk classifications or test-file markers.

Practical Usage Examples

Find all callers of OrderHandler up to three hops deep:

codebase-mcp trace_path \
  function_name=OrderHandler \
  project=my-service \
  direction=inbound \
  depth=3

JSON-RPC request with edge type filtering:

{
  "tool": "trace_path",
  "params": {
    "function_name": "OrderHandler",
    "project": "my-service",
    "direction": "inbound",
    "depth": 3,
    "edge_types": ["CALLS"],
    "risk_labels": true
  }
}

Trace both calls and data flows:

codebase-mcp trace_path function_name=ProcessData project=repo direction=both depth=2 edge_types=CALLS edge_types=DATA_FLOWS

Summary

• The trace_path tool delegates traversal to cbm_store_bfs in src/store/store.c rather than implementing its own graph walk.
• BFS traversal uses SQLite recursive CTEs that expand the graph layer by layer, respecting depth limits via the hop counter.
• Directionality (inbound/outbound) is handled by adjusting the join condition between the CTE and the edges table.
• Optional enrichment via bfs_collect_edges adds risk labels and test markers in a second pass after the initial traversal.

Frequently Asked Questions

How does trace_path handle cycles in the call graph?

The recursive CTE in cbm_store_bfs naturally handles cycles through the set semantics of SQL recursive queries. Because each iteration only joins the current frontier against unvisited edges and SQLite automatically prevents infinite recursion by tracking visited row combinations, the traversal terminates safely even when encountering circular dependencies between functions.

What is the performance impact of deep traversal depths?

Since the trace_path BFS traversal uses indexed SQL queries against the edges table, performance depends on database indexing and the cardinality of the result set. The LIMIT clause caps the total results returned, and the bfs.hop < max_depth condition stops expansion early, preventing unbounded queries even in large codebases with complex dependency graphs.

Can trace_path traverse custom relationship types beyond CALLS?

Yes, the edge_types parameter accepts an array of relationship type strings. The bfs_build_types_clause function constructs parameterized SQL placeholders for these types, allowing traversal of DATA_FLOWS, INHERITS, IMPORTS, or any custom edge types defined in your codebase graph schema.

Where is the tool entry point defined in the source code?

The tool dispatch table and JSON-RPC parameter extraction logic reside in src/mcp/mcp.c, where the trace_path entry maps incoming requests to the internal handler. This handler validates parameters, resolves the function name to a node ID, and invokes cbm_store_bfs to perform the actual database traversal.

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