Intern CanonicalVarValues

7 files changed, 73 insertions, 81 deletions

diff --git a/compiler/rustc_infer/src/infer/canonical/mod.rs b/compiler/rustc_infer/src/infer/canonical/mod.rs
index e59715b706b..f7e3e4a1cc0 100644
--- a/compiler/rustc_infer/src/infer/canonical/mod.rs
+++ b/compiler/rustc_infer/src/infer/canonical/mod.rs
@@ -26,7 +26,7 @@ use crate::infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin, TypeVari
 use rustc_index::vec::IndexVec;
 use rustc_middle::ty::fold::TypeFoldable;
 use rustc_middle::ty::subst::GenericArg;
-use rustc_middle::ty::{self, BoundVar, List};
+use rustc_middle::ty::{self, List};
 use rustc_span::source_map::Span;
 
 pub use rustc_middle::infer::canonical::*;
@@ -87,12 +87,13 @@ impl<'tcx> InferCtxt<'tcx> {
         variables: &List<CanonicalVarInfo<'tcx>>,
         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
     ) -> CanonicalVarValues<'tcx> {
-        let var_values: IndexVec<BoundVar, GenericArg<'tcx>> = variables
-            .iter()
-            .map(|info| self.instantiate_canonical_var(span, info, &universe_map))
-            .collect();
-
-        CanonicalVarValues { var_values }
+        CanonicalVarValues {
+            var_values: self.tcx.mk_substs(
+                variables
+                    .iter()
+                    .map(|info| self.instantiate_canonical_var(span, info, &universe_map)),
+            ),
+        }
     }
 
     /// Given the "info" about a canonical variable, creates a fresh
