| // Copyright 2017 The Rust Project Developers. See the COPYRIGHT |
| // file at the top-level directory of this distribution and at |
| // http://rust-lang.org/COPYRIGHT. |
| // |
| // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or |
| // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license |
| // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your |
| // option. This file may not be copied, modified, or distributed |
| // except according to those terms. |
| |
| use borrow_check::nll::region_infer::{ConstraintIndex, RegionInferenceContext}; |
| use borrow_check::nll::type_check::Locations; |
| use rustc::hir::def_id::DefId; |
| use rustc::infer::error_reporting::nice_region_error::NiceRegionError; |
| use rustc::infer::InferCtxt; |
| use rustc::mir::{self, Location, Mir, Place, Rvalue, StatementKind, TerminatorKind}; |
| use rustc::ty::RegionVid; |
| use rustc_data_structures::indexed_vec::IndexVec; |
| use rustc_errors::Diagnostic; |
| use std::collections::VecDeque; |
| use std::fmt; |
| use syntax_pos::Span; |
| |
| mod region_name; |
| mod var_name; |
| |
| /// Constraints that are considered interesting can be categorized to |
| /// determine why they are interesting. Order of variants indicates |
| /// sort order of the category, thereby influencing diagnostic output. |
| #[derive(Copy, Clone, Debug, Eq, PartialEq, PartialOrd, Ord)] |
| enum ConstraintCategory { |
| Cast, |
| Assignment, |
| Return, |
| CallArgument, |
| Other, |
| Boring, |
| } |
| |
| impl fmt::Display for ConstraintCategory { |
| fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
| // Must end with a space. Allows for empty names to be provided. |
| match self { |
| ConstraintCategory::Assignment => write!(f, "assignment "), |
| ConstraintCategory::Return => write!(f, "return "), |
| ConstraintCategory::Cast => write!(f, "cast "), |
| ConstraintCategory::CallArgument => write!(f, "argument "), |
| _ => write!(f, ""), |
| } |
| } |
| } |
| |
| #[derive(Copy, Clone, PartialEq, Eq)] |
| enum Trace { |
| StartRegion, |
| FromConstraint(ConstraintIndex), |
| NotVisited, |
| } |
| |
| impl<'tcx> RegionInferenceContext<'tcx> { |
| /// Tries to find the best constraint to blame for the fact that |
| /// `R: from_region`, where `R` is some region that meets |
| /// `target_test`. This works by following the constraint graph, |
| /// creating a constraint path that forces `R` to outlive |
| /// `from_region`, and then finding the best choices within that |
| /// path to blame. |
| fn best_blame_constraint( |
| &self, |
| mir: &Mir<'tcx>, |
| from_region: RegionVid, |
| target_test: impl Fn(RegionVid) -> bool, |
| ) -> (ConstraintCategory, Span, RegionVid) { |
| debug!("best_blame_constraint(from_region={:?})", from_region); |
| |
| // Find all paths |
| let (path, target_region) = self |
| .find_constraint_paths_between_regions(from_region, target_test) |
| .unwrap(); |
| debug!( |
| "best_blame_constraint: path={:#?}", |
| path.iter() |
| .map(|&ci| format!( |
| "{:?}: {:?} ({:?}: {:?})", |
| ci, |
| &self.constraints[ci], |
| self.constraint_sccs.scc(self.constraints[ci].sup), |
| self.constraint_sccs.scc(self.constraints[ci].sub), |
| )) |
| .collect::<Vec<_>>() |
| ); |
| |
| // Classify each of the constraints along the path. |
| let mut categorized_path: Vec<(ConstraintCategory, Span)> = path |
| .iter() |
| .map(|&index| self.classify_constraint(index, mir)) |
| .collect(); |
| debug!( |
| "best_blame_constraint: categorized_path={:#?}", |
| categorized_path |
| ); |
| |
| // To find the best span to cite, we first try to look for the |
| // final constraint that is interesting and where the `sup` is |
| // not unified with the ultimate target region. The reason |
| // for this is that we have a chain of constraints that lead |
| // from the source to the target region, something like: |
| // |
| // '0: '1 ('0 is the source) |
| // '1: '2 |
| // '2: '3 |
| // '3: '4 |
| // '4: '5 |
| // '5: '6 ('6 is the target) |
| // |
| // Some of those regions are unified with `'6` (in the same |
| // SCC). We want to screen those out. After that point, the |
| // "closest" constraint we have to the end is going to be the |
| // most likely to be the point where the value escapes -- but |
| // we still want to screen for an "interesting" point to |
| // highlight (e.g., a call site or something). |
| let target_scc = self.constraint_sccs.scc(target_region); |
| let best_choice = (0..path.len()).rev().find(|&i| { |
| let constraint = &self.constraints[path[i]]; |
| |
| let constraint_sup_scc = self.constraint_sccs.scc(constraint.sup); |
| if constraint_sup_scc == target_scc { |
| return false; |
| } |
| |
| match categorized_path[i].0 { |
| ConstraintCategory::Boring => false, |
| _ => true, |
| } |
| }); |
| if let Some(i) = best_choice { |
| let (category, span) = categorized_path[i]; |
| return (category, span, target_region); |
| } |
| |
| // If that search fails, that is.. unusual. Maybe everything |
| // is in the same SCC or something. In that case, find what |
| // appears to be the most interesting point to report to the |
| // user via an even more ad-hoc guess. |
| categorized_path.sort_by(|p0, p1| p0.0.cmp(&p1.0)); |
| debug!("best_blame_constraint: sorted_path={:#?}", categorized_path); |
| |
| let &(category, span) = categorized_path.first().unwrap(); |
| |
| (category, span, target_region) |
| } |
| |
| /// Walks the graph of constraints (where `'a: 'b` is considered |
| /// an edge `'a -> 'b`) to find all paths from `from_region` to |
| /// `to_region`. The paths are accumulated into the vector |
| /// `results`. The paths are stored as a series of |
| /// `ConstraintIndex` values -- in other words, a list of *edges*. |
| /// |
| /// Returns: a series of constraints as well as the region `R` |
| /// that passed the target test. |
| fn find_constraint_paths_between_regions( |
| &self, |
| from_region: RegionVid, |
| target_test: impl Fn(RegionVid) -> bool, |
| ) -> Option<(Vec<ConstraintIndex>, RegionVid)> { |
| let mut context = IndexVec::from_elem(Trace::NotVisited, &self.definitions); |
| context[from_region] = Trace::StartRegion; |
| |
| // Use a deque so that we do a breadth-first search. We will |
| // stop at the first match, which ought to be the shortest |
| // path (fewest constraints). |
| let mut deque = VecDeque::new(); |
| deque.push_back(from_region); |
| |
| while let Some(r) = deque.pop_front() { |
| // Check if we reached the region we were looking for. If so, |
| // we can reconstruct the path that led to it and return it. |
| if target_test(r) { |
| let mut result = vec![]; |
| let mut p = r; |
| loop { |
| match context[p] { |
| Trace::NotVisited => { |
| bug!("found unvisited region {:?} on path to {:?}", p, r) |
| } |
| Trace::FromConstraint(c) => { |
| result.push(c); |
| p = self.constraints[c].sup; |
| } |
| |
| Trace::StartRegion => { |
| result.reverse(); |
| return Some((result, r)); |
| } |
| } |
| } |
| } |
| |
| // Otherwise, walk over the outgoing constraints and |
| // enqueue any regions we find, keeping track of how we |
| // reached them. |
| for constraint in self.constraint_graph.outgoing_edges(r) { |
| assert_eq!(self.constraints[constraint].sup, r); |
| let sub_region = self.constraints[constraint].sub; |
| if let Trace::NotVisited = context[sub_region] { |
| context[sub_region] = Trace::FromConstraint(constraint); |
| deque.push_back(sub_region); |
| } |
| } |
| } |
| |
| None |
| } |
| |
| /// This function will return true if a constraint is interesting and false if a constraint |
| /// is not. It is useful in filtering constraint paths to only interesting points. |
| fn constraint_is_interesting(&self, index: ConstraintIndex) -> bool { |
| let constraint = self.constraints[index]; |
| debug!( |
| "constraint_is_interesting: locations={:?} constraint={:?}", |
| constraint.locations, constraint |
| ); |
| |
| match constraint.locations { |
| Locations::Interesting(_) | Locations::All => true, |
| _ => false, |
| } |
| } |
| |
| /// This function classifies a constraint from a location. |
| fn classify_constraint( |
| &self, |
| index: ConstraintIndex, |
| mir: &Mir<'tcx>, |
| ) -> (ConstraintCategory, Span) { |
| let constraint = self.constraints[index]; |
| debug!("classify_constraint: constraint={:?}", constraint); |
| let span = constraint.locations.span(mir); |
| let location = constraint |
| .locations |
| .from_location() |
| .unwrap_or(Location::START); |
| |
| if !self.constraint_is_interesting(index) { |
| return (ConstraintCategory::Boring, span); |
| } |
| |
| let data = &mir[location.block]; |
| debug!( |
| "classify_constraint: location={:?} data={:?}", |
| location, data |
| ); |
| let category = if location.statement_index == data.statements.len() { |
| if let Some(ref terminator) = data.terminator { |
| debug!("classify_constraint: terminator.kind={:?}", terminator.kind); |
| match terminator.kind { |
| TerminatorKind::DropAndReplace { .. } => ConstraintCategory::Assignment, |
| TerminatorKind::Call { .. } => ConstraintCategory::CallArgument, |
| _ => ConstraintCategory::Other, |
| } |
| } else { |
| ConstraintCategory::Other |
| } |
| } else { |
| let statement = &data.statements[location.statement_index]; |
| debug!("classify_constraint: statement.kind={:?}", statement.kind); |
| match statement.kind { |
| StatementKind::Assign(ref place, ref rvalue) => { |
| debug!("classify_constraint: place={:?} rvalue={:?}", place, rvalue); |
| if *place == Place::Local(mir::RETURN_PLACE) { |
| ConstraintCategory::Return |
| } else { |
| match rvalue { |
| Rvalue::Cast(..) => ConstraintCategory::Cast, |
| Rvalue::Use(..) | Rvalue::Aggregate(..) => { |
| ConstraintCategory::Assignment |
| } |
| _ => ConstraintCategory::Other, |
| } |
| } |
| } |
| _ => ConstraintCategory::Other, |
| } |
| }; |
| |
| (category, span) |
| } |
| |
| /// Report an error because the universal region `fr` was required to outlive |
| /// `outlived_fr` but it is not known to do so. For example: |
| /// |
| /// ``` |
| /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x } |
| /// ``` |
| /// |
| /// Here we would be invoked with `fr = 'a` and `outlived_fr = `'b`. |
| pub(super) fn report_error( |
| &self, |
| mir: &Mir<'tcx>, |
| infcx: &InferCtxt<'_, '_, 'tcx>, |
| mir_def_id: DefId, |
| fr: RegionVid, |
| outlived_fr: RegionVid, |
| errors_buffer: &mut Vec<Diagnostic>, |
| ) { |
| debug!("report_error(fr={:?}, outlived_fr={:?})", fr, outlived_fr); |
| |
| let (category, span, _) = self.best_blame_constraint(mir, fr, |r| r == outlived_fr); |
| |
| // Check if we can use one of the "nice region errors". |
| if let (Some(f), Some(o)) = (self.to_error_region(fr), self.to_error_region(outlived_fr)) { |
| let tables = infcx.tcx.typeck_tables_of(mir_def_id); |
| let nice = NiceRegionError::new_from_span(infcx.tcx, span, o, f, Some(tables)); |
| if let Some(_error_reported) = nice.try_report_from_nll() { |
| return; |
| } |
| } |
| |
| let (fr_is_local, outlived_fr_is_local): (bool, bool) = ( |
| self.universal_regions.is_local_free_region(fr), |
| self.universal_regions.is_local_free_region(outlived_fr), |
| ); |
| debug!("report_error: fr_is_local={:?} outlived_fr_is_local={:?} category={:?}", |
| fr_is_local, outlived_fr_is_local, category); |
| |
| match (category, fr_is_local, outlived_fr_is_local) { |
| (ConstraintCategory::Assignment, true, false) | |
| (ConstraintCategory::CallArgument, true, false) => |
| self.report_escaping_data_error(mir, infcx, mir_def_id, fr, outlived_fr, |
| category, span, errors_buffer), |
| _ => |
| self.report_general_error(mir, infcx, mir_def_id, fr, fr_is_local, |
| outlived_fr, outlived_fr_is_local, |
| category, span, errors_buffer), |
| }; |
| } |
| |
| fn report_escaping_data_error( |
| &self, |
| mir: &Mir<'tcx>, |
| infcx: &InferCtxt<'_, '_, 'tcx>, |
| mir_def_id: DefId, |
| fr: RegionVid, |
| outlived_fr: RegionVid, |
| category: ConstraintCategory, |
| span: Span, |
| errors_buffer: &mut Vec<Diagnostic>, |
| ) { |
| let fr_name_and_span = self.get_var_name_and_span_for_region(infcx.tcx, mir, fr); |
| let outlived_fr_name_and_span = |
| self.get_var_name_and_span_for_region(infcx.tcx, mir, outlived_fr); |
| |
| let escapes_from = if infcx.tcx.is_closure(mir_def_id) { "closure" } else { "function" }; |
| |
| if fr_name_and_span.is_none() && outlived_fr_name_and_span.is_none() { |
| return self.report_general_error(mir, infcx, mir_def_id, |
| fr, true, outlived_fr, false, |
| category, span, errors_buffer); |
| } |
| |
| let mut diag = infcx.tcx.sess.struct_span_err( |
| span, &format!("borrowed data escapes outside of {}", escapes_from), |
| ); |
| |
| if let Some((outlived_fr_name, outlived_fr_span)) = outlived_fr_name_and_span { |
| if let Some(name) = outlived_fr_name { |
| diag.span_label( |
| outlived_fr_span, |
| format!("`{}` is declared here, outside of the {} body", name, escapes_from), |
| ); |
| } |
| } |
| |
| if let Some((fr_name, fr_span)) = fr_name_and_span { |
| if let Some(name) = fr_name { |
| diag.span_label( |
| fr_span, |
| format!("`{}` is a reference that is only valid in the {} body", |
| name, escapes_from), |
| ); |
| |
| diag.span_label(span, format!("`{}` escapes the {} body here", |
| name, escapes_from)); |
| } |
| } |
| |
| diag.buffer(errors_buffer); |
| } |
| |
| fn report_general_error( |
| &self, |
| mir: &Mir<'tcx>, |
| infcx: &InferCtxt<'_, '_, 'tcx>, |
| mir_def_id: DefId, |
| fr: RegionVid, |
| fr_is_local: bool, |
| outlived_fr: RegionVid, |
| outlived_fr_is_local: bool, |
| category: ConstraintCategory, |
| span: Span, |
| errors_buffer: &mut Vec<Diagnostic>, |
| ) { |
| let mut diag = infcx.tcx.sess.struct_span_err( |
| span, |
| "unsatisfied lifetime constraints", // FIXME |
| ); |
| |
| let counter = &mut 1; |
| let fr_name = self.give_region_a_name( |
| infcx, mir, mir_def_id, fr, counter, &mut diag); |
| let outlived_fr_name = self.give_region_a_name( |
| infcx, mir, mir_def_id, outlived_fr, counter, &mut diag); |
| |
| let mir_def_name = if infcx.tcx.is_closure(mir_def_id) { "closure" } else { "function" }; |
| |
| match (category, outlived_fr_is_local, fr_is_local) { |
| (ConstraintCategory::Return, true, _) => { |
| diag.span_label(span, format!( |
| "{} was supposed to return data with lifetime `{}` but it is returning \ |
| data with lifetime `{}`", |
| mir_def_name, fr_name, outlived_fr_name, |
| )); |
| }, |
| _ => { |
| diag.span_label(span, format!( |
| "{}requires that `{}` must outlive `{}`", |
| category, fr_name, outlived_fr_name, |
| )); |
| }, |
| } |
| |
| diag.buffer(errors_buffer); |
| } |
| |
| // Finds some region R such that `fr1: R` and `R` is live at |
| // `elem`. |
| crate fn find_sub_region_live_at(&self, fr1: RegionVid, elem: Location) -> RegionVid { |
| // Find all paths |
| let (_path, r) = |
| self.find_constraint_paths_between_regions(fr1, |r| { |
| self.liveness_constraints.contains(r, elem) |
| }).unwrap(); |
| r |
| } |
| |
| // Finds a good span to blame for the fact that `fr1` outlives `fr2`. |
| crate fn find_outlives_blame_span( |
| &self, |
| mir: &Mir<'tcx>, |
| fr1: RegionVid, |
| fr2: RegionVid, |
| ) -> Span { |
| let (_, span, _) = self.best_blame_constraint(mir, fr1, |r| r == fr2); |
| span |
| } |
| } |