Trait bounds and method lookup

help
1

An area of the Rust documentation I've always felt lacked some details is the method lookup process, namely the page in the Rust Reference about method-call expressions, with particular regard to the (completely omitted) explanation about how trait bounds in where clauses intervene in the process of method selection.

I'm sorry that the following description is quite lengthy, but if you have the patience to bear with me, I'll give an example of a situation where I encounter a puzzling behavior.

Imagine having the following structs:

#[derive(Debug)]
pub struct Foo;
#[derive(Debug)]
pub struct Bar;
#[derive(Debug)]
pub struct FooRef;

impl std::ops::Deref for FooRef {
    type Target = Foo;
    fn deref(&self) -> &Foo {
        &Foo
    }
}

Bar leads its own solitary life, whereas FooRef can dereference to Foo.

Let's now consider two traits which resemble a home-made version of Into and From. To distinguish them from the standard ones, I'll use a double oo in their names:

// active conversion
trait Intoo<U> {
    fn intoo(&self) -> U;
}

// passive conversion
trait Froom<T> {
    fn froom(_: &T) -> Self;
}

We want to achieve the following:

  • we want active and passive conversions from Foo to Bar;
  • whereas we want to convert from FooRef to Bar only by passing through Foo, with implicit auto-dereference.

The obvious way seems to be

// blanket implementation
impl<T, U> Intoo<U> for T
where
    U: Froom<T>,
{
    fn intoo(&self) -> U {
        U::froom(self)
    }
}

// conversions Foo -> Bar
impl Froom<Foo> for Bar {
    fn froom(_: &Foo) -> Bar {
        Bar
    }
}

but then we notice that the following does not compile:

fn main() {
    let fooref: FooRef = FooRef;
    let bar: Bar = fooref.intoo();
    println!("{:?} {:?}", fooref, bar);
}

Apparently, the blanket implementation impl Intoo<Bar> for FooRef is not skipped, even though the where clause Bar: Froom<FooRef> is not satisfied. Therefore this method is selected as the "correct candidate", but it then fails to pass the trait bounds check at a later stage.

Ok, so maybe the method is not skipped because the trait bound in the where clause is a bound on the parameter U and not the type T itself, which is the subject of the impl. Let's try adding a bound on T. We introduce a new trait that controls whether the blanket implementation is available and then signal that we want it for Foo: Intoo<Bar>:

trait CanAutoIntoo<U> {}

impl CanAutoIntoo<Bar> for Foo {}

// blanket implementation
impl<T, U> Intoo<U> for T
where
    U: Froom<T>,
    T: CanAutoIntoo<U>,
{
    fn intoo(&self) -> U {
        U::froom(self)
    }
}

Excellent! The code now compiles as expected! During the method lookup process, it was noticed that FooRef: Intoo<Bar> is unavailable since FooRef: CanAutoIntoo<Bar> is not satisfied, hence the method was skipped and fooref gets auto-dereferenced to Foo, which implements Intoo<Bar>. Victory!

However, surely we don't want to manually implement CanAutoIntoo every time we implement Froom in order to get the blanket implementation too. We should try to implement CanAutoIntoo automatically. The obvious way is

impl<T, U> CanAutoIntoo<U> for T where U: Froom<T> {}

Very mysteriously however, this change breaks the compilation again! Even though FooRef: CanAutoIntoo<Bar> is cleary unsatisfied, this time around the method is not skipped and the compiler complains that Bar: Froom<FooRef> is unsatisfied, instead of moving along and dereference fooref to Foo.

After this long journey, I can formulate my question.

How do where clauses and trait bounds exactly intervene in the decision process whether to accept or skip a method during method lookup?

It seems to me that only some bounds are taken into consideration during an initial pass to select a candidate, and then only afterwards all the bounds are actually verified to confirm that the selection was indeed a good one.

