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