Rollup merge of #84613 - lcnr:recursive-types, r=jackh726

move representability checks to rustc_ty_utils

6 files changed, 194 insertions, 191 deletions

diff --git a/Cargo.lock b/Cargo.lock
index c142dd4d2ea..985c6bf481f 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -4590,6 +4590,7 @@ dependencies = [
  "rustc_span",
  "rustc_target",
  "rustc_trait_selection",
+ "rustc_ty_utils",
  "smallvec",
  "tracing",
 ]
diff --git a/compiler/rustc_middle/src/ty/util.rs b/compiler/rustc_middle/src/ty/util.rs
index 7d09ca5152f..e365928c15f 100644
--- a/compiler/rustc_middle/src/ty/util.rs
+++ b/compiler/rustc_middle/src/ty/util.rs
@@ -18,10 +18,10 @@ use rustc_hir as hir;
 use rustc_hir::def::DefKind;
 use rustc_hir::def_id::DefId;
 use rustc_macros::HashStable;
-use rustc_span::{Span, DUMMY_SP};
+use rustc_span::DUMMY_SP;
 use rustc_target::abi::{Integer, Size, TargetDataLayout};
 use smallvec::SmallVec;
-use std::{cmp, fmt, iter};
+use std::{fmt, iter};
 
 #[derive(Copy, Clone, Debug)]
 pub struct Discr<'tcx> {
@@ -135,21 +135,6 @@ impl IntTypeExt for attr::IntType {
     }
 }
 
-/// Describes whether a type is representable. For types that are not
-/// representable, 'SelfRecursive' and 'ContainsRecursive' are used to
-/// distinguish between types that are recursive with themselves and types that
-/// contain a different recursive type. These cases can therefore be treated
-/// differently when reporting errors.
-///
-/// The ordering of the cases is significant. They are sorted so that cmp::max
-/// will keep the "more erroneous" of two values.
-#[derive(Clone, PartialOrd, Ord, Eq, PartialEq, Debug)]
-pub enum Representability {
-    Representable,
-    ContainsRecursive,
-    SelfRecursive(Vec<Span>),
-}
-
 impl<'tcx> TyCtxt<'tcx> {
     /// Creates a hash of the type `Ty` which will be the same no matter what crate
     /// context it's calculated within. This is used by the `type_id` intrinsic.
@@ -870,178 +855,6 @@ impl<'tcx> ty::TyS<'tcx> {
         }
     }
 
