structured

package
v0.34.0 Latest Latest
Warning

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

 Go to latest Published: Aug 27, 2026 License: BSD-3-Clause Imports: 11 Imported by: 0

Documentation

Overview

Package structured turns the replicated primitives of the crdt package into a shared substrate for co-editing structured documents. One core expresses both a spreadsheet and an isometric diagram — and any other structured document — rather than each growing a merge engine of its own.

One core, many document types

Nothing here re-implements a CRDT. The merge logic lives entirely in the crdt package, and this layer only composes three of its structures:

  • crdt.List is an RGA: an ordered sequence whose every element carries a stable identity that survives concurrent insertion and deletion elsewhere. With its order ignored it is a reload-safe source of stable identities and an existence set, which is what a diagram's nodes and connectors are. It is not what an axis of a spreadsheet is, because an RGA has no operation for moving something already in it; see Sequence.
  • crdt.Map is a last-writer-wins key-value map. Each key is, on its own, an LWW-register: a single value merged by a (Lamport clock, site) total order with no tie left to chance and no wall clock read. Register names that degenerate case, and RecordMap composes many such registers into records whose fields merge independently.
  • crdt.Composite holds those parts under one name, one snapshot and one version, so a whole document is one thing to persist and to authorise.

Two things a map and a list do not express are built here rather than added to the crdt package, because neither needs a new merge rule — only a way of using the ones that exist:

  • Counter is a number several replicas add to at once. A register cannot be one, because "add one" is not a value and writing a value cannot say it. Keying the map by site, so that a replica writes only its own total, makes concurrent additions concurrent writes to different keys.
  • Tree is a tree whose nodes move. A parent is a single value and merges on its own; what does not is the shape two legal moves make between them, which is a ring. Tree resolves that when the tree is read, by rules that are a function of the state alone.
  • RichText is text that carries formatting. Written into the sequence — a bold-on character, a bold-off character — two replicas bolding overlapping stretches produce interleaved markers and read differently; written per character it converges and costs a write per letter. A mark is one operation naming two boundaries instead, and the formatting is worked out when the text is read.
  • Undo puts back what this replica did, and only that. It is not a stack of states — restoring one would throw away what everybody else has done since, and travel to them as an instruction to do the same. An undo here is a new edit, made now, that has the effect of the old one not having happened, and it reaches a peer as an ordinary edit.
  • Ink is what is drawn by hand. A stroke is a path that arrives a point at a time, so held as one value every point sent rewrites the whole path and the person watching sees the line redrawn rather than extended. The points are a sequence of their own here, appended to, each saying which stroke it belongs to — one stream rather than one per stroke, because a part cannot be taken out of a composite and a whiteboard would otherwise spend more on saying what it has than on what was drawn.
  • Blobs holds the files a document refers to but is not made of. A file as one map value is one operation the size of the file: it cannot be sent as it is read, resumed if the connection drops, or recognised as one a peer already has. Cut into chunks stored under the hash of their own bytes, it is as many operations as it has chunks, and the same chunk written by two replicas is the same key and the same value — so there is nothing to merge and nothing is stored twice.
  • Proposals are changes to a document that are not part of it yet: a suggested edit, a change put up for review. Held as a second copy of the document and reconciled later, accepting one means applying a difference between two texts, and applying a difference mints new characters — so every comment, mark and cursor anchored to the characters it replaced would be left pointing at nothing. A proposal is a replica that has not synced instead: its operations are the document's own, against the document's own identities, written down where reviewers can read them. Accepting is applying them, which merges with whatever happened meanwhile because that is what a replica coming back from offline does; turning one down costs nothing, because they were never applied.
  • Set is a collection of names replicas add to and take from at once — the labels on a card, the people in a conversation, the layers that are showing. A map keyed by the name converges on the case that happens badly: one replica adds a label while another, which has never seen it, takes it away, and one of the two writes wins by an order that has nothing to do with what either knew. Every addition mints a tag of its own instead, and a removal takes away the tags it can see — so an addition nobody had seen is untouched by it, not as a policy but for want of anything to base one on.
  • MultiRegister is a value two replicas are allowed to disagree about. A Register settles every concurrent write by the (clock, site) order, which is right when the losing write is of no interest and wrong when it is: two people rename the same thing at once and one of the names is gone, with nothing anywhere recording that there was a second. This keeps a version vector beside each replica's own value, so a value written without seeing another is not superseded by it and both are read. Choosing between them is writing the one chosen — a write dominates everything its writer could see — so there is no operation for settling and none is needed.
  • Blocks is a document made of blocks — paragraphs, headings, list items, quotes, code — each holding formatted text and nested to a depth. Written as a rich text per block it converges and does not scale: a part cannot be taken out of a composite and a version carries one entry per part, so a thousand blocks is a thousand entries exchanged on every sync whether the document still holds them or not. The blocks are markers in one text instead, keyed to one map, which is three parts however many blocks there are. The marker is a character rather than a boundary between two, because "the end of this paragraph" and "the start of the next" are the same offset and are not the same place — a character has two sides and a boundary has one.
  • Sequence is an ordered collection whose items move. crdt.List is an RGA and has no operation for moving something already in it; written as a delete and an insert, a move is two operations that a concurrent move splits, leaving the item in both places or in neither. An item carries where it sits as a rank instead, so a move is one field write. It is what the rows and columns of a Sheet are, which is what makes a row something a person can drag.

Sheet and Diagram are thin wrappers over the same crdt.Composite. That they share it is the point: the convergence, commutativity, idempotence and associativity the crdt package proves for its parts are inherited by every document type built here, because there is only ever one set of parts doing the merging.

Determinism

Like the crdt package, this one never reads the wall clock and never draws a random number, so a document compiled to js/wasm behaves exactly as it does on a server. Replica identity is the caller's crdt.SiteID; stable element identities are minted by the RGA, which is why they are reload-safe and never reused, even across a deletion.

What is replicated and what is not

The raw content of a cell — a literal or a formula's source text together with the stable identities it references — is replicated. A formula's computed value is not: it is derived locally from content every replica already agrees on, so replicating it would be replicating a function of the state rather than the state. This package is the data layer; it holds no formula engine and no widget.

Index

Examples

Constants

View Source 
const BlockMark = '\uFFFF'

BlockMark is the character a block begins at. It is U+FFFF, a Unicode noncharacter: permanently reserved and never legal in interchange, so it is not something a person types.

It is exported so that anything reading the text part directly — an anchor, a cursor, an authorship pass — can tell a marker from a character somebody wrote, rather than having to know the number.

View Source 
const DefaultChunkSize = 64 << 10

DefaultChunkSize is what Blobs.Put cuts at. Sixty-four kilobytes makes a two-megabyte figure thirty-two operations rather than one, which is small enough to send between two keystrokes and large enough that the hash beside each is a rounding error against it.

View Source 
const SelectionMetaKey = "sel"

SelectionMetaKey is the metadata key a structured selection travels under.

Variables

View Source 
var DocStart = BlockID{}

DocStart is the place before the first block: passing it to Blocks.Insert puts a block at the top of the document.

View Source 
var ErrInvalidID = errors.New("structured: invalid entity id")

ErrInvalidID reports an entity identity that cannot key a record: the empty string, or bytes that are not valid UTF-8. An id crosses into JavaScript, where a string is UTF-16, so it is held to the same rule a crdt.Map key is.

View Source 
var ErrNoChange = errors.New("structured: the operation would change nothing")

ErrNoChange is returned by an operation that would change nothing, so that a caller never has to decide whether a zero-valued operation is safe to send.

View Source 
var ErrReservedRune = errors.New("structured: text contains the block marker")

ErrReservedRune reports text offered to a Blocks that contains BlockMark. The marker is what tells one block from the next, so a caller that could write one could write a block boundary into the middle of a word, and no reader could tell that apart from a block somebody meant.

View Source 
var ErrUnknownConn = errors.New("structured: unknown connector")

ErrUnknownConn reports an operation naming a connector this replica does not hold as present.

View Source 
var ErrUnknownEntity = errors.New("structured: unknown entity")

ErrUnknownEntity reports an operation naming an entity this replica does not hold as present — one never added, or already removed.

View Source 
var ErrUnknownFamily = errors.New("structured: unknown family")

ErrUnknownFamily reports an operation naming a family a Document does not hold. The five valid families are the constants above.

View Source 
var ErrUnknownNode = errors.New("structured: unknown node")

ErrUnknownNode reports an operation naming a node this replica does not hold as present — one never added, or already removed.

View Source 
var SeqStart = ItemID{}

SeqStart is the place before the first item: passing it to Sequence.Insert or Sequence.Move puts an item at the front.

View Source 
var TreeRoot = TreeID{}

TreeRoot is the parent of a node at the top of the tree. It is not a node and has no fields; it is the name of the place a top-level node hangs from.

Functions

func CellSelectionOf 

func CellSelectionOf(p awareness.Peer) (RowID, ColID, bool)

CellSelectionOf returns the cell a peer has selected, and whether it has a valid one. A peer publishing a selection this package did not encode — or none — reports not ok.

func DecodeBool 

func DecodeBool(data []byte) (bool, bool)

DecodeBool reverses EncodeBool, reporting failure for anything but a single 0 or 1 byte — a peer may send other bytes, and a boolean has exactly two values.

func DecodeInt 

func DecodeInt(data []byte) (int32, bool)

DecodeInt reverses EncodeInt, reporting failure for bytes it did not produce: an empty slice, a truncated or trailing varint, or a value outside int32, since a peer's operation carries the bytes and a wider value would store differently on a 32-bit replica.

func EncodeBool 

func EncodeBool(v bool) []byte

EncodeBool renders a boolean as a single byte, 0 or 1.

func EncodeInt 

func EncodeInt(v int32) []byte

EncodeInt renders a signed integer as one varint, so that every replica, on any architecture, stores and compares an integer field identically. It is int32 for the same reason a Diagram's position is: a 32-bit target — js/wasm — and a 64-bit one must agree byte for byte.

func PublishCellSelection 

func PublishCellSelection(reg *awareness.Registry, site crdt.SiteID, row RowID, col ColID, meta map[string]string) awareness.Update

PublishCellSelection records that this replica has the cell (row, col) selected and returns the awareness update to broadcast. meta carries any presentation details — a display name, a colour — alongside the selection.

func PublishNodeSelection 

func PublishNodeSelection(reg *awareness.Registry, site crdt.SiteID, node NodeID, meta map[string]string) awareness.Update

PublishNodeSelection records that this replica has node selected and returns the awareness update to broadcast.

Types

type Blobs added in v0.24.0 

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

Blobs holds the files a document refers to but is not made of: the figures of a paper, an image pasted into a page, a font, a recorded clip.

Why a map value is not one

A file could be one value in a crdt.Map, and for a small one that is the right answer. For a two-megabyte figure it is not, because the operation that writes it is two megabytes: it cannot be sent as it is read, it cannot be resumed if the connection drops halfway, a peer that already has the same figure under another name receives it again, and changing one corner of the image sends the whole thing a second time.

How this one works

A file is cut into chunks, and each chunk is stored under the hash of its own bytes. What a name refers to is a manifest: the length of the file and the hashes of its chunks, in order.

Every property this type has follows from that one decision:

  • A file is as many operations as it has chunks, so it is sent as it is read and a peer that stops halfway has a prefix rather than nothing.
  • Two replicas storing the same chunk write the same key and the same bytes, so there is no conflict to resolve, ever. The same figure under two names, in two documents, or added twice by two people is stored once.
  • Changing part of a file rewrites only the chunks that changed, if the chunker cuts on the content rather than on a count; see Chunker.
  • A chunk arrives verified or not at all. The key says what the bytes must hash to, so a peer cannot quietly put something else there.

What a name points at is one value, so two replicas replacing the same file at once is a conflict crdt.Map settles: one of the two whole files wins, which is what replacing a file means. Neither replica ends up with a mixture.

func BlobsOf added in v0.24.0 

func BlobsOf(doc *crdt.Composite) *Blobs

BlobsOf reads a composite as a blob store, for a document that holds one among other parts — the usual case, since the files belong to the document that refers to them.

func LoadBlobs added in v0.24.0 

func LoadBlobs(site crdt.SiteID, snapshot []byte) (*Blobs, error)

LoadBlobs rebuilds a store from a snapshot, to be written as site.

func NewBlobs added in v0.24.0 

func NewBlobs(site crdt.SiteID) *Blobs

NewBlobs returns an empty store this site can write to.

func (*Blobs) Apply added in v0.24.0 

func (b *Blobs) Apply(batches ...crdt.PartOps) error

Apply integrates operations from peers.

func (*Blobs) Composite added in v0.24.0 

func (b *Blobs) Composite() *crdt.Composite

Composite returns the document underneath, which is what is snapshotted and what operations are applied to.

func (*Blobs) Get added in v0.24.0 

func (b *Blobs) Get(name string) ([]byte, bool)

Get returns the file stored under name.

It returns false while any of the file's chunks has not arrived, rather than a hole where one should be: half a figure is not a figure. Use Blobs.Missing to tell "not here" from "not here yet".

A chunk whose bytes do not hash to the key they are under is treated as not having arrived. A peer can write anything into the map; it cannot make this hand back bytes nobody asked for.

func (*Blobs) Missing added in v0.24.0 

func (b *Blobs) Missing(name string) int

Missing returns how many of a file's chunks have not arrived, or have arrived as something other than what their key says they must be.

func (*Blobs) Names added in v0.24.0 

func (b *Blobs) Names() []string

Names returns the files stored, in order.

func (*Blobs) OpsSince added in v0.24.0 

func (b *Blobs) OpsSince(v crdt.CompositeVersion) ([]crdt.PartOps, error)

OpsSince returns the operations a peer at v has not seen.

func (*Blobs) Pending added in v0.24.0 

func (b *Blobs) Pending() int

Pending reports how many received operations are still waiting.

func (*Blobs) Put added in v0.24.0 

func (b *Blobs) Put(name string, data []byte) ([]crdt.PartOps, error)

Put stores data under name, cut at DefaultChunkSize.

func (*Blobs) PutWith added in v0.24.0 

