findDiffStart / findDiffEnd：定位两份文档的差异区间

前十篇已经覆盖 model 层的文档存储（Node、Fragment、Mark）、结构约束（Schema）、位置解析（ResolvedPos）、Slice，以及 DOM 的序列化和解析。本篇分析 src/diff.ts 与 src/comparedeep.ts：两个文件合计不到 70 行，用于定位两份文档的差异区间。参考代码是 prosemirror-model 的 6264de0。

系列目录

产出是一个连续区间

先把接口形状定下来。src/diff.ts 导出两个函数：findDiffStart(a, b, pos) 找两个 Fragment 从头数第一个不同的位置，找不到返回 null；findDiffEnd(a, b, posA, posB) 从尾数，返回 {a, b} 两个位置。Fragment 上有同名方法（src/fragment.ts）做转发，findDiffStart 的 pos 缺省取 0，findDiffEnd 的两个位置缺省取各自的 size。

三个位置合起来表达一次变更：旧文档的 [start, endA) 被新文档的 [start, endB) 替换。结束位置拆成两个是因为插入和删除会改变文档长度，「差异部分的终点」在两份文档里不是同一个数字。开头位置不用拆，从头扫的时候两边同步前进，分叉点只有一个。

这套接口不产出操作列表，也不计算最小编辑脚本；它只定位一个连续区间，因此两处不相邻的修改会被包含在同一个区间中。它的主要消费场景是浏览器修改 DOM 后将变化读回文档，一次读回通常对应连续的 DOM 变化。两个函数同时暴露在 Fragment 的公开 API 上。例如，插件保存旧文档快照后，可以调用 findDiffStart 和 findDiffEnd 确定一次事务影响的区间。

findDiffStart：从前向后扫

从头扫描使用一个 for 循环，按以下顺序处理分支：

if (i == a.childCount || i == b.childCount)
  return a.childCount == b.childCount ? null : pos
let childA = a.child(i), childB = b.child(i)
if (childA == childB) { pos += childA.nodeSize; continue }
if (!childA.sameMarkup(childB)) return pos
if (childA.isText && childA.text != childB.text) {
  for (let j = 0; childA.text![j] == childB.text![j]; j++) pos++
  return pos
}
if (childA.content.size || childB.content.size) {
  let inner = findDiffStart(childA.content, childB.content, pos + 1)
  if (inner != null) return inner
}
pos += childA.nodeSize

逐条看：

• 某一边的孩子先数完：childCount 相等说明两边完全一样，返回 null；不相等说明一边多出一截，当前 pos 就是差异起点。
• 引用相等直接跳过整棵子树，pos 加上 nodeSize 继续。性能主要省在这条分支上：文档不可变（第 4 篇），没改过的子树在两个版本之间是同一个对象，== 一次比较就跳过整棵子树，不用递归。只改了一个字符的新旧文档之间，绝大部分子树走这条分支。
• sameMarkup 不同（类型、attrs、marks 有任何一个变了）直接返回当前位置。节点外壳变了，diff 不再往里看，整个节点算作差异。
• 文本节点且文字不同：逐字符比公共前缀，停在第一个不同的字符上。
• 两边至少一边有内容：递归进去，基准位置 pos + 1。加的这个 1 是子节点的开 token，第 7 篇的位置约定里每个节点边界占一个位置。递归返回 null 表示内容相同，落到最后一行 pos 加 nodeSize 继续；返回数字就直接往上抛。

「至少一边有内容」处理一边为空、另一边有内容的情况。例如旧节点是空段落、新节点的段落包含文字时，递归后空侧的 childCount 为 0，第一轮循环通过耗尽分支返回 pos + 1，差异起点位于段落内部的第一个位置。两边都为空时不进入递归，外壳相同的两个空节点会被视为相同并跳过。

引用相等分支的效果可以用单字符修改说明。新旧文档中，从根到被修改文本节点路径上的节点会被新建，路径之外的子树仍复用原对象。findDiffStart 从根向下扫描时，路径之外的子树都通过 == 整体跳过，只有这条路径需要展开比较。因此成本主要随差异所在的深度增长，与文档总大小关系较小。该特征依赖不可变文档的引用共享；若文档可变且每次比较都需逐节点深查，无法采用相同的实现。

findDiffEnd：从尾向前，两个位置各自记账

