src/librustc_mir/borrow_check/nll/region_infer/error_reporting.rs

   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.
   4 //
   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.
  10
  11 use std::fmt;
  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;
  22 use syntax_pos::Span;
  23
  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 {
  29     Cast,
  30     Assignment,
  31     Return,
  32     CallArgument,
  33     Other,
  34     Boring,
  35 }
  36
  37 impl fmt::Display for ConstraintCategory {
  38     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  39         match self {
  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"),
  45         }
  46     }
  47 }
  48
  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
  52     /// constraint.
  53     fn find_constraint_paths_from_region(
  54         &self,
  55         r0: RegionVid
  56     ) -> Vec<Vec<ConstraintIndex>> {
  57         let constraints = self.constraints.clone();
  58
  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();
  65         // Ends of paths.
  66         let mut end_regions = FxHashSet();
  67
  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);
  75
  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={:?}",
  82                            index, constraint);
  83                     let next_region = constraint.sup.clone();
  84
  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");
  88                         continue;
  89                     }
  90
  91                     previous.insert(next_region, (index, Some(current)));
  92                     upcoming.push(next_region);
  93                 }
  94             }
  95
  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);
 100             } else {
 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);
 104             }
 105
 106         }
 107
 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);
 113
 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);
 119
 120             // Keep track of the indices.
 121             let mut path: Vec<ConstraintIndex> = vec![index];
 122
 123             while region.is_some() && region != Some(r0) {
 124                 let p = previous.get(&region.unwrap()).unwrap();
 125                 index = p.0;
 126                 region = p.1;
 127
 128                 debug!("find_constraint_paths_from_region: index={:?} region={:?}", index, region);
 129                 path.push(index);
 130             }
 131
 132             // Add to our paths.
 133             paths.push(path);
 134         }
 135
 136         debug!("find_constraint_paths_from_region: paths={:?}", paths);
 137         paths
 138     }
 139
 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 }
 147         }).is_some()
 148     }
 149
 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()?;
 156
 157         if !self.constraint_is_interesting(index) {
 158             return Some((ConstraintCategory::Boring, span));
 159         }
 160
 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,
 168                 }
 169             } else {
 170                 ConstraintCategory::Other
 171             }
 172         } else {
 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
 178                     } else {
 179                         match rvalue {
 180                             Rvalue::Cast(..) => ConstraintCategory::Cast,
 181                             Rvalue::Use(..) => ConstraintCategory::Assignment,
 182                             _ => ConstraintCategory::Other,
 183                         }
 184                     }
 185                 },
 186                 _ => ConstraintCategory::Other,
 187             }
 188         };
 189
 190         Some((category, span))
 191     }
 192
 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:
 195     ///
 196     /// ```
 197     /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x }
 198     /// ```
 199     ///
 200     /// Here we would be invoked with `fr = 'a` and `outlived_fr = `'b`.
 201     pub(super) fn report_error(
 202         &self,
 203         mir: &Mir<'tcx>,
 204         infcx: &InferCtxt<'_, '_, 'tcx>,
 205         mir_def_id: DefId,
 206         fr: RegionVid,
 207         outlived_fr: RegionVid,
 208         blame_span: Span,
 209     ) {
 210         // Obviously uncool error reporting.
 211
 212         let fr_name = self.to_error_region(fr);
 213         let outlived_fr_name = self.to_error_region(outlived_fr);
 214
 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() {
 219                 return;
 220             }
 221         }
 222
 223         let fr_string = match fr_name {
 224             Some(r) => format!("free region `{}`", r),
 225             None => format!("free region `{:?}`", fr),
 226         };
 227
 228         let outlived_fr_string = match outlived_fr_name {
 229             Some(r) => format!("free region `{}`", r),
 230             None => format!("free region `{:?}`", outlived_fr),
 231         };
 232
 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);
 236
 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);
 241
 242         categorized_path.sort_by(|p0, p1| p0.0.cmp(&p1.0));
 243         debug!("report_error: sorted_path={:?}", categorized_path);
 244
 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),
 249             );
 250
 251             diag.emit();
 252         } else {
 253             let mut diag = infcx.tcx.sess.struct_span_err(
 254                 blame_span,
 255                 &format!("{} does not outlive {}", fr_string, outlived_fr_string,),
 256             );
 257
 258             diag.emit();
 259         }
 260     }
 261
 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
 268     }
 269
 270     /// Tries to finds a good span to blame for the fact that `fr1`
 271     /// contains `fr2`.
 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);
 276
 277         // Try to find some outlives constraint `'X: fr2` where `'X`
 278         // influenced `fr1`. Blame that.
 279         //
 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
 286             .iter_enumerated()
 287             .filter_map(|(i, constraint)| {
 288                 if !self.liveness_constraints.contains(constraint.sub, elem) {
 289                     None
 290                 } else {
 291                     influenced_fr1[constraint.sup]
 292                         .map(|distance| (distance, i))
 293                 }
 294             })
 295             .min() // constraining fr1 with fewer hops *ought* to be more obvious
 296             .map(|(_dist, i)| i);
 297
 298         relevant_constraint.unwrap_or_else(|| {
 299             bug!(
 300                 "could not find any constraint to blame for {:?}: {:?}",
 301                 fr1,
 302                 elem,
 303             );
 304         })
 305     }
 306
 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
 311     /// traversed).
 312     ///
 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`
 318
 319         while changed {
 320             changed = false;
 321             for constraint in &*self.constraints {
 322                 if let Some(n) = result_set[constraint.sup] {
 323                     let m = n + 1;
 324                     if result_set[constraint.sub]
 325                         .map(|distance| m < distance)
 326                         .unwrap_or(true)
 327                     {
 328                         result_set[constraint.sub] = Some(m);
 329                         changed = true;
 330                     }
 331                 }
 332             }
 333         }
 334
 335         result_set
 336     }
 337 }