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

use parser;

/// The matcher struct holds a single query object.
pub struct Matcher
{
    query: parser::Node
}

impl Matcher
{
    /// Constructs a new Matcher object from a string.
    ///
    /// Returns a ParsingError if it fails.
    pub fn from(s: &str) -> parser::Result<Self>
    {
        match parser::from(s)
        {
            Ok(q) => return Ok(Matcher { query: q }),
            Err(e) => return Err(e),
        }
    }

    /// Applies the query to the string.
    pub fn query(&self, s: &str) -> bool
    {
        return match_bquery(&self.query, s)
    }
}

/// Applies `query` to `s`.
fn match_bquery(query: &parser::Node, s: &str) -> bool
{
    use parser::Node::*;
    match query
    {
        &AND(ref a, ref b) => return match_bquery(&*a, s) && match_bquery(&*b, s),
        &OR(ref a, ref b) => return match_bquery(&*a, s) || match_bquery(&*b, s),
        &NOT(ref a) => return !match_bquery(&*a, s),
        &Leaf(ref keyword, ref jumptable) => return kmp(jumptable, keyword, s),
    }
}

/// An implementation of the [Knuth-Morris-Pratt](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm) algorithm.
/// I didn't come up with this, it is taken from a C implementation that I found elsewhere.
///
/// Parameters:
/// `table`: The precomputed jump table.
/// `s1`: The string to search for.
/// `s2`: The text to search for s1 in.
fn kmp(table: &Vec<i64>, s1: &str, s2: &str) -> bool
{
    let s1 = s1
        .to_string()
        .to_lowercase()
        .into_bytes();

    let s2 = s2
        .to_string()
        .to_lowercase()
        .into_bytes();

    let mut i: i64 = 0;
    let mut j: i64 = -1;

    while i < s2.len() as i64
    {
        while (j > -1) & (s1[(j+1) as usize] != s2[i as usize])
        {
            j = table[j as usize];
        }

        if s2[i as usize] == s1[(j+1) as usize]
        {
            j += 1;
        }

        if j == (s1.len()as i64 -1)
        {
            return true;
        }

        i += 1;
    }

    return false;
}

#[cfg(test)]
mod tests
{
    use super::*;

    fn print_on_failure(m: &Matcher, s: &str)
    {
        assert!(m.query(s), "was trying to match the string '{}'", s);
    }

    #[test]
    fn test()
    {
        let iphonex = Matcher::from("\"iphone\" | \"i phone\"").unwrap();
        print_on_failure(&iphonex, "I love my new iphone!");
    }

    #[test]
    fn groups()
    {
        let greeting = Matcher::from("(\"hello\" | \"hi\") & \"there\")").unwrap();
        print_on_failure(&greeting, "hi there, my name is Kyuss Caesar");
        print_on_failure(&greeting, "hello there, this should also be a greeting");
    }

    #[test]
    fn casesens()
    {
        let greeting = Matcher::from("('hello'|'hi'|'ho') & 'there'").unwrap();
        print_on_failure(&greeting, "HELLO THERE");
        print_on_failure(&greeting, "hI THERE");
        print_on_failure(&greeting, "Hi there!");
    }
}