Merge pull request #102 from Nadrieril/inline-headers

Implement inline headers parsing 

17 files changed, 343 insertions, 498 deletions

diff --git a/dhall/build.rs b/dhall/build.rs
index 790ad8e..cbda288 100644
--- a/dhall/build.rs
+++ b/dhall/build.rs
@@ -93,13 +93,6 @@ fn main() -> std::io::Result<()> {
     make_test_module(&mut file, "parse", "parser/", "Parser", |path| {
         // Too slow in debug mode
         path == "success/largeExpression"
-            // TODO: Inline headers
-            || path == "success/unit/import/inlineUsing"
-            || path == "success/unit/import/Headers"
-            || path == "success/unit/import/HeadersDoubleHash"
-            || path == "success/unit/import/HeadersDoubleHashPrecedence"
-            || path == "success/unit/import/HeadersHashPrecedence"
-            || path == "success/unit/import/HeadersInteriorHash"
             // TODO: projection by expression
             || path == "success/recordProjectionByExpression"
             || path == "success/RecordProjectionByType"
@@ -119,9 +112,6 @@ fn main() -> std::io::Result<()> {
         path.starts_with("failure/")
             // Too slow in debug mode
             || path == "success/largeExpression"
-            // TODO: Inline headers
-            || path == "success/unit/import/inlineUsing"
-            || path == "success/unit/import/Headers"
             // TODO: projection by expression
             || path == "success/recordProjectionByExpression"
             || path == "success/RecordProjectionByType"
@@ -149,9 +139,6 @@ fn main() -> std::io::Result<()> {
             || path == "success/double"
             || path == "success/unit/DoubleLitExponentNoDot"
             || path == "success/unit/DoubleLitSecretelyInt"
-            // TODO: Inline headers
-            || path == "success/unit/import/inlineUsing"
-            || path == "success/unit/import/Headers"
             // TODO: projection by expression
             || path == "success/recordProjectionByExpression"
             || path == "success/RecordProjectionByType"
@@ -237,10 +224,9 @@ fn main() -> std::io::Result<()> {
             false
             // TODO: Enable imports in typecheck tests
             || path == "failure/importBoundary"
+            || path == "failure/customHeadersUsingBoundVariable"
             // Too slow
             || path == "success/prelude"
-            // TODO: Inline headers
-            || path == "failure/customHeadersUsingBoundVariable"
             // TODO: projection by expression
             || path == "failure/unit/RecordProjectionByTypeFieldTypeMismatch"
             || path == "failure/unit/RecordProjectionByTypeNotPresent"
diff --git a/dhall/src/core/thunk.rs b/dhall/src/core/thunk.rs
index c18014e..7c5c537 100644
--- a/dhall/src/core/thunk.rs
+++ b/dhall/src/core/thunk.rs
@@ -2,7 +2,7 @@ use std::borrow::Cow;
 use std::cell::{Ref, RefCell};
 use std::rc::Rc;
 
-use dhall_syntax::{Const, ExprF, X};
+use dhall_syntax::{Const, ExprF};
 
 use crate::core::context::{NormalizationContext, TypecheckContext};
 use crate::core::value::Value;
@@ -12,7 +12,7 @@ use crate::phase::normalize::{
     apply_any, normalize_one_layer, normalize_whnf, InputSubExpr, OutputSubExpr,
 };
 use crate::phase::typecheck::type_of_const;
-use crate::phase::{NormalizedSubExpr, Type, Typed};
+use crate::phase::{Normalized, NormalizedSubExpr, Type, Typed};
 
 #[derive(Debug, Clone, Copy)]
 enum Marker {
@@ -30,7 +30,7 @@ enum ThunkInternal {
     /// Partially normalized value whose subexpressions have been thunked (this is returned from
     /// typechecking). Note that this is different from `Value::PartialExpr` because there is no
     /// requirement of WHNF here.
-    PartialExpr(ExprF<Thunk, X>),
+    PartialExpr(ExprF<Thunk, Normalized>),
     /// Partially normalized value.
     /// Invariant: if the marker is `NF`, the value must be fully normalized
     Value(Marker, Value),
@@ -123,7 +123,7 @@ impl Thunk {
         ThunkInternal::Value(WHNF, v).into_thunk()
     }
 
-    pub fn from_partial_expr(e: ExprF<Thunk, X>) -> Thunk {
+    pub fn from_partial_expr(e: ExprF<Thunk, Normalized>) -> Thunk {
         ThunkInternal::PartialExpr(e).into_thunk()
     }
 
@@ -309,7 +309,6 @@ impl Shift for ThunkInternal {
                 e.traverse_ref_with_special_handling_of_binders(
                     |v| Ok(v.shift(delta, var)?),
                     |x, v| Ok(v.shift(delta, &var.under_binder(x))?),
-                    |x| Ok(X::clone(x)),
                 )?,
             ),
             ThunkInternal::Value(m, v) => {
@@ -356,7 +355,6 @@ impl Subst<Typed> for ThunkInternal {
                             &val.under_binder(x),
                         )
                     },
-                    X::clone,
                 ),
             ),
             ThunkInternal::Value(_, v) => {
diff --git a/dhall/src/core/value.rs b/dhall/src/core/value.rs
index 8486d6e..20a6021 100644
--- a/dhall/src/core/value.rs
+++ b/dhall/src/core/value.rs
@@ -2,7 +2,7 @@ use std::collections::HashMap;
 
 use dhall_syntax::{
     rc, Builtin, Const, ExprF, Integer, InterpolatedTextContents, Label,
-    NaiveDouble, Natural, X,
+    NaiveDouble, Natural,
 };
 
 use crate::core::thunk::{Thunk, TypedThunk};
@@ -10,7 +10,7 @@ use crate::core::var::{AlphaLabel, AlphaVar, Shift, Subst};
 use crate::phase::normalize::{
     apply_builtin, normalize_one_layer, squash_textlit, OutputSubExpr,
 };
-use crate::phase::Typed;
+use crate::phase::{Normalized, Typed};
 
 /// A semantic value. The invariants ensure this value represents a Weak-Head
 /// Normal Form (WHNF). This means that this first constructor is the first constructor of the
@@ -59,7 +59,7 @@ pub enum Value {
     TextLit(Vec<InterpolatedTextContents<Thunk>>),
     Equivalence(TypedThunk, TypedThunk),
     // Invariant: this must not contain a value captured by one of the variants above.
-    PartialExpr(ExprF<Thunk, X>),
+    PartialExpr(ExprF<Thunk, Normalized>),
 }
 
 impl Value {
@@ -243,7 +243,7 @@ impl Value {
                 y.normalize_to_expr_maybe_alpha(alpha),
             )),
             Value::PartialExpr(e) => {
-                rc(e.map_ref_simple(|v| v.normalize_to_expr_maybe_alpha(alpha)))
+                rc(e.map_ref(|v| v.normalize_to_expr_maybe_alpha(alpha)))
             }
         }
     }
@@ -333,8 +333,8 @@ impl Value {
                 y.normalize_mut();
             }
             Value::PartialExpr(e) => {
-                // TODO: need map_mut_simple
-                e.map_ref_simple(|v| {
+                // TODO: need map_mut
+                e.map_ref(|v| {
                     v.normalize_nf();
                 });
             }
@@ -475,7 +475,6 @@ impl Shift for Value {
                 e.traverse_ref_with_special_handling_of_binders(
                     |v| Ok(v.shift(delta, var)?),
                     |x, v| Ok(v.shift(delta, &var.under_binder(x))?),
-                    |x| Ok(X::clone(x)),
                 )?,
             ),
         })
@@ -500,7 +499,6 @@ impl Subst<Typed> for Value {
                             &val.under_binder(x),
                         )
                     },
-                    X::clone,
                 ))
             }
             // Retry normalizing since substituting may allow progress
diff --git a/dhall/src/error/mod.rs b/dhall/src/error/mod.rs
index 3626d96..8f6ff51 100644
--- a/dhall/src/error/mod.rs
+++ b/dhall/src/error/mod.rs
@@ -4,7 +4,7 @@ use dhall_syntax::{BinOp, Import, Label, ParseError, V};
 
 use crate::core::context::TypecheckContext;
 use crate::phase::resolve::ImportStack;
-use crate::phase::{Normalized, Type, Typed};
+use crate::phase::{Normalized, NormalizedSubExpr, Type, Typed};
 
 pub type Result<T> = std::result::Result<T, Error>;
 
@@ -21,9 +21,9 @@ pub enum Error {
 
 #[derive(Debug)]
 pub enum ImportError {
-    Recursive(Import, Box<Error>),
-    UnexpectedImport(Import),
-    ImportCycle(ImportStack, Import),
+    Recursive(Import<NormalizedSubExpr>, Box<Error>),
+    UnexpectedImport(Import<NormalizedSubExpr>),
+    ImportCycle(ImportStack, Import<NormalizedSubExpr>),
 }
 
 #[derive(Debug)]
diff --git a/dhall/src/phase/binary.rs b/dhall/src/phase/binary.rs
index 3292617..36dd471 100644
--- a/dhall/src/phase/binary.rs
+++ b/dhall/src/phase/binary.rs
@@ -4,13 +4,12 @@ use std::iter::FromIterator;
 
 use dhall_syntax::map::DupTreeMap;
 use dhall_syntax::{
-    rc, ExprF, FilePrefix, Hash, Import, ImportHashed, ImportLocation,
-    ImportMode, Integer, InterpolatedText, Label, Natural, Scheme, SubExpr,
-    URL, V,
+    rc, ExprF, FilePrefix, Hash, Import, ImportLocation, ImportMode, Integer,
+    InterpolatedText, Label, Natural, Scheme, SubExpr, URL, V,
 };
 
 use crate::error::{DecodeError, EncodeError};
-use crate::phase::{DecodedSubExpr, ParsedSubExpr};
+use crate::phase::DecodedSubExpr;
 
 pub fn decode(data: &[u8]) -> Result<DecodedSubExpr, DecodeError> {
     match serde_cbor::de::from_slice(data) {
@@ -19,8 +18,7 @@ pub fn decode(data: &[u8]) -> Result<DecodedSubExpr, DecodeError> {
     }
 }
 
-//TODO: encode normalized expression too
-pub fn encode(expr: &ParsedSubExpr) -> Result<Vec<u8>, EncodeError> {
+pub fn encode<E>(expr: &SubExpr<E>) -> Result<Vec<u8>, EncodeError> {
     serde_cbor::ser::to_vec(&Serialize::Expr(expr))
         .map_err(|e| EncodeError::CBORError(e))
 }
@@ -261,20 +259,12 @@ fn cbor_value_to_dhall(
                         };
                         let headers = match rest.next() {
                             Some(Null) => None,
-                            // TODO
-                            // Some(x) => {
-                            //     match cbor_value_to_dhall(&x)?.as_ref() {
-                            //         Embed(import) => Some(Box::new(
-                            //             import.location_hashed.clone(),
-                            //         )),
-                            //         _ => Err(DecodeError::WrongFormatError(
-                            //             "import/remote/headers".to_owned(),
-                            //         ))?,
-                            //     }
-                            // }
+                            Some(x) => {
+                                let x = cbor_value_to_dhall(&x)?;
+                                Some(x)
+                            }
                             _ => Err(DecodeError::WrongFormatError(
-                                "import/remote/headers is unimplemented"
-                                    .to_owned(),
+                                "import/remote/headers".to_owned(),
                             ))?,
                         };
                         let authority = match rest.next() {
@@ -340,9 +330,10 @@ fn cbor_value_to_dhall(
                         "import/type".to_owned(),
                     ))?,
                 };
-                Embed(Import {
+                Import(dhall_syntax::Import {
                     mode,
-                    location_hashed: ImportHashed { hash, location },
+                    hash,
+                    location,
                 })
             }
             [U64(25), bindings..] => {
@@ -424,11 +415,11 @@ where
         .collect::<Result<_, _>>()
 }
 
-enum Serialize<'a> {
-    Expr(&'a ParsedSubExpr),
+enum Serialize<'a, E> {
+    Expr(&'a SubExpr<E>),
     CBOR(cbor::Value),
-    RecordMap(&'a DupTreeMap<Label, ParsedSubExpr>),
-    UnionMap(&'a DupTreeMap<Label, Option<ParsedSubExpr>>),
+    RecordMap(&'a DupTreeMap<Label, SubExpr<E>>),
+    UnionMap(&'a DupTreeMap<Label, Option<SubExpr<E>>>),
 }
 
 macro_rules! count {
@@ -448,7 +439,7 @@ macro_rules! ser_seq {
     }};
 }
 
-fn serialize_subexpr<S>(ser: S, e: &ParsedSubExpr) -> Result<S::Ok, S::Error>
+fn serialize_subexpr<S, E>(ser: S, e: &SubExpr<E>) -> Result<S::Ok, S::Error>
 where
     S: serde::ser::Serializer,
 {
@@ -458,21 +449,14 @@ where
     use std::iter::once;
 
     use self::Serialize::{RecordMap, UnionMap};
-    fn expr(x: &ParsedSubExpr) -> self::Serialize<'_> {
+    fn expr<E>(x: &SubExpr<E>) -> self::Serialize<'_, E> {
         self::Serialize::Expr(x)
     }
-    fn cbor<'a>(v: cbor::Value) -> self::Serialize<'a> {
-        self::Serialize::CBOR(v)
-    }
-    fn tag<'a>(x: u64) -> self::Serialize<'a> {
-        cbor(U64(x))
-    }
-    fn null<'a>() -> self::Serialize<'a> {
-        cbor(cbor::Value::Null)
-    }
-    fn label<'a>(l: &Label) -> self::Serialize<'a> {
-        cbor(cbor::Value::String(l.into()))
-    }
+    let cbor =
+        |v: cbor::Value| -> self::Serialize<'_, E> { self::Serialize::CBOR(v) };
+    let tag = |x: u64| cbor(U64(x));
+    let null = || cbor(cbor::Value::Null);
+    let label = |l: &Label| cbor(cbor::Value::String(l.into()));
 
     match e.as_ref() {
         Const(c) => ser.serialize_str(&c.to_string()),
@@ -573,18 +557,24 @@ where
                 .chain(once(expr(x)))
                 .chain(ls.iter().map(label)),
         ),
-        Embed(import) => serialize_import(ser, import),
+        Import(import) => serialize_import(ser, import),
+        Embed(_) => unimplemented!(
+            "An expression with resolved imports cannot be binary-encoded"
+        ),
     }
 }
 
-fn serialize_import<S>(ser: S, import: &Import) -> Result<S::Ok, S::Error>
+fn serialize_import<S, E>(
+    ser: S,
+    import: &Import<SubExpr<E>>,
+) -> Result<S::Ok, S::Error>
 where
     S: serde::ser::Serializer,
 {
     use cbor::Value::{Bytes, Null, U64};
     use serde::ser::SerializeSeq;
 
-    let count = 4 + match &import.location_hashed.location {
+    let count = 4 + match &import.location {
         ImportLocation::Remote(url) => 3 + url.path.len(),
         ImportLocation::Local(_, path) => path.len(),
         ImportLocation::Env(_) => 1,
@@ -594,7 +584,7 @@ where
 
     ser_seq.serialize_element(&U64(24))?;
 
-    let hash = match &import.location_hashed.hash {
+    let hash = match &import.hash {
         None => Null,
         Some(Hash::SHA256(h)) => {
             let mut bytes = vec![18, 32];
@@ -611,7 +601,7 @@ where
     };
     ser_seq.serialize_element(&U64(mode))?;
 
-    let scheme = match &import.location_hashed.location {
+    let scheme = match &import.location {
         ImportLocation::Remote(url) => match url.scheme {
             Scheme::HTTP => 0,
             Scheme::HTTPS => 1,
@@ -627,16 +617,13 @@ where
     };
     ser_seq.serialize_element(&U64(scheme))?;
 
-    match &import.location_hashed.location {
+    match &import.location {
         ImportLocation::Remote(url) => {
             match &url.headers {
                 None => ser_seq.serialize_element(&Null)?,
-                Some(location_hashed) => ser_seq.serialize_element(
-                    &self::Serialize::Expr(&rc(ExprF::Embed(Import {
-                        mode: ImportMode::Code,
-                        location_hashed: location_hashed.as_ref().clone(),
-                    }))),
-                )?,
+                Some(e) => {
+                    ser_seq.serialize_element(&self::Serialize::Expr(e))?
+                }
             };
             ser_seq.serialize_element(&url.authority)?;
             for p in &url.path {
@@ -661,7 +648,7 @@ where
     ser_seq.end()
 }
 
-impl<'a> serde::ser::Serialize for Serialize<'a> {
+impl<'a, E> serde::ser::Serialize for Serialize<'a, E> {
     fn serialize<S>(&self, ser: S) -> Result<S::Ok, S::Error>
     where
         S: serde::ser::Serializer,
diff --git a/dhall/src/phase/mod.rs b/dhall/src/phase/mod.rs
index 8c93889..b73597c 100644
--- a/dhall/src/phase/mod.rs
+++ b/dhall/src/phase/mod.rs
@@ -2,7 +2,7 @@ use std::borrow::Cow;
 use std::fmt::Display;
 use std::path::Path;
 
-use dhall_syntax::{Const, Import, SubExpr, X};
+use dhall_syntax::{Const, SubExpr, Void};
 
 use crate::core::thunk::{Thunk, TypedThunk};
 use crate::core::value::Value;
@@ -17,15 +17,17 @@ pub(crate) mod parse;
 pub(crate) mod resolve;
 pub(crate) mod typecheck;
 
-pub type ParsedSubExpr = SubExpr<Import>;
-pub type DecodedSubExpr = SubExpr<Import>;
+pub type ParsedSubExpr = SubExpr<Void>;
+pub type DecodedSubExpr = SubExpr<Void>;
 pub type ResolvedSubExpr = SubExpr<Normalized>;
-pub type NormalizedSubExpr = SubExpr<X>;
+pub type NormalizedSubExpr = SubExpr<Normalized>;
 
 #[derive(Debug, Clone)]
 pub struct Parsed(ParsedSubExpr, ImportRoot);
 
 /// An expression where all imports have been resolved
+///
+/// Invariant: there must be no `Import` nodes or `ImportAlt` operations left.
 #[derive(Debug, Clone)]
 pub struct Resolved(ResolvedSubExpr);
 
@@ -155,6 +157,10 @@ impl Typed {
 }
 
 impl Normalized {
+    pub fn encode(&self) -> Result<Vec<u8>, EncodeError> {
+        crate::phase::binary::encode(&self.to_expr())
+    }
+
     #[allow(dead_code)]
     pub fn to_expr(&self) -> NormalizedSubExpr {
         self.0.to_expr()
@@ -218,6 +224,18 @@ derive_traits_for_wrapper_struct!(Parsed);
 derive_traits_for_wrapper_struct!(Resolved);
 derive_traits_for_wrapper_struct!(Normalized);
 
+impl std::hash::Hash for Normalized {
+    fn hash<H>(&self, state: &mut H)
+    where
+        H: std::hash::Hasher,
+    {
+        match self.encode() {
+            Ok(vec) => vec.hash(state),
+            Err(_) => {}
+        }
+    }
+}
+
 impl Eq for Typed {}
 impl PartialEq for Typed {
     fn eq(&self, other: &Self) -> bool {
diff --git a/dhall/src/phase/normalize.rs b/dhall/src/phase/normalize.rs
index 644f98c..adbcb02 100644
--- a/dhall/src/phase/normalize.rs
+++ b/dhall/src/phase/normalize.rs
@@ -2,14 +2,14 @@ use std::collections::HashMap;
 
 use dhall_syntax::{
     BinOp, Builtin, ExprF, InterpolatedText, InterpolatedTextContents,
-    NaiveDouble, X,
+    NaiveDouble,
 };
 
 use crate::core::context::NormalizationContext;
 use crate::core::thunk::{Thunk, TypedThunk};
 use crate::core::value::Value;
 use crate::core::var::Subst;
-use crate::phase::{NormalizedSubExpr, ResolvedSubExpr, Typed};
+use crate::phase::{Normalized, NormalizedSubExpr, ResolvedSubExpr, Typed};
 
 pub type InputSubExpr = ResolvedSubExpr;
 pub type OutputSubExpr = NormalizedSubExpr;
@@ -86,7 +86,7 @@ pub fn apply_builtin(b: Builtin, args: Vec<Thunk>) -> Value {
                     // Empty string literal.
                     [] => {
                         // Printing InterpolatedText takes care of all the escaping
-                        let txt: InterpolatedText<X> =
+                        let txt: InterpolatedText<Normalized> =
                             std::iter::empty().collect();
                         let s = txt.to_string();
                         Ok((
@@ -98,10 +98,11 @@ pub fn apply_builtin(b: Builtin, args: Vec<Thunk>) -> Value {
                     // interpolations, there is a single Text item) in the literal.
                     [InterpolatedTextContents::Text(s)] => {
                         // Printing InterpolatedText takes care of all the escaping
-                        let txt: InterpolatedText<X> = std::iter::once(
-                            InterpolatedTextContents::Text(s.clone()),
-                        )
-                        .collect();
+                        let txt: InterpolatedText<Normalized> =
+                            std::iter::once(InterpolatedTextContents::Text(
+                                s.clone(),
+                            ))
+                            .collect();
                         let s = txt.to_string();
                         Ok((
                             r,
@@ -376,11 +377,10 @@ pub fn normalize_whnf(ctx: NormalizationContext, expr: InputSubExpr) -> Value {
     }
 
     // Thunk subexpressions
-    let expr: ExprF<Thunk, X> =
+    let expr: ExprF<Thunk, Normalized> =
         expr.as_ref().map_ref_with_special_handling_of_binders(
             |e| Thunk::new(ctx.clone(), e.clone()),
             |x, e| Thunk::new(ctx.skip(x), e.clone()),
-            |_| unreachable!(),
         );
 
     normalize_one_layer(expr)
@@ -391,7 +391,7 @@ enum Ret<'a> {
     Value(Value),
     Thunk(Thunk),
     ThunkRef(&'a Thunk),
-    Expr(ExprF<Thunk, X>),
+    Expr(ExprF<Thunk, Normalized>),
 }
 
 /// Performs an intersection of two HashMaps.
@@ -636,7 +636,7 @@ fn apply_binop<'a>(o: BinOp, x: &'a Thunk, y: &'a Thunk) -> Option<Ret<'a>> {
     })
 }
 
-pub fn normalize_one_layer(expr: ExprF<Thunk, X>) -> Value {
+pub fn normalize_one_layer(expr: ExprF<Thunk, Normalized>) -> Value {
     use Value::{
         AppliedBuiltin, BoolLit, DoubleLit, EmptyListLit, IntegerLit, Lam,
         NEListLit, NEOptionalLit, NaturalLit, Pi, RecordLit, RecordType,
@@ -644,6 +644,9 @@ pub fn normalize_one_layer(expr: ExprF<Thunk, X>) -> Value {
     };
 
     let ret = match expr {
+        ExprF::Import(_) => unreachable!(
+            "There should remain no imports in a resolved expression"
+        ),
         ExprF::Embed(_) => unreachable!(),
         ExprF::Var(_) => unreachable!(),
         ExprF::Annot(x, _) => Ret::Thunk(x),
diff --git a/dhall/src/phase/resolve.rs b/dhall/src/phase/resolve.rs
index abcee7e..52353e4 100644
--- a/dhall/src/phase/resolve.rs
+++ b/dhall/src/phase/resolve.rs
@@ -1,10 +1,10 @@
 use std::collections::HashMap;
 use std::path::{Path, PathBuf};
 
-use dhall_syntax::Import;
-
 use crate::error::{Error, ImportError};
-use crate::phase::{Normalized, Parsed, Resolved};
+use crate::phase::{Normalized, NormalizedSubExpr, Parsed, Resolved};
+
+type Import = dhall_syntax::Import<NormalizedSubExpr>;
 
 /// A root from which to resolve relative imports.
 #[derive(Debug, Clone, PartialEq, Eq)]
@@ -28,7 +28,7 @@ fn resolve_import(
     let cwd = match root {
         LocalDir(cwd) => cwd,
     };
-    match &import.location_hashed.location {
+    match &import.location {
         Local(prefix, path) => {
             let path: PathBuf = path.iter().cloned().collect();
             let path = match prefix {
diff --git a/dhall/src/phase/typecheck.rs b/dhall/src/phase/typecheck.rs
index ecf9793..89e2da8 100644
--- a/dhall/src/phase/typecheck.rs
+++ b/dhall/src/phase/typecheck.rs
@@ -2,7 +2,6 @@ use std::collections::HashMap;
 
 use dhall_syntax::{
     rc, Builtin, Const, Expr, ExprF, InterpolatedTextContents, Label, SubExpr,
-    X,
 };
 
 use crate::core::context::{NormalizationContext, TypecheckContext};
@@ -214,7 +213,7 @@ macro_rules! make_type {
     };
 }
 
-fn type_of_builtin(b: Builtin) -> Expr<X> {
+fn type_of_builtin<E>(b: Builtin) -> Expr<E> {
     use dhall_syntax::Builtin::*;
     match b {
         Bool | Natural | Integer | Double | Text => make_type!(Type),
@@ -377,12 +376,11 @@ fn type_with(
                 e.as_ref().traverse_ref_with_special_handling_of_binders(
                     |e| type_with(ctx, e.clone()),
                     |_, _| unreachable!(),
-                    |_| unreachable!(),
                 )?;
             let ret = type_last_layer(ctx, &expr)?;
             match ret {
                 RetTypeOnly(typ) => {
-                    let expr = expr.map_ref_simple(|typed| typed.to_thunk());
+                    let expr = expr.map_ref(|typed| typed.to_thunk());
                     Typed::from_thunk_and_type(
                         Thunk::from_partial_expr(expr),
                         typ,
@@ -398,7 +396,7 @@ fn type_with(
 /// layer.
 fn type_last_layer(
     ctx: &TypecheckContext,
-    e: &ExprF<Typed, X>,
+    e: &ExprF<Typed, Normalized>,
 ) -> Result<Ret, TypeError> {
     use crate::error::TypeMessage::*;
     use dhall_syntax::BinOp::*;
@@ -409,6 +407,9 @@ fn type_last_layer(
     let mkerr = |msg: TypeMessage| TypeError::new(ctx, msg);
 
     match e {
+        Import(_) => unreachable!(
+            "There should remain no imports in a resolved expression"
+        ),
         Lam(_, _, _) | Pi(_, _, _) | Let(_, _, _, _) | Embed(_) | Var(_) => {
             unreachable!()
         }
@@ -598,9 +599,7 @@ fn type_last_layer(
             }
         }
         Const(c) => Ok(RetWhole(Typed::from_const(*c))),
-        Builtin(b) => {
-            Ok(RetTypeOnly(mktype(ctx, rc(type_of_builtin(*b)).absurd())?))
-        }
+        Builtin(b) => Ok(RetTypeOnly(mktype(ctx, rc(type_of_builtin(*b)))?)),
         BoolLit(_) => Ok(RetTypeOnly(builtin_to_type(Bool)?)),
         NaturalLit(_) => Ok(RetTypeOnly(builtin_to_type(Natural)?)),
         IntegerLit(_) => Ok(RetTypeOnly(builtin_to_type(Integer)?)),
@@ -1016,7 +1015,7 @@ pub fn typecheck(e: Resolved) -> Result<Typed, TypeError> {
 
 pub fn typecheck_with(e: Resolved, ty: &Type) -> Result<Typed, TypeError> {
     let expr: SubExpr<_> = e.0;
-    let ty: SubExpr<_> = ty.to_expr().absurd();
+    let ty: SubExpr<_> = ty.to_expr();
     type_of(expr.rewrap(ExprF::Annot(expr.clone(), ty)))
 }
 pub fn skip_typecheck(e: Resolved) -> Typed {
diff --git a/dhall_generated_parser/build.rs b/dhall_generated_parser/build.rs
index 5275097..070aa9c 100644
--- a/dhall_generated_parser/build.rs
+++ b/dhall_generated_parser/build.rs
@@ -26,16 +26,15 @@ fn main() -> std::io::Result<()> {
             rules.get_mut(&line[2..]).map(|x| x.silent = true);
         }
     }
-    rules.remove("http");
-    rules.remove("url_path");
-    rules.remove("simple_label");
-    rules.remove("nonreserved_label");
 
     let mut file = File::create(pest_path)?;
     writeln!(&mut file, "// AUTO-GENERATED FILE. See build.rs.")?;
-    writeln!(&mut file, "{}", render_rules_to_pest(rules).pretty(80))?;
 
-    writeln!(&mut file)?;
+    // TODO: this is a cheat; properly support RFC3986 URLs instead
+    rules.remove("url_path");
+    writeln!(&mut file, "url_path = _{{ path }}")?;
+
+    rules.remove("simple_label");
     writeln!(
         &mut file,
         "simple_label = {{
@@ -43,30 +42,23 @@ fn main() -> std::io::Result<()> {
             | !keyword ~ simple_label_first_char ~ simple_label_next_char*
     }}"
     )?;
-    // TODO: this is a cheat; actually implement inline headers instead
-    writeln!(
-        &mut file,
-        "http = {{
-            http_raw
-            ~ (whsp
-                ~ using
-                ~ whsp1
-                ~ (import_hashed | ^\"(\" ~ whsp ~ import_hashed ~ whsp ~ ^\")\"))?
-    }}"
-    )?;
-    // TODO: this is a cheat; properly support RFC3986 URLs instead
-    writeln!(&mut file, "url_path = _{{ path }}")?;
+
+    rules.remove("nonreserved_label");
     writeln!(
         &mut file,
         "nonreserved_label = _{{
             !(builtin ~ !simple_label_next_char) ~ label
     }}"
     )?;
+
     writeln!(
         &mut file,
         "final_expression = ${{ SOI ~ complete_expression ~ EOI }}"
     )?;
 
+    writeln!(&mut file)?;
+    writeln!(&mut file, "{}", render_rules_to_pest(rules).pretty(80))?;
+
     // Generate pest parser manually to avoid spurious recompilations
     let derived = {
         let pest_path = "dhall.pest";
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 0cbece3..30ac4eb 100644
--- a/dhall_syntax/src/core/expr.rs
+++ b/dhall_syntax/src/core/expr.rs
@@ -10,9 +10,15 @@ pub type Double = NaiveDouble;
 
 /// An empty type
 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
-pub enum X {}
+pub enum Void {}
 
-pub fn trivial_result<T>(x: Result<T, X>) -> T {
+impl std::fmt::Display for Void {
+    fn fmt(&self, _f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
+        match *self {}
+    }
+}
+
+pub fn trivial_result<T>(x: Result<T, Void>) -> T {
     match x {
         Ok(x) => x,
         Err(e) => match e {},
@@ -55,6 +61,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)
@@ -68,7 +83,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,
@@ -80,7 +95,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
@@ -97,7 +112,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,
@@ -128,7 +143,7 @@ pub enum BinOp {
 }
 
 /// Built-ins
-#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub enum Builtin {
     Bool,
     Natural,
@@ -162,8 +177,8 @@ pub enum Builtin {
 }
 
 // Each node carries an annotation. In practice it's either X (no annotation) or a Span.
-#[derive(Debug)]
-pub struct SubExpr<Embed>(Rc<(Expr<Embed>, Option<Span>)>);
+#[derive(Debug, Clone)]
+pub struct SubExpr<Embed>(Box<(Expr<Embed>, Option<Span>)>);
 
 impl<Embed: PartialEq> std::cmp::PartialEq for SubExpr<Embed> {
     fn eq(&self, other: &Self) -> bool {
@@ -173,13 +188,22 @@ impl<Embed: PartialEq> std::cmp::PartialEq for SubExpr<Embed> {
 
 impl<Embed: Eq> std::cmp::Eq for SubExpr<Embed> {}
 
+impl<Embed: std::hash::Hash> std::hash::Hash for SubExpr<Embed> {
+    fn hash<H>(&self, state: &mut H)
+    where
+        H: std::hash::Hasher,
+    {
+        (self.0).0.hash(state)
+    }
+}
+
 pub type Expr<Embed> = ExprF<SubExpr<Embed>, Embed>;
 
 /// 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`
@@ -233,7 +257,9 @@ pub enum ExprF<SubExpr, Embed> {
     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),
 }
 
@@ -245,92 +271,62 @@ 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<E> Expr<E> {
-    fn traverse_embed<E2, Err>(
-        &self,
-        visit_embed: impl FnMut(&E) -> Result<E2, Err>,
-    ) -> Result<Expr<E2>, Err> {
-        self.visit(&mut visitor::TraverseEmbedVisitor(visit_embed))
-    }
-
-    fn map_embed<E2>(&self, mut map_embed: impl FnMut(&E) -> E2) -> Expr<E2> {
-        trivial_result(self.traverse_embed(|x| Ok(map_embed(x))))
-    }
-
     pub fn traverse_resolve<E2, Err>(
         &self,
-        visit_embed: impl FnMut(&E) -> Result<E2, Err>,
+        visit_import: impl FnMut(&Import<SubExpr<E2>>) -> Result<E2, Err>,
     ) -> Result<Expr<E2>, Err> {
         self.traverse_resolve_with_visitor(&mut visitor::ResolveVisitor(
-            visit_embed,
+            visit_import,
         ))
     }
 
@@ -339,35 +335,35 @@ impl<E> Expr<E> {
         visitor: &mut visitor::ResolveVisitor<F1>,
     ) -> Result<Expr<E2>, Err>
     where
-        F1: FnMut(&E) -> Result<E2, Err>,
+        F1: FnMut(&Import<SubExpr<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),
+            _ => {
+                let e = self.visit(&mut *visitor)?;
+                Ok(match &e {
+                    ExprF::Import(import) => ExprF::Embed((visitor.0)(import)?),
+                    _ => e,
+                })
+            }
         }
     }
 }
 
-impl Expr<X> {
-    pub fn absurd<E>(&self) -> Expr<E> {
-        self.visit(&mut visitor::AbsurdVisitor)
-    }
-}
-
 impl<E> SubExpr<E> {
     pub fn as_ref(&self) -> &Expr<E> {
         &self.0.as_ref().0
     }
 
     pub fn new(x: Expr<E>, n: Span) -> Self {
-        SubExpr(Rc::new((x, Some(n))))
+        SubExpr(Box::new((x, Some(n))))
     }
 
     pub fn from_expr_no_span(x: Expr<E>) -> Self {
-        SubExpr(Rc::new((x, None)))
+        SubExpr(Box::new((x, None)))
     }
 
     pub fn from_builtin(b: Builtin) -> Self {
@@ -375,56 +371,16 @@ impl<E> SubExpr<E> {
     }
 
     pub fn rewrap<E2>(&self, x: Expr<E2>) -> SubExpr<E2> {
-        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<E2>, Err> {
-        Ok(self.rewrap(self.as_ref().traverse_embed(visit_embed)?))
-    }
-
-    pub fn map_embed<E2>(
-        &self,
-        map_embed: impl FnMut(&E) -> E2,
-    ) -> SubExpr<E2> {
-        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 {
-        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!(),
-            )),
-        }
+        SubExpr(Box::new((x, (self.0).1.clone())))
     }
+}
 
+impl<E> SubExpr<E> {
     pub fn traverse_resolve<E2, Err>(
         &self,
-        visit_embed: impl FnMut(&E) -> Result<E2, Err>,
+        visit_import: impl FnMut(&Import<SubExpr<E2>>) -> Result<E2, Err>,
     ) -> Result<SubExpr<E2>, Err> {
-        Ok(self.rewrap(self.as_ref().traverse_resolve(visit_embed)?))
-    }
-}
-
-impl SubExpr<X> {
-    pub fn absurd<T>(&self) -> SubExpr<T> {
-        SubExpr::from_expr_no_span(self.as_ref().absurd())
-    }
-}
-
-impl<E> Clone for SubExpr<E> {
-    fn clone(&self) -> Self {
-        SubExpr(Rc::clone(&self.0))
+        Ok(self.rewrap(self.as_ref().traverse_resolve(visit_import)?))
     }
 }
 
diff --git a/dhall_syntax/src/core/import.rs b/dhall_syntax/src/core/import.rs
index d41eae2..9329d48 100644
--- a/dhall_syntax/src/core/import.rs
+++ b/dhall_syntax/src/core/import.rs
@@ -13,21 +13,20 @@ pub enum FilePrefix {
 
 /// 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, Vec<String>),
-    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: Vec<String>,
     pub query: Option<String>,
-    // TODO: implement inline headers
-    pub headers: Option<Box<ImportHashed>>,
+    pub headers: Option<SubExpr>,
 }
 
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -49,15 +48,54 @@ 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.clone(), 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(),
+        })
+    }
 }
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 50ec68a..7b4ed4b 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)?;
@@ -149,90 +153,19 @@ where
             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 +176,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 = Void;
 
     fn visit_subexpr(&mut self, subexpr: &'a SE1) -> Result<SE2, Self::Error> {
         Ok(self.0.visit_subexpr(subexpr))
@@ -259,40 +192,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,52 +219,29 @@ 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, E, E2, Err, F1>
-    ExprFFallibleVisitor<'a, SubExpr<E>, SubExpr<E2>, E, E2>
-    for &'b mut TraverseEmbedVisitor<F1>
-where
-    F1: FnMut(&E) -> Result<E2, Err>,
-{
-    type Error = Err;
-
-    fn visit_subexpr(
-        &mut self,
-        subexpr: &'a SubExpr<E>,
-    ) -> Result<SubExpr<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())
     }
 }
 
@@ -361,7 +251,7 @@ impl<'a, 'b, E, E2, Err, F1>
     ExprFFallibleVisitor<'a, SubExpr<E>, SubExpr<E2>, E, E2>
     for &'b mut ResolveVisitor<F1>
 where
-    F1: FnMut(&E) -> Result<E2, Err>,
+    F1: FnMut(&Import<SubExpr<E2>>) -> Result<E2, Err>,
 {
     type Error = Err;
 
@@ -375,20 +265,7 @@ where
                 .traverse_resolve_with_visitor(&mut **self)?,
         ))
     }
-    fn visit_embed(self, embed: &'a E) -> Result<E2, Self::Error> {
-        (self.0)(embed)
-    }
-}
-
-pub struct AbsurdVisitor;
-
-impl<'a, 'b, E> ExprFInFallibleVisitor<'a, SubExpr<X>, SubExpr<E>, X, E>
-    for &'b mut AbsurdVisitor
-{
-    fn visit_subexpr(&mut self, subexpr: &'a SubExpr<X>) -> SubExpr<E> {
-        SubExpr::from_expr_no_span(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/parser.rs b/dhall_syntax/src/parser.rs
index 1ab6e6d..8ecd0ab 100644
--- a/dhall_syntax/src/parser.rs
+++ b/dhall_syntax/src/parser.rs
@@ -15,10 +15,10 @@ 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.
 
-pub(crate) type ParsedExpr = Expr<Import>;
-pub(crate) type ParsedSubExpr = SubExpr<Import>;
-type ParsedText = InterpolatedText<SubExpr<Import>>;
-type ParsedTextContents = InterpolatedTextContents<SubExpr<Import>>;
+pub(crate) type ParsedExpr = Expr<Void>;
+pub(crate) type ParsedSubExpr = SubExpr<Void>;
+type ParsedText = InterpolatedText<ParsedSubExpr>;
+type ParsedTextContents = InterpolatedTextContents<ParsedSubExpr>;
 
 pub type ParseError = pest::error::Error<Rule>;
 
@@ -598,7 +598,7 @@ make_parser! {
         _ => unreachable!(),
     });
 
-    rule!(http_raw<URL>; children!(
+    rule!(http_raw<URL<ParsedSubExpr>>; children!(
         [scheme(sch), authority(auth), path(p)] => URL {
             scheme: sch,
             authority: auth,
@@ -619,10 +619,10 @@ make_parser! {
 
     rule!(query<String>; captured_str!(s) => s.to_owned());
 
-    rule!(http<URL>; children!(
+    rule!(http<URL<ParsedSubExpr>>; children!(
         [http_raw(url)] => url,
-        [http_raw(url), import_hashed(ih)] =>
-            URL { headers: Some(Box::new(ih)), ..url },
+        [http_raw(url), expression(e)] =>
+            URL { headers: Some(e), ..url },
     ));
 
     rule!(env<String>; children!(
@@ -654,7 +654,7 @@ make_parser! {
 
     token_rule!(missing<()>);
 
-    rule!(import_type<ImportLocation>; children!(
+    rule!(import_type<ImportLocation<ParsedSubExpr>>; children!(
         [missing(_)] => {
             ImportLocation::Missing
         },
@@ -679,33 +679,33 @@ make_parser! {
         Hash::SHA256(hex::decode(hash).unwrap())
     });
 
-    rule!(import_hashed<ImportHashed>; children!(
+    rule!(import_hashed<crate::Import<ParsedSubExpr>>; 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!(import<ParsedSubExpr> as expression; span; children!(
-        [import_hashed(location_hashed)] => {
-            spanned(span, Embed(Import {
+        [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
             }))
         },
     ));
diff --git a/dhall_syntax/src/printer.rs b/dhall_syntax/src/printer.rs
index 95eafe5..256ea65 100644
--- a/dhall_syntax/src/printer.rs
+++ b/dhall_syntax/src/printer.rs
@@ -88,6 +88,7 @@ impl<SE: Display + Clone, E: Display> Display for ExprF<SE, E> {
                 }
                 Ok(())
             })?,
+            Import(a) => a.fmt(f)?,
             Embed(a) => a.fmt(f)?,
         }
         Ok(())
@@ -151,12 +152,14 @@ impl<A: Display + Clone> Expr<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,8 +168,8 @@ impl<A: Display + Clone> Expr<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)),
             ),
             Annot(a, b) => Annot(a.phase(Operator), b),
@@ -175,8 +178,11 @@ impl<A: Display + Clone> Expr<A> {
                 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,
@@ -224,7 +230,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,10 +344,11 @@ 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::*;
+        use ImportMode::*;
         let fmt_remote_path_component = |s: &str| -> String {
             use percent_encoding::{
                 utf8_percent_encode, PATH_SEGMENT_ENCODE_SET,
@@ -417,14 +424,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")?,
@@ -491,9 +490,3 @@ impl<Label: Display> Display for V<Label> {
         Ok(())
     }
 }
-
-impl Display for X {
-    fn fmt(&self, _: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        match *self {}
-    }
-}