lattice_diff/

compute.rs

//! Hunk computation: the engine's single public entry point is
//! [`compute_diff`], which dispatches by participant count to
//! crate-private [`two_way`] / [`three_way`] helpers. External
//! consumers (subsystem, benches, integration tests in other
//! crates) go through `compute_diff` exclusively — no code
//! outside this crate branches on arity. v1 supports N ∈
//! {0, 1, 2, 3}; N=0 errors as `Empty`, N=1 returns an empty
//! `HunkIndex` (dormant session, no peers to diff against), N=2
//! / N=3 dispatch to the named helpers, N≥4 errors as
//! `Unsupported`. See `docs/dev/architecture/n-way-diff-membership.md`
//! (D.8) for the rationale.
//!
//! Both helpers materialise the input ropes to strings,
//! tokenise by line, and run `imara-diff`. The two-way path is
//! a thin wrapper around the engine; the three-way path
//! composes two two-way diffs against the base and merges them
//! by overlapping base ranges, producing `Conflict` hunks
//! where both sides independently touched the same base
//! lines.
//!
//! See `docs/dev/architecture/diff-system.md` §3 and §4.

use std::ops::Range;

use imara_diff::intern::InternedInput;
use imara_diff::{Algorithm, Sink};
use ropey::Rope;
use smallvec::smallvec;

use crate::types::{DiffAlgorithm, Hunk, HunkIndex, HunkKind, LineRange};

fn algorithm_to_imara(alg: DiffAlgorithm) -> Algorithm {
    match alg {
        DiffAlgorithm::Histogram => Algorithm::Histogram,
        DiffAlgorithm::Myers => Algorithm::Myers,
        DiffAlgorithm::MyersMinimal => Algorithm::MyersMinimal,
    }
}

/// `imara_diff::Sink` impl that collects each `process_change`
/// callback into a two-way `Hunk`.
struct TwoWaySink {
    hunks: Vec<Hunk>,
}

impl Sink for TwoWaySink {
    type Out = Vec<Hunk>;

    fn process_change(&mut self, before: Range<u32>, after: Range<u32>) {
        let a = LineRange::new(before.start, before.end);
        let b = LineRange::new(after.start, after.end);
        let kind = classify_two_way(a, b);
        self.hunks.push(Hunk {
            kind,
            ranges: smallvec![a, b],
            refine: Default::default(),
        });
    }

    fn finish(self) -> Self::Out {
        self.hunks
    }
}

fn classify_two_way(a: LineRange, b: LineRange) -> HunkKind {
    match (a.is_empty(), b.is_empty()) {
        // imara-diff does not emit an empty/empty hunk; fall
        // back to `Change` defensively rather than panic.
        (true, true) => HunkKind::Change,
        (true, false) => HunkKind::Add,
        (false, true) => HunkKind::Remove,
        (false, false) => HunkKind::Change,
    }
}

/// D.8.a: the engine's only public dispatch entry. Routes by
/// `sources.len()` to the appropriate algorithm, returning a
/// typed error for arities outside the supported range.
///
/// - **N=0**: `Err(DiffEngineError::Empty)` — there's nothing to
///   diff. Callers should never reach this; defensive.
/// - **N=1**: empty `HunkIndex` — a single participant has no
///   peers to compare against. The session is "dormant" in the
///   subsystem's terms (D.8.e); the first `:diffthis` lands
///   here, before a second `:diffthis` extends it to N=2.
/// - **N=2**: dispatches to [`two_way`].
/// - **N=3**: dispatches to [`three_way`].
/// - **N≥4**: `Err(DiffEngineError::Unsupported { n })`. v1 cap.
///   The reference table in §12 of
///   `docs/dev/architecture/n-way-diff-membership.md` surveys
///   how other editors handle this — Helix/Zed/VSCode also
///   don't support N≥4; Vim does via pairwise-vs-anchor. The
///   cap moves when user-feedback signals N>3 is wanted.
///
/// `compute_diff` is the **only** public entry — all external
/// callers go through it. The dispatch decision lives entirely
/// inside this function so consumers never branch on arity.
pub fn compute_diff(
    sources: &[Rope],
    algorithm: DiffAlgorithm,
) -> Result<HunkIndex, DiffEngineError> {
    match sources.len() {
        0 => Err(DiffEngineError::Empty),
        1 => Ok(HunkIndex {
            hunks: Vec::new(),
            algorithm,
            revision: 0,
        }),
        2 => Ok(two_way(&sources[0], &sources[1], algorithm)),
        3 => Ok(three_way(&sources[0], &sources[1], &sources[2], algorithm)),
        n => Err(DiffEngineError::Unsupported { n }),
    }
}

