Ensure `arbitrary_self_types` method resolution is forward-compatible with custom autoref

[cramertj]

arbitrary_self_types (v1 RFC, v2 amending RFC) is currently being considered for stabilization in #135881. This feature, designed to support methods which take self by an expanded set of user-defined types like self: SmartPointer<T>, self: CppRef<T>, makes several changes to method resolution.

How method lookup works today

Today, we search for methods on a type T in this order (rustc dev guide, reference):

• Methods for type T with a Self type of self, &self, &mut self
• Deref: while T is Deref, NewT = <T as Deref>::Target, consider T, &T, &mut T
• Unsizing: once T is no longer Deref, if T == [A; N], consider [A], &[A], &mut [A]

For each considered type, preference is given for inherent methods over extension methods (trait methods).

How method lookup works under arbitrary_self_types

arbitrary_self_types v2 changes this look up (RFC. reference PR):

• The first and most obvious change is that it uses the Receiver trait rather than the Deref trait for looking up candidate receiver types. This allows for method receivers like fn takes_cppref(self: CppRef<T>) where CppRef is some type that cannot implement Deref<Target = T>.
• However, the more significant change is that arbitrary_self_types allows for methods to be defined for impl MyType { fn foo(self: PtrLike<MyType>) { ... } } for custom Ptrlike types.

Other related outstanding features

• The arbitrary_self_types_pointers feature considers *const T methods for each candidate receiver type which is a *mut T.
• The pin_ergonomics feature as documented here consider "method[s] with a Pin that's reborrowed" (note: I, cramertj@, don't actually understand at this time how this changes the candidate or method set).

Why custom autoref

I created this issue because I believe that most uses of arbitrary_self_types that I'm aware of actually want custom autoref behavior (the exception is external std-likes e.g. RFL's Arc). That is, rather than extending the candidate set of receiver types, I believe they may instead/also want to modify the per-candidate set of Self types searched. I want to ensure that the parts of arbitrary_self_types being stabilized do not hamper our ability to do add autoref behavior (at least for Pin, if not for custom types).

For example:

struct MyType { ... }
impl MyType {
    fn foo(self: CppRef<Self>) { ... }
}

let x = MyType { ... };
x.foo(); // ERROR

Doing lookup for foo on MyType, we look for methods taking self: MyType, self: &MyType, and self: &mut MyType, see that there's no receiver impl or unsizing to follow, and give up. What should happen is that CppRef should behave as & does (as it is strictly less powerful than & and can be created from T "for free").

Note that this is a per-candidate type behavior, as we'd want Box::new(MyType{ ... }).foo() to work as well. That is, method resolution for foo on Box<MyType> should look for foo as a by-value, by-ref, by-cppref, by-mutref, and by-cppmutref method on candidate types Box<MyType> and then MyType.

• self: Box<MyType>, self: &Box<MyType>, self: CppRef<Box<MyType>>, self: &mut Box<MyType>, self: CppMutRef<Box<MyType>>
• self: MyType, self: &MyType, self: CppRef<MyType> <<< this one is found and selected

Similarly, we could imagine doing the same thing in order to support by-Pin methods on types which are Unpin (Unpin types can convert from Self to Pin<&Self>/Pin<&mut Self> "for free"):

struct MyType { ... }
impl Future for MyType { fn poll(self: Pin<&mut Self>, ... ) -> ... { ... } }

let x = MyType { ... };
x.poll(..) // ERROR today, we'd like this to work, maybe with something like

impl<T: ?Sized + Unpin> AutoRef<Pin<&T>> for T { ... }
impl<T: ?Sized + Unpin> AutoRefMut<Pin<&mut T>> for T { ... }

Similarly, we'd also love for Pin<&mut Self> methods to be callable on Pin<Box<Self>> receiver types, which can create a Pin<&mut Self> "for free", maybe with an impl like:

impl<T: ?Sized> AutoRef<Pin<&T> for Pin<Box<T>> { ... }
impl<T: ?Sized> AutoRefMut<Pin<&mut T>> for Pin<Box<T>> { ... }

Other examples of autoref-like non-Receivers that we'd like to consider in method resolution:

