Automatic dereferencing or borrowing on methods that exist behind a blanket (generic) trait implementation

language design
1

I first discovered this issue, and then asked this question on StackOverflow: Why do I need to implement From for both a value and a reference? Shouldn't methods be automatically dereferenced or borrowed?

It was discovered that the problem was the blanket trait implementation, which caused automatic dereferencing or borrowing to no longer work. I then decided to raise this as an issue on GitHub: Automatic dereferencing or borrowing on methods that exist behind a blanket (generic) trait implementation.

What is the problem?

The behaviour of a Rust method call is described in The Rust Reference, whereby it states that "when looking up a method call, the receiver may be automatically dereferenced or borrowed in order to call a method." The exact specification of this behaviour is explained in more detail in the chapter.

To do this a list of "candidate receiver types" is constructed. For example, given a "receiver type" of &usize it would be expanded through repeated dereferences to become &usize and usize. Next, as it has no unsized coercion, the list would be unchanged. Then, for each type in the list T, both &T and &mut T would be added immediately after T, thefore the list would become &usize, &&usize, &mut &usize, usize, &usize and &mut usize. Finally, any "visible method with a receiver of that type" is discovered. In the event that multiple matches are discovered, then this is an error and the exact method must be disambiguated.

Now, given a type T where From<T> for U is implemented and thus Into<U> for T is also implemented. Therefore, we should have the method U::from(T) and T::into(U). When I call T::into(U) it should and does work.

But, now when I call &T::into(U), it does not find an exact match. Since From<&T> for U is not implemented therefore Into<U> for &T is not implemented. However, it should still be possible to find a match through the automatic dereference and borrow procedure that was described above, but it does not.

Why is it a problem?

As explained in the answer on StackOverflow the reason for this is the blanket implementation of the Into trait. Due to the current way Rust attempts to resolve methods it appears to match the blanket implementation, but before it is fully resolved, therefore when the generic types are filled in there is actually no match.

I have created this reproduction on the Rust playground whereby you can uncomment section (A), (B), (C) or (D) to see the different behaviours. This example should be the easiest way to get a good understanding of this issue.

How can it be fixed?

I don't know if this can be fixed, but I believe the lookup routine could be adjusted. I expect there are other cases where this could be a problem, however the From and Into traits are the only place I have discovered this issue so far...

If it can be fixed, should it? Would this be a breaking change that requires a new edition of Rust?

EDIT: I should expand on how it should be adjusted. In the event that a blanket implementation is found, Rust should then check that trait for a concrete implementation under the constraints of the blanket implementation. The search should continue when no concrete implementation is found, instead of the current behaviour of being terminated. Would this cause a problem? Maybe. I guess the blanket implementation may one day be satisfied, which should therefore be an error and "the exact method must be disambiguated". However, if I am not mistaken this error can already occur in the current process.

2

There's a matching receiver for &A (<&'a A as Into<&'a A>>::into) so if it's true the compiler currently can't find <A as Into<B>>::into in this scenario, enabling it to find it wouldn't help without changing how method lookup works more drastically.

I'm not sure that it is really true that it can't find that method though, consider this playground that demonstrates you're out of luck due to the existence of an implementation with &A as a receiver. Then uncomment the generic implementation to see the error change, and delete either or both of the concrete implementations to see the errors change in new ways.

I suspect you're just getting different errors depending on how many candidate implementations there are and how generic they are.

3

I have expanded on your reproduction and tried to document it in this playground. I will use this as the basis of my discussion.

Hypothesis

The Rust follows the process as documented in the Rust reference.

  1. We call the method foo on &A. This is a visible method on the visible trait Foo.
  2. We then get the candidate receiver types of &A, A, ...

Case A: There is one implementation of Foo for &A.

  1. We get an error such as: expected i32, found &A.

Why? My guess: Rust finds one implementation of Foo for &A and decides to stop the method resolution. It then applies type inference and discovers it requires a return type of i32, but only one implementation exists with a return type of &A (or u32, or f32). Since the Rust compiler is nice, it displays a helpful error message that recommends that the type should be &A (or u32, or f32).

