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;
  from?: string;
  status: "added" | "deleted" | "modified" | "renamed";
  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 detectRenames(repo, changes.sort((a, b) => (a.path < b.path ? -1 : 1)));
}

const RENAME_SIMILARITY = 0.5;

type LineProfile = { counts: Map<string, number>; lines: number };

function profile(text: string): LineProfile {
  const lines = text === "" ? [] : text.split("\n");
  if (lines.at(-1) === "") lines.pop();
  const counts = new Map<string, number>();
  for (const line of lines) counts.set(line, (counts.get(line) ?? 0) + 1);
  return { counts, lines: lines.length };
}

/**
 * git-style rename detection over a tree diff's deletions and additions
 * 1. pair identical blobs at differing paths
 * 2. pair most-similar blobs that have >=50% shared lines
 */
async function detectRenames(repo: GitRepo, changes: FileChange[]): Promise<FileChange[]> {
  // a path that changed kind is both deleted and added; its halves belong to each other, not to a rename
  const addedPaths = new Set(changes.filter(c => c.status === "added").map(c => c.path));
  const deleted = changes.filter(c => c.status === "deleted" && !addedPaths.has(c.path));
  const deletedPaths = new Set(changes.filter(c => c.status === "deleted").map(c => c.path));
  const added = changes.filter(c => c.status === "added" && !deletedPaths.has(c.path));
  if (deleted.length === 0 || added.length === 0) return changes;

  // pairing converts the added entry in place; `changes` is sorted by the new path, so it stays sorted
  const gone = new Set<FileChange>();
  const taken = new Set<FileChange>();
  const pair = (from: FileChange, to: FileChange) => {
    gone.add(from);
    taken.add(to);
    to.status = "renamed";
    to.from = from.path;
    to.oldOid = from.oldOid;
  };

  const addedByOid = new Map<string, FileChange[]>();
  for (const change of added) {
    const queue = addedByOid.get(change.newOid!) ?? [];
    queue.push(change);
    addedByOid.set(change.newOid!, queue);
  }
  for (const change of deleted) {
    const match = addedByOid.get(change.oldOid!)?.shift();
    if (match) pair(change, match);
  }

  const leftoverDeleted = deleted.filter(c => !gone.has(c));
  const leftoverAdded = added.filter(c => !taken.has(c));
  if (leftoverDeleted.length > 0 && leftoverAdded.length > 0) {
    const leftover = [...leftoverDeleted, ...leftoverAdded];
    await repo.prefetch(leftover.map(c => (c.oldOid ?? c.newOid)!), { depth: 0 });
    const profiles = new Map<FileChange, LineProfile | null>();
    await Promise.all(leftover.map(async change => {
      const data = await repo.blob((change.oldOid ?? change.newOid)!);
      profiles.set(
        change,
        data.subarray(0, 8192).includes(0) ? null : profile(new TextDecoder().decode(data)),
      );
    }));
    const candidates: { from: FileChange; to: FileChange; score: number }[] = [];
    for (const from of leftoverDeleted) {
      const a = profiles.get(from);
      if (!a || a.lines === 0) continue;
      for (const to of leftoverAdded) {
        const b = profiles.get(to);
        if (!b || b.lines === 0) continue;
        if (Math.min(a.lines, b.lines) / Math.max(a.lines, b.lines) < RENAME_SIMILARITY) continue;
        let shared = 0;
        const [smaller, larger] = a.counts.size <= b.counts.size ? [a, b] : [b, a];
        for (const [line, count] of smaller.counts) {
          shared += Math.min(count, larger.counts.get(line) ?? 0);
        }
        const score = shared / Math.max(a.lines, b.lines);
        if (score >= RENAME_SIMILARITY) candidates.push({ from, to, score });
      }
    }
    candidates.sort((x, y) =>
      y.score - x.score || (x.from.path < y.from.path ? -1 : 1) || (x.to.path < y.to.path ? -1 : 1)
    );
    for (const { from, to } of candidates) {
      if (!gone.has(from) && !taken.has(to)) pair(from, to);
    }
  }

  return gone.size === 0 ? changes : changes.filter(c => !gone.has(c));
}