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;
12 use borrow_check::nll::region_infer::RegionInferenceContext;
13 use borrow_check::nll::type_check::Locations;
14 use rustc::hir::def_id::DefId;
15 use rustc::infer::error_reporting::nice_region_error::NiceRegionError;
16 use rustc::infer::InferCtxt;
17 use rustc::mir::{self, Location, Mir, Place, Rvalue, StatementKind, TerminatorKind};
18 use rustc::ty::{TyCtxt, RegionVid};
19 use rustc_data_structures::indexed_vec::IndexVec;
20 use rustc_errors::Diagnostic;
21 use std::collections::VecDeque;
28 /// Constraints that are considered interesting can be categorized to
29 /// determine why they are interesting. Order of variants indicates
30 /// sort order of the category, thereby influencing diagnostic output.
31 #[derive(Copy, Clone, Debug, Eq, PartialEq, PartialOrd, Ord)]
32 enum ConstraintCategory {
41 impl fmt::Display for ConstraintCategory {
42 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
43 // Must end with a space. Allows for empty names to be provided.
45 ConstraintCategory::Assignment => write!(f, "assignment "),
46 ConstraintCategory::Return => write!(f, "returning this value "),
47 ConstraintCategory::Cast => write!(f, "cast "),
48 ConstraintCategory::CallArgument => write!(f, "argument "),
54 #[derive(Copy, Clone, PartialEq, Eq)]
57 FromOutlivesConstraint(OutlivesConstraint),
61 impl<'tcx> RegionInferenceContext<'tcx> {
62 /// Tries to find the best constraint to blame for the fact that
63 /// `R: from_region`, where `R` is some region that meets
64 /// `target_test`. This works by following the constraint graph,
65 /// creating a constraint path that forces `R` to outlive
66 /// `from_region`, and then finding the best choices within that
68 fn best_blame_constraint(
71 tcx: TyCtxt<'_, '_, 'tcx>,
72 from_region: RegionVid,
73 target_test: impl Fn(RegionVid) -> bool,
74 ) -> (ConstraintCategory, Span, RegionVid) {
75 debug!("best_blame_constraint(from_region={:?})", from_region);
78 let (path, target_region) = self
79 .find_constraint_paths_between_regions(from_region, target_test)
82 "best_blame_constraint: path={:#?}",
87 self.constraint_sccs.scc(c.sup),
88 self.constraint_sccs.scc(c.sub),
93 // Classify each of the constraints along the path.
94 let mut categorized_path: Vec<(ConstraintCategory, Span)> = path
96 .map(|&index| self.classify_constraint(index, mir, tcx))
99 "best_blame_constraint: categorized_path={:#?}",
103 // To find the best span to cite, we first try to look for the
104 // final constraint that is interesting and where the `sup` is
105 // not unified with the ultimate target region. The reason
106 // for this is that we have a chain of constraints that lead
107 // from the source to the target region, something like:
109 // '0: '1 ('0 is the source)
114 // '5: '6 ('6 is the target)
116 // Some of those regions are unified with `'6` (in the same
117 // SCC). We want to screen those out. After that point, the
118 // "closest" constraint we have to the end is going to be the
119 // most likely to be the point where the value escapes -- but
120 // we still want to screen for an "interesting" point to
121 // highlight (e.g., a call site or something).
122 let target_scc = self.constraint_sccs.scc(target_region);
123 let best_choice = (0..path.len()).rev().find(|&i| {
124 let constraint = path[i];
126 let constraint_sup_scc = self.constraint_sccs.scc(constraint.sup);
128 match categorized_path[i].0 {
129 ConstraintCategory::Boring => false,
130 ConstraintCategory::Other => {
131 // other isn't interesting when the two lifetimes
133 constraint_sup_scc != self.constraint_sccs.scc(constraint.sub)
135 _ => constraint_sup_scc != target_scc,
138 if let Some(i) = best_choice {
139 let (category, span) = categorized_path[i];
140 return (category, span, target_region);
143 // If that search fails, that is.. unusual. Maybe everything
144 // is in the same SCC or something. In that case, find what
145 // appears to be the most interesting point to report to the
146 // user via an even more ad-hoc guess.
147 categorized_path.sort_by(|p0, p1| p0.0.cmp(&p1.0));
148 debug!("best_blame_constraint: sorted_path={:#?}", categorized_path);
150 let &(category, span) = categorized_path.first().unwrap();
152 (category, span, target_region)
155 /// Walks the graph of constraints (where `'a: 'b` is considered
156 /// an edge `'a -> 'b`) to find all paths from `from_region` to
157 /// `to_region`. The paths are accumulated into the vector
158 /// `results`. The paths are stored as a series of
159 /// `ConstraintIndex` values -- in other words, a list of *edges*.
161 /// Returns: a series of constraints as well as the region `R`
162 /// that passed the target test.
163 fn find_constraint_paths_between_regions(
165 from_region: RegionVid,
166 target_test: impl Fn(RegionVid) -> bool,
167 ) -> Option<(Vec<OutlivesConstraint>, RegionVid)> {
168 let mut context = IndexVec::from_elem(Trace::NotVisited, &self.definitions);
169 context[from_region] = Trace::StartRegion;
171 // Use a deque so that we do a breadth-first search. We will
172 // stop at the first match, which ought to be the shortest
173 // path (fewest constraints).
174 let mut deque = VecDeque::new();
175 deque.push_back(from_region);
177 while let Some(r) = deque.pop_front() {
178 // Check if we reached the region we were looking for. If so,
179 // we can reconstruct the path that led to it and return it.
181 let mut result = vec![];
185 Trace::NotVisited => {
186 bug!("found unvisited region {:?} on path to {:?}", p, r)
188 Trace::FromOutlivesConstraint(c) => {
193 Trace::StartRegion => {
195 return Some((result, r));
201 // Otherwise, walk over the outgoing constraints and
202 // enqueue any regions we find, keeping track of how we
204 let fr_static = self.universal_regions.fr_static;
205 for constraint in self.constraint_graph.outgoing_edges(r,
208 assert_eq!(constraint.sup, r);
209 let sub_region = constraint.sub;
210 if let Trace::NotVisited = context[sub_region] {
211 context[sub_region] = Trace::FromOutlivesConstraint(constraint);
212 deque.push_back(sub_region);
220 /// This function will return true if a constraint is interesting and false if a constraint
221 /// is not. It is useful in filtering constraint paths to only interesting points.
222 fn constraint_is_interesting(&self, constraint: OutlivesConstraint) -> bool {
224 "constraint_is_interesting: locations={:?} constraint={:?}",
225 constraint.locations, constraint
228 match constraint.locations {
229 Locations::Interesting(_) | Locations::All => true,
234 /// This function classifies a constraint from a location.
235 fn classify_constraint(
237 constraint: OutlivesConstraint,
239 tcx: TyCtxt<'_, '_, 'tcx>,
240 ) -> (ConstraintCategory, Span) {
241 debug!("classify_constraint: constraint={:?}", constraint);
242 let span = constraint.locations.span(mir);
243 let location = constraint
246 .unwrap_or(Location::START);
248 if !self.constraint_is_interesting(constraint) {
249 return (ConstraintCategory::Boring, span);
252 let data = &mir[location.block];
254 "classify_constraint: location={:?} data={:?}",
257 let category = if location.statement_index == data.statements.len() {
258 if let Some(ref terminator) = data.terminator {
259 debug!("classify_constraint: terminator.kind={:?}", terminator.kind);
260 match terminator.kind {
261 TerminatorKind::DropAndReplace { .. } => ConstraintCategory::Assignment,
262 // Classify calls differently depending on whether or not
263 // the sub region appears in the destination type (so the
264 // sup region is in the return type). If the return type
265 // contains the sub-region, then this is either an
266 // assignment or a return, depending on whether we are
267 // writing to the RETURN_PLACE or not.
269 // The idea here is that the region is being propagated
270 // from an input into the output place, so it's a kind of
271 // assignment. Otherwise, if the sub-region only appears in
272 // the argument types, then use the CallArgument
274 TerminatorKind::Call { destination: Some((ref place, _)), .. } => {
275 if tcx.any_free_region_meets(
276 &place.ty(mir, tcx).to_ty(tcx),
277 |region| self.to_region_vid(region) == constraint.sub,
280 Place::Local(mir::RETURN_PLACE) => ConstraintCategory::Return,
281 _ => ConstraintCategory::Assignment,
284 ConstraintCategory::CallArgument
287 TerminatorKind::Call { destination: None, .. } => {
288 ConstraintCategory::CallArgument
290 _ => ConstraintCategory::Other,
293 ConstraintCategory::Other
296 let statement = &data.statements[location.statement_index];
297 debug!("classify_constraint: statement.kind={:?}", statement.kind);
298 match statement.kind {
299 StatementKind::Assign(ref place, ref rvalue) => {
300 debug!("classify_constraint: place={:?} rvalue={:?}", place, rvalue);
301 if *place == Place::Local(mir::RETURN_PLACE) {
302 ConstraintCategory::Return
305 Rvalue::Cast(..) => ConstraintCategory::Cast,
306 Rvalue::Use(..) | Rvalue::Aggregate(..) => {
307 ConstraintCategory::Assignment
309 _ => ConstraintCategory::Other,
313 _ => ConstraintCategory::Other,
320 /// Report an error because the universal region `fr` was required to outlive
321 /// `outlived_fr` but it is not known to do so. For example:
324 /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x }
327 /// Here we would be invoked with `fr = 'a` and `outlived_fr = `'b`.
328 pub(super) fn report_error(
331 infcx: &InferCtxt<'_, '_, 'tcx>,
334 outlived_fr: RegionVid,
335 errors_buffer: &mut Vec<Diagnostic>,
337 debug!("report_error(fr={:?}, outlived_fr={:?})", fr, outlived_fr);
339 let (category, span, _) = self.best_blame_constraint(
346 // Check if we can use one of the "nice region errors".
347 if let (Some(f), Some(o)) = (self.to_error_region(fr), self.to_error_region(outlived_fr)) {
348 let tables = infcx.tcx.typeck_tables_of(mir_def_id);
349 let nice = NiceRegionError::new_from_span(infcx.tcx, span, o, f, Some(tables));
350 if let Some(_error_reported) = nice.try_report_from_nll() {
355 let (fr_is_local, outlived_fr_is_local): (bool, bool) = (
356 self.universal_regions.is_local_free_region(fr),
357 self.universal_regions.is_local_free_region(outlived_fr),
359 debug!("report_error: fr_is_local={:?} outlived_fr_is_local={:?} category={:?}",
360 fr_is_local, outlived_fr_is_local, category);
362 match (category, fr_is_local, outlived_fr_is_local) {
363 (ConstraintCategory::Assignment, true, false) |
364 (ConstraintCategory::CallArgument, true, false) =>
365 self.report_escaping_data_error(mir, infcx, mir_def_id, fr, outlived_fr,
366 category, span, errors_buffer),
368 self.report_general_error(mir, infcx, mir_def_id, fr, fr_is_local,
369 outlived_fr, outlived_fr_is_local,
370 category, span, errors_buffer),
374 fn report_escaping_data_error(
377 infcx: &InferCtxt<'_, '_, 'tcx>,
380 outlived_fr: RegionVid,
381 category: ConstraintCategory,
383 errors_buffer: &mut Vec<Diagnostic>,
385 let fr_name_and_span = self.get_var_name_and_span_for_region(infcx.tcx, mir, fr);
386 let outlived_fr_name_and_span =
387 self.get_var_name_and_span_for_region(infcx.tcx, mir, outlived_fr);
389 let escapes_from = if infcx.tcx.is_closure(mir_def_id) { "closure" } else { "function" };
391 if fr_name_and_span.is_none() && outlived_fr_name_and_span.is_none() {
392 return self.report_general_error(mir, infcx, mir_def_id,
393 fr, true, outlived_fr, false,
394 category, span, errors_buffer);
397 let mut diag = infcx.tcx.sess.struct_span_err(
398 span, &format!("borrowed data escapes outside of {}", escapes_from),
401 if let Some((outlived_fr_name, outlived_fr_span)) = outlived_fr_name_and_span {
402 if let Some(name) = outlived_fr_name {
405 format!("`{}` is declared here, outside of the {} body", name, escapes_from),
410 if let Some((fr_name, fr_span)) = fr_name_and_span {
411 if let Some(name) = fr_name {
414 format!("`{}` is a reference that is only valid in the {} body",
418 diag.span_label(span, format!("`{}` escapes the {} body here",
419 name, escapes_from));
423 diag.buffer(errors_buffer);
426 fn report_general_error(
429 infcx: &InferCtxt<'_, '_, 'tcx>,
433 outlived_fr: RegionVid,
434 outlived_fr_is_local: bool,
435 category: ConstraintCategory,
437 errors_buffer: &mut Vec<Diagnostic>,
439 let mut diag = infcx.tcx.sess.struct_span_err(
441 "unsatisfied lifetime constraints", // FIXME
444 let counter = &mut 1;
445 let fr_name = self.give_region_a_name(
446 infcx, mir, mir_def_id, fr, counter, &mut diag);
447 let outlived_fr_name = self.give_region_a_name(
448 infcx, mir, mir_def_id, outlived_fr, counter, &mut diag);
450 let mir_def_name = if infcx.tcx.is_closure(mir_def_id) { "closure" } else { "function" };
452 match (category, outlived_fr_is_local, fr_is_local) {
453 (ConstraintCategory::Return, true, _) => {
454 diag.span_label(span, format!(
455 "{} was supposed to return data with lifetime `{}` but it is returning \
456 data with lifetime `{}`",
457 mir_def_name, outlived_fr_name, fr_name
461 diag.span_label(span, format!(
462 "{}requires that `{}` must outlive `{}`",
463 category, fr_name, outlived_fr_name,
468 diag.buffer(errors_buffer);
471 // Finds some region R such that `fr1: R` and `R` is live at
473 crate fn find_sub_region_live_at(&self, fr1: RegionVid, elem: Location) -> RegionVid {
476 self.find_constraint_paths_between_regions(fr1, |r| {
477 self.liveness_constraints.contains(r, elem)
482 // Finds a good span to blame for the fact that `fr1` outlives `fr2`.
483 crate fn find_outlives_blame_span(
486 tcx: TyCtxt<'_, '_, 'tcx>,
490 let (_, span, _) = self.best_blame_constraint(mir, tcx, fr1, |r| r == fr2);