#moon_ycrdt

English summary — moon_ycrdt is a MoonBit CRDT library that reads and writes the Yjs v1 binary update format and the y-protocols sync messages, so MoonBit programs can collaborate with Yjs-based editors, y-websocket servers and Yrs backends. Text, Map and Array editing produce byte-identical updates to Yjs; content it does not model (formatting, embeds, XML, sub-documents) is preserved. Every expected value in the test suite is generated by the official Yjs packages.

#目录

• 定位
• 安装
• 快速上手
• 更新格式 v2 与不加载文档的更新操作
• 对接 y-websocket
• 可运行示例
• 协作编辑演示：y-websocket 服务端
• API 速查
• 支持范围
• 工作原理
• 性能
• 测试
• 开发
• 重新生成 fixtures
• 参考与许可证

#定位

#和 MoonBit 生态中已有 CRDT 库的区别

#安装

moon add sayoi7799/moon_ycrdt

import {
  "sayoi7799/moon_ycrdt/lib0",
  "sayoi7799/moon_ycrdt/doc",
  "sayoi7799/moon_ycrdt/types",
  "sayoi7799/moon_ycrdt/protocol",
}

#快速上手

// two replicas, each with its own 32-bit client id
let alice = @doc.Doc::new(1001)
let bob = @doc.Doc::new(2002)

// every local transaction produces a Yjs v1 update, like doc.on('update')
let outbox : Array[Bytes] = []
alice.on_update((update, is_local) => if is_local { outbox.push(update) })

let text = @types.Text::new(alice, "doc")
text.insert(0, "Hello world")
text.delete(5, 6)
@types.YMap::new(alice, "settings").set("theme", String("dark"))
@types.YArray::new(alice, "list").push([@lib0.Any::int(1), String("two")])

// apply updates from MoonBit or Yjs; missing dependencies wait in a queue
for update in outbox {
  bob.apply_update(update)
}
// bob's text is now "Hello"

// state-vector sync: send only what the other side is missing
let diff = @doc.encode_state_as_update(
  alice,
  target_state_vector=bob.encode_state_vector(),
)
bob.apply_update(diff)

#富文本

let doc = @doc.Doc::new(1)
let text = @types.Text::new(doc, "doc")
text.insert(0, "Hello world")
// format a range, insert with exactly the given formatting
text.format(0, 5, [("bold", Bool(true))])
text.insert_with_attributes(11, "!", [("italic", Bool(true))])
// a Quill-style delta: skip 6 positions, then insert coloured text
text.apply_delta([Retain(6, []), Insert(String("brave "), [("color", String("red"))])])
// read the formatted text back, as a delta and as JSON
let delta = text.to_delta()
let json = @types.delta_to_json(delta).stringify()
// [{"insert":"Hello","attributes":{"bold":true}},{"insert":" "},
//  {"insert":"brave ","attributes":{"color":"red"}},{"insert":"world"},
//  {"insert":"!","attributes":{"italic":true}}]
let parsed = @types.delta_from_json(@json.parse(json))

#更新格式 v2 与不加载文档的更新操作

• merge_updates(updates)：合并成一个更新，重叠的部分切开，空洞补上 Skip，删除集取并集（Y.mergeUpdates）；
• diff_update(update, state_vector)：只留下对方还没有的部分（Y.diffUpdate）；
• encode_state_vector_from_update(update)：这个更新单独能推出的状态向量（Y.encodeStateVectorFromUpdate）。

let v2 = alice.encode_state_as_update_v2()
bob.apply_update_v2(v2)

// work on updates as bytes: no document is needed
let merged = @update.merge_updates(updates)
let sv = @update.encode_state_vector_from_update(merged)
let missing = @update.diff_update(merged, bob.encode_state_vector())

• Yjs 读出一个更新后，会忘记"这个 map 条目带 key"那一位（有 origin 的条目线上不写 key，只在 info 字节里留一位）。 所以凡是"读出再写回"的操作（合并、差量、v1 与 v2 转换，以及带 pending 数据的 encode_state_as_update）写出的 字节里这一位都是清掉的；直接解码再编码（decode_update 后 encode）则保留原样。
• merge_updates 只有一个输入时原样返回输入，不重新编码。
• Embed 和格式属性的值在 v1 里是 JSON 文本，在 v2 里是 Any。本库把它们存成 JSON 文本，所以 v2 里不能用 JSON 表示的值 （Infinity、undefined、字节数组等）读出来会变成 JSON 能表示的样子，重新编码后与原字节不同。

#对接 y-websocket

