Rewrite normalization and typechecking with environments (#126)

Rewrite normalization and typechecking with environments

7 files changed, 241 insertions, 83 deletions

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 68cb524..28a0aee 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -24,7 +24,7 @@ pub enum Const {
 /// The `Int` field is a DeBruijn index.
 /// See dhall-lang/standard/semantics.md for details
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub struct V<Label>(pub Label, pub usize);
+pub struct V(pub Label, pub usize);
 
 // Definition order must match precedence order for
 // pretty-printing to work correctly
@@ -112,7 +112,7 @@ pub enum ExprKind<SubExpr, Embed> {
     Const(Const),
     ///  `x`
     ///  `x@n`
-    Var(V<Label>),
+    Var(V),
     ///  `λ(x : A) -> b`
     Lam(Label, SubExpr, SubExpr),
     ///  `A -> B`
@@ -174,29 +174,38 @@ pub enum ExprKind<SubExpr, Embed> {
 }
 
 impl<SE, E> ExprKind<SE, E> {
+    pub fn traverse_ref_maybe_binder<'a, SE2, Err>(
+        &'a self,
+        visit: impl FnMut(Option<&'a Label>, &'a SE) -> Result<SE2, Err>,
+    ) -> Result<ExprKind<SE2, E>, Err>
+    where
+        E: Clone,
+    {
+        visitor::TraverseRefMaybeBinderVisitor(visit).visit(self)
+    }
+
     pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, Err>(
         &'a self,
-        visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
-        visit_under_binder: impl FnOnce(&'a Label, &'a SE) -> Result<SE2, Err>,
+        mut visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
+        mut visit_under_binder: impl FnMut(&'a Label, &'a SE) -> Result<SE2, Err>,
     ) -> Result<ExprKind<SE2, E>, Err>
     where
         E: Clone,
     {
-        visitor::TraverseRefWithBindersVisitor {
-            visit_subexpr,
-            visit_under_binder,
-        }
-        .visit(self)
+        self.traverse_ref_maybe_binder(|l, x| match l {
+            None => visit_subexpr(x),
+            Some(l) => visit_under_binder(l, x),
+        })
     }
 
-    fn traverse_ref<'a, SE2, Err>(
+    pub(crate) fn traverse_ref<'a, SE2, Err>(
         &'a self,
-        visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
+        mut visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
     ) -> Result<ExprKind<SE2, E>, Err>
     where
         E: Clone,
     {
-        visitor::TraverseRefVisitor { visit_subexpr }.visit(self)
+        self.traverse_ref_maybe_binder(|_, e| visit_subexpr(e))
     }
 
     fn traverse_mut<'a, Err>(
@@ -206,6 +215,16 @@ impl<SE, E> ExprKind<SE, E> {
         visitor::TraverseMutVisitor { visit_subexpr }.visit(self)
     }
 
+    pub fn map_ref_maybe_binder<'a, SE2>(
+        &'a self,
+        mut map: impl FnMut(Option<&'a Label>, &'a SE) -> SE2,
+    ) -> ExprKind<SE2, E>
+    where
+        E: Clone,
+    {
+        trivial_result(self.traverse_ref_maybe_binder(|l, x| Ok(map(l, x))))
+    }
+
     pub fn map_ref_with_special_handling_of_binders<'a, SE2>(
         &'a self,
         mut map_subexpr: impl FnMut(&'a SE) -> SE2,
@@ -214,10 +233,10 @@ impl<SE, E> ExprKind<SE, E> {
     where
         E: Clone,
     {
-        trivial_result(self.traverse_ref_with_special_handling_of_binders(
-            |x| Ok(map_subexpr(x)),
-            |l, x| Ok(map_under_binder(l, x)),
-        ))
+        self.map_ref_maybe_binder(|l, x| match l {
+            None => map_subexpr(x),
+            Some(l) => map_under_binder(l, x),
+        })
     }
 
     pub fn map_ref<'a, SE2>(
@@ -227,7 +246,7 @@ impl<SE, E> ExprKind<SE, E> {
     where
         E: Clone,
     {
-        trivial_result(self.traverse_ref(|x| Ok(map_subexpr(x))))
+        self.map_ref_maybe_binder(|_, e| map_subexpr(e))
     }
 
     pub fn map_mut<'a>(&'a mut self, mut map_subexpr: impl FnMut(&'a mut SE)) {
@@ -295,22 +314,6 @@ impl<E> Expr<E> {
     }
 }
 
-impl<Label: PartialEq + Clone> V<Label> {
-    pub fn shift(&self, delta: isize, var: &V<Label>) -> Option<Self> {
-        let V(x, n) = var;
-        let V(y, m) = self;
-        Some(if x == y && n <= m {
-            V(y.clone(), add_ui(*m, delta)?)
-        } else {
-            V(y.clone(), *m)
-        })
-    }
-
-    pub fn over_binder(&self, x: &Label) -> Option<Self> {
-        self.shift(-1, &V(x.clone(), 0))
-    }
-}
-
 pub fn trivial_result<T>(x: Result<T, !>) -> T {
     match x {
         Ok(x) => x,
@@ -318,16 +321,6 @@ pub fn trivial_result<T>(x: Result<T, !>) -> T {
     }
 }
 
-/// Add an isize to an usize
-/// Returns `None` on over/underflow
-fn add_ui(u: usize, i: isize) -> Option<usize> {
-    Some(if i < 0 {
-        u.checked_sub(i.checked_neg()? as usize)?
-    } else {
-        u.checked_add(i as usize)?
-    })
-}
-
 impl PartialEq for NaiveDouble {
     fn eq(&self, other: &Self) -> bool {
         self.0.to_bits() == other.0.to_bits()
@@ -357,9 +350,8 @@ impl From<NaiveDouble> for f64 {
     }
 }
 
-/// This is only for the specific `Label` type, not generic
-impl From<Label> for V<Label> {
-    fn from(x: Label) -> V<Label> {
+impl From<Label> for V {
+    fn from(x: Label) -> V {
         V(x, 0)
     }
 }
diff --git a/dhall/src/syntax/ast/visitor.rs b/dhall/src/syntax/ast/visitor.rs
index 424048b..6a1ce7d 100644
--- a/dhall/src/syntax/ast/visitor.rs
+++ b/dhall/src/syntax/ast/visitor.rs
@@ -1,6 +1,7 @@
-use crate::syntax::*;
 use std::iter::FromIterator;
 
+use crate::syntax::*;
+
 /// A visitor trait that can be used to traverse `ExprKind`s. We need this pattern so that Rust lets
 /// us have as much mutability as we can.
 /// For example, `traverse_ref_with_special_handling_of_binders` cannot be made using only
@@ -295,51 +296,26 @@ where
     Ok(())
 }
 
-pub struct TraverseRefWithBindersVisitor<F1, F2> {
-    pub visit_subexpr: F1,
-    pub visit_under_binder: F2,
-}
+pub struct TraverseRefMaybeBinderVisitor<F>(pub F);
 
-impl<'a, SE, E, SE2, Err, F1, F2> ExprKindVisitor<'a, SE, SE2, E, E>
-    for TraverseRefWithBindersVisitor<F1, F2>
+impl<'a, SE, E, SE2, Err, F> ExprKindVisitor<'a, SE, SE2, E, E>
+    for TraverseRefMaybeBinderVisitor<F>
 where
     SE: 'a,
     E: 'a + Clone,
-    F1: FnMut(&'a SE) -> Result<SE2, Err>,
-    F2: FnOnce(&'a Label, &'a SE) -> Result<SE2, Err>,
+    F: FnMut(Option<&'a Label>, &'a SE) -> Result<SE2, Err>,
 {
     type Error = Err;
 
     fn visit_subexpr(&mut self, subexpr: &'a SE) -> Result<SE2, Self::Error> {
-        (self.visit_subexpr)(subexpr)
+        (self.0)(None, subexpr)
     }
     fn visit_subexpr_under_binder(
-        self,
+        mut self,
         label: &'a Label,
         subexpr: &'a SE,
     ) -> Result<SE2, Self::Error> {
-        (self.visit_under_binder)(label, subexpr)
-    }
-    fn visit_embed(self, embed: &'a E) -> Result<E, Self::Error> {
-        Ok(embed.clone())
-    }
-}
-
-pub struct TraverseRefVisitor<F1> {
-    pub visit_subexpr: F1,
-}
-
-impl<'a, SE, E, SE2, Err, F1> ExprKindVisitor<'a, SE, SE2, E, E>
-    for TraverseRefVisitor<F1>
-where
-    SE: 'a,
-    E: 'a + Clone,
-    F1: FnMut(&'a SE) -> Result<SE2, Err>,
-{
-    type Error = Err;
-
-    fn visit_subexpr(&mut self, subexpr: &'a SE) -> Result<SE2, Self::Error> {
-        (self.visit_subexpr)(subexpr)
+        (self.0)(Some(label), subexpr)
     }
     fn visit_embed(self, embed: &'a E) -> Result<E, Self::Error> {
         Ok(embed.clone())
diff --git a/dhall/src/syntax/binary/decode.rs b/dhall/src/syntax/binary/decode.rs
index c18deb5..52b699c 100644
--- a/dhall/src/syntax/binary/decode.rs
+++ b/dhall/src/syntax/binary/decode.rs
@@ -3,13 +3,13 @@ use serde_cbor::value::value as cbor;
 use std::iter::FromIterator;
 
 use crate::error::DecodeError;
-use crate::semantics::phase::DecodedExpr;
 use crate::syntax;
 use crate::syntax::{
     Expr, ExprKind, FilePath, FilePrefix, Hash, ImportLocation, ImportMode,
     Integer, InterpolatedText, Label, Natural, Scheme, Span, UnspannedExpr,
     URL, V,
 };
+use crate::DecodedExpr;
 
 pub(crate) fn decode(data: &[u8]) -> Result<DecodedExpr, DecodeError> {
     match serde_cbor::de::from_slice(data) {
diff --git a/dhall/src/syntax/text/dhall.abnf b/dhall/src/syntax/text/dhall.abnf
new file mode 120000
index 0000000..4a95034
--- /dev/null
+++ b/dhall/src/syntax/text/dhall.abnf
@@ -0,0 +1 @@
+../../../../dhall-lang/standard/dhall.abnf
\ No newline at end of file
diff --git a/dhall/src/syntax/text/dhall.pest.visibility b/dhall/src/syntax/text/dhall.pest.visibility
new file mode 100644
index 0000000..03a000b
--- /dev/null
+++ b/dhall/src/syntax/text/dhall.pest.visibility
@@ -0,0 +1,189 @@
+# end_of_line
+# valid_non_ascii
+# tab
+# block_comment
+# block_comment_char
+# block_comment_continue
+# not_end_of_line
+# line_comment
+# whitespace_chunk
+# whsp
+# whsp1
+# ALPHA
+# DIGIT
+# ALPHANUM
+# HEXDIG
+# simple_label_first_char
+# simple_label_next_char
+simple_label
+# quoted_label_char
+quoted_label
+# label
+# nonreserved_label
+# any_label
+any_label_or_some
+double_quote_chunk
+double_quote_escaped
+# unicode_escape
+# unicode_suffix
+# unbraced_escape
+# braced_codepoint
+# braced_escape
+double_quote_char
+double_quote_literal
+single_quote_continue
+escaped_quote_pair
+escaped_interpolation
+single_quote_char
+single_quote_literal
+# interpolation
+# text_literal
+if_
+# then
+# else_
+# let_
+# in_
+# as_
+# using
+merge
+missing
+# Infinity
+NaN
+Some_
+toMap
+assert
+# keyword
+builtin
+# Optional
+Text
+# List
+Location
+# Bool
+# True
+# False
+# None_
+# Natural
+# Integer
+# Double
+# Type
+# Kind
+# Sort
+# Natural_fold
+# Natural_build
+# Natural_isZero
+# Natural_even
+# Natural_odd
+# Natural_toInteger
+# Natural_show
+# Integer_toDouble
+# Integer_show
+# Natural_subtract
+# Double_show
+# List_build
+# List_fold
+# List_length
+# List_head
+# List_last
+# List_indexed
+# List_reverse
+# Optional_fold
+# Optional_build
+# Text_show
+combine
+combine_types
+equivalent
+prefer
+lambda
+forall
+arrow
+# complete
+# exponent
+numeric_double_literal
+minus_infinity_literal
+plus_infinity_literal
+# double_literal
+natural_literal
+integer_literal
+identifier
+variable
+# path_character
+# quoted_path_character
+unquoted_path_component
+quoted_path_component
+# path_component
+path
+local
+parent_path
+here_path
+home_path
+absolute_path
+scheme
+http_raw
+authority
+# userinfo
+# host
+# port
+# IP_literal
+# IPvFuture
+# IPv6address
+# h16
+# ls32
+# IPv4address
+# dec_octet
+# domain
+# domainlabel
+# pchar
+query
+# pct_encoded
+# unreserved
+# sub_delims
+http
+env
+bash_environment_variable
+posix_environment_variable
+posix_environment_variable_character
+# import_type
+hash
+import_hashed
+import
+expression
+# annotated_expression
+let_binding
+empty_list_literal
+operator_expression
+import_alt_expression
+or_expression
+plus_expression
+text_append_expression
+list_append_expression
+and_expression
+combine_expression
+prefer_expression
+combine_types_expression
+times_expression
+equal_expression
+not_equal_expression
+equivalent_expression
+application_expression
+first_application_expression
+# import_expression
+completion_expression
+selector_expression
+selector
+labels
+# type_selector
+primitive_expression
+# record_type_or_literal
+empty_record_literal
+empty_record_type
+non_empty_record_type_or_literal
+non_empty_record_type
+record_type_entry
+non_empty_record_literal
+record_literal_entry
+union_type
+empty_union_type
+# non_empty_union_type
+union_type_entry
+non_empty_list_literal
+# complete_expression
diff --git a/dhall/src/syntax/text/parser.rs b/dhall/src/syntax/text/parser.rs
index ef1471f..2ec63e2 100644
--- a/dhall/src/syntax/text/parser.rs
+++ b/dhall/src/syntax/text/parser.rs
@@ -5,7 +5,6 @@ use std::rc::Rc;
 
 use pest_consume::{match_nodes, Parser};
 
-use crate::semantics::phase::Normalized;
 use crate::syntax;
 use crate::syntax::map::{DupTreeMap, DupTreeSet};
 use crate::syntax::ExprKind::*;
@@ -14,6 +13,7 @@ use crate::syntax::{
     InterpolatedText, InterpolatedTextContents, Label, NaiveDouble, Natural,
     Scheme, Span, UnspannedExpr, URL, V,
 };
+use crate::Normalized;
 
 // This file consumes the parse tree generated by pest and turns it into
 // our own AST. All those custom macros should eventually moved into
@@ -422,7 +422,7 @@ impl DhallParser {
         ))
     }
 
-    fn variable(input: ParseInput) -> ParseResult<V<Label>> {
+    fn variable(input: ParseInput) -> ParseResult<V> {
         Ok(match_nodes!(input.into_children();
             [label(l), natural_literal(idx)] => V(l, idx),
             [label(l)] => V(l, 0),
diff --git a/dhall/src/syntax/text/printer.rs b/dhall/src/syntax/text/printer.rs
index 96f4c2a..06dd70f 100644
--- a/dhall/src/syntax/text/printer.rs
+++ b/dhall/src/syntax/text/printer.rs
@@ -496,7 +496,7 @@ impl Display for Scheme {
     }
 }
 
-impl<Label: Display> Display for V<Label> {
+impl Display for V {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         let V(x, n) = self;
         x.fmt(f)?;