]> git.proxmox.com Git - rustc.git/blob - src/librustc_mir/borrow_check/nll.rs
New upstream version 1.47.0+dfsg1
[rustc.git] / src / librustc_mir / borrow_check / nll.rs
1 //! The entry point of the NLL borrow checker.
2
3 use rustc_data_structures::fx::FxHashMap;
4 use rustc_errors::Diagnostic;
5 use rustc_hir::def_id::{DefId, LocalDefId};
6 use rustc_index::vec::IndexVec;
7 use rustc_infer::infer::InferCtxt;
8 use rustc_middle::mir::{
9 BasicBlock, Body, ClosureOutlivesSubject, ClosureRegionRequirements, LocalKind, Location,
10 Promoted,
11 };
12 use rustc_middle::ty::{self, InstanceDef, RegionKind, RegionVid};
13 use rustc_span::symbol::sym;
14 use std::env;
15 use std::fmt::Debug;
16 use std::io;
17 use std::path::PathBuf;
18 use std::rc::Rc;
19 use std::str::FromStr;
20
21 use self::mir_util::PassWhere;
22 use polonius_engine::{Algorithm, Output};
23
24 use crate::dataflow::impls::MaybeInitializedPlaces;
25 use crate::dataflow::move_paths::{InitKind, InitLocation, MoveData};
26 use crate::dataflow::ResultsCursor;
27 use crate::transform::MirSource;
28 use crate::util as mir_util;
29 use crate::util::pretty;
30
31 use crate::borrow_check::{
32 borrow_set::BorrowSet,
33 constraint_generation,
34 diagnostics::RegionErrors,
35 facts::{AllFacts, AllFactsExt, RustcFacts},
36 invalidation,
37 location::LocationTable,
38 region_infer::{values::RegionValueElements, RegionInferenceContext},
39 renumber,
40 type_check::{self, MirTypeckRegionConstraints, MirTypeckResults},
41 universal_regions::UniversalRegions,
42 Upvar,
43 };
44
45 crate type PoloniusOutput = Output<RustcFacts>;
46
47 /// The output of `nll::compute_regions`. This includes the computed `RegionInferenceContext`, any
48 /// closure requirements to propagate, and any generated errors.
49 crate struct NllOutput<'tcx> {
50 pub regioncx: RegionInferenceContext<'tcx>,
51 pub opaque_type_values: FxHashMap<DefId, ty::ResolvedOpaqueTy<'tcx>>,
52 pub polonius_output: Option<Rc<PoloniusOutput>>,
53 pub opt_closure_req: Option<ClosureRegionRequirements<'tcx>>,
54 pub nll_errors: RegionErrors<'tcx>,
55 }
56
57 /// Rewrites the regions in the MIR to use NLL variables, also scraping out the set of universal
58 /// regions (e.g., region parameters) declared on the function. That set will need to be given to
59 /// `compute_regions`.
60 pub(in crate::borrow_check) fn replace_regions_in_mir<'cx, 'tcx>(
61 infcx: &InferCtxt<'cx, 'tcx>,
62 def: ty::WithOptConstParam<LocalDefId>,
63 param_env: ty::ParamEnv<'tcx>,
64 body: &mut Body<'tcx>,
65 promoted: &mut IndexVec<Promoted, Body<'tcx>>,
66 ) -> UniversalRegions<'tcx> {
67 debug!("replace_regions_in_mir(def={:?})", def);
68
69 // Compute named region information. This also renumbers the inputs/outputs.
70 let universal_regions = UniversalRegions::new(infcx, def, param_env);
71
72 // Replace all remaining regions with fresh inference variables.
73 renumber::renumber_mir(infcx, body, promoted);
74
75 let source = MirSource { instance: InstanceDef::Item(def.to_global()), promoted: None };
76 mir_util::dump_mir(infcx.tcx, None, "renumber", &0, source, body, |_, _| Ok(()));
77
78 universal_regions
79 }
80
81 // This function populates an AllFacts instance with base facts related to
82 // MovePaths and needed for the move analysis.
83 fn populate_polonius_move_facts(
84 all_facts: &mut AllFacts,
85 move_data: &MoveData<'_>,
86 location_table: &LocationTable,
87 body: &Body<'_>,
88 ) {
89 all_facts
90 .path_is_var
91 .extend(move_data.rev_lookup.iter_locals_enumerated().map(|(v, &m)| (m, v)));
92
93 for (child, move_path) in move_data.move_paths.iter_enumerated() {
94 if let Some(parent) = move_path.parent {
95 all_facts.child_path.push((child, parent));
96 }
97 }
98
99 let fn_entry_start = location_table
100 .start_index(Location { block: BasicBlock::from_u32(0u32), statement_index: 0 });
101
102 // initialized_at
103 for init in move_data.inits.iter() {
104 match init.location {
105 InitLocation::Statement(location) => {
106 let block_data = &body[location.block];
107 let is_terminator = location.statement_index == block_data.statements.len();
108
109 if is_terminator && init.kind == InitKind::NonPanicPathOnly {
110 // We are at the terminator of an init that has a panic path,
111 // and where the init should not happen on panic
112
113 for &successor in block_data.terminator().successors() {
114 if body[successor].is_cleanup {
115 continue;
116 }
117
118 // The initialization happened in (or rather, when arriving at)
119 // the successors, but not in the unwind block.
120 let first_statement = Location { block: successor, statement_index: 0 };
121 all_facts
122 .path_assigned_at_base
123 .push((init.path, location_table.start_index(first_statement)));
124 }
125 } else {
126 // In all other cases, the initialization just happens at the
127 // midpoint, like any other effect.
128 all_facts
129 .path_assigned_at_base
130 .push((init.path, location_table.mid_index(location)));
131 }
132 }
133 // Arguments are initialized on function entry
134 InitLocation::Argument(local) => {
135 assert!(body.local_kind(local) == LocalKind::Arg);
136 all_facts.path_assigned_at_base.push((init.path, fn_entry_start));
137 }
138 }
139 }
140
141 for (local, &path) in move_data.rev_lookup.iter_locals_enumerated() {
142 if body.local_kind(local) != LocalKind::Arg {
143 // Non-arguments start out deinitialised; we simulate this with an
144 // initial move:
145 all_facts.path_moved_at_base.push((path, fn_entry_start));
146 }
147 }
148
149 // moved_out_at
150 // deinitialisation is assumed to always happen!
151 all_facts
152 .path_moved_at_base
153 .extend(move_data.moves.iter().map(|mo| (mo.path, location_table.mid_index(mo.source))));
154 }
155
156 /// Computes the (non-lexical) regions from the input MIR.
157 ///
158 /// This may result in errors being reported.
159 pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
160 infcx: &InferCtxt<'cx, 'tcx>,
161 def_id: LocalDefId,
162 universal_regions: UniversalRegions<'tcx>,
163 body: &Body<'tcx>,
164 promoted: &IndexVec<Promoted, Body<'tcx>>,
165 location_table: &LocationTable,
166 param_env: ty::ParamEnv<'tcx>,
167 flow_inits: &mut ResultsCursor<'cx, 'tcx, MaybeInitializedPlaces<'cx, 'tcx>>,
168 move_data: &MoveData<'tcx>,
169 borrow_set: &BorrowSet<'tcx>,
170 upvars: &[Upvar],
171 ) -> NllOutput<'tcx> {
172 let mut all_facts = AllFacts::enabled(infcx.tcx).then_some(AllFacts::default());
173
174 let universal_regions = Rc::new(universal_regions);
175
176 let elements = &Rc::new(RegionValueElements::new(&body));
177
178 // Run the MIR type-checker.
179 let MirTypeckResults { constraints, universal_region_relations, opaque_type_values } =
180 type_check::type_check(
181 infcx,
182 param_env,
183 body,
184 promoted,
185 def_id,
186 &universal_regions,
187 location_table,
188 borrow_set,
189 &mut all_facts,
190 flow_inits,
191 move_data,
192 elements,
193 upvars,
194 );
195
196 if let Some(all_facts) = &mut all_facts {
197 let _prof_timer = infcx.tcx.prof.generic_activity("polonius_fact_generation");
198 all_facts.universal_region.extend(universal_regions.universal_regions());
199 populate_polonius_move_facts(all_facts, move_data, location_table, &body);
200
201 // Emit universal regions facts, and their relations, for Polonius.
202 //
203 // 1: universal regions are modeled in Polonius as a pair:
204 // - the universal region vid itself.
205 // - a "placeholder loan" associated to this universal region. Since they don't exist in
206 // the `borrow_set`, their `BorrowIndex` are synthesized as the universal region index
207 // added to the existing number of loans, as if they succeeded them in the set.
208 //
209 let borrow_count = borrow_set.len();
210 debug!(
211 "compute_regions: polonius placeholders, num_universals={}, borrow_count={}",
212 universal_regions.len(),
213 borrow_count
214 );
215
216 for universal_region in universal_regions.universal_regions() {
217 let universal_region_idx = universal_region.index();
218 let placeholder_loan_idx = borrow_count + universal_region_idx;
219 all_facts.placeholder.push((universal_region, placeholder_loan_idx.into()));
220 }
221
222 // 2: the universal region relations `outlives` constraints are emitted as
223 // `known_subset` facts.
224 for (fr1, fr2) in universal_region_relations.known_outlives() {
225 if fr1 != fr2 {
226 debug!(
227 "compute_regions: emitting polonius `known_subset` fr1={:?}, fr2={:?}",
228 fr1, fr2
229 );
230 all_facts.known_subset.push((*fr1, *fr2));
231 }
232 }
233 }
234
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 {
240 placeholder_indices,
241 placeholder_index_to_region: _,
242 mut liveness_constraints,
243 outlives_constraints,
244 member_constraints,
245 closure_bounds_mapping,
246 type_tests,
247 } = constraints;
248 let placeholder_indices = Rc::new(placeholder_indices);
249
250 constraint_generation::generate_constraints(
251 infcx,
252 &mut liveness_constraints,
253 &mut all_facts,
254 location_table,
255 &body,
256 borrow_set,
257 );
258
259 let mut regioncx = RegionInferenceContext::new(
260 var_origins,
261 universal_regions,
262 placeholder_indices,
263 universal_region_relations,
264 outlives_constraints,
265 member_constraints,
266 closure_bounds_mapping,
267 type_tests,
268 liveness_constraints,
269 elements,
270 );
271
272 // Generate various additional constraints.
273 invalidation::generate_invalidates(infcx.tcx, &mut all_facts, location_table, body, borrow_set);
274
275 // Dump facts if requested.
276 let polonius_output = all_facts.and_then(|all_facts| {
277 if infcx.tcx.sess.opts.debugging_opts.nll_facts {
278 let def_path = infcx.tcx.def_path(def_id.to_def_id());
279 let dir_path =
280 PathBuf::from("nll-facts").join(def_path.to_filename_friendly_no_crate());
281 all_facts.write_to_dir(dir_path, location_table).unwrap();
282 }
283
284 if infcx.tcx.sess.opts.debugging_opts.polonius {
285 let algorithm =
286 env::var("POLONIUS_ALGORITHM").unwrap_or_else(|_| String::from("Naive"));
287 let algorithm = Algorithm::from_str(&algorithm).unwrap();
288 debug!("compute_regions: using polonius algorithm {:?}", algorithm);
289 let _prof_timer = infcx.tcx.prof.generic_activity("polonius_analysis");
290 Some(Rc::new(Output::compute(&all_facts, algorithm, false)))
291 } else {
292 None
293 }
294 });
295
296 // Solve the region constraints.
297 let (closure_region_requirements, nll_errors) =
298 regioncx.solve(infcx, &body, def_id.to_def_id(), polonius_output.clone());
299
300 if !nll_errors.is_empty() {
301 // Suppress unhelpful extra errors in `infer_opaque_types`.
302 infcx.set_tainted_by_errors();
303 }
304
305 let remapped_opaque_tys = regioncx.infer_opaque_types(&infcx, opaque_type_values, body.span);
306
307 NllOutput {
308 regioncx,
309 opaque_type_values: remapped_opaque_tys,
310 polonius_output,
311 opt_closure_req: closure_region_requirements,
312 nll_errors,
313 }
314 }
315
316 pub(super) fn dump_mir_results<'a, 'tcx>(
317 infcx: &InferCtxt<'a, 'tcx>,
318 source: MirSource<'tcx>,
319 body: &Body<'tcx>,
320 regioncx: &RegionInferenceContext<'tcx>,
321 closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
322 ) {
323 if !mir_util::dump_enabled(infcx.tcx, "nll", source.def_id()) {
324 return;
325 }
326
327 mir_util::dump_mir(infcx.tcx, None, "nll", &0, source, body, |pass_where, out| {
328 match pass_where {
329 // Before the CFG, dump out the values for each region variable.
330 PassWhere::BeforeCFG => {
331 regioncx.dump_mir(infcx.tcx, out)?;
332 writeln!(out, "|")?;
333
334 if let Some(closure_region_requirements) = closure_region_requirements {
335 writeln!(out, "| Free Region Constraints")?;
336 for_each_region_constraint(closure_region_requirements, &mut |msg| {
337 writeln!(out, "| {}", msg)
338 })?;
339 writeln!(out, "|")?;
340 }
341 }
342
343 PassWhere::BeforeLocation(_) => {}
344
345 PassWhere::AfterTerminator(_) => {}
346
347 PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {}
348 }
349 Ok(())
350 });
351
352 // Also dump the inference graph constraints as a graphviz file.
353 let _: io::Result<()> = try {
354 let mut file =
355 pretty::create_dump_file(infcx.tcx, "regioncx.all.dot", None, "nll", &0, source)?;
356 regioncx.dump_graphviz_raw_constraints(&mut file)?;
357 };
358
359 // Also dump the inference graph constraints as a graphviz file.
360 let _: io::Result<()> = try {
361 let mut file =
362 pretty::create_dump_file(infcx.tcx, "regioncx.scc.dot", None, "nll", &0, source)?;
363 regioncx.dump_graphviz_scc_constraints(&mut file)?;
364 };
365 }
366
367 pub(super) fn dump_annotation<'a, 'tcx>(
368 infcx: &InferCtxt<'a, 'tcx>,
369 body: &Body<'tcx>,
370 mir_def_id: DefId,
371 regioncx: &RegionInferenceContext<'tcx>,
372 closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
373 opaque_type_values: &FxHashMap<DefId, ty::ResolvedOpaqueTy<'tcx>>,
374 errors_buffer: &mut Vec<Diagnostic>,
375 ) {
376 let tcx = infcx.tcx;
377 let base_def_id = tcx.closure_base_def_id(mir_def_id);
378 if !tcx.has_attr(base_def_id, sym::rustc_regions) {
379 return;
380 }
381
382 // When the enclosing function is tagged with `#[rustc_regions]`,
383 // we dump out various bits of state as warnings. This is useful
384 // for verifying that the compiler is behaving as expected. These
385 // warnings focus on the closure region requirements -- for
386 // viewing the intraprocedural state, the -Zdump-mir output is
387 // better.
388
389 let mut err = if let Some(closure_region_requirements) = closure_region_requirements {
390 let mut err = tcx.sess.diagnostic().span_note_diag(body.span, "external requirements");
391
392 regioncx.annotate(tcx, &mut err);
393
394 err.note(&format!(
395 "number of external vids: {}",
396 closure_region_requirements.num_external_vids
397 ));
398
399 // Dump the region constraints we are imposing *between* those
400 // newly created variables.
401 for_each_region_constraint(closure_region_requirements, &mut |msg| {
402 err.note(msg);
403 Ok(())
404 })
405 .unwrap();
406
407 err
408 } else {
409 let mut err = tcx.sess.diagnostic().span_note_diag(body.span, "no external requirements");
410 regioncx.annotate(tcx, &mut err);
411
412 err
413 };
414
415 if !opaque_type_values.is_empty() {
416 err.note(&format!("Inferred opaque type values:\n{:#?}", opaque_type_values));
417 }
418
419 err.buffer(errors_buffer);
420 }
421
422 fn for_each_region_constraint(
423 closure_region_requirements: &ClosureRegionRequirements<'_>,
424 with_msg: &mut dyn FnMut(&str) -> io::Result<()>,
425 ) -> io::Result<()> {
426 for req in &closure_region_requirements.outlives_requirements {
427 let subject: &dyn Debug = match &req.subject {
428 ClosureOutlivesSubject::Region(subject) => subject,
429 ClosureOutlivesSubject::Ty(ty) => ty,
430 };
431 with_msg(&format!("where {:?}: {:?}", subject, req.outlived_free_region,))?;
432 }
433 Ok(())
434 }
435
436 /// Right now, we piggy back on the `ReVar` to store our NLL inference
437 /// regions. These are indexed with `RegionVid`. This method will
438 /// assert that the region is a `ReVar` and extract its internal index.
439 /// This is reasonable because in our MIR we replace all universal regions
440 /// with inference variables.
441 pub trait ToRegionVid {
442 fn to_region_vid(self) -> RegionVid;
443 }
444
445 impl<'tcx> ToRegionVid for &'tcx RegionKind {
446 fn to_region_vid(self) -> RegionVid {
447 if let ty::ReVar(vid) = self { *vid } else { bug!("region is not an ReVar: {:?}", self) }
448 }
449 }
450
451 impl ToRegionVid for RegionVid {
452 fn to_region_vid(self) -> RegionVid {
453 self
454 }
455 }
456
457 crate trait ConstraintDescription {
458 fn description(&self) -> &'static str;
459 }