list

package
v1.0.36 Latest Latest
Warning

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

 Go to latest Published: Aug 3, 2026 License: MIT Imports: 10 Imported by: 0

Documentation

Overview

Package list implements a generic, ordered Replicated Growable Array (RGA).

Each position holds one canonical caller-coded value. Positions, rather than offsets, are replicated, so duplicate and out-of-order delivery converge.

Index

Constants

View Source 
const MoveSemanticsVersion uint64 = crdt.SemanticsVersionMoveRGA

MoveSemanticsVersion is the immutable contract for the move-capable list. It is intentionally distinct from the insert/delete-only list RGA version.

View Source 
const SemanticsVersion uint64 = crdt.SemanticsVersionListRGA

SemanticsVersion is the immutable generic list RGA v1 contract. It must match the value negotiated in a replica manifest.

Variables

View Source 
var (
	ErrNilList          = errors.New("list: nil RGA")
	ErrInvalidReplica   = errors.New("list: invalid replica ID")
	ErrInvalidCodec     = errors.New("list: invalid element codec")
	ErrRange            = errors.New("list: range outside visible list")
	ErrInvalidDelta     = errors.New("list: invalid RGA delta")
	ErrTagConflict      = errors.New("list: conflicting node for one tag")
	ErrIncompleteState  = errors.New("list: incomplete RGA state")
	ErrResourceLimit    = errors.New("list: RGA resource limit exceeded")
	ErrUnsafeCompaction = errors.New("list: unsafe RGA tombstone compaction")
)

Functions

func MoveFrameType added in v1.0.26 

func MoveFrameType() crdt.FrameType

MoveFrameType returns the framed protocol a manifest must negotiate for a MoveRGA document. It is not interchangeable with StableFrameType, which describes the insert/delete-only generic list RGA.

func StableFrameType added in v1.0.25 

func StableFrameType() crdt.FrameType

StableFrameType returns the stable generic list RGA v1 state/delta pair.

Types

type Delta 

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

Delta is an opaque, joinable partial list state. It is constructed by local mutations or bounded frame decoding only.

func UnmarshalDelta 

func UnmarshalDelta[T any](data []byte, codec ElementCodec[T]) (Delta, error)

UnmarshalDelta decodes a bounded canonical list delta for codec.

func UnmarshalDeltaWithLimits 

func UnmarshalDeltaWithLimits[T any](data []byte, codec ElementCodec[T], limits frame.DecoderLimits) (Delta, error)

UnmarshalDeltaWithLimits decodes a bounded canonical list delta for codec.

func (Delta) MarshalBinary 

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

MarshalBinary returns one canonical list delta frame.

func (Delta) MarshalBinaryWithLimits 

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

MarshalBinaryWithLimits returns a canonical bounded list delta frame.

type ElementCodec 

type ElementCodec[T any] interface {
	ID() string
	Marshal(T) ([]byte, error)
	Unmarshal([]byte) (T, error)
}

ElementCodec defines one application value's canonical wire representation. Marshal must encode semantically equal values identically. The RGA verifies every locally created and remotely decoded value by a decode/re-encode round trip before it can enter replicated state.

type MoveDelta added in v1.0.25 

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

MoveDelta is an opaque, joinable partial MoveRGA state. Local operations and the bounded decoder are its only constructors.

func UnmarshalMoveDelta added in v1.0.25 

func UnmarshalMoveDelta[T any](data []byte, codec ElementCodec[T]) (MoveDelta, error)

UnmarshalMoveDelta decodes a bounded canonical move-sequence delta.

func UnmarshalMoveDeltaWithLimits added in v1.0.25 

func UnmarshalMoveDeltaWithLimits[T any](data []byte, codec ElementCodec[T], limits frame.DecoderLimits) (MoveDelta, error)

UnmarshalMoveDeltaWithLimits decodes a bounded canonical move-sequence delta and verifies that every application value round-trips canonically.

func (MoveDelta) MarshalBinary added in v1.0.25 

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

func (MoveDelta) MarshalBinaryWithLimits added in v1.0.25 

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

type MoveRGA added in v1.0.25 

type MoveRGA[T any] struct {
	// contains filtered or unexported fields
}

MoveRGA is a move-capable, generic sequence CRDT. It is intentionally a different protocol from RGA: existing List RGA frames retain their immutable insert/delete-only semantics.

Element identities are immutable. A move writes a per-element placement register whose HLC operation ID provides last-writer-wins conflict resolution. Concurrent moves can create an attachment cycle; projection deterministically drops the lower-priority cycle-closing attachment instead of mutating shared state. Therefore replicas converge without pretending that every concurrent intent can be satisfied simultaneously.

func NewMoveRGA added in v1.0.25 

func NewMoveRGA[T any](replicaID string, codec ElementCodec[T]) (*MoveRGA[T], error)

