Auto merge of #100720 - camsteffen:representable, r=cjgillot

Rewrite representability

 * Improve placement of `Box` in the suggestion
 * Multiple items in a cycle emit 1 error instead of an error for each item in the cycle
 * Introduce `representability` query to avoid traversing an item every time it is used.
 * Also introduce `params_in_repr` query to avoid traversing generic items every time it is used.

21 files changed, 341 insertions, 483 deletions

diff --git a/compiler/rustc_hir_analysis/Cargo.toml b/compiler/rustc_hir_analysis/Cargo.toml
index dd26b3da7bc..0761d8cdbd8 100644
--- a/compiler/rustc_hir_analysis/Cargo.toml
+++ b/compiler/rustc_hir_analysis/Cargo.toml
@@ -26,7 +26,6 @@ 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" }
 rustc_lint = { path = "../rustc_lint" }
 rustc_serialize = { path = "../rustc_serialize" }
 rustc_type_ir = { path = "../rustc_type_ir" }
diff --git a/compiler/rustc_hir_analysis/src/check/check.rs b/compiler/rustc_hir_analysis/src/check/check.rs
index da5d0706bc0..fea02d2356c 100644
--- a/compiler/rustc_hir_analysis/src/check/check.rs
+++ b/compiler/rustc_hir_analysis/src/check/check.rs
@@ -31,7 +31,6 @@ use rustc_span::{self, Span};
 use rustc_target::spec::abi::Abi;
 use rustc_trait_selection::traits::error_reporting::TypeErrCtxtExt as _;
 use rustc_trait_selection::traits::{self, ObligationCtxt};
-use rustc_ty_utils::representability::{self, Representability};
 
 use std::ops::ControlFlow;
 
@@ -381,7 +380,7 @@ fn check_struct(tcx: TyCtxt<'_>, def_id: LocalDefId) {
     let def = tcx.adt_def(def_id);
     let span = tcx.def_span(def_id);
     def.destructor(tcx); // force the destructor to be evaluated
-    check_representable(tcx, span, def_id);
+    let _ = tcx.representability(def_id);
 
     if def.repr().simd() {
         check_simd(tcx, span, def_id);
@@ -395,7 +394,7 @@ fn check_union(tcx: TyCtxt<'_>, def_id: LocalDefId) {
     let def = tcx.adt_def(def_id);
     let span = tcx.def_span(def_id);
     def.destructor(tcx); // force the destructor to be evaluated
-    check_representable(tcx, span, def_id);
+    let _ = tcx.representability(def_id);
     check_transparent(tcx, span, def);
     check_union_fields(tcx, span, def_id);
     check_packed(tcx, span, def);
@@ -1151,27 +1150,6 @@ fn check_impl_items_against_trait<'tcx>(
     }
 }
 
-/// Checks whether a type can be represented in memory. In particular, it
-/// identifies types that contain themselves without indirection through a
-/// pointer, which would mean their size is unbounded.
-pub(super) fn check_representable(tcx: TyCtxt<'_>, sp: Span, item_def_id: LocalDefId) -> bool {
-    let rty = tcx.type_of(item_def_id);
-
-    // Check that it is possible to represent this type. This call identifies
-    // (1) types that contain themselves and (2) types that contain a different
-    // 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 representability::ty_is_representable(tcx, rty, sp, None) {
-        Representability::SelfRecursive(spans) => {
-            recursive_type_with_infinite_size_error(tcx, item_def_id.to_def_id(), spans);
-            return false;
-        }
-        Representability::Representable | Representability::ContainsRecursive => (),
-    }
-    true
-}
-
 pub fn check_simd(tcx: TyCtxt<'_>, sp: Span, def_id: LocalDefId) {
     let t = tcx.type_of(def_id);
     if let ty::Adt(def, substs) = t.kind()
@@ -1509,7 +1487,7 @@ fn check_enum<'tcx>(tcx: TyCtxt<'tcx>, vs: &'tcx [hir::Variant<'tcx>], def_id: L
 
     detect_discriminant_duplicate(tcx, def.discriminants(tcx).collect(), vs, sp);
 
-    check_representable(tcx, sp, def_id);
+    let _ = tcx.representability(def_id);
     check_transparent(tcx, sp, def);
 }
 
diff --git a/compiler/rustc_hir_analysis/src/check/mod.rs b/compiler/rustc_hir_analysis/src/check/mod.rs
index 04e8c9c22d1..331bd7e26c8 100644
--- a/compiler/rustc_hir_analysis/src/check/mod.rs
+++ b/compiler/rustc_hir_analysis/src/check/mod.rs
@@ -123,7 +123,6 @@ use rustc_span::{self, BytePos, Span, Symbol};
 use rustc_target::abi::VariantIdx;
 use rustc_target::spec::abi::Abi;
 use rustc_trait_selection::traits;
-use rustc_trait_selection::traits::error_reporting::recursive_type_with_infinite_size_error;
 use rustc_trait_selection::traits::error_reporting::suggestions::ReturnsVisitor;
 use std::cell::RefCell;
 use std::num::NonZeroU32;
