revise handling of match expressions so that arms branch to next arm.

Update the graphviz tests accordingly.

Fixes #22073. (Includes regression test for the issue.)

(Factoring of aatch CFG code, Part 4.)

7 files changed, 203 insertions, 65 deletions

diff --git a/src/librustc/middle/cfg/construct.rs b/src/librustc/middle/cfg/construct.rs
index 4b06eecaffe..52eedc460eb 100644
--- a/src/librustc/middle/cfg/construct.rs
+++ b/src/librustc/middle/cfg/construct.rs
@@ -11,6 +11,7 @@
 use middle::cfg::*;
 use middle::def;
 use middle::graph;
+use middle::pat_util;
 use middle::region::CodeExtent;
 use middle::ty;
 use syntax::ast;
@@ -149,23 +150,6 @@ impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
         pats.fold(pred, |pred, pat| self.pat(&**pat, pred))
     }
 
-    fn pats_any(&mut self,
-                pats: &[P<ast::Pat>],
-                pred: CFGIndex) -> CFGIndex {
-        //! Handles case where just one of the patterns must match.
-
-        if pats.len() == 1 {
-            self.pat(&*pats[0], pred)
-        } else {
-            let collect = self.add_dummy_node(&[]);
-            for pat in pats {
-                let pat_exit = self.pat(&**pat, pred);
-                self.add_contained_edge(pat_exit, collect);
-            }
-            collect
-        }
-    }
-
     fn expr(&mut self, expr: &ast::Expr, pred: CFGIndex) -> CFGIndex {
         match expr.node {
             ast::ExprBlock(ref blk) => {
@@ -288,45 +272,7 @@ impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
             }
 
             ast::ExprMatch(ref discr, ref arms, _) => {
-                //
-                //     [pred]
-                //       |
-                //       v 1
-                //    [discr]
-                //       |
-                //       v 2
-                //    [cond1]
-                //      /  \
-                //     |    \
-                //     v 3   \
-                //  [pat1]    \
-                //     |       |
-                //     v 4     |
-                //  [guard1]   |
-                //     |       |
-                //     |       |
-                //     v 5     v
-                //  [body1]  [cond2]
-                //     |      /  \
-                //     |    ...  ...
-                //     |     |    |
-                //     v 6   v    v
-                //  [.....expr.....]
-                //
-                let discr_exit = self.expr(&**discr, pred);              // 1
-
-                let expr_exit = self.add_ast_node(expr.id, &[]);
-                let mut cond_exit = discr_exit;
-                for arm in arms {
-                    cond_exit = self.add_dummy_node(&[cond_exit]);        // 2
-                    let pats_exit = self.pats_any(&arm.pats,
-                                                  cond_exit);            // 3
-                    let guard_exit = self.opt_expr(&arm.guard,
-                                                   pats_exit);           // 4
-                    let body_exit = self.expr(&*arm.body, guard_exit);   // 5
-                    self.add_contained_edge(body_exit, expr_exit);       // 6
-                }
-                expr_exit
+                self.match_(expr.id, &discr, &arms, pred)
             }
 
             ast::ExprBinary(op, ref l, ref r) if ast_util::lazy_binop(op.node) => {
@@ -503,6 +449,108 @@ impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
         self.add_ast_node(expr.id, &[subexprs_exit])
     }
 
+    fn match_(&mut self, id: ast::NodeId, discr: &ast::Expr,
+              arms: &[ast::Arm], pred: CFGIndex) -> CFGIndex {
+        // The CFG for match expression is quite complex, so no ASCII
+        // art for it (yet).
+        //
+        // The CFG generated below matches roughly what trans puts
+        // out. Each pattern and guard is visited in parallel, with
+        // arms containing multiple patterns generating multiple nodes
+        // for the same guard expression. The guard expressions chain
+        // into each other from top to bottom, with a specific
+        // exception to allow some additional valid programs
+        // (explained below). Trans differs slightly in that the
+        // pattern matching may continue after a guard but the visible
+        // behaviour should be the same.
+        //
+        // What is going on is explained in further comments.
+
+        // Visit the discriminant expression
+        let discr_exit = self.expr(discr, pred);
+
+        // Add a node for the exit of the match expression as a whole.
+        let expr_exit = self.add_ast_node(id, &[]);
+
+        // Keep track of the previous guard expressions
+        let mut prev_guards = Vec::new();
+        // Track if the previous pattern contained bindings or wildcards
+        let mut prev_has_bindings = false;
+
+        for arm in arms {
+            // Add an exit node for when we've visited all the
+            // patterns and the guard (if there is one) in the arm.
+            let arm_exit = self.add_dummy_node(&[]);
+
+            for pat in &arm.pats {
+                // Visit the pattern, coming from the discriminant exit
+                let mut pat_exit = self.pat(&**pat, discr_exit);
+
+                // If there is a guard expression, handle it here
+                if let Some(ref guard) = arm.guard {
+                    // Add a dummy node for the previous guard
+                    // expression to target
+                    let guard_start = self.add_dummy_node(&[pat_exit]);
+                    // Visit the guard expression
+                    let guard_exit = self.expr(&**guard, guard_start);
+
+                    let this_has_bindings = pat_util::pat_contains_bindings_or_wild(
+                        &self.tcx.def_map, &**pat);
+
+                    // If both this pattern and the previous pattern
+                    // were free of bindings, they must consist only
+                    // of "constant" patterns. Note we cannot match an
+                    // all-constant pattern, fail the guard, and then
+                    // match *another* all-constant pattern. This is
+                    // because if the previous pattern matches, then
+                    // we *cannot* match this one, unless all the
+                    // constants are the same (which is rejected by
+                    // `check_match`).
+                    //
+                    // We can use this to be smarter about the flow
+                    // along guards. If the previous pattern matched,
+                    // then we know we will not visit the guard in
+                    // this one (whether or not the guard succeeded),
+                    // if the previous pattern failed, then we know
+                    // the guard for that pattern will not have been
+                    // visited. Thus, it is not possible to visit both
+                    // the previous guard and the current one when
+                    // both patterns consist only of constant
+                    // sub-patterns.
+                    //
+                    // However, if the above does not hold, then all
+                    // previous guards need to be wired to visit the
+                    // current guard pattern.
+                    if prev_has_bindings || this_has_bindings {
+                        while let Some(prev) = prev_guards.pop() {
+                            self.add_contained_edge(prev, guard_start);
+                        }
+                    }
+
+                    prev_has_bindings = this_has_bindings;
+
+                    // Push the guard onto the list of previous guards
+                    prev_guards.push(guard_exit);
+
+                    // Update the exit node for the pattern
+                    pat_exit = guard_exit;
+                }
+
+                // Add an edge from the exit of this pattern to the
+                // exit of the arm
+                self.add_contained_edge(pat_exit, arm_exit);
+            }
+
+            // Visit the body of this arm
+            let body_exit = self.expr(&arm.body, arm_exit);
+
+            // Link the body to the exit of the expression
+            self.add_contained_edge(body_exit, expr_exit);
+        }
+
+        expr_exit
+    }
+
     fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
         self.add_node(CFGNodeData::Dummy, preds)
     }
diff --git a/src/librustc/middle/pat_util.rs b/src/librustc/middle/pat_util.rs
index 01dc55c3eee..a7df2f4a5da 100644
--- a/src/librustc/middle/pat_util.rs
+++ b/src/librustc/middle/pat_util.rs
@@ -119,6 +119,21 @@ pub fn pat_contains_bindings(dm: &DefMap, pat: &ast::Pat) -> bool {
     contains_bindings
 }
 
+/// Checks if the pattern contains any patterns that bind something to
+/// an ident or wildcard, e.g. `foo`, or `Foo(_)`, `foo @ Bar(..)`,
+pub fn pat_contains_bindings_or_wild(dm: &DefMap, pat: &ast::Pat) -> bool {
+    let mut contains_bindings = false;
+    walk_pat(pat, |p| {
+        if pat_is_binding_or_wild(dm, p) {
+            contains_bindings = true;
+            false // there's at least one binding/wildcard, can short circuit now.
+        } else {
+            true
+        }
+    });
+    contains_bindings
+}
+
 pub fn simple_identifier<'a>(pat: &'a ast::Pat) -> Option<&'a ast::Ident> {
     match pat.node {
         ast::PatIdent(ast::BindByValue(_), ref path1, None) => {
diff --git a/src/test/compile-fail/move-in-guard-1.rs b/src/test/compile-fail/move-in-guard-1.rs
new file mode 100644
index 00000000000..5d29d0e1fd0
--- /dev/null
+++ b/src/test/compile-fail/move-in-guard-1.rs
@@ -0,0 +1,25 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(box_syntax)]
+
+pub fn main() {
+    let x = box 1;
+
+    let v = (1, 2);
+
+    match v {
+        (1, _) if take(x) => (),
+        (_, 2) if take(x) => (), //~ ERROR use of moved value: `x`
+        _ => (),
+    }
+}
+
+fn take<T>(_: T) -> bool { false }
diff --git a/src/test/compile-fail/move-in-guard-2.rs b/src/test/compile-fail/move-in-guard-2.rs
new file mode 100644
index 00000000000..23af2579797
--- /dev/null
+++ b/src/test/compile-fail/move-in-guard-2.rs
@@ -0,0 +1,25 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(box_syntax)]
+
+pub fn main() {
+    let x = box 1;
+
+    let v = (1, 2);
+
+    match v {
+        (1, _) |
+        (_, 2) if take(x) => (), //~ ERROR use of moved value: `x`
+        _ => (),
+    }
+}
+
+fn take<T>(_: T) -> bool { false }
diff --git a/src/test/run-make/graphviz-flowgraph/f07.dot-expected.dot b/src/test/run-make/graphviz-flowgraph/f07.dot-expected.dot
index bee4a120d59..51c6b14e1de 100644
--- a/src/test/run-make/graphviz-flowgraph/f07.dot-expected.dot
+++ b/src/test/run-make/graphviz-flowgraph/f07.dot-expected.dot
@@ -22,12 +22,12 @@ digraph block {
     N3 -> N4;
     N4 -> N5;
     N5 -> N6;
-    N6 -> N8;
-    N8 -> N9;
+    N6 -> N9;
     N9 -> N10;
     N10 -> N11;
     N11 -> N12;
-    N12 -> N13;
+    N12 -> N8;
+    N8 -> N13;
     N13 -> N14;
     N14 -> N15;
     N15 -> N7;
diff --git a/src/test/run-make/graphviz-flowgraph/f13.dot-expected.dot b/src/test/run-make/graphviz-flowgraph/f13.dot-expected.dot
index 76e66513515..fb7d2ad97bd 100644
--- a/src/test/run-make/graphviz-flowgraph/f13.dot-expected.dot
+++ b/src/test/run-make/graphviz-flowgraph/f13.dot-expected.dot
@@ -32,16 +32,16 @@ digraph block {
     N6 -> N7;
     N7 -> N8;
     N8 -> N9;
-    N9 -> N11;
-    N11 -> N12;
-    N12 -> N13;
+    N9 -> N12;
+    N12 -> N11;
+    N11 -> N13;
     N13 -> N14;
     N14 -> N15;
     N15 -> N10;
-    N11 -> N16;
-    N16 -> N17;
+    N9 -> N17;
     N17 -> N18;
-    N18 -> N19;
+    N18 -> N16;
+    N16 -> N19;
     N19 -> N20;
     N20 -> N21;
     N21 -> N22;
diff --git a/src/test/run-pass/move-guard-const.rs b/src/test/run-pass/move-guard-const.rs
new file mode 100644
index 00000000000..64c4f1fdbae
--- /dev/null
+++ b/src/test/run-pass/move-guard-const.rs
@@ -0,0 +1,25 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(box_syntax)]
+
+fn main() {
+    let x = box 1;
+
+    let v = (1, 2);
+
+    match v {
+        (2, 1) if take(x) => (),
+        (1, 2) if take(x) => (),
+        _ => (),
+    }
+}
+
+fn take<T>(_: T) -> bool { false }