Permit coinductive match only for purely OIBIT backtraces.

Better safe than sorry.

2 files changed, 39 insertions, 11 deletions

diff --git a/src/librustc/middle/traits/fulfill.rs b/src/librustc/middle/traits/fulfill.rs
index 97656ecf6ae..0e1c9c3843b 100644
--- a/src/librustc/middle/traits/fulfill.rs
+++ b/src/librustc/middle/traits/fulfill.rs
@@ -359,17 +359,8 @@ fn process_predicate1<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
     let obligation = &pending_obligation.obligation;
     match obligation.predicate {
         ty::Predicate::Trait(ref data) => {
-            // For defaulted traits, we use a co-inductive strategy to
-            // solve, so that recursion is ok.
-            if selcx.tcx().trait_has_default_impl(data.def_id()) {
-                debug!("process_predicate: trait has default impl");
-                for bt_obligation in backtrace {
-                    debug!("process_predicate: bt_obligation = {:?}", bt_obligation.obligation);
-                    if bt_obligation.obligation.predicate == obligation.predicate {
-                        debug!("process_predicate: found a match!");
-                        return Ok(Some(vec![]));
-                    }
-                }
+            if coinductive_match(selcx, obligation, data, &backtrace) {
+                return Ok(Some(vec![]));
             }
 
             let trait_obligation = obligation.with(data.clone());
@@ -483,6 +474,42 @@ fn process_predicate1<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
     }
 }
 
+/// For defaulted traits, we use a co-inductive strategy to solve, so
+/// that recursion is ok. This routine returns true if the top of the
+/// stack (`top_obligation` and `top_data`):
+/// - is a defaulted trait, and
+/// - it also appears in the backtrace at some position `X`; and,
+/// - all the predicates at positions `X..` between `X` an the top are
+///   also defaulted traits.
+fn coinductive_match<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
+                              top_obligation: &PredicateObligation<'tcx>,
+                              top_data: &ty::PolyTraitPredicate<'tcx>,
+                              backtrace: &Backtrace<PendingPredicateObligation<'tcx>>)
+                              -> bool
+{
+    if selcx.tcx().trait_has_default_impl(top_data.def_id()) {
+        for bt_obligation in backtrace.clone() {
+            // *Everything* in the backtrace must be a defaulted trait.
+            match bt_obligation.obligation.predicate {
+                ty::Predicate::Trait(ref data) => {
+                    if !selcx.tcx().trait_has_default_impl(data.def_id()) {
+                        break;
+                    }
+                }
+                _ => { break; }
+            }
+
+            // And we must find a recursive match.
+            if bt_obligation.obligation.predicate == top_obligation.predicate {
+                debug!("process_predicate: found a match in the backtrace");
+                return true;
+            }
+        }
+    }
+
+    false
+}
+
 fn register_region_obligation<'tcx>(t_a: Ty<'tcx>,
                                     r_b: ty::Region,
                                     cause: ObligationCause<'tcx>,
diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs
index 21fa150b012..d23b42790d7 100644
--- a/src/librustc_data_structures/obligation_forest/mod.rs
+++ b/src/librustc_data_structures/obligation_forest/mod.rs
@@ -379,6 +379,7 @@ impl<O> Node<O> {
     }
 }
 
+#[derive(Clone)]
 pub struct Backtrace<'b, O: 'b> {
     nodes: &'b [Node<O>],
     pointer: Option<NodeIndex>,