Use Rc instead of Box in AST to allow structural sharing

Closes #29

3 files changed, 10 insertions, 7 deletions

diff --git a/dhall/src/binary.rs b/dhall/src/binary.rs
index fbd343b..08bdba4 100644
--- a/dhall/src/binary.rs
+++ b/dhall/src/binary.rs
@@ -1,8 +1,9 @@
 use dhall_core::*;
 use itertools::*;
+use std::rc::Rc;
 use serde_cbor::value::value as cbor;
 
-type ParsedExpr = Box<Expr<X, Import>>;
+type ParsedExpr = Rc<Expr<X, Import>>;
 
 #[derive(Debug)]
 pub enum DecodeError {
diff --git a/dhall/src/normalize.rs b/dhall/src/normalize.rs
index c49d313..40112f1 100644
--- a/dhall/src/normalize.rs
+++ b/dhall/src/normalize.rs
@@ -2,6 +2,7 @@
 use dhall_core::core::*;
 use dhall_generator::dhall_expr;
 use std::fmt;
+use std::rc::Rc;
 
 /// Reduce an expression to its weak head normal form, i.e. normalize
 /// just enough to get the first constructor of the final expression
diff --git a/dhall/src/typecheck.rs b/dhall/src/typecheck.rs
index ca0d5af..f5670f7 100644
--- a/dhall/src/typecheck.rs
+++ b/dhall/src/typecheck.rs
@@ -2,6 +2,7 @@
 use std::collections::BTreeMap;
 use std::collections::HashSet;
 use std::fmt;
+use std::rc::Rc;
 
 use crate::normalize;
 use dhall_core::context::Context;
@@ -415,7 +416,7 @@ where
         }
         ListLit(ref t, ref xs) => {
             let mut iter = xs.iter().enumerate();
-            let t: Box<Expr<_, _>> = match t {
+            let t: Rc<Expr<_, _>> = match t {
                 Some(t) => t.clone(),
                 None => {
                     let (_, first_x) = iter.next().unwrap();
@@ -426,7 +427,7 @@ where
             let s = normalize::<_, S, _>(&type_with(ctx, &t)?);
             match s {
                 Const(Type) => {}
-                _ => return Err(TypeError::new(ctx, e, InvalidListType(*t))),
+                _ => return Err(TypeError::new(ctx, e, InvalidListType(t))),
             }
             for (i, x) in iter {
                 let t2 = type_with(ctx, x)?;
@@ -474,7 +475,7 @@ where
         )),
         OptionalLit(ref t, ref xs) => {
             let mut iter = xs.iter();
-            let t: Box<Expr<_, _>> = match t {
+            let t: Rc<Expr<_, _>> = match t {
                 Some(t) => t.clone(),
                 None => {
                     let x = iter.next().unwrap();
@@ -489,7 +490,7 @@ where
                     return Err(TypeError::new(
                         ctx,
                         e,
-                        InvalidOptionalType(*t),
+                        InvalidOptionalType(t),
                     ));
                 }
             }
@@ -689,10 +690,10 @@ pub enum TypeMessage<S> {
     AnnotMismatch(Expr<S, X>, Expr<S, X>, Expr<S, X>),
     Untyped,
     InvalidListElement(usize, Expr<S, X>, Expr<S, X>, Expr<S, X>),
-    InvalidListType(Expr<S, X>),
+    InvalidListType(Rc<Expr<S, X>>),
     InvalidOptionalElement(Expr<S, X>, Expr<S, X>, Expr<S, X>),
     InvalidOptionalLiteral(usize),
-    InvalidOptionalType(Expr<S, X>),
+    InvalidOptionalType(Rc<Expr<S, X>>),
     InvalidPredicate(Expr<S, X>, Expr<S, X>),
     IfBranchMismatch(Expr<S, X>, Expr<S, X>, Expr<S, X>, Expr<S, X>),
     IfBranchMustBeTerm(bool, Expr<S, X>, Expr<S, X>, Expr<S, X>),