《游戏引擎实现原理》7.3 字符串 intern、资源 GUID 与名字表

// file: src/core/string-intern.ts
// tier: L1
// verify: npx vitest run src/core/string-intern.test.ts
//
// 字符串驻留表：同样的字符串只存一份，返回一个稳定的数字 id。
// 之后比较两个名字就变成比较两个整数（O(1)），而不是逐字符比字符串。
// 同时给出由路径确定性地推导资源 GUID 的函数。

/** 驻留字符串的数字标识。0 保留为「无效」。 */
export type StringId = number;
export const INVALID_STRING: StringId = 0;

/** FNV-1a 32 位哈希，offset basis 可换以得到独立的第二路哈希。 */
export function fnv1a32(s: string, basis = 0x811c9dc5): number {
  let h = basis;
  for (let i = 0; i < s.length; i++) {
    h ^= s.charCodeAt(i);
    h = Math.imul(h, 0x01000193);
  }
  return h >>> 0;
}

export class StringTable {
  #ids = new Map<string, StringId>();
  #strings: string[] = ['']; // 下标 0 留给「无效」
  #hits = 0;

  get size(): number {
    return this.#strings.length - 1;
  }

  /** 命中次数：同名字符串被重复驻留时累加（用于观察复用率）。 */
  get hits(): number {
    return this.#hits;
  }

  /** 驻留一个字符串：已存在返回旧 id，否则分配新 id。 */
  intern(s: string): StringId {
    const existing = this.#ids.get(s);
    if (existing !== undefined) {
      this.#hits++;
      return existing;
    }
    const id = this.#strings.length;
    this.#ids.set(s, id);
    this.#strings.push(s);
    return id;
  }

  /** id → 字符串。越界或 INVALID_STRING 返回 undefined。 */
  resolve(id: StringId): string | undefined {
    return id > 0 && id < this.#strings.length ? this.#strings[id] : undefined;
  }

  /** 字符串 → id，未驻留过返回 undefined（不产生副作用）。 */
  idOf(s: string): StringId | undefined {
    return this.#ids.get(s);
  }

  *entries(): Generator<[StringId, string]> {
    for (let i = 1; i < this.#strings.length; i++) yield [i, this.#strings[i]];
  }
}

/** 由资源路径确定性地推导 64 位 GUID（16 个十六进制字符）。 */
export function guidFromPath(path: string): string {
  const lo = fnv1a32(path, 0x811c9dc5);
  const hi = fnv1a32(path, 0x9e3779b1); // 独立的第二路 offset basis
  return lo.toString(16).padStart(8, '0') + hi.toString(16).padStart(8, '0');
}

// file: src/core/name-table.ts
// tier: L1
// verify: npx vitest run src/core/name-table.test.ts
//
// 名字表：引擎里所有「按名字引用」的东西（组件类型、属性、系统）都登记在这里，
// 得到一个数字句柄。比较名字变成比较句柄，序列化时既存字符串也存哈希，
// 读档时能靠哈希把字符串快速接回同一个句柄。

import { StringTable, fnv1a32, type StringId } from './string-intern.ts';

export type NameHandle = StringId;

export class NameTable {
  #table = new StringTable();
  #hashById: number[] = [0]; // 下标 0 对应 INVALID

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

  /** 登记一个名字，返回稳定句柄。 */
  intern(name: string): NameHandle {
    const id = this.#table.intern(name);
    if (this.#hashById[id] === undefined) this.#hashById[id] = fnv1a32(name);
    return id;
  }

  nameOf(id: NameHandle): string | undefined {
    return this.#table.resolve(id);
  }

  idOf(name: string): NameHandle | undefined {
    return this.#table.idOf(name);
  }

  hashOf(id: NameHandle): number {
    return this.#hashById[id] ?? 0;
  }

  /** 句柄比较：一次整数比较，与名字长度无关。 */
  equal(a: NameHandle, b: NameHandle): boolean {
    return a === b;
  }

  /** 只拿到哈希时反查句柄（读档路径）。碰撞则返回第一个匹配。 */
  idByHash(hash: number): NameHandle | undefined {
    for (let id = 1; id < this.#hashById.length; id++) {
      if (this.#hashById[id] === hash) return id;
    }
    return undefined;
  }

  *entries(): Generator<[NameHandle, string]> {
    yield* this.#table.entries();
  }
}

/** 把 helio 内核的一组内建名字登记进名字表。 */
export function registerKernelNames(names: NameTable): void {
  for (const n of [
    'Transform',
    'MeshRenderer',
    'RigidBody',
    'Script',
    'position',
    'rotation',
    'scale',
    'UpdateSystem',
    'RenderSystem',
  ]) {
    names.intern(n);
  }
}

// file: src/core/string-intern.test.ts
// tier: L1
// verify: npx vitest run src/core/string-intern.test.ts

import { describe, expect, it } from 'vitest';
import { INVALID_STRING, StringTable, guidFromPath } from './string-intern.ts';

describe('StringTable', () => {
  it('同名字符串返回同一 id', () => {
    const t = new StringTable();
    const a = t.intern('health');
    const b = t.intern('health');
    expect(a).toBe(b);
    expect(t.size).toBe(1);
    expect(t.hits).toBe(1);
  });

  it('不同字符串得到不同 id 且可反查', () => {
    const t = new StringTable();
    const a = t.intern('position');
    const b = t.intern('velocity');
    expect(a).not.toBe(b);
    expect(t.resolve(a)).toBe('position');
    expect(t.resolve(b)).toBe('velocity');
  });

  it('id 从 1 开始，0 是无效', () => {
    const t = new StringTable();
    expect(t.intern('first')).toBe(1);
    expect(t.resolve(INVALID_STRING)).toBeUndefined();
    expect(t.resolve(999)).toBeUndefined();
  });

  it('idOf 不产生副作用', () => {
    const t = new StringTable();
    t.intern('mesh');
    expect(t.idOf('mesh')).toBe(1);
    expect(t.idOf('absent')).toBeUndefined();
    expect(t.size).toBe(1);
  });

  it('名字相等即整数相等（O(1) 比较）', () => {
    const t = new StringTable();
    const a = t.intern('Transform');
    const b = t.intern('Transform');
    expect(a === b).toBe(true); // 比较两个 number
  });
});

describe('guidFromPath', () => {
  it('同路径恒定、不同路径不同', () => {
    expect(guidFromPath('assets/mesh/island.gltf')).toBe(guidFromPath('assets/mesh/island.gltf'));
    expect(guidFromPath('assets/mesh/island.gltf')).not.toBe(guidFromPath('assets/mesh/rock.gltf'));
  });

  it('是 16 个十六进制字符', () => {
    expect(guidFromPath('a')).toMatch(/^[0-9a-f]{16}$/);
  });
});