Rollup merge of #48296 - ishitatsuyuki:exp-unblow, r=nikomatsakis

Fix exponential projection complexity on nested types

This implements solution 1 from https://github.com/rust-lang/rust/issues/38528#issuecomment-366263076.

The code quality is currently extremely poor, but we can improve them during review.

Blocking issues:

- we probably don't want a quadratic deduplication for obligations.
- is there an alternative to deduplication?

Based on #48315.

Needs changelog. Noticable improvement on compile time is expected.

Fix #38528
Close #39684
Close #43757

6 files changed, 133 insertions, 151 deletions

diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index 520b997882e..49f43b18e61 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -73,7 +73,7 @@ pub enum IntercrateMode {
 /// either identifying an `impl` (e.g., `impl Eq for int`) that
 /// provides the required vtable, or else finding a bound that is in
 /// scope. The eventual result is usually a `Selection` (defined below).
-#[derive(Clone, PartialEq, Eq)]
+#[derive(Clone, PartialEq, Eq, Hash)]
 pub struct Obligation<'tcx, T> {
     pub cause: ObligationCause<'tcx>,
     pub param_env: ty::ParamEnv<'tcx>,
@@ -85,7 +85,7 @@ pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>;
 pub type TraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitPredicate<'tcx>>;
 
 /// Why did we incur this obligation? Used for error reporting.
-#[derive(Clone, Debug, PartialEq, Eq)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
 pub struct ObligationCause<'tcx> {
     pub span: Span,
 
@@ -113,7 +113,7 @@ impl<'tcx> ObligationCause<'tcx> {
     }
 }
 
-#[derive(Clone, Debug, PartialEq, Eq)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
 pub enum ObligationCauseCode<'tcx> {
     /// Not well classified or should be obvious from span.
     MiscObligation,
@@ -215,7 +215,7 @@ pub enum ObligationCauseCode<'tcx> {
     BlockTailExpression(ast::NodeId),
 }
 
-#[derive(Clone, Debug, PartialEq, Eq)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
 pub struct DerivedObligationCause<'tcx> {
     /// The trait reference of the parent obligation that led to the
     /// current obligation. Note that only trait obligations lead to
@@ -304,7 +304,7 @@ pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
 /// ### The type parameter `N`
 ///
 /// See explanation on `VtableImplData`.
-#[derive(Clone, RustcEncodable, RustcDecodable)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 pub enum Vtable<'tcx, N> {
     /// Vtable identifying a particular impl.
     VtableImpl(VtableImplData<'tcx, N>),
@@ -374,13 +374,13 @@ pub struct VtableClosureData<'tcx, N> {
     pub nested: Vec<N>
 }
 
-#[derive(Clone, RustcEncodable, RustcDecodable)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 pub struct VtableAutoImplData<N> {
     pub trait_def_id: DefId,
     pub nested: Vec<N>
 }
 
-#[derive(Clone, RustcEncodable, RustcDecodable)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 pub struct VtableBuiltinData<N> {
     pub nested: Vec<N>
 }
diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs
index 0d0476e7c21..1778a8d693a 100644
--- a/src/librustc/traits/project.rs
+++ b/src/librustc/traits/project.rs
@@ -16,6 +16,7 @@ use super::translate_substs;
 use super::Obligation;
 use super::ObligationCause;
 use super::PredicateObligation;
+use super::Selection;
 use super::SelectionContext;
 use super::SelectionError;
 use super::VtableClosureData;
@@ -101,7 +102,7 @@ pub struct MismatchedProjectionTypes<'tcx> {
     pub err: ty::error::TypeError<'tcx>
 }
 
