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
122
123

//! Brzozowski regular expressions.

use std::marker::PhantomData;

mod derivation;
mod nullability;
pub mod ops;
mod similarity;

pub use derivation::*;
pub use nullability::*;
pub use similarity::*;

/// Constructor methods for regular expressions.
pub trait Builder: Sized {
    type Symbol;

    fn empty_set() -> Regex<Self>;
    fn empty_string() -> Regex<Self>;
    fn symbol(value: Self::Symbol) -> Regex<Self>;
    fn closure(inner: Regex<Self>) -> Regex<Self>;
    fn concat(left: Regex<Self>, right: Regex<Self>) -> Regex<Self>;
    fn or(left: Regex<Self>, right: Regex<Self>) -> Regex<Self>;
    fn and(left: Regex<Self>, right: Regex<Self>) -> Regex<Self>;
    fn complement(inner: Regex<Self>) -> Regex<Self>;
}

/// Data type describing regular expressions over values of type S.
#[derive(Clone, Debug, Hash, PartialEq, Eq)]
pub enum Regex<B: Builder> {
    EmptySet,
    EmptyString,
    Symbol(B::Symbol),
    Concat(Box<Self>, Box<Self>),
    Closure(Box<Self>),
    Or(Box<Self>, Box<Self>),
    And(Box<Self>, Box<Self>),
    Complement(Box<Self>),
}

impl<B: Builder> Regex<B> {
    // Returns whether this regular expression is the complement of the empty set.
    pub(crate) fn is_empty_set_complement(&self) -> bool {
        if let Regex::Complement(inner) = self {
            matches!(inner.as_ref(), Regex::EmptySet)
        } else {
            false
        }
    }
}

impl<B: Builder> Regex<B>
where
    B::Symbol: Clone,
{
    /// Rebuild this regular expression using a different builder over the same symbol type.
    pub fn rebuild<X: Builder<Symbol = B::Symbol>>(&self) -> Regex<X> {
        match self {
            Regex::EmptySet => X::empty_set(),
            Regex::EmptyString => X::empty_string(),
            Regex::Symbol(value) => X::symbol(value.clone()),
            Regex::Concat(left, right) => X::concat(left.rebuild(), right.rebuild()),
            Regex::Closure(inner) => X::closure(inner.rebuild()),
            Regex::Or(left, right) => X::or(left.rebuild(), right.rebuild()),
            Regex::And(left, right) => X::and(left.rebuild(), right.rebuild()),
            Regex::Complement(inner) => X::complement(inner.rebuild()),
        }
    }
}

/// The recommended regular expression builder.
pub type Default<S> = ApproximatelySimilarCanonical<S>;

/// A pure regular expression builder that keeps the structure of the
/// constructor calls in the result
#[derive(Clone, Debug, Hash, PartialEq, Eq)]
pub struct Pure<S> {
    _phantom: PhantomData<S>,
}

impl<S> Builder for Pure<S> {
    type Symbol = S;

    #[inline]
    fn empty_set() -> Regex<Self> {
        Regex::EmptySet
    }

    #[inline]
    fn empty_string() -> Regex<Self> {
        Regex::EmptyString
    }

    #[inline]
    fn symbol(value: S) -> Regex<Self> {
        Regex::Symbol(value)
    }

    #[inline]
    fn closure(inner: Regex<Self>) -> Regex<Self> {
        Regex::Closure(inner.into())
    }

    #[inline]
    fn concat(left: Regex<Self>, right: Regex<Self>) -> Regex<Self> {
        Regex::Concat(left.into(), right.into())
    }

    #[inline]
    fn or(left: Regex<Self>, right: Regex<Self>) -> Regex<Self> {
        Regex::Or(left.into(), right.into())
    }

    #[inline]
    fn and(left: Regex<Self>, right: Regex<Self>) -> Regex<Self> {
        Regex::And(left.into(), right.into())
    }

    #[inline]
    fn complement(inner: Regex<Self>) -> Regex<Self> {
        Regex::Complement(inner.into())
    }
}