tenant.openagents/omega

1use crate::{BufferSnapshot, Point, ToPoint, ToTreeSitterPoint};
2use fuzzy_nucleo::{Case, LengthPenalty, StringMatch, StringMatchCandidate};
3use gpui::{BackgroundExecutor, HighlightStyle, SharedString};
4use std::ops::Range;
5
6/// An outline of all the symbols contained in a buffer.
7#[derive(Debug)]
8pub struct Outline<T> {
9    pub items: Vec<OutlineItem<T>>,
10    /// Candidates contain the full path of each item, used for matching.
11    candidates: Vec<StringMatchCandidate>,
12    /// leaf_offsets stores the byte offset within that full path where the
13    /// item's own text starts. Anything before this offset is ancestor
14    /// path text used purely as match context.
15    leaf_offsets: Vec<usize>,
16}
17
18#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
19pub struct OutlineItem<T> {
20    pub depth: usize,
21    pub range: Range<T>,
22    pub selection_range: Range<T>,
23    pub source_range_for_text: Range<T>,
24    pub text: SharedString,
25    pub highlight_ranges: Vec<(Range<usize>, HighlightStyle)>,
26    pub name_ranges: Vec<Range<usize>>,
27    pub body_range: Option<Range<T>>,
28    pub annotation_range: Option<Range<T>>,
29}
30
31#[derive(Clone, Debug, Eq, PartialEq)]
32pub struct SymbolPath(pub SharedString);
33
34/// Result of [`Outline::search`]. Real fuzzy matches are `Match`; `Ancestor`
35/// rows are synthetic entries pointing at parent items, included so callers can
36/// show the full path of each match (Even when the ancestor has been filtered
37/// out due to not matching) but treat those synthetic ancestors differently
38/// from an entry that actually matched (e.g. they are not eligible for
39/// auto-selection).
40#[derive(Clone, Debug)]
41pub enum OutlineSearchEntry {
42    Match(StringMatch),
43    Ancestor { candidate_id: usize },
44}
45
46impl OutlineSearchEntry {
47    pub fn candidate_id(&self) -> usize {
48        match self {
49            Self::Match(m) => m.candidate_id,
50            Self::Ancestor { candidate_id } => *candidate_id,
51        }
52    }
53
54    pub fn as_match(&self) -> Option<&StringMatch> {
55        match self {
56            Self::Match(m) => Some(m),
57            Self::Ancestor { .. } => None,
58        }
59    }
60
61    pub fn into_match(self) -> Option<StringMatch> {
62        match self {
63            Self::Match(m) => Some(m),
64            Self::Ancestor { .. } => None,
65        }
66    }
67}
68
69impl<T: ToPoint> OutlineItem<T> {
70    /// Converts to an equivalent outline item, but with parameterized over Points.
71    pub fn to_point(&self, buffer: &BufferSnapshot) -> OutlineItem<Point> {
72        OutlineItem {
73            depth: self.depth,
74            range: self.range.start.to_point(buffer)..self.range.end.to_point(buffer),
75            selection_range: self.selection_range.start.to_point(buffer)
76                ..self.selection_range.end.to_point(buffer),
77            source_range_for_text: self.source_range_for_text.start.to_point(buffer)
78                ..self.source_range_for_text.end.to_point(buffer),
79            text: self.text.clone(),
80            highlight_ranges: self.highlight_ranges.clone(),
81            name_ranges: self.name_ranges.clone(),
82            body_range: self
83                .body_range
84                .as_ref()
85                .map(|r| r.start.to_point(buffer)..r.end.to_point(buffer)),
86            annotation_range: self
87                .annotation_range
88                .as_ref()
89                .map(|r| r.start.to_point(buffer)..r.end.to_point(buffer)),
90        }
91    }
92
93    pub fn body_range(&self, buffer: &BufferSnapshot) -> Option<Range<Point>> {
94        if let Some(range) = self.body_range.as_ref() {
95            return Some(range.start.to_point(buffer)..range.end.to_point(buffer));
96        }
97
98        let range = self.range.start.to_point(buffer)..self.range.end.to_point(buffer);
99        let start_indent = buffer.indent_size_for_line(range.start.row);
100        let node = buffer.syntax_ancestor(range.clone())?;
101
102        let mut cursor = node.walk();
103        loop {
104            let node = cursor.node();
105            if node.start_position() >= range.start.to_ts_point()
106                && node.end_position() <= range.end.to_ts_point()
107            {
108                break;
109            }
110            // If we can't descend further, the current node is the most specific
111            // ancestor that contains `range.start`. Bail out rather than spinning
112            // forever re-checking the same node.
113            if cursor
114                .goto_first_child_for_point(range.start.to_ts_point())
115                .is_none()
116            {
117                return None;
118            }
119        }
120
121        if !cursor.goto_last_child() {
122            return None;
123        }
124        let body_node = loop {
125            let node = cursor.node();
126            if node.child_count() > 0 {
127                break node;
128            }
129            if !cursor.goto_previous_sibling() {
130                return None;
131            }
132        };
133
134        let mut start_row = body_node.start_position().row as u32;
135        let mut end_row = body_node.end_position().row as u32;
136
137        while start_row < end_row && buffer.indent_size_for_line(start_row) == start_indent {
138            start_row += 1;
139        }
140        while start_row < end_row && buffer.indent_size_for_line(end_row - 1) == start_indent {
141            end_row -= 1;
142        }
143        if start_row < end_row {
144            return Some(Point::new(start_row, 0)..Point::new(end_row, 0));
145        }
146        None
147    }
148}
149
150impl<T> Outline<T> {
151    pub fn new(items: Vec<OutlineItem<T>>) -> Self {
152        let mut candidates = Vec::with_capacity(items.len());
153        let mut leaf_offsets = Vec::with_capacity(items.len());
154        let mut path_text = String::new();
155        let mut path_stack = Vec::new();
156
157        for (id, item) in items.iter().enumerate() {
158            if item.depth < path_stack.len() {
159                path_stack.truncate(item.depth);
160                path_text.truncate(path_stack.last().copied().unwrap_or(0));
161            }
162            if !path_text.is_empty() {
163                path_text.push(' ');
164            }
165            leaf_offsets.push(path_text.len());
166            path_text.push_str(&item.text);
167            path_stack.push(path_text.len());
168            candidates.push(StringMatchCandidate::new(id, &path_text));
169        }
170
171        Self {
172            items,
173            candidates,
174            leaf_offsets,
175        }
176    }
177
178    /// Find the most similar symbol to the provided query using normalized Levenshtein distance.
179    pub fn find_most_similar(&self, query: &str) -> Option<(SymbolPath, &OutlineItem<T>)> {
180        const SIMILARITY_THRESHOLD: f64 = 0.6;
181
182        let (position, similarity) = self
183            .candidates
184            .iter()
185            .enumerate()
186            .map(|(index, candidate)| {
187                let similarity = strsim::normalized_levenshtein(&candidate.string, query);
188                (index, similarity)
189            })
190            .max_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap())?;
191
192        if similarity >= SIMILARITY_THRESHOLD {
193            self.candidates
194                .get(position)
195                .map(|candidate| SymbolPath(candidate.string.clone()))
196                .zip(self.items.get(position))
197        } else {
198            None
199        }
200    }
201
202    /// Find all outline symbols that match with the nucleo fuzzy matcher, ordered by tree position.
203    /// Each real match is preceded by [`OutlineSearchEntry::Ancestor`] rows carrying parent
204    /// `candidate_id`s, so callers can render tree context above the match.
205    pub async fn search(
206        &self,
207        query: &str,
208        executor: BackgroundExecutor,
209    ) -> Vec<OutlineSearchEntry> {
210        let query = query.trim_start();
211        if query.is_empty() {
212            return Vec::new();
213        }
214        let mut matches = fuzzy_nucleo::match_strings_async(
215            &self.candidates,
216            query,
217            Case::Smart,
218            LengthPenalty::On,
219            100,
220            &Default::default(),
221            executor,
222        )
223        .await;
224        matches.sort_unstable_by_key(|m| m.candidate_id);
225
226        // Single-atom queries (no whitespace) require *all* matched chars to
227        // land in the leaf — typing "drop" should only surface leaves that
228        // actually contain "drop", not items whose ancestor path happens to.
229        // We can rely on that behavior because nucleo prefers matches at the
230        // end of the haystack, so the leafiest part of the candidate.
231        //
232        // Multi-atom queries (whitespace-separated) use the ancestor path
233        // for scoping. Rows whose entire match landed in an ancestor are
234        // kept as context, with empty positions and zero score, so
235        // descendants of a matched container surface alongside it. The
236        // picker's score-based auto-select skips them so they never steal
237        // focus from a row with real highlights.
238        let single_atom = !query.contains(char::is_whitespace);
239        matches.retain_mut(|string_match| {
240            let leaf_offset = self.leaf_offsets[string_match.candidate_id];
241            let total = string_match.positions.len();
242            string_match
243                .positions
244                .retain(|position| *position >= leaf_offset);
245            let kept = string_match.positions.len();
246            if single_atom && kept != total {
247                return false;
248            }
249            if kept == 0 {
250                string_match.score = 0.0;
251            }
252            for position in &mut string_match.positions {
253                *position -= leaf_offset;
254            }
255            string_match
256                .string
257                .clone_from(&self.items[string_match.candidate_id].text);
258            true
259        });
260
261        expand_tree(|i| self.items[i].depth, matches)
262    }
263}
264
265/// Interleaves synthetic [`OutlineSearchEntry::Ancestor`] rows before each match so callers
266/// can render the parent chain as tree context above the match.
267///
268/// `matches` must be sorted ascending by `candidate_id` (which is what
269/// [`Outline::search`] produces), this is so that we preserve the tree
270/// structure of the outline. `depth_at` returns the tree depth for the item at
271/// a given candidate index. Ancestors that already appear earlier in the output
272/// either as their own match or as an ancestor of an earlier match, are not
273/// duplicated.
274fn expand_tree(
275    depth_at: impl Fn(usize) -> usize,
276    matches: Vec<StringMatch>,
277) -> Vec<OutlineSearchEntry> {
278    debug_assert!(matches.is_sorted_by_key(|m| m.candidate_id));
279    let mut out = Vec::with_capacity(matches.len());
280    let mut prev_item_ix = 0;
281    for string_match in matches {
282        let insertion_ix = out.len();
283        let mut cur_depth = depth_at(string_match.candidate_id);
284        for ix in (prev_item_ix..string_match.candidate_id).rev() {
285            if cur_depth == 0 {
286                break;
287            }
288            if depth_at(ix) == cur_depth - 1 {
289                out.insert(
290                    insertion_ix,
291                    OutlineSearchEntry::Ancestor { candidate_id: ix },
292                );
293                cur_depth -= 1;
294            }
295        }
296        prev_item_ix = string_match.candidate_id + 1;
297        out.push(OutlineSearchEntry::Match(string_match));
298    }
299    out
300}
301
302#[cfg(test)]
303mod tests {
304    use super::*;
305    use crate::{Buffer, rust_lang};
306    use gpui::{AppContext as _, TestAppContext};
307
308    #[gpui::test]
309    fn test_body_range_hangs_when_outline_range_is_inside_leaf_node(cx: &mut TestAppContext) {
310        let text = "fn main() { let completion = 1; }";
311        let buffer = cx.new(|cx| Buffer::local(text, cx).with_language(rust_lang(), cx));
312        let snapshot = buffer.update(cx, |buffer, _| buffer.snapshot());
313        let identifier_start = text.find("completion").unwrap() + 1;
314        let identifier_end = identifier_start + 1;
315        let range =
316            snapshot.offset_to_point(identifier_start)..snapshot.offset_to_point(identifier_end);
317
318        let item = OutlineItem {
319            depth: 0,
320            range: range.clone(),
321            selection_range: range.clone(),
322            source_range_for_text: range,
323            text: "completion".into(),
324            highlight_ranges: Vec::new(),
325            name_ranges: Vec::new(),
326            body_range: None,
327            annotation_range: None,
328        };
329
330        assert_eq!(item.body_range(&snapshot), None);
331    }
332
333    #[gpui::test]
334    async fn test_entries_with_no_names(cx: &mut TestAppContext) {
335        let outline = Outline::new(vec![
336            OutlineItem {
337                depth: 0,
338                range: Point::new(0, 0)..Point::new(5, 0),
339                selection_range: Point::new(0, 6)..Point::new(0, 9),
340                source_range_for_text: Point::new(0, 0)..Point::new(0, 9),
341                text: "class Foo".into(),
342                highlight_ranges: vec![],
343                name_ranges: vec![6..9],
344                body_range: None,
345                annotation_range: None,
346            },
347            OutlineItem {
348                depth: 0,
349                range: Point::new(2, 0)..Point::new(2, 7),
350                selection_range: Point::new(2, 0)..Point::new(2, 7),
351                source_range_for_text: Point::new(0, 0)..Point::new(0, 7),
352                text: "private".into(),
353                highlight_ranges: vec![],
354                name_ranges: vec![],
355                body_range: None,
356                annotation_range: None,
357            },
358        ]);
359        assert!(
360            outline.search("", cx.executor()).await.is_empty(),
361            "empty queries return no matches; the picker handles 'show all' itself",
362        );
363        assert_eq!(
364            outline
365                .search("foo", cx.executor())
366                .await
367                .into_iter()
368                .filter_map(OutlineSearchEntry::into_match)
369                .map(|m| m.string)
370                .collect::<Vec<SharedString>>(),
371            vec![SharedString::from("class Foo")],
372            "'private' (empty name_ranges) is correctly excluded; only the matching 'class Foo' is returned",
373        );
374    }
375
376    #[test]
377    fn test_find_most_similar_with_low_similarity() {
378        let outline = Outline::new(vec![
379            OutlineItem {
380                depth: 0,
381                range: Point::new(0, 0)..Point::new(5, 0),
382                selection_range: Point::new(0, 3)..Point::new(0, 10),
383                source_range_for_text: Point::new(0, 0)..Point::new(0, 10),
384                text: "fn process".into(),
385                highlight_ranges: vec![],
386                name_ranges: vec![3..10],
387                body_range: None,
388                annotation_range: None,
389            },
390            OutlineItem {
391                depth: 0,
392                range: Point::new(7, 0)..Point::new(12, 0),
393                selection_range: Point::new(0, 7)..Point::new(0, 20),
394                source_range_for_text: Point::new(0, 0)..Point::new(0, 20),
395                text: "struct DataProcessor".into(),
396                highlight_ranges: vec![],
397                name_ranges: vec![7..20],
398                body_range: None,
399                annotation_range: None,
400            },
401        ]);
402        assert_eq!(
403            outline.find_most_similar("pub fn process"),
404            Some((SymbolPath("fn process".into()), &outline.items[0]))
405        );
406        assert_eq!(
407            outline.find_most_similar("async fn process"),
408            Some((SymbolPath("fn process".into()), &outline.items[0])),
409        );
410        assert_eq!(
411            outline.find_most_similar("struct Processor"),
412            Some((SymbolPath("struct DataProcessor".into()), &outline.items[1]))
413        );
414        assert_eq!(outline.find_most_similar("struct User"), None);
415        assert_eq!(outline.find_most_similar("struct"), None);
416    }
417}
418