`DefinitelyInitializedLvals` dataflow op (goal: move away from `MaybeUninitializedLvals`)

3 files changed, 220 insertions, 10 deletions

diff --git a/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs b/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs
index af31d929944..4cf739396e7 100644
--- a/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs
+++ b/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs
@@ -661,6 +661,53 @@ pub struct MaybeUninitializedLvals<'a, 'tcx: 'a> {
     phantom: PhantomData<Fn(&'a MoveData<'tcx>, TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>)>
 }
 
+/// `DefinitelyInitializedLvals` tracks all l-values that are definitely
+/// initialized upon reaching a particular point in the control flow
+/// for a function.
+///
+/// FIXME: Note that once flow-analysis is complete, this should be
+/// the set-complement of MaybeUninitializedLvals; thus we can get rid
+/// of one or the other of these two. I'm inclined to get rid of
+/// MaybeUninitializedLvals, simply because the sets will tend to be
+/// smaller in this analysis and thus easier for humans to process
+/// when debugging.
+///
+/// For example, in code like the following, we have corresponding
+/// dataflow information shown in the right-hand comments.
+///
+/// ```rust
+/// struct S;
+/// fn foo(pred: bool) {                       // definite-init:
+///                                            // {          }
+///     let a = S; let b = S; let c; let d;    // {a, b      }
+///
+///     if pred {
+///         drop(a);                           // {   b,     }
+///         b = S;                             // {   b,     }
+///
+///     } else {
+///         drop(b);                           // {a,        }
+///         d = S;                             // {a,       d}
+///
+///     }                                      // {          }
+///
+///     c = S;                                 // {       c  }
+/// }
+/// ```
+///
+/// To determine whether an l-value *may* be uninitialized at a
+/// particular control-flow point, one can take the set-complement
+/// of this data.
+///
+/// Similarly, at a given `drop` statement, the set-difference between
+/// this data and `MaybeInitializedLvals` yields the set of l-values
+/// that would require a dynamic drop-flag at that statement.
+#[derive(Debug, Default)]
+pub struct DefinitelyInitializedLvals<'a, 'tcx: 'a> {
+    // See "Note on PhantomData" above.
+    phantom: PhantomData<Fn(&'a MoveData<'tcx>, TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>)>
+}
+
 /// `MovingOutStatements` tracks the statements that perform moves out
 /// of particular l-values. More precisely, it tracks whether the
 /// *effect* of such moves (namely, the uninitialization of the
@@ -809,6 +856,23 @@ impl<'a, 'tcx> MaybeUninitializedLvals<'a, 'tcx> {
     }
 }
 
+impl<'a, 'tcx> DefinitelyInitializedLvals<'a, 'tcx> {
+    fn update_bits(sets: &mut BlockSets, path: MovePathIndex,
+                   state: super::DropFlagState)
+    {
+        match state {
+            DropFlagState::Dead => {
+                sets.gen_set.clear_bit(path.idx());
+                sets.kill_set.set_bit(path.idx());
+            }
+            DropFlagState::Live => {
+                sets.gen_set.set_bit(path.idx());
+                sets.kill_set.clear_bit(path.idx());
+            }
+        }
+    }
+}
+
 impl<'a, 'tcx> BitDenotation for MaybeInitializedLvals<'a, 'tcx> {
     type Bit = MovePath<'tcx>;
     type Ctxt = (TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>, MoveData<'tcx>);
@@ -940,6 +1004,72 @@ impl<'a, 'tcx> BitDenotation for MaybeUninitializedLvals<'a, 'tcx> {
     }
 }
 
+impl<'a, 'tcx> BitDenotation for DefinitelyInitializedLvals<'a, 'tcx> {
+    type Bit = MovePath<'tcx>;
+    type Ctxt = (TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>, MoveData<'tcx>);
+    fn name() -> &'static str { "definite_init" }
+    fn bits_per_block(&self, ctxt: &Self::Ctxt) -> usize {
+        ctxt.2.move_paths.len()
+    }
+    fn interpret<'c>(&self, ctxt: &'c Self::Ctxt, idx: usize) -> &'c Self::Bit {
+        &ctxt.2.move_paths[MovePathIndex::new(idx)]
+    }
+
+    // sets on_entry bits for Arg lvalues
+    fn start_block_effect(&self, ctxt: &Self::Ctxt, sets: &mut BlockSets) {
+        for e in &mut sets.on_entry[..] { *e = 0; }
+
+        super::drop_flag_effects_for_function_entry(
+            ctxt.0, ctxt.1, &ctxt.2,
+            |path, s| {
+                assert!(s == DropFlagState::Live);
+                sets.on_entry.set_bit(path.idx());
+            });
+    }
+
+    fn statement_effect(&self,
+                        ctxt: &Self::Ctxt,
+                        sets: &mut BlockSets,
+                        bb: repr::BasicBlock,
+                        idx: usize)
+    {
+        super::drop_flag_effects_for_location(
+            ctxt.0, ctxt.1, &ctxt.2,
+            Location { block: bb, index: idx },
+            |path, s| Self::update_bits(sets, path, s)
+        )
+    }
+
+    fn terminator_effect(&self,
+                         ctxt: &Self::Ctxt,
+                         sets: &mut BlockSets,
+                         bb: repr::BasicBlock,
+                         statements_len: usize)
+    {
+        super::drop_flag_effects_for_location(
+            ctxt.0, ctxt.1, &ctxt.2,
+            Location { block: bb, index: statements_len },
+            |path, s| Self::update_bits(sets, path, s)
+        )
+    }
+
+    fn propagate_call_return(&self,
+                             ctxt: &Self::Ctxt,
+                             in_out: &mut [usize],
+                             _call_bb: repr::BasicBlock,
+                             _dest_bb: repr::BasicBlock,
+                             dest_lval: &repr::Lvalue) {
+        // when a call returns successfully, that means we need to set
+        // the bits for that dest_lval to 1 (initialized).
+        let move_path_index = ctxt.2.rev_lookup.find(dest_lval);
+        super::on_all_children_bits(
+            ctxt.0, ctxt.1, &ctxt.2,
+            move_path_index,
+            |mpi| { in_out.set_bit(mpi.idx()); }
+        );
+    }
+}
+
 fn zero_to_one(bitvec: &mut [usize], move_index: MoveOutIndex) {
     let retval = bitvec.set_bit(move_index.idx());
     assert!(retval);
@@ -966,21 +1096,25 @@ impl<'a, 'tcx> BitwiseOperator for MaybeUninitializedLvals<'a, 'tcx> {
     }
 }
 
