crdt

package module
v0.57.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 9, 2026 License: BSD-3-Clause Imports: 14 Imported by: 10

README

go-crdt/crdt

crdt — collaborative text editing in pure Go

CI Go Reference coverage license

github.com/go-crdt/crdt is a pure-Go, CGO=0 conflict-free replicated data type for plain text: any number of replicas may edit the same document at once, offline, over an unreliable transport, and every replica ends up with the same text. No server arbitrates, and no operation is ever transformed.

It compiles to js/wasm, so the same merge logic runs on the server and in every browser tab — one implementation, one source of truth, no second codebase in JavaScript to keep in step. The whole test suite, convergence properties included, runs under js/wasm in CI.

Zero dependencies. CI still scans for known vulnerabilities on every run, which for a module that requires nothing means the standard library — the half nobody thinks to scan, and the half a toolchain bump changes underneath you. The lane judges the findings rather than govulncheck's exit status, which is 0 over an advisory it decides a module does not call.

Packages

Package Purpose
crdt the replicated text document (Doc), a replicated sequence of values (List), a replicated map (Map) and a document of named parts (Composite) — operations, version vectors, snapshots
crdt/awareness ephemeral presence — who is here and where their cursor is
crdt/structured a shared substrate for co-editing structured documents over one core — a block document (Blocks), formatted text (RichText), a value replicas may disagree about (MultiRegister), a set of names (Set), changes put up for review (Proposals), a spreadsheet (Sheet), an isometric diagram (Diagram), a movable tree (Tree), a movable sequence (Sequence), a counter (Counter), chunked files (Blobs), handwriting (Ink) and undo (Undo), plus the Register, RecordMap and Cell pieces they compose

Using it

ada, grace := crdt.New(1), crdt.New(2)

opening, _ := ada.Insert(0, "the quick fox")
grace.Apply(opening...)

// Both edit at once, neither having seen the other.
fromAda, _ := ada.Insert(10, "brown ")
fromGrace, _ := grace.Insert(13, " jumps")

ada.Apply(fromGrace...)
grace.Apply(fromAda...)

fmt.Println(ada)   // the quick brown fox jumps
fmt.Println(grace) // the quick brown fox jumps

A replica joining late loads a snapshot instead of the whole history; one coming back from offline hands over its version vector and is sent only what it missed:

client, err := crdt.Load(siteID, snapshot)   // join
missed := server.OpsSince(client.Version())  // catch up

A list, for what sits beside the text

The things built around a document are sequences too — the comments on it, the record of who changed what, the messages beside it — and they need the same guarantees. List is the same algorithm over values the caller encodes:

comments := crdt.NewList(site)
ops, _ := comments.Insert(0, encoded)   // values are opaque []byte
comments.Apply(fromPeers...)
anchor, _ := comments.Anchor(pos)       // a handle that survives other edits

It is a separate type rather than a generic one, deliberately: a document holds hundreds of thousands of characters and earns run-length storage and an index over runs, while a list holds tens or hundreds of values, where a slice is both faster and obviously correct.

A map, for the cells beside it

Not everything beside a document is a sequence. A spreadsheet is a map of cells, a table of settings is a map of settings: written and cleared, never woven in between their neighbours. Map merges those by last writer wins per key, under the same (clock, site) order the text uses, over values the caller encodes:

sheet := crdt.NewMap(site)
op, _ := sheet.Set("B7", []byte("42"))  // send op to every peer
value, ok := sheet.Get("B7")            // a copy; writing to it changes nothing
op, _ = sheet.Delete("B7")
sheet.Keys()                            // sorted, so every replica agrees

A deleted key keeps its clock. Dropping it would let an older write arriving afterwards bring the key back on the replica that heard it late and not on the one that heard it early, permanently — the classic mistake in a last-writer-wins map, and the thing here most worth reading docs/design.md for.

One document, many parts

An editor does not hold one structure. It holds the text, the comments on it, the record of who changed what, the messages beside it and a sheet of cells — and persisting those separately means five snapshots saved at five moments, five things to authorize, and no instant at which the set of them is consistent. Composite is those parts under one name:

doc := crdt.NewComposite(site)

text, _ := doc.Text("file:src/main.tex")   // a *Doc,  created on first use
chat, _ := doc.List("chat")                // a *List
cells, _ := doc.Map("cells")               // a *Map

snapshot := doc.Snapshot()                 // one thing to persist
missed := server.OpsSince(client.Version())

A part is identified by its name and its kind together, and it exists because operations for it exist — so there is no operation to create one, and two replicas that reach for "chat" at the same moment are already holding the same part. It follows that a part which exists and holds nothing is indistinguishable from one that was never created, and that has to be true rather than convenient: an empty part is in no snapshot and no version, or two replicas holding the same operations would disagree about their state.

Each part keeps its own site counter, clock and version vector, so a Doc inside a composite behaves exactly as one standing alone, and the version is per part. On a document of three hundred parts — one small map per comment, which is how a resolved flag flips with one write instead of a delete and a reinsert — the version encodes to 16 KB with the site identities shared in one table rather than repeated in every part, a third less than writing them out.

Keeping a view in step

A view of the text — an editor, a preview — has to be told what changed, not what the text now is. Handed only the new text it would have to replace everything, and replacing everything throws away the selection, the scroll position, the folded regions and the decorations, on every keystroke anybody else makes.

ApplyChanges is Apply and also reports the edits, in the order they have to be made, coalesced: a peer typing a word is one change, not one per letter. Apply does not pay for that.

Anchoring, and who wrote what

An offset names a place; an anchor names a character, and keeps naming it however the document moves around it. That is what a comment, a mark or a stored selection should be:

changes, _ := doc.ApplyChanges(ops...) // what a view has to do to catch up
anchor, _ := doc.Anchor(pos)     // the identity of the character there
pos, ok := doc.Position(anchor)  // where it is now — or where it was, if deleted
doc.Visible(anchor)              // whether it is still in the text
doc.AuthorRuns()                 // the visible text split by who wrote each stretch

Every character already carried the identity of the operation that created it, and the site is part of that identity, so none of this costs the document anything to store.

Counting the way a browser counts

The document counts characters. CodeMirror, the DOM, the Language Server Protocol and every index into a JavaScript string count UTF-16 code units, in which an emoji, an extended CJK ideograph or a 𝔸 is two units and one character. An editor handing its cursor offset to Insert therefore edits in the wrong place as soon as the document holds one of them — silently, and with nothing left behind that a later read could notice.

So the same operations are addressed both ways, and a caller who counts in UTF-16 never converts by hand:

doc.LenUTF16()                 // what JavaScript's String.length would report
doc.InsertUTF16(pos, "text")   // pos in code units
doc.DeleteUTF16(pos, n)        // pos and n in code units
doc.UTF16Offset(runePos)       // and the conversion, both ways
doc.RuneOffset(utf16Pos)

An offset landing between the two units of one character is refused rather than rounded; docs/design.md says why, and how to round it in one step if that is what you want. A document holding no such character converts in constant time, so nothing pays for this until it has an emoji in it. The answers are checked against node's, not against ours.

What it guarantees

  • Convergence. Replicas holding the same operations hold the same document, whatever order those operations arrived in. Proven by randomised sessions with late, reordered and duplicated delivery, and by enumerating every permutation of small histories.
  • Idempotence and reordering. Duplicates are ignored; an operation arriving before what it depends on is buffered until that lands. A transport needs to be eventually complete, not ordered.
  • Determinism. No wall clock, no randomness. Replica identity is injected by the caller, so a document behaves identically on a server and in a browser.
  • Intent. A run of characters typed one after another is never chopped up by someone else's concurrent insertion.
  • Nothing is trusted. Every decoder is fuzzed; a snapshot that no replica could have produced is rejected rather than loaded; and operations arranged to make integration walk the whole document cost a descent of an index instead.

Status

What is here: the text, list and map CRDTs, a composite document that holds them as named parts, the wire and snapshot formats, awareness, and the surface an editor needs — reported changes, anchors, authorship, UTF-16 addressing, undo, and reading a document as it stood at any version. The released version is whatever the newest tag says; this sentence used to name one and was twenty-eight releases behind it. Pure Go, CGO=0, 100% statement coverage on all three packages, race-clean, six-arch CI, and the full suite green under js/wasm. Full coverage says every line runs, not that anything would notice if a line were wrong — what 100% of statements does not say measures the difference over the 104 refusals in the three files that read somebody else's bytes.

A real editing history — 259 778 edits from the trace text CRDTs are commonly measured on — replays in 20.0 ms and matches the recorded text exactly; the same history delivered back to front, nothing applicable until the last operation, settles in 0.25 s, and the document encodes to 260 KB. See docs/performance.md.

See docs/design.md for how it works and why, and docs/performance.md for what it costs and what changes next.

License

BSD-3-Clause — see LICENSE. Copyright the go-crdt authors.

Documentation

Overview

Package crdt implements a conflict-free replicated data type for plain text: a replicated character sequence that any number of replicas may edit concurrently, offline, and in any delivery order, and that is guaranteed to converge to the same text on every replica.

The sequence is an RGA (Replicated Growable Array). Every character carries a unique ID and the ID of the character it was inserted after, so insertions are placed relative to content rather than to an index that concurrent edits would invalidate. Deletions are tombstones, so an insertion may still refer to a character another replica has already removed.

Where a concurrent word lands, which convergence does not decide

Converging on the same text is not the same as converging on the text a person would have written, and RGA is known to leave one case open. When two people type at the same place, and one of them typed twice there without the two runs being contiguous — typed a word, moved the cursor BACK, typed another — the other person's word may end up BETWEEN those two runs.

"Hello!", User 1 typing " reader" and then " dear" at the same anchor, User 2 concurrently typing " Alice" there, merges to one of: 

Hello dear reader Alice!
Hello dear Alice reader!    <- the other person's word, split into yours
Hello Alice dear reader!

