rustc: Implement typechecking for simple monomorphic derivable traits on monomorphic types. r=brson

23 files changed, 422 insertions, 123 deletions

diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index a3d2fe96b5d..579699c9958 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -1508,7 +1508,7 @@ enum item_ {
     item_impl(~[ty_param],
               Option<@trait_ref>, /* (optional) trait this impl implements */
               @Ty, /* self */
-              ~[@method]),
+              Option<~[@method]>),
     item_mac(mac),
 }
 
diff --git a/src/libsyntax/ast_map.rs b/src/libsyntax/ast_map.rs
index 8555ceed2db..bcda838b248 100644
--- a/src/libsyntax/ast_map.rs
+++ b/src/libsyntax/ast_map.rs
@@ -202,11 +202,13 @@ fn map_item(i: @item, cx: ctx, v: vt) {
     let item_path = @/* FIXME (#2543) */ copy cx.path;
     cx.map.insert(i.id, node_item(i, item_path));
     match i.node {
-      item_impl(_, _, _, ms) => {
+      item_impl(_, _, _, ms_opt) => {
         let impl_did = ast_util::local_def(i.id);
-        for ms.each |m| {
-            map_method(impl_did, extend(cx, i.ident), *m,
-                       cx);
+        for ms_opt.each |ms| {
+            for ms.each |m| {
+                map_method(impl_did, extend(cx, i.ident), *m,
+                           cx);
+            }
         }
       }
       item_enum(enum_definition, _) => {
diff --git a/src/libsyntax/ext/auto_serialize.rs b/src/libsyntax/ext/auto_serialize.rs
index 47e61c26f38..707787e78b9 100644
--- a/src/libsyntax/ext/auto_serialize.rs
+++ b/src/libsyntax/ext/auto_serialize.rs
@@ -398,7 +398,7 @@ fn mk_impl(
         ident: ast::token::special_idents::clownshoes_extensions,
         attrs: ~[],
         id: cx.next_id(),
-        node: ast::item_impl(trait_tps, opt_trait, ty, ~[f(ty)]),
+        node: ast::item_impl(trait_tps, opt_trait, ty, Some(~[f(ty)])),
         vis: ast::public,
         span: span,
     }
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index 311928dd4e0..7eb7b2853e3 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -248,11 +248,13 @@ fn noop_fold_item_underscore(i: item_, fld: ast_fold) -> item_ {
             let struct_def = fold_struct_def(struct_def, fld);
               item_class(struct_def, /* FIXME (#2543) */ copy typms)
           }
-          item_impl(tps, ifce, ty, methods) => {
+          item_impl(tps, ifce, ty, ref methods_opt) => {
               item_impl(fold_ty_params(tps, fld),
                         ifce.map(|p| fold_trait_ref(*p, fld)),
                         fld.fold_ty(ty),
-                        vec::map(methods, |x| fld.fold_method(*x)))
+                        option::map(methods_opt,
+                                    |methods| vec::map(
+                                        *methods, |x| fld.fold_method(*x))))
           }
           item_trait(tps, traits, methods) => {
             item_trait(fold_ty_params(tps, fld),
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 925da063ca6..672f86b7a10 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -2603,13 +2603,20 @@ impl Parser {
             None
         };
 
-        let mut meths = ~[];
-        self.expect(token::LBRACE);
-        while !self.eat(token::RBRACE) {
-            let vis = self.parse_visibility();
-            meths.push(self.parse_method(vis));
+        let meths_opt;
+        if self.eat(token::SEMI) {
+            meths_opt = None;
+        } else {
+            let mut meths = ~[];
+            self.expect(token::LBRACE);
+            while !self.eat(token::RBRACE) {
+                let vis = self.parse_visibility();
+                meths.push(self.parse_method(vis));
+            }
+            meths_opt = Some(move meths);
         }
-        (ident, item_impl(tps, opt_trait, ty, meths), None)
+
+        (ident, item_impl(tps, opt_trait, ty, meths_opt), None)
     }
 
     // Instantiates ident <i> with references to <typarams> as arguments.
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index 33915c8c0c9..d68b28c6836 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -522,7 +522,7 @@ fn print_item(s: ps, &&item: @ast::item) {
           print_struct(s, struct_def, tps, item.ident, item.span);
       }
 
-      ast::item_impl(tps, opt_trait, ty, methods) => {
+      ast::item_impl(tps, opt_trait, ty, methods_opt) => {
         head(s, visibility_qualified(item.vis, ~"impl"));
         if tps.is_not_empty() {
             print_type_params(s, tps);
@@ -539,11 +539,18 @@ fn print_item(s: ps, &&item: @ast::item) {
         };
         space(s.s);
 
-        bopen(s);
-        for methods.each |meth| {
-           print_method(s, *meth);
+        match methods_opt {
+            None => {
+                word(s.s, ~";");
+            }
+            Some(methods) => {
+                bopen(s);
+                for methods.each |meth| {
+                   print_method(s, *meth);
+                }
+                bclose(s, item.span);
+            }
         }
-        bclose(s, item.span);
       }
       ast::item_trait(tps, traits, methods) => {
         head(s, visibility_qualified(item.vis, ~"trait"));
diff --git a/src/libsyntax/visit.rs b/src/libsyntax/visit.rs
index b45af2d4ae8..7035400f92d 100644
--- a/src/libsyntax/visit.rs
+++ b/src/libsyntax/visit.rs
@@ -142,14 +142,16 @@ fn visit_item<E>(i: @item, e: E, v: vt<E>) {
         v.visit_ty_params(tps, e, v);
         visit_enum_def(enum_definition, tps, e, v);
       }
-      item_impl(tps, traits, ty, methods) => {
+      item_impl(tps, traits, ty, methods_opt) => {
         v.visit_ty_params(tps, e, v);
         for traits.each |p| {
             visit_path(p.path, e, v);
         }
         v.visit_ty(ty, e, v);
-        for methods.each |m| {
-            visit_method_helper(*m, e, v)
+        for methods_opt.each |methods| {
+            for methods.each |m| {
+                visit_method_helper(*m, e, v)
+            }
         }
       }
       item_class(struct_def, tps) => {
diff --git a/src/rustc/metadata/encoder.rs b/src/rustc/metadata/encoder.rs
index a1d85a63ee1..259d3aa6221 100644
--- a/src/rustc/metadata/encoder.rs
+++ b/src/rustc/metadata/encoder.rs
@@ -712,7 +712,7 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::Serializer,
         encode_index(ebml_w, bkts, write_int);
         ebml_w.end_tag();
       }
-      item_impl(tps, opt_trait, ty, methods) => {
+      item_impl(tps, opt_trait, ty, methods_opt) => {
         add_to_index();
         ebml_w.start_tag(tag_items_data_item);
         encode_def_id(ebml_w, local_def(item.id));
@@ -729,10 +729,13 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::Serializer,
             }
             _ => {}
         }
-        for methods.each |m| {
-            ebml_w.start_tag(tag_item_impl_method);
-            ebml_w.writer.write(str::to_bytes(def_to_str(local_def(m.id))));
-            ebml_w.end_tag();
+        for methods_opt.each |methods| {
+            for methods.each |m| {
+                ebml_w.start_tag(tag_item_impl_method);
+                let method_def_id = local_def(m.id);
+                ebml_w.writer.write(str::to_bytes(def_to_str(method_def_id)));
+                ebml_w.end_tag();
+            }
         }
         do opt_trait.iter() |associated_trait| {
            encode_trait_ref(ebml_w, ecx, *associated_trait)
@@ -742,11 +745,13 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::Serializer,
 
         let impl_path = vec::append_one(path,
                                         ast_map::path_name(item.ident));
-        for methods.each |m| {
-            index.push({val: m.id, pos: ebml_w.writer.tell()});
-            encode_info_for_method(ecx, ebml_w, impl_path,
-                                   should_inline(m.attrs), item.id, *m,
-                                   vec::append(tps, m.tps));
+        for methods_opt.each |methods| {
+            for methods.each |m| {
+                index.push({val: m.id, pos: ebml_w.writer.tell()});
+                encode_info_for_method(ecx, ebml_w, impl_path,
+                                       should_inline(m.attrs), item.id, *m,
+                                       vec::append(tps, m.tps));
+            }
         }
       }
       item_trait(tps, traits, ms) => {
diff --git a/src/rustc/middle/resolve.rs b/src/rustc/middle/resolve.rs
index 3d2cd6a621c..73720648798 100644
--- a/src/rustc/middle/resolve.rs
+++ b/src/rustc/middle/resolve.rs
@@ -1192,7 +1192,7 @@ impl Resolver {
                 visit_item(item, new_parent, visitor);
             }
 
-            item_impl(_, trait_ref_opt, ty, methods) => {
+            item_impl(_, trait_ref_opt, ty, methods_opt) => {
                 // If this implements an anonymous trait and it has static
                 // methods, then add all the static methods within to a new
                 // module, if the type was defined within this module.
@@ -1203,10 +1203,12 @@ impl Resolver {
 
                 // Bail out early if there are no static methods.
                 let mut has_static_methods = false;
-                for methods.each |method| {
-                    match method.self_ty.node {
-                        sty_static => has_static_methods = true,
-                        _ => {}
+                for methods_opt.each |methods| {
+                    for methods.each |method| {
+                        match method.self_ty.node {
+                            sty_static => has_static_methods = true,
+                            _ => {}
+                        }
                     }
                 }
 
@@ -1233,22 +1235,26 @@ impl Resolver {
                             name_bindings.get_module());
 
                         // For each static method...
-                        for methods.each |method| {
-                            match method.self_ty.node {
-                                sty_static => {
-                                    // Add the static method to the module.
-                                    let ident = method.ident;
-                                    let (method_name_bindings, _) =
-                                        self.add_child(ident,
-                                                       new_parent,
-                                                       ForbidDuplicateValues,
-                                                       method.span);
-                                    let def = def_fn(local_def(method.id),
-                                                     method.purity);
-                                    method_name_bindings.define_value(
-                                        Public, def, method.span);
+                        for methods_opt.each |methods| {
+                            for methods.each |method| {
+                                match method.self_ty.node {
+                                    sty_static => {
+                                        // Add the static method to the
+                                        // module.
+                                        let ident = method.ident;
+                                        let (method_name_bindings, _) =
+                                            self.add_child(
+                                                ident,
+                                                new_parent,
+                                                ForbidDuplicateValues,
+                                                method.span);
+                                        let def = def_fn(local_def(method.id),
+                                                         method.purity);
+                                        method_name_bindings.define_value(
+                                            Public, def, method.span);
+                                    }
+                                    _ => {}
                                 }
-                                _ => {}
                             }
                         }
                     }
@@ -3446,12 +3452,14 @@ impl Resolver {
             }
 
             item_impl(type_parameters, implemented_traits, self_type,
-                      methods) => {
-
-                self.resolve_implementation(item.id, item.span,
+                      methods_opt) => {
+                self.resolve_implementation(item.id,
+                                            item.span,
                                             type_parameters,
                                             implemented_traits,
-                                            self_type, methods, visitor);
+                                            self_type,
+                                            methods_opt,
+                                            visitor);
             }
 
             item_trait(type_parameters, traits, methods) => {
@@ -3876,7 +3884,7 @@ impl Resolver {
                               type_parameters: ~[ty_param],
                               opt_trait_reference: Option<@trait_ref>,
                               self_type: @Ty,
-                              methods: ~[@method],
+                              opt_methods: Option<~[@method]>,
                               visitor: ResolveVisitor) {
         // If applicable, create a rib for the type parameters.
         let outer_type_parameter_count = type_parameters.len();
@@ -3915,27 +3923,33 @@ impl Resolver {
             // Resolve the self type.
             self.resolve_type(self_type, visitor);
 
-            for methods.each |method| {
-                // We also need a new scope for the method-specific
-                // type parameters.
-                self.resolve_method(MethodRibKind(id, Provided(method.id)),
-                                    *method,
-                                    outer_type_parameter_count,
-                                    visitor);
+            for opt_methods.each |methods| {
+                for methods.each |method| {
+                    // We also need a new scope for the method-specific
+                    // type parameters.
+                    self.resolve_method(MethodRibKind(
+                        id,
+                        Provided(method.id)),
+                        *method,
+                        outer_type_parameter_count,
+                        visitor);
 /*
-                let borrowed_type_parameters = &method.tps;
-                self.resolve_function(MethodRibKind(id, Provided(method.id)),
-                                      Some(@method.decl),
-                                      HasTypeParameters
-                                        (borrowed_type_parameters,
-                                         method.id,
-                                         outer_type_parameter_count,
-                                         NormalRibKind),
-                                      method.body,
-                                      HasSelfBinding(method.self_id),
-                                      NoCaptureClause,
-                                      visitor);
+                    let borrowed_type_parameters = &method.tps;
+                    self.resolve_function(MethodRibKind(
+                                          id,
+                                          Provided(method.id)),
+                                          Some(@method.decl),
+                                          HasTypeParameters
+                                            (borrowed_type_parameters,
+                                             method.id,
+                                             outer_type_parameter_count,
+                                             NormalRibKind),
+                                          method.body,
+                                          HasSelfBinding(method.self_id),
+                                          NoCaptureClause,
+                                          visitor);
 */
+                }
             }
 
             // Restore the original trait references.
diff --git a/src/rustc/middle/trans/base.rs b/src/rustc/middle/trans/base.rs
index bf66ccbfeb5..61d4e6379a2 100644
--- a/src/rustc/middle/trans/base.rs
+++ b/src/rustc/middle/trans/base.rs
@@ -1798,8 +1798,17 @@ fn trans_item(ccx: @crate_ctxt, item: ast::item) {
             }
         }
       }
-      ast::item_impl(tps, _, _, ms) => {
-        meth::trans_impl(ccx, *path, item.ident, ms, tps, None, item.id);
+      ast::item_impl(tps, _, _, ms_opt) => {
+        match ms_opt {
+            None => {
+                deriving::trans_deriving_impl(ccx, *path, item.ident, tps,
+                                              None, item.id);
+            }
+            Some(ms) => {
+                meth::trans_impl(ccx, *path, item.ident, ms, tps, None,
+                                 item.id);
+            }
+        }
       }
       ast::item_mod(m) => {
         trans_mod(ccx, m);
diff --git a/src/rustc/middle/trans/deriving.rs b/src/rustc/middle/trans/deriving.rs
new file mode 100644
index 00000000000..5ef412888b9
--- /dev/null
+++ b/src/rustc/middle/trans/deriving.rs
@@ -0,0 +1,21 @@
+// Translation of automatically-derived trait implementations. This handles
+// enums and structs only; other types cannot be automatically derived.
+
+use middle::trans::base::get_insn_ctxt;
+use middle::trans::common::crate_ctxt;
+use syntax::ast::{ident, node_id, ty_param};
+use syntax::ast_map::path;
+
+/// The main "translation" pass for automatically-derived impls. Generates
+/// code for monomorphic methods only. Other methods will be generated when
+/// they are invoked with specific type parameters; see
+/// `trans::base::lval_static_fn()` or `trans::base::monomorphic_fn()`.
+pub fn trans_deriving_impl(ccx: @crate_ctxt, _path: path, _name: ident,
+                           tps: ~[ty_param], _self_ty: Option<ty::t>,
+                           _id: node_id) {
+    let _icx = ccx.insn_ctxt("deriving::trans_deriving_impl");
+    if tps.len() > 0 { return; }
+
+    // XXX: Unimplemented.
+}
+
diff --git a/src/rustc/middle/trans/meth.rs b/src/rustc/middle/trans/meth.rs
index 20dba35b231..e7c134fe546 100644
--- a/src/rustc/middle/trans/meth.rs
+++ b/src/rustc/middle/trans/meth.rs
@@ -306,7 +306,8 @@ fn method_with_name(ccx: @crate_ctxt, impl_id: ast::def_id,
                     name: ast::ident) -> ast::def_id {
     if impl_id.crate == ast::local_crate {
         match ccx.tcx.items.get(impl_id.node) {
-          ast_map::node_item(@{node: ast::item_impl(_, _, _, ms), _}, _) => {
+          ast_map::node_item(@{node: ast::item_impl(_, _, _, Some(ms)), _},
+                             _) => {
             method_from_methods(ms, name)
           }
           ast_map::node_item(@{node:
diff --git a/src/rustc/middle/trans/reachable.rs b/src/rustc/middle/trans/reachable.rs
index a99ef96b254..87cb4716cd2 100644
--- a/src/rustc/middle/trans/reachable.rs
+++ b/src/rustc/middle/trans/reachable.rs
@@ -90,12 +90,14 @@ fn traverse_public_item(cx: ctx, item: @item) {
             traverse_inline_body(cx, blk);
         }
       }
-      item_impl(tps, _, _, ms) => {
-        for vec::each(ms) |m| {
-            if tps.len() > 0u || m.tps.len() > 0u ||
-               attr::find_inline_attr(m.attrs) != attr::ia_none {
-                cx.rmap.insert(m.id, ());
-                traverse_inline_body(cx, m.body);
+      item_impl(tps, _, _, ms_opt) => {
+        for ms_opt.each |ms| {
+            for vec::each(*ms) |m| {
+                if tps.len() > 0u || m.tps.len() > 0u ||
+                   attr::find_inline_attr(m.attrs) != attr::ia_none {
+                    cx.rmap.insert(m.id, ());
+                    traverse_inline_body(cx, m.body);
+                }
             }
         }
       }
diff --git a/src/rustc/middle/ty.rs b/src/rustc/middle/ty.rs
index 8c4c4232b00..03e75957a92 100644
--- a/src/rustc/middle/ty.rs
+++ b/src/rustc/middle/ty.rs
@@ -374,7 +374,9 @@ type ctxt =
       lang_items: middle::lang_items::LanguageItems,
       legacy_boxed_traits: HashMap<node_id, ()>,
       provided_method_sources: HashMap<ast::def_id, ProvidedMethodSource>,
-      supertraits: HashMap<ast::def_id, @~[InstantiatedTraitRef]>};
+      supertraits: HashMap<ast::def_id, @~[InstantiatedTraitRef]>,
+      deriving_struct_methods: HashMap<ast::def_id,
+                                       @~[typeck::method_origin]>};
 
 enum tbox_flag {
     has_params = 1,
@@ -901,7 +903,8 @@ fn mk_ctxt(s: session::Session,
       lang_items: move lang_items,
       legacy_boxed_traits: HashMap(),
       provided_method_sources: HashMap(),
-      supertraits: HashMap()}
+      supertraits: HashMap(),
+      deriving_struct_methods: HashMap()}
 }
 
 
diff --git a/src/rustc/middle/typeck.rs b/src/rustc/middle/typeck.rs
index afb13cf52ab..2e55dd702f0 100644
--- a/src/rustc/middle/typeck.rs
+++ b/src/rustc/middle/typeck.rs
@@ -334,6 +334,7 @@ fn check_crate(tcx: ty::ctxt,
                             tcx: tcx});
     collect::collect_item_types(ccx, crate);
     coherence::check_coherence(ccx, crate);
+    deriving::check_deriving(ccx, crate);
 
     check::check_item_types(ccx, crate);
     check_for_main_fn(ccx);
diff --git a/src/rustc/middle/typeck/check.rs b/src/rustc/middle/typeck/check.rs
index 8d65cb9fdac..0641dc3bd7c 100644
--- a/src/rustc/middle/typeck/check.rs
+++ b/src/rustc/middle/typeck/check.rs
@@ -489,13 +489,15 @@ fn check_item(ccx: @crate_ctxt, it: @ast::item) {
       ast::item_fn(decl, _, _, body) => {
         check_bare_fn(ccx, decl, body, it.id, None);
       }
-      ast::item_impl(_, _, ty, ms) => {
+      ast::item_impl(_, _, ty, ms_opt) => {
         let rp = ccx.tcx.region_paramd_items.find(it.id);
         debug!("item_impl %s with id %d rp %?",
                ccx.tcx.sess.str_of(it.ident), it.id, rp);
         let self_ty = ccx.to_ty(rscope::type_rscope(rp), ty);
-        for ms.each |m| {
-            check_method(ccx, *m, self_ty, local_def(it.id));
+        for ms_opt.each |ms| {
+            for ms.each |m| {
+                check_method(ccx, *m, self_ty, local_def(it.id));
+            }
         }
       }
       ast::item_trait(_, _, trait_methods) => {
diff --git a/src/rustc/middle/typeck/coherence.rs b/src/rustc/middle/typeck/coherence.rs
index 189e7377d9c..b6b7a4c5f34 100644
--- a/src/rustc/middle/typeck/coherence.rs
+++ b/src/rustc/middle/typeck/coherence.rs
@@ -591,6 +591,32 @@ impl CoherenceChecker {
         return trait_id;
     }
 
+    fn add_automatically_derived_methods_from_trait(
+        all_methods: &mut ~[@MethodInfo], trait_did: def_id, self_ty: ty::t) {
+        let tcx = self.crate_context.tcx;
+        for (*ty::trait_methods(tcx, trait_did)).each |method| {
+            // Generate a def ID for each node.
+            let new_def_id = local_def(tcx.sess.next_node_id());
+            all_methods.push(@{
+                did: new_def_id,
+                n_tps: method.tps.len(),
+                ident: method.ident,
+                self_type: method.self_ty
+            });
+
+            // Additionally, generate the type for the derived method and add
+            // it to the type cache.
+            //
+            // XXX: Handle generics correctly.
+            let substs = { self_r: None, self_ty: Some(self_ty), tps: ~[] };
+            tcx.tcache.insert(new_def_id, {
+                bounds: @~[],
+                region_param: None,
+                ty: ty::subst(tcx, &substs, ty::mk_fn(tcx, method.fty))
+            });
+        }
+    }
+
     // Converts an implementation in the AST to an Impl structure.
     fn create_impl_from_item(item: @item) -> @Impl {
         fn add_provided_methods(all_methods: &mut ~[@MethodInfo],
@@ -605,11 +631,29 @@ impl CoherenceChecker {
         }
 
         match item.node {
-            item_impl(_, trait_refs, _, ast_methods) => {
+            item_impl(_, trait_refs, _, ast_methods_opt) => {
                 let mut methods = ~[];
 
-                for ast_methods.each |ast_method| {
-                    methods.push(method_to_MethodInfo(*ast_method));
+                match ast_methods_opt {
+                    Some(ast_methods) => {
+                        for ast_methods.each |ast_method| {
+                            methods.push(method_to_MethodInfo(*ast_method));
+                        }
+                    }
+                    None => {
+                        // This is a "deriving" impl. For each trait, collect
+                        // all the "required" methods and add them to the
+                        // Impl structure.
+                        let tcx = self.crate_context.tcx;
+                        let self_ty =
+                            ty::lookup_item_type(tcx, local_def(item.id));
+                        for trait_refs.each |trait_ref| {
+                            let trait_did =
+                                self.trait_ref_to_trait_def_id(*trait_ref);
+                            self.add_automatically_derived_methods_from_trait(
+                                &mut methods, trait_did, self_ty.ty);
+                        }
+                    }
                 }
 
                 // For each trait that the impl implements, see what
@@ -617,7 +661,6 @@ impl CoherenceChecker {
                 // if a method of that name is not inherent to the
                 // impl, use the provided definition in the trait.
                 for trait_refs.each |trait_ref| {
-
                     let trait_did =
                         self.trait_ref_to_trait_def_id(*trait_ref);
 
diff --git a/src/rustc/middle/typeck/collect.rs b/src/rustc/middle/typeck/collect.rs
index 7e1696549e1..262a8121ec5 100644
--- a/src/rustc/middle/typeck/collect.rs
+++ b/src/rustc/middle/typeck/collect.rs
@@ -463,7 +463,7 @@ fn convert(ccx: @crate_ctxt, it: @ast::item) {
         get_enum_variant_types(ccx, tpt.ty, enum_definition.variants,
                                ty_params, rp);
       }
-      ast::item_impl(tps, trait_ref, selfty, ms) => {
+      ast::item_impl(tps, trait_ref, selfty, ms_opt) => {
         let i_bounds = ty_param_bounds(ccx, tps);
         let selfty = ccx.to_ty(type_rscope(rp), selfty);
         write_ty_to_tcx(tcx, it.id, selfty);
@@ -472,9 +472,11 @@ fn convert(ccx: @crate_ctxt, it: @ast::item) {
                            region_param: rp,
                            ty: selfty});
 
-        let cms = convert_methods(ccx, ms, rp, i_bounds);
-        for trait_ref.each |t| {
-            check_methods_against_trait(ccx, tps, rp, selfty, *t, cms);
+        for ms_opt.each |ms| {
+            let cms = convert_methods(ccx, *ms, rp, i_bounds);
+            for trait_ref.each |t| {
+                check_methods_against_trait(ccx, tps, rp, selfty, *t, cms);
+            }
         }
       }
       ast::item_trait(tps, supertraits, trait_methods) => {
diff --git a/src/rustc/middle/typeck/deriving.rs b/src/rustc/middle/typeck/deriving.rs
new file mode 100644
index 00000000000..9a5d3ba027c
--- /dev/null
+++ b/src/rustc/middle/typeck/deriving.rs
@@ -0,0 +1,158 @@
+// Deriving phase
+//
+// The purpose of the deriving phase of typechecking is to ensure that, for
+// each automatically derived implementation of an automatically-derivable
+// trait (for example, Eq), all the subcomponents of the type in question
+// also implement the trait. This phase runs after coherence.
+
+use syntax::ast::crate;
+use syntax::ast::{def_id, ident};
+use syntax::ast::item_impl;
+use syntax::ast::node_id;
+use syntax::ast::self_ty_;
+use syntax::ast::trait_ref;
+use syntax::ast_util::def_id_of_def;
+use syntax::codemap::span;
+use syntax::print::pprust;
+use syntax::visit::{default_simple_visitor, mk_simple_visitor, visit_crate};
+use middle::resolve::{Impl, MethodInfo};
+use middle::ty;
+use middle::ty::{substs, ty_class, ty_enum, ty_param_bounds_and_ty};
+use /*middle::typeck::*/check::method;
+use /*middle::typeck::*/infer::infer_ctxt;
+
+struct DerivingChecker {
+    crate_context: @crate_ctxt,
+    inference_context: infer_ctxt
+}
+
+fn DerivingChecker_new(crate_context: @crate_ctxt) -> DerivingChecker {
+    DerivingChecker {
+        crate_context: crate_context,
+        inference_context: infer::new_infer_ctxt(crate_context.tcx)
+    }
+}
+
+impl DerivingChecker {
+    /// Matches one substructure type against an implementation.
+    fn match_impl_method(impl_info: @Impl,
+                         substructure_type: ty::t,
+                         method_info: @MethodInfo) -> bool {
+        // XXX: Generics and regions are not handled properly.
+        let tcx = self.crate_context.tcx;
+        let impl_self_ty = ty::lookup_item_type(tcx, impl_info.did).ty;
+        let transformed_type = method::transform_self_type_for_method(
+            tcx, None, impl_self_ty, method_info.self_type);
+        return infer::can_mk_subty(self.inference_context,
+                                   substructure_type,
+                                   transformed_type).is_ok();
+    }
+
+    fn check_deriving_for_substructure_type(substructure_type: ty::t,
+                                            trait_ref: @trait_ref,
+                                            impl_span: span) ->
+                                            Option<def_id> {
+        let tcx = self.crate_context.tcx;
+        let sess = tcx.sess;
+        let coherence_info = self.crate_context.coherence_info;
+        let trait_id = def_id_of_def(tcx.def_map.get(trait_ref.ref_id));
+        match coherence_info.extension_methods.find(trait_id) {
+            None => {
+                sess.span_bug(impl_span, ~"no extension method info found \
+                                           for this trait");
+            }
+            Some(impls) => {
+                // Try to unify each of these impls with the substructure
+                // type.
+                for impls.each |impl_info| {
+                    for impl_info.methods.each |method_info| {
+                        if self.match_impl_method(*impl_info,
+                                                  substructure_type,
+                                                  *method_info) {
+                            return Some(method_info.did);
+                        }
+                    }
+                }
+            }
+        }
+        return None;
+    }
+
+    fn check_deriving_for_struct(struct_def_id: def_id,
+                                 struct_substs: &substs,
+                                 trait_ref: @trait_ref,
+                                 impl_id: node_id,
+                                 impl_span: span) {
+        let tcx = self.crate_context.tcx;
+        let field_info = dvec::DVec();
+        for ty::lookup_class_fields(tcx, struct_def_id).each |field| {
+            let field_type = ty::lookup_field_type(
+                tcx, struct_def_id, field.id, struct_substs);
+            match self.check_deriving_for_substructure_type(field_type,
+                                                            trait_ref,
+                                                            impl_span) {
+                Some(method_target_def_id) => {
+                    field_info.push(method_static(method_target_def_id));
+                }
+                None => {
+                    let trait_str = pprust::path_to_str(
+                        trait_ref.path, tcx.sess.parse_sess.interner);
+                    tcx.sess.span_err(impl_span,
+                                      fmt!("cannot automatically derive an \
+                                            implementation for `%s`: field \
+                                            `%s` does not implement the \
+                                            trait `%s`",
+                                           trait_str,
+                                           tcx.sess.str_of(field.ident),
+                                           trait_str));
+                }
+            }
+        }
+
+        let field_info = @dvec::unwrap(move field_info);
+        tcx.deriving_struct_methods.insert(local_def(impl_id), field_info);
+    }
+
+    fn check_deriving(crate: @crate) {
+        let tcx = self.crate_context.tcx;
+        visit_crate(*crate, (), mk_simple_visitor(@{
+            visit_item: |item| {
+                match item.node {
+                    item_impl(_, Some(trait_ref), _, None) => {
+                        // XXX: This does not handle generic impls.
+                        let superty = ty::lookup_item_type(
+                            tcx, local_def(item.id)).ty;
+                        match ty::get(superty).sty {
+                            ty_enum(_def_id, _substs) => {
+                                // XXX: Handle enums.
+                            }
+                            ty_class(def_id, ref substs) => {
+                                self.check_deriving_for_struct(
+                                    def_id,
+                                    substs,
+                                    trait_ref,
+                                    item.id,
+                                    item.span);
+                            }
+                            _ => {
+                                tcx.sess.span_err(item.span,
+                                                  ~"only enums and structs \
+                                                    may have implementations \
+                                                    automatically derived \
+                                                    for them");
+                            }
+                        }
+                    }
+                    _ => {}
+                }
+            },
+            ..*default_simple_visitor()
+        }));
+    }
+}
+
+pub fn check_deriving(crate_context: @crate_ctxt, crate: @crate) {
+    let deriving_checker = @DerivingChecker_new(crate_context);
+    deriving_checker.check_deriving(crate);
+}
+
diff --git a/src/rustc/rustc.rc b/src/rustc/rustc.rc
index 5d1b217e623..10fd378ed17 100644
--- a/src/rustc/rustc.rc
+++ b/src/rustc/rustc.rc
@@ -89,6 +89,7 @@ mod middle {
         #[legacy_exports]
         mod reachable;
         mod machine;
+        mod deriving;
     }
     #[legacy_exports]
     mod ty;
@@ -146,6 +147,7 @@ mod middle {
         mod collect;
         #[legacy_exports]
         mod coherence;
+        mod deriving;
     }
     #[legacy_exports]
     mod check_loop;
diff --git a/src/rustdoc/attr_pass.rs b/src/rustdoc/attr_pass.rs
index 0748f603580..92ab33e3614 100644
--- a/src/rustdoc/attr_pass.rs
+++ b/src/rustdoc/attr_pass.rs
@@ -221,11 +221,17 @@ fn merge_method_attrs(
             })
           }
           ast_map::node_item(@{
-            node: ast::item_impl(_, _, _, methods), _
+            node: ast::item_impl(_, _, _, methods_opt), _
           }, _) => {
-            vec::map(methods, |method| {
-                (to_str(method.ident), attr_parser::parse_desc(method.attrs))
-            })
+            match methods_opt {
+                None => ~[],
+                Some(methods) => {
+                    vec::map(methods, |method| {
+                        (to_str(method.ident),
+                         attr_parser::parse_desc(method.attrs))
+                    })
+                }
+            }
           }
           _ => fail ~"unexpected item"
         }
diff --git a/src/rustdoc/extract.rs b/src/rustdoc/extract.rs
index 7b34a327bee..8ac74f4663c 100644
--- a/src/rustdoc/extract.rs
+++ b/src/rustdoc/extract.rs
@@ -258,20 +258,25 @@ fn should_extract_trait_methods() {
 
 fn impldoc_from_impl(
     itemdoc: doc::ItemDoc,
-    methods: ~[@ast::method]
+    methods_opt: Option<~[@ast::method]>
 ) -> doc::ImplDoc {
     {
         item: itemdoc,
         trait_types: ~[],
         self_ty: None,
-        methods: do vec::map(methods) |method| {
-            {
-                name: to_str(method.ident),
-                brief: None,
-                desc: None,
-                sections: ~[],
-                sig: None,
-                implementation: doc::Provided,
+        methods: match methods_opt {
+            None => ~[],
+            Some(methods) => {
+                do vec::map(methods) |method| {
+                    {
+                        name: to_str(method.ident),
+                        brief: None,
+                        desc: None,
+                        sections: ~[],
+                        sig: None,
+                        implementation: doc::Provided,
+                    }
+                }
             }
         }
     }
diff --git a/src/rustdoc/tystr_pass.rs b/src/rustdoc/tystr_pass.rs
index 08ad3ea3ecf..fb47e58f769 100644
--- a/src/rustdoc/tystr_pass.rs
+++ b/src/rustdoc/tystr_pass.rs
@@ -207,20 +207,25 @@ fn get_method_sig(
             }
           }
           ast_map::node_item(@{
-            node: ast::item_impl(_, _, _, methods), _
+            node: ast::item_impl(_, _, _, methods_opt), _
           }, _) => {
-            match vec::find(methods, |method| {
-                to_str(method.ident) == method_name
-            }) {
-                Some(method) => {
-                    Some(pprust::fun_to_str(
-                        method.decl,
-                        method.ident,
-                        method.tps,
-                        extract::interner()
-                    ))
+            match methods_opt {
+                None => fail ~"no methods in this impl",
+                Some(methods) => {
+                    match vec::find(methods, |method| {
+                        to_str(method.ident) == method_name
+                    }) {
+                        Some(method) => {
+                            Some(pprust::fun_to_str(
+                                method.decl,
+                                method.ident,
+                                method.tps,
+                                extract::interner()
+                            ))
+                        }
+                        None => fail ~"method not found"
+                    }
                 }
-                None => fail ~"method not found"
             }
           }
           _ => fail ~"get_method_sig: item ID not bound to trait or impl"