wt/util/
fuzzy.rs

1//! Fuzzy filtering for `wt list --filter` and the TUI `/` filter (spec §7/§10),
2//! backed by `nucleo-matcher`.
3
4use nucleo_matcher::pattern::{CaseMatching, Normalization, Pattern};
5use nucleo_matcher::{Config, Matcher, Utf32Str};
6
7/// Returns the indices of `haystacks` that fuzzy-match `query`, ordered by
8/// descending score (ties keep input order). An empty query matches everything
9/// in input order.
10pub fn filter_indices(haystacks: &[String], query: &str) -> Vec<usize> {
11    if query.trim().is_empty() {
12        return (0..haystacks.len()).collect();
13    }
14    let mut matcher = Matcher::new(Config::DEFAULT);
15    let pattern = Pattern::parse(query, CaseMatching::Smart, Normalization::Smart);
16    let mut scored: Vec<(usize, u32)> = Vec::new();
17    let mut buf = Vec::new();
18    for (index, haystack) in haystacks.iter().enumerate() {
19        let utf32 = Utf32Str::new(haystack, &mut buf);
20        if let Some(score) = pattern.score(utf32, &mut matcher) {
21            scored.push((index, score));
22        }
23    }
24    scored.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
25    scored.into_iter().map(|(index, _)| index).collect()
26}
27
28#[cfg(test)]
29mod tests {
30    use super::*;
31
32    fn haystacks() -> Vec<String> {
33        vec![
34            "feature/login".to_string(),
35            "feature/logout".to_string(),
36            "main".to_string(),
37            "hotfix/crash".to_string(),
38        ]
39    }
40
41    #[test]
42    fn empty_query_returns_all_in_order() {
43        assert_eq!(filter_indices(&haystacks(), ""), vec![0, 1, 2, 3]);
44        assert_eq!(filter_indices(&haystacks(), "   "), vec![0, 1, 2, 3]);
45    }
46
47    #[test]
48    fn matches_subsequence() {
49        // "flog" fuzzily matches the feature/log* entries.
50        let result = filter_indices(&haystacks(), "flog");
51        assert!(result.contains(&0));
52        assert!(result.contains(&1));
53        assert!(!result.contains(&2));
54    }
55
56    #[test]
57    fn exact_substring_matches() {
58        let result = filter_indices(&haystacks(), "main");
59        assert_eq!(result, vec![2]);
60    }
61
62    #[test]
63    fn no_match_is_empty() {
64        assert!(filter_indices(&haystacks(), "zzzzz").is_empty());
65    }
66
67    #[test]
68    fn ranks_better_matches_first() {
69        // "hotfix" should rank the hotfix entry first.
70        let result = filter_indices(&haystacks(), "hotfix");
71        assert_eq!(result.first(), Some(&3));
72    }
73}
wt/util/fuzzy.rs

wt/util/
fuzzy.rs
