Method lookup goes down the auto-deref rabbit hole when it doesn't need to

[tomjakubowski]

Here's a pathological example of two types, each implementing Deref on the other:

use std::ops::Deref;
use std::rc::Rc;

struct Foo;
struct Bar;

impl Deref<Bar> for Foo {
    fn deref<'a>(&'a self) -> &'a Bar {
        panic!()
    }
}

impl Deref<Foo> for Bar {
    fn deref<'a>(&'a self) -> &'a Foo {
        panic!()
    }
}

fn main() {
    let foo = Rc::new(Foo);
    let foo2 = foo.clone(); 
}

<anon>:21:20: 21:27 error: reached the recursion limit while auto-dereferencing alloc::rc::Rc<Foo> [E0055]
<anon>:21     let foo2 = foo.clone();
                             ^~~~~~~

Even though Rc<T> implements Clone and thus has a clone method, method resolution still tries to look up methods available via deref. This also happens for trying to call inherent methods on a Foo directly (without using Rc).

Update:

Modern code on playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=2ca8f056b69c0cd8e4ce0365a6356f02

Current error (as of 2024):

error[E0055]: reached the recursion limit while auto-dereferencing `Foo`
  --> src/main.rs:23:20
   |
23 |     let foo2 = foo.clone(); 
   |                    ^^^^^ deref recursion limit reached
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`playground`)

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

[Thiez]

Why was this issue closed? I tried on th playpen and it still gives the same error.

[mbrubeck]

This code still fails with the same error in Rust 1.5.0-nightly (after updating it to match the current Deref trait signature). Can this be re-opened?

[brson]

Also reported by @skeleten

[brson]

Nominating this just to raise visibility since it was thought fixed but seems not to be. @skeleten is interested in fixing it if somebody can point him the way. cc @rust-lang/compiler @nrc @pnkfelix @eddyb

[eddyb]

What happens is that method probing first collects all the types in the deref chain and only then attempts probing.
Stopping that collection at a cycle (or even just at the recursion limit) should work.

If a method wasn't found due to reaching the recursion limit, a recursion-limit-specific error could be used, but otherwise any result can be considered valid (ambiguities can only exist at the same deref level, not between levels).

[skeleten]

For reference, the adjusted code I'll be testing against:

use std::ops::Deref;

pub struct Foo {
    baz: Bar,
}
pub struct Bar;

impl Foo {
    pub fn foo_method(&self) {
        /* do something, doesn't really matter */
    }
}

impl Bar {
    pub fn bar_method(&self) {

    }
}

impl Deref for Foo {
    type Target = Bar;

    fn deref<'a>(&'a self) -> &'a Self::Target {
        &self.baz
    }
}

impl Deref for Bar {
    type Target = Foo;

    fn deref<'a>(&'a self) -> &'a Self::Target {
        panic!()
    }
}

fn main() {
    let foo = Foo {
        baz:    Bar,
    };
    let bar = Bar;

    // should work
    foo.bar_method();
    // should compile but panic on runtime
    bar.foo_method();
}

[nikomatsakis]

So, I'm not entirely convinced this is a bug. I'd certainly want to think carefully about any particular fix. For example, stopping at the recursion limit doesn't feel very good to me. IIRC (and this code has changed enough that my memory could easily be rusty (pun intended)), while we are expanding out the candidates, it can easily happen that a candidate after N derefs inserts something which is applicable to N-k derefs. For example, if we have a method like:

impl Bar {
    fn foo(self: Box<Rc<Self>>) // admittedly, not legal yet, but the code is trying to be prepared for it
}

then if we have a &Box<Rc<Bar>>, we have to deref 3 times to find out about the candidate which, in fact, will later match after only 1 deref.

It seems like stopping when we reach a cycle might be ok, but I don't like doing anything upon exceeding the recursion depth but reporting some sort of error. That has proven very hard to reason about in the past: the recursion depth is basically supposed to be the point where the compiler throws up its hands and says "this compile neither succeeds nor fails because I got stuck".

[nikomatsakis]

changing to T-lang because I think there is a language question here of the expected semantics of recursive autoderef.