text

package
v1.0.19-beta.3 Latest Latest
Warning

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

 Go to latest Published: Jul 29, 2026 License: MIT Imports: 10 Imported by: 0

Documentation

Overview

Package text implements a state-based Replicated Growable Array (RGA).

Positions are stable mutation tags, not offsets. Offsets are resolved only for a local edit, which makes duplicate and out-of-order deltas safe.

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrNilText          = errors.New("text: nil RGA")
	ErrInvalidReplicaID = errors.New("text: invalid replica ID")
	ErrInvalidText      = errors.New("text: invalid UTF-8 text")
	ErrRange            = errors.New("text: range outside visible text")
	ErrInvalidDelta     = errors.New("text: invalid RGA delta")
	// ErrIncompleteState indicates a state snapshot contains an unresolved
	// parent reference. Deltas may be partial for out-of-order delivery, but a
	// recoverable state frame must include the complete parent closure.
	ErrIncompleteState = errors.New("text: incomplete RGA state")
	ErrTagConflict     = errors.New("text: conflicting node for one tag")
	// ErrUnsafeCompaction means a tombstone still anchors local or unresolved
	// descendants, so removing it would change RGA ordering or permit a stale
	// insertion to become visible.
	ErrUnsafeCompaction = errors.New("text: unsafe RGA tombstone compaction")
	// ErrResourceLimit indicates that accepting a delta would exceed the
	// receiver's configured in-memory safety limits.
	ErrResourceLimit = errors.New("text: RGA resource limit exceeded")
)
View Source 
var (
	// ErrInvalidSnapshot indicates that a delta base is not a canonical,
	// complete RGA state snapshot in either supported RGA wire format.
	ErrInvalidSnapshot = errors.New("text: invalid RGA snapshot")
	// ErrIncompatibleSnapshot indicates that the current RGA no longer contains
	// state retained by the base checkpoint. A delta can add nodes and
	// tombstones, but cannot express physical removal or resurrection, so the
	// peer must install a newer complete checkpoint instead.
	ErrIncompatibleSnapshot = errors.New("text: RGA snapshot is incompatible with current state")
)

Functions

This section is empty.

Types

type Delta 

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

Delta is a joinable partial RGA state. Nodes and tombstones are deliberately opaque so a malformed delta cannot be assembled by direct field mutation.

func UnmarshalRGADelta 

func UnmarshalRGADelta(data []byte) (Delta, error)

UnmarshalRGADelta decodes one bounded canonical RGA delta frame.

func UnmarshalRGADeltaWithLimits 

func UnmarshalRGADeltaWithLimits(data []byte, limits frame.DecoderLimits) (Delta, error)

func UnmarshalRGARunDelta added in v1.0.6 

func UnmarshalRGARunDelta(data []byte) (Delta, error)

UnmarshalRGARunDelta decodes a bounded run-v2 delta.

func UnmarshalRGARunDeltaWithLimits added in v1.0.19 

func UnmarshalRGARunDeltaWithLimits(data []byte, limits frame.DecoderLimits) (Delta, error)

UnmarshalRGARunDeltaWithLimits decodes a bounded run-v2 delta while enforcing caller-selected input limits.

func (Delta) MarshalBinary 

func (d Delta) MarshalBinary() ([]byte, error)

MarshalBinary returns the canonical framed RGA delta.

func (Delta) MarshalBinaryWithLimits added in v1.0.19 

func (d Delta) MarshalBinaryWithLimits(limits frame.DecoderLimits) ([]byte, error)

MarshalBinaryWithLimits returns the canonical framed RGA delta while enforcing caller-selected frame limits.

func (Delta) MarshalJSON added in v1.0.5 

func (d Delta) MarshalJSON() ([]byte, error)

MarshalJSON returns a diagnostic summary for structured logs. It omits text content, positions, tombstone identities, and clock state.

func (Delta) MarshalRunBinary added in v1.0.6 

func (d Delta) MarshalRunBinary() ([]byte, error)

MarshalRunBinary encodes a delta with compact same-replica parent chains.

func (Delta) MarshalRunBinaryWithLimits added in v1.0.19 

func (d Delta) MarshalRunBinaryWithLimits(limits frame.DecoderLimits) ([]byte, error)

MarshalRunBinaryWithLimits encodes a delta with compact same-replica parent chains while enforcing caller-selected output limits.

func (Delta) Merge 

func (d Delta) Merge(other Delta) (Delta, error)

type Options added in v1.0.6 

type Options struct {
	MaxNodes        int
	MaxTombstones   int
	MaxPendingNodes int
	MaxPendingBytes int
}

