This technical specification outlines the architecture, implementation patterns, and design principles for building FormulaEngine, a high-performance, TypeScript-based formula engine library similar to HyperFormula. The specification synthesizes insights from leading implementations including HyperFormula, EtherCalc, Apache POI, and academic research to create a state-of-the-art sparse-aware formula engine with array formula support and broadcasting semantics.

FormulaEngine will be a headless, extensible calculation engine designed for modern web applications requiring sophisticated spreadsheet-like computational capabilities. The library prioritizes Excel compatibility, performance optimization, and developer experience through TypeScript's advanced type system.

FormulaEngine adopts HyperFormula's proven three-phase architecture with significant enhancements for sparse data handling and array operations:

Phase 1: Parsing and AST Construction

• Chevrotain-based parser provides superior performance over traditional parser generators while maintaining flexibility for complex formula syntax
• Direct AST construction during parsing eliminates intermediate representations and reduces memory overhead
• Relative addressing optimization stores formulas using relative cell references ([0][+3] + [+1][-1]) to enable AST reuse and reduce memory consumption by up to 70%
• Context-sensitive parsing handles complex scenarios including sheet references, named expressions, and array formulas

Phase 2: Dependency Graph Management

• Optimized dependency tracking uses directed acyclic graphs (DAGs) with range decomposition to avoid O(n²) complexity patterns
• Associative operation optimization transforms range operations like SUM(A1:A100) into incremental calculations B1=A1, B2=B1+A2, B3=B2+A3 reducing complexity from O(n²) to O(n)
• Strongly Connected Components (SCC) analysis for efficient circular reference detection using Tarjan's algorithm
• Incremental graph updates maintain dependency relationships efficiently during sheet modifications

Phase 3: Evaluation Engine

• Sparse-aware evaluation processes only non-empty cells, providing dramatic performance improvements for typical spreadsheets (which use <1% of theoretical capacity)
• Hybrid lazy/eager evaluation strategy optimizes for both immediate results and computation efficiency
• Multi-level caching includes AST caching, computed value caching, and intermediate result memoization

Progressive Type Safety:

// FormulaEngine core interface with progressive building
interface FormulaEngineBuilder<TState = {}> {
  addSheet<K extends string>(
    name: K
  ): FormulaEngineBuilder<TState & Record<K, Sheet>>;
  setCell(address: SimpleCellAddress, value: CellValue): FormulaEngineBuilder<TState>;
  build(): FormulaEngine<TState>;
}

// Type-safe cell addressing
export interface SimpleCellAddress {
  sheet: number;
  col: number;
  row: number;
}

// Union type for all possible cell values
type CellValue = number | string | boolean | FormulaError | undefined;

Dynamic Array Architecture:

• Spilling behavior automatically expands array results into neighboring cells with conflict detection
• Broadcasting rules follow NumPy semantics: smaller arrays are padded with repetitions, 1×n arrays expand to match output dimensions
• Vectorized operations apply scalar functions element-wise to arrays for optimal performance

Matrix Operations Implementation:

• MMULT function supports matrix multiplication with proper dimension validation and error handling
• Element-wise operations handle broadcasting for operations like A1:A3 * B1:B3 and A1:A3 * B1
• Memory-efficient matrix storage uses sparse representations for large matrices with limited non-zero elements

Array Formula Evaluation Algorithm:

class ArrayFormulaEvaluator {
  evaluate(formula: ArrayFormula): ArrayResult {
    // 1. Dimension analysis and compatibility checking
    const dimensions = this.analyzeDimensions(formula.operands);

    // 2. Broadcasting application using NumPy rules
    const broadcasted = this.applyBroadcasting(formula.operands, dimensions);

    // 3. Vectorized function application
    const result = this.vectorizeOperation(formula.operation, broadcasted);

    // 4. Spill range validation and result population
    return this.populateSpillRange(result, formula.outputRange);
  }
}

Hierarchical Scope Resolution:

• Global workbook scope for names accessible across all worksheets
• Local worksheet scope with override capabilities for sheet-specific names
• Priority-based resolution algorithm: local names override global names within their scope

Circular Dependency Prevention:

• Real-time validation prevents creation of names that would create circular references
• Dependency graph integration treats named expressions as first-class nodes in the dependency system

Reference Transformation Algorithm:

interface ReferenceTransformer {
  transformReferences(
    formula: string,
    sourceAddress: SimpleCellAddress,
    targetAddress: SimpleCellAddress
  ): string;
}

