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 rustc::infer::InferCtxt;
   7 use rustc::mir::visit::TyContext;
   8 use rustc::mir::visit::Visitor;
   9 use rustc::mir::{BasicBlock, BasicBlockData, Location, Mir, Place, PlaceBase, Rvalue};
  10 use rustc::mir::{SourceInfo, Statement, Terminator};
  11 use rustc::mir::UserTypeProjection;
  12 use rustc::ty::fold::TypeFoldable;
  13 use rustc::ty::{self, ClosureSubsts, GeneratorSubsts, RegionVid, Ty};
  14 use rustc::ty::subst::SubstsRef;
  15
  16 pub(super) fn generate_constraints<'cx, 'gcx, 'tcx>(
  17     infcx: &InferCtxt<'cx, 'gcx, 'tcx>,
  18     liveness_constraints: &mut LivenessValues<RegionVid>,
  19     all_facts: &mut Option<AllFacts>,
  20     location_table: &LocationTable,
  21     mir: &Mir<'tcx>,
  22     borrow_set: &BorrowSet<'tcx>,
  23 ) {
  24     let mut cg = ConstraintGeneration {
  25         borrow_set,
  26         infcx,
  27         liveness_constraints,
  28         location_table,
  29         all_facts,
  30     };
  31
  32     for (bb, data) in mir.basic_blocks().iter_enumerated() {
  33         cg.visit_basic_block_data(bb, data);
  34     }
  35 }
  36
  37 /// 'cg = the duration of the constraint generation process itself.
  38 struct ConstraintGeneration<'cg, 'cx: 'cg, 'gcx: 'tcx, 'tcx: 'cx> {
  39     infcx: &'cg InferCtxt<'cx, 'gcx, 'tcx>,
  40     all_facts: &'cg mut Option<AllFacts>,
  41     location_table: &'cg LocationTable,
  42     liveness_constraints: &'cg mut LivenessValues<RegionVid>,
  43     borrow_set: &'cg BorrowSet<'tcx>,
  44 }
  45
  46 impl<'cg, 'cx, 'gcx, 'tcx> Visitor<'tcx> for ConstraintGeneration<'cg, 'cx, 'gcx, 'tcx> {
  47     fn visit_basic_block_data(&mut self, bb: BasicBlock, data: &BasicBlockData<'tcx>) {
  48         self.super_basic_block_data(bb, data);
  49     }
  50
  51     /// We sometimes have `substs` within an rvalue, or within a
  52     /// call. Make them live at the location where they appear.
  53     fn visit_substs(&mut self, substs: &SubstsRef<'tcx>, location: Location) {
  54         self.add_regular_live_constraint(*substs, location);
  55         self.super_substs(substs);
  56     }
  57
  58     /// We sometimes have `region` within an rvalue, or within a
  59     /// call. Make them live at the location where they appear.
  60     fn visit_region(&mut self, region: &ty::Region<'tcx>, location: Location) {
  61         self.add_regular_live_constraint(*region, location);
  62         self.super_region(region);
  63     }
  64
  65     /// We sometimes have `ty` within an rvalue, or within a
  66     /// call. Make them live at the location where they appear.
  67     fn visit_ty(&mut self, ty: Ty<'tcx>, ty_context: TyContext) {
  68         match ty_context {
  69             TyContext::ReturnTy(SourceInfo { span, .. })
  70             | TyContext::YieldTy(SourceInfo { span, .. })
  71             | TyContext::UserTy(span)
  72             | TyContext::LocalDecl { source_info: SourceInfo { span, .. }, .. } => {
  73                 span_bug!(
  74                     span,
  75                     "should not be visiting outside of the CFG: {:?}",
  76                     ty_context
  77                 );
  78             }
  79             TyContext::Location(location) => {
  80                 self.add_regular_live_constraint(ty, location);
  81             }
  82         }
  83
  84         self.super_ty(ty);
  85     }
  86
  87     /// We sometimes have `generator_substs` within an rvalue, or within a
  88     /// call. Make them live at the location where they appear.
  89     fn visit_generator_substs(&mut self, substs: &GeneratorSubsts<'tcx>, location: Location) {
  90         self.add_regular_live_constraint(*substs, location);
  91         self.super_generator_substs(substs);
  92     }
  93
  94     /// We sometimes have `closure_substs` within an rvalue, or within a
  95     /// call. Make them live at the location where they appear.
  96     fn visit_closure_substs(&mut self, substs: &ClosureSubsts<'tcx>, location: Location) {
  97         self.add_regular_live_constraint(*substs, location);
  98         self.super_closure_substs(substs);
  99     }
 100
 101     fn visit_statement(
 102         &mut self,
 103         statement: &Statement<'tcx>,
 104         location: Location,
 105     ) {
 106         if let Some(all_facts) = self.all_facts {
 107             all_facts.cfg_edge.push((
 108                 self.location_table.start_index(location),
 109                 self.location_table.mid_index(location),
 110             ));
 111
 112             all_facts.cfg_edge.push((
 113                 self.location_table.mid_index(location),
 114                 self.location_table
 115                     .start_index(location.successor_within_block()),
 116             ));
 117         }
 118
 119         self.super_statement(statement, location);
 120     }
 121
 122     fn visit_assign(
 123         &mut self,
 124         place: &Place<'tcx>,
 125         rvalue: &Rvalue<'tcx>,
 126         location: Location,
 127     ) {
 128         // When we see `X = ...`, then kill borrows of
 129         // `(*X).foo` and so forth.
 130         if let Some(all_facts) = self.all_facts {
 131             if let Place::Base(PlaceBase::Local(temp)) = place {
 132                 if let Some(borrow_indices) = self.borrow_set.local_map.get(temp) {
 133                     all_facts.killed.reserve(borrow_indices.len());
 134                     for &borrow_index in borrow_indices {
 135                         let location_index = self.location_table.mid_index(location);
 136                         all_facts.killed.push((borrow_index, location_index));
 137                     }
 138                 }
 139             }
 140         }
 141
 142         self.super_assign(place, rvalue, location);
 143     }
 144
 145     fn visit_terminator(
 146         &mut self,
 147         terminator: &Terminator<'tcx>,
 148         location: Location,
 149     ) {
 150         if let Some(all_facts) = self.all_facts {
 151             all_facts.cfg_edge.push((
 152                 self.location_table.start_index(location),
 153                 self.location_table.mid_index(location),
 154             ));
 155
 156             let successor_blocks = terminator.successors();
 157             all_facts.cfg_edge.reserve(successor_blocks.size_hint().0);
 158             for successor_block in successor_blocks {
 159                 all_facts.cfg_edge.push((
 160                     self.location_table.mid_index(location),
 161                     self.location_table
 162                         .start_index(successor_block.start_location()),
 163                 ));
 164             }
 165         }
 166
 167         self.super_terminator(terminator, location);
 168     }
 169
 170     fn visit_ascribe_user_ty(
 171         &mut self,
 172         _place: &Place<'tcx>,
 173         _variance: &ty::Variance,
 174         _user_ty: &UserTypeProjection,
 175         _location: Location,
 176     ) {
 177     }
 178 }
 179
 180 impl<'cx, 'cg, 'gcx, 'tcx> ConstraintGeneration<'cx, 'cg, 'gcx, 'tcx> {
 181     /// Some variable with type `live_ty` is "regular live" at
 182     /// `location` -- i.e., it may be used later. This means that all
 183     /// regions appearing in the type `live_ty` must be live at
 184     /// `location`.
 185     fn add_regular_live_constraint<T>(&mut self, live_ty: T, location: Location)
 186     where
 187         T: TypeFoldable<'tcx>,
 188     {
 189         debug!(
 190             "add_regular_live_constraint(live_ty={:?}, location={:?})",
 191             live_ty, location
 192         );
 193
 194         self.infcx
 195             .tcx
 196             .for_each_free_region(&live_ty, |live_region| {
 197                 let vid = live_region.to_region_vid();
 198                 self.liveness_constraints.add_element(vid, location);
 199             });
 200     }
 201 }