block

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 block defines the building blocks of a Yjs document.

The central type is Item — a single insertion in the CRDT linked list, identified by an ID (clientID + clock). Items carry origin pointers captured at insertion time (used by YATA for conflict resolution) plus current left/right pointers in the post-merge structure.

Wire format compatibility with the JS Yjs implementation is the prime directive of this package; field semantics mirror y-crdt/yrs (see yrs/src/block.rs as the executable reference).

This package is internal: callers should use the public ygo, doc, and types packages instead.

Index

Constants

View Source 
const (
	InfoHasRightOrigin uint8 = 0b0100_0000 // bit 6
	InfoHasOrigin      uint8 = 0b1000_0000 // bit 7
	InfoHasParentSub   uint8 = 0b0010_0000 // bit 5
	InfoContentMask    uint8 = 0b0000_1111
)

Wire info byte. Emitted as the first byte of every Item record in the V1 update format. Bits 0-3 carry the Content kind (ref number 0..11), bits 5-7 carry presence flags. Bit 4 is currently unused on the wire.

Verbatim from yrs/src/block.rs:64-72 (commit 639db20).

View Source 
const (
	FlagKeep      uint16 = 0b0000_0000_0000_0001 // bit 0
	FlagCountable uint16 = 0b0000_0000_0000_0010 // bit 1
	FlagDeleted   uint16 = 0b0000_0000_0000_0100 // bit 2
	FlagMarked    uint16 = 0b0000_0000_0000_1000 // bit 3 — unused in yrs
	FlagLinked    uint16 = 0b0000_0001_0000_0000 // bit 8 — weak-link target
)

Internal Item flags. NOT serialized; live in Item.Flags as a uint16.

Verbatim from yrs/src/block.rs:1044-1057.

FlagMarked is dead in yrs ("not used atm"); we keep the constant to preserve bit-position equivalence in case a future Yjs version starts using it.

Variables

View Source 
var (
	ErrParentUnresolved   repairError = "block: parent could not be resolved"
	ErrParentIDUnresolved repairError = "block: parent-by-ID points to an Item not yet in the store (queue in pending)"
	ErrParentIDNotType    repairError = "block: parent-by-ID points to an Item whose Content is not KindType"
)

Errors returned by Repair.

Functions

func Repair 

func Repair(it *Item, ctx IntegrateContext) error

Repair pre-resolves an Item's transient pointers and parent reference so it is ready for Integrate. Called once per item in the update-apply path before push_block / Integrate.

Specifically:

  • Origin (immutable ID) → Left (live *Item), via ctx.MaterializeCleanEnd. The store splits the underlying block if Origin lands mid-block.
  • RightOrigin (immutable ID) → Right (live *Item), via ctx.MaterializeCleanStart.
  • Parent (tagged union) → resolved ParentBranch:
  • ParentBranch already resolved → no-op.
  • ParentNamed("name") → ctx.GetOrCreateBranch(name).
  • ParentUnknown → inherit from a resolved neighbour (left first, then right) per yrs Item::repair lines 1394-1404.
  • ParentID (nested type by item ID) → not yet implemented; returns ErrParentIDUnresolved.

Mirrors yrs/src/block.rs:1368-1431 Item::repair, omitting the rich-text / weak-link extras since we do not yet carry those content variants.

Concurrency: caller must hold the doc's write lock (ctx is a TransactionMut or equivalent).

Types

type Any 

type Any = any

Any is the JSON-like value type used as the payload for ContentAny, ContentEmbed, ContentFormat. yrs's Any is a proper tagged union (Bool, Number, BigInt, String, Buffer, Array, Map, Null, Undefined).

We use Go's any here as a placeholder. The proper tagged-union form will land with the encoding/decoding work since wire compatibility requires deterministic encoding of each variant.

type Branch 

