rustc: Implement custom derive (macros 1.1)

This commit is an implementation of [RFC 1681] which adds support to the
compiler for first-class user-define custom `#[derive]` modes with a far more
stable API than plugins have today.

[RFC 1681]: https://github.com/rust-lang/rfcs/blob/master/text/1681-macros-1.1.md

The main features added by this commit are:

* A new `rustc-macro` crate-type. This crate type represents one which will
  provide custom `derive` implementations and perhaps eventually flower into the
  implementation of macros 2.0 as well.

* A new `rustc_macro` crate in the standard distribution. This crate will
  provide the runtime interface between macro crates and the compiler. The API
  here is particularly conservative right now but has quite a bit of room to
  expand into any manner of APIs required by macro authors.

* The ability to load new derive modes through the `#[macro_use]` annotations on
  other crates.

All support added here is gated behind the `rustc_macro` feature gate, both for
the library support (the `rustc_macro` crate) as well as the language features.

There are a few minor differences from the implementation outlined in the RFC,
such as the `rustc_macro` crate being available as a dylib and all symbols are
`dlsym`'d directly instead of having a shim compiled. These should only affect
the implementation, however, not the public interface.

This commit also ended up touching a lot of code related to `#[derive]`, making
a few notable changes:

* Recognized derive attributes are no longer desugared to `derive_Foo`. Wasn't
  sure how to keep this behavior and *not* expose it to custom derive.

* Derive attributes no longer have access to unstable features by default, they
  have to opt in on a granular level.

* The `derive(Copy,Clone)` optimization is now done through another "obscure
  attribute" which is just intended to ferry along in the compiler that such an
  optimization is possible. The `derive(PartialEq,Eq)` optimization was also
  updated to do something similar.

---

One part of this PR which needs to be improved before stabilizing are the errors
and exact interfaces here. The error messages are relatively poor quality and
there are surprising spects of this such as `#[derive(PartialEq, Eq, MyTrait)]`
not working by default. The custom attributes added by the compiler end up
becoming unstable again when going through a custom impl.

Hopefully though this is enough to start allowing experimentation on crates.io!

syntax-[breaking-change]

6 files changed, 565 insertions, 133 deletions

diff --git a/src/libsyntax_ext/Cargo.toml b/src/libsyntax_ext/Cargo.toml
index 040c6c8ebff..6910e6400d4 100644
--- a/src/libsyntax_ext/Cargo.toml
+++ b/src/libsyntax_ext/Cargo.toml
@@ -11,6 +11,7 @@ crate-type = ["dylib"]
 [dependencies]
 fmt_macros = { path = "../libfmt_macros" }
 log = { path = "../liblog" }
+rustc_errors = { path = "../librustc_errors" }
+rustc_macro = { path = "../librustc_macro" }
 syntax = { path = "../libsyntax" }
 syntax_pos = { path = "../libsyntax_pos" }
