History Management Optimization – Editor Architecture

Overview

Storing full model snapshots for every history entry is memory-intensive and slow. Operation-based history management stores only operations and their inverses, dramatically reducing memory usage and improving performance.

Problem: Full model snapshots are expensive

Large memory footprint (full document × history size)
Slow clone operations for large documents
Garbage collection pressure
Poor scalability with document size

The Problem with Full Model Snapshots

Storing complete model clones for each history entry:

// ❌ BAD: Storing full model snapshots
interface HistoryEntry {
  operations: Operation[];
  beforeModel: DocumentModel; // Full clone - expensive!
  afterModel: DocumentModel;  // Full clone - expensive!
  beforeSelection: Selection;
  afterSelection: Selection;
}

class HistoryManager {
  #undoStack: HistoryEntry[] = [];
  
  record(operations: Operation[]) {
    const beforeModel = this.model.clone(); // Expensive!
    
    // Apply operations
    operations.forEach(op => this.model.apply(op));
    
    const afterModel = this.model.clone(); // Expensive!
    
    this.#undoStack.push({
      operations,
      beforeModel,  // Storing full document
      afterModel,   // Storing full document
      // ...
    });
  }
  
  undo() {
    const entry = this.#undoStack.pop()!;
    // Restore full model - also expensive
    this.model = entry.beforeModel.clone();
  }
}

// Memory usage: O(history_size × document_size)
// For 50 history entries with 1MB document = 50MB+ memory

This approach doesn't scale. A document with 10,000 nodes and 50 history entries would require storing 500,000 node copies.

Operation-Based History

Store only operations and apply their inverses for undo:

Using Inverse Operations

// ✅ GOOD: Operation-based history
interface HistoryEntry {
  operations: Operation[];
  inverseOperations: Operation[]; // Pre-computed inverses
  beforeSelection: Selection;
  afterSelection: Selection;
  // NO model snapshots!
}

class HistoryManager {
  #undoStack: HistoryEntry[] = [];
  #redoStack: HistoryEntry[] = [];
  #model: DocumentModel; // Single current model
  
  record(operations: Operation[]) {
    const beforeSelection = this.#model.getSelection();
    
    // Apply operations
    operations.forEach(op => this.#model.apply(op));
    
    const afterSelection = this.#model.getSelection();
    
    // Compute inverse operations
    const inverseOperations = operations
      .slice()
      .reverse()
      .map(op => this.#getInverseOperation(op));
    
    this.#undoStack.push({
      operations,
      inverseOperations,
      beforeSelection,
      afterSelection
    });
    
    this.#redoStack = []; // Clear redo on new action
  }
  
  undo(): boolean {
    if (this.#undoStack.length === 0) {
      return false;
    }
    
    const entry = this.#undoStack.pop()!;
    
    // Apply inverse operations (in reverse order)
    for (let i = entry.inverseOperations.length - 1; i >= 0; i--) {
      this.#model.apply(entry.inverseOperations[i]);
    }
    
    this.#model.setSelection(entry.beforeSelection);
    
    // Move to redo stack
    this.#redoStack.push(entry);
    return true;
  }
  
  redo(): boolean {
    if (this.#redoStack.length === 0) {
      return false;
    }
    
    const entry = this.#redoStack.pop()!;
    
    // Re-apply operations
    entry.operations.forEach(op => {
      this.#model.apply(op);
    });
    
    this.#model.setSelection(entry.afterSelection);
    
    // Move to undo stack
    this.#undoStack.push(entry);
    return true;
  }
  
  #getInverseOperation(op: Operation): Operation {
    switch (op.type) {
      case 'insertText':
        return {
          type: 'deleteText',
          path: op.path,
          length: op.text.length,
          deletedContent: op.text // Store for redo
        };
      
      case 'deleteText':
        return {
          type: 'insertText',
          path: op.path,
          text: op.deletedContent || ''
        };
      
      case 'insertNode':
        return {
          type: 'deleteNode',
          path: op.path,
          deletedNode: op.node // Store for redo
        };
      
      case 'deleteNode':
        return {
          type: 'insertNode',
          path: op.path,
          node: op.deletedNode
        };
      
      case 'applyFormat':
        return {
          type: 'removeFormat',
          path: op.path,
          length: op.length,
          format: op.format,
          previousValue: this.#model.getFormatAt(op.path, op.format)
        };
      
      case 'removeFormat':
        return {
          type: 'applyFormat',
          path: op.path,
          length: op.length,
          format: op.format,
          value: op.previousValue
        };
      
      default:
        throw new Error(`Unknown operation: ${op.type}`);
    }
  }
}