Options bounds retained RGA metadata. Values must be positive. The defaults match the maximum element count of one default framed payload while keeping unresolved dependency state substantially smaller than a full document. Applications handling untrusted peers should choose limits appropriate to a replication group instead of relying on process-wide memory availability.

func DefaultOptions added in v1.0.6 

func DefaultOptions() Options

DefaultOptions returns conservative per-RGA retention limits.

type Position 

type Position = crdt.Tag

Position is a stable, opaque identifier for one Unicode scalar value. It remains valid after inserts before it and after it has been deleted.

type RGA 

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

RGA is a collaborative text CRDT. A tombstone retained for a deleted position wins even if it arrives before the corresponding insertion.

func New 

func New(replicaID string) (*RGA, error)

func NewFromClock 

func NewFromClock(state clock.State) (*RGA, error)

func NewFromClockWithOptions added in v1.0.6 

func NewFromClockWithOptions(state clock.State, options Options) (*RGA, error)

NewFromClockWithOptions restores an RGA clock with explicit retention limits. Clock state must be persisted atomically with a complete snapshot before reusing its replica ID.

func NewFromSnapshot 

func NewFromSnapshot(saved snapshot.Snapshot) (*RGA, error)

func NewFromSnapshotWithOptions added in v1.0.19 

func NewFromSnapshotWithOptions(saved snapshot.Snapshot, options Options, limits frame.DecoderLimits) (*RGA, error)

NewFromSnapshotWithOptions restores an RGA snapshot using explicit retained state and frame limits. It validates the full state before installation and witnesses the saved frontier before returning, so a reused replica ID cannot create a tag that predates the recovered state.

func NewWithOptions added in v1.0.6 

func NewWithOptions(replicaID string, options Options) (*RGA, error)

NewWithOptions constructs an RGA with explicit retention limits.

func (*RGA) ApplyDelta 

func (r *RGA) ApplyDelta(delta Delta) error

func (*RGA) ClockState 

func (r *RGA) ClockState() clock.State

func (*RGA) CompactEligibleTombstones added in v1.0.19 

func (r *RGA) CompactEligibleTombstones(tags []Position) (int, error)

CompactEligibleTombstones makes best-effort structural progress through an exact-acknowledged batch. Unlike CompactTombstones, a non-leaf in tags does not block unrelated leaves. Deleted descendants are removed before their deleted ancestors, so a fully deleted chain can compact in one call.

It remains deliberately fail-closed for unresolved state: any pending node returns ErrUnsafeCompaction without changing the RGA. Callers still need an authenticated exact-acknowledgement epoch, a durable post-compaction checkpoint, and retirement of old deltas before using this method.

func (*RGA) CompactTombstones added in v1.0.6 

func (r *RGA) CompactTombstones(tags []Position) (int, error)

CompactTombstones physically removes exactly the requested tombstoned leaf nodes. It is deliberately stricter than OR-Set compaction: an RGA deletion remains a structural anchor while any integrated or pending child refers to it. Call this only after an authenticated, exact-acknowledgement epoch has durably checkpointed a post-compaction snapshot and retired old deltas.

The operation is all-or-nothing. Unknown tags are ignored; invalid tags, unresolved dependencies, non-leaf nodes, or tombstones received before their insertion return ErrUnsafeCompaction without changing the RGA.

func (*RGA) Delete 

func (r *RGA) Delete(offset, count int) (Delta, error)

Delete marks count visible runes starting at offset as removed. The delta carries only tombstones; replicas that have not received the inserts yet retain those tombstones until the matching nodes arrive.

func (*RGA) DeleteBinaryWithLimits added in v1.0.19 

func (r *RGA) DeleteBinaryWithLimits(offset, count int, limits frame.DecoderLimits) ([]byte, error)

DeleteBinaryWithLimits deletes visible text and returns the same preflighted canonical tombstone frame used to establish the local output budget.

func (*RGA) DeleteRunBinaryWithLimits added in v1.0.19 

func (r *RGA) DeleteRunBinaryWithLimits(offset, count int, limits frame.DecoderLimits) ([]byte, error)

DeleteRunBinaryWithLimits deletes visible text and returns the same preflighted run-v2 tombstone frame used to establish the local output budget. Callers must have separately negotiated the run-v2 RGA protocol.

func (*RGA) DeleteWithLimits added in v1.0.19 

func (r *RGA) DeleteWithLimits(offset, count int, limits frame.DecoderLimits) (Delta, error)

DeleteWithLimits deletes visible runes only when the canonical tombstone delta fits limits. A rejected output frame leaves the RGA content and tombstone set unchanged.

func (*RGA) DeltaSince added in v1.0.19 

func (r *RGA) DeltaSince(base snapshot.Snapshot) (Delta, error)

