src/librustc/infer/lexical_region_resolve/mod.rs

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