tree

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: 8 Imported by: 0

Documentation

Overview

Package tree implements an observed-remove rooted tree CRDT.

Index

Constants

View Source 
const SemanticsVersion uint64 = crdt.SemanticsVersionORTree

SemanticsVersion is the immutable observed-remove tree v1 contract. It must match the value negotiated in a replica manifest.

Variables

View Source 
var (
	ErrInvalidReplicaID = errors.New("tree: invalid replica ID")
	ErrNilTree          = errors.New("tree: nil OR-Tree")
	ErrUnknownParent    = errors.New("tree: unknown live parent")
	ErrUnknownNode      = errors.New("tree: unknown live node")
	ErrInvalidDelta     = errors.New("tree: invalid delta")
	ErrIncompleteState  = errors.New("tree: incomplete OR-Tree state")
	ErrNodeConflict     = errors.New("tree: conflicting node identity")
	ErrResourceLimit    = errors.New("tree: OR-Tree resource limit exceeded")
	ErrUnsafeCompaction = errors.New("tree: unsafe OR-Tree tombstone compaction")
)

Functions

func StableFrameType added in v1.0.24 

func StableFrameType() crdt.FrameType

StableFrameType returns the stable observed-remove tree state/delta pair. Tree v1 supports immutable parent links with add and observed-remove only; a future move protocol requires a distinct frame pair and semantic version.

Types

type Delta 

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

func UnmarshalDelta 

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

func UnmarshalDeltaWithLimits 

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

func (Delta) MarshalBinary 

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

func (Delta) MarshalBinaryWithLimits added in v1.0.24 

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

MarshalBinaryWithLimits returns a deterministic OR-Tree 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 node values, identities, tombstone identities, and clock state.

func (Delta) Merge 

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

type Node 

type Node struct {
	ID     NodeID
	Parent NodeID
	Value  []byte
}

Node is an immutable visible tree node. Value is always caller-owned.

type NodeID 

type NodeID = crdt.Tag

NodeID is an immutable node-instance identity. The zero ID is the synthetic root.

type ORTree 

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

ORTree supports add and observed-remove. Moving a node is deliberately not an in-place operation: remove it and add a new instance under the new parent.

func New 

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

func NewFromClock 

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

func NewFromClockWithOptions added in v1.0.10 

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

NewFromClockWithOptions restores an OR-Tree clock with explicit retained-state limits. Persist the clock atomically with a complete state before reusing its replica ID.

func NewFromSnapshot 

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

func NewFromSnapshotWithOptions added in v1.0.10 

func NewFromSnapshotWithOptions(saved snapshot.Snapshot, options Options) (*ORTree, error)

NewFromSnapshotWithOptions restores an OR-Tree snapshot while retaining the application's local resource limits. A snapshot is not allowed to widen the receiver's memory budget.

func NewFromSnapshotWithOptionsAndLimits added in v1.0.24 

func NewFromSnapshotWithOptionsAndLimits(saved snapshot.Snapshot, options Options, limits frame.DecoderLimits) (*ORTree, error)

NewFromSnapshotWithOptionsAndLimits restores an OR-Tree snapshot under the caller's retained-state and decoder limits. A snapshot never widens either budget on the recovering replica.

func NewWithOptions added in v1.0.10 

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

NewWithOptions constructs an OR-Tree with explicit retained-state limits.

func (*ORTree) Add 

func (t *ORTree) Add(parent NodeID, value []byte) (NodeID, Delta, error)

func (*ORTree) ApplyDelta 

func (t *ORTree) ApplyDelta(delta Delta) error

func (*ORTree) ClockState 

func (t *ORTree) ClockState() clock.State

func (*ORTree) CompactEligibleTombstones added in v1.0.24 

func (t *ORTree) CompactEligibleTombstones(tags []NodeID) (int, error)

