calldiff
§ · Nested detail page

调用树展开与结构 diff 深度解析

这一页拆 calltree / infer / diff：从 FunctionIndex 递归展开，到反向边推断受影响入口，再用 LCS 对齐前后调用树。

§ 01 · CALL TREE

调用树先解决递归展开

▸display label 与 loc 分离

src/calltree.ts:5 用 FunctionIndex 拿展示 label，找不到时才补一个 key()；src/calltree.ts:58 则区分根节点定义位置和子节点调用位置。这一差异让 --locs 输出符合 LSP Call Hierarchy 的 fromRanges 思路。

src/calltree.ts · L5-45TypeScript
5function displayCallLabel(key: string, index: FunctionIndex): string {
6  const info = index.get(key);
7  if (info) return info.label;
8  return key.includes("(") ? key : `${key}()`;
9}
10
11function expandSteps(
12  steps: CallStep[],
13  index: FunctionIndex,
14  depth: number,
15  maxDepth: number,
16  visiting: Set<string>,
17): CallNode[] {
18  return steps.map((step) => {
19    if (step.type === "branch") {
20      return {
21        key: step.key,
22        label: step.label,
23        kind: "branch" as const,
24        ...pickLoc(step),
25        children: expandSteps(
26          step.children,
27          index,
28          depth,
29          maxDepth,
30          visiting,
31        ),
32      };
33    }
34    return expandCall(
35      step.key,
36      index,
37      depth,
38      maxDepth,
39      visiting,
40      step.children,
41      step,
42    );
43  });
44}
45

▸visiting 防止循环展开

src/calltree.ts:72 发现当前 key 已在 visiting 中时，会返回带循环标记的节点；src/calltree.ts:86 到 src/calltree.ts:93 则只在进入函数体时 add/delete。这个设计避免递归函数把 CLI 输出拖成无限树。

