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    let line_non_whitespace_lens: Vec<usize> = haystack_lines
304        .iter()
305        .map(|line| strip_reflow_whitespace(line).len())
306        .collect();
307    let mut matches = Vec::new();
308
309    for start in 0..haystack_lines.len() {
310        if !has_reflow_content(haystack_lines[start]) {
311            continue;
312        }
313
314        let mut window_non_whitespace_len = 0usize;
315        for end in (start + 1)..=haystack_lines.len() {
316            let line = haystack_lines[end - 1];
317            window_non_whitespace_len += line_non_whitespace_lens[end - 1];
318
319            if window_non_whitespace_len > max_non_whitespace {
320                break;
321            }
322            if window_non_whitespace_len < min_non_whitespace {
323                continue;
324            }
325            if !has_reflow_content(line) {
326                continue;
327            }
328
329            let window_text = haystack_lines[start..end].join("\n");
330            let window_non_whitespace = strip_reflow_whitespace(&window_text);
331            if window_non_whitespace != needle_non_whitespace {
332                continue;
333            }
334            if normalize_reflow_whitespace(&window_text) != normalized_needle {
335                continue;
336            }
337
338            let byte_start = line_offsets[start];
339            let byte_end = if end < line_offsets.len() {
340                line_offsets[end]
341            } else {
342                haystack.len()
343            };
344            matches.push(FuzzyMatch {
345                byte_start,
346                byte_len: byte_end - byte_start,
347                pass: 5,
348            });
349        }
350    }
351
352    matches
353}
354
355fn normalize_reflow_whitespace(s: &str) -> String {
356    let mut normalized = String::new();
357    let mut in_whitespace = false;
358
359    for c in s.trim().chars() {
360        if c.is_whitespace() {
361            in_whitespace = true;
362        } else {
363            if in_whitespace && !normalized.is_empty() {
364                normalized.push(' ');
365            }
366            normalized.push(c);
367            in_whitespace = false;
368        }
369    }
370
371    normalized
372}
373
374fn strip_reflow_whitespace(s: &str) -> String {
375    s.chars().filter(|c| !c.is_whitespace()).collect()
376}
377
378fn has_reflow_content(s: &str) -> bool {
379    s.chars().any(|c| !c.is_whitespace())
380}
381
382/// Normalize Unicode punctuation to ASCII equivalents.
383fn normalize_unicode(s: &str) -> String {
384    s.chars()
385        .map(|c| match c {
386            '\u{2018}' | '\u{2019}' | '\u{201A}' | '\u{201B}' => '\'',
387            '\u{201C}' | '\u{201D}' | '\u{201E}' | '\u{201F}' => '"',
388            '\u{2010}' | '\u{2011}' | '\u{2012}' | '\u{2013}' | '\u{2014}' | '\u{2015}' => '-',
389            '\u{00A0}' => ' ',
390            _ => c,
391        })
392        .collect::<String>()
393        .replace('\u{2026}', "...")
394}
395
396#[cfg(test)]
397mod tests {
398    use super::*;
399
400    #[test]
401    fn test_exact_match() {
402        let matches = find_all_fuzzy("hello world", "world");
403        assert_eq!(matches.len(), 1);
404        assert_eq!(matches[0].byte_start, 6);
405        assert_eq!(matches[0].pass, 1);
406    }
407
408    #[test]
409    fn test_exact_match_multiple() {
410        let matches = find_all_fuzzy("foo bar foo baz foo", "foo");
411        assert_eq!(matches.len(), 3);
412        assert_eq!(matches[0].byte_start, 0);
413        assert_eq!(matches[1].byte_start, 8);
414        assert_eq!(matches[2].byte_start, 16);
415    }
416
417    #[test]
418    fn test_rstrip_match() {
419        let source = "  hello  \n  world  \n";
420        let needle = "  hello\n  world";
421        let matches = find_all_fuzzy(source, needle);
422        assert_eq!(matches.len(), 1);
423        assert_eq!(matches[0].pass, 2); // rstrip pass
424    }
425
426    #[test]
427    fn test_trim_match() {
428        let source = "    function foo() {\n      return 1;\n    }\n";
429        let needle = "function foo() {\n  return 1;\n}";
430        let matches = find_all_fuzzy(source, needle);
431        assert_eq!(matches.len(), 1);
432        assert_eq!(matches[0].pass, 3); // trim pass
433    }
434
435    #[test]
436    fn test_unicode_normalize() {
437        let source = "let msg = \u{201C}hello\u{201D}\n";
438        let needle = "let msg = \"hello\"";
439        let matches = find_all_fuzzy(source, needle);
440        assert_eq!(matches.len(), 1);
441        assert_eq!(matches[0].pass, 4); // unicode pass
442    }
443
444    #[test]
445    fn test_unicode_normalize_multiline_variants() {
446        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";
447        let needle = "let title = \"hello\"...\nlet slug = foo-bar baz";
448        let matches = find_all_fuzzy(source, needle);
449
450        assert_eq!(matches.len(), 1);
451        assert_eq!(matches[0].pass, 4);
452        assert_eq!(matches[0].byte_start, source.find("  let title").unwrap());
453    }
454
455    #[test]
456    fn test_no_match() {
457        let matches = find_all_fuzzy("hello world", "xyz");
458        assert!(matches.is_empty());
459    }
460
461    #[test]
462    fn test_multiline_exact() {
463        let source = "line1\nline2\nline3\nline4\n";
464        let needle = "line2\nline3";
465        let matches = find_all_fuzzy(source, needle);
466        assert_eq!(matches.len(), 1);
467        assert_eq!(matches[0].byte_start, 6);
468        assert_eq!(matches[0].pass, 1);
469    }
470
471    #[test]
472    fn test_reflow_one_line_needle_matches_three_line_split() {
473        let source = "before\nlet total = alpha +\n    beta +\n    gamma;\nafter\n";
474        let needle = "let total = alpha + beta + gamma;";
475        let matches = find_all_fuzzy(source, needle);
476
477        assert_eq!(matches.len(), 1);
478        assert_eq!(matches[0].pass, 5);
479        assert_eq!(matches[0].byte_start, source.find("let total").unwrap());
480        assert_eq!(
481            &source[matches[0].byte_start..matches[0].byte_start + matches[0].byte_len],
482            "let total = alpha +\n    beta +\n    gamma;\n"
483        );
484    }
485
486    #[test]
487    fn test_reflow_three_line_needle_matches_one_line_join() {
488        let source = "before\nlet total = alpha + beta + gamma;\nafter\n";
489        let needle = "let total = alpha +\n    beta +\n    gamma;";
490        let matches = find_all_fuzzy(source, needle);
491
492        assert_eq!(matches.len(), 1);
493        assert_eq!(matches[0].pass, 5);
494        assert_eq!(matches[0].byte_start, source.find("let total").unwrap());
495        assert_eq!(
496            &source[matches[0].byte_start..matches[0].byte_start + matches[0].byte_len],
497            "let total = alpha + beta + gamma;\n"
498        );
499    }
500
501    #[test]
502    fn test_reflow_reports_all_ambiguous_windows() {
503        let source =
504            "let total = alpha +\n  beta +\n  gamma;\n\nlet total = alpha +\n  beta +\n  gamma;\n";
505        let needle = "let total = alpha + beta + gamma;";
506        let matches = find_all_fuzzy(source, needle);
507
508        assert_eq!(matches.len(), 2);
509        assert!(matches.iter().all(|m| m.pass == 5));
510    }
511
512    #[test]
513    fn test_reflow_near_miss_does_not_match() {
514        let source = "let total = alpha +\n  beta +\n  gamma;\n";
515        let needle = "let total = alpha + beta + delta;";
516        let matches = find_all_fuzzy(source, needle);
517
518        assert!(matches.is_empty());
519    }
520
521    #[test]
522    fn test_reflow_does_not_preempt_exact_match() {
523        let source = "let total = alpha +\n  beta +\n  gamma;\nlet total = alpha + beta + gamma;\n";
524        let needle = "let total = alpha + beta + gamma;";
525        let matches = find_all_fuzzy(source, needle);
526
527        assert_eq!(matches.len(), 1);
528        assert_eq!(matches[0].pass, 1);
529        assert_eq!(matches[0].byte_start, source.rfind("let total").unwrap());
530    }
531
532    #[test]
533    fn nearest_miss_renders_candidate_and_first_divergence() {
534        let source =
535            "fn calculate() {\n    let first = 1;\n    let actual = 2;\n    let last = 3;\n}\n";
536        let needle =
537            "fn calculate() {\n    let first = 1;\n    let expected = 2;\n    let last = 3;\n}";
538        let detail = render_nearest_miss_detail(source, needle);
539
540        assert!(detail.contains("Nearest candidate at lines 1-5"));
541        assert!(detail.contains("- expected:     let expected = 2;"));
542        assert!(detail.contains("+ actual:     let actual = 2;"));
543    }
544
545    #[test]
546    fn nearest_miss_below_floor_reports_only_line_count() {
547        let source = "function totallyDifferent() {\n    return 42;\n}\n";
548        let needle = "function target() {\n    return expected;\n}";
549        let detail = render_nearest_miss_detail(source, needle);
550
551        assert_eq!(detail, " (file has 3 lines)");
552    }
553
554    #[test]
555    fn nearest_miss_excerpt_middle_truncates_after_ten_lines() {
556        let source = (1..=12)
557            .map(|line| format!("line {line}"))
558            .collect::<Vec<_>>()
559            .join("\n");
560        let needle = (1..=12)
561            .map(|line| {
562                if line == 6 {
563                    "different line".to_string()
564                } else {
565                    format!("line {line}")
566                }
567            })
568            .collect::<Vec<_>>()
569            .join("\n");
570        let detail = render_nearest_miss_detail(&source, &needle);
571
572        assert!(detail.contains("middle candidate lines truncated"));
573        assert!(detail.contains("line 1"));
574        assert!(detail.contains("line 12"));
575        assert!(!detail.contains("line 6 |"));
576    }
577
578    #[test]
579    fn occurrence_listing_is_one_based_and_capped() {
580        let source = "same\n".repeat(10);
581        let positions = source
582            .match_indices("same")
583            .map(|(offset, _)| offset)
584            .collect::<Vec<_>>();
585        let detail = render_occurrence_listing(&source, &positions);
586
587        assert!(detail.starts_with(" 10 occurrences: #1 at line 1, #2 at line 2"));
588        assert!(detail.contains("#8 at line 8"));
589        assert!(detail.contains("… and 2 more"));
590        assert!(!detail.contains("#9 at line 9"));
591    }
592}
aft/fuzzy_match.rs

aft/
fuzzy_match.rs
