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