From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_borrowck/src/nll.rs | 462 +++++++++++++++++++++++++++++++++++++ 1 file changed, 462 insertions(+) create mode 100644 compiler/rustc_borrowck/src/nll.rs (limited to 'compiler/rustc_borrowck/src/nll.rs') diff --git a/compiler/rustc_borrowck/src/nll.rs b/compiler/rustc_borrowck/src/nll.rs new file mode 100644 index 000000000..0961203d7 --- /dev/null +++ b/compiler/rustc_borrowck/src/nll.rs @@ -0,0 +1,462 @@ +//! The entry point of the NLL borrow checker. + +use rustc_data_structures::vec_map::VecMap; +use rustc_hir::def_id::LocalDefId; +use rustc_index::vec::IndexVec; +use rustc_infer::infer::InferCtxt; +use rustc_middle::mir::{create_dump_file, dump_enabled, dump_mir, PassWhere}; +use rustc_middle::mir::{ + BasicBlock, Body, ClosureOutlivesSubject, ClosureRegionRequirements, LocalKind, Location, + Promoted, +}; +use rustc_middle::ty::{self, OpaqueHiddenType, Region, RegionVid}; +use rustc_span::symbol::sym; +use std::env; +use std::fmt::Debug; +use std::io; +use std::path::PathBuf; +use std::rc::Rc; +use std::str::FromStr; + +use polonius_engine::{Algorithm, Output}; + +use rustc_mir_dataflow::impls::MaybeInitializedPlaces; +use rustc_mir_dataflow::move_paths::{InitKind, InitLocation, MoveData}; +use rustc_mir_dataflow::ResultsCursor; + +use crate::{ + borrow_set::BorrowSet, + constraint_generation, + diagnostics::RegionErrors, + facts::{AllFacts, AllFactsExt, RustcFacts}, + invalidation, + location::LocationTable, + region_infer::{values::RegionValueElements, RegionInferenceContext}, + renumber, + type_check::{self, MirTypeckRegionConstraints, MirTypeckResults}, + universal_regions::UniversalRegions, + Upvar, +}; + +pub type PoloniusOutput = Output; + +/// The output of `nll::compute_regions`. This includes the computed `RegionInferenceContext`, any +/// closure requirements to propagate, and any generated errors. +pub(crate) struct NllOutput<'tcx> { + pub regioncx: RegionInferenceContext<'tcx>, + pub opaque_type_values: VecMap>, + pub polonius_input: Option>, + pub polonius_output: Option>, + pub opt_closure_req: Option>, + pub nll_errors: RegionErrors<'tcx>, +} + +/// Rewrites the regions in the MIR to use NLL variables, also scraping out the set of universal +/// regions (e.g., region parameters) declared on the function. That set will need to be given to +/// `compute_regions`. +#[instrument(skip(infcx, param_env, body, promoted), level = "debug")] +pub(crate) fn replace_regions_in_mir<'cx, 'tcx>( + infcx: &InferCtxt<'cx, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + body: &mut Body<'tcx>, + promoted: &mut IndexVec>, +) -> UniversalRegions<'tcx> { + let def = body.source.with_opt_param().as_local().unwrap(); + + debug!(?def); + + // Compute named region information. This also renumbers the inputs/outputs. + let universal_regions = UniversalRegions::new(infcx, def, param_env); + + // Replace all remaining regions with fresh inference variables. + renumber::renumber_mir(infcx, body, promoted); + + dump_mir(infcx.tcx, None, "renumber", &0, body, |_, _| Ok(())); + + universal_regions +} + +// This function populates an AllFacts instance with base facts related to +// MovePaths and needed for the move analysis. +fn populate_polonius_move_facts( + all_facts: &mut AllFacts, + move_data: &MoveData<'_>, + location_table: &LocationTable, + body: &Body<'_>, +) { + all_facts + .path_is_var + .extend(move_data.rev_lookup.iter_locals_enumerated().map(|(l, r)| (r, l))); + + for (child, move_path) in move_data.move_paths.iter_enumerated() { + if let Some(parent) = move_path.parent { + all_facts.child_path.push((child, parent)); + } + } + + let fn_entry_start = location_table + .start_index(Location { block: BasicBlock::from_u32(0u32), statement_index: 0 }); + + // initialized_at + for init in move_data.inits.iter() { + match init.location { + InitLocation::Statement(location) => { + let block_data = &body[location.block]; + let is_terminator = location.statement_index == block_data.statements.len(); + + if is_terminator && init.kind == InitKind::NonPanicPathOnly { + // We are at the terminator of an init that has a panic path, + // and where the init should not happen on panic + + for successor in block_data.terminator().successors() { + if body[successor].is_cleanup { + continue; + } + + // The initialization happened in (or rather, when arriving at) + // the successors, but not in the unwind block. + let first_statement = Location { block: successor, statement_index: 0 }; + all_facts + .path_assigned_at_base + .push((init.path, location_table.start_index(first_statement))); + } + } else { + // In all other cases, the initialization just happens at the + // midpoint, like any other effect. + all_facts + .path_assigned_at_base + .push((init.path, location_table.mid_index(location))); + } + } + // Arguments are initialized on function entry + InitLocation::Argument(local) => { + assert!(body.local_kind(local) == LocalKind::Arg); + all_facts.path_assigned_at_base.push((init.path, fn_entry_start)); + } + } + } + + for (local, path) in move_data.rev_lookup.iter_locals_enumerated() { + if body.local_kind(local) != LocalKind::Arg { + // Non-arguments start out deinitialised; we simulate this with an + // initial move: + all_facts.path_moved_at_base.push((path, fn_entry_start)); + } + } + + // moved_out_at + // deinitialisation is assumed to always happen! + all_facts + .path_moved_at_base + .extend(move_data.moves.iter().map(|mo| (mo.path, location_table.mid_index(mo.source)))); +} + +/// Computes the (non-lexical) regions from the input MIR. +/// +/// This may result in errors being reported. +pub(crate) fn compute_regions<'cx, 'tcx>( + infcx: &InferCtxt<'cx, 'tcx>, + universal_regions: UniversalRegions<'tcx>, + body: &Body<'tcx>, + promoted: &IndexVec>, + location_table: &LocationTable, + param_env: ty::ParamEnv<'tcx>, + flow_inits: &mut ResultsCursor<'cx, 'tcx, MaybeInitializedPlaces<'cx, 'tcx>>, + move_data: &MoveData<'tcx>, + borrow_set: &BorrowSet<'tcx>, + upvars: &[Upvar<'tcx>], + use_polonius: bool, +) -> NllOutput<'tcx> { + let mut all_facts = + (use_polonius || AllFacts::enabled(infcx.tcx)).then_some(AllFacts::default()); + + let universal_regions = Rc::new(universal_regions); + + let elements = &Rc::new(RegionValueElements::new(&body)); + + // Run the MIR type-checker. + let MirTypeckResults { constraints, universal_region_relations, opaque_type_values } = + type_check::type_check( + infcx, + param_env, + body, + promoted, + &universal_regions, + location_table, + borrow_set, + &mut all_facts, + flow_inits, + move_data, + elements, + upvars, + use_polonius, + ); + + if let Some(all_facts) = &mut all_facts { + let _prof_timer = infcx.tcx.prof.generic_activity("polonius_fact_generation"); + all_facts.universal_region.extend(universal_regions.universal_regions()); + populate_polonius_move_facts(all_facts, move_data, location_table, &body); + + // Emit universal regions facts, and their relations, for Polonius. + // + // 1: universal regions are modeled in Polonius as a pair: + // - the universal region vid itself. + // - a "placeholder loan" associated to this universal region. Since they don't exist in + // the `borrow_set`, their `BorrowIndex` are synthesized as the universal region index + // added to the existing number of loans, as if they succeeded them in the set. + // + let borrow_count = borrow_set.len(); + debug!( + "compute_regions: polonius placeholders, num_universals={}, borrow_count={}", + universal_regions.len(), + borrow_count + ); + + for universal_region in universal_regions.universal_regions() { + let universal_region_idx = universal_region.index(); + let placeholder_loan_idx = borrow_count + universal_region_idx; + all_facts.placeholder.push((universal_region, placeholder_loan_idx.into())); + } + + // 2: the universal region relations `outlives` constraints are emitted as + // `known_placeholder_subset` facts. + for (fr1, fr2) in universal_region_relations.known_outlives() { + if fr1 != fr2 { + debug!( + "compute_regions: emitting polonius `known_placeholder_subset` \ + fr1={:?}, fr2={:?}", + fr1, fr2 + ); + all_facts.known_placeholder_subset.push((fr1, fr2)); + } + } + } + + // Create the region inference context, taking ownership of the + // region inference data that was contained in `infcx`, and the + // base constraints generated by the type-check. + let var_origins = infcx.take_region_var_origins(); + let MirTypeckRegionConstraints { + placeholder_indices, + placeholder_index_to_region: _, + mut liveness_constraints, + outlives_constraints, + member_constraints, + closure_bounds_mapping, + universe_causes, + type_tests, + } = constraints; + let placeholder_indices = Rc::new(placeholder_indices); + + constraint_generation::generate_constraints( + infcx, + &mut liveness_constraints, + &mut all_facts, + location_table, + &body, + borrow_set, + ); + + let mut regioncx = RegionInferenceContext::new( + var_origins, + universal_regions, + placeholder_indices, + universal_region_relations, + outlives_constraints, + member_constraints, + closure_bounds_mapping, + universe_causes, + type_tests, + liveness_constraints, + elements, + ); + + // Generate various additional constraints. + invalidation::generate_invalidates(infcx.tcx, &mut all_facts, location_table, body, borrow_set); + + let def_id = body.source.def_id(); + + // Dump facts if requested. + let polonius_output = all_facts.as_ref().and_then(|all_facts| { + if infcx.tcx.sess.opts.unstable_opts.nll_facts { + let def_path = infcx.tcx.def_path(def_id); + let dir_path = PathBuf::from(&infcx.tcx.sess.opts.unstable_opts.nll_facts_dir) + .join(def_path.to_filename_friendly_no_crate()); + all_facts.write_to_dir(dir_path, location_table).unwrap(); + } + + if use_polonius { + let algorithm = + env::var("POLONIUS_ALGORITHM").unwrap_or_else(|_| String::from("Hybrid")); + let algorithm = Algorithm::from_str(&algorithm).unwrap(); + debug!("compute_regions: using polonius algorithm {:?}", algorithm); + let _prof_timer = infcx.tcx.prof.generic_activity("polonius_analysis"); + Some(Rc::new(Output::compute(&all_facts, algorithm, false))) + } else { + None + } + }); + + // Solve the region constraints. + let (closure_region_requirements, nll_errors) = + regioncx.solve(infcx, param_env, &body, polonius_output.clone()); + + if !nll_errors.is_empty() { + // Suppress unhelpful extra errors in `infer_opaque_types`. + infcx.set_tainted_by_errors(); + } + + let remapped_opaque_tys = regioncx.infer_opaque_types(&infcx, opaque_type_values); + + NllOutput { + regioncx, + opaque_type_values: remapped_opaque_tys, + polonius_input: all_facts.map(Box::new), + polonius_output, + opt_closure_req: closure_region_requirements, + nll_errors, + } +} + +pub(super) fn dump_mir_results<'a, 'tcx>( + infcx: &InferCtxt<'a, 'tcx>, + body: &Body<'tcx>, + regioncx: &RegionInferenceContext<'tcx>, + closure_region_requirements: &Option>, +) { + if !dump_enabled(infcx.tcx, "nll", body.source.def_id()) { + return; + } + + dump_mir(infcx.tcx, None, "nll", &0, body, |pass_where, out| { + match pass_where { + // Before the CFG, dump out the values for each region variable. + PassWhere::BeforeCFG => { + regioncx.dump_mir(infcx.tcx, out)?; + writeln!(out, "|")?; + + if let Some(closure_region_requirements) = closure_region_requirements { + writeln!(out, "| Free Region Constraints")?; + for_each_region_constraint(closure_region_requirements, &mut |msg| { + writeln!(out, "| {}", msg) + })?; + writeln!(out, "|")?; + } + } + + PassWhere::BeforeLocation(_) => {} + + PassWhere::AfterTerminator(_) => {} + + PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {} + } + Ok(()) + }); + + // Also dump the inference graph constraints as a graphviz file. + let _: io::Result<()> = try { + let mut file = + create_dump_file(infcx.tcx, "regioncx.all.dot", None, "nll", &0, body.source)?; + regioncx.dump_graphviz_raw_constraints(&mut file)?; + }; + + // Also dump the inference graph constraints as a graphviz file. + let _: io::Result<()> = try { + let mut file = + create_dump_file(infcx.tcx, "regioncx.scc.dot", None, "nll", &0, body.source)?; + regioncx.dump_graphviz_scc_constraints(&mut file)?; + }; +} + +pub(super) fn dump_annotation<'a, 'tcx>( + infcx: &InferCtxt<'a, 'tcx>, + body: &Body<'tcx>, + regioncx: &RegionInferenceContext<'tcx>, + closure_region_requirements: &Option>, + opaque_type_values: &VecMap>, + errors: &mut crate::error::BorrowckErrors<'tcx>, +) { + let tcx = infcx.tcx; + let base_def_id = tcx.typeck_root_def_id(body.source.def_id()); + if !tcx.has_attr(base_def_id, sym::rustc_regions) { + return; + } + + // When the enclosing function is tagged with `#[rustc_regions]`, + // we dump out various bits of state as warnings. This is useful + // for verifying that the compiler is behaving as expected. These + // warnings focus on the closure region requirements -- for + // viewing the intraprocedural state, the -Zdump-mir output is + // better. + + let mut err = if let Some(closure_region_requirements) = closure_region_requirements { + let mut err = tcx.sess.diagnostic().span_note_diag(body.span, "external requirements"); + + regioncx.annotate(tcx, &mut err); + + err.note(&format!( + "number of external vids: {}", + closure_region_requirements.num_external_vids + )); + + // Dump the region constraints we are imposing *between* those + // newly created variables. + for_each_region_constraint(closure_region_requirements, &mut |msg| { + err.note(msg); + Ok(()) + }) + .unwrap(); + + err + } else { + let mut err = tcx.sess.diagnostic().span_note_diag(body.span, "no external requirements"); + regioncx.annotate(tcx, &mut err); + + err + }; + + if !opaque_type_values.is_empty() { + err.note(&format!("Inferred opaque type values:\n{:#?}", opaque_type_values)); + } + + errors.buffer_non_error_diag(err); +} + +fn for_each_region_constraint( + closure_region_requirements: &ClosureRegionRequirements<'_>, + with_msg: &mut dyn FnMut(&str) -> io::Result<()>, +) -> io::Result<()> { + for req in &closure_region_requirements.outlives_requirements { + let subject: &dyn Debug = match &req.subject { + ClosureOutlivesSubject::Region(subject) => subject, + ClosureOutlivesSubject::Ty(ty) => ty, + }; + with_msg(&format!("where {:?}: {:?}", subject, req.outlived_free_region,))?; + } + Ok(()) +} + +/// Right now, we piggy back on the `ReVar` to store our NLL inference +/// regions. These are indexed with `RegionVid`. This method will +/// assert that the region is a `ReVar` and extract its internal index. +/// This is reasonable because in our MIR we replace all universal regions +/// with inference variables. +pub trait ToRegionVid { + fn to_region_vid(self) -> RegionVid; +} + +impl<'tcx> ToRegionVid for Region<'tcx> { + fn to_region_vid(self) -> RegionVid { + if let ty::ReVar(vid) = *self { vid } else { bug!("region is not an ReVar: {:?}", self) } + } +} + +impl ToRegionVid for RegionVid { + fn to_region_vid(self) -> RegionVid { + self + } +} + +pub(crate) trait ConstraintDescription { + fn description(&self) -> &'static str; +} -- cgit v1.2.3