1use std::fmt::{Debug, Display};
2
3use crate::Atom;
4
5#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
6pub enum ASTNodeType {
7 Charcters,
8 Catenation,
9 Alternation,
10 ZeroOrOne,
11 ZeroOrMore,
12 OneOrMore,
13 Repeat,
14 RepeatExact,
15}
16
17pub enum ASTNode<A: Atom> {
18 Charcters {
19 start: A,
20 end: A,
21 negation: bool,
22 },
23 Catenation(Box<ASTNode<A>>, Box<ASTNode<A>>),
24 Alternation(Box<ASTNode<A>>, Box<ASTNode<A>>),
25 ZeroOrOne(Box<ASTNode<A>>),
26 ZeroOrMore(Box<ASTNode<A>>),
27 OneOrMore(Box<ASTNode<A>>),
28 Repeat {
29 node: Box<ASTNode<A>>,
30 at_least: usize,
31 at_most: Option<usize>,
32 },
33 RepeatExact(Box<ASTNode<A>>, usize),
34}
35
36impl<A: Atom> ASTNode<A> {
37 pub(crate) fn alternate_all(mut iter: impl Iterator<Item = (A, A)>) -> Option<Self> {
38 let (start, end) = iter.next()?;
39 let mut ret = ASTNode::Charcters {
40 start,
41 end,
42 negation: false,
43 };
44 for (start, end) in iter {
45 assert!(start <= end);
46 let alt = ASTNode::Charcters {
47 start,
48 end,
49 negation: false,
50 };
51 ret = ASTNode::Alternation(Box::new(ret), Box::new(alt));
52 }
53 Some(ret)
54 }
55
56 pub(crate) fn negate_all(iter: impl Iterator<Item = (A, A)>) -> Option<Self> {
57 let mut s = A::MIN;
58 let mut ret = None::<Self>;
59 for (start, end) in iter {
60 assert!(s <= start);
61 if let Some(end) = start.previous() {
62 assert!(s <= end);
63 let alt = ASTNode::Charcters {
64 start: s,
65 end,
66 negation: false,
67 };
68 if let Some(left) = ret {
69 ret = Some(ASTNode::Alternation(Box::new(left), Box::new(alt)));
70 } else {
71 ret = Some(alt);
72 }
73 }
74 if let Some(next) = end.next() {
75 s = next;
76 }
77 }
78 ret
79 }
80
81 pub fn node_type(&self) -> ASTNodeType {
82 match self {
83 Self::Charcters {
84 start: _,
85 end: _,
86 negation: _,
87 } => ASTNodeType::Charcters,
88 Self::Catenation(_, _) => ASTNodeType::Catenation,
89 Self::Alternation(_, _) => ASTNodeType::Alternation,
90 Self::ZeroOrOne(_) => ASTNodeType::ZeroOrOne,
91 Self::ZeroOrMore(_) => ASTNodeType::ZeroOrMore,
92 Self::OneOrMore(_) => ASTNodeType::OneOrMore,
93 Self::Repeat {
94 node: _,
95 at_least: _,
96 at_most: _,
97 } => ASTNodeType::Repeat,
98 Self::RepeatExact(_, _) => ASTNodeType::RepeatExact,
99 }
100 }
101}
102
103impl<A: Atom + Debug> std::fmt::Debug for ASTNode<A> {
104 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
105 use ASTNodeType::*;
106
107 match self {
108 &Self::Charcters {
109 start,
110 end,
111 negation,
112 } => {
113 if start <= end {
114 if start == end {
115 if negation {
116 write!(f, "[^{start:?}]")?;
117 } else {
118 write!(f, "{start:?}")?;
119 }
120 } else if negation {
121 write!(f, "[^{start:?}-{end:?}]")?;
122 } else {
123 write!(f, "[{start:?}-{end:?}]")?;
124 }
125 }
126 Ok(())
127 }
128 Self::Catenation(front, back) => {
129 write!(f, "{front:?}{back:?}")
130 }
131 Self::Alternation(left, right) => {
132 write!(f, "{left:?}|{right:?}")
133 }
134 Self::ZeroOrOne(node) => {
135 if matches!(node.node_type(), Charcters) {
136 write!(f, "{node:?}?")
137 } else {
138 write!(f, "({node:?})?")
139 }
140 }
141 Self::ZeroOrMore(node) => {
142 if matches!(node.node_type(), Charcters) {
143 write!(f, "{node:?}*")
144 } else {
145 write!(f, "({node:?})*")
146 }
147 }
148 Self::OneOrMore(node) => {
149 if matches!(node.node_type(), Charcters) {
150 write!(f, "{node:?}+")
151 } else {
152 write!(f, "({node:?})+")
153 }
154 }
155 Self::Repeat {
156 node,
157 at_least,
158 at_most,
159 } => {
160 if matches!(node.node_type(), Charcters) {
161 write!(f, "{node:?}{{{at_least},")?;
162 } else {
163 write!(f, "({node:?}){{{at_least},")?;
164 }
165 if let Some(at_most) = at_most {
166 write!(f, "{at_most}")?;
167 }
168 write!(f, "}}")
169 }
170 Self::RepeatExact(node, n) => {
171 if matches!(node.node_type(), Charcters) {
172 write!(f, "{node:?}{{{n}}}")
173 } else {
174 write!(f, "({node:?}){{{n}}}")
175 }
176 }
177 }
178 }
179}
180
181impl<A: Atom + Display> std::fmt::Display for ASTNode<A> {
182 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
183 use ASTNodeType::*;
184
185 match self {
186 &Self::Charcters {
187 start,
188 end,
189 negation,
190 } => {
191 if start <= end {
192 if start == end {
193 if negation {
194 write!(f, "[^{start}]")?;
195 } else {
196 write!(f, "{start}")?;
197 }
198 } else if negation {
199 write!(f, "[^{start}-{end}]")?;
200 } else {
201 write!(f, "[{start}-{end}]")?;
202 }
203 }
204 Ok(())
205 }
206 Self::Catenation(front, back) => {
207 write!(f, "{front}{back}")
208 }
209 Self::Alternation(left, right) => {
210 write!(f, "{left}|{right}")
211 }
212 Self::ZeroOrOne(node) => {
213 if matches!(node.node_type(), Charcters) {
214 write!(f, "{node}?")
215 } else {
216 write!(f, "({node})?")
217 }
218 }
219 Self::ZeroOrMore(node) => {
220 if matches!(node.node_type(), Charcters) {
221 write!(f, "{node}*")
222 } else {
223 write!(f, "({node})*")
224 }
225 }
226 Self::OneOrMore(node) => {
227 if matches!(node.node_type(), Charcters) {
228 write!(f, "{node}+")
229 } else {
230 write!(f, "({node})+")
231 }
232 }
233 Self::Repeat {
234 node,
235 at_least,
236 at_most,
237 } => {
238 if matches!(node.node_type(), Charcters) {
239 write!(f, "{node}{{{at_least},")?;
240 } else {
241 write!(f, "({node}){{{at_least},")?;
242 }
243 if let Some(at_most) = at_most {
244 write!(f, "{at_most}")?;
245 }
246 write!(f, "}}")
247 }
248 Self::RepeatExact(node, n) => {
249 if matches!(node.node_type(), Charcters) {
250 write!(f, "{node}{{{n}}}")
251 } else {
252 write!(f, "({node}){{{n}}}")
253 }
254 }
255 }
256 }
257}