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::{MirTypeckResults, MirTypeckRegionConstraints};
15 use borrow_check::nll::type_check::liveness::liveness_map::{NllLivenessMap, LocalWithRegion};
16 use borrow_check::nll::region_infer::values::RegionValueElements;
17 use dataflow::indexes::BorrowIndex;
18 use dataflow::move_paths::MoveData;
19 use dataflow::FlowAtLocation;
20 use dataflow::MaybeInitializedPlaces;
21 use rustc::hir::def_id::DefId;
22 use rustc::infer::InferCtxt;
23 use rustc::mir::{ClosureOutlivesSubject, ClosureRegionRequirements, Mir};
24 use rustc::ty::{self, RegionKind, RegionVid};
25 use rustc::util::nodemap::FxHashMap;
26 use rustc_errors::Diagnostic;
27 use std::collections::BTreeSet;
31 use std::path::PathBuf;
33 use std::str::FromStr;
34 use transform::MirSource;
35 use util::liveness::{LivenessResults, LiveVarSet};
37 use self::mir_util::PassWhere;
38 use polonius_engine::{Algorithm, Output};
40 use util::pretty::{self, ALIGN};
42 mod constraint_generation;
43 pub mod explain_borrow;
46 crate mod region_infer;
49 mod universal_regions;
53 use self::facts::AllFacts;
54 use self::region_infer::RegionInferenceContext;
55 use self::universal_regions::UniversalRegions;
57 /// Rewrites the regions in the MIR to use NLL variables, also
58 /// scraping out the set of universal regions (e.g., region parameters)
59 /// declared on the function. That set will need to be given to
60 /// `compute_regions`.
61 pub(in borrow_check) fn replace_regions_in_mir<'cx, 'gcx, 'tcx>(
62 infcx: &InferCtxt<'cx, 'gcx, 'tcx>,
64 param_env: ty::ParamEnv<'tcx>,
66 ) -> UniversalRegions<'tcx> {
67 debug!("replace_regions_in_mir(def_id={:?})", def_id);
69 // Compute named region information. This also renumbers the inputs/outputs.
70 let universal_regions = UniversalRegions::new(infcx, def_id, param_env);
72 // Replace all remaining regions with fresh inference variables.
73 renumber::renumber_mir(infcx, mir);
75 let source = MirSource::item(def_id);
76 mir_util::dump_mir(infcx.tcx, None, "renumber", &0, source, mir, |_, _| Ok(()));
81 /// Computes the (non-lexical) regions from the input MIR.
83 /// This may result in errors being reported.
84 pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
85 infcx: &InferCtxt<'cx, 'gcx, 'tcx>,
87 universal_regions: UniversalRegions<'tcx>,
89 location_table: &LocationTable,
90 param_env: ty::ParamEnv<'gcx>,
91 flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'cx, 'gcx, 'tcx>>,
92 move_data: &MoveData<'tcx>,
93 borrow_set: &BorrowSet<'tcx>,
94 errors_buffer: &mut Vec<Diagnostic>,
96 RegionInferenceContext<'tcx>,
97 Option<Rc<Output<RegionVid, BorrowIndex, LocationIndex>>>,
98 Option<ClosureRegionRequirements<'gcx>>,
100 let mut all_facts = if AllFacts::enabled(infcx.tcx) {
101 Some(AllFacts::default())
106 let universal_regions = Rc::new(universal_regions);
108 let elements = &Rc::new(RegionValueElements::new(mir));
110 // Run the MIR type-checker.
111 let MirTypeckResults {
113 universal_region_relations,
116 } = type_check::type_check(
130 if let Some(all_facts) = &mut all_facts {
133 .extend(universal_regions.universal_regions());
136 // Create the region inference context, taking ownership of the
137 // region inference data that was contained in `infcx`, and the
138 // base constraints generated by the type-check.
139 let var_origins = infcx.take_region_var_origins();
140 let MirTypeckRegionConstraints {
141 mut liveness_constraints,
142 outlives_constraints,
146 constraint_generation::generate_constraints(
148 &mut liveness_constraints,
155 let mut regioncx = RegionInferenceContext::new(
158 universal_region_relations,
160 outlives_constraints,
162 liveness_constraints,
166 // Generate various additional constraints.
167 invalidation::generate_invalidates(
176 // Dump facts if requested.
177 let polonius_output = all_facts.and_then(|all_facts| {
178 if infcx.tcx.sess.opts.debugging_opts.nll_facts {
179 let def_path = infcx.tcx.hir.def_path(def_id);
181 PathBuf::from("nll-facts").join(def_path.to_filename_friendly_no_crate());
182 all_facts.write_to_dir(dir_path, location_table).unwrap();
185 if infcx.tcx.sess.opts.debugging_opts.polonius {
186 let algorithm = env::var("POLONIUS_ALGORITHM")
187 .unwrap_or(String::from("DatafrogOpt"));
188 let algorithm = Algorithm::from_str(&algorithm).unwrap();
189 debug!("compute_regions: using polonius algorithm {:?}", algorithm);
190 Some(Rc::new(Output::compute(
200 // Solve the region constraints.
201 let closure_region_requirements = regioncx.solve(infcx, &mir, def_id, errors_buffer);
203 // Dump MIR results into a file, if that is enabled. This let us
204 // write unit-tests, as well as helping with debugging.
209 MirSource::item(def_id),
212 &closure_region_requirements,
215 // We also have a `#[rustc_nll]` annotation that causes us to dump
217 dump_annotation(infcx, &mir, def_id, ®ioncx, &closure_region_requirements, errors_buffer);
219 (regioncx, polonius_output, closure_region_requirements)
222 fn dump_mir_results<'a, 'gcx, 'tcx>(
223 infcx: &InferCtxt<'a, 'gcx, 'tcx>,
224 liveness: &LivenessResults<LocalWithRegion>,
225 liveness_map: &NllLivenessMap,
228 regioncx: &RegionInferenceContext,
229 closure_region_requirements: &Option<ClosureRegionRequirements>,
231 if !mir_util::dump_enabled(infcx.tcx, "nll", source) {
235 let regular_liveness_per_location: FxHashMap<_, _> = mir
239 let mut results = vec![];
242 .simulate_block(&mir, bb, liveness_map, |location, local_set| {
243 results.push((location, local_set.clone()));
249 let drop_liveness_per_location: FxHashMap<_, _> = mir
253 let mut results = vec![];
256 .simulate_block(&mir, bb, liveness_map, |location, local_set| {
257 results.push((location, local_set.clone()));
272 // Before the CFG, dump out the values for each region variable.
273 PassWhere::BeforeCFG => {
274 regioncx.dump_mir(out)?;
276 if let Some(closure_region_requirements) = closure_region_requirements {
278 writeln!(out, "| Free Region Constraints")?;
279 for_each_region_constraint(closure_region_requirements, &mut |msg| {
280 writeln!(out, "| {}", msg)
285 PassWhere::BeforeLocation(location) => {
286 let s = live_variable_set(
287 ®ular_liveness_per_location[&location],
288 &drop_liveness_per_location[&location],
292 "{:ALIGN$} | Live variables on entry to {:?}: {}",
300 // After each basic block, dump out the values
301 // that are live on exit from the basic block.
302 PassWhere::AfterTerminator(bb) => {
303 let s = live_variable_set(&liveness.regular.outs[bb], &liveness.drop.outs[bb]);
304 writeln!(out, " | Live variables on exit from {:?}: {}", bb, s)?;
307 PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {}
313 // Also dump the inference graph constraints as a graphviz file.
314 let _: io::Result<()> = do catch {
316 pretty::create_dump_file(infcx.tcx, "regioncx.all.dot", None, "nll", &0, source)?;
317 regioncx.dump_graphviz_raw_constraints(&mut file)?;
320 // Also dump the inference graph constraints as a graphviz file.
321 let _: io::Result<()> = do catch {
323 pretty::create_dump_file(infcx.tcx, "regioncx.scc.dot", None, "nll", &0, source)?;
324 regioncx.dump_graphviz_scc_constraints(&mut file)?;
328 fn dump_annotation<'a, 'gcx, 'tcx>(
329 infcx: &InferCtxt<'a, 'gcx, 'tcx>,
332 regioncx: &RegionInferenceContext,
333 closure_region_requirements: &Option<ClosureRegionRequirements>,
334 errors_buffer: &mut Vec<Diagnostic>,
337 let base_def_id = tcx.closure_base_def_id(mir_def_id);
338 if !tcx.has_attr(base_def_id, "rustc_regions") {
342 // When the enclosing function is tagged with `#[rustc_regions]`,
343 // we dump out various bits of state as warnings. This is useful
344 // for verifying that the compiler is behaving as expected. These
345 // warnings focus on the closure region requirements -- for
346 // viewing the intraprocedural state, the -Zdump-mir output is
349 if let Some(closure_region_requirements) = closure_region_requirements {
353 .span_note_diag(mir.span, "External requirements");
355 regioncx.annotate(&mut err);
358 "number of external vids: {}",
359 closure_region_requirements.num_external_vids
362 // Dump the region constraints we are imposing *between* those
363 // newly created variables.
364 for_each_region_constraint(closure_region_requirements, &mut |msg| {
369 err.buffer(errors_buffer);
374 .span_note_diag(mir.span, "No external requirements");
375 regioncx.annotate(&mut err);
377 err.buffer(errors_buffer);
381 fn for_each_region_constraint(
382 closure_region_requirements: &ClosureRegionRequirements,
383 with_msg: &mut dyn FnMut(&str) -> io::Result<()>,
384 ) -> io::Result<()> {
385 for req in &closure_region_requirements.outlives_requirements {
386 let subject: &dyn Debug = match &req.subject {
387 ClosureOutlivesSubject::Region(subject) => subject,
388 ClosureOutlivesSubject::Ty(ty) => ty,
392 subject, req.outlived_free_region,
398 /// Right now, we piggy back on the `ReVar` to store our NLL inference
399 /// regions. These are indexed with `RegionVid`. This method will
400 /// assert that the region is a `ReVar` and extract its internal index.
401 /// This is reasonable because in our MIR we replace all universal regions
402 /// with inference variables.
403 pub trait ToRegionVid {
404 fn to_region_vid(self) -> RegionVid;
407 impl<'tcx> ToRegionVid for &'tcx RegionKind {
408 fn to_region_vid(self) -> RegionVid {
409 if let ty::ReVar(vid) = self {
412 bug!("region is not an ReVar: {:?}", self)
417 impl ToRegionVid for RegionVid {
418 fn to_region_vid(self) -> RegionVid {
423 fn live_variable_set(
424 regular: &LiveVarSet<LocalWithRegion>,
425 drops: &LiveVarSet<LocalWithRegion>
427 // sort and deduplicate:
428 let all_locals: BTreeSet<_> = regular.iter().chain(drops.iter()).collect();
430 // construct a string with each local, including `(drop)` if it is
431 // only dropped, versus a regular use.
432 let mut string = String::new();
433 for local in all_locals {
434 string.push_str(&format!("{:?}", local));
436 if !regular.contains(&local) {
437 assert!(drops.contains(&local));
438 string.push_str(" (drop)");
441 string.push_str(", ");
444 let len = if string.is_empty() {
450 format!("[{}]", &string[..len])