Comprehence cycle detection in `collect`. In some cases, the cycles we

report are not *necessary* cycles, but we'll work on refactoring them
over time. This overlaps with the cycle detection that astconv already
does: I left that code in because it gives a more targeted error
message, though perhaps less helpful in that it doesn't give the full
details of the cycle.

8 files changed, 282 insertions, 68 deletions

diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 275007bf797..20a0c35d8e0 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -2546,6 +2546,13 @@ impl<'tcx> ctxt<'tcx> {
     {
         self.closure_tys.borrow()[def_id].subst(self, substs)
     }
+
+    pub fn type_parameter_def(&self,
+                              node_id: ast::NodeId)
+                              -> TypeParameterDef<'tcx>
+    {
+        self.ty_param_defs.borrow()[node_id].clone()
+    }
 }
 
 // Interns a type/name combination, stores the resulting box in cx.interner,
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index d0e194e15d2..48928516a60 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -53,7 +53,7 @@ use middle::const_eval;
 use middle::def;
 use middle::resolve_lifetime as rl;
 use middle::privacy::{AllPublic, LastMod};
-use middle::subst::{FnSpace, ParamSpace, TypeSpace, SelfSpace, Subst, Substs};
+use middle::subst::{FnSpace, TypeSpace, SelfSpace, Subst, Substs};
 use middle::traits;
 use middle::ty::{self, RegionEscape, ToPolyTraitRef, Ty};
 use rscope::{self, UnelidableRscope, RegionScope, ElidableRscope,
@@ -73,11 +73,14 @@ use syntax::print::pprust;
 pub trait AstConv<'tcx> {
     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
 
-    fn get_item_type_scheme(&self, id: ast::DefId) -> ty::TypeScheme<'tcx>;
+    fn get_item_type_scheme(&self, span: Span, id: ast::DefId)
+                            -> Result<ty::TypeScheme<'tcx>, ErrorReported>;
 
-    fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>>;
+    fn get_trait_def(&self, span: Span, id: ast::DefId)
+                     -> Result<Rc<ty::TraitDef<'tcx>>, ErrorReported>;
 
-    fn get_type_parameter_bounds(&self, space: ParamSpace, index: u32) -> Vec<ty::PolyTraitRef<'tcx>>;
+    fn get_type_parameter_bounds(&self, span: Span, def_id: ast::NodeId)
+                                 -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>;
 
     /// Return an (optional) substitution to convert bound type parameters that
     /// are in scope into free ones. This function should only return Some
@@ -685,7 +688,14 @@ fn ast_path_to_trait_ref<'a,'tcx>(
     -> Rc<ty::TraitRef<'tcx>>
 {
     debug!("ast_path_to_trait_ref {:?}", trait_segment);
-    let trait_def = this.get_trait_def(trait_def_id);
+    let trait_def = match this.get_trait_def(path.span, trait_def_id) {
+        Ok(trait_def) => trait_def,
+        Err(ErrorReported) => {
+            // No convenient way to recover from a cycle here. Just bail. Sorry!
+            this.tcx().sess.abort_if_errors();
+            this.tcx().sess.bug("ErrorReported returned, but no errors reports?")
+        }
+    };
 
     let (regions, types, assoc_bindings) = match trait_segment.parameters {
         ast::AngleBracketedParameters(ref data) => {
@@ -862,14 +872,17 @@ fn ast_path_to_ty<'tcx>(
     item_segment: &ast::PathSegment)
     -> Ty<'tcx>
 {
-    let ty::TypeScheme {
-        generics,
-        ty: decl_ty
-    } = this.get_item_type_scheme(did);
-
-    let substs = ast_path_substs_for_ty(this, rscope,
-                                        span, param_mode,
-                                        &generics, item_segment);
+    let tcx = this.tcx();
+    let substs = match this.get_item_type_scheme(path.span, did) {
+        Ok(ty::TypeScheme { generics,  ty: decl_ty }) => {
+            ast_path_substs_for_ty(this, rscope,
+                                   span, param_mode,
+                                   &generics, item_segment)
+        }
+        Err(ErrorReported) => {
+            return TypeAndSubsts { substs: Substs::empty(), ty: tcx.types.err };
+        }
+    };
 
     // FIXME(#12938): This is a hack until we have full support for DST.
     if Some(did) == this.tcx().lang_items.owned_box() {
@@ -1003,22 +1016,17 @@ fn associated_path_def_to_ty<'tcx>(this: &AstConv<'tcx>,
         return (tcx.types.err, ty_path_def);
     };
 
-    let mut suitable_bounds: Vec<_>;
-    let ty_param_name: ast::Name;
-    { // contain scope of refcell:
-        let ty_param_defs = tcx.ty_param_defs.borrow();
-        let ty_param_def = &ty_param_defs[ty_param_node_id];
-        ty_param_name = ty_param_def.name;
-
-
-        // FIXME(#20300) -- search where clauses, not bounds
-        suitable_bounds =
-            traits::transitive_bounds(tcx,
-                                      &this.get_type_parameter_bounds(ty_param_def.space,
-                                                                      ty_param_def.index))
-            .filter(|b| trait_defines_associated_type_named(this, b.def_id(), assoc_name))
-            .collect();
-    }
+    let ty_param_name = tcx.ty_param_defs.borrow()[ty_param_node_id].name;
+
+    // FIXME(#20300) -- search where clauses, not bounds
+    let bounds =
+        this.get_type_parameter_bounds(ast_ty.span, ty_param_ndoe_id)
+            .unwrap_or(Vec::new());
+
+    let mut suitable_bounds: Vec<_> =
+        traits::transitive_bounds(tcx, &bounds)
+        .filter(|b| trait_defines_associated_type_named(this, b.def_id(), assoc_name))
+        .collect();
 
     if suitable_bounds.len() == 0 {
         span_err!(tcx.sess, span, E0220,
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 968d67aca9d..43edb4f09cc 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -106,7 +106,7 @@ use session::Session;
 use {CrateCtxt, lookup_full_def, require_same_types};
 use TypeAndSubsts;
 use lint;
-use util::common::{block_query, indenter, loop_query};
+use util::common::{block_query, ErrorReported, indenter, loop_query};
 use util::ppaux::{self, Repr};
 use util::nodemap::{DefIdMap, FnvHashMap, NodeMap};
 use util::lev_distance::lev_distance;
@@ -1206,12 +1206,16 @@ fn check_cast<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>,
 impl<'a, 'tcx> AstConv<'tcx> for FnCtxt<'a, 'tcx> {
     fn tcx(&self) -> &ty::ctxt<'tcx> { self.ccx.tcx }
 
-    fn get_item_type_scheme(&self, id: ast::DefId) -> ty::TypeScheme<'tcx> {
-        ty::lookup_item_type(self.tcx(), id)
+    fn get_item_type_scheme(&self, _: Span, id: ast::DefId)
+                            -> Result<ty::TypeScheme<'tcx>, ErrorReported>
+    {
+        Ok(ty::lookup_item_type(self.tcx(), id))
     }
 
-    fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>> {
-        ty::lookup_trait_def(self.tcx(), id)
+    fn get_trait_def(&self, _: Span, id: ast::DefId)
+                     -> Result<Rc<ty::TraitDef<'tcx>>, ErrorReported>
+    {
+        Ok(ty::lookup_trait_def(self.tcx(), id))
     }
 
     fn get_free_substs(&self) -> Option<&Substs<'tcx>> {
@@ -1219,27 +1223,29 @@ impl<'a, 'tcx> AstConv<'tcx> for FnCtxt<'a, 'tcx> {
     }
 
     fn get_type_parameter_bounds(&self,
-                                 space: ParamSpace,
-                                 index: u32)
-                                 -> Vec<ty::PolyTraitRef<'tcx>>
+                                 _: Span,
+                                 node_id: ast::NodeId)
+                                 -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>
     {
-        self.inh.param_env.caller_bounds
-                          .iter()
-                          .filter_map(|predicate| {
-                              match *predicate {
-                                  ty::Predicate::Trait(ref data) => {
-                                      if data.0.self_ty().is_param(space, index) {
-                                          Some(data.to_poly_trait_ref())
-                                      } else {
-                                          None
+        let def = self.tcx().type_parameter_def(node_id);
+        let r = self.inh.param_env.caller_bounds
+                                  .iter()
+                                  .filter_map(|predicate| {
+                                      match *predicate {
+                                          ty::Predicate::Trait(ref data) => {
+                                              if data.0.self_ty().is_param(def.space, def.index) {
+                                                  Some(data.to_poly_trait_ref())
+                                              } else {
+                                                  None
+                                              }
+                                          }
+                                          _ => {
+                                              None
+                                          }
                                       }
-                                  }
-                                  _ => {
-                                      None
-                                  }
-                              }
-                          })
-                          .collect()
+                                  })
+                                  .collect();
+        Ok(r)
     }
 
     fn ty_infer(&self, _span: Span) -> Ty<'tcx> {
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 6d65d05bf6f..cef7f83840b 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -98,12 +98,13 @@ use middle::ty::{self, RegionEscape, Ty, TypeScheme};
 use middle::ty_fold::{self, TypeFolder, TypeFoldable};
 use middle::infer;
 use rscope::*;
-use util::common::memoized;
+use util::common::{ErrorReported, memoized};
 use util::nodemap::{FnvHashMap, FnvHashSet};
 use util::ppaux;
 use util::ppaux::{Repr,UserString};
 use write_ty_to_tcx;
 
+use std::cell::RefCell;
 use std::collections::HashSet;
 use std::rc::Rc;
 
@@ -121,7 +122,7 @@ use syntax::visit;
 // Main entry point
 
 pub fn collect_item_types(tcx: &ty::ctxt) {
-    let ccx = &CrateCtxt { tcx: tcx };
+    let ccx = &CrateCtxt { tcx: tcx, stack: RefCell::new(Vec::new()) };
 
     match ccx.tcx.lang_items.ty_desc() {
         Some(id) => { collect_intrinsic_type(ccx, id); }
@@ -143,6 +144,10 @@ pub fn collect_item_types(tcx: &ty::ctxt) {
 
 struct CrateCtxt<'a,'tcx:'a> {
     tcx: &'a ty::ctxt<'tcx>,
+
+    // This stack is used to identify cycles in the user's source.
+    // Note that these cycles can cross multiple items.
+    stack: RefCell<Vec<AstConvRequest>>,
 }
 
 struct ItemCtxt<'a,'tcx:'a> {
@@ -150,6 +155,13 @@ struct ItemCtxt<'a,'tcx:'a> {
     generics: &'a ty::Generics<'tcx>,
 }
 
+#[derive(Copy, PartialEq, Eq)]
+enum AstConvRequest {
+    GetItemTypeScheme(ast::DefId),
+    GetTraitDef(ast::DefId),
+    GetTypeParameterBounds(ast::NodeId),
+}
+
 ///////////////////////////////////////////////////////////////////////////
 // Zeroth phase: collect types of intrinsics
 
@@ -217,6 +229,94 @@ impl<'a,'tcx> CrateCtxt<'a,'tcx> {
             }
         }
     }
+
+    fn cycle_check<F,R>(&self,
+                        span: Span,
+                        request: AstConvRequest,
+                        code: F)
+                        -> Result<R,ErrorReported>
+        where F: FnOnce() -> R
+    {
+        {
+            let mut stack = self.stack.borrow_mut();
+            match stack.iter().enumerate().rev().find(|&(_, r)| *r == request) {
+                None => { }
+                Some((i, _)) => {
+                    let cycle = &stack[i..];
+                    self.report_cycle(span, cycle);
+                    return Err(ErrorReported);
+                }
+            }
+            stack.push(request);
+        }
+
+        let result = code();
+
+        self.stack.borrow_mut().pop();
+        Ok(result)
+    }
+
+    fn report_cycle(&self,
+                    span: Span,
+                    cycle: &[AstConvRequest])
+    {
+        assert!(!cycle.is_empty());
+        let tcx = self.tcx;
+
+        tcx.sess.span_err(
+            span,
+            &format!("unsupported cyclic reference between types/traits detected"));
+
+        match cycle[0] {
+            AstConvRequest::GetItemTypeScheme(def_id) |
+            AstConvRequest::GetTraitDef(def_id) => {
+                tcx.sess.note(
+                    &format!("the cycle begins when processing `{}`...",
+                             ty::item_path_str(tcx, def_id)));
+            }
+            AstConvRequest::GetTypeParameterBounds(id) => {
+                let def = tcx.type_parameter_def(id);
+                tcx.sess.note(
+                    &format!("the cycle begins when computing the bounds \
+                              for type parameter `{}`...",
+                             def.name.user_string(tcx)));
+            }
+        }
+
+        for request in cycle[1..].iter() {
+            match *request {
+                AstConvRequest::GetItemTypeScheme(def_id) |
+                AstConvRequest::GetTraitDef(def_id) => {
+                    tcx.sess.note(
+                        &format!("...which then requires processing `{}`...",
+                                 ty::item_path_str(tcx, def_id)));
+                }
+                AstConvRequest::GetTypeParameterBounds(id) => {
+                    let def = tcx.type_parameter_def(id);
+                    tcx.sess.note(
+                        &format!("...which then requires computing the bounds \
+                                  for type parameter `{}`...",
+                                 def.name.user_string(tcx)));
+                }
+            }
+        }
+
+        match cycle[0] {
+            AstConvRequest::GetItemTypeScheme(def_id) |
+            AstConvRequest::GetTraitDef(def_id) => {
+                tcx.sess.note(
+                    &format!("...which then again requires processing `{}`, completing the cycle.",
+                             ty::item_path_str(tcx, def_id)));
+            }
+            AstConvRequest::GetTypeParameterBounds(id) => {
+                let def = tcx.type_parameter_def(id);
+                tcx.sess.note(
+                    &format!("...which then again requires computing the bounds \
+                              for type parameter `{}`, completing the cycle.",
+                             def.name.user_string(tcx)));
+            }
+        }
+    }
 }
 
 pub trait ToTy<'tcx> {
@@ -232,25 +332,37 @@ impl<'a,'tcx> ToTy<'tcx> for ItemCtxt<'a,'tcx> {
 impl<'a, 'tcx> AstConv<'tcx> for ItemCtxt<'a, 'tcx> {
     fn tcx(&self) -> &ty::ctxt<'tcx> { self.ccx.tcx }
 
-    fn get_item_type_scheme(&self, id: ast::DefId) -> ty::TypeScheme<'tcx> {
-        type_scheme_of_def_id(self.ccx, id)
+    fn get_item_type_scheme(&self, span: Span, id: ast::DefId)
+                            -> Result<ty::TypeScheme<'tcx>, ErrorReported>
+    {
+        self.ccx.cycle_check(span, AstConvRequest::GetItemTypeScheme(id), || {
+            type_scheme_of_def_id(self.ccx, id)
+        })
     }
 
-    fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>> {
-        get_trait_def(self.ccx, id)
+    fn get_trait_def(&self, span: Span, id: ast::DefId)
+                     -> Result<Rc<ty::TraitDef<'tcx>>, ErrorReported>
+    {
+        self.ccx.cycle_check(span, AstConvRequest::GetTraitDef(id), || {
+            get_trait_def(self.ccx, id)
+        })
     }
 
     fn get_type_parameter_bounds(&self,
-                                 param: subst::ParamSpace,
-                                 index: u32)
-                                 -> Vec<ty::PolyTraitRef<'tcx>>
+                                 span: Span,
+                                 node_id: ast::NodeId)
+                                 -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>
     {
-        // TODO out of range indices can occur when you have something
-        // like fn foo<T:U::X,U>() { }
-        match self.generics.types.opt_get(param, index as usize) {
-            Some(def) => def.bounds.trait_bounds.clone(),
-            None => Vec::new(),
-        }
+        self.ccx.cycle_check(span, AstConvRequest::GetTypeParameterBounds(node_id), || {
+            let def = self.tcx().type_parameter_def(node_id);
+
+            // TODO out of range indices can occur when you have something
+            // like fn foo<T:U::X,U>() { }
+            match self.generics.types.opt_get(def.space, def.index as usize) {
+                Some(def) => def.bounds.trait_bounds.clone(),
+                None => Vec::new(),
+            }
+        })
     }
 
     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
diff --git a/src/test/compile-fail/cycle-generic-bound.rs b/src/test/compile-fail/cycle-generic-bound.rs
new file mode 100644
index 00000000000..51fee683a81
--- /dev/null
+++ b/src/test/compile-fail/cycle-generic-bound.rs
@@ -0,0 +1,19 @@
+// 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.
+
+// Regression test for #15477. This test should pass, vs reporting an
+// error as it does now, but at least this test shows it doesn't
+// segfault.
+
+trait Chromosome<X: Chromosome> {
+    //~^ ERROR cyclic reference detected
+}
+
+fn main() { }
diff --git a/src/test/compile-fail/cycle-trait-supertrait-direct.rs b/src/test/compile-fail/cycle-trait-supertrait-direct.rs
new file mode 100644
index 00000000000..836b581d2bf
--- /dev/null
+++ b/src/test/compile-fail/cycle-trait-supertrait-direct.rs
@@ -0,0 +1,17 @@
+// 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.
+
+// Test a supertrait cycle where a trait extends itself.
+
+trait Chromosome: Chromosome {
+    //~^ ERROR cyclic reference detected
+}
+
+fn main() { }
diff --git a/src/test/compile-fail/cycle-trait-supertrait-indirect.rs b/src/test/compile-fail/cycle-trait-supertrait-indirect.rs
new file mode 100644
index 00000000000..68553462036
--- /dev/null
+++ b/src/test/compile-fail/cycle-trait-supertrait-indirect.rs
@@ -0,0 +1,22 @@
+// 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.
+
+// Test a supertrait cycle where the first trait we find (`A`) is not
+// a direct participant in the cycle.
+
+trait A: B {
+}
+
+trait B: C { }
+    //~^ ERROR cyclic reference detected
+
+trait C: B { }
+
+fn main() { }
diff --git a/src/test/compile-fail/cycle-trait-type-trait.rs b/src/test/compile-fail/cycle-trait-type-trait.rs
new file mode 100644
index 00000000000..912961120c2
--- /dev/null
+++ b/src/test/compile-fail/cycle-trait-type-trait.rs
@@ -0,0 +1,23 @@
+// 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.
+
+// Test a supertrait cycle where a trait extends itself.
+
+trait Chromosome: Get<Struct> {
+    //~^ ERROR cyclic reference detected
+}
+
+trait Get<A> {
+    fn get(&self) -> A;
+}
+
+struct Struct<C:Chromosome> { c: C }
+
+fn main() { }