NewMoveRGA constructs a move-capable sequence using conservative defaults.

func NewMoveRGAFromClockWithOptions added in v1.0.25 

func NewMoveRGAFromClockWithOptions[T any](state clock.State, codec ElementCodec[T], options Options) (*MoveRGA[T], error)

NewMoveRGAFromClockWithOptions restores a replica clock that was persisted atomically with a MoveRGA snapshot.

func NewMoveRGAFromSnapshot added in v1.0.25 

func NewMoveRGAFromSnapshot[T any](saved snapshot.Snapshot, codec ElementCodec[T]) (*MoveRGA[T], error)

func NewMoveRGAWithOptions added in v1.0.25 

func NewMoveRGAWithOptions[T any](replicaID string, codec ElementCodec[T], options Options) (*MoveRGA[T], error)

NewMoveRGAWithOptions constructs a move-capable sequence with explicit retained-state limits.

func (*MoveRGA[T]) Append added in v1.0.25 

func (r *MoveRGA[T]) Append(values []T) (MoveDelta, error)

Append appends values to the current visible tail.

func (*MoveRGA[T]) ApplyDelta added in v1.0.25 

func (r *MoveRGA[T]) ApplyDelta(delta MoveDelta) error

ApplyDelta atomically joins a bounded, validated MoveRGA delta.

func (*MoveRGA[T]) ClockState added in v1.0.25 

func (r *MoveRGA[T]) ClockState() clock.State

ClockState returns the HLC state that must be persisted with a snapshot.

func (*MoveRGA[T]) Delete added in v1.0.25 

func (r *MoveRGA[T]) Delete(offset, count int) (MoveDelta, error)

Delete tombstones count visible elements starting at offset. Tombstones retain their placement identity until the same application-level checkpoint and acknowledgement lifecycle used by other structural sequences permits GC.

func (*MoveRGA[T]) Insert added in v1.0.25 

func (r *MoveRGA[T]) Insert(offset int, values []T) (MoveDelta, error)

Insert inserts values before offset. Each value receives a permanent identity; later Move calls relocate that identity rather than cloning it.

func (*MoveRGA[T]) MarshalBinary added in v1.0.25 

func (r *MoveRGA[T]) MarshalBinary() ([]byte, error)

MarshalBinary returns a complete canonical MoveRGA state frame. A complete snapshot rejects missing node/move dependencies rather than silently losing an out-of-order operation.

func (*MoveRGA[T]) MarshalBinaryWithClockState added in v1.0.25 

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

func (*MoveRGA[T]) MarshalBinaryWithLimits added in v1.0.25 

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

func (*MoveRGA[T]) Merge added in v1.0.25 

func (r *MoveRGA[T]) Merge(other *MoveRGA[T]) error

Merge joins the complete state of other. Both lists must use the same codec.

func (*MoveRGA[T]) Move added in v1.0.25 

func (r *MoveRGA[T]) Move(from, count, to int) (MoveDelta, error)

Move relocates count elements beginning at from. to is an offset in the visible list after the selected range has been removed, so Move(2, 1, 0) moves the third item to the front. A single operation tag and rank preserve the moved block's order under concurrent delivery.

Besides the selected range, a move rewrites the visible suffix that followed it. RGA insertions commonly form a parent chain; only moving the selected nodes would otherwise pull descendants from that suffix along with them. Reattaching the suffix as a chain at the former predecessor performs the required sequence splice while retaining every element's immutable identity.

func (*MoveRGA[T]) Positions added in v1.0.25 

func (r *MoveRGA[T]) Positions() []Position

Positions returns permanent identities in current visible order.

func (*MoveRGA[T]) SnapshotCurrentState added in v1.0.25 

func (r *MoveRGA[T]) SnapshotCurrentState() (snapshot.Snapshot, error)

func (*MoveRGA[T]) State added in v1.0.25 

func (r *MoveRGA[T]) State() crdt.StateSnapshot

State reports immutable diagnostic metadata only.

func (*MoveRGA[T]) UnmarshalBinary added in v1.0.25 

func (r *MoveRGA[T]) UnmarshalBinary(data []byte) error

func (*MoveRGA[T]) UnmarshalBinaryWithLimits added in v1.0.25 

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

func (*MoveRGA[T]) Values added in v1.0.25 

func (r *MoveRGA[T]) Values() ([]T, error)

Values returns a fresh decoded visible projection.

type Options 

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

Options bounds retained list state. Applications receiving untrusted peers should set a group-appropriate bound rather than rely on process memory.

func DefaultOptions 

func DefaultOptions() Options

DefaultOptions returns conservative per-list retention limits.

type Position 

type Position = crdt.Tag

Position is a stable, opaque list-element identity.

type RGA 

