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