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