DeltaSince returns the mutations that move a receiver known to contain base toward r's current state. The result includes every required structural ancestor absent from base, so it remains safe when the receiver installs the resulting delta before any later updates.

base is deliberately a validated complete snapshot rather than a map of greatest HLC tags. HLC tags are ordered but not contiguous, so a greatest-tag frontier cannot prove that a receiver has every earlier mutation and could otherwise make a differential update omit data it still needs.

func (*RGA) DeltaSinceBase added in v1.0.19 

func (r *RGA) DeltaSinceBase(base SnapshotBase) (Delta, error)

DeltaSinceBase is DeltaSince with a reusable parsed snapshot base.

func (*RGA) Insert 

func (r *RGA) Insert(offset int, value string) (Delta, error)

Insert inserts valid UTF-8 text before visible rune offset. It creates one node per Unicode scalar, so offset/count are rune based rather than byte based and can never split UTF-8.

func (*RGA) InsertBinaryWithLimits added in v1.0.19 

func (r *RGA) InsertBinaryWithLimits(offset int, value string, limits frame.DecoderLimits) ([]byte, error)

InsertBinaryWithLimits inserts text and returns the same preflighted canonical delta frame used to establish the local output budget.

func (*RGA) InsertRunBinaryWithLimits added in v1.0.19 

func (r *RGA) InsertRunBinaryWithLimits(offset int, value string, limits frame.DecoderLimits) ([]byte, error)

InsertRunBinaryWithLimits inserts text and returns the same preflighted run-v2 delta frame used to establish the local output budget. Callers must have separately negotiated the run-v2 RGA protocol before using this frame.

func (*RGA) InsertWithLimits added in v1.0.19 

func (r *RGA) InsertWithLimits(offset int, value string, limits frame.DecoderLimits) (Delta, error)

InsertWithLimits inserts text only when its complete canonical delta fits limits. A rejected output frame does not add nodes or tombstones to the RGA, which lets a transport-facing caller fail the local edit before it becomes state that cannot be replicated under its own budget. The HLC may still advance while reserving local tags; those un-emitted tags are safe to skip.

func (*RGA) MarshalBinary 

func (r *RGA) MarshalBinary() ([]byte, error)

MarshalBinary returns the canonical framed RGA state.

func (*RGA) MarshalBinaryWithClockState 

func (r *RGA) MarshalBinaryWithClockState() ([]byte, clock.State, error)

func (*RGA) MarshalBinaryWithClockStateAndLimits added in v1.0.19 

func (r *RGA) MarshalBinaryWithClockStateAndLimits(limits frame.DecoderLimits) ([]byte, clock.State, error)

MarshalBinaryWithClockStateAndLimits returns one complete state frame and the HLC state that must be persisted atomically before the replica ID is reused. The frame is constrained by limits.

func (*RGA) MarshalBinaryWithLimits added in v1.0.19 

func (r *RGA) MarshalBinaryWithLimits(limits frame.DecoderLimits) ([]byte, error)

MarshalBinaryWithLimits returns the canonical framed RGA state while enforcing caller-selected frame limits. It refuses incomplete state rather than serializing unresolved parent references.

func (*RGA) MarshalDeltaSince added in v1.0.19 

func (r *RGA) MarshalDeltaSince(base snapshot.Snapshot) ([]byte, error)

MarshalDeltaSince encodes DeltaSince(base) using the matching delta wire protocol for base. The receiver must apply the result to a state that contains base (or a CRDT superset of base).

func (*RGA) MarshalDeltaSinceBase added in v1.0.19 

func (r *RGA) MarshalDeltaSinceBase(base SnapshotBase) ([]byte, error)

MarshalDeltaSinceBase encodes DeltaSinceBase(base) using the matching delta wire protocol and default frame limits. Reuse a SnapshotBase when a peer checkpoint serves multiple anti-entropy rounds.

func (*RGA) MarshalDeltaSinceBaseWithLimits added in v1.0.19 

func (r *RGA) MarshalDeltaSinceBaseWithLimits(base SnapshotBase, limits frame.DecoderLimits) ([]byte, error)

MarshalDeltaSinceBaseWithLimits is MarshalDeltaSinceBase with caller-selected output frame bounds.

func (*RGA) MarshalDeltaSinceWithLimits added in v1.0.19 

func (r *RGA) MarshalDeltaSinceWithLimits(base snapshot.Snapshot, limits frame.DecoderLimits) ([]byte, error)

MarshalDeltaSinceWithLimits is MarshalDeltaSince with caller-selected bounds for both decoding the base snapshot and producing the matching delta frame.

func (*RGA) MarshalJSON added in v1.0.5 

func (r *RGA) MarshalJSON() ([]byte, error)

