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

Opened by Tom Jakubowski at 2022-03-22 08:18:30

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).

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();
                             ^~~~~~~

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`.

Dylan DPC at 2024-08-23 07:25:45

Why was this issue closed? I tried on th playpen and it still gives the same error.
Thiez at 2014-12-26 13:36:48
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?
Matt Brubeck at 2015-10-08 19:40:19
Also reported by @skeleten
Brian Anderson at 2015-10-08 22:50:47
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
Brian Anderson at 2015-10-08 22:51:49
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).
Eduard-Mihai Burtescu at 2015-10-08 23:39:05

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();
}

skeleten at 2015-10-09 01:04:34

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".
Niko Matsakis at 2015-10-14 23:29:47
changing to T-lang because I think there is a language question here of the expected semantics of recursive autoderef.
Niko Matsakis at 2015-10-15 20:18:36
IMHO, the language should use the type that requires the least deref's. This is how it currently works if more than one type in the chain matches. I'm not sure how the algorithm should be laid out. Your point about hitting the recursion limit not being the best option is very valid. However, simply doing a lookup back onto all the previously deref'd types would introduce a higher overhead when if we have larger chains. I also don't believe, that cycles itself should be forbidden, as they might prove usefull.
skeleten at 2015-10-16 23:58:07
triage: P-low

We discussed this in the @rust-lang/lang meeting some today. General conclusion was that if we can in fact detect a cycle, that is probably OK. It's worth pointing out there is some code in trait matching that aims to detect similar cycles -- it does have some problems around regions though -- but also that we can probably ignore regions for the purposes of establishing these cycles. This may take a bit of investigation. However, basically if we DO detect cycles the proper way (not merely by exceeding the recursion limit), then it seems ok to permit cutting off the method call candidate search there.

Classifying as low priority because while this use case would be nice to support, it's not urgent.
Niko Matsakis at 2015-10-23 18:54:35
According to src/librustc_typeck/check/method/README.rs looking up all the deref's is just the first step of the method probing; Do you think maintaining a collection of all previously seen types and terminating once we see a type for the second time would be a valid solution to this issue?

Edit: I mean like this
skeleten at 2016-01-17 18:15:42
Do you think maintaining a collection of all previously seen types and terminating once we see a type for the second time would be a valid solution to this issue?

No, because you could always construct new types at every level using generics.
Michael Howell at 2016-03-04 00:06:39
Triage: not aware of any movement here.
Steve Klabnik at 2019-03-11 17:25:45
Triage: no change
Maayan Hanin at 2022-03-22 08:18:30