src/librustc_mir/borrow_check/nll/region_infer/error_reporting/mod.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 borrow_check::nll::region_infer::{ConstraintIndex, RegionInferenceContext};
  12 use borrow_check::nll::type_check::Locations;
  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::{self, Location, Mir, Place, Rvalue, StatementKind, TerminatorKind};
  17 use rustc::ty::RegionVid;
  18 use rustc_data_structures::indexed_vec::IndexVec;
  19 use rustc_errors::Diagnostic;
  20 use std::collections::VecDeque;
  21 use std::fmt;
  22 use syntax_pos::Span;
  23
  24 mod region_name;
  25 mod var_name;
  26
  27 /// Constraints that are considered interesting can be categorized to
  28 /// determine why they are interesting. Order of variants indicates
  29 /// sort order of the category, thereby influencing diagnostic output.
  30 #[derive(Copy, Clone, Debug, Eq, PartialEq, PartialOrd, Ord)]
  31 enum ConstraintCategory {
  32     Cast,
  33     Assignment,
  34     Return,
  35     CallArgument,
  36     Other,
  37     Boring,
  38 }
  39
  40 impl fmt::Display for ConstraintCategory {
  41     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  42         // Must end with a space. Allows for empty names to be provided.
  43         match self {
  44             ConstraintCategory::Assignment => write!(f, "assignment "),
  45             ConstraintCategory::Return => write!(f, "return "),
  46             ConstraintCategory::Cast => write!(f, "cast "),
  47             ConstraintCategory::CallArgument => write!(f, "argument "),
  48             _ => write!(f, ""),
  49         }
  50     }
  51 }
  52
  53 #[derive(Copy, Clone, PartialEq, Eq)]
  54 enum Trace {
  55     StartRegion,
  56     FromConstraint(ConstraintIndex),
  57     NotVisited,
  58 }
  59
  60 impl<'tcx> RegionInferenceContext<'tcx> {
  61     /// Tries to find the best constraint to blame for the fact that
  62     /// `R: from_region`, where `R` is some region that meets
  63     /// `target_test`. This works by following the constraint graph,
  64     /// creating a constraint path that forces `R` to outlive
  65     /// `from_region`, and then finding the best choices within that
  66     /// path to blame.
  67     fn best_blame_constraint(
  68         &self,
  69         mir: &Mir<'tcx>,
  70         from_region: RegionVid,
  71         target_test: impl Fn(RegionVid) -> bool,
  72     ) -> (ConstraintCategory, Span, RegionVid) {
  73         debug!("best_blame_constraint(from_region={:?})", from_region);
  74
  75         // Find all paths
  76         let (path, target_region) = self
  77             .find_constraint_paths_between_regions(from_region, target_test)
  78             .unwrap();
  79         debug!(
  80             "best_blame_constraint: path={:#?}",
  81             path.iter()
  82                 .map(|&ci| format!(
  83                     "{:?}: {:?} ({:?}: {:?})",
  84                     ci,
  85                     &self.constraints[ci],
  86                     self.constraint_sccs.scc(self.constraints[ci].sup),
  87                     self.constraint_sccs.scc(self.constraints[ci].sub),
  88                 ))
  89                 .collect::<Vec<_>>()
  90         );
  91
  92         // Classify each of the constraints along the path.
  93         let mut categorized_path: Vec<(ConstraintCategory, Span)> = path
  94             .iter()
  95             .map(|&index| self.classify_constraint(index, mir))
  96             .collect();
  97         debug!(
  98             "best_blame_constraint: categorized_path={:#?}",
  99             categorized_path
 100         );
 101
 102         // To find the best span to cite, we first try to look for the
 103         // final constraint that is interesting and where the `sup` is
 104         // not unified with the ultimate target region. The reason
 105         // for this is that we have a chain of constraints that lead
 106         // from the source to the target region, something like:
 107         //
 108         //    '0: '1 ('0 is the source)
 109         //    '1: '2
 110         //    '2: '3
 111         //    '3: '4
 112         //    '4: '5
 113         //    '5: '6 ('6 is the target)
 114         //
 115         // Some of those regions are unified with `'6` (in the same
 116         // SCC).  We want to screen those out. After that point, the
 117         // "closest" constraint we have to the end is going to be the
 118         // most likely to be the point where the value escapes -- but
 119         // we still want to screen for an "interesting" point to
 120         // highlight (e.g., a call site or something).
 121         let target_scc = self.constraint_sccs.scc(target_region);
 122         let best_choice = (0..path.len()).rev().find(|&i| {
 123             let constraint = &self.constraints[path[i]];
 124
 125             let constraint_sup_scc = self.constraint_sccs.scc(constraint.sup);
 126             if constraint_sup_scc == target_scc {
 127                 return false;
 128             }
 129
 130             match categorized_path[i].0 {
 131                 ConstraintCategory::Boring => false,
 132                 _ => true,
 133             }
 134         });
 135         if let Some(i) = best_choice {
 136             let (category, span) = categorized_path[i];
 137             return (category, span, target_region);
 138         }
 139
 140         // If that search fails, that is.. unusual. Maybe everything
 141         // is in the same SCC or something. In that case, find what
 142         // appears to be the most interesting point to report to the
 143         // user via an even more ad-hoc guess.
 144         categorized_path.sort_by(|p0, p1| p0.0.cmp(&p1.0));
 145         debug!("best_blame_constraint: sorted_path={:#?}", categorized_path);
 146
 147         let &(category, span) = categorized_path.first().unwrap();
 148
 149         (category, span, target_region)
 150     }
 151
 152     /// Walks the graph of constraints (where `'a: 'b` is considered
 153     /// an edge `'a -> 'b`) to find all paths from `from_region` to
 154     /// `to_region`. The paths are accumulated into the vector
 155     /// `results`. The paths are stored as a series of
 156     /// `ConstraintIndex` values -- in other words, a list of *edges*.
 157     ///
 158     /// Returns: a series of constraints as well as the region `R`
 159     /// that passed the target test.
 160     fn find_constraint_paths_between_regions(
 161         &self,
 162         from_region: RegionVid,
 163         target_test: impl Fn(RegionVid) -> bool,
 164     ) -> Option<(Vec<ConstraintIndex>, RegionVid)> {
 165         let mut context = IndexVec::from_elem(Trace::NotVisited, &self.definitions);
 166         context[from_region] = Trace::StartRegion;
 167
 168         // Use a deque so that we do a breadth-first search. We will
 169         // stop at the first match, which ought to be the shortest
 170         // path (fewest constraints).
 171         let mut deque = VecDeque::new();
 172         deque.push_back(from_region);
 173
 174         while let Some(r) = deque.pop_front() {
 175             // Check if we reached the region we were looking for. If so,
 176             // we can reconstruct the path that led to it and return it.
 177             if target_test(r) {
 178                 let mut result = vec![];
 179                 let mut p = r;
 180                 loop {
 181                     match context[p] {
 182                         Trace::NotVisited => {
 183                             bug!("found unvisited region {:?} on path to {:?}", p, r)
 184                         }
 185                         Trace::FromConstraint(c) => {
 186                             result.push(c);
 187                             p = self.constraints[c].sup;
 188                         }
 189
 190                         Trace::StartRegion => {
 191                             result.reverse();
 192                             return Some((result, r));
 193                         }
 194                     }
 195                 }
 196             }
 197
 198             // Otherwise, walk over the outgoing constraints and
 199             // enqueue any regions we find, keeping track of how we
 200             // reached them.
 201             for constraint in self.constraint_graph.outgoing_edges(r) {
 202                 assert_eq!(self.constraints[constraint].sup, r);
 203                 let sub_region = self.constraints[constraint].sub;
 204                 if let Trace::NotVisited = context[sub_region] {
 205                     context[sub_region] = Trace::FromConstraint(constraint);
 206                     deque.push_back(sub_region);
 207                 }
 208             }
 209         }
 210
 211         None
 212     }
 213
 214     /// This function will return true if a constraint is interesting and false if a constraint
 215     /// is not. It is useful in filtering constraint paths to only interesting points.
 216     fn constraint_is_interesting(&self, index: ConstraintIndex) -> bool {
 217         let constraint = self.constraints[index];
 218         debug!(
 219             "constraint_is_interesting: locations={:?} constraint={:?}",
 220             constraint.locations, constraint
 221         );
 222
 223         match constraint.locations {
 224             Locations::Interesting(_) | Locations::All => true,
 225             _ => false,
 226         }
 227     }
 228
 229     /// This function classifies a constraint from a location.
 230     fn classify_constraint(
 231         &self,
 232         index: ConstraintIndex,
 233         mir: &Mir<'tcx>,
 234     ) -> (ConstraintCategory, Span) {
 235         let constraint = self.constraints[index];
 236         debug!("classify_constraint: constraint={:?}", constraint);
 237         let span = constraint.locations.span(mir);
 238         let location = constraint
 239             .locations
 240             .from_location()
 241             .unwrap_or(Location::START);
 242
 243         if !self.constraint_is_interesting(index) {
 244             return (ConstraintCategory::Boring, span);
 245         }
 246
 247         let data = &mir[location.block];
 248         debug!(
 249             "classify_constraint: location={:?} data={:?}",
 250             location, data
 251         );
 252         let category = if location.statement_index == data.statements.len() {
 253             if let Some(ref terminator) = data.terminator {
 254                 debug!("classify_constraint: terminator.kind={:?}", terminator.kind);
 255                 match terminator.kind {
 256                     TerminatorKind::DropAndReplace { .. } => ConstraintCategory::Assignment,
 257                     TerminatorKind::Call { .. } => ConstraintCategory::CallArgument,
 258                     _ => ConstraintCategory::Other,
 259                 }
 260             } else {
 261                 ConstraintCategory::Other
 262             }
 263         } else {
 264             let statement = &data.statements[location.statement_index];
 265             debug!("classify_constraint: statement.kind={:?}", statement.kind);
 266             match statement.kind {
 267                 StatementKind::Assign(ref place, ref rvalue) => {
 268                     debug!("classify_constraint: place={:?} rvalue={:?}", place, rvalue);
 269                     if *place == Place::Local(mir::RETURN_PLACE) {
 270                         ConstraintCategory::Return
 271                     } else {
 272                         match rvalue {
 273                             Rvalue::Cast(..) => ConstraintCategory::Cast,
 274                             Rvalue::Use(..) | Rvalue::Aggregate(..) => {
 275                                 ConstraintCategory::Assignment
 276                             }
 277                             _ => ConstraintCategory::Other,
 278                         }
 279                     }
 280                 }
 281                 _ => ConstraintCategory::Other,
 282             }
 283         };
 284
 285         (category, span)
 286     }
 287
 288     /// Report an error because the universal region `fr` was required to outlive
 289     /// `outlived_fr` but it is not known to do so. For example:
 290     ///
 291     /// ```
 292     /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x }
 293     /// ```
 294     ///
 295     /// Here we would be invoked with `fr = 'a` and `outlived_fr = `'b`.
 296     pub(super) fn report_error(
 297         &self,
 298         mir: &Mir<'tcx>,
 299         infcx: &InferCtxt<'_, '_, 'tcx>,
 300         mir_def_id: DefId,
 301         fr: RegionVid,
 302         outlived_fr: RegionVid,
 303         errors_buffer: &mut Vec<Diagnostic>,
 304     ) {
 305         debug!("report_error(fr={:?}, outlived_fr={:?})", fr, outlived_fr);
 306
 307         let (category, span, _) = self.best_blame_constraint(mir, fr, |r| r == outlived_fr);
 308
 309         // Check if we can use one of the "nice region errors".
 310         if let (Some(f), Some(o)) = (self.to_error_region(fr), self.to_error_region(outlived_fr)) {
 311             let tables = infcx.tcx.typeck_tables_of(mir_def_id);
 312             let nice = NiceRegionError::new_from_span(infcx.tcx, span, o, f, Some(tables));
 313             if let Some(_error_reported) = nice.try_report_from_nll() {
 314                 return;
 315             }
 316         }
 317
 318         let (fr_is_local, outlived_fr_is_local): (bool, bool) = (
 319             self.universal_regions.is_local_free_region(fr),
 320             self.universal_regions.is_local_free_region(outlived_fr),
 321         );
 322         debug!("report_error: fr_is_local={:?} outlived_fr_is_local={:?} category={:?}",
 323                fr_is_local, outlived_fr_is_local, category);
 324
 325         match (category, fr_is_local, outlived_fr_is_local) {
 326             (ConstraintCategory::Assignment, true, false) |
 327             (ConstraintCategory::CallArgument, true, false) =>
 328                 self.report_escaping_data_error(mir, infcx, mir_def_id, fr, outlived_fr,
 329                                                 category, span, errors_buffer),
 330             _ =>
 331                 self.report_general_error(mir, infcx, mir_def_id, fr, fr_is_local,
 332                                           outlived_fr, outlived_fr_is_local,
 333                                           category, span, errors_buffer),
 334         };
 335     }
 336
 337     fn report_escaping_data_error(
 338         &self,
 339         mir: &Mir<'tcx>,
 340         infcx: &InferCtxt<'_, '_, 'tcx>,
 341         mir_def_id: DefId,
 342         fr: RegionVid,
 343         outlived_fr: RegionVid,
 344         category: ConstraintCategory,
 345         span: Span,
 346         errors_buffer: &mut Vec<Diagnostic>,
 347     ) {
 348         let fr_name_and_span = self.get_var_name_and_span_for_region(infcx.tcx, mir, fr);
 349         let outlived_fr_name_and_span =
 350             self.get_var_name_and_span_for_region(infcx.tcx, mir, outlived_fr);
 351
 352         let escapes_from = if infcx.tcx.is_closure(mir_def_id) { "closure" } else { "function" };
 353
 354         if fr_name_and_span.is_none() && outlived_fr_name_and_span.is_none() {
 355             return self.report_general_error(mir, infcx, mir_def_id,
 356                                              fr, true, outlived_fr, false,
 357                                              category, span, errors_buffer);
 358         }
 359
 360         let mut diag = infcx.tcx.sess.struct_span_err(
 361             span, &format!("borrowed data escapes outside of {}", escapes_from),
 362         );
 363
 364         if let Some((outlived_fr_name, outlived_fr_span)) = outlived_fr_name_and_span {
 365             if let Some(name) = outlived_fr_name {
 366                 diag.span_label(
 367                     outlived_fr_span,
 368                     format!("`{}` is declared here, outside of the {} body", name, escapes_from),
 369                 );
 370             }
 371         }
 372
 373         if let Some((fr_name, fr_span)) = fr_name_and_span {
 374             if let Some(name) = fr_name {
 375                 diag.span_label(
 376                     fr_span,
 377                     format!("`{}` is a reference that is only valid in the {} body",
 378                             name, escapes_from),
 379                 );
 380
 381                 diag.span_label(span, format!("`{}` escapes the {} body here",
 382                                                name, escapes_from));
 383             }
 384         }
 385
 386         diag.buffer(errors_buffer);
 387     }
 388
 389     fn report_general_error(
 390         &self,
 391         mir: &Mir<'tcx>,
 392         infcx: &InferCtxt<'_, '_, 'tcx>,
 393         mir_def_id: DefId,
 394         fr: RegionVid,
 395         fr_is_local: bool,
 396         outlived_fr: RegionVid,
 397         outlived_fr_is_local: bool,
 398         category: ConstraintCategory,
 399         span: Span,
 400         errors_buffer: &mut Vec<Diagnostic>,
 401     ) {
 402         let mut diag = infcx.tcx.sess.struct_span_err(
 403             span,
 404             "unsatisfied lifetime constraints", // FIXME
 405         );
 406
 407         let counter = &mut 1;
 408         let fr_name = self.give_region_a_name(
 409             infcx, mir, mir_def_id, fr, counter, &mut diag);
 410         let outlived_fr_name = self.give_region_a_name(
 411             infcx, mir, mir_def_id, outlived_fr, counter, &mut diag);
 412
 413         let mir_def_name = if infcx.tcx.is_closure(mir_def_id) { "closure" } else { "function" };
 414
 415         match (category, outlived_fr_is_local, fr_is_local) {
 416             (ConstraintCategory::Return, true, _) => {
 417                 diag.span_label(span, format!(
 418                     "{} was supposed to return data with lifetime `{}` but it is returning \
 419                     data with lifetime `{}`",
 420                     mir_def_name, fr_name, outlived_fr_name,
 421                 ));
 422             },
 423             _ => {
 424                 diag.span_label(span, format!(
 425                     "{}requires that `{}` must outlive `{}`",
 426                     category, fr_name, outlived_fr_name,
 427                 ));
 428             },
 429         }
 430
 431         diag.buffer(errors_buffer);
 432     }
 433
 434     // Finds some region R such that `fr1: R` and `R` is live at
 435     // `elem`.
 436     crate fn find_sub_region_live_at(&self, fr1: RegionVid, elem: Location) -> RegionVid {
 437         // Find all paths
 438         let (_path, r) =
 439             self.find_constraint_paths_between_regions(fr1, |r| {
 440                 self.liveness_constraints.contains(r, elem)
 441             }).unwrap();
 442         r
 443     }
 444
 445     // Finds a good span to blame for the fact that `fr1` outlives `fr2`.
 446     crate fn find_outlives_blame_span(
 447         &self,
 448         mir: &Mir<'tcx>,
 449         fr1: RegionVid,
 450         fr2: RegionVid,
 451     ) -> Span {
 452         let (_, span, _) = self.best_blame_constraint(mir, fr1, |r| r == fr2);
 453         span
 454     }
 455 }