1import type { EvmClient } from '../client/EvmClient';
2import { multicallGetSubscriptions } from './contract';
3import type { SubscriptionGraph, SubscriptionNode, WalkOptions } from './types';
4
5// Balances RPC payload size against round-trip count (spec §6, unchanged).
6const BATCH_SIZE = 50;
7const DEFAULT_MAX_WALK_NODES = 1000;
8
9/**
10 * Off-chain BFS over the on-chain subscription graph, starting from
11 * rootUserId. Mirrors the on-chain Pass 1 discovery from
12 * SubscriptionManager's `_calculateDP` — discovers nodes only, computes no
13 * credits. Algorithm unchanged from the original spec §6; only the module
14 * boundary and read client moved. Takes a concrete EvmClient (not
15 * ReadOnlyDomainAPI) because multicall batching needs `.publicClient` (§15.4).
16 */
17export async function walkGraph(client: EvmClient, rootUserId: number, opts?: WalkOptions): Promise<SubscriptionGraph> {
18  const maxWalkNodes = opts?.maxNodes ?? DEFAULT_MAX_WALK_NODES;
19  const maxDepth = opts?.maxDepth;
20
21  const visited = new Set<number>([rootUserId]);
22  const depth = new Map<number, number>([[rootUserId, 0]]);
23  const nodes = new Map<number, SubscriptionNode>();
24  const queue: number[] = [rootUserId];
25  // A depth cutoff drops a node before it's ever visited/queued, so — unlike
26  // the maxNodes cap — it leaves nothing behind in `queue` for `truncated` to
27  // detect. Tracked separately so a depth-limited walk still reports itself
28  // as incomplete.
29  let depthLimited = false;
30
31  while (queue.length > 0 && visited.size < maxWalkNodes) {
32    const batch = queue.splice(0, BATCH_SIZE);
33    const results = await multicallGetSubscriptions(client, batch);
34
35    for (const userId of batch) {
36      const subs = results.get(userId) ?? [];
37      nodes.set(userId, { userId, subscriptions: subs });
38
39      for (const sub of subs) {
40        if (visited.has(sub) || visited.size >= maxWalkNodes) continue;
41        const nextDepth = (depth.get(userId) ?? 0) + 1;
42        if (maxDepth !== undefined && nextDepth > maxDepth) {
43          depthLimited = true;
44          continue;
45        }
46        visited.add(sub);
47        depth.set(sub, nextDepth);
48        queue.push(sub);
49      }
50    }
51  }
52
53  return { rootUserId, nodes, truncated: queue.length > 0 || depthLimited };
54}
55