type Branch struct {
	// Start is the head of the positional linked list (the first Item
	// in document order). nil for empty or map-only branches.
	Start *Item

	// Map associates a map-key with the rightmost Item that wrote
	// that key (the "winner" of the YATA tail). nil for non-map-like
	// branches; populated lazily.
	Map map[string]*Item

	// Item is the back-reference to the Item whose Content owns this
	// branch (for nested shared types). nil for root branches.
	// Integrate consults Item.IsDeleted to decide whether to
	// auto-delete the inserted item (parent_deleted path).
	Item *Item

	// BlockLen is the sum of Len for non-deleted, countable, positional
	// items in this branch. Integrate updates it as items land.
	BlockLen uint64

	// ContentLen is the sum of content-len for the same items. For
	// non-string content this matches BlockLen; for strings it may
	// differ once UTF-16 encoding semantics are wired (see
	// tech-debt.md surrogate-pair entry).
	ContentLen uint64

	// Name identifies a root branch. Empty string for non-root.
	// Used by encoders that need to emit the parent type name.
	Name string

	// TypeRef discriminates the kind of shared type this Branch
	// represents (Map, Array, Text, Xml*, etc.). Set on construction
	// by the types layer; consumed by the ContentType encoder and by
	// extractValue when wrapping a nested type for user code.
	//
	// The zero value (TypeRefArray) is intentional for the wire
	// format — Array's type-refs byte is 0. Constructors that build
	// non-Array branches MUST set this explicitly.
	TypeRef TypeRef

	// Markers is the per-branch search-marker cache used by Array /
	// Text position resolution to skip O(N) linked-list walks on
	// hot edit paths. Allocated lazily (nil until the first marker
	// goes in) so branches that never see large positional ops pay
	// no overhead. See search_marker.go for the LRU semantics and
	// docs/yrs-port-notes/types-array.md finding 1 + BENCHMARKS.md
	// B4 entry for the workload that motivated this.
	Markers *MarkerList
}

Branch is the owning collection for nested shared types (Map, Array, Text, Xml). The full type lives in the types layer when it lands; the fields below are the minimum subset that Item.Integrate and Item.Splice need to manipulate.

Concurrency: a Branch is mutated only under a TransactionMut write lock. Reading from a non-current transaction is undefined.

See yrs/src/branch.rs Branch.

type Content 

type Content struct {
	Kind ContentKind

	Anys      []Any    // KindAny, KindEmbed (1 elem), KindFormat (value, 1 elem)
	JSONStrs  []string // KindJSON (legacy stringified JSON, splittable)
	Bytes     []byte   // KindBinary
	Str       string   // KindString — UTF-8 input; internally normalized to UTF-16 for wire
	FormatKey string   // KindFormat (key)

	DeletedLen uint64 // KindDeleted, KindSkip — element count only

	Branch    *Branch // KindType
	Move      *Move   // KindMove
	Doc       *Doc    // KindDoc — child doc
	ParentDoc *Doc    // KindDoc — parent doc reference, set at integrate time
}

Content is the payload of an Item. A single struct (not an interface) so it embeds in Item without an extra allocation and reads cleanly in tests without a type-switch.

Each ContentKind uses only a subset of fields. The unused fields on any given variant must be left at their zero value; tests assert this.

See docs/yrs-port-notes/block.md "ItemContent tagged union" for the rationale and the variant-to-field mapping.

func (Content) IsCountable 

func (c Content) IsCountable() bool

IsCountable reports whether this content's elements contribute to the parent's user-facing length.

yrs/src/block.rs ItemContent::is_countable: false for Deleted, Format, Move; true for everything else.

func (Content) Len 

func (c Content) Len(_ OffsetKind) uint64

Len returns the number of elements (clock units) this content spans under the given offset semantics.

For splittable variants (Any, JSON, String) this is the slice length in the appropriate unit; for single-element variants (Binary, Embed, Type, Doc) it is 1; for Deleted/Skip it is the stored length.

String length is always UTF-16 code units regardless of kind, per yrs/src/block.rs comment on Item::new and the wire-format invariant. (See docs/yjs-architecture-notes.md §19 and DESIGN.md.)

Return type is uint64 (yrs uses u32). We accept wire values up to 2^64-1; clock and length values produced by yrs and JS Yjs always fit in u32 in practice, so this is strictly a defensive widening.

func (Content) RefNumber 

func (c Content) RefNumber() uint8