/// D.8.a: errors `compute_diff` returns for unsupported
/// participant counts. v1's cap (N ≤ 3) is enforced here, not in
/// the descriptor / subsystem layer — moving the cap means
/// extending the `Unsupported` arm with new computation.
#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
pub enum DiffEngineError {
    #[error("diff requires at least one participant")]
    Empty,
    #[error("v1 supports up to 3 participants; got N = {n}")]
    Unsupported { n: usize },
}

/// Compute the two-way hunk list between ropes `a` and `b`.
///
/// Crate-private since D.8.a — external consumers call
/// [`compute_diff`] which dispatches here for `sources.len() ==
/// 2`. Kept as a named function (rather than inlined) for the
/// internal tests in this module + the three-way pipeline's
/// `two_way_str` reuse.
///
/// Each hunk's `ranges` is `[a_range, b_range]`. The
/// classification (Add / Remove / Change) is relative to `a`
/// being the "earlier" side.
///
/// Allocates the full text of both ropes once each via
/// `Rope::to_string()` for the engine's interner. The cost is
/// O(N + M) bytes for ropes of sizes N and M; bench gated in
/// `benches/recompute.rs`.
pub(crate) fn two_way(a: &Rope, b: &Rope, algorithm: DiffAlgorithm) -> HunkIndex {
    let a_str = a.to_string();
    let b_str = b.to_string();
    let mut hunks = two_way_str(&a_str, &b_str, algorithm);
    // DR.4: refine here, where BOTH sides are in hand, rather than at
    // render time where only the baseline is. Computed once per diff
    // and carried on the hunk, so every consumer reads the same answer
    // and none of them re-derives it.
    fill_refinements(&mut hunks, &a_str, &b_str);
    HunkIndex {
        hunks,
        algorithm,
        revision: 0,
    }
}

/// DR.4: populate each `Change` hunk's `refine` from the two sides.
///
/// Only a `Change` has both sides — an `Add` has no removed
/// counterpart and a `Remove` no added one, so neither has anything to
/// compare against.
///
/// DR.5: the two sides go to `refine_regions` whole. There is no
/// length precondition any more — an *n*-removed / *m*-added hunk
/// refines like any other, which is the fix; `refine_regions` decides
/// on its own whether the result is signal (identical, wholesale, or
/// oversized regions come back empty).
fn fill_refinements(hunks: &mut [Hunk], a: &str, b: &str) {
    let a_lines: Vec<&str> = a.lines().collect();
    let b_lines: Vec<&str> = b.lines().collect();
    for hunk in hunks.iter_mut() {
        if hunk.kind != HunkKind::Change {
            continue;
        }
        let (Some(before), Some(after)) = (hunk.ranges.first(), hunk.ranges.get(1)) else {
            continue;
        };
        let slice = |src: &[&str], r: &LineRange| -> Vec<String> {
            (r.start as usize..r.end as usize)
                .filter_map(|i| src.get(i).map(|s| s.to_string()))
                .collect()
        };
        let removed = slice(&a_lines, before);
        let added = slice(&b_lines, after);
        let removed_refs: Vec<&str> = removed.iter().map(|s| s.as_str()).collect();
        let added_refs: Vec<&str> = added.iter().map(|s| s.as_str()).collect();
        hunk.refine = crate::refine::refine_regions(&removed_refs, &added_refs);
    }
}

