Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

9 files changed, 2282 insertions, 0 deletions

diff --git a/compiler/rustc_ty_utils/Cargo.toml b/compiler/rustc_ty_utils/Cargo.toml
new file mode 100644
index 000000000..caad2ed42
--- /dev/null
+++ b/compiler/rustc_ty_utils/Cargo.toml
@@ -0,0 +1,18 @@
+[package]
+name = "rustc_ty_utils"
+version = "0.0.0"
+edition = "2021"
+
+[dependencies]
+tracing = "0.1"
+rustc_middle = { path = "../rustc_middle" }
+rustc_data_structures = { path = "../rustc_data_structures" }
+rustc_errors = { path = "../rustc_errors" }
+rustc_hir = { path = "../rustc_hir" }
+rustc_infer = { path = "../rustc_infer" }
+rustc_span = { path = "../rustc_span" }
+rustc_session = { path = "../rustc_session" }
+rustc_target = { path = "../rustc_target" }
+rustc_trait_selection = { path = "../rustc_trait_selection" }
+rustc_type_ir = { path = "../rustc_type_ir" }
+rustc_index = { path = "../rustc_index" }
diff --git a/compiler/rustc_ty_utils/src/assoc.rs b/compiler/rustc_ty_utils/src/assoc.rs
new file mode 100644
index 000000000..515a73ead
--- /dev/null
+++ b/compiler/rustc_ty_utils/src/assoc.rs
@@ -0,0 +1,111 @@
+use rustc_data_structures::fx::FxHashMap;
+use rustc_hir as hir;
+use rustc_hir::def_id::DefId;
+use rustc_middle::ty::{self, TyCtxt};
+
+pub fn provide(providers: &mut ty::query::Providers) {
+    *providers = ty::query::Providers {
+        associated_item,
+        associated_item_def_ids,
+        associated_items,
+        impl_item_implementor_ids,
+        ..*providers
+    };
+}
+
+fn associated_item_def_ids(tcx: TyCtxt<'_>, def_id: DefId) -> &[DefId] {
+    let item = tcx.hir().expect_item(def_id.expect_local());
+    match item.kind {
+        hir::ItemKind::Trait(.., ref trait_item_refs) => tcx.arena.alloc_from_iter(
+            trait_item_refs.iter().map(|trait_item_ref| trait_item_ref.id.def_id.to_def_id()),
+        ),
+        hir::ItemKind::Impl(ref impl_) => tcx.arena.alloc_from_iter(
+            impl_.items.iter().map(|impl_item_ref| impl_item_ref.id.def_id.to_def_id()),
+        ),
+        hir::ItemKind::TraitAlias(..) => &[],
+        _ => span_bug!(item.span, "associated_item_def_ids: not impl or trait"),
+    }
+}
+
+fn associated_items(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AssocItems<'_> {
+    let items = tcx.associated_item_def_ids(def_id).iter().map(|did| tcx.associated_item(*did));
+    ty::AssocItems::new(items)
+}
+
+fn impl_item_implementor_ids(tcx: TyCtxt<'_>, impl_id: DefId) -> FxHashMap<DefId, DefId> {
+    tcx.associated_items(impl_id)
+        .in_definition_order()
+        .filter_map(|item| item.trait_item_def_id.map(|trait_item| (trait_item, item.def_id)))
+        .collect()
+}
+
+fn associated_item(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AssocItem {
+    let id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());
+    let parent_def_id = tcx.hir().get_parent_item(id);
+    let parent_item = tcx.hir().expect_item(parent_def_id);
+    match parent_item.kind {
+        hir::ItemKind::Impl(ref impl_) => {
+            if let Some(impl_item_ref) =
+                impl_.items.iter().find(|i| i.id.def_id.to_def_id() == def_id)
+            {
+                let assoc_item = associated_item_from_impl_item_ref(impl_item_ref);
+                debug_assert_eq!(assoc_item.def_id, def_id);
+                return assoc_item;
+            }
+        }
+
+        hir::ItemKind::Trait(.., ref trait_item_refs) => {
+            if let Some(trait_item_ref) =
+                trait_item_refs.iter().find(|i| i.id.def_id.to_def_id() == def_id)
+            {
+                let assoc_item = associated_item_from_trait_item_ref(trait_item_ref);
+                debug_assert_eq!(assoc_item.def_id, def_id);
+                return assoc_item;
+            }
+        }
+
+        _ => {}
+    }
+
+    span_bug!(
+        parent_item.span,
+        "unexpected parent of trait or impl item or item not found: {:?}",
+        parent_item.kind
+    )
+}
+
+fn associated_item_from_trait_item_ref(trait_item_ref: &hir::TraitItemRef) -> ty::AssocItem {
+    let def_id = trait_item_ref.id.def_id;
+    let (kind, has_self) = match trait_item_ref.kind {
+        hir::AssocItemKind::Const => (ty::AssocKind::Const, false),
+        hir::AssocItemKind::Fn { has_self } => (ty::AssocKind::Fn, has_self),
+        hir::AssocItemKind::Type => (ty::AssocKind::Type, false),
+    };
+
+    ty::AssocItem {
+        name: trait_item_ref.ident.name,
+        kind,
+        def_id: def_id.to_def_id(),
+        trait_item_def_id: Some(def_id.to_def_id()),
+        container: ty::TraitContainer,
+        fn_has_self_parameter: has_self,
+    }
+}
+
+fn associated_item_from_impl_item_ref(impl_item_ref: &hir::ImplItemRef) -> ty::AssocItem {
+    let def_id = impl_item_ref.id.def_id;
+    let (kind, has_self) = match impl_item_ref.kind {
+        hir::AssocItemKind::Const => (ty::AssocKind::Const, false),
+        hir::AssocItemKind::Fn { has_self } => (ty::AssocKind::Fn, has_self),
+        hir::AssocItemKind::Type => (ty::AssocKind::Type, false),
+    };
+
+    ty::AssocItem {
+        name: impl_item_ref.ident.name,
+        kind,
+        def_id: def_id.to_def_id(),
+        trait_item_def_id: impl_item_ref.trait_item_def_id,
+        container: ty::ImplContainer,
+        fn_has_self_parameter: has_self,
+    }
+}
diff --git a/compiler/rustc_ty_utils/src/common_traits.rs b/compiler/rustc_ty_utils/src/common_traits.rs
new file mode 100644
index 000000000..cedc84d97
--- /dev/null
+++ b/compiler/rustc_ty_utils/src/common_traits.rs
@@ -0,0 +1,51 @@
+//! Queries for checking whether a type implements one of a few common traits.
+
+use rustc_hir::lang_items::LangItem;
+use rustc_infer::infer::TyCtxtInferExt;
+use rustc_middle::ty::{self, Ty, TyCtxt};
+use rustc_span::DUMMY_SP;
+use rustc_trait_selection::traits;
+
+fn is_copy_raw<'tcx>(tcx: TyCtxt<'tcx>, query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool {
+    is_item_raw(tcx, query, LangItem::Copy)
+}
+
+fn is_sized_raw<'tcx>(tcx: TyCtxt<'tcx>, query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool {
+    is_item_raw(tcx, query, LangItem::Sized)
+}
+
+fn is_freeze_raw<'tcx>(tcx: TyCtxt<'tcx>, query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool {
+    is_item_raw(tcx, query, LangItem::Freeze)
+}
+
+fn is_unpin_raw<'tcx>(tcx: TyCtxt<'tcx>, query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool {
+    is_item_raw(tcx, query, LangItem::Unpin)
+}
+
+fn is_item_raw<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>,
+    item: LangItem,
+) -> bool {
+    let (param_env, ty) = query.into_parts();
+    let trait_def_id = tcx.require_lang_item(item, None);
+    tcx.infer_ctxt().enter(|infcx| {
+        traits::type_known_to_meet_bound_modulo_regions(
+            &infcx,
+            param_env,
+            ty,
+            trait_def_id,
+            DUMMY_SP,
+        )
+    })
+}
+
+pub(crate) fn provide(providers: &mut ty::query::Providers) {
+    *providers = ty::query::Providers {
+        is_copy_raw,
+        is_sized_raw,
+        is_freeze_raw,
+        is_unpin_raw,
+        ..*providers
+    };
+}
diff --git a/compiler/rustc_ty_utils/src/consts.rs b/compiler/rustc_ty_utils/src/consts.rs
new file mode 100644
index 000000000..7c2f4db94
--- /dev/null
+++ b/compiler/rustc_ty_utils/src/consts.rs
@@ -0,0 +1,469 @@
+use rustc_errors::ErrorGuaranteed;
+use rustc_hir::def::DefKind;
+use rustc_hir::def_id::LocalDefId;
+use rustc_index::vec::IndexVec;
+use rustc_middle::mir::interpret::{LitToConstError, LitToConstInput};
+use rustc_middle::ty::abstract_const::{CastKind, Node, NodeId};
+use rustc_middle::ty::{self, TyCtxt, TypeVisitable};
+use rustc_middle::{mir, thir};
+use rustc_span::Span;
+use rustc_target::abi::VariantIdx;
+
+use std::iter;
+
+/// Destructures array, ADT or tuple constants into the constants
+/// of their fields.
+pub(crate) fn destructure_const<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    const_: ty::Const<'tcx>,
+) -> ty::DestructuredConst<'tcx> {
+    let ty::ConstKind::Value(valtree) = const_.kind() else {
+        bug!("cannot destructure constant {:?}", const_)
+    };
+
+    let branches = match valtree {
+        ty::ValTree::Branch(b) => b,
+        _ => bug!("cannot destructure constant {:?}", const_),
+    };
+
+    let (fields, variant) = match const_.ty().kind() {
+        ty::Array(inner_ty, _) | ty::Slice(inner_ty) => {
+            // construct the consts for the elements of the array/slice
+            let field_consts = branches
+                .iter()
+                .map(|b| tcx.mk_const(ty::ConstS { kind: ty::ConstKind::Value(*b), ty: *inner_ty }))
+                .collect::<Vec<_>>();
+            debug!(?field_consts);
+
+            (field_consts, None)
+        }
+        ty::Adt(def, _) if def.variants().is_empty() => bug!("unreachable"),
+        ty::Adt(def, substs) => {
+            let (variant_idx, branches) = if def.is_enum() {
+                let (head, rest) = branches.split_first().unwrap();
+                (VariantIdx::from_u32(head.unwrap_leaf().try_to_u32().unwrap()), rest)
+            } else {
+                (VariantIdx::from_u32(0), branches)
+            };
+            let fields = &def.variant(variant_idx).fields;
+            let mut field_consts = Vec::with_capacity(fields.len());
+
+            for (field, field_valtree) in iter::zip(fields, branches) {
+                let field_ty = field.ty(tcx, substs);
+                let field_const = tcx.mk_const(ty::ConstS {
+                    kind: ty::ConstKind::Value(*field_valtree),
+                    ty: field_ty,
+                });
+                field_consts.push(field_const);
+            }
+            debug!(?field_consts);
+
+            (field_consts, Some(variant_idx))
+        }
+        ty::Tuple(elem_tys) => {
+            let fields = iter::zip(*elem_tys, branches)
+                .map(|(elem_ty, elem_valtree)| {
+                    tcx.mk_const(ty::ConstS {
+                        kind: ty::ConstKind::Value(*elem_valtree),
+                        ty: elem_ty,
+                    })
+                })
+                .collect::<Vec<_>>();
+
+            (fields, None)
+        }
+        _ => bug!("cannot destructure constant {:?}", const_),
+    };
+
+    let fields = tcx.arena.alloc_from_iter(fields.into_iter());
+
+    ty::DestructuredConst { variant, fields }
+}
+
+pub struct AbstractConstBuilder<'a, 'tcx> {
+    tcx: TyCtxt<'tcx>,
+    body_id: thir::ExprId,
+    body: &'a thir::Thir<'tcx>,
+    /// The current WIP node tree.
+    nodes: IndexVec<NodeId, Node<'tcx>>,
+}
+
+impl<'a, 'tcx> AbstractConstBuilder<'a, 'tcx> {
+    fn root_span(&self) -> Span {
+        self.body.exprs[self.body_id].span
+    }
+
+    fn error(&mut self, span: Span, msg: &str) -> Result<!, ErrorGuaranteed> {
+        let reported = self
+            .tcx
+            .sess
+            .struct_span_err(self.root_span(), "overly complex generic constant")
+            .span_label(span, msg)
+            .help("consider moving this anonymous constant into a `const` function")
+            .emit();
+
+        Err(reported)
+    }
+    fn maybe_supported_error(&mut self, span: Span, msg: &str) -> Result<!, ErrorGuaranteed> {
+        let reported = self
+            .tcx
+            .sess
+            .struct_span_err(self.root_span(), "overly complex generic constant")
+            .span_label(span, msg)
+            .help("consider moving this anonymous constant into a `const` function")
+            .note("this operation may be supported in the future")
+            .emit();
+
+        Err(reported)
+    }
+
+    #[instrument(skip(tcx, body, body_id), level = "debug")]
+    pub fn new(
+        tcx: TyCtxt<'tcx>,
+        (body, body_id): (&'a thir::Thir<'tcx>, thir::ExprId),
+    ) -> Result<Option<AbstractConstBuilder<'a, 'tcx>>, ErrorGuaranteed> {
+        let builder = AbstractConstBuilder { tcx, body_id, body, nodes: IndexVec::new() };
+
+        struct IsThirPolymorphic<'a, 'tcx> {
+            is_poly: bool,
+            thir: &'a thir::Thir<'tcx>,
+        }
+
+        use crate::rustc_middle::thir::visit::Visitor;
+        use thir::visit;
+
+        impl<'a, 'tcx> IsThirPolymorphic<'a, 'tcx> {
+            fn expr_is_poly(&mut self, expr: &thir::Expr<'tcx>) -> bool {
+                if expr.ty.has_param_types_or_consts() {
+                    return true;
+                }
+
+                match expr.kind {
+                    thir::ExprKind::NamedConst { substs, .. } => substs.has_param_types_or_consts(),
+                    thir::ExprKind::ConstParam { .. } => true,
+                    thir::ExprKind::Repeat { value, count } => {
+                        self.visit_expr(&self.thir()[value]);
+                        count.has_param_types_or_consts()
+                    }
+                    _ => false,
+                }
+            }
+
+            fn pat_is_poly(&mut self, pat: &thir::Pat<'tcx>) -> bool {
+                if pat.ty.has_param_types_or_consts() {
+                    return true;
+                }
+
+                match pat.kind.as_ref() {
+                    thir::PatKind::Constant { value } => value.has_param_types_or_consts(),
+                    thir::PatKind::Range(thir::PatRange { lo, hi, .. }) => {
+                        lo.has_param_types_or_consts() || hi.has_param_types_or_consts()
+                    }
+                    _ => false,
+                }
+            }
+        }
+
+        impl<'a, 'tcx> visit::Visitor<'a, 'tcx> for IsThirPolymorphic<'a, 'tcx> {
+            fn thir(&self) -> &'a thir::Thir<'tcx> {
+                &self.thir
+            }
+
+            #[instrument(skip(self), level = "debug")]
+            fn visit_expr(&mut self, expr: &thir::Expr<'tcx>) {
+                self.is_poly |= self.expr_is_poly(expr);
+                if !self.is_poly {
+                    visit::walk_expr(self, expr)
+                }
+            }
+
+            #[instrument(skip(self), level = "debug")]
+            fn visit_pat(&mut self, pat: &thir::Pat<'tcx>) {
+                self.is_poly |= self.pat_is_poly(pat);
+                if !self.is_poly {
+                    visit::walk_pat(self, pat);
+                }
+            }
+        }
+
+        let mut is_poly_vis = IsThirPolymorphic { is_poly: false, thir: body };
+        visit::walk_expr(&mut is_poly_vis, &body[body_id]);
+        debug!("AbstractConstBuilder: is_poly={}", is_poly_vis.is_poly);
+        if !is_poly_vis.is_poly {
+            return Ok(None);
+        }
+
+        Ok(Some(builder))
+    }
+
+    /// We do not allow all binary operations in abstract consts, so filter disallowed ones.
+    fn check_binop(op: mir::BinOp) -> bool {
+        use mir::BinOp::*;
+        match op {
+            Add | Sub | Mul | Div | Rem | BitXor | BitAnd | BitOr | Shl | Shr | Eq | Lt | Le
+            | Ne | Ge | Gt => true,
+            Offset => false,
+        }
+    }
+
+    /// While we currently allow all unary operations, we still want to explicitly guard against
+    /// future changes here.
+    fn check_unop(op: mir::UnOp) -> bool {
+        use mir::UnOp::*;
+        match op {
+            Not | Neg => true,
+        }
+    }
+
+    /// Builds the abstract const by walking the thir and bailing out when
+    /// encountering an unsupported operation.
+    pub fn build(mut self) -> Result<&'tcx [Node<'tcx>], ErrorGuaranteed> {
+        debug!("AbstractConstBuilder::build: body={:?}", &*self.body);
+        self.recurse_build(self.body_id)?;
+
+        for n in self.nodes.iter() {
+            if let Node::Leaf(ct) = n {
+                if let ty::ConstKind::Unevaluated(ct) = ct.kind() {
+                    // `AbstractConst`s should not contain any promoteds as they require references which
+                    // are not allowed.
+                    assert_eq!(ct.promoted, None);
+                    assert_eq!(ct, self.tcx.erase_regions(ct));
+                }
+            }
+        }
+
+        Ok(self.tcx.arena.alloc_from_iter(self.nodes.into_iter()))
+    }
+
+    fn recurse_build(&mut self, node: thir::ExprId) -> Result<NodeId, ErrorGuaranteed> {
+        use thir::ExprKind;
+        let node = &self.body.exprs[node];
+        Ok(match &node.kind {
+            // I dont know if handling of these 3 is correct
+            &ExprKind::Scope { value, .. } => self.recurse_build(value)?,
+            &ExprKind::PlaceTypeAscription { source, .. }
+            | &ExprKind::ValueTypeAscription { source, .. } => self.recurse_build(source)?,
+            &ExprKind::Literal { lit, neg} => {
+                let sp = node.span;
+                let constant =
+                    match self.tcx.at(sp).lit_to_const(LitToConstInput { lit: &lit.node, ty: node.ty, neg }) {
+                        Ok(c) => c,
+                        Err(LitToConstError::Reported) => {
+                            self.tcx.const_error(node.ty)
+                        }
+                        Err(LitToConstError::TypeError) => {
+                            bug!("encountered type error in lit_to_const")
+                        }
+                    };
+
+                self.nodes.push(Node::Leaf(constant))
+            }
+            &ExprKind::NonHirLiteral { lit , user_ty: _} => {
+                let val = ty::ValTree::from_scalar_int(lit);
+                self.nodes.push(Node::Leaf(ty::Const::from_value(self.tcx, val, node.ty)))
+            }
+            &ExprKind::ZstLiteral { user_ty: _ } => {
+                let val = ty::ValTree::zst();
+                self.nodes.push(Node::Leaf(ty::Const::from_value(self.tcx, val, node.ty)))
+            }
+            &ExprKind::NamedConst { def_id, substs, user_ty: _ } => {
+                let uneval = ty::Unevaluated::new(ty::WithOptConstParam::unknown(def_id), substs);
+
+                let constant = self.tcx.mk_const(ty::ConstS {
+                                kind: ty::ConstKind::Unevaluated(uneval),
+                                ty: node.ty,
+                            });
+
+                self.nodes.push(Node::Leaf(constant))
+            }
+
+            ExprKind::ConstParam {param, ..} => {
+                let const_param = self.tcx.mk_const(ty::ConstS {
+                        kind: ty::ConstKind::Param(*param),
+                        ty: node.ty,
+                    });
+                self.nodes.push(Node::Leaf(const_param))
+            }
+
+            ExprKind::Call { fun, args, .. } => {
+                let fun = self.recurse_build(*fun)?;
+
+                let mut new_args = Vec::<NodeId>::with_capacity(args.len());
+                for &id in args.iter() {
+                    new_args.push(self.recurse_build(id)?);
+                }
+                let new_args = self.tcx.arena.alloc_slice(&new_args);
+                self.nodes.push(Node::FunctionCall(fun, new_args))
+            }
+            &ExprKind::Binary { op, lhs, rhs } if Self::check_binop(op) => {
+                let lhs = self.recurse_build(lhs)?;
+                let rhs = self.recurse_build(rhs)?;
+                self.nodes.push(Node::Binop(op, lhs, rhs))
+            }
+            &ExprKind::Unary { op, arg } if Self::check_unop(op) => {
+                let arg = self.recurse_build(arg)?;
+                self.nodes.push(Node::UnaryOp(op, arg))
+            }
+            // This is necessary so that the following compiles:
+            //
+            // ```
+            // fn foo<const N: usize>(a: [(); N + 1]) {
+            //     bar::<{ N + 1 }>();
+            // }
+            // ```
+            ExprKind::Block { body: thir::Block { stmts: box [], expr: Some(e), .. } } => {
+                self.recurse_build(*e)?
+            }
+            // `ExprKind::Use` happens when a `hir::ExprKind::Cast` is a
+            // "coercion cast" i.e. using a coercion or is a no-op.
+            // This is important so that `N as usize as usize` doesnt unify with `N as usize`. (untested)
+            &ExprKind::Use { source } => {
+                let arg = self.recurse_build(source)?;
+                self.nodes.push(Node::Cast(CastKind::Use, arg, node.ty))
+            }
+            &ExprKind::Cast { source } => {
+                let arg = self.recurse_build(source)?;
+                self.nodes.push(Node::Cast(CastKind::As, arg, node.ty))
+            }
+            ExprKind::Borrow{ arg, ..} => {
+                let arg_node = &self.body.exprs[*arg];
+
+                // Skip reborrows for now until we allow Deref/Borrow/AddressOf
+                // expressions.
+                // FIXME(generic_const_exprs): Verify/explain why this is sound
+                if let ExprKind::Deref { arg } = arg_node.kind {
+                    self.recurse_build(arg)?
+                } else {
+                    self.maybe_supported_error(
+                        node.span,
+                        "borrowing is not supported in generic constants",
+                    )?
+                }
+            }
+            // FIXME(generic_const_exprs): We may want to support these.
+            ExprKind::AddressOf { .. } | ExprKind::Deref {..}=> self.maybe_supported_error(
+                node.span,
+                "dereferencing or taking the address is not supported in generic constants",
+            )?,
+            ExprKind::Repeat { .. } | ExprKind::Array { .. } =>  self.maybe_supported_error(
+                node.span,
+                "array construction is not supported in generic constants",
+            )?,
+            ExprKind::Block { .. } => self.maybe_supported_error(
+                node.span,
+                "blocks are not supported in generic constant",
+            )?,
+            ExprKind::NeverToAny { .. } => self.maybe_supported_error(
+                node.span,
+                "converting nevers to any is not supported in generic constant",
+            )?,
+            ExprKind::Tuple { .. } => self.maybe_supported_error(
+                node.span,
+                "tuple construction is not supported in generic constants",
+            )?,
+            ExprKind::Index { .. } => self.maybe_supported_error(
+                node.span,
+                "indexing is not supported in generic constant",
+            )?,
+            ExprKind::Field { .. } => self.maybe_supported_error(
+                node.span,
+                "field access is not supported in generic constant",
+            )?,
+            ExprKind::ConstBlock { .. } => self.maybe_supported_error(
+                node.span,
+                "const blocks are not supported in generic constant",
+            )?,
+            ExprKind::Adt(_) => self.maybe_supported_error(
+                node.span,
+                "struct/enum construction is not supported in generic constants",
+            )?,
+            // dont know if this is correct
+            ExprKind::Pointer { .. } =>
+                self.error(node.span, "pointer casts are not allowed in generic constants")?,
+            ExprKind::Yield { .. } =>
+                self.error(node.span, "generator control flow is not allowed in generic constants")?,
+            ExprKind::Continue { .. } | ExprKind::Break { .. } | ExprKind::Loop { .. } => self
+                .error(
+                    node.span,
+                    "loops and loop control flow are not supported in generic constants",
+                )?,
+            ExprKind::Box { .. } =>
+                self.error(node.span, "allocations are not allowed in generic constants")?,
+
+            ExprKind::Unary { .. } => unreachable!(),
+            // we handle valid unary/binary ops above
+            ExprKind::Binary { .. } =>
+                self.error(node.span, "unsupported binary operation in generic constants")?,
+            ExprKind::LogicalOp { .. } =>
+                self.error(node.span, "unsupported operation in generic constants, short-circuiting operations would imply control flow")?,
+            ExprKind::Assign { .. } | ExprKind::AssignOp { .. } => {
+                self.error(node.span, "assignment is not supported in generic constants")?
+            }
+            ExprKind::Closure { .. } | ExprKind::Return { .. } => self.error(
+                node.span,
+                "closures and function keywords are not supported in generic constants",
+            )?,
+            // let expressions imply control flow
+            ExprKind::Match { .. } | ExprKind::If { .. } | ExprKind::Let { .. } =>
+                self.error(node.span, "control flow is not supported in generic constants")?,
+            ExprKind::InlineAsm { .. } => {
+                self.error(node.span, "assembly is not supported in generic constants")?
+            }
+
+            // we dont permit let stmts so `VarRef` and `UpvarRef` cant happen
+            ExprKind::VarRef { .. }
+            | ExprKind::UpvarRef { .. }
+            | ExprKind::StaticRef { .. }
+            | ExprKind::ThreadLocalRef(_) => {
+                self.error(node.span, "unsupported operation in generic constant")?
+            }
+        })
+    }
+}
+
+/// Builds an abstract const, do not use this directly, but use `AbstractConst::new` instead.
+pub fn thir_abstract_const<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    def: ty::WithOptConstParam<LocalDefId>,
+) -> Result<Option<&'tcx [Node<'tcx>]>, ErrorGuaranteed> {
+    if tcx.features().generic_const_exprs {
+        match tcx.def_kind(def.did) {
+            // FIXME(generic_const_exprs): We currently only do this for anonymous constants,
+            // meaning that we do not look into associated constants. I(@lcnr) am not yet sure whether
+            // we want to look into them or treat them as opaque projections.
+            //
+            // Right now we do neither of that and simply always fail to unify them.
+            DefKind::AnonConst | DefKind::InlineConst => (),
+            _ => return Ok(None),
+        }
+
+        let body = tcx.thir_body(def)?;
+
+        AbstractConstBuilder::new(tcx, (&*body.0.borrow(), body.1))?
+            .map(AbstractConstBuilder::build)
+            .transpose()
+    } else {
+        Ok(None)
+    }
+}
+
+pub fn provide(providers: &mut ty::query::Providers) {
+    *providers = ty::query::Providers {
+        destructure_const,
+        thir_abstract_const: |tcx, def_id| {
+            let def_id = def_id.expect_local();
+            if let Some(def) = ty::WithOptConstParam::try_lookup(def_id, tcx) {
+                tcx.thir_abstract_const_of_const_arg(def)
+            } else {
+                thir_abstract_const(tcx, ty::WithOptConstParam::unknown(def_id))
+            }
+        },
+        thir_abstract_const_of_const_arg: |tcx, (did, param_did)| {
+            thir_abstract_const(
+                tcx,
+                ty::WithOptConstParam { did, const_param_did: Some(param_did) },
+            )
+        },
+        ..*providers
+    };
+}
diff --git a/compiler/rustc_ty_utils/src/instance.rs b/compiler/rustc_ty_utils/src/instance.rs
new file mode 100644
index 000000000..bd1d568cd
--- /dev/null
+++ b/compiler/rustc_ty_utils/src/instance.rs
@@ -0,0 +1,407 @@
+use rustc_errors::ErrorGuaranteed;
+use rustc_hir::def_id::{DefId, LocalDefId};
+use rustc_infer::infer::TyCtxtInferExt;
+use rustc_middle::traits::CodegenObligationError;
+use rustc_middle::ty::subst::SubstsRef;
+use rustc_middle::ty::{
+    self, Binder, Instance, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor,
+};
+use rustc_span::{sym, DUMMY_SP};
+use rustc_trait_selection::traits;
+use traits::{translate_substs, Reveal};
+
+use rustc_data_structures::sso::SsoHashSet;
+use std::collections::btree_map::Entry;
+use std::collections::BTreeMap;
+use std::ops::ControlFlow;
+
+use tracing::debug;
+
+// FIXME(#86795): `BoundVarsCollector` here should **NOT** be used
+// outside of `resolve_associated_item`. It's just to address #64494,
+// #83765, and #85848 which are creating bound types/regions that lose
+// their `Binder` *unintentionally*.
+// It's ideal to remove `BoundVarsCollector` and just use
+// `ty::Binder::*` methods but we use this stopgap until we figure out
+// the "real" fix.
+struct BoundVarsCollector<'tcx> {
+    binder_index: ty::DebruijnIndex,
+    vars: BTreeMap<u32, ty::BoundVariableKind>,
+    // We may encounter the same variable at different levels of binding, so
+    // this can't just be `Ty`
+    visited: SsoHashSet<(ty::DebruijnIndex, Ty<'tcx>)>,
+}
+
+impl<'tcx> BoundVarsCollector<'tcx> {
+    fn new() -> Self {
+        BoundVarsCollector {
+            binder_index: ty::INNERMOST,
+            vars: BTreeMap::new(),
+            visited: SsoHashSet::default(),
+        }
+    }
+
+    fn into_vars(self, tcx: TyCtxt<'tcx>) -> &'tcx ty::List<ty::BoundVariableKind> {
+        let max = self.vars.iter().map(|(k, _)| *k).max().unwrap_or(0);
+        for i in 0..max {
+            if let None = self.vars.get(&i) {
+                panic!("Unknown variable: {:?}", i);
+            }
+        }
+
+        tcx.mk_bound_variable_kinds(self.vars.into_iter().map(|(_, v)| v))
+    }
+}
+
+impl<'tcx> TypeVisitor<'tcx> for BoundVarsCollector<'tcx> {
+    type BreakTy = ();
+
+    fn visit_binder<T: TypeVisitable<'tcx>>(
+        &mut self,
+        t: &Binder<'tcx, T>,
+    ) -> ControlFlow<Self::BreakTy> {
+        self.binder_index.shift_in(1);
+        let result = t.super_visit_with(self);
+        self.binder_index.shift_out(1);
+        result
+    }
+
+    fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+        if t.outer_exclusive_binder() < self.binder_index
+            || !self.visited.insert((self.binder_index, t))
+        {
+            return ControlFlow::CONTINUE;
+        }
+        match *t.kind() {
+            ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
+                match self.vars.entry(bound_ty.var.as_u32()) {
+                    Entry::Vacant(entry) => {
+                        entry.insert(ty::BoundVariableKind::Ty(bound_ty.kind));
+                    }
+                    Entry::Occupied(entry) => match entry.get() {
+                        ty::BoundVariableKind::Ty(_) => {}
+                        _ => bug!("Conflicting bound vars"),
+                    },
+                }
+            }
+
+            _ => (),
+        };
+
+        t.super_visit_with(self)
+    }
+
+    fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
+        match *r {
+            ty::ReLateBound(index, br) if index == self.binder_index => {
+                match self.vars.entry(br.var.as_u32()) {
+                    Entry::Vacant(entry) => {
+                        entry.insert(ty::BoundVariableKind::Region(br.kind));
+                    }
+                    Entry::Occupied(entry) => match entry.get() {
+                        ty::BoundVariableKind::Region(_) => {}
+                        _ => bug!("Conflicting bound vars"),
+                    },
+                }
+            }
+
+            _ => (),
+        };
+
+        r.super_visit_with(self)
+    }
+}
+
+fn resolve_instance<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    key: ty::ParamEnvAnd<'tcx, (DefId, SubstsRef<'tcx>)>,
+) -> Result<Option<Instance<'tcx>>, ErrorGuaranteed> {
+    let (param_env, (did, substs)) = key.into_parts();
+    if let Some(did) = did.as_local() {
+        if let Some(param_did) = tcx.opt_const_param_of(did) {
+            return tcx.resolve_instance_of_const_arg(param_env.and((did, param_did, substs)));
+        }
+    }
+
+    inner_resolve_instance(tcx, param_env.and((ty::WithOptConstParam::unknown(did), substs)))
+}
+
+fn resolve_instance_of_const_arg<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    key: ty::ParamEnvAnd<'tcx, (LocalDefId, DefId, SubstsRef<'tcx>)>,
+) -> Result<Option<Instance<'tcx>>, ErrorGuaranteed> {
+    let (param_env, (did, const_param_did, substs)) = key.into_parts();
+    inner_resolve_instance(
+        tcx,
+        param_env.and((
+            ty::WithOptConstParam { did: did.to_def_id(), const_param_did: Some(const_param_did) },
+            substs,
+        )),
+    )
+}
+
+fn inner_resolve_instance<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    key: ty::ParamEnvAnd<'tcx, (ty::WithOptConstParam<DefId>, SubstsRef<'tcx>)>,
+) -> Result<Option<Instance<'tcx>>, ErrorGuaranteed> {
+    let (param_env, (def, substs)) = key.into_parts();
+
+    let result = if let Some(trait_def_id) = tcx.trait_of_item(def.did) {
+        debug!(" => associated item, attempting to find impl in param_env {:#?}", param_env);
+        resolve_associated_item(tcx, def.did, param_env, trait_def_id, substs)
+    } else {
+        let ty = tcx.type_of(def.def_id_for_type_of());
+        let item_type = tcx.subst_and_normalize_erasing_regions(substs, param_env, ty);
+
+        let def = match *item_type.kind() {
+            ty::FnDef(def_id, ..) if tcx.is_intrinsic(def_id) => {
+                debug!(" => intrinsic");
+                ty::InstanceDef::Intrinsic(def.did)
+            }
+            ty::FnDef(def_id, substs) if Some(def_id) == tcx.lang_items().drop_in_place_fn() => {
+                let ty = substs.type_at(0);
+
+                if ty.needs_drop(tcx, param_env) {
+                    debug!(" => nontrivial drop glue");
+                    match *ty.kind() {
+                        ty::Closure(..)
+                        | ty::Generator(..)
+                        | ty::Tuple(..)
+                        | ty::Adt(..)
+                        | ty::Dynamic(..)
+                        | ty::Array(..)
+                        | ty::Slice(..) => {}
+                        // Drop shims can only be built from ADTs.
+                        _ => return Ok(None),
+                    }
+
+                    ty::InstanceDef::DropGlue(def_id, Some(ty))
+                } else {
+                    debug!(" => trivial drop glue");
+                    ty::InstanceDef::DropGlue(def_id, None)
+                }
+            }
+            _ => {
+                debug!(" => free item");
+                ty::InstanceDef::Item(def)
+            }
+        };
+        Ok(Some(Instance { def, substs }))
+    };
+    debug!("inner_resolve_instance: result={:?}", result);
+    result
+}
+
+fn resolve_associated_item<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    trait_item_id: DefId,
+    param_env: ty::ParamEnv<'tcx>,
+    trait_id: DefId,
+    rcvr_substs: SubstsRef<'tcx>,
+) -> Result<Option<Instance<'tcx>>, ErrorGuaranteed> {
+    debug!(?trait_item_id, ?param_env, ?trait_id, ?rcvr_substs, "resolve_associated_item");
+
+    let trait_ref = ty::TraitRef::from_method(tcx, trait_id, rcvr_substs);
+
+    // See FIXME on `BoundVarsCollector`.
+    let mut bound_vars_collector = BoundVarsCollector::new();
+    trait_ref.visit_with(&mut bound_vars_collector);
+    let trait_binder = ty::Binder::bind_with_vars(trait_ref, bound_vars_collector.into_vars(tcx));
+    let vtbl = match tcx.codegen_fulfill_obligation((param_env, trait_binder)) {
+        Ok(vtbl) => vtbl,
+        Err(CodegenObligationError::Ambiguity) => {
+            let reported = tcx.sess.delay_span_bug(
+                tcx.def_span(trait_item_id),
+                &format!(
+                    "encountered ambiguity selecting `{:?}` during codegen, presuming due to \
+                     overflow or prior type error",
+                    trait_binder
+                ),
+            );
+            return Err(reported);
+        }
+        Err(CodegenObligationError::Unimplemented) => return Ok(None),
+        Err(CodegenObligationError::FulfillmentError) => return Ok(None),
+    };
+
+    // Now that we know which impl is being used, we can dispatch to
+    // the actual function:
+    Ok(match vtbl {
+        traits::ImplSource::UserDefined(impl_data) => {
+            debug!(
+                "resolving ImplSource::UserDefined: {:?}, {:?}, {:?}, {:?}",
+                param_env, trait_item_id, rcvr_substs, impl_data
+            );
+            assert!(!rcvr_substs.needs_infer());
+            assert!(!trait_ref.needs_infer());
+
+            let trait_def_id = tcx.trait_id_of_impl(impl_data.impl_def_id).unwrap();
+            let trait_def = tcx.trait_def(trait_def_id);
+            let leaf_def = trait_def
+                .ancestors(tcx, impl_data.impl_def_id)?
+                .leaf_def(tcx, trait_item_id)
+                .unwrap_or_else(|| {
+                    bug!("{:?} not found in {:?}", trait_item_id, impl_data.impl_def_id);
+                });
+
+            let substs = tcx.infer_ctxt().enter(|infcx| {
+                let param_env = param_env.with_reveal_all_normalized(tcx);
+                let substs = rcvr_substs.rebase_onto(tcx, trait_def_id, impl_data.substs);
+                let substs = translate_substs(
+                    &infcx,
+                    param_env,
+                    impl_data.impl_def_id,
+                    substs,
+                    leaf_def.defining_node,
+                );
+                infcx.tcx.erase_regions(substs)
+            });
+
+            // Since this is a trait item, we need to see if the item is either a trait default item
+            // or a specialization because we can't resolve those unless we can `Reveal::All`.
+            // NOTE: This should be kept in sync with the similar code in
+            // `rustc_trait_selection::traits::project::assemble_candidates_from_impls()`.
+            let eligible = if leaf_def.is_final() {
+                // Non-specializable items are always projectable.
+                true
+            } else {
+                // Only reveal a specializable default if we're past type-checking
+                // and the obligation is monomorphic, otherwise passes such as
+                // transmute checking and polymorphic MIR optimizations could
+                // get a result which isn't correct for all monomorphizations.
+                if param_env.reveal() == Reveal::All {
+                    !trait_ref.still_further_specializable()
+                } else {
+                    false
+                }
+            };
+
+            if !eligible {
+                return Ok(None);
+            }
+
+            // If the item does not have a value, then we cannot return an instance.
+            if !leaf_def.item.defaultness(tcx).has_value() {
+                return Ok(None);
+            }
+
+            let substs = tcx.erase_regions(substs);
+
+            // Check if we just resolved an associated `const` declaration from
+            // a `trait` to an associated `const` definition in an `impl`, where
+            // the definition in the `impl` has the wrong type (for which an
+            // error has already been/will be emitted elsewhere).
+            //
+            // NB: this may be expensive, we try to skip it in all the cases where
+            // we know the error would've been caught (e.g. in an upstream crate).
+            //
+            // A better approach might be to just introduce a query (returning
+            // `Result<(), ErrorGuaranteed>`) for the check that `rustc_typeck`
+            // performs (i.e. that the definition's type in the `impl` matches
+            // the declaration in the `trait`), so that we can cheaply check
+            // here if it failed, instead of approximating it.
+            if leaf_def.item.kind == ty::AssocKind::Const
+                && trait_item_id != leaf_def.item.def_id
+                && leaf_def.item.def_id.is_local()
+            {
+                let normalized_type_of = |def_id, substs| {
+                    tcx.subst_and_normalize_erasing_regions(substs, param_env, tcx.type_of(def_id))
+                };
+
+                let original_ty = normalized_type_of(trait_item_id, rcvr_substs);
+                let resolved_ty = normalized_type_of(leaf_def.item.def_id, substs);
+
+                if original_ty != resolved_ty {
+                    let msg = format!(
+                        "Instance::resolve: inconsistent associated `const` type: \
+                         was `{}: {}` but resolved to `{}: {}`",
+                        tcx.def_path_str_with_substs(trait_item_id, rcvr_substs),
+                        original_ty,
+                        tcx.def_path_str_with_substs(leaf_def.item.def_id, substs),
+                        resolved_ty,
+                    );
+                    let span = tcx.def_span(leaf_def.item.def_id);
+                    let reported = tcx.sess.delay_span_bug(span, &msg);
+
+                    return Err(reported);
+                }
+            }
+
+            Some(ty::Instance::new(leaf_def.item.def_id, substs))
+        }
+        traits::ImplSource::Generator(generator_data) => Some(Instance {
+            def: ty::InstanceDef::Item(ty::WithOptConstParam::unknown(
+                generator_data.generator_def_id,
+            )),
+            substs: generator_data.substs,
+        }),
+        traits::ImplSource::Closure(closure_data) => {
+            let trait_closure_kind = tcx.fn_trait_kind_from_lang_item(trait_id).unwrap();
+            Instance::resolve_closure(
+                tcx,
+                closure_data.closure_def_id,
+                closure_data.substs,
+                trait_closure_kind,
+            )
+        }
+        traits::ImplSource::FnPointer(ref data) => match data.fn_ty.kind() {
+            ty::FnDef(..) | ty::FnPtr(..) => Some(Instance {
+                def: ty::InstanceDef::FnPtrShim(trait_item_id, data.fn_ty),
+                substs: rcvr_substs,
+            }),
+            _ => None,
+        },
+        traits::ImplSource::Object(ref data) => {
+            if let Some(index) = traits::get_vtable_index_of_object_method(tcx, data, trait_item_id)
+            {
+                Some(Instance {
+                    def: ty::InstanceDef::Virtual(trait_item_id, index),
+                    substs: rcvr_substs,
+                })
+            } else {
+                None
+            }
+        }
+        traits::ImplSource::Builtin(..) => {
+            if Some(trait_ref.def_id) == tcx.lang_items().clone_trait() {
+                // FIXME(eddyb) use lang items for methods instead of names.
+                let name = tcx.item_name(trait_item_id);
+                if name == sym::clone {
+                    let self_ty = trait_ref.self_ty();
+
+                    let is_copy = self_ty.is_copy_modulo_regions(tcx.at(DUMMY_SP), param_env);
+                    match self_ty.kind() {
+                        _ if is_copy => (),
+                        ty::Closure(..) | ty::Tuple(..) => {}
+                        _ => return Ok(None),
+                    };
+
+                    Some(Instance {
+                        def: ty::InstanceDef::CloneShim(trait_item_id, self_ty),
+                        substs: rcvr_substs,
+                    })
+                } else {
+                    assert_eq!(name, sym::clone_from);
+
+                    // Use the default `fn clone_from` from `trait Clone`.
+                    let substs = tcx.erase_regions(rcvr_substs);
+                    Some(ty::Instance::new(trait_item_id, substs))
+                }
+            } else {
+                None
+            }
+        }
+        traits::ImplSource::AutoImpl(..)
+        | traits::ImplSource::Param(..)
+        | traits::ImplSource::TraitAlias(..)
+        | traits::ImplSource::DiscriminantKind(..)
+        | traits::ImplSource::Pointee(..)
+        | traits::ImplSource::TraitUpcasting(_)
+        | traits::ImplSource::ConstDestruct(_) => None,
+    })
+}
+
+pub fn provide(providers: &mut ty::query::Providers) {
+    *providers =
+        ty::query::Providers { resolve_instance, resolve_instance_of_const_arg, ..*providers };
+}
diff --git a/compiler/rustc_ty_utils/src/lib.rs b/compiler/rustc_ty_utils/src/lib.rs
new file mode 100644
index 000000000..09f5c2a11
--- /dev/null
+++ b/compiler/rustc_ty_utils/src/lib.rs
@@ -0,0 +1,36 @@
+//! Various checks
+//!
+//! # Note
+//!
+//! This API is completely unstable and subject to change.
+
+#![doc(html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/")]
+#![feature(control_flow_enum)]
+#![feature(let_else)]
+#![feature(never_type)]
+#![feature(box_patterns)]
+#![recursion_limit = "256"]
+
+#[macro_use]
+extern crate rustc_middle;
+#[macro_use]
+extern crate tracing;
+
+use rustc_middle::ty::query::Providers;
+
+mod assoc;
+mod common_traits;
+mod consts;
+pub mod instance;
+mod needs_drop;
+pub mod representability;
+mod ty;
+
+pub fn provide(providers: &mut Providers) {
+    assoc::provide(providers);
+    common_traits::provide(providers);
+    consts::provide(providers);
+    needs_drop::provide(providers);
+    ty::provide(providers);
+    instance::provide(providers);
+}
diff --git a/compiler/rustc_ty_utils/src/needs_drop.rs b/compiler/rustc_ty_utils/src/needs_drop.rs
new file mode 100644
index 000000000..9ad44d14d
--- /dev/null
+++ b/compiler/rustc_ty_utils/src/needs_drop.rs
@@ -0,0 +1,323 @@
+//! Check whether a type has (potentially) non-trivial drop glue.
+
+use rustc_data_structures::fx::FxHashSet;
+use rustc_hir::def_id::DefId;
+use rustc_middle::ty::subst::Subst;
+use rustc_middle::ty::subst::SubstsRef;
+use rustc_middle::ty::util::{needs_drop_components, AlwaysRequiresDrop};
+use rustc_middle::ty::{self, EarlyBinder, Ty, TyCtxt};
+use rustc_session::Limit;
+use rustc_span::{sym, DUMMY_SP};
+
+type NeedsDropResult<T> = Result<T, AlwaysRequiresDrop>;
+
+fn needs_drop_raw<'tcx>(tcx: TyCtxt<'tcx>, query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool {
+    // If we don't know a type doesn't need drop, for example if it's a type
+    // parameter without a `Copy` bound, then we conservatively return that it
+    // needs drop.
+    let adt_has_dtor =
+        |adt_def: ty::AdtDef<'tcx>| adt_def.destructor(tcx).map(|_| DtorType::Significant);
+    let res =
+        drop_tys_helper(tcx, query.value, query.param_env, adt_has_dtor, false).next().is_some();
+
+    debug!("needs_drop_raw({:?}) = {:?}", query, res);
+    res
+}
+
+fn has_significant_drop_raw<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>,
+) -> bool {
+    let res = drop_tys_helper(
+        tcx,
+        query.value,
+        query.param_env,
+        adt_consider_insignificant_dtor(tcx),
+        true,
+    )
+    .next()
+    .is_some();
+    debug!("has_significant_drop_raw({:?}) = {:?}", query, res);
+    res
+}
+
+struct NeedsDropTypes<'tcx, F> {
+    tcx: TyCtxt<'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    query_ty: Ty<'tcx>,
+    seen_tys: FxHashSet<Ty<'tcx>>,
+    /// A stack of types left to process, and the recursion depth when we
+    /// pushed that type. Each round, we pop something from the stack and check
+    /// if it needs drop. If the result depends on whether some other types
+    /// need drop we push them onto the stack.
+    unchecked_tys: Vec<(Ty<'tcx>, usize)>,
+    recursion_limit: Limit,
+    adt_components: F,
+}
+
+impl<'tcx, F> NeedsDropTypes<'tcx, F> {
+    fn new(
+        tcx: TyCtxt<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+        ty: Ty<'tcx>,
+        adt_components: F,
+    ) -> Self {
+        let mut seen_tys = FxHashSet::default();
+        seen_tys.insert(ty);
+        Self {
+            tcx,
+            param_env,
+            seen_tys,
+            query_ty: ty,
+            unchecked_tys: vec![(ty, 0)],
+            recursion_limit: tcx.recursion_limit(),
+            adt_components,
+        }
+    }
+}
+
+impl<'tcx, F, I> Iterator for NeedsDropTypes<'tcx, F>
+where
+    F: Fn(ty::AdtDef<'tcx>, SubstsRef<'tcx>) -> NeedsDropResult<I>,
+    I: Iterator<Item = Ty<'tcx>>,
+{
+    type Item = NeedsDropResult<Ty<'tcx>>;
+
+    fn next(&mut self) -> Option<NeedsDropResult<Ty<'tcx>>> {
+        let tcx = self.tcx;
+
+        while let Some((ty, level)) = self.unchecked_tys.pop() {
+            if !self.recursion_limit.value_within_limit(level) {
+                // Not having a `Span` isn't great. But there's hopefully some other
+                // recursion limit error as well.
+                tcx.sess.span_err(
+                    DUMMY_SP,
+                    &format!("overflow while checking whether `{}` requires drop", self.query_ty),
+                );
+                return Some(Err(AlwaysRequiresDrop));
+            }
+
+            let components = match needs_drop_components(ty, &tcx.data_layout) {
+                Err(e) => return Some(Err(e)),
+                Ok(components) => components,
+            };
+            debug!("needs_drop_components({:?}) = {:?}", ty, components);
+
+            let queue_type = move |this: &mut Self, component: Ty<'tcx>| {
+                if this.seen_tys.insert(component) {
+                    this.unchecked_tys.push((component, level + 1));
+                }
+            };
+
+            for component in components {
+                match *component.kind() {
+                    _ if component.is_copy_modulo_regions(tcx.at(DUMMY_SP), self.param_env) => (),
+
+                    ty::Closure(_, substs) => {
+                        queue_type(self, substs.as_closure().tupled_upvars_ty());
+                    }
+
+                    ty::Generator(def_id, substs, _) => {
+                        let substs = substs.as_generator();
+                        queue_type(self, substs.tupled_upvars_ty());
+
+                        let witness = substs.witness();
+                        let interior_tys = match witness.kind() {
+                            &ty::GeneratorWitness(tys) => tcx.erase_late_bound_regions(tys),
+                            _ => {
+                                tcx.sess.delay_span_bug(
+                                    tcx.hir().span_if_local(def_id).unwrap_or(DUMMY_SP),
+                                    &format!("unexpected generator witness type {:?}", witness),
+                                );
+                                return Some(Err(AlwaysRequiresDrop));
+                            }
+                        };
+
+                        for interior_ty in interior_tys {
+                            queue_type(self, interior_ty);
+                        }
+                    }
+
+                    // Check for a `Drop` impl and whether this is a union or
+                    // `ManuallyDrop`. If it's a struct or enum without a `Drop`
+                    // impl then check whether the field types need `Drop`.
+                    ty::Adt(adt_def, substs) => {
+                        let tys = match (self.adt_components)(adt_def, substs) {
+                            Err(e) => return Some(Err(e)),
+                            Ok(tys) => tys,
+                        };
+                        for required_ty in tys {
+                            let required = tcx
+                                .try_normalize_erasing_regions(self.param_env, required_ty)
+                                .unwrap_or(required_ty);
+
+                            queue_type(self, required);
+                        }
+                    }
+                    ty::Array(..) | ty::Opaque(..) | ty::Projection(..) | ty::Param(_) => {
+                        if ty == component {
+                            // Return the type to the caller: they may be able
+                            // to normalize further than we can.
+                            return Some(Ok(component));
+                        } else {
+                            // Store the type for later. We can't return here
+                            // because we would then lose any other components
+                            // of the type.
+                            queue_type(self, component);
+                        }
+                    }
+                    _ => return Some(Err(AlwaysRequiresDrop)),
+                }
+            }
+        }
+
+        None
+    }
+}
+
+enum DtorType {
+    /// Type has a `Drop` but it is considered insignificant.
+    /// Check the query `adt_significant_drop_tys` for understanding
+    /// "significant" / "insignificant".
+    Insignificant,
+
+    /// Type has a `Drop` implantation.
+    Significant,
+}
+
+// This is a helper function for `adt_drop_tys` and `adt_significant_drop_tys`.
+// Depending on the implantation of `adt_has_dtor`, it is used to check if the
+// ADT has a destructor or if the ADT only has a significant destructor. For
+// understanding significant destructor look at `adt_significant_drop_tys`.
+fn drop_tys_helper<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    ty: Ty<'tcx>,
+    param_env: rustc_middle::ty::ParamEnv<'tcx>,
+    adt_has_dtor: impl Fn(ty::AdtDef<'tcx>) -> Option<DtorType>,
+    only_significant: bool,
+) -> impl Iterator<Item = NeedsDropResult<Ty<'tcx>>> {
+    fn with_query_cache<'tcx>(
+        tcx: TyCtxt<'tcx>,
+        iter: impl IntoIterator<Item = Ty<'tcx>>,
+    ) -> NeedsDropResult<Vec<Ty<'tcx>>> {
+        iter.into_iter().try_fold(Vec::new(), |mut vec, subty| {
+            match subty.kind() {
+                ty::Adt(adt_id, subst) => {
+                    for subty in tcx.adt_drop_tys(adt_id.did())? {
+                        vec.push(EarlyBinder(subty).subst(tcx, subst));
+                    }
+                }
+                _ => vec.push(subty),
+            };
+            Ok(vec)
+        })
+    }
+
+    let adt_components = move |adt_def: ty::AdtDef<'tcx>, substs: SubstsRef<'tcx>| {
+        if adt_def.is_manually_drop() {
+            debug!("drop_tys_helper: `{:?}` is manually drop", adt_def);
+            Ok(Vec::new())
+        } else if let Some(dtor_info) = adt_has_dtor(adt_def) {
+            match dtor_info {
+                DtorType::Significant => {
+                    debug!("drop_tys_helper: `{:?}` implements `Drop`", adt_def);
+                    Err(AlwaysRequiresDrop)
+                }
+                DtorType::Insignificant => {
+                    debug!("drop_tys_helper: `{:?}` drop is insignificant", adt_def);
+
+                    // Since the destructor is insignificant, we just want to make sure all of
+                    // the passed in type parameters are also insignificant.
+                    // Eg: Vec<T> dtor is insignificant when T=i32 but significant when T=Mutex.
+                    Ok(substs.types().collect())
+                }
+            }
+        } else if adt_def.is_union() {
+            debug!("drop_tys_helper: `{:?}` is a union", adt_def);
+            Ok(Vec::new())
+        } else {
+            let field_tys = adt_def.all_fields().map(|field| {
+                let r = tcx.bound_type_of(field.did).subst(tcx, substs);
+                debug!("drop_tys_helper: Subst into {:?} with {:?} gettng {:?}", field, substs, r);
+                r
+            });
+            if only_significant {
+                // We can't recurse through the query system here because we might induce a cycle
+                Ok(field_tys.collect())
+            } else {
+                // We can use the query system if we consider all drops significant. In that case,
+                // ADTs are `needs_drop` exactly if they `impl Drop` or if any of their "transitive"
+                // fields do. There can be no cycles here, because ADTs cannot contain themselves as
+                // fields.
+                with_query_cache(tcx, field_tys)
+            }
+        }
+        .map(|v| v.into_iter())
+    };
+
+    NeedsDropTypes::new(tcx, param_env, ty, adt_components)
+}
+
+fn adt_consider_insignificant_dtor<'tcx>(
+    tcx: TyCtxt<'tcx>,
+) -> impl Fn(ty::AdtDef<'tcx>) -> Option<DtorType> + 'tcx {
+    move |adt_def: ty::AdtDef<'tcx>| {
+        let is_marked_insig = tcx.has_attr(adt_def.did(), sym::rustc_insignificant_dtor);
+        if is_marked_insig {
+            // In some cases like `std::collections::HashMap` where the struct is a wrapper around
+            // a type that is a Drop type, and the wrapped type (eg: `hashbrown::HashMap`) lies
+            // outside stdlib, we might choose to still annotate the the wrapper (std HashMap) with
+            // `rustc_insignificant_dtor`, even if the type itself doesn't have a `Drop` impl.
+            Some(DtorType::Insignificant)
+        } else if adt_def.destructor(tcx).is_some() {
+            // There is a Drop impl and the type isn't marked insignificant, therefore Drop must be
+            // significant.
+            Some(DtorType::Significant)
+        } else {
+            // No destructor found nor the type is annotated with `rustc_insignificant_dtor`, we
+            // treat this as the simple case of Drop impl for type.
+            None
+        }
+    }
+}
+
+fn adt_drop_tys<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    def_id: DefId,
+) -> Result<&ty::List<Ty<'tcx>>, AlwaysRequiresDrop> {
+    // This is for the "adt_drop_tys" query, that considers all `Drop` impls, therefore all dtors are
+    // significant.
+    let adt_has_dtor =
+        |adt_def: ty::AdtDef<'tcx>| adt_def.destructor(tcx).map(|_| DtorType::Significant);
+    // `tcx.type_of(def_id)` identical to `tcx.make_adt(def, identity_substs)`
+    drop_tys_helper(tcx, tcx.type_of(def_id), tcx.param_env(def_id), adt_has_dtor, false)
+        .collect::<Result<Vec<_>, _>>()
+        .map(|components| tcx.intern_type_list(&components))
+}
+// If `def_id` refers to a generic ADT, the queries above and below act as if they had been handed
+// a `tcx.make_ty(def, identity_substs)` and as such it is legal to substitute the generic parameters
+// of the ADT into the outputted `ty`s.
+fn adt_significant_drop_tys(
+    tcx: TyCtxt<'_>,
+    def_id: DefId,
+) -> Result<&ty::List<Ty<'_>>, AlwaysRequiresDrop> {
+    drop_tys_helper(
+        tcx,
+        tcx.type_of(def_id), // identical to `tcx.make_adt(def, identity_substs)`
+        tcx.param_env(def_id),
+        adt_consider_insignificant_dtor(tcx),
+        true,
+    )
+    .collect::<Result<Vec<_>, _>>()
+    .map(|components| tcx.intern_type_list(&components))
+}
+
+pub(crate) fn provide(providers: &mut ty::query::Providers) {
+    *providers = ty::query::Providers {
+        needs_drop_raw,
+        has_significant_drop_raw,
+        adt_drop_tys,
+        adt_significant_drop_tys,
+        ..*providers
+    };
+}
diff --git a/compiler/rustc_ty_utils/src/representability.rs b/compiler/rustc_ty_utils/src/representability.rs
new file mode 100644
index 000000000..eded78916
--- /dev/null
+++ b/compiler/rustc_ty_utils/src/representability.rs
@@ -0,0 +1,386 @@
+//! 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;
+
+/// 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>)>),
+}
+
+/// 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
+}
+
+// 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>,
+    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,
+                            },
+                        );
+                    }
+                }
+
+                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,
+    }
+}
+
+fn same_adt<'tcx>(ty: Ty<'tcx>, def: ty::AdtDef<'tcx>) -> 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>,
+    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();
+    }
+
+    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
+}
+
+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>> }
+
+                for &seen_adt in iter {
+                    if 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);
+            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,
+            )
+        }
+    }
+}
diff --git a/compiler/rustc_ty_utils/src/ty.rs b/compiler/rustc_ty_utils/src/ty.rs
new file mode 100644
index 000000000..db0d45b86
--- /dev/null
+++ b/compiler/rustc_ty_utils/src/ty.rs
@@ -0,0 +1,481 @@
+use rustc_data_structures::fx::FxIndexSet;
+use rustc_hir as hir;
+use rustc_hir::def_id::DefId;
+use rustc_middle::ty::subst::Subst;
+use rustc_middle::ty::{self, Binder, Predicate, PredicateKind, ToPredicate, Ty, TyCtxt};
+use rustc_trait_selection::traits;
+
+fn sized_constraint_for_ty<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    adtdef: ty::AdtDef<'tcx>,
+    ty: Ty<'tcx>,
+) -> Vec<Ty<'tcx>> {
+    use rustc_type_ir::sty::TyKind::*;
+
+    let result = match ty.kind() {
+        Bool | Char | Int(..) | Uint(..) | Float(..) | RawPtr(..) | Ref(..) | FnDef(..)
+        | FnPtr(_) | Array(..) | Closure(..) | Generator(..) | Never => vec![],
+
+        Str | Dynamic(..) | Slice(_) | Foreign(..) | Error(_) | GeneratorWitness(..) => {
+            // these are never sized - return the target type
+            vec![ty]
+        }
+
+        Tuple(ref tys) => match tys.last() {
+            None => vec![],
+            Some(&ty) => sized_constraint_for_ty(tcx, adtdef, ty),
+        },
+
+        Adt(adt, substs) => {
+            // recursive case
+            let adt_tys = adt.sized_constraint(tcx);
+            debug!("sized_constraint_for_ty({:?}) intermediate = {:?}", ty, adt_tys);
+            adt_tys
+                .0
+                .iter()
+                .map(|ty| adt_tys.rebind(*ty).subst(tcx, substs))
+                .flat_map(|ty| sized_constraint_for_ty(tcx, adtdef, ty))
+                .collect()
+        }
+
+        Projection(..) | Opaque(..) => {
+            // must calculate explicitly.
+            // FIXME: consider special-casing always-Sized projections
+            vec![ty]
+        }
+
+        Param(..) => {
+            // perf hack: if there is a `T: Sized` bound, then
+            // we know that `T` is Sized and do not need to check
+            // it on the impl.
+
+            let Some(sized_trait) = tcx.lang_items().sized_trait() else { return vec![ty] };
+            let sized_predicate = ty::Binder::dummy(ty::TraitRef {
+                def_id: sized_trait,
+                substs: tcx.mk_substs_trait(ty, &[]),
+            })
+            .without_const()
+            .to_predicate(tcx);
+            let predicates = tcx.predicates_of(adtdef.did()).predicates;
+            if predicates.iter().any(|(p, _)| *p == sized_predicate) { vec![] } else { vec![ty] }
+        }
+
+        Placeholder(..) | Bound(..) | Infer(..) => {
+            bug!("unexpected type `{:?}` in sized_constraint_for_ty", ty)
+        }
+    };
+    debug!("sized_constraint_for_ty({:?}) = {:?}", ty, result);
+    result
+}
+
+fn impl_defaultness(tcx: TyCtxt<'_>, def_id: DefId) -> hir::Defaultness {
+    match tcx.hir().get_by_def_id(def_id.expect_local()) {
+        hir::Node::Item(hir::Item { kind: hir::ItemKind::Impl(impl_), .. }) => impl_.defaultness,
+        hir::Node::ImplItem(hir::ImplItem { defaultness, .. })
+        | hir::Node::TraitItem(hir::TraitItem { defaultness, .. }) => *defaultness,
+        node => {
+            bug!("`impl_defaultness` called on {:?}", node);
+        }
+    }
+}
+
+/// Calculates the `Sized` constraint.
+///
+/// In fact, there are only a few options for the types in the constraint:
+///     - an obviously-unsized type
+///     - a type parameter or projection whose Sizedness can't be known
+///     - a tuple of type parameters or projections, if there are multiple
+///       such.
+///     - an Error, if a type contained itself. The representability
+///       check should catch this case.
+fn adt_sized_constraint(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AdtSizedConstraint<'_> {
+    let def = tcx.adt_def(def_id);
+
+    let result = tcx.mk_type_list(
+        def.variants()
+            .iter()
+            .flat_map(|v| v.fields.last())
+            .flat_map(|f| sized_constraint_for_ty(tcx, def, tcx.type_of(f.did))),
+    );
+
+    debug!("adt_sized_constraint: {:?} => {:?}", def, result);
+
+    ty::AdtSizedConstraint(result)
+}
+
+/// See `ParamEnv` struct definition for details.
+#[instrument(level = "debug", skip(tcx))]
+fn param_env(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> {
+    // The param_env of an impl Trait type is its defining function's param_env
+    if let Some(parent) = ty::is_impl_trait_defn(tcx, def_id) {
+        return param_env(tcx, parent.to_def_id());
+    }
+    // Compute the bounds on Self and the type parameters.
+
+    let ty::InstantiatedPredicates { mut predicates, .. } =
+        tcx.predicates_of(def_id).instantiate_identity(tcx);
+
+    // Finally, we have to normalize the bounds in the environment, in
+    // case they contain any associated type projections. This process
+    // can yield errors if the put in illegal associated types, like
+    // `<i32 as Foo>::Bar` where `i32` does not implement `Foo`. We
+    // report these errors right here; this doesn't actually feel
+    // right to me, because constructing the environment feels like a
+    // kind of an "idempotent" action, but I'm not sure where would be
+    // a better place. In practice, we construct environments for
+    // every fn once during type checking, and we'll abort if there
+    // are any errors at that point, so outside of type inference you can be
+    // sure that this will succeed without errors anyway.
+
+    if tcx.sess.opts.unstable_opts.chalk {
+        let environment = well_formed_types_in_env(tcx, def_id);
+        predicates.extend(environment);
+    }
+
+    let local_did = def_id.as_local();
+    let hir_id = local_did.map(|def_id| tcx.hir().local_def_id_to_hir_id(def_id));
+
+    let constness = match hir_id {
+        Some(hir_id) => match tcx.hir().get(hir_id) {
+            hir::Node::TraitItem(hir::TraitItem { kind: hir::TraitItemKind::Fn(..), .. })
+                if tcx.is_const_default_method(def_id) =>
+            {
+                hir::Constness::Const
+            }
+
+            hir::Node::Item(hir::Item { kind: hir::ItemKind::Const(..), .. })
+            | hir::Node::Item(hir::Item { kind: hir::ItemKind::Static(..), .. })
+            | hir::Node::TraitItem(hir::TraitItem {
+                kind: hir::TraitItemKind::Const(..), ..
+            })
+            | hir::Node::AnonConst(_)
+            | hir::Node::ImplItem(hir::ImplItem { kind: hir::ImplItemKind::Const(..), .. })
+            | hir::Node::ImplItem(hir::ImplItem {
+                kind:
+                    hir::ImplItemKind::Fn(
+                        hir::FnSig {
+                            header: hir::FnHeader { constness: hir::Constness::Const, .. },
+                            ..
+                        },
+                        ..,
+                    ),
+                ..
+            }) => hir::Constness::Const,
+
+            hir::Node::ImplItem(hir::ImplItem {
+                kind: hir::ImplItemKind::TyAlias(..) | hir::ImplItemKind::Fn(..),
+                ..
+            }) => {
+                let parent_hir_id = tcx.hir().get_parent_node(hir_id);
+                match tcx.hir().get(parent_hir_id) {
+                    hir::Node::Item(hir::Item {
+                        kind: hir::ItemKind::Impl(hir::Impl { constness, .. }),
+                        ..
+                    }) => *constness,
+                    _ => span_bug!(
+                        tcx.def_span(parent_hir_id.owner),
+                        "impl item's parent node is not an impl",
+                    ),
+                }
+            }
+
+            hir::Node::Item(hir::Item {
+                kind:
+                    hir::ItemKind::Fn(hir::FnSig { header: hir::FnHeader { constness, .. }, .. }, ..),
+                ..
+            })
+            | hir::Node::TraitItem(hir::TraitItem {
+                kind:
+                    hir::TraitItemKind::Fn(
+                        hir::FnSig { header: hir::FnHeader { constness, .. }, .. },
+                        ..,
+                    ),
+                ..
+            })
+            | hir::Node::Item(hir::Item {
+                kind: hir::ItemKind::Impl(hir::Impl { constness, .. }),
+                ..
+            }) => *constness,
+
+            _ => hir::Constness::NotConst,
+        },
+        None => hir::Constness::NotConst,
+    };
+
+    let unnormalized_env = ty::ParamEnv::new(
+        tcx.intern_predicates(&predicates),
+        traits::Reveal::UserFacing,
+        constness,
+    );
+
+    let body_id =
+        local_did.and_then(|id| tcx.hir().maybe_body_owned_by(id).map(|body| body.hir_id));
+    let body_id = match body_id {
+        Some(id) => id,
+        None if hir_id.is_some() => hir_id.unwrap(),
+        _ => hir::CRATE_HIR_ID,
+    };
+
+    let cause = traits::ObligationCause::misc(tcx.def_span(def_id), body_id);
+    traits::normalize_param_env_or_error(tcx, unnormalized_env, cause)
+}
+
+/// Elaborate the environment.
+///
+/// Collect a list of `Predicate`'s used for building the `ParamEnv`. Adds `TypeWellFormedFromEnv`'s
+/// that are assumed to be well-formed (because they come from the environment).
+///
+/// Used only in chalk mode.
+fn well_formed_types_in_env<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    def_id: DefId,
+) -> &'tcx ty::List<Predicate<'tcx>> {
+    use rustc_hir::{ForeignItemKind, ImplItemKind, ItemKind, Node, TraitItemKind};
+    use rustc_middle::ty::subst::GenericArgKind;
+
+    debug!("environment(def_id = {:?})", def_id);
+
+    // The environment of an impl Trait type is its defining function's environment.
+    if let Some(parent) = ty::is_impl_trait_defn(tcx, def_id) {
+        return well_formed_types_in_env(tcx, parent.to_def_id());
+    }
+
+    // Compute the bounds on `Self` and the type parameters.
+    let ty::InstantiatedPredicates { predicates, .. } =
+        tcx.predicates_of(def_id).instantiate_identity(tcx);
+
+    let clauses = predicates.into_iter();
+
+    if !def_id.is_local() {
+        return ty::List::empty();
+    }
+    let node = tcx.hir().get_by_def_id(def_id.expect_local());
+
+    enum NodeKind {
+        TraitImpl,
+        InherentImpl,
+        Fn,
+        Other,
+    }
+
+    let node_kind = match node {
+        Node::TraitItem(item) => match item.kind {
+            TraitItemKind::Fn(..) => NodeKind::Fn,
+            _ => NodeKind::Other,
+        },
+
+        Node::ImplItem(item) => match item.kind {
+            ImplItemKind::Fn(..) => NodeKind::Fn,
+            _ => NodeKind::Other,
+        },
+
+        Node::Item(item) => match item.kind {
+            ItemKind::Impl(hir::Impl { of_trait: Some(_), .. }) => NodeKind::TraitImpl,
+            ItemKind::Impl(hir::Impl { of_trait: None, .. }) => NodeKind::InherentImpl,
+            ItemKind::Fn(..) => NodeKind::Fn,
+            _ => NodeKind::Other,
+        },
+
+        Node::ForeignItem(item) => match item.kind {
+            ForeignItemKind::Fn(..) => NodeKind::Fn,
+            _ => NodeKind::Other,
+        },
+
+        // FIXME: closures?
+        _ => NodeKind::Other,
+    };
+
+    // FIXME(eddyb) isn't the unordered nature of this a hazard?
+    let mut inputs = FxIndexSet::default();
+
+    match node_kind {
+        // In a trait impl, we assume that the header trait ref and all its
+        // constituents are well-formed.
+        NodeKind::TraitImpl => {
+            let trait_ref = tcx.impl_trait_ref(def_id).expect("not an impl");
+
+            // FIXME(chalk): this has problems because of late-bound regions
+            //inputs.extend(trait_ref.substs.iter().flat_map(|arg| arg.walk()));
+            inputs.extend(trait_ref.substs.iter());
+        }
+
+        // In an inherent impl, we assume that the receiver type and all its
+        // constituents are well-formed.
+        NodeKind::InherentImpl => {
+            let self_ty = tcx.type_of(def_id);
+            inputs.extend(self_ty.walk());
+        }
+
+        // In an fn, we assume that the arguments and all their constituents are
+        // well-formed.
+        NodeKind::Fn => {
+            let fn_sig = tcx.fn_sig(def_id);
+            let fn_sig = tcx.liberate_late_bound_regions(def_id, fn_sig);
+
+            inputs.extend(fn_sig.inputs().iter().flat_map(|ty| ty.walk()));
+        }
+
+        NodeKind::Other => (),
+    }
+    let input_clauses = inputs.into_iter().filter_map(|arg| {
+        match arg.unpack() {
+            GenericArgKind::Type(ty) => {
+                let binder = Binder::dummy(PredicateKind::TypeWellFormedFromEnv(ty));
+                Some(tcx.mk_predicate(binder))
+            }
+
+            // FIXME(eddyb) no WF conditions from lifetimes?
+            GenericArgKind::Lifetime(_) => None,
+
+            // FIXME(eddyb) support const generics in Chalk
+            GenericArgKind::Const(_) => None,
+        }
+    });
+
+    tcx.mk_predicates(clauses.chain(input_clauses))
+}
+
+fn param_env_reveal_all_normalized(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> {
+    tcx.param_env(def_id).with_reveal_all_normalized(tcx)
+}
+
+fn instance_def_size_estimate<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    instance_def: ty::InstanceDef<'tcx>,
+) -> usize {
+    use ty::InstanceDef;
+
+    match instance_def {
+        InstanceDef::Item(..) | InstanceDef::DropGlue(..) => {
+            let mir = tcx.instance_mir(instance_def);
+            mir.basic_blocks().iter().map(|bb| bb.statements.len() + 1).sum()
+        }
+        // Estimate the size of other compiler-generated shims to be 1.
+        _ => 1,
+    }
+}
+
+/// If `def_id` is an issue 33140 hack impl, returns its self type; otherwise, returns `None`.
+///
+/// See [`ty::ImplOverlapKind::Issue33140`] for more details.
+fn issue33140_self_ty(tcx: TyCtxt<'_>, def_id: DefId) -> Option<Ty<'_>> {
+    debug!("issue33140_self_ty({:?})", def_id);
+
+    let trait_ref = tcx
+        .impl_trait_ref(def_id)
+        .unwrap_or_else(|| bug!("issue33140_self_ty called on inherent impl {:?}", def_id));
+
+    debug!("issue33140_self_ty({:?}), trait-ref={:?}", def_id, trait_ref);
+
+    let is_marker_like = tcx.impl_polarity(def_id) == ty::ImplPolarity::Positive
+        && tcx.associated_item_def_ids(trait_ref.def_id).is_empty();
+
+    // Check whether these impls would be ok for a marker trait.
+    if !is_marker_like {
+        debug!("issue33140_self_ty - not marker-like!");
+        return None;
+    }
+
+    // impl must be `impl Trait for dyn Marker1 + Marker2 + ...`
+    if trait_ref.substs.len() != 1 {
+        debug!("issue33140_self_ty - impl has substs!");
+        return None;
+    }
+
+    let predicates = tcx.predicates_of(def_id);
+    if predicates.parent.is_some() || !predicates.predicates.is_empty() {
+        debug!("issue33140_self_ty - impl has predicates {:?}!", predicates);
+        return None;
+    }
+
+    let self_ty = trait_ref.self_ty();
+    let self_ty_matches = match self_ty.kind() {
+        ty::Dynamic(ref data, re) if re.is_static() => data.principal().is_none(),
+        _ => false,
+    };
+
+    if self_ty_matches {
+        debug!("issue33140_self_ty - MATCHES!");
+        Some(self_ty)
+    } else {
+        debug!("issue33140_self_ty - non-matching self type");
+        None
+    }
+}
+
+/// Check if a function is async.
+fn asyncness(tcx: TyCtxt<'_>, def_id: DefId) -> hir::IsAsync {
+    let node = tcx.hir().get_by_def_id(def_id.expect_local());
+    if let Some(fn_kind) = node.fn_kind() { fn_kind.asyncness() } else { hir::IsAsync::NotAsync }
+}
+
+/// Don't call this directly: use ``tcx.conservative_is_privately_uninhabited`` instead.
+#[instrument(level = "debug", skip(tcx))]
+pub fn conservative_is_privately_uninhabited_raw<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    param_env_and: ty::ParamEnvAnd<'tcx, Ty<'tcx>>,
+) -> bool {
+    let (param_env, ty) = param_env_and.into_parts();
+    match ty.kind() {
+        ty::Never => {
+            debug!("ty::Never =>");
+            true
+        }
+        ty::Adt(def, _) if def.is_union() => {
+            debug!("ty::Adt(def, _) if def.is_union() =>");
+            // For now, `union`s are never considered uninhabited.
+            false
+        }
+        ty::Adt(def, substs) => {
+            debug!("ty::Adt(def, _) if def.is_not_union() =>");
+            // Any ADT is uninhabited if either:
+            // (a) It has no variants (i.e. an empty `enum`);
+            // (b) Each of its variants (a single one in the case of a `struct`) has at least
+            //     one uninhabited field.
+            def.variants().iter().all(|var| {
+                var.fields.iter().any(|field| {
+                    let ty = tcx.bound_type_of(field.did).subst(tcx, substs);
+                    tcx.conservative_is_privately_uninhabited(param_env.and(ty))
+                })
+            })
+        }
+        ty::Tuple(fields) => {
+            debug!("ty::Tuple(..) =>");
+            fields.iter().any(|ty| tcx.conservative_is_privately_uninhabited(param_env.and(ty)))
+        }
+        ty::Array(ty, len) => {
+            debug!("ty::Array(ty, len) =>");
+            match len.try_eval_usize(tcx, param_env) {
+                Some(0) | None => false,
+                // If the array is definitely non-empty, it's uninhabited if
+                // the type of its elements is uninhabited.
+                Some(1..) => tcx.conservative_is_privately_uninhabited(param_env.and(*ty)),
+            }
+        }
+        ty::Ref(..) => {
+            debug!("ty::Ref(..) =>");
+            // References to uninitialised memory is valid for any type, including
+            // uninhabited types, in unsafe code, so we treat all references as
+            // inhabited.
+            false
+        }
+        _ => {
+            debug!("_ =>");
+            false
+        }
+    }
+}
+
+pub fn provide(providers: &mut ty::query::Providers) {
+    *providers = ty::query::Providers {
+        asyncness,
+        adt_sized_constraint,
+        param_env,
+        param_env_reveal_all_normalized,
+        instance_def_size_estimate,
+        issue33140_self_ty,
+        impl_defaultness,
+        conservative_is_privately_uninhabited: conservative_is_privately_uninhabited_raw,
+        ..*providers
+    };
+}