RefNumber returns the Yjs wire ref number for the content's kind. This is the low nibble of the Item info byte.

func (*Content) Split 

func (c *Content) Split(offset uint64) (Content, error)

Split cuts the content at offset and returns the right half, mutating the receiver to hold the left half. Returns an error if the content kind is not splittable or offset is out of range.

Splittable kinds: String (currently byte offsets — UTF-16 awareness arrives with the Text shared type, see tech-debt.md), Any, JSON, Deleted. All other kinds are single-element or parallel cell kinds and reject Split.

See yrs/src/block.rs ItemContent::splice.

func (*Content) TrySquash 

func (c *Content) TrySquash(other *Content) bool

TrySquash extends the receiver to absorb other's payload, returning true on success. Squashable kinds: Any (slice append), Deleted (length sum), JSON (slice append), String (concat). Non-matching kinds and other variants return false without mutation.

Mirrors yrs/src/block.rs:1969-1993 ItemContent::try_squash.

type ContentKind 

type ContentKind uint8

ContentKind discriminates the variants of Content. The numeric values are the Yjs wire ref numbers (BLOCK_ITEM_*_REF_NUMBER from yrs/src/block.rs:28-72) and must not change.

KindGC (0) and KindSkip (10) are not Content variants — they are parallel BlockCell kinds — but the constants are reserved here so the nibble values stay consistent with the wire. 

const (
	KindGC      ContentKind = 0
	KindDeleted ContentKind = 1
	KindJSON    ContentKind = 2
	KindBinary  ContentKind = 3
	KindString  ContentKind = 4
	KindEmbed   ContentKind = 5
	KindFormat  ContentKind = 6
	KindType    ContentKind = 7
	KindAny     ContentKind = 8
	KindDoc     ContentKind = 9
	KindSkip    ContentKind = 10
	KindMove    ContentKind = 11
)

type Doc 

type Doc struct{}

Doc is the document container. Stubbed here so ContentDoc compiles without pulling in the doc package.

type ID 

type ID struct {
	Client uint64
	Clock  uint64
}

ID uniquely identifies an Item in a Yjs document. Client is the random uint64 assigned to a Doc at creation; Clock is a per-client monotonic counter that increments on every operation produced by that client. The pair is the Lamport timestamp Yjs uses for ordering and conflict resolution.

func (ID) Equal 

func (i ID) Equal(other ID) bool

Equal reports whether two IDs name the same Item.

func (ID) IsZero 

func (i ID) IsZero() bool

IsZero reports whether the ID is the zero value. Yjs treats Client=0,Clock=0 as a valid ID for the synthetic root entries, so callers should compare against an explicit "no parent" sentinel rather than relying on IsZero in origin/parent positions.

func (ID) Less 

func (i ID) Less(other ID) bool

Less orders IDs lexicographically: Client first, then Clock. This matches yrs's Ord impl for ID and is the order used by the y-sync state-vector encoding (which iterates clients in ascending order).

Note: this is *not* the YATA ordering used for conflict resolution at insertion time. YATA compares origins and falls back on Client only when origins tie. Use this Less only for storage/iteration ordering.

func (ID) String 

func (i ID) String() string

String returns a debug representation in the form "client:clock".

type IDOrNil 

type IDOrNil = *ID

IDOrNil is a pointer-or-value helper for fields that semantically permit "absent" (origin-left/right of an Item inserted at a boundary). nil means "no neighbor at insertion time"; a non-nil *ID names the neighbor.

Yjs distinguishes "no origin" (insertion at boundary) from "origin happens to be the synthetic root ID" — encoding them differently on the wire. Using *ID rather than a sentinel ID value keeps that distinction explicit.

type IntegrateContext 

