@barocss/datastore

Transactional, schema-aware node store for managing document structure with normalized INode and IMark using sid (stable ID) and stype (schema type).

Overview

@barocss/datastore provides a normalized, transactional data store for document nodes. It manages:

• Node Storage: Normalized node storage with sid (stable ID) and stype (schema type)
• Schema Validation: Schema-aware operations with validation
• Transactions: Atomic operations with rollback support via Copy-on-Write overlay
• Transactional Overlay: Efficient COW mechanism that only duplicates modified nodes
• Lock System: Global write lock with queue for concurrent transaction management
• Content Management: Parent-child relationships and content ordering
• Mark Management: Text marks (bold, italic, etc.) with range tracking
• Document Traversal: Iterator and Visitor patterns for efficient document processing
• Operation Events: emitOperation() / onOperation() for collaboration integration

Installation

pnpm add @barocss/datastore

Architecture

graph TB
    subgraph "DataStore"
        A["Node Storage<br/>Map&lt;sid, INode&gt;"]
        B["Content Operations<br/>Parent-Child"]
        C["Transaction Manager<br/>Begin/Commit/Rollback"]
        D["Schema Validation"]
        E["Transactional Overlay<br/>Copy-on-Write"]
        F["Lock System<br/>Global Write Lock"]
    end
    
    G["Schema"] --> D
    A --> B
    C --> E
    E --> A
    D --> A
    F --> C
    
    H["Model Operations"] --> C
    C --> I["DataStore State"]
    
    style A fill:#e1f5ff
    style B fill:#fff4e1
    style C fill:#e8f5e9
    style D fill:#f3e5f5
    style E fill:#fff9c4
    style F fill:#fce4ec
    style G fill:#e0f2f1
    style H fill:#e0f2f1
    style I fill:#f1f8e9

Memory Storage Structure & SID System

graph TB
    subgraph "Memory Storage"
        A["Map&lt;string, INode&gt;<br/>Key: sid<br/>Value: INode"]
        B["Node Lookup<br/>O(1) Access"]
    end
    
    subgraph "SID Generation"
        C["Session ID<br/>_sessionId: number"]
        D["Global Counter<br/>_globalCounter: number"]
        E["SID Format<br/>sessionId:counter<br/>e.g., '0:1', '1:5'"]
    end
    
    subgraph "Node Structure"
        F["INode<br/>sid: '0:1'<br/>stype: 'paragraph'<br/>text: 'Hello'<br/>content: ['0:2']<br/>parentId: '0:0'"]
    end
    
    subgraph "Collaborative Editing"
        G["Session A<br/>sessionId: 0"]
        H["Session B<br/>sessionId: 1"]
        I["Operation Broadcast<br/>AtomicOperation"]
        J["SID Consistency<br/>Same node = Same sid"]
    end
    
    C --> E
    D --> E
    E --> A
    A --> B
    A --> F
    
    G --> I
    H --> I
    I --> J
    J --> A
    
    style A fill:#e1f5ff
    style E fill:#fff4e1
    style F fill:#e8f5e9
    style I fill:#f3e5f5
    style J fill:#fce4ec

Key Concepts

• Memory Storage: Nodes are stored in a Map<string, INode> where the key is the sid (stable ID), providing O(1) lookup performance
• SID Format: sessionId:globalCounter (e.g., "0:1", "1:5")
  • sessionId: Unique identifier for each DataStore instance/session
  • globalCounter: Static counter that increments for each new node
• Collaborative Editing: SID ensures nodes can be consistently referenced across multiple sessions
  • Same node always has the same SID across all sessions
  • Operations are broadcast with SID references
  • Conflict resolution uses SID to identify target nodes

Transactional Overlay (Copy-on-Write)

DataStore uses a Copy-on-Write (COW) overlay mechanism to provide efficient transactional operations without copying the entire document state.

Architecture

