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