gramma/ast/
mod.rs

1///
2mod macros;
3pub mod print;
4pub mod transform;
5
6use core::{
7    any::{Any, TypeId},
8    cmp::Ordering,
9    fmt::{self, Debug, Formatter},
10    hash::Hash,
11    marker::PhantomData,
12    ops::ControlFlow::{self, Break, Continue},
13};
14
15use either::{for_both, Either};
16
17use crate::{
18    error::ExpectedParseObject,
19    internal_prelude::*,
20    parse::{
21        CxType, Location, LocationRange, ParseContext, ParseContextParts, ParseContextUpdate,
22        ParseError, SizedParseContext,
23    },
24    string_matcher,
25    token::{AnyToken, Eof, Token, TokenObject},
26    utils::{default, simple_name, try_run, DebugFn, MyTry},
27};
28
29use self::{
30    print::{PrintContext, PrintVisibility},
31    transform::{identity, TransformInto},
32};
33
34struct WithSource<'data, T: ?Sized> {
35    pub src: &'data str,
36    pub ast: &'data T,
37}
38
39impl<T: Rule + ?Sized> Debug for WithSource<'_, T> {
40    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
41        self.ast
42            .print_tree(PrintContext::new(self.src).set_debug(true), f)
43    }
44}
45
46impl<T: Rule + ?Sized> fmt::Display for WithSource<'_, T> {
47    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
48        self.ast.print_tree(&PrintContext::new(self.src), f)
49    }
50}
51
52/// Values used to represent the current parser state in [Rule::pre_parse].
53#[non_exhaustive]
54#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
55pub struct PreParseState {
56    pub start: Location,
57    pub end: Location,
58    pub dist: usize,
59    pub(crate) empty_state: EmptyParseState,
60}
61
62const MAX_CONSECUTIVE_EMPTY: usize = 8;
63
64#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
65pub(crate) struct EmptyParseState {
66    pub location: Location,
67    pub dist: usize,
68    pub count: usize,
69}
70
71/// Represents part of a grammar.
72///
73/// See also [crate::define_rule].
74pub trait Rule: Any + Debug {
75    /// Determines whether the AST node should be printed.
76    fn print_visibility(&self, cx: &PrintContext) -> PrintVisibility {
77        let _ = cx;
78        PrintVisibility::Always
79    }
80
81    /// Writes the contents of the parsed AST node to `f`.
82    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
83        let _ = cx;
84        Debug::fmt(self, f)
85    }
86
87    /// The name of the rule.
88    fn name() -> &'static str
89    where
90        Self: Sized,
91    {
92        simple_name::<Self>()
93    }
94
95    /// Writes the name of this rule to `f`.
96    fn print_name(f: &mut Formatter) -> fmt::Result
97    where
98        Self: Sized,
99    {
100        f.write_str(Self::name())
101    }
102
103    /// Begins evaluating this rule, stopping when the lookahead buffer is full.
104    fn pre_parse<Cx: CxType>(
105        cx: ParseContext<Cx>,
106        state: PreParseState,
107        next: &RuleObject<Cx>,
108    ) -> RuleParseResult<()>
109    where
110        Self: Sized;
111
112    /// Evaluates the rule.
113    ///
114    /// Returns `Ok(Self)` if successful, or `Err(_)` if the source does not match this rule.
115    fn parse<Cx: CxType>(cx: ParseContext<Cx>, next: &RuleObject<Cx>) -> RuleParseResult<Self>
116    where
117        Self: Sized;
118}
119
120/// An object dynamically representing an implementation of [Rule].
121#[derive(Clone, Copy)]
122pub struct RuleObject<'lt, Cx: CxType> {
123    name: fn() -> &'static str,
124    print_name: fn(&mut Formatter) -> fmt::Result,
125    pre_parse: &'lt (dyn Fn(ParseContext<Cx>, PreParseState, &RuleObject<Cx>) -> RuleParseResult<()>
126              + 'lt),
127    next: Option<&'lt Self>,
128}
129
130impl<'lt, Cx: CxType> RuleObject<'lt, Cx> {
131    /// Creates a [RuleObject] for rule `T`, which may be followed by another [RuleObject] `next`.
132    pub fn new<T: Rule>(next: impl Into<Option<&'lt Self>>) -> Self {
133        RuleObject {
134            name: T::name,
135            print_name: T::print_name,
136            pre_parse: &T::pre_parse::<Cx>,
137            next: next.into(),
138        }
139    }
140
141    /// Creates an unbounded reference to a [RuleObject] for `T`.
142    pub const fn of<T: Rule>() -> &'lt Self {
143        &RuleObject::<Cx> {
144            name: T::name,
145            print_name: T::print_name,
146            pre_parse: &T::pre_parse,
147            next: None,
148        }
149    }
150
151    /// Replace the `pre_parse` implementation with the given function:
152    pub(crate) const fn adapt<'lt2>(
153        &self,
154        pre_parse: &'lt2 (dyn Fn(ParseContext<Cx>, PreParseState, &RuleObject<Cx>) -> RuleParseResult<()>
155                   + 'lt2),
156    ) -> RuleObject<'lt2, Cx>
157    where
158        'lt: 'lt2,
159    {
160        RuleObject { pre_parse, ..*self }
161    }
162
163    /// The name of the rule.
164    #[inline]
165    pub fn name(&self) -> &str {
166        (self.name)()
167    }
168
169    /// Begins evaluating this rule, stopping when the lookahead buffer is full.
170    #[inline]
171    pub fn pre_parse(&self, cx: ParseContext<Cx>, mut state: PreParseState) -> RuleParseResult<()> {
172        if state.start > state.end || state.dist >= cx.look_ahead().len() {
173            return Ok(());
174        }
175
176        if state.start == state.empty_state.location && state.dist == state.empty_state.dist {
177            if state.empty_state.count > MAX_CONSECUTIVE_EMPTY {
178                return Err(RuleParseFailed {
179                    location: state.start,
180                });
181            }
182        } else {
183            state.empty_state = EmptyParseState {
184                location: state.start,
185                dist: state.dist,
186                count: 0,
187            }
188        }
189
190        (self.pre_parse)(cx, state, self.next.unwrap_or_default())
191    }
192}
193
194impl<Cx: CxType> Debug for RuleObject<'_, Cx> {
195    fn fmt(mut self: &Self, f: &mut Formatter<'_>) -> fmt::Result {
196        let mut list = f.debug_list();
197
198        loop {
199            list.entry(&DebugFn(self.print_name));
200
201            match self.next {
202                Some(next) => self = next,
203                None => break list.finish(),
204            }
205        }
206    }
207}
208
209impl<Cx: CxType> Default for RuleObject<'_, Cx> {
210    fn default() -> Self {
211        Self::new::<Accept>(None)
212    }
213}
214
215impl<'lt, Cx: CxType> Default for &'lt RuleObject<'lt, Cx> {
216    fn default() -> Self {
217        RuleObject::of::<Accept>()
218    }
219}
220
221/// A rule that rejects all possible source strings.
222#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
223pub enum Reject {}
224
225impl Rule for Reject {
226    fn pre_parse<Cx: CxType>(
227        _: ParseContext<Cx>,
228        state: PreParseState,
229        _: &RuleObject<Cx>,
230    ) -> RuleParseResult<()> {
231        Err(RuleParseFailed {
232            location: state.start,
233        })
234    }
235
236    fn parse<Cx: CxType>(cx: ParseContext<Cx>, _: &RuleObject<Cx>) -> RuleParseResult<Self>
237    where
238        Self: Sized,
239    {
240        Err(RuleParseFailed {
241            location: cx.location(),
242        })
243    }
244}
245
246/// A helper trait for implementing [Rule] based on another rule.
247pub trait DelegateRule: Any + Debug {
248    /// The rule to parse.
249    type Inner: Rule;
250
251    /// See [Rule::print_name].
252    fn print_name(f: &mut Formatter) -> fmt::Result {
253        f.write_str(Self::name())
254    }
255
256    /// See [Rule::print_visibility]
257    fn print_visibility(&self, cx: &PrintContext) -> PrintVisibility {
258        let _ = cx;
259        PrintVisibility::Always
260    }
261
262    /// Transforms `Self::Inner` into `Self` after successfully parsing `Self::Inner`.
263    fn from_inner(inner: Self::Inner) -> Self;
264
265    /// See [Rule::print_tree]
266    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
267        let _ = cx;
268        Debug::fmt(self, f)
269    }
270
271    /// See [Rule::name]
272    fn name() -> &'static str {
273        simple_name::<Self>()
274    }
275
276    /// Optionally performs operations on the [ParseContext] before parsing `Self::Inner`.
277    fn update_context<Cx: CxType, R>(
278        cx: ParseContext<Cx>,
279        f: impl FnOnce(ParseContext<Cx>) -> R,
280    ) -> R {
281        f(cx)
282    }
283}
284
285impl<This> Rule for This
286where
287    This: DelegateRule,
288{
289    fn print_name(f: &mut Formatter) -> fmt::Result {
290        <This as DelegateRule>::print_name(f)
291    }
292    fn name() -> &'static str {
293        <This as DelegateRule>::name()
294    }
295    fn print_visibility(&self, cx: &PrintContext) -> PrintVisibility {
296        DelegateRule::print_visibility(self, cx)
297    }
298
299    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
300        DelegateRule::print_tree(self, cx, f)
301    }
302
303    fn pre_parse<Cx: CxType>(
304        cx: ParseContext<Cx>,
305        state: PreParseState,
306        next: &RuleObject<Cx>,
307    ) -> RuleParseResult<()> {
308        Self::update_context(cx, |cx| This::Inner::pre_parse(cx, state, next))
309    }
310
311    fn parse<Cx: CxType>(cx: ParseContext<Cx>, next: &RuleObject<Cx>) -> RuleParseResult<Self>
312    where
313        Self: Sized,
314    {
315        Self::update_context(cx, |cx| This::Inner::parse(cx, next).map(This::from_inner))
316    }
317}
318
319/// Base [Rule] implementation for [Vec].
320pub struct TransformList<
321    T,
322    X: TransformInto<T>,
323    Delim = Empty,
324    const TRAIL: bool = false,
325    const PREFER_SHORT: bool = false,
326> {
327    pub items: Vec<T>,
328    _x: PhantomData<X>,
329    _delim: PhantomData<Delim>,
330}
331
332impl<T, X: TransformInto<T>, Delim, const TRAIL: bool, const PREFER_SHORT: bool>
333    TransformList<T, X, Delim, TRAIL, PREFER_SHORT>
334{
335    pub fn new(items: Vec<T>) -> Self {
336        Self {
337            items,
338            _x: PhantomData,
339            _delim: PhantomData,
340        }
341    }
342}
343
344impl<T: Debug, X: TransformInto<T>, Delim, const TRAIL: bool, const PREFER_SHORT: bool> Debug
345    for TransformList<T, X, Delim, TRAIL, PREFER_SHORT>
346{
347    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
348        Debug::fmt(&self.items, f)
349    }
350}
351
352impl<T: Rule> DelegateRule for Vec<T> {
353    type Inner = TransformList<T, identity>;
354    fn print_name(f: &mut Formatter) -> fmt::Result {
355        f.write_str("Vec(")?;
356        T::print_name(f)?;
357        f.write_str(")")
358    }
359
360    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
361        cx.debug_list(f, self.iter().map(|item| item as _))
362    }
363
364    fn from_inner(inner: Self::Inner) -> Self {
365        inner.items
366    }
367}
368
369/// Rule that reads zero tokens and accepts. Equivalent to using `()`.
370#[derive(Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
371pub struct Empty;
372
373impl Rule for Empty {
374    fn pre_parse<Cx: CxType>(
375        cx: ParseContext<Cx>,
376        state: PreParseState,
377        next: &RuleObject<Cx>,
378    ) -> RuleParseResult<()> {
379        next.pre_parse(cx, state)
380    }
381
382    fn parse<Cx: CxType>(_: ParseContext<Cx>, _: &RuleObject<Cx>) -> RuleParseResult<Self>
383    where
384        Self: Sized,
385    {
386        Ok(Self)
387    }
388}
389
390impl<T: Rule> DelegateRule for Option<T> {
391    fn print_name(f: &mut Formatter) -> fmt::Result {
392        f.write_str("(")?;
393        T::print_name(f)?;
394        f.write_str(")?")
395    }
396
397    type Inner = Either<NotEmpty<T>, Empty>;
398
399    fn from_inner(inner: Self::Inner) -> Self {
400        inner.left().map(|x| x.value)
401    }
402
403    fn print_visibility(&self, _: &PrintContext) -> PrintVisibility {
404        match self {
405            Some(_) => PrintVisibility::Always,
406            None => PrintVisibility::DebugOnly,
407        }
408    }
409
410    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
411        match (self, cx.is_debug()) {
412            (None, true) => f.write_str("None"),
413            (None, false) => Ok(()),
414            (Some(value), true) => {
415                f.write_str("Some(")?;
416                value.print_tree(cx, f)?;
417                f.write_str(")")
418            }
419            (Some(value), false) => value.print_tree(cx, f),
420        }
421    }
422}
423
424impl<T: Rule> DelegateRule for Box<T> {
425    type Inner = T;
426
427    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
428        (**self).print_tree(cx, f)
429    }
430
431    fn from_inner(inner: Self::Inner) -> Self {
432        Box::new(inner)
433    }
434}
435
436/// Simple error type indicating where parsing failed.
437#[derive(Debug, Clone)]
438pub struct RuleParseFailed {
439    pub location: Location,
440}
441
442impl RuleParseFailed {
443    pub fn furthest(self, rhs: Self) -> Self {
444        RuleParseFailed {
445            location: self.location.max(rhs.location),
446        }
447    }
448}
449
450pub type RuleParseResult<T> = Result<T, RuleParseFailed>;
451
452impl<T: Rule, U: Rule> Rule for Either<T, U> {
453    fn print_name(f: &mut Formatter) -> fmt::Result {
454        f.write_str("(")?;
455        T::print_name(f)?;
456        f.write_str(" | ")?;
457        U::print_name(f)?;
458        f.write_str(")")
459    }
460    fn print_visibility(&self, cx: &PrintContext) -> PrintVisibility {
461        for_both!(self, ast => ast.print_visibility(cx))
462    }
463    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
464        for_both!(self, ast => ast.print_tree(cx, f))
465    }
466
467    fn pre_parse<Cx: CxType>(
468        mut cx: ParseContext<Cx>,
469        state: PreParseState,
470        next: &RuleObject<Cx>,
471    ) -> RuleParseResult<()> {
472        T::pre_parse(cx.by_ref(), state, next)
473            .or_else(|err1| U::pre_parse(cx, state, next).map_err(|err2| err1.furthest(err2)))
474    }
475
476    fn parse<Cx: CxType>(mut cx: ParseContext<Cx>, next: &RuleObject<Cx>) -> RuleParseResult<Self>
477    where
478        Self: Sized,
479    {
480        let location = cx.location();
481        try_run(|| {
482            let mut cx = cx.by_ref();
483
484            let Err(mut err1) = cx.pre_parse::<T>(next) else {
485                return T::parse(cx, next).map(Either::Left);
486            };
487            let Err(mut err2) = cx.record_error::<U>(next) else {
488                return U::parse(cx, next).map(Either::Right);
489            };
490
491            // Not sure if this contributes anything:
492            if let Err(e) = cx.record_error::<T>(next) {
493                err1 = err1.furthest(e);
494            }
495
496            match T::parse(cx.by_ref(), next) {
497                Err(e) => err1 = err1.furthest(e),
498                out => return out.map(Either::Left),
499            }
500
501            cx.set_location(location);
502            match U::parse(cx.by_ref(), next) {
503                Err(e) => err2 = err2.furthest(e),
504                out => return out.map(Either::Right),
505            }
506
507            cx.set_location(location);
508            debug_assert!(cx.error_mut().location >= err1.location.max(err2.location));
509
510            Err(err1.furthest(err2))
511        })
512        .break_also(|_| {
513            cx.error_mut().error_rule_location = Some(location);
514        })
515    }
516}
517
518impl<T: Rule, U: Rule> Rule for (T, U) {
519    fn print_name(f: &mut Formatter) -> fmt::Result {
520        T::print_name(f)?;
521        f.write_str(" >> ")?;
522        U::print_name(f)
523    }
524
525    fn print_visibility(&self, cx: &PrintContext) -> PrintVisibility {
526        self.0.print_visibility(cx).max(self.1.print_visibility(cx))
527    }
528
529    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
530        cx.debug_tuple("", f, [&self.0 as _, &self.1 as _])
531    }
532
533    fn pre_parse<Cx: CxType>(
534        cx: ParseContext<Cx>,
535        state: PreParseState,
536        next: &RuleObject<Cx>,
537    ) -> RuleParseResult<()> {
538        T::pre_parse(cx, state, &RuleObject::new::<U>(next))
539    }
540
541    fn parse<Cx: CxType>(mut cx: ParseContext<Cx>, next: &RuleObject<Cx>) -> RuleParseResult<Self>
542    where
543        Self: Sized,
544    {
545        Ok((
546            T::parse(cx.by_ref(), &RuleObject::new::<U>(next))?,
547            U::parse(cx.expecting(None), next)?,
548        ))
549    }
550}
551
552impl DelegateRule for () {
553    type Inner = Empty;
554
555    fn print_name(f: &mut Formatter) -> fmt::Result {
556        f.write_str("()")
557    }
558
559    fn print_visibility(&self, _: &PrintContext) -> PrintVisibility {
560        PrintVisibility::DebugOnly
561    }
562
563    fn from_inner(_: Self::Inner) -> Self {
564        ()
565    }
566}
567
568impl<T0: Rule> DelegateRule for (T0,) {
569    type Inner = T0;
570
571    fn print_name(f: &mut Formatter) -> fmt::Result {
572        T0::print_name(f)
573    }
574
575    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
576        self.0.print_tree(cx, f)
577    }
578
579    fn print_visibility(&self, _: &PrintContext) -> PrintVisibility {
580        PrintVisibility::DebugOnly
581    }
582
583    fn from_inner(inner: Self::Inner) -> Self {
584        (inner,)
585    }
586}
587
588impl<T0: Rule, T1: Rule, T2: Rule> DelegateRule for (T0, T1, T2) {
589    type Inner = (T0, (T1, T2));
590
591    fn print_name(f: &mut Formatter) -> fmt::Result {
592        T0::print_name(f)?;
593        f.write_str(" >> ")?;
594        T1::print_name(f)?;
595        f.write_str(" >> ")?;
596        T2::print_name(f)
597    }
598
599    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
600        self.0.print_tree(cx, f)
601    }
602
603    fn print_visibility(&self, cx: &PrintContext) -> PrintVisibility {
604        self.0
605            .print_visibility(cx)
606            .max(self.1.print_visibility(cx))
607            .max(self.2.print_visibility(cx))
608    }
609
610    fn from_inner((x0, (x1, x2)): Self::Inner) -> Self {
611        (x0, x1, x2)
612    }
613}
614
615impl<T0: Rule, T1: Rule, T2: Rule, T3: Rule> DelegateRule for (T0, T1, T2, T3) {
616    type Inner = ((T0, T1), (T2, T3));
617
618    fn print_name(f: &mut Formatter) -> fmt::Result {
619        T0::print_name(f)?;
620        f.write_str(" >> ")?;
621        T1::print_name(f)?;
622        f.write_str(" >> ")?;
623        T2::print_name(f)?;
624        f.write_str(" >> ")?;
625        T3::print_name(f)
626    }
627
628    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
629        self.0.print_tree(cx, f)
630    }
631
632    fn print_visibility(&self, cx: &PrintContext) -> PrintVisibility {
633        self.0
634            .print_visibility(cx)
635            .max(self.1.print_visibility(cx))
636            .max(self.2.print_visibility(cx))
637            .max(self.3.print_visibility(cx))
638    }
639
640    fn from_inner(((x0, x1), (x2, x3)): Self::Inner) -> Self {
641        (x0, x1, x2, x3)
642    }
643}
644
645/// Rule that reads exactly one token of type `T`.
646#[derive(PartialEq, Eq, PartialOrd, Ord, Hash)]
647pub struct ReadToken<T> {
648    pub range: LocationRange,
649    _t: PhantomData<T>,
650}
651
652impl<T> Copy for ReadToken<T> {}
653
654impl<T> Clone for ReadToken<T> {
655    fn clone(&self) -> Self {
656        *self
657    }
658}
659
660impl<T: Token> Debug for ReadToken<T> {
661    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
662        f.write_str(T::name())
663    }
664}
665
666impl<T: Token> From<ReadToken<T>> for AnyToken {
667    fn from(value: ReadToken<T>) -> Self {
668        Self {
669            token_type: TokenObject::of::<T>(),
670            range: value.range,
671        }
672    }
673}
674
675impl<T> From<LocationRange> for ReadToken<T> {
676    fn from(range: LocationRange) -> Self {
677        Self {
678            range,
679            _t: PhantomData,
680        }
681    }
682}
683
684impl<T: Token> Rule for ReadToken<T> {
685    fn print_name(f: &mut Formatter) -> fmt::Result
686    where
687        Self: Sized,
688    {
689        f.write_str(T::display_name())
690    }
691
692    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
693        if cx.is_debug() {
694            T::print_debug(cx.src(), self.range, f)
695        } else {
696            T::print_display(cx.src(), self.range, f)
697        }
698    }
699    fn pre_parse<Cx: CxType>(
700        mut cx: ParseContext<Cx>,
701        state: PreParseState,
702        next: &RuleObject<Cx>,
703    ) -> RuleParseResult<()> {
704        if state.start > state.end {
705            return Ok(());
706        }
707
708        cx = cx.expecting(ExpectedParseObject::from_token::<T>());
709
710        let ParseContextParts {
711            src, look_ahead, ..
712        } = cx.as_parts();
713
714        let end = match look_ahead.get_mut(state.dist..) {
715            None | Some([]) => return Ok(()),
716            Some([Some(token), ..])
717                if token.token_type.token_id() == TypeId::of::<T>()
718                    && token.range.start == state.start =>
719            {
720                token.range.end
721            }
722            Some([token, ..]) => {
723                let Some(range) = T::try_lex(src, state.start) else {
724                    cx.error_at(state.start);
725                    return Err(RuleParseFailed {
726                        location: state.start,
727                    });
728                };
729                *token = Some(AnyToken {
730                    token_type: TokenObject::of::<T>(),
731                    range,
732                });
733                range.end
734            }
735        };
736
737        next.pre_parse(
738            cx.expecting(None),
739            PreParseState {
740                start: end,
741                dist: state.dist + 1,
742                ..state
743            },
744        )
745    }
746
747    fn parse<Cx: CxType>(mut cx: ParseContext<Cx>, _: &RuleObject<Cx>) -> RuleParseResult<Self>
748    where
749        Self: Sized,
750    {
751        cx = cx.expecting(ExpectedParseObject::from_token::<T>());
752        let location = cx.location();
753
754        try_run(|| {
755            if let [Some(token), ..] = **cx.look_ahead_mut() {
756                if token.range.start == location && token.token_type.token_id() == TypeId::of::<T>()
757                {
758                    cx.advance();
759                    return Ok(token.range.into());
760                }
761            }
762
763            let range = T::try_lex(cx.src(), location).ok_or(RuleParseFailed { location })?;
764            cx.set_location(range.end);
765
766            Ok(range.into())
767        })
768        .break_also(|err: &mut RuleParseFailed| cx.error_at(err.location))
769    }
770}
771
772impl<T: Rule> DelegateRule for PhantomData<T> {
773    type Inner = Discard<T>;
774
775    fn print_visibility(&self, _: &PrintContext) -> PrintVisibility {
776        PrintVisibility::Never
777    }
778
779    fn from_inner(_: Self::Inner) -> Self {
780        Self
781    }
782}
783
784macro_rules! generic_unit {
785    ($($(#$attr:tt)*$vis:vis struct $Name:ident<$($T:ident),* $(,)?>;)*) => {$(
786        $(#$attr)*
787        $vis struct $Name<$($T: ?Sized),*>($(PhantomData<$T>),*);
788
789
790        impl<$($T: ?Sized),*> Debug for $Name<$($T),*> {
791            fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
792                f.debug_tuple("Discard").field(&self.0).finish()
793            }
794        }
795
796        impl<$($T: ?Sized),*> Default for $Name<$($T),*> {
797            fn default() -> Self {
798                Self(PhantomData)
799            }
800        }
801
802        impl<$($T: ?Sized),*> Clone for $Name<$($T),*> {
803            fn clone(&self) -> Self {
804                *self
805            }
806        }
807
808        impl<$($T: ?Sized),*> Copy for $Name<$($T),*> {}
809
810        impl<$($T: ?Sized),*> PartialEq for $Name<$($T),*> {
811            fn eq(&self, _: &Self) -> bool {
812                true
813            }
814        }
815        impl<$($T: ?Sized),*> Eq for $Name<$($T),*> {}
816        impl<$($T: ?Sized),*> PartialOrd for $Name<$($T),*> {
817            fn partial_cmp(&self, _: &Self) -> Option<Ordering> {
818                Some(Ordering::Equal)
819            }
820        }
821        impl<$($T: ?Sized),*> Ord for $Name<$($T),*> {
822            fn cmp(&self, _: &Self) -> Ordering {
823                Ordering::Equal
824            }
825        }
826        impl<$($T: ?Sized),*> Hash for $Name<$($T),*> {
827            fn hash<H: core::hash::Hasher>(&self, _: &mut H) {}
828        }
829    )*};
830}
831
832/// Rule that consumes the remaining source string and accepts regardless of its content.
833#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
834pub struct Accept;
835
836impl Rule for Accept {
837    fn name() -> &'static str {
838        "Accept"
839    }
840
841    fn pre_parse<Cx: CxType>(
842        _: ParseContext<Cx>,
843        _: PreParseState,
844        _: &RuleObject<Cx>,
845    ) -> RuleParseResult<()> {
846        Ok(())
847    }
848
849    fn parse<Cx: CxType>(mut cx: ParseContext<Cx>, _: &RuleObject<Cx>) -> RuleParseResult<Self>
850    where
851        Self: Sized,
852    {
853        cx.set_location(Location {
854            position: cx.src().len(),
855        });
856        Ok(Self)
857    }
858}
859
860/// Rule that is initially parsed as `Outer`.
861/// If `Outer` parses successfully, the string that matched `Outer` will be parsed again as `Inner`.
862#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
863pub struct DualParse<Outer, Inner> {
864    pub outer: Outer,
865    pub inner: Inner,
866}
867
868impl<Outer: Rule, Inner: Rule> Rule for DualParse<Outer, Inner> {
869    fn print_name(f: &mut Formatter) -> fmt::Result
870    where
871        Self: Sized,
872    {
873        f.write_str("(")?;
874        Outer::print_name(f)?;
875        f.write_str(" & ")?;
876        Inner::print_name(f)?;
877        f.write_str(")")
878    }
879
880    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
881        let outer_vis = self.outer.print_visibility(cx).should_print(cx);
882        let inner_vis = self.inner.print_visibility(cx).should_print(cx);
883
884        if outer_vis {
885            self.outer.print_tree(cx, f)?;
886        }
887
888        if outer_vis && inner_vis {
889            f.write_str(" & ")?;
890        }
891
892        if inner_vis {
893            self.inner.print_tree(cx, f)?;
894        }
895
896        Ok(())
897    }
898
899    fn pre_parse<Cx: CxType>(
900        mut cx: ParseContext<Cx>,
901        state: PreParseState,
902        next: &RuleObject<Cx>,
903    ) -> RuleParseResult<()>
904    where
905        Self: Sized,
906    {
907        let mut look_ahead = *cx.look_ahead();
908        Outer::pre_parse(cx.by_ref(), state, next)?;
909        Inner::pre_parse(
910            cx.by_ref().update(ParseContextUpdate {
911                look_ahead: Some(&mut look_ahead),
912                ..default()
913            }),
914            state,
915            default(),
916        )
917    }
918
919    fn parse<Cx: CxType>(mut cx: ParseContext<Cx>, next: &RuleObject<Cx>) -> RuleParseResult<Self>
920    where
921        Self: Sized,
922    {
923        let src = cx.src();
924        let start = cx.location();
925
926        let (outer, end) = <(Outer, Location)>::parse(cx.by_ref(), next)?;
927
928        let (inner, _) = match cx.by_ref().update(ParseContextUpdate {
929            src: Some(&src[..end.position]),
930            location: Some(&mut start.clone()),
931            look_ahead: Some(&mut default()),
932            ..default()
933        }) {
934            cx => <(Inner, Silent<ReadToken<Eof>>)>::parse(cx, default())?,
935        };
936
937        if end > start {
938            cx.set_location(end);
939        }
940
941        Ok(Self { outer, inner })
942    }
943}
944
945/// Rule that parses `T` as if it's a singular token for lookahead purposes.
946#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
947pub struct CompoundToken<T> {
948    pub value: T,
949}
950
951struct CompoundTokenDef<T>(PhantomData<T>);
952
953impl<T: 'static> Token for CompoundTokenDef<T> {
954    fn try_lex(_: &str, _: Location) -> Option<LocationRange> {
955        None
956    }
957}
958
959impl<T: Rule> Rule for CompoundToken<T> {
960    fn print_name(f: &mut Formatter) -> fmt::Result {
961        f.write_str("CompoundToken(")?;
962        T::print_name(f)?;
963        f.write_str(")")
964    }
965
966    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
967        self.value.print_tree(cx, f)
968    }
969
970    fn print_visibility(&self, cx: &PrintContext) -> PrintVisibility {
971        self.value.print_visibility(cx)
972    }
973
974    fn pre_parse<Cx: CxType>(
975        mut cx: ParseContext<Cx>,
976        state: PreParseState,
977        next: &RuleObject<Cx>,
978    ) -> RuleParseResult<()>
979    where
980        Self: Sized,
981    {
982        let end = match cx.look_ahead().get(state.dist).copied() {
983            Some(Some(token)) if token.token_type == TokenObject::of::<CompoundTokenDef<T>>() => {
984                token.range.end
985            }
986            Some(_) => {
987                let (_, end) = cx.isolated_parse::<Discard<T>>(state.start, next)?;
988                cx.look_ahead_mut()[state.dist] = Some(AnyToken {
989                    token_type: TokenObject::of::<CompoundTokenDef<T>>(),
990                    range: LocationRange {
991                        start: state.start,
992                        end,
993                    },
994                });
995                end
996            }
997            None => return Ok(()),
998        };
999
1000        next.pre_parse(
1001            cx,
1002            PreParseState {
1003                start: end,
1004                dist: state.dist + 1,
1005                ..state
1006            },
1007        )
1008    }
1009
1010    fn parse<Cx: CxType>(mut cx: ParseContext<Cx>, next: &RuleObject<Cx>) -> RuleParseResult<Self>
1011    where
1012        Self: Sized,
1013    {
1014        let location = cx.location();
1015        Ok(match cx.look_ahead().first().copied().flatten() {
1016            Some(token) if token.token_type != TokenObject::of::<CompoundTokenDef<T>>() => {
1017                return Err(RuleParseFailed { location });
1018            }
1019            Some(_) => {
1020                let value = T::parse(
1021                    cx.by_ref().update(ParseContextUpdate {
1022                        look_ahead: Some(&mut default()),
1023                        ..default()
1024                    }),
1025                    next,
1026                )?;
1027                cx.advance();
1028                Self { value }
1029            }
1030            None => Self {
1031                value: T::parse(cx, next)?,
1032            },
1033        })
1034    }
1035}
1036
1037/// Rule that ignores the lookahead buffer altogether and just tries parsing to see if it matches the source.
1038#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
1039pub struct Backtrack<T> {
1040    pub value: T,
1041}
1042
1043impl<T: Rule> Rule for Backtrack<T> {
1044    fn pre_parse<Cx: CxType>(
1045        mut cx: ParseContext<Cx>,
1046        mut state: PreParseState,
1047        next: &RuleObject<Cx>,
1048    ) -> RuleParseResult<()>
1049    where
1050        Self: Sized,
1051    {
1052        let (_, end) = cx.isolated_parse::<Discard<T>>(state.start, next)?;
1053        if end == state.start {
1054            state.empty_state.count += 1;
1055        }
1056        next.pre_parse(
1057            cx,
1058            PreParseState {
1059                start: end,
1060                ..state
1061            },
1062        )
1063    }
1064
1065    fn parse<Cx: CxType>(cx: ParseContext<Cx>, next: &RuleObject<Cx>) -> RuleParseResult<Self>
1066    where
1067        Self: Sized,
1068    {
1069        let value = T::parse(
1070            cx.update(ParseContextUpdate {
1071                look_ahead: Some(&mut default()),
1072                ..default()
1073            }),
1074            next,
1075        )?;
1076        Ok(Self { value })
1077    }
1078}
1079
1080/// Rule that parses as `T` but doesn't record any of its errors, and potentially ignores subsequent rules' errors.
1081#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
1082pub struct Silent<T> {
1083    pub value: T,
1084}
1085
1086impl<T: Rule> DelegateRule for Silent<T> {
1087    type Inner = T;
1088
1089    fn print_name(f: &mut Formatter) -> fmt::Result {
1090        f.write_str("Silent(")?;
1091        T::print_name(f)?;
1092        f.write_str(")")
1093    }
1094
1095    fn print_visibility(&self, cx: &PrintContext) -> PrintVisibility {
1096        self.value.print_visibility(cx)
1097    }
1098
1099    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
1100        self.value.print_tree(cx, f)
1101    }
1102
1103    fn from_inner(value: Self::Inner) -> Self {
1104        Self { value }
1105    }
1106
1107    fn update_context<Cx: CxType, R>(
1108        cx: ParseContext<Cx>,
1109        f: impl FnOnce(ParseContext<Cx>) -> R,
1110    ) -> R {
1111        f(cx.update(ParseContextUpdate {
1112            error: Some(&mut ParseError {
1113                location: Location::MAX,
1114                ..default()
1115            }),
1116            ..default()
1117        }))
1118    }
1119}
1120
1121impl Rule for Location {
1122    fn pre_parse<Cx: CxType>(
1123        cx: ParseContext<Cx>,
1124        state: PreParseState,
1125        next: &RuleObject<Cx>,
1126    ) -> RuleParseResult<()>
1127    where
1128        Self: Sized,
1129    {
1130        next.pre_parse(cx, state)
1131    }
1132
1133    fn parse<Cx: CxType>(cx: ParseContext<Cx>, _: &RuleObject<Cx>) -> RuleParseResult<Self>
1134    where
1135        Self: Sized,
1136    {
1137        Ok(cx.location())
1138    }
1139}
1140
1141impl Rule for LocationRange {
1142    fn pre_parse<Cx: CxType>(
1143        cx: ParseContext<Cx>,
1144        state: PreParseState,
1145        next: &RuleObject<Cx>,
1146    ) -> RuleParseResult<()>
1147    where
1148        Self: Sized,
1149    {
1150        next.pre_parse(
1151            cx,
1152            PreParseState {
1153                start: state.end,
1154                ..state
1155            },
1156        )
1157    }
1158
1159    fn parse<Cx: CxType>(mut cx: ParseContext<Cx>, _: &RuleObject<Cx>) -> RuleParseResult<Self>
1160    where
1161        Self: Sized,
1162    {
1163        let start = cx.location();
1164        let end = Location {
1165            position: cx.src().len(),
1166        };
1167        cx.set_location(end);
1168        Ok(Self { start, end })
1169    }
1170
1171    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
1172        write!(
1173            f,
1174            "{}..{} => {:?}",
1175            self.start.position,
1176            self.end.position,
1177            cx.src()
1178                .get(self.start.position..self.end.position)
1179                .unwrap_or_default()
1180        )
1181    }
1182}
1183
1184impl Rule for alloc::string::String {
1185    fn pre_parse<Cx: CxType>(
1186        cx: ParseContext<Cx>,
1187        state: PreParseState,
1188        next: &RuleObject<Cx>,
1189    ) -> RuleParseResult<()>
1190    where
1191        Self: Sized,
1192    {
1193        next.pre_parse(
1194            cx,
1195            PreParseState {
1196                start: state.end,
1197                ..state
1198            },
1199        )
1200    }
1201
1202    fn parse<Cx: CxType>(mut cx: ParseContext<Cx>, _: &RuleObject<Cx>) -> RuleParseResult<Self>
1203    where
1204        Self: Sized,
1205    {
1206        let start = cx.location();
1207        let end = Location {
1208            position: cx.src().len(),
1209        };
1210        cx.set_location(end);
1211        Ok(if cx.should_discard() {
1212            default()
1213        } else {
1214            LocationRange { start, end }.slice(cx.src()).into()
1215        })
1216    }
1217
1218    fn print_tree(&self, _: &PrintContext, f: &mut Formatter) -> fmt::Result {
1219        Debug::fmt(self, f)
1220    }
1221}
1222
1223generic_unit!(
1224    /// Rule that parses as `T` but doesn't store the result.
1225    pub struct Discard<T>;
1226    /// Rule that optionally parses as `T`, but doesn't store the result
1227    /// and is omitted from the lookahead buffer.
1228    pub struct Ignore<T>;
1229);
1230
1231impl<T: Rule> DelegateRule for Discard<T> {
1232    type Inner = T;
1233
1234    fn print_name(f: &mut Formatter) -> fmt::Result {
1235        f.write_str("Discard(")?;
1236        T::print_name(f)?;
1237        f.write_str(")")
1238    }
1239
1240    fn from_inner(_: Self::Inner) -> Self {
1241        default()
1242    }
1243
1244    fn print_tree(&self, _: &PrintContext, f: &mut Formatter) -> fmt::Result {
1245        write!(f, "Discard<{}>", T::name())
1246    }
1247
1248    fn print_visibility(&self, _: &PrintContext) -> PrintVisibility {
1249        PrintVisibility::DebugOnly
1250    }
1251
1252    fn update_context<Cx: CxType, R>(
1253        cx: ParseContext<Cx>,
1254        f: impl FnOnce(ParseContext<Cx>) -> R,
1255    ) -> R {
1256        f(cx.discarding())
1257    }
1258}
1259
1260impl<T: Rule> Rule for Ignore<T> {
1261    fn print_name(f: &mut Formatter) -> fmt::Result {
1262        f.write_str("Ignore(")?;
1263        T::print_name(f)?;
1264        f.write_str(")")
1265    }
1266
1267    fn print_tree(&self, _: &PrintContext, _: &mut Formatter) -> fmt::Result {
1268        Ok(())
1269    }
1270
1271    fn print_visibility(&self, _: &PrintContext) -> PrintVisibility {
1272        PrintVisibility::Never
1273    }
1274
1275    fn pre_parse<Cx: CxType>(
1276        mut cx: ParseContext<Cx>,
1277        mut state: PreParseState,
1278        next: &RuleObject<Cx>,
1279    ) -> RuleParseResult<()>
1280    where
1281        Self: Sized,
1282    {
1283        if let Ok((_, end)) = cx.isolated_parse::<Silent<Discard<T>>>(state.start, default()) {
1284            if end == state.start {
1285                state.empty_state.count += 1;
1286            }
1287            next.pre_parse(
1288                cx,
1289                PreParseState {
1290                    start: end,
1291                    ..state
1292                },
1293            )
1294        } else {
1295            state.empty_state.count += 1;
1296            next.pre_parse(cx, state)
1297        }
1298    }
1299
1300    fn parse<Cx: CxType>(mut cx: ParseContext<Cx>, _: &RuleObject<Cx>) -> RuleParseResult<Self>
1301    where
1302        Self: Sized,
1303    {
1304        if let Ok((_, end)) = cx.isolated_parse::<Silent<Discard<T>>>(None, default()) {
1305            cx.set_location(end);
1306        }
1307        Ok(default())
1308    }
1309}
1310
1311impl<B: Rule, C: Rule> Rule for ControlFlow<B, C> {
1312    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
1313        if cx.is_debug() {
1314            match self {
1315                Continue(_) => {
1316                    f.write_str("Continue -> ")?;
1317                }
1318                Break(_) => {
1319                    f.write_str("Break -> ")?;
1320                }
1321            }
1322        }
1323
1324        match self {
1325            Continue(x) => x.print_tree(cx, f),
1326            Break(x) => x.print_tree(cx, f),
1327        }
1328    }
1329
1330    fn print_visibility(&self, cx: &PrintContext) -> PrintVisibility {
1331        match self {
1332            Continue(x) => x.print_visibility(cx),
1333            Break(x) => x.print_visibility(cx),
1334        }
1335    }
1336
1337    fn pre_parse<Cx: CxType>(
1338        cx: ParseContext<Cx>,
1339        state: PreParseState,
1340        next: &RuleObject<Cx>,
1341    ) -> RuleParseResult<()>
1342    where
1343        Self: Sized,
1344    {
1345        if cx.prefer_continue() {
1346            Either::<C, B>::pre_parse(cx, state, next)
1347        } else {
1348            Either::<B, C>::pre_parse(cx, state, next)
1349        }
1350    }
1351
1352    fn parse<Cx: CxType>(cx: ParseContext<Cx>, next: &RuleObject<Cx>) -> RuleParseResult<Self>
1353    where
1354        Self: Sized,
1355    {
1356        Ok(if cx.prefer_continue() {
1357            match Either::<C, B>::parse(cx, next)? {
1358                Either::Left(x) => Continue(x),
1359                Either::Right(x) => Break(x),
1360            }
1361        } else {
1362            match Either::<B, C>::parse(cx, next)? {
1363                Either::Left(x) => Break(x),
1364                Either::Right(x) => Continue(x),
1365            }
1366        })
1367    }
1368}
1369
1370/// Rule that parses `T` is if it may be followed by one or more instances of `T`.
1371#[derive(Debug)]
1372pub struct ListNode<T> {
1373    value: Option<T>,
1374}
1375
1376impl<T: Rule> DelegateRule for ListNode<T> {
1377    type Inner = ListNext<Partial<NotEmpty<T>, ControlFlow<(), ListNode<T>>>>;
1378
1379    fn print_name(f: &mut Formatter) -> fmt::Result {
1380        f.write_str("ListNodePlaceholder(")?;
1381        T::print_name(f)?;
1382        f.write_str(")")
1383    }
1384
1385    fn from_inner(inner: Self::Inner) -> Self {
1386        Self {
1387            value: match inner {
1388                Break(()) => None,
1389                Continue(Partial {
1390                    value: NotEmpty { value },
1391                    ..
1392                }) => Some(value),
1393            },
1394        }
1395    }
1396}
1397
1398/// Rule that parses `T` as if it is followed by `After`.
1399#[derive(Debug)]
1400pub struct Partial<T, After> {
1401    pub value: T,
1402    _after: PhantomData<After>,
1403}
1404
1405impl<T, After> Partial<T, After> {
1406    pub fn new(value: T) -> Self {
1407        Self {
1408            value,
1409            _after: PhantomData,
1410        }
1411    }
1412}
1413
1414impl<T: Rule, After: Rule> Rule for Partial<T, After> {
1415    fn print_name(f: &mut Formatter) -> fmt::Result
1416    where
1417        Self: Sized,
1418    {
1419        f.write_str("Partial(")?;
1420        T::print_name(f)?;
1421        f.write_str(", ")?;
1422        After::print_name(f)?;
1423        f.write_str(")")
1424    }
1425
1426    fn pre_parse<Cx: CxType>(
1427        cx: ParseContext<Cx>,
1428        state: PreParseState,
1429        next: &RuleObject<Cx>,
1430    ) -> RuleParseResult<()>
1431    where
1432        Self: Sized,
1433    {
1434        <(T, After)>::pre_parse(cx, state, next)
1435    }
1436
1437    fn parse<Cx: CxType>(cx: ParseContext<Cx>, next: &RuleObject<Cx>) -> RuleParseResult<Self>
1438    where
1439        Self: Sized,
1440    {
1441        T::parse(cx, &RuleObject::new::<After>(next)).map(Self::new)
1442    }
1443}
1444
1445/// Rule that parses `T` after transformation `X` has been applied.
1446pub struct Transformed<T, X> {
1447    pub value: T,
1448    _x: PhantomData<X>,
1449}
1450
1451impl<T, X> Debug for Transformed<T, X> {
1452    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1453        f.debug_struct("Transformed").finish_non_exhaustive()
1454    }
1455}
1456
1457impl<In: Rule, Out: 'static, X: TransformInto<Out, Input = In> + 'static> DelegateRule
1458    for Transformed<Out, X>
1459{
1460    type Inner = In;
1461
1462    fn from_inner(input: Self::Inner) -> Self {
1463        Self {
1464            value: X::transform(input),
1465            _x: PhantomData,
1466        }
1467    }
1468}
1469
1470type ListNext<T> = ControlFlow<(), T>;
1471
1472#[derive(Debug)]
1473struct TrailingListNode<T, Delim> {
1474    value: Option<T>,
1475    _delim: PhantomData<Delim>,
1476}
1477
1478type TrailingListTail<T, Delim> = ListNext<TrailingListNode<T, Delim>>;
1479
1480impl<T: Rule, Delim: Rule> DelegateRule for TrailingListNode<T, Delim> {
1481    type Inner = NotEmpty<(
1482        Discard<Delim>,
1483        ListNext<(Location, T, Location, ListNext<Partial<(), Self>>)>,
1484    )>;
1485    fn from_inner(NotEmpty { value: (_, next) }: Self::Inner) -> Self {
1486        let value = match next {
1487            Continue((_, value, _, Continue(_))) => Some(value),
1488            Continue((before, value, after, Break(()))) if after > before => Some(value),
1489            Continue((_, _, _, Break(()))) | Break(()) => None,
1490        };
1491        Self {
1492            value,
1493            _delim: PhantomData,
1494        }
1495    }
1496}
1497
1498type StandardListTail<T, Delim> = ListNode<(Discard<Delim>, T)>;
1499
1500/// Parses a list of `T` separated by `Delim`.
1501/// When `TRAIL` is `true`, the list may end with an optional extra `Delim`
1502pub type DelimitedList<T, Delim, const TRAIL: bool = true> =
1503    TransformList<T, identity, Delim, TRAIL>;
1504
1505impl<Out, In, X, Delim, const TRAIL: bool, const PREFER_SHORT: bool> Rule
1506    for TransformList<Out, X, Delim, TRAIL, PREFER_SHORT>
1507where
1508    Out: Rule,
1509    In: Rule,
1510    X: TransformInto<Out, Input = In> + 'static,
1511    Delim: Rule,
1512{
1513    fn print_name(f: &mut Formatter) -> fmt::Result {
1514        f.debug_struct("List")
1515            .field("In", &DebugFn(In::print_name))
1516            .field("Out", &DebugFn(Out::print_name))
1517            .field("Delim", &DebugFn(Delim::print_name))
1518            .finish()
1519    }
1520
1521    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
1522        cx.debug_list(f, self.items.iter().map(|item| item as _))
1523    }
1524
1525    fn pre_parse<Cx: CxType>(
1526        cx: ParseContext<Cx>,
1527        state: PreParseState,
1528        next: &RuleObject<Cx>,
1529    ) -> RuleParseResult<()>
1530    where
1531        Self: Sized,
1532    {
1533        if TRAIL {
1534            ListNext::<NotEmpty<(In, TrailingListTail<In, Delim>)>>::pre_parse(cx, state, next)
1535        } else {
1536            ListNext::<NotEmpty<(In, StandardListTail<In, Delim>)>>::pre_parse(cx, state, next)
1537        }
1538    }
1539
1540    fn parse<Cx: CxType>(mut cx: ParseContext<Cx>, next: &RuleObject<Cx>) -> RuleParseResult<Self>
1541    where
1542        Self: Sized,
1543    {
1544        cx = cx.update(ParseContextUpdate {
1545            prefer_continue: Some(!PREFER_SHORT),
1546            ..default()
1547        });
1548        let mut out = Vec::new();
1549        let discard = cx.should_discard();
1550
1551        let push = |item| {
1552            if !discard {
1553                out.push(X::transform(item))
1554            }
1555        };
1556        let name = DebugFn(Self::print_name);
1557
1558        if TRAIL {
1559            let get_first = |cx: ParseContext<Cx>, next: &RuleObject<Cx>| {
1560                ListNext::<Partial<In, TrailingListTail<In, Delim>>>::parse(cx, next)
1561                    .map(|p| p.flat_map(|Partial { value, .. }| Some(value)))
1562            };
1563
1564            let get_next = |cx: ParseContext<Cx>, next: &RuleObject<Cx>| {
1565                TrailingListTail::<In, Delim>::parse(cx, next).map(|p| p.flat_map(|x| x.value))
1566            };
1567
1568            parse_list(&mut cx, next, push, get_first, get_next, &name)?;
1569        } else {
1570            let get_first = |cx: ParseContext<Cx>, next: &RuleObject<Cx>| {
1571                ListNext::<Partial<In, StandardListTail<In, Delim>>>::parse(cx, next)
1572                    .map(|p| p.flat_map(|Partial { value, .. }| Some(value)))
1573            };
1574
1575            let get_next = |cx: ParseContext<Cx>, next: &RuleObject<Cx>| {
1576                StandardListTail::<In, Delim>::parse(cx, next).map(|p| p.value.map(|v| v.1))
1577            };
1578
1579            parse_list(&mut cx, next, push, get_first, get_next, &name)?;
1580        }
1581
1582        Ok(Self::new(out))
1583    }
1584}
1585
1586fn parse_list<Cx: CxType, In>(
1587    cx: &mut ParseContext<Cx>,
1588    next: &RuleObject<Cx>,
1589    mut push: impl FnMut(In),
1590    get_first: impl FnOnce(ParseContext<Cx>, &RuleObject<Cx>) -> RuleParseResult<Option<In>>,
1591    mut get_next: impl FnMut(ParseContext<Cx>, &RuleObject<Cx>) -> RuleParseResult<Option<In>>,
1592    name: &dyn fmt::Display,
1593) -> Result<(), RuleParseFailed>
1594where
1595    In: Rule,
1596{
1597    let start_location = cx.location();
1598    let Some(first_item) = get_first(cx.by_ref(), next)? else {
1599        return Ok(());
1600    };
1601
1602    let mut last_location = cx.location();
1603    let mut next_item = get_next(cx.by_ref(), next)?;
1604
1605    if cx.location() > start_location {
1606        push(first_item);
1607    }
1608
1609    while let Some(item) = next_item {
1610        push(item);
1611        if cx.location() > last_location {
1612            last_location = cx.location();
1613        } else {
1614            panic!("Zero-width item matched while parsing {name}");
1615        }
1616
1617        next_item = get_next(cx.by_ref(), next)?;
1618    }
1619
1620    Ok(())
1621}
1622
1623/// An operator-operand pair.
1624#[derive(Debug)]
1625pub struct InfixChainItem<T, Op> {
1626    op: Op,
1627    value: T,
1628}
1629
1630impl<T: Rule, Op: Rule> DelegateRule for InfixChainItem<T, Op> {
1631    type Inner = (Op, T);
1632
1633    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
1634        let Self { op, value } = self;
1635        f.write_str("{ ")?;
1636        op.print_tree(cx, f)?;
1637        f.write_str(", ")?;
1638        value.print_tree(cx, f)?;
1639        f.write_str(" }")
1640    }
1641
1642    fn from_inner((op, value): Self::Inner) -> Self {
1643        Self { op, value }
1644    }
1645}
1646
1647/// Parses a set of binary operations with operand `T` and operator `Op`.
1648#[derive(Debug)]
1649pub struct InfixChain<T, Op> {
1650    first: T,
1651    rest: Vec<InfixChainItem<T, Op>>,
1652}
1653
1654impl<T: Rule, Op: Rule> DelegateRule for InfixChain<T, Op> {
1655    type Inner = (T, Vec<InfixChainItem<T, Op>>);
1656
1657    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
1658        let Self { first, rest } = self;
1659        cx.debug_tuple(
1660            "",
1661            f,
1662            [first as _].into_iter().chain(rest.iter().map(|x| x as _)),
1663        )
1664    }
1665
1666    fn from_inner((first, rest): Self::Inner) -> Self {
1667        Self { first, rest }
1668    }
1669}
1670
1671/// Rule that parses as `T`, but rejects if it parses an empty string.
1672#[non_exhaustive]
1673#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
1674pub struct NotEmpty<T> {
1675    pub value: T,
1676}
1677
1678impl<T: Rule> NotEmpty<T> {
1679    fn adapt_next<Cx: CxType, R>(
1680        orig_start: Location,
1681        next: &RuleObject<Cx>,
1682        block: impl FnOnce(&RuleObject<Cx>) -> R,
1683    ) -> R {
1684        block(&next.adapt(&|mut cx, state, _| {
1685            if state.start > orig_start {
1686                next.pre_parse(cx, state)
1687            } else {
1688                cx.error_at(orig_start);
1689                Err(RuleParseFailed {
1690                    location: orig_start,
1691                })
1692            }
1693        }))
1694    }
1695}
1696
1697impl<T: Rule> Rule for NotEmpty<T> {
1698    fn pre_parse<Cx: CxType>(
1699        cx: ParseContext<Cx>,
1700        state: PreParseState,
1701        next: &RuleObject<Cx>,
1702    ) -> RuleParseResult<()>
1703    where
1704        Self: Sized,
1705    {
1706        Self::adapt_next(state.start, next, |next| T::pre_parse(cx, state, next))
1707    }
1708
1709    fn parse<Cx: CxType>(mut cx: ParseContext<Cx>, next: &RuleObject<Cx>) -> RuleParseResult<Self>
1710    where
1711        Self: Sized,
1712    {
1713        let orig_location = cx.location();
1714        let value = Self::adapt_next(orig_location, next, |next| T::parse(cx.by_ref(), next))?;
1715        if cx.location() > orig_location {
1716            Ok(Self { value })
1717        } else {
1718            cx.error_at(orig_location);
1719            Err(RuleParseFailed {
1720                location: orig_location,
1721            })
1722        }
1723    }
1724
1725    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
1726        self.value.print_tree(cx, f)
1727    }
1728
1729    fn print_name(f: &mut Formatter) -> fmt::Result
1730    where
1731        Self: Sized,
1732    {
1733        f.write_str("NotEmpty(")?;
1734        T::print_name(f)?;
1735        f.write_str(")")?;
1736        Ok(())
1737    }
1738}
1739
1740/// Rule that parses as `Valid`, but rejects if it also parses as `Invalid`.
1741#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
1742pub struct NotParse<Invalid, Valid = ()> {
1743    _invalid: PhantomData<Invalid>,
1744    pub value: Valid,
1745}
1746
1747impl<Invalid: Rule, Valid> NotParse<Invalid, Valid> {
1748    fn validate<Cx: CxType>(cx: &mut ParseContext<Cx>, location: Location) -> RuleParseResult<()> {
1749        let Err(_) = cx.isolated_parse::<Silent<Discard<Invalid>>>(location, default()) else {
1750            cx.error_at(location);
1751            return Err(RuleParseFailed { location });
1752        };
1753        Ok(())
1754    }
1755}
1756
1757impl<Invalid: Rule, Valid: Rule> Rule for NotParse<Invalid, Valid> {
1758    fn print_tree(&self, cx: &PrintContext, f: &mut Formatter) -> fmt::Result {
1759        self.value.print_tree(cx, f)
1760    }
1761
1762    fn print_visibility(&self, cx: &PrintContext) -> PrintVisibility {
1763        self.value.print_visibility(cx)
1764    }
1765
1766    fn pre_parse<Cx: CxType>(
1767        mut cx: ParseContext<Cx>,
1768        state: PreParseState,
1769        next: &RuleObject<Cx>,
1770    ) -> RuleParseResult<()>
1771    where
1772        Self: Sized,
1773    {
1774        Self::validate(&mut cx, state.start)?;
1775        Valid::pre_parse(cx.by_ref(), state, next)?;
1776        Ok(())
1777    }
1778
1779    fn parse<Cx: CxType>(mut cx: ParseContext<Cx>, next: &RuleObject<Cx>) -> RuleParseResult<Self>
1780    where
1781        Self: Sized,
1782    {
1783        let location = cx.location();
1784        Self::validate(&mut cx, location)?;
1785        let value = Valid::parse(cx.by_ref(), next)?;
1786
1787        Ok(Self {
1788            value,
1789            _invalid: PhantomData,
1790        })
1791    }
1792}
1793
1794/// Parses the `Ok(_)` branch, falling back to the `Err(_)` branch.
1795/// Useful for detecting invalid syntax while continuing to parse the rest of the document.
1796/// When processing the AST after it is parsed, check for `Err(_)` values to determine
1797/// if a syntax error occurred.
1798///
1799/// When possible, errors encountered while parsing the `Err(_)` branch are ignored.
1800///
1801/// # Example
1802///
1803/// ```
1804/// gramma::define_token!(
1805///     #[pattern(exact = "(")]
1806///     struct LParen;
1807///     #[pattern(exact = ")")]
1808///     struct RParen;
1809///     #[pattern(regex = r"\w+")]
1810///     struct Scalar;
1811///     #[pattern(regex = r"\s+")]
1812///     struct Whitespace;
1813/// );
1814/// gramma::define_rule!(
1815///     #[transform(ignore_around<Whitespace>)]
1816///     enum ExprKind {
1817///         Group {
1818///             open: LParen,
1819///             #[transform(ignore_after<Whitespace>)]
1820///             content: Content,
1821///             close: Result<RParen, ()>,
1822///         },
1823///         Scalar { scalar: Scalar },
1824///     }
1825///
1826///     struct Expr {
1827///         unexpected_close: Result<(), RParen>,
1828///         kind: ExprKind,
1829///     }
1830///
1831///     #[transform(ignore_around<Whitespace>)]
1832///     struct Content {
1833///         exprs: Vec<Expr>,
1834///         unexpected_close: Result<(), RParen>,
1835///     }
1836/// );
1837///
1838/// let ast = gramma::parse_tree::<Content, 2>(r"
1839///     (a (b c)
1840/// ").unwrap();
1841///
1842/// // The above example's outermost group has a missing close parenthesis:
1843/// assert!(matches!(ast.exprs[0].kind, ExprKind::Group { close: Err(()), .. }));
1844///
1845/// let ast = gramma::parse_tree::<Content, 2>(r"
1846///     (b c) )
1847/// ").unwrap();
1848///
1849/// // The above example ends with an unexpected close parenthesis:
1850/// assert!(matches!(ast, Content { unexpected_close: Err(RParen { .. }), ..}));
1851///
1852/// let ast = gramma::parse_tree::<Content, 2>(r"
1853///     (a (b c))
1854/// ").unwrap();
1855///
1856/// // The above example has balanced parentheses:
1857/// assert!(matches!(ast.exprs[0].kind, ExprKind::Group { close: Ok(_), .. }));
1858/// assert!(matches!(ast, Content { unexpected_close: Ok(()), ..}));
1859/// ```
1860impl<Valid: Rule, Invalid: Rule> DelegateRule for Result<Valid, Invalid> {
1861    type Inner = Either<Valid, Silent<Invalid>>;
1862
1863    fn from_inner(inner: Self::Inner) -> Self {
1864        match inner {
1865            Either::Left(valid) => Ok(valid),
1866            Either::Right(Silent { value: invalid }) => Err(invalid),
1867        }
1868    }
1869}
1870
1871fn extract_actual<'src>(src: &'src str, start: usize) -> &'src str {
1872    if start >= src.len() {
1873        return "<end-of-file>";
1874    }
1875
1876    const MAX_LEN: usize = 32;
1877
1878    let max_end = src.len().min(start + MAX_LEN);
1879
1880    let src_range = string_matcher!(
1881        whitespace().repeat(..).lazy()
1882            + whitespace().not().repeat(1..).lazy()
1883            + (word_boundary() | precedes(whitespace()))
1884    )
1885    .match_string(start, &src[0..max_end])
1886    .unwrap_or(start..src.len().min(start + 1));
1887
1888    &src[src_range]
1889}
1890
1891pub fn display_tree<'data>(
1892    src: &'data str,
1893    ast: &'data impl Rule,
1894) -> impl Debug + fmt::Display + 'data {
1895    WithSource { src, ast }
1896}
1897
1898/// Parses `src` using the rule `T` and lookahead buffer size `N`.
1899pub fn parse_tree<'src, T: Rule, const N: usize>(src: &'src str) -> Result<T, ParseError<'src>> {
1900    match SizedParseContext::<N>::new_with(src, move |cx| {
1901        <(T, ReadToken<Eof>)>::parse(cx, &mut default())
1902    }) {
1903        (Ok((value, _)), _) => Ok(value),
1904        (Err(_), mut err) => {
1905            err.actual = extract_actual(src, err.location.position);
1906            Err(err)
1907        }
1908    }
1909}
gramma/ast/mod.rs

gramma/ast/
mod.rs
