Implement binary encoding

Closes #39

5 files changed, 106 insertions, 50 deletions

diff --git a/dhall_syntax/src/core/import.rs b/dhall_syntax/src/core/import.rs
index 00f293c..fbf2f7b 100644
--- a/dhall_syntax/src/core/import.rs
+++ b/dhall_syntax/src/core/import.rs
@@ -1,5 +1,3 @@
-use std::path::PathBuf;
-
 /// The beginning of a file path which anchors subsequent path components
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub enum FilePrefix {
@@ -16,7 +14,7 @@ pub enum FilePrefix {
 /// The location of import (i.e. local vs. remote vs. environment)
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub enum ImportLocation {
-    Local(FilePrefix, PathBuf),
+    Local(FilePrefix, Vec<String>),
     Remote(URL),
     Env(String),
     Missing,
@@ -26,7 +24,7 @@ pub enum ImportLocation {
 pub struct URL {
     pub scheme: Scheme,
     pub authority: String,
-    pub path: PathBuf,
+    pub path: Vec<String>,
     pub query: Option<String>,
     pub headers: Option<Box<ImportHashed>>,
 }
diff --git a/dhall_syntax/src/core/map.rs b/dhall_syntax/src/core/map.rs
index e5b399e..63f19cd 100644
--- a/dhall_syntax/src/core/map.rs
+++ b/dhall_syntax/src/core/map.rs
@@ -62,20 +62,30 @@ mod dup_tree_map {
         size: usize,
     }
 
-    pub type IterInternal<'a, K, V> =
+    pub type IterInternalIntermediate<'a, K, V> =
         iter::Zip<iter::Repeat<&'a K>, one_or_more::Iter<'a, V>>;
-    pub type Iter<'a, K, V> = iter::FlatMap<
+    pub type IterInternal<'a, K, V> = iter::FlatMap<
         btree_map::Iter<'a, K, OneOrMore<V>>,
-        IterInternal<'a, K, V>,
-        for<'b> fn((&'b K, &'b OneOrMore<V>)) -> IterInternal<'b, K, V>,
+        IterInternalIntermediate<'a, K, V>,
+        for<'b> fn(
+            (&'b K, &'b OneOrMore<V>),
+        ) -> IterInternalIntermediate<'b, K, V>,
     >;
-    pub type IntoIterInternal<K, V> =
+    pub struct Iter<'a, K, V> {
+        iter: IterInternal<'a, K, V>,
+        size: usize,
+    }
+    pub type IntoIterInternalIntermediate<K, V> =
         iter::Zip<iter::Repeat<K>, one_or_more::IntoIter<V>>;
-    pub type IntoIter<K, V> = iter::FlatMap<
+    pub type IntoIterInternal<K, V> = iter::FlatMap<
         btree_map::IntoIter<K, OneOrMore<V>>,
-        IntoIterInternal<K, V>,
-        fn((K, OneOrMore<V>)) -> IntoIterInternal<K, V>,
+        IntoIterInternalIntermediate<K, V>,
+        fn((K, OneOrMore<V>)) -> IntoIterInternalIntermediate<K, V>,
     >;
+    pub struct IntoIter<K: Clone, V> {
+        iter: IntoIterInternal<K, V>,
+        size: usize,
+    }
 
     impl<K, V> DupTreeMap<K, V> {
         pub fn new() -> Self
@@ -115,10 +125,13 @@ mod dup_tree_map {
         {
             fn foo<'a, K, V>(
                 (k, oom): (&'a K, &'a OneOrMore<V>),
-            ) -> IterInternal<'a, K, V> {
+            ) -> IterInternalIntermediate<'a, K, V> {
                 iter::repeat(k).zip(oom.iter())
             }
-            self.map.iter().flat_map(foo)
+            Iter {
+                iter: self.map.iter().flat_map(foo),
+                size: self.size,
+            }
         }
     }
 
