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 according to the Jaro-Winkler distance measure.
88 pub fn find_most_similar(&self, query: &str) -> Option<&OutlineItem<T>> {
89 let candidate = self.path_candidates.iter().max_by(|a, b| {
90 strsim::jaro_winkler(&a.string, query)
91 .total_cmp(&strsim::jaro_winkler(&b.string, query))
92 })?;
93 Some(&self.items[candidate.id])
94 }
95
96 /// Find all outline symbols according to a longest subsequence match with the query, ordered descending by match score.
97 pub async fn search(&self, query: &str, executor: BackgroundExecutor) -> Vec<StringMatch> {
98 let query = query.trim_start();
99 let is_path_query = query.contains(' ');
100 let smart_case = query.chars().any(|c| c.is_uppercase());
101 let mut matches = fuzzy::match_strings(
102 if is_path_query {
103 &self.path_candidates
104 } else {
105 &self.candidates
106 },
107 query,
108 smart_case,
109 100,
110 &Default::default(),
111 executor.clone(),
112 )
113 .await;
114 matches.sort_unstable_by_key(|m| m.candidate_id);
115
116 let mut tree_matches = Vec::new();
117
118 let mut prev_item_ix = 0;
119 for mut string_match in matches {
120 let outline_match = &self.items[string_match.candidate_id];
121 string_match.string.clone_from(&outline_match.text);
122
123 if is_path_query {
124 let prefix_len = self.path_candidate_prefixes[string_match.candidate_id];
125 string_match
126 .positions
127 .retain(|position| *position >= prefix_len);
128 for position in &mut string_match.positions {
129 *position -= prefix_len;
130 }
131 } else {
132 let mut name_ranges = outline_match.name_ranges.iter();
133 let mut name_range = name_ranges.next().unwrap();
134 let mut preceding_ranges_len = 0;
135 for position in &mut string_match.positions {
136 while *position >= preceding_ranges_len + name_range.len() {
137 preceding_ranges_len += name_range.len();
138 name_range = name_ranges.next().unwrap();
139 }
140 *position = name_range.start + (*position - preceding_ranges_len);
141 }
142 }
143
144 let insertion_ix = tree_matches.len();
145 let mut cur_depth = outline_match.depth;
146 for (ix, item) in self.items[prev_item_ix..string_match.candidate_id]
147 .iter()
148 .enumerate()
149 .rev()
150 {
151 if cur_depth == 0 {
152 break;
153 }
154
155 let candidate_index = ix + prev_item_ix;
156 if item.depth == cur_depth - 1 {
157 tree_matches.insert(
158 insertion_ix,
159 StringMatch {
160 candidate_id: candidate_index,
161 score: Default::default(),
162 positions: Default::default(),
163 string: Default::default(),
164 },
165 );
166 cur_depth -= 1;
167 }
168 }
169
170 prev_item_ix = string_match.candidate_id + 1;
171 tree_matches.push(string_match);
172 }
173
174 tree_matches
175 }
176}
177
178pub fn render_item<T>(
179 outline_item: &OutlineItem<T>,
180 match_ranges: impl IntoIterator<Item = Range<usize>>,
181 cx: &AppContext,
182) -> StyledText {
183 let mut highlight_style = HighlightStyle::default();
184 highlight_style.background_color = Some(color_alpha(cx.theme().colors().text_accent, 0.3));
185 let custom_highlights = match_ranges
186 .into_iter()
187 .map(|range| (range, highlight_style));
188
189 let settings = ThemeSettings::get_global(cx);
190
191 // TODO: We probably shouldn't need to build a whole new text style here
192 // but I'm not sure how to get the current one and modify it.
193 // Before this change TextStyle::default() was used here, which was giving us the wrong font and text color.
194 let text_style = TextStyle {
195 color: cx.theme().colors().text,
196 font_family: settings.buffer_font.family.clone(),
197 font_features: settings.buffer_font.features.clone(),
198 font_fallbacks: settings.buffer_font.fallbacks.clone(),
199 font_size: settings.buffer_font_size(cx).into(),
200 font_weight: settings.buffer_font.weight,
201 line_height: relative(1.),
202 ..Default::default()
203 };
204 let highlights = gpui::combine_highlights(
205 custom_highlights,
206 outline_item.highlight_ranges.iter().cloned(),
207 );
208
209 StyledText::new(outline_item.text.clone()).with_highlights(&text_style, highlights)
210}