kaptein_viewmodel/
fuzzy.rs

1//! Fuzzy matching — the "fuzzy jump" semantic (M1.2).
2//!
3//! A renderer-agnostic subsequence matcher: a query matches a candidate when all of the
4//! query's characters appear in order within the candidate (case-insensitive). Matches
5//! score higher when they are contiguous, anchored at the start, or align with
6//! word/camel-case boundaries — the classic fuzzy-finder (fzf-style) behavior.
7//!
8//! The frontends call this with the current list of resource names and a typed query; it
9//! returns a ranked list of matches. No I/O, no rendering — pure semantics.
10
11/// A single fuzzy-match result, carrying a score (higher = better) for ranking.
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub struct FuzzyMatch {
14    /// The matched candidate string (e.g. a resource name).
15    pub candidate: String,
16    /// Match score: higher is better.
17    pub score: i32,
18}
19
20/// Score and rank `candidates` against a fuzzy `query`. Returns only matches, ordered
21/// best-first. An empty query matches everything at score 0 (preserving input order for
22/// stable output).
23pub fn fuzzy_jump<'a>(
24    candidates: impl IntoIterator<Item = &'a str>,
25    query: &str,
26) -> Vec<FuzzyMatch> {
27    let query = query.trim().to_ascii_lowercase();
28    if query.is_empty() {
29        return candidates
30            .into_iter()
31            .map(|c| FuzzyMatch {
32                candidate: c.to_string(),
33                score: 0,
34            })
35            .collect();
36    }
37
38    let mut matches: Vec<FuzzyMatch> = candidates
39        .into_iter()
40        .filter_map(|candidate| {
41            fuzzy_score(candidate, &query).map(|score| FuzzyMatch {
42                candidate: candidate.to_string(),
43                score,
44            })
45        })
46        .collect();
47
48    // Sort best-first; ties broken by candidate name for determinism.
49    matches.sort_by(|a, b| {
50        b.score
51            .cmp(&a.score)
52            .then_with(|| a.candidate.cmp(&b.candidate))
53    });
54    matches
55}
56
57/// Compute the fuzzy-match score of a candidate against a query, or `None` if the query
58/// is not a subsequence of the candidate.
59fn fuzzy_score(candidate: &str, query: &str) -> Option<i32> {
60    let lower = candidate.to_ascii_lowercase();
61    let candidate_chars: Vec<char> = lower.chars().collect();
62    let query_chars: Vec<char> = query.chars().collect();
63
64    if query_chars.is_empty() {
65        return Some(0);
66    }
67
68    // Subsequence check with scoring.
69    let mut score: i32 = 0;
70    let mut qi = 0usize; // index into query_chars
71    let mut prev_match: Option<usize> = None;
72
73    for (ci, c) in candidate_chars.iter().enumerate() {
74        if qi < query_chars.len() && *c == query_chars[qi] {
75            // Base score for matching a character.
76            score += 1;
77
78            if let Some(prev) = prev_match {
79                // Consecutive matches are worth more.
80                if ci == prev + 1 {
81                    score += 3;
82                }
83            } else if ci == 0 {
84                // Match at the very start of the candidate.
85                score += 4;
86            } else {
87                // Match after a word/camel boundary.
88                let prev_char = candidate_chars[ci - 1];
89                if prev_char == ' '
90                    || prev_char == '-'
91                    || prev_char == '_'
92                    || prev_char == '.'
93                    || prev_char.is_uppercase()
94                {
95                    score += 2;
96                }
97            }
98            prev_match = Some(ci);
99            qi += 1;
100        }
101    }
102
103    // All query chars must have matched in order.
104    if qi == query_chars.len() {
105        Some(score)
106    } else {
107        None
108    }
109}
110
111#[cfg(test)]
112mod tests {
113    use super::*;
114
115    #[test]
116    fn subsequence_matches_rank_contiguous_higher() {
117        let names = ["nginx-ingress-controller", "nagios", "nginxxxxxxxxx"];
118        let ranked = fuzzy_jump(names, "nginx");
119        // "nginx" as a contiguous prefix ranks first.
120        assert_eq!(ranked[0].candidate, "nginx-ingress-controller");
121    }
122
123    #[test]
124    fn empty_query_matches_all() {
125        let names = ["a", "b"];
126        let ranked = fuzzy_jump(names, "");
127        assert_eq!(ranked.len(), 2);
128    }
129
130    #[test]
131    fn no_match_returns_empty() {
132        let names = ["pod-a", "pod-b"];
133        let ranked = fuzzy_jump(names, "zzz");
134        assert!(ranked.is_empty());
135    }
136
137    #[test]
138    fn case_insensitive() {
139        let names = ["Deployment"];
140        let ranked = fuzzy_jump(names, "DEP");
141        assert_eq!(ranked.len(), 1);
142    }
143
144    #[test]
145    fn camel_case_boundary_boost() {
146        let names = ["imagePullBackOff", "ImagePullError"];
147        let ranked = fuzzy_jump(names, "ipbo");
148        // Both are subsequence matches; the camel-boundary-aligned one ranks first.
149        assert_eq!(ranked[0].candidate, "imagePullBackOff");
150    }
151}
kaptein_viewmodel/fuzzy.rs

kaptein_viewmodel/
fuzzy.rs
