// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>
// SPDX-License-Identifier: MIT

//! Rename and copy detection: deletions and additions among a list of
//! changed paths paired up as `-M` and `-C` pair them, scored as
//! `similarity` measures files.
//!
//! gitdiffcore(7) describes the stages in prose; how each one chooses was
//! found by asking git over thousands of generated trees:
//!
//! - **Sources** are the deleted paths; with copies also the modified
//!   ones and those whose type changed (their old contents), and with `--find-copies-harder` the
//!   unchanged ones. **Destinations** are the added paths. Both are taken
//!   in the order of the list.
//! - **Exact matches** come first, destination by destination: of the
//!   sources with the same object ID and the same kind of entry, the one
//!   scoring best on "same file name" plus "deleted and not yet taken"
//!   wins, the first in order on a tie. Without copies only deleted
//!   sources not yet taken qualify.
//! - **Same file name** (renames alone: not with copies, nor where `-B`
//!   broke a pair, though `-B` breaking nothing leaves it in): where
//!   exactly one remaining deleted source and exactly one remaining
//!   destination share a file name, they are paired if their score
//!   reaches halfway between the minimum and a full score.
//!   Where `-B` broke a pair, the deleted sources exact matches took
//!   stay among the inexact candidates below, holding places, though
//!   they cannot be renamed from again.
//! - **The limit**: the rest is skipped, with a warning, if the sources
//!   times the destinations left come to more than the limit squared;
//!   under `--find-copies-harder` git first tries again with the
//!   unchanged sources left out.
//! - **Inexact matches**: each remaining destination keeps four
//!   candidates. The first four sources fill them whatever they score;
//!   each later one replaces the first of the lowest-scoring if it scores
//!   higher (with "same file name" breaking ties). Sources whose sizes
//!   cannot reach the minimum score nothing but still take a place. The
//!   candidates reaching the minimum are sorted by score, ties kept in
//!   order, and taken first for renames (each deleted source once), then,
//!   with copies, for copies from any source.
//! - **Breaks** (`-B`): a modified file whose deletions and additions
//!   come to the break score is split into a deletion and an addition
//!   before any of this. The addition is a destination; the deletion is a
//!   rename source only if what was deleted reaches the merge score, and
//!   otherwise a copy source as a modified file is. A broken
//!   pair whose addition nothing else took is put back together, shown as
//!   a rewrite if its deletion was a source. A type change between a
//!   file and a symbolic link is always broken, as deep as can be, and put back together keeps its letter
//!   (`T100`).
//! - **Labels**: a deleted source used by several destinations is a
//!   rename for the last of them and a copy for the others, and its
//!   deletion is no longer listed. Inexact matches are only ever between
//!   regular files.

const std = @import("std");
const Allocator = std.mem.Allocator;

const object = @import("../object.zig");
const output = @import("output.zig");
const similarity = @import("similarity.zig");

const Pair = output.Pair;
const Side = output.Side;

/// How to look.
pub const Options = struct {
    /// Whether to look for renames at all; `-B` alone breaks rewrites
    /// without.
    renames: bool = true,
    /// `-C`: modified paths are sources too.
    copies: bool = false,
    /// `-B`: rewrites are broken into a deletion and an addition, which
    /// renames may take, and shown as rewrites if nothing does. It turns
    /// the same-file-name step off.
    breaks: ?Breaks = null,
    /// The minimum score, out of `similarity.max_score`.
    min_score: u32 = similarity.default_min_score,
    /// `-l`, `diff.renameLimit`; 0 for no limit.
    limit: u32 = 1000,
    /// `--rename-empty`: empty files may be paired.
    rename_empty: bool = true,
};

/// `-B[<n>][/<m>]`'s two scores, out of `similarity.max_score`.
pub const Breaks = struct {
    /// How much must be deleted and added together, against the larger
    /// file, to break a pair: 50% unless `<n>` says otherwise.
    break_score: u32 = similarity.max_score / 2,
    /// How much of the old file must be gone, against its size, to break
    /// it: 60% unless `<m>` says otherwise.
    merge_score: u32 = similarity.max_score * 6 / 10,
};

/// The smallest file, in bytes, `-B` breaks: the larger side must have
/// at least this many.
pub const break_min_size: u64 = 400;