graph TB
    subgraph "Base Layer (Read-Only)"
        A["baseNodes<br/>Map&lt;sid, INode&gt;<br/>Original State"]
    end
    
    subgraph "Overlay Layer (COW)"
        B["overlayNodes<br/>Map&lt;sid, INode&gt;<br/>Modified Nodes"]
        C["deletedNodeIds<br/>Set&lt;sid&gt;<br/>Deleted Nodes"]
        D["touchedParents<br/>Set&lt;sid&gt;<br/>Parents with Content Changes"]
        E["opBuffer<br/>AtomicOperation[]<br/>Operation History"]
    end
    
    subgraph "Read Path"
        F["getNode(id)"]
        G{"deletedNodeIds<br/>has(id)?"}
        H{"overlayNodes<br/>has(id)?"}
        I["Return overlay"]
        J["Return base"]
        K["Return undefined"]
    end
    
    subgraph "Write Path"
        L["updateNode/createNode"]
        M["Clone from base<br/>if needed"]
        N["Apply changes"]
        O["Store in overlay"]
    end
    
    A --> F
    B --> F
    C --> F
    
    F --> G
    G -->|yes| K
    G -->|no| H
    H -->|yes| I
    H -->|no| J
    
    L --> M
    M --> N
    N --> O
    O --> B
    
    style A fill:#e1f5ff
    style B fill:#fff4e1
    style C fill:#fce4ec
    style D fill:#e8f5e9
    style E fill:#f3e5f5

How It Works

1. Transaction Begin: begin() initializes an empty overlay without copying base nodes
2. Read Operations: getNode() checks in order:
   • deletedNodeIds → returns undefined if deleted
   • overlayNodes → returns overlay version if modified
   • baseNodes → returns original version (fallback)
3. Write Operations: Changes are written to overlay using COW:
   • If node exists in overlay → use overlay version
   • If node exists only in base → clone from base to overlay
   • Apply changes to cloned node
   • Store in overlay
4. Transaction End: end() returns collected operations (overlay remains active)
5. Commit: commit() applies overlay changes to base in deterministic order:
   • create → update → move → delete
   • Clears overlay after application
6. Rollback: rollback() discards overlay without applying changes

Transaction Lifecycle

sequenceDiagram
    participant Client
    participant DataStore
    participant Overlay
    participant Base
    
    Client->>DataStore: begin()
    DataStore->>Overlay: begin()
    Note over Overlay: Initialize empty overlay
    
    Client->>DataStore: updateNode(id, changes)
    DataStore->>Overlay: Check if node in overlay
    alt Node in overlay
        Overlay-->>DataStore: Use overlay node
    else Node only in base
        DataStore->>Base: getNode(id)
        Base-->>DataStore: Original node
        DataStore->>Overlay: Clone to overlay
    end
    DataStore->>Overlay: Apply changes
    DataStore->>Overlay: Store in overlayNodes
    DataStore->>Overlay: Record operation in opBuffer
    
    Client->>DataStore: end()
    DataStore->>Overlay: getCollectedOperations()
    Overlay-->>Client: Return operations array
    
    Client->>DataStore: commit()
    DataStore->>Overlay: Get operations
    DataStore->>Base: Apply operations in order
    Note over Base: create → update → move → delete
    DataStore->>Overlay: rollback()
    Note over Overlay: Clear overlay state

Benefits

• O(1) Transaction Start: No copying of base nodes on begin()
• Memory Efficient: Only modified nodes are duplicated
• Atomic Operations: All changes are collected and applied atomically
• Rollback Support: Discard changes without affecting base state
• Operation History: All operations are recorded for sync/collaboration

Lock System

DataStore provides a global write lock to prevent concurrent write conflicts during transactions.

Architecture

graph TB
    subgraph "Lock Manager"
        A["Current Lock<br/>lockId, ownerId, acquiredAt"]
        B["Transaction Queue<br/>Waiting Transactions"]
        C["Lock Statistics<br/>Acquisitions, Timeouts, Wait Time"]
    end
    
    subgraph "Lock Acquisition"
        D["acquireLock(ownerId)"]
        E{"Lock<br/>Available?"}
        F["Immediate Acquisition"]
        G["Queue Entry"]
        H["Wait for Release"]
    end
    
    subgraph "Lock Release"
        I["releaseLock(lockId)"]
        J["Clear Current Lock"]
        K["Grant to Next<br/>in Queue"]
    end
    
    D --> E
    E -->|Yes| F
    E -->|No| G
    G --> H
    H --> K
    
    I --> J
    J --> K
    
    F --> A
    K --> A
    A --> C
    B --> C
    
    style A fill:#e1f5ff
    style B fill:#fff4e1
    style C fill:#e8f5e9
    style F fill:#f3e5f5
    style G fill:#fce4ec

