Extract the core of parser macros into a separate crate

6 files changed, 252 insertions, 131 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 6e218fb..fa37a5e 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -82,6 +82,7 @@ name = "dhall_core"
 version = "0.1.0"
 dependencies = [
  "dhall_parser 0.1.0",
+ "iter_patterns 0.1.0",
  "itertools 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "pest 2.1.0 (git+https://github.com/pest-parser/pest)",
  "term-painter 0.2.4 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -144,6 +145,10 @@ version = "1.3.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "iter_patterns"
+version = "0.1.0"
+
+[[package]]
 name = "itertools"
 version = "0.8.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index 74388cb..c2c0fae 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -5,6 +5,9 @@ members = [
     "abnf_to_pest",
     "dhall",
     "dhall_parser",
+    "dhall_core",
+    "dhall_generator",
+    "iter_patterns",
 ]
 
 # # Parser is super slow when not optimized
diff --git a/dhall_core/Cargo.toml b/dhall_core/Cargo.toml
index 4010f4a..c3c417a 100644
--- a/dhall_core/Cargo.toml
+++ b/dhall_core/Cargo.toml
@@ -12,3 +12,4 @@ itertools = "0.8.0"
 term-painter = "0.2.3"
 pest = { git = "https://github.com/pest-parser/pest" }
 dhall_parser = { path = "../dhall_parser" }
+iter_patterns = { path = "../iter_patterns" }
diff --git a/dhall_core/src/parser.rs b/dhall_core/src/parser.rs
index 6f84abe..45930d4 100644
--- a/dhall_core/src/parser.rs
+++ b/dhall_core/src/parser.rs
@@ -71,102 +71,11 @@ fn debug_pair(pair: Pair<Rule>) -> String {
     s
 }
 
-/* Macro to pattern-match iterators.
- * Returns `Result<_, IterMatchError<_>>`.
- *
- * Example:
- * ```
- * let vec = vec![1, 2, 3];
- *
- * match_iter!(vec.into_iter(); (x, y?, z) => {
- *  // x: T
- *  // y: Option<T>
- *  // z: T
- * })
- *
- * // or
- * match_iter!(vec.into_iter(); (x, y, z*) => {
- *  // x, y: T
- *  // z: impl Iterator<T>
- * })
- * ```
- *
-*/
 #[derive(Debug)]
 enum IterMatchError<T> {
-    NotEnoughItems,
-    TooManyItems,
     NoMatchFound,
     Other(T), // Allow other macros to inject their own errors
 }
-macro_rules! match_iter {
-    // Everything else pattern
-    (@match 0, $iter:expr, $x:ident* $($rest:tt)*) => {
-        match_iter!(@match 2, $iter $($rest)*);
-        #[allow(unused_mut)]
-        let mut $x = $iter;
-    };
-    // Alias to use in macros
-    (@match 0, $iter:expr, $x:ident?? $($rest:tt)*) => {
-        match_iter!(@match 2, $iter $($rest)*);
-        #[allow(unused_mut)]
-        let mut $x = $iter;
-    };
-    // Optional pattern
-    (@match 0, $iter:expr, $x:ident? $($rest:tt)*) => {
-        match_iter!(@match 1, $iter $($rest)*);
-        #[allow(unused_mut)]
-        let mut $x = $iter.next();
-        if $iter.next().is_some() {
-            break Err(IterMatchError::TooManyItems);
-        }
-    };
-    // Normal pattern
-    (@match 0, $iter:expr, $x:ident $($rest:tt)*) => {
-        #[allow(unused_mut)]
-        let mut $x = match $iter.next() {
-            Some(x) => x,
-            None => break Err(IterMatchError::NotEnoughItems),
-        };
-        match_iter!(@match 0, $iter $($rest)*);
-    };
-    // Normal pattern after a variable length one: declare reversed and take from the end
-    (@match $w:expr, $iter:expr, $x:ident $($rest:tt)*) => {
-        match_iter!(@match $w, $iter $($rest)*);
-        #[allow(unused_mut)]
-        let mut $x = match $iter.next_back() {
-            Some(x) => x,
-            None => break Err(IterMatchError::NotEnoughItems),
-        };
-    };
-
-    // Check no elements remain
-    (@match 0, $iter:expr $(,)*) => {
-        if $iter.next().is_some() {
-            break Err(IterMatchError::TooManyItems);
-        }
-    };
-    (@match $_:expr, $iter:expr) => {};
-
-    (@panic; $($args:tt)*) => {
-        {
-            let ret: Result<_, IterMatchError<()>> = match_iter!($($args)*);
-            ret.unwrap()
-        }
-    };
-    ($iter:expr; ($($args:tt)*) => $body:expr) => {
-        {
-            #[allow(unused_mut)]
-            let mut iter = $iter;
-            // Not a real loop; used for error handling
-            let ret: Result<_, IterMatchError<_>> = loop {
-                match_iter!(@match 0, iter, $($args)*);
-                break Ok($body);
-            };
-            ret
-        }
-    };
-}
 
 /* Extends match_iter with typed matches. Takes a callback that determines
  * when a capture matches.
@@ -200,21 +109,21 @@ macro_rules! match_iter_typed {
     (@collect, ($($vars:tt)*), ($($args:tt)*), ($($acc:tt)*), ($x:ident : $ty:ident, $($rest:tt)*)) => {
         match_iter_typed!(@collect, ($($vars)*), ($($args)*), ($($acc)*, $x), ($($rest)*))
     };
-    (@collect, ($($vars:tt)*), ($($args:tt)*), ($($acc:tt)*), ($x:ident? : $ty:ident, $($rest:tt)*)) => {
-        match_iter_typed!(@collect, ($($vars)*), ($($args)*), ($($acc)*, $x?), ($($rest)*))
-    };
-    (@collect, ($($vars:tt)*), ($($args:tt)*), ($($acc:tt)*), ($x:ident* : $ty:ident, $($rest:tt)*)) => {
-        match_iter_typed!(@collect, ($($vars)*), ($($args)*), ($($acc)*, $x??), ($($rest)*))
+    (@collect, ($($vars:tt)*), ($($args:tt)*), ($($acc:tt)*), ($x:ident.. : $ty:ident, $($rest:tt)*)) => {
+        match_iter_typed!(@collect, ($($vars)*), ($($args)*), ($($acc)*, $x..), ($($rest)*))
     };
     // Catch extra comma if exists
     (@collect, ($($vars:tt)*), ($($args:tt)*), (,$($acc:tt)*), ($(,)*)) => {
         match_iter_typed!(@collect, ($($vars)*), ($($args)*), ($($acc)*), ())
     };
     (@collect, ($iter:expr, $body:expr, $callback:ident, $error:ident), ($($args:tt)*), ($($acc:tt)*), ($(,)*)) => {
-        match_iter!($iter; ($($acc)*) => {
-            match_iter_typed!(@callback, $callback, $iter, $($args)*);
-            $body
-        })
+        {
+            let res = iter_patterns::destructure_iter!($iter; [$($acc)*] => {
+                match_iter_typed!(@callback, $callback, $iter, $($args)*);
+                $body
+            });
+            res.ok_or(IterMatchError::NoMatchFound)
+        }
     };
 
     // Pass the matches through the callback
@@ -227,17 +136,7 @@ macro_rules! match_iter_typed {
         };
         match_iter_typed!(@callback, $callback, $iter $($rest)*);
     };
-    (@callback, $callback: ident, $iter:expr, $x:ident? : $ty:ident $($rest:tt)*) => {
-        let $x = $x.map(|x| $callback!(@type_callback, $ty, x));
-        #[allow(unused_mut)]
-        let mut $x = match $x {
-            Some(Ok(x)) => Some(x),
-            Some(Err(e)) => break Err(IterMatchError::Other(e)),
-            None => None,
-        };
-        match_iter_typed!(@callback, $callback, $iter $($rest)*);
-    };
-    (@callback, $callback: ident, $iter:expr, $x:ident* : $ty:ident $($rest:tt)*) => {
+    (@callback, $callback: ident, $iter:expr, $x:ident.. : $ty:ident $($rest:tt)*) => {
         let $x = $x.map(|x| $callback!(@type_callback, $ty, x)).collect();
         let $x: Vec<_> = match $x {
             Ok(x) => x,
@@ -253,10 +152,13 @@ macro_rules! match_iter_typed {
         {
             #[allow(unused_mut)]
             let mut iter = $iter;
-            match_iter_typed!(@collect,
-                (iter, $body, $callback, last_error),
-                ($($args)*), (), ($($args)*,)
-            )
+            let res: Result<_, IterMatchError<_>> = loop {
+                break match_iter_typed!(@collect,
+                    (iter, $body, $callback, last_error),
+                    ($($args)*), (), ($($args)*,)
+                )
+            };
+            res
         }
     };
 }
@@ -430,7 +332,7 @@ named!(raw_str<&'a str>; captured_str!(s) => s);
 named!(label<Label>; captured_str!(s) => Label::from(s.trim().to_owned()));
 
 rule!(double_quote_literal<ParsedText>;
-    children!(chunks*: double_quote_chunk) => {
+    children!(chunks..: double_quote_chunk) => {
         chunks.collect()
     }
 );
@@ -639,13 +541,14 @@ rule!(ifthenelse_expression<RcExpr>;
 );
 
 rule!(let_expression<RcExpr>;
-    children!(bindings*: let_binding, final_expr: expression) => {
+    children!(bindings..: let_binding, final_expr: expression) => {
         bindings.fold(final_expr, |acc, x| bx(Expr::Let(x.0, x.1, x.2, acc)))
     }
 );
 
 rule!(let_binding<(Label, Option<RcExpr>, RcExpr)>;
-    children!(name: label, annot?: expression, expr: expression) => (name, annot, expr)
+    children!(name: label, annot: expression, expr: expression) => (name, Some(annot), expr),
+    children!(name: label, expr: expression) => (name, None, expr),
 );
 
 rule!(forall_expression<RcExpr>;
@@ -661,9 +564,8 @@ rule!(arrow_expression<RcExpr>;
 );
 
 rule!(merge_expression<RcExpr>;
-    children!(x: expression, y: expression, z?: expression) => {
-        bx(Expr::Merge(x, y, z))
-    }
+    children!(x: expression, y: expression, z: expression) => bx(Expr::Merge(x, y, Some(z))),
+    children!(x: expression, y: expression) => bx(Expr::Merge(x, y, None)),
 );
 
 rule!(empty_collection<RcExpr>;
@@ -738,7 +640,7 @@ macro_rules! binop {
                     expression(pair)?
                 }
             }
-            // children!(first: expression, rest*: expression) => {
+            // children!(first: expression, rest..: expression) => {
             //     rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::$op, acc, e)))
             // }
         );
@@ -766,7 +668,7 @@ rule!(annotated_expression<RcExpr>;
 );
 
 rule!(application_expression<RcExpr>;
-    children!(first: expression, rest*: expression) => {
+    children!(first: expression, rest..: expression) => {
         let rest: Vec<_> = rest.collect();
         if rest.is_empty() {
             first
@@ -777,7 +679,7 @@ rule!(application_expression<RcExpr>;
 );
 
 rule!(selector_expression_raw<RcExpr>;
-    children!(first: expression, rest*: label) => {
+    children!(first: expression, rest..: label) => {
         rest.fold(first, |acc, e| bx(Expr::Field(acc, e)))
     }
 );
@@ -795,7 +697,7 @@ rule!(literal_expression_raw<RcExpr>;
 );
 
 rule!(identifier_raw<RcExpr>;
-    children!(name: str, idx?: natural_literal_raw) => {
+    children!(name: str, idx: natural_literal_raw) => {
         match Builtin::parse(name) {
             Some(b) => bx(Expr::Builtin(b)),
             None => match name {
@@ -803,10 +705,22 @@ rule!(identifier_raw<RcExpr>;
                 "False" => bx(Expr::BoolLit(false)),
                 "Type" => bx(Expr::Const(Const::Type)),
                 "Kind" => bx(Expr::Const(Const::Kind)),
-                name => bx(Expr::Var(V(Label::from(name.to_owned()), idx.unwrap_or(0)))),
+                name => bx(Expr::Var(V(Label::from(name.to_owned()), idx))),
             }
         }
-    }
+    },
+    children!(name: str) => {
+        match Builtin::parse(name) {
+            Some(b) => bx(Expr::Builtin(b)),
+            None => match name {
+                "True" => bx(Expr::BoolLit(true)),
+                "False" => bx(Expr::BoolLit(false)),
+                "Type" => bx(Expr::Const(Const::Type)),
+                "Kind" => bx(Expr::Const(Const::Kind)),
+                name => bx(Expr::Var(V(Label::from(name.to_owned()), 0))),
+            }
+        }
+    },
 );
 
 rule!(empty_record_literal<RcExpr>;
@@ -835,7 +749,7 @@ rule!(non_empty_record_type<(RcExpr, BTreeMap<Label, RcExpr>)>;
 );
 
 named!(partial_record_entries<(RcExpr, BTreeMap<Label, RcExpr>)>;
-    children!(expr: expression, entries*: record_entry) => {
+    children!(expr: expression, entries..: record_entry) => {
         (expr, entries.collect())
     }
 );
@@ -880,7 +794,7 @@ rule!(non_empty_union_type_or_literal
 );
 
 rule!(union_type_entries<BTreeMap<Label, RcExpr>>;
-    children!(entries*: union_type_entry) => {
+    children!(entries..: union_type_entry) => {
         entries.collect()
     }
 );
@@ -890,7 +804,7 @@ rule!(union_type_entry<(Label, RcExpr)>;
 );
 
 rule!(non_empty_list_literal_raw<RcExpr>;
-    children!(items*: expression) => {
+    children!(items..: expression) => {
         bx(Expr::NEListLit(items.collect()))
     }
 );
@@ -903,7 +817,7 @@ pub fn parse_expr(s: &str) -> ParseResult<RcExpr> {
     let pairs = DhallParser::parse(Rule::final_expression, s)?;
     // Match the only item in the pairs iterator
     // println!("{}", debug_pair(pairs.clone().next().unwrap()));
-    match_iter!(@panic; pairs; (p) => expression(p))
+    iter_patterns::destructure_iter!(pairs; [p] => expression(p)).unwrap()
     // Ok(bx(Expr::BoolLit(false)))
 }
 
diff --git a/iter_patterns/Cargo.toml b/iter_patterns/Cargo.toml
new file mode 100644
index 0000000..d63669d
--- /dev/null
+++ b/iter_patterns/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "iter_patterns"
+version = "0.1.0"
+authors = ["Nadrieril <nadrieril@users.noreply.github.com>"]
+edition = "2018"
+
+[lib]
+doctest = false
diff --git a/iter_patterns/src/lib.rs b/iter_patterns/src/lib.rs
new file mode 100644
index 0000000..75fe51c
--- /dev/null
+++ b/iter_patterns/src/lib.rs
@@ -0,0 +1,190 @@
+#![feature(slice_patterns)]
+
+/* Destructure an iterator using the syntax of slice_patterns.
+ * Wraps the match body in `Some` if there was a match; returns
+ * `None` otherwise.
+ * Contrary to slice_patterns, this allows moving out
+ * of the iterator.
+ * A variable length pattern (`x..`) is only allowed as the last
+ * pattern, unless the iterator is double-ended.
+ *
+ * Example:
+ * ```
+ * let vec = vec![Some(1), Some(2), None];
+ *
+ * destructure_iter!(vec.into_iter();
+ *     [Some(x), y.., z] => {
+ *         // x: usize
+ *         // y: impl Iterator<Option<usize>>
+ *         // z: Option<usize>
+ *     }
+ * )
+ * ```
+ *
+*/
+#[macro_export]
+macro_rules! destructure_iter {
+    // Variable length pattern
+    (@match 0, $iter:expr, ($body:expr), $x:ident.., $($rest:tt)*) => {
+        $crate::destructure_iter!(@match 1, $iter, ({
+            let $x = $iter;
+            $body
+        }), $($rest)*)
+    };
+    // Variable length pattern without a binder
+    (@match 0, $iter:expr, ($body:expr), .., $($rest:tt)*) => {
+        $crate::destructure_iter!(@match 1, $iter, ($body), $($rest)*)
+    };
+    // Single item pattern
+    (@match 0, $iter:expr, ($body:expr), $x:pat, $($rest:tt)*) => {
+        if let Some($x) = $iter.next() {
+            $crate::destructure_iter!(@match 0, $iter, ($body), $($rest)*)
+        } else {
+            None
+        }
+    };
+    // Single item pattern after a variable length one: declare reversed and take from the end
+    (@match 1, $iter:expr, ($body:expr), $x:pat, $($rest:tt)*) => {
+        $crate::destructure_iter!(@match 1, $iter, (
+            if let Some($x) = $iter.next_back() {
+                $body
+            } else {
+                None
+            }
+        ), $($rest)*)
+    };
+
+    // Check no elements remain
+    (@match 0, $iter:expr, ($body:expr) $(,)*) => {
+        if $iter.next().is_some() {
+            None
+        } else {
+            $body
+        }
+    };
+    // After a variable length pattern, everything has already been consumed
+    (@match 1, $iter:expr, ($body:expr) $(,)*) => {
+        $body
+    };
+
+    ($iter:expr; [$($args:tt)*] => $body:expr) => {
+        {
+            #[allow(unused_mut)]
+            let mut iter = $iter;
+            $crate::destructure_iter!(@match 0, iter, (Some($body)), $($args)*,)
+        }
+    };
+}
+
+
+/* Pattern-match on a vec using the syntax of slice_patterns.
+ * Wraps the match body in `Some` if there was a match; returns
+ * `None` otherwise.
+ * A variable length pattern (`x..`) returns an iterator.
+ *
+ * Example:
+ * ```
+ * let vec = vec![Some(1), Some(2), None];
+ *
+ * match_vec!(vec;
+ *     [Some(x), y.., z] => {
+ *         // x: usize
+ *         // y: impl Iterator<Option<usize>>
+ *         // z: Option<usize>
+ *     }
+ *     [x, Some(0)] => {
+ *         // x: Option<usize>
+ *     },
+ *     [..] => { }
+ * )
+ * ```
+ *
+*/
+#[macro_export]
+macro_rules! match_vec {
+    ($arg:expr; $( [$($args:tt)*] => $body:expr ),* $(,)*) => {
+        {
+            let vec = $arg;
+            // Match as references to decide which branch to take
+            // I think `match_default_bindings` should make this always work but
+            // there may be some patterns this doesn't capture.
+            #[allow(unused_variables, unreachable_patterns)]
+            match vec.as_slice() {
+                $(
+                    [$($args)*] => {
+                        // Actually consume the values
+                        #[allow(unused_mut)]
+                        let mut iter = vec.into_iter();
+                        $crate::destructure_iter!(iter; [$($args)*] => $body)
+                    }
+                )*
+                _ => None,
+            }
+        }
+    };
+}
+
+
+/* Pattern-match on an iterator using the syntax of slice_patterns.
+ * Wraps the match body in `Some` if there was a match; returns
+ * `None` otherwise.
+ *
+ * Example:
+ * ```
+ * let vec = vec![Some(1), Some(2), None];
+ *
+ * match_iter!(vec.into_iter();
+ *     [Some(x), y.., z] => {
+ *         // x: usize
+ *         // y: impl Iterator<Option<usize>>
+ *         // z: Option<usize>
+ *     }
+ *     [x, Some(0)] => {
+ *         // x: Option<usize>
+ *     },
+ *     [..] => {
+ * )
+ * ```
+ *
+*/
+#[macro_export]
+macro_rules! match_iter {
+    ($arg:expr; $($args:tt)*) => {
+        {
+            let vec: Vec<_> = $arg.collect();
+            $crate::match_vec!(vec, $($args)*)
+        }
+    };
+}
+
+
+#[test]
+fn test() {
+    let test = |v: Vec<Option<isize>>| {
+        match_vec!(v.into_iter();
+            [Some(_x), None, None] => 4,
+            [Some(_x), None] => 2,
+            [None, Some(y)] => 1,
+            [None, _y..] => 3,
+            [_x.., Some(y), Some(z)] => y - z,
+            [] => 0,
+            [..] => -1,
+        )
+        .unwrap()
+    };
+
+    assert_eq!(test(vec![Some(0), None, None]), 4);
+    assert_eq!(test(vec![Some(0), None]), 2);
+    assert_eq!(test(vec![None, Some(0)]), 1);
+    assert_eq!(test(vec![Some(1), Some(2), Some(5), Some(14)]), -9);
+    assert_eq!(test(vec![None]), 3);
+    assert_eq!(test(vec![]), 0);
+    assert_eq!(test(vec![Some(0)]), -1);
+
+    // Test move out of pattern
+    struct Foo;
+    let _: (Foo, Foo) = match_vec!(vec![Some(Foo), Some(Foo)].into_iter();
+        [Some(f1), Some(f2)] => (f1, f2),
+    )
+    .unwrap();
+}