/// What the limit made of the search, for the warnings git writes.
pub const Limited = struct {
    /// Whether the unchanged sources were left out rather than the
    /// inexact search skipped.
    copies_from_modified_only: bool,
    /// The limit that would have been enough.
    needed: usize,
};

/// What detection found.
pub const Result = struct {
    /// The pairs, renames and copies among them, in git's order.
    pairs: []Pair,
    /// Set when the limit cut the search short.
    limited: ?Limited = null,
    /// Whether the inexact search was held to the limit and came within
    /// it: some destination was left for it, and some source.
    within_limit: bool = false,

    /// Frees the list (not the paths, which are the caller's).
    pub fn deinit(r: *Result, gpa: Allocator) void {
        gpa.free(r.pairs);
        r.* = undefined;
    }
};

/// What detection can fail with: reading contents.
pub const Error = Allocator.Error || error{ContentsUnreadable};

const kind_mask: u32 = 0o170000;
const regular: u32 = 0o100000;

fn baseName(path: []const u8) []const u8 {
    return if (std.mem.findScalarLast(u8, path, '/')) |s| path[s + 1 ..] else path;
}

const SideInfo = struct {
    loaded: bool = false,
    id: object.Id = undefined,
    size: u64 = 0,
    signature: ?similarity.Signature = null,
};

const Detector = struct {
    gpa: Allocator,
    pairs: []const Pair,
    source: output.Source,
    options: Options,
    /// Per pair: the old side's and the new side's information.
    old_info: []SideInfo,
    new_info: []SideInfo,

    fn init(gpa: Allocator, pairs: []const Pair, source: output.Source, options: Options) Allocator.Error!Detector {
        const old_info = try gpa.alloc(SideInfo, pairs.len);
        errdefer gpa.free(old_info);
        const new_info = try gpa.alloc(SideInfo, pairs.len);
        @memset(old_info, .{});
        @memset(new_info, .{});
        return .{ .gpa = gpa, .pairs = pairs, .source = source, .options = options, .old_info = old_info, .new_info = new_info };
    }

    /// Takes what was loaded of one side, leaving nothing behind.
    fn take(d: *Detector, index: usize, old: bool) SideInfo {
        const info = if (old) &d.old_info[index] else &d.new_info[index];
        const taken = info.*;
        info.* = .{};
        return taken;
    }

    fn deinit(d: *Detector) void {
        for (d.old_info) |*i| if (i.signature) |*s| s.deinit(d.gpa);
        for (d.new_info) |*i| if (i.signature) |*s| s.deinit(d.gpa);
        d.gpa.free(d.old_info);
        d.gpa.free(d.new_info);
    }

    /// Loads one side: its object ID (hashing a working tree file whose ID
    /// is not known), size and, for a regular file, its signature.
    fn load(d: *Detector, index: usize, old: bool, want_signature: bool) Error!*SideInfo {
        const p = &d.pairs[index];
        const info = if (old) &d.old_info[index] else &d.new_info[index];
        const side = if (old) p.old else p.new;
        if (info.loaded and (!want_signature or info.signature != null or side.mode & kind_mask != regular)) return info;
        if (side.mode & kind_mask == 0o160000) {
            info.* = .{ .loaded = true, .id = side.id, .size = 0 };
            return info;
        }
        var view = p.*;
        if (old) if (p.old_path) |op| {
            view.path = op;
        };
        const contents = d.source.read(d.source.context, d.gpa, &view, side) catch |err| switch (err) {
            error.OutOfMemory => return error.OutOfMemory,
            else => return error.ContentsUnreadable,
        };
        defer if (contents.allocation) |a| d.gpa.free(a);
        info.loaded = true;
        info.size = contents.bytes.len;
        info.id = if (side.id_known) side.id else object.hash(side.id.object_format, .blob, contents.bytes);
        if (want_signature and side.mode & kind_mask == regular and info.signature == null)
            info.signature = try similarity.signature(d.gpa, contents.bytes);
        return info;
    }

    fn idOf(d: *Detector, index: usize, old: bool) Error!object.Id {
        const p = &d.pairs[index];
        const side = if (old) p.old else p.new;
        if (side.id_known) return side.id;
        return (try d.load(index, old, false)).id;
    }
};

const Match = struct {
    source: usize,
    score: u32,
};

const Candidate = struct {
    score: u32,
    same_name: bool,
    destination: usize,
    source: usize,
};

