From f5d2151d35942b957230c3081a928af3619d9400 Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Sun, 31 Mar 2019 18:47:34 +0200
Subject: Make SubExpr a newtype

---
 dhall_core/src/core.rs    | 45 +++++++++++++++++++++++++++++++++------------
 dhall_core/src/printer.rs |  6 ++++++
 dhall_core/src/text.rs    | 11 +++++------
 3 files changed, 44 insertions(+), 18 deletions(-)

(limited to 'dhall_core/src')

diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index 0ea8c83..b49515a 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -170,7 +170,8 @@ pub type ParsedExpr = SubExpr<X, Import>;
 pub type ResolvedExpr = SubExpr<X, X>;
 pub type DhallExpr = ResolvedExpr;
 
-pub type SubExpr<Note, Embed> = Rc<Expr<Note, Embed>>;
+#[derive(Debug, PartialEq, Eq)]
+pub struct SubExpr<Note, Embed>(pub Rc<Expr<Note, Embed>>);
 
 /// Syntax tree for expressions
 #[derive(Debug, Clone, PartialEq, Eq)]
@@ -315,13 +316,33 @@ impl<S: Clone, A: Clone> Expr<S, Expr<S, A>> {
     }
 }
 
+impl<N, E> Clone for SubExpr<N, E> {
+    fn clone(&self) -> Self {
+        SubExpr(Rc::clone(&self.0))
+    }
+}
+
+impl<N, E> std::ops::Deref for SubExpr<N, E> {
+    type Target = Rc<Expr<N, E>>;
+    #[inline(always)]
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+// impl<N, E> SubExpr<N, E> {
+//     pub fn as_ref(&self) -> &Expr<N, E> {
+//         self.0.as_ref()
+//     }
+// }
+
 // Remains of a previous life, where everything was in Boxes
-pub fn bx<T>(x: T) -> Rc<T> {
-    Rc::new(x)
+pub fn bx<N, E>(x: Expr<N, E>) -> SubExpr<N, E> {
+    SubExpr(Rc::new(x))
 }
 
-pub fn rc<T>(x: T) -> Rc<T> {
-    Rc::new(x)
+pub fn rc<N, E>(x: Expr<N, E>) -> SubExpr<N, E> {
+    SubExpr(Rc::new(x))
 }
 
 fn add_ui(u: usize, i: isize) -> usize {
@@ -401,7 +422,7 @@ where
     F2: FnOnce(&Label, &SubExpr<S, A>) -> SubExpr<S, A>,
 {
     match e.as_ref() {
-        Expr::Embed(_) => Rc::clone(e),
+        Expr::Embed(_) => SubExpr::clone(e),
         Expr::Note(_, e) => {
             map_subexpr_rc_binder(e, map_expr, map_under_binder)
         }
@@ -500,8 +521,8 @@ where
 pub fn shift<S, A>(
     delta: isize,
     var: &V,
-    in_expr: &Rc<Expr<S, A>>,
-) -> Rc<Expr<S, A>> {
+    in_expr: &SubExpr<S, A>,
+) -> SubExpr<S, A> {
     use crate::Expr::*;
     let V(x, n) = var;
     let under_binder = |y: &Label, e: &SubExpr<_, _>| {
@@ -529,9 +550,9 @@ pub fn shift<S, A>(
 ///
 pub fn subst<S, A>(
     var: &V,
-    value: &Rc<Expr<S, A>>,
-    in_expr: &Rc<Expr<S, A>>,
-) -> Rc<Expr<S, A>> {
+    value: &SubExpr<S, A>,
+    in_expr: &SubExpr<S, A>,
+) -> SubExpr<S, A> {
     use crate::Expr::*;
     let under_binder = |y: &Label, e: &SubExpr<_, _>| {
         let V(x, n) = var;
@@ -540,7 +561,7 @@ pub fn subst<S, A>(
         subst(newvar, &shift(1, &V(y.clone(), 0), value), e)
     };
     match in_expr.as_ref() {
-        Var(v) if var == v => Rc::clone(value),
+        Var(v) if var == v => SubExpr::clone(value),
         _ => map_subexpr_rc_binder(
             in_expr,
             |e| subst(var, value, e),
diff --git a/dhall_core/src/printer.rs b/dhall_core/src/printer.rs
index 1d1b063..b153d1b 100644
--- a/dhall_core/src/printer.rs
+++ b/dhall_core/src/printer.rs
@@ -8,6 +8,12 @@ impl<S, A: Display> Display for Expr<S, A> {
     }
 }
 
+impl<S, A: Display> Display for SubExpr<S, A> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
+        self.as_ref().fmt(f)
+    }
+}
+
 //  There is a one-to-one correspondence between the formatter and the grammar. Each phase is
 //  named after a corresponding grammar group, and the structure of the formatter reflects
 //  the relationship between the corresponding grammar rules. This leads to the nice property
diff --git a/dhall_core/src/text.rs b/dhall_core/src/text.rs
index d377877..eef0797 100644
--- a/dhall_core/src/text.rs
+++ b/dhall_core/src/text.rs
@@ -1,18 +1,17 @@
 use crate::*;
 use std::iter::FromIterator;
 use std::ops::Add;
-use std::rc::Rc;
 
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct InterpolatedText<Note, Embed> {
     head: String,
-    tail: Vec<(Rc<Expr<Note, Embed>>, String)>,
+    tail: Vec<(SubExpr<Note, Embed>, String)>,
 }
 
-impl<N, E> From<(String, Vec<(Rc<Expr<N, E>>, String)>)>
+impl<N, E> From<(String, Vec<(SubExpr<N, E>, String)>)>
     for InterpolatedText<N, E>
 {
-    fn from(x: (String, Vec<(Rc<Expr<N, E>>, String)>)) -> Self {
+    fn from(x: (String, Vec<(SubExpr<N, E>, String)>)) -> Self {
         InterpolatedText {
             head: x.0,
             tail: x.1,
@@ -38,7 +37,7 @@ pub enum InterpolatedTextContents<Note, Embed> {
 impl<N, E> InterpolatedText<N, E> {
     pub fn map<N2, E2, F>(&self, mut f: F) -> InterpolatedText<N2, E2>
     where
-        F: FnMut(&Rc<Expr<N, E>>) -> Rc<Expr<N2, E2>>,
+        F: FnMut(&SubExpr<N, E>) -> SubExpr<N2, E2>,
     {
         InterpolatedText {
             head: self.head.clone(),
@@ -52,7 +51,7 @@ impl<N, E> InterpolatedText<N, E> {
         use std::iter::once;
         once(InterpolatedTextContents::Text(self.head.clone())).chain(
             self.tail.iter().flat_map(|(e, s)| {
-                once(InterpolatedTextContents::Expr(Rc::clone(e)))
+                once(InterpolatedTextContents::Expr(SubExpr::clone(e)))
                     .chain(once(InterpolatedTextContents::Text(s.clone())))
             }),
         )
-- 
cgit v1.2.3


From 7374d0524ccd53b256107667b213597c05720d2d Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Sun, 31 Mar 2019 19:08:08 +0200
Subject: Move recursion out of Expr

---
 dhall_core/src/core.rs    |  76 +++++++++-----------
 dhall_core/src/parser.rs  | 172 +++++++++++++++++++++++-----------------------
 dhall_core/src/printer.rs |   8 +--
 dhall_core/src/text.rs    |  37 +++++-----
 4 files changed, 141 insertions(+), 152 deletions(-)

(limited to 'dhall_core/src')

diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index b49515a..2d11068 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -173,43 +173,39 @@ pub type DhallExpr = ResolvedExpr;
 #[derive(Debug, PartialEq, Eq)]
 pub struct SubExpr<Note, Embed>(pub Rc<Expr<Note, Embed>>);
 
+pub type Expr<Note, Embed> = ExprF<SubExpr<Note, Embed>, Note, Embed>;
+
 /// Syntax tree for expressions
+// Having the recursion out of the enum definition enables writing
+// much more generic code and improves pattern-matching behind
+// smart pointers.
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub enum Expr<Note, Embed> {
+pub enum ExprF<SubExpr, Note, Embed> {
     ///  `Const c                                  ~  c`
     Const(Const),
     ///  `Var (V x 0)                              ~  x`<br>
     ///  `Var (V x n)                              ~  x@n`
     Var(V),
     ///  `Lam x     A b                            ~  λ(x : A) -> b`
-    Lam(Label, SubExpr<Note, Embed>, SubExpr<Note, Embed>),
+    Lam(Label, SubExpr, SubExpr),
     ///  `Pi "_" A B                               ~        A  -> B`
     ///  `Pi x   A B                               ~  ∀(x : A) -> B`
-    Pi(Label, SubExpr<Note, Embed>, SubExpr<Note, Embed>),
+    Pi(Label, SubExpr, SubExpr),
     ///  `App f A                                  ~  f A`
-    App(SubExpr<Note, Embed>, Vec<SubExpr<Note, Embed>>),
+    App(SubExpr, Vec<SubExpr>),
     ///  `Let x Nothing  r e  ~  let x     = r in e`
     ///  `Let x (Just t) r e  ~  let x : t = r in e`
-    Let(
-        Label,
-        Option<SubExpr<Note, Embed>>,
-        SubExpr<Note, Embed>,
-        SubExpr<Note, Embed>,
-    ),
+    Let(Label, Option<SubExpr>, SubExpr, SubExpr),
     ///  `Annot x t                                ~  x : t`
-    Annot(SubExpr<Note, Embed>, SubExpr<Note, Embed>),
+    Annot(SubExpr, SubExpr),
     /// Built-in values
     Builtin(Builtin),
     // Binary operations
-    BinOp(BinOp, SubExpr<Note, Embed>, SubExpr<Note, Embed>),
+    BinOp(BinOp, SubExpr, SubExpr),
     ///  `BoolLit b                                ~  b`
     BoolLit(bool),
     ///  `BoolIf x y z                             ~  if x then y else z`
-    BoolIf(
-        SubExpr<Note, Embed>,
-        SubExpr<Note, Embed>,
-        SubExpr<Note, Embed>,
-    ),
+    BoolIf(SubExpr, SubExpr, SubExpr),
     ///  `NaturalLit n                             ~  +n`
     NaturalLit(Natural),
     ///  `IntegerLit n                             ~  n`
@@ -217,39 +213,31 @@ pub enum Expr<Note, Embed> {
     ///  `DoubleLit n                              ~  n`
     DoubleLit(Double),
     ///  `TextLit t                                ~  t`
-    TextLit(InterpolatedText<Note, Embed>),
+    TextLit(InterpolatedText<SubExpr>),
     ///  [] : List t`
-    EmptyListLit(SubExpr<Note, Embed>),
+    EmptyListLit(SubExpr),
     ///  [x, y, z]
-    NEListLit(Vec<SubExpr<Note, Embed>>),
+    NEListLit(Vec<SubExpr>),
     ///  None t
-    EmptyOptionalLit(SubExpr<Note, Embed>),
+    EmptyOptionalLit(SubExpr),
     ///  Some e
-    NEOptionalLit(SubExpr<Note, Embed>),
+    NEOptionalLit(SubExpr),
     ///  `Record            [(k1, t1), (k2, t2)]   ~  { k1 : t1, k2 : t1 }`
-    RecordType(BTreeMap<Label, SubExpr<Note, Embed>>),
+    RecordType(BTreeMap<Label, SubExpr>),
     ///  `RecordLit         [(k1, v1), (k2, v2)]   ~  { k1 = v1, k2 = v2 }`
-    RecordLit(BTreeMap<Label, SubExpr<Note, Embed>>),
+    RecordLit(BTreeMap<Label, SubExpr>),
     ///  `Union             [(k1, t1), (k2, t2)]   ~  < k1 : t1, k2 : t2 >`
-    UnionType(BTreeMap<Label, SubExpr<Note, Embed>>),
+    UnionType(BTreeMap<Label, SubExpr>),
     ///  `UnionLit (k1, v1) [(k2, t2), (k3, t3)]   ~  < k1 = t1, k2 : t2, k3 : t3 >`
-    UnionLit(
-        Label,
-        SubExpr<Note, Embed>,
-        BTreeMap<Label, SubExpr<Note, Embed>>,
-    ),
+    UnionLit(Label, SubExpr, BTreeMap<Label, SubExpr>),
     ///  `Merge x y t                              ~  merge x y : t`
-    Merge(
-        SubExpr<Note, Embed>,
-        SubExpr<Note, Embed>,
-        Option<SubExpr<Note, Embed>>,
-    ),
+    Merge(SubExpr, SubExpr, Option<SubExpr>),
     ///  e.x
-    Field(SubExpr<Note, Embed>, Label),
+    Field(SubExpr, Label),
     ///  e.{ x, y, z }
-    Projection(SubExpr<Note, Embed>, Vec<Label>),
+    Projection(SubExpr, Vec<Label>),
     /// Annotation on the AST. Unused for now but could hold e.g. file location information
-    Note(Note, SubExpr<Note, Embed>),
+    Note(Note, SubExpr),
     /// Embeds an import or the result of resolving the import
     Embed(Embed),
 }
@@ -305,7 +293,7 @@ impl<S, A> Expr<S, A> {
 impl<S: Clone, A: Clone> Expr<S, Expr<S, A>> {
     pub fn squash_embed(&self) -> Expr<S, A> {
         match self {
-            Expr::Embed(e) => e.clone(),
+            ExprF::Embed(e) => e.clone(),
             e => e.map_shallow(
                 |e| e.squash_embed(),
                 |x| x.clone(),
@@ -369,7 +357,7 @@ where
     F4: Fn(&Label) -> Label,
     F5: FnOnce(&Label, &SubExpr<S, A>) -> SubExpr<T, B>,
 {
-    use crate::Expr::*;
+    use crate::ExprF::*;
     let map = &map;
     let opt = |x: &Option<_>| x.as_ref().map(&map);
     let vec = |x: &Vec<_>| x.iter().map(&map).collect();
@@ -422,8 +410,8 @@ where
     F2: FnOnce(&Label, &SubExpr<S, A>) -> SubExpr<S, A>,
 {
     match e.as_ref() {
-        Expr::Embed(_) => SubExpr::clone(e),
-        Expr::Note(_, e) => {
+        ExprF::Embed(_) => SubExpr::clone(e),
+        ExprF::Note(_, e) => {
             map_subexpr_rc_binder(e, map_expr, map_under_binder)
         }
         _ => rc(map_subexpr(
@@ -523,7 +511,7 @@ pub fn shift<S, A>(
     var: &V,
     in_expr: &SubExpr<S, A>,
 ) -> SubExpr<S, A> {
-    use crate::Expr::*;
+    use crate::ExprF::*;
     let V(x, n) = var;
     let under_binder = |y: &Label, e: &SubExpr<_, _>| {
         let n = if x == y { n + 1 } else { *n };
@@ -553,7 +541,7 @@ pub fn subst<S, A>(
     value: &SubExpr<S, A>,
     in_expr: &SubExpr<S, A>,
 ) -> SubExpr<S, A> {
-    use crate::Expr::*;
+    use crate::ExprF::*;
     let under_binder = |y: &Label, e: &SubExpr<_, _>| {
         let V(x, n) = var;
         let n = if x == y { n + 1 } else { *n };
diff --git a/dhall_core/src/parser.rs b/dhall_core/src/parser.rs
index b7ac3f6..343a895 100644
--- a/dhall_core/src/parser.rs
+++ b/dhall_core/src/parser.rs
@@ -13,8 +13,10 @@ use crate::*;
 // their own crate because they are quite general and useful. For now they
 // are here and hopefully you can figure out how they work.
 
-type ParsedText = InterpolatedText<X, Import>;
-type ParsedTextContents = InterpolatedTextContents<X, Import>;
+use crate::ExprF::*;
+
+type ParsedText = InterpolatedText<SubExpr<X, Import>>;
+type ParsedTextContents = InterpolatedTextContents<SubExpr<X, Import>>;
 
 pub type ParseError = pest::error::Error<Rule>;
 
@@ -26,9 +28,9 @@ enum Either<A, B> {
     Right(B),
 }
 
-impl Builtin {
+impl crate::Builtin {
     pub fn parse(s: &str) -> Option<Self> {
-        use self::Builtin::*;
+        use crate::Builtin::*;
         match s {
             "Bool" => Some(Bool),
             "Natural" => Some(Natural),
@@ -267,7 +269,7 @@ make_parser! {
     ));
     rule!(unreserved_label<Label>; children!(
         [label(l)] => {
-            if Builtin::parse(&String::from(&l)).is_some() {
+            if crate::Builtin::parse(&String::from(&l)).is_some() {
                 Err(
                     format!("Builtin names are not allowed as bound variables")
                 )?
@@ -526,13 +528,13 @@ make_parser! {
 
     rule!(import<ParsedExpr> as expression; children!(
         [import_hashed(location_hashed)] => {
-            bx(Expr::Embed(Import {
+            bx(Embed(Import {
                 mode: ImportMode::Code,
                 location_hashed
             }))
         },
         [import_hashed(location_hashed), Text(_)] => {
-            bx(Expr::Embed(Import {
+            bx(Embed(Import {
                 mode: ImportMode::RawText,
                 location_hashed
             }))
@@ -541,13 +543,13 @@ make_parser! {
 
     rule!(lambda_expression<ParsedExpr> as expression; children!(
         [unreserved_label(l), expression(typ), expression(body)] => {
-            bx(Expr::Lam(l, typ, body))
+            bx(Lam(l, typ, body))
         }
     ));
 
     rule!(ifthenelse_expression<ParsedExpr> as expression; children!(
         [expression(cond), expression(left), expression(right)] => {
-            bx(Expr::BoolIf(cond, left, right))
+            bx(BoolIf(cond, left, right))
         }
     ));
 
@@ -555,7 +557,7 @@ make_parser! {
         [let_binding(bindings).., expression(final_expr)] => {
             bindings.fold(
                 final_expr,
-                |acc, x| bx(Expr::Let(x.0, x.1, x.2, acc))
+                |acc, x| bx(Let(x.0, x.1, x.2, acc))
             )
         }
     ));
@@ -569,21 +571,21 @@ make_parser! {
 
     rule!(forall_expression<ParsedExpr> as expression; children!(
         [unreserved_label(l), expression(typ), expression(body)] => {
-            bx(Expr::Pi(l, typ, body))
+            bx(Pi(l, typ, body))
         }
     ));
 
     rule!(arrow_expression<ParsedExpr> as expression; children!(
         [expression(typ), expression(body)] => {
-            bx(Expr::Pi("_".into(), typ, body))
+            bx(Pi("_".into(), typ, body))
         }
     ));
 
     rule!(merge_expression<ParsedExpr> as expression; children!(
         [expression(x), expression(y), expression(z)] =>
-            bx(Expr::Merge(x, y, Some(z))),
+            bx(Merge(x, y, Some(z))),
         [expression(x), expression(y)] =>
-            bx(Expr::Merge(x, y, None)),
+            bx(Merge(x, y, None)),
     ));
 
     rule!(List<()>; captured_str!(_) => ());
@@ -591,108 +593,108 @@ make_parser! {
 
     rule!(empty_collection<ParsedExpr> as expression; children!(
         [List(_), expression(t)] => {
-            bx(Expr::EmptyListLit(t))
+            bx(EmptyListLit(t))
         },
         [Optional(_), expression(t)] => {
-            bx(Expr::EmptyOptionalLit(t))
+            bx(EmptyOptionalLit(t))
         },
     ));
 
     rule!(non_empty_optional<ParsedExpr> as expression; children!(
         [expression(x), Optional(_), expression(t)] => {
-            rc(Expr::Annot(rc(Expr::NEOptionalLit(x)), t))
+            rc(Annot(rc(NEOptionalLit(x)), t))
         }
     ));
 
     rule!(import_alt_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::ImportAlt;
-            rest.fold(first, |acc, e| bx(Expr::BinOp(o, acc, e)))
+            let o = crate::BinOp::ImportAlt;
+            rest.fold(first, |acc, e| bx(BinOp(o, acc, e)))
         },
     ));
     rule!(or_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::BoolOr;
-            rest.fold(first, |acc, e| bx(Expr::BinOp(o, acc, e)))
+            let o = crate::BinOp::BoolOr;
+            rest.fold(first, |acc, e| bx(BinOp(o, acc, e)))
         },
     ));
     rule!(plus_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::NaturalPlus;
-            rest.fold(first, |acc, e| bx(Expr::BinOp(o, acc, e)))
+            let o = crate::BinOp::NaturalPlus;
+            rest.fold(first, |acc, e| bx(BinOp(o, acc, e)))
         },
     ));
     rule!(text_append_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::TextAppend;
-            rest.fold(first, |acc, e| bx(Expr::BinOp(o, acc, e)))
+            let o = crate::BinOp::TextAppend;
+            rest.fold(first, |acc, e| bx(BinOp(o, acc, e)))
         },
     ));
     rule!(list_append_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::ListAppend;
-            rest.fold(first, |acc, e| bx(Expr::BinOp(o, acc, e)))
+            let o = crate::BinOp::ListAppend;
+            rest.fold(first, |acc, e| bx(BinOp(o, acc, e)))
         },
     ));
     rule!(and_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::BoolAnd;
-            rest.fold(first, |acc, e| bx(Expr::BinOp(o, acc, e)))
+            let o = crate::BinOp::BoolAnd;
+            rest.fold(first, |acc, e| bx(BinOp(o, acc, e)))
         },
     ));
     rule!(combine_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::Combine;
-            rest.fold(first, |acc, e| bx(Expr::BinOp(o, acc, e)))
+            let o = crate::BinOp::Combine;
+            rest.fold(first, |acc, e| bx(BinOp(o, acc, e)))
         },
     ));
     rule!(prefer_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::Prefer;
-            rest.fold(first, |acc, e| bx(Expr::BinOp(o, acc, e)))
+            let o = crate::BinOp::Prefer;
+            rest.fold(first, |acc, e| bx(BinOp(o, acc, e)))
         },
     ));
     rule!(combine_types_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::CombineTypes;
-            rest.fold(first, |acc, e| bx(Expr::BinOp(o, acc, e)))
+            let o = crate::BinOp::CombineTypes;
+            rest.fold(first, |acc, e| bx(BinOp(o, acc, e)))
         },
     ));
     rule!(times_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::NaturalTimes;
-            rest.fold(first, |acc, e| bx(Expr::BinOp(o, acc, e)))
+            let o = crate::BinOp::NaturalTimes;
+            rest.fold(first, |acc, e| bx(BinOp(o, acc, e)))
         },
     ));
     rule!(equal_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::BoolEQ;
-            rest.fold(first, |acc, e| bx(Expr::BinOp(o, acc, e)))
+            let o = crate::BinOp::BoolEQ;
+            rest.fold(first, |acc, e| bx(BinOp(o, acc, e)))
         },
     ));
     rule!(not_equal_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::BoolNE;
-            rest.fold(first, |acc, e| bx(Expr::BinOp(o, acc, e)))
+            let o = crate::BinOp::BoolNE;
+            rest.fold(first, |acc, e| bx(BinOp(o, acc, e)))
         },
     ));
 
     rule!(annotated_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(e), expression(annot)] => {
-            bx(Expr::Annot(e, annot))
+            bx(Annot(e, annot))
         },
     ));
 
@@ -700,22 +702,22 @@ make_parser! {
         [expression(e)] => e,
         [expression(first), expression(second)] => {
             match first.as_ref() {
-                Expr::Builtin(Builtin::OptionalNone) =>
-                    bx(Expr::EmptyOptionalLit(second)),
-                Expr::Builtin(Builtin::OptionalSome) =>
-                    bx(Expr::NEOptionalLit(second)),
-                _ => bx(Expr::App(first, vec![second])),
+                Builtin(crate::Builtin::OptionalNone) =>
+                    bx(EmptyOptionalLit(second)),
+                Builtin(crate::Builtin::OptionalSome) =>
+                    bx(NEOptionalLit(second)),
+                _ => bx(App(first, vec![second])),
             }
         },
         [expression(first), expression(second), expression(rest)..] => {
             match first.as_ref() {
-                Expr::Builtin(Builtin::OptionalNone) =>
-                    bx(Expr::App(bx(Expr::EmptyOptionalLit(second)),
+                Builtin(crate::Builtin::OptionalNone) =>
+                    bx(App(bx(EmptyOptionalLit(second)),
                                  rest.collect())),
-                Expr::Builtin(Builtin::OptionalSome) =>
-                    bx(Expr::App(bx(Expr::NEOptionalLit(second)),
+                Builtin(crate::Builtin::OptionalSome) =>
+                    bx(App(bx(NEOptionalLit(second)),
                                  rest.collect())),
-                _ => bx(Expr::App(first,
+                _ => bx(App(first,
                                   std::iter::once(second)
                                     .chain(rest)
                                     .collect())),
@@ -727,8 +729,8 @@ make_parser! {
         [expression(e)] => e,
         [expression(first), selector(rest)..] => {
             rest.fold(first, |acc, e| match e {
-                Either::Left(l) => bx(Expr::Field(acc, l)),
-                Either::Right(ls) => bx(Expr::Projection(acc, ls)),
+                Either::Left(l) => bx(Field(acc, l)),
+                Either::Right(ls) => bx(Projection(acc, ls)),
             })
         }
     ));
@@ -743,66 +745,66 @@ make_parser! {
     ));
 
     rule!(literal_expression<ParsedExpr> as expression; children!(
-        [double_literal(n)] => bx(Expr::DoubleLit(n)),
+        [double_literal(n)] => bx(DoubleLit(n)),
         [minus_infinity_literal(n)] =>
-            bx(Expr::DoubleLit(std::f64::NEG_INFINITY.into())),
+            bx(DoubleLit(std::f64::NEG_INFINITY.into())),
         [plus_infinity_literal(n)] =>
-            bx(Expr::DoubleLit(std::f64::INFINITY.into())),
-        [NaN(n)] => bx(Expr::DoubleLit(std::f64::NAN.into())),
-        [natural_literal(n)] => bx(Expr::NaturalLit(n)),
-        [integer_literal(n)] => bx(Expr::IntegerLit(n)),
-        [double_quote_literal(s)] => bx(Expr::TextLit(s)),
-        [single_quote_literal(s)] => bx(Expr::TextLit(s)),
+            bx(DoubleLit(std::f64::INFINITY.into())),
+        [NaN(n)] => bx(DoubleLit(std::f64::NAN.into())),
+        [natural_literal(n)] => bx(NaturalLit(n)),
+        [integer_literal(n)] => bx(IntegerLit(n)),
+        [double_quote_literal(s)] => bx(TextLit(s)),
+        [single_quote_literal(s)] => bx(TextLit(s)),
         [expression(e)] => e,
     ));
 
     rule!(identifier<ParsedExpr> as expression; children!(
         [label(l), natural_literal(idx)] => {
             let name = String::from(&l);
-            match Builtin::parse(name.as_str()) {
-                Some(b) => bx(Expr::Builtin(b)),
+            match crate::Builtin::parse(name.as_str()) {
+                Some(b) => bx(Builtin(b)),
                 None => match name.as_str() {
-                    "True" => bx(Expr::BoolLit(true)),
-                    "False" => bx(Expr::BoolLit(false)),
-                    "Type" => bx(Expr::Const(Const::Type)),
-                    "Kind" => bx(Expr::Const(Const::Kind)),
-                    _ => bx(Expr::Var(V(l, idx))),
+                    "True" => bx(BoolLit(true)),
+                    "False" => bx(BoolLit(false)),
+                    "Type" => bx(Const(crate::Const::Type)),
+                    "Kind" => bx(Const(crate::Const::Kind)),
+                    _ => bx(Var(V(l, idx))),
                 }
             }
         },
         [label(l)] => {
             let name = String::from(&l);
-            match Builtin::parse(name.as_str()) {
-                Some(b) => bx(Expr::Builtin(b)),
+            match crate::Builtin::parse(name.as_str()) {
+                Some(b) => bx(Builtin(b)),
                 None => match name.as_str() {
-                    "True" => bx(Expr::BoolLit(true)),
-                    "False" => bx(Expr::BoolLit(false)),
-                    "Type" => bx(Expr::Const(Const::Type)),
-                    "Kind" => bx(Expr::Const(Const::Kind)),
-                    _ => bx(Expr::Var(V(l, 0))),
+                    "True" => bx(BoolLit(true)),
+                    "False" => bx(BoolLit(false)),
+                    "Type" => bx(Const(crate::Const::Type)),
+                    "Kind" => bx(Const(crate::Const::Kind)),
+                    _ => bx(Var(V(l, 0))),
                 }
             }
         },
     ));
 
     rule!(empty_record_literal<ParsedExpr> as expression;
-        captured_str!(_) => bx(Expr::RecordLit(BTreeMap::new()))
+        captured_str!(_) => bx(RecordLit(BTreeMap::new()))
     );
 
     rule!(empty_record_type<ParsedExpr> as expression;
-        captured_str!(_) => bx(Expr::RecordType(BTreeMap::new()))
+        captured_str!(_) => bx(RecordType(BTreeMap::new()))
     );
 
     rule!(non_empty_record_type_or_literal<ParsedExpr> as expression; children!(
         [label(first_label), non_empty_record_type(rest)] => {
             let (first_expr, mut map) = rest;
             map.insert(first_label, first_expr);
-            bx(Expr::RecordType(map))
+            bx(RecordType(map))
         },
         [label(first_label), non_empty_record_literal(rest)] => {
             let (first_expr, mut map) = rest;
             map.insert(first_label, first_expr);
-            bx(Expr::RecordLit(map))
+            bx(RecordLit(map))
         },
     ));
 
@@ -830,13 +832,13 @@ make_parser! {
 
     rule!(union_type_or_literal<ParsedExpr> as expression; children!(
         [empty_union_type(_)] => {
-            bx(Expr::UnionType(BTreeMap::new()))
+            bx(UnionType(BTreeMap::new()))
         },
         [non_empty_union_type_or_literal((Some((l, e)), entries))] => {
-            bx(Expr::UnionLit(l, e, entries))
+            bx(UnionLit(l, e, entries))
         },
         [non_empty_union_type_or_literal((None, entries))] => {
-            bx(Expr::UnionType(entries))
+            bx(UnionType(entries))
         },
     ));
 
@@ -869,7 +871,7 @@ make_parser! {
     ));
 
     rule!(non_empty_list_literal<ParsedExpr> as expression; children!(
-        [expression(items)..] => bx(Expr::NEListLit(items.collect()))
+        [expression(items)..] => bx(NEListLit(items.collect()))
     ));
 
     rule!(final_expression<ParsedExpr> as expression; children!(
@@ -885,7 +887,7 @@ pub fn parse_expr(s: &str) -> ParseResult<ParsedExpr> {
         ParsedValue::expression(e) => Ok(e),
         _ => unreachable!(),
     }
-    // Ok(bx(Expr::BoolLit(false)))
+    // Ok(bx(BoolLit(false)))
 }
 
 #[test]
diff --git a/dhall_core/src/printer.rs b/dhall_core/src/printer.rs
index b153d1b..b7d7506 100644
--- a/dhall_core/src/printer.rs
+++ b/dhall_core/src/printer.rs
@@ -35,7 +35,7 @@ impl<S, A: Display> Expr<S, A> {
         f: &mut fmt::Formatter,
         phase: PrintPhase,
     ) -> Result<(), fmt::Error> {
-        use crate::Expr::*;
+        use crate::ExprF::*;
         use PrintPhase::*;
         match self {
             _ if phase == Paren => {
@@ -143,7 +143,7 @@ impl<S, A: Display> Expr<S, A> {
                 write!(f, " : ")?;
                 b.fmt(f)?;
             }
-            Expr::BinOp(op, a, b) => {
+            ExprF::BinOp(op, a, b) => {
                 // Precedence is magically handled by the ordering of BinOps.
                 if phase > PrintPhase::BinOp(*op) {
                     return self.fmt_phase(f, Paren);
@@ -152,7 +152,7 @@ impl<S, A: Display> Expr<S, A> {
                 write!(f, " {} ", op)?;
                 b.fmt_phase(f, PrintPhase::BinOp(*op))?;
             }
-            Expr::App(a, args) => {
+            ExprF::App(a, args) => {
                 if phase > PrintPhase::App {
                     return self.fmt_phase(f, Paren);
                 }
@@ -239,7 +239,7 @@ where
     f.write_str(close)
 }
 
-impl<S, A: Display> Display for InterpolatedText<S, A> {
+impl<SubExpr: Display + Clone> Display for InterpolatedText<SubExpr> {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         f.write_str("\"")?;
         for x in self.iter() {
diff --git a/dhall_core/src/text.rs b/dhall_core/src/text.rs
index eef0797..d915553 100644
--- a/dhall_core/src/text.rs
+++ b/dhall_core/src/text.rs
@@ -1,17 +1,16 @@
-use crate::*;
 use std::iter::FromIterator;
 use std::ops::Add;
 
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub struct InterpolatedText<Note, Embed> {
+pub struct InterpolatedText<SubExpr> {
     head: String,
-    tail: Vec<(SubExpr<Note, Embed>, String)>,
+    tail: Vec<(SubExpr, String)>,
 }
 
-impl<N, E> From<(String, Vec<(SubExpr<N, E>, String)>)>
-    for InterpolatedText<N, E>
+impl<SubExpr> From<(String, Vec<(SubExpr, String)>)>
+    for InterpolatedText<SubExpr>
 {
-    fn from(x: (String, Vec<(SubExpr<N, E>, String)>)) -> Self {
+    fn from(x: (String, Vec<(SubExpr, String)>)) -> Self {
         InterpolatedText {
             head: x.0,
             tail: x.1,
@@ -19,7 +18,7 @@ impl<N, E> From<(String, Vec<(SubExpr<N, E>, String)>)>
     }
 }
 
-impl<N, E> From<String> for InterpolatedText<N, E> {
+impl<SubExpr> From<String> for InterpolatedText<SubExpr> {
     fn from(s: String) -> Self {
         InterpolatedText {
             head: s,
@@ -29,15 +28,15 @@ impl<N, E> From<String> for InterpolatedText<N, E> {
 }
 
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub enum InterpolatedTextContents<Note, Embed> {
+pub enum InterpolatedTextContents<SubExpr> {
     Text(String),
-    Expr(SubExpr<Note, Embed>),
+    Expr(SubExpr),
 }
 
-impl<N, E> InterpolatedText<N, E> {
-    pub fn map<N2, E2, F>(&self, mut f: F) -> InterpolatedText<N2, E2>
+impl<SubExpr: Clone> InterpolatedText<SubExpr> {
+    pub fn map<SubExpr2, F>(&self, mut f: F) -> InterpolatedText<SubExpr2>
     where
-        F: FnMut(&SubExpr<N, E>) -> SubExpr<N2, E2>,
+        F: FnMut(&SubExpr) -> SubExpr2,
     {
         InterpolatedText {
             head: self.head.clone(),
@@ -47,7 +46,7 @@ impl<N, E> InterpolatedText<N, E> {
 
     pub fn iter<'a>(
         &'a self,
-    ) -> impl Iterator<Item = InterpolatedTextContents<N, E>> + 'a {
+    ) -> impl Iterator<Item = InterpolatedTextContents<SubExpr>> + 'a {
         use std::iter::once;
         once(InterpolatedTextContents::Text(self.head.clone())).chain(
             self.tail.iter().flat_map(|(e, s)| {
@@ -58,12 +57,12 @@ impl<N, E> InterpolatedText<N, E> {
     }
 }
 
-impl<'a, N: 'a, E: 'a> FromIterator<InterpolatedTextContents<N, E>>
-    for InterpolatedText<N, E>
+impl<'a, SubExpr: Clone + 'a> FromIterator<InterpolatedTextContents<SubExpr>>
+    for InterpolatedText<SubExpr>
 {
     fn from_iter<T>(iter: T) -> Self
     where
-        T: IntoIterator<Item = InterpolatedTextContents<N, E>>,
+        T: IntoIterator<Item = InterpolatedTextContents<SubExpr>>,
     {
         let mut res = InterpolatedText {
             head: "".to_owned(),
@@ -83,9 +82,9 @@ impl<'a, N: 'a, E: 'a> FromIterator<InterpolatedTextContents<N, E>>
     }
 }
 
-impl<N, E> Add for &InterpolatedText<N, E> {
-    type Output = InterpolatedText<N, E>;
-    fn add(self, rhs: &InterpolatedText<N, E>) -> Self::Output {
+impl<SubExpr: Clone> Add for &InterpolatedText<SubExpr> {
+    type Output = InterpolatedText<SubExpr>;
+    fn add(self, rhs: &InterpolatedText<SubExpr>) -> Self::Output {
         self.iter().chain(rhs.iter()).collect()
     }
 }
-- 
cgit v1.2.3


From 737472abf9c0ca2030ab8c2bb0b1d4af41167183 Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Sun, 31 Mar 2019 19:37:29 +0200
Subject: Remove evil Deref impl

---
 dhall_core/src/core.rs    | 17 ++++++-----------
 dhall_core/src/printer.rs | 10 ++++++++++
 2 files changed, 16 insertions(+), 11 deletions(-)

(limited to 'dhall_core/src')

diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index 2d11068..3f01b55 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -305,30 +305,25 @@ impl<S: Clone, A: Clone> Expr<S, Expr<S, A>> {
 }
 
 impl<N, E> Clone for SubExpr<N, E> {
+    #[inline(always)]
     fn clone(&self) -> Self {
         SubExpr(Rc::clone(&self.0))
     }
 }
 
-impl<N, E> std::ops::Deref for SubExpr<N, E> {
-    type Target = Rc<Expr<N, E>>;
+impl<N, E> SubExpr<N, E> {
     #[inline(always)]
-    fn deref(&self) -> &Self::Target {
-        &self.0
+    pub fn as_ref(&self) -> &Expr<N, E> {
+        self.0.as_ref()
     }
 }
 
-// impl<N, E> SubExpr<N, E> {
-//     pub fn as_ref(&self) -> &Expr<N, E> {
-//         self.0.as_ref()
-//     }
-// }
-
 // Remains of a previous life, where everything was in Boxes
 pub fn bx<N, E>(x: Expr<N, E>) -> SubExpr<N, E> {
     SubExpr(Rc::new(x))
 }
 
+// Should probably rename this too
 pub fn rc<N, E>(x: Expr<N, E>) -> SubExpr<N, E> {
     SubExpr(Rc::new(x))
 }
@@ -414,7 +409,7 @@ where
         ExprF::Note(_, e) => {
             map_subexpr_rc_binder(e, map_expr, map_under_binder)
         }
-        _ => rc(map_subexpr(
+        e => rc(map_subexpr(
             e,
             map_expr,
             |_| unreachable!(),
diff --git a/dhall_core/src/printer.rs b/dhall_core/src/printer.rs
index b7d7506..fb3b8e8 100644
--- a/dhall_core/src/printer.rs
+++ b/dhall_core/src/printer.rs
@@ -217,6 +217,16 @@ impl<S, A: Display> Expr<S, A> {
     }
 }
 
+impl<S, A: Display> SubExpr<S, A> {
+    fn fmt_phase(
+        &self,
+        f: &mut fmt::Formatter,
+        phase: PrintPhase,
+    ) -> Result<(), fmt::Error> {
+        self.0.as_ref().fmt_phase(f, phase)
+    }
+}
+
 fn fmt_list<T, I, F>(
     open: &str,
     sep: &str,
-- 
cgit v1.2.3


From 83784947be0a1da6da316d0b3659cc9883b27d48 Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Sun, 31 Mar 2019 19:42:35 +0200
Subject: Generalize type of map

---
 dhall_core/src/core.rs | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)

(limited to 'dhall_core/src')

diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index 3f01b55..456a68c 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -337,20 +337,22 @@ fn add_ui(u: usize, i: isize) -> usize {
 }
 
 /// Map over the immediate children of the passed Expr
-pub fn map_subexpr<S, T, A, B, F1, F2, F3, F4, F5>(
-    e: &Expr<S, A>,
+pub fn map_subexpr<SE1, SE2, S, T, A, B, F1, F2, F3, F4, F5>(
+    e: &ExprF<SE1, S, A>,
     map: F1,
     map_note: F2,
     map_embed: F3,
     map_label: F4,
     map_under_binder: F5,
-) -> Expr<T, B>
+) -> ExprF<SE2, T, B>
 where
-    F1: Fn(&SubExpr<S, A>) -> SubExpr<T, B>,
+    SE1: Clone,
+    SE2: Clone,
+    F1: Fn(&SE1) -> SE2,
     F2: FnOnce(&S) -> T,
     F3: FnOnce(&A) -> B,
     F4: Fn(&Label) -> Label,
-    F5: FnOnce(&Label, &SubExpr<S, A>) -> SubExpr<T, B>,
+    F5: FnOnce(&Label, &SE1) -> SE2,
 {
     use crate::ExprF::*;
     let map = &map;
-- 
cgit v1.2.3


From 62970fd2010b01260cf45a1f2a6a582c6a8c0c12 Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Sun, 31 Mar 2019 21:04:10 +0200
Subject: Make Expr generic in Label

---
 dhall_core/src/core.rs    | 24 +++++++++++++-----------
 dhall_core/src/printer.rs |  2 +-
 2 files changed, 14 insertions(+), 12 deletions(-)

(limited to 'dhall_core/src')

diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index 456a68c..5ac3db6 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -100,7 +100,7 @@ pub enum Const {
 /// appear as a numeric suffix.
 ///
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub struct V(pub Label, pub usize);
+pub struct V<Label>(pub Label, pub usize);
 
 // Definition order must match precedence order for
 // pretty-printing to work correctly
@@ -173,19 +173,19 @@ pub type DhallExpr = ResolvedExpr;
 #[derive(Debug, PartialEq, Eq)]
 pub struct SubExpr<Note, Embed>(pub Rc<Expr<Note, Embed>>);
 
-pub type Expr<Note, Embed> = ExprF<SubExpr<Note, Embed>, Note, Embed>;
+pub type Expr<Note, Embed> = ExprF<SubExpr<Note, Embed>, Label, Note, Embed>;
 
 /// Syntax tree for expressions
 // Having the recursion out of the enum definition enables writing
 // much more generic code and improves pattern-matching behind
 // smart pointers.
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub enum ExprF<SubExpr, Note, Embed> {
+pub enum ExprF<SubExpr, Label, Note, Embed> {
     ///  `Const c                                  ~  c`
     Const(Const),
     ///  `Var (V x 0)                              ~  x`<br>
     ///  `Var (V x n)                              ~  x@n`
-    Var(V),
+    Var(V<Label>),
     ///  `Lam x     A b                            ~  λ(x : A) -> b`
     Lam(Label, SubExpr, SubExpr),
     ///  `Pi "_" A B                               ~        A  -> B`
@@ -337,22 +337,24 @@ fn add_ui(u: usize, i: isize) -> usize {
 }
 
 /// Map over the immediate children of the passed Expr
-pub fn map_subexpr<SE1, SE2, S, T, A, B, F1, F2, F3, F4, F5>(
-    e: &ExprF<SE1, S, A>,
+pub fn map_subexpr<SE1, SE2, L1, L2, S, T, A, B, F1, F2, F3, F4, F5>(
+    e: &ExprF<SE1, L1, S, A>,
     map: F1,
     map_note: F2,
     map_embed: F3,
     map_label: F4,
     map_under_binder: F5,
-) -> ExprF<SE2, T, B>
+) -> ExprF<SE2, L2, T, B>
 where
+    L1: Ord,
+    L2: Ord,
     SE1: Clone,
     SE2: Clone,
     F1: Fn(&SE1) -> SE2,
     F2: FnOnce(&S) -> T,
     F3: FnOnce(&A) -> B,
-    F4: Fn(&Label) -> Label,
-    F5: FnOnce(&Label, &SE1) -> SE2,
+    F4: Fn(&L1) -> L2,
+    F5: FnOnce(&L1, &SE1) -> SE2,
 {
     use crate::ExprF::*;
     let map = &map;
@@ -505,7 +507,7 @@ where
 ///
 pub fn shift<S, A>(
     delta: isize,
-    var: &V,
+    var: &V<Label>,
     in_expr: &SubExpr<S, A>,
 ) -> SubExpr<S, A> {
     use crate::ExprF::*;
@@ -534,7 +536,7 @@ pub fn shift<S, A>(
 /// ```
 ///
 pub fn subst<S, A>(
-    var: &V,
+    var: &V<Label>,
     value: &SubExpr<S, A>,
     in_expr: &SubExpr<S, A>,
 ) -> SubExpr<S, A> {
diff --git a/dhall_core/src/printer.rs b/dhall_core/src/printer.rs
index fb3b8e8..746b863 100644
--- a/dhall_core/src/printer.rs
+++ b/dhall_core/src/printer.rs
@@ -462,7 +462,7 @@ impl Display for Scheme {
     }
 }
 
-impl Display for V {
+impl<Label: Display> Display for V<Label> {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         let V(x, n) = self;
         x.fmt(f)?;
-- 
cgit v1.2.3


From 57ccbfa16f48f373ac5545b8523de56fb996ba3e Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Mon, 1 Apr 2019 00:17:44 +0200
Subject: Refactor and clarify various map methods

---
 dhall_core/src/core.rs | 349 +++++++++++++++++++++++++++++++++----------------
 dhall_core/src/text.rs |  24 +++-
 2 files changed, 254 insertions(+), 119 deletions(-)

(limited to 'dhall_core/src')

diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index 5ac3db6..0d4789a 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -259,13 +259,12 @@ impl<S, A> Expr<S, A> {
         F3: FnOnce(&A) -> B,
         F4: Fn(&Label) -> Label,
     {
-        map_subexpr(
-            self,
+        self.map_ref(
             |x| rc(map_expr(x.as_ref())),
+            |_, x| rc(map_expr(x.as_ref())),
             map_note,
             map_embed,
             map_label,
-            |_, x| rc(map_expr(x.as_ref())),
         )
     }
 
@@ -304,11 +303,205 @@ impl<S: Clone, A: Clone> Expr<S, Expr<S, A>> {
     }
 }
 
-impl<N, E> Clone for SubExpr<N, E> {
+impl<SE, L, N, E> ExprF<SE, L, N, E> {
     #[inline(always)]
-    fn clone(&self) -> Self {
-        SubExpr(Rc::clone(&self.0))
+    pub fn as_ref(&self) -> ExprF<&SE, &L, &N, &E>
+    where
+        L: Ord,
+    {
+        fn opt<T>(x: &Option<T>) -> Option<&T> {
+            x.as_ref()
+        }
+        fn vec<T>(x: &Vec<T>) -> Vec<&T> {
+            x.iter().collect()
+        }
+        fn btmap<L: Ord, SE>(x: &BTreeMap<L, SE>) -> BTreeMap<&L, &SE> {
+            x.iter().collect()
+        }
+
+        use crate::ExprF::*;
+        match self {
+            Var(V(l, n)) => Var(V(l, *n)),
+            Lam(l, t, b) => Lam(l, t, b),
+            Pi(l, t, b) => Pi(l, t, b),
+            Let(l, t, a, b) => Let(l, opt(t), a, b),
+            App(f, args) => App(f, vec(args)),
+            Annot(x, t) => Annot(x, 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.as_ref()),
+            BinOp(o, x, y) => BinOp(*o, x, y),
+            BoolIf(b, t, f) => BoolIf(b, t, f),
+            EmptyListLit(t) => EmptyListLit(t),
+            NEListLit(es) => NEListLit(vec(es)),
+            EmptyOptionalLit(t) => EmptyOptionalLit(t),
+            NEOptionalLit(e) => NEOptionalLit(e),
+            RecordType(kts) => RecordType(btmap(kts)),
+            RecordLit(kvs) => RecordLit(btmap(kvs)),
+            UnionType(kts) => UnionType(btmap(kts)),
+            UnionLit(k, v, kvs) => UnionLit(k, v, btmap(kvs)),
+            Merge(x, y, t) => Merge(x, y, opt(t)),
+            Field(e, l) => Field(e, l),
+            Projection(e, ls) => Projection(e, vec(ls)),
+            Note(n, e) => Note(n, e),
+            Embed(a) => Embed(a),
+        }
+    }
+
+    #[inline(always)]
+    pub fn map<SE2, L2, N2, E2, F1, F2, F3, F4, F5>(
+        self,
+        map_subexpr: F1,
+        map_under_binder: F2,
+        map_note: F3,
+        map_embed: F4,
+        mut map_label: F5,
+    ) -> ExprF<SE2, L2, N2, E2>
+    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,
+    {
+        let mut map = map_subexpr;
+        fn vec<T, U, F: FnMut(T) -> U>(x: Vec<T>, f: F) -> Vec<U> {
+            x.into_iter().map(f).collect()
+        }
+        fn btmap<K, L, T, U, FK, FV>(
+            x: BTreeMap<K, T>,
+            mut fk: FK,
+            mut fv: FV,
+        ) -> BTreeMap<L, U>
+        where
+            K: Ord,
+            L: Ord,
+            FK: FnMut(K) -> L,
+            FV: FnMut(T) -> U,
+        {
+            x.into_iter().map(|(k, v)| (fk(k), fv(v))).collect()
+        }
+
+        use crate::ExprF::*;
+        match self {
+            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)
+            }
+            Pi(l, t, b) => {
+                let b = map_under_binder(&l, b);
+                Pi(map_label(l), map(t), b)
+            }
+            Let(l, t, a, b) => {
+                let b = map_under_binder(&l, b);
+                Let(map_label(l), t.map(&mut map), map(a), b)
+            }
+            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.map(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)),
+            EmptyOptionalLit(t) => EmptyOptionalLit(map(t)),
+            NEOptionalLit(e) => NEOptionalLit(map(e)),
+            RecordType(kts) => RecordType(btmap(kts, map_label, map)),
+            RecordLit(kvs) => RecordLit(btmap(kvs, map_label, map)),
+            UnionType(kts) => UnionType(btmap(kts, map_label, map)),
+            UnionLit(k, v, kvs) => {
+                UnionLit(map_label(k), map(v), btmap(kvs, map_label, map))
+            }
+            Merge(x, y, t) => Merge(map(x), map(y), t.map(map)),
+            Field(e, l) => Field(map(e), map_label(l)),
+            Projection(e, ls) => Projection(map(e), vec(ls, map_label)),
+            Note(n, e) => Note(map_note(n), map(e)),
+            Embed(a) => Embed(map_embed(a)),
+        }
+    }
+
+    #[inline(always)]
+    pub fn map_ref<SE2, L2, N2, E2, F1, F2, F3, F4, F5>(
+        &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(&SE) -> SE2,
+        F2: FnOnce(&L, &SE) -> SE2,
+        F3: FnOnce(&N) -> N2,
+        F4: FnOnce(&E) -> E2,
+        F5: FnMut(&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,
+        )
     }
+
+    // #[inline(always)]
+    // pub fn zip<SE2, L2, N2, E2>(
+    //     self,
+    //     other: ExprF<SE2, L2, N2, E2>
+    // ) -> Option<ExprF<(SE, SE2), (L, L2), (N, N2), (E, E2)>>
+    // where
+    //     L: Ord,
+    //     L2: Ord,
+    // {
+    //     // What to do with Var ?
+    //     use crate::ExprF::*;
+    //     match (self, other) {
+    //         // Var(V(l, n)) => Var(V(map_label(l), n)),
+    //         // Lam(l, t, b) => {
+    //         // Pi(l, t, b) => {
+    //         // Let(l, t, a, b) => {
+    //         // App(f, args) => App(map(f), vec(args, map)),
+    //         // Annot(x, t) => Annot(map(x), map(t)),
+    //         (Const(x), Const(y)) if x == y => Some(Const(x)),
+    //         (Builtin(x), Builtin(y)) if x == y => Some(Builtin(x)),
+    //         (BoolLit(x), BoolLit(y)) if x == y => Some(BoolLit(x)),
+    //         (NaturalLit(x), NaturalLit(y)) if x == y => Some(NaturalLit(x)),
+    //         (IntegerLit(x), IntegerLit(y)) if x == y => Some(IntegerLit(x)),
+    //         (DoubleLit(x), DoubleLit(y)) if x == y => Some(DoubleLit(x)),
+    //         // TextLit(t) => TextLit(t.map(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)),
+    //         // EmptyOptionalLit(t) => EmptyOptionalLit(map(t)),
+    //         // NEOptionalLit(e) => NEOptionalLit(map(e)),
+    //         // RecordType(kts) => RecordType(btmap(kts, map_label, map)),
+    //         // RecordLit(kvs) => RecordLit(btmap(kvs, map_label, map)),
+    //         // UnionType(kts) => UnionType(btmap(kts, map_label, map)),
+    //         // UnionLit(k, v, kvs) => {
+    //         // Merge(x, y, t) => Merge(map(x), map(y), t.map(map)),
+    //         // Field(e, l) => Field(map(e), map_label(l)),
+    //         // Projection(e, ls) => Projection(map(e), vec(ls, map_label)),
+    //         // Note(n, e) => Note(map_note(n), map(e)),
+    //         // Embed(a) => Embed(map_embed(a)),
+    //     }
+    // }
 }
 
 impl<N, E> SubExpr<N, E> {
@@ -316,6 +509,40 @@ impl<N, E> SubExpr<N, E> {
     pub fn as_ref(&self) -> &Expr<N, E> {
         self.0.as_ref()
     }
+
+    pub fn map_ref<F1, F2>(&self, map_expr: F1, map_under_binder: F2) -> Self
+    where
+        F1: FnMut(&Self) -> Self,
+        F2: FnOnce(&Label, &Self) -> Self,
+    {
+        match self.as_ref() {
+            ExprF::Embed(_) => SubExpr::clone(self),
+            // Recursive call
+            ExprF::Note(_, e) => e.map_ref(map_expr, map_under_binder),
+            // Call ExprF::map_ref
+            e => rc(e.map_ref(
+                map_expr,
+                map_under_binder,
+                |_| unreachable!(),
+                |_| unreachable!(),
+                Label::clone,
+            )),
+        }
+    }
+
+    pub fn map_ref_simple<F1>(&self, map_expr: F1) -> Self
+    where
+        F1: Fn(&Self) -> Self,
+    {
+        self.map_ref(&map_expr, |_, e| map_expr(e))
+    }
+}
+
+impl<N, E> Clone for SubExpr<N, E> {
+    #[inline(always)]
+    fn clone(&self) -> Self {
+        SubExpr(Rc::clone(&self.0))
+    }
 }
 
 // Remains of a previous life, where everything was in Boxes
@@ -336,104 +563,6 @@ fn add_ui(u: usize, i: isize) -> usize {
     }
 }
 
-/// Map over the immediate children of the passed Expr
-pub fn map_subexpr<SE1, SE2, L1, L2, S, T, A, B, F1, F2, F3, F4, F5>(
-    e: &ExprF<SE1, L1, S, A>,
-    map: F1,
-    map_note: F2,
-    map_embed: F3,
-    map_label: F4,
-    map_under_binder: F5,
-) -> ExprF<SE2, L2, T, B>
-where
-    L1: Ord,
-    L2: Ord,
-    SE1: Clone,
-    SE2: Clone,
-    F1: Fn(&SE1) -> SE2,
-    F2: FnOnce(&S) -> T,
-    F3: FnOnce(&A) -> B,
-    F4: Fn(&L1) -> L2,
-    F5: FnOnce(&L1, &SE1) -> SE2,
-{
-    use crate::ExprF::*;
-    let map = &map;
-    let opt = |x: &Option<_>| x.as_ref().map(&map);
-    let vec = |x: &Vec<_>| x.iter().map(&map).collect();
-    let btmap = |x: &BTreeMap<_, _>| {
-        x.into_iter().map(|(k, v)| (map_label(k), map(v))).collect()
-    };
-    match e {
-        Const(k) => Const(*k),
-        Var(V(l, n)) => Var(V(map_label(l), *n)),
-        Lam(l, t, b) => Lam(map_label(l), map(t), map_under_binder(l, b)),
-        Pi(l, t, b) => Pi(map_label(l), map(t), map_under_binder(l, b)),
-        App(f, args) => App(map(f), vec(args)),
-        Let(l, t, a, b) => {
-            Let(map_label(l), opt(t), map(a), map_under_binder(l, b))
-        }
-        Annot(x, t) => Annot(map(x), map(t)),
-        Builtin(v) => Builtin(*v),
-        BoolLit(b) => BoolLit(*b),
-        BoolIf(b, t, f) => BoolIf(map(b), map(t), map(f)),
-        NaturalLit(n) => NaturalLit(*n),
-        IntegerLit(n) => IntegerLit(*n),
-        DoubleLit(n) => DoubleLit(*n),
-        TextLit(t) => TextLit(t.map(&map)),
-        BinOp(o, x, y) => BinOp(*o, map(x), map(y)),
-        EmptyListLit(t) => EmptyListLit(map(t)),
-        NEListLit(es) => NEListLit(vec(es)),
-        EmptyOptionalLit(t) => EmptyOptionalLit(map(t)),
-        NEOptionalLit(e) => NEOptionalLit(map(e)),
-        RecordType(kts) => RecordType(btmap(kts)),
-        RecordLit(kvs) => RecordLit(btmap(kvs)),
-        UnionType(kts) => UnionType(btmap(kts)),
-        UnionLit(k, v, kvs) => UnionLit(map_label(k), map(v), btmap(kvs)),
-        Merge(x, y, t) => Merge(map(x), map(y), opt(t)),
-        Field(e, l) => Field(map(e), map_label(l)),
-        Projection(e, ls) => {
-            Projection(map(e), ls.iter().map(&map_label).collect())
-        }
-        Note(n, e) => Note(map_note(n), map(e)),
-        Embed(a) => Embed(map_embed(a)),
-    }
-}
-
-pub fn map_subexpr_rc_binder<S, A, F1, F2>(
-    e: &SubExpr<S, A>,
-    map_expr: F1,
-    map_under_binder: F2,
-) -> SubExpr<S, A>
-where
-    F1: Fn(&SubExpr<S, A>) -> SubExpr<S, A>,
-    F2: FnOnce(&Label, &SubExpr<S, A>) -> SubExpr<S, A>,
-{
-    match e.as_ref() {
-        ExprF::Embed(_) => SubExpr::clone(e),
-        ExprF::Note(_, e) => {
-            map_subexpr_rc_binder(e, map_expr, map_under_binder)
-        }
-        e => rc(map_subexpr(
-            e,
-            map_expr,
-            |_| unreachable!(),
-            |_| unreachable!(),
-            Label::clone,
-            map_under_binder,
-        )),
-    }
-}
-
-pub fn map_subexpr_rc<S, A, F1>(
-    e: &SubExpr<S, A>,
-    map_expr: F1,
-) -> SubExpr<S, A>
-where
-    F1: Fn(&SubExpr<S, A>) -> SubExpr<S, A>,
-{
-    map_subexpr_rc_binder(e, &map_expr, |_, e| map_expr(e))
-}
-
 /// `shift` is used by both normalization and type-checking to avoid variable
 /// capture by shifting variable indices
 ///
@@ -521,11 +650,7 @@ pub fn shift<S, A>(
         Var(V(y, m)) if x == y && n <= m => {
             rc(Var(V(y.clone(), add_ui(*m, delta))))
         }
-        _ => map_subexpr_rc_binder(
-            in_expr,
-            |e| shift(delta, var, e),
-            under_binder,
-        ),
+        _ => in_expr.map_ref(|e| shift(delta, var, e), under_binder),
     }
 }
 
@@ -549,10 +674,6 @@ pub fn subst<S, A>(
     };
     match in_expr.as_ref() {
         Var(v) if var == v => SubExpr::clone(value),
-        _ => map_subexpr_rc_binder(
-            in_expr,
-            |e| subst(var, value, e),
-            under_binder,
-        ),
+        _ => in_expr.map_ref(|e| subst(var, value, e), under_binder),
     }
 }
diff --git a/dhall_core/src/text.rs b/dhall_core/src/text.rs
index d915553..9500f32 100644
--- a/dhall_core/src/text.rs
+++ b/dhall_core/src/text.rs
@@ -33,20 +33,34 @@ pub enum InterpolatedTextContents<SubExpr> {
     Expr(SubExpr),
 }
 
-impl<SubExpr: Clone> InterpolatedText<SubExpr> {
-    pub fn map<SubExpr2, F>(&self, mut f: F) -> InterpolatedText<SubExpr2>
+impl<SubExpr> InterpolatedText<SubExpr> {
+    pub fn map<SubExpr2, F>(self, mut f: F) -> InterpolatedText<SubExpr2>
     where
-        F: FnMut(&SubExpr) -> SubExpr2,
+        F: FnMut(SubExpr) -> SubExpr2,
     {
         InterpolatedText {
             head: self.head.clone(),
-            tail: self.tail.iter().map(|(e, s)| (f(e), s.clone())).collect(),
+            tail: self
+                .tail
+                .into_iter()
+                .map(|(e, s)| (f(e), s.clone()))
+                .collect(),
+        }
+    }
+
+    pub fn as_ref(&self) -> InterpolatedText<&SubExpr> {
+        InterpolatedText {
+            head: self.head.clone(),
+            tail: self.tail.iter().map(|(e, s)| (e, s.clone())).collect(),
         }
     }
 
     pub fn iter<'a>(
         &'a self,
-    ) -> impl Iterator<Item = InterpolatedTextContents<SubExpr>> + 'a {
+    ) -> impl Iterator<Item = InterpolatedTextContents<SubExpr>> + 'a
+    where
+        SubExpr: Clone,
+    {
         use std::iter::once;
         once(InterpolatedTextContents::Text(self.head.clone())).chain(
             self.tail.iter().flat_map(|(e, s)| {
-- 
cgit v1.2.3


From 627287185118482ceb7132f6dedad7111dccf972 Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Sat, 6 Apr 2019 00:06:13 +0200
Subject: Give up on laziness and greatly simplify normalization

---
 dhall_core/src/core.rs | 63 ++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 53 insertions(+), 10 deletions(-)

(limited to 'dhall_core/src')

diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index 0d4789a..db83a1e 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -287,6 +287,15 @@ impl<S, A> Expr<S, A> {
         let recurse = |e: &Self| -> Self { e.map_label(map_label) };
         self.map_shallow(recurse, |x| x.clone(), |x| x.clone(), map_label)
     }
+
+    #[inline(always)]
+    pub fn roll(&self) -> SubExpr<S, A>
+    where
+        S: Clone,
+        A: Clone,
+    {
+        rc(ExprF::clone(self))
+    }
 }
 
 impl<S: Clone, A: Clone> Expr<S, Expr<S, A>> {
@@ -433,8 +442,8 @@ impl<SE, L, N, E> ExprF<SE, L, N, E> {
     }
 
     #[inline(always)]
-    pub fn map_ref<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,
         map_subexpr: F1,
         map_under_binder: F2,
         map_note: F3,
@@ -444,11 +453,11 @@ 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,
     {
         // Not optimal: reallocates all the Vecs and BTreeMaps for nothing.
         self.as_ref().map(
@@ -460,6 +469,27 @@ impl<SE, L, N, E> ExprF<SE, L, N, E> {
         )
     }
 
+    #[inline(always)]
+    pub fn map_ref_simple<'a, SE2, F1>(
+        &'a self,
+        map_subexpr: F1,
+    ) -> ExprF<SE2, L, N, E>
+    where
+        L: Ord,
+        L: Clone,
+        N: Clone,
+        E: Clone,
+        F1: Fn(&'a SE) -> SE2,
+    {
+        self.map_ref(
+            &map_subexpr,
+            |_, e| map_subexpr(e),
+            N::clone,
+            E::clone,
+            L::clone,
+        )
+    }
+
     // #[inline(always)]
     // pub fn zip<SE2, L2, N2, E2>(
     //     self,
@@ -510,10 +540,14 @@ impl<N, E> SubExpr<N, E> {
         self.0.as_ref()
     }
 
-    pub fn map_ref<F1, F2>(&self, map_expr: F1, map_under_binder: F2) -> Self
+    pub fn map_ref<'a, F1, F2>(
+        &'a self,
+        map_expr: F1,
+        map_under_binder: F2,
+    ) -> Self
     where
-        F1: FnMut(&Self) -> Self,
-        F2: FnOnce(&Label, &Self) -> Self,
+        F1: FnMut(&'a Self) -> Self,
+        F2: FnOnce(&'a Label, &'a Self) -> Self,
     {
         match self.as_ref() {
             ExprF::Embed(_) => SubExpr::clone(self),
@@ -536,6 +570,15 @@ impl<N, E> SubExpr<N, E> {
     {
         self.map_ref(&map_expr, |_, e| map_expr(e))
     }
+
+    #[inline(always)]
+    pub fn unroll(&self) -> Expr<N, E>
+    where
+        N: Clone,
+        E: Clone,
+    {
+        ExprF::clone(self.as_ref())
+    }
 }
 
 impl<N, E> Clone for SubExpr<N, E> {
-- 
cgit v1.2.3