brzozowski_regex/
nullability.rs

1// Copyright 2024 Hendrik van Antwerpen
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Nullability of regular expressions.
16
17use crate::builder::Builder;
18use crate::builder::Regex;
19
20impl<B: Builder> Regex<B> {
21    /// Returns whether the empty string is in the language of this regular expression.
22    pub fn is_nullable(&self) -> bool {
23        match self {
24            Self::EmptySet => false,
25            Self::EmptyString => true,
26            Self::Symbol(_) => false,
27            Self::Concat(left, right) => left.is_nullable() && right.is_nullable(),
28            Self::Closure(_) => true,
29            Self::Or(left, right) => left.is_nullable() || right.is_nullable(),
30            Self::And(left, right) => left.is_nullable() && right.is_nullable(),
31            Self::Complement(inner) => !inner.is_nullable(),
32        }
33    }
34
35    /// Returns empty string if this regular expression is nullable, otherwise returns empty set.
36    pub fn nullable(&self) -> Regex<B> {
37        if self.is_nullable() {
38            Self::EmptyString
39        } else {
40            Self::EmptySet
41        }
42    }
43}
44
45#[cfg(test)]
46mod tests {
47    use crate::builder::ApproximatelySimilarCanonical;
48    use crate::builder::Pure;
49    use crate::ops::*;
50
51    use super::*;
52
53    #[test]
54    fn test_is_nullable_pure() {
55        test_is_nullable::<Pure<_>>();
56    }
57
58    #[test]
59    fn test_is_nullable_asc() {
60        test_is_nullable::<ApproximatelySimilarCanonical<_>>();
61    }
62
63    fn test_is_nullable<B: Builder<Symbol = usize> + Clone>() {
64        let tests: Vec<(Regex<B>, bool)> = vec![
65            (!().r(), true),
66            ([].r(), true),
67            (42.s(), false),
68            (().r().c(), true),
69            (42.s().c(), true),
70            ([42.s(), [].r()].r(), false),
71            ([[].r(), 42.s()].r(), false),
72            ([[].r(), 42.s().c()].r(), true),
73            ((42.s() | [].r()), true),
74            (([].r() | 42.s()), true),
75            (([].r() | 42.s().c()), true),
76            ((42.s() & ().r()), false),
77            ((().r() & 42.s()), false),
78            (([].r() & 42.s().c()), true),
79            (([].r() & 42.s()), false),
80            (!().r(), true),
81            ((!42.s()), true),
82        ];
83        for test in tests {
84            assert_eq!(test.1, test.0.is_nullable());
85        }
86    }
87}
brzozowski_regex/nullability.rs

brzozowski_regex/
nullability.rs
