Merge remote-tracking branch 'origin/master' into fintan/canonicalize

1 files changed, 117 insertions, 174 deletions

diff --git a/dhall_syntax/src/core/expr.rs b/dhall_syntax/src/core/expr.rs
index 6522cb1..51b6c47 100644
--- a/dhall_syntax/src/core/expr.rs
+++ b/dhall_syntax/src/core/expr.rs
@@ -8,14 +8,34 @@ pub type Integer = isize;
 pub type Natural = usize;
 pub type Double = NaiveDouble;
 
-/// An empty type
-#[derive(Debug, Copy, Clone, PartialEq, Eq)]
-pub enum X {}
-
-pub fn trivial_result<T>(x: Result<T, X>) -> T {
+pub fn trivial_result<T>(x: Result<T, !>) -> T {
     match x {
         Ok(x) => x,
-        Err(e) => match e {},
+        Err(e) => e,
+    }
+}
+
+/// A location in the source text
+#[derive(Debug, Clone)]
+pub struct Span {
+    input: Rc<str>,
+    /// # Safety
+    ///
+    /// Must be a valid character boundary index into `input`.
+    start: usize,
+    /// # Safety
+    ///
+    /// Must be a valid character boundary index into `input`.
+    end: usize,
+}
+
+impl Span {
+    pub(crate) fn make(input: Rc<str>, sp: pest::Span) -> Self {
+        Span {
+            input,
+            start: sp.start(),
+            end: sp.end(),
+        }
     }
 }
 
@@ -31,6 +51,15 @@ impl PartialEq for NaiveDouble {
 
 impl Eq for NaiveDouble {}
 
+impl std::hash::Hash for NaiveDouble {
+    fn hash<H>(&self, state: &mut H)
+    where
+        H: std::hash::Hasher,
+    {
+        self.0.to_bits().hash(state)
+    }
+}
+
 impl From<f64> for NaiveDouble {
     fn from(x: f64) -> Self {
         NaiveDouble(x)
@@ -44,7 +73,7 @@ impl From<NaiveDouble> for f64 {
 }
 
 /// Constants for a pure type system
-#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub enum Const {
     Type,
     Kind,
@@ -56,7 +85,7 @@ pub enum Const {
 /// The `Label` field is the variable's name (i.e. \"`x`\").
 /// The `Int` field is a DeBruijn index.
 /// See dhall-lang/standard/semantics.md for details
-#[derive(Debug, Clone, PartialEq, Eq)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct V<Label>(pub Label, pub usize);
 
 // This is only for the specific `Label` type, not generic
@@ -73,7 +102,7 @@ impl<'a> From<&'a Label> for V<Label> {
 
 // Definition order must match precedence order for
 // pretty-printing to work correctly
-#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub enum BinOp {
     /// `x ? y`
     ImportAlt,
@@ -104,7 +133,7 @@ pub enum BinOp {
 }
 
 /// Built-ins
-#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub enum Builtin {
     Bool,
     Natural,
@@ -137,29 +166,34 @@ pub enum Builtin {
     TextShow,
 }
 
-pub type ParsedExpr = SubExpr<X, Import>;
-pub type ResolvedExpr = SubExpr<X, X>;
-pub type DhallExpr = ResolvedExpr;
+// Each node carries an annotation.
+#[derive(Debug, Clone)]
+pub struct Expr<Embed>(Box<(RawExpr<Embed>, Option<Span>)>);
 
-// Each node carries an annotation. In practice it's either X (no annotation) or a Span.
-#[derive(Debug)]
-pub struct SubExpr<Note, Embed>(Rc<(Expr<Note, Embed>, Option<Note>)>);
+pub type RawExpr<Embed> = ExprF<Expr<Embed>, Embed>;
 
-impl<Note, Embed: PartialEq> std::cmp::PartialEq for SubExpr<Note, Embed> {
+impl<Embed: PartialEq> std::cmp::PartialEq for Expr<Embed> {
     fn eq(&self, other: &Self) -> bool {
         self.0.as_ref().0 == other.0.as_ref().0
     }
 }
 
-impl<Note, Embed: Eq> std::cmp::Eq for SubExpr<Note, Embed> {}
+impl<Embed: Eq> std::cmp::Eq for Expr<Embed> {}
 
-pub type Expr<Note, Embed> = ExprF<SubExpr<Note, Embed>, Embed>;
+impl<Embed: std::hash::Hash> std::hash::Hash for Expr<Embed> {
+    fn hash<H>(&self, state: &mut H)
+    where
+        H: std::hash::Hasher,
+    {
+        (self.0).0.hash(state)
+    }
+}
 
 /// Syntax tree for expressions
 // Having the recursion out of the enum definition enables writing
 // much more generic code and improves pattern-matching behind
 // smart pointers.
-#[derive(Debug, Clone, PartialEq, Eq)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub enum ExprF<SubExpr, Embed> {
     Const(Const),
     ///  `x`
@@ -209,11 +243,15 @@ pub enum ExprF<SubExpr, Embed> {
     UnionType(DupTreeMap<Label, Option<SubExpr>>),
     ///  `merge x y : t`
     Merge(SubExpr, SubExpr, Option<SubExpr>),
+    ///  `toMap x : t`
+    ToMap(SubExpr, Option<SubExpr>),
     ///  `e.x`
     Field(SubExpr, Label),
     ///  `e.{ x, y, z }`
     Projection(SubExpr, DupTreeSet<Label>),
-    /// Embeds an import or the result of resolving the import
+    /// `./some/path`
+    Import(Import<SubExpr>),
+    /// Embeds the result of resolving an import
     Embed(Embed),
 }
 
@@ -225,229 +263,134 @@ impl<SE, E> ExprF<SE, E> {
         v.visit(self)
     }
 
-    pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, E2, Err>(
+    pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, Err>(
         &'a self,
         visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
         visit_under_binder: impl FnOnce(&'a Label, &'a SE) -> Result<SE2, Err>,
-        visit_embed: impl FnOnce(&'a E) -> Result<E2, Err>,
-    ) -> Result<ExprF<SE2, E2>, Err> {
+    ) -> Result<ExprF<SE2, E>, Err>
+    where
+        E: Clone,
+    {
         self.visit(visitor::TraverseRefWithBindersVisitor {
             visit_subexpr,
             visit_under_binder,
-            visit_embed,
         })
     }
 
-    fn traverse_ref<'a, SE2, E2, Err>(
+    fn traverse_ref<'a, SE2, Err>(
         &'a self,
         visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
-        visit_embed: impl FnOnce(&'a E) -> Result<E2, Err>,
-    ) -> Result<ExprF<SE2, E2>, Err> {
-        self.visit(visitor::TraverseRefVisitor {
-            visit_subexpr,
-            visit_embed,
-        })
+    ) -> Result<ExprF<SE2, E>, Err>
+    where
+        E: Clone,
+    {
+        self.visit(visitor::TraverseRefVisitor { visit_subexpr })
     }
 
-    pub fn map_ref_with_special_handling_of_binders<'a, SE2, E2>(
+    pub fn map_ref_with_special_handling_of_binders<'a, SE2>(
         &'a self,
         mut map_subexpr: impl FnMut(&'a SE) -> SE2,
         mut map_under_binder: impl FnMut(&'a Label, &'a SE) -> SE2,
-        map_embed: impl FnOnce(&'a E) -> E2,
-    ) -> ExprF<SE2, E2> {
+    ) -> ExprF<SE2, E>
+    where
+        E: Clone,
+    {
         trivial_result(self.traverse_ref_with_special_handling_of_binders(
             |x| Ok(map_subexpr(x)),
             |l, x| Ok(map_under_binder(l, x)),
-            |x| Ok(map_embed(x)),
         ))
     }
 
-    pub fn map_ref<'a, SE2, E2>(
+    pub fn map_ref<'a, SE2>(
         &'a self,
         mut map_subexpr: impl FnMut(&'a SE) -> SE2,
-        map_embed: impl FnOnce(&'a E) -> E2,
-    ) -> ExprF<SE2, E2> {
-        trivial_result(
-            self.traverse_ref(|x| Ok(map_subexpr(x)), |x| Ok(map_embed(x))),
-        )
-    }
-
-    pub fn traverse_ref_simple<'a, SE2, Err>(
-        &'a self,
-        visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
-    ) -> Result<ExprF<SE2, E>, Err>
-    where
-        E: Clone,
-    {
-        self.traverse_ref(visit_subexpr, |x| Ok(E::clone(x)))
-    }
-
-    pub fn map_ref_simple<'a, SE2>(
-        &'a self,
-        map_subexpr: impl Fn(&'a SE) -> SE2,
     ) -> ExprF<SE2, E>
     where
         E: Clone,
     {
-        self.map_ref(map_subexpr, E::clone)
+        trivial_result(self.traverse_ref(|x| Ok(map_subexpr(x))))
     }
 }
 
-impl<N, E> Expr<N, E> {
-    fn traverse_embed<E2, Err>(
-        &self,
-        visit_embed: impl FnMut(&E) -> Result<E2, Err>,
-    ) -> Result<Expr<N, E2>, Err>
-    where
-        N: Clone,
-    {
-        self.visit(&mut visitor::TraverseEmbedVisitor(visit_embed))
-    }
-
-    fn map_embed<E2>(&self, mut map_embed: impl FnMut(&E) -> E2) -> Expr<N, E2>
-    where
-        N: Clone,
-    {
-        trivial_result(self.traverse_embed(|x| Ok(map_embed(x))))
-    }
-
+impl<E> RawExpr<E> {
     pub fn traverse_resolve<E2, Err>(
         &self,
-        visit_embed: impl FnMut(&E) -> Result<E2, Err>,
-    ) -> Result<Expr<N, E2>, Err>
-    where
-        N: Clone,
-    {
+        visit_import: impl FnMut(&Import<Expr<E2>>) -> Result<E2, Err>,
+    ) -> Result<RawExpr<E2>, Err> {
         self.traverse_resolve_with_visitor(&mut visitor::ResolveVisitor(
-            visit_embed,
+            visit_import,
         ))
     }
 
     pub(crate) fn traverse_resolve_with_visitor<E2, Err, F1>(
         &self,
         visitor: &mut visitor::ResolveVisitor<F1>,
-    ) -> Result<Expr<N, E2>, Err>
+    ) -> Result<RawExpr<E2>, Err>
     where
-        N: Clone,
-        F1: FnMut(&E) -> Result<E2, Err>,
+        F1: FnMut(&Import<Expr<E2>>) -> Result<E2, Err>,
     {
         match self {
             ExprF::BinOp(BinOp::ImportAlt, l, r) => l
                 .as_ref()
                 .traverse_resolve_with_visitor(visitor)
-                .or(r.as_ref().traverse_resolve_with_visitor(visitor)),
-            _ => self.visit(visitor),
+                .or_else(|_| r.as_ref().traverse_resolve_with_visitor(visitor)),
+            _ => {
+                let e = self.visit(&mut *visitor)?;
+                Ok(match &e {
+                    ExprF::Import(import) => ExprF::Embed((visitor.0)(import)?),
+                    _ => e,
+                })
+            }
         }
     }
 }
 
-impl Expr<X, X> {
-    pub fn absurd<N, E>(&self) -> Expr<N, E> {
-        self.visit(&mut visitor::AbsurdVisitor)
-    }
-}
-
-impl<E: Clone> Expr<X, E> {
-    pub fn note_absurd<N>(&self) -> Expr<N, E> {
-        self.visit(&mut visitor::NoteAbsurdVisitor)
-    }
-}
-
-impl<N, E> SubExpr<N, E> {
-    pub fn as_ref(&self) -> &Expr<N, E> {
+impl<E> Expr<E> {
+    pub fn as_ref(&self) -> &RawExpr<E> {
         &self.0.as_ref().0
     }
 
-    pub fn new(x: Expr<N, E>, n: N) -> Self {
-        SubExpr(Rc::new((x, Some(n))))
+    pub fn new(x: RawExpr<E>, n: Span) -> Self {
+        Expr(Box::new((x, Some(n))))
     }
 
-    pub fn from_expr_no_note(x: Expr<N, E>) -> Self {
-        SubExpr(Rc::new((x, None)))
+    pub fn from_expr_no_span(x: RawExpr<E>) -> Self {
+        Expr(Box::new((x, None)))
     }
 
     pub fn from_builtin(b: Builtin) -> Self {
-        SubExpr::from_expr_no_note(ExprF::Builtin(b))
+        Expr::from_expr_no_span(ExprF::Builtin(b))
     }
 
-    pub fn rewrap<E2>(&self, x: Expr<N, E2>) -> SubExpr<N, E2>
-    where
-        N: Clone,
-    {
-        SubExpr(Rc::new((x, (self.0).1.clone())))
-    }
-
-    pub fn traverse_embed<E2, Err>(
-        &self,
-        visit_embed: impl FnMut(&E) -> Result<E2, Err>,
-    ) -> Result<SubExpr<N, E2>, Err>
-    where
-        N: Clone,
-    {
-        Ok(self.rewrap(self.as_ref().traverse_embed(visit_embed)?))
-    }
-
-    pub fn map_embed<E2>(
-        &self,
-        map_embed: impl FnMut(&E) -> E2,
-    ) -> SubExpr<N, E2>
-    where
-        N: Clone,
-    {
-        self.rewrap(self.as_ref().map_embed(map_embed))
-    }
-
-    pub fn map_subexprs_with_special_handling_of_binders<'a>(
-        &'a self,
-        map_expr: impl FnMut(&'a Self) -> Self,
-        map_under_binder: impl FnMut(&'a Label, &'a Self) -> Self,
-    ) -> Self
-    where
-        N: Clone,
-    {
-        match self.as_ref() {
-            ExprF::Embed(_) => SubExpr::clone(self),
-            // This calls ExprF::map_ref
-            e => self.rewrap(e.map_ref_with_special_handling_of_binders(
-                map_expr,
-                map_under_binder,
-                |_| unreachable!(),
-            )),
-        }
+    pub fn rewrap<E2>(&self, x: RawExpr<E2>) -> Expr<E2> {
+        Expr(Box::new((x, (self.0).1.clone())))
     }
+}
 
+impl<E> Expr<E> {
     pub fn traverse_resolve<E2, Err>(
         &self,
-        visit_embed: impl FnMut(&E) -> Result<E2, Err>,
-    ) -> Result<SubExpr<N, E2>, Err>
-    where
-        N: Clone,
-    {
-        Ok(self.rewrap(self.as_ref().traverse_resolve(visit_embed)?))
-    }
-}
-
-impl SubExpr<X, X> {
-    pub fn absurd<N: Clone, T>(&self) -> SubExpr<N, T> {
-        SubExpr::from_expr_no_note(self.as_ref().absurd())
+        visit_import: impl FnMut(&Import<Expr<E2>>) -> Result<E2, Err>,
+    ) -> Result<Expr<E2>, Err> {
+        Ok(self.rewrap(self.as_ref().traverse_resolve(visit_import)?))
     }
 }
 
-impl<E: Clone> SubExpr<X, E> {
-    pub fn note_absurd<N>(&self) -> SubExpr<N, E> {
-        SubExpr::from_expr_no_note(self.as_ref().note_absurd())
-    }
+// Should probably rename this
+pub fn rc<E>(x: RawExpr<E>) -> Expr<E> {
+    Expr::from_expr_no_span(x)
 }
 
-impl<N, E> Clone for SubExpr<N, E> {
-    fn clone(&self) -> Self {
-        SubExpr(Rc::clone(&self.0))
-    }
+pub(crate) fn spanned(
+    span: Span,
+    x: crate::parser::ParsedRawExpr,
+) -> crate::parser::ParsedExpr {
+    Expr::new(x, span)
 }
-
-// Should probably rename this
-pub fn rc<E>(x: Expr<X, E>) -> SubExpr<X, E> {
-    SubExpr::from_expr_no_note(x)
+pub(crate) fn unspanned(
+    x: crate::parser::ParsedRawExpr,
+) -> crate::parser::ParsedExpr {
+    Expr::from_expr_no_span(x)
 }
 
 /// Add an isize to an usize