pag_lexer/
regex_tree.rs

1// Copyright (c) 2023 Paguroidea Developers
2//
3// Licensed under the Apache License, Version 2.0
4// <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0> or the MIT
5// license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6// option. All files in the project carrying such notice may not be copied,
7// modified, or distributed except according to those terms.
8
9use crate::intervals::{Interval, Intervals};
10use std::fmt::{Display, Formatter};
11use std::ops::RangeInclusive;
12use std::rc::Rc;
13
14#[derive(Ord, PartialOrd, Eq, PartialEq, Debug, Clone, Hash)]
15pub enum RegexTree {
16    Top,
17    // any character
18    Bottom,
19    // no character
20    Set(Intervals),
21    Epsilon,
22    Concat(Rc<RegexTree>, Rc<RegexTree>),
23    KleeneClosure(Rc<RegexTree>),
24    Union(Rc<RegexTree>, Rc<RegexTree>),
25    Intersection(Rc<RegexTree>, Rc<RegexTree>),
26    Complement(Rc<RegexTree>),
27}
28
29impl Display for RegexTree {
30    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
31        match self {
32            RegexTree::Top => {
33                write!(f, "⊤")
34            }
35            RegexTree::Bottom => {
36                write!(f, "⊥")
37            }
38            RegexTree::Set(x) => {
39                write!(f, "{}", x)
40            }
41            RegexTree::Epsilon => {
42                write!(f, "ε")
43            }
44            RegexTree::Concat(x, y) => {
45                write!(f, "({} ~ {})", x, y)
46            }
47            RegexTree::KleeneClosure(x) => {
48                write!(f, "{}*", x)
49            }
50            RegexTree::Union(x, y) => {
51                write!(f, "({} ∪ {})", x, y)
52            }
53            RegexTree::Intersection(x, y) => {
54                write!(f, "({} ∩ {})", x, y)
55            }
56            RegexTree::Complement(x) => {
57                write!(f, "¬({})", x)
58            }
59        }
60    }
61}
62
63impl RegexTree {
64    pub fn single(x: u8) -> Self {
65        unsafe { RegexTree::Set(Intervals::new([Interval(x, x)]).unwrap_unchecked()) }
66    }
67    pub fn range(x: RangeInclusive<u8>) -> Self {
68        if x.is_empty() {
69            return RegexTree::Bottom;
70        }
71        match Intervals::new([Interval(*x.start(), *x.end())]) {
72            Some(set) => RegexTree::Set(set),
73            None => RegexTree::Bottom,
74        }
75    }
76    pub fn mangle(&self) -> String {
77        match self {
78            RegexTree::Top => "T".to_string(),
79            RegexTree::Bottom => "B".to_string(),
80            RegexTree::Set(x) => x.mangle(),
81            RegexTree::Epsilon => "E".to_string(),
82            RegexTree::Concat(x, y) => {
83                let x = x.mangle();
84                let y = y.mangle();
85                format!("C{}{}{}{}", x.len(), x, y.len(), y)
86            }
87            RegexTree::KleeneClosure(x) => {
88                let x = x.mangle();
89                format!("K{}{}", x.len(), x)
90            }
91            RegexTree::Union(x, y) => {
92                let x = x.mangle();
93                let y = y.mangle();
94                format!("U{}{}{}{}", x.len(), x, y.len(), y)
95            }
96            RegexTree::Intersection(x, y) => {
97                let x = x.mangle();
98                let y = y.mangle();
99                format!("I{}{}{}{}", x.len(), x, y.len(), y)
100            }
101            RegexTree::Complement(x) => {
102                let x = x.mangle();
103                format!("N{}{}", x.len(), x)
104            }
105        }
106    }
107    pub fn is_nullable(&self) -> bool {
108        match self {
109            RegexTree::Top => false,
110            RegexTree::Bottom => false,
111            RegexTree::Set(_) => false,
112            RegexTree::Epsilon => true,
113            RegexTree::Concat(left, right) => left.is_nullable() && right.is_nullable(),
114            RegexTree::KleeneClosure(_) => true,
115            RegexTree::Union(left, right) => left.is_nullable() || right.is_nullable(),
116            RegexTree::Intersection(left, right) => left.is_nullable() && right.is_nullable(),
117            RegexTree::Complement(r) => !r.is_nullable(),
118        }
119    }
120}
pag_lexer/regex_tree.rs

pag_lexer/
regex_tree.rs
