From 7757e58229d077a4f2fd1fe4beb4062e006b04b8 Mon Sep 17 00:00:00 2001
From: Cassie Jones <code@witchoflight.com>
Date: Mon, 10 Feb 2020 20:42:07 -0500
Subject: [PATCH] Change List to use Cow<[Sexp]> instead of Vec<Sexp>

We would like to use Cow<[Sexp]> since this enables storing slices
inside the lists, and therefore allows you to calculate "cdr"
efficiently. It doesn't improve "cons" at all, however, so this might
not be the right option.
---
 src/parser.rs | 16 ++++++++--------
 src/sexp.rs   | 34 ++++++++++++++++++----------------
 2 files changed, 26 insertions(+), 24 deletions(-)

diff --git a/src/parser.rs b/src/parser.rs
index 6039a0d..0470fab 100644
--- a/src/parser.rs
+++ b/src/parser.rs
@@ -14,6 +14,7 @@
 
 use sexp::Sexp;
 use span::{ByteSpan, Span};
+use std::borrow::Cow;
 
 // Parsing Types ///////////////////////////////////////////////////////////////
 
@@ -206,7 +207,7 @@ pub fn parse_expression(input: &str, start_loc: usize) -> ParseResult<Sexp, Pars
     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Sexp);
 
     match input.chars().next() {
-        Some('0'...'9') => parse_number(input, start_loc),
+        Some('0'..='9') => parse_number(input, start_loc),
         Some('(') | Some('{') | Some('[') => parse_list(input, start_loc),
         Some('#') => parse_character(input, start_loc),
         Some('"') => parse_string(input, start_loc),
@@ -217,7 +218,7 @@ pub fn parse_expression(input: &str, start_loc: usize) -> ParseResult<Sexp, Pars
                 Done(
                     rest,
                     Sexp::List(
-                        vec![Sexp::Sym("quote".into(), quote_span), result],
+                        Cow::from(vec![Sexp::Sym("quote".into(), quote_span), result]),
                         quote_span.union(&span),
                     ),
                 )
@@ -231,7 +232,7 @@ pub fn parse_expression(input: &str, start_loc: usize) -> ParseResult<Sexp, Pars
                 Done(
                     rest,
                     Sexp::List(
-                        vec![Sexp::Sym("quasiquote".into(), quote_span), result],
+                        Cow::from(vec![Sexp::Sym("quasiquote".into(), quote_span), result]),
                         quote_span.union(&span),
                     ),
                 )
@@ -247,7 +248,7 @@ pub fn parse_expression(input: &str, start_loc: usize) -> ParseResult<Sexp, Pars
                         Done(
                             rest,
                             Sexp::List(
-                                vec![Sexp::Sym("unquote-splicing".into(), quote_span), result],
+                                Cow::from(vec![Sexp::Sym("unquote-splicing".into(), quote_span), result]),
                                 quote_span.union(&span),
                             ),
                         )
@@ -262,7 +263,7 @@ pub fn parse_expression(input: &str, start_loc: usize) -> ParseResult<Sexp, Pars
                         Done(
                             rest,
                             Sexp::List(
-                                vec![Sexp::Sym("unquote".into(), quote_span), result],
+                                Cow::from(vec![Sexp::Sym("unquote".into(), quote_span), result]),
                                 quote_span.union(&span),
                             ),
                         )
@@ -304,7 +305,7 @@ pub fn parse_list(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseError
         match input.chars().nth(0) {
             Some(c @ ')') | Some(c @ '}') | Some(c @ ']') => match (first_char, c) {
                 ('(', ')') | ('{', '}') | ('[', ']') => {
-                    return Done(&input[1..], Sexp::List(members, (start_loc, loc + 1)))
+                    return Done(&input[1..], Sexp::List(Cow::from(members), (start_loc, loc + 1)))
                 }
                 _ => {
                     return Error(ParseError::List(
@@ -424,7 +425,7 @@ pub fn parse_symbol(input: &str, start_loc: usize) -> ParseResult<Sexp, ParseErr
     let (input, start_loc) = consume_whitespace!(input, start_loc, ParseError::Symbol);
 
     match input.chars().next() {
-        Some(c @ '#') | Some(c @ ':') | Some(c @ '0'...'9') => {
+        Some(c @ '#') | Some(c @ ':') | Some(c @ '0'..='9') => {
             return Error(ParseError::Symbol(
                 Box::new(ParseError::Unexpected(c, start_loc)),
                 (0, 0).offset(start_loc),
@@ -534,7 +535,6 @@ pub fn parse_character(input: &str, start_loc: usize) -> ParseResult<Sexp, Parse
 
 #[cfg(test)]
 mod test {
-    use parser::ParseResult::*;
     use parser::*;
     use sexp::Sexp;
     use span::Span;
diff --git a/src/sexp.rs b/src/sexp.rs
index 4484fd3..8eb72f0 100644
--- a/src/sexp.rs
+++ b/src/sexp.rs
@@ -1,6 +1,6 @@
 //! The `Sexp` type, the representation of s-expressions.
 
-use std::borrow::Cow;
+use std::borrow::{Cow, ToOwned};
 
 use span::{ByteSpan, Span};
 
@@ -8,10 +8,10 @@ use span::{ByteSpan, Span};
 ///
 /// `Sexp` carries the source code location it came from along with it for later
 /// diagnostic purposes.
-#[derive(Debug, PartialEq, Clone, PartialOrd)]
+#[derive(Clone, Debug, PartialEq, PartialOrd)]
 pub enum Sexp<'a, Loc = ByteSpan>
 where
-    Loc: Span,
+    Loc: Span + Clone,
 {
     /// A value representing a symbol.
     Sym(Cow<'a, str>, Loc),
@@ -26,12 +26,12 @@ where
     /// decimal point will be parsed as a `Float`.
     Float(f64, Loc),
     /// A list of subexpressions.
-    List(Vec<Sexp<'a, Loc>>, Loc),
+    List(Cow<'a, [Sexp<'a, Loc>]>, Loc),
 }
 
 impl<'a, Loc> Sexp<'a, Loc>
 where
-    Loc: Span,
+    Loc: Span + Clone,
 {
     /// Gives a reference to the source location contained in the `Sexp`.
     pub fn get_loc(&self) -> &Loc {
@@ -67,19 +67,21 @@ where
 
 impl<'a, Loc> Sexp<'a, Loc>
 where
-    Loc: Span + Clone,
+    Loc: Span + ToOwned + Clone,
+    Loc::Owned: Span + Clone,
 {
     /// Take ownership of an s-expression's contents.
-    pub fn to_owned(&self) -> Sexp<'static, Loc> {
-        match *self {
-            Sexp::Sym(ref s, ref l) => Sexp::Sym(extend_cow(s), l.clone()),
-            Sexp::Str(ref s, ref l) => Sexp::Str(extend_cow(s), l.clone()),
-            Sexp::Char(c, ref l) => Sexp::Char(c, l.clone()),
-            Sexp::Int(i, ref l) => Sexp::Int(i, l.clone()),
-            Sexp::Float(f, ref l) => Sexp::Float(f, l.clone()),
-            Sexp::List(ref xs, ref l) => {
-                Sexp::List(xs.iter().map(Sexp::to_owned).collect(), l.clone())
-            }
+    pub fn to_owned(&self) -> Sexp<'static, Loc::Owned> {
+        match self {
+            Sexp::Sym(s, l) => Sexp::Sym(extend_cow(s), l.to_owned()),
+            Sexp::Str(s, l) => Sexp::Str(extend_cow(s), l.to_owned()),
+            Sexp::Char(c, l) => Sexp::Char(*c, l.to_owned()),
+            Sexp::Int(i, l) => Sexp::Int(*i, l.to_owned()),
+            Sexp::Float(f, l) => Sexp::Float(*f, l.to_owned()),
+            Sexp::List(xs, l) => Sexp::List(
+                xs.iter().map(Sexp::to_owned).collect(),
+                l.to_owned(),
+            ),
         }
     }
 }
-- 
2.43.2