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