Structural JSON diff/patch for MoonBit — compute and apply PatchOp sequences between Json trees

diff

patch

json

sync

Download zip

Author

tiye

Version

0.2.1

License

Apache-2.0

Repository

github.com/Cumulo/recollect.mbt

Last updated

5 months ago

Downloads

#recollect

tiye/recollect is a structural JSON diff/patch library for MoonBit.

It computes a compact sequence of PatchOp operations between two Json trees and applies them to reconstruct the target state. The library is designed for immutable-data workflows such as Cumulo and Respo, where you want to ship structural deltas over the network and rebuild the next state locally.

#Why this package exists

recollect is built for state synchronization in immutable applications:

compute diffs from an old state to a new state
serialize patches for transport
apply patches without mutating the previous value
preserve structural sharing on unchanged subtrees

That makes it suitable for render loops and server/client sync models that rely on stable equality checks and replacing the whole root value.

#Immutable data behavior

diff_json / diff_value are read-only
apply_patch / apply_patches / apply_to_value always return a new value
unchanged branches are structurally shared with the original tree
the input value is never mutated in place

let new_remote = @recollect.apply_to_value(old_remote, patches)
  catch { _ => old_remote }

// old_remote is still untouched

Do not keep your app state inside a mutable wrapper and patch it in place. Replace the whole value with the newly returned one, otherwise structural equality-based update logic may stop working correctly.

#API

diff_json(old, new) — compute Array[PatchOp] between two Json trees
diff_value(old, new) — compute patches after serializing typed values with ToJson
apply_patch(root, patch) — apply one PatchOp, return new Json
apply_patches(root, patches) — apply a sequence of patches, return new Json
apply_to_value(value, patches) — patch a typed value via ToJson/FromJson

Patch format:

PathSegment: Field(String) | Index(Int)
PatchOp: Set | Remove | Insert | Delete | Move

Insert / Delete / Move are only emitted for keyed arrays: arrays whose items are JSON objects carrying a unique string "id" field. Plain arrays fall back to positional diffing.

#Import

import {
  "tiye/recollect" @recollect,
}

#Json example

let before : Json = {
  "todos": [{ "id": "t-1", "title": "A", "done": false }],
}

let after : Json = {
  "todos": [
    { "id": "t-1", "title": "A", "done": true },
    { "id": "t-2", "title": "B", "done": false },
  ],
}

let patches = @recollect.diff_json(before, after)
let rebuilt = @recollect.apply_patches(before, patches)
// rebuilt == after

#Typed value example

struct Todo {
  id : String
  title : String
  done : Bool
} derive(FromJson, ToJson)

struct AppState {
  todos : Array[Todo]
} derive(FromJson, ToJson)

let before = AppState::{ todos: [{ id: "t-1", title: "A", done: false }] }
let after = AppState::{ todos: [
  { id: "t-1", title: "A", done: true },
  { id: "t-2", title: "B", done: false },
] }

let patches = @recollect.diff_value(before, after)
let rebuilt : AppState = @recollect.apply_to_value(before, patches)
  catch { _ => before }
// rebuilt == after

#Implementation notes

The core algorithm in recollect works on Json trees.

This is intentional, but it also reflects a current limitation of MoonBit: there is no built-in macro system or runtime reflection that lets the library generate a generic field-level diff/patch implementation directly for arbitrary user-defined structs.

Because of that, the typed API is currently implemented as a JSON round trip:

diff_value(a, b) = a.to_json() + b.to_json() + diff_json(...)
apply_to_value(value, patches) = value.to_json() + apply_patches(...) + from_json()

So the patch format is effectively a JSON-path-based structural delta.

#Trade-off

This design keeps the library generic and simple to integrate with any type that implements ToJson / FromJson, but it also means the typed API pays extra cost in:

serialization
deserialization
intermediate Json allocation
rebuilding typed values from patched Json

In practice, the main overhead is usually not the patch list itself, but the struct ↔ JSON conversion around it.

If you care about throughput on large states, prefer these guidelines:

use diff_json / apply_patches when your data is already represented as Json
use the typed API when convenience and integration matter more than raw speed
expect apply_to_value to be noticeably more expensive than raw JSON patching

Benchmark notes and measurements live in bench/BENCH_REPORT.md.

#Keyed array behavior

When both old and new arrays are arrays of objects with unique string id fields, recollect diffs them by identity instead of position. That allows local Move / Insert / Delete operations instead of rewriting neighboring items.

If array elements do not expose unique string id values, the library falls back to positional diffing.

#Validation

Run checks locally with:

moon check
moon test

#Notes for extraction and publishing

This package is already organized as a standalone MoonBit module:

package docs live next to the implementation
tests cover both JSON-first APIs and typed round trips
benchmark fixtures and reports are kept under bench/

