Understand any codebase instantly. System intelligence for codebases, built for humans and AI.
TypeScript aiai-memoryclaude-codeclicode-analysiscode-mappingcode-memorycodebase-understandingcodexdeveloper-toolsllmopenclawpersistent-memoryprogram-analysissoftware-architecturesystem-intelligencesystem-mapping
// Copyright 2026 Ix Infrastructure Inc.
import { describe, expect, it, vi } from "vitest";
import { buildDependencyTree, type DependencyNode } from "../commands/depends.js";
import { searchPath } from "../commands/trace.js";
import { isRawId } from "../resolve.js";
import { createLimiter, EXPAND_CONCURRENCY, walkTree } from "../tree-walk.js";
/**
* The walks behind `ix depends` and `ix trace` fetch breadth-first now. The
* contract is that nobody can tell from the output unless the node cap cut the
* walk: the depth-first walks they replaced are kept below, verbatim, as the
* oracle.
*/
// ── Oracles: the implementations this replaced ──────────────────────
const PREDICATE_META: Record<string, { relation: DependencyNode["relation"]; sourceEdge: DependencyNode["sourceEdge"] }> = {
CALLS: { relation: "called_by", sourceEdge: "CALLS" },
IMPORTS: { relation: "imported_by", sourceEdge: "IMPORTS" },
REFERENCES: { relation: "referenced_by", sourceEdge: "REFERENCES" },
EXTENDS: { relation: "extended_by", sourceEdge: "EXTENDS" },
IMPLEMENTS: { relation: "implemented_by", sourceEdge: "IMPLEMENTS" },
};
const DEPENDS_PREDICATES = Object.keys(PREDICATE_META);
function nodePriority(n: any): number {
const name = n.name || n.attrs?.name || "";
if (!name || isRawId(name)) return 2;
return (n.provenance?.source_uri ?? n.provenance?.sourceUri ?? n.attrs?.path) ? 0 : 1;
}
/** `buildDependencyTree` as it was before the breadth-first walk. */
async function oldBuildDependencyTree(client: any, rootId: string, opts: { maxDepth: number; maxNodes: number }) {
const { maxDepth, maxNodes } = opts;
const activePredicates = DEPENDS_PREDICATES;
const visited = new Set<string>([rootId]);
let nodesVisited = 0;
let truncated = false;
let depthLimited = false;
let maxDepthReached = 0;
async function expand(nodeId: string, depth: number): Promise<DependencyNode[]> {
if (depth > maxDepth) { depthLimited = true; return []; }
if (nodesVisited >= maxNodes) { truncated = true; return []; }
maxDepthReached = Math.max(maxDepthReached, depth);
const expandResults = await Promise.all(
activePredicates.map((p) => client.expand(nodeId, { direction: "in", predicates: [p], hops: 1 })),
);
const children: DependencyNode[] = [];
const levelSeen = new Set<string>();
const processNodes = async (rawNodes: any[], relation: DependencyNode["relation"], sourceEdge: DependencyNode["sourceEdge"]) => {
const nodes = [...rawNodes].sort((a, b) => nodePriority(a) - nodePriority(b));
for (const n of nodes) {
if (nodesVisited >= maxNodes) { truncated = true; break; }
if (levelSeen.has(n.id)) continue;
const name = n.name || n.attrs?.name || "";
const resolved = !!name && !isRawId(name);
const isCycle = visited.has(n.id);
nodesVisited++;
levelSeen.add(n.id);
visited.add(n.id);
const child: DependencyNode = {
id: n.id,
name: resolved ? name : n.id.slice(0, 8),
kind: n.kind ?? "unknown",
resolved,
relation,
sourceEdge,
path: n.provenance?.source_uri ?? n.provenance?.sourceUri ?? n.attrs?.path ?? undefined,
children: [],
...(isCycle ? { cycle: true } : {}),
};
if (!isCycle && resolved) {
child.children = await expand(n.id, depth + 1);
}
children.push(child);
}
};
for (let i = 0; i < activePredicates.length; i++) {
const meta = PREDICATE_META[activePredicates[i]];
await processNodes(expandResults[i].nodes, meta.relation, meta.sourceEdge);
}
return children;
}
const tree = await expand(rootId, 1);
return { tree, truncated, depthLimited, nodesVisited, maxDepthReached };
}
/** `searchPath` as it was before its queue was prefetched. */
async function oldSearchPath(client: any, fromId: string, toId: string, predicates: string[], maxDepth: number, maxNodes: number) {
if (maxNodes < 1) return { path: null, cut: true, cutReason: "node-cap" };
if (fromId === toId) return { path: [{ id: fromId, name: "", kind: "" }], cut: false };
const nodeMap = new Map<string, { name: string; kind: string }>();
const queue: Array<{ id: string; path: string[] }> = [{ id: fromId, path: [fromId] }];
const visited = new Set<string>([fromId]);
let depthCut = false;
while (queue.length > 0) {
const { id, path } = queue.shift()!;
if (path.length - 1 >= maxDepth) { depthCut = true; continue; }
const [outResult, inResult] = await Promise.all([
client.expand(id, { direction: "out", predicates, hops: 1 }),
client.expand(id, { direction: "in", predicates, hops: 1 }),
]);
for (const n of [...outResult.nodes, ...inResult.nodes]) {
if (visited.has(n.id)) continue;
if (visited.size >= maxNodes) return { path: null, cut: true, cutReason: "node-cap" };
visited.add(n.id);
const name = n.name || n.attrs?.name || n.id.slice(0, 8);
if (!nodeMap.has(n.id)) nodeMap.set(n.id, { name, kind: n.kind ?? "unknown" });
if (n.id === toId) {
return {
path: [...path, n.id].map((nodeId) => {
if (nodeId === fromId) return { id: nodeId, name: "", kind: "" };
const meta = nodeMap.get(nodeId) ?? { name: nodeId.slice(0, 8), kind: "unknown" };
return { id: nodeId, ...meta };
}),
cut: false,
};
}
queue.push({ id: n.id, path: [...path, n.id] });
}
}
return { path: null, cut: depthCut, cutReason: depthCut ? "depth" : undefined };
}
// ── Graphs and clients ──────────────────────────────────────────────
function mulberry32(seed: number): () => number {
let a = seed >>> 0;
return () => {
a = (a + 0x6d2b79f5) >>> 0;
let t = a;
t = Math.imul(t ^ (t >>> 15), t | 1);
t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
type Adjacency = Record<string, Record<string, any[]>>;
/**
* Branching, shared children, cycles back to the root and to ancestors,
* self-loops, one node under two predicates, and the node shapes the walk
* treats differently: unresolved (raw-id or empty name), name only in attrs,
* with and without a path.
*/
function randomGraph(seed: number, size: number, predicates: string[], maxFanout = 3): Adjacency {
const rand = mulberry32(seed);
const pick = (n: number) => Math.floor(rand() * n);
const nodeFor = (i: number): any => {
const roll = (i * 7919 + seed) % 20;
const id = `n${i}`;
if (roll === 0) return { id, name: `${String(i).padStart(4, "0")}d41d8cd98f00b204e9800998ecf8427e`, kind: "function" };
if (roll === 1) return { id, name: "", kind: "function" };
if (roll === 2) return { id, attrs: { name: `attr${i}` }, kind: "method" };
if (roll < 8) return { id, name: `fn${i}`, kind: "function" };
return { id, name: `fn${i}`, kind: "function", provenance: { source_uri: `src/f${i % 5}.ts` } };
};
const adjacency: Adjacency = {};
for (let i = 0; i < size; i++) {
const lists: Record<string, any[]> = {};
for (const p of predicates) {
const k = pick(maxFanout + 1);
lists[p] = Array.from({ length: k }, () => nodeFor(pick(size)));
}
adjacency[`n${i}`] = lists;
}
return adjacency;
}
/**
* A client over an adjacency, with optional per-request delays (so responses
* come back out of order) and in-flight accounting.
*/
function clientFor(adjacency: Adjacency, delaySeed?: number) {
const rand = delaySeed === undefined ? undefined : mulberry32(delaySeed);
const stats = { calls: 0, inFlight: 0, maxInFlight: 0, ids: [] as string[] };
const client = {
expand: vi.fn(async (id: string, opts: { predicates: string[] }) => {
stats.calls++;
stats.ids.push(id);
stats.inFlight++;
stats.maxInFlight = Math.max(stats.maxInFlight, stats.inFlight);
try {
if (rand) await new Promise((r) => setTimeout(r, Math.floor(rand() * 4)));
return { nodes: adjacency[id]?.[opts.predicates[0]] ?? [], edges: [] };
} finally {
stats.inFlight--;
}
}),
};
return { client: client as never, stats };
}
/** Breadth-first listing of a tree: `depth:name` per node. */
function levelOrder(tree: Array<{ name: string; children: any[] }>): string[] {
const out: string[] = [];
let level = tree.map((n) => ({ n, d: 1 }));
while (level.length > 0) {
const next: typeof level = [];
for (const { n, d } of level) {
out.push(`${d}:${n.name}`);
for (const c of n.children) next.push({ n: c, d: d + 1 });
}
level = next;
}
return out;
}
const UNBOUNDED = { maxDepth: Infinity, maxNodes: Infinity };
// ── Same output when no bound cuts ──────────────────────────────────
describe("the breadth-first walk reproduces the depth-first one", () => {
it("on a hand-built graph with a shared child, a diamond and cycles", async () => {
// root <- a, b; a <- c; c <- shared, and d under two predicates;
// b <- shared, root (a cycle); shared <- a (a cycle back up). The old
// walk expands `shared` under `c`, its first occurrence in pre-order, at
// depth 3, and marks it a cycle under `b` at depth 2 — a level-order walk
// would do it the other way round.
const fn = (id: string) => ({ id, name: id, kind: "function", provenance: { source_uri: `src/${id}.ts` } });
const adjacency: Adjacency = {
root: { CALLS: [fn("a"), fn("b")] },
a: { CALLS: [fn("c")] },
c: { CALLS: [fn("shared"), fn("d")], REFERENCES: [fn("d")] },
b: { CALLS: [fn("shared"), fn("root")] },
shared: { REFERENCES: [fn("a")] },
};
for (const bounds of [UNBOUNDED, { maxDepth: 2, maxNodes: Infinity }, { maxDepth: 3, maxNodes: 100 }]) {
const expected = await oldBuildDependencyTree(clientFor(adjacency).client, "root", bounds);
const actual = await buildDependencyTree(clientFor(adjacency).client, "root", bounds);
expect(actual).toEqual(expected);
}
const walk = await buildDependencyTree(clientFor(adjacency).client, "root", UNBOUNDED);
const c = walk.tree[0].children[0];
expect(c.children.map((n) => [n.name, n.relation, !!n.cycle])).toEqual([["shared", "called_by", false], ["d", "called_by", false]]);
expect(c.children[0].children.map((n) => [n.name, !!n.cycle])).toEqual([["a", true]]);
expect(walk.tree[1].children.map((n) => [n.name, !!n.cycle])).toEqual([["shared", true], ["root", true]]);
});
it("on random graphs, unbounded and depth-limited, for every counter and every node", async () => {
for (let seed = 1; seed <= 60; seed++) {
const adjacency = randomGraph(seed, 12 + (seed % 25), DEPENDS_PREDICATES);
for (const maxDepth of [Infinity, 1, 2, 3, 5]) {
const bounds = { maxDepth, maxNodes: Infinity };
const expected = await oldBuildDependencyTree(clientFor(adjacency).client, "n0", bounds);
const actual = await buildDependencyTree(clientFor(adjacency).client, "n0", bounds);
expect(actual, `seed ${seed} depth ${maxDepth}`).toEqual(expected);
}
}
});
it("whenever the cap does not cut the breadth-first walk", async () => {
let compared = 0;
let exact = 0;
for (let seed = 1; seed <= 40; seed++) {
const adjacency = randomGraph(seed, 20, DEPENDS_PREDICATES, 1);
for (const maxNodes of [0, 1, 5, 10, 20, 40, 80, 160]) {
const bounds = { maxDepth: 3, maxNodes };
const actual = await buildDependencyTree(clientFor(adjacency).client, "n0", bounds);
if (actual.truncated) continue;
compared++;
const expected = await oldBuildDependencyTree(clientFor(adjacency).client, "n0", bounds);
// The one deliberate difference: the old walk said `truncated` when
// the cap was spent exactly on the last node, though nothing was left.
if (expected.truncated) {
exact++;
expect(expected.nodesVisited).toBe(maxNodes);
}
expect(actual, `seed ${seed} cap ${maxNodes}`).toEqual({ ...expected, truncated: false });
}
}
expect(compared).toBeGreaterThan(100);
expect(exact).toBeGreaterThan(0);
});
it("the same tree however the responses are ordered in time", async () => {
for (let seed = 1; seed <= 8; seed++) {
const adjacency = randomGraph(seed, 30, DEPENDS_PREDICATES);
for (const bounds of [UNBOUNDED, { maxDepth: 3, maxNodes: 25 }]) {
const inOrder = await buildDependencyTree(clientFor(adjacency).client, "n0", bounds);
for (const delaySeed of [11, 12, 13]) {
const shuffled = await buildDependencyTree(clientFor(adjacency, delaySeed * seed).client, "n0", bounds);
expect(shuffled, `seed ${seed} delays ${delaySeed}`).toEqual(inOrder);
}
}
}
});
});
// ── Cap semantics under level order ─────────────────────────────────
describe("when the node cap cuts the walk", () => {
const fn = (id: string) => ({ id, name: id, kind: "function", provenance: { source_uri: `src/${id}.ts` } });
// root <- a, b, c; a <- a1 <- a2 <- a3; b <- b1
const adjacency: Adjacency = {
root: { CALLS: [fn("a"), fn("b"), fn("c")] },
a: { CALLS: [fn("a1")] },
a1: { CALLS: [fn("a2")] },
a2: { CALLS: [fn("a3")] },
b: { CALLS: [fn("b1")] },
};
it("keeps the shallowest nodes, where depth-first kept the first branch", async () => {
const bounds = { maxDepth: 10, maxNodes: 4 };
const old = await oldBuildDependencyTree(clientFor(adjacency).client, "root", bounds);
expect(levelOrder(old.tree)).toEqual(["1:a", "2:a1", "3:a2", "4:a3"]);
const walk = await buildDependencyTree(clientFor(adjacency).client, "root", bounds);
expect(levelOrder(walk.tree)).toEqual(["1:a", "1:b", "1:c", "2:a1"]);
expect(walk).toMatchObject({ nodesVisited: 4, maxDepthReached: 2, truncated: true, depthLimited: false });
});
it("is a prefix of the next larger cap's walk, level by level", async () => {
for (let seed = 1; seed <= 30; seed++) {
const graph = randomGraph(seed, 40, DEPENDS_PREDICATES);
let previous: string[] | undefined;
for (let cap = 1; cap <= 60; cap++) {
const walk = await buildDependencyTree(clientFor(graph).client, "n0", { maxDepth: 4, maxNodes: cap });
if (!walk.truncated) break;
expect(walk.nodesVisited).toBe(cap);
const order = levelOrder(walk.tree);
expect(order).toHaveLength(cap);
if (previous) expect(order.slice(0, previous.length), `seed ${seed} cap ${cap}`).toEqual(previous);
previous = order;
}
}
});
it("reports the depth bound only for kept nodes it stopped descending into", async () => {
// cap 4 keeps a, b, c, a1 and drops b1; a1 sits at the depth limit of 2
// and has a caller, so the walk stopped descending there as well.
const both = await buildDependencyTree(clientFor(adjacency).client, "root", { maxDepth: 2, maxNodes: 4 });
expect(levelOrder(both.tree)).toEqual(["1:a", "1:b", "1:c", "2:a1"]);
expect(both).toMatchObject({ nodesVisited: 4, maxDepthReached: 2, truncated: true, depthLimited: true });
// cap 3 is spent on the first level: nothing kept reached the depth limit.
const capOnly = await buildDependencyTree(clientFor(adjacency).client, "root", { maxDepth: 2, maxNodes: 3 });
expect(capOnly).toMatchObject({ nodesVisited: 3, maxDepthReached: 1, truncated: true, depthLimited: false });
});
it("does not claim a cut when the budget is spent exactly and nothing is left below", async () => {
// Four nodes in all; a cap of four keeps all of them.
const small: Adjacency = { root: { CALLS: [fn("a"), fn("b")] }, a: { CALLS: [fn("a1"), fn("a2")] } };
const walk = await buildDependencyTree(clientFor(small).client, "root", { maxDepth: 10, maxNodes: 4 });
expect(walk.nodesVisited).toBe(4);
expect(walk.truncated).toBe(false);
});
it("stops requesting once the cap is reached", async () => {
// Every node has two callers, forever.
const fanout = () => ({
expand: vi.fn(async (id: string, opts: { predicates: string[] }) => ({
nodes: opts.predicates[0] === "CALLS" ? [fn(`${id}.a`), fn(`${id}.b`)] : [],
})),
});
const bounds = { maxDepth: 50, maxNodes: 100 };
const client = fanout();
const walk = await buildDependencyTree(client as never, "root", bounds);
expect(walk.truncated).toBe(true);
const expanded = new Set(client.expand.mock.calls.map(([id]) => id));
// Level order reads 1 + 2 + 4 + 8 + 16 nodes and 19 of the next 32
// before the 100th kept node: 50. Past that is only what was already
// requested when the cap was reached.
expect(expanded.size).toBeGreaterThanOrEqual(50);
expect(expanded.size).toBeLessThanOrEqual(50 + EXPAND_CONCURRENCY);
// The depth-first walk spent the same budget on 73 expansions, most of
// them one long branch.
const old = fanout();
await oldBuildDependencyTree(old, "root", bounds);
expect(new Set(old.expand.mock.calls.map(([id]) => id)).size).toBe(73);
});
});
// ── Bounded concurrency ─────────────────────────────────────────────
describe("in-flight requests", () => {
it(`never exceed ${EXPAND_CONCURRENCY}, and the walk does use them`, async () => {
const adjacency = randomGraph(7, 200, DEPENDS_PREDICATES, 6);
const { client, stats } = clientFor(adjacency, 99);
await buildDependencyTree(client, "n0", { maxDepth: 4, maxNodes: 500 });
expect(stats.maxInFlight).toBeLessThanOrEqual(EXPAND_CONCURRENCY);
expect(stats.maxInFlight).toBe(EXPAND_CONCURRENCY);
});
it("hold across walks that share a limiter", async () => {
const adjacency = randomGraph(8, 200, ["CALLS"], 6);
const { client, stats } = clientFor(adjacency, 5);
const limiter = createLimiter(3);
const walk = (rootId: string) => walkTree({
rootId, maxDepth: 4, maxNodes: 200, predicates: ["CALLS"], limiter,
expand: (id, p) => (client as any).expand(id, { predicates: [p] }),
makeNode: (n, _p, { name }) => ({ id: n.id, name, children: [] as any[] }),
});
await Promise.all([walk("n0"), walk("n1"), walk("n2")]);
expect(stats.maxInFlight).toBe(3);
});
it("the limiter runs tasks in the order they were queued", async () => {
const limit = createLimiter(2);
const started: number[] = [];
await Promise.all([0, 1, 2, 3, 4, 5].map((i) => limit(async () => {
started.push(i);
await new Promise((r) => setTimeout(r, (6 - i) % 3));
})));
expect(started).toEqual([0, 1, 2, 3, 4, 5]);
});
});
// ── Failures ────────────────────────────────────────────────────────
describe("a failed expand", () => {
it("still rejects the walk, and a prefetch nobody reads does not crash the process", async () => {
const unhandled = vi.fn();
process.on("unhandledRejection", unhandled);
try {
const client = {
expand: vi.fn(async (id: string) => {
if (id === "bad") throw new Error("500: boom");
return { nodes: id === "root" ? [{ id: "bad", name: "bad", kind: "function" }, { id: "ok", name: "ok", kind: "function" }] : [] };
}),
};
await expect(buildDependencyTree(client as never, "root", UNBOUNDED)).rejects.toThrow("500: boom");
await new Promise((r) => setTimeout(r, 10));
expect(unhandled).not.toHaveBeenCalled();
} finally {
process.off("unhandledRejection", unhandled);
}
});
});
// ── Path mode ───────────────────────────────────────────────────────
describe("trace --to with a prefetched queue", () => {
it("returns the route, cut and reason the one-at-a-time search did", async () => {
let compared = 0;
for (let seed = 1; seed <= 40; seed++) {
const adjacency = randomGraph(seed, 40, ["out", "in"], 2);
const directed = (a: Adjacency) => ({
expand: async (id: string, opts: { direction: string }) => ({ nodes: a[id]?.[opts.direction] ?? [], edges: [] }),
});
const shuffled = (a: Adjacency, s: number) => {
const rand = mulberry32(s);
return {
expand: async (id: string, opts: { direction: string }) => {
await new Promise((r) => setTimeout(r, Math.floor(rand() * 3)));
return { nodes: a[id]?.[opts.direction] ?? [], edges: [] };
},
};
};
for (const [to, maxDepth, maxNodes] of [["n7", 10, 100], ["n13", 3, 100], ["n21", 10, 8], ["n39", 2, 1000]] as const) {
const expected = await oldSearchPath(directed(adjacency), "n0", to, ["X"], maxDepth, maxNodes);
expect(await searchPath(directed(adjacency) as never, "n0", to, ["X"], maxDepth, maxNodes)).toEqual(expected);
expect(await searchPath(shuffled(adjacency, seed) as never, "n0", to, ["X"], maxDepth, maxNodes)).toEqual(expected);
compared++;
}
}
expect(compared).toBe(160);
});
it(`keeps at most ${EXPAND_CONCURRENCY} requests in flight`, async () => {
const adjacency = randomGraph(3, 300, ["out", "in"], 5);
const { stats } = clientFor(adjacency);
let inFlight = 0;
const client = {
expand: async (id: string, opts: { direction: string }) => {
inFlight++;
stats.maxInFlight = Math.max(stats.maxInFlight, inFlight);
await new Promise((r) => setTimeout(r, 1));
inFlight--;
return { nodes: adjacency[id]?.[opts.direction] ?? [], edges: [] };
},
};
await searchPath(client as never, "n0", "nowhere", ["X"], 4, 1000);
expect(stats.maxInFlight).toBe(EXPAND_CONCURRENCY);
});
});