How It Works

1. Lock Acquisition: acquireLock(ownerId) attempts to acquire the global write lock

   • If available → immediately granted
   • If busy → added to queue, waits for current lock release
   • Returns a unique lockId for the acquired lock

2. Lock Queue: Multiple transactions can wait in a FIFO queue

   • Each queued transaction has a timeout (default: 5 seconds)
   • Timeout rejects the promise if lock not acquired in time

3. Lock Release: releaseLock(lockId) releases the current lock

   • Validates lockId matches current lock (optional)
   • Grants lock to next transaction in queue
   • Updates statistics

4. Lock Timeout: Automatic timeout prevents deadlocks

   • Queue timeout: 5 seconds (rejects if not acquired)
   • Lock timeout: 50 seconds (force releases if held too long)

Lock Methods

// Acquire lock (returns Promise<string>)
const lockId = await dataStore.acquireLock('owner-id');

// Release lock
dataStore.releaseLock(lockId);

// Check if locked
const isLocked = dataStore.isLocked();

// Get current lock info
const lockInfo = dataStore.getCurrentLock();
// { lockId: string, ownerId: string, acquiredAt: number } | null

// Get queue length
const queueLength = dataStore.getQueueLength();

// Get lock statistics
const stats = dataStore.getLockStats();

Lock Statistics

const stats = dataStore.getLockStats();
// {
//   totalAcquisitions: number,
//   totalReleases: number,
//   totalTimeouts: number,
//   averageWaitTime: number,
//   queueLength: number,
//   isLocked: boolean,
//   currentLock: { lockId, ownerId, acquiredAt } | null,
//   queue: Array<{ lockId, ownerId }>
// }

Best Practices

1. Always Release: Use try/finally to ensure lock is released
2. Timeout Handling: Handle timeout errors appropriately
3. Owner ID: Use meaningful owner IDs for debugging
4. Lock Scope: Keep lock scope minimal (only during critical sections)

Model Integration

When using @barocss/model transactions, the TransactionManager automatically orchestrates DataStore's lock and overlay systems:

sequenceDiagram
    participant Model as Model Transaction
    participant Lock as DataStore Lock
    participant Overlay as DataStore Overlay
    participant Base as Base Nodes
    
    Model->>Lock: acquireLock()
    Lock-->>Model: lockId
    
    Model->>Overlay: begin()
    Note over Overlay: Initialize overlay
    
    loop Operations
        Model->>Overlay: Execute operation
        Overlay->>Base: Read (if needed)
        Overlay->>Overlay: Write to overlay
    end
    
    Model->>Overlay: end()
    Overlay-->>Model: AtomicOperation[]
    
    Model->>Overlay: commit()
    Overlay->>Base: Apply all changes
    
    Model->>Lock: releaseLock()
    Lock->>Lock: Grant to next

Key Points:

• Lock acquired before overlay begins
• All operations execute within overlay
• Commit applies all changes atomically
• Lock released after commit (in finally block)

For detailed integration flow, see Transaction Integration Guide.

Basic Usage

Creating a DataStore

import { DataStore } from '@barocss/datastore';
import { createSchema } from '@barocss/schema';
import type { INode } from '@barocss/datastore';

// Create schema
const schema = createSchema('basic-doc', {
  topNode: 'document',
  nodes: {
    document: { name: 'document', group: 'document', content: 'block+' },
    paragraph: { name: 'paragraph', group: 'block', content: 'inline*' },
    'inline-text': { name: 'inline-text', group: 'inline' }
  }
});

// Create DataStore with schema
const dataStore = new DataStore();
dataStore.registerSchema(schema);

// Create document tree
const root = dataStore.createNodeWithChildren({
  stype: 'document',
  content: [
    {
      stype: 'paragraph',
      content: [
        { stype: 'inline-text', text: 'Hello, World!' }
      ]
    }
  ]
} as INode);

