Add a pass that checks for unreachable alt arms

5 files changed, 115 insertions, 2 deletions

diff --git a/src/comp/driver/rustc.rs b/src/comp/driver/rustc.rs
index 86ab4042fd3..60075585c85 100644
--- a/src/comp/driver/rustc.rs
+++ b/src/comp/driver/rustc.rs
@@ -138,6 +138,8 @@ fn compile_input(session::session sess, ast::crate_cfg cfg, str input,
     auto ty_cx = ty::mk_ctxt(sess, d, ast_map, freevars);
     time[()](time_passes, "typechecking",
              bind typeck::check_crate(ty_cx, crate));
+    time[()](time_passes, "alt checking",
+             bind middle::check_alt::check_crate(ty_cx, crate));
     if (sess.get_opts().run_typestate) {
         time(time_passes, "typestate checking",
              bind middle::tstate::ck::check_crate(ty_cx, crate));
diff --git a/src/comp/middle/check_alt.rs b/src/comp/middle/check_alt.rs
new file mode 100644
index 00000000000..6b7a2e90839
--- /dev/null
+++ b/src/comp/middle/check_alt.rs
@@ -0,0 +1,102 @@
+import syntax::ast::*;
+import syntax::visit;
+
+fn check_crate(&ty::ctxt tcx, &@crate crate) {
+    auto v = @rec(visit_expr=bind check_expr(tcx, _, _, _)
+                  with *visit::default_visitor[()]());
+    visit::visit_crate(*crate, (), visit::mk_vt(v));
+    tcx.sess.abort_if_errors();
+}
+
+fn check_expr(&ty::ctxt tcx, &@expr ex, &() s, &visit::vt[()] v) {
+    visit::visit_expr(ex, s, v);
+    alt ex.node {
+      expr_alt(_, ?arms) { check_arms(tcx, arms); }
+      _ {}
+    }
+}
+
+fn check_arms(&ty::ctxt tcx, &arm[] arms) {
+    auto i = 0;
+    for (arm arm in arms) {
+        for (@pat arm_pat in arm.pats) {
+            auto reachable = true;
+            auto j = 0;
+            while j < i {
+                for (@pat prev_pat in arms.(j).pats) {
+                    if pattern_supersedes(tcx, prev_pat, arm_pat) {
+                        reachable = false;
+                    }
+                }
+                j += 1;
+            }
+            if !reachable {
+                tcx.sess.span_err(arm_pat.span, "unreachable pattern");
+            }
+        }
+        i += 1;
+    }
+}
+
+fn pattern_supersedes(&ty::ctxt tcx, &@pat a, &@pat b) -> bool {
+    fn patterns_supersede(&ty::ctxt tcx, &(@pat)[] as, &(@pat)[] bs) -> bool {
+        auto i = 0;
+        for (@pat a in as) {
+            if !pattern_supersedes(tcx, a, bs.(i)) { ret false; }
+            i += 1;
+        }
+        ret true;
+    }
+    fn field_patterns_supersede(&ty::ctxt tcx, &field_pat[] fas,
+                                &field_pat[] fbs) -> bool {
+        auto wild = @rec(id=0, node=pat_wild, span=rec(lo=0u, hi=0u));
+        for (field_pat fa in fas) {
+            auto pb = wild;
+            for (field_pat fb in fbs) {
+                if fa.ident == fb.ident { pb = fb.pat; }
+            }
+            if !pattern_supersedes(tcx, fa.pat, pb) { ret false; }
+        }
+        ret true;
+    }
+
+    alt a.node {
+      pat_wild | pat_bind(_) { ret true; }
+      pat_lit(?la) {
+        alt b.node {
+          pat_lit(?lb) { ret util::common::lit_eq(la, lb); }
+          _ { ret false; }
+        }
+      }
+      pat_tag(?va, ?suba) {
+        alt b.node {
+          pat_tag(?vb, ?subb) {
+            ret tcx.def_map.get(a.id) == tcx.def_map.get(b.id) &&
+                patterns_supersede(tcx, suba, subb);
+          }
+          _ { ret false; }
+        }
+      }
+      pat_rec(?suba, _) {
+        alt b.node {
+          pat_rec(?subb, _) { ret field_patterns_supersede(tcx, suba, subb); }
+          _ { ret false; }
+        }
+      }
+      pat_box(?suba) {
+        alt b.node {
+          pat_box(?subb) { ret pattern_supersedes(tcx, suba, subb); }
+          _ { ret pattern_supersedes(tcx, suba, b); }
+        }
+      }
+    }
+}
+
+// Local Variables:
+// mode: rust
+// fill-column: 78;
+// indent-tabs-mode: nil
+// c-basic-offset: 4
+// buffer-file-coding-system: utf-8-unix
+// compile-command: "make -k -C $RBUILD 2>&1 | sed -e 's/\\/x\\//x:\\//g'";
+// End:
diff --git a/src/comp/middle/ty.rs b/src/comp/middle/ty.rs
index d6f723f1ea5..97c6edc23e4 100644
--- a/src/comp/middle/ty.rs
+++ b/src/comp/middle/ty.rs
@@ -1254,8 +1254,6 @@ fn type_owns_heap_mem(&ctxt cx, &t ty) -> bool {
         case (ty_port(_)) { result = false; }
         case (ty_chan(_)) { result = false; }
         case (ty_task) { result = false; }
-        case (ty_tup(_)) { result = false; }
-        case (ty_rec(_)) { result = false; }
         case (ty_var(_)) { fail "ty_var in type_owns_heap_mem"; }
         case (ty_param(_)) { result = false; }
     }
diff --git a/src/comp/rustc.rc b/src/comp/rustc.rc
index 1970aa66cd2..7c9377bd19d 100644
--- a/src/comp/rustc.rc
+++ b/src/comp/rustc.rc
@@ -25,6 +25,7 @@ mod middle {
     mod ast_map;
     mod resolve;
     mod typeck;
+    mod check_alt;
     mod alias;
     mod freevars;
 
diff --git a/src/test/compile-fail/unreachable-arm.rs b/src/test/compile-fail/unreachable-arm.rs
new file mode 100644
index 00000000000..cfff4794da9
--- /dev/null
+++ b/src/test/compile-fail/unreachable-arm.rs
@@ -0,0 +1,10 @@
+// error-pattern:unreachable pattern
+
+tag foo { a(@foo, int); b(uint); }
+
+fn main() {
+    alt b(1u) {
+      b(_) | a(@_, 1) {}
+      a(_, 1) {}
+    }
+}