store

package
v0.9.0 Latest Latest
Warning

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

 Go to latest Published: May 17, 2026 License: MIT Imports: 3 Imported by: 0

Documentation

Overview

Package store implements the per-client block storage that owns the memory for every Item in a Yjs document.

The store is responsible for:

  • Owning the per-client list of BlockCells (Item or GC) in clock order.
  • Looking up cells by ID via binary search.
  • Producing a StateVector summarizing what the local doc knows.
  • Computing clean-edge ItemSlices for sync / integration paths.

It is not responsible for:

  • Splicing Items mid-clock-range (that lives on block.Item.Splice; see tech-debt.md).
  • Integration / YATA conflict resolution (lives on block.Item.Integrate).
  • Squashing adjacent runs (lives on block.Item.TrySquash).
  • Building the delete set (separate id_set layer).
  • Concurrency control (the Doc layer holds a sync.RWMutex around store ops).

See docs/yrs-port-notes/store.md for the per-method contract and the 13 invariants every mutation must preserve.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type BlockCell 

type BlockCell struct {
	Kind CellKind
	GC   GC          // valid when Kind == CellKindGC
	Item *block.Item // valid when Kind == CellKindItem; nil otherwise
}

BlockCell is the unit a ClientBlockList holds. It carries either a pinned *Item (for live or soft-deleted items) or an inline GC range.

Single struct + discriminator instead of an interface: keeps the ClientBlockList slice cheap to shift on insert and avoids interface dispatch on the FindPivot binary search hot path.

func CellOfGC 

func CellOfGC(start, end uint64) BlockCell

CellOfGC builds a BlockCell wrapping the given GC range.

func CellOfItem 

func CellOfItem(it *block.Item) BlockCell

CellOfItem builds a BlockCell wrapping the given item. Convenience constructor for callers that produce items elsewhere.

func (BlockCell) AsItem 

func (c BlockCell) AsItem() *block.Item

AsItem returns the underlying *Item or nil if this is a GC cell. Provided so callers don't read c.Item directly without checking Kind.

func (BlockCell) ClockEnd 

func (c BlockCell) ClockEnd() uint64

ClockEnd returns the inclusive upper bound of the cell's ID range.

func (BlockCell) ClockStart 

func (c BlockCell) ClockStart() uint64

ClockStart returns the inclusive lower bound of the cell's ID range.

func (BlockCell) IsDeleted 

func (c BlockCell) IsDeleted() bool

IsDeleted reports whether the cell represents a tombstoned range. GC cells are always considered deleted (they exist only because something was deleted and then collected); Item cells consult Item.Flags.

func (BlockCell) Len 

func (c BlockCell) Len() uint64

Len returns the number of clocks this cell covers. Equivalent to ClockEnd - ClockStart + 1.

type BlockSlice 

type BlockSlice struct {
	Kind SliceKind
	Item ItemSlice
	GC   GCSlice
}

BlockSlice is a tagged union over ItemSlice and GCSlice.

type BlockStore 

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

BlockStore owns the per-client block lists for a single Doc. It is not safe for concurrent access; the Doc layer holds the RWMutex.

func NewBlockStore 

func NewBlockStore() *BlockStore

NewBlockStore returns an empty store.

func (*BlockStore) Contains 

func (s *BlockStore) Contains(id block.ID) bool

Contains reports whether the store has ever seen the given ID. Returns true even for IDs covered by GC cells — the underlying knowledge is preserved (matches JS Yjs and yrs semantics; see store.md open question 9).

func (*BlockStore) GetBlock 

func (s *BlockStore) GetBlock(id block.ID) (BlockCell, bool)

GetBlock returns the BlockCell containing id, or (zero, false) if no client list exists or id.Clock is out of that client's range.

func (*BlockStore) GetClient 

func (s *BlockStore) GetClient(c uint64) *ClientBlockList

GetClient returns the per-client list for client c, or nil if no block has ever been inserted for that client.

Mirrors yrs BlockStore::get_client (block_store.rs).

func (*BlockStore) GetClientMut 

func (s *BlockStore) GetClientMut(c uint64) *ClientBlockList

GetClientMut returns the per-client list for c, creating an empty list lazily if absent. The only API that constructs ClientBlockLists.

Mirrors yrs BlockStore::get_client_blocks_mut (block_store.rs:429-433).

func (*BlockStore) GetClock 

func (s *BlockStore) GetClock(c uint64) uint64

GetClock returns the next free clock for client c, or 0 if c is unknown. Convenience shortcut over GetClient(c).Clock().

Mirrors yrs BlockStore::get_clock (block_store.rs:419-425).

func (*BlockStore) GetItem 

func (s *BlockStore) GetItem(id block.ID) *block.Item

