Skip to main content

utils/parser/
macros.rs

1use crate::parser::ParseError;
2
3/// Helper to create a [`parser::byte_lut`](super::byte_lut) parser using `match`-like syntax.
4///
5/// Each expression must be const and must evaluate to a value of the same copy type.
6///
7/// # Examples
8/// ```
9/// # use utils::parser::{Leaf, self};
10/// let parser = parser::byte_map!(
11///     b'#' => true,
12///     b'.' | b'S' => false,
13/// );
14/// assert_eq!(parser.parse(b"#.S##"), Ok((true, &b".S##"[..])));
15/// assert_eq!(parser.parse(b".S##"), Ok((false, &b"S##"[..])));
16/// assert_eq!(parser.parse(b"S##"), Ok((false, &b"##"[..])));
17///
18/// let (err, remaining) = parser.parse(b"abc").unwrap_err();
19/// assert_eq!(err.to_string(), "expected one of '#', '.', 'S'");
20/// assert_eq!(remaining, &b"abc"[..]);
21/// ```
22#[macro_export]
23macro_rules! parser_byte_map {
24    (
25        $($($l:literal)|+ => $e:expr),+$(,)?
26    ) => {{
27        $crate::parser::byte_lut(&const {
28            // Don't use a const item for the lut to avoid naming the value type
29            let mut lut = [None; 256];
30            $($(
31                assert!(lut[$l as usize].is_none(), "duplicate literal");
32                lut[$l as usize] = Some($e);
33            )+)+
34            lut
35        }, const {
36            let mut set = 0u128;
37            $($(
38                let v: u8 = $l;
39                assert!(v < 128, "invalid ASCII");
40                set |= 1u128 << v;
41            )+)+
42            $crate::parser::ParseError::ExpectedOneOf($crate::ascii::AsciiSet::new(set))
43        })
44    }};
45}
46
47/// Helper to create a [`parser::digits_range`](crate::parser::digits_range()) parser using a range.
48///
49/// # Examples
50/// ```
51/// # use utils::parser::{Leaf, self};
52/// let parser = parser::digits_range!(0u32..=15);
53/// assert_eq!(parser.parse(b"12,34"), Ok((12, &b",34"[..])));
54/// assert!(parser.parse(b"16,34").is_err());
55/// ```
56#[macro_export]
57macro_rules! parser_digits_range {
58    ($range:expr) => {
59        $crate::parser::digits_range::<_, { *$range.start() as u128 }, { *$range.end() as u128 }>(
60            $range,
61        )
62    };
63}
64
65/// Helper to create a [`Leaf`](super::Leaf) parser matching string literals using `match`-like
66/// syntax.
67///
68/// This is a replacement for
69/// [`parser::one_of`](crate::parser::one_of())`(("a".map(|_| Enum::A), "b".map(|_| Enum::b)))`
70/// which produces more optimized assembly and is easier to read and write.
71///
72/// The string patterns are matched in the order provided, so strings should be ordered by length.
73///
74/// Using this makes [2017 day 11](../../year2017/struct.Day11.html), which parses a sequence of
75/// literals separated by commas, over 2x faster.
76///
77/// See also [`parser::parsable_enum!`](crate::parser::parsable_enum), which provides a macro to
78/// define an enum and literal parser together.
79///
80/// # Examples
81/// ```
82/// # use utils::parser::{Leaf, self};
83/// #[derive(Debug, PartialEq)]
84/// enum Example {
85///     A,
86///     B,
87///     C,
88/// }
89///
90/// let parser = parser::literal_map!(
91///     "A" | "a" => Example::A,
92///     "B" => Example::B,
93///     "C" => Example::C,
94/// );
95/// assert_eq!(parser.parse(b"A"), Ok((Example::A, &b""[..])));
96/// assert_eq!(parser.parse(b"a"), Ok((Example::A, &b""[..])));
97/// assert_eq!(parser.parse(b"B"), Ok((Example::B, &b""[..])));
98/// assert_eq!(parser.parse(b"C"), Ok((Example::C, &b""[..])));
99/// assert!(parser.parse(b"D").is_err());
100/// ```
101#[macro_export]
102macro_rules! parser_literal_map {
103    (
104        $($($l:literal)|+ => $e:expr),+$(,)?
105    ) => {{
106        $crate::parser::from_leaf_fn(|input| {
107            $($(
108                if input.len() >= const { $l.len() } && const { $l.as_bytes() } == &input[..const { $l.len() }] {
109                    return Ok((($e), &input[const { $l.len() }..]));
110                }
111            )+)*
112
113            Err(($crate::parser_literal_map!(@error $($($l)+)+), input))
114        })
115    }};
116    (@error $first:literal $($l:literal)+) => {
117        $crate::parser::ParseError::Custom(concat!("expected one of '", $first, "'", $(", '", $l, "'",)+))
118    };
119    (@error $first:literal) => {
120        $crate::parser::ParseError::ExpectedLiteral($first)
121    };
122}
123
124/// Helper to define a [`Parseable`](crate::parser::Parseable) fieldless unit-only enum.
125///
126/// The parser is implemented using [`parser::literal_map!`](crate::parser::literal_map) and
127/// [`enumerable_enum!`](crate::enumerable_enum!).
128///
129/// # Examples
130/// ```
131/// # use utils::parser::{Leaf, Parseable, self};
132/// parser::parsable_enum! {
133///     #[derive(Debug, PartialEq, Default)]
134///     enum Direction {
135///         #[default]
136///         "north" | "n" => North,
137///         "south" | "s" => South,
138///         "east" | "e" => East,
139///         "west" | "w" => West,
140///     }
141/// }
142///
143/// assert_eq!(Direction::PARSER.parse(b"north"), Ok((Direction::North, &b""[..])));
144/// assert_eq!(Direction::PARSER.parse(b"s"), Ok((Direction::South, &b""[..])));
145/// assert!(Direction::PARSER.parse(b"a").is_err());
146///
147/// assert_eq!(Direction::COUNT, 4);
148/// ```
149///
150/// With discriminant helpers (requires an explicit `#[repr(...)]` attribute first):
151/// ```
152/// # use utils::parser::{Leaf, Parseable, self};
153/// parser::parsable_enum! {
154///     #[repr(u8)]
155///     #[derive(Debug, PartialEq)]
156///     enum Operation {
157///         "add" => Add,
158///         "mul" => Mul,
159///         "div" => Div,
160///         "mod" => Mod,
161///         "eql" => Eql,
162///     }
163/// }
164///
165/// assert_eq!(Operation::PARSER.parse(b"add5"), Ok((Operation::Add, &b"5"[..])));
166/// assert_eq!(Operation::PARSER.parse(b"eql"), Ok((Operation::Eql, &b""[..])));
167///
168/// assert_eq!(Operation::COUNT, 5);
169/// assert_eq!(Operation::checked_from_discriminant(2), Some(Operation::Div));
170/// ```
171#[macro_export]
172macro_rules! parser_parsable_enum {
173    (
174        $(#[$($enum_meta:tt)+])*
175        enum $name:ident {$(
176            $(#[$meta:meta])*
177            $($l:literal)|+ => $variant:ident $(= $value:expr)?,
178        )+}
179    ) => {
180        // Use tt for enum_meta to avoid the attributes being captured as opaque fragments, which
181        // is required for the correct enumerable_enum arm to be selected for repr enums.
182        $crate::enumerable_enum! {
183            $(#[$($enum_meta)+])*
184            enum $name {$(
185                $(#[$meta])*
186                $variant $(= $value)?,
187            )+}
188        }
189
190        impl $crate::parser::Parseable for $name {
191            type Parser = for<'a> fn(&'a [u8]) -> $crate::parser::LeafResult<'a, Self>;
192            const PARSER: Self::Parser = $crate::parser_literal_map!($(
193                $($l)|+ => Self::$variant,
194            )+);
195        }
196    };
197}
198
199/// Helper to define a custom [`Parser`](super::Parser) using a `match` inspired parse tree syntax.
200///
201/// Each rule is made up of a list of chained parsers enclosed in brackets on the left-hand side.
202/// Parsers can be prefixed with an identifier followed by `@` to store the result of that parser in
203/// the supplied variable, similar to normal match patterns.
204///
205/// After the list of parsers, there is an arrow determining the functionality of the rule when the
206/// parsers match:
207/// - **Expression (`=>`)**: The expression on the right-hand is evaluated and returned.
208/// - **Fallible (`=?>`)**: Similar to Expression, but the right-hand side evaluates a result. If
209///   the expression evaluates to [`Ok`], the value contained inside is returned. Otherwise, the
210///   string contained inside the [`Err`] is handled as a custom [`ParseError`], and parsing will
211///   continue with the following rule.
212/// - **Subtree (`=>>`)**: The right-hand side is a nested set of rules enclosed in braces.
213///
214/// Both the top-level and each `=>>` subtree create their own commit scopes. If a parser commits,
215/// no more branches within the current scope are tried.
216///
217/// As an optimisation, when every rule in a scope starts with a string or byte literal, the
218/// generated parser matches each leading literal with a simple comparison for more efficient
219/// dispatch between rules. If no rule in such a scope matches, the error is "expected one of ..."
220/// listing the rules' leading literals. All leading literals in a scope must be the same type.
221///
222/// # Examples
223/// ```
224/// # use utils::parser::{self, Parser};
225/// #
226/// #[derive(Debug, PartialEq)]
227/// enum Register {
228///     A, B, C
229/// }
230///
231/// #[derive(Debug, PartialEq)]
232/// enum Instruction {
233///     Add(Register, Register),
234///     AddConstant(Register, i32),
235///     Copy(Register, Register),
236///     Noop,
237/// }
238///
239/// let register = parser::literal_map!(
240///     "A" => Register::A, "B" => Register::B, "C" => Register::C,
241/// );
242///
243/// let instruction = parser::parse_tree!(
244///     ("add ", r @ register, ", ") =>> {
245///         (r2 @ register) => Instruction::Add(r, r2),
246///         (v @ parser::i32()) => Instruction::AddConstant(r, v),
247///     },
248///     ("copy ", r @ register, ", ", r2 @ register) =?> {
249///         if r == r2 {
250///             Err("cannot copy register to itself")
251///         } else {
252///             Ok(Instruction::Copy(r, r2))
253///         }
254///     },
255///     ("noop") => Instruction::Noop,
256/// );
257///
258/// assert_eq!(
259///     instruction.parse_complete("add A, B").unwrap(),
260///     Instruction::Add(Register::A, Register::B)
261/// );
262/// assert_eq!(
263///     instruction.parse_complete("add C, 100").unwrap(),
264///     Instruction::AddConstant(Register::C, 100)
265/// );
266/// assert_eq!(
267///     instruction.parse_complete("copy A, B").unwrap(),
268///     Instruction::Copy(Register::A, Register::B)
269/// );
270/// assert!(instruction
271///     .parse_complete("copy A, A")
272///     .is_err_and(|err| err.to_string().contains("cannot copy register to itself")));
273/// assert!(instruction
274///     .parse_complete("mov A, B")
275///     .is_err_and(|err| err.to_string().contains(r#"expected one of "add ", "copy ", "noop""#)));
276/// ```
277#[macro_export]
278macro_rules! parser_parse_tree {
279    (@rule $input:ident $state:ident $commit:ident $token:ident [$(,)?] @expr $rhs:expr) => {
280        return Ok(($rhs, $input));
281    };
282    (@rule $input:ident $state:ident $commit:ident $token:ident [$(,)?] @expr_res $rhs:expr) => {
283        match $rhs {
284            Ok(v) => return Ok((v, $input)),
285            Err(e) => {
286                $token = $state.error($crate::parser::ParseError::Custom(e), $input);
287                if ($commit) {
288                    return Err($token);
289                }
290            }
291        };
292    };
293    (@rule $input:ident $state:ident $commit:ident $token:ident [$(,)?] @subtree $($rhs:tt)+) => {
294        // Consider
295        //  ("add ".commit(), r @ register, ", ") =>> {
296        //      (r2 @ register) => Instruction::Add(r, r2),
297        //      (v @ parser::i32()) => Instruction::AddConstant(r, v),
298        //  },
299        // The inner alternative has its own commit scope, so both branches are tried normally.
300        // However, if both fail then an error should be returned.
301        {
302            let mut $commit = false;
303            $crate::parser_parse_tree!(@scope $input $state $commit $token $($rhs)+);
304        }
305        if ($commit) {
306            return Err($token);
307        }
308    };
309
310    (@rule $input:ident $state:ident $commit:ident $token:ident
311        [$n:ident @ $lhs:expr $(,$($tail:tt)*)?] $($rhs:tt)+
312    ) => {
313        match $crate::parser::Parser::parse_ctx(&($lhs), $input, $state, &mut $commit, false) {
314            Ok(($n, $input)) => {
315                $crate::parser_parse_tree!(@rule $input $state $commit $token
316                    [$($($tail)*)?] $($rhs)+
317                );
318            }
319            Err(t) if $commit => return Err(t),
320            Err(t) => $token = t,
321        };
322    };
323    (@rule $input:ident $state:ident $commit:ident $token:ident
324        [$lhs:expr $(,$($tail:tt)*)?] $($rhs:tt)+
325    ) => {
326        match $crate::parser::Parser::parse_ctx(&($lhs), $input, $state, &mut $commit, false) {
327            Ok((_, $input)) => {
328                $crate::parser_parse_tree!(@rule $input $state $commit $token
329                    [$($($tail)*)?] $($rhs)+
330                );
331            }
332            Err(t) if $commit => return Err(t),
333            Err(t) => $token = t,
334        };
335    };
336
337    // Check whether every rule in the scope starts with a literal, taking a copy of the rules
338    // to emit once the answer is known
339    (@scope $input:ident $state:ident $commit:ident $token:ident $($rules:tt)+) => {
340        $crate::parser_parse_tree!(@check $input $state $commit $token [$($rules)+] $($rules)+)
341    };
342    (@check $input:ident $state:ident $commit:ident $token:ident [$($all:tt)+]
343        ($first:literal $(, $($lhs:tt)*)?) => $rhs:expr $(, $($tail:tt)*)?
344    ) => {
345        $crate::parser_parse_tree!(@check $input $state $commit $token [$($all)+] $($($tail)*)?)
346    };
347    (@check $input:ident $state:ident $commit:ident $token:ident [$($all:tt)+]
348        ($first:literal $(, $($lhs:tt)*)?) =?> $rhs:expr $(, $($tail:tt)*)?
349    ) => {
350        $crate::parser_parse_tree!(@check $input $state $commit $token [$($all)+] $($($tail)*)?)
351    };
352    (@check $input:ident $state:ident $commit:ident $token:ident [$($all:tt)+]
353        ($first:literal $(, $($lhs:tt)*)?) =>> {$($rhs:tt)+} $(, $($tail:tt)*)?
354    ) => {
355        $crate::parser_parse_tree!(@check $input $state $commit $token [$($all)+] $($($tail)*)?)
356    };
357    (@check $input:ident $state:ident $commit:ident $token:ident [$($all:tt)+]) => {
358        $crate::parser_parse_tree!(@lit $input $state $commit $token [] $($all)+)
359    };
360    (@check $input:ident $state:ident $commit:ident $token:ident [$($all:tt)+] $($rest:tt)+) => {
361        $crate::parser_parse_tree!(@seq $input $state $commit $token $($all)+)
362    };
363
364    // Every rule starts with a literal: try to match each literal with a
365    // `LiteralPrefix::strip_literal` comparison instead of the full parser for each literal.
366    // Eliminating the usual parser error path allows the comparisons to be optimized into a
367    // shared byte load and compare chain which dispatches between the rules. If no rule
368    // matches, an error containing all the leading literals is recorded.
369    (@lit $input:ident $state:ident $commit:ident $token:ident [$($lits:tt)*]
370        ($first:literal $(, $($lhs:tt)*)?) => $rhs:expr $(, $($tail:tt)*)?
371    ) => {
372        if let Some($input) = $crate::parser::LiteralPrefix::strip_literal(&$first, $input) {
373            $crate::parser_parse_tree!(@rule $input $state $commit $token
374                [$($($lhs)*)?] @expr $rhs);
375        }
376        $crate::parser_parse_tree!(@lit $input $state $commit $token
377            [$($lits)* $first] $($($tail)*)?);
378    };
379    (@lit $input:ident $state:ident $commit:ident $token:ident [$($lits:tt)*]
380        ($first:literal $(, $($lhs:tt)*)?) =?> $rhs:expr $(, $($tail:tt)*)?
381    ) => {
382        if let Some($input) = $crate::parser::LiteralPrefix::strip_literal(&$first, $input) {
383            $crate::parser_parse_tree!(@rule $input $state $commit $token
384                [$($($lhs)*)?] @expr_res $rhs);
385        }
386        $crate::parser_parse_tree!(@lit $input $state $commit $token
387            [$($lits)* $first] $($($tail)*)?);
388    };
389    (@lit $input:ident $state:ident $commit:ident $token:ident [$($lits:tt)*]
390        ($first:literal $(, $($lhs:tt)*)?) =>> {$($rhs:tt)+} $(, $($tail:tt)*)?
391    ) => {
392        if let Some($input) = $crate::parser::LiteralPrefix::strip_literal(&$first, $input) {
393            $crate::parser_parse_tree!(@rule $input $state $commit $token
394                [$($($lhs)*)?] @subtree $($rhs)+);
395        }
396        $crate::parser_parse_tree!(@lit $input $state $commit $token
397            [$($lits)* $first] $($($tail)*)?);
398    };
399    (@lit $input:ident $state:ident $commit:ident $token:ident [$($first:literal)+]) => {
400        $token = $state.error(
401            $crate::parser::LiteralPrefix::expected_one_of(&[$($first),+]),
402            $input,
403        );
404    };
405
406    // At least one rule starts with a parser: try each rule in order, with every failing rule
407    // recording an error
408    (@seq $input:ident $state:ident $commit:ident $token:ident
409        ($($lhs:tt)+) => $rhs:expr $(, $($tail:tt)*)?
410    ) => {
411        $crate::parser_parse_tree!(@rule $input $state $commit $token [$($lhs)+] @expr $rhs);
412        $($crate::parser_parse_tree!(@seq $input $state $commit $token $($tail)*);)?
413    };
414    (@seq $input:ident $state:ident $commit:ident $token:ident
415        ($($lhs:tt)+) =?> $rhs:expr $(, $($tail:tt)*)?
416    ) => {
417        $crate::parser_parse_tree!(@rule $input $state $commit $token [$($lhs)+] @expr_res $rhs);
418        $($crate::parser_parse_tree!(@seq $input $state $commit $token $($tail)*);)?
419    };
420    (@seq $input:ident $state:ident $commit:ident $token:ident
421        ($($lhs:tt)+) =>> {$($rhs:tt)+} $(, $($tail:tt)*)?
422    ) => {
423        $crate::parser_parse_tree!(@rule $input $state $commit $token [$($lhs)+] @subtree $($rhs)+);
424        $($crate::parser_parse_tree!(@seq $input $state $commit $token $($tail)*);)?
425    };
426    (@seq $input:ident $state:ident $commit:ident $token:ident $(,)?) => {};
427
428    // Ensures this branch only matches inputs starting with (, giving each rule set a unique prefix
429    (($($first:tt)+) $($tail:tt)+) => {{
430        $crate::parser::from_parser_fn(|input, state, _, _| {
431            let mut commit = false;
432            let mut token;
433
434            $crate::parser_parse_tree!(@scope input state commit token ($($first)+) $($tail)+);
435
436            Err(token)
437        })
438    }};
439}
440
441/// Helper trait for rule literals in [`parser::parse_tree!`](crate::parser::parse_tree) scopes.
442pub trait LiteralPrefix: Sized + 'static {
443    /// Returns the remaining input if the input starts with this literal.
444    fn strip_literal<'i>(&self, input: &'i [u8]) -> Option<&'i [u8]>;
445
446    /// Returns a [`ParseError`] containing the expected literals.
447    fn expected_one_of(literals: &'static [Self]) -> ParseError;
448}
449
450impl LiteralPrefix for &'static str {
451    #[inline]
452    fn strip_literal<'i>(&self, input: &'i [u8]) -> Option<&'i [u8]> {
453        let bytes = self.as_bytes();
454
455        // Deliberately redundant with strip_prefix below: LLVM merges the first byte checks
456        // from a parse_tree! scope's successive rules into one shared byte load and compare
457        // chain, dispatching between rules before the full literal comparisons.
458        if !bytes.is_empty() && input.first() != bytes.first() {
459            return None;
460        }
461
462        input.strip_prefix(bytes)
463    }
464
465    #[inline]
466    fn expected_one_of(literals: &'static [Self]) -> ParseError {
467        ParseError::ExpectedOneOfLiterals(literals)
468    }
469}
470
471impl LiteralPrefix for u8 {
472    #[inline]
473    fn strip_literal<'i>(&self, input: &'i [u8]) -> Option<&'i [u8]> {
474        match input {
475            [first, rest @ ..] if first == self => Some(rest),
476            _ => None,
477        }
478    }
479
480    #[inline]
481    fn expected_one_of(literals: &'static [Self]) -> ParseError {
482        ParseError::ExpectedOneOfBytes(literals)
483    }
484}