fn candidateBetter(a: Candidate, b: Candidate) bool {
    if (a.score != b.score) return a.score > b.score;
    return a.same_name and !b.same_name;
}

fn candidateOrder(_: void, a: Candidate, b: Candidate) bool {
    return candidateBetter(a, b);
}

/// Labels the pairs `pairs` takes from each deleted source again, once
/// they have been put in another order (an orderfile, `--rotate-to`,
/// `--skip-to` before it drops any): the last of them is the rename and
/// the others are copies, as git was seen to decide in the order the
/// pairs are written in rather than the order they were found in.
pub fn relabel(gpa: Allocator, pairs: []Pair) Allocator.Error!void {
    // The sources a rename took, and whether a later pair has claimed
    // the rename yet.
    var gone: std.StringHashMapUnmanaged(bool) = .empty;
    defer gone.deinit(gpa);
    for (pairs) |*p| if (p.status == .renamed) try gone.put(gpa, p.old_path.?, false);
    if (gone.count() == 0) return;
    var i = pairs.len;
    while (i > 0) {
        i -= 1;
        const p = &pairs[i];
        if (!p.moved()) continue;
        const claimed = gone.getPtr(p.old_path.?) orelse continue;
        p.status = if (claimed.*) .copied else .renamed;
        claimed.* = true;
    }
}

/// Pairs deletions with additions among `pairs` (in git's order, with
/// any unchanged paths `--find-copies-harder` adds marked `unmodified`),
/// reading contents from `source`, after breaking rewrites as `-B` asks.
/// The result lists every pair but the unchanged ones and the deletions
/// that became renames; a broken pair nothing took is a rewrite.
pub fn detect(gpa: Allocator, pairs: []const Pair, source: output.Source, options: Options) Error!Result {
    // Break rewrites first: each broken pair becomes a deletion and an
    // addition at its place.
    var expanded: std.ArrayList(Pair) = .empty;
    defer expanded.deinit(gpa);
    // For each entry of `expanded`, the pair it came from, if broken,
    // and how dissimilar the two were.
    var halves: std.ArrayList(?Half) = .empty;
    defer halves.deinit(gpa);
    var infos: std.ArrayList([2]SideInfo) = .empty;
    defer infos.deinit(gpa);
    {
        var b: Detector = try .init(gpa, pairs, source, options);
        defer b.deinit();
        for (pairs, 0..) |p, i| {
            if (options.breaks) |br| if (try breakScore(&b, i, br)) |brk| {
                // The old half of a pair not deep enough is no rename
                // source, but still a copy source, as a modified file is.
                if (brk.deep)
                    try expanded.append(gpa, .{ .status = .deleted, .path = p.path, .old = p.old, .new = .{ .id = object.Id.zero(p.old.id.object_format) } })
                else
                    try expanded.append(gpa, p);
                try expanded.append(gpa, .{ .status = .added, .path = p.path, .old = .{ .id = object.Id.zero(p.new.id.object_format) }, .new = p.new });
                const origin: Half = .{ .pair = p, .dissimilarity = brk.dissimilarity, .deep = brk.deep, .partner = expanded.items.len - 1 };
                try halves.append(gpa, origin);
                var other = origin;
                other.partner = expanded.items.len - 2;
                try halves.append(gpa, other);
                try infos.append(gpa, .{ b.take(i, true), .{} });
                try infos.append(gpa, .{ .{}, b.take(i, false) });
                continue;
            };
            try expanded.append(gpa, p);
            try halves.append(gpa, null);
            try infos.append(gpa, .{ b.take(i, true), b.take(i, false) });
        }
    }

    var d: Detector = try .init(gpa, expanded.items, source, options);
    defer d.deinit();
    for (infos.items, 0..) |info, k| {
        d.old_info[k] = info[0];
        d.new_info[k] = info[1];
    }
    // The detector owns the signatures now.
    infos.clearRetainingCapacity();

    var sources: std.ArrayList(usize) = .empty;
    defer sources.deinit(gpa);
    var destinations: std.ArrayList(usize) = .empty;
    defer destinations.deinit(gpa);
    for (expanded.items, 0..) |p, i| switch (p.status) {
        .deleted => try sources.append(gpa, i),
        .modified, .type_changed => if (options.copies) try sources.append(gpa, i),
        .unmodified => if (options.copies) try sources.append(gpa, i),
        .added => try destinations.append(gpa, i),
        else => {},
    };

    const matches = try gpa.alloc(?Match, expanded.items.len);
    defer gpa.free(matches);
    @memset(matches, null);
    // Deleted sources taken by a rename.
    const taken = try gpa.alloc(bool, expanded.items.len);
    defer gpa.free(taken);
    @memset(taken, false);

    var limited: ?Limited = null;
    var within_limit = false;
    if (options.renames and destinations.items.len != 0 and sources.items.len != 0) {
        try exactStep(&d, sources.items, destinations.items, matches, taken);
        // -B was seen to leave the same-name step out only where it
        // actually broke a pair.
        const broke_any = expanded.items.len != pairs.len;
        if (!options.copies and !broke_any) try nameStep(&d, sources.items, destinations.items, matches, taken);
        limited = try inexactStep(&d, sources.items, destinations.items, matches, taken, broke_any, &within_limit);
    }
    return .{ .pairs = try assemble(gpa, &d, matches, halves.items), .limited = limited, .within_limit = within_limit };
}

