Merge pull request #159 from Nadrieril/operations

Factor out operations

4 files changed, 57 insertions, 460 deletions

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 9e935dc..9d216a7 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -1,8 +1,9 @@
 use std::collections::BTreeMap;
 
+use crate::builtins::Builtin;
 use crate::error::Error;
+use crate::operations::OpKind;
 use crate::semantics::Universe;
-use crate::syntax::map::{DupTreeMap, DupTreeSet};
 use crate::syntax::visitor;
 use crate::syntax::*;
 
@@ -36,74 +37,6 @@ impl Const {
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct V(pub Label, pub usize);
 
-// Definition order must match precedence order for
-// pretty-printing to work correctly
-#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
-pub enum BinOp {
-    /// `x ? y`
-    ImportAlt,
-    /// `x || y`
-    BoolOr,
-    /// `x + y`
-    NaturalPlus,
-    /// `x ++ y`
-    TextAppend,
-    /// `x # y`
-    ListAppend,
-    /// `x && y`
-    BoolAnd,
-    /// `x ∧ y`
-    RecursiveRecordMerge,
-    /// `x ⫽ y`
-    RightBiasedRecordMerge,
-    /// `x ⩓ y`
-    RecursiveRecordTypeMerge,
-    /// `x * y`
-    NaturalTimes,
-    /// `x == y`
-    BoolEQ,
-    /// `x != y`
-    BoolNE,
-    /// x === y
-    Equivalence,
-}
-
-/// Built-ins
-#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
-pub enum Builtin {
-    Bool,
-    Natural,
-    Integer,
-    Double,
-    Text,
-    List,
-    Optional,
-    OptionalNone,
-    NaturalBuild,
-    NaturalFold,
-    NaturalIsZero,
-    NaturalEven,
-    NaturalOdd,
-    NaturalToInteger,
-    NaturalShow,
-    NaturalSubtract,
-    IntegerToDouble,
-    IntegerShow,
-    IntegerNegate,
-    IntegerClamp,
-    DoubleShow,
-    ListBuild,
-    ListFold,
-    ListLength,
-    ListHead,
-    ListLast,
-    ListIndexed,
-    ListReverse,
-    OptionalFold,
-    OptionalBuild,
-    TextShow,
-}
-
 // Each node carries an annotation.
 #[derive(Debug, Clone)]
 pub struct Expr {
@@ -132,57 +65,44 @@ pub enum NumKind {
 // smart pointers.
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub enum ExprKind<SubExpr> {
+    /// `Type`, `Kind` and `Sort`
     Const(Const),
+    /// Numbers and booleans
     Num(NumKind),
-    ///  `x`
-    ///  `x@n`
-    Var(V),
-    ///  `λ(x : A) -> b`
-    Lam(Label, SubExpr, SubExpr),
-    ///  `A -> B`
-    ///  `∀(x : A) -> B`
-    Pi(Label, SubExpr, SubExpr),
-    ///  `f a`
-    App(SubExpr, SubExpr),
-    ///  `let x     = r in e`
-    ///  `let x : t = r in e`
-    Let(Label, Option<SubExpr>, SubExpr, SubExpr),
-    ///  `x : t`
-    Annot(SubExpr, SubExpr),
-    ///  `assert : t`
-    Assert(SubExpr),
-    /// Built-in values
+    /// Built-in functions and types
     Builtin(Builtin),
-    // Binary operations
-    BinOp(BinOp, SubExpr, SubExpr),
-    ///  `if x then y else z`
-    BoolIf(SubExpr, SubExpr, SubExpr),
     ///  `"Some ${interpolated} text"`
     TextLit(InterpolatedText<SubExpr>),
+    ///  `Some e`
+    SomeLit(SubExpr),
     ///  `[] : t`
     EmptyListLit(SubExpr),
     ///  `[x, y, z]`
     NEListLit(Vec<SubExpr>),
-    ///  `Some e`
-    SomeLit(SubExpr),
     ///  `{ k1 : t1, k2 : t1 }`
-    RecordType(DupTreeMap<Label, SubExpr>),
+    RecordType(BTreeMap<Label, SubExpr>),
     ///  `{ k1 = v1, k2 = v2 }`
     RecordLit(BTreeMap<Label, SubExpr>),
     ///  `< k1 : t1, k2 >`
-    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>),
-    ///  `e.(t)`
-    ProjectionByExpr(SubExpr, SubExpr),
-    ///  `x::y`
-    Completion(SubExpr, SubExpr),
+    UnionType(BTreeMap<Label, Option<SubExpr>>),
+
+    ///  `x`, `x@n`
+    Var(V),
+    ///  `λ(x : A) -> b`
+    Lam(Label, SubExpr, SubExpr),
+    ///  `A -> B`, `∀(x : A) -> B`
+    Pi(Label, SubExpr, SubExpr),
+    ///  `let x : t = r in e`
+    Let(Label, Option<SubExpr>, SubExpr, SubExpr),
+
+    /// Operations
+    Op(OpKind<SubExpr>),
+
+    ///  `x : t`
+    Annot(SubExpr, SubExpr),
+    ///  `assert : t`
+    Assert(SubExpr),
+
     /// `./some/path`
     Import(Import<SubExpr>),
 }
diff --git a/dhall/src/syntax/ast/map.rs b/dhall/src/syntax/ast/map.rs
deleted file mode 100644
index 7a88204..0000000
--- a/dhall/src/syntax/ast/map.rs
+++ /dev/null
@@ -1,282 +0,0 @@
-/// A sorted map that allows multiple values for each key.
-pub use dup_tree_map::DupTreeMap;
-pub use dup_tree_set::DupTreeSet;
-
-mod known_size_iter {
-    pub struct KnownSizeIterator<I> {
-        pub iter: I,
-        pub size: usize,
-    }
-
-    impl<I: Iterator> Iterator for KnownSizeIterator<I> {
-        type Item = I::Item;
-
-        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<I: Iterator> iter::TrustedLen for KnownSizeIterator<I> {}
-}
-
-mod tuple {
-    mod sealed {
-        pub trait Sealed {}
-    }
-    pub trait Tuple: sealed::Sealed {
-        type First;
-        type Second;
-    }
-    impl<A, B> sealed::Sealed for (A, B) {}
-    impl<A, B> Tuple for (A, B) {
-        type First = A;
-        type Second = B;
-    }
-}
-
-mod dup_tree_map {
-    use super::known_size_iter::KnownSizeIterator;
-    use super::tuple::Tuple;
-    use smallvec::SmallVec;
-    use std::collections::BTreeMap;
-    use std::iter;
-
-    type OneOrMore<V> = SmallVec<[V; 1]>;
-    type DupTreeMapInternal<K, V> = BTreeMap<K, OneOrMore<V>>;
-
-    #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
-    pub struct DupTreeMap<K, V> {
-        map: DupTreeMapInternal<K, V>,
-        size: usize,
-    }
-
-    // Generic types and functions to construct the iterators for this struct.
-    type ZipRepeatIter<T> = iter::Zip<
-        iter::Repeat<<T as Tuple>::First>,
-        <<T as Tuple>::Second as IntoIterator>::IntoIter,
-    >;
-    type DupTreeMapIter<M> = KnownSizeIterator<
-        iter::FlatMap<
-            <M as IntoIterator>::IntoIter,
-            ZipRepeatIter<<M as IntoIterator>::Item>,
-            fn(
-                <M as IntoIterator>::Item,
-            ) -> ZipRepeatIter<<M as IntoIterator>::Item>,
-        >,
-    >;
-
-    fn zip_repeat<K, I>((k, iter): (K, I)) -> ZipRepeatIter<(K, I)>
-    where
-        K: Clone,
-        I: IntoIterator,
-    {
-        iter::repeat(k).zip(iter.into_iter())
-    }
-
-    fn make_map_iter<M, K, I>(map: M, size: usize) -> DupTreeMapIter<M>
-    where
-        M: IntoIterator<Item = (K, I)>,
-        K: Clone,
-        I: IntoIterator,
-    {
-        KnownSizeIterator {
-            iter: map.into_iter().flat_map(zip_repeat),
-            size,
-        }
-    }
-
-    pub type IterMut<'a, K, V> =
-        DupTreeMapIter<&'a mut DupTreeMapInternal<K, V>>;
-    pub type Iter<'a, K, V> = DupTreeMapIter<&'a DupTreeMapInternal<K, V>>;
-    pub type IntoIter<K, V> = DupTreeMapIter<DupTreeMapInternal<K, V>>;
-
-    impl<K: Ord, V> DupTreeMap<K, V> {
-        pub fn new() -> Self {
-            DupTreeMap {
-                map: BTreeMap::new(),
-                size: 0,
-            }
-        }
-
-        pub fn insert(&mut self, key: K, value: V) {
-            self.map.entry(key).or_default().push(value);
-            self.size += 1;
-        }
-
-        pub fn len(&self) -> usize {
-            self.size
-        }
-        pub fn is_empty(&self) -> bool {
-            self.size == 0
-        }
-
-        pub fn iter(&self) -> Iter<'_, K, V> {
-            make_map_iter(&self.map, self.size)
-        }
-
-        pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
-            make_map_iter(&mut self.map, self.size)
-        }
-    }
-
-    impl<K, V> Default for DupTreeMap<K, V>
-    where
-        K: Ord,
-    {
-        fn default() -> Self {
-            Self::new()
-        }
-    }
-
-    impl<K, V> IntoIterator for DupTreeMap<K, V>
-    where
-        K: Ord + Clone,
-    {
-        type Item = (K, V);
-        type IntoIter = IntoIter<K, V>;
-
-        fn into_iter(self) -> Self::IntoIter {
-            make_map_iter(self.map, self.size)
-        }
-    }
-
-    impl<'a, K, V> IntoIterator for &'a DupTreeMap<K, V>
-    where
-        K: Ord + 'a,
-        V: 'a,
-    {
-        type Item = (&'a K, &'a V);
-        type IntoIter = Iter<'a, K, V>;
-
-        fn into_iter(self) -> Self::IntoIter {
-            self.iter()
-        }
-    }
-
-    impl<'a, K, V> IntoIterator for &'a mut DupTreeMap<K, V>
-    where
-        K: Ord + 'a,
-        V: 'a,
-    {
-        type Item = (&'a K, &'a mut V);
-        type IntoIter = IterMut<'a, K, V>;
-
-        fn into_iter(self) -> Self::IntoIter {
-            self.iter_mut()
-        }
-    }
-
-    impl<K, V> iter::FromIterator<(K, V)> for DupTreeMap<K, V>
-    where
-        K: Ord,
-    {
-        fn from_iter<T>(iter: T) -> Self
-        where
-            T: IntoIterator<Item = (K, V)>,
-        {
-            let mut map = DupTreeMap::new();
-            for (k, v) in iter {
-                map.insert(k, v);
-            }
-            map
-        }
-    }
-}
-
-mod dup_tree_set {
-    use super::tuple::Tuple;
-    use super::DupTreeMap;
-    use std::iter;
-
-    #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
-    pub struct DupTreeSet<K> {
-        map: DupTreeMap<K, ()>,
-    }
-
-    type DupTreeSetIter<M> = iter::Map<
-        <M as IntoIterator>::IntoIter,
-        fn(
-            <M as IntoIterator>::Item,
-        ) -> <<M as IntoIterator>::Item as Tuple>::First,
-    >;
-
-    pub type Iter<'a, K> = DupTreeSetIter<&'a DupTreeMap<K, ()>>;
-    pub type IntoIter<K> = DupTreeSetIter<DupTreeMap<K, ()>>;
-
-    fn drop_second<A, B>((a, _): (A, B)) -> A {
-        a
-    }
-
-    impl<K: Ord> DupTreeSet<K> {
-        pub fn new() -> Self {
-            DupTreeSet {
-                map: DupTreeMap::new(),
-            }
-        }
-
-        pub fn len(&self) -> usize {
-            self.map.len()
-        }
-        pub fn is_empty(&self) -> bool {
-            self.map.is_empty()
-        }
-
-        pub fn iter(&self) -> Iter<'_, K> {
-            self.map.iter().map(drop_second)
-        }
-    }
-
-    impl<K> Default for DupTreeSet<K>
-    where
-        K: Ord,
-    {
-        fn default() -> Self {
-            Self::new()
-        }
-    }
-
-    impl<K> IntoIterator for DupTreeSet<K>
-    where
-        K: Ord + Clone,
-    {
-        type Item = K;
-        type IntoIter = IntoIter<K>;
-
-        fn into_iter(self) -> Self::IntoIter {
-            self.map.into_iter().map(drop_second)
-        }
-    }
-
-    impl<'a, K> IntoIterator for &'a DupTreeSet<K>
-    where
-        K: Ord + 'a,
-    {
-        type Item = &'a K;
-        type IntoIter = Iter<'a, K>;
-
-        fn into_iter(self) -> Self::IntoIter {
-            self.iter()
-        }
-    }
-
-    impl<K> iter::FromIterator<K> for DupTreeSet<K>
-    where
-        K: Ord,
-    {
-        fn from_iter<T>(iter: T) -> Self
-        where
-            T: IntoIterator<Item = K>,
-        {
-            let map = iter.into_iter().map(|k| (k, ())).collect();
-            DupTreeSet { map }
-        }
-    }
-}
diff --git a/dhall/src/syntax/ast/mod.rs b/dhall/src/syntax/ast/mod.rs
index 1950154..c341af7 100644
--- a/dhall/src/syntax/ast/mod.rs
+++ b/dhall/src/syntax/ast/mod.rs
@@ -8,5 +8,4 @@ mod span;
 pub use span::*;
 mod text;
 pub use text::*;
