MoonBit Diff

MoonBit Diff 是一个无第三方依赖的 MoonBit 文本差异库，提供 Unicode 安全的字符级编辑脚本、脚本压缩与统计、文本往返重建，以及支持自定义文件名、上下文行数和多 hunk 的 Unified Diff 渲染。

A dependency-free, Unicode-safe text diff and Unified Diff library for MoonBit.

功能概览

能力	API	说明
字符级差异	`diff`	返回最短的 `Equal/Delete/Insert` 编辑脚本
相邻操作合并	`compact`	将逐字符操作合并为适合展示和传输的文本片段
文本重建	`reconstruct_old/new`	从编辑脚本恢复修改前或修改后的文本
差异统计	`stats`	统计相同、删除、插入的 Unicode 字符数
校验并应用	`apply`	将脚本应用到源文本，不匹配时返回结构化错误
反向脚本	`invert`	交换插入和删除，用于从新文本恢复旧文本
全量 Unified Diff	`unified_diff`	使用默认标签并输出覆盖全部输入的单个 hunk
上下文 Unified Diff	`unified_diff_with_context`	自定义标签和上下文，远距离修改自动拆分为多个 hunk
标准 Unified Diff	`unified_diff_standard`	保留 EOF 换行状态并输出无末尾换行 marker

安装

从 mooncakes.io 安装已发布版本：

moon add pei0331/moonbit_diff@0.5.0

在使用方的 moon.pkg 中导入：

import {
  "pei0331/moonbit_diff" @diff,
}

快速开始

let edits = @diff.diff("Moon😀 diff", "Moon🌕 patch")
let compacted = @diff.compact(edits)

for edit in compacted {
  match edit {
    Equal(text) => println("Equal(\{text})")
    Delete(text) => println("Delete(\{text})")
    Insert(text) => println("Insert(\{text})")
  }
}

输出：

Equal(Moon)
Delete(😀)
Insert(🌕)
Equal( )
Delete(diff)
Insert(patch)

diff 保留细粒度的一字符一操作语义，适合精确定位；compact 只合并相邻的同类操作，不改变编辑脚本代表的新旧文本。

文本重建与统计

let edits = @diff.diff("A😀bc", "A😀🌕d")

assert_eq!(@diff.reconstruct_old(edits), "A😀bc")
assert_eq!(@diff.reconstruct_new(edits), "A😀🌕d")

let summary = @diff.stats(edits)
println("equal: \{summary.equal_count}")
println("deleted: \{summary.delete_count}")
println("inserted: \{summary.insert_count}")

stats 同时接受原始脚本和 compact 后的脚本，始终按 Unicode scalar value 计数，而不是按 UTF-16 code unit 计数。

应用与反转编辑脚本

apply 在生成结果的同时验证脚本中的 Equal 和 Delete 是否与指定源文本完全一致，因此适合在脚本跨进程、持久化或延迟执行时防止误应用：

let old_text = "Moon😀 diff"
let new_text = "Moon🌕 patch"
let edits = @diff.diff(old_text, new_text) |> @diff.compact

match @diff.apply(edits, old_text) {
  Ok(result) => println(result)
  Err(_) => println("source and edit script do not match")
}

let reverse_edits = @diff.invert(edits)
assert_eq!(@diff.apply(reverse_edits, new_text), Ok(old_text))

apply 可能返回三类错误：

错误	含义
`SourceExhausted(offset, expected)`	源文本提前结束
`SourceMismatch(offset, expected, actual)`	指定 Unicode 字符与源文本不同
`SourceNotFullyConsumed(offset, remaining)`	脚本结束后源文本仍有剩余

错误偏移量和其他字符级 API 一样，按 Unicode scalar value 计数。apply 同时支持 diff 产生的逐字符脚本与 compact 产生的合并脚本。

Unified Diff

简单全量输出

unified_diff 适合短文本和教学示例。它使用 old、new 作为文件标签，并在一个 hunk 中展示全部行：

let patch = @diff.unified_diff(
  "one\ntwo\nthree",
  "one\n2\nthree",
)
println(patch)

--- old
+++ new
@@ -1,3 +1,3 @@
 one
-two
+2
 three

自定义上下文与多 hunk

较长文件建议使用 unified_diff_with_context：

let patch = @diff.unified_diff_with_context(
  old_source,
  new_source,
  "src/before.mbt",
  "src/after.mbt",
  3,
)

