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::nll::constraints::{OutlivesConstraint, ConstraintCategory};
12 use borrow_check::nll::region_infer::RegionInferenceContext;
13 use rustc::hir::def_id::DefId;
14 use rustc::infer::error_reporting::nice_region_error::NiceRegionError;
15 use rustc::infer::InferCtxt;
16 use rustc::mir::{Location, Mir};
17 use rustc::ty::{self, RegionVid};
18 use rustc_data_structures::indexed_vec::IndexVec;
19 use rustc_errors::{Diagnostic, DiagnosticBuilder};
20 use std::collections::VecDeque;
22 use syntax::symbol::keywords;
24 use syntax::errors::Applicability;
29 use self::region_name::RegionName;
31 impl fmt::Display for ConstraintCategory {
32 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
33 // Must end with a space. Allows for empty names to be provided.
35 ConstraintCategory::Assignment => write!(f, "assignment "),
36 ConstraintCategory::Return => write!(f, "returning this value "),
37 ConstraintCategory::Cast => write!(f, "cast "),
38 ConstraintCategory::CallArgument => write!(f, "argument "),
39 ConstraintCategory::TypeAnnotation => write!(f, "type annotation "),
40 ConstraintCategory::ClosureBounds => write!(f, "closure body "),
41 ConstraintCategory::SizedBound => write!(f, "proving this value is `Sized` "),
42 ConstraintCategory::CopyBound => write!(f, "copying this value "),
43 ConstraintCategory::OpaqueType => write!(f, "opaque type "),
44 ConstraintCategory::Boring
45 | ConstraintCategory::BoringNoLocation
46 | ConstraintCategory::Internal => write!(f, ""),
51 #[derive(Copy, Clone, PartialEq, Eq)]
54 FromOutlivesConstraint(OutlivesConstraint),
58 impl<'tcx> RegionInferenceContext<'tcx> {
59 /// Tries to find the best constraint to blame for the fact that
60 /// `R: from_region`, where `R` is some region that meets
61 /// `target_test`. This works by following the constraint graph,
62 /// creating a constraint path that forces `R` to outlive
63 /// `from_region`, and then finding the best choices within that
65 fn best_blame_constraint(
68 from_region: RegionVid,
69 target_test: impl Fn(RegionVid) -> bool,
70 ) -> (ConstraintCategory, Span, RegionVid) {
71 debug!("best_blame_constraint(from_region={:?})", from_region);
74 let (path, target_region) = self
75 .find_constraint_paths_between_regions(from_region, target_test)
78 "best_blame_constraint: path={:#?}",
83 self.constraint_sccs.scc(c.sup),
84 self.constraint_sccs.scc(c.sub),
89 // Classify each of the constraints along the path.
90 let mut categorized_path: Vec<(ConstraintCategory, Span)> = path
92 .map(|constraint| (constraint.category, constraint.locations.span(mir)))
95 "best_blame_constraint: categorized_path={:#?}",
99 // To find the best span to cite, we first try to look for the
100 // final constraint that is interesting and where the `sup` is
101 // not unified with the ultimate target region. The reason
102 // for this is that we have a chain of constraints that lead
103 // from the source to the target region, something like:
105 // '0: '1 ('0 is the source)
110 // '5: '6 ('6 is the target)
112 // Some of those regions are unified with `'6` (in the same
113 // SCC). We want to screen those out. After that point, the
114 // "closest" constraint we have to the end is going to be the
115 // most likely to be the point where the value escapes -- but
116 // we still want to screen for an "interesting" point to
117 // highlight (e.g., a call site or something).
118 let target_scc = self.constraint_sccs.scc(target_region);
119 let best_choice = (0..path.len()).rev().find(|&i| {
120 let constraint = path[i];
122 let constraint_sup_scc = self.constraint_sccs.scc(constraint.sup);
124 match categorized_path[i].0 {
125 ConstraintCategory::OpaqueType
126 | ConstraintCategory::Boring
127 | ConstraintCategory::BoringNoLocation
128 | ConstraintCategory::Internal => false,
129 _ => constraint_sup_scc != target_scc,
132 if let Some(i) = best_choice {
133 let (category, span) = categorized_path[i];
134 return (category, span, target_region);
137 // If that search fails, that is.. unusual. Maybe everything
138 // is in the same SCC or something. In that case, find what
139 // appears to be the most interesting point to report to the
140 // user via an even more ad-hoc guess.
141 categorized_path.sort_by(|p0, p1| p0.0.cmp(&p1.0));
142 debug!("best_blame_constraint: sorted_path={:#?}", categorized_path);
144 let &(category, span) = categorized_path.first().unwrap();
146 (category, span, target_region)
149 /// Walks the graph of constraints (where `'a: 'b` is considered
150 /// an edge `'a -> 'b`) to find all paths from `from_region` to
151 /// `to_region`. The paths are accumulated into the vector
152 /// `results`. The paths are stored as a series of
153 /// `ConstraintIndex` values -- in other words, a list of *edges*.
155 /// Returns: a series of constraints as well as the region `R`
156 /// that passed the target test.
157 fn find_constraint_paths_between_regions(
159 from_region: RegionVid,
160 target_test: impl Fn(RegionVid) -> bool,
161 ) -> Option<(Vec<OutlivesConstraint>, RegionVid)> {
162 let mut context = IndexVec::from_elem(Trace::NotVisited, &self.definitions);
163 context[from_region] = Trace::StartRegion;
165 // Use a deque so that we do a breadth-first search. We will
166 // stop at the first match, which ought to be the shortest
167 // path (fewest constraints).
168 let mut deque = VecDeque::new();
169 deque.push_back(from_region);
171 while let Some(r) = deque.pop_front() {
172 // Check if we reached the region we were looking for. If so,
173 // we can reconstruct the path that led to it and return it.
175 let mut result = vec![];
179 Trace::NotVisited => {
180 bug!("found unvisited region {:?} on path to {:?}", p, r)
182 Trace::FromOutlivesConstraint(c) => {
187 Trace::StartRegion => {
189 return Some((result, r));
195 // Otherwise, walk over the outgoing constraints and
196 // enqueue any regions we find, keeping track of how we
198 let fr_static = self.universal_regions.fr_static;
199 for constraint in self.constraint_graph.outgoing_edges(r,
202 assert_eq!(constraint.sup, r);
203 let sub_region = constraint.sub;
204 if let Trace::NotVisited = context[sub_region] {
205 context[sub_region] = Trace::FromOutlivesConstraint(constraint);
206 deque.push_back(sub_region);
214 /// Report an error because the universal region `fr` was required to outlive
215 /// `outlived_fr` but it is not known to do so. For example:
218 /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x }
221 /// Here we would be invoked with `fr = 'a` and `outlived_fr = `'b`.
222 pub(super) fn report_error(
225 infcx: &InferCtxt<'_, '_, 'tcx>,
228 outlived_fr: RegionVid,
229 errors_buffer: &mut Vec<Diagnostic>,
231 debug!("report_error(fr={:?}, outlived_fr={:?})", fr, outlived_fr);
233 let (category, span, _) = self.best_blame_constraint(
239 // Check if we can use one of the "nice region errors".
240 if let (Some(f), Some(o)) = (self.to_error_region(fr), self.to_error_region(outlived_fr)) {
241 let tables = infcx.tcx.typeck_tables_of(mir_def_id);
242 let nice = NiceRegionError::new_from_span(infcx.tcx, span, o, f, Some(tables));
243 if let Some(_error_reported) = nice.try_report_from_nll() {
248 let (fr_is_local, outlived_fr_is_local): (bool, bool) = (
249 self.universal_regions.is_local_free_region(fr),
250 self.universal_regions.is_local_free_region(outlived_fr),
253 debug!("report_error: fr_is_local={:?} outlived_fr_is_local={:?} category={:?}",
254 fr_is_local, outlived_fr_is_local, category);
255 match (category, fr_is_local, outlived_fr_is_local) {
256 (ConstraintCategory::Assignment, true, false) |
257 (ConstraintCategory::CallArgument, true, false) =>
258 self.report_escaping_data_error(mir, infcx, mir_def_id, fr, outlived_fr,
259 category, span, errors_buffer),
261 self.report_general_error(mir, infcx, mir_def_id, fr, fr_is_local,
262 outlived_fr, outlived_fr_is_local,
263 category, span, errors_buffer),
267 fn report_escaping_data_error(
270 infcx: &InferCtxt<'_, '_, 'tcx>,
273 outlived_fr: RegionVid,
274 category: ConstraintCategory,
276 errors_buffer: &mut Vec<Diagnostic>,
278 let fr_name_and_span = self.get_var_name_and_span_for_region(infcx.tcx, mir, fr);
279 let outlived_fr_name_and_span =
280 self.get_var_name_and_span_for_region(infcx.tcx, mir, outlived_fr);
282 let escapes_from = if infcx.tcx.is_closure(mir_def_id) { "closure" } else { "function" };
284 // Revert to the normal error in these cases.
285 // Assignments aren't "escapes" in function items.
286 if (fr_name_and_span.is_none() && outlived_fr_name_and_span.is_none())
287 || (category == ConstraintCategory::Assignment && escapes_from == "function")
289 return self.report_general_error(mir, infcx, mir_def_id,
290 fr, true, outlived_fr, false,
291 category, span, errors_buffer);
294 let mut diag = infcx.tcx.sess.struct_span_err(
295 span, &format!("borrowed data escapes outside of {}", escapes_from),
298 if let Some((outlived_fr_name, outlived_fr_span)) = outlived_fr_name_and_span {
299 if let Some(name) = outlived_fr_name {
302 format!("`{}` is declared here, outside of the {} body", name, escapes_from),
307 if let Some((fr_name, fr_span)) = fr_name_and_span {
308 if let Some(name) = fr_name {
311 format!("`{}` is a reference that is only valid in the {} body",
315 diag.span_label(span, format!("`{}` escapes the {} body here",
316 name, escapes_from));
320 diag.buffer(errors_buffer);
323 fn report_general_error(
326 infcx: &InferCtxt<'_, '_, 'tcx>,
330 outlived_fr: RegionVid,
331 outlived_fr_is_local: bool,
332 category: ConstraintCategory,
334 errors_buffer: &mut Vec<Diagnostic>,
336 let mut diag = infcx.tcx.sess.struct_span_err(
338 "unsatisfied lifetime constraints", // FIXME
341 let counter = &mut 1;
342 let fr_name = self.give_region_a_name(infcx, mir, mir_def_id, fr, counter);
343 fr_name.highlight_region_name(&mut diag);
344 let outlived_fr_name = self.give_region_a_name(
345 infcx, mir, mir_def_id, outlived_fr, counter);
346 outlived_fr_name.highlight_region_name(&mut diag);
348 let mir_def_name = if infcx.tcx.is_closure(mir_def_id) { "closure" } else { "function" };
350 match (category, outlived_fr_is_local, fr_is_local) {
351 (ConstraintCategory::Return, true, _) => {
352 diag.span_label(span, format!(
353 "{} was supposed to return data with lifetime `{}` but it is returning \
354 data with lifetime `{}`",
355 mir_def_name, outlived_fr_name, fr_name
359 diag.span_label(span, format!(
360 "{}requires that `{}` must outlive `{}`",
361 category, fr_name, outlived_fr_name,
366 self.add_static_impl_trait_suggestion(
367 infcx, &mut diag, fr, fr_name, outlived_fr,
370 diag.buffer(errors_buffer);
373 fn add_static_impl_trait_suggestion(
375 infcx: &InferCtxt<'_, '_, 'tcx>,
376 diag: &mut DiagnosticBuilder<'_>,
378 // We need to pass `fr_name` - computing it again will label it twice.
380 outlived_fr: RegionVid,
384 Some(ty::RegionKind::ReStatic)
385 ) = (self.to_error_region(fr), self.to_error_region(outlived_fr)) {
386 if let Some(ty::TyS {
387 sty: ty::TyKind::Opaque(did, substs),
389 }) = infcx.tcx.is_suitable_region(f)
391 .map(|id| infcx.tcx.return_type_impl_trait(id))
394 // Check whether or not the impl trait return type is intended to capture
395 // data with the static lifetime.
397 // eg. check for `impl Trait + 'static` instead of `impl Trait`.
398 let has_static_predicate = {
399 let predicates_of = infcx.tcx.predicates_of(*did);
400 let bounds = predicates_of.instantiate(infcx.tcx, substs);
402 let mut found = false;
403 for predicate in bounds.predicates {
404 if let ty::Predicate::TypeOutlives(binder) = predicate {
405 if let ty::OutlivesPredicate(
407 ty::RegionKind::ReStatic
408 ) = binder.skip_binder() {
418 debug!("add_static_impl_trait_suggestion: has_static_predicate={:?}",
419 has_static_predicate);
420 let static_str = keywords::StaticLifetime.name();
421 // If there is a static predicate, then the only sensible suggestion is to replace
422 // fr with `'static`.
423 if has_static_predicate {
426 "consider replacing `{}` with `{}`",
431 // Otherwise, we should suggest adding a constraint on the return type.
432 let span = infcx.tcx.def_span(*did);
433 if let Ok(snippet) = infcx.tcx.sess.source_map().span_to_snippet(span) {
434 let suggestable_fr_name = if fr_name.was_named() {
435 format!("{}", fr_name)
440 diag.span_suggestion_with_applicability(
443 "to allow this impl Trait to capture borrowed data with lifetime \
444 `{}`, add `{}` as a constraint",
445 fr_name, suggestable_fr_name,
447 format!("{} + {}", snippet, suggestable_fr_name),
448 Applicability::MachineApplicable,
456 // Finds some region R such that `fr1: R` and `R` is live at
458 crate fn find_sub_region_live_at(&self, fr1: RegionVid, elem: Location) -> RegionVid {
461 self.find_constraint_paths_between_regions(fr1, |r| {
462 self.liveness_constraints.contains(r, elem)
467 // Finds a good span to blame for the fact that `fr1` outlives `fr2`.
468 crate fn find_outlives_blame_span(
474 let (_, span, _) = self.best_blame_constraint(mir, fr1, |r| r == fr2);