《游戏引擎实现原理》15.1 依赖 DAG 与拓扑执行

// file: src/core/task-graph.ts
// tier: L1
// verify: npx vitest run src/core/task-graph.test.ts
//
// helio 内核：任务依赖 DAG 与拓扑执行。
// 每个任务声明「必须在哪些任务之后」（after = 前置），
// TaskGraph 用 Kahn 算法分层拓扑排序：同一层内的任务互不依赖，可以并行跑。

export type TaskId = string;

/** 一个任务：id 唯一，after 列出必须先完成的前置任务，run 是执行体。 */
export interface TaskNode {
  readonly id: TaskId;
  readonly after: readonly TaskId[];
  readonly run: () => void;
}

/** 拓扑计划：order 是合法的串行执行序，levels 是分层的并行批次。 */
export interface TopoPlan {
  readonly order: readonly TaskId[];
  readonly levels: readonly (readonly TaskId[])[];
  readonly maxParallelism: number;
}

/** 检测到环时抛出，remaining 列出卡在环上的任务（入度始终不为 0）。 */
export class CyclicDependencyError extends Error {
  readonly remaining: readonly TaskId[];
  constructor(remaining: readonly TaskId[]) {
    super(`cyclic task dependency among: ${remaining.join(', ')}`);
    this.name = 'CyclicDependencyError';
    this.remaining = remaining;
  }
}

/** 任务依赖图。加入顺序决定同层内的稳定次序，便于复现。 */
export class TaskGraph {
  readonly #nodes = new Map<TaskId, TaskNode>();

  add(task: TaskNode): this {
    if (this.#nodes.has(task.id)) {
      throw new Error(`duplicate task: ${task.id}`);
    }
    this.#nodes.set(task.id, task);
    return this;
  }

  get size(): number {
    return this.#nodes.size;
  }

  /**
   * Kahn 分层拓扑排序。每一轮取出「当前入度为 0」的全部任务作为一层，
   * 再把它们指向的后继入度减一，减到 0 的进入下一层。
   * 若处理完的节点数少于总数，说明剩下的节点互相卡住——那就是环。
   */
  plan(): TopoPlan {
    const indegree = new Map<TaskId, number>();
    const dependents = new Map<TaskId, TaskId[]>();
    for (const id of this.#nodes.keys()) {
      indegree.set(id, 0);
      dependents.set(id, []);
    }
    for (const task of this.#nodes.values()) {
      for (const dep of task.after) {
        if (!this.#nodes.has(dep)) {
          throw new Error(`unknown task dependency: ${task.id} -> ${dep}`);
        }
        indegree.set(task.id, (indegree.get(task.id) ?? 0) + 1);
        dependents.get(dep)!.push(task.id);
      }
    }

    let frontier = [...this.#nodes.keys()].filter((id) => indegree.get(id) === 0);
    const levels: TaskId[][] = [];
    const order: TaskId[] = [];
    let processed = 0;

    while (frontier.length > 0) {
      const level = [...frontier];
      levels.push(level);
      const next: TaskId[] = [];
      for (const id of level) {
        order.push(id);
        processed++;
        for (const succ of dependents.get(id)!) {
          const d = (indegree.get(succ) ?? 0) - 1;
          indegree.set(succ, d);
          if (d === 0) next.push(succ);
        }
      }
      frontier = next;
    }

    if (processed !== this.#nodes.size) {
      const stuck = [...this.#nodes.keys()].filter((id) => (indegree.get(id) ?? 0) > 0);
      throw new CyclicDependencyError(stuck);
    }

    const maxParallelism = levels.reduce((m, l) => Math.max(m, l.length), 0);
    return { order, levels, maxParallelism };
  }

  /** 按拓扑序串行执行全部任务，返回实际执行顺序（便于断言）。 */
  run(): TaskId[] {
    const plan = this.plan();
    for (const id of plan.order) {
      this.#nodes.get(id)!.run();
    }
    return [...plan.order];
  }
}

// file: src/core/task-graph.test.ts
// tier: L1
// verify: npx vitest run src/core/task-graph.test.ts

import { describe, expect, it } from 'vitest';
import { CyclicDependencyError, TaskGraph } from './task-graph.ts';

/** 造一个「把执行顺序写进 log」的图，用于观察 run() 的真实次序。 */
function frameGraph(log: string[]): TaskGraph {
  const g = new TaskGraph();
  const add = (id: string, after: string[]): void => {
    g.add({ id, after, run: () => log.push(id) });
  };
  add('input', []);
  add('physics', ['input']);
  add('ai', ['input']);
  add('animation', ['physics']);
  add('render-list', ['animation', 'ai']);
  add('cull', ['render-list']);
  add('submit', ['cull']);
  return g;
}

describe('TaskGraph 分层拓扑排序', () => {
  it('给出合法的分层计划与最大并行度', () => {
    const g = frameGraph([]);
    const plan = g.plan();
    expect(plan.levels).toEqual([
      ['input'],
      ['physics', 'ai'],
      ['animation'],
      ['render-list'],
      ['cull'],
      ['submit'],
    ]);
    expect(plan.maxParallelism).toBe(2);
    expect(plan.order).toEqual(plan.levels.flat());
  });

  it('run() 的执行顺序满足所有依赖（前置一定先跑）', () => {
    const log: string[] = [];
    const g = frameGraph(log);
    const order = g.run();
    expect(log).toEqual(order);
    const pos = new Map(order.map((id, i) => [id, i]));
    for (const [succ, deps] of [
      ['physics', ['input']],
      ['animation', ['physics']],
      ['render-list', ['animation', 'ai']],
    ] as const) {
      for (const dep of deps) {
        expect(pos.get(dep)!).toBeLessThan(pos.get(succ)!);
      }
    }
  });

  it('重复加入同名任务报错', () => {
    const g = new TaskGraph();
    g.add({ id: 'a', after: [], run: () => {} });
    expect(() => g.add({ id: 'a', after: [], run: () => {} })).toThrow(/duplicate task: a/);
  });

  it('依赖不存在的任务报错', () => {
    const g = new TaskGraph();
    g.add({ id: 'a', after: ['ghost'], run: () => {} });
    expect(() => g.plan()).toThrow(/unknown task dependency: a -> ghost/);
  });
});

describe('TaskGraph 环检测', () => {
  it('两节点互相依赖时报错并列出环上的任务', () => {
    const g = new TaskGraph();
    g.add({ id: 'a', after: ['b'], run: () => {} });
    g.add({ id: 'b', after: ['a'], run: () => {} });
    let caught: unknown;
    try {
      g.plan();
    } catch (e) {
      caught = e;
    }
    expect(caught).toBeInstanceOf(CyclicDependencyError);
    expect([...(caught as CyclicDependencyError).remaining].sort()).toEqual(['a', 'b']);
    expect(() => g.plan()).toThrow(/cyclic task dependency/);
  });

  it('三节点长环也能检测到，未卡住的任务不出现在 remaining 里', () => {
    const g = new TaskGraph();
    g.add({ id: 'root', after: [], run: () => {} });
    g.add({ id: 'a', after: ['root', 'c'], run: () => {} });
    g.add({ id: 'b', after: ['a'], run: () => {} });
    g.add({ id: 'c', after: ['b'], run: () => {} });
    let caught: CyclicDependencyError | undefined;
    try {
      g.plan();
    } catch (e) {
      caught = e as CyclicDependencyError;
    }
    expect(caught).toBeInstanceOf(CyclicDependencyError);
    expect([...caught!.remaining].sort()).toEqual(['a', 'b', 'c']);
  });
});