/// One half of a broken pair.
const Half = struct {
    /// The pair before it was broken.
    pair: Pair,
    /// How much of the old file is gone, out of `similarity.max_score`.
    dissimilarity: u32,
    /// Whether that reaches the merge score: only then is the old half a
    /// rename source, and the pair shown as a rewrite if nothing takes it.
    deep: bool,
    /// The other half's place.
    partner: usize,
};

const Broken = struct { dissimilarity: u32, deep: bool };

/// Whether `-B` breaks pair `i`, and if so how: as git was seen to decide
/// over hundreds of generated edits, a modified regular file is broken
/// when the larger side has at least `break_min_size` bytes and what was
/// deleted and what was added come to `break_score` of the larger side;
/// it is deep when what was deleted comes to `merge_score` of the old.
///
/// The two amounts are not measured alike. What was deleted is the old
/// file's whole size less what was copied, so the carriage returns of a
/// CRLF file count as deleted; what was added is the new file's chunked
/// bytes less what was copied, so its carriage returns before newlines
/// do not count at all. Sizes (the larger side, the 400 bytes, the old
/// size the merge score is taken against) are whole sizes. gitdiffcore(7)
/// says the smaller side; git was seen to use the larger. What was
/// deleted on its own, against the old size, also breaks a pair, with
/// one exception for pairs that added almost nothing (see the body).
fn breakScore(d: *Detector, i: usize, br: Breaks) Error!?Broken {
    const p = &d.pairs[i];
    // A type change between a file and a symbolic link is always
    // broken, wholly dissimilar, whatever its size: git shows one nothing takes as `T100` and a rewrite in
    // `--summary`, and its old half was seen to be taken as a source.
    if (p.status == .type_changed) {
        // Not a gitlink, on either side.
        if (p.old.mode & kind_mask == 0o160000 or p.new.mode & kind_mask == 0o160000) return null;
        return .{ .dissimilarity = similarity.max_score, .deep = true };
    }
    if (p.status != .modified) return null;
    if (p.old.mode & kind_mask != regular or p.new.mode & kind_mask != regular) return null;
    if (p.old.id_known and p.new.id_known and p.old.id.eql(p.new.id)) return null;
    const a = try d.load(i, true, true);
    const b = try d.load(i, false, true);
    const larger = @max(a.size, b.size);
    // A file that was empty is never broken.
    if (larger < break_min_size or a.size == 0) return null;
    const shared = similarity.copied(a.signature.?, b.signature.?);
    const deleted = a.size - shared;
    const added = b.signature.?.chunked - shared;
    const max: u128 = similarity.max_score;
    const have = @as(u128, deleted) * max;
    const want = @as(u128, br.break_score) * a.size;
    // What was deleted alone, against the old size, breaks the pair once
    // it is a whole point of the score above the break score, whatever
    // was added and however large the new file grew.
    if (have < want + a.size) {
        // Just above the break score, a pair that added next to nothing
        // (less than a twentieth of what was deleted and of what was
        // kept) is a removal, not a rewrite: git left such pairs whole
        // at that one score while breaking them both below and above it.
        if (have > want and added * 20 < deleted and added * 20 < shared) return null;
        if (@as(u128, deleted + added) * max < @as(u128, br.break_score) * larger) return null;
    }
    const deep = @as(u128, deleted) * max >= @as(u128, br.merge_score) * a.size;
    return .{ .dissimilarity = @intCast(@as(u128, deleted) * max / a.size), .deep = deep };
}

