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