1 //! The entry point of the NLL borrow checker.
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
,
12 use rustc_middle
::ty
::{self, InstanceDef, RegionKind, RegionVid}
;
13 use rustc_span
::symbol
::sym
;
17 use std
::path
::PathBuf
;
19 use std
::str::FromStr
;
21 use self::mir_util
::PassWhere
;
22 use polonius_engine
::{Algorithm, Output}
;
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
;
31 use crate::borrow_check
::{
32 borrow_set
::BorrowSet
,
33 constraint_generation
,
34 diagnostics
::RegionErrors
,
35 facts
::{AllFacts, AllFactsExt, RustcFacts}
,
37 location
::LocationTable
,
38 region_infer
::{values::RegionValueElements, RegionInferenceContext}
,
40 type_check
::{self, MirTypeckRegionConstraints, MirTypeckResults}
,
41 universal_regions
::UniversalRegions
,
45 crate type PoloniusOutput
= Output
<RustcFacts
>;
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
>,
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
);
69 // Compute named region information. This also renumbers the inputs/outputs.
70 let universal_regions
= UniversalRegions
::new(infcx
, def
, param_env
);
72 // Replace all remaining regions with fresh inference variables.
73 renumber
::renumber_mir(infcx
, body
, promoted
);
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(()));
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(|(v
, &m
)| (m
, v
)));
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(in crate::borrow_check
) fn compute_regions
<'cx
, 'tcx
>(
160 infcx
: &InferCtxt
<'cx
, 'tcx
>,
162 universal_regions
: UniversalRegions
<'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
>,
171 ) -> NllOutput
<'tcx
> {
172 let mut all_facts
= AllFacts
::enabled(infcx
.tcx
).then_some(AllFacts
::default());
174 let universal_regions
= Rc
::new(universal_regions
);
176 let elements
= &Rc
::new(RegionValueElements
::new(&body
));
178 // Run the MIR type-checker.
179 let MirTypeckResults { constraints, universal_region_relations, opaque_type_values }
=
180 type_check
::type_check(
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
);
201 // Emit universal regions facts, and their relations, for Polonius.
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.
209 let borrow_count
= borrow_set
.len();
211 "compute_regions: polonius placeholders, num_universals={}, borrow_count={}",
212 universal_regions
.len(),
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()));
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() {
227 "compute_regions: emitting polonius `known_subset` fr1={:?}, fr2={:?}",
230 all_facts
.known_subset
.push((*fr1
, *fr2
));
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
{
241 placeholder_index_to_region
: _
,
242 mut liveness_constraints
,
243 outlives_constraints
,
245 closure_bounds_mapping
,
248 let placeholder_indices
= Rc
::new(placeholder_indices
);
250 constraint_generation
::generate_constraints(
252 &mut liveness_constraints
,
259 let mut regioncx
= RegionInferenceContext
::new(
263 universal_region_relations
,
264 outlives_constraints
,
266 closure_bounds_mapping
,
268 liveness_constraints
,
272 // Generate various additional constraints.
273 invalidation
::generate_invalidates(infcx
.tcx
, &mut all_facts
, location_table
, body
, borrow_set
);
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());
280 PathBuf
::from("nll-facts").join(def_path
.to_filename_friendly_no_crate());
281 all_facts
.write_to_dir(dir_path
, location_table
).unwrap();
284 if infcx
.tcx
.sess
.opts
.debugging_opts
.polonius
{
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)))
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());
300 if !nll_errors
.is_empty() {
301 // Suppress unhelpful extra errors in `infer_opaque_types`.
302 infcx
.set_tainted_by_errors();
305 let remapped_opaque_tys
= regioncx
.infer_opaque_types(&infcx
, opaque_type_values
, body
.span
);
309 opaque_type_values
: remapped_opaque_tys
,
311 opt_closure_req
: closure_region_requirements
,
316 pub(super) fn dump_mir_results
<'a
, 'tcx
>(
317 infcx
: &InferCtxt
<'a
, 'tcx
>,
318 source
: MirSource
<'tcx
>,
320 regioncx
: &RegionInferenceContext
<'tcx
>,
321 closure_region_requirements
: &Option
<ClosureRegionRequirements
<'_
>>,
323 if !mir_util
::dump_enabled(infcx
.tcx
, "nll", source
.def_id()) {
327 mir_util
::dump_mir(infcx
.tcx
, None
, "nll", &0, source
, body
, |pass_where
, out
| {
329 // Before the CFG, dump out the values for each region variable.
330 PassWhere
::BeforeCFG
=> {
331 regioncx
.dump_mir(infcx
.tcx
, out
)?
;
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
)
343 PassWhere
::BeforeLocation(_
) => {}
345 PassWhere
::AfterTerminator(_
) => {}
347 PassWhere
::BeforeBlock(_
) | PassWhere
::AfterLocation(_
) | PassWhere
::AfterCFG
=> {}
352 // Also dump the inference graph constraints as a graphviz file.
353 let _
: io
::Result
<()> = try
{
355 pretty
::create_dump_file(infcx
.tcx
, "regioncx.all.dot", None
, "nll", &0, source
)?
;
356 regioncx
.dump_graphviz_raw_constraints(&mut file
)?
;
359 // Also dump the inference graph constraints as a graphviz file.
360 let _
: io
::Result
<()> = try
{
362 pretty
::create_dump_file(infcx
.tcx
, "regioncx.scc.dot", None
, "nll", &0, source
)?
;
363 regioncx
.dump_graphviz_scc_constraints(&mut file
)?
;
367 pub(super) fn dump_annotation
<'a
, 'tcx
>(
368 infcx
: &InferCtxt
<'a
, 'tcx
>,
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
>,
377 let base_def_id
= tcx
.closure_base_def_id(mir_def_id
);
378 if !tcx
.has_attr(base_def_id
, sym
::rustc_regions
) {
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
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");
392 regioncx
.annotate(tcx
, &mut err
);
395 "number of external vids: {}",
396 closure_region_requirements
.num_external_vids
399 // Dump the region constraints we are imposing *between* those
400 // newly created variables.
401 for_each_region_constraint(closure_region_requirements
, &mut |msg
| {
409 let mut err
= tcx
.sess
.diagnostic().span_note_diag(body
.span
, "no external requirements");
410 regioncx
.annotate(tcx
, &mut err
);
415 if !opaque_type_values
.is_empty() {
416 err
.note(&format
!("Inferred opaque type values:\n{:#?}", opaque_type_values
));
419 err
.buffer(errors_buffer
);
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
,
431 with_msg(&format
!("where {:?}: {:?}", subject
, req
.outlived_free_region
,))?
;
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
;
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) }
451 impl ToRegionVid for RegionVid {
452 fn to_region_vid(self) -> RegionVid {
457 crate trait ConstraintDescription {
458 fn description(&self) -> &'static str;