brzozowski_regex/
display.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//! Regular expression formatting.
16
17use crate::builder::Builder;
18use crate::builder::Regex;
19
20#[derive(Copy, Clone, Eq, PartialEq, PartialOrd, Ord)]
21enum Level {
22    None,
23    Binary,
24    Unary,
25    Atom,
26}
27
28#[derive(Copy, Clone, Eq, PartialEq)]
29enum Context {
30    Inner,
31    Left,
32}
33
34impl<B: Builder> std::fmt::Display for Regex<B>
35where
36    B::Symbol: std::fmt::Display,
37{
38    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
39        self.fmt(f, Context::Inner, Level::None)
40    }
41}
42
43impl<B: Builder> Regex<B>
44where
45    B::Symbol: std::fmt::Display,
46{
47    fn fmt(&self, f: &mut std::fmt::Formatter<'_>, ctx: Context, level: Level) -> std::fmt::Result {
48        match ctx {
49            Context::Inner | Context::Left if self.level() <= level => {
50                write!(f, "(")?;
51            }
52            _ => {}
53        }
54        match self {
55            Regex::EmptySet => write!(f, "∅")?,
56            Regex::EmptyString => write!(f, "ε")?,
57            Regex::Symbol(value) => write!(f, "{}", value)?,
58            Regex::Concat(left, right) => {
59                self.fmt_left(f, left, level)?;
60                write!(f, " ")?;
61                self.fmt_right_or_inner(f, right)?;
62            }
63            Regex::Closure(inner) => {
64                self.fmt_right_or_inner(f, inner)?;
65                write!(f, "*")?;
66            }
67            Regex::Or(left, right) => {
68                self.fmt_left(f, left, level)?;
69                write!(f, " | ")?;
70                self.fmt_right_or_inner(f, right)?;
71            }
72            Regex::And(left, right) => {
73                self.fmt_left(f, left, level)?;
74                write!(f, " & ")?;
75                self.fmt_right_or_inner(f, right)?;
76            }
77            Regex::Complement(inner) => {
78                write!(f, "¬")?;
79                self.fmt_right_or_inner(f, inner)?;
80            }
81        };
82        match ctx {
83            Context::Inner if self.level() <= level => {
84                write!(f, ")")?;
85            }
86            _ => {}
87        }
88        Ok(())
89    }
90
91    fn fmt_left(
92        &self,
93        f: &mut std::fmt::Formatter<'_>,
94        left: &Regex<B>,
95        outer_level: Level,
96    ) -> std::fmt::Result {
97        match (self, left) {
98            (Self::Concat(_, _), Self::Concat(_, _))
99            | (Self::Or(_, _), Self::Or(_, _))
100            | (Self::And(_, _), Self::And(_, _)) => left.fmt(f, Context::Left, outer_level),
101            _ => left.fmt(f, Context::Inner, self.level()),
102        }
103    }
104
105    fn fmt_right_or_inner(
106        &self,
107        f: &mut std::fmt::Formatter<'_>,
108        right_or_inner: &Regex<B>,
109    ) -> std::fmt::Result {
110        right_or_inner.fmt(f, Context::Inner, self.level())
111    }
112}
113
114impl<B: Builder> Regex<B> {
115    fn level(&self) -> Level {
116        match self {
117            Regex::EmptySet | Regex::EmptyString | Regex::Symbol(_) => Level::Atom,
118            Regex::Concat(_, _) | Regex::Or(_, _) | Regex::And(_, _) => Level::Binary,
119            Regex::Closure(_) | Regex::Complement(_) => Level::Unary,
120        }
121    }
122}
123
124#[cfg(test)]
125mod tests {
126    use crate::builder::Pure;
127    use crate::builder::Regex;
128    use crate::ops::*;
129
130    #[test]
131    fn test_display() {
132        let tests: Vec<(&str, Regex<Pure<usize>>)> = vec![
133            ("∅", ().r()),
134            ("¬∅", !().r()),
135            ("¬(11*)", !11.s().c()),
136            ("ε | 11*", [].r() | 11.s().c()),
137            ("¬∅ & (11 7)", !().r() & [11.s(), 7.s()].r()),
138            ("1 & 2 & 4", 1.s() & 2.s() & 4.s()),
139            ("1 & (2 & 4)", 1.s() & (2.s() & 4.s())),
140            ("(1 & 2) | 4", (1.s() & 2.s()) | 4.s()),
141            ("¬(1 2)", !(1.s() + 2.s())),
142        ];
143        for (expected, r) in tests {
144            assert_eq!(expected, r.to_string());
145        }
146    }
147}
brzozowski_regex/display.rs

brzozowski_regex/
display.rs
