Implement pattern guards

The syntax is

    alt x {
        mypat where mycond { ... }
    }

The condition may refer to any of the variables bound by the pattern.
When a guard fails, pattern-matching continues with the next pattern.

Closes #857

8 files changed, 80 insertions, 29 deletions

diff --git a/src/comp/middle/check_alt.rs b/src/comp/middle/check_alt.rs
index 7c2f76c0590..9d99464c2b9 100644
--- a/src/comp/middle/check_alt.rs
+++ b/src/comp/middle/check_alt.rs
@@ -22,9 +22,11 @@ fn check_arms(tcx: &ty::ctxt, arms: &[arm]) {
             let reachable = true;
             let j = 0;
             while j < i {
-                for prev_pat: @pat in arms[j].pats {
-                    if pattern_supersedes(tcx, prev_pat, arm_pat) {
-                        reachable = false;
+                if std::option::is_none(arms[j].guard) {
+                    for prev_pat: @pat in arms[j].pats {
+                        if pattern_supersedes(tcx, prev_pat, arm_pat) {
+                            reachable = false;
+                        }
                     }
                 }
                 j += 1;
diff --git a/src/comp/middle/trans_alt.rs b/src/comp/middle/trans_alt.rs
index d0be6b60d9f..5d4cc64c079 100644
--- a/src/comp/middle/trans_alt.rs
+++ b/src/comp/middle/trans_alt.rs
@@ -55,8 +55,19 @@ fn variant_opt(ccx: &@crate_ctxt, pat_id: ast::node_id) -> opt {
 }
 
 type bind_map = [{ident: ast::ident, val: ValueRef}];
+fn assoc(key: str, list: &bind_map) -> option::t<ValueRef> {
+    for elt: {ident: ast::ident, val: ValueRef} in list {
+        if str::eq(elt.ident, key) { ret some(elt.val); }
+    }
+    ret none;
+}
+
 type match_branch =
-    @{pats: [@ast::pat], body: BasicBlockRef, mutable bound: bind_map};
+    @{pats: [@ast::pat],
+      bound: bind_map,
+      data: @{body: BasicBlockRef,
+              guard: option::t<@ast::expr>,
+              id_map: ast::pat_id_map}};
 type match = [match_branch];
 
 fn matches_always(p: &@ast::pat) -> bool {
@@ -69,14 +80,6 @@ fn matches_always(p: &@ast::pat) -> bool {
         };
 }
 
-
-fn bind_for_pat(p: &@ast::pat, br: &match_branch, val: ValueRef) {
-    alt p.node {
-      ast::pat_bind(name) { br.bound += [{ident: name, val: val}]; }
-      _ { }
-    }
-}
-
 type enter_pat = fn(&@ast::pat) -> option::t<[@ast::pat]>;
 
 fn enter_match(m: &match, col: uint, val: ValueRef, e: &enter_pat) -> match {
@@ -84,12 +87,17 @@ fn enter_match(m: &match, col: uint, val: ValueRef, e: &enter_pat) -> match {
     for br: match_branch in m {
         alt e(br.pats[col]) {
           some(sub) {
-            let pats =
-                vec::slice(br.pats, 0u, col) + sub +
+            let pats = vec::slice(br.pats, 0u, col) + sub +
                     vec::slice(br.pats, col + 1u, vec::len(br.pats));
-            let new_br = @{pats: pats with *br};
+            let new_br = @{pats: pats,
+                           bound: alt br.pats[col].node {
+                             ast::pat_bind(name) {
+                               br.bound + [{ident: name, val: val}]
+                             }
+                             _ { br.bound }
+                           }
+                           with *br};
             result += [new_br];
-            bind_for_pat(br.pats[col], new_br, val);
           }
           none. { }
         }
@@ -282,8 +290,30 @@ fn compile_submatch(bcx: @block_ctxt, m: &match, vals: [ValueRef],
                     f: &mk_fail, exits: &mutable [exit_node]) {
     if vec::len(m) == 0u { bcx.build.Br(f()); ret; }
     if vec::len(m[0].pats) == 0u {
-        exits += [{bound: m[0].bound, from: bcx.llbb, to: m[0].body}];
-        bcx.build.Br(m[0].body);
+        let data = m[0].data;
+        alt data.guard {
+          some(e) {
+            let guard_cx = new_scope_block_ctxt(bcx, "guard");
+            let next_cx = new_sub_block_ctxt(bcx, "next");
+            let else_cx = new_sub_block_ctxt(bcx, "else");
+            bcx.build.Br(guard_cx.llbb);
+            // Temporarily set bindings. They'll be rewritten to PHI nodes for
+            // the actual arm block.
+            for each @{key, val} in data.id_map.items() {
+                bcx.fcx.lllocals.insert
+                    (val, option::get(assoc(key, m[0].bound)));
+            }
+            let {bcx: guard_cx, val: guard_val} =
+                trans::trans_expr(guard_cx, e);
+            guard_cx.build.CondBr(guard_val, next_cx.llbb, else_cx.llbb);
+            compile_submatch(else_cx, vec::slice(m, 1u, vec::len(m)),
+                             vals, f, exits);
+            bcx = next_cx;
+          }
+          _ {}
+        }
+        exits += [{bound: m[0].bound, from: bcx.llbb, to: data.body}];
+        bcx.build.Br(data.body);
         ret;
     }
 
@@ -433,13 +463,6 @@ fn compile_submatch(bcx: @block_ctxt, m: &match, vals: [ValueRef],
 // Returns false for unreachable blocks
 fn make_phi_bindings(bcx: &@block_ctxt, map: &[exit_node],
                      ids: &ast::pat_id_map) -> bool {
-    fn assoc(key: str, list: &bind_map) -> option::t<ValueRef> {
-        for elt: {ident: ast::ident, val: ValueRef} in list {
-            if str::eq(elt.ident, key) { ret some(elt.val); }
-        }
-        ret none;
-    }
-
     let our_block = bcx.llbb as uint;
     let success = true;
     for each item: @{key: ast::ident, val: ast::node_id} in ids.items() {
@@ -477,9 +500,14 @@ fn trans_alt(cx: &@block_ctxt, expr: &@ast::expr, arms: &[ast::arm],
 
     for a: ast::arm in arms {
         let body = new_scope_block_ctxt(cx, "case_body");
+        let id_map = ast::pat_id_map(a.pats[0]);
         bodies += [body];
         for p: @ast::pat in a.pats {
-            match += [@{pats: [p], body: body.llbb, mutable bound: []}];
+            match += [@{pats: [p],
+                        bound: [],
+                        data: @{body: body.llbb,
+                                guard: a.guard,
+                                id_map: id_map}}];
         }
     }
 
diff --git a/src/comp/middle/typeck.rs b/src/comp/middle/typeck.rs
index cdbc833dac0..9f03a31fbb8 100644
--- a/src/comp/middle/typeck.rs
+++ b/src/comp/middle/typeck.rs
@@ -2038,6 +2038,12 @@ fn check_expr_with_unifier(fcx: &@fn_ctxt, expr: &@ast::expr, unify: &unifier,
         let result_ty = next_ty_var(fcx);
         let arm_non_bot = false;
         for arm: ast::arm in arms {
+            alt arm.guard {
+              some(e) {
+                check_expr_with(fcx, e, ty::mk_bool(tcx));
+              }
+              none. {}
+            }
             if !check_block(fcx, arm.body) { arm_non_bot = true; }
             let bty = block_ty(tcx, arm.body);
             result_ty = demand::simple(fcx, arm.body.span, result_ty, bty);
diff --git a/src/comp/syntax/ast.rs b/src/comp/syntax/ast.rs
index 80d327b119b..2537aa95f36 100644
--- a/src/comp/syntax/ast.rs
+++ b/src/comp/syntax/ast.rs
@@ -267,7 +267,7 @@ type decl = spanned<decl_>;
 
 tag decl_ { decl_local([@local]); decl_item(@item); }
 
-type arm = {pats: [@pat], body: blk};
+type arm = {pats: [@pat], guard: option::t<@expr>, body: blk};
 
 type field_ = {mut: mutability, ident: ident, expr: @expr};
 
diff --git a/src/comp/syntax/fold.rs b/src/comp/syntax/fold.rs
index ef04e66d756..a91b2f31814 100644
--- a/src/comp/syntax/fold.rs
+++ b/src/comp/syntax/fold.rs
@@ -269,7 +269,9 @@ fn noop_fold_stmt(s: &stmt_, fld: ast_fold) -> stmt_ {
 }
 
 fn noop_fold_arm(a: &arm, fld: ast_fold) -> arm {
-    ret {pats: vec::map(fld.fold_pat, a.pats), body: fld.fold_block(a.body)};
+    ret {pats: vec::map(fld.fold_pat, a.pats),
+         guard: option::map(fld.fold_expr, a.guard),
+         body: fld.fold_block(a.body)};
 }
 
 fn noop_fold_pat(p: &pat_, fld: ast_fold) -> pat_ {
diff --git a/src/comp/syntax/parse/parser.rs b/src/comp/syntax/parse/parser.rs
index d20f345b3af..b20c7905013 100644
--- a/src/comp/syntax/parse/parser.rs
+++ b/src/comp/syntax/parse/parser.rs
@@ -1360,8 +1360,12 @@ fn parse_alt_expr(p: &parser) -> @ast::expr {
     let arms: [ast::arm] = [];
     while p.peek() != token::RBRACE {
         let pats = parse_pats(p);
+        let guard = none;
+        if eat_word(p, "when") {
+            guard = some(parse_expr(p));
+        }
         let blk = parse_block(p);
-        arms += [{pats: pats, body: blk}];
+        arms += [{pats: pats, guard: guard, body: blk}];
     }
     let hi = p.get_hi_pos();
     p.bump();
diff --git a/src/comp/syntax/print/pprust.rs b/src/comp/syntax/print/pprust.rs
index c0e38a3b40e..8ecbfd58405 100644
--- a/src/comp/syntax/print/pprust.rs
+++ b/src/comp/syntax/print/pprust.rs
@@ -905,6 +905,14 @@ fn print_expr(s: &ps, expr: &@ast::expr) {
                 print_pat(s, p);
             }
             space(s.s);
+            alt arm.guard {
+              some(e) {
+                word_space(s, "when");
+                print_expr(s, e);
+                space(s.s);
+              }
+              none. {}
+            }
             print_possibly_embedded_block(s, arm.body, block_normal,
                                           alt_indent_unit);
         }
diff --git a/src/comp/syntax/visit.rs b/src/comp/syntax/visit.rs
index 350dfc3dd44..d69104a7010 100644
--- a/src/comp/syntax/visit.rs
+++ b/src/comp/syntax/visit.rs
@@ -332,6 +332,7 @@ fn visit_expr<E>(ex: &@expr, e: &E, v: &vt<E>) {
 
 fn visit_arm<E>(a: &arm, e: &E, v: &vt<E>) {
     for p: @pat in a.pats { v.visit_pat(p, e, v); }
+    visit_expr_opt(a.guard, e, v);
     v.visit_block(a.body, e, v);
 }