最后一个参数是每处修改前后的上下文行数。相距较远的修改会生成独立 hunk，重叠的上下文窗口会自动合并。负数上下文按 0 处理。文件标签中的 CR/LF 会替换成空格，避免破坏补丁头部结构。

两种 Unified Diff API 都会先将 CRLF、LF 和 CR 归一化为 LF；归一化后内容相同时返回空字符串。

标准 EOF 换行语义

需要让输出与常见 diff -u 工具互操作时，使用 unified_diff_standard。它会区分 "a" 与 "a\n"，并为未以换行符终止的行输出约定 marker：

let patch = @diff.unified_diff_standard(
  "value=old",
  "value=new\n",
  "a/config.txt",
  "b/config.txt",
  3,
)

--- a/config.txt
+++ b/config.txt
@@ -1,1 +1,1 @@
-value=old
\ No newline at end of file
+value=new

unified_diff 和 unified_diff_with_context 保留早期版本的简化行为；新代码如需准确表达文件末尾换行状态，建议优先使用 unified_diff_standard。

Unicode 语义

MoonBit 的 String.length() 返回 UTF-16 code unit 数量，直接按索引切片可能把非 BMP 字符拆成无效代理片段。本库先通过 String::to_array() 转换为 Array[Char]，因此 😀、🌕、𐐷 等字符始终作为完整操作输出。

这里的“字符”指 Unicode scalar value，不是扩展字素簇。由多个 scalar value 组成的用户感知字符，例如带肤色修饰符的 emoji、国旗和 ZWJ 家庭 emoji，可能产生多个编辑操作；可用 compact 合并相邻同类操作，但本库目前不执行字素簇分段。

API 参考

pub(all) enum EditOp {
  Equal(String)
  Delete(String)
  Insert(String)
}

pub(all) enum ApplyError {
  SourceExhausted(Int, String)
  SourceMismatch(Int, String, String)
  SourceNotFullyConsumed(Int, String)
}

pub(all) struct DiffStats {
  equal_count : Int
  delete_count : Int
  insert_count : Int
}

pub fn diff(String, String) -> Array[EditOp]
pub fn compact(Array[EditOp]) -> Array[EditOp]
pub fn reconstruct_old(Array[EditOp]) -> String
pub fn reconstruct_new(Array[EditOp]) -> String
pub fn stats(Array[EditOp]) -> DiffStats
pub fn apply(Array[EditOp], String) -> Result[String, ApplyError]
pub fn invert(Array[EditOp]) -> Array[EditOp]
pub fn unified_diff(String, String) -> String
pub fn unified_diff_with_context(
  String,
  String,
  String,
  String,
  Int,
) -> String
pub fn unified_diff_standard(String, String, String, String, Int) -> String

完整导出接口也可通过以下命令生成和查看：

moon info

可运行示例

仓库中的 examples/basic 覆盖差异计算、压缩、统计、文本重建和上下文 Diff：

moon run examples/basic

算法与复杂度

字符级和行级差异共用 Myers 最短编辑路径算法。
设新旧序列总长度为 N+M，最短编辑距离为 D，时间复杂度为 O((N+M)*D)，路径回溯空间复杂度为 O((N+M)*D)。
当修改量远小于文本长度时，D 较小，不再分配完整的 N*M LCS 矩阵。
最坏情况下 D 接近 N+M，时间和 trace 空间仍可能达到二次规模。
字符级 API 会先剥离公共前缀和后缀，因此局部修改通常只需处理较短的中间区间。
当前实现适合配置文件、源码片段、日志片段和中小型文本。
对超大文件或完全不同的长文本，建议先按块或按行缩小范围，避免保存过大的路径 trace。
Unified Diff 是渲染输出 API，当前不提供补丁解析或补丁应用功能。

算法设计、路径回溯和 hunk 聚合过程详见 docs/ALGORITHM.md。

开发与验证

安装 MoonBit 工具链后运行：

moon fmt --check
moon check --deny-warn
moon build --target wasm-gc
moon test --target wasm-gc
moon run examples/basic

CI 还会在 wasm-gc、js 和 native 后端执行构建与测试。贡献流程参见 CONTRIBUTING.md，版本变化参见 CHANGELOG.md。

仓库与发布

GitHub: https://github.com/pei0331/moon-diff
GitLink: https://gitlink.org.cn/peiyuran/moon-diff
Mooncakes: pei0331/moonbit_diff

License

Apache-2.0，详见 LICENSE。