compiler/rustc_middle/src/ty/visit.rs

   1 use crate::ty::{self, Binder, Ty, TyCtxt, TypeFlags};
   2
   3 use rustc_data_structures::fx::FxHashSet;
   4 use rustc_data_structures::sso::SsoHashSet;
   5 use rustc_type_ir::fold::TypeFoldable;
   6 use std::ops::ControlFlow;
   7
   8 pub use rustc_type_ir::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor};
   9
  10 ///////////////////////////////////////////////////////////////////////////
  11 // Region folder
  12
  13 impl<'tcx> TyCtxt<'tcx> {
  14     /// Invoke `callback` on every region appearing free in `value`.
  15     pub fn for_each_free_region(
  16         self,
  17         value: &impl TypeVisitable<TyCtxt<'tcx>>,
  18         mut callback: impl FnMut(ty::Region<'tcx>),
  19     ) {
  20         self.any_free_region_meets(value, |r| {
  21             callback(r);
  22             false
  23         });
  24     }
  25
  26     /// Returns `true` if `callback` returns true for every region appearing free in `value`.
  27     pub fn all_free_regions_meet(
  28         self,
  29         value: &impl TypeVisitable<TyCtxt<'tcx>>,
  30         mut callback: impl FnMut(ty::Region<'tcx>) -> bool,
  31     ) -> bool {
  32         !self.any_free_region_meets(value, |r| !callback(r))
  33     }
  34
  35     /// Returns `true` if `callback` returns true for some region appearing free in `value`.
  36     pub fn any_free_region_meets(
  37         self,
  38         value: &impl TypeVisitable<TyCtxt<'tcx>>,
  39         callback: impl FnMut(ty::Region<'tcx>) -> bool,
  40     ) -> bool {
  41         struct RegionVisitor<F> {
  42             /// The index of a binder *just outside* the things we have
  43             /// traversed. If we encounter a bound region bound by this
  44             /// binder or one outer to it, it appears free. Example:
  45             ///
  46             /// ```ignore (illustrative)
  47             ///       for<'a> fn(for<'b> fn(), T)
  48             /// // ^          ^          ^     ^
  49             /// // |          |          |     | here, would be shifted in 1
  50             /// // |          |          | here, would be shifted in 2
  51             /// // |          | here, would be `INNERMOST` shifted in by 1
  52             /// // | here, initially, binder would be `INNERMOST`
  53             /// ```
  54             ///
  55             /// You see that, initially, *any* bound value is free,
  56             /// because we've not traversed any binders. As we pass
  57             /// through a binder, we shift the `outer_index` by 1 to
  58             /// account for the new binder that encloses us.
  59             outer_index: ty::DebruijnIndex,
  60             callback: F,
  61         }
  62
  63         impl<'tcx, F> TypeVisitor<TyCtxt<'tcx>> for RegionVisitor<F>
  64         where
  65             F: FnMut(ty::Region<'tcx>) -> bool,
  66         {
  67             type Result = ControlFlow<()>;
  68
  69             fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(
  70                 &mut self,
  71                 t: &Binder<'tcx, T>,
  72             ) -> Self::Result {
  73                 self.outer_index.shift_in(1);
  74                 let result = t.super_visit_with(self);
  75                 self.outer_index.shift_out(1);
  76                 result
  77             }
  78
  79             fn visit_region(&mut self, r: ty::Region<'tcx>) -> Self::Result {
  80                 match *r {
  81                     ty::ReBound(debruijn, _) if debruijn < self.outer_index => {
  82                         ControlFlow::Continue(())
  83                     }
  84                     _ => {
  85                         if (self.callback)(r) {
  86                             ControlFlow::Break(())
  87                         } else {
  88                             ControlFlow::Continue(())
  89                         }
  90                     }
  91                 }
  92             }
  93
  94             fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
  95                 // We're only interested in types involving regions
  96                 if ty.flags().intersects(TypeFlags::HAS_FREE_REGIONS) {
  97                     ty.super_visit_with(self)
  98                 } else {
  99                     ControlFlow::Continue(())
 100                 }
 101             }
 102         }
 103
 104         value.visit_with(&mut RegionVisitor { outer_index: ty::INNERMOST, callback }).is_break()
 105     }
 106
 107     /// Returns a set of all late-bound regions that are constrained
 108     /// by `value`, meaning that if we instantiate those LBR with
 109     /// variables and equate `value` with something else, those
 110     /// variables will also be equated.
 111     pub fn collect_constrained_late_bound_regions<T>(
 112         self,
 113         value: Binder<'tcx, T>,
 114     ) -> FxHashSet<ty::BoundRegionKind>
 115     where
 116         T: TypeFoldable<TyCtxt<'tcx>>,
 117     {
 118         self.collect_late_bound_regions(value, true)
 119     }
 120
 121     /// Returns a set of all late-bound regions that appear in `value` anywhere.
 122     pub fn collect_referenced_late_bound_regions<T>(
 123         self,
 124         value: Binder<'tcx, T>,
 125     ) -> FxHashSet<ty::BoundRegionKind>
 126     where
 127         T: TypeFoldable<TyCtxt<'tcx>>,
 128     {
 129         self.collect_late_bound_regions(value, false)
 130     }
 131
 132     fn collect_late_bound_regions<T>(
 133         self,
 134         value: Binder<'tcx, T>,
 135         just_constrained: bool,
 136     ) -> FxHashSet<ty::BoundRegionKind>
 137     where
 138         T: TypeFoldable<TyCtxt<'tcx>>,
 139     {
 140         let mut collector = LateBoundRegionsCollector::new(just_constrained);
 141         let value = value.skip_binder();
 142         let value = if just_constrained { self.expand_weak_alias_tys(value) } else { value };
 143         value.visit_with(&mut collector);
 144         collector.regions
 145     }
 146 }
 147
 148 pub struct ValidateBoundVars<'tcx> {
 149     bound_vars: &'tcx ty::List<ty::BoundVariableKind>,
 150     binder_index: ty::DebruijnIndex,
 151     // We may encounter the same variable at different levels of binding, so
 152     // this can't just be `Ty`
 153     visited: SsoHashSet<(ty::DebruijnIndex, Ty<'tcx>)>,
 154 }
 155
 156 impl<'tcx> ValidateBoundVars<'tcx> {
 157     pub fn new(bound_vars: &'tcx ty::List<ty::BoundVariableKind>) -> Self {
 158         ValidateBoundVars {
 159             bound_vars,
 160             binder_index: ty::INNERMOST,
 161             visited: SsoHashSet::default(),
 162         }
 163     }
 164 }
 165
 166 impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ValidateBoundVars<'tcx> {
 167     type Result = ControlFlow<()>;
 168
 169     fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(
 170         &mut self,
 171         t: &Binder<'tcx, T>,
 172     ) -> Self::Result {
 173         self.binder_index.shift_in(1);
 174         let result = t.super_visit_with(self);
 175         self.binder_index.shift_out(1);
 176         result
 177     }
 178
 179     fn visit_ty(&mut self, t: Ty<'tcx>) -> Self::Result {
 180         if t.outer_exclusive_binder() < self.binder_index
 181             || !self.visited.insert((self.binder_index, t))
 182         {
 183             return ControlFlow::Break(());
 184         }
 185         match *t.kind() {
 186             ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
 187                 if self.bound_vars.len() <= bound_ty.var.as_usize() {
 188                     bug!("Not enough bound vars: {:?} not found in {:?}", t, self.bound_vars);
 189                 }
 190                 let list_var = self.bound_vars[bound_ty.var.as_usize()];
 191                 match list_var {
 192                     ty::BoundVariableKind::Ty(kind) => {
 193                         if kind != bound_ty.kind {
 194                             bug!(
 195                                 "Mismatched type kinds: {:?} doesn't var in list {:?}",
 196                                 bound_ty.kind,
 197                                 list_var
 198                             );
 199                         }
 200                     }
 201                     _ => {
 202                         bug!("Mismatched bound variable kinds! Expected type, found {:?}", list_var)
 203                     }
 204                 }
 205             }
 206
 207             _ => (),
 208         };
 209
 210         t.super_visit_with(self)
 211     }
 212
 213     fn visit_region(&mut self, r: ty::Region<'tcx>) -> Self::Result {
 214         match *r {
 215             ty::ReBound(index, br) if index == self.binder_index => {
 216                 if self.bound_vars.len() <= br.var.as_usize() {
 217                     bug!("Not enough bound vars: {:?} not found in {:?}", br, self.bound_vars);
 218                 }
 219                 let list_var = self.bound_vars[br.var.as_usize()];
 220                 match list_var {
 221                     ty::BoundVariableKind::Region(kind) => {
 222                         if kind != br.kind {
 223                             bug!(
 224                                 "Mismatched region kinds: {:?} doesn't match var ({:?}) in list ({:?})",
 225                                 br.kind,
 226                                 list_var,
 227                                 self.bound_vars
 228                             );
 229                         }
 230                     }
 231                     _ => bug!(
 232                         "Mismatched bound variable kinds! Expected region, found {:?}",
 233                         list_var
 234                     ),
 235                 }
 236             }
 237
 238             _ => (),
 239         };
 240
 241         ControlFlow::Continue(())
 242     }
 243 }
 244
 245 /// Collects all the late-bound regions at the innermost binding level
 246 /// into a hash set.
 247 struct LateBoundRegionsCollector {
 248     current_index: ty::DebruijnIndex,
 249     regions: FxHashSet<ty::BoundRegionKind>,
 250
 251     /// `true` if we only want regions that are known to be
 252     /// "constrained" when you equate this type with another type. In
 253     /// particular, if you have e.g., `&'a u32` and `&'b u32`, equating
 254     /// them constraints `'a == 'b`. But if you have `<&'a u32 as
 255     /// Trait>::Foo` and `<&'b u32 as Trait>::Foo`, normalizing those
 256     /// types may mean that `'a` and `'b` don't appear in the results,
 257     /// so they are not considered *constrained*.
 258     just_constrained: bool,
 259 }
 260
 261 impl LateBoundRegionsCollector {
 262     fn new(just_constrained: bool) -> Self {
 263         Self { current_index: ty::INNERMOST, regions: Default::default(), just_constrained }
 264     }
 265 }
 266
 267 impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for LateBoundRegionsCollector {
 268     fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, t: &Binder<'tcx, T>) {
 269         self.current_index.shift_in(1);
 270         t.super_visit_with(self);
 271         self.current_index.shift_out(1);
 272     }
 273
 274     fn visit_ty(&mut self, t: Ty<'tcx>) {
 275         if self.just_constrained {
 276             match t.kind() {
 277                 // If we are only looking for "constrained" regions, we have to ignore the
 278                 // inputs to a projection as they may not appear in the normalized form.
 279                 ty::Alias(ty::Projection | ty::Inherent | ty::Opaque, _) => {
 280                     return;
 281                 }
 282                 // All weak alias types should've been expanded beforehand.
 283                 ty::Alias(ty::Weak, _) => bug!("unexpected weak alias type"),
 284                 _ => {}
 285             }
 286         }
 287
 288         t.super_visit_with(self)
 289     }
 290
 291     fn visit_const(&mut self, c: ty::Const<'tcx>) {
 292         // if we are only looking for "constrained" region, we have to
 293         // ignore the inputs of an unevaluated const, as they may not appear
 294         // in the normalized form
 295         if self.just_constrained {
 296             if let ty::ConstKind::Unevaluated(..) = c.kind() {
 297                 return;
 298             }
 299         }
 300
 301         c.super_visit_with(self)
 302     }
 303
 304     fn visit_region(&mut self, r: ty::Region<'tcx>) {
 305         if let ty::ReBound(debruijn, br) = *r {
 306             if debruijn == self.current_index {
 307                 self.regions.insert(br.kind);
 308             }
 309         }
 310     }
 311 }
 312
 313 /// Finds the max universe present
 314 pub struct MaxUniverse {
 315     max_universe: ty::UniverseIndex,
 316 }
 317
 318 impl MaxUniverse {
 319     pub fn new() -> Self {
 320         MaxUniverse { max_universe: ty::UniverseIndex::ROOT }
 321     }
 322
 323     pub fn max_universe(self) -> ty::UniverseIndex {
 324         self.max_universe
 325     }
 326 }
 327
 328 impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for MaxUniverse {
 329     fn visit_ty(&mut self, t: Ty<'tcx>) {
 330         if let ty::Placeholder(placeholder) = t.kind() {
 331             self.max_universe = ty::UniverseIndex::from_u32(
 332                 self.max_universe.as_u32().max(placeholder.universe.as_u32()),
 333             );
 334         }
 335
 336         t.super_visit_with(self)
 337     }
 338
 339     fn visit_const(&mut self, c: ty::consts::Const<'tcx>) {
 340         if let ty::ConstKind::Placeholder(placeholder) = c.kind() {
 341             self.max_universe = ty::UniverseIndex::from_u32(
 342                 self.max_universe.as_u32().max(placeholder.universe.as_u32()),
 343             );
 344         }
 345
 346         c.super_visit_with(self)
 347     }
 348
 349     fn visit_region(&mut self, r: ty::Region<'tcx>) {
 350         if let ty::RePlaceholder(placeholder) = *r {
 351             self.max_universe = ty::UniverseIndex::from_u32(
 352                 self.max_universe.as_u32().max(placeholder.universe.as_u32()),
 353             );
 354         }
 355     }
 356 }