diff --git a/compiler/rustc_infer/src/infer/canonical/query_response.rs b/compiler/rustc_infer/src/infer/canonical/query_response.rs
index 3d49182f0b8..98272708c16 100644
--- a/compiler/rustc_infer/src/infer/canonical/query_response.rs
+++ b/compiler/rustc_infer/src/infer/canonical/query_response.rs
@@ -482,11 +482,8 @@ impl<'tcx> InferCtxt<'tcx> {
         // given variable in the loop above, use that. Otherwise, use
         // a fresh inference variable.
         let result_subst = CanonicalVarValues {
-            var_values: query_response
-                .variables
-                .iter()
-                .enumerate()
-                .map(|(index, info)| {
+            var_values: self.tcx.mk_substs(query_response.variables.iter().enumerate().map(
+                |(index, info)| {
                     if info.is_existential() {
                         match opt_values[BoundVar::new(index)] {
                             Some(k) => k,
@@ -499,8 +496,8 @@ impl<'tcx> InferCtxt<'tcx> {
                             universe_map[u.as_usize()]
                         })
                     }
-                })
-                .collect(),
+                },
+            )),
         };
 
         let mut obligations = vec![];
diff --git a/compiler/rustc_infer/src/infer/canonical/substitute.rs b/compiler/rustc_infer/src/infer/canonical/substitute.rs
index 389afe22eb7..e77f2d37b7d 100644
--- a/compiler/rustc_infer/src/infer/canonical/substitute.rs
+++ b/compiler/rustc_infer/src/infer/canonical/substitute.rs
@@ -72,16 +72,15 @@ where
         value
     } else {
         let delegate = FnMutDelegate {
-            regions: &mut |br: ty::BoundRegion| match var_values.var_values[br.var].unpack() {
+            regions: &mut |br: ty::BoundRegion| match var_values[br.var].unpack() {
                 GenericArgKind::Lifetime(l) => l,
                 r => bug!("{:?} is a region but value is {:?}", br, r),
             },
-            types: &mut |bound_ty: ty::BoundTy| match var_values.var_values[bound_ty.var].unpack() {
+            types: &mut |bound_ty: ty::BoundTy| match var_values[bound_ty.var].unpack() {
                 GenericArgKind::Type(ty) => ty,
                 r => bug!("{:?} is a type but value is {:?}", bound_ty, r),
             },
-            consts: &mut |bound_ct: ty::BoundVar, _| match var_values.var_values[bound_ct].unpack()
-            {
+            consts: &mut |bound_ct: ty::BoundVar, _| match var_values[bound_ct].unpack() {
                 GenericArgKind::Const(ct) => ct,
                 c => bug!("{:?} is a const but value is {:?}", bound_ct, c),
             },
diff --git a/compiler/rustc_middle/src/infer/canonical.rs b/compiler/rustc_middle/src/infer/canonical.rs
index 43583b5723e..2247090c38c 100644
--- a/compiler/rustc_middle/src/infer/canonical.rs
+++ b/compiler/rustc_middle/src/infer/canonical.rs
@@ -25,10 +25,8 @@ use crate::infer::MemberConstraint;
 use crate::mir::ConstraintCategory;
 use crate::ty::subst::GenericArg;
 use crate::ty::{self, BoundVar, List, Region, Ty, TyCtxt};
-use rustc_index::vec::IndexVec;
 use rustc_macros::HashStable;
 use smallvec::SmallVec;
-use std::iter;
 use std::ops::Index;
 
 /// A "canonicalized" type `V` is one where all free inference
@@ -62,23 +60,23 @@ impl<'tcx> ty::TypeFoldable<'tcx> for CanonicalVarInfos<'tcx> {
 /// vectors with the original values that were replaced by canonical
 /// variables. You will need to supply it later to instantiate the
 /// canonicalized query response.
-#[derive(Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable)]
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable)]
 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
 pub struct CanonicalVarValues<'tcx> {
-    pub var_values: IndexVec<BoundVar, GenericArg<'tcx>>,
+    pub var_values: ty::SubstsRef<'tcx>,
 }
 
 impl CanonicalVarValues<'_> {
     pub fn is_identity(&self) -> bool {
-        self.var_values.iter_enumerated().all(|(bv, arg)| match arg.unpack() {
+        self.var_values.iter().enumerate().all(|(bv, arg)| match arg.unpack() {
             ty::GenericArgKind::Lifetime(r) => {
-                matches!(*r, ty::ReLateBound(ty::INNERMOST, br) if br.var == bv)
+                matches!(*r, ty::ReLateBound(ty::INNERMOST, br) if br.var.as_usize() == bv)
             }
             ty::GenericArgKind::Type(ty) => {
-                matches!(*ty.kind(), ty::Bound(ty::INNERMOST, bt) if bt.var == bv)
+                matches!(*ty.kind(), ty::Bound(ty::INNERMOST, bt) if bt.var.as_usize() == bv)
             }
             ty::GenericArgKind::Const(ct) => {
-                matches!(ct.kind(), ty::ConstKind::Bound(ty::INNERMOST, bc) if bc == bv)
+                matches!(ct.kind(), ty::ConstKind::Bound(ty::INNERMOST, bc) if bc.as_usize() == bv)
             }
         })
     }
@@ -342,7 +340,7 @@ impl<'tcx> CanonicalVarValues<'tcx> {
     /// Creates dummy var values which should not be used in a
     /// canonical response.
     pub fn dummy() -> CanonicalVarValues<'tcx> {
-        CanonicalVarValues { var_values: Default::default() }
+        CanonicalVarValues { var_values: ty::List::empty() }
     }
 
     #[inline]
@@ -360,36 +358,38 @@ impl<'tcx> CanonicalVarValues<'tcx> {
         use crate::ty::subst::GenericArgKind;
 
         CanonicalVarValues {
-            var_values: iter::zip(&self.var_values, 0..)
-                .map(|(kind, i)| match kind.unpack() {
-                    GenericArgKind::Type(..) => {
-                        tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i).into())).into()
-                    }
-                    GenericArgKind::Lifetime(..) => {
-                        let br = ty::BoundRegion {
-                            var: ty::BoundVar::from_u32(i),
-                            kind: ty::BrAnon(i, None),
-                        };
-                        tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)).into()
+            var_values: tcx.mk_substs(self.var_values.iter().enumerate().map(
+                |(i, kind)| -> ty::GenericArg<'tcx> {
+                    match kind.unpack() {
+                        GenericArgKind::Type(..) => tcx
+                            .mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i).into()))
+                            .into(),
+                        GenericArgKind::Lifetime(..) => {
+                            let br = ty::BoundRegion {
+                                var: ty::BoundVar::from_usize(i),
+                                kind: ty::BrAnon(i as u32, None),
+                            };
+                            tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)).into()
+                        }
+                        GenericArgKind::Const(ct) => tcx
+                            .mk_const(
+                                ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i)),
+                                ct.ty(),
+                            )
+                            .into(),
                     }
-                    GenericArgKind::Const(ct) => tcx
-                        .mk_const(
-                            ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i)),
-                            ct.ty(),
-                        )
-                        .into(),
-                })
-                .collect(),
+                },
+            )),
         }
     }
 }
 
 impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
     type Item = GenericArg<'tcx>;
-    type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, GenericArg<'tcx>>>;
+    type IntoIter = ::std::iter::Copied<::std::slice::Iter<'a, GenericArg<'tcx>>>;
 
     fn into_iter(self) -> Self::IntoIter {
-        self.var_values.iter().cloned()
+        self.var_values.iter()
     }
 }
 
@@ -397,6 +397,6 @@ impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> {
     type Output = GenericArg<'tcx>;
 
     fn index(&self, value: BoundVar) -> &GenericArg<'tcx> {
-        &self.var_values[value]
+        &self.var_values[value.as_usize()]
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index f44648c95d7..1bd2f0fbda9 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -13,8 +13,6 @@
 // preserves universes and creates a unique var (in the highest universe) for each
 // appearance of a region.
 
-// FIXME: `CanonicalVarValues` should be interned and `Copy`.
-
 // FIXME: uses of `infcx.at` need to enable deferred projection equality once that's implemented.
 
 use std::mem;
@@ -227,7 +225,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         let external_constraints = take_external_constraints(self.infcx)?;
 
         Ok(self.infcx.canonicalize_response(Response {
-            var_values: self.var_values.clone(),
+            var_values: self.var_values,
             external_constraints,
             certainty,
         }))
@@ -483,26 +481,24 @@ pub(super) fn response_no_constraints<'tcx>(
     goal: Canonical<'tcx, impl Sized>,
     certainty: Certainty,
 ) -> QueryResult<'tcx> {