@@ -139,13 +152,18 @@ mod dup_tree_map {
         type IntoIter = IntoIter<K, V>;
 
         fn into_iter(self) -> Self::IntoIter {
-            fn foo<K, V>((k, oom): (K, OneOrMore<V>)) -> IntoIterInternal<K, V>
+            fn foo<K, V>(
+                (k, oom): (K, OneOrMore<V>),
+            ) -> IntoIterInternalIntermediate<K, V>
             where
                 K: Clone,
             {
                 iter::repeat(k).zip(oom.into_iter())
             }
-            self.map.into_iter().flat_map(foo)
+            IntoIter {
+                iter: self.map.into_iter().flat_map(foo),
+                size: self.size,
+            }
         }
     }
 
@@ -176,4 +194,41 @@ mod dup_tree_map {
             map
         }
     }
+
+    impl<'a, K, V> Iterator for Iter<'a, K, V> {
+        type Item = (&'a K, &'a V);
+
+        fn next(&mut self) -> Option<Self::Item> {
+            let next = self.iter.next();
+            if next.is_some() {
+                self.size -= 1;
+            }
+            next
+        }
+
+        fn size_hint(&self) -> (usize, Option<usize>) {
+            (self.size, Some(self.size))
+        }
+    }
+
+    impl<K, V> Iterator for IntoIter<K, V>
+    where
+        K: Clone,
+    {
+        type Item = (K, V);
+
+        fn next(&mut self) -> Option<Self::Item> {
+            let next = self.iter.next();
+            if next.is_some() {
+                self.size -= 1;
+            }
+            next
+        }
+
+        fn size_hint(&self) -> (usize, Option<usize>) {
+            (self.size, Some(self.size))
+        }
+    }
+
+    // unsafe impl<K, V> iter::TrustedLen for IntoIter<K, V> {}
 }
diff --git a/dhall_syntax/src/core/text.rs b/dhall_syntax/src/core/text.rs
index e79a86b..0ce1e6f 100644
--- a/dhall_syntax/src/core/text.rs
+++ b/dhall_syntax/src/core/text.rs
@@ -43,6 +43,10 @@ impl<SubExpr> InterpolatedTextContents<SubExpr> {
 }
 
 impl<SubExpr> InterpolatedText<SubExpr> {
+    pub fn len(&self) -> usize {
+        1 + 2 * self.tail.len()
+    }
+
     pub fn head(&self) -> &str {
         &self.head
     }
@@ -74,17 +78,12 @@ impl<SubExpr> InterpolatedText<SubExpr> {
 
     pub fn iter<'a>(
         &'a self,
-    ) -> impl Iterator<Item = InterpolatedTextContents<SubExpr>> + 'a
-    where
-        SubExpr: Clone,
-    {
+    ) -> impl Iterator<Item = InterpolatedTextContents<&'a SubExpr>> + 'a {
         use std::iter::once;
         use InterpolatedTextContents::{Expr, Text};
-        once(Text(self.head.clone()))
-            .chain(self.tail.iter().flat_map(|(e, s)| {
-                once(Expr(SubExpr::clone(e))).chain(once(Text(s.clone())))
-            }))
-            .filter(|c| !c.is_empty())
+        let exprs = self.tail.iter().map(|(e, _)| Expr(e));
+        let texts = self.tail.iter().map(|(_, s)| Text(s.clone()));
+        once(Text(self.head.clone())).chain(itertools::interleave(exprs, texts))
     }
 
     pub fn into_iter(
@@ -92,13 +91,11 @@ impl<SubExpr> InterpolatedText<SubExpr> {
     ) -> impl Iterator<Item = InterpolatedTextContents<SubExpr>> {
         use std::iter::once;
         use InterpolatedTextContents::{Expr, Text};
-        once(Text(self.head))
-            .chain(
-                self.tail
-                    .into_iter()
-                    .flat_map(|(e, s)| once(Expr(e)).chain(once(Text(s)))),
-            )
-            .filter(|c| !c.is_empty())
+        once(Text(self.head)).chain(
+            self.tail
+                .into_iter()
+                .flat_map(|(e, s)| once(Expr(e)).chain(once(Text(s)))),
+        )
     }
 }
 
diff --git a/dhall_syntax/src/parser.rs b/dhall_syntax/src/parser.rs
index c847b29..3e461df 100644
--- a/dhall_syntax/src/parser.rs
+++ b/dhall_syntax/src/parser.rs
@@ -2,7 +2,6 @@ use itertools::Itertools;
 use pest::iterators::Pair;
 use pest::Parser;
 use std::borrow::Cow;
-use std::path::PathBuf;
 use std::rc::Rc;
 
 use dhall_generated_parser::{DhallParser, Rule};
@@ -557,24 +556,24 @@ make_parser! {
         },
         [quoted_path_component(s)] => s.to_string(),
     ));