• @veluca93 mentioned having image types that would like to autoref into mutable image views.
• @sarah-quinones brought up the faer MatMut type which is a mutable view over a matrix. Ideally, methods which work on a MatMut would be callable on a local of type Mat.

Is this even a thing we can do?

Maybe not. Making method resolution search a (# of autoref types for Self) * (Receiver/Deref impls for Self + unsize) number of types when looking for a method seems expensive, but I don't have a good idea of how expensive.

However, I think this is well-motivated at least for Pin, and possibly some other select set of types.

Future compatibility issues

At this point this issue is mostly FUD, unfortunately-- I don't have a specific concern besides "method resolution is getting more complicated but maybe in the wrong way." Pin is already stable as a self type, so any extensions we make to support at least Pin-autoref have to be done in a backwards compatible way. Therefore, it may be the case that we're not making anything worse for ourselves by allowing other non-stdlib types to have this ability.

The arbitrary_self_types v2 RFC does say that arbitrary_self_types makes it so that "a wider set of locations is searched for methods with those receiver types." I haven't completely understood this-- it seems like the set of places we have to look today for a potential self: Arc<Self> method is the same set of locations we'd have to look for a self: NonStdArc<Self> (that is, we have to search both the impls of ...Arc and Self as well as any <Self as Receiver>::Target).

Am I (@cramertj) missing something? Are we committing to other method resolution complexities by stabilizing arbitrary_self_types that will make it harder to add autoref support for Pin or CppRef?

[tmandry]

Nominating for lang team discussion, as this is timely and relevant to the arbitrary self types stabilization.

@rustbot label I-lang-nominated

cc @adetaylor @rust-lang/lang @rust-lang/lang-advisors

[tmandry]

Similarly, we could imagine doing the same thing in order to support by-Pin methods on types which are Unpin (Unpin types can convert from Self to Pin<&Self>/Pin<&mut Self> "for free"):

Interestingly, I was talking with @nikomatsakis about doing the "inverse" of this in the trait system: If you have a trait with a Pin<&mut Self> method and you know your type is Unpin, you can implement it as &mut self. (This is important for Drop migration.)

It does make sense to me that we would want something that works both ways; in other words, that we would have autoref for pin. But the way I've been thinking we would do pin ergonomics was to build them into the borrow checker; at that point, pin becomes more like another one of the special reference types we have today.

[cramertj]

Specializing trait methods

Interestingly, I was talking with @nikomatsakis about doing the "inverse" of this in the trait system: If you have a trait with a Pin<&mut Self> method and you know your type is Unpin, you can implement it as &mut self. (This is important for Drop migration.)

This also feels related to being able to implement self-by-value trait methods using &mut self, or &mut self trait methods only using &self, or unsafe trait methods with a safe implementation. Historically, a lot of these have been handled by implementing the trait for &T or &mut T, but it would be great to relax these requirements.

the way I've been thinking we would do pin ergonomics was to build them into the borrow checker; at that point, pin becomes more like another one of the special reference types we have today.

We can do this for Pin, we could potentially do it for CppRef/AliasRef, but it gets more funky when extended to custom unsizing / custom DSTs and things like MatView that will never be "native". Maybe this is okay! Possibly we just rule that out as a side use-case that doesn't need the extra ergonomics.

On Deref

I've often struggled with the fact that Deref impls, like Index impls, cannot return a non-reference type. This means that whatever type you refer to must literally be stored within (or pointed to by) the type implementing Deref. This prevents you from doing useful things, like returning types that are logically a view but which are not literally an &T.

One could imagine a world where we relax Deref, rather than changing the result to Receiver. This would allow for types like Pin<Box<T>> to Deref to a Pin<&T> and DerefMut to a Pin<&mut T>. e.g.:

trait ExpandedDeref {
    type Target<'a>;
    fn deref(&self) -> Self::Target<'_>;
}

trait ExpandedDerefMut {
    type TargetMut<'a>;
    fn deref_mut(&mut self) -> Self::TargetMut<'_>;
}

This is a little bit of a counterfactual, as I don't see how we "get there from here", but maybe someone who has thought about this for longer than me has an idea :). I do really want Index/IndexMut to change to this behavior so that I can return custom view types which refer to values that are not stored literally in-memory (see also: custom DSTs, which take a different approach to solving this problem by expanding the kinds of things that can be an &T).

Notably this does not solve the problem of calling a Pin<&mut T> method on a value of type &mut T where T: Unpin, nor of calling a CppRef<'_, T> method on a value of type &T.

[tmandry]

Maybe not. Making method resolution search a (# of autoref types for Self) * (Receiver/Deref impls for Self + unsize) number of types when looking for a method seems expensive, but I don't have a good idea of how expensive.

Maybe it's worth drilling into this as a data structures and algorithms problem. This will be a bit rough, but maybe we can start putting some boundaries around the problem.

Defining an efficient autoref

Today method resolution proceeds in d steps, where d is the number of types along the Deref/Receiver chain for a given type. We can assume this is irreducible because there's no way to compute all possible receiver types ahead of time (e.g. we can have &&&&&&&T as a receiver).

Let's say our goal is to make it so that for each type we consider along the Receiver chain, we can consider a list of user defined methods named foo in a time proportionate to the number of methods named foo implemented on the receiver type and any extension traits in scope. So the final cost would be O(d * m), where m is the number of methods we would consider today. Importantly, the cost of should not scale upward with the number of autoref types "ambiently" defined.

Right now the dev guide describes an algorithm where we (roughly) adjust each receiver type with an extra & and &mut. Since those are the only types that have autoref behavior, there's a constant number of them, and we only apply one level of autoref, our O(d * m) requirement is met.

Extending to user defined autoref

If we allow arbitrary new types with autoref-like behavior, the same approach would not work: We would have to consider O(d * m * r) where r is the number of autoref-able pointer types in scope. Now, maybe this isn't so bad in practice; most method resolutions succeed and end in the earlier stages, and we can contain the cost by saying you need to explicitly import any autoref pointer type for it to be considered. But it has the ingredients of something bad, so let's avoid it if we can.

I'm somewhat optimistic we can still make resolution O(d * m) if we limit user-defined autoref in a particular way. Namely: Given a candidate method definition, we can quickly¹ derive the set of receiver types it is callable from and the adjustment to be made when considering each type. So in the example you gave of a self: CppRef<Self> we would know that it could only have come from a receiver type unifying with Self and the adjustment is CppRef(_).

If we do this for each method, we've responsibly bounded the set of self types and adjustments to be considered for that method instead of just trying

Note that this can work if we allowed applying multiple kinds of autoref, like self: &CppRef<Self>. If we're clever enough about it I think we can even support "branches" like if CppRef<T> could come from either T or &T². It should still only be a cost proportionate to the size of the self type written in the method and the number of autoref paths inherent in the named types.

Comparison to status quo

Now for the bad news: This limitation does not apply to autoref as it exists today. Consider this example:

trait Foo { fn method(self); }
trait Bar { fn method(&self); }

impl<T: Copy> Foo for T { fn method(self) {} }
impl Bar for String { fn method(&self) {} }

fn main() {
    let x: String = String::new();
    x.method();
}

This does not compile because when we consider &String, <&String as Foo>::method(&x) applies just as well as <String as Bar>::method(&x). This doesn't satisfy our limitation because we would not be able to tell just from looking at the impl<T: Copy> Foo for T the set of autoreffing types, and therefore receiver types, it could apply to.

I think we should be willing to give up on this code ever calling <CppRef<String> as Foo>::method even if CppRef were in scope. For one, it would mean introducing a slew of new method resolution errors anytime a custom reference type is in scope. For another, it doesn't seem that useful for custom reference types. I'm not exactly sure who is served by having the current behavior for references – probably someone, but I think we can live with the built in reference types being just a little bit more special than user defined ones, or (if it's not useful) phase out the behavior over an edition.

Precedence

Since we have a bounded set of self types to consider for each method, I don't think we should introduce further levels of precedence. We can add a single last level of precedence that considers all custom autoref types, and errors if there is any ambiguity. Arguably we should also do this for the builtin reference types in a future edition.

Summary sketch

Let's pretend we have a core trait

trait AutoRef<From> {}

with some to-be-designed rules around the kinds of impls you can write, and a custom reference type

struct MyRef<T>(*mut T);
impl<T> AutoRef<T> for MyRef<T> {}
impl<T> AutoRef<&T> for MyRef<T> {}

In summary, I think we could still support:

• Inherent and extension methods on our self type or any type along its Receiver chain that name the custom ref type in their signature
  • e.g. impl Struct { fn f(self: MyRef<Self>) {} } => x.f() works if x: MyRef<Struct>, x: Struct, x: &Struct, and even x: Box<Struct> (via Deref)
  • e.g. impl Foo for Box<Struct> { fn f(self: MyRef<Struct>) {} } => x.f() works if x: Box<Struct>
• Extension trait methods implemented on our custom ref type that name the custom ref type
  • e.g. impl<T> Foo for MyRef<T> { fn f(self) {} ) => x.f() works if x: T and if x: MyRef<T>, where T is any type parameter or concrete type
• Types that implement both Receiver and Autoref
  • Method resolution would always work in one direction at a time: Along the receiver chain from the original type to assemble the candidates, and along the autoref chain to decide which candidates are viable.

We would not support:

• Inherent methods on our custom ref type, unless that is the type you started with or a type along the Receiver chain
  • This is "preexisting": We already don't support impl &T {} or impl &mut T {} for any type, so I think this is fine
  • Inherent methods on autoref types should be considered antipattern, just as they would on receivers
• Extension trait methods that apply to our custom ref type without naming the type
  • This is new: See the "status quo" section above
  • Arguably it isn't that useful
• Associated types as self types or along the receiver/autoref chain
  • Too complicated; also why!?

Footnotes

1. Proportionate to the size of the definition and perhaps the number of Autoref impls of any self types it names. ↩

2. This is the part I'm least certain about. ↩

[RalfJung]

Cc @rust-lang/types

[adetaylor]

@ssbr posted some thoughts in this area too - taking the view that & and &mut are so baked into the language that we can't realistically support other reference types as first-class citizens. Perhaps we should challenge that assumption. I'm interested to see where this discussion goes.

[oli-obk]

I've often struggled with the fact that Deref impls, like Index impls, cannot return a non-reference type.

While I believe we can figure out a way to change deref into

trait Deref {
    type Target;
    type Output<'a> = &'a Self::Target;
    fn deref<'a>(&'a self) -> Self::Output<'a>;
}

in a way that doesn't break anyone, I'm not sure that Deref specifically is something this should be done for. Index, yes, I'm sold, but Deref is primitive enough that we'll have some problems if it returns anything but a reference:

*foo kind of desugars to *Deref::deref(&foo) for non-reference types, so the view type returned would itself have to implement Deref, but... to what would it dereference to? It exists precisely because we want a non-reference value.

We can't just rely on a Copy impl of the view type, as a mutable view returned from DerefMut would obviously not be Copy.

This is of course resolveable by saying that similar to how we decide, depending on the usage of the result of the deref, whether to invoke Deref or DerefMut, we can decide to just not deref the result again but just keep the value.

There's a slightly odd, but potentially simpler solution if we figure out DerefMove: just implement DerefMove for &YourType. Similar to how we have to make decisions on Deref vs DerefMut when we see a *foo expression, we can pick DerefMove and not deref the result again like we effectively do with Deref.

[veluca93]

This is a little bit of a counterfactual, as I don't see how we "get there from here", but maybe someone who has thought about this for longer than me has an idea :).

I think something like this would work:

• Define a ExpandedDeref trait.
• Either have a blanket impl of Deref -> ExpandedDeref, or somehow claim that one cannot implement both
• Across an edition, rename Deref into OldDeref and ExpandedDeref into Deref.

I believe such an approach would have fewer method resolution complications than a new trait (in particular I don't think it would have complexity implications), but I am not sure if it would solve everything (or even a majority of the things) that people want to solve with custom autoref that cannot be solved by making carve-outs for special types.