Mapping:多步映射的链式合并,rebase 的地基

📅
2 分钟阅读
·

上一篇介绍了 StepMap 如何用三元组数组描述单个 step、映射位置,并通过 recover 值记录被删除位置。recover 的消费方位于同一个文件:src/map.ts 的下半部分定义了 Mapping 类,用它可将零到多张 StepMap 组合起来,使位置依次经过多步修改。recover、StepMap.invert 和逆步骤共同用于 Mapping 的镜像机制。参考代码是 prosemirror-transform 的 662b7a9。

系列目录

四个字段:maps、mirror、from 与 to

Mapping 的构造参数是四个:StepMap 数组 maps、镜像记录 mirror、起始下标 from、结束下标 to。maps 是管线本体,位置从 from 开始一张张穿过去,到 to 为止。from 和 to 默认覆盖整个数组,slice 方法用它们圈出子区间,后面单独说。

mirror 是这篇重点拆的部分。它是一个普通数字数组,按对存放:setMirror(n, m) 直接 push 两个数,表示 maps[n] 和 maps[m] 互为镜像,也就是一张是另一张的逆。getMirror(n) 线性扫这个数组,在偶数下标找到 n 就返回后一个,奇数下标找到就返回前一个,一次查询两个方向都覆盖。数组通常很短,线性扫足够。

谁在生产镜像对,等下看消费方。先记住一点:Mapping 自己不验证两张 map 真的互逆,镜像关系完全是调用方声明的。声明错了,找回的位置就错了,机制本身不做防护。

还有一个内部字段 ownData。构造时如果传入了 maps 或 mirror,ownData 为 false,表示数组是共享的,不能改。slice 出来的子 Mapping 就和原 Mapping 共享这两个数组。appendMap 要追加时先检查 ownData,共享就先 slice 一份拷贝再改,是简单的写时复制。

没有镜像时:顺序映射与删除信息累计

先看 map 的实现:

map(pos: number, assoc = 1) {
  if (this.mirror) return this._map(pos, assoc, true) as number
  for (let i = this.from; i < this.to; i++)
    pos = this._maps[i].map(pos, assoc)
  return pos
}

没有 mirror 时走快速路径:一个循环,每张 StepMap 顺序映射,不创建任何 MapResult 对象。Transform 每应用一个 step 就把 step.getMap() 追加进自己的 mapping 字段(src/transform.ts),一次输入产生的选区映射、装饰映射走的就是这条路径,开销和步数成正比,中间没有对象分配。

值得留意的是,Mapping 和 StepMap 一样 implements Mappable,两个方法签名完全相同。所以消费方不需要区分自己拿到的是单步映射还是多步管线:Step.map 的签名(src/step.ts)收的是 Mappable,state 层 Selection 和 SelectionBookmark 的 map 方法收的也是 Mappable,传整张 Mapping 或者 slice 出来的窗口都行。链式语义被封装在 Mapping 内部,对外只是一个 map 调用。

assoc 在链里是逐张透传的,每张 StepMap 都拿同一个 assoc 做自己的边界决策。多步之后边界偏好会复合:第一步在位置处插入时 assoc=1 把位置推到插入内容之后,第二步又在那里插入时继续往后推。也就是说 assoc 表达的是「相对于所有在这些边界上插入的内容,我站哪边」,对链里每一张 map 生效。

mapResult 无条件走内部的 _map,因为它要累计删除信息。_map 的骨架:

for (let i = this.from; i < this.to; i++) {
  let map = this._maps[i], result = map.mapResult(pos, assoc)
  if (result.recover != null) {
    let corr = this.getMirror(i)
    if (corr != null && corr > i && corr < this.to) {
      i = corr
      pos = this._maps[corr].recover(result.recover)
      continue
    }
  }
  delInfo |= result.delInfo
  pos = result.pos
}
return simple ? pos : new MapResult(pos, delInfo, null)

先忽略镜像分支。每一步拿到 MapResult,delInfo 用按位或累计下来,pos 更新后继续。最终返回的 MapResult 里 recover 字段固定是 null:recover 值只在管线内部流转,出了 Mapping 就没有意义,因为解码它依赖生成它的那张具体 StepMap。