CompactEligibleTombstones makes best-effort structural progress through an exact-acknowledged tombstone batch. It removes deleted descendants before their deleted ancestors, so an entirely deleted tree branch can compact in one call. A retained child that is not part of the batch remains a structural anchor and prevents its parent from being removed.

For replicated state, callers must first authenticate exact acknowledgements for the current membership epoch, durably persist the post-compaction checkpoint, and retire old-epoch frames. tombstonegc.SimpleCollector may use this structural operation only for its documented local-only lifecycle.

func (*ORTree) CompactTombstones added in v1.0.10 

func (t *ORTree) CompactTombstones(tags []NodeID) (int, error)

CompactTombstones removes exactly the requested tombstoned leaf nodes. For replicated state, call it only after the current membership epoch has durably recorded exact acknowledgements, a post-compaction checkpoint, and retirement of old deltas. tombstonegc.SimpleCollector may call it only for its documented local-only lifecycle. Any known child makes a deleted node a structural anchor, so the operation is all-or-nothing for that request.

func (*ORTree) MarshalBinary 

func (t *ORTree) MarshalBinary() ([]byte, error)

MarshalBinary returns a deterministic, bounded framed OR-Tree state.

func (*ORTree) MarshalBinaryWithClockState 

func (t *ORTree) MarshalBinaryWithClockState() ([]byte, clock.State, error)

func (*ORTree) MarshalBinaryWithClockStateAndLimits added in v1.0.24 

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

MarshalBinaryWithClockStateAndLimits returns a complete framed state and the HLC state that must be persisted atomically before reusing the replica ID.

func (*ORTree) MarshalBinaryWithLimits added in v1.0.24 

func (t *ORTree) MarshalBinaryWithLimits(limits frame.DecoderLimits) ([]byte, error)

MarshalBinaryWithLimits returns a deterministic complete OR-Tree state while enforcing caller-selected frame limits.

func (*ORTree) MarshalJSON added in v1.0.5 

func (t *ORTree) MarshalJSON() ([]byte, error)

MarshalJSON returns a diagnostic summary for structured logs. It omits node values, identities, tombstone identities, and clock state.

func (*ORTree) Merge 

func (t *ORTree) Merge(other *ORTree) error

func (*ORTree) Nodes 

func (t *ORTree) Nodes() []Node

Nodes returns visible, root-reachable nodes in canonical preorder.

func (*ORTree) Remove 

func (t *ORTree) Remove(id NodeID) (Delta, error)

func (*ORTree) SnapshotCurrentState 

func (t *ORTree) SnapshotCurrentState() (snapshot.Snapshot, error)

func (*ORTree) SnapshotCurrentStateWithLimits added in v1.0.24 

func (t *ORTree) SnapshotCurrentStateWithLimits(limits frame.DecoderLimits) (snapshot.Snapshot, error)

SnapshotCurrentStateWithLimits returns a validated HLC-backed snapshot while enforcing caller-selected output limits.

func (*ORTree) State 

func (t *ORTree) State() crdt.StateSnapshot

func (*ORTree) TombstoneTags added in v1.0.10 

func (t *ORTree) TombstoneTags() []NodeID

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

func (*ORTree) UnmarshalBinary 

func (t *ORTree) UnmarshalBinary(data []byte) error

UnmarshalBinary validates the full state before atomically replacing t. Complete states additionally require every non-root parent to be present.

func (*ORTree) UnmarshalBinaryWithLimits 

func (t *ORTree) UnmarshalBinaryWithLimits(data []byte, limits frame.DecoderLimits) error

type Options added in v1.0.10 

type Options struct {
	MaxNodes      int
	MaxTombstones int
	MaxValueBytes int
}

Options bounds retained OR-Tree state. Applications handling untrusted peers should set limits for the replication group rather than rely on process-wide memory availability.

func DefaultOptions added in v1.0.10 

func DefaultOptions() Options

DefaultOptions returns conservative retention limits that align with one default frame's element and value limits.

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.