-    /// Check whether a type is representable. This means it cannot contain unboxed
-    /// structural recursion. This check is needed for structs and enums.
-    pub fn is_representable(&'tcx self, tcx: TyCtxt<'tcx>, sp: Span) -> Representability {
-        // Iterate until something non-representable is found
-        fn fold_repr<It: Iterator<Item = Representability>>(iter: It) -> Representability {
-            iter.fold(Representability::Representable, |r1, r2| match (r1, r2) {
-                (Representability::SelfRecursive(v1), Representability::SelfRecursive(v2)) => {
-                    Representability::SelfRecursive(v1.into_iter().chain(v2).collect())
-                }
-                (r1, r2) => cmp::max(r1, r2),
-            })
-        }
-
-        fn are_inner_types_recursive<'tcx>(
-            tcx: TyCtxt<'tcx>,
-            sp: Span,
-            seen: &mut Vec<Ty<'tcx>>,
-            representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
-            ty: Ty<'tcx>,
-        ) -> Representability {
-            match ty.kind() {
-                Tuple(..) => {
-                    // Find non representable
-                    fold_repr(ty.tuple_fields().map(|ty| {
-                        is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty)
-                    }))
-                }
-                // Fixed-length vectors.
-                // FIXME(#11924) Behavior undecided for zero-length vectors.
-                Array(ty, _) => {
-                    is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty)
-                }
-                Adt(def, substs) => {
-                    // Find non representable fields with their spans
-                    fold_repr(def.all_fields().map(|field| {
-                        let ty = field.ty(tcx, substs);
-                        let span = match field
-                            .did
-                            .as_local()
-                            .map(|id| tcx.hir().local_def_id_to_hir_id(id))
-                            .and_then(|id| tcx.hir().find(id))
-                        {
-                            Some(hir::Node::Field(field)) => field.ty.span,
-                            _ => sp,
-                        };
-                        match is_type_structurally_recursive(
-                            tcx,
-                            span,
-                            seen,
-                            representable_cache,
-                            ty,
-                        ) {
-                            Representability::SelfRecursive(_) => {
-                                Representability::SelfRecursive(vec![span])
-                            }
-                            x => x,
-                        }
-                    }))
-                }
-                Closure(..) => {
-                    // this check is run on type definitions, so we don't expect
-                    // to see closure types
-                    bug!("requires check invoked on inapplicable type: {:?}", ty)
-                }
-                _ => Representability::Representable,
-            }
-        }
-
-        fn same_struct_or_enum<'tcx>(ty: Ty<'tcx>, def: &'tcx ty::AdtDef) -> bool {
-            match *ty.kind() {
-                Adt(ty_def, _) => ty_def == def,
-                _ => false,
-            }
-        }
-
-        // Does the type `ty` directly (without indirection through a pointer)
-        // contain any types on stack `seen`?
-        fn is_type_structurally_recursive<'tcx>(
-            tcx: TyCtxt<'tcx>,
-            sp: Span,
-            seen: &mut Vec<Ty<'tcx>>,
-            representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
-            ty: Ty<'tcx>,
-        ) -> Representability {
-            debug!("is_type_structurally_recursive: {:?} {:?}", ty, sp);
-            if let Some(representability) = representable_cache.get(ty) {
-                debug!(
-                    "is_type_structurally_recursive: {:?} {:?} - (cached) {:?}",
-                    ty, sp, representability
-                );
-                return representability.clone();
-            }
-
-            let representability =
-                is_type_structurally_recursive_inner(tcx, sp, seen, representable_cache, ty);
-
-            representable_cache.insert(ty, representability.clone());
-            representability
-        }
-
-        fn is_type_structurally_recursive_inner<'tcx>(
-            tcx: TyCtxt<'tcx>,
-            sp: Span,
-            seen: &mut Vec<Ty<'tcx>>,
-            representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
-            ty: Ty<'tcx>,
-        ) -> Representability {
-            match ty.kind() {
-                Adt(def, _) => {
-                    {
-                        // Iterate through stack of previously seen types.
-                        let mut iter = seen.iter();
-
-                        // The first item in `seen` is the type we are actually curious about.
-                        // We want to return SelfRecursive if this type contains itself.
-                        // It is important that we DON'T take generic parameters into account
-                        // for this check, so that Bar<T> in this example counts as SelfRecursive:
-                        //
-                        // struct Foo;
-                        // struct Bar<T> { x: Bar<Foo> }
-
-                        if let Some(&seen_type) = iter.next() {
-                            if same_struct_or_enum(seen_type, *def) {
-                                debug!("SelfRecursive: {:?} contains {:?}", seen_type, ty);
-                                return Representability::SelfRecursive(vec![sp]);
-                            }
-                        }
-
-                        // We also need to know whether the first item contains other types
-                        // that are structurally recursive. If we don't catch this case, we
-                        // will recurse infinitely for some inputs.
-                        //
-                        // It is important that we DO take generic parameters into account
-                        // here, so that code like this is considered SelfRecursive, not
-                        // ContainsRecursive:
-                        //
-                        // struct Foo { Option<Option<Foo>> }
-
-                        for &seen_type in iter {
-                            if ty::TyS::same_type(ty, seen_type) {
-                                debug!("ContainsRecursive: {:?} contains {:?}", seen_type, ty);
-                                return Representability::ContainsRecursive;
-                            }
-                        }
-                    }
-
-                    // For structs and enums, track all previously seen types by pushing them
-                    // onto the 'seen' stack.
-                    seen.push(ty);
-                    let out = are_inner_types_recursive(tcx, sp, seen, representable_cache, ty);
-                    seen.pop();
-                    out
-                }
-                _ => {
-                    // No need to push in other cases.
-                    are_inner_types_recursive(tcx, sp, seen, representable_cache, ty)
-                }
-            }
-        }
-
-        debug!("is_type_representable: {:?}", self);
-
-        // To avoid a stack overflow when checking an enum variant or struct that
-        // contains a different, structurally recursive type, maintain a stack
-        // of seen types and check recursion for each of them (issues #3008, #3779).
-        let mut seen: Vec<Ty<'_>> = Vec::new();
-        let mut representable_cache = FxHashMap::default();
-        let r = is_type_structurally_recursive(tcx, sp, &mut seen, &mut representable_cache, self);
-        debug!("is_type_representable: {:?} is {:?}", self, r);
-        r
-    }
-
     /// Peel off all reference types in this type until there are none left.
     ///
     /// This method is idempotent, i.e. `ty.peel_refs().peel_refs() == ty.peel_refs()`.
