codeMapOf

tcmts.share.codeMapOf · #fc4i3lfp · function · runs anywhere

The CodeMap of a branch's names, made a step at a time (each yield a place to let other work run). Its dots are the definitions (one for each hash; tests, what only tests use, and files left out), usersOf says what uses one (by hash) and placeOf where one runs; root, the project's namespace, is left off the labels. alsoUses are references no code makes, by name, from one to another (a manifest's to what its strings name): one to a namespace is to the three most used in it (a namespace of a hundred counts as no more than a name). Grouped by references, the clouds are communities (communities), each named for the namespaces most of it is in (their last names); grouped by namespace, they're the namespaces under the root (or under the one namespace nearly everything's in). Either way a cloud's puffs are the namespaces a level below.

import { isTestPath } from "#codebase/tcmts/cli/testing";
import { communities, layOutClouds } from "#codebase/tcmts/share";
import type { CodeMap } from "#codebase/tcmts/share";
import type { NameRow } from "#codebase/tcmts/store";

export function* codeMapOf(
  rows: NameRow[],
  usersOf: (hash: string) => string[],
  placeOf: (hash: string) => string,
  root: string,
  alsoUses: [string, string][] = [],
): Generator<void, CodeMap> {
  // tests are left out, and so is what only tests use (their helpers, however they use each other): of the code
  // something uses, all but what's used by something not a test or test-only
  const tests = new Set(rows.filter((r) => isTestPath(r.path)).map((r) => r.hash));
  const code = rows.filter((r) => r.kind !== "file" && !tests.has(r.hash));
  const usersBy = new Map(code.map((r) => [r.hash, usersOf(r.hash)]));
  const testOnly = new Set(code.filter((r) => usersBy.get(r.hash)!.length > 0).map((r) => r.hash));
  for (let changed = true; changed;) {
    changed = false;
    for (const h of testOnly) {
      if (!usersBy.get(h)!.some((u) => !tests.has(u) && !testOnly.has(u))) continue;
      testOnly.delete(h);
      changed = true;
    }
  }
  const seen = new Set<string>();
  const kept = code.filter((r) => !testOnly.has(r.hash) && !seen.has(r.hash) && !!seen.add(r.hash));
  const index = new Map(kept.map((r, j) => [r.hash, j]));
  const n = kept.length;
  const dots = kept.map((r) => ({
    path: r.path,
    type: r.kind === "type" || r.kind === "class",
    place: r.kind === "type" ? "" : placeOf(r.hash),
  }));
  const refs: number[] = [];
  for (const [j, r] of kept.entries()) {
    for (const u of usersBy.get(r.hash)!) {
      const i = index.get(u);
      if (i !== undefined && i !== j) refs.push(i, j);
    }
  }
  const at = new Map(kept.map((r, j) => [r.path, j]));
  const used = Array.from({ length: kept.length }, () => 0);
  for (let k = 1; k < refs.length; k += 2) used[refs[k]!]!++;
  for (const [from, to] of alsoUses) {
    const i = at.get(from);
    if (i === undefined) continue;
    const exact = at.get(to);
    const js =
      exact !== undefined
        ? [exact]
        : kept
            .flatMap((r, j) => (r.path.startsWith(`${to}.`) ? [j] : []))
            .sort((a, b) => used[b]! - used[a]!)
            .slice(0, 3);
    for (const j of js) if (j !== i) refs.push(i, j);
  }
  yield;
  // namespaces, relative to the root: a dot's at two depths below it (its cloud's and its puff's). A namespace holding
  // nearly everything (a library's one top namespace) groups nothing, so it's looked inside.
  const nsOf = (j: number) => kept[j]!.path.split(".").slice(0, -1);
  const atDepth = (j: number, d: number) => nsOf(j).slice(0, d).join(".");
  let base = root;
  let depth = root ? root.split(".").length : 0;
  for (;;) {
    const counts = new Map<string, number>();
    for (let j = 0; j < n; j++) {
      if (nsOf(j).length <= depth) continue;
      const k = atDepth(j, depth + 1);
      counts.set(k, (counts.get(k) ?? 0) + 1);
    }
    const [top, most] = [...counts].sort((a, b) => b[1] - a[1])[0] ?? ["", 0];
    if (!n || most < n * 0.8) break;
    base = top;
    depth++;
  }
  const under = (ns: string) =>
    base && ns.startsWith(`${base}.`) ? ns.slice(base.length + 1) : ns === base ? "" : ns;
  const named = (ns: string) => under(ns) || base.split(".").pop() || "top level";
  const puffsBy = (
    members: number[],
    key: (j: number) => string,
    label: (ns: string) => string,
  ) => {
    const by = new Map<string, number[]>();
    for (const j of members) {
      const k = key(j);
      const there = by.get(k);
      if (there) there.push(j);
      else by.set(k, [j]);
    }
    return [...by]
      .sort((a, b) => b[1].length - a[1].length)
      .map(([ns, ms]) => ({ label: label(ns), ns, members: ms }));
  };
  // by references: communities big enough to be a cloud (the rest together, as loose ends)
  const found = communities(
    n,
    Array.from({ length: refs.length / 2 }, (_, k): [number, number, number] => [
      refs[2 * k]!,
      refs[2 * k + 1]!,
      1,
    ]),
  );
  yield;
  const least = Math.max(2, Math.round(n / 200));
  const big = found.filter((c) => c.length >= least).sort((a, b) => b.length - a.length);
  // a group too small for a cloud joins the cloud it references most (either way); one that references none, the
  // cloud most of each one's namespace is in (a library's API nothing here uses, say); only what's left is loose
  const cloudOf = Array.from({ length: n }, () => -1);
  big.forEach((c, ci) => c.forEach((j) => (cloudOf[j] = ci)));
  const nbrs = Array.from({ length: n }, () => [] as number[]);
  for (let k = 0; k < refs.length; k += 2) {
    nbrs[refs[k]!]!.push(refs[k + 1]!);
    nbrs[refs[k + 1]!]!.push(refs[k]!);
  }
  const most = (tally: Map<number, number>) => [...tally].sort((a, b) => b[1] - a[1])[0]?.[0];
  const unplaced: number[] = [];
  for (const c of found.filter((c) => c.length < least)) {
    const tally = new Map<number, number>();
    for (const j of c)
      for (const k of nbrs[j]!)
        if (cloudOf[k]! >= 0) tally.set(cloudOf[k]!, (tally.get(cloudOf[k]!) ?? 0) + 1);
    const to = most(tally);
    if (to === undefined) unplaced.push(...c);
    else for (const j of c) big[(cloudOf[j] = to)]!.push(j);
  }
  const where = (d: number) => {
    const by = new Map<string, Map<number, number>>();
    for (let j = 0; j < n; j++) {
      if (cloudOf[j]! < 0) continue;
      const key = atDepth(j, d);
      const tally = by.get(key) ?? new Map<number, number>();
      tally.set(cloudOf[j]!, (tally.get(cloudOf[j]!) ?? 0) + 1);
      by.set(key, tally);
    }
    return by;
  };
  const byPuff = where(depth + 2);
  const byCloud = where(depth + 1);
  const loose: number[] = [];
  for (const j of unplaced) {
    const to =
      most(byPuff.get(atDepth(j, depth + 2)) ?? new Map()) ??
      most(byCloud.get(atDepth(j, depth + 1)) ?? new Map());
    if (to === undefined) loose.push(j);
    else big[(cloudOf[j] = to)]!.push(j);
  }
  // a cloud's name: the last names of the one or two namespaces most of it is in (one like `internal` says nothing,
  // so the next is taken); where two clouds would be called the same, the next namespace's too, then whole names
  const SAY_NOTHING = new Set([
    "internal",
    "util",
    "utils",
    "impl",
    "helpers",
    "common",
    "private",
  ]);
  const leaf = (label: string) => label.slice(label.lastIndexOf(".") + 1);
  const mains = big.map((members) => {
    const puffs = puffsBy(members, (j) => atDepth(j, depth + 2), named);
    const telling = puffs.filter((p) => !SAY_NOTHING.has(leaf(p.label)));
    const top = (telling.length ? telling : puffs)
      .slice(0, 2)
      .filter((p, i) => i === 0 || p.members.length >= members.length * 0.15);
    return { puffs, top };
  });
  const twice = (labels: string[]) => labels.map((l) => labels.filter((m) => m === l).length > 1);
  let labels = mains.map((m) => m.top.map((p) => leaf(p.label)).join(" + "));
  let clash = twice(labels);
  labels = labels.map((l, i) => {
    const m = mains[i]!;
    const more =
      clash[i] && m.puffs.find((p) => !m.top.includes(p) && !SAY_NOTHING.has(leaf(p.label)));
    return more ? `${l} · ${leaf(more.label)}` : l;
  });
  clash = twice(labels);
  labels = labels.map((l, i) => (clash[i] ? mains[i]!.top.map((p) => p.label).join(" + ") : l));
  const byRefs: { label: string; loose?: boolean; puffs: ReturnType<typeof puffsBy> }[] = mains.map(
    (m, i) => ({ label: labels[i]!, puffs: m.puffs }),
  );
  if (loose.length)
    byRefs.push({
      label: "loose ends",
      loose: true,
      puffs: puffsBy(loose, (j) => atDepth(j, depth + 2), named),
    });
  const clusters = yield* layOutClouds(byRefs, n, refs);
  // by namespace
  const byNs = puffsBy([...Array(n).keys()], (j) => atDepth(j, depth + 1), named).map((c) => ({
    label: c.label,
    ns: c.ns,
    puffs: puffsBy(
      c.members,
      (j) => atDepth(j, depth + 2),
      (ns) => (ns === c.ns ? c.label : ns.slice(c.ns.length + 1)),
    ),
  }));
  const namespaces = yield* layOutClouds(byNs, n, refs);
  return { dots, refs, clusters, namespaces };
}