Why does changing from impl CanAutoIntoo<Bar> for Foo {} to impl<T, U> CanAutoIntoo<U> for T where U: Froom<T> {} alter the selection of the method? In the former case the method is skipped, in the latter it is not. I find this behavior very confusing, if not actually irritating. What is the difference in nature between the former and the latter that causes the trait bound T: CanAutoIntoo<U> to behave differently in the blanket implementation?

1 Like
2

To add another datapoint to your observations, changing the roles of Self-type and type argument in the CanAutoIntoo trait breaks the code, too. I.e. swapping the T and U as in

trait FroomWithAutoIntoo<T> {}

impl FroomWithAutoIntoo<Foo> for Bar {}

// blanket implementation
impl<T, U> Intoo<U> for T
where
    U: Froom<T>,
    U: FroomWithAutoIntoo<T>,
{
    fn intoo(&self) -> U {
        U::froom(self)
    }
}

(playground)

So apparently for the rules currently implemented in rustc, it seems like it’s important whether T appears as Self-type or otherwise in the bounds on the blanket Intoo impl.

Regarding your question about the blanket CanAutoIntoo implementation, I’m not so much surprised by the behavior there. I really don’t know the true rules at all, but if for blanket implementations on a generic type T, only T: ... bounds are considered, recursively, to answer the question of whether a method “exists” on a type or not, then the blanket CanAutoIntoo pushes the problem down the road and kind-of runs into the same thing that prevented the code from compiling in the first place.

  • Without any CanAutoIntoo helper trait, FooRef was considered to “have” an intoo method because it “has” an Intoo implementation; that’s because the generic Intoo for T method places no bounds on T directly,
  • with CanAutoIntoo generically implemented, FooRef is only considered to have an intoo method (i.e. considered to “have” an Intoo implementation) if FooRef has a CanAutoIntoo implementation; but following the same logic the blanket CanAutoIntoo for T implementation places no further T: ... bound, so it’s always considered.

That’s my interpretation of what the compiler might be “thinking” in its method lookup logic; I’d probably prefer if the logic could be better and just not consider a method at all unless all the relevant bounds are fulfilled. I’m not sure whether there are code examples where this would be resulting in unexpected behavior (code compiling when it shouldn’t and doing stuff you don’t want it to do). I’m also not sure what technical limitations in the compiler might be preventing more clever behavior here and/or whether chalk might eventually give more opportunity for improving the behavior.

1 Like
3

Yes, although I don't necessarily agree that this should be the "correct" behavior, I would have predicted it on the basis that now U: FroomWithAutoIntoo<T> is completely analogous to U: Froom<T>, hence it doesn't force the method to be skipped.

I also completely agree with your analysis here. I know that I just kicked the problem down the road, but it was for the sole purpose of making less obvious why the blanked implementation applies even if there is an unsatisfied bound on T itself just by looking at it. You are forced to examine the traits mentioned in the bounds to see whether they are considered "active" or not. Your description of the recursive nature of the implementation seems to capture well the observed behavior, but I'm arguing that it can be very surprising nonetheless.

This is precisely my sentiment too.

Probably the under-defined nature of the problem can be highlighted by the fact that you had to resort to expressions like "exists", "has", "have" to refer to implementations that would be valid if all the bounds were satisfied.

Maybe a distinction has to be drawn between implementations which are actually available (all bounds are satisfied) and implementations which are "considered available by a first negligent pass" but have some unsatisfied bound. What is the rationale for this distinction? Is this a really inevitable fundamental issue, or can the logic for determining whether a method is available be refined? If such a distinction exists and is bound to exist for a long time (pun intended), maybe it should be documented while explaining the method lookup process.

Let's hope a Rust guru jumps in :slight_smile:

4

I agree with @steffahn's assesment. My own hypothesis to justify these empricial observations is that this is the result of:

  • a (lack of) interaction between method resolution and type inference: we may imagine that the type U in foo_ref.intoo() is known, but it isn't!

  • a "lazy" method lookup algorithm.