Case B: There are multiple implementations of Foo for &A.

  1. We get an error such as: the trait Foo<i32> is not implemented for &A.

Why? My guess: Rust finds multiple implementations of Foo for &A and decides to stop the method resolution. It then applies type inference and discovers it requires a return type of i32, but only implementations exist with a return types of &A, u32, f32. The Rust compiler cannot be as helpful in this instance, so it doesn't recommend a type, but instead displays a message that indicates there are no implementations of Foo for &A.

Case C: There is no implementation of Foo for &A.

  1. There is no error.

Why? My guess: Rust doesn't find any implementations of Foo for &A and therefore continues the method resolution. The next candidate receiver type is A, so it finds implementations of Foo for A. In the example above, there is only one implementation of Foo for A, but given there were multiple it would then apply type inference and attempt to find one with a return type of i32. In this case, there is only one implementation and it does have a return type of i32, therefore there is no error!

Conclusion

I don't think the different error messages have any impact on the process.

The process could be adjusted, such that when an implementation of T is found, type inference is then applied, but in the event that it still cannot find a match, the method resolution algorithm doesn't stop. It will then move on to the next candidate receiver types.

I do think any adjustment to the method resolution algorithm could still have problems...

  • An increase in the complexity of the method resolution algorithm. Bad for the compiler and the user.
  • An error now may compile, whereas in previous code it could not. I think this would require a new edition of Rust.
  • The compiler cannot help the user as much, as the error cases and search space becomes larger.

I don't know if I fully understood your comment, but I may just be super tired!

4

I'm saying that what candidates the process finds impacts the error messages.

I'm still not sure you understand that the algorithm is working as documented in this example.

When there is just 2 it works as you say. There's no &A receiver, there's no &&A receiver, there is no &mut &A receiver, but then it finds the A receiver. The return type matches and the call is made.

If 1, 3, or 4 is present, there is a foo method that takes &A as a receiver (but none of them return i32). The call cannot succeed with the current method resolution algorithm. The error messages differ based on the implementations which are found.

So the rest is just an analysis of how diagnostics work.

I suspect this is when there is one there is one receiver for a given candidate. Maybe that's what you meant.

The method resolution could stop there, as by the algorithm, there's "no point" as anything else it found wouldn't be called. First existing candidate receiver wins.

But it doesn't actually stop there (or diagnostics does additional queries). This case can be split into two subcases:

  • 2 doesn't exist: Error gives list of the implementations corresponding to &A receivers is shown (which have different return types than i32)
  • 2 does exist: Error suggests removing & which would result in calling the implementation in 2 and getting an i32.

It found your implementation and told you how to call it.

I don't know how to translate this into the example, or if you still have a concrete suggestion given the notes above.

5

I could be wrong, but I think we are in agreement? I agree that the current method resolution algorithm is working as intended. I just wrote out the process to make it clear how I arrived at that conclusion, so other people can follow my logic and double check that it is correct.

My suggestion was that we could consider a change to the method resolution algorithm.

At the moment it iterates through the list of candidate receiver types (&A, ..., A, ...) until an implementation is found. In this example, we start with Foo<T> for &A, and given an implementation is found, we then type inference is used to determine which Foo<T> for &A we should use. In this case, type inference can only accept Foo<i32> for &A.

Current behaviour:

  • In the event that Foo<i32> for &A is found: Success.

  • In the event that Foo<i32> for &A is not found: We do not continue the method resolution algorithm (as expected). Error.

New behaviour:

However, we could change the method resolution:

  • In the event that Foo<i32> for &A is found: Still a success.

  • In the event that Foo<i32> for &A is not found: We decide to continue the method resolution algorithm. We continue on to the next candidate receiver types which would be &&A, then &mut &A, then A. Both &&A and &mut &A don't have any implementation Foo<T>, so are skipped. A does have an implementation of Foo<T>. We perform type inference again and find that Foo<i32> for A does exist. Success.

6

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