Rollup merge of #80593 - jackh726:chalk-upgrade, r=nikomatsakis

Upgrade Chalk

~~Blocked on rust-lang/chalk#670~~
~~Now blocked on rust-lang/chalk#680 and release~~

In addition to the straight upgrade, I also tried to fix some tests by properly returning variables and max universes in the solution. Unfortunately, this actually triggers the same perf problem that rustc traits code runs into in `canonicalizer`. Not sure what the root cause of this problem is, or why it's supposed to be solved in chalk.

r? ```@nikomatsakis```

8 files changed, 174 insertions, 39 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 8bfdf23a30b..e3e631613a9 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -496,9 +496,9 @@ checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
 
 [[package]]
 name = "chalk-derive"
-version = "0.36.0"
+version = "0.55.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "9f88ce4deae1dace71e49b7611cfae2d5489de3530d6daba5758043c47ac3a10"
+checksum = "3983193cacd81f0f924acb666b7fe5e1a0d81db9f113fa69203eda7ea8ce8b6c"
 dependencies = [
  "proc-macro2",
  "quote",
@@ -508,9 +508,9 @@ dependencies = [
 
 [[package]]
 name = "chalk-engine"
-version = "0.36.0"
+version = "0.55.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "0e34c9b1b10616782143d7f49490f91ae94afaf2202de3ab0b2835e78b4f0ccc"
+checksum = "05a171ce5abbf0fbd06f221ab80ab182c7ef78603d23b858bc44e7ce8a86a396"
 dependencies = [
  "chalk-derive",
  "chalk-ir",
@@ -521,19 +521,20 @@ dependencies = [
 
 [[package]]
 name = "chalk-ir"
-version = "0.36.0"
+version = "0.55.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "63362c629c2014ab639b04029070763fb8224df136d1363d30e9ece4c8877da3"
+checksum = "a522f53af971e7678f472d687e053120157b3ae26e2ebd5ecbc0f5ab124f2cb6"
 dependencies = [
+ "bitflags",
  "chalk-derive",
  "lazy_static",
 ]
 
 [[package]]
 name = "chalk-solve"
-version = "0.36.0"
+version = "0.55.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "cac338a67af52a7f50bb2f8232e730a3518ce432dbe303246acfe525ddd838c7"
+checksum = "cdf79fb77a567e456a170f7ec84ea6584163d4ba3f13660cd182013d34ca667c"
 dependencies = [
  "chalk-derive",
  "chalk-ir",
@@ -4313,6 +4314,7 @@ dependencies = [
  "chalk-ir",
  "chalk-solve",
  "rustc_ast",
+ "rustc_attr",
  "rustc_data_structures",
  "rustc_hir",
  "rustc_index",
diff --git a/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs b/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
index 9002d251f12..aa4fd055d5e 100644
--- a/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
+++ b/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
@@ -353,10 +353,8 @@ impl<'cx, 'tcx> TypeFolder<'tcx> for Canonicalizer<'cx, 'tcx> {
                     // `TyVar(vid)` is unresolved, track its universe index in the canonicalized
                     // result.
                     Err(mut ui) => {
-                        if !self.infcx.unwrap().tcx.sess.opts.debugging_opts.chalk {
-                            // FIXME: perf problem described in #55921.
-                            ui = ty::UniverseIndex::ROOT;
-                        }
+                        // FIXME: perf problem described in #55921.
+                        ui = ty::UniverseIndex::ROOT;
                         self.canonicalize_ty_var(
                             CanonicalVarInfo {
                                 kind: CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)),
@@ -440,10 +438,8 @@ impl<'cx, 'tcx> TypeFolder<'tcx> for Canonicalizer<'cx, 'tcx> {
                     // `ConstVar(vid)` is unresolved, track its universe index in the
                     // canonicalized result
                     Err(mut ui) => {
-                        if !self.infcx.unwrap().tcx.sess.opts.debugging_opts.chalk {
-                            // FIXME: perf problem described in #55921.
-                            ui = ty::UniverseIndex::ROOT;
-                        }
+                        // FIXME: perf problem described in #55921.
+                        ui = ty::UniverseIndex::ROOT;
                         return self.canonicalize_const_var(
                             CanonicalVarInfo { kind: CanonicalVarKind::Const(ui) },
                             ct,
diff --git a/compiler/rustc_middle/Cargo.toml b/compiler/rustc_middle/Cargo.toml
index 47b7768b410..d33aad3b710 100644
--- a/compiler/rustc_middle/Cargo.toml
+++ b/compiler/rustc_middle/Cargo.toml
@@ -26,7 +26,7 @@ rustc_index = { path = "../rustc_index" }
 rustc_serialize = { path = "../rustc_serialize" }
 rustc_ast = { path = "../rustc_ast" }
 rustc_span = { path = "../rustc_span" }
-chalk-ir = "0.36.0"
+chalk-ir = "0.55.0"
 smallvec = { version = "1.0", features = ["union", "may_dangle"] }
 measureme = "9.0.0"
 rustc_session = { path = "../rustc_session" }
diff --git a/compiler/rustc_middle/src/traits/chalk.rs b/compiler/rustc_middle/src/traits/chalk.rs
index f864ad8ebcd..74873778f74 100644
--- a/compiler/rustc_middle/src/traits/chalk.rs
+++ b/compiler/rustc_middle/src/traits/chalk.rs
@@ -72,6 +72,7 @@ impl<'tcx> chalk_ir::interner::Interner for RustInterner<'tcx> {
     type InternedQuantifiedWhereClauses = Vec<chalk_ir::QuantifiedWhereClause<Self>>;
     type InternedVariableKinds = Vec<chalk_ir::VariableKind<Self>>;
     type InternedCanonicalVarKinds = Vec<chalk_ir::CanonicalVarKind<Self>>;
+    type InternedVariances = Vec<chalk_ir::Variance>;
     type InternedConstraints = Vec<chalk_ir::InEnvironment<chalk_ir::Constraint<Self>>>;
     type DefId = DefId;
     type InternedAdtId = &'tcx AdtDef;
@@ -86,17 +87,34 @@ impl<'tcx> chalk_ir::interner::Interner for RustInterner<'tcx> {
             write!(fmt, "{:?}", pci.consequence)?;
 
             let conditions = pci.conditions.interned();
+            let constraints = pci.constraints.interned();
 
             let conds = conditions.len();
-            if conds == 0 {
+            let consts = constraints.len();
+            if conds == 0 && consts == 0 {
                 return Ok(());
             }
 
             write!(fmt, " :- ")?;
-            for cond in &conditions[..conds - 1] {
-                write!(fmt, "{:?}, ", cond)?;
+
+            if conds != 0 {
+                for cond in &conditions[..conds - 1] {
+                    write!(fmt, "{:?}, ", cond)?;
+                }
+                write!(fmt, "{:?}", conditions[conds - 1])?;
+            }
+
+            if conds != 0 && consts != 0 {
+                write!(fmt, " ; ")?;
             }
-            write!(fmt, "{:?}", conditions[conds - 1])?;
+
+            if consts != 0 {
+                for constraint in &constraints[..consts - 1] {
+                    write!(fmt, "{:?}, ", constraint)?;
+                }
+                write!(fmt, "{:?}", constraints[consts - 1])?;
+            }
+
             Ok(())
         };
         Some(write())
@@ -351,6 +369,20 @@ impl<'tcx> chalk_ir::interner::Interner for RustInterner<'tcx> {
     ) -> &'a [chalk_ir::InEnvironment<chalk_ir::Constraint<Self>>] {
         constraints
     }
+
+    fn intern_variances<E>(
+        &self,
+        data: impl IntoIterator<Item = Result<chalk_ir::Variance, E>>,
+    ) -> Result<Self::InternedVariances, E> {
+        data.into_iter().collect::<Result<Vec<_>, _>>()
+    }
+
+    fn variances_data<'a>(
+        &self,
+        variances: &'a Self::InternedVariances,
+    ) -> &'a [chalk_ir::Variance] {
+        variances
+    }
 }
 
 impl<'tcx> chalk_ir::interner::HasInterner for RustInterner<'tcx> {
diff --git a/compiler/rustc_traits/Cargo.toml b/compiler/rustc_traits/Cargo.toml
index 8bd9e29629d..8fdbc3b76b4 100644
--- a/compiler/rustc_traits/Cargo.toml
+++ b/compiler/rustc_traits/Cargo.toml
@@ -6,15 +6,16 @@ edition = "2018"
 
 [dependencies]
 tracing = "0.1"
+rustc_attr = { path = "../rustc_attr" }
 rustc_middle = { path = "../rustc_middle" }
 rustc_data_structures = { path = "../rustc_data_structures" }
 rustc_hir = { path = "../rustc_hir" }
 rustc_index = { path = "../rustc_index" }
 rustc_ast = { path = "../rustc_ast" }
 rustc_span = { path = "../rustc_span" }
-chalk-ir = "0.36.0"
-chalk-solve = "0.36.0"
-chalk-engine = "0.36.0"
+chalk-ir = "0.55.0"
+chalk-solve = "0.55.0"
+chalk-engine = "0.55.0"
 smallvec = { version = "1.0", features = ["union", "may_dangle"] }
 rustc_infer = { path = "../rustc_infer" }
 rustc_trait_selection = { path = "../rustc_trait_selection" }
diff --git a/compiler/rustc_traits/src/chalk/db.rs b/compiler/rustc_traits/src/chalk/db.rs
index bb48ed93618..916186f4204 100644
--- a/compiler/rustc_traits/src/chalk/db.rs
+++ b/compiler/rustc_traits/src/chalk/db.rs
@@ -10,6 +10,9 @@ use rustc_middle::traits::ChalkRustInterner as RustInterner;
 use rustc_middle::ty::subst::{InternalSubsts, Subst, SubstsRef};
 use rustc_middle::ty::{self, AssocItemContainer, AssocKind, TyCtxt, TypeFoldable};
 
+use rustc_ast::ast;
+use rustc_attr as attr;
+
 use rustc_hir::def_id::DefId;
 
 use rustc_span::symbol::sym;
@@ -18,7 +21,6 @@ use std::fmt;
 use std::sync::Arc;
 
 use crate::chalk::lowering::{self, LowerInto};
-use rustc_ast::ast;
 
 pub struct RustIrDatabase<'tcx> {
     pub(crate) interner: RustInterner<'tcx>,
@@ -205,12 +207,32 @@ impl<'tcx> chalk_solve::RustIrDatabase<RustInterner<'tcx>> for RustIrDatabase<'t
     fn adt_repr(
         &self,
         adt_id: chalk_ir::AdtId<RustInterner<'tcx>>,
-    ) -> chalk_solve::rust_ir::AdtRepr {
+    ) -> Arc<chalk_solve::rust_ir::AdtRepr<RustInterner<'tcx>>> {
         let adt_def = adt_id.0;
-        chalk_solve::rust_ir::AdtRepr {
-            repr_c: adt_def.repr.c(),
-            repr_packed: adt_def.repr.packed(),
-        }
+        let int = |i| chalk_ir::TyKind::Scalar(chalk_ir::Scalar::Int(i)).intern(&self.interner);
+        let uint = |i| chalk_ir::TyKind::Scalar(chalk_ir::Scalar::Uint(i)).intern(&self.interner);
+        Arc::new(chalk_solve::rust_ir::AdtRepr {
+            c: adt_def.repr.c(),
+            packed: adt_def.repr.packed(),
+            int: adt_def.repr.int.map(|i| match i {
+                attr::IntType::SignedInt(ty) => match ty {
+                    ast::IntTy::Isize => int(chalk_ir::IntTy::Isize),
+                    ast::IntTy::I8 => int(chalk_ir::IntTy::I8),
+                    ast::IntTy::I16 => int(chalk_ir::IntTy::I16),
+                    ast::IntTy::I32 => int(chalk_ir::IntTy::I32),
+                    ast::IntTy::I64 => int(chalk_ir::IntTy::I64),
+                    ast::IntTy::I128 => int(chalk_ir::IntTy::I128),
+                },
+                attr::IntType::UnsignedInt(ty) => match ty {
+                    ast::UintTy::Usize => uint(chalk_ir::UintTy::Usize),
+                    ast::UintTy::U8 => uint(chalk_ir::UintTy::U8),
+                    ast::UintTy::U16 => uint(chalk_ir::UintTy::U16),
+                    ast::UintTy::U32 => uint(chalk_ir::UintTy::U32),
+                    ast::UintTy::U64 => uint(chalk_ir::UintTy::U64),
+                    ast::UintTy::U128 => uint(chalk_ir::UintTy::U128),
+                },
+            }),
+        })
     }
 
     fn fn_def_datum(
@@ -316,7 +338,11 @@ impl<'tcx> chalk_solve::RustIrDatabase<RustInterner<'tcx>> for RustIrDatabase<'t
             let self_ty = self_ty.fold_with(&mut regions_substitutor);
             let lowered_ty = self_ty.lower_into(&self.interner);
 
-            parameters[0].assert_ty_ref(&self.interner).could_match(&self.interner, &lowered_ty)
+            parameters[0].assert_ty_ref(&self.interner).could_match(
+                &self.interner,
+                self.unification_database(),
+                &lowered_ty,
+            )
         });
 
         let impls = matched_impls.map(chalk_ir::ImplId).collect();
@@ -541,6 +567,7 @@ impl<'tcx> chalk_solve::RustIrDatabase<RustInterner<'tcx>> for RustIrDatabase<'t
             Unsize => lang_items.unsize_trait(),
             Unpin => lang_items.unpin_trait(),
             CoerceUnsized => lang_items.coerce_unsized_trait(),
+            DiscriminantKind => lang_items.discriminant_kind_trait(),
         };
         def_id.map(chalk_ir::TraitId)
     }
@@ -586,7 +613,7 @@ impl<'tcx> chalk_solve::RustIrDatabase<RustInterner<'tcx>> for RustIrDatabase<'t
         let sig = &substs.as_slice(&self.interner)[substs.len(&self.interner) - 2];
         match sig.assert_ty_ref(&self.interner).kind(&self.interner) {
             chalk_ir::TyKind::Function(f) => {
-                let substitution = f.substitution.as_slice(&self.interner);
+                let substitution = f.substitution.0.as_slice(&self.interner);
                 let return_type =
                     substitution.last().unwrap().assert_ty_ref(&self.interner).clone();
                 // Closure arguments are tupled
@@ -644,6 +671,51 @@ impl<'tcx> chalk_solve::RustIrDatabase<RustInterner<'tcx>> for RustIrDatabase<'t
     ) -> Arc<chalk_solve::rust_ir::GeneratorWitnessDatum<RustInterner<'tcx>>> {
         unimplemented!()
     }
+
+    fn unification_database(&self) -> &dyn chalk_ir::UnificationDatabase<RustInterner<'tcx>> {
+        self
+    }
+
+    fn discriminant_type(
+        &self,
+        _: chalk_ir::Ty<RustInterner<'tcx>>,
+    ) -> chalk_ir::Ty<RustInterner<'tcx>> {
+        unimplemented!()
+    }
+}
+
+impl<'tcx> chalk_ir::UnificationDatabase<RustInterner<'tcx>> for RustIrDatabase<'tcx> {
+    fn fn_def_variance(
+        &self,
+        def_id: chalk_ir::FnDefId<RustInterner<'tcx>>,
+    ) -> chalk_ir::Variances<RustInterner<'tcx>> {
+        let variances = self.interner.tcx.variances_of(def_id.0);
+        chalk_ir::Variances::from_iter(
+            &self.interner,
+            variances.iter().map(|v| match v {
+                ty::Variance::Invariant => chalk_ir::Variance::Invariant,
+                ty::Variance::Covariant => chalk_ir::Variance::Covariant,
+                ty::Variance::Contravariant => chalk_ir::Variance::Contravariant,
+                ty::Variance::Bivariant => unimplemented!(),
+            }),
+        )
+    }
+
+    fn adt_variance(
+        &self,
+        def_id: chalk_ir::AdtId<RustInterner<'tcx>>,
+    ) -> chalk_ir::Variances<RustInterner<'tcx>> {
+        let variances = self.interner.tcx.variances_of(def_id.0.did);
+        chalk_ir::Variances::from_iter(
+            &self.interner,
+            variances.iter().map(|v| match v {
+                ty::Variance::Invariant => chalk_ir::Variance::Invariant,
+                ty::Variance::Covariant => chalk_ir::Variance::Covariant,
+                ty::Variance::Contravariant => chalk_ir::Variance::Contravariant,
+                ty::Variance::Bivariant => unimplemented!(),
+            }),
+        )
+    }
 }
 
 /// Creates a `InternalSubsts` that maps each generic parameter to a higher-ranked
