Auto merge of #22541 - Manishearth:rollup, r=Gankro 1.0.0-alpha.2

Continued from #22520

4 files changed, 135 insertions, 51 deletions

diff --git a/src/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs
index 3a7522cafee..e199a60c370 100644
--- a/src/librustc/middle/traits/coherence.rs
+++ b/src/librustc/middle/traits/coherence.rs
@@ -10,24 +10,27 @@
 
 //! See `doc.rs` for high-level documentation
 
+use super::Normalized;
 use super::SelectionContext;
-use super::{Obligation, ObligationCause};
+use super::{ObligationCause};
+use super::PredicateObligation;
 use super::project;
 use super::util;
 
 use middle::subst::{Subst, TypeSpace};
-use middle::ty::{self, Ty};
-use middle::infer::InferCtxt;
+use middle::ty::{self, ToPolyTraitRef, Ty};
+use middle::infer::{self, InferCtxt};
 use std::collections::HashSet;
 use std::rc::Rc;
 use syntax::ast;
 use syntax::codemap::DUMMY_SP;
 use util::ppaux::Repr;
 
-pub fn impl_can_satisfy(infcx: &InferCtxt,
-                        impl1_def_id: ast::DefId,
-                        impl2_def_id: ast::DefId)
-                        -> bool
+/// True if there exist types that satisfy both of the two given impls.
+pub fn overlapping_impls(infcx: &InferCtxt,
+                         impl1_def_id: ast::DefId,
+                         impl2_def_id: ast::DefId)
+                         -> bool
 {
     debug!("impl_can_satisfy(\
            impl1_def_id={}, \
@@ -35,28 +38,68 @@ pub fn impl_can_satisfy(infcx: &InferCtxt,
            impl1_def_id.repr(infcx.tcx),
            impl2_def_id.repr(infcx.tcx));
 
-    let param_env = ty::empty_parameter_environment(infcx.tcx);
-    let mut selcx = SelectionContext::intercrate(infcx, &param_env);
-    let cause = ObligationCause::dummy();
-
-    // `impl1` provides an implementation of `Foo<X,Y> for Z`.
-    let impl1_substs =
-        util::fresh_substs_for_impl(infcx, DUMMY_SP, impl1_def_id);
-    let impl1_trait_ref =
-        (*ty::impl_trait_ref(infcx.tcx, impl1_def_id).unwrap()).subst(infcx.tcx, &impl1_substs);
-    let impl1_trait_ref =
-        project::normalize(&mut selcx, cause.clone(), &impl1_trait_ref);
-
-    // Determine whether `impl2` can provide an implementation for those
-    // same types.
-    let obligation = Obligation::new(cause,
-                                     ty::Binder(ty::TraitPredicate {
-                                         trait_ref: Rc::new(impl1_trait_ref.value),
-                                     }));
-    debug!("impl_can_satisfy(obligation={})", obligation.repr(infcx.tcx));
-    selcx.evaluate_impl(impl2_def_id, &obligation) &&
-        impl1_trait_ref.obligations.iter().all(
-            |o| selcx.evaluate_obligation(o))
+    let param_env = &ty::empty_parameter_environment(infcx.tcx);
+    let selcx = &mut SelectionContext::intercrate(infcx, param_env);
+    infcx.probe(|_| {
+        overlap(selcx, impl1_def_id, impl2_def_id) || overlap(selcx, impl2_def_id, impl1_def_id)
+    })
+}
+
+/// Can the types from impl `a` be used to satisfy impl `b`?
+/// (Including all conditions)
+fn overlap(selcx: &mut SelectionContext,
+           a_def_id: ast::DefId,
+           b_def_id: ast::DefId)
+           -> bool
+{
+    let (a_trait_ref, a_obligations) = impl_trait_ref_and_oblig(selcx, a_def_id);
+    let (b_trait_ref, b_obligations) = impl_trait_ref_and_oblig(selcx, b_def_id);
+
+    // Does `a <: b` hold? If not, no overlap.
+    if let Err(_) = infer::mk_sub_poly_trait_refs(selcx.infcx(),
+                                                  true,
+                                                  infer::Misc(DUMMY_SP),
+                                                  a_trait_ref.to_poly_trait_ref(),
+                                                  b_trait_ref.to_poly_trait_ref()) {
+        return false;
+    }
+
+    // Are any of the obligations unsatisfiable? If so, no overlap.
+    a_obligations.iter()
+                 .chain(b_obligations.iter())
+                 .all(|o| selcx.evaluate_obligation(o))
+}
+
+/// Instantiate fresh variables for all bound parameters of the impl
+/// and return the impl trait ref with those variables substituted.
+fn impl_trait_ref_and_oblig<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
+                                     impl_def_id: ast::DefId)
+                                     -> (Rc<ty::TraitRef<'tcx>>,
+                                         Vec<PredicateObligation<'tcx>>)
+{
+    let impl_substs =
+        &util::fresh_substs_for_impl(selcx.infcx(), DUMMY_SP, impl_def_id);
+    let impl_trait_ref =
+        ty::impl_trait_ref(selcx.tcx(), impl_def_id).unwrap();
+    let impl_trait_ref =
+        impl_trait_ref.subst(selcx.tcx(), impl_substs);
+    let Normalized { value: impl_trait_ref, obligations: normalization_obligations1 } =
+        project::normalize(selcx, ObligationCause::dummy(), &impl_trait_ref);
+
+    let predicates = ty::lookup_predicates(selcx.tcx(), impl_def_id);
+    let predicates = predicates.instantiate(selcx.tcx(), impl_substs);
+    let Normalized { value: predicates, obligations: normalization_obligations2 } =
+        project::normalize(selcx, ObligationCause::dummy(), &predicates);
+    let impl_obligations =
+        util::predicates_for_generics(selcx.tcx(), ObligationCause::dummy(), 0, &predicates);
+
+    let impl_obligations: Vec<_> =
+        impl_obligations.into_iter()
+        .chain(normalization_obligations1.into_iter())
+        .chain(normalization_obligations2.into_iter())
+        .collect();
+
+    (impl_trait_ref, impl_obligations)
 }
 
 pub enum OrphanCheckErr<'tcx> {
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index 57c9fa7a4d9..a63dcfc24a1 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -28,6 +28,7 @@ use util::ppaux::{Repr, UserString};
 pub use self::error_reporting::report_fulfillment_errors;
 pub use self::error_reporting::suggest_new_overflow_limit;
 pub use self::coherence::orphan_check;
+pub use self::coherence::overlapping_impls;
 pub use self::coherence::OrphanCheckErr;
 pub use self::fulfill::{FulfillmentContext, RegionObligation};
 pub use self::project::MismatchedProjectionTypes;
@@ -270,16 +271,6 @@ pub struct VtableObjectData<'tcx> {
     pub object_ty: Ty<'tcx>,
 }
 
