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