Rollup merge of #22777 - pnkfelix:issue-22443, r=nikomatsakis

 Check for unbounded recursion during dropck.

Such recursion can be introduced by the erroneous use of non-regular types (aka types employing polymorphic recursion), which Rust does not support.

Fix #22443

6 files changed, 299 insertions, 24 deletions

diff --git a/src/librustc_typeck/check/dropck.rs b/src/librustc_typeck/check/dropck.rs
index 083523f7ba9..cffd74ccd72 100644
--- a/src/librustc_typeck/check/dropck.rs
+++ b/src/librustc_typeck/check/dropck.rs
@@ -14,8 +14,9 @@ use middle::infer;
 use middle::region;
 use middle::subst;
 use middle::ty::{self, Ty};
-use util::ppaux::{Repr};
+use util::ppaux::{Repr, UserString};
 
+use syntax::ast;
 use syntax::codemap::Span;
 
 pub fn check_safety_of_destructor_if_necessary<'a, 'tcx>(rcx: &mut Rcx<'a, 'tcx>,
@@ -28,29 +29,98 @@ pub fn check_safety_of_destructor_if_necessary<'a, 'tcx>(rcx: &mut Rcx<'a, 'tcx>
     // types that have been traversed so far by `traverse_type_if_unseen`
     let mut breadcrumbs: Vec<Ty<'tcx>> = Vec::new();
 
-    iterate_over_potentially_unsafe_regions_in_type(
+    let result = iterate_over_potentially_unsafe_regions_in_type(
         rcx,
         &mut breadcrumbs,
+        TypeContext::Root,
         typ,
         span,
         scope,
+        0,
         0);
+    match result {
+        Ok(()) => {}
+        Err(Error::Overflow(ref ctxt, ref detected_on_typ)) => {
+            let tcx = rcx.tcx();
+            span_err!(tcx.sess, span, E0320,
+                      "overflow while adding drop-check rules for {}",
+                      typ.user_string(rcx.tcx()));
+            match *ctxt {
+                TypeContext::Root => {
+                    // no need for an additional note if the overflow
+                    // was somehow on the root.
+                }
+                TypeContext::EnumVariant { def_id, variant, arg_index } => {
+                    // FIXME (pnkfelix): eventually lookup arg_name
+                    // for the given index on struct variants.
+                    span_note!(
+                        rcx.tcx().sess,
+                        span,
+                        "overflowed on enum {} variant {} argument {} type: {}",
+                        ty::item_path_str(tcx, def_id),
+                        variant,
+                        arg_index,
+                        detected_on_typ.user_string(rcx.tcx()));
+                }
+                TypeContext::Struct { def_id, field } => {
+                    span_note!(
+                        rcx.tcx().sess,
+                        span,
+                        "overflowed on struct {} field {} type: {}",
+                        ty::item_path_str(tcx, def_id),
+                        field,
+                        detected_on_typ.user_string(rcx.tcx()));
+                }
+            }
+        }
+    }
+}
+
+enum Error<'tcx> {
+    Overflow(TypeContext, ty::Ty<'tcx>),
+}
+
+enum TypeContext {
+    Root,
+    EnumVariant {
+        def_id: ast::DefId,
+        variant: ast::Name,
+        arg_index: usize,
+    },
+    Struct {
+        def_id: ast::DefId,
+        field: ast::Name,
+    }
 }
 
+// The `depth` counts the number of calls to this function;
+// the `xref_depth` counts the subset of such calls that go
+// across a `Box<T>` or `PhantomData<T>`.
 fn iterate_over_potentially_unsafe_regions_in_type<'a, 'tcx>(
     rcx: &mut Rcx<'a, 'tcx>,
     breadcrumbs: &mut Vec<Ty<'tcx>>,
+    context: TypeContext,
     ty_root: ty::Ty<'tcx>,
     span: Span,
     scope: region::CodeExtent,
-    depth: uint)
+    depth: uint,
+    xref_depth: uint) -> Result<(), Error<'tcx>>
 {
+    // Issue #22443: Watch out for overflow. While we are careful to
+    // handle regular types properly, non-regular ones cause problems.
+    let recursion_limit = rcx.tcx().sess.recursion_limit.get();
+    if xref_depth >= recursion_limit {
+        return Err(Error::Overflow(context, ty_root))
+    }
+
     let origin = || infer::SubregionOrigin::SafeDestructor(span);
     let mut walker = ty_root.walk();
     let opt_phantom_data_def_id = rcx.tcx().lang_items.phantom_data();
 
     let destructor_for_type = rcx.tcx().destructor_for_type.borrow();
 
+    let xref_depth_orig = xref_depth;
+
     while let Some(typ) = walker.next() {
         // Avoid recursing forever.
         if breadcrumbs.contains(&typ) {
@@ -61,20 +131,33 @@ fn iterate_over_potentially_unsafe_regions_in_type<'a, 'tcx>(
         // If we encounter `PhantomData<T>`, then we should replace it
         // with `T`, the type it represents as owned by the
         // surrounding context, before doing further analysis.
-        let typ = if let ty::ty_struct(struct_did, substs) = typ.sty {
-            if opt_phantom_data_def_id == Some(struct_did) {
-                let item_type = ty::lookup_item_type(rcx.tcx(), struct_did);
-                let tp_def = item_type.generics.types
-                    .opt_get(subst::TypeSpace, 0).unwrap();
-                let new_typ = substs.type_for_def(tp_def);
-                debug!("replacing phantom {} with {}",
+        let (typ, xref_depth) = match typ.sty {
+            ty::ty_struct(struct_did, substs) => {
+                if opt_phantom_data_def_id == Some(struct_did) {
+                    let item_type = ty::lookup_item_type(rcx.tcx(), struct_did);
+                    let tp_def = item_type.generics.types
+                        .opt_get(subst::TypeSpace, 0).unwrap();
+                    let new_typ = substs.type_for_def(tp_def);
+                    debug!("replacing phantom {} with {}",
+                           typ.repr(rcx.tcx()), new_typ.repr(rcx.tcx()));
+                    (new_typ, xref_depth_orig + 1)
+                } else {
+                    (typ, xref_depth_orig)
+                }
+            }
+
+            // Note: When ty_uniq is removed from compiler, the
+            // definition of `Box<T>` must carry a PhantomData that
+            // puts us into the previous case.
+            ty::ty_uniq(new_typ) => {
+                debug!("replacing ty_uniq {} with {}",
                        typ.repr(rcx.tcx()), new_typ.repr(rcx.tcx()));
-                new_typ
-            } else {
-                typ
+                (new_typ, xref_depth_orig + 1)
+            }
+
+            _ => {
+                (typ, xref_depth_orig)
             }
-        } else {
-            typ
         };
 
         let opt_type_did = match typ.sty {
@@ -87,9 +170,9 @@ fn iterate_over_potentially_unsafe_regions_in_type<'a, 'tcx>(
             opt_type_did.and_then(|did| destructor_for_type.get(&did));
 
         debug!("iterate_over_potentially_unsafe_regions_in_type \
-                {}typ: {} scope: {:?} opt_dtor: {:?}",
+                {}typ: {} scope: {:?} opt_dtor: {:?} xref: {}",
                (0..depth).map(|_| ' ').collect::<String>(),
-               typ.repr(rcx.tcx()), scope, opt_dtor);
+               typ.repr(rcx.tcx()), scope, opt_dtor, xref_depth);
 
         // If `typ` has a destructor, then we must ensure that all
         // borrowed data reachable via `typ` must outlive the parent
@@ -228,6 +311,8 @@ fn iterate_over_potentially_unsafe_regions_in_type<'a, 'tcx>(
 
             match typ.sty {
                 ty::ty_struct(struct_did, substs) => {
+                    debug!("typ: {} is struct; traverse structure and not type-expression",
+                           typ.repr(rcx.tcx()));
                     // Don't recurse; we extract type's substructure,
                     // so do not process subparts of type expression.
                     walker.skip_current_subtree();
@@ -240,17 +325,24 @@ fn iterate_over_potentially_unsafe_regions_in_type<'a, 'tcx>(
                                                   struct_did,
                                                   field.id,
                                                   substs);
-                        iterate_over_potentially_unsafe_regions_in_type(
+                        try!(iterate_over_potentially_unsafe_regions_in_type(
                             rcx,
                             breadcrumbs,
+                            TypeContext::Struct {
+                                def_id: struct_did,
+                                field: field.name,
+                            },
                             field_type,
                             span,
                             scope,
-                            depth+1)
+                            depth+1,
+                            xref_depth))
                     }
                 }
 
                 ty::ty_enum(enum_did, substs) => {
+                    debug!("typ: {} is enum; traverse structure and not type-expression",
+                           typ.repr(rcx.tcx()));
                     // Don't recurse; we extract type's substructure,
                     // so do not process subparts of type expression.
                     walker.skip_current_subtree();
@@ -260,14 +352,20 @@ fn iterate_over_potentially_unsafe_regions_in_type<'a, 'tcx>(
                                                  enum_did,
                                                  substs);
                     for variant_info in all_variant_info.iter() {
-                        for argument_type in variant_info.args.iter() {
-                            iterate_over_potentially_unsafe_regions_in_type(
+                        for (i, arg_type) in variant_info.args.iter().enumerate() {
+                            try!(iterate_over_potentially_unsafe_regions_in_type(
                                 rcx,
                                 breadcrumbs,
-                                *argument_type,
+                                TypeContext::EnumVariant {
+                                    def_id: enum_did,
+                                    variant: variant_info.name,
+                                    arg_index: i,
+                                },
+                                *arg_type,
                                 span,
                                 scope,
-                                depth+1)
+                                depth+1,
+                                xref_depth));
                         }
                     }
                 }
@@ -290,4 +388,6 @@ fn iterate_over_potentially_unsafe_regions_in_type<'a, 'tcx>(
             // is done.
         }
     }
+
+    return Ok(());
 }
diff --git a/src/librustc_typeck/diagnostics.rs b/src/librustc_typeck/diagnostics.rs
index 7b43a9fef06..3bd15fbc7db 100644
--- a/src/librustc_typeck/diagnostics.rs
+++ b/src/librustc_typeck/diagnostics.rs
@@ -174,7 +174,8 @@ register_diagnostics! {
     E0249, // expected constant expr for array length
     E0250, // expected constant expr for array length
     E0318, // can't create default impls for traits outside their crates
-    E0319  // trait impls for defaulted traits allowed just for structs/enums
+    E0319, // trait impls for defaulted traits allowed just for structs/enums
+    E0320  // recursive overflow during dropck
 }
 
 __build_diagnostic_array! { DIAGNOSTICS }
diff --git a/src/test/compile-fail/dropck_no_diverge_on_nonregular_1.rs b/src/test/compile-fail/dropck_no_diverge_on_nonregular_1.rs
new file mode 100644
index 00000000000..f0968853819
--- /dev/null
+++ b/src/test/compile-fail/dropck_no_diverge_on_nonregular_1.rs
@@ -0,0 +1,37 @@
+// Copyright 2015 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.
+
+// Issue 22443: Reject code using non-regular types that would
+// otherwise cause dropck to loop infinitely.
+
+use std::marker::PhantomData;
+
+struct Digit<T> {
+    elem: T
+}
+
+struct Node<T:'static> { m: PhantomData<&'static T> }
+
+
+enum FingerTree<T:'static> {
+    Single(T),
+    // Bug report said Digit after Box would stack overflow (versus
+    // Digit before Box; see dropck_no_diverge_on_nonregular_2).
+    Deep(
+        Box<FingerTree<Node<T>>>,
+        Digit<T>,
+        )
+}
+
+fn main() {
+    let ft = //~ ERROR overflow while adding drop-check rules for FingerTree
+        FingerTree::Single(1);
+    //~^ ERROR overflow while adding drop-check rules for FingerTree
+}
diff --git a/src/test/compile-fail/dropck_no_diverge_on_nonregular_2.rs b/src/test/compile-fail/dropck_no_diverge_on_nonregular_2.rs
new file mode 100644
index 00000000000..886bd6bea20
--- /dev/null
+++ b/src/test/compile-fail/dropck_no_diverge_on_nonregular_2.rs
@@ -0,0 +1,36 @@
+// Copyright 2015 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.
+
+// Issue 22443: Reject code using non-regular types that would
+// otherwise cause dropck to loop infinitely.
+
+use std::marker::PhantomData;
+
+struct Digit<T> {
+    elem: T
+}
+
+struct Node<T:'static> { m: PhantomData<&'static T> }
+
+enum FingerTree<T:'static> {
+    Single(T),
+    // Bug report said Digit before Box would infinite loop (versus
+    // Digit after Box; see dropck_no_diverge_on_nonregular_1).
+    Deep(
+        Digit<T>,
+        Box<FingerTree<Node<T>>>,
+        )
+}
+
+fn main() {
+    let ft = //~ ERROR overflow while adding drop-check rules for FingerTree
+        FingerTree::Single(1);
+    //~^ ERROR overflow while adding drop-check rules for FingerTree
+}
diff --git a/src/test/compile-fail/dropck_no_diverge_on_nonregular_3.rs b/src/test/compile-fail/dropck_no_diverge_on_nonregular_3.rs
new file mode 100644
index 00000000000..f7eb6e10ca7
--- /dev/null
+++ b/src/test/compile-fail/dropck_no_diverge_on_nonregular_3.rs
@@ -0,0 +1,46 @@
+// Copyright 2015 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.
+
+// Issue 22443: Reject code using non-regular types that would
+// otherwise cause dropck to loop infinitely.
+//
+// This version is just checking that we still sanely handle a trivial
+// wrapper around the non-regular type. (It also demonstrates how the
+// error messages will report different types depending on which type
+// dropck is analyzing.)
+
+use std::marker::PhantomData;
+
+struct Digit<T> {
+    elem: T
+}
+
+struct Node<T:'static> { m: PhantomData<&'static T> }
+
+enum FingerTree<T:'static> {
+    Single(T),
+    // According to the bug report, Digit before Box would infinite loop.
+    Deep(
+        Digit<T>,
+        Box<FingerTree<Node<T>>>,
+        )
+}
+
+enum Wrapper<T:'static> {
+    Simple,
+    Other(FingerTree<T>),
+}
+
+fn main() {
+    let w = //~ ERROR overflow while adding drop-check rules for core::option
+        Some(Wrapper::Simple::<u32>);
+    //~^ ERROR overflow while adding drop-check rules for core::option::Option
+    //~| ERROR overflow while adding drop-check rules for Wrapper
+}
diff --git a/src/test/run-pass/issue-22777.rs b/src/test/run-pass/issue-22777.rs
new file mode 100644
index 00000000000..cab33beda40
--- /dev/null
+++ b/src/test/run-pass/issue-22777.rs
@@ -0,0 +1,55 @@
+// Copyright 2015 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.
+
+// This test is reduced from libsyntax.  It is just checking that we
+// can successfully deal with a "deep" structure, which the drop-check
+// was hitting a recursion limit on at one point.
+
+#![allow(non_camel_case_types)]
+
+pub fn noop_fold_impl_item() -> SmallVector<ImplItem> {
+    loop  { }
+}
+
+pub struct SmallVector<T>(P<T>);
+pub struct ImplItem(P<S01_Method>);
+
+struct P<T>(Box<T>);
+
+struct S01_Method(P<S02_Generics>);
+struct S02_Generics(P<S03_TyParam>);
+struct S03_TyParam(P<S04_TyParamBound>);
+struct S04_TyParamBound(S05_PolyTraitRef);
+struct S05_PolyTraitRef(S06_TraitRef);
+struct S06_TraitRef(S07_Path);
+struct S07_Path(Vec<S08_PathSegment>);
+struct S08_PathSegment(S09_PathParameters);
+struct S09_PathParameters(P<S10_ParenthesizedParameterData>);
+struct S10_ParenthesizedParameterData(Option<P<S11_Ty>>);
+struct S11_Ty(P<S12_Expr>);
+struct S12_Expr(P<S13_Block>);
+struct S13_Block(Vec<P<S14_Stmt>>);
+struct S14_Stmt(P<S15_Decl>);
+struct S15_Decl(P<S16_Local>);
+struct S16_Local(P<S17_Pat>);
+struct S17_Pat(P<S18_Mac>);
+struct S18_Mac(Vec<P<S19_TokenTree>>);
+struct S19_TokenTree(P<S20_Token>);
+struct S20_Token(P<S21_Nonterminal>);
+struct S21_Nonterminal(P<S22_Item>);
+struct S22_Item(P<S23_EnumDef>);
+struct S23_EnumDef(Vec<P<S24_Variant>>);
+struct S24_Variant(P<S25_VariantKind>);
+struct S25_VariantKind(P<S26_StructDef>);
+struct S26_StructDef(Vec<P<S27_StructField>>);
+struct S27_StructField(P<S28_StructFieldKind>);
+struct S28_StructFieldKind;
+
+pub fn main() {}