rustc_middle/ty/
visit.rs

Help
1use std::ops::ControlFlow;
2
3use rustc_data_structures::fx::FxIndexSet;
4use rustc_type_ir::TypeFoldable;
5
6use crate::ty::{
7    self, Binder, Ty, TyCtxt, TypeFlags, TypeSuperVisitable, TypeVisitable, TypeVisitor,
8};
9
10///////////////////////////////////////////////////////////////////////////
11// Region folder
12
13impl<'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    ) -> FxIndexSet<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    ) -> FxIndexSet<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    ) -> FxIndexSet<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/// Collects all the late-bound regions at the innermost binding level
149/// into a hash set.
150struct LateBoundRegionsCollector {
151    current_index: ty::DebruijnIndex,
152    regions: FxIndexSet<ty::BoundRegionKind>,
153
154    /// `true` if we only want regions that are known to be
155    /// "constrained" when you equate this type with another type. In
156    /// particular, if you have e.g., `&'a u32` and `&'b u32`, equating
157    /// them constraints `'a == 'b`. But if you have `<&'a u32 as
158    /// Trait>::Foo` and `<&'b u32 as Trait>::Foo`, normalizing those
159    /// types may mean that `'a` and `'b` don't appear in the results,
160    /// so they are not considered *constrained*.
161    just_constrained: bool,
162}
163
164impl LateBoundRegionsCollector {
165    fn new(just_constrained: bool) -> Self {
166        Self { current_index: ty::INNERMOST, regions: Default::default(), just_constrained }
167    }
168}
169
170impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for LateBoundRegionsCollector {
171    fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, t: &Binder<'tcx, T>) {
172        self.current_index.shift_in(1);
173        t.super_visit_with(self);
174        self.current_index.shift_out(1);
175    }
176
177    fn visit_ty(&mut self, t: Ty<'tcx>) {
178        if self.just_constrained {
179            match t.kind() {
180                // If we are only looking for "constrained" regions, we have to ignore the
181                // inputs to a projection as they may not appear in the normalized form.
182                ty::Alias(ty::Projection | ty::Inherent | ty::Opaque, _) => {
183                    return;
184                }
185                // All weak alias types should've been expanded beforehand.
186                ty::Alias(ty::Weak, _) => bug!("unexpected weak alias type"),
187                _ => {}
188            }
189        }
190
191        t.super_visit_with(self)
192    }
193
194    fn visit_const(&mut self, c: ty::Const<'tcx>) {
195        // if we are only looking for "constrained" region, we have to
196        // ignore the inputs of an unevaluated const, as they may not appear
197        // in the normalized form
198        if self.just_constrained {
199            if let ty::ConstKind::Unevaluated(..) = c.kind() {
200                return;
201            }
202        }
203
204        c.super_visit_with(self)
205    }
206
207    fn visit_region(&mut self, r: ty::Region<'tcx>) {
208        if let ty::ReBound(debruijn, br) = *r {
209            if debruijn == self.current_index {
210                self.regions.insert(br.kind);
211            }
212        }
213    }
214}
215
216/// Finds the max universe present
217pub struct MaxUniverse {
218    max_universe: ty::UniverseIndex,
219}
220
221impl MaxUniverse {
222    pub fn new() -> Self {
223        MaxUniverse { max_universe: ty::UniverseIndex::ROOT }
224    }
225
226    pub fn max_universe(self) -> ty::UniverseIndex {
227        self.max_universe
228    }
229}
230
231impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for MaxUniverse {
232    fn visit_ty(&mut self, t: Ty<'tcx>) {
233        if let ty::Placeholder(placeholder) = t.kind() {
234            self.max_universe = ty::UniverseIndex::from_u32(
235                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
236            );
237        }
238
239        t.super_visit_with(self)
240    }
241
242    fn visit_const(&mut self, c: ty::consts::Const<'tcx>) {
243        if let ty::ConstKind::Placeholder(placeholder) = c.kind() {
244            self.max_universe = ty::UniverseIndex::from_u32(
245                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
246            );
247        }
248
249        c.super_visit_with(self)
250    }
251
252    fn visit_region(&mut self, r: ty::Region<'tcx>) {
253        if let ty::RePlaceholder(placeholder) = *r {
254            self.max_universe = ty::UniverseIndex::from_u32(
255                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
256            );
257        }
258    }
259}
rustc_middle/ty/visit.rs

rustc_middle/ty/
visit.rs
