diff options
13 files changed, 155 insertions, 152 deletions
diff --git a/Cargo.lock b/Cargo.lock index cfdd873e80f..ee6726eae51 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -4158,7 +4158,6 @@ dependencies = [ "rustc_data_structures", "rustc_index", "rustc_macros", - "rustc_serialize", "rustc_type_ir", "rustc_type_ir_macros", "tracing", diff --git a/compiler/rustc_middle/src/ty/predicate.rs b/compiler/rustc_middle/src/ty/predicate.rs index 02e316dfc3d..551d816941b 100644 --- a/compiler/rustc_middle/src/ty/predicate.rs +++ b/compiler/rustc_middle/src/ty/predicate.rs @@ -121,11 +121,10 @@ impl<'tcx> Predicate<'tcx> { /// unsoundly accept some programs. See #91068. #[inline] pub fn allow_normalization(self) -> bool { - // Keep this in sync with the one in `rustc_type_ir::inherent`! match self.kind().skip_binder() { - PredicateKind::Clause(ClauseKind::WellFormed(_)) - | PredicateKind::AliasRelate(..) - | PredicateKind::NormalizesTo(..) => false, + PredicateKind::Clause(ClauseKind::WellFormed(_)) | PredicateKind::AliasRelate(..) => { + false + } PredicateKind::Clause(ClauseKind::Trait(_)) | PredicateKind::Clause(ClauseKind::HostEffect(..)) | PredicateKind::Clause(ClauseKind::RegionOutlives(_)) @@ -137,6 +136,7 @@ impl<'tcx> Predicate<'tcx> { | PredicateKind::Coerce(_) | PredicateKind::Clause(ClauseKind::ConstEvaluatable(_)) | PredicateKind::ConstEquate(_, _) + | PredicateKind::NormalizesTo(..) | PredicateKind::Ambiguous => true, } } diff --git a/compiler/rustc_next_trait_solver/Cargo.toml b/compiler/rustc_next_trait_solver/Cargo.toml index 63aa60f2f26..36d53901d9e 100644 --- a/compiler/rustc_next_trait_solver/Cargo.toml +++ b/compiler/rustc_next_trait_solver/Cargo.toml @@ -9,7 +9,6 @@ derive-where = "1.2.7" rustc_data_structures = { path = "../rustc_data_structures", optional = true } rustc_index = { path = "../rustc_index", default-features = false } rustc_macros = { path = "../rustc_macros", optional = true } -rustc_serialize = { path = "../rustc_serialize", optional = true } rustc_type_ir = { path = "../rustc_type_ir", default-features = false } rustc_type_ir_macros = { path = "../rustc_type_ir_macros" } tracing = "0.1" @@ -20,7 +19,6 @@ default = ["nightly"] nightly = [ "dep:rustc_data_structures", "dep:rustc_macros", - "dep:rustc_serialize", "rustc_index/nightly", "rustc_type_ir/nightly", ] diff --git a/compiler/rustc_next_trait_solver/src/solve/alias_relate.rs b/compiler/rustc_next_trait_solver/src/solve/alias_relate.rs index 0fc313e33b3..f7bd4600943 100644 --- a/compiler/rustc_next_trait_solver/src/solve/alias_relate.rs +++ b/compiler/rustc_next_trait_solver/src/solve/alias_relate.rs @@ -16,6 +16,7 @@ //! relate them structurally. use rustc_type_ir::inherent::*; +use rustc_type_ir::solve::GoalSource; use rustc_type_ir::{self as ty, Interner}; use tracing::{instrument, trace}; @@ -49,7 +50,10 @@ where // Structurally normalize the lhs. let lhs = if let Some(alias) = lhs.to_alias_term() { let term = self.next_term_infer_of_kind(lhs); - self.add_normalizes_to_goal(goal.with(cx, ty::NormalizesTo { alias, term })); + self.add_goal( + GoalSource::TypeRelating, + goal.with(cx, ty::NormalizesTo { alias, term }), + ); term } else { lhs @@ -58,7 +62,10 @@ where // Structurally normalize the rhs. let rhs = if let Some(alias) = rhs.to_alias_term() { let term = self.next_term_infer_of_kind(rhs); - self.add_normalizes_to_goal(goal.with(cx, ty::NormalizesTo { alias, term })); + self.add_goal( + GoalSource::TypeRelating, + goal.with(cx, ty::NormalizesTo { alias, term }), + ); term } else { rhs 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 index d56b0e5847e..04f80a056f9 100644 --- a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs +++ b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs @@ -22,7 +22,7 @@ use tracing::{debug, instrument, trace}; use crate::canonicalizer::Canonicalizer; use crate::delegate::SolverDelegate; use crate::resolve::EagerResolver; -use crate::solve::eval_ctxt::{CurrentGoalKind, NestedGoals}; +use crate::solve::eval_ctxt::CurrentGoalKind; use crate::solve::{ CanonicalInput, CanonicalResponse, Certainty, EvalCtxt, ExternalConstraintsData, Goal, MaybeCause, NestedNormalizationGoals, NoSolution, PredefinedOpaquesData, QueryInput, @@ -112,13 +112,9 @@ where // by `try_evaluate_added_goals()`. let (certainty, normalization_nested_goals) = match self.current_goal_kind { CurrentGoalKind::NormalizesTo => { - let NestedGoals { normalizes_to_goals, goals } = - std::mem::take(&mut self.nested_goals); - if cfg!(debug_assertions) { - assert!(normalizes_to_goals.is_empty()); - if goals.is_empty() { - assert!(matches!(goals_certainty, Certainty::Yes)); - } + let goals = std::mem::take(&mut self.nested_goals); + if goals.is_empty() { + assert!(matches!(goals_certainty, Certainty::Yes)); } (certainty, NestedNormalizationGoals(goals)) } 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 9994c85d0d0..27ca8787db5 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 @@ -1,8 +1,8 @@ +use std::mem; use std::ops::ControlFlow; -use derive_where::derive_where; #[cfg(feature = "nightly")] -use rustc_macros::{Decodable_NoContext, Encodable_NoContext, HashStable_NoContext}; +use rustc_macros::HashStable_NoContext; use rustc_type_ir::data_structures::{HashMap, HashSet, ensure_sufficient_stack}; use rustc_type_ir::fast_reject::DeepRejectCtxt; use rustc_type_ir::inherent::*; @@ -14,7 +14,6 @@ use rustc_type_ir::{ TypeSuperFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor, TypingMode, }; -use rustc_type_ir_macros::{Lift_Generic, TypeFoldable_Generic, TypeVisitable_Generic}; use tracing::{instrument, trace}; use crate::coherence; @@ -114,7 +113,7 @@ where pub(super) search_graph: &'a mut SearchGraph<D>, - nested_goals: NestedGoals<I>, + nested_goals: Vec<(GoalSource, Goal<I, I::Predicate>)>, pub(super) origin_span: I::Span, @@ -129,38 +128,6 @@ where pub(super) inspect: ProofTreeBuilder<D>, } -#[derive_where(Clone, Debug, Default; I: Interner)] -#[derive(TypeVisitable_Generic, TypeFoldable_Generic, Lift_Generic)] -#[cfg_attr( - feature = "nightly", - derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext) -)] -struct NestedGoals<I: Interner> { - /// These normalizes-to goals are treated specially during the evaluation - /// loop. In each iteration we take the RHS of the projection, replace it with - /// a fresh inference variable, and only after evaluating that goal do we - /// equate the fresh inference variable with the actual RHS of the predicate. - /// - /// This is both to improve caching, and to avoid using the RHS of the - /// projection predicate to influence the normalizes-to candidate we select. - /// - /// Forgetting to replace the RHS with a fresh inference variable when we evaluate - /// this goal results in an ICE.. - pub normalizes_to_goals: Vec<Goal<I, ty::NormalizesTo<I>>>, - /// The rest of the goals which have not yet processed or remain ambiguous. - pub goals: Vec<(GoalSource, Goal<I, I::Predicate>)>, -} - -impl<I: Interner> NestedGoals<I> { - fn new() -> Self { - Self { normalizes_to_goals: Vec::new(), goals: Vec::new() } - } - - fn is_empty(&self) -> bool { - self.normalizes_to_goals.is_empty() && self.goals.is_empty() - } -} - #[derive(PartialEq, Eq, Debug, Hash, Clone, Copy)] #[cfg_attr(feature = "nightly", derive(HashStable_NoContext))] pub enum GenerateProofTree { @@ -332,7 +299,7 @@ where let mut ecx = EvalCtxt { delegate, search_graph: &mut search_graph, - nested_goals: NestedGoals::new(), + nested_goals: Default::default(), inspect: ProofTreeBuilder::new_maybe_root(generate_proof_tree), // Only relevant when canonicalizing the response, @@ -385,7 +352,7 @@ where predefined_opaques_in_body: input.predefined_opaques_in_body, max_input_universe: canonical_input.canonical.max_universe, search_graph, - nested_goals: NestedGoals::new(), + nested_goals: Default::default(), origin_span: I::Span::dummy(), tainted: Ok(()), inspect: canonical_goal_evaluation.new_goal_evaluation_step(var_values), @@ -629,78 +596,83 @@ where /// Goals for the next step get directly added to the nested goals of the `EvalCtxt`. fn evaluate_added_goals_step(&mut self) -> Result<Option<Certainty>, NoSolution> { let cx = self.cx(); - let mut goals = core::mem::take(&mut self.nested_goals); - // If this loop did not result in any progress, what's our final certainty. let mut unchanged_certainty = Some(Certainty::Yes); - for goal in goals.normalizes_to_goals { - // Replace the goal with an unconstrained infer var, so the - // RHS does not affect projection candidate assembly. - let unconstrained_rhs = self.next_term_infer_of_kind(goal.predicate.term); - let unconstrained_goal = goal.with( - cx, - ty::NormalizesTo { alias: goal.predicate.alias, term: unconstrained_rhs }, - ); - - let (NestedNormalizationGoals(nested_goals), _, certainty) = self.evaluate_goal_raw( - GoalEvaluationKind::Nested, - GoalSource::TypeRelating, - unconstrained_goal, - )?; - // Add the nested goals from normalization to our own nested goals. - trace!(?nested_goals); - goals.goals.extend(nested_goals); - - // Finally, equate the goal's RHS with the unconstrained var. + for (source, goal) in mem::take(&mut self.nested_goals) { + // We treat normalizes-to goals specially here. In each iteration we take the + // RHS of the projection, replace it with a fresh inference variable, and only + // after evaluating that goal do we equate the fresh inference variable with the + // actual RHS of the predicate. // - // SUBTLE: - // We structurally relate aliases here. This is necessary - // as we otherwise emit a nested `AliasRelate` goal in case the - // returned term is a rigid alias, resulting in overflow. + // This is both to improve caching, and to avoid using the RHS of the + // projection predicate to influence the normalizes-to candidate we select. // - // It is correct as both `goal.predicate.term` and `unconstrained_rhs` - // start out as an unconstrained inference variable so any aliases get - // fully normalized when instantiating it. - // - // FIXME: Strictly speaking this may be incomplete if the normalized-to - // type contains an ambiguous alias referencing bound regions. We should - // consider changing this to only use "shallow structural equality". - self.eq_structurally_relating_aliases( - goal.param_env, - goal.predicate.term, - unconstrained_rhs, - )?; - - // We only look at the `projection_ty` part here rather than - // looking at the "has changed" return from evaluate_goal, - // because we expect the `unconstrained_rhs` part of the predicate - // to have changed -- that means we actually normalized successfully! - let with_resolved_vars = self.resolve_vars_if_possible(goal); - if goal.predicate.alias != with_resolved_vars.predicate.alias { - unchanged_certainty = None; - } - - match certainty { - Certainty::Yes => {} - Certainty::Maybe(_) => { - self.nested_goals.normalizes_to_goals.push(with_resolved_vars); - unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); + // Forgetting to replace the RHS with a fresh inference variable when we evaluate + // this goal results in an ICE. + if let Some(pred) = goal.predicate.as_normalizes_to() { + // We should never encounter higher-ranked normalizes-to goals. + let pred = pred.no_bound_vars().unwrap(); + // Replace the goal with an unconstrained infer var, so the + // RHS does not affect projection candidate assembly. + let unconstrained_rhs = self.next_term_infer_of_kind(pred.term); + let unconstrained_goal = + goal.with(cx, ty::NormalizesTo { alias: pred.alias, term: unconstrained_rhs }); + + let (NestedNormalizationGoals(nested_goals), _, certainty) = + self.evaluate_goal_raw(GoalEvaluationKind::Nested, source, unconstrained_goal)?; + // Add the nested goals from normalization to our own nested goals. + trace!(?nested_goals); + self.nested_goals.extend(nested_goals); + + // Finally, equate the goal's RHS with the unconstrained var. + // + // SUBTLE: + // We structurally relate aliases here. This is necessary + // as we otherwise emit a nested `AliasRelate` goal in case the + // returned term is a rigid alias, resulting in overflow. + // + // It is correct as both `goal.predicate.term` and `unconstrained_rhs` + // start out as an unconstrained inference variable so any aliases get + // fully normalized when instantiating it. + // + // FIXME: Strictly speaking this may be incomplete if the normalized-to + // type contains an ambiguous alias referencing bound regions. We should + // consider changing this to only use "shallow structural equality". + self.eq_structurally_relating_aliases( + goal.param_env, + pred.term, + unconstrained_rhs, + )?; + + // We only look at the `projection_ty` part here rather than + // looking at the "has changed" return from evaluate_goal, + // because we expect the `unconstrained_rhs` part of the predicate + // to have changed -- that means we actually normalized successfully! + let with_resolved_vars = self.resolve_vars_if_possible(goal); + if pred.alias != goal.predicate.as_normalizes_to().unwrap().skip_binder().alias { + unchanged_certainty = None; } - } - } - for (source, goal) in goals.goals { - let (has_changed, certainty) = - self.evaluate_goal(GoalEvaluationKind::Nested, source, goal)?; - if has_changed == HasChanged::Yes { - unchanged_certainty = None; - } + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => { + self.nested_goals.push((source, with_resolved_vars)); + unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); + } + } + } else { + let (has_changed, certainty) = + self.evaluate_goal(GoalEvaluationKind::Nested, source, goal)?; + if has_changed == HasChanged::Yes { + unchanged_certainty = None; + } - match certainty { - Certainty::Yes => {} - Certainty::Maybe(_) => { - self.nested_goals.goals.push((source, goal)); - unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => { + self.nested_goals.push((source, goal)); + unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); + } } } } @@ -717,23 +689,12 @@ where self.delegate.cx() } - #[instrument(level = "trace", skip(self))] - pub(super) fn add_normalizes_to_goal(&mut self, mut goal: Goal<I, ty::NormalizesTo<I>>) { - goal.predicate = goal.predicate.fold_with(&mut ReplaceAliasWithInfer::new( - self, - GoalSource::TypeRelating, - goal.param_env, - )); - self.inspect.add_normalizes_to_goal(self.delegate, self.max_input_universe, goal); - self.nested_goals.normalizes_to_goals.push(goal); - } - #[instrument(level = "debug", skip(self))] pub(super) fn add_goal(&mut self, source: GoalSource, mut goal: Goal<I, I::Predicate>) { goal.predicate = goal.predicate.fold_with(&mut ReplaceAliasWithInfer::new(self, source, goal.param_env)); self.inspect.add_goal(self.delegate, self.max_input_universe, source, goal); - self.nested_goals.goals.push((source, goal)); + self.nested_goals.push((source, goal)); } #[instrument(level = "trace", skip(self, goals))] 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 6a8e0790f7c..f22b275bc44 100644 --- a/compiler/rustc_next_trait_solver/src/solve/inspect/build.rs +++ b/compiler/rustc_next_trait_solver/src/solve/inspect/build.rs @@ -412,20 +412,6 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> ProofTreeBuilder<D> { } } - pub(crate) fn add_normalizes_to_goal( - &mut self, - delegate: &D, - max_input_universe: ty::UniverseIndex, - goal: Goal<I, ty::NormalizesTo<I>>, - ) { - self.add_goal( - delegate, - max_input_universe, - GoalSource::TypeRelating, - goal.with(delegate.cx(), goal.predicate), - ); - } - pub(crate) fn add_goal( &mut self, delegate: &D, diff --git a/compiler/rustc_type_ir/src/inherent.rs b/compiler/rustc_type_ir/src/inherent.rs index 417803e75ea..9b066b6869f 100644 --- a/compiler/rustc_type_ir/src/inherent.rs +++ b/compiler/rustc_type_ir/src/inherent.rs @@ -442,6 +442,14 @@ pub trait Predicate<I: Interner<Predicate = Self>>: { fn as_clause(self) -> Option<I::Clause>; + fn as_normalizes_to(self) -> Option<ty::Binder<I, ty::NormalizesTo<I>>> { + let kind = self.kind(); + match kind.skip_binder() { + ty::PredicateKind::NormalizesTo(pred) => Some(kind.rebind(pred)), + _ => None, + } + } + // FIXME: Eventually uplift the impl out of rustc and make this defaulted. fn allow_normalization(self) -> bool; } diff --git a/tests/ui/diagnostic_namespace/do_not_recommend/as_expression.next.stderr b/tests/ui/diagnostic_namespace/do_not_recommend/as_expression.next.stderr index 6170250992c..8178f54b2aa 100644 --- a/tests/ui/diagnostic_namespace/do_not_recommend/as_expression.next.stderr +++ b/tests/ui/diagnostic_namespace/do_not_recommend/as_expression.next.stderr @@ -18,13 +18,16 @@ LL | where LL | T: AsExpression<Self::SqlType>, | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `Foo::check` -error[E0271]: type mismatch resolving `Integer == Text` +error[E0277]: the trait bound `&str: AsExpression<Integer>` is not satisfied --> $DIR/as_expression.rs:56:5 | LL | SelectInt.check("bar"); - | ^^^^^^^^^^^^^^^^^^^^^^ types differ + | ^^^^^^^^^^^^^^^^^^^^^^ the trait `AsExpression<Integer>` is not implemented for `&str` + | + = help: the trait `AsExpression<Integer>` is not implemented for `&str` + but trait `AsExpression<Text>` is implemented for it + = help: for that trait implementation, expected `Text`, found `Integer` error: aborting due to 2 previous errors -Some errors have detailed explanations: E0271, E0277. -For more information about an error, try `rustc --explain E0271`. +For more information about this error, try `rustc --explain E0277`. diff --git a/tests/ui/diagnostic_namespace/do_not_recommend/as_expression.rs b/tests/ui/diagnostic_namespace/do_not_recommend/as_expression.rs index 673adb82870..86f39e43484 100644 --- a/tests/ui/diagnostic_namespace/do_not_recommend/as_expression.rs +++ b/tests/ui/diagnostic_namespace/do_not_recommend/as_expression.rs @@ -55,5 +55,5 @@ impl<T> Foo for T where T: Expression {} fn main() { SelectInt.check("bar"); //~^ ERROR the trait bound `&str: AsExpression<Integer>` is not satisfied - //[next]~| ERROR type mismatch + //[next]~| ERROR the trait bound `&str: AsExpression<Integer>` is not satisfied } diff --git a/tests/ui/traits/next-solver/normalize/eager-norm-pre-normalizes-to.rs b/tests/ui/traits/next-solver/normalize/eager-norm-pre-normalizes-to.rs new file mode 100644 index 00000000000..ea18ac54c05 --- /dev/null +++ b/tests/ui/traits/next-solver/normalize/eager-norm-pre-normalizes-to.rs @@ -0,0 +1,44 @@ +//@ check-pass +//@ compile-flags: -Znext-solver + +// A regression test for trait-system-refactor-initiative#184. +// +// When adding nested goals we replace aliases with infer vars +// and add `AliasRelate` goals to constrain them. When doing this +// for `NormalizesTo` goals, we then first tries to prove the +// `NormalizesTo` goal and then normalized the nested aliases. + +trait Trait<T> { + type Assoc; +} +impl<T, U> Trait<U> for T { + type Assoc = (); +} + +trait Id { + type This; +} +impl<T> Id for T { + type This = T; +} +trait Relate<T> { + type Alias; +} +impl<T, U> Relate<U> for T { + type Alias = <T as Trait<<U as Id>::This>>::Assoc; +} + + +fn guide_me<T: Trait<u32>>() { + // Normalizing `<T as Relate<i32>>::Alias` relates the associated type with an unconstrained + // term. This resulted in a `NormalizesTo(<T as Trait<<U as Id>::This>>::Assoc, ?x)` goal. + // We replace `<i32 as Id>::This` with an infer var `?y`, resulting in the following goals: + // - `NormalizesTo(<T as Trait<?y>::Assoc, ?x)` + // - `AliasRelate(<i32 as Id>::This, ?y)` + // + // When proving the `NormalizesTo` goal first, we incompletely constrain `?y` to `u32`, + // causing an unexpected type mismatch. + let _: <T as Relate<i32>>::Alias; +} + +fn main() {} diff --git a/tests/ui/traits/next-solver/normalize/normalize-allow-too-many-vars.rs b/tests/ui/traits/next-solver/normalize/normalize-allow-too-many-vars.rs index 5284220ac38..3150d9a88d0 100644 --- a/tests/ui/traits/next-solver/normalize/normalize-allow-too-many-vars.rs +++ b/tests/ui/traits/next-solver/normalize/normalize-allow-too-many-vars.rs @@ -1,4 +1,5 @@ //@ check-pass +//@ compile-flags: -Znext-solver // When canonicalizing a response in the trait solver, we bail with overflow // if there are too many non-region inference variables. Doing so in normalizes-to diff --git a/tests/ui/type-alias-impl-trait/issue-84660-unsoundness.rs b/tests/ui/type-alias-impl-trait/issue-84660-unsoundness.rs index 4391bf01dc9..7a540d2a574 100644 --- a/tests/ui/type-alias-impl-trait/issue-84660-unsoundness.rs +++ b/tests/ui/type-alias-impl-trait/issue-84660-unsoundness.rs @@ -22,7 +22,7 @@ impl<In, Out> Trait<Bar, In> for Out { type Out = Out; #[define_opaque(Bar)] fn convert(_i: In) -> Self::Out { - //[next]~^ ERROR: cannot satisfy `Bar == _` + //[next]~^ ERROR: type annotations needed: cannot satisfy `Bar == _` //[current]~^^ ERROR: item does not constrain `Bar::{opaque#0}` unreachable!(); } |