global where-bounds normalization issue

[lcnr]

affects binius_field https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/crater.20triage.20.3A3/near/553949363. Thanks @lqd ❤️

There are 3 different issues here, make sure the remaining ones are also tracked.

#![feature(rustc_attrs)]
#![expect(internal_features)]
#![rustc_no_implicit_bounds]

pub trait Bound {}
impl Bound for u8 {}

pub trait Proj {
    type Assoc;
}
impl<U: Bound> Proj for U {
    type Assoc = U;
}
impl Proj for MyField {
    type Assoc = u8;
}

pub trait Field: Proj<Assoc: Bound + 'static> {}

struct MyField;
impl Field for MyField {}

trait IdReqField {
    type This;
}
impl<F: Field> IdReqField for F {
    type This = F;
}

fn foo()
where
    <MyField as IdReqField>::This: Field,
{
}

[ShoyuVanilla]

While normalizing the predicate <MyField as IdReqField>::This: Field, nested goal <MyField as Proj>::Assoc NormalizesTo ?t is evaluated and the impl candidates impl Proj for MyField and impl<U: Bound> Proj for U are probed.

Of course, the later one should bailed out here:
https://github.com/rust-lang/rust/blob/b25b6eab7fae8ab1618da45d41f017d6bc186f5b/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs#L232-L236
and thus shouldn't be included to the candidates.

But while evaluating down nested and nested goals, the nested normalization goal MyField: Field is added and the super outlives bound of Field in pub trait Field: Proj<Assoc: Bound + 'static> {}, which is roughly a <_ as Proj>::Assoc: 'static as a nested goal in the following line:
https://github.com/rust-lang/rust/blob/b25b6eab7fae8ab1618da45d41f017d6bc186f5b/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs#L111-L116
And since it contains alias type <_ as Proj>::Assoc, it again pushes an extra nested goal for alias eq relation between the alias type and a new inference var.
Some nested goal from it causes the cycle with the previous search graph and that makes the probe for impl<U: Bound> Proj for U return overflowed maybe result instead of NoSolution and thus it doesn't bailed out. That causes the ambiguity error.

This feels very complex and confusing to me, but I guess the most problematic part of this issue is the special elaboration of outlives goal, as replacing the 'static bound with other bounds removes the error.
I think that the nested goals derived from the outlives goals with alias types by folding with RelpaceAliasWithInfer are not much intended, as the derived nested goals are not outlives goals but alias relate ones the ones derived from them.
So, I've tried adding a method add_goal_without_normalization to EvalCtxt and replace the previous normalized one from https://github.com/rust-lang/rust/blob/b25b6eab7fae8ab1618da45d41f017d6bc186f5b/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs#L111-L116 and confirmed that the issue is fixed but this doesn't feel so right to me as well 😅

[lcnr]

So the goal which ends up with incorrect overflow is <MyField as Proj>::Assoc NormalizesTo ?t?

An the reason it does is https://github.com/rust-lang/rust/blob/66bc5a43e55eae14a2ec70b11004c88072fe7f02/compiler/rustc_type_ir/src/search_graph/mod.rs#L1367-L1374? Does commenting out this code cause this to compile as expected?

And since it contains alias type <_ as Proj>::Assoc, it again pushes an extra nested goal for alias eq relation between the alias type and a new inference var.
Some nested goal from it causes the cycle with the previous search graph and that makes the probe for impl<U: Bound> Proj for U return overflowed maybe result instead of NoSolution and thus it doesn't bailed out. That causes the ambiguity error.

I don't get what you mean with that 😅

[ShoyuVanilla]

So the goal which ends up with incorrect overflow is <MyField as Proj>::Assoc NormalizesTo ?t?

The incorrect overflow comes from the cycle, as the following same input met twice while solving nested subgoals:

