Improve comments about type folding/visiting.

I have found this code confusing for years. I've always roughly
understood it, but never exactly. I just made my fourth(?) attempt and
finally cracked it.

This commit improves the comments. In particular, it explicitly
describes how you can't do a custom fold/visit of any type; there are
actually a handful of "types of interest" (e.g. `Ty`, `Predicate`,
`Region`, `Const`) that can be custom folded/visted, and all other types
just get a generic traversal. I think this was the part that eluded me
on all my prior attempts at understanding.

The commit also updates comments to account for some newer changes such
as the fallible/infallible folding distinction, does some minor
reorderings, and moves one `impl` to a better place.

2 files changed, 113 insertions, 77 deletions

diff --git a/compiler/rustc_middle/src/ty/fold.rs b/compiler/rustc_middle/src/ty/fold.rs
index b3006672e22..4922d07ae1c 100644
--- a/compiler/rustc_middle/src/ty/fold.rs
+++ b/compiler/rustc_middle/src/ty/fold.rs
@@ -1,38 +1,56 @@
-//! Generalized type folding mechanism. The setup is a bit convoluted
-//! but allows for convenient usage. Let T be an instance of some
-//! "foldable type" (one which implements `TypeFoldable`) and F be an
-//! instance of a "folder" (a type which implements `TypeFolder`). Then
-//! the setup is intended to be:
+//! A generalized traversal mechanism for complex data structures that contain
+//! type information.
 //!
-//!     T.fold_with(F) --calls--> F.fold_T(T) --calls--> T.super_fold_with(F)
+//! 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.
 //!
-//! This way, when you define a new folder F, you can override
-//! `fold_T()` to customize the behavior, and invoke `T.super_fold_with()`
-//! to get the original behavior. Meanwhile, to actually fold
-//! something, you can just write `T.fold_with(F)`, which is
-//! convenient. (Note that `fold_with` will also transparently handle
-//! things like a `Vec<T>` where T is foldable and so on.)
+//! 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`.
 //!
-//! In this ideal setup, the only function that actually *does*
-//! anything is `T.super_fold_with()`, which traverses the type `T`.
-//! Moreover, `T.super_fold_with()` should only ever call `T.fold_with()`.
+//! 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.
 //!
-//! In some cases, we follow a degenerate pattern where we do not have
-//! a `fold_T` method. Instead, `T.fold_with` traverses the structure directly.
-//! This is suboptimal because the behavior cannot be overridden, but it's
-//! much less work to implement. If you ever *do* need an override that
-//! doesn't exist, it's not hard to convert the degenerate pattern into the
-//! proper thing.
+//! 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.
 //!
-//! A `TypeFoldable` T can also be visited by a `TypeVisitor` V using similar setup:
-//!
-//!     T.visit_with(V) --calls--> V.visit_T(T) --calls--> T.super_visit_with(V).
-//!
-//! These methods return true to indicate that the visitor has found what it is
-//! looking for, and does not need to visit anything else.
+//! 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)
+//! ```
 use crate::mir;
 use crate::ty::{self, flags::FlagComputation, Binder, Ty, TyCtxt, TypeFlags};
-use rustc_hir as hir;
 use rustc_hir::def_id::DefId;
 
 use rustc_data_structures::fx::FxHashSet;
@@ -41,42 +59,67 @@ use std::collections::BTreeMap;
 use std::fmt;
 use std::ops::ControlFlow;
 
-/// This trait is implemented for every type that can be folded.
-/// Basically, every type that has a corresponding method in `TypeFolder`.
+/// This trait is implemented for every type that can be folded/visited,
+/// providing the skeleton of the traversal.
 ///
-/// To implement this conveniently, use the derive macro located in `rustc_macros`.
+/// To implement this conveniently, use the derive macro located in
+/// `rustc_macros`.
 pub trait TypeFoldable<'tcx>: fmt::Debug + Clone {