type IntegrateContext interface {
	// GetItem returns the Item containing the given ID, or nil if the
	// store has no record of that ID or the cell at that clock is
	// a GC tombstone.
	GetItem(id ID) *Item

	// MaterializeCleanStart returns an Item that starts exactly at
	// id.Clock, splitting the underlying block in the store if id
	// lands mid-block. Returns nil if id is in a GC cell or unknown.
	//
	// Wraps yrs's `store.blocks.get_item_clean_start(id).map(|slc|
	// store.materialize(slc))`.
	MaterializeCleanStart(id ID) *Item

	// MaterializeCleanEnd returns an Item ending exactly at id.Clock
	// (inclusive), splitting if needed. Returns nil under the same
	// conditions as MaterializeCleanStart.
	//
	// Wraps yrs's `store.blocks.get_item_clean_end(id).map(|slc|
	// store.materialize(slc))`.
	MaterializeCleanEnd(id ID) *Item

	// Delete tombstones an Item: sets FlagDeleted, records the ID in
	// the transaction's delete set, and schedules observer events on
	// the owning branch.
	Delete(item *Item)

	// AddChangedType marks a Branch (with optional map-key
	// discriminator) as having user-observable changes; observers
	// fire on the recorded set at Commit time.
	AddChangedType(parent *Branch, parentSub *string)

	// GetOrCreateBranch returns the root branch with the given name,
	// creating it lazily if absent. Used by Repair to resolve
	// ParentNamed references arriving from wire updates.
	GetOrCreateBranch(name string) *Branch
}

IntegrateContext is the subset of TransactionMut that Item.Integrate consumes. Defined here in the block package so Item.Integrate can be declared without an import cycle on the doc package.

All methods are called under the TransactionMut write lock; no internal synchronization is needed.

type Item 

type Item struct {
	// ID of the FIRST element in this block. The block covers
	// IDs (Client, Clock) ... (Client, Clock+Len-1).
	ID ID

	// Number of elements (clock units) packed into this block.
	// Always counted in UTF-16 code units for String content, per
	// yrs/src/block.rs Item::new (block.rs:1307).
	//
	// uint64 matches our ID.Clock width. yrs uses u32; we widen
	// defensively since lib0 varuints can carry values up to u64.
	Len uint64

	// Doubly-linked list neighbours in document order. Mutable —
	// repointed by integrate(), splice(), and squash. nil at the
	// edges of the parent collection.
	Left  *Item
	Right *Item

	// Insertion-time neighbour IDs. Immutable — part of the wire
	// identity and used by YATA conflict resolution. nil when the
	// item was inserted at the start/end of the parent.
	Origin      *ID
	RightOrigin *ID

	// User payload.
	Content Content

	// Owning collection. Stored items always have Parent.IsResolved.
	Parent Parent

	// Map key when Parent is map-like (Y.Map, XML attributes).
	// nil for sequence-positional items (Y.Array, Y.Text).
	ParentSub *string

	// UndoManager bookkeeping: ID of the item that revived this one
	// via redo. nil for items that have not been redone.
	Redone *ID

	// Active Move operation controlling this item, if any.
	Moved *Move

	// Internal flag bits: FlagKeep, FlagCountable, FlagDeleted,
	// FlagMarked, FlagLinked. NOT serialized.
	Flags uint16
}

Item is the atomic CRDT unit of a Yjs document. Every insertion the user makes produces an Item; deletions tombstone an Item but never remove it.

The struct shape mirrors yrs/src/block.rs Item one-for-one. See docs/yrs-port-notes/block.md for field-by-field semantics and the 13 invariants that integrate() and try_squash() depend on.

Concurrency: *Item must never escape the transaction that produced it. The Doc's RWMutex is the only thing that makes pointer access to Left/Right/Origin/RightOrigin sound.

func (*Item) EqualByID 

func (it *Item) EqualByID(other *Item) bool

EqualByID reports whether two items name the same insertion (same ID). Yjs's Item::PartialEq derives equality through ItemPtr which compares by id only; this is the same semantics in Go.

Use this for set/map keys and tests of structural identity. Use content/flag/neighbour comparison directly when checking whether two items are byte-identical (e.g. encode/decode roundtrip tests).

func (*Item) Info 

func (it *Item) Info() uint8

Info returns the Yjs wire info byte for this item: low nibble carries the content ref number; bits 5-7 carry presence flags for parent_sub, right_origin, origin.

yrs/src/block.rs Item::info(): 

