1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use borrow_check
::borrow_set
::BorrowSet
;
12 use borrow_check
::location
::{LocationIndex, LocationTable}
;
13 use borrow_check
::nll
::facts
::AllFactsExt
;
14 use borrow_check
::nll
::type_check
::MirTypeckRegionConstraints
;
15 use dataflow
::indexes
::BorrowIndex
;
16 use dataflow
::move_paths
::MoveData
;
17 use dataflow
::FlowAtLocation
;
18 use dataflow
::MaybeInitializedPlaces
;
19 use rustc
::hir
::def_id
::DefId
;
20 use rustc
::infer
::InferCtxt
;
21 use rustc
::mir
::{ClosureOutlivesSubject, ClosureRegionRequirements, Mir}
;
22 use rustc
::ty
::{self, RegionKind, RegionVid}
;
23 use rustc
::util
::nodemap
::FxHashMap
;
24 use std
::collections
::BTreeSet
;
28 use std
::path
::PathBuf
;
30 use std
::str::FromStr
;
31 use transform
::MirSource
;
32 use util
::liveness
::{LivenessResults, LocalSet}
;
34 use self::mir_util
::PassWhere
;
35 use polonius_engine
::{Algorithm, Output}
;
37 use util
::pretty
::{self, ALIGN}
;
39 mod constraint_generation
;
40 pub mod explain_borrow
;
43 crate mod region_infer
;
46 mod universal_regions
;
48 use self::facts
::AllFacts
;
49 use self::region_infer
::RegionInferenceContext
;
50 use self::universal_regions
::UniversalRegions
;
52 /// Rewrites the regions in the MIR to use NLL variables, also
53 /// scraping out the set of universal regions (e.g., region parameters)
54 /// declared on the function. That set will need to be given to
55 /// `compute_regions`.
56 pub(in borrow_check
) fn replace_regions_in_mir
<'cx
, 'gcx
, 'tcx
>(
57 infcx
: &InferCtxt
<'cx
, 'gcx
, 'tcx
>,
59 param_env
: ty
::ParamEnv
<'tcx
>,
61 ) -> UniversalRegions
<'tcx
> {
62 debug
!("replace_regions_in_mir(def_id={:?})", def_id
);
64 // Compute named region information. This also renumbers the inputs/outputs.
65 let universal_regions
= UniversalRegions
::new(infcx
, def_id
, param_env
);
67 // Replace all remaining regions with fresh inference variables.
68 renumber
::renumber_mir(infcx
, mir
);
70 let source
= MirSource
::item(def_id
);
71 mir_util
::dump_mir(infcx
.tcx
, None
, "renumber", &0, source
, mir
, |_
, _
| Ok(()));
76 /// Computes the (non-lexical) regions from the input MIR.
78 /// This may result in errors being reported.
79 pub(in borrow_check
) fn compute_regions
<'cx
, 'gcx
, 'tcx
>(
80 infcx
: &InferCtxt
<'cx
, 'gcx
, 'tcx
>,
82 universal_regions
: UniversalRegions
<'tcx
>,
84 location_table
: &LocationTable
,
85 param_env
: ty
::ParamEnv
<'gcx
>,
86 flow_inits
: &mut FlowAtLocation
<MaybeInitializedPlaces
<'cx
, 'gcx
, 'tcx
>>,
87 move_data
: &MoveData
<'tcx
>,
88 borrow_set
: &BorrowSet
<'tcx
>,
90 RegionInferenceContext
<'tcx
>,
91 Option
<Rc
<Output
<RegionVid
, BorrowIndex
, LocationIndex
>>>,
92 Option
<ClosureRegionRequirements
<'gcx
>>,
94 let mut all_facts
= if infcx
.tcx
.sess
.opts
.debugging_opts
.nll_facts
95 || infcx
.tcx
.sess
.opts
.debugging_opts
.polonius
97 Some(AllFacts
::default())
102 // Run the MIR type-checker.
103 let liveness
= &LivenessResults
::compute(mir
);
104 let constraint_sets
= type_check
::type_check(
117 if let Some(all_facts
) = &mut all_facts
{
120 .extend(universal_regions
.universal_regions());
123 // Create the region inference context, taking ownership of the
124 // region inference data that was contained in `infcx`, and the
125 // base constraints generated by the type-check.
126 let var_origins
= infcx
.take_region_var_origins();
127 let MirTypeckRegionConstraints
{
129 outlives_constraints
,
132 let mut regioncx
= RegionInferenceContext
::new(
136 outlives_constraints
,
140 // Generate various additional constraints.
141 constraint_generation
::generate_constraints(
150 invalidation
::generate_invalidates(
159 // Dump facts if requested.
160 let polonius_output
= all_facts
.and_then(|all_facts
| {
161 if infcx
.tcx
.sess
.opts
.debugging_opts
.nll_facts
{
162 let def_path
= infcx
.tcx
.hir
.def_path(def_id
);
164 PathBuf
::from("nll-facts").join(def_path
.to_filename_friendly_no_crate());
165 all_facts
.write_to_dir(dir_path
, location_table
).unwrap();
168 if infcx
.tcx
.sess
.opts
.debugging_opts
.polonius
{
169 let algorithm
= env
::var("POLONIUS_ALGORITHM")
170 .unwrap_or(String
::from("DatafrogOpt"));
171 let algorithm
= Algorithm
::from_str(&algorithm
).unwrap();
172 debug
!("compute_regions: using polonius algorithm {:?}", algorithm
);
173 Some(Rc
::new(Output
::compute(
183 // Solve the region constraints.
184 let closure_region_requirements
= regioncx
.solve(infcx
, &mir
, def_id
);
186 // Dump MIR results into a file, if that is enabled. This let us
187 // write unit-tests, as well as helping with debugging.
191 MirSource
::item(def_id
),
194 &closure_region_requirements
,
197 // We also have a `#[rustc_nll]` annotation that causes us to dump
199 dump_annotation(infcx
, &mir
, def_id
, ®ioncx
, &closure_region_requirements
);
201 (regioncx
, polonius_output
, closure_region_requirements
)
204 fn dump_mir_results
<'a
, 'gcx
, 'tcx
>(
205 infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>,
206 liveness
: &LivenessResults
,
209 regioncx
: &RegionInferenceContext
,
210 closure_region_requirements
: &Option
<ClosureRegionRequirements
>,
212 if !mir_util
::dump_enabled(infcx
.tcx
, "nll", source
) {
216 let regular_liveness_per_location
: FxHashMap
<_
, _
> = mir
220 let mut results
= vec
![];
223 .simulate_block(&mir
, bb
, |location
, local_set
| {
224 results
.push((location
, local_set
.clone()));
230 let drop_liveness_per_location
: FxHashMap
<_
, _
> = mir
234 let mut results
= vec
![];
237 .simulate_block(&mir
, bb
, |location
, local_set
| {
238 results
.push((location
, local_set
.clone()));
253 // Before the CFG, dump out the values for each region variable.
254 PassWhere
::BeforeCFG
=> {
255 regioncx
.dump_mir(out
)?
;
257 if let Some(closure_region_requirements
) = closure_region_requirements
{
259 writeln
!(out
, "| Free Region Constraints")?
;
260 for_each_region_constraint(closure_region_requirements
, &mut |msg
| {
261 writeln
!(out
, "| {}", msg
)
266 // Before each basic block, dump out the values
267 // that are live on entry to the basic block.
268 PassWhere
::BeforeBlock(bb
) => {
269 let s
= live_variable_set(&liveness
.regular
.ins
[bb
], &liveness
.drop
.ins
[bb
]);
270 writeln
!(out
, " | Live variables on entry to {:?}: {}", bb
, s
)?
;
273 PassWhere
::BeforeLocation(location
) => {
274 let s
= live_variable_set(
275 ®ular_liveness_per_location
[&location
],
276 &drop_liveness_per_location
[&location
],
280 "{:ALIGN$} | Live variables on entry to {:?}: {}",
288 PassWhere
::AfterLocation(_
) | PassWhere
::AfterCFG
=> {}
294 // Also dump the inference graph constraints as a graphviz file.
295 let _
: io
::Result
<()> = do catch {
297 pretty
::create_dump_file(infcx
.tcx
, "regioncx.dot", None
, "nll", &0, source
)?
;
298 regioncx
.dump_graphviz(&mut file
)?
;
302 fn dump_annotation
<'a
, 'gcx
, 'tcx
>(
303 infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>,
306 regioncx
: &RegionInferenceContext
,
307 closure_region_requirements
: &Option
<ClosureRegionRequirements
>,
310 let base_def_id
= tcx
.closure_base_def_id(mir_def_id
);
311 if !tcx
.has_attr(base_def_id
, "rustc_regions") {
315 // When the enclosing function is tagged with `#[rustc_regions]`,
316 // we dump out various bits of state as warnings. This is useful
317 // for verifying that the compiler is behaving as expected. These
318 // warnings focus on the closure region requirements -- for
319 // viewing the intraprocedural state, the -Zdump-mir output is
322 if let Some(closure_region_requirements
) = closure_region_requirements
{
326 .span_note_diag(mir
.span
, "External requirements");
328 regioncx
.annotate(&mut err
);
331 "number of external vids: {}",
332 closure_region_requirements
.num_external_vids
335 // Dump the region constraints we are imposing *between* those
336 // newly created variables.
337 for_each_region_constraint(closure_region_requirements
, &mut |msg
| {
347 .span_note_diag(mir
.span
, "No external requirements");
348 regioncx
.annotate(&mut err
);
353 fn for_each_region_constraint(
354 closure_region_requirements
: &ClosureRegionRequirements
,
355 with_msg
: &mut dyn FnMut(&str) -> io
::Result
<()>,
356 ) -> io
::Result
<()> {
357 for req
in &closure_region_requirements
.outlives_requirements
{
358 let subject
: &dyn Debug
= match &req
.subject
{
359 ClosureOutlivesSubject
::Region(subject
) => subject
,
360 ClosureOutlivesSubject
::Ty(ty
) => ty
,
364 subject
, req
.outlived_free_region
,
370 /// Right now, we piggy back on the `ReVar` to store our NLL inference
371 /// regions. These are indexed with `RegionVid`. This method will
372 /// assert that the region is a `ReVar` and extract its internal index.
373 /// This is reasonable because in our MIR we replace all universal regions
374 /// with inference variables.
375 pub trait ToRegionVid
{
376 fn to_region_vid(self) -> RegionVid
;
379 impl<'tcx
> ToRegionVid
for &'tcx RegionKind
{
380 fn to_region_vid(self) -> RegionVid
{
381 if let ty
::ReVar(vid
) = self {
384 bug
!("region is not an ReVar: {:?}", self)
389 impl ToRegionVid
for RegionVid
{
390 fn to_region_vid(self) -> RegionVid
{
395 fn live_variable_set(regular
: &LocalSet
, drops
: &LocalSet
) -> String
{
396 // sort and deduplicate:
397 let all_locals
: BTreeSet
<_
> = regular
.iter().chain(drops
.iter()).collect();
399 // construct a string with each local, including `(drop)` if it is
400 // only dropped, versus a regular use.
401 let mut string
= String
::new();
402 for local
in all_locals
{
403 string
.push_str(&format
!("{:?}", local
));
405 if !regular
.contains(&local
) {
406 assert
!(drops
.contains(&local
));
407 string
.push_str(" (drop)");
410 string
.push_str(", ");
413 let len
= if string
.is_empty() {
419 format
!("[{}]", &string
[..len
])