From e4bdadabeda8ff8dbae0376f9d1c25478b8c8821 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Thu, 15 Aug 2019 15:33:53 +0200 Subject: Use precedence climbing to parse expressions with operators This speeds up parsing around 30% --- dhall/build.rs | 5 +- dhall_generated_parser/build.rs | 31 ++++ dhall_generated_parser/src/dhall.pest.visibility | 10 +- dhall_syntax/src/parser.rs | 227 +++++++++++------------ 4 files changed, 147 insertions(+), 126 deletions(-) diff --git a/dhall/build.rs b/dhall/build.rs index cbda288..2305208 100644 --- a/dhall/build.rs +++ b/dhall/build.rs @@ -91,8 +91,9 @@ fn main() -> std::io::Result<()> { let mut file = File::create(parser_tests_path)?; make_test_module(&mut file, "parse", "parser/", "Parser", |path| { - // Too slow in debug mode - path == "success/largeExpression" + false + // Too slow in debug mode + || path == "success/largeExpression" // TODO: projection by expression || path == "success/recordProjectionByExpression" || path == "success/RecordProjectionByType" diff --git a/dhall_generated_parser/build.rs b/dhall_generated_parser/build.rs index 070aa9c..c562fad 100644 --- a/dhall_generated_parser/build.rs +++ b/dhall_generated_parser/build.rs @@ -51,6 +51,37 @@ fn main() -> std::io::Result<()> { }}" )?; + // Setup grammar for precedence climbing + rules.remove("operator_expression"); + writeln!(&mut file, r##" + import_alt = {{ "?" ~ whsp1 }} + bool_or = {{ "||" }} + natural_plus = {{ "+" ~ whsp1 }} + text_append = {{ "++" }} + list_append = {{ "#" }} + bool_and = {{ "&&" }} + natural_times = {{ "*" }} + bool_eq = {{ "==" }} + bool_ne = {{ "!=" }} + + operator = _{{ + equivalent | + bool_ne | + bool_eq | + natural_times | + combine_types | + prefer | + combine | + bool_and | + list_append | + text_append | + natural_plus | + bool_or | + import_alt + }} + operator_expression = {{ application_expression ~ (whsp ~ operator ~ whsp ~ application_expression)* }} + "##)?; + writeln!( &mut file, "final_expression = ${{ SOI ~ complete_expression ~ EOI }}" diff --git a/dhall_generated_parser/src/dhall.pest.visibility b/dhall_generated_parser/src/dhall.pest.visibility index 6b4c974..6fa5e01 100644 --- a/dhall_generated_parser/src/dhall.pest.visibility +++ b/dhall_generated_parser/src/dhall.pest.visibility @@ -84,10 +84,10 @@ Location # Optional_fold # Optional_build # Text_show -# combine -# combine_types -# equivalent -# prefer +combine +combine_types +equivalent +prefer lambda forall arrow @@ -144,7 +144,7 @@ expression annotated_expression let_binding empty_list_literal -# operator_expression +operator_expression import_alt_expression or_expression plus_expression diff --git a/dhall_syntax/src/parser.rs b/dhall_syntax/src/parser.rs index 8ecd0ab..5b213d1 100644 --- a/dhall_syntax/src/parser.rs +++ b/dhall_syntax/src/parser.rs @@ -1,5 +1,6 @@ use itertools::Itertools; use pest::iterators::Pair; +use pest::prec_climber as pcl; use pest::Parser; use std::borrow::Cow; use std::rc::Rc; @@ -219,7 +220,7 @@ macro_rules! make_parser { ); } -// Non-recursive implementation to avoid stack overflows +// (Mostly) non-recursive implementation to avoid stack overflows fn do_parse<'a>( input: Rc, initial_pair: Pair<'a, Rule>, @@ -232,30 +233,122 @@ fn do_parse<'a>( let mut pairs_stack: Vec = vec![Unprocessed(initial_pair.clone())]; let mut values_stack: Vec = vec![]; + + let operators = { + use Rule::*; + // In order of precedence + vec![ + import_alt, + bool_or, + natural_plus, + text_append, + list_append, + bool_and, + combine, + prefer, + combine_types, + natural_times, + bool_eq, + bool_ne, + equivalent, + ] + }; + let rule_to_binop = { + use crate::BinOp::*; + use Rule::*; + |r| { + Some(match r { + import_alt => ImportAlt, + bool_or => BoolOr, + natural_plus => NaturalPlus, + text_append => TextAppend, + list_append => ListAppend, + bool_and => BoolAnd, + combine => RecursiveRecordMerge, + prefer => RightBiasedRecordMerge, + combine_types => RecursiveRecordTypeMerge, + natural_times => NaturalTimes, + bool_eq => BoolEQ, + bool_ne => BoolNE, + equivalent => Equivalence, + _ => return None, + }) + } + }; + let climber = pcl::PrecClimber::new( + operators + .into_iter() + .map(|op| pcl::Operator::new(op, pcl::Assoc::Left)) + .collect(), + ); + while let Some(p) = pairs_stack.pop() { match p { Unprocessed(mut pair) => loop { - let mut pairs: Vec<_> = pair.clone().into_inner().collect(); - let n_children = pairs.len(); - if n_children == 1 && can_be_shortcutted(pair.as_rule()) { - pair = pairs.pop().unwrap(); - continue; + if can_be_shortcutted(pair.as_rule()) { + let mut i = pair.clone().into_inner(); + let first = i.next(); + let second = i.next(); + match (first, second) { + // If pair has exactly one child, just go on parsing that child + (Some(p), None) => { + pair = p; + continue; + } + // Otherwise parse normally + _ => {} + } + } + + // Use precedence climbing to parse operator_expression + if pair.as_rule() == Rule::operator_expression { + let val = climber.climb( + pair.clone().into_inner(), + |p| do_parse(input.clone(), p), + |l, p, r| { + let o = match rule_to_binop(p.as_rule()) { + Some(o) => o, + None => Err(custom_parse_error( + &pair, + format!( + "Rule {:?} isn't an operator", + p.as_rule() + ), + ))?, + }; + use ParsedValue::expression; + match (l?, r?) { + (expression(l), expression(r)) => { + Ok(expression(unspanned(BinOp(o, l, r)))) + } + (l, r) => Err(custom_parse_error( + &pair, + format!( + "Unexpected children: {:?}", + [l, r] + ), + ))?, + } + }, + )?; + values_stack.push(val); + break; } else { - pairs_stack.push(Processed(pair, n_children)); - pairs_stack - .extend(pairs.into_iter().map(StackFrame::Unprocessed)); + let n_children = pair.clone().into_inner().count(); + pairs_stack.push(Processed(pair.clone(), n_children)); + // Push the unparsed children onto the stack + pairs_stack.extend(pair.into_inner().map(Unprocessed)); break; } }, Processed(pair, n) => { + // Take as many values from the values stack as that pair had children. This + // means we get exactly the children of the pair, but now they are parsed. let mut children: Vec<_> = values_stack.split_off(values_stack.len() - n); children.reverse(); - let val = match parse_any(input.clone(), pair.clone(), children) - { - Ok(v) => v, - Err(msg) => Err(custom_parse_error(&pair, msg))?, - }; + let val = parse_any(input.clone(), pair.clone(), children) + .map_err(|msg| custom_parse_error(&pair, msg))?; values_stack.push(val); } } @@ -268,19 +361,7 @@ fn can_be_shortcutted(rule: Rule) -> bool { use Rule::*; match rule { expression - | import_alt_expression - | or_expression - | plus_expression - | text_append_expression - | list_append_expression - | and_expression - | combine_expression - | prefer_expression - | combine_types_expression - | times_expression - | equal_expression - | not_equal_expression - | equivalent_expression + | operator_expression | application_expression | first_application_expression | selector_expression @@ -765,98 +846,6 @@ make_parser! { token_rule!(List<()>); token_rule!(Optional<()>); - rule!(import_alt_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::ImportAlt; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(or_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::BoolOr; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(plus_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::NaturalPlus; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(text_append_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::TextAppend; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(list_append_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::ListAppend; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(and_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::BoolAnd; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(combine_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::RecursiveRecordMerge; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(prefer_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::RightBiasedRecordMerge; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(combine_types_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::RecursiveRecordTypeMerge; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(times_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::NaturalTimes; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(equal_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::BoolEQ; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(not_equal_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::BoolNE; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(equivalent_expression as expression; children!( - [expression(e)] => e, - [expression(first), expression(rest)..] => { - let o = crate::BinOp::Equivalence; - rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e))) - }, - )); - rule!(annotated_expression as expression; span; children!( [expression(e)] => e, [expression(e), expression(annot)] => { -- cgit v1.2.3 From f20e7fc0101c28f85c67e3566a16be4beaf2098c Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Thu, 15 Aug 2019 16:15:46 +0200 Subject: No need for manual stack handling in parser anymore --- dhall_syntax/src/parser.rs | 238 ++++++++++++++++++--------------------------- 1 file changed, 96 insertions(+), 142 deletions(-) diff --git a/dhall_syntax/src/parser.rs b/dhall_syntax/src/parser.rs index 5b213d1..52b4426 100644 --- a/dhall_syntax/src/parser.rs +++ b/dhall_syntax/src/parser.rs @@ -220,140 +220,111 @@ macro_rules! make_parser { ); } -// (Mostly) non-recursive implementation to avoid stack overflows fn do_parse<'a>( input: Rc, - initial_pair: Pair<'a, Rule>, + mut pair: Pair<'a, Rule>, ) -> ParseResult> { - enum StackFrame<'a> { - Unprocessed(Pair<'a, Rule>), - Processed(Pair<'a, Rule>, usize), - } - use StackFrame::*; - let mut pairs_stack: Vec = - vec![Unprocessed(initial_pair.clone())]; - let mut values_stack: Vec = vec![]; - - let operators = { - use Rule::*; - // In order of precedence - vec![ - import_alt, - bool_or, - natural_plus, - text_append, - list_append, - bool_and, - combine, - prefer, - combine_types, - natural_times, - bool_eq, - bool_ne, - equivalent, - ] - }; - let rule_to_binop = { - use crate::BinOp::*; - use Rule::*; - |r| { - Some(match r { - import_alt => ImportAlt, - bool_or => BoolOr, - natural_plus => NaturalPlus, - text_append => TextAppend, - list_append => ListAppend, - bool_and => BoolAnd, - combine => RecursiveRecordMerge, - prefer => RightBiasedRecordMerge, - combine_types => RecursiveRecordTypeMerge, - natural_times => NaturalTimes, - bool_eq => BoolEQ, - bool_ne => BoolNE, - equivalent => Equivalence, - _ => return None, - }) + // Avoid parsing while the pair has exactly one child that can be returned as-is + loop { + if can_be_shortcutted(pair.as_rule()) { + let mut i = pair.clone().into_inner(); + let first = i.next(); + let second = i.next(); + match (first, second) { + // If pair has exactly one child, just go on parsing that child + (Some(p), None) => { + pair = p; + continue; + } + // Otherwise parse normally + _ => break, + } } - }; - let climber = pcl::PrecClimber::new( - operators - .into_iter() - .map(|op| pcl::Operator::new(op, pcl::Assoc::Left)) - .collect(), - ); + break; + } - while let Some(p) = pairs_stack.pop() { - match p { - Unprocessed(mut pair) => loop { - if can_be_shortcutted(pair.as_rule()) { - let mut i = pair.clone().into_inner(); - let first = i.next(); - let second = i.next(); - match (first, second) { - // If pair has exactly one child, just go on parsing that child - (Some(p), None) => { - pair = p; - continue; - } - // Otherwise parse normally - _ => {} + // Use precedence climbing to parse operator_expression + if pair.as_rule() == Rule::operator_expression { + let rule_to_binop = { + use crate::BinOp::*; + use Rule::*; + |r| { + Some(match r { + import_alt => ImportAlt, + bool_or => BoolOr, + natural_plus => NaturalPlus, + text_append => TextAppend, + list_append => ListAppend, + bool_and => BoolAnd, + combine => RecursiveRecordMerge, + prefer => RightBiasedRecordMerge, + combine_types => RecursiveRecordTypeMerge, + natural_times => NaturalTimes, + bool_eq => BoolEQ, + bool_ne => BoolNE, + equivalent => Equivalence, + _ => return None, + }) + } + }; + let operators = { + use Rule::*; + // In order of precedence + vec![ + import_alt, + bool_or, + natural_plus, + text_append, + list_append, + bool_and, + combine, + prefer, + combine_types, + natural_times, + bool_eq, + bool_ne, + equivalent, + ] + }; + let climber = pcl::PrecClimber::new( + operators + .into_iter() + .map(|op| pcl::Operator::new(op, pcl::Assoc::Left)) + .collect(), + ); + + climber.climb( + pair.clone().into_inner(), + |p| do_parse(input.clone(), p), + |l, p, r| { + let o = match rule_to_binop(p.as_rule()) { + Some(o) => o, + None => Err(custom_parse_error( + &pair, + format!("Rule {:?} isn't an operator", p.as_rule()), + ))?, + }; + use ParsedValue::expression; + match (l?, r?) { + (expression(l), expression(r)) => { + Ok(expression(unspanned(BinOp(o, l, r)))) } - } - - // Use precedence climbing to parse operator_expression - if pair.as_rule() == Rule::operator_expression { - let val = climber.climb( - pair.clone().into_inner(), - |p| do_parse(input.clone(), p), - |l, p, r| { - let o = match rule_to_binop(p.as_rule()) { - Some(o) => o, - None => Err(custom_parse_error( - &pair, - format!( - "Rule {:?} isn't an operator", - p.as_rule() - ), - ))?, - }; - use ParsedValue::expression; - match (l?, r?) { - (expression(l), expression(r)) => { - Ok(expression(unspanned(BinOp(o, l, r)))) - } - (l, r) => Err(custom_parse_error( - &pair, - format!( - "Unexpected children: {:?}", - [l, r] - ), - ))?, - } - }, - )?; - values_stack.push(val); - break; - } else { - let n_children = pair.clone().into_inner().count(); - pairs_stack.push(Processed(pair.clone(), n_children)); - // Push the unparsed children onto the stack - pairs_stack.extend(pair.into_inner().map(Unprocessed)); - break; + (l, r) => Err(custom_parse_error( + &pair, + format!("Unexpected children: {:?}", [l, r]), + ))?, } }, - Processed(pair, n) => { - // Take as many values from the values stack as that pair had children. This - // means we get exactly the children of the pair, but now they are parsed. - let mut children: Vec<_> = - values_stack.split_off(values_stack.len() - n); - children.reverse(); - let val = parse_any(input.clone(), pair.clone(), children) - .map_err(|msg| custom_parse_error(&pair, msg))?; - values_stack.push(val); - } - } + ) + } else { + let children = pair + .clone() + .into_inner() + .map(|p| do_parse(input.clone(), p)) + .collect::>()?; + parse_any(input.clone(), pair.clone(), children) + .map_err(|msg| custom_parse_error(&pair, msg)) } - Ok(values_stack.pop().unwrap()) } // List of rules that can be shortcutted if they have a single child @@ -985,21 +956,4 @@ pub fn parse_expr(s: &str) -> ParseResult { ParsedValue::expression(e) => Ok(e), _ => unreachable!(), } - // Ok(BoolLit(false)) -} - -#[test] -fn test_parse() { - // let expr = r#"{ x = "foo", y = 4 }.x"#; - // let expr = r#"(1 + 2) * 3"#; - let expr = r#"(1) + 3 * 5"#; - println!("{:?}", parse_expr(expr)); - match parse_expr(expr) { - Err(e) => { - println!("{:?}", e); - println!("{}", e); - } - ok => println!("{:?}", ok), - }; - // assert!(false); } -- cgit v1.2.3 From ffb5a4c26960960f526719d9b333df80119fef3c Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Thu, 15 Aug 2019 17:59:01 +0200 Subject: Include precedence parsing in parser macros --- dhall_syntax/src/lib.rs | 1 + dhall_syntax/src/parser.rs | 320 ++++++++++++++++++++++++++------------------- 2 files changed, 188 insertions(+), 133 deletions(-) diff --git a/dhall_syntax/src/lib.rs b/dhall_syntax/src/lib.rs index 193c6ea..8406595 100644 --- a/dhall_syntax/src/lib.rs +++ b/dhall_syntax/src/lib.rs @@ -1,5 +1,6 @@ #![feature(trace_macros)] #![feature(slice_patterns)] +#![feature(try_blocks)] #![allow( clippy::many_single_char_names, clippy::should_implement_trait, diff --git a/dhall_syntax/src/parser.rs b/dhall_syntax/src/parser.rs index 52b4426..d467970 100644 --- a/dhall_syntax/src/parser.rs +++ b/dhall_syntax/src/parser.rs @@ -1,8 +1,10 @@ use itertools::Itertools; use pest::iterators::Pair; use pest::prec_climber as pcl; +use pest::prec_climber::PrecClimber; use pest::Parser; use std::borrow::Cow; +use std::collections::HashMap; use std::rc::Rc; use dhall_generated_parser::{DhallParser, Rule}; @@ -125,61 +127,117 @@ macro_rules! make_parser { (@filter, token_rule) => (true); (@filter, rule_group) => (false); - (@body, - ($($things:tt)*), - rule!( $name:ident<$o:ty>; $($args:tt)* ) - ) => ( - make_parser!(@body, - ($($things)*), - rule!( $name<$o> as $name; $($args)* ) + (@construct_climber, + ($map:expr), + rule!( + $name:ident<$o:ty> + as $group:ident; + prec_climb!( $climber:expr, $($_rest:tt)* ) ) - ); + ) => ({ + $map.insert(Rule::$name, $climber) + }); + (@construct_climber, ($($things:tt)*), $($args:tt)*) => (()); + (@body, - ($_input:expr, $pair:expr, $_children:expr), + ($climbers:expr, $input:expr, $pair:expr), rule!( $name:ident<$o:ty> as $group:ident; + $span:ident; captured_str!($x:pat) => $body:expr ) ) => ({ - let $x = $pair.as_str(); - let res: $o = $body; - Ok(ParsedValue::$group(res)) + let res: Result<_, String> = try { + let $span = Span::make($input, $pair.as_span()); + let $x = $pair.as_str(); + ParsedValue::$group($body) + }; + res.map_err(|msg| custom_parse_error(&$pair, msg)) }); (@body, - ($_input:expr, $_pair:expr, $children:expr), + ($climbers:expr, $input:expr, $pair:expr), rule!( $name:ident<$o:ty> as $group:ident; + $span:ident; children!( $( [$($args:tt)*] => $body:expr ),* $(,)* ) ) ) => ({ - #[allow(unused_imports)] - use ParsedValue::*; + let children: Vec<_> = $pair + .clone() + .into_inner() + .map(|p| parse_any($climbers, $input.clone(), p)) + .collect::>()?; + #[allow(unreachable_code)] - let res: $o = improved_slice_patterns::match_vec!($children; - $( [$($args)*] => $body, )* - [x..] => Err( - format!("Unexpected children: {:?}", x.collect::>()) - )?, - ).map_err(|_| -> String { unreachable!() })?; + let res: Result<_, String> = try { + #[allow(unused_imports)] + use ParsedValue::*; + let $span = Span::make($input, $pair.as_span()); + + improved_slice_patterns::match_vec!(children; + $( [$($args)*] => $body, )* + [x..] => Err( + format!("Unexpected children: {:?}", x.collect::>()) + )?, + ).map_err(|_| -> String { unreachable!() })? + }; + + let res = res.map_err(|msg| custom_parse_error(&$pair, msg))?; Ok(ParsedValue::$group(res)) }); (@body, - ($input:expr, $pair:expr, $children:expr), + ($climbers:expr, $input:expr, $pair:expr), + rule!( + $name:ident<$o:ty> + as $group:ident; + prec_climb!( $_climber:expr, $args:pat => $body:expr $(,)* ) + ) + ) => ({ + let climber = $climbers.get(&Rule::$name).unwrap(); + climber.climb( + $pair.clone().into_inner(), + |p| parse_any($climbers, $input.clone(), p), + |l, op, r| { + let (l, r) = (l?, r?); + let res: Result<_, String> = try { + #[allow(unused_imports)] + use ParsedValue::*; + match (l, op, r) { + $args => ParsedValue::$group($body), + children => Err( + format!("Unexpected children: {:?}", children) + )?, + } + }; + res.map_err(|msg| custom_parse_error(&$pair, msg)) + }, + ) + }); + (@body, + ($($things:tt)*), + rule!( $name:ident<$o:ty>; $($args:tt)* ) + ) => ( + make_parser!(@body, + ($($things)*), + rule!( $name<$o> as $name; $($args)* ) + ) + ); + (@body, + ($($things:tt)*), rule!( $name:ident<$o:ty> as $group:ident; - $span:ident; $($args:tt)* ) ) => ({ - let $span = Span::make($input, $pair.as_span()); make_parser!(@body, - ($input, $pair, $children), + ($($things)*), rule!( $name<$o> as $group; + _span; $($args)* ) ) @@ -201,20 +259,63 @@ macro_rules! make_parser { $( $name($o), )* } + fn construct_precclimbers() -> HashMap> { + let mut map = HashMap::new(); + $( + make_parser!(@construct_climber, (map), + $submac!( $name<$o> $($args)* )); + )* + map + } + + struct Parsers; + + impl Parsers { + $( + #[allow(non_snake_case, unused_variables)] + fn $name<'a>( + climbers: &HashMap>, + input: Rc, + pair: Pair<'a, Rule>, + ) -> ParseResult> { + make_parser!(@body, (climbers, input, pair), + $submac!( $name<$o> $($args)* )) + } + )* + } + fn parse_any<'a>( + climbers: &HashMap>, input: Rc, - pair: Pair<'a, Rule>, - children: Vec>, - ) -> Result, String> { + mut pair: Pair<'a, Rule>, + ) -> ParseResult> { + // Avoid parsing while the pair has exactly one child that can be returned as-is + loop { + if can_be_shortcutted(pair.as_rule()) { + let mut i = pair.clone().into_inner(); + let first = i.next(); + let second = i.next(); + match (first, second) { + // If pair has exactly one child, just go on parsing that child + (Some(p), None) => { + pair = p; + continue; + } + // Otherwise parse normally + _ => break, + } + } + break; + } + match pair.as_rule() { $( make_parser!(@pattern, $submac, $name) if make_parser!(@filter, $submac) - => make_parser!(@body, (input, pair, children), - $submac!( $name<$o> $($args)* )) + => Parsers::$name(climbers, input, pair) , )* - r => Err(format!("Unexpected {:?}", r)), + r => Err(custom_parse_error(&pair, format!("Unexpected {:?}", r))), } } ); @@ -222,109 +323,10 @@ macro_rules! make_parser { fn do_parse<'a>( input: Rc, - mut pair: Pair<'a, Rule>, + pair: Pair<'a, Rule>, ) -> ParseResult> { - // Avoid parsing while the pair has exactly one child that can be returned as-is - loop { - if can_be_shortcutted(pair.as_rule()) { - let mut i = pair.clone().into_inner(); - let first = i.next(); - let second = i.next(); - match (first, second) { - // If pair has exactly one child, just go on parsing that child - (Some(p), None) => { - pair = p; - continue; - } - // Otherwise parse normally - _ => break, - } - } - break; - } - - // Use precedence climbing to parse operator_expression - if pair.as_rule() == Rule::operator_expression { - let rule_to_binop = { - use crate::BinOp::*; - use Rule::*; - |r| { - Some(match r { - import_alt => ImportAlt, - bool_or => BoolOr, - natural_plus => NaturalPlus, - text_append => TextAppend, - list_append => ListAppend, - bool_and => BoolAnd, - combine => RecursiveRecordMerge, - prefer => RightBiasedRecordMerge, - combine_types => RecursiveRecordTypeMerge, - natural_times => NaturalTimes, - bool_eq => BoolEQ, - bool_ne => BoolNE, - equivalent => Equivalence, - _ => return None, - }) - } - }; - let operators = { - use Rule::*; - // In order of precedence - vec![ - import_alt, - bool_or, - natural_plus, - text_append, - list_append, - bool_and, - combine, - prefer, - combine_types, - natural_times, - bool_eq, - bool_ne, - equivalent, - ] - }; - let climber = pcl::PrecClimber::new( - operators - .into_iter() - .map(|op| pcl::Operator::new(op, pcl::Assoc::Left)) - .collect(), - ); - - climber.climb( - pair.clone().into_inner(), - |p| do_parse(input.clone(), p), - |l, p, r| { - let o = match rule_to_binop(p.as_rule()) { - Some(o) => o, - None => Err(custom_parse_error( - &pair, - format!("Rule {:?} isn't an operator", p.as_rule()), - ))?, - }; - use ParsedValue::expression; - match (l?, r?) { - (expression(l), expression(r)) => { - Ok(expression(unspanned(BinOp(o, l, r)))) - } - (l, r) => Err(custom_parse_error( - &pair, - format!("Unexpected children: {:?}", [l, r]), - ))?, - } - }, - ) - } else { - let children = pair - .clone() - .into_inner() - .map(|p| do_parse(input.clone(), p)) - .collect::>()?; - parse_any(input.clone(), pair.clone(), children) - .map_err(|msg| custom_parse_error(&pair, msg)) - } + let climbers = construct_precclimbers(); + parse_any(&climbers, input, pair) } // List of rules that can be shortcutted if they have a single child @@ -824,6 +826,58 @@ make_parser! { }, )); + rule!(operator_expression as expression; prec_climb!( + { + use Rule::*; + // In order of precedence + let operators = vec![ + import_alt, + bool_or, + natural_plus, + text_append, + list_append, + bool_and, + combine, + prefer, + combine_types, + natural_times, + bool_eq, + bool_ne, + equivalent, + ]; + PrecClimber::new( + operators + .into_iter() + .map(|op| pcl::Operator::new(op, pcl::Assoc::Left)) + .collect(), + ) + }, + (expression(l), op, expression(r)) => { + use crate::BinOp::*; + use Rule::*; + let op = match op.as_rule() { + import_alt => ImportAlt, + bool_or => BoolOr, + natural_plus => NaturalPlus, + text_append => TextAppend, + list_append => ListAppend, + bool_and => BoolAnd, + combine => RecursiveRecordMerge, + prefer => RightBiasedRecordMerge, + combine_types => RecursiveRecordTypeMerge, + natural_times => NaturalTimes, + bool_eq => BoolEQ, + bool_ne => BoolNE, + equivalent => Equivalence, + r => Err( + format!("Rule {:?} isn't an operator", r), + )?, + }; + + unspanned(BinOp(op, l, r)) + } + )); + token_rule!(Some_<()>); token_rule!(toMap<()>); -- cgit v1.2.3