前两篇看了 collab 怎么把本地 step 发给中心、远端 step 收回来怎么重整。协作场景还有另一个需求：把一段时间里发生的修改汇总展示出来，谁删了哪段、谁插了哪段。prosemirror-changeset 干的就是这个：输入是起始文档和一串 StepMap，输出是一组扁平的插入删除区间，每个区间上可以挂任意数据，比如作者和时间戳，拿去渲染修订模式。整个包四个源文件：changeset.ts 是 ChangeSet 类，change.ts 是 Change 和 Span 两个数据结构，diff.ts 是内置的 diff 算法，simplify.ts 是展示层的化简。对外导出 ChangeSet、Change、Span、ChangeJSON、simplifyChanges、TokenEncoder 六个名字。参考代码是 prosemirror-changeset 的 3e1c666；顺带引用的 prosemirror-model、prosemirror-transform 分别是 6264de0、662b7a9。
系列目录
Span 与 Change：变更集的数据结构
变更集最终要回答的问题是「从起始文档到现在，哪些地方被换成了什么」。Change（change.ts）就是对一处替换的记录，六个字段：
- fromA、toA：被替换区间在起始文档（A 坐标）里的起止。
- fromB、toB：替换结果在当前文档（B 坐标）里的起止。
- deleted：被删内容的元数据，一个 Span 数组。
- inserted：插入内容的元数据，一个 Span 数组。
Span 更简单，只有 length 和 data 两个字段。length 是这段内容的长度，data 是任意元数据。长度上有一条硬约束：deleted 里所有 span 的长度之和等于 toA - fromA，inserted 里所有 span 的长度之和等于 toB - fromB。也就是说 span 数组是对整个区间的不重叠切分，切几段取决于元数据换过几次手。同一个人连续插入的一段话是一个 span；两个人先后在同一段里插了内容，合并之后就会是两个 span，各自记各自的作者。
双坐标是这套数据结构里最值得记住的设计。fromA/toA 永远相对 startDoc（ChangeSet.create 时传入的那份文档，存在 config.doc 上，startDoc getter 直接返回它），fromB/toB 永远相对当前最新文档。中间经过多少步修改都不影响这两套坐标的含义：想在旧文档里定位被删的内容，直接用 A 坐标取；想在新文档里高亮插入的内容，直接用 B 坐标取。不需要拿着 Mapping 逐步映射，这是它比普通 StepMap 链好消费的地方。代价是每次 addSteps 都要做归并来维护这个不变式，下面讲。
Span 上有几个静态工具方法。Span.slice 按区间切出子数组，跨 span 的边界处用 span.cut 截断。Span.join 拼接两个 span 数组，边界处会调一次 combine 函数试探：combine(a[a.length-1].data, b[0].data) 返回非 null 就把两个 span 合成一个，返回 null 就原样相接。combine 是 ChangeSet.create 的第二个参数，默认值是 (a, b) => a === b ? a : null，即元数据完全相等才合并。自定义 combine 是实现「同一个人的连续修改合并显示」这类策略的入口：比如 data 是 {user, time} 时，可以让 combine 在 user 相同且时间接近时返回合并后的对象。combine 返回 null 的语义是「不可合并」，归并逻辑处处依赖这个约定。Span.none 是空数组常量，表示没有 span，Span.len 求一个 span 数组的总长度，主要给内部断言式的切片用。
Change 自身也有两个辅助。lenA、lenB 两个 getter 分别返回两侧区间长度。slice(startA, endA, startB, endB) 按相对偏移切出子 Change，span 数组跟着用 Span.slice 截，computeDiff 回溯时就是靠它把 token 坐标换算回文档坐标。
addSteps：从 StepMap 累积变更
ChangeSet 本体只有 config 和 changes 两个字段，不可变。增量接口是 addSteps(newDoc, maps, data)：maps 是一组 StepMap（第 15 篇 StepMap：一步修改怎么映射每个位置 讲的区间段编码），data 是这批步骤的元数据，可以传单个值也可以按 map 逐个传。
第一步，把每个 StepMap 展开成 Change。StepMap.forEach 回调给出 (fromA, toA, fromB, toB) 四元组，直接拿来建 Change：纯插入的区间 deleted 填 Span.none，纯删除的区间 inserted 填 Span.none。有一个细节：同一个 StepMap 里多段区间的 B 坐标是相对「应用了本段之前各段」的文档编的，所以循环里维护一个 off，每处理一段就累加 (toB - fromB) - (toA - fromA)，下一段的 A 侧坐标加上这个偏移才是统一坐标系里的值。
第二步，归并。这一步产生的 Change 先过 mergeAll 合成一组：mergeAll 是分治，数组对半切，两边各自递归，再用 Change.merge 合起来，避免顺序归并时后段不断偏移前段的重复开销。然后 Change.merge(this.changes, newChanges, combine) 把新变更合进既有变更集。
Change.merge（change.ts）是整个包最绕的一段，值得展开。它合并的两个变更集 x、y 有一个前提：x 的结束文档就是 y 的起始文档。代码里把这份中间文档叫 middle coordinate system，x 的 B 坐标和 y 的 A 坐标都指向它。主体是双指针并行扫描，注释把归并规则写成了三句：旧集的删除和新集的插入都保留；中间文档里被 x 覆盖但不被 y 覆盖的区域，是 x 的插入，要补进来；被 y 覆盖但不被 x 覆盖的区域，是 y 的删除，也要补进来。落到实现上是一个外层循环处理「完全不相交、可以直接平移输出」的情形，加上一个内层循环处理「碰到一起、需要拼成一个大 Change」的情形。内层循环里 pos 沿中间坐标推进，inX、inY 标记当前位置落在哪边的区间里，四种组合分别对应：进入 x 的区间时吞掉它的 deleted，只在 x 里时把 x 的 inserted 按片切进结果，进入 y 的区间时吞掉它的 inserted，只在 y 里时把 y 的 deleted 切进来。enteredX、enteredY 两个标志防止同一个 Change 的 deleted 或 inserted 被重复追加。扫完得到的 Change 直接跨越起始文档到最新文档，中间文档被消掉了，这正是双坐标不变式的维护过程。
第三步，最小化。merge 是按区间几何关系拼的，不关心内容。一个常见情形：用户删了一个词又原样打回来，几何上这是一处替换，内容上什么都没变。addSteps 的最后一段循环处理这个：对每个被本次新变更触碰到的 Change（判断条件是它与任一 newChange 在 B 坐标上有重叠），调 computeDiff 比较起始文档和 newDoc 在这个区间里的实际内容，把相同的前后缀和中间相同段落从变更里剥掉。剥完可能一个 Change 裂成几个，也可能整个消失。有个 fast path：diff 结果只有一段且覆盖整个 B 区间，说明两侧内容完全不同，剥不出东西，直接跳过。
addSteps 的文档注释里有一个提醒：增量添加和一次性添加的结果可能不同。因为最小化依赖当前变更边界做内容比较，分批进来时边界不同，匹配上的 token 就不同。这是设计接受的近似，不是 bug。
diff.ts：token 化之后的 Myers
computeDiff（diff.ts）是这个包内置的 diff。和第 11 篇 findDiffStart / findDiffEnd 的分工不同：model 里的 diff 只找一对边界，给 DOM 读回用；这里要找出一个区间里的全部差异段，给展示用。
比较之前先 token 化。tokens 函数把 fragment 的指定区间拉平成一个 token 数组：文本逐字符编码，非叶节点的开标签和闭标签各占一个 token，叶节点整体一个 token。编码方式由 TokenEncoder 接口决定，四个方法：encodeCharacter(char, marks)、encodeNodeStart(node)、encodeNodeEnd(node)、compareTokens(a, b)。默认实现 DefaultEncoder 里，字符用 charCode 本身，节点开标签用类型名字符串，闭标签用负的 typeID。typeID 是节点类型在 schema.nodes 里的序号加一，缓存在 schema.cached.changeSetIDs 上，避免每次重算。默认编码不看 mark 也不看 attrs，只改格式的修改会被 diff 判定为无变化。想让格式变化也进变更集，就传自定义 encoder，把 marks 编进 token；接口文档里提醒编码和比较调用次数很多，自定义实现别做重活。
算法本体分三段。先从两端扫，去掉公共前后缀。一侧扫空或者只剩单 token 的简单情形直接返回。剩下的进 Myers diff，代码注释里给了两篇参考文献。Myers 的复杂度跟差异量挂钩，大段替换会退化，所以有两个护栏。一是 MAX_DIFF_SIZE 等于 5000，编辑步数超过这个上限就放弃精细 diff，把剩余区间整体作为一个 change 返回，注释里说这个量级大约占 300 毫秒。二是 minUnchanged：差异段之间如果夹着的未变片段太短，就把它们合并成一段，阈值是 Math.min(15, Math.max(2, Math.floor(Math.max(sizeA, sizeB) / 10)))，区间越大阈值越高。注释解释了动机：替换一整段文字时，两侧碰巧相同的零散字母会切出一堆无意义的小变更，diff soup，合并阈值就是过滤这种巧合。
回溯阶段从最后一个 frontier 沿 history 数组倒走，next < prev 判定为删除，否则判定为插入，逐段构造 Change，再用 range.slice 把 token 坐标换算回文档坐标。
simplifyChanges：给人看的化简
computeDiff 的最小化让变更贴近内容，但贴近内容不等于贴近阅读习惯。simplify.ts 开头把假设写明了：同一个词里既有插入又有删除，对人来说读起来费劲，遇到这种情况应该把整个词整段标出来。例外是单字符替换，改一个字不至于。
simplifyChanges(changes, doc) 先在 B 坐标上把变更分组：相邻变更的间距不超过 MAX_SIMPLIFY_DISTANCE（30 个位置）就归进一组，组内交给 simplifyAdjacentChanges 处理。组内取组前后各 30 个位置的文本，getText 把区间拉成纯字符串，非文本 token 一律换成空格，保证词边界判断不被节点结构干扰。isLetter 判断一个码点是不是字母：优先用带 unicode 属性支持的正则 [\p{Alphabetic}_]，运行环境不支持就退化到「大小写变换后有变化」加上一组单 case 文字区间，中文、日文、韩文、阿拉伯文都在这组区间里。
之后逐个看组内相邻变更之间有没有词边界：两段变更之间只要夹着非字母字符（具体判断是逐对相邻字符检查，存在两侧不都是字母的一对即算边界），就认为边界存在，不动它们；中间全是字母，说明两段变更落在同一个词内部，合并。合并出来的组同时有插入和删除、且不是单字符替换（inserted == 1 && deleted == 1 的例外）时，把范围向两边扩到整个词：左端点是字母就一直往左扩到词头，右端点同理。fillChange 重建一个覆盖整词的大 Change，deleted 和 inserted 用 Span.join 重新拼，A 侧坐标按 B 侧的扩量同步加减。拼好的 Change 若和结果集里上一个 Change 在 A 坐标上首尾相接（last.toA == joined.fromA），直接并进上一个，避免输出两个相邻变更。不同时满足条件的组原样输出。
这个函数是纯展示层的，输出只用来渲染，不回写变更集。使用方通常在 ChangeSet 之外再调一次它，拿化简后的结果生成 Decoration（第 33 篇 Decoration 体系）：deleted 区间画删除线，inserted 区间上底色，span 的 data 决定悬浮提示里显示谁改的。
其余 API 与典型用法
ChangeSet 上还有三个方法。map(f) 把所有 span 的 data 过一个函数生成新集合，元数据换格式时用。changedRange(b, maps) 比较两个变更集，返回差异范围，文档在两份集合之间又变了的话把对应的 StepMap 传进来做坐标修正；用途是增量刷新，屏幕外的变更集没变就不重绘。实现上先用 touchedRange 算出这批 map 在两侧文档各自触碰的范围，touchedRange 内部对正序的 map 求 B 侧覆盖、对逐个 invert 后逆序的 map 求 A 侧覆盖，然后双指针扫两个 changes 数组，映射后仍相同的 Change 跳过，不同的把范围并进结果。序列化方面，Change.toJSON 直接返回 this，因为六个字段本身就是 JSON 兼容的；恢复时把 change 数组逐个 Change.fromJSON，再作为 create 的第四个参数传回去，config 里的 doc、combine、encoder 要自己重新提供。
串起来看，一个修订模式的典型装配是这样的：ChangeSet.create(初始文档) 建集，之后每次 dispatch 拿到 transaction，就把 tr.mapping 里的 StepMap（或协作场景下 receiveTransaction 带进来的远端 step maps）连同 {user, time} 元数据 addSteps 进去；渲染前 simplifyChanges 化简，转成 DecorationSet 交给 view。协同痕迹、编辑历史回放都是同一个套路，区别只在 data 里记什么、combine 怎么定。
小结与下一篇
这个包把「一串 step 改了什么」压缩成「旧文档哪些区间被换成了新文档哪些区间」：Change 的 A/B 双坐标免去了逐条映射，Change.merge 在中间坐标系上归并维持这个不变式，computeDiff 按内容剥掉没换的部分，simplifyChanges 再按词边界把结果收拾成适合展示的形状。四步各管一段，组合出修订模式的全部计算需求。
下一篇看 prosemirror-markdown：文档和 Markdown 文本之间怎么做双向转换，序列化表和解析栈各长什么样。
