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.

9 files changed, 240 insertions, 62 deletions

diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 832e9a79aca..0a5691541f1 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -2792,11 +2792,14 @@ pub fn is_instantiable(cx: &ctxt, r_ty: t) -> bool {
 /// distinguish between types that are recursive with themselves and types that
 /// contain a different recursive type. These cases can therefore be treated
 /// differently when reporting errors.
-#[deriving(PartialEq)]
+///
+/// The ordering of the cases is significant. They are sorted so that cmp::max
+/// will keep the "more erroneous" of two values.
+#[deriving(PartialOrd, Ord, Eq, PartialEq, Show)]
 pub enum Representability {
     Representable,
-    SelfRecursive,
     ContainsRecursive,
+    SelfRecursive,
 }
 
 /// Check whether a type is representable. This means it cannot contain unboxed
@@ -2804,87 +2807,136 @@ pub enum Representability {
 pub fn is_type_representable(cx: &ctxt, sp: Span, ty: t) -> Representability {
 
     // Iterate until something non-representable is found
-    fn find_nonrepresentable<It: Iterator<t>>(cx: &ctxt, sp: Span, seen: &mut Vec<DefId>,
+    fn find_nonrepresentable<It: Iterator<t>>(cx: &ctxt, sp: Span, seen: &mut Vec<t>,
                                               mut iter: It) -> Representability {
-        for ty in iter {
-            let r = type_structurally_recursive(cx, sp, seen, ty);
-            if r != Representable {
-                 return r
-            }
-        }
-        Representable
+        iter.fold(Representable,
+                  |r, ty| cmp::max(r, is_type_structurally_recursive(cx, sp, seen, ty)))
     }
 
-    // Does the type `ty` directly (without indirection through a pointer)
-    // contain any types on stack `seen`?
-    fn type_structurally_recursive(cx: &ctxt, sp: Span, seen: &mut Vec<DefId>,
-                                   ty: t) -> Representability {
-        debug!("type_structurally_recursive: {}",
-               ::util::ppaux::ty_to_string(cx, ty));
-
-        // Compare current type to previously seen types
-        match get(ty).sty {
-            ty_struct(did, _) |
-            ty_enum(did, _) => {
-                for (i, &seen_did) in seen.iter().enumerate() {
-                    if did == seen_did {
-                        return if i == 0 { SelfRecursive }
-                               else { ContainsRecursive }
-                    }
-                }
-            }
-            _ => (),
-        }
-
-        // Check inner types
+    fn are_inner_types_recursive(cx: &ctxt, sp: Span,
+                                 seen: &mut Vec<t>, ty: t) -> Representability {
         match get(ty).sty {
-            // Tuples
             ty_tup(ref ts) => {
                 find_nonrepresentable(cx, sp, seen, ts.iter().map(|t| *t))
             }
             // Fixed-length vectors.
             // FIXME(#11924) Behavior undecided for zero-length vectors.
             ty_vec(ty, Some(_)) => {
-                type_structurally_recursive(cx, sp, seen, ty)
+                is_type_structurally_recursive(cx, sp, seen, ty)
             }
-
-            // Push struct and enum def-ids onto `seen` before recursing.
             ty_struct(did, ref substs) => {
-                seen.push(did);
                 let fields = struct_fields(cx, did, substs);
-                let r = find_nonrepresentable(cx, sp, seen,
-                                              fields.iter().map(|f| f.mt.ty));
-                seen.pop();
-                r
+                find_nonrepresentable(cx, sp, seen, fields.iter().map(|f| f.mt.ty))
             }
-
             ty_enum(did, ref substs) => {
-                seen.push(did);
                 let vs = enum_variants(cx, did);
+                let iter = vs.iter()
+                    .flat_map(|variant| { variant.args.iter() })
+                    .map(|aty| { aty.subst_spanned(cx, substs, Some(sp)) });
 
-                let mut r = Representable;
-                for variant in vs.iter() {
-                    let iter = variant.args.iter().map(|aty| {
-                        aty.subst_spanned(cx, substs, Some(sp))
-                    });
-                    r = find_nonrepresentable(cx, sp, seen, iter);
+                find_nonrepresentable(cx, sp, seen, iter)
+            }
+            ty_unboxed_closure(did, _) => {
+                let upvars = unboxed_closure_upvars(cx, did);
+                find_nonrepresentable(cx, sp, seen, upvars.iter().map(|f| f.ty))
+            }
+            _ => Representable,
+        }
+    }
 
-                    if r != Representable { break }
+    fn same_struct_or_enum_def_id(ty: t, did: DefId) -> bool {
+        match get(ty).sty {
+            ty_struct(ty_did, _) | ty_enum(ty_did, _) => {
+                 ty_did == did
+            }
+            _ => false
+        }
+    }
+
+    fn same_type(a: t, b: t) -> bool {
+        match (&get(a).sty, &get(b).sty) {
+            (&ty_struct(did_a, ref substs_a), &ty_struct(did_b, ref substs_b)) |
+            (&ty_enum(did_a, ref substs_a), &ty_enum(did_b, ref substs_b)) => {
+                if did_a != did_b {
+                    return false;
                 }
 
-                seen.pop();
-                r
-            }
+                let types_a = substs_a.types.get_slice(subst::TypeSpace);
+                let types_b = substs_b.types.get_slice(subst::TypeSpace);
 
-            ty_unboxed_closure(did, _) => {
-                let upvars = unboxed_closure_upvars(cx, did);
-                find_nonrepresentable(cx,
-                                      sp,
-                                      seen,
-                                      upvars.iter().map(|f| f.ty))
+                let mut pairs = types_a.iter().zip(types_b.iter());
+
+                pairs.all(|(&a, &b)| same_type(a, b))
+            }
+            _ => {
+                type_id(a) == type_id(b)
             }
+        }
+    }
 
-            _ => Representable,
+    // Does the type `ty` directly (without indirection through a pointer)
+    // contain any types on stack `seen`?
+    fn is_type_structurally_recursive(cx: &ctxt, sp: Span, seen: &mut Vec<t>,
+                                      ty: t) -> Representability {
+        debug!("is_type_structurally_recursive: {}",
+               ::util::ppaux::ty_to_string(cx, ty));
+
+        match get(ty).sty {
+            ty_struct(did, _) | ty_enum(did, _) => {
+                {
+                    // Iterate through stack of previously seen types.
+                    let mut iter = seen.iter();
+
+                    // The first item in `seen` is the type we are actually curious about.
+                    // We want to return SelfRecursive if this type contains itself.
+                    // It is important that we DON'T take generic parameters into account
+                    // for this check, so that Bar<T> in this example counts as SelfRecursive:
+                    //
+                    // struct Foo;
+                    // struct Bar<T> { x: Bar<Foo> }
+
+                    match iter.next() {
+                        Some(&seen_type) => {
+                            if same_struct_or_enum_def_id(seen_type, did) {
+                                debug!("SelfRecursive: {} contains {}",
+                                       ::util::ppaux::ty_to_string(cx, seen_type),
+                                       ::util::ppaux::ty_to_string(cx, ty));
+                                return SelfRecursive;
+                            }
+                        }
+                        None => {}
+                    }
+
+                    // We also need to know whether the first item contains other types that
+                    // are structurally recursive. If we don't catch this case, we will recurse
+                    // infinitely for some inputs.
+                    //
+                    // It is important that we DO take generic parameters into account here,
+                    // so that code like this is considered SelfRecursive, not ContainsRecursive:
+                    //
+                    // struct Foo { Option<Option<Foo>> }
+
+                    for &seen_type in iter {
+                        if same_type(ty, seen_type) {
+                            debug!("ContainsRecursive: {} contains {}",
+                                   ::util::ppaux::ty_to_string(cx, seen_type),
+                                   ::util::ppaux::ty_to_string(cx, ty));
+                            return ContainsRecursive;
+                        }
+                    }
+                }
+
+                // For structs and enums, track all previously seen types by pushing them
+                // onto the 'seen' stack.
+                seen.push(ty);
+                let out = are_inner_types_recursive(cx, sp, seen, ty);
+                seen.pop();
+                out
+            }
+            _ => {
+                // No need to push in other cases.
+                are_inner_types_recursive(cx, sp, seen, ty)
+            }
         }
     }
 
@@ -2894,8 +2946,11 @@ pub fn is_type_representable(cx: &ctxt, sp: Span, ty: t) -> Representability {
     // To avoid a stack overflow when checking an enum variant or struct that
     // contains a different, structurally recursive type, maintain a stack
     // of seen types and check recursion for each of them (issues #3008, #3779).
-    let mut seen: Vec<DefId> = Vec::new();
-    type_structurally_recursive(cx, sp, &mut seen, ty)
+    let mut seen: Vec<t> = Vec::new();
+    let r = is_type_structurally_recursive(cx, sp, &mut seen, ty);
+    debug!("is_type_representable: {} is {}",
+           ::util::ppaux::ty_to_string(cx, ty), r);
+    r
 }
 
 pub fn type_is_trait(ty: t) -> bool {
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() {
 }