sley_diff_merge/

render.rs

//! Unified-diff / patch RENDERER: turn a computed file diff (the old/new
//! blob contents) into the textual unified-diff hunk body git's `diff.c`
//! emit path produces (`emit_diff_symbol` / `fn_out_consume`).
//!
//! This is the byte-for-byte port of git's hunk emitter: `@@ -os,oc +ns,nc @@
//! <heading>` hunk headers, the `+`/`-`/context lines, and the
//! `\ No newline at end of file` marker. It owns hunk *grouping* (combining
//! changes whose context windows overlap, `xdl_get_hunk`'s `distance >
//! max_common` break) and hunk *range* computation, then emits each hunk.
//!
//! What this module deliberately does NOT own (those stay with the caller,
//! which has the repository/userdiff/config context):
//!
//! * **The per-file metainfo header** (`diff --git`, `index`, `---`/`+++`,
//!   mode/similarity lines). That is repository- and option-shaped; the
//!   renderer only produces the hunk body that follows it.
//! * **Funcname section-heading resolution.** The caller supplies a
//!   [`HeadingFn`] closure that, given a candidate line, returns its section
//!   heading (git's `def_ff` default heuristic or a userdiff `xfuncname`
//!   pattern). The renderer does the *scan upward* for the nearest heading
//!   line; the caller only classifies a single line.
//! * **Word-diff body rendering.** When [`HunkRenderOptions::word_diff`] is
//!   set, the renderer delegates each hunk's body to a [`HunkWordDiff`] hook,
//!   which the caller implements over its own word-diff machinery.
//!
//! The seams keep the byte-shaping (ranges, headers, prefixes, no-newline
//! markers, color spans) here — the part every diff-emitting command used to
//! re-derive — while leaving the repository-coupled concerns in the consumer.

use crate::line_diff::{
    DiffAlgorithm, DiffLine, DiffOp, WsIgnore, line_is_blank, myers_diff_lines_ws,
    patience_diff_lines_anchored, split_lines,
};
use std::collections::HashMap;

/// git's default hunk context (`-U3`).
pub const DEFAULT_CONTEXT: usize = 3;
const FUNCTION_CONTEXT_FLAG: usize = 1usize << (usize::BITS - 1);
const CONTEXT_VALUE_MASK: usize = !FUNCTION_CONTEXT_FLAG;

/// Encode `-W` / `--function-context` into the context field without changing
/// the option shape used by the existing renderer call sites.
pub fn enable_function_context(context: usize) -> usize {
    (context & CONTEXT_VALUE_MASK) | FUNCTION_CONTEXT_FLAG
}

fn decode_context(context: usize) -> (usize, bool) {
    (
        context & CONTEXT_VALUE_MASK,
        context & FUNCTION_CONTEXT_FLAG != 0,
    )
}

fn replace_context_value(encoded: usize, context: usize) -> usize {
    (encoded & !CONTEXT_VALUE_MASK) | (context & CONTEXT_VALUE_MASK)
}

/// The per-line origin marker for an emitted diff line.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum LineKind {
    /// An unchanged (` `) line, present on both sides.
    Context,
    /// A removed (`-`) line, present only on the old side.
    Delete,
    /// An added (`+`) line, present only on the new side.
    Insert,
}

/// One line of the unified diff, with its origin and 0-based positions in the
/// old/new files (used to compute hunk ranges and feed the word-diff hook).
#[derive(Clone, Copy)]
pub struct TaggedLine<'a> {
    /// Whether the line is context / a deletion / an insertion.
    pub kind: LineKind,
    /// The raw line bytes, including the trailing `\n` when present.
    pub content: &'a [u8],
    /// 0-based index of this line on the old side.
    pub old_index: usize,
    /// 0-based index of this line on the new side.
    pub new_index: usize,
}

/// ANSI color palette for a unified diff, mirroring git's `diff_get_color`
/// slots. Each field is the raw escape sequence (empty string = no color).
///
/// The renderer only consults the slots it paints in the hunk body; the
/// per-file metainfo slot (`meta`) lives with the caller's header emitter and
/// is intentionally absent here.
#[derive(Clone, Copy)]
pub struct RenderColors<'a> {
    /// `color.diff.frag` — the `@@ .. @@` span.
    pub frag: &'a str,
    /// `color.diff.func` — the section heading after the frag.
    pub func: &'a str,
    /// `color.diff.old` — removed (`-`) lines.
    pub old: &'a str,
    /// `color.diff.new` — added (`+`) lines.
    pub new: &'a str,
    /// `color.diff.context` — context (` `) lines and the no-newline marker.
    pub context: &'a str,
    /// The reset sequence terminating each colored span.
    pub reset: &'a str,
    /// `color.diff.whitespace` — the highlight for whitespace errors
    /// (`--ws-error-highlight`).
    pub whitespace: &'a str,
    /// `color.diff.oldMoved` — removed lines detected as moved.
    pub old_moved: &'a str,
    /// `color.diff.oldMovedAlternative` — alternate removed moved block.
    pub old_moved_alt: &'a str,
    /// `color.diff.oldMovedDimmed` — uninteresting removed moved line.
    pub old_moved_dim: &'a str,
    /// `color.diff.oldMovedAlternativeDimmed` — alternate dimmed removed line.
    pub old_moved_alt_dim: &'a str,
    /// `color.diff.newMoved` — added lines detected as moved.
    pub new_moved: &'a str,
    /// `color.diff.newMovedAlternative` — alternate added moved block.
    pub new_moved_alt: &'a str,
    /// `color.diff.newMovedDimmed` — uninteresting added moved line.
    pub new_moved_dim: &'a str,
    /// `color.diff.newMovedAlternativeDimmed` — alternate dimmed added line.
    pub new_moved_alt_dim: &'a str,
}

/// `--color-moved=<mode>` hunk-body mode.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ColorMovedMode {
    /// Mark every matching `+`/`-` line.
    Plain,
    /// Mark moved blocks, without alternating colors.
    Blocks,
    /// Mark moved blocks, alternating adjacent blocks.
    Zebra,
    /// Like zebra, but dim interior lines.
    DimmedZebra,
}

/// `--color-moved-ws=<mode>` comparison mode.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct ColorMovedWs {
    /// Whitespace-ignore flags used when interning moved lines.
    pub ignore: WsIgnore,
    /// Allow a constant indentation delta across a moved block.
    pub allow_indentation_change: bool,
}

/// Moved-code coloring configuration.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct ColorMoved {
    /// Which moved-code coloring style to use.
    pub mode: ColorMovedMode,
    /// Whitespace handling for moved-code matching.
    pub ws: ColorMovedWs,
}

/// Resolve the section heading for one candidate line.
///
/// Returns `Some(heading)` when `line` is a heading line (git's `def_ff`
/// default heuristic or a userdiff `xfuncname` match) and `None` otherwise.
/// The renderer scans upward from each hunk's first line and uses the first
/// `Some` it finds — the caller only has to classify a single line, so it can
/// keep its userdiff-driver / config resolution out of this crate.
pub type HeadingFn<'a> = dyn FnMut(&[u8]) -> Option<Vec<u8>> + 'a;

/// A hook that renders a single hunk's body when `--word-diff` is active.
///
/// The renderer feeds the hunk's tagged lines through this in order
/// (`fn_out_consume`'s `diff_words` branch): each removed line is pushed to
/// the minus buffer, each added line to the plus buffer, and a context line
/// flushes the accumulated word diff before emitting the context line itself.
/// The implementor owns the actual word-level rendering and color spans; this
/// keeps the word-diff machinery in the consumer.
pub trait HunkWordDiff {
    /// Buffer one removed line's content for the next word-diff flush.
    fn push_minus(&mut self, content: &[u8]);
    /// Buffer one added line's content for the next word-diff flush.
    fn push_plus(&mut self, content: &[u8]);
    /// Word-diff the accumulated minus/plus buffers into `out` and reset them.
    fn flush(&mut self, out: &mut Vec<u8>);
    /// Emit one context line (the `--word-diff` context style).
    fn emit_context_line(&mut self, out: &mut Vec<u8>, content: &[u8]);
}

/// Hunk-shaping and styling options for [`render_hunks`].
///
/// Lifetimes are split so the funcname / word-diff hooks can be borrowed
/// mutably while `colors` is borrowed shared.
pub struct HunkRenderOptions<'a, 'h> {
    /// Lines of context around each change (`-U<n>`, default
    /// [`DEFAULT_CONTEXT`]).
    pub context: usize,
    /// Extra inter-hunk merging distance (`--inter-hunk-context`).
    pub interhunk: usize,
    /// Per-line section-heading classifier; `None` emits headerless hunks.
    pub heading: Option<&'a mut HeadingFn<'h>>,
    /// ANSI palette when color output is enabled.
    pub colors: Option<RenderColors<'a>>,
    /// Word-diff body hook (replaces the `+`/`-` line bodies of each hunk).
    pub word_diff: Option<&'a mut dyn HunkWordDiff>,
    /// Hunk body line indicators (` `, `-`, `+` by default).
    pub line_indicators: LineIndicators,
    /// `--ws-error-highlight` configuration: when set and colors are on, the
    /// renderer paints whitespace errors on the selected line kinds with
    /// `colors.whitespace` (git's `emit_line_ws_markup`). `None` disables it.
    pub ws_error: Option<WsErrorHighlight>,
    /// Whitespace-ignore flags (`-w`, `-b`, `--ignore-space-at-eol`,
    /// `--ignore-cr-at-eol`): applied to the line-level comparison so
    /// whitespace-only changes do not appear as diffs (git's
    /// `XDF_WHITESPACE_FLAGS`).
    pub ws_ignore: WsIgnore,
    /// The line-diff algorithm to use (Myers / patience / histogram).
    pub algorithm: DiffAlgorithm,
    /// Indent heuristic (`--indent-heuristic` / `diff.indentHeuristic`): when
    /// set, change groups that can slide within surrounding identical lines are
    /// shifted to the most readable boundary (git's `XDF_INDENT_HEURISTIC`
    /// scoring in `xdl_change_compact`). The base change compaction — sliding
    /// groups as far down as possible and aligning add/delete pairs — always
    /// runs; this flag only enables the indent-based slider scoring. Defaults to
    /// `true` to match git's `diff.indentHeuristic` default.
    pub indent_heuristic: bool,
    /// Change-group suppression (`--ignore-blank-lines`, `-I<regex>`): when
    /// set, change groups all of whose old and new lines are blank (and/or
    /// match a `-I` regex) are dropped from hunk emission, mirroring git's
    /// `xdl_mark_ignorable_lines` / `xdl_mark_ignorable_regex` + `xdl_get_hunk`.
    pub change_ignore: Option<&'a ChangeIgnore<'a>>,
    /// `log -L`: restrict the emitted hunks to the new-side (post-image) line
    /// ranges. Each range is 0-based, `[start, end)`. When set, the renderer
    /// inflates context to the widest range span (so every change inside a
    /// range merges into one xdiff hunk), then clips the emitted lines back to
    /// the range boundaries — a port of diff.c's `line_range_*` callbacks.
    /// Ranges must be sorted and disjoint. `None` disables the filter (every
    /// non-line-log caller).
    pub line_ranges: Option<&'a [LineRange]>,
    /// `--color-moved`: classify moved `+`/`-` lines and paint them with the
    /// moved-color slots. `None` disables moved-code coloring.
    pub color_moved: Option<ColorMoved>,
    /// `--anchored=<text>` prefixes (git's patience anchors). Only consulted when
    /// `algorithm` is [`DiffAlgorithm::Patience`]; empty (the default) is plain
    /// patience. Forces the matching unique lines to stay aligned.
    pub anchors: &'a [Vec<u8>],
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct LineIndicators {
    pub context: u8,
    pub old: u8,
    pub new: u8,
}

impl Default for LineIndicators {
    fn default() -> Self {
        Self {
            context: b' ',
            old: b'-',
            new: b'+',
        }
    }
}

/// A half-open `[start, end)` line range (0-based) for `log -L` hunk
/// restriction. Mirrors diff.c's `struct range`.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct LineRange {
    /// 0-based inclusive start line (post-image).
    pub start: i64,
    /// 0-based exclusive end line (post-image).
    pub end: i64,
}

/// Configuration for change-group suppression (`--ignore-blank-lines` and
/// `-I<regex>`). A change group is *ignorable* iff every old line and every new
/// line it touches is blank (when `ignore_blank_lines`) or matches one of the
/// `-I` regexes (`regex_match`). Ignorable groups are kept out of hunk emission
/// per `xdl_get_hunk`'s leading/isolated-ignorable removal.
pub type ChangeIgnoreRegex<'a> = &'a dyn Fn(&[u8]) -> bool;

pub struct ChangeIgnore<'a> {
    /// `--ignore-blank-lines`: blank change groups are ignorable.
    pub ignore_blank_lines: bool,
    /// `-I<regex>`: a line is regex-ignorable when this returns `true`. The
    /// closure receives the raw line bytes (including the trailing `\n`). When
    /// `None`, no regex suppression applies.
    pub regex_match: Option<ChangeIgnoreRegex<'a>>,
}

/// Which line kinds get whitespace-error highlighting, plus the rule to check
/// against. git's `--ws-error-highlight` defaults to highlighting only new
/// (`+`) lines.
#[derive(Clone, Copy)]
pub struct WsErrorHighlight {
    /// The resolved whitespace rule to check each line against.
    pub rule: crate::ws::WsRule,
    /// Highlight errors on removed (`-`) lines.
    pub old: bool,
    /// Highlight errors on added (`+`) lines.
    pub new: bool,
    /// Highlight errors on context (` `) lines.
    pub context: bool,
}

impl Default for HunkRenderOptions<'_, '_> {
    fn default() -> Self {
        Self {
            context: DEFAULT_CONTEXT,
            interhunk: 0,
            heading: None,
            colors: None,
            word_diff: None,
            line_indicators: LineIndicators::default(),
            ws_error: None,
            ws_ignore: WsIgnore::default(),
            algorithm: DiffAlgorithm::Myers,
            indent_heuristic: true,
            change_ignore: None,
            line_ranges: None,
            color_moved: None,
            anchors: &[],
        }
    }
}

