Change parser macros to use a function-like syntax

This makes the parser code look much less magical.

2 files changed, 928 insertions, 748 deletions

diff --git a/dhall_syntax/src/lib.rs b/dhall_syntax/src/lib.rs
index e4a6077..290f53c 100644
--- a/dhall_syntax/src/lib.rs
+++ b/dhall_syntax/src/lib.rs
@@ -3,6 +3,7 @@
 #![feature(try_blocks)]
 #![feature(never_type)]
 #![feature(bind_by_move_pattern_guards)]
+#![feature(proc_macro_hygiene)]
 #![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 4fd6f57..fa2d7c5 100644
--- a/dhall_syntax/src/parser.rs
+++ b/dhall_syntax/src/parser.rs
@@ -8,6 +8,7 @@ use std::collections::HashMap;
 use std::rc::Rc;
 
 use dhall_generated_parser::{DhallParser, Rule};
+use dhall_proc_macros::{make_parser, parse_children};
 
 use crate::map::{DupTreeMap, DupTreeSet};
 use crate::ExprF::*;
@@ -27,55 +28,39 @@ pub type ParseError = pest::error::Error<Rule>;
 
 pub type ParseResult<T> = Result<T, ParseError>;
 
-#[derive(Debug)]
-enum Either<A, B> {
-    Left(A),
-    Right(B),
+#[derive(Debug, Clone)]
+struct ParseInput<'input, 'climbers, Rule>
+where
+    Rule: std::fmt::Debug + Copy + std::hash::Hash + Ord,
+{
+    pair: Pair<'input, Rule>,
+    climbers: &'climbers HashMap<Rule, PrecClimber<Rule>>,
+    original_input_str: Rc<str>,
 }
 
-impl crate::Builtin {
-    pub fn parse(s: &str) -> Option<Self> {
-        use crate::Builtin::*;
-        match s {
-            "Bool" => Some(Bool),
-            "Natural" => Some(Natural),
-            "Integer" => Some(Integer),
-            "Double" => Some(Double),
-            "Text" => Some(Text),
-            "List" => Some(List),
-            "Optional" => Some(Optional),
-            "None" => Some(OptionalNone),
-            "Natural/build" => Some(NaturalBuild),
-            "Natural/fold" => Some(NaturalFold),
-            "Natural/isZero" => Some(NaturalIsZero),
-            "Natural/even" => Some(NaturalEven),
-            "Natural/odd" => Some(NaturalOdd),
-            "Natural/toInteger" => Some(NaturalToInteger),
-            "Natural/show" => Some(NaturalShow),
-            "Natural/subtract" => Some(NaturalSubtract),
-            "Integer/toDouble" => Some(IntegerToDouble),
-            "Integer/show" => Some(IntegerShow),
-            "Double/show" => Some(DoubleShow),
-            "List/build" => Some(ListBuild),
-            "List/fold" => Some(ListFold),
-            "List/length" => Some(ListLength),
-            "List/head" => Some(ListHead),
-            "List/last" => Some(ListLast),
-            "List/indexed" => Some(ListIndexed),
-            "List/reverse" => Some(ListReverse),
-            "Optional/fold" => Some(OptionalFold),
-            "Optional/build" => Some(OptionalBuild),
-            "Text/show" => Some(TextShow),
-            _ => None,
+impl<'input, 'climbers> ParseInput<'input, 'climbers, Rule> {
+    fn error(&self, message: String) -> ParseError {
+        let message = format!(
+            "{} while matching on:\n{}",
+            message,
+            debug_pair(self.pair.clone())
+        );
+        let e = pest::error::ErrorVariant::CustomError { message };
+        pest::error::Error::new_from_span(e, self.pair.as_span())
+    }
+    fn with_pair(&self, new_pair: Pair<'input, Rule>) -> Self {
+        ParseInput {
+            pair: new_pair,
+            climbers: self.climbers,
+            original_input_str: self.original_input_str.clone(),
         }
     }
-}
-
-pub fn custom_parse_error(pair: &Pair<Rule>, msg: String) -> ParseError {
-    let msg =
-        format!("{} while matching on:\n{}", msg, debug_pair(pair.clone()));
-    let e = pest::error::ErrorVariant::CustomError { message: msg };
-    pest::error::Error::new_from_span(e, pair.as_span())
+    fn as_span(&self) -> Span {
+        Span::make(self.original_input_str.clone(), self.pair.as_span())
+    }
+    fn as_str(&self) -> &'input str {
+        self.pair.as_str()
+    }
 }
 
 fn debug_pair(pair: Pair<Rule>) -> String {
@@ -119,74 +104,48 @@ fn debug_pair(pair: Pair<Rule>) -> String {
     s
 }
 
-macro_rules! parse_children {
-    // Variable length pattern with a common unary variant
-    (@match_forwards,
-        $parse_args:expr,
-        $iter:expr,
-        ($body:expr),
-        $variant:ident ($x:ident)..,
-        $($rest:tt)*
-    ) => {
-        parse_children!(@match_backwards,
-            $parse_args, $iter,
-            ({
-                let $x = $iter
-                    .map(|x| Parsers::$variant($parse_args, x))
-                    .collect::<Result<Vec<_>, _>>()?
-                    .into_iter();
-                $body
-            }),
-            $($rest)*
-        )
-    };
-    // Single item pattern
-    (@match_forwards,
-        $parse_args:expr,
-        $iter:expr,
-        ($body:expr),
-        $variant:ident ($x:pat),
-        $($rest:tt)*
-    ) => {{
-        let p = $iter.next().unwrap();
-        let $x = Parsers::$variant($parse_args, p)?;
-        parse_children!(@match_forwards,
-            $parse_args, $iter,
-            ($body),
-            $($rest)*
-        )
-    }};
-    // Single item pattern after a variable length one: declare reversed and take from the end
-    (@match_backwards,
-        $parse_args:expr,
-        $iter:expr,
-        ($body:expr),
-        $variant:ident ($x:pat),
-        $($rest:tt)*
-    ) => {
-        parse_children!(@match_backwards, $parse_args, $iter, ({
-            let p = $iter.next_back().unwrap();
-            let $x = Parsers::$variant($parse_args, p)?;
-            $body
-        }), $($rest)*)
-    };
-
-    // Check no elements remain
-    (@match_forwards, $parse_args:expr, $iter:expr, ($body:expr) $(,)*) => {
-        $body
-    };
-    // After a variable length pattern, everything has already been consumed
-    (@match_backwards, $parse_args:expr, $iter:expr, ($body:expr) $(,)*) => {
-        $body
-    };
+#[derive(Debug)]
+enum Either<A, B> {
+    Left(A),
+    Right(B),
+}
 
-    ($parse_args:expr, $iter:expr; [$($args:tt)*] => $body:expr) => {
-        parse_children!(@match_forwards,
-            $parse_args, $iter,
-            ($body),
-            $($args)*,
-        )
-    };
+impl crate::Builtin {
+    pub fn parse(s: &str) -> Option<Self> {
+        use crate::Builtin::*;
+        match s {
+            "Bool" => Some(Bool),
+            "Natural" => Some(Natural),
+            "Integer" => Some(Integer),
+            "Double" => Some(Double),
+            "Text" => Some(Text),
+            "List" => Some(List),
+            "Optional" => Some(Optional),
+            "None" => Some(OptionalNone),
+            "Natural/build" => Some(NaturalBuild),
+            "Natural/fold" => Some(NaturalFold),
+            "Natural/isZero" => Some(NaturalIsZero),
+            "Natural/even" => Some(NaturalEven),
+            "Natural/odd" => Some(NaturalOdd),
+            "Natural/toInteger" => Some(NaturalToInteger),
+            "Natural/show" => Some(NaturalShow),
+            "Natural/subtract" => Some(NaturalSubtract),
+            "Integer/toDouble" => Some(IntegerToDouble),
+            "Integer/show" => Some(IntegerShow),
+            "Double/show" => Some(DoubleShow),
+            "List/build" => Some(ListBuild),
+            "List/fold" => Some(ListFold),
+            "List/length" => Some(ListLength),
+            "List/head" => Some(ListHead),
+            "List/last" => Some(ListLast),
+            "List/indexed" => Some(ListIndexed),
+            "List/reverse" => Some(ListReverse),
+            "Optional/fold" => Some(OptionalFold),
+            "Optional/build" => Some(OptionalBuild),
+            "Text/show" => Some(TextShow),
+            _ => None,
+        }
+    }
 }
 
 // Trim the shared indent off of a vec of lines, as defined by the Dhall semantics of multiline
@@ -230,674 +189,894 @@ fn trim_indent(lines: &mut Vec<ParsedText>) {
     }
 }
 
-dhall_proc_macros::make_parser! {
-    rule!(EOI<()>);
-
-    rule!(simple_label<Label>;
-        captured_str!(s) => Label::from(s.trim().to_owned())
-    );
-    rule!(quoted_label<Label>;
-        captured_str!(s) => Label::from(s.trim().to_owned())
-    );
-    rule!(label<Label>; children!(
-        [simple_label(l)] => l,
-        [quoted_label(l)] => l,
-    ));
-
-    rule!(double_quote_literal<ParsedText>; children!(
-        [double_quote_chunk(chunks)..] => {
-            chunks.collect()
-        }
-    ));
-
-    rule!(double_quote_chunk<ParsedTextContents>; children!(
-        [interpolation(e)] => {
-            InterpolatedTextContents::Expr(e)
-        },
-        [double_quote_escaped(s)] => {
-            InterpolatedTextContents::Text(s)
-        },
-        [double_quote_char(s)] => {
-            InterpolatedTextContents::Text(s.to_owned())
-        },
-    ));
-    rule!(double_quote_escaped<String>;
-        captured_str!(s) => {
-            match s {
-                "\"" => "\"".to_owned(),
-                "$" => "$".to_owned(),
-                "\\" => "\\".to_owned(),
-                "/" => "/".to_owned(),
-                "b" => "\u{0008}".to_owned(),
-                "f" => "\u{000C}".to_owned(),
-                "n" => "\n".to_owned(),
-                "r" => "\r".to_owned(),
-                "t" => "\t".to_owned(),
-                // "uXXXX" or "u{XXXXX}"
-                _ => {
-                    use std::convert::{TryFrom, TryInto};
-
-                    let s = &s[1..];
-                    let s = if &s[0..1] == "{" {
-                        &s[1..s.len()-1]
-                    } else {
-                        &s[0..s.len()]
-                    };
-
-                    if s.len() > 8 {
-                        Err(format!("Escape sequences can't have more than 8 chars: \"{}\"", s))?
-                    }
+fn make_precclimber() -> PrecClimber<Rule> {
+    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(),
+    )
+}
+
+make_parser! {
+    fn EOI(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+
+    fn simple_label(input: ParseInput<Rule>) -> ParseResult<Label> {
+        Ok(Label::from(input.as_str().trim().to_owned()))
+    }
+    fn quoted_label(input: ParseInput<Rule>) -> ParseResult<Label> {
+        Ok(Label::from(input.as_str().trim().to_owned()))
+    }
+    fn label(input: ParseInput<Rule>) -> ParseResult<Label> {
+        Ok(parse_children!(input;
+            [simple_label(l)] => l,
+            [quoted_label(l)] => l,
+        ))
+    }
+
+    fn double_quote_literal(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<ParsedText> {
+        Ok(parse_children!(input;
+            [double_quote_chunk(chunks)..] => {
+                chunks.collect()
+            }
+        ))
+    }
 
-                    // pad with zeroes
-                    let s: String = std::iter::repeat('0')
-                        .take(8 - s.len())
-                        .chain(s.chars())
-                        .collect();
-
-                    // `s` has length 8, so `bytes` has length 4
-                    let bytes: &[u8] = &hex::decode(s).unwrap();
-                    let i = u32::from_be_bytes(bytes.try_into().unwrap());
-                    let c = char::try_from(i).unwrap();
-                    match i {
-                        0xD800..=0xDFFF => {
-                            let c_ecapsed = c.escape_unicode();
-                            Err(format!("Escape sequences can't contain surrogate pairs: \"{}\"", c_ecapsed))?
-                        },
-                        0x0FFFE..=0x0FFFF | 0x1FFFE..=0x1FFFF |
-                        0x2FFFE..=0x2FFFF | 0x3FFFE..=0x3FFFF |
-                        0x4FFFE..=0x4FFFF | 0x5FFFE..=0x5FFFF |
-                        0x6FFFE..=0x6FFFF | 0x7FFFE..=0x7FFFF |
-                        0x8FFFE..=0x8FFFF | 0x9FFFE..=0x9FFFF |
-                        0xAFFFE..=0xAFFFF | 0xBFFFE..=0xBFFFF |
-                        0xCFFFE..=0xCFFFF | 0xDFFFE..=0xDFFFF |
-                        0xEFFFE..=0xEFFFF | 0xFFFFE..=0xFFFFF |
-                        0x10_FFFE..=0x10_FFFF => {
-                            let c_ecapsed = c.escape_unicode();
-                            Err(format!("Escape sequences can't contain non-characters: \"{}\"", c_ecapsed))?
-                        },
-                        _ => {}
+    fn double_quote_chunk(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<ParsedTextContents> {
+        Ok(parse_children!(input;
+            [interpolation(e)] => {
+                InterpolatedTextContents::Expr(e)
+            },
+            [double_quote_escaped(s)] => {
+                InterpolatedTextContents::Text(s)
+            },
+            [double_quote_char(s)] => {
+                InterpolatedTextContents::Text(s.to_owned())
+            },
+        ))
+    }
+    fn double_quote_escaped(input: ParseInput<Rule>) -> ParseResult<String> {
+        Ok(match input.as_str() {
+            "\"" => "\"".to_owned(),
+            "$" => "$".to_owned(),
+            "\\" => "\\".to_owned(),
+            "/" => "/".to_owned(),
+            "b" => "\u{0008}".to_owned(),
+            "f" => "\u{000C}".to_owned(),
+            "n" => "\n".to_owned(),
+            "r" => "\r".to_owned(),
+            "t" => "\t".to_owned(),
+            // "uXXXX" or "u{XXXXX}"
+            s => {
+                use std::convert::{TryFrom, TryInto};
+
+                let s = &s[1..];
+                let s = if &s[0..1] == "{" {
+                    &s[1..s.len() - 1]
+                } else {
+                    &s[0..s.len()]
+                };
+
+                if s.len() > 8 {
+                    Err(input.error(format!(
+                        "Escape sequences can't have more than 8 chars: \"{}\"",
+                        s
+                    )))?
+                }
+
+                // pad with zeroes
+                let s: String = std::iter::repeat('0')
+                    .take(8 - s.len())
+                    .chain(s.chars())
+                    .collect();
+
+                // `s` has length 8, so `bytes` has length 4
+                let bytes: &[u8] = &hex::decode(s).unwrap();
+                let i = u32::from_be_bytes(bytes.try_into().unwrap());
+                let c = char::try_from(i).unwrap();
+                match i {
+                    0xD800..=0xDFFF => {
+                        let c_ecapsed = c.escape_unicode();
+                        Err(input.error(format!("Escape sequences can't contain surrogate pairs: \"{}\"", c_ecapsed)))?
+                    }
+                    0x0FFFE..=0x0FFFF
+                    | 0x1FFFE..=0x1FFFF
+                    | 0x2FFFE..=0x2FFFF
+                    | 0x3FFFE..=0x3FFFF
+                    | 0x4FFFE..=0x4FFFF
+                    | 0x5FFFE..=0x5FFFF
+                    | 0x6FFFE..=0x6FFFF
+                    | 0x7FFFE..=0x7FFFF
+                    | 0x8FFFE..=0x8FFFF
+                    | 0x9FFFE..=0x9FFFF
+                    | 0xAFFFE..=0xAFFFF
+                    | 0xBFFFE..=0xBFFFF
+                    | 0xCFFFE..=0xCFFFF
+                    | 0xDFFFE..=0xDFFFF
+                    | 0xEFFFE..=0xEFFFF
+                    | 0xFFFFE..=0xFFFFF
+                    | 0x10_FFFE..=0x10_FFFF => {
+                        let c_ecapsed = c.escape_unicode();
+                        Err(input.error(format!("Escape sequences can't contain non-characters: \"{}\"", c_ecapsed)))?
                     }
-                    std::iter::once(c).collect()
+                    _ => {}
                 }
+                std::iter::once(c).collect()
             }
-        }
-    );
-    rule!(double_quote_char<&'a str>;
-        captured_str!(s) => s
-    );
-
-    rule!(single_quote_literal<ParsedText>; children!(
-        [single_quote_continue(lines)] => {
-            let newline: ParsedText = "\n".to_string().into();
-
-            let mut lines: Vec<ParsedText> = lines
-                .into_iter()
-                .rev()
-                .map(|l| l.into_iter().rev().collect::<ParsedText>())
-                .collect();
-
-            trim_indent(&mut lines);
-
-            lines
-                .into_iter()
-                .intersperse(newline)
-                .flat_map(InterpolatedText::into_iter)
-                .collect::<ParsedText>()
-        }
-    ));
-    rule!(single_quote_char<&'a str>;
-        captured_str!(s) => s
-    );
-    rule!(escaped_quote_pair<&'a str>;
-        captured_str!(_) => "''"
-    );
-    rule!(escaped_interpolation<&'a str>;
-        captured_str!(_) => "${"
-    );
-    rule!(interpolation<ParsedExpr>; children!(
-        [expression(e)] => e
-    ));
+        })
+    }
+    fn double_quote_char<'a>(
+        input: ParseInput<'a, '_, Rule>,
+    ) -> ParseResult<&'a str> {
+        Ok(input.as_str())
+    }
+
+    fn single_quote_literal(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<ParsedText> {
+        Ok(parse_children!(input;
+            [single_quote_continue(lines)] => {
+                let newline: ParsedText = "\n".to_string().into();
+
+                let mut lines: Vec<ParsedText> = lines
+                    .into_iter()
+                    .rev()
+                    .map(|l| l.into_iter().rev().collect::<ParsedText>())
+                    .collect();
+
+                trim_indent(&mut lines);
+
+                lines
+                    .into_iter()
+                    .intersperse(newline)
+                    .flat_map(InterpolatedText::into_iter)
+                    .collect::<ParsedText>()
+            }
+        ))
+    }
+    fn single_quote_char<'a>(
+        input: ParseInput<'a, '_, Rule>,
+    ) -> ParseResult<&'a str> {
+        Ok(input.as_str())
+    }
+    fn escaped_quote_pair<'a>(
+        _: ParseInput<'a, '_, Rule>,
+    ) -> ParseResult<&'a str> {
+        Ok("''")
+    }
+    fn escaped_interpolation<'a>(
+        _: ParseInput<'a, '_, Rule>,
+    ) -> ParseResult<&'a str> {
+        Ok("${")
+    }
+    fn interpolation(input: ParseInput<Rule>) -> ParseResult<ParsedExpr> {
+        Ok(parse_children!(input;
+            [expression(e)] => e
+        ))
+    }
 
     // Returns a vec of lines in reversed order, where each line is also in reversed order.
-    rule!(single_quote_continue<Vec<Vec<ParsedTextContents>>>; children!(
-        [interpolation(c), single_quote_continue(lines)] => {
-            let c = InterpolatedTextContents::Expr(c);
-            let mut lines = lines;
-            lines.last_mut().unwrap().push(c);
-            lines
-        },
-        [escaped_quote_pair(c), single_quote_continue(lines)] => {
-            let mut lines = lines;
-            // TODO: don't allocate for every char
-            let c = InterpolatedTextContents::Text(c.to_owned());
-            lines.last_mut().unwrap().push(c);
-            lines
-        },
-        [escaped_interpolation(c), single_quote_continue(lines)] => {
-            let mut lines = lines;
-            // TODO: don't allocate for every char
-            let c = InterpolatedTextContents::Text(c.to_owned());
-            lines.last_mut().unwrap().push(c);
-            lines
-        },
-        [single_quote_char(c), single_quote_continue(lines)] => {
-            let mut lines = lines;
-            if c == "\n" || c == "\r\n" {
-                lines.push(vec![]);
-            } else {
+    fn single_quote_continue(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<Vec<Vec<ParsedTextContents>>> {
+        Ok(parse_children!(input;
+            [interpolation(c), single_quote_continue(lines)] => {
+                let c = InterpolatedTextContents::Expr(c);
+                let mut lines = lines;
+                lines.last_mut().unwrap().push(c);
+                lines
+            },
+            [escaped_quote_pair(c), single_quote_continue(lines)] => {
+                let mut lines = lines;
                 // TODO: don't allocate for every char
                 let c = InterpolatedTextContents::Text(c.to_owned());
                 lines.last_mut().unwrap().push(c);
-            }
-            lines
-        },
-        [] => {
-            vec![vec![]]
-        },
-    ));
-
-    rule!(builtin<ParsedExpr>; span;
-        captured_str!(s) => {
-            spanned(span, match crate::Builtin::parse(s) {
+                lines
+            },
+            [escaped_interpolation(c), single_quote_continue(lines)] => {
+                let mut lines = lines;
+                // TODO: don't allocate for every char
+                let c = InterpolatedTextContents::Text(c.to_owned());
+                lines.last_mut().unwrap().push(c);
+                lines
+            },
+            [single_quote_char(c), single_quote_continue(lines)] => {
+                let mut lines = lines;
+                if c == "\n" || c == "\r\n" {
+                    lines.push(vec![]);
+                } else {
+                    // TODO: don't allocate for every char
+                    let c = InterpolatedTextContents::Text(c.to_owned());
+                    lines.last_mut().unwrap().push(c);
+                }
+                lines
+            },
+            [] => {
+                vec![vec![]]
+            },
+        ))
+    }
+
+    fn builtin(input: ParseInput<Rule>) -> ParseResult<ParsedExpr> {
+        let s = input.as_str();
+        let span = input.as_span();
+        Ok(spanned(
+            span,
+            match crate::Builtin::parse(s) {
                 Some(b) => Builtin(b),
-                None => match s {
-                    "True" => BoolLit(true),
-                    "False" => BoolLit(false),
-                    "Type" => Const(crate::Const::Type),
-                    "Kind" => Const(crate::Const::Kind),
-                    "Sort" => Const(crate::Const::Sort),
-                    _ => Err(
-                        format!("Unrecognized builtin: '{}'", s)
-                    )?,
+                None => {
+                    match s {
+                        "True" => BoolLit(true),
+                        "False" => BoolLit(false),
+                        "Type" => Const(crate::Const::Type),
+                        "Kind" => Const(crate::Const::Kind),
+                        "Sort" => Const(crate::Const::Sort),
+                        _ => Err(input
+                            .error(format!("Unrecognized builtin: '{}'", s)))?,
+                    }
                 }
-            })
+            },
+        ))
+    }
+
+    fn NaN(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+    fn minus_infinity_literal(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+    fn plus_infinity_literal(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+
+    fn numeric_double_literal(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<core::Double> {
+        let s = input.as_str().trim();
+        match s.parse::<f64>() {
+            Ok(x) if x.is_infinite() => Err(input.error(format!(
+                "Overflow while parsing double literal '{}'",
+                s
+            ))),
+            Ok(x) => Ok(NaiveDouble::from(x)),
+            Err(e) => Err(input.error(format!("{}", e))),
         }
-    );
-
-    rule!(NaN<()>);
-    rule!(minus_infinity_literal<()>);
-    rule!(plus_infinity_literal<()>);
-
-    rule!(numeric_double_literal<core::Double>;
-        captured_str!(s) => {
-            let s = s.trim();
-            match s.parse::<f64>() {
-                Ok(x) if x.is_infinite() =>
-                    Err(format!("Overflow while parsing double literal '{}'", s))?,
-                Ok(x) => NaiveDouble::from(x),
-                Err(e) => Err(format!("{}", e))?,
+    }
+
+    fn double_literal(input: ParseInput<Rule>) -> ParseResult<core::Double> {
+        Ok(parse_children!(input;
+            [numeric_double_literal(n)] => n,
+            [minus_infinity_literal(_)] => std::f64::NEG_INFINITY.into(),
+            [plus_infinity_literal(_)] => std::f64::INFINITY.into(),
+            [NaN(_)] => std::f64::NAN.into(),
+        ))
+    }
+
+    fn natural_literal(input: ParseInput<Rule>) -> ParseResult<core::Natural> {
+        input
+            .as_str()
+            .trim()
+            .parse()
+            .map_err(|e| input.error(format!("{}", e)))
+    }
+
+    fn integer_literal(input: ParseInput<Rule>) -> ParseResult<core::Integer> {
+        input
+            .as_str()
+            .trim()
+            .parse()
+            .map_err(|e| input.error(format!("{}", e)))
+    }
+
+    fn identifier(input: ParseInput<Rule>) -> ParseResult<ParsedExpr> {
+        let span = input.as_span();
+        Ok(parse_children!(input;
+            [variable(v)] => {
+                spanned(span, Var(v))
+            },
+            [builtin(e)] => e,
+        ))
+    }
+
+    fn variable(input: ParseInput<Rule>) -> ParseResult<V<Label>> {
+        Ok(parse_children!(input;
+            [label(l), natural_literal(idx)] => {
+                V(l, idx)
+            },
+            [label(l)] => {
+                V(l, 0)
+            },
+        ))
+    }
+
+    fn unquoted_path_component<'a>(
+        input: ParseInput<'a, '_, Rule>,
+    ) -> ParseResult<&'a str> {
+        Ok(input.as_str())
+    }
+    fn quoted_path_component<'a>(
+        input: ParseInput<'a, '_, Rule>,
+    ) -> ParseResult<&'a str> {
+        Ok(input.as_str())
+    }
+    fn path_component(input: ParseInput<Rule>) -> ParseResult<String> {
+        Ok(parse_children!(input;
+            [unquoted_path_component(s)] => s.to_string(),
+            [quoted_path_component(s)] => {
+                const RESERVED: &percent_encoding::AsciiSet =
+                    &percent_encoding::CONTROLS
+                    .add(b'=').add(b':').add(b'/').add(b'?')
+                    .add(b'#').add(b'[').add(b']').add(b'@')
+                    .add(b'!').add(b'$').add(b'&').add(b'\'')
+                    .add(b'(').add(b')').add(b'*').add(b'+')
+                    .add(b',').add(b';');
+                s.chars()
+                    .map(|c| {
+                        // Percent-encode ascii chars
+                        if c.is_ascii() {
+                            percent_encoding::utf8_percent_encode(
+                                &c.to_string(),
+                                RESERVED,
+                            ).to_string()
+                        } else {
+                            c.to_string()
+                        }
+                    })
+                    .collect()
+            },
+        ))
+    }
+    fn path(input: ParseInput<Rule>) -> ParseResult<Vec<String>> {
+        Ok(parse_children!(input;
+            [path_component(components)..] => {
+                components.collect()
             }
-        }
-    );
-
-    rule!(double_literal<core::Double>; children!(
-        [numeric_double_literal(n)] => n,
-        [minus_infinity_literal(_)] => std::f64::NEG_INFINITY.into(),
-        [plus_infinity_literal(_)] => std::f64::INFINITY.into(),
-        [NaN(_)] => std::f64::NAN.into(),
-    ));
-
-    rule!(natural_literal<core::Natural>;
-        captured_str!(s) => {
-            s.trim()
-                .parse()
-                .map_err(|e| format!("{}", e))?
-        }
-    );
+        ))
+    }
 
-    rule!(integer_literal<core::Integer>;
-        captured_str!(s) => {
-            s.trim()
-                .parse()
-                .map_err(|e| format!("{}", e))?
-        }
-    );
-
-    rule!(identifier<ParsedExpr>; span; children!(
-        [variable(v)] => {
-            spanned(span, Var(v))
-        },
-        [builtin(e)] => e,
-    ));
-
-    rule!(variable<V<Label>>; children!(
-        [label(l), natural_literal(idx)] => {
-            V(l, idx)
-        },
-        [label(l)] => {
-            V(l, 0)
-        },
-    ));
-
-    rule!(unquoted_path_component<&'a str>; captured_str!(s) => s);
-    rule!(quoted_path_component<&'a str>; captured_str!(s) => s);
-    rule!(path_component<String>; children!(
-        [unquoted_path_component(s)] => s.to_string(),
-        [quoted_path_component(s)] => {
-            const RESERVED: &percent_encoding::AsciiSet =
-                &percent_encoding::CONTROLS
-                .add(b'=').add(b':').add(b'/').add(b'?')
-                .add(b'#').add(b'[').add(b']').add(b'@')
-                .add(b'!').add(b'$').add(b'&').add(b'\'')
-                .add(b'(').add(b')').add(b'*').add(b'+')
-                .add(b',').add(b';');
-            s.chars()
-                .map(|c| {
-                    // Percent-encode ascii chars
-                    if c.is_ascii() {
-                        percent_encoding::utf8_percent_encode(
-                            &c.to_string(),
-                            RESERVED,
-                        ).to_string()
-                    } else {
-                        c.to_string()
-                    }
-                })
-                .collect()
-        },
-    ));
-    rule!(path<Vec<String>>; children!(
-        [path_component(components)..] => {
-            components.collect()
-        }
-    ));
-
-    rule!(local<(FilePrefix, Vec<String>)>; children!(
-        [parent_path(l)] => l,
-        [here_path(l)] => l,
-        [home_path(l)] => l,
-        [absolute_path(l)] => l,
-    ));
-
-    rule!(parent_path<(FilePrefix, Vec<String>)>; children!(
-        [path(p)] => (FilePrefix::Parent, p)
-    ));
-    rule!(here_path<(FilePrefix, Vec<String>)>; children!(
-        [path(p)] => (FilePrefix::Here, p)
-    ));
-    rule!(home_path<(FilePrefix, Vec<String>)>; children!(
-        [path(p)] => (FilePrefix::Home, p)
-    ));
-    rule!(absolute_path<(FilePrefix, Vec<String>)>; children!(
-        [path(p)] => (FilePrefix::Absolute, p)
-    ));
-
-    rule!(scheme<Scheme>; captured_str!(s) => match s {
-        "http" => Scheme::HTTP,
-        "https" => Scheme::HTTPS,
-        _ => unreachable!(),
-    });
-
-    rule!(http_raw<URL<ParsedExpr>>; children!(
-        [scheme(sch), authority(auth), path(p)] => URL {
-            scheme: sch,
-            authority: auth,
-            path: p,
-            query: None,
-            headers: None,
-        },
-        [scheme(sch), authority(auth), path(p), query(q)] => URL {
-            scheme: sch,
-            authority: auth,
-            path: p,
-            query: Some(q),
-            headers: None,
-        },
-    ));
-
-    rule!(authority<String>; captured_str!(s) => s.to_owned());
-
-    rule!(query<String>; captured_str!(s) => s.to_owned());
-
-    rule!(http<URL<ParsedExpr>>; children!(
+    fn local(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<(FilePrefix, Vec<String>)> {
+        Ok(parse_children!(input;
+            [parent_path(l)] => l,
+            [here_path(l)] => l,
+            [home_path(l)] => l,
+            [absolute_path(l)] => l,
+        ))
+    }
+
+    fn parent_path(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<(FilePrefix, Vec<String>)> {
+        Ok(parse_children!(input;
+            [path(p)] => (FilePrefix::Parent, p)
+        ))
+    }
+    fn here_path(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<(FilePrefix, Vec<String>)> {
+        Ok(parse_children!(input;
+            [path(p)] => (FilePrefix::Here, p)
+        ))
+    }
+    fn home_path(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<(FilePrefix, Vec<String>)> {
+        Ok(parse_children!(input;
+            [path(p)] => (FilePrefix::Home, p)
+        ))
+    }
+    fn absolute_path(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<(FilePrefix, Vec<String>)> {
+        Ok(parse_children!(input;
+            [path(p)] => (FilePrefix::Absolute, p)
+        ))
+    }
+
+    fn scheme(input: ParseInput<Rule>) -> ParseResult<Scheme> {
+        Ok(match input.as_str() {
+            "http" => Scheme::HTTP,
+            "https" => Scheme::HTTPS,
+            _ => unreachable!(),
+        })
+    }
+
+    fn http_raw(input: ParseInput<Rule>) -> ParseResult<URL<ParsedExpr>> {
+        Ok(parse_children!(input;
+            [scheme(sch), authority(auth), path(p)] => URL {
+                scheme: sch,
+                authority: auth,
+                path: p,
+                query: None,
+                headers: None,
+            },
+            [scheme(sch), authority(auth), path(p), query(q)] => URL {
+                scheme: sch,
+                authority: auth,
+                path: p,
+                query: Some(q),
+                headers: None,
+            },
+        ))
+    }
+
+    fn authority(input: ParseInput<Rule>) -> ParseResult<String> {
+        Ok(input.as_str().to_owned())
+    }
+
+    fn query(input: ParseInput<Rule>) -> ParseResult<String> {
+        Ok(input.as_str().to_owned())
+    }
+
+    fn http(input: ParseInput<Rule>) -> ParseResult<URL<ParsedExpr>> {
+        Ok(parse_children!(input;
         [http_raw(url)] => url,
         [http_raw(url), import_expression(e)] =>
             URL { headers: Some(e), ..url },
-    ));
-
-    rule!(env<String>; children!(
-        [bash_environment_variable(s)] => s,
-        [posix_environment_variable(s)] => s,
-    ));
-    rule!(bash_environment_variable<String>; captured_str!(s) => s.to_owned());
-    rule!(posix_environment_variable<String>; children!(
-        [posix_environment_variable_character(chars)..] => {
-            chars.collect()
-        },
-    ));
-    rule!(posix_environment_variable_character<Cow<'a, str>>;
-        captured_str!(s) => {
-            match s {
-                "\\\"" => Cow::Owned("\"".to_owned()),
-                "\\\\" => Cow::Owned("\\".to_owned()),
-                "\\a" =>  Cow::Owned("\u{0007}".to_owned()),
-                "\\b" =>  Cow::Owned("\u{0008}".to_owned()),
-                "\\f" =>  Cow::Owned("\u{000C}".to_owned()),
-                "\\n" =>  Cow::Owned("\n".to_owned()),
-                "\\r" =>  Cow::Owned("\r".to_owned()),
-                "\\t" =>  Cow::Owned("\t".to_owned()),
-                "\\v" =>  Cow::Owned("\u{000B}".to_owned()),
-                _ => Cow::Borrowed(s)
-            }
-        }
-    );
-
-    rule!(missing<()>);
-
-    rule!(import_type<ImportLocation<ParsedExpr>>; children!(
-        [missing(_)] => {
-            ImportLocation::Missing
-        },
-        [env(e)] => {
-            ImportLocation::Env(e)
-        },
-        [http(url)] => {
-            ImportLocation::Remote(url)
-        },
-        [local((prefix, p))] => {
-            ImportLocation::Local(prefix, p)
-        },
-    ));
-
-    rule!(hash<Hash>; captured_str!(s) => {
-        let s = s.trim();
+        ))
+    }
+
+    fn env(input: ParseInput<Rule>) -> ParseResult<String> {
+        Ok(parse_children!(input;
+            [bash_environment_variable(s)] => s,
+            [posix_environment_variable(s)] => s,
+        ))
+    }
+    fn bash_environment_variable(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<String> {
+        Ok(input.as_str().to_owned())
+    }
+    fn posix_environment_variable(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<String> {
+        Ok(parse_children!(input;
+            [posix_environment_variable_character(chars)..] => {
+                chars.collect()
+            },
+        ))
+    }
+    fn posix_environment_variable_character<'a>(
+        input: ParseInput<'a, '_, Rule>,
+    ) -> ParseResult<Cow<'a, str>> {
+        Ok(match input.as_str() {
+            "\\\"" => Cow::Owned("\"".to_owned()),
+            "\\\\" => Cow::Owned("\\".to_owned()),
+            "\\a" => Cow::Owned("\u{0007}".to_owned()),
+            "\\b" => Cow::Owned("\u{0008}".to_owned()),
+            "\\f" => Cow::Owned("\u{000C}".to_owned()),
+            "\\n" => Cow::Owned("\n".to_owned()),
+            "\\r" => Cow::Owned("\r".to_owned()),
+            "\\t" => Cow::Owned("\t".to_owned()),
+            "\\v" => Cow::Owned("\u{000B}".to_owned()),
+            s => Cow::Borrowed(s),
+        })
+    }
+
+    fn missing(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+
+    fn import_type(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<ImportLocation<ParsedExpr>> {
+        Ok(parse_children!(input;
+            [missing(_)] => {
+                ImportLocation::Missing
+            },
+            [env(e)] => {
+                ImportLocation::Env(e)
+            },
+            [http(url)] => {
+                ImportLocation::Remote(url)
+            },
+            [local((prefix, p))] => {
+                ImportLocation::Local(prefix, p)
+            },
+        ))
+    }
+
+    fn hash(input: ParseInput<Rule>) -> ParseResult<Hash> {
+        let s = input.as_str().trim();
         let protocol = &s[..6];
         let hash = &s[7..];
         if protocol != "sha256" {
-            Err(format!("Unknown hashing protocol '{}'", protocol))?
+            Err(input.error(format!("Unknown hashing protocol '{}'", protocol)))?
         }
-        Hash::SHA256(hex::decode(hash).unwrap())
-    });
+        Ok(Hash::SHA256(hex::decode(hash).unwrap()))
+    }
 
-    rule!(import_hashed<crate::Import<ParsedExpr>>; children!(
+    fn import_hashed(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<crate::Import<ParsedExpr>> {
+        Ok(parse_children!(input;
         [import_type(location)] =>
             crate::Import {mode: ImportMode::Code, location, hash: None },
         [import_type(location), hash(h)] =>
-            crate::Import {mode: ImportMode::Code, location, hash: Some(h) },
-    ));
-
-    rule!(Text<()>);
-    rule!(Location<()>);
-
-    rule!(import<ParsedExpr>; span; children!(
-        [import_hashed(imp)] => {
-            spanned(span, Import(crate::Import {
-                mode: ImportMode::Code,
-                ..imp
-            }))
-        },
-        [import_hashed(imp), Text(_)] => {
-            spanned(span, Import(crate::Import {
-                mode: ImportMode::RawText,
-                ..imp
-            }))
-        },
-        [import_hashed(imp), Location(_)] => {
-            spanned(span, Import(crate::Import {
-                mode: ImportMode::Location,
-                ..imp
-            }))
-        },
-    ));
-
-    rule!(lambda<()>);
-    rule!(forall<()>);
-    rule!(arrow<()>);
-    rule!(merge<()>);
-    rule!(assert<()>);
-    rule!(if_<()>);
-    rule!(in_<()>);
-    rule!(toMap<()>);
-
-    rule!(empty_list_literal<ParsedExpr>; span; children!(
-        [application_expression(e)] => {
-            spanned(span, EmptyListLit(e))
-        },
-    ));
-
-    rule!(expression<ParsedExpr>; span; children!(
-        [lambda(()), label(l), expression(typ),
-                arrow(()), expression(body)] => {
-            spanned(span, Lam(l, typ, body))
-        },
-        [if_(()), expression(cond), expression(left), expression(right)] => {
-            spanned(span, BoolIf(cond, left, right))
-        },
-        [let_binding(bindings).., in_(()), expression(final_expr)] => {
-            bindings.rev().fold(
-                final_expr,
-                |acc, x| unspanned(Let(x.0, x.1, x.2, acc))
-            )
-        },
-        [forall(()), label(l), expression(typ),
-                arrow(()), expression(body)] => {
-            spanned(span, Pi(l, typ, body))
-        },
-        [operator_expression(typ), arrow(()), expression(body)] => {
-            spanned(span, Pi("_".into(), typ, body))
-        },
-        [merge(()), import_expression(x), import_expression(y),
-                application_expression(z)] => {
-            spanned(span, Merge(x, y, Some(z)))
-        },
-        [empty_list_literal(e)] => e,
-        [assert(()), expression(x)] => {
-            spanned(span, Assert(x))
-        },
-        [toMap(()), import_expression(x), application_expression(y)] => {
-            spanned(span, ToMap(x, Some(y)))
-        },
-        [operator_expression(e)] => e,
-        [operator_expression(e), expression(annot)] => {
-            spanned(span, Annot(e, annot))
-        },
-    ));
-
-    rule!(let_binding<(Label, Option<ParsedExpr>, ParsedExpr)>;
-            children!(
-        [label(name), expression(annot), expression(expr)] =>
-            (name, Some(annot), expr),
-        [label(name), expression(expr)] =>
-            (name, None, expr),
-    ));
-
-    rule!(List<()>);
-    rule!(Optional<()>);
-
-    rule!(operator_expression<ParsedExpr>; prec_climb!(
-        application_expression,
-        {
-            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(),
-            )
-        },
-        (l, op, 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))
-        }
-    ));
-
-    rule!(Some_<()>);
-
-    rule!(application_expression<ParsedExpr>; children!(
-        [first_application_expression(e)] => e,
-        [first_application_expression(first), import_expression(rest)..] => {
-            rest.fold(first, |acc, e| unspanned(App(acc, e)))
-        },
-    ));
-
-    rule!(first_application_expression<ParsedExpr>; span;
-            children!(
-        [Some_(()), import_expression(e)] => {
-            spanned(span, SomeLit(e))
-        },
-        [merge(()), import_expression(x), import_expression(y)] => {
-            spanned(span, Merge(x, y, None))
-        },
-        [toMap(()), import_expression(x)] => {
-            spanned(span, ToMap(x, None))
-        },
-        [import_expression(e)] => e,
-    ));
-
-    rule!(import_expression<ParsedExpr>;
-            children!(
-        [selector_expression(e)] => e,
-        [import(e)] => e,
-    ));
-
-    rule!(selector_expression<ParsedExpr>; children!(
-        [primitive_expression(e)] => e,
-        [primitive_expression(first), selector(rest)..] => {
-            rest.fold(first, |acc, e| unspanned(match e {
-                Either::Left(l) => Field(acc, l),
-                Either::Right(ls) => Projection(acc, ls),
-            }))
-        },
-    ));
-
-    rule!(selector<Either<Label, DupTreeSet<Label>>>; children!(
-        [label(l)] => Either::Left(l),
-        [labels(ls)] => Either::Right(ls),
-        [expression(_e)] => unimplemented!("selection by expression"), // TODO
-    ));
-
-    rule!(labels<DupTreeSet<Label>>; children!(
-        [label(ls)..] => ls.collect(),
-    ));
-
-    rule!(primitive_expression<ParsedExpr>; span; children!(
-        [double_literal(n)] => spanned(span, DoubleLit(n)),
-        [natural_literal(n)] => spanned(span, NaturalLit(n)),
-        [integer_literal(n)] => spanned(span, IntegerLit(n)),
-        [double_quote_literal(s)] => spanned(span, TextLit(s)),
-        [single_quote_literal(s)] => spanned(span, TextLit(s)),
-        [empty_record_type(e)] => e,
-        [empty_record_literal(e)] => e,
-        [non_empty_record_type_or_literal(e)] => e,
-        [union_type(e)] => e,
-        [non_empty_list_literal(e)] => e,
-        [identifier(e)] => e,
-        [expression(e)] => e,
-    ));
-
-    rule!(empty_record_literal<ParsedExpr>; span;
-        captured_str!(_) => spanned(span, RecordLit(Default::default()))
-    );
-
-    rule!(empty_record_type<ParsedExpr>; span;
-        captured_str!(_) => spanned(span, RecordType(Default::default()))
-    );
-
-    rule!(non_empty_record_type_or_literal<ParsedExpr>; span;
-          children!(
-        [label(first_label), non_empty_record_type(rest)] => {
-            let (first_expr, mut map) = rest;
-            map.insert(first_label, first_expr);
-            spanned(span, RecordType(map))
-        },
-        [label(first_label), non_empty_record_literal(rest)] => {
-            let (first_expr, mut map) = rest;
-            map.insert(first_label, first_expr);
-            spanned(span, RecordLit(map))
-        },
-    ));
-
-    rule!(non_empty_record_type
-          <(ParsedExpr, DupTreeMap<Label, ParsedExpr>)>; children!(
-        [expression(expr), record_type_entry(entries)..] => {
-            (expr, entries.collect())
-        }
-    ));
+        crate::Import {mode: ImportMode::Code, location, hash: Some(h) },
+        ))
+    }
 
-    rule!(record_type_entry<(Label, ParsedExpr)>; children!(
-        [label(name), expression(expr)] => (name, expr)
-    ));
+    fn Text(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+    fn Location(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
 
-    rule!(non_empty_record_literal
-          <(ParsedExpr, DupTreeMap<Label, ParsedExpr>)>; children!(
-        [expression(expr), record_literal_entry(entries)..] => {
-            (expr, entries.collect())
-        }
-    ));
-
-    rule!(record_literal_entry<(Label, ParsedExpr)>; children!(
-        [label(name), expression(expr)] => (name, expr)
-    ));
-
-    rule!(union_type<ParsedExpr>; span; children!(
-        [empty_union_type(_)] => {
-            spanned(span, UnionType(Default::default()))
-        },
-        [union_type_entry(entries)..] => {
-            spanned(span, UnionType(entries.collect()))
-        },
-    ));
-
-    rule!(empty_union_type<()>);
-
-    rule!(union_type_entry<(Label, Option<ParsedExpr>)>; children!(
-        [label(name), expression(expr)] => (name, Some(expr)),
-        [label(name)] => (name, None),
-    ));
-
-    rule!(non_empty_list_literal<ParsedExpr>; span;
-          children!(
-        [expression(items)..] => spanned(
-            span,
-            NEListLit(items.collect())
-        )
-    ));
+    fn import(input: ParseInput<Rule>) -> ParseResult<ParsedExpr> {
+        let span = input.as_span();
+        Ok(parse_children!(input;
+            [import_hashed(imp)] => {
+                spanned(span, Import(crate::Import {
+                    mode: ImportMode::Code,
+                    ..imp
+                }))
+            },
+            [import_hashed(imp), Text(_)] => {
+                spanned(span, Import(crate::Import {
+                    mode: ImportMode::RawText,
+                    ..imp
+                }))
+            },
+            [import_hashed(imp), Location(_)] => {
+                spanned(span, Import(crate::Import {
+                    mode: ImportMode::Location,
+                    ..imp
+                }))
+            },
+        ))
+    }
+
+    fn lambda(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+    fn forall(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+    fn arrow(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+    fn merge(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+    fn assert(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+    fn if_(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+    fn in_(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+    fn toMap(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+
+    fn empty_list_literal(input: ParseInput<Rule>) -> ParseResult<ParsedExpr> {
+        let span = input.as_span();
+        Ok(parse_children!(input;
+            [application_expression(e)] => {
+                spanned(span, EmptyListLit(e))
+            },
+        ))
+    }
+
+    fn expression(input: ParseInput<Rule>) -> ParseResult<ParsedExpr> {
+        let span = input.as_span();
+        Ok(parse_children!(input;
+            [lambda(()), label(l), expression(typ),
+                    arrow(()), expression(body)] => {
+                spanned(span, Lam(l, typ, body))
+            },
+            [if_(()), expression(cond), expression(left),
+                    expression(right)] => {
+                spanned(span, BoolIf(cond, left, right))
+            },
+            [let_binding(bindings).., in_(()), expression(final_expr)] => {
+                bindings.rev().fold(
+                    final_expr,
+                    |acc, x| unspanned(Let(x.0, x.1, x.2, acc))
+                )
+            },
+            [forall(()), label(l), expression(typ),
+                    arrow(()), expression(body)] => {
+                spanned(span, Pi(l, typ, body))
+            },
+            [operator_expression(typ), arrow(()), expression(body)] => {
+                spanned(span, Pi("_".into(), typ, body))
+            },
+            [merge(()), import_expression(x), import_expression(y),
+                    application_expression(z)] => {
+                spanned(span, Merge(x, y, Some(z)))
+            },
+            [empty_list_literal(e)] => e,
+            [assert(()), expression(x)] => {
+                spanned(span, Assert(x))
+            },
+            [toMap(()), import_expression(x), application_expression(y)] => {
+                spanned(span, ToMap(x, Some(y)))
+            },
+            [operator_expression(e)] => e,
+            [operator_expression(e), expression(annot)] => {
+                spanned(span, Annot(e, annot))
+            },
+        ))
+    }
+
+    fn let_binding(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<(Label, Option<ParsedExpr>, ParsedExpr)> {
+        Ok(parse_children!(input;
+            [label(name), expression(annot), expression(expr)] =>
+                (name, Some(annot), expr),
+            [label(name), expression(expr)] =>
+                (name, None, expr),
+        ))
+    }
+
+    fn List(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+    fn Optional(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+
+    #[prec_climb(application_expression, make_precclimber())]
+    fn operator_expression(
+        input: ParseInput<Rule>,
+        l: ParsedExpr,
+        op: Pair<Rule>,
+        r: ParsedExpr,
+    ) -> ParseResult<ParsedExpr> {
+        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(input.error(format!("Rule {:?} isn't an operator", r)))?,
+        };
+
+        Ok(unspanned(BinOp(op, l, r)))
+    }
+
+    fn Some_(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+
+    fn application_expression(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<ParsedExpr> {
+        Ok(parse_children!(input;
+            [first_application_expression(e)] => e,
+            [first_application_expression(first),
+                    import_expression(rest)..] => {
+                rest.fold(first, |acc, e| unspanned(App(acc, e)))
+            },
+        ))
+    }
+
+    fn first_application_expression(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<ParsedExpr> {
+        let span = input.as_span();
+        Ok(parse_children!(input;
+            [Some_(()), import_expression(e)] => {
+                spanned(span, SomeLit(e))
+            },
+            [merge(()), import_expression(x), import_expression(y)] => {
+                spanned(span, Merge(x, y, None))
+            },
+            [toMap(()), import_expression(x)] => {
+                spanned(span, ToMap(x, None))
+            },
+            [import_expression(e)] => e,
+        ))
+    }
+
+    fn import_expression(input: ParseInput<Rule>) -> ParseResult<ParsedExpr> {
+        Ok(parse_children!(input;
+            [selector_expression(e)] => e,
+            [import(e)] => e,
+        ))
+    }
+
+    fn selector_expression(input: ParseInput<Rule>) -> ParseResult<ParsedExpr> {
+        Ok(parse_children!(input;
+            [primitive_expression(e)] => e,
+            [primitive_expression(first), selector(rest)..] => {
+                rest.fold(first, |acc, e| unspanned(match e {
+                    Either::Left(l) => Field(acc, l),
+                    Either::Right(ls) => Projection(acc, ls),
+                }))
+            },
+        ))
+    }
+
+    fn selector(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<Either<Label, DupTreeSet<Label>>> {
+        Ok(parse_children!(input;
+            [label(l)] => Either::Left(l),
+            [labels(ls)] => Either::Right(ls),
+            [expression(_e)] => unimplemented!("selection by expression"), // TODO
+        ))
+    }
+
+    fn labels(input: ParseInput<Rule>) -> ParseResult<DupTreeSet<Label>> {
+        Ok(parse_children!(input;
+            [label(ls)..] => ls.collect(),
+        ))
+    }
+
+    fn primitive_expression(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<ParsedExpr> {
+        let span = input.as_span();
+        Ok(parse_children!(input;
+            [double_literal(n)] => spanned(span, DoubleLit(n)),
+            [natural_literal(n)] => spanned(span, NaturalLit(n)),
+            [integer_literal(n)] => spanned(span, IntegerLit(n)),
+            [double_quote_literal(s)] => spanned(span, TextLit(s)),
+            [single_quote_literal(s)] => spanned(span, TextLit(s)),
+            [empty_record_type(e)] => e,
+            [empty_record_literal(e)] => e,
+            [non_empty_record_type_or_literal(e)] => e,
+            [union_type(e)] => e,
+            [non_empty_list_literal(e)] => e,
+            [identifier(e)] => e,
+            [expression(e)] => e,
+        ))
+    }
+
+    fn empty_record_literal(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<ParsedExpr> {
+        let span = input.as_span();
+        Ok(spanned(span, RecordLit(Default::default())))
+    }
 
-    rule!(final_expression<ParsedExpr>; children!(
-        [expression(e), EOI(_)] => e
-    ));
+    fn empty_record_type(input: ParseInput<Rule>) -> ParseResult<ParsedExpr> {
+        let span = input.as_span();
+        Ok(spanned(span, RecordType(Default::default())))
+    }
+
+    fn non_empty_record_type_or_literal(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<ParsedExpr> {
+        let span = input.as_span();
+        Ok(parse_children!(input;
+            [label(first_label), non_empty_record_type(rest)] => {
+                let (first_expr, mut map) = rest;
+                map.insert(first_label, first_expr);
+                spanned(span, RecordType(map))
+            },
+            [label(first_label), non_empty_record_literal(rest)] => {
+                let (first_expr, mut map) = rest;
+                map.insert(first_label, first_expr);
+                spanned(span, RecordLit(map))
+            },
+        ))
+    }
+
+    fn non_empty_record_type(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<(ParsedExpr, DupTreeMap<Label, ParsedExpr>)> {
+        Ok(parse_children!(input;
+            [expression(expr), record_type_entry(entries)..] => {
+                (expr, entries.collect())
+            }
+        ))
+    }
+
+    fn record_type_entry(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<(Label, ParsedExpr)> {
+        Ok(parse_children!(input;
+            [label(name), expression(expr)] => (name, expr)
+        ))
+    }
+
+    fn non_empty_record_literal(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<(ParsedExpr, DupTreeMap<Label, ParsedExpr>)> {
+        Ok(parse_children!(input;
+            [expression(expr), record_literal_entry(entries)..] => {
+                (expr, entries.collect())
+            }
+        ))
+    }
+
+    fn record_literal_entry(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<(Label, ParsedExpr)> {
+        Ok(parse_children!(input;
+            [label(name), expression(expr)] => (name, expr)
+        ))
+    }
+
+    fn union_type(input: ParseInput<Rule>) -> ParseResult<ParsedExpr> {
+        let span = input.as_span();
+        Ok(parse_children!(input;
+            [empty_union_type(_)] => {
+                spanned(span, UnionType(Default::default()))
+            },
+            [union_type_entry(entries)..] => {
+                spanned(span, UnionType(entries.collect()))
+            },
+        ))
+    }
+
+    fn empty_union_type(_: ParseInput<Rule>) -> ParseResult<()> {
+        Ok(())
+    }
+
+    fn union_type_entry(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<(Label, Option<ParsedExpr>)> {
+        Ok(parse_children!(input;
+            [label(name), expression(expr)] => (name, Some(expr)),
+            [label(name)] => (name, None),
+        ))
+    }
+
+    fn non_empty_list_literal(
+        input: ParseInput<Rule>,
+    ) -> ParseResult<ParsedExpr> {
+        let span = input.as_span();
+        Ok(parse_children!(input;
+            [expression(items)..] => spanned(
+                span,
+                NEListLit(items.collect())
+            )
+        ))
+    }
+
+    fn final_expression(input: ParseInput<Rule>) -> ParseResult<ParsedExpr> {
+        Ok(parse_children!(input;
+            [expression(e), EOI(_)] => e
+        ))
+    }
 }
 
 pub fn parse_expr(s: &str) -> ParseResult<ParsedExpr> {
     let mut pairs = DhallParser::parse(Rule::final_expression, s)?;
-    let rc_input = s.to_string().into();
-    let expr = EntryPoint::final_expression(rc_input, pairs.next().unwrap())?;
+    let expr = EntryPoint::final_expression(s, pairs.next().unwrap())?;
     assert_eq!(pairs.next(), None);
     Ok(expr)
 }