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) -> Vec<Range<usize>> {
10 let mut matches = Vec::new();
11 let mut haystack_lines = haystack.chunks().lines();
12 let mut haystack_line_start = 0;
13 while let Some(haystack_line) = haystack_lines.next() {
14 let next_haystack_line_start = haystack_line_start + haystack_line.len() + 1;
15 let mut trimmed_needle_lines = needle.lines().map(|line| line.trim());
16 if Some(haystack_line.trim()) == trimmed_needle_lines.next() {
17 let match_start = haystack_line_start;
18 let mut match_end = next_haystack_line_start;
19 let matched = loop {
20 match (haystack_lines.next(), trimmed_needle_lines.next()) {
21 (Some(haystack_line), Some(needle_line)) => {
22 // Haystack line differs from needle line: not a match.
23 if haystack_line.trim() == needle_line {
24 match_end = haystack_lines.offset();
25 } else {
26 break false;
27 }
28 }
29 // We exhausted the haystack but not the query: not a match.
30 (None, Some(_)) => break false,
31 // We exhausted the query: it's a match.
32 (_, None) => break true,
33 }
34 };
35
36 if matched {
37 matches.push(match_start..match_end)
38 }
39
40 // Advance to the next line.
41 haystack_lines.seek(next_haystack_line_start);
42 }
43
44 haystack_line_start = next_haystack_line_start;
45 }
46 matches
47}
48
49#[cfg(test)]
50mod test {
51 use super::*;
52 use gpui::{AppContext, Context as _};
53 use language::{Buffer, OffsetRangeExt};
54 use unindent::Unindent as _;
55 use util::test::marked_text_ranges;
56
57 #[gpui::test]
58 fn test_fuzzy_search_lines(cx: &mut AppContext) {
59 let (text, expected_ranges) = marked_text_ranges(
60 &r#"
61 fn main() {
62 if a() {
63 assert_eq!(
64 1 + 2,
65 does_not_match,
66 );
67 }
68
69 println!("hi");
70
71 assert_eq!(
72 1 + 2,
73 3,
74 ); // this last line does not match
75
76 « assert_eq!(
77 1 + 2,
78 3,
79 );
80 »
81
82 assert_eq!(
83 "something",
84 "else",
85 );
86
87 if b {
88 « assert_eq!(
89 1 + 2,
90 3,
91 );
92 » }
93 }
94 "#
95 .unindent(),
96 false,
97 );
98
99 let buffer = cx.new_model(|cx| Buffer::local(&text, cx));
100 let snapshot = buffer.read_with(cx, |buffer, _| buffer.snapshot());
101
102 let actual_ranges = fuzzy_search_lines(
103 snapshot.as_rope(),
104 &"
105 assert_eq!(
106 1 + 2,
107 3,
108 );
109 "
110 .unindent(),
111 );
112 assert_eq!(
113 actual_ranges,
114 expected_ranges,
115 "actual: {:?}, expected: {:?}",
116 actual_ranges
117 .iter()
118 .map(|range| range.to_point(&snapshot))
119 .collect::<Vec<_>>(),
120 expected_ranges
121 .iter()
122 .map(|range| range.to_point(&snapshot))
123 .collect::<Vec<_>>()
124 );
125
126 let actual_ranges = fuzzy_search_lines(
127 snapshot.as_rope(),
128 &"
129 assert_eq!(
130 1 + 2,
131 3,
132 );
133 "
134 .unindent(),
135 );
136 assert_eq!(
137 actual_ranges,
138 expected_ranges,
139 "actual: {:?}, expected: {:?}",
140 actual_ranges
141 .iter()
142 .map(|range| range.to_point(&snapshot))
143 .collect::<Vec<_>>(),
144 expected_ranges
145 .iter()
146 .map(|range| range.to_point(&snapshot))
147 .collect::<Vec<_>>()
148 );
149 }
150}