src/librustc_mir/borrow_check/nll/constraint_generation.rs

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