1use language::Rope;
2use std::ops::Range;
3
4/// Search the given buffer for the given substring, ignoring any differences
5/// in line indentation between the query and the buffer.
6///
7/// Returns a vector of ranges of byte offsets in the buffer corresponding
8/// to the entire lines of the buffer.
9pub fn fuzzy_search_lines(haystack: &Rope, needle: &str) -> Option<Range<usize>> {
10 const SIMILARITY_THRESHOLD: f64 = 0.8;
11
12 let mut best_match: Option<(Range<usize>, f64)> = None; // (range, score)
13 let mut haystack_lines = haystack.chunks().lines();
14 let mut haystack_line_start = 0;
15 while let Some(mut haystack_line) = haystack_lines.next() {
16 let next_haystack_line_start = haystack_line_start + haystack_line.len() + 1;
17 let mut advanced_to_next_haystack_line = false;
18
19 let mut matched = true;
20 let match_start = haystack_line_start;
21 let mut match_end = next_haystack_line_start;
22 let mut match_score = 0.0;
23 let mut needle_lines = needle.lines().peekable();
24 while let Some(needle_line) = needle_lines.next() {
25 let similarity = line_similarity(haystack_line, needle_line);
26 if similarity >= SIMILARITY_THRESHOLD {
27 match_end = haystack_lines.offset();
28 match_score += similarity;
29
30 if needle_lines.peek().is_some() {
31 if let Some(next_haystack_line) = haystack_lines.next() {
32 advanced_to_next_haystack_line = true;
33 haystack_line = next_haystack_line;
34 } else {
35 matched = false;
36 break;
37 }
38 } else {
39 break;
40 }
41 } else {
42 matched = false;
43 break;
44 }
45 }
46
47 if matched
48 && best_match
49 .as_ref()
50 .map(|(_, best_score)| match_score > *best_score)
51 .unwrap_or(true)
52 {
53 best_match = Some((match_start..match_end, match_score));
54 }
55
56 if advanced_to_next_haystack_line {
57 haystack_lines.seek(next_haystack_line_start);
58 }
59 haystack_line_start = next_haystack_line_start;
60 }
61
62 best_match.map(|(range, _)| range)
63}
64
65/// Calculates the similarity between two lines, ignoring leading and trailing whitespace,
66/// using the Jaro-Winkler distance.
67///
68/// Returns a value between 0.0 and 1.0, where 1.0 indicates an exact match.
69fn line_similarity(line1: &str, line2: &str) -> f64 {
70 strsim::jaro_winkler(line1.trim(), line2.trim())
71}
72
73#[cfg(test)]
74mod test {
75 use super::*;
76 use gpui::{AppContext, Context as _};
77 use language::Buffer;
78 use unindent::Unindent as _;
79 use util::test::marked_text_ranges;
80
81 #[gpui::test]
82 fn test_fuzzy_search_lines(cx: &mut AppContext) {
83 let (text, expected_ranges) = marked_text_ranges(
84 &r#"
85 fn main() {
86 if a() {
87 assert_eq!(
88 1 + 2,
89 does_not_match,
90 );
91 }
92
93 println!("hi");
94
95 assert_eq!(
96 1 + 2,
97 3,
98 ); // this last line does not match
99
100 « assert_eq!(
101 1 + 2,
102 3,
103 );
104 »
105
106 « assert_eq!(
107 "something",
108 "else",
109 );
110 »
111 }
112 "#
113 .unindent(),
114 false,
115 );
116
117 let buffer = cx.new_model(|cx| Buffer::local(&text, cx));
118 let snapshot = buffer.read_with(cx, |buffer, _| buffer.snapshot());
119
120 let actual_range = fuzzy_search_lines(
121 snapshot.as_rope(),
122 &"
123 assert_eq!(
124 1 + 2,
125 3,
126 );
127 "
128 .unindent(),
129 )
130 .unwrap();
131 assert_eq!(actual_range, expected_ranges[0]);
132
133 let actual_range = fuzzy_search_lines(
134 snapshot.as_rope(),
135 &"
136 assert_eq!(
137 1 + 2,
138 3,
139 );
140 "
141 .unindent(),
142 )
143 .unwrap();
144 assert_eq!(actual_range, expected_ranges[0]);
145
146 let actual_range = fuzzy_search_lines(
147 snapshot.as_rope(),
148 &"
149 asst_eq!(
150 \"something\",
151 \"els\"
152 )
153 "
154 .unindent(),
155 )
156 .unwrap();
157 assert_eq!(actual_range, expected_ranges[1]);
158
159 let actual_range = fuzzy_search_lines(
160 snapshot.as_rope(),
161 &"
162 assert_eq!(
163 2 + 1,
164 3,
165 );
166 "
167 .unindent(),
168 );
169 assert_eq!(actual_range, None);
170 }
171}