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