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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

// This file is part of the uutils coreutils package.
//
// For the full copyright and license information, please view the LICENSE
// file that was distributed with this source code.

use memchr::{memchr, memchr2};

// Find the next matching byte sequence positions
// Return (first, last) where haystack[first..last] corresponds to the matched pattern
pub trait Matcher {
    fn next_match(&self, haystack: &[u8]) -> Option<(usize, usize)>;
}

// Matches for the exact byte sequence pattern
pub struct ExactMatcher<'a> {
    needle: &'a [u8],
}

impl<'a> ExactMatcher<'a> {
    pub fn new(needle: &'a [u8]) -> Self {
        assert!(!needle.is_empty());
        Self { needle }
    }
}

impl<'a> Matcher for ExactMatcher<'a> {
    fn next_match(&self, haystack: &[u8]) -> Option<(usize, usize)> {
        let mut pos = 0usize;
        loop {
            match memchr(self.needle[0], &haystack[pos..]) {
                Some(match_idx) => {
                    let match_idx = match_idx + pos; // account for starting from pos
                    if self.needle.len() == 1
                        || haystack[match_idx + 1..].starts_with(&self.needle[1..])
                    {
                        return Some((match_idx, match_idx + self.needle.len()));
                    } else {
                        pos = match_idx + 1;
                    }
                }
                None => {
                    return None;
                }
            }
        }
    }
}

// Matches for any number of SPACE or TAB
pub struct WhitespaceMatcher {}

impl Matcher for WhitespaceMatcher {
    fn next_match(&self, haystack: &[u8]) -> Option<(usize, usize)> {
        match memchr2(b' ', b'\t', haystack) {
            Some(match_idx) => {
                let mut skip = match_idx + 1;
                while skip < haystack.len() {
                    match haystack[skip] {
                        b' ' | b'\t' => skip += 1,
                        _ => break,
                    }
                }
                Some((match_idx, skip))
            }
            None => None,
        }
    }
}

#[cfg(test)]
mod matcher_tests {

    use super::*;

    #[test]
    fn test_exact_matcher_single_byte() {
        let matcher = ExactMatcher::new(":".as_bytes());
        // spell-checker:disable
        assert_eq!(matcher.next_match("".as_bytes()), None);
        assert_eq!(matcher.next_match(":".as_bytes()), Some((0, 1)));
        assert_eq!(matcher.next_match(":abcxyz".as_bytes()), Some((0, 1)));
        assert_eq!(matcher.next_match("abc:xyz".as_bytes()), Some((3, 4)));
        assert_eq!(matcher.next_match("abcxyz:".as_bytes()), Some((6, 7)));
        assert_eq!(matcher.next_match("abcxyz".as_bytes()), None);
        // spell-checker:enable
    }

    #[test]
    fn test_exact_matcher_multi_bytes() {
        let matcher = ExactMatcher::new("<>".as_bytes());
        // spell-checker:disable
        assert_eq!(matcher.next_match("".as_bytes()), None);
        assert_eq!(matcher.next_match("<>".as_bytes()), Some((0, 2)));
        assert_eq!(matcher.next_match("<>abcxyz".as_bytes()), Some((0, 2)));
        assert_eq!(matcher.next_match("abc<>xyz".as_bytes()), Some((3, 5)));
        assert_eq!(matcher.next_match("abcxyz<>".as_bytes()), Some((6, 8)));
        assert_eq!(matcher.next_match("abcxyz".as_bytes()), None);
        // spell-checker:enable
    }

    #[test]
    fn test_whitespace_matcher_single_space() {
        let matcher = WhitespaceMatcher {};
        // spell-checker:disable
        assert_eq!(matcher.next_match("".as_bytes()), None);
        assert_eq!(matcher.next_match(" ".as_bytes()), Some((0, 1)));
        assert_eq!(matcher.next_match("\tabcxyz".as_bytes()), Some((0, 1)));
        assert_eq!(matcher.next_match("abc\txyz".as_bytes()), Some((3, 4)));
        assert_eq!(matcher.next_match("abcxyz ".as_bytes()), Some((6, 7)));
        assert_eq!(matcher.next_match("abcxyz".as_bytes()), None);
        // spell-checker:enable
    }

    #[test]
    fn test_whitespace_matcher_multi_spaces() {
        let matcher = WhitespaceMatcher {};
        // spell-checker:disable
        assert_eq!(matcher.next_match("".as_bytes()), None);
        assert_eq!(matcher.next_match(" \t ".as_bytes()), Some((0, 3)));
        assert_eq!(matcher.next_match("\t\tabcxyz".as_bytes()), Some((0, 2)));
        assert_eq!(matcher.next_match("abc \txyz".as_bytes()), Some((3, 5)));
        assert_eq!(matcher.next_match("abcxyz  ".as_bytes()), Some((6, 8)));
        assert_eq!(matcher.next_match("abcxyz".as_bytes()), None);
        // spell-checker:enable
    }
}