type RGA[T any] struct {
	// contains filtered or unexported fields
}

RGA is a generic collaborative list. Deletion retains a structural tombstone: an element deleted before its insertion arrives remains hidden when that insertion is eventually delivered.

func New 

func New[T any](replicaID string, codec ElementCodec[T]) (*RGA[T], error)

New constructs a list with default retention limits.

func NewFromClock 

func NewFromClock[T any](state clock.State, codec ElementCodec[T]) (*RGA[T], error)

NewFromClock restores a replica clock with default list limits.

func NewFromClockWithOptions 

func NewFromClockWithOptions[T any](state clock.State, codec ElementCodec[T], options Options) (*RGA[T], error)

NewFromClockWithOptions restores a replica clock. Persist its state atomically with a complete list snapshot before reusing a replica ID.

func NewFromSnapshot 

func NewFromSnapshot[T any](saved snapshot.Snapshot, codec ElementCodec[T]) (*RGA[T], error)

NewFromSnapshot restores a complete HLC-backed list snapshot.

func NewFromSnapshotWithOptions 

func NewFromSnapshotWithOptions[T any](saved snapshot.Snapshot, codec ElementCodec[T], options Options, limits frame.DecoderLimits) (*RGA[T], error)

NewFromSnapshotWithOptions restores a complete snapshot within caller retention and decoder limits.

func NewWithOptions 

func NewWithOptions[T any](replicaID string, codec ElementCodec[T], options Options) (*RGA[T], error)

NewWithOptions constructs a list with explicit retained-state limits.

func (*RGA[T]) Append 

func (r *RGA[T]) Append(values []T) (Delta, error)

Append adds values after the current visible tail.

func (*RGA[T]) ApplyDelta 

func (r *RGA[T]) ApplyDelta(delta Delta) error

ApplyDelta atomically integrates a locally created or decoded delta.

func (*RGA[T]) At 

func (r *RGA[T]) At(offset int) (T, error)

At returns one visible element by offset.

func (*RGA[T]) ClockState 

func (r *RGA[T]) ClockState() clock.State

ClockState returns the HLC state that must be persisted with a snapshot.

func (*RGA[T]) CompactTombstones 

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

CompactTombstones removes exactly requested tombstoned leaves. For replicated state, the caller must first obtain exact authenticated acknowledgements for one epoch, save a post-compaction checkpoint, and retire old deltas. tombstonegc.SimpleCollector may call it only for its documented local-only lifecycle. Any retained child or unresolved dependent blocks the entire request.

func (*RGA[T]) Delete 

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

Delete marks count visible elements starting at offset as removed.

func (*RGA[T]) Insert 

func (r *RGA[T]) Insert(offset int, values []T) (Delta, error)

Insert inserts values before visible element offset. One value becomes one RGA position, even when its canonical encoding is large or multi-byte.

func (*RGA[T]) MarshalBinary 

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

MarshalBinary returns a canonical complete list state frame. Pending out-of-order dependencies are deliberately not serializable as a snapshot.

func (*RGA[T]) MarshalBinaryWithClockState 

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

MarshalBinaryWithClockState returns one complete frame and the HLC state that must be durably stored with it.

func (*RGA[T]) MarshalBinaryWithLimits 

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

MarshalBinaryWithLimits returns a canonical complete list state constrained by caller-selected transport limits.

func (*RGA[T]) Merge 

func (r *RGA[T]) Merge(other *RGA[T]) error

Merge joins every retained node and tombstone from other.

func (*RGA[T]) MissingParents 

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

MissingParents returns unique unresolved parent IDs in canonical order.

func (*RGA[T]) PendingCount 

func (r *RGA[T]) PendingCount() int

PendingCount returns unresolved out-of-order nodes. Any non-zero value prevents a complete state snapshot from being emitted.

func (*RGA[T]) Positions 

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

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

func (*RGA[T]) SnapshotCurrentState 

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

SnapshotCurrentState creates a complete HLC-backed list snapshot.

func (*RGA[T]) State 

func (r *RGA[T]) State() crdt.StateSnapshot

State returns an immutable diagnostic summary that contains no values, positions, clocks, or frame bytes.

func (*RGA[T]) TombstoneTags 

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

TombstoneTags returns every retained deletion identity in canonical order. It is an exact-acknowledgement input, never proof of safe collection.

func (*RGA[T]) UnmarshalBinary 

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

UnmarshalBinary validates a full list state before atomically replacing r.

func (*RGA[T]) UnmarshalBinaryWithLimits 

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

UnmarshalBinaryWithLimits validates a bounded full state before atomically replacing r. It refuses incomplete states and non-canonical values.

func (*RGA[T]) Values 

func (r *RGA[T]) Values() ([]T, error)

Values returns a fresh decoded projection in visible order.

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.