Trait implementation for reference to trait causes stack overflow at runtime

[devyn]

The following code produces a stack overflow at runtime, only when optimizations are turned off.

The behavior that occurs once optimizations are turned on is odd, too: "called Option::unwrap() on a None value" even though I don't see any way a None could possibly be produced, but presumably LLVM eliminates the recursive call to testcase::&'a T.Tag::to_tag somehow and the stack overflow doesn't occur anymore.

use std::sync::Arc;

pub trait Tag {
  fn to_tag(&self) -> Option<Arc<String>>;
}

impl Tag for Arc<String> {
  fn to_tag(&self) -> Option<Arc<String>> {
    Some(self.clone())
  }
}

impl Tag for String {
  fn to_tag(&self) -> Option<Arc<String>> {
    Some(Arc::new(self.clone()))
  }
}

impl<'a> Tag for &'a str {
  fn to_tag(&self) -> Option<Arc<String>> {
    Some(Arc::new(self.to_string()))
  }
}

impl<'a, T: Tag> Tag for &'a T {
  fn to_tag(&self) -> Option<Arc<String>> {
    self.to_tag()
  }
}

impl<T: Tag> Tag for Option<T> {
  fn to_tag(&self) -> Option<Arc<String>> {
    self.as_ref().and_then(|t| t.to_tag())
  }
}

fn main() {
  let tag = "hello".to_tag();

  println!("{}", *tag.as_ref().to_tag().unwrap())
}

Snippet of gdb backtrace:

#0  0x000000000045561a in rust_stack_exhausted ()
#1  0x00000000004050e1 in __morestack ()
#2  0x0000000000404f61 in testcase::&'a T.Tag::to_tag (self=0x7fffffffc810) at testcase.rs:27
#3  0x0000000000404f61 in testcase::&'a T.Tag::to_tag (self=0x7fffffffc810) at testcase.rs:27
#4  0x0000000000404f61 in testcase::&'a T.Tag::to_tag (self=0x7fffffffc810) at testcase.rs:27
...

Obviously this can just be fixed by correcting that particular implementation to:

impl<'a, T: Tag> Tag for &'a T {
  fn to_tag(&self) -> Option<Arc<String>> {
    (**self).to_tag()
  }
}

but I feel like the compiler should be able to detect this and either resolve the cycle or throw an error.

[huonw]

I've been tripped up by this too, I've thought about writing a lint that detects when a function/method is being called directly inside itself on the same arguments but never got around to it; I don't think it would be too hard, but I'm not sure. (Happy to mentor if someone feels like doing this; find me here, on IRC as huon or via email (in my github profile).)

but presumably LLVM eliminates the recursive call to testcase::&'a T.Tag::to_tag somehow

Yes, LLVM optimises away side-effect-less infinite recursions sometimes: http://llvm.org/bugs/show_bug.cgi?id=965

@huonw Closing this now that #20373 is merged.