Merge remote-tracking branch 'origin/master' into fintan/canonicalize

8 files changed, 727 insertions, 862 deletions

diff --git a/dhall_syntax/src/core/context.rs b/dhall_syntax/src/core/context.rs
index eeec121..6844baa 100644
--- a/dhall_syntax/src/core/context.rs
+++ b/dhall_syntax/src/core/context.rs
@@ -4,7 +4,7 @@ use std::hash::Hash;
 
 /// A `(Context a)` associates `Text` labels with values of type `a`
 ///
-/// The `Context` is used for type-checking when `(a = Expr X)`
+/// The `Context` is used for type-checking when `(a = Expr)`
 ///
 /// * You create a `Context` using `empty` and `insert`
 /// * You transform a `Context` using `fmap`
diff --git a/dhall_syntax/src/core/expr.rs b/dhall_syntax/src/core/expr.rs
index 6522cb1..51b6c47 100644
--- a/dhall_syntax/src/core/expr.rs
+++ b/dhall_syntax/src/core/expr.rs
@@ -8,14 +8,34 @@ pub type Integer = isize;
 pub type Natural = usize;
 pub type Double = NaiveDouble;
 
-/// An empty type
-#[derive(Debug, Copy, Clone, PartialEq, Eq)]
-pub enum X {}
-
-pub fn trivial_result<T>(x: Result<T, X>) -> T {
+pub fn trivial_result<T>(x: Result<T, !>) -> T {
     match x {
         Ok(x) => x,
-        Err(e) => match e {},
+        Err(e) => e,
+    }
+}
+
+/// A location in the source text
+#[derive(Debug, Clone)]
+pub struct Span {
+    input: Rc<str>,
+    /// # Safety
+    ///
+    /// Must be a valid character boundary index into `input`.
+    start: usize,
+    /// # Safety
+    ///
+    /// Must be a valid character boundary index into `input`.
+    end: usize,
+}
+
+impl Span {
+    pub(crate) fn make(input: Rc<str>, sp: pest::Span) -> Self {
+        Span {
+            input,
+            start: sp.start(),
+            end: sp.end(),
+        }
     }
 }
 
@@ -31,6 +51,15 @@ impl PartialEq for NaiveDouble {
 
 impl Eq for NaiveDouble {}
 
+impl std::hash::Hash for NaiveDouble {
+    fn hash<H>(&self, state: &mut H)
+    where
+        H: std::hash::Hasher,
+    {
+        self.0.to_bits().hash(state)
+    }
+}
+
 impl From<f64> for NaiveDouble {
     fn from(x: f64) -> Self {
         NaiveDouble(x)
@@ -44,7 +73,7 @@ impl From<NaiveDouble> for f64 {
 }
 
 /// Constants for a pure type system
-#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub enum Const {
     Type,
     Kind,
@@ -56,7 +85,7 @@ pub enum Const {
 /// The `Label` field is the variable's name (i.e. \"`x`\").
 /// The `Int` field is a DeBruijn index.
 /// See dhall-lang/standard/semantics.md for details
-#[derive(Debug, Clone, PartialEq, Eq)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct V<Label>(pub Label, pub usize);
 
 // This is only for the specific `Label` type, not generic
@@ -73,7 +102,7 @@ impl<'a> From<&'a Label> for V<Label> {
 
 // Definition order must match precedence order for
 // pretty-printing to work correctly
-#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub enum BinOp {
     /// `x ? y`
     ImportAlt,
@@ -104,7 +133,7 @@ pub enum BinOp {
 }
 
 /// Built-ins
-#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub enum Builtin {
     Bool,
     Natural,
@@ -137,29 +166,34 @@ pub enum Builtin {
     TextShow,
 }
 
-pub type ParsedExpr = SubExpr<X, Import>;
-pub type ResolvedExpr = SubExpr<X, X>;
-pub type DhallExpr = ResolvedExpr;
+// Each node carries an annotation.
+#[derive(Debug, Clone)]
+pub struct Expr<Embed>(Box<(RawExpr<Embed>, Option<Span>)>);
 
-// Each node carries an annotation. In practice it's either X (no annotation) or a Span.
-#[derive(Debug)]
-pub struct SubExpr<Note, Embed>(Rc<(Expr<Note, Embed>, Option<Note>)>);
+pub type RawExpr<Embed> = ExprF<Expr<Embed>, Embed>;
 
-impl<Note, Embed: PartialEq> std::cmp::PartialEq for SubExpr<Note, Embed> {
+impl<Embed: PartialEq> std::cmp::PartialEq for Expr<Embed> {
     fn eq(&self, other: &Self) -> bool {
         self.0.as_ref().0 == other.0.as_ref().0
     }
 }
 
-impl<Note, Embed: Eq> std::cmp::Eq for SubExpr<Note, Embed> {}
+impl<Embed: Eq> std::cmp::Eq for Expr<Embed> {}
 
-pub type Expr<Note, Embed> = ExprF<SubExpr<Note, Embed>, Embed>;
+impl<Embed: std::hash::Hash> std::hash::Hash for Expr<Embed> {
+    fn hash<H>(&self, state: &mut H)
+    where
+        H: std::hash::Hasher,
+    {
+        (self.0).0.hash(state)
+    }
+}
 
 /// Syntax tree for expressions
 // Having the recursion out of the enum definition enables writing
 // much more generic code and improves pattern-matching behind
 // smart pointers.
-#[derive(Debug, Clone, PartialEq, Eq)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub enum ExprF<SubExpr, Embed> {
     Const(Const),
     ///  `x`
@@ -209,11 +243,15 @@ pub enum ExprF<SubExpr, Embed> {
     UnionType(DupTreeMap<Label, Option<SubExpr>>),
     ///  `merge x y : t`
     Merge(SubExpr, SubExpr, Option<SubExpr>),
+    ///  `toMap x : t`
+    ToMap(SubExpr, Option<SubExpr>),
     ///  `e.x`
     Field(SubExpr, Label),
     ///  `e.{ x, y, z }`
     Projection(SubExpr, DupTreeSet<Label>),
-    /// Embeds an import or the result of resolving the import
+    /// `./some/path`
+    Import(Import<SubExpr>),
+    /// Embeds the result of resolving an import
     Embed(Embed),
 }
 
@@ -225,229 +263,134 @@ impl<SE, E> ExprF<SE, E> {
         v.visit(self)
     }
 
-    pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, E2, Err>(
+    pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, Err>(
         &'a self,
         visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
         visit_under_binder: impl FnOnce(&'a Label, &'a SE) -> Result<SE2, Err>,
-        visit_embed: impl FnOnce(&'a E) -> Result<E2, Err>,
-    ) -> Result<ExprF<SE2, E2>, Err> {
+    ) -> Result<ExprF<SE2, E>, Err>
+    where
+        E: Clone,
+    {
         self.visit(visitor::TraverseRefWithBindersVisitor {
             visit_subexpr,
             visit_under_binder,
-            visit_embed,
         })
     }
 
-    fn traverse_ref<'a, SE2, E2, Err>(
+    fn traverse_ref<'a, SE2, Err>(
         &'a self,
         visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
-        visit_embed: impl FnOnce(&'a E) -> Result<E2, Err>,
-    ) -> Result<ExprF<SE2, E2>, Err> {
-        self.visit(visitor::TraverseRefVisitor {
-            visit_subexpr,
-            visit_embed,
-        })
+    ) -> Result<ExprF<SE2, E>, Err>
+    where
+        E: Clone,
+    {
+        self.visit(visitor::TraverseRefVisitor { visit_subexpr })
     }
 
-    pub fn map_ref_with_special_handling_of_binders<'a, SE2, E2>(
+    pub fn map_ref_with_special_handling_of_binders<'a, SE2>(
         &'a self,
         mut map_subexpr: impl FnMut(&'a SE) -> SE2,
         mut map_under_binder: impl FnMut(&'a Label, &'a SE) -> SE2,
-        map_embed: impl FnOnce(&'a E) -> E2,
-    ) -> ExprF<SE2, E2> {
+    ) -> ExprF<SE2, E>
+    where
+        E: Clone,
+    {
         trivial_result(self.traverse_ref_with_special_handling_of_binders(
             |x| Ok(map_subexpr(x)),
             |l, x| Ok(map_under_binder(l, x)),
-            |x| Ok(map_embed(x)),
         ))
     }
 
-    pub fn map_ref<'a, SE2, E2>(
+    pub fn map_ref<'a, SE2>(
         &'a self,
         mut map_subexpr: impl FnMut(&'a SE) -> SE2,
-        map_embed: impl FnOnce(&'a E) -> E2,
-    ) -> ExprF<SE2, E2> {
-        trivial_result(
-            self.traverse_ref(|x| Ok(map_subexpr(x)), |x| Ok(map_embed(x))),
-        )
-    }
-
-    pub fn traverse_ref_simple<'a, SE2, Err>(
-        &'a self,
-        visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
-    ) -> Result<ExprF<SE2, E>, Err>
-    where
-        E: Clone,
-    {
-        self.traverse_ref(visit_subexpr, |x| Ok(E::clone(x)))
-    }
-
-    pub fn map_ref_simple<'a, SE2>(
-        &'a self,
-        map_subexpr: impl Fn(&'a SE) -> SE2,
     ) -> ExprF<SE2, E>
     where
         E: Clone,
     {
-        self.map_ref(map_subexpr, E::clone)
+        trivial_result(self.traverse_ref(|x| Ok(map_subexpr(x))))
     }
 }
 
-impl<N, E> Expr<N, E> {
-    fn traverse_embed<E2, Err>(
-        &self,
-        visit_embed: impl FnMut(&E) -> Result<E2, Err>,
-    ) -> Result<Expr<N, E2>, Err>
-    where
-        N: Clone,
-    {
-        self.visit(&mut visitor::TraverseEmbedVisitor(visit_embed))
-    }
-
-    fn map_embed<E2>(&self, mut map_embed: impl FnMut(&E) -> E2) -> Expr<N, E2>
-    where
-        N: Clone,
-    {
-        trivial_result(self.traverse_embed(|x| Ok(map_embed(x))))
-    }
-
+impl<E> RawExpr<E> {
     pub fn traverse_resolve<E2, Err>(
         &self,
-        visit_embed: impl FnMut(&E) -> Result<E2, Err>,
-    ) -> Result<Expr<N, E2>, Err>
-    where
-        N: Clone,
-    {
+        visit_import: impl FnMut(&Import<Expr<E2>>) -> Result<E2, Err>,
+    ) -> Result<RawExpr<E2>, Err> {
         self.traverse_resolve_with_visitor(&mut visitor::ResolveVisitor(
-            visit_embed,
+            visit_import,
         ))
     }
 
     pub(crate) fn traverse_resolve_with_visitor<E2, Err, F1>(
         &self,
         visitor: &mut visitor::ResolveVisitor<F1>,
-    ) -> Result<Expr<N, E2>, Err>
+    ) -> Result<RawExpr<E2>, Err>
     where
-        N: Clone,
-        F1: FnMut(&E) -> Result<E2, Err>,
+        F1: FnMut(&Import<Expr<E2>>) -> Result<E2, Err>,
     {
         match self {
             ExprF::BinOp(BinOp::ImportAlt, l, r) => l
                 .as_ref()
                 .traverse_resolve_with_visitor(visitor)
-                .or(r.as_ref().traverse_resolve_with_visitor(visitor)),
-            _ => self.visit(visitor),
+                .or_else(|_| r.as_ref().traverse_resolve_with_visitor(visitor)),
+            _ => {
+                let e = self.visit(&mut *visitor)?;
+                Ok(match &e {
+                    ExprF::Import(import) => ExprF::Embed((visitor.0)(import)?),
+                    _ => e,
+                })
+            }
         }
     }
 }
 
-impl Expr<X, X> {
-    pub fn absurd<N, E>(&self) -> Expr<N, E> {
-        self.visit(&mut visitor::AbsurdVisitor)
-    }
-}
-
-impl<E: Clone> Expr<X, E> {
-    pub fn note_absurd<N>(&self) -> Expr<N, E> {
-        self.visit(&mut visitor::NoteAbsurdVisitor)
-    }
-}
-
-impl<N, E> SubExpr<N, E> {
-    pub fn as_ref(&self) -> &Expr<N, E> {
+impl<E> Expr<E> {
+    pub fn as_ref(&self) -> &RawExpr<E> {
         &self.0.as_ref().0
     }
 
-    pub fn new(x: Expr<N, E>, n: N) -> Self {
-        SubExpr(Rc::new((x, Some(n))))
+    pub fn new(x: RawExpr<E>, n: Span) -> Self {
+        Expr(Box::new((x, Some(n))))
     }
 
-    pub fn from_expr_no_note(x: Expr<N, E>) -> Self {
-        SubExpr(Rc::new((x, None)))
+    pub fn from_expr_no_span(x: RawExpr<E>) -> Self {
+        Expr(Box::new((x, None)))
     }
 
     pub fn from_builtin(b: Builtin) -> Self {
-        SubExpr::from_expr_no_note(ExprF::Builtin(b))
+        Expr::from_expr_no_span(ExprF::Builtin(b))
     }
 
-    pub fn rewrap<E2>(&self, x: Expr<N, E2>) -> SubExpr<N, E2>
-    where
-        N: Clone,
-    {
-        SubExpr(Rc::new((x, (self.0).1.clone())))
-    }
-
-    pub fn traverse_embed<E2, Err>(
-        &self,
-        visit_embed: impl FnMut(&E) -> Result<E2, Err>,
-    ) -> Result<SubExpr<N, E2>, Err>
-    where
-        N: Clone,
-    {
-        Ok(self.rewrap(self.as_ref().traverse_embed(visit_embed)?))
-    }
-
-    pub fn map_embed<E2>(
-        &self,
-        map_embed: impl FnMut(&E) -> E2,
-    ) -> SubExpr<N, E2>
-    where
-        N: Clone,
-    {
-        self.rewrap(self.as_ref().map_embed(map_embed))
-    }
-
-    pub fn map_subexprs_with_special_handling_of_binders<'a>(
-        &'a self,
-        map_expr: impl FnMut(&'a Self) -> Self,
-        map_under_binder: impl FnMut(&'a Label, &'a Self) -> Self,
-    ) -> Self
-    where
-        N: Clone,
-    {
-        match self.as_ref() {
-            ExprF::Embed(_) => SubExpr::clone(self),
-            // This calls ExprF::map_ref
-            e => self.rewrap(e.map_ref_with_special_handling_of_binders(
-                map_expr,
-                map_under_binder,
-                |_| unreachable!(),
-            )),
-        }
+    pub fn rewrap<E2>(&self, x: RawExpr<E2>) -> Expr<E2> {
+        Expr(Box::new((x, (self.0).1.clone())))
     }
+}
 
+impl<E> Expr<E> {
     pub fn traverse_resolve<E2, Err>(
         &self,
-        visit_embed: impl FnMut(&E) -> Result<E2, Err>,
-    ) -> Result<SubExpr<N, E2>, Err>
-    where
-        N: Clone,
-    {
-        Ok(self.rewrap(self.as_ref().traverse_resolve(visit_embed)?))
-    }
-}
-
-impl SubExpr<X, X> {
-    pub fn absurd<N: Clone, T>(&self) -> SubExpr<N, T> {
-        SubExpr::from_expr_no_note(self.as_ref().absurd())
+        visit_import: impl FnMut(&Import<Expr<E2>>) -> Result<E2, Err>,
+    ) -> Result<Expr<E2>, Err> {
+        Ok(self.rewrap(self.as_ref().traverse_resolve(visit_import)?))
     }
 }
 
-impl<E: Clone> SubExpr<X, E> {
-    pub fn note_absurd<N>(&self) -> SubExpr<N, E> {
-        SubExpr::from_expr_no_note(self.as_ref().note_absurd())
-    }
+// Should probably rename this
+pub fn rc<E>(x: RawExpr<E>) -> Expr<E> {
+    Expr::from_expr_no_span(x)
 }
 
-impl<N, E> Clone for SubExpr<N, E> {
-    fn clone(&self) -> Self {
-        SubExpr(Rc::clone(&self.0))
-    }
+pub(crate) fn spanned(
+    span: Span,
+    x: crate::parser::ParsedRawExpr,
+) -> crate::parser::ParsedExpr {
+    Expr::new(x, span)
 }
-
-// Should probably rename this
-pub fn rc<E>(x: Expr<X, E>) -> SubExpr<X, E> {
-    SubExpr::from_expr_no_note(x)
+pub(crate) fn unspanned(
+    x: crate::parser::ParsedRawExpr,
+) -> crate::parser::ParsedExpr {
+    Expr::from_expr_no_span(x)
 }
 
 /// Add an isize to an usize
diff --git a/dhall_syntax/src/core/import.rs b/dhall_syntax/src/core/import.rs
index 4aad70d..ef696b9 100644
--- a/dhall_syntax/src/core/import.rs
+++ b/dhall_syntax/src/core/import.rs
@@ -16,32 +16,22 @@ pub struct File {
     pub file_path: Vec<String>,
 }
 
-impl IntoIterator for File {
-    type Item = String;
-    type IntoIter = ::std::vec::IntoIter<Self::Item>;
-
-    fn into_iter(self) -> Self::IntoIter {
-        self.file_path.into_iter()
-    }
-}
-
 /// The location of import (i.e. local vs. remote vs. environment)
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub enum ImportLocation {
+pub enum ImportLocation<SubExpr> {
     Local(FilePrefix, File),
-    Remote(URL),
+    Remote(URL<SubExpr>),
     Env(String),
     Missing,
 }
 
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub struct URL {
+pub struct URL<SubExpr> {
     pub scheme: Scheme,
     pub authority: String,
     pub path: File,
     pub query: Option<String>,
-    // TODO: implement inline headers
-    pub headers: Option<Box<ImportHashed>>,
+    pub headers: Option<SubExpr>,
 }
 
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -63,17 +53,56 @@ pub enum Hash {
     SHA256(Vec<u8>),
 }
 
+/// Reference to an external resource
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub struct ImportHashed {
-    pub location: ImportLocation,
+pub struct Import<SubExpr> {
+    pub mode: ImportMode,
+    pub location: ImportLocation<SubExpr>,
     pub hash: Option<Hash>,
 }
 
-/// Reference to an external resource
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub struct Import {
-    pub mode: ImportMode,
-    pub location_hashed: ImportHashed,
+impl<SE> URL<SE> {
+    pub fn visit_subexpr<'a, Err, SE2>(
+        &'a self,
+        f: impl FnOnce(&'a SE) -> Result<SE2, Err>,
+    ) -> Result<URL<SE2>, Err> {
+        let headers = self.headers.as_ref().map(f).transpose()?;
+        Ok(URL {
+            scheme: self.scheme,
+            authority: self.authority.clone(),
+            path: self.path.clone(),
+            query: self.query.clone(),
+            headers,
+        })
+    }
+}
+
+impl<SE> ImportLocation<SE> {
+    pub fn visit_subexpr<'a, Err, SE2>(
+        &'a self,
+        f: impl FnOnce(&'a SE) -> Result<SE2, Err>,
+    ) -> Result<ImportLocation<SE2>, Err> {
+        use ImportLocation::*;
+        Ok(match self {
+            Local(prefix, path) => Local(*prefix, path.clone()),
+            Remote(url) => Remote(url.visit_subexpr(f)?),
+            Env(env) => Env(env.clone()),
+            Missing => Missing,
+        })
+    }
+}
+
+impl<SE> Import<SE> {
+    pub fn visit_subexpr<'a, Err, SE2>(
+        &'a self,
+        f: impl FnOnce(&'a SE) -> Result<SE2, Err>,
+    ) -> Result<Import<SE2>, Err> {
+        Ok(Import {
+            mode: self.mode,
+            location: self.location.visit_subexpr(f)?,
+            hash: self.hash.clone(),
+        })
+    }
 }
 
 pub trait Canonicalize {
@@ -83,7 +112,7 @@ pub trait Canonicalize {
 impl Canonicalize for File {
     fn canonicalize(&self) -> File {
         let mut file_path = Vec::new();
-        let mut file_path_components = self.clone().into_iter();
+        let mut file_path_components = self.file_path.clone().into_iter();
 
         loop {
            let component = file_path_components.next();
@@ -128,8 +157,8 @@ impl Canonicalize for File {
     }
 }
 
-impl Canonicalize for ImportLocation {
-    fn canonicalize(&self) -> ImportLocation {
+impl<SubExpr: Copy> Canonicalize for ImportLocation<SubExpr>  {
+    fn canonicalize(&self) -> ImportLocation<SubExpr> {
         match self {
             ImportLocation::Local(prefix, file) => ImportLocation::Local(*prefix, file.canonicalize()),
             ImportLocation::Remote(url) => ImportLocation::Remote(URL {
@@ -137,22 +166,10 @@ impl Canonicalize for ImportLocation {
                     authority: url.authority.clone(),
                     path: url.path.canonicalize(),
                     query: url.query.clone(),
-                    headers: url.headers.clone().map(|boxed_hash| Box::new(boxed_hash.canonicalize())),
+                    headers: url.headers.clone(),
             }),
             ImportLocation::Env(name) => ImportLocation::Env(name.to_string()),
             ImportLocation::Missing => ImportLocation::Missing,
         }
     }
 }
-
-impl Canonicalize for ImportHashed {
-    fn canonicalize(&self) -> ImportHashed {
-        ImportHashed { hash: self.hash.clone(), location: self.location.canonicalize() }
-    }
-}
-
-impl Canonicalize for Import {
-    fn canonicalize(&self) -> Import {
-        Import { mode: self.mode, location_hashed: self.location_hashed.canonicalize() }
-    }
-}
diff --git a/dhall_syntax/src/core/text.rs b/dhall_syntax/src/core/text.rs
index 0ce1e6f..10fd68a 100644
--- a/dhall_syntax/src/core/text.rs
+++ b/dhall_syntax/src/core/text.rs
@@ -1,6 +1,6 @@
 use std::iter::FromIterator;
 
-#[derive(Debug, Clone, PartialEq, Eq)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct InterpolatedText<SubExpr> {
     head: String,
     tail: Vec<(SubExpr, String)>,
diff --git a/dhall_syntax/src/core/visitor.rs b/dhall_syntax/src/core/visitor.rs
index 18f76d9..435771e 100644
--- a/dhall_syntax/src/core/visitor.rs
+++ b/dhall_syntax/src/core/visitor.rs
@@ -2,52 +2,56 @@ use crate::*;
 use std::iter::FromIterator;
 
 /// A way too generic Visitor trait.
-pub trait GenericVisitor<Input, Return>: Sized {
-    fn visit(self, input: Input) -> Return;
+pub trait GenericVisitor<Input, Output>: Sized {
+    fn visit(self, input: Input) -> Output;
 }
 
-/// A visitor trait that can be used to traverse `ExprF`s. We need this pattern
-/// so that Rust lets us have as much mutability as we can.
-/// For example, `traverse_embed` cannot be made using only `traverse_ref`, because
-/// `traverse_ref` takes a `FnMut` so we would need to pass multiple mutable
-/// reverences to this argument to `traverse_ref`. But Rust's ownership system
-/// is all about preventing exactly this ! So we have to be more clever.
-/// The visitor pattern allows us to have only one mutable thing the whole
-/// time: the visitor itself. The visitor can then carry around multiple closures
-/// or just one, and Rust is ok with either. See for example TraverseRefVisitor
-/// and TraverseEmbedVisitor.
-/// This is very generic. For a more legible trait, see ExprFInFallibleVisitor
-pub trait ExprFVeryGenericVisitor<'a, Ret, SE1, E1>: Sized {
+/// A visitor trait that can be used to traverse `ExprF`s. We need this pattern so that Rust lets
+/// us have as much mutability as we can.
+/// For example, `traverse_ref_with_special_handling_of_binders` cannot be made using only
+/// `traverse_ref`, because `traverse_ref` takes a `FnMut` so we would need to pass multiple
+/// mutable reverences to this argument to `traverse_ref`. But Rust's ownership system is all about
+/// preventing exactly this ! So we have to be more clever. The visitor pattern allows us to have
+/// only one mutable thing the whole time: the visitor itself. The visitor can then carry around
+/// multiple closures or just one, and Rust is ok with either. See for example TraverseRefVisitor.
+pub trait ExprFFallibleVisitor<'a, SE1, SE2, E1, E2>: Sized {
     type Error;
-    type SE2;
-    type E2;
 
-    fn visit_subexpr(
-        &mut self,
-        subexpr: &'a SE1,
-    ) -> Result<Self::SE2, Self::Error>;
+    fn visit_subexpr(&mut self, subexpr: &'a SE1) -> Result<SE2, Self::Error>;
+    fn visit_embed(self, embed: &'a E1) -> Result<E2, Self::Error>;
 
     fn visit_subexpr_under_binder(
-        self,
-        label: &'a Label,
+        mut self,
+        _label: &'a Label,
         subexpr: &'a SE1,
-    ) -> Result<Self::SE2, Self::Error>;
+    ) -> Result<SE2, Self::Error> {
+        self.visit_subexpr(subexpr)
+    }
+}
 
-    fn visit_embed_squash(self, embed: &'a E1) -> Result<Ret, Self::Error>;
+/// Like ExprFFallibleVisitor, but without the error handling.
+pub trait ExprFInFallibleVisitor<'a, SE1, SE2, E1, E2>: Sized {
+    fn visit_subexpr(&mut self, subexpr: &'a SE1) -> SE2;
+    fn visit_embed(self, embed: &'a E1) -> E2;
 
-    // Called with the result of the map, in the non-embed case.
-    // Useful to change the result type, and/or avoid some loss of info
-    fn visit_resulting_exprf(
-        result: ExprF<Self::SE2, Self::E2>,
-    ) -> Result<Ret, Self::Error>;
+    fn visit_subexpr_under_binder(
+        mut self,
+        _label: &'a Label,
+        subexpr: &'a SE1,
+    ) -> SE2 {
+        self.visit_subexpr(subexpr)
+    }
 }
 
-impl<'a, T, Ret, SE1, E1>
-    GenericVisitor<&'a ExprF<SE1, E1>, Result<Ret, T::Error>> for T
+impl<'a, T, SE1, SE2, E1, E2>
+    GenericVisitor<&'a ExprF<SE1, E1>, Result<ExprF<SE2, E2>, T::Error>> for T
 where
-    T: ExprFVeryGenericVisitor<'a, Ret, SE1, E1>,
+    T: ExprFFallibleVisitor<'a, SE1, SE2, E1, E2>,
 {
-    fn visit(self, input: &'a ExprF<SE1, E1>) -> Result<Ret, T::Error> {
+    fn visit(
+        self,
+        input: &'a ExprF<SE1, E1>,
+    ) -> Result<ExprF<SE2, E2>, T::Error> {
         fn vec<'a, T, U, Err, F: FnMut(&'a T) -> Result<U, Err>>(
             x: &'a [T],
             f: F,
@@ -63,27 +67,27 @@ where
                 None => None,
             })
         }
-        fn dupmap<'a, V, Ret, SE, E, T>(
-            x: impl IntoIterator<Item = (&'a Label, &'a SE)>,
+        fn dupmap<'a, V, SE1, SE2, E1, E2, T>(
+            x: impl IntoIterator<Item = (&'a Label, &'a SE1)>,
             mut v: V,
         ) -> Result<T, V::Error>
         where
-            SE: 'a,
-            T: FromIterator<(Label, V::SE2)>,
-            V: ExprFVeryGenericVisitor<'a, Ret, SE, E>,
+            SE1: 'a,
+            T: FromIterator<(Label, SE2)>,
+            V: ExprFFallibleVisitor<'a, SE1, SE2, E1, E2>,
         {
             x.into_iter()
                 .map(|(k, x)| Ok((k.clone(), v.visit_subexpr(x)?)))
                 .collect()
         }
-        fn optdupmap<'a, V, Ret, SE, E, T>(
-            x: impl IntoIterator<Item = (&'a Label, &'a Option<SE>)>,
+        fn optdupmap<'a, V, SE1, SE2, E1, E2, T>(
+            x: impl IntoIterator<Item = (&'a Label, &'a Option<SE1>)>,
             mut v: V,
         ) -> Result<T, V::Error>
         where
-            SE: 'a,
-            T: FromIterator<(Label, Option<V::SE2>)>,
-            V: ExprFVeryGenericVisitor<'a, Ret, SE, E>,
+            SE1: 'a,
+            T: FromIterator<(Label, Option<SE2>)>,
+            V: ExprFFallibleVisitor<'a, SE1, SE2, E1, E2>,
         {
             x.into_iter()
                 .map(|(k, x)| {
@@ -100,7 +104,7 @@ where
 
         let mut v = self;
         use crate::ExprF::*;
-        T::visit_resulting_exprf(match input {
+        Ok(match input {
             Var(v) => Var(v.clone()),
             Lam(l, t, e) => {
                 let t = v.visit_subexpr(t)?;
@@ -146,93 +150,25 @@ where
                 v.visit_subexpr(y)?,
                 opt(t, |e| v.visit_subexpr(e))?,
             ),
+            ToMap(x, t) => {
+                ToMap(v.visit_subexpr(x)?, opt(t, |e| v.visit_subexpr(e))?)
+            }
             Field(e, l) => Field(v.visit_subexpr(e)?, l.clone()),
             Projection(e, ls) => Projection(v.visit_subexpr(e)?, ls.clone()),
             Assert(e) => Assert(v.visit_subexpr(e)?),
-            Embed(a) => return v.visit_embed_squash(a),
+            Import(i) => Import(i.visit_subexpr(|e| v.visit_subexpr(e))?),
+            Embed(a) => Embed(v.visit_embed(a)?),
         })
     }
 }
 
-/// Like ExprFVeryGenericVisitor, but sets the return
-/// type to ExprF<_>
-pub trait ExprFFallibleVisitor<'a, SE1, SE2, E1, E2>: Sized {
-    type Error;
-
-    fn visit_subexpr(&mut self, subexpr: &'a SE1) -> Result<SE2, Self::Error>;
-    fn visit_embed(self, embed: &'a E1) -> Result<E2, Self::Error>;
-
-    fn visit_subexpr_under_binder(
-        mut self,
-        _label: &'a Label,
-        subexpr: &'a SE1,
-    ) -> Result<SE2, Self::Error> {
-        self.visit_subexpr(subexpr)
-    }
-
-    fn visit_embed_squash(
-        self,
-        embed: &'a E1,
-    ) -> Result<ExprF<SE2, E2>, Self::Error> {
-        Ok(ExprF::Embed(self.visit_embed(embed)?))
-    }
-}
-
-impl<'a, T, SE1, SE2, E1, E2>
-    ExprFVeryGenericVisitor<'a, ExprF<SE2, E2>, SE1, E1> for T
+impl<'a, T, SE1, SE2, E1, E2> GenericVisitor<&'a ExprF<SE1, E1>, ExprF<SE2, E2>>
+    for T
 where
-    T: ExprFFallibleVisitor<'a, SE1, SE2, E1, E2>,
+    T: ExprFInFallibleVisitor<'a, SE1, SE2, E1, E2>,
 {
-    type Error = T::Error;
-    type SE2 = SE2;
-    type E2 = E2;
-
-    fn visit_subexpr(
-        &mut self,
-        subexpr: &'a SE1,
-    ) -> Result<Self::SE2, Self::Error> {
-        self.visit_subexpr(subexpr)
-    }
-
-    fn visit_subexpr_under_binder(
-        self,
-        label: &'a Label,
-        subexpr: &'a SE1,
-    ) -> Result<Self::SE2, Self::Error> {
-        self.visit_subexpr_under_binder(label, subexpr)
-    }
-
-    fn visit_embed_squash(
-        self,
-        embed: &'a E1,
-    ) -> Result<ExprF<SE2, E2>, Self::Error> {
-        self.visit_embed_squash(embed)
-    }
-
-    // Called with the result of the map, in the non-embed case.
-    // Useful to change the result type, and/or avoid some loss of info
-    fn visit_resulting_exprf(
-        result: ExprF<Self::SE2, Self::E2>,
-    ) -> Result<ExprF<SE2, E2>, Self::Error> {
-        Ok(result)
-    }
-}
-
-/// Like ExprFFallibleVisitor, but without the error handling.
-pub trait ExprFInFallibleVisitor<'a, SE1, SE2, E1, E2>: Sized {
-    fn visit_subexpr(&mut self, subexpr: &'a SE1) -> SE2;
-    fn visit_embed(self, embed: &'a E1) -> E2;
-
-    fn visit_subexpr_under_binder(
-        mut self,
-        _label: &'a Label,
-        subexpr: &'a SE1,
-    ) -> SE2 {
-        self.visit_subexpr(subexpr)
-    }
-
-    fn visit_embed_squash(self, embed: &'a E1) -> ExprF<SE2, E2> {
-        ExprF::Embed(self.visit_embed(embed))
+    fn visit(self, input: &'a ExprF<SE1, E1>) -> ExprF<SE2, E2> {
+        trivial_result(InfallibleWrapper(self).visit(input))
     }
 }
 
@@ -243,7 +179,7 @@ impl<'a, T, SE1, SE2, E1, E2> ExprFFallibleVisitor<'a, SE1, SE2, E1, E2>
 where
     T: ExprFInFallibleVisitor<'a, SE1, SE2, E1, E2>,
 {
-    type Error = X;
+    type Error = !;
 
     fn visit_subexpr(&mut self, subexpr: &'a SE1) -> Result<SE2, Self::Error> {
         Ok(self.0.visit_subexpr(subexpr))
@@ -259,40 +195,20 @@ where
     ) -> Result<SE2, Self::Error> {
         Ok(self.0.visit_subexpr_under_binder(label, subexpr))
     }
-
-    fn visit_embed_squash(
-        self,
-        embed: &'a E1,
-    ) -> Result<ExprF<SE2, E2>, Self::Error> {
-        Ok(self.0.visit_embed_squash(embed))
-    }
 }
 
-impl<'a, T, SE1, SE2, E1, E2> GenericVisitor<&'a ExprF<SE1, E1>, ExprF<SE2, E2>>
-    for T
-where
-    T: ExprFInFallibleVisitor<'a, SE1, SE2, E1, E2>,
-{
-    fn visit(self, input: &'a ExprF<SE1, E1>) -> ExprF<SE2, E2> {
-        trivial_result(InfallibleWrapper(self).visit(input))
-    }
-}
-
-pub struct TraverseRefWithBindersVisitor<F1, F2, F4> {
+pub struct TraverseRefWithBindersVisitor<F1, F2> {
     pub visit_subexpr: F1,
     pub visit_under_binder: F2,
-    pub visit_embed: F4,
 }
 
-impl<'a, SE, E, SE2, E2, Err, F1, F2, F4>
-    ExprFFallibleVisitor<'a, SE, SE2, E, E2>
-    for TraverseRefWithBindersVisitor<F1, F2, F4>
+impl<'a, SE, E, SE2, Err, F1, F2> ExprFFallibleVisitor<'a, SE, SE2, E, E>
+    for TraverseRefWithBindersVisitor<F1, F2>
 where
     SE: 'a,
-    E: 'a,
+    E: 'a + Clone,
     F1: FnMut(&'a SE) -> Result<SE2, Err>,
     F2: FnOnce(&'a Label, &'a SE) -> Result<SE2, Err>,
-    F4: FnOnce(&'a E) -> Result<E2, Err>,
 {
     type Error = Err;
 
@@ -306,107 +222,52 @@ where
     ) -> Result<SE2, Self::Error> {
         (self.visit_under_binder)(label, subexpr)
     }
-    fn visit_embed(self, embed: &'a E) -> Result<E2, Self::Error> {
-        (self.visit_embed)(embed)
+    fn visit_embed(self, embed: &'a E) -> Result<E, Self::Error> {
+        Ok(embed.clone())
     }
 }
 
-pub struct TraverseRefVisitor<F1, F3> {
+pub struct TraverseRefVisitor<F1> {
     pub visit_subexpr: F1,
-    pub visit_embed: F3,
 }
 
-impl<'a, SE, E, SE2, E2, Err, F1, F3> ExprFFallibleVisitor<'a, SE, SE2, E, E2>
-    for TraverseRefVisitor<F1, F3>
+impl<'a, SE, E, SE2, Err, F1> ExprFFallibleVisitor<'a, SE, SE2, E, E>
+    for TraverseRefVisitor<F1>
 where
     SE: 'a,
-    E: 'a,
+    E: 'a + Clone,
     F1: FnMut(&'a SE) -> Result<SE2, Err>,
-    F3: FnOnce(&'a E) -> Result<E2, Err>,
 {
     type Error = Err;
 
     fn visit_subexpr(&mut self, subexpr: &'a SE) -> Result<SE2, Self::Error> {
         (self.visit_subexpr)(subexpr)
     }
-    fn visit_embed(self, embed: &'a E) -> Result<E2, Self::Error> {
-        (self.visit_embed)(embed)
-    }
-}
-
-pub struct TraverseEmbedVisitor<F1>(pub F1);
-
-impl<'a, 'b, N, E, E2, Err, F1>
-    ExprFFallibleVisitor<'a, SubExpr<N, E>, SubExpr<N, E2>, E, E2>
-    for &'b mut TraverseEmbedVisitor<F1>
-where
-    N: Clone + 'a,
-    F1: FnMut(&E) -> Result<E2, Err>,
-{
-    type Error = Err;
-
-    fn visit_subexpr(
-        &mut self,
-        subexpr: &'a SubExpr<N, E>,
-    ) -> Result<SubExpr<N, E2>, Self::Error> {
-        Ok(subexpr.rewrap(subexpr.as_ref().visit(&mut **self)?))
-    }
-    fn visit_embed(self, embed: &'a E) -> Result<E2, Self::Error> {
-        (self.0)(embed)
+    fn visit_embed(self, embed: &'a E) -> Result<E, Self::Error> {
+        Ok(embed.clone())
     }
 }
 
 pub struct ResolveVisitor<F1>(pub F1);
 
-impl<'a, 'b, N, E, E2, Err, F1>
-    ExprFFallibleVisitor<'a, SubExpr<N, E>, SubExpr<N, E2>, E, E2>
+impl<'a, 'b, E, E2, Err, F1> ExprFFallibleVisitor<'a, Expr<E>, Expr<E2>, E, E2>
     for &'b mut ResolveVisitor<F1>
 where
-    N: Clone + 'a,
-    F1: FnMut(&E) -> Result<E2, Err>,
+    F1: FnMut(&Import<Expr<E2>>) -> Result<E2, Err>,
 {
     type Error = Err;
 
     fn visit_subexpr(
         &mut self,
-        subexpr: &'a SubExpr<N, E>,
-    ) -> Result<SubExpr<N, E2>, Self::Error> {
+        subexpr: &'a Expr<E>,
+    ) -> Result<Expr<E2>, Self::Error> {
         Ok(subexpr.rewrap(
             subexpr
                 .as_ref()
                 .traverse_resolve_with_visitor(&mut **self)?,
         ))
     }
-    fn visit_embed(self, embed: &'a E) -> Result<E2, Self::Error> {
-        (self.0)(embed)
-    }
-}
-pub struct NoteAbsurdVisitor;
-
-impl<'a, 'b, N, E>
-    ExprFInFallibleVisitor<'a, SubExpr<X, E>, SubExpr<N, E>, E, E>
-    for &'b mut NoteAbsurdVisitor
-where
-    E: Clone + 'a,
-{
-    fn visit_subexpr(&mut self, subexpr: &'a SubExpr<X, E>) -> SubExpr<N, E> {
-        SubExpr::from_expr_no_note(subexpr.as_ref().visit(&mut **self))
-    }
-    fn visit_embed(self, embed: &'a E) -> E {
-        E::clone(embed)
-    }
-}
-
-pub struct AbsurdVisitor;
-
-impl<'a, 'b, N, E>
-    ExprFInFallibleVisitor<'a, SubExpr<X, X>, SubExpr<N, E>, X, E>
-    for &'b mut AbsurdVisitor
-{
-    fn visit_subexpr(&mut self, subexpr: &'a SubExpr<X, X>) -> SubExpr<N, E> {
-        SubExpr::from_expr_no_note(subexpr.as_ref().visit(&mut **self))
-    }
-    fn visit_embed(self, embed: &'a X) -> E {
-        match *embed {}
+    fn visit_embed(self, _embed: &'a E) -> Result<E2, Self::Error> {
+        unimplemented!()
     }
 }
diff --git a/dhall_syntax/src/lib.rs b/dhall_syntax/src/lib.rs
index 193c6ea..e4a6077 100644
--- a/dhall_syntax/src/lib.rs
+++ b/dhall_syntax/src/lib.rs
@@ -1,5 +1,8 @@
 #![feature(trace_macros)]
 #![feature(slice_patterns)]
+#![feature(try_blocks)]
+#![feature(never_type)]
+#![feature(bind_by_move_pattern_guards)]
 #![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 71d0936..b70a236 100644
--- a/dhall_syntax/src/parser.rs
+++ b/dhall_syntax/src/parser.rs
@@ -1,7 +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};
@@ -15,46 +18,15 @@ use crate::*;
 // their own crate because they are quite general and useful. For now they
 // are here and hopefully you can figure out how they work.
 
-type ParsedExpr = Expr<Span, Import>;
-type ParsedSubExpr = SubExpr<Span, Import>;
-type ParsedText = InterpolatedText<SubExpr<Span, Import>>;
-type ParsedTextContents = InterpolatedTextContents<SubExpr<Span, Import>>;
+pub(crate) type ParsedRawExpr = RawExpr<!>;
+pub(crate) type ParsedExpr = Expr<!>;
+type ParsedText = InterpolatedText<ParsedExpr>;
+type ParsedTextContents = InterpolatedTextContents<ParsedExpr>;
 
 pub type ParseError = pest::error::Error<Rule>;
 
 pub type ParseResult<T> = Result<T, ParseError>;
 
-fn unspanned(x: ParsedExpr) -> ParsedSubExpr {
-    SubExpr::from_expr_no_note(x)
-}
-
-#[derive(Debug, Clone)]
-pub struct Span {
-    input: Rc<str>,
-    /// # Safety
-    ///
-    /// Must be a valid character boundary index into `input`.
-    start: usize,
-    /// # Safety
-    ///
-    /// Must be a valid character boundary index into `input`.
-    end: usize,
-}
-
-impl Span {
-    fn make(input: Rc<str>, sp: pest::Span) -> Self {
-        Span {
-            input,
-            start: sp.start(),
-            end: sp.end(),
-        }
-    }
-}
-
-fn spanned(span: Span, x: ParsedExpr) -> ParsedSubExpr {
-    SubExpr::new(x, span)
-}
-
 #[derive(Debug)]
 enum Either<A, B> {
     Left(A),
@@ -147,177 +119,271 @@ fn debug_pair(pair: Pair<Rule>) -> String {
     s
 }
 
-macro_rules! make_parser {
-    (@pattern, rule, $name:ident) => (Rule::$name);
-    (@pattern, token_rule, $name:ident) => (Rule::$name);
-    (@pattern, rule_group, $name:ident) => (_);
-    (@filter, rule) => (true);
-    (@filter, token_rule) => (true);
-    (@filter, rule_group) => (false);
+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)*)
+    };
 
-    (@body,
-        ($($things:tt)*),
-        rule!( $name:ident<$o:ty>; $($args:tt)* )
+    // 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
+    };
+
+    ($parse_args:expr, $iter:expr; [$($args:tt)*] => $body:expr) => {
+        parse_children!(@match_forwards,
+            $parse_args, $iter,
+            ($body),
+            $($args)*,
+        )
+    };
+}
+
+macro_rules! make_parser {
+    (@children_pattern,
+        $varpat:ident,
+        ($($acc:tt)*),
+        [$variant:ident ($x:pat), $($rest:tt)*]
     ) => (
-        make_parser!(@body,
-            ($($things)*),
-            rule!( $name<$o> as $name; $($args)* )
+        make_parser!(@children_pattern,
+            $varpat,
+            ($($acc)* , Rule::$variant),
+            [$($rest)*]
+        )
+    );
+    (@children_pattern,
+        $varpat:ident,
+        ($($acc:tt)*),
+        [$variant:ident ($x:ident).., $($rest:tt)*]
+    ) => (
+        make_parser!(@children_pattern,
+            $varpat,
+            ($($acc)* , $varpat..),
+            [$($rest)*]
         )
     );
+    (@children_pattern,
+        $varpat:ident,
+        (, $($acc:tt)*), [$(,)*]
+    ) => ([$($acc)*]);
+    (@children_pattern,
+        $varpat:ident,
+        ($($acc:tt)*), [$(,)*]
+    ) => ([$($acc)*]);
+
+    (@children_filter,
+        $varpat:ident,
+        [$variant:ident ($x:pat), $($rest:tt)*]
+    ) => (
+        make_parser!(@children_filter, $varpat, [$($rest)*])
+    );
+    (@children_filter,
+        $varpat:ident,
+        [$variant:ident ($x:ident).., $($rest:tt)*]
+    ) => (
+        $varpat.iter().all(|r| r == &Rule::$variant) &&
+        make_parser!(@children_filter, $varpat, [$($rest)*])
+    );
+    (@children_filter, $varpat:ident, [$(,)*]) => (true);
+
     (@body,
-        ($_input:expr, $pair:expr, $_children:expr),
+        ($climbers:expr, $input:expr, $pair:expr),
         rule!(
-            $name:ident<$o:ty>
-            as $group:ident;
+            $name:ident<$o:ty>;
+            $span:ident;
             captured_str!($x:pat) => $body:expr
         )
     ) => ({
+        let $span = Span::make($input.clone(), $pair.as_span());
         let $x = $pair.as_str();
-        let res: $o = $body;
-        Ok(ParsedValue::$group(res))
+        let res: Result<_, String> = try { $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;
+            $name:ident<$o:ty>;
+            $span:ident;
             children!( $( [$($args:tt)*] => $body:expr ),* $(,)* )
         )
     ) => ({
-        #[allow(unused_imports)]
-        use ParsedValue::*;
+        let children_rules: Vec<Rule> = $pair
+            .clone()
+            .into_inner()
+            .map(|p| p.as_rule())
+            .collect();
+
+        let $span = Span::make($input.clone(), $pair.as_span());
+        #[allow(unused_mut)]
+        let mut iter = $pair.clone().into_inner();
+
         #[allow(unreachable_code)]
-        let res: $o = improved_slice_patterns::match_vec!($children;
-            $( [$($args)*] => $body, )*
-            [x..] => Err(
-                format!("Unexpected children: {:?}", x.collect::<Vec<_>>())
-            )?,
-        ).map_err(|_| -> String { unreachable!() })?;
-        Ok(ParsedValue::$group(res))
+        match children_rules.as_slice() {
+            $(
+                make_parser!(@children_pattern, x, (), [$($args)*,])
+                if make_parser!(@children_filter, x, [$($args)*,])
+                => {
+                    parse_children!(($climbers, $input.clone()), iter;
+                        [$($args)*] => {
+                            let res: Result<_, String> = try { $body };
+                            res.map_err(|msg| custom_parse_error(&$pair, msg))
+                        }
+                    )
+                }
+                ,
+            )*
+            [..] => Err(custom_parse_error(
+                &$pair,
+                format!("Unexpected children: {:?}", children_rules)
+            )),
+        }
     });
     (@body,
-        ($input:expr, $pair:expr, $children:expr),
+        ($climbers:expr, $input:expr, $pair:expr),
         rule!(
-            $name:ident<$o:ty>
-            as $group:ident;
-            $span:ident;
+            $name:ident<$o:ty>;
+            prec_climb!(
+                $other_rule:ident,
+                $_climber:expr,
+                $args:pat => $body:expr $(,)*
+            )
+        )
+    ) => ({
+        let climber = $climbers.get(&Rule::$name).unwrap();
+        climber.climb(
+            $pair.clone().into_inner(),
+            |p| Parsers::$other_rule(($climbers, $input.clone()), p),
+            |l, op, r| {
+                let $args = (l?, op, r?);
+                let res: Result<_, String> = try { $body };
+                res.map_err(|msg| custom_parse_error(&$pair, msg))
+            },
+        )
+    });
+    (@body,
+        ($($things:tt)*),
+        rule!(
+            $name:ident<$o:ty>;
             $($args:tt)*
         )
     ) => ({
-        let $span = Span::make($input, $pair.as_span());
         make_parser!(@body,
-            ($input, $pair, $children),
+            ($($things)*),
             rule!(
-                $name<$o>
-                as $group;
+                $name<$o>;
+                _span;
                 $($args)*
             )
         )
     });
     (@body,
         ($($things:tt)*),
-        token_rule!($name:ident<$o:ty>)
+        rule!($name:ident<$o:ty>)
     ) => ({
-        Ok(ParsedValue::$name(()))
+        Ok(())
     });
-    (@body, ($($things:tt)*), rule_group!( $name:ident<$o:ty> )) => (
-        unreachable!()
-    );
+
+    (@construct_climber,
+        ($map:expr),
+        rule!(
+            $name:ident<$o:ty>;
+            prec_climb!($other_rule:ident, $climber:expr, $($_rest:tt)* )
+        )
+    ) => ({
+        $map.insert(Rule::$name, $climber)
+    });
+    (@construct_climber, ($($things:tt)*), $($args:tt)*) => (());
 
     ($( $submac:ident!( $name:ident<$o:ty> $($args:tt)* ); )*) => (
-        #[allow(non_camel_case_types, dead_code, clippy::large_enum_variant)]
-        #[derive(Debug)]
-        enum ParsedValue<'a> {
-            $( $name($o), )*
+        struct Parsers;
+
+        impl Parsers {
+            $(
+            #[allow(non_snake_case, unused_variables, clippy::let_unit_value)]
+            fn $name<'a>(
+                (climbers, input): (&HashMap<Rule, PrecClimber<Rule>>, Rc<str>),
+                pair: Pair<'a, Rule>,
+            ) -> ParseResult<$o> {
+                make_parser!(@body, (climbers, input, pair),
+                               $submac!( $name<$o> $($args)* ))
+            }
+            )*
         }
 
-        fn parse_any<'a>(
-            input: Rc<str>,
-            pair: Pair<'a, Rule>,
-            children: Vec<ParsedValue<'a>>,
-        ) -> Result<ParsedValue<'a>, String> {
-            match pair.as_rule() {
-                $(
-                    make_parser!(@pattern, $submac, $name)
-                    if make_parser!(@filter, $submac)
-                    => make_parser!(@body, (input, pair, children),
-                                           $submac!( $name<$o> $($args)* ))
-                    ,
-                )*
-                r => Err(format!("Unexpected {:?}", r)),
-            }
+        fn construct_precclimbers() -> HashMap<Rule, PrecClimber<Rule>> {
+            let mut map = HashMap::new();
+            $(
+                make_parser!(@construct_climber, (map),
+                        $submac!( $name<$o> $($args)* ));
+            )*
+            map
         }
-    );
-}
 
-// Non-recursive implementation to avoid stack overflows
-fn do_parse<'a>(
-    input: Rc<str>,
-    initial_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![];
-    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;
-                } else {
-                    pairs_stack.push(Processed(pair, n_children));
-                    pairs_stack
-                        .extend(pairs.into_iter().map(StackFrame::Unprocessed));
-                    break;
-                }
-            },
-            Processed(pair, n) => {
-                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))?,
-                };
-                values_stack.push(val);
+        struct EntryPoint;
+
+        impl EntryPoint {
+            $(
+            #[allow(non_snake_case, dead_code)]
+            fn $name<'a>(
+                input: Rc<str>,
+                pair: Pair<'a, Rule>,
+            ) -> ParseResult<$o> {
+                let climbers = construct_precclimbers();
+                Parsers::$name((&climbers, input), pair)
             }
+            )*
         }
-    }
-    Ok(values_stack.pop().unwrap())
-}
-
-// List of rules that can be shortcutted if they have a single child
-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
-        | application_expression
-        | first_application_expression
-        | selector_expression
-        | annotated_expression => true,
-        _ => false,
-    }
+    );
 }
 
 // Trim the shared indent off of a vec of lines, as defined by the Dhall semantics of multiline
@@ -362,7 +428,7 @@ fn trim_indent(lines: &mut Vec<ParsedText>) {
 }
 
 make_parser! {
-    token_rule!(EOI<()>);
+    rule!(EOI<()>);
 
     rule!(simple_label<Label>;
         captured_str!(s) => Label::from(s.trim().to_owned())
@@ -442,7 +508,7 @@ make_parser! {
                         0xAFFFE..=0xAFFFF | 0xBFFFE..=0xBFFFF |
                         0xCFFFE..=0xCFFFF | 0xDFFFE..=0xDFFFF |
                         0xEFFFE..=0xEFFFF | 0xFFFFE..=0xFFFFF |
-                        0x10FFFE..=0x10FFFF => {
+                        0x10_FFFE..=0x10_FFFF => {
                             let c_ecapsed = c.escape_unicode();
                             Err(format!("Escape sequences can't contain non-characters: \"{}\"", c_ecapsed))?
                         },
@@ -479,13 +545,13 @@ make_parser! {
     rule!(single_quote_char<&'a str>;
         captured_str!(s) => s
     );
-    rule!(escaped_quote_pair<&'a str> as single_quote_char;
+    rule!(escaped_quote_pair<&'a str>;
         captured_str!(_) => "''"
     );
-    rule!(escaped_interpolation<&'a str> as single_quote_char;
+    rule!(escaped_interpolation<&'a str>;
         captured_str!(_) => "${"
     );
-    rule!(interpolation<ParsedSubExpr>; children!(
+    rule!(interpolation<ParsedExpr>; children!(
         [expression(e)] => e
     ));
 
@@ -497,21 +563,29 @@ make_parser! {
             lines.last_mut().unwrap().push(c);
             lines
         },
-        [single_quote_char("\n"), single_quote_continue(lines)] => {
+        [escaped_quote_pair(c), single_quote_continue(lines)] => {
             let mut lines = lines;
-            lines.push(vec![]);
+            // TODO: don't allocate for every char
+            let c = InterpolatedTextContents::Text(c.to_owned());
+            lines.last_mut().unwrap().push(c);
             lines
         },
-        [single_quote_char("\r\n"), single_quote_continue(lines)] => {
+        [escaped_interpolation(c), single_quote_continue(lines)] => {
             let mut lines = lines;
-            lines.push(vec![]);
+            // 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)] => {
-            // TODO: don't allocate for every char
-            let c = InterpolatedTextContents::Text(c.to_owned());
             let mut lines = lines;
-            lines.last_mut().unwrap().push(c);
+            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
         },
         [] => {
@@ -519,7 +593,7 @@ make_parser! {
         },
     ));
 
-    rule!(builtin<ParsedSubExpr>; span;
+    rule!(builtin<ParsedExpr>; span;
         captured_str!(s) => {
             spanned(span, match crate::Builtin::parse(s) {
                 Some(b) => Builtin(b),
@@ -537,9 +611,9 @@ make_parser! {
         }
     );
 
-    token_rule!(NaN<()>);
-    token_rule!(minus_infinity_literal<()>);
-    token_rule!(plus_infinity_literal<()>);
+    rule!(NaN<()>);
+    rule!(minus_infinity_literal<()>);
+    rule!(plus_infinity_literal<()>);
 
     rule!(numeric_double_literal<core::Double>;
         captured_str!(s) => {
@@ -576,7 +650,7 @@ make_parser! {
         }
     );
 
-    rule!(identifier<ParsedSubExpr> as expression; span; children!(
+    rule!(identifier<ParsedExpr>; span; children!(
         [variable(v)] => {
             spanned(span, Var(v))
         },
@@ -595,12 +669,29 @@ make_parser! {
     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)] => {
-            percent_encoding::percent_decode(s.as_bytes())
-                .decode_utf8_lossy()
-                .into_owned()
+        [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()
         },
-        [quoted_path_component(s)] => s.to_string(),
     ));
     rule!(path<Vec<String>>; children!(
         [path_component(components)..] => {
@@ -608,18 +699,23 @@ make_parser! {
         }
     ));
 
-    rule_group!(local<(FilePrefix, Vec<String>)>);
+    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>)> as local; children!(
+    rule!(parent_path<(FilePrefix, Vec<String>)>; children!(
         [path(p)] => (FilePrefix::Parent, p)
     ));
-    rule!(here_path<(FilePrefix, Vec<String>)> as local; children!(
+    rule!(here_path<(FilePrefix, Vec<String>)>; children!(
         [path(p)] => (FilePrefix::Here, p)
     ));
-    rule!(home_path<(FilePrefix, Vec<String>)> as local; children!(
+    rule!(home_path<(FilePrefix, Vec<String>)>; children!(
         [path(p)] => (FilePrefix::Home, p)
     ));
-    rule!(absolute_path<(FilePrefix, Vec<String>)> as local; children!(
+    rule!(absolute_path<(FilePrefix, Vec<String>)>; children!(
         [path(p)] => (FilePrefix::Absolute, p)
     ));
 
@@ -629,15 +725,13 @@ make_parser! {
         _ => unreachable!(),
     });
 
-    rule!(http_raw<URL>; children!(
-        [scheme(sch), authority(auth), path(file_path)] => {
-            URL {
-                scheme: sch,
-                authority: auth,
-                path: File { file_path },
-                query: None,
-                headers: None,
-            }
+    rule!(http_raw<URL<ParsedExpr>>; children!(
+        [scheme(sch), authority(auth), path(file_path)] => URL {
+            scheme: sch,
+            authority: auth,
+            path: File { file_path },
+            query: None,
+            headers: None,
         },
         [scheme(sch), authority(auth), path(file_path), query(q)] => {
             URL {
@@ -654,10 +748,10 @@ make_parser! {
 
     rule!(query<String>; captured_str!(s) => s.to_owned());
 
-    rule!(http<URL>; children!(
+    rule!(http<URL<ParsedExpr>>; children!(
         [http_raw(url)] => url,
-        [http_raw(url), import_hashed(ih)] =>
-            URL { headers: Some(Box::new(ih)), ..url },
+        [http_raw(url), import_expression(e)] =>
+            URL { headers: Some(e), ..url },
     ));
 
     rule!(env<String>; children!(
@@ -687,9 +781,9 @@ make_parser! {
         }
     );
 
-    token_rule!(missing<()>);
+    rule!(missing<()>);
 
-    rule!(import_type<ImportLocation>; children!(
+    rule!(import_type<ImportLocation<ParsedExpr>>; children!(
         [missing(_)] => {
             ImportLocation::Missing
         },
@@ -714,52 +808,53 @@ make_parser! {
         Hash::SHA256(hex::decode(hash).unwrap())
     });
 
-    rule!(import_hashed<ImportHashed>; children!(
+    rule!(import_hashed<crate::Import<ParsedExpr>>; children!(
         [import_type(location)] =>
-            ImportHashed { location, hash: None },
+            crate::Import {mode: ImportMode::Code, location, hash: None },
         [import_type(location), hash(h)] =>
-            ImportHashed { location, hash: Some(h) },
+            crate::Import {mode: ImportMode::Code, location, hash: Some(h) },
     ));
 
-    token_rule!(Text<()>);
-    token_rule!(Location<()>);
+    rule!(Text<()>);
+    rule!(Location<()>);
 
-    rule!(import<ParsedSubExpr> as expression; span; children!(
-        [import_hashed(location_hashed)] => {
-            spanned(span, Embed(Import {
+    rule!(import<ParsedExpr>; span; children!(
+        [import_hashed(imp)] => {
+            spanned(span, Import(crate::Import {
                 mode: ImportMode::Code,
-                location_hashed
+                ..imp
             }))
         },
-        [import_hashed(location_hashed), Text(_)] => {
-            spanned(span, Embed(Import {
+        [import_hashed(imp), Text(_)] => {
+            spanned(span, Import(crate::Import {
                 mode: ImportMode::RawText,
-                location_hashed
+                ..imp
             }))
         },
-        [import_hashed(location_hashed), Location(_)] => {
-            spanned(span, Embed(Import {
+        [import_hashed(imp), Location(_)] => {
+            spanned(span, Import(crate::Import {
                 mode: ImportMode::Location,
-                location_hashed
+                ..imp
             }))
         },
     ));
 
-    token_rule!(lambda<()>);
-    token_rule!(forall<()>);
-    token_rule!(arrow<()>);
-    token_rule!(merge<()>);
-    token_rule!(assert<()>);
-    token_rule!(if_<()>);
-    token_rule!(in_<()>);
-
-    rule!(empty_list_literal<ParsedSubExpr> as expression; span; children!(
-        [expression(e)] => {
+    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<ParsedSubExpr> as expression; span; children!(
+    rule!(expression<ParsedExpr>; span; children!(
         [lambda(()), label(l), expression(typ),
                 arrow(()), expression(body)] => {
             spanned(span, Lam(l, typ, body))
@@ -777,19 +872,27 @@ make_parser! {
                 arrow(()), expression(body)] => {
             spanned(span, Pi(l, typ, body))
         },
-        [expression(typ), arrow(()), expression(body)] => {
+        [operator_expression(typ), arrow(()), expression(body)] => {
             spanned(span, Pi("_".into(), typ, body))
         },
-        [merge(()), expression(x), expression(y), expression(z)] => {
+        [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))
         },
-        [expression(e)] => e,
+        [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<ParsedSubExpr>, ParsedSubExpr)>;
+    rule!(let_binding<(Label, Option<ParsedExpr>, ParsedExpr)>;
             children!(
         [label(name), expression(annot), expression(expr)] =>
             (name, Some(annot), expr),
@@ -797,137 +900,99 @@ make_parser! {
             (name, None, expr),
     ));
 
-    token_rule!(List<()>);
-    token_rule!(Optional<()>);
-
-    rule!(import_alt_expression<ParsedSubExpr> 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<ParsedSubExpr> 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<ParsedSubExpr> 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<ParsedSubExpr> 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<ParsedSubExpr> 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<ParsedSubExpr> 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<ParsedSubExpr> 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<ParsedSubExpr> 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<ParsedSubExpr> 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<ParsedSubExpr> 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<ParsedSubExpr> 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<ParsedSubExpr> 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<ParsedSubExpr> 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<ParsedSubExpr> as expression; span; children!(
-        [expression(e)] => e,
-        [expression(e), expression(annot)] => {
-            spanned(span, Annot(e, annot))
+    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))
+        }
     ));
 
-    token_rule!(Some_<()>);
-    token_rule!(toMap<()>);
+    rule!(Some_<()>);
 
-    rule!(application_expression<ParsedSubExpr> as expression; children!(
-        [expression(e)] => e,
-        [expression(first), expression(rest)..] => {
+    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<ParsedSubExpr> as expression; span;
+    rule!(first_application_expression<ParsedExpr>; span;
             children!(
-        [expression(e)] => e,
-        [Some_(()), expression(e)] => {
+        [Some_(()), import_expression(e)] => {
             spanned(span, SomeLit(e))
         },
-        [merge(()), expression(x), expression(y)] => {
+        [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!(selector_expression<ParsedSubExpr> as expression; children!(
-        [expression(e)] => e,
-        [expression(first), selector(rest)..] => {
+    rule!(import_expression<ParsedExpr>; span;
+            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!(
@@ -940,24 +1005,30 @@ make_parser! {
         [label(ls)..] => ls.collect(),
     ));
 
-    rule!(primitive_expression<ParsedSubExpr> as expression; span; children!(
+    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<ParsedSubExpr> as expression; span;
+    rule!(empty_record_literal<ParsedExpr>; span;
         captured_str!(_) => spanned(span, RecordLit(Default::default()))
     );
 
-    rule!(empty_record_type<ParsedSubExpr> as expression; span;
+    rule!(empty_record_type<ParsedExpr>; span;
         captured_str!(_) => spanned(span, RecordType(Default::default()))
     );
 
-    rule!(non_empty_record_type_or_literal<ParsedSubExpr> as expression; span;
+    rule!(non_empty_record_type_or_literal<ParsedExpr>; span;
           children!(
         [label(first_label), non_empty_record_type(rest)] => {
             let (first_expr, mut map) = rest;
@@ -972,28 +1043,28 @@ make_parser! {
     ));
 
     rule!(non_empty_record_type
-          <(ParsedSubExpr, DupTreeMap<Label, ParsedSubExpr>)>; children!(
+          <(ParsedExpr, DupTreeMap<Label, ParsedExpr>)>; children!(
         [expression(expr), record_type_entry(entries)..] => {
             (expr, entries.collect())
         }
     ));
 
-    rule!(record_type_entry<(Label, ParsedSubExpr)>; children!(
+    rule!(record_type_entry<(Label, ParsedExpr)>; children!(
         [label(name), expression(expr)] => (name, expr)
     ));
 
     rule!(non_empty_record_literal
-          <(ParsedSubExpr, DupTreeMap<Label, ParsedSubExpr>)>; children!(
+          <(ParsedExpr, DupTreeMap<Label, ParsedExpr>)>; children!(
         [expression(expr), record_literal_entry(entries)..] => {
             (expr, entries.collect())
         }
     ));
 
-    rule!(record_literal_entry<(Label, ParsedSubExpr)>; children!(
+    rule!(record_literal_entry<(Label, ParsedExpr)>; children!(
         [label(name), expression(expr)] => (name, expr)
     ));
 
-    rule!(union_type<ParsedSubExpr> as expression; span; children!(
+    rule!(union_type<ParsedExpr>; span; children!(
         [empty_union_type(_)] => {
             spanned(span, UnionType(Default::default()))
         },
@@ -1002,14 +1073,14 @@ make_parser! {
         },
     ));
 
-    token_rule!(empty_union_type<()>);
+    rule!(empty_union_type<()>);
 
-    rule!(union_type_entry<(Label, Option<ParsedSubExpr>)>; children!(
+    rule!(union_type_entry<(Label, Option<ParsedExpr>)>; children!(
         [label(name), expression(expr)] => (name, Some(expr)),
         [label(name)] => (name, None),
     ));
 
-    rule!(non_empty_list_literal<ParsedSubExpr> as expression; span;
+    rule!(non_empty_list_literal<ParsedExpr>; span;
           children!(
         [expression(items)..] => spanned(
             span,
@@ -1017,35 +1088,15 @@ make_parser! {
         )
     ));
 
-    rule!(final_expression<ParsedSubExpr> as expression; children!(
-        [expression(e), EOI(_eoi)] => e
+    rule!(final_expression<ParsedExpr>; children!(
+        [expression(e), EOI(_)] => e
     ));
 }
 
-pub fn parse_expr(s: &str) -> ParseResult<ParsedSubExpr> {
+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 = do_parse(rc_input, pairs.next().unwrap())?;
+    let expr = EntryPoint::final_expression(rc_input, pairs.next().unwrap())?;
     assert_eq!(pairs.next(), None);
-    match expr {
-        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);
+    Ok(expr)
 }
diff --git a/dhall_syntax/src/printer.rs b/dhall_syntax/src/printer.rs
index 5312f23..1e3b7f2 100644
--- a/dhall_syntax/src/printer.rs
+++ b/dhall_syntax/src/printer.rs
@@ -41,6 +41,12 @@ impl<SE: Display + Clone, E: Display> Display for ExprF<SE, E> {
                     write!(f, " : {}", c)?;
                 }
             }
+            ToMap(a, b) => {
+                write!(f, "toMap {}", a)?;
+                if let Some(b) = b {
+                    write!(f, " : {}", b)?;
+                }
+            }
             Annot(a, b) => {
                 write!(f, "{} : {}", a, b)?;
             }
@@ -88,6 +94,7 @@ impl<SE: Display + Clone, E: Display> Display for ExprF<SE, E> {
                 }
                 Ok(())
             })?,
+            Import(a) => a.fmt(f)?,
             Embed(a) => a.fmt(f)?,
         }
         Ok(())
@@ -111,21 +118,21 @@ enum PrintPhase {
 // Wraps an Expr with a phase, so that phase selsction can be done
 // separate from the actual printing
 #[derive(Clone)]
-struct PhasedExpr<'a, S, A>(&'a SubExpr<S, A>, PrintPhase);
+struct PhasedExpr<'a, A>(&'a Expr<A>, PrintPhase);
 
-impl<'a, S: Clone, A: Display + Clone> Display for PhasedExpr<'a, S, A> {
+impl<'a, A: Display + Clone> Display for PhasedExpr<'a, A> {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         self.0.as_ref().fmt_phase(f, self.1)
     }
 }
 
-impl<'a, S: Clone, A: Display + Clone> PhasedExpr<'a, S, A> {
-    fn phase(self, phase: PrintPhase) -> PhasedExpr<'a, S, A> {
+impl<'a, A: Display + Clone> PhasedExpr<'a, A> {
+    fn phase(self, phase: PrintPhase) -> PhasedExpr<'a, A> {
         PhasedExpr(self.0, phase)
     }
 }
 
-impl<S: Clone, A: Display + Clone> Expr<S, A> {
+impl<A: Display + Clone> RawExpr<A> {
     fn fmt_phase(
         &self,
         f: &mut fmt::Formatter,
@@ -143,6 +150,7 @@ impl<S: Clone, A: Display + Clone> Expr<S, A> {
             | NEListLit(_)
             | SomeLit(_)
             | Merge(_, _, _)
+            | ToMap(_, _)
             | Annot(_, _)
                 if phase > Base =>
             {
@@ -151,12 +159,14 @@ impl<S: Clone, A: Display + Clone> Expr<S, A> {
             // Precedence is magically handled by the ordering of BinOps.
             ExprF::BinOp(op, _, _) if phase > PrintPhase::BinOp(*op) => true,
             ExprF::App(_, _) if phase > PrintPhase::App => true,
-            Field(_, _) | Projection(_, _) if phase > Import => true,
+            Field(_, _) | Projection(_, _) if phase > PrintPhase::Import => {
+                true
+            }
             _ => false,
         };
 
         // Annotate subexpressions with the appropriate phase, defaulting to Base
-        let phased_self = match self.map_ref_simple(|e| PhasedExpr(e, Base)) {
+        let phased_self = match self.map_ref(|e| PhasedExpr(e, Base)) {
             Pi(a, b, c) => {
                 if &String::from(&a) == "_" {
                     Pi(a, b.phase(Operator), c)
@@ -165,18 +175,25 @@ impl<S: Clone, A: Display + Clone> Expr<S, A> {
                 }
             }
             Merge(a, b, c) => Merge(
-                a.phase(Import),
-                b.phase(Import),
+                a.phase(PrintPhase::Import),
+                b.phase(PrintPhase::Import),
                 c.map(|x| x.phase(PrintPhase::App)),
             ),
+            ToMap(a, b) => ToMap(
+                a.phase(PrintPhase::Import),
+                b.map(|x| x.phase(PrintPhase::App)),
+            ),
             Annot(a, b) => Annot(a.phase(Operator), b),
             ExprF::BinOp(op, a, b) => ExprF::BinOp(
                 op,
                 a.phase(PrintPhase::BinOp(op)),
                 b.phase(PrintPhase::BinOp(op)),
             ),
-            SomeLit(e) => SomeLit(e.phase(Import)),
-            ExprF::App(f, a) => ExprF::App(f.phase(Import), a.phase(Import)),
+            SomeLit(e) => SomeLit(e.phase(PrintPhase::Import)),
+            ExprF::App(f, a) => ExprF::App(
+                f.phase(PrintPhase::Import),
+                a.phase(PrintPhase::Import),
+            ),
             Field(a, b) => Field(a.phase(Primitive), b),
             Projection(e, ls) => Projection(e.phase(Primitive), ls),
             e => e,
@@ -196,7 +213,7 @@ impl<S: Clone, A: Display + Clone> Expr<S, A> {
     }
 }
 
-impl<S: Clone, A: Display + Clone> Display for SubExpr<S, A> {
+impl<A: Display + Clone> Display for Expr<A> {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         self.as_ref().fmt_phase(f, PrintPhase::Base)
     }
@@ -224,7 +241,7 @@ where
     f.write_str(close)
 }
 
-impl<SubExpr: Display + Clone> Display for InterpolatedText<SubExpr> {
+impl<SubExpr: Display> Display for InterpolatedText<SubExpr> {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         f.write_str("\"")?;
         for x in self.iter() {
@@ -338,19 +355,14 @@ impl Display for Hash {
         }
     }
 }
-impl Display for ImportHashed {
+impl<SubExpr: Display> Display for Import<SubExpr> {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         use FilePrefix::*;
         use ImportLocation::*;
-        let fmt_remote_path_component = |s: &str| -> String {
-            use percent_encoding::{
-                utf8_percent_encode, PATH_SEGMENT_ENCODE_SET,
-            };
-            utf8_percent_encode(s, PATH_SEGMENT_ENCODE_SET).to_string()
-        };
-        let fmt_local_path_component = |s: &str| -> String {
+        use ImportMode::*;
+        let quote_if_needed = |s: &str| -> String {
             if s.chars().all(|c| c.is_ascii_alphanumeric()) {
-                s.to_owned()
+                s.to_string()
             } else {
                 format!("\"{}\"", s)
             }
@@ -365,21 +377,13 @@ impl Display for ImportHashed {
                     Absolute => "",
                 };
                 write!(f, "{}/", prefix)?;
-                let full_path: String = path
-                    .clone()
-                    .into_iter()
-                    .map(|c| fmt_local_path_component(c.as_ref()))
-                    .join("/");
-                f.write_str(&full_path)?;
+                let path: String =
+                    path.file_path.iter().map(|c| quote_if_needed(&*c)).join("/");
+                f.write_str(&path)?;
             }
             Remote(url) => {
                 write!(f, "{}://{}/", url.scheme, url.authority,)?;
-                let path: String = url
-                    .path
-                    .clone()
-                    .into_iter()
-                    .map(|c| fmt_remote_path_component(c.as_ref()))
-                    .join("/");
+                let path: String = url.path.file_path.iter().join("/");
                 f.write_str(&path)?;
                 if let Some(q) = &url.query {
                     write!(f, "?{}", q)?
@@ -419,14 +423,6 @@ impl Display for ImportHashed {
             write!(f, " ")?;
             hash.fmt(f)?;
         }
-        Ok(())
-    }
-}
-
-impl Display for Import {
-    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        self.location_hashed.fmt(f)?;
-        use ImportMode::*;
         match self.mode {
             Code => {}
             RawText => write!(f, " as Text")?,
@@ -493,9 +489,3 @@ impl<Label: Display> Display for V<Label> {
         Ok(())
     }
 }
-
-impl Display for X {
-    fn fmt(&self, _: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        match *self {}
-    }
-}