Infinite recursion error instead of trait bound error

[dnorman]

Observed behavior:
Receiving the following error when attempting to compile the sample program.

Expected behavior:
Indicate that there is a trait bound error.

rustc 1.16.0 (30cf806ef 2017-03-10)
error[E0275]: overflow evaluating the requirement `TransmitterInternal: std::marker::Send`
  --> <anon>:22:16
   |
22 | fn g(x: Memo) {f(x)}
   |                ^
   |
   = note: consider adding a `#![recursion_limit="128"]` attribute to your crate
   = note: required because of the requirements on the impl of `std::marker::Sync` for `std::sync::Arc<TransmitterInternal>`
   = note: required because it appears within the type `SlabRef`
   = note: required because of the requirements on the impl of `std::marker::Sync` for `std::ptr::Unique<SlabRef>`
   = note: required because it appears within the type `alloc::raw_vec::RawVec<SlabRef>`
   = note: required because it appears within the type `std::vec::Vec<SlabRef>`
   = note: required because it appears within the type `TransmitterInternal`
   = note: required because of the requirements on the impl of `std::marker::Send` for `std::sync::Arc<TransmitterInternal>`
   = note: required because it appears within the type `SlabRef`
   = note: required because of the requirements on the impl of `std::marker::Send` for `std::ptr::Unique<SlabRef>`
   = note: required because it appears within the type `alloc::raw_vec::RawVec<SlabRef>`
   = note: required because it appears within the type `std::vec::Vec<SlabRef>`
   = note: required because it appears within the type `TransmitterInternal`
   = note: required because of the requirements on the impl of `std::marker::Sync` for `std::sync::Arc<TransmitterInternal>`
   = note: required because it appears within the type `SlabRef`
...

Minimal reproduction case:

https://is.gd/KgD5Tk
Many thanks to the tireless efforts of @stephaneyfx in creating the repro above!

Bonus round
I haven't yet figured out a minimal repro for this second part, but if I'm interpreting correctly, it's possible that a variant of this endless recursion error does not require a trait bound error to be triggered. (noob warning: it's possible that the omission of +Send+Sync in 4ab0fdf is actually a trait bounds error, but I don't presently understand why)

Non-minimal repro:
https://travis-ci.org/dnorman/unbase/jobs/209643435#L240

Minimal change that fixed it:
dnorman/unbase@47c68bf
https://travis-ci.org/dnorman/unbase/jobs/209649602#L228

[stephaneyfx]

This is a simplified example reproducing the issue (playground).

use std::rc::Rc;
use std::sync::Arc;

// Rc<_>: !Send
// => Bar: !Send
// => Arc<Bar>: !Send
// => Foo: !Send
//
// Shouldn't the compiler come to the same conclusion instead of entering this
// infinite recursion?
struct Foo(Arc<Bar>);

enum Bar {
    A(Rc<Foo>),
    B(Option<Foo>),
}

fn f<T: Send>(_: T) {}

fn main() {
    f(Foo(Arc::new(Bar::B(None))));
}

rustc 1.16.0 (30cf806ef 2017-03-10)
error[E0275]: overflow evaluating the requirement `Foo: std::marker::Send`
  --> <anon>:21:5
   |
21 |     f(Foo(Arc::new(Bar::B(None))));
   |     ^
   |
   = note: consider adding a `#![recursion_limit="128"]` attribute to your crate
   = note: required because it appears within the type `std::option::Option<Foo>`
   = note: required because it appears within the type `Bar`
   = note: required because of the requirements on the impl of `std::marker::Sync` for `std::sync::Arc<Bar>`
   = note: required because it appears within the type `Foo`
   = note: required because it appears within the type `std::option::Option<Foo>`
   = note: required because it appears within the type `Bar`
   = note: required because of the requirements on the impl of `std::marker::Send` for `std::sync::Arc<Bar>`
   = note: required because it appears within the type `Foo`
...

[stephaneyfx]

Note that if Rc is removed (or replaced by Arc, for example), the compiler does not enter this infinite recursion and deduces Foo is Send (playground).

[dnorman]

This is the case I was referring to @aturon :)

[aturon]

@dnorman Thanks! Fascinating bug...

[orium]

I think I have hit the same bug with

use std::rc::Rc;
use std::sync::Arc;

struct List {
    value: Rc<i32>,
    next:  Option<Arc<List>>
}

fn is_send() {
    let _: Box<Send> = Box::new(List { value: Rc::new(4), next: None });
}

error[E0275]: overflow evaluating the requirement `std::sync::Arc<List>: std::marker::Send`
  --> src/lib.rs:12:24
   |
12 |     let _: Box<Send> = Box::new(List { value: Rc::new(4), next: None });
   |                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
   = note: required because it appears within the type `std::option::Option<std::sync::Arc<List>>`
   = note: required because it appears within the type `List`
   = note: required because of the requirements on the impl of `std::marker::Sync` for `std::sync::Arc<List>`
   = note: required because it appears within the type `std::option::Option<std::sync::Arc<List>>`

I did some digging around in the trait resolver and I believe what causes it is pointed by @nikomatsakis in #30533 (comment):

1. If you find that a new obligation is a duplicate of one already in the tree, the proper processing is:
   • if that other location is your parent, you should abort with a cycle error (or accept it, if coinductive)
   • if that other location is not an ancestor, you can safely ignore the new obligation

If this is truly the cause of the bug I will give it a go and try to fix it, but I would really appreciate some mentoring instructions. @nikomatsakis can you give me a few pointers?