-// FIXME: I'm not sure it ever makes sense to use `true` for a
-// DataflowOperator::initial_value implementation, because: the way
-// that dataflow fixed point iteration works, you want to start at
-// bottom and work your way to a fixed point.
+impl<'a, 'tcx> BitwiseOperator for DefinitelyInitializedLvals<'a, 'tcx> {
+    #[inline]
+    fn join(&self, pred1: usize, pred2: usize) -> usize {
+        pred1 & pred2 // "definitely" means we intersect effects of both preds
+    }
+}
+
+// FIXME: `DataflowOperator::initial_value` should be named
+// `bottom_value`. The way that dataflow fixed point iteration works,
+// you want to start at bottom and work your way to a fixed point.
+// This needs to include the detail that the control-flow merges will
+// apply the `join` operator above to current state (which starts at
+// that bottom value).
 //
 // This means, for propagation across the graph, that you either want
 // to start at all-zeroes and then use Union as your merge when
 // propagating, or you start at all-ones and then use Intersect as
 // your merge when propagating.
-//
-// (An alternative could be, when propagating from Block A into block
-// B, to clear B's on_entry bits, and then iterate over all of B's
-// immediate predecessors. This would require storing on_exit state
-// for each block, however.)
-   
+
 impl<'a, 'tcx> DataflowOperator for MovingOutStatements<'a, 'tcx> {
     #[inline]
     fn initial_value() -> bool {
@@ -1002,6 +1136,13 @@ impl<'a, 'tcx> DataflowOperator for MaybeUninitializedLvals<'a, 'tcx> {
     }
 }
 
+impl<'a, 'tcx> DataflowOperator for DefinitelyInitializedLvals<'a, 'tcx> {
+    #[inline]
+    fn initial_value() -> bool {
+        true // bottom = initialized
+    }
+}
+
 #[inline]
 fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize],
                                in_vec: &[usize],
diff --git a/src/librustc_borrowck/borrowck/mir/mod.rs b/src/librustc_borrowck/borrowck/mir/mod.rs
index ce49e9fc93d..405647aec02 100644
--- a/src/librustc_borrowck/borrowck/mir/mod.rs
+++ b/src/librustc_borrowck/borrowck/mir/mod.rs
@@ -32,6 +32,7 @@ use self::dataflow::{BitDenotation};
 use self::dataflow::{Dataflow, DataflowAnalysis, DataflowResults};
 use self::dataflow::{HasMoveData};
 use self::dataflow::{MaybeInitializedLvals, MaybeUninitializedLvals};
+use self::dataflow::{DefinitelyInitializedLvals};
 use self::gather_moves::{MoveData, MovePathIndex, Location};
 use self::gather_moves::{MovePathContent};
 
@@ -78,6 +79,8 @@ pub fn borrowck_mir<'a, 'tcx: 'a>(
         do_dataflow(tcx, mir, id, attributes, ctxt, MaybeInitializedLvals::default());
     let (ctxt, flow_uninits) =
         do_dataflow(tcx, mir, id, attributes, ctxt, MaybeUninitializedLvals::default());
+    let (ctxt, flow_def_inits) =
+        do_dataflow(tcx, mir, id, attributes, ctxt, DefinitelyInitializedLvals::default());
 
     if has_rustc_mir_with(attributes, "rustc_peek_maybe_init").is_some() {
         dataflow::sanity_check_via_rustc_peek(bcx.tcx, mir, id, attributes, &ctxt, &flow_inits);
@@ -85,6 +88,9 @@ pub fn borrowck_mir<'a, 'tcx: 'a>(
     if has_rustc_mir_with(attributes, "rustc_peek_maybe_uninit").is_some() {
         dataflow::sanity_check_via_rustc_peek(bcx.tcx, mir, id, attributes, &ctxt, &flow_uninits);
     }
+    if has_rustc_mir_with(attributes, "rustc_peek_definite_init").is_some() {
+        dataflow::sanity_check_via_rustc_peek(bcx.tcx, mir, id, attributes, &ctxt, &flow_def_inits);
+    }
     let move_data = ctxt.2;
 
     if has_rustc_mir_with(attributes, "stop_after_dataflow").is_some() {
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));
+}