Add syntax for negative implementations of traits

This commit introduces the syntax for negative implmenetations of traits
as shown below:

`impl !Trait for Type {}`

cc #13231
Part of RFC #3

34 files changed, 176 insertions, 39 deletions

diff --git a/src/librustc/lint/builtin.rs b/src/librustc/lint/builtin.rs
index 8f03f882128..bd3c22065c1 100644
--- a/src/librustc/lint/builtin.rs
+++ b/src/librustc/lint/builtin.rs
@@ -1762,7 +1762,7 @@ impl LintPass for Stability {
                     }
                 }
             }
-            ast::ItemImpl(_, _, Some(ref t), _, _) => {
+            ast::ItemImpl(_, _, _, Some(ref t), _, _) => {
                 let id = ty::trait_ref_to_def_id(cx.tcx, t);
                 self.lint(cx, id, t.path.span);
             }
diff --git a/src/librustc/metadata/common.rs b/src/librustc/metadata/common.rs
index cc21243b81d..ca7c65c8e2b 100644
--- a/src/librustc/metadata/common.rs
+++ b/src/librustc/metadata/common.rs
@@ -259,3 +259,5 @@ pub const tag_unsafety: uint = 0xb1;
 
 pub const tag_associated_type_names: uint = 0xb2;
 pub const tag_associated_type_name: uint = 0xb3;
+
+pub const tag_polarity: uint = 0xb4;
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index 75b9a18063e..59679f0bc7c 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -1207,7 +1207,7 @@ fn encode_info_for_item(ecx: &EncodeContext,
             None => {}
         }
       }
