Design a Layout Engine for a Design Tool (e.g. Figma)

┌──────────────────────────────────────────────────────┐
│ Input handling           │  1ms                       │
│ Dirty flag propagation   │  0.5ms                     │
│ Layout resolution        │  8ms (BUDGET)              │
│ Hit-test update          │  1ms                       │
│ Render tree diff         │  2ms                       │
│ GPU draw calls           │  3ms                       │
│ GC / slack              │  1.17ms                    │
└──────────────────────────────────────────────────────┘

Position (x, y):        8 bytes (2 × f32)
Size (w, h):            8 bytes (2 × f32)
Constraints:           32 bytes (sizing modes, min/max per axis)
Flex properties:       24 bytes (axis, gap, padding, alignment)
Dirty flags:            4 bytes (bitfield)
Cache hash:             8 bytes
Parent/child pointers: 16 bytes
─────────────────────────────────
Total:                ~100 bytes (leaves headroom for alignment)

/** Sizing mode for a single axis */
type SizingMode = "fixed" | "hug" | "fill";

/** Alignment on the main axis (distribution) */
type MainAxisAlignment =
  | "start"
  | "center"
  | "end"
  | "space-between"
  | "space-around"
  | "space-evenly";

/** Alignment on the cross axis */
type CrossAxisAlignment = "start" | "center" | "end" | "stretch" | "baseline";

/** Layout direction */
type LayoutDirection = "horizontal" | "vertical";

/** Overflow behavior */
type OverflowBehavior = "visible" | "hidden" | "scroll";

/** Edge insets (padding/margin) */
interface EdgeInsets {
  top: number;
  right: number;
  bottom: number;
  left: number;
}

/** Size constraints for a single axis */
interface AxisConstraint {
  mode: SizingMode;
  value: number; // used when mode === 'fixed'
  min: number; // 0 = unconstrained
  max: number; // Infinity = unconstrained
  growFactor: number; // flex-grow equivalent (0 = don't grow)
  shrinkFactor: number; // flex-shrink equivalent (1 = can shrink)
}

/** Auto-layout properties (only on frames with layoutMode !== 'none') */
interface AutoLayoutProps {
  direction: LayoutDirection;
  mainAxisAlignment: MainAxisAlignment;
  crossAxisAlignment: CrossAxisAlignment;
  gap: number;
  padding: EdgeInsets;
  counterAxisSizingMode: SizingMode; // 'hug' or 'fixed' on cross axis
  wrap: boolean; // wrap children to next line
  wrapGap: number; // gap between wrapped lines
}

/** Position mode within parent */
type PositionMode = "auto" | "absolute";

/** Constraints for absolute positioning (relative to parent edges) */
interface AbsoluteConstraints {
  top: number | null;
  right: number | null;
  bottom: number | null;
  left: number | null;
  centerX: boolean;
  centerY: boolean;
}

/** The core layout node — mirrors the design document node */
interface LayoutNode {
  id: string; // stable across CRDT operations
  parentId: string | null;
  childrenIds: string[]; // ordered

  // Sizing
  widthConstraint: AxisConstraint;
  heightConstraint: AxisConstraint;

  // Positioning
  positionMode: PositionMode;
  absoluteConstraints: AbsoluteConstraints | null;
  rotation: number; // degrees, applied after layout

  // Auto-layout (null if this node is not an auto-layout frame)
  autoLayout: AutoLayoutProps | null;

  // Type-specific
  nodeType: "frame" | "group" | "text" | "vector" | "instance" | "component";

  // Instance overrides
  masterComponentId: string | null; // for instances
  overriddenProperties: Set<string>; // tracks which props are locally overridden

  // Text-specific (intrinsic size comes from text shaper)
  textContent: string | null;
  textStyle: TextStyle | null;

  // Dirty tracking
  dirtyFlags: DirtyFlags;
}

/** Bitfield for dirty tracking */
interface DirtyFlags {
  selfLayout: boolean; // own constraints changed
  childrenLayout: boolean; // a child's size/constraints changed
  textContent: boolean; // text content or style changed
  subtreeStructure: boolean; // children added/removed/reordered
}

/** Resolved layout output for a single node */
interface LayoutResult {
  nodeId: string;
  x: number; // relative to parent's content box
  y: number;
  width: number;
  height: number;

  // Cached for hit-testing: absolute position in document space
  absoluteX: number;
  absoluteY: number;

  // Baseline for text alignment
  firstBaseline: number;
  lastBaseline: number;
}

/** Text measurement result (from text shaper) */
interface TextMeasurement {
  width: number;
  height: number;
  firstBaseline: number;
  lastBaseline: number;
  lineCount: number;
  lineBreaks: number[]; // character indices where lines break
}

