summaryrefslogtreecommitdiff
path: root/dhall_syntax/src
diff options
context:
space:
mode:
authorNadrieril2019-08-15 16:15:46 +0200
committerNadrieril2019-08-15 16:15:46 +0200
commitf20e7fc0101c28f85c67e3566a16be4beaf2098c (patch)
treef8054ce5c8d4388a6022f4a0657fa92f50579285 /dhall_syntax/src
parente4bdadabeda8ff8dbae0376f9d1c25478b8c8821 (diff)
No need for manual stack handling in parser anymore
Diffstat (limited to 'dhall_syntax/src')
-rw-r--r--dhall_syntax/src/parser.rs238
1 files 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<str>,
- initial_pair: Pair<'a, Rule>,
+ mut pair: Pair<'a, Rule>,
) -> ParseResult<ParsedValue<'a>> {
- enum StackFrame<'a> {
- Unprocessed(Pair<'a, Rule>),
- Processed(Pair<'a, Rule>, usize),
- }
- use StackFrame::*;
- let mut pairs_stack: Vec<StackFrame> =
- vec![Unprocessed(initial_pair.clone())];
- let mut values_stack: Vec<ParsedValue> = 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::<Result<_, _>>()?;
+ 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<ParsedSubExpr> {
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);
}