fn isFree(d: *const Detector, s: usize, taken: []const bool) bool {
    return d.pairs[s].status == .deleted and !taken[s];
}

fn emptyId(format: object.Format) object.Id {
    return object.hash(format, .blob, "");
}

fn exactStep(d: *Detector, sources: []const usize, destinations: []const usize, matches: []?Match, taken: []bool) Error!void {
    for (destinations) |t| {
        const dst = &d.pairs[t];
        const dst_id = try d.idOf(t, false);
        if (!d.options.rename_empty and dst_id.eql(emptyId(dst_id.object_format))) continue;
        var best: ?usize = null;
        var best_rank: u8 = 0;
        for (sources) |s| {
            const src = &d.pairs[s];
            if (src.old.mode & kind_mask != dst.new.mode & kind_mask) continue;
            const free = isFree(d, s, taken);
            if (!free and !d.options.copies) continue;
            if (!(try d.idOf(s, true)).eql(dst_id)) continue;
            const rank: u8 = @as(u8, @intFromBool(std.mem.eql(u8, baseName(src.path), baseName(dst.path)))) + @intFromBool(free);
            if (best == null or rank > best_rank) {
                best = s;
                best_rank = rank;
            }
        }
        if (best) |s| {
            matches[t] = .{ .source = s, .score = similarity.max_score };
            if (d.pairs[s].status == .deleted) taken[s] = true;
        }
    }
}

fn scorePair(d: *Detector, s: usize, t: usize, check_sizes: bool) Error!u32 {
    const src = &d.pairs[s];
    const dst = &d.pairs[t];
    if (src.old.mode & kind_mask != regular or dst.new.mode & kind_mask != regular) return 0;
    const a = try d.load(s, true, false);
    const b = try d.load(t, false, false);
    // Empty files pair only exactly.
    if (a.size == 0 or b.size == 0) return 0;
    if (check_sizes and !similarity.sizesCanReach(a.size, b.size, d.options.min_score)) return 0;
    const as = (try d.load(s, true, true)).signature.?;
    const bs = (try d.load(t, false, true)).signature.?;
    return similarity.score(a.size, b.size, similarity.copied(as, bs));
}

fn nameStep(d: *Detector, sources: []const usize, destinations: []const usize, matches: []?Match, taken: []bool) Error!void {
    const gpa = d.gpa;
    // For each file name: the one remaining source and destination, or
    // more than one.
    const Slot = struct { index: usize = 0, count: usize = 0 };
    var by_source: std.StringHashMapUnmanaged(Slot) = .empty;
    defer by_source.deinit(gpa);
    var by_destination: std.StringHashMapUnmanaged(Slot) = .empty;
    defer by_destination.deinit(gpa);
    for (sources) |s| {
        if (!isFree(d, s, taken)) continue;
        const gop = try by_source.getOrPut(gpa, baseName(d.pairs[s].path));
        if (!gop.found_existing) gop.value_ptr.* = .{};
        gop.value_ptr.index = s;
        gop.value_ptr.count += 1;
    }
    for (destinations) |t| {
        if (matches[t] != null) continue;
        const gop = try by_destination.getOrPut(gpa, baseName(d.pairs[t].path));
        if (!gop.found_existing) gop.value_ptr.* = .{};
        gop.value_ptr.index = t;
        gop.value_ptr.count += 1;
    }
    const threshold = (d.options.min_score + similarity.max_score) / 2;
    for (destinations) |t| {
        if (matches[t] != null) continue;
        const name = baseName(d.pairs[t].path);
        const ds = by_destination.get(name) orelse continue;
        if (ds.count != 1) continue;
        const ss = by_source.get(name) orelse continue;
        if (ss.count != 1) continue;
        const sc = try scorePair(d, ss.index, t, false);
        if (sc >= threshold) {
            matches[t] = .{ .source = ss.index, .score = sc };
            taken[ss.index] = true;
        }
    }
}

const slots = 4;

