Documentation
¶
Overview ¶
Myers diff 算法实现 -- An O(ND) Difference Algorithm (Myers, 1986).
核心思想:在编辑图(edit graph)中寻找最短编辑路径. 编辑图的 x 轴是旧文本行号,y 轴是新文本行号. 每一步可以向右(删除),向下(插入),或对角线(相同行跳过). Myers 算法贪心地按编辑距离 d = 0, 1, 2, ... 扩展,找到最短路径.
精妙之处(CLEVER): 算法复杂度 O(ND),其中 N 是两文本长度之和, D 是最小编辑距离.对于相似文件(D 很小),速度远快于 O(N^2).
大文件降级策略:如果两文本行数之和 > 10000,降级到简单的首尾匹配 + 中间全替换. 这是实用主义的妥协 -- 万行级别的完整 Myers diff 既慢又无意义 (人类根本看不懂那么长的 diff).
patch.go -- 从编辑脚本生成结构化 patch(多 hunk 支持).
核心抽象:Hunk(差异块).一个 patch 由多个 hunk 组成, 每个 hunk 代表文件中一个连续的变更区域(含上下文行).
精妙之处(CLEVER): hunk 合并策略 -- 相距 <= 2*contextLines 的变更区域 合并为同一个 hunk.这避免了大量碎片化的小 hunk,让 diff 输出更紧凑可读. 2*contextLines 的阈值来源:两个相邻变更各自需要 contextLines 行的 后文/前文上下文,如果这两段上下文会重叠,不如合并成一个 hunk.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ApplyPatch ¶
ApplyPatch 将结构化 hunks 应用到 oldText,生成修补后的新文本.
这是 StructuredPatch 的逆操作:
ApplyPatch(old, StructuredPatch(old, new, ctx)) == new
算法:
- 将 oldText 按行拆分
- 按 OldStart 排序 hunks(防御乱序输入)
- 逐 hunk 顺序处理: - 复制 hunk 前的不变行 - " " 上下文行: 校验必须匹配 oldText 对应行 - "-" 删除行: 校验必须匹配, 从结果中跳过 - "+" 插入行: 写入结果
- 复制最后一个 hunk 后的剩余行
精妙之处(CLEVER): 上下文行校验不是多余的防御 -- 它是"这个 patch 还能用吗" 的运行时检测. 原文被其他人改过? 上下文失配, 立即报错, 不会静默产生垃圾. 这与 git apply --check 的理念一致: 宁可拒绝, 不可误用.
ELEVATED: 不只是代码 patching -- 这是变更管理的"应用"原语. 法律合同修订/医疗处方变更/财务报表修正, 任何需要"可验证地应用一组结构化变更" 的领域都是这个函数的消费者. Diff 是"描述变更", ApplyPatch 是"执行变更".
func FormatUnified ¶
FormatUnified 将 hunks 格式化为 unified diff 文本. 输出格式遵循 GNU diff 的 unified format 标准.
精妙之处(CLEVER): 空 hunks 返回空字符串(不是带 header 的空 diff), 避免消费方看到只有 header 没有内容的无意义 diff.
Types ¶
type Edit ¶
type Edit struct {
Type EditType // 操作类型:相同 / 删除 / 插入
Content string // 行内容(不含换行符)
OldLine int // 在旧文本中的行号(从 1 开始,插入行为 0)
NewLine int // 在新文本中的行号(从 1 开始,删除行为 0)
}
Edit 表示单个编辑操作.
type Hunk ¶
type Hunk struct {
OldStart int // 旧文本中的起始行号(从 1 开始)
OldLines int // 旧文本中的行数(含上下文)
NewStart int // 新文本中的起始行号(从 1 开始)
NewLines int // 新文本中的行数(含上下文)
Lines []string // 差异行:" context" / "-deleted" / "+added"
}
Hunk 是一个差异块,包含变更行及其上下文.
func ReverseHunks ¶
ReverseHunks 反转 hunks 的方向: "+" 变 "-", "-" 变 "+", OldStart/OldLines 与 NewStart/NewLines 互换.
精妙之处(CLEVER): 结合 ApplyPatch 实现对称 undo, 无需存储完整快照:
ApplyPatch(newText, ReverseHunks(hunks)) == oldText
原方案(LEGACY): fileedit 当前用完整快照做 undo(存整个旧文件内容). 快照 undo 简单但 O(fileSize) 空间; patch-based undo 是 O(diffSize) 空间. 对于"改了一行的万行文件", patch undo 比快照节省 99.99% 存储.
Source Files