// Handles relative ($A1), absolute ($A$1), and mixed (A$1, $A1) references
class SmartReferenceTransformer implements ReferenceTransformer {
  transformReferences(
    formula: string,
    source: SimpleCellAddress,
    target: SimpleCellAddress
  ): string {
    const offset = this.calculateOffset(source, target);
    return this.parseAndTransform(formula, offset);
  }
}

Sparse Data Structures:

• Compressed Sparse Row (CSR) format for row-oriented operations with O(1) row access
• Dictionary of Keys (DOK) using hash maps for random access and efficient modifications
• Adaptive storage switches between dense and sparse representations based on data density

Only Non-Empty Cell Processing:

• Used range tracking limits computation boundaries to actual data regions
• Smart range operations skip empty cells entirely rather than checking and ignoring them
• Memory overhead reduction stores only non-zero/non-empty values with coordinate indexing

Comprehensive Caching Architecture:

class FormulaEngineCache {
  // AST-level caching for formula reuse
  private astCache = new LRUCache<string, ASTNode>(1000);

  // Result caching for expensive calculations
  private resultCache = new LRUCache<string, CellValue>(5000);

  // Function-specific memoization
  private functionCache = new WeakMap<Function, Map<string, any>>();

  // Dependency-aware invalidation
  invalidateDependencies(address: SimpleCellAddress): void {
    const dependents = this.dependencyGraph.getDependents(address);
    dependents.forEach((dep) =>
      this.resultCache.delete(this.addressToKey(dep))
    );
  }
}

Memory Optimization Patterns:

• Object pooling for frequently allocated temporary objects
• String interning for repeated text values and formula patterns
• Garbage collection optimization using generational collection strategies

Change Propagation System:

• Dirty cell tracking marks affected cells when dependencies change
• Topological sort optimization pre-computes calculation order for efficiency
• Batch update support processes multiple changes efficiently to minimize recalculation overhead

Core Plugin Interface:

interface FormulaPlugin {
  name: string;
  functions: Record<string, FormulaFunction>;
  initialize(engine: FormulaEngine): void;
}

// Type-safe function registration
interface FunctionDefinition<
  TArgs extends unknown[] = unknown[],
  TReturn = unknown,
> {
  name: string;
  args: readonly [...TArgs];
  returnType: TReturn;
  execute: (...args: TArgs) => TReturn;
  validate?: (args: TArgs) => boolean;
}

class FunctionRegistry {
  register<TArgs extends unknown[], TReturn>(
    definition: FunctionDefinition<TArgs, TReturn>
  ): void {
    this.functions.set(definition.name, definition);
  }
}

Extensible Architecture Benefits:

• Compile-time type safety for all plugin interactions
• Runtime validation with comprehensive error reporting
• Hot-swappable plugins for dynamic functionality updates

Type-Safe Error Management:

type Result<T, E = Error> =
  | { success: true; data: T }
  | { success: false; error: E };

class FormulaEvaluator {
  evaluate(formula: string): Result<CellValue, FormulaError> {
    try {
      const result = this.parseAndEvaluate(formula);
      return { success: true, data: result };
    } catch (error) {
      return {
        success: false,
        error: new FormulaError(error.message, formula),
      };
    }
  }
}

Error Propagation Architecture:

