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