《游戏引擎实现原理》2.2 缓存、热重载与增量构建

// file: src/subsys/asset/build-cache.ts
// tier: L1
// verify: npx vitest run src/subsys/asset/build-cache.test.ts
//
// 资源管线的「在线半边」：离线导入器很贵（解码 + mip + 压缩），所以构建系统
// 要能回答两个问题——「这个资源还需要重导吗」「改了它，谁跟着脏」。
// 答案是**内容哈希 + 依赖键传播**：每个节点的键由「源内容哈希 + 导入器版本 +
// 全部依赖的键」折叠而成。源不变、导入器不变、依赖不变 → 键不变 → 命中缓存。
// 任何一环变了，键就变，且变化会沿依赖边向下游传播（材质依赖纹理，纹理变了材质必脏）。
//
// 另配一条**产物校验**：构建缓存记录产物哈希，加载时可再算一遍，抓出磁盘损坏。

import type { AssetMeta } from './importer.ts';

// ---------------------------------------------------------------------------
// FNV-1a 64 位：够快、够短、无依赖，做内容寻址键足够。
// 用 BigInt 保证跨平台确定（JS 的 Number 只有 53 位尾数，装不下 64 位）。
// ---------------------------------------------------------------------------

const FNV_OFFSET = 0xcbf29ce484222325n;
const FNV_PRIME = 0x100000001b3n;
const MASK64 = 0xffffffffffffffffn;

/** 对字节流算 FNV-1a 64 位，返回 16 位十六进制串。 */
export function fnv1a64Hex(bytes: Uint8Array): string {
  let h = FNV_OFFSET;
  for (let i = 0; i < bytes.length; i++) {
    h ^= BigInt(bytes[i]!);
    h = (h * FNV_PRIME) & MASK64;
  }
  return h.toString(16).padStart(16, '0');
}

/** 对 UTF-8 文本算同一个哈希。 */
export function hashText(text: string): string {
  return fnv1a64Hex(new TextEncoder().encode(text));
}

/** 把多个键折叠成一个：先按字典序排，保证与依赖声明顺序无关。 */
export function foldKeys(parts: readonly string[]): string {
  return hashText([...parts].sort().join('\u0000'));
}

// ---------------------------------------------------------------------------
// 构建图与缓存。
// ---------------------------------------------------------------------------

/** 构建图里的一个节点：一份源资源 + 它的导入器 + 它依赖的其它资源。 */
export type BuildNode = {
  readonly id: string;
  readonly deps: readonly string[];
  /** 源文件内容哈希（源一变，此节点必重导）。 */
  readonly sourceHash: string;
  readonly importerId: string;
  readonly importerVersion: number;
};

/** 缓存条目：记录某节点上次构建时的键与产物指纹。 */
export type CacheEntry = {
  readonly nodeId: string;
  readonly key: string;
  readonly artifactHash: string;
  readonly payloadBytes: number;
  readonly meta: AssetMeta | null;
};

export class BuildCache {
  private readonly entries = new Map<string, CacheEntry>();

  /** 命中判定：同一节点、同一键，才算复用。 */
  matches(nodeId: string, key: string): boolean {
    return this.entries.get(nodeId)?.key === key;
  }

  get(nodeId: string): CacheEntry | undefined {
    return this.entries.get(nodeId);
  }

  put(entry: CacheEntry): void {
    this.entries.set(entry.nodeId, entry);
  }

  /** 清掉已不在图中的节点，避免缓存无限膨胀。 */
  prune(liveIds: ReadonlySet<string>): number {
    let removed = 0;
    for (const id of [...this.entries.keys()]) {
      if (!liveIds.has(id)) { this.entries.delete(id); removed++; }
    }
    return removed;
  }

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

  /** 落盘成可持久化的 JSON（键是十六进制串，天然可序列化）。 */
  toJSON(): string {
    return JSON.stringify([...this.entries.values()].sort((a, b) => a.nodeId.localeCompare(b.nodeId)));
  }

  static fromJSON(text: string): BuildCache {
    const cache = new BuildCache();
    for (const e of JSON.parse(text) as CacheEntry[]) cache.put(e);
    return cache;
  }
}

/** 拓扑排序：依赖在前。有环即抛错（构建图必须是 DAG）。 */
export function topoSort(nodes: readonly BuildNode[]): string[] {
  const byId = new Map(nodes.map((n) => [n.id, n]));
  const state = new Map<string, 0 | 1 | 2>(); // 0 未访问 / 1 访问中 / 2 完成
  const order: string[] = [];
  const visit = (id: string, stack: string[]): void => {
    const s = state.get(id) ?? 0;
    if (s === 2) return;
    if (s === 1) throw new Error(`构建图存在环：${[...stack, id].join(' -> ')}`);
    state.set(id, 1);
    for (const d of byId.get(id)!.deps) {
      if (!byId.has(d)) throw new Error(`节点 ${id} 依赖不存在的 ${d}`);
      visit(d, [...stack, id]);
    }
    state.set(id, 2);
    order.push(id);
  };
  for (const n of nodes) visit(n.id, []);
  return order;
}

