compiler/rustc_borrowck/src/constraint_generation.rs

   1 #![deny(rustc::untranslatable_diagnostic)]
   2 #![deny(rustc::diagnostic_outside_of_impl)]
   3 use rustc_infer::infer::InferCtxt;
   4 use rustc_middle::mir::visit::TyContext;
   5 use rustc_middle::mir::visit::Visitor;
   6 use rustc_middle::mir::{
   7     BasicBlock, BasicBlockData, Body, Local, Location, Place, PlaceRef, ProjectionElem, Rvalue,
   8     SourceInfo, Statement, StatementKind, Terminator, TerminatorKind, UserTypeProjection,
   9 };
  10 use rustc_middle::ty::subst::SubstsRef;
  11 use rustc_middle::ty::visit::TypeVisitable;
  12 use rustc_middle::ty::{self, RegionVid, Ty, TyCtxt};
  13
  14 use crate::{
  15     borrow_set::BorrowSet, facts::AllFacts, location::LocationTable, nll::ToRegionVid,
  16     places_conflict, region_infer::values::LivenessValues,
  17 };
  18
  19 pub(super) fn generate_constraints<'tcx>(
  20     infcx: &InferCtxt<'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, 'tcx> {
  43     infcx: &'cg InferCtxt<'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, 'tcx> Visitor<'tcx> for ConstraintGeneration<'cg, '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!(span, "should not be visiting outside of the CFG: {:?}", ty_context);
  79             }
  80             TyContext::Location(location) => {
  81                 self.add_regular_live_constraint(ty, location);
  82             }
  83         }
  84
  85         self.super_ty(ty);
  86     }
  87
  88     fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
  89         if let Some(all_facts) = self.all_facts {
  90             let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation");
  91             all_facts.cfg_edge.push((
  92                 self.location_table.start_index(location),
  93                 self.location_table.mid_index(location),
  94             ));
  95
  96             all_facts.cfg_edge.push((
  97                 self.location_table.mid_index(location),
  98                 self.location_table.start_index(location.successor_within_block()),
  99             ));
 100
 101             // If there are borrows on this now dead local, we need to record them as `killed`.
 102             if let StatementKind::StorageDead(local) = statement.kind {
 103                 record_killed_borrows_for_local(
 104                     all_facts,
 105                     self.borrow_set,
 106                     self.location_table,
 107                     local,
 108                     location,
 109                 );
 110             }
 111         }
 112
 113         self.super_statement(statement, location);
 114     }
 115
 116     fn visit_assign(&mut self, place: &Place<'tcx>, rvalue: &Rvalue<'tcx>, location: Location) {
 117         // When we see `X = ...`, then kill borrows of
 118         // `(*X).foo` and so forth.
 119         self.record_killed_borrows_for_place(*place, location);
 120
 121         self.super_assign(place, rvalue, location);
 122     }
 123
 124     fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) {
 125         if let Some(all_facts) = self.all_facts {
 126             let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation");
 127             all_facts.cfg_edge.push((
 128                 self.location_table.start_index(location),
 129                 self.location_table.mid_index(location),
 130             ));
 131
 132             let successor_blocks = terminator.successors();
 133             all_facts.cfg_edge.reserve(successor_blocks.size_hint().0);
 134             for successor_block in successor_blocks {
 135                 all_facts.cfg_edge.push((
 136                     self.location_table.mid_index(location),
 137                     self.location_table.start_index(successor_block.start_location()),
 138                 ));
 139             }
 140         }
 141
 142         // A `Call` terminator's return value can be a local which has borrows,
 143         // so we need to record those as `killed` as well.
 144         if let TerminatorKind::Call { destination, .. } = terminator.kind {
 145             self.record_killed_borrows_for_place(destination, location);
 146         }
 147
 148         self.super_terminator(terminator, location);
 149     }
 150
 151     fn visit_ascribe_user_ty(
 152         &mut self,
 153         _place: &Place<'tcx>,
 154         _variance: ty::Variance,
 155         _user_ty: &UserTypeProjection,
 156         _location: Location,
 157     ) {
 158     }
 159 }
 160
 161 impl<'cx, 'tcx> ConstraintGeneration<'cx, 'tcx> {
 162     /// Some variable with type `live_ty` is "regular live" at
 163     /// `location` -- i.e., it may be used later. This means that all
 164     /// regions appearing in the type `live_ty` must be live at
 165     /// `location`.
 166     fn add_regular_live_constraint<T>(&mut self, live_ty: T, location: Location)
 167     where
 168         T: TypeVisitable<TyCtxt<'tcx>>,
 169     {
 170         debug!("add_regular_live_constraint(live_ty={:?}, location={:?})", live_ty, location);
 171
 172         self.infcx.tcx.for_each_free_region(&live_ty, |live_region| {
 173             let vid = live_region.to_region_vid();
 174             self.liveness_constraints.add_element(vid, location);
 175         });
 176     }
 177
 178     /// When recording facts for Polonius, records the borrows on the specified place
 179     /// as `killed`. For example, when assigning to a local, or on a call's return destination.
 180     fn record_killed_borrows_for_place(&mut self, place: Place<'tcx>, location: Location) {
 181         if let Some(all_facts) = self.all_facts {
 182             let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation");
 183
 184             // Depending on the `Place` we're killing:
 185             // - if it's a local, or a single deref of a local,
 186             //   we kill all the borrows on the local.
 187             // - if it's a deeper projection, we have to filter which
 188             //   of the borrows are killed: the ones whose `borrowed_place`
 189             //   conflicts with the `place`.
 190             match place.as_ref() {
 191                 PlaceRef { local, projection: &[] }
 192                 | PlaceRef { local, projection: &[ProjectionElem::Deref] } => {
 193                     debug!(
 194                         "Recording `killed` facts for borrows of local={:?} at location={:?}",
 195                         local, location
 196                     );
 197
 198                     record_killed_borrows_for_local(
 199                         all_facts,
 200                         self.borrow_set,
 201                         self.location_table,
 202                         local,
 203                         location,
 204                     );
 205                 }
 206
 207                 PlaceRef { local, projection: &[.., _] } => {
 208                     // Kill conflicting borrows of the innermost local.
 209                     debug!(
 210                         "Recording `killed` facts for borrows of \
 211                             innermost projected local={:?} at location={:?}",
 212                         local, location
 213                     );
 214
 215                     if let Some(borrow_indices) = self.borrow_set.local_map.get(&local) {
 216                         for &borrow_index in borrow_indices {
 217                             let places_conflict = places_conflict::places_conflict(
 218                                 self.infcx.tcx,
 219                                 self.body,
 220                                 self.borrow_set[borrow_index].borrowed_place,
 221                                 place,
 222                                 places_conflict::PlaceConflictBias::NoOverlap,
 223                             );
 224
 225                             if places_conflict {
 226                                 let location_index = self.location_table.mid_index(location);
 227                                 all_facts.loan_killed_at.push((borrow_index, location_index));
 228                             }
 229                         }
 230                     }
 231                 }
 232             }
 233         }
 234     }
 235 }
 236
 237 /// When recording facts for Polonius, records the borrows on the specified local as `killed`.
 238 fn record_killed_borrows_for_local(
 239     all_facts: &mut AllFacts,
 240     borrow_set: &BorrowSet<'_>,
 241     location_table: &LocationTable,
 242     local: Local,
 243     location: Location,
 244 ) {
 245     if let Some(borrow_indices) = borrow_set.local_map.get(&local) {
 246         all_facts.loan_killed_at.reserve(borrow_indices.len());
 247         for &borrow_index in borrow_indices {
 248             let location_index = location_table.mid_index(location);
 249             all_facts.loan_killed_at.push((borrow_index, location_index));
 250         }
 251     }
 252 }