Skip to main content

pixie_pi/tools/
edit_diff.rs

1//! Exact-replace edit application + unified-diff generation
2//! (`core/tools/edit-diff.ts`).
3
4use serde::{Deserialize, Serialize};
5
6/// One targeted replacement. `old_text` must match a unique, non-overlapping
7/// region of the original file.
8#[derive(Debug, Clone, Serialize, Deserialize)]
9pub struct Edit {
10    #[serde(rename = "oldText")]
11    pub old_text: String,
12    #[serde(rename = "newText")]
13    pub new_text: String,
14}
15
16#[derive(Debug, Clone, Copy, PartialEq, Eq)]
17pub enum LineEnding {
18    Lf,
19    Crlf,
20}
21
22/// Strip a UTF-8 BOM if present. Returns (bom, text).
23pub fn strip_bom(raw: &str) -> (String, String) {
24    if let Some(rest) = raw.strip_prefix('\u{FEFF}') {
25        ("\u{FEFF}".to_string(), rest.to_string())
26    } else {
27        (String::new(), raw.to_string())
28    }
29}
30
31pub fn detect_line_ending(s: &str) -> LineEnding {
32    if s.contains("\r\n") {
33        LineEnding::Crlf
34    } else {
35        LineEnding::Lf
36    }
37}
38
39/// Normalize all line endings to LF.
40pub fn normalize_to_lf(s: &str) -> String {
41    s.replace("\r\n", "\n").replace('\r', "\n")
42}
43
44/// Restore the original line ending style.
45pub fn restore_line_endings(s: &str, ending: LineEnding) -> String {
46    match ending {
47        LineEnding::Lf => s.to_string(),
48        LineEnding::Crlf => s.replace('\n', "\r\n"),
49    }
50}
51
52/// Normalize text for fuzzy matching, mirroring pi's `normalizeForFuzzyMatch`:
53/// NFKC-fold, strip per-line trailing whitespace, and fold smart quotes / dashes
54/// / special spaces to their ASCII equivalents. Lets an edit land when the
55/// model's `oldText` differs only in cosmetic whitespace or Unicode look-alikes.
56pub fn normalize_for_fuzzy_match(text: &str) -> String {
57    use unicode_normalization::UnicodeNormalization;
58    const SMART_APOSTROPHES: &[char] = &['\u{2018}', '\u{2019}', '\u{201A}', '\u{201B}'];
59    const SMART_QUOTES: &[char] = &['\u{201C}', '\u{201D}', '\u{201E}', '\u{201F}'];
60    const DASHES: &[char] = &['\u{2010}', '\u{2011}', '\u{2012}', '\u{2013}', '\u{2014}', '\u{2015}', '\u{2212}'];
61    const SPECIAL_SPACES: &[char] = &[
62        '\u{00A0}', '\u{2002}', '\u{2003}', '\u{2004}', '\u{2005}', '\u{2006}', '\u{2007}', '\u{2008}',
63        '\u{2009}', '\u{200A}', '\u{202F}', '\u{205F}', '\u{3000}',
64    ];
65    let nfkc: String = text.nfkc().collect();
66    let trimmed = nfkc
67        .split('\n')
68        .map(|line| line.trim_end())
69        .collect::<Vec<_>>()
70        .join("\n");
71    trimmed
72        .replace(SMART_APOSTROPHES, "'")
73        .replace(SMART_QUOTES, "\"")
74        .replace(DASHES, "-")
75        .replace(SPECIAL_SPACES, " ")
76}
77
78/// True when `old` is absent from `content` exactly but present after
79/// fuzzy-normalizing both — i.e. a fuzzy fallback would rescue this edit.
80fn fuzzy_needed(content: &str, old: &str) -> bool {
81    if content.find(old).is_some() {
82        return false;
83    }
84    let fo = normalize_for_fuzzy_match(old);
85    !fo.is_empty() && normalize_for_fuzzy_match(content).find(&fo).is_some()
86}
87
88/// Find `old` in `base`: exact match first (byte index + byte len), else a
89/// match in fuzzy-normalized space. Returns `(start, length)` in `base`'s
90/// coordinates. Mirrors pi's `fuzzyFindText`.
91fn find_in_base(base: &str, old: &str) -> Option<(usize, usize)> {
92    if let Some(i) = base.find(old) {
93        return Some((i, old.len()));
94    }
95    let fo = normalize_for_fuzzy_match(old);
96    if fo.is_empty() {
97        return None;
98    }
99    normalize_for_fuzzy_match(base)
100        .find(fo.as_str())
101        .map(|i| (i, fo.len()))
102}
103
104/// Occurrence count in fuzzy space. Mirrors pi's `countOccurrences`, which
105/// always normalizes — so two regions differing only in trailing whitespace (or
106/// Unicode look-alikes) count as duplicates and are rejected as ambiguous.
107fn count_occurrences(content: &str, old: &str) -> usize {
108    let fo = normalize_for_fuzzy_match(old);
109    if fo.is_empty() {
110        return 0;
111    }
112    normalize_for_fuzzy_match(content).matches(fo.as_str()).count()
113}
114
115/// Splice non-overlapping `(start, len, new_text)` spans into `base` in order.
116fn splice_replacements(base: &str, spans: &[(usize, usize, String)]) -> String {
117    let mut out = String::with_capacity(base.len());
118    let mut cursor = 0;
119    for (start, len, new_text) in spans {
120        out.push_str(&base[cursor..*start]);
121        out.push_str(new_text);
122        cursor = *start + *len;
123    }
124    out.push_str(&base[cursor..]);
125    out
126}
127
128/// Split `content` into lines, each keeping its trailing '\n' (the final line is
129/// included only if non-empty). Mirrors pi's `splitLinesWithEndings`.
130fn split_lines_with_endings(content: &str) -> Vec<&str> {
131    let mut out = Vec::new();
132    let mut start = 0;
133    for (i, b) in content.bytes().enumerate() {
134        if b == b'\n' {
135            out.push(&content[start..=i]);
136            start = i + 1;
137        }
138    }
139    if start < content.len() {
140        out.push(&content[start..]);
141    }
142    out
143}
144
145/// Cumulative `(start_byte, end_byte)` span of each line (with its ending).
146fn line_spans(content: &str) -> Vec<(usize, usize)> {
147    let mut spans = Vec::new();
148    let mut offset = 0;
149    for line in split_lines_with_endings(content) {
150        let end = offset + line.len();
151        spans.push((offset, end));
152        offset = end;
153    }
154    spans
155}
156
157/// The half-open `[start_line, end_line)` range of lines a `(start, len)`
158/// replacement touches, in `spans` coordinates. Mirrors `getReplacementLineRange`.
159fn replacement_line_range(spans: &[(usize, usize)], start: usize, len: usize) -> Option<(usize, usize)> {
160    let end = start + len;
161    let start_line = spans.iter().position(|(s, e)| *s <= start && start < *e)?;
162    let mut end_line = start_line;
163    while end_line < spans.len() && spans[end_line].1 < end {
164        end_line += 1;
165    }
166    Some((start_line, end_line + 1))
167}
168
169/// Apply `reps` (absolute base coords) within a sliced region of the base, in
170/// reverse order so earlier offsets stay valid. `offset` is the slice's start in
171/// base coords. Mirrors pi's `applyReplacements`.
172fn apply_replacements_in_slice(slice: &str, reps: &[&(usize, usize, String)], offset: usize) -> String {
173    let mut result = slice.to_string();
174    for (at, len, new_text) in reps.iter().rev() {
175        let rel_start = *at - offset;
176        let rel_end = rel_start + *len;
177        result = format!("{}{}{}", &result[..rel_start], new_text, &result[rel_end..]);
178    }
179    result
180}
181
182/// Overlay `replacements` (matched in the fuzzy-normalized `base`) onto the
183/// `original` content: only the lines a replacement touches are rewritten from
184/// the normalized base; every other line is copied byte-for-byte from the
185/// original. This is what makes fuzzy matching safe — NFKC / trailing-whitespace
186/// folding can never corrupt untouched lines. Mirrors pi's
187/// `applyReplacementsPreservingUnchangedLines`.
188fn apply_replacements_preserving_unchanged_lines(
189    original: &str,
190    base: &str,
191    replacements: &[(usize, usize, String)],
192) -> String {
193    let original_lines = split_lines_with_endings(original);
194    let base_spans = line_spans(base);
195    // Fuzzy normalization only changes within-line bytes, never the line count,
196    // so the two line views stay aligned one-to-one. (If they ever diverged,
197    // overlaying would misalign — fall back to the original in that case.)
198    if original_lines.len() != base_spans.len() {
199        return original.to_string();
200    }
201
202    // Group replacements whose touched line-ranges overlap or abut.
203    type RepRef<'a> = &'a (usize, usize, String);
204    let mut sorted: Vec<RepRef<'_>> = replacements.iter().collect();
205    sorted.sort_by_key(|r| r.0);
206    let mut groups: Vec<(usize, usize, Vec<RepRef<'_>>)> = Vec::new();
207    for rep in &sorted {
208        let Some((sl, el)) = replacement_line_range(&base_spans, rep.0, rep.1) else {
209            continue;
210        };
211        if let Some(last) = groups.last_mut() {
212            if sl < last.1 {
213                last.1 = last.1.max(el);
214                last.2.push(*rep);
215                continue;
216            }
217        }
218        groups.push((sl, el, vec![*rep]));
219    }
220
221    let mut result = String::new();
222    let mut original_line_idx = 0usize;
223    for (start_line, end_line, group_reps) in &groups {
224        result.extend(original_lines[original_line_idx..*start_line].iter().copied());
225        let group_start_offset = base_spans[*start_line].0;
226        let group_end_offset = base_spans[*end_line - 1].1;
227        let slice = &base[group_start_offset..group_end_offset];
228        result.push_str(&apply_replacements_in_slice(slice, group_reps, group_start_offset));
229        original_line_idx = *end_line;
230    }
231    result.extend(original_lines[original_line_idx..].iter().copied());
232    result
233}
234
235/// Apply a set of edits to LF-normalized content. Each `old_text` is matched
236/// against the original (not incrementally); edits must be unique and
237/// non-overlapping. As a fallback, when an exact match fails the search retries
238/// in fuzzy-normalized space (mirrors pi's `applyEditsToNormalizedContent`). If
239/// any edit needs fuzzy matching, all edits are applied in that space and then
240/// overlaid onto the original line-by-line so untouched lines keep their bytes.
241/// Returns `(base, new)` for diffing.
242pub fn apply_edits(content: &str, edits: &[Edit], path: &str) -> anyhow::Result<(String, String)> {
243    // Normalize each edit's search/replace text to LF: the file content is
244    // already LF-normalized by the caller before matching, so a CRLF oldText
245    // (copied by the model from a CRLF file) would never match, and a CRLF
246    // newText would produce `\r\r\n` when line endings are restored.
247    let normalized_edits: Vec<(String, String)> = edits
248        .iter()
249        .map(|e| (normalize_to_lf(&e.old_text), normalize_to_lf(&e.new_text)))
250        .collect();
251    for (old, _) in &normalized_edits {
252        if old.is_empty() {
253            anyhow::bail!("Could not edit file: {path}. An edits[].oldText is empty.");
254        }
255    }
256
257    // If ANY edit fails the exact match but hits in fuzzy space, run the whole
258    // edit set in fuzzy space — you can't mix offsets across the two spaces —
259    // then overlay onto the original so unchanged lines keep their exact bytes.
260    let used_fuzzy = normalized_edits.iter().any(|(old, _)| fuzzy_needed(content, old));
261    let replacement_base: String = if used_fuzzy {
262        normalize_for_fuzzy_match(content)
263    } else {
264        content.to_string()
265    };
266
267    // Locate each edit's byte span in the replacement base.
268    let mut spans: Vec<(usize, usize, String)> = Vec::new(); // (start, len, new_text)
269    for (old, new) in &normalized_edits {
270        let Some((start, mlen)) = find_in_base(&replacement_base, old) else {
271            anyhow::bail!(
272                "Could not edit file: {path}. The oldText was not found. Make sure oldText matches the file exactly (including indentation and whitespace)."
273            );
274        };
275        let occ = count_occurrences(&replacement_base, old);
276        if occ > 1 {
277            anyhow::bail!(
278                "Could not edit file: {path}. The oldText is not unique (found {occ} matches). Include more surrounding context so oldText matches exactly one location."
279            );
280        }
281        spans.push((start, mlen, new.clone()));
282    }
283
284    // Sort by start position and reject overlaps.
285    spans.sort_by_key(|(s, _, _)| *s);
286    for window in spans.windows(2) {
287        let (a_start, a_len, _) = &window[0];
288        let (b_start, _, _) = &window[1];
289        if *b_start < *a_start + *a_len {
290            anyhow::bail!(
291                "Could not edit file: {path}. Overlapping or nested edits are not allowed. Merge nearby changes into a single edit."
292            );
293        }
294    }
295
296    let new_content = if used_fuzzy {
297        apply_replacements_preserving_unchanged_lines(content, &replacement_base, &spans)
298    } else {
299        splice_replacements(&replacement_base, &spans)
300    };
301
302    Ok((content.to_string(), new_content))
303}
304
305/// Generate a unified diff between two strings (line-based, 3 lines of
306/// context). Returns `(diff_string, first_changed_line)` where
307/// `first_changed_line` is 1-indexed in the new file.
308pub fn generate_diff(base: &str, new: &str, path: &str) -> (String, Option<usize>) {
309    // Split on '\n' but drop the trailing empty element produced when the
310    // content ends with a newline (otherwise the last hunk carries a phantom
311    // empty context line and an off-by-one line count).
312    let mut base_lines: Vec<&str> = base.split('\n').collect();
313    if base.ends_with('\n') {
314        base_lines.pop();
315    }
316    let mut new_lines: Vec<&str> = new.split('\n').collect();
317    if new.ends_with('\n') {
318        new_lines.pop();
319    }
320
321    let ops = diff_lines(&base_lines, &new_lines);
322    if ops.iter().all(|o| matches!(o, DiffOp::Equal(_))) {
323        return (String::new(), None);
324    }
325
326    let context = 3;
327    let hunks = group_hunks(&ops, context);
328
329    let mut out = String::new();
330    out.push_str(&format!("--- {path}\n+++ {path}\n"));
331    let mut first_changed_line: Option<usize> = None;
332    // Cumulative line counters across all preceding ops.
333    let mut old_prefix = 0usize;
334    let mut new_prefix = 0usize;
335    let mut consumed = 0usize;
336
337    for hunk in &hunks {
338        // Advance counters over the ops before this hunk.
339        for op in &ops[consumed..hunk.start] {
340            match op {
341                DiffOp::Equal(_) => {
342                    old_prefix += 1;
343                    new_prefix += 1;
344                }
345                DiffOp::Delete(_) => old_prefix += 1,
346                DiffOp::Insert(_) => new_prefix += 1,
347            }
348        }
349        consumed = hunk.end;
350
351        let old_start = old_prefix + 1;
352        let new_start = new_prefix + 1;
353        let (mut old_count, mut new_count) = (0usize, 0usize);
354        let mut new_cursor = new_prefix;
355        let mut body = String::new();
356        for op in &ops[hunk.start..hunk.end] {
357            match op {
358                DiffOp::Equal(l) => {
359                    body.push_str(&format!(" {l}\n"));
360                    old_count += 1;
361                    new_count += 1;
362                    new_cursor += 1;
363                }
364                DiffOp::Delete(l) => {
365                    if first_changed_line.is_none() {
366                        first_changed_line = Some(new_cursor + 1);
367                    }
368                    body.push_str(&format!("-{l}\n"));
369                    old_count += 1;
370                }
371                DiffOp::Insert(l) => {
372                    if first_changed_line.is_none() {
373                        first_changed_line = Some(new_cursor + 1);
374                    }
375                    body.push_str(&format!("+{l}\n"));
376                    new_count += 1;
377                    new_cursor += 1;
378                }
379            }
380        }
381        // Advance the running counters over this hunk's body so the next hunk
382        // computes its `@@ -start +start @@` line numbers relative to the true
383        // position in the file. (Without this, only inter-hunk gaps were counted
384        // and every hunk after the first reported stale, too-small line numbers.)
385        old_prefix += old_count;
386        new_prefix += new_count;
387        out.push_str(&format!(
388            "@@ -{},{} +{},{} @@\n{}",
389            old_start,
390            old_count.max(1),
391            new_start,
392            new_count.max(1),
393            body
394        ));
395    }
396    (out, first_changed_line)
397}
398
399#[derive(Debug, Clone, Copy)]
400enum DiffOp<'a> {
401    Equal(&'a str),
402    Delete(&'a str),
403    Insert(&'a str),
404}
405
406fn is_change(op: &DiffOp) -> bool {
407    matches!(op, DiffOp::Delete(_) | DiffOp::Insert(_))
408}
409
410struct HunkRange {
411    start: usize,
412    end: usize,
413}
414
415/// Partition `ops` into maximal runs of ops that lie within `context` ops of a
416/// change. Returns half-open `[start, end)` ranges.
417fn group_hunks(ops: &[DiffOp], context: usize) -> Vec<HunkRange> {
418    let n = ops.len();
419    let in_hunk: Vec<bool> = (0..n)
420        .map(|i| {
421            let lo = i.saturating_sub(context);
422            let hi = (i + context + 1).min(n);
423            ops[lo..hi].iter().any(is_change)
424        })
425        .collect();
426
427    let mut hunks = Vec::new();
428    let mut i = 0;
429    while i < n {
430        if in_hunk[i] {
431            let start = i;
432            while i < n && in_hunk[i] {
433                i += 1;
434            }
435            hunks.push(HunkRange { start, end: i });
436        } else {
437            i += 1;
438        }
439    }
440    hunks
441}
442
443/// Classic LCS line diff.
444///
445/// The LCS DP is O(n·m) in time *and* memory, and `generate_diff` runs it on the
446/// **whole** file after every edit. To keep an edit to a large file from
447/// allocating a multi-gigabyte table, we first strip the common leading and
448/// trailing lines — which a full LCS would only ever match as `Equal` anyway, so
449/// the resulting op sequence is identical — and run the DP over just the changed
450/// middle. For the pathological case where that middle is itself enormous (a
451/// full rewrite of a huge file), a cell-budget guard skips the DP and emits a
452/// coarse delete/insert hunk; the diff is cosmetic model feedback, so that is
453/// preferable to hanging or OOMing the agent mid-edit.
454fn diff_lines<'a>(a: &[&'a str], b: &[&'a str]) -> Vec<DiffOp<'a>> {
455    // Common leading lines.
456    let mut prefix = 0;
457    while prefix < a.len() && prefix < b.len() && a[prefix] == b[prefix] {
458        prefix += 1;
459    }
460    // Common trailing lines, kept from overlapping the prefix.
461    let mut suffix = 0;
462    while prefix + suffix < a.len()
463        && prefix + suffix < b.len()
464        && a[a.len() - 1 - suffix] == b[b.len() - 1 - suffix]
465    {
466        suffix += 1;
467    }
468
469    let mid_a = &a[prefix..a.len() - suffix];
470    let mid_b = &b[prefix..b.len() - suffix];
471
472    let mut ops = Vec::with_capacity(a.len() + b.len());
473    for l in &a[..prefix] {
474        ops.push(DiffOp::Equal(l));
475    }
476    ops.extend(diff_middle(mid_a, mid_b));
477    for l in &a[a.len() - suffix..] {
478        ops.push(DiffOp::Equal(l));
479    }
480    ops
481}
482
483/// LCS the changed middle, with a cell-budget guard against pathological inputs.
484fn diff_middle<'a>(a: &[&'a str], b: &[&'a str]) -> Vec<DiffOp<'a>> {
485    /// Max LCS-table cells we are willing to allocate (~16 MiB of `usize`).
486    const DP_CELL_BUDGET: usize = 2_000_000;
487    let n = a.len();
488    let m = b.len();
489
490    // Over budget (or the product would overflow): skip the DP and emit a coarse
491    // delete-old / insert-new diff. Memory is bounded to the ops vec — no OOM.
492    if n.checked_mul(m).is_none_or(|c| c > DP_CELL_BUDGET) {
493        let mut ops = Vec::with_capacity(n + m);
494        for l in a {
495            ops.push(DiffOp::Delete(l));
496        }
497        for l in b {
498            ops.push(DiffOp::Insert(l));
499        }
500        return ops;
501    }
502
503    let mut dp = vec![vec![0usize; m + 1]; n + 1];
504    for i in (0..n).rev() {
505        for j in (0..m).rev() {
506            dp[i][j] = if a[i] == b[j] {
507                dp[i + 1][j + 1] + 1
508            } else {
509                dp[i + 1][j].max(dp[i][j + 1])
510            };
511        }
512    }
513
514    let mut ops = Vec::new();
515    let (mut i, mut j) = (0, 0);
516    while i < n && j < m {
517        if a[i] == b[j] {
518            ops.push(DiffOp::Equal(a[i]));
519            i += 1;
520            j += 1;
521        } else if dp[i + 1][j] >= dp[i][j + 1] {
522            ops.push(DiffOp::Delete(a[i]));
523            i += 1;
524        } else {
525            ops.push(DiffOp::Insert(b[j]));
526            j += 1;
527        }
528    }
529    while i < n {
530        ops.push(DiffOp::Delete(a[i]));
531        i += 1;
532    }
533    while j < m {
534        ops.push(DiffOp::Insert(b[j]));
535        j += 1;
536    }
537    ops
538}
539
540#[cfg(test)]
541mod tests {
542    use super::*;
543
544    #[test]
545    fn applies_unique_non_overlapping_edits() {
546        let content = "fn main() {\n    let x = 1;\n    let y = 2;\n}\n";
547        let edits = vec![
548            Edit {
549                old_text: "let x = 1;".into(),
550                new_text: "let x = 42;".into(),
551            },
552            Edit {
553                old_text: "let y = 2;".into(),
554                new_text: "let y = 99;".into(),
555            },
556        ];
557        let (base, new) = apply_edits(content, &edits, "f.rs").unwrap();
558        assert!(new.contains("let x = 42;"));
559        assert!(new.contains("let y = 99;"));
560        assert!(!base.contains("let x = 42;"));
561    }
562
563    #[test]
564    fn rejects_non_unique_oldtext() {
565        let content = "a\na\n";
566        let edits = vec![Edit {
567            old_text: "a".into(),
568            new_text: "b".into(),
569        }];
570        let err = apply_edits(content, &edits, "f").unwrap_err();
571        assert!(format!("{err}").contains("not unique"));
572    }
573
574    #[test]
575    fn rejects_overlapping_edits() {
576        let content = "abcdef";
577        let edits = vec![
578            Edit {
579                old_text: "abcd".into(),
580                new_text: "X".into(),
581            },
582            Edit {
583                old_text: "cdef".into(),
584                new_text: "Y".into(),
585            },
586        ];
587        let err = apply_edits(content, &edits, "f").unwrap_err();
588        assert!(format!("{err}").contains("Overlap"));
589    }
590
591    #[test]
592    fn fuzzy_rescues_trailing_whitespace_and_preserves_untouched_lines() {
593        // The file's `foo  ` line has trailing spaces the model omitted from
594        // oldText ("foo\nbar"), so the exact match fails. Fuzzy (per-line
595        // trim_end) rescues it. Crucially, only the touched lines are rewritten
596        // from the normalized base; the untouched `header` / `footer` lines must
597        // keep their original trailing whitespace byte-for-byte.
598        let content = "header   \nfoo  \nbar\nfooter   \n";
599        let edits = vec![Edit {
600            old_text: "foo\nbar".into(),
601            new_text: "REPLACED".into(),
602        }];
603        let (base, new) = apply_edits(content, &edits, "f.rs").unwrap();
604        // Only the touched `foo  \nbar` region is rewritten; the untouched
605        // `header` and `footer` lines keep their trailing whitespace verbatim.
606        assert_eq!(
607            new, "header   \nREPLACED\nfooter   \n",
608            "fuzzy edit must replace only the touched lines: {new:?}"
609        );
610        assert_eq!(base, content, "base is the original content");
611    }
612
613    #[test]
614    fn fuzzy_rescues_smart_quotes_and_dashes() {
615        // File uses a smart apostrophe (') and em dash (—); oldText uses straight
616        // quotes / hyphen. Fuzzy normalization folds both, so the edit lands.
617        let content = "it\u{2019}s here\u{2014}now\n";
618        let edits = vec![Edit {
619            old_text: "it's here-now".into(),
620            new_text: "done".into(),
621        }];
622        let (_base, new) = apply_edits(content, &edits, "f").unwrap();
623        assert!(new.contains("done"), "{new}");
624    }
625
626    #[test]
627    fn fuzzy_count_rejects_whitespace_only_duplicate() {
628        // oldText "foo" matches `foo   ` exactly, but the file has a second
629        // `foo` line — count_occurrences normalizes, so it sees 2 and rejects as
630        // ambiguous rather than silently editing the first.
631        let content = "foo   \nfoo\n";
632        let edits = vec![Edit {
633            old_text: "foo".into(),
634            new_text: "bar".into(),
635        }];
636        let err = apply_edits(content, &edits, "f").unwrap_err();
637        assert!(format!("{err}").contains("not unique"), "{err}");
638        assert!(format!("{err}").contains("2 matches"), "{err}");
639    }
640
641    #[test]
642    fn fuzzy_genuinely_absent_oldtext_still_errors() {
643        // Not in the file even after normalization → must error, not silently no-op.
644        let content = "hello world\n";
645        let edits = vec![Edit {
646            old_text: "missing".into(),
647            new_text: "x".into(),
648        }];
649        let err = apply_edits(content, &edits, "f").unwrap_err();
650        assert!(format!("{err}").contains("was not found"), "{err}");
651    }
652
653    #[test]
654    fn diff_shows_changes() {
655        let (diff, first) = generate_diff("a\nb\nc\n", "a\nB\nc\n", "f");
656        assert!(diff.contains("-b"));
657        assert!(diff.contains("+B"));
658        assert_eq!(first, Some(2));
659    }
660
661    #[test]
662    fn matches_crlf_oldtext() {
663        // The file content is LF-normalized by the caller before matching; the
664        // search text is normalized too, so a model that echoes CRLF still hits.
665        let normalized = normalize_to_lf("a\r\nb\r\n");
666        let edits = vec![Edit {
667            old_text: "a\r\nb".into(),
668            new_text: "c\nd".into(),
669        }];
670        let (_, new) = apply_edits(&normalized, &edits, "f").unwrap();
671        assert!(new.contains("c\nd"));
672    }
673
674    #[test]
675    fn crlf_restore_has_no_doubled_carriage_returns() {
676        let normalized = normalize_to_lf("fn main() {\r\n    let x = 1;\r\n}\r\n");
677        let edits = vec![Edit {
678            old_text: "let x = 1;".into(),
679            new_text: "let x = 2;\n    let y = 3;".into(),
680        }];
681        let (_, new_normalized) = apply_edits(&normalized, &edits, "f.rs").unwrap();
682        let restored = restore_line_endings(&new_normalized, LineEnding::Crlf);
683        assert!(!restored.contains("\r\r"), "doubled CR after restore");
684        assert_eq!(
685            restored,
686            "fn main() {\r\n    let x = 2;\r\n    let y = 3;\r\n}\r\n"
687        );
688    }
689
690    #[test]
691    fn multihunk_diff_has_correct_line_numbers() {
692        // Two single-line changes 10 lines apart produce two hunks. The second
693        // hunk's change is at line 11; with 3 lines of context it must start at
694        // line 8 in both old and new files. (Previously the 2nd hunk header read
695        // `-4,5` because the running line counters were never advanced over a
696        // hunk's own body — only over the gap before it.)
697        let base = "1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n11\n";
698        let new = "X\n2\n3\n4\n5\n6\n7\n8\n9\n10\nY\n";
699        let (diff, first) = generate_diff(base, new, "f");
700        assert!(
701            diff.contains("@@ -8,4 +8,4 @@"),
702            "second hunk header should be @@ -8,4 +8,4 @@\ngot:\n{diff}"
703        );
704        assert_eq!(first, Some(1));
705        // No phantom empty trailing context line from the final newline.
706        assert!(
707            !diff.ends_with(" \n"),
708            "diff should not end with a spurious empty context line, got:\n{diff:?}"
709        );
710    }
711
712    #[test]
713    fn small_edit_in_a_large_file_produces_a_focused_diff() {
714        // One line changed in a 2000-line file. The common prefix/suffix must be
715        // stripped before the LCS so the DP runs over a 1×1 middle, not 2000×2000
716        // (4M cells). The diff is the same a full LCS would emit: one focused
717        // hunk around the change. The far-away unchanged lines must NOT appear.
718        let base: String = (0..2000)
719            .map(|i| format!("line-{i}"))
720            .collect::<Vec<_>>()
721            .join("\n")
722            + "\n";
723        let new = {
724            let mut lines: Vec<String> = (0..2000).map(|i| format!("line-{i}")).collect();
725            lines[1234] = "line-1234-CHANGED".into();
726            lines.join("\n") + "\n"
727        };
728        let (diff, first) = generate_diff(&base, &new, "f");
729        assert_eq!(first, Some(1235), "first changed line is line 1235 (1-indexed)");
730        assert!(diff.contains("-line-1234\n"), "{diff}");
731        assert!(diff.contains("+line-1234-CHANGED\n"), "{diff}");
732        assert!(
733            diff.contains("@@ -1232,7 +1232,7 @@\n"),
734            "expected a single focused hunk header, got:\n{diff}"
735        );
736        // Unchanged lines far from the edit must be absent.
737        assert!(!diff.contains("line-0\n"));
738        assert!(!diff.contains("line-1999\n"));
739    }
740
741    #[test]
742    fn large_full_rewrite_uses_the_bounded_fallback() {
743        // Every line differs, so the changed middle is 2000×2000 = 4M cells —
744        // over the DP budget. The LCS table must NOT be built; the fallback emits
745        // a coarse delete-old / insert-new hunk and returns bounded output
746        // without allocating (and without OOMing on a genuinely huge rewrite).
747        let base: String = (0..2000).map(|i| format!("old-{i}\n")).collect();
748        let new: String = (0..2000).map(|i| format!("new-{i}\n")).collect();
749        let (diff, first) = generate_diff(&base, &new, "big.txt");
750        assert!(diff.starts_with("--- big.txt\n+++ big.txt\n"), "{diff}");
751        assert_eq!(first, Some(1));
752        // Coarse fallback: all old lines deleted, all new lines inserted.
753        assert!(diff.contains("-old-0\n"), "{diff}");
754        assert!(diff.contains("+new-0\n"), "{diff}");
755    }
756}