/// Internal: two-way diff over `&str` inputs. Used by both
/// [`two_way`] and [`three_way`] (which materialises ropes once
/// and reuses the strings for the two base-vs-side diffs).
///
/// Tokenises with `imara_diff::sources::lines_with_terminator`
/// so trailing-newline differences are preserved (the default
/// `&str` tokenisation uses `str::lines()` which strips
/// terminators and treats `"x"` and `"x\n"` as identical).
fn two_way_str(a: &str, b: &str, algorithm: DiffAlgorithm) -> Vec<Hunk> {
    let input = InternedInput::new(
        imara_diff::sources::lines_with_terminator(a),
        imara_diff::sources::lines_with_terminator(b),
    );
    imara_diff::diff(
        algorithm_to_imara(algorithm),
        &input,
        TwoWaySink { hunks: Vec::new() },
    )
}

/// Compute a three-way hunk list between `base`, `local`, and
/// `remote`.
///
/// Crate-private since D.8.a — external consumers call
/// [`compute_diff`] which dispatches here for `sources.len() ==
/// 3`. Kept as a named function for internal tests + clarity.
///
/// Each hunk's `ranges` is `[base_range, local_range,
/// remote_range]`. A hunk is `Conflict` iff both `local` and
/// `remote` independently modified an overlapping base region.
/// Otherwise the hunk is classified relative to whichever side
/// changed (the other side's range covers the corresponding
/// untouched region in that side's coordinate system, computed
/// via running offset).
///
/// Adjacent (touching but not overlapping) hunks from
/// different sides are kept separate — they don't conflict.
/// Strict overlap (`a.start < b.end && b.start < a.end`) is
/// the conflict predicate.
pub(crate) fn three_way(
    base: &Rope,
    local: &Rope,
    remote: &Rope,
    algorithm: DiffAlgorithm,
) -> HunkIndex {
    let base_str = base.to_string();
    let local_str = local.to_string();
    let remote_str = remote.to_string();

    let local_hunks = two_way_str(&base_str, &local_str, algorithm);
    let remote_hunks = two_way_str(&base_str, &remote_str, algorithm);

    let merged = merge_three_way(&local_hunks, &remote_hunks, &local_str, &remote_str);

    HunkIndex {
        hunks: merged,
        algorithm,
        revision: 0,
    }
}

/// Precompute byte offsets of every line start in `s`.
///
/// `offsets[i]` is the byte index in `s` where line `i`
/// starts. `offsets[len_lines]` is `s.len()` (past-the-end
/// sentinel). Used by [`line_slice`] for O(1) line-range
/// indexing during three-way merge content comparison.
fn line_offsets(s: &str) -> Vec<usize> {
    let mut offsets = Vec::with_capacity(s.len() / 32 + 2);
    offsets.push(0);
    for (i, byte) in s.bytes().enumerate() {
        if byte == b'\n' {
            offsets.push(i + 1);
        }
    }
    if offsets.last().copied() != Some(s.len()) {
        offsets.push(s.len());
    }
    offsets
}

/// Slice `s` by line range, using precomputed offsets.
/// Returns an empty slice if the range is empty or out of
/// bounds.
fn line_slice<'a>(s: &'a str, offsets: &[usize], range: LineRange) -> &'a str {
    let start = offsets
        .get(range.start as usize)
        .copied()
        .unwrap_or(s.len());
    let end = offsets.get(range.end as usize).copied().unwrap_or(s.len());
    if start > end || start > s.len() {
        return "";
    }
    &s[start..end.min(s.len())]
}

