Merge pull request #99 from FintanH/fintan/canonicalize

Introduce Canonicalize

5 files changed, 102 insertions, 24 deletions

diff --git a/dhall/src/phase/binary.rs b/dhall/src/phase/binary.rs
index 76d7ec9..4831c7e 100644
--- a/dhall/src/phase/binary.rs
+++ b/dhall/src/phase/binary.rs
@@ -1,11 +1,12 @@
 use itertools::Itertools;
 use serde_cbor::value::value as cbor;
 use std::iter::FromIterator;
+use std::vec;
 
 use dhall_syntax::map::DupTreeMap;
 use dhall_syntax::{
     rc, Expr, ExprF, FilePrefix, Hash, Import, ImportLocation, ImportMode,
-    Integer, InterpolatedText, Label, Natural, Scheme, URL, V,
+    Integer, InterpolatedText, Label, Natural, Scheme, URL, V, FilePath
 };
 
 use crate::error::{DecodeError, EncodeError};
@@ -280,7 +281,7 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result<DecodedExpr, DecodeError> {
                                 "import/remote/query".to_owned(),
                             ))?,
                         };
-                        let path = rest
+                        let file_path = rest
                             .map(|s| match s.as_string() {
                                 Some(s) => Ok(s.clone()),
                                 None => Err(DecodeError::WrongFormatError(
@@ -288,6 +289,7 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result<DecodedExpr, DecodeError> {
                                 )),
                             })
                             .collect::<Result<_, _>>()?;
+                        let path = FilePath { file_path };
                         ImportLocation::Remote(URL {
                             scheme,
                             authority,
@@ -306,7 +308,7 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result<DecodedExpr, DecodeError> {
                                 "import/local/prefix".to_owned(),
                             ))?,
                         };
-                        let path = rest
+                        let file_path = rest
                             .map(|s| match s.as_string() {
                                 Some(s) => Ok(s.clone()),
                                 None => Err(DecodeError::WrongFormatError(
@@ -314,6 +316,7 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result<DecodedExpr, DecodeError> {
                                 )),
                             })
                             .collect::<Result<_, _>>()?;
+                        let path = FilePath { file_path };
                         ImportLocation::Local(prefix, path)
                     }
                     6 => {
@@ -580,8 +583,8 @@ where
     use serde::ser::SerializeSeq;
 
     let count = 4 + match &import.location {
-        ImportLocation::Remote(url) => 3 + url.path.len(),
-        ImportLocation::Local(_, path) => path.len(),
+        ImportLocation::Remote(url) => 3 + url.path.file_path.len(),
+        ImportLocation::Local(_, path) => path.file_path.len(),
         ImportLocation::Env(_) => 1,
         ImportLocation::Missing => 0,
     };
@@ -631,8 +634,8 @@ where
                 }
             };
             ser_seq.serialize_element(&url.authority)?;
