如何使用VS Code的语言API在TypeScript中构建代码图表

即使我们在查看来电信息时发现了这种关联关系，也是如此。

稳定的符号标识符

函数名称并不具有唯一性。一个项目中很可能会存在以下情况：

// users.ts
function save() {}

以及：

payments.ts
function save() {}

因此，我们需要根据符号在代码中的位置来为其生成唯一的标识符。

function idOf(
  uri: vscode.Uri,
  pos: vscode.Position
): string {
  return `${uri.toString()}#${pos.line}:${pos.character}`;
}

对于那些属于调用层次结构中的元素，我们可以使用它们的selectionRange属性来获取标识符：

function itemId(
  item: vscode.CallHierarchyItem
): string {
  return idOf(
    item.uri,
    item_selectionRange.start
  );
}

使用selectionRange之所以有用，是因为它能够识别符号的名称，而不是整个代码段或声明范围。这种稳定的标识符是实现去重功能的基础。如果通过代码图中的不同路径发现了同一个函数，我们就可以确定这些发现实际上都是指向同一个节点。

4. 查找函数和方法

构建代码图的第一步就是找出当前激活文件中所有的符号。VS Code通过以下方式提供了对这些符号的访问接口：

vscode.executeDocumentSymbolProvider

我们可以这样调用它：

/*
 * 使用VS Code内置的语言服务来获取文档中的所有符号，而无需自行解析代码。这样一来，我们就能得到文档中的方法、函数和变量等信息。
 */
async function getDocumentSymbols(
  uri: vscode Uri
): Promise<vscode.DocumentSymbol[]>> {

  /*
   * `vscode.executeDocumentSymbolProvider`会将分析任务委托给为该文档所支持的语言注册的语言服务提供商。
   */

  const result =
    await vscodecommands.executeCommand<
      vscode.DocumentSymbol[] | undefined
    >>(
      'vscodeexecuteDocumentSymbolProvider',
      uri
    );

  // 如果没有找到任何符号，就返回一个空数组。
  return result ?? [];
}

返回出来的这些符号会形成一个层次结构。例如：

我们需要遍历这个层次结构，并收集那些可能代表可执行代码的符号。

// 判断某个符号是否属于可执行的节点。
const isCallableKind = (
  kind: vscode.SymbolKind,
  includeConstructors: boolean
) =>
  kind === vscode.SymbolKind.Function ||
  kind === vscode.SymbolKind.Method ||
  (
    includeConstructors && kind === vscode.SymbolKind.Constructor
  );

我们可以递归地遍历符号树：

变量值得被重点考虑，因为赋值给变量的函数可能会被语言工具以不同的方式呈现出来。例如：

即使某个符号参与了调用层次结构，它仍然可能被识别为变量。

5. 在指定位置查找符号

当用户打开某个方法的代码图时，我们需要确定哪个符号对应着光标所在的位置。由于文档符号具有层次结构，我们可以递归地找到包含该位置的最底层符号。

这一机制使得编辑器与代码图能够顺利连接起来：用户在源文件中选定一个位置，系统会将该位置对应到某个符号，然后再将该符号转化为调用层次结构中的相应节点。

6. 解析调用层次结构

调用层次结构的API分为两个阶段来执行。首先：

然后：

我们可以按照以下方式准备这些数据：

一旦我们获得了某个元素，就可以查询调用它的符号：

或者，也可以查询被该元素调用的符号：

如果我们有这样的图结构：

并且我们查询 processPayment 的调用者，那么语言 API 会返回：

我们将这些结果整理成如下形式：

因此，同样的图结构既可以用来表示调用关系，也可以用来表示被调用关系。

7. 构建符号注册表

在遍历这个图结构的过程中，同一个符号可能会多次出现。例如：

我们应该为 C 创建一个节点，而不是三个。注册表正好起到了去除重复数据的作用。

8. 使用广度优先搜索遍历图结构

一次调用关系查询只能让我们了解图中的一层连接关系。而一个有用的代码图结构需要展示多层的关联关系。例如，A()调用了B()，但这并不能告诉我们B()接下来会调用哪些函数。

为了构建出一个有用的代码图结构，我们需要反复追踪这些调用关系，比如A → B → C → D。每次这样的查询都会使图的结构扩展一层，因此我们需要像广度优先搜索这样的遍历策略，才能高效地探索多层的连接关系。

举个例子：

// 假设这个图结构包含4层连接关系
A --> B --> C --> D --> E

