findDiffStart / findDiffEnd：两份文档怎么求差

前十篇把 model 层读了大半：文档怎么存（Node、Fragment、Mark），结构怎么约束（Schema），位置怎么解析（ResolvedPos），怎么切块再塞回（Slice），进出 DOM 的两个方向（to_dom、from_dom）。这篇读 model 里剩下的一个小角落：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，把变化读回文档」这条路径，那里一次变化本来就是连续的，最后一节细说。这两个函数挂在 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 的懒版本：不先把整棵树比完，边扫边问，发现不同立即定位。

这套相等定义不只服务 diff。view 层做增量渲染时，ViewDesc 树要判断「已有的 DOM 描述能不能承载新文档里的这个节点」，viewdesc.ts 里 matchesNode 的判定中就有一行 node.sameMarkup(this.node)：外壳相同就复用旧 DOM 只更新内容，外壳不同就推倒重建。model 层把「相等」定义清楚一次，diff、节点比较、视图复用三处共用，这是小函数的价值。

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 变化翻译成文档变更时，负责定位变更区间的那一步。

小结

model 层读到这里接近尾声。diff.ts 和 comparedeep.ts 是其中最小的两个文件，角色很清楚：compareDeep 定义「值相等」，sameMarkup 在其上定义「节点外壳相等」，findDiffStart 和 findDiffEnd 用这两层判定从两端向中间扫描，产出 [start, endA, endB) 三元组。不可变文档的引用共享让相同子树 O(1) 跳过，是这套扫描在实际文档上跑得动的前提。下一篇是 model 阶段的收官，把 Node 和 Fragment 上剩下的辅助方法梳理一遍：遍历族、canReplace 校验族、位置查询的边界行为，给这个阶段收尾。