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