-            for p in &url.path {
-                ser_seq.serialize_element(p)?;
+            for p in url.path.file_path.iter() {
+                ser_seq.serialize_element(&p)?;
             }
             match &url.query {
                 None => ser_seq.serialize_element(&Null)?,
@@ -640,8 +643,8 @@ where
             };
         }
         ImportLocation::Local(_, path) => {
-            for p in path {
-                ser_seq.serialize_element(p)?;
+            for p in path.file_path.iter() {
+                ser_seq.serialize_element(&p)?;
             }
         }
         ImportLocation::Env(env) => {
diff --git a/dhall/src/phase/resolve.rs b/dhall/src/phase/resolve.rs
index 32e90c8..cccc7a7 100644
--- a/dhall/src/phase/resolve.rs
+++ b/dhall/src/phase/resolve.rs
@@ -3,6 +3,7 @@ use std::path::{Path, PathBuf};
 
 use crate::error::{Error, ImportError};
 use crate::phase::{Normalized, NormalizedExpr, Parsed, Resolved};
+use dhall_syntax::{FilePath, ImportLocation, URL};
 
 type Import = dhall_syntax::Import<NormalizedExpr>;
 
@@ -30,14 +31,14 @@ fn resolve_import(
     };
     match &import.location {
         Local(prefix, path) => {
-            let path: PathBuf = path.iter().cloned().collect();
-            let path = match prefix {
+            let path_buf: PathBuf = path.file_path.iter().collect();
+            let path_buf = match prefix {
                 // TODO: fail gracefully
-                Parent => cwd.parent().unwrap().join(path),
-                Here => cwd.join(path),
+                Parent => cwd.parent().unwrap().join(path_buf),
+                Here => cwd.join(path_buf),
                 _ => unimplemented!("{:?}", import),
             };
-            Ok(load_import(&path, import_cache, import_stack).map_err(|e| {
+            Ok(load_import(&path_buf, import_cache, import_stack).map_err(|e| {
                 ImportError::Recursive(import.clone(), Box::new(e))
             })?)
         }
@@ -107,6 +108,75 @@ pub(crate) fn skip_resolve_expr(
     Ok(Resolved(expr))
 }
 
+pub trait Canonicalize {
+    fn canonicalize(&self) -> Self;
+}
+
+impl Canonicalize for FilePath {
+    fn canonicalize(&self) -> FilePath {
+        let mut file_path = Vec::new();
+        let mut file_path_components = self.file_path.clone().into_iter();
+
+        loop {
+           let component = file_path_components.next();
+           match component.as_ref() {
+               // ───────────────────
+               // canonicalize(ε) = ε
+               None => break,
+
+               // canonicalize(directory₀) = directory₁
+               // ───────────────────────────────────────
+               // canonicalize(directory₀/.) = directory₁
+               Some(c) if c == "." => continue,
+
+               Some(c) if c == ".." => match file_path_components.next() {
+                   // canonicalize(directory₀) = ε
+                   // ────────────────────────────
+                   // canonicalize(directory₀/..) = /..
+                   None => file_path.push("..".to_string()),
+
+                   // canonicalize(directory₀) = directory₁/..
+                   // ──────────────────────────────────────────────
+                   // canonicalize(directory₀/..) = directory₁/../..
+                   Some(ref c) if c == ".." => {
+                       file_path.push("..".to_string());
+                       file_path.push("..".to_string());
+                   },
+
+                   // canonicalize(directory₀) = directory₁/component
+                   // ───────────────────────────────────────────────  ; If "component" is not
+                   // canonicalize(directory₀/..) = directory₁         ; ".."
+                   Some(_) => continue,
+               },
+
+               // canonicalize(directory₀) = directory₁
+               // ─────────────────────────────────────────────────────────  ; If no other
+               // canonicalize(directory₀/component) = directory₁/component  ; rule matches
+               Some(c) => file_path.push(c.clone()),
+           }
+        }
+
+        FilePath { file_path }
+    }
+}
+
+impl<SE: Copy> Canonicalize for ImportLocation<SE>  {
+    fn canonicalize(&self) -> ImportLocation<SE> {
+        match self {
+            ImportLocation::Local(prefix, file) => ImportLocation::Local(*prefix, file.canonicalize()),
+            ImportLocation::Remote(url) => ImportLocation::Remote(URL {
+                    scheme: url.scheme,
+                    authority: url.authority.clone(),
+                    path: url.path.canonicalize(),
+                    query: url.query.clone(),
+                    headers: url.headers.clone(),
+            }),
+            ImportLocation::Env(name) => ImportLocation::Env(name.to_string()),
+            ImportLocation::Missing => ImportLocation::Missing,
+        }
+    }
+}
+
 #[cfg(test)]
 #[rustfmt::skip]
 mod spec_tests {
diff --git a/dhall_syntax/src/core/import.rs b/dhall_syntax/src/core/import.rs
index 43597df..da3e99b 100644
--- a/dhall_syntax/src/core/import.rs
+++ b/dhall_syntax/src/core/import.rs
@@ -11,10 +11,15 @@ pub enum FilePrefix {
     Home,
 }
 
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub struct FilePath {
+    pub file_path: Vec<String>,
+}
+
 /// The location of import (i.e. local vs. remote vs. environment)
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub enum ImportLocation<SubExpr> {
-    Local(FilePrefix, Vec<String>),
+    Local(FilePrefix, FilePath),
     Remote(URL<SubExpr>),
     Env(String),
     Missing,
@@ -24,7 +29,7 @@ pub enum ImportLocation<SubExpr> {
 pub struct URL<SubExpr> {
     pub scheme: Scheme,
     pub authority: String,
-    pub path: Vec<String>,
+    pub path: FilePath,
     pub query: Option<String>,
     pub headers: Option<SubExpr>,
 }
diff --git a/dhall_syntax/src/parser.rs b/dhall_syntax/src/parser.rs
index 71fab0f..f2dea53 100644
--- a/dhall_syntax/src/parser.rs
+++ b/dhall_syntax/src/parser.rs
@@ -429,10 +429,10 @@ impl DhallParser {
             })
             .collect())
     }
-    fn path(input: ParseInput) -> ParseResult<Vec<String>> {
+    fn path(input: ParseInput) -> ParseResult<FilePath> {
         Ok(match_nodes!(input.into_children();
             [path_component(components)..] => {
-                components.collect()
+                FilePath { file_path: components.collect() }
             }
         ))
     }
@@ -449,19 +449,19 @@ impl DhallParser {
     #[alias(local_path)]
     fn parent_path(
         input: ParseInput,
-    ) -> ParseResult<(FilePrefix, Vec<String>)> {
+    ) -> ParseResult<(FilePrefix, FilePath)> {
         Ok(match_nodes!(input.into_children();
             [path(p)] => (FilePrefix::Parent, p)
         ))
     }
     #[alias(local_path)]
-    fn here_path(input: ParseInput) -> ParseResult<(FilePrefix, Vec<String>)> {
+    fn here_path(input: ParseInput) -> ParseResult<(FilePrefix, FilePath)> {
         Ok(match_nodes!(input.into_children();
             [path(p)] => (FilePrefix::Here, p)
         ))
     }
     #[alias(local_path)]
-    fn home_path(input: ParseInput) -> ParseResult<(FilePrefix, Vec<String>)> {
+    fn home_path(input: ParseInput) -> ParseResult<(FilePrefix, FilePath)> {
         Ok(match_nodes!(input.into_children();
             [path(p)] => (FilePrefix::Home, p)
         ))
@@ -469,7 +469,7 @@ impl DhallParser {
     #[alias(local_path)]
     fn absolute_path(
         input: ParseInput,
-    ) -> ParseResult<(FilePrefix, Vec<String>)> {
+    ) -> ParseResult<(FilePrefix, FilePath)> {
         Ok(match_nodes!(input.into_children();
             [path(p)] => (FilePrefix::Absolute, p)
         ))
diff --git a/dhall_syntax/src/printer.rs b/dhall_syntax/src/printer.rs
index f3dc648..1e3b7f2 100644
--- a/dhall_syntax/src/printer.rs
+++ b/dhall_syntax/src/printer.rs
@@ -378,12 +378,12 @@ impl<SubExpr: Display> Display for Import<SubExpr> {
                 };
                 write!(f, "{}/", prefix)?;
                 let path: String =
-                    path.iter().map(|c| quote_if_needed(&*c)).join("/");
+                    path.file_path.iter().map(|c| quote_if_needed(&*c)).join("/");
                 f.write_str(&path)?;
             }
             Remote(url) => {
                 write!(f, "{}://{}/", url.scheme, url.authority,)?;
-                let path: String = url.path.iter().join("/");
+                let path: String = url.path.file_path.iter().join("/");
                 f.write_str(&path)?;
                 if let Some(q) = &url.query {
                     write!(f, "?{}", q)?