rustc_type_ir::search_graph::evaluate_goal input=CanonicalQueryInput { canonical: Canonical { value: QueryInput { goal: Goal { param_env: ParamEnv { caller_bounds: [Binder { value: TraitPredicate(<<MyField as IdReqField>::This as Field>, polarity:Positive), bound_vars: [] }, Binder { value: OutlivesPredicate(Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [MyField], def_id: DefId(0:17 ~ issue_257[1041]::IdReqField::This), .. })], def_id: DefId(0:6 ~ issue_257[1041]::Proj::Assoc), .. }), 'static), bound_vars: [] }, Binder { value: TraitPredicate(<<<MyField as IdReqField>::This as Proj>::Assoc as Bound>, polarity:Positive), bound_vars: [] }, Binder { value: TraitPredicate(<<MyField as IdReqField>::This as Proj>, polarity:Positive), bound_vars: [] }] }, predicate: Binder { value: AliasRelate(Term::Ty(Alias(Projection, AliasTy { args: [MyField], def_id: DefId(0:17 ~ issue_257[1041]::IdReqField::This), .. })), Equate, Term::Ty(^c_0)), bound_vars: [] } }, predefined_opaques_in_body: [] }, max_universe: U0, variables: [Ty { ui: U0, sub_root: 0 }] }, typing_mode: Analysis { defining_opaque_types_and_generators: [] } }, step_kind_from_parent=Inductive

The predicate part is:
Binder { value: AliasRelate(Term::Ty(Alias(Projection, AliasTy { args: [MyField], def_id: DefId(0:17 ~ issue_257[1041]::IdReqField::This), .. })), Equate, Term::Ty(^c_0)), bound_vars: [] } }, predefined_opaques_in_body: [] }, max_universe: U0, variables: [Ty { ui: U0, sub_root: 0 }] }, typing_mode: Analysis { defining_opaque_types_and_generators: [] } }

An the reason it does is https://github.com/rust-lang/rust/blob/66bc5a43e55eae14a2ec70b11004c88072fe7f02/compiler/rustc_type_ir/src/search_graph/mod.rs#L1367-L1374? Does commenting out this code cause this to compile as expected?

I haven't tried with those lines but as the overflow comes from the cycle, the relevant lines would be
https://github.com/rust-lang/rust/blob/66bc5a43e55eae14a2ec70b11004c88072fe7f02/compiler/rustc_type_ir/src/search_graph/mod.rs#L1271-L1275
but I think we can't comment out them as doing so will cause literally an infinite recursion 😅

I don't get what you mean with that 😅

My terms are not so precise, sorry 😅 I mean, when adding the trait predicate MyField: Field as a subgoal, it's super outlives bound <_ as Proj>::Assoc: 'static is added as well in https://github.com/rust-lang/rust/blob/66bc5a43e55eae14a2ec70b11004c88072fe7f02/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs#L111-L116
And I think that the original intention for those lines might have been adding outlives goal only, but as the goal <_ as Proj>::Assoc: 'static contains an alias type <_ as Proj>::Assoc, it adds extra an AliasRelate goal in https://github.com/rust-lang/rust/blob/66bc5a43e55eae14a2ec70b11004c88072fe7f02/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs#L761-L762 and https://github.com/rust-lang/rust/blob/66bc5a43e55eae14a2ec70b11004c88072fe7f02/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs#L1428-L1436.
And while evaluating this AliasRelate goal and its subgoals, we again start probing impl candidates, so I feel that might be the root cause of the cycle.
So I have tried adding super outlives goals without normalizing alias types and it worked, but I'm not sure it may cause other weird issues like hanging over an alias type.

[ShoyuVanilla]

Does commenting out this code cause this to compile as expected?

Oh, this worked, so the cycle might not the root cause, but some invalid ambiguity from before might be the culprit 😅

[lcnr]

So I have tried adding super outlives goals without normalizing alias types and it worked, but I'm not sure it may cause other weird issues like hanging over an alias type.

I think we could limit the super outlives goals to only return goals for the current self type. This check only really exits as a temporary measure to make it harder to hit an unsoundness.

Given that it's caused by the "tainting" of provisional cache entries here, that doesn't seem, necessary and we should somehow avoid forcing MyField: Field to ambiguity.

---

🤔

So the reason normalizing <MyField as Proj>::Assoc participates in the cycle and has a "proper usage" of a cycle head (which then forces it to ambiguity) is that when considering the impl<U: Bound> Proj for U we try to use the elaborated <<MyField as IdReqField>::This as Proj>::Assoc: Bound where-clause. Normalizing that one then encounters a cycle.

For the trait solver to know that this where-bound does not apply it needs to normalize <<MyField as IdReqField>::This as Proj>::Assoc to a rigid alias.

I don't know whether forcing ambiguity is currently actually necessary to avoid any specific hangs we know about, so we could try to remove that hack and see what breaks 🤔