Handle and parse interpolated strings

Closes #25

8 files changed, 185 insertions, 43 deletions

diff --git a/dhall/Cargo.toml b/dhall/Cargo.toml
index 12622f8..fd462b1 100644
--- a/dhall/Cargo.toml
+++ b/dhall/Cargo.toml
@@ -15,3 +15,6 @@ term-painter = "0.2.3"
 serde_cbor = "0.9.0"
 dhall_core = { path = "../dhall_core" }
 dhall_generator = { path = "../dhall_generator" }
+
+[dev-dependencies]
+pretty_assertions = "0.6.1"
diff --git a/dhall/src/binary.rs b/dhall/src/binary.rs
index 0f09987..6d0f1e9 100644
--- a/dhall/src/binary.rs
+++ b/dhall/src/binary.rs
@@ -160,9 +160,21 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result<ParsedExpr, DecodeError> {
             [U64(15), U64(x)] => Ok(NaturalLit(*x as Natural)),
             [U64(16), U64(x)] => Ok(IntegerLit(*x as Integer)),
             [U64(16), I64(x)] => Ok(IntegerLit(*x as Integer)),
-            [U64(18), String(first), _rest..] => {
-                // TODO: interpolated string
-                Ok(TextLit(first.clone()))
+            [U64(18), String(first), rest..] => {
+                Ok(TextLit(InterpolatedText::from((
+                    first.clone(),
+                    rest.iter()
+                        .tuples()
+                        .map(|(x, y)| {
+                            let x = cbor_value_to_dhall(&x)?;
+                            let y = match y {
+                                String(s) => s.clone(),
+                                _ => Err(DecodeError::WrongFormatError)?,
+                            };
+                            Ok((x, y))
+                        })
+                        .collect::<Result<_, _>>()?,
+                ))))
             }
             [U64(25), bindings..] => {
                 let mut tuples = bindings.iter().tuples();
diff --git a/dhall/src/normalize.rs b/dhall/src/normalize.rs
index 50a1625..5003ccd 100644
--- a/dhall/src/normalize.rs
+++ b/dhall/src/normalize.rs
@@ -42,7 +42,7 @@ where
                 (NaturalEven, NaturalLit(n)) => BoolLit(n % 2 == 0),
                 (NaturalOdd, NaturalLit(n)) => BoolLit(n % 2 != 0),
                 (NaturalToInteger, NaturalLit(n)) => IntegerLit(n as isize),
-                (NaturalShow, NaturalLit(n)) => TextLit(n.to_string()),
+                (NaturalShow, NaturalLit(n)) => TextLit(n.to_string().into()),
 
                 (b, App(f, x)) => match (b, normalize_whnf(&f), x) {
                     // fold/build fusion for `Natural`
@@ -202,7 +202,7 @@ where
             (BoolNE, BoolLit(x), BoolLit(y)) => BoolLit(x != y),
             (NaturalPlus, NaturalLit(x), NaturalLit(y)) => NaturalLit(x + y),
             (NaturalTimes, NaturalLit(x), NaturalLit(y)) => NaturalLit(x * y),
-            (TextAppend, TextLit(x), TextLit(y)) => TextLit(x + &y),
+            (TextAppend, TextLit(x), TextLit(y)) => TextLit(x + y),
             (ListAppend, ListLit(t1, xs), ListLit(t2, ys)) => {
                 // Drop type annotation if the result is nonempty
                 let t = if xs.is_empty() && ys.is_empty() {
diff --git a/dhall/tests/macros.rs b/dhall/tests/macros.rs
index 1d90e87..4109f84 100644
--- a/dhall/tests/macros.rs
+++ b/dhall/tests/macros.rs
@@ -1,5 +1,7 @@
+use pretty_assertions::assert_eq as assert_eq_pretty;
+
 #[macro_export]
-macro_rules! assert_eq_ {
+macro_rules! assert_eq_display {
     ($left:expr, $right:expr) => {{
         match (&$left, &$right) {
             (left_val, right_val) => {
@@ -104,7 +106,7 @@ pub fn run_test(base_path: &str, feature: Feature, expected: ExpectedResult) {
             let expected = dhall::binary::decode(&data).unwrap();
             let expected = dhall::imports::panic_imports(&expected);
 
-            assert_eq!(expr, expected);
+            assert_eq_pretty!(expr, expected);
         }
         (Feature::Parser, ExpectedResult::Failure) => {
             let file_path = base_path.to_owned() + ".dhall";
@@ -120,7 +122,7 @@ pub fn run_test(base_path: &str, feature: Feature, expected: ExpectedResult) {
             let expr = read_dhall_file(&expr_file_path).unwrap();
             let expected = read_dhall_file(&expected_file_path).unwrap();
 
-            assert_eq_!(
+            assert_eq_display!(
                 normalize::<_, X, _>(&expr),
                 normalize::<_, X, _>(&expected)
             );
diff --git a/dhall/tests/tests.rs b/dhall/tests/tests.rs
index 51df149..24e8aa4 100644
--- a/dhall/tests/tests.rs
+++ b/dhall/tests/tests.rs
@@ -179,15 +179,15 @@ make_spec_test!(parser, spec_parser_success_builtins, "parser/success/builtins")
 make_spec_test!(parser, spec_parser_success_doubleQuotedString, "parser/success/doubleQuotedString");
 // make_spec_test!(parser, spec_parser_success_environmentVariables, "parser/success/environmentVariables");
 // make_spec_test!(parser, spec_parser_success_escapedDoubleQuotedString, "parser/success/escapedDoubleQuotedString");
-// make_spec_test!(parser, spec_parser_success_escapedSingleQuotedString, "parser/success/escapedSingleQuotedString");
+make_spec_test!(parser, spec_parser_success_escapedSingleQuotedString, "parser/success/escapedSingleQuotedString");
 make_spec_test!(parser, spec_parser_success_fields, "parser/success/fields");
 make_spec_test!(parser, spec_parser_success_forall, "parser/success/forall");
 make_spec_test!(parser, spec_parser_success_functionType, "parser/success/functionType");
 make_spec_test!(parser, spec_parser_success_identifier, "parser/success/identifier");
 make_spec_test!(parser, spec_parser_success_ifThenElse, "parser/success/ifThenElse");
 // make_spec_test!(parser, spec_parser_success_importAlt, "parser/success/importAlt");
-// make_spec_test!(parser, spec_parser_success_interpolatedDoubleQuotedString, "parser/success/interpolatedDoubleQuotedString");
-// make_spec_test!(parser, spec_parser_success_interpolatedSingleQuotedString, "parser/success/interpolatedSingleQuotedString");
+make_spec_test!(parser, spec_parser_success_interpolatedDoubleQuotedString, "parser/success/interpolatedDoubleQuotedString");
+make_spec_test!(parser, spec_parser_success_interpolatedSingleQuotedString, "parser/success/interpolatedSingleQuotedString");
 make_spec_test!(parser, spec_parser_success_label, "parser/success/label");
 make_spec_test!(parser, spec_parser_success_lambda, "parser/success/lambda");
 // make_spec_test!(parser, spec_parser_success_largeExpression, "parser/success/largeExpression");
@@ -206,9 +206,9 @@ make_spec_test!(parser, spec_parser_success_operators, "parser/success/operators
 // make_spec_test!(parser, spec_parser_success_quotedPaths, "parser/success/quotedPaths");
 make_spec_test!(parser, spec_parser_success_record, "parser/success/record");
 make_spec_test!(parser, spec_parser_success_reservedPrefix, "parser/success/reservedPrefix");
-// make_spec_test!(parser, spec_parser_success_singleQuotedString, "parser/success/singleQuotedString");
+make_spec_test!(parser, spec_parser_success_singleQuotedString, "parser/success/singleQuotedString");
 make_spec_test!(parser, spec_parser_success_sort, "parser/success/sort");
-// make_spec_test!(parser, spec_parser_success_template, "parser/success/template");
+make_spec_test!(parser, spec_parser_success_template, "parser/success/template");
 make_spec_test!(parser, spec_parser_success_unicodeComment, "parser/success/unicodeComment");
 make_spec_test!(parser, spec_parser_success_unicodeDoubleQuotedString, "parser/success/unicodeDoubleQuotedString");
 // make_spec_test!(parser, spec_parser_success_unicodePaths, "parser/success/unicodePaths");
diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index b3ba142..8ce9715 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -1,6 +1,8 @@
 #![allow(non_snake_case)]
 use std::collections::BTreeMap;
 use std::fmt::{self, Display};
+use std::iter::FromIterator;
+use std::ops::Add;
 use std::path::PathBuf;
 use std::rc::Rc;
 
@@ -171,6 +173,112 @@ pub enum BinOp {
     ListAppend,
 }
 
+#[derive(Debug, Clone, PartialEq)]
+pub struct InterpolatedText<Note, Embed> {
+    head: String,
+    tail: Vec<(Expr<Note, Embed>, String)>,
+}
+
+impl<N, E> From<(String, Vec<(Expr<N, E>, String)>)>
+    for InterpolatedText<N, E>
+{
+    fn from(x: (String, Vec<(Expr<N, E>, String)>)) -> Self {
+        InterpolatedText {
+            head: x.0,
+            tail: x.1,
+        }
+    }
+}
+
+impl<N, E> From<String> for InterpolatedText<N, E> {
+    fn from(s: String) -> Self {
+        InterpolatedText {
+            head: s,
+            tail: vec![],
+        }
+    }
+}
+
+// TODO: merge both when we move to Rc<>
+// This one is needed when parsing, because we need to own the Expr
+pub enum OwnedInterpolatedTextContents<'a, Note, Embed> {
+    Text(&'a str),
+    Expr(Expr<Note, Embed>),
+}
+
+// This one is needed everywhere else, because we don't want Clone traits bounds
+// everywhere
+pub enum BorrowedInterpolatedTextContents<'a, Note, Embed> {
+    Text(&'a str),
+    Expr(&'a Expr<Note, Embed>),
+}
+
+impl<'a, N: Clone + 'a, E: Clone + 'a> BorrowedInterpolatedTextContents<'a, N, E> {
+    pub fn to_owned(self) -> OwnedInterpolatedTextContents<'a, N, E> {
+        match self {
+            BorrowedInterpolatedTextContents::Text(s) => OwnedInterpolatedTextContents::Text(s),
+            BorrowedInterpolatedTextContents::Expr(e) => OwnedInterpolatedTextContents::Expr(e.clone()),
+        }
+    }
+}
+
+impl<N, E> InterpolatedText<N, E> {
+    pub fn map<N2, E2, F>(&self, mut f: F) -> InterpolatedText<N2, E2>
+    where
+        F: FnMut(&Expr<N, E>) -> Expr<N2, E2>,
+    {
+        InterpolatedText {
+            head: self.head.clone(),
+            tail: self.tail.iter().map(|(e, s)| (f(e), s.clone())).collect(),
+        }
+    }
+
+    pub fn iter(&self) -> impl Iterator<Item = BorrowedInterpolatedTextContents<N, E>> {
+        use std::iter::once;
+        once(BorrowedInterpolatedTextContents::Text(self.head.as_ref())).chain(
+            self.tail.iter().flat_map(|(e, s)| {
+                once(BorrowedInterpolatedTextContents::Expr(e))
+                    .chain(once(BorrowedInterpolatedTextContents::Text(s)))
+            }),
+        )
+    }
+}
+
+impl<'a, N: Clone + 'a, E: Clone + 'a>
+    FromIterator<OwnedInterpolatedTextContents<'a, N, E>>
+    for InterpolatedText<N, E>
+{
+    fn from_iter<T>(iter: T) -> Self
+    where
+        T: IntoIterator<Item = OwnedInterpolatedTextContents<'a, N, E>>,
+    {
+        let mut res = InterpolatedText {
+            head: "".to_owned(),
+            tail: vec![],
+        };
+        // let mut empty_string = "".to_owned();
+        let mut crnt_str = &mut res.head;
+        for x in iter.into_iter() {
+            match x {
+                OwnedInterpolatedTextContents::Text(s) => crnt_str.push_str(s),
+                OwnedInterpolatedTextContents::Expr(e) => {
+                    // crnt_str = &mut empty_string;
+                    res.tail.push((e.clone(), "".to_owned()));
+                    crnt_str = &mut res.tail.last_mut().unwrap().1;
+                }
+            }
+        }
+        res
+    }
+}
+
+impl<N: Clone, E: Clone> Add for InterpolatedText<N, E> {
+    type Output = InterpolatedText<N, E>;
+    fn add(self, rhs: InterpolatedText<N, E>) -> Self::Output {
+        self.iter().chain(rhs.iter()).map(BorrowedInterpolatedTextContents::to_owned).collect()
+    }
+}
+
 /// Syntax tree for expressions
 #[derive(Debug, Clone, PartialEq)]
 pub enum Expr<Note, Embed> {
@@ -215,7 +323,7 @@ pub enum Expr<Note, Embed> {
     ///  `DoubleLit n                              ~  n`
     DoubleLit(Double),
     ///  `TextLit t                                ~  t`
-    TextLit(Builder),
+    TextLit(InterpolatedText<Note, Embed>),
     ///  `ListLit t [x, y, z]                      ~  [x, y, z] : List t`
     ListLit(Option<Box<Expr<Note, Embed>>>, Vec<Expr<Note, Embed>>),
     ///  `OptionalLit t [e]                        ~  [e] : Optional t`
@@ -358,13 +466,6 @@ impl<S, A> Expr<S, A> {
             _ => None,
         }
     }
-
-    pub fn text_lit(&self) -> Option<String> {
-        match *self {
-            Expr::TextLit(ref t) => Some(t.clone()), // FIXME?
-            _ => None,
-        }
-    }
 }
 
 impl<S: Clone, A: Clone> Expr<S, Expr<S, A>> {
@@ -570,7 +671,21 @@ impl<S, A: Display> Expr<S, A> {
                 a.fmt(f)
             }
             &DoubleLit(a) => a.fmt(f),
-            &TextLit(ref a) => <String as fmt::Debug>::fmt(a, f), // FIXME Format with Haskell escapes
+            &TextLit(ref a) => {
+                for x in a.iter() {
+                    match x {
+                        BorrowedInterpolatedTextContents::Text(a) => {
+                            <str as fmt::Debug>::fmt(a, f)?
+                        } // TODO Format escapes properly
+                        BorrowedInterpolatedTextContents::Expr(e) => {
+                            f.write_str("${")?;
+                            e.fmt(f)?;
+                            f.write_str("}")?;
+                        }
+                    }
+                }
+                Ok(())
+            }
             &Record(ref a) if a.is_empty() => f.write_str("{}"),
             &Record(ref a) => fmt_list("{ ", " }", a, f, |(k, t), f| {
                 write!(f, "{} : {}", k, t)
@@ -724,7 +839,6 @@ where
     Expr::App(bx(f.into()), bx(x.into()))
 }
 
-pub type Builder = String;
 pub type Double = f64;
 pub type Int = isize;
 pub type Integer = isize;
@@ -788,7 +902,7 @@ where
         NaturalLit(n) => NaturalLit(n),
         IntegerLit(n) => IntegerLit(n),
         DoubleLit(n) => DoubleLit(n),
-        TextLit(ref t) => TextLit(t.clone()),
+        TextLit(ref t) => TextLit(t.map(|e| map(e))),
         BinOp(o, ref x, ref y) => BinOp(o, bxmap(x), bxmap(y)),
         ListLit(ref t, ref es) => {
             let es = es.iter().map(&map).collect();
@@ -972,7 +1086,7 @@ pub fn shift<S, T, A: Clone>(d: isize, v: &V, e: &Expr<S, A>) -> Expr<T, A> {
         NaturalLit(a) => NaturalLit(*a),
         IntegerLit(a) => IntegerLit(*a),
         DoubleLit(a) => DoubleLit(*a),
-        TextLit(a) => TextLit(a.clone()),
+        TextLit(a) => TextLit(a.map(|e| shift(d, v, e))),
         ListLit(t, es) => ListLit(
             t.as_ref().map(|t| bx(shift(d, v, t))),
             es.iter().map(|e| shift(d, v, e)).collect(),
@@ -1075,7 +1189,7 @@ where
         NaturalLit(a) => NaturalLit(*a),
         IntegerLit(a) => IntegerLit(*a),
         DoubleLit(a) => DoubleLit(*a),
-        TextLit(a) => TextLit(a.clone()),
+        TextLit(a) => TextLit(a.map(|b| subst(v, e, b))),
         ListLit(a, b) => {
             let a2 = a.as_ref().map(|a| bx(subst(v, e, a)));
             let b2 = b.iter().map(|be| subst(v, e, be)).collect();
diff --git a/dhall_core/src/parser.rs b/dhall_core/src/parser.rs
index 57dd151..ddf3f8f 100644
--- a/dhall_core/src/parser.rs
+++ b/dhall_core/src/parser.rs
@@ -14,6 +14,8 @@ use crate::core::*;
 // are here and hopefully you can figure out how they work.
 
 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 ParseError = pest::error::Error<Rule>;
@@ -426,17 +428,25 @@ named!(raw_str<&'a str>; captured_str!(s) => s);
 
 named!(label<Label>; captured_str!(s) => Label::from(s.trim().to_owned()));
 
-// TODO: parse escapes and interpolation
-rule!(double_quote_literal<String>;
-    children!(strs*: raw_str) => {
-        strs.collect()
+rule!(double_quote_literal<ParsedText>;
+    children!(chunks*: double_quote_chunk) => {
+        chunks.collect()
     }
 );
 
-rule!(single_quote_literal<String>;
+// TODO: parse escapes
+rule!(double_quote_chunk<ParsedTextContents<'a>>;
+    children!(c: interpolation) => {
+        OwnedInterpolatedTextContents::Expr(*c)
+    },
+    captured_str!(s) => {
+        OwnedInterpolatedTextContents::Text(s)
+    },
+);
+
+rule!(single_quote_literal<ParsedText>;
     children!(eol: raw_str, contents: single_quote_continue) => {
-        contents.push(eol);
-        contents.into_iter().rev().collect()
+        contents.into_iter().rev().collect::<ParsedText>()
     }
 );
 rule!(escaped_quote_pair<&'a str>;
@@ -445,21 +455,22 @@ rule!(escaped_quote_pair<&'a str>;
 rule!(escaped_interpolation<&'a str>;
     children!() => "${"
 );
+rule!(interpolation<BoxExpr>;
+    children!(e: expression) => e
+);
 
-rule!(single_quote_continue<Vec<&'a str>>;
-    // TODO: handle interpolation
-    // children!(c: expression, rest: single_quote_continue) => {
-    //     rest.push(c); rest
-    // },
+rule!(single_quote_continue<Vec<ParsedTextContents<'a>>>;
+    children!(c: interpolation, rest: single_quote_continue) => {
+        rest.push(OwnedInterpolatedTextContents::Expr(*c)); rest
+    },
     children!(c: escaped_quote_pair, rest: single_quote_continue) => {
-        rest.push(c); rest
+        rest.push(OwnedInterpolatedTextContents::Text(c)); rest
     },
     children!(c: escaped_interpolation, rest: single_quote_continue) => {
-        rest.push(c); rest
+        rest.push(OwnedInterpolatedTextContents::Text(c)); rest
     },
-    // capture interpolation as string
     children!(c: raw_str, rest: single_quote_continue) => {
-        rest.push(c); rest
+        rest.push(OwnedInterpolatedTextContents::Text(c)); rest
     },
     children!() => {
         vec![]
diff --git a/dhall_parser/src/dhall.pest.visibility b/dhall_parser/src/dhall.pest.visibility
index 5dcaa19..8c0e67d 100644
--- a/dhall_parser/src/dhall.pest.visibility
+++ b/dhall_parser/src/dhall.pest.visibility
@@ -21,7 +21,7 @@ simple_label
 quoted_label
 label_raw
 label
-# double_quote_chunk
+double_quote_chunk
 double_quote_literal
 single_quote_continue
 single_quote_literal