-#[derive(PartialEq, Eq, PartialOrd, Ord, Debug)]
+#[derive(PartialEq, Eq, Debug)]
 enum ProjectionTyCandidate<'tcx> {
     // from a where-clause in the env or object type
     ParamEnv(ty::PolyProjectionPredicate<'tcx>),
@@ -110,12 +111,59 @@ enum ProjectionTyCandidate<'tcx> {
     TraitDef(ty::PolyProjectionPredicate<'tcx>),
 
     // from a "impl" (or a "pseudo-impl" returned by select)
-    Select,
+    Select(Selection<'tcx>),
 }
 
-struct ProjectionTyCandidateSet<'tcx> {
-    vec: Vec<ProjectionTyCandidate<'tcx>>,
-    ambiguous: bool
+enum ProjectionTyCandidateSet<'tcx> {
+    None,
+    Single(ProjectionTyCandidate<'tcx>),
+    Ambiguous,
+    Error(SelectionError<'tcx>),
+}
+
+impl<'tcx> ProjectionTyCandidateSet<'tcx> {
+    fn mark_ambiguous(&mut self) {
+        *self = ProjectionTyCandidateSet::Ambiguous;
+    }
+
+    fn mark_error(&mut self, err: SelectionError<'tcx>) {
+        *self = ProjectionTyCandidateSet::Error(err);
+    }
+
+    // Returns true if the push was successful, or false if the candidate
+    // was discarded -- this could be because of ambiguity, or because
+    // a higher-priority candidate is already there.
+    fn push_candidate(&mut self, candidate: ProjectionTyCandidate<'tcx>) -> bool {
+        use self::ProjectionTyCandidateSet::*;
+        use self::ProjectionTyCandidate::*;
+        match self {
+            None => {
+                *self = Single(candidate);
+                true
+            }
+            Single(current) => {
+                // No duplicates are expected.
+                assert_ne!(current, &candidate);
+                // Prefer where-clauses. As in select, if there are multiple
+                // candidates, we prefer where-clause candidates over impls.  This
+                // may seem a bit surprising, since impls are the source of
+                // "truth" in some sense, but in fact some of the impls that SEEM
+                // applicable are not, because of nested obligations. Where
+                // clauses are the safer choice. See the comment on
+                // `select::SelectionCandidate` and #21974 for more details.
+                match (current, candidate) {
+                    (ParamEnv(..), ParamEnv(..)) => { *self = Ambiguous; }
+                    (ParamEnv(..), _) => {}
+                    (_, ParamEnv(..)) => { unreachable!(); }
+                    (_, _) => { *self = Ambiguous; }
+                }
+                false
+            }
+            Ambiguous | Error(..) => {
+                false
+            }
+        }
+    }
 }
 
 /// Evaluates constraints of the form:
@@ -803,11 +851,11 @@ fn project_type<'cx, 'gcx, 'tcx>(
         return Ok(ProjectedTy::Progress(Progress::error(selcx.tcx())));
     }
 
-    let mut candidates = ProjectionTyCandidateSet {
-        vec: Vec::new(),
-        ambiguous: false,
-    };
+    let mut candidates = ProjectionTyCandidateSet::None;
 
+    // Make sure that the following procedures are kept in order. ParamEnv
+    // needs to be first because it has highest priority, and Select checks
+    // the return value of push_candidate which assumes it's ran at last.
     assemble_candidates_from_param_env(selcx,
                                        obligation,
                                        &obligation_trait_ref,
@@ -818,67 +866,27 @@ fn project_type<'cx, 'gcx, 'tcx>(
                                        &obligation_trait_ref,
                                        &mut candidates);
 
-    if let Err(e) = assemble_candidates_from_impls(selcx,
-                                                   obligation,
-                                                   &obligation_trait_ref,
-                                                   &mut candidates) {
-        return Err(ProjectionTyError::TraitSelectionError(e));
-    }
-
-    debug!("{} candidates, ambiguous={}",
-           candidates.vec.len(),
-           candidates.ambiguous);
-
-    // Inherent ambiguity that prevents us from even enumerating the
-    // candidates.
-    if candidates.ambiguous {
-        return Err(ProjectionTyError::TooManyCandidates);
-    }
-
-    // Drop duplicates.
-    //
-    // Note: `candidates.vec` seems to be on the critical path of the
-    // compiler. Replacing it with an HashSet was also tried, which would
-    // render the following dedup unnecessary. The original comment indicated
-    // that it was 9% slower, but that data is now obsolete and a new
-    // benchmark should be performed.
-    candidates.vec.sort_unstable();
-    candidates.vec.dedup();
-
-    // Prefer where-clauses. As in select, if there are multiple
-    // candidates, we prefer where-clause candidates over impls.  This
-    // may seem a bit surprising, since impls are the source of
-    // "truth" in some sense, but in fact some of the impls that SEEM
-    // applicable are not, because of nested obligations. Where
-    // clauses are the safer choice. See the comment on
-    // `select::SelectionCandidate` and #21974 for more details.
-    if candidates.vec.len() > 1 {
-        debug!("retaining param-env candidates only from {:?}", candidates.vec);
-        candidates.vec.retain(|c| match *c {
-            ProjectionTyCandidate::ParamEnv(..) => true,
-            ProjectionTyCandidate::TraitDef(..) |
-            ProjectionTyCandidate::Select => false,
-        });
-        debug!("resulting candidate set: {:?}", candidates.vec);
-        if candidates.vec.len() != 1 {
-            return Err(ProjectionTyError::TooManyCandidates);
-        }
-    }
-
-    assert!(candidates.vec.len() <= 1);
+    assemble_candidates_from_impls(selcx,
+                                   obligation,
+                                   &obligation_trait_ref,
+                                   &mut candidates);
+
+    match candidates {
+        ProjectionTyCandidateSet::Single(candidate) => Ok(ProjectedTy::Progress(
+            confirm_candidate(selcx,
+                              obligation,
+                              &obligation_trait_ref,
+                              candidate))),
+        ProjectionTyCandidateSet::None => Ok(ProjectedTy::NoProgress(
+            selcx.tcx().mk_projection(
+                obligation.predicate.item_def_id,
+                obligation.predicate.substs))),
+        // Error occurred while trying to processing impls.
+        ProjectionTyCandidateSet::Error(e) => Err(ProjectionTyError::TraitSelectionError(e)),
+        // Inherent ambiguity that prevents us from even enumerating the
+        // candidates.
+        ProjectionTyCandidateSet::Ambiguous => Err(ProjectionTyError::TooManyCandidates),
 
-    match candidates.vec.pop() {
-        Some(candidate) => {
-            Ok(ProjectedTy::Progress(
-                confirm_candidate(selcx,
-                                  obligation,
-                                  &obligation_trait_ref,
-                                  candidate)))
-        }
-        None => Ok(ProjectedTy::NoProgress(
-                    selcx.tcx().mk_projection(
-                        obligation.predicate.item_def_id,
-                        obligation.predicate.substs)))
     }
 }
 
@@ -928,7 +936,7 @@ fn assemble_candidates_from_trait_def<'cx, 'gcx, 'tcx>(
         ty::TyInfer(ty::TyVar(_)) => {
             // If the self-type is an inference variable, then it MAY wind up
             // being a projected type, so induce an ambiguity.
-            candidate_set.ambiguous = true;
+            candidate_set.mark_ambiguous();
             return;
         }
         _ => { return; }
@@ -962,7 +970,7 @@ fn assemble_candidates_from_predicates<'cx, 'gcx, 'tcx, I>(
         debug!("assemble_candidates_from_predicates: predicate={:?}",
                predicate);
         match predicate {
-            ty::Predicate::Projection(ref data) => {
+            ty::Predicate::Projection(data) => {
                 let same_def_id =
                     data.0.projection_ty.item_def_id == obligation.predicate.item_def_id;
 
@@ -985,10 +993,10 @@ fn assemble_candidates_from_predicates<'cx, 'gcx, 'tcx, I>(
                        data, is_match, same_def_id);
 
                 if is_match {
-                    candidate_set.vec.push(ctor(data.clone()));
+                    candidate_set.push_candidate(ctor(data));
                 }
             }
-            _ => { }
+            _ => {}
         }
     }
 }
