Skip to content

Commit 98bfd54

Browse files
lcnrlcnr
committed
eagerly normalize when adding goals
1 parent 13ce229 commit 98bfd54

9 files changed

Lines changed: 207 additions & 16 deletions

File tree

‎compiler/rustc_middle/src/ty/predicate.rs‎

Lines changed: 3 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -121,17 +121,14 @@ impl<'tcx> Predicate<'tcx> {
121121
#[inline]
122122
pub fn allow_normalization(self) -> bool {
123123
match self.kind().skip_binder() {
124-
PredicateKind::Clause(ClauseKind::WellFormed(_)) => false,
125-
// `NormalizesTo` is only used in the new solver, so this shouldn't
126-
// matter. Normalizing `term` would be 'wrong' however, as it changes whether
127-
// `normalizes-to(<T as Trait>::Assoc, <T as Trait>::Assoc)` holds.
128-
PredicateKind::NormalizesTo(..) => false,
124+
PredicateKind::Clause(ClauseKind::WellFormed(_))
125+
| PredicateKind::AliasRelate(..)
126+
| PredicateKind::NormalizesTo(..) => false,
129127
PredicateKind::Clause(ClauseKind::Trait(_))
130128
| PredicateKind::Clause(ClauseKind::RegionOutlives(_))
131129
| PredicateKind::Clause(ClauseKind::TypeOutlives(_))
132130
| PredicateKind::Clause(ClauseKind::Projection(_))
133131
| PredicateKind::Clause(ClauseKind::ConstArgHasType(..))
134-
| PredicateKind::AliasRelate(..)
135132
| PredicateKind::ObjectSafe(_)
136133
| PredicateKind::Subtype(_)
137134
| PredicateKind::Coerce(_)

‎compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs‎

Lines changed: 75 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -13,11 +13,14 @@ use rustc_middle::traits::solve::{
1313
inspect, CanonicalInput, CanonicalResponse, Certainty, PredefinedOpaquesData, QueryResult,
1414
};
1515
use rustc_middle::traits::specialization_graph;
16+
use rustc_middle::ty::AliasRelationDirection;
17+
use rustc_middle::ty::TypeFolder;
1618
use rustc_middle::ty::{
1719
self, InferCtxtLike, OpaqueTypeKey, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable,
1820
TypeVisitable, TypeVisitableExt, TypeVisitor,
1921
};
2022
use rustc_span::DUMMY_SP;
23+
use rustc_type_ir::fold::TypeSuperFoldable;
2124
use rustc_type_ir::{self as ir, CanonicalVarValues, Interner};
2225
use rustc_type_ir_macros::{Lift_Generic, TypeFoldable_Generic, TypeVisitable_Generic};
2326
use std::ops::ControlFlow;
@@ -455,13 +458,23 @@ impl<'a, 'tcx> EvalCtxt<'a, InferCtxt<'tcx>> {
455458
}
456459

457460
#[instrument(level = "trace", skip(self))]
458-
pub(super) fn add_normalizes_to_goal(&mut self, goal: Goal<'tcx, ty::NormalizesTo<'tcx>>) {
461+
pub(super) fn add_normalizes_to_goal(&mut self, mut goal: Goal<'tcx, ty::NormalizesTo<'tcx>>) {
462+
goal.predicate = goal
463+
.predicate
464+
.fold_with(&mut ReplaceAliasWithInfer { ecx: self, param_env: goal.param_env });
459465
self.inspect.add_normalizes_to_goal(self.infcx, self.max_input_universe, goal);
460466
self.nested_goals.normalizes_to_goals.push(goal);
461467
}
462468

463469
#[instrument(level = "debug", skip(self))]
464-
pub(super) fn add_goal(&mut self, source: GoalSource, goal: Goal<'tcx, ty::Predicate<'tcx>>) {
470+
pub(super) fn add_goal(
471+
&mut self,
472+
source: GoalSource,
473+
mut goal: Goal<'tcx, ty::Predicate<'tcx>>,
474+
) {
475+
goal.predicate = goal
476+
.predicate
477+
.fold_with(&mut ReplaceAliasWithInfer { ecx: self, param_env: goal.param_env });
465478
self.inspect.add_goal(self.infcx, self.max_input_universe, source, goal);
466479
self.nested_goals.goals.push((source, goal));
467480
}
@@ -1084,3 +1097,63 @@ impl<'tcx> EvalCtxt<'_, InferCtxt<'tcx>> {
10841097
});
10851098
}
10861099
}
1100+
1101+
/// Eagerly replace aliases with inference variables, emitting `AliasRelate`
1102+
/// goals, used when adding goals to the `EvalCtxt`. We compute the
1103+
/// `AliasRelate` goals before evaluating the actual goal to get all the
1104+
/// constraints we can.
1105+
///
1106+
/// This is a performance optimization to more eagerly detect cycles during trait
1107+
/// solving. See tests/ui/traits/next-solver/cycles/cycle-modulo-ambig-aliases.rs.
1108+
struct ReplaceAliasWithInfer<'me, 'a, 'tcx> {
1109+
ecx: &'me mut EvalCtxt<'a, InferCtxt<'tcx>>,
1110+
param_env: ty::ParamEnv<'tcx>,
1111+
}
1112+
1113+
impl<'tcx> TypeFolder<TyCtxt<'tcx>> for ReplaceAliasWithInfer<'_, '_, 'tcx> {
1114+
fn interner(&self) -> TyCtxt<'tcx> {
1115+
self.ecx.tcx()
1116+
}
1117+
1118+
fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
1119+
match *ty.kind() {
1120+
ty::Alias(..) if !ty.has_escaping_bound_vars() => {
1121+
let infer_ty = self.ecx.next_ty_infer();
1122+
let normalizes_to = ty::PredicateKind::AliasRelate(
1123+
ty.into(),
1124+
infer_ty.into(),
1125+
AliasRelationDirection::Equate,
1126+
);
1127+
self.ecx.add_goal(
1128+
GoalSource::Misc,
1129+
Goal::new(self.interner(), self.param_env, normalizes_to),
1130+
);
1131+
infer_ty
1132+
}
1133+
_ => ty.super_fold_with(self),
1134+
}
1135+
}
1136+
1137+
fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
1138+
match ct.kind() {
1139+
ty::ConstKind::Unevaluated(..) if !ct.has_escaping_bound_vars() => {
1140+
let infer_ct = self.ecx.next_const_infer(ct.ty());
1141+
let normalizes_to = ty::PredicateKind::AliasRelate(
1142+
ct.into(),
1143+
infer_ct.into(),
1144+
AliasRelationDirection::Equate,
1145+
);
1146+
self.ecx.add_goal(
1147+
GoalSource::Misc,
1148+
Goal::new(self.interner(), self.param_env, normalizes_to),
1149+
);
1150+
infer_ct
1151+
}
1152+
_ => ct.super_fold_with(self),
1153+
}
1154+
}
1155+
1156+
fn fold_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
1157+
if predicate.allow_normalization() { predicate.super_fold_with(self) } else { predicate }
1158+
}
1159+
}

