《游戏引擎实现原理》9.1 命令模式与可撤销操作

// file: src/editor/command/command.ts
// tier: L1
// verify: npx vitest run src/editor/command/command.test.ts
//
// helio 编辑器：命令栈的核心。命令把「一次可撤销的编辑」封成对象，
// 栈负责 do / undo / redo，并在压入时用 mergeWith 判定是否与栈顶合并。
// 编辑器 UI（10 / 11 章）只调 push / undo / redo，不直接碰文档。

/** 一条可撤销的编辑。do 与 undo 必须严格互逆。 */
export interface Command {
  /** 显示在「撤销 / 重做」菜单上的名字。 */
  readonly label: string;
  /** 正向应用。构造时不应有副作用，副作用只在 do 里发生。 */
  do(): void;
  /** 逆向回滚到 do 之前的状态。 */
  undo(): void;
  /** 可选：能否与「刚压入的上一条」合并；返回合并后的命令，或 null 表示不合并。 */
  mergeWith?(prev: Command): Command | null;
  /** 可选：估算本条命令占用的字节数，供栈的内存预算使用。 */
  byteSize?(): number;
}

function sizeOf(cmd: Command): number {
  return cmd.byteSize ? cmd.byteSize() : 0;
}

/**
 * 撤销栈。push 时先 do，再尝试与栈顶合并，最后按条数上限与字节预算裁剪最旧的命令。
 * 任何新编辑都会清空 redo 栈——这是「撤销后又编辑，重做链断裂」的标准语义。
 */
export class CommandStack {
  #undo: Command[] = [];
  #redo: Command[] = [];
  #limit = 256;
  #byteBudget = 8 * 1024 * 1024;
  #bytes = 0;