(origin.is_some()       ? HAS_ORIGIN       : 0)
| (right_origin.is_some() ? HAS_RIGHT_ORIGIN : 0)
| (parent_sub.is_some()   ? HAS_PARENT_SUB   : 0)
| (content.get_ref_number() & 0b1111)

func (*Item) Integrate 

func (i *Item) Integrate(ctx IntegrateContext, offset uint64) bool

Integrate inserts this Item into its parent branch, running the YATA conflict-resolution algorithm to find the right position among any concurrent inserts. The Item must already be present in the block store (typically via store.PushBlock) before calling Integrate; Integrate only wires the doubly-linked list and updates parent fields.

Preconditions:

  • i.Origin / i.RightOrigin (immutable) are set if the item is not anchored at the parent boundary.
  • i.Left / i.Right have been pre-resolved by a Repair pass that looked up the Origin / RightOrigin in the store. (Until our Repair pass ships, callers must do this manually; see tech-debt.md.)
  • i.Parent.Kind is ParentBranch with a resolved *Branch. The ParentNamed and ParentID forms are not yet handled — callers must pre-resolve via the types layer's root-type registry.

Return value mirrors yrs: true means "the item is now wired into the parent, but the caller must immediately Delete it." Reasons:

  • parent is deleted, or
  • this is a map-key insert that lost the LWW race (parent_sub.is_some() && right.is_some()).

false means "successfully integrated, do nothing further."

See docs/yrs-port-notes/integrate.md for the line-by-line mapping to yrs/src/block.rs:562-846.

Limitations vs yrs (tracked in tech-debt.md):

  • offset > 0 (the Update partial-integrate path) is not handled.
  • Named/ID parent variants return false without wiring (caller bug — pre-resolve to ParentBranch).
  • Move integration recursion is skipped.
  • Subdoc registration (ContentDoc) is skipped.
  • Weak-link (info.IsLinked) bookkeeping is skipped.
  • Format-marker integration is a no-op (matches yrs).

func (*Item) IsCountable 

func (it *Item) IsCountable() bool

func (*Item) IsDeleted 

func (it *Item) IsDeleted() bool

func (*Item) IsKeep 

func (it *Item) IsKeep() bool

func (*Item) IsLinked 

func (it *Item) IsLinked() bool

func (*Item) LastID 

func (it *Item) LastID() ID

LastID returns the ID of the last element this block covers, i.e. (Client, Clock+Len-1). Mirrors yrs Item::last_id (block.rs).

Caller must ensure Len > 0; an empty Item is rejected at construction.

func (*Item) SetCountable 

func (it *Item) SetCountable(v bool)

func (*Item) SetDeleted 

func (it *Item) SetDeleted(v bool)

func (*Item) SetKeep 

func (it *Item) SetKeep(v bool)

func (*Item) SetLinked 

func (it *Item) SetLinked(v bool)

func (*Item) Splice 

func (it *Item) Splice(offset uint64) *Item

Splice cuts self at offset (in clock units) and returns the new right-half Item. Returns nil if offset is 0, offset >= self.Len, or the content kind is not splittable.

Mutations:

  • self.Len truncated to offset.
  • self.Content split (right half migrated into the returned Item).
  • self.Right re-pointed to the new Item; the previous self.Right's Left re-pointed to the new Item if it existed.

The new right Item carries:

  • ID = (self.client, self.clock + offset).
  • Len = self.Len - offset (original Len).
  • Origin = &(self.client, self.clock + offset - 1) — the ID of the last element of self after truncation; this is the YATA-time left neighbour of the new half.
  • RightOrigin = self.RightOrigin (preserved; immutable per YATA).
  • Parent, ParentSub, Moved, Flags copied from self.
  • Left = self; Right = self's original Right.

Caller is responsible for storing the new right Item in the block store. Use store.BlockStore.SplitBlock for integrated insertion.

Known limitation: when self was the most recent writer on a map-like parent (Right=nil, ParentSub != nil), yrs additionally rewrites parent.Branch.Map[*ParentSub] = right. We do not, because Branch is a stub until the types layer lands. See tech-debt.md.

Mirrors yrs/src/block.rs:516-560 ItemPtr::splice.

