gpui_cn/
fuzzy.rs

1//! The fuzzy matcher every search in gpui-cn uses: the folder and file
2//! pickers, the model picker, the selects, the searchable status lists, and
3//! the palettes.
4//!
5//! A query matches an item when its characters are a subsequence of the
6//! item's text, ignoring case and accents. Matches that run together or start words score
7//! higher. [`rank`] returns the matches best first, with the byte ranges of
8//! the characters the query matched, so a row can mark them.
9//!
10//! The module is public as a small utility, so an application's own search
11//! box can rank like the library's.
12
13use std::{cell::RefCell, ops::Range};
14
15use gpui_kit::{FontWeight, HighlightStyle, Hsla, SharedString, StyledText};
16use nucleo_matcher::{
17    Config, Matcher, Utf32Str,
18    pattern::{Atom, AtomKind, CaseMatching, Normalization},
19};
20
21/// An item that matches the query, and where.
22#[derive(Clone, Debug, PartialEq, Eq)]
23#[non_exhaustive]
24pub struct Match {
25    /// The index of the item in the list that was ranked.
26    pub index: usize,
27    /// The score: a higher one ranks first.
28    pub score: u32,
29    /// The byte ranges of the item's text that the query matched. Empty
30    /// for an empty query.
31    pub ranges: Vec<Range<usize>>,
32}
33
34/// Ranks `items` by how well `query` matches `key(item)`, best first. An
35/// empty query (or one of only spaces) returns every item in its own
36/// order. Items that do not match are left out. Equal scores go to the
37/// shorter text, then keep the list's order.
38///
39/// ```
40/// use gpui_cn::fuzzy::rank;
41///
42/// let names = ["feature/composer", "main", "fix/popover"];
43/// let found = rank("cmpsr", &names, |name| name);
44/// assert_eq!(found.len(), 1);
45/// assert_eq!(names[found[0].index], "feature/composer");
46/// ```
47pub fn rank<T>(query: &str, items: &[T], key: impl Fn(&T) -> &str) -> Vec<Match> {
48    let query = query.trim();
49    if query.is_empty() {
50        return (0..items.len())
51            .map(|index| Match {
52                index,
53                score: 0,
54                ranges: Vec::new(),
55            })
56            .collect();
57    }
58    let atom = atom(query);
59    let mut buffer = Vec::new();
60    let mut indices = Vec::new();
61    let mut matches: Vec<Match> = items
62        .iter()
63        .enumerate()
64        .filter_map(|(index, item)| {
65            let text = key(item);
66            let (score, ranges) = score(&atom, text, &mut buffer, &mut indices)?;
67            Some(Match {
68                index,
69                score,
70                ranges,
71            })
72        })
73        .collect();
74    matches.sort_by(|a, b| {
75        let length = |found: &Match| key(&items[found.index]).chars().count();
76        b.score
77            .cmp(&a.score)
78            .then_with(|| length(a).cmp(&length(b)))
79            .then_with(|| a.index.cmp(&b.index))
80    });
81    matches
82}
83
84fn atom(query: &str) -> Atom {
85    Atom::new(
86        query,
87        CaseMatching::Ignore,
88        Normalization::Smart,
89        AtomKind::Fuzzy,
90        false,
91    )
92}
93
94thread_local! {
95    static MATCHER: RefCell<Matcher> = RefCell::new(Matcher::new(Config::DEFAULT));
96}
97
98fn score(
99    atom: &Atom,
100    text: &str,
101    buffer: &mut Vec<char>,
102    indices: &mut Vec<u32>,
103) -> Option<(u32, Vec<Range<usize>>)> {
104    indices.clear();
105    // One entry per char, so the indices nucleo returns are char indices.
106    // `Utf32Str::new` would merge a combining mark or a CRLF into one
107    // entry and shift every index after it.
108    let haystack = if text.is_ascii() {
109        Utf32Str::Ascii(text.as_bytes())
110    } else {
111        buffer.clear();
112        buffer.extend(text.chars());
113        Utf32Str::Unicode(buffer)
114    };
115    let score =
116        MATCHER.with(|matcher| atom.indices(haystack, &mut matcher.borrow_mut(), indices))?;
117    indices.sort_unstable();
118    indices.dedup();
119    Some((u32::from(score), byte_ranges(text, indices)))
120}
121
122/// Whether `query` matches `text`. An empty query matches everything.
123///
124/// ```
125/// use gpui_cn::fuzzy::is_match;
126///
127/// assert!(is_match("cmpsr", "feature/composer"));
128/// assert!(!is_match("zzz", "feature/composer"));
129/// ```
130pub fn is_match(query: &str, text: &str) -> bool {
131    let query = query.trim();
132    query.is_empty() || matched(query, text).is_some()
133}
134
135/// How well `query` matches `text`: a higher score ranks first, `None` when
136/// it does not match. An empty query matches everything with score 0.
137pub fn score_of(query: &str, text: &str) -> Option<u32> {
138    let query = query.trim();
139    if query.is_empty() {
140        return Some(0);
141    }
142    score(&atom(query), text, &mut Vec::new(), &mut Vec::new()).map(|(score, _)| score)
143}
144
145/// The byte ranges of `text` that `query` matches, or `None` when it does
146/// not match. An empty query matches with no ranges.
147///
148/// ```
149/// use gpui_cn::fuzzy::matched;
150///
151/// assert_eq!(matched("cmp", "feature/composer"), Some(vec![8..9, 10..12]));
152/// assert_eq!(matched("zzz", "feature/composer"), None);
153/// ```
154pub fn matched(query: &str, text: &str) -> Option<Vec<Range<usize>>> {
155    let query = query.trim();
156    if query.is_empty() {
157        return Some(Vec::new());
158    }
159    let (_, ranges) = score(&atom(query), text, &mut Vec::new(), &mut Vec::new())?;
160    Some(ranges)
161}
162
163/// The byte ranges of the characters at `indices`, joined where they run
164/// together.
165fn byte_ranges(text: &str, indices: &[u32]) -> Vec<Range<usize>> {
166    let mut ranges: Vec<Range<usize>> = Vec::new();
167    let mut chars = text.char_indices().enumerate();
168    for &wanted in indices {
169        let Some((_, (start, c))) = chars.by_ref().find(|(at, _)| *at == wanted as usize) else {
170            break;
171        };
172        let end = start + c.len_utf8();
173        match ranges.last_mut() {
174            Some(last) if last.end == start => last.end = end,
175            _ => ranges.push(start..end),
176        }
177    }
178    ranges
179}
180
181/// `text` with the matched `ranges` in `color` and medium weight, for a row
182/// that shows why it matched. No range gives plain text.
183pub fn highlighted(text: SharedString, ranges: &[Range<usize>], color: Hsla) -> StyledText {
184    StyledText::new(text).with_highlights(ranges.iter().cloned().map(|range| {
185        (
186            range,
187            HighlightStyle {
188                color: Some(color),
189                font_weight: Some(FontWeight::MEDIUM),
190                ..Default::default()
191            },
192        )
193    }))
194}
195
196#[cfg(test)]
197mod tests {
198    use super::*;
199
200    fn found(query: &str, items: &[&str]) -> Vec<String> {
201        rank(query, items, |item| item)
202            .into_iter()
203            .map(|m| items[m.index].to_string())
204            .collect()
205    }
206
207    #[test]
208    fn a_subsequence_finds_the_item() {
209        assert_eq!(
210            found("gpt56m", &["Opus 5.5", "GPT-5.6 Mini"]),
211            ["GPT-5.6 Mini"]
212        );
213        assert_eq!(found("ops", &["GPT-5.6 Mini", "Opus 5.5"]), ["Opus 5.5"]);
214        assert_eq!(
215            found("cmpsr", &["main", "feature/composer"]),
216            ["feature/composer"]
217        );
218    }
219
220    #[test]
221    fn an_exact_prefix_ranks_first() {
222        assert_eq!(
223            found("fea", &["a-fresh-edge-a", "feature", "unfeasible"])[0],
224            "feature"
225        );
226    }
227
228    #[test]
229    fn an_empty_query_keeps_the_order_and_no_match_is_empty() {
230        assert_eq!(found("", &["b", "a", "c"]), ["b", "a", "c"]);
231        assert_eq!(found("  ", &["b", "a"]), ["b", "a"]);
232        assert!(found("zzz", &["b", "a"]).is_empty());
233    }
234
235    #[test]
236    fn matched_characters_come_back_as_byte_ranges() {
237        let items = ["feature/composer"];
238        let found = rank("cmp", &items, |item| item);
239        assert_eq!(found[0].ranges, vec![8..9, 10..12]);
240        let accented = ["\u{e9}t\u{e9}"];
241        assert_eq!(rank("t", &accented, |item| item)[0].ranges, vec![2..3]);
242    }
243
244    fn marked(query: &str, text: &str) -> Vec<String> {
245        matched(query, text)
246            .unwrap_or_default()
247            .into_iter()
248            .map(|range| text[range].to_string())
249            .collect()
250    }
251
252    #[test]
253    fn marks_land_on_the_matched_characters_in_any_script() {
254        assert_eq!(marked("x", "e\u{301}x"), ["x"], "after a combining mark");
255        assert_eq!(
256            marked("b", "\u{1F468}\u{200D}\u{1F469}b"),
257            ["b"],
258            "after a ZWJ emoji"
259        );
260        assert_eq!(
261            marked("\u{6587}", "\u{65e5}\u{672c}\u{6587}\u{5b57}"),
262            ["\u{6587}"],
263            "CJK"
264        );
265        assert_eq!(marked("z", "\u{130}z"), ["z"], "after U+0130");
266        assert_eq!(marked("b", "a\r\nb"), ["b"], "after a CRLF");
267        assert_eq!(marked("cf", "caf\u{e9}"), ["c", "f"]);
268    }
269
270    #[test]
271    fn equal_scores_prefer_the_shorter_text_then_the_list_order() {
272        assert_eq!(found("a", &["ab", "a", "ac", "a"]), ["a", "a", "ab", "ac"]);
273    }
274
275    #[test]
276    fn case_does_not_matter() {
277        assert_eq!(found("GPT", &["gpt-5", "other"]), ["gpt-5"]);
278        assert_eq!(found("gpt", &["gpt-5", "GPT-5"]).len(), 2);
279    }
280}
gpui_cn/fuzzy.rs

gpui_cn/
fuzzy.rs
