src/librustc/infer/lexical_region_resolve/mod.rs

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