Use Rc instead of Box in AST to allow structural sharing

Closes #29

2 files changed, 75 insertions, 72 deletions

diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index 34738bb..f5da1df 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -176,13 +176,13 @@ pub enum BinOp {
 #[derive(Debug, Clone, PartialEq)]
 pub struct InterpolatedText<Note, Embed> {
     head: String,
-    tail: Vec<(Box<Expr<Note, Embed>>, String)>,
+    tail: Vec<(Rc<Expr<Note, Embed>>, String)>,
 }
 
-impl<N, E> From<(String, Vec<(Box<Expr<N, E>>, String)>)>
+impl<N, E> From<(String, Vec<(Rc<Expr<N, E>>, String)>)>
     for InterpolatedText<N, E>
 {
-    fn from(x: (String, Vec<(Box<Expr<N, E>>, String)>)) -> Self {
+    fn from(x: (String, Vec<(Rc<Expr<N, E>>, String)>)) -> Self {
         InterpolatedText {
             head: x.0,
             tail: x.1,
@@ -203,7 +203,7 @@ impl<N, E> From<String> for InterpolatedText<N, E> {
 // This one is needed when parsing, because we need to own the Expr
 pub enum OwnedInterpolatedTextContents<'a, Note, Embed> {
     Text(&'a str),
-    Expr(Box<Expr<Note, Embed>>),
+    Expr(Rc<Expr<Note, Embed>>),
 }
 
 // This one is needed everywhere else, because we don't want Clone traits bounds
@@ -231,7 +231,7 @@ impl<'a, N: Clone + 'a, E: Clone + 'a>
 impl<N, E> InterpolatedText<N, E> {
     pub fn map<N2, E2, F>(&self, mut f: F) -> InterpolatedText<N2, E2>
     where
-        F: FnMut(&Box<Expr<N, E>>) -> Box<Expr<N2, E2>>,
+        F: FnMut(&Rc<Expr<N, E>>) -> Rc<Expr<N2, E2>>,
     {
         InterpolatedText {
             head: self.head.clone(),
@@ -299,33 +299,33 @@ pub enum Expr<Note, Embed> {
     ///  `Var (V x n)                              ~  x@n`
     Var(V),
     ///  `Lam x     A b                            ~  λ(x : A) -> b`
-    Lam(Label, Box<Expr<Note, Embed>>, Box<Expr<Note, Embed>>),
+    Lam(Label, Rc<Expr<Note, Embed>>, Rc<Expr<Note, Embed>>),
     ///  `Pi "_" A B                               ~        A  -> B`
     ///  `Pi x   A B                               ~  ∀(x : A) -> B`
-    Pi(Label, Box<Expr<Note, Embed>>, Box<Expr<Note, Embed>>),
+    Pi(Label, Rc<Expr<Note, Embed>>, Rc<Expr<Note, Embed>>),
     ///  `App f A                                  ~  f A`
-    App(Box<Expr<Note, Embed>>, Vec<Box<Expr<Note, Embed>>>),
+    App(Rc<Expr<Note, Embed>>, Vec<Rc<Expr<Note, Embed>>>),
     ///  `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<Box<Expr<Note, Embed>>>,
-        Box<Expr<Note, Embed>>,
-        Box<Expr<Note, Embed>>,
+        Option<Rc<Expr<Note, Embed>>>,
+        Rc<Expr<Note, Embed>>,
+        Rc<Expr<Note, Embed>>,
     ),
     ///  `Annot x t                                ~  x : t`
-    Annot(Box<Expr<Note, Embed>>, Box<Expr<Note, Embed>>),
+    Annot(Rc<Expr<Note, Embed>>, Rc<Expr<Note, Embed>>),
     /// Built-in values
     Builtin(Builtin),
     // Binary operations
-    BinOp(BinOp, Box<Expr<Note, Embed>>, Box<Expr<Note, Embed>>),
+    BinOp(BinOp, Rc<Expr<Note, Embed>>, Rc<Expr<Note, Embed>>),
     ///  `BoolLit b                                ~  b`
     BoolLit(bool),
     ///  `BoolIf x y z                             ~  if x then y else z`
     BoolIf(
-        Box<Expr<Note, Embed>>,
-        Box<Expr<Note, Embed>>,
-        Box<Expr<Note, Embed>>,
+        Rc<Expr<Note, Embed>>,
+        Rc<Expr<Note, Embed>>,
+        Rc<Expr<Note, Embed>>,
     ),
     ///  `NaturalLit n                             ~  +n`
     NaturalLit(Natural),
@@ -336,35 +336,35 @@ pub enum Expr<Note, Embed> {
     ///  `TextLit t                                ~  t`
     TextLit(InterpolatedText<Note, Embed>),
     ///  `ListLit t [x, y, z]                      ~  [x, y, z] : List t`
-    ListLit(Option<Box<Expr<Note, Embed>>>, Vec<Box<Expr<Note, Embed>>>),
+    ListLit(Option<Rc<Expr<Note, Embed>>>, Vec<Rc<Expr<Note, Embed>>>),
     ///  `OptionalLit t [e]                        ~  [e] : Optional t`
     ///  `OptionalLit t []                         ~  []  : Optional t`
     OptionalLit(
-        Option<Box<Expr<Note, Embed>>>,
-        Option<Box<Expr<Note, Embed>>>,
+        Option<Rc<Expr<Note, Embed>>>,
+        Option<Rc<Expr<Note, Embed>>>,
     ),
     ///  `Record            [(k1, t1), (k2, t2)]   ~  { k1 : t1, k2 : t1 }`
-    Record(BTreeMap<Label, Box<Expr<Note, Embed>>>),
+    Record(BTreeMap<Label, Rc<Expr<Note, Embed>>>),
     ///  `RecordLit         [(k1, v1), (k2, v2)]   ~  { k1 = v1, k2 = v2 }`
-    RecordLit(BTreeMap<Label, Box<Expr<Note, Embed>>>),
+    RecordLit(BTreeMap<Label, Rc<Expr<Note, Embed>>>),
     ///  `Union             [(k1, t1), (k2, t2)]   ~  < k1 : t1, k2 : t2 >`
-    Union(BTreeMap<Label, Box<Expr<Note, Embed>>>),
+    Union(BTreeMap<Label, Rc<Expr<Note, Embed>>>),
     ///  `UnionLit (k1, v1) [(k2, t2), (k3, t3)]   ~  < k1 = t1, k2 : t2, k3 : t3 >`
     UnionLit(
         Label,
-        Box<Expr<Note, Embed>>,
-        BTreeMap<Label, Box<Expr<Note, Embed>>>,
+        Rc<Expr<Note, Embed>>,
+        BTreeMap<Label, Rc<Expr<Note, Embed>>>,
     ),
     ///  `Merge x y t                              ~  merge x y : t`
     Merge(
-        Box<Expr<Note, Embed>>,
-        Box<Expr<Note, Embed>>,
-        Option<Box<Expr<Note, Embed>>>,
+        Rc<Expr<Note, Embed>>,
+        Rc<Expr<Note, Embed>>,
+        Option<Rc<Expr<Note, Embed>>>,
     ),
     ///  `Field e x                                ~  e.x`
-    Field(Box<Expr<Note, Embed>>, Label),
+    Field(Rc<Expr<Note, Embed>>, Label),
     /// Annotation on the AST. Unused for now but could hold e.g. file location information
-    Note(Note, Box<Expr<Note, Embed>>),
+    Note(Note, Rc<Expr<Note, Embed>>),
     /// Embeds an import or the result of resolving the import
     Embed(Embed),
 }
@@ -848,14 +848,13 @@ where
     Expr::Pi(var.into(), bx(ty.into()), bx(value.into()))
 }
 
-pub fn app<S, A, Ef, Ex>(f: Ef, x: Vec<Box<Ex>>) -> Expr<S, A>
+pub fn app<S, A, Ef>(f: Ef, x: Vec<Rc<Expr<S, A>>>) -> Expr<S, A>
 where
     Ef: Into<Expr<S, A>>,
-    Ex: Into<Expr<S, A>>,
 {
     Expr::App(
         bx(f.into()),
-        x.into_iter().map(|x| bx((*x).into())).collect(),
+        x,
     )
 }
 
@@ -874,8 +873,11 @@ impl Display for X {
     }
 }
 
-pub fn bx<T>(x: T) -> Box<T> {
-    Box::new(x)
+pub fn bx<T>(x: T) -> Rc<T> {
+    Rc::new(x)
+}
+pub fn rc<T>(x: T) -> Rc<T> {
+    Rc::new(x)
 }
 
 fn add_ui(u: usize, i: isize) -> usize {
@@ -904,8 +906,8 @@ where
     F4: Fn(&Label) -> Label,
 {
     use crate::Expr::*;
-    let bxmap = |x: &Expr<S, A>| -> Box<Expr<T, B>> { bx(map(x)) };
-    let bxbxmap = |x: &Box<Expr<S, A>>| -> Box<Expr<T, B>> { bx(map(&**x)) };
+    let bxmap = |x: &Expr<S, A>| -> Rc<Expr<T, B>> { bx(map(x)) };
+    let bxbxmap = |x: &Rc<Expr<S, A>>| -> Rc<Expr<T, B>> { bx(map(&**x)) };
     let opt = |x| map_opt_box(x, &map);
     match *e {
         Const(k) => Const(k),
@@ -980,7 +982,7 @@ where
     it.into_iter().map(|(k, v)| (g(k), f(v))).collect()
 }
 
-pub fn map_opt_box<T, U, F>(x: &Option<Box<T>>, f: F) -> Option<Box<U>>
+pub fn map_opt_box<T, U, F>(x: &Option<Rc<T>>, f: F) -> Option<Rc<U>>
 where
     F: FnOnce(&T) -> U,
 {
@@ -1153,7 +1155,7 @@ fn shift_op2<S, T, A, F>(
     b: &Expr<S, A>,
 ) -> Expr<T, A>
 where
-    F: FnOnce(Box<Expr<T, A>>, Box<Expr<T, A>>) -> Expr<T, A>,
+    F: FnOnce(Rc<Expr<T, A>>, Rc<Expr<T, A>>) -> Expr<T, A>,
     A: Clone,
 {
     map_op2(f, |x| bx(shift(d, v, x)), a, b)
@@ -1258,7 +1260,7 @@ fn subst_op2<S, T, A, F>(
     b: &Expr<T, A>,
 ) -> Expr<S, A>
 where
-    F: FnOnce(Box<Expr<S, A>>, Box<Expr<S, A>>) -> Expr<S, A>,
+    F: FnOnce(Rc<Expr<S, A>>, Rc<Expr<S, A>>) -> Expr<S, A>,
     S: Clone,
     A: Clone,
 {
diff --git a/dhall_core/src/parser.rs b/dhall_core/src/parser.rs
index b2955fb..682e081 100644
--- a/dhall_core/src/parser.rs
+++ b/dhall_core/src/parser.rs
@@ -2,6 +2,7 @@ use pest::iterators::Pair;
 use pest::Parser;
 use std::collections::BTreeMap;
 use std::path::PathBuf;
+use std::rc::Rc;
 
 use dhall_parser::{DhallParser, Rule};
 
@@ -16,7 +17,7 @@ use crate::core::*;
 pub type ParsedExpr = Expr<X, Import>;
 pub type ParsedText = InterpolatedText<X, Import>;
 pub type ParsedTextContents<'a> = OwnedInterpolatedTextContents<'a, X, Import>;
-pub type BoxExpr = Box<ParsedExpr>;
+pub type RcExpr = Rc<ParsedExpr>;
 
 pub type ParseError = pest::error::Error<Rule>;
 
@@ -455,7 +456,7 @@ rule!(escaped_quote_pair<&'a str>;
 rule!(escaped_interpolation<&'a str>;
     children!() => "${"
 );
-rule!(interpolation<BoxExpr>;
+rule!(interpolation<RcExpr>;
     children!(e: expression) => e
 );
 
@@ -556,7 +557,7 @@ rule!(import_hashed_raw<(ImportLocation, Option<()>)>;
     }
 );
 
-rule!(import_raw<BoxExpr>;
+rule!(import_raw<RcExpr>;
     // TODO: handle "as Text"
     children!(import: import_hashed_raw) => {
         let (location, hash) = import;
@@ -568,7 +569,7 @@ rule!(import_raw<BoxExpr>;
     }
 );
 
-rule_group!(expression<BoxExpr>;
+rule_group!(expression<RcExpr>;
     identifier_raw,
     lambda_expression,
     ifthenelse_expression,
@@ -605,47 +606,47 @@ rule_group!(expression<BoxExpr>;
     final_expression
 );
 
-rule!(lambda_expression<BoxExpr>;
+rule!(lambda_expression<RcExpr>;
     children!(l: label, typ: expression, body: expression) => {
         bx(Expr::Lam(l, typ, body))
     }
 );
 
-rule!(ifthenelse_expression<BoxExpr>;
+rule!(ifthenelse_expression<RcExpr>;
     children!(cond: expression, left: expression, right: expression) => {
         bx(Expr::BoolIf(cond, left, right))
     }
 );
 
-rule!(let_expression<BoxExpr>;
+rule!(let_expression<RcExpr>;
     children!(bindings*: let_binding, final_expr: expression) => {
         bindings.fold(final_expr, |acc, x| bx(Expr::Let(x.0, x.1, x.2, acc)))
     }
 );
 
-rule!(let_binding<(Label, Option<BoxExpr>, BoxExpr)>;
+rule!(let_binding<(Label, Option<RcExpr>, RcExpr)>;
     children!(name: label, annot?: expression, expr: expression) => (name, annot, expr)
 );
 
-rule!(forall_expression<BoxExpr>;
+rule!(forall_expression<RcExpr>;
     children!(l: label, typ: expression, body: expression) => {
         bx(Expr::Pi(l, typ, body))
     }
 );
 
-rule!(arrow_expression<BoxExpr>;
+rule!(arrow_expression<RcExpr>;
     children!(typ: expression, body: expression) => {
         bx(Expr::Pi("_".into(), typ, body))
     }
 );
 
-rule!(merge_expression<BoxExpr>;
+rule!(merge_expression<RcExpr>;
     children!(x: expression, y: expression, z?: expression) => {
         bx(Expr::Merge(x, y, z))
     }
 );
 
-rule!(empty_collection<BoxExpr>;
+rule!(empty_collection<RcExpr>;
     children!(x: str, y: expression) => {
        match x {
           "Optional" => bx(Expr::OptionalLit(Some(y), None)),
@@ -655,7 +656,7 @@ rule!(empty_collection<BoxExpr>;
     }
 );
 
-rule!(non_empty_optional<BoxExpr>;
+rule!(non_empty_optional<RcExpr>;
     children!(x: expression, _y: str, z: expression) => {
         bx(Expr::OptionalLit(Some(z), Some(x)))
     }
@@ -686,7 +687,7 @@ fn can_be_shortcutted(rule: Rule) -> bool {
 
 macro_rules! binop {
     ($rule:ident, $op:ident) => {
-        rule!($rule<BoxExpr>;
+        rule!($rule<RcExpr>;
             raw_pair!(pair) => {
                 // This all could be a trivial fold, but to avoid stack explosion
                 // we try to cut down on the recursion level here, by consuming
@@ -737,14 +738,14 @@ binop!(times_expression, NaturalTimes);
 binop!(equal_expression, BoolEQ);
 binop!(not_equal_expression, BoolNE);
 
-rule!(annotated_expression<BoxExpr>;
+rule!(annotated_expression<RcExpr>;
     children!(e: expression, annot: expression) => {
         bx(Expr::Annot(e, annot))
     },
     children!(e: expression) => e,
 );
 
-rule!(application_expression<BoxExpr>;
+rule!(application_expression<RcExpr>;
     children!(first: expression, rest*: expression) => {
         let rest: Vec<_> = rest.collect();
         if rest.is_empty() {
@@ -755,13 +756,13 @@ rule!(application_expression<BoxExpr>;
     }
 );
 
-rule!(selector_expression_raw<BoxExpr>;
+rule!(selector_expression_raw<RcExpr>;
     children!(first: expression, rest*: label) => {
         rest.fold(first, |acc, e| bx(Expr::Field(acc, e)))
     }
 );
 
-rule!(literal_expression_raw<BoxExpr>;
+rule!(literal_expression_raw<RcExpr>;
     children!(n: double_literal_raw) => bx(Expr::DoubleLit(n)),
     children!(n: minus_infinity_literal) => bx(Expr::DoubleLit(std::f64::NEG_INFINITY)),
     children!(n: plus_infinity_literal) => bx(Expr::DoubleLit(std::f64::INFINITY)),
@@ -773,7 +774,7 @@ rule!(literal_expression_raw<BoxExpr>;
     children!(e: expression) => e,
 );
 
-rule!(identifier_raw<BoxExpr>;
+rule!(identifier_raw<RcExpr>;
     children!(name: str, idx?: natural_literal_raw) => {
         match Builtin::parse(name) {
             Some(b) => bx(Expr::Builtin(b)),
@@ -788,15 +789,15 @@ rule!(identifier_raw<BoxExpr>;
     }
 );
 
-rule!(empty_record_literal<BoxExpr>;
+rule!(empty_record_literal<RcExpr>;
     children!() => bx(Expr::RecordLit(BTreeMap::new()))
 );
 
-rule!(empty_record_type<BoxExpr>;
+rule!(empty_record_type<RcExpr>;
     children!() => bx(Expr::Record(BTreeMap::new()))
 );
 
-rule!(non_empty_record_type_or_literal<BoxExpr>;
+rule!(non_empty_record_type_or_literal<RcExpr>;
     children!(first_label: label, rest: non_empty_record_type) => {
         let (first_expr, mut map) = rest;
         map.insert(first_label, first_expr);
@@ -809,25 +810,25 @@ rule!(non_empty_record_type_or_literal<BoxExpr>;
     },
 );
 
-rule!(non_empty_record_type<(BoxExpr, BTreeMap<Label, BoxExpr>)>;
+rule!(non_empty_record_type<(RcExpr, BTreeMap<Label, RcExpr>)>;
     self!(x: partial_record_entries) => x
 );
 
-named!(partial_record_entries<(BoxExpr, BTreeMap<Label, BoxExpr>)>;
+named!(partial_record_entries<(RcExpr, BTreeMap<Label, RcExpr>)>;
     children!(expr: expression, entries*: record_entry) => {
         (expr, entries.collect())
     }
 );
 
-named!(record_entry<(Label, BoxExpr)>;
+named!(record_entry<(Label, RcExpr)>;
     children!(name: label, expr: expression) => (name, expr)
 );
 
-rule!(non_empty_record_literal<(BoxExpr, BTreeMap<Label, BoxExpr>)>;
+rule!(non_empty_record_literal<(RcExpr, BTreeMap<Label, RcExpr>)>;
     self!(x: partial_record_entries) => x
 );
 
-rule!(union_type_or_literal<BoxExpr>;
+rule!(union_type_or_literal<RcExpr>;
     children!(_e: empty_union_type) => {
         bx(Expr::Union(BTreeMap::new()))
     },
@@ -842,7 +843,7 @@ rule!(union_type_or_literal<BoxExpr>;
 rule!(empty_union_type<()>; children!() => ());
 
 rule!(non_empty_union_type_or_literal
-      <(Option<(Label, BoxExpr)>, BTreeMap<Label, BoxExpr>)>;
+      <(Option<(Label, RcExpr)>, BTreeMap<Label, RcExpr>)>;
     children!(l: label, e: expression, entries: union_type_entries) => {
         (Some((l, e)), entries)
     },
@@ -858,27 +859,27 @@ rule!(non_empty_union_type_or_literal
     },
 );
 
-rule!(union_type_entries<BTreeMap<Label, BoxExpr>>;
+rule!(union_type_entries<BTreeMap<Label, RcExpr>>;
     children!(entries*: union_type_entry) => {
         entries.collect()
     }
 );
 
-rule!(union_type_entry<(Label, BoxExpr)>;
+rule!(union_type_entry<(Label, RcExpr)>;
     children!(name: label, expr: expression) => (name, expr)
 );
 
-rule!(non_empty_list_literal_raw<BoxExpr>;
+rule!(non_empty_list_literal_raw<RcExpr>;
     children!(items*: expression) => {
         bx(Expr::ListLit(None, items.collect()))
     }
 );
 
-rule!(final_expression<BoxExpr>;
+rule!(final_expression<RcExpr>;
     children!(e: expression, _eoi: EOI) => e
 );
 
-pub fn parse_expr(s: &str) -> ParseResult<BoxExpr> {
+pub fn parse_expr(s: &str) -> ParseResult<RcExpr> {
     let pairs = DhallParser::parse(Rule::final_expression, s)?;
     // Match the only item in the pairs iterator
     // println!("{}", debug_pair(pairs.clone().next().unwrap()));