Merge branch 'lifetimes'

Closes #55

8 files changed, 199 insertions, 156 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 => {