  get canUndo(): boolean { return this.#undo.length > 0; }
  get canRedo(): boolean { return this.#redo.length > 0; }
  get depth(): number { return this.#undo.length; }
  get bytes(): number { return this.#bytes; }
  get limit(): number { return this.#limit; }

  set limit(n: number) {
    this.#limit = Math.max(1, Math.floor(n));
    this.#trim();
  }

  set byteBudget(n: number) {
    this.#byteBudget = Math.max(0, n);
    this.#trim();
  }

  /** 下一次 undo 会撤销哪条命令。 */
  undoLabel(): string | null { return this.#undo.at(-1)?.label ?? null; }
  /** 下一次 redo 会重做哪条命令。 */
  redoLabel(): string | null { return this.#redo.at(-1)?.label ?? null; }

  push(cmd: Command): void {
    cmd.do();
    this.#redo.length = 0;
    const top = this.#undo.at(-1);
    const merged = top && cmd.mergeWith ? cmd.mergeWith(top) : null;
    if (merged) {
      this.#bytes -= sizeOf(top!);
      this.#undo[this.#undo.length - 1] = merged;
      this.#bytes += sizeOf(merged);
    } else {
      this.#undo.push(cmd);
      this.#bytes += sizeOf(cmd);
    }
    this.#trim();
  }

  undo(): boolean {
    const cmd = this.#undo.pop();
    if (!cmd) return false;
    cmd.undo();
    this.#redo.push(cmd);
    return true;
  }

  redo(): boolean {
    const cmd = this.#redo.pop();
    if (!cmd) return false;
    cmd.do();
    this.#undo.push(cmd);
    return true;
  }

  clear(): void {
    this.#undo.length = 0;
    this.#redo.length = 0;
    this.#bytes = 0;
  }

  /** 从最旧的（数组头部）开始丢弃，先满足条数上限，再满足字节预算。 */
  #trim(): void {
    while (this.#undo.length > this.#limit) {
      this.#bytes -= sizeOf(this.#undo.shift()!);
    }
    while (this.#bytes > this.#byteBudget && this.#undo.length > 1) {
      this.#bytes -= sizeOf(this.#undo.shift()!);
    }
  }
}

// file: src/editor/command/command.test.ts
// tier: L1
// verify: npx vitest run src/editor/command/command.test.ts
import { describe, expect, it } from 'vitest';
import { CommandStack, type Command } from './command.ts';

interface Box { v: number }

/** 最小命令：把 Box.v 从 from 设为 to，可合并同一目标上的连续赋值。 */
class SetValue implements Command {
  readonly label: string;
  #target: Box;
  #from: number;
  #to: number;

  constructor(target: Box, from: number, to: number, label = 'set value') {
    this.#target = target;
    this.#from = from;
    this.#to = to;
    this.label = label;
  }

  do(): void { this.#target.v = this.#to; }
  undo(): void { this.#target.v = this.#from; }
  byteSize(): number { return 32; }

  mergeWith(prev: Command): Command | null {
    if (!(prev instanceof SetValue) || prev.#target !== this.#target) return null;
    return new SetValue(this.#target, prev.#from, this.#to, prev.label);
  }
}

describe('命令栈的 do / undo / redo', () => {
  it('push 立即生效，undo 回滚，redo 重放', () => {
    const box: Box = { v: 0 };
    const stack = new CommandStack();
    stack.push(new SetValue(box, box.v, 5));
    expect(box.v).toBe(5);
    expect(stack.canUndo).toBe(true);
    stack.undo();
    expect(box.v).toBe(0);
    expect(stack.canRedo).toBe(true);
    stack.redo();
    expect(box.v).toBe(5);
  });

  it('空栈上 undo / redo 返回 false 且不抛错', () => {
    const stack = new CommandStack();
    expect(stack.undo()).toBe(false);
    expect(stack.redo()).toBe(false);
  });

  it('新编辑清空 redo 栈', () => {
    const box: Box = { v: 0 };
    const stack = new CommandStack();
    stack.push(new SetValue(box, 0, 1));
    stack.push(new SetValue(box, 1, 2, 'second'));
    stack.undo();
    expect(stack.canRedo).toBe(true);
    stack.push(new SetValue(box, box.v, 9, 'fresh'));
    expect(stack.canRedo).toBe(false);
    expect(stack.redoLabel()).toBeNull();
  });
});

describe('合并判定', () => {
  it('同一目标的连续赋值合并成一条栈记录', () => {
    const box: Box = { v: 0 };
    const stack = new CommandStack();
    stack.push(new SetValue(box, 0, 1));
    stack.push(new SetValue(box, 1, 2));
    stack.push(new SetValue(box, 2, 3));
    expect(stack.depth).toBe(1);
    stack.undo();
    expect(box.v).toBe(0); // 一步撤销回到最初
    expect(stack.canUndo).toBe(false);
  });

  it('不同目标不合并', () => {
    const a: Box = { v: 0 };
    const b: Box = { v: 0 };
    const stack = new CommandStack();
    stack.push(new SetValue(a, 0, 1));
    stack.push(new SetValue(b, 0, 1));
    expect(stack.depth).toBe(2);
  });
});

describe('栈上限与内存预算', () => {
  it('超出条数上限时丢弃最旧的命令', () => {
    const stack = new CommandStack();
    stack.limit = 3;
    const boxes = [0, 1, 2, 3, 4].map(() => ({ v: 0 }));
    boxes.forEach((box) => stack.push(new SetValue(box, 0, 1, 'no-merge-' + boxes.indexOf(box))));
    expect(stack.depth).toBe(3);
    // 最旧两条被丢弃，撤销只能回滚最后三条
    stack.undo(); stack.undo(); stack.undo();
    expect(stack.canUndo).toBe(false);
    expect(boxes[0]!.v).toBe(1); // 第 0 条已不可撤销
    expect(boxes[2]!.v).toBe(0); // 第 2 条仍在栈内，已回滚
  });

  it('字节预算触发裁剪，且至少保留一条', () => {
    const stack = new CommandStack();
    stack.byteBudget = 70; // 每条 32 字节，最多放 2 条
    const boxes = [0, 1, 2].map(() => ({ v: 0 }));
    boxes.forEach((box) => stack.push(new SetValue(box, 0, 1, 'k' + boxes.indexOf(box))));
    expect(stack.depth).toBe(2);
    expect(stack.bytes).toBeLessThanOrEqual(70);
    stack.byteBudget = 1; // 即使预算极小也要留一条，避免栈被清空后无法撤销
    expect(stack.depth).toBe(1);
  });
});