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

utils/parser/
macros.rs
