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