-    rule!(path<PathBuf>; children!(
+    rule!(path<Vec<String>>; children!(
         [path_component(components)..] => {
             components.collect()
         }
     ));
 
-    rule_group!(local<(FilePrefix, PathBuf)>);
+    rule_group!(local<(FilePrefix, Vec<String>)>);
 
-    rule!(parent_path<(FilePrefix, PathBuf)> as local; children!(
+    rule!(parent_path<(FilePrefix, Vec<String>)> as local; children!(
         [path(p)] => (FilePrefix::Parent, p)
     ));
-    rule!(here_path<(FilePrefix, PathBuf)> as local; children!(
+    rule!(here_path<(FilePrefix, Vec<String>)> as local; children!(
         [path(p)] => (FilePrefix::Here, p)
     ));
-    rule!(home_path<(FilePrefix, PathBuf)> as local; children!(
+    rule!(home_path<(FilePrefix, Vec<String>)> as local; children!(
         [path(p)] => (FilePrefix::Home, p)
     ));
-    rule!(absolute_path<(FilePrefix, PathBuf)> as local; children!(
+    rule!(absolute_path<(FilePrefix, Vec<String>)> as local; children!(
         [path(p)] => (FilePrefix::Absolute, p)
     ));
 
diff --git a/dhall_syntax/src/printer.rs b/dhall_syntax/src/printer.rs
index 0162693..f1ce230 100644
--- a/dhall_syntax/src/printer.rs
+++ b/dhall_syntax/src/printer.rs
@@ -353,23 +353,21 @@ impl Display for Hash {
 }
 impl Display for ImportHashed {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        use std::path::PathBuf;
         use FilePrefix::*;
         use ImportLocation::*;
-        let quoted_path_component = |s: &str| -> String {
+        let fmt_remote_path_component = |s: &str| -> String {
+            use percent_encoding::{
+                utf8_percent_encode, PATH_SEGMENT_ENCODE_SET,
+            };
+            utf8_percent_encode(s, PATH_SEGMENT_ENCODE_SET).to_string()
+        };
+        let fmt_local_path_component = |s: &str| -> String {
             if s.chars().all(|c| c.is_ascii_alphanumeric()) {
                 s.to_owned()
             } else {
                 format!("\"{}\"", s)
             }
         };
-        let fmt_path = |f: &mut fmt::Formatter, p: &PathBuf| {
-            let res: String = p
-                .iter()
-                .map(|c| quoted_path_component(c.to_string_lossy().as_ref()))
-                .join("/");
-            f.write_str(&res)
-        };
 
         match &self.location {
             Local(prefix, path) => {
@@ -380,11 +378,20 @@ impl Display for ImportHashed {
                     Absolute => "",
                 };
                 write!(f, "{}/", prefix)?;
-                fmt_path(f, path)?;
+                let path: String = path
+                    .iter()
+                    .map(|c| fmt_local_path_component(c.as_ref()))
+                    .join("/");
+                f.write_str(&path)?;
             }
             Remote(url) => {
                 write!(f, "{}://{}/", url.scheme, url.authority,)?;
-                fmt_path(f, &url.path)?;
+                let path: String = url
+                    .path
+                    .iter()
+                    .map(|c| fmt_remote_path_component(c.as_ref()))
+                    .join("/");
+                f.write_str(&path)?;
                 if let Some(q) = &url.query {
                     write!(f, "?{}", q)?
                 }