从尾扫是镜像逻辑：iA、iB 从各自的 childCount 倒着减，引用相等就两边各回退 nodeSize；sameMarkup 不同返回当时的 {a: posA, b: posB}；文本不同就从末尾往前比公共后缀，每多一个相同字符 posA、posB 各减一；递归时基准是 posA - 1 和 posB - 1，减的 1 是闭 token。

返回值是 {a: number, b: number} | null。一边先数完时，iA 和 iB 同时归零说明相同，返回 null；否则返回当时剩下的 posA 和 posB。因为两边长度可能不同，扫描全程两个位置各自记账，互不借用。

拿一个具体例子走一遍：旧文档一个段落，内容 “abc”；新文档一个段落，内容 “axyc”。

findDiffStart：两个段落节点引用不等，sameMarkup 相同（同类型、无 attrs、无 marks），递归进内容，基准 1。文本节点逐字符比，‘a’ 相同 pos 到 2，‘b’ 对 ‘x’ 停下，返回 2。

findDiffEnd：外层 posA 传 5、posB 传 6，递归进段落内容时各减 1 变成 4 和 5。后缀比较：‘c’ 相同，posA 退到 3、posB 退到 4；下一个字符 ‘b’ 对 ‘y’ 停下。返回 {a: 3, b: 4}。

合起来：start = 2，endA = 3，endB = 4。旧文档 [2, 3) 的 “b” 被新文档 [2, 4) 的 “xy” 替换，语义正好是一次替换。图里把段落的递归展开成了 token 序列，p 始、p 终各代表一个位置边界。

反方向走一遍能看清 endA、endB 的不对称。把两份文档对调：旧文档 “axyc”、新文档 “abc”。findDiffStart 同样停在 2。findDiffEnd 外层 posA 传 6、posB 传 5，递归进段落内容各减 1 变成 5 和 4；后缀比较 ‘c’ 相同，posA 退到 4、posB 退到 3，下一个字符 ‘y’ 对 ‘b’ 停下，返回 {a: 4, b: 3}。结果是 start = 2，endA = 4，endB = 3：旧文档 [2, 4) 的 “xy” 被新文档 [2, 3) 的 “b” 替换，正好是上一个例子的逆操作。三元组里 endB < endA 表示变短，endB > endA 表示变长，增删改三种形态用同一组数字表达。

compareDeep：相等的定义

diff 的两个函数通过三层判定比较节点，compareDeep 位于最底层。

第一层是引用相等，前面说了。第二层是 sameMarkup（src/node.ts），本体是 hasMarkup：类型相等、attrs 相等、marks 集合相等。第三层落到 attrs 怎么判相等。Node 和 Mark 的 attrs 是普通对象，每次解析、反序列化、create 都新建一份，引用比较必然失败，只能按值比。Mark.eq（src/mark.ts）是同样的结构，「type 相同加 compareDeep(attrs)」，Mark.sameSet 再对两个 marks 数组逐项 eq。

compareDeep 本体（src/comparedeep.ts）十五行：

export function compareDeep(a: any, b: any) {
  if (a === b) return true
  if (!(a && typeof a == "object") ||
      !(b && typeof b == "object")) return false
  let array = Array.isArray(a)
  if (Array.isArray(b) != array) return false
  if (array) {
    if (a.length != b.length) return false
    for (let i = 0; i < a.length; i++) if (!compareDeep(a[i], b[i])) return false
  } else {
    for (let p in a) if (!(p in b) || !compareDeep(a[p], b[p])) return false
    for (let p in b) if (!(p in a)) return false
  }
  return true
}

几个设计点：

• === 先挡一层。原始值相等、同一对象引用都在这一步返回，null 对 null 也在这里接住。
• 走到第二行的「非对象」只剩数字、字符串、布尔这类原始值，=== 不等就是不等，判负。
• 数组和对象不混：Array.isArray 两边结果不一致直接判负。
• 对象比较用两个 for-in 循环。第一个查 a 的每个键在 b 里存在且值相等，但它查不出 b 多出来的键，所以第二个循环专查「b 有 a 没有」。两轮合起来才是键集合相等。
• 没有循环引用检测，也没有 Date、RegExp 之类的特判。这能成立是因为 attrs 的约定就是可 JSON 化的纯数据，schema 的 attrs 声明（第 6 篇）只会产出字符串、数字、布尔、数组和普通对象。

hasMarkup 里 attrs 的比较写法是 compareDeep(this.attrs, attrs || type.defaultAttrs || emptyAttrs)：调用方没给 attrs 时用类型的默认值兜底，保证「没传」和「传了默认值」判相等。

