auto merge of #20972 : FlaPer87/rust/oibit-send-and-friends, r=nikomatsakis

This PR adds rules for negative implementations. It follows pretty much what the [RFC](https://github.com/rust-lang/rfcs/blob/master/text/0019-opt-in-builtin-traits.md) says with 1 main difference:

Instead of positive implementations override negative implementations, this have been implemented in a way that a negative implementation of `Trait` for `T` will overlap with a positive implementation, causing a coherence error.

@nikomatsakis r?

cc #13231

[breaking-change]

4 files changed, 75 insertions, 9 deletions

diff --git a/src/librustc/metadata/csearch.rs b/src/librustc/metadata/csearch.rs
index 0bbd11bea0a..e34fb37e1c5 100644
--- a/src/librustc/metadata/csearch.rs
+++ b/src/librustc/metadata/csearch.rs
@@ -262,6 +262,15 @@ pub fn get_field_type<'tcx>(tcx: &ty::ctxt<'tcx>, class_id: ast::DefId,
     }
 }
 
+pub fn get_impl_polarity<'tcx>(tcx: &ty::ctxt<'tcx>,
+                               def: ast::DefId)
+                               -> Option<ast::ImplPolarity>
+{
+    let cstore = &tcx.sess.cstore;
+    let cdata = cstore.get_crate_data(def.krate);
+    decoder::get_impl_polarity(&*cdata, def.node)
+}
+
 // Given a def_id for an impl, return the trait it implements,
 // if there is one.
 pub fn get_impl_trait<'tcx>(tcx: &ty::ctxt<'tcx>,
diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index dfbff715688..6bf1798d246 100644
--- a/src/librustc/metadata/decoder.rs
+++ b/src/librustc/metadata/decoder.rs
@@ -371,6 +371,15 @@ fn parse_unsafety(item_doc: rbml::Doc) -> ast::Unsafety {
     }
 }
 
+fn parse_polarity(item_doc: rbml::Doc) -> ast::ImplPolarity {
+    let polarity_doc = reader::get_doc(item_doc, tag_polarity);
+    if reader::doc_as_u8(polarity_doc) != 0 {
+        ast::ImplPolarity::Negative
+    } else {
+        ast::ImplPolarity::Positive
+    }
+}
+
 fn parse_associated_type_names(item_doc: rbml::Doc) -> Vec<ast::Name> {
     let names_doc = reader::get_doc(item_doc, tag_associated_type_names);
     let mut names = Vec::new();
@@ -436,6 +445,20 @@ pub fn get_repr_attrs(cdata: Cmd, id: ast::NodeId) -> Vec<attr::ReprAttr> {
     }
 }
 
+pub fn get_impl_polarity<'tcx>(cdata: Cmd,
+                               id: ast::NodeId)
+                               -> Option<ast::ImplPolarity>
+{
+    let item_doc = lookup_item(id, cdata.data());
+    let fam = item_family(item_doc);
+    match fam {
+        Family::Impl => {
+            Some(parse_polarity(item_doc))
+        }
+        _ => None
+    }
+}
+
 pub fn get_impl_trait<'tcx>(cdata: Cmd,
                             id: ast::NodeId,
                             tcx: &ty::ctxt<'tcx>)
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index a38814580f5..62649653a69 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -611,6 +611,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             return Ok(None);
         }
 
+
         // If there are *NO* candidates, that there are no impls --
         // that we know of, anyway. Note that in the case where there
         // are unbound type variables within the obligation, it might
@@ -626,6 +627,17 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         // Just one candidate left.
         let candidate = candidates.pop().unwrap();
+
+        match candidate {
+            ImplCandidate(def_id) => {
+                match ty::trait_impl_polarity(self.tcx(), def_id) {
+                    Some(ast::ImplPolarity::Negative) => return Err(Unimplemented),
+                    _ => {}
+                }
+            }
+            _ => {}
+        }
+
         Ok(Some(candidate))
     }
 
@@ -714,7 +726,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 debug!("obligation self ty is {}",
                        obligation.predicate.0.self_ty().repr(self.tcx()));
 