// Memory usage: O(history_size × operation_size)
// For 50 history entries with ~10 operations each = ~few KB
// vs 50MB+ with full snapshots!

Memory Efficiency

Operation-based approach is orders of magnitude more efficient:

// Example: User types "Hello World"
// Full snapshot approach:
// - beforeModel: ~1MB (full document)
// - afterModel: ~1MB (full document)
// Total: ~2MB per entry

// Operation-based approach:
const entry = {
  operations: [
    { type: 'insertText', path: [0, 5], text: 'H' },
    { type: 'insertText', path: [0, 6], text: 'e' },
    { type: 'insertText', path: [0, 7], text: 'l' },
    { type: 'insertText', path: [0, 8], text: 'l' },
    { type: 'insertText', path: [0, 9], text: 'o' },
    { type: 'insertText', path: [0, 10], text: ' ' },
    { type: 'insertText', path: [0, 11], text: 'W' },
    { type: 'insertText', path: [0, 12], text: 'o' },
    { type: 'insertText', path: [0, 13], text: 'r' },
    { type: 'insertText', path: [0, 14], text: 'l' },
    { type: 'insertText', path: [0, 15], text: 'd' }
  ],
  inverseOperations: [/* 11 inverse operations */]
};
// Total: ~few hundred bytes vs 2MB!

// Memory savings: 99.9%+ reduction

Hybrid Approach

For very long undo chains, combine operation-based history with periodic snapshots:

Periodic Snapshots

class HybridHistoryManager {
  #undoStack: HistoryEntry[] = [];
  #checkpoints: Map<number, DocumentModel> = new Map();
  #checkpointInterval = 20; // Create snapshot every 20 entries
  
  record(operations: Operation[]) {
    const entryIndex = this.#undoStack.length;
    
    // Create checkpoint periodically
    if (entryIndex % this.#checkpointInterval === 0) {
      this.#checkpoints.set(entryIndex, this.#model.clone());
    }
    
    // Store operations (not full model)
    const entry: HistoryEntry = {
      operations,
      inverseOperations: this.#computeInverses(operations),
      checkpointIndex: entryIndex,
      // ...
    };
    
    this.#undoStack.push(entry);
  }
  
  undo(): boolean {
    if (this.#undoStack.length === 0) {
      return false;
    }
    
    const entry = this.#undoStack.pop()!;
    
    // Check if we have a checkpoint nearby
    const nearestCheckpoint = this.#findNearestCheckpoint(entry.checkpointIndex);
    
    if (nearestCheckpoint && this.#shouldUseCheckpoint(entry, nearestCheckpoint)) {
      // Restore from checkpoint and replay operations
      this.#restoreFromCheckpoint(nearestCheckpoint, entry);
    } else {
      // Use inverse operations (normal case)
      this.#applyInverseOperations(entry.inverseOperations);
    }
    
    return true;
  }
  
  #shouldUseCheckpoint(entry: HistoryEntry, checkpoint: number): boolean {
    // Use checkpoint if we need to undo many operations
    const distance = entry.checkpointIndex - checkpoint;
    return distance > 10; // Threshold for checkpoint usage
  }
  
  #restoreFromCheckpoint(checkpointIndex: number, targetEntry: HistoryEntry) {
    const checkpoint = this.#checkpoints.get(checkpointIndex)!;
    this.#model = checkpoint.clone();
    
    // Replay operations from checkpoint to target
    const entries = this.#undoStack.slice(checkpointIndex, targetEntry.checkpointIndex);
    entries.forEach(e => {
      e.operations.forEach(op => this.#model.apply(op));
    });
  }
}

Checkpoint System

// Checkpoint strategy: Store snapshots at strategic points
class CheckpointManager {
  #checkpoints: Map<number, DocumentModel> = new Map();
  #maxCheckpoints = 5; // Limit number of checkpoints
  