Node.eq 把三层串成一句：this == other || (this.sameMarkup(other) && this.content.eq(other.content))，Fragment.eq 逐个孩子 eq。diff 里的 sameMarkup 检查可以看作 eq 的懒版本：不先把整棵树比完，边扫边问，发现不同立即定位。

这套相等定义也服务于 view 层的增量渲染。ViewDesc 树需要判断已有 DOM 描述是否可用于新文档中的节点；viewdesc.ts 的 matchesNode 使用 node.sameMarkup(this.node)。外壳相同时复用旧 DOM 并更新内容，外壳不同时重新创建 DOM。diff、节点比较和视图复用共用 model 层的相等定义。

compareDeep 也递归处理数组值。schema 允许 attr 的默认值为数组，例如自定义节点保存坐标对时；compareDeep 会先比较数组长度，再逐项递归比较。对象比较需要遍历全部键，但 attrs 通常只包含少量键。

谁在用：domchange 的读回

model 层这两个函数不修改任何东西，纯查询。最大的消费方在 view 层：浏览器直接改了 DOM 之后的读回。参考代码是 prosemirror-view 的 ca4c78e，src/domchange.ts。

用户在编辑器里打字、输入法上屏、按退格，浏览器先把 contenteditable 里的 DOM 改掉，DOMObserver 收集到 MutationRecord 之后调 readDOMChange。这个函数的任务是把「DOM 变成什么样了」翻译成对文档的一次修改，其中和 diff 相关的部分：

1. parseBetween 把变化区间的 DOM 用 DOMParser 重新解析成一份新文档。第 10 篇的解析器在这里被消费，topOpen、context 这些参数保证解析结果和原文档的上下文对齐。
2. compare = doc.slice(parse.from, parse.to)，从旧文档切出同一区间的内容。
3. 调 domchange.ts 里的包装函数 findDiff：内部先 findDiffStart，返回 null 说明内容没变，可能只是选区变了，走只更新选区的分支；有起点再 findDiffEnd 拿 endA、endB。

findDiffStart 返回 null 还有一个例外出口：typeOver 场景。用户选中一段文字后直接键入，浏览器把选中内容替换成了新字符；如果键入的内容恰好和选区原有内容一样，两份文档求差的结果就是「没变」，但用户实际做了一次替换。readDOMChange 检查到 typeOver 为真、选区非空、锚点和焦点在同一父节点里，就手工补一个 change：{start: sel.from, endA: sel.to, endB: sel.to}，把整个选区算作被替换。这个分支能存在，正好说明这种两头扫描的盲区：它只保证找到「能解释两份文档差异」的一个区间，不保证区间和用户实际操作一一对应，view 层要靠上下文（按键记录、选区、计时）把歧义消解掉。

包装函数会修正原始扫描结果。纯插入时，前缀和后缀扫描可能重叠，出现 endA < start；此时 preferredPos（当前光标位置）决定变更锚定在哪一端。刚按下退格键时 preferredSide 取 “end”，变更锚定在区间尾部，以对应删除光标前内容的操作。锚定后还会执行 isSurrogatePair 检查：start 若落在 UTF-16 代理对的边界上（emoji 等增补平面字符占两个码元），则向一侧移动一个码元，避免变更范围从代理对中间截断。

拿到 {start, endA, endB} 之后还有一层启发式值得提：变化看起来像按了一次 Enter 或 Backspace 的效果时（looksLikeBackspace 等判断），readDOMChange 放弃按区间替换，改成 handleKeyDown 事件重放，让 keymap 和命令插件接管。原因很实际：Enter 在插件眼里可能挂着输入规则、列表拆分等一串行为，直接替换文档会把这些行为全部绕过。diff 给出的是「文档层面变了什么」，要不要按原样应用，view 层还会再过一道判断。这条读回链路的完整细节到 view 阶段再展开，这里只要记住 diff 的位置：它是 DOM 变化翻译成文档变更时，负责定位变更区间的那一步。

差异定位的范围

compareDeep 定义值相等，sameMarkup 在此基础上定义节点外壳相等，findDiffStart 和 findDiffEnd 据此从两端扫描，产出 [start, endA, endB) 三元组。不可变文档的引用共享使相同子树可通过 O(1) 的引用比较跳过。该算法定位的是能够解释两份文档差异的连续区间，不保证还原用户的实际操作；DOM 读回路径会结合选区和按键等上下文处理这种歧义。下一篇整理 Node 与 Fragment 中遍历、canReplace 校验和位置查询相关的辅助方法。