src/librustc_mir/borrow_check/constraint_generation.rs

   1 use rustc::infer::InferCtxt;
   2 use rustc::mir::visit::TyContext;
   3 use rustc::mir::visit::Visitor;
   4 use rustc::mir::{
   5     BasicBlock, BasicBlockData, Body, Local, Location, Place, PlaceBase, PlaceRef, ProjectionElem,
   6     Rvalue, SourceInfo, Statement, StatementKind, Terminator, TerminatorKind, UserTypeProjection,
   7 };
   8 use rustc::ty::fold::TypeFoldable;
   9 use rustc::ty::{self, RegionVid, Ty};
  10 use rustc::ty::subst::SubstsRef;
  11
  12 use crate::borrow_check::{
  13     borrow_set::BorrowSet,
  14     location::LocationTable,
  15     nll::ToRegionVid,
  16     facts::AllFacts,
  17     region_infer::values::LivenessValues,
  18     places_conflict,
  19 };
  20
  21 pub(super) fn generate_constraints<'cx, 'tcx>(
  22     infcx: &InferCtxt<'cx, 'tcx>,
  23     param_env: ty::ParamEnv<'tcx>,
  24     liveness_constraints: &mut LivenessValues<RegionVid>,
  25     all_facts: &mut Option<AllFacts>,
  26     location_table: &LocationTable,
  27     body: &Body<'tcx>,
  28     borrow_set: &BorrowSet<'tcx>,
  29 ) {
  30     let mut cg = ConstraintGeneration {
  31         borrow_set,
  32         infcx,
  33         liveness_constraints,
  34         location_table,
  35         all_facts,
  36         body,
  37         param_env,
  38     };
  39
  40     for (bb, data) in body.basic_blocks().iter_enumerated() {
  41         cg.visit_basic_block_data(bb, data);
  42     }
  43 }
  44
  45 /// 'cg = the duration of the constraint generation process itself.
  46 struct ConstraintGeneration<'cg, 'cx, 'tcx> {
  47     infcx: &'cg InferCtxt<'cx, 'tcx>,
  48     param_env: ty::ParamEnv<'tcx>,
  49     all_facts: &'cg mut Option<AllFacts>,
  50     location_table: &'cg LocationTable,
  51     liveness_constraints: &'cg mut LivenessValues<RegionVid>,
  52     borrow_set: &'cg BorrowSet<'tcx>,
  53     body: &'cg Body<'tcx>,
  54 }
  55
  56 impl<'cg, 'cx, 'tcx> Visitor<'tcx> for ConstraintGeneration<'cg, 'cx, 'tcx> {
  57     fn visit_basic_block_data(&mut self, bb: BasicBlock, data: &BasicBlockData<'tcx>) {
  58         self.super_basic_block_data(bb, data);
  59     }
  60
  61     /// We sometimes have `substs` within an rvalue, or within a
  62     /// call. Make them live at the location where they appear.
  63     fn visit_substs(&mut self, substs: &SubstsRef<'tcx>, location: Location) {
  64         self.add_regular_live_constraint(*substs, location);
  65         self.super_substs(substs);
  66     }
  67
  68     /// We sometimes have `region` within an rvalue, or within a
  69     /// call. Make them live at the location where they appear.
  70     fn visit_region(&mut self, region: &ty::Region<'tcx>, location: Location) {
  71         self.add_regular_live_constraint(*region, location);
  72         self.super_region(region);
  73     }
  74
  75     /// We sometimes have `ty` within an rvalue, or within a
  76     /// call. Make them live at the location where they appear.
  77     fn visit_ty(&mut self, ty: Ty<'tcx>, ty_context: TyContext) {
  78         match ty_context {
  79             TyContext::ReturnTy(SourceInfo { span, .. })
  80             | TyContext::YieldTy(SourceInfo { span, .. })
  81             | TyContext::UserTy(span)
  82             | TyContext::LocalDecl { source_info: SourceInfo { span, .. }, .. } => {
  83                 span_bug!(
  84                     span,
  85                     "should not be visiting outside of the CFG: {:?}",
  86                     ty_context
  87                 );
  88             }
  89             TyContext::Location(location) => {
  90                 self.add_regular_live_constraint(ty, location);
  91             }
  92         }
  93
  94         self.super_ty(ty);
  95     }
  96
  97     fn visit_statement(
  98         &mut self,
  99         statement: &Statement<'tcx>,
 100         location: Location,
 101     ) {
 102         if let Some(all_facts) = self.all_facts {
 103             let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation");
 104             all_facts.cfg_edge.push((
 105                 self.location_table.start_index(location),
 106                 self.location_table.mid_index(location),
 107             ));
 108
 109             all_facts.cfg_edge.push((
 110                 self.location_table.mid_index(location),
 111                 self.location_table
 112                     .start_index(location.successor_within_block()),
 113             ));
 114
 115             // If there are borrows on this now dead local, we need to record them as `killed`.
 116             if let StatementKind::StorageDead(ref local) = statement.kind {
 117                 record_killed_borrows_for_local(
 118                     all_facts,
 119                     self.borrow_set,
 120                     self.location_table,
 121                     local,
 122                     location,
 123                 );
 124             }
 125         }
 126
 127         self.super_statement(statement, location);
 128     }
 129
 130     fn visit_assign(
 131         &mut self,
 132         place: &Place<'tcx>,
 133         rvalue: &Rvalue<'tcx>,
 134         location: Location,
 135     ) {
 136         // When we see `X = ...`, then kill borrows of
 137         // `(*X).foo` and so forth.
 138         self.record_killed_borrows_for_place(place, location);
 139
 140         self.super_assign(place, rvalue, location);
 141     }
 142
 143     fn visit_terminator(
 144         &mut self,
 145         terminator: &Terminator<'tcx>,
 146         location: Location,
 147     ) {
 148         if let Some(all_facts) = self.all_facts {
 149             let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation");
 150             all_facts.cfg_edge.push((
 151                 self.location_table.start_index(location),
 152                 self.location_table.mid_index(location),
 153             ));
 154
 155             let successor_blocks = terminator.successors();
 156             all_facts.cfg_edge.reserve(successor_blocks.size_hint().0);
 157             for successor_block in successor_blocks {
 158                 all_facts.cfg_edge.push((
 159                     self.location_table.mid_index(location),
 160                     self.location_table
 161                         .start_index(successor_block.start_location()),
 162                 ));
 163             }
 164         }
 165
 166         // A `Call` terminator's return value can be a local which has borrows,
 167         // so we need to record those as `killed` as well.
 168         if let TerminatorKind::Call { ref destination, .. } = terminator.kind {
 169             if let Some((place, _)) = destination {
 170                 self.record_killed_borrows_for_place(place, location);
 171             }
 172         }
 173
 174         self.super_terminator(terminator, location);
 175     }
 176
 177     fn visit_ascribe_user_ty(
 178         &mut self,
 179         _place: &Place<'tcx>,
 180         _variance: &ty::Variance,
 181         _user_ty: &UserTypeProjection,
 182         _location: Location,
 183     ) {
 184     }
 185 }
 186
 187 impl<'cx, 'cg, 'tcx> ConstraintGeneration<'cx, 'cg, 'tcx> {
 188     /// Some variable with type `live_ty` is "regular live" at
 189     /// `location` -- i.e., it may be used later. This means that all
 190     /// regions appearing in the type `live_ty` must be live at
 191     /// `location`.
 192     fn add_regular_live_constraint<T>(&mut self, live_ty: T, location: Location)
 193     where
 194         T: TypeFoldable<'tcx>,
 195     {
 196         debug!(
 197             "add_regular_live_constraint(live_ty={:?}, location={:?})",
 198             live_ty, location
 199         );
 200
 201         self.infcx
 202             .tcx
 203             .for_each_free_region(&live_ty, |live_region| {
 204                 let vid = live_region.to_region_vid();
 205                 self.liveness_constraints.add_element(vid, location);
 206             });
 207     }
 208
 209     /// When recording facts for Polonius, records the borrows on the specified place
 210     /// as `killed`. For example, when assigning to a local, or on a call's return destination.
 211     fn record_killed_borrows_for_place(&mut self, place: &Place<'tcx>, location: Location) {
 212         if let Some(all_facts) = self.all_facts {
 213             let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation");
 214
 215             // Depending on the `Place` we're killing:
 216             // - if it's a local, or a single deref of a local,
 217             //   we kill all the borrows on the local.
 218             // - if it's a deeper projection, we have to filter which
 219             //   of the borrows are killed: the ones whose `borrowed_place`
 220             //   conflicts with the `place`.
 221             match place.as_ref() {
 222                 PlaceRef {
 223                     base: &PlaceBase::Local(local),
 224                     projection: &[],
 225                 } |
 226                 PlaceRef {
 227                     base: &PlaceBase::Local(local),
 228                     projection: &[ProjectionElem::Deref],
 229                 } => {
 230                     debug!(
 231                         "Recording `killed` facts for borrows of local={:?} at location={:?}",
 232                         local, location
 233                     );
 234
 235                     record_killed_borrows_for_local(
 236                         all_facts,
 237                         self.borrow_set,
 238                         self.location_table,
 239                         &local,
 240                         location,
 241                     );
 242                 }
 243
 244                 PlaceRef {
 245                     base: &PlaceBase::Static(_),
 246                     ..
 247                 } => {
 248                     // Ignore kills of static or static mut variables.
 249                 }
 250
 251                 PlaceRef {
 252                     base: &PlaceBase::Local(local),
 253                     projection: &[.., _],
 254                 } => {
 255                     // Kill conflicting borrows of the innermost local.
 256                     debug!(
 257                         "Recording `killed` facts for borrows of \
 258                             innermost projected local={:?} at location={:?}",
 259                         local, location
 260                     );
 261
 262                     if let Some(borrow_indices) = self.borrow_set.local_map.get(&local) {
 263                         for &borrow_index in borrow_indices {
 264                             let places_conflict = places_conflict::places_conflict(
 265                                 self.infcx.tcx,
 266                                 self.param_env,
 267                                 self.body,
 268                                 &self.borrow_set.borrows[borrow_index].borrowed_place,
 269                                 place,
 270                                 places_conflict::PlaceConflictBias::NoOverlap,
 271                             );
 272
 273                             if places_conflict {
 274                                 let location_index = self.location_table.mid_index(location);
 275                                 all_facts.killed.push((borrow_index, location_index));
 276                             }
 277                         }
 278                     }
 279                 }
 280             }
 281         }
 282     }
 283 }
 284
 285 /// When recording facts for Polonius, records the borrows on the specified local as `killed`.
 286 fn record_killed_borrows_for_local(
 287     all_facts: &mut AllFacts,
 288     borrow_set: &BorrowSet<'_>,
 289     location_table: &LocationTable,
 290     local: &Local,
 291     location: Location,
 292 ) {
 293     if let Some(borrow_indices) = borrow_set.local_map.get(local) {
 294         all_facts.killed.reserve(borrow_indices.len());
 295         for &borrow_index in borrow_indices {
 296             let location_index = location_table.mid_index(location);
 297             all_facts.killed.push((borrow_index, location_index));
 298         }
 299     }
 300 }