Add support for dependent types

3 files changed, 56 insertions, 23 deletions

diff --git a/dhall/src/phase/binary.rs b/dhall/src/phase/binary.rs
index 5e7eb40..719b1c7 100644
--- a/dhall/src/phase/binary.rs
+++ b/dhall/src/phase/binary.rs
@@ -119,6 +119,7 @@ fn cbor_value_to_dhall(
                     9 => RightBiasedRecordMerge,
                     10 => RecursiveRecordTypeMerge,
                     11 => ImportAlt,
+                    12 => Equivalence,
                     _ => {
                         Err(DecodeError::WrongFormatError("binop".to_owned()))?
                     }
@@ -211,6 +212,10 @@ fn cbor_value_to_dhall(
                         .collect::<Result<_, _>>()?,
                 )))
             }
+            [U64(19), t] => {
+                let t = cbor_value_to_dhall(&t)?;
+                Assert(t)
+            }
             [U64(24), hash, U64(mode), U64(scheme), rest..] => {
                 let mode = match mode {
                     0 => ImportMode::Code,
@@ -504,6 +509,7 @@ where
             )
         }
         Annot(x, y) => ser_seq!(ser; tag(26), expr(x), expr(y)),
+        Assert(x) => ser_seq!(ser; tag(19), expr(x)),
         SomeLit(x) => ser_seq!(ser; tag(5), null(), expr(x)),
         EmptyListLit(x) => match x.as_ref() {
             App(f, a) => match f.as_ref() {
@@ -541,6 +547,7 @@ where
                 RightBiasedRecordMerge => 9,
                 RecursiveRecordTypeMerge => 10,
                 ImportAlt => 11,
+                Equivalence => 12,
             };
             ser_seq!(ser; tag(3), U64(op), expr(x), expr(y))
         }
diff --git a/dhall/src/phase/normalize.rs b/dhall/src/phase/normalize.rs
index 395cf28..ecad063 100644
--- a/dhall/src/phase/normalize.rs
+++ b/dhall/src/phase/normalize.rs
@@ -508,9 +508,9 @@ where
 
 fn apply_binop<'a>(o: BinOp, x: &'a Thunk, y: &'a Thunk) -> Option<Ret<'a>> {
     use BinOp::{
-        BoolAnd, BoolEQ, BoolNE, BoolOr, ListAppend, NaturalPlus, NaturalTimes,
-        RecursiveRecordMerge, RecursiveRecordTypeMerge, RightBiasedRecordMerge,
-        TextAppend,
+        BoolAnd, BoolEQ, BoolNE, BoolOr, Equivalence, ListAppend, NaturalPlus,
+        NaturalTimes, RecursiveRecordMerge, RecursiveRecordTypeMerge,
+        RightBiasedRecordMerge, TextAppend,
     };
     use Value::{
         BoolLit, EmptyListLit, NEListLit, NaturalLit, RecordLit, RecordType,
@@ -626,6 +626,11 @@ fn apply_binop<'a>(o: BinOp, x: &'a Thunk, y: &'a Thunk) -> Option<Ret<'a>> {
             Ret::Value(RecordType(kvs))
         }
 
+        (Equivalence, _, _) => Ret::Value(Value::Equivalence(
+            TypeThunk::from_thunk(x.clone()),
+            TypeThunk::from_thunk(y.clone()),
+        )),
+
         _ => return None,
     })
 }
@@ -641,6 +646,7 @@ pub fn normalize_one_layer(expr: ExprF<Thunk, X>) -> Value {
         ExprF::Embed(_) => unreachable!(),
         ExprF::Var(_) => unreachable!(),
         ExprF::Annot(x, _) => Ret::Thunk(x),
+        ExprF::Assert(_) => Ret::Expr(expr),
         ExprF::Lam(x, t, e) => {
             Ret::Value(Lam(x.into(), TypeThunk::from_thunk(t), e))
         }
diff --git a/dhall/src/phase/typecheck.rs b/dhall/src/phase/typecheck.rs
index 2e4642c..297a096 100644
--- a/dhall/src/phase/typecheck.rs
+++ b/dhall/src/phase/typecheck.rs
@@ -60,18 +60,7 @@ fn tck_pi_type(
         }
     };
 
-    let k = match function_check(ka, kb) {
-        Ok(k) => k,
-        Err(()) => {
-            return Err(TypeError::new(
-                ctx,
-                NoDependentTypes(
-                    tx.to_normalized(),
-                    te.get_type()?.to_normalized(),
-                ),
-            ))
-        }
-    };
+    let k = function_check(ka, kb);
 
     Ok(Typed::from_thunk_and_type(
         Value::Pi(x.into(), TypeThunk::from_type(tx), TypeThunk::from_type(te))
@@ -164,14 +153,13 @@ fn tck_union_type(
     ))
 }
 
-fn function_check(a: Const, b: Const) -> Result<Const, ()> {
-    use dhall_syntax::Const::*;
-    match (a, b) {
-        (_, Type) => Ok(Type),
-        (Kind, Kind) => Ok(Kind),
-        (Sort, Sort) => Ok(Sort),
-        (Sort, Kind) => Ok(Sort),
-        _ => Err(()),
+fn function_check(a: Const, b: Const) -> Const {
+    use dhall_syntax::Const::Type;
+    use std::cmp::max;
+    if b == Type {
+        Type
+    } else {
+        max(a, b)
     }
 }
 
@@ -403,6 +391,19 @@ fn type_last_layer(
             );
             Ok(RetTypeOnly(x.get_type()?.into_owned()))
         }
+        Assert(t) => {
+            match t.to_value() {
+                Value::Equivalence(x, y) if x == y => {}
+                Value::Equivalence(x, y) => {
+                    return Err(mkerr(AssertMismatch(
+                        x.to_typed(),
+                        y.to_typed(),
+                    )))
+                }
+                _ => return Err(mkerr(AssertMustTakeEquivalence)),
+            }
+            Ok(RetTypeOnly(t.to_type()))
+        }
         BoolIf(x, y, z) => {
             ensure_equal!(
                 x.get_type()?,
@@ -807,6 +808,24 @@ fn type_last_layer(
 
             Ok(RetTypeOnly(l.get_type()?.into_owned()))
         }
+        BinOp(Equivalence, l, r) => {
+            ensure_simple_type!(
+                l.get_type()?,
+                mkerr(EquivalenceArgumentMustBeTerm(true, l.clone())),
+            );
+            ensure_simple_type!(
+                r.get_type()?,
+                mkerr(EquivalenceArgumentMustBeTerm(false, r.clone())),
+            );
+
+            ensure_equal!(
+                l.get_type()?,
+                r.get_type()?,
+                mkerr(EquivalenceTypeMismatch(r.clone(), l.clone()))
+            );
+
+            Ok(RetTypeOnly(Type::from_const(dhall_syntax::Const::Type)))
+        }
         BinOp(o, l, r) => {
             let t = builtin_to_type(match o {
                 BoolAnd => Bool,
@@ -821,6 +840,7 @@ fn type_last_layer(
                 RecursiveRecordMerge => unreachable!(),
                 RecursiveRecordTypeMerge => unreachable!(),
                 ImportAlt => unreachable!("There should remain no import alternatives in a resolved expression"),
+                Equivalence => unreachable!(),
             })?;
 
             ensure_equal!(