let doc = @doc.Doc::new(42)

// 1. on connect, send SyncStep1 (our state vector)
send(@protocol.Sync(@protocol.sync_step1(doc)).encode())

// 2. broadcast every local change as an Update message
doc.on_update((update, is_local) => {
  if is_local {
    send(@protocol.Sync(@protocol.update_message(update)).encode())
  }
})

// 3. handle every received frame; send back the reply, if any
//    (SyncStep1 is answered with SyncStep2; SyncStep2 / Update are applied)
if @protocol.handle_ws_message(doc, frame) is Some(reply) {
  send(reply)
}

#可运行示例

moon run examples/concurrent

cd scripts && npm ci && cd ..

node scripts/make_example_input.mjs > input.txt

moon run examples/roundtrip -- "$(cat input.txt)"

node scripts/read_update.mjs "<示例输出的 base64>" doc

import * as Y from 'yjs'
const doc = new Y.Doc()
Y.applyUpdate(doc, new Uint8Array(Buffer.from(base64, 'base64')))
console.log(doc.getText('doc').toString()) // "hello, Alice, Bob world"

#协作编辑演示：y-websocket 服务端

cd examples/ws_server

moon run --target native . -- --port 1234 --data ./data

cd examples/web

npm ci

npm run dev

• 连接路径就是房间名（ws://host:port/<房间名>），每个房间一个 Doc；房间名最长 40 个 UTF-16 码元。
• 新连接先收到服务端的 SyncStep1；客户端的 SyncStep1 由 handle_sync_message 回复 SyncStep2；SyncStep2 和 Update 应用到文档，Doc::on_update 把结果作为 Update 广播给同房间的其他连接（不回给发送者）。
• awareness 消息不解析，原样转发给同房间的其他连接。服务端不记录各客户端的 awareness 状态，所以新连接看不到之前 已在线的光标（演示的网页没有用 awareness）。
• 每个房间保存为 <data>/<房间名转义后>.ydoc，内容是 encode_state_as_update 的结果，所以可以直接用 Y.applyUpdate 读取。先写 .tmp 再改名，中途崩溃不会留下写了一半的文件；第一个客户端进入房间时从文件恢复。 保存间隔内的改动在进程被强杀时会丢失。
• 没有认证、没有 TLS，只适合本机或可信网络。

cd examples/ws_server && moon build --target native

cd examples/web && npm run e2e -- ../ws_server/_build/native/debug/build/sayoi7799/moon_ycrdt_ws_server/moon_ycrdt_ws_server.exe

#API 速查

#支持范围

• Yjs 的定位缓存（search marker）与带格式的文本：本库实现了 Yjs 的 search marker：每个 Y.Text / Y.Array 最多 80 个，选择最近的 marker、移动或替换最久未用的、本地编辑后平移、合并 Item 时调整、远端更新后清空， 规则逐条按 AbstractType.js 移植。这不只是为了速度：Yjs 里不带属性的 insert 和 delete 通过 marker 定位， 带属性的 insert、format 和 applyDelta 不用；marker 从目标位置附近开始，看不到它左边的格式项，所以带格式的 文本里"新文本继承什么格式"取决于 marker 在哪里。marker 属于某一个 JS 对象，规律是：
  1. 一个 YText 对象一旦整合过任何格式项（本地的或远端更新里的），marker 就被永久关闭，之后所有定位都从头 累积属性，结果是确定的。先调用 getText 再同步更新（编辑器绑定的通常用法）就是这种情形，本库与 Yjs 逐字节一致 （300 组随机并发场景和各组脚本）。
  2. 例外：根类型在内容到达之后才调用 getText。 Yjs 此时用一个新对象替换占位类型：marker 是开着的，而且这个 对象还没有"含格式"标志，所以不带属性的 insert 和 delete 看不到 marker 左边的格式；远端更新后的格式清理 也要等到整合第一个新的格式项才开始。本库实现了这两点，marker 在多次操作之间累积、被替换（超过 80 个）、 被远端更新清空的行为也一致：20 组各约 100 步的长序列与 Yjs 逐步一致（改动 marker 的上限、清空规则或最近 marker 的取舍，其中至少一个测试会失败）。"没有含格式标志所以不清理"这一条仍没有专门的测试覆盖。