dataStore.setRootNodeId(root.sid!);

Node Operations

// Get node
const node = dataStore.getNode('text-1');

// Update node
dataStore.updateNode('text-1', { text: 'Updated text' });

// Create node
const newNode = dataStore.createNode({
  stype: 'paragraph',
  content: []
});

// Delete node
dataStore.deleteNode('node-id');

Content Operations

// Add child
dataStore.content.addChild('parent-id', childNode, 0);

// Remove child
dataStore.content.removeChild('parent-id', 'child-id');

// Move node
dataStore.content.moveNode('node-id', 'new-parent-id', 0);

// Reorder children
dataStore.content.reorderChildren('parent-id', ['child-1', 'child-2', 'child-3']);

Block Operations

// Move block up/down
dataStore.moveBlockUp('block-id');
dataStore.moveBlockDown('block-id');

// Transform node type
dataStore.transformNode('node-id', 'heading', { level: 1 });

Transactions

Transactions use a Copy-on-Write overlay mechanism for efficient atomic operations:

// Begin transaction (initializes overlay)
dataStore.begin();

try {
  // All operations are written to overlay (not base)
  dataStore.updateNode('text-1', { text: 'New text' });
  dataStore.content.addChild('parent-id', newNode, 0);
  
  // End transaction (returns collected operations)
  const operations = dataStore.end();
  
  // Commit applies overlay to base
  dataStore.commit();
} catch (error) {
  // Rollback discards overlay without affecting base
  dataStore.rollback();
}

Transactions with Lock

For concurrent access, use the lock system:

// Acquire lock before transaction
const lockId = await dataStore.acquireLock('transaction-1');

try {
  dataStore.begin();
  dataStore.updateNode('text-1', { text: 'New text' });
  dataStore.commit();
} catch (error) {
  dataStore.rollback();
} finally {
  // Always release lock
  dataStore.releaseLock(lockId);
}

Collaborative Editing Integration

graph TB
    subgraph "Local Session A"
        A1["DataStore A<br/>sessionId: 0"]
        A2["User Input"]
        A3["Local Operations"]
        A4["TransactionalOverlay<br/>COW Operations"]
        A5["emitOperation<br/>AtomicOperation"]
    end
    
    subgraph "Local Session B"
        B1["DataStore B<br/>sessionId: 1"]
        B2["User Input"]
        B3["Local Operations"]
        B4["TransactionalOverlay<br/>COW Operations"]
        B5["emitOperation<br/>AtomicOperation"]
    end
    
    subgraph "Operation Structure"
        C1["AtomicOperation<br/>type: create|update|delete|move<br/>nodeId: sid<br/>data: INode snapshot<br/>timestamp: number<br/>parentId?: string<br/>position?: number"]
    end
    
    subgraph "Collaboration Layer"
        D1["Operation Broadcast<br/>CollaborationMessage"]
        D2["OT/CRDT Server<br/>Ordering & Transform"]
        D3["Conflict Resolution<br/>User > AI Priority"]
    end
    
    subgraph "Remote Sync"
        E1["onOperation Callback<br/>Receive Remote Ops"]
        E2["Apply to Local DataStore<br/>Merge with SID"]
        E3["Update Map&lt;sid, INode&gt;<br/>Maintain Consistency"]
    end
    
    A2 --> A3
    A3 --> A4
    A4 --> A5
    A5 --> C1
    
    B2 --> B3
    B3 --> B4
    B4 --> B5
    B5 --> C1
    
    C1 --> D1
    D1 --> D2
    D2 --> D3
    D3 --> E1
    
    E1 --> E2
    E2 --> E3
    E3 --> A1
    E3 --> B1
    
    style A1 fill:#e1f5ff
    style B1 fill:#e1f5ff
    style C1 fill:#fff4e1
    style D1 fill:#e8f5e9
    style D2 fill:#f3e5f5
    style D3 fill:#fce4ec
    style E1 fill:#fff9c4
    style E2 fill:#e0f2f1
    style E3 fill:#f1f8e9

Collaborative Editing Flow

1. Local Operations

   • User input triggers local operations in DataStore
   • Operations are collected in TransactionalOverlay (Copy-on-Write)
   • Each operation emits AtomicOperation event via emitOperation()

