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, 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: Arc<Background>) -> 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
 85            if is_path_query {
 86                let prefix_len = self.path_candidate_prefixes[string_match.candidate_id];
 87                string_match
 88                    .positions
 89                    .retain(|position| *position >= prefix_len);
 90                for position in &mut string_match.positions {
 91                    *position -= prefix_len;
 92                }
 93            } else {
 94                let mut name_ranges = outline_match.name_ranges.iter();
 95                let mut name_range = name_ranges.next().unwrap();
 96                let mut preceding_ranges_len = 0;
 97                for position in &mut string_match.positions {
 98                    while *position >= preceding_ranges_len + name_range.len() as usize {
 99                        preceding_ranges_len += name_range.len();
100                        name_range = name_ranges.next().unwrap();
101                    }
102                    *position = name_range.start as usize + (*position - preceding_ranges_len);
103                }
104            }
105
106            let insertion_ix = tree_matches.len();
107            let mut cur_depth = outline_match.depth;
108            for (ix, item) in self.items[prev_item_ix..string_match.candidate_id]
109                .iter()
110                .enumerate()
111                .rev()
112            {
113                if cur_depth == 0 {
114                    break;
115                }
116
117                let candidate_index = ix + prev_item_ix;
118                if item.depth == cur_depth - 1 {
119                    tree_matches.insert(
120                        insertion_ix,
121                        StringMatch {
122                            candidate_id: candidate_index,
123                            score: Default::default(),
124                            positions: Default::default(),
125                            string: Default::default(),
126                        },
127                    );
128                    cur_depth -= 1;
129                }
130            }
131
132            prev_item_ix = string_match.candidate_id + 1;
133            tree_matches.push(string_match);
134        }
135
136        tree_matches
137    }
138}