-rustc_errors = { path = "../librustc_errors" }
\ No newline at end of file
diff --git a/src/libsyntax_ext/deriving/clone.rs b/src/libsyntax_ext/deriving/clone.rs
index f1a3a1f41b1..c7afaaf4796 100644
--- a/src/libsyntax_ext/deriving/clone.rs
+++ b/src/libsyntax_ext/deriving/clone.rs
@@ -49,7 +49,7 @@ pub fn expand_deriving_clone(cx: &mut ExtCtxt,
                 ItemKind::Struct(_, Generics { ref ty_params, .. }) |
                 ItemKind::Enum(_, Generics { ref ty_params, .. })
                     if ty_params.is_empty() &&
-                       attr::contains_name(&annitem.attrs, "derive_Copy") => {
+                       attr::contains_name(&annitem.attrs, "rustc_copy_clone_marker") => {
 
                     bounds = vec![Literal(path_std!(cx, core::marker::Copy))];
                     unify_fieldless_variants = true;
@@ -110,12 +110,12 @@ fn cs_clone(name: &str,
         Mode::Shallow => cx.std_path(&["clone", "assert_receiver_is_clone"]),
         Mode::Deep => cx.std_path(&["clone", "Clone", "clone"]),
     };
-    let subcall = |field: &FieldInfo| {
+    let subcall = |cx: &mut ExtCtxt, field: &FieldInfo| {
         let args = vec![cx.expr_addr_of(field.span, field.self_.clone())];
 
         let span = if mode == Mode::Shallow {
             // set the expn ID so we can call the unstable method
-            Span { expn_id: cx.backtrace(), ..trait_span }
+            super::allow_unstable(cx, field.span, "derive(Clone)")
         } else {
             field.span
         };
@@ -147,8 +147,10 @@ fn cs_clone(name: &str,
 
     match mode {
         Mode::Shallow => {
-            let mut stmts: Vec<_> =
-                all_fields.iter().map(subcall).map(|e| cx.stmt_expr(e)).collect();
+            let mut stmts = all_fields.iter().map(|f| {
+                let call = subcall(cx, f);
+                cx.stmt_expr(call)
+            }).collect::<Vec<_>>();
             stmts.push(cx.stmt_expr(cx.expr_deref(trait_span, cx.expr_self(trait_span))));
             cx.expr_block(cx.block(trait_span, stmts))
         }
@@ -166,14 +168,15 @@ fn cs_clone(name: &str,
                                                          name))
                                 }
                             };
-                            cx.field_imm(field.span, ident, subcall(field))
+                            let call = subcall(cx, field);
+                            cx.field_imm(field.span, ident, call)
                         })
                         .collect::<Vec<_>>();
 
                     cx.expr_struct(trait_span, ctor_path, fields)
                 }
                 VariantData::Tuple(..) => {
-                    let subcalls = all_fields.iter().map(subcall).collect();
+                    let subcalls = all_fields.iter().map(|f| subcall(cx, f)).collect();
                     let path = cx.expr_path(ctor_path);
                     cx.expr_call(trait_span, path, subcalls)
                 }
diff --git a/src/libsyntax_ext/deriving/custom.rs b/src/libsyntax_ext/deriving/custom.rs
new file mode 100644
index 00000000000..1f9c24a0dcd
--- /dev/null
+++ b/src/libsyntax_ext/deriving/custom.rs
@@ -0,0 +1,97 @@
+// Copyright 2016 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::panic;
+
+use rustc_macro::{TokenStream, __internal};
+use syntax::ast::{self, ItemKind};
+use syntax::codemap::Span;
+use syntax::ext::base::*;
+use syntax::fold::{self, Folder};
+use errors::FatalError;
+
+pub struct CustomDerive {
+    inner: fn(TokenStream) -> TokenStream,
+}
+
+impl CustomDerive {
+    pub fn new(inner: fn(TokenStream) -> TokenStream) -> CustomDerive {
+        CustomDerive { inner: inner }
+    }
+}
+
+impl MultiItemModifier for CustomDerive {
+    fn expand(&self,
+              ecx: &mut ExtCtxt,
+              span: Span,
+              _meta_item: &ast::MetaItem,
+              item: Annotatable)
+              -> Vec<Annotatable> {
+        let item = match item {
+            Annotatable::Item(item) => item,
+            Annotatable::ImplItem(_) |
+            Annotatable::TraitItem(_) => {
+                ecx.span_err(span, "custom derive attributes may only be \
+                                    applied to struct/enum items");
+                return Vec::new()
+            }
+        };
+        match item.node {
+            ItemKind::Struct(..) |
+            ItemKind::Enum(..) => {}
+            _ => {
+                ecx.span_err(span, "custom derive attributes may only be \
+                                    applied to struct/enum items");
+                return Vec::new()
+            }
+        }
+
+        let input = __internal::new_token_stream(item);
+        let res = __internal::set_parse_sess(&ecx.parse_sess, || {
+            let inner = self.inner;
+            panic::catch_unwind(panic::AssertUnwindSafe(|| inner(input)))
+        });
+        let item = match res {
+            Ok(stream) => __internal::token_stream_items(stream),
+            Err(e) => {
+                let msg = "custom derive attribute panicked";
+                let mut err = ecx.struct_span_fatal(span, msg);
+                if let Some(s) = e.downcast_ref::<String>() {
+                    err.help(&format!("message: {}", s));
+                }
+                if let Some(s) = e.downcast_ref::<&'static str>() {
+                    err.help(&format!("message: {}", s));
+                }
+
+                err.emit();
+                panic!(FatalError);
+            }
+        };
+
+        // Right now we have no knowledge of spans at all in custom derive
+        // macros, everything is just parsed as a string. Reassign all spans to
+        // the #[derive] attribute for better errors here.
+        item.into_iter().flat_map(|item| {
+            ChangeSpan { span: span }.fold_item(item)
+        }).map(Annotatable::Item).collect()
+    }
+}
+
+struct ChangeSpan { span: Span }
+
+impl Folder for ChangeSpan {
+    fn new_span(&mut self, _sp: Span) -> Span {
+        self.span
+    }
+
+    fn fold_mac(&mut self, mac: ast::Mac) -> ast::Mac {
+        fold::noop_fold_mac(mac, self)
+    }
+}
diff --git a/src/libsyntax_ext/deriving/mod.rs b/src/libsyntax_ext/deriving/mod.rs
index 81085122e87..5582166c12e 100644
--- a/src/libsyntax_ext/deriving/mod.rs
+++ b/src/libsyntax_ext/deriving/mod.rs
@@ -12,7 +12,7 @@
 
 use syntax::ast::{self, MetaItem};
 use syntax::ext::base::{Annotatable, ExtCtxt, SyntaxEnv};
