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

//! Derivation and derivation-based matching for regular expressions.

use std::borrow::Borrow;

use crate::Builder;
use crate::Regex;

impl<B: Builder> Regex<B> {
    /// Returns the derivative of this regular expression w.r.t. to the given symbol.
    pub fn derive(&self, symbol: &B::Symbol) -> Regex<B>
    where
        B: Clone,
        B::Symbol: Clone + Eq,
    {
        match self {
            Self::EmptySet => B::empty_set(),
            Self::EmptyString => B::empty_set(),
            Self::Symbol(inner) => {
                if inner == symbol {
                    B::empty_string()
                } else {
                    B::empty_set()
                }
            }
            Self::Concat(left, right) => B::or(
                B::concat(left.derive(symbol), *right.clone()),
                B::concat(left.nullable(), right.derive(symbol)),
            ),
            Self::Closure(inner) => B::concat(inner.derive(symbol), B::closure(*inner.clone())),
            Self::Or(left, right) => B::or(left.derive(symbol), right.derive(symbol)),
            Self::And(left, right) => B::and(left.derive(symbol), right.derive(symbol)),
            Self::Complement(inner) => B::complement(inner.derive(symbol)),
        }
    }

    /// Returns the derivative of this regular expression w.r.t. the given symbols.
    pub fn derive_iter<I>(&self, symbols: impl IntoIterator<Item = I>) -> Regex<B>
    where
        B: Clone,
        B::Symbol: Clone + Eq,
        I: Borrow<B::Symbol>,
    {
        let mut d = self.clone();
        for symbol in symbols {
            d = d.derive(symbol.borrow());
        }
        d
    }

    /// Returns whether the string of symbols is in the language of this regular expression.
    pub fn is_match<I>(&self, symbols: impl IntoIterator<Item = I>) -> bool
    where
        B: Clone,
        B::Symbol: Clone + Eq,
        I: Borrow<B::Symbol>,
    {
        self.derive_iter(symbols).is_nullable()
    }
}

#[cfg(test)]
mod tests {
    use crate::ops::*;
    use crate::similarity::ApproximatelySimilarCanonical;
    use crate::Pure;

    use super::*;

    #[test]
    fn test_is_match_pure() {
        test_is_match::<Pure<_>>();
    }

    #[test]
    fn test_is_match_asc() {
        test_is_match::<ApproximatelySimilarCanonical<_>>();
    }

    fn test_is_match<B: Builder<Symbol = usize> + Clone>() {
        let tests: Vec<(Regex<B>, Vec<_>, bool)> = vec![
            ((().r()), vec![], false),
            (([].r()), vec![], true),
            (42.s(), vec![42], true),
            (42.s(), vec![42, 42], false),
            (42.s(), vec![11], false),
            ((![42.s()].r()), vec![], true),
            (([42.s()].r()), vec![42], true),
            (([42.s(), (11.s() | 7.s())].r()), vec![42], false),
            (([42.s(), (11.s() | 7.s())].r()), vec![42, 11], true),
            (([42.s(), (11.s() | 7.s())].r()), vec![42, 7], true),
            ((42.s().c()), vec![], true),
            ((42.s().c()), vec![42], true),
            ((42.s().c()), vec![42, 42, 42], true),
            ((42.s().c()), vec![42, 11], false),
            ((42.s() & [].r()), vec![42], false),
            ((42.s() & 42.s().c()), vec![42], true),
            ((42.s() & 42.s().c()), vec![42, 42], false),
            ((42.s() | 11.s()), vec![42], true),
            ((42.s() | 11.s()), vec![11], true),
            ((42.s() | 11.s()), vec![11, 42], false),
            ((42.s() | 11.s().c()), vec![42], true),
            ((42.s() | 11.s().c()), vec![11], true),
            ((42.s() | 11.s().c()), vec![11, 11], true),
            ((42.s() | 11.s().c()), vec![42, 11], false),
            ((!().r()), vec![11], true),
            ((!11.s()), vec![42], true),
            ((!11.s()), vec![11], false),
        ];
        for test in tests {
            assert_eq!(test.2, test.0.is_match(test.1));
        }
    }
}