1use fuzzy::{StringMatch, StringMatchCandidate};
2use gpui::{executor::Background, fonts::HighlightStyle};
3use std::{ops::Range, sync::Arc};
4
5#[derive(Debug)]
6pub struct Outline<T> {
7 pub items: Vec<OutlineItem<T>>,
8 candidates: Vec<StringMatchCandidate>,
9 path_candidates: Vec<StringMatchCandidate>,
10 path_candidate_prefixes: Vec<usize>,
11}
12
13#[derive(Clone, Debug)]
14pub struct OutlineItem<T> {
15 pub depth: usize,
16 pub range: Range<T>,
17 pub text: String,
18 pub highlight_ranges: Vec<(Range<usize>, HighlightStyle)>,
19 pub name_ranges: Vec<Range<usize>>,
20}
21
22impl<T> Outline<T> {
23 pub fn new(items: Vec<OutlineItem<T>>) -> Self {
24 let mut candidates = Vec::new();
25 let mut path_candidates = Vec::new();
26 let mut path_candidate_prefixes = Vec::new();
27 let mut path_text = String::new();
28 let mut path_stack = Vec::new();
29
30 for (id, item) in items.iter().enumerate() {
31 if item.depth < path_stack.len() {
32 path_stack.truncate(item.depth);
33 path_text.truncate(path_stack.last().copied().unwrap_or(0));
34 }
35 if !path_text.is_empty() {
36 path_text.push(' ');
37 }
38 path_candidate_prefixes.push(path_text.len());
39 path_text.push_str(&item.text);
40 path_stack.push(path_text.len());
41
42 let candidate_text = item
43 .name_ranges
44 .iter()
45 .map(|range| &item.text[range.start as usize..range.end as usize])
46 .collect::<String>();
47
48 path_candidates.push(StringMatchCandidate {
49 id,
50 char_bag: path_text.as_str().into(),
51 string: path_text.clone(),
52 });
53 candidates.push(StringMatchCandidate {
54 id,
55 char_bag: candidate_text.as_str().into(),
56 string: candidate_text,
57 });
58 }
59
60 Self {
61 candidates,
62 path_candidates,
63 path_candidate_prefixes,
64 items,
65 }
66 }
67
68 pub async fn search(&self, query: &str, executor: Arc<Background>) -> Vec<StringMatch> {
69 let query = query.trim_start();
70 let is_path_query = query.contains(' ');
71 let smart_case = query.chars().any(|c| c.is_uppercase());
72 let mut matches = fuzzy::match_strings(
73 if is_path_query {
74 &self.path_candidates
75 } else {
76 &self.candidates
77 },
78 query,
79 smart_case,
80 100,
81 &Default::default(),
82 executor.clone(),
83 )
84 .await;
85 matches.sort_unstable_by_key(|m| m.candidate_id);
86
87 let mut tree_matches = Vec::new();
88
89 let mut prev_item_ix = 0;
90 for mut string_match in matches {
91 let outline_match = &self.items[string_match.candidate_id];
92
93 if is_path_query {
94 let prefix_len = self.path_candidate_prefixes[string_match.candidate_id];
95 string_match
96 .positions
97 .retain(|position| *position >= prefix_len);
98 for position in &mut string_match.positions {
99 *position -= prefix_len;
100 }
101 } else {
102 let mut name_ranges = outline_match.name_ranges.iter();
103 let mut name_range = name_ranges.next().unwrap();
104 let mut preceding_ranges_len = 0;
105 for position in &mut string_match.positions {
106 while *position >= preceding_ranges_len + name_range.len() as usize {
107 preceding_ranges_len += name_range.len();
108 name_range = name_ranges.next().unwrap();
109 }
110 *position = name_range.start as usize + (*position - preceding_ranges_len);
111 }
112 }
113
114 let insertion_ix = tree_matches.len();
115 let mut cur_depth = outline_match.depth;
116 for (ix, item) in self.items[prev_item_ix..string_match.candidate_id]
117 .iter()
118 .enumerate()
119 .rev()
120 {
121 if cur_depth == 0 {
122 break;
123 }
124
125 let candidate_index = ix + prev_item_ix;
126 if item.depth == cur_depth - 1 {
127 tree_matches.insert(
128 insertion_ix,
129 StringMatch {
130 candidate_id: candidate_index,
131 score: Default::default(),
132 positions: Default::default(),
133 string: Default::default(),
134 },
135 );
136 cur_depth -= 1;
137 }
138 }
139
140 prev_item_ix = string_match.candidate_id + 1;
141 tree_matches.push(string_match);
142 }
143
144 tree_matches
145 }
146}