嵌套插值变量解析的算法与数据结构设计问询

问题背景 #

给定嵌套插值字符串：

foo{a{x}-{y}}-{baz{one}-{two}}-foo{c}

需要实现依赖驱动的逐步求值，遵循以下逻辑：

• 先等待叶子变量x、y、one、two、c全部解析完成
• 当x和y均就绪时，立即解析a{x}-{y}
• 当one和two均就绪时，立即解析baz{one}-{two}
• 当a{x}-{y}、baz{one}-{two}和c全部就绪时，完成顶层表达式的最终求值

核心数据模型设计 #

采用树状观察者模型，每个节点跟踪自身依赖的就绪状态，分为两类节点：

1. 插值节点（描述字符串结构） #

// 区分叶子变量节点和复合插值节点
type InterpolNode = 
  // 叶子变量节点：如{x}中的x
  { type: 'variable'; name: string } 
  // 复合插值节点：如a{x}-{y}，包含模板和子依赖
  | { type: 'compound'; template: string; children: InterpolNode[] };

2. 观察者节点（跟踪就绪状态） #

每个观察者节点关联一个插值节点，负责管理依赖计数和触发求值：

type ObserverNode = {
  node: InterpolNode;
  parent?: ObserverNode;
  remainingDependencies: number; // 未就绪的子依赖数量
  values: any[]; // 存储已就绪的子节点值
  onReady: (value: any) => void; // 自身就绪后的回调（通知父节点）
};

核心算法实现 #

步骤1：解析字符串构建插值树 #

递归解析输入字符串，拆分静态文本与插值块，生成对应的InterpolNode树：

function parseInterpolString(input) {
  // 简化实现：返回对应输入的树结构
  return {
    type: 'compound',
    template: "foo{0}-{1}-foo{2}",
    children: [
      {
        type: 'compound',
        template: "a{0}-{1}",
        children: [
          { type: 'variable', name: 'x' },
          { type: 'variable', name: 'y' }
        ]
      },
      {
        type: 'compound',
        template: "baz{0}-{1}",
        children: [
          { type: 'variable', name: 'one' },
          { type: 'variable', name: 'two' }
        ]
      },
      { type: 'variable', name: 'c' }
    ]
  };
}

步骤2：构建观察者树并绑定回调 #

遍历插值树，为每个节点创建观察者，同时维护叶子变量到观察者的映射：

function buildObserverTree(rootNode, onRootReady) {
  const variableObservers = new Map(); // 叶子变量 -> 对应的观察者列表

  function traverse(node, parent, onNodeReady) {
    const observer = {
      node,
      parent,
      remainingDependencies: node.type === 'compound' ? node.children.length : 0,
      values: [],
      onReady: onNodeReady || (() => {})
    };

    if (node.type === 'variable') {
      // 叶子变量：加入映射表
      if (!variableObservers.has(node.name)) {
        variableObservers.set(node.name, []);
      }
      variableObservers.get(node.name).push(observer);
    } else if (node.type === 'compound') {
      // 复合节点：为每个子节点绑定就绪回调
      node.children.forEach((child, index) => {
        const childOnReady = (value) => {
          observer.values[index] = value;
          observer.remainingDependencies--;
          // 所有子依赖就绪，触发自身求值
          if (observer.remainingDependencies === 0) {
            const computedValue = evaluateTemplate(observer.node.template, observer.values);
            observer.onReady(computedValue);
          }
        };
        traverse(child, observer, childOnReady);
      });
    }

    return observer;
  }

  // 从根节点开始遍历，绑定最终回调
  traverse(rootNode, undefined, onRootReady);
  return variableObservers;
}

// 求值复合节点模板：替换占位符为子节点值
function evaluateTemplate(template, values) {
  return template.replace(/\{(\d+)\}/g, (_, idx) => values[Number(idx)]);
}

步骤3：事件驱动的就绪触发 #

通过markVariableReady函数模拟变量就绪事件，自动触发链式求值：

// 初始化流程
const inputStr = "foo{a{x}-{y}}-{baz{one}-{two}}-foo{c}";
const rootNode = parseInterpolString(inputStr);

// 根节点就绪后的最终回调
function onRootReady(finalValue) {
  console.log("最终结果：", finalValue);
}

const variableObservers = buildObserverTree(rootNode, onRootReady);

// 标记变量就绪的函数
function markVariableReady(varName, value) {
  const observers = variableObservers.get(varName);
  if (!observers) return;
  observers.forEach(obs => obs.onReady(value));
}

// 模拟变量就绪顺序
markVariableReady('y', 'Y');
markVariableReady('c', 'C');
markVariableReady('x', 'X'); // x和y就绪，触发a{x}-{y}求值
markVariableReady('one', '1');
markVariableReady('two', '2'); // one和two就绪，触发baz{one}-{two}求值，随后根节点所有依赖就绪，输出最终结果

核心逻辑说明 #

1. 依赖跟踪：每个复合节点通过remainingDependencies计数，子节点就绪时递减，计数为0时触发自身求值
2. 回调链式触发：子节点的onReady回调会自动通知父节点更新状态，形成从叶子到根的求值链
3. 多依赖共享：同一个叶子变量可以被多个复合节点依赖，通过variableObservers映射表批量通知所有关联观察者

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