Merge branch 'lifetimes'

Closes #55

14 files changed, 398 insertions, 316 deletions

diff --git a/dhall/src/expr.rs b/dhall/src/expr.rs
index 1ce20e3..ab59ce0 100644
--- a/dhall/src/expr.rs
+++ b/dhall/src/expr.rs
@@ -1,15 +1,16 @@
 use crate::imports::ImportRoot;
 use dhall_core::*;
+use std::marker::PhantomData;
 
 macro_rules! derive_other_traits {
     ($ty:ident) => {
-        impl std::cmp::PartialEq for $ty {
+        impl<'a> std::cmp::PartialEq for $ty<'a> {
             fn eq(&self, other: &Self) -> bool {
                 self.0 == other.0
             }
         }
 
-        impl std::fmt::Display for $ty {
+        impl<'a> std::fmt::Display for $ty<'a> {
             fn fmt(
                 &self,
                 f: &mut std::fmt::Formatter,
@@ -21,83 +22,97 @@ macro_rules! derive_other_traits {
 }
 
 #[derive(Debug, Clone, Eq)]
-pub struct Parsed(pub(crate) SubExpr<X, Import>, pub(crate) ImportRoot);
+pub struct Parsed<'a>(
+    pub(crate) SubExpr<Span<'a>, Import>,
+    pub(crate) ImportRoot,
+);
 derive_other_traits!(Parsed);
 
 #[derive(Debug, Clone, Eq)]
-pub struct Resolved(pub(crate) SubExpr<X, Normalized>);
+pub struct Resolved<'a>(pub(crate) SubExpr<Span<'a>, Normalized<'static>>);
 derive_other_traits!(Resolved);
 
 #[derive(Debug, Clone, Eq)]
-pub struct Typed(pub(crate) SubExpr<X, Normalized>, pub(crate) Option<Type>);
+pub struct Typed<'a>(
+    pub(crate) SubExpr<X, Normalized<'static>>,
+    pub(crate) Option<Type<'static>>,
+    pub(crate) PhantomData<&'a ()>,
+);
 derive_other_traits!(Typed);
 
 #[derive(Debug, Clone, Eq)]
-pub struct Normalized(pub(crate) SubExpr<X, X>, pub(crate) Option<Type>);
+pub struct Normalized<'a>(
+    pub(crate) SubExpr<X, X>,
+    pub(crate) Option<Type<'static>>,
+    pub(crate) PhantomData<&'a ()>,
+);
 derive_other_traits!(Normalized);
 
 /// An expression of type `Type` (like `Bool` or `Natural -> Text`, but not `Type`)
 #[derive(Debug, Clone, Eq)]
-pub struct SimpleType(pub(crate) SubExpr<X, X>);
+pub struct SimpleType<'a>(
+    pub(crate) SubExpr<X, X>,
+    pub(crate) PhantomData<&'a ()>,
+);
 derive_other_traits!(SimpleType);
 
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub struct Type(pub(crate) TypeInternal);
+pub struct Type<'a>(pub(crate) TypeInternal<'a>);
 
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub(crate) enum TypeInternal {
-    Expr(Box<Normalized>),
+pub(crate) enum TypeInternal<'a> {
+    Expr(Box<Normalized<'a>>),
     // The type of `Sort`
     SuperType,
 }
 
 // Exposed for the macros
 #[doc(hidden)]
-impl From<SimpleType> for SubExpr<X, X> {
-    fn from(x: SimpleType) -> SubExpr<X, X> {
+impl<'a> From<SimpleType<'a>> for SubExpr<X, X> {
+    fn from(x: SimpleType<'a>) -> SubExpr<X, X> {
         x.0
     }
 }
 
 // Exposed for the macros
 #[doc(hidden)]
-impl From<SubExpr<X, X>> for SimpleType {
-    fn from(x: SubExpr<X, X>) -> SimpleType {
-        SimpleType(x)
+impl<'a> From<SubExpr<X, X>> for SimpleType<'a> {
+    fn from(x: SubExpr<X, X>) -> SimpleType<'a> {
+        SimpleType(x, PhantomData)
     }
 }
 
 // Exposed for the macros
 #[doc(hidden)]
-impl From<Normalized> for Typed {
-    fn from(x: Normalized) -> Typed {
-        Typed(x.0.absurd(), x.1)
+impl<'a> From<Normalized<'a>> for Typed<'a> {
+    fn from(x: Normalized<'a>) -> Typed<'a> {
+        Typed(x.0.absurd(), x.1, x.2)
     }
 }
 
-impl Typed {
-    pub(crate) fn as_expr(&self) -> &SubExpr<X, Normalized> {
+impl<'a> Typed<'a> {
+    pub(crate) fn as_expr(&self) -> &SubExpr<X, Normalized<'a>> {
         &self.0
     }
-    pub(crate) fn into_expr(self) -> SubExpr<X, Normalized> {
+    pub(crate) fn into_expr(self) -> SubExpr<X, Normalized<'a>> {
         self.0
     }
 }
 
-impl Normalized {
+impl<'a> Normalized<'a> {
     pub(crate) fn as_expr(&self) -> &SubExpr<X, X> {
         &self.0
     }
     pub(crate) fn into_expr<T>(self) -> SubExpr<X, T> {
         self.0.absurd()
     }
-    pub(crate) fn into_type(self) -> Type {
+    pub(crate) fn into_type(self) -> Type<'a> {
         crate::expr::Type(TypeInternal::Expr(Box::new(self)))
     }
 }
 
-impl SimpleType {
-    pub(crate) fn into_type(self) -> Type {
-        Normalized(self.0, Some(Type::const_type())).into_type()
+impl<'a> SimpleType<'a> {
+    pub(crate) fn into_type(self) -> Type<'a> {
+        Normalized(self.0, Some(Type::const_type()), PhantomData).into_type()
     }
 }
diff --git a/dhall/src/imports.rs b/dhall/src/imports.rs
index b5546b2..36f0802 100644
--- a/dhall/src/imports.rs
+++ b/dhall/src/imports.rs
@@ -21,7 +21,7 @@ pub enum ImportRoot {
 fn resolve_import(
     import: &Import,
     root: &ImportRoot,
-) -> Result<Normalized, ImportError> {
+) -> Result<Normalized<'static>, ImportError> {
     use self::ImportRoot::*;
     use dhall_core::FilePrefix::*;
     use dhall_core::ImportLocation::*;
@@ -44,53 +44,54 @@ fn resolve_import(
     }
 }
 
-fn load_import(f: &Path) -> Result<Normalized, Error> {
+fn load_import(f: &Path) -> Result<Normalized<'static>, Error> {
     Ok(Parsed::parse_file(f)?.resolve()?.typecheck()?.normalize())
 }
 
-fn resolve_expr(
-    Parsed(expr, root): Parsed,
+fn resolve_expr<'a>(
+    Parsed(expr, root): Parsed<'a>,
     allow_imports: bool,
-) -> Result<Resolved, ImportError> {
-    let resolve = |import: &Import| -> Result<Normalized, ImportError> {
-        if allow_imports {
-            let expr = resolve_import(import, &root)?;
-            Ok(expr)
-        } else {
-            Err(ImportError::UnexpectedImport(import.clone()))
-        }
-    };
+) -> Result<Resolved<'a>, ImportError> {
+    let resolve =
+        |import: &Import| -> Result<Normalized<'static>, ImportError> {
+            if allow_imports {
+                let expr = resolve_import(import, &root)?;
+                Ok(expr)
+            } else {
+                Err(ImportError::UnexpectedImport(import.clone()))
+            }
+        };
     let expr = expr.as_ref().traverse_embed(&resolve)?;
     Ok(Resolved(rc(expr)))
 }
 
-impl Parsed {
-    pub fn parse_file(f: &Path) -> Result<Parsed, Error> {
+impl<'a> Parsed<'a> {
+    pub fn parse_file(f: &Path) -> Result<Parsed<'a>, Error> {
         let mut buffer = String::new();
         File::open(f)?.read_to_string(&mut buffer)?;
         let expr = parse_expr(&*buffer)?;
         let root = ImportRoot::LocalDir(f.parent().unwrap().to_owned());
-        Ok(Parsed(expr, root))
+        Ok(Parsed(expr.unnote().note_absurd(), root))
     }
 
-    pub fn parse_str(s: &str) -> Result<Parsed, Error> {
+    pub fn parse_str(s: &'a str) -> Result<Parsed<'a>, Error> {
         let expr = parse_expr(s)?;
         let root = ImportRoot::LocalDir(std::env::current_dir()?);
         Ok(Parsed(expr, root))
     }
 
-    pub fn parse_binary_file(f: &Path) -> Result<Parsed, Error> {
+    pub fn parse_binary_file(f: &Path) -> Result<Parsed<'a>, Error> {
         let mut buffer = Vec::new();
         File::open(f)?.read_to_end(&mut buffer)?;
         let expr = crate::binary::decode(&buffer)?;
         let root = ImportRoot::LocalDir(f.parent().unwrap().to_owned());
-        Ok(Parsed(expr, root))
+        Ok(Parsed(expr.note_absurd(), root))
     }
 
-    pub fn resolve(self) -> Result<Resolved, ImportError> {
+    pub fn resolve(self) -> Result<Resolved<'a>, ImportError> {
         crate::imports::resolve_expr(self, true)
     }
-    pub fn skip_resolve(self) -> Result<Resolved, ImportError> {
+    pub fn skip_resolve(self) -> Result<Resolved<'a>, ImportError> {
         crate::imports::resolve_expr(self, false)
     }
 }
diff --git a/dhall/src/normalize.rs b/dhall/src/normalize.rs
index 1adc0f8..d6c3805 100644
--- a/dhall/src/normalize.rs
+++ b/dhall/src/normalize.rs
@@ -4,13 +4,17 @@ use dhall_core::*;
 use dhall_generator::dhall_expr;
 use std::fmt;
 
-impl Typed {
-    pub fn normalize(self) -> Normalized {
-        Normalized(normalize(self.0), self.1)
+impl<'a> Typed<'a> {
+    pub fn normalize(self) -> Normalized<'a> {
+        Normalized(normalize(self.0), self.1, self.2)
     }
     /// Pretends this expression is normalized. Use with care.
-    pub fn skip_normalize(self) -> Normalized {
-        Normalized(self.0.unroll().squash_embed(&|e| e.0.clone()), self.1)
+    pub fn skip_normalize(self) -> Normalized<'a> {
+        Normalized(
+            self.0.unroll().squash_embed(&|e| e.0.clone()),
+            self.1,
+            self.2,
+        )
     }
 }
 
@@ -221,11 +225,11 @@ enum WhatNext<'a, S, A> {
     DoneAsIs,
 }
 
-fn normalize_ref(expr: &Expr<X, Normalized>) -> Expr<X, X> {
+fn normalize_ref(expr: &Expr<X, Normalized<'static>>) -> Expr<X, X> {
     use dhall_core::BinOp::*;
     use dhall_core::ExprF::*;
     // Recursively normalize all subexpressions
-    let expr: ExprF<Expr<X, X>, Label, X, Normalized> =
+    let expr: ExprF<Expr<X, X>, Label, X, Normalized<'static>> =
         expr.map_ref_simple(|e| normalize_ref(e.as_ref()));
 
     use WhatNext::*;
@@ -327,7 +331,7 @@ fn normalize_ref(expr: &Expr<X, Normalized>) -> Expr<X, X> {
 /// However, `normalize` will not fail if the expression is ill-typed and will
 /// leave ill-typed sub-expressions unevaluated.
 ///
-fn normalize(e: SubExpr<X, Normalized>) -> SubExpr<X, X> {
+fn normalize(e: SubExpr<X, Normalized<'static>>) -> SubExpr<X, X> {
     normalize_ref(e.as_ref()).roll()
 }
 
diff --git a/dhall/src/tests.rs b/dhall/src/tests.rs
index 798f3e9..14c2a5f 100644
--- a/dhall/src/tests.rs
+++ b/dhall/src/tests.rs
@@ -99,7 +99,8 @@ pub fn run_test(
                 assert_eq_pretty!(expr, expected);
 
                 // Round-trip pretty-printer
-                let expr: Parsed = crate::from_str(&expr.to_string(), None)?;
+                let expr_string = expr.to_string();
+                let expr: Parsed = crate::from_str(&expr_string, None)?;
                 assert_eq!(expr, expected);
 
                 return Ok(());
diff --git a/dhall/src/traits/deserialize.rs b/dhall/src/traits/deserialize.rs
index 1fbdfe1..f1be054 100644
--- a/dhall/src/traits/deserialize.rs
+++ b/dhall/src/traits/deserialize.rs
@@ -5,25 +5,25 @@ pub trait Deserialize<'a>: Sized {
     fn from_str(s: &'a str, ty: Option<&Type>) -> Result<Self>;
 }
 
-impl<'a> Deserialize<'a> for Parsed {
+impl<'de: 'a, 'a> Deserialize<'de> for Parsed<'a> {
     /// Simply parses the provided string. Ignores the
     /// provided type.
-    fn from_str(s: &'a str, _: Option<&Type>) -> Result<Self> {
+    fn from_str(s: &'de str, _: Option<&Type>) -> Result<Self> {
         Ok(Parsed::parse_str(s)?)
     }
 }
 
-impl<'a> Deserialize<'a> for Resolved {
+impl<'de: 'a, 'a> Deserialize<'de> for Resolved<'a> {
     /// Parses and resolves the provided string. Ignores the
     /// provided type.
-    fn from_str(s: &'a str, ty: Option<&Type>) -> Result<Self> {
+    fn from_str(s: &'de str, ty: Option<&Type>) -> Result<Self> {
         Ok(Parsed::from_str(s, ty)?.resolve()?)
     }
 }
 
-impl<'a> Deserialize<'a> for Typed {
+impl<'de: 'a, 'a> Deserialize<'de> for Typed<'a> {
     /// Parses, resolves and typechecks the provided string.
-    fn from_str(s: &'a str, ty: Option<&Type>) -> Result<Self> {
+    fn from_str(s: &'de str, ty: Option<&Type>) -> Result<Self> {
         let resolved = Resolved::from_str(s, ty)?;
         match ty {
             None => Ok(resolved.typecheck()?),
@@ -32,15 +32,15 @@ impl<'a> Deserialize<'a> for Typed {
     }
 }
 
-impl<'a> Deserialize<'a> for Normalized {
+impl<'de: 'a, 'a> Deserialize<'de> for Normalized<'a> {
     /// Parses, resolves, typechecks and normalizes the provided string.
-    fn from_str(s: &'a str, ty: Option<&Type>) -> Result<Self> {
+    fn from_str(s: &'de str, ty: Option<&Type>) -> Result<Self> {
         Ok(Typed::from_str(s, ty)?.normalize())
     }
 }
 
-impl<'a> Deserialize<'a> for Type {
-    fn from_str(s: &'a str, ty: Option<&Type>) -> Result<Self> {
+impl<'de: 'a, 'a> Deserialize<'de> for Type<'a> {
+    fn from_str(s: &'de str, ty: Option<&Type>) -> Result<Self> {
         Ok(Normalized::from_str(s, ty)?.into_type())
     }
 }
diff --git a/dhall/src/traits/dynamic_type.rs b/dhall/src/traits/dynamic_type.rs
index d03f8cd..28ed76d 100644
--- a/dhall/src/traits/dynamic_type.rs
+++ b/dhall/src/traits/dynamic_type.rs
@@ -6,17 +6,17 @@ use dhall_core::{Const, ExprF};
 use std::borrow::Cow;
 
 pub trait DynamicType {
-    fn get_type<'a>(&'a self) -> Result<Cow<'a, Type>, TypeError>;
+    fn get_type<'a>(&'a self) -> Result<Cow<'a, Type<'static>>, TypeError>;
 }
 
 impl<T: StaticType> DynamicType for T {
-    fn get_type<'a>(&'a self) -> Result<Cow<'a, Type>, TypeError> {
+    fn get_type<'a>(&'a self) -> Result<Cow<'a, Type<'static>>, TypeError> {
         Ok(Cow::Owned(T::get_static_type()))
     }
 }
 
-impl DynamicType for Type {
-    fn get_type(&self) -> Result<Cow<'_, Type>, TypeError> {
+impl<'a> DynamicType for Type<'a> {
+    fn get_type(&self) -> Result<Cow<'_, Type<'static>>, TypeError> {
         use TypeInternal::*;
         match &self.0 {
             Expr(e) => e.get_type(),
@@ -29,8 +29,8 @@ impl DynamicType for Type {
     }
 }
 
-impl DynamicType for Normalized {
-    fn get_type(&self) -> Result<Cow<'_, Type>, TypeError> {
+impl<'a> DynamicType for Normalized<'a> {
+    fn get_type(&self) -> Result<Cow<'_, Type<'static>>, TypeError> {
         match &self.1 {
             Some(t) => Ok(Cow::Borrowed(t)),
             None => Err(TypeError::new(
@@ -42,8 +42,8 @@ impl DynamicType for Normalized {
     }
 }
 
-impl DynamicType for Typed {
-    fn get_type(&self) -> Result<Cow<'_, Type>, TypeError> {
+impl<'a> DynamicType for Typed<'a> {
+    fn get_type(&self) -> Result<Cow<'_, Type<'static>>, TypeError> {
         match &self.1 {
             Some(t) => Ok(Cow::Borrowed(t)),
             None => Err(TypeError::new(
diff --git a/dhall/src/traits/static_type.rs b/dhall/src/traits/static_type.rs
index 6b0f5c5..35d91e1 100644
--- a/dhall/src/traits/static_type.rs
+++ b/dhall/src/traits/static_type.rs
@@ -3,7 +3,7 @@ use dhall_core::*;
 use dhall_generator::*;
 
 pub trait StaticType {
-    fn get_static_type() -> Type;
+    fn get_static_type() -> Type<'static>;
 }
 
 /// Trait for rust types that can be represented in dhall in
@@ -12,79 +12,80 @@ pub trait StaticType {
 /// is `HashMap<Text, bool>` because dhall cannot represent records with a
 /// variable number of fields.
 pub trait SimpleStaticType {
-    fn get_simple_static_type() -> SimpleType;
+    fn get_simple_static_type<'a>() -> SimpleType<'a>;
 }
 
-fn mktype(x: SubExpr<X, X>) -> SimpleType {
-    SimpleType(x)
+fn mktype<'a>(x: SubExpr<X, X>) -> SimpleType<'a> {
+    SimpleType(x, std::marker::PhantomData)
 }
 
 impl<T: SimpleStaticType> StaticType for T {
-    fn get_static_type() -> Type {
+    fn get_static_type() -> Type<'static> {
         crate::expr::Normalized(
             T::get_simple_static_type().into(),
             Some(Type::const_type()),
+            std::marker::PhantomData,
         )
         .into_type()
     }
 }
 
-impl StaticType for SimpleType {
-    fn get_static_type() -> Type {
+impl<'a> StaticType for SimpleType<'a> {
+    fn get_static_type() -> Type<'static> {
         Type::const_type()
     }
 }
 
 impl SimpleStaticType for bool {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         mktype(dhall_expr!(Bool))
     }
 }
 
 impl SimpleStaticType for Natural {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         mktype(dhall_expr!(Natural))
     }
 }
 
 impl SimpleStaticType for u32 {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         mktype(dhall_expr!(Natural))
     }
 }
 
 impl SimpleStaticType for u64 {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         mktype(dhall_expr!(Natural))
     }
 }
 
 impl SimpleStaticType for Integer {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         mktype(dhall_expr!(Integer))
     }
 }
 
 impl SimpleStaticType for i32 {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         mktype(dhall_expr!(Integer))
     }
 }
 
 impl SimpleStaticType for i64 {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         mktype(dhall_expr!(Integer))
     }
 }
 
 impl SimpleStaticType for String {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         mktype(dhall_expr!(Text))
     }
 }
 
 impl<A: SimpleStaticType, B: SimpleStaticType> SimpleStaticType for (A, B) {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         let ta: SubExpr<_, _> = A::get_simple_static_type().into();
         let tb: SubExpr<_, _> = B::get_simple_static_type().into();
         mktype(dhall_expr!({ _1: ta, _2: tb }))
@@ -92,27 +93,27 @@ impl<A: SimpleStaticType, B: SimpleStaticType> SimpleStaticType for (A, B) {
 }
 
 impl<T: SimpleStaticType> SimpleStaticType for Option<T> {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         let t: SubExpr<_, _> = T::get_simple_static_type().into();
         mktype(dhall_expr!(Optional t))
     }
 }
 
 impl<T: SimpleStaticType> SimpleStaticType for Vec<T> {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         let t: SubExpr<_, _> = T::get_simple_static_type().into();
         mktype(dhall_expr!(List t))
     }
 }
 
-impl<'a, T: SimpleStaticType> SimpleStaticType for &'a T {
-    fn get_simple_static_type() -> SimpleType {
+impl<'b, T: SimpleStaticType> SimpleStaticType for &'b T {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         T::get_simple_static_type()
     }
 }
 
 impl<T> SimpleStaticType for std::marker::PhantomData<T> {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         mktype(dhall_expr!({}))
     }
 }
@@ -120,7 +121,7 @@ impl<T> SimpleStaticType for std::marker::PhantomData<T> {
 impl<T: SimpleStaticType, E: SimpleStaticType> SimpleStaticType
     for std::result::Result<T, E>
 {
-    fn get_simple_static_type() -> SimpleType {
+    fn get_simple_static_type<'a>() -> SimpleType<'a> {
         let tt: SubExpr<_, _> = T::get_simple_static_type().into();
         let te: SubExpr<_, _> = E::get_simple_static_type().into();
         mktype(dhall_expr!(< Ok: tt | Err: te>))
diff --git a/dhall/src/typecheck.rs b/dhall/src/typecheck.rs
index 4881972..5a28089 100644
--- a/dhall/src/typecheck.rs
+++ b/dhall/src/typecheck.rs
@@ -1,6 +1,7 @@
 #![allow(non_snake_case)]
 use std::borrow::Borrow;
 use std::fmt;
+use std::marker::PhantomData;
 
 use crate::expr::*;
 use crate::traits::DynamicType;
@@ -11,22 +12,25 @@ use dhall_generator as dhall;
 
 use self::TypeMessage::*;
 
-impl Resolved {
-    pub fn typecheck(self) -> Result<Typed, TypeError> {
-        type_of(self.0.clone())
+impl<'a> Resolved<'a> {
+    pub fn typecheck(self) -> Result<Typed<'static>, TypeError> {
+        type_of(self.0.unnote())
     }
-    pub fn typecheck_with(self, ty: &Type) -> Result<Typed, TypeError> {
-        let expr: SubExpr<_, _> = self.0.clone();
+    pub fn typecheck_with(
+        self,
+        ty: &Type,
+    ) -> Result<Typed<'static>, TypeError> {
+        let expr: SubExpr<_, _> = self.0.unnote();
         let ty: SubExpr<_, _> = ty.as_normalized()?.as_expr().absurd();
         type_of(dhall::subexpr!(expr: ty))
     }
     /// Pretends this expression has been typechecked. Use with care.
-    pub fn skip_typecheck(self) -> Typed {
-        Typed(self.0, None)
+    pub fn skip_typecheck(self) -> Typed<'a> {
+        Typed(self.0.unnote(), None, PhantomData)
     }
 }
-impl Typed {
-    fn get_type_move(self) -> Result<Type, TypeError> {
+impl<'a> Typed<'a> {
+    fn get_type_move(self) -> Result<Type<'static>, TypeError> {
         self.1.ok_or(TypeError::new(
             &Context::new(),
             self.0,
@@ -34,18 +38,18 @@ impl Typed {
         ))
     }
 }
-impl Normalized {
+impl<'a> Normalized<'a> {
     // Expose the outermost constructor
     fn unroll_ref(&self) -> &Expr<X, X> {
         self.as_expr().as_ref()
     }
     fn shift(&self, delta: isize, var: &V<Label>) -> Self {
         // shift the type too ?
-        Normalized(shift(delta, var, &self.0), self.1.clone())
+        Normalized(shift(delta, var, &self.0), self.1.clone(), self.2)
     }
 }
-impl Type {
-    pub fn as_normalized(&self) -> Result<&Normalized, TypeError> {
+impl<'a> Type<'a> {
+    pub fn as_normalized(&self) -> Result<&Normalized<'a>, TypeError> {
         use TypeInternal::*;
         match &self.0 {
             Expr(e) => Ok(e),
@@ -56,7 +60,7 @@ impl Type {
             )),
         }
     }
-    pub(crate) fn into_normalized(self) -> Result<Normalized, TypeError> {
+    pub(crate) fn into_normalized(self) -> Result<Normalized<'a>, TypeError> {
         use TypeInternal::*;
         match self.0 {
             Expr(e) => Ok(*e),
@@ -83,16 +87,25 @@ impl Type {
         Normalized(
             rc(ExprF::Const(Const::Sort)),
             Some(Type(TypeInternal::SuperType)),
+            PhantomData,
         )
         .into_type()
     }
     pub fn const_kind() -> Self {
-        Normalized(rc(ExprF::Const(Const::Kind)), Some(Type::const_sort()))
-            .into_type()
+        Normalized(
+            rc(ExprF::Const(Const::Kind)),
+            Some(Type::const_sort()),
+            PhantomData,
+        )
+        .into_type()
     }
     pub fn const_type() -> Self {
-        Normalized(rc(ExprF::Const(Const::Type)), Some(Type::const_kind()))
-            .into_type()
+        Normalized(
+            rc(ExprF::Const(Const::Type)),
+            Some(Type::const_kind()),
+            PhantomData,
+        )
+        .into_type()
     }
 }
 
@@ -129,8 +142,8 @@ fn match_vars(vl: &V<Label>, vr: &V<Label>, ctx: &[(Label, Label)]) -> bool {
 // Equality up to alpha-equivalence (renaming of bound variables)
 fn prop_equal<T, U>(eL0: T, eR0: U) -> bool
 where
-    T: Borrow<Type>,
-    U: Borrow<Type>,
+    T: Borrow<Type<'static>>,
+    U: Borrow<Type<'static>>,
 {
     use dhall_core::ExprF::*;
     fn go<S, T>(
@@ -197,7 +210,7 @@ where
     }
 }
 
-fn type_of_builtin<S>(b: Builtin) -> Expr<S, Normalized> {
+fn type_of_builtin<S>(b: Builtin) -> Expr<S, Normalized<'static>> {
     use dhall_core::Builtin::*;
     match b {
         Bool | Natural | Integer | Double | Text => dhall::expr!(Type),
@@ -294,23 +307,24 @@ macro_rules! ensure_is_const {
 /// Type-check an expression and return the expression alongside its type
 /// if type-checking succeeded, or an error if type-checking failed
 pub fn type_with(
-    ctx: &Context<Label, Type>,
-    e: SubExpr<X, Normalized>,
-) -> Result<Typed, TypeError> {
+    ctx: &Context<Label, Type<'static>>,
+    e: SubExpr<X, Normalized<'static>>,
+) -> Result<Typed<'static>, TypeError> {
     use dhall_core::BinOp::*;
     use dhall_core::Const::*;
     use dhall_core::ExprF::*;
-    let mkerr = |msg: TypeMessage| TypeError::new(ctx, e.clone(), msg);
+    let mkerr = |msg: TypeMessage<'static>| TypeError::new(ctx, e.clone(), msg);
 
-    let mktype = |ctx, x: SubExpr<X, Normalized>| {
+    let mktype = |ctx, x: SubExpr<X, Normalized<'static>>| {
         Ok(type_with(ctx, x)?.normalize().into_type())
     };
 
-    let mksimpletype = |x: SubExpr<X, X>| SimpleType(x).into_type();
+    let mksimpletype =
+        |x: SubExpr<X, X>| SimpleType(x, PhantomData).into_type();
 
     enum Ret {
-        RetType(crate::expr::Type),
-        RetExpr(Expr<X, Normalized>),
+        RetType(crate::expr::Type<'static>),
+        RetExpr(Expr<X, Normalized<'static>>),
     }
     use Ret::*;
     let ret = match e.as_ref() {
@@ -418,6 +432,7 @@ pub fn type_with(
                         mkerr(NotAFunction(Typed(
                             rc(App(f.into_expr(), seen_args)),
                             Some(tf),
+                            PhantomData
                         )))
                     );
                     let tx = mktype(ctx, tx.absurd())?;
@@ -425,7 +440,11 @@ pub fn type_with(
                         &tx,
                         a.get_type()?,
                         mkerr(TypeMismatch(
-                            Typed(rc(App(f.into_expr(), seen_args)), Some(tf)),
+                            Typed(
+                                rc(App(f.into_expr(), seen_args)),
+                                Some(tf),
+                                PhantomData
+                            ),
                             tx.into_normalized()?,
                             a,
                         ))
@@ -592,15 +611,17 @@ pub fn type_with(
         },
     }?;
     match ret {
-        RetExpr(ret) => Ok(Typed(e, Some(mktype(ctx, rc(ret))?))),
-        RetType(typ) => Ok(Typed(e, Some(typ))),
+        RetExpr(ret) => Ok(Typed(e, Some(mktype(ctx, rc(ret))?), PhantomData)),
+        RetType(typ) => Ok(Typed(e, Some(typ), PhantomData)),
     }
 }
 
 /// `typeOf` is the same as `type_with` with an empty context, meaning that the
 /// expression must be closed (i.e. no free variables), otherwise type-checking
 /// will fail.
-pub fn type_of(e: SubExpr<X, Normalized>) -> Result<Typed, TypeError> {
+pub fn type_of(
+    e: SubExpr<X, Normalized<'static>>,
+) -> Result<Typed<'static>, TypeError> {
     let ctx = Context::new();
     let e = type_with(&ctx, e)?;
     // Ensure the inferred type isn't SuperType
@@ -610,45 +631,45 @@ pub fn type_of(e: SubExpr<X, Normalized>) -> Result<Typed, TypeError> {
 
 /// The specific type error
 #[derive(Debug)]
-pub enum TypeMessage {
+pub enum TypeMessage<'a> {
     UnboundVariable,
-    InvalidInputType(Normalized),
-    InvalidOutputType(Normalized),
-    NotAFunction(Typed),
-    TypeMismatch(Typed, Normalized, Typed),
-    AnnotMismatch(Typed, Normalized),
+    InvalidInputType(Normalized<'a>),
+    InvalidOutputType(Normalized<'a>),
+    NotAFunction(Typed<'a>),
+    TypeMismatch(Typed<'a>, Normalized<'a>, Typed<'a>),
+    AnnotMismatch(Typed<'a>, Normalized<'a>),
     Untyped,
-    InvalidListElement(usize, Normalized, Typed),
-    InvalidListType(Normalized),
-    InvalidOptionalType(Normalized),
-    InvalidPredicate(Typed),
-    IfBranchMismatch(Typed, Typed),
-    IfBranchMustBeTerm(bool, Typed),
-    InvalidField(Label, Typed),
-    InvalidFieldType(Label, Typed),
+    InvalidListElement(usize, Normalized<'a>, Typed<'a>),
+    InvalidListType(Normalized<'a>),
+    InvalidOptionalType(Normalized<'a>),
+    InvalidPredicate(Typed<'a>),
+    IfBranchMismatch(Typed<'a>, Typed<'a>),
+    IfBranchMustBeTerm(bool, Typed<'a>),
+    InvalidField(Label, Typed<'a>),
+    InvalidFieldType(Label, Typed<'a>),
     DuplicateAlternative(Label),
     FieldCollision(Label),
-    NotARecord(Label, Typed),
-    MissingField(Label, Typed),
-    BinOpTypeMismatch(BinOp, Typed),
-    NoDependentLet(Normalized, Normalized),
-    NoDependentTypes(Normalized, Normalized),
+    NotARecord(Label, Typed<'a>),
+    MissingField(Label, Typed<'a>),
+    BinOpTypeMismatch(BinOp, Typed<'a>),
+    NoDependentLet(Normalized<'a>, Normalized<'a>),
+    NoDependentTypes(Normalized<'a>, Normalized<'a>),
     Unimplemented,
 }
 
 /// A structured type error that includes context
 #[derive(Debug)]
 pub struct TypeError {
-    pub context: Context<Label, Type>,
-    pub current: SubExpr<X, Normalized>,
-    pub type_message: TypeMessage,
+    pub context: Context<Label, Type<'static>>,
+    pub current: SubExpr<X, Normalized<'static>>,
+    pub type_message: TypeMessage<'static>,
 }
 
 impl TypeError {
     pub fn new(
-        context: &Context<Label, Type>,
-        current: SubExpr<X, Normalized>,
-        type_message: TypeMessage,
+        context: &Context<Label, Type<'static>>,
+        current: SubExpr<X, Normalized<'static>>,
+        type_message: TypeMessage<'static>,
     ) -> Self {
         TypeError {
             context: context.clone(),
@@ -658,7 +679,7 @@ impl TypeError {
     }
 }
 
-impl ::std::error::Error for TypeMessage {
+impl ::std::error::Error for TypeMessage<'static> {
     fn description(&self) -> &str {
         match *self {
             UnboundVariable => "Unbound variable",
@@ -671,7 +692,7 @@ impl ::std::error::Error for TypeMessage {
     }
 }
 
-impl fmt::Display for TypeMessage {
+impl fmt::Display for TypeMessage<'static> {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         match self {
             UnboundVariable => {
diff --git a/dhall/tests/traits.rs b/dhall/tests/traits.rs
index 1e9b3c2..ef3e385 100644
--- a/dhall/tests/traits.rs
+++ b/dhall/tests/traits.rs
@@ -5,7 +5,7 @@ use dhall_generator::dhall_expr;
 
 #[test]
 fn test_static_type() {
-    fn mktype(x: SubExpr<X, X>) -> dhall::expr::SimpleType {
+    fn mktype(x: SubExpr<X, X>) -> dhall::expr::SimpleType<'static> {
         x.into()
     }
 
diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index d2ecf53..5b138b8 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -296,7 +296,7 @@ impl<S, A> Expr<S, A> {
         let recurse = |e: &SubExpr<S, A>| -> Result<SubExpr<S, B>, Err> {
             Ok(e.as_ref().traverse_embed(map_embed)?.roll())
         };
-        self.as_ref().traverse(
+        self.traverse_ref(
             |e| recurse(e),
             |_, e| recurse(e),
             |x| Ok(S::clone(x)),
@@ -331,8 +331,8 @@ impl<N: Clone, E> Expr<N, E> {
     ) -> SubExpr<N, E2> {
         match self.as_ref() {
             ExprF::Embed(e) => f(e),
-            e => e
-                .map(
+            _ => self
+                .map_ref(
                     |e| e.as_ref().squash_embed(f),
                     |_, e| e.as_ref().squash_embed(f),
                     N::clone,
@@ -392,8 +392,8 @@ impl<SE, L, N, E> ExprF<SE, L, N, E> {
         }
     }
 
-    pub fn traverse<SE2, L2, N2, E2, Err, F1, F2, F3, F4, F5>(
-        self,
+    fn traverse_ref<'a, SE2, L2, N2, E2, Err, F1, F2, F3, F4, F5>(
+        &'a self,
         map_subexpr: F1,
         map_under_binder: F2,
         map_note: F3,
@@ -403,21 +403,21 @@ impl<SE, L, N, E> ExprF<SE, L, N, E> {
     where
         L: Ord,
         L2: Ord,
-        F1: FnMut(SE) -> Result<SE2, Err>,
-        F2: FnOnce(&L, SE) -> Result<SE2, Err>,
-        F3: FnOnce(N) -> Result<N2, Err>,
-        F4: FnOnce(E) -> Result<E2, Err>,
-        F5: FnMut(L) -> Result<L2, Err>,
+        F1: FnMut(&'a SE) -> Result<SE2, Err>,
+        F2: FnOnce(&'a L, &'a SE) -> Result<SE2, Err>,
+        F3: FnOnce(&'a N) -> Result<N2, Err>,
+        F4: FnOnce(&'a E) -> Result<E2, Err>,
+        F5: FnMut(&'a L) -> Result<L2, Err>,
     {
         let mut map = map_subexpr;
-        fn vec<T, U, Err, F: FnMut(T) -> Result<U, Err>>(
-            x: Vec<T>,
+        fn vec<'a, T, U, Err, F: FnMut(&'a T) -> Result<U, Err>>(
+            x: &'a Vec<T>,
             f: F,
         ) -> Result<Vec<U>, Err> {
-            x.into_iter().map(f).collect()
+            x.iter().map(f).collect()
         }
-        fn opt<T, U, Err, F: FnOnce(T) -> Result<U, Err>>(
-            x: Option<T>,
+        fn opt<'a, T, U, Err, F: FnOnce(&'a T) -> Result<U, Err>>(
+            x: &'a Option<T>,
             f: F,
         ) -> Result<Option<U>, Err> {
             Ok(match x {
@@ -425,23 +425,23 @@ impl<SE, L, N, E> ExprF<SE, L, N, E> {
                 None => None,
             })
         }
-        fn btmap<K, L, T, U, Err, FK, FV>(
-            x: BTreeMap<K, T>,
+        fn btmap<'a, K, L, T, U, Err, FK, FV>(
+            x: &'a BTreeMap<K, T>,
             mut fk: FK,
             mut fv: FV,
         ) -> Result<BTreeMap<L, U>, Err>
         where
             K: Ord,
             L: Ord,
-            FK: FnMut(K) -> Result<L, Err>,
-            FV: FnMut(T) -> Result<U, Err>,
+            FK: FnMut(&'a K) -> Result<L, Err>,
+            FV: FnMut(&'a T) -> Result<U, Err>,
         {
             x.into_iter().map(|(k, v)| Ok((fk(k)?, fv(v)?))).collect()
         }
 
         use crate::ExprF::*;
         Ok(match self {
-            Var(V(l, n)) => Var(V(map_label(l)?, n)),
+            Var(V(l, n)) => Var(V(map_label(l)?, *n)),
             Lam(l, t, b) => {
                 let b = map_under_binder(&l, b)?;
                 Lam(map_label(l)?, map(t)?, b)
@@ -456,14 +456,14 @@ impl<SE, L, N, E> ExprF<SE, L, N, E> {
             }
             App(f, args) => App(map(f)?, vec(args, map)?),
             Annot(x, t) => Annot(map(x)?, map(t)?),
-            Const(k) => Const(k),
-            Builtin(v) => Builtin(v),
-            BoolLit(b) => BoolLit(b),
-            NaturalLit(n) => NaturalLit(n),
-            IntegerLit(n) => IntegerLit(n),
-            DoubleLit(n) => DoubleLit(n),
-            TextLit(t) => TextLit(t.traverse(map)?),
-            BinOp(o, x, y) => BinOp(o, map(x)?, map(y)?),
+            Const(k) => Const(*k),
+            Builtin(v) => Builtin(*v),
+            BoolLit(b) => BoolLit(*b),
+            NaturalLit(n) => NaturalLit(*n),
+            IntegerLit(n) => IntegerLit(*n),
+            DoubleLit(n) => DoubleLit(*n),
+            TextLit(t) => TextLit(t.traverse_ref(map)?),
+            BinOp(o, x, y) => BinOp(*o, map(x)?, map(y)?),
             BoolIf(b, t, f) => BoolIf(map(b)?, map(t)?, map(f)?),
             EmptyListLit(t) => EmptyListLit(map(t)?),
             NEListLit(es) => NEListLit(vec(es, map)?),
@@ -483,8 +483,8 @@ impl<SE, L, N, E> ExprF<SE, L, N, E> {
         })
     }
 
-    pub fn map<SE2, L2, N2, E2, F1, F2, F3, F4, F5>(
-        self,
+    pub fn map_ref<'a, SE2, L2, N2, E2, F1, F2, F3, F4, F5>(
+        &'a self,
         mut map_subexpr: F1,
         map_under_binder: F2,
         map_note: F3,
@@ -494,13 +494,13 @@ impl<SE, L, N, E> ExprF<SE, L, N, E> {
     where
         L: Ord,
         L2: Ord,
-        F1: FnMut(SE) -> SE2,
-        F2: FnOnce(&L, SE) -> SE2,
-        F3: FnOnce(N) -> N2,
-        F4: FnOnce(E) -> E2,
-        F5: FnMut(L) -> L2,
+        F1: FnMut(&'a SE) -> SE2,
+        F2: FnOnce(&'a L, &'a SE) -> SE2,
+        F3: FnOnce(&'a N) -> N2,
+        F4: FnOnce(&'a E) -> E2,
+        F5: FnMut(&'a L) -> L2,
     {
-        trivial_result(self.traverse(
+        trivial_result(self.traverse_ref(
             |x| Ok(map_subexpr(x)),
             |l, x| Ok(map_under_binder(l, x)),
             |x| Ok(map_note(x)),
@@ -509,33 +509,6 @@ impl<SE, L, N, E> ExprF<SE, L, N, E> {
         ))
     }
 
-    pub fn map_ref<'a, SE2, L2, N2, E2, F1, F2, F3, F4, F5>(
-        &'a self,
-        map_subexpr: F1,
-        map_under_binder: F2,
-        map_note: F3,
-        map_embed: F4,
-        map_label: F5,
-    ) -> ExprF<SE2, L2, N2, E2>
-    where
-        L: Ord,
-        L2: Ord,
-        F1: FnMut(&'a SE) -> SE2,
-        F2: FnOnce(&'a L, &'a SE) -> SE2,
-        F3: FnOnce(&'a N) -> N2,
-        F4: FnOnce(&'a E) -> E2,
-        F5: FnMut(&'a L) -> L2,
-    {
-        // Not optimal: reallocates all the Vecs and BTreeMaps for nothing.
-        self.as_ref().map(
-            map_subexpr,
-            |l, e| map_under_binder(*l, e),
-            map_note,
-            map_embed,
-            map_label,
-        )
-    }
-
     pub fn map_ref_simple<'a, SE2, F1>(
         &'a self,
         map_subexpr: F1,
@@ -567,7 +540,7 @@ impl<SE, L, N, E> ExprF<SE, L, N, E> {
         E: Clone,
         F1: Fn(&'a SE) -> Result<SE2, Err>,
     {
-        self.as_ref().traverse(
+        self.traverse_ref(
             &map_subexpr,
             |_, e| map_subexpr(e),
             |x| Ok(N::clone(x)),
@@ -670,6 +643,39 @@ impl<N: Clone> SubExpr<N, X> {
     }
 }
 
+impl<E: Clone> SubExpr<X, E> {
+    pub fn note_absurd<N>(&self) -> SubExpr<N, E> {
+        rc(self.as_ref().map_ref(
+            |e| e.note_absurd(),
+            |_, e| e.note_absurd(),
+            |_| unreachable!(),
+            E::clone,
+            Label::clone,
+        ))
+    }
+}
+
+impl<E: Clone> Expr<X, E> {
+    pub fn note_absurd<N: Clone>(&self) -> Expr<N, E> {
+        self.roll().note_absurd().unroll()
+    }
+}
+
+impl<N: Clone, E: Clone> SubExpr<N, E> {
+    pub fn unnote(&self) -> SubExpr<X, E> {
+        match self.as_ref() {
+            ExprF::Note(_, e) => e.unnote(),
+            e => rc(e.map_ref(
+                |e| e.unnote(),
+                |_, e| e.unnote(),
+                |_| unreachable!(),
+                E::clone,
+                Label::clone,
+            )),
+        }
+    }
+}
+
 impl<N: Clone> Expr<N, X> {
     // This is all very sad and I hope this can be avoided sometime
     pub fn absurd_rec<T>(&self) -> Expr<N, T> {
diff --git a/dhall_core/src/parser.rs b/dhall_core/src/parser.rs
index 888f29e..62135a3 100644
--- a/dhall_core/src/parser.rs
+++ b/dhall_core/src/parser.rs
@@ -1,6 +1,7 @@
 use itertools::Itertools;
 use pest::iterators::Pair;
 use pest::Parser;
+pub use pest::Span;
 use std::collections::BTreeMap;
 use std::path::PathBuf;
 
@@ -15,15 +16,24 @@ use crate::*;
 
 use crate::ExprF::*;
 
-type ParsedExpr = Expr<X, Import>;
-type ParsedSubExpr = SubExpr<X, Import>;
-type ParsedText = InterpolatedText<SubExpr<X, Import>>;
-type ParsedTextContents = InterpolatedTextContents<SubExpr<X, Import>>;
+type ParsedExpr<'a> = Expr<Span<'a>, Import>;
+type ParsedSubExpr<'a> = SubExpr<Span<'a>, Import>;
+type ParsedText<'a> = InterpolatedText<SubExpr<Span<'a>, Import>>;
+type ParsedTextContents<'a> =
+    InterpolatedTextContents<SubExpr<Span<'a>, Import>>;
 
 pub type ParseError = pest::error::Error<Rule>;
 
 pub type ParseResult<T> = Result<T, ParseError>;
 
+fn rc<'a>(x: ParsedExpr<'a>) -> ParsedSubExpr<'a> {
+    crate::rc(x)
+}
+
+fn spanned<'a>(span: Span<'a>, x: ParsedExpr<'a>) -> ParsedExpr<'a> {
+    Note(span, rc(x))
+}
+
 #[derive(Debug)]
 enum Either<A, B> {
     Left(A),
@@ -170,6 +180,27 @@ macro_rules! make_parser {
     (@body,
         $pair:expr,
         $children:expr,
+        rule!(
+            $name:ident<$o:ty>
+            as $group:ident;
+            $span:ident;
+            $($args:tt)*
+        )
+    ) => ({
+        let $span = $pair.as_span();
+        make_parser!(@body,
+            $pair,
+            $children,
+            rule!(
+                $name<$o>
+                as $group;
+                $($args)*
+            )
+        )
+    });
+    (@body,
+        $pair:expr,
+        $children:expr,
         token_rule!($name:ident<$o:ty>)
     ) => ({
         Ok(ParsedValue::$name(()))
@@ -289,13 +320,13 @@ make_parser! {
         },
     ));
 
-    rule!(double_quote_literal<ParsedText>; children!(
+    rule!(double_quote_literal<ParsedText<'a>>; children!(
         [double_quote_chunk(chunks)..] => {
             chunks.collect()
         }
     ));
 
-    rule!(double_quote_chunk<ParsedTextContents>; children!(
+    rule!(double_quote_chunk<ParsedTextContents<'a>>; children!(
         [interpolation(e)] => {
             InterpolatedTextContents::Expr(rc(e))
         },
@@ -332,7 +363,7 @@ make_parser! {
         captured_str!(s) => s
     );
 
-    rule!(single_quote_literal<ParsedText>; children!(
+    rule!(single_quote_literal<ParsedText<'a>>; children!(
         [single_quote_continue(lines)] => {
             let space = InterpolatedTextContents::Text(" ".to_owned());
             let newline = InterpolatedTextContents::Text("\n".to_owned());
@@ -362,11 +393,11 @@ make_parser! {
     rule!(escaped_interpolation<&'a str>;
         captured_str!(_) => "${"
     );
-    rule!(interpolation<ParsedExpr>; children!(
+    rule!(interpolation<ParsedExpr<'a>>; children!(
         [expression(e)] => e
     ));
 
-    rule!(single_quote_continue<Vec<Vec<ParsedTextContents>>>; children!(
+    rule!(single_quote_continue<Vec<Vec<ParsedTextContents<'a>>>>; children!(
         [interpolation(c), single_quote_continue(lines)] => {
             let c = InterpolatedTextContents::Expr(rc(c));
             let mut lines = lines;
@@ -540,18 +571,18 @@ make_parser! {
 
     token_rule!(Text<()>);
 
-    rule!(import<ParsedExpr> as expression; children!(
+    rule!(import<ParsedExpr<'a>> as expression; span; children!(
         [import_hashed(location_hashed)] => {
-            Embed(Import {
+            spanned(span, Embed(Import {
                 mode: ImportMode::Code,
                 location_hashed
-            })
+            }))
         },
         [import_hashed(location_hashed), Text(_)] => {
-            Embed(Import {
+            spanned(span, Embed(Import {
                 mode: ImportMode::RawText,
                 location_hashed
-            })
+            }))
         },
     ));
 
@@ -562,13 +593,13 @@ make_parser! {
     token_rule!(if_<()>);
     token_rule!(in_<()>);
 
-    rule!(expression<ParsedExpr> as expression; children!(
+    rule!(expression<ParsedExpr<'a>> as expression; span; children!(
         [lambda(()), nonreserved_label(l), expression(typ),
                 arrow(()), expression(body)] => {
-            Lam(l, rc(typ), rc(body))
+            spanned(span, Lam(l, rc(typ), rc(body)))
         },
         [if_(()), expression(cond), expression(left), expression(right)] => {
-            BoolIf(rc(cond), rc(left), rc(right))
+            spanned(span, BoolIf(rc(cond), rc(left), rc(right)))
         },
         [let_binding(bindings).., in_(()), expression(final_expr)] => {
             bindings.fold(
@@ -578,21 +609,22 @@ make_parser! {
         },
         [forall(()), nonreserved_label(l), expression(typ),
                 arrow(()), expression(body)] => {
-            Pi(l, rc(typ), rc(body))
+            spanned(span, Pi(l, rc(typ), rc(body)))
         },
         [expression(typ), arrow(()), expression(body)] => {
-            Pi("_".into(), rc(typ), rc(body))
+            spanned(span, Pi("_".into(), rc(typ), rc(body)))
         },
         [merge(()), expression(x), expression(y), expression(z)] => {
-            Merge(rc(x), rc(y), Option::Some(rc(z)))
+            spanned(span, Merge(rc(x), rc(y), Option::Some(rc(z))))
         },
         [merge(()), expression(x), expression(y)] => {
-            Merge(rc(x), rc(y), Option::None)
+            spanned(span, Merge(rc(x), rc(y), Option::None))
         },
         [expression(e)] => e,
     ));
 
-    rule!(let_binding<(Label, Option<ParsedSubExpr>, ParsedSubExpr)>; children!(
+    rule!(let_binding<(Label, Option<ParsedSubExpr<'a>>, ParsedSubExpr<'a>)>;
+            children!(
         [nonreserved_label(name), expression(annot), expression(expr)] =>
             (name, Option::Some(rc(annot)), rc(expr)),
         [nonreserved_label(name), expression(expr)] =>
@@ -602,99 +634,99 @@ make_parser! {
     token_rule!(List<()>);
     token_rule!(Optional<()>);
 
-    rule!(empty_collection<ParsedExpr> as expression; children!(
+    rule!(empty_collection<ParsedExpr<'a>> as expression; span; children!(
         [List(_), expression(t)] => {
-            EmptyListLit(rc(t))
+            spanned(span, EmptyListLit(rc(t)))
         },
         [Optional(_), expression(t)] => {
-            EmptyOptionalLit(rc(t))
+            spanned(span, EmptyOptionalLit(rc(t)))
         },
     ));
 
-    rule!(non_empty_optional<ParsedExpr> as expression; children!(
+    rule!(non_empty_optional<ParsedExpr<'a>> as expression; span; children!(
         [expression(x), Optional(_), expression(t)] => {
-            Annot(rc(NEOptionalLit(rc(x))), rc(t))
+            spanned(span, Annot(rc(NEOptionalLit(rc(x))), rc(t)))
         }
     ));
 
-    rule!(import_alt_expression<ParsedExpr> as expression; children!(
+    rule!(import_alt_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::ImportAlt;
             rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
-    rule!(or_expression<ParsedExpr> as expression; children!(
+    rule!(or_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::BoolOr;
             rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
-    rule!(plus_expression<ParsedExpr> as expression; children!(
+    rule!(plus_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::NaturalPlus;
             rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
-    rule!(text_append_expression<ParsedExpr> as expression; children!(
+    rule!(text_append_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::TextAppend;
             rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
-    rule!(list_append_expression<ParsedExpr> as expression; children!(
+    rule!(list_append_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::ListAppend;
             rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
-    rule!(and_expression<ParsedExpr> as expression; children!(
+    rule!(and_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::BoolAnd;
             rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
-    rule!(combine_expression<ParsedExpr> as expression; children!(
+    rule!(combine_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::Combine;
             rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
-    rule!(prefer_expression<ParsedExpr> as expression; children!(
+    rule!(prefer_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::Prefer;
             rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
-    rule!(combine_types_expression<ParsedExpr> as expression; children!(
+    rule!(combine_types_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::CombineTypes;
             rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
-    rule!(times_expression<ParsedExpr> as expression; children!(
+    rule!(times_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::NaturalTimes;
             rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
-    rule!(equal_expression<ParsedExpr> as expression; children!(
+    rule!(equal_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::BoolEQ;
             rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
-    rule!(not_equal_expression<ParsedExpr> as expression; children!(
+    rule!(not_equal_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::BoolNE;
@@ -702,30 +734,30 @@ make_parser! {
         },
     ));
 
-    rule!(annotated_expression<ParsedExpr> as expression; children!(
+    rule!(annotated_expression<ParsedExpr<'a>> as expression; span; children!(
         [expression(e)] => e,
         [expression(e), expression(annot)] => {
-            Annot(rc(e), rc(annot))
+            spanned(span, Annot(rc(e), rc(annot)))
         },
     ));
 
     token_rule!(Some<()>);
 
-    rule!(application_expression<ParsedExpr> as expression; children!(
+    rule!(application_expression<ParsedExpr<'a>> as expression; span; children!(
         [expression(e)] => e,
         [expression(Builtin(crate::Builtin::OptionalNone)),
                 expression(e), expression(rest)..] => {
-            app(EmptyOptionalLit(rc(e)), rest.map(rc).collect())
+            spanned(span, app(EmptyOptionalLit(rc(e)), rest.map(rc).collect()))
         },
         [Some(()), expression(e), expression(rest)..] => {
-            app(NEOptionalLit(rc(e)), rest.map(rc).collect())
+            spanned(span, app(NEOptionalLit(rc(e)), rest.map(rc).collect()))
         },
         [expression(first), expression(rest)..] => {
-            app(first, rest.map(rc).collect())
+            spanned(span, app(first, rest.map(rc).collect()))
         },
     ));
 
-    rule!(selector_expression<ParsedExpr> as expression; children!(
+    rule!(selector_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e)] => e,
         [expression(first), selector(rest)..] => {
             rest.fold(first, |acc, e| match e {
@@ -744,19 +776,19 @@ make_parser! {
         [label(ls)..] => ls.collect(),
     ));
 
-    rule!(primitive_expression<ParsedExpr> as expression; children!(
-        [double_literal(n)] => DoubleLit(n),
-        [natural_literal(n)] => NaturalLit(n),
-        [integer_literal(n)] => IntegerLit(n),
-        [double_quote_literal(s)] => TextLit(s),
-        [single_quote_literal(s)] => TextLit(s),
+    rule!(primitive_expression<ParsedExpr<'a>> as expression; 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)),
         [expression(e)] => e,
     ));
 
-    rule!(identifier<ParsedExpr> as expression; children!(
+    rule!(identifier<ParsedExpr<'a>> as expression; span; children!(
         [label(l), natural_literal(idx)] => {
             let name = String::from(&l);
-            match crate::Builtin::parse(name.as_str()) {
+            spanned(span, match crate::Builtin::parse(name.as_str()) {
                 Option::Some(b) => Builtin(b),
                 Option::None => match name.as_str() {
                     "True" => BoolLit(true),
@@ -766,11 +798,11 @@ make_parser! {
                     "Sort" => Const(crate::Const::Sort),
                     _ => Var(V(l, idx)),
                 }
-            }
+            })
         },
         [label(l)] => {
             let name = String::from(&l);
-            match crate::Builtin::parse(name.as_str()) {
+            spanned(span, match crate::Builtin::parse(name.as_str()) {
                 Option::Some(b) => Builtin(b),
                 Option::None => match name.as_str() {
                     "True" => BoolLit(true),
@@ -780,69 +812,71 @@ make_parser! {
                     "Sort" => Const(crate::Const::Sort),
                     _ => Var(V(l, 0)),
                 }
-            }
+            })
         },
     ));
 
-    rule!(empty_record_literal<ParsedExpr> as expression;
-        captured_str!(_) => RecordLit(BTreeMap::new())
+    rule!(empty_record_literal<ParsedExpr<'a>> as expression; span;
+        captured_str!(_) => spanned(span, RecordLit(BTreeMap::new()))
     );
 
-    rule!(empty_record_type<ParsedExpr> as expression;
-        captured_str!(_) => RecordType(BTreeMap::new())
+    rule!(empty_record_type<ParsedExpr<'a>> as expression; span;
+        captured_str!(_) => spanned(span, RecordType(BTreeMap::new()))
     );
 
-    rule!(non_empty_record_type_or_literal<ParsedExpr> as expression; children!(
+    rule!(non_empty_record_type_or_literal<ParsedExpr<'a>> as expression; span;
+          children!(
         [label(first_label), non_empty_record_type(rest)] => {
             let (first_expr, mut map) = rest;
             map.insert(first_label, rc(first_expr));
-            RecordType(map)
+            spanned(span, RecordType(map))
         },
         [label(first_label), non_empty_record_literal(rest)] => {
             let (first_expr, mut map) = rest;
             map.insert(first_label, rc(first_expr));
-            RecordLit(map)
+            spanned(span, RecordLit(map))
         },
     ));
 
     rule!(non_empty_record_type
-          <(ParsedExpr, BTreeMap<Label, ParsedSubExpr>)>; children!(
+          <(ParsedExpr<'a>, BTreeMap<Label, ParsedSubExpr<'a>>)>; children!(
         [expression(expr), record_type_entry(entries)..] => {
             (expr, entries.collect())
         }
     ));
 
-    rule!(record_type_entry<(Label, ParsedSubExpr)>; children!(
+    rule!(record_type_entry<(Label, ParsedSubExpr<'a>)>; children!(
         [label(name), expression(expr)] => (name, rc(expr))
     ));
 
     rule!(non_empty_record_literal
-          <(ParsedExpr, BTreeMap<Label, ParsedSubExpr>)>; children!(
+          <(ParsedExpr<'a>, BTreeMap<Label, ParsedSubExpr<'a>>)>; children!(
         [expression(expr), record_literal_entry(entries)..] => {
             (expr, entries.collect())
         }
     ));
 
-    rule!(record_literal_entry<(Label, ParsedSubExpr)>; children!(
+    rule!(record_literal_entry<(Label, ParsedSubExpr<'a>)>; children!(
         [label(name), expression(expr)] => (name, rc(expr))
     ));
 
-    rule!(union_type_or_literal<ParsedExpr> as expression; children!(
+    rule!(union_type_or_literal<ParsedExpr<'a>> as expression; span; children!(
         [empty_union_type(_)] => {
-            UnionType(BTreeMap::new())
+            spanned(span, UnionType(BTreeMap::new()))
         },
         [non_empty_union_type_or_literal((Option::Some((l, e)), entries))] => {
-            UnionLit(l, e, entries)
+            spanned(span, UnionLit(l, e, entries))
         },
         [non_empty_union_type_or_literal((Option::None, entries))] => {
-            UnionType(entries)
+            spanned(span, UnionType(entries))
         },
     ));
 
     token_rule!(empty_union_type<()>);
 
     rule!(non_empty_union_type_or_literal
-          <(Option<(Label, ParsedSubExpr)>, BTreeMap<Label, ParsedSubExpr>)>;
+          <(Option<(Label, ParsedSubExpr<'a>)>,
+            BTreeMap<Label, ParsedSubExpr<'a>>)>;
             children!(
         [label(l), union_literal_variant_value((e, entries))] => {
             (Option::Some((l, rc(e))), entries)
@@ -855,21 +889,22 @@ make_parser! {
     ));
 
     rule!(union_literal_variant_value
-          <(ParsedExpr, BTreeMap<Label, ParsedSubExpr>)>;
+          <(ParsedExpr<'a>, BTreeMap<Label, ParsedSubExpr<'a>>)>;
             children!(
         [expression(e), union_type_entry(entries)..] => {
             (e, entries.collect())
         },
     ));
 
-    rule!(union_type_entry<(Label, ParsedSubExpr)>; children!(
+    rule!(union_type_entry<(Label, ParsedSubExpr<'a>)>; children!(
         [label(name), expression(expr)] => (name, rc(expr))
     ));
 
     // TODO: unary union variants
     rule!(union_type_or_literal_variant_type
-          <(ParsedExpr,
-            (Option<(Label, ParsedSubExpr)>, BTreeMap<Label, ParsedSubExpr>))>;
+          <(ParsedExpr<'a>,
+            (Option<(Label, ParsedSubExpr<'a>)>,
+             BTreeMap<Label, ParsedSubExpr<'a>>))>;
                 children!(
         [expression(e), non_empty_union_type_or_literal(rest)] => {
             (e, rest)
@@ -879,16 +914,20 @@ make_parser! {
         },
     ));
 
-    rule!(non_empty_list_literal<ParsedExpr> as expression; children!(
-        [expression(items)..] => NEListLit(items.map(rc).collect())
+    rule!(non_empty_list_literal<ParsedExpr<'a>> as expression; span;
+          children!(
+        [expression(items)..] => spanned(
+            span,
+            NEListLit(items.map(rc).collect())
+        )
     ));
 
-    rule!(final_expression<ParsedExpr> as expression; children!(
+    rule!(final_expression<ParsedExpr<'a>> as expression; children!(
         [expression(e), EOI(_eoi)] => e
     ));
 }
 
-pub fn parse_expr(s: &str) -> ParseResult<ParsedSubExpr> {
+pub fn parse_expr<'a>(s: &'a str) -> ParseResult<ParsedSubExpr<'a>> {
     let mut pairs = DhallParser::parse(Rule::final_expression, s)?;
     let expr = do_parse(pairs.next().unwrap())?;
     assert_eq!(pairs.next(), None);
diff --git a/dhall_core/src/text.rs b/dhall_core/src/text.rs
index 7c0e2b4..0cfbd7b 100644
--- a/dhall_core/src/text.rs
+++ b/dhall_core/src/text.rs
@@ -34,30 +34,23 @@ pub enum InterpolatedTextContents<SubExpr> {
 }
 
 impl<SubExpr> InterpolatedText<SubExpr> {
-    pub fn traverse<SubExpr2, E, F>(
-        self,
+    pub fn traverse_ref<'a, SubExpr2, E, F>(
+        &'a self,
         mut f: F,
     ) -> Result<InterpolatedText<SubExpr2>, E>
     where
-        F: FnMut(SubExpr) -> Result<SubExpr2, E>,
+        F: FnMut(&'a SubExpr) -> Result<SubExpr2, E>,
     {
         Ok(InterpolatedText {
             head: self.head.clone(),
             tail: self
                 .tail
-                .into_iter()
+                .iter()
                 .map(|(e, s)| Ok((f(e)?, s.clone())))
                 .collect::<Result<_, _>>()?,
         })
     }
 
-    pub fn map<SubExpr2, F>(self, mut f: F) -> InterpolatedText<SubExpr2>
-    where
-        F: FnMut(SubExpr) -> SubExpr2,
-    {
-        crate::trivial_result(self.traverse(|e| Ok(f(e))))
-    }
-
     pub fn as_ref(&self) -> InterpolatedText<&SubExpr> {
         InterpolatedText {
             head: self.head.clone(),
diff --git a/dhall_generator/src/derive.rs b/dhall_generator/src/derive.rs
index c911be5..e231702 100644
--- a/dhall_generator/src/derive.rs
+++ b/dhall_generator/src/derive.rs
@@ -176,7 +176,8 @@ pub fn derive_simple_static_type_inner(
     let tokens = quote! {
         impl #impl_generics dhall::SimpleStaticType for #ident #ty_generics
                 #where_clause {
-            fn get_simple_static_type() -> dhall::expr::SimpleType {
+            fn get_simple_static_type<'get_simple_static_type>() ->
+                    dhall::expr::SimpleType<'get_simple_static_type> {
                 #(#assertions)*
                 dhall::expr::SimpleType::from(#get_type)
             }
diff --git a/dhall_generator/src/quote.rs b/dhall_generator/src/quote.rs
index 8552def..2d2eada 100644
--- a/dhall_generator/src/quote.rs
+++ b/dhall_generator/src/quote.rs
@@ -7,7 +7,7 @@ use std::collections::BTreeMap;
 
 pub fn expr(input: proc_macro::TokenStream) -> proc_macro::TokenStream {
     let input_str = input.to_string();
-    let expr: SubExpr<X, Import> = parse_expr(&input_str).unwrap();
+    let expr: SubExpr<_, Import> = parse_expr(&input_str).unwrap().unnote();
     let no_import =
         |_: &Import| -> X { panic!("Don't use import in dhall::expr!()") };
     let expr = expr.as_ref().map_embed(&no_import);
@@ -17,7 +17,7 @@ pub fn expr(input: proc_macro::TokenStream) -> proc_macro::TokenStream {
 
 pub fn subexpr(input: proc_macro::TokenStream) -> proc_macro::TokenStream {
     let input_str = input.to_string();
-    let expr: SubExpr<X, Import> = parse_expr(&input_str).unwrap();
+    let expr: SubExpr<_, Import> = parse_expr(&input_str).unwrap().unnote();
     let no_import =
         |_: &Import| -> X { panic!("Don't use import in dhall::subexpr!()") };
     let expr = expr.as_ref().map_embed(&no_import);