Add empty ConstKind::Abstract

Initial pass at expr/abstract const/s

Address comments

Switch to using a list instead of &[ty::Const], rm `AbstractConst`

Remove try_unify_abstract_consts

Update comments

Add edits

Recurse more

More edits

Prevent equating associated consts

Move failing test to ui

Changes this test from incremental to ui, and mark it as failing and a known bug.
Does not cause the compiler to ICE, so should be ok.

16 files changed, 215 insertions, 192 deletions

diff --git a/compiler/rustc_middle/src/mir/pretty.rs b/compiler/rustc_middle/src/mir/pretty.rs
index 2b3f2c02411..1cac656674d 100644
--- a/compiler/rustc_middle/src/mir/pretty.rs
+++ b/compiler/rustc_middle/src/mir/pretty.rs
@@ -476,6 +476,7 @@ impl<'tcx> Visitor<'tcx> for ExtraComments<'tcx> {
                     // These variants shouldn't exist in the MIR.
                     ty::ConstKind::Placeholder(_)
                     | ty::ConstKind::Infer(_)
+                    | ty::ConstKind::Expr(_)
                     | ty::ConstKind::Bound(..) => bug!("unexpected MIR constant: {:?}", literal),
                 },
                 ConstantKind::Unevaluated(uv, _) => {
diff --git a/compiler/rustc_middle/src/mir/syntax.rs b/compiler/rustc_middle/src/mir/syntax.rs
index fed943169df..f2030b91b9b 100644
--- a/compiler/rustc_middle/src/mir/syntax.rs
+++ b/compiler/rustc_middle/src/mir/syntax.rs
@@ -1185,7 +1185,8 @@ pub enum NullOp {
     AlignOf,
 }
 
-#[derive(Copy, Clone, Debug, PartialEq, Eq, TyEncodable, TyDecodable, Hash, HashStable)]
+#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
+#[derive(HashStable, TyEncodable, TyDecodable, TypeFoldable, TypeVisitable)]
 pub enum UnOp {
     /// The `!` operator for logical inversion
     Not,
@@ -1193,7 +1194,8 @@ pub enum UnOp {
     Neg,
 }
 
-#[derive(Copy, Clone, Debug, PartialEq, PartialOrd, Eq, TyEncodable, TyDecodable, Hash, HashStable)]
+#[derive(Copy, Clone, Debug, PartialEq, PartialOrd, Ord, Eq, Hash)]
+#[derive(TyEncodable, TyDecodable, HashStable, TypeFoldable, TypeVisitable)]
 pub enum BinOp {
     /// The `+` operator (addition)
     Add,
diff --git a/compiler/rustc_middle/src/mir/type_foldable.rs b/compiler/rustc_middle/src/mir/type_foldable.rs
index 4c0974f86fb..0705b4cff53 100644
--- a/compiler/rustc_middle/src/mir/type_foldable.rs
+++ b/compiler/rustc_middle/src/mir/type_foldable.rs
@@ -16,9 +16,7 @@ TrivialTypeTraversalAndLiftImpls! {
     UserTypeAnnotationIndex,
     BorrowKind,
     CastKind,
-    BinOp,
     NullOp,
-    UnOp,
     hir::Movability,
     BasicBlock,
     SwitchTargets,
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index d86bdbd63d8..36cdb50958c 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -400,7 +400,7 @@ rustc_queries! {
     /// Try to build an abstract representation of the given constant.
     query thir_abstract_const(
         key: DefId
-    ) -> Result<Option<&'tcx [ty::abstract_const::Node<'tcx>]>, ErrorGuaranteed> {
+    ) -> Result<Option<ty::Const<'tcx>>, ErrorGuaranteed> {
         desc {
             |tcx| "building an abstract representation for `{}`", tcx.def_path_str(key),
         }
@@ -409,7 +409,7 @@ rustc_queries! {
     /// Try to build an abstract representation of the given constant.
     query thir_abstract_const_of_const_arg(
         key: (LocalDefId, DefId)
-    ) -> Result<Option<&'tcx [ty::abstract_const::Node<'tcx>]>, ErrorGuaranteed> {
+    ) -> Result<Option<ty::Const<'tcx>>, ErrorGuaranteed> {
         desc {
             |tcx|
             "building an abstract representation for the const argument `{}`",
@@ -417,15 +417,6 @@ rustc_queries! {
         }
     }
 
-    query try_unify_abstract_consts(key:
-        ty::ParamEnvAnd<'tcx, (ty::UnevaluatedConst<'tcx>, ty::UnevaluatedConst<'tcx>
-    )>) -> bool {
-        desc {
-            |tcx| "trying to unify the generic constants `{}` and `{}`",
-            tcx.def_path_str(key.value.0.def.did), tcx.def_path_str(key.value.1.def.did)
-        }
-    }
-
     query mir_drops_elaborated_and_const_checked(
         key: ty::WithOptConstParam<LocalDefId>
     ) -> &'tcx Steal<mir::Body<'tcx>> {
diff --git a/compiler/rustc_middle/src/ty/abstract_const.rs b/compiler/rustc_middle/src/ty/abstract_const.rs
index e5bcd5fb27a..8a8c46d6f21 100644
--- a/compiler/rustc_middle/src/ty/abstract_const.rs
+++ b/compiler/rustc_middle/src/ty/abstract_const.rs
@@ -1,98 +1,10 @@
 //! A subset of a mir body used for const evaluatability checking.
-use crate::mir;
-use crate::ty::visit::TypeVisitable;
-use crate::ty::{self, EarlyBinder, SubstsRef, Ty, TyCtxt};
+use crate::ty::{self, Const, EarlyBinder, FallibleTypeFolder, GenericArg, TyCtxt, TypeFoldable};
 use rustc_errors::ErrorGuaranteed;
 use rustc_hir::def_id::DefId;
-use std::cmp;
-use std::ops::ControlFlow;
 
-rustc_index::newtype_index! {
-    /// An index into an `AbstractConst`.
-    pub struct NodeId {
-        derive [HashStable]
-        DEBUG_FORMAT = "n{}",
-    }
-}
-
-/// A tree representing an anonymous constant.
-///
-/// This is only able to represent a subset of `MIR`,
-/// and should not leak any information about desugarings.
-#[derive(Debug, Clone, Copy)]
-pub struct AbstractConst<'tcx> {
-    // FIXME: Consider adding something like `IndexSlice`
-    // and use this here.
-    inner: &'tcx [Node<'tcx>],
-    substs: SubstsRef<'tcx>,
-}
-
-impl<'tcx> AbstractConst<'tcx> {
-    pub fn new(
-        tcx: TyCtxt<'tcx>,
-        uv: ty::UnevaluatedConst<'tcx>,
-    ) -> Result<Option<AbstractConst<'tcx>>, ErrorGuaranteed> {
-        let inner = tcx.thir_abstract_const_opt_const_arg(uv.def)?;
-        debug!("AbstractConst::new({:?}) = {:?}", uv, inner);
-        Ok(inner.map(|inner| AbstractConst { inner, substs: tcx.erase_regions(uv.substs) }))
-    }
-
-    pub fn from_const(
-        tcx: TyCtxt<'tcx>,
-        ct: ty::Const<'tcx>,
-    ) -> Result<Option<AbstractConst<'tcx>>, ErrorGuaranteed> {
-        match ct.kind() {
-            ty::ConstKind::Unevaluated(uv) => AbstractConst::new(tcx, uv),
-            ty::ConstKind::Error(reported) => Err(reported),
-            _ => Ok(None),
-        }
-    }
-
-    #[inline]
-    pub fn subtree(self, node: NodeId) -> AbstractConst<'tcx> {
-        AbstractConst { inner: &self.inner[..=node.index()], substs: self.substs }
-    }
-
-    #[inline]
-    pub fn root(self, tcx: TyCtxt<'tcx>) -> Node<'tcx> {
-        let node = self.inner.last().copied().unwrap();
-        match node {
-            Node::Leaf(leaf) => Node::Leaf(EarlyBinder(leaf).subst(tcx, self.substs)),
-            Node::Cast(kind, operand, ty) => {
-                Node::Cast(kind, operand, EarlyBinder(ty).subst(tcx, self.substs))
-            }
-            // Don't perform substitution on the following as they can't directly contain generic params
-            Node::Binop(_, _, _) | Node::UnaryOp(_, _) | Node::FunctionCall(_, _) => node,
-        }
-    }
-
-    pub fn unify_failure_kind(self, tcx: TyCtxt<'tcx>) -> FailureKind {
-        let mut failure_kind = FailureKind::Concrete;
-        walk_abstract_const::<!, _>(tcx, self, |node| {
-            match node.root(tcx) {
-                Node::Leaf(leaf) => {
-                    if leaf.has_non_region_infer() {
-                        failure_kind = FailureKind::MentionsInfer;
-                    } else if leaf.has_non_region_param() {
-                        failure_kind = cmp::min(failure_kind, FailureKind::MentionsParam);
-                    }
-                }
-                Node::Cast(_, _, ty) => {
-                    if ty.has_non_region_infer() {
-                        failure_kind = FailureKind::MentionsInfer;
-                    } else if ty.has_non_region_param() {
-                        failure_kind = cmp::min(failure_kind, FailureKind::MentionsParam);
-                    }
-                }
-                Node::Binop(_, _, _) | Node::UnaryOp(_, _) | Node::FunctionCall(_, _) => {}
-            }
-            ControlFlow::CONTINUE
-        });
-        failure_kind
-    }
-}
-
-#[derive(Debug, Clone, Copy, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
+#[derive(Hash, Debug, Clone, Copy, Ord, PartialOrd, PartialEq, Eq)]
+#[derive(TyDecodable, TyEncodable, HashStable, TypeVisitable, TypeFoldable)]
 pub enum CastKind {
     /// thir::ExprKind::As
     As,
@@ -100,16 +12,6 @@ pub enum CastKind {
     Use,
 }
 
-/// A node of an `AbstractConst`.
-#[derive(Debug, Clone, Copy, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
-pub enum Node<'tcx> {
-    Leaf(ty::Const<'tcx>),
-    Binop(mir::BinOp, NodeId, NodeId),
-    UnaryOp(mir::UnOp, NodeId),
-    FunctionCall(NodeId, &'tcx [NodeId]),
-    Cast(CastKind, NodeId, Ty<'tcx>),
-}
-
 #[derive(Debug, Copy, Clone, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
 pub enum NotConstEvaluatable {
     Error(ErrorGuaranteed),
@@ -127,68 +29,75 @@ TrivialTypeTraversalAndLiftImpls! {
     NotConstEvaluatable,
 }
 
+pub type BoundAbstractConst<'tcx> = Result<Option<EarlyBinder<ty::Const<'tcx>>>, ErrorGuaranteed>;
+
 impl<'tcx> TyCtxt<'tcx> {
+    /// Returns a const with substs applied by
+    pub fn bound_abstract_const(
+        self,
+        uv: ty::WithOptConstParam<DefId>,
+    ) -> BoundAbstractConst<'tcx> {
+        self.thir_abstract_const_opt_const_arg(uv).map(|ac| ac.map(|ac| EarlyBinder(ac)))
+    }
     #[inline]
     pub fn thir_abstract_const_opt_const_arg(
         self,
         def: ty::WithOptConstParam<DefId>,
-    ) -> Result<Option<&'tcx [Node<'tcx>]>, ErrorGuaranteed> {
+    ) -> Result<Option<ty::Const<'tcx>>, ErrorGuaranteed> {
         if let Some((did, param_did)) = def.as_const_arg() {
             self.thir_abstract_const_of_const_arg((did, param_did))
         } else {
             self.thir_abstract_const(def.did)
         }
     }
-}
 
-#[instrument(skip(tcx, f), level = "debug")]
-pub fn walk_abstract_const<'tcx, R, F>(
-    tcx: TyCtxt<'tcx>,
-    ct: AbstractConst<'tcx>,
-    mut f: F,
-) -> ControlFlow<R>
-where
-    F: FnMut(AbstractConst<'tcx>) -> ControlFlow<R>,
-{
-    #[instrument(skip(tcx, f), level = "debug")]
-    fn recurse<'tcx, R>(
-        tcx: TyCtxt<'tcx>,
-        ct: AbstractConst<'tcx>,
-        f: &mut dyn FnMut(AbstractConst<'tcx>) -> ControlFlow<R>,
-    ) -> ControlFlow<R> {
-        f(ct)?;
-        let root = ct.root(tcx);
-        debug!(?root);
-        match root {
-            Node::Leaf(_) => ControlFlow::CONTINUE,
-            Node::Binop(_, l, r) => {
-                recurse(tcx, ct.subtree(l), f)?;
-                recurse(tcx, ct.subtree(r), f)
+    pub fn expand_bound_abstract_const(
+        self,
+        ct: BoundAbstractConst<'tcx>,
+        substs: &[GenericArg<'tcx>],
+    ) -> Result<Option<Const<'tcx>>, ErrorGuaranteed> {
+        struct Expander<'tcx> {
+            tcx: TyCtxt<'tcx>,
+        }
+        impl<'tcx> FallibleTypeFolder<'tcx> for Expander<'tcx> {
+            type Error = ErrorGuaranteed;
+            fn tcx(&self) -> TyCtxt<'tcx> {
+                self.tcx
             }
-            Node::UnaryOp(_, v) => recurse(tcx, ct.subtree(v), f),
-            Node::FunctionCall(func, args) => {
-                recurse(tcx, ct.subtree(func), f)?;
-                args.iter().try_for_each(|&arg| recurse(tcx, ct.subtree(arg), f))
+            fn try_fold_const(&mut self, c: Const<'tcx>) -> Result<Const<'tcx>, ErrorGuaranteed> {
+                use ty::ConstKind::*;
+                let uv = match c.kind() {
+                    Unevaluated(uv) => uv,
+                    Param(..) | Infer(..) | Bound(..) | Placeholder(..) | Value(..) | Error(..) => {
+                        return Ok(c);
+                    }
+                    Expr(e) => {
+                        let new_expr = match e {
+                            ty::Expr::Binop(op, l, r) => {
+                                ty::Expr::Binop(op, l.try_fold_with(self)?, r.try_fold_with(self)?)
+                            }
+                            ty::Expr::UnOp(op, v) => ty::Expr::UnOp(op, v.try_fold_with(self)?),
+                            ty::Expr::Cast(k, c, t) => {
+                                ty::Expr::Cast(k, c.try_fold_with(self)?, t.try_fold_with(self)?)
+                            }
+                            ty::Expr::FunctionCall(func, args) => ty::Expr::FunctionCall(
+                                func.try_fold_with(self)?,
+                                args.try_fold_with(self)?,
+                            ),
+                        };
+                        return Ok(self.tcx().mk_const(ty::ConstKind::Expr(new_expr), c.ty()));
+                    }
+                };
+                let bac = self.tcx.bound_abstract_const(uv.def);
+                let ac = self.tcx.expand_bound_abstract_const(bac, uv.substs);
+                if let Ok(Some(ac)) = ac { ac.try_fold_with(self) } else { Ok(c) }
             }
-            Node::Cast(_, operand, _) => recurse(tcx, ct.subtree(operand), f),
         }
-    }
 
-    recurse(tcx, ct, &mut f)
-}
-
-// We were unable to unify the abstract constant with
-// a constant found in the caller bounds, there are
-// now three possible cases here.
-#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
-pub enum FailureKind {
-    /// The abstract const still references an inference
-    /// variable, in this case we return `TooGeneric`.
-    MentionsInfer,
-    /// The abstract const references a generic parameter,
-    /// this means that we emit an error here.
-    MentionsParam,
-    /// The substs are concrete enough that we can simply
-    /// try and evaluate the given constant.
-    Concrete,
+        let Some(ac) = ct? else {
+            return Ok(None);
+        };
+        let ac = ac.subst(self, substs);
+        Ok(Some(ac.try_fold_with(&mut Expander { tcx: self })?))
+    }
 }
diff --git a/compiler/rustc_middle/src/ty/codec.rs b/compiler/rustc_middle/src/ty/codec.rs
index b469eebfad9..b22b3961f34 100644
--- a/compiler/rustc_middle/src/ty/codec.rs
+++ b/compiler/rustc_middle/src/ty/codec.rs
@@ -346,33 +346,22 @@ impl<'tcx, D: TyDecoder<I = TyCtxt<'tcx>>> RefDecodable<'tcx, D>
 }
 
 impl<'tcx, D: TyDecoder<I = TyCtxt<'tcx>>> RefDecodable<'tcx, D>
-    for [ty::abstract_const::Node<'tcx>]
-{
-    fn decode(decoder: &mut D) -> &'tcx Self {
-        decoder.interner().arena.alloc_from_iter(
-            (0..decoder.read_usize()).map(|_| Decodable::decode(decoder)).collect::<Vec<_>>(),
-        )
-    }
-}
-
-impl<'tcx, D: TyDecoder<I = TyCtxt<'tcx>>> RefDecodable<'tcx, D>
-    for [ty::abstract_const::NodeId]
+    for ty::List<ty::BoundVariableKind>
 {
     fn decode(decoder: &mut D) -> &'tcx Self {
-        decoder.interner().arena.alloc_from_iter(
-            (0..decoder.read_usize()).map(|_| Decodable::decode(decoder)).collect::<Vec<_>>(),
+        let len = decoder.read_usize();
+        decoder.interner().mk_bound_variable_kinds(
+            (0..len).map::<ty::BoundVariableKind, _>(|_| Decodable::decode(decoder)),
         )
     }
 }
 
-impl<'tcx, D: TyDecoder<I = TyCtxt<'tcx>>> RefDecodable<'tcx, D>
-    for ty::List<ty::BoundVariableKind>
-{
+impl<'tcx, D: TyDecoder<I = TyCtxt<'tcx>>> RefDecodable<'tcx, D> for ty::List<ty::Const<'tcx>> {
     fn decode(decoder: &mut D) -> &'tcx Self {
         let len = decoder.read_usize();
-        decoder.interner().mk_bound_variable_kinds(
-            (0..len).map::<ty::BoundVariableKind, _>(|_| Decodable::decode(decoder)),
-        )
+        decoder
+            .interner()
+            .mk_const_list((0..len).map::<ty::Const<'tcx>, _>(|_| Decodable::decode(decoder)))
     }
 }
 
diff --git a/compiler/rustc_middle/src/ty/consts/kind.rs b/compiler/rustc_middle/src/ty/consts/kind.rs
index 321cba693d9..de63dae8a3d 100644
--- a/compiler/rustc_middle/src/ty/consts/kind.rs
+++ b/compiler/rustc_middle/src/ty/consts/kind.rs
@@ -1,10 +1,12 @@
 use std::convert::TryInto;
 
+use super::Const;
 use crate::mir;
 use crate::mir::interpret::{AllocId, ConstValue, Scalar};
+use crate::ty::abstract_const::CastKind;
 use crate::ty::subst::{InternalSubsts, SubstsRef};
 use crate::ty::ParamEnv;
-use crate::ty::{self, TyCtxt, TypeVisitable};
+use crate::ty::{self, List, Ty, TyCtxt, TypeVisitable};
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_errors::ErrorGuaranteed;
 use rustc_hir::def_id::DefId;
@@ -70,9 +72,24 @@ pub enum ConstKind<'tcx> {
     /// A placeholder for a const which could not be computed; this is
     /// propagated to avoid useless error messages.
     Error(ErrorGuaranteed),
+
+    /// Expr which contains an expression which has partially evaluated items.
+    Expr(Expr<'tcx>),
+}
+
+#[derive(Copy, Clone, Debug, Eq, PartialEq, PartialOrd, Ord, Hash)]
+#[derive(HashStable, TyEncodable, TyDecodable, TypeVisitable, TypeFoldable)]
+pub enum Expr<'tcx> {
+    Binop(mir::BinOp, Const<'tcx>, Const<'tcx>),
+    UnOp(mir::UnOp, Const<'tcx>),
+    FunctionCall(Const<'tcx>, &'tcx List<Const<'tcx>>),
+    Cast(CastKind, Const<'tcx>, Ty<'tcx>),
 }
 
 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
+static_assert_size!(Expr<'_>, 24);
+
+#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
 static_assert_size!(ConstKind<'_>, 32);
 
 impl<'tcx> ConstKind<'tcx> {
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index b5327ad0cec..f627dc7ceb1 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -2714,6 +2714,17 @@ impl<'tcx> TyCtxt<'tcx> {
         }
     }
 
+    pub fn mk_const_list<I: InternAs<[ty::Const<'tcx>], &'tcx List<ty::Const<'tcx>>>>(
+        self,
+        iter: I,
+    ) -> I::Output {
+        iter.intern_with(|xs| self.intern_const_list(xs))
+    }
+
+    pub fn intern_const_list(self, cs: &[ty::Const<'tcx>]) -> &'tcx List<ty::Const<'tcx>> {
+        if cs.is_empty() { List::empty() } else { List::from_arena(self.arena, cs) }
+    }
+
     pub fn intern_type_list(self, ts: &[Ty<'tcx>]) -> &'tcx List<Ty<'tcx>> {
         if ts.is_empty() {
             List::empty()
diff --git a/compiler/rustc_middle/src/ty/fast_reject.rs b/compiler/rustc_middle/src/ty/fast_reject.rs
index 1ee4985cf8d..c9c09c93a3e 100644
--- a/compiler/rustc_middle/src/ty/fast_reject.rs
+++ b/compiler/rustc_middle/src/ty/fast_reject.rs
@@ -356,7 +356,10 @@ impl DeepRejectCtxt {
 
     pub fn consts_may_unify(self, obligation_ct: ty::Const<'_>, impl_ct: ty::Const<'_>) -> bool {
         match impl_ct.kind() {
-            ty::ConstKind::Param(_) | ty::ConstKind::Unevaluated(_) | ty::ConstKind::Error(_) => {
+            ty::ConstKind::Expr(_)
+            | ty::ConstKind::Param(_)
+            | ty::ConstKind::Unevaluated(_)
+            | ty::ConstKind::Error(_) => {
                 return true;
             }
             ty::ConstKind::Value(_) => {}
@@ -374,7 +377,9 @@ impl DeepRejectCtxt {
 
             // As we don't necessarily eagerly evaluate constants,
             // they might unify with any value.
-            ty::ConstKind::Unevaluated(_) | ty::ConstKind::Error(_) => true,
+            ty::ConstKind::Expr(_) | ty::ConstKind::Unevaluated(_) | ty::ConstKind::Error(_) => {
+                true
+            }
             ty::ConstKind::Value(obl) => match k {
                 ty::ConstKind::Value(imp) => obl == imp,
                 _ => true,
diff --git a/compiler/rustc_middle/src/ty/flags.rs b/compiler/rustc_middle/src/ty/flags.rs
index ee4b8f91c54..bbd050d7cae 100644
--- a/compiler/rustc_middle/src/ty/flags.rs
+++ b/compiler/rustc_middle/src/ty/flags.rs
@@ -307,6 +307,26 @@ impl FlagComputation {
                 self.add_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE);
             }
             ty::ConstKind::Value(_) => {}
+            ty::ConstKind::Expr(e) => {
+                use ty::Expr;
+                match e {
+                    Expr::Binop(_, l, r) => {
+                        self.add_const(l);
+                        self.add_const(r);
+                    }
+                    Expr::UnOp(_, v) => self.add_const(v),
+                    Expr::FunctionCall(f, args) => {
+                        self.add_const(f);
+                        for arg in args {
+                            self.add_const(arg);
+                        }
+                    }
+                    Expr::Cast(_, c, t) => {
+                        self.add_ty(t);
+                        self.add_const(c);
+                    }
+                }
+            }
             ty::ConstKind::Error(_) => self.add_flags(TypeFlags::HAS_ERROR),
         }
     }
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index 9d778ff2fb6..9928340d921 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -77,7 +77,7 @@ pub use self::closure::{
     CAPTURE_STRUCT_LOCAL,
 };
 pub use self::consts::{
-    Const, ConstInt, ConstKind, ConstS, InferConst, ScalarInt, UnevaluatedConst, ValTree,
+    Const, ConstInt, ConstKind, ConstS, Expr, InferConst, ScalarInt, UnevaluatedConst, ValTree,
 };
 pub use self::context::{
     tls, CanonicalUserType, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations,
diff --git a/compiler/rustc_middle/src/ty/parameterized.rs b/compiler/rustc_middle/src/ty/parameterized.rs
index d6025248081..b2bcf0e29cd 100644
--- a/compiler/rustc_middle/src/ty/parameterized.rs
+++ b/compiler/rustc_middle/src/ty/parameterized.rs
@@ -4,7 +4,6 @@ use rustc_index::vec::{Idx, IndexVec};
 
 use crate::middle::exported_symbols::ExportedSymbol;
 use crate::mir::Body;
-use crate::ty::abstract_const::Node;
 use crate::ty::{
     self, Const, FnSig, GeneratorDiagnosticData, GenericPredicates, Predicate, TraitRef, Ty,
 };
@@ -124,6 +123,5 @@ parameterized_over_tcx! {
     Predicate,
     GeneratorDiagnosticData,
     Body,
-    Node,
     ExportedSymbol,
 }
diff --git a/compiler/rustc_middle/src/ty/print/pretty.rs b/compiler/rustc_middle/src/ty/print/pretty.rs
index c54edf10c2d..249004cbc5c 100644
--- a/compiler/rustc_middle/src/ty/print/pretty.rs
+++ b/compiler/rustc_middle/src/ty/print/pretty.rs
@@ -1253,6 +1253,9 @@ pub trait PrettyPrinter<'tcx>:
                 self.pretty_print_bound_var(debruijn, bound_var)?
             }
             ty::ConstKind::Placeholder(placeholder) => p!(write("Placeholder({:?})", placeholder)),
+            // FIXME(generic_const_exprs):
+            // write out some legible representation of an abstract const?
+            ty::ConstKind::Expr(_) => p!("[Const Expr]"),
             ty::ConstKind::Error(_) => p!("[const error]"),
         };
         Ok(self)
diff --git a/compiler/rustc_middle/src/ty/relate.rs b/compiler/rustc_middle/src/ty/relate.rs
index 3d47b71b7ce..4249decc88f 100644
--- a/compiler/rustc_middle/src/ty/relate.rs
+++ b/compiler/rustc_middle/src/ty/relate.rs
@@ -5,7 +5,7 @@
 //! subtyping, type equality, etc.
 
 use crate::ty::error::{ExpectedFound, TypeError};
-use crate::ty::{self, ImplSubject, Term, TermKind, Ty, TyCtxt, TypeFoldable};
+use crate::ty::{self, Expr, ImplSubject, Term, TermKind, Ty, TyCtxt, TypeFoldable};
 use crate::ty::{GenericArg, GenericArgKind, SubstsRef};
 use rustc_hir as ast;
 use rustc_hir::def_id::DefId;
@@ -613,7 +613,10 @@ pub fn super_relate_consts<'tcx, R: TypeRelation<'tcx>>(
     if a_ty != b_ty {
         relation.tcx().sess.delay_span_bug(
             DUMMY_SP,
-            &format!("cannot relate constants of different types: {} != {}", a_ty, b_ty),
+            &format!(
+                "cannot relate constants ({:?}, {:?}) of different types: {} != {}",
+                a, b, a_ty, b_ty
+            ),
         );
     }
 
@@ -647,13 +650,21 @@ pub fn super_relate_consts<'tcx, R: TypeRelation<'tcx>>(
         (ty::ConstKind::Unevaluated(au), ty::ConstKind::Unevaluated(bu))
             if tcx.features().generic_const_exprs =>
         {
-            tcx.try_unify_abstract_consts(relation.param_env().and((au, bu)))
+            if let (Ok(Some(a)), Ok(Some(b))) = (
+                tcx.expand_bound_abstract_const(tcx.bound_abstract_const(au.def), au.substs),
+                tcx.expand_bound_abstract_const(tcx.bound_abstract_const(bu.def), bu.substs),
+            ) && a.ty() == b.ty() {
+                return relation.consts(a, b);
+            } else {
+                false
+            }
         }
 
         // While this is slightly incorrect, it shouldn't matter for `min_const_generics`
         // and is the better alternative to waiting until `generic_const_exprs` can
         // be stabilized.
         (ty::ConstKind::Unevaluated(au), ty::ConstKind::Unevaluated(bu)) if au.def == bu.def => {
+            assert_eq!(a.ty(), b.ty());
             let substs = relation.relate_with_variance(
                 ty::Variance::Invariant,
                 ty::VarianceDiagInfo::default(),
@@ -665,6 +676,50 @@ pub fn super_relate_consts<'tcx, R: TypeRelation<'tcx>>(
                 a.ty(),
             ));
         }
+        // Before calling relate on exprs, it is necessary to ensure that the nested consts
+        // have identical types.
+        (ty::ConstKind::Expr(ae), ty::ConstKind::Expr(be)) => {
+            let r = relation;
+
+            // FIXME(julianknodt): is it possible to relate two consts which are not identical
+            // exprs? Should we care about that?
+            let expr = match (ae, be) {
+                (Expr::Binop(a_op, al, ar), Expr::Binop(b_op, bl, br))
+                    if a_op == b_op && al.ty() == bl.ty() && ar.ty() == br.ty() =>
+                {
+                    Expr::Binop(a_op, r.consts(al, bl)?, r.consts(ar, br)?)
+                }
+                (Expr::UnOp(a_op, av), Expr::UnOp(b_op, bv))
+                    if a_op == b_op && av.ty() == bv.ty() =>
+                {
+                    Expr::UnOp(a_op, r.consts(av, bv)?)
+                }
+                (Expr::Cast(ak, av, at), Expr::Cast(bk, bv, bt))
+                    if ak == bk && av.ty() == bv.ty() =>
+                {
+                    Expr::Cast(ak, r.consts(av, bv)?, r.tys(at, bt)?)
+                }
+                (Expr::FunctionCall(af, aa), Expr::FunctionCall(bf, ba))
+                    if aa.len() == ba.len()
+                        && af.ty() == bf.ty()
+                        && aa
+                            .iter()
+                            .zip(ba.iter())
+                            .all(|(a_arg, b_arg)| a_arg.ty() == b_arg.ty()) =>
+                {
+                    let func = r.consts(af, bf)?;
+                    let mut related_args = Vec::with_capacity(aa.len());
+                    for (a_arg, b_arg) in aa.iter().zip(ba.iter()) {
+                        related_args.push(r.consts(a_arg, b_arg)?);
+                    }
+                    let related_args = tcx.mk_const_list(related_args.iter());
+                    Expr::FunctionCall(func, related_args)
+                }
+                _ => return Err(TypeError::ConstMismatch(expected_found(r, a, b))),
+            };
+            let kind = ty::ConstKind::Expr(expr);
+            return Ok(tcx.mk_const(kind, a.ty()));
+        }
         _ => false,
     };
     if is_match { Ok(a) } else { Err(TypeError::ConstMismatch(expected_found(relation, a, b))) }
diff --git a/compiler/rustc_middle/src/ty/structural_impls.rs b/compiler/rustc_middle/src/ty/structural_impls.rs
index 64b4fd11762..7726ab8e5ab 100644
--- a/compiler/rustc_middle/src/ty/structural_impls.rs
+++ b/compiler/rustc_middle/src/ty/structural_impls.rs
@@ -593,6 +593,12 @@ impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ty::PolyExistentialPredicate<'t
     }
 }
 
+impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ty::Const<'tcx>> {
+    fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
+        ty::util::fold_list(self, folder, |tcx, v| tcx.mk_const_list(v.iter()))
+    }
+}
+
 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ProjectionKind> {
     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
         ty::util::fold_list(self, folder, |tcx, v| tcx.intern_projs(v))
diff --git a/compiler/rustc_middle/src/ty/walk.rs b/compiler/rustc_middle/src/ty/walk.rs
index 91db9698c41..4fab5abe909 100644
--- a/compiler/rustc_middle/src/ty/walk.rs
+++ b/compiler/rustc_middle/src/ty/walk.rs
@@ -214,6 +214,24 @@ fn push_inner<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent: GenericArg<'tcx>)
                 | ty::ConstKind::Value(_)
                 | ty::ConstKind::Error(_) => {}
 
+                ty::ConstKind::Expr(expr) => match expr {
+                    ty::Expr::UnOp(_, v) => push_inner(stack, v.into()),
+                    ty::Expr::Binop(_, l, r) => {
+                        push_inner(stack, r.into());
+                        push_inner(stack, l.into())
+                    }
+                    ty::Expr::FunctionCall(func, args) => {
+                        for a in args.iter().rev() {
+                            push_inner(stack, a.into());
+                        }
+                        push_inner(stack, func.into());
+                    }
+                    ty::Expr::Cast(_, c, t) => {
+                        push_inner(stack, t.into());
+                        push_inner(stack, c.into());
+                    }
+                },
+
                 ty::ConstKind::Unevaluated(ct) => {
                     stack.extend(ct.substs.iter().rev());
                 }