Pre-RFC: Subtyping coercion with inferred target

language design
1

This RFC uses the proposed template of RFC 3339.

Summary

This RFC expands subtyping coercion, allowing it to occur in certain contexts where the target type must be inferred. As a necessary prerequisite for accomplishing this, the RFC proposes to make some patterns that are currently future-compatibility warnings under coherence_leak_check into hard errors.

The proposal smooths the path forward for future extensions to subtyping in Rust, e.g. pattern types, by ensuring that those extensions will play well with type inference.

Motivation and background

Type inference failure

Consider the following code example (playground).

fn takes_concrete_supertype(_: fn(&'static u8)) {}

trait Trait {}
impl Trait for fn(&'static u8) {}

fn takes_impl_trait(_: impl Trait) {}

fn main() {
    let fn_ptr: for<'a> fn(&'a u8) = |_| {};

    // This works today. Rust realizes it needs to convert `fn_ptr`
    // from a `for<'a> fn(&'a u8)` to its supertype `fn(&'static u8)`.
    takes_concrete_supertype(fn_ptr);

    // This doesn't compile today :(
    // Rust doesn't infer that it must coerce
    // the `for<'a> fn(&'a u8)` to its supertype `fn(&'static u8)`.
    takes_impl_trait(fn_ptr);
}

for<'a> fn(&'a u8) <: fn(&'static u8). (<: means "is a subtype of"). Rust allows coerecing subtype values to supertypes in many different contexts. But, as shown as the example above, Rust can't perform these coercions when the target supertype must be inferred.

In current Rust, this issue only arises with higher-ranked lifetimes on function pointers, so it's not a major problem. However, features like pattern types would expose this type inference failure in many more situations, by introducing new instances of subtyping.

For code like the above to compile, Rust must be able to determine a single "best" supertype to coerce to, even though multiple options could potentially satisfy the trait bounds. This RFC's proposed changes ensure that this is possible.

coherence_leak_check today

For any type T and trait Trait, Rust's coherence rules allow at most one impl Trait for T. For any type U such that U <: T xor T <: U, you can write impl Trait for T and impl Trait for U together, but this triggers the coherence_leak_check future-compatibility lint. coherence_leak_check has not been made a hard error, because such impls occasionally come up in real-world code.

Explanation

New coherence rules

This RFC proposes the following new coherence rules.

For any type T and trait Trait, one of the following two cases must hold:

  1. T implements Trait.

    1. In this case, if any of T's supertypes or subtypes also implement Trait, those impls must come from the same impl block as the impl of Trait for T.
    2. None of T's supertypes or subtypes may implement !Trait. (Similarly, if T actually implements !Trait, none of its subtypes or supertypes may implement Trait.)

  2. T does not implement Trait. In this case, consider the set {U} of all supertypes of T that do implement Trait. If {U} is non-empty, then all of the elements of {U} must share a common subtype S, that itself implements Trait, and is a member of {U}.

As far as I am aware, it is impossible to write a trait impl in current Rust that violates these rules without triggering the coherence_leak_check lint. Rules 1.2 and 2 are currently impossible to violate even with the lint allowed.

Inferred supertype coercions

These rules allow selecting a single "best" target type to coerce to in cases like the above example. In general, when a value of type T is provided but a value of a type implementing Trait is expected, the value of type T is coerced to S. In the specific case of the above example, T is for<'a> fn(&'a u8) and S is fn(&'static u8).

Why rule 1.1?

Rule 1.1 is not strictly necessary for this scheme to work; S could be inferred without it. However, the rule defuses a major footgun. Both subtyping coercion and type inference happen implicitly; the programmer may not be aware of the exact types being selected. In addition, the details of type inference are not part of Rust's stability guarantees, and can change with compiler upgrades. The "one impl block" rule makes it difficult (though not impossible) to write code that breaks or silently changes behavior depending on type inference details.

Why rule 1.2?

This rule exists to prevent conflicts with potential future features that add variance to traits. It may be relaxed or removed in the future.

New hard errors

As part of ensuring that the rules above are upheld, some patterns that currently trigger the coherence_leak_check lint become hard errors. Specifically, for any pair of type T and U such that T <: U, impl Trait for T and impl Trait for U cannot both be present at the same time. (Impls that currently trigger the lint but don't violate the above rules are unaffected; they stay future-compatibility warnings).

Migration strategy for projects relying on the old behavior

Real-world code that trips coherence_leak_check today is rare, but not unheard-of. Searching all Rust code on GitHub, I found two projects using #![allow(coherence_leak_check)]:

  • wasm-bindgen could remove its #![allow(coherence_leak_check)] once negative impls integrated into coherence are stabilized, by adding impl<'a, T: ?Sized> !FromWasmAbi for &'a T {} to its source code. This RFC should not be stabilized until negative impls have been stabilized for some time.
  • The gcmodule project defines some impls that trigger the lint, as described here. (Old versions of Servo would also be affected by this issue, though the latest version is not.) This RFC proposes to support gcmodule's use-case by ensuring that impl<T> Trait for fn(T) subsumes/implies impl<T> Trait for fn(&T). This is to be accomplished by treating for<'a> fn(&'a T) as essentially equivalent to fn(&'empty T),where 'empty is a lifetime that all lifetimes outlive. More generally, any type with a higher-ranked lifetime in contravariant positions only can be treated as essentially equivalent to the same type, but with the lifetime replaced with 'empty. The full details of how this works are explained in this GitHub comment.

Drawbacks

  • The proposal contains some breaking changes. Though very few projects appear to be affected, one of them is the widely-used crate wasm-bindgen.
  • The proposal makes type inference more complex.
  • The proposal makes the coherence rules more complex.
  • The proposal is primarily motivated by future language extensions, which might never happen.

Rationale and alternatives

  • Compared to doing nothing: not addressing the inference issue at all would make it impossible for libraries to start using features like pattern types in existing APIs without breaking their consumers.
  • Compared to having different subtyping coercion inference rules for higher-ranked lifetime subtyping and other forms of subtyping: this alternative would needlessly complicate the language and specification.
  • Compared to not having rule 1.1: without this restriction, Rust code would become more brittle in the face of extensions to subtyping, which is exactly counter to the motivation behind this RFC.

Prior art

None that I am aware of.

Unresolved questions

  • The rules involving 'empty probably need more experimentation and thought to establish with certainty they are correct.

Future possibilities

  • This proposal is primarily intended to support future extensions to subtyping.
  • This proposal leaves the future of some patterns that coherence_leak_check lints against unresolved. In the future, these could be either permitted without lint, or forbidden with or without replacement.
  • Future extensions to variance/subtyping could address more of the issues that features like pattern types face.
  • An "escape hatch" annotation of some sort could be added to allow violating proposed coherence rule 1.1 if the programmer is "really sure." (This would restrict potential future features that add variance to traits.)
  • Proposed coherence rule 1.2 could be relaxed in the future. (Ditto.)
  • Proposed coherence rule 2 could be relaxed in the future, at the price of making type inference worse when it is violated.
1 Like
2

Could this feature make it more likely for users to accidentally run into the soundness hole with HRTB subtyping and implied bounds?

3

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.