1use std::{marker::PhantomData, mem};
2
3use crate::span::Spanned;
4
5mod example;
6
7#[derive(Debug, Clone, Copy, Eq, Hash, Ord, PartialEq, PartialOrd)]
8pub enum TokenType {
9 Value,
10 Precedence {
11 precedence: i8,
12 associativity: Associativity,
13 },
14}
15
16#[derive(Debug, Clone, Copy, Eq, Hash, Ord, PartialEq, PartialOrd)]
17pub enum Associativity {
18 Left,
20 Right,
22 ClosedRight,
24}
25
26pub trait IsResolvedToken {
27 fn get_type(&self) -> TokenType;
28}
29
30#[derive(Debug, Clone, Copy, Eq, Hash, Ord, PartialEq, PartialOrd)]
31pub enum OrderingBehaviour {
32 Right { precedence: i8, closed: bool },
33 SoftLeft { precedence: i8 },
34 ClosedLeft,
35}
36
37pub trait IsOrdering {
38 fn behaviour(&self) -> OrderingBehaviour;
39}
40
41pub enum StackEntry<T: IsResolvedToken, O: IsOrdering> {
42 Resolved(Spanned<T>),
43 Ordering(Spanned<O>),
44}
45
46pub trait FromStackEntry: Sized {
47 type Token: IsResolvedToken;
48 type Ordering: IsOrdering;
49
50 fn from_entry(token: &StackEntry<Self::Token, Self::Ordering>) -> Self;
51}
52
53pub type StackEntryToken<S> = <S as FromStackEntry>::Token;
54pub type StackEntryOrdering<S> = <S as FromStackEntry>::Ordering;
55pub type StackEntryFrom<S> = StackEntry<StackEntryToken<S>, StackEntryOrdering<S>>;
56
57pub trait HasStateTransition<T: ?Sized> {
58 type Token: IsResolvedToken;
59 type Ordering: IsOrdering;
60 type Error;
61
62 #[allow(clippy::type_complexity)]
63 fn transition(
64 self,
65 token: T,
66 ) -> Result<StackEntry<Self::Token, Self::Ordering>, Spanned<Self::Error>>;
67}
68
69pub trait IsState<T: IsResolvedToken, O: IsOrdering> {
70 type Error;
71
72 fn update(&mut self, token: &StackEntry<T, O>);
73
74 fn proccess_closed(&mut self, token: &mut Spanned<T>);
75
76 fn delete_closed_ordering(&mut self, ordering: Spanned<O>);
77
78 fn no_ordering_found(&self) -> Spanned<Self::Error>;
79}
80impl<T: IsResolvedToken, O: IsOrdering> IsState<T, O> for () {
81 type Error = ();
82
83 #[inline(always)]
84 fn update(&mut self, _: &StackEntry<T, O>) {}
85
86 #[inline(always)]
87 fn proccess_closed(&mut self, _: &mut Spanned<T>) {}
88
89 #[inline(always)]
90 fn delete_closed_ordering(&mut self, _: Spanned<O>) {}
91
92 #[inline(always)]
93 fn no_ordering_found(&self) -> Spanned<Self::Error> {
94 Spanned::default()
95 }
96}
97
98#[derive(Debug, Clone, Copy, Eq, Hash, Ord, PartialEq, PartialOrd)]
99pub enum ProcessTokenIteratorState<T: IsResolvedToken, O: IsOrdering> {
100 Pending,
101 ProcessResolved(Spanned<T>),
102 ProcessOrdering(Spanned<O>),
103 ClearingStack,
104 Completed,
105}
106
107pub struct CreateTokenProcessor<
108 T,
109 TS: FromStackEntry
110 + HasStateTransition<T, Token = StackEntryToken<TS>, Ordering = StackEntryOrdering<TS>>
111 + Default,
112 S: IsState<StackEntryToken<TS>, StackEntryOrdering<TS>>,
113> {
114 __raw_token: PhantomData<T>,
115 __tree_state: PhantomData<TS>,
116 __state: PhantomData<S>,
117}
118
119pub struct ProcessTokenIterator<
120 T,
121 TS: FromStackEntry
122 + HasStateTransition<T, Token = StackEntryToken<TS>, Ordering = StackEntryOrdering<TS>>
123 + Default,
124 S: IsState<StackEntryToken<TS>, StackEntryOrdering<TS>> + Default,
125 I: Iterator<Item = T>,
126> {
127 internal_state: ProcessTokenIteratorState<StackEntryToken<TS>, StackEntryOrdering<TS>>,
128 tokens: I,
129 tree_state: TS,
130 state: S,
131 stack: Vec<StackEntryFrom<TS>>,
132}
133
134impl<
135 T,
136 TS: FromStackEntry
137 + HasStateTransition<T, Token = StackEntryToken<TS>, Ordering = StackEntryOrdering<TS>>
138 + Default,
139 S: IsState<StackEntryToken<TS>, StackEntryOrdering<TS>, Error = TS::Error> + Default,
140> CreateTokenProcessor<T, TS, S>
141{
142 #[allow(clippy::new_ret_no_self)]
143 pub fn new(
144 iter: impl Iterator<Item = T>,
145 ) -> ProcessTokenIterator<T, TS, S, impl Iterator<Item = T>> {
146 ProcessTokenIterator {
147 internal_state: ProcessTokenIteratorState::Pending,
148 tokens: iter,
149 tree_state: TS::default(),
150 state: S::default(),
151 stack: Vec::new(),
152 }
153 }
154}
155
156impl<
157 T,
158 TS: FromStackEntry
159 + HasStateTransition<T, Token = StackEntryToken<TS>, Ordering = StackEntryOrdering<TS>>
160 + Default,
161 S: IsState<StackEntryToken<TS>, StackEntryOrdering<TS>, Error = TS::Error> + Default,
162 I: Iterator<Item = T>,
163> Iterator for ProcessTokenIterator<T, TS, S, I>
164{
165 type Item = Result<Spanned<StackEntryToken<TS>>, Spanned<TS::Error>>;
166
167 fn next(&mut self) -> Option<Self::Item> {
168 'main: loop {
169 match self.internal_state {
170 ProcessTokenIteratorState::Pending => {
171 let Some(token) = self.tokens.next() else {
172 self.internal_state = ProcessTokenIteratorState::ClearingStack;
173 continue 'main;
174 };
175
176 let entry = match mem::take(&mut self.tree_state).transition(token) {
177 Ok(entry) => entry,
178 Err(error) => {
179 self.internal_state = ProcessTokenIteratorState::Completed;
180 return Some(Err(error));
181 }
182 };
183
184 self.tree_state = TS::from_entry(&entry);
185 self.state.update(&entry);
186
187 self.internal_state = match entry {
188 StackEntry::Resolved(resolved) => {
189 ProcessTokenIteratorState::ProcessResolved(resolved)
190 }
191 StackEntry::Ordering(ordering) => {
192 ProcessTokenIteratorState::ProcessOrdering(ordering)
193 }
194 };
195
196 continue 'main;
197 }
198 ProcessTokenIteratorState::ProcessResolved(ref resolved) => {
199 match resolved.inner.get_type() {
200 TokenType::Value => {
201 let resolved = match mem::replace(
202 &mut self.internal_state,
203 ProcessTokenIteratorState::Pending,
204 ) {
205 ProcessTokenIteratorState::ProcessResolved(resolved) => resolved,
206 _ => unreachable!(),
207 };
208
209 return Some(Ok(resolved));
210 }
211 TokenType::Precedence {
212 precedence,
213 associativity,
214 } => {
215 let result = self.stack.pop_if(|token| {
216 let last_precedence = match token {
217 StackEntry::Resolved(resolved) => {
218 match resolved.inner.get_type() {
219 TokenType::Precedence {
220 precedence: last_precedence,
221 associativity,
222 } => match associativity {
223 Associativity::Left | Associativity::Right => {
224 last_precedence
225 }
226 Associativity::ClosedRight => return false,
227 },
228 _ => unreachable!(
229 "Stack should only contain precedence tokens!"
230 ),
231 }
232 }
233 StackEntry::Ordering(ordering) => {
234 match ordering.inner.behaviour() {
235 OrderingBehaviour::Right {
236 precedence,
237 closed: false,
238 } => precedence,
239 _ => return false,
240 }
241 }
242 };
243
244 last_precedence >= precedence
245 && (associativity == Associativity::Left
246 || precedence != last_precedence)
247 });
248
249 if let Some(StackEntry::Resolved(resolved)) = result {
250 return Some(Ok(resolved));
251 }
252
253 let resolved = match mem::replace(
254 &mut self.internal_state,
255 ProcessTokenIteratorState::Pending,
256 ) {
257 ProcessTokenIteratorState::ProcessResolved(resolved) => resolved,
258 _ => unreachable!(),
259 };
260
261 self.stack.push(StackEntry::Resolved(resolved));
262 }
263 }
264 }
265 ProcessTokenIteratorState::ProcessOrdering(ref ordering) => {
266 match ordering.inner.behaviour() {
267 OrderingBehaviour::Right { precedence, .. } => {
268 let result = self.stack.pop_if(|token| {
269 let last_precedence = match token {
270 StackEntry::Resolved(resolved) => {
271 match resolved.inner.get_type() {
272 TokenType::Precedence {
273 precedence: last_precedence,
274 associativity,
275 } => match associativity {
276 Associativity::Left | Associativity::Right => {
277 last_precedence
278 }
279 Associativity::ClosedRight => return false,
280 },
281 _ => unreachable!(
282 "Stack should only contain precedence tokens!"
283 ),
284 }
285 }
286 StackEntry::Ordering(ordering) => {
287 match ordering.inner.behaviour() {
288 OrderingBehaviour::Right {
289 precedence,
290 closed: false,
291 } => precedence,
292 _ => return false,
293 }
294 }
295 };
296
297 last_precedence > precedence
298 });
299
300 if let Some(StackEntry::Resolved(resolved)) = result {
301 return Some(Ok(resolved));
302 }
303
304 let ordering = match mem::replace(
305 &mut self.internal_state,
306 ProcessTokenIteratorState::Pending,
307 ) {
308 ProcessTokenIteratorState::ProcessOrdering(ordering) => ordering,
309 _ => unreachable!(),
310 };
311
312 self.stack.push(StackEntry::Ordering(ordering));
313 }
314 OrderingBehaviour::SoftLeft { precedence } => {
315 let result = self.stack.pop_if(|token| {
316 let last_precedence = match token {
317 StackEntry::Resolved(resolved) => {
318 match resolved.inner.get_type() {
319 TokenType::Precedence {
320 precedence: last_precedence,
321 associativity,
322 } => match associativity {
323 Associativity::Left | Associativity::Right => {
324 last_precedence
325 }
326 Associativity::ClosedRight => return false,
327 },
328 _ => unreachable!(
329 "Stack should only contain precedence tokens!"
330 ),
331 }
332 }
333 StackEntry::Ordering(ordering) => {
334 match ordering.inner.behaviour() {
335 OrderingBehaviour::Right {
336 precedence,
337 closed: false,
338 } => precedence,
339 _ => return false,
340 }
341 }
342 };
343
344 last_precedence >= precedence
345 });
346
347 if let Some(StackEntry::Resolved(resolved)) = result {
348 return Some(Ok(resolved));
349 }
350
351 self.internal_state = ProcessTokenIteratorState::Pending;
352 }
353 OrderingBehaviour::ClosedLeft => {
354 if let Some(token) = self.stack.pop() {
355 match token {
356 StackEntry::Resolved(mut resolved) => {
357 match resolved.inner.get_type() {
358 TokenType::Precedence {
359 precedence: _,
360 associativity: Associativity::ClosedRight,
361 } => {
362 self.internal_state =
363 ProcessTokenIteratorState::Pending;
364 self.state.proccess_closed(&mut resolved);
365 }
366 _ => return Some(Ok(resolved)),
367 }
368 return Some(Ok(resolved));
369 }
370 StackEntry::Ordering(last_ordering) => {
371 match last_ordering.inner.behaviour() {
372 OrderingBehaviour::Right {
373 precedence: _,
374 closed: true,
375 } => {
376 self.internal_state =
377 ProcessTokenIteratorState::Pending;
378 self.state.delete_closed_ordering(last_ordering);
379 continue 'main;
380 }
381 _ => continue 'main,
382 }
383 }
384 }
385 } else {
386 self.internal_state = ProcessTokenIteratorState::Completed;
387 return Some(Err(self.state.no_ordering_found()));
388 }
389 }
390 }
391 }
392 ProcessTokenIteratorState::ClearingStack => {
393 while let Some(entry) = self.stack.pop() {
394 match entry {
395 StackEntry::Resolved(resolved) => return Some(Ok(resolved)),
396 StackEntry::Ordering(ordering) => {
397 self.state.delete_closed_ordering(ordering)
398 }
399 }
400 }
401
402 self.internal_state = ProcessTokenIteratorState::Completed;
403 return None;
404 }
405 ProcessTokenIteratorState::Completed => return None,
406 }
407 }
408 }
409}