zh CN Token 遍历 - chiba233/yumeDSL GitHub Wiki

Token 遍历

处理器工具函数 | 源码位置追踪

解析器给你一棵 token 树，但光有树还不够——你得能逛这棵树。 这个模块提供三个工具：只读的 walkTokens（看一遍）、不可变的 mapTokens（变一棵新的）、以及快捷的 filterTokens（做树裁剪）。

架构一览

                    TextToken[]
                        │
           ┌────────────┼────────────┐
           ▼            ▼            ▼
      walkTokens   mapTokens   filterTokens
    （只读遍历）  （不可变变换）（基于 mapTokens）
           │            │            │
      前序 DFS     后序 DFS     后序 DFS
   父 → 子 → 兄弟  子先映射     保留 / 删除
           │       → 再到父
           ▼            ▼            ▼
     副作用回调    全新 TextToken[]  过滤后的树

一句话总结：

  • walkTokens = 带着笔记本逛博物馆，只看不摸
  • mapTokens = 复印一份画，想改哪幅改哪幅，原件不动
  • filterTokens = 在复印件上把不想要的部分裁掉，剩下的画仍保持原来的挂法

walkTokens(tokens, visitor)

function walkTokens(tokens: TextToken[], visitor: WalkVisitor): void

深度优先前序遍历——先看父节点，再递归进子节点。纯副作用，不会改动树。

visitor 的两种写法

// 写法一：通用函数——每个 token 都会调用
walkTokens(tokens, (token, ctx) => {
    console.log(token.type, ctx.depth);
});

// 写法二：按类型分发——只关心你感兴趣的类型
walkTokens(tokens, {
    bold: (token, ctx) => console.log(`bold at depth ${ctx.depth}`),
    link: (token) => urls.push(token.url as string),
});

ctx 里有什么

interface TokenVisitContext {
    parent: TextToken | null;  // 父节点，根节点时为 null
    depth: number;              // 嵌套深度，根节点为 0
    index: number;              // 在兄弟节点中的位置
}

遍历顺序图解

输入树：  text("Hello ") → bold([ text("world") ]) → text("!")

访问顺序：
  ①  text("Hello ")     depth=0
  ②  bold(...)           depth=0
  ③    text("world")     depth=1   ← bold 的子节点
  ④  text("!")           depth=0

先父后子，同层从左到右。

实战例子

收集所有出现过的标签类型：

const types = new Set<string>();
walkTokens(tokens, (token) => types.add(token.type));
// types → Set { "text", "bold", "link", ... }

mapTokens(tokens, visitor)

function mapTokens(tokens: TextToken[], visitor: MapVisitor): TextToken[]

深度优先后序变换——先把子节点全部映射完，再轮到父节点。返回一棵全新的树，原树不受影响。

visitor 返回值决定一切

type MapVisitor = (
    token: TextToken,
    ctx: TokenVisitContext,
) => TextToken | TextToken[] | null;
返回值 效果
TextToken 保留或替换这个节点
TextToken[] 把一个节点展开成多个兄弟节点
null 删掉这个节点

为什么是后序？

原始树：        bold([ text("hello"), em([ text("world") ]) ])

映射顺序：
  ①  text("hello")    ← 叶子先处理
  ②  text("world")    ← 叶子先处理
  ③  em(...)           ← 子节点已经映射完了，em 拿到的是新的子树
  ④  bold(...)         ← 最后才轮到根

好处： 当你的回调看到 bold 时，token.value 里的子节点已经是映射后的版本了。你可以放心地基于子节点的新状态做决策。

ctx.parent 注意事项

ctx.parent 始终是原始父节点（映射之前的）。单次后序遍历在处理子节点时，父节点还没被映射，所以不可能给你映射后的版本。别依赖 ctx.parent.value 反映已映射的子节点。

实战例子

删除所有 hidden 节点：

const visible = mapTokens(tokens, (token) =>
    token.type === "hidden" ? null : token,
);

文本全部大写：

const shouted = mapTokens(tokens, (token) =>
    token.type === "text" && typeof token.value === "string"
        ? {...token, value: token.value.toUpperCase()}
        : token,
);

去掉包装器，把子节点提升为兄弟节点：

const unwrapped = mapTokens(tokens, (token) =>
    token.type === "wrapper" ? (token.value as TextToken[]) : token,
);

filterTokens(tokens, predicate)

function filterTokens<T extends TextToken = TextToken>(
    tokens: TextToken[],
    predicate: (token: TextToken, ctx: TokenVisitContext) => boolean,
): T[]

mapTokens 的快捷写法——只保留 predicate 返回 true 的节点，删掉其余的。 注意它的语义是树裁剪，不是“先拍平成一列再筛选”。 保留下来的节点仍然保持原有嵌套结构，被删掉节点的子树会原位一起移除。

等价于：

mapTokens(tokens, (token, ctx) => predicate(token, ctx) ? token : null)

类型谓词收窄

如果 predicate 是类型谓词函数，返回值会自动收窄：

interface LinkToken extends TextToken { type: "link"; url: string }

const links = filterTokens(tokens, (t): t is LinkToken => t.type === "link");
// links: LinkToken[]

实战例子

删除所有 hidden 节点（和 mapTokens 返回 null 等价，但更直观）：

const visible = filterTokens(tokens, (token) => token.type !== "hidden");

只保留深度不超过 2 的节点：

const shallow = filterTokens(tokens, (_token, ctx) => ctx.depth <= 2);

如果你想要的是“平铺收集所有匹配节点”，那应该用 walkTokens(...) 自己 push 到数组里，而不是用 filterTokens(...)。

性能

在 ~200 KB 文档上测量（9,165 渲染 token，共访问 9,165 个节点）。 环境：鲲鹏 920 aarch64 / Node v24.14.0。数据为 5 次独立运行的平均值。

操作 耗时 备注
walkTokens 0.50 ms 先序 DFS，访问所有 9,165 个节点
mapTokens 恒等 1.21 ms 返回相同的树，不做变换
mapTokens 变换 1.55 ms 将整棵树中的 bold 改名为 strong

两者在 200 KB 文档上均约为 1.5ms 左右——在任何实际管线里相当于免费。

⚠️ **GitHub.com Fallback** ⚠️