@@ -998,37 +1006,36 @@ fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx>(
     obligation: &ProjectionTyObligation<'tcx>,
     obligation_trait_ref: &ty::TraitRef<'tcx>,
     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
-    -> Result<(), SelectionError<'tcx>>
 {
     // If we are resolving `<T as TraitRef<...>>::Item == Type`,
     // start out by selecting the predicate `T as TraitRef<...>`:
     let poly_trait_ref = obligation_trait_ref.to_poly_trait_ref();
     let trait_obligation = obligation.with(poly_trait_ref.to_poly_trait_predicate());
-    selcx.infcx().probe(|_| {
+    let _ = selcx.infcx().commit_if_ok(|_| {
         let vtable = match selcx.select(&trait_obligation) {
             Ok(Some(vtable)) => vtable,
             Ok(None) => {
-                candidate_set.ambiguous = true;
-                return Ok(());
+                candidate_set.mark_ambiguous();
+                return Err(());
             }
             Err(e) => {
                 debug!("assemble_candidates_from_impls: selection error {:?}",
                        e);
-                return Err(e);
+                candidate_set.mark_error(e);
+                return Err(());
             }
         };
 
-        match vtable {
+        let eligible = match &vtable {
             super::VtableClosure(_) |
             super::VtableGenerator(_) |
             super::VtableFnPointer(_) |
             super::VtableObject(_) => {
                 debug!("assemble_candidates_from_impls: vtable={:?}",
                        vtable);
-
-                candidate_set.vec.push(ProjectionTyCandidate::Select);
+                true
             }
-            super::VtableImpl(ref impl_data) => {
+            super::VtableImpl(impl_data) => {
                 // We have to be careful when projecting out of an
                 // impl because of specialization. If we are not in
                 // trans (i.e., projection mode is not "any"), and the
@@ -1072,27 +1079,25 @@ fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx>(
                     node_item.item.defaultness.has_value()
                 } else {
                     node_item.item.defaultness.is_default() ||
-                    selcx.tcx().impl_is_default(node_item.node.def_id())
+                        selcx.tcx().impl_is_default(node_item.node.def_id())
                 };
 
                 // Only reveal a specializable default if we're past type-checking
                 // and the obligations is monomorphic, otherwise passes such as
                 // transmute checking and polymorphic MIR optimizations could
                 // get a result which isn't correct for all monomorphizations.
-                let new_candidate = if !is_default {
-                    Some(ProjectionTyCandidate::Select)
+                if !is_default {
+                    true
                 } else if obligation.param_env.reveal == Reveal::All {
                     assert!(!poly_trait_ref.needs_infer());
                     if !poly_trait_ref.needs_subst() {
-                        Some(ProjectionTyCandidate::Select)
+                        true
                     } else {
-                        None
+                        false
                     }
                 } else {
-                    None
-                };
-
-                candidate_set.vec.extend(new_candidate);
+                    false
+                }
             }
             super::VtableParam(..) => {
                 // This case tell us nothing about the value of an
@@ -1120,6 +1125,7 @@ fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx>(
                 // in the compiler: a trait predicate (`T : SomeTrait`) and a
                 // projection. And the projection where clause is handled
                 // in `assemble_candidates_from_param_env`.
+                false
             }
             super::VtableAutoImpl(..) |
             super::VtableBuiltin(..) => {
@@ -1129,10 +1135,18 @@ fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx>(
                     "Cannot project an associated type from `{:?}`",
                     vtable);
             }
-        }
+        };
 
-        Ok(())
-    })
+        if eligible {
+            if candidate_set.push_candidate(ProjectionTyCandidate::Select(vtable)) {
+                Ok(())
+            } else {
+                Err(())
+            }
+        } else {
+            Err(())
+        }
+    });
 }
 
 fn confirm_candidate<'cx, 'gcx, 'tcx>(
@@ -1152,8 +1166,8 @@ fn confirm_candidate<'cx, 'gcx, 'tcx>(
             confirm_param_env_candidate(selcx, obligation, poly_projection)
         }
 
-        ProjectionTyCandidate::Select => {
-            confirm_select_candidate(selcx, obligation, obligation_trait_ref)
+        ProjectionTyCandidate::Select(vtable) => {
+            confirm_select_candidate(selcx, obligation, obligation_trait_ref, vtable)
         }
     }
 }
@@ -1161,21 +1175,10 @@ fn confirm_candidate<'cx, 'gcx, 'tcx>(
 fn confirm_select_candidate<'cx, 'gcx, 'tcx>(
     selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
     obligation: &ProjectionTyObligation<'tcx>,
-    obligation_trait_ref: &ty::TraitRef<'tcx>)
+    obligation_trait_ref: &ty::TraitRef<'tcx>,
+    vtable: Selection<'tcx>)
     -> Progress<'tcx>
 {
-    let poly_trait_ref = obligation_trait_ref.to_poly_trait_ref();
-    let trait_obligation = obligation.with(poly_trait_ref.to_poly_trait_predicate());
-    let vtable = match selcx.select(&trait_obligation) {
-        Ok(Some(vtable)) => vtable,
-        _ => {
-            span_bug!(
-                obligation.cause.span,
-                "Failed to select `{:?}`",
-                trait_obligation);
-        }
-    };
-
     match vtable {
         super::VtableImpl(data) =>
             confirm_impl_candidate(selcx, obligation, data),
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index cfeb456acef..fca7c3bcb8e 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -53,7 +53,7 @@ use std::rc::Rc;
 use syntax::abi::Abi;
 use hir;
 use lint;
-use util::nodemap::FxHashMap;
+use util::nodemap::{FxHashMap, FxHashSet};
 
 struct InferredObligationsSnapshotVecDelegate<'tcx> {
     phantom: PhantomData<&'tcx i32>,
@@ -3303,7 +3303,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         // that order.
         let predicates = tcx.predicates_of(def_id);
         assert_eq!(predicates.parent, None);
-        let predicates = predicates.predicates.iter().flat_map(|predicate| {
+        let mut predicates: Vec<_> = predicates.predicates.iter().flat_map(|predicate| {
             let predicate = normalize_with_depth(self, param_env, cause.clone(), recursion_depth,
                                                  &predicate.subst(tcx, substs));
             predicate.obligations.into_iter().chain(
@@ -3314,6 +3314,13 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                     predicate: predicate.value
                 }))
         }).collect();
+        // We are performing deduplication here to avoid exponential blowups
+        // (#38528) from happening, but the real cause of the duplication is
+        // unknown. What we know is that the deduplication avoids exponential
+        // amount of predicates being propogated when processing deeply nested
+        // types.
+        let mut seen = FxHashSet();
+        predicates.retain(|i| seen.insert(i.clone()));
         self.infcx().plug_leaks(skol_map, snapshot, predicates)
     }
 }
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index f52f2ea0f9f..3ab2cd274b9 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -39,7 +39,6 @@ use util::nodemap::{NodeSet, DefIdMap, FxHashMap, FxHashSet};
 use serialize::{self, Encodable, Encoder};
 use std::cell::RefCell;
 use std::cmp;
-use std::cmp::Ordering;
 use std::fmt;
 use std::hash::{Hash, Hasher};
 use std::iter::FromIterator;
@@ -498,20 +497,6 @@ impl<'tcx> Hash for TyS<'tcx> {
     }
 }
 
