如何为树节点创建高效查找结构，实现AST延迟解析且不污染原AST

问题背景 #

正在实现一门自定义编程语言，遇到AST延迟解析的问题：AST中存在waiting类型节点，这类节点对应的变量需在后续程序激活/设置后才能完成解析。当后续匹配到对应变量时，需要将AST中所有匹配的waiting节点替换为变量值。

示例场景 #

初始AST结构 #

example {foo}
  {bar}
    hello {world}
      baz
  asdf {another}

变量设置后的AST（执行world = "earth"） #

example
  user
  {bar}
    hello
      earth
      baz
  asdf
    {another}

完全饱和的最终AST #

example
  user
  BAR
    hello
      earth
      baz
  asdf
    random

核心需求 #

1. 建立变量名到AST节点的映射，避免每次处理新变量时遍历整棵树
2. 为节点及其父节点维护计数器，标记节点是否“完成”
3. 不污染原始AST，通过原始AST与解析后AST的映射保留原对象

高效实现方案 #

1. 预遍历初始化映射与计数器 #

一次性遍历原始AST，完成以下初始化工作：

• 变量映射表：记录每个变量名对应的所有waiting节点在解析后AST中的位置（目标节点、属性名/索引），后续设置变量时直接通过映射表定位，无需重复遍历AST
• 节点映射表：建立原始AST节点到解析后AST节点的一一映射，确保原始AST不被修改
• 待处理计数器：为每个解析后AST节点维护pendingCount（单独用Map存储，不污染节点），记录该节点及其子节点中未解析的waiting节点数量

初始化代码示例

// 变量名 -> 等待替换的节点位置数组
const waitingMap = new Map();
// 原始节点 -> 解析后节点的映射
const nodeMap = new Map();
// 解析后节点 -> 待处理waiting节点数量
const pendingCountMap = new Map();
// 解析后节点 -> 父节点的映射
const parentMap = new Map();

// 深度克隆原始AST并初始化各类映射
function cloneAndInit(originalNode, parent = null) {
  const clonedNode = { ...originalNode };
  nodeMap.set(originalNode, clonedNode);
  if (parent) parentMap.set(clonedNode, parent);

  let pendingCount = 0;

  // 处理当前节点的name属性是否为waiting节点
  if (clonedNode.name?.type === 'waiting') {
    const varName = clonedNode.name.value;
    if (!waitingMap.has(varName)) waitingMap.set(varName, []);
    waitingMap.get(varName).push({ targetNode: clonedNode, prop: 'name' });
    pendingCount++;
  }

  // 处理子节点
  if (clonedNode.children) {
    clonedNode.children = clonedNode.children.map((child, index) => {
      const clonedChild = cloneAndInit(child, clonedNode);
      pendingCount += pendingCountMap.get(clonedChild) || 0;
      return clonedChild;
    });
  }

  pendingCountMap.set(clonedNode, pendingCount);
  return clonedNode;
}

// 生成解析后AST的基础结构
const parsedAst = ast.map(root => cloneAndInit(root));

2. 变量设置与节点更新 #

当变量被设置时，通过waitingMap快速找到所有待替换的节点位置，完成替换后向上更新父节点的pendingCount，当计数器归零时标记节点为“完成”。

变量处理代码示例

function setVariable(varName, value) {
  if (!waitingMap.has(varName)) return;

  // 将变量值转换为符合AST结构的节点
  const resolvedNode = typeof value === 'string' 
    ? { type: 'literal', value } 
    : value;

  const targets = waitingMap.get(varName);
  targets.forEach(({ targetNode, prop }) => {
    // 替换waiting节点
    targetNode[prop] = resolvedNode;

    // 向上遍历父节点，更新待处理计数器
    let currentNode = targetNode;
    while (currentNode) {
      const currentCount = pendingCountMap.get(currentNode);
      const newCount = currentCount - 1;
      pendingCountMap.set(currentNode, newCount);

      // 计数器归零时标记节点完成
      if (newCount === 0) {
        currentNode.isCompleted = true; // 或用单独的completedMap存储
      }
      currentNode = parentMap.get(currentNode);
    }
  });

  // 移除已处理的变量，避免重复操作
  waitingMap.delete(varName);
}

方案优势 #

• 性能高效：仅需遍历原始AST一次，后续变量处理为O(k)复杂度（k为变量对应的waiting节点数量）
• 无原始AST污染：所有修改均在克隆后的AST上进行，原始AST完全保留
• 状态清晰：通过独立的计数器Map维护节点完成状态，不侵入AST节点结构

内容的提问来源于stack exchange，提问作者Lance Pollard