diff options
| -rw-r--r-- | src/librustc_borrowck/borrowck/mir/dataflow/impls.rs | 584 | ||||
| -rw-r--r-- | src/librustc_borrowck/borrowck/mir/dataflow/mod.rs | 573 |
2 files changed, 588 insertions, 569 deletions
diff --git a/src/librustc_borrowck/borrowck/mir/dataflow/impls.rs b/src/librustc_borrowck/borrowck/mir/dataflow/impls.rs new file mode 100644 index 00000000000..c9a23e3f288 --- /dev/null +++ b/src/librustc_borrowck/borrowck/mir/dataflow/impls.rs @@ -0,0 +1,584 @@ +// Copyright 2012-2016 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. + +use rustc::ty::TyCtxt; +use rustc::mir::repr::{self, Mir}; + +use super::super::gather_moves::{Location}; +use super::super::gather_moves::{MoveData, MoveOut, MoveOutIndex, MovePath, MovePathIndex}; +use super::super::DropFlagState; +use super::super::drop_flag_effects_for_function_entry; +use super::super::drop_flag_effects_for_location; +use super::super::on_all_children_bits; + +use super::{BitDenotation, BlockSets, DataflowOperator}; + +use bitslice::BitSlice; // adds set_bit/get_bit to &[usize] bitvector rep. +use bitslice::{BitwiseOperator}; +use indexed_set::{Idx, IdxSet}; + +use std::marker::PhantomData; + +// Dataflow analyses are built upon some interpretation of the +// bitvectors attached to each basic block, represented via a +// zero-sized structure. +// +// Note on PhantomData: Each interpretation will need to instantiate +// the `Bit` and `Ctxt` associated types, and in this case, those +// associated types need an associated lifetime `'tcx`. The +// interpretive structures are zero-sized, so they all need to carry a +// `PhantomData` representing how the structures relate to the `'tcx` +// lifetime. +// +// But, since all of the uses of `'tcx` are solely via instances of +// `Ctxt` that are passed into the `BitDenotation` methods, we can +// consistently use a `PhantomData` that is just a function over a +// `&Ctxt` (== `&MoveData<'tcx>). + +/// `MaybeInitializedLvals` tracks all l-values that might be +/// initialized upon reaching a particular point in the control flow +/// for a function. +/// +/// 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) { // maybe-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} +/// +/// } // {a, b, d} +/// +/// c = S; // {a, b, c, d} +/// } +/// ``` +/// +/// To determine whether an l-value *must* be initialized at a +/// particular control-flow point, one can take the set-difference +/// between this data and the data from `MaybeUninitializedLvals` at the +/// corresponding control-flow point. +/// +/// Similarly, at a given `drop` statement, the set-intersection +/// between this data and `MaybeUninitializedLvals` yields the set of +/// l-values that would require a dynamic drop-flag at that statement. +#[derive(Debug, Default)] +pub struct MaybeInitializedLvals<'a, 'tcx: 'a> { + // See "Note on PhantomData" above. + phantom: PhantomData<Fn(&'a MoveData<'tcx>, TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>)> +} + +/// `MaybeUninitializedLvals` tracks all l-values that might be +/// uninitialized upon reaching a particular point in the control flow +/// for a function. +/// +/// 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) { // maybe-uninit: +/// // {a, b, c, d} +/// let a = S; let b = S; let c; let d; // { c, d} +/// +/// if pred { +/// drop(a); // {a, c, d} +/// b = S; // {a, c, d} +/// +/// } else { +/// drop(b); // { b, c, d} +/// d = S; // { b, c } +/// +/// } // {a, b, c, d} +/// +/// c = S; // {a, b, d} +/// } +/// ``` +/// +/// To determine whether an l-value *must* be uninitialized at a +/// particular control-flow point, one can take the set-difference +/// between this data and the data from `MaybeInitializedLvals` at the +/// corresponding control-flow point. +/// +/// Similarly, at a given `drop` statement, the set-intersection +/// 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 MaybeUninitializedLvals<'a, 'tcx: 'a> { + // See "Note on PhantomData" above. + 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 +/// l-value in question) can reach some point in the control-flow of +/// the function, or if that effect is "killed" by some intervening +/// operation reinitializing that l-value. +/// +/// The resulting dataflow is a more enriched version of +/// `MaybeUninitializedLvals`. Both structures on their own only tell +/// you if an l-value *might* be uninitialized at a given point in the +/// control flow. But `MovingOutStatements` also includes the added +/// data of *which* particular statement causing the deinitialization +/// that the borrow checker's error meessage may need to report. +#[derive(Debug, Default)] +pub struct MovingOutStatements<'a, 'tcx: 'a> { + // See "Note on PhantomData" above. + phantom: PhantomData<Fn(&'a MoveData<'tcx>, TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>)> +} + +impl<'a, 'tcx> MaybeInitializedLvals<'a, 'tcx> { + fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex, + state: DropFlagState) + { + match state { + DropFlagState::Absent => sets.kill(&path), + DropFlagState::Present => sets.gen(&path), + } + } +} + +impl<'a, 'tcx> MaybeUninitializedLvals<'a, 'tcx> { + fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex, + state: DropFlagState) + { + match state { + DropFlagState::Absent => sets.gen(&path), + DropFlagState::Present => sets.kill(&path), + } + } +} + +impl<'a, 'tcx> DefinitelyInitializedLvals<'a, 'tcx> { + fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex, + state: DropFlagState) + { + match state { + DropFlagState::Absent => sets.kill(&path), + DropFlagState::Present => sets.gen(&path), + } + } +} + +impl<'a, 'tcx> BitDenotation for MaybeInitializedLvals<'a, 'tcx> { + type Idx = MovePathIndex; + type Bit = MovePath<'tcx>; + type Ctxt = (TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>, MoveData<'tcx>); + fn name() -> &'static str { "maybe_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)] + } + fn start_block_effect(&self, ctxt: &Self::Ctxt, sets: &mut BlockSets<MovePathIndex>) + { + drop_flag_effects_for_function_entry( + ctxt.0, ctxt.1, &ctxt.2, + |path, s| { + assert!(s == DropFlagState::Present); + sets.on_entry.add(&path); + }); + } + + fn statement_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MovePathIndex>, + bb: repr::BasicBlock, + idx: usize) + { + 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<MovePathIndex>, + bb: repr::BasicBlock, + statements_len: usize) + { + 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 IdxSet<MovePathIndex>, + _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_data = &ctxt.2; + let move_path_index = move_data.rev_lookup.find(dest_lval); + on_all_children_bits(ctxt.0, ctxt.1, &ctxt.2, + move_path_index, + |mpi| { in_out.add(&mpi); }); + } +} + +impl<'a, 'tcx> BitDenotation for MaybeUninitializedLvals<'a, 'tcx> { + type Idx = MovePathIndex; + type Bit = MovePath<'tcx>; + type Ctxt = (TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>, MoveData<'tcx>); + fn name() -> &'static str { "maybe_uninit" } + 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<MovePathIndex>) { + // set all bits to 1 (uninit) before gathering counterevidence + for e in sets.on_entry.words_mut() { *e = !0; } + + drop_flag_effects_for_function_entry( + ctxt.0, ctxt.1, &ctxt.2, + |path, s| { + assert!(s == DropFlagState::Present); + sets.on_entry.remove(&path); + }); + } + + fn statement_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MovePathIndex>, + bb: repr::BasicBlock, + idx: usize) + { + 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<MovePathIndex>, + bb: repr::BasicBlock, + statements_len: usize) + { + 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 IdxSet<MovePathIndex>, + _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); + on_all_children_bits(ctxt.0, ctxt.1, &ctxt.2, + move_path_index, + |mpi| { in_out.remove(&mpi); }); + } +} + +impl<'a, 'tcx> BitDenotation for DefinitelyInitializedLvals<'a, 'tcx> { + type Idx = MovePathIndex; + 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<MovePathIndex>) { + for e in sets.on_entry.words_mut() { *e = 0; } + + drop_flag_effects_for_function_entry( + ctxt.0, ctxt.1, &ctxt.2, + |path, s| { + assert!(s == DropFlagState::Present); + sets.on_entry.add(&path); + }); + } + + fn statement_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MovePathIndex>, + bb: repr::BasicBlock, + idx: usize) + { + 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<MovePathIndex>, + bb: repr::BasicBlock, + statements_len: usize) + { + 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 IdxSet<MovePathIndex>, + _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); + on_all_children_bits(ctxt.0, ctxt.1, &ctxt.2, + move_path_index, + |mpi| { in_out.add(&mpi); }); + } +} + +impl<'a, 'tcx> BitDenotation for MovingOutStatements<'a, 'tcx> { + type Idx = MoveOutIndex; + type Bit = MoveOut; + type Ctxt = (TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>, MoveData<'tcx>); + fn name() -> &'static str { "moving_out" } + fn bits_per_block(&self, ctxt: &Self::Ctxt) -> usize { + ctxt.2.moves.len() + } + fn interpret<'c>(&self, ctxt: &'c Self::Ctxt, idx: usize) -> &'c Self::Bit { + &ctxt.2.moves[idx] + } + fn start_block_effect(&self,_move_data: &Self::Ctxt, _sets: &mut BlockSets<MoveOutIndex>) { + // no move-statements have been executed prior to function + // execution, so this method has no effect on `_sets`. + } + fn statement_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MoveOutIndex>, + bb: repr::BasicBlock, + idx: usize) { + let &(tcx, mir, ref move_data) = ctxt; + let stmt = &mir.basic_block_data(bb).statements[idx]; + let loc_map = &move_data.loc_map; + let path_map = &move_data.path_map; + let rev_lookup = &move_data.rev_lookup; + + let loc = Location { block: bb, index: idx }; + debug!("stmt {:?} at loc {:?} moves out of move_indexes {:?}", + stmt, loc, &loc_map[loc]); + for move_index in &loc_map[loc] { + // Every path deinitialized by a *particular move* + // has corresponding bit, "gen'ed" (i.e. set) + // here, in dataflow vector + zero_to_one(sets.gen_set.words_mut(), *move_index); + } + let bits_per_block = self.bits_per_block(ctxt); + match stmt.kind { + repr::StatementKind::Assign(ref lvalue, _) => { + // assigning into this `lvalue` kills all + // MoveOuts from it, and *also* all MoveOuts + // for children and associated fragment sets. + let move_path_index = rev_lookup.find(lvalue); + on_all_children_bits(tcx, + mir, + move_data, + move_path_index, + |mpi| for moi in &path_map[mpi] { + assert!(moi.idx() < bits_per_block); + sets.kill_set.add(&moi); + }); + } + } + } + + fn terminator_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MoveOutIndex>, + bb: repr::BasicBlock, + statements_len: usize) + { + let &(_tcx, mir, ref move_data) = ctxt; + let term = mir.basic_block_data(bb).terminator.as_ref().unwrap(); + let loc_map = &move_data.loc_map; + let loc = Location { block: bb, index: statements_len }; + debug!("terminator {:?} at loc {:?} moves out of move_indexes {:?}", + term, loc, &loc_map[loc]); + let bits_per_block = self.bits_per_block(ctxt); + for move_index in &loc_map[loc] { + assert!(move_index.idx() < bits_per_block); + zero_to_one(sets.gen_set.words_mut(), *move_index); + } + } + + fn propagate_call_return(&self, + ctxt: &Self::Ctxt, + in_out: &mut IdxSet<MoveOutIndex>, + _call_bb: repr::BasicBlock, + _dest_bb: repr::BasicBlock, + dest_lval: &repr::Lvalue) { + let move_data = &ctxt.2; + let move_path_index = move_data.rev_lookup.find(dest_lval); + let bits_per_block = self.bits_per_block(ctxt); + + let path_map = &move_data.path_map; + on_all_children_bits(ctxt.0, + ctxt.1, + move_data, + move_path_index, + |mpi| for moi in &path_map[mpi] { + assert!(moi.idx() < bits_per_block); + in_out.remove(&moi); + }); + } +} + +fn zero_to_one(bitvec: &mut [usize], move_index: MoveOutIndex) { + let retval = bitvec.set_bit(move_index.idx()); + assert!(retval); +} + +impl<'a, 'tcx> BitwiseOperator for MovingOutStatements<'a, 'tcx> { + #[inline] + fn join(&self, pred1: usize, pred2: usize) -> usize { + pred1 | pred2 // moves from both preds are in scope + } +} + +impl<'a, 'tcx> BitwiseOperator for MaybeInitializedLvals<'a, 'tcx> { + #[inline] + fn join(&self, pred1: usize, pred2: usize) -> usize { + pred1 | pred2 // "maybe" means we union effects of both preds + } +} + +impl<'a, 'tcx> BitwiseOperator for MaybeUninitializedLvals<'a, 'tcx> { + #[inline] + fn join(&self, pred1: usize, pred2: usize) -> usize { + pred1 | pred2 // "maybe" means we union effects of both preds + } +} + +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 + } +} + +// The way that dataflow fixed point iteration works, you want to +// start at bottom and work your way to a fixed point. Control-flow +// merges will apply the `join` operator to each block entry's 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. + +impl<'a, 'tcx> DataflowOperator for MovingOutStatements<'a, 'tcx> { + #[inline] + fn bottom_value() -> bool { + false // bottom = no loans in scope by default + } +} + +impl<'a, 'tcx> DataflowOperator for MaybeInitializedLvals<'a, 'tcx> { + #[inline] + fn bottom_value() -> bool { + false // bottom = uninitialized + } +} + +impl<'a, 'tcx> DataflowOperator for MaybeUninitializedLvals<'a, 'tcx> { + #[inline] + fn bottom_value() -> bool { + false // bottom = initialized (start_block_effect counters this at outset) + } +} + +impl<'a, 'tcx> DataflowOperator for DefinitelyInitializedLvals<'a, 'tcx> { + #[inline] + fn bottom_value() -> bool { + true // bottom = initialized (start_block_effect counters this at outset) + } +} diff --git a/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs b/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs index e1459ad2abe..97e29fe064f 100644 --- a/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs +++ b/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs @@ -13,24 +13,23 @@ use rustc::mir::repr::{self, Mir}; use std::fmt::Debug; use std::io; -use std::marker::PhantomData; use std::mem; use std::path::PathBuf; use std::usize; use super::MirBorrowckCtxtPreDataflow; -use super::gather_moves::{Location, MoveData, MovePathIndex, MoveOutIndex}; -use super::gather_moves::{MoveOut, MovePath}; -use super::DropFlagState; +use super::gather_moves::{MoveData}; -use bitslice::BitSlice; // adds set_bit/get_bit to &[usize] bitvector rep. use bitslice::{bitwise, BitwiseOperator}; use indexed_set::{Idx, IdxSet, OwnIdxSet}; pub use self::sanity_check::sanity_check_via_rustc_peek; +pub use self::impls::{MaybeInitializedLvals, MaybeUninitializedLvals}; +pub use self::impls::{DefinitelyInitializedLvals, MovingOutStatements}; mod graphviz; mod sanity_check; +mod impls; pub trait Dataflow { fn dataflow(&mut self); @@ -550,567 +549,3 @@ impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> } } } - -// Dataflow analyses are built upon some interpretation of the -// bitvectors attached to each basic block, represented via a -// zero-sized structure. -// -// Note on PhantomData: Each interpretation will need to instantiate -// the `Bit` and `Ctxt` associated types, and in this case, those -// associated types need an associated lifetime `'tcx`. The -// interpretive structures are zero-sized, so they all need to carry a -// `PhantomData` representing how the structures relate to the `'tcx` -// lifetime. -// -// But, since all of the uses of `'tcx` are solely via instances of -// `Ctxt` that are passed into the `BitDenotation` methods, we can -// consistently use a `PhantomData` that is just a function over a -// `&Ctxt` (== `&MoveData<'tcx>). - -/// `MaybeInitializedLvals` tracks all l-values that might be -/// initialized upon reaching a particular point in the control flow -/// for a function. -/// -/// 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) { // maybe-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} -/// -/// } // {a, b, d} -/// -/// c = S; // {a, b, c, d} -/// } -/// ``` -/// -/// To determine whether an l-value *must* be initialized at a -/// particular control-flow point, one can take the set-difference -/// between this data and the data from `MaybeUninitializedLvals` at the -/// corresponding control-flow point. -/// -/// Similarly, at a given `drop` statement, the set-intersection -/// between this data and `MaybeUninitializedLvals` yields the set of -/// l-values that would require a dynamic drop-flag at that statement. -#[derive(Debug, Default)] -pub struct MaybeInitializedLvals<'a, 'tcx: 'a> { - // See "Note on PhantomData" above. - phantom: PhantomData<Fn(&'a MoveData<'tcx>, TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>)> -} - -/// `MaybeUninitializedLvals` tracks all l-values that might be -/// uninitialized upon reaching a particular point in the control flow -/// for a function. -/// -/// 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) { // maybe-uninit: -/// // {a, b, c, d} -/// let a = S; let b = S; let c; let d; // { c, d} -/// -/// if pred { -/// drop(a); // {a, c, d} -/// b = S; // {a, c, d} -/// -/// } else { -/// drop(b); // { b, c, d} -/// d = S; // { b, c } -/// -/// } // {a, b, c, d} -/// -/// c = S; // {a, b, d} -/// } -/// ``` -/// -/// To determine whether an l-value *must* be uninitialized at a -/// particular control-flow point, one can take the set-difference -/// between this data and the data from `MaybeInitializedLvals` at the -/// corresponding control-flow point. -/// -/// Similarly, at a given `drop` statement, the set-intersection -/// 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 MaybeUninitializedLvals<'a, 'tcx: 'a> { - // See "Note on PhantomData" above. - 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 -/// l-value in question) can reach some point in the control-flow of -/// the function, or if that effect is "killed" by some intervening -/// operation reinitializing that l-value. -/// -/// The resulting dataflow is a more enriched version of -/// `MaybeUninitializedLvals`. Both structures on their own only tell -/// you if an l-value *might* be uninitialized at a given point in the -/// control flow. But `MovingOutStatements` also includes the added -/// data of *which* particular statement causing the deinitialization -/// that the borrow checker's error meessage may need to report. -#[derive(Debug, Default)] -pub struct MovingOutStatements<'a, 'tcx: 'a> { - // See "Note on PhantomData" above. - phantom: PhantomData<Fn(&'a MoveData<'tcx>, TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>)> -} - -impl<'a, 'tcx> BitDenotation for MovingOutStatements<'a, 'tcx> { - type Idx = MoveOutIndex; - type Bit = MoveOut; - type Ctxt = (TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>, MoveData<'tcx>); - fn name() -> &'static str { "moving_out" } - fn bits_per_block(&self, ctxt: &Self::Ctxt) -> usize { - ctxt.2.moves.len() - } - fn interpret<'c>(&self, ctxt: &'c Self::Ctxt, idx: usize) -> &'c Self::Bit { - &ctxt.2.moves[idx] - } - fn start_block_effect(&self,_move_data: &Self::Ctxt, _sets: &mut BlockSets<MoveOutIndex>) { - // no move-statements have been executed prior to function - // execution, so this method has no effect on `_sets`. - } - fn statement_effect(&self, - ctxt: &Self::Ctxt, - sets: &mut BlockSets<MoveOutIndex>, - bb: repr::BasicBlock, - idx: usize) { - let &(tcx, mir, ref move_data) = ctxt; - let stmt = &mir.basic_block_data(bb).statements[idx]; - let loc_map = &move_data.loc_map; - let path_map = &move_data.path_map; - let rev_lookup = &move_data.rev_lookup; - - let loc = Location { block: bb, index: idx }; - debug!("stmt {:?} at loc {:?} moves out of move_indexes {:?}", - stmt, loc, &loc_map[loc]); - for move_index in &loc_map[loc] { - // Every path deinitialized by a *particular move* - // has corresponding bit, "gen'ed" (i.e. set) - // here, in dataflow vector - zero_to_one(sets.gen_set.words_mut(), *move_index); - } - let bits_per_block = self.bits_per_block(ctxt); - match stmt.kind { - repr::StatementKind::Assign(ref lvalue, _) => { - // assigning into this `lvalue` kills all - // MoveOuts from it, and *also* all MoveOuts - // for children and associated fragment sets. - let move_path_index = rev_lookup.find(lvalue); - super::on_all_children_bits(tcx, - mir, - move_data, - move_path_index, - |mpi| for moi in &path_map[mpi] { - assert!(moi.idx() < bits_per_block); - sets.kill_set.add(&moi); - }); - } - } - } - - fn terminator_effect(&self, - ctxt: &Self::Ctxt, - sets: &mut BlockSets<MoveOutIndex>, - bb: repr::BasicBlock, - statements_len: usize) - { - let &(_tcx, mir, ref move_data) = ctxt; - let term = mir.basic_block_data(bb).terminator.as_ref().unwrap(); - let loc_map = &move_data.loc_map; - let loc = Location { block: bb, index: statements_len }; - debug!("terminator {:?} at loc {:?} moves out of move_indexes {:?}", - term, loc, &loc_map[loc]); - let bits_per_block = self.bits_per_block(ctxt); - for move_index in &loc_map[loc] { - assert!(move_index.idx() < bits_per_block); - zero_to_one(sets.gen_set.words_mut(), *move_index); - } - } - - fn propagate_call_return(&self, - ctxt: &Self::Ctxt, - in_out: &mut IdxSet<MoveOutIndex>, - _call_bb: repr::BasicBlock, - _dest_bb: repr::BasicBlock, - dest_lval: &repr::Lvalue) { - let move_data = &ctxt.2; - let move_path_index = move_data.rev_lookup.find(dest_lval); - let bits_per_block = self.bits_per_block(ctxt); - - let path_map = &move_data.path_map; - super::on_all_children_bits(ctxt.0, - ctxt.1, - move_data, - move_path_index, - |mpi| for moi in &path_map[mpi] { - assert!(moi.idx() < bits_per_block); - in_out.remove(&moi); - }); - } -} - -impl<'a, 'tcx> MaybeInitializedLvals<'a, 'tcx> { - fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex, - state: super::DropFlagState) - { - match state { - DropFlagState::Absent => sets.kill(&path), - DropFlagState::Present => sets.gen(&path), - } - } -} - -impl<'a, 'tcx> MaybeUninitializedLvals<'a, 'tcx> { - fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex, - state: super::DropFlagState) - { - match state { - DropFlagState::Absent => sets.gen(&path), - DropFlagState::Present => sets.kill(&path), - } - } -} - -impl<'a, 'tcx> DefinitelyInitializedLvals<'a, 'tcx> { - fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex, - state: super::DropFlagState) - { - match state { - DropFlagState::Absent => sets.kill(&path), - DropFlagState::Present => sets.gen(&path), - } - } -} - -impl<'a, 'tcx> BitDenotation for MaybeInitializedLvals<'a, 'tcx> { - type Idx = MovePathIndex; - type Bit = MovePath<'tcx>; - type Ctxt = (TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>, MoveData<'tcx>); - fn name() -> &'static str { "maybe_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)] - } - fn start_block_effect(&self, ctxt: &Self::Ctxt, sets: &mut BlockSets<MovePathIndex>) - { - super::drop_flag_effects_for_function_entry( - ctxt.0, ctxt.1, &ctxt.2, - |path, s| { - assert!(s == DropFlagState::Present); - sets.on_entry.add(&path); - }); - } - - fn statement_effect(&self, - ctxt: &Self::Ctxt, - sets: &mut BlockSets<MovePathIndex>, - 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<MovePathIndex>, - 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 IdxSet<MovePathIndex>, - _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_data = &ctxt.2; - let move_path_index = move_data.rev_lookup.find(dest_lval); - super::on_all_children_bits( - ctxt.0, ctxt.1, &ctxt.2, - move_path_index, - |mpi| { in_out.add(&mpi); } - ); - } -} - -impl<'a, 'tcx> BitDenotation for MaybeUninitializedLvals<'a, 'tcx> { - type Idx = MovePathIndex; - type Bit = MovePath<'tcx>; - type Ctxt = (TyCtxt<'a, 'tcx, 'tcx>, &'a Mir<'tcx>, MoveData<'tcx>); - fn name() -> &'static str { "maybe_uninit" } - 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<MovePathIndex>) { - // set all bits to 1 (uninit) before gathering counterevidence - for e in sets.on_entry.words_mut() { *e = !0; } - - super::drop_flag_effects_for_function_entry( - ctxt.0, ctxt.1, &ctxt.2, - |path, s| { - assert!(s == DropFlagState::Present); - sets.on_entry.remove(&path); - }); - } - - fn statement_effect(&self, - ctxt: &Self::Ctxt, - sets: &mut BlockSets<MovePathIndex>, - 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<MovePathIndex>, - 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 IdxSet<MovePathIndex>, - _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.remove(&mpi); } - ); - } -} - -impl<'a, 'tcx> BitDenotation for DefinitelyInitializedLvals<'a, 'tcx> { - type Idx = MovePathIndex; - 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<MovePathIndex>) { - for e in sets.on_entry.words_mut() { *e = 0; } - - super::drop_flag_effects_for_function_entry( - ctxt.0, ctxt.1, &ctxt.2, - |path, s| { - assert!(s == DropFlagState::Present); - sets.on_entry.add(&path); - }); - } - - fn statement_effect(&self, - ctxt: &Self::Ctxt, - sets: &mut BlockSets<MovePathIndex>, - 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<MovePathIndex>, - 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 IdxSet<MovePathIndex>, - _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.add(&mpi); } - ); - } -} - -fn zero_to_one(bitvec: &mut [usize], move_index: MoveOutIndex) { - let retval = bitvec.set_bit(move_index.idx()); - assert!(retval); -} - -impl<'a, 'tcx> BitwiseOperator for MovingOutStatements<'a, 'tcx> { - #[inline] - fn join(&self, pred1: usize, pred2: usize) -> usize { - pred1 | pred2 // moves from both preds are in scope - } -} - -impl<'a, 'tcx> BitwiseOperator for MaybeInitializedLvals<'a, 'tcx> { - #[inline] - fn join(&self, pred1: usize, pred2: usize) -> usize { - pred1 | pred2 // "maybe" means we union effects of both preds - } -} - -impl<'a, 'tcx> BitwiseOperator for MaybeUninitializedLvals<'a, 'tcx> { - #[inline] - fn join(&self, pred1: usize, pred2: usize) -> usize { - pred1 | pred2 // "maybe" means we union effects of both preds - } -} - -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 - } -} - -// The way that dataflow fixed point iteration works, you want to -// start at bottom and work your way to a fixed point. Control-flow -// merges will apply the `join` operator to each block entry's 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. - -impl<'a, 'tcx> DataflowOperator for MovingOutStatements<'a, 'tcx> { - #[inline] - fn bottom_value() -> bool { - false // bottom = no loans in scope by default - } -} - -impl<'a, 'tcx> DataflowOperator for MaybeInitializedLvals<'a, 'tcx> { - #[inline] - fn bottom_value() -> bool { - false // bottom = uninitialized - } -} - -impl<'a, 'tcx> DataflowOperator for MaybeUninitializedLvals<'a, 'tcx> { - #[inline] - fn bottom_value() -> bool { - false // bottom = initialized (start_block_effect counters this at outset) - } -} - -impl<'a, 'tcx> DataflowOperator for DefinitelyInitializedLvals<'a, 'tcx> { - #[inline] - fn bottom_value() -> bool { - true // bottom = initialized - } -} - |