1 //! The entry point of the NLL borrow checker.
3 use rustc::infer::InferCtxt;
5 BasicBlock, Body, BodyAndCache, ClosureOutlivesSubject, ClosureRegionRequirements, LocalKind,
6 Location, Promoted, ReadOnlyBodyAndCache,
8 use rustc::ty::{self, RegionKind, RegionVid};
9 use rustc_data_structures::fx::FxHashMap;
10 use rustc_errors::Diagnostic;
11 use rustc_hir::def_id::DefId;
12 use rustc_index::vec::IndexVec;
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::generic::ResultsCursor;
25 use crate::dataflow::move_paths::{InitKind, InitLocation, MoveData};
26 use crate::dataflow::MaybeInitializedPlaces;
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,
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>,
62 param_env: ty::ParamEnv<'tcx>,
63 body: &mut BodyAndCache<'tcx>,
64 promoted: &mut IndexVec<Promoted, BodyAndCache<'tcx>>,
65 ) -> UniversalRegions<'tcx> {
66 debug!("replace_regions_in_mir(def_id={:?})", def_id);
68 // Compute named region information. This also renumbers the inputs/outputs.
69 let universal_regions = UniversalRegions::new(infcx, def_id, param_env);
71 // Replace all remaining regions with fresh inference variables.
72 renumber::renumber_mir(infcx, body, promoted);
74 let source = MirSource::item(def_id);
75 mir_util::dump_mir(infcx.tcx, None, "renumber", &0, source, 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() {
95 .extend(move_path.parents(&move_data.move_paths).iter().map(|&parent| (child, parent)));
99 for init in move_data.inits.iter() {
100 match init.location {
101 InitLocation::Statement(location) => {
102 let block_data = &body[location.block];
103 let is_terminator = location.statement_index == block_data.statements.len();
105 if is_terminator && init.kind == InitKind::NonPanicPathOnly {
106 // We are at the terminator of an init that has a panic path,
107 // and where the init should not happen on panic
109 for &successor in block_data.terminator().successors() {
110 if body[successor].is_cleanup {
114 // The initialization happened in (or rather, when arriving at)
115 // the successors, but not in the unwind block.
116 let first_statement = Location { block: successor, statement_index: 0 };
119 .push((init.path, location_table.start_index(first_statement)));
122 // In all other cases, the initialization just happens at the
123 // midpoint, like any other effect.
124 all_facts.initialized_at.push((init.path, location_table.mid_index(location)));
127 // Arguments are initialized on function entry
128 InitLocation::Argument(local) => {
129 assert!(body.local_kind(local) == LocalKind::Arg);
130 let fn_entry = Location { block: BasicBlock::from_u32(0u32), statement_index: 0 };
131 all_facts.initialized_at.push((init.path, location_table.start_index(fn_entry)));
137 // deinitialisation is assumed to always happen!
140 .extend(move_data.moves.iter().map(|mo| (mo.path, location_table.mid_index(mo.source))));
143 /// Computes the (non-lexical) regions from the input MIR.
145 /// This may result in errors being reported.
146 pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
147 infcx: &InferCtxt<'cx, 'tcx>,
149 universal_regions: UniversalRegions<'tcx>,
150 body: ReadOnlyBodyAndCache<'_, 'tcx>,
151 promoted: &IndexVec<Promoted, ReadOnlyBodyAndCache<'_, 'tcx>>,
152 location_table: &LocationTable,
153 param_env: ty::ParamEnv<'tcx>,
154 flow_inits: &mut ResultsCursor<'cx, 'tcx, MaybeInitializedPlaces<'cx, 'tcx>>,
155 move_data: &MoveData<'tcx>,
156 borrow_set: &BorrowSet<'tcx>,
157 ) -> NllOutput<'tcx> {
158 let mut all_facts = AllFacts::enabled(infcx.tcx).then_some(AllFacts::default());
160 let universal_regions = Rc::new(universal_regions);
162 let elements = &Rc::new(RegionValueElements::new(&body));
164 // Run the MIR type-checker.
165 let MirTypeckResults { constraints, universal_region_relations, opaque_type_values } =
166 type_check::type_check(
181 if let Some(all_facts) = &mut all_facts {
182 let _prof_timer = infcx.tcx.prof.generic_activity("polonius_fact_generation");
183 all_facts.universal_region.extend(universal_regions.universal_regions());
184 populate_polonius_move_facts(all_facts, move_data, location_table, &body);
186 // Emit universal regions facts, and their relations, for Polonius.
188 // 1: universal regions are modeled in Polonius as a pair:
189 // - the universal region vid itself.
190 // - a "placeholder loan" associated to this universal region. Since they don't exist in
191 // the `borrow_set`, their `BorrowIndex` are synthesized as the universal region index
192 // added to the existing number of loans, as if they succeeded them in the set.
194 let borrow_count = borrow_set.borrows.len();
196 "compute_regions: polonius placeholders, num_universals={}, borrow_count={}",
197 universal_regions.len(),
201 for universal_region in universal_regions.universal_regions() {
202 let universal_region_idx = universal_region.index();
203 let placeholder_loan_idx = borrow_count + universal_region_idx;
204 all_facts.placeholder.push((universal_region, placeholder_loan_idx.into()));
207 // 2: the universal region relations `outlives` constraints are emitted as
208 // `known_subset` facts.
209 for (fr1, fr2) in universal_region_relations.known_outlives() {
212 "compute_regions: emitting polonius `known_subset` fr1={:?}, fr2={:?}",
215 all_facts.known_subset.push((*fr1, *fr2));
220 // Create the region inference context, taking ownership of the
221 // region inference data that was contained in `infcx`, and the
222 // base constraints generated by the type-check.
223 let var_origins = infcx.take_region_var_origins();
224 let MirTypeckRegionConstraints {
226 placeholder_index_to_region: _,
227 mut liveness_constraints,
228 outlives_constraints,
230 closure_bounds_mapping,
233 let placeholder_indices = Rc::new(placeholder_indices);
235 constraint_generation::generate_constraints(
237 &mut liveness_constraints,
244 let mut regioncx = RegionInferenceContext::new(
248 universal_region_relations,
249 outlives_constraints,
251 closure_bounds_mapping,
253 liveness_constraints,
257 // Generate various additional constraints.
258 invalidation::generate_invalidates(infcx.tcx, &mut all_facts, location_table, body, borrow_set);
260 // Dump facts if requested.
261 let polonius_output = all_facts.and_then(|all_facts| {
262 if infcx.tcx.sess.opts.debugging_opts.nll_facts {
263 let def_path = infcx.tcx.hir().def_path(def_id);
265 PathBuf::from("nll-facts").join(def_path.to_filename_friendly_no_crate());
266 all_facts.write_to_dir(dir_path, location_table).unwrap();
269 if infcx.tcx.sess.opts.debugging_opts.polonius {
271 env::var("POLONIUS_ALGORITHM").unwrap_or_else(|_| String::from("Naive"));
272 let algorithm = Algorithm::from_str(&algorithm).unwrap();
273 debug!("compute_regions: using polonius algorithm {:?}", algorithm);
274 let _prof_timer = infcx.tcx.prof.generic_activity("polonius_analysis");
275 Some(Rc::new(Output::compute(&all_facts, algorithm, false)))
281 // Solve the region constraints.
282 let (closure_region_requirements, nll_errors) =
283 regioncx.solve(infcx, &body, def_id, polonius_output.clone());
289 opt_closure_req: closure_region_requirements,
294 pub(super) fn dump_mir_results<'a, 'tcx>(
295 infcx: &InferCtxt<'a, 'tcx>,
296 source: MirSource<'tcx>,
298 regioncx: &RegionInferenceContext<'_>,
299 closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
301 if !mir_util::dump_enabled(infcx.tcx, "nll", source) {
305 mir_util::dump_mir(infcx.tcx, None, "nll", &0, source, body, |pass_where, out| {
307 // Before the CFG, dump out the values for each region variable.
308 PassWhere::BeforeCFG => {
309 regioncx.dump_mir(out)?;
312 if let Some(closure_region_requirements) = closure_region_requirements {
313 writeln!(out, "| Free Region Constraints")?;
314 for_each_region_constraint(closure_region_requirements, &mut |msg| {
315 writeln!(out, "| {}", msg)
321 PassWhere::BeforeLocation(_) => {}
323 PassWhere::AfterTerminator(_) => {}
325 PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {}
330 // Also dump the inference graph constraints as a graphviz file.
331 let _: io::Result<()> = try {
333 pretty::create_dump_file(infcx.tcx, "regioncx.all.dot", None, "nll", &0, source)?;
334 regioncx.dump_graphviz_raw_constraints(&mut file)?;
337 // Also dump the inference graph constraints as a graphviz file.
338 let _: io::Result<()> = try {
340 pretty::create_dump_file(infcx.tcx, "regioncx.scc.dot", None, "nll", &0, source)?;
341 regioncx.dump_graphviz_scc_constraints(&mut file)?;
345 pub(super) fn dump_annotation<'a, 'tcx>(
346 infcx: &InferCtxt<'a, 'tcx>,
349 regioncx: &RegionInferenceContext<'tcx>,
350 closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
351 errors_buffer: &mut Vec<Diagnostic>,
354 let base_def_id = tcx.closure_base_def_id(mir_def_id);
355 if !tcx.has_attr(base_def_id, sym::rustc_regions) {
359 // When the enclosing function is tagged with `#[rustc_regions]`,
360 // we dump out various bits of state as warnings. This is useful
361 // for verifying that the compiler is behaving as expected. These
362 // warnings focus on the closure region requirements -- for
363 // viewing the intraprocedural state, the -Zdump-mir output is
366 if let Some(closure_region_requirements) = closure_region_requirements {
367 let mut err = tcx.sess.diagnostic().span_note_diag(body.span, "external requirements");
369 regioncx.annotate(tcx, &mut err);
372 "number of external vids: {}",
373 closure_region_requirements.num_external_vids
376 // Dump the region constraints we are imposing *between* those
377 // newly created variables.
378 for_each_region_constraint(closure_region_requirements, &mut |msg| {
384 err.buffer(errors_buffer);
386 let mut err = tcx.sess.diagnostic().span_note_diag(body.span, "no external requirements");
387 regioncx.annotate(tcx, &mut err);
389 err.buffer(errors_buffer);
393 fn for_each_region_constraint(
394 closure_region_requirements: &ClosureRegionRequirements<'_>,
395 with_msg: &mut dyn FnMut(&str) -> io::Result<()>,
396 ) -> io::Result<()> {
397 for req in &closure_region_requirements.outlives_requirements {
398 let subject: &dyn Debug = match &req.subject {
399 ClosureOutlivesSubject::Region(subject) => subject,
400 ClosureOutlivesSubject::Ty(ty) => ty,
402 with_msg(&format!("where {:?}: {:?}", subject, req.outlived_free_region,))?;
407 /// Right now, we piggy back on the `ReVar` to store our NLL inference
408 /// regions. These are indexed with `RegionVid`. This method will
409 /// assert that the region is a `ReVar` and extract its internal index.
410 /// This is reasonable because in our MIR we replace all universal regions
411 /// with inference variables.
412 pub trait ToRegionVid {
413 fn to_region_vid(self) -> RegionVid;
416 impl<'tcx> ToRegionVid for &'tcx RegionKind {
417 fn to_region_vid(self) -> RegionVid {
418 if let ty::ReVar(vid) = self { *vid } else { bug!("region is not an ReVar: {:?}", self) }
422 impl ToRegionVid for RegionVid {
423 fn to_region_vid(self) -> RegionVid {
428 crate trait ConstraintDescription {
429 fn description(&self) -> &'static str;