-/// True if there exist types that satisfy both of the two given impls.
-pub fn overlapping_impls(infcx: &InferCtxt,
-                         impl1_def_id: ast::DefId,
-                         impl2_def_id: ast::DefId)
-                         -> bool
-{
-    coherence::impl_can_satisfy(infcx, impl1_def_id, impl2_def_id) &&
-    coherence::impl_can_satisfy(infcx, impl2_def_id, impl1_def_id)
-}
-
 /// Creates predicate obligations from the generic bounds.
 pub fn predicates_for_generics<'tcx>(tcx: &ty::ctxt<'tcx>,
                                      cause: ObligationCause<'tcx>,
diff --git a/src/librustc/middle/traits/object_safety.rs b/src/librustc/middle/traits/object_safety.rs
index b2701ae875c..f10f7eb3951 100644
--- a/src/librustc/middle/traits/object_safety.rs
+++ b/src/librustc/middle/traits/object_safety.rs
@@ -20,7 +20,7 @@
 use super::supertraits;
 use super::elaborate_predicates;
 
-use middle::subst::{self, SelfSpace};
+use middle::subst::{self, SelfSpace, TypeSpace};
 use middle::traits;
 use middle::ty::{self, Ty};
 use std::rc::Rc;
@@ -31,6 +31,10 @@ pub enum ObjectSafetyViolation<'tcx> {
     /// Self : Sized declared on the trait
     SizedSelf,
 
