auto merge of #17815 : typelist/rust/recursive-structs, r=brson

The representability-checking routine ```is_type_representable``` failed to detect structural recursion in some cases, leading to stack overflow later on.

The first problem was in the loop in the ```find_nonrepresentable``` function. We were improperly terminating the iteration if we saw a ```ContainsRecursive``` condition. We should have kept going in case a later member of the struct (or enum, etc) being examined was ```SelfRecursive```. The example from #17431 triggered this issue:

```rust
use std::sync::Mutex;
struct Foo { foo: Mutex<Option<Foo>> }
impl Foo { fn bar(self) {} }
fn main() {}
```

I'm not 100% sure, but I think the ```ty_enum``` case of ```fn type_structurally_recursive``` had a similar problem, since it could ```break``` on ```ContainsRecursive``` before looking at all variants. I've replaced this with a ```flat_map``` call.

The second problem was that we were failing to identify code like ```struct Foo { foo: Option<Option<Foo>> }``` as SelfRecursive, even though we correctly identified ```struct Foo { foo: Option<Foo> }```. This was caused by using DefId's for the ```ContainsRecursive``` check, which meant the nested ```Option```s were identified as illegally recursive (because ```ContainsRecursive``` is not an error, we would then keep compiling and eventually hit a stack overflow).

In order to make sure that we can recurse through the different ```Option``` invocations, I've changed the type of ```seen``` from ```Vec<DefId>``` to ```Vec<t>``` and added a separate ```same_type``` function to check whether two types are the same when generics are taken into account. Now we only return ```ContainsRecursive``` when this stricter check is satisfied. (There's probably a better way to do this, and I'm not sure my code is entirely correct--but my knowledge of rustc internals is pretty limited, so any help here would be appreciated!)

Note that the ```SelfRecursive``` check is still comparing ```DefId```s--this is necessary to prevent code like this from being allowed:

```rust
struct Foo { x: Bar<Foo> }
struct Bar<T> { x: Bar<Foo> }
```

All four of the new ```issue-17431``` tests cause infinite recursion on master, and errors with this pull request. I wrote the extra ```issue-3008-4.rs``` test to make sure I wasn't introducing a regression.

Fixes #17431.

8 files changed, 123 insertions, 0 deletions

diff --git a/src/test/compile-fail/issue-17431-1.rs b/src/test/compile-fail/issue-17431-1.rs
new file mode 100644
index 00000000000..896a9c06873
--- /dev/null
+++ b/src/test/compile-fail/issue-17431-1.rs
@@ -0,0 +1,16 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+struct Foo { foo: Option<Option<Foo>> }
+//~^ ERROR illegal recursive struct type; wrap the inner value in a box to make it representable
+
+impl Foo { fn bar(&self) {} }
+
+fn main() {}
diff --git a/src/test/compile-fail/issue-17431-2.rs b/src/test/compile-fail/issue-17431-2.rs
new file mode 100644
index 00000000000..886fe8d771a
--- /dev/null
+++ b/src/test/compile-fail/issue-17431-2.rs
@@ -0,0 +1,19 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+struct Baz { q: Option<Foo> }
+//~^ ERROR illegal recursive struct type; wrap the inner value in a box to make it representable
+
+struct Foo { q: Option<Baz> }
+//~^ ERROR illegal recursive struct type; wrap the inner value in a box to make it representable
+
+impl Foo { fn bar(&self) {} }
+
+fn main() {}
diff --git a/src/test/compile-fail/issue-17431-3.rs b/src/test/compile-fail/issue-17431-3.rs
new file mode 100644
index 00000000000..c1c450935f6
--- /dev/null
+++ b/src/test/compile-fail/issue-17431-3.rs
@@ -0,0 +1,18 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::sync::Mutex;
+
+struct Foo { foo: Mutex<Option<Foo>> }
+//~^ ERROR illegal recursive struct type; wrap the inner value in a box to make it representable
+
+impl Foo { fn bar(&self) {} }
+
+fn main() {}
diff --git a/src/test/compile-fail/issue-17431-4.rs b/src/test/compile-fail/issue-17431-4.rs
new file mode 100644
index 00000000000..1e27f025564
--- /dev/null
+++ b/src/test/compile-fail/issue-17431-4.rs
@@ -0,0 +1,16 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+struct Foo<T> { foo: Option<Option<Foo<T>>> }
+//~^ ERROR illegal recursive struct type; wrap the inner value in a box to make it representable
+
+impl<T> Foo<T> { fn bar(&self) {} }
+
+fn main() {}
diff --git a/src/test/compile-fail/issue-17431-5.rs b/src/test/compile-fail/issue-17431-5.rs
new file mode 100644
index 00000000000..d22d79ecaa5
--- /dev/null
+++ b/src/test/compile-fail/issue-17431-5.rs
@@ -0,0 +1,18 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+struct Foo { foo: Bar<Foo> }
+struct Bar<T> { x: Bar<Foo> }
+//~^ ERROR illegal recursive struct type; wrap the inner value in a box to make it representable
+
+impl Foo { fn foo(&self) {} }
+
+fn main() {
+}
diff --git a/src/test/compile-fail/issue-17431-6.rs b/src/test/compile-fail/issue-17431-6.rs
new file mode 100644
index 00000000000..8eac295353d
--- /dev/null
+++ b/src/test/compile-fail/issue-17431-6.rs
@@ -0,0 +1,18 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::sync::Mutex;
+
+enum Foo { X(Mutex<Option<Foo>>) }
+//~^ ERROR illegal recursive enum type; wrap the inner value in a box to make it representable
+
+impl Foo { fn bar(self) {} }
+
+fn main() {}
diff --git a/src/test/compile-fail/issue-17431-7.rs b/src/test/compile-fail/issue-17431-7.rs
new file mode 100644
index 00000000000..c64c040aa44
--- /dev/null
+++ b/src/test/compile-fail/issue-17431-7.rs
@@ -0,0 +1,16 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+enum Foo { Voo(Option<Option<Foo>>) }
+//~^ ERROR illegal recursive enum type; wrap the inner value in a box to make it representable
+
+impl Foo { fn bar(&self) {} }
+
+fn main() { }
diff --git a/src/test/compile-fail/issue-3008-3.rs b/src/test/compile-fail/issue-3008-3.rs
index b8ef57e2dd3..a338a01690d 100644
--- a/src/test/compile-fail/issue-3008-3.rs
+++ b/src/test/compile-fail/issue-3008-3.rs
@@ -12,5 +12,7 @@ enum E1 { V1(E2<E1>), }
 enum E2<T> { V2(E2<E1>), }
 //~^ ERROR illegal recursive enum type; wrap the inner value in a box to make it representable
 
+impl E1 { fn foo(&self) {} }
+
 fn main() {
 }