Expand description

A generalized traversal mechanism for complex data structures that contain type information.

There are two types of traversal.

  • Folding. This is a modifying traversal. It consumes the data structure, producing a (possibly) modified version of it. Both fallible and infallible versions are available. The name is potentially confusing, because this traversal is more like Iterator::map than Iterator::fold.
  • Visiting. This is a read-only traversal of the data structure.

These traversals have limited flexibility. Only a small number of “types of interest” within the complex data structures can receive custom modification (when folding) or custom visitation (when visiting). These are the ones containing the most important type-related information, such as Ty, Predicate, Region, and Const.

There are two traits involved in each traversal type.

  • The first trait is TypeFoldable, which is implemented once for many types. This includes both (a) types of interest, and (b) all other relevant types, including generic containers like Vec and Option. It defines a “skeleton” of how they should be traversed, for both folding and visiting.
  • The second trait is TypeFolder/FallibleTypeFolder (for infallible/fallible folding traversals) or TypeVisitor (for visiting traversals). One of these is implemented for each folder/visitor. This defines how types of interest are handled.

This means each traversal is a mixture of (a) generic traversal operations, and (b) custom fold/visit operations that are specific to the folder/visitor.

  • The TypeFoldable impls handle most of the traversal, and call into TypeFolder/FallibleTypeFolder/TypeVisitor when they encounter a type of interest.
  • A TypeFolder/FallibleTypeFolder/TypeVisitor may also call back into a TypeFoldable impl, because (a) the types of interest are recursive and can contain other types of interest, and (b) each folder/visitor might provide custom handling only for some types of interest, or only for some variants of each type of interest, and then use default traversal for the remaining cases.

For example, if you have struct S(Ty, U) where S: TypeFoldable and U: TypeFoldable, and an instance S(ty, u), it would be visited like so:

s.visit_with(visitor) calls
- s.super_visit_with(visitor) calls
  - ty.visit_with(visitor) calls
    - visitor.visit_ty(ty) may call
      - ty.super_visit_with(visitor)
  - u.visit_with(visitor)

Structs

Replaces the escaping bound vars (late bound regions or bound types) in a type.

FoundFlags 🔒

An “escaping var” is a bound var whose binder is not part of t. A bound var can be a bound region or a bound type.

Collects all the late-bound regions at the innermost binding level into a hash set.

Finds the max universe present

Folds over the substructure of a type, visiting its component types and all regions that occur free within it.

Shifter 🔒

Traits

This trait is implemented for every folding traversal. There is a fold method defined for every type of interest. Each such method has a default that does an “identity” fold.

This trait is implemented for every type that can be folded/visited, providing the skeleton of the traversal.

This trait is implemented for every folding traversal. There is a fold method defined for every type of interest. Each such method has a default that does an “identity” fold.

This trait is implemented for every visiting traversal. There is a visit method defined for every type of interest. Each such method has a default that recurses into the type’s fields in a non-custom fashion.

Functions