-pub mod map;
 pub mod visitor;
diff --git a/dhall/src/syntax/ast/visitor.rs b/dhall/src/syntax/ast/visitor.rs
index 0a0c5ef..7244d0a 100644
--- a/dhall/src/syntax/ast/visitor.rs
+++ b/dhall/src/syntax/ast/visitor.rs
@@ -1,22 +1,13 @@
+use itertools::Itertools;
 use std::iter::FromIterator;
 
 use crate::syntax::*;
 
-fn vec<'a, T, U, Err>(
-    x: &'a [T],
-    f: impl FnMut(&'a T) -> Result<U, Err>,
-) -> Result<Vec<U>, Err> {
-    x.iter().map(f).collect()
-}
-
 fn opt<'a, T, U, Err>(
     x: &'a Option<T>,
     f: impl FnOnce(&'a T) -> Result<U, Err>,
 ) -> Result<Option<U>, Err> {
-    Ok(match x {
-        Some(x) => Some(f(x)?),
-        None => None,
-    })
+    x.as_ref().map(f).transpose()
 }
 
 fn dupmap<'a, SE1, SE2, T, Err>(
@@ -30,27 +21,6 @@ where
     x.into_iter().map(|(k, x)| Ok((k.clone(), f(x)?))).collect()
 }
 