diff --git a/compiler/rustc_lint_defs/src/lib.rs b/compiler/rustc_lint_defs/src/lib.rs
index cbe7afc8e55..aa54b3d8ac2 100644
--- a/compiler/rustc_lint_defs/src/lib.rs
+++ b/compiler/rustc_lint_defs/src/lib.rs
@@ -25,6 +25,9 @@ macro_rules! pluralize {
     ($x:expr) => {
         if $x != 1 { "s" } else { "" }
     };
+    ("has", $x:expr) => {
+        if $x == 1 { "has" } else { "have" }
+    };
     ("is", $x:expr) => {
         if $x == 1 { "is" } else { "are" }
     };
diff --git a/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs b/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
index 466da175810..c4dff8b3f48 100644
--- a/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
+++ b/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
@@ -210,6 +210,7 @@ provide! { tcx, def_id, other, cdata,
     lookup_const_stability => { table }
     lookup_default_body_stability => { table }
     lookup_deprecation_entry => { table }
+    params_in_repr => { table }
     unused_generic_params => { table }
     opt_def_kind => { table_direct }
     impl_parent => { table }
diff --git a/compiler/rustc_metadata/src/rmeta/encoder.rs b/compiler/rustc_metadata/src/rmeta/encoder.rs
index 1a7a3c65c3b..3fc10197b91 100644
--- a/compiler/rustc_metadata/src/rmeta/encoder.rs
+++ b/compiler/rustc_metadata/src/rmeta/encoder.rs
@@ -1156,6 +1156,10 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
             if let DefKind::Trait | DefKind::TraitAlias = def_kind {
                 record!(self.tables.super_predicates_of[def_id] <- self.tcx.super_predicates_of(def_id));
             }
+            if let DefKind::Enum | DefKind::Struct | DefKind::Union = def_kind {
+                let params_in_repr = self.tcx.params_in_repr(def_id);
+                record!(self.tables.params_in_repr[def_id] <- params_in_repr);
+            }
             if should_encode_trait_impl_trait_tys(tcx, def_id)
                 && let Ok(table) = self.tcx.collect_trait_impl_trait_tys(def_id)
             {
diff --git a/compiler/rustc_metadata/src/rmeta/mod.rs b/compiler/rustc_metadata/src/rmeta/mod.rs
index 6d7345570af..a509ecdf759 100644
--- a/compiler/rustc_metadata/src/rmeta/mod.rs
+++ b/compiler/rustc_metadata/src/rmeta/mod.rs
@@ -13,7 +13,8 @@ use rustc_hir::def::{CtorKind, DefKind};
 use rustc_hir::def_id::{CrateNum, DefId, DefIndex, DefPathHash, StableCrateId};
 use rustc_hir::definitions::DefKey;
 use rustc_hir::lang_items;
-use rustc_index::{bit_set::FiniteBitSet, vec::IndexVec};
+use rustc_index::bit_set::{BitSet, FiniteBitSet};
+use rustc_index::vec::IndexVec;
 use rustc_middle::metadata::ModChild;
 use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrs;
 use rustc_middle::middle::exported_symbols::{ExportedSymbol, SymbolExportInfo};
@@ -383,6 +384,7 @@ define_tables! {
     inherent_impls: Table<DefIndex, LazyArray<DefIndex>>,
     expn_that_defined: Table<DefIndex, LazyValue<ExpnId>>,
     unused_generic_params: Table<DefIndex, LazyValue<FiniteBitSet<u32>>>,
+    params_in_repr: Table<DefIndex, LazyValue<BitSet<u32>>>,
     repr_options: Table<DefIndex, LazyValue<ReprOptions>>,
     // `def_keys` and `def_path_hashes` represent a lazy version of a
     // `DefPathTable`. This allows us to avoid deserializing an entire
diff --git a/compiler/rustc_middle/src/arena.rs b/compiler/rustc_middle/src/arena.rs
index 6bdf5a023b6..d2847e4bc12 100644
--- a/compiler/rustc_middle/src/arena.rs
+++ b/compiler/rustc_middle/src/arena.rs
@@ -103,6 +103,7 @@ macro_rules! arena_types {
             [] dep_kind: rustc_middle::dep_graph::DepKindStruct<'tcx>,
 
             [decode] trait_impl_trait_tys: rustc_data_structures::fx::FxHashMap<rustc_hir::def_id::DefId, rustc_middle::ty::Ty<'tcx>>,
+            [] bit_set_u32: rustc_index::bit_set::BitSet<u32>,
         ]);
     )
 }
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index 334eb953cbc..a175b1eb467 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -301,6 +301,32 @@ rustc_queries! {
         separate_provide_extern
     }
 
+    /// Checks whether a type is representable or infinitely sized
+    query representability(_: LocalDefId) -> rustc_middle::ty::Representability {
+        desc { "checking if {:?} is representable", tcx.def_path_str(key.to_def_id()) }
+        // infinitely sized types will cause a cycle
+        cycle_delay_bug
+        // we don't want recursive representability calls to be forced with
+        // incremental compilation because, if a cycle occurs, we need the
+        // entire cycle to be in memory for diagnostics
+        anon
+    }
+
+    /// An implementation detail for the `representability` query
+    query representability_adt_ty(_: Ty<'tcx>) -> rustc_middle::ty::Representability {
+        desc { "checking if {:?} is representable", key }
+        cycle_delay_bug
+        anon
+    }
+
+    /// Set of param indexes for type params that are in the type's representation
+    query params_in_repr(key: DefId) -> rustc_index::bit_set::BitSet<u32> {
+        desc { "finding type parameters in the representation" }
+        arena_cache
+        no_hash
+        separate_provide_extern
+    }
+
     /// Fetch the THIR for a given body. If typeck for that body failed, returns an empty `Thir`.
     query thir_body(key: ty::WithOptConstParam<LocalDefId>)
         -> Result<(&'tcx Steal<thir::Thir<'tcx>>, thir::ExprId), ErrorGuaranteed>
diff --git a/compiler/rustc_middle/src/ty/adt.rs b/compiler/rustc_middle/src/ty/adt.rs
index 3c485e26409..80bbc8e630e 100644
--- a/compiler/rustc_middle/src/ty/adt.rs
+++ b/compiler/rustc_middle/src/ty/adt.rs
@@ -566,3 +566,10 @@ impl<'tcx> AdtDef<'tcx> {
         ty::EarlyBinder(tcx.adt_sized_constraint(self.did()).0)
     }
 }
