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.
12 use borrow_check::nll::region_infer::{ConstraintIndex, RegionInferenceContext};
13 use borrow_check::nll::region_infer::values::ToElementIndex;
14 use borrow_check::nll::type_check::Locations;
15 use rustc::hir::def_id::DefId;
16 use rustc::infer::InferCtxt;
17 use rustc::infer::error_reporting::nice_region_error::NiceRegionError;
18 use rustc::mir::{self, Location, Mir, Place, StatementKind, TerminatorKind, Rvalue};
19 use rustc::ty::RegionVid;
20 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
21 use rustc_data_structures::indexed_vec::IndexVec;
24 /// Constraints that are considered interesting can be categorized to
25 /// determine why they are interesting. Order of variants indicates
26 /// sort order of the category, thereby influencing diagnostic output.
27 #[derive(Debug, Eq, PartialEq, PartialOrd, Ord)]
28 enum ConstraintCategory {
37 impl fmt::Display for ConstraintCategory {
38 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
40 ConstraintCategory::Assignment => write!(f, "assignment"),
41 ConstraintCategory::Return => write!(f, "return"),
42 ConstraintCategory::Cast => write!(f, "cast"),
43 ConstraintCategory::CallArgument => write!(f, "argument"),
44 _ => write!(f, "free region"),
49 impl<'tcx> RegionInferenceContext<'tcx> {
50 /// When reporting an error, it is useful to be able to determine which constraints influenced
51 /// the region being reported as an error. This function finds all of the paths from the
53 fn find_constraint_paths_from_region(
56 ) -> Vec<Vec<ConstraintIndex>> {
57 let constraints = self.constraints.clone();
59 // Mapping of regions to the previous region and constraint index that led to it.
60 let mut previous = FxHashMap();
61 // Regions yet to be visited.
62 let mut next = vec! [ r0 ];
63 // Regions that have been visited.
64 let mut visited = FxHashSet();
66 let mut end_regions = FxHashSet();
68 // When we've still got points to visit...
69 while let Some(current) = next.pop() {
70 // ...take the next point...
71 debug!("find_constraint_paths_from_region: current={:?} visited={:?} next={:?}",
72 current, visited, next);
73 // ...but make sure not to visit this point again...
74 visited.insert(current);
76 // ...find the edges containing it...
77 let mut upcoming = Vec::new();
78 for (index, constraint) in constraints.iter_enumerated() {
79 if constraint.sub == current {
80 // ...add the regions that join us with to the path we've taken...
81 debug!("find_constraint_paths_from_region: index={:?} constraint={:?}",
83 let next_region = constraint.sup.clone();
85 // ...unless we've visited it since this was added...
86 if visited.contains(&next_region) {
87 debug!("find_constraint_paths_from_region: skipping as visited");
91 previous.insert(next_region, (index, Some(current)));
92 upcoming.push(next_region);
96 if upcoming.is_empty() {
97 // If we didn't find any edges then this is the end of a path...
98 debug!("find_constraint_paths_from_region: new end region current={:?}", current);
99 end_regions.insert(current);
101 // ...but, if we did find edges, then add these to the regions yet to visit.
102 debug!("find_constraint_paths_from_region: extend next upcoming={:?}", upcoming);
103 next.extend(upcoming);
108 // Now we've visited each point, compute the final paths.
109 let mut paths: Vec<Vec<ConstraintIndex>> = Vec::new();
110 debug!("find_constraint_paths_from_region: end_regions={:?}", end_regions);
111 for end_region in end_regions {
112 debug!("find_constraint_paths_from_region: end_region={:?}", end_region);
114 // Get the constraint and region that led to this end point.
115 // We can unwrap as we know if end_point was in the vector that it
116 // must also be in our previous map.
117 let (mut index, mut region) = previous.get(&end_region).unwrap();
118 debug!("find_constraint_paths_from_region: index={:?} region={:?}", index, region);
120 // Keep track of the indices.
121 let mut path: Vec<ConstraintIndex> = vec![index];
123 while region.is_some() && region != Some(r0) {
124 let p = previous.get(®ion.unwrap()).unwrap();
128 debug!("find_constraint_paths_from_region: index={:?} region={:?}", index, region);
136 debug!("find_constraint_paths_from_region: paths={:?}", paths);
140 /// This function will return true if a constraint is interesting and false if a constraint
141 /// is not. It is useful in filtering constraint paths to only interesting points.
142 fn constraint_is_interesting(&self, index: &ConstraintIndex) -> bool {
143 self.constraints.get(*index).filter(|constraint| {
144 debug!("constraint_is_interesting: locations={:?} constraint={:?}",
145 constraint.locations, constraint);
146 if let Locations::Interesting(_) = constraint.locations { true } else { false }
150 /// This function classifies a constraint from a location.
151 fn classify_constraint(&self, index: &ConstraintIndex,
152 mir: &Mir<'tcx>) -> Option<(ConstraintCategory, Span)> {
153 let constraint = self.constraints.get(*index)?;
154 let span = constraint.locations.span(mir);
155 let location = constraint.locations.from_location()?;
157 if !self.constraint_is_interesting(index) {
158 return Some((ConstraintCategory::Boring, span));
161 let data = &mir[location.block];
162 let category = if location.statement_index == data.statements.len() {
163 if let Some(ref terminator) = data.terminator {
164 match terminator.kind {
165 TerminatorKind::DropAndReplace { .. } => ConstraintCategory::Assignment,
166 TerminatorKind::Call { .. } => ConstraintCategory::CallArgument,
167 _ => ConstraintCategory::Other,
170 ConstraintCategory::Other
173 let statement = &data.statements[location.statement_index];
174 match statement.kind {
175 StatementKind::Assign(ref place, ref rvalue) => {
176 if *place == Place::Local(mir::RETURN_PLACE) {
177 ConstraintCategory::Return
180 Rvalue::Cast(..) => ConstraintCategory::Cast,
181 Rvalue::Use(..) => ConstraintCategory::Assignment,
182 _ => ConstraintCategory::Other,
186 _ => ConstraintCategory::Other,
190 Some((category, span))
193 /// Report an error because the universal region `fr` was required to outlive
194 /// `outlived_fr` but it is not known to do so. For example:
197 /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x }
200 /// Here we would be invoked with `fr = 'a` and `outlived_fr = `'b`.
201 pub(super) fn report_error(
204 infcx: &InferCtxt<'_, '_, 'tcx>,
207 outlived_fr: RegionVid,
210 // Obviously uncool error reporting.
212 let fr_name = self.to_error_region(fr);
213 let outlived_fr_name = self.to_error_region(outlived_fr);
215 if let (Some(f), Some(o)) = (fr_name, outlived_fr_name) {
216 let tables = infcx.tcx.typeck_tables_of(mir_def_id);
217 let nice = NiceRegionError::new_from_span(infcx.tcx, blame_span, o, f, Some(tables));
218 if let Some(_error_reported) = nice.try_report() {
223 let fr_string = match fr_name {
224 Some(r) => format!("free region `{}`", r),
225 None => format!("free region `{:?}`", fr),
228 let outlived_fr_string = match outlived_fr_name {
229 Some(r) => format!("free region `{}`", r),
230 None => format!("free region `{:?}`", outlived_fr),
233 let constraints = self.find_constraint_paths_from_region(fr.clone());
234 let path = constraints.iter().min_by_key(|p| p.len()).unwrap();
235 debug!("report_error: shortest_path={:?}", path);
237 let mut categorized_path = path.iter().filter_map(|index| {
238 self.classify_constraint(index, mir)
239 }).collect::<Vec<(ConstraintCategory, Span)>>();
240 debug!("report_error: categorized_path={:?}", categorized_path);
242 categorized_path.sort_by(|p0, p1| p0.0.cmp(&p1.0));
243 debug!("report_error: sorted_path={:?}", categorized_path);
245 if let Some((category, span)) = &categorized_path.first() {
246 let mut diag = infcx.tcx.sess.struct_span_err(
247 *span, &format!("{} requires that data must outlive {}",
248 category, outlived_fr_string),
253 let mut diag = infcx.tcx.sess.struct_span_err(
255 &format!("{} does not outlive {}", fr_string, outlived_fr_string,),
262 // Find some constraint `X: Y` where:
263 // - `fr1: X` transitively
264 // - and `Y` is live at `elem`
265 crate fn find_constraint(&self, fr1: RegionVid, elem: Location) -> RegionVid {
266 let index = self.blame_constraint(fr1, elem);
267 self.constraints[index].sub
270 /// Tries to finds a good span to blame for the fact that `fr1`
272 pub(super) fn blame_constraint(&self, fr1: RegionVid,
273 elem: impl ToElementIndex) -> ConstraintIndex {
274 // Find everything that influenced final value of `fr`.
275 let influenced_fr1 = self.dependencies(fr1);
277 // Try to find some outlives constraint `'X: fr2` where `'X`
278 // influenced `fr1`. Blame that.
280 // NB, this is a pretty bad choice most of the time. In
281 // particular, the connection between `'X` and `fr1` may not
282 // be obvious to the user -- not to mention the naive notion
283 // of dependencies, which doesn't account for the locations of
284 // contraints at all. But it will do for now.
285 let relevant_constraint = self.constraints
287 .filter_map(|(i, constraint)| {
288 if !self.liveness_constraints.contains(constraint.sub, elem) {
291 influenced_fr1[constraint.sup]
292 .map(|distance| (distance, i))
295 .min() // constraining fr1 with fewer hops *ought* to be more obvious
296 .map(|(_dist, i)| i);
298 relevant_constraint.unwrap_or_else(|| {
300 "could not find any constraint to blame for {:?}: {:?}",
307 /// Finds all regions whose values `'a` may depend on in some way.
308 /// For each region, returns either `None` (does not influence
309 /// `'a`) or `Some(d)` which indicates that it influences `'a`
310 /// with distinct `d` (minimum number of edges that must be
313 /// Used during error reporting, extremely naive and inefficient.
314 fn dependencies(&self, r0: RegionVid) -> IndexVec<RegionVid, Option<usize>> {
315 let mut result_set = IndexVec::from_elem(None, &self.definitions);
316 let mut changed = true;
317 result_set[r0] = Some(0); // distance 0 from `r0`
321 for constraint in &*self.constraints {
322 if let Some(n) = result_set[constraint.sup] {
324 if result_set[constraint.sub]
325 .map(|distance| m < distance)
328 result_set[constraint.sub] = Some(m);