Auto merge of #33667 - pnkfelix:fixes-to-mir-dataflow, r=arielb1

Fixes to mir dataflow

Fixes to mir dataflow

This collects a bunch of changes to `rustc_borrowck::borrowck::dataflow` (which others have pointed out should probably migrate to some crate that isn't tied to the borrow-checker -- but I have not attempted that here, especially since there are competing approaches to dataflow that we should also evaluate).

These changes:
 1. Provide a family of related analyses: MovingOutStatements (which is what the old AST-based dataflo computed), as well as MaybeInitialized, MaybeUninitalized, and DefinitelyInitialized.
   * (The last two are actually inverses of each other; we should pick one and drop the other.)
 2. Fix bugs in the pre-existing analysis implementation, which was untested and thus some obvious bugs went unnoticed, which brings us to the third point:
 3. Add a unit test infrastructure for the MIR dataflow analysis.
   * The tests work by adding a new intrinsic that is able to query the analysis state for a particular expression (technically, a particular L-value).
   * See the examples in compile-fail/mir-dataflow/inits-1.rs and compile-fail/mir-dataflow/uninits-1.rs
   * These tests are only checking the results for MaybeInitialized, MaybeUninitalized, and DefinitelyInitialized; I am not sure if it will be feasible to generalize this testing strategy to the MovingOutStatements dataflow operator.

5 files changed, 280 insertions, 0 deletions

diff --git a/src/test/compile-fail/mir-dataflow/README.md b/src/test/compile-fail/mir-dataflow/README.md
new file mode 100644
index 00000000000..a3ab14b23c7
--- /dev/null
+++ b/src/test/compile-fail/mir-dataflow/README.md
@@ -0,0 +1,53 @@
+This directory contains unit tests for the MIR-based dataflow
+analysis.
+
+These unit tests check the dataflow analysis by embedding calls to a
+special `rustc_peek` intrinsic within the code, in tandem with an
+attribute `#[rustc_mir(rustc_peek_maybe_init)]` (\*). With that
+attribute in place, `rustc_peek` calls are a signal to the compiler to
+lookup the computed dataflow state for the Lvalue corresponding to the
+argument expression being fed to `rustc_peek`. If the dataflow state
+for that Lvalue is a 1-bit at that point in the control flow, then no
+error is emitted by the compiler at that point; if it is a 0-bit, then
+that invocation of `rustc_peek` will emit an error with the message
+"rustc_peek: bit not set".
+
+(\*): Or `#[rustc_mir(rustc_peek_maybe_uninit)]`, and perhaps other
+variants in the future.
+
+The end effect is that one can write unit tests for MIR dataflow that
+perform simple-queries of the computed dataflow state, and the tests
+should be able to be robust in the face of changes to how MIR is
+represented or constructed.
+
+----
+
+Sometimes understanding the dataflow results is difficult without
+looking at the actual MIR control-flow graph being processed with the
+corresponding GEN and KILL sets.
+
+For a graphviz-rendering with dataflow annotations, add the attribute
+`#[rustc_mir(borrowck_graphviz_postflow="/path/to/suffix.dot")]` to
+the function in question. (You can change the content of
+`"suffix.dot"` to control the filenames used for the output). This
+will generate a separate file for each dataflow analysis, adding a
+prefix (corresponding to the name of the analysis) to the filename in
+each generated output path.
+
+ * For example, the above attribute will currently cause two files to
+   be generated: `/path/to/maybe_init_suffix.dot` and
+   `/path/to/maybe_uninit_suffix.dot`.
+
+ * The generated `.dot` file shows both the computed dataflow results
+   on *entry* to each block, as well as the gen- and kill-sets that
+   were so-called "transfer functions" summarizing the effect of each
+   basic block.
+
+ * (In addition to the `borrowck_graphviz_postflow` attribute-key
+   noted above, there is also `borrowck_graphviz_preflow`; it has the
+   same interface and generates the same set of files, but it renders
+   the dataflow state after building the gen- and kill-sets but
+   *before* running the dataflow analysis itself, so each entry-set is
+   just the initial default state for that dataflow analysis. This is
+   less useful for understanding the error message output in these
+   tests.)
diff --git a/src/test/compile-fail/mir-dataflow/def-inits-1.rs b/src/test/compile-fail/mir-dataflow/def-inits-1.rs
new file mode 100644
index 00000000000..a133ddc15f1
--- /dev/null
+++ b/src/test/compile-fail/mir-dataflow/def-inits-1.rs
@@ -0,0 +1,63 @@
+// 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.
+
+// General test of maybe_uninits state computed by MIR dataflow.
+
+#![feature(rustc_attrs)]
+#![feature(stmt_expr_attributes)]
+
+use std::intrinsics::rustc_peek;
+use std::mem::{drop, replace};
+
+struct S(i32);
+
+#[rustc_mir_borrowck]
+#[rustc_mir(rustc_peek_definite_init,stop_after_dataflow)]
+fn foo(test: bool, x: &mut S, y: S, mut z: S) -> S {
+    let ret;
+    // `ret` starts off uninitialized
+    unsafe { rustc_peek(&ret); }  //~ ERROR rustc_peek: bit not set
+
+    // All function formal parameters start off initialized.
+
+    unsafe { rustc_peek(&x) };
+    unsafe { rustc_peek(&y) };
+    unsafe { rustc_peek(&z) };
+
+    ret = if test {
+        ::std::mem::replace(x, y)
+    } else {
+        z = y;
+        z
+    };
+
+    // `z` may be uninitialized here.
+    unsafe { rustc_peek(&z); } //~ ERROR rustc_peek: bit not set
+
+    // `y` is definitely uninitialized here.
+    unsafe { rustc_peek(&y); } //~ ERROR rustc_peek: bit not set
+
+    // `x` is still (definitely) initialized (replace above is a reborrow).
+    unsafe { rustc_peek(&x); }
+
+    ::std::mem::drop(x);
+
+    // `x` is *definitely* uninitialized here
+    unsafe { rustc_peek(&x); } //~ ERROR rustc_peek: bit not set
+
+    // `ret` is now definitely initialized (via `if` above).
+    unsafe { rustc_peek(&ret); }
+
+    ret
+}
+fn main() {
+    foo(true, &mut S(13), S(14), S(15));
+    foo(false, &mut S(13), S(14), S(15));
+}
diff --git a/src/test/compile-fail/mir-dataflow/inits-1.rs b/src/test/compile-fail/mir-dataflow/inits-1.rs
new file mode 100644
index 00000000000..949688098f6
--- /dev/null
+++ b/src/test/compile-fail/mir-dataflow/inits-1.rs
@@ -0,0 +1,65 @@
+// 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.
+
+// General test of maybe_inits state computed by MIR dataflow.
+
+#![feature(rustc_attrs)]
+#![feature(stmt_expr_attributes)]
+
+use std::intrinsics::rustc_peek;
+use std::mem::{drop, replace};
+
+struct S(i32);
+
+#[rustc_mir_borrowck]
+#[rustc_mir(rustc_peek_maybe_init,stop_after_dataflow)]
+fn foo(test: bool, x: &mut S, y: S, mut z: S) -> S {
+    let ret;
+    // `ret` starts off uninitialized, so we get an error report here.
+    unsafe { rustc_peek(&ret); }  //~ ERROR rustc_peek: bit not set
+
+    // All function formal parameters start off initialized.
+
+    unsafe { rustc_peek(&x) };
+    unsafe { rustc_peek(&y) };
+    unsafe { rustc_peek(&z) };
+
+    ret = if test {
+        ::std::mem::replace(x, y)
+    } else {
+        z = y;
+        z
+    };
+
+
+    // `z` may be initialized here.
+    unsafe { rustc_peek(&z); }
+
+    // `y` is definitely uninitialized here.
+    unsafe { rustc_peek(&y); }  //~ ERROR rustc_peek: bit not set
+
+    // `x` is still (definitely) initialized (replace above is a reborrow).
+    unsafe { rustc_peek(&x); }
+
+    ::std::mem::drop(x);
+
+    // `x` is *definitely* uninitialized here
+    unsafe { rustc_peek(&x); } //~ ERROR rustc_peek: bit not set
+
+    // `ret` is now definitely initialized (via `if` above).
+    unsafe { rustc_peek(&ret); }
+
+    ret
+}
+
+fn main() {
+    foo(true, &mut S(13), S(14), S(15));
+    foo(false, &mut S(13), S(14), S(15));
+}
diff --git a/src/test/compile-fail/mir-dataflow/uninits-1.rs b/src/test/compile-fail/mir-dataflow/uninits-1.rs
new file mode 100644
index 00000000000..c13daae24f3
--- /dev/null
+++ b/src/test/compile-fail/mir-dataflow/uninits-1.rs
@@ -0,0 +1,63 @@
+// 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.
+
+// General test of maybe_uninits state computed by MIR dataflow.
+
+#![feature(rustc_attrs)]
+#![feature(stmt_expr_attributes)]
+
+use std::intrinsics::rustc_peek;
+use std::mem::{drop, replace};
+
+struct S(i32);
+
+#[rustc_mir_borrowck]
+#[rustc_mir(rustc_peek_maybe_uninit,stop_after_dataflow)]
+fn foo(test: bool, x: &mut S, y: S, mut z: S) -> S {
+    let ret;
+    // `ret` starts off uninitialized
+    unsafe { rustc_peek(&ret); }
+
+    // All function formal parameters start off initialized.
+
+    unsafe { rustc_peek(&x) }; //~ ERROR rustc_peek: bit not set
+    unsafe { rustc_peek(&y) }; //~ ERROR rustc_peek: bit not set
+    unsafe { rustc_peek(&z) }; //~ ERROR rustc_peek: bit not set
+
+    ret = if test {
+        ::std::mem::replace(x, y)
+    } else {
+        z = y;
+        z
+    };
+
+    // `z` may be uninitialized here.
+    unsafe { rustc_peek(&z); }
+
+    // `y` is definitely uninitialized here.
+    unsafe { rustc_peek(&y); }
+
+    // `x` is still (definitely) initialized (replace above is a reborrow).
+    unsafe { rustc_peek(&x); } //~ ERROR rustc_peek: bit not set
+
+    ::std::mem::drop(x);
+
+    // `x` is *definitely* uninitialized here
+    unsafe { rustc_peek(&x); }
+
+    // `ret` is now definitely initialized (via `if` above).
+    unsafe { rustc_peek(&ret); } //~ ERROR rustc_peek: bit not set
+
+    ret
+}
+fn main() {
+    foo(true, &mut S(13), S(14), S(15));
+    foo(false, &mut S(13), S(14), S(15));
+}
diff --git a/src/test/compile-fail/mir-dataflow/uninits-2.rs b/src/test/compile-fail/mir-dataflow/uninits-2.rs
new file mode 100644
index 00000000000..e0bf4253449
--- /dev/null
+++ b/src/test/compile-fail/mir-dataflow/uninits-2.rs
@@ -0,0 +1,36 @@
+// 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.
+
+// General test of maybe_uninits state computed by MIR dataflow.
+
+#![feature(rustc_attrs)]
+#![feature(stmt_expr_attributes)]
+
+use std::intrinsics::rustc_peek;
+use std::mem::{drop, replace};
+
+struct S(i32);
+
+#[rustc_mir_borrowck]
+#[rustc_mir(rustc_peek_maybe_uninit,stop_after_dataflow)]
+fn foo(x: &mut S) {
+    // `x` is initialized here, so maybe-uninit bit is 0.
+
+    unsafe { *rustc_peek(&x) }; //~ ERROR rustc_peek: bit not set
+
+    ::std::mem::drop(x);
+
+    // `x` definitely uninitialized here, so maybe-uninit bit is 1.
+    unsafe { rustc_peek(&x) };
+}
+fn main() {
+    foo(&mut S(13));
+    foo(&mut S(13));
+}