pg_automergev0.1.0

Rich text spans

A text object maps to a plain string, so formatting (marks) and block markers (paragraphs, headings, list items, embeds: maps inserted into the text with splitBlock) are invisible in the jsonb view: marks leave no trace and each block shows up as U+FFFC. automerge_spans returns that structure:

automerge_spans(doc automerge, path text[]) → jsonb
automerge_spans(doc automerge, path text[], heads text[]) → jsonb  -- as of heads

Both are IMMUTABLE STRICT PARALLEL SAFE. The result mirrors the Automerge JavaScript API's spans(doc, path), so frontends and backends can use it as they use spans():

[{"type": "block", "value": {"type": "heading", "parents": [], "attrs": {"level": 1}}},
 {"type": "text", "value": "Shopping tips"},
 {"type": "block", "value": {"type": "paragraph", "parents": [], "attrs": {}}},
 {"type": "text", "value": "Buy "},
 {"type": "text", "value": "fresh milk", "marks": {"bold": true}},
 {"type": "text", "value": "."}]

Path. As jsonb's #> takes it: from the root, map keys as strings and list indices as integers ('{notes,0,body}'; negative indices count from the end, and an index is parsed as #> parses it: optional leading whitespace and sign, int4 range, nothing after the digits). '{}' is the root. Where #> would return NULL, so does automerge_spans: a missing key, an index out of range or not an integer, a step into a scalar or into a text (jsonb shows it as a string), a NULL path element. A map key with conflicting values uses Automerge's winner, as the jsonb view does. When the value at the path exists but is not a text object (the root, any map, table, list or scalar, including a string scalar, which jsonb also shows as a string), it is 22023 naming the path and what is there: automerge value at path {notes,0} is a map, not a text object.

Heads. The three-argument form reads the state as of heads with the semantics and errors of automerge_to_jsonb(doc, heads) (see History): every hash must be a change of the document (22023), '{}' is the state before any change (whose root is empty, so any non-empty path gives NULL), malformed hashes are 22P02 and NULL elements 22004.