/// `broke_any`: `-B` broke a pair, and then git was seen to keep the
/// deleted sources exact matches took among the candidates, holding
/// places they can no longer be renamed from.
/// `within_limit` is set when the pairs to score came within the limit.
fn inexactStep(d: *Detector, all_sources: []const usize, destinations: []const usize, matches: []?Match, taken: []bool, broke_any: bool, within_limit: *bool) Error!?Limited {
    const gpa = d.gpa;
    var remaining: std.ArrayList(usize) = .empty;
    defer remaining.deinit(gpa);
    for (destinations) |t| if (matches[t] == null) try remaining.append(gpa, t);
    if (remaining.items.len == 0) return null;

    var sources: std.ArrayList(usize) = .empty;
    defer sources.deinit(gpa);
    for (all_sources) |s| {
        const listed = isFree(d, s, taken) or (broke_any and d.pairs[s].status == .deleted);
        if (!d.options.copies and !listed) continue;
        try sources.append(gpa, s);
    }
    if (sources.items.len == 0) return null;

    var limited: ?Limited = null;
    const limit: u64 = d.options.limit;
    const too_many = struct {
        fn f(lim: u64, a: usize, b: usize) bool {
            return lim != 0 and @as(u128, a) * b > @as(u128, lim) * lim;
        }
    }.f;
    if (too_many(limit, sources.items.len, remaining.items.len)) {
        const needed = @max(sources.items.len, remaining.items.len);
        // Under --find-copies-harder, git tries again without the
        // unchanged sources.
        var modified: usize = 0;
        var any_unchanged = false;
        for (sources.items) |s| {
            if (d.pairs[s].status == .unmodified) any_unchanged = true else modified += 1;
        }
        if (!any_unchanged or too_many(limit, modified, remaining.items.len)) {
            return .{ .copies_from_modified_only = false, .needed = needed };
        }
        var k: usize = 0;
        for (sources.items) |s| {
            if (d.pairs[s].status == .unmodified) continue;
            sources.items[k] = s;
            k += 1;
        }
        sources.shrinkRetainingCapacity(k);
        limited = .{ .copies_from_modified_only = true, .needed = needed };
    } else within_limit.* = true;

    var kept: std.ArrayList(Candidate) = .empty;
    defer kept.deinit(gpa);
    for (remaining.items) |t| {
        if (d.pairs[t].new.mode & kind_mask != regular) continue;
        var best: [slots]Candidate = undefined;
        var n: usize = 0;
        const dst_name = baseName(d.pairs[t].path);
        for (sources.items) |s| {
            const c: Candidate = .{
                .score = try scorePair(d, s, t, true),
                .same_name = std.mem.eql(u8, baseName(d.pairs[s].path), dst_name),
                .destination = t,
                .source = s,
            };
            if (n < slots) {
                best[n] = c;
                n += 1;
                continue;
            }
            var low: usize = 0;
            for (best[1..], 1..) |b, j| {
                if (candidateBetter(best[low], b)) low = j;
            }
            if (candidateBetter(c, best[low])) best[low] = c;
        }
        for (best[0..n]) |c| if (c.score >= d.options.min_score) try kept.append(gpa, c);
    }
    std.mem.sort(Candidate, kept.items, {}, candidateOrder);
    for (kept.items) |c| {
        if (matches[c.destination] != null) continue;
        if (!isFree(d, c.source, taken)) continue;
        matches[c.destination] = .{ .source = c.source, .score = c.score };
        taken[c.source] = true;
    }
    if (d.options.copies) for (kept.items) |c| {
        if (matches[c.destination] != null) continue;
        matches[c.destination] = .{ .source = c.source, .score = c.score };
    };
    return limited;
}

/// A side with the object ID detection worked out, if it hashed one: git
/// shows the IDs of working tree files it read to look for renames.
fn known(side: Side, info: SideInfo) Side {
    var s = side;
    if (!s.id_known and info.loaded and s.mode & kind_mask != 0o160000) {
        s.id = info.id;
        s.id_known = true;
    }
    return s;
}

