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