2. AtomicOperation Structure

   interface AtomicOperation {
     type: 'create' | 'update' | 'delete' | 'move';
     nodeId: string;        // SID reference
     data?: any;            // Node snapshot
     timestamp: number;
     parentId?: string;     // SID reference
     position?: number;
   }

3. Operation Broadcast

   • Operations are wrapped in CollaborationMessage and sent to server
   • Server applies OT/CRDT transformations for ordering
   • Conflict resolution follows priority: User > AI

4. Remote Synchronization

   • Remote operations received via onOperation() callback
   • Operations are applied to local DataStore using SID references
   • Map<sid, INode> is updated maintaining consistency across sessions

Key Integration Points

• SID Consistency: All sessions reference the same node using the same SID
• Operation Events: emitOperation() / onOperation() for operation lifecycle
• Transactional Overlay: COW mechanism ensures atomic operations
• Conflict Resolution: Operation-level conflict resolution, not node-level

Collaboration Adapters

For production use, consider using collaboration adapter packages which provide ready-to-use adapters for popular CRDT/OT libraries:

• @barocss/collaboration-yjs: Yjs WebSocket-based real-time collaboration
• @barocss/collaboration-liveblocks: Liveblocks managed collaboration infrastructure

All adapters are built on top of @barocss/collaboration which provides the core interfaces and base adapter.

Quick Integration Example

All adapters follow the same pattern: create the adapter, connect it to DataStore, and operations will automatically sync:

import { DataStore } from '@barocss/datastore';
import { YjsAdapter } from '@barocss/collaboration-yjs';
import * as Y from 'yjs';
import { WebsocketProvider } from 'y-websocket';

// 1. Create DataStore
const dataStore = new DataStore();

// 2. Set up collaboration backend (example: Yjs)
const ydoc = new Y.Doc();
const provider = new WebsocketProvider('ws://localhost:1234', 'room-id', ydoc);

// 3. Create and connect adapter
const adapter = new YjsAdapter({
  ydoc,
  config: { clientId: 'user-1' }
});

await adapter.connect(dataStore);

// 4. Operations are now automatically synced!
// - Local operations → sent to backend via adapter
// - Remote operations → applied to DataStore via adapter

How It Works

1. Local Operations: When DataStore emits operations via emitOperation(), the adapter captures them and sends to the collaboration backend
2. Remote Operations: When the backend receives operations from other clients, the adapter applies them to DataStore using applyOperationToDataStore() (which temporarily disables operation listeners to prevent circular updates)
3. SID Consistency: All clients use the same SID for the same node, ensuring consistent references across sessions

Choosing an Adapter

• Yjs: Best for WebSocket-based real-time collaboration with self-hosted or cloud servers
• Automerge: Best for peer-to-peer collaboration or when you need immutable document history
• Yorkie: Best for self-hosted or cloud-based collaboration with built-in presence features
• Liveblocks: Best for managed infrastructure with built-in authentication and presence

See individual adapter READMEs for detailed setup instructions and examples.

API Reference

DataStore Class

Constructor

new DataStore(rootNodeId?: string, schema?: Schema, sessionId?: number)

Methods

Node Management

• getNode(nodeId: string): INode | null - Get node by ID
• setNode(node: INode, validate?: boolean): void - Set/update node
• createNode(node: INode): INode - Create new node (assigns sid)
• createNodeWithChildren(node: INode): INode - Create node with children
• updateNode(nodeId: string, updates: Partial<INode>, validate?: boolean): void - Update node
• deleteNode(nodeId: string): void - Delete node
• transformNode(nodeId: string, newType: string, newAttrs?: Record<string, any>): ValidationResult - Transform node type

Content Management

• content.addChild(parentId: string, child: INode, position?: number): void - Add child
• content.removeChild(parentId: string, childId: string): boolean - Remove child
• content.moveNode(nodeId: string, newParentId: string, position?: number): void - Move node
• content.reorderChildren(parentId: string, childIds: string[]): void - Reorder children
• content.moveBlockUp(nodeId: string): boolean - Move block up
• content.moveBlockDown(nodeId: string): boolean - Move block down