diff --git a/compiler/rustc_ty_utils/src/lib.rs b/compiler/rustc_ty_utils/src/lib.rs
index aa5d3388401..67a692eceac 100644
--- a/compiler/rustc_ty_utils/src/lib.rs
+++ b/compiler/rustc_ty_utils/src/lib.rs
@@ -20,6 +20,7 @@ use rustc_middle::ty::query::Providers;
 mod common_traits;
 pub mod instance;
 mod needs_drop;
+pub mod representability;
 mod ty;
 
 pub fn provide(providers: &mut Providers) {
diff --git a/compiler/rustc_ty_utils/src/representability.rs b/compiler/rustc_ty_utils/src/representability.rs
new file mode 100644
index 00000000000..ca001635a3d
--- /dev/null
+++ b/compiler/rustc_ty_utils/src/representability.rs
@@ -0,0 +1,186 @@
+//! Check whether a type is representable.
+use rustc_data_structures::stable_map::FxHashMap;
+use rustc_hir as hir;
+use rustc_middle::ty::{self, Ty, TyCtxt};
+use rustc_span::Span;
+use std::cmp;
+
+/// Describes whether a type is representable. For types that are not
+/// representable, 'SelfRecursive' and 'ContainsRecursive' are used to
+/// distinguish between types that are recursive with themselves and types that
+/// contain a different recursive type. These cases can therefore be treated
+/// differently when reporting errors.
+///
+/// The ordering of the cases is significant. They are sorted so that cmp::max
+/// will keep the "more erroneous" of two values.
+#[derive(Clone, PartialOrd, Ord, Eq, PartialEq, Debug)]
+pub enum Representability {
+    Representable,
+    ContainsRecursive,
+    SelfRecursive(Vec<Span>),
+}
+
+/// Check whether a type is representable. This means it cannot contain unboxed
+/// structural recursion. This check is needed for structs and enums.
+pub fn ty_is_representable<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, sp: Span) -> Representability {
+    debug!("is_type_representable: {:?}", ty);
+    // To avoid a stack overflow when checking an enum variant or struct that
+    // contains a different, structurally recursive type, maintain a stack
+    // of seen types and check recursion for each of them (issues #3008, #3779).
+    let mut seen: Vec<Ty<'_>> = Vec::new();
+    let mut representable_cache = FxHashMap::default();
+    let r = is_type_structurally_recursive(tcx, sp, &mut seen, &mut representable_cache, ty);
+    debug!("is_type_representable: {:?} is {:?}", ty, r);
+    r
+}
+
+// Iterate until something non-representable is found
+fn fold_repr<It: Iterator<Item = Representability>>(iter: It) -> Representability {
+    iter.fold(Representability::Representable, |r1, r2| match (r1, r2) {
+        (Representability::SelfRecursive(v1), Representability::SelfRecursive(v2)) => {
+            Representability::SelfRecursive(v1.into_iter().chain(v2).collect())
+        }
+        (r1, r2) => cmp::max(r1, r2),
+    })
+}
+
+fn are_inner_types_recursive<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    sp: Span,
+    seen: &mut Vec<Ty<'tcx>>,
+    representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
+    ty: Ty<'tcx>,
+) -> Representability {
+    match ty.kind() {
+        ty::Tuple(..) => {
+            // Find non representable
+            fold_repr(
+                ty.tuple_fields().map(|ty| {
+                    is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty)
+                }),
+            )
+        }
+        // Fixed-length vectors.
+        // FIXME(#11924) Behavior undecided for zero-length vectors.
+        ty::Array(ty, _) => is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty),
+        ty::Adt(def, substs) => {
+            // Find non representable fields with their spans
+            fold_repr(def.all_fields().map(|field| {
+                let ty = field.ty(tcx, substs);
+                let span = match field
+                    .did
+                    .as_local()
+                    .map(|id| tcx.hir().local_def_id_to_hir_id(id))
+                    .and_then(|id| tcx.hir().find(id))
+                {
+                    Some(hir::Node::Field(field)) => field.ty.span,
+                    _ => sp,
+                };
+                match is_type_structurally_recursive(tcx, span, seen, representable_cache, ty) {
+                    Representability::SelfRecursive(_) => {
+                        Representability::SelfRecursive(vec![span])
+                    }
+                    x => x,
+                }
+            }))
+        }
+        ty::Closure(..) => {
+            // this check is run on type definitions, so we don't expect
+            // to see closure types
+            bug!("requires check invoked on inapplicable type: {:?}", ty)
+        }
+        _ => Representability::Representable,
+    }
+}
+
+fn same_adt<'tcx>(ty: Ty<'tcx>, def: &'tcx ty::AdtDef) -> bool {
+    match *ty.kind() {
+        ty::Adt(ty_def, _) => ty_def == def,
+        _ => false,
+    }
+}
+
+// Does the type `ty` directly (without indirection through a pointer)
+// contain any types on stack `seen`?
+fn is_type_structurally_recursive<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    sp: Span,
+    seen: &mut Vec<Ty<'tcx>>,
+    representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
+    ty: Ty<'tcx>,
+) -> Representability {
+    debug!("is_type_structurally_recursive: {:?} {:?}", ty, sp);
+    if let Some(representability) = representable_cache.get(ty) {
+        debug!(
+            "is_type_structurally_recursive: {:?} {:?} - (cached) {:?}",
+            ty, sp, representability
+        );
+        return representability.clone();
+    }
+
+    let representability =
+        is_type_structurally_recursive_inner(tcx, sp, seen, representable_cache, ty);
+
+    representable_cache.insert(ty, representability.clone());
+    representability
+}
+
+fn is_type_structurally_recursive_inner<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    sp: Span,
+    seen: &mut Vec<Ty<'tcx>>,
+    representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
+    ty: Ty<'tcx>,
+) -> Representability {
+    match ty.kind() {
+        ty::Adt(def, _) => {
+            {
+                // Iterate through stack of previously seen types.
+                let mut iter = seen.iter();
+
+                // The first item in `seen` is the type we are actually curious about.
+                // We want to return SelfRecursive if this type contains itself.
+                // It is important that we DON'T take generic parameters into account
+                // for this check, so that Bar<T> in this example counts as SelfRecursive:
+                //
+                // struct Foo;
+                // struct Bar<T> { x: Bar<Foo> }
+
+                if let Some(&seen_adt) = iter.next() {
+                    if same_adt(seen_adt, *def) {
+                        debug!("SelfRecursive: {:?} contains {:?}", seen_adt, ty);
+                        return Representability::SelfRecursive(vec![sp]);
+                    }
+                }
+
+                // We also need to know whether the first item contains other types
+                // that are structurally recursive. If we don't catch this case, we
+                // will recurse infinitely for some inputs.
+                //
+                // It is important that we DO take generic parameters into account
+                // here, so that code like this is considered SelfRecursive, not
+                // ContainsRecursive:
+                //
+                // struct Foo { Option<Option<Foo>> }
+
+                for &seen_adt in iter {
+                    if ty::TyS::same_type(ty, seen_adt) {
+                        debug!("ContainsRecursive: {:?} contains {:?}", seen_adt, ty);
+                        return Representability::ContainsRecursive;
+                    }
+                }
+            }
+
+            // For structs and enums, track all previously seen types by pushing them
+            // onto the 'seen' stack.
+            seen.push(ty);
+            let out = are_inner_types_recursive(tcx, sp, seen, representable_cache, ty);
+            seen.pop();
+            out
+        }
+        _ => {
+            // No need to push in other cases.
+            are_inner_types_recursive(tcx, sp, seen, representable_cache, ty)
+        }
+    }
+}
diff --git a/compiler/rustc_typeck/Cargo.toml b/compiler/rustc_typeck/Cargo.toml
index d92d317e34a..eb55a8a23ad 100644
--- a/compiler/rustc_typeck/Cargo.toml
+++ b/compiler/rustc_typeck/Cargo.toml
@@ -26,3 +26,4 @@ rustc_span = { path = "../rustc_span" }
 rustc_index = { path = "../rustc_index" }
 rustc_infer = { path = "../rustc_infer" }
 rustc_trait_selection = { path = "../rustc_trait_selection" }
