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