librustc: Implement the fully-expanded, UFCS form of explicit self.

This makes two changes to region inference: (1) it allows region
inference to relate early-bound regions; and (2) it allows regions to be
related before variance runs. The former is needed because there is no
relation between the two regions before region substitution happens,
while the latter is needed because type collection has to run before
variance. We assume that, before variance is inferred, that lifetimes
are invariant. This is a conservative overapproximation.

This relates to #13885. This does not remove `~self` from the language
yet, however.

[breaking-change]

25 files changed, 633 insertions, 157 deletions

diff --git a/src/librustc/metadata/csearch.rs b/src/librustc/metadata/csearch.rs
index 5ab8eeeb360..0adc8e915c6 100644
--- a/src/librustc/metadata/csearch.rs
+++ b/src/librustc/metadata/csearch.rs
@@ -132,7 +132,8 @@ pub fn get_method(tcx: &ty::ctxt, def: ast::DefId) -> ty::Method {
 
 pub fn get_method_name_and_explicit_self(cstore: &cstore::CStore,
                                          def: ast::DefId)
-                                     -> (ast::Ident, ast::ExplicitSelf_)
+                                         -> (ast::Ident,
+                                             ty::ExplicitSelfCategory)
 {
     let cdata = cstore.get_crate_data(def.krate);
     decoder::get_method_name_and_explicit_self(cstore.intr.clone(), &*cdata, def.node)
diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index cc41223688e..094e83d2a47 100644
--- a/src/librustc/metadata/decoder.rs
+++ b/src/librustc/metadata/decoder.rs
@@ -724,7 +724,7 @@ pub fn get_enum_variants(intr: Rc<IdentInterner>, cdata: Cmd, id: ast::NodeId,
     }).collect()
 }
 