The compiler sees FooRef as a possible receiver for .intoo(), where the whole thing would be applicable, given a currently not yet known U? (inference variable) type,

  1. if FooRef : Intoo<U?>

  2. if:

    • FooRef : CanAutoIntoo<U?>,

    • U? : Froom<FooRef>,

The "lazy" part is that this approach will not really try to guess U? / trait impl "preimages": that could be expensive (I guess?), and if multiple applicable types were to appear, then it would still be for the job of the follow-up pass of type inference to tackle identifying those. So, for, instance, things like the second bound will just be dismissed, and let for the type inference algorithm to handle.

But the FooRef : … is another story. There is no "preimage" trait resolution, quite the opposite, so the method look up does try to find if "that generic trait is implemented".

  • In your approach with the non-blanket impl of that trait, that generic trait is not implemented whatsoever, so it can dismiss this FooRef candidate receiver of the method, and keep digging (to reach the Deref point).

    • This approach can be confirmed by experimenting with an impl CanAutoIntoo<()> for FooRef {} addition: with it, the "generic trait is not implemented" step fails —the "generic trait is implemented fails to fail, we could say—, and thus there seems to be a potential candidate by the method resolver, leaving it to the type inference to later on observe that FooRef: CanAutoInto<U?> and U? = Bar are two things impossible to conciliate.

  • In your approach with a blanket impl, it just brings it back to your very first situation (no CanAutoIntoo, as Steffahn said).

  • In the "no CanAutoIntoo" trait bound situation, it thus has the fact that that FooRef would be a valid receiver for all of the U? types where U? : From<FooRef>. It can "thus" let type inference sort these things out, to know which one type U? it is exactly. The issue is in that "thus": it's only fully correct to use this approach when we know there is at least one possible candidate. So, ideally, the method resolution algorithm should try to perform a minimal amount of "trait impl preimage search" to know of the existence of solutions. At least some basic heuristics so that in cases such as this simple one, it can realize there are no solutions, and that it should therefore not let type inference miserably fail to solve the constraints, and that it should, instead, consider this method lookup to be non-eligible and try the next round of possible applicants.

1 Like
5

Thanks for the very detailed explanation. Distinguishing the method resolution and type inference passes really clarifies the inner workings. Your example with impl CanAutoIntoo<()> for FooRef {} is particularly eye opening: it is very surprising a priori, but makes perfect sense with your decription.

So in a certain sense there a two notions of "available implementations" during method lookup:

  1. "superficially available", meaning that all the trait bounds on the type itself are recursively "superficially available" but there may be some indeterminate bounds involving other type variables;
  2. "actually available", meaning that the type inference will not fail to unify the type variables.

During lookup, finding a "superficially available" implementation does not cause the method to be skipped, even if it turns out to not be satisfiabe by the later type inference pass.

Ok, so I agree this is a satisfactory description of the current implementation. Now for the most important question: is it really unavoidable?

In my mind, writing impl<T,U> CanAutoIntoo<U> for T where U: Froom<T> should be really just a shortcut to write all the specific impl CanAutoIntoo<Bar> for Foo etc., it shouldn't interfere with method selection.

Are there fundamental reasons why the current behavior is "the correct one"? Is it just a limitation (for efficiency/simplicity?) in order to separate method lookup and type inference? Will Chalk address this issue differently? Is this aspect susceptible to change in the future? I don't see what could go wrong if rustc started accepting my first example as valid.

Edit: also, as a side note, I find the error message in your example with impl CanAutoIntoo<()> for FooRef particularly intricate, since rustc insisted in picking the wrong candidate and then type inference causes mayhem.

1 Like
6

Type inference in Rust, and Rust’s type system + trait system in general, stems from other languages like e.g. Haskell that don’t have anything like Rust’s method-lookup. The type inference is not designed to interact nicely with method-lookup, hence it doesn’t. This is probably a theoretical problem even; AFAIK the fact that type inference works as smooth as it does in languages like Haskell is because the constraints involved are well-formed; they come in the form of signatures of generic functions with trait bounds, and only in this form. In Haskell, without language extensions, you often technically don’t need to write a single type annotation at all.

