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::MirTypeckRegionConstraints;
  15 use borrow_check::nll::region_infer::values::RegionValueElements;
  16 use borrow_check::nll::liveness_map::{NllLivenessMap, LocalWithRegion};
  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::util::nodemap::FxHashMap;
  26 use rustc_errors::Diagnostic;
  27 use std::collections::BTreeSet;
  28 use std::fmt::Debug;
  29 use std::env;
  30 use std::io;
  31 use std::path::PathBuf;
  32 use std::rc::Rc;
  33 use std::str::FromStr;
  34 use transform::MirSource;
  35 use util::liveness::{LivenessResults, LiveVarSet};
  36
  37 use self::mir_util::PassWhere;
  38 use polonius_engine::{Algorithm, Output};
  39 use util as mir_util;
  40 use util::pretty::{self, ALIGN};
  41
  42 mod constraint_generation;
  43 pub mod explain_borrow;
  44 mod facts;
  45 mod invalidation;
  46 crate mod region_infer;
  47 mod renumber;
  48 crate mod type_check;
  49 mod universal_regions;
  50 crate mod liveness_map;
  51
  52 mod constraints;
  53
  54 use self::facts::AllFacts;
  55 use self::region_infer::RegionInferenceContext;
  56 use self::universal_regions::UniversalRegions;
  57
  58 /// Rewrites the regions in the MIR to use NLL variables, also
  59 /// scraping out the set of universal regions (e.g., region parameters)
  60 /// declared on the function. That set will need to be given to
  61 /// `compute_regions`.
  62 pub(in borrow_check) fn replace_regions_in_mir<'cx, 'gcx, 'tcx>(
  63     infcx: &InferCtxt<'cx, 'gcx, 'tcx>,
  64     def_id: DefId,
  65     param_env: ty::ParamEnv<'tcx>,
  66     mir: &mut Mir<'tcx>,
  67 ) -> UniversalRegions<'tcx> {
  68     debug!("replace_regions_in_mir(def_id={:?})", def_id);
  69
  70     // Compute named region information. This also renumbers the inputs/outputs.
  71     let universal_regions = UniversalRegions::new(infcx, def_id, param_env);
  72
  73     // Replace all remaining regions with fresh inference variables.
  74     renumber::renumber_mir(infcx, mir);
  75
  76     let source = MirSource::item(def_id);
  77     mir_util::dump_mir(infcx.tcx, None, "renumber", &0, source, mir, |_, _| Ok(()));
  78
  79     universal_regions
  80 }
  81
  82 /// Computes the (non-lexical) regions from the input MIR.
  83 ///
  84 /// This may result in errors being reported.
  85 pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
  86     infcx: &InferCtxt<'cx, 'gcx, 'tcx>,
  87     def_id: DefId,
  88     universal_regions: UniversalRegions<'tcx>,
  89     mir: &Mir<'tcx>,
  90     location_table: &LocationTable,
  91     param_env: ty::ParamEnv<'gcx>,
  92     flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'cx, 'gcx, 'tcx>>,
  93     move_data: &MoveData<'tcx>,
  94     borrow_set: &BorrowSet<'tcx>,
  95     errors_buffer: &mut Vec<Diagnostic>,
  96 ) -> (
  97     RegionInferenceContext<'tcx>,
  98     Option<Rc<Output<RegionVid, BorrowIndex, LocationIndex>>>,
  99     Option<ClosureRegionRequirements<'gcx>>,
 100 ) {
 101     let mut all_facts = if AllFacts::enabled(infcx.tcx) {
 102         Some(AllFacts::default())
 103     } else {
 104         None
 105     };
 106
 107     let universal_regions = Rc::new(universal_regions);
 108
 109     let elements = &Rc::new(RegionValueElements::new(mir));
 110
 111     // Run the MIR type-checker.
 112     let liveness_map = NllLivenessMap::compute(&mir);
 113     let liveness = LivenessResults::compute(mir, &liveness_map);
 114     let (constraint_sets, universal_region_relations) = type_check::type_check(
 115         infcx,
 116         param_env,
 117         mir,
 118         def_id,
 119         &universal_regions,
 120         location_table,
 121         borrow_set,
 122         &liveness,
 123         &mut all_facts,
 124         flow_inits,
 125         move_data,
 126         elements,
 127         errors_buffer,
 128     );
 129
 130     if let Some(all_facts) = &mut all_facts {
 131         all_facts
 132             .universal_region
 133             .extend(universal_regions.universal_regions());
 134     }
 135
 136     // Create the region inference context, taking ownership of the
 137     // region inference data that was contained in `infcx`, and the
 138     // base constraints generated by the type-check.
 139     let var_origins = infcx.take_region_var_origins();
 140     let MirTypeckRegionConstraints {
 141         mut liveness_constraints,
 142         outlives_constraints,
 143         type_tests,
 144     } = constraint_sets;
 145
 146     constraint_generation::generate_constraints(
 147         infcx,
 148         &mut liveness_constraints,
 149         &mut all_facts,
 150         location_table,
 151         &mir,
 152         borrow_set,
 153     );
 154
 155     let mut regioncx = RegionInferenceContext::new(
 156         var_origins,
 157         universal_regions,
 158         universal_region_relations,
 159         mir,
 160         outlives_constraints,
 161         type_tests,
 162         liveness_constraints,
 163         elements,
 164     );
 165
 166     // Generate various additional constraints.
 167     invalidation::generate_invalidates(
 168         infcx,
 169         &mut all_facts,
 170         location_table,
 171         &mir,
 172         def_id,
 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(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         &liveness,
 208         MirSource::item(def_id),
 209         &mir,
 210         &regioncx,
 211         &closure_region_requirements,
 212     );
 213
 214     // We also have a `#[rustc_nll]` annotation that causes us to dump
 215     // information
 216     dump_annotation(infcx, &mir, def_id, &regioncx, &closure_region_requirements, errors_buffer);
 217
 218     (regioncx, polonius_output, closure_region_requirements)
 219 }
 220
 221 fn dump_mir_results<'a, 'gcx, 'tcx>(
 222     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 223     liveness: &LivenessResults<LocalWithRegion>,
 224     source: MirSource,
 225     mir: &Mir<'tcx>,
 226     regioncx: &RegionInferenceContext,
 227     closure_region_requirements: &Option<ClosureRegionRequirements>,
 228 ) {
 229     if !mir_util::dump_enabled(infcx.tcx, "nll", source) {
 230         return;
 231     }
 232
 233     let map = &NllLivenessMap::compute(mir);
 234
 235     let regular_liveness_per_location: FxHashMap<_, _> = mir
 236         .basic_blocks()
 237         .indices()
 238         .flat_map(|bb| {
 239             let mut results = vec![];
 240             liveness
 241                 .regular
 242                 .simulate_block(&mir, bb, map, |location, local_set| {
 243                     results.push((location, local_set.clone()));
 244                 });
 245             results
 246         })
 247         .collect();
 248
 249     let drop_liveness_per_location: FxHashMap<_, _> = mir
 250         .basic_blocks()
 251         .indices()
 252         .flat_map(|bb| {
 253             let mut results = vec![];
 254             liveness
 255                 .drop
 256                 .simulate_block(&mir, bb, map, |location, local_set| {
 257                     results.push((location, local_set.clone()));
 258                 });
 259             results
 260         })
 261         .collect();
 262
 263     mir_util::dump_mir(
 264         infcx.tcx,
 265         None,
 266         "nll",
 267         &0,
 268         source,
 269         mir,
 270         |pass_where, out| {
 271             match pass_where {
 272                 // Before the CFG, dump out the values for each region variable.
 273                 PassWhere::BeforeCFG => {
 274                     regioncx.dump_mir(out)?;
 275
 276                     if let Some(closure_region_requirements) = closure_region_requirements {
 277                         writeln!(out, "|")?;
 278                         writeln!(out, "| Free Region Constraints")?;
 279                         for_each_region_constraint(closure_region_requirements, &mut |msg| {
 280                             writeln!(out, "| {}", msg)
 281                         })?;
 282                     }
 283                 }
 284
 285                 PassWhere::BeforeLocation(location) => {
 286                     let s = live_variable_set(
 287                         &regular_liveness_per_location[&location],
 288                         &drop_liveness_per_location[&location],
 289                     );
 290                     writeln!(
 291                         out,
 292                         "{:ALIGN$} | Live variables on entry to {:?}: {}",
 293                         "",
 294                         location,
 295                         s,
 296                         ALIGN = ALIGN
 297                     )?;
 298                 }
 299
 300                 // After each basic block, dump out the values
 301                 // that are live on exit from the basic block.
 302                 PassWhere::AfterTerminator(bb) => {
 303                     let s = live_variable_set(&liveness.regular.outs[bb], &liveness.drop.outs[bb]);
 304                     writeln!(out, "    | Live variables on exit from {:?}: {}", bb, s)?;
 305                 }
 306
 307                 PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {}
 308             }
 309             Ok(())
 310         },
 311     );
 312
 313     // Also dump the inference graph constraints as a graphviz file.
 314     let _: io::Result<()> = do catch {
 315         let mut file =
 316             pretty::create_dump_file(infcx.tcx, "regioncx.all.dot", None, "nll", &0, source)?;
 317         regioncx.dump_graphviz_raw_constraints(&mut file)?;
 318     };
 319
 320     // Also dump the inference graph constraints as a graphviz file.
 321     let _: io::Result<()> = do catch {
 322         let mut file =
 323             pretty::create_dump_file(infcx.tcx, "regioncx.scc.dot", None, "nll", &0, source)?;
 324         regioncx.dump_graphviz_scc_constraints(&mut file)?;
 325     };
 326 }
 327
 328 fn dump_annotation<'a, 'gcx, 'tcx>(
 329     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 330     mir: &Mir<'tcx>,
 331     mir_def_id: DefId,
 332     regioncx: &RegionInferenceContext,
 333     closure_region_requirements: &Option<ClosureRegionRequirements>,
 334     errors_buffer: &mut Vec<Diagnostic>,
 335 ) {
 336     let tcx = infcx.tcx;
 337     let base_def_id = tcx.closure_base_def_id(mir_def_id);
 338     if !tcx.has_attr(base_def_id, "rustc_regions") {
 339         return;
 340     }
 341
 342     // When the enclosing function is tagged with `#[rustc_regions]`,
 343     // we dump out various bits of state as warnings. This is useful
 344     // for verifying that the compiler is behaving as expected.  These
 345     // warnings focus on the closure region requirements -- for
 346     // viewing the intraprocedural state, the -Zdump-mir output is
 347     // better.
 348
 349     if let Some(closure_region_requirements) = closure_region_requirements {
 350         let mut err = tcx
 351             .sess
 352             .diagnostic()
 353             .span_note_diag(mir.span, "External requirements");
 354
 355         regioncx.annotate(&mut err);
 356
 357         err.note(&format!(
 358             "number of external vids: {}",
 359             closure_region_requirements.num_external_vids
 360         ));
 361
 362         // Dump the region constraints we are imposing *between* those
 363         // newly created variables.
 364         for_each_region_constraint(closure_region_requirements, &mut |msg| {
 365             err.note(msg);
 366             Ok(())
 367         }).unwrap();
 368
 369         err.buffer(errors_buffer);
 370     } else {
 371         let mut err = tcx
 372             .sess
 373             .diagnostic()
 374             .span_note_diag(mir.span, "No external requirements");
 375         regioncx.annotate(&mut err);
 376
 377         err.buffer(errors_buffer);
 378     }
 379 }
 380
 381 fn for_each_region_constraint(
 382     closure_region_requirements: &ClosureRegionRequirements,
 383     with_msg: &mut dyn FnMut(&str) -> io::Result<()>,
 384 ) -> io::Result<()> {
 385     for req in &closure_region_requirements.outlives_requirements {
 386         let subject: &dyn Debug = match &req.subject {
 387             ClosureOutlivesSubject::Region(subject) => subject,
 388             ClosureOutlivesSubject::Ty(ty) => ty,
 389         };
 390         with_msg(&format!(
 391             "where {:?}: {:?}",
 392             subject, req.outlived_free_region,
 393         ))?;
 394     }
 395     Ok(())
 396 }
 397
 398 /// Right now, we piggy back on the `ReVar` to store our NLL inference
 399 /// regions. These are indexed with `RegionVid`. This method will
 400 /// assert that the region is a `ReVar` and extract its internal index.
 401 /// This is reasonable because in our MIR we replace all universal regions
 402 /// with inference variables.
 403 pub trait ToRegionVid {
 404     fn to_region_vid(self) -> RegionVid;
 405 }
 406
 407 impl<'tcx> ToRegionVid for &'tcx RegionKind {
 408     fn to_region_vid(self) -> RegionVid {
 409         if let ty::ReVar(vid) = self {
 410             *vid
 411         } else {
 412             bug!("region is not an ReVar: {:?}", self)
 413         }
 414     }
 415 }
 416
 417 impl ToRegionVid for RegionVid {
 418     fn to_region_vid(self) -> RegionVid {
 419         self
 420     }
 421 }
 422
 423 fn live_variable_set(
 424     regular: &LiveVarSet<LocalWithRegion>,
 425     drops: &LiveVarSet<LocalWithRegion>
 426 ) -> String {
 427     // sort and deduplicate:
 428     let all_locals: BTreeSet<_> = regular.iter().chain(drops.iter()).collect();
 429
 430     // construct a string with each local, including `(drop)` if it is
 431     // only dropped, versus a regular use.
 432     let mut string = String::new();
 433     for local in all_locals {
 434         string.push_str(&format!("{:?}", local));
 435
 436         if !regular.contains(&local) {
 437             assert!(drops.contains(&local));
 438             string.push_str(" (drop)");
 439         }
 440
 441         string.push_str(", ");
 442     }
 443
 444     let len = if string.is_empty() {
 445         0
 446     } else {
 447         string.len() - 2
 448     };
 449
 450     format!("[{}]", &string[..len])
 451 }