Reference input strings without copying

5 files changed, 70 insertions, 66 deletions

diff --git a/src/core.rs b/src/core.rs
index 8e59141..85ebf1b 100644
--- a/src/core.rs
+++ b/src/core.rs
@@ -1,3 +1,4 @@
+use std::borrow::Cow;
 use std::collections::HashMap;
 use std::path::PathBuf;
 
@@ -43,7 +44,7 @@ module Dhall.Core (
 /// Note that Dhall does not support functions from terms to types and therefore
 /// Dhall is not a dependently typed language
 ///
-#[derive(Debug, PartialEq, Eq)] // (Show, Bounded, Enum)
+#[derive(Debug, Copy, Clone, PartialEq, Eq)] // (Show, Bounded, Enum)
 pub enum Const {
     Type,
     Kind,
@@ -51,7 +52,7 @@ pub enum Const {
 
 
 /// Path to an external resource
-#[derive(Debug, PartialEq, Eq)] // (Eq, Ord, Show)
+#[derive(Debug, Clone, PartialEq, Eq)] // (Eq, Ord, Show)
 pub enum Path {
     File(PathBuf),
     URL(String),
@@ -93,8 +94,8 @@ pub enum Path {
 /// Zero indices are omitted when pretty-printing `Var`s and non-zero indices
 /// appear as a numeric suffix.
 ///
-#[derive(Debug, PartialEq, Eq)] // (Eq, Show)
-pub struct Var(pub String, pub Int);
+#[derive(Debug, Clone, PartialEq, Eq)] // (Eq, Show)
+pub struct V<'i>(pub Cow<'i, str>, pub usize);
 
 /*
 instance IsString Var where
@@ -105,39 +106,39 @@ instance Buildable Var where
 */
 
 /// Syntax tree for expressions
-#[derive(Debug, PartialEq)] // (Functor, Foldable, Traversable, Show)
-pub enum Expr<S, A> {
+#[derive(Debug, Clone, PartialEq)] // (Functor, Foldable, Traversable, Show)
+pub enum Expr<'i, S, A> {
     ///  `Const c                                  ~  c`
     Const(Const),
     ///  `Var (V x 0)                              ~  x`<br>
     ///  `Var (V x n)                              ~  x@n`
-    Var(Var),
+    Var(V<'i>),
     ///  `Lam x     A b                            ~  λ(x : A) -> b`
-    Lam(String, Box<Expr<S, A>>, Box<Expr<S, A>>),
+    Lam(Cow<'i, str>, Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `Pi "_" A B                               ~        A  -> B`
     ///  `Pi x   A B                               ~  ∀(x : A) -> B`
-    Pi(String, Box<Expr<S, A>>, Box<Expr<S, A>>),
+    Pi(Cow<'i, str>, Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `App f A                                  ~  f A`
-    App(Box<Expr<S, A>>, Box<Expr<S, A>>),
+    App(Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `Let x Nothing  r e  ~  let x     = r in e`
     ///  `Let x (Just t) r e  ~  let x : t = r in e`
-    Let(String, Option<Box<Expr<S, A>>>, Box<Expr<S, A>>, Box<Expr<S, A>>),
+    Let(Cow<'i, str>, Option<Box<Expr<'i, S, A>>>, Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `Annot x t                                ~  x : t`
-    Annot(Box<Expr<S, A>>, Box<Expr<S, A>>),
+    Annot(Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `Bool                                     ~  Bool`
     Bool,
     ///  `BoolLit b                                ~  b`
     BoolLit(bool),
     ///  `BoolAnd x y                              ~  x && y`
-    BoolAnd(Box<Expr<S, A>>, Box<Expr<S, A>>),
+    BoolAnd(Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `BoolOr  x y                              ~  x || y`
-    BoolOr(Box<Expr<S, A>>, Box<Expr<S, A>>),
+    BoolOr(Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `BoolEQ  x y                              ~  x == y`
-    BoolEQ(Box<Expr<S, A>>, Box<Expr<S, A>>),
+    BoolEQ(Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `BoolNE  x y                              ~  x != y`
-    BoolNE(Box<Expr<S, A>>, Box<Expr<S, A>>),
+    BoolNE(Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `BoolIf x y z                             ~  if x then y else z`
-    BoolIf(Box<Expr<S, A>>, Box<Expr<S, A>>, Box<Expr<S, A>>),
+    BoolIf(Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `Natural                                  ~  Natural`
     Natural,
     ///  `NaturalLit n                             ~  +n`
@@ -153,9 +154,9 @@ pub enum Expr<S, A> {
     ///  `NaturalOdd                               ~  Natural/odd`
     NaturalOdd,
     ///  `NaturalPlus x y                          ~  x + y`
-    NaturalPlus(Box<Expr<S, A>>, Box<Expr<S, A>>),
+    NaturalPlus(Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `NaturalTimes x y                         ~  x * y`
-    NaturalTimes(Box<Expr<S, A>>, Box<Expr<S, A>>),
+    NaturalTimes(Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `Integer                                  ~  Integer`
     Integer,
     ///  `IntegerLit n                             ~  n`
@@ -169,11 +170,11 @@ pub enum Expr<S, A> {
     ///  `TextLit t                                ~  t`
     TextLit(Builder),
     ///  `TextAppend x y                           ~  x ++ y`
-    TextAppend(Box<Expr<S, A>>, Box<Expr<S, A>>),
+    TextAppend(Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `List                                     ~  List`
     List,
     ///  `ListLit t [x, y, z]                      ~  [x, y, z] : List t`
-    ListLit(Box<Expr<S, A>>, Vec<Expr<S, A>>),
+    ListLit(Box<Expr<'i, S, A>>, Vec<Expr<'i, S, A>>),
     ///  `ListBuild                                ~  List/build`
     ListBuild,
     ///  `ListFold                                 ~  List/fold`
@@ -192,25 +193,25 @@ pub enum Expr<S, A> {
     Optional,
     ///  `OptionalLit t [e]                        ~  [e] : Optional t`
     ///  `OptionalLit t []                         ~  []  : Optional t`
-    OptionalLit(Box<Expr<S, A>>, Vec<Expr<S, A>>),
+    OptionalLit(Box<Expr<'i, S, A>>, Vec<Expr<'i, S, A>>),
     ///  `OptionalFold                             ~  Optional/fold`
     OptionalFold,
     ///  `Record            [(k1, t1), (k2, t2)]   ~  { k1 : t1, k2 : t1 }`
-    Record(HashMap<String, Expr<S, A>>),
+    Record(HashMap<Cow<'i, str>, Expr<'i, S, A>>),
     ///  `RecordLit         [(k1, v1), (k2, v2)]   ~  { k1 = v1, k2 = v2 }`
-    RecordLit(HashMap<String, Expr<S, A>>),
+    RecordLit(HashMap<Cow<'i, str>, Expr<'i, S, A>>),
     ///  `Union             [(k1, t1), (k2, t2)]   ~  < k1 : t1, k2 : t2 >`
-    Union(HashMap<String, Expr<S, A>>),
+    Union(HashMap<Cow<'i, str>, Expr<'i, S, A>>),
     ///  `UnionLit (k1, v1) [(k2, t2), (k3, t3)]   ~  < k1 = t1, k2 : t2, k3 : t3 >`
-    UnionLit(String, Box<Expr<S, A>>, HashMap<String, Expr<S, A>>),
+    UnionLit(Cow<'i, str>, Box<Expr<'i, S, A>>, HashMap<Cow<'i, str>, Expr<'i, S, A>>),
     ///  `Combine x y                              ~  x ∧ y`
-    Combine(Box<Expr<S, A>>, Box<Expr<S, A>>),
+    Combine(Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `Merge x y t                              ~  merge x y : t`
-    Merge(Box<Expr<S, A>>, Box<Expr<S, A>>, Box<Expr<S, A>>),
+    Merge(Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>, Box<Expr<'i, S, A>>),
     ///  `Field e x                                ~  e.x`
-    Field(Box<Expr<S, A>>, String),
+    Field(Box<Expr<'i, S, A>>, Cow<'i, str>),
     ///  `Note S x                                 ~  e`
-    Note(S, Box<Expr<S, A>>),
+    Note(S, Box<Expr<'i, S, A>>),
     ///  `Embed path                               ~  path`
     Embed(A),
 }
diff --git a/src/grammar.lalrpop b/src/grammar.lalrpop
index c49e2b6..3e216ac 100644
--- a/src/grammar.lalrpop
+++ b/src/grammar.lalrpop
@@ -3,17 +3,18 @@ use core::Expr::*;
 use grammar_util::*;
 use lexer::*;
 
+use std::borrow::Cow;
 use std::collections::HashMap;
 use std::iter;
 use std::iter::FromIterator;
 
-grammar;
+grammar<'input>;
 
 extern {
     type Location = usize;
     type Error = LexicalError;
 
-    enum Tok {
+    enum Tok<'input> {
         Pi => Tok::Pi,
         Lambda => Tok::Lambda,
         Combine => Tok::Combine,
@@ -23,7 +24,7 @@ extern {
         Nat => Tok::Natural(<usize>),
         Text => Tok::Text(<String>),
         Bool => Tok::Bool(<bool>),
-        Label => Tok::Identifier(<String>),
+        Label => Tok::Identifier(<Cow<'input, str>>),
         Const => Tok::Const(<core::Const>),
         Let => Tok::Keyword(Keyword::Let),
         In => Tok::Keyword(Keyword::In),
@@ -54,36 +55,36 @@ extern {
     }
 }
 
-pub Expr: BoxExpr = { // exprA
+pub Expr: BoxExpr<'input> = { // exprA
     <ExprB> ":" <Expr> => bx(Annot(<>)),
     ExprB,
 };
 
-ExprB: BoxExpr = {
+ExprB: BoxExpr<'input> = {
     Lambda "(" <Label> ":" <Expr> ")" "->" <ExprB> => bx(Lam(<>)),
     Pi "(" <Label> ":" <Expr> ")" "->" <ExprB> => bx(Pi(<>)),
     If <Expr> Then <ExprB> Else <ExprC> => bx(BoolIf(<>)),
-    <ExprC> "->" <ExprB> => bx(Pi("_".to_owned(), <>)),
+    <ExprC> "->" <ExprB> => bx(Pi(Cow::Borrowed("_"), <>)),
     Let <Label> <(":" <Expr>)?> "=" <Expr> In <ExprB> => bx(Let(<>)),
     "[" <a:Elems> "]" ":" <b:ListLike> <c:ExprE> => bx(b(c, a)),
     ExprC,
 };
 
-ListLike: ExprListFn = {
+ListLike: ExprListFn<'input> = {
     List => ListLit,
     Optional => OptionalLit,
 };
 
-BoolOr: ExprOpFn = { "||" => BoolOr };
-NaturalPlus: ExprOpFn = { "+" => NaturalPlus };
-TextAppend: ExprOpFn = { "++" => TextAppend };
-BoolAnd: ExprOpFn = { "&&" => BoolAnd };
-CombineOp: ExprOpFn = { Combine => Combine };
-NaturalTimes: ExprOpFn = { "*" => NaturalTimes };
-BoolEQ: ExprOpFn = { "==" => BoolEQ };
-BoolNE: ExprOpFn = { "!=" => BoolNE };
+BoolOr: ExprOpFn<'input> = { "||" => BoolOr };
+NaturalPlus: ExprOpFn<'input> = { "+" => NaturalPlus };
+TextAppend: ExprOpFn<'input> = { "++" => TextAppend };
+BoolAnd: ExprOpFn<'input> = { "&&" => BoolAnd };
+CombineOp: ExprOpFn<'input> = { Combine => Combine };
+NaturalTimes: ExprOpFn<'input> = { "*" => NaturalTimes };
+BoolEQ: ExprOpFn<'input> = { "==" => BoolEQ };
+BoolNE: ExprOpFn<'input> = { "!=" => BoolNE };
 
-Tier<NextTier, Op>: BoxExpr = {
+Tier<NextTier, Op>: BoxExpr<'input> = {
     <a:NextTier> <f:Op> <b:Tier<NextTier, Op>> => bx(f(a, b)),
     // <b:Tier<NextTier, Op>> <f:Op> <a:NextTier> => bx(f(a, b)),
     NextTier,
@@ -98,7 +99,7 @@ ExprC5 = Tier<ExprC6, NaturalTimes>;
 ExprC6 = Tier<ExprC7, BoolEQ>;
 ExprC7 = Tier<ExprD, BoolNE>;
 
-ExprD: BoxExpr = {
+ExprD: BoxExpr<'input> = {
     <v:(ExprE)+> => {
         let mut it = v.into_iter();
         let f = it.next().unwrap();
@@ -106,17 +107,17 @@ ExprD: BoxExpr = {
     }
 };
 
-ExprE: BoxExpr = {
+ExprE: BoxExpr<'input> = {
     <a:ExprF> <fields:("." <Label>)*> => {
         fields.into_iter().fold(a, |x, f| bx(Field(x, f)))
     },
 };
 
-ExprF: BoxExpr = {
+ExprF: BoxExpr<'input> = {
     Nat => bx(NaturalLit(<>)),
     Int => bx(IntegerLit(<>)),
     Text => bx(TextLit(<>)),
-    Label => bx(Var(core::Var(<>, 0))), // FIXME support var@n syntax
+    Label => bx(Var(core::V(<>, 0))), // FIXME support var@n syntax
     Const => bx(Const(<>)),
     List => bx(List),
     Optional => bx(Optional),
@@ -135,7 +136,7 @@ SepBy1<S, T>: iter::Chain<::std::vec::IntoIter<T>, iter::Once<T>> = {
     <v:(<T> S)*> <last:T> => v.into_iter().chain(iter::once(last)),
 };
 
-Elems: Vec<ParsedExpr> = {
+Elems: Vec<ParsedExpr<'input>> = {
     <v:SepBy<",", Expr>> => {
         v.into_iter()
          .map(|b| *b)
@@ -143,18 +144,18 @@ Elems: Vec<ParsedExpr> = {
     }
 };
 
-RecordLit: BoxExpr = {
+RecordLit: BoxExpr<'input> = {
     "{" "=" "}" => bx(RecordLit(HashMap::new())),
     "{" <FieldValues> "}" => bx(RecordLit(HashMap::from_iter(<>))),
 };
 
-Record: BoxExpr = {
+Record: BoxExpr<'input> = {
     "{" <FieldTypes> "}" => bx(Record(HashMap::from_iter(<>))),
 };
 
 FieldValues = SepBy1<",", Field<"=">>;
 FieldTypes = SepBy<",", Field<":">>;
 
-Field<Sep>: (String, ParsedExpr) = {
+Field<Sep>: (Cow<'input, str>, ParsedExpr<'input>) = {
     <a:Label> Sep <b:Expr> => (a, *b),
 };
diff --git a/src/grammar_util.rs b/src/grammar_util.rs
index 4a14175..cf0ee59 100644
--- a/src/grammar_util.rs
+++ b/src/grammar_util.rs
@@ -1,16 +1,16 @@
 use core::Expr;
 use lexer::Builtin;
 
-pub type ParsedExpr = Expr<(), ()>;
-pub type BoxExpr = Box<ParsedExpr>;
-pub type ExprOpFn = fn(BoxExpr, BoxExpr) -> ParsedExpr;
-pub type ExprListFn = fn(BoxExpr, Vec<ParsedExpr>) -> ParsedExpr;
+pub type ParsedExpr<'i> = Expr<'i, (), ()>;
+pub type BoxExpr<'i> = Box<ParsedExpr<'i>>;
+pub type ExprOpFn<'i> = fn(BoxExpr<'i>, BoxExpr<'i>) -> ParsedExpr<'i>;
+pub type ExprListFn<'i> = fn(BoxExpr<'i>, Vec<ParsedExpr<'i>>) -> ParsedExpr<'i>;
 
 pub fn bx<T>(x: T) -> Box<T> {
     Box::new(x)
 }
 
-pub fn builtin_expr<S, A>(b: Builtin) -> Expr<S, A> {
+pub fn builtin_expr<'i, S, A>(b: Builtin) -> Expr<'i, S, A> {
     match b {
         Builtin::Natural => Expr::Natural,
         Builtin::NaturalFold => Expr::NaturalFold,
diff --git a/src/lexer.rs b/src/lexer.rs
index beb3b83..ca181ce 100644
--- a/src/lexer.rs
+++ b/src/lexer.rs
@@ -2,6 +2,8 @@ use nom;
 
 use core::Const;
 
+use std::borrow::Cow;
+
 #[derive(Debug, PartialEq, Eq)]
 pub enum Keyword {
     Let,
@@ -40,8 +42,8 @@ pub enum Builtin {
 }
 
 #[derive(Debug, PartialEq, Eq)]
-pub enum Tok {
-    Identifier(String),
+pub enum Tok<'i> {
+    Identifier(Cow<'i, str>),
     Keyword(Keyword),
     Builtin(Builtin),
     ListLike(ListLike),
@@ -258,7 +260,7 @@ named!(token<&str, Tok>, alt!(
     map!(list_like, Tok::ListLike) |
     map!(natural, Tok::Natural) |
     map!(integer, Tok::Integer) |
-    map!(identifier, |s: &str| Tok::Identifier(s.to_owned())) |
+    map!(identifier, |s| Tok::Identifier(Cow::Borrowed(s))) |
     map!(string_lit, Tok::Text) |
 
     value!(Tok::BraceL, tag!("{")) |
@@ -334,7 +336,7 @@ impl<'input> Lexer<'input> {
 }
 
 impl<'input> Iterator for Lexer<'input> {
-    type Item = Spanned<Tok, usize, LexicalError>;
+    type Item = Spanned<Tok<'input>, usize, LexicalError>;
 
     fn next(&mut self) -> Option<Self::Item> {
         use nom::IResult::*;
@@ -369,12 +371,12 @@ fn test_lex() {
     let s = "λ(b : Bool) → b == False";
     let expected = [Lambda,
                     ParenL,
-                    Identifier("b".to_owned()),
+                    Identifier(Cow::Borrowed("b")),
                     Ascription,
                     Builtin(self::Builtin::Bool),
                     ParenR,
                     Arrow,
-                    Identifier("b".to_owned()),
+                    Identifier(Cow::Borrowed("b")),
                     CompareEQ,
                     Bool(false)];
     let lexer = Lexer::new(s);
diff --git a/src/parser.rs b/src/parser.rs
index e3f3420..945d150 100644
--- a/src/parser.rs
+++ b/src/parser.rs
@@ -4,7 +4,7 @@ use grammar;
 use grammar_util::BoxExpr;
 use lexer::{Lexer, LexicalError, Tok};
 
-pub type ParseError = lalrpop_util::ParseError<usize, Tok, LexicalError>;
+pub type ParseError<'i> = lalrpop_util::ParseError<usize, Tok<'i>, LexicalError>;
 
 pub fn parse_expr(s: &str) -> Result<BoxExpr, ParseError>  {
     grammar::parse_Expr(Lexer::new(s))