/// Merge two sorted two-way hunk lists (each `[base, side]`)
/// into a unified three-way list `[base, local, remote]`.
///
/// Walks both lists in tandem in base-ascending order. Picks
/// the earliest unprocessed hunk as the seed of a new union
/// region, then takes every subsequent hunk from either side
/// that strictly overlaps the growing union. A union that
/// took hunks from both sides is classified `Conflict`; a
/// union touched by only one side is attributed to that
/// side's change kind.
fn merge_three_way(
    local_hunks: &[Hunk],
    remote_hunks: &[Hunk],
    local_str: &str,
    remote_str: &str,
) -> Vec<Hunk> {
    let local_offsets = line_offsets(local_str);
    let remote_offsets = line_offsets(remote_str);

    let mut merged = Vec::new();
    let mut li = 0;
    let mut ri = 0;

    // Running net deltas: how many lines local/remote has
    // gained (positive) or lost (negative) vs base by the time
    // we reach the current base position. Used to project an
    // untouched base range into the side's coordinate space.
    let mut local_delta: i64 = 0;
    let mut remote_delta: i64 = 0;

    while li < local_hunks.len() || ri < remote_hunks.len() {
        let l_pos = local_hunks.get(li).map(|h| h.ranges[0].start);
        let r_pos = remote_hunks.get(ri).map(|h| h.ranges[0].start);

        // Pick the earliest unprocessed hunk as the seed.
        let take_local_first = match (l_pos, r_pos) {
            (Some(l), Some(r)) => l <= r,
            (Some(_), None) => true,
            (None, Some(_)) => false,
            (None, None) => break,
        };

        let mut taken_local: Vec<usize> = Vec::new();
        let mut taken_remote: Vec<usize> = Vec::new();
        let mut union_base;

        if take_local_first {
            union_base = local_hunks[li].ranges[0];
            taken_local.push(li);
            li += 1;
        } else {
            union_base = remote_hunks[ri].ranges[0];
            taken_remote.push(ri);
            ri += 1;
        }

        // Extend the union while either side has a strictly-
        // overlapping next hunk.
        loop {
            let mut extended = false;
            if let Some(h) = local_hunks.get(li)
                && h.ranges[0].start < union_base.end
            {
                union_base = LineRange::new(union_base.start, union_base.end.max(h.ranges[0].end));
                taken_local.push(li);
                li += 1;
                extended = true;
            }
            if let Some(h) = remote_hunks.get(ri)
                && h.ranges[0].start < union_base.end
            {
                union_base = LineRange::new(union_base.start, union_base.end.max(h.ranges[0].end));
                taken_remote.push(ri);
                ri += 1;
                extended = true;
            }
            if !extended {
                break;
            }
        }

        let local_range = side_range(&taken_local, local_hunks, union_base, local_delta);
        let remote_range = side_range(&taken_remote, remote_hunks, union_base, remote_delta);

        // Advance running deltas past the taken hunks.
        for &idx in &taken_local {
            let h = &local_hunks[idx];
            local_delta += h.ranges[1].len() as i64 - h.ranges[0].len() as i64;
        }
        for &idx in &taken_remote {
            let h = &remote_hunks[idx];
            remote_delta += h.ranges[1].len() as i64 - h.ranges[0].len() as i64;
        }

        let kind = if !taken_local.is_empty() && !taken_remote.is_empty() {
            // Both sides touched this region. If the resulting
            // content is identical, this is a "soft" merge
            // where both sides made the same change — not a
            // conflict. Compare the actual line content rather
            // than just the ranges, since equivalent edits can
            // land at different line indices in their side's
            // coordinate space.
            let local_text = line_slice(local_str, &local_offsets, local_range);
            let remote_text = line_slice(remote_str, &remote_offsets, remote_range);
            if local_text == remote_text {
                classify_three_way_attributed(union_base, local_range)
            } else {
                HunkKind::Conflict
            }
        } else if !taken_local.is_empty() {
            classify_three_way_attributed(union_base, local_range)
        } else {
            classify_three_way_attributed(union_base, remote_range)
        };

        merged.push(Hunk {
            kind,
            ranges: smallvec![union_base, local_range, remote_range],
            refine: Default::default(),
        });
    }

    merged
}

/// Compute one side's (local *or* remote) range corresponding
/// to the union base range.
///
/// - If the side touched the union (one or more hunks taken),
///   the range spans from the first taken hunk's side-start
///   (extended by the base-prefix preceding it) to the last
///   taken hunk's side-end (extended by the base-suffix
///   following it).
/// - If the side did not touch the union, project the base
///   range into the side's coordinate space via the running
///   delta.
fn side_range(
    taken: &[usize],
    hunks: &[Hunk],
    union_base: LineRange,
    side_delta: i64,
) -> LineRange {
    if taken.is_empty() {
        let start = (union_base.start as i64 + side_delta).max(0) as u32;
        let end = (union_base.end as i64 + side_delta).max(0) as u32;
        LineRange::new(start, end)
    } else {
        let first = &hunks[taken[0]];
        let last = &hunks[*taken.last().expect("taken non-empty")];
        // How much base extends before the first taken hunk
        // (untouched prefix that we count as side-untouched).
        let prefix = first.ranges[0].start.saturating_sub(union_base.start);
        let suffix = union_base.end.saturating_sub(last.ranges[0].end);
        let start = first.ranges[1].start.saturating_sub(prefix);
        let end = last.ranges[1].end + suffix;
        LineRange::new(start, end)
    }
}