diff --git a/compiler/rustc_traits/src/chalk/lowering.rs b/compiler/rustc_traits/src/chalk/lowering.rs
index 2a1a3f57e23..7d3589c4b6b 100644
--- a/compiler/rustc_traits/src/chalk/lowering.rs
+++ b/compiler/rustc_traits/src/chalk/lowering.rs
@@ -287,12 +287,12 @@ impl<'tcx> LowerInto<'tcx, chalk_ir::Ty<RustInterner<'tcx>>> for Ty<'tcx> {
                 chalk_ir::TyKind::Function(chalk_ir::FnPointer {
                     num_binders: binders.len(interner),
                     sig: sig.lower_into(interner),
-                    substitution: chalk_ir::Substitution::from_iter(
+                    substitution: chalk_ir::FnSubst(chalk_ir::Substitution::from_iter(
                         interner,
                         inputs_and_outputs.iter().map(|ty| {
                             chalk_ir::GenericArgData::Ty(ty.lower_into(interner)).intern(interner)
                         }),
-                    ),
+                    )),
                 })
             }
             ty::Dynamic(predicates, region) => chalk_ir::TyKind::Dyn(chalk_ir::DynTy {
@@ -478,6 +478,10 @@ impl<'tcx> LowerInto<'tcx, Region<'tcx>> for &chalk_ir::Lifetime<RustInterner<'t
             }
             chalk_ir::LifetimeData::Static => ty::RegionKind::ReStatic,
             chalk_ir::LifetimeData::Phantom(_, _) => unimplemented!(),
+            chalk_ir::LifetimeData::Empty(ui) => {
+                ty::RegionKind::ReEmpty(ty::UniverseIndex::from_usize(ui.counter))
+            }
+            chalk_ir::LifetimeData::Erased => ty::RegionKind::ReErased,
         };
         interner.tcx.mk_region(kind)
     }
