aft/
fuzzy_match.rs

1//! Fuzzy string matching for edit_match, inspired by opencode's 4-pass approach.
2//!
3//! When exact matching fails, progressively relaxes comparison:
4//!   Pass 1: Exact match (str::find / match_indices)
5//!   Pass 2: Trim trailing whitespace per line
6//!   Pass 3: Trim both ends per line
7//!   Pass 4: Normalize Unicode punctuation + trim
8//!   Pass 5: Reflowed line wraps/joins with whitespace-normalized content
9
10use crate::patch::matcher::{find_nearest_miss, NearestMissSearch};
11
12// A half-match floor keeps diagnostics useful for a likely stale edit while
13// suppressing suggestions for candidates that share too little of the needle.
14pub(crate) const NEAREST_MISS_SIMILARITY_FLOOR: f32 = 0.5;
15// Ten candidate lines provide context without turning an error into a file dump.
16pub(crate) const NEAREST_MISS_EXCERPT_LINES: usize = 10;
17// Eight occurrence entries are enough to choose a match while bounding error text.
18pub(crate) const AMBIGUOUS_OCCURRENCE_LIST_LIMIT: usize = 8;
19// Long generated lines need a byte-independent cap so one line cannot dominate the detail.
20pub(crate) const NEAREST_MISS_LINE_CHARS: usize = 240;
21
22/// A match result: byte offset in source and the matched byte length.
23#[derive(Debug, Clone)]
24pub struct FuzzyMatch {
25    pub byte_start: usize,
26    pub byte_len: usize,
27    /// Which pass found the match (1=exact, 2=rstrip, 3=trim, 4=unicode, 5=reflow)
28    pub pass: u8,
29}
30
31/// Find all occurrences of `needle` in `haystack` using progressive fuzzy matching.
32/// Returns matches in order of their byte position in the source.
33pub fn find_all_fuzzy(haystack: &str, needle: &str) -> Vec<FuzzyMatch> {
34    // Pass 1: exact match (fast path)
35    let exact: Vec<FuzzyMatch> = haystack
36        .match_indices(needle)
37        .map(|(idx, _)| FuzzyMatch {
38            byte_start: idx,
39            byte_len: needle.len(),
40            pass: 1,
41        })
42        .collect();
43
44    if !exact.is_empty() {
45        return exact;
46    }
47
48    // For fuzzy passes, work line-by-line
49    let needle_lines: Vec<&str> = needle.lines().collect();
50    if needle_lines.is_empty() {
51        return vec![];
52    }
53
54    let haystack_lines: Vec<&str> = haystack.lines().collect();
55    let line_byte_offsets = compute_line_offsets(haystack);
56
57    // Pass 2: rstrip (trim trailing whitespace)
58    let rstrip_matches = find_line_matches(
59        &haystack_lines,
60        &needle_lines,
61        &line_byte_offsets,
62        haystack,
63        |a, b| a.trim_end() == b.trim_end(),
64        2,
65    );
66    if !rstrip_matches.is_empty() {
67        return rstrip_matches;
68    }
69
70    // Pass 3: trim (both ends)
71    let trim_matches = find_line_matches(
72        &haystack_lines,
73        &needle_lines,
74        &line_byte_offsets,
75        haystack,
76        |a, b| a.trim() == b.trim(),
77        3,
78    );
79    if !trim_matches.is_empty() {
80        return trim_matches;
81    }
82
83    // Pass 4: normalized Unicode + trim. Normalize each line once instead of
84    // allocating inside the O(haystack_lines × needle_lines) comparison loop.
85    let normalized_haystack_lines: Vec<String> = haystack_lines
86        .iter()
87        .map(|line| normalize_unicode(line.trim()))
88        .collect();
89    let normalized_needle_lines: Vec<String> = needle_lines
90        .iter()
91        .map(|line| normalize_unicode(line.trim()))
92        .collect();
93    let normalized_haystack_refs: Vec<&str> = normalized_haystack_lines
94        .iter()
95        .map(String::as_str)
96        .collect();
97    let normalized_needle_refs: Vec<&str> =
98        normalized_needle_lines.iter().map(String::as_str).collect();
99    let normalized_matches = find_line_matches(
100        &normalized_haystack_refs,
101        &normalized_needle_refs,
102        &line_byte_offsets,
103        haystack,
104        |a, b| a == b,
105        4,
106    );
107    if !normalized_matches.is_empty() {
108        return normalized_matches;
109    }
110
111    // Pass 5: final fallback for formatter reflows. This pass deliberately
112    // runs only after every line-contiguous pass fails, and each candidate
113    // window must have the same non-whitespace content as the needle.
114    find_reflow_matches(&haystack_lines, &needle_lines, &line_byte_offsets, haystack)
115}
116
117pub(crate) fn render_nearest_miss_detail(source: &str, needle: &str) -> String {
118    let lines: Vec<&str> = source.lines().collect();
119    let pattern: Vec<&str> = needle.lines().collect();
120    let fallback = format!(" (file has {} lines)", lines.len());
121
122    let nearest = match find_nearest_miss(&lines, &pattern, source.len()) {
123        NearestMissSearch::Found(nearest) => nearest,
124        NearestMissSearch::NoSimilarRegion | NearestMissSearch::SkippedLargeFile => {
125            return fallback;
126        }
127    };
128    let similarity = nearest.matched_lines as f32 / pattern.len().max(1) as f32;
129    if similarity < NEAREST_MISS_SIMILARITY_FLOOR {
130        return fallback;
131    }
132
133    let start_line = nearest.start + 1;
134    let end_line = nearest.end;
135    let mut detail = format!("\nNearest candidate at lines {start_line}-{end_line}:");
136    let available_lines = nearest.end.saturating_sub(nearest.start);
137    let line_number_width = end_line.to_string().len();
138
139    if available_lines <= NEAREST_MISS_EXCERPT_LINES {
140        for (offset, line) in lines[nearest.start..nearest.end].iter().enumerate() {
141            append_diagnostic_line(&mut detail, nearest.start, offset, line, line_number_width);
142        }
143    } else {
144        let head_lines = NEAREST_MISS_EXCERPT_LINES / 2;
145        let tail_lines = NEAREST_MISS_EXCERPT_LINES - head_lines;
146        for (offset, line) in lines[nearest.start..nearest.start + head_lines]
147            .iter()
148            .enumerate()
149        {
150            append_diagnostic_line(&mut detail, nearest.start, offset, line, line_number_width);
151        }
152        detail.push_str("\n  ... (middle candidate lines truncated)");
153        for (offset, line) in lines[nearest.end - tail_lines..nearest.end]
154            .iter()
155            .enumerate()
156        {
157            append_diagnostic_line(
158                &mut detail,
159                nearest.start,
160                available_lines - tail_lines + offset,
161                line,
162                line_number_width,
163            );
164        }
165    }
166
167    let divergence = nearest.first_divergence;
168    let expected = pattern.get(divergence).copied().unwrap_or("<EOF>");
169    let actual = lines
170        .get(nearest.start + divergence)
171        .copied()
172        .unwrap_or("<EOF>");
173    detail.push_str(&format!(
174        "\nFirst divergence:\n- expected: {}\n+ actual: {}",
175        shorten_diagnostic_line(expected),
176        shorten_diagnostic_line(actual),
177    ));
178    detail
179}
180
181fn append_diagnostic_line(
182    detail: &mut String,
183    start: usize,
184    offset: usize,
185    line: &str,
186    line_number_width: usize,
187) {
188    let line_number = start + offset + 1;
189    detail.push_str(&format!(
190        "\n  {line_number:>line_number_width$} | {}",
191        shorten_diagnostic_line(line),
192        line_number_width = line_number_width,
193    ));
194}
195
196fn shorten_diagnostic_line(line: &str) -> String {
197    let chars = line.chars().collect::<Vec<_>>();
198    if chars.len() <= NEAREST_MISS_LINE_CHARS {
199        return line.to_string();
200    }
201
202    let head = NEAREST_MISS_LINE_CHARS / 2;
203    let tail = NEAREST_MISS_LINE_CHARS - head;
204    let mut shortened = chars[..head].iter().collect::<String>();
205    shortened.push('…');
206    shortened.extend(chars[chars.len() - tail..].iter());
207    shortened
208}
209
210/// Render a bounded 1-based occurrence list for an ambiguity error.
211pub(crate) fn render_occurrence_listing(source: &str, positions: &[usize]) -> String {
212    let listed = positions
213        .iter()
214        .take(AMBIGUOUS_OCCURRENCE_LIST_LIMIT)
215        .enumerate()
216        .map(|(index, position)| {
217            let line = source[0..*position].matches('\n').count() + 1;
218            format!("#{} at line {}", index + 1, line)
219        })
220        .collect::<Vec<_>>();
221    let mut detail = format!(" {} occurrences: {}", positions.len(), listed.join(", "));
222    if positions.len() > AMBIGUOUS_OCCURRENCE_LIST_LIMIT {
223        detail.push_str(&format!(
224            ", … and {} more",
225            positions.len() - AMBIGUOUS_OCCURRENCE_LIST_LIMIT
226        ));
227    }
228    detail
229}
230
231/// Compute byte offset of each line start in the source string.
232fn compute_line_offsets(source: &str) -> Vec<usize> {
233    let mut offsets = vec![0];
234    for (i, c) in source.char_indices() {
235        if c == '\n' && i + 1 <= source.len() {
236            offsets.push(i + 1);
237        }
238    }
239    offsets
240}
241
242/// Find all positions where `needle_lines` matches a contiguous sequence in `haystack_lines`.
243fn find_line_matches<F>(
244    haystack_lines: &[&str],
245    needle_lines: &[&str],
246    line_offsets: &[usize],
247    haystack: &str,
248    compare: F,
249    pass: u8,
250) -> Vec<FuzzyMatch>
251where
252    F: Fn(&str, &str) -> bool,
253{
254    let mut matches = Vec::new();
255    if needle_lines.len() > haystack_lines.len() {
256        return matches;
257    }
258
259    'outer: for i in 0..=(haystack_lines.len() - needle_lines.len()) {
260        for j in 0..needle_lines.len() {
261            if !compare(haystack_lines[i + j], needle_lines[j]) {
262                continue 'outer;
263            }
264        }
265        // Found a match at line `i` spanning `needle_lines.len()` lines
266        let byte_start = line_offsets[i];
267        let end_line = i + needle_lines.len();
268        let byte_end = if end_line < line_offsets.len() {
269            // Include the newline after the last matched line
270            line_offsets[end_line]
271        } else {
272            haystack.len()
273        };
274        matches.push(FuzzyMatch {
275            byte_start,
276            byte_len: byte_end - byte_start,
277            pass,
278        });
279    }
280
281    matches
282}
283
284const REFLOW_NON_WS_TOLERANCE: usize = 8;
285
286fn find_reflow_matches(
287    haystack_lines: &[&str],
288    needle_lines: &[&str],
289    line_offsets: &[usize],
290    haystack: &str,
291) -> Vec<FuzzyMatch> {
292    let needle_text = needle_lines.join("\n");
293    let normalized_needle = normalize_reflow_whitespace(&needle_text);
294    let needle_non_whitespace = strip_reflow_whitespace(&needle_text);
295    if normalized_needle.is_empty() || needle_non_whitespace.is_empty() {
296        return Vec::new();
297    }
298
299    let min_non_whitespace = needle_non_whitespace
300        .len()
301        .saturating_sub(REFLOW_NON_WS_TOLERANCE);
302    let max_non_whitespace = needle_non_whitespace.len() + REFLOW_NON_WS_TOLERANCE;
303    // The scan only needs byte lengths. Materializing a whitespace-stripped String
304    // for every source line made large generated-file misses allocate repeatedly.
305    let line_non_whitespace_lens = reflow_non_whitespace_lens(haystack_lines);
306    let mut matches = Vec::new();
307
308    for start in 0..haystack_lines.len() {
309        if !has_reflow_content(haystack_lines[start]) {
310            continue;
311        }
312
313        let mut window_non_whitespace_len = 0usize;
314        for end in (start + 1)..=haystack_lines.len() {
315            let line = haystack_lines[end - 1];
316            window_non_whitespace_len += line_non_whitespace_lens[end - 1];
317
318            if window_non_whitespace_len > max_non_whitespace {
319                break;
320            }
321            if window_non_whitespace_len < min_non_whitespace {
322                continue;
323            }
324            if !has_reflow_content(line) {
325                continue;
326            }
327
328            let window_text = haystack_lines[start..end].join("\n");
329            let window_non_whitespace = strip_reflow_whitespace(&window_text);
330            if window_non_whitespace != needle_non_whitespace {
331                continue;
332            }
333            if normalize_reflow_whitespace(&window_text) != normalized_needle {
334                continue;
335            }
336
337            let byte_start = line_offsets[start];
338            let byte_end = if end < line_offsets.len() {
339                line_offsets[end]
340            } else {
341                haystack.len()
342            };
343            matches.push(FuzzyMatch {
344                byte_start,
345                byte_len: byte_end - byte_start,
346                pass: 5,
347            });
348        }
349    }
350
351    matches
352}
353
354fn normalize_reflow_whitespace(s: &str) -> String {
355    let mut normalized = String::new();
356    let mut in_whitespace = false;
357
358    for c in s.trim().chars() {
359        if c.is_whitespace() {
360            in_whitespace = true;
361        } else {
362            if in_whitespace && !normalized.is_empty() {
363                normalized.push(' ');
364            }
365            normalized.push(c);
366            in_whitespace = false;
367        }
368    }
369
370    normalized
371}
372
373fn reflow_non_whitespace_lens(lines: &[&str]) -> Vec<usize> {
374    lines
375        .iter()
376        .map(|line| {
377            line.chars()
378                .filter(|character| !character.is_whitespace())
379                .map(char::len_utf8)
380                .sum()
381        })
382        .collect()
383}
384
385fn strip_reflow_whitespace(s: &str) -> String {
386    s.chars().filter(|c| !c.is_whitespace()).collect()
387}
388
389fn has_reflow_content(s: &str) -> bool {
390    s.chars().any(|c| !c.is_whitespace())
391}
392
393/// Normalize Unicode punctuation to ASCII equivalents.
394fn normalize_unicode(s: &str) -> String {
395    s.chars()
396        .map(|c| match c {
397            '\u{2018}' | '\u{2019}' | '\u{201A}' | '\u{201B}' => '\'',
398            '\u{201C}' | '\u{201D}' | '\u{201E}' | '\u{201F}' => '"',
399            '\u{2010}' | '\u{2011}' | '\u{2012}' | '\u{2013}' | '\u{2014}' | '\u{2015}' => '-',
400            '\u{00A0}' => ' ',
401            _ => c,
402        })
403        .collect::<String>()
404        .replace('\u{2026}', "...")
405}
406
407#[cfg(test)]
408mod tests {
409    use super::*;
410
411    #[test]
412    fn test_exact_match() {
413        let matches = find_all_fuzzy("hello world", "world");
414        assert_eq!(matches.len(), 1);
415        assert_eq!(matches[0].byte_start, 6);
416        assert_eq!(matches[0].pass, 1);
417    }
418
419    #[test]
420    fn test_exact_match_multiple() {
421        let matches = find_all_fuzzy("foo bar foo baz foo", "foo");
422        assert_eq!(matches.len(), 3);
423        assert_eq!(matches[0].byte_start, 0);
424        assert_eq!(matches[1].byte_start, 8);
425        assert_eq!(matches[2].byte_start, 16);
426    }
427
428    #[test]
429    fn test_rstrip_match() {
430        let source = "  hello  \n  world  \n";
431        let needle = "  hello\n  world";
432        let matches = find_all_fuzzy(source, needle);
433        assert_eq!(matches.len(), 1);
434        assert_eq!(matches[0].pass, 2); // rstrip pass
435    }
436
437    #[test]
438    fn test_trim_match() {
439        let source = "    function foo() {\n      return 1;\n    }\n";
440        let needle = "function foo() {\n  return 1;\n}";
441        let matches = find_all_fuzzy(source, needle);
442        assert_eq!(matches.len(), 1);
443        assert_eq!(matches[0].pass, 3); // trim pass
444    }
445
446    #[test]
447    fn test_unicode_normalize() {
448        let source = "let msg = \u{201C}hello\u{201D}\n";
449        let needle = "let msg = \"hello\"";
450        let matches = find_all_fuzzy(source, needle);
451        assert_eq!(matches.len(), 1);
452        assert_eq!(matches[0].pass, 4); // unicode pass
453    }
454
455    #[test]
456    fn test_unicode_normalize_multiline_variants() {
457        let source = "alpha\n  let title = \u{201C}hello\u{201D}\u{2026}\n  let slug = foo\u{2014}bar\u{00A0}baz\nomega\n";
458        let needle = "let title = \"hello\"...\nlet slug = foo-bar baz";
459        let matches = find_all_fuzzy(source, needle);
460
461        assert_eq!(matches.len(), 1);
462        assert_eq!(matches[0].pass, 4);
463        assert_eq!(matches[0].byte_start, source.find("  let title").unwrap());
464    }
465
466    #[test]
467    fn test_no_match() {
468        let matches = find_all_fuzzy("hello world", "xyz");
469        assert!(matches.is_empty());
470    }
471
472    #[test]
473    fn test_multiline_exact() {
474        let source = "line1\nline2\nline3\nline4\n";
475        let needle = "line2\nline3";
476        let matches = find_all_fuzzy(source, needle);
477        assert_eq!(matches.len(), 1);
478        assert_eq!(matches[0].byte_start, 6);
479        assert_eq!(matches[0].pass, 1);
480    }
481
482    #[test]
483    fn test_reflow_one_line_needle_matches_three_line_split() {
484        let source = "before\nlet total = alpha +\n    beta +\n    gamma;\nafter\n";
485        let needle = "let total = alpha + beta + gamma;";
486        let matches = find_all_fuzzy(source, needle);
487
488        assert_eq!(matches.len(), 1);
489        assert_eq!(matches[0].pass, 5);
490        assert_eq!(matches[0].byte_start, source.find("let total").unwrap());
491        assert_eq!(
492            &source[matches[0].byte_start..matches[0].byte_start + matches[0].byte_len],
493            "let total = alpha +\n    beta +\n    gamma;\n"
494        );
495    }
496
497    #[test]
498    fn test_reflow_three_line_needle_matches_one_line_join() {
499        let source = "before\nlet total = alpha + beta + gamma;\nafter\n";
500        let needle = "let total = alpha +\n    beta +\n    gamma;";
501        let matches = find_all_fuzzy(source, needle);
502
503        assert_eq!(matches.len(), 1);
504        assert_eq!(matches[0].pass, 5);
505        assert_eq!(matches[0].byte_start, source.find("let total").unwrap());
506        assert_eq!(
507            &source[matches[0].byte_start..matches[0].byte_start + matches[0].byte_len],
508            "let total = alpha + beta + gamma;\n"
509        );
510    }
511
512    #[test]
513    fn test_reflow_reports_all_ambiguous_windows() {
514        let source =
515            "let total = alpha +\n  beta +\n  gamma;\n\nlet total = alpha +\n  beta +\n  gamma;\n";
516        let needle = "let total = alpha + beta + gamma;";
517        let matches = find_all_fuzzy(source, needle);
518
519        assert_eq!(matches.len(), 2);
520        assert!(matches.iter().all(|m| m.pass == 5));
521    }
522
523    #[test]
524    fn test_reflow_near_miss_does_not_match() {
525        let source = "let total = alpha +\n  beta +\n  gamma;\n";
526        let needle = "let total = alpha + beta + delta;";
527        let matches = find_all_fuzzy(source, needle);
528
529        assert!(matches.is_empty());
530    }
531
532    #[test]
533    fn test_reflow_does_not_preempt_exact_match() {
534        let source = "let total = alpha +\n  beta +\n  gamma;\nlet total = alpha + beta + gamma;\n";
535        let needle = "let total = alpha + beta + gamma;";
536        let matches = find_all_fuzzy(source, needle);
537
538        assert_eq!(matches.len(), 1);
539        assert_eq!(matches[0].pass, 1);
540        assert_eq!(matches[0].byte_start, source.rfind("let total").unwrap());
541    }
542
543    #[test]
544    fn reflow_length_precomputation_allocates_only_the_result_vector() {
545        let line =
546            "export const generated = café\u{2003}+\t中 + padding_padding_padding_padding;\n";
547        let source = line.repeat(256);
548        let lines: Vec<&str> = source.lines().collect();
549        let expected: Vec<usize> = lines
550            .iter()
551            .map(|line| strip_reflow_whitespace(line).len())
552            .collect();
553
554        let (actual, allocations) =
555            crate::test_allocations::count(|| reflow_non_whitespace_lens(&lines));
556
557        assert_eq!(actual, expected);
558        assert_eq!(allocations, 1, "length precomputation allocated per line");
559    }
560
561    #[test]
562    fn nearest_miss_renders_candidate_and_first_divergence() {
563        let source =
564            "fn calculate() {\n    let first = 1;\n    let actual = 2;\n    let last = 3;\n}\n";
565        let needle =
566            "fn calculate() {\n    let first = 1;\n    let expected = 2;\n    let last = 3;\n}";
567        let detail = render_nearest_miss_detail(source, needle);
568
569        assert!(detail.contains("Nearest candidate at lines 1-5"));
570        assert!(detail.contains("- expected:     let expected = 2;"));
571        assert!(detail.contains("+ actual:     let actual = 2;"));
572    }
573
574    #[test]
575    fn nearest_miss_below_floor_reports_only_line_count() {
576        let source = "function totallyDifferent() {\n    return 42;\n}\n";
577        let needle = "function target() {\n    return expected;\n}";
578        let detail = render_nearest_miss_detail(source, needle);
579
580        assert_eq!(detail, " (file has 3 lines)");
581    }
582
583    #[test]
584    fn nearest_miss_excerpt_middle_truncates_after_ten_lines() {
585        let source = (1..=12)
586            .map(|line| format!("line {line}"))
587            .collect::<Vec<_>>()
588            .join("\n");
589        let needle = (1..=12)
590            .map(|line| {
591                if line == 6 {
592                    "different line".to_string()
593                } else {
594                    format!("line {line}")
595                }
596            })
597            .collect::<Vec<_>>()
598            .join("\n");
599        let detail = render_nearest_miss_detail(&source, &needle);
600
601        assert!(detail.contains("middle candidate lines truncated"));
602        assert!(detail.contains("line 1"));
603        assert!(detail.contains("line 12"));
604        assert!(!detail.contains("line 6 |"));
605    }
606
607    #[test]
608    fn occurrence_listing_is_one_based_and_capped() {
609        let source = "same\n".repeat(10);
610        let positions = source
611            .match_indices("same")
612            .map(|(offset, _)| offset)
613            .collect::<Vec<_>>();
614        let detail = render_occurrence_listing(&source, &positions);
615
616        assert!(detail.starts_with(" 10 occurrences: #1 at line 1, #2 at line 2"));
617        assert!(detail.contains("#8 at line 8"));
618        assert!(detail.contains("… and 2 more"));
619        assert!(!detail.contains("#9 at line 9"));
620    }
621}
aft/fuzzy_match.rs

aft/
fuzzy_match.rs
