ui/components/command_palette/
fuzzy.rs

1//! In-house fuzzy match/score, no external crate. See phase file's ADR
2//! rationale: the corpus (a few dozen app commands) is far too small to
3//! justify a real fuzzy-match library's complexity.
4
5/// Scores `candidate` against `query`, case-insensitively. Returns `None` if
6/// `query` is not a (possibly non-contiguous, in-order) subsequence of
7/// `candidate` — i.e. no match at all. Higher scores rank better; an empty
8/// `query` matches everything with score `0` (unfiltered default state).
9pub fn score(query: &str, candidate: &str) -> Option<i32> {
10    if query.is_empty() {
11        return Some(0);
12    }
13
14    let query_lower = query.to_lowercase();
15    let candidate_lower = candidate.to_lowercase();
16
17    // A contiguous substring match always outranks a scattered subsequence
18    // match, and ranks higher the closer it is to the start of the
19    // candidate (prefix matches feel most relevant in a command list).
20    if let Some(index) = candidate_lower.find(&query_lower) {
21        let position_bonus = (100 - (index as i32).min(100)) * 10;
22        let length_bonus = query_lower.chars().count() as i32;
23        return Some(1_000 + position_bonus + length_bonus);
24    }
25
26    subsequence_score(&query_lower, &candidate_lower)
27}
28
29/// Scores an in-order, non-contiguous character subsequence match. Rewards
30/// longer contiguous runs and matches that occur earlier in the candidate.
31/// Returns `None` if `query`'s characters don't all appear, in order, in
32/// `candidate`.
33fn subsequence_score(query: &str, candidate: &str) -> Option<i32> {
34    let query_chars: Vec<char> = query.chars().collect();
35    if query_chars.is_empty() {
36        return Some(0);
37    }
38
39    let mut query_ix = 0;
40    let mut run_length = 0;
41    let mut total_score = 0;
42    let mut previous_match_ix: Option<usize> = None;
43
44    for (candidate_ix, candidate_char) in candidate.chars().enumerate() {
45        if query_ix >= query_chars.len() {
46            break;
47        }
48        if candidate_char != query_chars[query_ix] {
49            continue;
50        }
51
52        let is_contiguous = previous_match_ix.map(|ix| ix + 1) == Some(candidate_ix);
53        run_length = if is_contiguous { run_length + 1 } else { 1 };
54        total_score += run_length * 5 - (candidate_ix as i32) / 4;
55        previous_match_ix = Some(candidate_ix);
56        query_ix += 1;
57    }
58
59    if query_ix == query_chars.len() {
60        Some(total_score)
61    } else {
62        None
63    }
64}
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn empty_query_matches_everything() {
72        assert_eq!(score("", "New Profile"), Some(0));
73        assert_eq!(score("", ""), Some(0));
74    }
75
76    #[test]
77    fn substring_match_is_case_insensitive() {
78        assert!(score("prof", "New Profile").is_some());
79        assert!(score("PROF", "new profile").is_some());
80        assert!(score("Profile", "PROFILE").is_some());
81    }
82
83    #[test]
84    fn no_subsequence_match_returns_none() {
85        assert_eq!(score("xyz", "New Profile"), None);
86        assert_eq!(score("zzz", ""), None);
87    }
88
89    #[test]
90    fn scattered_subsequence_still_matches() {
91        // "npf" -> N(ew) P(rofile) F(...)? not exactly, use a case that is a
92        // genuine in-order (non-contiguous) subsequence.
93        assert!(score("newprof", "New Profile").is_some());
94    }
95
96    #[test]
97    fn contiguous_substring_ranks_above_scattered_subsequence() {
98        let contiguous = score("prof", "New Profile").unwrap();
99        let scattered = score("nwpf", "New Profile").unwrap();
100        assert!(contiguous > scattered);
101    }
102
103    #[test]
104    fn earlier_matches_rank_higher() {
105        let early = score("new", "New Profile").unwrap();
106        let late = score("file", "New Profile").unwrap();
107        assert!(early > late);
108    }
109
110    #[test]
111    fn out_of_order_characters_do_not_match() {
112        // "c" appears before "a" in the query, but after it in "abc", so this
113        // is not a valid in-order subsequence.
114        assert_eq!(score("ca", "abc"), None);
115    }
116}
ui/components/command_palette/fuzzy.rs

ui/components/command_palette/
fuzzy.rs
