qframe/text/
fuzzy.rs

1//! Fuzzy matching: finding text by a few of its letters, in order.
2
3/// A fuzzy match: how good it is and which characters of the text matched. Made by [`fuzzy`].
4#[derive(Debug, Clone, PartialEq, Eq)]
5pub struct FuzzyMatch {
6    pub(crate) score: i32,
7    /// Character indices of the text, ascending.
8    pub(crate) positions: Vec<usize>,
9}
10
11impl FuzzyMatch {
12    /// How good the match is: higher is better. Only the order of scores for one query means
13    /// anything; an empty query scores 0.
14    #[must_use]
15    pub fn score(&self) -> i32 {
16        self.score
17    }
18
19    /// The indices of the matched characters of the text, counted in `char`s, ascending: what a
20    /// list draws in the match colour.
21    #[must_use]
22    pub fn positions(&self) -> &[usize] {
23        &self.positions
24    }
25}
26
27/// Matches `query` against `text`, ignoring case and spaces in the query: every query
28/// character must appear in order. Consecutive characters and characters at word starts score
29/// higher. An empty query matches everything with score 0.
30///
31/// This is the rule the framework's filter, command palette and pickers find with, so an
32/// application's own search that uses it finds what they find.
33///
34/// ```
35/// use qframe::text::fuzzy;
36///
37/// let found = fuzzy("rst", "Restart container").expect("every letter appears in order");
38/// assert_eq!(found.positions(), &[0, 2, 3]);
39/// assert!(fuzzy("tsr", "Restart").is_none());
40/// let word_start = fuzzy("ol", "Open logs").expect("matches").score();
41/// let inside = fuzzy("ol", "Pool").expect("matches").score();
42/// assert!(word_start > inside);
43/// ```
44#[must_use]
45pub fn fuzzy(query: &str, text: &str) -> Option<FuzzyMatch> {
46    // Both sides keep the first character of a lower case form, so a letter such as `İ`, whose
47    // lower case is two characters, compares equal to itself.
48    let lower_char = |c: char| c.to_lowercase().next().unwrap_or(c);
49    let wanted: Vec<char> = query.chars().filter(|c| !c.is_whitespace()).map(lower_char).collect();
50    if wanted.is_empty() {
51        return Some(FuzzyMatch { score: 0, positions: Vec::new() });
52    }
53    let chars: Vec<char> = text.chars().collect();
54    let lower: Vec<char> = chars.iter().copied().map(lower_char).collect();
55    let word_start = |i: usize| {
56        i == 0 || !chars[i - 1].is_alphanumeric() || (chars[i].is_uppercase() && chars[i - 1].is_lowercase())
57    };
58    // Try every place the first character occurs and keep the best greedy alignment.
59    let mut best: Option<FuzzyMatch> = None;
60    for first in (0..lower.len()).filter(|i| lower[*i] == wanted[0]) {
61        let mut positions = vec![first];
62        let mut at = first;
63        for c in &wanted[1..] {
64            let Some(next) = (at + 1..lower.len()).find(|i| lower[*i] == *c) else {
65                break;
66            };
67            positions.push(next);
68            at = next;
69        }
70        if positions.len() < wanted.len() {
71            break;
72        }
73        let mut score = 0;
74        for (index, position) in positions.iter().enumerate() {
75            score += 1;
76            if word_start(*position) {
77                score += 4;
78            }
79            if index > 0 && positions[index - 1] + 1 == *position {
80                score += 3;
81            }
82        }
83        score -= i32::try_from(positions[positions.len() - 1] - positions[0]).unwrap_or(i32::MAX / 2) / 4;
84        score -= i32::try_from(first).unwrap_or(0).min(8) / 4;
85        if best.as_ref().is_none_or(|b| score > b.score) {
86            best = Some(FuzzyMatch { score, positions });
87        }
88    }
89    best
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95
96    #[test]
97    fn matches_in_order_ignoring_case() {
98        let found = fuzzy("rst", "Restart container").expect("matches");
99        assert_eq!(found.positions, vec![0, 2, 3]);
100        assert!(fuzzy("tsr", "Restart").is_none());
101        assert_eq!(fuzzy("", "anything").map(|m| m.score), Some(0));
102        assert_eq!(fuzzy("o l", "Open logs").map(|m| m.positions), Some(vec![0, 5]));
103    }
104
105    #[test]
106    fn a_letter_whose_lower_case_is_two_characters_matches_itself() {
107        // `İ` lowers to `i` and a combining dot; the text side keeps only the `i`, so the query
108        // must do the same or Turkish names never match.
109        assert_eq!(fuzzy("İz", "İzmir").map(|m| m.positions), Some(vec![0, 1]));
110        assert_eq!(fuzzy("iz", "İzmir").map(|m| m.positions), Some(vec![0, 1]));
111    }
112
113    #[test]
114    fn word_starts_and_runs_score_higher() {
115        let starts = fuzzy("ol", "Open logs").expect("matches").score;
116        let middle = fuzzy("ol", "Pool").expect("matches").score;
117        assert!(starts > middle, "{starts} {middle}");
118        let run = fuzzy("dep", "Deploy").expect("matches").score;
119        let spread = fuzzy("dep", "Delete old snapshots and prune").expect("matches").score;
120        assert!(run > spread);
121        let better = fuzzy("log", "Toggle logs").expect("matches");
122        assert_eq!(better.positions, vec![7, 8, 9], "the word start beats the first occurrence");
123    }
124}
qframe/text/fuzzy.rs

qframe/text/
fuzzy.rs