Shape, checked against the JavaScript implementation at the tag js/automerge-3.5.0 (whose rust/automerge is 0.12.0, the version the extension pins): spans() in javascript/src/implementation.ts returns the WASM spans(obj, heads) as is, and export_span in rust/automerge-wasm/src/interop.rs builds each element from Automerge's Span:

  • Span::Text → {"type": "text", "value": <text>} plus "marks": {name: value, ...} when the mark set is non-empty (no "marks" key otherwise, never an empty object).
  • Span::Block → {"type": "block", "value": <the block's map>}. The value is the block map exactly as stored (JS: export_hydrate of the hydrated map). Automerge adds nothing to it: the type, parents, attrs and isEmbed fields are a convention of editors such as automerge-prosemirror (JS splitBlock(doc, path, index, block) stores whatever map it is given), so they appear only if the writer stored them.
  • Runs come from Automerge's own span iterator (ReadDoc::spans / spans_at), which the JS API uses too, so the split is identical: a new run wherever the set of marks changes; adjacent text with the same marks is one run; a block ends the run before it, so text is split at every block (the result is flat: blocks do not contain their text, they precede it).
  • Marks whose value is null are removals (unmark, or a mark set to null), and Automerge's span iterator already drops them from each run's mark set: a run with only removed marks has no "marks", and a null mark value never appears. Expand flags (before/after/both/none) only decide which inserted text a mark covers; they are not part of the output (nor of JS's).
  • Other non-string elements in a text (a list, a nested text, a number inserted with insert) are not blocks: like text(), the span iterator puts U+FFFC for them in the surrounding text run. A literal U+FFFC typed by a user is text too.

Deliberate deviations, all from the jsonb scalar mapping (see the table above), used for mark values and block contents, compared with what alloc_scalar / export_hydrate give in JS:

  • integers (int, uint, counter) are exact JSON numbers. JS gives a number for an int or counter within ±(2^53−1) and a BigInt outside it (which JSON.stringify refuses); a uint is always a BigInt there (automerge-wasm's safe range for uints, 0..MIN_SAFE_INTEGER as u64, is empty);
  • counters are their current value. JS gives a Counter object in block values (registerDatatypes wraps them; its JSON is the value) and a plain number (or BigInt) in mark values, which are not wrapped;
  • NaN/±Infinity are null, timestamps ISO 8601 strings (JS: Date), bytes base64 strings (JS: Uint8Array), U+0000 in strings and keys (mark names too) U+FFFD.

Not deviations: strings in block values are ImmutableString objects in JS (registerDatatypes wraps str too), whose JSON is the plain string, as here; mark values that are strings are plain strings in both. Text inside a block's map is a string, as in JS; conflicting keys in a block show the winner, as in JS.

Positions. The result has none (neither does JS's), so no text encoding is involved in it: a client that needs offsets sums the lengths of the values in its own unit, counting each block as one U+FFFC character (JavaScript's .length, UTF-16 code units, gives exactly the indices of the JS API, whose documents use UTF-16; U+FFFC is one code point and one UTF-16 unit, three UTF-8 bytes).

Protections. The document is loaded as for any read (with_doc: an expanded value in place, a stored one loaded; reading stored values is not subject to pg_automerge.max_load_memory), under the panic guard (a panic is XX000 for a stored value). The span loop and the block walks check for interrupts. The result is built with the same JsonbBuilder as the cast (jsonb's string, element and pair limits, 54000).

Automerge renders a block's value with hydrate, which recurses once per level of nesting inside the block and needs about 13 kB of stack per level in a release build: a block holding maps nested a few hundred levels deep (a document of about 2 kB) overflows the backend's 8 MB stack inside spans(), a crash (a segfault restarts the cluster) that no guard can catch (see Deep blocks for the other paths). So before spans() is called, every block of the text is found without hydrating (one list_range over the text, as of the heads; the map objects among its elements are the blocks) and its depth is measured with an iterative walk: a block nested more than 32 levels deep (the block's map is level 1) is 54000 (automerge text block is nested more than 32 levels deep), which leaves the stack below 0.5 MB. Real blocks are 2 or 3 levels deep. The block values in the result are then converted from the maps spans() hydrated (a recursion as deep as the checked block, far smaller frames than hydrate's) with the jsonb mapping; keys are taken in Automerge's order, not the hydrated map's hash order, so that two keys that become one after U+0000 → U+FFFD keep the same one as automerge_to_jsonb does.

Cost: one load, one list_range over the text, the depth walk (one map_range / list_range per map and list inside each block), and Automerge's own span iteration, which hydrates every block. Measured with mise run bench-core (document rich20k: 200,000 characters in 20,000 paragraphs, each block with type, parents, attrs and isEmbed, every tenth paragraph bold; release build): ReadDoc::spans alone 0.81 s, write_spans on the loaded document 1.29 s, of which the depth walk is about 0.45 s (some 7 µs per range call, three per block) and finding the blocks 0.04 s; spans_to_json of the stored value (load included) 1.79 s. So automerge_spans costs about 1.6 times Automerge's own spans(), linearly in the number of blocks; the depth walk is the price of not crashing on deep blocks. (An earlier version, which found blocks with text() and one get() each and wrote block values with a second walk of the objects, took 2.11 s.)

Tests: crates/pg_automerge_core/tests/spans.rs compares the result with Automerge's own spans() / spans_at() rendered as export_span does (plain and empty text, overlapping marks, marks expanding or not at their boundaries, removed marks, every mark value type, nested and adjacent blocks and embeds, block values of every type, emoji and other multi-unit characters before blocks and marks with documents loaded in each text encoding, literal U+FFFC and non-map objects in a text, conflicting texts under one key, historical heads, and random concurrent rich-text edits merged, at every intermediate heads), plus path resolution, the depth guard (up to 20,000 levels, at heads before the nesting, and at heads where a block since made shallow was deep), blocks present only at some heads, NUL replacement, and block keys that collide after it (the same winner as automerge_to_jsonb, whatever the hash order); src/tests/spans.rs covers the SQL side (paths against #>, 22023 messages, heads errors, NULLs, expanded values, the labels and the depth error); the regress example shows the output.