fn assemble(gpa: Allocator, d: *const Detector, matches: []const ?Match, halves: []const ?Half) Allocator.Error![]Pair {
    const pairs = d.pairs;
    // Whether a deleted source is gone from the new side: a broken
    // pair's deleted half is not, if its added half was left to it.
    const gone = try gpa.alloc(bool, pairs.len);
    defer gpa.free(gone);
    for (pairs, 0..) |p, i| {
        gone[i] = p.status == .deleted;
        if (halves[i]) |h| if (p.status == .deleted) {
            const m = matches[h.partner];
            gone[i] = m != null and m.?.source != i;
        };
    }
    // The last destination using each source that is gone is its rename.
    const last_use = try gpa.alloc(?usize, pairs.len);
    defer gpa.free(last_use);
    @memset(last_use, null);
    for (matches, 0..) |m, t| if (m) |x| {
        if (gone[x.source]) last_use[x.source] = t;
    };
    var out: std.ArrayList(Pair) = .empty;
    errdefer out.deinit(gpa);
    for (pairs, 0..) |p, i| {
        if (p.status == .unmodified) continue;
        if (halves[i]) |h| {
            // The old half is shown with the new half, or not at all.
            if (h.partner > i) continue;
            const m = matches[i];
            if (m == null or m.?.source == h.partner) {
                var q = h.pair;
                q.old = known(q.old, d.old_info[h.partner]);
                q.new = known(q.new, d.new_info[i]);
                if (h.deep) {
                    q.score = h.dissimilarity;
                    q.rewrite = true;
                }
                try out.append(gpa, q);
                continue;
            }
        }
        if (p.status == .deleted and last_use[i] != null) continue;
        if (matches[i]) |m| {
            const src = pairs[m.source];
            const rename = gone[m.source] and last_use[m.source].? == i;
            try out.append(gpa, .{
                .status = if (rename) .renamed else .copied,
                .path = p.path,
                .old_path = src.path,
                .old = known(src.old, d.old_info[m.source]),
                .new = known(p.new, d.new_info[i]),
                .score = m.score,
            });
            continue;
        }
        var q = p;
        if (q.status == .added) q.new = known(q.new, d.new_info[i]);
        try out.append(gpa, q);
    }
    return out.toOwnedSlice(gpa);
}

// -- tests ---------------------------------------------------------------------

const TestSource = struct {
    contents: std.StringHashMapUnmanaged([]const u8) = .empty,

    fn read(context: *anyopaque, gpa: Allocator, pair: *const Pair, side: Side) output.Error!output.Contents {
        _ = gpa;
        _ = side;
        const self: *TestSource = @ptrCast(@alignCast(context));
        return .{ .bytes = self.contents.get(pair.path) orelse return error.ContentsUnreadable };
    }
};

fn testPair(status: output.Status, path: []const u8, data: []const u8) Pair {
    const id = object.hash(.sha1, .blob, data);
    const present: Side = .{ .mode = 0o100644, .id = id };
    const absent: Side = .{ .id = object.Id.zero(.sha1) };
    return .{
        .status = status,
        .path = path,
        .old = if (status == .added) absent else present,
        .new = if (status == .deleted) absent else present,
    };
}

test "a rename and a copy" {
    const gpa = std.testing.allocator;
    const base = "one\ntwo\nthree\nfour\nfive\nsix\nseven\neight\nnine\nten\n";
    const edited = "one\ntwo\nthree\nfour\nfive\nsix\nseven\neight\nnine\nTEN\n";
    var ts: TestSource = .{};
    defer ts.contents.deinit(gpa);
    try ts.contents.put(gpa, "a", base);
    try ts.contents.put(gpa, "b", edited);
    try ts.contents.put(gpa, "c", base);
    const pairs = [_]Pair{ testPair(.deleted, "a", base), testPair(.added, "b", edited), testPair(.added, "c", base) };
    var r = try detect(gpa, &pairs, .{ .context = &ts, .read = TestSource.read }, .{ .copies = true });
    defer r.deinit(gpa);
    try std.testing.expectEqual(@as(usize, 2), r.pairs.len);
    // "c" is the exact match, and comes last, so it is the rename; "b" is
    // a copy of the same source.
    try std.testing.expectEqual(output.Status.copied, r.pairs[0].status);
    try std.testing.expectEqualStrings("b", r.pairs[0].path);
    try std.testing.expectEqualStrings("a", r.pairs[0].old_path.?);
    try std.testing.expectEqual(@as(u32, 91), similarity.percent(r.pairs[0].score));
    try std.testing.expectEqual(output.Status.renamed, r.pairs[1].status);
    try std.testing.expectEqual(similarity.max_score, r.pairs[1].score);
}