如果我们从A开始遍历，并且指定遍历深度为3层，那么我们期望得到的结果应该是：

深度0: A
深度1: B
深度2: C
深度3: D

广度优先搜索是一种非常适合这种需求的方法，因为这个图结构本身就是按照调用层次来组织的。在遍历过程中，会始终保持一个“当前边界”节点：

当前边界节点
      ↓
发现相邻节点
      ↓
下一个边界节点
      ↓
发现相邻节点

其基本实现代码如下：

const walk = async (
  start: Handle,
  direction: 'incoming' | 'outgoing',
  limit: number
) => {
  // 从给定的节点开始，逐层遍历代码图结构。
  let frontier: Handle[] = [start];

  for (
    let depth = 0;
    depth < limit && frontier.length > 0;
    depth++;
  ) {
    // 同时处理多层的查询任务，但并发数量最多为6个。
    const results =
      await mapLimit(
        frontier,
        6,
        handle =>
          oneHop(
            handle,
            direction
          )
      );

    const next: Handle[] = [];

    frontier.forEach(
      (handle, index) => {
        for (
          const other of results[index]
        ) {
          // 在添加新的连接关系之前，先将其加入注册表中。
          if (!registry.has(other.node.id)) {
            registry.register(
              other.node.uri,
              other.node.name,
              other.node.kind,
              other.node.pos
            );
          }

          // 保持图中调用关系的方向不变。
          if (direction === 'outgoing') {
            addEdge(handle.node.id, other.node.id);
          } else {
            addEdge(other.node.id, handle.node.id);
          }

          next.push(other);
        }
      }
    );

    // 从这一层发现的节点继续进行遍历。
    frontier = next;
  }
};

mapLimit这个辅助函数能够有效控制同时进行的语言服务器请求数量：

async function mapLimit(  
  items: T[],  
  limit: number,  
  fn: (item: T) => Promise,  
): Promise {  
  // 同时最多执行 `limit` 个异步操作。  
  const results = new Array(items.length);  

  let next = 0;  

  // 创建一些工作线程，这些线程会共享下一个可处理的元素。  
  const workers = Array.from(  
    {  
      length: Math.min(limit, items.length),  
    },  
    async () => {  
      while (next < items.length) {  
        const index = next++;  
        results[index] = await fn(items[index]);  
      }  
    }  
  );  
  await Promise.all(workers);  
  return results;  
}

关键的区别在于：BFS只涉及局部计算，而解析符号通常需要让VS Code的语言工具来执行实际的处理工作。

对于我们访问的每一个符号，Code Graph View可能都需要向语言服务查询其相关的调用信息。这些查询操作可能会涉及到解析源文件、解析符号以及与语言服务器进行通信。随着图结构的不断扩大，这类请求的数量也会随之增加。

因此，尽管遍历本身很简单，但如果这些查询操作是顺序执行的，那么整个过程的速度就会变得很慢。mapLimit函数通过允许多个独立的语言工具请求同时运行来解决这个问题，同时也对并发数量进行了限制，以防止语言服务被过度负担。

9. 处理循环结构

实际的代码结构并不是树形结构，而是图结构。因此，循环的存在是正常的。

例如：

如果使用简单的递归遍历方式，那么这个过程可能会无限地进行下去。因此，我们需要记录已经访问过哪些节点。但这里有一个细节需要注意：仅仅使用Set结构来存储已访问过的节点是不够的，因为如果同一个节点可以从不同的深度被访问到，那么这种数据结构就无法准确反映这一情况。相反，我们应该记录在访问某个节点时还剩下多少层需要遍历。

Set

因此，我们可以使用Map结构来存储每个节点的剩余遍历深度：

const explored = new Map();

然后，我们可以这样编写代码来跟踪每个节点的剩余遍历深度：

// 记录访问某个节点时还剩下多少层需要遍历。
const key = `${direction}:${node.id}`;
if ((explored.get(key) ?? -1) < remainingDepth) {
  // 只有当当前层的遍历能够探索到比之前更深的层次时，才重新访问该节点。
  explored.set(key, remainingDepth);
  next.push(node);
}

这样做的优点是：如果我们之前发现某个节点还需要再走一层才能到达，但后来发现实际上只需要走三层就可以到达，那么我们就可以再次访问这个节点。这种处理方式比简单地将节点标记为“已访问”要准确得多。

10. 限制图的规模

