compiler/rustc_borrowck/src/nll.rs

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