+rustc_ty_utils = { path = "../rustc_ty_utils" }
diff --git a/compiler/rustc_typeck/src/check/check.rs b/compiler/rustc_typeck/src/check/check.rs
index 892abb5a344..72c633dcb20 100644
--- a/compiler/rustc_typeck/src/check/check.rs
+++ b/compiler/rustc_typeck/src/check/check.rs
@@ -15,7 +15,7 @@ use rustc_infer::infer::{RegionVariableOrigin, TyCtxtInferExt};
 use rustc_middle::ty::fold::TypeFoldable;
 use rustc_middle::ty::layout::MAX_SIMD_LANES;
 use rustc_middle::ty::subst::GenericArgKind;
-use rustc_middle::ty::util::{Discr, IntTypeExt, Representability};
+use rustc_middle::ty::util::{Discr, IntTypeExt};
 use rustc_middle::ty::{self, ParamEnv, RegionKind, ToPredicate, Ty, TyCtxt};
 use rustc_session::config::EntryFnType;
 use rustc_session::lint::builtin::UNINHABITED_STATIC;
@@ -25,6 +25,7 @@ use rustc_target::spec::abi::Abi;
 use rustc_trait_selection::opaque_types::InferCtxtExt as _;
 use rustc_trait_selection::traits::error_reporting::InferCtxtExt as _;
 use rustc_trait_selection::traits::{self, ObligationCauseCode};
+use rustc_ty_utils::representability::{self, Representability};
 
 use std::iter;
 use std::ops::ControlFlow;
@@ -1188,7 +1189,7 @@ pub(super) fn check_representable(tcx: TyCtxt<'_>, sp: Span, item_def_id: LocalD
     // recursive type. It is only necessary to throw an error on those that
     // contain themselves. For case 2, there must be an inner type that will be
     // caught by case 1.
-    match rty.is_representable(tcx, sp) {
+    match representability::ty_is_representable(tcx, rty, sp) {
         Representability::SelfRecursive(spans) => {
             recursive_type_with_infinite_size_error(tcx, item_def_id.to_def_id(), spans);
             return false;