src/librustc_mir/borrow_check/nll/constraint_generation.rs

   1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use borrow_check::borrow_set::BorrowSet;
  12 use borrow_check::location::LocationTable;
  13 use borrow_check::nll::ToRegionVid;
  14 use borrow_check::nll::facts::AllFacts;
  15 use borrow_check::nll::region_infer::RegionInferenceContext;
  16 use borrow_check::nll::type_check::AtLocation;
  17 use rustc::hir;
  18 use rustc::infer::InferCtxt;
  19 use rustc::mir::visit::TyContext;
  20 use rustc::mir::visit::Visitor;
  21 use rustc::mir::Place::Projection;
  22 use rustc::mir::{BasicBlock, BasicBlockData, Location, Mir, Place, Rvalue};
  23 use rustc::mir::{Local, PlaceProjection, ProjectionElem, Statement, Terminator};
  24 use rustc::ty::fold::TypeFoldable;
  25 use rustc::ty::subst::Substs;
  26 use rustc::ty::{self, CanonicalTy, ClosureSubsts, GeneratorSubsts};
  27 use std::iter;
  28
  29 pub(super) fn generate_constraints<'cx, 'gcx, 'tcx>(
  30     infcx: &InferCtxt<'cx, 'gcx, 'tcx>,
  31     regioncx: &mut RegionInferenceContext<'tcx>,
  32     all_facts: &mut Option<AllFacts>,
  33     location_table: &LocationTable,
  34     mir: &Mir<'tcx>,
  35     borrow_set: &BorrowSet<'tcx>,
  36     liveness_set_from_typeck: &[(ty::Region<'tcx>, Location)],
  37 ) {
  38     let mut cg = ConstraintGeneration {
  39         borrow_set,
  40         infcx,
  41         regioncx,
  42         location_table,
  43         all_facts,
  44         mir,
  45     };
  46
  47     cg.add_region_liveness_constraints_from_type_check(liveness_set_from_typeck);
  48
  49     for (bb, data) in mir.basic_blocks().iter_enumerated() {
  50         cg.visit_basic_block_data(bb, data);
  51     }
  52 }
  53
  54 /// 'cg = the duration of the constraint generation process itself.
  55 struct ConstraintGeneration<'cg, 'cx: 'cg, 'gcx: 'tcx, 'tcx: 'cx> {
  56     infcx: &'cg InferCtxt<'cx, 'gcx, 'tcx>,
  57     all_facts: &'cg mut Option<AllFacts>,
  58     location_table: &'cg LocationTable,
  59     regioncx: &'cg mut RegionInferenceContext<'tcx>,
  60     mir: &'cg Mir<'tcx>,
  61     borrow_set: &'cg BorrowSet<'tcx>,
  62 }
  63
  64 impl<'cg, 'cx, 'gcx, 'tcx> Visitor<'tcx> for ConstraintGeneration<'cg, 'cx, 'gcx, 'tcx> {
  65     fn visit_basic_block_data(&mut self, bb: BasicBlock, data: &BasicBlockData<'tcx>) {
  66         self.super_basic_block_data(bb, data);
  67     }
  68
  69     /// We sometimes have `substs` within an rvalue, or within a
  70     /// call. Make them live at the location where they appear.
  71     fn visit_substs(&mut self, substs: &&'tcx Substs<'tcx>, location: Location) {
  72         self.add_regular_live_constraint(*substs, location);
  73         self.super_substs(substs);
  74     }
  75
  76     /// We sometimes have `region` within an rvalue, or within a
  77     /// call. Make them live at the location where they appear.
  78     fn visit_region(&mut self, region: &ty::Region<'tcx>, location: Location) {
  79         self.add_regular_live_constraint(*region, location);
  80         self.super_region(region);
  81     }
  82
  83     /// We sometimes have `ty` within an rvalue, or within a
  84     /// call. Make them live at the location where they appear.
  85     fn visit_ty(&mut self, ty: &ty::Ty<'tcx>, ty_context: TyContext) {
  86         match ty_context {
  87             TyContext::ReturnTy(source_info)
  88             | TyContext::YieldTy(source_info)
  89             | TyContext::LocalDecl { source_info, .. } => {
  90                 span_bug!(
  91                     source_info.span,
  92                     "should not be visiting outside of the CFG: {:?}",
  93                     ty_context
  94                 );
  95             }
  96             TyContext::Location(location) => {
  97                 self.add_regular_live_constraint(*ty, location);
  98             }
  99         }
 100
 101         self.super_ty(ty);
 102     }
 103
 104     /// We sometimes have `generator_substs` within an rvalue, or within a
 105     /// call. Make them live at the location where they appear.
 106     fn visit_generator_substs(&mut self, substs: &GeneratorSubsts<'tcx>, location: Location) {
 107         self.add_regular_live_constraint(*substs, location);
 108         self.super_generator_substs(substs);
 109     }
 110
 111     /// We sometimes have `closure_substs` within an rvalue, or within a
 112     /// call. Make them live at the location where they appear.
 113     fn visit_closure_substs(&mut self, substs: &ClosureSubsts<'tcx>, location: Location) {
 114         self.add_regular_live_constraint(*substs, location);
 115         self.super_closure_substs(substs);
 116     }
 117
 118     fn visit_statement(
 119         &mut self,
 120         block: BasicBlock,
 121         statement: &Statement<'tcx>,
 122         location: Location,
 123     ) {
 124         if let Some(all_facts) = self.all_facts {
 125             all_facts.cfg_edge.push((
 126                 self.location_table.start_index(location),
 127                 self.location_table.mid_index(location),
 128             ));
 129
 130             all_facts.cfg_edge.push((
 131                 self.location_table.mid_index(location),
 132                 self.location_table
 133                     .start_index(location.successor_within_block()),
 134             ));
 135         }
 136
 137         self.super_statement(block, statement, location);
 138     }
 139
 140     fn visit_assign(
 141         &mut self,
 142         block: BasicBlock,
 143         place: &Place<'tcx>,
 144         rvalue: &Rvalue<'tcx>,
 145         location: Location,
 146     ) {
 147         // When we see `X = ...`, then kill borrows of
 148         // `(*X).foo` and so forth.
 149         if let Some(all_facts) = self.all_facts {
 150             if let Place::Local(temp) = place {
 151                 if let Some(borrow_indices) = self.borrow_set.local_map.get(temp) {
 152                     for &borrow_index in borrow_indices {
 153                         let location_index = self.location_table.mid_index(location);
 154                         all_facts.killed.push((borrow_index, location_index));
 155                     }
 156                 }
 157             }
 158         }
 159
 160         self.super_assign(block, place, rvalue, location);
 161     }
 162
 163     fn visit_terminator(
 164         &mut self,
 165         block: BasicBlock,
 166         terminator: &Terminator<'tcx>,
 167         location: Location,
 168     ) {
 169         if let Some(all_facts) = self.all_facts {
 170             all_facts.cfg_edge.push((
 171                 self.location_table.start_index(location),
 172                 self.location_table.mid_index(location),
 173             ));
 174
 175             for successor_block in terminator.successors() {
 176                 all_facts.cfg_edge.push((
 177                     self.location_table.mid_index(location),
 178                     self.location_table
 179                         .start_index(successor_block.start_location()),
 180                 ));
 181             }
 182         }
 183
 184         self.super_terminator(block, terminator, location);
 185     }
 186
 187     fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location) {
 188         debug!("visit_rvalue(rvalue={:?}, location={:?})", rvalue, location);
 189
 190         match rvalue {
 191             Rvalue::Ref(region, _borrow_kind, borrowed_place) => {
 192                 // In some cases, e.g. when borrowing from an unsafe
 193                 // place, we don't bother to create a loan, since
 194                 // there are no conditions to validate.
 195                 if let Some(all_facts) = self.all_facts {
 196                     if let Some(borrow_index) = self.borrow_set.location_map.get(&location) {
 197                         let region_vid = region.to_region_vid();
 198                         all_facts.borrow_region.push((
 199                             region_vid,
 200                             *borrow_index,
 201                             self.location_table.mid_index(location),
 202                         ));
 203                     }
 204                 }
 205
 206                 // Look for an rvalue like:
 207                 //
 208                 //     & L
 209                 //
 210                 // where L is the path that is borrowed. In that case, we have
 211                 // to add the reborrow constraints (which don't fall out
 212                 // naturally from the type-checker).
 213                 self.add_reborrow_constraint(location, region, borrowed_place);
 214             }
 215
 216             _ => {}
 217         }
 218
 219         self.super_rvalue(rvalue, location);
 220     }
 221
 222     fn visit_user_assert_ty(
 223         &mut self,
 224         _c_ty: &CanonicalTy<'tcx>,
 225         _local: &Local,
 226         _location: Location,
 227     ) {
 228     }
 229 }
 230
 231 impl<'cx, 'cg, 'gcx, 'tcx> ConstraintGeneration<'cx, 'cg, 'gcx, 'tcx> {
 232     /// The MIR type checker generates region liveness constraints
 233     /// that we also have to respect.
 234     fn add_region_liveness_constraints_from_type_check(
 235         &mut self,
 236         liveness_set: &[(ty::Region<'tcx>, Location)],
 237     ) {
 238         debug!(
 239             "add_region_liveness_constraints_from_type_check(liveness_set={} items)",
 240             liveness_set.len(),
 241         );
 242
 243         let ConstraintGeneration {
 244             regioncx,
 245             location_table,
 246             all_facts,
 247             ..
 248         } = self;
 249
 250         for (region, location) in liveness_set {
 251             debug!("generate: {:#?} is live at {:#?}", region, location);
 252             let region_vid = regioncx.to_region_vid(region);
 253             regioncx.add_live_point(region_vid, *location);
 254         }
 255
 256         if let Some(all_facts) = all_facts {
 257             all_facts
 258                 .region_live_at
 259                 .extend(liveness_set.into_iter().flat_map(|(region, location)| {
 260                     let r = regioncx.to_region_vid(region);
 261                     let p1 = location_table.start_index(*location);
 262                     let p2 = location_table.mid_index(*location);
 263                     iter::once((r, p1)).chain(iter::once((r, p2)))
 264                 }));
 265         }
 266     }
 267
 268     /// Some variable with type `live_ty` is "regular live" at
 269     /// `location` -- i.e., it may be used later. This means that all
 270     /// regions appearing in the type `live_ty` must be live at
 271     /// `location`.
 272     fn add_regular_live_constraint<T>(&mut self, live_ty: T, location: Location)
 273     where
 274         T: TypeFoldable<'tcx>,
 275     {
 276         debug!(
 277             "add_regular_live_constraint(live_ty={:?}, location={:?})",
 278             live_ty, location
 279         );
 280
 281         self.infcx
 282             .tcx
 283             .for_each_free_region(&live_ty, |live_region| {
 284                 let vid = live_region.to_region_vid();
 285                 self.regioncx.add_live_point(vid, location);
 286             });
 287     }
 288
 289     // Add the reborrow constraint at `location` so that `borrowed_place`
 290     // is valid for `borrow_region`.
 291     fn add_reborrow_constraint(
 292         &mut self,
 293         location: Location,
 294         borrow_region: ty::Region<'tcx>,
 295         borrowed_place: &Place<'tcx>,
 296     ) {
 297         let mut borrowed_place = borrowed_place;
 298
 299         debug!(
 300             "add_reborrow_constraint({:?}, {:?}, {:?})",
 301             location, borrow_region, borrowed_place
 302         );
 303         while let Projection(box PlaceProjection { base, elem }) = borrowed_place {
 304             debug!("add_reborrow_constraint - iteration {:?}", borrowed_place);
 305
 306             match *elem {
 307                 ProjectionElem::Deref => {
 308                     let tcx = self.infcx.tcx;
 309                     let base_ty = base.ty(self.mir, tcx).to_ty(tcx);
 310
 311                     debug!("add_reborrow_constraint - base_ty = {:?}", base_ty);
 312                     match base_ty.sty {
 313                         ty::TyRef(ref_region, _, mutbl) => {
 314                             self.regioncx.add_outlives(
 315                                 location.boring(),
 316                                 ref_region.to_region_vid(),
 317                                 borrow_region.to_region_vid(),
 318                             );
 319
 320                             if let Some(all_facts) = self.all_facts {
 321                                 all_facts.outlives.push((
 322                                     ref_region.to_region_vid(),
 323                                     borrow_region.to_region_vid(),
 324                                     self.location_table.mid_index(location),
 325                                 ));
 326                             }
 327
 328                             match mutbl {
 329                                 hir::Mutability::MutImmutable => {
 330                                     // Immutable reference. We don't need the base
 331                                     // to be valid for the entire lifetime of
 332                                     // the borrow.
 333                                     break;
 334                                 }
 335                                 hir::Mutability::MutMutable => {
 336                                     // Mutable reference. We *do* need the base
 337                                     // to be valid, because after the base becomes
 338                                     // invalid, someone else can use our mutable deref.
 339
 340                                     // This is in order to make the following function
 341                                     // illegal:
 342                                     // ```
 343                                     // fn unsafe_deref<'a, 'b>(x: &'a &'b mut T) -> &'b mut T {
 344                                     //     &mut *x
 345                                     // }
 346                                     // ```
 347                                     //
 348                                     // As otherwise you could clone `&mut T` using the
 349                                     // following function:
 350                                     // ```
 351                                     // fn bad(x: &mut T) -> (&mut T, &mut T) {
 352                                     //     let my_clone = unsafe_deref(&'a x);
 353                                     //     ENDREGION 'a;
 354                                     //     (my_clone, x)
 355                                     // }
 356                                     // ```
 357                                 }
 358                             }
 359                         }
 360                         ty::TyRawPtr(..) => {
 361                             // deref of raw pointer, guaranteed to be valid
 362                             break;
 363                         }
 364                         ty::TyAdt(def, _) if def.is_box() => {
 365                             // deref of `Box`, need the base to be valid - propagate
 366                         }
 367                         _ => bug!("unexpected deref ty {:?} in {:?}", base_ty, borrowed_place),
 368                     }
 369                 }
 370                 ProjectionElem::Field(..)
 371                 | ProjectionElem::Downcast(..)
 372                 | ProjectionElem::Index(..)
 373                 | ProjectionElem::ConstantIndex { .. }
 374                 | ProjectionElem::Subslice { .. } => {
 375                     // other field access
 376                 }
 377             }
 378
 379             // The "propagate" case. We need to check that our base is valid
 380             // for the borrow's lifetime.
 381             borrowed_place = base;
 382         }
 383     }
 384 }