From 8e2da26650e202f9ccb1531fc8a88cfd89e54b6d Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Fri, 27 Dec 2019 15:15:08 +0000
Subject: Implement traverse_ref for ValueKind

---
 dhall/src/syntax/ast/expr.rs | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'dhall/src/syntax/ast/expr.rs')

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 68cb524..376480f 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -189,7 +189,7 @@ impl<SE, E> ExprKind<SE, E> {
         .visit(self)
     }
 
-    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>,
     ) -> Result<ExprKind<SE2, E>, Err>
-- 
cgit v1.2.3


From fc1d7b758008643447f17bc9d05adb128d1567cc Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Fri, 17 Jan 2020 10:25:28 +0000
Subject: Remove binder ids

The underlying purpose of them turned out to be unsound
---
 dhall/src/syntax/ast/expr.rs | 9 +++++++++
 1 file changed, 9 insertions(+)

(limited to 'dhall/src/syntax/ast/expr.rs')

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 376480f..0ac31a5 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -173,6 +173,15 @@ pub enum ExprKind<SubExpr, Embed> {
     Embed(Embed),
 }
 
+impl<Label> V<Label> {
+    pub(crate) fn name(&self) -> &Label {
+        &self.0
+    }
+    pub(crate) fn idx(&self) -> usize {
+        self.1
+    }
+}
+
 impl<SE, E> ExprKind<SE, E> {
     pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, Err>(
         &'a self,
-- 
cgit v1.2.3


From f7a8d967b02bc20c093d501746ed3de53cc7da13 Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Fri, 17 Jan 2020 10:49:02 +0000
Subject: Simplify Shift and Subst instances

---
 dhall/src/syntax/ast/expr.rs | 3 ---
 1 file changed, 3 deletions(-)

(limited to 'dhall/src/syntax/ast/expr.rs')

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 0ac31a5..04b5adc 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -174,9 +174,6 @@ pub enum ExprKind<SubExpr, Embed> {
 }
 
 impl<Label> V<Label> {
-    pub(crate) fn name(&self) -> &Label {
-        &self.0
-    }
     pub(crate) fn idx(&self) -> usize {
         self.1
     }
-- 
cgit v1.2.3


From 3881d36335fca6d72b0dd447130d6c1ce7ccbfee Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Fri, 17 Jan 2020 18:19:33 +0000
Subject: Implement bulk shifting

---
 dhall/src/syntax/ast/expr.rs | 33 +++++++++++++++++++++++++++++----
 1 file changed, 29 insertions(+), 4 deletions(-)

(limited to 'dhall/src/syntax/ast/expr.rs')

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 04b5adc..2372b0a 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -1,3 +1,5 @@
+use std::collections::HashMap;
+
 use crate::syntax::map::{DupTreeMap, DupTreeSet};
 use crate::syntax::visitor::{self, ExprKindMutVisitor, ExprKindVisitor};
 use crate::syntax::*;
@@ -302,7 +304,7 @@ impl<E> Expr<E> {
 }
 
 impl<Label: PartialEq + Clone> V<Label> {
-    pub fn shift(&self, delta: isize, var: &V<Label>) -> Option<Self> {
+    pub(crate) 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 {
@@ -312,11 +314,35 @@ impl<Label: PartialEq + Clone> V<Label> {
         })
     }
 
-    pub fn over_binder(&self, x: &Label) -> Option<Self> {
+    pub(crate) fn over_binder(&self, x: &Label) -> Option<Self> {
         self.shift(-1, &V(x.clone(), 0))
     }
 }
 
+impl V<Label> {
+    pub(crate) fn under_multiple_binders(
+        &self,
+        shift_map: &HashMap<Label, usize>,
+    ) -> Self {
+        let name = &self.0;
+        let idx = self.1 + shift_map.get(name).unwrap_or(&0);
+        V(name.clone(), idx)
+    }
+}
+
+impl V<()> {
+    pub(crate) fn under_multiple_binders(
+        &self,
+        shift_map: &HashMap<Label, usize>,
+    ) -> Self {
+        let mut idx = self.1;
+        for (_, n) in shift_map {
+            idx += n;
+        }
+        V((), idx)
+    }
+}
+
 pub fn trivial_result<T>(x: Result<T, !>) -> T {
     match x {
         Ok(x) => x,
@@ -363,8 +389,7 @@ impl From<NaiveDouble> for f64 {
     }
 }
 
-/// This is only for the specific `Label` type, not generic
-impl From<Label> for V<Label> {
+impl<Label> From<Label> for V<Label> {
     fn from(x: Label) -> V<Label> {
         V(x, 0)
     }
-- 
cgit v1.2.3


From 0f4a4801ed67826dc82015d39ce8fd05e7950035 Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Fri, 17 Jan 2020 18:42:13 +0000
Subject: Replace all bulk shifting by a single shift

---
 dhall/src/syntax/ast/expr.rs | 26 --------------------------
 1 file changed, 26 deletions(-)

(limited to 'dhall/src/syntax/ast/expr.rs')

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 2372b0a..170cbe7 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -1,5 +1,3 @@
-use std::collections::HashMap;
-
 use crate::syntax::map::{DupTreeMap, DupTreeSet};
 use crate::syntax::visitor::{self, ExprKindMutVisitor, ExprKindVisitor};
 use crate::syntax::*;
@@ -319,30 +317,6 @@ impl<Label: PartialEq + Clone> V<Label> {
     }
 }
 
-impl V<Label> {
-    pub(crate) fn under_multiple_binders(
-        &self,
-        shift_map: &HashMap<Label, usize>,
-    ) -> Self {
-        let name = &self.0;
-        let idx = self.1 + shift_map.get(name).unwrap_or(&0);
-        V(name.clone(), idx)
-    }
-}
-
-impl V<()> {
-    pub(crate) fn under_multiple_binders(
-        &self,
-        shift_map: &HashMap<Label, usize>,
-    ) -> Self {
-        let mut idx = self.1;
-        for (_, n) in shift_map {
-            idx += n;
-        }
-        V((), idx)
-    }
-}
-
 pub fn trivial_result<T>(x: Result<T, !>) -> T {
     match x {
         Ok(x) => x,
-- 
cgit v1.2.3


From ec28905d32c23109da17696faefab284fde3e103 Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Sat, 18 Jan 2020 18:46:09 +0000
Subject: Introduce intermediate representation that stores typed expr

---
 dhall/src/syntax/ast/expr.rs | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'dhall/src/syntax/ast/expr.rs')

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 170cbe7..f22a279 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -23,7 +23,7 @@ pub enum Const {
 /// The `Label` field is the variable's name (i.e. \"`x`\").
 /// The `Int` field is a DeBruijn index.
 /// See dhall-lang/standard/semantics.md for details
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct V<Label>(pub Label, pub usize);
 
 // Definition order must match precedence order for
-- 
cgit v1.2.3


From d6e5c56a5ef1d5f2b7cafd4a8fb44ce038932547 Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Sat, 18 Jan 2020 19:08:34 +0000
Subject: Add Expr visitor and improve tyexpr_to_expr

---
 dhall/src/syntax/ast/expr.rs | 47 +++++++++++++++++++++++++++++++-------------
 1 file changed, 33 insertions(+), 14 deletions(-)

(limited to 'dhall/src/syntax/ast/expr.rs')

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index f22a279..dbe233b 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -180,29 +180,38 @@ impl<Label> V<Label> {
 }
 
 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),
+        })
     }
 
     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>(
@@ -212,6 +221,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,
@@ -220,10 +239,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>(
@@ -233,7 +252,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)) {
-- 
cgit v1.2.3


From db6c09f33c3c794e4b6ec8a7aa80978d945a9d7a Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Wed, 29 Jan 2020 21:26:42 +0000
Subject: Remove dead code

---
 dhall/src/syntax/ast/expr.rs | 4 ----
 1 file changed, 4 deletions(-)

(limited to 'dhall/src/syntax/ast/expr.rs')

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index dbe233b..0da617b 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -330,10 +330,6 @@ impl<Label: PartialEq + Clone> V<Label> {
             V(y.clone(), *m)
         })
     }
-
-    pub(crate) fn over_binder(&self, x: &Label) -> Option<Self> {
-        self.shift(-1, &V(x.clone(), 0))
-    }
 }
 
 pub fn trivial_result<T>(x: Result<T, !>) -> T {
-- 
cgit v1.2.3


From 280b3174476ef8fe5a98f3614f4fe253fa243d8c Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Wed, 29 Jan 2020 21:35:28 +0000
Subject: Finally get rid of all of the shift/subst_shift !

---
 dhall/src/syntax/ast/expr.rs | 22 ----------------------
 1 file changed, 22 deletions(-)

(limited to 'dhall/src/syntax/ast/expr.rs')

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 0da617b..424ac34 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -320,18 +320,6 @@ impl<E> Expr<E> {
     }
 }
 
-impl<Label: PartialEq + Clone> V<Label> {
-    pub(crate) 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 trivial_result<T>(x: Result<T, !>) -> T {
     match x {
         Ok(x) => x,
@@ -339,16 +327,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()
-- 
cgit v1.2.3


From a928c3c4f51d87fd942e8a81727962c00abf6808 Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Wed, 29 Jan 2020 22:06:01 +0000
Subject: Cleanup variable handling

---
 dhall/src/syntax/ast/expr.rs | 16 +++++-----------
 1 file changed, 5 insertions(+), 11 deletions(-)

(limited to 'dhall/src/syntax/ast/expr.rs')

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 424ac34..28a0aee 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -23,8 +23,8 @@ pub enum Const {
 /// The `Label` field is the variable's name (i.e. \"`x`\").
 /// The `Int` field is a DeBruijn index.
 /// See dhall-lang/standard/semantics.md for details
-#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
-pub struct V<Label>(pub Label, pub usize);
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+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`
@@ -173,12 +173,6 @@ pub enum ExprKind<SubExpr, Embed> {
     Embed(Embed),
 }
 
-impl<Label> V<Label> {
-    pub(crate) fn idx(&self) -> usize {
-        self.1
-    }
-}
-
 impl<SE, E> ExprKind<SE, E> {
     pub fn traverse_ref_maybe_binder<'a, SE2, Err>(
         &'a self,
@@ -356,8 +350,8 @@ impl From<NaiveDouble> for f64 {
     }
 }
 
-impl<Label> From<Label> for V<Label> {
-    fn from(x: Label) -> V<Label> {
+impl From<Label> for V {
+    fn from(x: Label) -> V {
         V(x, 0)
     }
 }
-- 
cgit v1.2.3