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