GetItem returns the *Item containing id. Returns nil for GC cells (callers must treat nil as "either not found or already collected"; use Contains to disambiguate when it matters).

Mirrors yrs BlockStore::get_item (block_store.rs:386-393).

func (*BlockStore) GetItemCleanEnd 

func (s *BlockStore) GetItemCleanEnd(id block.ID) (ItemSlice, bool)

GetItemCleanEnd returns the slice from the beginning of id's block up to and including id. Symmetric to GetItemCleanStart.

Mirrors yrs BlockStore::get_item_clean_end (block_store.rs:409-414).

func (*BlockStore) GetItemCleanStart 

func (s *BlockStore) GetItemCleanStart(id block.ID) (ItemSlice, bool)

GetItemCleanStart returns the slice from id.Clock to the end of its underlying block, without mutating anything. The caller can pass the returned slice to a future Materialize to physically split the block; here we only compute offsets.

Returns (zero, false) when id is in a GC cell, in an unknown client, or out of range.

Mirrors yrs BlockStore::get_item_clean_start (block_store.rs:399-403).

func (*BlockStore) GetStateVector 

func (s *BlockStore) GetStateVector() StateVector

GetStateVector materializes a fresh StateVector from the per-client Clock() values. No caching — yrs derives the SV on each call too (block_store.rs:357-364).

Iteration order over s.clients is non-deterministic; the returned map's order is also non-deterministic. Encoding paths must sort by client ID before emitting bytes.

func (*BlockStore) Materialize 

func (s *BlockStore) Materialize(slc ItemSlice) *block.Item

Materialize splits the underlying block on both sides (as needed) so that the returned *Item covers exactly the slice's [Start, End] range in clock units. If the slice already covers the full block on either side, the corresponding split is skipped.

Returns the (possibly new) *Item that represents the slice exactly. Always uses UTF-16 offset semantics, matching yrs's hard-coding.

Mirrors yrs/src/store.rs:295-342 Store::materialize (without the linked_by rewiring, which lives on the future Doc layer once weak references arrive).

func (*BlockStore) PushBlock 

func (s *BlockStore) PushBlock(item *block.Item)

PushBlock appends a fresh Item to its client's list. The caller must guarantee item.ID.Clock == s.GetClock(item.ID.Client) — i.e. the new block's first clock is exactly the next free clock for that client. Violating this breaks invariant 1 of ClientBlockList; tests should follow with CheckInvariants.

Mirrors yrs BlockStore::push_block (block_store.rs:314-326).

func (*BlockStore) PushGC 

func (s *BlockStore) PushGC(client, start, end uint64)

PushGC appends a fresh GC range to its client's list, with the same monotonicity precondition as PushBlock.

Mirrors yrs BlockStore::push_gc (block_store.rs:328-341).

func (*BlockStore) SplitBlock 

func (s *BlockStore) SplitBlock(it *block.Item, offset uint64) *block.Item

SplitBlock locates the cell containing it.ID in its client's list, calls it.Splice(offset), and inserts the new right-half cell at index+1. Returns the new *Item.

Returns nil if Splice declines (offset 0, offset >= it.Len, or non-splittable content kind) or if the item is not currently in the store.

Implicitly uses UTF-16 offset semantics — matches yrs's split_block_inner (block_store.rs:453-455). See store.md open question 7.

Mirrors yrs/src/block_store.rs:437-451.

type CellKind 

type CellKind uint8

CellKind discriminates BlockCell variants. Mirrors yrs BlockCell enum. 

const (
	// CellKindGC is a tombstone range whose content has been collected.
	// The ID range stays valid so that other items pointing at it via
	// Origin/RightOrigin continue to resolve.
	CellKindGC CellKind = 0
	// CellKindItem is a live or tombstoned-but-content-preserved item.
	CellKindItem CellKind = 1
)

type ClientBlockList 

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

ClientBlockList is the dense, clock-ordered list of every block produced by a single client. Invariants enforced:

  1. Per-client clock density: the union of cell ranges equals [0, Clock()) with no gaps and no overlaps.
  2. Sorted by clock: list[i].ClockStart < list[i+1].ClockStart.
  3. Inclusive ranges: ClockStart and ClockEnd are both inclusive; Len = End - Start + 1.

See docs/yrs-port-notes/store.md "Internal invariants".

func NewClientBlockList 

func NewClientBlockList() *ClientBlockList

NewClientBlockList returns an empty list. Capacity is reserved for the common case of a few-dozen blocks per client.

func (*ClientBlockList) CheckInvariants 

func (l *ClientBlockList) CheckInvariants() error

CheckInvariants validates structural invariants 1-3 across the list. Returns the first error found, or nil if everything is consistent.