When doing method-lookup you’re looking up the method depending on the receiver-type (i.e. the Self-type); the function-signature is only known once the method-lookup is complete. The way in which the function-signature depends on the Self-type is highly nontrivial, and non-regular in a way that the type inference algorithm cannot support.

The way out that rustc seems to take (only my intuition based on observarion/experience, no guarantees for any accuracy or correctness) is to incrementally add more and more information to type inference and retrieve information from type inference interactively; e.g. you could add the type inference goals and information line-by-line or subexpression-by-subexpression; and every time you hit a method-call expression, you first query your type inference infrastructure about what’s already known about the receiver type.

This means two things:

  • the receiver type must be fully known (or fully known to some degrees) before encountering a method expression. Type information that only comes after a method call cannot help anymore.

    This leads to examples like

    use std::ops::Add;

/// WORKS
fn foo1() {
    let x = Default::default();
    let y = x + x;
    let z: u64 = x;
}
/// WORKS!
fn foo2() {
    let x = Default::default();
    let z: u64 = x;
    let y = x.add(x);
}
/// DOESN’T WORK!
fn foo3() {
    let x = Default::default();
    let y = x.add(x); // method-call syntax
    let z: u64 = x; // crucial information comes *AFTER* method-call
}
/// WORKS!
fn foo4() {
    let x = Default::default();
    let y = <_>::add(x, x);
    let z: u64 = x;
}

  • only the Self-type can be used for method-resolution, things like the return-type can’t be used; the surrounding expression/statement probably hasn’t even been looked at at all for type inference, so the return-type is completely unknown to the compiler anyways. Argument-types aren’t considered either, because they are not forced to be known yet. (You won’t get any errors like in foo3 above when the argument type of a method call wasn’t known from information that comes syntactically before that method call.)

Why your code example can’t work is already fully explained by that; together with orphan rules. I’ll retract my expectation that

and instead claim that things might already be working as good as they can, or that it’s at least highly nontrivial to improve the situation. Let me explain.

Your code example (the first playground link in the OP) uses

let bar: Bar = fooref.intoo();

Now, considering fooref: FooRef is known at this time to type inference, now it’s time to look up an intoo method without taking the return type into consideration. (The let statement is only handled after method-lookup of the fooref.intoo() is finished.)

If you don’t know the return type to look up fooref.intoo(), orphan rules strike: With a generic implementation based on Froom, what if a downstream crate defined a type Qux and implements Froom<FooRef> for Qux? Suddently fooref.intoo() would refer to a method that exists (at least downstream), and you wouln’t want to resolve the same call fooref.into() with the same traits in scope to a different method depending on what crate this call happens in, would you?!?

Really –considering orphan rules – the only way how

let bar: Bar = fooref.intoo();

ever could use a deref to Foo legitimately is when return types are considered; but this would mean that type inference somehow already considers the surrounding statement (in order to determine the return type) before the method-resolution finishes. Maybe possible, but at least not straightforward, probably fairly nontrivial.

Maybe some improvement could be achieved by doing 2 passes of type-inference+method-lookup, a first type-inference-only pass where no methods (in method-syntax) are looked up at all and all type information that can be found out and then a second one similar to current inference, where (AFAICT) the methods are looked up in order of syntactical appearance. It’s probably possible to make examples like foo3 above compile; regarding your code however, we’d first need to ask the question of whether we even want method-lookup to depend on anything other than the Self-type. If the answer to that is no, then I’d say that the two playgrounds in your OP that don’t compile do so for good reason, when you consider what downstream trait implementations are allowed to exist under Rust’s orphan rules.

2 Likes
7

Now that I wrote this answer I remember that orphan rules also allow concrete implementations impl Trait<Type1> for Type2 where Type2 and Trait are external; so the argument

