char/sorcery

git clone https://git.t4t.associates/char/sorcery

Charlotte Somfix path-history smart query type (+ add a new obj frame type)5d40e972026-09-03

import type { Commit, LocatedObject } from "./types.ts";
import type { GitRepo } from "./repo.ts";

/**
 * changes per path-history request. each comes with its trees along the
 * path, and the daemon's bundles cap out at 128 objects.
 */
const HISTORY_PAGE = 10;

/** breadth-first walk matching gix's default revision order */
export async function* log(repo: GitRepo, tips: string[], pageSize: number): AsyncGenerator<Commit> {
  const seen = new Set<string>(tips);
  const frontier = [...tips];

  while (frontier.length > 0) {
    await repo.prefetch(frontier.slice(0, pageSize), { smart: "commit-pagination", limit: pageSize });
    for (let i = 0; i < pageSize && frontier.length > 0; i++) {
      const commit = await repo.commit(frontier.shift()!);
      yield commit;
      for (const parent of commit.parents) {
        if (seen.has(parent)) continue;
        seen.add(parent);
        frontier.push(parent);
      }
    }
  }
}

export interface FileChange {
  path: string;
  status: "added" | "deleted" | "modified";
  oldOid: string | null;
  newOid: string | null;
  mode: number;
}

const TREE = 0o040000;
const GITLINK = 0o160000;
const isTree = (mode: number) => (mode & 0o170000) === TREE;

/** the entry at `path` within `tree`; null if absent (or under a non-tree) */
export async function objectAt(repo: GitRepo, tree: string, path: string[]): Promise<LocatedObject | null> {
  let object: LocatedObject | null = { oid: tree, mode: TREE };
  for (const name of path) {
    if (!object || !isTree(object.mode)) return null;
    object = (await repo.tree(object.oid)).find(entry => entry.name === name) ?? null;
  }
  return object;
}

export interface PathChange {
  commit: Commit;
  /** null when the commit deleted it */
  object: LocatedObject | null;
}

/**
 * `git log -- path`: commits whose object at `path` differs from every
 * parent's, following only a TREESAME parent through merges that didn't
 * touch it. the daemon computes pages when it can; otherwise the same walk
 * runs here, picking up from whatever frontier the daemon last returned.
 * `scanned` reports commits examined by the local walk, for progress.
 */
export async function* pathHistory(
  repo: GitRepo,
  tips: string[],
  path: string[],
  scanned: (count: number) => void,
): AsyncGenerator<PathChange> {
  let frontier = tips;
  while (frontier.length > 0) {
    const page = await repo.pathHistory(frontier, path, HISTORY_PAGE);
    if (!page) return yield* walkPathHistory(repo, frontier, path, scanned);
    for (const commit of page.commits) {
      yield { commit, object: await objectAt(repo, commit.tree, path) };
    }
    frontier = page.frontier;
  }
}

const sameObject = (a: LocatedObject | null, b: LocatedObject | null) =>
  a?.oid === b?.oid && a?.mode === b?.mode;

async function* walkPathHistory(
  repo: GitRepo,
  frontier: string[],
  path: string[],
  scanned: (count: number) => void,
): AsyncGenerator<PathChange> {
  const seen = new Set<string>();
  const queue: Commit[] = []; // newest committer date first, like git
  const located = new Map<string, LocatedObject | null>();
  const locate = async (tree: string) => {
    let object = located.get(tree);
    if (object === undefined) located.set(tree, object = await objectAt(repo, tree, path));
    return object;
  };
  const push = async (oid: string) => {
    const commit = await repo.commit(oid); // peels tags
    if (seen.has(commit.oid)) return;
    seen.add(commit.oid);
    const at = queue.findIndex(other => other.committer.time < commit.committer.time);
    queue.splice(at === -1 ? queue.length : at, 0, commit);
  };

  for (const oid of frontier) await push(oid);
  while (queue.length > 0) {
    const commit = queue.shift()!;
    scanned(1);
    const object = await locate(commit.tree);
    let treesame: string | undefined;
    for (const parent of commit.parents) {
      if (sameObject(object, await locate((await repo.commit(parent)).tree))) {
        treesame = parent;
        break;
      }
    }
    if (treesame !== undefined) {
      await push(treesame);
      continue;
    }
    if (commit.parents.length === 0 && !object) continue;
    yield { commit, object };
    for (const parent of commit.parents) await push(parent);
  }
}

/** diff two trees, skipping identical subtrees by oid */
export async function treeDiff(
  repo: GitRepo,
  oldTree: string | null,
  newTree: string | null,
  prefix = "",
): Promise<FileChange[]> {
  if (oldTree === newTree) return [];
  const changes: FileChange[] = [];
  let frontier = [{ oldTree, newTree, prefix }];

  while (frontier.length > 0) {
    await repo.prefetch(
      frontier.flatMap(pair => [pair.oldTree, pair.newTree].filter(oid => oid !== null)),
      { depth: 0 },
    );
    const subtrees: typeof frontier = [];

    for (const pair of frontier) {
      if (pair.oldTree === pair.newTree) continue;
      const [olds, news] = await Promise.all([
        pair.oldTree ? repo.tree(pair.oldTree) : Promise.resolve([]),
        pair.newTree ? repo.tree(pair.newTree) : Promise.resolve([]),
      ]);
      const oldByName = new Map(olds.map(entry => [entry.name, entry]));

      for (const entry of news) {
        const old = oldByName.get(entry.name);
        oldByName.delete(entry.name);
        const path = pair.prefix + entry.name;
        if (old?.oid === entry.oid && old.mode === entry.mode) continue;

        if (isTree(entry.mode) || (old && isTree(old.mode))) {
          subtrees.push({
            oldTree: old && isTree(old.mode) ? old.oid : null,
            newTree: isTree(entry.mode) ? entry.oid : null,
            prefix: path + "/",
          });
          // an entry that changed kind between tree and file also diffs as a file
          if (!isTree(entry.mode) && entry.mode !== GITLINK) {
            changes.push({ path, status: "added", oldOid: null, newOid: entry.oid, mode: entry.mode });
          }
          if (old && !isTree(old.mode) && old.mode !== GITLINK) {
            changes.push({ path, status: "deleted", oldOid: old.oid, newOid: null, mode: old.mode });
          }
          continue;
        }
        if (entry.mode === GITLINK || old?.mode === GITLINK) continue;
        changes.push({
          path,
          status: old ? "modified" : "added",
          oldOid: old?.oid ?? null,
          newOid: entry.oid,
          mode: entry.mode,
        });
      }

      for (const old of oldByName.values()) {
        const path = pair.prefix + old.name;
        if (isTree(old.mode)) {
          subtrees.push({ oldTree: old.oid, newTree: null, prefix: path + "/" });
        } else if (old.mode !== GITLINK) {
          changes.push({ path, status: "deleted", oldOid: old.oid, newOid: null, mode: old.mode });
        }
      }
    }
    frontier = subtrees;
  }

  return changes.sort((a, b) => (a.path < b.path ? -1 : 1));
}