fn classify_three_way_attributed(base: LineRange, side: LineRange) -> HunkKind {
    match (base.is_empty(), side.is_empty()) {
        (true, false) => HunkKind::Add,
        (false, true) => HunkKind::Remove,
        (false, false) => HunkKind::Change,
        // An empty/empty union shouldn't occur after a
        // hunk-taking iteration; classify defensively.
        (true, true) => HunkKind::Change,
    }
}

#[cfg(test)]
mod refine_at_compute_time {
    use super::*;

    fn rope(s: &str) -> Rope {
        Rope::from_str(s)
    }

    /// DR.4: a Change hunk carries its own refinement, computed once at
    /// diff time. The render path only has the baseline rope, so if it
    /// were not computed here it could not be computed at all.
    #[test]
    fn a_change_hunk_carries_refinement() {
        let a = rope("fn main() {\n    let old = 1;\n}\n");
        let b = rope("fn main() {\n    let new = 1;\n}\n");
        let idx = two_way(&a, &b, DiffAlgorithm::Histogram);
        let change = idx
            .hunks
            .iter()
            .find(|h| h.kind == HunkKind::Change)
            .expect("one changed line");
        // The ranges address the SOURCE line, not the diff line — there
        // is no +/- marker here.
        let line = "    let old = 1;";
        let got: Vec<&str> = change
            .refine
            .removed_line(0)
            .iter()
            .map(|x| &line[x.clone()])
            .collect();
        assert_eq!(got, vec!["old"]);
    }

    /// An Add has no removed counterpart, so there is nothing to
    /// compare against and the hunk keeps an empty refinement.
    #[test]
    fn an_add_hunk_carries_no_refinement() {
        let a = rope("one\n");
        let b = rope("one\ntwo\n");
        let idx = two_way(&a, &b, DiffAlgorithm::Histogram);
        assert!(idx.hunks.iter().all(|h| h.refine.is_empty()));
    }

    /// DR.5: a 1-removed / 2-added change refines. Under DR.1's
    /// pairing rule this declined outright — unequal runs had no
    /// principled pairing — and that was the bug: the shape is what
    /// "rewrite a line and add one above it" produces every time.
    #[test]
    fn an_unequal_change_still_refines() {
        let a = rope("let value = compute(a);\n");
        let b = rope("// explain it\nlet value = derive(a);\n");
        let idx = two_way(&a, &b, DiffAlgorithm::Histogram);
        let change = idx
            .hunks
            .iter()
            .find(|h| h.kind == HunkKind::Change)
            .expect("a change hunk");
        let line = "let value = compute(a);";
        let got: Vec<&str> = change
            .refine
            .removed_line(0)
            .iter()
            .map(|x| &line[x.clone()])
            .collect();
        assert_eq!(
            got,
            vec!["compute"],
            "the removed side marks the replaced identifier"
        );
    }

