From 15c757aca9c3f2381c72195488f641f9563492a2 Mon Sep 17 00:00:00 2001
From: Eh2406 <YeomanYaacov@gmail.com>
Date: Wed, 14 Mar 2018 20:02:06 -0400
Subject: [PATCH] Clean the `backtrack_stack` so we don't backtrack to a place
 with cashed bad activations

---
 src/cargo/core/resolver/mod.rs | 54 ++++++++++++++++++----------------
 1 file changed, 28 insertions(+), 26 deletions(-)

diff --git a/src/cargo/core/resolver/mod.rs b/src/cargo/core/resolver/mod.rs
index 377a20236..dbb86a14a 100644
--- a/src/cargo/core/resolver/mod.rs
+++ b/src/cargo/core/resolver/mod.rs
@@ -952,10 +952,7 @@ fn activate_deps_loop(
                 .get(&dep)
                 .and_then(|past_bad| {
                     past_bad.iter().find(|conflicting| {
-                        conflicting
-                    .iter()
-                    // note: a lot of redundant work in is_active for similar debs
-                    .all(|(con, _)| cx.is_active(con))
+                        cx.is_conflicting(None, conflicting)
                     })
                 })
                 .is_some();
@@ -1085,21 +1082,14 @@ fn activate_deps_loop(
                     // but we may want to scrap it if it is not going to end well
                     let mut has_past_conflicting_dep = just_here_for_the_error_messages;
                     if !has_past_conflicting_dep {
-                        if let Some(conflicting) = frame
-                            .remaining_siblings
-                            .clone()
-                            .filter_map(|(_, (deb, _, _))| {
-                                past_conflicting_activations.get(&deb).and_then(|past_bad| {
-                                    // for each dependency check all of its cashed conflicts
-                                    past_bad.iter().find(|conflicting| {
-                                        conflicting
-                                        .iter()
-                                        // note: a lot of redundant work in is_active for similar debs
-                                        .all(|(con, _)| cx.is_active(con))
-                                    })
+                        if let Some(conflicting) = frame.remaining_siblings.clone().filter_map(|(_, (deb, _, _))| {
+                            past_conflicting_activations.get(&deb).and_then(|past_bad| {
+                                // for each dependency check all of its cashed conflicts
+                                past_bad.iter().find(|conflicting| {
+                                    cx.is_conflicting(None, conflicting)
                                 })
                             })
-                            .next()
+                        }).next()
                         {
                             // if any of them match than it will just backtrack to us
                             // so let's save the effort.
@@ -1123,6 +1113,9 @@ fn activate_deps_loop(
                                 conflicting_activations
                             );
                             past.push(conflicting_activations.clone());
+                            // also clean the `backtrack_stack` so we don't
+                            // backtrack to a place where we will try this again.
+                            backtrack_stack.retain(|bframe| !bframe.context_backup.is_conflicting(Some(parent.package_id()), &conflicting_activations));
                         }
                     }
                     // if not has_another we we activate for the better error messages
@@ -1191,15 +1184,10 @@ fn find_candidate<'a>(
     conflicting_activations: &HashMap<PackageId, ConflictReason>,
 ) -> Option<(Candidate, bool, BacktrackFrame)> {
     while let Some(mut frame) = backtrack_stack.pop() {
-        let next = frame.remaining_candidates.next(
-            frame.context_backup.prev_active(&frame.dep),
-            &frame.context_backup.links,
-        );
-        if frame.context_backup.is_active(parent.package_id())
-            && conflicting_activations
-           .iter()
-           // note: a lot of redundant work in is_active for similar debs
-           .all(|(con, _)| frame.context_backup.is_active(con))
+        let next= frame.remaining_candidates.next(frame.context_backup.prev_active(&frame.dep), &frame.context_backup.links,);
+        if frame.context_backup.is_conflicting(Some(parent.package_id())
+           , conflicting_activations
+           )
         {
             continue;
         }
@@ -1643,6 +1631,20 @@ impl Context {
             .unwrap_or(false)
     }
 
+    /// checks whether all of `parent` and the keys of `conflicting activations`
+    /// are still active
+    fn is_conflicting(
+        &self,
+        parent: Option<&PackageId>,
+        conflicting_activations: &HashMap<PackageId, ConflictReason>,
+    ) -> bool {
+        parent.map(|p| self.is_active(p)).unwrap_or(true) &&
+            conflicting_activations
+                .keys()
+                // note: a lot of redundant work in is_active for similar debs
+                .all(|con| self.is_active(con))
+    }
+
     /// Return all dependencies and the features we want from them.
     fn resolve_features<'b>(
         &mut self,
-- 
2.30.2