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, c: I::Clauses) -> Self::Result {
124        c.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 has_coroutines(&self) -> bool {
273        self.has_type_flags(TypeFlags::HAS_TY_CORO)
274    }
275
276    fn references_error(&self) -> bool {
277        self.has_type_flags(TypeFlags::HAS_ERROR)
278    }
279
280    fn error_reported(&self) -> Result<(), I::ErrorGuaranteed>;
281
282    fn has_non_region_param(&self) -> bool {
283        self.has_type_flags(TypeFlags::HAS_PARAM - TypeFlags::HAS_RE_PARAM)
284    }
285
286    fn has_infer_regions(&self) -> bool {
287        self.has_type_flags(TypeFlags::HAS_RE_INFER)
288    }
289
290    fn has_infer_types(&self) -> bool {
291        self.has_type_flags(TypeFlags::HAS_TY_INFER)
292    }
293
294    fn has_non_region_infer(&self) -> bool {
295        self.has_type_flags(TypeFlags::HAS_INFER - TypeFlags::HAS_RE_INFER)
296    }
297
298    fn has_infer(&self) -> bool {
299        self.has_type_flags(TypeFlags::HAS_INFER)
300    }
301
302    fn has_placeholders(&self) -> bool {
303        self.has_type_flags(TypeFlags::HAS_PLACEHOLDER)
304    }
305
306    fn has_non_region_placeholders(&self) -> bool {
307        self.has_type_flags(TypeFlags::HAS_PLACEHOLDER - TypeFlags::HAS_RE_PLACEHOLDER)
308    }
309
310    fn has_param(&self) -> bool {
311        self.has_type_flags(TypeFlags::HAS_PARAM)
312    }
313
314    /// "Free" regions in this context means that it has any region
315    /// that is not (a) erased or (b) late-bound.
316    fn has_free_regions(&self) -> bool {
317        self.has_type_flags(TypeFlags::HAS_FREE_REGIONS)
318    }
319
320    fn has_erased_regions(&self) -> bool {
321        self.has_type_flags(TypeFlags::HAS_RE_ERASED)
322    }
323
324    /// True if there are any un-erased free regions.
325    fn has_erasable_regions(&self) -> bool {
326        self.has_type_flags(TypeFlags::HAS_FREE_REGIONS)
327    }
328
329    /// Indicates whether this value references only 'global'
330    /// generic parameters that are the same regardless of what fn we are
331    /// in. This is used for caching.
332    fn is_global(&self) -> bool {
333        !self.has_type_flags(TypeFlags::HAS_FREE_LOCAL_NAMES)
334    }
335
336    /// True if there are any late-bound regions
337    fn has_bound_regions(&self) -> bool {
338        self.has_type_flags(TypeFlags::HAS_RE_BOUND)
339    }
340    /// True if there are any late-bound non-region variables
341    fn has_non_region_bound_vars(&self) -> bool {
342        self.has_type_flags(TypeFlags::HAS_BOUND_VARS - TypeFlags::HAS_RE_BOUND)
343    }
344    /// True if there are any bound variables
345    fn has_bound_vars(&self) -> bool {
346        self.has_type_flags(TypeFlags::HAS_BOUND_VARS)
347    }
348
349    /// Indicates whether this value still has parameters/placeholders/inference variables
350    /// which could be replaced later, in a way that would change the results of `impl`
351    /// specialization.
352    fn still_further_specializable(&self) -> bool {
353        self.has_type_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE)
354    }
355}
356
357impl<I: Interner, T: TypeVisitable<I>> TypeVisitableExt<I> for T {
358    fn has_type_flags(&self, flags: TypeFlags) -> bool {
359        let res =
360            self.visit_with(&mut HasTypeFlagsVisitor { flags }) == ControlFlow::Break(FoundFlags);
361        res
362    }
363
364    fn has_vars_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool {
365        self.visit_with(&mut HasEscapingVarsVisitor { outer_index: binder }).is_break()
366    }
367
368    fn error_reported(&self) -> Result<(), I::ErrorGuaranteed> {
369        if self.references_error() {
370            if let ControlFlow::Break(guar) = self.visit_with(&mut HasErrorVisitor) {
371                Err(guar)
372            } else {
373                panic!("type flags said there was an error, but now there is not")
374            }
375        } else {
376            Ok(())
377        }
378    }
379}
380
381#[derive(Debug, PartialEq, Eq, Copy, Clone)]
382struct FoundFlags;
383
384// FIXME: Optimize for checking for infer flags
385struct HasTypeFlagsVisitor {
386    flags: ty::TypeFlags,
387}
388
389impl std::fmt::Debug for HasTypeFlagsVisitor {
390    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
391        self.flags.fmt(fmt)
392    }
393}
394
395// Note: this visitor traverses values down to the level of
396// `Ty`/`Const`/`Predicate`, but not within those types. This is because the
397// type flags at the outer layer are enough. So it's faster than it first
398// looks, particular for `Ty`/`Predicate` where it's just a field access.
399//
400// N.B. The only case where this isn't totally true is binders, which also
401// add `HAS_BINDER_VARS` flag depending on the *bound variables* that
402// are present, regardless of whether those bound variables are used. This
403// is important for anonymization of binders in `TyCtxt::erase_and_anonymize_regions`. We
404// specifically detect this case in `visit_binder`.
405impl<I: Interner> TypeVisitor<I> for HasTypeFlagsVisitor {
406    type Result = ControlFlow<FoundFlags>;
407
408    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
409        // If we're looking for the HAS_BINDER_VARS flag, check if the
410        // binder has vars. This won't be present in the binder's bound
411        // value, so we need to check here too.
412        if self.flags.intersects(TypeFlags::HAS_BINDER_VARS) && !t.bound_vars().is_empty() {
413            return ControlFlow::Break(FoundFlags);
414        }
415
416        t.super_visit_with(self)
417    }
418
419    #[inline]
420    fn visit_ty(&mut self, t: I::Ty) -> Self::Result {
421        // Note: no `super_visit_with` call.
422        let flags = t.flags();
423        if flags.intersects(self.flags) {
424            ControlFlow::Break(FoundFlags)
425        } else {
426            ControlFlow::Continue(())
427        }
428    }
429
430    #[inline]
431    fn visit_region(&mut self, r: I::Region) -> Self::Result {
432        // Note: no `super_visit_with` call, as usual for `Region`.
433        let flags = r.flags();
434        if flags.intersects(self.flags) {
435            ControlFlow::Break(FoundFlags)
436        } else {
437            ControlFlow::Continue(())
438        }
439    }
440
441    #[inline]
442    fn visit_const(&mut self, c: I::Const) -> Self::Result {
443        // Note: no `super_visit_with` call.
444        if c.flags().intersects(self.flags) {
445            ControlFlow::Break(FoundFlags)
446        } else {
447            ControlFlow::Continue(())
448        }
449    }
450
451    #[inline]
452    fn visit_predicate(&mut self, predicate: I::Predicate) -> Self::Result {
453        // Note: no `super_visit_with` call.
454        if predicate.flags().intersects(self.flags) {
455            ControlFlow::Break(FoundFlags)
456        } else {
457            ControlFlow::Continue(())
458        }
459    }
460
461    #[inline]
462    fn visit_clauses(&mut self, clauses: I::Clauses) -> Self::Result {
463        // Note: no `super_visit_with` call.
464        if clauses.flags().intersects(self.flags) {
465            ControlFlow::Break(FoundFlags)
466        } else {
467            ControlFlow::Continue(())
468        }
469    }
470
471    #[inline]
472    fn visit_error(&mut self, _guar: <I as Interner>::ErrorGuaranteed) -> Self::Result {
473        if self.flags.intersects(TypeFlags::HAS_ERROR) {
474            ControlFlow::Break(FoundFlags)
475        } else {
476            ControlFlow::Continue(())
477        }
478    }
479}
480
481#[derive(Debug, PartialEq, Eq, Copy, Clone)]
482struct FoundEscapingVars;
483
484/// An "escaping var" is a bound var whose binder is not part of `t`. A bound var can be a
485/// bound region or a bound type.
486///
487/// So, for example, consider a type like the following, which has two binders:
488///
489///    for<'a> fn(x: for<'b> fn(&'a isize, &'b isize))
490///    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ outer scope
491///                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~  inner scope
492///
493/// This type has *bound regions* (`'a`, `'b`), but it does not have escaping regions, because the
494/// binders of both `'a` and `'b` are part of the type itself. However, if we consider the *inner
495/// fn type*, that type has an escaping region: `'a`.
496///
497/// Note that what I'm calling an "escaping var" is often just called a "free var". However,
498/// we already use the term "free var". It refers to the regions or types that we use to represent
499/// bound regions or type params on a fn definition while we are type checking its body.
500///
501/// To clarify, conceptually there is no particular difference between
502/// an "escaping" var and a "free" var. However, there is a big
503/// difference in practice. Basically, when "entering" a binding
504/// level, one is generally required to do some sort of processing to
505/// a bound var, such as replacing it with a fresh/placeholder
506/// var, or making an entry in the environment to represent the
507/// scope to which it is attached, etc. An escaping var represents
508/// a bound var for which this processing has not yet been done.
509struct HasEscapingVarsVisitor {
510    /// Anything bound by `outer_index` or "above" is escaping.
511    outer_index: ty::DebruijnIndex,
512}
513
514impl<I: Interner> TypeVisitor<I> for HasEscapingVarsVisitor {
515    type Result = ControlFlow<FoundEscapingVars>;
516
517    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
518        self.outer_index.shift_in(1);
519        let result = t.super_visit_with(self);
520        self.outer_index.shift_out(1);
521        result
522    }
523
524    #[inline]
525    fn visit_ty(&mut self, t: I::Ty) -> Self::Result {
526        // If the outer-exclusive-binder is *strictly greater* than
527        // `outer_index`, that means that `t` contains some content
528        // bound at `outer_index` or above (because
529        // `outer_exclusive_binder` is always 1 higher than the
530        // content in `t`). Therefore, `t` has some escaping vars.
531        if t.outer_exclusive_binder() > self.outer_index {
532            ControlFlow::Break(FoundEscapingVars)
533        } else {
534            ControlFlow::Continue(())
535        }
536    }
537
538    #[inline]
539    fn visit_region(&mut self, r: I::Region) -> Self::Result {
540        // If the region is bound by `outer_index` or anything outside
541        // of outer index, then it escapes the binders we have
542        // visited.
543        if r.outer_exclusive_binder() > self.outer_index {
544            ControlFlow::Break(FoundEscapingVars)
545        } else {
546            ControlFlow::Continue(())
547        }
548    }
549
550    fn visit_const(&mut self, ct: I::Const) -> Self::Result {
551        // If the outer-exclusive-binder is *strictly greater* than
552        // `outer_index`, that means that `ct` contains some content
553        // bound at `outer_index` or above (because
554        // `outer_exclusive_binder` is always 1 higher than the
555        // content in `t`). Therefore, `t` has some escaping vars.
556        if ct.outer_exclusive_binder() > self.outer_index {
557            ControlFlow::Break(FoundEscapingVars)
558        } else {
559            ControlFlow::Continue(())
560        }
561    }
562
563    #[inline]
564    fn visit_predicate(&mut self, predicate: I::Predicate) -> Self::Result {
565        if predicate.outer_exclusive_binder() > self.outer_index {
566            ControlFlow::Break(FoundEscapingVars)
567        } else {
568            ControlFlow::Continue(())
569        }
570    }
571
572    #[inline]
573    fn visit_clauses(&mut self, clauses: I::Clauses) -> Self::Result {
574        if clauses.outer_exclusive_binder() > self.outer_index {
575            ControlFlow::Break(FoundEscapingVars)
576        } else {
577            ControlFlow::Continue(())
578        }
579    }
580}
581
582struct HasErrorVisitor;
583
584impl<I: Interner> TypeVisitor<I> for HasErrorVisitor {
585    type Result = ControlFlow<I::ErrorGuaranteed>;
586
587    fn visit_error(&mut self, guar: <I as Interner>::ErrorGuaranteed) -> Self::Result {
588        ControlFlow::Break(guar)
589    }
590}
rustc_type_ir/visit.rs

rustc_type_ir/
visit.rs
