DOM插入算法中嵌套子树双重遍历的疑问解析

熟悉DOM的开发者都了解append、prepend这类插入方法。我在研究WHATWG的DOM插入算法时产生了困惑：

规范的步骤7要求按树序遍历nodes中的每个节点，执行节点文档适配、插入等操作；而子步骤7.7则要求按包含阴影树的树序遍历当前节点的所有含阴影后代节点，执行插入步骤、触发回调等操作。

以插入包含shadow-root的复杂DOM结构为例：

<section>
  <div id="1">
    <title>Title 1</title>
    <component-description>
      #shadow-root
        <span>Lorem ipsum</span>
    </component-description>
  </div>
  <div id="2">
    <title>Title 2</title>
    <component-description>
      #shadow-root
        <span>Lorem ipsum</span>
    </component-description>
  </div>
  <div id="3">
    <title>Title 3</title>
    <component-description>
      #shadow-root
        <span>Lorem ipsum</span>
    </component-description></div>
</section>

执行插入算法时，步骤7遍历section节点后，7.7会遍历其所有含阴影的后代；回到步骤7遍历div#1时，7.7又会遍历div#1的所有含阴影后代，导致div#1等节点被重复遍历。

核心疑问 #

• 为何在已有覆盖阴影树的广范围遍历的情况下，仍需保留仅遍历普通树的步骤7？
• 算法步骤11再次执行类似的双重遍历，目的是什么？

直观展示重复访问现象的代码示例 #

let wrapper = document.createElement("div");
wrapper.setHTMLUnsafe(`<section>
  <div id="1">
    <title>Title 1</title>
    <component-description>
        <template shadowrootmode="open">
            <span>Lorem ipsum</span>
        </template>
    </component-description>
  </div>
  <div id="2">
    <title>Title 2</title>
    <component-description>
        <template shadowrootmode="open">
            <span>Lorem ipsum</span>
        </template>
    </component-description>
  </div>
  <div id="3">
    <title>Title 3</title>
    <component-description>
        <template shadowrootmode="open">
            <span>Lorem ipsum</span>
        </template>
    </component-description></div>
</section>`)
let targetNode = wrapper.firstElementChild;

/// 对应规范中的步骤7
function traverseTree(node, shadows){
  if (node.visited === undefined) node.visited = 0;
  ++node.visited;
  node.setAttribute?.("visited", node.visited);
  console.log(node, "=>", node.visited);

  if (typeof shadows === "function") shadows(node);

  for (let child = node.firstChild; child; child = child.nextSibling){
      traverseTree(child, shadows);
  }
}

function traverseTreeWithShadows(node){
  if (node.visited === undefined) node.visited = 0;
  ++node.visited
  node.setAttribute?.("visited", node.visited);

  if (node.shadowRoot) traverseTreeWithShadows(node.shadowRoot);
  for (let child = node.firstChild; child; child = child.nextSibling) {
      traverseTreeWithShadows(child);
  }
}

traverseTree(targetNode, traverseTreeWithShadows)

设计意图解析 #

1. 步骤7：普通树遍历的必要性

步骤7的核心是处理普通DOM节点本身的插入逻辑，职责包括：

• 节点的文档适配：将节点从原文档迁移到目标文档，同步跨文档节点的状态
• 维护DOM树结构：更新父节点、兄弟节点的关联指针
• 触发节点级插入钩子：比如beforeinsert这类针对宿主节点本身的回调

子步骤7.7的阴影树遍历则是处理宿主节点关联的阴影DOM内容——阴影树是附着在普通节点上的独立子树，需要单独完成插入、回调触发等操作。两者处理对象和职责完全分离：步骤7管"宿主节点"，7.7管"宿主节点带的阴影树"，不存在覆盖关系，因此必须分开执行。

2. 步骤11：二次双重遍历的目的

步骤11的遍历是处理插入完成后的收尾逻辑，比如：

• 触发DOMNodeInserted这类全局插入事件
• 同步节点的布局、样式计算状态
• 激活阴影树的渲染上下文，完成shadow root的初始化

和步骤7的"插入过程中"逻辑不同，步骤11是"插入完成后"的状态同步。同样需要分两层：先遍历普通DOM树确认所有宿主节点就位，再遍历阴影树完成内部内容的最终激活，确保整个DOM结构（包括阴影部分）的状态一致性。

关于"重复遍历"的误解

代码中看到的节点多次访问，是模拟时叠加了步骤7和7.7的计数逻辑，但实际规范中两者执行的是完全不同的操作：

• 步骤7的遍历是给节点做"插入到目标树"的标记和状态更新
• 7.7的遍历是进入阴影树内部，处理阴影节点的插入逻辑
  两者不会重复执行相同操作，只是遍历路径有重叠，并非无意义的重复。

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