/// Render the unified-diff hunk body for a single file change into `out`.
///
/// `old_content` / `new_content` are the full blob contents (`None` for an
/// absent side — a created or deleted file). The function computes the
/// line-level Myers diff, groups changes into hunks with `options.context`
/// lines of surrounding context (merging nearby groups per
/// `options.interhunk`), and emits each hunk: the `@@` header (with git's
/// section heading), then the context / `-` / `+` lines including
/// `\ No newline at end of file` markers.
///
/// Nothing is written when the contents are identical (no changed lines).
/// This is the body *after* the per-file metainfo header the caller emits.
pub fn render_hunks(
    out: &mut Vec<u8>,
    old_content: Option<&[u8]>,
    new_content: Option<&[u8]>,
    options: &mut HunkRenderOptions<'_, '_>,
) {
    let (context, function_context) = decode_context(options.context);
    // `log -L` hunk restriction: render with inflated context into a scratch
    // buffer, then clip the emitted lines to the tracked ranges (diff.c's
    // `line_range_*` callbacks). The widest range span is the upper bound on
    // the context needed for every change in a range to land in one hunk.
    if let Some(ranges) = options.line_ranges {
        let max_span = ranges
            .iter()
            .map(|r| r.end - r.start)
            .max()
            .unwrap_or(0)
            .max(0) as usize;
        let saved_context = options.context;
        let line_indicators = options.line_indicators;
        let word_diff = options.word_diff.is_some();
        options.context = replace_context_value(saved_context, context.max(max_span));
        options.line_ranges = None;
        let mut full = Vec::new();
        render_hunks(&mut full, old_content, new_content, options);
        options.context = saved_context;
        options.line_ranges = Some(ranges);
        filter_hunks_to_ranges(out, &full, ranges, line_indicators, word_diff);
        return;
    }
    let old = split_lines(old_content.unwrap_or_default());
    let new = split_lines(new_content.unwrap_or_default());
    // `--anchored` only applies to the patience algorithm and on the raw
    // (no whitespace-ignore) comparison — git forces patience and matches anchor
    // text against the line bytes. Everything else takes the normal path.
    let mut ops = if options.algorithm == DiffAlgorithm::Patience
        && !options.anchors.is_empty()
        && options.ws_ignore.is_empty()
    {
        patience_diff_lines_anchored(&old, &new, options.anchors)
    } else {
        myers_diff_lines_ws(&old, &new, options.ws_ignore, options.algorithm)
    };

    // git's `xdl_change_compact`: slide each change group as far down as
    // possible, snap add/delete pairs back into alignment, and (under the
    // indent heuristic) shift to the most readable split. Runs on the raw edit
    // script before it is flattened into tagged lines.
    change_compact(
        &mut ops,
        &old,
        &new,
        options.ws_ignore,
        options.indent_heuristic,
    );

    // Flatten the edit script into a tagged line stream carrying old/new
    // positions.
    let mut tagged: Vec<TaggedLine<'_>> = Vec::new();
    let mut old_idx = 0usize;
    let mut new_idx = 0usize;
    for op in ops {
        match op {
            DiffOp::Equal(n) => {
                for _ in 0..n {
                    // When records match only under whitespace-ignore flags,
                    // git emits the postimage bytes as context.
                    tagged.push(TaggedLine {
                        kind: LineKind::Context,
                        content: new[new_idx].content,
                        old_index: old_idx,
                        new_index: new_idx,
                    });
                    old_idx += 1;
                    new_idx += 1;
                }
            }
            DiffOp::Delete(n) => {
                for _ in 0..n {
                    tagged.push(TaggedLine {
                        kind: LineKind::Delete,
                        content: old[old_idx].content,
                        old_index: old_idx,
                        new_index: new_idx,
                    });
                    old_idx += 1;
                }
            }
            DiffOp::Insert(n) => {
                for _ in 0..n {
                    tagged.push(TaggedLine {
                        kind: LineKind::Insert,
                        content: new[new_idx].content,
                        old_index: old_idx,
                        new_index: new_idx,
                    });
                    new_idx += 1;
                }
            }
        }
    }

    // Build the change list (git's xdchange script): each maximal run of
    // consecutive `-`/`+` tagged lines is one change, carrying its old/new line
    // ranges and the tagged-stream span it occupies.
    let changes = build_changes(&tagged);
    if changes.is_empty() {
        return;
    }

    // Mark each change ignorable when `--ignore-blank-lines` / `-I<regex>`
    // applies and every old and new line it touches is blank / regex-matched
    // (git's xdl_mark_ignorable_lines + xdl_mark_ignorable_regex).
    let mut changes = changes;
    if let Some(ci) = options.change_ignore {
        mark_ignorable_changes(&mut changes, &old, &new, options.ws_ignore, ci);
    }

    // Group changes into hunks (xdl_get_hunk): the `distance > max_common`
    // break plus leading/isolated-ignorable-change removal. Each hunk is a
    // tagged-stream `(first_change_pos, last_change_pos)` span of *real*
    // (emitted) changes.
    let mut groups = group_changes_into_hunks(&changes, context, options.interhunk);
    if function_context {
        groups = expand_hunks_to_function_context(
            &groups,
            &tagged,
            &old,
            &new,
            options.heading.as_deref_mut(),
        );
    }

    let moved_styles = options
        .color_moved
        .filter(|_| options.colors.is_some() && options.word_diff.is_none())
        .map(|color_moved| mark_color_as_moved(&tagged, color_moved));

    for (first_change, last_change) in groups {
        let (hunk_start, hunk_end) = if function_context {
            (first_change, (last_change + 1).min(tagged.len()))
        } else {
            (
                first_change.saturating_sub(context),
                (last_change + context + 1).min(tagged.len()),
            )
        };
        render_one_hunk(
            out,
            &tagged,
            moved_styles.as_deref(),
            &old,
            hunk_start,
            hunk_end,
            options,
        );
    }
}

// ===========================================================================
// Change compaction: a faithful port of git's `xdl_change_compact`
// (xdiff/xdiffi.c), including the `XDF_INDENT_HEURISTIC` slider scoring.
//
// git represents a diff as two per-file boolean "changed" arrays (`xdf1.rchg`
// for the old file, `xdf2.rchg` for the new). A *group* is a maximal run of
// changed lines (a deletion run in the old file, an insertion run in the new
// file), separated by runs of unchanged lines. `xdl_change_compact` walks the
// groups of one file while keeping a synchronized cursor over the groups of the
// other, sliding each group up/down within identical surrounding lines to a
// canonical (and, under the indent heuristic, more readable) position.
//
// We reconstruct the two `changed[]` arrays from the [`DiffOp`] script, run the
// algorithm on each file (old then new, exactly as git does), and rebuild the
// script. Line equality for sliding (`recs_match`) uses the same
// whitespace-canonicalized bytes the line-level diff used, so a group only
// slides across lines the diff itself considered identical.
// ===========================================================================

/// If a line is indented more than this, [`get_indent`] returns this value
/// (git's `MAX_INDENT`).
const MAX_INDENT: i32 = 200;
/// Cap on consecutive blank lines counted around a split (git's `MAX_BLANKS`).
const MAX_BLANKS: i32 = 20;

// Empirically-determined weight factors from git's xdiffi.c.
const START_OF_FILE_PENALTY: i32 = 1;
const END_OF_FILE_PENALTY: i32 = 21;
const TOTAL_BLANK_WEIGHT: i32 = -30;
const POST_BLANK_WEIGHT: i32 = 6;
const RELATIVE_INDENT_PENALTY: i32 = -4;
const RELATIVE_INDENT_WITH_BLANK_PENALTY: i32 = 10;
const RELATIVE_OUTDENT_PENALTY: i32 = 24;
const RELATIVE_OUTDENT_WITH_BLANK_PENALTY: i32 = 17;
const RELATIVE_DEDENT_PENALTY: i32 = 23;
const RELATIVE_DEDENT_WITH_BLANK_PENALTY: i32 = 17;
const INDENT_WEIGHT: i32 = 60;
const INDENT_HEURISTIC_MAX_SLIDING: i64 = 100;

/// One file's record set for compaction: the whitespace-canonicalized line
/// bytes (for `recs_match` and `get_indent`) and the per-line `changed` flags.
/// `nrec` is the number of records; index `-1` and `nrec` are treated as
/// "unchanged" sentinels, matching git's zero-padded `rchg`.
struct CompactFile {
    recs: Vec<Vec<u8>>,
    changed: Vec<bool>,
}

impl CompactFile {
    fn nrec(&self) -> i64 {
        self.recs.len() as i64
    }

    /// `xdf->changed[i]` with git's out-of-range sentinels: positions `-1` and
    /// `nrec` are unchanged (`false`).
    fn changed(&self, i: i64) -> bool {
        if i < 0 || i >= self.nrec() {
            false
        } else {
            self.changed[i as usize]
        }
    }

    fn set_changed(&mut self, i: i64, v: bool) {
        self.changed[i as usize] = v;
    }
}

/// git's `get_indent`: indentation columns of `rec` treating TAB as advancing
/// to the next multiple of 8; `-1` for a blank (whitespace-only / empty) line;
/// clamped at [`MAX_INDENT`].
fn get_indent(rec: &[u8]) -> i32 {
    let mut ret: i32 = 0;
    for &c in rec {
        if !xdl_isspace(c) {
            return ret;
        } else if c == b' ' {
            ret += 1;
        } else if c == b'\t' {
            ret += 8 - ret % 8;
        }
        // other whitespace (e.g. CR) is ignored, matching git.
        if ret >= MAX_INDENT {
            return MAX_INDENT;
        }
    }
    // The line contains only whitespace.
    -1
}

/// git's `XDL_ISSPACE`: space, tab, newline, vertical tab, form feed, carriage
/// return.
fn xdl_isspace(c: u8) -> bool {
    matches!(c, b' ' | b'\t' | b'\n' | 0x0b | 0x0c | b'\r')
}

/// git's `struct split_measurement`.
#[derive(Default)]
struct SplitMeasurement {
    end_of_file: bool,
    indent: i32,
    pre_blank: i32,
    pre_indent: i32,
    post_blank: i32,
    post_indent: i32,
}

/// git's `struct split_score`.
#[derive(Default, Clone, Copy)]
struct SplitScore {
    effective_indent: i32,
    penalty: i32,
}

/// git's `measure_split`: characteristics of a hypothetical split above line
/// `split` in `xdf`.
fn measure_split(xdf: &CompactFile, split: i64) -> SplitMeasurement {
    let mut m = SplitMeasurement::default();
    if split >= xdf.nrec() {
        m.end_of_file = true;
        m.indent = -1;
    } else {
        m.end_of_file = false;
        m.indent = get_indent(&xdf.recs[split as usize]);
    }

    m.pre_blank = 0;
    m.pre_indent = -1;
    let mut i = split - 1;
    while i >= 0 {
        m.pre_indent = get_indent(&xdf.recs[i as usize]);
        if m.pre_indent != -1 {
            break;
        }
        m.pre_blank += 1;
        if m.pre_blank == MAX_BLANKS {
            m.pre_indent = 0;
            break;
        }
        i -= 1;
    }

    m.post_blank = 0;
    m.post_indent = -1;
    let mut i = split + 1;
    while i < xdf.nrec() {
        m.post_indent = get_indent(&xdf.recs[i as usize]);
        if m.post_indent != -1 {
            break;
        }
        m.post_blank += 1;
        if m.post_blank == MAX_BLANKS {
            m.post_indent = 0;
            break;
        }
        i += 1;
    }

    m
}

/// git's `score_add_split`: accumulate the badness of split `m` into `s`.
fn score_add_split(m: &SplitMeasurement, s: &mut SplitScore) {
    if m.pre_indent == -1 && m.pre_blank == 0 {
        s.penalty += START_OF_FILE_PENALTY;
    }
    if m.end_of_file {
        s.penalty += END_OF_FILE_PENALTY;
    }

    let post_blank = if m.indent == -1 { 1 + m.post_blank } else { 0 };
    let total_blank = m.pre_blank + post_blank;

    s.penalty += TOTAL_BLANK_WEIGHT * total_blank;
    s.penalty += POST_BLANK_WEIGHT * post_blank;

    let indent = if m.indent != -1 {
        m.indent
    } else {
        m.post_indent
    };
    let any_blanks = total_blank != 0;

    s.effective_indent += indent;

    if indent == -1 || m.pre_indent == -1 {
        // End of file, or no non-blank predecessor: no adjustment needed
        // (git's two separate `indent == -1` / `pre_indent == -1` no-op arms).
    } else if indent > m.pre_indent {
        s.penalty += if any_blanks {
            RELATIVE_INDENT_WITH_BLANK_PENALTY
        } else {
            RELATIVE_INDENT_PENALTY
        };
    } else if indent == m.pre_indent {
        // Same indentation as predecessor; no adjustment.
    } else if m.post_indent != -1 && m.post_indent > indent {
        s.penalty += if any_blanks {
            RELATIVE_OUTDENT_WITH_BLANK_PENALTY
        } else {
            RELATIVE_OUTDENT_PENALTY
        };
    } else {
        s.penalty += if any_blanks {
            RELATIVE_DEDENT_WITH_BLANK_PENALTY
        } else {
            RELATIVE_DEDENT_PENALTY
        };
    }
}

/// git's `score_cmp`: `<0` when `s1` is the better (lower-badness) split.
fn score_cmp(s1: &SplitScore, s2: &SplitScore) -> i32 {
    let cmp_indents = (s1.effective_indent > s2.effective_indent) as i32
        - (s1.effective_indent < s2.effective_indent) as i32;
    INDENT_WEIGHT * cmp_indents + (s1.penalty - s2.penalty)
}

/// git's `struct xdlgroup`: a (possibly empty) group spanning `[start, end)` of
/// changed lines.
struct XdlGroup {
    start: i64,
    end: i64,
}

/// git's `recs_match`: the two records hash-equal (here: canonicalized bytes
/// equal).
fn recs_match(xdf: &CompactFile, a: i64, b: i64) -> bool {
    xdf.recs[a as usize] == xdf.recs[b as usize]
}

/// git's `group_init`: point `g` at the first group in `xdf`.
fn group_init(xdf: &CompactFile) -> XdlGroup {
    let mut end = 0i64;
    while xdf.changed(end) {
        end += 1;
    }
    XdlGroup { start: 0, end }
}

/// git's `group_next`: advance to the next group; `false` if already at EOF.
fn group_next(xdf: &CompactFile, g: &mut XdlGroup) -> bool {
    if g.end == xdf.nrec() {
        return false;
    }
    g.start = g.end + 1;
    g.end = g.start;
    while xdf.changed(g.end) {
        g.end += 1;
    }
    true
}

