Implement valtree

valtree is a version of constants that is inherently safe to be used within types.
This is in contrast to ty::Const which can have different representations of the same value. These representation differences can show up in hashing or equality comparisons, breaking type equality of otherwise equal types.
valtrees do not have this problem.

6 files changed, 28 insertions, 3 deletions

diff --git a/compiler/rustc_middle/src/mir/interpret/value.rs b/compiler/rustc_middle/src/mir/interpret/value.rs
index a07ccd4d2b5..ba9b285e8e6 100644
--- a/compiler/rustc_middle/src/mir/interpret/value.rs
+++ b/compiler/rustc_middle/src/mir/interpret/value.rs
@@ -13,7 +13,7 @@ use crate::ty::{ParamEnv, ScalarInt, Ty, TyCtxt};
 use super::{AllocId, Allocation, InterpResult, Pointer, PointerArithmetic};
 
 /// Represents the result of const evaluation via the `eval_to_allocation` query.
-#[derive(Clone, HashStable, TyEncodable, TyDecodable, Debug)]
+#[derive(Copy, Clone, HashStable, TyEncodable, TyDecodable, Debug, Hash, Eq, PartialEq)]
 pub struct ConstAlloc<'tcx> {
     // the value lives here, at offset 0, and that allocation definitely is a `AllocKind::Memory`
     // (so you can use `AllocMap::unwrap_memory`).
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index b03b26d6460..b0c066fb42f 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -785,6 +785,14 @@ rustc_queries! {
         cache_on_disk_if { true }
     }
 
+    /// Convert an evaluated constant to a type level constant or
+    /// return `None` if that is not possible.
+    query const_to_valtree(
+        key: ty::ParamEnvAnd<'tcx, ConstAlloc<'tcx>>
+    ) -> Option<ty::ValTree> {
+        desc { "destructure constant" }
+    }
+
     /// Destructure a constant ADT or array into its variant index and its
     /// field values.
     query destructure_const(
diff --git a/compiler/rustc_middle/src/ty/consts.rs b/compiler/rustc_middle/src/ty/consts.rs
index e7b2c9efd63..622f8e8ff6c 100644
--- a/compiler/rustc_middle/src/ty/consts.rs
+++ b/compiler/rustc_middle/src/ty/consts.rs
@@ -10,9 +10,11 @@ use rustc_macros::HashStable;
 
 mod int;
 mod kind;
+mod valtree;
 
 pub use int::*;
 pub use kind::*;
+pub use valtree::*;
 
 /// Typed constant value.
 #[derive(Copy, Clone, Debug, Hash, TyEncodable, TyDecodable, Eq, PartialEq, Ord, PartialOrd)]
diff --git a/compiler/rustc_middle/src/ty/consts/valtree.rs b/compiler/rustc_middle/src/ty/consts/valtree.rs
new file mode 100644
index 00000000000..9b42023f054
--- /dev/null
+++ b/compiler/rustc_middle/src/ty/consts/valtree.rs
@@ -0,0 +1,15 @@
+use super::ScalarInt;
+use rustc_macros::HashStable;
+
+#[derive(Clone, Debug, Hash, TyEncodable, TyDecodable, Eq, PartialEq, Ord, PartialOrd)]
+#[derive(HashStable)]
+pub enum ValTree {
+    Leaf(ScalarInt),
+    Branch(Vec<ValTree>),
+}
+
+impl ValTree {
+    pub fn zst() -> Self {
+        Self::Branch(Vec::new())
+    }
+}
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index f5aef108927..5bbf7b35d3d 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -55,7 +55,7 @@ pub use rustc_type_ir::*;
 
 pub use self::binding::BindingMode;
 pub use self::binding::BindingMode::*;
-pub use self::consts::{Const, ConstInt, ConstKind, InferConst, ScalarInt};
+pub use self::consts::{Const, ConstInt, ConstKind, InferConst, ScalarInt, ValTree};
 pub use self::context::{
     tls, CanonicalUserType, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations,
     CtxtInterners, DelaySpanBugEmitted, FreeRegionInfo, GeneratorInteriorTypeCause, GlobalCtxt,
diff --git a/compiler/rustc_middle/src/ty/query/mod.rs b/compiler/rustc_middle/src/ty/query/mod.rs
index 51a214bc07b..48e777f7158 100644
--- a/compiler/rustc_middle/src/ty/query/mod.rs
+++ b/compiler/rustc_middle/src/ty/query/mod.rs
@@ -14,8 +14,8 @@ use crate::middle::resolve_lifetime::{ObjectLifetimeDefault, Region, ResolveLife
 use crate::middle::stability::{self, DeprecationEntry};
 use crate::mir;
 use crate::mir::interpret::GlobalId;
+use crate::mir::interpret::{ConstAlloc, LitToConstError, LitToConstInput};
 use crate::mir::interpret::{ConstValue, EvalToAllocationRawResult, EvalToConstValueResult};
-use crate::mir::interpret::{LitToConstError, LitToConstInput};
 use crate::mir::mono::CodegenUnit;
 use crate::traits::query::{
     CanonicalPredicateGoal, CanonicalProjectionGoal, CanonicalTyGoal,