compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs

   1 //! Lexical region resolution.
   2
   3 use crate::infer::region_constraints::Constraint;
   4 use crate::infer::region_constraints::GenericKind;
   5 use crate::infer::region_constraints::RegionConstraintData;
   6 use crate::infer::region_constraints::VarInfos;
   7 use crate::infer::region_constraints::VerifyBound;
   8 use crate::infer::RegionRelations;
   9 use crate::infer::RegionVariableOrigin;
  10 use crate::infer::SubregionOrigin;
  11 use rustc_data_structures::fx::FxHashSet;
  12 use rustc_data_structures::graph::implementation::{
  13     Direction, Graph, NodeIndex, INCOMING, OUTGOING,
  14 };
  15 use rustc_data_structures::intern::Interned;
  16 use rustc_index::vec::{Idx, IndexVec};
  17 use rustc_middle::ty::fold::TypeFoldable;
  18 use rustc_middle::ty::PlaceholderRegion;
  19 use rustc_middle::ty::{self, Ty, TyCtxt};
  20 use rustc_middle::ty::{ReEarlyBound, ReErased, ReFree, ReStatic};
  21 use rustc_middle::ty::{ReLateBound, RePlaceholder, ReVar};
  22 use rustc_middle::ty::{Region, RegionVid};
  23 use rustc_span::Span;
  24 use std::fmt;
  25
  26 use super::outlives::test_type_match;
  27
  28 /// This function performs lexical region resolution given a complete
  29 /// set of constraints and variable origins. It performs a fixed-point
  30 /// iteration to find region values which satisfy all constraints,
  31 /// assuming such values can be found. It returns the final values of
  32 /// all the variables as well as a set of errors that must be reported.
  33 #[instrument(level = "debug", skip(region_rels, var_infos, data))]
  34 pub(crate) fn resolve<'tcx>(
  35     param_env: ty::ParamEnv<'tcx>,
  36     region_rels: &RegionRelations<'_, 'tcx>,
  37     var_infos: VarInfos,
  38     data: RegionConstraintData<'tcx>,
  39 ) -> (LexicalRegionResolutions<'tcx>, Vec<RegionResolutionError<'tcx>>) {
  40     let mut errors = vec![];
  41     let mut resolver = LexicalResolver { param_env, region_rels, var_infos, data };
  42     let values = resolver.infer_variable_values(&mut errors);
  43     (values, errors)
  44 }
  45
  46 /// Contains the result of lexical region resolution. Offers methods
  47 /// to lookup up the final value of a region variable.
  48 #[derive(Clone)]
  49 pub struct LexicalRegionResolutions<'tcx> {
  50     pub(crate) values: IndexVec<RegionVid, VarValue<'tcx>>,
  51 }
  52
  53 #[derive(Copy, Clone, Debug)]
  54 pub(crate) enum VarValue<'tcx> {
  55     /// Empty lifetime is for data that is never accessed.  We tag the
  56     /// empty lifetime with a universe -- the idea is that we don't
  57     /// want `exists<'a> { forall<'b> { 'b: 'a } }` to be satisfiable.
  58     /// Therefore, the `'empty` in a universe `U` is less than all
  59     /// regions visible from `U`, but not less than regions not visible
  60     /// from `U`.
  61     Empty(ty::UniverseIndex),
  62     Value(Region<'tcx>),
  63     ErrorValue,
  64 }
  65
  66 #[derive(Clone, Debug)]
  67 pub enum RegionResolutionError<'tcx> {
  68     /// `ConcreteFailure(o, a, b)`:
  69     ///
  70     /// `o` requires that `a <= b`, but this does not hold
  71     ConcreteFailure(SubregionOrigin<'tcx>, Region<'tcx>, Region<'tcx>),
  72
  73     /// `GenericBoundFailure(p, s, a)
  74     ///
  75     /// The parameter/associated-type `p` must be known to outlive the lifetime
  76     /// `a` (but none of the known bounds are sufficient).
  77     GenericBoundFailure(SubregionOrigin<'tcx>, GenericKind<'tcx>, Region<'tcx>),
  78
  79     /// `SubSupConflict(v, v_origin, sub_origin, sub_r, sup_origin, sup_r)`:
  80     ///
  81     /// Could not infer a value for `v` (which has origin `v_origin`)
  82     /// because `sub_r <= v` (due to `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
  83     /// `sub_r <= sup_r` does not hold.
  84     SubSupConflict(
  85         RegionVid,
  86         RegionVariableOrigin,
  87         SubregionOrigin<'tcx>,
  88         Region<'tcx>,
  89         SubregionOrigin<'tcx>,
  90         Region<'tcx>,
  91         Vec<Span>, // All the influences on a given value that didn't meet its constraints.
  92     ),
  93
  94     /// Indicates a `'b: 'a` constraint where `'a` is in a universe that
  95     /// cannot name the placeholder `'b`.
  96     UpperBoundUniverseConflict(
  97         RegionVid,
  98         RegionVariableOrigin,
  99         ty::UniverseIndex,     // the universe index of the region variable
 100         SubregionOrigin<'tcx>, // cause of the constraint
 101         Region<'tcx>,          // the placeholder `'b`
 102     ),
 103 }
 104
 105 struct RegionAndOrigin<'tcx> {
 106     region: Region<'tcx>,
 107     origin: SubregionOrigin<'tcx>,
 108 }
 109
 110 type RegionGraph<'tcx> = Graph<(), Constraint<'tcx>>;
 111
 112 struct LexicalResolver<'cx, 'tcx> {
 113     param_env: ty::ParamEnv<'tcx>,
 114     region_rels: &'cx RegionRelations<'cx, 'tcx>,
 115     var_infos: VarInfos,
 116     data: RegionConstraintData<'tcx>,
 117 }
 118
 119 impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
 120     fn tcx(&self) -> TyCtxt<'tcx> {
 121         self.region_rels.tcx
 122     }
 123
 124     fn infer_variable_values(
 125         &mut self,
 126         errors: &mut Vec<RegionResolutionError<'tcx>>,
 127     ) -> LexicalRegionResolutions<'tcx> {
 128         let mut var_data = self.construct_var_data();
 129
 130         if cfg!(debug_assertions) {
 131             self.dump_constraints();
 132         }
 133
 134         let graph = self.construct_graph();
 135         self.expand_givens(&graph);
 136         self.expansion(&mut var_data);
 137         self.collect_errors(&mut var_data, errors);
 138         self.collect_var_errors(&var_data, &graph, errors);
 139         var_data
 140     }
 141
 142     fn num_vars(&self) -> usize {
 143         self.var_infos.len()
 144     }
 145
 146     /// Initially, the value for all variables is set to `'empty`, the
 147     /// empty region. The `expansion` phase will grow this larger.
 148     fn construct_var_data(&self) -> LexicalRegionResolutions<'tcx> {
 149         LexicalRegionResolutions {
 150             values: IndexVec::from_fn_n(
 151                 |vid| {
 152                     let vid_universe = self.var_infos[vid].universe;
 153                     VarValue::Empty(vid_universe)
 154                 },
 155                 self.num_vars(),
 156             ),
 157         }
 158     }
 159
 160     #[instrument(level = "debug", skip(self))]
 161     fn dump_constraints(&self) {
 162         for (idx, (constraint, _)) in self.data.constraints.iter().enumerate() {
 163             debug!("Constraint {} => {:?}", idx, constraint);
 164         }
 165     }
 166
 167     fn expand_givens(&mut self, graph: &RegionGraph<'_>) {
 168         // Givens are a kind of horrible hack to account for
 169         // constraints like 'c <= '0 that are known to hold due to
 170         // closure signatures (see the comment above on the `givens`
 171         // field). They should go away. But until they do, the role
 172         // of this fn is to account for the transitive nature:
 173         //
 174         //     Given 'c <= '0
 175         //     and   '0 <= '1
 176         //     then  'c <= '1
 177
 178         let seeds: Vec<_> = self.data.givens.iter().cloned().collect();
 179         for (r, vid) in seeds {
 180             // While all things transitively reachable in the graph
 181             // from the variable (`'0` in the example above).
 182             let seed_index = NodeIndex(vid.index() as usize);
 183             for succ_index in graph.depth_traverse(seed_index, OUTGOING) {
 184                 let succ_index = succ_index.0;
 185
 186                 // The first N nodes correspond to the region
 187                 // variables. Other nodes correspond to constant
 188                 // regions.
 189                 if succ_index < self.num_vars() {
 190                     let succ_vid = RegionVid::new(succ_index);
 191
 192                     // Add `'c <= '1`.
 193                     self.data.givens.insert((r, succ_vid));
 194                 }
 195             }
 196         }
 197     }
 198
 199     /// Gets the LUb of a given region and the empty region
 200     fn lub_empty(&self, a_region: Region<'tcx>) -> Result<Region<'tcx>, PlaceholderRegion> {
 201         match *a_region {
 202             ReLateBound(..) | ReErased => {
 203                 bug!("cannot relate region: {:?}", a_region);
 204             }
 205
 206             ReVar(v_id) => {
 207                 span_bug!(
 208                     self.var_infos[v_id].origin.span(),
 209                     "lub invoked with non-concrete regions: {:?}",
 210                     a_region,
 211                 );
 212             }
 213
 214             ReStatic => {
 215                 // nothing lives longer than `'static`
 216                 Ok(self.tcx().lifetimes.re_static)
 217             }
 218
 219             ReEarlyBound(_) | ReFree(_) => {
 220                 // All empty regions are less than early-bound, free,
 221                 // and scope regions.
 222                 Ok(a_region)
 223             }
 224
 225             RePlaceholder(placeholder) => Err(placeholder),
 226         }
 227     }
 228
 229     fn expansion(&self, var_values: &mut LexicalRegionResolutions<'tcx>) {
 230         // In the first pass, we expand region vids according to constraints we
 231         // have previously found. In the second pass, we loop through the region
 232         // vids we expanded and expand *across* region vids (effectively
 233         // "expanding" new `RegSubVar` constraints).
 234
 235         // Tracks the `VarSubVar` constraints generated for each region vid. We
 236         // later use this to expand across vids.
 237         let mut constraints = IndexVec::from_elem_n(Vec::new(), var_values.values.len());
 238         // Tracks the changed region vids.
 239         let mut changes = Vec::new();
 240         for constraint in self.data.constraints.keys() {
 241             match *constraint {
 242                 Constraint::RegSubVar(a_region, b_vid) => {
 243                     let b_data = var_values.value_mut(b_vid);
 244
 245                     if self.expand_node(a_region, b_vid, b_data) {
 246                         changes.push(b_vid);
 247                     }
 248                 }
 249                 Constraint::VarSubVar(a_vid, b_vid) => match *var_values.value(a_vid) {
 250                     VarValue::ErrorValue => continue,
 251                     VarValue::Empty(a_universe) => {
 252                         let b_data = var_values.value_mut(b_vid);
 253
 254                         let changed = (|| match *b_data {
 255                             VarValue::Empty(b_universe) => {
 256                                 // Empty regions are ordered according to the universe
 257                                 // they are associated with.
 258                                 let ui = a_universe.min(b_universe);
 259
 260                                 debug!(
 261                                     "Expanding value of {:?} \
 262                                     from empty lifetime with universe {:?} \
 263                                     to empty lifetime with universe {:?}",
 264                                     b_vid, b_universe, ui
 265                                 );
 266
 267                                 *b_data = VarValue::Empty(ui);
 268                                 true
 269                             }
 270                             VarValue::Value(cur_region) => {
 271                                 let lub = match self.lub_empty(cur_region) {
 272                                     Ok(r) => r,
 273                                     // If the empty and placeholder regions are in the same universe,
 274                                     // then the LUB is the Placeholder region (which is the cur_region).
 275                                     // If they are not in the same universe, the LUB is the Static lifetime.
 276                                     Err(placeholder) if a_universe == placeholder.universe => {
 277                                         cur_region
 278                                     }
 279                                     Err(_) => self.tcx().lifetimes.re_static,
 280                                 };
 281
 282                                 if lub == cur_region {
 283                                     return false;
 284                                 }
 285
 286                                 debug!(
 287                                     "Expanding value of {:?} from {:?} to {:?}",
 288                                     b_vid, cur_region, lub
 289                                 );
 290
 291                                 *b_data = VarValue::Value(lub);
 292                                 true
 293                             }
 294
 295                             VarValue::ErrorValue => false,
 296                         })();
 297
 298                         if changed {
 299                             changes.push(b_vid);
 300                         }
 301                         match b_data {
 302                             VarValue::Value(Region(Interned(ReStatic, _)))
 303                             | VarValue::ErrorValue => (),
 304                             _ => {
 305                                 constraints[a_vid].push((a_vid, b_vid));
 306                                 constraints[b_vid].push((a_vid, b_vid));
 307                             }
 308                         }
 309                     }
 310                     VarValue::Value(a_region) => {
 311                         let b_data = var_values.value_mut(b_vid);
 312
 313                         if self.expand_node(a_region, b_vid, b_data) {
 314                             changes.push(b_vid);
 315                         }
 316                         match b_data {
 317                             VarValue::Value(Region(Interned(ReStatic, _)))
 318                             | VarValue::ErrorValue => (),
 319                             _ => {
 320                                 constraints[a_vid].push((a_vid, b_vid));
 321                                 constraints[b_vid].push((a_vid, b_vid));
 322                             }
 323                         }
 324                     }
 325                 },
 326                 Constraint::RegSubReg(..) | Constraint::VarSubReg(..) => {
 327                     // These constraints are checked after expansion
 328                     // is done, in `collect_errors`.
 329                     continue;
 330                 }
 331             }
 332         }
 333
 334         while let Some(vid) = changes.pop() {
 335             constraints[vid].retain(|&(a_vid, b_vid)| {
 336                 let VarValue::Value(a_region) = *var_values.value(a_vid) else {
 337                     return false;
 338                 };
 339                 let b_data = var_values.value_mut(b_vid);
 340                 if self.expand_node(a_region, b_vid, b_data) {
 341                     changes.push(b_vid);
 342                 }
 343                 !matches!(
 344                     b_data,
 345                     VarValue::Value(Region(Interned(ReStatic, _))) | VarValue::ErrorValue
 346                 )
 347             });
 348         }
 349     }
 350
 351     /// Expands the value of the region represented with `b_vid` with current
 352     /// value `b_data` to the lub of `b_data` and `a_region`. The corresponds
 353     /// with the constraint `'?b: 'a` (`'a <: '?b`), where `'a` is some known
 354     /// region and `'?b` is some region variable.
 355     fn expand_node(
 356         &self,
 357         a_region: Region<'tcx>,
 358         b_vid: RegionVid,
 359         b_data: &mut VarValue<'tcx>,
 360     ) -> bool {
 361         debug!("expand_node({:?}, {:?} == {:?})", a_region, b_vid, b_data);
 362
 363         match *a_region {
 364             // Check if this relationship is implied by a given.
 365             ty::ReEarlyBound(_) | ty::ReFree(_) => {
 366                 if self.data.givens.contains(&(a_region, b_vid)) {
 367                     debug!("given");
 368                     return false;
 369                 }
 370             }
 371
 372             _ => {}
 373         }
 374
 375         match *b_data {
 376             VarValue::Empty(empty_ui) => {
 377                 let lub = match self.lub_empty(a_region) {
 378                     Ok(r) => r,
 379                     // If this empty region is from a universe that can
 380                     // name the placeholder, then the placeholder is
 381                     // larger; otherwise, the only ancestor is `'static`.
 382                     Err(placeholder) if empty_ui.can_name(placeholder.universe) => {
 383                         self.tcx().mk_region(RePlaceholder(placeholder))
 384                     }
 385                     Err(_) => self.tcx().lifetimes.re_static,
 386                 };
 387
 388                 debug!("Expanding value of {:?} from empty lifetime to {:?}", b_vid, lub);
 389
 390                 *b_data = VarValue::Value(lub);
 391                 true
 392             }
 393             VarValue::Value(cur_region) => {
 394                 // This is a specialized version of the `lub_concrete_regions`
 395                 // check below for a common case, here purely as an
 396                 // optimization.
 397                 let b_universe = self.var_infos[b_vid].universe;
 398
 399                 let mut lub = self.lub_concrete_regions(a_region, cur_region);
 400                 if lub == cur_region {
 401                     return false;
 402                 }
 403
 404                 // Watch out for `'b: !1` relationships, where the
 405                 // universe of `'b` can't name the placeholder `!1`. In
 406                 // that case, we have to grow `'b` to be `'static` for the
 407                 // relationship to hold. This is obviously a kind of sub-optimal
 408                 // choice -- in the future, when we incorporate a knowledge
 409                 // of the parameter environment, we might be able to find a
 410                 // tighter bound than `'static`.
 411                 //
 412                 // (This might e.g. arise from being asked to prove `for<'a> { 'b: 'a }`.)
 413                 if let ty::RePlaceholder(p) = *lub && b_universe.cannot_name(p.universe) {
 414                     lub = self.tcx().lifetimes.re_static;
 415                 }
 416
 417                 debug!("Expanding value of {:?} from {:?} to {:?}", b_vid, cur_region, lub);
 418
 419                 *b_data = VarValue::Value(lub);
 420                 true
 421             }
 422
 423             VarValue::ErrorValue => false,
 424         }
 425     }
 426
 427     /// True if `a <= b`.
 428     fn sub_region_values(&self, a: VarValue<'tcx>, b: VarValue<'tcx>) -> bool {
 429         match (a, b) {
 430             // Error region is `'static`
 431             (VarValue::ErrorValue, _) | (_, VarValue::ErrorValue) => return true,
 432             (VarValue::Empty(a_ui), VarValue::Empty(b_ui)) => {
 433                 // Empty regions are ordered according to the universe
 434                 // they are associated with.
 435                 a_ui.min(b_ui) == b_ui
 436             }
 437             (VarValue::Value(a), VarValue::Empty(_)) => {
 438                 match *a {
 439                     ReLateBound(..) | ReErased => {
 440                         bug!("cannot relate region: {:?}", a);
 441                     }
 442
 443                     ReVar(v_id) => {
 444                         span_bug!(
 445                             self.var_infos[v_id].origin.span(),
 446                             "lub_concrete_regions invoked with non-concrete region: {:?}",
 447                             a
 448                         );
 449                     }
 450
 451                     ReStatic | ReEarlyBound(_) | ReFree(_) => {
 452                         // nothing lives longer than `'static`
 453
 454                         // All empty regions are less than early-bound, free,
 455                         // and scope regions.
 456
 457                         false
 458                     }
 459
 460                     RePlaceholder(_) => {
 461                         // The LUB is either `a` or `'static`
 462                         false
 463                     }
 464                 }
 465             }
 466             (VarValue::Empty(a_ui), VarValue::Value(b)) => {
 467                 match *b {
 468                     ReLateBound(..) | ReErased => {
 469                         bug!("cannot relate region: {:?}", b);
 470                     }
 471
 472                     ReVar(v_id) => {
 473                         span_bug!(
 474                             self.var_infos[v_id].origin.span(),
 475                             "lub_concrete_regions invoked with non-concrete regions: {:?}",
 476                             b
 477                         );
 478                     }
 479
 480                     ReStatic | ReEarlyBound(_) | ReFree(_) => {
 481                         // nothing lives longer than `'static`
 482                         // All empty regions are less than early-bound, free,
 483                         // and scope regions.
 484                         true
 485                     }
 486
 487                     RePlaceholder(placeholder) => {
 488                         // If this empty region is from a universe that can
 489                         // name the placeholder, then the placeholder is
 490                         // larger; otherwise, the only ancestor is `'static`.
 491                         return a_ui.can_name(placeholder.universe);
 492                     }
 493                 }
 494             }
 495             (VarValue::Value(a), VarValue::Value(b)) => self.sub_concrete_regions(a, b),
 496         }
 497     }
 498
 499     /// True if `a <= b`, but not defined over inference variables.
 500     #[instrument(level = "trace", skip(self))]
 501     fn sub_concrete_regions(&self, a: Region<'tcx>, b: Region<'tcx>) -> bool {
 502         let tcx = self.tcx();
 503         let sub_free_regions = |r1, r2| self.region_rels.free_regions.sub_free_regions(tcx, r1, r2);
 504
 505         // Check for the case where we know that `'b: 'static` -- in that case,
 506         // `a <= b` for all `a`.
 507         let b_free_or_static = b.is_free_or_static();
 508         if b_free_or_static && sub_free_regions(tcx.lifetimes.re_static, b) {
 509             return true;
 510         }
 511
 512         // If both `a` and `b` are free, consult the declared
 513         // relationships.  Note that this can be more precise than the
 514         // `lub` relationship defined below, since sometimes the "lub"
 515         // is actually the `postdom_upper_bound` (see
 516         // `TransitiveRelation` for more details).
 517         let a_free_or_static = a.is_free_or_static();
 518         if a_free_or_static && b_free_or_static {
 519             return sub_free_regions(a, b);
 520         }
 521
 522         // For other cases, leverage the LUB code to find the LUB and
 523         // check if it is equal to `b`.
 524         self.lub_concrete_regions(a, b) == b
 525     }
 526
 527     /// Returns the least-upper-bound of `a` and `b`; i.e., the
 528     /// smallest region `c` such that `a <= c` and `b <= c`.
 529     ///
 530     /// Neither `a` nor `b` may be an inference variable (hence the
 531     /// term "concrete regions").
 532     #[instrument(level = "trace", skip(self), ret)]
 533     fn lub_concrete_regions(&self, a: Region<'tcx>, b: Region<'tcx>) -> Region<'tcx> {
 534         match (*a, *b) {
 535             (ReLateBound(..), _) | (_, ReLateBound(..)) | (ReErased, _) | (_, ReErased) => {
 536                 bug!("cannot relate region: LUB({:?}, {:?})", a, b);
 537             }
 538
 539             (ReVar(v_id), _) | (_, ReVar(v_id)) => {
 540                 span_bug!(
 541                     self.var_infos[v_id].origin.span(),
 542                     "lub_concrete_regions invoked with non-concrete \
 543                      regions: {:?}, {:?}",
 544                     a,
 545                     b
 546                 );
 547             }
 548
 549             (ReStatic, _) | (_, ReStatic) => {
 550                 // nothing lives longer than `'static`
 551                 self.tcx().lifetimes.re_static
 552             }
 553
 554             (ReEarlyBound(_) | ReFree(_), ReEarlyBound(_) | ReFree(_)) => {
 555                 self.region_rels.lub_free_regions(a, b)
 556             }
 557
 558             // For these types, we cannot define any additional
 559             // relationship:
 560             (RePlaceholder(..), _) | (_, RePlaceholder(..)) => {
 561                 if a == b {
 562                     a
 563                 } else {
 564                     self.tcx().lifetimes.re_static
 565                 }
 566             }
 567         }
 568     }
 569
 570     /// After expansion is complete, go and check upper bounds (i.e.,
 571     /// cases where the region cannot grow larger than a fixed point)
 572     /// and check that they are satisfied.
 573     #[instrument(skip(self, var_data, errors))]
 574     fn collect_errors(
 575         &self,
 576         var_data: &mut LexicalRegionResolutions<'tcx>,
 577         errors: &mut Vec<RegionResolutionError<'tcx>>,
 578     ) {
 579         for (constraint, origin) in &self.data.constraints {
 580             debug!(?constraint, ?origin);
 581             match *constraint {
 582                 Constraint::RegSubVar(..) | Constraint::VarSubVar(..) => {
 583                     // Expansion will ensure that these constraints hold. Ignore.
 584                 }
 585
 586                 Constraint::RegSubReg(sub, sup) => {
 587                     if self.sub_concrete_regions(sub, sup) {
 588                         continue;
 589                     }
 590
 591                     debug!(
 592                         "region error at {:?}: \
 593                          cannot verify that {:?} <= {:?}",
 594                         origin, sub, sup
 595                     );
 596
 597                     errors.push(RegionResolutionError::ConcreteFailure(
 598                         (*origin).clone(),
 599                         sub,
 600                         sup,
 601                     ));
 602                 }
 603
 604                 Constraint::VarSubReg(a_vid, b_region) => {
 605                     let a_data = var_data.value_mut(a_vid);
 606                     debug!("contraction: {:?} == {:?}, {:?}", a_vid, a_data, b_region);
 607
 608                     let VarValue::Value(a_region) = *a_data else {
 609                         continue;
 610                     };
 611
 612                     // Do not report these errors immediately:
 613                     // instead, set the variable value to error and
 614                     // collect them later.
 615                     if !self.sub_concrete_regions(a_region, b_region) {
 616                         debug!(
 617                             "region error at {:?}: \
 618                             cannot verify that {:?}={:?} <= {:?}",
 619                             origin, a_vid, a_region, b_region
 620                         );
 621                         *a_data = VarValue::ErrorValue;
 622                     }
 623                 }
 624             }
 625         }
 626
 627         for verify in &self.data.verifys {
 628             debug!("collect_errors: verify={:?}", verify);
 629             let sub = var_data.normalize(self.tcx(), verify.region);
 630
 631             let verify_kind_ty = verify.kind.to_ty(self.tcx());
 632             let verify_kind_ty = var_data.normalize(self.tcx(), verify_kind_ty);
 633             if self.bound_is_met(&verify.bound, var_data, verify_kind_ty, sub) {
 634                 continue;
 635             }
 636
 637             debug!(
 638                 "collect_errors: region error at {:?}: \
 639                  cannot verify that {:?} <= {:?}",
 640                 verify.origin, verify.region, verify.bound
 641             );
 642
 643             errors.push(RegionResolutionError::GenericBoundFailure(
 644                 verify.origin.clone(),
 645                 verify.kind,
 646                 sub,
 647             ));
 648         }
 649     }
 650
 651     /// Go over the variables that were declared to be error variables
 652     /// and create a `RegionResolutionError` for each of them.
 653     fn collect_var_errors(
 654         &self,
 655         var_data: &LexicalRegionResolutions<'tcx>,
 656         graph: &RegionGraph<'tcx>,
 657         errors: &mut Vec<RegionResolutionError<'tcx>>,
 658     ) {
 659         debug!("collect_var_errors, var_data = {:#?}", var_data.values);
 660
 661         // This is the best way that I have found to suppress
 662         // duplicate and related errors. Basically we keep a set of
 663         // flags for every node. Whenever an error occurs, we will
 664         // walk some portion of the graph looking to find pairs of
 665         // conflicting regions to report to the user. As we walk, we
 666         // trip the flags from false to true, and if we find that
 667         // we've already reported an error involving any particular
 668         // node we just stop and don't report the current error.  The
 669         // idea is to report errors that derive from independent
 670         // regions of the graph, but not those that derive from
 671         // overlapping locations.
 672         let mut dup_vec = IndexVec::from_elem_n(None, self.num_vars());
 673
 674         for (node_vid, value) in var_data.values.iter_enumerated() {
 675             match *value {
 676                 VarValue::Empty(_) | VarValue::Value(_) => { /* Inference successful */ }
 677                 VarValue::ErrorValue => {
 678                     // Inference impossible: this value contains
 679                     // inconsistent constraints.
 680                     //
 681                     // I think that in this case we should report an
 682                     // error now -- unlike the case above, we can't
 683                     // wait to see whether the user needs the result
 684                     // of this variable. The reason is that the mere
 685                     // existence of this variable implies that the
 686                     // region graph is inconsistent, whether or not it
 687                     // is used.
 688                     //
 689                     // For example, we may have created a region
 690                     // variable that is the GLB of two other regions
 691                     // which do not have a GLB. Even if that variable
 692                     // is not used, it implies that those two regions
 693                     // *should* have a GLB.
 694                     //
 695                     // At least I think this is true. It may be that
 696                     // the mere existence of a conflict in a region
 697                     // variable that is not used is not a problem, so
 698                     // if this rule starts to create problems we'll
 699                     // have to revisit this portion of the code and
 700                     // think hard about it. =) -- nikomatsakis
 701
 702                     // Obtain the spans for all the places that can
 703                     // influence the constraints on this value for
 704                     // richer diagnostics in `static_impl_trait`.
 705
 706                     self.collect_error_for_expanding_node(graph, &mut dup_vec, node_vid, errors);
 707                 }
 708             }
 709         }
 710     }
 711
 712     fn construct_graph(&self) -> RegionGraph<'tcx> {
 713         let num_vars = self.num_vars();
 714
 715         let mut graph = Graph::new();
 716
 717         for _ in 0..num_vars {
 718             graph.add_node(());
 719         }
 720
 721         // Issue #30438: two distinct dummy nodes, one for incoming
 722         // edges (dummy_source) and another for outgoing edges
 723         // (dummy_sink). In `dummy -> a -> b -> dummy`, using one
 724         // dummy node leads one to think (erroneously) there exists a
 725         // path from `b` to `a`. Two dummy nodes sidesteps the issue.
 726         let dummy_source = graph.add_node(());
 727         let dummy_sink = graph.add_node(());
 728
 729         for constraint in self.data.constraints.keys() {
 730             match *constraint {
 731                 Constraint::VarSubVar(a_id, b_id) => {
 732                     graph.add_edge(
 733                         NodeIndex(a_id.index() as usize),
 734                         NodeIndex(b_id.index() as usize),
 735                         *constraint,
 736                     );
 737                 }
 738                 Constraint::RegSubVar(_, b_id) => {
 739                     graph.add_edge(dummy_source, NodeIndex(b_id.index() as usize), *constraint);
 740                 }
 741                 Constraint::VarSubReg(a_id, _) => {
 742                     graph.add_edge(NodeIndex(a_id.index() as usize), dummy_sink, *constraint);
 743                 }
 744                 Constraint::RegSubReg(..) => {
 745                     // this would be an edge from `dummy_source` to
 746                     // `dummy_sink`; just ignore it.
 747                 }
 748             }
 749         }
 750
 751         graph
 752     }
 753
 754     fn collect_error_for_expanding_node(
 755         &self,
 756         graph: &RegionGraph<'tcx>,
 757         dup_vec: &mut IndexVec<RegionVid, Option<RegionVid>>,
 758         node_idx: RegionVid,
 759         errors: &mut Vec<RegionResolutionError<'tcx>>,
 760     ) {
 761         // Errors in expanding nodes result from a lower-bound that is
 762         // not contained by an upper-bound.
 763         let (mut lower_bounds, lower_vid_bounds, lower_dup) =
 764             self.collect_bounding_regions(graph, node_idx, INCOMING, Some(dup_vec));
 765         let (mut upper_bounds, _, upper_dup) =
 766             self.collect_bounding_regions(graph, node_idx, OUTGOING, Some(dup_vec));
 767
 768         if lower_dup || upper_dup {
 769             return;
 770         }
 771
 772         // We place free regions first because we are special casing
 773         // SubSupConflict(ReFree, ReFree) when reporting error, and so
 774         // the user will more likely get a specific suggestion.
 775         fn region_order_key(x: &RegionAndOrigin<'_>) -> u8 {
 776             match *x.region {
 777                 ReEarlyBound(_) => 0,
 778                 ReFree(_) => 1,
 779                 _ => 2,
 780             }
 781         }
 782         lower_bounds.sort_by_key(region_order_key);
 783         upper_bounds.sort_by_key(region_order_key);
 784
 785         let node_universe = self.var_infos[node_idx].universe;
 786
 787         for lower_bound in &lower_bounds {
 788             let effective_lower_bound = if let ty::RePlaceholder(p) = *lower_bound.region {
 789                 if node_universe.cannot_name(p.universe) {
 790                     self.tcx().lifetimes.re_static
 791                 } else {
 792                     lower_bound.region
 793                 }
 794             } else {
 795                 lower_bound.region
 796             };
 797
 798             for upper_bound in &upper_bounds {
 799                 if !self.sub_concrete_regions(effective_lower_bound, upper_bound.region) {
 800                     let origin = self.var_infos[node_idx].origin;
 801                     debug!(
 802                         "region inference error at {:?} for {:?}: SubSupConflict sub: {:?} \
 803                          sup: {:?}",
 804                         origin, node_idx, lower_bound.region, upper_bound.region
 805                     );
 806
 807                     errors.push(RegionResolutionError::SubSupConflict(
 808                         node_idx,
 809                         origin,
 810                         lower_bound.origin.clone(),
 811                         lower_bound.region,
 812                         upper_bound.origin.clone(),
 813                         upper_bound.region,
 814                         vec![],
 815                     ));
 816                     return;
 817                 }
 818             }
 819         }
 820
 821         // If we have a scenario like `exists<'a> { forall<'b> { 'b:
 822         // 'a } }`, we wind up without any lower-bound -- all we have
 823         // are placeholders as upper bounds, but the universe of the
 824         // variable `'a`, or some variable that `'a` has to outlive, doesn't
 825         // permit those placeholders.
 826         //
 827         // We only iterate to find the min, which means it doesn't cause reproducibility issues
 828         #[allow(rustc::potential_query_instability)]
 829         let min_universe = lower_vid_bounds
 830             .into_iter()
 831             .map(|vid| self.var_infos[vid].universe)
 832             .min()
 833             .expect("lower_vid_bounds should at least include `node_idx`");
 834
 835         for upper_bound in &upper_bounds {
 836             if let ty::RePlaceholder(p) = *upper_bound.region {
 837                 if min_universe.cannot_name(p.universe) {
 838                     let origin = self.var_infos[node_idx].origin;
 839                     errors.push(RegionResolutionError::UpperBoundUniverseConflict(
 840                         node_idx,
 841                         origin,
 842                         min_universe,
 843                         upper_bound.origin.clone(),
 844                         upper_bound.region,
 845                     ));
 846                     return;
 847                 }
 848             }
 849         }
 850
 851         // Errors in earlier passes can yield error variables without
 852         // resolution errors here; delay ICE in favor of those errors.
 853         self.tcx().sess.delay_span_bug(
 854             self.var_infos[node_idx].origin.span(),
 855             &format!(
 856                 "collect_error_for_expanding_node() could not find \
 857                  error for var {:?} in universe {:?}, lower_bounds={:#?}, \
 858                  upper_bounds={:#?}",
 859                 node_idx, node_universe, lower_bounds, upper_bounds
 860             ),
 861         );
 862     }
 863
 864     /// Collects all regions that "bound" the variable `orig_node_idx` in the
 865     /// given direction.
 866     ///
 867     /// If `dup_vec` is `Some` it's used to track duplicates between successive
 868     /// calls of this function.
 869     ///
 870     /// The return tuple fields are:
 871     /// - a list of all concrete regions bounding the given region.
 872     /// - the set of all region variables bounding the given region.
 873     /// - a `bool` that's true if the returned region variables overlap with
 874     ///   those returned by a previous call for another region.
 875     fn collect_bounding_regions(
 876         &self,
 877         graph: &RegionGraph<'tcx>,
 878         orig_node_idx: RegionVid,
 879         dir: Direction,
 880         mut dup_vec: Option<&mut IndexVec<RegionVid, Option<RegionVid>>>,
 881     ) -> (Vec<RegionAndOrigin<'tcx>>, FxHashSet<RegionVid>, bool) {
 882         struct WalkState<'tcx> {
 883             set: FxHashSet<RegionVid>,
 884             stack: Vec<RegionVid>,
 885             result: Vec<RegionAndOrigin<'tcx>>,
 886             dup_found: bool,
 887         }
 888         let mut state = WalkState {
 889             set: Default::default(),
 890             stack: vec![orig_node_idx],
 891             result: Vec::new(),
 892             dup_found: false,
 893         };
 894         state.set.insert(orig_node_idx);
 895
 896         // to start off the process, walk the source node in the
 897         // direction specified
 898         process_edges(&self.data, &mut state, graph, orig_node_idx, dir);
 899
 900         while let Some(node_idx) = state.stack.pop() {
 901             // check whether we've visited this node on some previous walk
 902             if let Some(dup_vec) = &mut dup_vec {
 903                 if dup_vec[node_idx].is_none() {
 904                     dup_vec[node_idx] = Some(orig_node_idx);
 905                 } else if dup_vec[node_idx] != Some(orig_node_idx) {
 906                     state.dup_found = true;
 907                 }
 908
 909                 debug!(
 910                     "collect_concrete_regions(orig_node_idx={:?}, node_idx={:?})",
 911                     orig_node_idx, node_idx
 912                 );
 913             }
 914
 915             process_edges(&self.data, &mut state, graph, node_idx, dir);
 916         }
 917
 918         let WalkState { result, dup_found, set, .. } = state;
 919         return (result, set, dup_found);
 920
 921         fn process_edges<'tcx>(
 922             this: &RegionConstraintData<'tcx>,
 923             state: &mut WalkState<'tcx>,
 924             graph: &RegionGraph<'tcx>,
 925             source_vid: RegionVid,
 926             dir: Direction,
 927         ) {
 928             debug!("process_edges(source_vid={:?}, dir={:?})", source_vid, dir);
 929
 930             let source_node_index = NodeIndex(source_vid.index() as usize);
 931             for (_, edge) in graph.adjacent_edges(source_node_index, dir) {
 932                 match edge.data {
 933                     Constraint::VarSubVar(from_vid, to_vid) => {
 934                         let opp_vid = if from_vid == source_vid { to_vid } else { from_vid };
 935                         if state.set.insert(opp_vid) {
 936                             state.stack.push(opp_vid);
 937                         }
 938                     }
 939
 940                     Constraint::RegSubVar(region, _) | Constraint::VarSubReg(_, region) => {
 941                         state.result.push(RegionAndOrigin {
 942                             region,
 943                             origin: this.constraints.get(&edge.data).unwrap().clone(),
 944                         });
 945                     }
 946
 947                     Constraint::RegSubReg(..) => panic!(
 948                         "cannot reach reg-sub-reg edge in region inference \
 949                          post-processing"
 950                     ),
 951                 }
 952             }
 953         }
 954     }
 955
 956     fn bound_is_met(
 957         &self,
 958         bound: &VerifyBound<'tcx>,
 959         var_values: &LexicalRegionResolutions<'tcx>,
 960         generic_ty: Ty<'tcx>,
 961         min: ty::Region<'tcx>,
 962     ) -> bool {
 963         match bound {
 964             VerifyBound::IfEq(verify_if_eq_b) => {
 965                 let verify_if_eq_b = var_values.normalize(self.region_rels.tcx, *verify_if_eq_b);
 966                 match test_type_match::extract_verify_if_eq(
 967                     self.tcx(),
 968                     self.param_env,
 969                     &verify_if_eq_b,
 970                     generic_ty,
 971                 ) {
 972                     Some(r) => {
 973                         self.bound_is_met(&VerifyBound::OutlivedBy(r), var_values, generic_ty, min)
 974                     }
 975
 976                     None => false,
 977                 }
 978             }
 979
 980             VerifyBound::OutlivedBy(r) => {
 981                 let a = match *min {
 982                     ty::ReVar(rid) => var_values.values[rid],
 983                     _ => VarValue::Value(min),
 984                 };
 985                 let b = match **r {
 986                     ty::ReVar(rid) => var_values.values[rid],
 987                     _ => VarValue::Value(*r),
 988                 };
 989                 self.sub_region_values(a, b)
 990             }
 991
 992             VerifyBound::IsEmpty => match *min {
 993                 ty::ReVar(rid) => match var_values.values[rid] {
 994                     VarValue::ErrorValue => false,
 995                     VarValue::Empty(_) => true,
 996                     VarValue::Value(_) => false,
 997                 },
 998                 _ => false,
 999             },
1000
1001             VerifyBound::AnyBound(bs) => {
1002                 bs.iter().any(|b| self.bound_is_met(b, var_values, generic_ty, min))
1003             }
1004
1005             VerifyBound::AllBounds(bs) => {
1006                 bs.iter().all(|b| self.bound_is_met(b, var_values, generic_ty, min))
1007             }
1008         }
1009     }
1010 }
1011
1012 impl<'tcx> fmt::Debug for RegionAndOrigin<'tcx> {
1013     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1014         write!(f, "RegionAndOrigin({:?},{:?})", self.region, self.origin)
1015     }
1016 }
1017
1018 impl<'tcx> LexicalRegionResolutions<'tcx> {
1019     fn normalize<T>(&self, tcx: TyCtxt<'tcx>, value: T) -> T
1020     where
1021         T: TypeFoldable<'tcx>,
1022     {
1023         tcx.fold_regions(value, |r, _db| self.resolve_region(tcx, r))
1024     }
1025
1026     fn value(&self, rid: RegionVid) -> &VarValue<'tcx> {
1027         &self.values[rid]
1028     }
1029
1030     fn value_mut(&mut self, rid: RegionVid) -> &mut VarValue<'tcx> {
1031         &mut self.values[rid]
1032     }
1033
1034     pub(crate) fn resolve_region(
1035         &self,
1036         tcx: TyCtxt<'tcx>,
1037         r: ty::Region<'tcx>,
1038     ) -> ty::Region<'tcx> {
1039         let result = match *r {
1040             ty::ReVar(rid) => match self.values[rid] {
1041                 VarValue::Empty(_) => r,
1042                 VarValue::Value(r) => r,
1043                 VarValue::ErrorValue => tcx.lifetimes.re_static,
1044             },
1045             _ => r,
1046         };
1047         debug!("resolve_region({:?}) = {:?}", r, result);
1048         result
1049     }
1050 }