/// git's `group_previous`: step back to the previous group; `false` if at BOF.
fn group_previous(xdf: &CompactFile, g: &mut XdlGroup) -> bool {
    if g.start == 0 {
        return false;
    }
    g.end = g.start - 1;
    g.start = g.end;
    while xdf.changed(g.start - 1) {
        g.start -= 1;
    }
    true
}

/// git's `group_slide_down`: slide `g` toward EOF if the line below equals the
/// group's first line, absorbing any group it bumps into. `false` if it cannot
/// slide.
fn group_slide_down(xdf: &mut CompactFile, g: &mut XdlGroup) -> bool {
    if g.end < xdf.nrec() && recs_match(xdf, g.start, g.end) {
        xdf.set_changed(g.start, false);
        xdf.set_changed(g.end, true);
        g.start += 1;
        g.end += 1;
        while xdf.changed(g.end) {
            g.end += 1;
        }
        true
    } else {
        false
    }
}

/// git's `group_slide_up`: slide `g` toward BOF if the line above equals the
/// group's last line, absorbing any group it bumps into. `false` if it cannot
/// slide.
fn group_slide_up(xdf: &mut CompactFile, g: &mut XdlGroup) -> bool {
    if g.start > 0 && recs_match(xdf, g.start - 1, g.end - 1) {
        g.start -= 1;
        g.end -= 1;
        xdf.set_changed(g.start, true);
        xdf.set_changed(g.end, false);
        while xdf.changed(g.start - 1) {
            g.start -= 1;
        }
        true
    } else {
        false
    }
}

/// Compact the change groups of `xdf`, keeping `xdfo` (the other file) in sync.
/// A faithful port of the per-file body of git's `xdl_change_compact`. The
/// `xdfo` re-diff tail (only reachable for histogram diff) is omitted: this
/// compaction never merges groups in a way that creates new matching lines for
/// the Myers/patience/histogram scripts produced here, so the re-diff is a
/// no-op for our outputs.
fn compact_one(xdf: &mut CompactFile, xdfo: &mut CompactFile, indent_heuristic: bool) {
    let mut g = group_init(xdf);
    let mut go = group_init(xdfo);

    loop {
        // Skip empty groups in the to-be-compacted file.
        if g.end == g.start {
            if !group_next(xdf, &mut g) {
                break;
            }
            if !group_next(xdfo, &mut go) {
                break;
            }
            continue;
        }

        let mut groupsize;
        let mut earliest_end;
        let mut end_matching_other;

        loop {
            groupsize = g.end - g.start;
            end_matching_other = -1i64;

            // Shift the group backward as far as possible.
            while group_slide_up(xdf, &mut g) {
                let ok = group_previous(xdfo, &mut go);
                debug_assert!(ok, "group sync broken sliding up");
            }
            // Highest this group can be shifted; record its end.
            earliest_end = g.end;
            if go.end > go.start {
                end_matching_other = g.end;
            }
            // Now shift the group forward as far as possible.
            loop {
                if !group_slide_down(xdf, &mut g) {
                    break;
                }
                let ok = group_next(xdfo, &mut go);
                debug_assert!(ok, "group sync broken sliding down");
                if go.end > go.start {
                    end_matching_other = g.end;
                }
            }
            if groupsize == g.end - g.start {
                break;
            }
        }

        // The group is now shifted as far down as possible; only upward shifts
        // remain to consider.
        if g.end == earliest_end {
            // No shifting was possible.
        } else if end_matching_other != -1 {
            // Move the (possibly merged) group back to line up with the last
            // group of changes from the other file it can align with. Avoids
            // splitting one change into a separate add/delete.
            while go.end == go.start {
                let ok = group_slide_up(xdf, &mut g);
                debug_assert!(ok, "match disappeared");
                let ok = group_previous(xdfo, &mut go);
                debug_assert!(ok, "group sync broken sliding to match");
            }
        } else if indent_heuristic {
            // Pick the shift with the lowest indent-heuristic score.
            let mut best_shift = -1i64;
            let mut best_score = SplitScore::default();

            let mut shift = earliest_end;
            if g.end - groupsize - 1 > shift {
                shift = g.end - groupsize - 1;
            }
            if g.end - INDENT_HEURISTIC_MAX_SLIDING > shift {
                shift = g.end - INDENT_HEURISTIC_MAX_SLIDING;
            }
            while shift <= g.end {
                let mut score = SplitScore::default();
                let m = measure_split(xdf, shift);
                score_add_split(&m, &mut score);
                let m = measure_split(xdf, shift - groupsize);
                score_add_split(&m, &mut score);
                if best_shift == -1 || score_cmp(&score, &best_score) <= 0 {
                    best_score = score;
                    best_shift = shift;
                }
                shift += 1;
            }

            while g.end > best_shift {
                let ok = group_slide_up(xdf, &mut g);
                debug_assert!(ok, "best shift unreached");
                let ok = group_previous(xdfo, &mut go);
                debug_assert!(ok, "group sync broken sliding to blank line");
            }
        }

        // Advance to the next group pair.
        if !group_next(xdf, &mut g) {
            break;
        }
        if !group_next(xdfo, &mut go) {
            break;
        }
    }
}

/// Run git's `xdl_change_compact` over the [`DiffOp`] script in place.
///
/// Reconstructs the per-file `changed[]` flags from `ops`, compacts the old
/// file then the new file (each synchronized against the other, as git does),
/// and rebuilds `ops` from the recompacted flags.
fn change_compact(
    ops: &mut Vec<DiffOp>,
    old: &[DiffLine<'_>],
    new: &[DiffLine<'_>],
    ws_ignore: WsIgnore,
    indent_heuristic: bool,
) {
    // Fast path: no changes (or a single trivial run) cannot be slid.
    if ops.iter().all(|op| matches!(op, DiffOp::Equal(_))) {
        return;
    }

    // Canonicalized record bytes — the same equality the line-level diff used.
    let canon = |lines: &[DiffLine<'_>]| -> Vec<Vec<u8>> {
        if ws_ignore.is_empty() {
            lines.iter().map(|l| l.content.to_vec()).collect()
        } else {
            lines
                .iter()
                .map(|l| crate::canonicalize_line_for_match(l.content, ws_ignore))
                .collect()
        }
    };

    let mut xdf1 = CompactFile {
        recs: canon(old),
        changed: vec![false; old.len()],
    };
    let mut xdf2 = CompactFile {
        recs: canon(new),
        changed: vec![false; new.len()],
    };

    // Reconstruct git's two `changed[]` arrays from the run-length script.
    let mut oi = 0usize;
    let mut ni = 0usize;
    for op in ops.iter() {
        match *op {
            DiffOp::Equal(n) => {
                oi += n;
                ni += n;
            }
            DiffOp::Delete(n) => {
                for _ in 0..n {
                    xdf1.changed[oi] = true;
                    oi += 1;
                }
            }
            DiffOp::Insert(n) => {
                for _ in 0..n {
                    xdf2.changed[ni] = true;
                    ni += 1;
                }
            }
        }
    }

    // git compacts xdf1 (synced against xdf2) then xdf2 (synced against xdf1).
    compact_one(&mut xdf1, &mut xdf2, indent_heuristic);
    compact_one(&mut xdf2, &mut xdf1, indent_heuristic);

    // Rebuild the coalesced op script by walking both files' changed flags in
    // lockstep, emitting deletes for the old side and inserts for the new side.
    let n_old = xdf1.changed.len();
    let n_new = xdf2.changed.len();
    let mut rebuilt: Vec<DiffOp> = Vec::with_capacity(ops.len());
    let mut i = 0usize; // old index
    let mut j = 0usize; // new index
    while i < n_old || j < n_new {
        let del = i < n_old && xdf1.changed[i];
        let ins = j < n_new && xdf2.changed[j];
        if del {
            let mut run = 0usize;
            while i < n_old && xdf1.changed[i] {
                run += 1;
                i += 1;
            }
            push_op(&mut rebuilt, DiffOp::Delete(run));
        } else if ins {
            let mut run = 0usize;
            while j < n_new && xdf2.changed[j] {
                run += 1;
                j += 1;
            }
            push_op(&mut rebuilt, DiffOp::Insert(run));
        } else {
            // Both sides are unchanged here: an equal run.
            let mut run = 0usize;
            while i < n_old && j < n_new && !xdf1.changed[i] && !xdf2.changed[j] {
                run += 1;
                i += 1;
                j += 1;
            }
            debug_assert!(run > 0, "change_compact stalled rebuilding script");
            push_op(&mut rebuilt, DiffOp::Equal(run));
        }
    }

    *ops = rebuilt;
}

/// Append `op` to `out`, coalescing with a same-kind run at the tail.
fn push_op(out: &mut Vec<DiffOp>, op: DiffOp) {
    match (out.last_mut(), op) {
        (Some(DiffOp::Equal(prev)), DiffOp::Equal(n)) => *prev += n,
        (Some(DiffOp::Delete(prev)), DiffOp::Delete(n)) => *prev += n,
        (Some(DiffOp::Insert(prev)), DiffOp::Insert(n)) => *prev += n,
        _ => out.push(op),
    }
}

/// State for [`filter_hunks_to_ranges`], a port of diff.c's
/// `struct line_range_callback`. We drive it over the already-rendered
/// unified-diff lines (with inflated context) rather than xdiff's raw line
/// callback, but the algorithm is the same: buffer pending removals, open a
/// range hunk when an in-range post-image line is seen, and emit the clipped
/// `@@` header + body for each range.
struct RangeFilter<'r> {
    ranges: &'r [LineRange],
    cur_range: usize,
    /// Post/pre-image 1-based line counters seeded from each `@@` header.
    lno_post: i64,
    lno_pre: i64,
    /// The old/new line counts from the current xdiff hunk header.
    hunk_old_count: i64,
    hunk_new_count: i64,
    /// Function-name heading carried from the current `@@` header (the suffix
    /// after `@@ ... @@ `), reused verbatim on every emitted range hunk.
    func: Vec<u8>,
    /// Range hunk being accumulated.
    rhunk: Vec<u8>,
    rhunk_old_begin: i64,
    rhunk_old_count: i64,
    rhunk_new_begin: i64,
    rhunk_new_count: i64,
    rhunk_active: bool,
    rhunk_has_changes: bool,
    /// Removal lines not yet known to be in-range.
    pending_rm: Vec<u8>,
    pending_rm_count: i64,
    pending_rm_pre_begin: i64,
}

#[derive(Clone, Copy, PartialEq, Eq)]
enum RangeBodyKind {
    Context,
    Delete,
    Insert,
    Change,
    NoNewline,
}

impl RangeFilter<'_> {
    fn discard_pending_rm(&mut self) {
        self.pending_rm.clear();
        self.pending_rm_count = 0;
    }

    /// Port of diff.c:flush_rhunk — emit the accumulated range hunk (header +
    /// body) into `out`, dropping context-only hunks.
    fn flush_rhunk(&mut self, out: &mut Vec<u8>) {
        if !self.rhunk_active {
            return;
        }
        if self.pending_rm_count != 0 {
            self.rhunk.extend_from_slice(&self.pending_rm);
            self.rhunk_old_count += self.pending_rm_count;
            self.rhunk_has_changes = true;
            self.discard_pending_rm();
        }
        if !self.rhunk_has_changes {
            self.rhunk_active = false;
            self.rhunk.clear();
            return;
        }
        // git's flush_rhunk uses `@@ -%ld,%ld +%ld,%ld @@` unconditionally —
        // the count is ALWAYS shown (unlike the normal emitter, which omits a
        // count of 1).
        out.extend_from_slice(
            format!(
                "@@ -{},{} +{},{} @@",
                self.rhunk_old_begin,
                self.rhunk_old_count,
                self.rhunk_new_begin,
                self.rhunk_new_count
            )
            .as_bytes(),
        );
        if !self.func.is_empty() {
            out.push(b' ');
            out.extend_from_slice(&self.func);
        }
        out.push(b'\n');
        out.extend_from_slice(&self.rhunk);
        self.rhunk_active = false;
        self.rhunk.clear();
    }

    /// Port of diff.c:line_range_line_fn for one rendered body line. `kind`
    /// is the logical role of the rendered line after accounting for custom
    /// output indicators, ANSI color, and word-diff body rendering.
    fn body_line(&mut self, out: &mut Vec<u8>, kind: RangeBodyKind, line: &[u8]) {
        if kind == RangeBodyKind::Delete {
            if self.pending_rm_count == 0 {
                self.pending_rm_pre_begin = self.lno_pre;
            }
            self.lno_pre += 1;
            self.pending_rm.extend_from_slice(line);
            self.pending_rm_count += 1;
            return;
        }
        if kind == RangeBodyKind::NoNewline {
            if self.pending_rm_count != 0 {
                self.pending_rm.extend_from_slice(line);
            } else if self.rhunk_active {
                self.rhunk.extend_from_slice(line);
            }
            return;
        }
        // Context, insertion, and word-diff replacement lines all consume a
        // post-image line. Context/replacement lines also consume a pre-image
        // line; insertions do not.
        let lno_0 = self.lno_post - 1;
        let cur_pre = self.lno_pre;
        self.lno_post += 1;
        if matches!(kind, RangeBodyKind::Context | RangeBodyKind::Change) {
            self.lno_pre += 1;
        }

        while self.cur_range < self.ranges.len() && lno_0 >= self.ranges[self.cur_range].end {
            if self.rhunk_active {
                self.flush_rhunk(out);
            }
            self.discard_pending_rm();
            self.cur_range += 1;
        }
        if self.cur_range >= self.ranges.len() {
            self.discard_pending_rm();
            return;
        }
        let cur = self.ranges[self.cur_range];
        if lno_0 < cur.start {
            self.discard_pending_rm();
            return;
        }
        if !self.rhunk_active {
            self.rhunk_active = true;
            self.rhunk_has_changes = false;
            self.rhunk_new_begin = lno_0 + 1;
            self.rhunk_old_begin = if self.pending_rm_count != 0 {
                self.pending_rm_pre_begin
            } else {
                cur_pre
            };
            self.rhunk_old_count = 0;
            self.rhunk_new_count = 0;
            self.rhunk.clear();
        }
        if self.pending_rm_count != 0 {
            self.rhunk.extend_from_slice(&self.pending_rm);
            self.rhunk_old_count += self.pending_rm_count;
            self.rhunk_has_changes = true;
            self.discard_pending_rm();
        }
        self.rhunk.extend_from_slice(line);
        self.rhunk_new_count += 1;
        if matches!(kind, RangeBodyKind::Insert | RangeBodyKind::Change) {
            self.rhunk_has_changes = true;
        }
        if matches!(kind, RangeBodyKind::Context | RangeBodyKind::Change) {
            self.rhunk_old_count += 1;
        }
    }
}

