src/librustc_mir/borrow_check/nll.rs

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