src/librustc_mir/borrow_check/nll/type_check/liveness.rs

   1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use borrow_check::nll::region_infer::Cause;
  12 use borrow_check::nll::type_check::AtLocation;
  13 use dataflow::move_paths::{HasMoveData, MoveData};
  14 use dataflow::MaybeInitializedPlaces;
  15 use dataflow::{FlowAtLocation, FlowsAtLocation};
  16 use rustc::infer::canonical::QueryRegionConstraint;
  17 use rustc::mir::Local;
  18 use rustc::mir::{BasicBlock, Location, Mir};
  19 use rustc::traits::query::dropck_outlives::DropckOutlivesResult;
  20 use rustc::traits::query::type_op::outlives::DropckOutlives;
  21 use rustc::traits::query::type_op::TypeOp;
  22 use rustc::ty::{Ty, TypeFoldable};
  23 use rustc_data_structures::fx::FxHashMap;
  24 use std::rc::Rc;
  25 use util::liveness::LivenessResults;
  26
  27 use super::TypeChecker;
  28
  29 /// Combines liveness analysis with initialization analysis to
  30 /// determine which variables are live at which points, both due to
  31 /// ordinary uses and drops. Returns a set of (ty, location) pairs
  32 /// that indicate which types must be live at which point in the CFG.
  33 /// This vector is consumed by `constraint_generation`.
  34 ///
  35 /// NB. This computation requires normalization; therefore, it must be
  36 /// performed before
  37 pub(super) fn generate<'gcx, 'tcx>(
  38     cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
  39     mir: &Mir<'tcx>,
  40     liveness: &LivenessResults,
  41     flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>,
  42     move_data: &MoveData<'tcx>,
  43 ) {
  44     let mut generator = TypeLivenessGenerator {
  45         cx,
  46         mir,
  47         liveness,
  48         flow_inits,
  49         move_data,
  50         drop_data: FxHashMap(),
  51     };
  52
  53     for bb in mir.basic_blocks().indices() {
  54         generator.add_liveness_constraints(bb);
  55     }
  56 }
  57
  58 struct TypeLivenessGenerator<'gen, 'typeck, 'flow, 'gcx, 'tcx>
  59 where
  60     'typeck: 'gen,
  61     'flow: 'gen,
  62     'tcx: 'typeck + 'flow,
  63     'gcx: 'tcx,
  64 {
  65     cx: &'gen mut TypeChecker<'typeck, 'gcx, 'tcx>,
  66     mir: &'gen Mir<'tcx>,
  67     liveness: &'gen LivenessResults,
  68     flow_inits: &'gen mut FlowAtLocation<MaybeInitializedPlaces<'flow, 'gcx, 'tcx>>,
  69     move_data: &'gen MoveData<'tcx>,
  70     drop_data: FxHashMap<Ty<'tcx>, DropData<'tcx>>,
  71 }
  72
  73 struct DropData<'tcx> {
  74     dropck_result: DropckOutlivesResult<'tcx>,
  75     region_constraint_data: Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>,
  76 }
  77
  78 impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flow, 'gcx, 'tcx> {
  79     /// Liveness constraints:
  80     ///
  81     /// > If a variable V is live at point P, then all regions R in the type of V
  82     /// > must include the point P.
  83     fn add_liveness_constraints(&mut self, bb: BasicBlock) {
  84         debug!("add_liveness_constraints(bb={:?})", bb);
  85
  86         self.liveness
  87             .regular
  88             .simulate_block(self.mir, bb, |location, live_locals| {
  89                 for live_local in live_locals.iter() {
  90                     let live_local_ty = self.mir.local_decls[live_local].ty;
  91                     let cause = Cause::LiveVar(live_local, location);
  92                     Self::push_type_live_constraint(&mut self.cx, live_local_ty, location, cause);
  93                 }
  94             });
  95
  96         let mut all_live_locals: Vec<(Location, Vec<Local>)> = vec![];
  97         self.liveness
  98             .drop
  99             .simulate_block(self.mir, bb, |location, live_locals| {
 100                 all_live_locals.push((location, live_locals.iter().collect()));
 101             });
 102         debug!(
 103             "add_liveness_constraints: all_live_locals={:#?}",
 104             all_live_locals
 105         );
 106
 107         let terminator_index = self.mir.basic_blocks()[bb].statements.len();
 108         self.flow_inits.reset_to_entry_of(bb);
 109         while let Some((location, live_locals)) = all_live_locals.pop() {
 110             for live_local in live_locals {
 111                 debug!(
 112                     "add_liveness_constraints: location={:?} live_local={:?}",
 113                     location, live_local
 114                 );
 115
 116                 if log_enabled!(::log::Level::Debug) {
 117                     self.flow_inits.each_state_bit(|mpi_init| {
 118                         debug!(
 119                             "add_liveness_constraints: location={:?} initialized={:?}",
 120                             location,
 121                             &self.flow_inits.operator().move_data().move_paths[mpi_init]
 122                         );
 123                     });
 124                 }
 125
 126                 let mpi = self.move_data.rev_lookup.find_local(live_local);
 127                 if let Some(initialized_child) = self.flow_inits.has_any_child_of(mpi) {
 128                     debug!(
 129                         "add_liveness_constraints: mpi={:?} has initialized child {:?}",
 130                         self.move_data.move_paths[mpi],
 131                         self.move_data.move_paths[initialized_child]
 132                     );
 133
 134                     let live_local_ty = self.mir.local_decls[live_local].ty;
 135                     self.add_drop_live_constraint(live_local, live_local_ty, location);
 136                 }
 137             }
 138
 139             if location.statement_index == terminator_index {
 140                 debug!(
 141                     "add_liveness_constraints: reconstruct_terminator_effect from {:#?}",
 142                     location
 143                 );
 144                 self.flow_inits.reconstruct_terminator_effect(location);
 145             } else {
 146                 debug!(
 147                     "add_liveness_constraints: reconstruct_statement_effect from {:#?}",
 148                     location
 149                 );
 150                 self.flow_inits.reconstruct_statement_effect(location);
 151             }
 152             self.flow_inits.apply_local_effect(location);
 153         }
 154     }
 155
 156     /// Some variable with type `live_ty` is "regular live" at
 157     /// `location` -- i.e., it may be used later. This means that all
 158     /// regions appearing in the type `live_ty` must be live at
 159     /// `location`.
 160     fn push_type_live_constraint<T>(
 161         cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
 162         value: T,
 163         location: Location,
 164         cause: Cause,
 165     ) where
 166         T: TypeFoldable<'tcx>,
 167     {
 168         debug!(
 169             "push_type_live_constraint(live_ty={:?}, location={:?})",
 170             value, location
 171         );
 172
 173         cx.tcx().for_each_free_region(&value, |live_region| {
 174             cx.constraints
 175                 .liveness_set
 176                 .push((live_region, location, cause.clone()));
 177         });
 178     }
 179
 180     /// Some variable with type `live_ty` is "drop live" at `location`
 181     /// -- i.e., it may be dropped later. This means that *some* of
 182     /// the regions in its type must be live at `location`. The
 183     /// precise set will depend on the dropck constraints, and in
 184     /// particular this takes `#[may_dangle]` into account.
 185     fn add_drop_live_constraint(
 186         &mut self,
 187         dropped_local: Local,
 188         dropped_ty: Ty<'tcx>,
 189         location: Location,
 190     ) {
 191         debug!(
 192             "add_drop_live_constraint(dropped_local={:?}, dropped_ty={:?}, location={:?})",
 193             dropped_local, dropped_ty, location
 194         );
 195
 196         let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({
 197             let cx = &mut self.cx;
 198             move || Self::compute_drop_data(cx, dropped_ty)
 199         });
 200
 201         if let Some(data) = &drop_data.region_constraint_data {
 202             self.cx.push_region_constraints(location.boring(), data);
 203         }
 204
 205         drop_data.dropck_result.report_overflows(
 206             self.cx.infcx.tcx,
 207             self.mir.source_info(location).span,
 208             dropped_ty,
 209         );
 210
 211         // All things in the `outlives` array may be touched by
 212         // the destructor and must be live at this point.
 213         let cause = Cause::DropVar(dropped_local, location);
 214         for &kind in &drop_data.dropck_result.kinds {
 215             Self::push_type_live_constraint(&mut self.cx, kind, location, cause);
 216         }
 217     }
 218
 219     fn compute_drop_data(
 220         cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
 221         dropped_ty: Ty<'tcx>,
 222     ) -> DropData<'tcx> {
 223         debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,);
 224
 225         let param_env = cx.param_env;
 226         let (dropck_result, region_constraint_data) = param_env
 227             .and(DropckOutlives::new(dropped_ty))
 228             .fully_perform(cx.infcx)
 229             .unwrap();
 230
 231         DropData {
 232             dropck_result,
 233             region_constraint_data,
 234         }
 235     }
 236 }