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