-fn get_explicit_self(item: ebml::Doc) -> ast::ExplicitSelf_ {
+fn get_explicit_self(item: ebml::Doc) -> ty::ExplicitSelfCategory {
     fn get_mutability(ch: u8) -> ast::Mutability {
         match ch as char {
             'i' => ast::MutImmutable,
@@ -738,12 +738,15 @@ fn get_explicit_self(item: ebml::Doc) -> ast::ExplicitSelf_ {
 
     let explicit_self_kind = string.as_bytes()[0];
     match explicit_self_kind as char {
-        's' => ast::SelfStatic,
-        'v' => ast::SelfValue(special_idents::self_),
-        '~' => ast::SelfUniq(special_idents::self_),
+        's' => ty::StaticExplicitSelfCategory,
+        'v' => ty::ByValueExplicitSelfCategory,
+        '~' => ty::ByBoxExplicitSelfCategory,
         // FIXME(#4846) expl. region
-        '&' => ast::SelfRegion(None, get_mutability(string.as_bytes()[1]),
-                               special_idents::self_),
+        '&' => {
+            ty::ByReferenceExplicitSelfCategory(
+                ty::ReEmpty,
+                get_mutability(string.as_bytes()[1]))
+        }
         _ => fail!("unknown self type code: `{}`", explicit_self_kind as char)
     }
 }
@@ -761,11 +764,11 @@ pub fn get_impl_methods(cdata: Cmd, impl_id: ast::NodeId) -> Vec<ast::DefId> {
     methods
 }
 
-pub fn get_method_name_and_explicit_self(
-    intr: Rc<IdentInterner>,
-    cdata: Cmd,
-    id: ast::NodeId) -> (ast::Ident, ast::ExplicitSelf_)
-{
+pub fn get_method_name_and_explicit_self(intr: Rc<IdentInterner>,
+                                         cdata: Cmd,
+                                         id: ast::NodeId)
+                                         -> (ast::Ident,
+                                             ty::ExplicitSelfCategory) {
     let method_doc = lookup_item(id, cdata.data());
     let name = item_name(&*intr, method_doc);
     let explicit_self = get_explicit_self(method_doc);
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index 0a050850fe9..3c9f32dcd2f 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -402,7 +402,7 @@ fn encode_reexported_static_base_methods(ecx: &EncodeContext,
             for base_impl_did in implementations.borrow().iter() {
                 for &method_did in impl_methods.get(base_impl_did).iter() {
                     let m = ty::method(ecx.tcx, method_did);
-                    if m.explicit_self == ast::SelfStatic {
+                    if m.explicit_self == ty::StaticExplicitSelfCategory {
                         encode_reexported_static_method(ebml_w, exp, m.def_id, m.ident);
                     }
                 }
@@ -421,7 +421,7 @@ fn encode_reexported_static_trait_methods(ecx: &EncodeContext,
     match ecx.tcx.trait_methods_cache.borrow().find(&exp.def_id) {
         Some(methods) => {
             for m in methods.iter() {
-                if m.explicit_self == ast::SelfStatic {
+                if m.explicit_self == ty::StaticExplicitSelfCategory {
                     encode_reexported_static_method(ebml_w, exp, m.def_id, m.ident);
                 }
             }
@@ -623,15 +623,22 @@ fn encode_visibility(ebml_w: &mut Encoder, visibility: Visibility) {
     ebml_w.end_tag();
 }
 
-fn encode_explicit_self(ebml_w: &mut Encoder, explicit_self: ast::ExplicitSelf_) {
+fn encode_explicit_self(ebml_w: &mut Encoder,
+                        explicit_self: &ty::ExplicitSelfCategory) {
     ebml_w.start_tag(tag_item_trait_method_explicit_self);
 
     // Encode the base self type.
-    match explicit_self {
-        SelfStatic   => { ebml_w.writer.write(&[ 's' as u8 ]); }
-        SelfValue(_) => { ebml_w.writer.write(&[ 'v' as u8 ]); }
-        SelfUniq(_)  => { ebml_w.writer.write(&[ '~' as u8 ]); }
-        SelfRegion(_, m, _) => {
+    match *explicit_self {
+        ty::StaticExplicitSelfCategory => {
+            ebml_w.writer.write(&[ 's' as u8 ]);
+        }
+        ty::ByValueExplicitSelfCategory => {
+            ebml_w.writer.write(&[ 'v' as u8 ]);
+        }
+        ty::ByBoxExplicitSelfCategory => {
+            ebml_w.writer.write(&[ '~' as u8 ]);
+        }
+        ty::ByReferenceExplicitSelfCategory(_, m) => {
             // FIXME(#4846) encode custom lifetime
             ebml_w.writer.write(&['&' as u8]);
             encode_mutability(ebml_w, m);
@@ -748,10 +755,10 @@ fn encode_method_ty_fields(ecx: &EncodeContext,
                               tag_item_method_tps);
     encode_method_fty(ecx, ebml_w, &method_ty.fty);
     encode_visibility(ebml_w, method_ty.vis);
-    encode_explicit_self(ebml_w, method_ty.explicit_self);
+    encode_explicit_self(ebml_w, &method_ty.explicit_self);
     let fn_style = method_ty.fty.fn_style;
     match method_ty.explicit_self {
-        ast::SelfStatic => {
+        ty::StaticExplicitSelfCategory => {
             encode_family(ebml_w, fn_style_static_method_family(fn_style));
         }
         _ => encode_family(ebml_w, style_fn_family(fn_style))
@@ -1206,7 +1213,7 @@ fn encode_info_for_item(ecx: &EncodeContext,
             encode_path(ebml_w, path.clone().chain(Some(elem).move_iter()));
 
             match method_ty.explicit_self {
-                SelfStatic => {
+                ty::StaticExplicitSelfCategory => {
                     encode_family(ebml_w,
                                   fn_style_static_method_family(
                                       method_ty.fty.fn_style));
@@ -1233,7 +1240,7 @@ fn encode_info_for_item(ecx: &EncodeContext,
                     encode_attributes(ebml_w, m.attrs.as_slice());
                     // If this is a static method, we've already encoded
                     // this.
-                    if method_ty.explicit_self != SelfStatic {
+                    if method_ty.explicit_self != ty::StaticExplicitSelfCategory {
                         // FIXME: I feel like there is something funny going on.
                         let pty = ty::lookup_item_type(tcx, method_def_id);
                         encode_bounds_and_type(ebml_w, ecx, &pty);
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index df4d3b7efe4..822a43f2619 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -314,6 +314,16 @@ impl RegionMaps {
                     self.sub_free_region(sub_fr, super_fr)
                 }
 
+                (ty::ReEarlyBound(param_id_a, param_space_a, index_a, _),
+                 ty::ReEarlyBound(param_id_b, param_space_b, index_b, _)) => {
+                    // This case is used only to make sure that explicitly-
+                    // specified `Self` types match the real self type in
+                    // implementations.
+                    param_id_a == param_id_b &&
+                        param_space_a == param_space_b &&
+                        index_a == index_b
+                }
+
                 _ => {
                     false
                 }
diff --git a/src/librustc/middle/resolve.rs b/src/librustc/middle/resolve.rs
index 40237e7984f..f00d7c36f53 100644
--- a/src/librustc/middle/resolve.rs
+++ b/src/librustc/middle/resolve.rs
@@ -11,13 +11,14 @@
 #![allow(non_camel_case_types)]
 
 use driver::session::Session;
+use lint;
 use metadata::csearch;
 use metadata::decoder::{DefLike, DlDef, DlField, DlImpl};
 use middle::def::*;
 use middle::lang_items::LanguageItems;
 use middle::pat_util::pat_bindings;
 use middle::subst::{ParamSpace, FnSpace, TypeSpace};
-use lint;
+use middle::ty::{ExplicitSelfCategory, StaticExplicitSelfCategory};
 use util::nodemap::{NodeMap, DefIdSet, FnvHashMap};
 
 use syntax::ast::*;
@@ -287,6 +288,24 @@ enum ModulePrefixResult {
     PrefixFound(Rc<Module>, uint)
 }
 
+#[deriving(Clone, Eq, PartialEq)]
+enum MethodIsStaticFlag {
+    MethodIsNotStatic,
+    MethodIsStatic,
+}
+
+impl MethodIsStaticFlag {
+    fn from_explicit_self_category(explicit_self_category:
+                                   ExplicitSelfCategory)
+                                   -> MethodIsStaticFlag {
+        if explicit_self_category == StaticExplicitSelfCategory {
+            MethodIsStatic
+        } else {
+            MethodIsNotStatic
+        }
+    }
+}
+
 #[deriving(PartialEq)]
 enum NameSearchType {
     /// We're doing a name search in order to resolve a `use` directive.
@@ -805,7 +824,8 @@ struct Resolver<'a> {
 
     graph_root: NameBindings,
 
-    method_map: RefCell<FnvHashMap<(Name, DefId), ast::ExplicitSelf_>>,
+    method_map: RefCell<FnvHashMap<(Name, DefId), MethodIsStaticFlag>>,
+
     structs: FnvHashMap<DefId, Vec<Name>>,
 
     // The number of imports that are currently unresolved.
@@ -1361,17 +1381,19 @@ impl<'a> Resolver<'a> {
                     let ident = ty_m.ident;
 
                     // Add it as a name in the trait module.
-                    let def = match ty_m.explicit_self.node {
+                    let (def, static_flag) = match ty_m.explicit_self.node {
                         SelfStatic => {
                             // Static methods become `def_static_method`s.
-                            DefStaticMethod(local_def(ty_m.id),
+                            (DefStaticMethod(local_def(ty_m.id),
                                               FromTrait(local_def(item.id)),
-                                              ty_m.fn_style)
+                                              ty_m.fn_style),
+                             MethodIsStatic)
                         }
                         _ => {
                             // Non-static methods become `def_method`s.
-                            DefMethod(local_def(ty_m.id),
-                                       Some(local_def(item.id)))
+                            (DefMethod(local_def(ty_m.id),
+                                       Some(local_def(item.id))),
+                             MethodIsNotStatic)
                         }
                     };
 
@@ -1382,8 +1404,9 @@ impl<'a> Resolver<'a> {
                                        ty_m.span);
                     method_name_bindings.define_value(def, ty_m.span, true);
 
-                    self.method_map.borrow_mut().insert((ident.name, def_id),
-                                                        ty_m.explicit_self.node);
+                    self.method_map
+                        .borrow_mut()
+                        .insert((ident.name, def_id), static_flag);
                 }
 
                 name_bindings.define_type(DefTrait(def_id), sp, is_public);
@@ -1670,7 +1693,11 @@ impl<'a> Resolver<'a> {
                           trait method '{}'",
                          token::get_ident(method_name));
 
-                  self.method_map.borrow_mut().insert((method_name.name, def_id), explicit_self);
+                  self.method_map
+                      .borrow_mut()
+                      .insert((method_name.name, def_id),
+                              MethodIsStaticFlag::from_explicit_self_category(
+                                  explicit_self));
 
                   if is_exported {
                       self.external_exports.insert(method_def_id);
@@ -3678,6 +3705,13 @@ impl<'a> Resolver<'a> {
                                     this.resolve_type(&*argument.ty);
                                 }
 
+                                match ty_m.explicit_self.node {
+                                    SelfExplicit(ref typ, _) => {
+                                        this.resolve_type(*typ)
+                                    }
+                                    _ => {}
+                                }
+
                                 this.resolve_type(&*ty_m.decl.output);
                             });
                           }
@@ -4009,7 +4043,14 @@ impl<'a> Resolver<'a> {
                                                 method.id,
                                                 rib_kind);
 
-        self.resolve_function(rib_kind, Some(method.pe_fn_decl()), type_parameters,
+        match method.pe_explicit_self().node {
+            SelfExplicit(ref typ, _) => self.resolve_type(*typ),
+            _ => {}
+        }
+
+        self.resolve_function(rib_kind,
+                              Some(method.pe_fn_decl()),
+                              type_parameters,
                               method.pe_body());
     }
 
@@ -4765,7 +4806,7 @@ impl<'a> Resolver<'a> {
                 match containing_module.def_id.get() {
                     Some(def_id) => {
                         match self.method_map.borrow().find(&(ident.name, def_id)) {
-                            Some(x) if *x == SelfStatic => (),
+                            Some(&MethodIsStatic) => (),
                             None => (),
                             _ => {
                                 debug!("containing module was a trait or impl \
@@ -5037,7 +5078,7 @@ impl<'a> Resolver<'a> {
                 let path_str = self.path_idents_to_string(&trait_ref.path);
 
                 match method_map.find(&(name, did)) {
-                    Some(&SelfStatic) => return StaticTraitMethod(path_str),
+                    Some(&MethodIsStatic) => return StaticTraitMethod(path_str),
                     Some(_) => return TraitMethod,
                     None => {}
                 }
diff --git a/src/librustc/middle/trans/meth.rs b/src/librustc/middle/trans/meth.rs
index f9c5f82fb29..53f0645cb87 100644
--- a/src/librustc/middle/trans/meth.rs
+++ b/src/librustc/middle/trans/meth.rs
@@ -502,15 +502,12 @@ fn emit_vtable_methods(bcx: &Block,
                                                        ExprId(0),
                                                        substs.clone(),
                                                        vtables.clone());
-            match m.explicit_self {
-                ast::SelfValue(_) => {
-                    fn_ref = trans_unboxing_shim(bcx,
-                                                 fn_ref,
-                                                 &*m,
-                                                 m_id,
-                                                 substs.clone());
-                },
-                _ => {}
+            if m.explicit_self == ty::ByValueExplicitSelfCategory {
+                fn_ref = trans_unboxing_shim(bcx,
+                                             fn_ref,
+                                             &*m,
+                                             m_id,
+                                             substs.clone());
             }
             fn_ref
         }
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index dc69e3fd639..cfafe99090d 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -85,7 +85,7 @@ pub struct Method {
     pub ident: ast::Ident,
     pub generics: ty::Generics,
     pub fty: BareFnTy,
-    pub explicit_self: ast::ExplicitSelf_,
+    pub explicit_self: ExplicitSelfCategory,
     pub vis: ast::Visibility,
     pub def_id: ast::DefId,
     pub container: MethodContainer,
@@ -98,7 +98,7 @@ impl Method {
     pub fn new(ident: ast::Ident,
                generics: ty::Generics,
                fty: BareFnTy,
-               explicit_self: ast::ExplicitSelf_,
+               explicit_self: ExplicitSelfCategory,
                vis: ast::Visibility,
                def_id: ast::DefId,
                container: MethodContainer,
@@ -311,6 +311,9 @@ pub struct ctxt {
     /// (inferred) variance.
     pub item_variance_map: RefCell<DefIdMap<Rc<ItemVariances>>>,
 
+    /// True if the variance has been computed yet; false otherwise.
+    pub variance_computed: Cell<bool>,
+
     /// A mapping from the def ID of an enum or struct type to the def ID
     /// of the method that implements its destructor. If the type is not
     /// present in this map, it does not have a destructor. This map is
@@ -1055,6 +1058,7 @@ pub fn mk_ctxt(s: Session,
     ctxt {
         named_region_map: named_region_map,
         item_variance_map: RefCell::new(DefIdMap::new()),
+        variance_computed: Cell::new(false),
         interner: RefCell::new(FnvHashMap::new()),
         next_id: Cell::new(primitives::LAST_PRIMITIVE_ID),
         sess: s,
@@ -4767,3 +4771,13 @@ impl mc::Typer for ty::ctxt {
         self.upvar_borrow_map.borrow().get_copy(&upvar_id)
     }
 }
+
+/// The category of explicit self.
+#[deriving(Clone, Eq, PartialEq)]
+pub enum ExplicitSelfCategory {
+    StaticExplicitSelfCategory,
+    ByValueExplicitSelfCategory,
+    ByReferenceExplicitSelfCategory(Region, ast::Mutability),
+    ByBoxExplicitSelfCategory,
+}
+
diff --git a/src/librustc/middle/typeck/astconv.rs b/src/librustc/middle/typeck/astconv.rs
index 5ed92b305be..09557c94aa6 100644
--- a/src/librustc/middle/typeck/astconv.rs
+++ b/src/librustc/middle/typeck/astconv.rs
@@ -52,13 +52,13 @@
 use middle::const_eval;
 use middle::def;
 use middle::lang_items::FnMutTraitLangItem;
-use rl = middle::resolve_lifetime;
 use middle::subst::{FnSpace, TypeSpace, SelfSpace, Subst, Substs};
 use middle::ty;
-use middle::typeck::TypeAndSubsts;
-use middle::typeck::lookup_def_tcx;
+use middle::ty_fold::TypeFolder;
 use middle::typeck::rscope::RegionScope;
-use middle::typeck::rscope;
+use middle::typeck::{TypeAndSubsts, infer, lookup_def_tcx, rscope};
+use middle::typeck;
+use rl = middle::resolve_lifetime;
 use util::ppaux::Repr;
 
 use std::rc::Rc;
@@ -900,58 +900,73 @@ pub fn ty_of_arg<AC: AstConv, RS: RegionScope>(this: &AC, rscope: &RS, a: &ast::
     }
 }
 
-struct SelfInfo {
+struct SelfInfo<'a> {
     untransformed_self_ty: ty::t,
-    explicit_self: ast::ExplicitSelf
+    explicit_self: ast::ExplicitSelf,
 }
 
 pub fn ty_of_method<AC:AstConv>(
-    this: &AC,
-    id: ast::NodeId,
-    fn_style: ast::FnStyle,
-    untransformed_self_ty: ty::t,
-    explicit_self: ast::ExplicitSelf,
-    decl: &ast::FnDecl)
-    -> ty::BareFnTy
-{
-    ty_of_method_or_bare_fn(this, id, fn_style, abi::Rust, Some(SelfInfo {
+                    this: &AC,
+                    id: ast::NodeId,
+                    fn_style: ast::FnStyle,
+                    untransformed_self_ty: ty::t,
+                    explicit_self: ast::ExplicitSelf,
+                    decl: &ast::FnDecl)
+                    -> (ty::BareFnTy, ty::ExplicitSelfCategory) {
+    let self_info = Some(SelfInfo {
         untransformed_self_ty: untransformed_self_ty,
-        explicit_self: explicit_self
-    }), decl)
+        explicit_self: explicit_self,
+    });
+    let (bare_fn_ty, optional_explicit_self_category) =
+        ty_of_method_or_bare_fn(this,
+                                id,
+                                fn_style,
+                                abi::Rust,
+                                self_info,
+                                decl);
+    (bare_fn_ty, optional_explicit_self_category.unwrap())
 }
 
 pub fn ty_of_bare_fn<AC:AstConv>(this: &AC, id: ast::NodeId,
                                  fn_style: ast::FnStyle, abi: abi::Abi,
                                  decl: &ast::FnDecl) -> ty::BareFnTy {
-    ty_of_method_or_bare_fn(this, id, fn_style, abi, None, decl)
+    let (bare_fn_ty, _) =
+        ty_of_method_or_bare_fn(this, id, fn_style, abi, None, decl);
+    bare_fn_ty
 }
 
-fn ty_of_method_or_bare_fn<AC:AstConv>(this: &AC, id: ast::NodeId,
-                                       fn_style: ast::FnStyle, abi: abi::Abi,
-                                       opt_self_info: Option<SelfInfo>,
-                                       decl: &ast::FnDecl) -> ty::BareFnTy {
+fn ty_of_method_or_bare_fn<AC:AstConv>(
+                           this: &AC,
+                           id: ast::NodeId,
+                           fn_style: ast::FnStyle,
+                           abi: abi::Abi,
+                           opt_self_info: Option<SelfInfo>,
+                           decl: &ast::FnDecl)
+                           -> (ty::BareFnTy,
+                               Option<ty::ExplicitSelfCategory>) {
     debug!("ty_of_method_or_bare_fn");
 
     // new region names that appear inside of the fn decl are bound to
     // that function type
     let rb = rscope::BindingRscope::new(id);
 
+    let mut explicit_self_category_result = None;
     let self_ty = opt_self_info.and_then(|self_info| {
-        match self_info.explicit_self.node {
-            ast::SelfStatic => None,
-            ast::SelfValue(_) => {
+        // Figure out and record the explicit self category.
+        let explicit_self_category =
+            determine_explicit_self_category(this, &rb, &self_info);
+        explicit_self_category_result = Some(explicit_self_category);
+        match explicit_self_category {
+            ty::StaticExplicitSelfCategory => None,
+            ty::ByValueExplicitSelfCategory => {
                 Some(self_info.untransformed_self_ty)
             }
-            ast::SelfRegion(ref lifetime, mutability, _) => {
-                let region =
-                    opt_ast_region_to_region(this, &rb,
-                                             self_info.explicit_self.span,
-                                             lifetime);
+            ty::ByReferenceExplicitSelfCategory(region, mutability) => {
                 Some(ty::mk_rptr(this.tcx(), region,
                                  ty::mt {ty: self_info.untransformed_self_ty,
                                          mutbl: mutability}))
             }
-            ast::SelfUniq(_) => {
+            ty::ByBoxExplicitSelfCategory => {
                 Some(ty::mk_uniq(this.tcx(), self_info.untransformed_self_ty))
             }
         }
@@ -972,7 +987,7 @@ fn ty_of_method_or_bare_fn<AC:AstConv>(this: &AC, id: ast::NodeId,
         _ => ast_ty_to_ty(this, &rb, &*decl.output)
     };
 
-    return ty::BareFnTy {
+    (ty::BareFnTy {
         fn_style: fn_style,
         abi: abi,
         sig: ty::FnSig {
@@ -981,7 +996,83 @@ fn ty_of_method_or_bare_fn<AC:AstConv>(this: &AC, id: ast::NodeId,
             output: output_ty,
             variadic: decl.variadic
         }
-    };
+    }, explicit_self_category_result)
+}
+
+fn determine_explicit_self_category<AC:AstConv,
+                                    RS:RegionScope>(
+                                    this: &AC,
+                                    rscope: &RS,
+                                    self_info: &SelfInfo)
+                                    -> ty::ExplicitSelfCategory {
+    match self_info.explicit_self.node {
+        ast::SelfStatic => ty::StaticExplicitSelfCategory,
+        ast::SelfValue(_) => ty::ByValueExplicitSelfCategory,
+        ast::SelfRegion(ref lifetime, mutability, _) => {
+            let region =
+                opt_ast_region_to_region(this,
+                                         rscope,
+                                         self_info.explicit_self.span,
+                                         lifetime);
+            ty::ByReferenceExplicitSelfCategory(region, mutability)
+        }
+        ast::SelfUniq(_) => ty::ByBoxExplicitSelfCategory,
+        ast::SelfExplicit(ast_type, _) => {
+            let explicit_type = ast_ty_to_ty(this, rscope, ast_type);
+
+            {
+                let inference_context = infer::new_infer_ctxt(this.tcx());
+                let expected_self = self_info.untransformed_self_ty;
+                let actual_self = explicit_type;
+                let result = infer::mk_eqty(
+                    &inference_context,
+                    false,
+                    infer::Misc(self_info.explicit_self.span),
+                    expected_self,
+                    actual_self);
+                match result {
+                    Ok(_) => {
+                        inference_context.resolve_regions_and_report_errors();
+                        return ty::ByValueExplicitSelfCategory
+                    }
+                    Err(_) => {}
+                }
+            }
+
+            match ty::get(explicit_type).sty {
+                ty::ty_rptr(region, tm) => {
+                    typeck::require_same_types(
+                        this.tcx(),
+                        None,
+                        false,
+                        self_info.explicit_self.span,
+                        self_info.untransformed_self_ty,
+                        tm.ty,
+                        || "not a valid type for `self`".to_owned());
+                    return ty::ByReferenceExplicitSelfCategory(region,
+                                                               tm.mutbl)
+                }
+                ty::ty_uniq(typ) => {
+                    typeck::require_same_types(
+                        this.tcx(),
+                        None,
+                        false,
+                        self_info.explicit_self.span,
+                        self_info.untransformed_self_ty,
+                        typ,
+                        || "not a valid type for `self`".to_owned());
+                    return ty::ByBoxExplicitSelfCategory
+                }
+                _ => {
+                    this.tcx()
+                        .sess
+                        .span_err(self_info.explicit_self.span,
+                                  "not a valid type for `self`");
+                    return ty::ByValueExplicitSelfCategory
+                }
+            }
+        }
+    }
 }
 
 pub fn ty_of_closure<AC:AstConv>(
@@ -1098,3 +1189,4 @@ fn conv_builtin_bounds(tcx: &ty::ctxt,
         (&None, ty::UniqTraitStore) => ty::empty_builtin_bounds(),
     }
 }
+
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index 47878370938..e12fae4f950 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -100,9 +100,7 @@ use util::ppaux::Repr;
 
 use std::collections::HashSet;
 use std::rc::Rc;
-use syntax::ast::{DefId, SelfValue, SelfRegion};
-use syntax::ast::{SelfUniq, SelfStatic};
-use syntax::ast::{MutMutable, MutImmutable};
+use syntax::ast::{DefId, MutImmutable, MutMutable};
 use syntax::ast;
 use syntax::codemap::Span;
 use syntax::parse::token;
@@ -267,15 +265,15 @@ fn construct_transformed_self_ty_for_object(
     obj_substs.types.pop(subst::SelfSpace).unwrap();
 
     match method_ty.explicit_self {
-        ast::SelfStatic => {
+        StaticExplicitSelfCategory => {
             tcx.sess.span_bug(span, "static method for object type receiver");
         }
-        ast::SelfValue(_) => {
+        ByValueExplicitSelfCategory => {
             let tr = ty::mk_trait(tcx, trait_def_id, obj_substs,
                                   ty::empty_builtin_bounds());
             ty::mk_uniq(tcx, tr)
         }
-        ast::SelfRegion(..) | ast::SelfUniq(..) => {
+        ByReferenceExplicitSelfCategory(..) | ByBoxExplicitSelfCategory => {
             let transformed_self_ty = *method_ty.fty.sig.inputs.get(0);
             match ty::get(transformed_self_ty).sty {
                 ty::ty_rptr(r, mt) => { // must be SelfRegion
@@ -618,7 +616,7 @@ impl<'a> LookupContext<'a> {
 
             let trait_methods = ty::trait_methods(tcx, bound_trait_ref.def_id);
             match trait_methods.iter().position(|m| {
-                m.explicit_self != ast::SelfStatic &&
+                m.explicit_self != ty::StaticExplicitSelfCategory &&
                 m.ident.name == self.m_name }) {
                 Some(pos) => {
                     let method = trait_methods.get(pos).clone();
@@ -1023,7 +1021,10 @@ impl<'a> LookupContext<'a> {
 
         if self.report_statics == ReportStaticMethods {
             // lookup should only be called with ReportStaticMethods if a regular lookup failed
-            assert!(relevant_candidates.iter().all(|c| c.method_ty.explicit_self == SelfStatic));
+            assert!(relevant_candidates.iter()
+                                       .all(|c| {
+                c.method_ty.explicit_self == ty::StaticExplicitSelfCategory
+            }));
 
             self.tcx().sess.fileline_note(self.span,
                                 "found defined static methods, maybe a `self` is missing?");
@@ -1100,7 +1101,8 @@ impl<'a> LookupContext<'a> {
         self.enforce_drop_trait_limitations(candidate);
 
         // static methods should never have gotten this far:
-        assert!(candidate.method_ty.explicit_self != SelfStatic);
+        assert!(candidate.method_ty.explicit_self !=
+                ty::StaticExplicitSelfCategory);
 
         // Determine the values for the generic parameters of the method.
         // If they were not explicitly supplied, just construct fresh
@@ -1217,12 +1219,16 @@ impl<'a> LookupContext<'a> {
         }
 
         match candidate.method_ty.explicit_self {
-            ast::SelfStatic => { // reason (a) above
-                span_err!(self.tcx().sess, self.span, E0037,
-                    "cannot call a method without a receiver through an object");
+            ty::StaticExplicitSelfCategory => { // reason (a) above
+                self.tcx().sess.span_err(
+                    self.span,
+                    "cannot call a method without a receiver \
+                     through an object");
             }
 
-            ast::SelfValue(_) | ast::SelfRegion(..) | ast::SelfUniq(_) => {}
+            ty::ByValueExplicitSelfCategory |
+            ty::ByReferenceExplicitSelfCategory(..) |
+            ty::ByBoxExplicitSelfCategory => {}
         }
 
         // reason (a) above
@@ -1284,12 +1290,12 @@ impl<'a> LookupContext<'a> {
                self.ty_to_string(rcvr_ty), candidate.repr(self.tcx()));
 
         return match candidate.method_ty.explicit_self {
-            SelfStatic => {
+            StaticExplicitSelfCategory => {
                 debug!("(is relevant?) explicit self is static");
                 self.report_statics == ReportStaticMethods
             }
 
-            SelfValue(_) => {
+            ByValueExplicitSelfCategory => {
                 debug!("(is relevant?) explicit self is by-value");
                 match ty::get(rcvr_ty).sty {
                     ty::ty_uniq(typ) => {
@@ -1312,7 +1318,7 @@ impl<'a> LookupContext<'a> {
                 }
             }
 
-            SelfRegion(_, m, _) => {
+            ByReferenceExplicitSelfCategory(_, m) => {
                 debug!("(is relevant?) explicit self is a region");
                 match ty::get(rcvr_ty).sty {
                     ty::ty_rptr(_, mt) => {
@@ -1332,7 +1338,7 @@ impl<'a> LookupContext<'a> {
                 }
             }
 
-            SelfUniq(_) => {
+            ByBoxExplicitSelfCategory => {
                 debug!("(is relevant?) explicit self is a unique pointer");
                 match ty::get(rcvr_ty).sty {
                     ty::ty_uniq(typ) => {
@@ -1480,3 +1486,6 @@ impl Repr for RcvrMatchCondition {
         }
     }
 }
+
+
+
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index bc4d1c73ffb..4f07f1121b7 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -862,19 +862,26 @@ fn compare_impl_method(tcx: &ty::ctxt,
     // inscrutable, particularly for cases where one method has no
     // self.
     match (&trait_m.explicit_self, &impl_m.explicit_self) {
-        (&ast::SelfStatic, &ast::SelfStatic) => {}
-        (&ast::SelfStatic, _) => {
-            span_err!(tcx.sess, impl_m_span, E0047,
-                "method `{}` has a `{}` declaration in the impl, but not in the trait",
-                token::get_ident(trait_m.ident),
-                pprust::explicit_self_to_string(impl_m.explicit_self));
+        (&ty::StaticExplicitSelfCategory,
+         &ty::StaticExplicitSelfCategory) => {}
+        (&ty::StaticExplicitSelfCategory, _) => {
+            tcx.sess.span_err(
+                impl_m_span,
+                format!("method `{}` has a `{}` declaration in the impl, \
+                        but not in the trait",
+                        token::get_ident(trait_m.ident),
+                        ppaux::explicit_self_category_to_str(
+                            &impl_m.explicit_self)).as_slice());
             return;
         }
-        (_, &ast::SelfStatic) => {
-            span_err!(tcx.sess, impl_m_span, E0048,
-                "method `{}` has a `{}` declaration in the trait, but not in the impl",
-                token::get_ident(trait_m.ident),
-                pprust::explicit_self_to_string(trait_m.explicit_self));
+        (_, &ty::StaticExplicitSelfCategory) => {
+            tcx.sess.span_err(
+                impl_m_span,
+                format!("method `{}` has a `{}` declaration in the trait, \
+                        but not in the impl",
+                        token::get_ident(trait_m.ident),
+                        ppaux::explicit_self_category_to_str(
+                            &trait_m.explicit_self)).as_slice());
             return;
         }
         _ => {
@@ -4787,3 +4794,4 @@ pub fn check_intrinsic_type(ccx: &CrateCtxt, it: &ast::ForeignItem) {
             });
     }
 }
+
diff --git a/src/librustc/middle/typeck/collect.rs b/src/librustc/middle/typeck/collect.rs
index e21a7949ec7..eea26fbcfc7 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -40,11 +40,14 @@ use middle::subst::{Substs};
 use middle::ty::{ImplContainer, MethodContainer, TraitContainer};
 use middle::ty::{Polytype};
 use middle::ty;
+use middle::ty_fold::TypeFolder;
 use middle::typeck::astconv::{AstConv, ty_of_arg};
 use middle::typeck::astconv::{ast_ty_to_ty};
 use middle::typeck::astconv;
+use middle::typeck::infer;
 use middle::typeck::rscope::*;
 use middle::typeck::{CrateCtxt, lookup_def_tcx, no_params, write_ty_to_tcx};
+use middle::typeck;
 use util::ppaux;
 use util::ppaux::Repr;
 
@@ -218,7 +221,8 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt,
                             }
                         });
 
-                        if ty_method.explicit_self == ast::SelfStatic {
+                        if ty_method.explicit_self ==
+                                ty::StaticExplicitSelfCategory {
                             make_static_method_ty(ccx, &*ty_method);
                         }
 
@@ -266,18 +270,26 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt,
                                  m_fn_style: &ast::FnStyle,
                                  m_decl: &ast::FnDecl) -> ty::Method
     {
-        let trait_self_ty = ty::mk_self_type(this.tcx, local_def(trait_id));
-        let fty = astconv::ty_of_method(this, *m_id, *m_fn_style, trait_self_ty,
-                                        *m_explicit_self, m_decl);
-        let ty_generics =
-            ty_generics_for_fn_or_method(this,
-                                         m_generics,
-                                         (*trait_generics).clone());
+        let trait_self_ty = ty::mk_param(this.tcx,
+                                         subst::SelfSpace,
+                                         0,
+                                         local_def(trait_id));
+        let ty_generics = ty_generics_for_fn_or_method(
+            this,
+            m_generics,
+            (*trait_generics).clone());
+        let (fty, explicit_self_category) =
+            astconv::ty_of_method(this,
+                                  *m_id,
+                                  *m_fn_style,
+                                  trait_self_ty,
+                                  *m_explicit_self,
+                                  m_decl);
         ty::Method::new(
             *m_ident,
             ty_generics,
             fty,
-            m_explicit_self.node,
+            explicit_self_category,
             // assume public, because this is only invoked on trait methods
             ast::Public,
             local_def(*m_id),
@@ -365,9 +377,13 @@ fn convert_methods(ccx: &CrateCtxt,
                     rcvr_visibility: ast::Visibility)
                     -> ty::Method
     {
-        let fty = astconv::ty_of_method(ccx, m.id, m.pe_fn_style(),
-                                        untransformed_rcvr_ty,
-                                        *m.pe_explicit_self(), m.pe_fn_decl());
+        let (fty, explicit_self_category) =
+            astconv::ty_of_method(ccx,
+                                  m.id,
+                                  m.pe_fn_style(),
+                                  untransformed_rcvr_ty,
+                                  *m.pe_explicit_self(),
+                                  m.pe_fn_decl());
 
         // if the method specifies a visibility, use that, otherwise
         // inherit the visibility from the impl (so `foo` in `pub impl
@@ -381,7 +397,7 @@ fn convert_methods(ccx: &CrateCtxt,
         ty::Method::new(m.pe_ident(),
                         m_ty_generics,
                         fty,
-                        m.pe_explicit_self().node,
+                        explicit_self_category,
                         method_vis,
                         local_def(m.id),
                         container,
@@ -450,6 +466,13 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
                 it.vis
             };
 
+            for method in ms.iter() {
+                check_method_self_type(ccx,
+                                       &BindingRscope::new(method.id),
+                                       selfty,
+                                       method.pe_explicit_self())
+            }
+
             convert_methods(ccx,
                             ImplContainer(local_def(it.id)),
                             ms.as_slice(),
@@ -464,6 +487,28 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
         ast::ItemTrait(_, _, _, ref trait_methods) => {
             let trait_def = trait_def_of_item(ccx, it);
 
+            for trait_method in trait_methods.iter() {
+                let self_type = ty::mk_param(ccx.tcx,
+                                             subst::SelfSpace,
+                                             0,
+                                             local_def(it.id));
+                match *trait_method {
+                    ast::Required(ref type_method) => {
+                        let rscope = BindingRscope::new(type_method.id);
+                        check_method_self_type(ccx,
+                                               &rscope,
+                                               self_type,
+                                               &type_method.explicit_self)
+                    }
+                    ast::Provided(ref method) => {
+                        check_method_self_type(ccx,
+                                               &BindingRscope::new(method.id),
+                                               self_type,
+                                               method.pe_explicit_self())
+                    }
+                }
+            }
+
             // Run convert_methods on the provided methods.
             let (_, provided_methods) =
                 split_trait_methods(trait_methods.as_slice());
@@ -1240,3 +1285,36 @@ pub fn mk_item_substs(ccx: &CrateCtxt,
 
     subst::Substs::new(types, regions)
 }
+
+/// Verifies that the explicit self type of a method matches the impl or
+/// trait.
+fn check_method_self_type<RS:RegionScope>(
+                          crate_context: &CrateCtxt,
+                          rs: &RS,
+                          required_type: ty::t,
+                          explicit_self: &ast::ExplicitSelf) {
+    match explicit_self.node {
+        ast::SelfExplicit(ref ast_type, _) => {
+            let typ = crate_context.to_ty(rs, *ast_type);
+            let base_type = match ty::get(typ).sty {
+                ty::ty_rptr(_, tm) => tm.ty,
+                ty::ty_uniq(typ) => typ,
+                _ => typ,
+            };
+            let infcx = infer::new_infer_ctxt(crate_context.tcx);
+            drop(typeck::require_same_types(crate_context.tcx,
+                                            Some(&infcx),
+                                            false,
+                                            explicit_self.span,
+                                            base_type,
+                                            required_type,
+                                            || {
+                format!("mismatched self type: expected `{}`",
+                        ppaux::ty_to_string(crate_context.tcx, required_type))
+            }));
+            infcx.resolve_regions_and_report_errors();
+        }
+        _ => {}
+    }
+}
+
diff --git a/src/librustc/middle/typeck/infer/combine.rs b/src/librustc/middle/typeck/infer/combine.rs
index 1e33b1d5d0e..c3de120a0c3 100644
--- a/src/librustc/middle/typeck/infer/combine.rs
+++ b/src/librustc/middle/typeck/infer/combine.rs
@@ -111,7 +111,11 @@ pub trait Combine {
               b_subst: &subst::Substs)
               -> cres<subst::Substs>
     {
-        let variances = ty::item_variances(self.infcx().tcx, item_def_id);
+        let variances = if self.infcx().tcx.variance_computed.get() {
+            Some(ty::item_variances(self.infcx().tcx, item_def_id))
+        } else {
+            None
+        };
         let mut substs = subst::Substs::empty();
 
         for &space in subst::ParamSpace::all().iter() {
@@ -121,7 +125,18 @@ pub trait Combine {
 
             let a_regions = a_subst.regions().get_slice(space);
             let b_regions = b_subst.regions().get_slice(space);
-            let r_variances = variances.regions.get_slice(space);
+
+            let mut invariance = Vec::new();
+            let r_variances = match variances {
+                Some(ref variances) => variances.regions.get_slice(space),
+                None => {
+                    for _ in a_regions.iter() {
+                        invariance.push(ty::Invariant);
+                    }
+                    invariance.as_slice()
+                }
+            };
+
             let regions = if_ok!(relate_region_params(self,
                                                       item_def_id,
                                                       r_variances,
diff --git a/src/librustc/middle/typeck/infer/region_inference/mod.rs b/src/librustc/middle/typeck/infer/region_inference/mod.rs
index 28240686dc3..d17553e9c39 100644
--- a/src/librustc/middle/typeck/infer/region_inference/mod.rs
+++ b/src/librustc/middle/typeck/infer/region_inference/mod.rs
@@ -13,16 +13,15 @@
 
 use middle::ty;
 use middle::ty::{BoundRegion, FreeRegion, Region, RegionVid};
-use middle::ty::{ReEmpty, ReStatic, ReInfer, ReFree, ReEarlyBound,
-                 ReLateBound};
-use middle::ty::{ReScope, ReVar, ReSkolemized, BrFresh};
+use middle::ty::{ReEmpty, ReStatic, ReInfer, ReFree, ReEarlyBound};
+use middle::ty::{ReLateBound, ReScope, ReVar, ReSkolemized, BrFresh};
 use middle::typeck::infer::cres;
 use middle::typeck::infer::{RegionVariableOrigin, SubregionOrigin, TypeTrace};
 use middle::typeck::infer;
 use middle::graph;
 use middle::graph::{Direction, NodeIndex};
 use util::common::indenter;
-use util::ppaux::{Repr};
+use util::ppaux::Repr;
 
 use std::cell::{Cell, RefCell};
 use std::uint;
@@ -318,6 +317,11 @@ impl<'a> RegionVarBindings<'a> {
                origin.repr(self.tcx));
 
         match (sub, sup) {
+          (ReEarlyBound(..), ReEarlyBound(..)) => {
+            // This case is used only to make sure that explicitly-specified
+            // `Self` types match the real self type in implementations.
+            self.add_constraint(ConstrainRegSubReg(sub, sup), origin);
+          }
           (ReEarlyBound(..), _) |
           (ReLateBound(..), _) |
           (_, ReEarlyBound(..)) |
diff --git a/src/librustc/middle/typeck/variance.rs b/src/librustc/middle/typeck/variance.rs
index 8b5d16620b0..a65aa0423a6 100644
--- a/src/librustc/middle/typeck/variance.rs
+++ b/src/librustc/middle/typeck/variance.rs
@@ -214,6 +214,7 @@ pub fn infer_variance(tcx: &ty::ctxt,
     let terms_cx = determine_parameters_to_be_inferred(tcx, &mut arena, krate);
     let constraints_cx = add_constraints_from_crate(terms_cx, krate);
     solve_constraints(constraints_cx);
+    tcx.variance_computed.set(true);
 }
 
 /**************************************************************************
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 6526943955c..e37bef98e44 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -14,7 +14,7 @@ use middle::subst;
 use middle::subst::{VecPerParamSpace,Subst};
 use middle::ty::{ReSkolemized, ReVar};
 use middle::ty::{BoundRegion, BrAnon, BrNamed};
-use middle::ty::{BrFresh, ctxt};
+use middle::ty::{ReEarlyBound, BrFresh, ctxt};
 use middle::ty::{mt, t, ParamTy};
 use middle::ty::{ReFree, ReScope, ReInfer, ReStatic, Region, ReEmpty};
 use middle::ty::{ty_bool, ty_char, ty_bot, ty_box, ty_struct, ty_enum};
@@ -130,9 +130,13 @@ pub fn explain_region_and_span(cx: &ctxt, region: ty::Region)
 
       ReEmpty => { ("the empty lifetime".to_string(), None) }
 
+      ReEarlyBound(_, _, _, name) => {
+        (format!("{}", token::get_name(name)), None)
+      }
+
       // I believe these cases should not occur (except when debugging,
       // perhaps)
-      ty::ReInfer(_) | ty::ReEarlyBound(..) | ty::ReLateBound(..) => {
+      ty::ReInfer(_) | ty::ReLateBound(..) => {
         (format!("lifetime {:?}", region), None)
       }
     };
@@ -421,6 +425,19 @@ pub fn ty_to_string(cx: &ctxt, typ: t) -> String {
     }
 }
 
+pub fn explicit_self_category_to_str(category: &ty::ExplicitSelfCategory)
+                                     -> &'static str {
+    match *category {
+        ty::StaticExplicitSelfCategory => "static",
+        ty::ByValueExplicitSelfCategory => "self",
+        ty::ByReferenceExplicitSelfCategory(_, ast::MutMutable) => {
+            "&mut self"
+        }
+        ty::ByReferenceExplicitSelfCategory(_, ast::MutImmutable) => "&self",
+        ty::ByBoxExplicitSelfCategory => "Box<self>",
+    }
+}
+
 pub fn parameterized(cx: &ctxt,
                      base: &str,
                      substs: &subst::Substs,
@@ -1083,3 +1100,10 @@ impl Repr for region_inference::VarValue {
         }
     }
 }
+
+impl Repr for ty::ExplicitSelfCategory {
+    fn repr(&self, _: &ctxt) -> String {
+        explicit_self_category_to_str(self).to_string()
+    }
+}
+
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index 54053d215dc..5be66885320 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -394,7 +394,7 @@ impl Clean<Item> for doctree::Module {
     }
 }
 
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub enum Attribute {
     Word(String),
     List(String, Vec<Attribute> ),
@@ -447,7 +447,7 @@ impl<'a> attr::AttrMetaMethods for &'a Attribute {
     fn meta_item_list<'a>(&'a self) -> Option<&'a [Gc<ast::MetaItem>]> { None }
 }
 
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub struct TyParam {
     pub name: String,
     pub did: ast::DefId,
@@ -479,7 +479,7 @@ impl Clean<TyParam> for ty::TypeParameterDef {
     }
 }
 
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub enum TyParamBound {
     RegionBound,
     TraitBound(Type)
@@ -638,7 +638,7 @@ impl Clean<Option<Lifetime>> for ty::Region {
 }
 
 // maybe use a Generic enum and use ~[Generic]?
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub struct Generics {
     pub lifetimes: Vec<Lifetime>,
     pub type_params: Vec<TyParam>,
@@ -771,6 +771,7 @@ pub enum SelfTy {
     SelfValue,
     SelfBorrowed(Option<Lifetime>, Mutability),
     SelfOwned,
+    SelfExplicit(Type),
 }
 
 impl Clean<SelfTy> for ast::ExplicitSelf_ {
@@ -779,7 +780,10 @@ impl Clean<SelfTy> for ast::ExplicitSelf_ {
             ast::SelfStatic => SelfStatic,
             ast::SelfValue(_) => SelfValue,
             ast::SelfUniq(_) => SelfOwned,
-            ast::SelfRegion(lt, mt, _) => SelfBorrowed(lt.clean(), mt.clean()),
+            ast::SelfRegion(lt, mt, _) => {
+                SelfBorrowed(lt.clean(), mt.clean())
+            }
+            ast::SelfExplicit(typ, _) => SelfExplicit(typ.clean()),
         }
     }
 }
@@ -809,7 +813,7 @@ impl Clean<Item> for doctree::Function {
     }
 }
 
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub struct ClosureDecl {
     pub lifetimes: Vec<Lifetime>,
     pub decl: FnDecl,
@@ -833,7 +837,7 @@ impl Clean<ClosureDecl> for ast::ClosureTy {
     }
 }
 
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub struct FnDecl {
     pub inputs: Arguments,
     pub output: Type,
@@ -841,7 +845,7 @@ pub struct FnDecl {
     pub attrs: Vec<Attribute>,
 }
 
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub struct Arguments {
     pub values: Vec<Argument>,
 }
@@ -888,7 +892,7 @@ impl<'a> Clean<FnDecl> for (ast::DefId, &'a ty::FnSig) {
     }
 }
 
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub struct Argument {
     pub type_: Type,
     pub name: String,
@@ -905,7 +909,7 @@ impl Clean<Argument> for ast::Arg {
     }
 }
 
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub enum RetStyle {
     NoReturn,
     Return
@@ -991,22 +995,28 @@ impl Clean<Item> for ty::Method {
     fn clean(&self) -> Item {
         let cx = get_cx();
         let (self_, sig) = match self.explicit_self {
-            ast::SelfStatic => (ast::SelfStatic.clean(), self.fty.sig.clone()),
+            ty::StaticExplicitSelfCategory => (ast::SelfStatic.clean(), self.fty.sig.clone()),
             s => {
                 let sig = ty::FnSig {
                     inputs: Vec::from_slice(self.fty.sig.inputs.slice_from(1)),
                     ..self.fty.sig.clone()
                 };
                 let s = match s {
-                    ast::SelfRegion(..) => {
-                        match ty::get(self.fty.sig.inputs[0]).sty {
+                    ty::ByReferenceExplicitSelfCategory(..) => {
+                        match ty::get(*self.fty.sig.inputs[0]).sty {
                             ty::ty_rptr(r, mt) => {
                                 SelfBorrowed(r.clean(), mt.mutbl.clean())
                             }
-                            _ => s.clean(),
+                            _ => {
+                                // FIXME(pcwalton): This is wrong.
+                                SelfStatic
+                            }
                         }
                     }
-                    s => s.clean(),
+                    _ => {
+                        // FIXME(pcwalton): This is wrong.
+                        SelfStatic
+                    }
                 };
                 (s, sig)
             }
@@ -1032,7 +1042,7 @@ impl Clean<Item> for ty::Method {
 /// A representation of a Type suitable for hyperlinking purposes. Ideally one can get the original
 /// type out of the AST/ty::ctxt given one of these, if more information is needed. Most importantly
 /// it does not preserve mutability or boxes.
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub enum Type {
     /// structs/enums/traits (anything that'd be an ast::TyPath)
     ResolvedPath {
@@ -1550,7 +1560,7 @@ impl Clean<Span> for syntax::codemap::Span {
     }
 }
 
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub struct Path {
     pub global: bool,
     pub segments: Vec<PathSegment>,
@@ -1565,7 +1575,7 @@ impl Clean<Path> for ast::Path {
     }
 }
 
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub struct PathSegment {
     pub name: String,
     pub lifetimes: Vec<Lifetime>,
@@ -1631,7 +1641,7 @@ impl Clean<Item> for doctree::Typedef {
     }
 }
 
-#[deriving(Clone, Encodable, Decodable)]
+#[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub struct BareFunctionDecl {
     pub fn_style: ast::FnStyle,
     pub generics: Generics,
diff --git a/src/librustdoc/html/format.rs b/src/librustdoc/html/format.rs
index f64a75c559e..d0f9b37cc4c 100644
--- a/src/librustdoc/html/format.rs
+++ b/src/librustdoc/html/format.rs
@@ -500,6 +500,9 @@ impl<'a> fmt::Show for Method<'a> {
                 args.push_str(format!("&amp;{}self",
                                       MutableSpace(mtbl)).as_slice());
             }
+            clean::SelfExplicit(ref typ) => {
+                args.push_str(format!("self: {}", *typ).as_slice());
+            }
         }
         for (i, input) in d.inputs.values.iter().enumerate() {
             if i > 0 || args.len() > 0 { args.push_str(", "); }
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 857cb4c0162..d9f14bfa156 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -949,12 +949,14 @@ pub enum RetStyle {
 pub enum ExplicitSelf_ {
     /// No self
     SelfStatic,
-    /// `self
+    /// `self`
     SelfValue(Ident),
     /// `&'lt self`, `&'lt mut self`
     SelfRegion(Option<Lifetime>, Mutability, Ident),
     /// `~self`
-    SelfUniq(Ident)
+    SelfUniq(Ident),
+    /// `self: TYPE`
+    SelfExplicit(P<Ty>, Ident),
 }
 
 pub type ExplicitSelf = Spanned<ExplicitSelf_>;
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index fd786192cb4..87c762af2e5 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -344,6 +344,7 @@ pub trait Folder {
             SelfRegion(ref lifetime, m, id) => {
                 SelfRegion(fold_opt_lifetime(lifetime, self), m, id)
             }
+            SelfExplicit(ref typ, id) => SelfExplicit(self.fold_ty(*typ), id),
         }
     }
 
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index e0c94dffb5c..bdfd928cfbc 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -45,7 +45,7 @@ use ast::{RetStyle, Return, BiShl, BiShr, Stmt, StmtDecl};
 use ast::{StmtExpr, StmtSemi, StmtMac, StructDef, StructField};
 use ast::{StructVariantKind, BiSub};
 use ast::StrStyle;
-use ast::{SelfRegion, SelfStatic, SelfUniq, SelfValue};
+use ast::{SelfExplicit, SelfRegion, SelfStatic, SelfUniq, SelfValue};
 use ast::{TokenTree, TraitMethod, TraitRef, TTDelim, TTSeq, TTTok};
 use ast::{TTNonterminal, TupleVariantKind, Ty, Ty_, TyBot, TyBox};
 use ast::{TypeField, TyFixedLengthVec, TyClosure, TyProc, TyBareFn};
@@ -3843,7 +3843,15 @@ impl<'a> Parser<'a> {
                 }
             }
             token::IDENT(..) if self.is_self_ident() => {
-                SelfValue(self.expect_self_ident())
+                let self_ident = self.expect_self_ident();
+
+                // Determine whether this is the fully explicit form, `self:
+                // TYPE`.
+                if self.eat(&token::COLON) {
+                    SelfExplicit(self.parse_ty(false), self_ident)
+                } else {
+                    SelfValue(self_ident)
+                }
             }
             token::BINOP(token::STAR) => {
                 // Possibly "*self" or "*mut self" -- not supported. Try to avoid
@@ -3851,7 +3859,9 @@ impl<'a> Parser<'a> {
                 self.bump();
                 let _mutability = if Parser::token_is_mutability(&self.token) {
                     self.parse_mutability()
-                } else { MutImmutable };
+                } else {
+                    MutImmutable
+                };
                 if self.is_self_ident() {
                     let span = self.span;
                     self.span_err(span, "cannot pass self by unsafe pointer");
@@ -3863,7 +3873,15 @@ impl<'a> Parser<'a> {
             _ if Parser::token_is_mutability(&self.token) &&
                     self.look_ahead(1, |t| token::is_keyword(keywords::Self, t)) => {
                 mutbl_self = self.parse_mutability();
-                SelfValue(self.expect_self_ident())
+                let self_ident = self.expect_self_ident();
+
+                // Determine whether this is the fully explicit form, `self:
+                // TYPE`.
+                if self.eat(&token::COLON) {
+                    SelfExplicit(self.parse_ty(false), self_ident)
+                } else {
+                    SelfValue(self_ident)
+                }
             }
             _ if Parser::token_is_mutability(&self.token) &&
                     self.look_ahead(1, |t| *t == token::TILDE) &&
@@ -3914,8 +3932,8 @@ impl<'a> Parser<'a> {
             }
             SelfValue(id) => parse_remaining_arguments!(id),
             SelfRegion(_,_,id) => parse_remaining_arguments!(id),
-            SelfUniq(id) => parse_remaining_arguments!(id)
-
+            SelfUniq(id) => parse_remaining_arguments!(id),
+            SelfExplicit(_,id) => parse_remaining_arguments!(id),
         };
 
 
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index d524622f8ec..428a15cb8cf 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -1859,6 +1859,11 @@ impl<'a> State<'a> {
                 try!(self.print_mutability(m));
                 try!(word(&mut self.s, "self"));
             }
+            ast::SelfExplicit(ref typ, _) => {
+                try!(word(&mut self.s, "self"));
+                try!(self.word_space(":"));
+                try!(self.print_type(*typ));
+            }
         }
         return Ok(true);
     }
diff --git a/src/libsyntax/visit.rs b/src/libsyntax/visit.rs
index 795f19d0cfb..6760d7a3932 100644
--- a/src/libsyntax/visit.rs
+++ b/src/libsyntax/visit.rs
@@ -215,6 +215,7 @@ pub fn walk_explicit_self<E: Clone, V: Visitor<E>>(visitor: &mut V,
         SelfRegion(ref lifetime, _, _) => {
             visitor.visit_opt_lifetime_ref(explicit_self.span, lifetime, env)
         }
+        SelfExplicit(ref typ, _) => visitor.visit_ty(*typ, env.clone()),
     }
 }
 
diff --git a/src/test/compile-fail/explicit-self-lifetime-mismatch.rs b/src/test/compile-fail/explicit-self-lifetime-mismatch.rs
new file mode 100644
index 00000000000..285792e26b1
--- /dev/null
+++ b/src/test/compile-fail/explicit-self-lifetime-mismatch.rs
@@ -0,0 +1,26 @@
+// 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.
+
+struct Foo<'a,'b> {
+    x: &'a int,
+    y: &'b int,
+}
+
+impl<'a,'b> Foo<'a,'b> {
+    // The number of errors is related to the way invariance works.
+    fn bar(self: Foo<'b,'a>) {}
+    //~^ ERROR mismatched types: expected `Foo<'a,'b>` but found `Foo<'b,'a>`
+    //~^^ ERROR mismatched types: expected `Foo<'a,'b>` but found `Foo<'b,'a>`
+    //~^^^ ERROR mismatched types: expected `Foo<'b,'a>` but found `Foo<'a,'b>`
+    //~^^^^ ERROR mismatched types: expected `Foo<'b,'a>` but found `Foo<'a,'b>`
+}
+
+fn main() {}
+
diff --git a/src/test/compile-fail/ufcs-explicit-self-bad.rs b/src/test/compile-fail/ufcs-explicit-self-bad.rs
new file mode 100644
index 00000000000..e5bad7e31b8
--- /dev/null
+++ b/src/test/compile-fail/ufcs-explicit-self-bad.rs
@@ -0,0 +1,49 @@
+// Copyright 2012 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::owned::Box;
+
+struct Foo {
+    f: int,
+}
+
+impl Foo {
+    fn foo(self: int, x: int) -> int {  //~ ERROR mismatched self type
+//~^ ERROR not a valid type for `self`
+        self.f + x
+    }
+}
+
+struct Bar<T> {
+    f: T,
+}
+
+impl<T> Bar<T> {
+    fn foo(self: Bar<int>, x: int) -> int { //~ ERROR mismatched self type
+//~^ ERROR not a valid type for `self`
+        x
+    }
+    fn bar(self: &Bar<uint>, x: int) -> int {   //~ ERROR mismatched self type
+//~^ ERROR not a valid type for `self`
+        x
+    }
+}
+
+fn main() {
+    let foo = box Foo {
+        f: 1,
+    };
+    println!("{}", foo.foo(2));
+    let bar = box Bar {
+        f: 1,
+    };
+    println!("{} {}", bar.foo(2), bar.bar(2));
+}
+
diff --git a/src/test/run-pass/ufcs-explicit-self.rs b/src/test/run-pass/ufcs-explicit-self.rs
new file mode 100644
index 00000000000..9ffb56c516a
--- /dev/null
+++ b/src/test/run-pass/ufcs-explicit-self.rs
@@ -0,0 +1,57 @@
+// Copyright 2012 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::owned::Box;
+
+struct Foo {
+    f: int,
+}
+
+impl Foo {
+    fn foo(self: Foo, x: int) -> int {
+        self.f + x
+    }
+    fn bar(self: &Foo, x: int) -> int {
+        self.f + x
+    }
+    fn baz(self: Box<Foo>, x: int) -> int {
+        self.f + x
+    }
+}
+
+struct Bar<T> {
+    f: T,
+}
+
+impl<T> Bar<T> {
+    fn foo(self: Bar<T>, x: int) -> int {
+        x
+    }
+    fn bar<'a>(self: &'a Bar<T>, x: int) -> int {
+        x
+    }
+    fn baz(self: Bar<T>, x: int) -> int {
+        x
+    }
+}
+
+fn main() {
+    let foo = box Foo {
+        f: 1,
+    };
+    println!("{} {} {}", foo.foo(2), foo.bar(2), foo.baz(2));
+    let bar = box Bar {
+        f: 1,
+    };
+    println!("{} {} {}", bar.foo(2), bar.bar(2), bar.baz(2));
+    let bar: Box<Bar<int>> = bar;
+    println!("{} {} {}", bar.foo(2), bar.bar(2), bar.baz(2));
+}
+