-use syntax::ext::base::{MultiDecorator, MultiItemDecorator, MultiModifier};
+use syntax::ext::base::MultiModifier;
 use syntax::ext::build::AstBuilder;
 use syntax::feature_gate;
 use syntax::codemap;
@@ -61,6 +61,7 @@ pub mod decodable;
 pub mod hash;
 pub mod debug;
 pub mod default;
+pub mod custom;
 
 #[path="cmp/partial_eq.rs"]
 pub mod partial_eq;
@@ -74,156 +75,201 @@ pub mod ord;
 
 pub mod generic;
 
+fn allow_unstable(cx: &mut ExtCtxt, span: Span, attr_name: &str) -> Span {
+    Span {
+        expn_id: cx.codemap().record_expansion(codemap::ExpnInfo {
+            call_site: span,
+            callee: codemap::NameAndSpan {
+                format: codemap::MacroAttribute(intern(attr_name)),
+                span: Some(span),
+                allow_internal_unstable: true,
+            },
+        }),
+        ..span
+    }
+}
+
 fn expand_derive(cx: &mut ExtCtxt,
                  span: Span,
                  mitem: &MetaItem,
                  annotatable: Annotatable)
-                 -> Annotatable {
+                 -> Vec<Annotatable> {
     debug!("expand_derive: span = {:?}", span);
     debug!("expand_derive: mitem = {:?}", mitem);
     debug!("expand_derive: annotatable input  = {:?}", annotatable);
-    let annot = annotatable.map_item_or(|item| {
-        item.map(|mut item| {
-            if mitem.value_str().is_some() {
-                cx.span_err(mitem.span, "unexpected value in `derive`");
-            }
+    let mut item = match annotatable {
+        Annotatable::Item(item) => item,
+        other => {
+            cx.span_err(span, "`derive` can only be applied to items");
+            return vec![other]
+        }
+    };
 
-            let traits = mitem.meta_item_list().unwrap_or(&[]);
-            if traits.is_empty() {
-                cx.span_warn(mitem.span, "empty trait list in `derive`");
-            }
+    if mitem.value_str().is_some() {
+        cx.span_err(mitem.span, "unexpected value in `derive`");
+    }
 
-            let mut found_partial_eq = false;
-            let mut eq_span = None;
-
-            for titem in traits.iter().rev() {
-                let tname = if let Some(word) = titem.word() {
-                    word.name()
-                } else {
-                    cx.span_err(titem.span, "malformed `derive` entry");
-                    continue;
-                };
-
-                if !(is_builtin_trait(&tname) || cx.ecfg.enable_custom_derive()) {
-                    feature_gate::emit_feature_err(&cx.parse_sess.span_diagnostic,
-                                                   "custom_derive",
-                                                   titem.span,
-                                                   feature_gate::GateIssue::Language,
-                                                   feature_gate::EXPLAIN_CUSTOM_DERIVE);
-                    continue;
-                }
+    let traits = mitem.meta_item_list().unwrap_or(&[]);
+    if traits.is_empty() {
+        cx.span_warn(mitem.span, "empty trait list in `derive`");
+    }
 
-                let span = Span {
-                    expn_id: cx.codemap().record_expansion(codemap::ExpnInfo {
-                        call_site: titem.span,
-                        callee: codemap::NameAndSpan {
-                            format: codemap::MacroAttribute(intern(&format!("derive({})", tname))),
-                            span: Some(titem.span),
-                            allow_internal_unstable: true,
-                        },
-                    }),
-                    ..titem.span
-                };
-
-                if &tname[..] == "Eq" {
-                    eq_span = Some(span);
-                } else if &tname[..] == "PartialEq" {
-                    found_partial_eq = true;
-                }
+    // RFC #1445. `#[derive(PartialEq, Eq)]` adds a (trusted)
+    // `#[structural_match]` attribute.
+    if traits.iter().filter_map(|t| t.name()).any(|t| t == "PartialEq") &&
+       traits.iter().filter_map(|t| t.name()).any(|t| t == "Eq") {
+        let structural_match = intern_and_get_ident("structural_match");
+        let span = allow_unstable(cx, span, "derive(PartialEq, Eq)");
+        let meta = cx.meta_word(span, structural_match);
+        item = item.map(|mut i| {
+            i.attrs.push(cx.attribute(span, meta));
+            i
+        });
+    }
 
-                // #[derive(Foo, Bar)] expands to #[derive_Foo] #[derive_Bar]
-                item.attrs.push(cx.attribute(span,
-                               cx.meta_word(titem.span,
-                                            intern_and_get_ident(&format!("derive_{}", tname)))));
-            }
+    // RFC #1521. `Clone` can assume that `Copy` types' clone implementation is
+    // the same as the copy implementation.
+    //
+    // Add a marker attribute here picked up during #[derive(Clone)]
+    if traits.iter().filter_map(|t| t.name()).any(|t| t == "Clone") &&
+       traits.iter().filter_map(|t| t.name()).any(|t| t == "Copy") {
+        let marker = intern_and_get_ident("rustc_copy_clone_marker");
+        let span = allow_unstable(cx, span, "derive(Copy, Clone)");
+        let meta = cx.meta_word(span, marker);
+        item = item.map(|mut i| {
+            i.attrs.push(cx.attribute(span, meta));
+            i
+        });
+    }
 
-            // RFC #1445. `#[derive(PartialEq, Eq)]` adds a (trusted)
-            // `#[structural_match]` attribute.
-            if let Some(eq_span) = eq_span {
-                if found_partial_eq {
-                    let structural_match = intern_and_get_ident("structural_match");
-                    item.attrs.push(cx.attribute(eq_span, cx.meta_word(eq_span, structural_match)));
-                }
+    let mut other_items = Vec::new();
+
+    let mut iter = traits.iter();
+    while let Some(titem) = iter.next() {
+
+        let tword = match titem.word() {
+            Some(name) => name,
+            None => {
+                cx.span_err(titem.span, "malformed `derive` entry");
+                continue
             }
+        };
+        let tname = tword.name();
+
+        // If this is a built-in derive mode, then we expand it immediately
+        // here.
+        if is_builtin_trait(&tname) {
+            let name = intern_and_get_ident(&format!("derive({})", tname));
+            let mitem = cx.meta_word(titem.span, name);
+
+            let span = Span {
+                expn_id: cx.codemap().record_expansion(codemap::ExpnInfo {
+                    call_site: titem.span,
+                    callee: codemap::NameAndSpan {
+                        format: codemap::MacroAttribute(intern(&format!("derive({})", tname))),
+                        span: Some(titem.span),
+                        allow_internal_unstable: true,
+                    },
+                }),
+                ..titem.span
+            };
+
+            let my_item = Annotatable::Item(item);
+            expand_builtin(&tname, cx, span, &mitem, &my_item, &mut |a| {
+                other_items.push(a);
+            });
+            item = my_item.expect_item();
+
+        // Otherwise if this is a `rustc_macro`-style derive mode, we process it
+        // here. The logic here is to:
+        //
+        // 1. Collect the remaining `#[derive]` annotations into a list. If
+        //    there are any left, attach a `#[derive]` attribute to the item
+        //    that we're currently expanding with the remaining derive modes.
+        // 2. Manufacture a `#[derive(Foo)]` attribute to pass to the expander.
+        // 3. Expand the current item we're expanding, getting back a list of
+        //    items that replace it.
+        // 4. Extend the returned list with the current list of items we've
+        //    collected so far.
+        // 5. Return everything!
+        //
+        // If custom derive extensions end up threading through the `#[derive]`
+        // attribute, we'll get called again later on to continue expanding
+        // those modes.
+        } else if let Some(ext) = cx.derive_modes.remove(&tname) {
+            let remaining_derives = iter.cloned().collect::<Vec<_>>();
+            if remaining_derives.len() > 0 {
+                let list = cx.meta_list(titem.span,
+                                        intern_and_get_ident("derive"),
+                                        remaining_derives);
+                let attr = cx.attribute(titem.span, list);
+                item = item.map(|mut i| {
+                    i.attrs.push(attr);
+                    i
+                });
+            }
+            let titem = cx.meta_list_item_word(titem.span, tname.clone());
+            let mitem = cx.meta_list(titem.span,
+                                     intern_and_get_ident("derive"),
+                                     vec![titem]);
+            let item = Annotatable::Item(item);
+            let mut items = ext.expand(cx, mitem.span, &mitem, item);
+            items.extend(other_items);
+            cx.derive_modes.insert(tname.clone(), ext);
+            return items
+
+        // If we've gotten this far then it means that we're in the territory of
+        // the old custom derive mechanism. If the feature isn't enabled, we
+        // issue an error, otherwise manufacture the `derive_Foo` attribute.
+        } else if !cx.ecfg.enable_custom_derive() {
+            feature_gate::emit_feature_err(&cx.parse_sess.span_diagnostic,
+                                           "custom_derive",
+                                           titem.span,
+                                           feature_gate::GateIssue::Language,
+                                           feature_gate::EXPLAIN_CUSTOM_DERIVE);
+        } else {
+            let name = intern_and_get_ident(&format!("derive_{}", tname));
+            let mitem = cx.meta_word(titem.span, name);
+            item = item.map(|mut i| {
+                i.attrs.push(cx.attribute(mitem.span, mitem));
+                i
+            });
+        }
+    }
 
-            item
-        })
-    },
-                                        |a| {
-                                            cx.span_err(span,
-                                                        "`derive` can only be applied to items");
-                                            a
-                                        });
-    debug!("expand_derive: annotatable output = {:?}", annot);
-    annot
+    other_items.insert(0, Annotatable::Item(item));
+    return other_items
 }
 
 macro_rules! derive_traits {
     ($( $name:expr => $func:path, )+) => {
         pub fn register_all(env: &mut SyntaxEnv) {
-            // Define the #[derive_*] extensions.
-            $({
-                struct DeriveExtension;
-
-                impl MultiItemDecorator for DeriveExtension {
-                    fn expand(&self,
-                              ecx: &mut ExtCtxt,
-                              sp: Span,
-                              mitem: &MetaItem,
-                              annotatable: &Annotatable,
-                              push: &mut FnMut(Annotatable)) {
-                        if !ecx.parse_sess.codemap().span_allows_unstable(sp)
-                            && !ecx.ecfg.features.unwrap().custom_derive {
-                            // FIXME:
-                            // https://github.com/rust-lang/rust/pull/32671#issuecomment-206245303
-                            // This is just to avoid breakage with syntex.
-                            // Remove that to spawn an error instead.
-                            let cm = ecx.parse_sess.codemap();
-                            let parent = cm.with_expn_info(ecx.backtrace(),
-                                                           |info| info.unwrap().call_site.expn_id);
-                            cm.with_expn_info(parent, |info| {
-                                if info.is_some() {
-                                    let mut w = ecx.parse_sess.span_diagnostic.struct_span_warn(
-                                        sp, feature_gate::EXPLAIN_DERIVE_UNDERSCORE,
-                                    );
-                                    if option_env!("CFG_DISABLE_UNSTABLE_FEATURES").is_none() {
-                                        w.help(
-                                            &format!("add #![feature(custom_derive)] to \
-                                                      the crate attributes to enable")
-                                        );
-                                    }
-                                    w.emit();
-                                } else {
-                                    feature_gate::emit_feature_err(
-                                        &ecx.parse_sess.span_diagnostic,
-                                        "custom_derive", sp, feature_gate::GateIssue::Language,
-                                        feature_gate::EXPLAIN_DERIVE_UNDERSCORE
-                                    );
-
-                                    return;
-                                }
-                            })
-                        }
-
-                        warn_if_deprecated(ecx, sp, $name);
-                        $func(ecx, sp, mitem, annotatable, push);
-                    }
-                }
-
-                env.insert(intern(concat!("derive_", $name)),
-                           MultiDecorator(Box::new(DeriveExtension)));
-            })+
-
-            env.insert(intern("derive"),
-                       MultiModifier(Box::new(expand_derive)));
+            env.insert(intern("derive"), MultiModifier(Box::new(expand_derive)));
         }
 
-        fn is_builtin_trait(name: &str) -> bool {
+        pub fn is_builtin_trait(name: &str) -> bool {
             match name {
                 $( $name )|+ => true,
                 _ => false,
             }
         }
+
+        fn expand_builtin(name: &str,
+                          ecx: &mut ExtCtxt,
+                          span: Span,
+                          mitem: &MetaItem,
+                          item: &Annotatable,
+                          push: &mut FnMut(Annotatable)) {
+            match name {
+                $(
+                    $name => {
+                        warn_if_deprecated(ecx, span, $name);
+                        $func(ecx, span, mitem, item, push);
+                    }
+                )*
+                _ => panic!("not a builtin derive mode: {}", name),
+            }
+        }
     }
 }
 
diff --git a/src/libsyntax_ext/lib.rs b/src/libsyntax_ext/lib.rs
index 3aa62339b47..4bae9ec5a1a 100644
--- a/src/libsyntax_ext/lib.rs
+++ b/src/libsyntax_ext/lib.rs
@@ -19,6 +19,8 @@
        html_root_url = "https://doc.rust-lang.org/nightly/")]
 #![cfg_attr(not(stage0), deny(warnings))]
 
+#![feature(rustc_macro_lib)]
+#![feature(rustc_macro_internals)]
 #![feature(rustc_private)]
 #![feature(staged_api)]
 
@@ -28,6 +30,7 @@ extern crate log;
 #[macro_use]
 extern crate syntax;
 extern crate syntax_pos;
+extern crate rustc_macro;
 extern crate rustc_errors as errors;
 
 use syntax::ext::base::{MacroExpanderFn, NormalTT};
@@ -44,6 +47,8 @@ mod format;
 mod log_syntax;
 mod trace_macros;
 
+pub mod rustc_macro_registrar;
+
 // for custom_derive
 pub mod deriving;
 
diff --git a/src/libsyntax_ext/rustc_macro_registrar.rs b/src/libsyntax_ext/rustc_macro_registrar.rs
new file mode 100644
index 00000000000..7693e2416f4
--- /dev/null
+++ b/src/libsyntax_ext/rustc_macro_registrar.rs
@@ -0,0 +1,280 @@
+// Copyright 2016 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::mem;
+
+use errors;
+use syntax::ast::{self, Ident, NodeId};
+use syntax::codemap::{ExpnInfo, NameAndSpan, MacroAttribute};
+use syntax::ext::base::{ExtCtxt, DummyMacroLoader};
+use syntax::ext::build::AstBuilder;
+use syntax::ext::expand::ExpansionConfig;
+use syntax::parse::ParseSess;
+use syntax::parse::token::{self, InternedString};
+use syntax::feature_gate::Features;
+use syntax::ptr::P;
+use syntax_pos::{Span, DUMMY_SP};
+use syntax::visit::{self, Visitor};
+
+use deriving;
+
+struct CustomDerive {
+    trait_name: InternedString,
+    function_name: Ident,
+    span: Span,
+}
+
+struct CollectCustomDerives<'a> {
+    derives: Vec<CustomDerive>,
+    in_root: bool,
+    handler: &'a errors::Handler,
+    is_rustc_macro_crate: bool,
+}
+
+pub fn modify(sess: &ParseSess,
+              mut krate: ast::Crate,
+              is_rustc_macro_crate: bool,
+              num_crate_types: usize,
+              handler: &errors::Handler,
+              features: &Features) -> ast::Crate {
+    let mut loader = DummyMacroLoader;
+    let mut cx = ExtCtxt::new(sess,
+                              Vec::new(),
+                              ExpansionConfig::default("rustc_macro".to_string()),
+                              &mut loader);
+
+    let mut collect = CollectCustomDerives {
+        derives: Vec::new(),
+        in_root: true,
+        handler: handler,
+        is_rustc_macro_crate: is_rustc_macro_crate,
+    };
+    visit::walk_crate(&mut collect, &krate);
+
+    if !is_rustc_macro_crate {
+        return krate
+    } else if !features.rustc_macro {
+        let mut err = handler.struct_err("the `rustc-macro` crate type is \
+                                          experimental");
+        err.help("add #![feature(rustc_macro)] to the crate attributes to \
+                  enable");
+        err.emit();
+    }
+
+    if num_crate_types > 1 {
+        handler.err("cannot mix `rustc-macro` crate type with others");
+    }
+
+    krate.module.items.push(mk_registrar(&mut cx, &collect.derives));
+
+    if krate.exported_macros.len() > 0 {
+        handler.err("cannot export macro_rules! macros from a `rustc-macro` \
+                     crate type currently");
+    }
+
+    return krate
+}
+
+impl<'a> CollectCustomDerives<'a> {
+    fn check_not_pub_in_root(&self, vis: &ast::Visibility, sp: Span) {
+        if self.is_rustc_macro_crate &&
+           self.in_root &&
+           *vis == ast::Visibility::Public {
+            self.handler.span_err(sp,
+                                  "`rustc-macro` crate types cannot \
+                                   export any items other than functions \
+                                   tagged with `#[rustc_macro_derive]` \
+                                   currently");
+        }
+    }
+}
+
+impl<'a> Visitor for CollectCustomDerives<'a> {
+    fn visit_item(&mut self, item: &ast::Item) {
+        // First up, make sure we're checking a bare function. If we're not then
+        // we're just not interested in this item.
+        //
+        // If we find one, try to locate a `#[rustc_macro_derive]` attribute on
+        // it.
+        match item.node {
+            ast::ItemKind::Fn(..) => {}
+            _ => {
+                self.check_not_pub_in_root(&item.vis, item.span);
+                return visit::walk_item(self, item)
+            }
+        }
+
+        let mut attrs = item.attrs.iter()
+                            .filter(|a| a.check_name("rustc_macro_derive"));
+        let attr = match attrs.next() {
+            Some(attr) => attr,
+            None => {
+                self.check_not_pub_in_root(&item.vis, item.span);
+                return visit::walk_item(self, item)
+            }
+        };
+
+        if let Some(a) = attrs.next() {
+            self.handler.span_err(a.span(), "multiple `#[rustc_macro_derive]` \
+                                             attributes found");
+        }
+
+        if !self.is_rustc_macro_crate {
+            self.handler.span_err(attr.span(),
+                                  "the `#[rustc_macro_derive]` attribute is \
+                                   only usable with crates of the `rustc-macro` \
+                                   crate type");
+        }
+
+        // Once we've located the `#[rustc_macro_derive]` attribute, verify
+        // that it's of the form `#[rustc_macro_derive(Foo)]`
+        let list = match attr.meta_item_list() {
+            Some(list) => list,
+            None => {
+                self.handler.span_err(attr.span(),
+                                      "attribute must be of form: \
+                                       #[rustc_macro_derive(TraitName)]");
+                return
+            }
+        };
+        if list.len() != 1 {
+            self.handler.span_err(attr.span(),
+                                  "attribute must only have one argument");
+            return
+        }
+        let attr = &list[0];
+        let trait_name = match attr.name() {
+            Some(name) => name,
+            _ => {
+                self.handler.span_err(attr.span(), "not a meta item");
+                return
+            }
+        };
+        if !attr.is_word() {
+            self.handler.span_err(attr.span(), "must only be one word");
+        }
+
+        if deriving::is_builtin_trait(&trait_name) {
+            self.handler.span_err(attr.span(),
+                                  "cannot override a built-in #[derive] mode");
+        }
+
+        if self.derives.iter().any(|d| d.trait_name == trait_name) {
+            self.handler.span_err(attr.span(),
+                                  "derive mode defined twice in this crate");
+        }
+
+        if self.in_root {
+            self.derives.push(CustomDerive {
+                span: item.span,
+                trait_name: trait_name,
+                function_name: item.ident,
+            });
+        } else {
+            let msg = "functions tagged with `#[rustc_macro_derive]` must \
+                       currently reside in the root of the crate";
+            self.handler.span_err(item.span, msg);
+        }
+
+        visit::walk_item(self, item);
+    }
+
+    fn visit_mod(&mut self, m: &ast::Mod, _s: Span, id: NodeId) {
+        let mut prev_in_root = self.in_root;
+        if id != ast::CRATE_NODE_ID {
+            prev_in_root = mem::replace(&mut self.in_root, false);
+        }
+        visit::walk_mod(self, m);
+        self.in_root = prev_in_root;
+    }
+
+    fn visit_mac(&mut self, mac: &ast::Mac) {
+        visit::walk_mac(self, mac)
+    }
+}
+
+// Creates a new module which looks like:
+//
+//      mod $gensym {
+//          extern crate rustc_macro;
+//
+//          use rustc_macro::__internal::Registry;
+//
+//          #[plugin_registrar]
+//          fn registrar(registrar: &mut Registry) {
+//              registrar.register_custom_derive($name_trait1, ::$name1);
+//              registrar.register_custom_derive($name_trait2, ::$name2);
+//              // ...
+//          }
+//      }
+fn mk_registrar(cx: &mut ExtCtxt,
+                custom_derives: &[CustomDerive]) -> P<ast::Item> {
+    let eid = cx.codemap().record_expansion(ExpnInfo {
+        call_site: DUMMY_SP,
+        callee: NameAndSpan {
+            format: MacroAttribute(token::intern("rustc_macro")),
+            span: None,
+            allow_internal_unstable: true,
+        }
+    });
+    let span = Span { expn_id: eid, ..DUMMY_SP };
+
+    let rustc_macro = token::str_to_ident("rustc_macro");
+    let krate = cx.item(span,
+                        rustc_macro,
+                        Vec::new(),
+                        ast::ItemKind::ExternCrate(None));
+
+    let __internal = token::str_to_ident("__internal");
+    let registry = token::str_to_ident("Registry");
+    let registrar = token::str_to_ident("registrar");
+    let register_custom_derive = token::str_to_ident("register_custom_derive");
+    let stmts = custom_derives.iter().map(|cd| {
+        let path = cx.path_global(cd.span, vec![cd.function_name]);
+        let trait_name = cx.expr_str(cd.span, cd.trait_name.clone());
+        (path, trait_name)
+    }).map(|(path, trait_name)| {
+        let registrar = cx.expr_ident(span, registrar);
+        let ufcs_path = cx.path(span, vec![rustc_macro, __internal, registry,
+                                           register_custom_derive]);
+        cx.expr_call(span,
+                     cx.expr_path(ufcs_path),
+                     vec![registrar, trait_name, cx.expr_path(path)])
+    }).map(|expr| {
+        cx.stmt_expr(expr)
+    }).collect::<Vec<_>>();
+
+    let path = cx.path(span, vec![rustc_macro, __internal, registry]);
+    let registrar_path = cx.ty_path(path);
+    let arg_ty = cx.ty_rptr(span, registrar_path, None, ast::Mutability::Mutable);
+    let func = cx.item_fn(span,
+                          registrar,
+                          vec![cx.arg(span, registrar, arg_ty)],
+                          cx.ty(span, ast::TyKind::Tup(Vec::new())),
+                          cx.block(span, stmts));
+
+    let derive_registrar = token::intern_and_get_ident("rustc_derive_registrar");
+    let derive_registrar = cx.meta_word(span, derive_registrar);
+    let derive_registrar = cx.attribute(span, derive_registrar);
+    let func = func.map(|mut i| {
+        i.attrs.push(derive_registrar);
+        i.vis = ast::Visibility::Public;
+        i
+    });
+    let module = cx.item_mod(span,
+                             span,
+                             ast::Ident::with_empty_ctxt(token::gensym("registrar")),
+                             Vec::new(),
+                             vec![krate, func]);
+    module.map(|mut i| {
+        i.vis = ast::Visibility::Public;
+        i
+    })
+}