  createCheckpoint(index: number, model: DocumentModel) {
    // Remove oldest checkpoint if limit reached
    if (this.#checkpoints.size >= this.#maxCheckpoints) {
      const oldest = Math.min(...this.#checkpoints.keys());
      this.#checkpoints.delete(oldest);
    }
    
    this.#checkpoints.set(index, model.clone());
  }
  
  getNearestCheckpoint(targetIndex: number): [number, DocumentModel] | null {
    let nearest: [number, DocumentModel] | null = null;
    let minDistance = Infinity;
    
    for (const [index, model] of this.#checkpoints) {
      if (index <= targetIndex) {
        const distance = targetIndex - index;
        if (distance < minDistance) {
          minDistance = distance;
          nearest = [index, model];
        }
      }
    }
    
    return nearest;
  }
  
  // Cleanup old checkpoints
  cleanup(beforeIndex: number) {
    for (const index of this.#checkpoints.keys()) {
      if (index < beforeIndex) {
        this.#checkpoints.delete(index);
      }
    }
  }
}

Performance Comparison

Metric	Full Snapshots	Operation-Based	Hybrid
Memory per entry	~1-10MB	~1-10KB	~1-10KB + periodic snapshots
Record time	Slow (clone)	Fast (operations only)	Fast (periodic clone)
Undo time	Fast (restore)	Fast (apply inverses)	Fast (checkpoint or inverses)
Scalability	Poor (O(n×m))	Excellent (O(n))	Excellent (O(n))

Implementation

Complete implementation example:

class OptimizedHistoryManager {
  #undoStack: HistoryEntry[] = [];
  #redoStack: HistoryEntry[] = [];
  #model: DocumentModel;
  #maxSize = 100;
  
  constructor(model: DocumentModel) {
    this.#model = model;
  }
  
  recordTransaction(transaction: Transaction) {
    const operations = transaction.getOperations();
    const beforeSelection = transaction.getBeforeSelection();
    const afterSelection = transaction.getAfterSelection();
    
    // Compute inverse operations
    const inverseOperations = this.#computeInverseOperations(operations);
    
    const entry: HistoryEntry = {
      id: generateId(),
      timestamp: Date.now(),
      operations,
      inverseOperations,
      beforeSelection,
      afterSelection
      // NO model snapshots!
    };
    
    this.#undoStack.push(entry);
    
    // Limit stack size
    if (this.#undoStack.length > this.#maxSize) {
      this.#undoStack.shift();
    }
    
    this.#redoStack = [];
  }
  
  undo(): boolean {
    if (this.#undoStack.length === 0) {
      return false;
    }
    
    const entry = this.#undoStack.pop()!;
    
    // Apply inverse operations in reverse order
    for (let i = entry.inverseOperations.length - 1; i >= 0; i--) {
      const inverseOp = entry.inverseOperations[i];
      this.#model.apply(inverseOp);
    }
    
    this.#model.setSelection(entry.beforeSelection);
    this.#redoStack.push(entry);
    
    return true;
  }
  
  redo(): boolean {
    if (this.#redoStack.length === 0) {
      return false;
    }
    
    const entry = this.#redoStack.pop()!;
    
    // Re-apply operations
    for (const op of entry.operations) {
      this.#model.apply(op);
    }
    
    this.#model.setSelection(entry.afterSelection);
    this.#undoStack.push(entry);
    
    return true;
  }
  
  #computeInverseOperations(operations: Operation[]): Operation[] {
    // Need to compute inverses in reverse order
    // and capture state before each operation
    const inverses: Operation[] = [];
    
    for (let i = operations.length - 1; i >= 0; i--) {
      const op = operations[i];
      const inverse = this.#getInverseOperation(op);
      inverses.unshift(inverse); // Add to beginning
    }
    
    return inverses;
  }
  
  #getInverseOperation(op: Operation): Operation {
    // Implementation depends on operation type
    // Must capture necessary state (e.g., deleted content)
    switch (op.type) {
      case 'insertText':
        return {
          type: 'deleteText',
          path: op.path,
          length: op.text.length
        };
      
      case 'deleteText':
        // Must have stored deletedContent in original operation
        return {
          type: 'insertText',
          path: op.path,
          text: op.deletedContent!
        };
      
      // ... other operation types
    }
  }
  
  // Optional: Get current model state (for debugging)
  getCurrentModel(): DocumentModel {
    return this.#model;
  }
  
  // Optional: Clear history
  clear() {
    this.#undoStack = [];
    this.#redoStack = [];
  }
}

Best Practices

Always store inverse operations: Pre-compute inverses when recording to avoid computation during undo
Store deleted content: Delete operations must store deleted content for proper undo
Store previous values: Format operations should store previous format values
Limit history size: Remove old entries to prevent unbounded memory growth
Use checkpoints for long chains: For very long undo chains, use hybrid approach with periodic snapshots
Validate operations: Ensure operations are valid before applying inverses
Handle edge cases: Consider empty operations, invalid paths, and boundary conditions

History Management

History management overview

Transaction System

Using transactions

Operations

Operation types