src/calltree.ts · L46-113TypeScript
46function expandCall(
47  key: string,
48  index: FunctionIndex,
49  depth: number,
50  maxDepth: number,
51  visiting: Set<string>,
52  inlineChildren?: CallStep[],
53  callSite?: { file?: string; line?: number; endLine?: number },
54): CallNode {
55  const label = displayCallLabel(key, index);
56  const info = index.get(key);
57
58  // Root uses the definition start line; every other node uses the call-site in the parent.
59  const loc =
60    depth === 0 && info?.line != null
61      ? pickLoc({ file: info.file, line: info.line })
62      : pickLoc(callSite);
63
64  if (depth >= maxDepth) {
65    return { key, label, kind: "call", ...loc, children: [] };
66  }
67
68  if (!info && !inlineChildren?.length) {
69    return { key, label, kind: "call", ...loc, children: [] };
70  }
71
72  if (info && visiting.has(key)) {
73    // Still expand call-site JSX children; they are not a re-entry into `key`'s body.
74    const callSiteChildren = inlineChildren?.length
75      ? expandSteps(inlineChildren, index, depth + 1, maxDepth, visiting)
76      : [];
77    return {
78      key,
79      label: `${label} ⇄`,
80      kind: "call",
81      ...loc,
82      children: callSiteChildren,
83    };
84  }
85
86  if (info) visiting.add(key);
87  const bodyChildren = info
88    ? expandSteps(info.steps, index, depth + 1, maxDepth, visiting)
89    : [];
90  const callSiteChildren = inlineChildren?.length
91    ? expandSteps(inlineChildren, index, depth + 1, maxDepth, visiting)
92    : [];
93  if (info) visiting.delete(key);
94
95  return {
96    key,
97    label,
98    kind: "call",
99    ...loc,
100    children: [...bodyChildren, ...callSiteChildren],
101  };
102}
103
104/**
105 * Expand a function into a nested call tree by following known definitions.
106 */
107export function buildCallTree(
108  entryKey: string,
109  index: FunctionIndex,
110  maxDepth: number,
111): CallNode {
112  const resolved = resolveEntry(entryKey, index) ?? entryKey;
113  return expandCall(resolved, index, 0, maxDepth, new Set());
§ 02 · INFER

入口推断从反向边开始

▸findAffected 把变化向调用者传播

src/infer.ts:12 构建 callee→callers 反向边，src/infer.ts:28 从 before/after 函数 shape 变化出发，用 BFS 传播到上游调用者。这样即使底层 helper 改了，src/infer.ts:80 也能推断真正值得展示的 exported entrypoint。

src/infer.ts · L12-63TypeScript
12function addReverseEdges(
13  reverse: Map<string, Set<string>>,
14  index: FunctionIndex,
15): void {
16  for (const [caller, fn] of index) {
17    for (const callee of flattenCallKeys(fn.steps)) {
18      let callers = reverse.get(callee);
19      if (!callers) {
20        callers = new Set();
21        reverse.set(callee, callers);
22      }
23      callers.add(caller);
24    }
25  }
26}
27
28function findAffected(
29  before: FunctionIndex,
30  after: FunctionIndex,
31  maxDepth: number,
32): Set<string> {
33  const keys = new Set([...before.keys(), ...after.keys()]);
34  const reverse = new Map<string, Set<string>>();
35  addReverseEdges(reverse, before);
36  addReverseEdges(reverse, after);
37
38  const distance = new Map<string, number>();
39  const queue: string[] = [];
40
41  for (const key of keys) {
42    if (functionShape(before.get(key)) === functionShape(after.get(key))) {
43      continue;
44    }
45    distance.set(key, 0);
46    queue.push(key);
47  }
48
49  for (let i = 0; i < queue.length; i += 1) {
50    const callee = queue[i]!;
51    const nextDistance = distance.get(callee)! + 1;
52    if (nextDistance > maxDepth) continue;
53
54    for (const caller of reverse.get(callee) ?? []) {
55      const previous = distance.get(caller);
56      if (previous !== undefined && previous <= nextDistance) continue;
57      distance.set(caller, nextDistance);
58      queue.push(caller);
59    }
60  }
61
62  return new Set(distance.keys());
63}

▸explicit entry 优先，fallback 再兜底

src/infer.ts:86 明确用户指定 entry 时不再猜；没有 entry 时，src/infer.ts:96 优先筛 affected exported 函数，src/infer.ts:105 才回退到非 exported 受影响函数。这个顺序让输出更像 review summary，而不是内部 helper 清单。

src/infer.ts · L80-108TypeScript
80export function inferEntries(
81  before: FunctionIndex,
82  after: FunctionIndex,
83  explicit: string[],
84  maxDepth: number,
85): string[] {
86  if (explicit.length > 0) {
87    const entries: string[] = [];
88    for (const entry of explicit) {
89      const key = resolveEntry(entry, after) ?? resolveEntry(entry, before);
90      if (!key) throw new Error(`Entrypoint not found: ${entry}`);
91      if (!entries.includes(key)) entries.push(key);
92    }
93    return entries;
94  }
95
96  const affected = [...findAffected(before, after, maxDepth)].filter(
97    (key) => !key.startsWith("new "),
98  );
99  const exported = affected.filter((key) =>
100    Boolean(before.get(key)?.exported || after.get(key)?.exported),
101  );
102  const entries = changedKeys(exported, before, after, maxDepth);
103  if (entries.length > 0) return entries;
104
105  const checked = new Set(exported);
106  const fallback = affected.filter((key) => !checked.has(key));
107  return changedKeys(fallback, before, after, maxDepth);
108}
§ 03 · DIFF

结构 diff 如何保持可读顺序

▸LCS 对齐 children

src/diff.ts:62 建 dp 表，src/diff.ts:82 之后按 before/after key 走 LCS。相同节点递归 diff，不同节点标 added/removed；这让 refactor 后的新树顺序被保留，同时仍能显示删除的旧调用。

src/diff.ts · L1-109TypeScript
1import { pickLoc } from "./loc.js";
2import type { CallNode, DiffNode } from "./types.js";
3
4/**
5 * Structural tree diff keyed by call identity.
6 * Children are aligned with LCS so output order stays close to the "after" tree.
7 */
8export function diffTrees(before: CallNode, after: CallNode): DiffNode {
9  return diffNode(before, after);
10}
11
12function diffNode(before: CallNode | null, after: CallNode | null): DiffNode {
13  if (before && after) {
14    return {
15      key: after.key,
16      label: after.label,
17      kind: after.kind ?? before.kind,
18      ...pickLoc(after.file ? after : before),
19      status: "same",
20      children: diffChildren(before.children, after.children),
21    };
22  }
23
24  if (after) {
25    return {
26      key: after.key,
27      label: after.label,
28      kind: after.kind,
29      ...pickLoc(after),
30      status: "added",
31      children: after.children.map(markTree("added")),
32    };
33  }
34
35  if (before) {
36    return {
37      key: before.key,
38      label: before.label,
39      kind: before.kind,
40      ...pickLoc(before),
41      status: "removed",
42      children: before.children.map(markTree("removed")),
43    };
44  }
45
46  throw new Error("diffNode called with no trees");
47}
48
49function markTree(status: "added" | "removed") {
50  return function mark(node: CallNode): DiffNode {
51    return {
52      key: node.key,
53      label: node.label,
54      kind: node.kind,
55      ...pickLoc(node),
56      status,
57      children: node.children.map(mark),
58    };
59  };
60}
61
62function diffChildren(before: CallNode[], after: CallNode[]): DiffNode[] {
63  const n = before.length;
64  const m = after.length;
65  const dp: number[][] = Array.from({ length: n + 1 }, () =>
66    Array.from({ length: m + 1 }, () => 0),
67  );
68
69  for (let i = n - 1; i >= 0; i--) {
70    for (let j = m - 1; j >= 0; j--) {
71      if (before[i]!.key === after[j]!.key) {
72        dp[i]![j] = dp[i + 1]![j + 1]! + 1;
73      } else {
74        dp[i]![j] = Math.max(dp[i + 1]![j]!, dp[i]![j + 1]!);
75      }
76    }
77  }
78
79  const result: DiffNode[] = [];
80  let i = 0;
81  let j = 0;
82  while (i < n && j < m) {
83    if (before[i]!.key === after[j]!.key) {
84      result.push(diffNode(before[i]!, after[j]!));
85      i += 1;
86      j += 1;
87    } else if (dp[i + 1]![j]! >= dp[i]![j + 1]!) {
88      result.push(diffNode(before[i]!, null));
89      i += 1;
90    } else {
91      result.push(diffNode(null, after[j]!));
92      j += 1;
93    }
94  }
95  while (i < n) {
96    result.push(diffNode(before[i]!, null));
97    i += 1;
98  }
99  while (j < m) {
100    result.push(diffNode(null, after[j]!));
101    j += 1;
102  }
103  return result;
104}
105
106export function treeHasChanges(node: DiffNode): boolean {
107  if (node.status !== "same") return true;
108  return node.children.some(treeHasChanges);
109}
Function shape changed → affected entries → build before tree + after tree → diffChildren(LCS) → render +/- ASCII
§ 04 · TESTS

测试直接覆盖输出形状

▸helper refactor 样例

test/callstack-diff.test.ts:3 的测试非常贴近产品定位：原来三个调用被重构到 PiService.getServices，期望输出同时显示删除的旧子调用和新增 helper 的嵌套结构。它验证了 src/diff.ts:49 的 markTree 与 src/render.ts:121 的 renderDiff 能正确配合。

test/callstack-diff.test.ts · L3-67TypeScript
3test("refactors calls into a helper, preserves if/else branch labels", ({
4  expectCallstack,
5}) => {
6  expectCallstack(
7    `
8      export class PiService {
9        static createAgentSession(options: { sessionId?: string }) {
10    -     AuthStorage.create();
11    -     new ModelRegistry();
12    -     createCodingTools();
13    +     const services = PiService.getServices();
14    +     services.boot();
15          if (!options.sessionId) {
16            SessionManager.create();
17          } else {
18            SessionManager.open(options.sessionId);
19          }
20        }
21    +
22    +   static getServices() {
23    +     SettingsManager.create();
24    +     AuthStorage.create();
25    +     new ModelRegistry();
26    +     createCodingTools();
27    +     return { boot() {} };
28    +   }
29      }
30
31      class AuthStorage {
32        static create() {}
33      }
34
35      class ModelRegistry {
36        constructor() {}
37      }
38
39      class SessionManager {
40        static create() {}
41        static open(_id: string) {}
42      }
43    +
44    + class SettingsManager {
45    +   static create() {}
46    + }
47
48      function createCodingTools() {}
49    `,
50    "PiService.createAgentSession",
51  ).toEqual(`
52      PiService.createAgentSession(options)
53    - ├─ AuthStorage.create()
54    - ├─ new ModelRegistry()
55    - ├─ createCodingTools()
56    + ├─ PiService.getServices()
57    + │  ├─ SettingsManager.create()
58    + │  ├─ AuthStorage.create()
59    + │  ├─ new ModelRegistry()
60    + │  └─ createCodingTools()
61    + ├─ services.boot()
62      ├─ if (!options.sessionId)
63         └─ SessionManager.create()
64      └─ else
65         └─ SessionManager.open(_id)
66  `);
67});
§ 05 · RISKS

图模型边界

▸key 冲突和动态派发

src/extract.ts:92 的 buildIndex 以 key 去重，src/calltree.ts:125 在多个后缀匹配时排序取一个。这个策略简单稳定，但跨文件同名函数、interface dispatch 或动态对象方法仍可能被简化。

另一个取舍在 entry 推断：src/infer.ts:41 从所有 key 比较函数 shape，src/infer.ts:49 用队列向上游扩散，src/infer.ts:96 再过滤掉 new constructor，src/infer.ts:102 最终只保留确实有树变化的 entry。它偏向 review 摘要，而不是完整 call graph dump。

src/extract.ts · L92-107TypeScript
92export function buildIndex(functions: FunctionInfo[]): FunctionIndex {
93  const index: FunctionIndex = new Map();
94  for (const fn of functions) {
95    if (!index.has(fn.key)) {
96      index.set(fn.key, fn);
97    }
98    if (fn.key.endsWith(".constructor")) {
99      const className = fn.key.slice(0, -".constructor".length);
100      const newKey = `new ${className}`;
101      if (!index.has(newKey)) {
102        index.set(newKey, { ...fn, key: newKey, label: `new ${className}()` });
103      }
104    }
105  }
106  return index;
107}
Generated · 2026-08-11Source · tanishqkancharla/calldiff