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