1use crate::{BufferSnapshot, Point, ToPoint};
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
53impl<T> Outline<T> {
54 pub fn new(items: Vec<OutlineItem<T>>) -> Self {
55 let mut candidates = Vec::new();
56 let mut path_candidates = Vec::new();
57 let mut path_candidate_prefixes = Vec::new();
58 let mut path_text = String::new();
59 let mut path_stack = Vec::new();
60
61 for (id, item) in items.iter().enumerate() {
62 if item.depth < path_stack.len() {
63 path_stack.truncate(item.depth);
64 path_text.truncate(path_stack.last().copied().unwrap_or(0));
65 }
66 if !path_text.is_empty() {
67 path_text.push(' ');
68 }
69 path_candidate_prefixes.push(path_text.len());
70 path_text.push_str(&item.text);
71 path_stack.push(path_text.len());
72
73 let candidate_text = item
74 .name_ranges
75 .iter()
76 .map(|range| &item.text[range.start..range.end])
77 .collect::<String>();
78
79 path_candidates.push(StringMatchCandidate::new(id, &path_text));
80 candidates.push(StringMatchCandidate::new(id, &candidate_text));
81 }
82
83 Self {
84 candidates,
85 path_candidates,
86 path_candidate_prefixes,
87 items,
88 }
89 }
90
91 /// Find the most similar symbol to the provided query using normalized Levenshtein distance.
92 pub fn find_most_similar(&self, query: &str) -> Option<(SymbolPath, &OutlineItem<T>)> {
93 const SIMILARITY_THRESHOLD: f64 = 0.6;
94
95 let (position, similarity) = self
96 .path_candidates
97 .iter()
98 .enumerate()
99 .map(|(index, candidate)| {
100 let similarity = strsim::normalized_levenshtein(&candidate.string, query);
101 (index, similarity)
102 })
103 .max_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap())?;
104
105 if similarity >= SIMILARITY_THRESHOLD {
106 self.path_candidates
107 .get(position)
108 .map(|candidate| SymbolPath(candidate.string.clone()))
109 .zip(self.items.get(position))
110 } else {
111 None
112 }
113 }
114
115 /// Find all outline symbols according to a longest subsequence match with the query, ordered descending by match score.
116 pub async fn search(&self, query: &str, executor: BackgroundExecutor) -> Vec<StringMatch> {
117 let query = query.trim_start();
118 let is_path_query = query.contains(' ');
119 let smart_case = query.chars().any(|c| c.is_uppercase());
120 let mut matches = fuzzy::match_strings(
121 if is_path_query {
122 &self.path_candidates
123 } else {
124 &self.candidates
125 },
126 query,
127 smart_case,
128 true,
129 100,
130 &Default::default(),
131 executor.clone(),
132 )
133 .await;
134 matches.sort_unstable_by_key(|m| m.candidate_id);
135
136 let mut tree_matches = Vec::new();
137
138 let mut prev_item_ix = 0;
139 for mut string_match in matches {
140 let outline_match = &self.items[string_match.candidate_id];
141 string_match.string.clone_from(&outline_match.text);
142
143 if is_path_query {
144 let prefix_len = self.path_candidate_prefixes[string_match.candidate_id];
145 string_match
146 .positions
147 .retain(|position| *position >= prefix_len);
148 for position in &mut string_match.positions {
149 *position -= prefix_len;
150 }
151 } else {
152 let mut name_ranges = outline_match.name_ranges.iter();
153 let Some(mut name_range) = name_ranges.next() else {
154 continue;
155 };
156 let mut preceding_ranges_len = 0;
157 for position in &mut string_match.positions {
158 while *position >= preceding_ranges_len + name_range.len() {
159 preceding_ranges_len += name_range.len();
160 name_range = name_ranges.next().unwrap();
161 }
162 *position = name_range.start + (*position - preceding_ranges_len);
163 }
164 }
165
166 let insertion_ix = tree_matches.len();
167 let mut cur_depth = outline_match.depth;
168 for (ix, item) in self.items[prev_item_ix..string_match.candidate_id]
169 .iter()
170 .enumerate()
171 .rev()
172 {
173 if cur_depth == 0 {
174 break;
175 }
176
177 let candidate_index = ix + prev_item_ix;
178 if item.depth == cur_depth - 1 {
179 tree_matches.insert(
180 insertion_ix,
181 StringMatch {
182 candidate_id: candidate_index,
183 score: Default::default(),
184 positions: Default::default(),
185 string: Default::default(),
186 },
187 );
188 cur_depth -= 1;
189 }
190 }
191
192 prev_item_ix = string_match.candidate_id + 1;
193 tree_matches.push(string_match);
194 }
195
196 tree_matches
197 }
198}
199
200#[cfg(test)]
201mod tests {
202 use super::*;
203 use gpui::TestAppContext;
204
205 #[gpui::test]
206 async fn test_entries_with_no_names(cx: &mut TestAppContext) {
207 let outline = Outline::new(vec![
208 OutlineItem {
209 depth: 0,
210 range: Point::new(0, 0)..Point::new(5, 0),
211 source_range_for_text: Point::new(0, 0)..Point::new(0, 9),
212 text: "class Foo".to_string(),
213 highlight_ranges: vec![],
214 name_ranges: vec![6..9],
215 body_range: None,
216 annotation_range: None,
217 },
218 OutlineItem {
219 depth: 0,
220 range: Point::new(2, 0)..Point::new(2, 7),
221 source_range_for_text: Point::new(0, 0)..Point::new(0, 7),
222 text: "private".to_string(),
223 highlight_ranges: vec![],
224 name_ranges: vec![],
225 body_range: None,
226 annotation_range: None,
227 },
228 ]);
229 assert_eq!(
230 outline
231 .search(" ", cx.executor())
232 .await
233 .into_iter()
234 .map(|mat| mat.string)
235 .collect::<Vec<String>>(),
236 vec!["class Foo".to_string()]
237 );
238 }
239
240 #[test]
241 fn test_find_most_similar_with_low_similarity() {
242 let outline = Outline::new(vec![
243 OutlineItem {
244 depth: 0,
245 range: Point::new(0, 0)..Point::new(5, 0),
246 source_range_for_text: Point::new(0, 0)..Point::new(0, 10),
247 text: "fn process".to_string(),
248 highlight_ranges: vec![],
249 name_ranges: vec![3..10],
250 body_range: None,
251 annotation_range: None,
252 },
253 OutlineItem {
254 depth: 0,
255 range: Point::new(7, 0)..Point::new(12, 0),
256 source_range_for_text: Point::new(0, 0)..Point::new(0, 20),
257 text: "struct DataProcessor".to_string(),
258 highlight_ranges: vec![],
259 name_ranges: vec![7..20],
260 body_range: None,
261 annotation_range: None,
262 },
263 ]);
264 assert_eq!(
265 outline.find_most_similar("pub fn process"),
266 Some((SymbolPath("fn process".into()), &outline.items[0]))
267 );
268 assert_eq!(
269 outline.find_most_similar("async fn process"),
270 Some((SymbolPath("fn process".into()), &outline.items[0])),
271 );
272 assert_eq!(
273 outline.find_most_similar("struct Processor"),
274 Some((SymbolPath("struct DataProcessor".into()), &outline.items[1]))
275 );
276 assert_eq!(outline.find_most_similar("struct User"), None);
277 assert_eq!(outline.find_most_similar("struct"), None);
278 }
279}