From a08e6499e6a215021684681448ed0f3ce60c827a Mon Sep 17 00:00:00 2001 From: lcnr Date: Tue, 16 Sep 2025 15:18:42 +0200 Subject: move `mod canonical` out of `eval_ctxt` --- .../src/canonical/canonicalizer.rs | 573 +++++++++++++++++++++ .../rustc_next_trait_solver/src/canonical/mod.rs | 341 ++++++++++++ .../rustc_next_trait_solver/src/canonicalizer.rs | 573 --------------------- compiler/rustc_next_trait_solver/src/lib.rs | 2 +- .../src/solve/eval_ctxt/canonical.rs | 517 ------------------- .../src/solve/eval_ctxt/mod.rs | 202 +++++++- .../src/solve/inspect/build.rs | 2 +- .../src/solve/inspect/mod.rs | 2 - compiler/rustc_next_trait_solver/src/solve/mod.rs | 19 - .../src/solve/search_graph.rs | 3 +- .../src/solve/inspect/analyse.rs | 4 +- 11 files changed, 1118 insertions(+), 1120 deletions(-) create mode 100644 compiler/rustc_next_trait_solver/src/canonical/canonicalizer.rs create mode 100644 compiler/rustc_next_trait_solver/src/canonical/mod.rs delete mode 100644 compiler/rustc_next_trait_solver/src/canonicalizer.rs delete mode 100644 compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs diff --git a/compiler/rustc_next_trait_solver/src/canonical/canonicalizer.rs b/compiler/rustc_next_trait_solver/src/canonical/canonicalizer.rs new file mode 100644 index 00000000000..4b4ec4956eb --- /dev/null +++ b/compiler/rustc_next_trait_solver/src/canonical/canonicalizer.rs @@ -0,0 +1,573 @@ +use rustc_type_ir::data_structures::{HashMap, ensure_sufficient_stack}; +use rustc_type_ir::inherent::*; +use rustc_type_ir::solve::{Goal, QueryInput}; +use rustc_type_ir::{ + self as ty, Canonical, CanonicalParamEnvCacheEntry, CanonicalVarKind, Flags, InferCtxtLike, + Interner, TypeFlags, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt, +}; + +use crate::delegate::SolverDelegate; + +/// Does this have infer/placeholder/param, free regions or ReErased? +const NEEDS_CANONICAL: TypeFlags = TypeFlags::from_bits( + TypeFlags::HAS_INFER.bits() + | TypeFlags::HAS_PLACEHOLDER.bits() + | TypeFlags::HAS_PARAM.bits() + | TypeFlags::HAS_FREE_REGIONS.bits() + | TypeFlags::HAS_RE_ERASED.bits(), +) +.unwrap(); + +#[derive(Debug, Clone, Copy)] +enum CanonicalizeInputKind { + /// When canonicalizing the `param_env`, we keep `'static` as merging + /// trait candidates relies on it when deciding whether a where-bound + /// is trivial. + ParamEnv, + /// When canonicalizing predicates, we don't keep `'static`. + Predicate, +} + +/// Whether we're canonicalizing a query input or the query response. +/// +/// 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)] +enum CanonicalizeMode { + Input(CanonicalizeInputKind), + /// FIXME: We currently return region constraints referring 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, D: SolverDelegate, I: Interner> { + delegate: &'a D, + + // Immutable field. + canonicalize_mode: CanonicalizeMode, + + // Mutable fields. + variables: &'a mut Vec, + var_kinds: Vec>, + variable_lookup_table: HashMap, + /// Maps each `sub_unification_table_root_var` to the index of the first + /// variable which used it. + /// + /// This means in case two type variables have the same sub relations root, + /// we set the `sub_root` of the second variable to the position of the first. + /// Otherwise the `sub_root` of each type variable is just its own position. + sub_root_lookup_table: HashMap, + binder_index: ty::DebruijnIndex, + + /// We only use the debruijn index during lookup. We don't need to + /// track the `variables` as each generic arg only results in a single + /// bound variable regardless of how many times it is encountered. + cache: HashMap<(ty::DebruijnIndex, I::Ty), I::Ty>, +} + +impl<'a, D: SolverDelegate, I: Interner> Canonicalizer<'a, D, I> { + pub fn canonicalize_response>( + delegate: &'a D, + max_input_universe: ty::UniverseIndex, + variables: &'a mut Vec, + value: T, + ) -> ty::Canonical { + let mut canonicalizer = Canonicalizer { + delegate, + canonicalize_mode: CanonicalizeMode::Response { max_input_universe }, + + variables, + variable_lookup_table: Default::default(), + sub_root_lookup_table: Default::default(), + var_kinds: Vec::new(), + binder_index: ty::INNERMOST, + + cache: Default::default(), + }; + + let value = if value.has_type_flags(NEEDS_CANONICAL) { + value.fold_with(&mut canonicalizer) + } else { + value + }; + debug_assert!(!value.has_infer(), "unexpected infer in {value:?}"); + debug_assert!(!value.has_placeholders(), "unexpected placeholders in {value:?}"); + let (max_universe, variables) = canonicalizer.finalize(); + Canonical { max_universe, variables, value } + } + + fn canonicalize_param_env( + delegate: &'a D, + variables: &'a mut Vec, + param_env: I::ParamEnv, + ) -> (I::ParamEnv, HashMap, Vec>) { + if !param_env.has_type_flags(NEEDS_CANONICAL) { + return (param_env, Default::default(), Vec::new()); + } + + // Check whether we can use the global cache for this param_env. As we only use + // the `param_env` itself as the cache key, considering any additional information + // durnig its canonicalization would be incorrect. We always canonicalize region + // inference variables in a separate universe, so these are fine. However, we do + // track the universe of type and const inference variables so these must not be + // globally cached. We don't rely on any additional information when canonicalizing + // placeholders. + if !param_env.has_non_region_infer() { + delegate.cx().canonical_param_env_cache_get_or_insert( + param_env, + || { + let mut variables = Vec::new(); + let mut env_canonicalizer = Canonicalizer { + delegate, + canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv), + + variables: &mut variables, + variable_lookup_table: Default::default(), + sub_root_lookup_table: Default::default(), + var_kinds: Vec::new(), + binder_index: ty::INNERMOST, + + cache: Default::default(), + }; + let param_env = param_env.fold_with(&mut env_canonicalizer); + debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST); + debug_assert!(env_canonicalizer.sub_root_lookup_table.is_empty()); + CanonicalParamEnvCacheEntry { + param_env, + variable_lookup_table: env_canonicalizer.variable_lookup_table, + var_kinds: env_canonicalizer.var_kinds, + variables, + } + }, + |&CanonicalParamEnvCacheEntry { + param_env, + variables: ref cache_variables, + ref variable_lookup_table, + ref var_kinds, + }| { + debug_assert!(variables.is_empty()); + variables.extend(cache_variables.iter().copied()); + (param_env, variable_lookup_table.clone(), var_kinds.clone()) + }, + ) + } else { + let mut env_canonicalizer = Canonicalizer { + delegate, + canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv), + + variables, + variable_lookup_table: Default::default(), + sub_root_lookup_table: Default::default(), + var_kinds: Vec::new(), + binder_index: ty::INNERMOST, + + cache: Default::default(), + }; + let param_env = param_env.fold_with(&mut env_canonicalizer); + debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST); + debug_assert!(env_canonicalizer.sub_root_lookup_table.is_empty()); + (param_env, env_canonicalizer.variable_lookup_table, env_canonicalizer.var_kinds) + } + } + + /// When canonicalizing query inputs, we keep `'static` in the `param_env` + /// but erase it everywhere else. We generally don't want to depend on region + /// identity, so while it should not matter whether `'static` is kept in the + /// value or opaque type storage as well, this prevents us from accidentally + /// relying on it in the future. + /// + /// We want to keep the option of canonicalizing `'static` to an existential + /// variable in the future by changing the way we detect global where-bounds. + pub fn canonicalize_input>( + delegate: &'a D, + variables: &'a mut Vec, + input: QueryInput, + ) -> ty::Canonical> { + // First canonicalize the `param_env` while keeping `'static` + let (param_env, variable_lookup_table, var_kinds) = + Canonicalizer::canonicalize_param_env(delegate, variables, input.goal.param_env); + // Then canonicalize the rest of the input without keeping `'static` + // while *mostly* reusing the canonicalizer from above. + let mut rest_canonicalizer = Canonicalizer { + delegate, + canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::Predicate), + + variables, + variable_lookup_table, + sub_root_lookup_table: Default::default(), + var_kinds, + binder_index: ty::INNERMOST, + + // We do not reuse the cache as it may contain entries whose canonicalized + // value contains `'static`. While we could alternatively handle this by + // checking for `'static` when using cached entries, this does not + // feel worth the effort. I do not expect that a `ParamEnv` will ever + // contain large enough types for caching to be necessary. + cache: Default::default(), + }; + + let predicate = input.goal.predicate; + let predicate = if predicate.has_type_flags(NEEDS_CANONICAL) { + predicate.fold_with(&mut rest_canonicalizer) + } else { + predicate + }; + let goal = Goal { param_env, predicate }; + + let predefined_opaques_in_body = input.predefined_opaques_in_body; + let predefined_opaques_in_body = + if input.predefined_opaques_in_body.has_type_flags(NEEDS_CANONICAL) { + predefined_opaques_in_body.fold_with(&mut rest_canonicalizer) + } else { + predefined_opaques_in_body + }; + + let value = QueryInput { goal, predefined_opaques_in_body }; + + debug_assert!(!value.has_infer(), "unexpected infer in {value:?}"); + debug_assert!(!value.has_placeholders(), "unexpected placeholders in {value:?}"); + let (max_universe, variables) = rest_canonicalizer.finalize(); + Canonical { max_universe, variables, value } + } + + fn get_or_insert_bound_var( + &mut self, + arg: impl Into, + kind: CanonicalVarKind, + ) -> ty::BoundVar { + // FIXME: 16 is made up and arbitrary. We should look at some + // perf data here. + let arg = arg.into(); + let idx = if self.variables.len() > 16 { + if self.variable_lookup_table.is_empty() { + self.variable_lookup_table.extend(self.variables.iter().copied().zip(0..)); + } + + *self.variable_lookup_table.entry(arg).or_insert_with(|| { + let var = self.variables.len(); + self.variables.push(arg); + self.var_kinds.push(kind); + var + }) + } else { + self.variables.iter().position(|&v| v == arg).unwrap_or_else(|| { + let var = self.variables.len(); + self.variables.push(arg); + self.var_kinds.push(kind); + var + }) + }; + + ty::BoundVar::from(idx) + } + + fn get_or_insert_sub_root(&mut self, vid: ty::TyVid) -> ty::BoundVar { + let root_vid = self.delegate.sub_unification_table_root_var(vid); + let idx = + *self.sub_root_lookup_table.entry(root_vid).or_insert_with(|| self.variables.len()); + ty::BoundVar::from(idx) + } + + fn finalize(self) -> (ty::UniverseIndex, I::CanonicalVarKinds) { + let mut var_kinds = self.var_kinds; + // See the rustc-dev-guide section about how we deal with universes + // during canonicalization in the new solver. + match self.canonicalize_mode { + // All placeholders and vars are canonicalized in the root universe. + CanonicalizeMode::Input { .. } => { + debug_assert!( + var_kinds.iter().all(|var| var.universe() == ty::UniverseIndex::ROOT), + "expected all vars to be canonicalized in root universe: {var_kinds:#?}" + ); + let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds); + (ty::UniverseIndex::ROOT, var_kinds) + } + // 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_kinds.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_kinds + .iter() + .map(|kind| kind.universe()) + .max() + .unwrap_or(ty::UniverseIndex::ROOT); + let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds); + (max_universe, var_kinds) + } + } + } + + fn inner_fold_ty(&mut self, t: I::Ty) -> I::Ty { + let kind = match t.kind() { + ty::Infer(i) => match i { + ty::TyVar(vid) => { + debug_assert_eq!( + self.delegate.opportunistic_resolve_ty_var(vid), + t, + "ty vid should have been resolved fully before canonicalization" + ); + + let sub_root = self.get_or_insert_sub_root(vid); + let ui = match self.canonicalize_mode { + CanonicalizeMode::Input { .. } => ty::UniverseIndex::ROOT, + CanonicalizeMode::Response { .. } => self + .delegate + .universe_of_ty(vid) + .unwrap_or_else(|| panic!("ty var should have been resolved: {t:?}")), + }; + CanonicalVarKind::Ty { ui, sub_root } + } + ty::IntVar(vid) => { + debug_assert_eq!( + self.delegate.opportunistic_resolve_int_var(vid), + t, + "ty vid should have been resolved fully before canonicalization" + ); + CanonicalVarKind::Int + } + ty::FloatVar(vid) => { + debug_assert_eq!( + self.delegate.opportunistic_resolve_float_var(vid), + t, + "ty vid should have been resolved fully before canonicalization" + ); + CanonicalVarKind::Float + } + ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => { + panic!("fresh vars not expected in canonicalization") + } + }, + ty::Placeholder(placeholder) => match self.canonicalize_mode { + CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy( + PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()), + ), + CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder), + }, + ty::Param(_) => match self.canonicalize_mode { + CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy( + PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()), + ), + CanonicalizeMode::Response { .. } => panic!("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::Pat(_, _) + | ty::FnDef(_, _) + | ty::FnPtr(..) + | ty::UnsafeBinder(_) + | ty::Dynamic(_, _) + | ty::Closure(..) + | ty::CoroutineClosure(..) + | ty::Coroutine(_, _) + | ty::CoroutineWitness(..) + | ty::Never + | ty::Tuple(_) + | ty::Alias(_, _) + | ty::Bound(_, _) + | ty::Error(_) => { + return if t.has_type_flags(NEEDS_CANONICAL) { + ensure_sufficient_stack(|| t.super_fold_with(self)) + } else { + t + }; + } + }; + + let var = self.get_or_insert_bound_var(t, kind); + + Ty::new_anon_bound(self.cx(), self.binder_index, var) + } +} + +impl, I: Interner> TypeFolder for Canonicalizer<'_, D, I> { + fn cx(&self) -> I { + self.delegate.cx() + } + + fn fold_binder(&mut self, t: ty::Binder) -> ty::Binder + where + T: TypeFoldable, + { + 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: I::Region) -> I::Region { + let kind = match r.kind() { + ty::ReBound(..) => return r, + + // We don't canonicalize `ReStatic` in the `param_env` as we use it + // when checking whether a `ParamEnv` candidate is global. + ty::ReStatic => match self.canonicalize_mode { + CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { .. }) => { + CanonicalVarKind::Region(ty::UniverseIndex::ROOT) + } + CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv) + | CanonicalizeMode::Response { .. } => return r, + }, + + // `ReErased` should only be encountered in the hidden + // type of an opaque for regions that are ignored for the purposes of + // captures. + // + // FIXME: We should investigate the perf implications of not uniquifying + // `ReErased`. We may be able to short-circuit registering region + // obligations if we encounter a `ReErased` on one side, for example. + ty::ReErased | ty::ReError(_) => match self.canonicalize_mode { + CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Response { .. } => return r, + }, + + ty::ReEarlyParam(_) | ty::ReLateParam(_) => match self.canonicalize_mode { + CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Response { .. } => { + panic!("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()) { + panic!("new placeholder in universe {max_input_universe:?}: {r:?}"); + } + CanonicalVarKind::PlaceholderRegion(placeholder) + } + }, + + ty::ReVar(vid) => { + debug_assert_eq!( + self.delegate.opportunistic_resolve_lt_var(vid), + r, + "region vid should have been resolved fully before canonicalization" + ); + match self.canonicalize_mode { + CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Response { .. } => { + CanonicalVarKind::Region(self.delegate.universe_of_lt(vid).unwrap()) + } + } + } + }; + + let var = self.get_or_insert_bound_var(r, kind); + + Region::new_anon_bound(self.cx(), self.binder_index, var) + } + + fn fold_ty(&mut self, t: I::Ty) -> I::Ty { + if let Some(&ty) = self.cache.get(&(self.binder_index, t)) { + ty + } else { + let res = self.inner_fold_ty(t); + let old = self.cache.insert((self.binder_index, t), res); + assert_eq!(old, None); + res + } + } + + fn fold_const(&mut self, c: I::Const) -> I::Const { + let kind = match c.kind() { + ty::ConstKind::Infer(i) => match i { + ty::InferConst::Var(vid) => { + debug_assert_eq!( + self.delegate.opportunistic_resolve_ct_var(vid), + c, + "const vid should have been resolved fully before canonicalization" + ); + + match self.canonicalize_mode { + CanonicalizeMode::Input { .. } => { + CanonicalVarKind::Const(ty::UniverseIndex::ROOT) + } + CanonicalizeMode::Response { .. } => { + CanonicalVarKind::Const(self.delegate.universe_of_ct(vid).unwrap()) + } + } + } + ty::InferConst::Fresh(_) => todo!(), + }, + ty::ConstKind::Placeholder(placeholder) => match self.canonicalize_mode { + CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst( + PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()), + ), + CanonicalizeMode::Response { .. } => { + CanonicalVarKind::PlaceholderConst(placeholder) + } + }, + ty::ConstKind::Param(_) => match self.canonicalize_mode { + CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst( + PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()), + ), + CanonicalizeMode::Response { .. } => panic!("param ty in response: {c:?}"), + }, + // FIXME: See comment above -- we could fold the region separately or something. + ty::ConstKind::Bound(_, _) + | ty::ConstKind::Unevaluated(_) + | ty::ConstKind::Value(_) + | ty::ConstKind::Error(_) + | ty::ConstKind::Expr(_) => { + return if c.has_type_flags(NEEDS_CANONICAL) { c.super_fold_with(self) } else { c }; + } + }; + + let var = self.get_or_insert_bound_var(c, kind); + + Const::new_anon_bound(self.cx(), self.binder_index, var) + } + + fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate { + if p.flags().intersects(NEEDS_CANONICAL) { p.super_fold_with(self) } else { p } + } + + fn fold_clauses(&mut self, c: I::Clauses) -> I::Clauses { + match self.canonicalize_mode { + CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv) + | CanonicalizeMode::Response { max_input_universe: _ } => {} + CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { .. }) => { + panic!("erasing 'static in env") + } + } + if c.flags().intersects(NEEDS_CANONICAL) { c.super_fold_with(self) } else { c } + } +} diff --git a/compiler/rustc_next_trait_solver/src/canonical/mod.rs b/compiler/rustc_next_trait_solver/src/canonical/mod.rs new file mode 100644 index 00000000000..35881acf0c7 --- /dev/null +++ b/compiler/rustc_next_trait_solver/src/canonical/mod.rs @@ -0,0 +1,341 @@ +//! 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 std::iter; + +use canonicalizer::Canonicalizer; +use rustc_index::IndexVec; +use rustc_type_ir::inherent::*; +use rustc_type_ir::relate::solver_relating::RelateExt; +use rustc_type_ir::{ + self as ty, Canonical, CanonicalVarKind, CanonicalVarValues, InferCtxtLike, Interner, + TypeFoldable, +}; +use tracing::instrument; + +use crate::delegate::SolverDelegate; +use crate::resolve::eager_resolve_vars; +use crate::solve::{ + CanonicalInput, CanonicalResponse, Certainty, EvalCtxt, ExternalConstraintsData, Goal, + NestedNormalizationGoals, PredefinedOpaquesData, QueryInput, Response, inspect, +}; + +pub mod canonicalizer; + +trait ResponseT { + fn var_values(&self) -> CanonicalVarValues; +} + +impl ResponseT for Response { + fn var_values(&self) -> CanonicalVarValues { + self.var_values + } +} + +impl ResponseT for inspect::State { + fn var_values(&self) -> CanonicalVarValues { + self.var_values + } +} + +impl EvalCtxt<'_, D> +where + D: SolverDelegate, + I: Interner, +{ + /// Canonicalizes the goal remembering the original values + /// for each bound variable. + /// + /// This expects `goal` and `opaque_types` to be eager resolved. + pub(super) fn canonicalize_goal( + delegate: &D, + goal: Goal, + opaque_types: Vec<(ty::OpaqueTypeKey, I::Ty)>, + ) -> (Vec, CanonicalInput) { + let mut orig_values = Default::default(); + let canonical = Canonicalizer::canonicalize_input( + delegate, + &mut orig_values, + QueryInput { + goal, + predefined_opaques_in_body: delegate + .cx() + .mk_predefined_opaques_in_body(PredefinedOpaquesData { opaque_types }), + }, + ); + let query_input = + ty::CanonicalQueryInput { canonical, typing_mode: delegate.typing_mode() }; + (orig_values, query_input) + } + + /// 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, returning + /// the `normalization_nested_goals` + pub(super) fn instantiate_and_apply_query_response( + delegate: &D, + param_env: I::ParamEnv, + original_values: &[I::GenericArg], + response: CanonicalResponse, + span: I::Span, + ) -> (NestedNormalizationGoals, Certainty) { + let instantiation = Self::compute_query_response_instantiation_values( + delegate, + &original_values, + &response, + span, + ); + + let Response { var_values, external_constraints, certainty } = + delegate.instantiate_canonical(response, instantiation); + + Self::unify_query_var_values(delegate, param_env, &original_values, var_values, span); + + let ExternalConstraintsData { + region_constraints, + opaque_types, + normalization_nested_goals, + } = &*external_constraints; + + Self::register_region_constraints(delegate, region_constraints, span); + Self::register_new_opaque_types(delegate, opaque_types, span); + + (normalization_nested_goals.clone(), certainty) + } + + /// This returns the canonical variable values to instantiate the bound variables of + /// the canonical response. This depends on the `original_values` for the + /// bound variables. + fn compute_query_response_instantiation_values>( + delegate: &D, + original_values: &[I::GenericArg], + response: &Canonical, + span: I::Span, + ) -> CanonicalVarValues { + // 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 = delegate.universe(); + let universes_created_in_query = response.max_universe.index(); + for _ in 0..universes_created_in_query { + delegate.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 = IndexVec::from_elem_n(None, response.variables.len()); + for (original_value, result_value) in + iter::zip(original_values, var_values.var_values.iter()) + { + match result_value.kind() { + ty::GenericArgKind::Type(t) => { + // We disable the instantiation guess for inference variables + // and only use it for placeholders. We need to handle the + // `sub_root` of type inference variables which would make this + // more involved. They are also a lot rarer than region variables. + if let ty::Bound(debruijn, b) = t.kind() + && !matches!( + response.variables.get(b.var().as_usize()).unwrap(), + CanonicalVarKind::Ty { .. } + ) + { + assert_eq!(debruijn, ty::INNERMOST); + opt_values[b.var()] = Some(*original_value); + } + } + ty::GenericArgKind::Lifetime(r) => { + if let ty::ReBound(debruijn, br) = r.kind() { + assert_eq!(debruijn, ty::INNERMOST); + opt_values[br.var()] = Some(*original_value); + } + } + ty::GenericArgKind::Const(c) => { + if let ty::ConstKind::Bound(debruijn, bv) = c.kind() { + assert_eq!(debruijn, ty::INNERMOST); + opt_values[bv.var()] = Some(*original_value); + } + } + } + } + CanonicalVarValues::instantiate(delegate.cx(), response.variables, |var_values, kind| { + if kind.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. + delegate.instantiate_canonical_var(kind, span, &var_values, |idx| { + prev_universe + idx.index() + }) + } else if kind.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 conceptually 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[ty::BoundVar::from_usize(var_values.len())] { + v + } else { + delegate.instantiate_canonical_var(kind, span, &var_values, |_| 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[kind.expect_placeholder_index()] + } + }) + } + + /// Unify the `original_values` with the `var_values` returned by the canonical query.. + /// + /// This assumes that this unification will always succeed. This is the case when + /// applying a query response right away. However, calling a canonical query, doing any + /// other kind of trait solving, and only then instantiating the result of the query + /// can cause the instantiation to fail. This is not supported and we ICE in this case. + /// + /// We always structurally instantiate aliases. Relating aliases needs to be different + /// depending on whether the alias is *rigid* or not. We're only really able to tell + /// whether an alias is rigid by using the trait solver. When instantiating a response + /// from the solver we assume that the solver correctly handled aliases and therefore + /// always relate them structurally here. + #[instrument(level = "trace", skip(delegate))] + fn unify_query_var_values( + delegate: &D, + param_env: I::ParamEnv, + original_values: &[I::GenericArg], + var_values: CanonicalVarValues, + span: I::Span, + ) { + assert_eq!(original_values.len(), var_values.len()); + + for (&orig, response) in iter::zip(original_values, var_values.var_values.iter()) { + let goals = + delegate.eq_structurally_relating_aliases(param_env, orig, response, span).unwrap(); + assert!(goals.is_empty()); + } + } + + fn register_region_constraints( + delegate: &D, + outlives: &[ty::OutlivesPredicate], + span: I::Span, + ) { + for &ty::OutlivesPredicate(lhs, rhs) in outlives { + match lhs.kind() { + ty::GenericArgKind::Lifetime(lhs) => delegate.sub_regions(rhs, lhs, span), + ty::GenericArgKind::Type(lhs) => delegate.register_ty_outlives(lhs, rhs, span), + ty::GenericArgKind::Const(_) => panic!("const outlives: {lhs:?}: {rhs:?}"), + } + } + } + + fn register_new_opaque_types( + delegate: &D, + opaque_types: &[(ty::OpaqueTypeKey, I::Ty)], + span: I::Span, + ) { + for &(key, ty) in opaque_types { + let prev = delegate.register_hidden_type_in_storage(key, ty, span); + // We eagerly resolve inference variables when computing the query response. + // This can cause previously distinct opaque type keys to now be structurally equal. + // + // To handle this, we store any duplicate entries in a separate list to check them + // at the end of typeck/borrowck. We could alternatively eagerly equate the hidden + // types here. However, doing so is difficult as it may result in nested goals and + // any errors may make it harder to track the control flow for diagnostics. + if let Some(prev) = prev { + delegate.add_duplicate_opaque_type(key, prev, span); + } + } + } +} + +/// Used by proof trees to be able to recompute intermediate actions while +/// evaluating a goal. The `var_values` not only include the bound variables +/// of the query input, but also contain all unconstrained inference vars +/// created while evaluating this goal. +pub fn make_canonical_state( + delegate: &D, + var_values: &[I::GenericArg], + max_input_universe: ty::UniverseIndex, + data: T, +) -> inspect::CanonicalState +where + D: SolverDelegate, + I: Interner, + T: TypeFoldable, +{ + let var_values = CanonicalVarValues { var_values: delegate.cx().mk_args(var_values) }; + let state = inspect::State { var_values, data }; + let state = eager_resolve_vars(delegate, state); + Canonicalizer::canonicalize_response(delegate, max_input_universe, &mut vec![], state) +} + +// FIXME: needs to be pub to be accessed by downstream +// `rustc_trait_selection::solve::inspect::analyse`. +pub fn instantiate_canonical_state>( + delegate: &D, + span: I::Span, + param_env: I::ParamEnv, + orig_values: &mut Vec, + state: inspect::CanonicalState, +) -> T +where + D: SolverDelegate, + I: Interner, +{ + // In case any fresh inference variables have been created between `state` + // and the previous instantiation, extend `orig_values` for it. + orig_values.extend( + state.value.var_values.var_values.as_slice()[orig_values.len()..] + .iter() + .map(|&arg| delegate.fresh_var_for_kind_with_span(arg, span)), + ); + + let instantiation = + EvalCtxt::compute_query_response_instantiation_values(delegate, orig_values, &state, span); + + let inspect::State { var_values, data } = delegate.instantiate_canonical(state, instantiation); + + EvalCtxt::unify_query_var_values(delegate, param_env, orig_values, var_values, span); + data +} + +pub fn response_no_constraints_raw( + cx: I, + max_universe: ty::UniverseIndex, + variables: I::CanonicalVarKinds, + certainty: Certainty, +) -> CanonicalResponse { + ty::Canonical { + max_universe, + variables, + value: Response { + var_values: ty::CanonicalVarValues::make_identity(cx, variables), + // FIXME: maybe we should store the "no response" version in cx, like + // we do for cx.types and stuff. + external_constraints: cx.mk_external_constraints(ExternalConstraintsData::default()), + certainty, + }, + } +} diff --git a/compiler/rustc_next_trait_solver/src/canonicalizer.rs b/compiler/rustc_next_trait_solver/src/canonicalizer.rs deleted file mode 100644 index 4b4ec4956eb..00000000000 --- a/compiler/rustc_next_trait_solver/src/canonicalizer.rs +++ /dev/null @@ -1,573 +0,0 @@ -use rustc_type_ir::data_structures::{HashMap, ensure_sufficient_stack}; -use rustc_type_ir::inherent::*; -use rustc_type_ir::solve::{Goal, QueryInput}; -use rustc_type_ir::{ - self as ty, Canonical, CanonicalParamEnvCacheEntry, CanonicalVarKind, Flags, InferCtxtLike, - Interner, TypeFlags, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt, -}; - -use crate::delegate::SolverDelegate; - -/// Does this have infer/placeholder/param, free regions or ReErased? -const NEEDS_CANONICAL: TypeFlags = TypeFlags::from_bits( - TypeFlags::HAS_INFER.bits() - | TypeFlags::HAS_PLACEHOLDER.bits() - | TypeFlags::HAS_PARAM.bits() - | TypeFlags::HAS_FREE_REGIONS.bits() - | TypeFlags::HAS_RE_ERASED.bits(), -) -.unwrap(); - -#[derive(Debug, Clone, Copy)] -enum CanonicalizeInputKind { - /// When canonicalizing the `param_env`, we keep `'static` as merging - /// trait candidates relies on it when deciding whether a where-bound - /// is trivial. - ParamEnv, - /// When canonicalizing predicates, we don't keep `'static`. - Predicate, -} - -/// Whether we're canonicalizing a query input or the query response. -/// -/// 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)] -enum CanonicalizeMode { - Input(CanonicalizeInputKind), - /// FIXME: We currently return region constraints referring 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, D: SolverDelegate, I: Interner> { - delegate: &'a D, - - // Immutable field. - canonicalize_mode: CanonicalizeMode, - - // Mutable fields. - variables: &'a mut Vec, - var_kinds: Vec>, - variable_lookup_table: HashMap, - /// Maps each `sub_unification_table_root_var` to the index of the first - /// variable which used it. - /// - /// This means in case two type variables have the same sub relations root, - /// we set the `sub_root` of the second variable to the position of the first. - /// Otherwise the `sub_root` of each type variable is just its own position. - sub_root_lookup_table: HashMap, - binder_index: ty::DebruijnIndex, - - /// We only use the debruijn index during lookup. We don't need to - /// track the `variables` as each generic arg only results in a single - /// bound variable regardless of how many times it is encountered. - cache: HashMap<(ty::DebruijnIndex, I::Ty), I::Ty>, -} - -impl<'a, D: SolverDelegate, I: Interner> Canonicalizer<'a, D, I> { - pub fn canonicalize_response>( - delegate: &'a D, - max_input_universe: ty::UniverseIndex, - variables: &'a mut Vec, - value: T, - ) -> ty::Canonical { - let mut canonicalizer = Canonicalizer { - delegate, - canonicalize_mode: CanonicalizeMode::Response { max_input_universe }, - - variables, - variable_lookup_table: Default::default(), - sub_root_lookup_table: Default::default(), - var_kinds: Vec::new(), - binder_index: ty::INNERMOST, - - cache: Default::default(), - }; - - let value = if value.has_type_flags(NEEDS_CANONICAL) { - value.fold_with(&mut canonicalizer) - } else { - value - }; - debug_assert!(!value.has_infer(), "unexpected infer in {value:?}"); - debug_assert!(!value.has_placeholders(), "unexpected placeholders in {value:?}"); - let (max_universe, variables) = canonicalizer.finalize(); - Canonical { max_universe, variables, value } - } - - fn canonicalize_param_env( - delegate: &'a D, - variables: &'a mut Vec, - param_env: I::ParamEnv, - ) -> (I::ParamEnv, HashMap, Vec>) { - if !param_env.has_type_flags(NEEDS_CANONICAL) { - return (param_env, Default::default(), Vec::new()); - } - - // Check whether we can use the global cache for this param_env. As we only use - // the `param_env` itself as the cache key, considering any additional information - // durnig its canonicalization would be incorrect. We always canonicalize region - // inference variables in a separate universe, so these are fine. However, we do - // track the universe of type and const inference variables so these must not be - // globally cached. We don't rely on any additional information when canonicalizing - // placeholders. - if !param_env.has_non_region_infer() { - delegate.cx().canonical_param_env_cache_get_or_insert( - param_env, - || { - let mut variables = Vec::new(); - let mut env_canonicalizer = Canonicalizer { - delegate, - canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv), - - variables: &mut variables, - variable_lookup_table: Default::default(), - sub_root_lookup_table: Default::default(), - var_kinds: Vec::new(), - binder_index: ty::INNERMOST, - - cache: Default::default(), - }; - let param_env = param_env.fold_with(&mut env_canonicalizer); - debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST); - debug_assert!(env_canonicalizer.sub_root_lookup_table.is_empty()); - CanonicalParamEnvCacheEntry { - param_env, - variable_lookup_table: env_canonicalizer.variable_lookup_table, - var_kinds: env_canonicalizer.var_kinds, - variables, - } - }, - |&CanonicalParamEnvCacheEntry { - param_env, - variables: ref cache_variables, - ref variable_lookup_table, - ref var_kinds, - }| { - debug_assert!(variables.is_empty()); - variables.extend(cache_variables.iter().copied()); - (param_env, variable_lookup_table.clone(), var_kinds.clone()) - }, - ) - } else { - let mut env_canonicalizer = Canonicalizer { - delegate, - canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv), - - variables, - variable_lookup_table: Default::default(), - sub_root_lookup_table: Default::default(), - var_kinds: Vec::new(), - binder_index: ty::INNERMOST, - - cache: Default::default(), - }; - let param_env = param_env.fold_with(&mut env_canonicalizer); - debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST); - debug_assert!(env_canonicalizer.sub_root_lookup_table.is_empty()); - (param_env, env_canonicalizer.variable_lookup_table, env_canonicalizer.var_kinds) - } - } - - /// When canonicalizing query inputs, we keep `'static` in the `param_env` - /// but erase it everywhere else. We generally don't want to depend on region - /// identity, so while it should not matter whether `'static` is kept in the - /// value or opaque type storage as well, this prevents us from accidentally - /// relying on it in the future. - /// - /// We want to keep the option of canonicalizing `'static` to an existential - /// variable in the future by changing the way we detect global where-bounds. - pub fn canonicalize_input>( - delegate: &'a D, - variables: &'a mut Vec, - input: QueryInput, - ) -> ty::Canonical> { - // First canonicalize the `param_env` while keeping `'static` - let (param_env, variable_lookup_table, var_kinds) = - Canonicalizer::canonicalize_param_env(delegate, variables, input.goal.param_env); - // Then canonicalize the rest of the input without keeping `'static` - // while *mostly* reusing the canonicalizer from above. - let mut rest_canonicalizer = Canonicalizer { - delegate, - canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::Predicate), - - variables, - variable_lookup_table, - sub_root_lookup_table: Default::default(), - var_kinds, - binder_index: ty::INNERMOST, - - // We do not reuse the cache as it may contain entries whose canonicalized - // value contains `'static`. While we could alternatively handle this by - // checking for `'static` when using cached entries, this does not - // feel worth the effort. I do not expect that a `ParamEnv` will ever - // contain large enough types for caching to be necessary. - cache: Default::default(), - }; - - let predicate = input.goal.predicate; - let predicate = if predicate.has_type_flags(NEEDS_CANONICAL) { - predicate.fold_with(&mut rest_canonicalizer) - } else { - predicate - }; - let goal = Goal { param_env, predicate }; - - let predefined_opaques_in_body = input.predefined_opaques_in_body; - let predefined_opaques_in_body = - if input.predefined_opaques_in_body.has_type_flags(NEEDS_CANONICAL) { - predefined_opaques_in_body.fold_with(&mut rest_canonicalizer) - } else { - predefined_opaques_in_body - }; - - let value = QueryInput { goal, predefined_opaques_in_body }; - - debug_assert!(!value.has_infer(), "unexpected infer in {value:?}"); - debug_assert!(!value.has_placeholders(), "unexpected placeholders in {value:?}"); - let (max_universe, variables) = rest_canonicalizer.finalize(); - Canonical { max_universe, variables, value } - } - - fn get_or_insert_bound_var( - &mut self, - arg: impl Into, - kind: CanonicalVarKind, - ) -> ty::BoundVar { - // FIXME: 16 is made up and arbitrary. We should look at some - // perf data here. - let arg = arg.into(); - let idx = if self.variables.len() > 16 { - if self.variable_lookup_table.is_empty() { - self.variable_lookup_table.extend(self.variables.iter().copied().zip(0..)); - } - - *self.variable_lookup_table.entry(arg).or_insert_with(|| { - let var = self.variables.len(); - self.variables.push(arg); - self.var_kinds.push(kind); - var - }) - } else { - self.variables.iter().position(|&v| v == arg).unwrap_or_else(|| { - let var = self.variables.len(); - self.variables.push(arg); - self.var_kinds.push(kind); - var - }) - }; - - ty::BoundVar::from(idx) - } - - fn get_or_insert_sub_root(&mut self, vid: ty::TyVid) -> ty::BoundVar { - let root_vid = self.delegate.sub_unification_table_root_var(vid); - let idx = - *self.sub_root_lookup_table.entry(root_vid).or_insert_with(|| self.variables.len()); - ty::BoundVar::from(idx) - } - - fn finalize(self) -> (ty::UniverseIndex, I::CanonicalVarKinds) { - let mut var_kinds = self.var_kinds; - // See the rustc-dev-guide section about how we deal with universes - // during canonicalization in the new solver. - match self.canonicalize_mode { - // All placeholders and vars are canonicalized in the root universe. - CanonicalizeMode::Input { .. } => { - debug_assert!( - var_kinds.iter().all(|var| var.universe() == ty::UniverseIndex::ROOT), - "expected all vars to be canonicalized in root universe: {var_kinds:#?}" - ); - let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds); - (ty::UniverseIndex::ROOT, var_kinds) - } - // 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_kinds.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_kinds - .iter() - .map(|kind| kind.universe()) - .max() - .unwrap_or(ty::UniverseIndex::ROOT); - let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds); - (max_universe, var_kinds) - } - } - } - - fn inner_fold_ty(&mut self, t: I::Ty) -> I::Ty { - let kind = match t.kind() { - ty::Infer(i) => match i { - ty::TyVar(vid) => { - debug_assert_eq!( - self.delegate.opportunistic_resolve_ty_var(vid), - t, - "ty vid should have been resolved fully before canonicalization" - ); - - let sub_root = self.get_or_insert_sub_root(vid); - let ui = match self.canonicalize_mode { - CanonicalizeMode::Input { .. } => ty::UniverseIndex::ROOT, - CanonicalizeMode::Response { .. } => self - .delegate - .universe_of_ty(vid) - .unwrap_or_else(|| panic!("ty var should have been resolved: {t:?}")), - }; - CanonicalVarKind::Ty { ui, sub_root } - } - ty::IntVar(vid) => { - debug_assert_eq!( - self.delegate.opportunistic_resolve_int_var(vid), - t, - "ty vid should have been resolved fully before canonicalization" - ); - CanonicalVarKind::Int - } - ty::FloatVar(vid) => { - debug_assert_eq!( - self.delegate.opportunistic_resolve_float_var(vid), - t, - "ty vid should have been resolved fully before canonicalization" - ); - CanonicalVarKind::Float - } - ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => { - panic!("fresh vars not expected in canonicalization") - } - }, - ty::Placeholder(placeholder) => match self.canonicalize_mode { - CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy( - PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()), - ), - CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder), - }, - ty::Param(_) => match self.canonicalize_mode { - CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy( - PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()), - ), - CanonicalizeMode::Response { .. } => panic!("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::Pat(_, _) - | ty::FnDef(_, _) - | ty::FnPtr(..) - | ty::UnsafeBinder(_) - | ty::Dynamic(_, _) - | ty::Closure(..) - | ty::CoroutineClosure(..) - | ty::Coroutine(_, _) - | ty::CoroutineWitness(..) - | ty::Never - | ty::Tuple(_) - | ty::Alias(_, _) - | ty::Bound(_, _) - | ty::Error(_) => { - return if t.has_type_flags(NEEDS_CANONICAL) { - ensure_sufficient_stack(|| t.super_fold_with(self)) - } else { - t - }; - } - }; - - let var = self.get_or_insert_bound_var(t, kind); - - Ty::new_anon_bound(self.cx(), self.binder_index, var) - } -} - -impl, I: Interner> TypeFolder for Canonicalizer<'_, D, I> { - fn cx(&self) -> I { - self.delegate.cx() - } - - fn fold_binder(&mut self, t: ty::Binder) -> ty::Binder - where - T: TypeFoldable, - { - 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: I::Region) -> I::Region { - let kind = match r.kind() { - ty::ReBound(..) => return r, - - // We don't canonicalize `ReStatic` in the `param_env` as we use it - // when checking whether a `ParamEnv` candidate is global. - ty::ReStatic => match self.canonicalize_mode { - CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { .. }) => { - CanonicalVarKind::Region(ty::UniverseIndex::ROOT) - } - CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv) - | CanonicalizeMode::Response { .. } => return r, - }, - - // `ReErased` should only be encountered in the hidden - // type of an opaque for regions that are ignored for the purposes of - // captures. - // - // FIXME: We should investigate the perf implications of not uniquifying - // `ReErased`. We may be able to short-circuit registering region - // obligations if we encounter a `ReErased` on one side, for example. - ty::ReErased | ty::ReError(_) => match self.canonicalize_mode { - CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), - CanonicalizeMode::Response { .. } => return r, - }, - - ty::ReEarlyParam(_) | ty::ReLateParam(_) => match self.canonicalize_mode { - CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), - CanonicalizeMode::Response { .. } => { - panic!("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()) { - panic!("new placeholder in universe {max_input_universe:?}: {r:?}"); - } - CanonicalVarKind::PlaceholderRegion(placeholder) - } - }, - - ty::ReVar(vid) => { - debug_assert_eq!( - self.delegate.opportunistic_resolve_lt_var(vid), - r, - "region vid should have been resolved fully before canonicalization" - ); - match self.canonicalize_mode { - CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), - CanonicalizeMode::Response { .. } => { - CanonicalVarKind::Region(self.delegate.universe_of_lt(vid).unwrap()) - } - } - } - }; - - let var = self.get_or_insert_bound_var(r, kind); - - Region::new_anon_bound(self.cx(), self.binder_index, var) - } - - fn fold_ty(&mut self, t: I::Ty) -> I::Ty { - if let Some(&ty) = self.cache.get(&(self.binder_index, t)) { - ty - } else { - let res = self.inner_fold_ty(t); - let old = self.cache.insert((self.binder_index, t), res); - assert_eq!(old, None); - res - } - } - - fn fold_const(&mut self, c: I::Const) -> I::Const { - let kind = match c.kind() { - ty::ConstKind::Infer(i) => match i { - ty::InferConst::Var(vid) => { - debug_assert_eq!( - self.delegate.opportunistic_resolve_ct_var(vid), - c, - "const vid should have been resolved fully before canonicalization" - ); - - match self.canonicalize_mode { - CanonicalizeMode::Input { .. } => { - CanonicalVarKind::Const(ty::UniverseIndex::ROOT) - } - CanonicalizeMode::Response { .. } => { - CanonicalVarKind::Const(self.delegate.universe_of_ct(vid).unwrap()) - } - } - } - ty::InferConst::Fresh(_) => todo!(), - }, - ty::ConstKind::Placeholder(placeholder) => match self.canonicalize_mode { - CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst( - PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()), - ), - CanonicalizeMode::Response { .. } => { - CanonicalVarKind::PlaceholderConst(placeholder) - } - }, - ty::ConstKind::Param(_) => match self.canonicalize_mode { - CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst( - PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()), - ), - CanonicalizeMode::Response { .. } => panic!("param ty in response: {c:?}"), - }, - // FIXME: See comment above -- we could fold the region separately or something. - ty::ConstKind::Bound(_, _) - | ty::ConstKind::Unevaluated(_) - | ty::ConstKind::Value(_) - | ty::ConstKind::Error(_) - | ty::ConstKind::Expr(_) => { - return if c.has_type_flags(NEEDS_CANONICAL) { c.super_fold_with(self) } else { c }; - } - }; - - let var = self.get_or_insert_bound_var(c, kind); - - Const::new_anon_bound(self.cx(), self.binder_index, var) - } - - fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate { - if p.flags().intersects(NEEDS_CANONICAL) { p.super_fold_with(self) } else { p } - } - - fn fold_clauses(&mut self, c: I::Clauses) -> I::Clauses { - match self.canonicalize_mode { - CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv) - | CanonicalizeMode::Response { max_input_universe: _ } => {} - CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { .. }) => { - panic!("erasing 'static in env") - } - } - if c.flags().intersects(NEEDS_CANONICAL) { c.super_fold_with(self) } else { c } - } -} diff --git a/compiler/rustc_next_trait_solver/src/lib.rs b/compiler/rustc_next_trait_solver/src/lib.rs index d3965e14c68..5fa29b7d9f8 100644 --- a/compiler/rustc_next_trait_solver/src/lib.rs +++ b/compiler/rustc_next_trait_solver/src/lib.rs @@ -10,7 +10,7 @@ #![allow(rustc::usage_of_type_ir_traits)] // tidy-alphabetical-end -pub mod canonicalizer; +pub mod canonical; pub mod coherence; pub mod delegate; pub mod placeholder; diff --git a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs deleted file mode 100644 index 889588afe61..00000000000 --- a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs +++ /dev/null @@ -1,517 +0,0 @@ -//! 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 std::iter; - -use rustc_index::IndexVec; -use rustc_type_ir::data_structures::HashSet; -use rustc_type_ir::inherent::*; -use rustc_type_ir::relate::solver_relating::RelateExt; -use rustc_type_ir::solve::OpaqueTypesJank; -use rustc_type_ir::{ - self as ty, Canonical, CanonicalVarKind, CanonicalVarValues, InferCtxtLike, Interner, - TypeFoldable, -}; -use tracing::{debug, instrument, trace}; - -use crate::canonicalizer::Canonicalizer; -use crate::delegate::SolverDelegate; -use crate::resolve::eager_resolve_vars; -use crate::solve::eval_ctxt::CurrentGoalKind; -use crate::solve::{ - CanonicalInput, CanonicalResponse, Certainty, EvalCtxt, ExternalConstraintsData, Goal, - MaybeCause, NestedNormalizationGoals, NoSolution, PredefinedOpaquesData, QueryInput, - QueryResult, Response, inspect, response_no_constraints_raw, -}; - -trait ResponseT { - fn var_values(&self) -> CanonicalVarValues; -} - -impl ResponseT for Response { - fn var_values(&self) -> CanonicalVarValues { - self.var_values - } -} - -impl ResponseT for inspect::State { - fn var_values(&self) -> CanonicalVarValues { - self.var_values - } -} - -impl EvalCtxt<'_, D> -where - D: SolverDelegate, - I: Interner, -{ - /// Canonicalizes the goal remembering the original values - /// for each bound variable. - /// - /// This expects `goal` and `opaque_types` to be eager resolved. - pub(super) fn canonicalize_goal( - delegate: &D, - goal: Goal, - opaque_types: Vec<(ty::OpaqueTypeKey, I::Ty)>, - ) -> (Vec, CanonicalInput) { - let mut orig_values = Default::default(); - let canonical = Canonicalizer::canonicalize_input( - delegate, - &mut orig_values, - QueryInput { - goal, - predefined_opaques_in_body: delegate - .cx() - .mk_predefined_opaques_in_body(PredefinedOpaquesData { opaque_types }), - }, - ); - let query_input = - ty::CanonicalQueryInput { canonical, typing_mode: delegate.typing_mode() }; - (orig_values, query_input) - } - - /// 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 expressible - /// using simple unification of inference variables. - /// - /// This takes the `shallow_certainty` which represents whether we're confident - /// that the final result of the current goal only depends on the nested goals. - /// - /// In case this is `Certainty::Maybe`, there may still be additional nested goals - /// or inference constraints required for this candidate to be hold. The candidate - /// always requires all already added constraints and nested goals. - #[instrument(level = "trace", skip(self), ret)] - pub(in crate::solve) fn evaluate_added_goals_and_make_canonical_response( - &mut self, - shallow_certainty: Certainty, - ) -> QueryResult { - self.inspect.make_canonical_response(shallow_certainty); - - let goals_certainty = self.try_evaluate_added_goals()?; - assert_eq!( - self.tainted, - Ok(()), - "EvalCtxt is tainted -- nested goals may have been dropped in a \ - previous call to `try_evaluate_added_goals!`" - ); - - // We only check for leaks from universes which were entered inside - // of the query. - self.delegate.leak_check(self.max_input_universe).map_err(|NoSolution| { - trace!("failed the leak check"); - NoSolution - })?; - - let (certainty, normalization_nested_goals) = - match (self.current_goal_kind, shallow_certainty) { - // When normalizing, we've replaced the expected term with an unconstrained - // inference variable. This means that we dropped information which could - // have been important. We handle this by instead returning the nested goals - // to the caller, where they are then handled. We only do so if we do not - // need to recompute the `NormalizesTo` goal afterwards to avoid repeatedly - // uplifting its nested goals. This is the case if the `shallow_certainty` is - // `Certainty::Yes`. - (CurrentGoalKind::NormalizesTo, Certainty::Yes) => { - let goals = std::mem::take(&mut self.nested_goals); - // As we return all ambiguous nested goals, we can ignore the certainty - // returned by `self.try_evaluate_added_goals()`. - if goals.is_empty() { - assert!(matches!(goals_certainty, Certainty::Yes)); - } - ( - Certainty::Yes, - NestedNormalizationGoals( - goals.into_iter().map(|(s, g, _)| (s, g)).collect(), - ), - ) - } - _ => { - let certainty = shallow_certainty.and(goals_certainty); - (certainty, NestedNormalizationGoals::empty()) - } - }; - - if let Certainty::Maybe { - cause: cause @ MaybeCause::Overflow { keep_constraints: false, .. }, - opaque_types_jank, - } = certainty - { - // If we have overflow, it's probable that we're substituting a type - // into itself infinitely and any partial substitutions in the query - // response are probably not useful anyways, so just return an empty - // query response. - // - // This may prevent us from potentially useful inference, e.g. - // 2 candidates, one ambiguous and one overflow, which both - // have the same inference constraints. - // - // Changing this to retain some constraints in the future - // won't be a breaking change, so this is good enough for now. - return Ok(self.make_ambiguous_response_no_constraints(cause, opaque_types_jank)); - } - - let external_constraints = - self.compute_external_query_constraints(certainty, normalization_nested_goals); - let (var_values, mut external_constraints) = - eager_resolve_vars(self.delegate, (self.var_values, external_constraints)); - - // Remove any trivial or duplicated region constraints once we've resolved regions - let mut unique = HashSet::default(); - external_constraints.region_constraints.retain(|outlives| { - outlives.0.as_region().is_none_or(|re| re != outlives.1) && unique.insert(*outlives) - }); - - let canonical = Canonicalizer::canonicalize_response( - self.delegate, - self.max_input_universe, - &mut Default::default(), - Response { - var_values, - certainty, - external_constraints: self.cx().mk_external_constraints(external_constraints), - }, - ); - - // HACK: We bail with overflow if the response would have too many non-region - // inference variables. This tends to only happen if we encounter a lot of - // ambiguous alias types which get replaced with fresh inference variables - // during generalization. This prevents hangs caused by an exponential blowup, - // see tests/ui/traits/next-solver/coherence-alias-hang.rs. - match self.current_goal_kind { - // We don't do so for `NormalizesTo` goals as we erased the expected term and - // bailing with overflow here would prevent us from detecting a type-mismatch, - // causing a coherence error in diesel, see #131969. We still bail with overflow - // when later returning from the parent AliasRelate goal. - CurrentGoalKind::NormalizesTo => {} - CurrentGoalKind::Misc | CurrentGoalKind::CoinductiveTrait => { - let num_non_region_vars = canonical - .variables - .iter() - .filter(|c| !c.is_region() && c.is_existential()) - .count(); - if num_non_region_vars > self.cx().recursion_limit() { - debug!(?num_non_region_vars, "too many inference variables -> overflow"); - return Ok(self.make_ambiguous_response_no_constraints( - MaybeCause::Overflow { - suggest_increasing_limit: true, - keep_constraints: false, - }, - OpaqueTypesJank::AllGood, - )); - } - } - } - - Ok(canonical) - } - - /// Constructs a totally unconstrained, ambiguous response to a goal. - /// - /// Take care when using this, since often it's useful to respond with - /// ambiguity but return constrained variables to guide inference. - pub(in crate::solve) fn make_ambiguous_response_no_constraints( - &self, - cause: MaybeCause, - opaque_types_jank: OpaqueTypesJank, - ) -> CanonicalResponse { - response_no_constraints_raw( - self.cx(), - self.max_input_universe, - self.variables, - Certainty::Maybe { cause, opaque_types_jank }, - ) - } - - /// Computes the region constraints and *new* opaque types registered when - /// proving a goal. - /// - /// If an opaque was already constrained before proving this goal, then the - /// external constraints do not need to record that opaque, since if it is - /// further constrained by inference, that will be passed back in the var - /// values. - #[instrument(level = "trace", skip(self), ret)] - fn compute_external_query_constraints( - &self, - certainty: Certainty, - normalization_nested_goals: NestedNormalizationGoals, - ) -> ExternalConstraintsData { - // We only return region constraints once the certainty is `Yes`. This - // is necessary as we may drop nested goals on ambiguity, which may result - // in unconstrained inference variables in the region constraints. It also - // prevents us from emitting duplicate region constraints, avoiding some - // unnecessary work. This slightly weakens the leak check in case it uses - // region constraints from an ambiguous nested goal. This is tested in both - // `tests/ui/higher-ranked/leak-check/leak-check-in-selection-5-ambig.rs` and - // `tests/ui/higher-ranked/leak-check/leak-check-in-selection-6-ambig-unify.rs`. - let region_constraints = if certainty == Certainty::Yes { - self.delegate.make_deduplicated_outlives_constraints() - } else { - Default::default() - }; - - // We only return *newly defined* opaque types from canonical queries. - // - // Constraints for any existing opaque types are already tracked by changes - // to the `var_values`. - let opaque_types = self - .delegate - .clone_opaque_types_added_since(self.initial_opaque_types_storage_num_entries); - - ExternalConstraintsData { region_constraints, opaque_types, normalization_nested_goals } - } - - /// 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, returning - /// the `normalization_nested_goals` - pub(super) fn instantiate_and_apply_query_response( - delegate: &D, - param_env: I::ParamEnv, - original_values: &[I::GenericArg], - response: CanonicalResponse, - span: I::Span, - ) -> (NestedNormalizationGoals, Certainty) { - let instantiation = Self::compute_query_response_instantiation_values( - delegate, - &original_values, - &response, - span, - ); - - let Response { var_values, external_constraints, certainty } = - delegate.instantiate_canonical(response, instantiation); - - Self::unify_query_var_values(delegate, param_env, &original_values, var_values, span); - - let ExternalConstraintsData { - region_constraints, - opaque_types, - normalization_nested_goals, - } = &*external_constraints; - - Self::register_region_constraints(delegate, region_constraints, span); - Self::register_new_opaque_types(delegate, opaque_types, span); - - (normalization_nested_goals.clone(), certainty) - } - - /// This returns the canonical variable values to instantiate the bound variables of - /// the canonical response. This depends on the `original_values` for the - /// bound variables. - fn compute_query_response_instantiation_values>( - delegate: &D, - original_values: &[I::GenericArg], - response: &Canonical, - span: I::Span, - ) -> CanonicalVarValues { - // 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 = delegate.universe(); - let universes_created_in_query = response.max_universe.index(); - for _ in 0..universes_created_in_query { - delegate.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 = IndexVec::from_elem_n(None, response.variables.len()); - for (original_value, result_value) in - iter::zip(original_values, var_values.var_values.iter()) - { - match result_value.kind() { - ty::GenericArgKind::Type(t) => { - // We disable the instantiation guess for inference variables - // and only use it for placeholders. We need to handle the - // `sub_root` of type inference variables which would make this - // more involved. They are also a lot rarer than region variables. - if let ty::Bound(debruijn, b) = t.kind() - && !matches!( - response.variables.get(b.var().as_usize()).unwrap(), - CanonicalVarKind::Ty { .. } - ) - { - assert_eq!(debruijn, ty::INNERMOST); - opt_values[b.var()] = Some(*original_value); - } - } - ty::GenericArgKind::Lifetime(r) => { - if let ty::ReBound(debruijn, br) = r.kind() { - assert_eq!(debruijn, ty::INNERMOST); - opt_values[br.var()] = Some(*original_value); - } - } - ty::GenericArgKind::Const(c) => { - if let ty::ConstKind::Bound(debruijn, bv) = c.kind() { - assert_eq!(debruijn, ty::INNERMOST); - opt_values[bv.var()] = Some(*original_value); - } - } - } - } - CanonicalVarValues::instantiate(delegate.cx(), response.variables, |var_values, kind| { - if kind.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. - delegate.instantiate_canonical_var(kind, span, &var_values, |idx| { - prev_universe + idx.index() - }) - } else if kind.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 conceptually 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[ty::BoundVar::from_usize(var_values.len())] { - v - } else { - delegate.instantiate_canonical_var(kind, span, &var_values, |_| 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[kind.expect_placeholder_index()] - } - }) - } - - /// Unify the `original_values` with the `var_values` returned by the canonical query.. - /// - /// This assumes that this unification will always succeed. This is the case when - /// applying a query response right away. However, calling a canonical query, doing any - /// other kind of trait solving, and only then instantiating the result of the query - /// can cause the instantiation to fail. This is not supported and we ICE in this case. - /// - /// We always structurally instantiate aliases. Relating aliases needs to be different - /// depending on whether the alias is *rigid* or not. We're only really able to tell - /// whether an alias is rigid by using the trait solver. When instantiating a response - /// from the solver we assume that the solver correctly handled aliases and therefore - /// always relate them structurally here. - #[instrument(level = "trace", skip(delegate))] - fn unify_query_var_values( - delegate: &D, - param_env: I::ParamEnv, - original_values: &[I::GenericArg], - var_values: CanonicalVarValues, - span: I::Span, - ) { - assert_eq!(original_values.len(), var_values.len()); - - for (&orig, response) in iter::zip(original_values, var_values.var_values.iter()) { - let goals = - delegate.eq_structurally_relating_aliases(param_env, orig, response, span).unwrap(); - assert!(goals.is_empty()); - } - } - - fn register_region_constraints( - delegate: &D, - outlives: &[ty::OutlivesPredicate], - span: I::Span, - ) { - for &ty::OutlivesPredicate(lhs, rhs) in outlives { - match lhs.kind() { - ty::GenericArgKind::Lifetime(lhs) => delegate.sub_regions(rhs, lhs, span), - ty::GenericArgKind::Type(lhs) => delegate.register_ty_outlives(lhs, rhs, span), - ty::GenericArgKind::Const(_) => panic!("const outlives: {lhs:?}: {rhs:?}"), - } - } - } - - fn register_new_opaque_types( - delegate: &D, - opaque_types: &[(ty::OpaqueTypeKey, I::Ty)], - span: I::Span, - ) { - for &(key, ty) in opaque_types { - let prev = delegate.register_hidden_type_in_storage(key, ty, span); - // We eagerly resolve inference variables when computing the query response. - // This can cause previously distinct opaque type keys to now be structurally equal. - // - // To handle this, we store any duplicate entries in a separate list to check them - // at the end of typeck/borrowck. We could alternatively eagerly equate the hidden - // types here. However, doing so is difficult as it may result in nested goals and - // any errors may make it harder to track the control flow for diagnostics. - if let Some(prev) = prev { - delegate.add_duplicate_opaque_type(key, prev, span); - } - } - } -} - -/// Used by proof trees to be able to recompute intermediate actions while -/// evaluating a goal. The `var_values` not only include the bound variables -/// of the query input, but also contain all unconstrained inference vars -/// created while evaluating this goal. -pub(in crate::solve) fn make_canonical_state( - delegate: &D, - var_values: &[I::GenericArg], - max_input_universe: ty::UniverseIndex, - data: T, -) -> inspect::CanonicalState -where - D: SolverDelegate, - I: Interner, - T: TypeFoldable, -{ - let var_values = CanonicalVarValues { var_values: delegate.cx().mk_args(var_values) }; - let state = inspect::State { var_values, data }; - let state = eager_resolve_vars(delegate, state); - Canonicalizer::canonicalize_response(delegate, max_input_universe, &mut vec![], state) -} - -// FIXME: needs to be pub to be accessed by downstream -// `rustc_trait_selection::solve::inspect::analyse`. -pub fn instantiate_canonical_state>( - delegate: &D, - span: I::Span, - param_env: I::ParamEnv, - orig_values: &mut Vec, - state: inspect::CanonicalState, -) -> T -where - D: SolverDelegate, - I: Interner, -{ - // In case any fresh inference variables have been created between `state` - // and the previous instantiation, extend `orig_values` for it. - orig_values.extend( - state.value.var_values.var_values.as_slice()[orig_values.len()..] - .iter() - .map(|&arg| delegate.fresh_var_for_kind_with_span(arg, span)), - ); - - let instantiation = - EvalCtxt::compute_query_response_instantiation_values(delegate, orig_values, &state, span); - - let inspect::State { var_values, data } = delegate.instantiate_canonical(state, instantiation); - - EvalCtxt::unify_query_var_values(delegate, param_env, orig_values, var_values, span); - data -} diff --git a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs index 5df7c92d881..8f9b68dbac4 100644 --- a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs +++ b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs @@ -17,6 +17,8 @@ use rustc_type_ir::{ use tracing::{debug, instrument, trace}; use super::has_only_region_constraints; +use crate::canonical::canonicalizer::Canonicalizer; +use crate::canonical::response_no_constraints_raw; use crate::coherence; use crate::delegate::SolverDelegate; use crate::placeholder::BoundVarReplacer; @@ -24,12 +26,11 @@ use crate::resolve::eager_resolve_vars; use crate::solve::search_graph::SearchGraph; use crate::solve::ty::may_use_unstable_feature; use crate::solve::{ - CanonicalInput, Certainty, FIXPOINT_STEP_LIMIT, Goal, GoalEvaluation, GoalSource, - GoalStalledOn, HasChanged, NestedNormalizationGoals, NoSolution, QueryInput, QueryResult, - inspect, + CanonicalInput, CanonicalResponse, Certainty, ExternalConstraintsData, FIXPOINT_STEP_LIMIT, + Goal, GoalEvaluation, GoalSource, GoalStalledOn, HasChanged, MaybeCause, + NestedNormalizationGoals, NoSolution, QueryInput, QueryResult, Response, inspect, }; -pub(super) mod canonical; mod probe; /// The kind of goal we're currently proving. @@ -1223,6 +1224,199 @@ where vec![] } } + + /// 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 expressible + /// using simple unification of inference variables. + /// + /// This takes the `shallow_certainty` which represents whether we're confident + /// that the final result of the current goal only depends on the nested goals. + /// + /// In case this is `Certainty::Maybe`, there may still be additional nested goals + /// or inference constraints required for this candidate to be hold. The candidate + /// always requires all already added constraints and nested goals. + #[instrument(level = "trace", skip(self), ret)] + pub(in crate::solve) fn evaluate_added_goals_and_make_canonical_response( + &mut self, + shallow_certainty: Certainty, + ) -> QueryResult { + self.inspect.make_canonical_response(shallow_certainty); + + let goals_certainty = self.try_evaluate_added_goals()?; + assert_eq!( + self.tainted, + Ok(()), + "EvalCtxt is tainted -- nested goals may have been dropped in a \ + previous call to `try_evaluate_added_goals!`" + ); + + // We only check for leaks from universes which were entered inside + // of the query. + self.delegate.leak_check(self.max_input_universe).map_err(|NoSolution| { + trace!("failed the leak check"); + NoSolution + })?; + + let (certainty, normalization_nested_goals) = + match (self.current_goal_kind, shallow_certainty) { + // When normalizing, we've replaced the expected term with an unconstrained + // inference variable. This means that we dropped information which could + // have been important. We handle this by instead returning the nested goals + // to the caller, where they are then handled. We only do so if we do not + // need to recompute the `NormalizesTo` goal afterwards to avoid repeatedly + // uplifting its nested goals. This is the case if the `shallow_certainty` is + // `Certainty::Yes`. + (CurrentGoalKind::NormalizesTo, Certainty::Yes) => { + let goals = std::mem::take(&mut self.nested_goals); + // As we return all ambiguous nested goals, we can ignore the certainty + // returned by `self.try_evaluate_added_goals()`. + if goals.is_empty() { + assert!(matches!(goals_certainty, Certainty::Yes)); + } + ( + Certainty::Yes, + NestedNormalizationGoals( + goals.into_iter().map(|(s, g, _)| (s, g)).collect(), + ), + ) + } + _ => { + let certainty = shallow_certainty.and(goals_certainty); + (certainty, NestedNormalizationGoals::empty()) + } + }; + + if let Certainty::Maybe { + cause: cause @ MaybeCause::Overflow { keep_constraints: false, .. }, + opaque_types_jank, + } = certainty + { + // If we have overflow, it's probable that we're substituting a type + // into itself infinitely and any partial substitutions in the query + // response are probably not useful anyways, so just return an empty + // query response. + // + // This may prevent us from potentially useful inference, e.g. + // 2 candidates, one ambiguous and one overflow, which both + // have the same inference constraints. + // + // Changing this to retain some constraints in the future + // won't be a breaking change, so this is good enough for now. + return Ok(self.make_ambiguous_response_no_constraints(cause, opaque_types_jank)); + } + + let external_constraints = + self.compute_external_query_constraints(certainty, normalization_nested_goals); + let (var_values, mut external_constraints) = + eager_resolve_vars(self.delegate, (self.var_values, external_constraints)); + + // Remove any trivial or duplicated region constraints once we've resolved regions + let mut unique = HashSet::default(); + external_constraints.region_constraints.retain(|outlives| { + outlives.0.as_region().is_none_or(|re| re != outlives.1) && unique.insert(*outlives) + }); + + let canonical = Canonicalizer::canonicalize_response( + self.delegate, + self.max_input_universe, + &mut Default::default(), + Response { + var_values, + certainty, + external_constraints: self.cx().mk_external_constraints(external_constraints), + }, + ); + + // HACK: We bail with overflow if the response would have too many non-region + // inference variables. This tends to only happen if we encounter a lot of + // ambiguous alias types which get replaced with fresh inference variables + // during generalization. This prevents hangs caused by an exponential blowup, + // see tests/ui/traits/next-solver/coherence-alias-hang.rs. + match self.current_goal_kind { + // We don't do so for `NormalizesTo` goals as we erased the expected term and + // bailing with overflow here would prevent us from detecting a type-mismatch, + // causing a coherence error in diesel, see #131969. We still bail with overflow + // when later returning from the parent AliasRelate goal. + CurrentGoalKind::NormalizesTo => {} + CurrentGoalKind::Misc | CurrentGoalKind::CoinductiveTrait => { + let num_non_region_vars = canonical + .variables + .iter() + .filter(|c| !c.is_region() && c.is_existential()) + .count(); + if num_non_region_vars > self.cx().recursion_limit() { + debug!(?num_non_region_vars, "too many inference variables -> overflow"); + return Ok(self.make_ambiguous_response_no_constraints( + MaybeCause::Overflow { + suggest_increasing_limit: true, + keep_constraints: false, + }, + OpaqueTypesJank::AllGood, + )); + } + } + } + + Ok(canonical) + } + + /// Constructs a totally unconstrained, ambiguous response to a goal. + /// + /// Take care when using this, since often it's useful to respond with + /// ambiguity but return constrained variables to guide inference. + pub(in crate::solve) fn make_ambiguous_response_no_constraints( + &self, + cause: MaybeCause, + opaque_types_jank: OpaqueTypesJank, + ) -> CanonicalResponse { + response_no_constraints_raw( + self.cx(), + self.max_input_universe, + self.variables, + Certainty::Maybe { cause, opaque_types_jank }, + ) + } + + /// Computes the region constraints and *new* opaque types registered when + /// proving a goal. + /// + /// If an opaque was already constrained before proving this goal, then the + /// external constraints do not need to record that opaque, since if it is + /// further constrained by inference, that will be passed back in the var + /// values. + #[instrument(level = "trace", skip(self), ret)] + fn compute_external_query_constraints( + &self, + certainty: Certainty, + normalization_nested_goals: NestedNormalizationGoals, + ) -> ExternalConstraintsData { + // We only return region constraints once the certainty is `Yes`. This + // is necessary as we may drop nested goals on ambiguity, which may result + // in unconstrained inference variables in the region constraints. It also + // prevents us from emitting duplicate region constraints, avoiding some + // unnecessary work. This slightly weakens the leak check in case it uses + // region constraints from an ambiguous nested goal. This is tested in both + // `tests/ui/higher-ranked/leak-check/leak-check-in-selection-5-ambig.rs` and + // `tests/ui/higher-ranked/leak-check/leak-check-in-selection-6-ambig-unify.rs`. + let region_constraints = if certainty == Certainty::Yes { + self.delegate.make_deduplicated_outlives_constraints() + } else { + Default::default() + }; + + // We only return *newly defined* opaque types from canonical queries. + // + // Constraints for any existing opaque types are already tracked by changes + // to the `var_values`. + let opaque_types = self + .delegate + .clone_opaque_types_added_since(self.initial_opaque_types_storage_num_entries); + + ExternalConstraintsData { region_constraints, opaque_types, normalization_nested_goals } + } } /// Eagerly replace aliases with inference variables, emitting `AliasRelate` diff --git a/compiler/rustc_next_trait_solver/src/solve/inspect/build.rs b/compiler/rustc_next_trait_solver/src/solve/inspect/build.rs index 2675ed0d0da..4369148baf9 100644 --- a/compiler/rustc_next_trait_solver/src/solve/inspect/build.rs +++ b/compiler/rustc_next_trait_solver/src/solve/inspect/build.rs @@ -10,8 +10,8 @@ use derive_where::derive_where; use rustc_type_ir::inherent::*; use rustc_type_ir::{self as ty, Interner}; +use crate::canonical; use crate::delegate::SolverDelegate; -use crate::solve::eval_ctxt::canonical; use crate::solve::{Certainty, Goal, GoalSource, QueryResult, inspect}; /// We need to know whether to build a prove tree while evaluating. We diff --git a/compiler/rustc_next_trait_solver/src/solve/inspect/mod.rs b/compiler/rustc_next_trait_solver/src/solve/inspect/mod.rs index 0d8c0060126..65f32f1947f 100644 --- a/compiler/rustc_next_trait_solver/src/solve/inspect/mod.rs +++ b/compiler/rustc_next_trait_solver/src/solve/inspect/mod.rs @@ -2,5 +2,3 @@ pub use rustc_type_ir::solve::inspect::*; mod build; pub(in crate::solve) use build::*; - -pub use crate::solve::eval_ctxt::canonical::instantiate_canonical_state; diff --git a/compiler/rustc_next_trait_solver/src/solve/mod.rs b/compiler/rustc_next_trait_solver/src/solve/mod.rs index fb900b592d1..afb86aaf8ab 100644 --- a/compiler/rustc_next_trait_solver/src/solve/mod.rs +++ b/compiler/rustc_next_trait_solver/src/solve/mod.rs @@ -380,25 +380,6 @@ where } } -fn response_no_constraints_raw( - cx: I, - max_universe: ty::UniverseIndex, - variables: I::CanonicalVarKinds, - certainty: Certainty, -) -> CanonicalResponse { - ty::Canonical { - max_universe, - variables, - value: Response { - var_values: ty::CanonicalVarValues::make_identity(cx, variables), - // FIXME: maybe we should store the "no response" version in cx, like - // we do for cx.types and stuff. - external_constraints: cx.mk_external_constraints(ExternalConstraintsData::default()), - certainty, - }, - } -} - /// The result of evaluating a goal. pub struct GoalEvaluation { /// The goal we've evaluated. This is the input goal, but potentially with its diff --git a/compiler/rustc_next_trait_solver/src/solve/search_graph.rs b/compiler/rustc_next_trait_solver/src/solve/search_graph.rs index 289325d7055..aa9dfc9a9a2 100644 --- a/compiler/rustc_next_trait_solver/src/solve/search_graph.rs +++ b/compiler/rustc_next_trait_solver/src/solve/search_graph.rs @@ -6,6 +6,7 @@ use rustc_type_ir::search_graph::{self, PathKind}; use rustc_type_ir::solve::{CanonicalInput, Certainty, NoSolution, QueryResult}; use rustc_type_ir::{Interner, TypingMode}; +use crate::canonical::response_no_constraints_raw; use crate::delegate::SolverDelegate; use crate::solve::{ EvalCtxt, FIXPOINT_STEP_LIMIT, has_no_inference_or_external_constraints, inspect, @@ -127,7 +128,7 @@ fn response_no_constraints( input: CanonicalInput, certainty: Certainty, ) -> QueryResult { - Ok(super::response_no_constraints_raw( + Ok(response_no_constraints_raw( cx, input.canonical.max_universe, input.canonical.variables, diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs index 086a7a44786..c010add0fc5 100644 --- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs +++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs @@ -18,9 +18,9 @@ use rustc_middle::traits::ObligationCause; use rustc_middle::traits::solve::{Certainty, Goal, GoalSource, NoSolution, QueryResult}; use rustc_middle::ty::{TyCtxt, VisitorResult, try_visit}; use rustc_middle::{bug, ty}; +use rustc_next_trait_solver::canonical::instantiate_canonical_state; use rustc_next_trait_solver::resolve::eager_resolve_vars; -use rustc_next_trait_solver::solve::inspect::{self, instantiate_canonical_state}; -use rustc_next_trait_solver::solve::{MaybeCause, SolverDelegateEvalExt as _}; +use rustc_next_trait_solver::solve::{MaybeCause, SolverDelegateEvalExt as _, inspect}; use rustc_span::Span; use tracing::instrument; -- cgit 1.4.1-3-g733a5 From b83c0f0e94592d1a7eae1124e4e951f331ccf6c8 Mon Sep 17 00:00:00 2001 From: lcnr Date: Tue, 16 Sep 2025 15:30:25 +0200 Subject: canonical: yeet `EvalCtxt`, mk `Canonicalizer` private --- .../src/canonical/canonicalizer.rs | 7 +- .../rustc_next_trait_solver/src/canonical/mod.rs | 419 +++++++++++---------- .../src/solve/eval_ctxt/mod.rs | 18 +- 3 files changed, 233 insertions(+), 211 deletions(-) diff --git a/compiler/rustc_next_trait_solver/src/canonical/canonicalizer.rs b/compiler/rustc_next_trait_solver/src/canonical/canonicalizer.rs index 4b4ec4956eb..b25671d676b 100644 --- a/compiler/rustc_next_trait_solver/src/canonical/canonicalizer.rs +++ b/compiler/rustc_next_trait_solver/src/canonical/canonicalizer.rs @@ -57,7 +57,7 @@ enum CanonicalizeMode { }, } -pub struct Canonicalizer<'a, D: SolverDelegate, I: Interner> { +pub(super) struct Canonicalizer<'a, D: SolverDelegate, I: Interner> { delegate: &'a D, // Immutable field. @@ -83,7 +83,7 @@ pub struct Canonicalizer<'a, D: SolverDelegate, I: Interner> { } impl<'a, D: SolverDelegate, I: Interner> Canonicalizer<'a, D, I> { - pub fn canonicalize_response>( + pub(super) fn canonicalize_response>( delegate: &'a D, max_input_universe: ty::UniverseIndex, variables: &'a mut Vec, @@ -112,7 +112,6 @@ impl<'a, D: SolverDelegate, I: Interner> Canonicalizer<'a, D, I> { let (max_universe, variables) = canonicalizer.finalize(); Canonical { max_universe, variables, value } } - fn canonicalize_param_env( delegate: &'a D, variables: &'a mut Vec, @@ -195,7 +194,7 @@ impl<'a, D: SolverDelegate, I: Interner> Canonicalizer<'a, D, I> { /// /// We want to keep the option of canonicalizing `'static` to an existential /// variable in the future by changing the way we detect global where-bounds. - pub fn canonicalize_input>( + pub(super) fn canonicalize_input>( delegate: &'a D, variables: &'a mut Vec, input: QueryInput, diff --git a/compiler/rustc_next_trait_solver/src/canonical/mod.rs b/compiler/rustc_next_trait_solver/src/canonical/mod.rs index 35881acf0c7..e3520e238ed 100644 --- a/compiler/rustc_next_trait_solver/src/canonical/mod.rs +++ b/compiler/rustc_next_trait_solver/src/canonical/mod.rs @@ -24,7 +24,7 @@ use tracing::instrument; use crate::delegate::SolverDelegate; use crate::resolve::eager_resolve_vars; use crate::solve::{ - CanonicalInput, CanonicalResponse, Certainty, EvalCtxt, ExternalConstraintsData, Goal, + CanonicalInput, CanonicalResponse, Certainty, ExternalConstraintsData, Goal, NestedNormalizationGoals, PredefinedOpaquesData, QueryInput, Response, inspect, }; @@ -46,226 +46,248 @@ impl ResponseT for inspect::State { } } -impl EvalCtxt<'_, D> +/// Canonicalizes the goal remembering the original values +/// for each bound variable. +/// +/// This expects `goal` and `opaque_types` to be eager resolved. +pub(super) fn canonicalize_goal( + delegate: &D, + goal: Goal, + opaque_types: Vec<(ty::OpaqueTypeKey, I::Ty)>, +) -> (Vec, CanonicalInput) where D: SolverDelegate, I: Interner, { - /// Canonicalizes the goal remembering the original values - /// for each bound variable. - /// - /// This expects `goal` and `opaque_types` to be eager resolved. - pub(super) fn canonicalize_goal( - delegate: &D, - goal: Goal, - opaque_types: Vec<(ty::OpaqueTypeKey, I::Ty)>, - ) -> (Vec, CanonicalInput) { - let mut orig_values = Default::default(); - let canonical = Canonicalizer::canonicalize_input( - delegate, - &mut orig_values, - QueryInput { - goal, - predefined_opaques_in_body: delegate - .cx() - .mk_predefined_opaques_in_body(PredefinedOpaquesData { opaque_types }), - }, - ); - let query_input = - ty::CanonicalQueryInput { canonical, typing_mode: delegate.typing_mode() }; - (orig_values, query_input) - } + let mut orig_values = Default::default(); + let canonical = Canonicalizer::canonicalize_input( + delegate, + &mut orig_values, + QueryInput { + goal, + predefined_opaques_in_body: delegate + .cx() + .mk_predefined_opaques_in_body(PredefinedOpaquesData { opaque_types }), + }, + ); + let query_input = ty::CanonicalQueryInput { canonical, typing_mode: delegate.typing_mode() }; + (orig_values, query_input) +} - /// 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, returning - /// the `normalization_nested_goals` - pub(super) fn instantiate_and_apply_query_response( - delegate: &D, - param_env: I::ParamEnv, - original_values: &[I::GenericArg], - response: CanonicalResponse, - span: I::Span, - ) -> (NestedNormalizationGoals, Certainty) { - let instantiation = Self::compute_query_response_instantiation_values( - delegate, - &original_values, - &response, - span, - ); +pub(super) fn canonicalize_response( + delegate: &D, + max_input_universe: ty::UniverseIndex, + value: T, +) -> ty::Canonical +where + D: SolverDelegate, + I: Interner, + T: TypeFoldable, +{ + let mut orig_values = Default::default(); + let canonical = + Canonicalizer::canonicalize_response(delegate, max_input_universe, &mut orig_values, value); + canonical +} - let Response { var_values, external_constraints, certainty } = - delegate.instantiate_canonical(response, instantiation); +/// 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, returning +/// the `normalization_nested_goals` +pub(super) fn instantiate_and_apply_query_response( + delegate: &D, + param_env: I::ParamEnv, + original_values: &[I::GenericArg], + response: CanonicalResponse, + span: I::Span, +) -> (NestedNormalizationGoals, Certainty) +where + D: SolverDelegate, + I: Interner, +{ + let instantiation = + compute_query_response_instantiation_values(delegate, &original_values, &response, span); - Self::unify_query_var_values(delegate, param_env, &original_values, var_values, span); + let Response { var_values, external_constraints, certainty } = + delegate.instantiate_canonical(response, instantiation); - let ExternalConstraintsData { - region_constraints, - opaque_types, - normalization_nested_goals, - } = &*external_constraints; + unify_query_var_values(delegate, param_env, &original_values, var_values, span); - Self::register_region_constraints(delegate, region_constraints, span); - Self::register_new_opaque_types(delegate, opaque_types, span); + let ExternalConstraintsData { region_constraints, opaque_types, normalization_nested_goals } = + &*external_constraints; - (normalization_nested_goals.clone(), certainty) - } + register_region_constraints(delegate, region_constraints, span); + register_new_opaque_types(delegate, opaque_types, span); - /// This returns the canonical variable values to instantiate the bound variables of - /// the canonical response. This depends on the `original_values` for the - /// bound variables. - fn compute_query_response_instantiation_values>( - delegate: &D, - original_values: &[I::GenericArg], - response: &Canonical, - span: I::Span, - ) -> CanonicalVarValues { - // 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 = delegate.universe(); - let universes_created_in_query = response.max_universe.index(); - for _ in 0..universes_created_in_query { - delegate.create_next_universe(); - } + (normalization_nested_goals.clone(), certainty) +} + +/// This returns the canonical variable values to instantiate the bound variables of +/// the canonical response. This depends on the `original_values` for the +/// bound variables. +fn compute_query_response_instantiation_values( + delegate: &D, + original_values: &[I::GenericArg], + response: &Canonical, + span: I::Span, +) -> CanonicalVarValues +where + D: SolverDelegate, + I: Interner, + T: ResponseT, +{ + // 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 = delegate.universe(); + let universes_created_in_query = response.max_universe.index(); + for _ in 0..universes_created_in_query { + delegate.create_next_universe(); + } - let var_values = response.value.var_values(); - assert_eq!(original_values.len(), var_values.len()); + 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 = IndexVec::from_elem_n(None, response.variables.len()); - for (original_value, result_value) in - iter::zip(original_values, var_values.var_values.iter()) - { - match result_value.kind() { - ty::GenericArgKind::Type(t) => { - // We disable the instantiation guess for inference variables - // and only use it for placeholders. We need to handle the - // `sub_root` of type inference variables which would make this - // more involved. They are also a lot rarer than region variables. - if let ty::Bound(debruijn, b) = t.kind() - && !matches!( - response.variables.get(b.var().as_usize()).unwrap(), - CanonicalVarKind::Ty { .. } - ) - { - assert_eq!(debruijn, ty::INNERMOST); - opt_values[b.var()] = Some(*original_value); - } + // 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 = IndexVec::from_elem_n(None, response.variables.len()); + for (original_value, result_value) in iter::zip(original_values, var_values.var_values.iter()) { + match result_value.kind() { + ty::GenericArgKind::Type(t) => { + // We disable the instantiation guess for inference variables + // and only use it for placeholders. We need to handle the + // `sub_root` of type inference variables which would make this + // more involved. They are also a lot rarer than region variables. + if let ty::Bound(debruijn, b) = t.kind() + && !matches!( + response.variables.get(b.var().as_usize()).unwrap(), + CanonicalVarKind::Ty { .. } + ) + { + assert_eq!(debruijn, ty::INNERMOST); + opt_values[b.var()] = Some(*original_value); } - ty::GenericArgKind::Lifetime(r) => { - if let ty::ReBound(debruijn, br) = r.kind() { - assert_eq!(debruijn, ty::INNERMOST); - opt_values[br.var()] = Some(*original_value); - } + } + ty::GenericArgKind::Lifetime(r) => { + if let ty::ReBound(debruijn, br) = r.kind() { + assert_eq!(debruijn, ty::INNERMOST); + opt_values[br.var()] = Some(*original_value); } - ty::GenericArgKind::Const(c) => { - if let ty::ConstKind::Bound(debruijn, bv) = c.kind() { - assert_eq!(debruijn, ty::INNERMOST); - opt_values[bv.var()] = Some(*original_value); - } + } + ty::GenericArgKind::Const(c) => { + if let ty::ConstKind::Bound(debruijn, bv) = c.kind() { + assert_eq!(debruijn, ty::INNERMOST); + opt_values[bv.var()] = Some(*original_value); } } } - CanonicalVarValues::instantiate(delegate.cx(), response.variables, |var_values, kind| { - if kind.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. - delegate.instantiate_canonical_var(kind, span, &var_values, |idx| { - prev_universe + idx.index() - }) - } else if kind.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 conceptually 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[ty::BoundVar::from_usize(var_values.len())] { - v - } else { - delegate.instantiate_canonical_var(kind, span, &var_values, |_| prev_universe) - } + } + CanonicalVarValues::instantiate(delegate.cx(), response.variables, |var_values, kind| { + if kind.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. + delegate.instantiate_canonical_var(kind, span, &var_values, |idx| { + prev_universe + idx.index() + }) + } else if kind.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 conceptually 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[ty::BoundVar::from_usize(var_values.len())] { + v } 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[kind.expect_placeholder_index()] + delegate.instantiate_canonical_var(kind, span, &var_values, |_| 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[kind.expect_placeholder_index()] + } + }) +} - /// Unify the `original_values` with the `var_values` returned by the canonical query.. - /// - /// This assumes that this unification will always succeed. This is the case when - /// applying a query response right away. However, calling a canonical query, doing any - /// other kind of trait solving, and only then instantiating the result of the query - /// can cause the instantiation to fail. This is not supported and we ICE in this case. - /// - /// We always structurally instantiate aliases. Relating aliases needs to be different - /// depending on whether the alias is *rigid* or not. We're only really able to tell - /// whether an alias is rigid by using the trait solver. When instantiating a response - /// from the solver we assume that the solver correctly handled aliases and therefore - /// always relate them structurally here. - #[instrument(level = "trace", skip(delegate))] - fn unify_query_var_values( - delegate: &D, - param_env: I::ParamEnv, - original_values: &[I::GenericArg], - var_values: CanonicalVarValues, - span: I::Span, - ) { - assert_eq!(original_values.len(), var_values.len()); +/// Unify the `original_values` with the `var_values` returned by the canonical query.. +/// +/// This assumes that this unification will always succeed. This is the case when +/// applying a query response right away. However, calling a canonical query, doing any +/// other kind of trait solving, and only then instantiating the result of the query +/// can cause the instantiation to fail. This is not supported and we ICE in this case. +/// +/// We always structurally instantiate aliases. Relating aliases needs to be different +/// depending on whether the alias is *rigid* or not. We're only really able to tell +/// whether an alias is rigid by using the trait solver. When instantiating a response +/// from the solver we assume that the solver correctly handled aliases and therefore +/// always relate them structurally here. +#[instrument(level = "trace", skip(delegate))] +fn unify_query_var_values( + delegate: &D, + param_env: I::ParamEnv, + original_values: &[I::GenericArg], + var_values: CanonicalVarValues, + span: I::Span, +) where + D: SolverDelegate, + I: Interner, +{ + assert_eq!(original_values.len(), var_values.len()); - for (&orig, response) in iter::zip(original_values, var_values.var_values.iter()) { - let goals = - delegate.eq_structurally_relating_aliases(param_env, orig, response, span).unwrap(); - assert!(goals.is_empty()); - } + for (&orig, response) in iter::zip(original_values, var_values.var_values.iter()) { + let goals = + delegate.eq_structurally_relating_aliases(param_env, orig, response, span).unwrap(); + assert!(goals.is_empty()); } +} - fn register_region_constraints( - delegate: &D, - outlives: &[ty::OutlivesPredicate], - span: I::Span, - ) { - for &ty::OutlivesPredicate(lhs, rhs) in outlives { - match lhs.kind() { - ty::GenericArgKind::Lifetime(lhs) => delegate.sub_regions(rhs, lhs, span), - ty::GenericArgKind::Type(lhs) => delegate.register_ty_outlives(lhs, rhs, span), - ty::GenericArgKind::Const(_) => panic!("const outlives: {lhs:?}: {rhs:?}"), - } +fn register_region_constraints( + delegate: &D, + outlives: &[ty::OutlivesPredicate], + span: I::Span, +) where + D: SolverDelegate, + I: Interner, +{ + for &ty::OutlivesPredicate(lhs, rhs) in outlives { + match lhs.kind() { + ty::GenericArgKind::Lifetime(lhs) => delegate.sub_regions(rhs, lhs, span), + ty::GenericArgKind::Type(lhs) => delegate.register_ty_outlives(lhs, rhs, span), + ty::GenericArgKind::Const(_) => panic!("const outlives: {lhs:?}: {rhs:?}"), } } +} - fn register_new_opaque_types( - delegate: &D, - opaque_types: &[(ty::OpaqueTypeKey, I::Ty)], - span: I::Span, - ) { - for &(key, ty) in opaque_types { - let prev = delegate.register_hidden_type_in_storage(key, ty, span); - // We eagerly resolve inference variables when computing the query response. - // This can cause previously distinct opaque type keys to now be structurally equal. - // - // To handle this, we store any duplicate entries in a separate list to check them - // at the end of typeck/borrowck. We could alternatively eagerly equate the hidden - // types here. However, doing so is difficult as it may result in nested goals and - // any errors may make it harder to track the control flow for diagnostics. - if let Some(prev) = prev { - delegate.add_duplicate_opaque_type(key, prev, span); - } +fn register_new_opaque_types( + delegate: &D, + opaque_types: &[(ty::OpaqueTypeKey, I::Ty)], + span: I::Span, +) where + D: SolverDelegate, + I: Interner, +{ + for &(key, ty) in opaque_types { + let prev = delegate.register_hidden_type_in_storage(key, ty, span); + // We eagerly resolve inference variables when computing the query response. + // This can cause previously distinct opaque type keys to now be structurally equal. + // + // To handle this, we store any duplicate entries in a separate list to check them + // at the end of typeck/borrowck. We could alternatively eagerly equate the hidden + // types here. However, doing so is difficult as it may result in nested goals and + // any errors may make it harder to track the control flow for diagnostics. + if let Some(prev) = prev { + delegate.add_duplicate_opaque_type(key, prev, span); } } } @@ -274,7 +296,7 @@ where /// evaluating a goal. The `var_values` not only include the bound variables /// of the query input, but also contain all unconstrained inference vars /// created while evaluating this goal. -pub fn make_canonical_state( +pub fn make_canonical_state( delegate: &D, var_values: &[I::GenericArg], max_input_universe: ty::UniverseIndex, @@ -293,7 +315,7 @@ where // FIXME: needs to be pub to be accessed by downstream // `rustc_trait_selection::solve::inspect::analyse`. -pub fn instantiate_canonical_state>( +pub fn instantiate_canonical_state( delegate: &D, span: I::Span, param_env: I::ParamEnv, @@ -303,6 +325,7 @@ pub fn instantiate_canonical_state>( where D: SolverDelegate, I: Interner, + T: TypeFoldable, { // In case any fresh inference variables have been created between `state` // and the previous instantiation, extend `orig_values` for it. @@ -313,11 +336,11 @@ where ); let instantiation = - EvalCtxt::compute_query_response_instantiation_values(delegate, orig_values, &state, span); + compute_query_response_instantiation_values(delegate, orig_values, &state, span); let inspect::State { var_values, data } = delegate.instantiate_canonical(state, instantiation); - EvalCtxt::unify_query_var_values(delegate, param_env, orig_values, var_values, span); + unify_query_var_values(delegate, param_env, orig_values, var_values, span); data } diff --git a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs index 8f9b68dbac4..bb86357a85f 100644 --- a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs +++ b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs @@ -17,8 +17,10 @@ use rustc_type_ir::{ use tracing::{debug, instrument, trace}; use super::has_only_region_constraints; -use crate::canonical::canonicalizer::Canonicalizer; -use crate::canonical::response_no_constraints_raw; +use crate::canonical::{ + canonicalize_goal, canonicalize_response, instantiate_and_apply_query_response, + response_no_constraints_raw, +}; use crate::coherence; use crate::delegate::SolverDelegate; use crate::placeholder::BoundVarReplacer; @@ -465,8 +467,7 @@ where let opaque_types = self.delegate.clone_opaque_types_lookup_table(); let (goal, opaque_types) = eager_resolve_vars(self.delegate, (goal, opaque_types)); - let (orig_values, canonical_goal) = - Self::canonicalize_goal(self.delegate, goal, opaque_types); + let (orig_values, canonical_goal) = canonicalize_goal(self.delegate, goal, opaque_types); let canonical_result = self.search_graph.evaluate_goal( self.cx(), canonical_goal, @@ -481,7 +482,7 @@ where let has_changed = if !has_only_region_constraints(response) { HasChanged::Yes } else { HasChanged::No }; - let (normalization_nested_goals, certainty) = Self::instantiate_and_apply_query_response( + let (normalization_nested_goals, certainty) = instantiate_and_apply_query_response( self.delegate, goal.param_env, &orig_values, @@ -1319,10 +1320,9 @@ where outlives.0.as_region().is_none_or(|re| re != outlives.1) && unique.insert(*outlives) }); - let canonical = Canonicalizer::canonicalize_response( + let canonical = canonicalize_response( self.delegate, self.max_input_universe, - &mut Default::default(), Response { var_values, certainty, @@ -1557,7 +1557,7 @@ pub(super) fn evaluate_root_goal_for_proof_tree, let opaque_types = delegate.clone_opaque_types_lookup_table(); let (goal, opaque_types) = eager_resolve_vars(delegate, (goal, opaque_types)); - let (orig_values, canonical_goal) = EvalCtxt::canonicalize_goal(delegate, goal, opaque_types); + let (orig_values, canonical_goal) = canonicalize_goal(delegate, goal, opaque_types); let (canonical_result, final_revision) = delegate.cx().evaluate_root_goal_for_proof_tree_raw(canonical_goal); @@ -1574,7 +1574,7 @@ pub(super) fn evaluate_root_goal_for_proof_tree, Ok(response) => response, }; - let (normalization_nested_goals, _certainty) = EvalCtxt::instantiate_and_apply_query_response( + let (normalization_nested_goals, _certainty) = instantiate_and_apply_query_response( delegate, goal.param_env, &proof_tree.orig_values, -- cgit 1.4.1-3-g733a5