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 (position, similarity) = self
92 .path_candidates
93 .iter()
94 .enumerate()
95 .map(|(index, candidate)| {
96 let similarity = strsim::normalized_levenshtein(&candidate.string, query);
97 (index, similarity)
98 })
99 .max_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap())?;
100
101 if similarity >= SIMILARITY_THRESHOLD {
102 let item = self.items.get(position)?;
103 Some(item)
104 } else {
105 None
106 }
107 }
108
109 /// Find all outline symbols according to a longest subsequence match with the query, ordered descending by match score.
110 pub async fn search(&self, query: &str, executor: BackgroundExecutor) -> Vec<StringMatch> {
111 let query = query.trim_start();
112 let is_path_query = query.contains(' ');
113 let smart_case = query.chars().any(|c| c.is_uppercase());
114 let mut matches = fuzzy::match_strings(
115 if is_path_query {
116 &self.path_candidates
117 } else {
118 &self.candidates
119 },
120 query,
121 smart_case,
122 100,
123 &Default::default(),
124 executor.clone(),
125 )
126 .await;
127 matches.sort_unstable_by_key(|m| m.candidate_id);
128
129 let mut tree_matches = Vec::new();
130
131 let mut prev_item_ix = 0;
132 for mut string_match in matches {
133 let outline_match = &self.items[string_match.candidate_id];
134 string_match.string.clone_from(&outline_match.text);
135
136 if is_path_query {
137 let prefix_len = self.path_candidate_prefixes[string_match.candidate_id];
138 string_match
139 .positions
140 .retain(|position| *position >= prefix_len);
141 for position in &mut string_match.positions {
142 *position -= prefix_len;
143 }
144 } else {
145 let mut name_ranges = outline_match.name_ranges.iter();
146 let mut name_range = name_ranges.next().unwrap();
147 let mut preceding_ranges_len = 0;
148 for position in &mut string_match.positions {
149 while *position >= preceding_ranges_len + name_range.len() {
150 preceding_ranges_len += name_range.len();
151 name_range = name_ranges.next().unwrap();
152 }
153 *position = name_range.start + (*position - preceding_ranges_len);
154 }
155 }
156
157 let insertion_ix = tree_matches.len();
158 let mut cur_depth = outline_match.depth;
159 for (ix, item) in self.items[prev_item_ix..string_match.candidate_id]
160 .iter()
161 .enumerate()
162 .rev()
163 {
164 if cur_depth == 0 {
165 break;
166 }
167
168 let candidate_index = ix + prev_item_ix;
169 if item.depth == cur_depth - 1 {
170 tree_matches.insert(
171 insertion_ix,
172 StringMatch {
173 candidate_id: candidate_index,
174 score: Default::default(),
175 positions: Default::default(),
176 string: Default::default(),
177 },
178 );
179 cur_depth -= 1;
180 }
181 }
182
183 prev_item_ix = string_match.candidate_id + 1;
184 tree_matches.push(string_match);
185 }
186
187 tree_matches
188 }
189}
190
191pub fn render_item<T>(
192 outline_item: &OutlineItem<T>,
193 match_ranges: impl IntoIterator<Item = Range<usize>>,
194 cx: &AppContext,
195) -> StyledText {
196 let mut highlight_style = HighlightStyle::default();
197 highlight_style.background_color = Some(color_alpha(cx.theme().colors().text_accent, 0.3));
198 let custom_highlights = match_ranges
199 .into_iter()
200 .map(|range| (range, highlight_style));
201
202 let settings = ThemeSettings::get_global(cx);
203
204 // TODO: We probably shouldn't need to build a whole new text style here
205 // but I'm not sure how to get the current one and modify it.
206 // Before this change TextStyle::default() was used here, which was giving us the wrong font and text color.
207 let text_style = TextStyle {
208 color: cx.theme().colors().text,
209 font_family: settings.buffer_font.family.clone(),
210 font_features: settings.buffer_font.features.clone(),
211 font_fallbacks: settings.buffer_font.fallbacks.clone(),
212 font_size: settings.buffer_font_size(cx).into(),
213 font_weight: settings.buffer_font.weight,
214 line_height: relative(1.),
215 ..Default::default()
216 };
217 let highlights = gpui::combine_highlights(
218 custom_highlights,
219 outline_item.highlight_ranges.iter().cloned(),
220 );
221
222 StyledText::new(outline_item.text.clone()).with_highlights(&text_style, highlights)
223}
224
225#[cfg(test)]
226mod tests {
227 use super::*;
228
229 #[test]
230 fn test_find_most_similar_with_low_similarity() {
231 let outline = Outline::new(vec![
232 OutlineItem {
233 depth: 0,
234 range: Point::new(0, 0)..Point::new(5, 0),
235 text: "fn process".to_string(),
236 highlight_ranges: vec![],
237 name_ranges: vec![3..10],
238 body_range: None,
239 annotation_range: None,
240 },
241 OutlineItem {
242 depth: 0,
243 range: Point::new(7, 0)..Point::new(12, 0),
244 text: "struct DataProcessor".to_string(),
245 highlight_ranges: vec![],
246 name_ranges: vec![7..20],
247 body_range: None,
248 annotation_range: None,
249 },
250 ]);
251 assert_eq!(
252 outline.find_most_similar("pub fn process"),
253 Some(&outline.items[0])
254 );
255 assert_eq!(
256 outline.find_most_similar("async fn process"),
257 Some(&outline.items[0])
258 );
259 assert_eq!(
260 outline.find_most_similar("struct Processor"),
261 Some(&outline.items[1])
262 );
263 assert_eq!(outline.find_most_similar("struct User"), None);
264 assert_eq!(outline.find_most_similar("struct"), None);
265 }
266}