regexsolver 1.0.0

High-performance Rust library for building, combining, and analyzing regular expressions and finite automata
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
89
90
91
92

use crate::error::EngineError;

use super::*;

impl FastAutomaton {
    /// Returns `true` if both automata accept the same language.
    ///
    /// Non-deterministic operands are determinized internally, unless the
    /// execution profile disables implicit determinization, in which case
    /// [`EngineError::DeterministicAutomatonRequired`] is returned.
    #[tracing::instrument(level = "debug", skip_all, fields(self_states = self.number_of_states(), self_deterministic = self.is_deterministic(), other_states = other.number_of_states(), other_deterministic = other.is_deterministic()))]
    pub fn equivalent(&self, other: &FastAutomaton) -> Result<bool, EngineError> {
        // `is_empty` is exact, so a mismatch proves the languages differ.
        // (`is_total` must NOT be part of this fast path: it is conservative
        // on non-deterministic automata — it can return `false` for an
        // automaton that actually accepts every string — so an `is_total`
        // mismatch alone proves nothing.)
        if self.is_empty() != other.is_empty() {
            return Ok(false);
        } else if self == other {
            return Ok(true);
        }

        let mut other_complement = other.determinize_implicit()?.into_owned();
        other_complement.complement()?;

        if self.has_intersection(&other_complement)? {
            return Ok(false);
        }

        let mut self_complement = self.determinize_implicit()?.into_owned();
        self_complement.complement()?;

        Ok(!self_complement.has_intersection(other)?)
    }
}

#[cfg(test)]
mod tests {

    use crate::regex::RegularExpression;

    #[test]
    fn test_equivalent() -> Result<(), String> {
        assert_equivalent(
            &RegularExpression::new_empty(),
            &RegularExpression::new_empty_string(),
            false,
        );

        assert_equivalent(
            &RegularExpression::new_total(),
            &RegularExpression::new_empty_string(),
            false,
        );

        let regex_1 = RegularExpression::parse("cd", false).unwrap();
        let regex_2 = RegularExpression::parse("cd", false).unwrap();
        assert_equivalent(&regex_1, &regex_2, true);

        let regex_1 = RegularExpression::parse("test.*other", false).unwrap();
        let regex_2 = RegularExpression::parse("test.*othew", false).unwrap();

        assert_equivalent(&regex_1, &regex_2, false);

        let regex_1 = RegularExpression::parse("test.{0,50}other", false).unwrap();
        let regex_2 = RegularExpression::parse("test.{0,49}other", false).unwrap();

        assert_equivalent(&regex_1, &regex_2, false);

        let regex_1 = RegularExpression::parse("[0]", false).unwrap();
        let regex_2 = RegularExpression::parse("[01]", false).unwrap();
        assert_equivalent(&regex_1, &regex_2, false);

        let regex_1 = RegularExpression::parse("(b+a+)*", false).unwrap();
        let regex_2 = RegularExpression::parse("(b[a-b]*a)?", false).unwrap();
        assert_equivalent(&regex_1, &regex_2, true);

        Ok(())
    }

    fn assert_equivalent(regex_1: &RegularExpression, regex_2: &RegularExpression, expected: bool) {
        println!("{regex_1} and {regex_2}");
        let automaton_1 = regex_1.to_automaton().unwrap();
        assert!(automaton_1.equivalent(&automaton_1).unwrap());

        let automaton_2 = regex_2.to_automaton().unwrap();
        assert!(automaton_2.equivalent(&automaton_2).unwrap());

        assert_eq!(expected, automaton_1.equivalent(&automaton_2).unwrap());
    }
}