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}