Skip to content

candidate selection for normalization and trait goals disagree #133044

New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Open
lcnr opened this issue Nov 14, 2024 · 3 comments
Open

candidate selection for normalization and trait goals disagree #133044

lcnr opened this issue Nov 14, 2024 · 3 comments
Labels
A-type-system Area: Type system P-low Low priority T-types Relevant to the types team, which will review and decide on the PR/issue.

Comments

@lcnr
Copy link
Contributor

lcnr commented Nov 14, 2024

#![feature(discriminant_kind)]
use std::marker::DiscriminantKind;

fn trait_bound<T: DiscriminantKind>() {}
fn normalize<T: DiscriminantKind<Discriminant = u8>>() {}

fn foo<'a, 'b>()
where
    &'b (): DiscriminantKind<Discriminant = u8>,    
{
    trait_bound::<&'a ()>();
}

fn bar<'a, 'b>()
where
    &'b (): DiscriminantKind<Discriminant = u8>,    
{
    normalize::<&'a ()>();
}

foo compiles, bar does not:

error: lifetime may not live long enough
  --> src/lib.rs:18:5
   |
14 | fn bar<'a, 'b>()
   |        --  -- lifetime `'b` defined here
   |        |
   |        lifetime `'a` defined here
...
18 |     normalize::<&'a ()>();
   |     ^^^^^^^^^^^^^^^^^^^ requires that `'b` must outlive `'a`
   |
   = help: consider adding the following bound: `'b: 'a`

error: lifetime may not live long enough
  --> src/lib.rs:18:5
   |
14 | fn bar<'a, 'b>()
   |        --  -- lifetime `'b` defined here
   |        |
   |        lifetime `'a` defined here
...
18 |     normalize::<&'a ()>();
   |     ^^^^^^^^^^^^^^^^^^^ requires that `'a` must outlive `'b`
   |
   = help: consider adding the following bound: `'a: 'b`

help: `'b` and `'a` must be the same: replace one with the other

Candidate selection for the trait goal prefers the trivial builtin impl. Normalization instead prefers the where-bound. This is inconsistent and means that whether we use the associated items impacts whether a trait bound holds.

It impacts all trivial builtin traits with associated types, I don't think this effects stable rn as either the trait is unstable or the builtin impls only exist for unnameable types. Nominating for t-types vibeck

@rustbot rustbot added the needs-triage This issue may need triage. Remove it if it has been sufficiently triaged. label Nov 14, 2024
@lcnr lcnr added I-types-nominated Nominated for discussion during a types team meeting. A-type-system Area: Type system T-types Relevant to the types team, which will review and decide on the PR/issue. and removed needs-triage This issue may need triage. Remove it if it has been sufficiently triaged. labels Nov 14, 2024
@lcnr
Copy link
Contributor Author

lcnr commented Nov 14, 2024

I realize this also affects our preference of impls over global where-bounds:

trait Trait {
    type Assoc;
}

impl Trait for &u32 {
    type Assoc = u32;
}

fn trait_bound<T: Trait>() {}
fn normalize<T: Trait<Assoc = u32>>() {}

fn foo<'a>()
where
    &'static u32: Trait<Assoc = u32>,
{
    trait_bound::<&'a u32>(); // ok
    normalize::<&'a u32>(); // error
}

@lcnr lcnr changed the title normalization does not prefer trivial builtin impls over where-bounds candidate selection for normalization and trait goals disagree Nov 14, 2024
@lcnr lcnr added I-types-nominated Nominated for discussion during a types team meeting. P-low Low priority and removed I-types-nominated Nominated for discussion during a types team meeting. labels Nov 14, 2024
@lcnr
Copy link
Contributor Author

lcnr commented Nov 26, 2024

we also have the same issue with alias-bound/where-bound mismatch

trait Bound<'a> {
    type Assoc;
}
trait Trait {
    type Assoc: Bound<'static, Assoc = u32>;
}

fn heck<'a, T: Trait<Assoc: Bound<'a>>>(x: <T::Assoc as Bound<'a>>::Assoc) {
    drop(x);
}

1 similar comment
@lcnr

This comment has been minimized.

@lcnr lcnr removed the I-types-nominated Nominated for discussion during a types team meeting. label Mar 10, 2025
bors added a commit to rust-lang-ci/rust that referenced this issue Mar 13, 2025
…try>

Prefer built-in sized impls (and only sized impls) for rigid types always

