Pre-RFC: enable deref coercion on trait-bound parameters

pitaj · February 20, 2023, 1:14am

Feature Name: trait_bound_deref_coercion

Summary

Enable deref conversions (RFC#241) while solving for trait-bound generics.

These coercions eliminate the need for "re-borrowing" (things like &*v) when using borrowed values that do not themselves implement the bounding trait(s) but have a deref target that does.

Motivation

Rust currently supports a useful set of implicit coercions that are used when calling functions, passing arguments, etc. These drastically improve the ergonomics of using borrowed values.

One current limitation of this is that deref coercions are only used if there is a concrete target type:

trait Foo {}
impl Foo for &str {}
fn bar(f: impl Foo) {}

let s = String::new();
bar(&s); // error[E0277]: the trait bound `&String: Foo` is not satisfied

For &String -> &str, this is not a huge problem: we can impl Foo for &String as well. However, there are several problems with this approach:

If the trait is sealed, third-party types that deref to &str will not be able to add a similar impl
It will not handle arbitrary levels of indirection, such as &&str or &&&&String
Far more types deref to slices, for instance - leading to a large amount of redundant impls
Most importantly, this leaves no room for various API extensions in the standard library, such as applying the Pattern API to slices

Extending the `Pattern` API for `[T]`

Various str methods make use of the Pattern API. This allows something like str::contains to work with chars, &strs, etc.

We'd like to extend this to support slices as well. However, doing so can cause current valid code to stop compiling:

let a: Vec<i32> = (1..10).collect();
let b: Vec<i32> = (1..3).collect();

assert!(a.starts_with(&b));

Currently, &b auto-derefs from &Vec<i32> to &[i32], because starts_with only accepts &[T]. If we change starts_with to accept any Pattern<&[T]>, this will fail to compile unless we manually implement Pattern<&[T]> for &Vec<T>. That is not a workable solution, however, because countless third-party types deref to slices.

This issue specifically is the primary motivation behind this language change. We hope to enable extending various APIs within the standard library in a backwards-compatible fashion.

Ergonomic improvement for third-party string and array/vector types

While not a primary motivation, this feature will improve the ergonomics of using various third-party libraries.

One example is stack-stored strings, like CompactString. Currently using this with the str Pattern API requires re-borrowing:

let text = "abcdefghijk";
let needle = CompactString::new("f");
text.find(&*needle); // Currently, re-borrow is necessary, otherwise E0277

With this proposal, an &CompactString can be used just like an &String or &str:

text.find(&needle);

Similarly, SmallVec would be useable with the slice pattern API:

let slice: &[u8] = &[1, 2, 3, 4, 5, 6, 7, 8, 9];
let prefix = SmallVec::from([1, 2, 3]);
let rest = slice.strip_prefix(&*prefix); // Currently, re-borrow is necessary, otherwise E0277

Without the re-borrow:

let rest = slice.strip_prefix(&prefix);

Simplification of API implementations

This would reduce various redundant trait implementations in the standard library, such as the Pattern impls for &&str and &String.

Guide-level explanation

Rust users are already aware of normal deref coercions, defined in RFC 241. They allow the programmer to pass an &T value into a function accepting &<T as Deref>::Target:

// `&Vec<T>` gets automatically coerced to `&[T]`
fn foo(_: &[u8]) {}
let v: Vec<u8> = vec![];
foo(&v);

// `&String` gets automatically coerced to `&str`
fn bar(_: &str) {}
let s: String = format!("Hello, {}", "World!");
bar(&s);

// This is applied recursively, so `&&&String` will also coerce to `&str`.
bar(&&&s);

The compiler will also take into account possible deref coercions when processing a generic parameter bounded by a trait:

trait Dog {
    fn bark(self);
}
impl Dog for &str {
    fn bark(self) {
        println!("Ruff!");
    }
}

fn approach(dog: impl Dog) {
    dog.bark();
}

let a: &str = "";
let b: &String = &String::new();

approach(a); // Ruff!
approach(b); // Ruff! - Used to error, but now coerces to `&str`

Deref coercions will only be used if a direct implementation of the type does not exist for the type passed. And, any deref coercion will only recurse the minimum amount of times to find a suitable target:

impl Dog for &String {
    fn bark(self) {
        println!("Woof!");
    }
}

let a: &str = "";
let b: &String = &String::new();

approach(a); // Ruff!
approach(b); // Woof! - Deref coercion not used because of the direct impl
approach(&b); // Woof! - `&&String` coerces to `&String`, not all the way to `&str`

In this way, direct implementations have higher precedence than deref coercions.

Reference-level explanation

Changes to trait selection

The idea is to introduce a deref coercion to the trait selection process, only for already-borrowed values, and only if there is not a direct impl for the trait for the type in question.

The coercion will be applied recursively, just like a normal deref coercion in argument position.

Here is a simple pseudocode algorithm for trait selection. Let Implementors(Trait) be a procedure for listing all types which implement Trait. The general Select(Trait, T) procedure would work as follows:

Select(Trait, T):

  if T in Implementors(Trait) then
      T as Trait
  else if T = &V and V: Deref<W> then
      Select(Trait, &W)
  else if T = &mut V and V: Deref<W> then
      Select(Trait, &W)
  else if T = &mut V and V: DerefMut<W> then
      Select(Trait, &mut W)
  else
      nil

The truth table below compares current and proposed behavior using [T] and Vec<T> as an example given the following:

trait Pattern is implemented for only &[T]
trait ToSlice is implemented for &[T] and &Vec<T>

Function definition	Argument type	Current Behavior	Proposed Behavior
`fn run(_: &[T])`	`&[T]`	Passed directly	Passed directly
`fn run(_: &[T])`	`&Vec<T>`	Deref coercion to `&[T]`	Deref coercion to `&[T]`
`fn run(_: &[T])`	`&&[T]`	Deref coercion to `&[T]`	Deref coercion to `&[T]`
`fn run(_: &[T])`	`&&Vec<T>`	Deref coercion to `&[T]`	Deref coercion to `&[T]`
`fn run(_: &[T])`	`Vec<T>`	Compiler Error	Compiler Error
`fn run(_: impl Pattern)`	`&[T]`	Passed directly	Passed directly
`fn run(_: impl Pattern)`	`&Vec<T>`	Compiler Error	Deref coercion to `&[T]`
`fn run(_: impl Pattern)`	`&&[T]`	Compiler Error	Deref coercion to `&[T]`
`fn run(_: impl Pattern)`	`&&Vec<T>`	Compiler Error	Deref coercion to `&[T]`
`fn run(_: impl Pattern)`	`Vec<T>`	Compiler Error	Compiler Error
`fn run(_: impl ToSlice)`	`&[T]`	Passed directly	Passed directly
`fn run(_: impl ToSlice)`	`&Vec<T>`	Passed directly	Passed directly
`fn run(_: impl ToSlice)`	`&&[T]`	Compiler Error	Deref coercion to `&[T]`
`fn run(_: impl ToSlice)`	`&&Vec<T>`	Compiler Error	Deref coercion to `&Vec<T>`
`fn run(_: impl ToSlice)`	`Vec<T>`	Compiler Error	Compiler Error

Only the following cases are changed:

fn run(_: impl Pattern) with &&[T] and any further indirection like &&&[T]
fn run(_: impl ToSlice) with &&[T] and any further indirection like &&&[T]
fn run(_: impl Pattern) with &Vec<T> and any further indirection like &&Vec<T>
fn run(_: impl ToSlice) with &&Vec<T> and any further indirection like &&&Vec<T>

Implementation

There already exists a compiler suggestion for E0277 (implemented in rust-lang/rust#72456) when a re-borrow will solve the error:

error[E0277]: the trait bound `&String: Foo` is not satisfied
 --> src/main.rs:9:5
  |
9 | bar(&s);
  | --- ^^ the trait `Foo` is not implemented for `&String`
  | |
  | required by a bound introduced by this call
  |
note: required by a bound in `bar`
 --> src/main.rs:6:16
  |
6 | fn bar(f: impl Foo) {}
  |                ^^^ required by this bound in `bar`
help: consider dereferencing here
  |
9 | bar(&*s);
  |      +

For more information about this error, try `rustc --explain E0277`.

The same machinery can be adapted to perform the coercion instead.

Drawbacks

This allows a kind of specialization, since implementing the trait manually can have different behavior from the deref coercion fallback
This allows non-local types to indirectly implement a sealed trait by implementing dereferencing to a local type that already implements it. This could be considered a coherence violation, but how this could cause problems in practice is unclear.

This does add to the implicitness around using borrowed values. However, this is already widespread with the application of deref coercions. The current behavior is often unintuitive to beginners, so this proposal may actually reduce misunderstandings.

Rationale and alternatives

The main motivation behind this proposal is to allow functions currently taking a concrete reference type to transition into taking a generic trait-bound type. This would be used to generalize the Pattern API for use with [T], which is currently not impossible to do without breaking code that depends upon the deref coercions.

Not doing this could result in further long-term stagnation of the slice APIs and the inconsistencies related to that within the standard library.

The change we propose is the only known way to achieve this in a backwards-compatible way.

Alternative 1: many manual implementations

One alternative is to manually implement the trait for every type we want to work. This is still limited:

Does not apply recursively. You could implement for &String, but that would not work for &&String. We could hack around this by implementing an arbitrary number of levels of indirection (&&String, &&&String, etc)
Unstable or sealed traits cannot be implemented by third-party types

Alternative 2: blanket impl with `Deref`

Another alternative is to create a blanket implementation based on Deref:

trait Foo {}
impl Foo for &str {}
fn bar(f: impl Foo) {}

impl<'a, T> Foo for &'a T
where
    T: std::ops::Deref<Target = str>,
{}

let s = String::new();
bar(&s);

Like alternative 1, this does not apply recursively:

bar(&&s); // error[E0271]: type mismatch resolving `<&String as Deref>::Target == str`

And it will not work for intended usage with the slice Pattern API:

trait SlicePattern<T> {}
impl<'p, T> SlicePattern<T> for &'p T {}
impl<'p, T> SlicePattern<T> for &'p [T] {}

// error[E0119]: conflicting implementations of trait `SlicePattern<_>` for type `&_`
impl<'p, T, P> SlicePattern<T> for &'p P
where
    P: std::ops::Deref<Target = [T]>,
{}

So it would still depend on some possible future language feature that could resolve the conflict:

impl<'p, T, P> SlicePattern<T> for &'p P
where
    P: std::ops::Deref<Target = [T]>,
    T != P, // Possible future feature
{}

Prior art

Unresolved questions

How will this affect diagnostics?
What are the implications to coherency rules?
Should this extend more generally to all coercions, not just deref coercions?

Future possibilities

Unrelated, but the T != P bound from the example above would also be useful for some From impls:

struct Generic<T>(T);

impl<T, U> From<Generic<U>> for Generic<T>
where
     T: From<U>,
{ ... }

error[E0119]: conflicting implementations of trait `From<Generic<_>>` for type `Generic<_>`
  --> src/main.rs:91:1
   |
91 | impl<T, U> From<Generic<U>> for Generic<T>
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: conflicting implementation in crate `core`:
           - impl<T> From<T> for T;

pitaj · February 24, 2023, 7:02pm

pitaj:

So it would still depend on some possible future language feature that could resolve the conflict:
impl<'p, T, P> SlicePattern<T> for &'p P
where
    P: std::ops::Deref<Target = [T]>,
    T != P, // Possible future feature
{}

I've become aware that this is actually possible today using just the negative_impls unstable feature:

#![feature(negative_impls)]

pub mod marker {
    // core::marker
    mod different {
        // So `Helper<T, U>` can be `Send`,
        // even if `T` or `U` is not `Send`
        struct AlwaysSend<T>(T);
        unsafe impl<T> Send for AlwaysSend<T> {}

        struct Helper<T, U>(AlwaysSend<T>, AlwaysSend<U>);
        impl<T> !Send for Helper<T, T> {}

        // Hide within this module so it can't be
        // unimplemented for any other case
        pub trait Sealed {}
        impl<T, U> Sealed for (T, U) where Helper<T, U>: Send {}

        // Depends on inaccessible trait to
        // seal it from external implementations
        pub trait Different: Sealed {}
        impl<T, U> Different for (T, U) where Helper<T, U>: Send {}
    }

    pub use different::Different;
}

use marker::Different;

impl<'p, T, P> SlicePattern<T> for &'p P
where
    P: std::ops::Deref<Target = [T]>,
    (T, P): Different,
{}