Schema Management

• registerSchema(schema: Schema): void - Register schema
• getActiveSchema(): Schema | null - Get active schema
• setSchema(schema: Schema): void - Set active schema

Transaction Management

• begin(): void - Begin transaction (initializes overlay)
• end(): AtomicOperation[] - End transaction (returns collected operations)
• commit(): void - Commit transaction (applies overlay to base)
• rollback(): void - Rollback transaction (discards overlay)
• getCollectedOperations(): AtomicOperation[] - Get collected operations

Lock Management

• acquireLock(ownerId?: string): Promise<string> - Acquire global write lock
• releaseLock(lockId?: string): void - Release global write lock
• isLocked(): boolean - Check if lock is currently held
• getCurrentLock(): { lockId: string; ownerId: string; acquiredAt: number } | null - Get current lock info
• getQueueLength(): number - Get number of transactions waiting in queue
• getLockStats(): LockStats - Get lock statistics

Document Management

• setRootNodeId(nodeId: string): void - Set root node
• getRootNodeId(): string | null - Get root node ID
• getRootNode(): INode | null - Get root node

Operation Events

• emitOperation(operation: AtomicOperation): void - Emit operation event
• onOperation(callback: (operation: AtomicOperation) => void): void - Register operation listener
• offOperation(callback: (operation: AtomicOperation) => void): void - Unregister operation listener

Document Traversal & Iteration

• createDocumentIterator(options?: DocumentIteratorOptions): DocumentIterator - Create document iterator
• createRangeIterator(startNodeId: string, endNodeId: string, options?: RangeIteratorOptions): DocumentIterator - Create range-based iterator
• traverse(visitor: DocumentVisitor, options?: VisitorTraversalOptions): TraversalResult - Traverse with visitor pattern
• getNodesInRange(startNodeId: string, endNodeId: string, options?: RangeIteratorOptions): string[] - Get nodes in range
• getRangeNodeCount(startNodeId: string, endNodeId: string, options?: RangeIteratorOptions): number - Get node count in range

Serialization

• serializeRange(startNodeId: string, startOffset: number, endNodeId: string, endOffset: number): SerializedRange - Serialize range
• deserializeNodes(serialized: SerializedRange): INode[] - Deserialize nodes

Types

INode

interface INode {
  sid?: string;           // Stable ID (assigned by DataStore)
  stype: string;          // Schema type
  text?: string;          // Text content (for text nodes)
  attributes?: Record<string, any>;  // Node attributes
  content?: string[];     // Child node IDs
  parentId?: string;      // Parent node ID
  marks?: IMark[];        // Text marks
}

IMark

interface IMark {
  type: string;           // Mark type (bold, italic, etc.)
  range: [number, number]; // Text range [start, end]
  attrs?: Record<string, any>;  // Mark attributes
}

AtomicOperation

interface AtomicOperation {
  type: 'create' | 'update' | 'delete' | 'move';
  nodeId: string;        // SID reference
  data?: any;            // Node snapshot
  timestamp: number;
  parentId?: string;     // SID reference
  position?: number;     // Position in parent content
}

LockStats

interface LockStats {
  totalAcquisitions: number;    // Total number of lock acquisitions
  totalReleases: number;        // Total number of lock releases
  totalTimeouts: number;        // Total number of timeout errors
  averageWaitTime: number;      // Average wait time in milliseconds
  queueLength: number;          // Current queue length
  isLocked: boolean;            // Whether lock is currently held
  currentLock: {                // Current lock info (null if unlocked)
    lockId: string;
    ownerId: string;
    acquiredAt: number;
  } | null;
  queue: Array<{                // Queued transactions
    lockId: string;
    ownerId: string;
  }>;
}

DocumentIteratorOptions

interface DocumentIteratorOptions {
  startNodeId?: string;              // Start node (default: root)
  reverse?: boolean;                 // Reverse traversal
  maxDepth?: number;                 // Maximum depth limit
  filter?: {
    stype?: string;                  // Single type filter
    stypes?: string[];               // Multiple types filter
    excludeTypes?: string[];         // Excluded types
  };
  customFilter?: (nodeId: string, node: INode) => boolean;
  shouldStop?: (nodeId: string, node: INode) => boolean;
  range?: {
    startNodeId: string;
    endNodeId: string;
    includeStart?: boolean;
    includeEnd?: boolean;
  };
}

