src/librustc/infer/lexical_region_resolve/mod.rs

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