-      ast::ItemImpl(unsafety, _, ref opt_trait, ref ty, ref ast_items) => {
+      ast::ItemImpl(unsafety, polarity, _, ref opt_trait, ref ty, ref ast_items) => {
         // We need to encode information about the default methods we
         // have inherited, so we drive this based on the impl structure.
         let impl_items = tcx.impl_items.borrow();
@@ -1221,6 +1221,7 @@ fn encode_info_for_item(ecx: &EncodeContext,
         encode_name(rbml_w, item.ident.name);
         encode_attributes(rbml_w, item.attrs[]);
         encode_unsafety(rbml_w, unsafety);
+        encode_polarity(rbml_w, polarity);
         match ty.node {
             ast::TyPath(ref path, _) if path.segments.len() == 1 => {
                 let ident = path.segments.last().unwrap().identifier;
@@ -1704,6 +1705,14 @@ fn encode_associated_type_names(rbml_w: &mut Encoder, names: &[ast::Name]) {
     rbml_w.end_tag();
 }
 
+fn encode_polarity(rbml_w: &mut Encoder, polarity: ast::ImplPolarity) {
+    let byte: u8 = match polarity {
+        ast::ImplPolarity::Positive => 0,
+        ast::ImplPolarity::Negative => 1,
+    };
+    rbml_w.wr_tagged_u8(tag_polarity, byte);
+}
+
 fn encode_crate_deps(rbml_w: &mut Encoder, cstore: &cstore::CStore) {
     fn get_ordered_deps(cstore: &cstore::CStore) -> Vec<decoder::CrateDep> {
         // Pull the cnums and name,vers,hash out of cstore
@@ -1885,7 +1894,7 @@ struct ImplVisitor<'a, 'b:'a, 'c:'a, 'tcx:'b> {
 
 impl<'a, 'b, 'c, 'tcx, 'v> Visitor<'v> for ImplVisitor<'a, 'b, 'c, 'tcx> {
     fn visit_item(&mut self, item: &ast::Item) {
-        if let ast::ItemImpl(_, _, Some(ref trait_ref), _, _) = item.node {
+        if let ast::ItemImpl(_, _, _, Some(ref trait_ref), _, _) = item.node {
             let def_map = &self.ecx.tcx.def_map;
             let trait_def = def_map.borrow()[trait_ref.ref_id].clone();
             let def_id = trait_def.def_id();
diff --git a/src/librustc/middle/dead.rs b/src/librustc/middle/dead.rs
index 5a2085bee24..2e40bdd001a 100644
--- a/src/librustc/middle/dead.rs
+++ b/src/librustc/middle/dead.rs
@@ -355,7 +355,7 @@ impl<'v> Visitor<'v> for LifeSeeder {
             ast::ItemEnum(ref enum_def, _) if allow_dead_code => {
                 self.worklist.extend(enum_def.variants.iter().map(|variant| variant.node.id));
             }
-            ast::ItemImpl(_, _, Some(ref _trait_ref), _, ref impl_items) => {
+            ast::ItemImpl(_, _, _, Some(ref _trait_ref), _, ref impl_items) => {
                 for impl_item in impl_items.iter() {
                     match *impl_item {
                         ast::MethodImplItem(ref method) => {
diff --git a/src/librustc/middle/infer/error_reporting.rs b/src/librustc/middle/infer/error_reporting.rs
index 7ff585087f5..c015c2307f6 100644
--- a/src/librustc/middle/infer/error_reporting.rs
+++ b/src/librustc/middle/infer/error_reporting.rs
@@ -1712,7 +1712,7 @@ fn lifetimes_in_scope(tcx: &ty::ctxt,
         match tcx.map.find(parent) {
             Some(node) => match node {
                 ast_map::NodeItem(item) => match item.node {
-                    ast::ItemImpl(_, ref gen, _, _, _) => {
+                    ast::ItemImpl(_, _, ref gen, _, _, _) => {
                         taken.push_all(gen.lifetimes.as_slice());
                     }
                     _ => ()
diff --git a/src/librustc/middle/privacy.rs b/src/librustc/middle/privacy.rs
index e6665699b7b..ace0882a12c 100644
--- a/src/librustc/middle/privacy.rs
+++ b/src/librustc/middle/privacy.rs
@@ -287,7 +287,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for EmbargoVisitor<'a, 'tcx> {
             //   undefined symbols at linkage time if this case is not handled.
             //
             // * Private trait impls for private types can be completely ignored
-            ast::ItemImpl(_, _, _, ref ty, ref impl_items) => {
+            ast::ItemImpl(_, _, _, _, ref ty, ref impl_items) => {
                 let public_ty = match ty.node {
                     ast::TyPath(_, id) => {
                         match self.tcx.def_map.borrow()[id].clone() {
@@ -657,7 +657,7 @@ impl<'a, 'tcx> PrivacyVisitor<'a, 'tcx> {
                     // invoked, and the struct/enum itself is private. Crawl
                     // back up the chains to find the relevant struct/enum that
                     // was private.
-                    ast::ItemImpl(_, _, _, ref ty, _) => {
+                    ast::ItemImpl(_, _, _, _, ref ty, _) => {
                         let id = match ty.node {
                             ast::TyPath(_, id) => id,
                             _ => return Some((err_span, err_msg, None)),
@@ -1137,7 +1137,7 @@ impl<'a, 'tcx> SanePrivacyVisitor<'a, 'tcx> {
         match item.node {
             // implementations of traits don't need visibility qualifiers because
             // that's controlled by having the trait in scope.
-            ast::ItemImpl(_, _, Some(..), _, ref impl_items) => {
+            ast::ItemImpl(_, _, _, Some(..), _, ref impl_items) => {
                 check_inherited(item.span, item.vis,
                                 "visibility qualifiers have no effect on trait \
                                  impls");
@@ -1216,7 +1216,7 @@ impl<'a, 'tcx> SanePrivacyVisitor<'a, 'tcx> {
         };
         check_inherited(tcx, item.span, item.vis);
         match item.node {
-            ast::ItemImpl(_, _, _, _, ref impl_items) => {
+            ast::ItemImpl(_, _, _, _, _, ref impl_items) => {
                 for impl_item in impl_items.iter() {
                     match *impl_item {
                         ast::MethodImplItem(ref m) => {
@@ -1361,7 +1361,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for VisiblePrivateTypesVisitor<'a, 'tcx> {
             // (i.e. we could just return here to not check them at
             // all, or some worse estimation of whether an impl is
             // publicly visible.
-            ast::ItemImpl(_, ref g, ref trait_ref, ref self_, ref impl_items) => {
+            ast::ItemImpl(_, _, ref g, ref trait_ref, ref self_, ref impl_items) => {
                 // `impl [... for] Private` is never visible.
                 let self_contains_private;
                 // impl [... for] Public<...>, but not `impl [... for]
diff --git a/src/librustc/middle/reachable.rs b/src/librustc/middle/reachable.rs
index 4d83075480b..5736e307286 100644
--- a/src/librustc/middle/reachable.rs
+++ b/src/librustc/middle/reachable.rs
@@ -55,7 +55,7 @@ fn item_might_be_inlined(item: &ast::Item) -> bool {
     }
 
     match item.node {
-        ast::ItemImpl(_, ref generics, _, _, _) |
+        ast::ItemImpl(_, _, ref generics, _, _, _) |
         ast::ItemFn(_, _, _, ref generics, _) => {
             generics_require_inlining(generics)
         }
@@ -216,7 +216,7 @@ impl<'a, 'tcx> ReachableContext<'a, 'tcx> {
                                       .map
                                       .expect_item(impl_did.node)
                                       .node {
-                                ast::ItemImpl(_, ref generics, _, _, _) => {
+                                ast::ItemImpl(_, _, ref generics, _, _, _) => {
                                     generics_require_inlining(generics)
                                 }
                                 _ => false
diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index 5eb033a01bd..c9273e0b8d5 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -106,7 +106,7 @@ impl<'a, 'v> Visitor<'v> for LifetimeContext<'a> {
                 ast::ItemEnum(_, ref generics) |
                 ast::ItemStruct(_, ref generics) |
                 ast::ItemTrait(_, ref generics, _, _) |
-                ast::ItemImpl(_, ref generics, _, _, _) => {
+                ast::ItemImpl(_, _, ref generics, _, _, _) => {
                     // These kinds of items have only early bound lifetime parameters.
                     let lifetimes = &generics.lifetimes;
                     let early_scope = EarlyScope(subst::TypeSpace, lifetimes, &ROOT_SCOPE);
diff --git a/src/librustc/middle/stability.rs b/src/librustc/middle/stability.rs
index 505352fa123..362d5fedaa3 100644
--- a/src/librustc/middle/stability.rs
+++ b/src/librustc/middle/stability.rs
@@ -82,7 +82,7 @@ impl<'v> Visitor<'v> for Annotator {
         // stability of the trait. This is WRONG, but expedient to get
         // libstd stabilized for the 1.0 release.
         let use_parent = match i.node {
-            ast::ItemImpl(_, _, Some(_), _, _) => false,
+            ast::ItemImpl(_, _, _, Some(_), _, _) => false,
             _ => true,
         };
 
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index d168e84a01c..9b85d8d2290 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -5128,7 +5128,7 @@ pub fn impl_trait_ref<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
             match cx.map.find(id.node) {
                 Some(ast_map::NodeItem(item)) => {
                     match item.node {
-                        ast::ItemImpl(_, _, ref opt_trait, _, _) => {
+                        ast::ItemImpl(_, _, _, ref opt_trait, _, _) => {
                             match opt_trait {
                                 &Some(ref t) => {
                                     let trait_ref = ty::node_id_to_trait_ref(cx, t.ref_id);
diff --git a/src/librustc_resolve/build_reduced_graph.rs b/src/librustc_resolve/build_reduced_graph.rs
index d7c1a4fe17b..10788f9f7cb 100644
--- a/src/librustc_resolve/build_reduced_graph.rs
+++ b/src/librustc_resolve/build_reduced_graph.rs
@@ -386,7 +386,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                 parent.clone()
             }
 
-            ItemImpl(_, _, None, ref ty, ref impl_items) => {
+            ItemImpl(_, _, _, None, ref ty, ref impl_items) => {
                 // If this implements an anonymous trait, then add all the
                 // methods within to a new module, if the type was defined
                 // within this module.
@@ -527,7 +527,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                 parent.clone()
             }
 
-            ItemImpl(_, _, Some(_), _, _) => parent.clone(),
+            ItemImpl(_, _, _, Some(_), _, _) => parent.clone(),
 
             ItemTrait(_, _, _, ref items) => {
                 let name_bindings =
diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index 3be7aa294f1..59f0964a230 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -972,7 +972,6 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         }
     }
 
-
     // Import resolution
     //
     // This is a fixed-point algorithm. We resolve imports until our efforts
@@ -2841,7 +2840,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                 });
             }
 
-            ItemImpl(_,
+            ItemImpl(_, _,
                      ref generics,
                      ref implemented_traits,
                      ref self_type,
diff --git a/src/librustc_trans/save/mod.rs b/src/librustc_trans/save/mod.rs
index 55bdff81910..8e6276b61f9 100644
--- a/src/librustc_trans/save/mod.rs
+++ b/src/librustc_trans/save/mod.rs
@@ -283,7 +283,7 @@ impl <'l, 'tcx> DxrVisitor<'l, 'tcx> {
                 NodeItem(item) => {
                     scope_id = item.id;
                     match item.node {
-                        ast::ItemImpl(_, _, _, ref ty, _) => {
+                        ast::ItemImpl(_, _, _, _, ref ty, _) => {
                             let mut result = String::from_str("<");
                             result.push_str(ty_to_string(&**ty)[]);
 
@@ -1040,7 +1040,7 @@ impl<'l, 'tcx, 'v> Visitor<'v> for DxrVisitor<'l, 'tcx> {
                 self.process_const(item, &**typ, &**expr),
             ast::ItemStruct(ref def, ref ty_params) => self.process_struct(item, &**def, ty_params),
             ast::ItemEnum(ref def, ref ty_params) => self.process_enum(item, def, ty_params),
-            ast::ItemImpl(_,
+            ast::ItemImpl(_, _,
                           ref ty_params,
                           ref trait_ref,
                           ref typ,
diff --git a/src/librustc_trans/trans/base.rs b/src/librustc_trans/trans/base.rs
index 58cb2ebd256..8c6697f0e9d 100644
--- a/src/librustc_trans/trans/base.rs
+++ b/src/librustc_trans/trans/base.rs
@@ -2317,7 +2317,7 @@ pub fn trans_item(ccx: &CrateContext, item: &ast::Item) {
         let mut v = TransItemVisitor{ ccx: ccx };
         v.visit_block(&**body);
       }
-      ast::ItemImpl(_, ref generics, _, _, ref impl_items) => {
+      ast::ItemImpl(_, _, ref generics, _, _, ref impl_items) => {
         meth::trans_impl(ccx,
                          item.ident,
                          impl_items[],
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index e6ae5f0a447..9cd43e9182b 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -699,7 +699,7 @@ pub fn check_item(ccx: &CrateCtxt, it: &ast::Item) {
         let param_env = ParameterEnvironment::for_item(ccx.tcx, it.id);
         check_bare_fn(ccx, &**decl, &**body, it.id, fn_pty.ty, param_env);
       }
-      ast::ItemImpl(_, _, _, _, ref impl_items) => {
+      ast::ItemImpl(_, _, _, _, _, ref impl_items) => {
         debug!("ItemImpl {} with id {}", token::get_ident(it.ident), it.id);
 
         let impl_pty = ty::lookup_item_type(ccx.tcx, ast_util::local_def(it.id));
diff --git a/src/librustc_typeck/coherence/mod.rs b/src/librustc_typeck/coherence/mod.rs
index 45b248dac93..bb2c6221e21 100644
--- a/src/librustc_typeck/coherence/mod.rs
+++ b/src/librustc_typeck/coherence/mod.rs
@@ -102,7 +102,7 @@ impl<'a, 'tcx, 'v> visit::Visitor<'v> for CoherenceCheckVisitor<'a, 'tcx> {
         //debug!("(checking coherence) item '{}'", token::get_ident(item.ident));
 
         match item.node {
-            ItemImpl(_, _, ref opt_trait, _, _) => {
+            ItemImpl(_, _, _, ref opt_trait, _, _) => {
                 match opt_trait.clone() {
                     Some(opt_trait) => {
                         self.cc.check_implementation(item, &[opt_trait]);
@@ -283,7 +283,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
     // Converts an implementation in the AST to a vector of items.
     fn create_impl_from_item(&self, item: &Item) -> Vec<ImplOrTraitItemId> {
         match item.node {
-            ItemImpl(_, _, ref trait_refs, _, ref ast_items) => {
+            ItemImpl(_, _, _, ref trait_refs, _, ref ast_items) => {
                 let mut items: Vec<ImplOrTraitItemId> =
                         ast_items.iter()
                                  .map(|ast_item| {
diff --git a/src/librustc_typeck/coherence/orphan.rs b/src/librustc_typeck/coherence/orphan.rs
index 1da49799712..d90bfe04ea1 100644
--- a/src/librustc_typeck/coherence/orphan.rs
+++ b/src/librustc_typeck/coherence/orphan.rs
@@ -44,7 +44,7 @@ impl<'cx, 'tcx,'v> visit::Visitor<'v> for OrphanChecker<'cx, 'tcx> {
     fn visit_item(&mut self, item: &'v ast::Item) {
         let def_id = ast_util::local_def(item.id);
         match item.node {
-            ast::ItemImpl(_, _, None, _, _) => {
+            ast::ItemImpl(_, _, _, None, _, _) => {
                 // For inherent impls, self type must be a nominal type
                 // defined in this crate.
                 debug!("coherence2::orphan check: inherent impl {}", item.repr(self.tcx));
@@ -69,7 +69,7 @@ impl<'cx, 'tcx,'v> visit::Visitor<'v> for OrphanChecker<'cx, 'tcx> {
                     }
                 }
             }
-            ast::ItemImpl(_, _, Some(_), _, _) => {
+            ast::ItemImpl(_, _, _, Some(_), _, _) => {
                 // "Trait" impl
                 debug!("coherence2::orphan check: trait impl {}", item.repr(self.tcx));
                 match traits::orphan_check(self.tcx, def_id) {
diff --git a/src/librustc_typeck/coherence/unsafety.rs b/src/librustc_typeck/coherence/unsafety.rs
index 07a84846c47..1acea6fd581 100644
--- a/src/librustc_typeck/coherence/unsafety.rs
+++ b/src/librustc_typeck/coherence/unsafety.rs
@@ -30,7 +30,7 @@ struct UnsafetyChecker<'cx, 'tcx:'cx> {
 impl<'cx, 'tcx,'v> visit::Visitor<'v> for UnsafetyChecker<'cx, 'tcx> {
     fn visit_item(&mut self, item: &'v ast::Item) {
         match item.node {
-            ast::ItemImpl(unsafety, _, _, _, _) => {
+            ast::ItemImpl(unsafety, _, _, _, _, _) => {
                 match ty::impl_trait_ref(self.tcx, ast_util::local_def(item.id)) {
                     None => {
                         // Inherent impl.
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 009f1e50e9b..7c88404eb64 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -549,7 +549,7 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
                                    enum_definition.variants.as_slice(),
                                    generics);
         },
-        ast::ItemImpl(_,
+        ast::ItemImpl(_, _,
                       ref generics,
                       ref opt_trait_ref,
                       ref selfty,
diff --git a/src/librustdoc/doctree.rs b/src/librustdoc/doctree.rs
index d05e15ff251..99afef4173f 100644
--- a/src/librustdoc/doctree.rs
+++ b/src/librustdoc/doctree.rs
@@ -182,6 +182,7 @@ pub struct Trait {
 
 pub struct Impl {
     pub unsafety: ast::Unsafety,
+    pub polarity: ast::ImplPolarity,
     pub generics: ast::Generics,
     pub trait_: Option<ast::TraitRef>,
     pub for_: P<ast::Ty>,
diff --git a/src/librustdoc/visit_ast.rs b/src/librustdoc/visit_ast.rs
index e71711aa8d6..c98ec97ab87 100644
--- a/src/librustdoc/visit_ast.rs
+++ b/src/librustdoc/visit_ast.rs
@@ -337,9 +337,10 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
                 };
                 om.traits.push(t);
             },
-            ast::ItemImpl(unsafety, ref gen, ref tr, ref ty, ref items) => {
+            ast::ItemImpl(unsafety, polarity, ref gen, ref tr, ref ty, ref items) => {
                 let i = Impl {
                     unsafety: unsafety,
+                    polarity: polarity,
                     generics: gen.clone(),
                     trait_: tr.clone(),
                     for_: ty.clone(),
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 01f66f3bbd0..c9c3ce45f20 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -1299,6 +1299,24 @@ impl fmt::Show for Unsafety {
     }
 }
 
+#[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
+pub enum ImplPolarity {
+    /// impl Trait for Type
+    Positive,
+    /// impl !Trait for Type
+    Negative,
+}
+
+impl fmt::Show for ImplPolarity {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match *self {
+            ImplPolarity::Positive => "positive".fmt(f),
+            ImplPolarity::Negative => "negative".fmt(f),
+        }
+    }
+}
+
+
 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
 pub enum FunctionRetTy {
     /// Functions with return type ! that always
@@ -1587,6 +1605,7 @@ pub enum Item_ {
               TyParamBounds,
               Vec<TraitItem>),
     ItemImpl(Unsafety,
+             ImplPolarity,
              Generics,
              Option<TraitRef>, // (optional) trait this impl implements
              P<Ty>, // self
diff --git a/src/libsyntax/ast_map/mod.rs b/src/libsyntax/ast_map/mod.rs
index c5dbd194e3e..ce7b964959f 100644
--- a/src/libsyntax/ast_map/mod.rs
+++ b/src/libsyntax/ast_map/mod.rs
@@ -755,7 +755,7 @@ impl<'ast> Visitor<'ast> for NodeCollector<'ast> {
         let parent = self.parent;
         self.parent = i.id;
         match i.node {
-            ItemImpl(_, _, _, _, ref impl_items) => {
+            ItemImpl(_, _, _, _, _, ref impl_items) => {
                 for impl_item in impl_items.iter() {
                     match *impl_item {
                         MethodImplItem(ref m) => {
diff --git a/src/libsyntax/config.rs b/src/libsyntax/config.rs
index 94a3784291d..3f91831a5df 100644
--- a/src/libsyntax/config.rs
+++ b/src/libsyntax/config.rs
@@ -133,11 +133,11 @@ fn fold_item_underscore<F>(cx: &mut Context<F>, item: ast::Item_) -> ast::Item_
     F: FnMut(&[ast::Attribute]) -> bool
 {
     let item = match item {
-        ast::ItemImpl(u, a, b, c, impl_items) => {
+        ast::ItemImpl(u, o, a, b, c, impl_items) => {
             let impl_items = impl_items.into_iter()
                                        .filter(|ii| impl_item_in_cfg(cx, ii))
                                        .collect();
-            ast::ItemImpl(u, a, b, c, impl_items)
+            ast::ItemImpl(u, o, a, b, c, impl_items)
         }
         ast::ItemTrait(u, a, b, methods) => {
             let methods = methods.into_iter()
diff --git a/src/libsyntax/ext/deriving/generic/mod.rs b/src/libsyntax/ext/deriving/generic/mod.rs
index 8863de8757b..459abf15b33 100644
--- a/src/libsyntax/ext/deriving/generic/mod.rs
+++ b/src/libsyntax/ext/deriving/generic/mod.rs
@@ -488,6 +488,7 @@ impl<'a> TraitDef<'a> {
             ident,
             a,
             ast::ItemImpl(ast::Unsafety::Normal,
+                          ast::ImplPolarity::Positive,
                           trait_generics,
                           opt_trait_ref,
                           self_type,
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index e65ecc19ea1..b3f30dd4581 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -1111,7 +1111,7 @@ impl<'a, 'b> Folder for MacroExpander<'a, 'b> {
 
     fn fold_item(&mut self, item: P<ast::Item>) -> SmallVector<P<ast::Item>> {
         let prev_type = self.current_impl_type.clone();
-        if let ast::Item_::ItemImpl(_, _, _, ref ty, _) = item.node {
+        if let ast::Item_::ItemImpl(_, _, _, _, ref ty, _) = item.node {
             self.current_impl_type = Some(ty.clone());
         }
 
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index f75873ac1c0..29f8ff9e812 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -291,7 +291,7 @@ impl<'a, 'v> Visitor<'v> for PostExpansionVisitor<'a> {
                 }
             }
 
-            ast::ItemImpl(_, _, _, _, ref items) => {
+            ast::ItemImpl(_, _, _, _, _, ref items) => {
                 if attr::contains_name(i.attrs[],
                                        "unsafe_destructor") {
                     self.gate_feature("unsafe_destructor",
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index 3d3068f6868..35b2e5dbc53 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -1014,7 +1014,7 @@ pub fn noop_fold_item_underscore<T: Folder>(i: Item_, folder: &mut T) -> Item_ {
             let struct_def = folder.fold_struct_def(struct_def);
             ItemStruct(struct_def, folder.fold_generics(generics))
         }
-        ItemImpl(unsafety, generics, ifce, ty, impl_items) => {
+        ItemImpl(unsafety, polarity, generics, ifce, ty, impl_items) => {
             let mut new_impl_items = Vec::new();
             for impl_item in impl_items.iter() {
                 match *impl_item {
@@ -1037,6 +1037,7 @@ pub fn noop_fold_item_underscore<T: Folder>(i: Item_, folder: &mut T) -> Item_ {
                 }
             };
             ItemImpl(unsafety,
+                     polarity,
                      folder.fold_generics(generics),
                      ifce,
                      folder.fold_ty(ty),
@@ -1166,7 +1167,7 @@ pub fn noop_fold_item_simple<T: Folder>(Item {id, ident, attrs, node, vis, span}
     let node = folder.fold_item_underscore(node);
     let ident = match node {
         // The node may have changed, recompute the "pretty" impl name.
-        ItemImpl(_, _, ref maybe_trait, ref ty, _) => {
+        ItemImpl(_, _, _, ref maybe_trait, ref ty, _) => {
             ast_util::impl_pretty_name(maybe_trait, &**ty)
         }
         _ => ident
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index c0444363d4e..b4223a989ba 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -4802,6 +4802,13 @@ impl<'a> Parser<'a> {
         // allow this to be parsed as a trait.
         let could_be_trait = self.token != token::OpenDelim(token::Paren);
 
+        let neg_span = self.span;
+        let polarity = if self.eat(&token::Not) {
+            ast::ImplPolarity::Negative
+        } else {
+            ast::ImplPolarity::Positive
+        };
+
         // Parse the trait.
         let mut ty = self.parse_ty_sum();
 
@@ -4824,6 +4831,14 @@ impl<'a> Parser<'a> {
             ty = self.parse_ty_sum();
             opt_trait_ref
         } else {
+            match polarity {
+                ast::ImplPolarity::Negative => {
+                    // This is a negated type implementation
+                    // `impl !MyType {}`, which is not allowed.
+                    self.span_err(neg_span, "inherent implementation can't be negated");
+                },
+                _ => {}
+            }
             None
         };
 
@@ -4833,7 +4848,7 @@ impl<'a> Parser<'a> {
         let ident = ast_util::impl_pretty_name(&opt_trait, &*ty);
 
         (ident,
-         ItemImpl(unsafety, generics, opt_trait, ty, impl_items),
+         ItemImpl(unsafety, polarity, generics, opt_trait, ty, impl_items),
          Some(attrs))
     }
 
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index 9702c79719c..61b7aa408a8 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -917,6 +917,7 @@ impl<'a> State<'a> {
             }
 
             ast::ItemImpl(unsafety,
+                          polarity,
                           ref generics,
                           ref opt_trait,
                           ref ty,
@@ -931,6 +932,13 @@ impl<'a> State<'a> {
                     try!(space(&mut self.s));
                 }
 
+                match polarity {
+                    ast::ImplPolarity::Negative => {
+                        try!(word(&mut self.s, "!"));
+                    },
+                    _ => {}
+                }
+
                 match opt_trait {
                     &Some(ref t) => {
                         try!(self.print_trait_ref(t));
diff --git a/src/libsyntax/visit.rs b/src/libsyntax/visit.rs
index ec6b2cfa5c3..054a288a69e 100644
--- a/src/libsyntax/visit.rs
+++ b/src/libsyntax/visit.rs
@@ -297,7 +297,7 @@ pub fn walk_item<'v, V: Visitor<'v>>(visitor: &mut V, item: &'v Item) {
             visitor.visit_generics(type_parameters);
             walk_enum_def(visitor, enum_definition, type_parameters)
         }
-        ItemImpl(_,
+        ItemImpl(_, _,
                  ref type_parameters,
                  ref trait_reference,
                  ref typ,
diff --git a/src/test/compile-fail/syntax-trait-polarity.rs b/src/test/compile-fail/syntax-trait-polarity.rs
new file mode 100644
index 00000000000..dc01fbaefbd
--- /dev/null
+++ b/src/test/compile-fail/syntax-trait-polarity.rs
@@ -0,0 +1,31 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::kinds::Send;
+
+struct TestType;
+
+impl !TestType {}
+//~^ ERROR inherent implementation can't be negated
+
+trait TestTrait {}
+
+unsafe impl !Send for TestType {}
+impl !TestTrait for TestType {}
+
+struct TestType2<T>;
+
+impl<T> !TestType2<T> {}
+//~^ ERROR inherent implementation can't be negated
+
+unsafe impl<T> !Send for TestType2<T> {}
+impl<T> !TestTrait for TestType2<T> {}
+
+fn main() {}
diff --git a/src/test/pretty/trait-polarity.rs b/src/test/pretty/trait-polarity.rs
new file mode 100644
index 00000000000..dbc4c263571
--- /dev/null
+++ b/src/test/pretty/trait-polarity.rs
@@ -0,0 +1,21 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// pp-exact
+
+trait UnsafeTrait {
+    fn foo(&self);
+}
+
+impl !UnsafeTrait for int {
+    fn foo(&self) { }
+}
+
+pub fn main() { }
diff --git a/src/test/run-pass/syntax-trait-polarity.rs b/src/test/run-pass/syntax-trait-polarity.rs
new file mode 100644
index 00000000000..263fc4c0231
--- /dev/null
+++ b/src/test/run-pass/syntax-trait-polarity.rs
@@ -0,0 +1,29 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::kinds::Send;
+
+struct TestType;
+
+impl TestType {}
+
+trait TestTrait {}
+
+unsafe impl !Send for TestType {}
+impl !TestTrait for TestType {}
+
+struct TestType2<T>;
+
+impl<T> TestType2<T> {}
+
+unsafe impl<T> !Send for TestType2<T> {}
+impl<T> !TestTrait for TestType2<T> {}
+
+fn main() {}