Auto merge of #40857 - estebank:recursive, r=arielb1

Point at fields that make the type recursive

On recursive types of infinite size, point at all the fields that make
the type recursive.

```rust
struct Foo {
    bar: Bar,
}

struct Bar {
    foo: Foo,
}
```

outputs

```
error[E0072]: recursive type `Foo` has infinite size
 --> file.rs:1:1
1 | struct Foo {
  | ^^^^^^^^^^ recursive type has infinite size
2 |     bar: Bar,
  |     -------- recursive here
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Foo` representable

error[E0072]: recursive type `Bar` has infinite size
 --> file.rs:5:1
  |
5 | struct Bar {
  | ^^^^^^^^^^ recursive type has infinite size
6 |     foo: Foo,
  |     -------- recursive here
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Bar` representable
```

11 files changed, 119 insertions, 26 deletions

diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index 24dfae3c540..06d09bd350a 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -145,11 +145,11 @@ pub enum CopyImplementationError<'tcx> {
 ///
 /// The ordering of the cases is significant. They are sorted so that cmp::max
 /// will keep the "more erroneous" of two values.
-#[derive(Copy, Clone, PartialOrd, Ord, Eq, PartialEq, Debug)]
+#[derive(Clone, PartialOrd, Ord, Eq, PartialEq, Debug)]
 pub enum Representability {
     Representable,
     ContainsRecursive,
-    SelfRecursive,
+    SelfRecursive(Vec<Span>),
 }
 
 impl<'tcx> ParameterEnvironment<'tcx> {
@@ -1006,18 +1006,22 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
 
     /// Check whether a type is representable. This means it cannot contain unboxed
     /// structural recursion. This check is needed for structs and enums.
-    pub fn is_representable(&'tcx self, tcx: TyCtxt<'a, 'tcx, 'tcx>, sp: Span)
+    pub fn is_representable(&'tcx self,
+                            tcx: TyCtxt<'a, 'tcx, 'tcx>,
+                            sp: Span)
                             -> Representability {
 
         // Iterate until something non-representable is found
-        fn find_nonrepresentable<'a, 'tcx, It>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
-                                               sp: Span,
-                                               seen: &mut Vec<Ty<'tcx>>,
-                                               iter: It)
-                                               -> Representability
-        where It: Iterator<Item=Ty<'tcx>> {
-            iter.fold(Representability::Representable,
-                      |r, ty| cmp::max(r, is_type_structurally_recursive(tcx, sp, seen, ty)))
+        fn fold_repr<It: Iterator<Item=Representability>>(iter: It) -> Representability {
+            iter.fold(Representability::Representable, |r1, r2| {
+                match (r1, r2) {
+                    (Representability::SelfRecursive(v1),
+                     Representability::SelfRecursive(v2)) => {
+                        Representability::SelfRecursive(v1.iter().map(|s| *s).chain(v2).collect())
+                    }
+                    (r1, r2) => cmp::max(r1, r2)
+                }
+            })
         }
 
         fn are_inner_types_recursive<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, sp: Span,
@@ -1025,7 +1029,10 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
                                                -> Representability {
             match ty.sty {
                 TyTuple(ref ts, _) => {
-                    find_nonrepresentable(tcx, sp, seen, ts.iter().cloned())
+                    // Find non representable
+                    fold_repr(ts.iter().map(|ty| {
+                        is_type_structurally_recursive(tcx, sp, seen, ty)
+                    }))
                 }
                 // Fixed-length vectors.
                 // FIXME(#11924) Behavior undecided for zero-length vectors.
@@ -1033,10 +1040,17 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
                     is_type_structurally_recursive(tcx, sp, seen, ty)
                 }
                 TyAdt(def, substs) => {
-                    find_nonrepresentable(tcx,
-                                          sp,
-                                          seen,
-                                          def.all_fields().map(|f| f.ty(tcx, substs)))
+                    // Find non representable fields with their spans
+                    fold_repr(def.all_fields().map(|field| {
+                        let ty = field.ty(tcx, substs);
+                        let span = tcx.hir.span_if_local(field.did).unwrap_or(sp);
+                        match is_type_structurally_recursive(tcx, span, seen, ty) {
+                            Representability::SelfRecursive(_) => {
+                                Representability::SelfRecursive(vec![span])
+                            }
+                            x => x,
+                        }
+                    }))
                 }
                 TyClosure(..) => {
                     // this check is run on type definitions, so we don't expect
@@ -1075,7 +1089,7 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
                                                     sp: Span,
                                                     seen: &mut Vec<Ty<'tcx>>,
                                                     ty: Ty<'tcx>) -> Representability {
-            debug!("is_type_structurally_recursive: {:?}", ty);
+            debug!("is_type_structurally_recursive: {:?} {:?}", ty, sp);
 
             match ty.sty {
                 TyAdt(def, _) => {
@@ -1096,7 +1110,7 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
                                 debug!("SelfRecursive: {:?} contains {:?}",
                                        seen_type,
                                        ty);
-                                return Representability::SelfRecursive;
+                                return Representability::SelfRecursive(vec![sp]);
                             }
                         }
 
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index e22c198fdb4..2e29aeeb022 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -1374,8 +1374,12 @@ fn check_representable<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     // contain themselves. For case 2, there must be an inner type that will be
     // caught by case 1.
     match rty.is_representable(tcx, sp) {
-        Representability::SelfRecursive => {
-            tcx.recursive_type_with_infinite_size_error(item_def_id).emit();
+        Representability::SelfRecursive(spans) => {
+            let mut err = tcx.recursive_type_with_infinite_size_error(item_def_id);
+            for span in spans {
+                err.span_label(span, &"recursive without indirection");
+            }
+            err.emit();
             return false
         }
         Representability::Representable | Representability::ContainsRecursive => (),
diff --git a/src/test/compile-fail/issue-3008-1.rs b/src/test/compile-fail/issue-3008-1.rs
index d3c15763eb0..7ca6d9301a6 100644
--- a/src/test/compile-fail/issue-3008-1.rs
+++ b/src/test/compile-fail/issue-3008-1.rs
@@ -8,9 +8,16 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-enum foo { foo_(bar) }
-enum bar { bar_none, bar_some(bar) }
-//~^ ERROR recursive type `bar` has infinite size
+enum Foo {
+    Foo_(Bar)
+}
+
+enum Bar {
+    //~^ ERROR recursive type `Bar` has infinite size
+    //~| NOTE recursive type has infinite size
+    BarNone,
+    BarSome(Bar)  //~ NOTE recursive without indirection
+}
 
 fn main() {
 }
diff --git a/src/test/compile-fail/issue-3008-2.rs b/src/test/compile-fail/issue-3008-2.rs
index 3bc8413cbca..061d1facda0 100644
--- a/src/test/compile-fail/issue-3008-2.rs
+++ b/src/test/compile-fail/issue-3008-2.rs
@@ -12,6 +12,7 @@ enum foo { foo_(bar) }
 struct bar { x: bar }
 //~^ ERROR E0072
 //~| NOTE recursive type has infinite size
+//~| NOTE recursive without indirection
 
 fn main() {
 }
diff --git a/src/test/compile-fail/issue-32326.rs b/src/test/compile-fail/issue-32326.rs
index afffe2a2c8d..70a7cd8b970 100644
--- a/src/test/compile-fail/issue-32326.rs
+++ b/src/test/compile-fail/issue-32326.rs
@@ -15,6 +15,8 @@
 enum Expr { //~ ERROR E0072
             //~| NOTE recursive type has infinite size
     Plus(Expr, Expr),
+    //~^ NOTE recursive without indirection
+    //~| NOTE recursive without indirection
     Literal(i64),
 }
 
diff --git a/src/test/compile-fail/issue-3779.rs b/src/test/compile-fail/issue-3779.rs
index 71e9325ab75..10f73dc0862 100644
--- a/src/test/compile-fail/issue-3779.rs
+++ b/src/test/compile-fail/issue-3779.rs
@@ -8,9 +8,11 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-struct S { //~ ERROR E0072
-           //~| NOTE recursive type has infinite size
+struct S {
+    //~^ ERROR E0072
+    //~| NOTE recursive type has infinite size
     element: Option<S>
+    //~^ NOTE recursive without indirection
 }
 
 fn main() {
diff --git a/src/test/compile-fail/type-recursive.rs b/src/test/compile-fail/type-recursive.rs
index 7b56c6c15eb..5dd76ce32c7 100644
--- a/src/test/compile-fail/type-recursive.rs
+++ b/src/test/compile-fail/type-recursive.rs
@@ -11,7 +11,7 @@
 struct t1 { //~ ERROR E0072
             //~| NOTE recursive type has infinite size
     foo: isize,
-    foolish: t1
+    foolish: t1  //~ NOTE recursive without indirection
 }
 
 fn main() { }
diff --git a/src/test/ui/span/E0072.stderr b/src/test/ui/span/E0072.stderr
index 5204390ef9d..1f6dd6b1d16 100644
--- a/src/test/ui/span/E0072.stderr
+++ b/src/test/ui/span/E0072.stderr
@@ -3,6 +3,9 @@ error[E0072]: recursive type `ListNode` has infinite size
    |
 11 | struct ListNode {
    | ^^^^^^^^^^^^^^^ recursive type has infinite size
+12 |     head: u8,
+13 |     tail: Option<ListNode>,
+   |     ---------------------- recursive without indirection
    |
    = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `ListNode` representable
 
diff --git a/src/test/ui/span/multiline-span-E0072.stderr b/src/test/ui/span/multiline-span-E0072.stderr
index 9c6816e7363..a06cbd04deb 100644
--- a/src/test/ui/span/multiline-span-E0072.stderr
+++ b/src/test/ui/span/multiline-span-E0072.stderr
@@ -6,6 +6,7 @@ error[E0072]: recursive type `ListNode` has infinite size
 14 | | {
 15 | |     head: u8,
 16 | |     tail: Option<ListNode>,
+   | |     ---------------------- recursive without indirection
 17 | | }
    | |_^ recursive type has infinite size
    |
diff --git a/src/test/ui/span/recursive-type-field.rs b/src/test/ui/span/recursive-type-field.rs
new file mode 100644
index 00000000000..6fef4d30f7a
--- /dev/null
+++ b/src/test/ui/span/recursive-type-field.rs
@@ -0,0 +1,28 @@
+// Copyright 2017 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::rc::Rc;
+
+struct Foo<'a> {
+    bar: Bar<'a>,
+    b: Rc<Bar<'a>>,
+}
+
+struct Bar<'a> {
+    y: (Foo<'a>, Foo<'a>),
+    z: Option<Bar<'a>>,
+    a: &'a Foo<'a>,
+    c: &'a [Bar<'a>],
+    d: [Bar<'a>; 1],
+    e: Foo<'a>,
+    x: Bar<'a>,
+}
+
+fn main() {}
diff --git a/src/test/ui/span/recursive-type-field.stderr b/src/test/ui/span/recursive-type-field.stderr
new file mode 100644
index 00000000000..b4d0b5a6a25
--- /dev/null
+++ b/src/test/ui/span/recursive-type-field.stderr
@@ -0,0 +1,31 @@
+error[E0072]: recursive type `Foo` has infinite size
+  --> $DIR/recursive-type-field.rs:13:1
+   |
+13 | struct Foo<'a> {
+   | ^^^^^^^^^^^^^^ recursive type has infinite size
+14 |     bar: Bar<'a>,
+   |     ------------ recursive without indirection
+   |
+   = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Foo` representable
+
+error[E0072]: recursive type `Bar` has infinite size
+  --> $DIR/recursive-type-field.rs:18:1
+   |
+18 | struct Bar<'a> {
+   | ^^^^^^^^^^^^^^ recursive type has infinite size
+19 |     y: (Foo<'a>, Foo<'a>),
+   |     --------------------- recursive without indirection
+20 |     z: Option<Bar<'a>>,
+   |     ------------------ recursive without indirection
+...
+23 |     d: [Bar<'a>; 1],
+   |     --------------- recursive without indirection
+24 |     e: Foo<'a>,
+   |     ---------- recursive without indirection
+25 |     x: Bar<'a>,
+   |     ---------- recursive without indirection
+   |
+   = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Bar` representable
+
+error: aborting due to 2 previous errors
+