If MoonBit later provides stronger compile-time metaprogramming support, recollect can evolve toward a more direct typed diff/patch path with less JSON conversion overhead. For now, the JSON-path-based approach is the portable implementation that works across user-defined data types.

PatchOp

source

pub(all) enum PatchOp {
  Set(Array[PathSegment], Json)
  Remove(Array[PathSegment])
  Insert(Array[PathSegment], Int, Json)
  Delete(Array[PathSegment], Int)
  Move(Array[PathSegment], Int, Int)
} derive(Eq, ToJson, @moonbitlang/core/debug.Debug
Debug, @moonbitlang/core/json.FromJson
FromJson)

A single structural edit operation on a Json tree.

Patch operations are always non-destructive with respect to the input: every apply_* function returns a new tree rather than mutating the original. This makes the patch format safe to use with immutable-data architectures (e.g. Cumulo server state, Respo stores).

Variant	Meaning
Set	Overwrite a value at path (creates intermediate nodes if absent)
Remove	Delete the field or array element addressed by path
Insert	Splice a new element into the array at path before index
Delete	Remove the element at index from the array at path
Move	Re-order an element within the array at path

Insert/Delete/Move are only emitted for keyed arrays — arrays whose every element is a JSON object with a unique string "id" field. Plain arrays fall back to positional Set patches.

PathSegment

source

pub(all) enum PathSegment {
  Field(String)
  Index(Int)
} derive(Eq, ToJson, @moonbitlang/core/debug.Debug
Debug, @moonbitlang/core/json.FromJson
FromJson)

A single segment in a path through a Json tree.

Paths are sequences of segments used by PatchOp to address nested locations. Field("key") traverses into a JSON object; Index(n) traverses into a JSON array.

apply_patch

source

fn apply_patch(root : Json, patch : PatchOp) -> Json

Apply a single PatchOp to root and return the resulting Json tree.

The input root is never mutated — all intermediate nodes on the affected path are copied, producing a new tree that shares unchanged subtrees with the original. This structural sharing makes the function safe to use in immutable-data architectures.

Panics (via abort) if the path in the patch is structurally inconsistent with the tree (e.g. Field segment on an array node).

apply_patches

source

fn apply_patches(root : Json, patches : Array[PatchOp]) -> Json

Apply a sequence of PatchOps to root, threading the result of each operation as the input to the next.

Like apply_patch, the original root is never mutated.

An empty patches slice returns root unchanged.

let new_json = apply_patches(old_json, diff_json(old_json, new_json))
assert_eq(new_json, new_json)

apply_to_value

source

fn[T : ToJson + @moonbitlang/core/json.FromJson
FromJson] apply_to_value(value : T, patches : Array[PatchOp]) -> T raise @moonbitlang/core/json.JsonDecodeError
JsonDecodeError

Apply patches to a typed MoonBit value by round-tripping through Json.

The value is serialized to Json via ToJson, the patches are applied with apply_patches, and the result is deserialized back to T via FromJson. Raises @json.JsonDecodeError if the patched JSON cannot be decoded into T.

This is the primary function used by Cumulo-style clients to advance their local state when receiving a Delta event from the server:

let new_remote = @recollect.apply_to_value(old_remote, patches)
  catch { err => ... }

Because both serialization and deserialization produce new values, the original value is never mutated.

diff_json

source

fn diff_json(old_json : Json, new_json : Json) -> Array[PatchOp]

Compute a minimal sequence of PatchOps that transforms old_json into new_json.

The diff is structural: objects are compared field-by-field, arrays are compared element-by-element (or by "id" key when all elements carry unique string ids). Unchanged subtrees produce no patches.

The result can be serialized (via ToJson/FromJson on PatchOp) and sent over a network, then applied on the other side with apply_patches.

let patches = diff_json(
  { "count": 1 },
  { "count": 2, "label": "hi" },
)
// patches: [Set(path=[Field("count")], value=2),
//           Set(path=[Field("label")], value="hi")]

diff_value

source

fn[T : ToJson] diff_value(old_value : T, new_value : T) -> Array[PatchOp]

Compute a minimal patch sequence by first serializing both values to Json via ToJson, then delegating to diff_json.

This is the typical entry point when working with typed MoonBit structs. The type T must derive (or implement) ToJson; it does not need FromJson at the diff stage.

struct Counter { value : Int } derive(ToJson)
let patches = diff_value({ value: 1 }, { value: 2 })

Source Files

recollect.mbt

Site source Report issue Packages Build queue Skills Statistics

recollect

#recollect

#Why this package exists

#Immutable data behavior

#API

#Import

#Json example

#Typed value example

#Implementation notes

#Trade-off

#Keyed array behavior

#Validation

#Notes for extraction and publishing

#PatchOp

#PathSegment

#apply_patch

#apply_patches

#apply_to_value

#diff_json

#diff_value

Source Files

PatchOp

PathSegment

apply_patch

apply_patches

apply_to_value

diff_json

diff_value