1use fuzzy::{StringMatch, StringMatchCandidate};
2use gpui::{BackgroundExecutor, HighlightStyle};
3use std::ops::Range;
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, PartialEq, Eq)]
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::new(id, path_text.clone()));
49 candidates.push(StringMatchCandidate::new(id, candidate_text));
50 }
51
52 Self {
53 candidates,
54 path_candidates,
55 path_candidate_prefixes,
56 items,
57 }
58 }
59
60 pub async fn search(&self, query: &str, executor: BackgroundExecutor) -> Vec<StringMatch> {
61 let query = query.trim_start();
62 let is_path_query = query.contains(' ');
63 let smart_case = query.chars().any(|c| c.is_uppercase());
64 let mut matches = fuzzy::match_strings(
65 if is_path_query {
66 &self.path_candidates
67 } else {
68 &self.candidates
69 },
70 query,
71 smart_case,
72 100,
73 &Default::default(),
74 executor.clone(),
75 )
76 .await;
77 matches.sort_unstable_by_key(|m| m.candidate_id);
78
79 let mut tree_matches = Vec::new();
80
81 let mut prev_item_ix = 0;
82 for mut string_match in matches {
83 let outline_match = &self.items[string_match.candidate_id];
84 string_match.string = outline_match.text.clone();
85
86 if is_path_query {
87 let prefix_len = self.path_candidate_prefixes[string_match.candidate_id];
88 string_match
89 .positions
90 .retain(|position| *position >= prefix_len);
91 for position in &mut string_match.positions {
92 *position -= prefix_len;
93 }
94 } else {
95 let mut name_ranges = outline_match.name_ranges.iter();
96 let mut name_range = name_ranges.next().unwrap();
97 let mut preceding_ranges_len = 0;
98 for position in &mut string_match.positions {
99 while *position >= preceding_ranges_len + name_range.len() as usize {
100 preceding_ranges_len += name_range.len();
101 name_range = name_ranges.next().unwrap();
102 }
103 *position = name_range.start as usize + (*position - preceding_ranges_len);
104 }
105 }
106
107 let insertion_ix = tree_matches.len();
108 let mut cur_depth = outline_match.depth;
109 for (ix, item) in self.items[prev_item_ix..string_match.candidate_id]
110 .iter()
111 .enumerate()
112 .rev()
113 {
114 if cur_depth == 0 {
115 break;
116 }
117
118 let candidate_index = ix + prev_item_ix;
119 if item.depth == cur_depth - 1 {
120 tree_matches.insert(
121 insertion_ix,
122 StringMatch {
123 candidate_id: candidate_index,
124 score: Default::default(),
125 positions: Default::default(),
126 string: Default::default(),
127 },
128 );
129 cur_depth -= 1;
130 }
131 }
132
133 prev_item_ix = string_match.candidate_id + 1;
134 tree_matches.push(string_match);
135 }
136
137 tree_matches
138 }
139}