-impl<'tcx> Ord for TyS<'tcx> {
-    #[inline]
-    fn cmp(&self, other: &TyS<'tcx>) -> Ordering {
-        // (self as *const _).cmp(other as *const _)
-        (self as *const TyS<'tcx>).cmp(&(other as *const TyS<'tcx>))
-    }
-}
-impl<'tcx> PartialOrd for TyS<'tcx> {
-    #[inline]
-    fn partial_cmp(&self, other: &TyS<'tcx>) -> Option<Ordering> {
-        Some(self.cmp(other))
-    }
-}
-
 impl<'tcx> TyS<'tcx> {
     pub fn is_primitive_ty(&self) -> bool {
         match self.sty {
@@ -581,19 +566,6 @@ impl<T> PartialEq for Slice<T> {
 }
 impl<T> Eq for Slice<T> {}
 
-impl<T> Ord for Slice<T> {
-    #[inline]
-    fn cmp(&self, other: &Slice<T>) -> Ordering {
-        (&self.0 as *const [T]).cmp(&(&other.0 as *const [T]))
-    }
-}
-impl<T> PartialOrd for Slice<T> {
-    #[inline]
-    fn partial_cmp(&self, other: &Slice<T>) -> Option<Ordering> {
-        Some(self.cmp(other))
-    }
-}
-
 impl<T> Hash for Slice<T> {
     fn hash<H: Hasher>(&self, s: &mut H) {
         (self.as_ptr(), self.len()).hash(s)
@@ -1128,7 +1100,7 @@ pub type PolySubtypePredicate<'tcx> = ty::Binder<SubtypePredicate<'tcx>>;
 /// equality between arbitrary types. Processing an instance of
 /// Form #2 eventually yields one of these `ProjectionPredicate`
 /// instances to normalize the LHS.
-#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
+#[derive(Copy, Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 pub struct ProjectionPredicate<'tcx> {
     pub projection_ty: ProjectionTy<'tcx>,
     pub ty: Ty<'tcx>,
@@ -1532,7 +1504,7 @@ impl<'gcx> HashStable<StableHashingContext<'gcx>> for AdtDef {
     }
 }
 
-#[derive(Copy, Clone, Debug, Eq, PartialEq)]
+#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
 pub enum AdtKind { Struct, Union, Enum }
 
 bitflags! {
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 961c2650afd..503418b044f 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -645,7 +645,7 @@ impl<'tcx> PolyExistentialTraitRef<'tcx> {
 /// erase, or otherwise "discharge" these bound regions, we change the
 /// type from `Binder<T>` to just `T` (see
 /// e.g. `liberate_late_bound_regions`).
-#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, RustcEncodable, RustcDecodable)]
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable)]
 pub struct Binder<T>(pub T);
 
 impl<T> Binder<T> {
@@ -745,7 +745,7 @@ impl<T> Binder<T> {
 
 /// Represents the projection of an associated type. In explicit UFCS
 /// form this would be written `<T as Trait<..>>::N`.
-#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, RustcEncodable, RustcDecodable)]
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable)]
 pub struct ProjectionTy<'tcx> {
     /// The parameters of the associated item.
     pub substs: &'tcx Substs<'tcx>,
diff --git a/src/librustc/ty/subst.rs b/src/librustc/ty/subst.rs
index 7c167f69ebd..80b113dfdf5 100644
--- a/src/librustc/ty/subst.rs
+++ b/src/librustc/ty/subst.rs
@@ -29,7 +29,7 @@ use std::mem;
 /// To reduce memory usage, a `Kind` is a interned pointer,
 /// with the lowest 2 bits being reserved for a tag to
 /// indicate the type (`Ty` or `Region`) it points to.
-#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
+#[derive(Copy, Clone, PartialEq, Eq, Hash)]
 pub struct Kind<'tcx> {
     ptr: NonZero<usize>,
     marker: PhantomData<(Ty<'tcx>, ty::Region<'tcx>)>