1 #![deny(rustc::untranslatable_diagnostic)]
2 #![deny(rustc::diagnostic_outside_of_impl)]
3 //! The entry point of the NLL borrow checker.
5 use rustc_data_structures::vec_map::VecMap;
6 use rustc_hir::def_id::LocalDefId;
7 use rustc_index::vec::IndexVec;
8 use rustc_infer::infer::InferCtxt;
9 use rustc_middle::mir::{create_dump_file, dump_enabled, dump_mir, PassWhere};
10 use rustc_middle::mir::{
11 BasicBlock, Body, ClosureOutlivesSubject, ClosureRegionRequirements, LocalKind, Location,
14 use rustc_middle::ty::{self, OpaqueHiddenType, Region, RegionVid};
15 use rustc_span::symbol::sym;
19 use std::path::PathBuf;
21 use std::str::FromStr;
23 use polonius_engine::{Algorithm, Output};
25 use rustc_mir_dataflow::impls::MaybeInitializedPlaces;
26 use rustc_mir_dataflow::move_paths::{InitKind, InitLocation, MoveData};
27 use rustc_mir_dataflow::ResultsCursor;
30 borrow_set::BorrowSet,
31 constraint_generation,
32 diagnostics::RegionErrors,
33 facts::{AllFacts, AllFactsExt, RustcFacts},
35 location::LocationTable,
36 region_infer::{values::RegionValueElements, RegionInferenceContext},
38 type_check::{self, MirTypeckRegionConstraints, MirTypeckResults},
39 universal_regions::UniversalRegions,
43 pub type PoloniusOutput = Output<RustcFacts>;
45 /// The output of `nll::compute_regions`. This includes the computed `RegionInferenceContext`, any
46 /// closure requirements to propagate, and any generated errors.
47 pub(crate) struct NllOutput<'tcx> {
48 pub regioncx: RegionInferenceContext<'tcx>,
49 pub opaque_type_values: VecMap<LocalDefId, OpaqueHiddenType<'tcx>>,
50 pub polonius_input: Option<Box<AllFacts>>,
51 pub polonius_output: Option<Rc<PoloniusOutput>>,
52 pub opt_closure_req: Option<ClosureRegionRequirements<'tcx>>,
53 pub nll_errors: RegionErrors<'tcx>,
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 #[instrument(skip(infcx, param_env, body, promoted), level = "debug")]
60 pub(crate) fn replace_regions_in_mir<'tcx>(
61 infcx: &InferCtxt<'tcx>,
62 param_env: ty::ParamEnv<'tcx>,
63 body: &mut Body<'tcx>,
64 promoted: &mut IndexVec<Promoted, Body<'tcx>>,
65 ) -> UniversalRegions<'tcx> {
66 let def = body.source.with_opt_param().as_local().unwrap();
70 // Compute named region information. This also renumbers the inputs/outputs.
71 let universal_regions = UniversalRegions::new(infcx, def, param_env);
73 // Replace all remaining regions with fresh inference variables.
74 renumber::renumber_mir(infcx, body, promoted);
76 dump_mir(infcx.tcx, false, "renumber", &0, body, |_, _| Ok(()));
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,
91 .extend(move_data.rev_lookup.iter_locals_enumerated().map(|(l, r)| (r, l)));
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));
99 let fn_entry_start = location_table
100 .start_index(Location { block: BasicBlock::from_u32(0u32), statement_index: 0 });
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();
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
113 for successor in block_data.terminator().successors() {
114 if body[successor].is_cleanup {
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 };
122 .path_assigned_at_base
123 .push((init.path, location_table.start_index(first_statement)));
126 // In all other cases, the initialization just happens at the
127 // midpoint, like any other effect.
129 .path_assigned_at_base
130 .push((init.path, location_table.mid_index(location)));
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));
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
145 all_facts.path_moved_at_base.push((path, fn_entry_start));
150 // deinitialisation is assumed to always happen!
153 .extend(move_data.moves.iter().map(|mo| (mo.path, location_table.mid_index(mo.source))));
156 /// Computes the (non-lexical) regions from the input MIR.
158 /// This may result in errors being reported.
159 pub(crate) fn compute_regions<'cx, 'tcx>(
160 infcx: &InferCtxt<'tcx>,
161 universal_regions: UniversalRegions<'tcx>,
163 promoted: &IndexVec<Promoted, Body<'tcx>>,
164 location_table: &LocationTable,
165 param_env: ty::ParamEnv<'tcx>,
166 flow_inits: &mut ResultsCursor<'cx, 'tcx, MaybeInitializedPlaces<'cx, 'tcx>>,
167 move_data: &MoveData<'tcx>,
168 borrow_set: &BorrowSet<'tcx>,
169 upvars: &[Upvar<'tcx>],
171 ) -> NllOutput<'tcx> {
173 (use_polonius || AllFacts::enabled(infcx.tcx)).then_some(AllFacts::default());
175 let universal_regions = Rc::new(universal_regions);
177 let elements = &Rc::new(RegionValueElements::new(&body));
179 // Run the MIR type-checker.
180 let MirTypeckResults { constraints, universal_region_relations, opaque_type_values } =
181 type_check::type_check(
197 if let Some(all_facts) = &mut all_facts {
198 let _prof_timer = infcx.tcx.prof.generic_activity("polonius_fact_generation");
199 all_facts.universal_region.extend(universal_regions.universal_regions());
200 populate_polonius_move_facts(all_facts, move_data, location_table, &body);
202 // Emit universal regions facts, and their relations, for Polonius.
204 // 1: universal regions are modeled in Polonius as a pair:
205 // - the universal region vid itself.
206 // - a "placeholder loan" associated to this universal region. Since they don't exist in
207 // the `borrow_set`, their `BorrowIndex` are synthesized as the universal region index
208 // added to the existing number of loans, as if they succeeded them in the set.
210 let borrow_count = borrow_set.len();
212 "compute_regions: polonius placeholders, num_universals={}, borrow_count={}",
213 universal_regions.len(),
217 for universal_region in universal_regions.universal_regions() {
218 let universal_region_idx = universal_region.index();
219 let placeholder_loan_idx = borrow_count + universal_region_idx;
220 all_facts.placeholder.push((universal_region, placeholder_loan_idx.into()));
223 // 2: the universal region relations `outlives` constraints are emitted as
224 // `known_placeholder_subset` facts.
225 for (fr1, fr2) in universal_region_relations.known_outlives() {
228 "compute_regions: emitting polonius `known_placeholder_subset` \
232 all_facts.known_placeholder_subset.push((fr1, fr2));
237 // Create the region inference context, taking ownership of the
238 // region inference data that was contained in `infcx`, and the
239 // base constraints generated by the type-check.
240 let var_origins = infcx.take_region_var_origins();
241 let MirTypeckRegionConstraints {
243 placeholder_index_to_region: _,
244 mut liveness_constraints,
245 outlives_constraints,
250 let placeholder_indices = Rc::new(placeholder_indices);
252 constraint_generation::generate_constraints(
254 &mut liveness_constraints,
261 let mut regioncx = RegionInferenceContext::new(
265 universal_region_relations,
266 outlives_constraints,
270 liveness_constraints,
274 // Generate various additional constraints.
275 invalidation::generate_invalidates(infcx.tcx, &mut all_facts, location_table, body, borrow_set);
277 let def_id = body.source.def_id();
279 // Dump facts if requested.
280 let polonius_output = all_facts.as_ref().and_then(|all_facts| {
281 if infcx.tcx.sess.opts.unstable_opts.nll_facts {
282 let def_path = infcx.tcx.def_path(def_id);
283 let dir_path = PathBuf::from(&infcx.tcx.sess.opts.unstable_opts.nll_facts_dir)
284 .join(def_path.to_filename_friendly_no_crate());
285 all_facts.write_to_dir(dir_path, location_table).unwrap();
290 env::var("POLONIUS_ALGORITHM").unwrap_or_else(|_| String::from("Hybrid"));
291 let algorithm = Algorithm::from_str(&algorithm).unwrap();
292 debug!("compute_regions: using polonius algorithm {:?}", algorithm);
293 let _prof_timer = infcx.tcx.prof.generic_activity("polonius_analysis");
294 Some(Rc::new(Output::compute(&all_facts, algorithm, false)))
300 // Solve the region constraints.
301 let (closure_region_requirements, nll_errors) =
302 regioncx.solve(infcx, param_env, &body, polonius_output.clone());
304 if !nll_errors.is_empty() {
305 // Suppress unhelpful extra errors in `infer_opaque_types`.
306 infcx.set_tainted_by_errors(infcx.tcx.sess.delay_span_bug(
308 "`compute_regions` tainted `infcx` with errors but did not emit any errors",
312 let remapped_opaque_tys = regioncx.infer_opaque_types(&infcx, opaque_type_values);
316 opaque_type_values: remapped_opaque_tys,
317 polonius_input: all_facts.map(Box::new),
319 opt_closure_req: closure_region_requirements,
324 pub(super) fn dump_mir_results<'tcx>(
325 infcx: &InferCtxt<'tcx>,
327 regioncx: &RegionInferenceContext<'tcx>,
328 closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
330 if !dump_enabled(infcx.tcx, "nll", body.source.def_id()) {
334 dump_mir(infcx.tcx, false, "nll", &0, body, |pass_where, out| {
336 // Before the CFG, dump out the values for each region variable.
337 PassWhere::BeforeCFG => {
338 regioncx.dump_mir(infcx.tcx, out)?;
341 if let Some(closure_region_requirements) = closure_region_requirements {
342 writeln!(out, "| Free Region Constraints")?;
343 for_each_region_constraint(closure_region_requirements, &mut |msg| {
344 writeln!(out, "| {}", msg)
350 PassWhere::BeforeLocation(_) => {}
352 PassWhere::AfterTerminator(_) => {}
354 PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {}
359 // Also dump the inference graph constraints as a graphviz file.
360 let _: io::Result<()> = try {
361 let mut file = create_dump_file(infcx.tcx, "regioncx.all.dot", false, "nll", &0, body)?;
362 regioncx.dump_graphviz_raw_constraints(&mut file)?;
365 // Also dump the inference graph constraints as a graphviz file.
366 let _: io::Result<()> = try {
367 let mut file = create_dump_file(infcx.tcx, "regioncx.scc.dot", false, "nll", &0, body)?;
368 regioncx.dump_graphviz_scc_constraints(&mut file)?;
372 pub(super) fn dump_annotation<'tcx>(
373 infcx: &InferCtxt<'tcx>,
375 regioncx: &RegionInferenceContext<'tcx>,
376 closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
377 opaque_type_values: &VecMap<LocalDefId, OpaqueHiddenType<'tcx>>,
378 errors: &mut crate::error::BorrowckErrors<'tcx>,
381 let base_def_id = tcx.typeck_root_def_id(body.source.def_id());
382 if !tcx.has_attr(base_def_id, sym::rustc_regions) {
386 // When the enclosing function is tagged with `#[rustc_regions]`,
387 // we dump out various bits of state as warnings. This is useful
388 // for verifying that the compiler is behaving as expected. These
389 // warnings focus on the closure region requirements -- for
390 // viewing the intraprocedural state, the -Zdump-mir output is
393 let def_span = tcx.def_span(body.source.def_id());
394 let mut err = if let Some(closure_region_requirements) = closure_region_requirements {
395 let mut err = tcx.sess.diagnostic().span_note_diag(def_span, "external requirements");
397 regioncx.annotate(tcx, &mut err);
400 "number of external vids: {}",
401 closure_region_requirements.num_external_vids
404 // Dump the region constraints we are imposing *between* those
405 // newly created variables.
406 for_each_region_constraint(closure_region_requirements, &mut |msg| {
414 let mut err = tcx.sess.diagnostic().span_note_diag(def_span, "no external requirements");
415 regioncx.annotate(tcx, &mut err);
420 if !opaque_type_values.is_empty() {
421 err.note(&format!("Inferred opaque type values:\n{:#?}", opaque_type_values));
424 errors.buffer_non_error_diag(err);
427 fn for_each_region_constraint(
428 closure_region_requirements: &ClosureRegionRequirements<'_>,
429 with_msg: &mut dyn FnMut(&str) -> io::Result<()>,
430 ) -> io::Result<()> {
431 for req in &closure_region_requirements.outlives_requirements {
432 let subject: &dyn Debug = match &req.subject {
433 ClosureOutlivesSubject::Region(subject) => subject,
434 ClosureOutlivesSubject::Ty(ty) => ty,
436 with_msg(&format!("where {:?}: {:?}", subject, req.outlived_free_region,))?;
441 /// Right now, we piggy back on the `ReVar` to store our NLL inference
442 /// regions. These are indexed with `RegionVid`. This method will
443 /// assert that the region is a `ReVar` and extract its internal index.
444 /// This is reasonable because in our MIR we replace all universal regions
445 /// with inference variables.
446 pub trait ToRegionVid {
447 fn to_region_vid(self) -> RegionVid;
450 impl<'tcx> ToRegionVid for Region<'tcx> {
451 fn to_region_vid(self) -> RegionVid {
452 if let ty::ReVar(vid) = *self { vid } else { bug!("region is not an ReVar: {:?}", self) }
456 impl ToRegionVid for RegionVid {
457 fn to_region_vid(self) -> RegionVid {
462 pub(crate) trait ConstraintDescription {
463 fn description(&self) -> &'static str;