func (b *Blobs) PutWith(name string, data []byte, cut Chunker) ([]crdt.PartOps, error)

PutWith stores data under name, cut by the given chunker.

The batches come back in the order they should be sent: every chunk, and the manifest last. A peer that receives a prefix of them holds chunks it cannot yet assemble, which is what makes the transfer resumable — nothing refers to them until the manifest arrives, and Blobs.Missing says what is still to come.

A chunk already stored is not written again, so putting a file twice costs one operation and putting a file that shares chunks with one already there costs only what is new.

func (*Blobs) Remove added in v0.24.0 

func (b *Blobs) Remove(name string) (crdt.PartOps, error)

Remove takes a name away. The chunks stay, because another name may share them; see Blobs.Sweep.

func (*Blobs) Site added in v0.24.0 

func (b *Blobs) Site() crdt.SiteID

Site returns the replica this store writes as.

func (*Blobs) Size added in v0.24.0 

func (b *Blobs) Size(name string) (int, bool)

Size returns how long the file under name is, and whether there is one. It answers before the chunks have arrived, because the manifest carries the length — which is what lets a caller show a figure's dimensions, or a progress bar, while it is still coming.

func (*Blobs) Snapshot added in v0.24.0 

func (b *Blobs) Snapshot() []byte

Snapshot encodes the whole store.

func (*Blobs) Stored added in v0.24.0 

func (b *Blobs) Stored() int

Stored returns how many distinct chunks are held, which is what the store costs rather than the sum of the sizes of the files in it.

func (*Blobs) Sweep added in v0.24.0 

func (b *Blobs) Sweep() ([]crdt.PartOps, error)

Sweep removes every chunk no name refers to.

It is not safe to run while a peer may be storing something. A peer that has just put a file whose chunks this replica also had would have written no chunk operations for them — they were already here — and sweeping them leaves that peer's manifest naming chunks nobody holds. What that costs is bounded and visible: Blobs.Missing reports it, and putting the file again restores exactly the chunks that went. It is not corruption, but it is work, so sweep when a document is quiet rather than as a matter of course.

func (*Blobs) Version added in v0.24.0 

func (b *Blobs) Version() crdt.CompositeVersion

Version returns what this replica holds.

type Block added in v0.27.0 

type Block struct {
	// ID names the block.
	ID BlockID
	// Type is what the block is — "paragraph", "heading", "quote", whatever
	// the caller uses. It is free text rather than an enumeration, because
	// this package holds no renderer and has no business deciding what a
	// document can contain. The empty string is a block nobody has typed.
	Type string
	// Depth is how deeply the block is nested; zero is the top level.
	Depth int
	// Text is the block's characters, without the marker and without the
	// formatting. See [Blocks.Spans] for the formatting.
	Text string
}

A Block is one block as it reads now.

type BlockID added in v0.27.0 

type BlockID crdt.ID

A BlockID names a block for as long as the block exists, whatever concurrent edits do to the blocks around it. It is the identity of the marker character the block begins at, minted by the RGA, so it is unique across replicas, reload-safe, and never reused.

func (BlockID) IsStart added in v0.27.0 

func (b BlockID) IsStart() bool

IsStart reports whether b names the place before the first block rather than a block.

func (BlockID) String added in v0.27.0 

func (b BlockID) String() string

String renders the identity in the "seq@site" notation the crdt package uses.

type Blocks added in v0.27.0 

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

A Blocks is a document made of blocks: paragraphs, headings, list items, quotes, code, each holding text that carries formatting, each nested to a depth. It is what a page in a notebook, an outline, a wiki article and the body of a message all are.

Why not one rich text per block

The obvious shape is a RichText per block, held in a crdt.Composite under a part apiece. It converges, and it does not scale, for a reason that has nothing to do with merging: a part cannot be taken out of a composite, and a version carries one entry per part. A thousand-block document is then a thousand parts whose version is exchanged on every sync, and the version of an empty document that once had a thousand blocks is the same size as the version of a full one. Measured, in this package's own tests: a thousand blocks written a part apiece is 18894 bytes of version vector, and written this way it is 35. It is the same argument Ink settles the same way — one stream of points rather than one part per stroke.

How this one works

There is one text, holding every block's characters in reading order, and one map holding what each block is. A block begins at a marker character in the text, and the map records that marker's type, its depth and whatever else the caller puts on it, keyed by the marker's own identity. So a document of any number of blocks is three parts: the text, the marks over it, and the blocks.

The marker is a real character rather than a boundary between two of them, and that is the whole reason this works. Two people can edit the same seam at the same moment and mean different things: one is finishing a paragraph, the other is starting the next. Both are the same offset. A boundary stored as "before the first character of this block" makes the first intention expressible and the second impossible; stored as "after the last character of the one before", the other way round. Neither can be both, because there is only one place in the sequence to insert at. A marker gives the seam two sides: text typed before it is the end of one block and text typed after it is the start of the next, and the sequence already knows how to keep two concurrent insertions at two different places apart. Nothing has to be arbitrated and nothing is lost.

The marker is U+FFFF, a Unicode noncharacter — permanently reserved, never legal in interchange, so no text a person can type contains one. Text offered to this type is refused if it does one anyway (ErrReservedRune), and a marker that arrives from a peer with no record against it reads as an untyped block rather than as an error, because what a document reads as has to be a function of the state it is in.

Why nesting is a depth and not a parent

A Tree is what nesting normally wants, and it is not what this wants. The order of the blocks is already decided, by the text, and a parent pointer is a second statement about the same arrangement — one that can contradict the first, so that a block reads before the block it hangs under. There is no answer to that contradiction which is not an arbitration.

A depth cannot contradict anything. Every sequence of depths is a document somebody can read: a jump of two is a list that starts two levels in, which is what a person who indents twice meant. Two replicas indenting the same block at the same moment are two writes to one field, which crdt.Map settles the same way on both, and the loser can indent again.

Example

A Blocks is a document made of blocks — headings, paragraphs, list items — however many of them, in three parts. Here two replicas edit the same seam at the same moment: one is finishing a paragraph and the other is starting the next, which are the same offset and are not the same place. Both edits land where they were meant, with nothing arbitrated. 

package main