diff --git a/compiler/rustc_traits/src/chalk/mod.rs b/compiler/rustc_traits/src/chalk/mod.rs
index bd2f87f70a2..d98f18182c8 100644
--- a/compiler/rustc_traits/src/chalk/mod.rs
+++ b/compiler/rustc_traits/src/chalk/mod.rs
@@ -105,14 +105,40 @@ crate fn evaluate_goal<'tcx>(
     // really need this and so it's really minimal.
     // Right now, we also treat a `Unique` solution the same as
     // `Ambig(Definite)`. This really isn't right.
-    let make_solution = |subst: chalk_ir::Substitution<_>| {
+    let make_solution = |subst: chalk_ir::Substitution<_>,
+                         binders: chalk_ir::CanonicalVarKinds<_>| {
+        use rustc_middle::infer::canonical::CanonicalVarInfo;
+
         let mut var_values: IndexVec<BoundVar, GenericArg<'tcx>> = IndexVec::new();
         subst.as_slice(&interner).iter().for_each(|p| {
             var_values.push(p.lower_into(&interner));
         });
+        let variables: Vec<_> = binders
+            .iter(&interner)
+            .map(|var| {
+                let kind = match var.kind {
+                    chalk_ir::VariableKind::Ty(ty_kind) => CanonicalVarKind::Ty(match ty_kind {
+                        chalk_ir::TyVariableKind::General => CanonicalTyVarKind::General(
+                            ty::UniverseIndex::from_usize(var.skip_kind().counter),
+                        ),
+                        chalk_ir::TyVariableKind::Integer => CanonicalTyVarKind::Int,
+                        chalk_ir::TyVariableKind::Float => CanonicalTyVarKind::Float,
+                    }),
+                    chalk_ir::VariableKind::Lifetime => CanonicalVarKind::Region(
+                        ty::UniverseIndex::from_usize(var.skip_kind().counter),
+                    ),
+                    chalk_ir::VariableKind::Const(_) => CanonicalVarKind::Const(
+                        ty::UniverseIndex::from_usize(var.skip_kind().counter),
+                    ),
+                };
+                CanonicalVarInfo { kind }
+            })
+            .collect();
+        let max_universe =
+            binders.iter(&interner).map(|v| v.skip_kind().counter).max().unwrap_or(0);
         let sol = Canonical {
-            max_universe: ty::UniverseIndex::from_usize(0),
-            variables: obligation.variables.clone(),
+            max_universe: ty::UniverseIndex::from_usize(max_universe),
+            variables: tcx.intern_canonical_var_infos(&variables),
             value: QueryResponse {
                 var_values: CanonicalVarValues { var_values },
                 region_constraints: QueryRegionConstraints::default(),
@@ -126,11 +152,13 @@ crate fn evaluate_goal<'tcx>(
         .map(|s| match s {
             Solution::Unique(subst) => {
                 // FIXME(chalk): handle constraints
-                make_solution(subst.value.subst)
+                make_solution(subst.value.subst, subst.binders)
             }
             Solution::Ambig(guidance) => {
                 match guidance {
-                    chalk_solve::Guidance::Definite(subst) => make_solution(subst.value),
+                    chalk_solve::Guidance::Definite(subst) => {
+                        make_solution(subst.value, subst.binders)
+                    }
                     chalk_solve::Guidance::Suggested(_) => unimplemented!(),
                     chalk_solve::Guidance::Unknown => {
                         // chalk_fulfill doesn't use the var_values here, so