neo_frizbee 0.5.0

Fast fuzzy matching via SIMD smith waterman, similar algorithm to FZF/FZY
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

use memchr::{memchr, memchr2};

pub fn prefilter(needle: &str, haystack: &str) -> bool {
    if needle.len() > haystack.len() {
        return false;
    }
    prefilter_ascii(needle.as_bytes(), haystack.as_bytes()).is_some()
}
pub fn prefilter_with_typo(needle: &str, haystack: &str) -> bool {
    if needle.len() > haystack.len() + 1 {
        return false;
    }
    prefilter_ascii_with_typo(needle.as_bytes(), haystack.as_bytes()).is_some()
}

/// Ripped directly from nucleo-matcher. It makes the algo much faster but disables resistance
/// to typos
#[inline(always)]
fn prefilter_ascii(needle: &[u8], mut haystack: &[u8]) -> Option<()> {
    // If the first char is later than the haystack.len() - needle.len() + 1, then the
    // haystack is too short to contain the needle
    let start = find_ascii_ignore_case(needle[0], &haystack[..haystack.len() - needle.len() + 1])?;
    haystack = &haystack[(start + 1)..];
    for &c in &needle[1..] {
        let idx = find_ascii_ignore_case(c, haystack)? + 1;
        haystack = &haystack[idx..];
    }
    Some(())
}

/// Same as prefilter_ascii but allows for a single typo
#[inline(always)]
fn prefilter_ascii_with_typo(needle: &[u8], mut haystack: &[u8]) -> Option<()> {
    if needle.len() < 2 {
        return Some(());
    }

    // If the first char is later than the haystack.len() - needle.len() + 1, then the
    // haystack is too short to contain the needle. We use +2 instead of +1 to account
    // for the possibility of a single typo
    let (mut typos, start) = find_two_ascii_ignore_case(
        needle[0],
        needle[1],
        &haystack[..haystack.len() - needle.len() + 2],
    )?;
    haystack = &haystack[(start + 1)..];
    let mut idx = typos + 1;
    while idx < needle.len() {
        // Found a match
        if let Some(match_idx) = find_ascii_ignore_case(needle[idx], haystack) {
            haystack = &haystack[(match_idx + 1)..];
        } else {
            typos += 1;
            if typos > 1 {
                return None;
            }
        }
        idx += 1;
    }
    Some(())
}

#[inline(always)]
fn find_two_ascii_ignore_case(c1: u8, c2: u8, haystack: &[u8]) -> Option<(usize, usize)> {
    if let Some(idx) = find_ascii_ignore_case(c1, haystack) {
        return Some((0, idx));
    } else if let Some(idx) = find_ascii_ignore_case(c2, haystack) {
        return Some((1, idx));
    }
    None
}

#[inline(always)]
fn find_ascii_ignore_case(c: u8, haystack: &[u8]) -> Option<usize> {
    if c.is_ascii_lowercase() {
        memchr2(c, c - 32, haystack)
    } else {
        memchr(c, haystack)
    }
}