opgrain

    JSON0 operational transformation for MoonBit

    json0
    operational-transformation
    Download zip
    Author
    Version
    0.2.0
    License
    MIT
    Last updated
    4 hours ago
    Downloads
    5

    No dependencies

    #opgrain

    看板里有两张卡片。左端把第一张卡片移到第二张之后。右端看到的是同一份初始看板,在第一张卡的标题末尾加了一个感叹号。

    {"tasks":[{"title":"A"},{"title":"B"}]}

    左操作 [{"p":["tasks",0],"lm":1}]。右操作 [{"p":["tasks",0,"title",1],"si":"!"}]。

    transform_x(left, right) 返回以下两条操作,分别用于已经应用右操作、已经应用左操作的文档。

    [ [{"p":["tasks",0],"lm":1}], [{"p":["tasks",1,"title",1],"si":"!"}] ]

    右操作的卡片索引随移动变成 1。按任一顺序应用,最终文档都是 {"tasks":[{"title":"B"},{"title":"A!"}]}。运行 看板示例 查看转换结果和最终文档。

    moon run examples/board --target js

    同一命令包含以下五个并发案例。每个案例都校验两条执行顺序得到预期看板,并检查撤销转换后的左操作能恢复右侧状态。

    看板案例可以观察到的转换规则
    移动卡片时另一端修改标题编辑路径随原卡片移动
    两端都在列表头部新增卡片同位置插入时左侧在前,右侧下标后移
    两端同时重分配负责人左侧替换获胜,并把右侧负责人记录为被替换值
    删除卡片时另一端调整工分删除载荷保留更新后的工分,撤销删除能恢复修改过的卡片
    删除标题片段时另一端在 emoji 后插入text0 按 UTF-16 偏移拆分删除,保留并发插入

    #操作入口

    Operation::parse 从 JSON0 操作数组读取已校验的组件。用 apply 得到新文档,compose 合并同一条历史中的连续操作,invert 构造逆操作。用 transform_x 计算一对并发操作,或用 transform 和明确的 Left / Right 计算单侧结果。

    let board = @opgrain.parse_json("{\"tasks\":[\"Review\"]}")
    let op = @opgrain.Operation::parse("[{\"p\":[\"tasks\",1],\"li\":\"Publish\"}]")
    let next = @opgrain.apply(board, op)
    println(@opgrain.stringify_json(next))

    安装指定版本后,在调用方的 moon.pkg 中导入 "sbqrre/opgrain"。

    moon add sbqrre/opgrain@0.2.0

    库模块名为 sbqrre/opgrain。从源代码使用时,把本库和调用方的模块放入同一个 moon.work,在调用方的 moon.mod 中声明 "sbqrre/opgrain@0.2.0",并在 moon.pkg 中导入 "sbqrre/opgrain"。

    处理离线看板时,可以用 Engine::draft 记录真实旧值,或用 Engine::diff 从两份快照生成 JSON0 操作。示例的第六个案例将卡片移动与离线标题编辑合并,跟随标题光标,再用 Journal::revert 撤销移动并保留标题编辑。详见 快照编辑、合并与位置跟踪。

    需要保留多个看板版本时,Snapshot 句柄共享未编辑分支,Draft::transaction 原子提交一组修改,Journal::compact 按绝对版本号压缩旧历史。prepare_edit 可以用实际旧值构造并验证撤销。示例还演示批量发布任务、压缩后的离线编辑合并,以及浮点舍入后的工分撤销,共 9 个案例。见 快照、事务与历史压缩。

    #互通与边界

    基准是 ot-json0@1.1.0 的发布源码。支持数字增量、对象和列表编辑、列表移动、旧式文本操作及显式 text0。每个 Engine 可以注册自己的 JSON 子类型。

    文本偏移按 UTF-16 代码单元计算。含单独代理项的线格式请用库的 parse_json / stringify_json。同一文本位置混用旧式操作和显式 text0 时,上游存在不收敛的组合。数字使用二进制双精度,舍入会影响组合和求逆。详见 API 与兼容性。

    #可复现验证

    npm --prefix test/oracle ci --ignore-scripts npm --prefix test/oracle test npm --prefix test/oracle run fixtures -- --check npm --prefix test/oracle run live npm --prefix test/oracle run extended npm --prefix test/oracle run package-smoke moon test --frozen --deny-warn --target native moon test --frozen --deny-warn --target js moon test --frozen --deny-warn --target wasm moon test --frozen --deny-warn --target wasm-gc

    MoonBit 套件读取 Node 生成的固定语料。比较操作数组时忽略 JSON 对象键的排列顺序,并单独检查应用后的语义。Node.js 只用于生成和复核测试数据。测试范围和复现细节见 测试方法。

    基准覆盖 100、1,000 和 10,000 张卡片,使用 release 构建并记录 9 批计时。运行 node benchmarks/run.mjs 可测量当前版本,node benchmarks/compare.mjs js 可与固定历史版本比较。本机实测表与成本说明见 看板工作负载基准。

    HistoryError

    pub(all) suberror HistoryError {
    InvalidHistorySnapshot(OpError)
    HistoryBusy
    RevisionOverflow
    HistoryEncodingFailed(Side, Int, OpError)
    HistoryTransformFailed(Int, Int, OpError)
    HistoryApplyFailed(HistoryPhase, Side, Int, VerificationError)
    DivergentHistory(
    Json
    ?,
    Json
    ?)
    InvalidRevisionRange(Int, Int, Int)
    HistoryInvertFailed(Int, OpError)
    HistoryUndoFailed(Int, VerificationError)
    HistoryUndoMismatch(
    Json
    ?,
    Json
    ?)
    } derive(
    Debug
    )

    HistoryError::to_repr

    automatically derived

    OpError

    pub(all) suberror OpError {
    InvalidJson(String)
    InvalidComponent(Int, String)
    InvalidPath(Array[PathSegment], String)
    UnknownSubtype(String)
    SubtypeError(String, String)
    TextMismatch(Int)
    NonFiniteNumber
    MissingRoot
    DraftBusy
    } derive(
    Debug
    )

    OpError::to_repr

    automatically derived

    TrackingError

    pub(all) suberror TrackingError {
    InvalidLocation(Int, Array[PathSegment], OpError)
    TrackingSnapshotFailed(OpError)
    TrackingApplyFailed(Int, VerificationError)
    } derive(
    Debug
    )

    TrackingError::to_repr

    automatically derived

    UndoError

    pub(all) suberror UndoError {
    ForwardRejected(VerificationError)
    InverseRejected(Int, OpError)
    UndoRejected(VerificationError)
    UndoDidNotRestore(
    Json
    ?,
    Json
    ?)
    } derive(
    Debug
    )

    UndoError::to_repr

    automatically derived

    VerificationError

    pub(all) suberror VerificationError {
    InvalidSnapshot(OpError)
    ComponentFailed(Int, Array[PathSegment], OpError)
    StalePreimage(Int, Array[PathSegment],
    Json
    ?,
    Json
    ?)
    } derive(
    Debug
    )

    VerificationError::to_repr

    automatically derived

    Component

    pub struct Component {
    // private fields
    }

    Component::from_json

    Component::get_path

    fn Component::get_path(self : Component) -> Array[PathSegment]

    Component::to_json

    DiffOptions

    pub(all) struct DiffOptions {
    text_encoding : TextEncoding
    alignment_cells : Int
    list_identity_key : String?
    prefer_number_add : Bool
    }

    DiffOptions::default

    fn DiffOptions::default() -> DiffOptions

    Draft

    pub struct Draft {
    // private fields
    }

    A detached working snapshot and the sequential JSON0 operation that produced it.

    Draft::add_number

    fn Draft::add_number(self : Draft, path : Array[PathSegment], amount : Double) -> Unit raise OpError

    Draft::append

    fn Draft::append(self : Draft, operation : Operation) -> Unit raise VerificationError

    Append an existing JSON0 operation atomically, checking its preimages.

    Draft::edit_subtype

    fn Draft::edit_subtype(self : Draft, path : Array[PathSegment], name : String, payload :
    Json
    ) -> Unit raise OpError

    Delegate a typed path and detached payload to a registered subtype.

    Draft::insert_item

    fn Draft::insert_item(self : Draft, path : Array[PathSegment], value :
    Json
    ) -> Unit raise OpError

    Draft::move_item

    fn Draft::move_item(self : Draft, path : Array[PathSegment], destination : Int) -> Unit raise OpError

    Destination is the index in the list after the move.

    Draft::operation

    fn Draft::operation(self : Draft) -> Operation

    Draft::read

    Read a value from the current document. An empty path denotes the root.

    Draft::remove

    fn Draft::remove(self : Draft, path : Array[PathSegment]) -> Unit raise OpError

    Remove an existing object member or the entire root.

    Draft::remove_item

    fn Draft::remove_item(self : Draft, path : Array[PathSegment]) -> Unit raise OpError

    Draft::replace_item

    fn Draft::replace_item(self : Draft, path : Array[PathSegment], value :
    Json
    ) -> Unit raise OpError

    Draft::set

    fn Draft::set(self : Draft, path : Array[PathSegment], value :
    Json
    ) -> Unit raise OpError

    Insert or replace an object member or the entire root.

    Draft::snapshot

    Draft::snapshot_handle

    fn Draft::snapshot_handle(self : Draft) -> Snapshot

    Draft::splice_items

    fn Draft::splice_items(self : Draft, path : Array[PathSegment], position : Int, delete_count : Int, values : Array[
    Json
    ]) -> Unit raise OpError

    Insert and remove several list items as one atomic transaction.

    Draft::splice_text

    fn Draft::splice_text(self : Draft, path : Array[PathSegment], position : Int, delete_count : Int, inserted : String, encoding? : TextEncoding) -> Unit raise OpError

    Build a text edit with offsets and counts measured in UTF-16 code units. Text0 overrides do not participate in this document-aware constructor.

    Draft::transaction

    fn Draft::transaction(self : Draft, edit : (Draft) -> Unit raise OpError) -> Operation raise OpError

    Edit an isolated candidate and record the whole delta after the callback succeeds. Reentrant writes to this draft are rejected while the callback is running.

    Engine

    pub struct Engine {
    // private fields
    }

    Each engine owns its subtype registry.

    Engine::append

    fn Engine::append(self : Engine, dest : Operation, component : Component) -> Operation raise OpError

    Engine::apply

    Engine::apply_optional

    fn Engine::apply_optional(self : Engine, snapshot :
    Json
    ?, op : Operation) ->
    Json
    ? raise OpError

    Apply an operation to a detached copy. None represents a missing root.

    Engine::apply_snapshot

    fn Engine::apply_snapshot(self : Engine, snapshot : Snapshot, operation : Operation) -> Snapshot raise OpError

    Apply by copying the edited container and each ancestor. Unedited branches are shared.

    Engine::apply_snapshot_batches

    fn Engine::apply_snapshot_batches(self : Engine, snapshot : Snapshot, operations : Array[Operation]) -> Snapshot raise HistoryError

    Validate the whole sequence before returning a new snapshot.

    Engine::apply_snapshot_verified

    fn Engine::apply_snapshot_verified(self : Engine, snapshot : Snapshot, operation : Operation) -> Snapshot raise VerificationError

    Verify preimages against the evolving snapshot before applying each component.

    Engine::apply_tracked

    fn Engine::apply_tracked(self : Engine, snapshot :
    Json
    ?, operation : Operation, locations : Array[Location]) -> TrackedApply raise TrackingError

    Apply a verified JSON0 operation and follow nodes and UTF-16 text positions.

    Engine::apply_tracked_batches

    fn Engine::apply_tracked_batches(self : Engine, snapshot :
    Json
    ?, operations : Array[Operation], locations : Array[Location]) -> TrackedApply raise TrackingError

    Follow locations through sequential batches without composing their components.

    Engine::apply_verified

    fn Engine::apply_verified(self : Engine, snapshot :
    Json
    ?, operation : Operation) ->
    Json
    ? raise VerificationError

    Apply against a private copy and verify the preimages of object and list edits. The error index refers to the operation array supplied by the caller.

    Engine::check_valid_op

    fn Engine::check_valid_op(self : Engine, value :
    Json
    ) -> Unit raise OpError

    Engine::compose

    fn Engine::compose(self : Engine, first : Operation, second : Operation) -> Operation raise OpError

    Engine::diff

    Generate a sequential JSON0 operation with correct preimages.

    Engine::draft

    fn Engine::draft(self : Engine, snapshot :
    Json
    ?) -> Draft raise OpError

    Engine::draft_snapshot

    fn Engine::draft_snapshot(self : Engine, snapshot : Snapshot) -> Draft

    Start a draft from an already validated immutable checkpoint.

    Engine::fork

    fn Engine::fork(self : Engine) -> Engine

    Fork registry membership so subsequent registrations can be managed independently.

    Engine::incremental_apply

    fn Engine::incremental_apply(self : Engine, snapshot :
    Json
    ?, op : Operation, on_step : (Operation,
    Json
    ?) -> Unit) ->
    Json
    ? raise OpError

    Engine::invert

    fn Engine::invert(self : Engine, op : Operation) -> Operation raise OpError

    Engine::invert_component

    fn Engine::invert_component(self : Engine, component : Component) -> Component raise OpError

    Engine::journal

    fn Engine::journal(self : Engine, snapshot :
    Json
    ?) -> Journal raise HistoryError

    Engine::journal_snapshot

    fn Engine::journal_snapshot(self : Engine, snapshot : Snapshot) -> Journal

    Engine::merge_histories

    fn Engine::merge_histories(self : Engine, base :
    Json
    ?, left : Array[Operation], right : Array[Operation], text_encoding? : TextEncoding?) -> HistoryMerge raise HistoryError

    Engine::merge_snapshot_histories

    fn Engine::merge_snapshot_histories(self : Engine, base : Snapshot, left : Array[Operation], right : Array[Operation], text_encoding? : TextEncoding?) -> HistoryMerge raise HistoryError

    Validate each path through the merge and return only a converged snapshot.

    Engine::new

    fn Engine::new() -> Engine

    Engine::normalize

    fn Engine::normalize(self : Engine, value :
    Json
    ) -> Operation raise OpError

    Engine::prepare_edit

    fn Engine::prepare_edit(self : Engine, snapshot : Snapshot, operation : Operation) -> UndoableEdit raise UndoError

    Construct undo from the actual preimages and verify that it restores the input. When numeric negation loses precision, undo uses a JSON0 value replacement.

    Engine::reencode_text

    fn Engine::reencode_text(self : Engine, operation : Operation, encoding : TextEncoding) -> Operation raise OpError

    Convert built-in text operations while preserving their sequential coordinates.

    Engine::register_subtype

    fn Engine::register_subtype(self : Engine, name : String, subtype : Subtype) -> Unit

    Engine::transform

    fn Engine::transform(self : Engine, op : Operation, other : Operation, side : Side) -> Operation raise OpError

    Engine::transform_component

    fn Engine::transform_component(self : Engine, c : Component, other : Component, side : Side) -> Operation raise OpError

    Engine::transform_histories

    fn Engine::transform_histories(self : Engine, left : Array[Operation], right : Array[Operation]) -> TransformedHistories raise HistoryError

    Cross two sequential histories based on the same starting revision. Left keeps its normal JSON0 tie-break priority at each crossing.

    Engine::transform_x

    fn Engine::transform_x(self : Engine, left : Operation, right : Operation) -> (Operation, Operation) raise OpError

    Returns the left operation after the right, and the right operation after the left.

    HistoryMerge

    pub struct HistoryMerge {
    // private fields
    }

    HistoryMerge::histories

    HistoryMerge::snapshot

    HistoryMerge::snapshot_handle

    fn HistoryMerge::snapshot_handle(self : HistoryMerge) -> Snapshot

    HistoryPhase

    pub(all) enum HistoryPhase {
    Original
    Transformed
    } derive(
    Debug
    )

    HistoryPhase::to_repr

    automatically derived

    InsertionAffinity

    pub(all) enum InsertionAffinity {
    BeforeInsertion
    AfterInsertion
    } derive(Eq,
    Debug
    )

    InsertionAffinity::equal

    automatically derived

    InsertionAffinity::not_equal

    fn InsertionAffinity::not_equal(x : InsertionAffinity, y : InsertionAffinity) -> Bool
    automatically derived

    InsertionAffinity::to_repr

    automatically derived

    Journal

    pub struct Journal {
    // private fields
    }

    Persistent checkpoints with absolute revision numbers and explicit compaction.

    Journal::append

    fn Journal::append(self : Journal, operation : Operation) -> Int raise HistoryError

    Journal::append_all

    fn Journal::append_all(self : Journal, operations : Array[Operation]) -> Int raise HistoryError

    Record all revisions only after every operation succeeds.

    Journal::compact

    fn Journal::compact(self : Journal, through : Int) -> Unit raise HistoryError

    Release checkpoints through a retained base revision without renumbering the head. Snapshot handles already returned remain usable.

    Journal::head

    fn Journal::head(self : Journal) -> Int

    Journal::integrate

    fn Journal::integrate(self : Journal, base : Int, incoming : Array[Operation], text_encoding? : TextEncoding?) -> Int raise HistoryError

    Journal::oldest_revision

    fn Journal::oldest_revision(self : Journal) -> Int

    The oldest revision still available for reads, rebasing and undo.

    Journal::operations

    fn Journal::operations(self : Journal, start : Int, end : Int) -> Array[Operation] raise HistoryError

    Journal::revert

    fn Journal::revert(self : Journal, start : Int, end : Int, text_encoding? : TextEncoding?) -> Int raise HistoryError

    Journal::snapshot

    Journal::snapshot_at

    fn Journal::snapshot_at(self : Journal, revision : Int) ->
    Json
    ? raise HistoryError

    Journal::snapshot_handle_at

    fn Journal::snapshot_handle_at(self : Journal, revision : Int) -> Snapshot raise HistoryError

    Return an immutable handle without materializing the document.

    Journal::undo_operation

    fn Journal::undo_operation(self : Journal, start : Int, end : Int) -> Operation raise HistoryError

    Location

    Location::equal

    fn Location::equal(Location, Location) -> Bool
    automatically derived

    Location::not_equal

    fn Location::not_equal(x : Location, y : Location) -> Bool
    automatically derived

    Location::to_repr

    automatically derived

    LocationLoss

    pub(all) struct LocationLoss {
    batch : Int
    component : Int
    reason : LossReason
    } derive(Eq,
    Debug
    )

    LocationLoss::equal

    automatically derived

    LocationLoss::not_equal

    fn LocationLoss::not_equal(x : LocationLoss, y : LocationLoss) -> Bool
    automatically derived

    LocationLoss::to_repr

    automatically derived

    LossReason

    pub(all) enum LossReason {
    ListItemRemoved
    NodeOverwritten
    OpaqueSubtype
    } derive(Eq,
    Debug
    )

    LossReason::equal

    fn LossReason::equal(LossReason, LossReason) -> Bool
    automatically derived

    LossReason::not_equal

    fn LossReason::not_equal(x : LossReason, y : LossReason) -> Bool
    automatically derived

    LossReason::to_repr

    automatically derived

    Operation

    pub struct Operation {
    // private fields
    }

    A validated JSON0 operation. Components are applied in array order.

    Operation::from_components

    fn Operation::from_components(components : Array[Component]) -> Operation

    Operation::from_json

    Operation::get_components

    fn Operation::get_components(self : Operation) -> Array[Component]

    Operation::length

    fn Operation::length(self : Operation) -> Int

    Operation::parse

    fn Operation::parse(source : String) -> Operation raise OpError

    Operation::shatter

    fn Operation::shatter(self : Operation) -> Array[Operation]

    Operation::stringify

    fn Operation::stringify(self : Operation) -> String raise OpError

    Operation::to_json

    PathSegment

    pub(all) enum PathSegment {
    Key(String)
    Index(Int)
    } derive(Eq,
    Debug
    )

    PathSegment::equal

    fn PathSegment::equal(PathSegment, PathSegment) -> Bool
    automatically derived

    PathSegment::not_equal

    fn PathSegment::not_equal(x : PathSegment, y : PathSegment) -> Bool
    automatically derived

    PathSegment::to_repr

    automatically derived

    Side

    pub(all) enum Side {
    Left
    Right
    } derive(Eq,
    Debug
    )

    Side::equal

    fn Side::equal(Side, Side) -> Bool
    automatically derived

    Side::not_equal

    fn Side::not_equal(x : Side, y : Side) -> Bool
    automatically derived

    Side::to_repr

    automatically derived

    Snapshot

    pub struct Snapshot {
    // private fields
    }

    An owned JSON value whose containers are only visible through detached reads.

    Snapshot::new

    Validate and detach input once. None denotes an absent root.

    Snapshot::read

    Snapshot::subtree

    fn Snapshot::subtree(self : Snapshot, path : Array[PathSegment]) -> Snapshot raise OpError

    Select a subtree without copying its containers. The result is an opaque snapshot.

    Snapshot::to_json

    TextEncoding

    pub(all) enum TextEncoding {
    Legacy
    Text0
    } derive(Eq,
    Debug
    )

    Choose the representation used by text edits created by opgrain.

    TextEncoding::equal

    automatically derived

    TextEncoding::not_equal

    fn TextEncoding::not_equal(x : TextEncoding, y : TextEncoding) -> Bool
    automatically derived

    TextEncoding::to_repr

    automatically derived

    TextPosition

    pub(all) struct TextPosition {
    offset : Int
    affinity : InsertionAffinity
    } derive(Eq,
    Debug
    )

    TextPosition::equal

    automatically derived

    TextPosition::not_equal

    fn TextPosition::not_equal(x : TextPosition, y : TextPosition) -> Bool
    automatically derived

    TextPosition::to_repr

    automatically derived

    TrackedApply

    pub struct TrackedApply {
    // private fields
    }

    TrackedApply::locations

    fn TrackedApply::locations(self : TrackedApply) -> Array[Location?]

    Results follow input order. None means the location no longer has an anchor.

    TrackedApply::losses

    The first invalidating component for each location, using zero-based indices.

    TrackedApply::snapshot

    TransformedHistories

    pub struct TransformedHistories {
    // private fields
    }

    Operations retain their branch order and original batch boundaries.

    TransformedHistories::left_after_right

    fn TransformedHistories::left_after_right(self : TransformedHistories) -> Array[Operation]

    TransformedHistories::right_after_left

    fn TransformedHistories::right_after_left(self : TransformedHistories) -> Array[Operation]

    UndoableEdit

    pub struct UndoableEdit {
    // private fields
    }

    A forward operation, a verified undo operation and its resulting snapshot.

    UndoableEdit::inverse

    fn UndoableEdit::inverse(self : UndoableEdit) -> Operation

    UndoableEdit::operation

    fn UndoableEdit::operation(self : UndoableEdit) -> Operation

    UndoableEdit::snapshot

    fn UndoableEdit::snapshot(self : UndoableEdit) -> Snapshot

    can_op_affect_path

    fn can_op_affect_path(op : Operation, path : Array[PathSegment]) -> Bool

    check_list

    fn check_list(value :
    Json
    ) -> Unit raise OpError

    Check the operand for a JSON0 list instruction.

    check_obj

    fn check_obj(value :
    Json
    ) -> Unit raise OpError

    Check the operand for a JSON0 object instruction.

    check_valid_op

    fn check_valid_op(value :
    Json
    ) -> Unit raise OpError

    common_length_for_ops

    fn common_length_for_ops(a : Component, b : Component) -> Int?

    compose

    fn compose(first : Operation, second : Operation) -> Operation raise OpError

    invert

    fn invert(op : Operation) -> Operation raise OpError

    name

    let name : String

    normalize

    fn normalize(value :
    Json
    ) -> Operation raise OpError

    parse_json

    fn parse_json(source : String) ->
    Json
    raise OpError

    Parse JSON while retaining isolated UTF-16 surrogate code units.

    path_matches

    fn path_matches(left : Array[PathSegment], right : Array[PathSegment], ignore_last? : Bool) -> Bool

    stringify_json

    fn stringify_json(value :
    Json
    ) -> String raise OpError

    Write JSON with a reversible escape for every non-ASCII code unit.

    text0_normalize

    text0_transform_cursor

    fn text0_transform_cursor(position : Int, op :
    Json
    , side? : Side) -> Int raise OpError

    transform

    fn transform(op : Operation, other : Operation, side : Side) -> Operation raise OpError

    transform_x

    fn transform_x(left : Operation, right : Operation) -> (Operation, Operation) raise OpError

    uri

    let uri : String