删除信息的累计语义因此是「整串步骤里,这个位置经历过什么」。第一步被删了左边,第三步被删了右边,最后 deletedBefore 和 deletedAfter 都为真。调用方拿这个判断位置记录还靠不靠谱,比如 AttrStep.map 里那个 deletedAfter 检查,穿过多步后依然成立。对应的代价是,多步的 MapResult 不再带 recover(返回值里固定 null),想恢复位置只能靠镜像机制在管线内部完成,出了 Mapping 就没有找回的机会了。

镜像分支:被删的位置在逆步处找回

镜像分支是 _map 里最值得逐行读的几行。触发条件是三个同时成立:当前这张 StepMap 的 mapResult 带出了 recover 值(pos 落在被删区间内部;落在 assoc 指向那侧边界上的位置没有 recover,它本来就能映射到区间边上);这张 map 登记了镜像(getMirror(i) 有值);镜像在后方且在映射范围内(corr > i 且 corr < this.to)。

三个条件都在说同一件事:后面有一步会把当前这一步逆过来,而且这次映射会经过它。成立时的动作是:i 直接跳到镜像下标,pos 用镜像那张 map 的 recover 方法解码回原位置,continue 进入下一轮循环(i++ 之后从镜像的下一张继续)。中间那些步被整个跳过,删除步的 delInfo 累计也被 continue 跳过去了。这一点很讲究:从调用方看,这个位置最终活着出来了,中间那次删除被逆步抵消,不该在结果里留下「被删过」的标记。

Mapping 的镜像跳转

拿一组具体数字把跳转走一遍。设管线里有三张 map:maps[0] 是删除区间 [10, 16) 的 map,ranges 为 [10, 6, 0];maps[1] 是在 2 处插入 4 个位置的 map,ranges 为 [2, 0, 4];maps[2] 是在 14 处插入同样 6 个位置内容的 map,ranges 为 [14, 0, 6],并且 setMirror(0, 2) 登记了这对镜像。这个三段结构就是 rebase 里「撤销本地、应用远端、重做本地」拼出来的样子,maps[0] 撤销的内容和 maps[2] 重做的内容是同一份,只是位置挪了。

映射 p = 13。maps[0] 里 13 落在被删区间内部,偏移 3,mapResult 带回 recover = makeRecover(0, 3)。_map 查到 getMirror(0) = 2,满足 2 > 0 且 2 < to,于是跳过 maps[1],直接调 maps[2].recover:第 0 个区间的 start 是 14,前面没有别的区间,diff 为 0,加上偏移 3,得 17。continue 之后循环从 maps[3] 继续,这里没有更多 map,映射结束。13 是原内容里偏移 3 的位置,重做后内容在 [14, 20),偏移 3 正好是 17,对上了。

该例说明 recover 的约束:两张互为镜像的 map 必须描述同一份内容,区间内偏移才有意义。maps[0] 的第 0 个区间与 maps[2] 的第 0 个区间对应同一段内容,recover 值中的「区间下标 + 区间内偏移」才能直接用于镜像 map。登记镜像的调用方需要保证这一点。重做时 step 可以被映射到新位置;Step.map 只修改作用区间,不改变内容本身。映射返回 null 的 step 已被其他修改覆盖,不会重做或登记镜像,对应位置按普通删除处理。

还要注意 recover 解出来的是穿过镜像 map 之后的文档坐标。maps[2].recover 的非 inverted 分支会把区间 start 加上前面区间的净变化,落在这张 map 之后文档里内容所在的位置,所以 continue 之后可以直接拿它继续喂给后面的 map,坐标系是衔接的。

corr < this.to 这个条件单看不起眼,配上 slice 就有意义了。slice(from, to) 返回一个共享底层数组、只圈定窗口的 Mapping。窗口外的镜像不会被跳转,位置被删了就是真的被删了,按正常路径累计 delInfo。部分映射因此是安全的:圈一段出来映射,语义和整段映射在该窗口内的部分一致,不会因为窗口外的逆步产生错误找回。

谁在生产镜像对:rebase 的三段式

