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