Fix crash for super trait cycles

3 files changed, 39 insertions, 19 deletions

diff --git a/crates/ra_hir/Cargo.toml b/crates/ra_hir/Cargo.toml
index e89b97daf..d9bed4dda 100644
--- a/crates/ra_hir/Cargo.toml
+++ b/crates/ra_hir/Cargo.toml
@@ -12,7 +12,6 @@ rustc-hash = "1.0"
 parking_lot = "0.9.0"
 ena = "0.13"
 once_cell = "1.0.1"
-itertools = "0.8.0"
 
 ra_syntax = { path = "../ra_syntax" }
 ra_arena = { path = "../ra_arena" }
diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index 52ee1834f..1bb2f9f28 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -1,11 +1,8 @@
 pub(crate) mod src;
 pub(crate) mod docs;
 
-use std::iter;
 use std::sync::Arc;
 
-use itertools::Itertools;
-
 use ra_db::{CrateId, Edition, FileId, SourceRootId};
 use ra_syntax::ast::{self, NameOwner, TypeAscriptionOwner};
 
@@ -849,20 +846,23 @@ impl Trait {
 
     /// Returns an iterator over the whole super trait hierarchy (including the
     /// trait itself).
-    pub fn all_super_traits<'a>(
-        self,
-        db: &'a impl HirDatabase,
-    ) -> impl Iterator<Item = Trait> + 'a {
-        self.all_super_traits_inner(db).unique()
-    }
-
-    fn all_super_traits_inner<'a>(
-        self,
-        db: &'a impl HirDatabase,
-    ) -> impl Iterator<Item = Trait> + 'a {
-        iter::once(self).chain(self.direct_super_traits(db).into_iter().flat_map(move |t| {
-            iter::once(t).chain(Box::new(t.all_super_traits(db)) as Box<dyn Iterator<Item = Trait>>)
-        }))
+    pub fn all_super_traits(self, db: &impl HirDatabase) -> Vec<Trait> {
+        // we need to take care a bit here to avoid infinite loops in case of cycles
+        // (i.e. if we have `trait A: B; trait B: A;`)
+        let mut result = vec![self];
+        let mut i = 0;
+        while i < result.len() {
+            let t = result[i];
+            // yeah this is quadratic, but trait hierarchies should be flat
+            // enough that this doesn't matter
+            for tt in t.direct_super_traits(db) {
+                if !result.contains(&tt) {
+                    result.push(tt);
+                }
+            }
+            i += 1;
+        }
+        result
     }
 
     pub fn associated_type_by_name(self, db: &impl DefDatabase, name: &Name) -> Option<TypeAlias> {
@@ -882,7 +882,7 @@ impl Trait {
         db: &impl HirDatabase,
         name: &Name,
     ) -> Option<TypeAlias> {
-        self.all_super_traits(db).find_map(|t| t.associated_type_by_name(db, name))
+        self.all_super_traits(db).into_iter().find_map(|t| t.associated_type_by_name(db, name))
     }
 
     pub(crate) fn trait_data(self, db: &impl DefDatabase) -> Arc<TraitData> {
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 3f86a5c80..c4bddde85 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -3695,6 +3695,27 @@ fn test<T: Trait1, U: Trait2>(x: T, y: U) {
 }
 
 #[test]
+fn super_trait_cycle() {
+    // This just needs to not crash
+    assert_snapshot!(
+        infer(r#"
+trait A: B {}
+trait B: A {}
+
+fn test<T: A>(x: T) {
+    x.foo();
+}
+"#),
+        @r###"
+    [44; 45) 'x': T
+    [50; 66) '{     ...o(); }': ()
+    [56; 57) 'x': T
+    [56; 63) 'x.foo()': {unknown}
+    "###
+    );
+}
+
+#[test]
 fn super_trait_assoc_type_bounds() {
     assert_snapshot!(
         infer(r#"