From 3e106c77ff76c39be49444165eac805d32666e41 Mon Sep 17 00:00:00 2001
From: Florian Diebold <flodiebold@gmail.com>
Date: Sat, 22 Feb 2020 13:14:39 +0100
Subject: Rework find_super_trait_path to protect against cycles

---
 crates/ra_hir_ty/src/lib.rs            | 17 ++++++++-------
 crates/ra_hir_ty/src/lower.rs          |  3 ++-
 crates/ra_hir_ty/src/tests/coercion.rs | 38 ++++++++++++++++++++++++++++++++++
 crates/ra_hir_ty/src/traits/builtin.rs |  6 ++----
 crates/ra_hir_ty/src/utils.rs          | 33 +++++++++++++++++++----------
 5 files changed, 74 insertions(+), 23 deletions(-)

diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs
index 182f847f1..0009c426c 100644
--- a/crates/ra_hir_ty/src/lib.rs
+++ b/crates/ra_hir_ty/src/lib.rs
@@ -814,13 +814,16 @@ pub trait TypeWalk {
     where
         Self: Sized,
     {
-        self.fold_binders(&mut |ty, binders| match ty {
-            Ty::Bound(idx) if idx as usize >= binders => {
-                assert!(idx as i32 >= -n);
-                Ty::Bound((idx as i32 + n) as u32)
-            }
-            ty => ty,
-        }, 0)
+        self.fold_binders(
+            &mut |ty, binders| match ty {
+                Ty::Bound(idx) if idx as usize >= binders => {
+                    assert!(idx as i32 >= -n);
+                    Ty::Bound((idx as i32 + n) as u32)
+                }
+                ty => ty,
+            },
+            0,
+        )
     }
 }
 
diff --git a/crates/ra_hir_ty/src/lower.rs b/crates/ra_hir_ty/src/lower.rs
index 0e6efa971..092977e93 100644
--- a/crates/ra_hir_ty/src/lower.rs
+++ b/crates/ra_hir_ty/src/lower.rs
@@ -241,7 +241,8 @@ impl Ty {
             TypeNs::TraitId(trait_) => {
                 // if this is a bare dyn Trait, we'll directly put the required ^0 for the self type in there
                 let self_ty = if remaining_segments.len() == 0 { Some(Ty::Bound(0)) } else { None };
-                let trait_ref = TraitRef::from_resolved_path(ctx, trait_, resolved_segment, self_ty);
+                let trait_ref =
+                    TraitRef::from_resolved_path(ctx, trait_, resolved_segment, self_ty);
                 return if remaining_segments.len() == 1 {
                     let segment = remaining_segments.first().unwrap();
                     let associated_ty = associated_type_by_name_including_super_traits(
diff --git a/crates/ra_hir_ty/src/tests/coercion.rs b/crates/ra_hir_ty/src/tests/coercion.rs
index 5594ed394..60ad6e9be 100644
--- a/crates/ra_hir_ty/src/tests/coercion.rs
+++ b/crates/ra_hir_ty/src/tests/coercion.rs
@@ -622,6 +622,44 @@ fn test() {
     );
 }
 
+#[test]
+fn coerce_unsize_super_trait_cycle() {
+    assert_snapshot!(
+        infer_with_mismatches(r#"
+#[lang = "unsize"]
+pub trait Unsize<T> {}
+#[lang = "coerce_unsized"]
+pub trait CoerceUnsized<T> {}
+
+impl<T: Unsize<U>, U> CoerceUnsized<&U> for &T {}
+
+trait A {}
+trait B: C + A {}
+trait C: B {}
+trait D: C
+
+struct S;
+impl A for S {}
+impl B for S {}
+impl C for S {}
+impl D for S {}
+
+fn test() {
+    let obj: &dyn D = &S;
+    let obj: &dyn A = obj;
+}
+"#, true),
+        @r###"
+    [292; 348) '{     ...obj; }': ()
+    [302; 305) 'obj': &dyn D
+    [316; 318) '&S': &S
+    [317; 318) 'S': S
+    [328; 331) 'obj': &dyn A
+    [342; 345) 'obj': &dyn D
+    "###
+    );
+}
+
 #[ignore]
 #[test]
 fn coerce_unsize_generic() {
diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs
index 19e533cee..df0645717 100644
--- a/crates/ra_hir_ty/src/traits/builtin.rs
+++ b/crates/ra_hir_ty/src/traits/builtin.rs
@@ -316,12 +316,10 @@ fn super_trait_object_unsize_impl_datum(
     let self_bounds = vec![GenericPredicate::Implemented(self_trait_ref.clone())];
 
     // we need to go from our trait to the super trait, substituting type parameters
-    let mut path = crate::utils::find_super_trait_path(db, data.super_trait, data.trait_);
-    path.pop(); // the last one is our current trait, we don't need that
-    path.reverse(); // we want to go from trait to super trait
+    let path = crate::utils::find_super_trait_path(db, data.trait_, data.super_trait);
 
     let mut current_trait_ref = self_trait_ref;
-    for t in path {
+    for t in path.into_iter().skip(1) {
         let bounds = db.generic_predicates(current_trait_ref.trait_.into());
         let super_trait_ref = bounds
             .iter()
diff --git a/crates/ra_hir_ty/src/utils.rs b/crates/ra_hir_ty/src/utils.rs
index 0d1583c39..463fd65b4 100644
--- a/crates/ra_hir_ty/src/utils.rs
+++ b/crates/ra_hir_ty/src/utils.rs
@@ -62,25 +62,36 @@ pub(super) fn all_super_traits(db: &impl DefDatabase, trait_: TraitId) -> Vec<Tr
     result
 }
 
-/// Finds a path from a trait to one of its descendant traits. Returns an empty
+/// Finds a path from a trait to one of its super traits. Returns an empty
 /// vector if there is no path.
 pub(super) fn find_super_trait_path(
     db: &impl DefDatabase,
-    super_trait: TraitId,
     trait_: TraitId,
+    super_trait: TraitId,
 ) -> Vec<TraitId> {
-    if trait_ == super_trait {
-        return vec![trait_];
-    }
+    let mut result = Vec::with_capacity(2);
+    result.push(trait_);
+    return if go(db, super_trait, &mut result) { result } else { Vec::new() };
+
+    fn go(db: &impl DefDatabase, super_trait: TraitId, path: &mut Vec<TraitId>) -> bool {
+        let trait_ = *path.last().unwrap();
+        if trait_ == super_trait {
+            return true;
+        }
 
-    for tt in direct_super_traits(db, trait_) {
-        let mut path = find_super_trait_path(db, super_trait, tt);
-        if !path.is_empty() {
-            path.push(trait_);
-            return path;
+        for tt in direct_super_traits(db, trait_) {
+            if path.contains(&tt) {
+                continue;
+            }
+            path.push(tt);
+            if go(db, super_trait, path) {
+                return true;
+            } else {
+                path.pop();
+            }
         }
+        false
     }
-    Vec::new()
 }
 
 pub(super) fn associated_type_by_name_including_super_traits(
-- 
cgit v1.2.3