src/librustc_mir/borrow_check/nll.rs

   1 //! The entry point of the NLL borrow checker.
   2
   3 use rustc::mir::{
   4     BasicBlock, Body, BodyAndCache, ClosureOutlivesSubject, ClosureRegionRequirements, LocalKind,
   5     Location, Promoted, ReadOnlyBodyAndCache,
   6 };
   7 use rustc::ty::{self, RegionKind, RegionVid};
   8 use rustc_data_structures::fx::FxHashMap;
   9 use rustc_errors::Diagnostic;
  10 use rustc_hir::def_id::DefId;
  11 use rustc_index::vec::IndexVec;
  12 use rustc_infer::infer::InferCtxt;
  13 use rustc_span::symbol::sym;
  14 use std::env;
  15 use std::fmt::Debug;
  16 use std::io;
  17 use std::path::PathBuf;
  18 use std::rc::Rc;
  19 use std::str::FromStr;
  20
  21 use self::mir_util::PassWhere;
  22 use polonius_engine::{Algorithm, Output};
  23
  24 use crate::dataflow::generic::ResultsCursor;
  25 use crate::dataflow::move_paths::{InitKind, InitLocation, MoveData};
  26 use crate::dataflow::MaybeInitializedPlaces;
  27 use crate::transform::MirSource;
  28 use crate::util as mir_util;
  29 use crate::util::pretty;
  30
  31 use crate::borrow_check::{
  32     borrow_set::BorrowSet,
  33     constraint_generation,
  34     diagnostics::RegionErrors,
  35     facts::{AllFacts, AllFactsExt, RustcFacts},
  36     invalidation,
  37     location::LocationTable,
  38     region_infer::{values::RegionValueElements, RegionInferenceContext},
  39     renumber,
  40     type_check::{self, MirTypeckRegionConstraints, MirTypeckResults},
  41     universal_regions::UniversalRegions,
  42 };
  43
  44 crate type PoloniusOutput = Output<RustcFacts>;
  45
  46 /// The output of `nll::compute_regions`. This includes the computed `RegionInferenceContext`, any
  47 /// closure requirements to propagate, and any generated errors.
  48 crate struct NllOutput<'tcx> {
  49     pub regioncx: RegionInferenceContext<'tcx>,
  50     pub opaque_type_values: FxHashMap<DefId, ty::ResolvedOpaqueTy<'tcx>>,
  51     pub polonius_output: Option<Rc<PoloniusOutput>>,
  52     pub opt_closure_req: Option<ClosureRegionRequirements<'tcx>>,
  53     pub nll_errors: RegionErrors<'tcx>,
  54 }
  55
  56 /// Rewrites the regions in the MIR to use NLL variables, also scraping out the set of universal
  57 /// regions (e.g., region parameters) declared on the function. That set will need to be given to
  58 /// `compute_regions`.
  59 pub(in crate::borrow_check) fn replace_regions_in_mir<'cx, 'tcx>(
  60     infcx: &InferCtxt<'cx, 'tcx>,
  61     def_id: DefId,
  62     param_env: ty::ParamEnv<'tcx>,
  63     body: &mut BodyAndCache<'tcx>,
  64     promoted: &mut IndexVec<Promoted, BodyAndCache<'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, body, promoted);
  73
  74     let source = MirSource::item(def_id);
  75     mir_util::dump_mir(infcx.tcx, None, "renumber", &0, source, body, |_, _| Ok(()));
  76
  77     universal_regions
  78 }
  79
  80 // This function populates an AllFacts instance with base facts related to
  81 // MovePaths and needed for the move analysis.
  82 fn populate_polonius_move_facts(
  83     all_facts: &mut AllFacts,
  84     move_data: &MoveData<'_>,
  85     location_table: &LocationTable,
  86     body: &Body<'_>,
  87 ) {
  88     all_facts
  89         .path_belongs_to_var
  90         .extend(move_data.rev_lookup.iter_locals_enumerated().map(|(v, &m)| (m, v)));
  91
  92     for (child, move_path) in move_data.move_paths.iter_enumerated() {
  93         all_facts
  94             .child
  95             .extend(move_path.parents(&move_data.move_paths).iter().map(|&parent| (child, parent)));
  96     }
  97
  98     // initialized_at
  99     for init in move_data.inits.iter() {
 100         match init.location {
 101             InitLocation::Statement(location) => {
 102                 let block_data = &body[location.block];
 103                 let is_terminator = location.statement_index == block_data.statements.len();
 104
 105                 if is_terminator && init.kind == InitKind::NonPanicPathOnly {
 106                     // We are at the terminator of an init that has a panic path,
 107                     // and where the init should not happen on panic
 108
 109                     for &successor in block_data.terminator().successors() {
 110                         if body[successor].is_cleanup {
 111                             continue;
 112                         }
 113
 114                         // The initialization happened in (or rather, when arriving at)
 115                         // the successors, but not in the unwind block.
 116                         let first_statement = Location { block: successor, statement_index: 0 };
 117                         all_facts
 118                             .initialized_at
 119                             .push((init.path, location_table.start_index(first_statement)));
 120                     }
 121                 } else {
 122                     // In all other cases, the initialization just happens at the
 123                     // midpoint, like any other effect.
 124                     all_facts.initialized_at.push((init.path, location_table.mid_index(location)));
 125                 }
 126             }
 127             // Arguments are initialized on function entry
 128             InitLocation::Argument(local) => {
 129                 assert!(body.local_kind(local) == LocalKind::Arg);
 130                 let fn_entry = Location { block: BasicBlock::from_u32(0u32), statement_index: 0 };
 131                 all_facts.initialized_at.push((init.path, location_table.start_index(fn_entry)));
 132             }
 133         }
 134     }
 135
 136     // moved_out_at
 137     // deinitialisation is assumed to always happen!
 138     all_facts
 139         .moved_out_at
 140         .extend(move_data.moves.iter().map(|mo| (mo.path, location_table.mid_index(mo.source))));
 141 }
 142
 143 /// Computes the (non-lexical) regions from the input MIR.
 144 ///
 145 /// This may result in errors being reported.
 146 pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
 147     infcx: &InferCtxt<'cx, 'tcx>,
 148     def_id: DefId,
 149     universal_regions: UniversalRegions<'tcx>,
 150     body: ReadOnlyBodyAndCache<'_, 'tcx>,
 151     promoted: &IndexVec<Promoted, ReadOnlyBodyAndCache<'_, 'tcx>>,
 152     location_table: &LocationTable,
 153     param_env: ty::ParamEnv<'tcx>,
 154     flow_inits: &mut ResultsCursor<'cx, 'tcx, MaybeInitializedPlaces<'cx, 'tcx>>,
 155     move_data: &MoveData<'tcx>,
 156     borrow_set: &BorrowSet<'tcx>,
 157 ) -> NllOutput<'tcx> {
 158     let mut all_facts = AllFacts::enabled(infcx.tcx).then_some(AllFacts::default());
 159
 160     let universal_regions = Rc::new(universal_regions);
 161
 162     let elements = &Rc::new(RegionValueElements::new(&body));
 163
 164     // Run the MIR type-checker.
 165     let MirTypeckResults { constraints, universal_region_relations, opaque_type_values } =
 166         type_check::type_check(
 167             infcx,
 168             param_env,
 169             body,
 170             promoted,
 171             def_id,
 172             &universal_regions,
 173             location_table,
 174             borrow_set,
 175             &mut all_facts,
 176             flow_inits,
 177             move_data,
 178             elements,
 179         );
 180
 181     if let Some(all_facts) = &mut all_facts {
 182         let _prof_timer = infcx.tcx.prof.generic_activity("polonius_fact_generation");
 183         all_facts.universal_region.extend(universal_regions.universal_regions());
 184         populate_polonius_move_facts(all_facts, move_data, location_table, &body);
 185
 186         // Emit universal regions facts, and their relations, for Polonius.
 187         //
 188         // 1: universal regions are modeled in Polonius as a pair:
 189         // - the universal region vid itself.
 190         // - a "placeholder loan" associated to this universal region. Since they don't exist in
 191         //   the `borrow_set`, their `BorrowIndex` are synthesized as the universal region index
 192         //   added to the existing number of loans, as if they succeeded them in the set.
 193         //
 194         let borrow_count = borrow_set.borrows.len();
 195         debug!(
 196             "compute_regions: polonius placeholders, num_universals={}, borrow_count={}",
 197             universal_regions.len(),
 198             borrow_count
 199         );
 200
 201         for universal_region in universal_regions.universal_regions() {
 202             let universal_region_idx = universal_region.index();
 203             let placeholder_loan_idx = borrow_count + universal_region_idx;
 204             all_facts.placeholder.push((universal_region, placeholder_loan_idx.into()));
 205         }
 206
 207         // 2: the universal region relations `outlives` constraints are emitted as
 208         //  `known_subset` facts.
 209         for (fr1, fr2) in universal_region_relations.known_outlives() {
 210             if fr1 != fr2 {
 211                 debug!(
 212                     "compute_regions: emitting polonius `known_subset` fr1={:?}, fr2={:?}",
 213                     fr1, fr2
 214                 );
 215                 all_facts.known_subset.push((*fr1, *fr2));
 216             }
 217         }
 218     }
 219
 220     // Create the region inference context, taking ownership of the
 221     // region inference data that was contained in `infcx`, and the
 222     // base constraints generated by the type-check.
 223     let var_origins = infcx.take_region_var_origins();
 224     let MirTypeckRegionConstraints {
 225         placeholder_indices,
 226         placeholder_index_to_region: _,
 227         mut liveness_constraints,
 228         outlives_constraints,
 229         member_constraints,
 230         closure_bounds_mapping,
 231         type_tests,
 232     } = constraints;
 233     let placeholder_indices = Rc::new(placeholder_indices);
 234
 235     constraint_generation::generate_constraints(
 236         infcx,
 237         &mut liveness_constraints,
 238         &mut all_facts,
 239         location_table,
 240         &body,
 241         borrow_set,
 242     );
 243
 244     let mut regioncx = RegionInferenceContext::new(
 245         var_origins,
 246         universal_regions,
 247         placeholder_indices,
 248         universal_region_relations,
 249         outlives_constraints,
 250         member_constraints,
 251         closure_bounds_mapping,
 252         type_tests,
 253         liveness_constraints,
 254         elements,
 255     );
 256
 257     // Generate various additional constraints.
 258     invalidation::generate_invalidates(infcx.tcx, &mut all_facts, location_table, body, borrow_set);
 259
 260     // Dump facts if requested.
 261     let polonius_output = all_facts.and_then(|all_facts| {
 262         if infcx.tcx.sess.opts.debugging_opts.nll_facts {
 263             let def_path = infcx.tcx.hir().def_path(def_id);
 264             let dir_path =
 265                 PathBuf::from("nll-facts").join(def_path.to_filename_friendly_no_crate());
 266             all_facts.write_to_dir(dir_path, location_table).unwrap();
 267         }
 268
 269         if infcx.tcx.sess.opts.debugging_opts.polonius {
 270             let algorithm =
 271                 env::var("POLONIUS_ALGORITHM").unwrap_or_else(|_| String::from("Naive"));
 272             let algorithm = Algorithm::from_str(&algorithm).unwrap();
 273             debug!("compute_regions: using polonius algorithm {:?}", algorithm);
 274             let _prof_timer = infcx.tcx.prof.generic_activity("polonius_analysis");
 275             Some(Rc::new(Output::compute(&all_facts, algorithm, false)))
 276         } else {
 277             None
 278         }
 279     });
 280
 281     // Solve the region constraints.
 282     let (closure_region_requirements, nll_errors) =
 283         regioncx.solve(infcx, &body, def_id, polonius_output.clone());
 284
 285     if !nll_errors.is_empty() {
 286         // Suppress unhelpful extra errors in `infer_opaque_types`.
 287         infcx.set_tainted_by_errors();
 288     }
 289
 290     let remapped_opaque_tys = regioncx.infer_opaque_types(&infcx, opaque_type_values, body.span);
 291
 292     NllOutput {
 293         regioncx,
 294         opaque_type_values: remapped_opaque_tys,
 295         polonius_output,
 296         opt_closure_req: closure_region_requirements,
 297         nll_errors,
 298     }
 299 }
 300
 301 pub(super) fn dump_mir_results<'a, 'tcx>(
 302     infcx: &InferCtxt<'a, 'tcx>,
 303     source: MirSource<'tcx>,
 304     body: &Body<'tcx>,
 305     regioncx: &RegionInferenceContext<'_>,
 306     closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
 307 ) {
 308     if !mir_util::dump_enabled(infcx.tcx, "nll", source) {
 309         return;
 310     }
 311
 312     mir_util::dump_mir(infcx.tcx, None, "nll", &0, source, body, |pass_where, out| {
 313         match pass_where {
 314             // Before the CFG, dump out the values for each region variable.
 315             PassWhere::BeforeCFG => {
 316                 regioncx.dump_mir(out)?;
 317                 writeln!(out, "|")?;
 318
 319                 if let Some(closure_region_requirements) = closure_region_requirements {
 320                     writeln!(out, "| Free Region Constraints")?;
 321                     for_each_region_constraint(closure_region_requirements, &mut |msg| {
 322                         writeln!(out, "| {}", msg)
 323                     })?;
 324                     writeln!(out, "|")?;
 325                 }
 326             }
 327
 328             PassWhere::BeforeLocation(_) => {}
 329
 330             PassWhere::AfterTerminator(_) => {}
 331
 332             PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {}
 333         }
 334         Ok(())
 335     });
 336
 337     // Also dump the inference graph constraints as a graphviz file.
 338     let _: io::Result<()> = try {
 339         let mut file =
 340             pretty::create_dump_file(infcx.tcx, "regioncx.all.dot", None, "nll", &0, source)?;
 341         regioncx.dump_graphviz_raw_constraints(&mut file)?;
 342     };
 343
 344     // Also dump the inference graph constraints as a graphviz file.
 345     let _: io::Result<()> = try {
 346         let mut file =
 347             pretty::create_dump_file(infcx.tcx, "regioncx.scc.dot", None, "nll", &0, source)?;
 348         regioncx.dump_graphviz_scc_constraints(&mut file)?;
 349     };
 350 }
 351
 352 pub(super) fn dump_annotation<'a, 'tcx>(
 353     infcx: &InferCtxt<'a, 'tcx>,
 354     body: &Body<'tcx>,
 355     mir_def_id: DefId,
 356     regioncx: &RegionInferenceContext<'tcx>,
 357     closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
 358     opaque_type_values: &FxHashMap<DefId, ty::ResolvedOpaqueTy<'tcx>>,
 359     errors_buffer: &mut Vec<Diagnostic>,
 360 ) {
 361     let tcx = infcx.tcx;
 362     let base_def_id = tcx.closure_base_def_id(mir_def_id);
 363     if !tcx.has_attr(base_def_id, sym::rustc_regions) {
 364         return;
 365     }
 366
 367     // When the enclosing function is tagged with `#[rustc_regions]`,
 368     // we dump out various bits of state as warnings. This is useful
 369     // for verifying that the compiler is behaving as expected.  These
 370     // warnings focus on the closure region requirements -- for
 371     // viewing the intraprocedural state, the -Zdump-mir output is
 372     // better.
 373
 374     let mut err = if let Some(closure_region_requirements) = closure_region_requirements {
 375         let mut err = tcx.sess.diagnostic().span_note_diag(body.span, "external requirements");
 376
 377         regioncx.annotate(tcx, &mut err);
 378
 379         err.note(&format!(
 380             "number of external vids: {}",
 381             closure_region_requirements.num_external_vids
 382         ));
 383
 384         // Dump the region constraints we are imposing *between* those
 385         // newly created variables.
 386         for_each_region_constraint(closure_region_requirements, &mut |msg| {
 387             err.note(msg);
 388             Ok(())
 389         })
 390         .unwrap();
 391
 392         err
 393     } else {
 394         let mut err = tcx.sess.diagnostic().span_note_diag(body.span, "no external requirements");
 395         regioncx.annotate(tcx, &mut err);
 396
 397         err
 398     };
 399
 400     if !opaque_type_values.is_empty() {
 401         err.note(&format!("Inferred opaque type values:\n{:#?}", opaque_type_values));
 402     }
 403
 404     err.buffer(errors_buffer);
 405 }
 406
 407 fn for_each_region_constraint(
 408     closure_region_requirements: &ClosureRegionRequirements<'_>,
 409     with_msg: &mut dyn FnMut(&str) -> io::Result<()>,
 410 ) -> io::Result<()> {
 411     for req in &closure_region_requirements.outlives_requirements {
 412         let subject: &dyn Debug = match &req.subject {
 413             ClosureOutlivesSubject::Region(subject) => subject,
 414             ClosureOutlivesSubject::Ty(ty) => ty,
 415         };
 416         with_msg(&format!("where {:?}: {:?}", subject, req.outlived_free_region,))?;
 417     }
 418     Ok(())
 419 }
 420
 421 /// Right now, we piggy back on the `ReVar` to store our NLL inference
 422 /// regions. These are indexed with `RegionVid`. This method will
 423 /// assert that the region is a `ReVar` and extract its internal index.
 424 /// This is reasonable because in our MIR we replace all universal regions
 425 /// with inference variables.
 426 pub trait ToRegionVid {
 427     fn to_region_vid(self) -> RegionVid;
 428 }
 429
 430 impl<'tcx> ToRegionVid for &'tcx RegionKind {
 431     fn to_region_vid(self) -> RegionVid {
 432         if let ty::ReVar(vid) = self { *vid } else { bug!("region is not an ReVar: {:?}", self) }
 433     }
 434 }
 435
 436 impl ToRegionVid for RegionVid {
 437     fn to_region_vid(self) -> RegionVid {
 438         self
 439     }
 440 }
 441
 442 crate trait ConstraintDescription {
 443     fn description(&self) -> &'static str;
 444 }