+
+#[derive(Clone, Copy, Debug)]
+#[derive(HashStable)]
+pub enum Representability {
+    Representable,
+    Infinite,
+}
diff --git a/compiler/rustc_middle/src/ty/parameterized.rs b/compiler/rustc_middle/src/ty/parameterized.rs
index 0257ca7b29c..f289f2265a2 100644
--- a/compiler/rustc_middle/src/ty/parameterized.rs
+++ b/compiler/rustc_middle/src/ty/parameterized.rs
@@ -82,6 +82,7 @@ trivially_parameterized_over_tcx! {
     rustc_hir::def::DefKind,
     rustc_hir::def_id::DefIndex,
     rustc_hir::definitions::DefKey,
+    rustc_index::bit_set::BitSet<u32>,
     rustc_index::bit_set::FiniteBitSet<u32>,
     rustc_session::cstore::ForeignModule,
     rustc_session::cstore::LinkagePreference,
diff --git a/compiler/rustc_middle/src/values.rs b/compiler/rustc_middle/src/values.rs
index 7fbe9ae2a84..bb89959b29d 100644
--- a/compiler/rustc_middle/src/values.rs
+++ b/compiler/rustc_middle/src/values.rs
@@ -1,8 +1,18 @@
-use rustc_middle::ty::{self, AdtSizedConstraint, Ty, TyCtxt};
+use rustc_data_structures::fx::FxHashSet;
+use rustc_errors::{pluralize, struct_span_err, Applicability, MultiSpan};
+use rustc_hir as hir;
+use rustc_hir::def::DefKind;
+use rustc_middle::ty::Representability;
+use rustc_middle::ty::{self, AdtSizedConstraint, DefIdTree, Ty, TyCtxt};
+use rustc_query_system::query::QueryInfo;
 use rustc_query_system::Value;
+use rustc_span::def_id::LocalDefId;
+use rustc_span::Span;
+
+use std::fmt::Write;
 
 impl<'tcx> Value<TyCtxt<'tcx>> for Ty<'_> {
-    fn from_cycle_error(tcx: TyCtxt<'tcx>) -> Self {
+    fn from_cycle_error(tcx: TyCtxt<'tcx>, _: &[QueryInfo]) -> Self {
         // SAFETY: This is never called when `Self` is not `Ty<'tcx>`.
         // FIXME: Represent the above fact in the trait system somehow.
         unsafe { std::mem::transmute::<Ty<'tcx>, Ty<'_>>(tcx.ty_error()) }
@@ -10,7 +20,7 @@ impl<'tcx> Value<TyCtxt<'tcx>> for Ty<'_> {
 }
 
 impl<'tcx> Value<TyCtxt<'tcx>> for ty::SymbolName<'_> {
-    fn from_cycle_error(tcx: TyCtxt<'tcx>) -> Self {
+    fn from_cycle_error(tcx: TyCtxt<'tcx>, _: &[QueryInfo]) -> Self {
         // SAFETY: This is never called when `Self` is not `SymbolName<'tcx>`.
         // FIXME: Represent the above fact in the trait system somehow.
         unsafe {
@@ -22,7 +32,7 @@ impl<'tcx> Value<TyCtxt<'tcx>> for ty::SymbolName<'_> {
 }
 
 impl<'tcx> Value<TyCtxt<'tcx>> for AdtSizedConstraint<'_> {
-    fn from_cycle_error(tcx: TyCtxt<'tcx>) -> Self {
+    fn from_cycle_error(tcx: TyCtxt<'tcx>, _: &[QueryInfo]) -> Self {
         // SAFETY: This is never called when `Self` is not `AdtSizedConstraint<'tcx>`.
         // FIXME: Represent the above fact in the trait system somehow.
         unsafe {
@@ -34,7 +44,7 @@ impl<'tcx> Value<TyCtxt<'tcx>> for AdtSizedConstraint<'_> {
 }
 
 impl<'tcx> Value<TyCtxt<'tcx>> for ty::Binder<'_, ty::FnSig<'_>> {
-    fn from_cycle_error(tcx: TyCtxt<'tcx>) -> Self {
+    fn from_cycle_error(tcx: TyCtxt<'tcx>, _: &[QueryInfo]) -> Self {
         let err = tcx.ty_error();
         // FIXME(compiler-errors): It would be nice if we could get the
         // query key, so we could at least generate a fn signature that
@@ -52,3 +62,153 @@ impl<'tcx> Value<TyCtxt<'tcx>> for ty::Binder<'_, ty::FnSig<'_>> {
         unsafe { std::mem::transmute::<ty::PolyFnSig<'tcx>, ty::Binder<'_, ty::FnSig<'_>>>(fn_sig) }
     }
 }
+
+impl<'tcx> Value<TyCtxt<'tcx>> for Representability {
+    fn from_cycle_error(tcx: TyCtxt<'tcx>, cycle: &[QueryInfo]) -> Self {
+        let mut item_and_field_ids = Vec::new();
+        let mut representable_ids = FxHashSet::default();
+        for info in cycle {
+            if info.query.name == "representability"
+                && let Some(field_id) = info.query.def_id
+                && let Some(field_id) = field_id.as_local()
+                && let Some(DefKind::Field) = info.query.def_kind
+            {
+                let parent_id = tcx.parent(field_id.to_def_id());
+                let item_id = match tcx.def_kind(parent_id) {
+                    DefKind::Variant => tcx.parent(parent_id),
+                    _ => parent_id,
+                };
+                item_and_field_ids.push((item_id.expect_local(), field_id));
+            }
+        }
+        for info in cycle {
+            if info.query.name == "representability_adt_ty"
+                && let Some(def_id) = info.query.ty_adt_id
+                && let Some(def_id) = def_id.as_local()
+                && !item_and_field_ids.iter().any(|&(id, _)| id == def_id)
+            {
+                representable_ids.insert(def_id);
+            }
+        }
+        recursive_type_error(tcx, item_and_field_ids, &representable_ids);
+        Representability::Infinite
+    }
+}
+
+// item_and_field_ids should form a cycle where each field contains the
+// type in the next element in the list
+pub fn recursive_type_error(
+    tcx: TyCtxt<'_>,
+    mut item_and_field_ids: Vec<(LocalDefId, LocalDefId)>,
+    representable_ids: &FxHashSet<LocalDefId>,
+) {
+    const ITEM_LIMIT: usize = 5;
+
+    // Rotate the cycle so that the item with the lowest span is first
+    let start_index = item_and_field_ids
+        .iter()
+        .enumerate()
+        .min_by_key(|&(_, &(id, _))| tcx.def_span(id))
+        .unwrap()
+        .0;
+    item_and_field_ids.rotate_left(start_index);
+
+    let cycle_len = item_and_field_ids.len();
+    let show_cycle_len = cycle_len.min(ITEM_LIMIT);
+
+    let mut err_span = MultiSpan::from_spans(
+        item_and_field_ids[..show_cycle_len]
+            .iter()
+            .map(|(id, _)| tcx.def_span(id.to_def_id()))
+            .collect(),
+    );
+    let mut suggestion = Vec::with_capacity(show_cycle_len * 2);
+    for i in 0..show_cycle_len {
+        let (_, field_id) = item_and_field_ids[i];
+        let (next_item_id, _) = item_and_field_ids[(i + 1) % cycle_len];
+        // Find the span(s) that contain the next item in the cycle
+        let hir_id = tcx.hir().local_def_id_to_hir_id(field_id);
+        let hir::Node::Field(field) = tcx.hir().get(hir_id) else { bug!("expected field") };
+        let mut found = Vec::new();
+        find_item_ty_spans(tcx, field.ty, next_item_id, &mut found, representable_ids);
+
+        // Couldn't find the type. Maybe it's behind a type alias?
+        // In any case, we'll just suggest boxing the whole field.
+        if found.is_empty() {
+            found.push(field.ty.span);
+        }
+
+        for span in found {
+            err_span.push_span_label(span, "recursive without indirection");
+            // FIXME(compiler-errors): This suggestion might be erroneous if Box is shadowed
+            suggestion.push((span.shrink_to_lo(), "Box<".to_string()));
+            suggestion.push((span.shrink_to_hi(), ">".to_string()));
+        }
+    }
+    let items_list = {
+        let mut s = String::new();
+        for (i, (item_id, _)) in item_and_field_ids.iter().enumerate() {
+            let path = tcx.def_path_str(item_id.to_def_id());
+            write!(&mut s, "`{path}`").unwrap();
+            if i == (ITEM_LIMIT - 1) && cycle_len > ITEM_LIMIT {
+                write!(&mut s, " and {} more", cycle_len - 5).unwrap();
+                break;
+            }
+            if cycle_len > 1 && i < cycle_len - 2 {
+                s.push_str(", ");
+            } else if cycle_len > 1 && i == cycle_len - 2 {
+                s.push_str(" and ")
+            }
+        }
+        s
+    };
+    let mut err = struct_span_err!(
+        tcx.sess,
+        err_span,
+        E0072,
+        "recursive type{} {} {} infinite size",
+        pluralize!(cycle_len),
+        items_list,
+        pluralize!("has", cycle_len),
+    );
+    err.multipart_suggestion(
+        "insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle",
+        suggestion,
+        Applicability::HasPlaceholders,
+    );
+    err.emit();
+}
+
+fn find_item_ty_spans(
+    tcx: TyCtxt<'_>,
+    ty: &hir::Ty<'_>,
+    needle: LocalDefId,
+    spans: &mut Vec<Span>,
+    seen_representable: &FxHashSet<LocalDefId>,
+) {
+    match ty.kind {
+        hir::TyKind::Path(hir::QPath::Resolved(_, path)) => {
+            if let Some(def_id) = path.res.opt_def_id() {
+                let check_params = def_id.as_local().map_or(true, |def_id| {
+                    if def_id == needle {
+                        spans.push(ty.span);
+                    }
+                    seen_representable.contains(&def_id)
+                });
+                if check_params && let Some(args) = path.segments.last().unwrap().args {
+                    let params_in_repr = tcx.params_in_repr(def_id);
+                    for (i, arg) in args.args.iter().enumerate() {
+                        if let hir::GenericArg::Type(ty) = arg && params_in_repr.contains(i as u32) {
+                            find_item_ty_spans(tcx, ty, needle, spans, seen_representable);
+                        }
+                    }
+                }
+            }
+        }
+        hir::TyKind::Array(ty, _) => find_item_ty_spans(tcx, ty, needle, spans, seen_representable),
+        hir::TyKind::Tup(tys) => {
+            tys.iter().for_each(|ty| find_item_ty_spans(tcx, ty, needle, spans, seen_representable))
+        }
+        _ => {}
+    }
+}
diff --git a/compiler/rustc_query_impl/src/keys.rs b/compiler/rustc_query_impl/src/keys.rs
index cdbf734cdbe..8be2e2be86b 100644
--- a/compiler/rustc_query_impl/src/keys.rs
+++ b/compiler/rustc_query_impl/src/keys.rs
@@ -27,6 +27,10 @@ pub trait Key {
     fn key_as_def_id(&self) -> Option<DefId> {
         None
     }
+
+    fn ty_adt_id(&self) -> Option<DefId> {
+        None
+    }
 }
 
 impl Key for () {
@@ -407,6 +411,12 @@ impl<'tcx> Key for Ty<'tcx> {
     fn default_span(&self, _: TyCtxt<'_>) -> Span {
         DUMMY_SP
     }
+    fn ty_adt_id(&self) -> Option<DefId> {
+        match self.kind() {
+            ty::Adt(adt, _) => Some(adt.did()),
+            _ => None,
+        }
+    }
 }
 
 impl<'tcx> Key for TyAndLayout<'tcx> {
diff --git a/compiler/rustc_query_impl/src/plumbing.rs b/compiler/rustc_query_impl/src/plumbing.rs
index 2b3850bc0df..aaeaa3bd51d 100644
--- a/compiler/rustc_query_impl/src/plumbing.rs
+++ b/compiler/rustc_query_impl/src/plumbing.rs
@@ -318,13 +318,12 @@ pub(crate) fn create_query_frame<
     } else {
         Some(key.default_span(*tcx))
     };
+    let def_id = key.key_as_def_id();
     let def_kind = if kind == dep_graph::DepKind::opt_def_kind {
         // Try to avoid infinite recursion.
         None
     } else {
-        key.key_as_def_id()
-            .and_then(|def_id| def_id.as_local())
-            .and_then(|def_id| tcx.opt_def_kind(def_id))
+        def_id.and_then(|def_id| def_id.as_local()).and_then(|def_id| tcx.opt_def_kind(def_id))
     };
     let hash = || {
         tcx.with_stable_hashing_context(|mut hcx| {
@@ -334,8 +333,9 @@ pub(crate) fn create_query_frame<
             hasher.finish::<u64>()
         })
     };
+    let ty_adt_id = key.ty_adt_id();
 
-    QueryStackFrame::new(name, description, span, def_kind, hash)
+    QueryStackFrame::new(name, description, span, def_id, def_kind, ty_adt_id, hash)
 }
 
 fn try_load_from_on_disk_cache<'tcx, Q>(tcx: TyCtxt<'tcx>, dep_node: DepNode)
diff --git a/compiler/rustc_query_system/src/query/job.rs b/compiler/rustc_query_system/src/query/job.rs
index 64aba4703ca..ed65393f57e 100644
--- a/compiler/rustc_query_system/src/query/job.rs
+++ b/compiler/rustc_query_system/src/query/job.rs
@@ -551,7 +551,7 @@ pub fn deadlock(query_map: QueryMap, registry: &rayon_core::Registry) {
 #[cold]
 pub(crate) fn report_cycle<'a>(
     sess: &'a Session,
-    CycleError { usage, cycle: stack }: CycleError,
+    CycleError { usage, cycle: stack }: &CycleError,
 ) -> DiagnosticBuilder<'a, ErrorGuaranteed> {
     assert!(!stack.is_empty());
 
@@ -569,10 +569,10 @@ pub(crate) fn report_cycle<'a>(
     }
 
     let mut cycle_usage = None;
-    if let Some((span, query)) = usage {
+    if let Some((span, ref query)) = *usage {
         cycle_usage = Some(crate::error::CycleUsage {
             span: query.default_span(span),
-            usage: query.description,
+            usage: query.description.to_string(),
         });
     }
 
diff --git a/compiler/rustc_query_system/src/query/mod.rs b/compiler/rustc_query_system/src/query/mod.rs
index 7a96c53b604..118703fc0d4 100644
--- a/compiler/rustc_query_system/src/query/mod.rs
+++ b/compiler/rustc_query_system/src/query/mod.rs
@@ -18,6 +18,7 @@ use crate::dep_graph::{DepNodeIndex, HasDepContext, SerializedDepNodeIndex};
 use rustc_data_structures::sync::Lock;
 use rustc_errors::Diagnostic;
 use rustc_hir::def::DefKind;
+use rustc_span::def_id::DefId;
 use rustc_span::Span;
 use thin_vec::ThinVec;
 
@@ -29,7 +30,9 @@ pub struct QueryStackFrame {
     pub name: &'static str,
     pub description: String,
     span: Option<Span>,
-    def_kind: Option<DefKind>,
+    pub def_id: Option<DefId>,
+    pub def_kind: Option<DefKind>,
+    pub ty_adt_id: Option<DefId>,
     /// This hash is used to deterministically pick
     /// a query to remove cycles in the parallel compiler.
     #[cfg(parallel_compiler)]
@@ -42,14 +45,18 @@ impl QueryStackFrame {
         name: &'static str,
         description: String,
         span: Option<Span>,
+        def_id: Option<DefId>,
         def_kind: Option<DefKind>,
+        ty_adt_id: Option<DefId>,
         _hash: impl FnOnce() -> u64,
     ) -> Self {
         Self {
             name,
             description,
             span,
+            def_id,
             def_kind,
+            ty_adt_id,
             #[cfg(parallel_compiler)]
             hash: _hash(),
         }
diff --git a/compiler/rustc_query_system/src/query/plumbing.rs b/compiler/rustc_query_system/src/query/plumbing.rs
index 8179a674afa..15b89daa6db 100644
--- a/compiler/rustc_query_system/src/query/plumbing.rs
+++ b/compiler/rustc_query_system/src/query/plumbing.rs
@@ -119,7 +119,7 @@ where
 #[inline(never)]
 fn mk_cycle<CTX, V, R>(
     tcx: CTX,
-    error: CycleError,
+    cycle_error: CycleError,
     handler: HandleCycleError,
     cache: &dyn crate::query::QueryStorage<Value = V, Stored = R>,
 ) -> R
@@ -128,13 +128,14 @@ where
     V: std::fmt::Debug + Value<CTX::DepContext>,
     R: Clone,
 {
-    let error = report_cycle(tcx.dep_context().sess(), error);
-    let value = handle_cycle_error(*tcx.dep_context(), error, handler);
+    let error = report_cycle(tcx.dep_context().sess(), &cycle_error);
+    let value = handle_cycle_error(*tcx.dep_context(), &cycle_error, error, handler);
     cache.store_nocache(value)
 }
 
 fn handle_cycle_error<CTX, V>(
     tcx: CTX,
+    cycle_error: &CycleError,
     mut error: DiagnosticBuilder<'_, ErrorGuaranteed>,
     handler: HandleCycleError,
 ) -> V
@@ -146,7 +147,7 @@ where
     match handler {
         Error => {
             error.emit();
-            Value::from_cycle_error(tcx)
+            Value::from_cycle_error(tcx, &cycle_error.cycle)
         }
         Fatal => {
             error.emit();
@@ -155,7 +156,7 @@ where
         }
         DelayBug => {
             error.delay_as_bug();
-            Value::from_cycle_error(tcx)
+            Value::from_cycle_error(tcx, &cycle_error.cycle)
         }
     }
 }
diff --git a/compiler/rustc_query_system/src/values.rs b/compiler/rustc_query_system/src/values.rs
index aeef66f86da..67fbf14e612 100644
--- a/compiler/rustc_query_system/src/values.rs
+++ b/compiler/rustc_query_system/src/values.rs
@@ -1,11 +1,12 @@
 use crate::dep_graph::DepContext;
+use crate::query::QueryInfo;
 
 pub trait Value<CTX: DepContext>: Sized {
-    fn from_cycle_error(tcx: CTX) -> Self;
+    fn from_cycle_error(tcx: CTX, cycle: &[QueryInfo]) -> Self;
 }
 
 impl<CTX: DepContext, T> Value<CTX> for T {
-    default fn from_cycle_error(tcx: CTX) -> T {
+    default fn from_cycle_error(tcx: CTX, _: &[QueryInfo]) -> T {
         tcx.sess().abort_if_errors();
         // Ideally we would use `bug!` here. But bug! is only defined in rustc_middle, and it's
         // non-trivial to define it earlier.
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
index 5b4fa1df426..22289657b81 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
@@ -2751,82 +2751,6 @@ impl<'v> Visitor<'v> for FindTypeParam {
     }
 }
 
-pub fn recursive_type_with_infinite_size_error<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    type_def_id: DefId,
-    spans: Vec<(Span, Option<hir::HirId>)>,
-) {
-    assert!(type_def_id.is_local());
-    let span = tcx.def_span(type_def_id);
-    let path = tcx.def_path_str(type_def_id);
-    let mut err =
-        struct_span_err!(tcx.sess, span, E0072, "recursive type `{}` has infinite size", path);
-    err.span_label(span, "recursive type has infinite size");
-    for &(span, _) in &spans {
-        err.span_label(span, "recursive without indirection");
-    }
-    let msg = format!(
-        "insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `{}` representable",
-        path,
-    );
-    if spans.len() <= 4 {
-        // FIXME(compiler-errors): This suggestion might be erroneous if Box is shadowed
-        err.multipart_suggestion(
-            &msg,
-            spans
-                .into_iter()
-                .flat_map(|(span, field_id)| {
-                    if let Some(generic_span) = get_option_generic_from_field_id(tcx, field_id) {
-                        // If we match an `Option` and can grab the span of the Option's generic, then
-                        // suggest boxing the generic arg for a non-null niche optimization.
-                        vec![
-                            (generic_span.shrink_to_lo(), "Box<".to_string()),
-                            (generic_span.shrink_to_hi(), ">".to_string()),
-                        ]
-                    } else {
-                        vec![
-                            (span.shrink_to_lo(), "Box<".to_string()),
-                            (span.shrink_to_hi(), ">".to_string()),
-                        ]
-                    }
-                })
-                .collect(),
-            Applicability::HasPlaceholders,
-        );
-    } else {
-        err.help(&msg);
-    }
-    err.emit();
-}
-
-/// Extract the span for the generic type `T` of `Option<T>` in a field definition
-fn get_option_generic_from_field_id(tcx: TyCtxt<'_>, field_id: Option<hir::HirId>) -> Option<Span> {
-    let node = tcx.hir().find(field_id?);
-
-    // Expect a field from our field_id
-    let Some(hir::Node::Field(field_def)) = node
-        else { bug!("Expected HirId corresponding to FieldDef, found: {:?}", node) };
-
-    // Match a type that is a simple QPath with no Self
-    let hir::TyKind::Path(hir::QPath::Resolved(None, path)) = &field_def.ty.kind
-        else { return None };
-
-    // Check if the path we're checking resolves to Option
-    let hir::def::Res::Def(_, did) = path.res
-        else { return None };
-
-    // Bail if this path doesn't describe `::core::option::Option`
-    if !tcx.is_diagnostic_item(sym::Option, did) {
-        return None;
-    }
-
-    // Match a single generic arg in the 0th path segment
-    let generic_arg = path.segments.last()?.args?.args.get(0)?;
-
-    // Take the span out of the type, if it's a type
-    if let hir::GenericArg::Type(generic_ty) = generic_arg { Some(generic_ty.span) } else { None }
-}
-
 /// Summarizes information
 #[derive(Clone)]
 pub enum ArgKind {
diff --git a/compiler/rustc_ty_utils/src/lib.rs b/compiler/rustc_ty_utils/src/lib.rs
index 0ddc154fbeb..cce5a79ddc8 100644
--- a/compiler/rustc_ty_utils/src/lib.rs
+++ b/compiler/rustc_ty_utils/src/lib.rs
@@ -39,6 +39,7 @@ pub fn provide(providers: &mut Providers) {
     implied_bounds::provide(providers);
     layout::provide(providers);
     needs_drop::provide(providers);
+    representability::provide(providers);
     ty::provide(providers);
     instance::provide(providers);
 }
diff --git a/compiler/rustc_ty_utils/src/representability.rs b/compiler/rustc_ty_utils/src/representability.rs
index eded7891682..7f48fb80417 100644
--- a/compiler/rustc_ty_utils/src/representability.rs
+++ b/compiler/rustc_ty_utils/src/representability.rs
@@ -1,386 +1,119 @@
-//! Check whether a type is representable.
-use rustc_data_structures::fx::FxHashMap;
-use rustc_hir as hir;
-use rustc_middle::ty::{self, Ty, TyCtxt};
-use rustc_span::Span;
-use std::cmp;
+#![allow(rustc::untranslatable_diagnostic, rustc::diagnostic_outside_of_impl)]
 
-/// 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,
-    /// Return a list of types that are included in themselves:
-    /// the spans where they are self-included, and (if found)
-    /// the HirId of the FieldDef that defines the self-inclusion.
-    SelfRecursive(Vec<(Span, Option<hir::HirId>)>),
-}
+use rustc_hir::def::DefKind;
+use rustc_index::bit_set::BitSet;
+use rustc_middle::ty::query::Providers;
+use rustc_middle::ty::{self, Representability, Ty, TyCtxt};
+use rustc_span::def_id::{DefId, LocalDefId};
 
-/// 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,
-    field_id: Option<hir::HirId>,
-) -> 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,
-    // #74224, #84611). `shadow_seen` contains the full stack and `seen` only
-    // the one for the current type (e.g. if we have structs A and B, B contains
-    // a field of type A, and we're currently looking at B, then `seen` will be
-    // cleared when recursing to check A, but `shadow_seen` won't, so that we
-    // can catch cases of mutual recursion where A also contains B).
-    let mut seen: Vec<Ty<'_>> = Vec::new();
-    let mut shadow_seen: Vec<ty::AdtDef<'tcx>> = Vec::new();
-    let mut representable_cache = FxHashMap::default();
-    let mut force_result = false;
-    let r = is_type_structurally_recursive(
-        tcx,
-        &mut seen,
-        &mut shadow_seen,
-        &mut representable_cache,
-        ty,
-        sp,
-        field_id,
-        &mut force_result,
-    );
-    debug!("is_type_representable: {:?} is {:?}", ty, r);
-    r
+pub fn provide(providers: &mut Providers) {
+    *providers =
+        Providers { representability, representability_adt_ty, params_in_repr, ..*providers };
 }
 
-// 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())
+macro_rules! rtry {
+    ($e:expr) => {
+        match $e {
+            e @ Representability::Infinite => return e,
+            Representability::Representable => {}
         }
-        (r1, r2) => cmp::max(r1, r2),
-    })
+    };
 }
 
-fn are_inner_types_recursive<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    seen: &mut Vec<Ty<'tcx>>,
-    shadow_seen: &mut Vec<ty::AdtDef<'tcx>>,
-    representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
-    ty: Ty<'tcx>,
-    sp: Span,
-    field_id: Option<hir::HirId>,
-    force_result: &mut bool,
-) -> Representability {
-    debug!("are_inner_types_recursive({:?}, {:?}, {:?})", ty, seen, shadow_seen);
-    match ty.kind() {
-        ty::Tuple(fields) => {
-            // Find non representable
-            fold_repr(fields.iter().map(|ty| {
-                is_type_structurally_recursive(
-                    tcx,
-                    seen,
-                    shadow_seen,
-                    representable_cache,
-                    ty,
-                    sp,
-                    field_id,
-                    force_result,
-                )
-            }))
-        }
-        // Fixed-length vectors.
-        // FIXME(#11924) Behavior undecided for zero-length vectors.
-        ty::Array(ty, _) => is_type_structurally_recursive(
-            tcx,
-            seen,
-            shadow_seen,
-            representable_cache,
-            *ty,
-            sp,
-            field_id,
-            force_result,
-        ),
-        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 (sp, field_id) = 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, Some(field.hir_id)),
-                    _ => (sp, field_id),
-                };
-
-                let mut result = None;
-
-                // First, we check whether the field type per se is representable.
-                // This catches cases as in #74224 and #84611. There is a special
-                // case related to mutual recursion, though; consider this example:
-                //
-                //   struct A<T> {
-                //       z: T,
-                //       x: B<T>,
-                //   }
-                //
-                //   struct B<T> {
-                //       y: A<T>
-                //   }
-                //
-                // Here, without the following special case, both A and B are
-                // ContainsRecursive, which is a problem because we only report
-                // errors for SelfRecursive. We fix this by detecting this special
-                // case (shadow_seen.first() is the type we are originally
-                // interested in, and if we ever encounter the same AdtDef again,
-                // we know that it must be SelfRecursive) and "forcibly" returning
-                // SelfRecursive (by setting force_result, which tells the calling
-                // invocations of are_inner_types_representable to forward the
-                // result without adjusting).
-                if shadow_seen.len() > seen.len() && shadow_seen.first() == Some(def) {
-                    *force_result = true;
-                    result = Some(Representability::SelfRecursive(vec![(sp, field_id)]));
-                }
-
-                if result == None {
-                    result = Some(Representability::Representable);
-
-                    // Now, we check whether the field types per se are representable, e.g.
-                    // for struct Foo { x: Option<Foo> }, we first check whether Option<_>
-                    // by itself is representable (which it is), and the nesting of Foo
-                    // will be detected later. This is necessary for #74224 and #84611.
-
-                    // If we have encountered an ADT definition that we have not seen
-                    // before (no need to check them twice), recurse to see whether that
-                    // definition is SelfRecursive. If so, we must be ContainsRecursive.
-                    if shadow_seen.len() > 1
-                        && !shadow_seen
-                            .iter()
-                            .take(shadow_seen.len() - 1)
-                            .any(|seen_def| seen_def == def)
-                    {
-                        let adt_def_id = def.did();
-                        let raw_adt_ty = tcx.type_of(adt_def_id);
-                        debug!("are_inner_types_recursive: checking nested type: {:?}", raw_adt_ty);
-
-                        // Check independently whether the ADT is SelfRecursive. If so,
-                        // we must be ContainsRecursive (except for the special case
-                        // mentioned above).
-                        let mut nested_seen: Vec<Ty<'_>> = vec![];
-                        result = Some(
-                            match is_type_structurally_recursive(
-                                tcx,
-                                &mut nested_seen,
-                                shadow_seen,
-                                representable_cache,
-                                raw_adt_ty,
-                                sp,
-                                field_id,
-                                force_result,
-                            ) {
-                                Representability::SelfRecursive(_) => {
-                                    if *force_result {
-                                        Representability::SelfRecursive(vec![(sp, field_id)])
-                                    } else {
-                                        Representability::ContainsRecursive
-                                    }
-                                }
-                                x => x,
-                            },
-                        );
-                    }
-
-                    // We only enter the following block if the type looks representable
-                    // so far. This is necessary for cases such as this one (#74224):
-                    //
-                    //   struct A<T> {
-                    //       x: T,
-                    //       y: A<A<T>>,
-                    //   }
-                    //
-                    //   struct B {
-                    //       z: A<usize>
-                    //   }
-                    //
-                    // When checking B, we recurse into A and check field y of type
-                    // A<A<usize>>. We haven't seen this exact type before, so we recurse
-                    // into A<A<usize>>, which contains, A<A<A<usize>>>, and so forth,
-                    // ad infinitum. We can prevent this from happening by first checking
-                    // A separately (the code above) and only checking for nested Bs if
-                    // A actually looks representable (which it wouldn't in this example).
-                    if result == Some(Representability::Representable) {
-                        // Now, even if the type is representable (e.g. Option<_>),
-                        // it might still contribute to a recursive type, e.g.:
-                        //   struct Foo { x: Option<Option<Foo>> }
-                        // These cases are handled by passing the full `seen`
-                        // stack to is_type_structurally_recursive (instead of the
-                        // empty `nested_seen` above):
-                        result = Some(
-                            match is_type_structurally_recursive(
-                                tcx,
-                                seen,
-                                shadow_seen,
-                                representable_cache,
-                                ty,
-                                sp,
-                                field_id,
-                                force_result,
-                            ) {
-                                Representability::SelfRecursive(_) => {
-                                    Representability::SelfRecursive(vec![(sp, field_id)])
-                                }
-                                x => x,
-                            },
-                        );
-                    }
+fn representability(tcx: TyCtxt<'_>, def_id: LocalDefId) -> Representability {
+    match tcx.def_kind(def_id) {
+        DefKind::Struct | DefKind::Union | DefKind::Enum => {
+            let adt_def = tcx.adt_def(def_id);
+            for variant in adt_def.variants() {
+                for field in variant.fields.iter() {
+                    rtry!(tcx.representability(field.did.expect_local()));
                 }
-
-                result.unwrap()
-            }))
-        }
-        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
         }
-        _ => Representability::Representable,
+        DefKind::Field => representability_ty(tcx, tcx.type_of(def_id)),
+        def_kind => bug!("unexpected {def_kind:?}"),
     }
 }
 
-fn same_adt<'tcx>(ty: Ty<'tcx>, def: ty::AdtDef<'tcx>) -> bool {
+fn representability_ty<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Representability {
     match *ty.kind() {
-        ty::Adt(ty_def, _) => ty_def == def,
-        _ => false,
+        ty::Adt(..) => tcx.representability_adt_ty(ty),
+        // FIXME(#11924) allow zero-length arrays?
+        ty::Array(ty, _) => representability_ty(tcx, ty),
+        ty::Tuple(tys) => {
+            for ty in tys {
+                rtry!(representability_ty(tcx, ty));
+            }
+            Representability::Representable
+        }
+        _ => Representability::Representable,
     }
 }
 
-// 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>,
-    seen: &mut Vec<Ty<'tcx>>,
-    shadow_seen: &mut Vec<ty::AdtDef<'tcx>>,
-    representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
-    ty: Ty<'tcx>,
-    sp: Span,
-    field_id: Option<hir::HirId>,
-    force_result: &mut bool,
-) -> Representability {
-    debug!("is_type_structurally_recursive: {:?} {:?} {:?}", ty, sp, field_id);
-    if let Some(representability) = representable_cache.get(&ty) {
-        debug!(
-            "is_type_structurally_recursive: {:?} {:?} {:?} - (cached) {:?}",
-            ty, sp, field_id, representability
-        );
-        return representability.clone();
+/*
+The reason for this being a separate query is very subtle:
+Consider this infinitely sized struct: `struct Foo(Box<Foo>, Bar<Foo>)`:
+When calling representability(Foo), a query cycle will occur:
+  representability(Foo)
+    -> representability_adt_ty(Bar<Foo>)
+    -> representability(Foo)
+For the diagnostic output (in `Value::from_cycle_error`), we want to detect that
+the `Foo` in the *second* field of the struct is culpable. This requires
+traversing the HIR of the struct and calling `params_in_repr(Bar)`. But we can't
+call params_in_repr for a given type unless it is known to be representable.
+params_in_repr will cycle/panic on infinitely sized types. Looking at the query
+cycle above, we know that `Bar` is representable because
+representability_adt_ty(Bar<..>) is in the cycle and representability(Bar) is
+*not* in the cycle.
+*/
+fn representability_adt_ty<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Representability {
+    let ty::Adt(adt, substs) = ty.kind() else { bug!("expected adt") };
+    if let Some(def_id) = adt.did().as_local() {
+        rtry!(tcx.representability(def_id));
     }
-
-    let representability = is_type_structurally_recursive_inner(
-        tcx,
-        seen,
-        shadow_seen,
-        representable_cache,
-        ty,
-        sp,
-        field_id,
-        force_result,
-    );
-
-    representable_cache.insert(ty, representability.clone());
-    representability
+    // At this point, we know that the item of the ADT type is representable;
+    // but the type parameters may cause a cycle with an upstream type
+    let params_in_repr = tcx.params_in_repr(adt.did());
+    for (i, subst) in substs.iter().enumerate() {
+        if let ty::GenericArgKind::Type(ty) = subst.unpack() {
+            if params_in_repr.contains(i as u32) {
+                rtry!(representability_ty(tcx, ty));
+            }
+        }
+    }
+    Representability::Representable
 }
 
-fn is_type_structurally_recursive_inner<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    seen: &mut Vec<Ty<'tcx>>,
-    shadow_seen: &mut Vec<ty::AdtDef<'tcx>>,
-    representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
-    ty: Ty<'tcx>,
-    sp: Span,
-    field_id: Option<hir::HirId>,
-    force_result: &mut bool,
-) -> Representability {
-    match ty.kind() {
-        ty::Adt(def, _) => {
-            {
-                debug!("is_type_structurally_recursive_inner: adt: {:?}, seen: {:?}", ty, seen);
-
-                // 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, field_id)]);
-                    }
-                }
-
-                // 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, because nesting e.g. Options is allowed (as long as the
-                // definition of Option doesn't itself include an Option field, which
-                // would be a case of SelfRecursive above). The following, too, counts
-                // as SelfRecursive:
-                //
-                // struct Foo { Option<Option<Foo>> }
+fn params_in_repr(tcx: TyCtxt<'_>, def_id: DefId) -> BitSet<u32> {
+    let adt_def = tcx.adt_def(def_id);
+    let generics = tcx.generics_of(def_id);
+    let mut params_in_repr = BitSet::new_empty(generics.params.len());
+    for variant in adt_def.variants() {
+        for field in variant.fields.iter() {
+            params_in_repr_ty(tcx, tcx.type_of(field.did), &mut params_in_repr);
+        }
+    }
+    params_in_repr
+}
 
-                for &seen_adt in iter {
-                    if ty == seen_adt {
-                        debug!("ContainsRecursive: {:?} contains {:?}", seen_adt, ty);
-                        return Representability::ContainsRecursive;
+fn params_in_repr_ty<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, params_in_repr: &mut BitSet<u32>) {
+    match *ty.kind() {
+        ty::Adt(adt, substs) => {
+            let inner_params_in_repr = tcx.params_in_repr(adt.did());
+            for (i, subst) in substs.iter().enumerate() {
+                if let ty::GenericArgKind::Type(ty) = subst.unpack() {
+                    if inner_params_in_repr.contains(i as u32) {
+                        params_in_repr_ty(tcx, ty, params_in_repr);
                     }
                 }
             }
-
-            // For structs and enums, track all previously seen types by pushing them
-            // onto the 'seen' stack.
-            seen.push(ty);
-            shadow_seen.push(*def);
-            let out = are_inner_types_recursive(
-                tcx,
-                seen,
-                shadow_seen,
-                representable_cache,
-                ty,
-                sp,
-                field_id,
-                force_result,
-            );
-            shadow_seen.pop();
-            seen.pop();
-            out
         }
-        _ => {
-            // No need to push in other cases.
-            are_inner_types_recursive(
-                tcx,
-                seen,
-                shadow_seen,
-                representable_cache,
-                ty,
-                sp,
-                field_id,
-                force_result,
-            )
+        ty::Array(ty, _) => params_in_repr_ty(tcx, ty, params_in_repr),
+        ty::Tuple(tys) => tys.iter().for_each(|ty| params_in_repr_ty(tcx, ty, params_in_repr)),
+        ty::Param(param) => {
+            params_in_repr.insert(param.index);
         }
+        _ => {}
     }
 }