This PR changes the confirmation of `Sized` obligations to unconditionally prefer the built-in impl, even if it has nested obligations. This also changes all other built-in impls (namely, `Copy`/`Clone`/`DiscriminantKind`/`Pointee`) to *not* prefer built-in impls over param-env impls. This aligns the old solver with the behavior of the new solver.

---

In the old solver, we register many builtin candidates with the `BuiltinCandidate { has_nested: bool }` candidate kind. The precedence this candidate takes over other candidates is based on the `has_nested` field. We only prefer builtin impls over param-env candidates if `has_nested` is `false`

https://github.com/rust-lang/rust/blob/2b4694a69804f89ff9d47d1a427f72c876f7f44c/compiler/rustc_trait_selection/src/traits/select/mod.rs#L1804-L1866

Preferring param-env candidates when the builtin candidate has nested obligations *still* ends up leading to detrimental inference guidance, like:

```rust
fn hello<T>() where (T,): Sized {
    let x: (_,) = Default::default();
    // ^^ The `Sized` obligation on the variable infers `_ = T`.
    let x: (i32,) = x;
    // We error here, both a type mismatch and also b/c `T: Default` doesn't hold.
}
```

Therefore this PR adjusts the candidate precedence of `Sized` obligations by making them a distinct candidate kind and unconditionally preferring them over all other candidate kinds.

Special-casing `Sized` this way is necessary as there are a lot of traits with a `Sized` super-trait bound, so a `&'a str: From<T>` where-bound results in an elaborated `&'a str: Sized` bound. People tend to not add explicit where-clauses which overlap with builtin impls, so this tends to not be an issue for other traits.

We don't know of any tests/crates which need preference for other builtin traits. As this causes builtin impls to diverge from user-written impls we would like to minimize the affected traits. Otherwise e.g. moving impls for tuples to std by using variadic generics would be a breaking change. For other builtin impls it's also easier for the preference of builtin impls over where-bounds to result in issues.

---

There are two ways preferring builtin impls over where-bounds can be incorrect and undesirable:
- applying the builtin impl results in undesirable region constraints. E.g. if only `MyType<'static>` implements `Copy` then a goal like `(MyType<'a>,): Copy` would require `'a == 'static` so we must not prefer it over a `(MyType<'a>,): Copy` where-bound
   - this is mostly not an issue for `Sized` as all `Sized` impls are builtin and don't add any region constraints not already required for the type to be well-formed
   - however, even with `Sized` this is still an issue if a nested goal also gets proven via a where-bound: [playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=30377da5b8a88f654884ab4ebc72f52b)
- if the builtin impl has associated types, we should not prefer it over where-bounds when normalizing that associated type. This can result in normalization adding more region constraints than just proving trait bounds. rust-lang#133044
  - not an issue for `Sized` as it doesn't have associated types.

r? lcnr
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Mar 31, 2025
…=lcnr

Prefer built-in sized impls (and only sized impls) for rigid types always

This PR changes the confirmation of `Sized` obligations to unconditionally prefer the built-in impl, even if it has nested obligations. This also changes all other built-in impls (namely, `Copy`/`Clone`/`DiscriminantKind`/`Pointee`) to *not* prefer built-in impls over param-env impls. This aligns the old solver with the behavior of the new solver.

---

In the old solver, we register many builtin candidates with the `BuiltinCandidate { has_nested: bool }` candidate kind. The precedence this candidate takes over other candidates is based on the `has_nested` field. We only prefer builtin impls over param-env candidates if `has_nested` is `false`

https://github.com/rust-lang/rust/blob/2b4694a69804f89ff9d47d1a427f72c876f7f44c/compiler/rustc_trait_selection/src/traits/select/mod.rs#L1804-L1866

Preferring param-env candidates when the builtin candidate has nested obligations *still* ends up leading to detrimental inference guidance, like:

```rust
fn hello<T>() where (T,): Sized {
    let x: (_,) = Default::default();
    // ^^ The `Sized` obligation on the variable infers `_ = T`.
    let x: (i32,) = x;
    // We error here, both a type mismatch and also b/c `T: Default` doesn't hold.
}
```

Therefore this PR adjusts the candidate precedence of `Sized` obligations by making them a distinct candidate kind and unconditionally preferring them over all other candidate kinds.

Special-casing `Sized` this way is necessary as there are a lot of traits with a `Sized` super-trait bound, so a `&'a str: From<T>` where-bound results in an elaborated `&'a str: Sized` bound. People tend to not add explicit where-clauses which overlap with builtin impls, so this tends to not be an issue for other traits.