• 对象或数组形式的属性值：Yjs 在格式清理里用 === 比较解码出的值。同一个 JS 对象被两个格式项共用时 （例如 format 为恢复旧值会重用已有格式项的值对象）它们被认为相同；编码后的数据里看不出共用，本库把对象和数组 视为恒不相同。这只影响清理时多余格式项的取舍，不影响文本和格式的收敛。布尔、数字、字符串和 null 完全一致； "属性是否已经生效"的判断（equalAttrs）按 Yjs 的规则只比较一层。
• 属性的键顺序：属性按给定的顺序写入，和 JS 对象一致，只是 JS 会把整数形式的键（如 "1"）排在最前面按数值 升序，本库没有模拟。
• delta 里的嵌套类型：文本里嵌入的共享类型在 to_delta 里读作 Insert(Undefined, …)；to_delta 不支持 snapshot 和 ychange。
• Yjs 自身的行为：并发编辑把一个 emoji 切成两半时，各个 Yjs 副本看到的文本可能不一致（一边保留 emoji，另一边是 两个 U+FFFD），与格式无关。我们在随机测试里观察到过（最初的 300 组里有 14 组），本库不试图修正它。富文本随机测试 因此把位置限制在字符边界上；代理对被切开的情形由边界情况测试覆盖。
• Yjs 的数组不接受 undefined 和 bigint；本库照常把它们编码进数组（Yjs 能解码）。
• 不检测 client id 冲突（Yjs 会在冲突时换 id）。每个副本应使用随机的 32 位 client id， examples/roundtrip 演示了用 @env.rand 生成。
• 更新格式 v2 里的 JSON 值：Embed 和格式属性的值在 v1 里是 JSON 文本，在 v2 里是 Any。本库存成 JSON 文本，所以 v2 里不能用 JSON 表示的值（Infinity、undefined、字节数组）读出来会变成 JSON 能表示的样子，重新编码后与原字节不同。 v2 编码器里记住用过的键的那一行在 Yjs 里是被注释掉的，所以每个键都当新键写，本库照搬；解码时两种都认。
• merge_updates：两个输入在同一位置分别是 GC 和 Item 时，Yjs 的排序比较函数本身不自洽，本库用稳定的插入排序， 没有照搬 V8 的排序实现；"延长已有 Skip"这个分支没有测试能走到（在实际输入里几乎不会出现）。
• 性能：随机位置编辑已经与 Yjs 同一量级（见性能），但长文档（10 万字符）上的随机插入删除比 Yjs 慢约 2.3 到 2.9 倍，加载和导出整个文档约慢 2 倍。search marker 把沿链表走的步数降到每次约 18 步；剩下的主要是每个 client 的 struct 数组在中间插入（拆分）和删除（合并）一项时要移动后面的元素。

#工作原理

#性能

moon bench -p sayoi7799/moon_ycrdt/benchmarks --target native --release

#与 Yjs 的对比

cd scripts && npm ci && cd ..

node scripts/bench_yjs.mjs

• 逐字输入、短文档的随机插入和删除、Map、Array 与 Yjs 在同一量级，有的略快；
• 加载（apply_update）和导出整个文档比 Yjs 慢约 2 倍，我没有分析原因；
• 10 万字符 / 10 万个值上的随机插入删除慢约 2.3 到 2.9 倍。这一项我分析过：search marker 之后沿链表走的步数不是瓶颈， 剩下的是 struct 数组在中间插入和删除的开销（见上面"为什么只快了 3.5 到 4 倍"）。
• 两个运行时不同（native 与 JIT），表只说明量级，不是同一条件下的严格对比。

#测试

#开发

moon check --deny-warn --target all

moon build --target all

moon test --target all

moon fmt --check

moon info && git diff --exit-code

moon run cmd/export --target native > fixtures/moonbit_out.json

node scripts/verify_moonbit.mjs fixtures/moonbit_out.json

#重新生成 fixtures

• 生成脚本：scripts/gen_fixtures.mjs
• 版本：yjs@13.6.33、lib0@0.2.119、y-protocols@1.0.7，固定在 scripts/package.json 和 package-lock.json
• 输出：fixtures/*.json（可读的记录），以及内嵌同样数据的 MoonBit 文件 lib0/lib0_gen_test.mbt、update/updates_gen_test.mbt、protocol/protocol_gen_test.mbt、 tests/interop_gen_test.mbt、tests/convergence_gen_test.mbt、tests/edge_gen_test.mbt、 tests/preserve_gen_test.mbt、tests/arrays_gen_test.mbt、tests/rich_*_gen_test.mbt、 tests/readme_rich_gen_test.mbt、cmd/export/yjs_base_gen.mbt （wasm-gc 后端的测试读不了文件，所以数据生成为代码）

cd scripts && npm ci && node gen_fixtures.mjs && cd .. && moon fmt

#参考与许可证