图的规模可能会迅速扩大。一个关联度很高的函数可能会拥有数十个调用者，而这些调用者各自也可能又有几十个其他调用者。因此，图构建工具应当设置明确的限制条件。

例如：

const MAX_SYMBOLS = 400;
const MAX_CALLS_PER.Symbol = 50;
const HOP_CONCURRENCY = 6;

如果图的规模超过了这些限制，我们不应该假装图已经完整构建完毕。相反，应该采取以下措施：

let truncated = false;

然后执行如下代码：

if (
  registry.size >= MAX_SYMBOLS
) {
  truncated = true;
  continue;
}

这样，最终的GraphData就可以向用户界面提示：

此图已被截断。

这样做总比让代码库规模过大而导致扩展功能无法正常使用要好得多。

11. 过滤文件

语言服务器可能会返回一些与我们正在分析的应用程序无关的文件信息。这些文件可能是构建过程中产生的文件，或者是由于依赖关系安装或特定语言的构建/运行时操作而生成的输出文件。例如，一个TypeScript项目可能会包含以下路径：

node_modules

而一个Python项目则可能包含：

site-packages

在将这些文件添加到图中之前，我们可以先对它们进行过滤。

const DEPENDENCY_DIRS =
  /\/(node_modules|vendor|target|\.venv|venv|site-packages|__pycache__|build|obj|\.dart_tool)\//;

function isWorkspaceFile(
  uri: vscode.Uri
): boolean {
  if (
    uri.scheme !== 'file' ||
    DEPENDENCY_DIRS.test(uri.path)
  ) {
    return false;
  }
  return !!vscode/workspace
    .getWorkspaceFolder(uri);
}

这样就能确保图只包含用户工作区中的文件信息。这也体现了语言智能与应用程序行为之间的重要区别：语言服务器告诉我们它能够解析哪些信息，而图的构建工具则负责决定哪些内容应该被纳入图中。

12. 为什么有些边会默默地消失

在规模庞大的图中，一些明明存在相互调用关系的函数最终可能会显示为没有连接关系，而且也不会有任何错误提示。问题的根源在于：CallHierarchyItem对象是与语言服务器的状态相关联的。如果该状态变得过时，那么查询其调用者或被调用者时可能会得到一个空数组。从图构建工具的角度来看，这种情况就相当于某个函数根本没有调用者。

在VS Code的实现中，调用关系信息只会为最近的一定数量的请求保留。我们的爬取程序也可以同时进行多次查询，因此在一些较旧的查询结果还在被处理的过程中，新的数据可能会覆盖它们。针对这个问题，图构建工具采用了三种解决方法。

1. 它存储的是普通数据，而非实时更新的信息。

每个功能都通过一个NodeRef来表示，其中包含了该功能的ID、URI、名称、类型以及位置信息。一步查询的结果也会被缓存为NodeRef形式。这样，在需要时，我们就能利用这些信息重新构建相应的调用关系结构。

interface NodeRef {
  id: string;
  uri: vscode Uri;
  name: string;
  kind: vscode.SymbolKind;
  pos: vscode.Position;
}

2. 它会记录每个已准备好的数据项的创建时间。

每当有一个新的调用关系结构项被生成时，一个全局的epoch计数器就会增加。每个数据项都会记录下其创建时的时间戳。如果某个数据项已经变得过于陈旧，爬虫会从已缓存的NodeRef中重新生成一个新的数据项。

3. 它会重新尝试获取那些返回空结果的数据项。

oneHop函数的简化版本如下所示：

const SESSION_WINDOW = 7;

// 如果必要，会刷新过期的语言工具引用并重试一次。
for (let attempt = 0; attempt < 2; attempt++) {
  const stale =
    !current.item ||
    epoch - current_epoch > SESSION_WINDOW;

  if (stale) {
    // 在使用过期的CallHierarchyItem之前，先重新解析相关符号。
    const fresh = await prepareFresh(
      current.node.uri,
      current.node.pos
    );

    if (!fresh) {
      return [];
    }

    current = fresh;
  }

  const items =
    await lookup(
      current.item!,
      direction
    );

  // 如果获取到的结果为空，就将其标记为无效并重试一次。
  if (
    items.length === 0 && attempt === 0 && epoch - current_epoch > SESSION_WINDOW
  ) {
    current = {
      node: current.node,
      epoch: -1,
    };

    continue;
  }

  // 将解析得到的关系信息缓存起来，以避免重复进行语言工具查询。
  hopCache.set(key, {
    nodes: items.map(refOf),
    at: Date.now(),
  });

  return items.map(child => ({
    node: refOf(child),
    item: child,
    epoch: current_epoch,
  }));
}

