egui_charts/ui_kit/command_palette/
fuzzy.rs

1//! Fuzzy search implementation for command palette
2
3/// Result of a fuzzy match
4#[derive(Debug, Clone)]
5pub struct FuzzyMatch {
6    /// Match score (higher is better)
7    pub score: i32,
8    /// Indices in the target string that matched
9    pub matched_indices: Vec<usize>,
10}
11
12/// Perform fuzzy matching of a query against a target string
13///
14/// Returns `Some(FuzzyMatch)` if the query matches, `None` otherwise.
15/// The match is case-insensitive and supports non-contiguous matching.
16pub fn fuzzy_match(query: &str, target: &str) -> Option<FuzzyMatch> {
17    if query.is_empty() {
18        return Some(FuzzyMatch {
19            score: 0,
20            matched_indices: Vec::new(),
21        });
22    }
23
24    let query_lower: Vec<char> = query.to_lowercase().chars().collect();
25    let target_lower: Vec<char> = target.to_lowercase().chars().collect();
26
27    let mut score = 0i32;
28    let mut matched_indices = Vec::new();
29    let mut query_idx = 0;
30    let mut prev_matched = false;
31    let mut prev_was_separator = true; // Start of string counts as separator
32
33    for (target_idx, &target_char) in target_lower.iter().enumerate() {
34        let is_separator = target_char == ' ' || target_char == '_' || target_char == '-';
35
36        if query_idx < query_lower.len() && target_char == query_lower[query_idx] {
37            matched_indices.push(target_idx);
38            query_idx += 1;
39
40            // Scoring bonuses
41            if prev_matched {
42                // Consecutive match bonus
43                score += 15;
44            }
45            if prev_was_separator {
46                // Word boundary bonus (match at start of word)
47                score += 20;
48            }
49            if target_idx == 0 {
50                // First character bonus
51                score += 25;
52            }
53
54            // Base score for a match
55            score += 10;
56            prev_matched = true;
57        } else {
58            prev_matched = false;
59        }
60
61        prev_was_separator = is_separator;
62    }
63
64    // Did we match all query characters?
65    if query_idx == query_lower.len() {
66        // Penalty for unmatched characters
67        let unmatched_count = target_lower.len() - matched_indices.len();
68        score -= unmatched_count as i32;
69
70        // Bonus for exact match
71        if matched_indices.len() == target_lower.len() {
72            score += 50;
73        }
74
75        Some(FuzzyMatch {
76            score,
77            matched_indices,
78        })
79    } else {
80        None
81    }
82}
83
84/// Search through a list of items and return matches sorted by score
85pub fn fuzzy_search<'a, T>(
86    query: &str,
87    items: &'a [T],
88    get_text: impl Fn(&T) -> &str,
89) -> Vec<(&'a T, FuzzyMatch)> {
90    let mut matches: Vec<_> = items
91        .iter()
92        .filter_map(|item| fuzzy_match(query, get_text(item)).map(|m| (item, m)))
93        .collect();
94
95    // Sort by score (descending)
96    matches.sort_by_key(|m| std::cmp::Reverse(m.1.score));
97
98    matches
99}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104
105    #[test]
106    fn matches_subsequences_case_insensitively() {
107        for (query, target, indices) in [
108            ("", "hello", Some(&[][..])),
109            ("hello", "hello", Some(&[0, 1, 2, 3, 4][..])),
110            ("nch", "new chart", Some(&[0, 4, 5][..])),
111            ("xyz", "hello", None),
112            ("HELLO", "hello", Some(&[0, 1, 2, 3, 4][..])),
113        ] {
114            let result = fuzzy_match(query, target);
115            assert_eq!(
116                result.as_ref().map(|m| m.matched_indices.as_slice()),
117                indices,
118                "{query:?} in {target:?}"
119            );
120            if query.is_empty() {
121                assert_eq!(result.unwrap().score, 0);
122            }
123        }
124    }
125
126    #[test]
127    fn test_word_boundary_bonus() {
128        // "nc" should score higher on "New Chart" than "branch"
129        // because N matches at word boundary
130        let score_nc = fuzzy_match("nc", "New Chart").unwrap().score;
131        let score_branch = fuzzy_match("nc", "branch").unwrap().score;
132        assert!(score_nc > score_branch);
133    }
134}
egui_charts/ui_kit/command_palette/fuzzy.rs

egui_charts/ui_kit/command_palette/
fuzzy.rs