+    /// Supertrait reference references `Self` an in illegal location
+    /// (e.g. `trait Foo : Bar<Self>`)
+    SupertraitSelf,
+
     /// Method has something illegal
     Method(Rc<ty::Method<'tcx>>, MethodViolationCode),
 }
@@ -57,7 +61,7 @@ pub fn is_object_safe<'tcx>(tcx: &ty::ctxt<'tcx>,
 {
     // Because we query yes/no results frequently, we keep a cache:
     let cached_result =
-        tcx.object_safety_cache.borrow().get(&trait_ref.def_id()).map(|&r| r);
+        tcx.object_safety_cache.borrow().get(&trait_ref.def_id()).cloned();
 
     let result =
         cached_result.unwrap_or_else(|| {
@@ -110,6 +114,9 @@ fn object_safety_violations_for_trait<'tcx>(tcx: &ty::ctxt<'tcx>,
     if trait_has_sized_self(tcx, trait_def_id) {
         violations.push(ObjectSafetyViolation::SizedSelf);
     }
+    if supertraits_reference_self(tcx, trait_def_id) {
+        violations.push(ObjectSafetyViolation::SupertraitSelf);
+    }
 
     debug!("object_safety_violations_for_trait(trait_def_id={}) = {}",
            trait_def_id.repr(tcx),
@@ -118,6 +125,35 @@ fn object_safety_violations_for_trait<'tcx>(tcx: &ty::ctxt<'tcx>,
     violations
 }
 
+fn supertraits_reference_self<'tcx>(tcx: &ty::ctxt<'tcx>,
+                                    trait_def_id: ast::DefId)
+                                    -> bool
+{
+    let trait_def = ty::lookup_trait_def(tcx, trait_def_id);
+    let trait_ref = trait_def.trait_ref.clone();
+    let predicates = ty::predicates_for_trait_ref(tcx, &ty::Binder(trait_ref));
+    predicates
+        .into_iter()
+        .any(|predicate| {
+            match predicate {
+                ty::Predicate::Trait(ref data) => {
+                    // In the case of a trait predicate, we can skip the "self" type.
+                    Some(data.def_id()) != tcx.lang_items.phantom_fn() &&
+                        data.0.trait_ref.substs.types.get_slice(TypeSpace)
+                                                     .iter()
+                                                     .cloned()
+                                                     .any(is_self)
+                }
+                ty::Predicate::Projection(..) |
+                ty::Predicate::TypeOutlives(..) |
+                ty::Predicate::RegionOutlives(..) |
+                ty::Predicate::Equate(..) => {
+                    false
+                }
+            }
+        })
+}
+
 fn trait_has_sized_self<'tcx>(tcx: &ty::ctxt<'tcx>,
                               trait_def_id: ast::DefId)
                               -> bool
@@ -138,11 +174,7 @@ fn trait_has_sized_self<'tcx>(tcx: &ty::ctxt<'tcx>,
         .any(|predicate| {
             match predicate {
                 ty::Predicate::Trait(ref trait_pred) if trait_pred.def_id() == sized_def_id => {
-                    let self_ty = trait_pred.0.self_ty();
-                    match self_ty.sty {
-                        ty::ty_param(ref data) => data.space == subst::SelfSpace,
-                        _ => false,
-                    }
+                    is_self(trait_pred.0.self_ty())
                 }
                 ty::Predicate::Projection(..) |
                 ty::Predicate::Trait(..) |
@@ -295,8 +327,17 @@ impl<'tcx> Repr<'tcx> for ObjectSafetyViolation<'tcx> {
         match *self {
             ObjectSafetyViolation::SizedSelf =>
                 format!("SizedSelf"),
+            ObjectSafetyViolation::SupertraitSelf =>
+                format!("SupertraitSelf"),
             ObjectSafetyViolation::Method(ref m, code) =>
                 format!("Method({},{:?})", m.repr(tcx), code),
         }
     }
 }
+
+fn is_self<'tcx>(ty: Ty<'tcx>) -> bool {
+    match ty.sty {
+        ty::ty_param(ref data) => data.space == subst::SelfSpace,
+        _ => false,
+    }
+}
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 027415de998..0e298920841 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -132,6 +132,7 @@ pub enum MethodMatchedData {
 /// parameters) that would have to be inferred from the impl.
 #[derive(PartialEq,Eq,Debug,Clone)]
 enum SelectionCandidate<'tcx> {
+    PhantomFnCandidate,
     BuiltinCandidate(ty::BuiltinBound),
     ParamCandidate(ty::PolyTraitRef<'tcx>),
     ImplCandidate(ast::DefId),
@@ -736,7 +737,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     {
         let cache = self.pick_candidate_cache();
         let hashmap = cache.hashmap.borrow();
-        hashmap.get(&cache_fresh_trait_pred.0.trait_ref).map(|c| (*c).clone())
+        hashmap.get(&cache_fresh_trait_pred.0.trait_ref).cloned()
     }
 
     fn insert_candidate_cache(&mut self,
@@ -793,8 +794,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                stack: &TraitObligationStack<'o, 'tcx>)
                                -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>>
     {
-        // Check for overflow.
-
         let TraitObligationStack { obligation, .. } = *stack;
 
         let mut candidates = SelectionCandidateSet {
@@ -802,6 +801,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             ambiguous: false
         };
 
+        // Check for the `PhantomFn` trait. This is really just a
+        // special annotation that is *always* considered to match, no
+        // matter what the type parameters are etc.
+        if self.tcx().lang_items.phantom_fn() == Some(obligation.predicate.def_id()) {
+            candidates.vec.push(PhantomFnCandidate);
+            return Ok(candidates);
+        }
+
         // Other bounds. Consider both in-scope bounds from fn decl
         // and applicable impls. There is a certain set of precedence rules here.
 
@@ -996,7 +1003,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         let all_bounds =
             util::transitive_bounds(
-                self.tcx(), &caller_trait_refs[]);
+                self.tcx(), &caller_trait_refs[..]);
 
         let matching_bounds =
             all_bounds.filter(
@@ -1521,7 +1528,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     ty::substd_enum_variants(self.tcx(), def_id, substs)
                     .iter()
                     .flat_map(|variant| variant.args.iter())
-                    .map(|&ty| ty)
+                    .cloned()
                     .collect();
                 nominal(self, bound, def_id, types)
             }
@@ -1629,6 +1636,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     try!(self.confirm_builtin_candidate(obligation, builtin_bound))))
             }
 
+            PhantomFnCandidate |
             ErrorCandidate => {
                 Ok(VtableBuiltin(VtableBuiltinData { nested: VecPerParamSpace::empty() }))
             }
@@ -2295,6 +2303,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 impl<'tcx> Repr<'tcx> for SelectionCandidate<'tcx> {
     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
         match *self {
+            PhantomFnCandidate => format!("PhantomFnCandidate"),
             ErrorCandidate => format!("ErrorCandidate"),
             BuiltinCandidate(b) => format!("BuiltinCandidate({:?})", b),
             ParamCandidate(ref a) => format!("ParamCandidate({})", a.repr(tcx)),