1import { describe, it, expect, vi, beforeEach } from 'vitest';
2import { walkGraph } from './graph-walk';
3
4const { multicallGetSubscriptions } = vi.hoisted(() => ({ multicallGetSubscriptions: vi.fn() }));
5vi.mock('./contract', () => ({ multicallGetSubscriptions }));
6
7beforeEach(() => {
8  multicallGetSubscriptions.mockReset();
9});
10
11function graphOf(adjacency: Record<number, number[]>) {
12  multicallGetSubscriptions.mockImplementation(async (_client: any, userIds: number[]) => {
13    const result = new Map<number, number[]>();
14    for (const id of userIds) result.set(id, adjacency[id] ?? []);
15    return result;
16  });
17}
18
19const fakeClient = {} as any;
20
21describe('walkGraph', () => {
22  it('discovers all reachable nodes in a simple chain', async () => {
23    graphOf({ 1: [2], 2: [3], 3: [] });
24
25    const graph = await walkGraph(fakeClient, 1);
26
27    expect([...graph.nodes.keys()].sort()).toEqual([1, 2, 3]);
28    expect(graph.truncated).toBe(false);
29  });
30
31  it('does not revisit nodes in a cycle', async () => {
32    graphOf({ 1: [2], 2: [1] });
33
34    const graph = await walkGraph(fakeClient, 1);
35
36    expect([...graph.nodes.keys()].sort()).toEqual([1, 2]);
37    // BFS processes one queue-batch per while-loop iteration, not one call per
38    // depth level: [1] is fetched, discovers 2 and enqueues it, then [2] is
39    // fetched on the next iteration and discovers only the already-visited 1.
40    expect(multicallGetSubscriptions).toHaveBeenCalledTimes(2);
41  });
42
43  it('records a node with no subscriptions as an empty array', async () => {
44    graphOf({ 1: [] });
45
46    const graph = await walkGraph(fakeClient, 1);
47
48    expect(graph.nodes.get(1)).toEqual({ userId: 1, subscriptions: [] });
49  });
50
51  it('splits large frontiers into batches of 50', async () => {
52    const adjacency: Record<number, number[]> = { 0: Array.from({ length: 120 }, (_, i) => i + 1) };
53    for (let i = 1; i <= 120; i++) adjacency[i] = [];
54    graphOf(adjacency);
55
56    const graph = await walkGraph(fakeClient, 0);
57
58    expect(graph.nodes.size).toBe(121);
59    // root batch (1) + 120 children split into ceil(120/50) = 3 batches
60    expect(multicallGetSubscriptions).toHaveBeenCalledTimes(4);
61    for (const call of multicallGetSubscriptions.mock.calls) {
62      expect(call[1].length).toBeLessThanOrEqual(50);
63    }
64  });
65
66  it('stops discovering new nodes once maxNodes is reached and reports truncated', async () => {
67    const adjacency: Record<number, number[]> = { 1: [2, 3, 4, 5] };
68    for (const id of [2, 3, 4, 5]) adjacency[id] = [];
69    graphOf(adjacency);
70
71    const graph = await walkGraph(fakeClient, 1, { maxNodes: 2 });
72
73    expect(graph.nodes.size).toBeLessThanOrEqual(2);
74    expect(graph.truncated).toBe(true);
75  });
76
77  it('respects maxDepth by not traversing past the configured depth', async () => {
78    graphOf({ 1: [2], 2: [3], 3: [] });
79
80    const graph = await walkGraph(fakeClient, 1, { maxDepth: 1 });
81
82    expect([...graph.nodes.keys()].sort()).toEqual([1, 2]);
83  });
84
85  it('reports truncated=true when maxDepth cuts off part of the graph (fixed)', async () => {
86    // Regression test: node 3 exists beyond the depth-1 frontier and is never
87    // recorded. truncated must reflect that, not just the maxNodes cap.
88    graphOf({ 1: [2], 2: [3], 3: [] });
89
90    const graph = await walkGraph(fakeClient, 1, { maxDepth: 1 });
91
92    expect(graph.nodes.has(3)).toBe(false);
93    expect(graph.truncated).toBe(true);
94  });
95
96  it('does not report truncated when the walk naturally ends within the depth budget', async () => {
97    // The whole graph is depth <= 1 already, so maxDepth never actually cuts
98    // anything off — truncated should stay false.
99    graphOf({ 1: [2], 2: [] });
100
101    const graph = await walkGraph(fakeClient, 1, { maxDepth: 1 });
102
103    expect([...graph.nodes.keys()].sort()).toEqual([1, 2]);
104    expect(graph.truncated).toBe(false);
105  });
106
107  it('treats maxDepth: 0 as root-only and reports truncated when the root has subscriptions', async () => {
108    graphOf({ 1: [2] });
109
110    const graph = await walkGraph(fakeClient, 1, { maxDepth: 0 });
111
112    expect([...graph.nodes.keys()]).toEqual([1]);
113    expect(graph.truncated).toBe(true);
114  });
115
116  it('does not report truncated when maxDepth: 0 and the root has no subscriptions', async () => {
117    graphOf({ 1: [] });
118
119    const graph = await walkGraph(fakeClient, 1, { maxDepth: 0 });
120
121    expect(graph.truncated).toBe(false);
122  });
123
124  it('does not treat a node reachable via two paths, one over the depth limit, as depth-truncated', async () => {
125    // 3 is reachable at depth 1 (via the direct 1->3 edge) *and* would be
126    // reachable at depth 2 via 1->2->3. Because 3 gets visited through the
127    // depth-1 path first, the depth-2 discovery attempt hits the
128    // `visited.has(sub)` short-circuit (graph-walk.ts:35) before the depth
129    // check ever runs, so this must NOT count as a depth cutoff.
130    graphOf({ 1: [2, 3], 2: [3], 3: [] });
131
132    const graph = await walkGraph(fakeClient, 1, { maxDepth: 1 });
133
134    expect([...graph.nodes.keys()].sort()).toEqual([1, 2, 3]);
135    expect(graph.truncated).toBe(false);
136  });
137
138  it('maxNodes truncation and maxDepth truncation are both reported via the same flag', async () => {
139    const adjacency: Record<number, number[]> = { 1: [2, 3], 2: [4], 3: [] };
140    adjacency[4] = [];
141    graphOf(adjacency);
142
143    // maxNodes caps discovery before depth would even matter here.
144    const graph = await walkGraph(fakeClient, 1, { maxNodes: 2, maxDepth: 5 });
145
146    expect(graph.nodes.size).toBeLessThanOrEqual(2);
147    expect(graph.truncated).toBe(true);
148  });
149
150  it('never sets truncated due to depth when maxDepth is left unspecified, however deep the graph', async () => {
151    graphOf({ 1: [2], 2: [3], 3: [4], 4: [5], 5: [] });
152
153    const graph = await walkGraph(fakeClient, 1);
154
155    expect([...graph.nodes.keys()].sort()).toEqual([1, 2, 3, 4, 5]);
156    expect(graph.truncated).toBe(false);
157  });
158});
159