1use language::{Point, TextBufferSnapshot};
2use std::{cmp, ops::Range};
3
4const REPLACEMENT_COST: u32 = 1;
5const INSERTION_COST: u32 = 3;
6const DELETION_COST: u32 = 10;
7
8/// A streaming fuzzy matcher that can process text chunks incrementally
9/// and return the best match found so far at each step.
10pub struct StreamingFuzzyMatcher {
11 snapshot: TextBufferSnapshot,
12 query_lines: Vec<String>,
13 line_hint: Option<u32>,
14 incomplete_line: String,
15 matches: Vec<Range<usize>>,
16 matrix: SearchMatrix,
17}
18
19impl StreamingFuzzyMatcher {
20 pub fn new(snapshot: TextBufferSnapshot) -> Self {
21 let buffer_line_count = snapshot.max_point().row as usize + 1;
22 Self {
23 snapshot,
24 query_lines: Vec::new(),
25 line_hint: None,
26 incomplete_line: String::new(),
27 matches: Vec::new(),
28 matrix: SearchMatrix::new(buffer_line_count + 1),
29 }
30 }
31
32 /// Returns the query lines.
33 pub fn query_lines(&self) -> &[String] {
34 &self.query_lines
35 }
36
37 /// Push a new chunk of text and get the best match found so far.
38 ///
39 /// This method accumulates text chunks and processes complete lines.
40 /// Partial lines are buffered internally until a newline is received.
41 ///
42 /// # Returns
43 ///
44 /// Returns `Some(range)` if a match has been found with the accumulated
45 /// query so far, or `None` if no suitable match exists yet.
46 pub fn push(&mut self, chunk: &str, line_hint: Option<u32>) -> Option<Range<usize>> {
47 if line_hint.is_some() {
48 self.line_hint = line_hint;
49 }
50
51 // Add the chunk to our incomplete line buffer
52 self.incomplete_line.push_str(chunk);
53 self.line_hint = line_hint;
54
55 if let Some((last_pos, _)) = self.incomplete_line.match_indices('\n').next_back() {
56 let complete_part = &self.incomplete_line[..=last_pos];
57
58 // Split into lines and add to query_lines
59 for line in complete_part.lines() {
60 self.query_lines.push(line.to_string());
61 }
62
63 self.incomplete_line.replace_range(..last_pos + 1, "");
64
65 self.matches = self.resolve_location_fuzzy();
66 }
67
68 let best_match = self.select_best_match();
69 best_match.or_else(|| self.matches.first().cloned())
70 }
71
72 /// Finish processing and return the final best match(es).
73 ///
74 /// This processes any remaining incomplete line before returning the final
75 /// match result.
76 pub fn finish(&mut self) -> Vec<Range<usize>> {
77 // Process any remaining incomplete line
78 if !self.incomplete_line.is_empty() {
79 self.query_lines.push(self.incomplete_line.clone());
80 self.incomplete_line.clear();
81 self.matches = self.resolve_location_fuzzy();
82 }
83 self.matches.clone()
84 }
85
86 fn resolve_location_fuzzy(&mut self) -> Vec<Range<usize>> {
87 let new_query_line_count = self.query_lines.len();
88 let old_query_line_count = self.matrix.rows.saturating_sub(1);
89 if new_query_line_count == old_query_line_count {
90 return Vec::new();
91 }
92
93 self.matrix.resize_rows(new_query_line_count + 1);
94
95 // Process only the new query lines
96 for row in old_query_line_count..new_query_line_count {
97 let query_line = self.query_lines[row].trim();
98 let leading_deletion_cost = (row + 1) as u32 * DELETION_COST;
99
100 self.matrix.set(
101 row + 1,
102 0,
103 SearchState::new(leading_deletion_cost, SearchDirection::Up),
104 );
105
106 let mut buffer_lines = self.snapshot.as_rope().chunks().lines();
107 let mut col = 0;
108 while let Some(buffer_line) = buffer_lines.next() {
109 let buffer_line = buffer_line.trim();
110 let up = SearchState::new(
111 self.matrix
112 .get(row, col + 1)
113 .cost
114 .saturating_add(DELETION_COST),
115 SearchDirection::Up,
116 );
117 let left = SearchState::new(
118 self.matrix
119 .get(row + 1, col)
120 .cost
121 .saturating_add(INSERTION_COST),
122 SearchDirection::Left,
123 );
124 let diagonal = SearchState::new(
125 if query_line == buffer_line {
126 self.matrix.get(row, col).cost
127 } else if fuzzy_eq(query_line, buffer_line) {
128 self.matrix.get(row, col).cost + REPLACEMENT_COST
129 } else {
130 self.matrix
131 .get(row, col)
132 .cost
133 .saturating_add(DELETION_COST + INSERTION_COST)
134 },
135 SearchDirection::Diagonal,
136 );
137 self.matrix
138 .set(row + 1, col + 1, up.min(left).min(diagonal));
139 col += 1;
140 }
141 }
142
143 // Find all matches with the best cost
144 let buffer_line_count = self.snapshot.max_point().row as usize + 1;
145 let mut best_cost = u32::MAX;
146 let mut matches_with_best_cost = Vec::new();
147
148 for col in 1..=buffer_line_count {
149 let cost = self.matrix.get(new_query_line_count, col).cost;
150 if cost < best_cost {
151 best_cost = cost;
152 matches_with_best_cost.clear();
153 matches_with_best_cost.push(col as u32);
154 } else if cost == best_cost {
155 matches_with_best_cost.push(col as u32);
156 }
157 }
158
159 // Find ranges for the matches
160 let mut valid_matches = Vec::new();
161 for &buffer_row_end in &matches_with_best_cost {
162 let mut matched_lines = 0;
163 let mut query_row = new_query_line_count;
164 let mut buffer_row_start = buffer_row_end;
165 while query_row > 0 && buffer_row_start > 0 {
166 let current = self.matrix.get(query_row, buffer_row_start as usize);
167 match current.direction {
168 SearchDirection::Diagonal => {
169 query_row -= 1;
170 buffer_row_start -= 1;
171 matched_lines += 1;
172 }
173 SearchDirection::Up => {
174 query_row -= 1;
175 }
176 SearchDirection::Left => {
177 buffer_row_start -= 1;
178 }
179 }
180 }
181
182 let matched_buffer_row_count = buffer_row_end - buffer_row_start;
183 let matched_ratio = matched_lines as f32
184 / (matched_buffer_row_count as f32).max(new_query_line_count as f32);
185 if matched_ratio >= 0.8 {
186 let buffer_start_ix = self
187 .snapshot
188 .point_to_offset(Point::new(buffer_row_start, 0));
189 let buffer_end_ix = self.snapshot.point_to_offset(Point::new(
190 buffer_row_end - 1,
191 self.snapshot.line_len(buffer_row_end - 1),
192 ));
193 valid_matches.push((buffer_row_start, buffer_start_ix..buffer_end_ix));
194 }
195 }
196
197 valid_matches.into_iter().map(|(_, range)| range).collect()
198 }
199
200 /// Return the best match with starting position close enough to line_hint.
201 pub fn select_best_match(&self) -> Option<Range<usize>> {
202 // Allow line hint to be off by that many lines.
203 // Higher values increase probability of applying edits to a wrong place,
204 // Lower values increase edits failures and overall conversation length.
205 const LINE_HINT_TOLERANCE: u32 = 200;
206
207 if self.matches.is_empty() {
208 return None;
209 }
210
211 if self.matches.len() == 1 {
212 return self.matches.first().cloned();
213 }
214
215 let Some(line_hint) = self.line_hint else {
216 // Multiple ambiguous matches
217 return None;
218 };
219
220 let mut best_match = None;
221 let mut best_distance = u32::MAX;
222
223 for range in &self.matches {
224 let start_point = self.snapshot.offset_to_point(range.start);
225 let start_line = start_point.row;
226 let distance = start_line.abs_diff(line_hint);
227
228 if distance <= LINE_HINT_TOLERANCE && distance < best_distance {
229 best_distance = distance;
230 best_match = Some(range.clone());
231 }
232 }
233
234 best_match
235 }
236}
237
238fn fuzzy_eq(left: &str, right: &str) -> bool {
239 const THRESHOLD: f64 = 0.8;
240
241 let min_levenshtein = left.len().abs_diff(right.len());
242 let min_normalized_levenshtein =
243 1. - (min_levenshtein as f64 / cmp::max(left.len(), right.len()) as f64);
244 if min_normalized_levenshtein < THRESHOLD {
245 return false;
246 }
247
248 strsim::normalized_levenshtein(left, right) >= THRESHOLD
249}
250
251#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
252enum SearchDirection {
253 Up,
254 Left,
255 Diagonal,
256}
257
258#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
259struct SearchState {
260 cost: u32,
261 direction: SearchDirection,
262}
263
264impl SearchState {
265 fn new(cost: u32, direction: SearchDirection) -> Self {
266 Self { cost, direction }
267 }
268}
269
270struct SearchMatrix {
271 cols: usize,
272 rows: usize,
273 data: Vec<SearchState>,
274}
275
276impl SearchMatrix {
277 fn new(cols: usize) -> Self {
278 SearchMatrix {
279 cols,
280 rows: 0,
281 data: Vec::new(),
282 }
283 }
284
285 fn resize_rows(&mut self, needed_rows: usize) {
286 debug_assert!(needed_rows > self.rows);
287 self.rows = needed_rows;
288 self.data.resize(
289 self.rows * self.cols,
290 SearchState::new(0, SearchDirection::Diagonal),
291 );
292 }
293
294 fn get(&self, row: usize, col: usize) -> SearchState {
295 debug_assert!(row < self.rows && col < self.cols);
296 self.data[row * self.cols + col]
297 }
298
299 fn set(&mut self, row: usize, col: usize, state: SearchState) {
300 debug_assert!(row < self.rows && col < self.cols);
301 self.data[row * self.cols + col] = state;
302 }
303}
304
305#[cfg(test)]
306mod tests {
307 use super::*;
308 use gpui::TestAppContext;
309 use indoc::indoc;
310 use language::{BufferId, TextBuffer};
311 use rand::prelude::*;
312 use text::ReplicaId;
313 use util::test::{generate_marked_text, marked_text_ranges};
314
315 #[gpui::test]
316 fn test_empty_query(cx: &mut gpui::TestAppContext) {
317 let buffer = TextBuffer::new(
318 ReplicaId::LOCAL,
319 BufferId::new(1).unwrap(),
320 "Hello world\nThis is a test\nFoo bar baz",
321 cx.background_executor(),
322 );
323 let snapshot = buffer.snapshot();
324
325 let mut finder = StreamingFuzzyMatcher::new(snapshot);
326 assert_eq!(push(&mut finder, ""), None);
327 assert_eq!(finish(finder), None);
328 }
329
330 #[gpui::test]
331 fn test_streaming_exact_match(cx: &mut gpui::TestAppContext) {
332 let buffer = TextBuffer::new(
333 ReplicaId::LOCAL,
334 BufferId::new(1).unwrap(),
335 "Hello world\nThis is a test\nFoo bar baz",
336 cx.background_executor(),
337 );
338 let snapshot = buffer.snapshot();
339
340 let mut finder = StreamingFuzzyMatcher::new(snapshot);
341
342 // Push partial query
343 assert_eq!(push(&mut finder, "This"), None);
344
345 // Complete the line
346 assert_eq!(
347 push(&mut finder, " is a test\n"),
348 Some("This is a test".to_string())
349 );
350
351 // Finish should return the same result
352 assert_eq!(finish(finder), Some("This is a test".to_string()));
353 }
354
355 #[gpui::test]
356 fn test_streaming_fuzzy_match(cx: &mut gpui::TestAppContext) {
357 let buffer = TextBuffer::new(
358 ReplicaId::LOCAL,
359 BufferId::new(1).unwrap(),
360 indoc! {"
361 function foo(a, b) {
362 return a + b;
363 }
364
365 function bar(x, y) {
366 return x * y;
367 }
368 "},
369 cx.background_executor(),
370 );
371 let snapshot = buffer.snapshot();
372
373 let mut finder = StreamingFuzzyMatcher::new(snapshot);
374
375 // Push a fuzzy query that should match the first function
376 assert_eq!(
377 push(&mut finder, "function foo(a, c) {\n").as_deref(),
378 Some("function foo(a, b) {")
379 );
380 assert_eq!(
381 push(&mut finder, " return a + c;\n}\n").as_deref(),
382 Some(concat!(
383 "function foo(a, b) {\n",
384 " return a + b;\n",
385 "}"
386 ))
387 );
388 }
389
390 #[gpui::test]
391 fn test_incremental_improvement(cx: &mut gpui::TestAppContext) {
392 let buffer = TextBuffer::new(
393 ReplicaId::LOCAL,
394 BufferId::new(1).unwrap(),
395 "Line 1\nLine 2\nLine 3\nLine 4\nLine 5",
396 cx.background_executor(),
397 );
398 let snapshot = buffer.snapshot();
399
400 let mut finder = StreamingFuzzyMatcher::new(snapshot);
401
402 // No match initially
403 assert_eq!(push(&mut finder, "Lin"), None);
404
405 // Get a match when we complete a line
406 assert_eq!(push(&mut finder, "e 3\n"), Some("Line 3".to_string()));
407
408 // The match might change if we add more specific content
409 assert_eq!(
410 push(&mut finder, "Line 4\n"),
411 Some("Line 3\nLine 4".to_string())
412 );
413 assert_eq!(finish(finder), Some("Line 3\nLine 4".to_string()));
414 }
415
416 #[gpui::test]
417 fn test_incomplete_lines_buffering(cx: &mut gpui::TestAppContext) {
418 let buffer = TextBuffer::new(
419 ReplicaId::LOCAL,
420 BufferId::new(1).unwrap(),
421 indoc! {"
422 The quick brown fox
423 jumps over the lazy dog
424 Pack my box with five dozen liquor jugs
425 "},
426 cx.background_executor(),
427 );
428 let snapshot = buffer.snapshot();
429
430 let mut finder = StreamingFuzzyMatcher::new(snapshot);
431
432 // Push text in small chunks across line boundaries
433 assert_eq!(push(&mut finder, "jumps "), None); // No newline yet
434 assert_eq!(push(&mut finder, "over the"), None); // Still no newline
435 assert_eq!(push(&mut finder, " lazy"), None); // Still incomplete
436
437 // Complete the line
438 assert_eq!(
439 push(&mut finder, " dog\n"),
440 Some("jumps over the lazy dog".to_string())
441 );
442 }
443
444 #[gpui::test]
445 fn test_multiline_fuzzy_match(cx: &mut gpui::TestAppContext) {
446 let buffer = TextBuffer::new(
447 ReplicaId::LOCAL,
448 BufferId::new(1).unwrap(),
449 indoc! {r#"
450 impl Display for User {
451 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
452 write!(f, "User: {} ({})", self.name, self.email)
453 }
454 }
455
456 impl Debug for User {
457 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
458 f.debug_struct("User")
459 .field("name", &self.name)
460 .field("email", &self.email)
461 .finish()
462 }
463 }
464 "#},
465 cx.background_executor(),
466 );
467 let snapshot = buffer.snapshot();
468
469 let mut finder = StreamingFuzzyMatcher::new(snapshot);
470
471 assert_eq!(
472 push(&mut finder, "impl Debug for User {\n"),
473 Some("impl Debug for User {".to_string())
474 );
475 assert_eq!(
476 push(
477 &mut finder,
478 " fn fmt(&self, f: &mut Formatter) -> Result {\n"
479 )
480 .as_deref(),
481 Some(concat!(
482 "impl Debug for User {\n",
483 " fn fmt(&self, f: &mut Formatter) -> fmt::Result {"
484 ))
485 );
486 assert_eq!(
487 push(&mut finder, " f.debug_struct(\"User\")\n").as_deref(),
488 Some(concat!(
489 "impl Debug for User {\n",
490 " fn fmt(&self, f: &mut Formatter) -> fmt::Result {\n",
491 " f.debug_struct(\"User\")"
492 ))
493 );
494 assert_eq!(
495 push(
496 &mut finder,
497 " .field(\"name\", &self.username)\n"
498 )
499 .as_deref(),
500 Some(concat!(
501 "impl Debug for User {\n",
502 " fn fmt(&self, f: &mut Formatter) -> fmt::Result {\n",
503 " f.debug_struct(\"User\")\n",
504 " .field(\"name\", &self.name)"
505 ))
506 );
507 assert_eq!(
508 finish(finder).as_deref(),
509 Some(concat!(
510 "impl Debug for User {\n",
511 " fn fmt(&self, f: &mut Formatter) -> fmt::Result {\n",
512 " f.debug_struct(\"User\")\n",
513 " .field(\"name\", &self.name)"
514 ))
515 );
516 }
517
518 #[gpui::test(iterations = 100)]
519 fn test_resolve_location_single_line(mut rng: StdRng, cx: &mut TestAppContext) {
520 assert_location_resolution(
521 concat!(
522 " Lorem\n",
523 "« ipsum»\n",
524 " dolor sit amet\n",
525 " consecteur",
526 ),
527 "ipsum",
528 &mut rng,
529 cx,
530 );
531 }
532
533 #[gpui::test(iterations = 100)]
534 fn test_resolve_location_multiline(mut rng: StdRng, cx: &mut TestAppContext) {
535 assert_location_resolution(
536 concat!(
537 " Lorem\n",
538 "« ipsum\n",
539 " dolor sit amet»\n",
540 " consecteur",
541 ),
542 "ipsum\ndolor sit amet",
543 &mut rng,
544 cx,
545 );
546 }
547
548 #[gpui::test(iterations = 100)]
549 fn test_resolve_location_function_with_typo(mut rng: StdRng, cx: &mut TestAppContext) {
550 assert_location_resolution(
551 indoc! {"
552 «fn foo1(a: usize) -> usize {
553 40
554 }»
555
556 fn foo2(b: usize) -> usize {
557 42
558 }
559 "},
560 "fn foo1(a: usize) -> u32 {\n40\n}",
561 &mut rng,
562 cx,
563 );
564 }
565
566 #[gpui::test(iterations = 100)]
567 fn test_resolve_location_class_methods(mut rng: StdRng, cx: &mut TestAppContext) {
568 assert_location_resolution(
569 indoc! {"
570 class Something {
571 one() { return 1; }
572 « two() { return 2222; }
573 three() { return 333; }
574 four() { return 4444; }
575 five() { return 5555; }
576 six() { return 6666; }»
577 seven() { return 7; }
578 eight() { return 8; }
579 }
580 "},
581 indoc! {"
582 two() { return 2222; }
583 four() { return 4444; }
584 five() { return 5555; }
585 six() { return 6666; }
586 "},
587 &mut rng,
588 cx,
589 );
590 }
591
592 #[gpui::test(iterations = 100)]
593 fn test_resolve_location_imports_no_match(mut rng: StdRng, cx: &mut TestAppContext) {
594 assert_location_resolution(
595 indoc! {"
596 use std::ops::Range;
597 use std::sync::Mutex;
598 use std::{
599 collections::HashMap,
600 env,
601 ffi::{OsStr, OsString},
602 fs,
603 io::{BufRead, BufReader},
604 mem,
605 path::{Path, PathBuf},
606 process::Command,
607 sync::LazyLock,
608 time::SystemTime,
609 };
610 "},
611 indoc! {"
612 use std::collections::{HashMap, HashSet};
613 use std::ffi::{OsStr, OsString};
614 use std::fmt::Write as _;
615 use std::fs;
616 use std::io::{BufReader, Read, Write};
617 use std::mem;
618 use std::path::{Path, PathBuf};
619 use std::process::Command;
620 use std::sync::Arc;
621 "},
622 &mut rng,
623 cx,
624 );
625 }
626
627 #[gpui::test(iterations = 100)]
628 fn test_resolve_location_nested_closure(mut rng: StdRng, cx: &mut TestAppContext) {
629 assert_location_resolution(
630 indoc! {"
631 impl Foo {
632 fn new() -> Self {
633 Self {
634 subscriptions: vec![
635 cx.observe_window_activation(window, |editor, window, cx| {
636 let active = window.is_window_active();
637 editor.blink_manager.update(cx, |blink_manager, cx| {
638 if active {
639 blink_manager.enable(cx);
640 } else {
641 blink_manager.disable(cx);
642 }
643 });
644 }),
645 ];
646 }
647 }
648 }
649 "},
650 concat!(
651 " editor.blink_manager.update(cx, |blink_manager, cx| {\n",
652 " blink_manager.enable(cx);\n",
653 " });",
654 ),
655 &mut rng,
656 cx,
657 );
658 }
659
660 #[gpui::test(iterations = 100)]
661 fn test_resolve_location_tool_invocation(mut rng: StdRng, cx: &mut TestAppContext) {
662 assert_location_resolution(
663 indoc! {r#"
664 let tool = cx
665 .update(|cx| working_set.tool(&tool_name, cx))
666 .map_err(|err| {
667 anyhow!("Failed to look up tool '{}': {}", tool_name, err)
668 })?;
669
670 let Some(tool) = tool else {
671 return Err(anyhow!("Tool '{}' not found", tool_name));
672 };
673
674 let project = project.clone();
675 let action_log = action_log.clone();
676 let messages = messages.clone();
677 let tool_result = cx
678 .update(|cx| tool.run(invocation.input, &messages, project, action_log, cx))
679 .map_err(|err| anyhow!("Failed to start tool '{}': {}", tool_name, err))?;
680
681 tasks.push(tool_result.output);
682 "#},
683 concat!(
684 "let tool_result = cx\n",
685 " .update(|cx| tool.run(invocation.input, &messages, project, action_log, cx))\n",
686 " .output;",
687 ),
688 &mut rng,
689 cx,
690 );
691 }
692
693 #[gpui::test]
694 fn test_line_hint_selection(cx: &mut TestAppContext) {
695 let text = indoc! {r#"
696 fn first_function() {
697 return 42;
698 }
699
700 fn second_function() {
701 return 42;
702 }
703
704 fn third_function() {
705 return 42;
706 }
707 "#};
708
709 let buffer = TextBuffer::new(
710 ReplicaId::LOCAL,
711 BufferId::new(1).unwrap(),
712 text.to_string(),
713 cx.background_executor(),
714 );
715 let snapshot = buffer.snapshot();
716 let mut matcher = StreamingFuzzyMatcher::new(snapshot.clone());
717
718 // Given a query that matches all three functions
719 let query = "return 42;\n";
720
721 // Test with line hint pointing to second function (around line 5)
722 let best_match = matcher.push(query, Some(5)).expect("Failed to match query");
723
724 let matched_text = snapshot
725 .text_for_range(best_match.clone())
726 .collect::<String>();
727 assert!(matched_text.contains("return 42;"));
728 assert_eq!(
729 best_match,
730 63..77,
731 "Expected to match `second_function` based on the line hint"
732 );
733
734 let mut matcher = StreamingFuzzyMatcher::new(snapshot);
735 matcher.push(query, None);
736 matcher.finish();
737 let best_match = matcher.select_best_match();
738 assert!(
739 best_match.is_none(),
740 "Best match should be None when query cannot be uniquely resolved"
741 );
742 }
743
744 #[track_caller]
745 fn assert_location_resolution(
746 text_with_expected_range: &str,
747 query: &str,
748 rng: &mut StdRng,
749 cx: &mut TestAppContext,
750 ) {
751 let (text, expected_ranges) = marked_text_ranges(text_with_expected_range, false);
752 let buffer = TextBuffer::new(
753 ReplicaId::LOCAL,
754 BufferId::new(1).unwrap(),
755 text.clone(),
756 cx.background_executor(),
757 );
758 let snapshot = buffer.snapshot();
759
760 let mut matcher = StreamingFuzzyMatcher::new(snapshot);
761
762 // Split query into random chunks
763 let chunks = to_random_chunks(rng, query);
764
765 // Push chunks incrementally
766 for chunk in &chunks {
767 matcher.push(chunk, None);
768 }
769
770 let actual_ranges = matcher.finish();
771
772 // If no expected ranges, we expect no match
773 if expected_ranges.is_empty() {
774 assert!(
775 actual_ranges.is_empty(),
776 "Expected no match for query: {:?}, but found: {:?}",
777 query,
778 actual_ranges
779 );
780 } else {
781 let text_with_actual_range = generate_marked_text(&text, &actual_ranges, false);
782 pretty_assertions::assert_eq!(
783 text_with_actual_range,
784 text_with_expected_range,
785 indoc! {"
786 Query: {:?}
787 Chunks: {:?}
788 Expected marked text: {}
789 Actual marked text: {}
790 Expected ranges: {:?}
791 Actual ranges: {:?}"
792 },
793 query,
794 chunks,
795 text_with_expected_range,
796 text_with_actual_range,
797 expected_ranges,
798 actual_ranges
799 );
800 }
801 }
802
803 fn to_random_chunks(rng: &mut StdRng, input: &str) -> Vec<String> {
804 let chunk_count = rng.random_range(1..=cmp::min(input.len(), 50));
805 let mut chunk_indices = (0..input.len()).choose_multiple(rng, chunk_count);
806 chunk_indices.sort();
807 chunk_indices.push(input.len());
808
809 let mut chunks = Vec::new();
810 let mut last_ix = 0;
811 for chunk_ix in chunk_indices {
812 chunks.push(input[last_ix..chunk_ix].to_string());
813 last_ix = chunk_ix;
814 }
815 chunks
816 }
817
818 fn push(finder: &mut StreamingFuzzyMatcher, chunk: &str) -> Option<String> {
819 finder
820 .push(chunk, None)
821 .map(|range| finder.snapshot.text_for_range(range).collect::<String>())
822 }
823
824 fn finish(mut finder: StreamingFuzzyMatcher) -> Option<String> {
825 let snapshot = finder.snapshot.clone();
826 let matches = finder.finish();
827 matches
828 .first()
829 .map(|range| snapshot.text_for_range(range.clone()).collect::<String>())
830 }
831}