/** Input to the text shaper */
interface TextStyle {
  fontFamily: string;
  fontSize: number;
  fontWeight: number;
  lineHeight: number | "auto";
  letterSpacing: number;
  textAlign: "left" | "center" | "right" | "justify";
  maxWidth: number | null; // available width for line-breaking
}

/** Layout computation context passed through the tree */
interface LayoutContext {
  availableWidth: number; // space offered by parent on main axis
  availableHeight: number; // space offered by parent on cross axis
  isWidthDefined: boolean; // parent has definite width (vs hug)
  isHeightDefined: boolean;
}

interface LayoutEngine {
  /**
   * Initialize the engine with a node tree.
   * Allocates WASM linear memory for the tree structure.
   */
  initialize(nodes: LayoutNode[]): void;

  /**
   * Perform layout on dirty subtrees.
   * Returns only the nodes whose layout changed.
   * Complexity: O(dirty subtree size), not O(document size).
   */
  computeLayout(): LayoutResult[];

  /**
   * Mark a node as dirty (constraints changed).
   * Propagates dirty flags up to the root.
   * Complexity: O(depth).
   */
  markDirty(nodeId: string, reason: DirtyReason): void;

  /**
   * Bulk update: insert, remove, or reorder children.
   * More efficient than individual markDirty calls.
   */
  applyTreeMutation(mutation: TreeMutation): void;

  /**
   * Get the current layout result for a node.
   * Returns cached result — does NOT trigger recomputation.
   */
  getLayoutResult(nodeId: string): LayoutResult | null;

  /**
   * Register a text measurement provider.
   * Called by the engine when it needs intrinsic text size.
   */
  setTextMeasurer(measurer: TextMeasurer): void;

  /**
   * Force full relayout of entire document.
   * Used for undo/redo where dirty tracking is unreliable.
   */
  computeFullLayout(): LayoutResult[];

  /**
   * Dispose WASM memory and caches. */
  destroy(): void;
}

type DirtyReason =
  | "constraint_change" // sizing mode, min/max, grow/shrink
  | "auto_layout_change" // direction, gap, padding, alignment
  | "content_change" // text content changed
  | "child_added"
  | "child_removed"
  | "child_reordered"
  | "position_mode_change"; // auto ↔ absolute

interface TreeMutation {
  inserts: Array<{ parentId: string; index: number; node: LayoutNode }>;
  removals: Array<{ nodeId: string }>;
  moves: Array<{ nodeId: string; newParentId: string; newIndex: number }>;
}

interface TextMeasurer {
  /**
   * Measure text given style and available width.
   * Implementation uses Canvas 2D measureText or HarfBuzz WASM.
   */
  measure(
    text: string,
    style: TextStyle,
    availableWidth: number,
  ): TextMeasurement;
}

/** Called per auto-layout frame during layout resolution */
interface FlexSolver {
  /**
   * Measure pass: determine intrinsic sizes of all children.
   * Returns the minimum and maximum content size of this container.
   */
  measureChildren(
    children: LayoutNode[],
    parentContext: LayoutContext,
  ): { minContent: Size; maxContent: Size };

  /**
   * Arrange pass: distribute available space among children.
   * Writes final positions into the output buffer.
   */
  arrangeChildren(
    children: LayoutNode[],
    containerSize: Size,
    autoLayout: AutoLayoutProps,
  ): LayoutResult[];

  /**
   * Handle overflow: clamp children that exceed min/max after arrangement.
   * May trigger a re-arrangement if clamping changes available space.
   */
  applyMinMaxClamping(
    results: LayoutResult[],
    children: LayoutNode[],
  ): { changed: boolean; results: LayoutResult[] };
}

/**
 * When a property changes, the propagation follows this protocol:
 *
 * 1. Mark the node dirty (selfLayout = true)
 * 2. Walk up to root, marking each ancestor (childrenLayout = true)
 * 3. On next layout pass, walk down from root:
 *    - Skip clean subtrees entirely
 *    - For dirty nodes: run measure + arrange
 *    - Clear dirty flags after successful layout
 * 4. Emit changed LayoutResults to the renderer
 */
interface ChangeEvent {
  nodeId: string;
  property: string;
  oldValue: unknown;
  newValue: unknown;
  timestamp: number; // for CRDT ordering
}

interface LayoutCacheKey {
  /** Hash of: sizing modes, auto-layout props, child count, child order */
  constraintHash: number;
  /** Hash of: available width/height from parent context */
  contextHash: number;
}

interface LayoutCacheEntry {
  key: LayoutCacheKey;
  results: LayoutResult[];
  timestamp: number; // for LRU eviction
  hitCount: number; // for frequency-based retention
}