-    /// Consumers may find this more convenient to use with infallible folders than
-    /// [`try_super_fold_with`][`TypeFoldable::try_super_fold_with`], to which the
-    /// provided default definition delegates.  Implementors **should not** override
-    /// this provided default definition, to ensure that the two methods are coherent
-    /// (provide a definition of `try_super_fold_with` instead).
-    fn super_fold_with<F: TypeFolder<'tcx, Error = !>>(self, folder: &mut F) -> Self {
-        self.try_super_fold_with(folder).into_ok()
+    /// The main entry point for folding. To fold a value `t` with a folder `f`
+    /// call: `t.try_fold_with(f)`.
+    ///
+    /// For types of interest (such as `Ty`), this default is overridden with a
+    /// method that calls a folder method specifically for that type (such as
+    /// `F::try_fold_ty`). This is where control transfers from `TypeFoldable`
+    /// to `TypeFolder`.
+    ///
+    /// For other types, this default is used.
+    fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
+        self.try_super_fold_with(folder)
     }
-    /// Consumers may find this more convenient to use with infallible folders than
-    /// [`try_fold_with`][`TypeFoldable::try_fold_with`], to which the provided
-    /// default definition delegates.  Implementors **should not** override this
-    /// provided default definition, to ensure that the two methods are coherent
-    /// (provide a definition of `try_fold_with` instead).
+
+    /// A convenient alternative to `try_fold_with` for use with infallible
+    /// folders. Do not override this method, to ensure coherence with
+    /// `try_fold_with`.
     fn fold_with<F: TypeFolder<'tcx, Error = !>>(self, folder: &mut F) -> Self {
         self.try_fold_with(folder).into_ok()
     }
 
+    /// Traverses the type in question, typically by calling `try_fold_with` on
+    /// each field/element. This is true even for types of interest such as
+    /// `Ty`. This should only be called within `TypeFolder` methods, when
+    /// non-custom traversals are desired for types of interest.
     fn try_super_fold_with<F: FallibleTypeFolder<'tcx>>(
         self,
         folder: &mut F,
     ) -> Result<Self, F::Error>;
 
-    fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
-        self.try_super_fold_with(folder)
+    /// A convenient alternative to `try_super_fold_with` for use with
+    /// infallible folders. Do not override this method, to ensure coherence
+    /// with `try_super_fold_with`.
+    fn super_fold_with<F: TypeFolder<'tcx, Error = !>>(self, folder: &mut F) -> Self {
+        self.try_super_fold_with(folder).into_ok()
     }
 
-    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy>;
+    /// The entry point for visiting. To visit a value `t` with a visitor `v`
+    /// call: `t.visit_with(v)`.
+    ///
+    /// For types of interest (such as `Ty`), this default is overridden with a
+    /// method that calls a visitor method specifically for that type (such as
+    /// `V::visit_ty`). This is where control transfers from `TypeFoldable` to
+    /// `TypeVisitor`.
+    ///
+    /// For other types, this default is used.
     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
         self.super_visit_with(visitor)
     }
 
+    /// Traverses the type in question, typically by calling `visit_with` on
+    /// each field/element. This is true even for types of interest such as
+    /// `Ty`. This should only be called within `TypeVisitor` methods, when
+    /// non-custom traversals are desired for types of interest.
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy>;
+
     /// Returns `true` if `self` has any late-bound regions that are either
     /// bound by `binder` or bound by some binder outside of `binder`.
     /// If `binder` is `ty::INNERMOST`, this indicates whether
@@ -168,24 +211,13 @@ pub trait TypeFoldable<'tcx>: fmt::Debug + Clone {
     }
 }
 
-impl<'tcx> TypeFoldable<'tcx> for hir::Constness {
-    fn try_super_fold_with<F: TypeFolder<'tcx>>(self, _: &mut F) -> Result<Self, F::Error> {
-        Ok(self)
-    }
-    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _: &mut V) -> ControlFlow<V::BreakTy> {
-        ControlFlow::CONTINUE
-    }
-}
-
-/// The `TypeFolder` trait defines the actual *folding*. There is a
-/// method defined for every foldable type. Each of these has a
-/// default implementation that does an "identity" fold. Within each
-/// identity fold, it should invoke `foo.fold_with(self)` to fold each
-/// sub-item.
+/// 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.
 ///
 /// If this folder is fallible (and therefore its [`Error`][`TypeFolder::Error`]
