No need for manual stack handling in parser anymore

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);
 }