func (*Item) TrySquash 

func (i *Item) TrySquash(other *Item) bool

TrySquash attempts to merge `other` into the receiver, producing a single combined Item that covers both ID ranges. Returns true on success; the caller must then drop `other` from its container.

Squash refuses if any of the following fails:

  • Same client.
  • Adjacent clocks: i.LastClock + 1 == other.ID.Clock.
  • Same deleted state.
  • other.Origin == i.LastID (i.e. other was inserted with i as its left neighbour at insertion time).
  • other.RightOrigin == i.RightOrigin (immutable invariants line up).
  • i.Right == other (current linked-list pointers agree).
  • Neither is in a Move range or has been redone.
  • Neither is weak-linked.
  • Content.TrySquash succeeds for the kind-specific payload.

Mirrors yrs/src/block.rs:848-876 ItemPtr::try_squash.

type MarkerList 

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

MarkerList is a fixed-cap pool of SearchMarkers attached to a Branch. Construct lazily — branches that never see large findPosition calls pay nothing.

func NewMarkerList 

func NewMarkerList() *MarkerList

NewMarkerList returns an empty MarkerList sized to markerCap.

func (*MarkerList) Add 

func (m *MarkerList) Add(item *Item, index uint64)

Add records a fresh marker. If at cap, evicts the marker with the smallest timestamp (LRU). If the new marker's item already has a marker, the existing one is updated in-place rather than adding a duplicate — keeps the cache useful when the same item is touched repeatedly.

func (*MarkerList) Invalidate 

func (m *MarkerList) Invalidate()

Invalidate clears every marker. Use when the underlying linked list undergoes structural changes the shift helpers can't describe (deep nested operations, bulk apply, etc.). The next findPosition call will walk from branch.Start as if no cache existed.

func (*MarkerList) Len 

func (m *MarkerList) Len() int

Len returns the current marker count — useful only for tests and debug observability.

func (*MarkerList) Nearest 

func (m *MarkerList) Nearest(target uint64) *SearchMarker

Nearest returns a pointer to the marker whose Index is closest to target, or nil if the list is empty. The caller may walk forward (target > marker.Index) or backward (target < marker.Index) from marker.Item; both directions are supported by the linked-list structure (Item.Right / Item.Left).

Returned pointer aliases internal state; callers must NOT retain it past the next list mutation (Add / Touch / ShiftAfter / ShrinkAfter).

func (*MarkerList) ShiftAfter 

func (m *MarkerList) ShiftAfter(insertIdx, insertLen uint64)

ShiftAfter is called after an Insert at insertIdx with length insertLen. Markers whose Index is strictly greater than insertIdx shift right by insertLen (their items now appear `insertLen` positions later). Markers at exactly insertIdx and before are unaffected — the newly-inserted item lives at insertIdx but did not displace anything before it.

func (*MarkerList) ShrinkAfter 

func (m *MarkerList) ShrinkAfter(delIdx, delLen uint64)

