crdt

Documentation

Overview

Package crdt is a sequence CRDT for note text (conflict-free replicated document).

Port of server/crdt.py, preserving the on-disk JSON format exactly — existing .grimoire/crdt state and any paired peer must keep working across the switch.

Model: a Logoot/fractional-index sequence CRDT. Every character is an *atom* with a globally-unique, totally-ordered identifier

id = (key, site, clock)

where key is a fractional-index digit path (a slice of ints) that densely orders atoms, and (site, clock) makes the id unique and breaks ties between concurrent inserts. Deletes are tombstones; document state is the set of live atoms.

Merge is a state-based join (union of atoms, union of tombstones, minus any tombstoned atom). That join is commutative, associative and idempotent, so all replicas seeing the same edits converge to identical text regardless of arrival order.

Index

• Constants
• func KeyBetween(a, b []int) []int
• type Doc
  • func FromJSON(data, site string) (*Doc, error)
  • func FromText(text, site string) *Doc
  • func New(site string) *Doc
  • func (d *Doc) LocalEdit(newText string)
  • func (d *Doc) Merge(other *Doc) *Doc
  • func (d *Doc) Text() string
  • func (d *Doc) ToJSON() string
• type ID

Constants

const Base = 1 << 16

Base is the digit radix for fractional keys.

Functions

func KeyBetween

func KeyBetween(a, b []int) []int

KeyBetween returns a fractional key strictly between keys a and b (a < b). Keys compare lexicographically; a shorter key that is a prefix of a longer one sorts first (missing digit = -1 lower bound).

Types

type Doc

type Doc struct {
	Site  string
	Clock int
	// contains filtered or unexported fields
}

Doc is a replicated text document. Site identifies this replica.

func FromJSON

func FromJSON(data, site string) (*Doc, error)

FromJSON parses a serialized document. Field order and escaping are irrelevant here — only the values matter — so documents written by any version or implementation load.

func FromText

func FromText(text, site string) *Doc

FromText builds a document from an initial string.

func New

func New(site string) *Doc

func (*Doc) LocalEdit

func (d *Doc) LocalEdit(newText string)

LocalEdit reconciles a full-text replacement (from a file or editor) into CRDT operations.

func (*Doc) Merge

func (d *Doc) Merge(other *Doc) *Doc

Merge is the CRDT join: union of atoms and tombstones, minus anything the union of tombstones covers.

func (*Doc) Text

func (d *Doc) Text() string

Text renders the live atoms in order.

func (*Doc) ToJSON

func (d *Doc) ToJSON() string

ToJSON serializes in canonical order: identical document state must produce identical bytes, so the on-disk file doesn't churn and any implementation can reproduce it. Ordering is not semantic — FromJSON rebuilds the same state either way.

The encoding deliberately matches Python's json.dumps(ensure_ascii=True, separators=(",", ":")) byte for byte, so switching implementations doesn't rewrite every CRDT file with different escaping.

type ID

type ID struct {
	Key   []int
	Site  string
	Clock int
}

ID identifies one atom. Key is the fractional index path.