• Hierarchical error types with specific error codes (#REF!, #VALUE!, #DIV/0!, etc.)
• Error recovery mechanisms using IFERROR and similar functions
• Contextual error reporting with formula location and dependency information

Type-Safe Command System:

interface Command {
  execute(): CommandResult;
  undo(): CommandResult;
  redo(): CommandResult;
}

class UpdateCellCommand implements Command {
  constructor(
    private address: SimpleCellAddress,
    private newValue: CellValue,
    private oldValue?: CellValue
  ) {}

  execute(): CommandResult {
    this.oldValue = this.engine.getCellValue(this.address);
    this.engine.setCellValue(this.address, this.newValue);
    return { success: true, canUndo: true };
  }

  undo(): CommandResult {
    this.engine.setCellValue(this.address, this.oldValue);
    return { success: true, canRedo: true };
  }
}

Progressive API Building:

const engine = FormulaEngine.create()
  .addSheet("Calculator")
  .setCell({ sheet: 0, row: 0, col: 0 }, "=SUM(A2:A10)")
  .addNamedExpression("TaxRate", "0.08")
  .build();

Event-Driven Architecture:

FormulaEngine implements a hybrid event system combining efficient cell/sheet update handling with traditional event emitting for structural changes:

Cell-Level Events:

• Immediate notification for individual cell changes
• Efficient listener mapping using cell addresses as keys
• Automatic cleanup when listeners are removed
• Supports granular reactivity for UI components

Sheet-Level Events:

• Batched notifications delivered at completion of operations
• Collects multiple changes across sheets during batch operations
• Triggered only at the end of setCellContent and setSheetContent calls
• Optimizes performance by avoiding excessive event firing during bulk updates

Sheet Management Events:

• Traditional event emitter pattern for structural changes
• Immediate emission for sheet-added, sheet-removed, and sheet-renamed events
• Simple event payload with relevant sheet information
• Standard EventEmitter interface for compatibility with existing patterns

Listener Management Strategy:

• Maps maintain only active listeners for cell/sheet updates, eliminating unnecessary triggering
• Traditional event listeners for sheet management events
• Automatic memory management with cleanup functions for mapped listeners
• Supports both specific cell subscriptions and sheet-wide monitoring
• Cross-sheet change collection for comprehensive update notifications

Event Timing Design:

• Cell listeners: Immediate firing for real-time responsiveness
• Sheet listeners: Deferred firing for batch efficiency
• Sheet management listeners: Immediate firing for structural changes
• Change collection during operations to ensure consistency
• Single notification per sheet regardless of number of changes within operation

Example:

type CellUpdateEvent = {
  address: SimpleCellAddress;
  oldValue: CellValue;
  newValue: CellValue;
};

interface FormulaEngineEvents {
  "sheet-added": {
    sheetId: number;
    sheetName: string;
  };
  "sheet-removed": {
    sheetId: number;
    sheetName: string;
  };
  "sheet-renamed": {
    sheetId: number;
    oldName: string;
    newName: string;
  };
}

type CellUpdateListener = (event: CellUpdateEvent) => void;
type CellsUpdateListener = (events: CellUpdateEvent[]) => void;

class FormulaEngine  {
  // Maps for efficient listener management - only active listeners are triggered
  private cellUpdateListeners = new Map<string, Set<CellUpdateListener>>();
  private cellsUpdateListeners = new Map<number, Set<CellsUpdateListener>>();

  renameSheet(sheetId: number, newName: string): void {
    if (!this.isItPossibleToRenameSheet(sheetId, newName)) return;

    const sheet = this.sheets.get(sheetId);
    if (sheet) {
      const oldName = sheet.name;
      sheet.name = newName;

      // Emit sheet-renamed event
      this.emit("sheet-renamed", {
        sheetId,
        oldName,
        newName,
      });
    }
  }

  // Register listener for specific cell updates
  onCellUpdate(address: SimpleCellAddress, listener: CellUpdateListener): () => void {
    const key = this.addressToKey(address);
    if (!this.cellUpdateListeners.has(key)) {
      this.cellUpdateListeners.set(key, new Set());
    }
    this.cellUpdateListeners.get(key)!.add(listener);

    // Return cleanup function
    return () => {
      const listeners = this.cellUpdateListeners.get(key);
      if (listeners) {
        listeners.delete(listener);
        if (listeners.size === 0) {
          this.cellUpdateListeners.delete(key);
        }
      }
    };
  }

  // Register listener for sheet-wide updates
  onCellsUpdate(sheetId: number, listener: CellsUpdateListener): () => void {
    if (!this.cellsUpdateListeners.has(sheetId)) {
      this.cellsUpdateListeners.set(sheetId, new Set());
    }
    this.cellsUpdateListeners.get(sheetId)!.add(listener);

    // Return cleanup function
    return () => {
      const listeners = this.cellsUpdateListeners.get(sheetId);
      if (listeners) {
        listeners.delete(listener);
        if (listeners.size === 0) {
          this.cellsUpdateListeners.delete(sheetId);
        }
      }
    };
  }

  // Public API method for single cell updates
  setCellContent(address: SimpleCellAddress, value: CellValue): void {
    // ...current code
    this.flushSheetUpdates();
  }

  // Public API method for batch updates
  setSheetContent(
    updates: Array<{ address: SimpleCellAddress; value: CellValue }>
  ): void {
    // ...current code
    this.flushSheetUpdates();
  }

  // Sheet management methods with traditional event emission
  addSheet(name: string): number {
    const sheetId = this.createSheet(name);
    this.emit('sheet-added', { sheetId, name });
    return sheetId;
  }

  removeSheet(sheetId: number): void {
    const name = this.getSheetName(sheetId);
    this.deleteSheet(sheetId);
    this.emit('sheet-removed', { sheetId, name });
  }

  renameSheet(sheetId: number, newName: string): void {
    const oldName = this.getSheetName(sheetId);
    this.updateSheetName(sheetId, newName);
    this.emit('sheet-renamed', { sheetId, oldName, newName });
  }

  private addressToKey(address: SimpleCellAddress): string {
    return `${address.sheet}:${address.row}:${address.col}`;
  }
}

Multi-Layer Testing Architecture:

• Unit testing for individual functions and components with Jest
• Integration testing for complex dependency chains and edge cases
• Property-based testing using fast-check for mathematical property validation
• Compatibility testing against Excel and Google Sheets behavior

Validation Infrastructure:

// Schema validation using zod/v4
const CellValueSchema = z.union([
  z.number(),
  z.string(),
  z.boolean(),
  z.date(),
  z.null(),
  z.undefined(),
]);

function validateFormulaArgs(
  args: unknown
): Result<FunctionArgs, ValidationError> {
  const result = FunctionArgsSchema.safeParse(args);
  return result.success
    ? { success: true, data: result.data }
    : { success: false, error: new ValidationError(result.error.message) };
}

Architecture Decisions That Work:

• Headless design enables maximum flexibility for integration scenarios
• Three-phase processing provides clear separation of concerns and optimization opportunities
• Relative addressing dramatically reduces memory usage through AST reuse
• Dependency graph optimization is fundamental to spreadsheet engine performance
• Incremental recalculation is essential for real-world spreadsheet sizes

Common Pitfalls to Avoid:

• Monolithic architectures don't scale and are difficult to maintain
• Premature optimization without profiling can lead to complex, buggy code
• Tight UI coupling limits reusability and testing capabilities
• Insufficient error handling creates poor user experiences

Performance Optimization Insights:

• GPU acceleration showed limited practical benefits in HyperFormula testing
• WebWorkers didn't provide expected performance gains due to serialization overhead
• Multi-threading works best for independent calculation chains
• Memory management is more critical than raw computational speed for most use cases

1. Parser Infrastructure: Implement Chevrotain-based formula parser with comprehensive grammar
2. Basic Evaluation Engine: Core cell evaluation with simple dependency tracking
3. TypeScript Type System: Establish type-safe interfaces and core data structures
4. Testing Infrastructure: Unit testing framework with Excel compatibility testing

1. Array Formula Support: Implement broadcasting semantics and spilling behavior
2. Named Expressions: Complete scoping system with circular reference prevention
3. Error Handling: Comprehensive error propagation and recovery mechanisms
4. Performance Optimization: Sparse-aware evaluation and caching strategies

1. Plugin Architecture: Extensible function registration and custom logic support
2. Advanced Operations: Copy/paste mechanics, undo/redo, and bulk operations
3. Performance Tuning: Memory optimization, multi-threading, and benchmarking
4. Documentation and Examples: Comprehensive API documentation and usage examples

Critical Path Dependencies:

1. Dependency graph system (blocks everything else)
2. Parser and AST construction (enables formula processing)
3. Basic evaluation engine (provides core functionality)
4. Type system design (ensures maintainability)

Performance Optimization Strategy:

1. Profile early with realistic datasets
2. Implement sparse-aware algorithms from the start
3. Add caching incrementally based on bottleneck analysis
4. Validate optimizations against Excel compatibility

Quality Assurance Approach:

1. Test-driven development with Excel compatibility as primary requirement
2. Continuous integration with performance regression testing
3. Real-world workbook testing throughout development
4. Community beta testing for validation and feedback

FormulaEngine represents an opportunity to create a next-generation spreadsheet calculation library that combines the architectural insights of HyperFormula with modern TypeScript development practices and enhanced performance optimizations. The key to success lies in maintaining unwavering focus on Excel compatibility while leveraging TypeScript's advanced type system to create an exceptional developer experience.

The sparse-aware architecture, array formula support with broadcasting, and comprehensive error handling will provide a robust foundation for modern web applications requiring sophisticated computational capabilities. By learning from the documented experiences of existing implementations and avoiding their pitfalls, FormulaEngine can establish itself as the premier choice for TypeScript-based formula evaluation.

Success Metrics:

• Performance: Sub-second recalculation for spreadsheets with 100,000+ formulas
• Developer Experience: Type-safe APIs with comprehensive IntelliSense support
• Memory Efficiency: 10x memory reduction compared to dense storage for typical sparse spreadsheets
• Extensibility: Plugin architecture supporting custom functions and evaluation strategies

This technical specification provides the roadmap for building a world-class formula engine that pushes the boundaries of what's possible with web-based spreadsheet computation while maintaining the reliability and compatibility that users expect.