MarshalJSON returns a diagnostic summary for structured logs. It omits text content, positions, tombstone identities, and clock state.

func (*RGA) MarshalRunBinary added in v1.0.6 

func (r *RGA) MarshalRunBinary() ([]byte, error)

MarshalRunBinary encodes complete RGA state using the separately negotiated run-v2 frame. It retains v1 scalar Positions and is therefore safe to merge with v1 deltas after decoding.

func (*RGA) MarshalRunBinaryWithLimits added in v1.0.19 

func (r *RGA) MarshalRunBinaryWithLimits(limits frame.DecoderLimits) ([]byte, error)

MarshalRunBinaryWithLimits encodes complete RGA state using the run-v2 frame while enforcing caller-selected output limits.

func (*RGA) Merge 

func (r *RGA) Merge(other *RGA) error

func (*RGA) MissingParents added in v1.0.6 

func (r *RGA) MissingParents() []Position

MissingParents returns stable IDs that must arrive before pending nodes can integrate. The returned slice is sorted and safe for callers to retain.

func (*RGA) PendingCount added in v1.0.6 

func (r *RGA) PendingCount() int

PendingCount reports the number of accepted nodes still waiting for a missing parent. It is useful for replication diagnostics and backpressure.

func (*RGA) Positions 

func (r *RGA) Positions() []Position

Positions returns a copy of visible stable IDs in display order.

func (*RGA) Snapshot 

func (r *RGA) Snapshot(frontier map[string]crdt.Tag) (snapshot.Snapshot, error)

func (*RGA) SnapshotCurrentState 

func (r *RGA) SnapshotCurrentState() (snapshot.Snapshot, error)

func (*RGA) SnapshotCurrentStateWithLimits added in v1.0.19 

func (r *RGA) SnapshotCurrentStateWithLimits(limits frame.DecoderLimits) (snapshot.Snapshot, error)

SnapshotCurrentStateWithLimits returns a complete, HLC-backed snapshot while enforcing caller-selected frame limits. Persist the returned snapshot atomically so that state and clock recovery cannot reuse a mutation tag.

func (*RGA) SnapshotRunCurrentState added in v1.0.6 

func (r *RGA) SnapshotRunCurrentState() (snapshot.Snapshot, error)

SnapshotRunCurrentState returns an HLC-backed run-v2 snapshot.

func (*RGA) SnapshotRunCurrentStateWithLimits added in v1.0.19 

func (r *RGA) SnapshotRunCurrentStateWithLimits(limits frame.DecoderLimits) (snapshot.Snapshot, error)

SnapshotRunCurrentStateWithLimits returns an HLC-backed, validated run-v2 snapshot while enforcing caller-selected output limits.

func (*RGA) State 

func (r *RGA) State() crdt.StateSnapshot

func (*RGA) String 

func (r *RGA) String() string

func (*RGA) TombstoneTags added in v1.0.6 

func (r *RGA) TombstoneTags() []Position

TombstoneTags returns every retained deletion tag in canonical order. It is an acknowledgement input, not proof that a tag is safe to collect.

func (*RGA) UnmarshalBinary 

func (r *RGA) UnmarshalBinary(data []byte) error

func (*RGA) UnmarshalBinaryWithLimits 

func (r *RGA) UnmarshalBinaryWithLimits(data []byte, limits frame.DecoderLimits) error

func (*RGA) UnmarshalRunBinary added in v1.0.6 

func (r *RGA) UnmarshalRunBinary(data []byte) error

UnmarshalRunBinary installs one complete run-v2 RGA state frame.

func (*RGA) UnmarshalRunBinaryWithLimits added in v1.0.19 

func (r *RGA) UnmarshalRunBinaryWithLimits(data []byte, limits frame.DecoderLimits) error

UnmarshalRunBinaryWithLimits installs one complete run-v2 RGA state frame while enforcing caller-selected input limits.

type SnapshotBase added in v1.0.19 

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

SnapshotBase is an immutable, decoded complete RGA state that can be reused for repeated differential encodes against the same peer checkpoint. It has no exported mutable state; create it only with NewSnapshotBase.

func NewSnapshotBase added in v1.0.19 

func NewSnapshotBase(saved snapshot.Snapshot) (SnapshotBase, error)

NewSnapshotBase validates and decodes the saved snapshot once so callers that repeatedly synchronize against the same checkpoint do not reparse its full state frame for every delta.

func NewSnapshotBaseWithLimits added in v1.0.19 

func NewSnapshotBaseWithLimits(saved snapshot.Snapshot, limits frame.DecoderLimits) (SnapshotBase, error)

NewSnapshotBaseWithLimits is NewSnapshotBase with caller-selected decoder limits for the supplied checkpoint.

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.