function invalidateNode(node: LayoutNode): void {
  // Invalidate self
  node.dirtyFlags.selfLayout = true;
  layoutCache.delete(node.id);

  // Propagate upward until hitting a layout boundary
  let current = node.parentId;
  while (current !== null) {
    const parent = getNode(current);
    parent.dirtyFlags.childrenLayout = true;
    layoutCache.delete(parent.id);

    // Stop at layout boundary: fixed size on both axes
    if (isLayoutBoundary(parent)) break;
    current = parent.parentId;
  }
}

function isLayoutBoundary(node: LayoutNode): boolean {
  return (
    node.widthConstraint.mode === "fixed" &&
    node.heightConstraint.mode === "fixed" &&
    node.autoLayout === null // not an auto-layout frame
  );
}

┌─────────────────────────────────────────────────────────────┐
│                  LAYOUT PIPELINE                             │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  1. DIRTY COLLECTION                                        │
│     Walk dirty flags → collect dirty roots                  │
│     (Topmost dirty ancestor for each dirty path)            │
│                                                             │
│  2. MEASURE PASS (bottom-up)                                │
│     For each dirty root, recursively:                       │
│     • Leaf nodes: return intrinsic size                     │
│       - Text: call TextMeasurer                             │
│       - Vector: bounding box of path                        │
│       - Frame (hug): recurse into children first            │
│     • Auto-layout frames: sum children sizes + gaps         │
│     • Result: each node knows its "desired" size            │
│                                                             │
│  3. CONSTRAINT RESOLUTION                                   │
│     Resolve conflicts between parent and child:             │
│     • Fill children: allocated = remaining space / N        │
│     • Hug parents: size = max(children's resolved sizes)    │
│     • Apply min/max clamping                                │
│     • If clamping changes allocation → re-run distribution  │
│                                                             │
│  4. ARRANGE PASS (top-down)                                 │
│     For each dirty root, recursively:                       │
│     • Compute child positions based on:                     │
│       - Main axis: start position + cumulative offset       │
│       - Cross axis: alignment within container              │
│       - Absolute children: constraint-based positioning     │
│     • Write [x, y, w, h] to output buffer                  │
│                                                             │
│  5. ABSOLUTE POSITION RESOLUTION                            │
│     For absolute children within auto-layout frames:        │
│     • Resolve top/right/bottom/left constraints             │
│     • Apply center constraints                              │
│     • Do NOT affect sibling layout                          │
│                                                             │
│  6. OUTPUT + CLEAR                                          │
│     • Emit changed LayoutResults                            │
│     • Clear dirty flags                                     │
│     • Update cache entries                                  │
│                                                             │
└─────────────────────────────────────────────────────────────┘

function distributeFlexSpace(
  children: LayoutNode[],
  availableSpace: number,
  gap: number,
  direction: "main" | "cross",
): number[] {
  const constraint =
    direction === "main" ? "widthConstraint" : "heightConstraint";

  // Step 1: Allocate fixed and hug children their intrinsic sizes
  let usedSpace = 0;
  let totalGrow = 0;
  const sizes: number[] = new Array(children.length);

  for (let i = 0; i < children.length; i++) {
    const child = children[i];
    if (child[constraint].mode === "fill") {
      totalGrow += child[constraint].growFactor || 1;
      sizes[i] = 0; // will be resolved in step 2
    } else {
      sizes[i] = getIntrinsicSize(child, direction);
      usedSpace += sizes[i];
    }
  }

  // Step 2: Distribute remaining space among fill children
  const totalGaps = (children.length - 1) * gap;
  const remainingSpace = Math.max(0, availableSpace - usedSpace - totalGaps);

  for (let i = 0; i < children.length; i++) {
    const child = children[i];
    if (child[constraint].mode === "fill") {
      const growFactor = child[constraint].growFactor || 1;
      sizes[i] = (growFactor / totalGrow) * remainingSpace;
    }
  }

  // Step 3: Apply min/max clamping (may require redistribution)
  let changed = true;
  let iterations = 0;
  while (changed && iterations < 3) {
    changed = false;
    iterations++;
    let clampedSpace = 0;
    let remainingGrow = 0;

    for (let i = 0; i < children.length; i++) {
      const child = children[i];
      const clamped = clamp(
        sizes[i],
        child[constraint].min,
        child[constraint].max,
      );
      if (clamped !== sizes[i]) {
        sizes[i] = clamped;
        clampedSpace += clamped;
        changed = true;
      } else if (child[constraint].mode === "fill") {
        remainingGrow += child[constraint].growFactor || 1;
      }
    }

    // Redistribute remaining space among unclamped fill children
    if (changed && remainingGrow > 0) {
      const newRemaining = availableSpace - clampedSpace - totalGaps;
      for (let i = 0; i < children.length; i++) {
        const child = children[i];
        if (
          child[constraint].mode === "fill" &&
          !isClamped(sizes[i], child[constraint])
        ) {
          sizes[i] =
            ((child[constraint].growFactor || 1) / remainingGrow) *
            newRemaining;
        }
      }
    }
  }

  return sizes;
}

class IncrementalLayoutScheduler {
  private dirtyRoots: Set<string> = new Set();
  private pendingMutations: TreeMutation[] = [];
  private frameRequested = false;

  markDirty(nodeId: string): void {
    const root = findDirtyRoot(nodeId);
    this.dirtyRoots.add(root);
    this.scheduleLayout();
  }

  private scheduleLayout(): void {
    if (!this.frameRequested) {
      this.frameRequested = true;
      requestAnimationFrame(() => this.flush());
    }
  }

  private flush(): void {
    this.frameRequested = false;

    // Apply pending tree mutations
    for (const mutation of this.pendingMutations) {
      this.engine.applyTreeMutation(mutation);
    }
    this.pendingMutations = [];

    // Compute layout only for dirty subtrees
    const startTime = performance.now();
    const changedResults = this.engine.computeLayout();
    const layoutTime = performance.now() - startTime;

    // Emit to renderer
    this.renderer.updateLayout(changedResults);

    // Performance monitoring
    if (layoutTime > 8) {
      this.metrics.recordSlowLayout(layoutTime, this.dirtyRoots.size);
    }

    this.dirtyRoots.clear();
  }
}

interface PluginLayoutAPI {
  /** Read-only access to resolved layout */
  getAbsoluteBoundingBox(nodeId: string): Rect;

  /** Plugins can set constraints but not bypass validation */
  setConstraints(nodeId: string, constraints: Partial<AxisConstraint>): void;

  /** NOT exposed: direct access to WASM memory, output buffer, or cache */
}

interface AccessibilityNode {
  role: "group" | "img" | "text" | "button" | "region";
  label: string; // derived from layer name
  description: string; // derived from node type + constraints
  bounds: Rect; // for spatial navigation
  children: AccessibilityNode[];
}

/**
 * Sync accessibility tree with layout results.
 * Called after each layout pass (only for changed nodes).
 */
function updateAccessibilityTree(changedResults: LayoutResult[]): void {
  for (const result of changedResults) {
    const a11yNode = a11yTree.get(result.nodeId);
    if (a11yNode) {
      a11yNode.bounds = {
        x: result.absoluteX,
        y: result.absoluteY,
        width: result.width,
        height: result.height,
      };
      updateAriaAttributes(a11yNode);
    }
  }
}

function announceLayoutChange(node: LayoutNode, result: LayoutResult): void {
  const announcement = buildAnnouncement(node, result);
  // Example: "Frame 'Header' — auto-layout horizontal, 3 children,
  //           1200×80 pixels, gap 16, padding 24"
  ariaLiveRegion.textContent = announcement;
}

function buildAnnouncement(node: LayoutNode, result: LayoutResult): string {
  const parts: string[] = [`${node.nodeType} '${node.name}'`];

  if (node.autoLayout) {
    parts.push(`auto-layout ${node.autoLayout.direction}`);
    parts.push(`${node.childrenIds.length} children`);
    parts.push(`gap ${node.autoLayout.gap}`);
  }

  parts.push(`${Math.round(result.width)}×${Math.round(result.height)} pixels`);
  parts.push(`width: ${node.widthConstraint.mode}`);
  parts.push(`height: ${node.heightConstraint.mode}`);

  return parts.join(", ");
}

interface LayoutProfileFrame {
  timestamp: number;
  totalDuration: number;
  phases: {
    dirtyCollection: number;
    measurePass: number;
    constraintResolution: number;
    arrangePass: number;
    absolutePositioning: number;
    cacheUpdate: number;
    outputEmit: number;
  };
  nodeCount: number; // nodes visited
  cacheHits: number;
  cacheMisses: number;
  textMeasurements: number; // text nodes measured (not cached)
}

class LayoutProfiler {
  private frames: RingBuffer<LayoutProfileFrame>;
  private readonly capacity = 600; // 10 seconds at 60fps

  startFrame(): ProfileFrameBuilder {
    return new ProfileFrameBuilder(performance.now());
  }

  /** Dump last N seconds for debugging slow layout */
  exportProfile(seconds: number): LayoutProfileFrame[] {
    return this.frames.last(seconds * 60);
  }

  /** Real-time summary for the performance HUD */
  getSummary(): { avg: number; p95: number; max: number } {
    const durations = this.frames.last(60).map((f) => f.totalDuration);
    return {
      avg: mean(durations),
      p95: percentile(durations, 0.95),
      max: Math.max(...durations),
    };
  }
}

interface LayoutError {
  type:
    | "nan_output"
    | "timeout"
    | "depth_exceeded"
    | "circular_dependency"
    | "wasm_trap";
  nodeId: string;
  parentId: string | null;
  constraints: AxisConstraint; // the constraint config that caused the error
  context: LayoutContext; // what the parent offered
  timestamp: number;
  documentId: string; // for reproduction
}