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