might be kind-of invalid because that’s already what’s happening? :thinking:

I’ll try to build an example now… okay, let’s take a look at your second playground. But remove the type signature on bar, so

fn main() {
    let fooref: FooRef = FooRef;
    let bar = fooref.intoo();
    println!("{:?} {:?}", fooref, bar);
}

is used.

Now, adding

#[derive(Debug)]
pub struct Qux;
impl Froom<FooRef> for Qux {
    fn froom(x: &FooRef) -> Qux {
        Qux
    }
}

impl CanAutoIntoo<Qux> for FooRef {}

changes the behavior of the code in main.

Let me next double-check that this has the effect that it’s also possible that just adding a dependency can change the behavior of your code...

8

Yes it does! This is slightly disturbing.... my setup:

Cargo.toml

[workspace]

members = [
    "first_dep",
    "second_dep",
    "main_crate",
]

first_dep/Cargo.toml

[package]
name = "first_dep"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]

first_dep/src/lib.rs

#[derive(Debug)]
pub struct Foo;
#[derive(Debug)]
pub struct Bar;
#[derive(Debug)]
pub struct FooRef;

impl std::ops::Deref for FooRef {
    type Target = Foo;
    fn deref(&self) -> &Foo {
        &Foo
    }
}

// active conversion
pub trait Intoo<U> {
    fn intoo(&self) -> U;
}

// passive conversion
pub trait Froom<T> {
    fn froom(_: &T) -> Self;
}

pub trait CanAutoIntoo<U> {}

impl CanAutoIntoo<Bar> for Foo {}

// blanket implementation
impl<T, U> Intoo<U> for T
where
    U: Froom<T>,
    T: CanAutoIntoo<U>,
{
    fn intoo(&self) -> U {
        U::froom(self)
    }
}

// conversions Foo -> Bar
impl Froom<Foo> for Bar {
    fn froom(_: &Foo) -> Bar {
        Bar
    }
}

second_dep/Cargo.toml

[package]
name = "second_dep"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]

first_dep = { path = "../first_dep" }

second_dep/src/lib.rs

use first_dep::*;

#[derive(Debug)]
pub struct Qux;
impl Froom<FooRef> for Qux {
    fn froom(_: &FooRef) -> Qux {
        Qux
    }
}

impl CanAutoIntoo<Qux> for FooRef {}

pub fn f() {}

main_crate/Cargo.toml

[package]
name = "main_crate"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]

first_dep = { path = "../first_dep" }
second_dep = { path = "../second_dep" }

main_crate/src/main.rs

use first_dep::*;

fn _g() {
    // second_dep::f(); // uncomment this line to change the behavior
                        // of `main` function!
}

fn main() {
    let fooref: FooRef = FooRef;
    let bar = fooref.intoo();
    println!("{:?} {:?}", fooref, bar);
}
1 Like
9

Dear @steffahn, thanks for your well thought response and example. I have to admit that I'm quite confused about this matter as to what should be a good solution.

Originally I was thinking about a backtracking method lookup, that selects a method candidate, proceeds with type inference, and if that is unsatisfiable it backtracks and tries the next candidate, until there are no more, at which point it fails.

Playing around a bit with your example (I uploaded it as a GitHub repo), I realized that it still fails even if you make the Qux struct private and you use the dependency in an inner private submodule. Inside the main function Rust still considers FooRef to implement CanAutoIntoo<_> for some type and tries to call <FooRef as Intoo<_>>::intoo(&fooref) instead of dereferencing it.

Edit
I should probably add that I didn't come here to fight for a change. If the current behavior is really what is desired, then I would merely ask for a clarification of the rules that determine under what circumstances a trait is considered to be "available" during the method lookup process and how it affects the selection of the candidate.

10

For the record, I’ve filed an issue on the behavior:

https://github.com/rust-lang/rust/issues/90907

1 Like
11

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.