fn skip_ansi_prefix(mut line: &[u8]) -> &[u8] {
    loop {
        let Some(rest) = line.strip_prefix(b"\x1b[") else {
            return line;
        };
        let Some(end) = rest.iter().position(|&b| (0x40..=0x7e).contains(&b)) else {
            return line;
        };
        line = &rest[end + 1..];
    }
}

fn strip_ansi(line: &[u8]) -> Vec<u8> {
    let mut stripped = Vec::with_capacity(line.len());
    let mut idx = 0usize;
    while idx < line.len() {
        if line[idx] == b'\x1b'
            && line.get(idx + 1) == Some(&b'[')
            && let Some(end) = line[idx + 2..]
                .iter()
                .position(|&b| (0x40..=0x7e).contains(&b))
        {
            idx += end + 3;
            continue;
        }
        stripped.push(line[idx]);
        idx += 1;
    }
    stripped
}

fn classify_word_diff_line(visible: &[u8]) -> RangeBodyKind {
    if visible.starts_with(b"\\") {
        return RangeBodyKind::NoNewline;
    }
    let has_old = find_subslice(visible, b"[-").is_some();
    let has_new = find_subslice(visible, b"{+").is_some();
    match (has_old, has_new) {
        (true, false) if visible.starts_with(b"[-") => return RangeBodyKind::Delete,
        (false, true) if visible.starts_with(b"{+") => return RangeBodyKind::Insert,
        (true, _) | (_, true) => return RangeBodyKind::Change,
        _ => {}
    }
    // Porcelain word-diff keeps line-level markers.
    match visible.first().copied() {
        Some(b'-') => RangeBodyKind::Delete,
        Some(b'+') => RangeBodyKind::Insert,
        Some(b' ') => RangeBodyKind::Context,
        Some(b'~') => RangeBodyKind::NoNewline,
        _ => RangeBodyKind::Context,
    }
}

fn classify_range_body_line(
    line: &[u8],
    indicators: LineIndicators,
    word_diff: bool,
    hunk_old_count: i64,
    hunk_new_count: i64,
) -> RangeBodyKind {
    let visible = skip_ansi_prefix(line);
    if word_diff {
        if hunk_old_count == 0 {
            return RangeBodyKind::Insert;
        }
        if hunk_new_count == 0 {
            return RangeBodyKind::Delete;
        }
        return classify_word_diff_line(visible);
    }
    match visible.first().copied() {
        Some(b'\\') => RangeBodyKind::NoNewline,
        Some(marker) if marker == indicators.old => RangeBodyKind::Delete,
        Some(marker) if marker == indicators.new => RangeBodyKind::Insert,
        Some(marker) if marker == indicators.context => RangeBodyKind::Context,
        _ => RangeBodyKind::Context,
    }
}

/// Clip a fully-rendered unified-diff hunk body (`full`, produced with
/// inflated context) down to the tracked `ranges`, mirroring diff.c's
/// `line_range_hunk_fn` / `line_range_line_fn` / `flush_rhunk`. The renderer's
/// `@@` header already carries the funcname suffix; we parse it back out and
/// reuse it on every emitted range hunk.
fn filter_hunks_to_ranges(
    out: &mut Vec<u8>,
    full: &[u8],
    ranges: &[LineRange],
    line_indicators: LineIndicators,
    word_diff: bool,
) {
    if ranges.is_empty() {
        return;
    }
    let mut filter = RangeFilter {
        ranges,
        cur_range: 0,
        lno_post: 0,
        lno_pre: 0,
        hunk_old_count: 0,
        hunk_new_count: 0,
        func: Vec::new(),
        rhunk: Vec::new(),
        rhunk_old_begin: 0,
        rhunk_old_count: 0,
        rhunk_new_begin: 0,
        rhunk_new_count: 0,
        rhunk_active: false,
        rhunk_has_changes: false,
        pending_rm: Vec::new(),
        pending_rm_count: 0,
        pending_rm_pre_begin: 0,
    };
    for line in split_keep_newline(full) {
        let parse_line = if line.starts_with(b"@@ ") {
            line.to_vec()
        } else {
            strip_ansi(line)
        };
        if parse_line.starts_with(b"@@ ") {
            // New xdiff hunk: any pending removals from the previous hunk are
            // left in place (diff.c does the same — the next body line decides
            // their fate), and the range hunk cursor is NOT reset across xdiff
            // hunks. Parse the begin line numbers + funcname suffix.
            if let Some((old_begin, old_count, new_begin, new_count, func)) =
                parse_hunk_header(&parse_line)
            {
                filter.lno_post = new_begin;
                filter.lno_pre = old_begin;
                filter.hunk_old_count = old_count;
                filter.hunk_new_count = new_count;
                filter.func = func;
            }
            continue;
        }
        let kind = classify_range_body_line(
            line,
            line_indicators,
            word_diff,
            filter.hunk_old_count,
            filter.hunk_new_count,
        );
        filter.body_line(out, kind, line);
    }
    filter.flush_rhunk(out);
}

/// Split `buf` into lines, each INCLUDING its trailing `\n` (the final line may
/// lack one). Empty input yields no lines.
fn split_keep_newline(buf: &[u8]) -> impl Iterator<Item = &[u8]> {
    let mut start = 0usize;
    std::iter::from_fn(move || {
        if start >= buf.len() {
            return None;
        }
        let rel = buf[start..].iter().position(|&b| b == b'\n');
        let end = match rel {
            Some(pos) => start + pos + 1,
            None => buf.len(),
        };
        let line = &buf[start..end];
        start = end;
        Some(line)
    })
}

/// Parse a rendered `@@ -o[,c] +n[,c] @@[ func]` header, returning the 1-based
/// old/new begin line numbers, old/new counts, and the trailing funcname bytes
/// (without the leading space, without a trailing newline). Begin is the value
/// xdiff emits: 1-based when the count is non-zero, one-less when zero.
fn parse_hunk_header(line: &[u8]) -> Option<(i64, i64, i64, i64, Vec<u8>)> {
    // line = "@@ -A,B +C,D @@ func\n" (or "@@ -A +C @@\n", etc.)
    let rest = line.strip_prefix(b"@@ -")?;
    let plus = rest.iter().position(|&b| b == b'+')?;
    let old_part = &rest[..plus];
    // skip "+", parse new part up to " @@"
    let after_plus = &rest[plus + 1..];
    let close = find_subslice(after_plus, b" @@")?;
    let new_part = &after_plus[..close];
    let (old_begin, old_count) = parse_range_side(old_part)?;
    let (new_begin, new_count) = parse_range_side(new_part)?;
    // Funcname suffix: everything after " @@ " (a single space separates it).
    let tail = &after_plus[close + 3..];
    let func = if let Some(f) = tail.strip_prefix(b" ") {
        let mut f = f.to_vec();
        if f.last() == Some(&b'\n') {
            f.pop();
        }
        f
    } else {
        Vec::new()
    };
    Some((old_begin, old_count, new_begin, new_count, func))
}

/// Parse an `@@` range side field, `A` or `A,B`, into `(A, B)`. A missing
/// count means one line.
fn parse_range_side(field: &[u8]) -> Option<(i64, i64)> {
    let field = field.split(|&b| b == b' ').next().unwrap_or(field);
    let mut parts = field.splitn(2, |&b| b == b',');
    let begin = std::str::from_utf8(parts.next()?)
        .ok()?
        .trim()
        .parse::<i64>()
        .ok()?;
    let count = match parts.next() {
        Some(count) => std::str::from_utf8(count)
            .ok()?
            .trim()
            .parse::<i64>()
            .ok()?,
        None => 1,
    };
    Some((begin, count))
}

fn find_subslice(haystack: &[u8], needle: &[u8]) -> Option<usize> {
    if needle.is_empty() || haystack.len() < needle.len() {
        return None;
    }
    (0..=haystack.len() - needle.len()).find(|&i| &haystack[i..i + needle.len()] == needle)
}

/// One contiguous change in the edit script (git's `xdchange`): the old/new
/// line ranges it covers, the tagged-stream positions of its first/last
/// non-context line, and whether it is ignorable (`--ignore-blank-lines` /
/// `-I<regex>`).
#[derive(Clone, Copy)]
struct Change {
    /// 0-based first old line in this change (`i1`).
    i1: usize,
    /// Number of old lines deleted (`chg1`).
    chg1: usize,
    /// 0-based first new line in this change (`i2`).
    i2: usize,
    /// Number of new lines inserted (`chg2`).
    chg2: usize,
    /// Tagged-stream index of this change's first non-context line.
    tag_first: usize,
    /// Tagged-stream index of this change's last non-context line.
    tag_last: usize,
    /// Whether this change is ignorable (blank-only / regex-only).
    ignore: bool,
}