DocumentVisitor

interface DocumentVisitor {
  visit(nodeId: string, node: INode, context?: any): void | boolean;
  enter?(nodeId: string, node: INode, context?: any): void;
  exit?(nodeId: string, node: INode, context?: any): void;
  shouldVisitChildren?(nodeId: string, node: INode): boolean;
}

VisitorTraversalOptions

interface VisitorTraversalOptions {
  startNodeId?: string;
  reverse?: boolean;
  maxDepth?: number;
  filter?: {
    stype?: string;
    stypes?: string[];
    excludeTypes?: string[];
  };
  customFilter?: (nodeId: string, node: INode) => boolean;
  shouldStop?: (nodeId: string, node: INode) => boolean;
  range?: {
    startNodeId: string;
    endNodeId: string;
    includeStart?: boolean;
    includeEnd?: boolean;
  };
  context?: any;
}

TraversalResult

interface TraversalResult {
  visitedCount: number;    // Number of nodes visited
  skippedCount: number;    // Number of nodes skipped
  stopped: boolean;        // Whether traversal was stopped early
}

Document Traversal & Iteration

DataStore provides powerful document traversal capabilities through iterators and visitor patterns for efficient document processing.

DocumentIterator

DocumentIterator implements the standard JavaScript IterableIterator<string> interface, allowing you to traverse the document tree using for...of loops.

Basic Usage

// Basic traversal
const iterator = dataStore.createDocumentIterator();

for (const nodeId of iterator) {
  const node = dataStore.getNode(nodeId);
  console.log(`${nodeId}: ${node.stype}`);
}

Filtering Options

// Filter by node type
const textIterator = dataStore.createDocumentIterator({
  filter: { stype: 'inline-text' }
});

// Filter by multiple types
const blockIterator = dataStore.createDocumentIterator({
  filter: { stypes: ['paragraph', 'heading'] }
});

// Exclude certain types
const contentIterator = dataStore.createDocumentIterator({
  filter: { excludeTypes: ['document'] }
});

// Custom filter function
const customIterator = dataStore.createDocumentIterator({
  customFilter: (nodeId, node) => {
    return node.attributes?.level === 1;
  }
});

Depth and Direction Control

// Limit depth
const shallowIterator = dataStore.createDocumentIterator({
  maxDepth: 2
});

// Reverse traversal
const reverseIterator = dataStore.createDocumentIterator({
  reverse: true
});

// Start from specific node
const subtreeIterator = dataStore.createDocumentIterator({
  startNodeId: 'paragraph-1'
});

Range-Based Iteration

// Create range iterator
const rangeIterator = dataStore.createRangeIterator('0:2', '0:6');

for (const nodeId of rangeIterator) {
  const node = dataStore.getNode(nodeId);
  console.log(nodeId, node);
}

// Exclude boundaries
const innerRangeIterator = dataStore.createRangeIterator('0:2', '0:6', {
  includeStart: false,
  includeEnd: false
});

// With filtering
const filteredRangeIterator = dataStore.createRangeIterator('0:2', '0:6', {
  filter: { stype: 'inline-text' }
});

// Convenience methods
const nodesInRange = dataStore.getNodesInRange('0:2', '0:6');
const count = dataStore.getRangeNodeCount('0:2', '0:6');

Visitor Pattern

The visitor pattern allows you to perform operations while traversing the document:

// Single visitor
const result = dataStore.traverse({
  visit: (nodeId, node) => {
    console.log(`Visiting: ${nodeId} (${node.stype})`);
  },
  enter: (nodeId, node) => {
    console.log(`Entering: ${nodeId}`);
  },
  exit: (nodeId, node) => {
    console.log(`Exiting: ${nodeId}`);
  },
  shouldVisitChildren: (nodeId, node) => {
    // Skip children of inline-text nodes
    return node.stype !== 'inline-text';
  }
});

console.log(result); // { visitedCount: 5, skippedCount: 0, stopped: false }

