src/librustc_mir/borrow_check/nll/mod.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::{LocationIndex, LocationTable};
  13 use borrow_check::nll::facts::AllFactsExt;
  14 use borrow_check::nll::type_check::{MirTypeckResults, MirTypeckRegionConstraints};
  15 use borrow_check::nll::type_check::liveness::liveness_map::NllLivenessMap;
  16 use borrow_check::nll::region_infer::values::RegionValueElements;
  17 use dataflow::indexes::BorrowIndex;
  18 use dataflow::move_paths::MoveData;
  19 use dataflow::FlowAtLocation;
  20 use dataflow::MaybeInitializedPlaces;
  21 use rustc::hir::def_id::DefId;
  22 use rustc::infer::InferCtxt;
  23 use rustc::mir::{ClosureOutlivesSubject, ClosureRegionRequirements, Mir};
  24 use rustc::ty::{self, RegionKind, RegionVid};
  25 use rustc_errors::Diagnostic;
  26 use std::fmt::Debug;
  27 use std::env;
  28 use std::io;
  29 use std::path::PathBuf;
  30 use std::rc::Rc;
  31 use std::str::FromStr;
  32 use transform::MirSource;
  33
  34 use self::mir_util::PassWhere;
  35 use polonius_engine::{Algorithm, Output};
  36 use util as mir_util;
  37 use util::pretty;
  38
  39 mod constraint_generation;
  40 pub mod explain_borrow;
  41 mod facts;
  42 mod invalidation;
  43 crate mod region_infer;
  44 mod renumber;
  45 crate mod type_check;
  46 mod universal_regions;
  47
  48 mod constraints;
  49
  50 use self::facts::AllFacts;
  51 use self::region_infer::RegionInferenceContext;
  52 use self::universal_regions::UniversalRegions;
  53
  54 /// Rewrites the regions in the MIR to use NLL variables, also
  55 /// scraping out the set of universal regions (e.g., region parameters)
  56 /// declared on the function. That set will need to be given to
  57 /// `compute_regions`.
  58 pub(in borrow_check) fn replace_regions_in_mir<'cx, 'gcx, 'tcx>(
  59     infcx: &InferCtxt<'cx, 'gcx, 'tcx>,
  60     def_id: DefId,
  61     param_env: ty::ParamEnv<'tcx>,
  62     mir: &mut Mir<'tcx>,
  63 ) -> UniversalRegions<'tcx> {
  64     debug!("replace_regions_in_mir(def_id={:?})", def_id);
  65
  66     // Compute named region information. This also renumbers the inputs/outputs.
  67     let universal_regions = UniversalRegions::new(infcx, def_id, param_env);
  68
  69     // Replace all remaining regions with fresh inference variables.
  70     renumber::renumber_mir(infcx, mir);
  71
  72     let source = MirSource::item(def_id);
  73     mir_util::dump_mir(infcx.tcx, None, "renumber", &0, source, mir, |_, _| Ok(()));
  74
  75     universal_regions
  76 }
  77
  78 /// Computes the (non-lexical) regions from the input MIR.
  79 ///
  80 /// This may result in errors being reported.
  81 pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
  82     infcx: &InferCtxt<'cx, 'gcx, 'tcx>,
  83     def_id: DefId,
  84     universal_regions: UniversalRegions<'tcx>,
  85     mir: &Mir<'tcx>,
  86     location_table: &LocationTable,
  87     param_env: ty::ParamEnv<'gcx>,
  88     flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'cx, 'gcx, 'tcx>>,
  89     move_data: &MoveData<'tcx>,
  90     borrow_set: &BorrowSet<'tcx>,
  91     errors_buffer: &mut Vec<Diagnostic>,
  92 ) -> (
  93     RegionInferenceContext<'tcx>,
  94     Option<Rc<Output<RegionVid, BorrowIndex, LocationIndex>>>,
  95     Option<ClosureRegionRequirements<'gcx>>,
  96 ) {
  97     let mut all_facts = if AllFacts::enabled(infcx.tcx) {
  98         Some(AllFacts::default())
  99     } else {
 100         None
 101     };
 102
 103     let universal_regions = Rc::new(universal_regions);
 104
 105     let elements = &Rc::new(RegionValueElements::new(mir));
 106
 107     // Run the MIR type-checker.
 108     let MirTypeckResults {
 109         constraints,
 110         placeholder_indices,
 111         universal_region_relations,
 112     } = type_check::type_check(
 113         infcx,
 114         param_env,
 115         mir,
 116         def_id,
 117         &universal_regions,
 118         location_table,
 119         borrow_set,
 120         &mut all_facts,
 121         flow_inits,
 122         move_data,
 123         elements,
 124     );
 125
 126     let placeholder_indices = Rc::new(placeholder_indices);
 127
 128     if let Some(all_facts) = &mut all_facts {
 129         all_facts
 130             .universal_region
 131             .extend(universal_regions.universal_regions());
 132     }
 133
 134     // Create the region inference context, taking ownership of the
 135     // region inference data that was contained in `infcx`, and the
 136     // base constraints generated by the type-check.
 137     let var_origins = infcx.take_region_var_origins();
 138     let MirTypeckRegionConstraints {
 139         mut liveness_constraints,
 140         outlives_constraints,
 141         closure_bounds_mapping,
 142         type_tests,
 143     } = constraints;
 144
 145     constraint_generation::generate_constraints(
 146         infcx,
 147         &mut liveness_constraints,
 148         &mut all_facts,
 149         location_table,
 150         &mir,
 151         borrow_set,
 152     );
 153
 154     let mut regioncx = RegionInferenceContext::new(
 155         var_origins,
 156         universal_regions,
 157         placeholder_indices,
 158         universal_region_relations,
 159         mir,
 160         outlives_constraints,
 161         closure_bounds_mapping,
 162         type_tests,
 163         liveness_constraints,
 164         elements,
 165     );
 166
 167     // Generate various additional constraints.
 168     invalidation::generate_invalidates(
 169         infcx.tcx,
 170         &mut all_facts,
 171         location_table,
 172         &mir,
 173         borrow_set,
 174     );
 175
 176     // Dump facts if requested.
 177     let polonius_output = all_facts.and_then(|all_facts| {
 178         if infcx.tcx.sess.opts.debugging_opts.nll_facts {
 179             let def_path = infcx.tcx.hir.def_path(def_id);
 180             let dir_path =
 181                 PathBuf::from("nll-facts").join(def_path.to_filename_friendly_no_crate());
 182             all_facts.write_to_dir(dir_path, location_table).unwrap();
 183         }
 184
 185         if infcx.tcx.sess.opts.debugging_opts.polonius {
 186             let algorithm = env::var("POLONIUS_ALGORITHM")
 187                 .unwrap_or_else(|_| String::from("DatafrogOpt"));
 188             let algorithm = Algorithm::from_str(&algorithm).unwrap();
 189             debug!("compute_regions: using polonius algorithm {:?}", algorithm);
 190             Some(Rc::new(Output::compute(
 191                 &all_facts,
 192                 algorithm,
 193                 false,
 194             )))
 195         } else {
 196             None
 197         }
 198     });
 199
 200     // Solve the region constraints.
 201     let closure_region_requirements = regioncx.solve(infcx, &mir, def_id, errors_buffer);
 202
 203     // Dump MIR results into a file, if that is enabled. This let us
 204     // write unit-tests, as well as helping with debugging.
 205     dump_mir_results(
 206         infcx,
 207         MirSource::item(def_id),
 208         &mir,
 209         &regioncx,
 210         &closure_region_requirements,
 211     );
 212
 213     // We also have a `#[rustc_nll]` annotation that causes us to dump
 214     // information
 215     dump_annotation(infcx, &mir, def_id, &regioncx, &closure_region_requirements, errors_buffer);
 216
 217     (regioncx, polonius_output, closure_region_requirements)
 218 }
 219
 220 fn dump_mir_results<'a, 'gcx, 'tcx>(
 221     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 222     source: MirSource,
 223     mir: &Mir<'tcx>,
 224     regioncx: &RegionInferenceContext,
 225     closure_region_requirements: &Option<ClosureRegionRequirements>,
 226 ) {
 227     if !mir_util::dump_enabled(infcx.tcx, "nll", source) {
 228         return;
 229     }
 230
 231     mir_util::dump_mir(
 232         infcx.tcx,
 233         None,
 234         "nll",
 235         &0,
 236         source,
 237         mir,
 238         |pass_where, out| {
 239             match pass_where {
 240                 // Before the CFG, dump out the values for each region variable.
 241                 PassWhere::BeforeCFG => {
 242                     regioncx.dump_mir(out)?;
 243
 244                     if let Some(closure_region_requirements) = closure_region_requirements {
 245                         writeln!(out, "|")?;
 246                         writeln!(out, "| Free Region Constraints")?;
 247                         for_each_region_constraint(closure_region_requirements, &mut |msg| {
 248                             writeln!(out, "| {}", msg)
 249                         })?;
 250                     }
 251                 }
 252
 253                 PassWhere::BeforeLocation(_) => {
 254                 }
 255
 256                 PassWhere::AfterTerminator(_) => {
 257                 }
 258
 259                 PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {}
 260             }
 261             Ok(())
 262         },
 263     );
 264
 265     // Also dump the inference graph constraints as a graphviz file.
 266     let _: io::Result<()> = try_block! {
 267         let mut file =
 268             pretty::create_dump_file(infcx.tcx, "regioncx.all.dot", None, "nll", &0, source)?;
 269         regioncx.dump_graphviz_raw_constraints(&mut file)?;
 270     };
 271
 272     // Also dump the inference graph constraints as a graphviz file.
 273     let _: io::Result<()> = try_block! {
 274         let mut file =
 275             pretty::create_dump_file(infcx.tcx, "regioncx.scc.dot", None, "nll", &0, source)?;
 276         regioncx.dump_graphviz_scc_constraints(&mut file)?;
 277     };
 278 }
 279
 280 fn dump_annotation<'a, 'gcx, 'tcx>(
 281     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 282     mir: &Mir<'tcx>,
 283     mir_def_id: DefId,
 284     regioncx: &RegionInferenceContext<'tcx>,
 285     closure_region_requirements: &Option<ClosureRegionRequirements>,
 286     errors_buffer: &mut Vec<Diagnostic>,
 287 ) {
 288     let tcx = infcx.tcx;
 289     let base_def_id = tcx.closure_base_def_id(mir_def_id);
 290     if !tcx.has_attr(base_def_id, "rustc_regions") {
 291         return;
 292     }
 293
 294     // When the enclosing function is tagged with `#[rustc_regions]`,
 295     // we dump out various bits of state as warnings. This is useful
 296     // for verifying that the compiler is behaving as expected.  These
 297     // warnings focus on the closure region requirements -- for
 298     // viewing the intraprocedural state, the -Zdump-mir output is
 299     // better.
 300
 301     if let Some(closure_region_requirements) = closure_region_requirements {
 302         let mut err = tcx
 303             .sess
 304             .diagnostic()
 305             .span_note_diag(mir.span, "External requirements");
 306
 307         regioncx.annotate(tcx, &mut err);
 308
 309         err.note(&format!(
 310             "number of external vids: {}",
 311             closure_region_requirements.num_external_vids
 312         ));
 313
 314         // Dump the region constraints we are imposing *between* those
 315         // newly created variables.
 316         for_each_region_constraint(closure_region_requirements, &mut |msg| {
 317             err.note(msg);
 318             Ok(())
 319         }).unwrap();
 320
 321         err.buffer(errors_buffer);
 322     } else {
 323         let mut err = tcx
 324             .sess
 325             .diagnostic()
 326             .span_note_diag(mir.span, "No external requirements");
 327         regioncx.annotate(tcx, &mut err);
 328
 329         err.buffer(errors_buffer);
 330     }
 331 }
 332
 333 fn for_each_region_constraint(
 334     closure_region_requirements: &ClosureRegionRequirements,
 335     with_msg: &mut dyn FnMut(&str) -> io::Result<()>,
 336 ) -> io::Result<()> {
 337     for req in &closure_region_requirements.outlives_requirements {
 338         let subject: &dyn Debug = match &req.subject {
 339             ClosureOutlivesSubject::Region(subject) => subject,
 340             ClosureOutlivesSubject::Ty(ty) => ty,
 341         };
 342         with_msg(&format!(
 343             "where {:?}: {:?}",
 344             subject, req.outlived_free_region,
 345         ))?;
 346     }
 347     Ok(())
 348 }
 349
 350 /// Right now, we piggy back on the `ReVar` to store our NLL inference
 351 /// regions. These are indexed with `RegionVid`. This method will
 352 /// assert that the region is a `ReVar` and extract its internal index.
 353 /// This is reasonable because in our MIR we replace all universal regions
 354 /// with inference variables.
 355 pub trait ToRegionVid {
 356     fn to_region_vid(self) -> RegionVid;
 357 }
 358
 359 impl<'tcx> ToRegionVid for &'tcx RegionKind {
 360     fn to_region_vid(self) -> RegionVid {
 361         if let ty::ReVar(vid) = self {
 362             *vid
 363         } else {
 364             bug!("region is not an ReVar: {:?}", self)
 365         }
 366     }
 367 }
 368
 369 impl ToRegionVid for RegionVid {
 370     fn to_region_vid(self) -> RegionVid {
 371         self
 372     }
 373 }
 374
 375 crate trait ConstraintDescription {
 376     fn description(&self) -> &'static str;
 377 }