compiler/rustc_borrowck/src/constraint_generation.rs

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