rustc_type_ir/
visit.rs

1//! A visiting traversal mechanism for complex data structures that contain type
2//! information.
3//!
4//! This is a read-only traversal of the data structure.
5//!
6//! This traversal has limited flexibility. Only a small number of "types of
7//! interest" within the complex data structures can receive custom
8//! visitation. These are the ones containing the most important type-related
9//! information, such as `Ty`, `Predicate`, `Region`, and `Const`.
10//!
11//! There are three traits involved in each traversal.
12//! - `TypeVisitable`. This is implemented once for many types, including:
13//!   - Types of interest, for which the methods delegate to the visitor.
14//!   - All other types, including generic containers like `Vec` and `Option`.
15//!     It defines a "skeleton" of how they should be visited.
16//! - `TypeSuperVisitable`. This is implemented only for recursive types of
17//!   interest, and defines the visiting "skeleton" for these types. (This
18//!   excludes `Region` because it is non-recursive, i.e. it never contains
19//!   other types of interest.)
20//! - `TypeVisitor`. This is implemented for each visitor. This defines how
21//!   types of interest are visited.
22//!
23//! This means each visit is a mixture of (a) generic visiting operations, and (b)
24//! custom visit operations that are specific to the visitor.
25//! - The `TypeVisitable` impls handle most of the traversal, and call into
26//!   `TypeVisitor` when they encounter a type of interest.
27//! - A `TypeVisitor` may call into another `TypeVisitable` impl, because some of
28//!   the types of interest are recursive and can contain other types of interest.
29//! - A `TypeVisitor` may also call into a `TypeSuperVisitable` impl, because each
30//!   visitor might provide custom handling only for some types of interest, or
31//!   only for some variants of each type of interest, and then use default
32//!   traversal for the remaining cases.
33//!
34//! For example, if you have `struct S(Ty, U)` where `S: TypeVisitable` and `U:
35//! TypeVisitable`, and an instance `s = S(ty, u)`, it would be visited like so:
36//! ```text
37//! s.visit_with(visitor) calls
38//! - ty.visit_with(visitor) calls
39//!   - visitor.visit_ty(ty) may call
40//!     - ty.super_visit_with(visitor)
41//! - u.visit_with(visitor)
42//! ```
43
44use std::fmt;
45use std::ops::ControlFlow;
46use std::sync::Arc;
47
48pub use rustc_ast_ir::visit::VisitorResult;
49pub use rustc_ast_ir::{try_visit, walk_visitable_list};
50use rustc_index::{Idx, IndexVec};
51use smallvec::SmallVec;
52use thin_vec::ThinVec;
53
54use crate::inherent::*;
55use crate::{self as ty, Interner, TypeFlags};
56
57/// This trait is implemented for every type that can be visited,
58/// providing the skeleton of the traversal.
59///
60/// To implement this conveniently, use the derive macro located in
61/// `rustc_macros`.
62pub trait TypeVisitable<I: Interner>: fmt::Debug {
63    /// The entry point for visiting. To visit a value `t` with a visitor `v`
64    /// call: `t.visit_with(v)`.
65    ///
66    /// For most types, this just traverses the value, calling `visit_with` on
67    /// each field/element.
68    ///
69    /// For types of interest (such as `Ty`), the implementation of this method
70    /// that calls a visitor method specifically for that type (such as
71    /// `V::visit_ty`). This is where control transfers from `TypeVisitable` to
72    /// `TypeVisitor`.
73    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result;
74}
75
76// This trait is implemented for types of interest.
77pub trait TypeSuperVisitable<I: Interner>: TypeVisitable<I> {
78    /// Provides a default visit for a recursive type of interest. This should
79    /// only be called within `TypeVisitor` methods, when a non-custom
80    /// traversal is desired for the value of the type of interest passed to
81    /// that method. For example, in `MyVisitor::visit_ty(ty)`, it is valid to
82    /// call `ty.super_visit_with(self)`, but any other visiting should be done
83    /// with `xyz.visit_with(self)`.
84    fn super_visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result;
85}
86
87/// This trait is implemented for every visiting traversal. There is a visit
88/// method defined for every type of interest. Each such method has a default
89/// that recurses into the type's fields in a non-custom fashion.
90pub trait TypeVisitor<I: Interner>: Sized {
91    #[cfg(feature = "nightly")]
92    type Result: VisitorResult = ();
93
94    #[cfg(not(feature = "nightly"))]
95    type Result: VisitorResult;
96
97    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
98        t.super_visit_with(self)
99    }
100
101    fn visit_ty(&mut self, t: I::Ty) -> Self::Result {
102        t.super_visit_with(self)
103    }
104
105    // The default region visitor is a no-op because `Region` is non-recursive
106    // and has no `super_visit_with` method to call.
107    fn visit_region(&mut self, r: I::Region) -> Self::Result {
108        if let ty::ReError(guar) = r.kind() {
109            self.visit_error(guar)
110        } else {
111            Self::Result::output()
112        }
113    }
114
115    fn visit_const(&mut self, c: I::Const) -> Self::Result {
116        c.super_visit_with(self)
117    }
118
119    fn visit_predicate(&mut self, p: I::Predicate) -> Self::Result {
120        p.super_visit_with(self)
121    }
122
123    fn visit_clauses(&mut self, p: I::Clauses) -> Self::Result {
124        p.super_visit_with(self)
125    }
126
127    fn visit_error(&mut self, _guar: I::ErrorGuaranteed) -> Self::Result {
128        Self::Result::output()
129    }
130}
131
132///////////////////////////////////////////////////////////////////////////
133// Traversal implementations.
134
135impl<I: Interner, T: TypeVisitable<I>, U: TypeVisitable<I>> TypeVisitable<I> for (T, U) {
136    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
137        try_visit!(self.0.visit_with(visitor));
138        self.1.visit_with(visitor)
139    }
140}
141
142impl<I: Interner, A: TypeVisitable<I>, B: TypeVisitable<I>, C: TypeVisitable<I>> TypeVisitable<I>
143    for (A, B, C)
144{
145    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
146        try_visit!(self.0.visit_with(visitor));
147        try_visit!(self.1.visit_with(visitor));
148        self.2.visit_with(visitor)
149    }
150}
151
152impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Option<T> {
153    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
154        match self {
155            Some(v) => v.visit_with(visitor),
156            None => V::Result::output(),
157        }
158    }
159}
160
161impl<I: Interner, T: TypeVisitable<I>, E: TypeVisitable<I>> TypeVisitable<I> for Result<T, E> {
162    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
163        match self {
164            Ok(v) => v.visit_with(visitor),
165            Err(e) => e.visit_with(visitor),
166        }
167    }
168}
169
170impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Arc<T> {
171    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
172        (**self).visit_with(visitor)
173    }
174}
175
176impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Box<T> {
177    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
178        (**self).visit_with(visitor)
179    }
180}
181
182impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Vec<T> {
183    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
184        walk_visitable_list!(visitor, self.iter());
185        V::Result::output()
186    }
187}
188
189impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for ThinVec<T> {
190    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
191        walk_visitable_list!(visitor, self.iter());
192        V::Result::output()
193    }
194}
195
196impl<I: Interner, T: TypeVisitable<I>, const N: usize> TypeVisitable<I> for SmallVec<[T; N]> {
197    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
198        walk_visitable_list!(visitor, self.iter());
199        V::Result::output()
200    }
201}
202
203// `TypeFoldable` isn't impl'd for `&[T]`. It doesn't make sense in the general
204// case, because we can't return a new slice. But note that there are a couple
205// of trivial impls of `TypeFoldable` for specific slice types elsewhere.
206impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for &[T] {
207    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
208        walk_visitable_list!(visitor, self.iter());
209        V::Result::output()
210    }
211}
212
213impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Box<[T]> {
214    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
215        walk_visitable_list!(visitor, self.iter());
216        V::Result::output()
217    }
218}
219
220impl<I: Interner, T: TypeVisitable<I>, Ix: Idx> TypeVisitable<I> for IndexVec<Ix, T> {
221    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
222        walk_visitable_list!(visitor, self.iter());
223        V::Result::output()
224    }
225}
226
227impl<I: Interner, T: TypeVisitable<I>, S> TypeVisitable<I> for indexmap::IndexSet<T, S> {
228    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
229        walk_visitable_list!(visitor, self.iter());
230        V::Result::output()
231    }
232}
233
234pub trait Flags {
235    fn flags(&self) -> TypeFlags;
236    fn outer_exclusive_binder(&self) -> ty::DebruijnIndex;
237}
238
239pub trait TypeVisitableExt<I: Interner>: TypeVisitable<I> {
240    fn has_type_flags(&self, flags: TypeFlags) -> bool;
241
242    /// Returns `true` if `self` has any late-bound regions that are either
243    /// bound by `binder` or bound by some binder outside of `binder`.
244    /// If `binder` is `ty::INNERMOST`, this indicates whether
245    /// there are any late-bound regions that appear free.
246    fn has_vars_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool;
247
248    /// Returns `true` if this type has any regions that escape `binder` (and
249    /// hence are not bound by it).
250    fn has_vars_bound_above(&self, binder: ty::DebruijnIndex) -> bool {
251        self.has_vars_bound_at_or_above(binder.shifted_in(1))
252    }
253
254    /// Return `true` if this type has regions that are not a part of the type.
255    /// For example, `for<'a> fn(&'a i32)` return `false`, while `fn(&'a i32)`
256    /// would return `true`. The latter can occur when traversing through the
257    /// former.
258    ///
259    /// See [`HasEscapingVarsVisitor`] for more information.
260    fn has_escaping_bound_vars(&self) -> bool {
261        self.has_vars_bound_at_or_above(ty::INNERMOST)
262    }
263
264    fn has_aliases(&self) -> bool {
265        self.has_type_flags(TypeFlags::HAS_ALIAS)
266    }
267
268    fn has_opaque_types(&self) -> bool {
269        self.has_type_flags(TypeFlags::HAS_TY_OPAQUE)
270    }
271
272    fn references_error(&self) -> bool {
273        self.has_type_flags(TypeFlags::HAS_ERROR)
274    }
275
276    fn error_reported(&self) -> Result<(), I::ErrorGuaranteed>;
277
278    fn has_non_region_param(&self) -> bool {
279        self.has_type_flags(TypeFlags::HAS_PARAM - TypeFlags::HAS_RE_PARAM)
280    }
281
282    fn has_infer_regions(&self) -> bool {
283        self.has_type_flags(TypeFlags::HAS_RE_INFER)
284    }
285
286    fn has_infer_types(&self) -> bool {
287        self.has_type_flags(TypeFlags::HAS_TY_INFER)
288    }
289
290    fn has_non_region_infer(&self) -> bool {
291        self.has_type_flags(TypeFlags::HAS_INFER - TypeFlags::HAS_RE_INFER)
292    }
293
294    fn has_infer(&self) -> bool {
295        self.has_type_flags(TypeFlags::HAS_INFER)
296    }
297
298    fn has_placeholders(&self) -> bool {
299        self.has_type_flags(TypeFlags::HAS_PLACEHOLDER)
300    }
301
302    fn has_non_region_placeholders(&self) -> bool {
303        self.has_type_flags(TypeFlags::HAS_PLACEHOLDER - TypeFlags::HAS_RE_PLACEHOLDER)
304    }
305
306    fn has_param(&self) -> bool {
307        self.has_type_flags(TypeFlags::HAS_PARAM)
308    }
309
310    /// "Free" regions in this context means that it has any region
311    /// that is not (a) erased or (b) late-bound.
312    fn has_free_regions(&self) -> bool {
313        self.has_type_flags(TypeFlags::HAS_FREE_REGIONS)
314    }
315
316    fn has_erased_regions(&self) -> bool {
317        self.has_type_flags(TypeFlags::HAS_RE_ERASED)
318    }
319
320    /// True if there are any un-erased free regions.
321    fn has_erasable_regions(&self) -> bool {
322        self.has_type_flags(TypeFlags::HAS_FREE_REGIONS)
323    }
324
325    /// Indicates whether this value references only 'global'
326    /// generic parameters that are the same regardless of what fn we are
327    /// in. This is used for caching.
328    fn is_global(&self) -> bool {
329        !self.has_type_flags(TypeFlags::HAS_FREE_LOCAL_NAMES)
330    }
331
332    /// True if there are any late-bound regions
333    fn has_bound_regions(&self) -> bool {
334        self.has_type_flags(TypeFlags::HAS_RE_BOUND)
335    }
336    /// True if there are any late-bound non-region variables
337    fn has_non_region_bound_vars(&self) -> bool {
338        self.has_type_flags(TypeFlags::HAS_BOUND_VARS - TypeFlags::HAS_RE_BOUND)
339    }
340    /// True if there are any bound variables
341    fn has_bound_vars(&self) -> bool {
342        self.has_type_flags(TypeFlags::HAS_BOUND_VARS)
343    }
344
345    /// Indicates whether this value still has parameters/placeholders/inference variables
346    /// which could be replaced later, in a way that would change the results of `impl`
347    /// specialization.
348    fn still_further_specializable(&self) -> bool {
349        self.has_type_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE)
350    }
351}
352
353impl<I: Interner, T: TypeVisitable<I>> TypeVisitableExt<I> for T {
354    fn has_type_flags(&self, flags: TypeFlags) -> bool {
355        let res =
356            self.visit_with(&mut HasTypeFlagsVisitor { flags }) == ControlFlow::Break(FoundFlags);
357        res
358    }
359
360    fn has_vars_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool {
361        self.visit_with(&mut HasEscapingVarsVisitor { outer_index: binder }).is_break()
362    }
363
364    fn error_reported(&self) -> Result<(), I::ErrorGuaranteed> {
365        if self.references_error() {
366            if let ControlFlow::Break(guar) = self.visit_with(&mut HasErrorVisitor) {
367                Err(guar)
368            } else {
369                panic!("type flags said there was an error, but now there is not")
370            }
371        } else {
372            Ok(())
373        }
374    }
375}
376
377#[derive(Debug, PartialEq, Eq, Copy, Clone)]
378struct FoundFlags;
379
380// FIXME: Optimize for checking for infer flags
381struct HasTypeFlagsVisitor {
382    flags: ty::TypeFlags,
383}
384
385impl std::fmt::Debug for HasTypeFlagsVisitor {
386    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
387        self.flags.fmt(fmt)
388    }
389}
390
391// Note: this visitor traverses values down to the level of
392// `Ty`/`Const`/`Predicate`, but not within those types. This is because the
393// type flags at the outer layer are enough. So it's faster than it first
394// looks, particular for `Ty`/`Predicate` where it's just a field access.
395//
396// N.B. The only case where this isn't totally true is binders, which also
397// add `HAS_{RE,TY,CT}_LATE_BOUND` flag depending on the *bound variables* that
398// are present, regardless of whether those bound variables are used. This
399// is important for anonymization of binders in `TyCtxt::erase_regions`. We
400// specifically detect this case in `visit_binder`.
401impl<I: Interner> TypeVisitor<I> for HasTypeFlagsVisitor {
402    type Result = ControlFlow<FoundFlags>;
403
404    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
405        // If we're looking for the HAS_BINDER_VARS flag, check if the
406        // binder has vars. This won't be present in the binder's bound
407        // value, so we need to check here too.
408        if self.flags.intersects(TypeFlags::HAS_BINDER_VARS) && !t.bound_vars().is_empty() {
409            return ControlFlow::Break(FoundFlags);
410        }
411
412        t.super_visit_with(self)
413    }
414
415    #[inline]
416    fn visit_ty(&mut self, t: I::Ty) -> Self::Result {
417        // Note: no `super_visit_with` call.
418        let flags = t.flags();
419        if flags.intersects(self.flags) {
420            ControlFlow::Break(FoundFlags)
421        } else {
422            ControlFlow::Continue(())
423        }
424    }
425
426    #[inline]
427    fn visit_region(&mut self, r: I::Region) -> Self::Result {
428        // Note: no `super_visit_with` call, as usual for `Region`.
429        let flags = r.flags();
430        if flags.intersects(self.flags) {
431            ControlFlow::Break(FoundFlags)
432        } else {
433            ControlFlow::Continue(())
434        }
435    }
436
437    #[inline]
438    fn visit_const(&mut self, c: I::Const) -> Self::Result {
439        // Note: no `super_visit_with` call.
440        if c.flags().intersects(self.flags) {
441            ControlFlow::Break(FoundFlags)
442        } else {
443            ControlFlow::Continue(())
444        }
445    }
446
447    #[inline]
448    fn visit_predicate(&mut self, predicate: I::Predicate) -> Self::Result {
449        // Note: no `super_visit_with` call.
450        if predicate.flags().intersects(self.flags) {
451            ControlFlow::Break(FoundFlags)
452        } else {
453            ControlFlow::Continue(())
454        }
455    }
456
457    #[inline]
458    fn visit_clauses(&mut self, clauses: I::Clauses) -> Self::Result {
459        // Note: no `super_visit_with` call.
460        if clauses.flags().intersects(self.flags) {
461            ControlFlow::Break(FoundFlags)
462        } else {
463            ControlFlow::Continue(())
464        }
465    }
466
467    #[inline]
468    fn visit_error(&mut self, _guar: <I as Interner>::ErrorGuaranteed) -> Self::Result {
469        if self.flags.intersects(TypeFlags::HAS_ERROR) {
470            ControlFlow::Break(FoundFlags)
471        } else {
472            ControlFlow::Continue(())
473        }
474    }
475}
476
477#[derive(Debug, PartialEq, Eq, Copy, Clone)]
478struct FoundEscapingVars;
479
480/// An "escaping var" is a bound var whose binder is not part of `t`. A bound var can be a
481/// bound region or a bound type.
482///
483/// So, for example, consider a type like the following, which has two binders:
484///
485///    for<'a> fn(x: for<'b> fn(&'a isize, &'b isize))
486///    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ outer scope
487///                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~  inner scope
488///
489/// This type has *bound regions* (`'a`, `'b`), but it does not have escaping regions, because the
490/// binders of both `'a` and `'b` are part of the type itself. However, if we consider the *inner
491/// fn type*, that type has an escaping region: `'a`.
492///
493/// Note that what I'm calling an "escaping var" is often just called a "free var". However,
494/// we already use the term "free var". It refers to the regions or types that we use to represent
495/// bound regions or type params on a fn definition while we are type checking its body.
496///
497/// To clarify, conceptually there is no particular difference between
498/// an "escaping" var and a "free" var. However, there is a big
499/// difference in practice. Basically, when "entering" a binding
500/// level, one is generally required to do some sort of processing to
501/// a bound var, such as replacing it with a fresh/placeholder
502/// var, or making an entry in the environment to represent the
503/// scope to which it is attached, etc. An escaping var represents
504/// a bound var for which this processing has not yet been done.
505struct HasEscapingVarsVisitor {
506    /// Anything bound by `outer_index` or "above" is escaping.
507    outer_index: ty::DebruijnIndex,
508}
509
510impl<I: Interner> TypeVisitor<I> for HasEscapingVarsVisitor {
511    type Result = ControlFlow<FoundEscapingVars>;
512
513    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
514        self.outer_index.shift_in(1);
515        let result = t.super_visit_with(self);
516        self.outer_index.shift_out(1);
517        result
518    }
519
520    #[inline]
521    fn visit_ty(&mut self, t: I::Ty) -> Self::Result {
522        // If the outer-exclusive-binder is *strictly greater* than
523        // `outer_index`, that means that `t` contains some content
524        // bound at `outer_index` or above (because
525        // `outer_exclusive_binder` is always 1 higher than the
526        // content in `t`). Therefore, `t` has some escaping vars.
527        if t.outer_exclusive_binder() > self.outer_index {
528            ControlFlow::Break(FoundEscapingVars)
529        } else {
530            ControlFlow::Continue(())
531        }
532    }
533
534    #[inline]
535    fn visit_region(&mut self, r: I::Region) -> Self::Result {
536        // If the region is bound by `outer_index` or anything outside
537        // of outer index, then it escapes the binders we have
538        // visited.
539        if r.outer_exclusive_binder() > self.outer_index {
540            ControlFlow::Break(FoundEscapingVars)
541        } else {
542            ControlFlow::Continue(())
543        }
544    }
545
546    fn visit_const(&mut self, ct: I::Const) -> Self::Result {
547        // If the outer-exclusive-binder is *strictly greater* than
548        // `outer_index`, that means that `ct` contains some content
549        // bound at `outer_index` or above (because
550        // `outer_exclusive_binder` is always 1 higher than the
551        // content in `t`). Therefore, `t` has some escaping vars.
552        if ct.outer_exclusive_binder() > self.outer_index {
553            ControlFlow::Break(FoundEscapingVars)
554        } else {
555            ControlFlow::Continue(())
556        }
557    }
558
559    #[inline]
560    fn visit_predicate(&mut self, predicate: I::Predicate) -> Self::Result {
561        if predicate.outer_exclusive_binder() > self.outer_index {
562            ControlFlow::Break(FoundEscapingVars)
563        } else {
564            ControlFlow::Continue(())
565        }
566    }
567
568    #[inline]
569    fn visit_clauses(&mut self, clauses: I::Clauses) -> Self::Result {
570        if clauses.outer_exclusive_binder() > self.outer_index {
571            ControlFlow::Break(FoundEscapingVars)
572        } else {
573            ControlFlow::Continue(())
574        }
575    }
576}
577
578struct HasErrorVisitor;
579
580impl<I: Interner> TypeVisitor<I> for HasErrorVisitor {
581    type Result = ControlFlow<I::ErrorGuaranteed>;
582
583    fn visit_error(&mut self, guar: <I as Interner>::ErrorGuaranteed) -> Self::Result {
584        ControlFlow::Break(guar)
585    }
586}
rustc_type_ir/visit.rs

rustc_type_ir/
visit.rs