在这里，lookup实际上是之前提到的vscode.provideIncomingCalls或vscode.provideOutgoingCalls命令的简写形式。至于具体的会话限制值，这属于VS Code的内部实现细节，并非扩展程序必须依赖的因素。因此，爬虫并不假定这种限制总是存在；SESSION_WINDOW这个数值只是为我们提供了一个用于刷新旧数据项的保守阈值而已。

这种方式可以减少信息丢失的情况，但仍然无法保证能够得到一个完整的关联图谱。语言工具仍有可能返回不完整的信息，或者无法解析某些关系。

这一原则其实适用于所有语言服务API：应该存储那些能够用来重新构建某个对象所需的信息，而不是对象本身。对于因数据过期而返回的空结果，应将其视为“未知状态”，而不能直接认为其确实不存在。

13. 将图表连接到Web视图

一旦图表生成完成，扩展程序就需要一个地方来显示它。VS Code的Web视图正是为此而设计的。

扩展程序会创建相应的面板：

const panel =
  vscode.window.createWebviewPanel(
    'codeGraphView',
    'Code Graph',
    vscode.ViewColumn.Beside,
    {
      enableScripts: true,
      retainContextWhenHidden: true,
    }
  );

图表会以可序列化的数据形式被发送到Web视图：

panel.webview.postMessage({
  command: 'graphData',
  data: graphData,
});

然后Web视图就可以接收这些数据并进行显示：

window.addEventListener(
  'message',
  event => {
    const message =
      event.data;

    if (
      message-command !==
      'graphData'
    ) {
      return;
    }

    renderGraph(
      message.data
    );
  }
);

至此，与语言服务器相关的工作就已经完成了。

我们原本将源代码转化为符号及其关联关系，然后再将其转换为GraphData格式。现在，可视化层就可以利用这些数据来生成图表了。

像ELK这样的工具也可以用来计算图表中各元素的位置，而不会影响到图表的生成逻辑。

14. 测试图表生成器

如果每次测试都需要运行VS Code实例并使用真实的语言服务器，那么测试这类扩展程序就会变得相当困难。一种更好的方法是将图表生成逻辑与VS Code本身分离出来。实际上，爬取器只需要执行以下几项操作即可：

prepareCallHierarchy
provideIncomingCalls
provideOutgoingCalls

我们可以为这些命令创建模拟实现。例如：

const sessions = new Map();

let sessionCounter = 0;

async function executeCommand(
  command,
  ...args
) {
  // 模拟VS Code在解析符号时创建会话的过程。
  if (
    command ===
    'vscode.prepareCallHierarchy'
  ) {
    const id =
      'session-' +
      ++sessionCounter;

    sessions.set(id, true);

    return [
      createFakeItem(
        args,
        id
      ),
    ];
  }

  // 模拟那些依赖于有效会话的调用操作。
  if (
    command ===
      'vscode.provideIncomingCalls' ||
    command ===
      'vscode.provideOutgoingCalls'
  ) {
    const item = args[0];

    // 如果该调用属于已过期的会话，就返回空数组。
    if (
      !sessions.has(
        item.sessionId
      )
    ) {
      return [];
    }

    return getFakeCalls(
      item
    );
  }
}

这种模拟机制可以用来处理诸如会话过期之类的边缘情况。需要注意的是，如果这些模拟实现使用了特定的会话限制条件，那么这应该仅仅被视为一种测试模型，而不能自动被视为VS Code官方API的承诺或保证。

flowchart LR
    A[A] --> B[B]
    A --> C[C]
    B --> D[D]
    C --> D
    D --> E[E]

15. 代码图表的局限性

• 动态调度

• 反射机制

• 依赖注入

• 事件发射器

• 回调函数

• 运行时生成的代码

• 特定框架的行为特性

eventEmitter.on(
  'payment_completed',
  handlePayment
);

结论

文档 -> 文档符号 -> 调用层次结构 -> 图表节点与边关系 -> 广度优先搜索遍历 -> 图表数据 -> 可视化展示

我根据这些资料制作了一个可正常使用的版本，访问地址为：https://github.com/otobongfp/code-graph-view。

我很期待看到大家能够利用这些图表创造出哪些有趣的东西，从而为软件工程的发展做出贡献。