1use crate::{BufferSnapshot, Point, ToPoint, ToTreeSitterPoint};
2use fuzzy::{StringMatch, StringMatchCandidate};
3use gpui::{BackgroundExecutor, HighlightStyle};
4use std::ops::Range;
5
6/// An outline of all the symbols contained in a buffer.
7#[derive(Debug)]
8pub struct Outline<T> {
9 pub items: Vec<OutlineItem<T>>,
10 candidates: Vec<StringMatchCandidate>,
11 pub path_candidates: Vec<StringMatchCandidate>,
12 path_candidate_prefixes: Vec<usize>,
13}
14
15#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
16pub struct OutlineItem<T> {
17 pub depth: usize,
18 pub range: Range<T>,
19 pub source_range_for_text: Range<T>,
20 pub text: String,
21 pub highlight_ranges: Vec<(Range<usize>, HighlightStyle)>,
22 pub name_ranges: Vec<Range<usize>>,
23 pub body_range: Option<Range<T>>,
24 pub annotation_range: Option<Range<T>>,
25}
26
27#[derive(Clone, Debug, Eq, PartialEq)]
28pub struct SymbolPath(pub String);
29
30impl<T: ToPoint> OutlineItem<T> {
31 /// Converts to an equivalent outline item, but with parameterized over Points.
32 pub fn to_point(&self, buffer: &BufferSnapshot) -> OutlineItem<Point> {
33 OutlineItem {
34 depth: self.depth,
35 range: self.range.start.to_point(buffer)..self.range.end.to_point(buffer),
36 source_range_for_text: self.source_range_for_text.start.to_point(buffer)
37 ..self.source_range_for_text.end.to_point(buffer),
38 text: self.text.clone(),
39 highlight_ranges: self.highlight_ranges.clone(),
40 name_ranges: self.name_ranges.clone(),
41 body_range: self
42 .body_range
43 .as_ref()
44 .map(|r| r.start.to_point(buffer)..r.end.to_point(buffer)),
45 annotation_range: self
46 .annotation_range
47 .as_ref()
48 .map(|r| r.start.to_point(buffer)..r.end.to_point(buffer)),
49 }
50 }
51
52 pub fn body_range(&self, buffer: &BufferSnapshot) -> Option<Range<Point>> {
53 if let Some(range) = self.body_range.as_ref() {
54 return Some(range.start.to_point(buffer)..range.end.to_point(buffer));
55 }
56
57 let range = self.range.start.to_point(buffer)..self.range.end.to_point(buffer);
58 let start_indent = buffer.indent_size_for_line(range.start.row);
59 let node = buffer.syntax_ancestor(range.clone())?;
60
61 let mut cursor = node.walk();
62 loop {
63 let node = cursor.node();
64 if node.start_position() >= range.start.to_ts_point()
65 && node.end_position() <= range.end.to_ts_point()
66 {
67 break;
68 }
69 cursor.goto_first_child_for_point(range.start.to_ts_point());
70 }
71
72 if !cursor.goto_last_child() {
73 return None;
74 }
75 let body_node = loop {
76 let node = cursor.node();
77 if node.child_count() > 0 {
78 break node;
79 }
80 if !cursor.goto_previous_sibling() {
81 return None;
82 }
83 };
84
85 let mut start_row = body_node.start_position().row as u32;
86 let mut end_row = body_node.end_position().row as u32;
87
88 while start_row < end_row && buffer.indent_size_for_line(start_row) == start_indent {
89 start_row += 1;
90 }
91 while start_row < end_row && buffer.indent_size_for_line(end_row - 1) == start_indent {
92 end_row -= 1;
93 }
94 if start_row < end_row {
95 return Some(Point::new(start_row, 0)..Point::new(end_row, 0));
96 }
97 None
98 }
99}
100
101impl<T> Outline<T> {
102 pub fn new(items: Vec<OutlineItem<T>>) -> Self {
103 let mut candidates = Vec::new();
104 let mut path_candidates = Vec::new();
105 let mut path_candidate_prefixes = Vec::new();
106 let mut path_text = String::new();
107 let mut path_stack = Vec::new();
108
109 for (id, item) in items.iter().enumerate() {
110 if item.depth < path_stack.len() {
111 path_stack.truncate(item.depth);
112 path_text.truncate(path_stack.last().copied().unwrap_or(0));
113 }
114 if !path_text.is_empty() {
115 path_text.push(' ');
116 }
117 path_candidate_prefixes.push(path_text.len());
118 path_text.push_str(&item.text);
119 path_stack.push(path_text.len());
120
121 let candidate_text = item
122 .name_ranges
123 .iter()
124 .map(|range| &item.text[range.start..range.end])
125 .collect::<String>();
126
127 path_candidates.push(StringMatchCandidate::new(id, &path_text));
128 candidates.push(StringMatchCandidate::new(id, &candidate_text));
129 }
130
131 Self {
132 candidates,
133 path_candidates,
134 path_candidate_prefixes,
135 items,
136 }
137 }
138
139 /// Find the most similar symbol to the provided query using normalized Levenshtein distance.
140 pub fn find_most_similar(&self, query: &str) -> Option<(SymbolPath, &OutlineItem<T>)> {
141 const SIMILARITY_THRESHOLD: f64 = 0.6;
142
143 let (position, similarity) = self
144 .path_candidates
145 .iter()
146 .enumerate()
147 .map(|(index, candidate)| {
148 let similarity = strsim::normalized_levenshtein(&candidate.string, query);
149 (index, similarity)
150 })
151 .max_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap())?;
152
153 if similarity >= SIMILARITY_THRESHOLD {
154 self.path_candidates
155 .get(position)
156 .map(|candidate| SymbolPath(candidate.string.clone()))
157 .zip(self.items.get(position))
158 } else {
159 None
160 }
161 }
162
163 /// Find all outline symbols according to a longest subsequence match with the query, ordered descending by match score.
164 pub async fn search(&self, query: &str, executor: BackgroundExecutor) -> Vec<StringMatch> {
165 let query = query.trim_start();
166 let is_path_query = query.contains(' ');
167 let smart_case = query.chars().any(|c| c.is_uppercase());
168 let mut matches = fuzzy::match_strings(
169 if is_path_query {
170 &self.path_candidates
171 } else {
172 &self.candidates
173 },
174 query,
175 smart_case,
176 true,
177 100,
178 &Default::default(),
179 executor.clone(),
180 )
181 .await;
182 matches.sort_unstable_by_key(|m| m.candidate_id);
183
184 let mut tree_matches = Vec::new();
185
186 let mut prev_item_ix = 0;
187 for mut string_match in matches {
188 let outline_match = &self.items[string_match.candidate_id];
189 string_match.string.clone_from(&outline_match.text);
190
191 if is_path_query {
192 let prefix_len = self.path_candidate_prefixes[string_match.candidate_id];
193 string_match
194 .positions
195 .retain(|position| *position >= prefix_len);
196 for position in &mut string_match.positions {
197 *position -= prefix_len;
198 }
199 } else {
200 let mut name_ranges = outline_match.name_ranges.iter();
201 let Some(mut name_range) = name_ranges.next() else {
202 continue;
203 };
204 let mut preceding_ranges_len = 0;
205 for position in &mut string_match.positions {
206 while *position >= preceding_ranges_len + name_range.len() {
207 preceding_ranges_len += name_range.len();
208 name_range = name_ranges.next().unwrap();
209 }
210 *position = name_range.start + (*position - preceding_ranges_len);
211 }
212 }
213
214 let insertion_ix = tree_matches.len();
215 let mut cur_depth = outline_match.depth;
216 for (ix, item) in self.items[prev_item_ix..string_match.candidate_id]
217 .iter()
218 .enumerate()
219 .rev()
220 {
221 if cur_depth == 0 {
222 break;
223 }
224
225 let candidate_index = ix + prev_item_ix;
226 if item.depth == cur_depth - 1 {
227 tree_matches.insert(
228 insertion_ix,
229 StringMatch {
230 candidate_id: candidate_index,
231 score: Default::default(),
232 positions: Default::default(),
233 string: Default::default(),
234 },
235 );
236 cur_depth -= 1;
237 }
238 }
239
240 prev_item_ix = string_match.candidate_id + 1;
241 tree_matches.push(string_match);
242 }
243
244 tree_matches
245 }
246}
247
248#[cfg(test)]
249mod tests {
250 use super::*;
251 use gpui::TestAppContext;
252
253 #[gpui::test]
254 async fn test_entries_with_no_names(cx: &mut TestAppContext) {
255 let outline = Outline::new(vec![
256 OutlineItem {
257 depth: 0,
258 range: Point::new(0, 0)..Point::new(5, 0),
259 source_range_for_text: Point::new(0, 0)..Point::new(0, 9),
260 text: "class Foo".to_string(),
261 highlight_ranges: vec![],
262 name_ranges: vec![6..9],
263 body_range: None,
264 annotation_range: None,
265 },
266 OutlineItem {
267 depth: 0,
268 range: Point::new(2, 0)..Point::new(2, 7),
269 source_range_for_text: Point::new(0, 0)..Point::new(0, 7),
270 text: "private".to_string(),
271 highlight_ranges: vec![],
272 name_ranges: vec![],
273 body_range: None,
274 annotation_range: None,
275 },
276 ]);
277 assert_eq!(
278 outline
279 .search(" ", cx.executor())
280 .await
281 .into_iter()
282 .map(|mat| mat.string)
283 .collect::<Vec<String>>(),
284 vec!["class Foo".to_string()]
285 );
286 }
287
288 #[test]
289 fn test_find_most_similar_with_low_similarity() {
290 let outline = Outline::new(vec![
291 OutlineItem {
292 depth: 0,
293 range: Point::new(0, 0)..Point::new(5, 0),
294 source_range_for_text: Point::new(0, 0)..Point::new(0, 10),
295 text: "fn process".to_string(),
296 highlight_ranges: vec![],
297 name_ranges: vec![3..10],
298 body_range: None,
299 annotation_range: None,
300 },
301 OutlineItem {
302 depth: 0,
303 range: Point::new(7, 0)..Point::new(12, 0),
304 source_range_for_text: Point::new(0, 0)..Point::new(0, 20),
305 text: "struct DataProcessor".to_string(),
306 highlight_ranges: vec![],
307 name_ranges: vec![7..20],
308 body_range: None,
309 annotation_range: None,
310 },
311 ]);
312 assert_eq!(
313 outline.find_most_similar("pub fn process"),
314 Some((SymbolPath("fn process".into()), &outline.items[0]))
315 );
316 assert_eq!(
317 outline.find_most_similar("async fn process"),
318 Some((SymbolPath("fn process".into()), &outline.items[0])),
319 );
320 assert_eq!(
321 outline.find_most_similar("struct Processor"),
322 Some((SymbolPath("struct DataProcessor".into()), &outline.items[1]))
323 );
324 assert_eq!(outline.find_most_similar("struct User"), None);
325 assert_eq!(outline.find_most_similar("struct"), None);
326 }
327}