1 //! The entry point of the NLL borrow checker.
3 use rustc_data_structures
::vec_map
::VecMap
;
4 use rustc_hir
::def_id
::DefId
;
5 use rustc_index
::vec
::IndexVec
;
6 use rustc_infer
::infer
::InferCtxt
;
7 use rustc_middle
::mir
::{create_dump_file, dump_enabled, dump_mir, PassWhere}
;
8 use rustc_middle
::mir
::{
9 BasicBlock
, Body
, ClosureOutlivesSubject
, ClosureRegionRequirements
, LocalKind
, Location
,
12 use rustc_middle
::ty
::{self, OpaqueHiddenType, Region, RegionVid}
;
13 use rustc_span
::symbol
::sym
;
17 use std
::path
::PathBuf
;
19 use std
::str::FromStr
;
21 use polonius_engine
::{Algorithm, Output}
;
23 use rustc_mir_dataflow
::impls
::MaybeInitializedPlaces
;
24 use rustc_mir_dataflow
::move_paths
::{InitKind, InitLocation, MoveData}
;
25 use rustc_mir_dataflow
::ResultsCursor
;
28 borrow_set
::BorrowSet
,
29 constraint_generation
,
30 diagnostics
::RegionErrors
,
31 facts
::{AllFacts, AllFactsExt, RustcFacts}
,
33 location
::LocationTable
,
34 region_infer
::{values::RegionValueElements, RegionInferenceContext}
,
36 type_check
::{self, MirTypeckRegionConstraints, MirTypeckResults}
,
37 universal_regions
::UniversalRegions
,
41 pub type PoloniusOutput
= Output
<RustcFacts
>;
43 /// The output of `nll::compute_regions`. This includes the computed `RegionInferenceContext`, any
44 /// closure requirements to propagate, and any generated errors.
45 crate struct NllOutput
<'tcx
> {
46 pub regioncx
: RegionInferenceContext
<'tcx
>,
47 pub opaque_type_values
: VecMap
<DefId
, OpaqueHiddenType
<'tcx
>>,
48 pub polonius_input
: Option
<Box
<AllFacts
>>,
49 pub polonius_output
: Option
<Rc
<PoloniusOutput
>>,
50 pub opt_closure_req
: Option
<ClosureRegionRequirements
<'tcx
>>,
51 pub nll_errors
: RegionErrors
<'tcx
>,
54 /// Rewrites the regions in the MIR to use NLL variables, also scraping out the set of universal
55 /// regions (e.g., region parameters) declared on the function. That set will need to be given to
56 /// `compute_regions`.
57 #[instrument(skip(infcx, param_env, body, promoted), level = "debug")]
58 pub(crate) fn replace_regions_in_mir
<'cx
, 'tcx
>(
59 infcx
: &InferCtxt
<'cx
, 'tcx
>,
60 param_env
: ty
::ParamEnv
<'tcx
>,
61 body
: &mut Body
<'tcx
>,
62 promoted
: &mut IndexVec
<Promoted
, Body
<'tcx
>>,
63 ) -> UniversalRegions
<'tcx
> {
64 let def
= body
.source
.with_opt_param().as_local().unwrap();
68 // Compute named region information. This also renumbers the inputs/outputs.
69 let universal_regions
= UniversalRegions
::new(infcx
, def
, param_env
);
71 // Replace all remaining regions with fresh inference variables.
72 renumber
::renumber_mir(infcx
, body
, promoted
);
74 dump_mir(infcx
.tcx
, None
, "renumber", &0, body
, |_
, _
| Ok(()));
79 // This function populates an AllFacts instance with base facts related to
80 // MovePaths and needed for the move analysis.
81 fn populate_polonius_move_facts(
82 all_facts
: &mut AllFacts
,
83 move_data
: &MoveData
<'_
>,
84 location_table
: &LocationTable
,
89 .extend(move_data
.rev_lookup
.iter_locals_enumerated().map(|(l
, r
)| (r
, l
)));
91 for (child
, move_path
) in move_data
.move_paths
.iter_enumerated() {
92 if let Some(parent
) = move_path
.parent
{
93 all_facts
.child_path
.push((child
, parent
));
97 let fn_entry_start
= location_table
98 .start_index(Location { block: BasicBlock::from_u32(0u32), statement_index: 0 }
);
101 for init
in move_data
.inits
.iter() {
102 match init
.location
{
103 InitLocation
::Statement(location
) => {
104 let block_data
= &body
[location
.block
];
105 let is_terminator
= location
.statement_index
== block_data
.statements
.len();
107 if is_terminator
&& init
.kind
== InitKind
::NonPanicPathOnly
{
108 // We are at the terminator of an init that has a panic path,
109 // and where the init should not happen on panic
111 for &successor
in block_data
.terminator().successors() {
112 if body
[successor
].is_cleanup
{
116 // The initialization happened in (or rather, when arriving at)
117 // the successors, but not in the unwind block.
118 let first_statement
= Location { block: successor, statement_index: 0 }
;
120 .path_assigned_at_base
121 .push((init
.path
, location_table
.start_index(first_statement
)));
124 // In all other cases, the initialization just happens at the
125 // midpoint, like any other effect.
127 .path_assigned_at_base
128 .push((init
.path
, location_table
.mid_index(location
)));
131 // Arguments are initialized on function entry
132 InitLocation
::Argument(local
) => {
133 assert
!(body
.local_kind(local
) == LocalKind
::Arg
);
134 all_facts
.path_assigned_at_base
.push((init
.path
, fn_entry_start
));
139 for (local
, path
) in move_data
.rev_lookup
.iter_locals_enumerated() {
140 if body
.local_kind(local
) != LocalKind
::Arg
{
141 // Non-arguments start out deinitialised; we simulate this with an
143 all_facts
.path_moved_at_base
.push((path
, fn_entry_start
));
148 // deinitialisation is assumed to always happen!
151 .extend(move_data
.moves
.iter().map(|mo
| (mo
.path
, location_table
.mid_index(mo
.source
))));
154 /// Computes the (non-lexical) regions from the input MIR.
156 /// This may result in errors being reported.
157 pub(crate) fn compute_regions
<'cx
, 'tcx
>(
158 infcx
: &InferCtxt
<'cx
, 'tcx
>,
159 universal_regions
: UniversalRegions
<'tcx
>,
161 promoted
: &IndexVec
<Promoted
, Body
<'tcx
>>,
162 location_table
: &LocationTable
,
163 param_env
: ty
::ParamEnv
<'tcx
>,
164 flow_inits
: &mut ResultsCursor
<'cx
, 'tcx
, MaybeInitializedPlaces
<'cx
, 'tcx
>>,
165 move_data
: &MoveData
<'tcx
>,
166 borrow_set
: &BorrowSet
<'tcx
>,
167 upvars
: &[Upvar
<'tcx
>],
169 ) -> NllOutput
<'tcx
> {
171 (use_polonius
|| AllFacts
::enabled(infcx
.tcx
)).then_some(AllFacts
::default());
173 let universal_regions
= Rc
::new(universal_regions
);
175 let elements
= &Rc
::new(RegionValueElements
::new(&body
));
177 // Run the MIR type-checker.
178 let MirTypeckResults { constraints, universal_region_relations, opaque_type_values }
=
179 type_check
::type_check(
195 if let Some(all_facts
) = &mut all_facts
{
196 let _prof_timer
= infcx
.tcx
.prof
.generic_activity("polonius_fact_generation");
197 all_facts
.universal_region
.extend(universal_regions
.universal_regions());
198 populate_polonius_move_facts(all_facts
, move_data
, location_table
, &body
);
200 // Emit universal regions facts, and their relations, for Polonius.
202 // 1: universal regions are modeled in Polonius as a pair:
203 // - the universal region vid itself.
204 // - a "placeholder loan" associated to this universal region. Since they don't exist in
205 // the `borrow_set`, their `BorrowIndex` are synthesized as the universal region index
206 // added to the existing number of loans, as if they succeeded them in the set.
208 let borrow_count
= borrow_set
.len();
210 "compute_regions: polonius placeholders, num_universals={}, borrow_count={}",
211 universal_regions
.len(),
215 for universal_region
in universal_regions
.universal_regions() {
216 let universal_region_idx
= universal_region
.index();
217 let placeholder_loan_idx
= borrow_count
+ universal_region_idx
;
218 all_facts
.placeholder
.push((universal_region
, placeholder_loan_idx
.into()));
221 // 2: the universal region relations `outlives` constraints are emitted as
222 // `known_placeholder_subset` facts.
223 for (fr1
, fr2
) in universal_region_relations
.known_outlives() {
226 "compute_regions: emitting polonius `known_placeholder_subset` \
230 all_facts
.known_placeholder_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
,
249 let placeholder_indices
= Rc
::new(placeholder_indices
);
251 constraint_generation
::generate_constraints(
253 &mut liveness_constraints
,
260 let mut regioncx
= RegionInferenceContext
::new(
264 universal_region_relations
,
265 outlives_constraints
,
267 closure_bounds_mapping
,
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
.debugging_opts
.nll_facts
{
282 let def_path
= infcx
.tcx
.def_path(def_id
);
283 let dir_path
= PathBuf
::from(&infcx
.tcx
.sess
.opts
.debugging_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
, &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();
309 let remapped_opaque_tys
= regioncx
.infer_opaque_types(&infcx
, opaque_type_values
);
313 opaque_type_values
: remapped_opaque_tys
,
314 polonius_input
: all_facts
.map(Box
::new
),
316 opt_closure_req
: closure_region_requirements
,
321 pub(super) fn dump_mir_results
<'a
, 'tcx
>(
322 infcx
: &InferCtxt
<'a
, 'tcx
>,
324 regioncx
: &RegionInferenceContext
<'tcx
>,
325 closure_region_requirements
: &Option
<ClosureRegionRequirements
<'_
>>,
327 if !dump_enabled(infcx
.tcx
, "nll", body
.source
.def_id()) {
331 dump_mir(infcx
.tcx
, None
, "nll", &0, body
, |pass_where
, out
| {
333 // Before the CFG, dump out the values for each region variable.
334 PassWhere
::BeforeCFG
=> {
335 regioncx
.dump_mir(infcx
.tcx
, out
)?
;
338 if let Some(closure_region_requirements
) = closure_region_requirements
{
339 writeln
!(out
, "| Free Region Constraints")?
;
340 for_each_region_constraint(closure_region_requirements
, &mut |msg
| {
341 writeln
!(out
, "| {}", msg
)
347 PassWhere
::BeforeLocation(_
) => {}
349 PassWhere
::AfterTerminator(_
) => {}
351 PassWhere
::BeforeBlock(_
) | PassWhere
::AfterLocation(_
) | PassWhere
::AfterCFG
=> {}
356 // Also dump the inference graph constraints as a graphviz file.
357 let _
: io
::Result
<()> = try
{
359 create_dump_file(infcx
.tcx
, "regioncx.all.dot", None
, "nll", &0, body
.source
)?
;
360 regioncx
.dump_graphviz_raw_constraints(&mut file
)?
;
363 // Also dump the inference graph constraints as a graphviz file.
364 let _
: io
::Result
<()> = try
{
366 create_dump_file(infcx
.tcx
, "regioncx.scc.dot", None
, "nll", &0, body
.source
)?
;
367 regioncx
.dump_graphviz_scc_constraints(&mut file
)?
;
371 pub(super) fn dump_annotation
<'a
, 'tcx
>(
372 infcx
: &InferCtxt
<'a
, 'tcx
>,
374 regioncx
: &RegionInferenceContext
<'tcx
>,
375 closure_region_requirements
: &Option
<ClosureRegionRequirements
<'_
>>,
376 opaque_type_values
: &VecMap
<DefId
, OpaqueHiddenType
<'tcx
>>,
377 errors
: &mut crate::error
::BorrowckErrors
<'tcx
>,
380 let base_def_id
= tcx
.typeck_root_def_id(body
.source
.def_id());
381 if !tcx
.has_attr(base_def_id
, sym
::rustc_regions
) {
385 // When the enclosing function is tagged with `#[rustc_regions]`,
386 // we dump out various bits of state as warnings. This is useful
387 // for verifying that the compiler is behaving as expected. These
388 // warnings focus on the closure region requirements -- for
389 // viewing the intraprocedural state, the -Zdump-mir output is
392 let mut err
= if let Some(closure_region_requirements
) = closure_region_requirements
{
393 let mut err
= tcx
.sess
.diagnostic().span_note_diag(body
.span
, "external requirements");
395 regioncx
.annotate(tcx
, &mut err
);
398 "number of external vids: {}",
399 closure_region_requirements
.num_external_vids
402 // Dump the region constraints we are imposing *between* those
403 // newly created variables.
404 for_each_region_constraint(closure_region_requirements
, &mut |msg
| {
412 let mut err
= tcx
.sess
.diagnostic().span_note_diag(body
.span
, "no external requirements");
413 regioncx
.annotate(tcx
, &mut err
);
418 if !opaque_type_values
.is_empty() {
419 err
.note(&format
!("Inferred opaque type values:\n{:#?}", opaque_type_values
));
422 errors
.buffer_non_error_diag(err
);
425 fn for_each_region_constraint(
426 closure_region_requirements
: &ClosureRegionRequirements
<'_
>,
427 with_msg
: &mut dyn FnMut(&str) -> io
::Result
<()>,
428 ) -> io
::Result
<()> {
429 for req
in &closure_region_requirements
.outlives_requirements
{
430 let subject
: &dyn Debug
= match &req
.subject
{
431 ClosureOutlivesSubject
::Region(subject
) => subject
,
432 ClosureOutlivesSubject
::Ty(ty
) => ty
,
434 with_msg(&format
!("where {:?}: {:?}", subject
, req
.outlived_free_region
,))?
;
439 /// Right now, we piggy back on the `ReVar` to store our NLL inference
440 /// regions. These are indexed with `RegionVid`. This method will
441 /// assert that the region is a `ReVar` and extract its internal index.
442 /// This is reasonable because in our MIR we replace all universal regions
443 /// with inference variables.
444 pub trait ToRegionVid
{
445 fn to_region_vid(self) -> RegionVid
;
448 impl<'tcx
> ToRegionVid
for Region
<'tcx
> {
449 fn to_region_vid(self) -> RegionVid
{
450 if let ty
::ReVar(vid
) = *self { vid }
else { bug!("region is not an ReVar: {:?}
", self) }
454 impl ToRegionVid for RegionVid {
455 fn to_region_vid(self) -> RegionVid {
460 crate trait ConstraintDescription {
461 fn description(&self) -> &'static str;