We don't know of any tests/crates which need preference for other builtin traits. As this causes builtin impls to diverge from user-written impls we would like to minimize the affected traits. Otherwise e.g. moving impls for tuples to std by using variadic generics would be a breaking change. For other builtin impls it's also easier for the preference of builtin impls over where-bounds to result in issues.

---

There are two ways preferring builtin impls over where-bounds can be incorrect and undesirable:
- applying the builtin impl results in undesirable region constraints. E.g. if only `MyType<'static>` implements `Copy` then a goal like `(MyType<'a>,): Copy` would require `'a == 'static` so we must not prefer it over a `(MyType<'a>,): Copy` where-bound
   - this is mostly not an issue for `Sized` as all `Sized` impls are builtin and don't add any region constraints not already required for the type to be well-formed
   - however, even with `Sized` this is still an issue if a nested goal also gets proven via a where-bound: [playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=30377da5b8a88f654884ab4ebc72f52b)
- if the builtin impl has associated types, we should not prefer it over where-bounds when normalizing that associated type. This can result in normalization adding more region constraints than just proving trait bounds. rust-lang#133044
  - not an issue for `Sized` as it doesn't have associated types.

r? lcnr
rust-timer added a commit to rust-lang-ci/rust that referenced this issue Mar 31, 2025
Rollup merge of rust-lang#138176 - compiler-errors:rigid-sized-obl, r=lcnr

Prefer built-in sized impls (and only sized impls) for rigid types always

This PR changes the confirmation of `Sized` obligations to unconditionally prefer the built-in impl, even if it has nested obligations. This also changes all other built-in impls (namely, `Copy`/`Clone`/`DiscriminantKind`/`Pointee`) to *not* prefer built-in impls over param-env impls. This aligns the old solver with the behavior of the new solver.

---

In the old solver, we register many builtin candidates with the `BuiltinCandidate { has_nested: bool }` candidate kind. The precedence this candidate takes over other candidates is based on the `has_nested` field. We only prefer builtin impls over param-env candidates if `has_nested` is `false`

https://github.com/rust-lang/rust/blob/2b4694a69804f89ff9d47d1a427f72c876f7f44c/compiler/rustc_trait_selection/src/traits/select/mod.rs#L1804-L1866

Preferring param-env candidates when the builtin candidate has nested obligations *still* ends up leading to detrimental inference guidance, like:

```rust
fn hello<T>() where (T,): Sized {
    let x: (_,) = Default::default();
    // ^^ The `Sized` obligation on the variable infers `_ = T`.
    let x: (i32,) = x;
    // We error here, both a type mismatch and also b/c `T: Default` doesn't hold.
}
```

Therefore this PR adjusts the candidate precedence of `Sized` obligations by making them a distinct candidate kind and unconditionally preferring them over all other candidate kinds.

Special-casing `Sized` this way is necessary as there are a lot of traits with a `Sized` super-trait bound, so a `&'a str: From<T>` where-bound results in an elaborated `&'a str: Sized` bound. People tend to not add explicit where-clauses which overlap with builtin impls, so this tends to not be an issue for other traits.

We don't know of any tests/crates which need preference for other builtin traits. As this causes builtin impls to diverge from user-written impls we would like to minimize the affected traits. Otherwise e.g. moving impls for tuples to std by using variadic generics would be a breaking change. For other builtin impls it's also easier for the preference of builtin impls over where-bounds to result in issues.

---

There are two ways preferring builtin impls over where-bounds can be incorrect and undesirable:
- applying the builtin impl results in undesirable region constraints. E.g. if only `MyType<'static>` implements `Copy` then a goal like `(MyType<'a>,): Copy` would require `'a == 'static` so we must not prefer it over a `(MyType<'a>,): Copy` where-bound
   - this is mostly not an issue for `Sized` as all `Sized` impls are builtin and don't add any region constraints not already required for the type to be well-formed
   - however, even with `Sized` this is still an issue if a nested goal also gets proven via a where-bound: [playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=30377da5b8a88f654884ab4ebc72f52b)
- if the builtin impl has associated types, we should not prefer it over where-bounds when normalizing that associated type. This can result in normalization adding more region constraints than just proving trait bounds. rust-lang#133044
  - not an issue for `Sized` as it doesn't have associated types.

r? lcnr
# for free to join this conversation on GitHub. Already have an account? # to comment
Labels
A-type-system Area: Type system P-low Low priority T-types Relevant to the types team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests

2 participants