镜像对通常由「撤销一批步骤、应用另一批步骤、再重做前一批步骤」的 Transform 流程产生。协作场景中,本地存在未提交 step 而远端 step 到达时,rebase 会依次逆序应用本地 step 的逆步骤、应用远端 step,再将本地 step 逐张映射到当前 mapping 后重新应用。完成后,Transform 的 mapping 包含本地逆步骤、远端步骤和重做后的本地步骤三段。撤销段第 i 张 map 与重做段对应的 map 互为镜像,rebase 代码使用 setMirror 在 mirror 数组中记录其下标。

登记完之后,任何以「rebase 前文档」为基准的位置,map 过这个 mapping 就能直接得到「rebase 后文档」里的正确位置:没被本地修改影响的位置顺序穿过三段,每段正常映射;落在被撤销区域里的位置走镜像跳转,跳过中间所有步直接回到原坐标。选区就是这么跟过 rebase 的。这里只交代 Mapping 提供的机制,完整的收发循环和步骤变换后面协作篇展开。

slice 在这个流程里的用途也值得看一眼。重做每个本地 step 时,要用 step.map(mapping.slice(mapFrom)) 把它映射到当前文档。mapFrom 的初值是撤销段的长度,每重做一张就减一:撤销段是逆序追加的,第 i 张本地 step 的逆在撤销段里的下标是 steps.length - 1 - i,重做第 i 张时窗口从下标 steps.length - i 开始,正好把它自己的逆步留在窗口外,只穿过别人的逆步、远端段和已重做的部分。自己的逆步描述的是自己原本做的修改,拿它映射自己会把区间挪错。slice 返回的是共享数组的视图,不开新数组,配合前面说的写时复制,appendMap 不会污染原 mapping。

历史管理是另一个消费者。undo 栈里每个条目存一张 map,有的条目带 mirrorOffset,声明自己是栈上之前第几个条目的逆,历史栈被 rebase、条目需要保留重放时会产生这种配对。把一段历史条目拼成 Mapping 时(Branch.remapping),mirrorOffset 被翻译成 appendMap 的 mirrors 参数,选区书签这类位置记录穿过这对互逆的 map 时就能找回被删的位置,而不是映射到区间边界上丢信息。具体的数据结构放到历史篇再拆。

追加与整体求逆

Mapping 自身的组装方法有三个,都在维护镜像信息。

appendMap(map, mirrors) 前面提过:写时复制之后 push,mirrors 给了就 setMirror。这是逐张追加的入口。

appendMapping(mapping) 把另一个 Mapping 的全部 map 接过来。镜像对要重排下标:原 Mapping 里 maps[j] 的镜像在新数组里应该变成 startSize + j。实现里有个方向过滤,只保留 mirr < i 的对,也就是镜像指向前方已追加的 map 时才登记。这不算丢信息:镜像对是对称的,getMirror 两个方向都能查,处理到靠后的那张时把整对登记一次就够了,处理靠前那张时它的镜像还没进新数组,登记了也是悬空下标。

appendMappingInverted(mapping) 把另一个 Mapping 逆序、逐张 invert 之后接过来,等于接上对方的逆映射。下标换算跟着反过来:原数组下标 j 在新数组里落在 totalSize - j - 1,镜像的过滤方向也跟着变成 mirr > i。invert() 方法就是新建一个空 Mapping,对自己调一遍 appendMappingInverted,得到整体逆映射,把位置从最终文档映回最初文档。

这三个方法都不做深拷贝,StepMap 对象本身是不可变的(ranges 数组构造后不改,invert 也只是翻转标志位共享数组),共享是安全的。整条链上需要拷贝的只有下标数组和 mirror 数组,成本很低。

小结

Mapping 有两种处理路径。没有镜像时,位置依次经过每张 StepMap,delInfo 按位或累计。有镜像时,被删除的位置取得 recover 值后查询镜像表;命中时跳至逆步骤处恢复坐标,并跳过中间变换。这样,撤销后重做的过程可以保留位置的映射关系。下一篇分析 structure.ts 中 split、join、lift、wrap 的可达性判断;随后介绍将 Step、StepMap 和 Mapping 组织为 API 的 Transform 类。


867 字 · 38 段落
ximing

Follow onGitHub

相关文章