NameTrees

tcmts.share.NameTrees · #hfymzwcd · class

A codebase's history entries' names, read as the trees they're stored as. A namespace node's hash is its content's, so two entries' names differ only under nodes whose hashes differ, and comparing them reads only those; one name is a walk down its path. What's read is kept (a node never changes), and so are the last few entries' names, each made from the names asked for before it and what changed between them: walking a branch's history back reads each step's changes, not every name of every entry.

import { stateKey, stateOf } from "#codebase/tcmts/cli/diff";
import type { NameState } from "#codebase/tcmts/cli/diff";
import type { DefKind } from "#codebase/tcmts/core/types";
import type { NameChange, NameTreeNode } from "#codebase/tcmts/share";
import { unpacked } from "#codebase/tcmts/store";
import type { NamespaceBody, Store } from "#codebase/tcmts/store";
import type { StatementSync } from "node:sqlite";

export class NameTrees {
  private store: Store;
  private nodes = new Map<string, NameTreeNode>();
  private size = 0;
  // (what's kept of nodes, as their stored text's length)
  private budget = 16 * 1024 * 1024;
  private kinds = new Map<string, DefKind>();
  private states = new Map<string, { namespace: string; names: NameState }>();
  // (read from the table as namespaceRows does, not as getDef does: that keeps every record it reads, and a history's
  // pages read thousands of past versions, once each)
  private kindOf: StatementSync;
  private irOf: StatementSync;

  constructor(store: Store) {
    this.store = store;
    this.kindOf = store.db.prepare("SELECT kind FROM definitions WHERE hash = ?");
    this.irOf = store.db.prepare("SELECT ir FROM definitions WHERE hash = ?");
  }

  /** A definition's IR, as stored. */
  ir(hash: string): string {
    const row = this.irOf.get(hash) as { ir: unknown } | undefined;
    if (!row) throw new Error(`definition ${hash.slice(0, 8)} is missing from this codebase`);
    return unpacked(row.ir);
  }

  /** A namespace node. */
  node(hash: string): NameTreeNode {
    const kept = this.nodes.get(hash);
    if (kept) {
      // (the most recently read last: the first goes first)
      this.nodes.delete(hash);
      this.nodes.set(hash, kept);
      return kept;
    }
    const body = this.store.getNamespaces([hash])[0]?.body;
    if (body === undefined)
      throw new Error(`namespace ${hash.slice(0, 8)} is missing from this codebase`);
    const [, names, children] = JSON.parse(body) as NamespaceBody;
    const node: NameTreeNode = {
      names: new Map(names),
      children: new Map(children),
      size: body.length,
    };
    this.nodes.set(hash, node);
    this.size += node.size;
    for (const [h, n] of this.nodes) {
      if (this.size <= this.budget) break;
      this.nodes.delete(h);
      this.size -= n.size;
    }
    return node;
  }

  /** The hashes a name points at in a namespace (none: there's no such name), read down its path. */
  hashesAt(namespace: string, path: string): string[] {
    const parts = path.split(".");
    let node = this.node(namespace);
    for (const part of parts.slice(0, -1)) {
      const child = node.children.get(part);
      if (!child) return [];
      node = this.node(child);
    }
    return node.names.get(parts.at(-1)!) ?? [];
  }

  /** The names whose hashes differ between two namespaces (undefined: no names), reading only the nodes that differ. */
  delta(
    before: string | undefined,
    after: string | undefined,
    prefix = "",
    out: NameChange[] = [],
  ): NameChange[] {
    if (before === after) return out;
    const a = before === undefined ? undefined : this.node(before);
    const b = after === undefined ? undefined : this.node(after);
    for (const [n, hs] of b?.names ?? []) {
      const was = a?.names.get(n) ?? [];
      // (a node's hashes are sorted)
      if (was.join(" ") !== hs.join(" ")) out.push({ path: prefix + n, before: was, after: hs });
    }
    for (const [n, hs] of a?.names ?? [])
      if (!b?.names.has(n)) out.push({ path: prefix + n, before: hs, after: [] });
    for (const [n, h] of b?.children ?? [])
      this.delta(a?.children.get(n), h, `${prefix}${n}.`, out);
    for (const [n, h] of a?.children ?? [])
      if (!b?.children.has(n)) this.delta(h, undefined, `${prefix}${n}.`, out);
    return out;
  }

  /** The names as of a history entry, as `stateAt` reads them. Don't change what it returns: it's kept. */
  state(causal: string): NameState {
    const kept = this.states.get(causal);
    if (kept) {
      this.states.delete(causal);
      this.states.set(causal, kept);
      return kept.names;
    }
    const namespace = this.store.causal(causal)!.namespace;
    const last = [...this.states.values()].at(-1);
    const names = last ? this.moved(last, namespace) : this.read(namespace);
    this.states.set(causal, { namespace, names });
    if (this.states.size > 4) this.states.delete(this.states.keys().next().value!);
    return names;
  }

  private read(namespace: string): NameState {
    const rows = this.store.namespaceRows(namespace);
    for (const r of rows) this.kinds.set(r.hash, r.kind);
    return stateOf(rows);
  }

  /** Names kept for one namespace, changed to another's. */
  private moved(from: { namespace: string; names: NameState }, namespace: string): NameState {
    const names = new Map(from.names);
    for (const c of this.delta(from.namespace, namespace)) {
      for (const h of c.before) names.delete(stateKey(c.path, this.kind(h)));
      // (sets made anew: the ones there are shared with the names they came from)
      const now = new Map<string, Set<string>>();
      for (const h of c.after) {
        const key = stateKey(c.path, this.kind(h));
        now.set(key, (now.get(key) ?? new Set()).add(h));
      }
      for (const [key, hashes] of now) names.set(key, hashes);
    }
    return names;
  }

  private kind(hash: string): DefKind {
    let kind = this.kinds.get(hash);
    if (!kind) {
      if (this.kinds.size > 500_000) this.kinds.clear();
      this.kinds.set(
        hash,
        (kind = (this.kindOf.get(hash) as { kind: DefKind } | undefined)?.kind ?? "term"),
      );
    }
    return kind;
  }
}

uses

used by