-/// associated type is something other than the default, never),
-/// [`FallibleTypeFolder`] should be implemented manually; otherwise,
+/// associated type is something other than the default `!`) then
+/// [`FallibleTypeFolder`] should be implemented manually. Otherwise,
 /// a blanket implementation of [`FallibleTypeFolder`] will defer to
 /// the infallible methods of this trait to ensure that the two APIs
 /// are coherent.
@@ -238,11 +270,9 @@ pub trait TypeFolder<'tcx>: Sized {
     }
 }
 
-/// The `FallibleTypeFolder` trait defines the actual *folding*. There is a
-/// method defined for every foldable type. Each of these has a
-/// default implementation that does an "identity" fold. Within each
-/// identity fold, it should invoke `foo.try_fold_with(self)` to fold each
-/// sub-item.
+/// 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.
 ///
 /// A blanket implementation of this trait (that defers to the relevant
 /// method of [`TypeFolder`]) is provided for all infallible folders in
@@ -282,8 +312,8 @@ pub trait FallibleTypeFolder<'tcx>: TypeFolder<'tcx> {
     }
 }
 
-// Blanket implementation of fallible trait for infallible folders
-// delegates to infallible methods to prevent incoherence
+// This blanket implementation of the fallible trait for infallible folders
+// delegates to infallible methods to ensure coherence.
 impl<'tcx, F> FallibleTypeFolder<'tcx> for F
 where
     F: TypeFolder<'tcx, Error = !>,
@@ -322,6 +352,9 @@ where
     }
 }
 
+/// 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.
 pub trait TypeVisitor<'tcx>: Sized {
     type BreakTy = !;
 
diff --git a/compiler/rustc_middle/src/ty/structural_impls.rs b/compiler/rustc_middle/src/ty/structural_impls.rs
index c1d714ed8d6..e4691dee779 100644
--- a/compiler/rustc_middle/src/ty/structural_impls.rs
+++ b/compiler/rustc_middle/src/ty/structural_impls.rs
@@ -8,6 +8,7 @@ use crate::ty::fold::{FallibleTypeFolder, TypeFoldable, TypeVisitor};
 use crate::ty::print::{with_no_trimmed_paths, FmtPrinter, Printer};
 use crate::ty::{self, InferConst, Lift, Term, Ty, TyCtxt};
 use rustc_data_structures::functor::IdFunctor;
+use rustc_hir as hir;
 use rustc_hir::def::Namespace;
 use rustc_hir::def_id::CRATE_DEF_INDEX;
 use rustc_index::vec::{Idx, IndexVec};
@@ -663,14 +664,6 @@ impl<'a, 'tcx> Lift<'tcx> for ty::InstanceDef<'a> {
 
 ///////////////////////////////////////////////////////////////////////////
 // TypeFoldable implementations.
-//
-// Ideally, each type should invoke `folder.fold_foo(self)` and
-// nothing else. In some cases, though, we haven't gotten around to
-// adding methods on the `folder` yet, and thus the folding is
-// hard-coded here. This is less-flexible, because folders cannot
-// override the behavior, but there are a lot of random types and one
-// can easily refactor the folding into the TypeFolder trait as
-// needed.
 
 /// AdtDefs are basically the same as a DefId.
 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::AdtDef {
@@ -1270,3 +1263,13 @@ impl<'tcx> TypeFoldable<'tcx> for ty::Unevaluated<'tcx, ()> {
         self.substs.visit_with(visitor)
     }
 }
+
+impl<'tcx> TypeFoldable<'tcx> for hir::Constness {
+    fn try_super_fold_with<F: FallibleTypeFolder<'tcx>>(self, _: &mut F) -> Result<Self, F::Error> {
+        Ok(self)
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _: &mut V) -> ControlFlow<V::BreakTy> {
+        ControlFlow::CONTINUE
+    }
+}