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}
10
11#[derive(Clone, Debug)]
12pub struct OutlineItem<T> {
13    pub depth: usize,
14    pub range: Range<T>,
15    pub text: String,
16    pub highlight_ranges: Vec<(Range<usize>, HighlightStyle)>,
17}
18
19impl<T> Outline<T> {
20    pub fn new(items: Vec<OutlineItem<T>>) -> Self {
21        Self {
22            candidates: items
23                .iter()
24                .enumerate()
25                .map(|(id, item)| StringMatchCandidate {
26                    id,
27                    char_bag: item.text.as_str().into(),
28                    string: item.text.clone(),
29                })
30                .collect(),
31            items,
32        }
33    }
34
35    pub async fn search(&self, query: &str, executor: Arc<Background>) -> Vec<StringMatch> {
36        let mut matches = fuzzy::match_strings(
37            &self.candidates,
38            query,
39            true,
40            100,
41            &Default::default(),
42            executor.clone(),
43        )
44        .await;
45        matches.sort_unstable_by_key(|m| m.candidate_id);
46
47        let mut tree_matches = Vec::new();
48
49        let mut prev_item_ix = 0;
50        for string_match in matches {
51            let outline_match = &self.items[string_match.candidate_id];
52            let insertion_ix = tree_matches.len();
53            let mut cur_depth = outline_match.depth;
54            for (ix, item) in self.items[prev_item_ix..string_match.candidate_id]
55                .iter()
56                .enumerate()
57                .rev()
58            {
59                if cur_depth == 0 {
60                    break;
61                }
62
63                let candidate_index = ix + prev_item_ix;
64                if item.depth == cur_depth - 1 {
65                    tree_matches.insert(
66                        insertion_ix,
67                        StringMatch {
68                            candidate_id: candidate_index,
69                            score: Default::default(),
70                            positions: Default::default(),
71                            string: Default::default(),
72                        },
73                    );
74                    cur_depth -= 1;
75                }
76            }
77
78            prev_item_ix = string_match.candidate_id + 1;
79            tree_matches.push(string_match);
80        }
81
82        tree_matches
83    }
84}