Multiple Visitors

class TextExtractor {
  private texts: string[] = [];
  visit(nodeId: string, node: any) {
    if (node.stype === 'inline-text' && node.text) {
      this.texts.push(node.text);
    }
  }
  getTexts() { return this.texts; }
}

class LinkCollector {
  private links: Array<{nodeId: string, href: string}> = [];
  visit(nodeId: string, node: any) {
    if (node.marks) {
      const linkMark = node.marks.find((m: any) => m.type === 'link');
      if (linkMark) {
        this.links.push({ nodeId, href: linkMark.attrs?.href || '' });
      }
    }
  }
  getLinks() { return this.links; }
}

// Execute multiple visitors in one traversal
const textExtractor = new TextExtractor();
const linkCollector = new LinkCollector();

const results = dataStore.traverse(textExtractor, linkCollector);

console.log('Texts:', textExtractor.getTexts());
console.log('Links:', linkCollector.getLinks());

Iterator Options

interface DocumentIteratorOptions {
  startNodeId?: string;              // Start node (default: root)
  reverse?: boolean;                 // Reverse traversal
  maxDepth?: number;                 // Maximum depth limit
  filter?: {
    stype?: string;                  // Single type filter
    stypes?: string[];               // Multiple types filter
    excludeTypes?: string[];         // Excluded types
  };
  customFilter?: (nodeId: string, node: INode) => boolean;
  shouldStop?: (nodeId: string, node: INode) => boolean;
  range?: {
    startNodeId: string;
    endNodeId: string;
    includeStart?: boolean;
    includeEnd?: boolean;
  };
}

Visitor Interface

interface DocumentVisitor {
  visit(nodeId: string, node: INode, context?: any): void | boolean;
  enter?(nodeId: string, node: INode, context?: any): void;
  exit?(nodeId: string, node: INode, context?: any): void;
  shouldVisitChildren?(nodeId: string, node: INode): boolean;
}

Performance Characteristics

• Time Complexity: O(n) for full traversal, O(r) for range-based (r ≤ n)
• Space Complexity: O(n) for visited tracking, O(r) for range-based
• Node Lookup: O(1) using Map-based storage
• Filtering: O(1) per node check

Use Cases

1. Text Extraction: Extract all text content from document
2. Link Collection: Find all links in document
3. Structure Analysis: Analyze document hierarchy
4. Range Operations: Process specific document sections
5. Statistics: Collect node type statistics
6. Search: Find nodes matching specific criteria

For detailed documentation, see Document Iterator Specification and Model Traversal API.

Advanced Features

Drop Behavior

Define custom drop behavior for draggable nodes:

import { defineDropBehavior } from '@barocss/datastore';

defineDropBehavior('image', {
  canDrop: (source, target) => {
    return target.stype === 'paragraph';
  },
  onDrop: (source, target, position) => {
    // Custom drop logic
  }
});

Performance Optimization

Batch Operations with Overlay

The Copy-on-Write overlay allows efficient batching:

// Begin transaction (O(1) - no copying)
dataStore.begin();

// Multiple operations (only modified nodes are duplicated)
dataStore.updateNode('node-1', { text: 'Updated' });
dataStore.updateNode('node-2', { text: 'Updated' });
dataStore.createNode({ stype: 'paragraph', text: 'New' });

// End returns operations, commit applies atomically
const operations = dataStore.end();
dataStore.commit(); // All changes applied in one go

Benefits

• O(1) Transaction Start: No copying on begin()
• Memory Efficient: Only modified nodes are duplicated
• Atomic Commit: All changes applied together
• Operation Collection: All operations collected for sync/collaboration

Testing

cd packages/datastore
pnpm test:run

Documentation

Implementation Guides

• Transaction Integration Guide - How Model transactions integrate with DataStore lock and overlay systems
• Document Iterator Specification - Detailed specification of DocumentIterator traversal logic and algorithms
• Model Traversal API - Complete API reference for document traversal and navigation

Design Decisions

• Drop Behavior Architecture - Design rationale for drop behavior system (hybrid approach: schema + defineDropBehavior)
• Node Type Specifications - Specifications for draggable, droppable, editable, and selectable nodes

License

MIT