Outline 中 vendorized rfc6902RFC 6902 JSON Patch 的完整实现与数组 Diff 性能优化实录【免费下载链接】outlineThe fastest knowledge base for growing teams. Beautiful, realtime collaborative, feature packed, and markdown compatible.项目地址: https://gitcode.com/GitHub_Trending/ou/outline导读本文讲解 Outline 前端代码库中shared/utils/rfc6902目录的来龙去脉它是一份vendorized供应商化/本地化内嵌的 RFC 6902 JSON Patch 实现在完整移植上游rfc6902包全部能力diff、patch、pointer、test的基础上针对diffArrays在处理大数组时递归记忆化导致内存与 CPU 爆炸的已知缺陷做了迭代式动态规划重写。读完本文你将理解为什么 Outline 要内嵌第三方库、新diffArrays算法相比旧实现赢在哪里、以及这份库又是如何支撑 Outline 编辑器协同场景的相关调用链见 recreateTransform.ts。一、这是什么一份内嵌的 RFC 6902 完整实现RFC 6902 定义了JSON Patch用一组有序的操作add、remove、replace、move、copy、test来描述如何把一份 JSON 文档变成另一份是高效同步、协同编辑、冲突检测领域的经典数据格式。Outline 并未把上游 rfc6902 作为普通npm依赖直接引用而是在仓库内维护了一份vendorized copy位置如下README.md —— 本目录的定位说明即本文讲解的主体index.ts —— 对外主入口applyPatch/createPatch/createTestsdiff.ts —— 差异计算引擎diffAny/diffArrays/diffObjects与六种 Operation 的 TypeScript 类型定义patch.ts —— 六种操作的落地执行与错误类型pointer.ts —— JSON Pointer 解析与求值util.ts —— 类型判断与深拷贝等基础工具说明本 README 中列出的上游 GitHub 链接原包、修复 PR #88、含修复的 fork属于外部来源标注本文不对其外部链接展开仅就仓库内实际存在的代码做实现级分析。二、为什么要 vendorizediffArrays的性能病根README 明确给出了内嵌的唯一动机上游rfc6902包的diffArrays函数存在性能问题。对于大型数组递归式的记忆化recursive memoization方案会消耗过量的内存与 CPU使其无法用于真实场景。所谓真实场景落到 Outline 身上非常具体把一份 ProseMirror 文档序列化成 JSON 后与另一份文档的 JSON 做全量对比其中content数组可能包含数千乃至上万个节点recreateTransform.ts 的recalculateOps就是createPatch(currentJSON, finalJSON)的直接调用处。此时递归记忆化需要为(i, j)的每一种子问题组合保存一张二维备忘表子问题数量在O(n·m)量级若实现把整棵递归树都物化下来大数组会瞬间吃穿内存递归深度与返回路径的回溯也带来大量函数调用开销与 GC 压力。因此 README 声明本 vendorized 版本吸收了PR #88的修复——用迭代式动态规划取代递归做法显著提升大型数组比较的性能。三、新实现长什么样一次 Levenshtein 风格的迭代 DP仓库内实际生效的代码位于 diff.ts 的diffArraysTL240-L395。与旧递归记忆化相比它有以下设计要点。3.1 三个降维技巧前缀裁剪、后缀裁剪、DP 网格代码先对两个数组做相同前缀/相同后缀的批量跳过L253-L273// Skip matching prefix let start 0; while ( start input_length start output_length isEqual(input[start], output[start]) ) { start; } // Skip matching suffix let input_end input_length; let output_end output_length; while (input_end start output_end start) { if (isEqual(input[input_end - 1], output[output_end - 1])) { input_end--; output_end--; } else { break; } }相等性判断复用的是es-toolkit的isEqual文件头部import { isEqual } from es-toolkit/compat与input output的引用判断不同它做的是深度值比较。裁剪之后才计算真正需要动刀的子问题规模subInput/subOutputL275-L277并开辟二维 DP 表const memo: ArrayArrayDynamicAlternative new Array(subInput 1); for (let i 0; i subInput; i) { memo[i] new Array(subOutput 1); } memo[0][0] { prevI: -1, prevJ: -1, operation: null, cost: 0 };3.2 每个格子记录代价 前驱 操作每个 DP 格子是一个DynamicAlternativeL183-L193记录到达该位置的最低累计代价、前驱坐标与一步操作interface DynamicAlternative { prevI: number; // 前驱 i 坐标-1 表示无前驱 prevJ: number; // 前驱 j 坐标-1 表示无前驱 operation: ArrayOperation | null; cost: number; // 到达该位置的总代价 }填充顺序自左上至右下每个格子只允许来自三种转移之一从而保证最短操作序列j 0只能来自左侧记removei 0只能来自上方记add把output的对应值带上其余格子若当前元素深度相等直接继承对角前驱否则在remove / add / replace三者中取cost最小者打破平局优先 remove 再 addL312-L356。关键点在于每个格子只会被计算一次配合if (memoized) continue;L289-L292避免重复计算——这正是迭代 DP 相对递归记忆化在常数与栈开销上的核心优势。3.3 回溯与填充量修正buildOperationsL195-L210从右下角沿prevI/prevJ前驱指针一路回溯、再reverse()得到正序的中间操作序列。由于add/remove会改变数组长度中间坐标必须换算为当前真实数组的下标。代码用padding已净插入量做修正例如 add 的目标下标index 1 padding若已越界则输出 JSON Patch 的数组尾部哨兵-remove 的下标则为index paddingL361-L393const padded_index array_operation.index 1 padding; const index_token padded_index input_length padding ? String(padded_index) : -;这样产出的就是真正可被 JSON Patch 语义逐条消费的path如/content/5、/content/-。3.4 源码注释里现成的复杂度论证diffArrays上方的 JSDoc 用inputABC → outputAZ画了一张 4×3 的 DP 表L212-L238并点明算法本质基于 Levenshtein 距离算法的动态规划实现input 为空则全为 add、output 为空则全为 remove。结合recalculateOps中this.ops.length * size maxComplexity的护栏recreateTransform.tsOutline 既拿到了数组越大收益越明显的新算法又为最坏情况设了熔断避免在超大文档上无界耗时。四、API 面面观diff、patch、test 三位一体尽管 README 篇幅极短目录内的实现完整承载了 RFC 6902 的全部能力。核心 API 收敛在 index.ts按功能分三组。4.1createPatch算出怎么变export function createPatch( input: unknown, output: unknown, diff?: VoidableDiff ): Operation[] { const ptr new Pointer(); return (diff ? wrapVoidableDiff(diff) : diffAny)(input, output, ptr); }diffAnydiff.ts是统一的入口按对象类型分派两个数组 →diffArrays两个普通对象 →diffObjects用subtract产出remove、add用intersection找公共键递归 diff其余含类型变化、null/undefined交叉等→ 整段replace。wrapVoidableDiffindex.ts允许调用方注入局部 diff 钩子自定义函数返回void时自动回退到默认diffAny返回数组则直接采用实现局部定制。diffObjects中一个值得注意的语义细节diff.ts 的注释值为undefined的键会被忽略以对齐 JSON 序列化丢弃undefined字段的语义。4.2applyPatch就地把它变了export function applyPatch(object: unknown, patch: Operation[]) { return patch.map((operation) apply(object, operation)); }它原地修改目标对象并针对每个 op 返回一个结果null表示成功失败则返回MissingError/InvalidOperationError/TestError之一index.ts。执行层在 patch.tsswitch按op分发到六个实现op核心语义关键边界/校验见 patch.tsadd数组下标插入或对象键赋值数组key -走push目标父级不存在 →MissingErrorL64-L75remove删除目标位置的值目标不存在 →MissingError数组按下标spliceL81-L93replace等价于 remove add但要求目标已存在数组越界或对象值缺失 →MissingErrorL107-L125move从from移到pathfrom不得是path的真前缀禁止移入自身子树→InvalidOperationErrorL140-L166copy复制from的值到path源不存在或目标父级缺失 →MissingError深拷贝后addL181-L195test校验目标位置的值与value深度相等不等 → 抛TestError(actual, expected)实现上复用diffAny判空L205-L215add/copy写入前都会经 util.ts 的clone深拷贝避免 Patch 里的value与目标对象共享引用而相互污染。4.3createTests变化前的安检快照export function createTests(input: unknown, patch: Operation[]): TestOperation[] { const tests new ArrayTestOperation(); patch.filter(isDestructive).forEach((operation) { ... }); return tests; }isDestructivediff.ts判定remove/replace/copy/move四类破坏性操作createTests为每个这类操作的path与若有from生成对应的test操作从而在正式 apply 前验证文档仍然处于生成 patch 时的状态——这正是乐观并发控制 / CAS 式冲突检测的基石如果服务端值已变test会失败本地 patch 就不应继续。4.4 JSON Pointer 层pointer.ts 实现了 RFC 6901 的指针求值。值得强调的细节转义规则~1 → /~0 → ~解码先~1后~0防止~01被错误解码编码反之L21-L36Pointer.fromJSON校验tokens[0]必须为空串否则抛Invalid JSON PointerL53-L59evaluate返回{ parent, key, value }三元组供六个 op 直接取父容器操作遍历时会跳过__proto__、constructor、prototype三个危险键L78从根上规避原型链污染类攻击——这对消费来自网络/他人文档的 Patch场景至关重要。五、在 Outline 中的真实用武之地协同与粘贴rfc6902不是被内嵌后束之高阁的工具而是贯穿 Outline 编辑器协作链路的底座。全局搜索确认其消费方集中在共享编辑器库recreateTransform.ts 在模块顶部直接import { applyPatch, createPatch } from shared/utils/rfc6902先把去掉了 mark 的两版文档toJSON()再用createPatch生成 op 序列见上文recalculateOps随后逐条applyPatch到中间 JSON边应用边尝试schema.nodeFromJSON(...) check()还原为合法 ProseMirror 文档再逐步转换为 ProseMirror 的TransformstepL104-L158。单条replace命中text叶子时还会退化为字符级/词级 diffdiffChars/diffWordsWithSpace把大段文本替换细化为最小编辑步。该重放为 step的机制被三处调用恰好覆盖了协作的三种入口multiplayer.ts —— 协同现场收到远端文档后用recreateTransform对齐本地tr支撑 Yjs 之外的二次校验ChangesetHelper.ts —— 文档变更集历史/撤销重做的步级重建PasteHandler.tsx —— 富文本粘贴后把解析结果与当前文档 diff 成最小可回放步骤。在这三条链路上大数组 diff 又快又省内存直接决定了粘贴长文、多人同时大改、历史回溯等操作的流畅度——这正是 Outline 选择 vendorize 并打上 PR #88 性能补丁的现实收益从源码调用结构看rfc6902 输出的 op 数量与文档节点规模乘积是成本上限maxComplexity正是为此设防。六、小结一次库内嵌带来什么回顾 shared/utils/rfc6902 这份 README 的决策可提炼出三点工程启示可控性优先关键路径上的算法实现一旦从黑盒依赖变为仓库内源码即可锁定行为、直接跟进上游补丁如 PR #88无需等待发版、不受 semver 范围漂移影响算法换血有据可依从递归记忆化到迭代 DP本质是把填表从隐式递归改为显式双层循环 前驱链空间仍是O(subInput × subOutput)的二维表但省去了递归栈与重复入栈出栈开销配合前缀/后缀裁剪使真实文档对比大量落在isEqual即可判等的场景上内嵌库也可自成体系diffdiff.ts、patchpatch.ts、pointerpointer.ts三层边界清晰、类型完整Operation联合类型 TestOperation/ReplaceOperation等具名导出对 Outline 而言是拿来即用、能看能改的协作基础设施。如果你要在 Outline 里进一步调试文档 diff 结果异常建议从 createTests 生成的安检清单入手验证前置状态如果要评估某次变更的成本则关注 recreateTransform.ts 的maxComplexity报错信息——这两处分别是语义正确性与性能边界最直接的观测点。【免费下载链接】outlineThe fastest knowledge base for growing teams. Beautiful, realtime collaborative, feature packed, and markdown compatible.项目地址: https://gitcode.com/GitHub_Trending/ou/outline创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
