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

> Discover how trace_path uses BFS traversal with SQLite recursive CTEs in cbm_store_bfs to analyze inbound and outbound call chains layer by layer within codebase memory.

- Repository: [Martin Vogel/codebase-memory-mcp](https://github.com/DeusData/codebase-memory-mcp)
- Tags: deep-dive
- Published: 2026-07-07

---

**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`](https://github.com/DeusData/codebase-memory-mcp/blob/main/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`](https://github.com/DeusData/codebase-memory-mcp/blob/main/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:

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

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

```

JSON-RPC request with edge type filtering:

```json
{
  "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:

```sh
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`](https://github.com/DeusData/codebase-memory-mcp/blob/main/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`](https://github.com/DeusData/codebase-memory-mcp/blob/main/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.