Every replica agrees on which, and which one it is comes from the tie-break between equal Lamport clocks rather than from anything either person did. It is not a defect of this implementation: Kleppmann, Gomes, Mulligan & Beresford proved RGA free of the SEVERE anomaly — two concurrent words jumbled character by character, which Logoot and LSEQ do exhibit — and showed this lesser one remains ("Interleaving anomalies in collaborative text editors", PaPoC '19, §3).

More precisely, and this is the distinction that names what is above: RGA is proved free of FORWARD interleaving, where each person types left to right. It exhibits BACKWARD interleaving, which is what moving the cursor back and typing again produces, and which is not exotic — hitting backspace to fix a typo does it, and so does prepending rows to a list or a spreadsheet.

That 2019 paper proposes a fix, and the fix does not work. Weidner & Kleppmann report it as two flaws ("The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing", §3.2): the non-interleaving property it defines "cannot be satisfied by any algorithm", and the algorithm it proposes "is incorrect — it does not converge". So there is nothing here to weigh up and decline.

What does work is a different algorithm, not a patch to this one. Fugue and FugueMax are proved to interleave "only in the rare situations where some interleaving is inevitable", FugueMax satisfying their maximal non-interleaving property, with performance their paper compares to Yjs on a real editing trace. Adopting one would replace how this package orders concurrent insertions at a shared anchor, which is its centre rather than a setting.

TestWhereAConcurrentWordLandsAmongTwoOfYourOwn holds what is actually promised: every merge order agrees, and the result is one of those three. A fourth would be the severe anomaly and a real defect.

Determinism

The package never reads the wall clock and never draws random numbers, so the same Doc compiled to js/wasm behaves exactly as it does on a server. Replica identity is injected by the caller as a SiteID; see DeriveSiteID for a deterministic way to obtain one from bytes the caller already has.

TestTheSourceNeverReadsTheClockOrDrawsRandomNumbers holds this one, and it reads the source rather than exercising the code, because what the sentence forbids is an absence. A time.Now() added to a new file tomorrow would break it with every test still passing — the convergence suite least of all, since two replicas that both read the clock can still agree with each other and disagree only with a replay of themselves.

Two counters

Each operation carries two numbers, and they are not the same thing:

  • ID.Seq is a per-site counter that increases by exactly one per operation the site issues. It gives the operation its identity and lets a VersionVector describe, exactly, which operations a replica holds.
  • Op.Clock is a Lamport timestamp, bumped past every clock a replica has seen. It orders concurrent insertions at the same position, and it is what makes RGA integration convergent.

Folding the two into one counter would create gaps in a site's own sequence, and a version vector cannot describe a sequence with gaps.

Delivery

Doc.Apply tolerates duplicates, and it tolerates operations that arrive before the operations they depend on: an operation that is not yet ready is buffered and integrated as soon as its dependencies land. Callers therefore do not need an ordered transport, only an eventually-complete one.

A replicated map

Map is the same machinery applied to a key-value map, for what an editor keeps beside its text — a spreadsheet of cells, a table of settings. The last write to a key wins, under the same (clock, site) order, and a deleted key keeps its clock so that an older write arriving later cannot resurrect it. It shares ID, VersionVector, ErrMalformed and the wire conventions with Doc and nothing else, so neither structure can disturb the other.

One document of many parts

Composite holds named parts, each a Doc, a List or a Map, so that a text, the comments on it and a sheet of cells are one snapshot, one version and one thing to authorize rather than five. It adds no merge rule: each part keeps its own counters and converges exactly as it does standing alone. A part is identified by its name and its kind together, and exists because operations for it exist, so two replicas that reach for the same part are already holding it and nothing is exchanged to create one.

Example

Two people edit the same document at the same time, neither having seen the other's change. Once the two operations have crossed, both replicas hold the same text — with no server deciding anything. 

package main

import (
	"fmt"

	"github.com/go-crdt/crdt"
)

func main() {
	ada, grace := crdt.New(1), crdt.New(2)

	opening, err := ada.Insert(0, "the quick fox")
	if err != nil {
		panic(err)
	}
	if err := grace.Apply(opening...); err != nil {
		panic(err)
	}

	// Both edit at once, neither seeing the other.
	fromAda, err := ada.Insert(10, "brown ")
	if err != nil {
		panic(err)
	}
	fromGrace, err := grace.Insert(13, " jumps")
	if err != nil {
		panic(err)
	}

	if err := ada.Apply(fromGrace...); err != nil {
		panic(err)
	}
	if err := grace.Apply(fromAda...); err != nil {
		panic(err)
	}

	fmt.Println(ada)
	fmt.Println(grace)
}

Output:
the quick brown fox jumps
the quick brown fox jumps

Index

Examples

Constants

View Source 
const MaxClock = 1 << 62

MaxClock is the highest Lamport timestamp an operation may carry, and so also the highest sequence number, since a clock is never below the sequence number beside it.

A clock counts operations: to reach this one, a session would have to issue four quintillion of them, one per nanosecond for a century and a half. The ceiling exists for what arrives from elsewhere, not for what is issued here. A replica raises its clock past every clock it is told about, so without a ceiling one operation from one peer — a corrupted varint is enough, no malice required — leaves the receiver's clock at the top of the range, and its next edit wraps to zero. That edit is then an operation every replica rejects as invalid, its own author included, and one that loses every tie it takes part in: the peer is silently and permanently unable to write. Refusing the clock on arrival is what keeps that from being reachable at all.

Variables

View Source 
var ErrCollidingID = errors.New("crdt: two operations share one ID")

ErrCollidingID reports two different operations wearing one name: one this replica has already applied, and an arriving one with the same ID whose character is not the one it holds.

An ID is (site, sequence number), and a site number is claimed rather than proved — DeriveSiteID is a pure function of a name, so two replicas can choose the same site by accident as easily as on purpose. When they do, each mints operations the other will file under names it already has, and VersionVector.Includes cannot tell them apart: that is what a version vector IS, a statement about how far a site has counted and not about what it said.

Without this the consequence is silent and permanent. A replica discards what it has never seen as already-seen, or grafts the part of the other's history that runs past its own onto its own -- and both replicas then report the SAME version vector while holding different text, so each believes it is completely caught up with the other and neither will ever ask for anything again. Measured in collab's TestAFederatedPeerCanSpeakAsAnotherServersUser.

What it is and is not

It is a guard on a premise, not a policy. The skip it sits in front of assumes that applying an operation twice cannot change anything; this checks that assumption instead of trusting it, so a genuine duplicate -- which a transport may deliver freely, and which compares equal -- is still ignored in silence.

Where it is checked, and what that does and does not promise

At the skip, as each operation is offered. So a batch stops at the first collision it reaches: often before anything of it has landed, and not as a guarantee -- a batch whose collision comes late has applied what came before it. This names a collision; it is not a boundary.

The position cost two earlier attempts, both caught by FuzzApply within a second of being written.

It can arrive on a replay rather than on the first pass

An operation whose causal predecessor has not arrived is PARKED before it reaches the skip, so it is held without being compared. Its twin -- an operation of the same ID saying something else -- may land afterwards, and the parked one is then a collision nobody has looked at. Offered again, which a transport may do freely, it reaches the skip and is refused. So a message can be accepted once and refused on a replay.

Two ways to close that were tried and neither is worth its price. Walking every parked operation at the end of each Apply made the test suite take seventy seconds instead of twelve, because a history delivered back to front parks a chain as long as itself and each Apply then walks all of it. Walking only what the same call parked is cheap and does not close it: the composite applies one batch per part per call, so a twin arriving in the next batch of the same message still slips past -- FuzzParsePartOps found that in forty-four seconds.

The cost of leaving it is bounded and the benefit is not worth more: by the time a collision exists the document is already wrong, and an error that arrives on the next delivery still arrives. Indexing parked operations by their own ID would close it, and that is a structure to keep and maintain for a case that only a broken or hostile sender reaches.

A batch may contain its own collision: two operations with one ID and different characters, which no honest replica can produce because a site's sequence number rises once per operation.

  • Checked BEFORE anything lands -- which keeps Doc.Apply's promise that a refusal changes nothing -- neither of the two is applied yet, so nothing collides: the batch is ACCEPTED and one of them silently dropped. Replay the same bytes, which a transport may do freely, and the dropped one now collides with the applied one, so they are REFUSED.
  • Checked AT THE SKIP alone, an operation can still slip past: one whose predecessor is missing is parked BEFORE the skip is reached, its twin lands, and the batch is accepted -- then refused on the replay, when the parked one is offered again and the twin is there. Hence the walk over what this call parked.

Both made the answer depend on the interleaving, and an answer that changes between two identical calls is worse than either answer given twice. The first made it depend on something worse still: how a transport chose to BATCH the operations, so two replicas told the same things in a different number of messages would disagree about whether they were acceptable.

A third position, a walk over the whole batch after applying it, is consistent and costs too much: every operation the batch just landed is then "already seen" and pays an index lookup for nothing, which measured +18% on BenchmarkApplyRemote against +0 for the check that only looks where the information already is.

So the guarantee here is that a collision is NAMED, not that it is kept out. Keeping it out means refusing the operations before they reach Apply, which is a decision about who may speak for a site and belongs at the boundary: github.com/go-crdt/collab.Config.AuthorizeOperations, and go-crdt/collab#175.

The inputs are kept: testdata/fuzz/FuzzApply/d82de10c3d0a704d and testdata/fuzz/FuzzParsePartOps/d0076032193cd682.

It is a diagnostic rather than a defence, and the difference matters. It fires when the collision has a consequence, which is exactly when the arriving content differs, so an accidental collision names itself at the first character that disagrees. It does not stop somebody who means it: an attacker who can read the document can reproduce the operations it already holds exactly and diverge only after them, which this cannot see and nothing here can. Refusing that needs authority over a site name -- a signature, or a declared set of sites a link may speak for -- which is go-crdt/collab#175.

Only the text can answer, and that is a property of the structures

A document keeps every character it was ever told about until a purge or a collect drops it, so a text part can be asked what it holds under a name. A map keeps one record per key rather than one per operation, so an operation that has since been superseded leaves nothing to compare; a list is the same. The strength of a content check therefore differs by part type, which is one reason it cannot be the answer on its own: an authority check does not vary like that.

View Source 
var ErrEmptyValue = errors.New("crdt: a list value must not be empty")

ErrEmptyValue reports an attempt to insert a value of no bytes. A list of nothings is almost always a caller encoding badly, and allowing it would make "absent" and "empty" the same on the wire.

View Source 
var ErrExhausted = errors.New("crdt: the site has no clock left")

ErrExhausted reports a replica that can issue no further operations because its Lamport clock has reached MaxClock. Reaching it honestly is not something a running program does; see MaxClock.

View Source 
var ErrInvalidOp = errors.New("crdt: invalid operation")

ErrInvalidOp reports an operation that cannot be applied because it is not well formed — an unknown kind, a missing identity, an unusable character, or a field set that does not belong to its kind.

View Source 
var ErrInvalidPart = errors.New("crdt: invalid part")

ErrInvalidPart reports a part that cannot name anything: an unknown kind, a name that is not valid UTF-8, or no name at all.

View Source 
var ErrInvalidText = errors.New("crdt: invalid UTF-8")

ErrInvalidText reports text that is not valid UTF-8. The package refuses it rather than substituting replacement characters, which would silently corrupt a document that no later edit could repair.

View Source 
var ErrMalformed = errors.New("crdt: malformed encoding")

ErrMalformed reports bytes that are not a valid encoding.

View Source 
var ErrOutOfRange = errors.New("crdt: position out of range")

ErrOutOfRange reports a position or length outside the document.

View Source 
var ErrPurged = errors.New("crdt: a purge discarded characters this version still needs")

ErrPurged reports a version this replica can no longer answer for, because a purge discarded characters that answering it would need.

Beside ErrStranded, and for the reason written there: an operation that can never be applied is returned rather than left waiting, because parking it is the silent version of the same failure. This is the same doctrine one step earlier — refusing to send what would park at the far end — and it is the shape the field settled on independently. Loro names two of these: 

ImportUpdatesThatDependsOnOutdatedVersion
SwitchToVersionBeforeShallowRoot

A caller that gets this sends a Doc.Snapshot instead of operations. That is not a fallback but the whole design: a snapshot carries a purged document exactly, which is what Doc.Purge keeping every identity buys.

View Source 
var ErrStranded = errors.New("crdt: operation names a collected character")

ErrStranded reports an operation that can never be applied, because what it names was dropped by a collection.

Parking it instead would be the silent version of the same failure: the operation would wait for something that is never coming, and the work it carries would be lost with nothing said. Only Map.Collect can produce it; see the note there.

View Source 
var ErrSurrogateBoundary = errors.New("crdt: UTF-16 offset splits a surrogate pair")

ErrSurrogateBoundary reports a UTF-16 offset that falls between the two code units of one character.

Such an offset names a position that does not exist: half of an emoji is not a place a cursor can be, and no editor's user ever put it there. It is refused rather than rounded because rounding would move an edit somewhere the caller did not ask for and leave nothing behind to say so — the same reasoning that has Doc.Insert refuse invalid UTF-8 rather than substitute replacement characters.

It is not a hypothetical. JavaScript will happily do the operation, and `"a😀b".slice(0, 2) + "x"` is a string containing a lone high surrogate: not text, not valid UTF-8, and not anything this package can hold. An offset that splits a character has already lost the information needed to honour it.

A caller who must tolerate such an offset can round it down in one step, without a second API: an offset that splits a character is always exactly one past that character's first unit, so Doc.RuneOffset of pos-1 is the position of the character it landed inside.

View Source 
var ErrTooManyOps = errors.New("crdt: more operations than allowed")

ErrTooManyOps reports a message claiming more operations than the caller allowed.

It is not corruption. The counted headers are already checked against the bytes that follow them -- a claim of more records than the remaining bytes could hold is ErrMalformed -- so what this refuses is a message that is honest and too big: the worst claim those checks permit still reserves sixteen to twenty-four times the input, because that is the ratio of a record in memory to the smallest encoded one. A gibibyte of real operations is therefore sixteen to twenty-four gibibytes reserved, for an honest sender as much as a hostile one.

Which is why the bound is the CALLER's and not this package's. A ceiling picked here would be a guess about somebody's machine, and this package has been wrong that way before: an allocation ceiling chosen for one architecture failed on riscv64 over runtime noise that had nothing to do with the code. So ParseOps and its three siblings bound nothing, and ParseOpsLimit and its three take the number from whoever knows the machine.

The layering is HPACK's, which is worth naming because this follows it deliberately: a decoder there offers SetMaxStringLength and defaults to unlimited, and the server sets it. See go-crdt/collab#169.

View Source 
var ErrUnknownFormat = fmt.Errorf("%w: format version this build does not know", ErrMalformed)

ErrUnknownFormat reports a snapshot this build cannot read because it does not know the format version, rather than because the bytes are damaged.

The two are worth telling apart by the person holding them. A snapshot travels -- in go-crdt/collab a joining client loads one the server sends it -- so the ordinary way to meet this is a peer running a newer build, and the answer is to upgrade rather than to go looking for corruption. Reported as a malformed encoding, which is what this used to be, it reads as damaged data and sends somebody after the wrong thing.

The magic matched, so these bytes are a snapshot of the right kind. Only the version is one this build has no reader for -- either later than any it knows, or a number reserved for work that has not landed. It wraps ErrMalformed, because these bytes are malformed as far as this build is concerned and a caller that only asks that question must go on getting the same answer. What is new is being able to ask the narrower one.

Functions

func AppendListOps added in v0.12.0 

func AppendListOps(dst []byte, ops []ListOp) ([]byte, error)

AppendListOps encodes a batch of operations onto dst — the form a transport sends. The batch is length-prefixed, so ParseListOps can reject a truncated message instead of silently returning the operations that happened to survive.

func AppendMapOps added in v0.10.0 

func AppendMapOps(dst []byte, ops []MapOp) ([]byte, error)

AppendMapOps encodes a batch of operations onto dst — the form a transport sends. The batch is length-prefixed, so ParseMapOps can reject a truncated message instead of silently returning the operations that happened to survive.

func AppendOps 

func AppendOps(dst []byte, ops []Op) ([]byte, error)

AppendOps encodes a batch of operations onto dst — the form a transport sends. The batch is length-prefixed, so ParseOps can reject a truncated message instead of silently returning the operations that happened to survive.

func AppendPartOps added in v0.12.0 

func AppendPartOps(dst []byte, batches []PartOps) ([]byte, error)

AppendPartOps encodes batches of operations onto dst — the form a transport sends, and what Composite.OpsSince returns handed over whole. The batches are length-prefixed, and so are the operations inside each of them, so ParsePartOps can reject a truncated message instead of silently returning the batches that happened to survive.

Every batch is validated before a byte is written, so what this produces is what Composite.Apply accepts, and what it refuses it refuses with the error Apply would have given: a batch that cannot be sent is a batch that could not have been applied either.

Unlike a snapshot, this is a message rather than a state, and the canonical claim it makes is the one a message can make: re-encoding what was decoded gives back the same bytes. It does not claim that one set of operations has one encoding — batches may repeat a part or arrive in any order, because Composite.Apply accepts them that way and applying an operation twice changes nothing.

func Reads added in v0.40.0 

func Reads(f Format) []byte

Reads reports the versions of a format this build can load, ascending.

A set rather than a range, because the versions are not contiguous and assuming they were is a mistake this package has already made: version 7 of a text is reserved for the purge and refused here, so this build reads 8 and 9 and nothing between. A peer told "up to 9" would send a 7 and be refused.

Empty for a format this build does not know, which is how a peer built later can name one and be understood to have said something rather than nothing.

What it is for

A snapshot travels: a joining participant loads one the server sends, and a federated link adopts one from the server it follows. Neither can negotiate -- a reader knows the version byte or refuses the bytes -- so the only way to avoid sending something unreadable is to have been told what the other side reads. This is the half of that a peer can say about itself.

The result is freshly allocated; a caller may keep it.

func Writes added in v0.40.0 

func Writes(f Format) byte

Writes reports the version of a format this build produces.

It is not always the highest version read: a format ships its reader first and its writer a release later, so that a peer meets nothing it cannot understand.

Nor is it always what a given document writes. A text is version 9 here and version 8 in the bytes of every document that has not purged, because the purge's fields are written only by a document that has any -- see [Doc.formatVersion]. The higher number is the honest answer to a sender's question all the same: what a peer has to be able to read is the most this build might send it, and a peer told 8 would be sent a 9 the first time somebody called Doc.Purge.

Zero for a format this build does not know.

Types

type AuthorRun added in v0.7.0 

type AuthorRun struct {
	// Pos is the visible offset the stretch starts at.
	Pos int
	// Len is how many characters it covers.
	Len int
	// Site is the replica that wrote them.
	Site SiteID
}

An AuthorRun is a stretch of the visible text one replica wrote.

type Change added in v0.7.0 

type Change struct {
	Pos     int
	Removed int
	Text    string
}

A Change is one contiguous edit to the visible text: remove Removed characters at Pos, then put Text there. Either part may be empty.

Offsets are in runes, and each change is expressed against the text as it stands after the changes before it. Applying them in order to a copy of the text is what brings the copy up to date.

func ChangesFrom added in v0.7.0 

func ChangesFrom(text, want string) []Change

ChangesFrom returns the edits that turn text into the document's current text, for a caller holding a copy it cannot otherwise reconcile — a view that has just been reconnected, say. It is a convenience over Doc.String, not a cheaper path: it compares the two.

type Composite added in v0.11.0 

type Composite struct {
	// contains filtered or unexported fields
}

A Composite is a document made of named parts, each a Doc, a List or a Map. It is one replica of the whole: one snapshot to persist, one version to hand a peer, one thing to authorize.

Parts are created by being used

Composite.Text, Composite.List and Composite.Map return the part with that name, creating it on first use. There is no operation for creating one and none is needed: two replicas that each reach for the same name are already holding the same part, because a part is identified by nothing but its name and its kind. Nothing has to be exchanged, so nothing can be lost, arrive late, or conflict.

The consequence is that a part which exists and holds nothing is indistinguishable from one that was never created — and that had better be true rather than merely convenient, because it is: a replica that has reached for "chat" and typed nothing must produce the same snapshot bytes as one that has never heard the word, or two replicas holding exactly the same operations would disagree about their state. So an empty part is written to no snapshot, carried in no version, and not returned by Composite.Parts. It costs its creator a map entry and every other replica nothing at all.

Each part keeps its own counters

A part is an ordinary Doc, List or Map, with its own site counter, Lamport clock and version vector, and it is edited through its own methods. The alternative — one counter for the whole composite — was considered and rejected twice over. It would make Doc.Version describe operations a standalone Doc knows nothing about, damaging three clean types for a container's convenience; and it would not buy cross-part causality anyway, since contiguous sequence numbers only order operations issued by the same site, so a comment Bob writes on text Ada typed is unprotected either way.

What follows from that is worth stating: operations are addressed to a part by the caller, in a PartOps, and nothing here can check that the address is the one the operations came from. Editing the text and sending its operations labelled as a list is a caller bug this type cannot catch.

A Composite is not safe for concurrent use. The zero Composite is unusable — construct one with NewComposite or LoadComposite.

Example

A composite holds a text, the lists beside it and a map of cells as one document. Nothing is exchanged to create a part: both replicas reach for "chat" and are already holding the same one. 

package main

import (
	"bytes"
	"fmt"

	"github.com/go-crdt/crdt"
)

func main() {
	ada, grace := crdt.NewComposite(1), crdt.NewComposite(2)

	text, err := ada.Text("file:main.tex")
	if err != nil {
		panic(err)
	}
	typed, err := text.Insert(0, "\\section{Results}")
	if err != nil {
		panic(err)
	}

	chat, err := grace.List("chat")
	if err != nil {
		panic(err)
	}
	said, err := chat.Insert(0, []byte("looks good"))
	if err != nil {
		panic(err)
	}

	// Operations are addressed to a part by the caller; only the caller knows.
	err = grace.Apply(crdt.PartOps{
		Part: crdt.Part{Kind: crdt.PartText, Name: "file:main.tex"},
		Text: typed,
	})
	if err != nil {
		panic(err)
	}
	err = ada.Apply(crdt.PartOps{
		Part: crdt.Part{Kind: crdt.PartList, Name: "chat"},
		List: said,
	})
	if err != nil {
		panic(err)
	}

	fmt.Println(ada.Parts())
	fmt.Println(bytes.Equal(ada.Snapshot(), grace.Snapshot()))

	// A part reached for and left empty is in no snapshot: it is
	// indistinguishable from one nobody ever named.
	if _, err := ada.Map("cells"); err != nil {
		panic(err)
	}
	fmt.Println(bytes.Equal(ada.Snapshot(), grace.Snapshot()))

}

Output:
[{text file:main.tex} {list chat}]
true
true

func LoadComposite added in v0.11.0 

func LoadComposite(site SiteID, snapshot []byte) (*Composite, error)

LoadComposite rebuilds a document from a snapshot, to be edited as site. The site need not be one that appears in the snapshot — a client joining brings its own.

Each part's bytes are handed to that part's own loader, which is where the clock ceiling, the version vector's promise and the rest of what Load, LoadList and LoadMap refuse are enforced; nothing is re-checked here and nothing is waived. What this loader adds is what only it can see: that the parts are the ones a replica could have written, in the order it would have written them, and that none of them is empty — an empty part is one no snapshot carries, so a snapshot carrying one is not a snapshot this package produced, and accepting it would mean re-encoding gave back different bytes.

What it deliberately does not insist on is that a part's bytes are themselves the current encoding. A text part written by an older build is still read by Load, and is written back in the current form — so a snapshot this package accepts is normalised on load, while one it produced reloads to itself byte for byte. Refusing the older form would buy an exact fixed point on arbitrary input at the price of the migration the older form exists for.

func NewComposite added in v0.11.0 

func NewComposite(site SiteID) *Composite

NewComposite returns a document with no parts, whose parts issue operations as site. Every replica editing a composite concurrently must pass a distinct site; see SiteID.

func (*Composite) Apply added in v0.11.0 

func (c *Composite) Apply(batches ...PartOps) error

Apply integrates batches of operations from peers, creating any part they name and do not find. Duplicates are ignored and an operation arriving before what it depends on waits, exactly as it does in the part standing alone.

A malformed batch is rejected and nothing in the call is applied, parts included: a call that fails creates no part. That is why every batch is checked before any is applied.

func (*Composite) ApplyAbsorbed added in v0.32.0 

func (c *Composite) ApplyAbsorbed(batches ...PartOps) ([]PartOps, error)

ApplyAbsorbed is Composite.Apply, and also reports what it integrated, per part, including operations that had been parked waiting for them.

A part that integrated nothing is not in the result, so an empty result means this replica learned nothing — which is exactly when a relay has nothing to pass on and a loop between two replicas has to stop.

func (*Composite) ApplyChanges added in v0.13.0 

func (c *Composite) ApplyChanges(batches ...PartOps) ([]PartChange, error)

ApplyChanges is Composite.Apply, and also reports what each part did, in the canonical part order so that two replicas given the same batches report the same thing.

Only what actually happened is reported: an operation already applied, or one still waiting for the operation its site issued before it, changes nothing and says nothing; when a waiting one lands, the change is reported then. A batch naming a part that ends up doing nothing produces no PartChange.

Finding where each text edit landed costs a walk up the index per operation, which Composite.Apply does not pay. Use that one when nothing is watching.

func (*Composite) CanServe added in v0.41.0 

func (c *Composite) CanServe(v CompositeVersion) error

CanServe reports whether this document can answer a peer at v, or ErrPurged if a text part has discarded characters that peer would need.

It is Doc.CanServe over every text part, and it exists because Composite.Text hands out the *Doc: anything holding a composite can purge one of its texts, and Composite.OpsSince would then serve a peer it cannot serve with nothing to ask. A safety on the part and none on the whole is a safety somebody reaches around without meaning to.

A part the peer names nothing for is a part it holds nothing of, which is the emptiest version there is and the one a purge is likeliest to have outrun -- so it is asked about with an empty vector rather than skipped.

func (*Composite) Clocks added in v0.36.0 

func (c *Composite) Clocks() CompositeClocks

Clocks reports how far each map part of this document has counted.

It is what a participant tells a server so the server can build a floor to collect against: this replica writes above these, on every part, whatever it does next. A text and a list are left out, having nothing to give back.

func (*Composite) Collect added in v0.33.0 

func (c *Composite) Collect(stable CompositeVersion, below CompositeClocks) int

Collect drops what every map part of this document can spare, given what every replica has delivered, and reports how many tombstones went.

Only the maps. A text and a list had one too and it was withdrawn — see the note in text.go — so a document made of them gives nothing back for now. A map is unaffected because it re-points nothing, which is exactly what the other two got wrong.

A part not named in stable is left alone. That is not a nicety: collecting a part against a version nobody vouched for is exactly the mistake the other [Doc.Collect] guards against, and the guard cannot see a part the caller forgot.

There is deliberately no rewrite for a Composite — see Doc.Rewritten — because rewriting mints new identities and the structured layer keeps rich text marks, tree parents and sequence positions against the identities of the characters they describe. Collecting a map keeps every identity it does not drop, and drops only records that are already invisible and already agreed to be gone.

func (*Composite) Digest added in v0.51.0 

func (c *Composite) Digest() Digest

Digest fingerprints every part of the composite, in the order [Parts] gives, which is by kind and then by name and is the same on every replica that has applied the same operations.

A part a caller reached for and left empty is not in it, for the same reason it is not in Composite.Parts: one replica having touched a name is not a difference in the document.

func (*Composite) DropPending added in v0.31.0 

func (c *Composite) DropPending() int

DropPending forgets what every part is holding back, and returns how many operations that was. See Doc.DropPending for why it is safe.

func (*Composite) List added in v0.11.0 

func (c *Composite) List(name string) (*List, error)

List returns the list part called name, creating an empty one on first use.

func (*Composite) Map added in v0.11.0 

func (c *Composite) Map(name string) (*Map, error)

Map returns the map part called name, creating an empty one on first use.

func (*Composite) OpsSince added in v0.11.0 

func (c *Composite) OpsSince(v CompositeVersion) []PartOps

OpsSince returns the operations this replica holds that v does not, batched by part and ready to send to the peer that produced v. Pass a nil version for everything.

The version is compared before anything else is done, so a part the peer is up to date on costs a walk of its version vector rather than of its history. That is what a document of hundreds of parts needs: a peer that has missed one comment must not pay for the other two hundred and ninety-nine.

No batch it returns is empty, which is the same statement: a part with nothing to send is a part whose version the peer already covers. A part that has been reached for and left empty needs no case of its own — the empty vector is covered by everything, this one included.

func (*Composite) Parts added in v0.11.0 

func (c *Composite) Parts() []Part

Parts returns every part holding at least one operation, ordered by kind and then by name. Two replicas that have applied the same operations return the same slice, which is what makes anything a caller derives from it — a list of files, a count of comments — the same everywhere. Parts a caller has reached for and left empty are not among them; see Composite.

func (*Composite) Pending added in v0.11.0 

func (c *Composite) Pending() int

Pending reports how many operations, across every part, are still waiting for operations they depend on.

func (*Composite) Site added in v0.11.0 

func (c *Composite) Site() SiteID

Site returns the replica identity this document's parts issue operations as.

func (*Composite) Snapshot added in v0.11.0 

func (c *Composite) Snapshot() []byte

Snapshot encodes the whole document: every part that holds anything, in the canonical order, each as its own snapshot with its name and kind in front. It is what a server sends a client joining an existing session, and what it persists — one file rather than one per part, saved at one moment rather than at five.

A part's bytes are its own snapshot, verbatim, including that snapshot's magic and format version. Stripping the six bytes back off was the obvious economy and was not taken: it would tie this format to the internal layout of the other three, so a part's format could not be revised without revising this one, and a document a previous build wrote could not be opened by wrapping its bytes. Six bytes per part is a twentieth of what a part's name costs.

The encoding is canonical. Two replicas that have applied the same operations produce identical bytes, whatever order those operations arrived in, because each part's own encoding is canonical and the order the parts are written in is fixed. That is what lets the test suite compare snapshots rather than values, which is the stronger claim: two replicas can agree on every value and still disagree about which write produced it.

func (*Composite) Text added in v0.11.0 

func (c *Composite) Text(name string) (*Doc, error)

Text returns the text part called name, creating an empty one on first use. The name is rejected rather than corrected; see Part.

func (*Composite) Version added in v0.11.0 

func (c *Composite) Version() CompositeVersion

Version returns what this replica holds, to be handed to a peer that will send back what it is missing; see Composite.OpsSince.

Every vector in it is a copy. Handing out the live ones would put the thing a caller measures against under the control of the thing being measured: a server that took a client's version, then applied an operation, and then asked what the client was missing would find the question had answered itself.

A map has no order, so this is one of the two places that walk the parts without asking Composite.Parts for them in order — which on a document of three hundred parts is most of the cost of the answer.

type CompositeClocks added in v0.36.0 

type CompositeClocks map[Part]uint64

CompositeClocks is a clock floor for each part of a document: a promise that no operation with a clock at or under it can still arrive at that part. It is the second half of what Composite.Collect needs, and a part it does not name is a part nothing is given back from.

One entry per part and not one number, because each map carries a Lamport clock of its own and they do not run together.

func (CompositeClocks) MarshalBinary added in v0.36.0 

func (c CompositeClocks) MarshalBinary() ([]byte, error)

MarshalBinary encodes the floors, sorted by part so that two callers holding the same clocks produce the same bytes.

A clock above MaxClock is refused for the reason a sequence number is: it is not something this package can have produced, so carrying it would be carrying somebody else's mistake onto the wire.

func (*CompositeClocks) UnmarshalBinary added in v0.36.0 

func (c *CompositeClocks) UnmarshalBinary(in []byte) error

UnmarshalBinary reads what MarshalBinary wrote, and refuses anything else: these arrive from a peer, so nothing about them is trusted.

type CompositeVersion added in v0.11.0 

type CompositeVersion map[Part]VersionVector

A CompositeVersion records what a replica holds, part by part. There is no single vector for a composite, because there is no single sequence of operations: each part counts its own, so what a peer is missing is a question asked once per part.

The nil version is valid and reads as "nothing at all", and a part mapped to a vector that promises nothing is the same as a part not mentioned.

func (CompositeVersion) Clone added in v0.11.0 

func (v CompositeVersion) Clone() CompositeVersion

Clone returns an independent copy, vectors included.

func (CompositeVersion) Equal added in v0.11.0 

func (v CompositeVersion) Equal(other CompositeVersion) bool

Equal reports whether v and other describe the same operations. A part promising nothing counts as absent, so a nil version equals one whose every part is empty.

func (CompositeVersion) MarshalBinary added in v0.11.0 

func (v CompositeVersion) MarshalBinary() ([]byte, error)

MarshalBinary encodes the version. A peer sends this on every join, and a document with one map part per comment has hundreds of parts and a handful of sites, so the sites are written once in a table and each part's entries name an index into it.

That is not a micro-economy. A SiteID is a whole uint64 — DeriveSiteID hashes one, so it uses the range — and a uint64 is ten bytes as a varint, while an index into a table of three is one. Repeating the identity in every part would put nine tenths of the message in the same three numbers written three hundred times.

Like VersionVector.MarshalBinary it carries no magic: it travels in a field whose type is already known.

A part that could not name anything is refused rather than encoded, as is a sequence number above MaxClock, which no replica could have issued.

func (*CompositeVersion) UnmarshalBinary added in v0.11.0 

func (v *CompositeVersion) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes a version written by MarshalBinary.

It arrives from a peer, so it is a trust boundary, and what it is held to is that no two *structures* describe one version: the site table ascends and is used in full, the parts ascend, each part's entries ascend, and no part is written that promises nothing. Each of those would otherwise let a peer state the same thing two ways, and one of the two would be a shape nothing here produces.

What that does not reach is the varint layer underneath it. binary.Uvarint accepts an overlong encoding — 0x80 0x00 is a zero written in two bytes — so bytes this decoder accepts may still re-encode shorter. Every decoder in this package inherits that from the reader they share, and the guarantee is therefore the one they all make: what this package encodes reloads to itself byte for byte, and what it accepts is normalised. A caller wanting to compare two peers by their bytes must compare what MarshalBinary gave back, not what arrived.

A sequence number above MaxClock names an operation no replica could have issued, and is refused here rather than in the parts, because a version never passes through a part's loader; see MaxClock.

type Digest added in v0.51.0 

type Digest [32]byte

A Digest fingerprints what a replica holds: equal digests for replicas holding the same document, different ones otherwise.

It is not a version and cannot be ordered or subtracted. Two replicas learn from it that they differ, not which of them is behind — that is what the version vector is for, and the two are exchanged together.

func (Digest) String added in v0.51.0 

func (d Digest) String() string

String renders a digest as hex, which is how an operator sees one: a mismatch is worth logging, and a 32-byte array is not worth reading as decimal.

type Doc 

type Doc struct {
	// contains filtered or unexported fields
}

A Doc is one replica of a text document. It is not safe for concurrent use; serialize access from the outside, as an editor naturally does.

The zero Doc is unusable — construct one with New or Load.

func Load 

func Load(site SiteID, snapshot []byte) (*Doc, error)

Load rebuilds a document from a snapshot, to be edited as site. The site need not be one that appears in the snapshot — a client joining an existing document brings its own.

Example

A replica joining an existing session is given a snapshot rather than the whole history, and can take part immediately. 

package main

import (
	"fmt"

	"github.com/go-crdt/crdt"
)

func main() {
	server := crdt.New(1)
	if _, err := server.Insert(0, "shared draft"); err != nil {
		panic(err)
	}

	client, err := crdt.Load(2, server.Snapshot())
	if err != nil {
		panic(err)
	}
	edit, err := client.Insert(client.Len(), " — revised")
	if err != nil {
		panic(err)
	}
	if err := server.Apply(edit...); err != nil {
		panic(err)
	}

	fmt.Println(server)
}

Output:
shared draft — revised

func New 

func New(site SiteID) *Doc

New returns an empty document that issues operations as site. Every replica editing a document concurrently must pass a distinct site; see SiteID.

func (*Doc) Anchor added in v0.7.0 

func (d *Doc) Anchor(pos int) (ID, error)

Anchor returns the identity of the character at visible offset pos.

The identity does not move. Insertions and deletions elsewhere change which offset the character sits at, and never change what it is, so an anchor is what a comment, a mark or a selection should be stored as — an offset stored instead would point somewhere else the moment anyone edits above it.

pos may equal Doc.Len, which anchors to the end of the document and returns the zero ID: the position after every character there is, and the one thing insertions at the end do not move.

func (*Doc) Apply 

func (d *Doc) Apply(ops ...Op) error

Apply integrates operations from peers. Duplicates are ignored, and an operation that arrives before the operations it depends on is buffered until they do, so the caller needs no ordered delivery.

A malformed operation is rejected and nothing in the batch is applied.

An operation wearing the name of one this replica has already applied while saying something else is also rejected -- ErrCollidingID -- and the batch stops there, so what came before it in the batch has been applied and what comes after has not. A duplicate says the same thing and is still ignored in silence.

func (*Doc) ApplyAbsorbed added in v0.32.0 

func (d *Doc) ApplyAbsorbed(ops ...Op) ([]Op, error)

ApplyAbsorbed is Doc.Apply, and also reports the operations it integrated, including any that had been parked waiting for them.

The order is the order they were integrated in, which is a causal order: an operation appears after the one it was waiting for.

func (*Doc) ApplyChanges added in v0.7.0 

func (d *Doc) ApplyChanges(ops ...Op) ([]Change, error)

ApplyChanges is Doc.Apply, and also reports what the document did: the edits a view of the text has to make to catch up, in the order it has to make them.

Only what actually happened is reported. An operation already applied, or one still waiting for the operations it depends on, changes nothing and says nothing; when it does land, the change is reported then.

Finding where each edit landed costs a walk up the index per operation, which Doc.Apply does not pay. Use that one when nothing is watching.

func (*Doc) Author added in v0.7.0 

func (d *Doc) Author(pos int) (SiteID, error)

Author returns the replica that wrote the character at visible offset pos.

func (*Doc) AuthorRuns added in v0.7.0 

func (d *Doc) AuthorRuns() []AuthorRun

AuthorRuns splits the visible text into stretches by who wrote them, in order. It is what colouring a document by author needs, and it costs one pass rather than one lookup per character.

Adjacent stretches by the same replica are joined, so the result depends on the text rather than on how the document happens to be stored: two replicas holding the same document return the same runs.

func (*Doc) CanServe added in v0.41.0 

func (d *Doc) CanServe(v VersionVector) error

CanServe reports whether this replica can still answer for a peer at v, returning nil when it can and ErrPurged when a purge has taken what answering would need. Ask it before Doc.OpsSince, and send a Doc.Snapshot instead when it refuses.

A document that has purged nothing accepts every version, including one that has seen nothing at all.

It answers for reading the past as well as for serving a peer, and the two are one question rather than two that happen to agree: it accepts v only when every purged character was both written and deleted as of v, and a character deleted as of v is one no reading of v would have shown.

It is not enough for v to be past the deletions

The obvious condition — nothing purged was still visible at v — is the one for reading and not the one for serving, and it accepts the worst peer there is. A version that never saw a purged run at all was never shown those characters, so it passes; and it is precisely the version that must be refused, because everything the purge took is what it is owed. Measured on a forty-edit document, purged: the weaker condition accepted the empty version vector, and the 798 operations sent to a peer at it all parked.

func (*Doc) ChangesSince added in v0.26.0 

func (d *Doc) ChangesSince(v VersionVector) []Change

ChangesSince returns the edits that turn the text as it stood at v into the text as it stands now, in order, with offsets into the text being edited as each is applied — the same shape Doc.ApplyChanges reports, so a caller that can replay one can replay the other.

It is not a diff. Two texts can be turned into one another in many ways and a diff picks one; this reports what actually happened, because every character says whether it arrived since v and every deletion says whether it did. Text that was written and then removed, both since v, is in neither the old text nor the new one and is reported in neither.

func (*Doc) Delete 

func (d *Doc) Delete(pos, length int) ([]Op, error)

Delete removes length runes starting at rune offset pos and returns the operations that describe it. Deleting nothing is a no-op.

func (*Doc) DeleteUTF16 added in v0.8.0 

func (d *Doc) DeleteUTF16(pos, length int) ([]Op, error)

DeleteUTF16 is Doc.Delete with pos and length counted in UTF-16 code units rather than in runes.

Both ends of the range are converted, so length is a number of code units and the number of characters removed may be fewer — deleting the four units of two emoji removes two characters. A range whose either end splits a character is refused; see ErrSurrogateBoundary.

func (*Doc) Digest added in v0.51.0 

func (d *Doc) Digest() Digest

Digest fingerprints the visible text and the identity of every character in it, in document order.

No flush first, deliberately: [Doc.flush] settles the index summaries in tree.go, and this reads the blocks themselves, which are never behind.

func (*Doc) DropPending added in v0.31.0 

func (d *Doc) DropPending() int

DropPending forgets the operations this replica is holding back, and returns how many there were.

An operation that arrives before the one it depends on is parked, which is right: it may become applicable a moment later, and dropping it silently would lose an edit. What is not right is that nothing bounds the pile. A peer sending operations that can never apply — each waiting on a sequence number that site never issues — costs about 140 bytes apiece, forever, for a document that stays empty.

This is the lever for that, and it is safe for one reason: a parked operation has had no effect on the state, so it is not in the version vector. A peer asked what this replica is missing sends it again. Dropping and re-syncing therefore loses nothing and diverges from nobody — which is asserted in the tests rather than argued here.

It is deliberately the caller's decision. A cap inside this package would have to choose what to do when it is reached, and the only answers are to drop — which is a policy, not a merge rule — or to refuse an Apply for reasons that have nothing to do with what it was handed.

func (*Doc) Insert 

func (d *Doc) Insert(pos int, text string) ([]Op, error)

Insert adds text at rune offset pos and returns the operations that describe it. The operations are already applied here; send them to every peer.

pos may equal Doc.Len, which appends. Inserting the empty string is a no-op that returns no operations.

func (*Doc) InsertUTF16 added in v0.8.0 

func (d *Doc) InsertUTF16(pos int, text string) ([]Op, error)

InsertUTF16 is Doc.Insert with pos counted in UTF-16 code units rather than in runes. The text itself is a Go string, and so is measured in neither.

Example

A browser's cursor offset counts UTF-16 code units, and an emoji is two of them. Handing that offset to Insert would put the text one place to the left of where the user asked for it, without an error and without a trace. 

package main

import (
	"fmt"

	"github.com/go-crdt/crdt"
)

func main() {
	doc := crdt.New(1)
	if _, err := doc.Insert(0, "ship \U0001F680 it"); err != nil {
		panic(err)
	}

	// Nine characters, ten code units: the rocket is one and two.
	fmt.Println(doc.Len(), doc.LenUTF16())

	// The editor reports its caret just after the rocket, which is code unit
	// seven and character six.
	if _, err := doc.InsertUTF16(7, " now"); err != nil {
		panic(err)
	}
	fmt.Println(doc)

	// The offset between the rocket's two units names no position at all.
	_, err := doc.InsertUTF16(6, "x")
	fmt.Println(err)

}

Output:
9 10
ship 🚀 now it
crdt: UTF-16 offset splits a surrogate pair

func (*Doc) Len 

func (d *Doc) Len() int

Len returns the number of visible characters, counted in runes.

func (*Doc) LenAt added in v0.26.0 

func (d *Doc) LenAt(v VersionVector) int

LenAt returns how many characters the text held at version v, without building it.

func (*Doc) LenUTF16 added in v0.8.0 

func (d *Doc) LenUTF16() int

LenUTF16 returns the length of the document in UTF-16 code units — the number JavaScript's String.prototype.length reports for Doc.String.

It is a counter, not a walk: the count of visible supplementary characters is maintained beside the count of visible characters, so this reads the document no more than Doc.Len does.

func (*Doc) OpsSince 

func (d *Doc) OpsSince(vv VersionVector) []Op

OpsSince returns the operations this replica holds that vv does not, ready to be sent to the peer that produced vv. Pass a nil vector for the whole history.

The result is in document order, which for insertions is a causal order: a character always follows its origin. Deletions may arrive before the insertions they refer to, which the receiving Doc.Apply buffers.

A deletion's Lamport timestamp is not retained — it never affects ordering — so replayed deletions carry their sequence number as their clock.

Example

A replica that has been away asks for what it missed by handing over its version vector; it is sent those operations and nothing else. 

package main

import (
	"fmt"

	"github.com/go-crdt/crdt"
)

func main() {
	online, offline := crdt.New(1), crdt.New(2)
	start, err := online.Insert(0, "notes")
	if err != nil {
		panic(err)
	}
	if err := offline.Apply(start...); err != nil {
		panic(err)
	}

	// The offline replica misses everything that follows.
	if _, err := online.Insert(5, ": chapter one"); err != nil {
		panic(err)
	}
	if _, err := online.Delete(0, 1); err != nil {
		panic(err)
	}

	missed := online.OpsSince(offline.Version())
	fmt.Println(len(missed), "operations missed")
	if err := offline.Apply(missed...); err != nil {
		panic(err)
	}
	fmt.Println(offline)
}

Output:
14 operations missed
otes: chapter one

func (*Doc) Pending 

func (d *Doc) Pending() int

Pending returns the number of operations buffered awaiting their dependencies. A healthy replica returns to zero once delivery catches up; a number that only grows means a peer is withholding operations.

func (*Doc) Position added in v0.7.0 

func (d *Doc) Position(anchor ID) (pos int, ok bool)

Position returns where the character an anchor names sits now.

A deleted character still has a place — the offset it would occupy, which is where the text around it closed up — and that is returned too, because a comment on a deleted sentence belongs where the sentence was rather than nowhere. Use Doc.Visible to tell the two apart.

The zero ID anchors to the end of the document. ok is false only for an identity this document has never seen, which means the anchor came from somewhere else or the operations that would explain it have not arrived.

func (*Doc) Purge added in v0.41.0 

func (d *Doc) Purge() int

Discarding what a document no longer says.

A deletion hides a character and does not forget it, because a replica that forgot could not tell a character arriving late from one it had already seen. The identity has to stay. What does not have to stay is the character itself: once it is deleted, nobody can read it, and the only thing still asking about it is the past.

So a purged run keeps its identity, its length, its origin and the operations that deleted it, and drops the characters. Nothing is re-pointed and nothing moves: a survivor that named one of these characters still finds it, because it is still there — which is the whole difference between this and the collection that was withdrawn in v0.35.0 for leaving two replicas holding different documents.

This is the shape Yjs uses. `Item.gc` replaces a deleted item in place with `GC(this.id, this.length)` and re-points nothing, and Yjs runs it unconditionally rather than waiting for every replica to have seen the deletion. That it converges under concurrency was checked against Yjs itself before this was written: two hundred random histories over five peers with gc on, and all of them agree.

What it costs

A peer that is behind it. A purged run is not in Doc.OpsSince at all — neither its insertions nor the deletions that explain them, because both are read from characters that are gone — so a peer missing any of them is sent a history with a hole in it and parks everything that followed. That is what Doc.CanServe is for: ask before serving, and send a Doc.Snapshot instead of operations to a version it refuses.

The past, in the same breath and for the same reason. Doc.TextAt, Doc.LenAt and Doc.ChangesSince read the characters, so a version in which a purged character was still visible reads back without it. None of the three can refuse — they return no error, and giving them one would break every caller — so the refusal is the caller's to make, against the same question: a version Doc.CanServe accepts is one whose text this replica can still rebuild, because accepting it means every purged character was already deleted at that version.

Nothing else. A purged run answers to its identity exactly as it did, so an operation naming one still finds it, and an ordinary edit from a peer that never purged applies unchanged.

Reading one back costs what it holds rather than what it says. That is worth writing down because the opposite is what a purged run invites: it names a million characters in a uvarint and carries none of them, so a reader that wrote them out to throw them away would turn a hundred bytes into hundreds of megabytes, on input a peer chooses. Load integrates the first character of such a run and claims the rest as a stretch; see readRun in snapshot.go.

Purge reports how many characters it discarded.

func (*Doc) PurgedBelow added in v0.41.0 

func (d *Doc) PurgedBelow() uint64

PurgedBelow reports the highest clock this replica has discarded a character under, and zero for a document nobody has purged.

It is a clock rather than a version because what a purge takes is a moment, and a moment is what a clock names. It says that this replica has given something up; it does not say which peers that costs, which is a question about a version vector and is Doc.CanServe's to answer.

func (*Doc) Rewritten added in v0.33.0 

func (d *Doc) Rewritten(site SiteID) (*Doc, error)

Rewriting a replica trades its past for its size.

A replica remembers every operation ever applied to it, including the ones that removed things: a deletion hides a character, it does not forget it, because a replica that forgot could not tell a late arrival apart from a character it had already seen. That memory is what makes merging work without a server, and it is also what makes a heavily revised document larger than its text.

A rewrite builds a new replica holding the same content and none of the history. What that buys is exactly what was deleted and nothing else: a document nothing was ever removed from rewrites to the same size, while one that was emptied rewrites to nothing. Measured on a text of 40 000 edits: no deletions, 1.0x; a third of it deleted, 1.6x; all of it, four orders of magnitude.

What it costs is every identity. The new replica mints its own, so:

  • Operations from the old replica no longer apply to the new one. They are not rejected and they do not corrupt it; they anchor to characters it has never heard of, so they park as pending and stay there. Any replica still holding the old identities has to be replaced by the rewrite, not merged with it.
  • Anything anchored to a character is left pointing at nothing. This is the same trap [Proposals] exists to avoid, and it is why there is no rewrite for a Composite: rich text marks, tree parents and sequence positions are stored against the identities of the characters they describe, and a composite cannot tell a part that carries such anchors from one that does not. Rewrite the parts you know are plain, or rebuild the anchors yourself.

So a rewrite belongs where a document is quiescent and about to be archived, or where a single writer is compacting its own copy. It does not belong in a live session.

Rewritten returns a new document with this one's text, minted at site. Pass a site the old replica never used: reusing one would let two different characters carry the same identity, which is the one thing a replica may not allow.

func (*Doc) RuneOffset added in v0.8.0 

func (d *Doc) RuneOffset(pos int) (int, error)

RuneOffset converts a UTF-16 offset into the rune offset naming the same position. pos may equal Doc.LenUTF16, which converts to Doc.Len.

An offset falling between the two code units of one character is refused with ErrSurrogateBoundary; see there for why, and for the one-line way to round it down instead.

func (*Doc) Site 

func (d *Doc) Site() SiteID

Site returns the replica identity this document issues operations as.

func (*Doc) Snapshot 

func (d *Doc) Snapshot() []byte

Snapshot encodes the whole document — every character, alive or tombstoned, in document order, plus the version vector. It is what a server sends a client joining an existing session, and what it persists.

Characters are written in runs: one header for a stretch one site typed consecutively, then its text, then the stretches of it that have been deleted. Writing one record per character instead, as version 1 did, cost twenty-five bytes for every character of a real document — measured against other implementations, between eight and twenty-four times what they need.

The runs written are maximal, whatever boundaries the document happens to hold in memory. That is what keeps the encoding canonical: two replicas that have applied the same operations produce identical bytes even if the operations arrived in different orders, so a snapshot doubles as a convergence check. It also keeps the format independent of the layout a replica stores, which is what let that layout change twice without a flag day.

The full history is recoverable from a snapshot: Doc.OpsSince on a loaded document returns the same operations it would have on the original.

func (*Doc) String 

func (d *Doc) String() string

String returns the document text.

func (*Doc) TextAt added in v0.26.0 

func (d *Doc) TextAt(v VersionVector) string

TextAt returns the text as it stood at version v: every character whose insertion v had seen, less every character whose deletion v had seen.

A version this replica has not reached is not refused. Operations it has not seen simply are not in the document to be counted, so the answer is the text as of everything the two have in common — which is what a replica can honestly say about a version it does not hold.

func (*Doc) Tombstones 

func (d *Doc) Tombstones() int

Tombstones returns the number of deleted characters still held in memory. They cannot be dropped, because a concurrent insertion may name one as its origin; see docs/performance.md.

func (*Doc) UTF16Offset added in v0.8.0 

func (d *Doc) UTF16Offset(pos int) (int, error)

UTF16Offset converts a rune offset into the UTF-16 offset naming the same position. pos may equal Doc.Len, which converts to Doc.LenUTF16.

This is the direction an editor needs to place someone else's cursor, or to report where an edit of its own landed.

Example

Awareness offsets are rune positions, because both peers have to agree what an offset means and an update has nowhere to say. A peer whose editor counts UTF-16 converts at its own edge — where it has to clamp in any case, since a cursor may describe a document longer than the one it now has. 

package main

import (
	"fmt"

	"github.com/go-crdt/crdt"
	"github.com/go-crdt/crdt/awareness"
)

func main() {
	doc := crdt.New(1)
	if _, err := doc.Insert(0, "\U0001F600 hello"); err != nil {
		panic(err)
	}

	peers := awareness.New()
	peers.Apply(awareness.Update{Site: 2, Clock: 1, Cursor: awareness.Cursor{Anchor: 2, Head: 99}})

	for _, peer := range peers.Peers() {
		head := min(max(peer.Cursor.Head, 0), doc.Len())
		at, err := doc.UTF16Offset(head)
		if err != nil {
			panic(err)
		}
		fmt.Println("caret at code unit", at)
	}
}

Output:
caret at code unit 8

func (*Doc) Version 

func (d *Doc) Version() VersionVector

Version returns a copy of the version vector describing which operations this replica holds. Pass it to a peer's Doc.OpsSince to be sent exactly what is missing.

func (*Doc) Visible added in v0.7.0 

func (d *Doc) Visible(anchor ID) bool

Visible reports whether the character an anchor names is still in the text.

type Format added in v0.40.0 

type Format uint8

A Format is one of the snapshot encodings this package writes. Each has a version of its own, moving at its own pace: a change to how a text is written does not disturb a map. 

const (
	FormatText Format = iota + 1
	FormatList
	FormatMap
	FormatComposite
)

The four snapshot encodings. A composite snapshot embeds one of each of the other three, so reading a composite means reading whatever it contains.

func Formats added in v0.40.0 

func Formats() []Format

Formats reports every format this build knows, in order, so a peer can say what it reads without a list of its own to keep in step.

func (Format) String added in v0.40.0 

func (f Format) String() string

String names a format, and says so for one this build does not know rather than printing a bare number.

type ID 

type ID struct {
	Site SiteID
	Seq  uint64
}

ID names a single operation, and — for an insertion — the character that operation created. It is unique across replicas because Site is unique and Seq counts that site's own operations.

The zero ID is the document root: the virtual character that precedes all content. It is a valid insertion origin and is never the ID of a real operation, because Seq starts at one.

func (ID) IsRoot 

func (id ID) IsRoot() bool

IsRoot reports whether id names the virtual character at the start of every document rather than a real operation.

The test is on Seq alone, because Seq counts from one: no operation ever carries zero, whatever its site. A decoder that only compared against the zero ID would let a sequence number of zero paired with a non-zero site through as if it named something real.

func (ID) String 

func (id ID) String() string

String renders the ID as "seq@site", the notation used in the CRDT literature. The root prints as "root".

type List added in v0.9.0 

type List struct {
	// contains filtered or unexported fields
}

A List is one replica of a sequence of values. It is not safe for concurrent use; serialize access from the outside.

The zero List is unusable — construct one with NewList or LoadList.

func LoadList added in v0.9.0 

func LoadList(site SiteID, snapshot []byte) (*List, error)

LoadList rebuilds a list from a snapshot, to be edited as site.

func NewList added in v0.9.0 

func NewList(site SiteID) *List

NewList returns an empty list that issues operations as site. Every replica editing a list concurrently must pass a distinct site; see SiteID.

func (*List) Anchor added in v0.9.0 

func (l *List) Anchor(pos int) (ID, error)

Anchor returns the identity of the value at index pos, which keeps naming that value however the list moves around it — what a reference to a comment should hold. pos may equal List.Len, which anchors to the end and returns the zero ID.

func (*List) Apply added in v0.9.0 

func (l *List) Apply(ops ...ListOp) error

Apply integrates operations from peers. Duplicates are ignored, and an operation arriving before what it depends on waits until that lands.

A malformed operation is rejected and nothing in the batch is applied.

func (*List) ApplyAbsorbed added in v0.32.0 

func (l *List) ApplyAbsorbed(ops ...ListOp) ([]ListOp, error)

ApplyAbsorbed is List.Apply, and also reports the operations it integrated, including any that had been parked waiting for them.

func (*List) ApplyChanges added in v0.13.0 

func (l *List) ApplyChanges(ops ...ListOp) (bool, error)

ApplyChanges is List.Apply, and also reports whether the list is not what it was. An operation already applied, or one still waiting for the operation its site issued before it, changes nothing and reports false; when a waiting one lands, that call reports true.

It reports that something changed rather than what, which is a deliberate stop. Naming the positions would be a second protocol to keep correct, and the consumers this was written for read the whole list back when they are told — a list here holds tens or hundreds of values, not the hundreds of thousands a document holds, which is the same reason a list is a slice and a document is not. A caller that needs the positions can be given them without breaking anyone; none has needed them yet.

func (*List) Delete added in v0.9.0 

func (l *List) Delete(pos, count int) ([]ListOp, error)

Delete removes count values from index pos and returns the operations describing it. Removing nothing is a no-op.

func (*List) Digest added in v0.51.0 

func (l *List) Digest() Digest

Digest fingerprints the values present in the list, in list order, each with the identity that carries it.

func (*List) DropPending added in v0.31.0 

func (l *List) DropPending() int

DropPending forgets the operations this replica is holding back, and returns how many there were.

An operation that arrives before the one it depends on is parked, which is right: it may become applicable a moment later, and dropping it silently would lose an edit. What is not right is that nothing bounds the pile. A peer sending operations that can never apply — each waiting on a sequence number that site never issues — costs about 140 bytes apiece, forever, for a document that stays empty.

This is the lever for that, and it is safe for one reason: a parked operation has had no effect on the state, so it is not in the version vector. A peer asked what this replica is missing sends it again. Dropping and re-syncing therefore loses nothing and diverges from nobody — which is asserted in the tests rather than argued here.

It is deliberately the caller's decision. A cap inside this package would have to choose what to do when it is reached, and the only answers are to drop — which is a policy, not a merge rule — or to refuse an Apply for reasons that have nothing to do with what it was handed.

func (*List) Get added in v0.9.0 

func (l *List) Get(pos int) ([]byte, error)

Get returns a copy of the value at index pos.

func (*List) Insert added in v0.9.0 

func (l *List) Insert(pos int, values ...[]byte) ([]ListOp, error)

Insert adds values at index pos and returns the operations describing it. The operations are already applied here; send them to every peer.

pos may equal List.Len, which appends. Inserting nothing is a no-op.

func (*List) Len added in v0.9.0 

func (l *List) Len() int

Len returns the number of values present.

func (*List) LenAt added in v0.26.0 

func (l *List) LenAt(v VersionVector) int

LenAt returns how many elements the list held at version v, without building them.

func (*List) OpsSince added in v0.9.0 

func (l *List) OpsSince(vv VersionVector) []ListOp

OpsSince returns the operations this replica holds that vv does not, ready to send to the peer that produced vv. Pass a nil vector for the whole history.

The result is in list order, which for insertions is a causal order: an element always follows its origin.

func (*List) Pending added in v0.9.0 

func (l *List) Pending() int

Pending returns the number of operations waiting for the operations they depend on.

func (*List) Position added in v0.9.0 

func (l *List) Position(anchor ID) (pos int, ok bool)

Position returns where the value an anchor names sits now, or where it was if it has been removed. ok is false for an identity this list has never seen.

func (*List) Rewritten added in v0.33.0 

func (l *List) Rewritten(site SiteID) (*List, error)

Rewritten returns a new list with this one's values, minted at site. It trades the list's past for its size on the terms described on Doc.Rewritten.

func (*List) Site added in v0.9.0 

func (l *List) Site() SiteID

Site returns the replica identity this list issues operations as.

func (*List) Snapshot added in v0.9.0 

func (l *List) Snapshot() []byte

Snapshot encodes the whole list — every value, present or removed, in order, plus the version vector. It is what a server sends a client joining, and what it persists.

The encoding is deterministic: two replicas holding the same operations produce identical bytes, so a snapshot doubles as a convergence check. The full history is recoverable: List.OpsSince on a loaded list returns what it would have on the original.

func (*List) Tombstones added in v0.9.0 

func (l *List) Tombstones() int

Tombstones returns the number of removed values still held. They cannot be dropped: a concurrent insertion may still name one as its origin.

func (*List) Values added in v0.9.0 

func (l *List) Values() [][]byte

Values returns copies of every value present, in order.

func (*List) ValuesAt added in v0.26.0 

func (l *List) ValuesAt(v VersionVector) [][]byte

ValuesAt returns the elements the list held at version v, in order: every element whose insertion v had seen, less every element whose deletion v had seen. It reads the list the way Doc.TextAt reads the text, and for the same reason — an element carries the identity of what made it and of what removed it, so the list is its own history.

func (*List) Version added in v0.9.0 

func (l *List) Version() VersionVector

Version returns a copy of the version vector describing which operations this replica holds.

func (*List) Visible added in v0.9.0 

func (l *List) Visible(anchor ID) bool

Visible reports whether the value an anchor names is still in the list.

type ListOp added in v0.9.0 

type ListOp struct {
	// Kind selects insertion or deletion.
	Kind OpKind
	// ID names this operation, its Seq counting the issuing site's operations.
	ID ID
	// Clock is the Lamport timestamp ordering this against concurrent
	// operations; see the package documentation on the two counters.
	Clock uint64
	// Origin is the element the new one is inserted after; the zero ID means
	// the start of the list. OpInsert only.
	Origin ID
	// Value is the inserted element. OpInsert only.
	Value []byte
	// Target is the element to remove. OpDelete only.
	Target ID
	// Span is how many consecutive sequence numbers this operation accounts for,
	// ending at ID.Seq. OpSuperseded only. See [OpSuperseded], and the note
	// there on which operations a run may stand in for: an insertion is named by
	// what was inserted after it and is not one of them.
	Span uint64
}

A ListOp is one indivisible change to a list. Like Op it is self-describing and applying it is idempotent, so a transport may duplicate or reorder freely.

func ParseListOps added in v0.12.0 

func ParseListOps(data []byte) ([]ListOp, error)

ParseListOps decodes a batch written by AppendListOps.

func ParseListOpsLimit added in v0.50.0 

func ParseListOpsLimit(data []byte, max int) ([]ListOp, error)

ParseListOpsLimit is ParseListOps with a ceiling on how many operations the message may claim: zero is unlimited, and any other value refuses a larger claim with ErrTooManyOps before reserving for it. See ErrTooManyOps.

func (ListOp) MarshalBinary added in v0.12.0 

func (o ListOp) MarshalBinary() ([]byte, error)

MarshalBinary encodes the operation. It reports ErrInvalidOp rather than producing bytes that would be rejected on arrival.

func (*ListOp) UnmarshalBinary added in v0.12.0 

func (o *ListOp) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes an operation written by MarshalBinary. Trailing bytes are an error: an operation is decoded from exactly its own encoding.

type Map added in v0.10.0 

type Map struct {
	// contains filtered or unexported fields
}

A Map is a replicated key-value map: any number of replicas may write to it at once, offline, in any delivery order, and every replica ends up holding the same keys and the same values. Values are opaque bytes — the caller encodes whatever it likes — and they are copied in and out, so no slice is ever shared between a caller and the map.

Writes to one key are ordered by the same (clock, site) total order the text uses: a Lamport clock raised past everything the replica has seen, ties broken by site. The highest write wins, and it wins everywhere whatever order the writes arrived in, because a maximum does not depend on the order it is taken in. Writes to different keys never interact at all.

A deleted key keeps its clock

A deletion leaves a record behind rather than dropping the key. Dropping it would leave nothing for an older write arriving later to lose against, so that write would take effect — resurrecting the key on the replica that heard it late and not on the one that heard it early, permanently. Keeping the clock is also what makes a delete and a concurrent set to the same key resolve identically everywhere. Map.Len and Map.Keys do not count a deleted key; Map.Snapshot writes it.

What a replica may forget, and what it may not

A map keeps one record per key, so the value a write put there is gone the moment a later write replaces it. The operation is not gone. Sequence numbers are contiguous per site — that is what lets a VersionVector describe a replica exactly — and Map.Apply never skips one: an operation that arrives before its predecessor waits for it rather than being dropped. A peer catching up therefore has to be told that the number was used, and Map.OpsSince tells it with a MapSuperseded operation, which names no key, carries no value, and covers a whole run of numbers at once. Catching up a peer from nothing therefore costs one operation per key it does not hold plus one per stretch it does not need, never one per write ever made.

That is sound only because the operation which superseded it travels in the same batch: it is either the record now held for that key, which OpsSince sends whenever the peer lacks it, or something the peer already has. A caller that filters what OpsSince returns breaks the map.

A Map is not safe for concurrent use. The zero Map is unusable — construct one with NewMap or LoadMap.

Example

Two replicas write to the same cell at the same time, and one of them then deletes it. The later write wins wherever the operations arrive, and the deleted cell keeps the clock that beat them: an older write turning up afterwards cannot bring it back. 

package main

import (
	"fmt"

	"github.com/go-crdt/crdt"
)

func main() {
	ada, grace := crdt.NewMap(1), crdt.NewMap(2)

	fromAda, err := ada.Set("B7", []byte("41"))
	if err != nil {
		panic(err)
	}
	fromGrace, err := grace.Set("B7", []byte("42"))
	if err != nil {
		panic(err)
	}
	if err := ada.Apply(fromGrace); err != nil {
		panic(err)
	}
	if err := grace.Apply(fromAda); err != nil {
		panic(err)
	}

	value, _ := ada.Get("B7")
	fmt.Printf("%s %s\n", value, ada.Keys())

	// Grace clears the cell, having seen both writes.
	cleared, err := grace.Delete("B7")
	if err != nil {
		panic(err)
	}
	if err := ada.Apply(cleared); err != nil {
		panic(err)
	}
	_, present := ada.Get("B7")
	fmt.Println(present, ada.Len())

}

Output:
42 [B7]
false 0

func LoadMap added in v0.10.0 

func LoadMap(site SiteID, snapshot []byte) (*Map, error)

LoadMap rebuilds a map from a snapshot, to be written as site. The site need not be one that appears in the snapshot — a client joining an existing map brings its own.

A snapshot arrives over a network, so most of what follows is refusing states no replica could have reached. The version vector is what the rest is measured against: a record written by an operation the vector does not promise, or by an operation another record already claims, describes a map that could not reproduce its own history.

func NewMap added in v0.10.0 

func NewMap(site SiteID) *Map

NewMap returns an empty map that issues operations as site. Every replica writing to a map concurrently must pass a distinct site; see SiteID.

func (*Map) Apply added in v0.10.0 

func (m *Map) Apply(ops ...MapOp) error

Apply integrates operations from peers. Duplicates are ignored, and an operation that arrives before the operation its site issued before it is buffered until that one lands, so the caller needs no ordered delivery.

A malformed operation is rejected and nothing in the batch is applied.

func (*Map) ApplyAbsorbed added in v0.32.0 

func (m *Map) ApplyAbsorbed(ops ...MapOp) ([]MapOp, error)

ApplyAbsorbed is Map.Apply, and also reports the operations it integrated, including any that had been parked waiting for them.

func (*Map) ApplyChanges added in v0.13.0 

func (m *Map) ApplyChanges(ops ...MapOp) ([]string, error)

ApplyChanges is Map.Apply, and also reports which keys it changed: those whose value or presence is not what it was, in ascending order so that two replicas given the same batch report the same thing.

Only what actually happened is reported. An operation already applied, one still waiting for the operation its site issued before it, and one that lost to a write already held all change nothing and say nothing; when a waiting one lands, its key is reported then.

A key is named, not its new value. A caller reads what it wants of the key it is told about, which is also what keeps this honest when a batch writes one key twice: the key appears once, and reading it gives the winner.

func (*Map) Clock added in v0.36.0 

func (m *Map) Clock() uint64

Clock reports the Lamport clock this replica has reached.

Every operation it issues from now on carries a clock above this one, which is what makes it the bound on a site that has written nothing yet: a participant handed this document writes later than it, whatever it does. A caller building a floor for Map.Collect needs that bound for the sites Map.LastClocks cannot speak for.

func (*Map) Collect added in v0.33.0 

func (m *Map) Collect(stable VersionVector, below uint64) int

Collect drops the tombstones nothing can still be confused by.

A map keeps one record per key rather than one per edit, so it has far less past to give back than a text or a list: what accumulates is not the history of a key but the keys that were deleted. A diagram whose nodes come and go carries every node it ever held, as a record saying that node is gone.

A tombstone is kept for one reason, which [Map.integrate] states: it is what stops an older set resurrecting a key somebody has since deleted. So it may go once no replica can still send a write that would lose to it.

That takes two things, and for a long time this asked for only one of them.

The first is a version every replica has delivered, exactly as elsewhere; see [Doc.Collect] for what that means and who can know it. The second is a clock, and it is not the same question. A version says which operations everybody holds. It says nothing about the clocks of the operations still in flight: a site that has seen nothing writes at clock one, however far along everyone else is. So a write from a site that had not seen the deletion can arrive afterwards carrying a clock that beats it — and a replica that dropped the tombstone has nothing left to make that comparison against, while one that kept it brings the key back. Two replicas, the same operations, different documents. See TestCollectingLosesAComparisonALaterWriteNeeded.

So below is a clock floor: a promise that no operation with a clock at or under it can still arrive. A tombstone goes when its own clock is at or under that floor, which is what makes every write that can still come strictly later than it — and a write that is strictly later beats it, comes back, and wants no comparison. What needed the tombstone was a write at or below its clock, and the floor is the promise there will not be one.

A replica cannot work the floor out alone, for the same reason it cannot work out the version: it does not know who is out there. Map.LastClocks is what it can offer somebody who does — a server, which everything passes through — and the arithmetic is a minimum over every site that could still send.

What Yjs does instead

It does not do this at all, and the difference is worth stating because it is the whole reason a floor is needed here and nowhere in that codebase.

Yjs collects a deleted item by replacing its *content* and keeping the item: Item.gc, called with parentGCd false, sets this.content = new ContentDeleted(this.length) and leaves the item in the store with its id, its origins and its key. The other branch, for an item whose parent is going too, is replaceStruct(store, this, new GC(this.id, this.length)) — which also keeps the id. Either way the identity survives, so an operation arriving late still finds something to lose to, and no precondition beyond causal delivery is needed. (Read in yjs 13.6.32, src/structs/Item.js and src/utils/Transaction.js.)

What that reclaims is the content. A map's tombstone has none: the record is the space, and giving it back means giving back the identity. So this is an economy Yjs does not attempt, and the floor is its price rather than the repair of a mistake. A diagram whose nodes come and go is what makes the price worth paying; see [Diagram.Collect].

Why this one needs no format version and no floor

A map already gives back a sequence number without its operation: a second write to a key overwrites the first, so the first is gone and Map.OpsSince reports the gap as MapSuperseded rather than pretending the operation is still here. Collecting a tombstone frees a sequence number the same way, and the same span covers it. Nothing on the wire changes, no peer has to be re-seeded, and a map's loader has no completeness ledger to relax because a map never had a complete history to hold it to.

What it costs

Map.Stamp can no longer say when a collected key was deleted; it answers as it does for a key that never existed. That is the whole of what is lost from reading.

What is lost from *misuse* is worse than elsewhere, which is why the guard below exists. Given a version some replica has not delivered, or a floor no caller could promise, that replica's write arrives naming a key whose tombstone is gone, finds no record to lose to, and the key comes back. So a map remembers the highest clock it collected under and refuses a write at or below it for a key it does not hold, with ErrStranded. Given both of the things above, no such operation can arrive at all and the guard never fires; when it does, it is naming the mistake, and Composite.Apply passes it on rather than dropping it.

The guard catches half of that misuse. The other half arrives from the opposite direction and nothing here can see it: the replica that has not delivered the deletion is also the one that will ask for it. Map.OpsSince answers for a collected stretch with MapSuperseded, because under correct use those sequence numbers are accounted for — so that replica's version vector advances over the deletion without it ever learning what the operation did, and it goes on holding a value every other replica removed. Its version vector then equals theirs, which is what makes it permanent: there is nothing left for a catch-up to send. Found this way in a server that collected against the participants it had a connection to rather than every participant it had ever had: two participants, one deletion, and the one that was away came back still holding the key, with a version equal to the server's.

Collect reports how many tombstones it dropped.

func (*Map) CollectedBelow added in v0.33.0 

func (m *Map) CollectedBelow() uint64

CollectedBelow reports the floor this map has been collected against, and zero if it has never been collected.

It is the floor it was asked with rather than the highest clock it actually dropped, and the difference matters: what is dropped depends on what this replica happened to hold, so remembering that would put replica-relative state in the snapshot and two replicas that had applied the same operations would write different bytes.

It is a clock rather than a version, unlike [Doc.Floor] and [List.Floor], because what a map has to recognise is not an operation it dropped but a write that would have lost to one. That comparison is by clock, so the guard is too.

func (*Map) Delete added in v0.10.0 

func (m *Map) Delete(key string) (MapOp, error)

Delete removes key and returns the operation that describes it.

It writes a tombstone whether or not this replica holds the key. What a deletion means cannot depend on what the deleting replica happens to have heard: a peer's write still in flight has to lose to a later deletion on every replica, including one that has not yet seen the write it is beating.

func (*Map) Digest added in v0.51.0 

func (m *Map) Digest() Digest

Digest fingerprints the live keys of the map and the value each holds, in key order, with the identity of the write that put it there.

Key order rather than the map's own, which has none: a Go map is deliberately unordered, so a digest that walked it would differ between two replicas holding the same keys, and between two runs of the same one.

func (*Map) DropPending added in v0.31.0 

func (m *Map) DropPending() int

DropPending forgets the operations this replica is holding back, and returns how many there were.

An operation that arrives before the one it depends on is parked, which is right: it may become applicable a moment later, and dropping it silently would lose an edit. What is not right is that nothing bounds the pile. A peer sending operations that can never apply — each waiting on a sequence number that site never issues — costs about 140 bytes apiece, forever, for a document that stays empty.

This is the lever for that, and it is safe for one reason: a parked operation has had no effect on the state, so it is not in the version vector. A peer asked what this replica is missing sends it again. Dropping and re-syncing therefore loses nothing and diverges from nobody — which is asserted in the tests rather than argued here.

It is deliberately the caller's decision. A cap inside this package would have to choose what to do when it is reached, and the only answers are to drop — which is a policy, not a merge rule — or to refuse an Apply for reasons that have nothing to do with what it was handed.

func (*Map) Get added in v0.10.0 

func (m *Map) Get(key string) ([]byte, bool)

Get returns the value stored at key, and whether the key is present. The value is a copy: writing to it does not change what the map holds.

A value stored as empty reads back as nil — the two are one value here, and the encoding cannot tell them apart either.

func (*Map) Keys added in v0.10.0 

func (m *Map) Keys() []string

Keys returns the keys present, in ascending order, so that anything a caller derives from them is the same on every replica. Deleted keys are not among them.

func (*Map) LastClocks added in v0.36.0 

func (m *Map) LastClocks() map[SiteID]uint64

LastClocks reports, for each site, the clock of the last operation this replica integrated from it.

A site issues in increasing clock order and a transport delivers one site's operations in order, so whatever has not arrived yet from that site carries a clock above the one reported here. That is the whole of what a replica can say about what it has not seen, and it is what a collection floor is built from — by somebody who knows which sites there are to take the minimum over. A replica cannot: a site it has never heard from is missing from this map entirely, and that site is exactly the one whose write is still on its way.

The value is a copy.

func (*Map) Len added in v0.10.0 

func (m *Map) Len() int

Len returns how many keys are present, not counting deleted ones.

func (*Map) OpsSince added in v0.10.0 

func (m *Map) OpsSince(vv VersionVector) []MapOp

OpsSince returns the operations this replica holds that vv does not, ready to be sent to the peer that produced vv. Pass a nil vector for everything.

The result is ordered by site and then by sequence number, so the peer can apply it as it arrives without ever having to buffer. Operations whose values have since been overwritten come back as MapSuperseded runs, carrying nothing but the sequence numbers they stand for; the writes that overwrote them are in the same result, which is what makes that safe. See Map.

func (*Map) Pending added in v0.10.0 

func (m *Map) Pending() int

Pending reports how many received operations are still waiting for the operation their own site issued before them.

func (*Map) Rewritten added in v0.33.0 

func (m *Map) Rewritten(site SiteID) (*Map, error)

Rewritten returns a new map with this one's entries, minted at site. A map keeps one record per key rather than a record per edit, so it has far less past to trade than a text does; this exists so a composite's parts can all be rewritten the same way, on the terms described on Doc.Rewritten.

func (*Map) Set added in v0.10.0 

func (m *Map) Set(key string, value []byte) (MapOp, error)

Set stores value at key and returns the operation that describes it. The operation is already applied here; send it to every peer.

The map copies value, so the caller may reuse the slice, and the returned operation carries a copy of its own, so writing to it cannot reach the map. A key that is not valid UTF-8 is refused; see MapOp.

func (*Map) Site added in v0.20.0 

func (m *Map) Site() SiteID

Site returns the replica this map writes as. Doc and List answer the same question the same way.

func (*Map) Snapshot added in v0.10.0 

func (m *Map) Snapshot() []byte

Snapshot encodes the whole map — every key ever written, deleted ones included, each with the identity and Lamport timestamp of the write it holds — plus the version vector. It is what a server sends a client joining an existing session, and what it persists.

Keys are written in ascending order, so two replicas that have applied the same operations produce identical bytes whatever order those operations arrived in. That makes a snapshot a convergence check: agreeing on the keys and values is weaker than agreeing on the state, because two replicas can agree on every value while disagreeing about which write produced it, and would then resolve the next concurrent write differently.

What a snapshot does not keep is the values of writes that have already lost; see Map for what Map.OpsSince sends in their place.

func (*Map) Stamp added in v0.20.0 

func (m *Map) Stamp(key string) (clock uint64, site SiteID, ok bool)

Stamp returns the (clock, site) the current value of key was written at, and whether the key is live. It is the total order the map resolves concurrent writes by, made readable so that something built on the map can order two writes the same way the map did — see structured.Tree, which has to decide which of two concurrent moves happened later.

func (*Map) Tombstones added in v0.10.0 

func (m *Map) Tombstones() int

Tombstones returns how many keys are held only to keep their clock. They are the one thing here that grows without bound, so a caller measuring what a long session costs measures this.

func (*Map) Version added in v0.10.0 

func (m *Map) Version() VersionVector

Version returns what this replica holds, to be handed to a peer that will send back what it is missing; see Map.OpsSince.

type MapOp added in v0.10.0 

type MapOp struct {
	// Kind selects writing, removal, or values the sender has forgotten.
	Kind MapOpKind
	// ID names this operation. Its Seq is the issuing site's own counter and
	// increases by exactly one per operation. For MapSuperseded it is the last
	// of the sequence numbers the operation accounts for.
	ID ID
	// Clock is the Lamport timestamp that orders this operation against
	// concurrent writes to the same key. See the package documentation.
	Clock uint64
	// Key is the key written or removed. MapSet and MapDelete only.
	Key string
	// Value is the bytes written. MapSet only; it may be empty.
	Value []byte
	// Span is how many consecutive sequence numbers this operation accounts for,
	// ending at ID.Seq. MapSuperseded only, where it is at least one.
	Span uint64
}

A MapOp is one indivisible change to a Map. It is the only thing replicas exchange, it is self-describing, and applying it is idempotent, so a transport may duplicate or reorder operations freely.

Which fields carry meaning depends on Kind: Key belongs to MapSet and MapDelete, Value to MapSet alone, Span to MapSuperseded alone. The unused fields must be zero, and are checked, so a garbled operation is rejected rather than silently reinterpreted.

func ParseMapOps added in v0.10.0 

func ParseMapOps(data []byte) ([]MapOp, error)

ParseMapOps decodes a batch written by AppendMapOps.

func ParseMapOpsLimit added in v0.50.0 

func ParseMapOpsLimit(data []byte, max int) ([]MapOp, error)

ParseMapOpsLimit is ParseMapOps with a ceiling on how many operations the message may claim: zero is unlimited, and any other value refuses a larger claim with ErrTooManyOps before reserving for it. See ErrTooManyOps.

func (MapOp) MarshalBinary added in v0.10.0 

func (o MapOp) MarshalBinary() ([]byte, error)

MarshalBinary encodes the operation. It reports ErrInvalidOp rather than producing bytes that would be rejected on arrival.

func (*MapOp) UnmarshalBinary added in v0.10.0 

func (o *MapOp) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes an operation written by MarshalBinary. Trailing bytes are an error: an operation is decoded from exactly its own encoding.

type MapOpKind added in v0.10.0 

type MapOpKind uint8

MapOpKind distinguishes the operations a replicated map exchanges. 

const (
	// MapSet writes a value at a key.
	MapSet MapOpKind = 1
	// MapDelete removes a key, and leaves its clock behind. See [Map].
	MapDelete MapOpKind = 2
	// MapSuperseded stands in for operations whose values the sending replica no
	// longer holds, because later writes to the same keys replaced them. It names
	// no key and carries no value: it exists so that a peer catching up can
	// account for the sequence numbers and move on. Only [Map.OpsSince] produces
	// one.
	//
	// It covers a run of consecutive sequence numbers rather than one, because
	// the numbers a replica has forgotten are exactly the gaps between the ones
	// it still holds: a key written a million times leaves one record and one
	// run, not a million operations to send.
	MapSuperseded MapOpKind = 3
)

func (MapOpKind) String added in v0.10.0 

func (k MapOpKind) String() string

String renders the kind for diagnostics.

type Op 

type Op struct {
	// Kind selects insertion or deletion.
	Kind OpKind
	// ID names this operation. Its Seq is the issuing site's own counter and
	// increases by exactly one per operation.
	ID ID
	// Clock is the Lamport timestamp that orders this operation against
	// concurrent ones. See the package documentation.
	Clock uint64
	// Origin is the character the new one is inserted after; the zero ID means
	// the start of the document. OpInsert only.
	Origin ID
	// Char is the inserted character. OpInsert only.
	Char rune
	// Target is the character to tombstone. OpDelete only.
	Target ID
	// Span is how many consecutive sequence numbers this operation accounts for,
	// ending at ID.Seq. OpSuperseded only, where it is at least one and never
	// reaches below sequence number one.
	Span uint64
}

An Op is one indivisible change to a document. It is the only thing replicas exchange, it is self-describing, and applying it is idempotent, so a transport may duplicate or reorder operations freely.

Which fields carry meaning depends on Kind: Origin and Char belong to OpInsert, Target to OpDelete. The unused fields must be zero, and are checked, so a garbled operation is rejected rather than silently reinterpreted.

func ParseOps 

func ParseOps(data []byte) ([]Op, error)

ParseOps decodes a batch written by AppendOps.

func ParseOpsLimit added in v0.50.0 

func ParseOpsLimit(data []byte, max int) ([]Op, error)

ParseOpsLimit is ParseOps with a ceiling on how many operations the message may claim: zero is unlimited, and any other value refuses a larger claim with ErrTooManyOps before reserving for it. See ErrTooManyOps for why the number is the caller's.

func (Op) MarshalBinary 

func (o Op) MarshalBinary() ([]byte, error)

MarshalBinary encodes the operation. It reports ErrInvalidOp rather than producing bytes that would be rejected on arrival.

func (*Op) UnmarshalBinary 

func (o *Op) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes an operation written by MarshalBinary. Trailing bytes are an error: an operation is decoded from exactly its own encoding.

type OpKind 

type OpKind uint8

OpKind distinguishes the operations a text CRDT carries. 

const (
	// OpInsert adds one character after an existing one.
	OpInsert OpKind = 1
	// OpDelete tombstones an existing character.
	OpDelete OpKind = 2
	// OpSuperseded stands in for operations the sending replica no longer holds.
	// It names no character and does nothing: it exists so that a peer catching
	// up can account for the sequence numbers and move on, exactly as
	// [MapSuperseded] does for a map.
	//
	// It covers a run of consecutive sequence numbers rather than one, ending at
	// its own ID.Seq and reaching back Span of them.
	//
	// It may only stand in for operations nothing else names. A deletion is
	// named by nothing, so a losing one — the case this exists for, where two
	// replicas deleted the same character and only one of them is the
	// character's recorded deletion — can go. An insertion is named by whatever
	// was inserted after it, so it cannot: a peer sent a run over an insertion
	// would park everything that followed, waiting for an origin it will never
	// be given.
	//
	// Nothing here produces one yet. This release understands one, so that a
	// later release may send one to a peer that has been upgraded in between —
	// the two ends of a session are not deployed at the same moment, and a kind
	// a peer does not know is a kind it refuses. See go-crdt/crdt#80.
	OpSuperseded OpKind = 3
)

func (OpKind) String 

func (k OpKind) String() string

String renders the kind for diagnostics.

type Part added in v0.11.0 

type Part struct {
	Kind PartKind
	Name string
}

A Part names one structure inside a Composite.

The kind is part of the name, not a property of it. Two replicas that have never spoken may each reach for "notes", one as a list and one as a map, and there is no operation to exchange that would tell them so — a part exists because operations for it exist, and those operations were addressed to different things. Identifying a part by name alone would make that pair a conflict needing a tie-break, and whichever way the tie-break fell one replica would find its writes gone. Identifying it by both makes it two parts, which is a convergent answer needing no arbitration and no rule anybody has to know.

A name is arbitrary UTF-8 and is expected to carry structure — "file:src/main.tex", "comment:9f3c…", "chat". It must be valid UTF-8 because a name crosses into JavaScript, where a string is UTF-16 and bytes that are not text cannot survive the trip; it is the same rule Map holds its keys to, for the same reason. It must not be empty, which is a decision rather than an oversight: the name is the only thing telling one part from another, and "" is what a caller passes when the name it meant to compute never got computed. Two unrelated bugs would then share one part, silently, and nothing downstream could notice.

type PartChange added in v0.13.0 

type PartChange struct {
	// Part names the part that changed.
	Part Part
	// Text is the edits to make, in order. PartText only.
	Text []Change
	// Keys names the keys that changed, ascending. PartMap only.
	Keys []string
}

A PartChange is what one part did when a batch was applied. A part that did nothing is not reported at all, so a PartChange existing is itself the news that its part is not what it was — which for a list is the whole of the news.

Which field carries it depends on the kind, and the three differ because what a view has to do with them differs:

  • PartText fills Text with the edits a view of the text has to make, in the order it has to make them. A text editor cannot re-read a document per keystroke and keep a cursor, so it needs the edits themselves.
  • PartMap fills Keys with the keys whose value or presence changed, ascending. A view reads back the keys it is told about.
  • PartList fills neither. A list here holds tens or hundreds of values and the views written against one read it back whole; naming positions would be a second protocol to keep correct for nobody. It can be added later without breaking a caller, which is why it is a field left empty rather than a kind left out.

type PartKind added in v0.11.0 

type PartKind uint8

PartKind names which of the three replicated structures a part is. 

const (
	// PartText is a [Doc], a replicated sequence of characters.
	PartText PartKind = 1
	// PartList is a [List], a replicated sequence of values.
	PartList PartKind = 2
	// PartMap is a [Map], a replicated key-value map.
	PartMap PartKind = 3
)

func (PartKind) String added in v0.11.0 

func (k PartKind) String() string

String renders the kind for diagnostics.

type PartOps added in v0.11.0 

type PartOps struct {
	// Part names what the operations are addressed to.
	Part Part
	// Text carries the operations of a PartText batch.
	Text []Op
	// List carries the operations of a PartList batch.
	List []ListOp
	// Map carries the operations of a PartMap batch.
	Map []MapOp
}

PartOps is a batch of operations addressed to one part. Operations travel grouped rather than one by one because a composite has many parts and few operations each: naming the part once per batch keeps a document of three hundred comment parts from paying its part names three hundred times, and it keeps a batch's operations the one kind its part can hold.

Exactly the field matching the part's kind may be set, and the other two are checked to be empty, so a batch built with the wrong field is refused rather than silently read as an empty one.

func ParsePartOps added in v0.12.0 

func ParsePartOps(data []byte) ([]PartOps, error)

ParsePartOps decodes batches written by AppendPartOps.

There is deliberately no MarshalBinary on PartOps to go with the ones Op, ListOp and MapOp carry. Those three are operations: indivisible, the unit a replica exchanges, and a caller may reasonably want one on its own in a field. A PartOps is not an operation but the envelope addressing a batch of them to a part, and the unit that crosses a wire is the whole set of them — which is what Composite.OpsSince returns and what Composite.Apply takes. Encoding one alone would advertise a message neither end of this package ever produces or consumes, and it would be a fourth format to keep canonical, fuzzed and held to its coverage for no caller. A caller that really has one batch writes AppendPartOps(nil, batches[:1]).

func ParsePartOpsLimit added in v0.50.0 

func ParsePartOpsLimit(data []byte, max int) ([]PartOps, error)

ParsePartOpsLimit is ParsePartOps with a ceiling on how many operations the whole message may claim: zero is unlimited, and any other value refuses a larger claim with ErrTooManyOps before reserving for it.

The ceiling is for the MESSAGE and not for each batch, because a message is what arrives and what a reservation is paid for. A thousand batches of a thousand operations costs the same as one of a million, and a per-batch bound would refuse the second while waving the first through.

See ErrTooManyOps for why the number is the caller's rather than this package's.

type SiteID 

type SiteID uint64

SiteID identifies a replica. It is chosen by the caller and must be distinct for every replica that concurrently edits a document; two replicas sharing a SiteID can mint the same ID for different characters, which breaks convergence.

The package never generates one itself: a random or clock-derived identifier is unavailable, or not reproducible, under js/wasm. See DeriveSiteID.

func DeriveSiteID 

func DeriveSiteID(b []byte) SiteID

DeriveSiteID hashes b into a SiteID with FNV-1a. It gives callers a deterministic way to turn an identifier they already hold — a session token, a user ID, a tab identifier — into a replica identity, on any platform, including js/wasm where the usual sources of randomness are absent.

Distinctness is the caller's responsibility: distinct b almost always yields distinct SiteIDs, but a hash cannot promise it.

Across instances that have never spoken

That responsibility has a sharp edge the moment more than one instance is involved. A site identity has to be unique across every replica that will ever meet, not merely across the ones one server hands out — two operations claiming one identity is the thing this package rests on not happening, and no merge can recover from it.

So b must carry the instance. Derive from something SCOPED — an eduPersonPrincipalName, a subject-id, an OIDC issuer and subject together, a URL — and never from a bare local identifier: two instances that each have a user "42" would derive the same site from it, on purpose, because a hash is a function and that is what a function does. There is a test of both.

Measured on scoped identifiers of the shape a SAML assertion carries: twenty million of them over four thousand scopes, no collisions, which is what a uniform 64-bit hash gives at that size. See federation_test.go.

Example

Site identities have to be distinct and cannot be drawn at random under js/wasm, so they are derived from something the caller already holds. 

package main

import (
	"fmt"

	"github.com/go-crdt/crdt"
)

func main() {
	first := crdt.DeriveSiteID([]byte("session-8f2c"))
	second := crdt.DeriveSiteID([]byte("session-8f2c"))
	fmt.Println(first == second, first == crdt.DeriveSiteID([]byte("session-91ab")))
}

Output:
true false

type VersionVector 

type VersionVector map[SiteID]uint64

A VersionVector records, per site, the highest sequence number a replica has applied. Because a site's sequence numbers have no gaps and Doc refuses to apply an operation until its predecessor has landed, the vector describes a replica's state exactly: it holds operation Seq from Site if and only if Seq <= v[Site].

The nil vector is valid and reads as "nothing applied".

func (VersionVector) Clone 

func (v VersionVector) Clone() VersionVector

Clone returns an independent copy. The clone of a nil vector is empty but non-nil, so it can be written to.

func (VersionVector) Equal 

func (v VersionVector) Equal(other VersionVector) bool

Equal reports whether v and other describe the same set of operations. Sites recorded with a zero sequence number count as absent, so a nil vector equals an empty one.

func (VersionVector) Get 

func (v VersionVector) Get(site SiteID) uint64

Get returns the highest sequence number applied for site, or zero.

func (VersionVector) Includes 

func (v VersionVector) Includes(id ID) bool

Includes reports whether the operation named by id has been applied.

func (VersionVector) MarshalBinary added in v0.1.1 

func (v VersionVector) MarshalBinary() ([]byte, error)

MarshalBinary encodes the vector. Entries are written in ascending site order, so the same state always produces the same bytes and a caller may compare or cache them.

A replica sends this to be told what it has missed; see Doc.OpsSince.

func (*VersionVector) UnmarshalBinary added in v0.1.1 

func (v *VersionVector) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes a vector written by MarshalBinary. A site listed twice, a sequence number of zero, and trailing bytes are all rejected: each would leave what the vector means dependent on decoding order.

Source Files

View all Source files

Directories

Path Synopsis
Package awareness tracks who else has a document open and where their cursor is — the coloured carets and name labels a collaborative editor shows.
 Package awareness tracks who else has a document open and where their cursor is — the coloured carets and name labels a collaborative editor shows.
Package structured turns the replicated primitives of the crdt package into a shared substrate for co-editing structured documents.
 Package structured turns the replicated primitives of the crdt package into a shared substrate for co-editing structured documents.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.