Test-only utility; production code should not call this on the hot path. Recommended pattern: defer l.CheckInvariants() in any test that performs Push / Insert / SquashLeft to catch regressions immediately.

func (*ClientBlockList) Clock 

func (l *ClientBlockList) Clock() uint64

Clock returns the next free clock for this client. Equal to list[len-1].ClockEnd() + 1, or 0 for an empty list. Constant-time.

Mirrors yrs ClientBlockList::clock (block_store.rs:24-34). Used for state vector materialization and append-precondition checks.

func (*ClientBlockList) FindPivot 

func (l *ClientBlockList) FindPivot(clock uint64) (int, bool)

FindPivot returns the index of the cell whose [ClockStart, ClockEnd] inclusive range contains the given clock. Returns (0, false) if the list is empty or the clock is past Clock().

Implementation uses sort.Search rather than yrs's hand-rolled interpolation+binary search (block_store.rs:42-68). The interpolation is a micro-optimisation; sort.Search costs at most log2(N) extra comparisons and avoids the divide-by-zero edge case yrs has when the list contains a single block ending at clock 0.

func (*ClientBlockList) Get 

func (l *ClientBlockList) Get(i int) (BlockCell, bool)

Get returns the cell at index i. Returns the zero BlockCell and false if i is out of range.

func (*ClientBlockList) Insert 

func (l *ClientBlockList) Insert(index int, cell BlockCell)

Insert places cell at the given index, shifting later cells right. Used by split_block and materialize for the new right-half cell; caller must compute index via FindPivot and validate that the insert keeps invariants 1-3.

Mirrors yrs ClientBlockList::insert (block_store.rs:89-93).

func (*ClientBlockList) Len 

func (l *ClientBlockList) Len() int

Len returns the number of cells in the list.

func (*ClientBlockList) Push 

func (l *ClientBlockList) Push(cell BlockCell)

Push appends a cell to the list. Caller must guarantee cell.ClockStart() == l.Clock() to preserve invariant 1; in tests, follow with CheckInvariants.

Mirrors yrs ClientBlockList::push (block_store.rs:84-87).

type GC 

type GC struct {
	Start uint64
	End   uint64 // inclusive
}

GC is a garbage-collected ID range. Both Start and End are inclusive (matching yrs BlockCell::clock_range invariant 3 in store.md).

func (GC) Len 

func (g GC) Len() uint64

Len returns the number of clocks this GC range covers.

type GCSlice 

type GCSlice struct {
	Start uint64 // inclusive
	End   uint64 // inclusive
}

GCSlice is the GC-cell counterpart to ItemSlice. Fields are absolute clocks, not offsets, because GC cells have no notion of an underlying block.

func (GCSlice) Len 

func (s GCSlice) Len() uint64

Len returns the number of clocks the GC slice covers.

type ItemSlice 

type ItemSlice struct {
	Ptr   *block.Item
	Start uint64 // inclusive offset into [Ptr.ID.Clock, Ptr.ID.Clock+Ptr.Len)
	End   uint64 // inclusive offset; Start <= End <= Ptr.Len-1
}

ItemSlice is a non-destructive sub-range view over an Item. Start and End are inclusive offsets within the underlying block (0..=Item.Len-1).

A read-only computation; no mutation. To actually realize the slice boundaries as separate Items, callers must run Materialize on it, which splices the underlying block. See tech-debt.md and store.md "Edge cases".

func (ItemSlice) AdjacentLeft 

func (s ItemSlice) AdjacentLeft() bool

AdjacentLeft reports whether the slice covers the leftmost element of the underlying block. Materialize uses this to skip a no-op left split.

func (ItemSlice) AdjacentRight 

func (s ItemSlice) AdjacentRight() bool

AdjacentRight reports whether the slice covers the rightmost element of the underlying block. Materialize uses this to skip a no-op right split.

func (ItemSlice) ClockEnd 

func (s ItemSlice) ClockEnd() uint64

ClockEnd returns the absolute clock of the last element in the slice.

func (ItemSlice) ClockStart 

func (s ItemSlice) ClockStart() uint64

ClockStart returns the absolute clock of the first element in the slice.

func (ItemSlice) Len 

func (s ItemSlice) Len() uint64

Len returns the number of clocks the slice covers.

type SliceKind 

type SliceKind uint8

SliceKind discriminates BlockSlice variants. Mirrors yrs slice.rs. 

const (
	SliceKindItem SliceKind = 0
	SliceKindGC   SliceKind = 1
)

type StateVector 

type StateVector map[uint64]uint64

StateVector summarizes what the local doc knows. For each client it holds the next free clock (exclusive). A peer can compare its own StateVector against a remote SV to compute the diff.

Iteration order is non-deterministic; wire-emitting paths must sort by client ID before encoding. See store.md open question 4.

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.