ashlar_command/
fuzzy.rs

1//! Fuzzy matching for a command palette: the query's characters must appear in order in the
2//! candidate (case-insensitive, spaces in the query ignored). The best-scoring alignment wins:
3//! matches at word starts (`File Export` ← `fe`), camelCase humps and consecutive runs score
4//! higher, gaps cost.
5
6/// Longer queries never match (bounded work on hostile input).
7const MAX_QUERY: usize = 64;
8/// Only this many leading characters of a candidate are considered.
9const MAX_CANDIDATE: usize = 512;
10
11const SCORE_MATCH: i32 = 16;
12const GAP_START: i32 = 3;
13const GAP_EXTEND: i32 = 1;
14const BONUS_FIRST: i32 = 8;
15const BONUS_BOUNDARY: i32 = 8;
16const BONUS_CAMEL: i32 = 7;
17const BONUS_CONSECUTIVE: i32 = 6;
18const BONUS_CASE: i32 = 1;
19const NONE: i32 = i32::MIN / 4;
20
21/// A match: higher scores are better; `positions` are the matched **char** indices of the
22/// candidate (for highlighting), ascending.
23#[derive(Debug, Clone, PartialEq, Eq)]
24pub struct FuzzyMatch {
25    pub score: i32,
26    pub positions: Vec<usize>,
27}
28
29fn lower(c: char) -> char {
30    c.to_lowercase().next().unwrap_or(c)
31}
32
33fn bonus(prev: Option<char>, c: char) -> i32 {
34    match prev {
35        None => BONUS_FIRST + BONUS_BOUNDARY,
36        Some(p) if !p.is_alphanumeric() && c.is_alphanumeric() => BONUS_BOUNDARY,
37        Some(p) if p.is_lowercase() && c.is_uppercase() => BONUS_CAMEL,
38        Some(p) if p.is_alphabetic() && c.is_numeric() => BONUS_CAMEL,
39        _ => 0,
40    }
41}
42
43/// Score `candidate` against `query`; `None` when the query's characters do not all appear in
44/// order. An empty query matches everything with score 0.
45pub fn fuzzy_match(query: &str, candidate: &str) -> Option<FuzzyMatch> {
46    let q: Vec<char> = query.chars().filter(|c| !c.is_whitespace()).collect();
47    if q.is_empty() {
48        return Some(FuzzyMatch { score: 0, positions: vec![] });
49    }
50    if q.len() > MAX_QUERY {
51        return None;
52    }
53    let c: Vec<char> = candidate.chars().take(MAX_CANDIDATE).collect();
54    let (n, m) = (q.len(), c.len());
55    if n > m {
56        return None;
57    }
58    let ql: Vec<char> = q.iter().map(|&x| lower(x)).collect();
59    let cl: Vec<char> = c.iter().map(|&x| lower(x)).collect();
60    // cheap subsequence test before the n×m table
61    let mut it = cl.iter();
62    if !ql.iter().all(|x| it.any(|y| y == x)) {
63        return None;
64    }
65    let gain: Vec<i32> = (0..m)
66        .map(|j| {
67            let ch = c.get(j).copied().unwrap_or(' ');
68            let prev = j.checked_sub(1).and_then(|p| c.get(p)).copied();
69            let case = if q.contains(&ch) { BONUS_CASE } else { 0 };
70            SCORE_MATCH + bonus(prev, ch) + case
71        })
72        .collect();
73    // score[i][j]: best score with query char i matched at candidate char j; from[i][j]: where
74    // query char i-1 was matched on that best path
75    let mut score = vec![vec![NONE; m]; n];
76    let mut from = vec![vec![usize::MAX; m]; n];
77    for i in 0..n {
78        let qi = ql.get(i).copied().unwrap_or_default();
79        let (prev_rows, rest) = score.split_at_mut(i);
80        let prev = prev_rows.last();
81        let Some(row) = rest.first_mut() else { break };
82        let Some(from_row) = from.get_mut(i) else { break };
83        // best over k <= j-2 of prev[k] minus the gap between k and j
84        let (mut run, mut run_k) = (NONE, usize::MAX);
85        for j in 0..m {
86            if let Some(prev) = prev
87                && j >= 2
88            {
89                let decayed = if run > NONE { run - GAP_EXTEND } else { NONE };
90                let fresh = prev.get(j - 2).copied().filter(|v| *v > NONE).map_or(NONE, |v| v - GAP_START);
91                if fresh >= decayed {
92                    (run, run_k) = (fresh, j - 2);
93                } else {
94                    run = decayed;
95                }
96            }
97            if cl.get(j) != Some(&qi) {
98                continue;
99            }
100            let g = gain.get(j).copied().unwrap_or(SCORE_MATCH);
101            match prev {
102                None => {
103                    if let Some(cell) = row.get_mut(j) {
104                        *cell = g;
105                    }
106                }
107                Some(prev) => {
108                    let diag = j.checked_sub(1).and_then(|k| prev.get(k)).copied().filter(|v| *v > NONE).map(|v| (v + BONUS_CONSECUTIVE, j - 1));
109                    let gap = (run > NONE).then_some((run, run_k));
110                    let best = match (diag, gap) {
111                        (Some(d), Some(g)) => Some(if d.0 >= g.0 { d } else { g }),
112                        (d, g) => d.or(g),
113                    };
114                    if let Some((s, k)) = best {
115                        if let Some(cell) = row.get_mut(j) {
116                            *cell = s + g;
117                        }
118                        if let Some(cell) = from_row.get_mut(j) {
119                            *cell = k;
120                        }
121                    }
122                }
123            }
124        }
125    }
126    let last = score.last()?;
127    let (mut j, best) = last.iter().copied().enumerate().filter(|(_, s)| *s > NONE).max_by_key(|&(j, s)| (s, std::cmp::Reverse(j)))?;
128    let mut positions = vec![0; n];
129    for i in (0..n).rev() {
130        if let Some(p) = positions.get_mut(i) {
131            *p = j;
132        }
133        if i > 0 {
134            j = from.get(i).and_then(|r| r.get(j)).copied().filter(|k| *k != usize::MAX)?;
135        }
136    }
137    Some(FuzzyMatch { score: best, positions })
138}
139
140/// Match `query` against every candidate and return the matches, best first (ties keep the input
141/// order, so callers can pre-sort by recency or frequency).
142pub fn fuzzy_rank<'a, T>(query: &str, candidates: impl IntoIterator<Item = (T, &'a str)>) -> Vec<(T, FuzzyMatch)> {
143    let mut out: Vec<(T, FuzzyMatch)> = candidates.into_iter().filter_map(|(t, s)| fuzzy_match(query, s).map(|m| (t, m))).collect();
144    out.sort_by_key(|m| std::cmp::Reverse(m.1.score));
145    out
146}
147
148#[cfg(test)]
149mod tests {
150    use super::*;
151
152    #[test]
153    fn subsequence_required() {
154        assert!(fuzzy_match("xyz", "File Export").is_none());
155        assert!(fuzzy_match("fe", "File Export").is_some());
156        assert_eq!(fuzzy_match("", "anything").unwrap().score, 0);
157    }
158
159    #[test]
160    fn word_starts_beat_middles() {
161        let m = fuzzy_match("fe", "File Export").unwrap();
162        assert_eq!(m.positions, [0, 5]);
163        let a = fuzzy_match("exp", "File Export").unwrap();
164        let b = fuzzy_match("exp", "Complex Paths").unwrap();
165        assert!(a.score > b.score, "{a:?} {b:?}");
166    }
167
168    #[test]
169    fn camel_case_and_ids() {
170        let m = fuzzy_match("rd", "edit.rippleDelete").unwrap();
171        assert_eq!(m.positions, [5, 11]);
172    }
173
174    #[test]
175    fn consecutive_preferred() {
176        let m = fuzzy_match("undo", "Edit: Undo").unwrap();
177        assert_eq!(m.positions, [6, 7, 8, 9]);
178    }
179
180    #[test]
181    fn ranking() {
182        let items = ["Save As…", "Save", "Select All", "Snap"];
183        let r = fuzzy_rank("sa", items.iter().enumerate().map(|(i, s)| (i, *s)));
184        let order: Vec<&str> = r.iter().map(|(i, _)| items[*i]).collect();
185        assert_eq!(order, ["Save As…", "Save", "Select All", "Snap"]);
186    }
187
188    #[test]
189    fn hostile_sizes_are_bounded() {
190        let long = "a".repeat(100_000);
191        assert!(fuzzy_match(&long, &long).is_none());
192        let q = "a".repeat(64);
193        let m = fuzzy_match(&q, &long).unwrap();
194        assert_eq!(m.positions.len(), 64);
195    }
196}
ashlar_command/fuzzy.rs

ashlar_command/
fuzzy.rs