-    let var_values = goal
-        .variables
-        .iter()
-        .enumerate()
-        .map(|(i, info)| match info.kind {
-            CanonicalVarKind::Ty(_) | CanonicalVarKind::PlaceholderTy(_) => {
-                tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i).into())).into()
-            }
-            CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => {
-                let br = ty::BoundRegion {
-                    var: ty::BoundVar::from_usize(i),
-                    kind: ty::BrAnon(i as u32, None),
-                };
-                tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)).into()
+    let var_values =
+        tcx.mk_substs(goal.variables.iter().enumerate().map(|(i, info)| -> ty::GenericArg<'tcx> {
+            match info.kind {
+                CanonicalVarKind::Ty(_) | CanonicalVarKind::PlaceholderTy(_) => {
+                    tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i).into())).into()
+                }
+                CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => {
+                    let br = ty::BoundRegion {
+                        var: ty::BoundVar::from_usize(i),
+                        kind: ty::BrAnon(i as u32, None),
+                    };
+                    tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)).into()
+                }
+                CanonicalVarKind::Const(_, ty) | CanonicalVarKind::PlaceholderConst(_, ty) => tcx
+                    .mk_const(ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i)), ty)
+                    .into(),
             }
-            CanonicalVarKind::Const(_, ty) | CanonicalVarKind::PlaceholderConst(_, ty) => tcx
-                .mk_const(ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i)), ty)
-                .into(),
-        })
-        .collect();
+        }));
 
     Ok(Canonical {
         max_universe: goal.max_universe,
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
index 730a8e61258..80a388b8498 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
@@ -95,6 +95,7 @@ impl<'tcx> ProvisionalCache<'tcx> {
     }
 
     pub(super) fn provisional_result(&self, entry_index: EntryIndex) -> QueryResult<'tcx> {
+        // FIXME: Responses should probably be `Copy` as well
         self.entries[entry_index].response.clone()
     }
 }
diff --git a/compiler/rustc_traits/src/chalk/mod.rs b/compiler/rustc_traits/src/chalk/mod.rs
index f76386fa720..13d83b92689 100644
--- a/compiler/rustc_traits/src/chalk/mod.rs
+++ b/compiler/rustc_traits/src/chalk/mod.rs
@@ -8,13 +8,10 @@ pub(crate) mod lowering;
 
 use rustc_data_structures::fx::FxHashMap;
 
-use rustc_index::vec::IndexVec;
-
 use rustc_middle::infer::canonical::{CanonicalTyVarKind, CanonicalVarKind};
 use rustc_middle::traits::ChalkRustInterner;
 use rustc_middle::ty::query::Providers;
-use rustc_middle::ty::subst::GenericArg;
-use rustc_middle::ty::{self, BoundVar, ParamTy, TyCtxt, TypeFoldable, TypeVisitable};
+use rustc_middle::ty::{self, ParamTy, TyCtxt, TypeFoldable, TypeVisitable};
 
 use rustc_infer::infer::canonical::{
     Canonical, CanonicalVarValues, Certainty, QueryRegionConstraints, QueryResponse,
@@ -100,11 +97,13 @@ pub(crate) fn evaluate_goal<'tcx>(
                          binders: chalk_ir::CanonicalVarKinds<_>| {
         use rustc_middle::infer::canonical::CanonicalVarInfo;
 
-        let mut var_values: IndexVec<BoundVar, GenericArg<'tcx>> = IndexVec::new();
         let mut reverse_param_substitutor = ReverseParamsSubstitutor::new(tcx, params);
-        subst.as_slice(interner).iter().for_each(|p| {
-            var_values.push(p.lower_into(interner).fold_with(&mut reverse_param_substitutor));
-        });
+        let var_values = tcx.mk_substs(
+            subst
+                .as_slice(interner)
+                .iter()
+                .map(|p| p.lower_into(interner).fold_with(&mut reverse_param_substitutor)),
+        );
         let variables: Vec<_> = binders
             .iter(interner)
             .map(|var| {
@@ -159,8 +158,7 @@ pub(crate) fn evaluate_goal<'tcx>(
                             max_universe: ty::UniverseIndex::from_usize(0),
                             variables: obligation.variables,
                             value: QueryResponse {
-                                var_values: CanonicalVarValues { var_values: IndexVec::new() }
-                                    .make_identity(tcx),
+                                var_values: CanonicalVarValues::dummy(),
                                 region_constraints: QueryRegionConstraints::default(),
                                 certainty: Certainty::Ambiguous,
                                 opaque_types: vec![],