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
93
94
95
96
97
98
99
100
101

use crate::error::EngineError;

use super::*;

impl FastAutomaton {
    /// Returns `true` if all strings accepted by `self` are also accepted by `other`.
    ///
    /// A non-deterministic `other` is 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 subset(&self, other: &FastAutomaton) -> Result<bool, EngineError> {
        if self.is_empty() || other.is_total() || self == other {
            return Ok(true);
        } else if other.is_empty() {
            return Ok(false);
        } else if self.is_total() {
            // self ⊆ other iff Σ* ⊆ other iff other = Σ*. We already failed
            // the cheap `other.is_total()` check above; that check is sound
            // but conservative on NFAs, so retry on the determinized form.
            return Ok(other.determinize_implicit()?.is_total());
        }

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

        Ok(!self.has_intersection(&other)?)
    }
}

#[cfg(test)]
mod tests {

    use crate::regex::RegularExpression;

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

        assert_subset(
            &RegularExpression::new_total(),
            &RegularExpression::new_empty_string(),
            false,
            true,
        );

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

        assert_subset(&regex1, &regex2, false, false);

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

        assert_subset(&regex1, &regex2, false, true);

        let regex1 = RegularExpression::parse("(abc|def)", false).unwrap();
        let regex2 = RegularExpression::parse("(abc|def|xyz)", false).unwrap();

        assert_subset(&regex1, &regex2, true, false);

        let regex1 = RegularExpression::parse("[0]", false).unwrap();
        let regex2 = RegularExpression::parse("[01]", false).unwrap();

        assert_subset(&regex1, &regex2, true, false);

        let regex1 = RegularExpression::parse("a.*b.*c.*", false).unwrap();
        let regex2 = RegularExpression::parse("a.*b.*", false).unwrap();

        assert_subset(&regex1, &regex2, true, false);

        let regex1 = RegularExpression::parse("1..", false).unwrap();
        let regex2 = RegularExpression::parse("...", false).unwrap();

        assert_subset(&regex1, &regex2, true, false);

        Ok(())
    }

    fn assert_subset(
        regex_1: &RegularExpression,
        regex_2: &RegularExpression,
        expected_1_2: bool,
        expected_2_1: bool,
    ) {
        println!("{regex_1} and {regex_2}");
        let automaton_1 = regex_1.to_automaton().unwrap();
        assert!(automaton_1.subset(&automaton_1).unwrap());

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

        assert_eq!(expected_1_2, automaton_1.subset(&automaton_2).unwrap());
        assert_eq!(expected_2_1, automaton_2.subset(&automaton_1).unwrap());
    }
}