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
;
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, 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::util
as mir_util
;
28 use crate::util
::pretty
;
30 use crate::borrow_check
::{
31 borrow_set
::BorrowSet
,
32 constraint_generation
,
33 diagnostics
::RegionErrors
,
34 facts
::{AllFacts, AllFactsExt, RustcFacts}
,
36 location
::LocationTable
,
37 region_infer
::{values::RegionValueElements, RegionInferenceContext}
,
39 type_check
::{self, MirTypeckRegionConstraints, MirTypeckResults}
,
40 universal_regions
::UniversalRegions
,
44 crate type PoloniusOutput
= Output
<RustcFacts
>;
46 /// The output of `nll::compute_regions`. This includes the computed `RegionInferenceContext`, any
47 /// closure requirements to propagate, and any generated errors.
48 crate struct NllOutput
<'tcx
> {
49 pub regioncx
: RegionInferenceContext
<'tcx
>,
50 pub opaque_type_values
: FxHashMap
<DefId
, ty
::ResolvedOpaqueTy
<'tcx
>>,
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 pub(in crate::borrow_check
) fn replace_regions_in_mir
<'cx
, 'tcx
>(
60 infcx
: &InferCtxt
<'cx
, 'tcx
>,
61 param_env
: ty
::ParamEnv
<'tcx
>,
62 body
: &mut Body
<'tcx
>,
63 promoted
: &mut IndexVec
<Promoted
, Body
<'tcx
>>,
64 ) -> UniversalRegions
<'tcx
> {
65 let def
= body
.source
.with_opt_param().as_local().unwrap();
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 mir_util
::dump_mir(infcx
.tcx
, None
, "renumber", &0, body
, |_
, _
| Ok(()));
80 // This function populates an AllFacts instance with base facts related to
81 // MovePaths and needed for the move analysis.
82 fn populate_polonius_move_facts(
83 all_facts
: &mut AllFacts
,
84 move_data
: &MoveData
<'_
>,
85 location_table
: &LocationTable
,
90 .extend(move_data
.rev_lookup
.iter_locals_enumerated().map(|(v
, &m
)| (m
, v
)));
92 for (child
, move_path
) in move_data
.move_paths
.iter_enumerated() {
93 if let Some(parent
) = move_path
.parent
{
94 all_facts
.child_path
.push((child
, parent
));
98 let fn_entry_start
= location_table
99 .start_index(Location { block: BasicBlock::from_u32(0u32), statement_index: 0 }
);
102 for init
in move_data
.inits
.iter() {
103 match init
.location
{
104 InitLocation
::Statement(location
) => {
105 let block_data
= &body
[location
.block
];
106 let is_terminator
= location
.statement_index
== block_data
.statements
.len();
108 if is_terminator
&& init
.kind
== InitKind
::NonPanicPathOnly
{
109 // We are at the terminator of an init that has a panic path,
110 // and where the init should not happen on panic
112 for &successor
in block_data
.terminator().successors() {
113 if body
[successor
].is_cleanup
{
117 // The initialization happened in (or rather, when arriving at)
118 // the successors, but not in the unwind block.
119 let first_statement
= Location { block: successor, statement_index: 0 }
;
121 .path_assigned_at_base
122 .push((init
.path
, location_table
.start_index(first_statement
)));
125 // In all other cases, the initialization just happens at the
126 // midpoint, like any other effect.
128 .path_assigned_at_base
129 .push((init
.path
, location_table
.mid_index(location
)));
132 // Arguments are initialized on function entry
133 InitLocation
::Argument(local
) => {
134 assert
!(body
.local_kind(local
) == LocalKind
::Arg
);
135 all_facts
.path_assigned_at_base
.push((init
.path
, fn_entry_start
));
140 for (local
, &path
) in move_data
.rev_lookup
.iter_locals_enumerated() {
141 if body
.local_kind(local
) != LocalKind
::Arg
{
142 // Non-arguments start out deinitialised; we simulate this with an
144 all_facts
.path_moved_at_base
.push((path
, fn_entry_start
));
149 // deinitialisation is assumed to always happen!
152 .extend(move_data
.moves
.iter().map(|mo
| (mo
.path
, location_table
.mid_index(mo
.source
))));
155 /// Computes the (non-lexical) regions from the input MIR.
157 /// This may result in errors being reported.
158 pub(in crate::borrow_check
) fn compute_regions
<'cx
, 'tcx
>(
159 infcx
: &InferCtxt
<'cx
, 'tcx
>,
160 universal_regions
: UniversalRegions
<'tcx
>,
162 promoted
: &IndexVec
<Promoted
, Body
<'tcx
>>,
163 location_table
: &LocationTable
,
164 param_env
: ty
::ParamEnv
<'tcx
>,
165 flow_inits
: &mut ResultsCursor
<'cx
, 'tcx
, MaybeInitializedPlaces
<'cx
, 'tcx
>>,
166 move_data
: &MoveData
<'tcx
>,
167 borrow_set
: &BorrowSet
<'tcx
>,
169 ) -> NllOutput
<'tcx
> {
170 let mut all_facts
= AllFacts
::enabled(infcx
.tcx
).then_some(AllFacts
::default());
172 let universal_regions
= Rc
::new(universal_regions
);
174 let elements
= &Rc
::new(RegionValueElements
::new(&body
));
176 // Run the MIR type-checker.
177 let MirTypeckResults { constraints, universal_region_relations, opaque_type_values }
=
178 type_check
::type_check(
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
);
198 // Emit universal regions facts, and their relations, for Polonius.
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.
206 let borrow_count
= borrow_set
.len();
208 "compute_regions: polonius placeholders, num_universals={}, borrow_count={}",
209 universal_regions
.len(),
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()));
219 // 2: the universal region relations `outlives` constraints are emitted as
220 // `known_subset` facts.
221 for (fr1
, fr2
) in universal_region_relations
.known_outlives() {
224 "compute_regions: emitting polonius `known_subset` fr1={:?}, fr2={:?}",
227 all_facts
.known_subset
.push((*fr1
, *fr2
));
232 // Create the region inference context, taking ownership of the
233 // region inference data that was contained in `infcx`, and the
234 // base constraints generated by the type-check.
235 let var_origins
= infcx
.take_region_var_origins();
236 let MirTypeckRegionConstraints
{
238 placeholder_index_to_region
: _
,
239 mut liveness_constraints
,
240 outlives_constraints
,
242 closure_bounds_mapping
,
245 let placeholder_indices
= Rc
::new(placeholder_indices
);
247 constraint_generation
::generate_constraints(
249 &mut liveness_constraints
,
256 let mut regioncx
= RegionInferenceContext
::new(
260 universal_region_relations
,
261 outlives_constraints
,
263 closure_bounds_mapping
,
265 liveness_constraints
,
269 // Generate various additional constraints.
270 invalidation
::generate_invalidates(infcx
.tcx
, &mut all_facts
, location_table
, body
, borrow_set
);
272 let def_id
= body
.source
.def_id();
274 // Dump facts if requested.
275 let polonius_output
= all_facts
.and_then(|all_facts
| {
276 if infcx
.tcx
.sess
.opts
.debugging_opts
.nll_facts
{
277 let def_path
= infcx
.tcx
.def_path(def_id
);
278 let dir_path
= PathBuf
::from(&infcx
.tcx
.sess
.opts
.debugging_opts
.nll_facts_dir
)
279 .join(def_path
.to_filename_friendly_no_crate());
280 all_facts
.write_to_dir(dir_path
, location_table
).unwrap();
283 if infcx
.tcx
.sess
.opts
.debugging_opts
.polonius
{
285 env
::var("POLONIUS_ALGORITHM").unwrap_or_else(|_
| String
::from("Naive"));
286 let algorithm
= Algorithm
::from_str(&algorithm
).unwrap();
287 debug
!("compute_regions: using polonius algorithm {:?}", algorithm
);
288 let _prof_timer
= infcx
.tcx
.prof
.generic_activity("polonius_analysis");
289 Some(Rc
::new(Output
::compute(&all_facts
, algorithm
, false)))
295 // Solve the region constraints.
296 let (closure_region_requirements
, nll_errors
) =
297 regioncx
.solve(infcx
, &body
, polonius_output
.clone());
299 if !nll_errors
.is_empty() {
300 // Suppress unhelpful extra errors in `infer_opaque_types`.
301 infcx
.set_tainted_by_errors();
304 let remapped_opaque_tys
= regioncx
.infer_opaque_types(&infcx
, opaque_type_values
, body
.span
);
308 opaque_type_values
: remapped_opaque_tys
,
310 opt_closure_req
: closure_region_requirements
,
315 pub(super) fn dump_mir_results
<'a
, 'tcx
>(
316 infcx
: &InferCtxt
<'a
, 'tcx
>,
318 regioncx
: &RegionInferenceContext
<'tcx
>,
319 closure_region_requirements
: &Option
<ClosureRegionRequirements
<'_
>>,
321 if !mir_util
::dump_enabled(infcx
.tcx
, "nll", body
.source
.def_id()) {
325 mir_util
::dump_mir(infcx
.tcx
, None
, "nll", &0, body
, |pass_where
, out
| {
327 // Before the CFG, dump out the values for each region variable.
328 PassWhere
::BeforeCFG
=> {
329 regioncx
.dump_mir(infcx
.tcx
, out
)?
;
332 if let Some(closure_region_requirements
) = closure_region_requirements
{
333 writeln
!(out
, "| Free Region Constraints")?
;
334 for_each_region_constraint(closure_region_requirements
, &mut |msg
| {
335 writeln
!(out
, "| {}", msg
)
341 PassWhere
::BeforeLocation(_
) => {}
343 PassWhere
::AfterTerminator(_
) => {}
345 PassWhere
::BeforeBlock(_
) | PassWhere
::AfterLocation(_
) | PassWhere
::AfterCFG
=> {}
350 // Also dump the inference graph constraints as a graphviz file.
351 let _
: io
::Result
<()> = try
{
353 pretty
::create_dump_file(infcx
.tcx
, "regioncx.all.dot", None
, "nll", &0, body
.source
)?
;
354 regioncx
.dump_graphviz_raw_constraints(&mut file
)?
;
357 // Also dump the inference graph constraints as a graphviz file.
358 let _
: io
::Result
<()> = try
{
360 pretty
::create_dump_file(infcx
.tcx
, "regioncx.scc.dot", None
, "nll", &0, body
.source
)?
;
361 regioncx
.dump_graphviz_scc_constraints(&mut file
)?
;
365 pub(super) fn dump_annotation
<'a
, 'tcx
>(
366 infcx
: &InferCtxt
<'a
, 'tcx
>,
368 regioncx
: &RegionInferenceContext
<'tcx
>,
369 closure_region_requirements
: &Option
<ClosureRegionRequirements
<'_
>>,
370 opaque_type_values
: &FxHashMap
<DefId
, ty
::ResolvedOpaqueTy
<'tcx
>>,
371 errors_buffer
: &mut Vec
<Diagnostic
>,
374 let base_def_id
= tcx
.closure_base_def_id(body
.source
.def_id());
375 if !tcx
.has_attr(base_def_id
, sym
::rustc_regions
) {
379 // When the enclosing function is tagged with `#[rustc_regions]`,
380 // we dump out various bits of state as warnings. This is useful
381 // for verifying that the compiler is behaving as expected. These
382 // warnings focus on the closure region requirements -- for
383 // viewing the intraprocedural state, the -Zdump-mir output is
386 let mut err
= if let Some(closure_region_requirements
) = closure_region_requirements
{
387 let mut err
= tcx
.sess
.diagnostic().span_note_diag(body
.span
, "external requirements");
389 regioncx
.annotate(tcx
, &mut err
);
392 "number of external vids: {}",
393 closure_region_requirements
.num_external_vids
396 // Dump the region constraints we are imposing *between* those
397 // newly created variables.
398 for_each_region_constraint(closure_region_requirements
, &mut |msg
| {
406 let mut err
= tcx
.sess
.diagnostic().span_note_diag(body
.span
, "no external requirements");
407 regioncx
.annotate(tcx
, &mut err
);
412 if !opaque_type_values
.is_empty() {
413 err
.note(&format
!("Inferred opaque type values:\n{:#?}", opaque_type_values
));
416 err
.buffer(errors_buffer
);
419 fn for_each_region_constraint(
420 closure_region_requirements
: &ClosureRegionRequirements
<'_
>,
421 with_msg
: &mut dyn FnMut(&str) -> io
::Result
<()>,
422 ) -> io
::Result
<()> {
423 for req
in &closure_region_requirements
.outlives_requirements
{
424 let subject
: &dyn Debug
= match &req
.subject
{
425 ClosureOutlivesSubject
::Region(subject
) => subject
,
426 ClosureOutlivesSubject
::Ty(ty
) => ty
,
428 with_msg(&format
!("where {:?}: {:?}", subject
, req
.outlived_free_region
,))?
;
433 /// Right now, we piggy back on the `ReVar` to store our NLL inference
434 /// regions. These are indexed with `RegionVid`. This method will
435 /// assert that the region is a `ReVar` and extract its internal index.
436 /// This is reasonable because in our MIR we replace all universal regions
437 /// with inference variables.
438 pub trait ToRegionVid
{
439 fn to_region_vid(self) -> RegionVid
;
442 impl<'tcx
> ToRegionVid
for &'tcx RegionKind
{
443 fn to_region_vid(self) -> RegionVid
{
444 if let ty
::ReVar(vid
) = self { *vid }
else { bug!("region is not an ReVar: {:?}
", self) }
448 impl ToRegionVid for RegionVid {
449 fn to_region_vid(self) -> RegionVid {
454 crate trait ConstraintDescription {
455 fn description(&self) -> &'static str;