From 408bba76bd95a2aabd49046443950a37771f6008 Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Sat, 4 May 2019 16:13:18 +0200
Subject: Thread Spans through the AST

---
 dhall/src/typecheck.rs         |   2 +-
 dhall_proc_macros/src/quote.rs |   2 +-
 dhall_syntax/src/core.rs       |  93 +++++++++++++----------
 dhall_syntax/src/parser.rs     | 162 ++++++++++++++++++++---------------------
 dhall_syntax/src/visitor.rs    |  11 +--
 5 files changed, 141 insertions(+), 129 deletions(-)

diff --git a/dhall/src/typecheck.rs b/dhall/src/typecheck.rs
index ce4ca96..732f7bc 100644
--- a/dhall/src/typecheck.rs
+++ b/dhall/src/typecheck.rs
@@ -350,7 +350,7 @@ fn type_of_const(c: Const) -> Result<Type, TypeError> {
     }
 }
 
-fn type_of_builtin<N, E>(b: Builtin) -> Expr<N, E> {
+fn type_of_builtin<E>(b: Builtin) -> Expr<X, E> {
     use dhall_syntax::Builtin::*;
     match b {
         Bool | Natural | Integer | Double | Text => dhall::expr!(Type),
diff --git a/dhall_proc_macros/src/quote.rs b/dhall_proc_macros/src/quote.rs
index e11bbaa..eaf4946 100644
--- a/dhall_proc_macros/src/quote.rs
+++ b/dhall_proc_macros/src/quote.rs
@@ -11,7 +11,7 @@ pub fn expr(input: proc_macro::TokenStream) -> proc_macro::TokenStream {
     let no_import =
         |_: &Import| -> X { panic!("Don't use import in dhall::expr!()") };
     let expr = expr.map_embed(no_import);
-    let output = quote_expr(&expr.unroll(), &Context::new());
+    let output = quote_expr(expr.as_ref(), &Context::new());
     output.into()
 }
 
diff --git a/dhall_syntax/src/core.rs b/dhall_syntax/src/core.rs
index a81f96c..a186d19 100644
--- a/dhall_syntax/src/core.rs
+++ b/dhall_syntax/src/core.rs
@@ -141,12 +141,13 @@ pub type ParsedExpr = SubExpr<X, Import>;
 pub type ResolvedExpr = SubExpr<X, X>;
 pub type DhallExpr = ResolvedExpr;
 
+// Each node carries an annotation. In practice it's either X (no annotation) or a Span.
 #[derive(Debug)]
-pub struct SubExpr<Note, Embed>(Rc<Expr<Note, Embed>>, Option<Note>);
+pub struct SubExpr<Note, Embed>(Rc<(Expr<Note, Embed>, Option<Note>)>);
 
 impl<Note, Embed: PartialEq> std::cmp::PartialEq for SubExpr<Note, Embed> {
     fn eq(&self, other: &Self) -> bool {
-        self.0 == other.0
+        self.0.as_ref().0 == other.0.as_ref().0
     }
 }
 
@@ -345,14 +346,6 @@ impl<N, E> Expr<N, E> {
         trivial_result(self.traverse_embed(|x| Ok(map_embed(x))))
     }
 
-    pub fn roll(&self) -> SubExpr<N, E>
-    where
-        N: Clone,
-        E: Clone,
-    {
-        rc(ExprF::clone(self))
-    }
-
     pub fn squash_embed<E2>(
         &self,
         f: impl FnMut(&E) -> SubExpr<N, E2>,
@@ -378,7 +371,33 @@ impl<N: Clone> Expr<N, X> {
 
 impl<N, E> SubExpr<N, E> {
     pub fn as_ref(&self) -> &Expr<N, E> {
-        self.0.as_ref()
+        &self.0.as_ref().0
+    }
+
+    pub fn new(x: Expr<N, E>, n: N) -> Self {
+        SubExpr(Rc::new((x, Some(n))))
+    }
+
+    pub fn from_expr_no_note(x: Expr<N, E>) -> Self {
+        SubExpr(Rc::new((x, None)))
+    }
+
+    pub fn unnote(&self) -> SubExpr<X, E>
+    where
+        E: Clone,
+    {
+        SubExpr::from_expr_no_note(
+            self.as_ref().visit(&mut visitor::UnNoteVisitor),
+        )
+    }
+}
+
+impl<N: Clone, E> SubExpr<N, E> {
+    pub fn rewrap<E2>(&self, x: Expr<N, E2>) -> SubExpr<N, E2>
+    where
+        N: Clone,
+    {
+        SubExpr(Rc::new((x, (self.0).1.clone())))
     }
 
     pub fn traverse_embed<E2, Err>(
@@ -388,7 +407,7 @@ impl<N, E> SubExpr<N, E> {
     where
         N: Clone,
     {
-        Ok(rc(self.as_ref().traverse_embed(visit_embed)?))
+        Ok(self.rewrap(self.as_ref().traverse_embed(visit_embed)?))
     }
 
     pub fn map_embed<E2>(
@@ -398,7 +417,7 @@ impl<N, E> SubExpr<N, E> {
     where
         N: Clone,
     {
-        rc(self.as_ref().map_embed(map_embed))
+        self.rewrap(self.as_ref().map_embed(map_embed))
     }
 
     pub fn map_subexprs_with_special_handling_of_binders<'a>(
@@ -409,7 +428,7 @@ impl<N, E> SubExpr<N, E> {
         match self.as_ref() {
             ExprF::Embed(_) => SubExpr::clone(self),
             // This calls ExprF::map_ref
-            e => rc(e.map_ref_with_special_handling_of_binders(
+            e => self.rewrap(e.map_ref_with_special_handling_of_binders(
                 map_expr,
                 map_under_binder,
                 |_| unreachable!(),
@@ -418,28 +437,13 @@ impl<N, E> SubExpr<N, E> {
         }
     }
 
-    pub fn unroll(&self) -> Expr<N, E>
-    where
-        N: Clone,
-        E: Clone,
-    {
-        ExprF::clone(self.as_ref())
-    }
-
-    pub fn unnote(&self) -> SubExpr<X, E>
-    where
-        E: Clone,
-    {
-        rc(self.as_ref().visit(&mut visitor::UnNoteVisitor))
-    }
-
     /// `shift` is used by both normalization and type-checking to avoid variable
     /// capture by shifting variable indices
     /// See https://github.com/dhall-lang/dhall-lang/blob/master/standard/semantics.md#shift
     /// for details
     pub fn shift(&self, delta: isize, var: &V<Label>) -> Self {
         match self.as_ref() {
-            ExprF::Var(v) => rc(ExprF::Var(v.shift(delta, var))),
+            ExprF::Var(v) => self.rewrap(ExprF::Var(v.shift(delta, var))),
             _ => self.map_subexprs_with_special_handling_of_binders(
                 |e| e.shift(delta, var),
                 |x: &Label, e| e.shift(delta, &var.shift(1, &x.into())),
@@ -450,7 +454,7 @@ impl<N, E> SubExpr<N, E> {
     pub fn subst_shift(&self, var: &V<Label>, val: &Self) -> Self {
         match self.as_ref() {
             ExprF::Var(v) if v == var => val.clone(),
-            ExprF::Var(v) => rc(ExprF::Var(v.shift(-1, var))),
+            ExprF::Var(v) => self.rewrap(ExprF::Var(v.shift(-1, var))),
             _ => self.map_subexprs_with_special_handling_of_binders(
                 |e| e.subst_shift(var, val),
                 |x: &Label, e| {
@@ -466,25 +470,25 @@ impl<N, E> SubExpr<N, E> {
 
 impl<N: Clone> SubExpr<N, X> {
     pub fn embed_absurd<T>(&self) -> SubExpr<N, T> {
-        rc(self.as_ref().embed_absurd())
+        self.rewrap(self.as_ref().embed_absurd())
     }
 }
 
 impl<E: Clone> SubExpr<X, E> {
     pub fn note_absurd<N>(&self) -> SubExpr<N, E> {
-        rc(self.as_ref().note_absurd())
+        SubExpr::from_expr_no_note(self.as_ref().note_absurd())
     }
 }
 
 impl<N, E> Clone for SubExpr<N, E> {
     fn clone(&self) -> Self {
-        SubExpr(Rc::clone(&self.0), None)
+        SubExpr(Rc::clone(&self.0))
     }
 }
 
 // Should probably rename this
-pub fn rc<N, E>(x: Expr<N, E>) -> SubExpr<N, E> {
-    SubExpr(Rc::new(x), None)
+pub fn rc<E>(x: Expr<X, E>) -> SubExpr<X, E> {
+    SubExpr::from_expr_no_note(x)
 }
 
 /// Add an isize to an usize
@@ -518,14 +522,20 @@ pub fn shift<N, E>(
     delta: isize,
     var: &V<Label>,
     in_expr: &SubExpr<N, E>,
-) -> SubExpr<N, E> {
+) -> SubExpr<N, E>
+where
+    N: Clone,
+{
     in_expr.shift(delta, var)
 }
 
 pub fn shift0_multiple<N, E>(
     deltas: &HashMap<Label, isize>,
     in_expr: &SubExpr<N, E>,
-) -> SubExpr<N, E> {
+) -> SubExpr<N, E>
+where
+    N: Clone,
+{
     shift0_multiple_inner(&Context::new(), deltas, in_expr)
 }
 
@@ -533,12 +543,15 @@ fn shift0_multiple_inner<N, E>(
     ctx: &Context<Label, ()>,
     deltas: &HashMap<Label, isize>,
     in_expr: &SubExpr<N, E>,
-) -> SubExpr<N, E> {
+) -> SubExpr<N, E>
+where
+    N: Clone,
+{
     use crate::ExprF::*;
     match in_expr.as_ref() {
         Var(V(y, m)) if ctx.lookup(y, *m).is_none() => {
             let delta = deltas.get(y).unwrap_or(&0);
-            rc(Var(V(y.clone(), add_ui(*m, *delta))))
+            in_expr.rewrap(Var(V(y.clone(), add_ui(*m, *delta))))
         }
         _ => in_expr.map_subexprs_with_special_handling_of_binders(
             |e| shift0_multiple_inner(ctx, deltas, e),
diff --git a/dhall_syntax/src/parser.rs b/dhall_syntax/src/parser.rs
index b5bf09d..83ccc1e 100644
--- a/dhall_syntax/src/parser.rs
+++ b/dhall_syntax/src/parser.rs
@@ -25,8 +25,8 @@ pub type ParseError = pest::error::Error<Rule>;
 
 pub type ParseResult<T> = Result<T, ParseError>;
 
-fn rc(x: ParsedExpr) -> ParsedSubExpr {
-    crate::rc(x)
+fn unspanned(x: ParsedExpr) -> ParsedSubExpr {
+    SubExpr::from_expr_no_note(x)
 }
 
 #[derive(Debug, Clone)]
@@ -52,10 +52,8 @@ impl Span {
     }
 }
 
-fn spanned(_span: Span, x: ParsedExpr) -> ParsedExpr {
-    x
-    // This breaks equality testing; I need to fix that first
-    // Note(span, rc(x))
+fn spanned(span: Span, x: ParsedExpr) -> ParsedSubExpr {
+    SubExpr::new(x, span)
 }
 
 #[derive(Debug)]
@@ -343,7 +341,7 @@ make_parser! {
 
     rule!(double_quote_chunk<ParsedTextContents>; children!(
         [interpolation(e)] => {
-            InterpolatedTextContents::Expr(rc(e))
+            InterpolatedTextContents::Expr(e)
         },
         [double_quote_escaped(s)] => {
             InterpolatedTextContents::Text(s)
@@ -408,13 +406,13 @@ make_parser! {
     rule!(escaped_interpolation<&'a str>;
         captured_str!(_) => "${"
     );
-    rule!(interpolation<ParsedExpr>; children!(
+    rule!(interpolation<ParsedSubExpr>; children!(
         [expression(e)] => e
     ));
 
     rule!(single_quote_continue<Vec<Vec<ParsedTextContents>>>; children!(
         [interpolation(c), single_quote_continue(lines)] => {
-            let c = InterpolatedTextContents::Expr(rc(c));
+            let c = InterpolatedTextContents::Expr(c);
             let mut lines = lines;
             lines.last_mut().unwrap().push(c);
             lines
@@ -447,7 +445,7 @@ make_parser! {
         },
     ));
 
-    rule!(builtin<ParsedExpr>; span;
+    rule!(builtin<ParsedSubExpr>; span;
         captured_str!(s) => {
             spanned(span, match crate::Builtin::parse(s) {
                 Some(b) => Builtin(b),
@@ -504,7 +502,7 @@ make_parser! {
         }
     );
 
-    rule!(identifier<ParsedExpr> as expression; span; children!(
+    rule!(identifier<ParsedSubExpr> as expression; span; children!(
         [variable(v)] => {
             spanned(span, Var(v))
         },
@@ -644,7 +642,7 @@ make_parser! {
 
     token_rule!(Text<()>);
 
-    rule!(import<ParsedExpr> as expression; span; children!(
+    rule!(import<ParsedSubExpr> as expression; span; children!(
         [import_hashed(location_hashed)] => {
             spanned(span, Embed(Import {
                 mode: ImportMode::Code,
@@ -666,29 +664,29 @@ make_parser! {
     token_rule!(if_<()>);
     token_rule!(in_<()>);
 
-    rule!(expression<ParsedExpr> as expression; span; children!(
+    rule!(expression<ParsedSubExpr> as expression; span; children!(
         [lambda(()), label(l), expression(typ),
                 arrow(()), expression(body)] => {
-            spanned(span, Lam(l, rc(typ), rc(body)))
+            spanned(span, Lam(l, typ, body))
         },
         [if_(()), expression(cond), expression(left), expression(right)] => {
-            spanned(span, BoolIf(rc(cond), rc(left), rc(right)))
+            spanned(span, BoolIf(cond, left, right))
         },
         [let_binding(bindings).., in_(()), expression(final_expr)] => {
             bindings.rev().fold(
                 final_expr,
-                |acc, x| Let(x.0, x.1, x.2, rc(acc))
+                |acc, x| unspanned(Let(x.0, x.1, x.2, acc))
             )
         },
         [forall(()), label(l), expression(typ),
                 arrow(()), expression(body)] => {
-            spanned(span, Pi(l, rc(typ), rc(body)))
+            spanned(span, Pi(l, typ, body))
         },
         [expression(typ), arrow(()), expression(body)] => {
-            spanned(span, Pi("_".into(), rc(typ), rc(body)))
+            spanned(span, Pi("_".into(), typ, body))
         },
         [merge(()), expression(x), expression(y), expression(z)] => {
-            spanned(span, Merge(rc(x), rc(y), Some(rc(z))))
+            spanned(span, Merge(x, y, Some(z)))
         },
         [expression(e)] => e,
     ));
@@ -696,148 +694,148 @@ make_parser! {
     rule!(let_binding<(Label, Option<ParsedSubExpr>, ParsedSubExpr)>;
             children!(
         [label(name), expression(annot), expression(expr)] =>
-            (name, Some(rc(annot)), rc(expr)),
+            (name, Some(annot), expr),
         [label(name), expression(expr)] =>
-            (name, None, rc(expr)),
+            (name, None, expr),
     ));
 
     token_rule!(List<()>);
     token_rule!(Optional<()>);
 
-    rule!(empty_collection<ParsedExpr> as expression; span; children!(
+    rule!(empty_collection<ParsedSubExpr> as expression; span; children!(
         [List(_), expression(t)] => {
-            spanned(span, EmptyListLit(rc(t)))
+            spanned(span, EmptyListLit(t))
         },
         [Optional(_), expression(t)] => {
-            spanned(span, OldOptionalLit(None, rc(t)))
+            spanned(span, OldOptionalLit(None, t))
         },
     ));
 
-    rule!(non_empty_optional<ParsedExpr> as expression; span; children!(
+    rule!(non_empty_optional<ParsedSubExpr> as expression; span; children!(
         [expression(x), Optional(_), expression(t)] => {
-            spanned(span, OldOptionalLit(Some(rc(x)), rc(t)))
+            spanned(span, OldOptionalLit(Some(x), t))
         }
     ));
 
-    rule!(import_alt_expression<ParsedExpr> as expression; children!(
+    rule!(import_alt_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::ImportAlt;
-            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e)))
         },
     ));
-    rule!(or_expression<ParsedExpr> as expression; children!(
+    rule!(or_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::BoolOr;
-            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e)))
         },
     ));
-    rule!(plus_expression<ParsedExpr> as expression; children!(
+    rule!(plus_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::NaturalPlus;
-            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e)))
         },
     ));
-    rule!(text_append_expression<ParsedExpr> as expression; children!(
+    rule!(text_append_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::TextAppend;
-            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e)))
         },
     ));
-    rule!(list_append_expression<ParsedExpr> as expression; children!(
+    rule!(list_append_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::ListAppend;
-            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e)))
         },
     ));
-    rule!(and_expression<ParsedExpr> as expression; children!(
+    rule!(and_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::BoolAnd;
-            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e)))
         },
     ));
-    rule!(combine_expression<ParsedExpr> as expression; children!(
+    rule!(combine_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::Combine;
-            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e)))
         },
     ));
-    rule!(prefer_expression<ParsedExpr> as expression; children!(
+    rule!(prefer_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::Prefer;
-            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e)))
         },
     ));
-    rule!(combine_types_expression<ParsedExpr> as expression; children!(
+    rule!(combine_types_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::CombineTypes;
-            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e)))
         },
     ));
-    rule!(times_expression<ParsedExpr> as expression; children!(
+    rule!(times_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::NaturalTimes;
-            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e)))
         },
     ));
-    rule!(equal_expression<ParsedExpr> as expression; children!(
+    rule!(equal_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::BoolEQ;
-            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e)))
         },
     ));
-    rule!(not_equal_expression<ParsedExpr> as expression; children!(
+    rule!(not_equal_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
             let o = crate::BinOp::BoolNE;
-            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(BinOp(o, acc, e)))
         },
     ));
 
-    rule!(annotated_expression<ParsedExpr> as expression; span; children!(
+    rule!(annotated_expression<ParsedSubExpr> as expression; span; children!(
         [expression(e)] => e,
         [expression(e), expression(annot)] => {
-            spanned(span, Annot(rc(e), rc(annot)))
+            spanned(span, Annot(e, annot))
         },
     ));
 
     token_rule!(Some_<()>);
 
-    rule!(application_expression<ParsedExpr> as expression; children!(
+    rule!(application_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            rest.fold(first, |acc, e| App(rc(acc), rc(e)))
+            rest.fold(first, |acc, e| unspanned(App(acc, e)))
         },
     ));
 
-    rule!(first_application_expression<ParsedExpr> as expression; span;
+    rule!(first_application_expression<ParsedSubExpr> as expression; span;
             children!(
         [expression(e)] => e,
         [Some_(()), expression(e)] => {
-            spanned(span, SomeLit(rc(e)))
+            spanned(span, SomeLit(e))
         },
         [merge(()), expression(x), expression(y)] => {
-            spanned(span, Merge(rc(x), rc(y), None))
+            spanned(span, Merge(x, y, None))
         },
     ));
 
-    rule!(selector_expression<ParsedExpr> as expression; children!(
+    rule!(selector_expression<ParsedSubExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), selector(rest)..] => {
-            rest.fold(first, |acc, e| match e {
-                Either::Left(l) => Field(rc(acc), l),
-                Either::Right(ls) => Projection(rc(acc), ls),
-            })
+            rest.fold(first, |acc, e| unspanned(match e {
+                Either::Left(l) => Field(acc, l),
+                Either::Right(ls) => Projection(acc, ls),
+            }))
         }
     ));
 
@@ -850,7 +848,7 @@ make_parser! {
         [label(ls)..] => ls.collect(),
     ));
 
-    rule!(primitive_expression<ParsedExpr> as expression; span; children!(
+    rule!(primitive_expression<ParsedSubExpr> as expression; span; children!(
         [double_literal(n)] => spanned(span, DoubleLit(n)),
         [natural_literal(n)] => spanned(span, NaturalLit(n)),
         [integer_literal(n)] => spanned(span, IntegerLit(n)),
@@ -859,51 +857,51 @@ make_parser! {
         [expression(e)] => e,
     ));
 
-    rule!(empty_record_literal<ParsedExpr> as expression; span;
+    rule!(empty_record_literal<ParsedSubExpr> as expression; span;
         captured_str!(_) => spanned(span, RecordLit(BTreeMap::new()))
     );
 
-    rule!(empty_record_type<ParsedExpr> as expression; span;
+    rule!(empty_record_type<ParsedSubExpr> as expression; span;
         captured_str!(_) => spanned(span, RecordType(BTreeMap::new()))
     );
 
-    rule!(non_empty_record_type_or_literal<ParsedExpr> as expression; span;
+    rule!(non_empty_record_type_or_literal<ParsedSubExpr> as expression; span;
           children!(
         [label(first_label), non_empty_record_type(rest)] => {
             let (first_expr, mut map) = rest;
-            map.insert(first_label, rc(first_expr));
+            map.insert(first_label, first_expr);
             spanned(span, RecordType(map))
         },
         [label(first_label), non_empty_record_literal(rest)] => {
             let (first_expr, mut map) = rest;
-            map.insert(first_label, rc(first_expr));
+            map.insert(first_label, first_expr);
             spanned(span, RecordLit(map))
         },
     ));
 
     rule!(non_empty_record_type
-          <(ParsedExpr, BTreeMap<Label, ParsedSubExpr>)>; children!(
+          <(ParsedSubExpr, BTreeMap<Label, ParsedSubExpr>)>; children!(
         [expression(expr), record_type_entry(entries)..] => {
             (expr, entries.collect())
         }
     ));
 
     rule!(record_type_entry<(Label, ParsedSubExpr)>; children!(
-        [label(name), expression(expr)] => (name, rc(expr))
+        [label(name), expression(expr)] => (name, expr)
     ));
 
     rule!(non_empty_record_literal
-          <(ParsedExpr, BTreeMap<Label, ParsedSubExpr>)>; children!(
+          <(ParsedSubExpr, BTreeMap<Label, ParsedSubExpr>)>; children!(
         [expression(expr), record_literal_entry(entries)..] => {
             (expr, entries.collect())
         }
     ));
 
     rule!(record_literal_entry<(Label, ParsedSubExpr)>; children!(
-        [label(name), expression(expr)] => (name, rc(expr))
+        [label(name), expression(expr)] => (name, expr)
     ));
 
-    rule!(union_type_or_literal<ParsedExpr> as expression; span; children!(
+    rule!(union_type_or_literal<ParsedSubExpr> as expression; span; children!(
         [empty_union_type(_)] => {
             spanned(span, UnionType(BTreeMap::new()))
         },
@@ -935,12 +933,12 @@ make_parser! {
           <(ParsedSubExpr, BTreeMap<Label, Option<ParsedSubExpr>>)>;
             children!(
         [expression(e), union_type_entry(entries)..] => {
-            (rc(e), entries.collect())
+            (e, entries.collect())
         },
     ));
 
     rule!(union_type_entry<(Label, Option<ParsedSubExpr>)>; children!(
-        [label(name), expression(expr)] => (name, Some(rc(expr))),
+        [label(name), expression(expr)] => (name, Some(expr)),
         [label(name)] => (name, None),
     ));
 
@@ -951,10 +949,10 @@ make_parser! {
              BTreeMap<Label, Option<ParsedSubExpr>>))>;
                 children!(
         [expression(e), non_empty_union_type_or_literal(rest)] => {
-            (Some(rc(e)), rest)
+            (Some(e), rest)
         },
         [expression(e)] => {
-            (Some(rc(e)), (None, BTreeMap::new()))
+            (Some(e), (None, BTreeMap::new()))
         },
         [non_empty_union_type_or_literal(rest)] => {
             (None, rest)
@@ -964,15 +962,15 @@ make_parser! {
         },
     ));
 
-    rule!(non_empty_list_literal<ParsedExpr> as expression; span;
+    rule!(non_empty_list_literal<ParsedSubExpr> as expression; span;
           children!(
         [expression(items)..] => spanned(
             span,
-            NEListLit(items.map(rc).collect())
+            NEListLit(items.collect())
         )
     ));
 
-    rule!(final_expression<ParsedExpr> as expression; children!(
+    rule!(final_expression<ParsedSubExpr> as expression; children!(
         [expression(e), EOI(_eoi)] => e
     ));
 }
@@ -983,10 +981,10 @@ pub fn parse_expr<'a>(s: &'a str) -> ParseResult<ParsedSubExpr> {
     let expr = do_parse(rc_input, pairs.next().unwrap())?;
     assert_eq!(pairs.next(), None);
     match expr {
-        ParsedValue::expression(e) => Ok(rc(e)),
+        ParsedValue::expression(e) => Ok(e),
         _ => unreachable!(),
     }
-    // Ok(rc(BoolLit(false)))
+    // Ok(BoolLit(false))
 }
 
 #[test]
diff --git a/dhall_syntax/src/visitor.rs b/dhall_syntax/src/visitor.rs
index cbaa21e..7fdf217 100644
--- a/dhall_syntax/src/visitor.rs
+++ b/dhall_syntax/src/visitor.rs
@@ -411,7 +411,7 @@ where
         &mut self,
         subexpr: &'a SubExpr<N, E>,
     ) -> Result<SubExpr<N, E2>, Self::Error> {
-        Ok(rc(subexpr.as_ref().visit(&mut **self)?))
+        Ok(subexpr.rewrap(subexpr.as_ref().visit(&mut **self)?))
     }
     fn visit_embed(self, embed: &'a E) -> Result<E2, Self::Error> {
         (self.0)(embed)
@@ -469,7 +469,8 @@ where
     fn visit_resulting_exprf(
         result: ExprF<Self::SE2, Self::L2, Self::E2>,
     ) -> Result<SubExpr<N, E2>, Self::Error> {
-        Ok(rc(result))
+        // TODO: don't lose note
+        Ok(SubExpr::from_expr_no_note(result))
     }
 }
 
@@ -482,7 +483,7 @@ where
     E: Clone + 'a,
 {
     fn visit_subexpr(&mut self, subexpr: &'a SubExpr<N, E>) -> SubExpr<X, E> {
-        rc(subexpr.as_ref().visit(&mut **self))
+        SubExpr::from_expr_no_note(subexpr.as_ref().visit(&mut **self))
     }
     fn visit_embed(self, embed: &'a E) -> E {
         E::clone(embed)
@@ -501,7 +502,7 @@ where
     E: Clone + 'a,
 {
     fn visit_subexpr(&mut self, subexpr: &'a SubExpr<X, E>) -> SubExpr<N, E> {
-        rc(subexpr.as_ref().visit(&mut **self))
+        SubExpr::from_expr_no_note(subexpr.as_ref().visit(&mut **self))
     }
     fn visit_embed(self, embed: &'a E) -> E {
         E::clone(embed)
@@ -520,7 +521,7 @@ where
     N: Clone + 'a,
 {
     fn visit_subexpr(&mut self, subexpr: &'a SubExpr<N, X>) -> SubExpr<N, E> {
-        rc(subexpr.as_ref().visit(&mut **self))
+        subexpr.rewrap(subexpr.as_ref().visit(&mut **self))
     }
     fn visit_embed(self, embed: &'a X) -> E {
         match *embed {}
-- 
cgit v1.2.3