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 rustc_data_structures::indexed_vec::Idx;
  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, V: Idx>(
  38     cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
  39     mir: &Mir<'tcx>,
  40     liveness: &LivenessResults<V>,
  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, V>
  59 where
  60     'typeck: 'gen,
  61     'flow: 'gen,
  62     'tcx: 'typeck + 'flow,
  63     'gcx: 'tcx,
  64     V: Idx + 'gen,
  65 {
  66     cx: &'gen mut TypeChecker<'typeck, 'gcx, 'tcx>,
  67     mir: &'gen Mir<'tcx>,
  68     liveness: &'gen LivenessResults<V>,
  69     flow_inits: &'gen mut FlowAtLocation<MaybeInitializedPlaces<'flow, 'gcx, 'tcx>>,
  70     move_data: &'gen MoveData<'tcx>,
  71     drop_data: FxHashMap<Ty<'tcx>, DropData<'tcx>>,
  72 }
  73
  74 struct DropData<'tcx> {
  75     dropck_result: DropckOutlivesResult<'tcx>,
  76     region_constraint_data: Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>,
  77 }
  78
  79 impl<'gen, 'typeck, 'flow, 'gcx, 'tcx, V: Idx> TypeLivenessGenerator<'gen, 'typeck, 'flow, 'gcx, 'tcx, V> {
  80     /// Liveness constraints:
  81     ///
  82     /// > If a variable V is live at point P, then all regions R in the type of V
  83     /// > must include the point P.
  84     fn add_liveness_constraints(&mut self, bb: BasicBlock) {
  85         debug!("add_liveness_constraints(bb={:?})", bb);
  86
  87         self.liveness
  88             .regular
  89             .simulate_block(self.mir, bb, |location, live_locals| {
  90                 for live_local in live_locals.iter() {
  91                     let live_local_ty = self.mir.local_decls[live_local].ty;
  92                     Self::push_type_live_constraint(&mut self.cx, live_local_ty, location);
  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     ) where
 165         T: TypeFoldable<'tcx>,
 166     {
 167         debug!(
 168             "push_type_live_constraint(live_ty={:?}, location={:?})",
 169             value, location
 170         );
 171
 172         cx.tcx().for_each_free_region(&value, |live_region| {
 173             if let Some(ref mut borrowck_context) = cx.borrowck_context {
 174                 let region_vid = borrowck_context.universal_regions.to_region_vid(live_region);
 175                 borrowck_context.constraints.liveness_constraints.add_element(region_vid, location);
 176
 177                 if let Some(all_facts) = borrowck_context.all_facts {
 178                     let start_index = borrowck_context.location_table.start_index(location);
 179                     all_facts.region_live_at.push((region_vid, start_index));
 180
 181                     let mid_index = borrowck_context.location_table.mid_index(location);
 182                     all_facts.region_live_at.push((region_vid, mid_index));
 183                 }
 184             }
 185         });
 186     }
 187
 188     /// Some variable with type `live_ty` is "drop live" at `location`
 189     /// -- i.e., it may be dropped later. This means that *some* of
 190     /// the regions in its type must be live at `location`. The
 191     /// precise set will depend on the dropck constraints, and in
 192     /// particular this takes `#[may_dangle]` into account.
 193     fn add_drop_live_constraint(
 194         &mut self,
 195         dropped_local: Local,
 196         dropped_ty: Ty<'tcx>,
 197         location: Location,
 198     ) {
 199         debug!(
 200             "add_drop_live_constraint(dropped_local={:?}, dropped_ty={:?}, location={:?})",
 201             dropped_local, dropped_ty, location
 202         );
 203
 204         let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({
 205             let cx = &mut self.cx;
 206             move || Self::compute_drop_data(cx, dropped_ty)
 207         });
 208
 209         if let Some(data) = &drop_data.region_constraint_data {
 210             self.cx.push_region_constraints(location.boring(), data);
 211         }
 212
 213         drop_data.dropck_result.report_overflows(
 214             self.cx.infcx.tcx,
 215             self.mir.source_info(location).span,
 216             dropped_ty,
 217         );
 218
 219         // All things in the `outlives` array may be touched by
 220         // the destructor and must be live at this point.
 221         for &kind in &drop_data.dropck_result.kinds {
 222             Self::push_type_live_constraint(&mut self.cx, kind, location);
 223         }
 224     }
 225
 226     fn compute_drop_data(
 227         cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
 228         dropped_ty: Ty<'tcx>,
 229     ) -> DropData<'tcx> {
 230         debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,);
 231
 232         let param_env = cx.param_env;
 233         let (dropck_result, region_constraint_data) = param_env
 234             .and(DropckOutlives::new(dropped_ty))
 235             .fully_perform(cx.infcx)
 236             .unwrap();
 237
 238         DropData {
 239             dropck_result,
 240             region_constraint_data,
 241         }
 242     }
 243 }