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