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