thndrs_lib/core/
fuzzy.rs

1/// Case-insensitive fuzzy subsequence matching.
2///
3/// Every query character must appear in order. Lower
4/// scores are better; matches at path boundaries and contiguous runs score
5/// ahead of spread-out matches.
6#[derive(Clone, Debug, Eq, PartialEq)]
7pub struct FuzzyMatch {
8    pub indices: Vec<usize>,
9    pub score: i32,
10}
11
12pub fn fuzzy_match(query: &str, text: &str) -> Option<FuzzyMatch> {
13    let query = query.trim();
14    if query.is_empty() {
15        return Some(FuzzyMatch { indices: Vec::new(), score: 0 });
16    }
17
18    let text_chars: Vec<char> = text.chars().collect();
19    let text_lower: Vec<char> = text.to_lowercase().chars().collect();
20    let query_lower: Vec<char> = query.to_lowercase().chars().collect();
21    if query_lower.len() > text_lower.len() {
22        return None;
23    }
24
25    let mut query_idx = 0usize;
26    let mut last_match: Option<usize> = None;
27    let mut indices = Vec::with_capacity(query_lower.len());
28    let mut score = 0i32;
29    let mut contiguous_run = 0i32;
30
31    for (idx, ch) in text_lower.iter().enumerate() {
32        if query_idx >= query_lower.len() {
33            break;
34        }
35        if *ch != query_lower[query_idx] {
36            continue;
37        }
38
39        if Some(idx.saturating_sub(1)) == last_match {
40            contiguous_run += 1;
41            score -= contiguous_run * 5;
42        } else {
43            contiguous_run = 0;
44            if let Some(prev) = last_match {
45                score += (idx.saturating_sub(prev + 1) as i32) * 2;
46            }
47        }
48
49        if is_path_boundary(&text_chars, idx) {
50            score -= 10;
51        }
52        score += (idx as i32).min(50);
53
54        indices.push(idx);
55        last_match = Some(idx);
56        query_idx += 1;
57    }
58
59    if query_idx != query_lower.len() {
60        return None;
61    }
62
63    if text.eq_ignore_ascii_case(query) {
64        score -= 100;
65    }
66
67    Some(FuzzyMatch { indices, score })
68}
69
70/// Filter items by fuzzy match, returning each result with matched character
71/// indices so callers can highlight which characters matched.
72pub fn fuzzy_filter(items: &[String], query: &str, limit: usize) -> Vec<(String, Vec<usize>)> {
73    let mut scored: Vec<(i32, &String, Vec<usize>)> = items
74        .iter()
75        .filter_map(|item| fuzzy_match(query, item).map(|m| (m.score, item, m.indices)))
76        .collect();
77    scored.sort_by(|(a_score, a_item, _), (b_score, b_item, _)| a_score.cmp(b_score).then_with(|| a_item.cmp(b_item)));
78    scored
79        .into_iter()
80        .take(limit)
81        .map(|(_, item, indices)| (item.clone(), indices))
82        .collect()
83}
84
85fn is_path_boundary(chars: &[char], idx: usize) -> bool {
86    idx == 0
87        || matches!(
88            chars.get(idx.saturating_sub(1)),
89            Some('/' | '\\' | '-' | '_' | '.' | ' ' | ':')
90        )
91}
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96
97    #[test]
98    fn fuzzy_match_prefers_exact_and_boundary_matches() {
99        let exact = fuzzy_match("app", "app").expect("match");
100        let nested = fuzzy_match("app", "src/app.rs").expect("match");
101        let spread = fuzzy_match("app", "alpha/path/provider.rs").expect("match");
102
103        assert!(exact.score < nested.score);
104        assert!(nested.score < spread.score);
105    }
106
107    #[test]
108    fn fuzzy_filter_sorts_best_matches_first_and_returns_indices() {
109        let items = vec![
110            "src/provider/app.rs".to_string(),
111            "src/app.rs".to_string(),
112            "README.md".to_string(),
113        ];
114
115        assert_eq!(
116            fuzzy_filter(&items, "app", 10),
117            vec![
118                ("src/app.rs".to_string(), vec![4, 5, 6]),
119                ("src/provider/app.rs".to_string(), vec![13, 14, 15]),
120            ]
121        );
122    }
123}
thndrs_lib/core/fuzzy.rs

thndrs_lib/core/
fuzzy.rs