/// Build the change list (xdchange script) from the flattened tagged stream.
/// Each maximal run of consecutive `-`/`+` lines becomes one [`Change`].
fn build_changes(tagged: &[TaggedLine<'_>]) -> Vec<Change> {
    let mut changes: Vec<Change> = Vec::new();
    let mut idx = 0usize;
    while idx < tagged.len() {
        if tagged[idx].kind == LineKind::Context {
            idx += 1;
            continue;
        }
        let tag_first = idx;
        let i1 = tagged[idx].old_index;
        let i2 = tagged[idx].new_index;
        let mut chg1 = 0usize;
        let mut chg2 = 0usize;
        while idx < tagged.len() && tagged[idx].kind != LineKind::Context {
            match tagged[idx].kind {
                LineKind::Delete => chg1 += 1,
                LineKind::Insert => chg2 += 1,
                LineKind::Context => unreachable!(),
            }
            idx += 1;
        }
        changes.push(Change {
            i1,
            chg1,
            i2,
            chg2,
            tag_first,
            tag_last: idx - 1,
            ignore: false,
        });
    }
    changes
}

/// Mark each change ignorable when its old and new lines are all blank
/// (`--ignore-blank-lines`) or all regex-matched (`-I<regex>`), mirroring
/// git's `xdl_mark_ignorable_lines` then `xdl_mark_ignorable_regex` (the regex
/// pass never overrides a blank-marked change).
fn mark_ignorable_changes(
    changes: &mut [Change],
    old: &[DiffLine<'_>],
    new: &[DiffLine<'_>],
    ws_ignore: WsIgnore,
    ci: &ChangeIgnore<'_>,
) {
    for change in changes.iter_mut() {
        if ci.ignore_blank_lines {
            let blank = (change.i1..change.i1 + change.chg1)
                .all(|i| line_is_blank(old[i].content, ws_ignore))
                && (change.i2..change.i2 + change.chg2)
                    .all(|i| line_is_blank(new[i].content, ws_ignore));
            change.ignore = blank;
        }
        if !change.ignore
            && let Some(regex_match) = ci.regex_match
        {
            let matched = (change.i1..change.i1 + change.chg1).all(|i| regex_match(old[i].content))
                && (change.i2..change.i2 + change.chg2).all(|i| regex_match(new[i].content));
            change.ignore = matched;
        }
    }
}

/// Group the change list into hunks, returning each hunk's
/// `(first_real_change_tag, last_real_change_tag)` tagged-stream span. This is
/// a behavioural port of git's `xemit.c:xdl_get_hunk` driving
/// `xdl_call_hunk_func`'s loop: it applies the `distance > max_common` hunk
/// break, drops leading ignorable changes, and excludes trailing/isolated
/// ignorable changes from the emitted span.
fn group_changes_into_hunks(
    changes: &[Change],
    context: usize,
    interhunk: usize,
) -> Vec<(usize, usize)> {
    let max_common = context.saturating_add(context).saturating_add(interhunk);
    let max_ignorable = context;

    let mut hunks: Vec<(usize, usize)> = Vec::new();
    // `start` is the index into `changes` of the first change still to emit
    // (xdl_call_hunk_func's `xch` cursor).
    let mut start = 0usize;
    while start < changes.len() {
        // Remove ignorable changes that are too far before other changes
        // (xdl_get_hunk's leading-ignorable loop). Faithful port: `xchp`
        // iterates over EVERY leading ignorable change; whenever the gap to the
        // next change is ≥ max_ignorable (or there is no next change), the hunk
        // start advances to that next change (`None` ⇒ the whole tail is
        // ignorable ⇒ no hunk). Unlike a break-on-first-keep loop, this still
        // advances past a run of ignorables when the FINAL one has no successor.
        {
            let mut xchp = start;
            while xchp < changes.len() && changes[xchp].ignore {
                let cur = &changes[xchp];
                match changes.get(xchp + 1) {
                    None => {
                        start = changes.len();
                    }
                    Some(next) => {
                        if next.i1 - (cur.i1 + cur.chg1) >= max_ignorable {
                            start = xchp + 1;
                        }
                    }
                }
                xchp += 1;
            }
        }
        if start >= changes.len() {
            break;
        }

        // Walk forward extending the hunk; `last` tracks the last *real*
        // (non-ignorable, or the very first) change that defines the hunk end.
        let mut last = start;
        let mut ignored = 0usize; // ignored new-line count accumulated
        let mut prev = start;
        let mut idx = start + 1;
        while idx < changes.len() {
            let xch = &changes[idx];
            let xchp = &changes[prev];
            let distance = xch.i1 - (xchp.i1 + xchp.chg1);
            if distance > max_common {
                break;
            }
            if distance < max_ignorable && (!xch.ignore || last == prev) {
                last = idx;
                ignored = 0;
            } else if distance < max_ignorable && xch.ignore {
                ignored += xch.chg2;
            } else if last != prev
                && xch.i1 + ignored - (changes[last].i1 + changes[last].chg1) > max_common
            {
                break;
            } else if !xch.ignore {
                last = idx;
                ignored = 0;
            } else {
                ignored += xch.chg2;
            }
            prev = idx;
            idx += 1;
        }

        let first_change = &changes[start];
        let last_change = &changes[last];
        hunks.push((first_change.tag_first, last_change.tag_last));
        start = last + 1;
    }

    hunks
}

fn expand_hunks_to_function_context(
    groups: &[(usize, usize)],
    tagged: &[TaggedLine<'_>],
    old: &[DiffLine<'_>],
    new: &[DiffLine<'_>],
    mut heading: Option<&mut HeadingFn<'_>>,
) -> Vec<(usize, usize)> {
    let Some(classifier) = heading.as_mut() else {
        return groups.to_vec();
    };
    let mut expanded = Vec::with_capacity(groups.len());
    for &(start, end) in groups {
        let first = tagged[start];
        let last = tagged[end];
        let old_changed = tagged[start..=end]
            .iter()
            .any(|line| line.kind == LineKind::Delete);
        let (side, range) = if old_changed {
            (
                FunctionSide::Old,
                function_context_range(old, first.old_index, false, classifier),
            )
        } else {
            (
                FunctionSide::New,
                function_context_range(new, first.new_index, true, classifier),
            )
        };
        let Some((range_start, range_end)) = range else {
            expanded.push((start, end));
            continue;
        };
        let mut hunk_start = expand_tag_start(tagged, start, side, range_start);
        let mut hunk_end = expand_tag_end(tagged, end, side, range_end);
        if old_changed {
            if last.old_index >= range_end {
                hunk_end = end;
            }
        } else if last.new_index >= range_end {
            hunk_end = end;
        }
        if hunk_start > start {
            hunk_start = start;
        }
        if hunk_end < end {
            hunk_end = end;
        }
        if let Some(prev) = expanded.last_mut()
            && hunk_start <= prev.1 + 1
        {
            prev.1 = prev.1.max(hunk_end);
            continue;
        }
        expanded.push((hunk_start, hunk_end));
    }
    expanded
}

#[derive(Clone, Copy)]
enum FunctionSide {
    Old,
    New,
}

fn function_context_range(
    lines: &[DiffLine<'_>],
    anchor: usize,
    prefer_forward: bool,
    heading: &mut HeadingFn<'_>,
) -> Option<(usize, usize)> {
    if lines.is_empty() {
        return None;
    }
    let anchor = anchor.min(lines.len() - 1);
    let mut heading_idx = None;
    for idx in (0..=anchor).rev() {
        if heading(lines[idx].content).is_some() {
            heading_idx = Some(idx);
            break;
        }
    }
    if heading_idx.is_none() && prefer_forward {
        for (idx, line) in lines.iter().enumerate().skip(anchor) {
            if heading(line.content).is_some() {
                heading_idx = Some(idx);
                break;
            }
        }
    }

    let (mut start, mut end) = if let Some(idx) = heading_idx {
        let mut start = idx;
        while start > 0 && !line_is_blank(lines[start - 1].content, WsIgnore::default()) {
            start -= 1;
        }
        let mut end = lines.len();
        for (next, line) in lines.iter().enumerate().skip(idx + 1) {
            if heading(line.content).is_some() {
                end = next;
                break;
            }
        }
        (start, end)
    } else {
        (0, lines.len())
    };

    while start < end && line_is_blank(lines[start].content, WsIgnore::default()) {
        start += 1;
    }
    while end > start && line_is_blank(lines[end - 1].content, WsIgnore::default()) {
        end -= 1;
    }
    (start < end).then_some((start, end))
}

fn expand_tag_start(
    tagged: &[TaggedLine<'_>],
    current: usize,
    side: FunctionSide,
    range_start: usize,
) -> usize {
    let mut start = current;
    while start > 0 {
        let prev = tagged[start - 1];
        let line_index = match side {
            FunctionSide::Old => prev.old_index,
            FunctionSide::New => prev.new_index,
        };
        if line_index < range_start {
            break;
        }
        start -= 1;
    }
    start
}

fn expand_tag_end(
    tagged: &[TaggedLine<'_>],
    current: usize,
    side: FunctionSide,
    range_end: usize,
) -> usize {
    let mut end = current;
    while end + 1 < tagged.len() {
        let next = tagged[end + 1];
        let line_index = match side {
            FunctionSide::Old => next.old_index,
            FunctionSide::New => next.new_index,
        };
        if line_index >= range_end {
            break;
        }
        end += 1;
    }
    end
}

const COLOR_MOVED_MIN_ALNUM_COUNT: usize = 20;
const INDENT_BLANKLINE: i32 = i32::MIN;

#[derive(Clone, Copy, Default)]
struct MovedStyle {
    moved: bool,
    alt: bool,
    uninteresting: bool,
}

#[derive(Clone)]
struct MovedEntry {
    tag_idx: usize,
    next_line: Option<usize>,
    next_match: Option<usize>,
    id: usize,
    indent_width: i32,
}

#[derive(Clone, Copy, Default)]
struct MovedEntryList {
    add: Option<usize>,
    del: Option<usize>,
}

#[derive(Clone, Copy)]
struct MovedBlock {
    match_entry: usize,
    wsd: i32,
}

fn mark_color_as_moved(tagged: &[TaggedLine<'_>], color_moved: ColorMoved) -> Vec<MovedStyle> {
    let (entries, entry_for_tag, entry_list) = add_lines_to_move_detection(tagged, color_moved.ws);
    let mut styles = vec![MovedStyle::default(); tagged.len()];
    let mut pmb: Vec<MovedBlock> = Vec::new();
    let mut n = 0usize;
    let mut flipped_block = false;
    let mut block_length = 0usize;
    let mut moved_symbol: Option<LineKind> = None;

    while n < tagged.len() {
        let line = tagged[n];
        let line_entry = entry_for_tag[n];
        let mut line_match = line_entry.and_then(|entry_idx| {
            let id = entries[entry_idx].id;
            match line.kind {
                LineKind::Insert => entry_list.get(id).and_then(|list| list.del),
                LineKind::Delete => entry_list.get(id).and_then(|list| list.add),
                LineKind::Context => None,
            }
        });

        if line.kind == LineKind::Context {
            flipped_block = false;
        }

        if !pmb.is_empty() && (line_match.is_none() || Some(line.kind) != moved_symbol) {
            if !adjust_last_block(&mut styles, tagged, color_moved.mode, n, block_length)
                && block_length > 1
            {
                line_match = None;
                n -= block_length;
            }
            pmb.clear();
            block_length = 0;
            flipped_block = false;
        }

        let Some(line_match) = line_match else {
            moved_symbol = None;
            n += 1;
            continue;
        };

        if color_moved.mode == ColorMovedMode::Plain {
            styles[n].moved = true;
            n += 1;
            continue;
        }

        pmb_advance_or_null(
            &mut pmb,
            &entries,
            tagged,
            line_entry.expect("plus/minus line has move-detection entry"),
            color_moved.ws,
        );

        if pmb.is_empty() {
            let contiguous =
                adjust_last_block(&mut styles, tagged, color_moved.mode, n, block_length);
            if !contiguous && block_length > 1 {
                n -= block_length;
            } else {
                fill_potential_moved_blocks(
                    line_match,
                    &entries,
                    tagged,
                    n,
                    color_moved.ws,
                    &mut pmb,
                );
            }

            if contiguous && !pmb.is_empty() && moved_symbol == Some(line.kind) {
                flipped_block = !flipped_block;
            } else {
                flipped_block = false;
            }

            moved_symbol = (!pmb.is_empty()).then_some(line.kind);
            block_length = 0;
        }

        if !pmb.is_empty() {
            block_length += 1;
            styles[n].moved = true;
            if flipped_block && color_moved.mode != ColorMovedMode::Blocks {
                styles[n].alt = true;
            }
        }
        n += 1;
    }

    adjust_last_block(&mut styles, tagged, color_moved.mode, n, block_length);
    if color_moved.mode == ColorMovedMode::DimmedZebra {
        dim_moved_lines(&mut styles, tagged);
    }
    styles
}

fn add_lines_to_move_detection(
    tagged: &[TaggedLine<'_>],
    ws: ColorMovedWs,
) -> (Vec<MovedEntry>, Vec<Option<usize>>, Vec<MovedEntryList>) {
    let mut entries: Vec<MovedEntry> = Vec::new();
    let mut entry_for_tag = vec![None; tagged.len()];
    let mut entry_list = Vec::<MovedEntryList>::new();
    let mut interned = HashMap::<Vec<u8>, usize>::new();
    let mut prev_line: Option<usize> = None;

    for (tag_idx, line) in tagged.iter().enumerate() {
        if line.kind != LineKind::Insert && line.kind != LineKind::Delete {
            prev_line = None;
            continue;
        }
        let indent = if ws.allow_indentation_change {
            moved_indent_data(line.content)
        } else {
            (0, 0)
        };
        let key = moved_line_key(line.content, indent.0, ws.ignore);
        let id = match interned.get(&key) {
            Some(id) => *id,
            None => {
                let id = interned.len();
                interned.insert(key, id);
                entry_list.push(MovedEntryList::default());
                id
            }
        };

        let entry_idx = entries.len();
        if let Some(prev) = prev_line
            && tagged[entries[prev].tag_idx].kind == line.kind
        {
            entries[prev].next_line = Some(entry_idx);
        }
        let next_match = match line.kind {
            LineKind::Insert => entry_list[id].add,
            LineKind::Delete => entry_list[id].del,
            LineKind::Context => None,
        };
        entries.push(MovedEntry {
            tag_idx,
            next_line: None,
            next_match,
            id,
            indent_width: indent.1,
        });
        match line.kind {
            LineKind::Insert => entry_list[id].add = Some(entry_idx),
            LineKind::Delete => entry_list[id].del = Some(entry_idx),
            LineKind::Context => {}
        }
        entry_for_tag[tag_idx] = Some(entry_idx);
        prev_line = Some(entry_idx);
    }

    (entries, entry_for_tag, entry_list)
}

fn moved_line_key(line: &[u8], indent_off: usize, ignore: WsIgnore) -> Vec<u8> {
    let bytes = line.get(indent_off..).unwrap_or_default();
    if ignore.is_empty() {
        bytes.to_vec()
    } else {
        canonicalize_moved_line(bytes, ignore)
    }
}

fn canonicalize_moved_line(line: &[u8], ignore: WsIgnore) -> Vec<u8> {
    let is_ws = |b: u8| matches!(b, b' ' | b'\t' | b'\n' | b'\r' | 0x0b | 0x0c);
    if ignore.all_space {
        return line.iter().copied().filter(|b| !is_ws(*b)).collect();
    }
    if ignore.space_change {
        let mut out = Vec::with_capacity(line.len());
        let mut i = 0usize;
        while i < line.len() {
            if is_ws(line[i]) {
                out.push(b' ');
                while i < line.len() && is_ws(line[i]) {
                    i += 1;
                }
            } else {
                out.push(line[i]);
                i += 1;
            }
        }
        while out.last() == Some(&b' ') {
            out.pop();
        }
        return out;
    }
    if ignore.space_at_eol {
        let mut end = line.len();
        if end > 0 && line[end - 1] == b'\n' {
            end -= 1;
        }
        while end > 0 && matches!(line[end - 1], b' ' | b'\t') {
            end -= 1;
        }
        let mut out = line[..end].to_vec();
        if line.ends_with(b"\n") {
            out.push(b'\n');
        }
        return out;
    }
    if ignore.cr_at_eol {
        let mut out = line.to_vec();
        if out.ends_with(b"\r\n") {
            let len = out.len();
            out.remove(len - 2);
        }
        return out;
    }
    line.to_vec()
}

fn moved_indent_data(line: &[u8]) -> (usize, i32) {
    let mut off = 0usize;
    let mut width = 0i32;
    while off < line.len() && matches!(line[off], b'\x0c' | b'\x0b' | b'\r') {
        off += 1;
    }
    while off < line.len() {
        match line[off] {
            b' ' => {
                width += 1;
                off += 1;
            }
            b'\t' => {
                width += 8 - (width % 8);
                off += 1;
                while off < line.len() && line[off] == b'\t' {
                    width += 8;
                    off += 1;
                }
            }
            _ => break,
        }
    }
    if line[off..].iter().all(|b| b.is_ascii_whitespace()) {
        (line.len(), INDENT_BLANKLINE)
    } else {
        (off, width)
    }
}

fn pmb_advance_or_null(
    pmb: &mut Vec<MovedBlock>,
    entries: &[MovedEntry],
    tagged: &[TaggedLine<'_>],
    line_entry: usize,
    ws: ColorMovedWs,
) {
    let mut kept = Vec::with_capacity(pmb.len());
    for mut block in pmb.iter().copied() {
        let Some(cur) = entries[block.match_entry].next_line else {
            continue;
        };
        let matched = if ws.allow_indentation_change {
            !cmp_in_block_with_wsd(entries, cur, tagged, line_entry, &mut block)
        } else {
            entries[cur].id == entries[line_entry].id
        };
        if matched {
            block.match_entry = cur;
            kept.push(block);
        }
    }
    *pmb = kept;
}

fn fill_potential_moved_blocks(
    mut line_match: usize,
    entries: &[MovedEntry],
    tagged: &[TaggedLine<'_>],
    tag_idx: usize,
    ws: ColorMovedWs,
    pmb: &mut Vec<MovedBlock>,
) {
    loop {
        let entry = &entries[line_match];
        let wsd = if ws.allow_indentation_change {
            compute_ws_delta(tagged[tag_idx].content, entry.indent_width)
        } else {
            0
        };
        pmb.push(MovedBlock {
            match_entry: line_match,
            wsd,
        });
        match entry.next_match {
            Some(next) => line_match = next,
            None => break,
        }
    }
}

fn compute_ws_delta(line: &[u8], match_indent_width: i32) -> i32 {
    let (_, width) = moved_indent_data(line);
    if width == INDENT_BLANKLINE && match_indent_width == INDENT_BLANKLINE {
        INDENT_BLANKLINE
    } else {
        width - match_indent_width
    }
}

fn cmp_in_block_with_wsd(
    entries: &[MovedEntry],
    cur: usize,
    tagged: &[TaggedLine<'_>],
    line_entry: usize,
    block: &mut MovedBlock,
) -> bool {
    let cur_entry = &entries[cur];
    if cur_entry.id != entries[line_entry].id {
        return true;
    }
    if cur_entry.indent_width == INDENT_BLANKLINE {
        return false;
    }
    let (_, line_width) = moved_indent_data(tagged[entries[line_entry].tag_idx].content);
    let delta = line_width - cur_entry.indent_width;
    if block.wsd == INDENT_BLANKLINE {
        block.wsd = delta;
    }
    delta != block.wsd
}

fn adjust_last_block(
    styles: &mut [MovedStyle],
    tagged: &[TaggedLine<'_>],
    mode: ColorMovedMode,
    n: usize,
    block_length: usize,
) -> bool {
    if mode == ColorMovedMode::Plain {
        return block_length != 0;
    }
    let mut alnum_count = 0usize;
    for i in 1..=block_length {
        for byte in tagged[n - i].content {
            if byte.is_ascii_alphanumeric() {
                alnum_count += 1;
                if alnum_count >= COLOR_MOVED_MIN_ALNUM_COUNT {
                    return true;
                }
            }
        }
    }
    for i in 1..=block_length {
        styles[n - i] = MovedStyle::default();
    }
    false
}

fn dim_moved_lines(styles: &mut [MovedStyle], tagged: &[TaggedLine<'_>]) {
    for n in 0..tagged.len() {
        if tagged[n].kind != LineKind::Insert && tagged[n].kind != LineKind::Delete {
            continue;
        }
        if !styles[n].moved {
            continue;
        }
        let prev = (n > 0
            && (tagged[n - 1].kind == LineKind::Insert || tagged[n - 1].kind == LineKind::Delete))
            .then_some(n - 1);
        let next = (n + 1 < tagged.len()
            && (tagged[n + 1].kind == LineKind::Insert || tagged[n + 1].kind == LineKind::Delete))
            .then_some(n + 1);

        if prev.is_some_and(|i| moved_zebra_mask(styles[i]) == moved_zebra_mask(styles[n]))
            && next.is_some_and(|i| moved_zebra_mask(styles[i]) == moved_zebra_mask(styles[n]))
        {
            styles[n].uninteresting = true;
            continue;
        }
        if prev.is_some_and(|i| styles[i].moved && styles[i].alt != styles[n].alt) {
            continue;
        }
        if next.is_some_and(|i| styles[i].moved && styles[i].alt != styles[n].alt) {
            continue;
        }
        styles[n].uninteresting = true;
    }
}

fn moved_zebra_mask(style: MovedStyle) -> (bool, bool) {
    (style.moved, style.alt)
}

/// Emit a single hunk covering `tagged[start..end]`: the `@@ -os,oc +ns,nc @@
/// <heading>` header followed by the context/`-`/`+` lines, including the
/// `\ No newline at end of file` markers.
fn render_one_hunk(
    out: &mut Vec<u8>,
    tagged: &[TaggedLine<'_>],
    moved_styles: Option<&[MovedStyle]>,
    old_lines: &[DiffLine<'_>],
    start: usize,
    end: usize,
    options: &mut HunkRenderOptions<'_, '_>,
) {
    let slice = &tagged[start..end];
    let mut old_count = 0usize;
    let mut new_count = 0usize;
    for line in slice {
        match line.kind {
            LineKind::Context => {
                old_count += 1;
                new_count += 1;
            }
            LineKind::Delete => old_count += 1,
            LineKind::Insert => new_count += 1,
        }
    }
    // 1-based starting line numbers; an empty side starts at 0.
    let old_start = if old_count == 0 {
        slice.first().map(|line| line.old_index).unwrap_or(0)
    } else {
        slice
            .iter()
            .find(|line| line.kind != LineKind::Insert)
            .map(|line| line.old_index + 1)
            .unwrap_or(1)
    };
    let new_start = if new_count == 0 {
        slice.first().map(|line| line.new_index).unwrap_or(0)
    } else {
        slice
            .iter()
            .find(|line| line.kind != LineKind::Delete)
            .map(|line| line.new_index + 1)
            .unwrap_or(1)
    };

    let heading = hunk_section_heading(
        old_lines,
        slice.first().map(|line| line.old_index),
        options.heading.as_deref_mut(),
    );
    let frag = format!(
        "@@ -{} +{} @@",
        format_hunk_range(old_start, old_count),
        format_hunk_range(new_start, new_count)
    );
    match options.colors {
        // Port of emit_hunk_header: the "@@ .. @@" span in the frag color,
        // the separating blank in the context color, the heading in the func
        // color (each reset-terminated).
        Some(colors) => {
            out.extend_from_slice(colors.frag.as_bytes());
            out.extend_from_slice(frag.as_bytes());
            out.extend_from_slice(colors.reset.as_bytes());
            if let Some(heading) = &heading {
                out.extend_from_slice(colors.context.as_bytes());
                out.push(b' ');
                out.extend_from_slice(colors.reset.as_bytes());
                out.extend_from_slice(colors.func.as_bytes());
                out.extend_from_slice(heading);
                out.extend_from_slice(colors.reset.as_bytes());
            }
            out.push(b'\n');
        }
        None => {
            out.extend_from_slice(frag.as_bytes());
            if let Some(heading) = &heading {
                out.push(b' ');
                out.extend_from_slice(heading);
            }
            out.push(b'\n');
        }
    }

    if let Some(word_diff) = options.word_diff.as_deref_mut() {
        // Word-diff rendering: minus/plus runs accumulate and flush at
        // context lines (fn_out_consume's diff_words branch); the
        // "\ No newline" markers are eaten.
        for line in slice {
            match line.kind {
                LineKind::Delete => word_diff.push_minus(line.content),
                LineKind::Insert => word_diff.push_plus(line.content),
                LineKind::Context => {
                    word_diff.flush(out);
                    word_diff.emit_context_line(out, line.content);
                }
            }
        }
        word_diff.flush(out);
        return;
    }

    for (offset, line) in slice.iter().enumerate() {
        let prefix = match line.kind {
            LineKind::Context => options.line_indicators.context,
            LineKind::Delete => options.line_indicators.old,
            LineKind::Insert => options.line_indicators.new,
        };
        match options.colors {
            Some(colors) => {
                // Whitespace-error highlighting applies to the selected line
                // kinds (default: new lines only).
                let ws_rule = options.ws_error.and_then(|ws| {
                    let enabled = match line.kind {
                        LineKind::Context => ws.context,
                        LineKind::Delete => ws.old,
                        LineKind::Insert => ws.new,
                    };
                    enabled.then_some(ws.rule)
                });
                let moved = moved_styles
                    .and_then(|styles| styles.get(start + offset))
                    .copied()
                    .filter(|style| style.moved);
                write_patch_line_colored(out, prefix, line.content, colors, ws_rule, moved);
            }
            None => write_patch_line(out, prefix, line.content),
        }
    }
}

/// Format one `start,count` side of an `@@` header. git omits the count when
/// it is exactly 1 (e.g. `+5` rather than `+5,1`).
fn format_hunk_range(start: usize, count: usize) -> String {
    if count == 1 {
        start.to_string()
    } else {
        format!("{start},{count}")
    }
}

/// git's section heading for a hunk: the nearest line *before* the hunk's
/// first line accepted by the caller's `heading` classifier. Headings are
/// produced by the classifier (already capped/trimmed by the caller's
/// userdiff machinery). Returns `None` when no such line precedes the hunk or
/// no classifier was supplied.
fn hunk_section_heading(
    old_lines: &[DiffLine<'_>],
    first_old_index: Option<usize>,
    mut heading: Option<&mut HeadingFn<'_>>,
) -> Option<Vec<u8>> {
    let first = first_old_index?;
    let classifier = heading.as_mut()?;
    // Scan upward from the line just above the hunk.
    for idx in (0..first).rev() {
        if let Some(found) = classifier(old_lines[idx].content) {
            return Some(found);
        }
    }
    None
}

/// Write a single diff line with its `prefix` marker, appending the
/// `\ No newline at end of file` note when the source line lacks a trailing
/// LF.
fn write_patch_line(out: &mut Vec<u8>, prefix: u8, line: &[u8]) {
    out.push(prefix);
    out.extend_from_slice(line);
    if !line.ends_with(b"\n") {
        out.extend_from_slice(b"\n\\ No newline at end of file\n");
    }
}

/// [`write_patch_line`] in color, optionally painting whitespace errors.
///
/// When `ws_rule` is `Some`, the line body is emitted through
/// [`crate::ws::ws_check_emit`] (git's `emit_line_ws_markup` highlighted
/// branch): the sign is painted in the line color, then the body's non-error
/// segments in the line color and its whitespace-error segments in
/// `colors.whitespace`. A clean line produces no whitespace spans, so it stays
/// visually plain.
///
/// When `ws_rule` is `None`, context/old lines paint the sign and body in one
/// span; new lines paint the sign and body as separate spans (the default
/// `ws-error-highlight` path with no rule).
fn write_patch_line_colored(
    out: &mut Vec<u8>,
    prefix: u8,
    line: &[u8],
    colors: RenderColors<'_>,
    ws_rule: Option<crate::ws::WsRule>,
    moved: Option<MovedStyle>,
) {
    let (body, terminated) = match line.split_last() {
        Some((b'\n', body)) => (body, true),
        _ => (line, false),
    };
    let color = match (prefix, moved) {
        (b'-', Some(style)) if style.uninteresting && style.alt => colors.old_moved_alt_dim,
        (b'-', Some(style)) if style.uninteresting => colors.old_moved_dim,
        (b'-', Some(style)) if style.alt => colors.old_moved_alt,
        (b'-', Some(_)) => colors.old_moved,
        (b'+', Some(style)) if style.uninteresting && style.alt => colors.new_moved_alt_dim,
        (b'+', Some(style)) if style.uninteresting => colors.new_moved_dim,
        (b'+', Some(style)) if style.alt => colors.new_moved_alt,
        (b'+', Some(_)) => colors.new_moved,
        (b'-', _) => colors.old,
        (b'+', _) => colors.new,
        _ => colors.context,
    };

    if let Some(rule) = ws_rule {
        if rule == 0 {
            out.extend_from_slice(color.as_bytes());
            out.push(prefix);
            out.extend_from_slice(body);
            out.extend_from_slice(colors.reset.as_bytes());
            out.push(b'\n');
            if !terminated {
                out.extend_from_slice(colors.context.as_bytes());
                out.extend_from_slice(b"\\ No newline at end of file");
                out.extend_from_slice(colors.reset.as_bytes());
                out.push(b'\n');
            }
            return;
        }
        // Sign in the line color, then the body through ws_check_emit (no
        // trailing newline in `body`, so the emit's own LF handling is inert).
        out.extend_from_slice(color.as_bytes());
        out.push(prefix);
        out.extend_from_slice(colors.reset.as_bytes());
        let emit_colors = crate::ws::WsEmitColors {
            set: color,
            reset: colors.reset,
            ws: colors.whitespace,
        };
        crate::ws::ws_check_emit(body, rule, out, &emit_colors);
        out.push(b'\n');
        if !terminated {
            let marker_color = if rule & crate::ws::WS_INCOMPLETE_LINE != 0 {
                colors.whitespace
            } else {
                colors.context
            };
            out.extend_from_slice(marker_color.as_bytes());
            out.extend_from_slice(b"\\ No newline at end of file");
            out.extend_from_slice(colors.reset.as_bytes());
            out.push(b'\n');
        }
        return;
    }

    if prefix == b'+' {
        out.extend_from_slice(color.as_bytes());
        out.push(prefix);
        out.extend_from_slice(colors.reset.as_bytes());
        if !body.is_empty() {
            out.extend_from_slice(color.as_bytes());
            out.extend_from_slice(body);
            out.extend_from_slice(colors.reset.as_bytes());
        }
    } else {
        out.extend_from_slice(color.as_bytes());
        out.push(prefix);
        out.extend_from_slice(body);
        out.extend_from_slice(colors.reset.as_bytes());
    }
    out.push(b'\n');
    if !terminated {
        out.extend_from_slice(colors.context.as_bytes());
        out.extend_from_slice(b"\\ No newline at end of file");
        out.extend_from_slice(colors.reset.as_bytes());
        out.push(b'\n');
    }
}

// ===========================================================================
// Combined / merge-commit diff renderer (`-c` / `--cc`).
//
// This is the byte-for-byte port of git's `combine-diff.c`
// (`combine_diff` / `make_hunks` / `dump_sline`): the multi-parent
// `@@@ -p1 -p2 +out @@@` hunk header (with one extra `@` per parent and one
// `-pN,cN` column per parent), the per-parent prefix columns on each body
// line, and the `--cc` "dense" simplification that drops hunks whose result
// matches at least one parent ("uninteresting" hunks).
//
// The renderer is repository-agnostic, exactly like the unified-diff renderer
// above: the caller supplies the *result* blob and one blob per parent (plus
// the line-diff algorithm / whitespace flags), and we emit only the hunk body
// — the per-file `diff --cc`/`index`/`---`/`+++` metainfo header stays with the
// command, which owns the repository / oid / mode context.
//
// Data-structure correspondence with combine-diff.c:
//   * `Sline`  <-> `struct sline` (one per result line, plus a trailing
//     sentinel `sline[cnt]` whose `bol` is empty),
//   * `Sline.lost` <-> `struct lline` list (lines deleted relative to some
//     parent, hung before the surviving result line),
//   * the `flag` bitset: bit `n` set => parent `n` did NOT have this result
//     line (i.e. it was added relative to parent `n`); bit `num_parent`
//     ("mark") => the line is part of a shown hunk; bit `num_parent+1`
//     ("no_pre_delete") => suppress the leading deletions before this line.
// ===========================================================================

/// One result line in the combined-diff `sline` array, plus the deletions
/// ("lost" lines) that hang in front of it.
struct CdLine {
    /// The surviving result line bytes, WITHOUT the trailing newline.
    bol: Vec<u8>,
    /// Deletions hung before this line, in display order. `parent_map` is the
    /// bitset of parents that had the deleted line (git coalesces these across
    /// parents via an LCS; we replicate that with [`coalesce_lost`]).
    lost: Vec<CdLost>,
    /// Pre-coalesce deletions accumulated for the parent currently being
    /// folded (drained into `lost` after each parent, like git's `plost`).
    plost: Vec<Vec<u8>>,
    /// `flag` bitset (see module comment).
    flag: u64,
    /// `p_lno[n]` = 1-based line number in parent `n` at which a hunk starting
    /// at this result line begins. Sized `num_parent`.
    p_lno: Vec<u64>,
}

/// A single deleted ("lost") line and the set of parents it was removed from.
struct CdLost {
    line: Vec<u8>,
    parent_map: u64,
}

/// Options controlling the combined-diff body emission.
pub struct CombinedRenderOptions {
    /// `--cc` dense simplification (drop hunks the result shares with a parent);
    /// `-c` (plain combined) leaves it `false`.
    pub dense: bool,
    /// Unified-context line count (`-U`, default 3).
    pub context: usize,
    /// Line-diff algorithm used for each parent-vs-result 2-way diff.
    pub algorithm: DiffAlgorithm,
    /// Whitespace-ignore flags applied to each parent-vs-result 2-way diff and
    /// to the lost-line coalescing match.
    pub ws_ignore: WsIgnore,
}

impl Default for CombinedRenderOptions {
    fn default() -> Self {
        Self {
            dense: true,
            context: DEFAULT_CONTEXT,
            algorithm: DiffAlgorithm::Myers,
            ws_ignore: WsIgnore::default(),
        }
    }
}

/// Render a combined / merge diff body into `out`.
///
/// `result` is the merge-result blob; `parents` holds one blob per parent (in
/// parent order). Returns `true` when at least one hunk survives the
/// "interesting" filter — the caller uses this to decide whether to print the
/// metainfo header at all (git only prints `diff --cc <path>` + body when
/// `show_hunks || mode_differs`).
///
/// Mirrors `show_patch_diff`'s body half: build the `sline` array, fold each
/// parent into it via [`combine_one_parent`], run [`make_hunks`], then
/// [`dump_sline`].
pub fn render_combined(out: &mut Vec<u8>, result: &[u8], parents: &[&[u8]]) -> bool {
    render_combined_with(out, result, parents, &CombinedRenderOptions::default())
}

/// [`render_combined`] with explicit options.
pub fn render_combined_with(
    out: &mut Vec<u8>,
    result: &[u8],
    parents: &[&[u8]],
    options: &CombinedRenderOptions,
) -> bool {
    let num_parent = parents.len();
    debug_assert!(num_parent >= 1);

    // Split the result into lines (without trailing newline), counting an
    // unterminated final line as its own line — git's `cnt` counts '\n' plus an
    // incomplete trailing line.
    let result_lines = split_lines(result);
    let cnt = result_lines.len();

    // git allocates `cnt + 2` slines: indices `0..cnt-1` are the result lines,
    // `sline[cnt]` is the trailing sentinel (where end-of-file deletions hang),
    // and `sline[cnt+1]` carries the per-parent trailer p_lno that
    // `show_parent_lno` reads for a hunk whose end touches the last line.
    let mut sline: Vec<CdLine> = Vec::with_capacity(cnt + 2);
    for line in &result_lines {
        sline.push(CdLine {
            bol: line.bytes_without_newline().to_vec(),
            lost: Vec::new(),
            plost: Vec::new(),
            flag: 0,
            p_lno: vec![0; num_parent],
        });
    }
    for _ in 0..2 {
        sline.push(CdLine {
            bol: Vec::new(),
            lost: Vec::new(),
            plost: Vec::new(),
            flag: 0,
            p_lno: vec![0; num_parent],
        });
    }

    // Fold each parent into the sline array. git reuses an earlier parent's
    // result when two parents have the identical blob (`reuse_combine_diff`);
    // we replicate that to keep p_lno / flags identical.
    for n in 0..num_parent {
        let mut reused = None;
        for j in 0..n {
            if parents[j] == parents[n] {
                reused = Some(j);
                break;
            }
        }
        match reused {
            Some(j) => reuse_combine_diff(&mut sline, cnt, n, j),
            None => combine_one_parent(&mut sline, &result_lines, parents[n], n, options),
        }
    }

    let show_hunks = make_hunks(&mut sline, cnt, num_parent, options.dense, options.context);
    if show_hunks {
        dump_sline(out, &sline, cnt, num_parent, options.context);
    }
    show_hunks
}

/// Fold one parent's 2-way diff against the result into the `sline` array
/// (git's `combine_diff` + the consume_hunk/consume_line callbacks).
fn combine_one_parent(
    sline: &mut [CdLine],
    result_lines: &[DiffLine<'_>],
    parent: &[u8],
    n: usize,
    options: &CombinedRenderOptions,
) {
    let cnt = result_lines.len();
    let nmask = 1u64 << n;
    let parent_lines = split_lines(parent);
    let ops = myers_diff_lines_ws(
        &parent_lines,
        result_lines,
        options.ws_ignore,
        options.algorithm,
    );

    // Walk the edit script, tracking the 1-based result line number (`lno`,
    // git's `state->lno`) and the parent line number (`p_lno`/`ob`). For each
    // hunk: deletions hang on `lost_bucket`; insertions set the nmask flag on
    // the result line; the hunk start records the parent line number into
    // `p_lno[n]` of the result line preceding the hunk.
    //
    // git groups the script into hunks (runs separated by Equal context); we
    // mirror consume_hunk by detecting the boundary at each non-Equal run.
    let mut old_idx: usize = 0; // 0-based parent line consumed
    let mut new_idx: usize = 0; // 0-based result line consumed
    let mut i = 0;
    while i < ops.len() {
        match ops[i] {
            DiffOp::Equal(k) => {
                old_idx += k;
                new_idx += k;
                i += 1;
            }
            _ => {
                // Collect a maximal run of consecutive Delete/Insert ops as one
                // hunk (git's xdiff emits one @@ hunk per such run).
                let hunk_old_start = old_idx; // 0-based
                let hunk_new_start = new_idx; // 0-based
                let mut dels: Vec<&[u8]> = Vec::new();
                while i < ops.len() {
                    match ops[i] {
                        DiffOp::Delete(k) => {
                            for _ in 0..k {
                                dels.push(parent_lines[old_idx].bytes_without_newline());
                                old_idx += 1;
                            }
                            i += 1;
                        }
                        DiffOp::Insert(k) => {
                            new_idx += k;
                            i += 1;
                        }
                        DiffOp::Equal(_) => break,
                    }
                }
                let _ = hunk_old_start;

                // Lost bucket: deletions hang on the result line at the hunk
                // start (sline[hunk_new_start]). git's distinction between the
                // additions-present (`nb-1`) and pure-deletion (`nb`) cases
                // collapses to the same index here because our `hunk_new_start`
                // is the 0-based result line immediately *after* the preceding
                // context, matching git's `nb-1` for the additions case and the
                // bucket-after for the pure-deletion case once the result line
                // numbering (1-based `nb`) is accounted for. The authoritative
                // p_lno values are recomputed in the loop below, so we do not
                // record them here.
                for d in &dels {
                    sline[hunk_new_start].plost.push(d.to_vec());
                }
                // Mark inserted result lines: flag bit n set => parent n lacked
                // this line.
                for line in sline.iter_mut().take(new_idx.min(cnt)).skip(hunk_new_start) {
                    line.flag |= nmask;
                }
            }
        }
    }

    // Coalesce the plost lines into lost (git's coalesce_lines), then assign
    // p_lno numbers per parent — git's second loop in combine_diff.
    let mut p_lno: u64 = 1;
    for (lno, line) in sline.iter_mut().enumerate().take(cnt + 1) {
        line.p_lno[n] = p_lno;
        if !line.plost.is_empty() {
            let plost = std::mem::take(&mut line.plost);
            coalesce_lost(&mut line.lost, plost, n, options);
        }
        // How many parent lines does this sline advance?
        for ll in &line.lost {
            if ll.parent_map & nmask != 0 {
                p_lno += 1; // '-' means parent had it
            }
        }
        if lno < cnt && (line.flag & nmask) == 0 {
            p_lno += 1; // no '+' means parent had it
        }
    }
    sline[cnt + 1].p_lno[n] = p_lno; // trailer (git's sline[cnt+1])
}

/// Coalesce a parent's freshly-collected deletions into the line's existing
/// lost list (git's `coalesce_lines` LCS merge). A deletion that matches an
/// already-present lost line (under the active whitespace flags) gets its
/// parent bit OR'd into that line's `parent_map` instead of being added again.
fn coalesce_lost(
    base: &mut Vec<CdLost>,
    newlines: Vec<Vec<u8>>,
    n: usize,
    options: &CombinedRenderOptions,
) {
    let pmask = 1u64 << n;
    if newlines.is_empty() {
        return;
    }
    if base.is_empty() {
        for line in newlines {
            base.push(CdLost {
                line,
                parent_map: pmask,
            });
        }
        return;
    }

    // LCS over (base lines, new lines) by whitespace-aware equality, exactly
    // like git: MATCH => OR the parent bit into the base line; NEW => insert the
    // new line at that position; BASE => keep base line as-is.
    let m = base.len();
    let k = newlines.len();
    let mut lcs = vec![vec![0i32; k + 1]; m + 1];
    for i in 1..=m {
        for j in 1..=k {
            if combined_lines_match(&base[i - 1].line, &newlines[j - 1], options.ws_ignore) {
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
            } else if lcs[i][j - 1] >= lcs[i - 1][j] {
                lcs[i][j] = lcs[i][j - 1];
            } else {
                lcs[i][j] = lcs[i - 1][j];
            }
        }
    }

    // Backtrack, building the merged list in reverse.
    let mut merged: Vec<CdLost> = Vec::with_capacity(m + k);
    let mut i = m;
    let mut j = k;
    while i > 0 || j > 0 {
        if i > 0
            && j > 0
            && combined_lines_match(&base[i - 1].line, &newlines[j - 1], options.ws_ignore)
        {
            let mut entry = std::mem::replace(
                &mut base[i - 1],
                CdLost {
                    line: Vec::new(),
                    parent_map: 0,
                },
            );
            entry.parent_map |= pmask;
            merged.push(entry);
            i -= 1;
            j -= 1;
        } else if j > 0 && (i == 0 || lcs[i][j - 1] >= lcs[i - 1][j]) {
            merged.push(CdLost {
                line: newlines[j - 1].clone(),
                parent_map: pmask,
            });
            j -= 1;
        } else {
            let entry = std::mem::replace(
                &mut base[i - 1],
                CdLost {
                    line: Vec::new(),
                    parent_map: 0,
                },
            );
            merged.push(entry);
            i -= 1;
        }
    }
    merged.reverse();
    *base = merged;
}

/// Whitespace-aware line equality used by the lost-line coalescer
/// (git's `match_string_spaces`). Only the all-space / space-change flavours
/// affect the comparison; otherwise it is a byte compare.
fn combined_lines_match(a: &[u8], b: &[u8], ws: WsIgnore) -> bool {
    if ws.all_space || ws.space_change || ws.space_at_eol {
        let at = strip_trailing_ws(a);
        let bt = strip_trailing_ws(b);
        if !ws.all_space && !ws.space_change {
            return at == bt;
        }
        return ws_squash_eq(at, bt, ws.space_change);
    }
    a == b
}

fn strip_trailing_ws(s: &[u8]) -> &[u8] {
    let mut end = s.len();
    while end > 0 && (s[end - 1] == b' ' || s[end - 1] == b'\t') {
        end -= 1;
    }
    &s[..end]
}

/// Compare two lines ignoring whitespace runs (`-w`) or treating runs as a
/// single space (`-b`).
fn ws_squash_eq(a: &[u8], b: &[u8], change_only: bool) -> bool {
    let is_ws = |c: u8| c == b' ' || c == b'\t';
    let (mut ia, mut ib) = (0usize, 0usize);
    while ia < a.len() && ib < b.len() {
        let (ca, cb) = (a[ia], b[ib]);
        if is_ws(ca) || is_ws(cb) {
            if change_only && (!is_ws(ca) || !is_ws(cb)) {
                return false;
            }
            // For -b, a whitespace run on both sides counts as equal; for -w,
            // whitespace is skipped entirely. Skip the runs on both sides.
            if change_only {
                while ia < a.len() && is_ws(a[ia]) {
                    ia += 1;
                }
                while ib < b.len() && is_ws(b[ib]) {
                    ib += 1;
                }
                continue;
            } else {
                if is_ws(ca) {
                    ia += 1;
                    continue;
                }
                if is_ws(cb) {
                    ib += 1;
                    continue;
                }
            }
        }
        if ca != cb {
            return false;
        }
        ia += 1;
        ib += 1;
    }
    // Consume trailing whitespace.
    while ia < a.len() && is_ws(a[ia]) {
        ia += 1;
    }
    while ib < b.len() && is_ws(b[ib]) {
        ib += 1;
    }
    ia == a.len() && ib == b.len()
}

/// git's `reuse_combine_diff`: when parent `i` has the same blob as a
/// previously-folded parent `j`, copy `j`'s flags / lost parent-bits / p_lno
/// across instead of re-diffing.
fn reuse_combine_diff(sline: &mut [CdLine], cnt: usize, i: usize, j: usize) {
    let imask = 1u64 << i;
    let jmask = 1u64 << j;
    for line in sline.iter_mut().take(cnt + 1) {
        line.p_lno[i] = line.p_lno[j];
        for ll in &mut line.lost {
            if ll.parent_map & jmask != 0 {
                ll.parent_map |= imask;
            }
        }
        if line.flag & jmask != 0 {
            line.flag |= imask;
        }
    }
    // The overall trailer (sline[cnt+1]).
    sline[cnt + 1].p_lno[i] = sline[cnt + 1].p_lno[j];
}

/// Is this result line "interesting" — does any parent lack it, or does it have
/// deletions hung in front (git's `interesting`).
fn cd_interesting(sline: &CdLine, all_mask: u64) -> bool {
    (sline.flag & all_mask) != 0 || !sline.lost.is_empty()
}

/// git's `adjust_hunk_tail`.
fn adjust_hunk_tail(sline: &[CdLine], all_mask: u64, hunk_begin: usize, mut i: usize) -> usize {
    if hunk_begin < i && (sline[i - 1].flag & all_mask) == 0 {
        i -= 1;
    }
    i
}

/// git's `find_next`.
fn find_next(
    sline: &[CdLine],
    mark: u64,
    mut i: usize,
    cnt: usize,
    look_for_uninteresting: bool,
) -> usize {
    while i <= cnt {
        let marked = (sline[i].flag & mark) != 0;
        if look_for_uninteresting {
            if !marked {
                return i;
            }
        } else if marked {
            return i;
        }
        i += 1;
    }
    i
}

/// git's `give_context`: paint context lines (and bridge small gaps) around the
/// interesting lines, using the `mark` bit. Returns whether any hunk shows.
fn give_context(sline: &mut [CdLine], cnt: usize, num_parent: usize, context: usize) -> bool {
    let all_mask = (1u64 << num_parent) - 1;
    let mark = 1u64 << num_parent;
    let no_pre_delete = 2u64 << num_parent;

    let mut i = find_next(sline, mark, 0, cnt, false);
    if cnt < i {
        return false;
    }

    while i <= cnt {
        let mut j = i.saturating_sub(context);
        // Paint a few lines before the first interesting line.
        while j < i {
            if (sline[j].flag & mark) == 0 {
                sline[j].flag |= no_pre_delete;
            }
            sline[j].flag |= mark;
            j += 1;
        }

        loop {
            // Where does the next uninteresting line start?
            j = find_next(sline, mark, i, cnt, true);
            if cnt < j {
                // The rest are all interesting.
                return true;
            }
            // Lookahead context lines.
            let k = find_next(sline, mark, j, cnt, false);
            let j2 = adjust_hunk_tail(sline, all_mask, i, j);

            if k < j2 + context {
                // Small gap: paint it interesting and continue.
                let mut jj = j2;
                while jj < k {
                    sline[jj].flag |= mark;
                    jj += 1;
                }
                i = k;
                continue;
            }

            // No overlap within context: paint the trailing edge a bit.
            i = k;
            let kk = if j2 + context < cnt + 1 {
                j2 + context
            } else {
                cnt + 1
            };
            let mut jj = j2;
            while jj < kk {
                sline[jj].flag |= mark;
                jj += 1;
            }
            break;
        }
    }
    true
}

/// git's `make_hunks`: mark interesting lines, run the `--cc` dense
/// simplification when requested, then `give_context`.
fn make_hunks(
    sline: &mut [CdLine],
    cnt: usize,
    num_parent: usize,
    dense: bool,
    context: usize,
) -> bool {
    let all_mask = (1u64 << num_parent) - 1;
    let mark = 1u64 << num_parent;

    for line in sline.iter_mut().take(cnt + 1) {
        if cd_interesting(line, all_mask) {
            line.flag |= mark;
        } else {
            line.flag &= !mark;
        }
    }
    if !dense {
        return give_context(sline, cnt, num_parent, context);
    }

    // Dense simplification: for each marked hunk, drop it when the result
    // differs from a single parent only (or matches all but one parent the
    // same way) — git's "interesting" recomputation.
    let mut i = 0;
    while i <= cnt {
        while i <= cnt && (sline[i].flag & mark) == 0 {
            i += 1;
        }
        if cnt < i {
            break;
        }
        let hunk_begin = i;
        let mut j = i + 1;
        while j <= cnt {
            if (sline[j].flag & mark) == 0 {
                // Look beyond the end for an interesting line within context.
                let mut la = adjust_hunk_tail(sline, all_mask, hunk_begin, j);
                la = if la + context < cnt + 1 {
                    la + context
                } else {
                    cnt + 1
                };
                let mut contin = false;
                while la > 0 && j < la {
                    la -= 1;
                    if (sline[la].flag & mark) != 0 {
                        contin = true;
                        break;
                    }
                }
                if !contin {
                    break;
                }
                j = la;
            }
            j += 1;
        }
        let hunk_end = j;

        // Is the hunk "really" interesting? Check whether all changed lines
        // record the same set of parents.
        let mut same_diff: u64 = 0;
        let mut has_interesting = false;
        let mut jj = i;
        while jj < hunk_end && !has_interesting {
            let this_diff = sline[jj].flag & all_mask;
            if this_diff != 0 {
                if same_diff == 0 {
                    same_diff = this_diff;
                } else if same_diff != this_diff {
                    has_interesting = true;
                    break;
                }
            }
            for ll in &sline[jj].lost {
                if has_interesting {
                    break;
                }
                let td = ll.parent_map;
                if same_diff == 0 {
                    same_diff = td;
                } else if same_diff != td {
                    has_interesting = true;
                }
            }
            jj += 1;
        }

        if !has_interesting && same_diff != all_mask {
            // Not interesting after all: unmark the whole hunk.
            for line in sline.iter_mut().take(hunk_end).skip(hunk_begin) {
                line.flag &= !mark;
            }
        }
        i = hunk_end;
    }

    give_context(sline, cnt, num_parent, context)
}

/// git's `show_parent_lno`: emit one `-l0,len` column for parent `n`.
fn show_parent_lno(
    out: &mut Vec<u8>,
    sline: &[CdLine],
    l0: usize,
    l1: usize,
    n: usize,
    null_context: u64,
) {
    let a = sline[l0].p_lno[n];
    let b = sline[l1].p_lno[n];
    out.extend_from_slice(format!(" -{},{}", a, b - a - null_context).as_bytes());
}

/// git's `hunk_comment_line` test (used to append a function-context comment
/// to the `@@@ ... @@@` header).
fn hunk_comment_line(bol: &[u8]) -> bool {
    if bol.is_empty() {
        return false;
    }
    let ch = bol[0];
    ch.is_ascii_alphabetic() || ch == b'_' || ch == b'$'
}

/// git's `show_line_to_eol`: emit a line, preserving a trailing CR. The bytes
/// here never include the newline; we add it.
fn show_line_to_eol(out: &mut Vec<u8>, line: &[u8]) {
    let saw_cr = line.last() == Some(&b'\r');
    if saw_cr {
        out.extend_from_slice(&line[..line.len() - 1]);
        out.push(b'\r');
    } else {
        out.extend_from_slice(line);
    }
    out.push(b'\n');
}

/// git's `dump_sline`: emit the combined-diff hunk bodies for all marked hunks.
fn dump_sline(out: &mut Vec<u8>, sline: &[CdLine], cnt: usize, num_parent: usize, context: usize) {
    let mark = 1u64 << num_parent;
    let no_pre_delete = 2u64 << num_parent;
    let mut lno: usize = 0;

    loop {
        let mut hunk_comment: Option<&[u8]> = None;
        while lno <= cnt && (sline[lno].flag & mark) == 0 {
            if hunk_comment_line(&sline[lno].bol) {
                hunk_comment = Some(&sline[lno].bol);
            }
            lno += 1;
        }
        if cnt < lno {
            break;
        }
        let mut hunk_end = lno + 1;
        while hunk_end <= cnt {
            if (sline[hunk_end].flag & mark) == 0 {
                break;
            }
            hunk_end += 1;
        }

        let mut rlines = (hunk_end - lno) as u64;
        if cnt < hunk_end {
            rlines -= 1; // pointing at the last delete hunk
        }

        let mut null_context: u64 = 0;
        if context == 0 {
            // --unified=0: count the all-blank-context result lines so the
            // header line counts exclude them.
            for sl in sline.iter().take(hunk_end).skip(lno) {
                if (sl.flag & (mark - 1)) == 0 {
                    null_context += 1;
                }
            }
            rlines -= null_context;
        }

        // Header: `@@@`... (num_parent+1 markers), one -l,c column per parent,
        // ` +out_start,out_len `, num_parent+1 markers again.
        for _ in 0..=num_parent {
            out.push(b'@');
        }
        for i in 0..num_parent {
            show_parent_lno(out, sline, lno, hunk_end, i, null_context);
        }
        out.extend_from_slice(format!(" +{},{} ", lno + 1, rlines).as_bytes());
        for _ in 0..=num_parent {
            out.push(b'@');
        }

        if let Some(comment) = hunk_comment {
            let mut comment_end = 0;
            for (idx, &ch) in comment.iter().take(40).enumerate() {
                if ch == b'\n' {
                    break;
                }
                if !ch.is_ascii_whitespace() {
                    comment_end = idx + 1;
                }
            }
            if comment_end != 0 {
                out.push(b' ');
                out.extend_from_slice(&comment[..comment_end]);
            }
        }
        out.push(b'\n');

        // Body.
        while lno < hunk_end {
            let sl = &sline[lno];
            lno += 1;
            // Lost (deleted) lines hung before this result line.
            if (sl.flag & no_pre_delete) == 0 {
                for ll in &sl.lost {
                    for j in 0..num_parent {
                        if ll.parent_map & (1u64 << j) != 0 {
                            out.push(b'-');
                        } else {
                            out.push(b' ');
                        }
                    }
                    show_line_to_eol(out, &ll.line);
                }
            }
            if cnt < lno {
                break;
            }
            if (sl.flag & (mark - 1)) == 0 {
                // This sline only existed to hang the lost lines in front.
                if context == 0 {
                    continue;
                }
            }
            let mut p_mask = 1u64;
            for _ in 0..num_parent {
                if p_mask & sl.flag != 0 {
                    out.push(b'+');
                } else {
                    out.push(b' ');
                }
                p_mask <<= 1;
            }
            show_line_to_eol(out, &sl.bol);
        }
    }
}

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

    fn render_plain(old: Option<&[u8]>, new: Option<&[u8]>) -> Vec<u8> {
        let mut out = Vec::new();
        let mut options = HunkRenderOptions::default();
        render_hunks(&mut out, old, new, &mut options);
        out
    }

    #[test]
    fn identical_content_renders_nothing() {
        assert!(render_plain(Some(b"a\nb\n"), Some(b"a\nb\n")).is_empty());
    }

    #[test]
    fn single_line_change_basic_hunk() {
        let out = render_plain(Some(b"alpha\nbeta\ngamma\n"), Some(b"alpha\nBETA\ngamma\n"));
        assert_eq!(
            out,
            b"@@ -1,3 +1,3 @@\n alpha\n-beta\n+BETA\n gamma\n".to_vec(),
        );
    }

    #[test]
    fn count_omitted_when_one() {
        // A single-line file changed in place yields `-1 +1` (no `,1`).
        let out = render_plain(Some(b"old\n"), Some(b"new\n"));
        assert_eq!(out, b"@@ -1 +1 @@\n-old\n+new\n".to_vec());
    }

    #[test]
    fn no_newline_marker_on_old_side() {
        let out = render_plain(Some(b"only line no newline"), None);
        assert_eq!(
            out,
            b"@@ -1 +0,0 @@\n-only line no newline\n\\ No newline at end of file\n".to_vec(),
        );
    }

    #[test]
    fn no_newline_marker_on_new_side() {
        let out = render_plain(Some(b"beta\n"), Some(b"beta-notail"));
        assert_eq!(
            out,
            b"@@ -1 +1 @@\n-beta\n+beta-notail\n\\ No newline at end of file\n".to_vec(),
        );
    }

    #[test]
    fn pure_insertion_into_empty() {
        let out = render_plain(None, Some(b"x\ny\n"));
        assert_eq!(out, b"@@ -0,0 +1,2 @@\n+x\n+y\n".to_vec());
    }

    #[test]
    fn distant_changes_split_into_two_hunks() {
        let old: &[u8] = b"a\nb\nc\nd\ne\nf\ng\nh\ni\nj\n";
        let new: &[u8] = b"A\nb\nc\nd\ne\nf\ng\nh\ni\nJ\n";
        let out = render_plain(Some(old), Some(new));
        // Two changes 9 lines apart (> 2*3+1) produce two separate hunks.
        let text = String::from_utf8(out).expect("rendered output is valid UTF-8");
        assert_eq!(text.matches("@@ ").count(), 2, "expected two hunks: {text}");
    }

    #[test]
    fn heading_callback_supplies_section() {
        // The change is far enough below `fn foo()` that the funcname line
        // precedes the hunk (the heading scan looks *above* the hunk's first
        // line, so a change touching line 1 would correctly find no heading).
        let old: &[u8] = b"fn foo() {\n    a\n    b\n    c\n    d\n    e\n    f\n    g\n}\n";
        let new: &[u8] = b"fn foo() {\n    a\n    b\n    c\n    d\n    CHANGED\n    f\n    g\n}\n";
        let mut out = Vec::new();
        // Classifier accepts any line whose first byte is an ASCII letter
        // (a crude def_ff stand-in for the test).
        let mut heading_fn = |line: &[u8]| -> Option<Vec<u8>> {
            if line.first().is_some_and(u8::is_ascii_alphabetic) {
                Some(line.strip_suffix(b"\n").unwrap_or(line).to_vec())
            } else {
                None
            }
        };
        let mut options = HunkRenderOptions {
            heading: Some(&mut heading_fn),
            ..Default::default()
        };
        render_hunks(&mut out, Some(old), Some(new), &mut options);
        let text = String::from_utf8(out).expect("rendered output is valid UTF-8");
        assert!(
            text.starts_with("@@ -3,7 +3,7 @@ fn foo() {\n"),
            "expected funcname heading: {text}",
        );
    }

    fn render_cc(result: &[u8], parents: &[&[u8]], dense: bool) -> String {
        let mut out = Vec::new();
        let opts = CombinedRenderOptions {
            dense,
            ..Default::default()
        };
        render_combined_with(&mut out, result, parents, &opts);
        String::from_utf8(out).expect("combined output is valid UTF-8")
    }

    #[test]
    fn combined_two_parent_dense_header_and_columns() {
        // A merge result that adds lines on top of two parents, the t4013
        // dir/sub shape: parent0 = "A\nB\nC\nD\nE\nF\n", parent1 = "A\nB\n1\n2\n",
        // result = "A\nB\nC\nD\nE\nF\n1\n2\n". git emits one combined hunk with
        // the `@@@ -1,6 -1,4 +1,8 @@@` header and two prefix columns.
        let p0 = b"A\nB\nC\nD\nE\nF\n";
        let p1 = b"A\nB\n1\n2\n";
        let result = b"A\nB\nC\nD\nE\nF\n1\n2\n";
        let text = render_cc(result, &[p0, p1], true);
        assert_eq!(
            text, "@@@ -1,6 -1,4 +1,8 @@@\n  A\n  B\n +C\n +D\n +E\n +F\n+ 1\n+ 2\n",
            "combined dense output:\n{text}",
        );
    }

    #[test]
    fn combined_identical_to_one_parent_dense_drops_hunk() {
        // When the result is identical to one parent, the dense (`--cc`) filter
        // drops the hunk (the change is "interesting" only against the other
        // parent), so nothing is emitted; the non-dense (`-c`) form still shows
        // every parent.
        let p0 = b"x\ny\n";
        let p1 = b"x\nCHANGED\n";
        let result = b"x\ny\n"; // identical to p0
        assert_eq!(render_cc(result, &[p0, p1], true), "");
        // Non-dense still shows the hunk (differs from p1).
        assert!(render_cc(result, &[p0, p1], false).starts_with("@@@"));
    }

    #[test]
    fn combined_reuse_identical_parents() {
        // Two parents with the identical blob must produce identical columns
        // (git's reuse_combine_diff path); the result adds a line relative to
        // both, so both columns carry `+`.
        let parent = b"a\nb\n";
        let result = b"a\nb\nc\n";
        let text = render_cc(result, &[parent, parent], true);
        assert_eq!(
            text, "@@@ -1,2 -1,2 +1,3 @@@\n  a\n  b\n++c\n",
            "reuse output:\n{text}",
        );
    }
}