‎tests/ui/coherence/coherence-overlap-unnormalizable-projection-1.next.stderr‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@ LL | impl<T> Trait for Box<T> {}
1212
| ^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `Box<_>`
1313
|
1414
= note: downstream crates may implement trait `WithAssoc<'a>` for type `std::boxed::Box<_>`
15-
= note: downstream crates may implement trait `WhereBound` for type `std::boxed::Box<<std::boxed::Box<_> as WithAssoc<'a>>::Assoc>`
15+
= note: downstream crates may implement trait `WhereBound` for type `std::boxed::Box<_>`
1616

1717
error: aborting due to 1 previous error
1818

‎tests/ui/coherence/occurs-check/opaques.next.stderr‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ error[E0282]: type annotations needed
1111
--> $DIR/opaques.rs:13:20
1212
|
1313
LL | pub fn cast<T>(x: Container<Alias<T>, T>) -> Container<T, T> {
14-
| ^ cannot infer type for associated type `<T as Trait<T>>::Assoc`
14+
| ^ cannot infer type
1515

1616
error: aborting due to 2 previous errors
1717

‎tests/ui/diagnostic_namespace/do_not_recommend/as_expression.next.stderr‎

Lines changed: 18 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,22 @@ LL | where
1616
LL | T: AsExpression<Self::SqlType>,
1717
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `Foo::check`
1818

19-
error: aborting due to 1 previous error
19+
error[E0277]: the trait bound `&str: AsExpression<Integer>` is not satisfied
20+
--> $DIR/as_expression.rs:57:15
21+
|
22+
LL | SelectInt.check("bar");
23+
| ^^^^^ the trait `AsExpression<Integer>` is not implemented for `&str`
24+
|
25+
= help: the trait `AsExpression<Text>` is implemented for `&str`
26+
= help: for that trait implementation, expected `Text`, found `Integer`
27+
28+
error[E0271]: type mismatch resolving `<&str as AsExpression<<SelectInt as Expression>::SqlType>>::Expression == _`
29+
--> $DIR/as_expression.rs:57:5
30+
|
31+
LL | SelectInt.check("bar");
32+
| ^^^^^^^^^^^^^^^^^^^^^^ types differ
33+
34+
error: aborting due to 3 previous errors
2035

21-
For more information about this error, try `rustc --explain E0277`.
36+
Some errors have detailed explanations: E0271, E0277.
37+
For more information about an error, try `rustc --explain E0271`.

‎tests/ui/diagnostic_namespace/do_not_recommend/as_expression.rs‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,7 @@ impl<T> Foo for T where T: Expression {}
5555

5656
fn main() {
5757
SelectInt.check("bar");
58-
//[next]~^ ERROR the trait bound `&str: AsExpression<<SelectInt as Expression>::SqlType>` is not satisfied
59-
//[current]~^^ ERROR the trait bound `&str: AsExpression<Integer>` is not satisfied
58+
//~^ ERROR the trait bound `&str: AsExpression<Integer>` is not satisfied
59+
//[next]~| the trait bound `&str: AsExpression<<SelectInt as Expression>::SqlType>` is not satisfied
60+
//[next]~| type mismatch
6061
}

‎tests/ui/traits/next-solver/canonical/const-region-infer-to-static-in-binder.stderr‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
1-
error[E0284]: type annotations needed: cannot satisfy `the constant `{ || {} }` can be evaluated`
1+
error[E0284]: type annotations needed: cannot satisfy `{ || {} } == _`
22
--> $DIR/const-region-infer-to-static-in-binder.rs:4:10
33
|
44
LL | struct X<const FN: fn() = { || {} }>;
5-
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot satisfy `the constant `{ || {} }` can be evaluated`
5+
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot satisfy `{ || {} } == _`
66

77
error: using function pointers as const generic parameters is forbidden
88
--> $DIR/const-region-infer-to-static-in-binder.rs:4:20

‎tests/ui/traits/next-solver/cycles/cycle-modulo-ambig-aliases.rs‎

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
//@ compile-flags: -Znext-solver
2+
3+
// A regression test for #125269. We previously ended up
4+
// recursively proving `&<_ as SpeciesPackedElem>::Assoc: Typed`
5+
// for all aliases which ended up causing exponential blowup.
6+
//
7+
// This has been fixed by eagerly normalizing the associated
8+
// type before computing the nested goals, resulting in an
9+
// immediate inductive cycle.
10+
11+
pub trait Typed {}
12+
13+
pub struct SpeciesCases<E>(E);
14+
15+
pub trait SpeciesPackedElim {
16+
type Ogre;
17+
type Cyclops;
18+
type Wendigo;
19+
type Cavetroll;
20+
type Mountaintroll;
21+
type Swamptroll;
22+
type Dullahan;
23+
type Werewolf;
24+
type Occultsaurok;
25+
type Mightysaurok;
26+
type Slysaurok;
27+
type Mindflayer;
28+
type Minotaur;
29+
type Tidalwarrior;
30+
type Yeti;
31+
type Harvester;
32+
type Blueoni;
33+
type Redoni;
34+
type Cultistwarlord;
35+
type Cultistwarlock;
36+
type Huskbrute;
37+
type Tursus;
38+
type Gigasfrost;
39+
type AdletElder;
40+
type SeaBishop;
41+
type HaniwaGeneral;
42+
type TerracottaBesieger;
43+
type TerracottaDemolisher;
44+
type TerracottaPunisher;
45+
type TerracottaPursuer;
46+
type Cursekeeper;
47+
}
48+
49+
impl<'b, E: SpeciesPackedElim> Typed for &'b SpeciesCases<E>
50+
where
51+
&'b E::Ogre: Typed,
52+
&'b E::Cyclops: Typed,
53+
&'b E::Wendigo: Typed,
54+
&'b E::Cavetroll: Typed,
55+
&'b E::Mountaintroll: Typed,
56+
&'b E::Swamptroll: Typed,
57+
&'b E::Dullahan: Typed,
58+
&'b E::Werewolf: Typed,
59+
&'b E::Occultsaurok: Typed,
60+
&'b E::Mightysaurok: Typed,
61+
&'b E::Slysaurok: Typed,
62+
&'b E::Mindflayer: Typed,
63+
&'b E::Minotaur: Typed,
64+
&'b E::Tidalwarrior: Typed,
65+
&'b E::Yeti: Typed,
66+
&'b E::Harvester: Typed,
67+
&'b E::Blueoni: Typed,
68+
&'b E::Redoni: Typed,
69+
&'b E::Cultistwarlord: Typed,
70+
&'b E::Cultistwarlock: Typed,
71+
&'b E::Huskbrute: Typed,
72+
&'b E::Tursus: Typed,
73+
&'b E::Gigasfrost: Typed,
74+
&'b E::AdletElder: Typed,
75+
&'b E::SeaBishop: Typed,
76+
&'b E::HaniwaGeneral: Typed,
77+
&'b E::TerracottaBesieger: Typed,
78+
&'b E::TerracottaDemolisher: Typed,
79+
&'b E::TerracottaPunisher: Typed,
80+
&'b E::TerracottaPursuer: Typed,
81+
&'b E::Cursekeeper: Typed,
82+
{}
83+
84+
fn foo<T: Typed>() {}
85+
86+
fn main() {
87+
foo::<&_>();
88+
//~^ ERROR overflow evaluating the requirement `&_: Typed`
89+
}

‎tests/ui/traits/next-solver/cycles/cycle-modulo-ambig-aliases.stderr‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
error[E0275]: overflow evaluating the requirement `&_: Typed`
2+
--> $DIR/cycle-modulo-ambig-aliases.rs:87:11
3+
|
4+
LL | foo::<&_>();
5+
| ^^
6+
|
7+
note: required by a bound in `foo`
8+
--> $DIR/cycle-modulo-ambig-aliases.rs:84:11
9+
|
10+
LL | fn foo<T: Typed>() {}
11+
| ^^^^^ required by this bound in `foo`
12+
13+
error: aborting due to 1 previous error
14+
15+
For more information about this error, try `rustc --explain E0275`.

0 commit comments

Comments
 (0)