-fn optdupmap<'a, SE1, SE2, T, Err>(
-    x: impl IntoIterator<Item = (&'a Label, &'a Option<SE1>)>,
-    mut f: impl FnMut(&'a SE1) -> Result<SE2, Err>,
-) -> Result<T, Err>
-where
-    SE1: 'a,
-    T: FromIterator<(Label, Option<SE2>)>,
-{
-    x.into_iter()
-        .map(|(k, x)| {
-            Ok((
-                k.clone(),
-                match x {
-                    Some(x) => Some(f(x)?),
-                    None => None,
-                },
-            ))
-        })
-        .collect()
-}
-
 pub fn visit_ref<'a, F, SE1, SE2, Err>(
     input: &'a ExprKind<SE1>,
     mut f: F,
@@ -60,54 +30,44 @@ where
 {
     // Can't use closures because of borrowing rules
     macro_rules! expr {
+        () => {
+            |e| Ok(expr!(e))
+        };
         ($e:expr) => {
-            f(None, $e)
+            f(None, $e)?
         };
         ($l:expr, $e:expr) => {
-            f(Some($l), $e)
+            f(Some($l), $e)?
+        };
+    }
+    macro_rules! opt {
+        () => {
+            |e| Ok(opt!(e))
+        };
+        ($e:expr) => {
+            opt($e, |e| Ok(expr!(e)))?
         };
     }
 
     use crate::syntax::ExprKind::*;
     Ok(match input {
         Var(v) => Var(v.clone()),
-        Lam(l, t, e) => {
-            let t = expr!(t)?;
-            let e = expr!(l, e)?;
-            Lam(l.clone(), t, e)
-        }
-        Pi(l, t, e) => {
-            let t = expr!(t)?;
-            let e = expr!(l, e)?;
-            Pi(l.clone(), t, e)
-        }
-        Let(l, t, a, e) => {
-            let t = opt(t, &mut |e| expr!(e))?;
-            let a = expr!(a)?;
-            let e = expr!(l, e)?;
-            Let(l.clone(), t, a, e)
-        }
-        App(f, a) => App(expr!(f)?, expr!(a)?),
-        Annot(x, t) => Annot(expr!(x)?, expr!(t)?),
+        Lam(l, t, e) => Lam(l.clone(), expr!(t), expr!(l, e)),
+        Pi(l, t, e) => Pi(l.clone(), expr!(t), expr!(l, e)),
+        Let(l, t, a, e) => Let(l.clone(), opt!(t), expr!(a), expr!(l, e)),
         Const(k) => Const(*k),
-        Builtin(v) => Builtin(*v),
         Num(n) => Num(n.clone()),
-        TextLit(t) => TextLit(t.traverse_ref(|e| expr!(e))?),
-        BinOp(o, x, y) => BinOp(*o, expr!(x)?, expr!(y)?),
-        BoolIf(b, t, f) => BoolIf(expr!(b)?, expr!(t)?, expr!(f)?),
-        EmptyListLit(t) => EmptyListLit(expr!(t)?),
-        NEListLit(es) => NEListLit(vec(es, |e| expr!(e))?),
-        SomeLit(e) => SomeLit(expr!(e)?),
-        RecordType(kts) => RecordType(dupmap(kts, |e| expr!(e))?),
-        RecordLit(kvs) => RecordLit(dupmap(kvs, |e| expr!(e))?),
-        UnionType(kts) => UnionType(optdupmap(kts, |e| expr!(e))?),
-        Merge(x, y, t) => Merge(expr!(x)?, expr!(y)?, opt(t, |e| expr!(e))?),
-        ToMap(x, t) => ToMap(expr!(x)?, opt(t, |e| expr!(e))?),
-        Field(e, l) => Field(expr!(e)?, l.clone()),
-        Projection(e, ls) => Projection(expr!(e)?, ls.clone()),
-        ProjectionByExpr(e, x) => ProjectionByExpr(expr!(e)?, expr!(x)?),
-        Completion(e, x) => Completion(expr!(e)?, expr!(x)?),
-        Assert(e) => Assert(expr!(e)?),
-        Import(i) => Import(i.traverse_ref(|e| expr!(e))?),
+        Builtin(v) => Builtin(*v),
+        TextLit(t) => TextLit(t.traverse_ref(expr!())?),
+        SomeLit(e) => SomeLit(expr!(e)),
+        EmptyListLit(t) => EmptyListLit(expr!(t)),
+        NEListLit(es) => NEListLit(es.iter().map(expr!()).try_collect()?),
+        RecordType(kts) => RecordType(dupmap(kts, expr!())?),
+        RecordLit(kvs) => RecordLit(dupmap(kvs, expr!())?),
+        UnionType(kts) => UnionType(dupmap(kts, opt!())?),
+        Op(op) => Op(op.traverse_ref(expr!())?),
+        Annot(x, t) => Annot(expr!(x), expr!(t)),
+        Assert(e) => Assert(expr!(e)),
+        Import(i) => Import(i.traverse_ref(expr!())?),
     })
 }