/** 单节点内容键 = hash(导入器标识 + 版本 + 源哈希 + 折叠后的依赖键)。 */
export function nodeKey(node: BuildNode, depKeys: readonly string[]): string {
  return foldKeys([`${node.importerId}@${node.importerVersion}`, node.sourceHash, foldKeys(depKeys)]);
}

export type BuildStats = {
  /** 拓扑序（依赖在前）。 */
  readonly order: string[];
  /** 本次真正重导的节点。 */
  readonly rebuilt: string[];
  /** 直接复用缓存的节点。 */
  readonly reused: string[];
  /** 重导的传播深度：脏节点在下游的「代际」，用于观察失效扩散。 */
  readonly generation: ReadonlyMap<string, number>;
};

/**
 * 增量构建：按拓扑序逐个算键，命中则复用、未命中则重导并把新键写回缓存。
 * 依赖键取自**本轮**已算出的值，故上游一变，下游键必然跟着变。
 */
export function incrementalBuild(nodes: readonly BuildNode[], cache: BuildCache): BuildStats {
  const byId = new Map(nodes.map((n) => [n.id, n]));
  const order = topoSort(nodes);
  const keys = new Map<string, string>();
  const generation = new Map<string, number>();
  const rebuilt: string[] = [];
  const reused: string[] = [];
  for (const id of order) {
    const node = byId.get(id)!;
    const depKeys = node.deps.map((d) => keys.get(d)!);
    const key = nodeKey(node, depKeys);
    keys.set(id, key);
    const gen = node.deps.length === 0 ? 0 : Math.max(...node.deps.map((d) => generation.get(d)!)) + 1;
    generation.set(id, gen);
    if (cache.matches(id, key)) {
      reused.push(id);
    } else {
      rebuilt.push(id);
      const prev = cache.get(id);
      cache.put({
        nodeId: id, key,
        artifactHash: key, // 内容寻址：键即产物指纹
        payloadBytes: prev?.payloadBytes ?? 0,
        meta: prev?.meta ?? null,
      });
    }
  }
  return { order, rebuilt, reused, generation };
}

// ---------------------------------------------------------------------------
// 产物校验与热重载派发。
// ---------------------------------------------------------------------------

/** 校验产物字节是否与记录的哈希一致，抓磁盘损坏 / 传输截断。 */
export function verifyArtifact(bytes: Uint8Array, expectedHex: string): boolean {
  return fnv1a64Hex(bytes) === expectedHex;
}

export type HotReloadEvent = {
  readonly changed: readonly string[];
  /** 是否只是复用（false 表示发生了重导）。 */
  readonly rebuilt: boolean;
};

/**
 * 热重载派发器：构建完成后把「哪些节点变了」广播给订阅者。
 * 依赖被重导的节点会随依赖一起出现在 changed 里（级联失效），
 * 订阅者据此决定重建 GPU 资源、重放动画还是保留状态。
 */
export class HotReloadDispatcher {
  private readonly listeners = new Set<(e: HotReloadEvent) => void>();
  private readonly history: HotReloadEvent[] = [];

  subscribe(fn: (e: HotReloadEvent) => void): () => void {
    this.listeners.add(fn);
    return () => this.listeners.delete(fn);
  }

  /** 由一次构建结果派发事件；无变化时不派发。 */
  dispatchFrom(stats: BuildStats): HotReloadEvent | null {
    if (stats.rebuilt.length === 0) return null;
    const event: HotReloadEvent = { changed: stats.rebuilt, rebuilt: true };
    this.history.push(event);
    for (const fn of this.listeners) fn(event);
    return event;
  }

  get events(): readonly HotReloadEvent[] { return this.history; }
}

// ---- 直接运行：造一张小资源图，全量建一次再改一个源，看失效扩散 ----
if ((import.meta as { main?: boolean }).main) {
  const n = (id: string, deps: string[], src: string, imp: string, ver: number): BuildNode =>
    ({ id, deps, sourceHash: hashText(src), importerId: imp, importerVersion: ver });
  const graph = (tex: string): BuildNode[] => [
    n('rock.tex', [], tex, 'helio.texture', 3),
    n('rock.mesh', [], 'mesh-v1', 'helio.mesh', 2),
    n('rock.mat', ['rock.tex'], 'mat-v1', 'helio.material', 1),
    n('rock.prefab', ['rock.mesh', 'rock.mat'], 'prefab-v1', 'helio.prefab', 1),
    n('water.tex', [], 'water-v1', 'helio.texture', 3),
  ];
  const cache = new BuildCache();
  console.log(`首次 rebuilt=${incrementalBuild(graph('v1'), cache).rebuilt.length} reused=0`);
  console.log(`无改动 rebuilt=${incrementalBuild(graph('v1'), cache).rebuilt.length}`);
  console.log(`改 rock.tex rebuilt=[${incrementalBuild(graph('v2'), cache).rebuilt.join(', ')}]`);
  const json = cache.toJSON();
  console.log(`落盘再读 rebuilt=${incrementalBuild(graph('v2'), BuildCache.fromJSON(json)).rebuilt.length} cacheBytes=${json.length}`);
}

首次 rebuilt=5 reused=0
无改动 rebuilt=0
改 rock.tex rebuilt=[rock.tex, rock.mat, rock.prefab]
落盘再读 rebuilt=0 cacheBytes=556