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::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;
  22 use std::fmt;
  23 use syntax_pos::Span;
  24
  25 mod region_name;
  26 mod var_name;
  27
  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 {
  33     Cast,
  34     Assignment,
  35     Return,
  36     CallArgument,
  37     Other,
  38     Boring,
  39 }
  40
  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.
  44         match self {
  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 "),
  49             _ => write!(f, ""),
  50         }
  51     }
  52 }
  53
  54 #[derive(Copy, Clone, PartialEq, Eq)]
  55 enum Trace {
  56     StartRegion,
  57     FromOutlivesConstraint(OutlivesConstraint),
  58     NotVisited,
  59 }
  60
  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
  67     /// path to blame.
  68     fn best_blame_constraint(
  69         &self,
  70         mir: &Mir<'tcx>,
  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);
  76
  77         // Find all paths
  78         let (path, target_region) = self
  79             .find_constraint_paths_between_regions(from_region, target_test)
  80             .unwrap();
  81         debug!(
  82             "best_blame_constraint: path={:#?}",
  83             path.iter()
  84                 .map(|&c| format!(
  85                     "{:?} ({:?}: {:?})",
  86                     c,
  87                     self.constraint_sccs.scc(c.sup),
  88                     self.constraint_sccs.scc(c.sub),
  89                 ))
  90                 .collect::<Vec<_>>()
  91         );
  92
  93         // Classify each of the constraints along the path.
  94         let mut categorized_path: Vec<(ConstraintCategory, Span)> = path
  95             .iter()
  96             .map(|&index| self.classify_constraint(index, mir, tcx))
  97             .collect();
  98         debug!(
  99             "best_blame_constraint: categorized_path={:#?}",
 100             categorized_path
 101         );
 102
 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:
 108         //
 109         //    '0: '1 ('0 is the source)
 110         //    '1: '2
 111         //    '2: '3
 112         //    '3: '4
 113         //    '4: '5
 114         //    '5: '6 ('6 is the target)
 115         //
 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];
 125
 126             let constraint_sup_scc = self.constraint_sccs.scc(constraint.sup);
 127
 128             match categorized_path[i].0 {
 129                 ConstraintCategory::Boring => false,
 130                 ConstraintCategory::Other => {
 131                     // other isn't interesting when the two lifetimes
 132                     // are unified.
 133                     constraint_sup_scc != self.constraint_sccs.scc(constraint.sub)
 134                 }
 135                 _ => constraint_sup_scc != target_scc,
 136             }
 137         });
 138         if let Some(i) = best_choice {
 139             let (category, span) = categorized_path[i];
 140             return (category, span, target_region);
 141         }
 142
 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);
 149
 150         let &(category, span) = categorized_path.first().unwrap();
 151
 152         (category, span, target_region)
 153     }
 154
 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*.
 160     ///
 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(
 164         &self,
 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;
 170
 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);
 176
 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.
 180             if target_test(r) {
 181                 let mut result = vec![];
 182                 let mut p = r;
 183                 loop {
 184                     match context[p] {
 185                         Trace::NotVisited => {
 186                             bug!("found unvisited region {:?} on path to {:?}", p, r)
 187                         }
 188                         Trace::FromOutlivesConstraint(c) => {
 189                             result.push(c);
 190                             p = c.sup;
 191                         }
 192
 193                         Trace::StartRegion => {
 194                             result.reverse();
 195                             return Some((result, r));
 196                         }
 197                     }
 198                 }
 199             }
 200
 201             // Otherwise, walk over the outgoing constraints and
 202             // enqueue any regions we find, keeping track of how we
 203             // reached them.
 204             let fr_static = self.universal_regions.fr_static;
 205             for constraint in self.constraint_graph.outgoing_edges(r,
 206                                                                    &self.constraints,
 207                                                                    fr_static) {
 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);
 213                 }
 214             }
 215         }
 216
 217         None
 218     }
 219
 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 {
 223         debug!(
 224             "constraint_is_interesting: locations={:?} constraint={:?}",
 225             constraint.locations, constraint
 226         );
 227
 228         match constraint.locations {
 229             Locations::Interesting(_) | Locations::All => true,
 230             _ => false,
 231         }
 232     }
 233
 234     /// This function classifies a constraint from a location.
 235     fn classify_constraint(
 236         &self,
 237         constraint: OutlivesConstraint,
 238         mir: &Mir<'tcx>,
 239         tcx: TyCtxt<'_, '_, 'tcx>,
 240     ) -> (ConstraintCategory, Span) {
 241         debug!("classify_constraint: constraint={:?}", constraint);
 242         let span = constraint.locations.span(mir);
 243         let location = constraint
 244             .locations
 245             .from_location()
 246             .unwrap_or(Location::START);
 247
 248         if !self.constraint_is_interesting(constraint) {
 249             return (ConstraintCategory::Boring, span);
 250         }
 251
 252         let data = &mir[location.block];
 253         debug!(
 254             "classify_constraint: location={:?} data={:?}",
 255             location, data
 256         );
 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.
 268                     //
 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
 273                     // classification.
 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,
 278                         ) {
 279                             match place {
 280                                 Place::Local(mir::RETURN_PLACE) => ConstraintCategory::Return,
 281                                 _ => ConstraintCategory::Assignment,
 282                             }
 283                         } else {
 284                             ConstraintCategory::CallArgument
 285                         }
 286                     }
 287                     TerminatorKind::Call { destination: None, .. } => {
 288                         ConstraintCategory::CallArgument
 289                     }
 290                     _ => ConstraintCategory::Other,
 291                 }
 292             } else {
 293                 ConstraintCategory::Other
 294             }
 295         } else {
 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
 303                     } else {
 304                         match rvalue {
 305                             Rvalue::Cast(..) => ConstraintCategory::Cast,
 306                             Rvalue::Use(..) | Rvalue::Aggregate(..) => {
 307                                 ConstraintCategory::Assignment
 308                             }
 309                             _ => ConstraintCategory::Other,
 310                         }
 311                     }
 312                 }
 313                 _ => ConstraintCategory::Other,
 314             }
 315         };
 316
 317         (category, span)
 318     }
 319
 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:
 322     ///
 323     /// ```
 324     /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x }
 325     /// ```
 326     ///
 327     /// Here we would be invoked with `fr = 'a` and `outlived_fr = `'b`.
 328     pub(super) fn report_error(
 329         &self,
 330         mir: &Mir<'tcx>,
 331         infcx: &InferCtxt<'_, '_, 'tcx>,
 332         mir_def_id: DefId,
 333         fr: RegionVid,
 334         outlived_fr: RegionVid,
 335         errors_buffer: &mut Vec<Diagnostic>,
 336     ) {
 337         debug!("report_error(fr={:?}, outlived_fr={:?})", fr, outlived_fr);
 338
 339         let (category, span, _) = self.best_blame_constraint(
 340             mir,
 341             infcx.tcx,
 342             fr,
 343             |r| r == outlived_fr
 344         );
 345
 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() {
 351                 return;
 352             }
 353         }
 354
 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),
 358         );
 359         debug!("report_error: fr_is_local={:?} outlived_fr_is_local={:?} category={:?}",
 360                fr_is_local, outlived_fr_is_local, category);
 361
 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),
 367             _ =>
 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),
 371         };
 372     }
 373
 374     fn report_escaping_data_error(
 375         &self,
 376         mir: &Mir<'tcx>,
 377         infcx: &InferCtxt<'_, '_, 'tcx>,
 378         mir_def_id: DefId,
 379         fr: RegionVid,
 380         outlived_fr: RegionVid,
 381         category: ConstraintCategory,
 382         span: Span,
 383         errors_buffer: &mut Vec<Diagnostic>,
 384     ) {
 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);
 388
 389         let escapes_from = if infcx.tcx.is_closure(mir_def_id) { "closure" } else { "function" };
 390
 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);
 395         }
 396
 397         let mut diag = infcx.tcx.sess.struct_span_err(
 398             span, &format!("borrowed data escapes outside of {}", escapes_from),
 399         );
 400
 401         if let Some((outlived_fr_name, outlived_fr_span)) = outlived_fr_name_and_span {
 402             if let Some(name) = outlived_fr_name {
 403                 diag.span_label(
 404                     outlived_fr_span,
 405                     format!("`{}` is declared here, outside of the {} body", name, escapes_from),
 406                 );
 407             }
 408         }
 409
 410         if let Some((fr_name, fr_span)) = fr_name_and_span {
 411             if let Some(name) = fr_name {
 412                 diag.span_label(
 413                     fr_span,
 414                     format!("`{}` is a reference that is only valid in the {} body",
 415                             name, escapes_from),
 416                 );
 417
 418                 diag.span_label(span, format!("`{}` escapes the {} body here",
 419                                                name, escapes_from));
 420             }
 421         }
 422
 423         diag.buffer(errors_buffer);
 424     }
 425
 426     fn report_general_error(
 427         &self,
 428         mir: &Mir<'tcx>,
 429         infcx: &InferCtxt<'_, '_, 'tcx>,
 430         mir_def_id: DefId,
 431         fr: RegionVid,
 432         fr_is_local: bool,
 433         outlived_fr: RegionVid,
 434         outlived_fr_is_local: bool,
 435         category: ConstraintCategory,
 436         span: Span,
 437         errors_buffer: &mut Vec<Diagnostic>,
 438     ) {
 439         let mut diag = infcx.tcx.sess.struct_span_err(
 440             span,
 441             "unsatisfied lifetime constraints", // FIXME
 442         );
 443
 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);
 449
 450         let mir_def_name = if infcx.tcx.is_closure(mir_def_id) { "closure" } else { "function" };
 451
 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
 458                 ));
 459             },
 460             _ => {
 461                 diag.span_label(span, format!(
 462                     "{}requires that `{}` must outlive `{}`",
 463                     category, fr_name, outlived_fr_name,
 464                 ));
 465             },
 466         }
 467
 468         diag.buffer(errors_buffer);
 469     }
 470
 471     // Finds some region R such that `fr1: R` and `R` is live at
 472     // `elem`.
 473     crate fn find_sub_region_live_at(&self, fr1: RegionVid, elem: Location) -> RegionVid {
 474         // Find all paths
 475         let (_path, r) =
 476             self.find_constraint_paths_between_regions(fr1, |r| {
 477                 self.liveness_constraints.contains(r, elem)
 478             }).unwrap();
 479         r
 480     }
 481
 482     // Finds a good span to blame for the fact that `fr1` outlives `fr2`.
 483     crate fn find_outlives_blame_span(
 484         &self,
 485         mir: &Mir<'tcx>,
 486         tcx: TyCtxt<'_, '_, 'tcx>,
 487         fr1: RegionVid,
 488         fr2: RegionVid,
 489     ) -> Span {
 490         let (_, span, _) = self.best_blame_constraint(mir, tcx, fr1, |r| r == fr2);
 491         span
 492     }
 493 }