    /// Each side is indexed by its OWN range, so consumers can index
    /// removed by `line - ranges[0].start` and added by
    /// `line - ranges[1].start` — which is what the overlay and the
    /// magit path do.
    #[test]
    fn each_side_is_aligned_with_its_own_range() {
        let a = rope("a1\na2\n");
        let b = rope("b1\nb2\n");
        let idx = two_way(&a, &b, DiffAlgorithm::Histogram);
        for h in idx.hunks.iter().filter(|h| h.kind == HunkKind::Change) {
            if h.refine.is_empty() {
                continue;
            }
            assert_eq!(
                h.refine.removed.len(),
                (h.ranges[0].end - h.ranges[0].start) as usize,
                "one entry per baseline line in the hunk"
            );
            assert_eq!(
                h.refine.added.len(),
                (h.ranges[1].end - h.ranges[1].start) as usize,
                "one entry per added line in the hunk"
            );
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty_inputs_have_no_hunks() {
        let a = Rope::new();
        let b = Rope::new();
        let idx = two_way(&a, &b, DiffAlgorithm::Histogram);
        assert!(idx.is_empty());
    }

    #[test]
    fn identical_inputs_have_no_hunks() {
        let a = Rope::from("alpha\nbeta\ngamma\n");
        let b = Rope::from("alpha\nbeta\ngamma\n");
        let idx = two_way(&a, &b, DiffAlgorithm::Histogram);
        assert!(idx.is_empty());
    }

    #[test]
    fn pure_add_classifies_as_add() {
        let a = Rope::from("alpha\ngamma\n");
        let b = Rope::from("alpha\nbeta\ngamma\n");
        let idx = two_way(&a, &b, DiffAlgorithm::Histogram);
        assert_eq!(idx.len(), 1);
        assert_eq!(idx.hunks[0].kind, HunkKind::Add);
    }

    #[test]
    fn pure_remove_classifies_as_remove() {
        let a = Rope::from("alpha\nbeta\ngamma\n");
        let b = Rope::from("alpha\ngamma\n");
        let idx = two_way(&a, &b, DiffAlgorithm::Histogram);
        assert_eq!(idx.len(), 1);
        assert_eq!(idx.hunks[0].kind, HunkKind::Remove);
    }

    #[test]
    fn change_classifies_as_change() {
        let a = Rope::from("alpha\nbeta\ngamma\n");
        let b = Rope::from("alpha\nBETA\ngamma\n");
        let idx = two_way(&a, &b, DiffAlgorithm::Histogram);
        assert_eq!(idx.len(), 1);
        assert_eq!(idx.hunks[0].kind, HunkKind::Change);
    }

    #[test]
    fn three_way_non_overlapping_changes_no_conflict() {
        let base = Rope::from("a\nb\nc\nd\ne\nf\n");
        let local = Rope::from("a\nB\nc\nd\ne\nf\n"); // changed line 1
        let remote = Rope::from("a\nb\nc\nd\nE\nf\n"); // changed line 4
        let idx = three_way(&base, &local, &remote, DiffAlgorithm::Histogram);
        // Two separate non-conflict hunks (one per side).
        assert_eq!(idx.len(), 2);
        assert!(idx.hunks.iter().all(|h| h.kind != HunkKind::Conflict));
    }

    #[test]
    fn three_way_overlapping_changes_yield_conflict() {
        let base = Rope::from("a\nb\nc\n");
        let local = Rope::from("a\nLOCAL\nc\n"); // changed line 1
        let remote = Rope::from("a\nREMOTE\nc\n"); // changed line 1 differently
        let idx = three_way(&base, &local, &remote, DiffAlgorithm::Histogram);
        assert_eq!(idx.len(), 1);
        assert_eq!(idx.hunks[0].kind, HunkKind::Conflict);
    }

    #[test]
    fn three_way_no_changes_no_hunks() {
        let base = Rope::from("a\nb\nc\n");
        let local = base.clone();
        let remote = base.clone();
        let idx = three_way(&base, &local, &remote, DiffAlgorithm::Histogram);
        assert!(idx.is_empty());
    }

    #[test]
    fn all_algorithms_agree_on_simple_change() {
        let a = Rope::from("alpha\nbeta\ngamma\n");
        let b = Rope::from("alpha\nBETA\ngamma\n");
        for alg in [
            DiffAlgorithm::Histogram,
            DiffAlgorithm::Myers,
            DiffAlgorithm::MyersMinimal,
        ] {
            let idx = two_way(&a, &b, alg);
            assert_eq!(idx.len(), 1, "algorithm {alg:?}");
            assert_eq!(idx.hunks[0].kind, HunkKind::Change, "algorithm {alg:?}");
            assert_eq!(idx.algorithm, alg);
        }
    }

    // ──────────────────────────────────────────────────────
    // D.8.a (2026-05-31): compute_diff dispatch matrix
    // ──────────────────────────────────────────────────────

    #[test]
    fn compute_diff_zero_participants_is_empty_error() {
        let result = compute_diff(&[], DiffAlgorithm::Histogram);
        assert!(matches!(result, Err(DiffEngineError::Empty)));
    }

    #[test]
    fn compute_diff_one_participant_returns_empty_hunk_index() {
        // N=1 = dormant session. Vim parity: `:set diff` on a
        // single buffer with no peers is a visual no-op.
        let rope = Rope::from("alpha\nbeta\n");
        let idx =
            compute_diff(&[rope], DiffAlgorithm::Histogram).expect("N=1 must succeed (dormant)");
        assert!(idx.is_empty());
        assert_eq!(idx.algorithm, DiffAlgorithm::Histogram);
    }

    #[test]
    fn compute_diff_two_participants_dispatches_to_two_way() {
        let a = Rope::from("alpha\nbeta\ngamma\n");
        let b = Rope::from("alpha\nBETA\ngamma\n");
        let via_dispatch = compute_diff(&[a.clone(), b.clone()], DiffAlgorithm::Histogram)
            .expect("N=2 is supported");
        let direct = two_way(&a, &b, DiffAlgorithm::Histogram);
        // Same hunks shape (the dispatch is a thin wrapper).
        assert_eq!(via_dispatch.len(), direct.len());
        assert_eq!(via_dispatch.hunks.len(), 1);
        assert_eq!(via_dispatch.hunks[0].kind, HunkKind::Change);
    }

    #[test]
    fn compute_diff_three_participants_dispatches_to_three_way() {
        let base = Rope::from("aaa\nbbb\nccc\n");
        let local = Rope::from("aaa\nBBB\nccc\n");
        let remote = Rope::from("aaa\nbbb\nCCC\n");
        let via_dispatch = compute_diff(
            &[base.clone(), local.clone(), remote.clone()],
            DiffAlgorithm::Histogram,
        )
        .expect("N=3 is supported");
        let direct = three_way(&base, &local, &remote, DiffAlgorithm::Histogram);
        assert_eq!(via_dispatch.len(), direct.len());
        // Disjoint edits → no Conflict.
        assert!(
            via_dispatch
                .hunks
                .iter()
                .all(|h| !matches!(h.kind, HunkKind::Conflict))
        );
        // Every hunk carries 3 ranges per the three-way contract.
        for h in &via_dispatch.hunks {
            assert_eq!(h.ranges.len(), 3);
        }
    }

    #[test]
    fn compute_diff_four_participants_errors_unsupported() {
        let r = Rope::from("x\n");
        let result = compute_diff(
            &[r.clone(), r.clone(), r.clone(), r],
            DiffAlgorithm::Histogram,
        );
        assert!(matches!(result, Err(DiffEngineError::Unsupported { n: 4 })));
    }

    #[test]
    fn compute_diff_arbitrarily_large_n_errors_unsupported() {
        let sources: Vec<Rope> = (0..10).map(|i| Rope::from(format!("rope-{i}\n"))).collect();
        let result = compute_diff(&sources, DiffAlgorithm::Histogram);
        assert!(matches!(
            result,
            Err(DiffEngineError::Unsupported { n: 10 })
        ));
    }

    #[test]
    fn diff_engine_error_messages_name_the_cap() {
        // Surfaces in dispatch.rs error messages; verify they
        // stay user-readable.
        let empty = DiffEngineError::Empty;
        let unsup = DiffEngineError::Unsupported { n: 5 };
        assert_eq!(format!("{empty}"), "diff requires at least one participant");
        assert_eq!(
            format!("{unsup}"),
            "v1 supports up to 3 participants; got N = 5"
        );
    }

    #[test]
    fn compute_diff_three_way_overlap_produces_conflict() {
        // Belt-and-braces: confirm the three-way Conflict path
        // fires through the dispatch wrapper.
        let base = Rope::from("aaa\nbbb\nccc\n");
        let local = Rope::from("aaa\nLOCAL\nccc\n");
        let remote = Rope::from("aaa\nREMOTE\nccc\n");
        let idx =
            compute_diff(&[base, local, remote], DiffAlgorithm::Histogram).expect("N=3 supported");
        assert!(
            idx.hunks
                .iter()
                .any(|h| matches!(h.kind, HunkKind::Conflict))
        );
    }
}