-                try!(self.assemble_candidates_from_impls(obligation, &mut candidates.vec));
+                try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
 
                 try!(self.assemble_builtin_bound_candidates(ty::BoundCopy,
                                                             stack,
@@ -722,10 +734,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             }
             Some(bound @ ty::BoundSend) |
             Some(bound @ ty::BoundSync) => {
-                try!(self.assemble_candidates_from_impls(obligation, &mut candidates.vec));
+                try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
 
                 // No explicit impls were declared for this type, consider the fallback rules.
-                if candidates.vec.is_empty() {
+                if candidates.vec.is_empty() && !candidates.ambiguous {
                     try!(self.assemble_builtin_bound_candidates(bound, stack, &mut candidates));
                 }
             }
@@ -741,7 +753,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 // (And unboxed candidates only apply to the Fn/FnMut/etc traits.)
                 try!(self.assemble_unboxed_closure_candidates(obligation, &mut candidates));
                 try!(self.assemble_fn_pointer_candidates(obligation, &mut candidates));
-                try!(self.assemble_candidates_from_impls(obligation, &mut candidates.vec));
+                try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
                 self.assemble_candidates_from_object_ty(obligation, &mut candidates);
             }
         }
@@ -1013,9 +1025,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     /// Search for impls that might apply to `obligation`.
     fn assemble_candidates_from_impls(&mut self,
                                       obligation: &TraitObligation<'tcx>,
-                                      candidate_vec: &mut Vec<SelectionCandidate<'tcx>>)
+                                      candidates: &mut SelectionCandidateSet<'tcx>)
                                       -> Result<(), SelectionError<'tcx>>
     {
+        let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
+        debug!("assemble_candidates_from_impls(self_ty={})", self_ty.repr(self.tcx()));
+
         let all_impls = self.all_impls(obligation.predicate.def_id());
         for &impl_def_id in all_impls.iter() {
             self.infcx.probe(|snapshot| {
@@ -1024,7 +1039,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 match self.match_impl(impl_def_id, obligation, snapshot,
                                       &skol_map, skol_obligation_trait_pred.trait_ref.clone()) {
                     Ok(_) => {
-                        candidate_vec.push(ImplCandidate(impl_def_id));
+                        candidates.vec.push(ImplCandidate(impl_def_id));
                     }
                     Err(()) => { }
                 }
@@ -2214,8 +2229,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
     /// Returns set of all impls for a given trait.
     fn all_impls(&self, trait_def_id: ast::DefId) -> Vec<ast::DefId> {
-        ty::populate_implementations_for_trait_if_necessary(self.tcx(),
-                                                            trait_def_id);
+        ty::populate_implementations_for_trait_if_necessary(self.tcx(), trait_def_id);
+
         match self.tcx().trait_impls.borrow().get(&trait_def_id) {
             None => Vec::new(),
             Some(impls) => impls.borrow().clone()
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 11b605e2e2f..c72fbc74565 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -1891,7 +1891,7 @@ pub type PolyTypeOutlivesPredicate<'tcx> = PolyOutlivesPredicate<Ty<'tcx>, ty::R
 /// normal trait predicate (`T : TraitRef<...>`) and one of these
 /// predicates. Form #2 is a broader form in that it also permits
 /// equality between arbitrary types. Processing an instance of Form
-/// \#2 eventually yields one of these `ProjectionPredicate`
+/// #2 eventually yields one of these `ProjectionPredicate`
 /// instances to normalize the LHS.
 #[derive(Clone, PartialEq, Eq, Hash, Show)]
 pub struct ProjectionPredicate<'tcx> {
@@ -5035,6 +5035,23 @@ pub fn trait_items<'tcx>(cx: &ctxt<'tcx>, trait_did: ast::DefId)
     }
 }
 
+pub fn trait_impl_polarity<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
+                            -> Option<ast::ImplPolarity> {
+     if id.krate == ast::LOCAL_CRATE {
+         match cx.map.find(id.node) {
+             Some(ast_map::NodeItem(item)) => {
+                 match item.node {
+                     ast::ItemImpl(_, polarity, _, _, _, _) => Some(polarity),
+                     _ => None
+                 }
+             }
+             _ => None
+         }
+     } else {
+         csearch::get_impl_polarity(cx, id)
+     }
+}
+
 pub fn impl_or_trait_item<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
                                 -> ImplOrTraitItem<'tcx> {
     lookup_locally_or_in_crate_store("impl_or_trait_items",
@@ -5984,6 +6001,7 @@ pub fn item_variances(tcx: &ctxt, item_id: ast::DefId) -> Rc<ItemVariances> {
 pub fn record_trait_implementation(tcx: &ctxt,
                                    trait_def_id: DefId,
                                    impl_def_id: DefId) {
+
     match tcx.trait_impls.borrow().get(&trait_def_id) {
         Some(impls_for_trait) => {
             impls_for_trait.borrow_mut().push(impl_def_id);
@@ -5991,6 +6009,7 @@ pub fn record_trait_implementation(tcx: &ctxt,
         }
         None => {}
     }
+
     tcx.trait_impls.borrow_mut().insert(trait_def_id, Rc::new(RefCell::new(vec!(impl_def_id))));
 }