skim 5.1.0

Fuzzy Finder in rust!
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

//! Fuzzy matching algorithms and implementations.
//!
//! This module provides different fuzzy matching algorithms including
//! skim's own algorithm and clangd's algorithm for matching text patterns.

/// Arinae fuzzy matching algorithm (Smith-Waterman with affine gaps)
pub mod arinae;
/// Clangd fuzzy matching algorithm
pub mod clangd;
#[cfg(feature = "frizbee")]
pub mod frizbee;
/// Fzy fuzzy matching algorithm
pub mod fzy;
/// Skim fuzzy matching algorithm
pub mod skim;
mod util;

pub(crate) type IndexType = usize;
pub(crate) type ScoreType = i64;

pub(crate) type MatchIndices = Vec<IndexType>;

/// Trait for fuzzy matching text patterns against choices
pub trait FuzzyMatcher: Send + Sync {
    /// fuzzy match choice with pattern, and return the score & matched indices of characters
    fn fuzzy_indices(&self, choice: &str, pattern: &str) -> Option<(i64, MatchIndices)>;

    /// fuzzy match choice with pattern, and return the score of matching
    fn fuzzy_match(&self, choice: &str, pattern: &str) -> Option<i64> {
        self.fuzzy_indices(choice, pattern).map(|(score, _)| score)
    }

    /// Fuzzy match and return (score, `begin_char_index`, `end_char_index`) without
    /// computing per-character match indices. This avoids the Vec allocation and
    /// traceback that `fuzzy_indices` requires, making it much faster for ranking.
    ///
    /// `begin` is the character index of the first matched pattern character,
    /// `end` is the character index of the last matched pattern character.
    ///
    /// Default implementation falls back to `fuzzy_indices`.
    fn fuzzy_match_range(&self, choice: &str, pattern: &str) -> Option<(i64, usize, usize)> {
        self.fuzzy_indices(choice, pattern).map(|(score, indices)| {
            let begin = indices.first().copied().unwrap_or(0);
            let end = indices.last().copied().unwrap_or(0);
            (score, begin, end)
        })
    }
}

#[cfg(test)]
#[cfg_attr(coverage, coverage(off))]
mod tests {
    use super::*;

    /// A matcher that only implements `fuzzy_indices`, so it exercises the
    /// default `fuzzy_match` / `fuzzy_match_range` implementations.
    struct StubMatcher;

    impl FuzzyMatcher for StubMatcher {
        fn fuzzy_indices(&self, choice: &str, pattern: &str) -> Option<(i64, MatchIndices)> {
            if pattern.is_empty() {
                return Some((0, vec![]));
            }
            // Match only when the pattern is a prefix of the choice.
            choice
                .starts_with(pattern)
                .then(|| (10, (0..pattern.chars().count()).collect()))
        }
    }

    #[test]
    fn default_fuzzy_match_uses_indices_score() {
        assert_eq!(StubMatcher.fuzzy_match("hello", "he"), Some(10));
        assert_eq!(StubMatcher.fuzzy_match("hello", "xy"), None);
    }

    #[test]
    fn default_fuzzy_match_range_spans_first_to_last() {
        assert_eq!(StubMatcher.fuzzy_match_range("hello", "hel"), Some((10, 0, 2)));
        assert_eq!(StubMatcher.fuzzy_match_range("hello", "zz"), None);
    }

    #[test]
    fn default_fuzzy_match_range_empty_indices_default_to_zero() {
        // Empty pattern yields an empty index list, so begin/end fall back to 0.
        assert_eq!(StubMatcher.fuzzy_match_range("hello", ""), Some((0, 0, 0)));
    }
}