ShrinkAfter is called after a Delete at [delIdx, delIdx+delLen). Markers whose Index falls inside the deleted range are dropped (their items may now point at tombstones for which we can't reliably regenerate a position without re-walking). Markers strictly after the range shift left by delLen. Markers strictly before are unaffected.

func (*MarkerList) Touch 

func (m *MarkerList) Touch(mk *SearchMarker)

Touch bumps the marker's timestamp so the next eviction skips it. Call after a successful Nearest hit + walk.

type Move 

type Move struct{}

Move records a move operation for movable list items. Defined when Y.Array move support is added (post-MVP). See yrs/src/moving.rs.

type OffsetKind 

type OffsetKind uint8

OffsetKind selects between Yjs's UTF-16 (default, matches JS) and UTF-8 (alternative) text-position semantics. Internal Item lengths are always UTF-16 regardless of this setting; OffsetKind only affects what user-facing index parameters mean.

See yrs/src/doc.rs OffsetKind enum and DESIGN.md "Wire-format-driven storage decisions". 

const (
	// OffsetUtf16 is the default. ytext.Insert(idx int, ...) accepts
	// idx in UTF-16 code units, matching JS Y.Text.length semantics.
	OffsetUtf16 OffsetKind = iota
	// OffsetBytes is an alternative where idx is in UTF-8 bytes.
	OffsetBytes
)

type Parent 

type Parent struct {
	Kind   ParentKind
	Branch *Branch // ParentBranch
	Named  string  // ParentNamed
	ID     ID      // ParentID
}

Parent is a tagged union holding either a resolved Branch reference or one of the unresolved forms used during update decoding.

See docs/yrs-port-notes/block.md "BranchPtr / parent reference".

func (Parent) IsResolved 

func (p Parent) IsResolved() bool

IsResolved reports whether this parent reference points at a live Branch and is therefore safe to use as the owning collection.

type ParentKind 

type ParentKind uint8

ParentKind discriminates the four states a parent reference can be in. Mirrors yrs/src/types/mod.rs TypePtr. 

const (
	// ParentUnknown is the pre-resolution sentinel. Items decoded
	// from updates start here; integrate() resolves to one of the
	// concrete variants. Items in this state are not yet stored.
	ParentUnknown ParentKind = iota
	// ParentBranch points directly at a live owning collection.
	// Stored items are always in this state.
	ParentBranch
	// ParentNamed identifies a root type by name; resolves to
	// ParentBranch on integrate via the Doc's root-type registry.
	ParentNamed
	// ParentID identifies a nested type by the ID of the Item whose
	// content owns it; resolves to ParentBranch on integrate via the
	// store.
	ParentID
)

type SearchMarker 

type SearchMarker struct {
	// Item is the linked-list node this marker points at. May be
	// a tombstone (in which case Index is the position immediately
	// after the tombstone run that includes Item — slightly stale
	// markers still resolve correctly because the search walks
	// forward from the marker and counts live items).
	Item *Item

	// Index is the user-facing index where Item starts in document
	// order (countable, non-deleted items only).
	Index uint64

	// Timestamp is a monotonic clock value bumped on Touch / Add;
	// used to evict the oldest marker when len == Cap.
	Timestamp uint64
}

SearchMarker caches "item I starts at user-facing index N" so a subsequent position lookup near N can walk the linked list from I instead of from branch.Start. Without markers, every Array / Text Insert at index P walks O(P) items; B4 (259k sequential edits on a 100k-char doc) is the canonical pathological workload — see BENCHMARKS.md and docs/yrs-port-notes/types-array.md finding 1.

Mirrors yrs's SearchMarker (yrs/src/branch.rs around the `search_marker` field) with the same ~80-marker LRU cap.

Concurrency: MarkerList is mutated only under the doc write lock (held by TransactionMut). Read-only access from a read txn is safe as long as no concurrent writer holds the same Branch.

type TypeRef 

type TypeRef uint8

TypeRef discriminates the kind of shared type a Branch represents. Wire constants match yjs/src/structs/ContentType.js Y*RefID family (Item.js:1382-1388) and yrs/src/types/mod.rs TypeRef enum.

The TypeRef byte is emitted as a varuint at the start of a ContentType payload — see docs/yrs-port-notes/nested-types.md §2. Root branches do NOT emit TypeRef on the wire (they are referenced by name), but their in-memory Branch.TypeRef field is still set so extractValue can return the right wrapper type to user code.

TypeRefArray is intentionally 0 to match the JS/Rust wire value. TypeRefUndefined (15) is the sentinel for "not specified" — used for Branch values constructed before their final type is known (e.g. a freshly-decoded ContentType payload whose type-refs byte hasn't been read yet). A zero Branch{} would silently read as Array without an explicit sentinel, so constructors must set TypeRef explicitly. 

const (
	TypeRefArray       TypeRef = 0
	TypeRefMap         TypeRef = 1
	TypeRefText        TypeRef = 2
	TypeRefXmlElement  TypeRef = 3
	TypeRefXmlFragment TypeRef = 4
	TypeRefXmlHook     TypeRef = 5
	TypeRefXmlText     TypeRef = 6
	TypeRefDoc         TypeRef = 9
	TypeRefUndefined   TypeRef = 15
)

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.