import (
	"fmt"

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

func main() {
	ada, grace := structured.NewBlocks(1), structured.NewBlocks(2)

	// Ada writes a heading and a paragraph, and shares them.
	title, first, _ := ada.Insert(structured.DocStart, "heading")
	second, _ := ada.InsertText(title, 0, "Rivers")
	body, third, _ := ada.Insert(title, "paragraph")
	fourth, _ := ada.InsertText(body, 0, "They run downhill")
	grace.Apply(append(append(first, second), append(third, fourth)...)...)

	// Offline: Ada finishes the heading, Grace starts the paragraph.
	fromAda, _ := ada.InsertText(title, 6, " and seas")
	fromGrace, _ := grace.InsertText(body, 0, "Mostly, ")

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

	for _, block := range grace.List() {
		fmt.Printf("%s: %s\n", block.Type, block.Text)
	}
	fmt.Println(len(grace.Version()), "parts")
}

Output:
heading: Rivers and seas
paragraph: Mostly, They run downhill
2 parts

func BlocksOf added in v0.27.0 

func BlocksOf(doc *crdt.Composite) *Blocks

BlocksOf reads a composite as a block document, for a document that holds these parts among others.

func LoadBlocks added in v0.27.0 

func LoadBlocks(site crdt.SiteID, snapshot []byte) (*Blocks, error)

LoadBlocks rebuilds a document from a snapshot, to be edited as site.

func NewBlocks added in v0.27.0 

func NewBlocks(site crdt.SiteID) *Blocks

NewBlocks returns an empty document this site can edit.

func (*Blocks) Apply added in v0.27.0 

func (b *Blocks) Apply(batches ...crdt.PartOps) error

Apply takes operations from a peer.

func (*Blocks) At added in v0.27.0 

func (b *Blocks) At(id BlockID, offset int) (int, error)

At returns where a place inside a block sits in the underlying text, which is what Blocks.RichText and crdt.Doc.Anchor are in terms of.

offset may equal the block's length, which is the place after its last character.

func (*Blocks) Block added in v0.27.0 

func (b *Blocks) Block(id BlockID) (Block, bool)

Block returns one block as it reads now.

func (*Blocks) Children added in v0.27.0 

func (b *Blocks) Children(parent BlockID) []BlockID

Children returns the blocks that hang directly under one block, in reading order. DocStart returns the blocks at the top level.

func (*Blocks) Composite added in v0.27.0 

func (b *Blocks) Composite() *crdt.Composite

Composite returns the document underneath, which is what is snapshotted and what operations are applied to.

func (*Blocks) DeleteText added in v0.27.0 

func (b *Blocks) DeleteText(id BlockID, offset, count int) (crdt.PartOps, error)

DeleteText takes count characters out of a block at offset.

It cannot reach past the end of the block, so a deletion can never take a marker out by accident and turn two blocks into one; that is Blocks.Merge, which is a different thing to ask for.

func (*Blocks) Field added in v0.27.0 

func (b *Blocks) Field(id BlockID, field string) ([]byte, bool)

Field reads one of the caller's own fields.

func (*Blocks) IDs added in v0.27.0 

func (b *Blocks) IDs() []BlockID

IDs returns the identity of every block, in reading order. It is what Blocks.List returns without reading any text, for a caller that only wants to know what is there.

func (*Blocks) Insert added in v0.27.0 

func (b *Blocks) Insert(after BlockID, typ string) (BlockID, []crdt.PartOps, error)

Insert puts a new empty block of type typ after the block named by after, or at the top of the document for DocStart. The new block is nested as deeply as the one it follows, which is what pressing return at the end of a list item means.

func (*Blocks) InsertText added in v0.27.0 

func (b *Blocks) InsertText(id BlockID, offset int, s string) (crdt.PartOps, error)

InsertText puts s into a block at offset, which may equal the block's length.

func (*Blocks) Len added in v0.27.0 

func (b *Blocks) Len() int

Len returns how many blocks there are. It is the document's length in blocks; its length in characters is RichText.Len of Blocks.RichText, which counts the markers too.

func (*Blocks) List added in v0.27.0 

func (b *Blocks) List() []Block

List returns every block, in reading order.

func (*Blocks) Mark added in v0.27.0 

func (b *Blocks) Mark(from BlockID, fromOff int, to BlockID, toOff int, name string, value []byte, expand Expand) (crdt.PartOps, error)

Mark puts a mark on the text from one place in the document to another, carrying value, which may be nil for a mark that is only on or off.

A mark may span blocks — a comment on two paragraphs, a sentence someone started emphasising and finished in the next one — because the text it runs over is one text. expand says whether text typed at either edge joins it; see Expand.

func (*Blocks) MarksAt added in v0.27.0 

func (b *Blocks) MarksAt(id BlockID, offset int) map[string][]byte

MarksAt returns the formatting of one character of a block.

func (*Blocks) Merge added in v0.27.0 

func (b *Blocks) Merge(id BlockID) ([]crdt.PartOps, error)

Merge takes the boundary between a block and the one before it away, so that its text joins the block above. It is what pressing backspace at the start of a block does.

The first block of a document has nothing above it to join, and merging it is an error rather than a silent no-op: a caller that asks has miscounted.

func (*Blocks) OpsSince added in v0.27.0 

func (b *Blocks) OpsSince(v crdt.CompositeVersion) ([]crdt.PartOps, error)

OpsSince returns the operations a peer at v has not seen.

func (*Blocks) Outline added in v0.27.0 

func (b *Blocks) Outline() []Outlined

Outline returns the blocks with their nesting made explicit: each block paired with the block it hangs under, which is the nearest one before it at a smaller depth.

It is derived, not stored — see the type's own documentation for why nesting is a depth — so two replicas holding the same document read the same outline. A block at the top level has DocStart as its parent.

func (*Blocks) Pending added in v0.27.0 

func (b *Blocks) Pending() int

Pending reports how many operations are held back waiting for ones they depend on.

func (*Blocks) Plain added in v0.27.0 

func (b *Blocks) Plain(sep string) string

Plain returns the whole document as text, with the markers taken out and the blocks separated by sep — "\n" for something a person reads.

It is a rendering, not the state: the state is the blocks.

func (*Blocks) Preamble added in v0.31.0 

func (b *Blocks) Preamble() string

Preamble returns the characters before the first block, which is nothing in any document this package wrote.

A block begins at a marker, so a document written through this type begins with one and there is nothing in front of it. Another writer — a peer running a different version, or a caller reaching past this type to the text part — can put characters there, and they belong to no block. They are returned here rather than dropped: text that is in the document but reachable through no method is worse than text somebody has to decide what to do with.

func (*Blocks) Records added in v0.27.0 

func (b *Blocks) Records() *RecordMap

Records returns the record map the blocks live in, for reading a block's own fields.

func (*Blocks) Remove added in v0.27.0 

func (b *Blocks) Remove(id BlockID) ([]crdt.PartOps, error)

Remove takes a block and everything in it out of the document.

func (*Blocks) RichText added in v0.27.0 

func (b *Blocks) RichText() *RichText

RichText returns the text and its formatting as one rich text, for anything this type does not wrap. Its offsets are over the whole document, markers included; see Blocks.At to convert one.

func (*Blocks) SetDepth added in v0.27.0 

func (b *Blocks) SetDepth(id BlockID, depth int) (crdt.PartOps, error)

SetDepth says how deeply a block is nested. Zero is the top level.

func (*Blocks) SetField added in v0.27.0 

func (b *Blocks) SetField(id BlockID, field string, value []byte) (crdt.PartOps, error)

SetField puts one of the caller's own fields on a block: the level of a heading, the language of a code block, whether a task is done.

A field name may be anything valid UTF-8 that does not start with a NUL, which is what this type keeps its own two under.

func (*Blocks) SetType added in v0.27.0 

func (b *Blocks) SetType(id BlockID, typ string) (crdt.PartOps, error)

SetType says what a block is. The empty string takes the type off.

func (*Blocks) Site added in v0.27.0 

func (b *Blocks) Site() crdt.SiteID

Site returns the replica this document edits as.

func (*Blocks) Snapshot added in v0.27.0 

func (b *Blocks) Snapshot() []byte

Snapshot returns the document as bytes.

func (*Blocks) Spans added in v0.27.0 

func (b *Blocks) Spans(id BlockID) []Span

Spans returns one block's text broken into stretches over which the formatting does not change, in order, covering every character of it exactly once. Offsets are within the block.

A block with no characters has no spans, which is the same answer RichText.Spans gives an empty text.

func (*Blocks) Split added in v0.27.0 

func (b *Blocks) Split(id BlockID, offset int, typ string) (BlockID, []crdt.PartOps, error)

Split cuts a block in two at offset, and returns the new block, which holds everything from offset on and follows the one split. It is what pressing return in the middle of a paragraph does.

The new block is of type typ and is nested as deeply as the one it came from. Splitting at the end of a block leaves an empty one after it, and splitting at the start leaves an empty one before it; both are what a person pressing return at those places means.

func (*Blocks) Text added in v0.27.0 

func (b *Blocks) Text(id BlockID) (string, bool)

Text returns one block's characters, without the formatting.

func (*Blocks) Unmark added in v0.27.0 

func (b *Blocks) Unmark(from BlockID, fromOff int, to BlockID, toOff int, name string) (crdt.PartOps, error)

Unmark takes a mark off the text between two places, on the terms RichText.Unmark describes: it is a mark of its own rather than the removal of one.

func (*Blocks) Version added in v0.27.0 

func (b *Blocks) Version() crdt.CompositeVersion

Version returns what this replica has, one entry per part — three, whatever the document holds.

type Cell 

type Cell struct {
	// Kind selects a literal or a formula.
	Kind CellKind
	// Text is the literal's value or the formula's source, as the caller renders
	// it. It is opaque here.
	Text string
	// Refs are the cells a formula depends on, by stable identity. It is empty for
	// a literal, and may be empty for a formula that references nothing.
	Refs []CellRef
}

A Cell is the raw content of a spreadsheet cell: a literal value, or a formula's source together with the cells it references. It is what a Sheet stores and merges; a formula engine and a view are built above it and are no concern of this layer.

The zero Cell is a literal with no text, which is how an unset cell reads.

func Formula 

func Formula(source string, refs ...CellRef) Cell

Formula is the cell holding source, referencing refs by stable identity.

func Literal 

func Literal(value string) Cell

Literal is the cell holding value, the common case, without the caller naming a kind.

type CellKind 

type CellKind uint8

CellKind distinguishes a cell holding a plain value from one holding a formula. 

const (
	// CellLiteral is a cell whose content is its own value.
	CellLiteral CellKind = 1
	// CellFormula is a cell whose content is an expression over other cells. Its
	// source text is replicated; its computed value is not — that is derived
	// locally, so it is never a thing two replicas can disagree about.
	CellFormula CellKind = 2
)

type CellRef 

type CellRef struct {
	Row RowID
	Col ColID
}

A CellRef names a cell a formula depends on, by the stable identities of its row and column rather than by a position. A concurrent insertion or deletion of some other row renumbers positions but touches no identity, so a reference stored this way still names the same cell afterwards — which is what keeps =SUM(...) pointing where its author meant when the sheet changes shape beneath it.

type Chunker added in v0.24.0 

type Chunker func(data []byte) [][]byte

A Chunker cuts a file into the pieces it is stored as.

The pieces are what deduplication and repeated sending work in terms of, so where the cuts fall is what decides whether changing one corner of an image rewrites one chunk or all of them. FixedChunks cuts every n bytes, which is enough for a file that is written once and never edited and is the wrong answer for one that is: inserting a single byte at the front moves every later boundary and nothing matches any more.

A chunker that cuts on the content — one that hashes a sliding window and cuts where the hash has some shape, so a boundary depends on the bytes around it and not on how far into the file it is — makes an edit rewrite only the chunks it touched. This package does not carry one, because it carries nothing: the crdt module has no dependencies and this is not the thing to spend the first one on. Pass whichever you have.

func FixedChunks added in v0.24.0 

func FixedChunks(size int) Chunker

FixedChunks cuts every size bytes. A size of zero or less is one chunk.

type ColID 

type ColID crdt.ID

A ColID names a column, on the same terms as a RowID.

func (ColID) String 

func (c ColID) String() string

type ConnID 

type ConnID crdt.ID

A ConnID names a diagram connector, on the same terms as a RowID.

func (ConnID) String 

func (c ConnID) String() string

type Counter added in v0.20.0 

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

A Counter is a number any number of replicas may add to at once, offline, in any delivery order, and every replica ends up holding the same total.

Why a register is not one

The obvious way to share a number is a last-writer-wins register: read it, add one, write it back. That loses. Two replicas holding 7 both write 8, one of the two writes wins, and a vote is missed — the outcome does not depend on what either replica meant, only on which write sorted higher. The mistake is not in the register; it is that "add one" is not a value, and writing a value cannot express it.

How this one works

A counter is a map keyed by site, and a replica writes only its own key. Its key holds everything that replica has ever added and everything it has ever taken away, as two numbers that only ever grow. The total is the sum of the first minus the sum of the second, over every key.

Nothing ever conflicts, because no two replicas write the same key, and a replica's own key is a number it computes from what it alone has done. That is the whole of it: the crdt.Map underneath is doing no merging at all, and the counter is correct because concurrent additions are concurrent writes to different keys.

Why two numbers rather than one

A single signed total per site would be shorter and would work. Two are kept because each of them only ever increases, which is what makes a site's key safe to read back from any snapshot — an older copy of it can only be behind, never wrong in the other direction — and because a tally of what was added against what was taken away is what a vote, a stock level or a budget is actually asking for. Counter.Added and Counter.Removed return them.

func CounterOf added in v0.20.0 

func CounterOf(m *crdt.Map) *Counter

CounterOf reads a map as a counter, for a map that is a part of a crdt.Composite.

func LoadCounter added in v0.20.0 

func LoadCounter(site crdt.SiteID, snapshot []byte) (*Counter, error)

LoadCounter reads a snapshot back, as the given site.

func NewCounter added in v0.20.0 

func NewCounter(site crdt.SiteID) *Counter

NewCounter returns a counter this site can add to.

func (*Counter) Add added in v0.20.0 

func (c *Counter) Add(delta int64) (crdt.MapOp, error)

Add moves the counter by delta, which may be negative. Adding zero is not an operation and returns ErrNoChange.

func (*Counter) Added added in v0.20.0 

func (c *Counter) Added() int64

Added returns everything every replica has ever added, ignoring what was taken away. Removed returns the other half.

func (*Counter) Apply added in v0.20.0 

func (c *Counter) Apply(ops ...crdt.MapOp) error

Apply takes operations from a peer.

func (*Counter) Map added in v0.20.0 

func (c *Counter) Map() *crdt.Map

Map returns the map underneath, which is what is snapshotted and what operations are applied to.

func (*Counter) OpsSince added in v0.20.0 

func (c *Counter) OpsSince(vv crdt.VersionVector) []crdt.MapOp

OpsSince returns the operations a peer at vv has not seen.

func (*Counter) Removed added in v0.20.0 

func (c *Counter) Removed() int64

Removed returns everything every replica has ever taken away.

func (*Counter) Site added in v0.20.0 

func (c *Counter) Site() crdt.SiteID

Site returns the replica this counter adds as.

func (*Counter) Snapshot added in v0.20.0 

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

Snapshot returns the counter as bytes.

func (*Counter) Value added in v0.20.0 

func (c *Counter) Value() int64

Value returns the total: everything every replica has added, less everything every replica has taken away.

func (*Counter) Version added in v0.20.0 

func (c *Counter) Version() crdt.VersionVector

Version returns what this replica has seen.

type Diagram 

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

A Diagram is a collaborative diagram of nodes and connectors — an isometric diagram is the case it was shaped for. A node is a record of fields (a grid position, a label, a colour); a connector is a record whose fields are the identities of the two nodes it joins. Editing it produces operations that any number of replicas may exchange, offline and in any order, converging to the same diagram.

It is one crdt.Composite — the same core a Sheet is — which is the point of this package: a spreadsheet and a diagram are two thin addressings of one merging substrate, not two implementations. Each node and connector field merges on its own, so one replica may move a node while another recolours it and both edits survive.

Membership is the node and connector lists: Diagram.Nodes and Diagram.Conns say what exists. A field read is by identity and independent of membership, so it still answers for a removed node — a view renders what Diagram.Nodes returns and needs no more.

A Diagram is not safe for concurrent use. Construct one with NewDiagram or LoadDiagram.

func LoadDiagram 

func LoadDiagram(site crdt.SiteID, snapshot []byte) (*Diagram, error)

LoadDiagram rebuilds a diagram from a snapshot, to be edited as site.

func NewDiagram 

func NewDiagram(site crdt.SiteID) *Diagram

NewDiagram returns an empty diagram that issues operations as site. Every replica editing a diagram concurrently must pass a distinct crdt.SiteID.

func (*Diagram) AddConn 

func (d *Diagram) AddConn(from, to NodeID) (ConnID, []crdt.PartOps, error)

AddConn adds a connector from one node to another and returns its identity and the operations to broadcast: the connector's own identity, then its endpoints. The endpoints are stored by identity and are not required to name nodes this replica already holds — the node may arrive later, or be concurrently removed.

func (*Diagram) AddNode 

func (d *Diagram) AddNode() (NodeID, crdt.PartOps, error)

AddNode adds a node and returns its identity and the operation to broadcast. The node has no fields yet.

func (*Diagram) Apply 

func (d *Diagram) Apply(batches ...crdt.PartOps) error

Apply integrates batches of operations from peers, tolerating duplicates and reordering.

func (*Diagram) Collect added in v0.33.0 

func (d *Diagram) Collect(stable crdt.CompositeVersion) int

Collect gives back what a diagram that has been worked on no longer needs: the nodes and connectors that were removed, and the records saying they were.

A diagram is where this is worth asking for by hand. Its nodes live in a list and their properties in a map, and neither gives anything back on its own: a node dragged around and then deleted leaves an element and a record per property behind it, for good. On a diagram of two hundred nodes half of which were tried and removed, that is most of what the file weighs.

stable must be a version every replica has delivered, per part; see crdt.Doc.Collect for what that means and who can know it. A part it does not name is left alone.

func (*Diagram) Composite added in v0.33.0 

func (d *Diagram) Composite() *crdt.Composite

Composite returns the document underneath, for a caller that needs the parts themselves.

func (*Diagram) ConnEndpoints 

func (d *Diagram) ConnEndpoints(c ConnID) (from, to NodeID, ok bool)

ConnEndpoints returns the nodes a connector joins and whether both are set.

func (*Diagram) ConnField 

func (d *Diagram) ConnField(c ConnID, field string) ([]byte, bool)

ConnField returns the value of an arbitrary connector field and whether it is set. The value is a copy.

func (*Diagram) Conns 

func (d *Diagram) Conns() []ConnID

Conns returns the identities of the connectors present.

func (*Diagram) HasConn 

func (d *Diagram) HasConn(c ConnID) bool

HasConn reports whether a connector is present.

func (*Diagram) HasNode 

func (d *Diagram) HasNode(n NodeID) bool

HasNode reports whether a node is present.

func (*Diagram) NodeColour 

func (d *Diagram) NodeColour(n NodeID) (string, bool)

NodeColour returns a node's colour and whether it is set.

func (*Diagram) NodeField 

func (d *Diagram) NodeField(n NodeID, field string) ([]byte, bool)

NodeField returns the value of an arbitrary node field and whether it is set. The value is a copy.

func (*Diagram) NodeLabel 

func (d *Diagram) NodeLabel(n NodeID) (string, bool)

NodeLabel returns a node's label and whether it is set.

func (*Diagram) NodePosition 

func (d *Diagram) NodePosition(n NodeID) (x, y int32, ok bool)

NodePosition returns a node's grid position and whether it is set.

func (*Diagram) Nodes 

func (d *Diagram) Nodes() []NodeID

Nodes returns the identities of the nodes present. Two replicas holding the same operations return the same slice.

func (*Diagram) OpsSince 

func (d *Diagram) OpsSince(v crdt.CompositeVersion) ([]crdt.PartOps, error)

OpsSince returns the operations this replica holds that v does not, batched by part. Pass a nil version for everything.

func (*Diagram) Pending 

func (d *Diagram) Pending() int

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

func (*Diagram) RemoveConn 

func (d *Diagram) RemoveConn(c ConnID) (crdt.PartOps, error)

RemoveConn removes a connector's identity and returns the operation to broadcast. Its fields are left in place, as a removed node's are. A connector not present is ErrUnknownConn.

func (*Diagram) RemoveNode 

func (d *Diagram) RemoveNode(n NodeID) (crdt.PartOps, error)

RemoveNode removes a node's identity and returns the operation to broadcast. Its fields are left in place, unreferenced by any present node, exactly as a removed row's cells are in a Sheet. A node not present is ErrUnknownNode.

func (*Diagram) SetConnEndpoints 

func (d *Diagram) SetConnEndpoints(c ConnID, from, to NodeID) (crdt.PartOps, error)

SetConnEndpoints rewrites which nodes a connector joins and returns the operation to broadcast. The connector must be present.

func (*Diagram) SetConnField 

func (d *Diagram) SetConnField(c ConnID, field string, value []byte) (crdt.PartOps, error)

SetConnField writes an arbitrary field of a connector and returns the operation to broadcast — the generic form of Diagram.SetConnEndpoints for the fields a connector carries beyond its endpoints: a label, a style, an arrow, a colour, a width. Like Diagram.SetNodeField each field is its own register.

func (*Diagram) SetNodeColour 

func (d *Diagram) SetNodeColour(n NodeID, colour string) (crdt.PartOps, error)

SetNodeColour writes a node's colour and returns the operation to broadcast.

func (*Diagram) SetNodeField 

func (d *Diagram) SetNodeField(n NodeID, field string, value []byte) (crdt.PartOps, error)

SetNodeField writes an arbitrary field of a node and returns the operation to broadcast. It is the generic form of Diagram.SetNodePosition, Diagram.SetNodeLabel and Diagram.SetNodeColour, for the scalar fields a caller's schema carries beyond those three — a shape, an icon, a layer. Each field is its own LWW-register, so a concurrent write to two of them never conflicts. The value is opaque bytes; a caller storing a number should encode it identically on every architecture, as EncodeInt does. Writing the field a typed setter uses ("pos", "label", "colour") reaches the very same register.

func (*Diagram) SetNodeLabel 

func (d *Diagram) SetNodeLabel(n NodeID, label string) (crdt.PartOps, error)

SetNodeLabel writes a node's label and returns the operation to broadcast.

func (*Diagram) SetNodePosition 

func (d *Diagram) SetNodePosition(n NodeID, x, y int32) (crdt.PartOps, error)

SetNodePosition writes a node's grid position and returns the operation to broadcast. Coordinates are int32 so that every replica, on any architecture, stores and compares them identically.

func (*Diagram) Site 

func (d *Diagram) Site() crdt.SiteID

Site returns the replica identity this diagram issues operations as.

func (*Diagram) Snapshot 

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

Snapshot encodes the whole diagram, for a joining peer or for persistence.

func (*Diagram) Sweep added in v0.33.0 

func (d *Diagram) Sweep() ([]crdt.PartOps, error)

Sweep removes the properties of nodes and connectors that are no longer in the diagram.

It is the counterpart of Diagram.RemoveNode being one operation. Removing a node takes it out of the list of what exists; its label, its colour and its position stay in the map, keyed by a node nothing can reach any more. That is deliberate — a removal should be one operation, not one per property somebody happened to set — and it means a diagram worked on for a while carries every node it ever held.

This is what takes those bytes away, and it belongs where Ink.Sweep belongs: run when the drawing is quiet rather than while somebody is editing it. It has the same hazard for the same reason — a peer may be setting a property on a node this replica has been told to remove, and that arrives after the sweep and is swept by the next one. Nothing is corrupted; the node is removed, which is what was asked.

Sweeping turns unreachable records into tombstones. Diagram.Collect is what gives the tombstones back, once every replica has seen them go.

func (*Diagram) Version 

func (d *Diagram) Version() crdt.CompositeVersion

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

type Document 

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

A Document is a collaborative document made of several families of entities, each entity addressed by a stable identity the caller chooses. It is the shape an isometric diagram takes: nodes, connectors, zones, free text and layers all living in one merging substrate, every family a map of records and every field an independent LWW-register.

One composite, one boundary

Like Sheet and Diagram a Document is exactly one crdt.Composite: every family is a RecordMap over a distinct map part of that one composite, so the whole document has a single Document.Snapshot, a single Document.Version, a single Document.OpsSince and a single Document.Apply covering all five families at once. There is nothing to bundle and no second transport to keep in step — the convergence, commutativity, idempotence and associativity the crdt package proves for its parts are inherited whole, because there is only ever one set of parts doing the merging.

Caller-chosen identities

A Diagram mints a node's identity from its RGA, so two replicas that each "add a node" get two distinct nodes — which is right when the two are genuinely different. A Document instead lets the caller name an entity, because a toolkit that already has its own stable id for a shape needs the two replicas that create "the shape the user just dropped" to converge on one entity, not two. The id is the record key, so Document.Add of the same id on two replicas is the same write to the same key: they converge, with no local, non-replicated id table to keep. An id is arbitrary, non-empty UTF-8.

What exists

An entity exists exactly while it holds at least one live field — a field the caller set, or the presence marker Document.Add writes so that a freshly created entity with no fields yet still shows in Document.IDs. Reading a field is by identity and independent of membership, exactly as it is for a Diagram: a view renders what Document.IDs returns.

A Document holds no widget and no geometry engine. Field values are opaque bytes; EncodeInt, DecodeInt, EncodeBool and DecodeBool are offered so that the non-string fields a diagram carries are encoded identically on every architecture, js/wasm included, but nothing here interprets a field.

A Document is not safe for concurrent use. Construct one with NewDocument or LoadDocument.

Example

A Document is the five-family isometric core: nodes, connectors, zones, text and layers under one composite. Here two replicas, disconnected, each create the entity the user dropped under the same caller-chosen id and edit different fields of it; they exchange operations and converge on one entity carrying both edits. 

package main

import (
	"fmt"

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

func main() {
	ada, grace := structured.NewDocument(1), structured.NewDocument(2)

	// Both name the same node — a caller-chosen id, so the two creations converge.
	fromAda, _ := ada.Add(structured.Nodes, "server")
	fromGrace, _ := grace.Add(structured.Nodes, "server")

	// Offline, each writes a different field.
	adaX, _ := ada.Set(structured.Nodes, "server", "x", structured.EncodeInt(5))
	graceLabel, _ := grace.Set(structured.Nodes, "server", "label", []byte("web"))

	// They swap every operation, in either order, and agree.
	ada.Apply(fromGrace, graceLabel)
	grace.Apply(fromAda, adaX)

	x, _ := grace.Field(structured.Nodes, "server", "x")
	n, _ := structured.DecodeInt(x)
	label, _ := grace.Field(structured.Nodes, "server", "label")
	fmt.Println(grace.IDs(structured.Nodes), n, string(label))
}

Output:
[server] 5 web

func LoadDocument 

func LoadDocument(site crdt.SiteID, snapshot []byte) (*Document, error)

LoadDocument rebuilds a document from a snapshot, to be edited as site.

func NewDocument 

func NewDocument(site crdt.SiteID) *Document

NewDocument returns an empty document that issues operations as site. Every replica editing a document concurrently must pass a distinct crdt.SiteID.

func (*Document) Add 

func (d *Document) Add(fam Family, id string) (crdt.PartOps, error)

Add creates an entity in a family under the caller's id and returns the operation to broadcast. It writes a presence marker, so an entity with no fields yet is still present. Adding an id that already exists rewrites the marker and changes nothing observable, which is what lets two replicas both "create X" and converge.

func (*Document) Apply 

func (d *Document) Apply(batches ...crdt.PartOps) error

Apply integrates batches of operations from peers, tolerating duplicates and reordering, across every family at once.

func (*Document) DeleteField 

func (d *Document) DeleteField(fam Family, id, field string) (crdt.PartOps, error)

DeleteField removes one field of one entity and returns the operation to broadcast. Removing a field an entity does not hold is a no-op, not an error. Removing an entity's last field — the presence marker included — makes it cease to exist; use Document.Remove to clear an entity whole.

func (*Document) Field 

func (d *Document) Field(fam Family, id, field string) ([]byte, bool)

Field returns the value of one field and whether it is set. The value is a copy. An unknown family, an invalid id or an unset field reads as absent.

func (*Document) Fields 

func (d *Document) Fields(fam Family, id string) []string

Fields returns the field names an entity holds, ascending and with the internal namespace stripped, so the caller sees exactly the names it set. The presence marker and any foreign key a peer injected are not among them.

func (*Document) Has 

func (d *Document) Has(fam Family, id string) bool

Has reports whether an entity is present — whether it holds any live field. An unknown family or an invalid id is not present rather than an error, so a view may ask freely.

func (*Document) IDs 

func (d *Document) IDs(fam Family) []string

IDs returns the identities present in a family, ascending, so two replicas holding the same operations return the same slice. An unknown family has none.

func (*Document) OpsSince 

func (d *Document) OpsSince(v crdt.CompositeVersion) ([]crdt.PartOps, error)

OpsSince returns the operations this replica holds that v does not, batched by part and covering all five families. Pass a nil version for everything.

func (*Document) Pending 

func (d *Document) Pending() int

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

func (*Document) Remove 

func (d *Document) Remove(fam Family, id string) (crdt.PartOps, error)

Remove clears an entity — every field it holds, presence marker included — and returns the operations to broadcast, ascending so the batch is deterministic. An entity not present is ErrUnknownEntity. The concurrent case, a Remove racing a field write, is resolved per field by (clock, site) exactly as it is for a RecordMap: a write the Remove did not see re-establishes the entity.

func (*Document) Set 

func (d *Document) Set(fam Family, id, field string, value []byte) (crdt.PartOps, error)

Set writes value to one field of one entity and returns the operation to broadcast. The entity is created by the write if it did not exist, on the same terms as [Add], so a field may be set without a prior Add. value is opaque; use the encoders for a non-string field.

func (*Document) Site 

func (d *Document) Site() crdt.SiteID

Site returns the replica identity this document issues operations as.

func (*Document) Snapshot 

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

Snapshot encodes the whole document — all five families — for a joining peer or for persistence. Two replicas holding the same operations produce identical bytes.

func (*Document) Version 

func (d *Document) Version() crdt.CompositeVersion

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

type Draft added in v0.30.0 

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

A Draft is a working copy of a document, and a replica of it: edit the composite, then hand the draft to Proposals.Put.

func (*Draft) Base added in v0.30.0 

func (d *Draft) Base() crdt.CompositeVersion

Base returns the version the draft was taken at.

func (*Draft) Changed added in v0.30.0 

func (d *Draft) Changed() bool

Changed reports whether the draft has anything in it the document did not.

func (*Draft) Composite added in v0.30.0 

func (d *Draft) Composite() *crdt.Composite

Composite returns the working copy to edit. It is an ordinary document — wrap it in whatever this package's types the real one is read through.

type Expand added in v0.23.0 

type Expand uint8

Expand says whether text typed at the edge of a mark joins it.

It is the difference between bold, which continues as you type at the end of it, and a link, which does not. 

const (
	// ExpandNone is a mark neither edge of which grows: typing at either end
	// stays outside it. A link, a comment, a footnote reference.
	ExpandNone Expand = 0
	// ExpandStart makes text typed immediately before the mark part of it.
	ExpandStart Expand = 1 << iota
	// ExpandEnd makes text typed immediately after the mark part of it, which
	// is what bold and italic do.
	ExpandEnd
	// ExpandBoth grows at either edge.
	ExpandBoth = ExpandStart | ExpandEnd
)

type Family 

type Family string

A Family names one of the five kinds of entity a Document holds. Its value is also the name of the crdt.Composite map part the family lives in, so the set of families is the document's structural layout, fixed and the same on every replica; the fields inside a record are the caller's own schema, not this package's. 

const (
	// Nodes is the family of diagram nodes.
	Nodes Family = "node"
	// Connectors is the family of edges joining nodes.
	Connectors Family = "conn"
	// Zones is the family of rectangular regions.
	Zones Family = "zone"
	// TextBoxes is the family of free-standing text entities. It is not named
	// "Text" so as not to be mistaken for a [crdt.PartText]; a Document holds no
	// text part.
	TextBoxes Family = "text"
	// Layers is the family of layers entities are assigned to.
	Layers Family = "layer"
)

type Ink added in v0.25.0 

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

Ink is what is drawn by hand: the strokes of a whiteboard, an annotation over a figure, a signature.

What a stroke needs that the other types do not give it

A stroke is a list of points, and it arrives one point at a time while somebody is drawing it. Held as one value — a Sequence item whose contents are the whole path — every point sent rewrites the path: a stroke of four hundred points costs four hundred operations whose average size is two hundred points, and the person watching sees the line redrawn rather than extended.

So the points are a sequence of their own, appended to, and each point says which stroke it belongs to.

Why one stream of points and not one per stroke

A crdt.Composite part per stroke would keep each stroke's points together and read more simply. It would also put a part in the document for every stroke anybody ever drew, and a part cannot be taken out again: the version two replicas exchange to find out what they are missing carries one entry per part, so a whiteboard would come to spend more on saying what it has than on what was drawn.

One stream costs a stroke identity on every point — a dozen bytes — and keeps the document two parts wide however much is drawn on it.

What is where

  • The strokes are a Sequence, so the order they are drawn in is the order they are painted in, and a stroke can be moved above or below another without being redrawn. Anything a stroke carries — its colour, its width, the pen it was drawn with — is a field on the item.
  • The points are a crdt.List, appended to as the pen moves.

func InkOf added in v0.25.0 

func InkOf(doc *crdt.Composite) *Ink

InkOf reads a composite as a drawing, for a document that holds one among other parts.

func LoadInk added in v0.25.0 

func LoadInk(site crdt.SiteID, snapshot []byte) (*Ink, error)

LoadInk rebuilds a drawing from a snapshot, to be drawn on as site.

func NewInk added in v0.25.0 

func NewInk(site crdt.SiteID) *Ink

NewInk returns an empty drawing this site can draw on.

func (*Ink) Apply added in v0.25.0 

func (i *Ink) Apply(batches ...crdt.PartOps) error

Apply integrates operations from peers.

func (*Ink) Begin added in v0.25.0 

func (i *Ink) Begin() (StrokeID, []crdt.PartOps, error)

Begin starts a stroke, above every stroke already drawn, and returns it with no points yet.

func (*Ink) Composite added in v0.25.0 

func (i *Ink) Composite() *crdt.Composite

Composite returns the document underneath.

func (*Ink) Erase added in v0.25.0 

func (i *Ink) Erase(stroke StrokeID) (crdt.PartOps, error)

Erase takes a stroke out of the drawing.

Its points stay until Ink.Sweep takes them, because erasing happens while somebody is drawing and has to cost one operation rather than one per point.

func (*Ink) Extend added in v0.25.0 

func (i *Ink) Extend(stroke StrokeID, pts ...Point) (crdt.PartOps, error)

Extend adds points to the end of a stroke.

It is one operation however many points are given, so a pen that reports several samples between two frames costs one operation rather than several.

func (*Ink) OpsSince added in v0.25.0 

func (i *Ink) OpsSince(v crdt.CompositeVersion) ([]crdt.PartOps, error)

OpsSince returns the operations a peer at v has not seen.

func (*Ink) Paths added in v0.25.0 

func (i *Ink) Paths() [][]Point

Paths returns every stroke that is still drawn, in the order they are painted in, with its points.

It is one walk of the points rather than one per stroke, which is what a repaint wants: Ink.Points asked for each of five hundred strokes walks the whole drawing five hundred times.

func (*Ink) Pending added in v0.25.0 

func (i *Ink) Pending() int

Pending reports how many received operations are still waiting.

func (*Ink) Points added in v0.25.0 

func (i *Ink) Points(stroke StrokeID) []Point

Points returns the points of a stroke, in the order they were drawn.

func (*Ink) Site added in v0.25.0 

func (i *Ink) Site() crdt.SiteID

Site returns the replica this drawing draws as.

func (*Ink) Snapshot added in v0.25.0 

func (i *Ink) Snapshot() []byte

Snapshot encodes the whole drawing.

func (*Ink) Strokes added in v0.25.0 

func (i *Ink) Strokes() *Sequence

Strokes returns the sequence the strokes live in, for the order they are painted in and whatever each of them carries.

func (*Ink) Sweep added in v0.25.0 

func (i *Ink) Sweep() (crdt.PartOps, error)

Sweep removes the points of strokes that are no longer drawn.

It is the counterpart of Ink.Erase being one operation: erasing says the stroke is gone, and this is what takes the bytes away, when the drawing is quiet rather than while somebody is drawing on it.

It has the hazard Blobs.Sweep has and for the same reason: a peer may be extending a stroke this replica has been told to erase, and those points arrive after the sweep and are swept by the next one. Nothing is corrupted — the stroke is erased, which is what was asked.

func (*Ink) Version added in v0.25.0 

func (i *Ink) Version() crdt.CompositeVersion

Version returns what this replica holds.

type ItemID added in v0.21.0 

type ItemID crdt.ID

An ItemID names an item. It is stable across a reload and unique across replicas, because it is the identity of the operation that created the item.

func (ItemID) IsStart added in v0.21.0 

func (i ItemID) IsStart() bool

IsStart reports whether i names the place before the first item rather than an item.

func (ItemID) String added in v0.21.0 

func (i ItemID) String() string

String returns the identity in the form the rest of this package prints one.

type MultiRegister added in v0.28.0 

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

A MultiRegister is a value that two replicas are allowed to disagree about, where the disagreement is the answer rather than something to be settled.

What a register cannot say

Register resolves every concurrent write by the (clock, site) order, which is exactly right when a losing write is of no interest: a cursor position, a window size, a colour somebody picked. It is wrong when it is. Two people rename the same file at the same moment and one of the names is gone, with nothing anywhere recording that there was ever a second one — not in the state, not in the operations, not in anything a reader could show. The register did not choose badly; it has no way of saying that a choice was made.

How this one works

Each replica writes only its own key, as a Counter does, so no two replicas ever write the same one and the map underneath is doing no merging at all. What a replica writes is its value together with a version vector: how many times it has written, and how many times it had seen every other replica write when it did.

A value is live when no other value's vector strictly dominates it. Two replicas that wrote without seeing each other have vectors neither of which dominates the other, so both values are live and both are read. A replica that writes having seen the other dominates it, and its value is the only one read.

That last sentence is also the whole of resolving a conflict: choosing one of the values is writing it, and writing it dominates everything the writer could see, including the value they chose. There is no separate operation for settling, and none is needed — see MultiRegister.Set.

What it costs

One key per replica that has ever written, and a vector of one entry per replica that has ever written inside each of those. That is the same shape a Counter has, for the same reason, and it is the price of being able to say that two writes did not see each other — a Lamport clock cannot, because it gives a total order, and the question is which pairs are unordered.

Example

A MultiRegister keeps a disagreement instead of settling it. Here two replicas rename the same thing while disconnected: an ordinary register would throw one name away with nothing left saying it existed, and this one hands both back. Choosing between them is writing the one chosen. 

package main

import (
	"fmt"

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

func main() {
	ada, grace := structured.NewMultiRegister(1), structured.NewMultiRegister(2)

	// Offline, each names the file.
	fromAda, _ := ada.Set([]byte("notes.txt"))
	fromGrace, _ := grace.Set([]byte("readme.txt"))

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

	fmt.Println(ada.Conflicted())
	for _, name := range ada.Values() {
		fmt.Printf("%s\n", name)
	}

	// Ada picks one. That write saw both, so it supersedes both.
	chosen, _ := ada.Set([]byte("readme.txt"))
	grace.Apply(chosen)
	name, only := grace.Value()
	fmt.Printf("%s %v\n", name, only)
}

Output:
true
notes.txt
readme.txt
readme.txt true

func LoadMultiRegister added in v0.28.0 

func LoadMultiRegister(site crdt.SiteID, snapshot []byte) (*MultiRegister, error)

LoadMultiRegister rebuilds one from a snapshot, to be written as site.

func MultiRegisterOf added in v0.28.0 

func MultiRegisterOf(m *crdt.Map) *MultiRegister

MultiRegisterOf reads a map as a multi-value register, for a map that is a part of a crdt.Composite.

func NewMultiRegister added in v0.28.0 

func NewMultiRegister(site crdt.SiteID) *MultiRegister

NewMultiRegister returns an empty register this site can write.

func (*MultiRegister) Apply added in v0.28.0 

func (r *MultiRegister) Apply(ops ...crdt.MapOp) error

Apply integrates operations from peers, tolerating duplicates and reordering.

func (*MultiRegister) Clear added in v0.28.0 

func (r *MultiRegister) Clear() (crdt.MapOp, error)

Clear takes the value away, on the same terms as MultiRegister.Set: it is a writing of its own, it dominates everything this replica has seen, and a concurrent write that has not seen it stays live beside it.

func (*MultiRegister) Conflicted added in v0.28.0 

func (r *MultiRegister) Conflicted() bool

Conflicted reports whether more than one writing is live: two replicas wrote without seeing each other, and both writings stand.

func (*MultiRegister) Map added in v0.28.0 

func (r *MultiRegister) Map() *crdt.Map

Map returns the map underneath, which is what is snapshotted and what operations are applied to.

func (*MultiRegister) OpsSince added in v0.28.0 

func (r *MultiRegister) OpsSince(vv crdt.VersionVector) []crdt.MapOp

OpsSince returns the operations this replica holds that vv does not.

func (*MultiRegister) Readings added in v0.28.0 

func (r *MultiRegister) Readings() []Reading

Readings returns every writing of the register that nothing has superseded, in site order.

One reading is the ordinary case. More than one is a disagreement: two or more replicas wrote without seeing each other, and there is no fact anywhere that says which of them is the answer. Nothing here invents one.

func (*MultiRegister) Set added in v0.28.0 

func (r *MultiRegister) Set(value []byte) (crdt.MapOp, error)

Set writes value, and in doing so settles every disagreement this replica can see: the write's vector dominates every reading it was made against, so the register reads as this one value until somebody who has not seen it writes again.

Choosing between the values of a conflict is therefore not a separate operation. Write the one that was chosen.

func (*MultiRegister) Site added in v0.28.0 

func (r *MultiRegister) Site() crdt.SiteID

Site returns the replica this register writes as.

func (*MultiRegister) Snapshot added in v0.28.0 

func (r *MultiRegister) Snapshot() []byte

Snapshot encodes the whole register, for a joining peer or for persistence.

func (*MultiRegister) Value added in v0.28.0 

func (r *MultiRegister) Value() ([]byte, bool)

Value returns the one value the register holds, and whether it holds exactly one. A register nobody has written, one everybody agrees is cleared, and one two replicas disagree about all report false — so a caller that ignores the second return reads no value rather than an arbitrary one.

func (*MultiRegister) Values added in v0.28.0 

func (r *MultiRegister) Values() [][]byte

Values returns the values of the live readings, in site order, leaving out any replica that cleared the register.

It is what a reader that has no way of showing a conflict should use with MultiRegister.Conflicted: one value, or a list to be offered.

func (*MultiRegister) Version added in v0.28.0 

func (r *MultiRegister) Version() crdt.VersionVector

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

type NodeID 

type NodeID crdt.ID

A NodeID names a diagram node, on the same terms as a RowID. A node's fields are stored against it, and a connector's endpoints reference it.

func NodeSelectionOf 

func NodeSelectionOf(p awareness.Peer) (NodeID, bool)

NodeSelectionOf returns the node a peer has selected, and whether it has a valid one.

func (NodeID) String 

func (n NodeID) String() string

type Outlined added in v0.27.0 

type Outlined struct {
	Block
	Parent BlockID
}

An Outlined is a block together with the block it hangs under.

type Point added in v0.25.0 

type Point struct {
	X, Y     float32
	Pressure float32
}

A Point is one sample of a pen: where it was, and how hard it was pressed.

Pressure is whatever the input device reports, normally between zero and one, and is carried rather than interpreted. A device with no pressure sensor should send one.

type Proposal added in v0.30.0 

type Proposal struct {
	// ID names it.
	ID ProposalID
	// Title is what it was put up as.
	Title string
	// Author is the replica that put it up, which is the site the proposal's
	// identity was minted by. It is not the draft's site: a draft's site is a
	// second identity the same person holds so that its operations do not
	// collide with the ones their replica is making, and it says nothing about
	// who they are.
	Author crdt.SiteID
	// State is what has become of it.
	State State
	// Base is the version of the document the draft was taken from. It is
	// informational: the operations merge whatever the document has done
	// since, and what a reader wants it for is whether the change still means
	// what its author meant — a reworded sentence somebody has since deleted
	// merges cleanly and says nothing.
	Base crdt.CompositeVersion
	// Ops is what accepting it would apply.
	Ops []crdt.PartOps
}

A Proposal is one proposed change as it stands.

type ProposalID added in v0.30.0 

type ProposalID crdt.ID

A ProposalID names a proposal. It is the identity of the operation that created it, so it is unique across replicas, reload-safe, and carries the site that raised it.

func (ProposalID) String added in v0.30.0 

func (p ProposalID) String() string

String renders the identity in the "seq@site" notation the crdt package uses.

type Proposals added in v0.30.0 

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

Proposals are changes to a document that are not part of it yet: a suggested edit, a change put up for review, a branch somebody wants merged.

Why this is not a fork

The obvious shape is a second copy of the document, edited on its own and reconciled later. Reconciling is where it falls apart. Two copies of a text can be compared, and what a comparison produces is a difference — insert this here, delete that — and applying a difference mints new characters. Every anchor, mark, comment and cursor hanging off the characters it replaced is then pointing at something that no longer exists, in a document nobody edited in the meantime. A review that accepts a wording change would take the comments off the paragraph around it.

What a proposal actually is

A replica that has not synced. Nothing more.

Operations here commute, so a replica that goes offline, edits, and comes back a week later needs no reconciliation: its operations merge with everything that happened while it was away, and every identity it wrote is the identity the rest of the document already knows. A proposal is that same replica, kept offline on purpose, with its operations written down where reviewers can read them and applied if somebody says yes.

So accepting is crdt.Composite.Apply of the operations, and there is no rebase, no merge step and no conflict to settle: whatever the document did while the proposal was open, the proposal merges into it as concurrent work, because it is concurrent work. And nothing an anchor points at is disturbed, because the proposal is made of the document's own operations against the document's own identities rather than of a difference between two texts.

Rejecting is free for the same reason: the operations were never applied, so there is nothing to take back. That is not true of anything already in the document, which can only be undone by Undo — a new edit that has the effect of the old one not having happened.

A draft is a replica, so it needs a site of its own

Proposals.Draft hands back a working copy to edit, and it takes a crdt.SiteID, for exactly the reason every replica takes one: two replicas minting operations under one site mint the same identity for different operations, and a document that received both would be holding two different things that claim to be the same. A draft is a replica. Give it its own site.

What it costs, and what it will not do

A proposal is stored as one map value holding its operations, so it is one operation the size of the change. That is the right shape for a review — a wording, a paragraph, a renamed field — and the wrong one for a rewrite of the whole document, which should be a document.

A proposal is a recorded set of operations, not a live session: this package does not carry two people typing into one draft at the same time. Two people can each hold the draft as a replica and exchange its operations — which is what a draft being a replica means — and what gets written down when it is put up is whatever the draft holds then.

Example

A Proposals is changes to a document that are not part of it yet. A proposal is a replica that has not synced: accepting it applies the document's own operations, so it merges with whatever happened while it was open and leaves every anchor where it was. 

package main

import (
	"fmt"

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

func main() {
	docs := structured.NewProposals(1)
	text, _ := docs.Composite().Text("text")
	text.Insert(0, "Hello world")

	// A draft is a replica, so it gets a site of its own.
	draft, _ := docs.Draft(2)
	drafted, _ := draft.Composite().Text("text")
	drafted.Insert(6, "beautiful ")
	id, _, _ := docs.Put("an adjective", draft)

	// The document has not moved, and the proposal can be read before it is in.
	fmt.Println(text.String())
	preview, _ := docs.Preview(id, 9)
	previewed, _ := preview.Text("text")
	fmt.Println(previewed.String())

	// Meanwhile somebody edits the same sentence, and accepting merges.
	text.Insert(11, ", and goodbye")
	docs.Accept(id)
	fmt.Println(text.String())
	fmt.Println(docs.List()[0].State)
}

Output:
Hello world
Hello beautiful world
Hello beautiful world, and goodbye
accepted

func LoadProposals added in v0.30.0 

func LoadProposals(site crdt.SiteID, snapshot []byte) (*Proposals, error)

LoadProposals rebuilds one from a snapshot, to be edited as site.

func NewProposals added in v0.30.0 

func NewProposals(site crdt.SiteID) *Proposals

NewProposals returns an empty document with proposals on it, this site can edit.

func ProposalsOf added in v0.30.0 

func ProposalsOf(doc *crdt.Composite) *Proposals

ProposalsOf reads a composite as a document that can carry proposals. The proposals are one part of it; the rest of the document is whatever else it holds.

func (*Proposals) Accept added in v0.30.0 

func (p *Proposals) Accept(id ProposalID) ([]crdt.PartOps, error)

Accept applies a proposal's operations to the document and records that it was accepted.

There is no rebase and nothing to settle. The operations merge with whatever the document has done since the draft was taken, exactly as a replica coming back from a week offline does, because that is what they are.

Accepting one that is already accepted applies the operations again, which changes nothing — they are the same operations — and writes the field again. Accepting a withdrawn one is allowed and makes it accepted: somebody changed their mind, and the document is what says so.

func (*Proposals) Apply added in v0.30.0 

func (p *Proposals) Apply(batches ...crdt.PartOps) error

Apply takes operations from a peer.

func (*Proposals) Composite added in v0.30.0 

func (p *Proposals) Composite() *crdt.Composite

Composite returns the document underneath, which is what is snapshotted and what operations are applied to.

func (*Proposals) Draft added in v0.30.0 

func (p *Proposals) Draft(site crdt.SiteID) (*Draft, error)

Draft returns a working copy of the document as it stands, to be edited as site.

site must be one no other replica is using, for the reason every replica's must be: a draft is a replica, and two replicas sharing a site mint one identity for two different operations. Passing the document's own site is refused, because that is the one collision this package can see coming.

func (*Proposals) Forget added in v0.30.0 

func (p *Proposals) Forget(id ProposalID) ([]crdt.PartOps, error)

Forget takes a proposal's record out of the document, which is what an accepted one is once nobody needs to read what it was: its operations are in the document, and the record is a copy of them.

It does not take the change out. Nothing does; see Undo.

func (*Proposals) Get added in v0.30.0 

func (p *Proposals) Get(id ProposalID) (Proposal, bool)

Get returns one proposal.

A record missing any of the three things a proposal is made of — a title, a base and its operations — is not one, and reads as absent rather than as a proposal that would do nothing. A map holds whatever key an applied operation names, so that is a state a peer can put this replica in.

func (*Proposals) List added in v0.30.0 

func (p *Proposals) List() []Proposal

List returns every proposal in the order they were raised.

The order is the (clock, site) one the map resolves its own writes by, taken from the write of the title — so it is a causal order where there is one, and settled by site where two replicas raised a proposal without seeing each other. Every replica reads the same list.

func (*Proposals) Open added in v0.30.0 

func (p *Proposals) Open() []Proposal

Open returns the proposals nobody has decided about, oldest first.

func (*Proposals) OpsSince added in v0.30.0 

func (p *Proposals) OpsSince(v crdt.CompositeVersion) ([]crdt.PartOps, error)

OpsSince returns the operations a peer at v has not seen.

func (*Proposals) Pending added in v0.30.0 

func (p *Proposals) Pending() int

Pending reports how many operations are held back waiting for ones they depend on.

func (*Proposals) Preview added in v0.30.0 

func (p *Proposals) Preview(id ProposalID, site crdt.SiteID) (*crdt.Composite, error)

Preview returns the document as it would read with a proposal in it, without putting it in: a copy, loaded as site, with the operations applied.

site is what the copy would edit as if the caller went on to edit it, and is subject to the same rule Proposals.Draft states. Nothing here writes to it.

func (*Proposals) Put added in v0.30.0 

func (p *Proposals) Put(title string, d *Draft) (ProposalID, []crdt.PartOps, error)

Put writes a draft up as a proposal, and returns its identity.

A draft that changes nothing is ErrNoChange rather than an empty proposal: there is nothing for a reviewer to look at and nothing for accepting to do.

func (*Proposals) Records added in v0.30.0 

func (p *Proposals) Records() *RecordMap

Records returns the record map the proposals live in.

func (*Proposals) Site added in v0.30.0 

func (p *Proposals) Site() crdt.SiteID

Site returns the replica this document edits as.

func (*Proposals) Snapshot added in v0.30.0 

func (p *Proposals) Snapshot() []byte

Snapshot returns the document as bytes, proposals included.

func (*Proposals) Version added in v0.30.0 

func (p *Proposals) Version() crdt.CompositeVersion

Version returns what this replica holds.

func (*Proposals) Withdraw added in v0.30.0 

func (p *Proposals) Withdraw(id ProposalID) (crdt.PartOps, error)

Withdraw records that a proposal was taken back or turned down. Its operations were never applied, so there is nothing to take out of the document; withdrawing costs one write and leaves the proposal readable, which is what a record of a decision is for.

A withdrawal of a proposal somebody else has already accepted is a label. See Proposals.Accept.

type Reading added in v0.28.0 

type Reading struct {
	// Site is the replica that wrote it.
	Site crdt.SiteID
	// Value is what that replica wrote, or nil if it cleared the register.
	Value []byte
	// Cleared is true when that replica took the value away rather than
	// writing one. A clear that nobody has seen is as live as a value nobody
	// has seen, which is what makes "somebody deleted this while I was
	// renaming it" a thing a reader can be shown.
	Cleared bool
}

A Reading is one replica's writing of the register, as it stands now.

type RecordMap 

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

A RecordMap is a map of records built over a single crdt.Map: an observed- remove map whose values are themselves records, each a set of named fields, and each field an independent LWW-register.

Why the fields merge independently

A record is not stored as one opaque value. Were it, two replicas that concurrently changed two different fields of the same record — one moved a node, the other recoloured it — would collide, and last-writer-wins would discard one of the two edits wholesale. Storing each field under its own map key makes the two edits touch different keys, so both survive and only a genuine same-field conflict is a conflict, resolved by the (clock, site) order.

Add and remove

A record exists exactly while it has a live field. RecordMap.DeleteRecord removes the fields it can see, which is the whole record as this replica knows it. The policy for the race that leaves — a delete concurrent with a write to the same record — is the map's own: it is resolved per field by (clock, site), so a field written after the delete it did not see re-establishes the record, and one written before loses. That is last-writer-wins at the granularity of a field, stated once here rather than arbitrated case by case.

A RecordMap is not safe for concurrent use. The zero RecordMap is unusable — construct one with NewRecordMap, or view an existing map with RecordsOf.

func NewRecordMap 

func NewRecordMap(site crdt.SiteID) *RecordMap

NewRecordMap returns an empty record map that issues operations as site.

func RecordsOf 

func RecordsOf(m *crdt.Map) *RecordMap

RecordsOf views an existing map as a record map. The two share their storage, so an operation applied through one is seen by the other; it is how a document keeps a part's records beside its other parts.

func (*RecordMap) DeleteField 

func (r *RecordMap) DeleteField(rec, field string) (crdt.MapOp, error)

DeleteField removes one field and returns the operation describing it. The record ceases to exist when its last field is removed.

func (*RecordMap) DeleteRecord 

func (r *RecordMap) DeleteRecord(rec string) ([]crdt.MapOp, error)

DeleteRecord removes every live field of one record and returns the operations describing it, in ascending field order so the batch is deterministic. It removes what this replica can see; see RecordMap for the concurrent case.

func (*RecordMap) Fields 

func (r *RecordMap) Fields(rec string) []string

Fields returns the live field names of one record, ascending, so that two replicas holding the same operations return the same slice.

func (*RecordMap) GetField 

func (r *RecordMap) GetField(rec, field string) ([]byte, bool)

GetField returns the value of one field and whether it is set. The value is a copy.

func (*RecordMap) HasRecord 

func (r *RecordMap) HasRecord(rec string) bool

HasRecord reports whether a record has at least one live field — which is what it means for it to exist. It stops at the first, so it does not build the whole field list a membership test does not need. A foreign key an operation injected that this map's own writes could not have produced is not a field and does not make a record exist.

func (*RecordMap) Map 

func (r *RecordMap) Map() *crdt.Map

Map returns the underlying map, whose Version, OpsSince, Apply and Snapshot are the record map's transport and persistence.

func (*RecordMap) Records 

func (r *RecordMap) Records() []string

Records returns the identities of every record with at least one live field, ascending. A key an operation injected that this map's own writes could not have produced is not a record and is skipped.

func (*RecordMap) SetField 

func (r *RecordMap) SetField(rec, field string, value []byte) (crdt.MapOp, error)

SetField writes value to one field of one record and returns the operation describing it, already applied. The record is created by the write if it did not exist.

type Register 

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

A Register is a single last-writer-wins value: any number of replicas may write it at once, offline, in any delivery order, and every replica ends up holding the same value. Writes are ordered by the (Lamport clock, site) total order the crdt package defines — a maximum, so it does not depend on the order the writes arrive in — and the tie a shared clock would leave is broken by site, deterministically, without a wall clock ever being read.

It is the degenerate keyed map: one key, and nothing to merge that crdt.Map does not already merge. The whole of a Register is that restriction, so it carries no merge logic of its own and inherits the map's convergence, idempotence and wire format unchanged.

A Register is not safe for concurrent use. The zero Register is unusable — construct one with NewRegister or LoadRegister.

func LoadRegister 

func LoadRegister(site crdt.SiteID, snapshot []byte) (*Register, error)

LoadRegister rebuilds a register from a snapshot, to be written as site.

func NewRegister 

func NewRegister(site crdt.SiteID) *Register

NewRegister returns an empty register that issues operations as site. Every replica writing to a register concurrently must pass a distinct site.

func (*Register) Apply 

func (r *Register) Apply(ops ...crdt.MapOp) error

Apply integrates operations from peers, tolerating duplicates and reordering.

func (*Register) Clear 

func (r *Register) Clear() (crdt.MapOp, error)

Clear removes the value and returns the operation describing it. Like a map deletion it keeps the write's clock, so a concurrent Set resolves against it by the same order rather than always winning.

func (*Register) Get 

func (r *Register) Get() ([]byte, bool)

Get returns the current value and whether one is set. A cleared register reads as absent. The value is a copy.

func (*Register) OpsSince 

func (r *Register) OpsSince(vv crdt.VersionVector) []crdt.MapOp

OpsSince returns the operations this replica holds that vv does not.

func (*Register) Set 

func (r *Register) Set(value []byte) (crdt.MapOp, error)

Set writes value and returns the operation describing it, already applied; send it to every peer. The register copies value.

func (*Register) Snapshot 

func (r *Register) Snapshot() []byte

Snapshot encodes the whole register, for a joining peer or for persistence.

func (*Register) Version 

func (r *Register) Version() crdt.VersionVector

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

type RichText added in v0.23.0 

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

A RichText is text that carries formatting: bold, italic, a colour, a link, a comment — anything that covers a stretch of characters rather than one of them.

Why the marks are not in the text

The obvious way to write formatting into a sequence CRDT is to put it there: a bold-on character, a bold-off character, or a per-character attribute. Both lose.

Markers in the sequence come apart. Two replicas that bold overlapping stretches produce interleaved on and off markers, and the text between them reads as bold on one replica and not on the other, because which marker won depends on where each landed rather than on what either person meant.

A per-character attribute does converge, and costs a write per character: a person selecting a paragraph and pressing bold sends one operation for every letter of it, forever, and each of those operations is stored forever.

How this one works

A mark is one operation naming two anchors, and the formatting of the document is worked out when it is read. That is the shape Tree and Sequence use for the same reason: the answer is a function of the state, so two replicas holding the same operations read the same formatting whatever order it arrived in.

Where two marks of the same name disagree about a character — one bolding it, another taking bold away — the later of the two wins, by the (clock, site) order crdt.Map resolves its own writes by. Nothing is discarded: a mark that lost to a later one is still there, and a third mark can put it back.

What an anchor is, and why formatting grows the way it does

An anchor is not an offset. An offset stored anywhere in a document people are editing means something else a moment later. An anchor names a character and a side of it: the boundary immediately before it, or immediately after it. Text typed into the gap that boundary sits in falls on one side or the other, and that is exactly the question "does what I am typing continue the bold".

Which side is the caller's to choose, because the answer differs by what the mark is. Typing at the end of a bold word should continue it, so bold ends at the boundary before the next character and grows. Typing at the end of a link should not become part of the link, so a link ends at the boundary after its last character and does not. See Expand.

func LoadRichText added in v0.23.0 

func LoadRichText(site crdt.SiteID, snapshot []byte) (*RichText, error)

LoadRichText rebuilds one from a snapshot, to be edited as site.

func NewRichText added in v0.23.0 

func NewRichText(site crdt.SiteID) *RichText

NewRichText returns an empty rich text this site can edit.

func RichTextOf added in v0.23.0 

func RichTextOf(doc *crdt.Composite) *RichText

RichTextOf reads a composite as a rich text, for a document that holds one among other parts.

func (*RichText) Apply added in v0.23.0 

func (r *RichText) Apply(batches ...crdt.PartOps) error

Apply integrates operations from peers.

func (*RichText) Composite added in v0.23.0 

func (r *RichText) Composite() *crdt.Composite

Composite returns the document underneath, which is what is snapshotted and what operations are applied to.

func (*RichText) Delete added in v0.23.0 

func (r *RichText) Delete(pos, count int) (crdt.PartOps, error)

Delete removes count characters from visible offset pos.

func (*RichText) Doc added in v0.23.0 

func (r *RichText) Doc() *crdt.Doc

Doc returns the text part, for anything this type does not wrap — anchors for a cursor, the authorship of a character.

func (*RichText) Insert added in v0.23.0 

func (r *RichText) Insert(pos int, s string) (crdt.PartOps, error)

Insert puts s at visible offset pos.

func (*RichText) Len added in v0.23.0 

func (r *RichText) Len() int

Len returns how many visible characters there are.

func (*RichText) Mark added in v0.23.0 

func (r *RichText) Mark(from, to int, name string, value []byte, expand Expand) (crdt.PartOps, error)

Mark puts a mark on the characters at [from, to), carrying value, which may be nil for a mark that is only on or off.

expand says whether text typed at either edge joins it; see Expand.

func (*RichText) MarksAt added in v0.23.0 

func (r *RichText) MarksAt(pos int) map[string][]byte

MarksAt returns the formatting of the character at pos.

func (*RichText) OpsSince added in v0.23.0 

func (r *RichText) OpsSince(v crdt.CompositeVersion) ([]crdt.PartOps, error)

OpsSince returns the operations a peer at v has not seen.

func (*RichText) Pending added in v0.23.0 

func (r *RichText) Pending() int

Pending reports how many received operations are still waiting for the ones they depend on.

func (*RichText) Site added in v0.23.0 

func (r *RichText) Site() crdt.SiteID

Site returns the replica this text edits as.

func (*RichText) Snapshot added in v0.23.0 

func (r *RichText) Snapshot() []byte

Snapshot encodes the whole thing, text and formatting together.

func (*RichText) Spans added in v0.23.0 

func (r *RichText) Spans() []Span

Spans returns the text broken into stretches over which the formatting does not change, in order, covering every character exactly once.

func (*RichText) Text added in v0.23.0 

func (r *RichText) Text() string

Text returns the characters, without the formatting.

func (*RichText) Unmark added in v0.23.0 

func (r *RichText) Unmark(from, to int, name string) (crdt.PartOps, error)

Unmark takes a mark off the characters at [from, to).

It is a mark of its own rather than the removal of one, because the mark it undoes may not have arrived yet, may cover more than this, and may be one of several. What it says is that these characters do not carry this name as of now, and a later mark can say otherwise.

func (*RichText) Version added in v0.23.0 

func (r *RichText) Version() crdt.CompositeVersion

Version returns what this replica holds.

type RowID 

type RowID crdt.ID

A RowID names a row for as long as the row exists, whatever concurrent edits do to the rows around it. It is a crdt.List element identity minted by the RGA, so it is unique across replicas, reload-safe, and never reused — the property a formula reference depends on.

func (RowID) String 

func (r RowID) String() string

String renders each identity as the "seq@site" notation the crdt package uses.

type Sequence added in v0.21.0 

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

A Sequence is an ordered collection whose items can be moved: the slides of a talk, the columns of a board, the order of a bibliography, the layers of a drawing, the rows of a list a person drags about.

Why not a list

crdt.List is an RGA, and it is the right structure for text: it decides where a new character goes against every other character being typed at the same moment, and it does so per character. What it has no operation for is moving something that is already in it. Written with the operations it does have, a move is a delete and an insert — two operations, and a second replica moving the same item at the same time splits them, so the item ends up in both places or in neither.

How this one works

An item carries where it sits as a value, the way a node of a Tree carries where it sits among its siblings: a rank, with another always available between any two, so moving an item is a single write of a single field. Two replicas that move the same item at once are then two writes to one field, which is a conflict crdt.Map already knows how to settle and settles the same way on both.

Items are read in order of (rank, identity). The identity is there because two replicas inserting at the same place at the same moment mint the same rank, and an order that stopped at the rank would not be an order.

What it gives up against a list

The RGA's per-character judgement, which an opaque item does not need, and with it the property that an insert never has to be told about its neighbours. This has to read the ranks either side of where an item is going, which is one descent of a sorted slice rather than a walk of the collection.

func LoadSequence added in v0.21.0 

func LoadSequence(site crdt.SiteID, snapshot []byte) (*Sequence, error)

LoadSequence reads a snapshot back, as the given site.

func NewSequence added in v0.21.0 

func NewSequence(site crdt.SiteID) *Sequence

NewSequence returns an empty sequence this site can edit.

func SequenceOf added in v0.21.0 

func SequenceOf(m *crdt.Map) *Sequence

SequenceOf reads a map as a sequence, for a map that is a part of a crdt.Composite.

func (*Sequence) Apply added in v0.21.0 

func (s *Sequence) Apply(ops ...crdt.MapOp) error

Apply takes operations from a peer.

func (*Sequence) At added in v0.21.0 

func (s *Sequence) At(pos int) (ItemID, bool)

At returns the item at a position, and whether there is one there.

func (*Sequence) GetField added in v0.21.0 

func (s *Sequence) GetField(item ItemID, field string) ([]byte, bool)

GetField reads one of an item's own fields.

func (*Sequence) IndexOf added in v0.21.0 

func (s *Sequence) IndexOf(item ItemID) int

IndexOf returns where an item sits, or -1 if it is not there.

func (*Sequence) Insert added in v0.21.0 

func (s *Sequence) Insert(after ItemID, value []byte) (ItemID, []crdt.MapOp, error)

Insert puts a new item holding value after the item named by after, or at the front for SeqStart.

A nil value writes no value at all, which is one operation fewer and is what a sequence whose items are identities rather than contents wants — the axes of a Sheet, where the item is the row and the row has no value of its own. It is not the same as an empty value, which is written.

func (*Sequence) Items added in v0.21.0 

func (s *Sequence) Items() []ItemID

Items returns every item, in order.

func (*Sequence) Len added in v0.21.0 

func (s *Sequence) Len() int

Len returns how many items there are.

func (*Sequence) Map added in v0.21.0 

func (s *Sequence) Map() *crdt.Map

Map returns the map underneath, which is what is snapshotted and what operations are applied to.

func (*Sequence) Move added in v0.21.0 

func (s *Sequence) Move(item, after ItemID) (crdt.MapOp, error)

Move puts an item after the item named by after, or at the front for SeqStart. It is one operation: an item's place is one field.

func (*Sequence) OpsSince added in v0.21.0 

func (s *Sequence) OpsSince(vv crdt.VersionVector) []crdt.MapOp

OpsSince returns the operations a peer at vv has not seen.

func (*Sequence) Records added in v0.21.0 

func (s *Sequence) Records() *RecordMap

Records returns the record map underneath, for reading an item's own fields.

func (*Sequence) Remove added in v0.21.0 

func (s *Sequence) Remove(item ItemID) ([]crdt.MapOp, error)

Remove takes an item out.

func (*Sequence) Set added in v0.21.0 

func (s *Sequence) Set(item ItemID, value []byte) (crdt.MapOp, error)

Set replaces what an item holds.

func (*Sequence) SetField added in v0.21.0 

func (s *Sequence) SetField(item ItemID, field string, value []byte) (crdt.MapOp, error)

SetField sets one of an item's own fields, beside what it holds.

func (*Sequence) Snapshot added in v0.21.0 

func (s *Sequence) Snapshot() []byte

Snapshot returns the sequence as bytes.

func (*Sequence) Value added in v0.21.0 

func (s *Sequence) Value(item ItemID) ([]byte, bool)

Value returns what an item holds, and whether the item exists.

func (*Sequence) Values added in v0.21.0 

func (s *Sequence) Values() [][]byte

Values returns what every item holds, in order.

func (*Sequence) Version added in v0.21.0 

func (s *Sequence) Version() crdt.VersionVector

Version returns what this replica has seen.

type Set added in v0.29.0 

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

A Set is a collection of names any number of replicas may add to and take from at once: the labels on a card, the people in a conversation, the layers that are showing, the tags on a document.

Why a map of flags is not one

The obvious way to share a set is a crdt.Map keyed by the name, holding a flag or nothing at all. It converges, and the case it converges badly on is the one that happens: Ada adds "urgent" while Grace, who has never seen it, takes it away. Both wrote the same key, so one of the two writes wins by the (clock, site) order — and which one is nothing to do with what either of them knew. Grace can remove a label she has never been shown.

How this one works

Every addition mints a tag of its own, and a name is in the set while it has at least one tag. Removing a name takes away the tags this replica can see, which is the removal that was actually asked for: these ones, the ones the person was looking at.

A tag nobody has seen is untouched by that, so an addition concurrent with a removal survives it. This is usually stated as a policy — "add wins" — and it is better read as the absence of one. A removal says what it observed. There is no rule here about an addition it did not observe, because there is nothing to base one on: neither replica knew about the other, and inventing a winner would be inventing knowledge.

It is a RecordMap with the fields used as tags and never written twice, so the merging is the map's, unchanged: a record exists while it has a live field, and a field written after a deletion it did not see re-establishes it.

What it costs

One map entry per addition that has not been removed, and — because a tag is an identity, and an identity here is the identity of an operation — two operations per addition rather than one. Adding a name that is already there mints another tag rather than doing nothing, and it has to: a removal still on its way would otherwise take the name away, having seen every tag it had.

Example

A Set is a collection of names, where a removal takes away what it saw and nothing else. Here two replicas edit the labels on a card at the same moment: Grace clears the labels she has been shown while Ada adds one Grace has never seen, and the new label survives — which a map keyed by the label would have settled by an order that has nothing to do with what either knew. 

package main

import (
	"fmt"

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

func main() {
	ada, grace := structured.NewSet(1), structured.NewSet(2)

	shared, _ := ada.Add("draft")
	grace.Apply(shared...)

	// Offline: Ada labels it urgent, Grace clears what she can see.
	added, _ := ada.Add("urgent")
	removed, _ := grace.Remove("draft")

	ada.Apply(removed...)
	grace.Apply(added...)

	fmt.Println(grace.Names())
	fmt.Println(grace.Adders("urgent"))
}

Output:
[urgent]
[1]

func LoadSet added in v0.29.0 

func LoadSet(site crdt.SiteID, snapshot []byte) (*Set, error)

LoadSet rebuilds a set from a snapshot, to be edited as site.

func NewSet added in v0.29.0 

func NewSet(site crdt.SiteID) *Set

NewSet returns an empty set this site can edit.

func SetOf added in v0.29.0 

func SetOf(m *crdt.Map) *Set

SetOf reads a map as a set, for a map that is a part of a crdt.Composite.

func (*Set) Add added in v0.29.0 

func (s *Set) Add(name string) ([]crdt.MapOp, error)

Add puts a name in the set.

It is two operations: one to mint the tag, which has to be an identity no replica can mint twice, and one to write it. Both must reach a peer, or the name arrives with a tag that replica could mint again after a reload.

Adding a name that is already there is not nothing. It mints another tag, because a removal still on its way has seen every tag the name had, and would otherwise take it away.

func (*Set) Adders added in v0.29.0 

func (s *Set) Adders(name string) []crdt.SiteID

Adders returns the replicas whose additions of a name are still standing, in order and without repetition. It is what "who put this label on" asks, and it is free: a tag is the identity of the operation that minted it, and an identity carries its site.

A name held only by tags this version cannot read returns nothing, which is the same answer as a name nobody added.

func (*Set) Apply added in v0.29.0 

func (s *Set) Apply(ops ...crdt.MapOp) error

Apply integrates operations from peers, tolerating duplicates and reordering.

func (*Set) Contains added in v0.29.0 

func (s *Set) Contains(name string) bool

Contains reports whether a name is in the set.

func (*Set) Len added in v0.29.0 

func (s *Set) Len() int

Len returns how many names are in the set.

func (*Set) Map added in v0.29.0 

func (s *Set) Map() *crdt.Map

Map returns the map underneath, which is what is snapshotted and what operations are applied to.

func (*Set) Names added in v0.29.0 

func (s *Set) Names() []string

Names returns everything in the set, in order, so that two replicas holding the same set list it the same way.

func (*Set) OpsSince added in v0.29.0 

func (s *Set) OpsSince(vv crdt.VersionVector) []crdt.MapOp

OpsSince returns the operations this replica holds that vv does not.

func (*Set) Records added in v0.29.0 

func (s *Set) Records() *RecordMap

Records returns the record map underneath, for a caller that wants to read the tags themselves.

func (*Set) Remove added in v0.29.0 

func (s *Set) Remove(name string) ([]crdt.MapOp, error)

Remove takes a name out of the set, by taking away the tags this replica can see. A tag added concurrently, which this replica has not seen, is not one of them and the name stays.

A name that is not in the set is ErrNoChange rather than a silent nothing, so a caller never has to decide whether an empty batch is safe to send.

func (*Set) Site added in v0.29.0 

func (s *Set) Site() crdt.SiteID

Site returns the replica this set edits as.

func (*Set) Snapshot added in v0.29.0 

func (s *Set) Snapshot() []byte

Snapshot encodes the whole set, for a joining peer or for persistence.

func (*Set) Tags added in v0.29.0 

func (s *Set) Tags(name string) int

Tags returns how many additions of a name are still standing. Two is two replicas that added it without seeing each other, or one replica that added it twice — and it is what a removal will have to take away.

func (*Set) Version added in v0.29.0 

func (s *Set) Version() crdt.VersionVector

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

type Sheet 

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

A Sheet is a collaborative spreadsheet: rows and columns are two ordered collections of stable identities, and cells are a map keyed by a (row, column) identity pair. Editing it produces operations that any number of replicas may exchange, offline and in any order, and every replica converges to the same sheet.

It is one crdt.Composite — the same core a Diagram is — so it borrows the crdt package's convergence rather than restating it. What this type adds is the addressing: a cell named by the identities of its row and column, so that a concurrent change to the sheet's shape leaves every other cell, and every formula reference, exactly where it was.

Why the axes are sequences and not lists

They were crdt.List — an RGA — and a row could then be added and removed but not moved. Dragging a row to another place had to be written as a delete and an insert, which is two operations, and a second replica dragging the same row at the same time splits them: the row ends up twice over, or not at all, and its cells follow whichever copy survives.

Sequence carries a row's place as a rank, so moving one is a single write and two replicas moving the same row are two writes to one field — a conflict crdt.Map already settles. The identity is untouched by a move, so the cells and every formula reference come with it for free.

A Sheet is not safe for concurrent use. Construct one with NewSheet or LoadSheet.

Example

A spreadsheet and a diagram are two thin wrappers over one collaborative core. Here two replicas of a sheet edit two different cells while disconnected, then exchange operations and converge — the same merge a Diagram would use. 

package main

import (
	"fmt"

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

func main() {
	ada, grace := structured.NewSheet(1), structured.NewSheet(2)

	// Ada lays out a row and a column and shares them.
	row, r1, _ := ada.AppendRow()
	col, r2, _ := ada.AppendCol()
	grace.Apply(r1, r2)

	// Offline, each writes a different cell.
	fromAda, _ := ada.SetCell(row, col, structured.Literal("42"))
	other, _, _ := grace.AppendRow()
	fromGrace, _ := grace.SetCell(other, col, structured.Literal("7"))

	// They swap operations, in either order, and agree.
	ada.Apply(fromGrace)
	grace.Apply(fromAda)

	cell, _ := grace.GetCell(row, col)
	fmt.Println(cell.Text, len(grace.Rows()))
}

Output:
42 2

func LoadSheet 

func LoadSheet(site crdt.SiteID, snapshot []byte) (*Sheet, error)

LoadSheet rebuilds a sheet from a snapshot, to be edited as site.

func NewSheet 

func NewSheet(site crdt.SiteID) *Sheet

NewSheet returns an empty sheet that issues operations as site. Every replica editing a sheet concurrently must pass a distinct crdt.SiteID.

func (*Sheet) AppendCol 

func (s *Sheet) AppendCol() (ColID, crdt.PartOps, error)

AppendCol adds a column after the last and returns its identity and the operations to broadcast.

func (*Sheet) AppendRow 

func (s *Sheet) AppendRow() (RowID, crdt.PartOps, error)

AppendRow adds a row after the last and returns its identity and the operations to broadcast.

func (*Sheet) Apply 

func (s *Sheet) Apply(batches ...crdt.PartOps) error

Apply integrates batches of operations from peers, tolerating duplicates and reordering exactly as the underlying parts do.

func (*Sheet) ClearCell 

func (s *Sheet) ClearCell(row RowID, col ColID) (crdt.PartOps, error)

ClearCell removes the cell at the intersection of row and col and returns the operation to broadcast.

func (*Sheet) ColCount 

func (s *Sheet) ColCount() int

ColCount returns the number of columns present.

func (*Sheet) Cols 

func (s *Sheet) Cols() []ColID

Cols returns the identities of the columns present, in order.

func (*Sheet) DeleteCol 

func (s *Sheet) DeleteCol(pos int) (crdt.PartOps, error)

DeleteCol removes the column at index pos and returns the operations to broadcast, on the same terms as Sheet.DeleteRow.

func (*Sheet) DeleteRow 

func (s *Sheet) DeleteRow(pos int) (crdt.PartOps, error)

DeleteRow removes the row at index pos and returns the operations to broadcast. The cells of a removed row are left in place, unreferenced by any live row, so they neither show through Sheet.Rows nor cost a second batch to remove.

func (*Sheet) GetCell 

func (s *Sheet) GetCell(row RowID, col ColID) (Cell, bool)

GetCell returns the cell at the intersection of row and col and whether one is set. A cell whose stored bytes are not a cell this package wrote — which a peer may inject — reads as absent.

func (*Sheet) InsertCol 

func (s *Sheet) InsertCol(pos int) (ColID, crdt.PartOps, error)

InsertCol adds a column at index pos and returns its identity and the operations to broadcast.

func (*Sheet) InsertRow 

func (s *Sheet) InsertRow(pos int) (RowID, crdt.PartOps, error)

InsertRow adds a row at index pos and returns its identity and the operations to broadcast. pos may equal Sheet.RowCount, which appends.

func (*Sheet) MoveCol added in v0.22.0 

func (s *Sheet) MoveCol(from, to int) (crdt.PartOps, error)

MoveCol moves the column at index from to index to, on the same terms as Sheet.MoveRow.

func (*Sheet) MoveRow added in v0.22.0 

func (s *Sheet) MoveRow(from, to int) (crdt.PartOps, error)

MoveRow moves the row at index from to index to, and returns the operation to broadcast. It is one operation: a row's place is one field.

The row keeps its identity, so its cells and every formula naming them come with it and nothing else in the sheet moves.

func (*Sheet) OpsSince 

func (s *Sheet) OpsSince(v crdt.CompositeVersion) ([]crdt.PartOps, error)

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.

func (*Sheet) Pending 

func (s *Sheet) Pending() int

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

func (*Sheet) RowCount 

func (s *Sheet) RowCount() int

RowCount returns the number of rows present.

func (*Sheet) Rows 

func (s *Sheet) Rows() []RowID

Rows returns the identities of the rows present, in order. Two replicas holding the same operations return the same slice.

func (*Sheet) SetCell 

func (s *Sheet) SetCell(row RowID, col ColID, cell Cell) (crdt.PartOps, error)

SetCell writes cell at the intersection of row and col and returns the operation to broadcast. The cell is addressed by identity, so the write lands on the same cell on every replica however the sheet's shape has changed.

func (*Sheet) Site 

func (s *Sheet) Site() crdt.SiteID

Site returns the replica identity this sheet issues operations as.

func (*Sheet) Snapshot 

func (s *Sheet) Snapshot() []byte

Snapshot encodes the whole sheet, for a joining peer or for persistence. Two replicas holding the same operations produce identical bytes.

func (*Sheet) Version 

func (s *Sheet) Version() crdt.CompositeVersion

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

type Span added in v0.23.0 

type Span struct {
	// Pos is where the stretch starts, in visible characters.
	Pos int
	// Text is what it holds.
	Text string
	// Marks is the formatting covering all of it, by name. A mark with no value
	// of its own — bold — has a nil value; a mark that carries one — a colour,
	// the target of a link — has it here.
	Marks map[string][]byte
}

A Span is a stretch of the text over which the formatting does not change.

type State added in v0.30.0 

type State uint8

A State is what has become of a proposal. 

const (
	// Open is a proposal nobody has decided about.
	Open State = iota
	// Accepted is a proposal whose operations are in the document.
	Accepted
	// Withdrawn is a proposal somebody took back or turned down.
	Withdrawn
)

func (State) String added in v0.30.0 

func (s State) String() string

String renders the state for diagnostics.

type StrokeID added in v0.25.0 

type StrokeID = ItemID

A StrokeID names a stroke. It is a Sequence item, so the sequence's own ordering and fields apply to it.

type Tree added in v0.20.0 

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

A Tree is a collaborative tree whose nodes can be moved: a file tree, the outline of a document, the grouping of a diagram, a thread of replies.

Why moving is the whole problem

Every other structure here is a map of records, and a tree could be one too: a node is a record, and one of its fields names its parent. That much merges on its own, because a parent is a single value and Register already says how two replicas that write one at the same time agree.

What does not merge on its own is the shape. Two replicas can each move a node under the other, and each move is fine by itself: A under B is a tree, B under A is a tree, both together are a ring floating free of the root. Nothing in the operations is wrong, and no amount of ordering them differently helps — the pair is what is wrong, and it only exists once they meet.

The same is true of deleting: one replica removes a folder while another moves a file into it, and neither operation is in conflict with the other, but the file is now under a node that is not there.

How this one answers

Both are answered when the tree is read rather than when an operation is applied, by rules that are a function of the state alone. Every replica holding the same state reads the same tree out of it, whatever order the operations arrived in, which is what convergence asks for:

  • A node whose parent is not a live node is read as a child of the root. So deleting a folder does not delete a file a peer concurrently moved into it; the file resurfaces. That direction is deliberate: a tree that loses work to a concurrent delete cannot be trusted with a project.

  • A node that cannot reach the root is in a ring, or below one. The ring is broken at the node whose parent was written last, by the same (clock, site) order the map underneath resolves writes by — the move that arrived into an already-moved tree is the one that gives way — and that node is read as a child of the root.

Neither rule discards an operation. The state keeps every move that was ever made, and a later move can put back what a ring detached; what the rules decide is only what the tree looks like now.

Where a node sits among its siblings

A node carries its order as a rank rather than living in a list per parent; see rank.go for why that is a single field write and a list would not be. Siblings are read in order of (rank, identity), which is total, so two replicas read the same order.

func LoadTree added in v0.20.0 

func LoadTree(site crdt.SiteID, snapshot []byte) (*Tree, error)

LoadTree reads a snapshot back, as the given site.

func NewTree added in v0.20.0 

func NewTree(site crdt.SiteID) *Tree

NewTree returns an empty tree this site can edit.

func TreeOf added in v0.20.0 

func TreeOf(m *crdt.Map) *Tree

TreeOf reads a map as a tree, for a map that is a part of a crdt.Composite.

func (*Tree) Apply added in v0.20.0 

func (t *Tree) Apply(ops ...crdt.MapOp) error

Apply takes operations from a peer.

func (*Tree) Children added in v0.20.0 

func (t *Tree) Children(parent TreeID) []TreeID

Children returns the children of a node, in order. Passing the root returns the nodes at the top of the tree.

func (*Tree) Depth added in v0.20.0 

func (t *Tree) Depth(node TreeID) (int, bool)

Depth returns how far a node is below the root, the top of the tree being depth one, and whether the node exists.

func (*Tree) GetField added in v0.20.0 

func (t *Tree) GetField(node TreeID, field string) ([]byte, bool)

GetField reads one of a node's own fields.

func (*Tree) Insert added in v0.20.0 

func (t *Tree) Insert(parent, after TreeID) (TreeID, []crdt.MapOp, error)

Insert adds a node under parent, after the sibling named by after. A root TreeID for after puts it first.

It returns the new node's identity and the operations that made it.

func (*Tree) Map added in v0.20.0 

func (t *Tree) Map() *crdt.Map

Map returns the map underneath, which is what is snapshotted and what operations are applied to.

func (*Tree) Move added in v0.20.0 

func (t *Tree) Move(node, parent, after TreeID) ([]crdt.MapOp, error)

Move puts node under parent, after the sibling named by after. A root TreeID for after puts it first.

Moving a node under itself or under one of its own descendants is refused here, because a replica can see that it is about to make a ring and there is no reason to make one. It is only when two replicas each make a legal move that a ring can appear, and that is what reading the tree resolves.

func (*Tree) Nodes added in v0.20.0 

func (t *Tree) Nodes() []TreeID

Nodes returns every node in the tree, in depth-first order from the root, which is the order a file tree or an outline is read in.

func (*Tree) OpsSince added in v0.20.0 

func (t *Tree) OpsSince(vv crdt.VersionVector) []crdt.MapOp

OpsSince returns the operations a peer at vv has not seen.

func (*Tree) Parent added in v0.20.0 

func (t *Tree) Parent(node TreeID) (TreeID, bool)

Parent returns the node's parent as the tree reads now, and whether the node exists. A node at the top of the tree has the root as its parent, which is reported as a root TreeID and true.

func (*Tree) Records added in v0.20.0 

func (t *Tree) Records() *RecordMap

Records returns the record map underneath, for setting and reading a node's own fields.

func (*Tree) Remove added in v0.20.0 

func (t *Tree) Remove(node TreeID) ([]crdt.MapOp, error)

Remove deletes a node. Its children are read as children of the root, by the rule this type states: a concurrent move into a node being deleted keeps what was moved.

RemoveSubtree is what deleting a folder and its contents means.

func (*Tree) RemoveSubtree added in v0.20.0 

func (t *Tree) RemoveSubtree(node TreeID) ([]crdt.MapOp, error)

RemoveSubtree deletes a node and everything under it, as the tree reads now.

func (*Tree) SetField added in v0.20.0 

func (t *Tree) SetField(node TreeID, field string, value []byte) (crdt.MapOp, error)

SetField sets one of a node's own fields.

func (*Tree) Snapshot added in v0.20.0 

func (t *Tree) Snapshot() []byte

Snapshot returns the tree as bytes.

func (*Tree) Version added in v0.20.0 

func (t *Tree) Version() crdt.VersionVector

Version returns what this replica has seen.

type TreeID added in v0.20.0 

type TreeID crdt.ID

A TreeID names a node.

func (TreeID) IsRoot added in v0.20.0 

func (t TreeID) IsRoot() bool

IsRoot reports whether t names the root rather than a node.

func (TreeID) String added in v0.20.0 

func (t TreeID) String() string

String returns the identity in the form the rest of this package prints one.

type Undo added in v0.26.0 

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

An Undo puts back what this replica did, and only what this replica did.

Why a stack of edits is not enough

Undo in a document one person is editing is a stack of states: keep the old one, put it back. That is wrong here, and quietly so. Between making an edit and undoing it, other people have been editing too — their work is in the document, and restoring a remembered state would throw it away. Worse, an undo that replaced the document would travel to them as "the document is now this", and take their work away on their screens as well.

So an undo is not a restoration. It is a new edit, made now, that has the effect of the old one not having happened — and it travels as an ordinary edit, which is why a peer needs no code to receive one.

What that means for what it can promise

  • Undoing an insertion removes those characters, wherever they have since moved to, and however much has been typed around them. They are named by identity, not by where they were.
  • Undoing a removal puts the text back after the character it followed. If somebody has typed at that spot in the meantime, both replicas agree about the order, because the sequence decides it and not this.
  • Undoing something a peer has already undone by other means does nothing, rather than doing it twice.

What it does not promise is that the document returns to a state it was in. It cannot, because that state was never the shared one.

What it records

Edits go through this rather than through the document, because inverting one afterwards is not possible from what the document keeps: a removal has to know the text that went, and a document that has removed it no longer says. Undo.Insert and Undo.Delete take that note as they go.

An Undo is not safe for concurrent use.

func NewUndo added in v0.26.0 

func NewUndo(doc *crdt.Doc) *Undo

NewUndo watches a document. Only the edits made through it are undoable, which is what makes an undo this replica's own and not everybody's.

func (*Undo) Begin added in v0.26.0 

func (u *Undo) Begin()

Begin starts a group: everything until Undo.Commit is put back by one Undo. It is what makes typing a word undo as a word rather than a letter at a time, and the caller decides where a word ends because only the caller knows.

Begin inside a group does nothing, so a caller need not track whether one is open.

func (*Undo) CanRedo added in v0.26.0 

func (u *Undo) CanRedo() bool

func (*Undo) CanUndo added in v0.26.0 

func (u *Undo) CanUndo() bool

CanUndo and CanRedo report whether there is anything to put back or do again.

func (*Undo) Commit added in v0.26.0 

func (u *Undo) Commit()

Commit closes the group. A group that turned out to be empty leaves nothing to undo, so pressing undo afterwards reaches past it to the edit before.

func (*Undo) Delete added in v0.26.0 

func (u *Undo) Delete(pos, count int) ([]crdt.Op, error)

Delete removes count characters from a visible offset and returns the operations to broadcast.

func (*Undo) Doc added in v0.26.0 

func (u *Undo) Doc() *crdt.Doc

Doc returns the document being edited.

func (*Undo) Insert added in v0.26.0 

func (u *Undo) Insert(pos int, text string) ([]crdt.Op, error)

Insert puts text in at a visible offset and returns the operations to broadcast, as crdt.Doc.Insert does.

func (*Undo) Redo added in v0.26.0 

func (u *Undo) Redo() ([]crdt.Op, error)

Redo does again what the last Undo put back. It returns ErrNoChange when there is nothing, which includes after any new edit: making one says what the document is to become, and what Redo was holding is no longer part of it.

func (*Undo) Undo added in v0.26.0 

func (u *Undo) Undo() ([]crdt.Op, error)

Undo puts back the last edit, or the last group, and returns the operations to broadcast. It returns ErrNoChange when there is nothing to put back.

An open group is closed first, so a caller that began one and then asked for an undo gets what it has just done rather than what came before it.

Source Files

View all Source files

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.