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.

[programmerjake]

a solution to customizable Deref could be to do something like C++'s operator -> where the compiler keeps invoking Deref on the output of the Deref call until it returns a type with built-in dereferencing (so, only references or Box most likely).

e.g. the following BitRefMut can be read/written through Deref[Mut] just like &mut bool can be, but it acts on only a particular bit in a byte and only creates an actual bool value when you dereference it:

pub struct BitRefMut<'a> {
    byte: &'a mut u8,
    bit: usize,
}

impl Deref for BitRefMut<'_> {
    type Target = bool;
    type Output<'a> = BitPlace;
    fn deref(&self) -> Self::Output<'_> {
        BitPlace { value: *self.byte & (1 << self.bit) != 0 }
    }
}

struct BitPlace {
    value: bool,
}

impl Deref for BitPlace {
    type Target = bool;
    fn deref(&self) -> &Self::Target {
        &self.value
    }
}

impl DerefMut for BitRefMut<'_> {
    type Output<'a> = BitPlaceMut<'a>;
    fn deref_mut(&mut self) -> Self::Output<'_> {
        BitPlaceMut { value: *self.byte & (1 << self.bit) != 0, byte: self.byte, bit: self.bit }
    }
}

struct BitPlaceMut<'a> {
    value: bool,
    byte: &'a mut u8,
    bit: usize,
}

impl Deref for BitPlaceMut<'_> {
    type Target = bool;
    fn deref(&self) -> &Self::Target {
        &self.value
    }
}

impl DerefMut for BitPlaceMut<'_> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.value
    }
}

impl Drop for BitPlaceMut<'_> {
    fn drop(&mut self) {
        let bit = 1 << self.bit;
        if self.value {
            *self.byte |= bit;
        } else {
            *self.byte &= !bit;
        }
    }
}

[traviscross]

cc @eholk, who is working on pin ergonomics.

[traviscross]

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?

So, I've thought a lot about this recently (resulting in more review comments over on rust-lang/reference#1725), and I'm not seeing a problem here (famous last words, I know). The reason is essentially the one you gave, from the RFC:

The possible self types in the method call expression are unchanged - they're still obtained by searching the Deref chain for t - but we'll look in more places for methods with those valid self types.

The way the algorithm works conceptually is as follows:

• We construct the unordered set of receiver candidates, starting with T, by walking down T = <T as Receiver>::Target.
• We construct the ordered set of deref candidates, starting with T, by walking down T = <T as Deref>::Target.
• We add an entry for an unsized coercion, if applicable (details elided).
• We walk both sets and insert autoref entries after each type.
• We identify impl blocks to search for candidate methods by checking whether each item in the receiver set could be the Self type for that impl block.
• Within those impl blocks, we collect into an unordered set of candidate methods those methods where the name matches and the self type matches a type in the deref set.
• We then iterate across the types in the deref set, in order, and query from the set of candidate methods for methods whose self type matches.
  • If there's one match, we resolve to that and exit.
  • If there are many matches, but only one is an inherent candidate (details elided), we resolve to that and exit.
  • If there are no matches, we continue.
  • Otherwise, we raise an ambiguity error.
• If we haven't found a match, we raise an error.

Prior to arbitrary self types, the receiver set was equal to the deref set and the set of type constructors that could be applied to the Self type in method self types was fixed.

The expanded receiver set causes us to search more impl blocks. Within those blocks, the criteria for a candidate method is the same as it was before. There are now more possible self types for any given impl block, but not more possible self types for any given deref chain.

If we later expand that autoref step to add more entries, that all still seems fine. At least, I'm not seeing how searching more impl blocks and allowing more composition of Self in self types within those blocks, as with arbitrary self types, would make anything a problem for that that isn't already.

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.

Regarding this, I'm meaning to look into, and I'd be curious to hear, what the constraints in the impl are. In an ideal implementation of the algorithm, this doesn't seem much a problem, since we can search a set in constant time, but it'd be good to know if that's not possible here for some reason. Without precedence between arbitrary autoref type constructors, the final picking step scales with only the length of the deref chain before autoref -- and we could do even better than that by treating the deref set as an unordered set of (Type, Depth) tuples and doing just a single set intersection with the candidate methods by self type.

[tmandry]

@traviscross The intuition you have is what sent me down the rabbit hole of writing my long comment above. In short I believe it is more complicated than doing a straightforward set lookup, because we have to perform type unification with every candidate. When you have an impl<T> Foo for T where ... that might apply to your pointer type there is no type to use as a lookup key, you just have to go check the where clause to see if the impl applies.

The limitation I describe is to disallow user-defined autoref from applying through these "opaque" impls and only apply when the autoref type is named in the impl (on the impl block or in the self type of a method). This means that when considering a candidate we only have to consider user-defined autoref in the places naming a type with an Autoref impl, instead of extending the current strategy of trying every possible autoref on each candidate and seeing what sticks.

[traviscross]

Yes, you're right of course. I had tenuously in mind for that a scheme where one would elaborate receiver rows with bounds satisfied and the index for them with inner parts of the type recursively replaced with placeholders, with the idea being to frontload some cost by building this database, essentially, so that the query cost could remain constant (or at least log(N)) with respect to the size of the receiver set. E.g. given impl<T: Copy> Tr for W<T> where Self: Copy ... we'd query for a W<_>: Copy receiver, then we'd expand that _ from the row, and query to check whether _: Copy also. (In a way, this is similar to what you propose with those adjustments, but applied earlier in the flow.) Could something like that work? I don't know. Intuitively, it feels that there should be some DB-oriented approach for decoupling that Depth * Autorefs cost from the number of methods to search. That'd need much more analysis, of course, and who knows whether it'd be a win as compared to just caching query results as we go along in the ordinary way.

Probably I wonder how much it actually matters. My guess would be that in a large program the number of custom autoref types would scale logarithmically with program size. So maybe the cost here, which is in the worst case linear in the number of autoref type constructors, wouldn't much matter. If they had to be brought explicitly in scope, that seems even more likely.

But, fortunately, we probably don't need to fully design an arbitrary autoref scheme right now. We just need to work out that stabilizing arbitrary self types doesn't close too many doors for it. That's the main thrust.

[cramertj]

Discussed in the lang meeting today-- overall there was relatively high shared confidence that stabilizing arbitrary_self_types will not significantly complicate the work needed for custom autoref.

Notably, this comment from the RFC:

a wider set of locations is searched for methods with those receiver types

only means having to search the impl blocks of Receiver target types, instead of only Deref target types. This isn't a concerningly large increase-- most types will still only have Deref types in their candidate type set, and the additional number of Receiver impls is likely to small.

Thanks for the discussion here!