diff options
Diffstat (limited to 'compiler')
| -rw-r--r-- | compiler/rustc_infer/src/infer/at.rs | 28 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/canonical/mod.rs | 8 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/canonical/query_response.rs | 20 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/canonical/substitute.rs | 4 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/infer/canonical.rs | 62 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/infer/mod.rs | 3 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/traits/solve.rs | 16 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/sty.rs | 9 | ||||
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs | 390 | ||||
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/canonical/mod.rs | 240 | ||||
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/eval_ctxt.rs | 11 | ||||
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/mod.rs | 97 | ||||
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/project_goals.rs | 5 |
13 files changed, 805 insertions, 88 deletions
diff --git a/compiler/rustc_infer/src/infer/at.rs b/compiler/rustc_infer/src/infer/at.rs index c952ddc827a..7d9bae735e5 100644 --- a/compiler/rustc_infer/src/infer/at.rs +++ b/compiler/rustc_infer/src/infer/at.rs @@ -369,6 +369,34 @@ impl<'tcx> ToTrace<'tcx> for Const<'tcx> { } } +impl<'tcx> ToTrace<'tcx> for ty::GenericArg<'tcx> { + fn to_trace( + _: TyCtxt<'tcx>, + cause: &ObligationCause<'tcx>, + a_is_expected: bool, + a: Self, + b: Self, + ) -> TypeTrace<'tcx> { + use GenericArgKind::*; + TypeTrace { + cause: cause.clone(), + values: match (a.unpack(), b.unpack()) { + (Lifetime(a), Lifetime(b)) => Regions(ExpectedFound::new(a_is_expected, a, b)), + (Type(a), Type(b)) => Terms(ExpectedFound::new(a_is_expected, a.into(), b.into())), + (Const(a), Const(b)) => { + Terms(ExpectedFound::new(a_is_expected, a.into(), b.into())) + } + + (Lifetime(_), Type(_) | Const(_)) + | (Type(_), Lifetime(_) | Const(_)) + | (Const(_), Lifetime(_) | Type(_)) => { + bug!("relating different kinds: {a:?} {b:?}") + } + }, + } + } +} + impl<'tcx> ToTrace<'tcx> for ty::Term<'tcx> { fn to_trace( _: TyCtxt<'tcx>, diff --git a/compiler/rustc_infer/src/infer/canonical/mod.rs b/compiler/rustc_infer/src/infer/canonical/mod.rs index 8c782a933a5..ce230afdab3 100644 --- a/compiler/rustc_infer/src/infer/canonical/mod.rs +++ b/compiler/rustc_infer/src/infer/canonical/mod.rs @@ -30,7 +30,7 @@ use rustc_middle::ty::{self, List, TyCtxt}; use rustc_span::source_map::Span; pub use rustc_middle::infer::canonical::*; -use substitute::CanonicalExt; +pub use substitute::CanonicalExt; mod canonicalizer; pub mod query_response; @@ -100,7 +100,11 @@ impl<'tcx> InferCtxt<'tcx> { /// variable for it. If this is an existentially quantified /// variable, then you'll get a new inference variable; if it is a /// universally quantified variable, you get a placeholder. - fn instantiate_canonical_var( + /// + /// FIXME(-Ztrait-solver=next): This is public because it's used by the + /// new trait solver which has a different canonicalization routine. + /// We should somehow deduplicate all of this. + pub fn instantiate_canonical_var( &self, span: Span, cv_info: CanonicalVarInfo<'tcx>, diff --git a/compiler/rustc_infer/src/infer/canonical/query_response.rs b/compiler/rustc_infer/src/infer/canonical/query_response.rs index 832af91a431..436d29c2449 100644 --- a/compiler/rustc_infer/src/infer/canonical/query_response.rs +++ b/compiler/rustc_infer/src/infer/canonical/query_response.rs @@ -151,11 +151,21 @@ impl<'tcx> InferCtxt<'tcx> { }) } - /// FIXME: This method should only be used for canonical queries and therefore be private. - /// - /// As the new solver does canonicalization slightly differently, this is also used there - /// for now. This should hopefully change fairly soon. - pub fn take_opaque_types_for_query_response(&self) -> Vec<(Ty<'tcx>, Ty<'tcx>)> { + /// Used by the new solver as that one takes the opaque types at the end of a probe + /// to deal with multiple candidates without having to recompute them. + pub fn clone_opaque_types_for_query_response(&self) -> Vec<(Ty<'tcx>, Ty<'tcx>)> { + self.inner + .borrow() + .opaque_type_storage + .opaque_types + .iter() + .map(|&(k, ref v)| { + (self.tcx.mk_opaque(k.def_id.to_def_id(), k.substs), v.hidden_type.ty) + }) + .collect() + } + + fn take_opaque_types_for_query_response(&self) -> Vec<(Ty<'tcx>, Ty<'tcx>)> { std::mem::take(&mut self.inner.borrow_mut().opaque_type_storage.opaque_types) .into_iter() .map(|(k, v)| (self.tcx.mk_opaque(k.def_id.to_def_id(), k.substs), v.hidden_type.ty)) diff --git a/compiler/rustc_infer/src/infer/canonical/substitute.rs b/compiler/rustc_infer/src/infer/canonical/substitute.rs index c5c6fc41b9e..cac3b407251 100644 --- a/compiler/rustc_infer/src/infer/canonical/substitute.rs +++ b/compiler/rustc_infer/src/infer/canonical/substitute.rs @@ -11,7 +11,9 @@ use rustc_middle::ty::fold::{FnMutDelegate, TypeFoldable}; use rustc_middle::ty::subst::GenericArgKind; use rustc_middle::ty::{self, TyCtxt}; -pub(super) trait CanonicalExt<'tcx, V> { +/// FIXME(-Ztrait-solver=next): This or public because it is shared with the +/// new trait solver implementation. We should deduplicate canonicalization. +pub trait CanonicalExt<'tcx, V> { /// Instantiate the wrapped value, replacing each canonical value /// with the value given in `var_values`. fn substitute(&self, tcx: TyCtxt<'tcx>, var_values: &CanonicalVarValues<'tcx>) -> V diff --git a/compiler/rustc_middle/src/infer/canonical.rs b/compiler/rustc_middle/src/infer/canonical.rs index 8712514a384..7f8fc17744d 100644 --- a/compiler/rustc_middle/src/infer/canonical.rs +++ b/compiler/rustc_middle/src/infer/canonical.rs @@ -123,6 +123,11 @@ impl<'tcx> CanonicalVarInfo<'tcx> { self.kind.universe() } + #[must_use] + pub fn with_updated_universe(self, ui: ty::UniverseIndex) -> CanonicalVarInfo<'tcx> { + CanonicalVarInfo { kind: self.kind.with_updated_universe(ui) } + } + pub fn is_existential(&self) -> bool { match self.kind { CanonicalVarKind::Ty(_) => true, @@ -133,6 +138,28 @@ impl<'tcx> CanonicalVarInfo<'tcx> { CanonicalVarKind::PlaceholderConst(_, _) => false, } } + + pub fn is_region(&self) -> bool { + match self.kind { + CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => true, + CanonicalVarKind::Ty(_) + | CanonicalVarKind::PlaceholderTy(_) + | CanonicalVarKind::Const(_, _) + | CanonicalVarKind::PlaceholderConst(_, _) => false, + } + } + + pub fn expect_anon_placeholder(self) -> u32 { + match self.kind { + CanonicalVarKind::Ty(_) + | CanonicalVarKind::Region(_) + | CanonicalVarKind::Const(_, _) => bug!("expected placeholder: {self:?}"), + + CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.name.expect_anon(), + CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.name.expect_anon(), + CanonicalVarKind::PlaceholderConst(placeholder, _) => placeholder.name.as_u32(), + } + } } /// Describes the "kind" of the canonical variable. This is a "kind" @@ -177,6 +204,38 @@ impl<'tcx> CanonicalVarKind<'tcx> { CanonicalVarKind::PlaceholderConst(placeholder, _) => placeholder.universe, } } + + /// Replaces the universe of this canonical variable with `ui`. + /// + /// In case this is a float or int variable, this causes an ICE if + /// the updated universe is not the root. + pub fn with_updated_universe(self, ui: ty::UniverseIndex) -> CanonicalVarKind<'tcx> { + match self { + CanonicalVarKind::Ty(kind) => match kind { + CanonicalTyVarKind::General(_) => { + CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)) + } + CanonicalTyVarKind::Int | CanonicalTyVarKind::Float => { + assert_eq!(ui, ty::UniverseIndex::ROOT); + CanonicalVarKind::Ty(kind) + } + }, + CanonicalVarKind::PlaceholderTy(placeholder) => { + CanonicalVarKind::PlaceholderTy(ty::Placeholder { universe: ui, ..placeholder }) + } + CanonicalVarKind::Region(_) => CanonicalVarKind::Region(ui), + CanonicalVarKind::PlaceholderRegion(placeholder) => { + CanonicalVarKind::PlaceholderRegion(ty::Placeholder { universe: ui, ..placeholder }) + } + CanonicalVarKind::Const(_, ty) => CanonicalVarKind::Const(ui, ty), + CanonicalVarKind::PlaceholderConst(placeholder, ty) => { + CanonicalVarKind::PlaceholderConst( + ty::Placeholder { universe: ui, ..placeholder }, + ty, + ) + } + } + } } /// Rust actually has more than one category of type variables; @@ -213,7 +272,8 @@ pub struct QueryResponse<'tcx, R> { pub value: R, } -#[derive(Clone, Debug, Default, HashStable, TypeFoldable, TypeVisitable, Lift)] +#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)] +#[derive(HashStable, TypeFoldable, TypeVisitable, Lift)] pub struct QueryRegionConstraints<'tcx> { pub outlives: Vec<QueryOutlivesConstraint<'tcx>>, pub member_constraints: Vec<MemberConstraint<'tcx>>, diff --git a/compiler/rustc_middle/src/infer/mod.rs b/compiler/rustc_middle/src/infer/mod.rs index 38868c21049..2db59f37f40 100644 --- a/compiler/rustc_middle/src/infer/mod.rs +++ b/compiler/rustc_middle/src/infer/mod.rs @@ -12,7 +12,8 @@ use rustc_span::Span; /// ```text /// R0 member of [O1..On] /// ``` -#[derive(Debug, Clone, HashStable, TypeFoldable, TypeVisitable, Lift)] +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +#[derive(HashStable, TypeFoldable, TypeVisitable, Lift)] pub struct MemberConstraint<'tcx> { /// The `DefId` and substs of the opaque type causing this constraint. /// Used for error reporting. diff --git a/compiler/rustc_middle/src/traits/solve.rs b/compiler/rustc_middle/src/traits/solve.rs index c5bf9717f03..bd43867a3da 100644 --- a/compiler/rustc_middle/src/traits/solve.rs +++ b/compiler/rustc_middle/src/traits/solve.rs @@ -2,6 +2,7 @@ use std::ops::ControlFlow; use rustc_data_structures::intern::Interned; +use crate::infer::canonical::QueryRegionConstraints; use crate::ty::{ FallibleTypeFolder, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeVisitable, TypeVisitor, }; @@ -18,20 +19,25 @@ impl<'tcx> std::ops::Deref for ExternalConstraints<'tcx> { } /// Additional constraints returned on success. -#[derive(Debug, PartialEq, Eq, Clone, Hash, Default)] +#[derive(Debug, PartialEq, Eq, Clone, Hash, Default, TypeFoldable, TypeVisitable)] pub struct ExternalConstraintsData<'tcx> { // FIXME: implement this. - pub regions: (), + pub region_constraints: QueryRegionConstraints<'tcx>, pub opaque_types: Vec<(Ty<'tcx>, Ty<'tcx>)>, } +// FIXME: Having to clone `region_constraints` for folding feels bad and +// probably isn't great wrt performance. +// +// Not sure how to fix this, maybe we should also intern `opaque_types` and +// `region_constraints` here or something. impl<'tcx> TypeFoldable<TyCtxt<'tcx>> for ExternalConstraints<'tcx> { fn try_fold_with<F: FallibleTypeFolder<TyCtxt<'tcx>>>( self, folder: &mut F, ) -> Result<Self, F::Error> { Ok(FallibleTypeFolder::interner(folder).mk_external_constraints(ExternalConstraintsData { - regions: (), + region_constraints: self.region_constraints.clone().try_fold_with(folder)?, opaque_types: self .opaque_types .iter() @@ -42,7 +48,7 @@ impl<'tcx> TypeFoldable<TyCtxt<'tcx>> for ExternalConstraints<'tcx> { fn fold_with<F: TypeFolder<TyCtxt<'tcx>>>(self, folder: &mut F) -> Self { TypeFolder::interner(folder).mk_external_constraints(ExternalConstraintsData { - regions: (), + region_constraints: self.region_constraints.clone().fold_with(folder), opaque_types: self.opaque_types.iter().map(|opaque| opaque.fold_with(folder)).collect(), }) } @@ -53,7 +59,7 @@ impl<'tcx> TypeVisitable<TyCtxt<'tcx>> for ExternalConstraints<'tcx> { &self, visitor: &mut V, ) -> std::ops::ControlFlow<V::BreakTy> { - self.regions.visit_with(visitor)?; + self.region_constraints.visit_with(visitor)?; self.opaque_types.visit_with(visitor)?; ControlFlow::Continue(()) } diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs index ba714541c9e..e6a73e8bb1c 100644 --- a/compiler/rustc_middle/src/ty/sty.rs +++ b/compiler/rustc_middle/src/ty/sty.rs @@ -107,6 +107,15 @@ impl BoundRegionKind { _ => None, } } + + pub fn expect_anon(&self) -> u32 { + match *self { + BoundRegionKind::BrNamed(_, _) | BoundRegionKind::BrEnv => { + bug!("expected anon region: {self:?}") + } + BoundRegionKind::BrAnon(idx, _) => idx, + } + } } pub trait Article { diff --git a/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs b/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs new file mode 100644 index 00000000000..c048d4a2aad --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs @@ -0,0 +1,390 @@ +use std::cmp::Ordering; + +use crate::infer::InferCtxt; +use rustc_middle::infer::canonical::Canonical; +use rustc_middle::infer::canonical::CanonicalTyVarKind; +use rustc_middle::infer::canonical::CanonicalVarInfo; +use rustc_middle::infer::canonical::CanonicalVarInfos; +use rustc_middle::infer::canonical::CanonicalVarKind; +use rustc_middle::ty::BoundRegionKind::BrAnon; +use rustc_middle::ty::BoundTyKind; +use rustc_middle::ty::TyCtxt; +use rustc_middle::ty::TypeVisitableExt; +use rustc_middle::ty::{self, Ty}; +use rustc_middle::ty::{TypeFoldable, TypeFolder, TypeSuperFoldable}; + +/// Whether we're canonicalizing a query input or the query reponse. +/// +/// When canonicalizing an input we're in the context of the caller +/// while canonicalizing the response happens in the context of the +/// query. +#[derive(Debug, Clone, Copy)] +pub enum CanonicalizeMode { + Input, + /// FIXME: We currently return region constraints refering to + /// placeholders and inference variables from a binder instantiated + /// inside of the query. + /// + /// In the long term we should eagerly deal with these constraints + /// inside of the query and only propagate constraints which are + /// actually nameable by the caller. + Response { + /// The highest universe nameable by the caller. + /// + /// All variables in a universe nameable by the caller get mapped + /// to the root universe in the response and then mapped back to + /// their correct universe when applying the query response in the + /// context of the caller. + /// + /// This doesn't work for universes created inside of the query so + /// we do remember their universe in the response. + max_input_universe: ty::UniverseIndex, + }, +} + +pub struct Canonicalizer<'a, 'tcx> { + infcx: &'a InferCtxt<'tcx>, + canonicalize_mode: CanonicalizeMode, + + variables: &'a mut Vec<ty::GenericArg<'tcx>>, + primitive_var_infos: Vec<CanonicalVarInfo<'tcx>>, + binder_index: ty::DebruijnIndex, +} + +impl<'a, 'tcx> Canonicalizer<'a, 'tcx> { + #[instrument(level = "debug", skip(infcx), ret)] + pub fn canonicalize<T: TypeFoldable<TyCtxt<'tcx>>>( + infcx: &'a InferCtxt<'tcx>, + canonicalize_mode: CanonicalizeMode, + variables: &'a mut Vec<ty::GenericArg<'tcx>>, + value: T, + ) -> Canonical<'tcx, T> { + let mut canonicalizer = Canonicalizer { + infcx, + canonicalize_mode, + + variables, + primitive_var_infos: Vec::new(), + binder_index: ty::INNERMOST, + }; + + let value = value.fold_with(&mut canonicalizer); + assert!(!value.needs_infer()); + assert!(!value.has_placeholders()); + + let (max_universe, variables) = canonicalizer.finalize(); + + Canonical { max_universe, variables, value } + } + + fn finalize(self) -> (ty::UniverseIndex, CanonicalVarInfos<'tcx>) { + let mut var_infos = self.primitive_var_infos; + // See the rustc-dev-guide section about how we deal with universes + // during canonicalization in the new solver. + match self.canonicalize_mode { + // We try to deduplicate as many query calls as possible and hide + // all information which should not matter for the solver. + // + // For this we compress universes as much as possible. + CanonicalizeMode::Input => {} + // When canonicalizing a response we map a universes already entered + // by the caller to the root universe and only return useful universe + // information for placeholders and inference variables created inside + // of the query. + CanonicalizeMode::Response { max_input_universe } => { + for var in var_infos.iter_mut() { + let uv = var.universe(); + let new_uv = ty::UniverseIndex::from( + uv.index().saturating_sub(max_input_universe.index()), + ); + *var = var.with_updated_universe(new_uv); + } + let max_universe = var_infos + .iter() + .map(|info| info.universe()) + .max() + .unwrap_or(ty::UniverseIndex::ROOT); + + let var_infos = self.infcx.tcx.mk_canonical_var_infos(&var_infos); + return (max_universe, var_infos); + } + } + + // Given a `var_infos` with existentials `En` and universals `Un` in + // universes `n`, this algorithm compresses them in place so that: + // + // - the new universe indices are as small as possible + // - we only create a new universe if we would otherwise put a placeholder in + // the same compressed universe as an existential which cannot name it + // + // Let's walk through an example: + // - var_infos: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 0, next_orig_uv: 0 + // - var_infos: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 0, next_orig_uv: 1 + // - var_infos: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 1, next_orig_uv: 2 + // - var_infos: [E0, U1, E5, U1, E1, E6, U6], curr_compressed_uv: 1, next_orig_uv: 5 + // - var_infos: [E0, U1, E1, U1, E1, E6, U6], curr_compressed_uv: 1, next_orig_uv: 6 + // - var_infos: [E0, U1, E1, U1, E1, E2, U2], curr_compressed_uv: 2, next_orig_uv: - + // + // This algorithm runs in `O(n²)` where `n` is the number of different universe + // indices in the input. This should be fine as `n` is expected to be small. + let mut curr_compressed_uv = ty::UniverseIndex::ROOT; + let mut existential_in_new_uv = false; + let mut next_orig_uv = Some(ty::UniverseIndex::ROOT); + while let Some(orig_uv) = next_orig_uv.take() { + let mut update_uv = |var: &mut CanonicalVarInfo<'tcx>, orig_uv, is_existential| { + let uv = var.universe(); + match uv.cmp(&orig_uv) { + Ordering::Less => (), // Already updated + Ordering::Equal => { + if is_existential { + existential_in_new_uv = true; + } else if existential_in_new_uv { + // `var` is a placeholder from a universe which is not nameable + // by an existential which we already put into the compressed + // universe `curr_compressed_uv`. We therefore have to create a + // new universe for `var`. + curr_compressed_uv = curr_compressed_uv.next_universe(); + existential_in_new_uv = false; + } + + *var = var.with_updated_universe(curr_compressed_uv); + } + Ordering::Greater => { + // We can ignore this variable in this iteration. We only look at + // universes which actually occur in the input for performance. + // + // For this we set `next_orig_uv` to the next smallest, not yet compressed, + // universe of the input. + if next_orig_uv.map_or(true, |curr_next_uv| uv.cannot_name(curr_next_uv)) { + next_orig_uv = Some(uv); + } + } + } + }; + + // For each universe which occurs in the input, we first iterate over all + // placeholders and then over all inference variables. + // + // Whenever we compress the universe of a placeholder, no existential with + // an already compressed universe can name that placeholder. + for is_existential in [false, true] { + for var in var_infos.iter_mut() { + // We simply put all regions from the input into the highest + // compressed universe, so we only deal with them at the end. + if !var.is_region() { + if is_existential == var.is_existential() { + update_uv(var, orig_uv, is_existential) + } + } + } + } + } + + for var in var_infos.iter_mut() { + if var.is_region() { + assert!(var.is_existential()); + *var = var.with_updated_universe(curr_compressed_uv); + } + } + + let var_infos = self.infcx.tcx.mk_canonical_var_infos(&var_infos); + (curr_compressed_uv, var_infos) + } +} + +impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { + fn interner(&self) -> TyCtxt<'tcx> { + self.infcx.tcx + } + + fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T> + where + T: TypeFoldable<TyCtxt<'tcx>>, + { + self.binder_index.shift_in(1); + let t = t.super_fold_with(self); + self.binder_index.shift_out(1); + t + } + + fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { + let r = self.infcx.shallow_resolve(r); + let kind = match *r { + ty::ReLateBound(..) => return r, + + ty::ReStatic => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Response { .. } => return r, + }, + + ty::ReErased | ty::ReFree(_) | ty::ReEarlyBound(_) => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Response { .. } => bug!("unexpected region in response: {r:?}"), + }, + + ty::RePlaceholder(placeholder) => match self.canonicalize_mode { + // We canonicalize placeholder regions as existentials in query inputs. + CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Response { max_input_universe } => { + // If we have a placeholder region inside of a query, it must be from + // a new universe. + if max_input_universe.can_name(placeholder.universe) { + bug!("new placeholder in universe {max_input_universe:?}: {r:?}"); + } + CanonicalVarKind::PlaceholderRegion(placeholder) + } + }, + + ty::ReVar(_) => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Response { .. } => { + CanonicalVarKind::Region(self.infcx.universe_of_region(r)) + } + }, + + ty::ReError(_) => return r, + }; + + let existing_bound_var = match self.canonicalize_mode { + CanonicalizeMode::Input => None, + CanonicalizeMode::Response { .. } => { + self.variables.iter().position(|&v| v == r.into()).map(ty::BoundVar::from) + } + }; + let var = existing_bound_var.unwrap_or_else(|| { + let var = ty::BoundVar::from(self.variables.len()); + self.variables.push(r.into()); + self.primitive_var_infos.push(CanonicalVarInfo { kind }); + var + }); + let br = ty::BoundRegion { var, kind: BrAnon(var.as_u32(), None) }; + self.interner().mk_re_late_bound(self.binder_index, br) + } + + fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { + let kind = match *t.kind() { + ty::Infer(ty::TyVar(vid)) => match self.infcx.probe_ty_var(vid) { + Ok(t) => return self.fold_ty(t), + Err(ui) => CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)), + }, + ty::Infer(ty::IntVar(_)) => { + let nt = self.infcx.shallow_resolve(t); + if nt != t { + return self.fold_ty(nt); + } else { + CanonicalVarKind::Ty(CanonicalTyVarKind::Int) + } + } + ty::Infer(ty::FloatVar(_)) => { + let nt = self.infcx.shallow_resolve(t); + if nt != t { + return self.fold_ty(nt); + } else { + CanonicalVarKind::Ty(CanonicalTyVarKind::Int) + } + } + ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { + bug!("fresh var during canonicalization: {t:?}") + } + ty::Placeholder(placeholder) => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::PlaceholderTy(ty::Placeholder { + universe: placeholder.universe, + name: BoundTyKind::Anon(self.variables.len() as u32), + }), + CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder), + }, + ty::Param(_) => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::PlaceholderTy(ty::Placeholder { + universe: ty::UniverseIndex::ROOT, + name: ty::BoundTyKind::Anon(self.variables.len() as u32), + }), + CanonicalizeMode::Response { .. } => bug!("param ty in response: {t:?}"), + }, + ty::Bool + | ty::Char + | ty::Int(_) + | ty::Uint(_) + | ty::Float(_) + | ty::Adt(_, _) + | ty::Foreign(_) + | ty::Str + | ty::Array(_, _) + | ty::Slice(_) + | ty::RawPtr(_) + | ty::Ref(_, _, _) + | ty::FnDef(_, _) + | ty::FnPtr(_) + | ty::Dynamic(_, _, _) + | ty::Closure(_, _) + | ty::Generator(_, _, _) + | ty::GeneratorWitness(_) + | ty::GeneratorWitnessMIR(..) + | ty::Never + | ty::Tuple(_) + | ty::Alias(_, _) + | ty::Bound(_, _) + | ty::Error(_) => return t.super_fold_with(self), + }; + + let var = ty::BoundVar::from( + self.variables.iter().position(|&v| v == t.into()).unwrap_or_else(|| { + let var = self.variables.len(); + self.variables.push(t.into()); + self.primitive_var_infos.push(CanonicalVarInfo { kind }); + var + }), + ); + let bt = ty::BoundTy { var, kind: BoundTyKind::Anon(var.index() as u32) }; + self.interner().mk_bound(self.binder_index, bt) + } + + fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> { + let kind = match c.kind() { + ty::ConstKind::Infer(ty::InferConst::Var(vid)) => match self.infcx.probe_const_var(vid) + { + Ok(c) => return self.fold_const(c), + Err(universe) => CanonicalVarKind::Const(universe, c.ty()), + }, + ty::ConstKind::Infer(ty::InferConst::Fresh(_)) => { + bug!("fresh var during canonicalization: {c:?}") + } + ty::ConstKind::Placeholder(placeholder) => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::PlaceholderConst( + ty::Placeholder { + universe: placeholder.universe, + name: ty::BoundVar::from(self.variables.len()), + }, + c.ty(), + ), + CanonicalizeMode::Response { .. } => { + CanonicalVarKind::PlaceholderConst(placeholder, c.ty()) + } + }, + ty::ConstKind::Param(_) => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::PlaceholderConst( + ty::Placeholder { + universe: ty::UniverseIndex::ROOT, + name: ty::BoundVar::from(self.variables.len()), + }, + c.ty(), + ), + CanonicalizeMode::Response { .. } => bug!("param ty in response: {c:?}"), + }, + ty::ConstKind::Bound(_, _) + | ty::ConstKind::Unevaluated(_) + | ty::ConstKind::Value(_) + | ty::ConstKind::Error(_) + | ty::ConstKind::Expr(_) => return c.super_fold_with(self), + }; + + let var = ty::BoundVar::from( + self.variables.iter().position(|&v| v == c.into()).unwrap_or_else(|| { + let var = self.variables.len(); + self.variables.push(c.into()); + self.primitive_var_infos.push(CanonicalVarInfo { kind }); + var + }), + ); + self.interner().mk_const(ty::ConstKind::Bound(self.binder_index, var), c.ty()) + } +} diff --git a/compiler/rustc_trait_selection/src/solve/canonical/mod.rs b/compiler/rustc_trait_selection/src/solve/canonical/mod.rs new file mode 100644 index 00000000000..8c3be8da16b --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/canonical/mod.rs @@ -0,0 +1,240 @@ +/// Canonicalization is used to separate some goal from its context, +/// throwing away unnecessary information in the process. +/// +/// This is necessary to cache goals containing inference variables +/// and placeholders without restricting them to the current `InferCtxt`. +/// +/// Canonicalization is fairly involved, for more details see the relevant +/// section of the [rustc-dev-guide][c]. +/// +/// [c]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html +use self::canonicalize::{CanonicalizeMode, Canonicalizer}; +use super::{CanonicalGoal, Certainty, EvalCtxt, Goal}; +use super::{CanonicalResponse, ExternalConstraints, QueryResult, Response}; +use rustc_infer::infer::canonical::query_response::make_query_region_constraints; +use rustc_infer::infer::canonical::CanonicalVarValues; +use rustc_infer::infer::canonical::{CanonicalExt, QueryRegionConstraints}; +use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::solve::ExternalConstraintsData; +use rustc_infer::traits::ObligationCause; +use rustc_middle::ty::{self, GenericArgKind}; +use rustc_span::DUMMY_SP; +use std::iter; +use std::ops::Deref; + +mod canonicalize; + +impl<'tcx> EvalCtxt<'_, 'tcx> { + /// Canonicalizes the goal remembering the original values + /// for each bound variable. + pub(super) fn canonicalize_goal( + &self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + ) -> (Vec<ty::GenericArg<'tcx>>, CanonicalGoal<'tcx>) { + let mut orig_values = Default::default(); + let canonical_goal = Canonicalizer::canonicalize( + self.infcx, + CanonicalizeMode::Input, + &mut orig_values, + goal, + ); + (orig_values, canonical_goal) + } + + /// To return the constraints of a canonical query to the caller, we canonicalize: + /// + /// - `var_values`: a map from bound variables in the canonical goal to + /// the values inferred while solving the instantiated goal. + /// - `external_constraints`: additional constraints which aren't expressable + /// using simple unification of inference variables. + #[instrument(level = "debug", skip(self))] + pub(super) fn make_canonical_response(&self, certainty: Certainty) -> QueryResult<'tcx> { + let external_constraints = self.compute_external_query_constraints()?; + + let response = Response { var_values: self.var_values, external_constraints, certainty }; + let canonical = Canonicalizer::canonicalize( + self.infcx, + CanonicalizeMode::Response { max_input_universe: self.max_input_universe }, + &mut Default::default(), + response, + ); + Ok(canonical) + } + + #[instrument(level = "debug", skip(self), ret)] + fn compute_external_query_constraints(&self) -> Result<ExternalConstraints<'tcx>, NoSolution> { + // Cannot use `take_registered_region_obligations` as we may compute the response + // inside of a `probe` whenever we have multiple choices inside of the solver. + let region_obligations = self.infcx.inner.borrow().region_obligations().to_owned(); + let region_constraints = self.infcx.with_region_constraints(|region_constraints| { + make_query_region_constraints( + self.tcx(), + region_obligations + .iter() + .map(|r_o| (r_o.sup_type, r_o.sub_region, r_o.origin.to_constraint_category())), + region_constraints, + ) + }); + let opaque_types = self.infcx.clone_opaque_types_for_query_response(); + Ok(self + .tcx() + .mk_external_constraints(ExternalConstraintsData { region_constraints, opaque_types })) + } + + /// After calling a canonical query, we apply the constraints returned + /// by the query using this function. + /// + /// This happens in three steps: + /// - we instantiate the bound variables of the query response + /// - we unify the `var_values` of the response with the `original_values` + /// - we apply the `external_constraints` returned by the query + pub(super) fn instantiate_and_apply_query_response( + &mut self, + param_env: ty::ParamEnv<'tcx>, + original_values: Vec<ty::GenericArg<'tcx>>, + response: CanonicalResponse<'tcx>, + ) -> Result<Certainty, NoSolution> { + let substitution = self.compute_query_response_substitution(&original_values, &response); + + let Response { var_values, external_constraints, certainty } = + response.substitute(self.tcx(), &substitution); + + self.unify_query_var_values(param_env, &original_values, var_values)?; + + // FIXME: implement external constraints. + let ExternalConstraintsData { region_constraints, opaque_types: _ } = + external_constraints.deref(); + self.register_region_constraints(region_constraints); + + Ok(certainty) + } + + /// This returns the substitutions to instantiate the bound variables of + /// the canonical reponse. This depends on the `original_values` for the + /// bound variables. + fn compute_query_response_substitution( + &self, + original_values: &[ty::GenericArg<'tcx>], + response: &CanonicalResponse<'tcx>, + ) -> CanonicalVarValues<'tcx> { + // FIXME: Longterm canonical queries should deal with all placeholders + // created inside of the query directly instead of returning them to the + // caller. + let prev_universe = self.infcx.universe(); + let universes_created_in_query = response.max_universe.index() + 1; + for _ in 0..universes_created_in_query { + self.infcx.create_next_universe(); + } + + let var_values = response.value.var_values; + assert_eq!(original_values.len(), var_values.len()); + + // If the query did not make progress with constraining inference variables, + // we would normally create a new inference variables for bound existential variables + // only then unify this new inference variable with the inference variable from + // the input. + // + // We therefore instantiate the existential variable in the canonical response with the + // inference variable of the input right away, which is more performant. + let mut opt_values = vec![None; response.variables.len()]; + for (original_value, result_value) in iter::zip(original_values, var_values.var_values) { + match result_value.unpack() { + GenericArgKind::Type(t) => { + if let &ty::Bound(debruijn, b) = t.kind() { + assert_eq!(debruijn, ty::INNERMOST); + opt_values[b.var.index()] = Some(*original_value); + } + } + GenericArgKind::Lifetime(r) => { + if let ty::ReLateBound(debruijn, br) = *r { + assert_eq!(debruijn, ty::INNERMOST); + opt_values[br.var.index()] = Some(*original_value); + } + } + GenericArgKind::Const(c) => { + if let ty::ConstKind::Bound(debrujin, b) = c.kind() { + assert_eq!(debrujin, ty::INNERMOST); + opt_values[b.index()] = Some(*original_value); + } + } + } + } + + let var_values = self.tcx().mk_substs_from_iter(response.variables.iter().enumerate().map( + |(index, info)| { + if info.universe() != ty::UniverseIndex::ROOT { + // A variable from inside a binder of the query. While ideally these shouldn't + // exist at all (see the FIXME at the start of this method), we have to deal with + // them for now. + self.infcx.instantiate_canonical_var(DUMMY_SP, info, |idx| { + ty::UniverseIndex::from(prev_universe.index() + idx.index()) + }) + } else if info.is_existential() { + // As an optimization we sometimes avoid creating a new inference variable here. + // + // All new inference variables we create start out in the current universe of the caller. + // This is conceptionally wrong as these inference variables would be able to name + // more placeholders then they should be able to. However the inference variables have + // to "come from somewhere", so by equating them with the original values of the caller + // later on, we pull them down into their correct universe again. + if let Some(v) = opt_values[index] { + v + } else { + self.infcx.instantiate_canonical_var(DUMMY_SP, info, |_| prev_universe) + } + } else { + // For placeholders which were already part of the input, we simply map this + // universal bound variable back the placeholder of the input. + original_values[info.expect_anon_placeholder() as usize] + } + }, + )); + + CanonicalVarValues { var_values } + } + + #[instrument(level = "debug", skip(self, param_env), ret)] + fn unify_query_var_values( + &self, + param_env: ty::ParamEnv<'tcx>, + original_values: &[ty::GenericArg<'tcx>], + var_values: CanonicalVarValues<'tcx>, + ) -> Result<(), NoSolution> { + assert_eq!(original_values.len(), var_values.len()); + for (&orig, response) in iter::zip(original_values, var_values.var_values) { + // This can fail due to the occurs check, see + // `tests/ui/typeck/lazy-norm/equating-projection-cyclically.rs` for an example + // where that can happen. + // + // FIXME: To deal with #105787 I also expect us to emit nested obligations here at + // some point. We can figure out how to deal with this once we actually have + // an ICE. + let nested_goals = self.eq(param_env, orig, response)?; + assert!(nested_goals.is_empty(), "{nested_goals:?}"); + } + + Ok(()) + } + + fn register_region_constraints(&mut self, region_constraints: &QueryRegionConstraints<'tcx>) { + for &(ty::OutlivesPredicate(lhs, rhs), _) in ®ion_constraints.outlives { + match lhs.unpack() { + GenericArgKind::Lifetime(lhs) => self.infcx.region_outlives_predicate( + &ObligationCause::dummy(), + ty::Binder::dummy(ty::OutlivesPredicate(lhs, rhs)), + ), + GenericArgKind::Type(lhs) => self.infcx.register_region_obligation_with_cause( + lhs, + rhs, + &ObligationCause::dummy(), + ), + GenericArgKind::Const(_) => bug!("const outlives: {lhs:?}: {rhs:?}"), + } + } + + for member_constraint in ®ion_constraints.member_constraints { + // FIXME: Deal with member constraints :< + let _ = member_constraint; + } + } +} diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs index c8097e81953..95612674eb9 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs @@ -19,8 +19,17 @@ use super::Goal; pub struct EvalCtxt<'a, 'tcx> { // FIXME: should be private. pub(super) infcx: &'a InferCtxt<'tcx>, - pub(super) var_values: CanonicalVarValues<'tcx>, + /// The highest universe index nameable by the caller. + /// + /// When we enter a new binder inside of the query we create new universes + /// which the caller cannot name. We have to be careful with variables from + /// these new universes when creating the query response. + /// + /// Both because these new universes can prevent us from reaching a fixpoint + /// if we have a coinductive cycle and because that's the only way we can return + /// new placeholders to the caller. + pub(super) max_input_universe: ty::UniverseIndex, pub(super) search_graph: &'a mut SearchGraph<'tcx>, diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index 71f536dd3cb..57b6a452737 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -19,11 +19,9 @@ use std::mem; use rustc_hir::def_id::DefId; use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues}; -use rustc_infer::infer::canonical::{OriginalQueryValues, QueryRegionConstraints, QueryResponse}; use rustc_infer::infer::{InferCtxt, InferOk, TyCtxtInferExt}; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::Obligation; -use rustc_middle::infer::canonical::Certainty as OldCertainty; use rustc_middle::traits::solve::{ExternalConstraints, ExternalConstraintsData}; use rustc_middle::ty::{self, Ty, TyCtxt}; use rustc_middle::ty::{ @@ -35,6 +33,7 @@ use crate::solve::search_graph::OverflowHandler; use crate::traits::ObligationCause; mod assembly; +mod canonical; mod eval_ctxt; mod fulfill; mod project_goals; @@ -89,11 +88,8 @@ trait CanonicalResponseExt { impl<'tcx> CanonicalResponseExt for Canonical<'tcx, Response<'tcx>> { fn has_no_inference_or_external_constraints(&self) -> bool { - // so that we get a compile error when regions are supported - // so this code can be checked for being correct - let _: () = self.value.external_constraints.regions; - - self.value.var_values.is_identity() + self.value.external_constraints.region_constraints.is_empty() + && self.value.var_values.is_identity() && self.value.external_constraints.opaque_types.is_empty() } } @@ -169,6 +165,8 @@ impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { let result = EvalCtxt { search_graph: &mut search_graph, infcx: self, + // Only relevant when canonicalizing the response. + max_input_universe: ty::UniverseIndex::ROOT, var_values: CanonicalVarValues::dummy(), in_projection_eq_hack: false, } @@ -201,36 +199,33 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { search_graph.with_new_goal(tcx, canonical_goal, |search_graph| { let (ref infcx, goal, var_values) = tcx.infer_ctxt().build_with_canonical(DUMMY_SP, &canonical_goal); - let mut ecx = - EvalCtxt { infcx, var_values, search_graph, in_projection_eq_hack: false }; + let mut ecx = EvalCtxt { + infcx, + var_values, + max_input_universe: canonical_goal.max_universe, + search_graph, + in_projection_eq_hack: false, + }; ecx.compute_goal(goal) }) } - fn make_canonical_response(&self, certainty: Certainty) -> QueryResult<'tcx> { - let external_constraints = compute_external_query_constraints(self.infcx)?; - - Ok(self.infcx.canonicalize_response(Response { - var_values: self.var_values, - external_constraints, - certainty, - })) - } - /// Recursively evaluates `goal`, returning whether any inference vars have /// been constrained and the certainty of the result. fn evaluate_goal( &mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>, ) -> Result<(bool, Certainty), NoSolution> { - let mut orig_values = OriginalQueryValues::default(); - let canonical_goal = self.infcx.canonicalize_query(goal, &mut orig_values); + let (orig_values, canonical_goal) = self.canonicalize_goal(goal); let canonical_response = EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?; let has_changed = !canonical_response.value.var_values.is_identity(); - let certainty = - instantiate_canonical_query_response(self.infcx, &orig_values, canonical_response); + let certainty = self.instantiate_and_apply_query_response( + goal.param_env, + orig_values, + canonical_response, + )?; // Check that rerunning this query with its inference constraints applied // doesn't result in new inference constraints and has the same result. @@ -244,8 +239,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { && !self.in_projection_eq_hack && !self.search_graph.in_cycle() { - let mut orig_values = OriginalQueryValues::default(); - let canonical_goal = self.infcx.canonicalize_query(goal, &mut orig_values); + let (_orig_values, canonical_goal) = self.canonicalize_goal(goal); let canonical_response = EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?; if !canonical_response.value.var_values.is_identity() { @@ -316,15 +310,21 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { fn compute_type_outlives_goal( &mut self, - _goal: Goal<'tcx, TypeOutlivesPredicate<'tcx>>, + goal: Goal<'tcx, TypeOutlivesPredicate<'tcx>>, ) -> QueryResult<'tcx> { + let ty::OutlivesPredicate(ty, lt) = goal.predicate; + self.infcx.register_region_obligation_with_cause(ty, lt, &ObligationCause::dummy()); self.make_canonical_response(Certainty::Yes) } fn compute_region_outlives_goal( &mut self, - _goal: Goal<'tcx, RegionOutlivesPredicate<'tcx>>, + goal: Goal<'tcx, RegionOutlivesPredicate<'tcx>>, ) -> QueryResult<'tcx> { + self.infcx.region_outlives_predicate( + &ObligationCause::dummy(), + ty::Binder::dummy(goal.predicate), + ); self.make_canonical_response(Certainty::Yes) } @@ -561,49 +561,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } -#[instrument(level = "debug", skip(infcx), ret)] -fn compute_external_query_constraints<'tcx>( - infcx: &InferCtxt<'tcx>, -) -> Result<ExternalConstraints<'tcx>, NoSolution> { - let region_obligations = infcx.take_registered_region_obligations(); - let opaque_types = infcx.take_opaque_types_for_query_response(); - Ok(infcx.tcx.mk_external_constraints(ExternalConstraintsData { - // FIXME: Now that's definitely wrong :) - // - // Should also do the leak check here I think - regions: drop(region_obligations), - opaque_types, - })) -} - -fn instantiate_canonical_query_response<'tcx>( - infcx: &InferCtxt<'tcx>, - original_values: &OriginalQueryValues<'tcx>, - response: CanonicalResponse<'tcx>, -) -> Certainty { - let Ok(InferOk { value, obligations }) = infcx - .instantiate_query_response_and_region_obligations( - &ObligationCause::dummy(), - ty::ParamEnv::empty(), - original_values, - &response.unchecked_map(|resp| QueryResponse { - var_values: resp.var_values, - region_constraints: QueryRegionConstraints::default(), - certainty: match resp.certainty { - Certainty::Yes => OldCertainty::Proven, - Certainty::Maybe(_) => OldCertainty::Ambiguous, - }, - // FIXME: This to_owned makes me sad, but we should eventually impl - // `instantiate_query_response_and_region_obligations` separately - // instead of piggybacking off of the old implementation. - opaque_types: resp.external_constraints.opaque_types.to_owned(), - value: resp.certainty, - }), - ) else { bug!(); }; - assert!(obligations.is_empty()); - value -} - pub(super) fn response_no_constraints<'tcx>( tcx: TyCtxt<'tcx>, goal: Canonical<'tcx, impl Sized>, diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs index 88fd8bb8bd0..33c66d072e9 100644 --- a/compiler/rustc_trait_selection/src/solve/project_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs @@ -77,10 +77,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let nested_goals = self .eq(goal.param_env, goal.predicate.term, normalized_alias.into()) .expect("failed to unify with unconstrained term"); - let rhs_certainty = + + let unify_certainty = self.evaluate_all(nested_goals).expect("failed to unify with unconstrained term"); - self.make_canonical_response(normalization_certainty.unify_and(rhs_certainty)) + self.make_canonical_response(normalization_certainty.unify_and(unify_certainty)) } } |