auto merge of #16377 : pcwalton/rust/associated-items, r=nikomatsakis

This is waiting on an RFC, but this basic functionality should be
straightforward. The implementation essentially desugars during type
collection and AST type conversion time into the parameter scheme we
have now.

r? @nikomatsakis 

67 files changed, 3031 insertions, 550 deletions

diff --git a/src/doc/rust.md b/src/doc/rust.md
index 345b7615168..5028f224475 100644
--- a/src/doc/rust.md
+++ b/src/doc/rust.md
@@ -2557,6 +2557,8 @@ The currently implemented features of the reference compiler are:
 
 * `tuple_indexing` - Allows use of tuple indexing (expressions like `expr.0`)
 
+* `associated_types` - Allows type aliases in traits. Experimental.
+
 If a feature is promoted to a language feature, then all existing programs will
 start to receive compilation warnings about #[feature] directives which enabled
 the new feature (because the directive is no longer necessary). However, if
diff --git a/src/jemalloc b/src/jemalloc
-Subproject 2dba541881fb8e35246d653bbe2e7c7088777a4
+Subproject aae04170ccbfeea620502106b581c3c216cd132
diff --git a/src/librustc/lint/builtin.rs b/src/librustc/lint/builtin.rs
index 836d355d55b..473c3935769 100644
--- a/src/librustc/lint/builtin.rs
+++ b/src/librustc/lint/builtin.rs
@@ -844,6 +844,17 @@ fn method_context(cx: &Context, m: &ast::Method) -> MethodContext {
                         }
                     }
                 }
+                ty::TypeTraitItem(typedef) => {
+                    match typedef.container {
+                        ty::TraitContainer(..) => TraitDefaultImpl,
+                        ty::ImplContainer(cid) => {
+                            match ty::impl_trait_ref(cx.tcx, cid) {
+                                Some(..) => TraitImpl,
+                                None => PlainImpl
+                            }
+                        }
+                    }
+                }
             }
         }
     }
@@ -1511,13 +1522,9 @@ impl LintPass for Stability {
                                 method_num: index,
                                 ..
                             }) => {
-                                match ty::trait_item(cx.tcx,
-                                                     trait_ref.def_id,
-                                                     index) {
-                                    ty::MethodTraitItem(method) => {
-                                        method.def_id
-                                    }
-                                }
+                                ty::trait_item(cx.tcx,
+                                               trait_ref.def_id,
+                                               index).def_id()
                             }
                         }
                     }
diff --git a/src/librustc/lint/context.rs b/src/librustc/lint/context.rs
index e39685705df..51852a347d1 100644
--- a/src/librustc/lint/context.rs
+++ b/src/librustc/lint/context.rs
@@ -25,6 +25,7 @@
 //! for all lint attributes.
 
 use middle::privacy::ExportedItems;
+use middle::subst;
 use middle::ty;
 use middle::typeck::astconv::AstConv;
 use middle::typeck::infer;
@@ -491,6 +492,26 @@ impl<'a, 'tcx> AstConv<'tcx> for Context<'a, 'tcx>{
     fn ty_infer(&self, _span: Span) -> ty::t {
         infer::new_infer_ctxt(self.tcx).next_ty_var()
     }
+
+    fn associated_types_of_trait_are_valid(&self, _: ty::t, _: ast::DefId)
+                                           -> bool {
+        // FIXME(pcwalton): This is wrong.
+        true
+    }
+
+    fn associated_type_binding(&self,
+                               _: Span,
+                               _: Option<ty::t>,
+                               trait_id: ast::DefId,
+                               associated_type_id: ast::DefId)
+                               -> ty::t {
+        // FIXME(pcwalton): This is wrong.
+        let trait_def = self.get_trait_def(trait_id);
+        let index = ty::associated_type_parameter_index(self.tcx,
+                                                        &*trait_def,
+                                                        associated_type_id);
+        ty::mk_param(self.tcx, subst::TypeSpace, index, associated_type_id)
+    }
 }
 
 impl<'a, 'tcx, 'v> Visitor<'v> for Context<'a, 'tcx> {
diff --git a/src/librustc/metadata/csearch.rs b/src/librustc/metadata/csearch.rs
index c27f1d9ed1f..c8ed926d6fe 100644
--- a/src/librustc/metadata/csearch.rs
+++ b/src/librustc/metadata/csearch.rs
@@ -349,3 +349,9 @@ pub fn get_stability(cstore: &cstore::CStore,
     let cdata = cstore.get_crate_data(def.krate);
     decoder::get_stability(&*cdata, def.node)
 }
+
+pub fn is_associated_type(cstore: &cstore::CStore, def: ast::DefId) -> bool {
+    let cdata = cstore.get_crate_data(def.krate);
+    decoder::is_associated_type(&*cdata, def.node)
+}
+
diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index 748e59b75ed..ac7f83cb385 100644
--- a/src/librustc/metadata/decoder.rs
+++ b/src/librustc/metadata/decoder.rs
@@ -23,7 +23,7 @@ use metadata::tydecode::{parse_ty_data, parse_region_data, parse_def_id,
                          parse_bare_fn_ty_data, parse_trait_ref_data};
 use middle::def;
 use middle::lang_items;
-use middle::resolve::TraitItemKind;
+use middle::resolve::{TraitItemKind, TypeTraitItemKind};
 use middle::subst;
 use middle::ty::{ImplContainer, TraitContainer};
 use middle::ty;
@@ -167,6 +167,8 @@ fn item_visibility(item: rbml::Doc) -> ast::Visibility {
 }
 
 fn item_sort(item: rbml::Doc) -> char {
+    // NB(pcwalton): The default of 'r' here is relied upon in
+    // `is_associated_type` below.
     let mut ret = 'r';
     reader::tagged_docs(item, tag_item_trait_item_sort, |doc| {
         ret = doc.as_str_slice().as_bytes()[0] as char;
@@ -714,6 +716,7 @@ pub fn get_impl_items(cdata: Cmd, impl_id: ast::NodeId)
         let def_id = item_def_id(doc, cdata);
         match item_sort(doc) {
             'r' | 'p' => impl_items.push(ty::MethodTraitItemId(def_id)),
+            't' => impl_items.push(ty::TypeTraitItemId(def_id)),
             _ => fail!("unknown impl item sort"),
         }
         true
@@ -733,6 +736,7 @@ pub fn get_trait_item_name_and_kind(intr: Rc<IdentInterner>,
             let explicit_self = get_explicit_self(doc);
             (name, TraitItemKind::from_explicit_self_category(explicit_self))
         }
+        't' => (name, TypeTraitItemKind),
         c => {
             fail!("get_trait_item_name_and_kind(): unknown trait item kind \
                    in metadata: `{}`", c)
@@ -758,13 +762,13 @@ pub fn get_impl_or_trait_item(intr: Rc<IdentInterner>,
     };
 
     let name = item_name(&*intr, method_doc);
+    let vis = item_visibility(method_doc);
 
     match item_sort(method_doc) {
         'r' | 'p' => {
             let generics = doc_generics(method_doc, tcx, cdata,
                                         tag_method_ty_generics);
             let fty = doc_method_fty(method_doc, tcx, cdata);
-            let vis = item_visibility(method_doc);
             let explicit_self = get_explicit_self(method_doc);
             let provided_source = get_provided_source(method_doc, cdata);
 
@@ -777,6 +781,14 @@ pub fn get_impl_or_trait_item(intr: Rc<IdentInterner>,
                                                         container,
                                                         provided_source)))
         }
+        't' => {
+            ty::TypeTraitItem(Rc::new(ty::AssociatedType {
+                ident: name,
+                vis: vis,
+                def_id: def_id,
+                container: container,
+            }))
+        }
         _ => fail!("unknown impl/trait item sort"),
     }
 }
@@ -790,6 +802,7 @@ pub fn get_trait_item_def_ids(cdata: Cmd, id: ast::NodeId)
         let def_id = item_def_id(mth, cdata);
         match item_sort(mth) {
             'r' | 'p' => result.push(ty::MethodTraitItemId(def_id)),
+            't' => result.push(ty::TypeTraitItemId(def_id)),
             _ => fail!("unknown trait item sort"),
         }
         true
@@ -827,6 +840,7 @@ pub fn get_provided_trait_methods(intr: Rc<IdentInterner>,
                 ty::MethodTraitItem(ref method) => {
                     result.push((*method).clone())
                 }
+                ty::TypeTraitItem(_) => {}
             }
         }
         true
@@ -1394,3 +1408,12 @@ fn doc_generics(base_doc: rbml::Doc,
 
     ty::Generics { types: types, regions: regions }
 }
+
+pub fn is_associated_type(cdata: Cmd, id: ast::NodeId) -> bool {
+    let items = reader::get_doc(rbml::Doc::new(cdata.data()), tag_items);
+    match maybe_find_item(id, items) {
+        None => false,
+        Some(item) => item_sort(item) == 't',
+    }
+}
+
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index c4f7c2db6a2..d27a0d27c7b 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -416,6 +416,7 @@ fn encode_reexported_static_base_methods(ecx: &EncodeContext,
                                                                 m.ident);
                             }
                         }
+                        ty::TypeTraitItem(_) => {}
                     }
                 }
             }
@@ -887,7 +888,44 @@ fn encode_info_for_method(ecx: &EncodeContext,
             }
             encode_method_argument_names(rbml_w, ast_method.pe_fn_decl());
         }
+        Some(_) | None => {}
+    }
+
+    rbml_w.end_tag();
+}
+
+fn encode_info_for_associated_type(ecx: &EncodeContext,
+                                   rbml_w: &mut Encoder,
+                                   associated_type: &ty::AssociatedType,
+                                   impl_path: PathElems,
+                                   parent_id: NodeId,
+                                   typedef_opt: Option<P<ast::Typedef>>) {
+    debug!("encode_info_for_associated_type({},{})",
+           associated_type.def_id,
+           token::get_ident(associated_type.ident));
+
+    rbml_w.start_tag(tag_items_data_item);
+
+    encode_def_id(rbml_w, associated_type.def_id);
+    encode_name(rbml_w, associated_type.ident.name);
+    encode_visibility(rbml_w, associated_type.vis);
+    encode_family(rbml_w, 'y');
+    encode_parent_item(rbml_w, local_def(parent_id));
+    encode_item_sort(rbml_w, 'r');
+
+    let stab = stability::lookup(ecx.tcx, associated_type.def_id);
+    encode_stability(rbml_w, stab);
+
+    let elem = ast_map::PathName(associated_type.ident.name);
+    encode_path(rbml_w, impl_path.chain(Some(elem).move_iter()));
+
+    match typedef_opt {
         None => {}
+        Some(typedef) => {
+            encode_attributes(rbml_w, typedef.attrs.as_slice());
+            encode_type(ecx, rbml_w, ty::node_id_to_type(ecx.tcx,
+                                                         typedef.id));
+        }
     }
 
     rbml_w.end_tag();
@@ -1198,6 +1236,10 @@ fn encode_info_for_item(ecx: &EncodeContext,
                     encode_def_id(rbml_w, item_def_id);
                     encode_item_sort(rbml_w, 'r');
                 }
+                ty::TypeTraitItemId(item_def_id) => {
+                    encode_def_id(rbml_w, item_def_id);
+                    encode_item_sort(rbml_w, 't');
+                }
             }
             rbml_w.end_tag();
         }
@@ -1227,10 +1269,46 @@ fn encode_info_for_item(ecx: &EncodeContext,
                 pos: rbml_w.writer.tell().unwrap(),
             });
 
-            let ty::MethodTraitItem(method_type) =
+            let trait_item_type =
                 ty::impl_or_trait_item(tcx, trait_item_def_id.def_id());
-            encode_info_for_method(ecx, rbml_w, &*method_type, path.clone(),
-                                   false, item.id, ast_item)
+            match (trait_item_type, ast_item) {
+                (ty::MethodTraitItem(ref method_type),
+                 Some(&ast::MethodImplItem(_))) => {
+                    encode_info_for_method(ecx,
+                                           rbml_w,
+                                           &**method_type,
+                                           path.clone(),
+                                           false,
+                                           item.id,
+                                           ast_item)
+                }
+                (ty::MethodTraitItem(ref method_type), _) => {
+                    encode_info_for_method(ecx,
+                                           rbml_w,
+                                           &**method_type,
+                                           path.clone(),
+                                           false,
+                                           item.id,
+                                           None)
+                }
+                (ty::TypeTraitItem(ref associated_type),
+                 Some(&ast::TypeImplItem(ref typedef))) => {
+                    encode_info_for_associated_type(ecx,
+                                                    rbml_w,
+                                                    &**associated_type,
+                                                    path.clone(),
+                                                    item.id,
+                                                    Some((*typedef).clone()))
+                }
+                (ty::TypeTraitItem(ref associated_type), _) => {
+                    encode_info_for_associated_type(ecx,
+                                                    rbml_w,
+                                                    &**associated_type,
+                                                    path.clone(),
+                                                    item.id,
+                                                    None)
+                }
+            }
         }
       }
       ItemTrait(_, _, _, ref ms) => {
@@ -1253,6 +1331,10 @@ fn encode_info_for_item(ecx: &EncodeContext,
                     encode_def_id(rbml_w, method_def_id);
                     encode_item_sort(rbml_w, 'r');
                 }
+                ty::TypeTraitItemId(type_def_id) => {
+                    encode_def_id(rbml_w, type_def_id);
+                    encode_item_sort(rbml_w, 't');
+                }
             }
             rbml_w.end_tag();
 
@@ -1281,17 +1363,19 @@ fn encode_info_for_item(ecx: &EncodeContext,
 
             rbml_w.start_tag(tag_items_data_item);
 
+            encode_parent_item(rbml_w, def_id);
+
+            let stab = stability::lookup(tcx, item_def_id.def_id());
+            encode_stability(rbml_w, stab);
+
             let trait_item_type =
                 ty::impl_or_trait_item(tcx, item_def_id.def_id());
+            let is_nonstatic_method;
             match trait_item_type {
-                 ty::MethodTraitItem(method_ty) => {
+                ty::MethodTraitItem(method_ty) => {
                     let method_def_id = item_def_id.def_id();
 
                     encode_method_ty_fields(ecx, rbml_w, &*method_ty);
-                    encode_parent_item(rbml_w, def_id);
-
-                    let stab = stability::lookup(tcx, method_def_id);
-                    encode_stability(rbml_w, stab);
 
                     let elem = ast_map::PathName(method_ty.ident.name);
                     encode_path(rbml_w,
@@ -1315,33 +1399,53 @@ fn encode_info_for_item(ecx: &EncodeContext,
                         }
                     }
 
-                    let trait_item = ms.get(i);
-                    match *trait_item {
-                        RequiredMethod(ref tm) => {
-                            encode_attributes(rbml_w, tm.attrs.as_slice());
-                            encode_item_sort(rbml_w, 'r');
-                            encode_parent_sort(rbml_w, 't');
-                            encode_method_argument_names(rbml_w, &*tm.decl);
-                        }
+                    is_nonstatic_method = method_ty.explicit_self !=
+                        ty::StaticExplicitSelfCategory;
+                }
+                ty::TypeTraitItem(associated_type) => {
+                    let elem = ast_map::PathName(associated_type.ident.name);
+                    encode_path(rbml_w,
+                                path.clone().chain(Some(elem).move_iter()));
 
-                        ProvidedMethod(ref m) => {
-                            encode_attributes(rbml_w, m.attrs.as_slice());
-                            // If this is a static method, we've already
-                            // encoded this.
-                            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(rbml_w, ecx, &pty);
-                            }
-                            encode_item_sort(rbml_w, 'p');
-                            encode_parent_sort(rbml_w, 't');
-                            encode_inlined_item(ecx, rbml_w,
-                                                IITraitItemRef(def_id, trait_item));
-                            encode_method_argument_names(rbml_w, &*m.pe_fn_decl());
-                        }
+                    encode_family(rbml_w, 'y');
+
+                    is_nonstatic_method = false;
+                }
+            }
+
+            encode_parent_sort(rbml_w, 't');
+
+            let trait_item = ms.get(i);
+            match ms.get(i) {
+                &RequiredMethod(ref tm) => {
+                    encode_attributes(rbml_w, tm.attrs.as_slice());
+                    encode_item_sort(rbml_w, 'r');
+                    encode_method_argument_names(rbml_w, &*tm.decl);
+                }
+
+                &ProvidedMethod(ref m) => {
+                    encode_attributes(rbml_w, m.attrs.as_slice());
+                    // If this is a static method, we've already
+                    // encoded this.
+                    if is_nonstatic_method {
+                        // FIXME: I feel like there is something funny
+                        // going on.
+                        let pty = ty::lookup_item_type(tcx,
+                                                       item_def_id.def_id());
+                        encode_bounds_and_type(rbml_w, ecx, &pty);
                     }
+                    encode_item_sort(rbml_w, 'p');
+                    encode_inlined_item(ecx,
+                                        rbml_w,
+                                        IITraitItemRef(def_id, trait_item));
+                    encode_method_argument_names(rbml_w,
+                                                 &*m.pe_fn_decl());
+                }
+
+                &TypeTraitItem(ref associated_type) => {
+                    encode_attributes(rbml_w,
+                                      associated_type.attrs.as_slice());
+                    encode_item_sort(rbml_w, 't');
                 }
             }
 
diff --git a/src/librustc/metadata/tydecode.rs b/src/librustc/metadata/tydecode.rs
index 0e888b39b85..d319559044c 100644
--- a/src/librustc/metadata/tydecode.rs
+++ b/src/librustc/metadata/tydecode.rs
@@ -630,6 +630,10 @@ fn parse_type_param_def(st: &mut PState, conv: conv_did) -> ty::TypeParameterDef
     assert_eq!(next(st), '|');
     let index = parse_uint(st);
     assert_eq!(next(st), '|');
+    let associated_with = parse_opt(st, |st| {
+        parse_def(st, NominalType, |x,y| conv(x,y))
+    });
+    assert_eq!(next(st), '|');
     let bounds = parse_bounds(st, |x,y| conv(x,y));
     let default = parse_opt(st, |st| parse_ty(st, |x,y| conv(x,y)));
 
@@ -638,6 +642,7 @@ fn parse_type_param_def(st: &mut PState, conv: conv_did) -> ty::TypeParameterDef
         def_id: def_id,
         space: space,
         index: index,
+        associated_with: associated_with,
         bounds: bounds,
         default: default
     }
diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs
index 3ef1d15cf56..fd3e4fe6738 100644
--- a/src/librustc/metadata/tyencode.rs
+++ b/src/librustc/metadata/tyencode.rs
@@ -383,6 +383,8 @@ pub fn enc_type_param_def(w: &mut SeekableMemWriter, cx: &ctxt, v: &ty::TypePara
     mywrite!(w, "{}:{}|{}|{}|",
              token::get_ident(v.ident), (cx.ds)(v.def_id),
              v.space.to_uint(), v.index);
+    enc_opt(w, v.associated_with, |w, did| mywrite!(w, "{}", (cx.ds)(did)));
+    mywrite!(w, "|");
     enc_bounds(w, cx, &v.bounds);
     enc_opt(w, v.default, |w, t| enc_ty(w, cx, t));
 }
diff --git a/src/librustc/middle/astencode.rs b/src/librustc/middle/astencode.rs
index 880445ff38d..399313ddd8e 100644
--- a/src/librustc/middle/astencode.rs
+++ b/src/librustc/middle/astencode.rs
@@ -83,7 +83,9 @@ pub fn encode_inlined_item(ecx: &e::EncodeContext,
         e::IIForeignRef(i) => i.id,
         e::IITraitItemRef(_, &ast::ProvidedMethod(ref m)) => m.id,
         e::IITraitItemRef(_, &ast::RequiredMethod(ref m)) => m.id,
-        e::IIImplItemRef(_, &ast::MethodImplItem(ref m)) => m.id
+        e::IITraitItemRef(_, &ast::TypeTraitItem(ref ti)) => ti.id,
+        e::IIImplItemRef(_, &ast::MethodImplItem(ref m)) => m.id,
+        e::IIImplItemRef(_, &ast::TypeImplItem(ref ti)) => ti.id,
     };
     debug!("> Encoding inlined item: {} ({})",
            ecx.tcx.map.path_to_string(id),
@@ -155,12 +157,14 @@ pub fn decode_inlined_item<'tcx>(cdata: &cstore::crate_metadata,
             ast::IITraitItem(_, ref ti) => {
                 match *ti {
                     ast::ProvidedMethod(ref m) => m.pe_ident(),
-                    ast::RequiredMethod(ref ty_m) => ty_m.ident
+                    ast::RequiredMethod(ref ty_m) => ty_m.ident,
+                    ast::TypeTraitItem(ref ti) => ti.ident,
                 }
             },
             ast::IIImplItem(_, ref m) => {
                 match *m {
-                    ast::MethodImplItem(ref m) => m.pe_ident()
+                    ast::MethodImplItem(ref m) => m.pe_ident(),
+                    ast::TypeImplItem(ref ti) => ti.ident,
                 }
             }
         };
@@ -392,6 +396,12 @@ fn simplify_ast(ii: e::InlinedItemRef) -> ast::InlinedItem {
                     ast::RequiredMethod(
                         fold::noop_fold_type_method(ty_m.clone(), &mut fld))
                 }
+                ast::TypeTraitItem(ref associated_type) => {
+                    ast::TypeTraitItem(
+                        P(fold::noop_fold_associated_type(
+                            (**associated_type).clone(),
+                            &mut fld)))
+                }
             })
         }
         e::IIImplItemRef(d, m) => {
@@ -402,6 +412,10 @@ fn simplify_ast(ii: e::InlinedItemRef) -> ast::InlinedItem {
                             .expect_one("noop_fold_method must produce \
                                          exactly one method"))
                 }
+                ast::TypeImplItem(ref td) => {
+                    ast::TypeImplItem(
+                        P(fold::noop_fold_typedef((**td).clone(), &mut fld)))
+                }
             })
         }
         e::IIForeignRef(i) => {
@@ -455,6 +469,7 @@ impl tr for def::Def {
           },
           def::DefTrait(did) => def::DefTrait(did.tr(dcx)),
           def::DefTy(did, is_enum) => def::DefTy(did.tr(dcx), is_enum),
+          def::DefAssociatedTy(did) => def::DefAssociatedTy(did.tr(dcx)),
           def::DefPrimTy(p) => def::DefPrimTy(p),
           def::DefTyParam(s, did, v) => def::DefTyParam(s, did.tr(dcx), v),
           def::DefBinding(nid, bm) => def::DefBinding(dcx.tr_id(nid), bm),
diff --git a/src/librustc/middle/dead.rs b/src/librustc/middle/dead.rs
index a9c0b877d55..b75d61100ec 100644
--- a/src/librustc/middle/dead.rs
+++ b/src/librustc/middle/dead.rs
@@ -118,6 +118,9 @@ impl<'a, 'tcx> MarkSymbolVisitor<'a, 'tcx> {
                             ty::MethodTraitItem(method) => {
                                 self.check_def_id(method.def_id);
                             }
+                            ty::TypeTraitItem(typedef) => {
+                                self.check_def_id(typedef.def_id);
+                            }
                         }
                     }
                 }
@@ -226,6 +229,7 @@ impl<'a, 'tcx> MarkSymbolVisitor<'a, 'tcx> {
                     ast::MethodImplItem(ref method) => {
                         visit::walk_block(self, method.pe_body());
                     }
+                    ast::TypeImplItem(_) => {}
                 }
             }
             ast_map::NodeForeignItem(foreign_item) => {
@@ -341,6 +345,7 @@ impl<'v> Visitor<'v> for LifeSeeder {
                         ast::MethodImplItem(ref method) => {
                             self.worklist.push(method.id);
                         }
+                        ast::TypeImplItem(_) => {}
                     }
                 }
             }
@@ -544,7 +549,8 @@ impl<'a, 'tcx, 'v> Visitor<'v> for DeadVisitor<'a, 'tcx> {
             ast::ProvidedMethod(ref method) => {
                 visit::walk_block(self, &*method.pe_body())
             }
-            ast::RequiredMethod(_) => ()
+            ast::RequiredMethod(_) => {}
+            ast::TypeTraitItem(_) => {}
         }
     }
 }
diff --git a/src/librustc/middle/def.rs b/src/librustc/middle/def.rs
index 70a9b6c5337..ae45d827def 100644
--- a/src/librustc/middle/def.rs
+++ b/src/librustc/middle/def.rs
@@ -26,6 +26,7 @@ pub enum Def {
     DefLocal(ast::NodeId, ast::BindingMode),
     DefVariant(ast::DefId /* enum */, ast::DefId /* variant */, bool /* is_structure */),
     DefTy(ast::DefId, bool /* is_enum */),
+    DefAssociatedTy(ast::DefId),
     DefTrait(ast::DefId),
     DefPrimTy(ast::PrimTy),
     DefTyParam(ParamSpace, ast::DefId, uint),
@@ -62,8 +63,9 @@ impl Def {
         match *self {
             DefFn(id, _) | DefStaticMethod(id, _, _) | DefMod(id) |
             DefForeignMod(id) | DefStatic(id, _) |
-            DefVariant(_, id, _) | DefTy(id, _) | DefTyParam(_, id, _) |
-            DefUse(id) | DefStruct(id) | DefTrait(id) | DefMethod(id, _) => {
+            DefVariant(_, id, _) | DefTy(id, _) | DefAssociatedTy(id) |
+            DefTyParam(_, id, _) | DefUse(id) | DefStruct(id) | DefTrait(id) |
+            DefMethod(id, _) => {
                 id
             }
             DefArg(id, _) |
@@ -90,3 +92,4 @@ impl Def {
         }
     }
 }
+
diff --git a/src/librustc/middle/expr_use_visitor.rs b/src/librustc/middle/expr_use_visitor.rs
index d6c11caefe8..c8c5284022d 100644
--- a/src/librustc/middle/expr_use_visitor.rs
+++ b/src/librustc/middle/expr_use_visitor.rs
@@ -134,6 +134,9 @@ impl OverloadedCallType {
             ty::MethodTraitItem(ref method_descriptor) => {
                 (*method_descriptor).clone()
             }
+            ty::TypeTraitItem(_) => {
+                tcx.sess.bug("overloaded call method wasn't in method map")
+            }
         };
         let impl_id = match method_descriptor.container {
             ty::TraitContainer(_) => {
diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index 4f9cc9c080f..17d941b5958 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -319,7 +319,9 @@ impl MutabilityCategory {
             def::DefTy(..) | def::DefTrait(..) | def::DefPrimTy(..) |
             def::DefTyParam(..) | def::DefUse(..) | def::DefStruct(..) |
             def::DefTyParamBinder(..) | def::DefRegion(..) | def::DefLabel(..) |
-            def::DefMethod(..) => fail!("no MutabilityCategory for def: {}", *def),
+            def::DefMethod(..) | def::DefAssociatedTy(..) => {
+                fail!("no MutabilityCategory for def: {}", *def)
+            }
 
             def::DefStatic(_, false) => McImmutable,
             def::DefStatic(_, true) => McDeclared,
@@ -533,7 +535,8 @@ impl<'t,'tcx,TYPER:Typer<'tcx>> MemCategorizationContext<'t,TYPER> {
           def::DefMod(_) | def::DefForeignMod(_) | def::DefUse(_) |
           def::DefTrait(_) | def::DefTy(..) | def::DefPrimTy(_) |
           def::DefTyParam(..) | def::DefTyParamBinder(..) | def::DefRegion(_) |
-          def::DefLabel(_) | def::DefSelfTy(..) | def::DefMethod(..) => {
+          def::DefLabel(_) | def::DefSelfTy(..) | def::DefMethod(..) |
+          def::DefAssociatedTy(..) => {
               Ok(Rc::new(cmt_ {
                   id:id,
                   span:span,
diff --git a/src/librustc/middle/privacy.rs b/src/librustc/middle/privacy.rs
index 0eb684fe18e..8aac96a5410 100644
--- a/src/librustc/middle/privacy.rs
+++ b/src/librustc/middle/privacy.rs
@@ -82,8 +82,13 @@ impl<'v> Visitor<'v> for ParentVisitor {
             ast::ItemTrait(_, _, _, ref methods) if item.vis != ast::Public => {
                 for m in methods.iter() {
                     match *m {
-                        ast::ProvidedMethod(ref m) => self.parents.insert(m.id, item.id),
-                        ast::RequiredMethod(ref m) => self.parents.insert(m.id, item.id),
+                        ast::ProvidedMethod(ref m) => {
+                            self.parents.insert(m.id, item.id);
+                        }
+                        ast::RequiredMethod(ref m) => {
+                            self.parents.insert(m.id, item.id);
+                        }
+                        ast::TypeTraitItem(_) => {}
                     };
                 }
             }
@@ -272,6 +277,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for EmbargoVisitor<'a, 'tcx> {
                                     self.exported_items.insert(method.id);
                                 }
                             }
+                            ast::TypeImplItem(_) => {}
                         }
                     }
                 }
@@ -290,6 +296,10 @@ impl<'a, 'tcx, 'v> Visitor<'v> for EmbargoVisitor<'a, 'tcx> {
                             debug!("required {}", m.id);
                             self.exported_items.insert(m.id);
                         }
+                        ast::TypeTraitItem(ref t) => {
+                            debug!("typedef {}", t.id);
+                            self.exported_items.insert(t.id);
+                        }
                     }
                 }
             }
@@ -419,6 +429,31 @@ impl<'a, 'tcx> PrivacyVisitor<'a, 'tcx> {
                         }
                     }
                 }
+                Some(&ty::TypeTraitItem(ref typedef)) => {
+                    match typedef.container {
+                        ty::TraitContainer(id) => {
+                            debug!("privacy - recursing on trait {:?}", id);
+                            self.def_privacy(id)
+                        }
+                        ty::ImplContainer(id) => {
+                            match ty::impl_trait_ref(self.tcx, id) {
+                                Some(t) => {
+                                    debug!("privacy - impl of trait {:?}", id);
+                                    self.def_privacy(t.def_id)
+                                }
+                                None => {
+                                    debug!("privacy - found a typedef {:?}",
+                                            typedef.vis);
+                                    if typedef.vis == ast::Public {
+                                        Allowable
+                                    } else {
+                                        ExternallyDenied
+                                    }
+                                }
+                            }
+                        }
+                    }
+                }
                 None => {
                     debug!("privacy - nope, not even a method");
                     ExternallyDenied
@@ -469,6 +504,7 @@ impl<'a, 'tcx> PrivacyVisitor<'a, 'tcx> {
                                 _ => m.pe_vis()
                             }
                         }
+                        ast::TypeImplItem(_) => return Allowable,
                     }
                 }
                 Some(ast_map::NodeTraitItem(_)) => {
@@ -670,6 +706,7 @@ impl<'a, 'tcx> PrivacyVisitor<'a, 'tcx> {
             ty::MethodTraitItem(method_type) => {
                 method_type.provided_source.unwrap_or(method_id)
             }
+            ty::TypeTraitItem(_) => method_id,
         };
 
         let string = token::get_ident(name);
@@ -1110,6 +1147,7 @@ impl<'a, 'tcx> SanePrivacyVisitor<'a, 'tcx> {
                         ast::MethodImplItem(ref m) => {
                             check_inherited(m.span, m.pe_vis(), "");
                         }
+                        ast::TypeImplItem(_) => {}
                     }
                 }
             }
@@ -1149,6 +1187,7 @@ impl<'a, 'tcx> SanePrivacyVisitor<'a, 'tcx> {
                             check_inherited(m.span, m.vis,
                                             "unnecessary visibility");
                         }
+                        ast::TypeTraitItem(_) => {}
                     }
                 }
             }
@@ -1184,6 +1223,7 @@ impl<'a, 'tcx> SanePrivacyVisitor<'a, 'tcx> {
                         ast::MethodImplItem(ref m) => {
                             check_inherited(tcx, m.span, m.pe_vis());
                         }
+                        ast::TypeImplItem(_) => {}
                     }
                 }
             }
@@ -1211,6 +1251,7 @@ impl<'a, 'tcx> SanePrivacyVisitor<'a, 'tcx> {
                         ast::RequiredMethod(..) => {}
                         ast::ProvidedMethod(ref m) => check_inherited(tcx, m.span,
                                                                 m.pe_vis()),
+                        ast::TypeTraitItem(_) => {}
                     }
                 }
             }
@@ -1351,6 +1392,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for VisiblePrivateTypesVisitor<'a, 'tcx> {
                                       ast::MethodImplItem(ref m) => {
                                           self.exported_items.contains(&m.id)
                                       }
+                                      ast::TypeImplItem(_) => false,
                                   }
                               });
 
@@ -1367,6 +1409,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for VisiblePrivateTypesVisitor<'a, 'tcx> {
                                     ast::MethodImplItem(ref method) => {
                                         visit::walk_method_helper(self, &**method)
                                     }
+                                    ast::TypeImplItem(_) => {}
                                 }
                             }
                         }
@@ -1401,6 +1444,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for VisiblePrivateTypesVisitor<'a, 'tcx> {
                                     visit::walk_method_helper(self, &**method);
                                 }
                             }
+                            ast::TypeImplItem(_) => {}
                         }
                     }
                     if found_pub_static {
diff --git a/src/librustc/middle/reachable.rs b/src/librustc/middle/reachable.rs
index 630b65f5278..555a033a568 100644
--- a/src/librustc/middle/reachable.rs
+++ b/src/librustc/middle/reachable.rs
@@ -197,6 +197,7 @@ impl<'a, 'tcx> ReachableContext<'a, 'tcx> {
                 match *trait_method {
                     ast::RequiredMethod(_) => false,
                     ast::ProvidedMethod(_) => true,
+                    ast::TypeTraitItem(_) => false,
                 }
             }
             Some(ast_map::NodeImplItem(impl_item)) => {
@@ -225,6 +226,7 @@ impl<'a, 'tcx> ReachableContext<'a, 'tcx> {
                             }
                         }
                     }
+                    ast::TypeImplItem(_) => false,
                 }
             }
             Some(_) => false,
@@ -327,8 +329,9 @@ impl<'a, 'tcx> ReachableContext<'a, 'tcx> {
                         // Keep going, nothing to get exported
                     }
                     ast::ProvidedMethod(ref method) => {
-                        visit::walk_block(self, &*method.pe_body())
+                        visit::walk_block(self, &*method.pe_body());
                     }
+                    ast::TypeTraitItem(_) => {}
                 }
             }
             ast_map::NodeImplItem(impl_item) => {
@@ -339,6 +342,7 @@ impl<'a, 'tcx> ReachableContext<'a, 'tcx> {
                             visit::walk_block(self, method.pe_body())
                         }
                     }
+                    ast::TypeImplItem(_) => {}
                 }
             }
             // Nothing to recurse on for these
diff --git a/src/librustc/middle/resolve.rs b/src/librustc/middle/resolve.rs
index 861ac2ffe60..6fa33f4b5aa 100644
--- a/src/librustc/middle/resolve.rs
+++ b/src/librustc/middle/resolve.rs
@@ -37,13 +37,15 @@ use syntax::ast::{RegionTyParamBound, StmtDecl, StructField};
 use syntax::ast::{StructVariantKind, TraitRef, TraitTyParamBound};
 use syntax::ast::{TupleVariantKind, Ty, TyBool, TyChar, TyClosure, TyF32};
 use syntax::ast::{TyF64, TyFloat, TyI, TyI8, TyI16, TyI32, TyI64, TyInt};
-use syntax::ast::{TyParam, TyParamBound, TyPath, TyPtr, TyProc, TyRptr};
-use syntax::ast::{TyStr, TyU, TyU8, TyU16, TyU32, TyU64, TyUint};
-use syntax::ast::{UnboxedFnTyParamBound, UnnamedField, UnsafeFn, Variant};
-use syntax::ast::{ViewItem, ViewItemExternCrate, ViewItemUse, ViewPathGlob};
-use syntax::ast::{ViewPathList, ViewPathSimple, Visibility};
+use syntax::ast::{TyParam, TyParamBound, TyPath, TyPtr, TyProc, TyQPath};
+use syntax::ast::{TyRptr, TyStr, TyU, TyU8, TyU16, TyU32, TyU64, TyUint};
+use syntax::ast::{TypeImplItem, UnboxedFnTyParamBound, UnnamedField};
+use syntax::ast::{UnsafeFn, Variant, ViewItem, ViewItemExternCrate};
+use syntax::ast::{ViewItemUse, ViewPathGlob, ViewPathList, ViewPathSimple};
+use syntax::ast::{Visibility};
 use syntax::ast;
 use syntax::ast_util::{PostExpansionMethod, local_def, walk_pat};
+use syntax::ast_util;
 use syntax::attr::AttrMetaMethods;
 use syntax::ext::mtwt;
 use syntax::parse::token::special_names;
@@ -313,6 +315,7 @@ enum ModulePrefixResult {
 pub enum TraitItemKind {
     NonstaticMethodTraitItemKind,
     StaticMethodTraitItemKind,
+    TypeTraitItemKind,
 }
 
 impl TraitItemKind {
@@ -1393,6 +1396,24 @@ impl<'a> Resolver<'a> {
                                         method.span,
                                         is_public);
                                 }
+                                TypeImplItem(ref typedef) => {
+                                    // Add the typedef to the module.
+                                    let ident = typedef.ident;
+                                    let typedef_name_bindings =
+                                        self.add_child(
+                                            ident,
+                                            new_parent.clone(),
+                                            ForbidDuplicateTypesAndModules,
+                                            typedef.span);
+                                    let def = DefAssociatedTy(local_def(
+                                            typedef.id));
+                                    let is_public = typedef.vis ==
+                                        ast::Public;
+                                    typedef_name_bindings.define_type(
+                                        def,
+                                        typedef.span,
+                                        is_public);
+                                }
                             }
                         }
                     }
@@ -1432,42 +1453,66 @@ impl<'a> Resolver<'a> {
 
                 // Add the names of all the methods to the trait info.
                 for method in methods.iter() {
-                    let (m_id, m_ident, m_fn_style, m_self, m_span) = match *method {
-                        ast::RequiredMethod(ref m) => {
-                            (m.id, m.ident, m.fn_style, &m.explicit_self, m.span)
-                        }
-                        ast::ProvidedMethod(ref m) => {
-                            (m.id, m.pe_ident(), m.pe_fn_style(), m.pe_explicit_self(), m.span)
-                        }
-                    };
+                    let (ident, kind) = match *method {
+                        ast::RequiredMethod(_) |
+                        ast::ProvidedMethod(_) => {
+                            let ty_m =
+                                ast_util::trait_item_to_ty_method(method);
+
+                            let ident = ty_m.ident;
+
+                            // Add it as a name in the trait module.
+                            let (def, static_flag) = match ty_m.explicit_self
+                                                               .node {
+                                SelfStatic => {
+                                    // Static methods become
+                                    // `def_static_method`s.
+                                    (DefStaticMethod(
+                                            local_def(ty_m.id),
+                                            FromTrait(local_def(item.id)),
+                                            ty_m.fn_style),
+                                     StaticMethodTraitItemKind)
+                                }
+                                _ => {
+                                    // Non-static methods become
+                                    // `def_method`s.
+                                    (DefMethod(local_def(ty_m.id),
+                                               Some(local_def(item.id))),
+                                     NonstaticMethodTraitItemKind)
+                                }
+                            };
 
-                    // Add it as a name in the trait module.
-                    let (def, static_flag) = match m_self.node {
-                        SelfStatic => {
-                            // Static methods become `def_static_method`s.
-                            (DefStaticMethod(local_def(m_id),
-                                              FromTrait(local_def(item.id)),
-                                              m_fn_style),
-                             StaticMethodTraitItemKind)
+                            let method_name_bindings =
+                                self.add_child(ident,
+                                               module_parent.clone(),
+                                               ForbidDuplicateTypesAndValues,
+                                               ty_m.span);
+                            method_name_bindings.define_value(def,
+                                                              ty_m.span,
+                                                              true);
+
+                            (ident, static_flag)
                         }
-                        _ => {
-                            // Non-static methods become `def_method`s.
-                            (DefMethod(local_def(m_id),
-                                       Some(local_def(item.id))),
-                             NonstaticMethodTraitItemKind)
+                        ast::TypeTraitItem(ref associated_type) => {
+                            let def = DefAssociatedTy(local_def(
+                                    associated_type.id));
+
+                            let name_bindings =
+                                self.add_child(associated_type.ident,
+                                               module_parent.clone(),
+                                               ForbidDuplicateTypesAndValues,
+                                               associated_type.span);
+                            name_bindings.define_type(def,
+                                                      associated_type.span,
+                                                      true);
+
+                            (associated_type.ident, TypeTraitItemKind)
                         }
                     };
 
-                    let method_name_bindings =
-                        self.add_child(m_ident,
-                                       module_parent.clone(),
-                                       ForbidDuplicateValues,
-                                       m_span);
-                    method_name_bindings.define_value(def, m_span, true);
-
                     self.trait_item_map
                         .borrow_mut()
-                        .insert((m_ident.name, def_id), static_flag);
+                        .insert((ident.name, def_id), kind);
                 }
 
                 name_bindings.define_type(DefTrait(def_id), sp, is_public);
@@ -1823,7 +1868,7 @@ impl<'a> Resolver<'a> {
                                                   is_public,
                                                   DUMMY_SP)
           }
-          DefTy(..) => {
+          DefTy(..) | DefAssociatedTy(..) => {
               debug!("(building reduced graph for external \
                       crate) building type {}", final_ident);
 
@@ -4065,6 +4110,9 @@ impl<'a> Resolver<'a> {
                                                                 ProvidedMethod(m.id)),
                                                   &**m)
                           }
+                          ast::TypeTraitItem(_) => {
+                              visit::walk_trait_item(this, method);
+                          }
                         }
                     }
                 });
@@ -4509,6 +4557,14 @@ impl<'a> Resolver<'a> {
                                                   ProvidedMethod(method.id)),
                                     &**method);
                             }
+                            TypeImplItem(ref typedef) => {
+                                // If this is a trait impl, ensure the method
+                                // exists in trait
+                                this.check_trait_item(typedef.ident,
+                                                      typedef.span);
+
+                                this.resolve_type(&*typedef.typ);
+                            }
                         }
                     }
                 });
@@ -4745,9 +4801,73 @@ impl<'a> Resolver<'a> {
                 });
             }
 
+            TyQPath(ref qpath) => {
+                self.resolve_type(&*qpath.for_type);
+
+                let current_module = self.current_module.clone();
+                let module_path_idents: Vec<_> =
+                    qpath.trait_name
+                         .segments
+                         .iter()
+                         .map(|ps| ps.identifier)
+                         .collect();
+                match self.resolve_module_path(
+                        current_module,
+                        module_path_idents.as_slice(),
+                        UseLexicalScope,
+                        qpath.trait_name.span,
+                        PathSearch) {
+                    Success((ref module, _)) if module.kind.get() ==
+                            TraitModuleKind => {
+                        match self.resolve_definition_of_name_in_module(
+                                (*module).clone(),
+                                qpath.item_name.name,
+                                TypeNS) {
+                            ChildNameDefinition(def, lp) |
+                            ImportNameDefinition(def, lp) => {
+                                match def {
+                                    DefAssociatedTy(trait_type_id) => {
+                                        let def = DefAssociatedTy(
+                                            trait_type_id);
+                                        self.record_def(ty.id, (def, lp));
+                                    }
+                                    _ => {
+                                        self.resolve_error(
+                                            ty.span,
+                                            "not an associated type");
+                                    }
+                                }
+                            }
+                            NoNameDefinition => {
+                                self.resolve_error(ty.span,
+                                                   "unresolved associated \
+                                                    type");
+                            }
+                        }
+                    }
+                    Success(..) => self.resolve_error(ty.span, "not a trait"),
+                    Indeterminate => {
+                        self.session.span_bug(ty.span,
+                                              "indeterminate result when \
+                                               resolving associated type")
+                    }
+                    Failed(error) => {
+                        let (span, help) = match error {
+                            Some((span, msg)) => (span, format!("; {}", msg)),
+                            None => (ty.span, String::new()),
+                        };
+                        self.resolve_error(span,
+                                           format!("unresolved trait: {}",
+                                                   help).as_slice())
+                    }
+                }
+            }
+
             TyClosure(ref c) | TyProc(ref c) => {
-                self.resolve_type_parameter_bounds(ty.id, &c.bounds,
-                                                   TraitBoundingTypeParameter);
+                self.resolve_type_parameter_bounds(
+                    ty.id,
+                    &c.bounds,
+                    TraitBoundingTypeParameter);
                 visit::walk_ty(self, ty);
             }
 
@@ -5210,8 +5330,9 @@ impl<'a> Resolver<'a> {
                     Some(def_id) => {
                         match self.trait_item_map.borrow().find(&(ident.name, def_id)) {
                             Some(&StaticMethodTraitItemKind) => (),
+                            Some(&TypeTraitItemKind) => (),
                             None => (),
-                            _ => {
+                            Some(&NonstaticMethodTraitItemKind) => {
                                 debug!("containing module was a trait or impl \
                                 and name was a method -> not resolved");
                                 return None;
diff --git a/src/librustc/middle/save/mod.rs b/src/librustc/middle/save/mod.rs
index 37ba3b75f89..cab83f4cda2 100644
--- a/src/librustc/middle/save/mod.rs
+++ b/src/librustc/middle/save/mod.rs
@@ -227,6 +227,7 @@ impl <'l, 'tcx> DxrVisitor<'l, 'tcx> {
             def::DefForeignMod(_) => Some(recorder::ModRef),
             def::DefStruct(_) => Some(recorder::StructRef),
             def::DefTy(..) |
+            def::DefAssociatedTy(..) |
             def::DefTrait(_) => Some(recorder::TypeRef),
             def::DefStatic(_, _) |
             def::DefBinding(_, _) |
@@ -355,11 +356,12 @@ impl <'l, 'tcx> DxrVisitor<'l, 'tcx> {
                     ty::MethodTraitItemId(def_id) => {
                         method.id != 0 && def_id.node == 0
                     }
+                    ty::TypeTraitItemId(_) => false,
                 }
             });
         let decl_id = match decl_id {
             None => None,
-            Some(ty::MethodTraitItemId(def_id)) => Some(def_id),
+            Some(id) => Some(id.def_id()),
         };
 
         let sub_span = self.span.sub_span_after_keyword(method.span, keywords::Fn);
@@ -646,6 +648,9 @@ impl <'l, 'tcx> DxrVisitor<'l, 'tcx> {
                 ast::MethodImplItem(ref method) => {
                     visit::walk_method_helper(self, &**method)
                 }
+                ast::TypeImplItem(ref typedef) => {
+                    visit::walk_ty(self, &*typedef.typ)
+                }
             }
         }
     }
@@ -764,12 +769,7 @@ impl <'l, 'tcx> DxrVisitor<'l, 'tcx> {
                                                  def_id)
                                     .iter()
                                     .find(|mr| {
-                                        match **mr {
-                                            ty::MethodTraitItem(ref mr) => {
-                                                mr.ident.name == ti.ident()
-                                                                   .name
-                                            }
-                                        }
+                                        mr.ident().name == ti.ident().name
                                     })
                                     .unwrap()
                                     .def_id())
@@ -782,18 +782,13 @@ impl <'l, 'tcx> DxrVisitor<'l, 'tcx> {
                             Some(impl_items.get(&def_id)
                                            .iter()
                                            .find(|mr| {
-                                            match **mr {
-                                                ty::MethodTraitItemId(mr) => {
-                                                    ty::impl_or_trait_item(
-                                                            &self.analysis
-                                                                 .ty_cx,
-                                                            mr).ident()
-                                                               .name ==
-                                                        ti.ident().name
-                                                    }
-                                                }
-                                            }).unwrap()
-                                              .def_id())
+                                            ty::impl_or_trait_item(
+                                                &self.analysis.ty_cx,
+                                                mr.def_id()).ident().name ==
+                                                ti.ident().name
+                                            })
+                                           .unwrap()
+                                           .def_id())
                         }
                     }
                 } else {
@@ -894,7 +889,7 @@ impl <'l, 'tcx> DxrVisitor<'l, 'tcx> {
                     match ty::trait_item_of_item(&self.analysis.ty_cx,
                                                  def_id) {
                         None => None,
-                        Some(ty::MethodTraitItemId(decl_id)) => Some(decl_id),
+                        Some(decl_id) => Some(decl_id.def_id()),
                     };
 
                 // This incantation is required if the method referenced is a
@@ -905,6 +900,7 @@ impl <'l, 'tcx> DxrVisitor<'l, 'tcx> {
                     ty::MethodTraitItem(method) => {
                         method.provided_source.unwrap_or(def_id)
                     }
+                    ty::TypeTraitItem(_) => def_id,
                 };
                 (Some(def_id), decl_id)
             }
@@ -913,23 +909,15 @@ impl <'l, 'tcx> DxrVisitor<'l, 'tcx> {
                 let trait_item = ty::trait_item(&self.analysis.ty_cx,
                                                 mp.trait_ref.def_id,
                                                 mp.method_num);
-                match trait_item {
-                    ty::MethodTraitItem(method) => {
-                        (None, Some(method.def_id))
-                    }
-                }
-            },
+                (None, Some(trait_item.def_id()))
+            }
             typeck::MethodObject(ref mo) => {
                 // method invoked on a trait instance
                 let trait_item = ty::trait_item(&self.analysis.ty_cx,
                                                 mo.trait_ref.def_id,
                                                 mo.method_num);
-                match trait_item {
-                    ty::MethodTraitItem(method) => {
-                        (None, Some(method.def_id))
-                    }
-                }
-            },
+                (None, Some(trait_item.def_id()))
+            }
         };
         let sub_span = self.span.sub_span_for_meth_name(ex.span);
         self.fmt.meth_call_str(ex.span,
@@ -1139,7 +1127,8 @@ impl<'l, 'tcx, 'v> Visitor<'v> for DxrVisitor<'l, 'tcx> {
                                             qualname,
                                             method_type.id);
             }
-            ast::ProvidedMethod(ref method) => self.process_method(&**method)
+            ast::ProvidedMethod(ref method) => self.process_method(&**method),
+            ast::TypeTraitItem(_) => {}
         }
     }
 
diff --git a/src/librustc/middle/stability.rs b/src/librustc/middle/stability.rs
index eb736ae8a76..ef169264650 100644
--- a/src/librustc/middle/stability.rs
+++ b/src/librustc/middle/stability.rs
@@ -16,8 +16,9 @@ use syntax::codemap::Span;
 use syntax::{attr, visit};
 use syntax::ast;
 use syntax::ast::{Attribute, Block, Crate, DefId, FnDecl, NodeId, Variant};
-use syntax::ast::{Item, RequiredMethod, ProvidedMethod, TraitItem, TypeMethod, Method};
-use syntax::ast::{Generics, StructDef, StructField, Ident};
+use syntax::ast::{Item, RequiredMethod, ProvidedMethod, TraitItem};
+use syntax::ast::{TypeMethod, Method, Generics, StructDef, StructField};
+use syntax::ast::{Ident, TypeTraitItem};
 use syntax::ast_util::is_local;
 use syntax::attr::Stability;
 use syntax::visit::{FnKind, FkMethod, Visitor};
@@ -79,9 +80,13 @@ impl<'v> Visitor<'v> for Annotator {
             RequiredMethod(TypeMethod {id, ref attrs, ..}) => (id, attrs),
 
             // work around lack of pattern matching for @ types
-            ProvidedMethod(ref method) => match **method {
-                Method {id, ref attrs, ..} => (id, attrs)
+            ProvidedMethod(ref method) => {
+                match **method {
+                    Method {attrs: ref attrs, id: id, ..} => (id, attrs),
+                }
             }
+
+            TypeTraitItem(ref typedef) => (typedef.id, &typedef.attrs),
         };
         self.annotate(id, attrs, |v| visit::walk_trait_item(v, t));
     }
diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index 4b35024ecb0..9583dcf560e 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -630,7 +630,12 @@ impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> {
 
         let t1 = match ty::get(t).sty {
             ty::ty_param(p) => {
-                check(self, p, t, self.substs.types.opt_get(p.space, p.idx))
+                check(self,
+                      p,
+                      t,
+                      self.substs.types.opt_get(p.space, p.idx),
+                      p.space,
+                      p.idx)
             }
             _ => {
                 ty_fold::super_fold_ty(self, t)
@@ -648,7 +653,9 @@ impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> {
         fn check(this: &SubstFolder,
                  p: ty::ParamTy,
                  source_ty: ty::t,
-                 opt_ty: Option<&ty::t>)
+                 opt_ty: Option<&ty::t>,
+                 space: ParamSpace,
+                 index: uint)
                  -> ty::t {
             match opt_ty {
                 Some(t) => *t,
@@ -656,10 +663,12 @@ impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> {
                     let span = this.span.unwrap_or(DUMMY_SP);
                     this.tcx().sess.span_bug(
                         span,
-                        format!("Type parameter `{}` ({}) out of range \
+                        format!("Type parameter `{}` ({}/{}/{}) out of range \
                                  when substituting (root type={})",
                                 p.repr(this.tcx()),
                                 source_ty.repr(this.tcx()),
+                                space,
+                                index,
                                 this.root_ty.repr(this.tcx())).as_slice());
                 }
             }
diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs
index a0cb8810289..a814c9d624c 100644
--- a/src/librustc/middle/trans/base.rs
+++ b/src/librustc/middle/trans/base.rs
@@ -1375,6 +1375,10 @@ fn has_nested_returns(tcx: &ty::ctxt, id: ast::NodeId) -> bool {
                     tcx.sess.bug("unexpected variant: required trait method \
                                   in has_nested_returns")
                 }
+                ast::TypeTraitItem(_) => {
+                    tcx.sess.bug("unexpected variant: type trait item in \
+                                  has_nested_returns")
+                }
             }
         }
         Some(ast_map::NodeImplItem(ii)) => {
@@ -1391,6 +1395,10 @@ fn has_nested_returns(tcx: &ty::ctxt, id: ast::NodeId) -> bool {
                         ast::MethMac(_) => tcx.sess.bug("unexpanded macro")
                     }
                 }
+                ast::TypeImplItem(_) => {
+                    tcx.sess.bug("unexpected variant: type impl item in \
+                                  has_nested_returns")
+                }
             }
         }
         Some(ast_map::NodeExpr(e)) => {
@@ -2779,9 +2787,9 @@ pub fn get_item_val(ccx: &CrateContext, id: ast::NodeId) -> ValueRef {
         ast_map::NodeTraitItem(trait_method) => {
             debug!("get_item_val(): processing a NodeTraitItem");
             match *trait_method {
-                ast::RequiredMethod(_) => {
-                    ccx.sess().bug("unexpected variant: required trait method in \
-                                   get_item_val()");
+                ast::RequiredMethod(_) | ast::TypeTraitItem(_) => {
+                    ccx.sess().bug("unexpected variant: required trait \
+                                    method in get_item_val()");
                 }
                 ast::ProvidedMethod(ref m) => {
                     register_method(ccx, id, &**m)
@@ -2792,6 +2800,11 @@ pub fn get_item_val(ccx: &CrateContext, id: ast::NodeId) -> ValueRef {
         ast_map::NodeImplItem(ii) => {
             match *ii {
                 ast::MethodImplItem(ref m) => register_method(ccx, id, &**m),
+                ast::TypeImplItem(ref typedef) => {
+                    ccx.sess().span_bug(typedef.span,
+                                        "unexpected variant: required impl \
+                                         method in get_item_val()")
+                }
             }
         }
 
diff --git a/src/librustc/middle/trans/callee.rs b/src/librustc/middle/trans/callee.rs
index ef98a734302..c54a446c455 100644
--- a/src/librustc/middle/trans/callee.rs
+++ b/src/librustc/middle/trans/callee.rs
@@ -203,7 +203,7 @@ fn trans<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, expr: &ast::Expr)
                 datum_callee(bcx, ref_expr)
             }
             def::DefMod(..) | def::DefForeignMod(..) | def::DefTrait(..) |
-            def::DefTy(..) | def::DefPrimTy(..) |
+            def::DefTy(..) | def::DefPrimTy(..) | def::DefAssociatedTy(..) |
             def::DefUse(..) | def::DefTyParamBinder(..) |
             def::DefRegion(..) | def::DefLabel(..) | def::DefTyParam(..) |
             def::DefSelfTy(..) | def::DefMethod(..) => {
@@ -458,6 +458,10 @@ pub fn trans_fn_ref_with_substs(
 
                     (true, source_id, new_substs)
                 }
+                ty::TypeTraitItem(_) => {
+                    bcx.tcx().sess.bug("trans_fn_ref_with_vtables() tried \
+                                        to translate an associated type?!")
+                }
             }
         }
     };
diff --git a/src/librustc/middle/trans/debuginfo.rs b/src/librustc/middle/trans/debuginfo.rs
index a600baba554..359da14d57e 100644
--- a/src/librustc/middle/trans/debuginfo.rs
+++ b/src/librustc/middle/trans/debuginfo.rs
@@ -1153,6 +1153,11 @@ pub fn create_function_debug_context(cx: &CrateContext,
                      method.span,
                      true)
                 }
+                ast::TypeImplItem(ref typedef) => {
+                    cx.sess().span_bug(typedef.span,
+                                       "create_function_debug_context() \
+                                        called on associated type?!")
+                }
             }
         }
         ast_map::NodeExpr(ref expr) => {
diff --git a/src/librustc/middle/trans/inline.rs b/src/librustc/middle/trans/inline.rs
index e1e728fbea0..e5c8d4d0ab3 100644
--- a/src/librustc/middle/trans/inline.rs
+++ b/src/librustc/middle/trans/inline.rs
@@ -156,6 +156,9 @@ fn instantiate_inline(ccx: &CrateContext, fn_id: ast::DefId)
                     // don't.
                     local_def(mth.id)
                 }
+                ast::TypeTraitItem(_) => {
+                    ccx.sess().bug("found TypeTraitItem IITraitItem")
+                }
             }
         }
         csearch::found(&ast::IIImplItem(impl_did, ref impl_item)) => {
@@ -185,6 +188,9 @@ fn instantiate_inline(ccx: &CrateContext, fn_id: ast::DefId)
                     }
                     local_def(mth.id)
                 }
+                ast::TypeImplItem(_) => {
+                    ccx.sess().bug("found TypeImplItem IIImplItem")
+                }
             }
         }
     };
diff --git a/src/librustc/middle/trans/meth.rs b/src/librustc/middle/trans/meth.rs
index 27216d067b9..f1276387745 100644
--- a/src/librustc/middle/trans/meth.rs
+++ b/src/librustc/middle/trans/meth.rs
@@ -71,6 +71,7 @@ pub fn trans_impl(ccx: &CrateContext,
                 ast::MethodImplItem(ref method) => {
                     visit::walk_method_helper(&mut v, &**method);
                 }
+                ast::TypeImplItem(_) => {}
             }
         }
         return;
@@ -100,6 +101,7 @@ pub fn trans_impl(ccx: &CrateContext,
                 };
                 visit::walk_method_helper(&mut v, &**method);
             }
+            ast::TypeImplItem(_) => {}
         }
     }
 }
@@ -183,7 +185,11 @@ pub fn trans_static_method_callee(bcx: Block,
             ast_map::NodeTraitItem(method) => {
                 let ident = match *method {
                     ast::RequiredMethod(ref m) => m.ident,
-                    ast::ProvidedMethod(ref m) => m.pe_ident()
+                    ast::ProvidedMethod(ref m) => m.pe_ident(),
+                    ast::TypeTraitItem(_) => {
+                        bcx.tcx().sess.bug("trans_static_method_callee() on \
+                                            an associated type?!")
+                    }
                 };
                 ident.name
             }
@@ -294,14 +300,10 @@ fn method_with_name(ccx: &CrateContext, impl_id: ast::DefId, name: ast::Name)
                   .expect("could not find impl while translating");
     let meth_did = impl_items.iter()
                              .find(|&did| {
-                                match *did {
-                                    ty::MethodTraitItemId(did) => {
-                                        ty::impl_or_trait_item(ccx.tcx(),
-                                                               did).ident()
-                                                                   .name ==
-                                            name
-                                    }
-                                }
+                                ty::impl_or_trait_item(ccx.tcx(),
+                                                       did.def_id()).ident()
+                                                                    .name ==
+                                    name
                              }).expect("could not find method while \
                                         translating");
 
@@ -323,6 +325,10 @@ fn trans_monomorphized_callee<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
             let impl_did = vtable_impl.impl_def_id;
             let mname = match ty::trait_item(ccx.tcx(), trait_id, n_method) {
                 ty::MethodTraitItem(method) => method.ident,
+                ty::TypeTraitItem(_) => {
+                    bcx.tcx().sess.bug("can't monomorphize an associated \
+                                        type")
+                }
             };
             let mth_id = method_with_name(bcx.ccx(), impl_did, mname.name);
 
@@ -693,7 +699,7 @@ fn emit_vtable_methods(bcx: Block,
     ty::populate_implementations_for_trait_if_necessary(bcx.tcx(), trt_id);
 
     let trait_item_def_ids = ty::trait_item_def_ids(tcx, trt_id);
-    trait_item_def_ids.iter().map(|method_def_id| {
+    trait_item_def_ids.iter().flat_map(|method_def_id| {
         let method_def_id = method_def_id.def_id();
         let ident = ty::impl_or_trait_item(tcx, method_def_id).ident();
         // The substitutions we have are on the impl, so we grab
@@ -710,7 +716,7 @@ fn emit_vtable_methods(bcx: Block,
                     debug!("(making impl vtable) method has self or type \
                             params: {}",
                            token::get_ident(ident));
-                    C_null(Type::nil(ccx).ptr_to())
+                    Some(C_null(Type::nil(ccx).ptr_to())).move_iter()
                 } else {
                     let mut fn_ref = trans_fn_ref_with_substs(
                         bcx,
@@ -724,9 +730,12 @@ fn emit_vtable_methods(bcx: Block,
                                                      m_id,
                                                      substs.clone());
                     }
-                    fn_ref
+                    Some(fn_ref).move_iter()
                 }
             }
+            ty::TypeTraitItem(_) => {
+                None.move_iter()
+            }
         }
     }).collect()
 }
diff --git a/src/librustc/middle/trans/monomorphize.rs b/src/librustc/middle/trans/monomorphize.rs
index 00e9d9f0e39..d2bbbdfad0e 100644
--- a/src/librustc/middle/trans/monomorphize.rs
+++ b/src/librustc/middle/trans/monomorphize.rs
@@ -231,6 +231,9 @@ pub fn monomorphic_fn(ccx: &CrateContext,
                     }
                     d
                 }
+                ast::TypeImplItem(_) => {
+                    ccx.sess().bug("can't monomorphize an associated type")
+                }
             }
         }
         ast_map::NodeTraitItem(method) => {
diff --git a/src/librustc/middle/trans/reflect.rs b/src/librustc/middle/trans/reflect.rs
index 214726edd77..03550299fbd 100644
--- a/src/librustc/middle/trans/reflect.rs
+++ b/src/librustc/middle/trans/reflect.rs
@@ -92,6 +92,7 @@ impl<'a, 'blk, 'tcx> Reflector<'a, 'blk, 'tcx> {
                 format!("couldn't find visit method for {}", ty_name).as_slice());
         let method = match self.visitor_items[mth_idx] {
             ty::MethodTraitItem(ref method) => (*method).clone(),
+            ty::TypeTraitItem(_) => return,
         };
         let mth_ty = ty::mk_bare_fn(tcx, method.fty.clone());
         debug!("Emit call visit method: visit_{}: {}", ty_name, ty_to_string(tcx, mth_ty));
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 09912b54583..897bc4517f4 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -97,30 +97,37 @@ impl ImplOrTraitItemContainer {
 #[deriving(Clone)]
 pub enum ImplOrTraitItem {
     MethodTraitItem(Rc<Method>),
+    TypeTraitItem(Rc<AssociatedType>),
 }
 
 impl ImplOrTraitItem {
     fn id(&self) -> ImplOrTraitItemId {
         match *self {
             MethodTraitItem(ref method) => MethodTraitItemId(method.def_id),
+            TypeTraitItem(ref associated_type) => {
+                TypeTraitItemId(associated_type.def_id)
+            }
         }
     }
 
     pub fn def_id(&self) -> ast::DefId {
         match *self {
             MethodTraitItem(ref method) => method.def_id,
+            TypeTraitItem(ref associated_type) => associated_type.def_id,
         }
     }
 
     pub fn ident(&self) -> ast::Ident {
         match *self {
             MethodTraitItem(ref method) => method.ident,
+            TypeTraitItem(ref associated_type) => associated_type.ident,
         }
     }
 
     pub fn container(&self) -> ImplOrTraitItemContainer {
         match *self {
             MethodTraitItem(ref method) => method.container,
+            TypeTraitItem(ref associated_type) => associated_type.container,
         }
     }
 }
@@ -128,12 +135,14 @@ impl ImplOrTraitItem {
 #[deriving(Clone)]
 pub enum ImplOrTraitItemId {
     MethodTraitItemId(ast::DefId),
+    TypeTraitItemId(ast::DefId),
 }
 
 impl ImplOrTraitItemId {
     pub fn def_id(&self) -> ast::DefId {
         match *self {
             MethodTraitItemId(def_id) => def_id,
+            TypeTraitItemId(def_id) => def_id,
         }
     }
 }
@@ -182,6 +191,14 @@ impl Method {
     }
 }
 
+#[deriving(Clone)]
+pub struct AssociatedType {
+    pub ident: ast::Ident,
+    pub vis: ast::Visibility,
+    pub def_id: ast::DefId,
+    pub container: ImplOrTraitItemContainer,
+}
+
 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
 pub struct mt {
     pub ty: t,
@@ -556,6 +573,13 @@ pub struct ctxt<'tcx> {
 
     /// Maps closures to their capture clauses.
     pub capture_modes: RefCell<CaptureModeMap>,
+
+    /// Maps def IDs to true if and only if they're associated types.
+    pub associated_types: RefCell<DefIdMap<bool>>,
+
+    /// Maps def IDs of traits to information about their associated types.
+    pub trait_associated_types:
+        RefCell<DefIdMap<Rc<Vec<AssociatedTypeInfo>>>>,
 }
 
 pub enum tbox_flag {
@@ -1179,6 +1203,7 @@ pub struct TypeParameterDef {
     pub def_id: ast::DefId,
     pub space: subst::ParamSpace,
     pub index: uint,
+    pub associated_with: Option<ast::DefId>,
     pub bounds: ParamBounds,
     pub default: Option<ty::t>,
 }
@@ -1238,7 +1263,7 @@ pub struct ParameterEnvironment {
     /// the "outer" view of a type or method to the "inner" view.
     /// In general, this means converting from bound parameters to
     /// free parameters. Since we currently represent bound/free type
-    /// parameters in the same way, this only has an affect on regions.
+    /// parameters in the same way, this only has an effect on regions.
     pub free_substs: Substs,
 
     /// Bounds on the various type parameters
@@ -1275,8 +1300,19 @@ impl ParameterEnvironment {
                                     method_generics,
                                     method.pe_body().id)
                             }
+                            TypeTraitItem(_) => {
+                                cx.sess
+                                  .bug("ParameterEnvironment::from_item(): \
+                                        can't create a parameter environment \
+                                        for type trait items")
+                            }
                         }
                     }
+                    ast::TypeImplItem(_) => {
+                        cx.sess.bug("ParameterEnvironment::from_item(): \
+                                     can't create a parameter environment \
+                                     for type impl items")
+                    }
                 }
             }
             Some(ast_map::NodeTraitItem(trait_method)) => {
@@ -1299,8 +1335,19 @@ impl ParameterEnvironment {
                                     method_generics,
                                     method.pe_body().id)
                             }
+                            TypeTraitItem(_) => {
+                                cx.sess
+                                  .bug("ParameterEnvironment::from_item(): \
+                                        can't create a parameter environment \
+                                        for type trait items")
+                            }
                         }
                     }
+                    ast::TypeTraitItem(_) => {
+                        cx.sess.bug("ParameterEnvironment::from_item(): \
+                                     can't create a parameter environment \
+                                     for type trait items")
+                    }
                 }
             }
             Some(ast_map::NodeItem(item)) => {
@@ -1476,6 +1523,8 @@ pub fn mk_ctxt<'tcx>(s: Session,
         transmute_restrictions: RefCell::new(Vec::new()),
         stability: RefCell::new(stability),
         capture_modes: RefCell::new(capture_modes),
+        associated_types: RefCell::new(DefIdMap::new()),
+        trait_associated_types: RefCell::new(DefIdMap::new()),
     }
 }
 
@@ -1894,6 +1943,10 @@ impl ParamTy {
     pub fn to_ty(self, tcx: &ty::ctxt) -> ty::t {
         ty::mk_param(tcx, self.space, self.idx, self.def_id)
     }
+
+    pub fn is_self(&self) -> bool {
+        self.space == subst::SelfSpace && self.idx == 0
+    }
 }
 
 impl ItemSubsts {
@@ -3543,6 +3596,10 @@ pub fn method_call_type_param_defs<'tcx, T>(typer: &T,
         }) => {
             match ty::trait_item(typer.tcx(), trait_ref.def_id, n_mth) {
                 ty::MethodTraitItem(method) => method.generics.types.clone(),
+                ty::TypeTraitItem(_) => {
+                    typer.tcx().sess.bug("method_call_type_param_defs() \
+                                          called on associated type")
+                }
             }
         }
     }
@@ -4007,12 +4064,19 @@ pub fn provided_trait_methods(cx: &ctxt, id: ast::DefId) -> Vec<Rc<Method>> {
             Some(ast_map::NodeItem(item)) => {
                 match item.node {
                     ItemTrait(_, _, _, ref ms) => {
-                        ms.iter().filter_map(|m| match *m {
-                            ast::RequiredMethod(_) => None,
-                            ast::ProvidedMethod(ref m) => {
-                                match impl_or_trait_item(cx,
-                                        ast_util::local_def(m.id)) {
-                                    MethodTraitItem(m) => Some(m),
+                        let (_, p) =
+                            ast_util::split_trait_methods(ms.as_slice());
+                        p.iter()
+                         .map(|m| {
+                            match impl_or_trait_item(
+                                    cx,
+                                    ast_util::local_def(m.id)) {
+                                MethodTraitItem(m) => m,
+                                TypeTraitItem(_) => {
+                                    cx.sess.bug("provided_trait_methods(): \
+                                                 split_trait_methods() put \
+                                                 associated types in the \
+                                                 provided method bucket?!")
                                 }
                             }
                          }).collect()
@@ -4097,6 +4161,75 @@ pub fn impl_or_trait_item(cx: &ctxt, id: ast::DefId) -> ImplOrTraitItem {
     })
 }
 
+/// Returns true if the given ID refers to an associated type and false if it
+/// refers to anything else.
+pub fn is_associated_type(cx: &ctxt, id: ast::DefId) -> bool {
+    let result = match cx.associated_types.borrow_mut().find(&id) {
+        Some(result) => return *result,
+        None if id.krate == ast::LOCAL_CRATE => {
+            match cx.impl_or_trait_items.borrow().find(&id) {
+                Some(ref item) => {
+                    match **item {
+                        TypeTraitItem(_) => true,
+                        MethodTraitItem(_) => false,
+                    }
+                }
+                None => false,
+            }
+        }
+        None => {
+            csearch::is_associated_type(&cx.sess.cstore, id)
+        }
+    };
+
+    cx.associated_types.borrow_mut().insert(id, result);
+    result
+}
+
+/// Returns the parameter index that the given associated type corresponds to.
+pub fn associated_type_parameter_index(cx: &ctxt,
+                                       trait_def: &TraitDef,
+                                       associated_type_id: ast::DefId)
+                                       -> uint {
+    for type_parameter_def in trait_def.generics.types.iter() {
+        if type_parameter_def.def_id == associated_type_id {
+            return type_parameter_def.index
+        }
+    }
+    cx.sess.bug("couldn't find associated type parameter index")
+}
+
+#[deriving(PartialEq, Eq)]
+pub struct AssociatedTypeInfo {
+    pub def_id: ast::DefId,
+    pub index: uint,
+    pub ident: ast::Ident,
+}
+
+impl PartialOrd for AssociatedTypeInfo {
+    fn partial_cmp(&self, other: &AssociatedTypeInfo) -> Option<Ordering> {
+        Some(self.index.cmp(&other.index))
+    }
+}
+
+impl Ord for AssociatedTypeInfo {
+    fn cmp(&self, other: &AssociatedTypeInfo) -> Ordering {
+        self.index.cmp(&other.index)
+    }
+}
+
+/// Returns the associated types belonging to the given trait, in parameter
+/// order.
+pub fn associated_types_for_trait(cx: &ctxt, trait_id: ast::DefId)
+                                  -> Rc<Vec<AssociatedTypeInfo>> {
+    cx.trait_associated_types
+      .borrow()
+      .find(&trait_id)
+      .expect("associated_types_for_trait(): trait not found, try calling \
+               ensure_associated_types()")
+      .clone()
+}
+
 pub fn trait_item_def_ids(cx: &ctxt, id: ast::DefId)
                           -> Rc<Vec<ImplOrTraitItemId>> {
     lookup_locally_or_in_crate_store("trait_item_def_ids",
@@ -4978,6 +5111,7 @@ pub fn populate_implementations_for_type_if_necessary(tcx: &ctxt,
                            .insert(method_def_id, source);
                     }
                 }
+                TypeTraitItem(_) => {}
             }
         }
 
@@ -5025,6 +5159,7 @@ pub fn populate_implementations_for_trait_if_necessary(
                            .insert(method_def_id, source);
                     }
                 }
+                TypeTraitItem(_) => {}
             }
         }
 
@@ -5108,9 +5243,7 @@ pub fn trait_item_of_item(tcx: &ctxt, def_id: ast::DefId)
         Some(m) => m.clone(),
         None => return None,
     };
-    let name = match impl_item {
-        MethodTraitItem(method) => method.ident.name,
-    };
+    let name = impl_item.ident().name;
     match trait_of_item(tcx, def_id) {
         Some(trait_did) => {
             let trait_items = ty::trait_items(tcx, trait_did);
@@ -5364,6 +5497,11 @@ pub fn construct_parameter_environment(
                             space: subst::ParamSpace,
                             defs: &[TypeParameterDef]) {
         for (i, def) in defs.iter().enumerate() {
+            debug!("construct_parameter_environment(): push_types_from_defs: \
+                    space={} def={} index={}",
+                   space,
+                   def.repr(tcx),
+                   i);
             let ty = ty::mk_param(tcx, space, i, def.def_id);
             types.push(space, ty);
         }
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
index 48fa6f823b0..3b08ccd5a7b 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -301,6 +301,7 @@ impl TypeFoldable for ty::TypeParameterDef {
             def_id: self.def_id,
             space: self.space,
             index: self.index,
+            associated_with: self.associated_with,
             bounds: self.bounds.fold_with(folder),
             default: self.default.fold_with(folder),
         }
diff --git a/src/librustc/middle/typeck/astconv.rs b/src/librustc/middle/typeck/astconv.rs
index 00678eb6380..8f60be8f7fb 100644
--- a/src/librustc/middle/typeck/astconv.rs
+++ b/src/librustc/middle/typeck/astconv.rs
@@ -70,14 +70,30 @@ use std::rc::Rc;
 use syntax::abi;
 use syntax::{ast, ast_util};
 use syntax::codemap::Span;
+use syntax::parse::token;
 
 pub trait AstConv<'tcx> {
     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype;
     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef>;
 
-    // what type should we use when a type is omitted?
+    /// What type should we use when a type is omitted?
     fn ty_infer(&self, span: Span) -> ty::t;
+
+    /// Returns true if associated types from the given trait and type are
+    /// allowed to be used here and false otherwise.
+    fn associated_types_of_trait_are_valid(&self,
+                                           ty: ty::t,
+                                           trait_id: ast::DefId)
+                                           -> bool;
+
+    /// Returns the binding of the given associated type for some type.
+    fn associated_type_binding(&self,
+                               span: Span,
+                               ty: Option<ty::t>,
+                               trait_id: ast::DefId,
+                               associated_type_id: ast::DefId)
+                               -> ty::t;
 }
 
 pub fn ast_region_to_region(tcx: &ty::ctxt, lifetime: &ast::Lifetime)
@@ -152,13 +168,16 @@ pub fn opt_ast_region_to_region<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
     r
 }
 
-fn ast_path_substs<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
-    this: &AC,
-    rscope: &RS,
-    decl_generics: &ty::Generics,
-    self_ty: Option<ty::t>,
-    path: &ast::Path) -> Substs
-{
+fn ast_path_substs<'tcx,AC,RS>(
+                   this: &AC,
+                   rscope: &RS,
+                   decl_def_id: ast::DefId,
+                   decl_generics: &ty::Generics,
+                   self_ty: Option<ty::t>,
+                   associated_ty: Option<ty::t>,
+                   path: &ast::Path)
+                   -> Substs
+                   where AC: AstConv<'tcx>, RS: RegionScope {
     /*!
      * Given a path `path` that refers to an item `I` with the
      * declared generics `decl_generics`, returns an appropriate
@@ -206,10 +225,17 @@ fn ast_path_substs<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
     // Convert the type parameters supplied by the user.
     let ty_param_defs = decl_generics.types.get_slice(TypeSpace);
     let supplied_ty_param_count = path.segments.iter().flat_map(|s| s.types.iter()).count();
-    let formal_ty_param_count = ty_param_defs.len();
-    let required_ty_param_count = ty_param_defs.iter()
-                                               .take_while(|x| x.default.is_none())
-                                               .count();
+    let formal_ty_param_count =
+        ty_param_defs.iter()
+                     .take_while(|x| !ty::is_associated_type(tcx, x.def_id))
+                     .count();
+    let required_ty_param_count =
+        ty_param_defs.iter()
+                     .take_while(|x| {
+                        x.default.is_none() &&
+                        !ty::is_associated_type(tcx, x.def_id)
+                     })
+                     .count();
     if supplied_ty_param_count < required_ty_param_count {
         let expected = if required_ty_param_count < formal_ty_param_count {
             "expected at least"
@@ -242,9 +268,11 @@ fn ast_path_substs<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
             "add #![feature(default_type_params)] to the crate attributes to enable");
     }
 
-    let tps = path.segments.iter().flat_map(|s| s.types.iter())
-                            .map(|a_t| ast_ty_to_ty(this, rscope, &**a_t))
-                            .collect();
+    let tps = path.segments
+                  .iter()
+                  .flat_map(|s| s.types.iter())
+                  .map(|a_t| ast_ty_to_ty(this, rscope, &**a_t))
+                  .collect();
 
     let mut substs = Substs::new_type(tps, regions);
 
@@ -263,24 +291,48 @@ fn ast_path_substs<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
     }
 
     for param in ty_param_defs.slice_from(supplied_ty_param_count).iter() {
-        let default = param.default.unwrap();
-        let default = default.subst_spanned(tcx, &substs, Some(path.span));
-        substs.types.push(TypeSpace, default);
+        match param.default {
+            Some(default) => {
+                // This is a default type parameter.
+                let default = default.subst_spanned(tcx,
+                                                    &substs,
+                                                    Some(path.span));
+                substs.types.push(TypeSpace, default);
+            }
+            None => {
+                // This is an associated type.
+                substs.types.push(
+                    TypeSpace,
+                    this.associated_type_binding(path.span,
+                                                 associated_ty,
+                                                 decl_def_id,
+                                                 param.def_id))
+            }
+        }
     }
 
     substs
 }
 
-pub fn ast_path_to_trait_ref<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
-        this: &AC,
-        rscope: &RS,
-        trait_def_id: ast::DefId,
-        self_ty: Option<ty::t>,
-        path: &ast::Path) -> Rc<ty::TraitRef> {
+pub fn ast_path_to_trait_ref<'tcx,AC,RS>(this: &AC,
+                                         rscope: &RS,
+                                         trait_def_id: ast::DefId,
+                                         self_ty: Option<ty::t>,
+                                         associated_type: Option<ty::t>,
+                                         path: &ast::Path)
+                                         -> Rc<ty::TraitRef>
+                                         where AC: AstConv<'tcx>,
+                                               RS: RegionScope {
     let trait_def = this.get_trait_def(trait_def_id);
     Rc::new(ty::TraitRef {
         def_id: trait_def_id,
-        substs: ast_path_substs(this, rscope, &trait_def.generics, self_ty, path)
+        substs: ast_path_substs(this,
+                                rscope,
+                                trait_def_id,
+                                &trait_def.generics,
+                                self_ty,
+                                associated_type,
+                                path)
     })
 }
 
@@ -289,15 +341,20 @@ pub fn ast_path_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
     rscope: &RS,
     did: ast::DefId,
     path: &ast::Path)
-    -> TypeAndSubsts
-{
+    -> TypeAndSubsts {
     let tcx = this.tcx();
     let ty::Polytype {
         generics: generics,
         ty: decl_ty
     } = this.get_item_ty(did);
 
-    let substs = ast_path_substs(this, rscope, &generics, None, path);
+    let substs = ast_path_substs(this,
+                                 rscope,
+                                 did,
+                                 &generics,
+                                 None,
+                                 None,
+                                 path);
     let ty = decl_ty.subst(tcx, &substs);
     TypeAndSubsts { substs: substs, ty: ty }
 }
@@ -333,7 +390,7 @@ pub fn ast_path_to_ty_relaxed<'tcx, AC: AstConv<'tcx>,
         Substs::new(VecPerParamSpace::params_from_type(type_params),
                     VecPerParamSpace::params_from_type(region_params))
     } else {
-        ast_path_substs(this, rscope, &generics, None, path)
+        ast_path_substs(this, rscope, did, &generics, None, None, path)
     };
 
     let ty = decl_ty.subst(tcx, &substs);
@@ -639,8 +696,12 @@ fn mk_pointer<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
                     }
                 }
                 Some(&def::DefTrait(trait_def_id)) => {
-                    let result = ast_path_to_trait_ref(
-                        this, rscope, trait_def_id, None, path);
+                    let result = ast_path_to_trait_ref(this,
+                                                       rscope,
+                                                       trait_def_id,
+                                                       None,
+                                                       None,
+                                                       path);
                     let bounds = match *opt_bounds {
                         None => {
                             conv_existential_bounds(this,
@@ -686,6 +747,52 @@ fn mk_pointer<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
     constr(ast_ty_to_ty(this, rscope, a_seq_ty))
 }
 
+fn associated_ty_to_ty<'tcx,AC,RS>(this: &AC,
+                                   rscope: &RS,
+                                   trait_path: &ast::Path,
+                                   for_ast_type: &ast::Ty,
+                                   trait_type_id: ast::DefId,
+                                   span: Span)
+                                   -> ty::t
+                                   where AC: AstConv<'tcx>, RS: RegionScope {
+    // Find the trait that this associated type belongs to.
+    let trait_did = match ty::impl_or_trait_item(this.tcx(),
+                                                 trait_type_id).container() {
+        ty::ImplContainer(_) => {
+            this.tcx().sess.span_bug(span,
+                                     "associated_ty_to_ty(): impl associated \
+                                      types shouldn't go through this \
+                                      function")
+        }
+        ty::TraitContainer(trait_id) => trait_id,
+    };
+
+    let for_type = ast_ty_to_ty(this, rscope, for_ast_type);
+    if !this.associated_types_of_trait_are_valid(for_type, trait_did) {
+        this.tcx().sess.span_err(span,
+                                 "this associated type is not \
+                                  allowed in this context");
+        return ty::mk_err()
+    }
+
+    let trait_ref = ast_path_to_trait_ref(this,
+                                          rscope,
+                                          trait_did,
+                                          None,
+                                          Some(for_type),
+                                          trait_path);
+    let trait_def = this.get_trait_def(trait_did);
+    for type_parameter in trait_def.generics.types.iter() {
+        if type_parameter.def_id == trait_type_id {
+            return *trait_ref.substs.types.get(type_parameter.space,
+                                               type_parameter.index)
+        }
+    }
+    this.tcx().sess.span_bug(span,
+                             "this associated type didn't get added \
+                              as a parameter for some reason")
+}
+
 // Parses the programmer's textual representation of a type into our
 // internal notion of a type.
 pub fn ast_ty_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
@@ -816,8 +923,12 @@ pub fn ast_ty_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
                 }
                 match a_def {
                     def::DefTrait(trait_def_id) => {
-                        let result = ast_path_to_trait_ref(
-                            this, rscope, trait_def_id, None, path);
+                        let result = ast_path_to_trait_ref(this,
+                                                           rscope,
+                                                           trait_def_id,
+                                                           None,
+                                                           None,
+                                                           path);
                         let empty_bounds: &[ast::TyParamBound] = &[];
                         let ast_bounds = match *bounds {
                             Some(ref b) => b.as_slice(),
@@ -856,6 +967,23 @@ pub fn ast_ty_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
                     def::DefPrimTy(_) => {
                         fail!("DefPrimTy arm missed in previous ast_ty_to_prim_ty call");
                     }
+                    def::DefAssociatedTy(trait_type_id) => {
+                        let path_str = tcx.map.path_to_string(
+                            tcx.map.get_parent(trait_type_id.node));
+                        tcx.sess.span_err(ast_ty.span,
+                                          format!("ambiguous associated \
+                                                   type; specify the type \
+                                                   using the syntax `<Type \
+                                                   as {}>::{}`",
+                                                  path_str,
+                                                  token::get_ident(
+                                                      path.segments
+                                                          .last()
+                                                          .unwrap()
+                                                          .identifier)
+                                                  .get()).as_slice());
+                        ty::mk_err()
+                    }
                     _ => {
                         tcx.sess.span_fatal(ast_ty.span,
                                             format!("found value name used \
@@ -864,6 +992,28 @@ pub fn ast_ty_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
                     }
                 }
             }
+            ast::TyQPath(ref qpath) => {
+                match tcx.def_map.borrow().find(&ast_ty.id) {
+                    None => {
+                        tcx.sess.span_bug(ast_ty.span,
+                                          "unbound qualified path")
+                    }
+                    Some(&def::DefAssociatedTy(trait_type_id)) => {
+                        associated_ty_to_ty(this,
+                                            rscope,
+                                            &qpath.trait_name,
+                                            &*qpath.for_type,
+                                            trait_type_id,
+                                            ast_ty.span)
+                    }
+                    Some(_) => {
+                        tcx.sess.span_err(ast_ty.span,
+                                          "this qualified path does not name \
+                                           an associated type");
+                        ty::mk_err()
+                    }
+                }
+            }
             ast::TyFixedLengthVec(ref ty, ref e) => {
                 match const_eval::eval_const_expr_partial(tcx, &**e) {
                     Ok(ref r) => {
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index d3cae157d3b..5d2ce7b080e 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -226,6 +226,7 @@ fn get_method_index(tcx: &ty::ctxt,
             for trait_item in trait_items.iter() {
                 match *trait_item {
                     ty::MethodTraitItem(_) => method_count += 1,
+                    ty::TypeTraitItem(_) => {}
                 }
             }
             true
@@ -531,6 +532,11 @@ impl<'a, 'tcx> LookupContext<'a, 'tcx> {
                                                                .clone();
         let method = match trait_item {
             ty::MethodTraitItem(method) => method,
+            ty::TypeTraitItem(_) => {
+                self.tcx().sess.bug(
+                    "push_unboxed_closure_call_candidates_if_applicable(): \
+                     unexpected associated type in function trait")
+            }
         };
 
         // Make sure it has the right name!
@@ -730,11 +736,16 @@ impl<'a, 'tcx> LookupContext<'a, 'tcx> {
                         m.explicit_self != ty::StaticExplicitSelfCategory &&
                         m.ident.name == self.m_name
                     }
+                    ty::TypeTraitItem(_) => false,
                 }
             }) {
                 Some(pos) => {
                     let method = match *trait_items.get(pos) {
                         ty::MethodTraitItem(ref method) => (*method).clone(),
+                        ty::TypeTraitItem(_) => {
+                            tcx.sess.bug("typechecking associated type as \
+                                          though it were a method")
+                        }
                     };
 
                     match mk_cand(self,
@@ -812,7 +823,10 @@ impl<'a, 'tcx> LookupContext<'a, 'tcx> {
                                          m.ident().name == self.m_name
                                      }) {
             Some(ty::MethodTraitItem(method)) => method,
-            None => { return; } // No method with the right name.
+            Some(ty::TypeTraitItem(_)) | None => {
+                // No method with the right name.
+                return
+            }
         };
 
         // determine the `self` of the impl with fresh
@@ -1575,7 +1589,7 @@ impl<'a, 'tcx> LookupContext<'a, 'tcx> {
                     // If we're reporting statics, we want to report the trait
                     // definition if possible, rather than an impl
                     match ty::trait_item_of_item(self.tcx(), impl_did) {
-                        None => {
+                        None | Some(TypeTraitItemId(_)) => {
                             debug!("(report candidate) No trait method \
                                     found");
                             impl_did
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 2f5b6e1fa03..c8728d375f6 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -126,7 +126,7 @@ use std::mem::replace;
 use std::rc::Rc;
 use std::slice;
 use syntax::abi;
-use syntax::ast::{ProvidedMethod, RequiredMethod};
+use syntax::ast::{ProvidedMethod, RequiredMethod, TypeTraitItem};
 use syntax::ast;
 use syntax::ast_map;
 use syntax::ast_util::{local_def, PostExpansionMethod};
@@ -765,6 +765,9 @@ pub fn check_item(ccx: &CrateCtxt, it: &ast::Item) {
                 ast::MethodImplItem(ref m) => {
                     check_method_body(ccx, &impl_pty.generics, &**m);
                 }
+                ast::TypeImplItem(_) => {
+                    // Nothing to do here.
+                }
             }
         }
 
@@ -793,6 +796,9 @@ pub fn check_item(ccx: &CrateCtxt, it: &ast::Item) {
                 ProvidedMethod(ref m) => {
                     check_method_body(ccx, &trait_def.generics, &**m);
                 }
+                TypeTraitItem(_) => {
+                    // Nothing to do.
+                }
             }
         }
       }
@@ -898,6 +904,20 @@ fn check_impl_items_against_trait(ccx: &CrateCtxt,
                                                     &**trait_method_ty,
                                                     &impl_trait_ref.substs);
                             }
+                            _ => {
+                                // This is span_bug as it should have already been
+                                // caught in resolve.
+                                tcx.sess
+                                   .span_bug(impl_method.span,
+                                             format!("item `{}` is of a \
+                                                      different kind from \
+                                                      its trait `{}`",
+                                                     token::get_ident(
+                                                        impl_item_ty.ident()),
+                                                     pprust::path_to_string(
+                                                        &ast_trait_ref.path))
+                                             .as_slice());
+                            }
                         }
                     }
                     None => {
@@ -913,10 +933,57 @@ fn check_impl_items_against_trait(ccx: &CrateCtxt,
                     }
                 }
             }
+            ast::TypeImplItem(ref typedef) => {
+                let typedef_def_id = local_def(typedef.id);
+                let typedef_ty = ty::impl_or_trait_item(ccx.tcx,
+                                                        typedef_def_id);
+
+                // If this is an impl of an associated type, find the
+                // corresponding type definition in the trait.
+                let opt_associated_type =
+                    trait_items.iter()
+                               .find(|ti| {
+                                   ti.ident().name == typedef_ty.ident().name
+                               });
+                match opt_associated_type {
+                    Some(associated_type) => {
+                        match (associated_type, &typedef_ty) {
+                            (&ty::TypeTraitItem(_),
+                             &ty::TypeTraitItem(_)) => {}
+                            _ => {
+                                // This is `span_bug` as it should have
+                                // already been caught in resolve.
+                                tcx.sess
+                                   .span_bug(typedef.span,
+                                             format!("item `{}` is of a \
+                                                      different kind from \
+                                                      its trait `{}`",
+                                                     token::get_ident(
+                                                        typedef_ty.ident()),
+                                                     pprust::path_to_string(
+                                                        &ast_trait_ref.path))
+                                             .as_slice());
+                            }
+                        }
+                    }
+                    None => {
+                        // This is `span_bug` as it should have already been
+                        // caught in resolve.
+                        tcx.sess.span_bug(
+                            typedef.span,
+                            format!(
+                                "associated type `{}` is not a member of \
+                                 trait `{}`",
+                                token::get_ident(typedef_ty.ident()),
+                                pprust::path_to_string(
+                                    &ast_trait_ref.path)).as_slice());
+                    }
+                }
+            }
         }
     }
 
-    // Check for missing methods from trait
+    // Check for missing items from trait
     let provided_methods = ty::provided_trait_methods(tcx,
                                                       impl_trait_ref.def_id);
     let mut missing_methods = Vec::new();
@@ -929,6 +996,7 @@ fn check_impl_items_against_trait(ccx: &CrateCtxt,
                             ast::MethodImplItem(ref m) => {
                                 m.pe_ident().name == trait_method.ident.name
                             }
+                            ast::TypeImplItem(_) => false,
                         }
                     });
                 let is_provided =
@@ -940,12 +1008,27 @@ fn check_impl_items_against_trait(ccx: &CrateCtxt,
                                 token::get_ident(trait_method.ident)));
                 }
             }
+            ty::TypeTraitItem(ref associated_type) => {
+                let is_implemented = impl_items.iter().any(|ii| {
+                    match *ii {
+                        ast::TypeImplItem(ref typedef) => {
+                            typedef.ident.name == associated_type.ident.name
+                        }
+                        ast::MethodImplItem(_) => false,
+                    }
+                });
+                if !is_implemented {
+                    missing_methods.push(
+                        format!("`{}`",
+                                token::get_ident(associated_type.ident)));
+                }
+            }
         }
     }
 
     if !missing_methods.is_empty() {
         span_err!(tcx.sess, impl_span, E0046,
-            "not all trait methods implemented, missing: {}",
+            "not all trait items implemented, missing: {}",
             missing_methods.connect(", "));
     }
 }
@@ -969,7 +1052,8 @@ fn compare_impl_method(tcx: &ty::ctxt,
                        impl_m_body_id: ast::NodeId,
                        trait_m: &ty::Method,
                        trait_to_impl_substs: &subst::Substs) {
-    debug!("compare_impl_method()");
+    debug!("compare_impl_method(trait_to_impl_substs={})",
+           trait_to_impl_substs.repr(tcx));
     let infcx = infer::new_infer_ctxt(tcx);
 
     // Try to give more informative error messages about self typing
@@ -1138,11 +1222,13 @@ fn compare_impl_method(tcx: &ty::ctxt,
         // FIXME(pcwalton): We could be laxer here regarding sub- and super-
         // traits, but I doubt that'll be wanted often, so meh.
         for impl_trait_bound in impl_param_def.bounds.trait_bounds.iter() {
+            debug!("compare_impl_method(): impl-trait-bound subst");
             let impl_trait_bound =
                 impl_trait_bound.subst(tcx, &impl_to_skol_substs);
 
             let mut ok = false;
             for trait_bound in trait_param_def.bounds.trait_bounds.iter() {
+                debug!("compare_impl_method(): trait-bound subst");
                 let trait_bound =
                     trait_bound.subst(tcx, &trait_to_skol_substs);
                 let infcx = infer::new_infer_ctxt(tcx);
@@ -1185,6 +1271,9 @@ fn compare_impl_method(tcx: &ty::ctxt,
     // other words, anyone expecting to call a method with the type
     // from the trait, can safely call a method with the type from the
     // impl instead.
+    debug!("checking trait method for compatibility: impl ty {}, trait ty {}",
+           impl_fty.repr(tcx),
+           trait_fty.repr(tcx));
     match infer::mk_subty(&infcx, false, infer::MethodCompatCheck(impl_m_span),
                           impl_fty, trait_fty) {
         Ok(()) => {}
@@ -1513,6 +1602,21 @@ impl<'a, 'tcx> AstConv<'tcx> for FnCtxt<'a, 'tcx> {
     fn ty_infer(&self, _span: Span) -> ty::t {
         self.infcx().next_ty_var()
     }
+
+    fn associated_types_of_trait_are_valid(&self, _: ty::t, _: ast::DefId)
+                                           -> bool {
+        false
+    }
+
+    fn associated_type_binding(&self,
+                               span: Span,
+                               _: Option<ty::t>,
+                               _: ast::DefId,
+                               _: ast::DefId)
+                               -> ty::t {
+        self.tcx().sess.span_err(span, "unsupported associated type binding");
+        ty::mk_err()
+    }
 }
 
 impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
@@ -4938,6 +5042,7 @@ pub fn polytype_for_def(fcx: &FnCtxt,
       }
       def::DefTrait(_) |
       def::DefTy(..) |
+      def::DefAssociatedTy(..) |
       def::DefPrimTy(_) |
       def::DefTyParam(..)=> {
         fcx.ccx.tcx.sess.span_bug(sp, "expected value, found type");
@@ -5048,6 +5153,7 @@ pub fn instantiate_path(fcx: &FnCtxt,
         def::DefVariant(..) |
         def::DefTyParamBinder(..) |
         def::DefTy(..) |
+        def::DefAssociatedTy(..) |
         def::DefTrait(..) |
         def::DefPrimTy(..) |
         def::DefTyParam(..) => {
diff --git a/src/librustc/middle/typeck/coherence/mod.rs b/src/librustc/middle/typeck/coherence/mod.rs
index 76c5cab234f..cef6e31b937 100644
--- a/src/librustc/middle/typeck/coherence/mod.rs
+++ b/src/librustc/middle/typeck/coherence/mod.rs
@@ -22,7 +22,7 @@ use middle::subst;
 use middle::subst::{Substs};
 use middle::ty::get;
 use middle::ty::{ImplContainer, ImplOrTraitItemId, MethodTraitItemId};
-use middle::ty::{lookup_item_type};
+use middle::ty::{TypeTraitItemId, lookup_item_type};
 use middle::ty::{t, ty_bool, ty_char, ty_bot, ty_box, ty_enum, ty_err};
 use middle::ty::{ty_str, ty_vec, ty_float, ty_infer, ty_int, ty_nil, ty_open};
 use middle::ty::{ty_param, Polytype, ty_ptr};
@@ -332,6 +332,9 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
                                     MethodTraitItemId(
                                         local_def(ast_method.id))
                                 }
+                                ast::TypeImplItem(ref typedef) => {
+                                    TypeTraitItemId(local_def(typedef.id))
+                                }
                             }
                         }).collect();
 
@@ -393,6 +396,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
                            .insert(item_def_id.def_id(), source);
                     }
                 }
+                ty::TypeTraitItem(_) => {}
             }
         }
 
diff --git a/src/librustc/middle/typeck/collect.rs b/src/librustc/middle/typeck/collect.rs
index dedb860967c..b7aa7656ae9 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -138,7 +138,13 @@ pub trait ToTy {
     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> ty::t;
 }
 
-impl<'a, 'tcx> ToTy for CrateCtxt<'a, 'tcx> {
+impl<'a,'tcx> ToTy for ImplCtxt<'a,'tcx> {
+    fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> ty::t {
+        ast_ty_to_ty(self, rs, ast_ty)
+    }
+}
+
+impl<'a,'tcx> ToTy for CrateCtxt<'a,'tcx> {
     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> ty::t {
         ast_ty_to_ty(self, rs, ast_ty)
     }
@@ -158,6 +164,9 @@ impl<'a, 'tcx> AstConv<'tcx> for CrateCtxt<'a, 'tcx> {
                 let abi = self.tcx.map.get_foreign_abi(id.node);
                 ty_of_foreign_item(self, &*foreign_item, abi)
             }
+            Some(ast_map::NodeTraitItem(trait_item)) => {
+                ty_of_trait_item(self, &*trait_item)
+            }
             x => {
                 self.tcx.sess.bug(format!("unexpected sort of node \
                                            in get_item_ty(): {:?}",
@@ -175,6 +184,22 @@ impl<'a, 'tcx> AstConv<'tcx> for CrateCtxt<'a, 'tcx> {
                   "the type placeholder `_` is not allowed within types on item signatures.");
         ty::mk_err()
     }
+
+    fn associated_types_of_trait_are_valid(&self, _: ty::t, _: ast::DefId)
+                                           -> bool {
+        false
+    }
+
+    fn associated_type_binding(&self,
+                               span: Span,
+                               _: Option<ty::t>,
+                               _: ast::DefId,
+                               _: ast::DefId)
+                               -> ty::t {
+        self.tcx().sess.span_err(span, "associated types may not be \
+                                        referenced here");
+        ty::mk_err()
+    }
 }
 
 pub fn get_enum_variant_types(ccx: &CrateCtxt,
@@ -201,7 +226,10 @@ pub fn get_enum_variant_types(ccx: &CrateCtxt,
 
             ast::StructVariantKind(ref struct_def) => {
                 let pty = Polytype {
-                    generics: ty_generics_for_type(ccx, generics),
+                    generics: ty_generics_for_type(
+                        ccx,
+                        generics,
+                        DontCreateTypeParametersForAssociatedTypes),
                     ty: enum_ty
                 };
 
@@ -214,7 +242,10 @@ pub fn get_enum_variant_types(ccx: &CrateCtxt,
         };
 
         let pty = Polytype {
-            generics: ty_generics_for_type(ccx, generics),
+            generics: ty_generics_for_type(
+                          ccx,
+                          generics,
+                          DontCreateTypeParametersForAssociatedTypes),
             ty: result_ty
         };
 
@@ -244,6 +275,7 @@ fn collect_trait_methods(ccx: &CrateCtxt,
                                             ccx,
                                             trait_id,
                                             &trait_def.generics,
+                                            trait_items.as_slice(),
                                             &m.id,
                                             &m.ident,
                                             &m.explicit_self,
@@ -257,6 +289,7 @@ fn collect_trait_methods(ccx: &CrateCtxt,
                                             ccx,
                                             trait_id,
                                             &trait_def.generics,
+                                            trait_items.as_slice(),
                                             &m.id,
                                             &m.pe_ident(),
                                             m.pe_explicit_self(),
@@ -265,6 +298,12 @@ fn collect_trait_methods(ccx: &CrateCtxt,
                                             &m.pe_fn_style(),
                                             &*m.pe_fn_decl())
                                     }
+                                    ast::TypeTraitItem(ref at) => {
+                                        tcx.sess.span_bug(at.span,
+                                                          "there shouldn't \
+                                                           be a type trait \
+                                                           item here")
+                                    }
                                 });
 
                                 if ty_method.explicit_self ==
@@ -277,6 +316,22 @@ fn collect_trait_methods(ccx: &CrateCtxt,
                                    .insert(ty_method.def_id,
                                            ty::MethodTraitItem(ty_method));
                             }
+                            ast::TypeTraitItem(ref ast_associated_type) => {
+                                let trait_did = local_def(trait_id);
+                                let associated_type = ty::AssociatedType {
+                                    ident: ast_associated_type.ident,
+                                    vis: ast::Public,
+                                    def_id: local_def(ast_associated_type.id),
+                                    container: TraitContainer(trait_did),
+                                };
+
+                                let trait_item = ty::TypeTraitItem(Rc::new(
+                                        associated_type));
+                                tcx.impl_or_trait_items
+                                   .borrow_mut()
+                                   .insert(associated_type.def_id,
+                                           trait_item);
+                            }
                         }
                     }
 
@@ -293,6 +348,9 @@ fn collect_trait_methods(ccx: &CrateCtxt,
                                     ty::MethodTraitItemId(local_def(
                                             method.id))
                                 }
+                                ast::TypeTraitItem(ref typedef) => {
+                                    ty::TypeTraitItemId(local_def(typedef.id))
+                                }
                             }
                         }).collect());
 
@@ -314,9 +372,10 @@ fn collect_trait_methods(ccx: &CrateCtxt,
                 ty: ty::mk_bare_fn(ccx.tcx, m.fty.clone()) });
     }
 
-    fn ty_method_of_trait_method(this: &CrateCtxt,
+    fn ty_method_of_trait_method(ccx: &CrateCtxt,
                                  trait_id: ast::NodeId,
                                  trait_generics: &ty::Generics,
+                                 trait_items: &[ast::TraitItem],
                                  m_id: &ast::NodeId,
                                  m_ident: &ast::Ident,
                                  m_explicit_self: &ast::ExplicitSelf,
@@ -325,20 +384,31 @@ fn collect_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, explicit_self_category) =
-            astconv::ty_of_method(this,
+        let ty_generics =
+            ty_generics_for_fn_or_method(
+                ccx,
+                m_generics,
+                (*trait_generics).clone(),
+                DontCreateTypeParametersForAssociatedTypes);
+
+        let (fty, explicit_self_category) = {
+            let tmcx = TraitMethodCtxt {
+                ccx: ccx,
+                trait_id: local_def(trait_id),
+                trait_items: trait_items.as_slice(),
+                method_generics: &ty_generics,
+            };
+            let trait_self_ty = ty::mk_self_type(tmcx.tcx(),
+                                                 local_def(trait_id));
+            astconv::ty_of_method(&tmcx,
                                   *m_id,
                                   *m_fn_style,
                                   trait_self_ty,
                                   m_explicit_self,
                                   m_decl,
-                                  m_abi);
-        let ty_generics =
-            ty_generics_for_fn_or_method(this,
-                                         m_generics,
-                                         (*trait_generics).clone());
+                                  m_abi)
+        };
+
         ty::Method::new(
             *m_ident,
             ty_generics,
@@ -386,12 +456,73 @@ pub fn convert_field(ccx: &CrateCtxt,
     }
 }
 
-fn convert_methods<'a, I: Iterator<&'a ast::Method>>(ccx: &CrateCtxt,
-        container: ImplOrTraitItemContainer,
-        mut ms: I,
-        untransformed_rcvr_ty: ty::t,
-        rcvr_ty_generics: &ty::Generics,
-        rcvr_visibility: ast::Visibility) {
+fn convert_associated_type(ccx: &CrateCtxt,
+                           trait_def: &ty::TraitDef,
+                           associated_type: &ast::AssociatedType)
+                           -> ty::Polytype {
+    // Find the type parameter ID corresponding to this
+    // associated type.
+    let type_parameter_def = trait_def.generics
+                                      .types
+                                      .get_slice(subst::TypeSpace)
+                                      .iter()
+                                      .find(|def| {
+        def.def_id == local_def(associated_type.id)
+    });
+    let type_parameter_def = match type_parameter_def {
+        Some(type_parameter_def) => type_parameter_def,
+        None => {
+            ccx.tcx().sess.span_bug(associated_type.span,
+                                    "`convert_associated_type()` didn't find \
+                                     a type parameter ID corresponding to \
+                                     this type")
+        }
+    };
+    let param_type = ty::mk_param(ccx.tcx,
+                                  subst::TypeSpace,
+                                  type_parameter_def.index,
+                                  local_def(associated_type.id));
+    ccx.tcx.tcache.borrow_mut().insert(local_def(associated_type.id),
+                                       Polytype {
+                                        generics: ty::Generics::empty(),
+                                        ty: param_type,
+                                       });
+    write_ty_to_tcx(ccx.tcx, associated_type.id, param_type);
+
+    let associated_type = Rc::new(ty::AssociatedType {
+        ident: associated_type.ident,
+        vis: ast::Public,
+        def_id: local_def(associated_type.id),
+        container: TraitContainer(trait_def.trait_ref.def_id),
+    });
+    ccx.tcx
+       .impl_or_trait_items
+       .borrow_mut()
+       .insert(associated_type.def_id,
+               ty::TypeTraitItem(associated_type));
+
+    Polytype {
+        generics: ty::Generics::empty(),
+        ty: param_type,
+    }
+}
+
+enum ConvertMethodContext<'a> {
+    /// Used when converting implementation methods.
+    ImplConvertMethodContext,
+    /// Used when converting method signatures. The def ID is the def ID of
+    /// the trait we're translating.
+    TraitConvertMethodContext(ast::DefId, &'a [ast::TraitItem]),
+}
+
+fn convert_methods<'a,I>(ccx: &CrateCtxt,
+                         convert_method_context: ConvertMethodContext,
+                         container: ImplOrTraitItemContainer,
+                         mut ms: I,
+                         untransformed_rcvr_ty: ty::t,
+                         rcvr_ty_generics: &ty::Generics,
+                         rcvr_visibility: ast::Visibility)
+                         where I: Iterator<&'a ast::Method> {
     debug!("convert_methods(untransformed_rcvr_ty={}, \
             rcvr_ty_generics={})",
            untransformed_rcvr_ty.repr(ccx.tcx),
@@ -400,11 +531,12 @@ fn convert_methods<'a, I: Iterator<&'a ast::Method>>(ccx: &CrateCtxt,
     let tcx = ccx.tcx;
     let mut seen_methods = HashSet::new();
     for m in ms {
-        if !seen_methods.insert(m.pe_ident().repr(ccx.tcx)) {
+        if !seen_methods.insert(m.pe_ident().repr(tcx)) {
             tcx.sess.span_err(m.span, "duplicate method in trait impl");
         }
 
         let mty = Rc::new(ty_of_method(ccx,
+                                       convert_method_context,
                                        container,
                                        m,
                                        untransformed_rcvr_ty,
@@ -412,9 +544,9 @@ fn convert_methods<'a, I: Iterator<&'a ast::Method>>(ccx: &CrateCtxt,
                                        rcvr_visibility));
         let fty = ty::mk_bare_fn(tcx, mty.fty.clone());
         debug!("method {} (id {}) has type {}",
-                m.pe_ident().repr(ccx.tcx),
+                m.pe_ident().repr(tcx),
                 m.id,
-                fty.repr(ccx.tcx));
+                fty.repr(tcx));
         tcx.tcache.borrow_mut().insert(
             local_def(m.id),
             Polytype {
@@ -433,6 +565,7 @@ fn convert_methods<'a, I: Iterator<&'a ast::Method>>(ccx: &CrateCtxt,
     }
 
     fn ty_of_method(ccx: &CrateCtxt,
+                    convert_method_context: ConvertMethodContext,
                     container: ImplOrTraitItemContainer,
                     m: &ast::Method,
                     untransformed_rcvr_ty: ty::t,
@@ -453,14 +586,43 @@ fn convert_methods<'a, I: Iterator<&'a ast::Method>>(ccx: &CrateCtxt,
             _ => m.pe_abi(),
         };
 
-        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(),
-                                  real_abi);
+        let m_ty_generics =
+            ty_generics_for_fn_or_method(
+                ccx,
+                m.pe_generics(),
+                (*rcvr_ty_generics).clone(),
+                CreateTypeParametersForAssociatedTypes);
+
+        let (fty, explicit_self_category) = match convert_method_context {
+            ImplConvertMethodContext => {
+                let imcx = ImplMethodCtxt {
+                    ccx: ccx,
+                    method_generics: &m_ty_generics,
+                };
+                astconv::ty_of_method(&imcx,
+                                      m.id,
+                                      m.pe_fn_style(),
+                                      untransformed_rcvr_ty,
+                                      m.pe_explicit_self(),
+                                      &*m.pe_fn_decl(),
+                                      real_abi)
+            }
+            TraitConvertMethodContext(trait_id, trait_items) => {
+                let tmcx = TraitMethodCtxt {
+                    ccx: ccx,
+                    trait_id: trait_id,
+                    trait_items: trait_items,
+                    method_generics: &m_ty_generics,
+                };
+                astconv::ty_of_method(&tmcx,
+                                      m.id,
+                                      m.pe_fn_style(),
+                                      untransformed_rcvr_ty,
+                                      m.pe_explicit_self(),
+                                      &*m.pe_fn_decl(),
+                                      real_abi)
+            }
+        };
 
         // if the method specifies a visibility, use that, otherwise
         // inherit the visibility from the impl (so `foo` in `pub impl
@@ -468,9 +630,6 @@ fn convert_methods<'a, I: Iterator<&'a ast::Method>>(ccx: &CrateCtxt,
         // foo(); }`).
         let method_vis = m.pe_vis().inherit_from(rcvr_visibility);
 
-        let m_ty_generics =
-            ty_generics_for_fn_or_method(ccx, m.pe_generics(),
-                                         (*rcvr_ty_generics).clone());
         ty::Method::new(m.pe_ident(),
                         m_ty_generics,
                         fty,
@@ -507,6 +666,404 @@ pub fn ensure_no_ty_param_bounds(ccx: &CrateCtxt,
     }
 }
 
+fn is_associated_type_valid_for_param(ty: ty::t,
+                                      trait_id: ast::DefId,
+                                      generics: &ty::Generics)
+                                      -> bool {
+    match ty::get(ty).sty {
+        ty::ty_param(param_ty) => {
+            let type_parameter = generics.types.get(param_ty.space,
+                                                    param_ty.idx);
+            for trait_bound in type_parameter.bounds.trait_bounds.iter() {
+                if trait_bound.def_id == trait_id {
+                    return true
+                }
+            }
+        }
+        _ => {}
+    }
+
+    false
+}
+
+fn find_associated_type_in_generics(tcx: &ty::ctxt,
+                                    span: Span,
+                                    ty: Option<ty::t>,
+                                    associated_type_id: ast::DefId,
+                                    generics: &ty::Generics)
+                                    -> ty::t {
+    let ty = match ty {
+        None => {
+            tcx.sess.span_bug(span,
+                              "find_associated_type_in_generics(): no self \
+                               type")
+        }
+        Some(ty) => ty,
+    };
+
+    match ty::get(ty).sty {
+        ty::ty_param(ref param_ty) => {
+            /*let type_parameter = generics.types.get(param_ty.space,
+                                                    param_ty.idx);
+            let param_id = type_parameter.def_id;*/
+            let param_id = param_ty.def_id;
+            for type_parameter in generics.types.iter() {
+                if type_parameter.def_id == associated_type_id
+                    && type_parameter.associated_with == Some(param_id) {
+                    return ty::mk_param_from_def(tcx, type_parameter)
+                }
+            }
+
+            tcx.sess.span_bug(span,
+                              "find_associated_type_in_generics(): didn't \
+                               find associated type anywhere in the generics \
+                               list")
+        }
+        _ => {
+            tcx.sess.span_bug(span,
+                              "find_associated_type_in_generics(): self type \
+                               is not a parameter")
+
+        }
+    }
+}
+
+fn type_is_self(ty: ty::t) -> bool {
+    match ty::get(ty).sty {
+        ty::ty_param(ref param_ty) if param_ty.is_self() => true,
+        _ => false,
+    }
+}
+
+struct ImplCtxt<'a,'tcx:'a> {
+    ccx: &'a CrateCtxt<'a,'tcx>,
+    opt_trait_ref_id: Option<ast::DefId>,
+    impl_items: &'a [ast::ImplItem],
+    impl_generics: &'a ty::Generics,
+}
+
+impl<'a,'tcx> AstConv<'tcx> for ImplCtxt<'a,'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
+        self.ccx.tcx
+    }
+
+    fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype {
+        self.ccx.get_item_ty(id)
+    }
+
+    fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef> {
+        self.ccx.get_trait_def(id)
+    }
+
+    fn ty_infer(&self, span: Span) -> ty::t {
+        self.ccx.ty_infer(span)
+    }
+
+    fn associated_types_of_trait_are_valid(&self,
+                                           ty: ty::t,
+                                           trait_id: ast::DefId)
+                                           -> bool {
+        // OK if the trait with the associated type is the trait we're
+        // implementing.
+        match self.opt_trait_ref_id {
+            Some(trait_ref_id) if trait_ref_id == trait_id => {
+                if type_is_self(ty) {
+                    return true
+                }
+            }
+            Some(_) | None => {}
+        }
+
+        // OK if the trait with the associated type is one of the traits in
+        // our bounds.
+        is_associated_type_valid_for_param(ty, trait_id, self.impl_generics)
+    }
+
+    fn associated_type_binding(&self,
+                               span: Span,
+                               ty: Option<ty::t>,
+                               trait_id: ast::DefId,
+                               associated_type_id: ast::DefId)
+                               -> ty::t {
+        ensure_associated_types(self, trait_id);
+        let associated_type_ids = ty::associated_types_for_trait(self.ccx.tcx,
+                                                                 trait_id);
+        match self.opt_trait_ref_id {
+            Some(trait_ref_id) if trait_ref_id == trait_id => {
+                // It's an associated type on the trait that we're
+                // implementing.
+                let associated_type_id =
+                    associated_type_ids.iter()
+                                       .find(|id| {
+                                           id.def_id == associated_type_id
+                                       })
+                                       .expect("associated_type_binding(): \
+                                                expected associated type ID \
+                                                in trait");
+                let associated_type =
+                    ty::impl_or_trait_item(self.ccx.tcx,
+                                           associated_type_id.def_id);
+                for impl_item in self.impl_items.iter() {
+                    match *impl_item {
+                        ast::MethodImplItem(_) => {}
+                        ast::TypeImplItem(ref typedef) => {
+                            if associated_type.ident().name == typedef.ident
+                                                                      .name {
+                                return self.ccx.to_ty(&ExplicitRscope,
+                                                      &*typedef.typ)
+                            }
+                        }
+                    }
+                }
+                self.ccx
+                    .tcx
+                    .sess
+                    .span_bug(span,
+                              "ImplCtxt::associated_type_binding(): didn't \
+                               find associated type")
+            }
+            Some(_) | None => {}
+        }
+
+        // OK then, it should be an associated type on one of the traits in
+        // our bounds.
+        find_associated_type_in_generics(self.ccx.tcx,
+                                         span,
+                                         ty,
+                                         associated_type_id,
+                                         self.impl_generics)
+    }
+}
+
+struct FnCtxt<'a,'tcx:'a> {
+    ccx: &'a CrateCtxt<'a,'tcx>,
+    generics: &'a ty::Generics,
+}
+
+impl<'a,'tcx> AstConv<'tcx> for FnCtxt<'a,'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
+        self.ccx.tcx
+    }
+
+    fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype {
+        self.ccx.get_item_ty(id)
+    }
+
+    fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef> {
+        self.ccx.get_trait_def(id)
+    }
+
+    fn ty_infer(&self, span: Span) -> ty::t {
+        self.ccx.ty_infer(span)
+    }
+
+    fn associated_types_of_trait_are_valid(&self,
+                                           ty: ty::t,
+                                           trait_id: ast::DefId)
+                                           -> bool {
+        // OK if the trait with the associated type is one of the traits in
+        // our bounds.
+        is_associated_type_valid_for_param(ty, trait_id, self.generics)
+    }
+
+    fn associated_type_binding(&self,
+                               span: Span,
+                               ty: Option<ty::t>,
+                               _: ast::DefId,
+                               associated_type_id: ast::DefId)
+                               -> ty::t {
+        debug!("collect::FnCtxt::associated_type_binding()");
+
+        // The ID should map to an associated type on one of the traits in
+        // our bounds.
+        find_associated_type_in_generics(self.ccx.tcx,
+                                         span,
+                                         ty,
+                                         associated_type_id,
+                                         self.generics)
+    }
+}
+
+struct ImplMethodCtxt<'a,'tcx:'a> {
+    ccx: &'a CrateCtxt<'a,'tcx>,
+    method_generics: &'a ty::Generics,
+}
+
+impl<'a,'tcx> AstConv<'tcx> for ImplMethodCtxt<'a,'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
+        self.ccx.tcx
+    }
+
+    fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype {
+        self.ccx.get_item_ty(id)
+    }
+
+    fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef> {
+        self.ccx.get_trait_def(id)
+    }
+
+    fn ty_infer(&self, span: Span) -> ty::t {
+        self.ccx.ty_infer(span)
+    }
+
+    fn associated_types_of_trait_are_valid(&self,
+                                           ty: ty::t,
+                                           trait_id: ast::DefId)
+                                           -> bool {
+        is_associated_type_valid_for_param(ty, trait_id, self.method_generics)
+    }
+
+    fn associated_type_binding(&self,
+                               span: Span,
+                               ty: Option<ty::t>,
+                               _: ast::DefId,
+                               associated_type_id: ast::DefId)
+                               -> ty::t {
+        debug!("collect::ImplMethodCtxt::associated_type_binding()");
+
+        // The ID should map to an associated type on one of the traits in
+        // our bounds.
+        find_associated_type_in_generics(self.ccx.tcx,
+                                         span,
+                                         ty,
+                                         associated_type_id,
+                                         self.method_generics)
+    }
+}
+
+struct TraitMethodCtxt<'a,'tcx:'a> {
+    ccx: &'a CrateCtxt<'a,'tcx>,
+    trait_id: ast::DefId,
+    trait_items: &'a [ast::TraitItem],
+    method_generics: &'a ty::Generics,
+}
+
+impl<'a,'tcx> AstConv<'tcx> for TraitMethodCtxt<'a,'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
+        self.ccx.tcx
+    }
+
+    fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype {
+        self.ccx.get_item_ty(id)
+    }
+
+    fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef> {
+        self.ccx.get_trait_def(id)
+    }
+
+    fn ty_infer(&self, span: Span) -> ty::t {
+        self.ccx.ty_infer(span)
+    }
+
+    fn associated_types_of_trait_are_valid(&self,
+                                           ty: ty::t,
+                                           trait_id: ast::DefId)
+                                           -> bool {
+        // OK if the trait with the associated type is this trait.
+        if self.trait_id == trait_id && type_is_self(ty) {
+            return true
+        }
+
+        // OK if the trait with the associated type is one of the traits in
+        // our bounds.
+        is_associated_type_valid_for_param(ty, trait_id, self.method_generics)
+    }
+
+    fn associated_type_binding(&self,
+                               span: Span,
+                               ty: Option<ty::t>,
+                               trait_id: ast::DefId,
+                               associated_type_id: ast::DefId)
+                               -> ty::t {
+        debug!("collect::TraitMethodCtxt::associated_type_binding()");
+
+        // If this is one of our own associated types, return it.
+        if trait_id == self.trait_id {
+            let mut index = 0;
+            for item in self.trait_items.iter() {
+                match *item {
+                    ast::RequiredMethod(_) | ast::ProvidedMethod(_) => {}
+                    ast::TypeTraitItem(ref item) => {
+                        if local_def(item.id) == associated_type_id {
+                            return ty::mk_param(self.tcx(),
+                                                subst::TypeSpace,
+                                                index,
+                                                associated_type_id)
+                        }
+                        index += 1;
+                    }
+                }
+            }
+            self.ccx
+                .tcx
+                .sess
+                .span_bug(span,
+                          "TraitMethodCtxt::associated_type_binding(): \
+                           didn't find associated type anywhere in the item \
+                           list")
+        }
+
+        // The ID should map to an associated type on one of the traits in
+        // our bounds.
+        find_associated_type_in_generics(self.ccx.tcx,
+                                         span,
+                                         ty,
+                                         associated_type_id,
+                                         self.method_generics)
+    }
+}
+
+struct GenericsCtxt<'a,AC:'a> {
+    chain: &'a AC,
+    associated_types_generics: &'a ty::Generics,
+}
+
+impl<'a,'tcx,AC:AstConv<'tcx>> AstConv<'tcx> for GenericsCtxt<'a,AC> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
+        self.chain.tcx()
+    }
+
+    fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype {
+        self.chain.get_item_ty(id)
+    }
+
+    fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef> {
+        self.chain.get_trait_def(id)
+    }
+
+    fn ty_infer(&self, span: Span) -> ty::t {
+        self.chain.ty_infer(span)
+    }
+
+    fn associated_types_of_trait_are_valid(&self,
+                                           ty: ty::t,
+                                           trait_id: ast::DefId)
+                                           -> bool {
+        // OK if the trait with the associated type is one of the traits in
+        // our bounds.
+        is_associated_type_valid_for_param(ty,
+                                           trait_id,
+                                           self.associated_types_generics)
+    }
+
+    fn associated_type_binding(&self,
+                               span: Span,
+                               ty: Option<ty::t>,
+                               _: ast::DefId,
+                               associated_type_id: ast::DefId)
+                               -> ty::t {
+        debug!("collect::GenericsCtxt::associated_type_binding()");
+
+        // The ID should map to an associated type on one of the traits in
+        // our bounds.
+        find_associated_type_in_generics(self.chain.tcx(),
+                                         span,
+                                         ty,
+                                         associated_type_id,
+                                         self.associated_types_generics)
+    }
+}
+
 pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
     let tcx = ccx.tcx;
     debug!("convert: item {} with id {}", token::get_ident(it.ident), it.id);
@@ -525,14 +1082,22 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
                       ref opt_trait_ref,
                       ref selfty,
                       ref impl_items) => {
-            let ty_generics = ty_generics_for_type(ccx, generics);
+            // Create generics from the generics specified in the impl head.
+            let ty_generics = ty_generics_for_type(
+                    ccx,
+                    generics,
+                    CreateTypeParametersForAssociatedTypes);
+
             let selfty = ccx.to_ty(&ExplicitRscope, &**selfty);
             write_ty_to_tcx(tcx, it.id, selfty);
 
-            tcx.tcache.borrow_mut().insert(local_def(it.id),
-                                Polytype {
-                                    generics: ty_generics.clone(),
-                                    ty: selfty});
+            tcx.tcache
+               .borrow_mut()
+               .insert(local_def(it.id),
+                       Polytype {
+                        generics: ty_generics.clone(),
+                        ty: selfty,
+                       });
 
             // If there is a trait reference, treat the methods as always public.
             // This is to work around some incorrect behavior in privacy checking:
@@ -545,6 +1110,20 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
                 it.vis
             };
 
+            let icx = ImplCtxt {
+                ccx: ccx,
+                opt_trait_ref_id: match *opt_trait_ref {
+                    None => None,
+                    Some(ref ast_trait_ref) => {
+                        Some(lookup_def_tcx(tcx,
+                                            ast_trait_ref.path.span,
+                                            ast_trait_ref.ref_id).def_id())
+                    }
+                },
+                impl_items: impl_items.as_slice(),
+                impl_generics: &ty_generics,
+            };
+
             let mut methods = Vec::new();
             for impl_item in impl_items.iter() {
                 match *impl_item {
@@ -555,10 +1134,33 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
                                                method.pe_explicit_self());
                         methods.push(&**method);
                     }
+                    ast::TypeImplItem(ref typedef) => {
+                        let typ = icx.to_ty(&ExplicitRscope, &*typedef.typ);
+                        tcx.tcache
+                           .borrow_mut()
+                           .insert(local_def(typedef.id),
+                                   Polytype {
+                                    generics: ty::Generics::empty(),
+                                    ty: typ,
+                                   });
+                        write_ty_to_tcx(ccx.tcx, typedef.id, typ);
+
+                        let associated_type = Rc::new(ty::AssociatedType {
+                            ident: typedef.ident,
+                            vis: typedef.vis,
+                            def_id: local_def(typedef.id),
+                            container: ty::ImplContainer(local_def(it.id)),
+                        });
+                        tcx.impl_or_trait_items
+                           .borrow_mut()
+                           .insert(local_def(typedef.id),
+                                   ty::TypeTraitItem(associated_type));
+                    }
                 }
             }
 
             convert_methods(ccx,
+                            ImplConvertMethodContext,
                             ImplContainer(local_def(it.id)),
                             methods.into_iter(),
                             selfty,
@@ -566,7 +1168,7 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
                             parent_visibility);
 
             for trait_ref in opt_trait_ref.iter() {
-                instantiate_trait_ref(ccx, trait_ref, selfty);
+                instantiate_trait_ref(&icx, trait_ref, selfty, None);
             }
         },
         ast::ItemTrait(_, _, _, ref trait_methods) => {
@@ -595,16 +1197,27 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
                                                self_type,
                                                method.pe_explicit_self())
                     }
+                    ast::TypeTraitItem(ref associated_type) => {
+                        convert_associated_type(ccx,
+                                                &*trait_def,
+                                                &**associated_type);
+                    }
                 }
             }
 
             // Run convert_methods on the provided methods.
-            let untransformed_rcvr_ty = ty::mk_self_type(tcx, local_def(it.id));
+            let untransformed_rcvr_ty = ty::mk_self_type(tcx,
+                                                         local_def(it.id));
+            let convert_method_context =
+                TraitConvertMethodContext(local_def(it.id),
+                                          trait_methods.as_slice());
             convert_methods(ccx,
+                            convert_method_context,
                             TraitContainer(local_def(it.id)),
                             trait_methods.iter().filter_map(|m| match *m {
                                 ast::RequiredMethod(_) => None,
-                                ast::ProvidedMethod(ref m) => Some(&**m)
+                                ast::ProvidedMethod(ref m) => Some(&**m),
+                                ast::TypeTraitItem(_) => None,
                             }),
                             untransformed_rcvr_ty,
                             &trait_def.generics,
@@ -765,9 +1378,12 @@ pub fn convert_foreign(ccx: &CrateCtxt, i: &ast::ForeignItem) {
     ccx.tcx.tcache.borrow_mut().insert(local_def(i.id), pty);
 }
 
-pub fn instantiate_trait_ref(ccx: &CrateCtxt,
-                             ast_trait_ref: &ast::TraitRef,
-                             self_ty: ty::t) -> Rc<ty::TraitRef> {
+pub fn instantiate_trait_ref<'tcx,AC>(this: &AC,
+                                      ast_trait_ref: &ast::TraitRef,
+                                      self_ty: ty::t,
+                                      associated_type: Option<ty::t>)
+                                      -> Rc<ty::TraitRef>
+                                      where AC: AstConv<'tcx> {
     /*!
      * Instantiates the path for the given trait reference, assuming that
      * it's bound to a valid trait type. Returns the def_id for the defining
@@ -777,18 +1393,24 @@ pub fn instantiate_trait_ref(ccx: &CrateCtxt,
     // FIXME(#5121) -- distinguish early vs late lifetime params
     let rscope = ExplicitRscope;
 
-    match lookup_def_tcx(ccx.tcx, ast_trait_ref.path.span, ast_trait_ref.ref_id) {
+    match lookup_def_tcx(this.tcx(),
+                         ast_trait_ref.path.span,
+                         ast_trait_ref.ref_id) {
         def::DefTrait(trait_did) => {
             let trait_ref =
-                astconv::ast_path_to_trait_ref(
-                    ccx, &rscope, trait_did, Some(self_ty), &ast_trait_ref.path);
+                astconv::ast_path_to_trait_ref(this,
+                                               &rscope,
+                                               trait_did,
+                                               Some(self_ty),
+                                               associated_type,
+                                               &ast_trait_ref.path);
 
-            ccx.tcx.trait_refs.borrow_mut().insert(ast_trait_ref.ref_id,
-                                                   trait_ref.clone());
+            this.tcx().trait_refs.borrow_mut().insert(ast_trait_ref.ref_id,
+                                                      trait_ref.clone());
             trait_ref
         }
         _ => {
-            ccx.tcx.sess.span_fatal(
+            this.tcx().sess.span_fatal(
                 ast_trait_ref.path.span,
                 format!("`{}` is not a trait",
                         path_to_string(&ast_trait_ref.path)).as_slice());
@@ -796,14 +1418,14 @@ pub fn instantiate_trait_ref(ccx: &CrateCtxt,
     }
 }
 
-pub fn instantiate_unboxed_fn_ty(ccx: &CrateCtxt,
-                                 unboxed_function: &ast::UnboxedFnTy,
-                                 param_ty: ty::ParamTy)
-                                 -> Rc<ty::TraitRef>
-{
+pub fn instantiate_unboxed_fn_ty<'tcx,AC>(this: &AC,
+                                          unboxed_function: &ast::UnboxedFnTy,
+                                          param_ty: ty::ParamTy)
+                                          -> Rc<ty::TraitRef>
+                                          where AC: AstConv<'tcx> {
     let rscope = ExplicitRscope;
-    let param_ty = param_ty.to_ty(ccx.tcx);
-    Rc::new(astconv::trait_ref_for_unboxed_function(ccx,
+    let param_ty = param_ty.to_ty(this.tcx());
+    Rc::new(astconv::trait_ref_for_unboxed_function(this,
                                                     &rscope,
                                                     unboxed_function,
                                                     Some(param_ty)))
@@ -831,9 +1453,12 @@ pub fn trait_def_of_item(ccx: &CrateCtxt, it: &ast::Item) -> Rc<ty::TraitDef> {
         _ => {}
     }
 
-    let (generics, unbound, bounds) = match it.node {
-        ast::ItemTrait(ref generics, ref unbound, ref bounds, _) => {
-            (generics, unbound, bounds)
+    let (generics, unbound, bounds, items) = match it.node {
+        ast::ItemTrait(ref generics,
+                       ref unbound,
+                       ref supertraits,
+                       ref items) => {
+            (generics, unbound, supertraits, items.as_slice())
         }
         ref s => {
             tcx.sess.span_bug(
@@ -842,12 +1467,13 @@ pub fn trait_def_of_item(ccx: &CrateCtxt, it: &ast::Item) -> Rc<ty::TraitDef> {
         }
     };
 
-    let substs = mk_trait_substs(ccx, it.id, generics);
+    let substs = mk_trait_substs(ccx, it.id, generics, items);
 
     let ty_generics = ty_generics_for_trait(ccx,
                                             it.id,
                                             &substs,
-                                            generics);
+                                            generics,
+                                            items);
 
     let self_param_ty = ty::ParamTy::for_self(def_id);
 
@@ -870,9 +1496,9 @@ pub fn trait_def_of_item(ccx: &CrateCtxt, it: &ast::Item) -> Rc<ty::TraitDef> {
 
     fn mk_trait_substs(ccx: &CrateCtxt,
                        trait_id: ast::NodeId,
-                       generics: &ast::Generics)
-                        -> subst::Substs
-    {
+                       generics: &ast::Generics,
+                       items: &[ast::TraitItem])
+                        -> subst::Substs {
         // Creates a no-op substitution for the trait's type parameters.
         let regions =
             generics.lifetimes
@@ -884,7 +1510,8 @@ pub fn trait_def_of_item(ccx: &CrateCtxt, it: &ast::Item) -> Rc<ty::TraitDef> {
                                                      def.lifetime.name))
                     .collect();
 
-        let types =
+        // Start with the generics in the type parameters...
+        let mut types: Vec<_> =
             generics.ty_params
                     .iter()
                     .enumerate()
@@ -892,6 +1519,20 @@ pub fn trait_def_of_item(ccx: &CrateCtxt, it: &ast::Item) -> Rc<ty::TraitDef> {
                                                  i, local_def(def.id)))
                     .collect();
 
+        // ...and add generics synthesized from the associated types.
+        for item in items.iter() {
+            match *item {
+                ast::TypeTraitItem(ref trait_item) => {
+                    let index = types.len();
+                    types.push(ty::mk_param(ccx.tcx,
+                                            subst::TypeSpace,
+                                            index,
+                                            local_def(trait_item.id)))
+                }
+                ast::RequiredMethod(_) | ast::ProvidedMethod(_) => {}
+            }
+        }
+
         let self_ty =
             ty::mk_param(ccx.tcx, subst::SelfSpace, 0, local_def(trait_id));
 
@@ -916,13 +1557,22 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: &ast::Item)
             return pty;
         }
         ast::ItemFn(ref decl, fn_style, abi, ref generics, _) => {
-            let ty_generics = ty_generics_for_fn_or_method(ccx, generics,
-                                                           ty::Generics::empty());
-            let tofd = astconv::ty_of_bare_fn(ccx,
-                                              it.id,
-                                              fn_style,
-                                              abi,
-                                              &**decl);
+            let ty_generics = ty_generics_for_fn_or_method(
+                ccx,
+                generics,
+                ty::Generics::empty(),
+                CreateTypeParametersForAssociatedTypes);
+            let tofd = {
+                let fcx = FnCtxt {
+                    ccx: ccx,
+                    generics: &ty_generics,
+                };
+                astconv::ty_of_bare_fn(&fcx,
+                                       it.id,
+                                       fn_style,
+                                       abi,
+                                       &**decl)
+            };
             let pty = Polytype {
                 generics: ty_generics,
                 ty: ty::mk_bare_fn(ccx.tcx, tofd)
@@ -930,7 +1580,7 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: &ast::Item)
             debug!("type of {} (id {}) is {}",
                     token::get_ident(it.ident),
                     it.id,
-                    ppaux::ty_to_string(tcx, pty.ty));
+                    pty.repr(tcx));
 
             ccx.tcx.tcache.borrow_mut().insert(local_def(it.id), pty.clone());
             return pty;
@@ -944,7 +1594,10 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: &ast::Item)
             let pty = {
                 let ty = ccx.to_ty(&ExplicitRscope, &**t);
                 Polytype {
-                    generics: ty_generics_for_type(ccx, generics),
+                    generics: ty_generics_for_type(
+                                  ccx,
+                                  generics,
+                                  DontCreateTypeParametersForAssociatedTypes),
                     ty: ty
                 }
             };
@@ -954,7 +1607,10 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: &ast::Item)
         }
         ast::ItemEnum(_, ref generics) => {
             // Create a new generic polytype.
-            let ty_generics = ty_generics_for_type(ccx, generics);
+            let ty_generics = ty_generics_for_type(
+                ccx,
+                generics,
+                DontCreateTypeParametersForAssociatedTypes);
             let substs = mk_item_substs(ccx, &ty_generics);
             let t = ty::mk_enum(tcx, local_def(it.id), substs);
             let pty = Polytype {
@@ -969,7 +1625,10 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: &ast::Item)
             tcx.sess.span_bug(it.span, "invoked ty_of_item on trait");
         }
         ast::ItemStruct(_, ref generics) => {
-            let ty_generics = ty_generics_for_type(ccx, generics);
+            let ty_generics = ty_generics_for_type(
+                ccx,
+                generics,
+                DontCreateTypeParametersForAssociatedTypes);
             let substs = mk_item_substs(ccx, &ty_generics);
             let t = ty::mk_struct(tcx, local_def(it.id), substs);
             let pty = Polytype {
@@ -1006,30 +1665,88 @@ pub fn ty_of_foreign_item(ccx: &CrateCtxt,
     }
 }
 
+fn ty_of_trait_item(ccx: &CrateCtxt, trait_item: &ast::TraitItem)
+                    -> ty::Polytype {
+    match *trait_item {
+        ast::RequiredMethod(ref m) => {
+            ccx.tcx.sess.span_bug(m.span,
+                                  "ty_of_trait_item() on required method")
+        }
+        ast::ProvidedMethod(ref m) => {
+            ccx.tcx.sess.span_bug(m.span,
+                                  "ty_of_trait_item() on provided method")
+        }
+        ast::TypeTraitItem(ref associated_type) => {
+            let parent = ccx.tcx.map.get_parent(associated_type.id);
+            let trait_def = match ccx.tcx.map.get(parent) {
+                ast_map::NodeItem(item) => trait_def_of_item(ccx, &*item),
+                _ => {
+                    ccx.tcx.sess.span_bug(associated_type.span,
+                                          "associated type's parent wasn't \
+                                           an item?!")
+                }
+            };
+            convert_associated_type(ccx, &*trait_def, &**associated_type)
+        }
+    }
+}
+
 fn ty_generics_for_type(ccx: &CrateCtxt,
-                        generics: &ast::Generics)
-                        -> ty::Generics
-{
+                        generics: &ast::Generics,
+                        create_type_parameters_for_associated_types:
+                            CreateTypeParametersForAssociatedTypesFlag)
+                        -> ty::Generics {
     ty_generics(ccx,
                 subst::TypeSpace,
                 generics.lifetimes.as_slice(),
                 generics.ty_params.as_slice(),
                 ty::Generics::empty(),
-                &generics.where_clause)
+                &generics.where_clause,
+                create_type_parameters_for_associated_types)
 }
 
 fn ty_generics_for_trait(ccx: &CrateCtxt,
                          trait_id: ast::NodeId,
                          substs: &subst::Substs,
-                         generics: &ast::Generics)
+                         generics: &ast::Generics,
+                         items: &[ast::TraitItem])
                          -> ty::Generics {
-    let mut generics = ty_generics(ccx,
-                                   subst::TypeSpace,
-                                   generics.lifetimes.as_slice(),
-                                   generics.ty_params.as_slice(),
-                                   ty::Generics::empty(),
-                                   &generics.where_clause);
+    let mut generics =
+        ty_generics(ccx,
+                    subst::TypeSpace,
+                    generics.lifetimes.as_slice(),
+                    generics.ty_params.as_slice(),
+                    ty::Generics::empty(),
+                    &generics.where_clause,
+                    DontCreateTypeParametersForAssociatedTypes);
+
+    // Add in type parameters for any associated types.
+    for item in items.iter() {
+        match *item {
+            ast::TypeTraitItem(ref associated_type) => {
+                let def = ty::TypeParameterDef {
+                    space: subst::TypeSpace,
+                    index: generics.types.len(subst::TypeSpace),
+                    ident: associated_type.ident,
+                    def_id: local_def(associated_type.id),
+                    bounds: ty::ParamBounds {
+                        builtin_bounds: ty::empty_builtin_bounds(),
+                        trait_bounds: Vec::new(),
+                        region_bounds: Vec::new(),
+                    },
+                    associated_with: Some(local_def(trait_id)),
+                    default: None,
+                };
+                ccx.tcx.ty_param_defs.borrow_mut().insert(associated_type.id,
+                                                          def.clone());
+                generics.types.push(subst::TypeSpace, def);
+            }
+            ast::ProvidedMethod(_) | ast::RequiredMethod(_) => {}
+        }
+    }
 
+    // Add in the self type parameter.
+    //
     // Something of a hack: use the node id for the trait, also as
     // the node id for the Self type parameter.
     let param_id = trait_id;
@@ -1048,6 +1765,7 @@ fn ty_generics_for_trait(ccx: &CrateCtxt,
             builtin_bounds: ty::empty_builtin_bounds(),
             trait_bounds: vec!(self_trait_ref),
         },
+        associated_with: None,
         default: None
     };
 
@@ -1058,41 +1776,48 @@ fn ty_generics_for_trait(ccx: &CrateCtxt,
     generics
 }
 
-fn ty_generics_for_fn_or_method(ccx: &CrateCtxt,
-                                generics: &ast::Generics,
-                                base_generics: ty::Generics)
-                                -> ty::Generics {
+fn ty_generics_for_fn_or_method<'tcx,AC>(
+        this: &AC,
+        generics: &ast::Generics,
+        base_generics: ty::Generics,
+        create_type_parameters_for_associated_types:
+        CreateTypeParametersForAssociatedTypesFlag)
+        -> ty::Generics
+        where AC: AstConv<'tcx> {
     let early_lifetimes = resolve_lifetime::early_bound_lifetimes(generics);
-    ty_generics(ccx,
+    ty_generics(this,
                 subst::FnSpace,
                 early_lifetimes.as_slice(),
                 generics.ty_params.as_slice(),
                 base_generics,
-                &generics.where_clause)
+                &generics.where_clause,
+                create_type_parameters_for_associated_types)
 }
 
 // Add the Sized bound, unless the type parameter is marked as `Sized?`.
-fn add_unsized_bound(ccx: &CrateCtxt,
-                     unbound: &Option<ast::TyParamBound>,
-                     bounds: &mut ty::BuiltinBounds,
-                     desc: &str,
-                     span: Span) {
-    let kind_id = ccx.tcx.lang_items.require(SizedTraitLangItem);
-
+fn add_unsized_bound<'tcx,AC>(this: &AC,
+                              unbound: &Option<ast::TyParamBound>,
+                              bounds: &mut ty::BuiltinBounds,
+                              desc: &str,
+                              span: Span)
+                              where AC: AstConv<'tcx> {
+    let kind_id = this.tcx().lang_items.require(SizedTraitLangItem);
     match unbound {
         &Some(ast::TraitTyParamBound(ref tpb)) => {
             // FIXME(#8559) currently requires the unbound to be built-in.
-            let trait_def_id = ty::trait_ref_to_def_id(ccx.tcx, tpb);
+            let trait_def_id = ty::trait_ref_to_def_id(this.tcx(), tpb);
             match kind_id {
                 Ok(kind_id) if trait_def_id != kind_id => {
-                    ccx.tcx.sess.span_warn(span,
-                                           format!("default bound relaxed \
-                                                    for a {}, but this does \
-                                                    nothing because the given \
-                                                    bound is not a default. \
-                                                    Only `Sized?` is supported.",
-                                                   desc).as_slice());
-                    ty::try_add_builtin_trait(ccx.tcx,
+                    this.tcx().sess.span_warn(span,
+                                              format!("default bound relaxed \
+                                                       for a {}, but this \
+                                                       does nothing because \
+                                                       the given bound is not \
+                                                       a default. \
+                                                       Only `Sized?` is \
+                                                       supported.",
+                                                      desc).as_slice());
+                    ty::try_add_builtin_trait(this.tcx(),
                                               kind_id,
                                               bounds);
                 }
@@ -1100,28 +1825,104 @@ fn add_unsized_bound(ccx: &CrateCtxt,
             }
         }
         _ if kind_id.is_ok() => {
-            ty::try_add_builtin_trait(ccx.tcx,
-                                      kind_id.unwrap(),
-                                      bounds);
+            ty::try_add_builtin_trait(this.tcx(), kind_id.unwrap(), bounds);
         }
         // No lang item for Sized, so we can't add it as a bound.
         _ => {}
     }
 }
 
-fn ty_generics(ccx: &CrateCtxt,
-               space: subst::ParamSpace,
-               lifetime_defs: &[ast::LifetimeDef],
-               types: &[ast::TyParam],
-               base_generics: ty::Generics,
-               where_clause: &ast::WhereClause)
-               -> ty::Generics
-{
+#[deriving(Clone, PartialEq, Eq)]
+enum CreateTypeParametersForAssociatedTypesFlag {
+    DontCreateTypeParametersForAssociatedTypes,
+    CreateTypeParametersForAssociatedTypes,
+}
+
+fn ensure_associated_types<'tcx,AC>(this: &AC, trait_id: ast::DefId)
+                                    where AC: AstConv<'tcx> {
+    if this.tcx().trait_associated_types.borrow().contains_key(&trait_id) {
+        return
+    }
+
+    if trait_id.krate == ast::LOCAL_CRATE {
+        match this.tcx().map.find(trait_id.node) {
+            Some(ast_map::NodeItem(item)) => {
+                match item.node {
+                    ast::ItemTrait(_, _, _, ref trait_items) => {
+                        let mut result = Vec::new();
+                        let mut index = 0;
+                        for trait_item in trait_items.iter() {
+                            match *trait_item {
+                                ast::RequiredMethod(_) |
+                                ast::ProvidedMethod(_) => {}
+                                ast::TypeTraitItem(ref associated_type) => {
+                                    let info = ty::AssociatedTypeInfo {
+                                        def_id: local_def(associated_type.id),
+                                        index: index,
+                                        ident: associated_type.ident,
+                                    };
+                                    result.push(info);
+                                    index += 1;
+                                }
+                            }
+                        }
+                        this.tcx()
+                            .trait_associated_types
+                            .borrow_mut()
+                            .insert(trait_id, Rc::new(result));
+                        return
+                    }
+                    _ => {
+                        this.tcx().sess.bug("ensure_associated_types() \
+                                             called on non-trait")
+                    }
+                }
+            }
+            _ => {
+                this.tcx().sess.bug("ensure_associated_types() called on \
+                                     non-trait")
+            }
+        }
+
+    }
+
+    // Cross-crate case.
+    let mut result = Vec::new();
+    let mut index = 0;
+    let trait_items = ty::trait_items(this.tcx(), trait_id);
+    for trait_item in trait_items.iter() {
+        match *trait_item {
+            ty::MethodTraitItem(_) => {}
+            ty::TypeTraitItem(ref associated_type) => {
+                let info = ty::AssociatedTypeInfo {
+                    def_id: associated_type.def_id,
+                    index: index,
+                    ident: associated_type.ident
+                };
+                result.push(info);
+                index += 1;
+            }
+        }
+    }
+    this.tcx().trait_associated_types.borrow_mut().insert(trait_id,
+                                                          Rc::new(result));
+}
+
+fn ty_generics<'tcx,AC>(this: &AC,
+                        space: subst::ParamSpace,
+                        lifetime_defs: &[ast::LifetimeDef],
+                        types: &[ast::TyParam],
+                        base_generics: ty::Generics,
+                        where_clause: &ast::WhereClause,
+                        create_type_parameters_for_associated_types:
+                        CreateTypeParametersForAssociatedTypesFlag)
+                        -> ty::Generics
+                        where AC: AstConv<'tcx> {
     let mut result = base_generics;
 
     for (i, l) in lifetime_defs.iter().enumerate() {
         let bounds = l.bounds.iter()
-                             .map(|l| ast_region_to_region(ccx.tcx, l))
+                             .map(|l| ast_region_to_region(this.tcx(), l))
                              .collect();
         let def = ty::RegionParameterDef { name: l.lifetime.name,
                                            space: space,
@@ -1132,80 +1933,170 @@ fn ty_generics(ccx: &CrateCtxt,
         result.regions.push(space, def);
     }
 
+    assert!(result.types.is_empty_in(space));
+
+    // First, create the virtual type parameters for associated types if
+    // necessary.
+    let mut associated_types_generics = ty::Generics::empty();
+    match create_type_parameters_for_associated_types {
+        DontCreateTypeParametersForAssociatedTypes => {}
+        CreateTypeParametersForAssociatedTypes => {
+            let mut index = 0;
+            for param in types.iter() {
+                for bound in param.bounds.iter() {
+                    match *bound {
+                        ast::TraitTyParamBound(ref trait_bound) => {
+                            match lookup_def_tcx(this.tcx(),
+                                                 trait_bound.path.span,
+                                                 trait_bound.ref_id) {
+                                def::DefTrait(trait_did) => {
+                                    ensure_associated_types(this, trait_did);
+                                    let associated_types =
+                                        ty::associated_types_for_trait(
+                                            this.tcx(),
+                                            trait_did);
+                                    for associated_type_info in
+                                            associated_types.iter() {
+                                        let associated_type_trait_item =
+                                            ty::impl_or_trait_item(
+                                                this.tcx(),
+                                                associated_type_info.def_id);
+                                        let def = ty::TypeParameterDef {
+                                            ident: associated_type_trait_item
+                                                       .ident(),
+                                            def_id:
+                                                associated_type_info.def_id,
+                                            space: space,
+                                            index: types.len() + index,
+                                            bounds: ty::ParamBounds {
+                                                builtin_bounds:
+                                                ty::empty_builtin_bounds(),
+                                                trait_bounds: Vec::new(),
+                                                region_bounds: Vec::new(),
+                                            },
+                                            associated_with: {
+                                                Some(local_def(param.id))
+                                            },
+                                            default: None,
+                                        };
+                                        associated_types_generics.types
+                                                                 .push(space,
+                                                                       def);
+                                        index += 1;
+                                    }
+                                }
+                                _ => {
+                                    this.tcx().sess.span_bug(trait_bound.path
+                                                                        .span,
+                                                             "not a trait?!")
+                                }
+                            }
+                        }
+                        _ => {}
+                    }
+                }
+            }
+        }
+    }
+
+    // Now create the real type parameters.
+    let gcx = GenericsCtxt {
+        chain: this,
+        associated_types_generics: &associated_types_generics,
+    };
     for (i, param) in types.iter().enumerate() {
-        let def = get_or_create_type_parameter_def(ccx,
+        let def = get_or_create_type_parameter_def(&gcx,
                                                    space,
                                                    param,
                                                    i,
                                                    where_clause);
-        debug!("ty_generics: def for type param: {}", def.repr(ccx.tcx));
+        debug!("ty_generics: def for type param: {}, {}",
+               def.repr(this.tcx()),
+               space);
         result.types.push(space, def);
     }
 
+    // Append the associated types to the result.
+    for associated_type_param in associated_types_generics.types
+                                                          .get_slice(space)
+                                                          .iter() {
+        assert!(result.types.get_slice(space).len() ==
+                associated_type_param.index);
+        debug!("ty_generics: def for associated type: {}, {}",
+               associated_type_param.repr(this.tcx()),
+               space);
+        result.types.push(space, (*associated_type_param).clone());
+    }
+
     return result;
 
-    fn get_or_create_type_parameter_def(ccx: &CrateCtxt,
+    fn get_or_create_type_parameter_def<'tcx,AC>(
+                                        this: &AC,
                                         space: subst::ParamSpace,
                                         param: &ast::TyParam,
                                         index: uint,
                                         where_clause: &ast::WhereClause)
-                                        -> ty::TypeParameterDef {
-        match ccx.tcx.ty_param_defs.borrow().find(&param.id) {
+                                        -> ty::TypeParameterDef
+                                        where AC: AstConv<'tcx> {
+        match this.tcx().ty_param_defs.borrow().find(&param.id) {
             Some(d) => { return (*d).clone(); }
             None => { }
         }
 
         let param_ty = ty::ParamTy::new(space, index, local_def(param.id));
-        let bounds = compute_bounds(ccx,
+        let bounds = compute_bounds(this,
                                     param.ident.name,
                                     param_ty,
                                     param.bounds.as_slice(),
                                     &param.unbound,
                                     param.span,
                                     where_clause);
-            let default = param.default.as_ref().map(|path| {
-            let ty = ast_ty_to_ty(ccx, &ExplicitRscope, &**path);
-            let cur_idx = index;
-
-            ty::walk_ty(ty, |t| {
-                match ty::get(t).sty {
-                    ty::ty_param(p) => if p.idx > cur_idx {
-                    span_err!(ccx.tcx.sess, path.span, E0128,
-                              "type parameters with a default cannot use \
-                               forward declared identifiers");
-                    },
-                    _ => {}
-                }
-            });
+        let default = match param.default {
+            None => None,
+            Some(ref path) => {
+                let ty = ast_ty_to_ty(this, &ExplicitRscope, &**path);
+                let cur_idx = index;
+
+                ty::walk_ty(ty, |t| {
+                    match ty::get(t).sty {
+                        ty::ty_param(p) => if p.idx > cur_idx {
+                        span_err!(this.tcx().sess, path.span, E0128,
+                                  "type parameters with a default cannot use \
+                                   forward declared identifiers");
+                        },
+                        _ => {}
+                    }
+                });
 
-            ty
-        });
+                Some(ty)
+            }
+        };
 
         let def = ty::TypeParameterDef {
             space: space,
             index: index,
             ident: param.ident,
             def_id: local_def(param.id),
+            associated_with: None,
             bounds: bounds,
             default: default
         };
 
-        ccx.tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
+        this.tcx().ty_param_defs.borrow_mut().insert(param.id, def.clone());
 
         def
     }
 }
 
-fn compute_bounds(
-    ccx: &CrateCtxt,
-    name_of_bounded_thing: ast::Name,
-    param_ty: ty::ParamTy,
-    ast_bounds: &[ast::TyParamBound],
-    unbound: &Option<ast::TyParamBound>,
-    span: Span,
-    where_clause: &ast::WhereClause)
-    -> ty::ParamBounds
-{
+fn compute_bounds<'tcx,AC>(this: &AC,
+                           name_of_bounded_thing: ast::Name,
+                           param_ty: ty::ParamTy,
+                           ast_bounds: &[ast::TyParamBound],
+                           unbound: &Option<ast::TyParamBound>,
+                           span: Span,
+                           where_clause: &ast::WhereClause)
+                           -> ty::ParamBounds
+                           where AC: AstConv<'tcx> {
     /*!
      * Translate the AST's notion of ty param bounds (which are an
      * enum consisting of a newtyped Ty or a region) to ty's
@@ -1213,21 +2104,23 @@ fn compute_bounds(
      * traits, or the built-in trait (formerly known as kind): Send.
      */
 
-    let mut param_bounds = conv_param_bounds(ccx,
+    let mut param_bounds = conv_param_bounds(this,
                                              span,
                                              param_ty,
                                              ast_bounds,
                                              where_clause);
 
 
-    add_unsized_bound(ccx,
+    add_unsized_bound(this,
                       unbound,
                       &mut param_bounds.builtin_bounds,
                       "type parameter",
                       span);
 
-    check_bounds_compatible(ccx.tcx, name_of_bounded_thing,
-                            &param_bounds, span);
+    check_bounds_compatible(this.tcx(),
+                            name_of_bounded_thing,
+                            &param_bounds,
+                            span);
 
     param_bounds.trait_bounds.sort_by(|a,b| a.def_id.cmp(&b.def_id));
 
@@ -1258,31 +2151,36 @@ fn check_bounds_compatible(tcx: &ty::ctxt,
     }
 }
 
-fn conv_param_bounds(ccx: &CrateCtxt,
-                     span: Span,
-                     param_ty: ty::ParamTy,
-                     ast_bounds: &[ast::TyParamBound],
-                     where_clause: &ast::WhereClause)
-                     -> ty::ParamBounds
-{
+fn conv_param_bounds<'tcx,AC>(this: &AC,
+                              span: Span,
+                              param_ty: ty::ParamTy,
+                              ast_bounds: &[ast::TyParamBound],
+                              where_clause: &ast::WhereClause)
+                              -> ty::ParamBounds
+                              where AC: AstConv<'tcx> {
     let all_bounds =
-        merge_param_bounds(ccx, param_ty, ast_bounds, where_clause);
+        merge_param_bounds(this.tcx(), param_ty, ast_bounds, where_clause);
     let astconv::PartitionedBounds { builtin_bounds,
                                      trait_bounds,
                                      region_bounds,
                                      unboxed_fn_ty_bounds } =
-        astconv::partition_bounds(ccx.tcx, span, all_bounds.as_slice());
+        astconv::partition_bounds(this.tcx(), span, all_bounds.as_slice());
     let unboxed_fn_ty_bounds =
         unboxed_fn_ty_bounds.into_iter()
-        .map(|b| instantiate_unboxed_fn_ty(ccx, b, param_ty));
+        .map(|b| instantiate_unboxed_fn_ty(this, b, param_ty));
     let trait_bounds: Vec<Rc<ty::TraitRef>> =
         trait_bounds.into_iter()
-        .map(|b| instantiate_trait_ref(ccx, b, param_ty.to_ty(ccx.tcx)))
+        .map(|b| {
+            instantiate_trait_ref(this,
+                                  b,
+                                  param_ty.to_ty(this.tcx()),
+                                  Some(param_ty.to_ty(this.tcx())))
+        })
         .chain(unboxed_fn_ty_bounds)
         .collect();
     let region_bounds: Vec<ty::Region> =
         region_bounds.move_iter()
-        .map(|r| ast_region_to_region(ccx.tcx, r))
+        .map(|r| ast_region_to_region(this.tcx(), r))
         .collect();
     ty::ParamBounds {
         region_bounds: region_bounds,
@@ -1291,12 +2189,11 @@ fn conv_param_bounds(ccx: &CrateCtxt,
     }
 }
 
-fn merge_param_bounds<'a>(ccx: &CrateCtxt,
+fn merge_param_bounds<'a>(tcx: &ty::ctxt,
                           param_ty: ty::ParamTy,
                           ast_bounds: &'a [ast::TyParamBound],
                           where_clause: &'a ast::WhereClause)
-                          -> Vec<&'a ast::TyParamBound>
-{
+                          -> Vec<&'a ast::TyParamBound> {
     /*!
      * Merges the bounds declared on a type parameter with those
      * found from where clauses into a single list.
@@ -1309,15 +2206,13 @@ fn merge_param_bounds<'a>(ccx: &CrateCtxt,
     }
 
     for predicate in where_clause.predicates.iter() {
-        let predicate_param_id = ccx.tcx
-            .def_map
-            .borrow()
-            .find(&predicate.id)
-            .expect("compute_bounds(): resolve \
-                     didn't resolve the type \
-                     parameter identifier in a \
-                     `where` clause")
-            .def_id();
+        let predicate_param_id =
+            tcx.def_map
+               .borrow()
+               .find(&predicate.id)
+               .expect("compute_bounds(): resolve didn't resolve the type \
+                        parameter identifier in a `where` clause")
+               .def_id();
         if param_ty.def_id != predicate_param_id {
             continue
         }
@@ -1334,8 +2229,7 @@ pub fn ty_of_foreign_fn_decl(ccx: &CrateCtxt,
                              def_id: ast::DefId,
                              ast_generics: &ast::Generics,
                              abi: abi::Abi)
-                          -> ty::Polytype {
-
+                             -> ty::Polytype {
     for i in decl.inputs.iter() {
         match (*i).pat.node {
             ast::PatIdent(_, _, _) => (),
@@ -1347,9 +2241,11 @@ pub fn ty_of_foreign_fn_decl(ccx: &CrateCtxt,
         }
     }
 
-    let ty_generics_for_fn_or_method =
-        ty_generics_for_fn_or_method(ccx, ast_generics,
-                                     ty::Generics::empty());
+    let ty_generics_for_fn_or_method = ty_generics_for_fn_or_method(
+            ccx,
+            ast_generics,
+            ty::Generics::empty(),
+            DontCreateTypeParametersForAssociatedTypes);
     let rb = BindingRscope::new(def_id.node);
     let input_tys = decl.inputs
                         .iter()
diff --git a/src/librustc/middle/typeck/infer/error_reporting.rs b/src/librustc/middle/typeck/infer/error_reporting.rs
index af670f25e56..6ea80a59230 100644
--- a/src/librustc/middle/typeck/infer/error_reporting.rs
+++ b/src/librustc/middle/typeck/infer/error_reporting.rs
@@ -871,6 +871,7 @@ impl<'a, 'tcx> ErrorReporting for InferCtxt<'a, 'tcx> {
                                   Some(&m.pe_explicit_self().node),
                                   m.span))
                         }
+                        ast::TypeImplItem(_) => None,
                     }
                 },
                 _ => None
@@ -1687,6 +1688,7 @@ fn lifetimes_in_scope(tcx: &ty::ctxt,
                         taken.push_all(m.pe_generics().lifetimes.as_slice());
                         Some(m.id)
                     }
+                    ast::TypeImplItem(_) => None,
                 }
             }
             _ => None
diff --git a/src/librustc/middle/typeck/variance.rs b/src/librustc/middle/typeck/variance.rs
index 547fbce573b..a6edfcf80fd 100644
--- a/src/librustc/middle/typeck/variance.rs
+++ b/src/librustc/middle/typeck/variance.rs
@@ -522,6 +522,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for ConstraintContext<'a, 'tcx> {
                             self.add_constraints_from_sig(&method.fty.sig,
                                                           self.covariant);
                         }
+                        ty::TypeTraitItem(_) => {}
                     }
                 }
             }
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index be4a1c95e55..2083aa52bec 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -603,9 +603,11 @@ impl Repr for def::Def {
 
 impl Repr for ty::TypeParameterDef {
     fn repr(&self, tcx: &ctxt) -> String {
-        format!("TypeParameterDef({}, {})",
-                self.def_id.repr(tcx),
-                self.bounds.repr(tcx))
+        format!("TypeParameterDef({}, {}, {}/{})",
+                self.def_id,
+                self.bounds.repr(tcx),
+                self.space,
+                self.index)
     }
 }
 
diff --git a/src/librustdoc/clean/inline.rs b/src/librustdoc/clean/inline.rs
index ccb01ca620e..1a324e25472 100644
--- a/src/librustdoc/clean/inline.rs
+++ b/src/librustdoc/clean/inline.rs
@@ -316,6 +316,10 @@ fn build_impl(cx: &DocContext, tcx: &ty::ctxt,
                 };
                 Some(item)
             }
+            ty::TypeTraitItem(_) => {
+                // FIXME(pcwalton): Implement.
+                None
+            }
         }
     }).collect();
     return Some(clean::Item {
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index c03c56cd223..9e05382fa55 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -17,7 +17,7 @@ use syntax::ast_util;
 use syntax::ast_util::PostExpansionMethod;
 use syntax::attr;
 use syntax::attr::{AttributeMethods, AttrMetaMethods};
-use syntax::codemap::Pos;
+use syntax::codemap::{DUMMY_SP, Pos};
 use syntax::parse::token::InternedString;
 use syntax::parse::token;
 use syntax::ptr::P;
@@ -317,6 +317,7 @@ pub enum ItemEnum {
     ForeignStaticItem(Static),
     MacroItem(Macro),
     PrimitiveItem(Primitive),
+    AssociatedTypeItem,
 }
 
 #[deriving(Clone, Encodable, Decodable)]
@@ -933,6 +934,7 @@ impl Clean<Type> for ast::TraitRef {
 pub enum TraitItem {
     RequiredMethod(Item),
     ProvidedMethod(Item),
+    TypeTraitItem(Item),
 }
 
 impl TraitItem {
@@ -952,6 +954,7 @@ impl TraitItem {
         match *self {
             RequiredMethod(ref item) => item,
             ProvidedMethod(ref item) => item,
+            TypeTraitItem(ref item) => item,
         }
     }
 }
@@ -961,6 +964,7 @@ impl Clean<TraitItem> for ast::TraitItem {
         match self {
             &ast::RequiredMethod(ref t) => RequiredMethod(t.clean(cx)),
             &ast::ProvidedMethod(ref t) => ProvidedMethod(t.clean(cx)),
+            &ast::TypeTraitItem(ref t) => TypeTraitItem(t.clean(cx)),
         }
     }
 }
@@ -968,12 +972,14 @@ impl Clean<TraitItem> for ast::TraitItem {
 #[deriving(Clone, Encodable, Decodable)]
 pub enum ImplItem {
     MethodImplItem(Item),
+    TypeImplItem(Item),
 }
 
 impl Clean<ImplItem> for ast::ImplItem {
     fn clean(&self, cx: &DocContext) -> ImplItem {
         match self {
             &ast::MethodImplItem(ref t) => MethodImplItem(t.clean(cx)),
+            &ast::TypeImplItem(ref t) => TypeImplItem(t.clean(cx)),
         }
     }
 }
@@ -1028,6 +1034,7 @@ impl Clean<Item> for ty::ImplOrTraitItem {
     fn clean(&self, cx: &DocContext) -> Item {
         match *self {
             ty::MethodTraitItem(ref mti) => mti.clean(cx),
+            ty::TypeTraitItem(ref tti) => tti.clean(cx),
         }
     }
 }
@@ -1743,6 +1750,7 @@ impl Clean<Item> for doctree::Impl {
                 items: self.items.clean(cx).into_iter().map(|ti| {
                         match ti {
                             MethodImplItem(i) => i,
+                            TypeImplItem(i) => i,
                         }
                     }).collect(),
                 derived: detect_derived(self.attrs.as_slice()),
@@ -2125,6 +2133,54 @@ impl Clean<Stability> for attr::Stability {
     }
 }
 
+impl Clean<Item> for ast::AssociatedType {
+    fn clean(&self, cx: &DocContext) -> Item {
+        Item {
+            source: self.span.clean(cx),
+            name: Some(self.ident.clean(cx)),
+            attrs: self.attrs.clean(cx),
+            inner: AssociatedTypeItem,
+            visibility: None,
+            def_id: ast_util::local_def(self.id),
+            stability: None,
+        }
+    }
+}
+
+impl Clean<Item> for ty::AssociatedType {
+    fn clean(&self, cx: &DocContext) -> Item {
+        Item {
+            source: DUMMY_SP.clean(cx),
+            name: Some(self.ident.clean(cx)),
+            attrs: Vec::new(),
+            inner: AssociatedTypeItem,
+            visibility: None,
+            def_id: self.def_id,
+            stability: None,
+        }
+    }
+}
+
+impl Clean<Item> for ast::Typedef {
+    fn clean(&self, cx: &DocContext) -> Item {
+        Item {
+            source: self.span.clean(cx),
+            name: Some(self.ident.clean(cx)),
+            attrs: self.attrs.clean(cx),
+            inner: TypedefItem(Typedef {
+                type_: self.typ.clean(cx),
+                generics: Generics {
+                    lifetimes: Vec::new(),
+                    type_params: Vec::new(),
+                },
+            }),
+            visibility: None,
+            def_id: ast_util::local_def(self.id),
+            stability: None,
+        }
+    }
+}
+
 fn lang_struct(cx: &DocContext, did: Option<ast::DefId>,
                t: ty::t, name: &str,
                fallback: fn(Box<Type>) -> Type) -> Type {
diff --git a/src/librustdoc/fold.rs b/src/librustdoc/fold.rs
index 66e93de995e..54e9c29e11d 100644
--- a/src/librustdoc/fold.rs
+++ b/src/librustdoc/fold.rs
@@ -55,6 +55,12 @@ pub trait DocFolder {
                                 None => return None,
                             }
                         },
+                        TypeTraitItem(it) => {
+                            match this.fold_item(it) {
+                                Some(x) => return Some(TypeTraitItem(x)),
+                                None => return None,
+                            }
+                        }
                     }
                 }
                 let mut foo = Vec::new(); swap(&mut foo, &mut i.items);
diff --git a/src/librustdoc/html/item_type.rs b/src/librustdoc/html/item_type.rs
index 6e240b0d8d4..e18ab0bd14f 100644
--- a/src/librustdoc/html/item_type.rs
+++ b/src/librustdoc/html/item_type.rs
@@ -38,6 +38,7 @@ pub enum ItemType {
     ForeignStatic   = 14,
     Macro           = 15,
     Primitive       = 16,
+    AssociatedType  = 17,
 }
 
 impl ItemType {
@@ -60,6 +61,7 @@ impl ItemType {
             ForeignStatic   => "ffs",
             Macro           => "macro",
             Primitive       => "primitive",
+            AssociatedType  => "associatedtype",
         }
     }
 }
@@ -95,6 +97,7 @@ pub fn shortty(item: &clean::Item) -> ItemType {
         clean::ForeignStaticItem(..)   => ForeignStatic,
         clean::MacroItem(..)           => Macro,
         clean::PrimitiveItem(..)       => Primitive,
+        clean::AssociatedTypeItem      => AssociatedType,
     }
 }
 
diff --git a/src/librustdoc/html/render.rs b/src/librustdoc/html/render.rs
index a0c4283711e..2107854c52b 100644
--- a/src/librustdoc/html/render.rs
+++ b/src/librustdoc/html/render.rs
@@ -1512,6 +1512,7 @@ fn item_module(w: &mut fmt::Formatter, cx: &Context,
                 clean::ForeignStaticItem(..)   => ("ffi-statics", "Foreign Statics"),
                 clean::MacroItem(..)           => ("macros", "Macros"),
                 clean::PrimitiveItem(..)       => ("primitives", "Primitive Types"),
+                clean::AssociatedTypeItem(..)  => ("associated-types", "Associated Types"),
             };
             try!(write!(w,
                         "<h2 id='{id}' class='section-header'>\
diff --git a/src/librustdoc/passes.rs b/src/librustdoc/passes.rs
index eeccc3303eb..33337594b4c 100644
--- a/src/librustdoc/passes.rs
+++ b/src/librustdoc/passes.rs
@@ -175,6 +175,9 @@ impl<'a> fold::DocFolder for Stripper<'a> {
 
             // Primitives are never stripped
             clean::PrimitiveItem(..) => {}
+
+            // Associated types are never stripped
+            clean::AssociatedTypeItem(..) => {}
         }
 
         let fastreturn = match i.inner {
diff --git a/src/librustdoc/stability_summary.rs b/src/librustdoc/stability_summary.rs
index 11d00fa20a4..02dc4e9bdb6 100644
--- a/src/librustdoc/stability_summary.rs
+++ b/src/librustdoc/stability_summary.rs
@@ -22,7 +22,7 @@ use syntax::ast::Public;
 
 use clean::{Crate, Item, ModuleItem, Module, StructItem, Struct, EnumItem, Enum};
 use clean::{ImplItem, Impl, Trait, TraitItem, ProvidedMethod, RequiredMethod};
-use clean::{ViewItemItem, PrimitiveItem};
+use clean::{TypeTraitItem, ViewItemItem, PrimitiveItem};
 
 #[deriving(Zero, Encodable, Decodable, PartialEq, Eq)]
 /// The counts for each stability level.
@@ -131,7 +131,8 @@ fn summarize_item(item: &Item) -> (Counts, Option<ModuleSummary>) {
             fn extract_item<'a>(trait_item: &'a TraitItem) -> &'a Item {
                 match *trait_item {
                     ProvidedMethod(ref item) |
-                    RequiredMethod(ref item) => item
+                    RequiredMethod(ref item) |
+                    TypeTraitItem(ref item) => item
                 }
             }
             let subcounts = trait_items.iter()
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 5546f868ba0..eac158e664c 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -555,6 +555,18 @@ pub enum Expr_ {
     ExprParen(P<Expr>)
 }
 
+/// A "qualified path":
+///
+///     <Vec<T> as SomeTrait>::SomeAssociatedItem
+///      ^~~~~     ^~~~~~~~~   ^~~~~~~~~~~~~~~~~~
+///      for_type  trait_name  item_name
+#[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash, Show)]
+pub struct QPath {
+    pub for_type: P<Ty>,
+    pub trait_name: Path,
+    pub item_name: Ident,
+}
+
 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash, Show)]
 pub enum CaptureClause {
     CaptureByValue,
@@ -766,11 +778,31 @@ pub struct TypeMethod {
 pub enum TraitItem {
     RequiredMethod(TypeMethod),
     ProvidedMethod(P<Method>),
+    TypeTraitItem(P<AssociatedType>),
 }
 
 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash, Show)]
 pub enum ImplItem {
     MethodImplItem(P<Method>),
+    TypeImplItem(P<Typedef>),
+}
+
+#[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash, Show)]
+pub struct AssociatedType {
+    pub id: NodeId,
+    pub span: Span,
+    pub ident: Ident,
+    pub attrs: Vec<Attribute>,
+}
+
+#[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash, Show)]
+pub struct Typedef {
+    pub id: NodeId,
+    pub span: Span,
+    pub ident: Ident,
+    pub vis: Visibility,
+    pub attrs: Vec<Attribute>,
+    pub typ: P<Ty>,
 }
 
 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
@@ -917,6 +949,8 @@ pub enum Ty_ {
     TyUnboxedFn(P<UnboxedFnTy>),
     TyTup(Vec<P<Ty>> ),
     TyPath(Path, Option<TyParamBounds>, NodeId), // for #7264; see above
+    /// A "qualified path", e.g. `<Vec<T> as SomeTrait>::SomeType`
+    TyQPath(P<QPath>),
     /// No-op; kept solely so that we can pretty-print faithfully
     TyParen(P<Ty>),
     TyTypeof(P<Expr>),
diff --git a/src/libsyntax/ast_map/blocks.rs b/src/libsyntax/ast_map/blocks.rs
index 1400e494917..8280f34615f 100644
--- a/src/libsyntax/ast_map/blocks.rs
+++ b/src/libsyntax/ast_map/blocks.rs
@@ -207,6 +207,9 @@ impl<'a> FnLikeNode<'a> {
             ast_map::NodeImplItem(ii) => {
                 match *ii {
                     ast::MethodImplItem(ref m) => method(&**m),
+                    ast::TypeImplItem(_) => {
+                        fail!("impl method FnLikeNode that is not fn-like")
+                    }
                 }
             }
             ast_map::NodeExpr(e) => match e.node {
diff --git a/src/libsyntax/ast_map/mod.rs b/src/libsyntax/ast_map/mod.rs
index ed0b8700bf3..a5458461a8b 100644
--- a/src/libsyntax/ast_map/mod.rs
+++ b/src/libsyntax/ast_map/mod.rs
@@ -11,11 +11,11 @@
 use abi;
 use ast::*;
 use ast_util;
-use ast_util::PostExpansionMethod;
 use codemap::{DUMMY_SP, Span, Spanned};
 use fold::Folder;
 use parse::token;
 use print::pprust;
+use ptr::P;
 use visit::{mod, Visitor};
 
 use arena::TypedArena;
@@ -391,16 +391,20 @@ impl<'ast> Map<'ast> {
                             }
                         }
                     }
+                    TypeImplItem(ref t) => PathName(t.ident.name),
                 }
             },
             NodeTraitItem(tm) => match *tm {
                 RequiredMethod(ref m) => PathName(m.ident.name),
-                ProvidedMethod(ref m) => match m.node {
-                    MethDecl(ident, _, _, _, _, _, _, _) => {
-                        PathName(ident.name)
+                ProvidedMethod(ref m) => {
+                    match m.node {
+                        MethDecl(ident, _, _, _, _, _, _, _) => {
+                            PathName(ident.name)
+                        }
+                        MethMac(_) => fail!("no path elem for {:?}", node),
                     }
-                    MethMac(_) => fail!("no path elem for {:?}", node),
                 }
+                TypeTraitItem(ref m) => PathName(m.ident.name),
             },
             NodeVariant(v) => PathName(v.node.name.name),
             _ => fail!("no path elem for {:?}", node)
@@ -459,11 +463,13 @@ impl<'ast> Map<'ast> {
             NodeForeignItem(fi) => Some(fi.attrs.as_slice()),
             NodeTraitItem(ref tm) => match **tm {
                 RequiredMethod(ref type_m) => Some(type_m.attrs.as_slice()),
-                ProvidedMethod(ref m) => Some(m.attrs.as_slice())
+                ProvidedMethod(ref m) => Some(m.attrs.as_slice()),
+                TypeTraitItem(ref typ) => Some(typ.attrs.as_slice()),
             },
             NodeImplItem(ref ii) => {
                 match **ii {
                     MethodImplItem(ref m) => Some(m.attrs.as_slice()),
+                    TypeImplItem(ref t) => Some(t.attrs.as_slice()),
                 }
             }
             NodeVariant(ref v) => Some(v.node.attrs.as_slice()),
@@ -503,11 +509,13 @@ impl<'ast> Map<'ast> {
                 match *trait_method {
                     RequiredMethod(ref type_method) => type_method.span,
                     ProvidedMethod(ref method) => method.span,
+                    TypeTraitItem(ref typedef) => typedef.span,
                 }
             }
             Some(NodeImplItem(ref impl_item)) => {
                 match **impl_item {
                     MethodImplItem(ref method) => method.span,
+                    TypeImplItem(ref typedef) => typedef.span,
                 }
             }
             Some(NodeVariant(variant)) => variant.span,
@@ -633,6 +641,7 @@ impl Named for TraitItem {
         match *self {
             RequiredMethod(ref tm) => tm.ident.name,
             ProvidedMethod(ref m) => m.name(),
+            TypeTraitItem(ref at) => at.ident.name,
         }
     }
 }
@@ -640,6 +649,7 @@ impl Named for ImplItem {
     fn name(&self) -> Name {
         match *self {
             MethodImplItem(ref m) => m.name(),
+            TypeImplItem(ref td) => td.ident.name,
         }
     }
 }
@@ -712,10 +722,14 @@ impl<'ast> Visitor<'ast> for NodeCollector<'ast> {
         match i.node {
             ItemImpl(_, _, _, ref impl_items) => {
                 for impl_item in impl_items.iter() {
-                    let id = match *impl_item {
-                        MethodImplItem(ref m) => m.id
-                    };
-                    self.insert(id, NodeImplItem(impl_item));
+                    match *impl_item {
+                        MethodImplItem(ref m) => {
+                            self.insert(m.id, NodeImplItem(impl_item));
+                        }
+                        TypeImplItem(ref t) => {
+                            self.insert(t.id, NodeImplItem(impl_item));
+                        }
+                    }
                 }
             }
             ItemEnum(ref enum_definition, _) => {
@@ -737,13 +751,28 @@ impl<'ast> Visitor<'ast> for NodeCollector<'ast> {
                     None => {}
                 }
             }
-            ItemTrait(_, _, _, ref methods) => {
-                for tm in methods.iter() {
-                    let id = match *tm {
-                        RequiredMethod(ref m) => m.id,
-                        ProvidedMethod(ref m) => m.id
-                    };
-                    self.insert(id, NodeTraitItem(tm));
+            ItemTrait(_, _, ref bounds, ref trait_items) => {
+                for b in bounds.iter() {
+                    match *b {
+                        TraitTyParamBound(ref t) => {
+                            self.insert(t.ref_id, NodeItem(i));
+                        }
+                        _ => {}
+                    }
+                }
+
+                for tm in trait_items.iter() {
+                    match *tm {
+                        RequiredMethod(ref m) => {
+                            self.insert(m.id, NodeTraitItem(tm));
+                        }
+                        ProvidedMethod(ref m) => {
+                            self.insert(m.id, NodeTraitItem(tm));
+                        }
+                        TypeTraitItem(ref typ) => {
+                            self.insert(typ.id, NodeTraitItem(tm));
+                        }
+                    }
                 }
             }
             _ => {}
@@ -892,6 +921,11 @@ pub fn map_decoded_item<'ast, F: FoldOps>(map: &Map<'ast>,
                 IITraitItem(fld.fold_ops.new_def_id(d),
                             RequiredMethod(fld.fold_type_method(ty_m)))
             }
+            TypeTraitItem(at) => {
+                IITraitItem(
+                    fld.fold_ops.new_def_id(d),
+                    TypeTraitItem(P(fld.fold_associated_type((*at).clone()))))
+            }
         },
         IIImplItem(d, m) => match m {
             MethodImplItem(m) => {
@@ -899,6 +933,10 @@ pub fn map_decoded_item<'ast, F: FoldOps>(map: &Map<'ast>,
                            MethodImplItem(fld.fold_method(m)
                                              .expect_one("expected one method")))
             }
+            TypeImplItem(t) => {
+                IIImplItem(fld.fold_ops.new_def_id(d),
+                           TypeImplItem(P(fld.fold_typedef((*t).clone()))))
+            }
         },
         IIForeign(i) => IIForeign(fld.fold_foreign_item(i))
     };
@@ -924,14 +962,16 @@ pub fn map_decoded_item<'ast, F: FoldOps>(map: &Map<'ast>,
         IITraitItem(_, ref trait_item) => {
             let trait_item_id = match *trait_item {
                 ProvidedMethod(ref m) => m.id,
-                RequiredMethod(ref m) => m.id
+                RequiredMethod(ref m) => m.id,
+                TypeTraitItem(ref ty) => ty.id,
             };
 
             collector.insert(trait_item_id, NodeTraitItem(trait_item));
         }
         IIImplItem(_, ref impl_item) => {
             let impl_item_id = match *impl_item {
-                MethodImplItem(ref m) => m.id
+                MethodImplItem(ref m) => m.id,
+                TypeImplItem(ref ti) => ti.id,
             };
 
             collector.insert(impl_item_id, NodeImplItem(impl_item));
@@ -1007,16 +1047,30 @@ fn node_id_to_string(map: &Map, id: NodeId) -> String {
                                     pprust::mac_to_string(mac), id)
                     }
                 }
+                TypeImplItem(ref t) => {
+                    format!("typedef {} in {} (id={})",
+                            token::get_ident(t.ident),
+                            map.path_to_string(id),
+                            id)
+                }
             }
         }
-        Some(NodeTraitItem(ref ti)) => {
-            let ident = match **ti {
-                ProvidedMethod(ref m) => m.pe_ident(),
-                RequiredMethod(ref m) => m.ident
-            };
-            format!("method {} in {} (id={})",
-                    token::get_ident(ident),
-                    map.path_to_string(id), id)
+        Some(NodeTraitItem(ref tm)) => {
+            match **tm {
+                RequiredMethod(_) | ProvidedMethod(_) => {
+                    let m = ast_util::trait_item_to_ty_method(&**tm);
+                    format!("method {} in {} (id={})",
+                            token::get_ident(m.ident),
+                            map.path_to_string(id),
+                            id)
+                }
+                TypeTraitItem(ref t) => {
+                    format!("type item {} in {} (id={})",
+                            token::get_ident(t.ident),
+                            map.path_to_string(id),
+                            id)
+                }
+            }
         }
         Some(NodeVariant(ref variant)) => {
             format!("variant {} in {} (id={})",
diff --git a/src/libsyntax/ast_util.rs b/src/libsyntax/ast_util.rs
index becfe715f29..6d61c851476 100644
--- a/src/libsyntax/ast_util.rs
+++ b/src/libsyntax/ast_util.rs
@@ -213,6 +213,62 @@ pub fn impl_pretty_name(trait_ref: &Option<TraitRef>, ty: &Ty) -> Ident {
     token::gensym_ident(pretty.as_slice())
 }
 
+pub fn trait_method_to_ty_method(method: &Method) -> TypeMethod {
+    match method.node {
+        MethDecl(ident,
+                 ref generics,
+                 abi,
+                 ref explicit_self,
+                 fn_style,
+                 ref decl,
+                 _,
+                 vis) => {
+            TypeMethod {
+                ident: ident,
+                attrs: method.attrs.clone(),
+                fn_style: fn_style,
+                decl: (*decl).clone(),
+                generics: generics.clone(),
+                explicit_self: (*explicit_self).clone(),
+                id: method.id,
+                span: method.span,
+                vis: vis,
+                abi: abi,
+            }
+        },
+        MethMac(_) => fail!("expected non-macro method declaration")
+    }
+}
+
+/// extract a TypeMethod from a TraitItem. if the TraitItem is
+/// a default, pull out the useful fields to make a TypeMethod
+//
+// NB: to be used only after expansion is complete, and macros are gone.
+pub fn trait_item_to_ty_method(method: &TraitItem) -> TypeMethod {
+    match *method {
+        RequiredMethod(ref m) => (*m).clone(),
+        ProvidedMethod(ref m) => trait_method_to_ty_method(&**m),
+        TypeTraitItem(_) => {
+            fail!("trait_method_to_ty_method(): expected method but found \
+                   typedef")
+        }
+    }
+}
+
+pub fn split_trait_methods(trait_methods: &[TraitItem])
+                           -> (Vec<TypeMethod>, Vec<P<Method>> ) {
+    let mut reqd = Vec::new();
+    let mut provd = Vec::new();
+    for trt_method in trait_methods.iter() {
+        match *trt_method {
+            RequiredMethod(ref tm) => reqd.push((*tm).clone()),
+            ProvidedMethod(ref m) => provd.push((*m).clone()),
+            TypeTraitItem(_) => {}
+        }
+    };
+    (reqd, provd)
+}
+
 pub fn struct_field_visibility(field: ast::StructField) -> Visibility {
     match field.node.kind {
         ast::NamedField(_, v) | ast::UnnamedField(v) => v
@@ -471,6 +527,7 @@ impl<'a, 'v, O: IdVisitingOperation> Visitor<'v> for IdVisitor<'a, O> {
         match *tm {
             ast::RequiredMethod(ref m) => self.operation.visit_id(m.id),
             ast::ProvidedMethod(ref m) => self.operation.visit_id(m.id),
+            ast::TypeTraitItem(ref typ) => self.operation.visit_id(typ.id),
         }
         visit::walk_trait_item(self, tm);
     }
diff --git a/src/libsyntax/config.rs b/src/libsyntax/config.rs
index cb96cd911b5..3b250de8701 100644
--- a/src/libsyntax/config.rs
+++ b/src/libsyntax/config.rs
@@ -235,13 +235,15 @@ fn view_item_in_cfg(cx: &mut Context, item: &ast::ViewItem) -> bool {
 fn trait_method_in_cfg(cx: &mut Context, meth: &ast::TraitItem) -> bool {
     match *meth {
         ast::RequiredMethod(ref meth) => (cx.in_cfg)(meth.attrs.as_slice()),
-        ast::ProvidedMethod(ref meth) => (cx.in_cfg)(meth.attrs.as_slice())
+        ast::ProvidedMethod(ref meth) => (cx.in_cfg)(meth.attrs.as_slice()),
+        ast::TypeTraitItem(ref typ) => (cx.in_cfg)(typ.attrs.as_slice()),
     }
 }
 
 fn impl_item_in_cfg(cx: &mut Context, impl_item: &ast::ImplItem) -> bool {
     match *impl_item {
         ast::MethodImplItem(ref meth) => (cx.in_cfg)(meth.attrs.as_slice()),
+        ast::TypeImplItem(ref typ) => (cx.in_cfg)(typ.attrs.as_slice()),
     }
 }
 
diff --git a/src/libsyntax/ext/tt/macro_rules.rs b/src/libsyntax/ext/tt/macro_rules.rs
index 6c7bbb2384c..7a7dbc54c9e 100644
--- a/src/libsyntax/ext/tt/macro_rules.rs
+++ b/src/libsyntax/ext/tt/macro_rules.rs
@@ -90,7 +90,10 @@ impl<'a> MacResult for ParserAnyMacro<'a> {
             let mut parser = self.parser.borrow_mut();
             match parser.token {
                 EOF => break,
-                _ => ret.push(parser.parse_method(None))
+                _ => {
+                    let attrs = parser.parse_outer_attributes();
+                    ret.push(parser.parse_method(attrs, ast::Inherited))
+                }
             }
         }
         self.ensure_complete_parse(false);
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index e22e55193fc..5203ed0a073 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -68,6 +68,7 @@ static KNOWN_FEATURES: &'static [(&'static str, Status)] = &[
     ("import_shadowing", Active),
     ("advanced_slice_patterns", Active),
     ("tuple_indexing", Active),
+    ("associated_types", Active),
 
     // if you change this list without updating src/doc/rust.md, cmr will be sad
 
@@ -235,7 +236,7 @@ impl<'a, 'v> Visitor<'v> for Context<'a> {
                 }
             }
 
-            ast::ItemImpl(..) => {
+            ast::ItemImpl(_, _, _, ref items) => {
                 if attr::contains_name(i.attrs.as_slice(),
                                        "unsafe_destructor") {
                     self.gate_feature("unsafe_destructor",
@@ -244,6 +245,18 @@ impl<'a, 'v> Visitor<'v> for Context<'a> {
                                        many unsafe patterns and may be \
                                        removed in the future");
                 }
+
+                for item in items.iter() {
+                    match *item {
+                        ast::MethodImplItem(_) => {}
+                        ast::TypeImplItem(ref typedef) => {
+                            self.gate_feature("associated_types",
+                                              typedef.span,
+                                              "associated types are \
+                                               experimental")
+                        }
+                    }
+                }
             }
 
             _ => {}
@@ -252,6 +265,17 @@ impl<'a, 'v> Visitor<'v> for Context<'a> {
         visit::walk_item(self, i);
     }
 
+    fn visit_trait_item(&mut self, trait_item: &ast::TraitItem) {
+        match *trait_item {
+            ast::RequiredMethod(_) | ast::ProvidedMethod(_) => {}
+            ast::TypeTraitItem(ref ti) => {
+                self.gate_feature("associated_types",
+                                  ti.span,
+                                  "associated types are experimental")
+            }
+        }
+    }
+
     fn visit_mac(&mut self, macro: &ast::Mac) {
         let ast::MacInvocTT(ref path, _, _) = macro.node;
         let id = path.segments.last().unwrap().identifier;
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index 4806c5fa7c0..3beba5bcda4 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -287,6 +287,15 @@ pub trait Folder {
         noop_fold_where_predicate(where_predicate, self)
     }
 
+    fn fold_typedef(&mut self, typedef: Typedef) -> Typedef {
+        noop_fold_typedef(typedef, self)
+    }
+
+    fn fold_associated_type(&mut self, associated_type: AssociatedType)
+                            -> AssociatedType {
+        noop_fold_associated_type(associated_type, self)
+    }
+
     fn new_id(&mut self, i: NodeId) -> NodeId {
         i
     }
@@ -414,6 +423,13 @@ pub fn noop_fold_ty<T: Folder>(t: P<Ty>, fld: &mut T) -> P<Ty> {
                         fld.fold_opt_bounds(bounds),
                         id)
             }
+            TyQPath(ref qpath) => {
+                TyQPath(P(QPath {
+                    for_type: fld.fold_ty(qpath.for_type.clone()),
+                    trait_name: fld.fold_path(qpath.trait_name.clone()),
+                    item_name: fld.fold_ident(qpath.item_name.clone()),
+                }))
+            }
             TyFixedLengthVec(ty, e) => {
                 TyFixedLengthVec(fld.fold_ty(ty), fld.fold_expr(e))
             }
@@ -735,6 +751,44 @@ pub fn noop_fold_where_predicate<T: Folder>(
     }
 }
 
+pub fn noop_fold_typedef<T>(t: Typedef, folder: &mut T)
+                            -> Typedef
+                            where T: Folder {
+    let new_id = folder.new_id(t.id);
+    let new_span = folder.new_span(t.span);
+    let new_attrs = t.attrs.iter().map(|attr| {
+        folder.fold_attribute((*attr).clone())
+    }).collect();
+    let new_ident = folder.fold_ident(t.ident);
+    let new_type = folder.fold_ty(t.typ);
+    ast::Typedef {
+        ident: new_ident,
+        typ: new_type,
+        id: new_id,
+        span: new_span,
+        vis: t.vis,
+        attrs: new_attrs,
+    }
+}
+
+pub fn noop_fold_associated_type<T>(at: AssociatedType, folder: &mut T)
+                                    -> AssociatedType
+                                    where T: Folder {
+    let new_id = folder.new_id(at.id);
+    let new_span = folder.new_span(at.span);
+    let new_ident = folder.fold_ident(at.ident);
+    let new_attrs = at.attrs
+                      .iter()
+                      .map(|attr| folder.fold_attribute((*attr).clone()))
+                      .collect();
+    ast::AssociatedType {
+        ident: new_ident,
+        attrs: new_attrs,
+        id: new_id,
+        span: new_span,
+    }
+}
+
 pub fn noop_fold_struct_def<T: Folder>(struct_def: P<StructDef>, fld: &mut T) -> P<StructDef> {
     struct_def.map(|StructDef {fields, ctor_id, super_struct, is_virtual}| StructDef {
         fields: fields.move_map(|f| fld.fold_struct_field(f)),
@@ -857,31 +911,59 @@ pub fn noop_fold_item_underscore<T: Folder>(i: Item_, folder: &mut T) -> Item_ {
             ItemStruct(struct_def, folder.fold_generics(generics))
         }
         ItemImpl(generics, ifce, ty, impl_items) => {
+            let mut new_impl_items = Vec::new();
+            for impl_item in impl_items.iter() {
+                match *impl_item {
+                    MethodImplItem(ref x) => {
+                        for method in folder.fold_method((*x).clone())
+                                            .move_iter() {
+                            new_impl_items.push(MethodImplItem(method))
+                        }
+                    }
+                    TypeImplItem(ref t) => {
+                        new_impl_items.push(TypeImplItem(
+                                P(folder.fold_typedef((**t).clone()))));
+                    }
+                }
+            }
+            let ifce = match ifce {
+                None => None,
+                Some(ref trait_ref) => {
+                    Some(folder.fold_trait_ref((*trait_ref).clone()))
+                }
+            };
             ItemImpl(folder.fold_generics(generics),
-                     ifce.map(|p| folder.fold_trait_ref(p)),
+                     ifce,
                      folder.fold_ty(ty),
-                     impl_items.into_iter().flat_map(|impl_item| match impl_item {
-                        MethodImplItem(x) => {
-                            folder.fold_method(x).into_iter().map(|x| MethodImplItem(x))
-                        }
-                     }).collect())
+                     new_impl_items)
         }
         ItemTrait(generics, unbound, bounds, methods) => {
             let bounds = folder.fold_bounds(bounds);
-            let methods = methods.into_iter().flat_map(|method| match method {
-                RequiredMethod(m) => {
-                    SmallVector::one(RequiredMethod(folder.fold_type_method(m))).into_iter()
-                }
-                ProvidedMethod(method) => {
-                    // the awkward collect/iter idiom here is because
-                    // even though an iter and a map satisfy the same trait bound,
-                    // they're not actually the same type, so the method arms
-                    // don't unify.
-                    let methods: SmallVector<ast::TraitItem> =
-                        folder.fold_method(method).into_iter()
-                        .map(|m| ProvidedMethod(m)).collect();
-                    methods.into_iter()
-                }
+            let methods = methods.into_iter().flat_map(|method| {
+                let r = match method {
+                    RequiredMethod(m) => {
+                            SmallVector::one(RequiredMethod(
+                                    folder.fold_type_method(m)))
+                                .move_iter()
+                    }
+                    ProvidedMethod(method) => {
+                        // the awkward collect/iter idiom here is because
+                        // even though an iter and a map satisfy the same
+                        // trait bound, they're not actually the same type, so
+                        // the method arms don't unify.
+                        let methods: SmallVector<ast::TraitItem> =
+                            folder.fold_method(method).move_iter()
+                            .map(|m| ProvidedMethod(m)).collect();
+                        methods.move_iter()
+                    }
+                    TypeTraitItem(at) => {
+                        SmallVector::one(TypeTraitItem(P(
+                                    folder.fold_associated_type(
+                                        (*at).clone()))))
+                            .move_iter()
+                    }
+                };
+                r
             }).collect();
             ItemTrait(folder.fold_generics(generics),
                       unbound,
@@ -893,7 +975,18 @@ pub fn noop_fold_item_underscore<T: Folder>(i: Item_, folder: &mut T) -> Item_ {
 }
 
 pub fn noop_fold_type_method<T: Folder>(m: TypeMethod, fld: &mut T) -> TypeMethod {
-    let TypeMethod {id, ident, attrs, fn_style, abi, decl, generics, explicit_self, vis, span} = m;
+    let TypeMethod {
+        id,
+        ident,
+        attrs,
+        fn_style,
+        abi,
+        decl,
+        generics,
+        explicit_self,
+        vis,
+        span
+    } = m;
     TypeMethod {
         id: fld.new_id(id),
         ident: fld.fold_ident(ident),
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index ea392c87723..ff4fd41fbd7 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -11,11 +11,11 @@
 #![macro_escape]
 
 use abi;
-use ast::{BareFnTy, ClosureTy};
+use ast::{AssociatedType, BareFnTy, ClosureTy};
 use ast::{RegionTyParamBound, TraitTyParamBound};
 use ast::{ProvidedMethod, Public, FnStyle};
 use ast::{Mod, BiAdd, Arg, Arm, Attribute, BindByRef, BindByValue};
-use ast::{BiBitAnd, BiBitOr, BiBitXor, Block};
+use ast::{BiBitAnd, BiBitOr, BiBitXor, BiRem, Block};
 use ast::{BlockCheckMode, UnBox};
 use ast::{CaptureByRef, CaptureByValue, CaptureClause};
 use ast::{Crate, CrateConfig, Decl, DeclItem};
@@ -42,7 +42,7 @@ use ast::{MatchSeq, MatchTok, Method, MutTy, BiMul, Mutability};
 use ast::{MethodImplItem, NamedField, UnNeg, NoReturn, UnNot};
 use ast::{Pat, PatEnum, PatIdent, PatLit, PatRange, PatRegion, PatStruct};
 use ast::{PatTup, PatBox, PatWild, PatWildMulti, PatWildSingle};
-use ast::{BiRem, RequiredMethod};
+use ast::{QPath, RequiredMethod};
 use ast::{RetStyle, Return, BiShl, BiShr, Stmt, StmtDecl};
 use ast::{StmtExpr, StmtSemi, StmtMac, StructDef, StructField};
 use ast::{StructVariantKind, BiSub};
@@ -52,10 +52,10 @@ use ast::{TokenTree, TraitItem, TraitRef, TTDelim, TTSeq, TTTok};
 use ast::{TTNonterminal, TupleVariantKind, Ty, Ty_, TyBot, TyBox};
 use ast::{TypeField, TyFixedLengthVec, TyClosure, TyProc, TyBareFn};
 use ast::{TyTypeof, TyInfer, TypeMethod};
-use ast::{TyNil, TyParam, TyParamBound, TyParen, TyPath, TyPtr, TyRptr};
-use ast::{TyTup, TyU32, TyUnboxedFn, TyUniq, TyVec, UnUniq};
-use ast::{UnboxedClosureKind, UnboxedFnTy, UnboxedFnTyParamBound};
-use ast::{UnnamedField, UnsafeBlock};
+use ast::{TyNil, TyParam, TyParamBound, TyParen, TyPath, TyPtr, TyQPath};
+use ast::{TyRptr, TyTup, TyU32, TyUnboxedFn, TyUniq, TyVec, UnUniq};
+use ast::{TypeImplItem, TypeTraitItem, Typedef, UnboxedClosureKind};
+use ast::{UnboxedFnTy, UnboxedFnTyParamBound, UnnamedField, UnsafeBlock};
 use ast::{UnsafeFn, ViewItem, ViewItem_, ViewItemExternCrate, ViewItemUse};
 use ast::{ViewPath, ViewPathGlob, ViewPathList, ViewPathSimple};
 use ast::{Visibility, WhereClause, WherePredicate};
@@ -1235,86 +1235,125 @@ impl<'a> Parser<'a> {
         (decl, lifetime_defs)
     }
 
-    /// Parse the methods in a trait declaration
-    pub fn parse_trait_methods(&mut self) -> Vec<TraitItem> {
+    /// Parses `type Foo;` in a trait declaration only. The `type` keyword has
+    /// already been parsed.
+    fn parse_associated_type(&mut self, attrs: Vec<Attribute>)
+                             -> AssociatedType {
+        let lo = self.span.lo;
+        let ident = self.parse_ident();
+        let hi = self.span.hi;
+        self.expect(&token::SEMI);
+        AssociatedType {
+            id: ast::DUMMY_NODE_ID,
+            span: mk_sp(lo, hi),
+            ident: ident,
+            attrs: attrs,
+        }
+    }
+
+    /// Parses `type Foo = TYPE;` in an implementation declaration only. The
+    /// `type` keyword has already been parsed.
+    fn parse_typedef(&mut self, attrs: Vec<Attribute>, vis: Visibility)
+                     -> Typedef {
+        let lo = self.span.lo;
+        let ident = self.parse_ident();
+        self.expect(&token::EQ);
+        let typ = self.parse_ty(true);
+        let hi = self.span.hi;
+        self.expect(&token::SEMI);
+        Typedef {
+            id: ast::DUMMY_NODE_ID,
+            span: mk_sp(lo, hi),
+            ident: ident,
+            vis: vis,
+            attrs: attrs,
+            typ: typ,
+        }
+    }
+
+    /// Parse the items in a trait declaration
+    pub fn parse_trait_items(&mut self) -> Vec<TraitItem> {
         self.parse_unspanned_seq(
             &token::LBRACE,
             &token::RBRACE,
             seq_sep_none(),
             |p| {
             let attrs = p.parse_outer_attributes();
-            let lo = p.span.lo;
-
-            // NB: at the moment, trait methods are public by default; this
-            // could change.
-            let vis = p.parse_visibility();
-            let abi = if p.eat_keyword(keywords::Extern) {
-                p.parse_opt_abi().unwrap_or(abi::C)
-            } else if attr::contains_name(attrs.as_slice(),
-                                          "rust_call_abi_hack") {
-                // FIXME(stage0, pcwalton): Remove this awful hack after a
-                // snapshot, and change to `extern "rust-call" fn`.
-                abi::RustCall
+
+            if p.eat_keyword(keywords::Type) {
+                TypeTraitItem(P(p.parse_associated_type(attrs)))
             } else {
-                abi::Rust
-            };
-            let style = p.parse_fn_style();
-            let ident = p.parse_ident();
+                let lo = p.span.lo;
 
-            let mut generics = p.parse_generics();
+                let vis = p.parse_visibility();
+                let abi = if p.eat_keyword(keywords::Extern) {
+                    p.parse_opt_abi().unwrap_or(abi::C)
+                } else if attr::contains_name(attrs.as_slice(),
+                                              "rust_call_abi_hack") {
+                    // FIXME(stage0, pcwalton): Remove this awful hack after a
+                    // snapshot, and change to `extern "rust-call" fn`.
+                    abi::RustCall
+                } else {
+                    abi::Rust
+                };
 
-            let (explicit_self, d) = p.parse_fn_decl_with_self(|p| {
-                // This is somewhat dubious; We don't want to allow argument
-                // names to be left off if there is a definition...
-                p.parse_arg_general(false)
-            });
+                let style = p.parse_fn_style();
+                let ident = p.parse_ident();
+                let mut generics = p.parse_generics();
 
-            p.parse_where_clause(&mut generics);
+                let (explicit_self, d) = p.parse_fn_decl_with_self(|p| {
+                    // This is somewhat dubious; We don't want to allow
+                    // argument names to be left off if there is a
+                    // definition...
+                    p.parse_arg_general(false)
+                });
 
-            let hi = p.last_span.hi;
-            match p.token {
-              token::SEMI => {
-                p.bump();
-                debug!("parse_trait_methods(): parsing required method");
-                RequiredMethod(TypeMethod {
-                    ident: ident,
-                    attrs: attrs,
-                    fn_style: style,
-                    decl: d,
-                    generics: generics,
-                    abi: abi,
-                    explicit_self: explicit_self,
-                    id: ast::DUMMY_NODE_ID,
-                    span: mk_sp(lo, hi),
-                    vis: vis,
-                })
-              }
-              token::LBRACE => {
-                debug!("parse_trait_methods(): parsing provided method");
-                let (inner_attrs, body) =
-                    p.parse_inner_attrs_and_block();
-                let mut attrs = attrs;
-                attrs.extend(inner_attrs.into_iter());
-                ProvidedMethod(P(ast::Method {
-                    attrs: attrs,
-                    id: ast::DUMMY_NODE_ID,
-                    span: mk_sp(lo, hi),
-                    node: ast::MethDecl(ident,
-                                        generics,
-                                        abi,
-                                        explicit_self,
-                                        style,
-                                        d,
-                                        body,
-                                        vis)
-                }))
-              }
+                p.parse_where_clause(&mut generics);
+
+                let hi = p.last_span.hi;
+                match p.token {
+                  token::SEMI => {
+                    p.bump();
+                    debug!("parse_trait_methods(): parsing required method");
+                    RequiredMethod(TypeMethod {
+                        ident: ident,
+                        attrs: attrs,
+                        fn_style: style,
+                        decl: d,
+                        generics: generics,
+                        abi: abi,
+                        explicit_self: explicit_self,
+                        id: ast::DUMMY_NODE_ID,
+                        span: mk_sp(lo, hi),
+                        vis: vis,
+                    })
+                  }
+                  token::LBRACE => {
+                    debug!("parse_trait_methods(): parsing provided method");
+                    let (inner_attrs, body) =
+                        p.parse_inner_attrs_and_block();
+                    let attrs = attrs.append(inner_attrs.as_slice());
+                    ProvidedMethod(P(ast::Method {
+                        attrs: attrs,
+                        id: ast::DUMMY_NODE_ID,
+                        span: mk_sp(lo, hi),
+                        node: ast::MethDecl(ident,
+                                            generics,
+                                            abi,
+                                            explicit_self,
+                                            style,
+                                            d,
+                                            body,
+                                            vis)
+                    }))
+                  }
 
-              _ => {
-                  let token_str = p.this_token_to_string();
-                  p.fatal((format!("expected `;` or `{{`, found `{}`",
-                                   token_str)).as_slice())
-              }
+                  _ => {
+                      let token_str = p.this_token_to_string();
+                      p.fatal((format!("expected `;` or `{{`, found `{}`",
+                                       token_str)).as_slice())
+                  }
+                }
             }
         })
     }
@@ -1455,12 +1494,11 @@ impl<'a> Parser<'a> {
         } else if self.token_is_closure_keyword() ||
                 self.token == token::BINOP(token::OR) ||
                 self.token == token::OROR ||
-                self.token == token::LT {
+                (self.token == token::LT &&
+                 self.look_ahead(1, |t| {
+                     *t == token::GT || Parser::token_is_lifetime(t)
+                 })) {
             // CLOSURE
-            //
-            // FIXME(pcwalton): Eventually `token::LT` will not unambiguously
-            // introduce a closure, once procs can have lifetime bounds. We
-            // will need to refactor the grammar a little bit at that point.
 
             self.parse_ty_closure()
         } else if self.eat_keyword(keywords::Typeof) {
@@ -1472,6 +1510,20 @@ impl<'a> Parser<'a> {
             TyTypeof(e)
         } else if self.eat_keyword(keywords::Proc) {
             self.parse_proc_type()
+        } else if self.token == token::LT {
+            // QUALIFIED PATH
+            self.bump();
+            let for_type = self.parse_ty(true);
+            self.expect_keyword(keywords::As);
+            let trait_name = self.parse_path(LifetimeAndTypesWithoutColons);
+            self.expect(&token::GT);
+            self.expect(&token::MOD_SEP);
+            let item_name = self.parse_ident();
+            TyQPath(P(QPath {
+                for_type: for_type,
+                trait_name: trait_name.path,
+                item_name: item_name,
+            }))
         } else if self.token == token::MOD_SEP
             || is_ident_or_path(&self.token) {
             // NAMED TYPE
@@ -2071,7 +2123,7 @@ impl<'a> Parser<'a> {
                     }
                 }
                 hi = self.last_span.hi;
-            },
+            }
             _ => {
                 if self.eat_keyword(keywords::Ref) {
                     return self.parse_lambda_expr(CaptureByRef);
@@ -4215,14 +4267,9 @@ impl<'a> Parser<'a> {
 
     /// Parse a method in a trait impl, starting with `attrs` attributes.
     pub fn parse_method(&mut self,
-                        already_parsed_attrs: Option<Vec<Attribute>>)
+                        attrs: Vec<Attribute>,
+                        visa: Visibility)
                         -> P<Method> {
-        let next_attrs = self.parse_outer_attributes();
-        let attrs = match already_parsed_attrs {
-            Some(mut a) => { a.push_all_move(next_attrs); a }
-            None => next_attrs
-        };
-
         let lo = self.span.lo;
 
         // code copied from parse_macro_use_or_failure... abstraction!
@@ -4251,7 +4298,6 @@ impl<'a> Parser<'a> {
                                                              self.span.hi) };
                 (ast::MethMac(m), self.span.hi, attrs)
             } else {
-                let visa = self.parse_visibility();
                 let abi = if self.eat_keyword(keywords::Extern) {
                     self.parse_opt_abi().unwrap_or(abi::C)
                 } else if attr::contains_name(attrs.as_slice(),
@@ -4302,18 +4348,28 @@ impl<'a> Parser<'a> {
 
         self.parse_where_clause(&mut tps);
 
-        let meths = self.parse_trait_methods();
+        let meths = self.parse_trait_items();
         (ident, ItemTrait(tps, sized, bounds, meths), None)
     }
 
     fn parse_impl_items(&mut self) -> (Vec<ImplItem>, Vec<Attribute>) {
         let mut impl_items = Vec::new();
         self.expect(&token::LBRACE);
-        let (inner_attrs, next) = self.parse_inner_attrs_and_next();
-        let mut method_attrs = Some(next);
+        let (inner_attrs, mut method_attrs) =
+            self.parse_inner_attrs_and_next();
         while !self.eat(&token::RBRACE) {
-            impl_items.push(MethodImplItem(self.parse_method(method_attrs)));
-            method_attrs = None;
+            method_attrs.push_all_move(self.parse_outer_attributes());
+            let vis = self.parse_visibility();
+            if self.eat_keyword(keywords::Type) {
+                impl_items.push(TypeImplItem(P(self.parse_typedef(
+                            method_attrs,
+                            vis))))
+            } else {
+                impl_items.push(MethodImplItem(self.parse_method(
+                            method_attrs,
+                            vis)));
+            }
+            method_attrs = self.parse_outer_attributes();
         }
         (impl_items, inner_attrs)
     }
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index d0df95d711e..0ae5303641b 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -9,10 +9,11 @@
 // except according to those terms.
 
 use abi;
-use ast::{FnMutUnboxedClosureKind, FnOnceUnboxedClosureKind};
-use ast::{FnUnboxedClosureKind, MethodImplItem};
-use ast::{RegionTyParamBound, TraitTyParamBound, UnboxedClosureKind};
-use ast::{UnboxedFnTyParamBound, RequiredMethod, ProvidedMethod};
+use ast::{FnUnboxedClosureKind, FnMutUnboxedClosureKind};
+use ast::{FnOnceUnboxedClosureKind};
+use ast::{MethodImplItem, RegionTyParamBound, TraitTyParamBound};
+use ast::{RequiredMethod, ProvidedMethod, TypeImplItem, TypeTraitItem};
+use ast::{UnboxedClosureKind, UnboxedFnTyParamBound};
 use ast;
 use ast_util;
 use owned_slice::OwnedSlice;
@@ -660,6 +661,16 @@ impl<'a> State<'a> {
             ast::TyPath(ref path, ref bounds, _) => {
                 try!(self.print_bounded_path(path, bounds));
             }
+            ast::TyQPath(ref qpath) => {
+                try!(word(&mut self.s, "<"));
+                try!(self.print_type(&*qpath.for_type));
+                try!(space(&mut self.s));
+                try!(self.word_space("as"));
+                try!(self.print_path(&qpath.trait_name, false));
+                try!(word(&mut self.s, ">"));
+                try!(word(&mut self.s, "::"));
+                try!(self.print_ident(qpath.item_name));
+            }
             ast::TyFixedLengthVec(ref ty, ref v) => {
                 try!(word(&mut self.s, "["));
                 try!(self.print_type(&**ty));
@@ -708,6 +719,22 @@ impl<'a> State<'a> {
         }
     }
 
+    fn print_associated_type(&mut self, typedef: &ast::AssociatedType)
+                             -> IoResult<()> {
+        try!(self.word_space("type"));
+        try!(self.print_ident(typedef.ident));
+        word(&mut self.s, ";")
+    }
+
+    fn print_typedef(&mut self, typedef: &ast::Typedef) -> IoResult<()> {
+        try!(self.word_space("type"));
+        try!(self.print_ident(typedef.ident));
+        try!(space(&mut self.s));
+        try!(self.word_space("="));
+        try!(self.print_type(&*typedef.typ));
+        word(&mut self.s, ";")
+    }
+
     /// Pretty-print an item
     pub fn print_item(&mut self, item: &ast::Item) -> IoResult<()> {
         try!(self.hardbreak_if_not_bol());
@@ -825,6 +852,9 @@ impl<'a> State<'a> {
                         ast::MethodImplItem(ref meth) => {
                             try!(self.print_method(&**meth));
                         }
+                        ast::TypeImplItem(ref typ) => {
+                            try!(self.print_typedef(&**typ));
+                        }
                     }
                 }
                 try!(self.bclose(item.span));
@@ -1071,13 +1101,15 @@ impl<'a> State<'a> {
                               m: &ast::TraitItem) -> IoResult<()> {
         match *m {
             RequiredMethod(ref ty_m) => self.print_ty_method(ty_m),
-            ProvidedMethod(ref m) => self.print_method(&**m)
+            ProvidedMethod(ref m) => self.print_method(&**m),
+            TypeTraitItem(ref t) => self.print_associated_type(&**t),
         }
     }
 
     pub fn print_impl_item(&mut self, ii: &ast::ImplItem) -> IoResult<()> {
         match *ii {
             MethodImplItem(ref m) => self.print_method(&**m),
+            TypeImplItem(ref td) => self.print_typedef(&**td),
         }
     }
 
diff --git a/src/libsyntax/visit.rs b/src/libsyntax/visit.rs
index 30a38e28729..d425c60f4c9 100644
--- a/src/libsyntax/visit.rs
+++ b/src/libsyntax/visit.rs
@@ -116,12 +116,19 @@ pub trait Visitor<'v> {
     fn visit_attribute(&mut self, _attr: &'v Attribute) {}
 }
 
-pub fn walk_inlined_item<'v, V: Visitor<'v>>(visitor: &mut V, item: &'v InlinedItem) {
+pub fn walk_inlined_item<'v,V>(visitor: &mut V, item: &'v InlinedItem)
+                         where V: Visitor<'v> {
     match *item {
         IIItem(ref i) => visitor.visit_item(&**i),
         IIForeign(ref i) => visitor.visit_foreign_item(&**i),
         IITraitItem(_, ref ti) => visitor.visit_trait_item(ti),
-        IIImplItem(_, MethodImplItem(ref m)) => walk_method_helper(visitor, &**m)
+        IIImplItem(_, MethodImplItem(ref m)) => {
+            walk_method_helper(visitor, &**m)
+        }
+        IIImplItem(_, TypeImplItem(ref typedef)) => {
+            visitor.visit_ident(typedef.span, typedef.ident);
+            visitor.visit_ty(&*typedef.typ);
+        }
     }
 }
 
@@ -248,6 +255,10 @@ pub fn walk_item<'v, V: Visitor<'v>>(visitor: &mut V, item: &'v Item) {
                     MethodImplItem(ref method) => {
                         walk_method_helper(visitor, &**method)
                     }
+                    TypeImplItem(ref typedef) => {
+                        visitor.visit_ident(typedef.span, typedef.ident);
+                        visitor.visit_ty(&*typedef.typ);
+                    }
                 }
             }
         }
@@ -366,6 +377,11 @@ pub fn walk_ty<'v, V: Visitor<'v>>(visitor: &mut V, typ: &'v Ty) {
                 None => { }
             }
         }
+        TyQPath(ref qpath) => {
+            visitor.visit_ty(&*qpath.for_type);
+            visitor.visit_path(&qpath.trait_name, typ.id);
+            visitor.visit_ident(typ.span, qpath.item_name);
+        }
         TyFixedLengthVec(ref ty, ref expression) => {
             visitor.visit_ty(&**ty);
             visitor.visit_expr(&**expression)
@@ -573,10 +589,11 @@ pub fn walk_ty_method<'v, V: Visitor<'v>>(visitor: &mut V, method_type: &'v Type
 
 pub fn walk_trait_item<'v, V: Visitor<'v>>(visitor: &mut V, trait_method: &'v TraitItem) {
     match *trait_method {
-        RequiredMethod(ref method_type) => {
-            visitor.visit_ty_method(method_type)
-        }
+        RequiredMethod(ref method_type) => visitor.visit_ty_method(method_type),
         ProvidedMethod(ref method) => walk_method_helper(visitor, &**method),
+        TypeTraitItem(ref associated_type) => {
+            visitor.visit_ident(associated_type.span, associated_type.ident)
+        }
     }
 }
 
diff --git a/src/test/compile-fail/associated-types-feature-gate.rs b/src/test/compile-fail/associated-types-feature-gate.rs
new file mode 100644
index 00000000000..d95b94f0067
--- /dev/null
+++ b/src/test/compile-fail/associated-types-feature-gate.rs
@@ -0,0 +1,33 @@
+// 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.
+
+trait Get {
+    type Value; //~ ERROR associated types are experimental
+    fn get(&self) -> Get::Value;
+}
+
+struct Struct {
+    x: int,
+}
+
+impl Get for Struct {
+    type Value = int;   //~ ERROR associated types are experimental
+    fn get(&self) -> int {
+        self.x
+    }
+}
+
+fn main() {
+    let s = Struct {
+        x: 100,
+    };
+    assert_eq!(s.get(), 100);
+}
+
diff --git a/src/test/compile-fail/associated-types-in-ambiguous-context.rs b/src/test/compile-fail/associated-types-in-ambiguous-context.rs
new file mode 100644
index 00000000000..a2c01fe62f6
--- /dev/null
+++ b/src/test/compile-fail/associated-types-in-ambiguous-context.rs
@@ -0,0 +1,39 @@
+// 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.
+
+#![feature(associated_types)]
+
+trait Get {
+    type Value;
+    fn get(&self) -> <Self as Get>::Value;
+}
+
+fn get<T:Get,U:Get>(x: T, y: U) -> Get::Value {}
+//~^ ERROR ambiguous associated type
+
+trait Other {
+    fn uhoh<U:Get>(&self, foo: U, bar: <Self as Get>::Value) {}
+    //~^ ERROR this associated type is not allowed in this context
+}
+
+impl<T:Get> Other for T {
+    fn uhoh<U:Get>(&self, foo: U, bar: <(T, U) as Get>::Value) {}
+    //~^ ERROR this associated type is not allowed in this context
+}
+
+trait Grab {
+    type Value;
+    fn grab(&self) -> Grab::Value;
+    //~^ ERROR ambiguous associated type
+}
+
+fn main() {
+}
+
diff --git a/src/test/compile-fail/associated-types-in-wrong-context.rs b/src/test/compile-fail/associated-types-in-wrong-context.rs
new file mode 100644
index 00000000000..8fbfc33896b
--- /dev/null
+++ b/src/test/compile-fail/associated-types-in-wrong-context.rs
@@ -0,0 +1,32 @@
+// 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.
+
+#![feature(associated_types)]
+
+trait Get {
+    type Value;
+    fn get(&self) -> <Self as Get>::Value;
+}
+
+fn get(x: int) -> <int as Get>::Value {}
+//~^ ERROR this associated type is not allowed in this context
+
+struct Struct {
+    x: int,
+}
+
+impl Struct {
+    fn uhoh<T>(foo: <T as Get>::Value) {}
+    //~^ ERROR this associated type is not allowed in this context
+}
+
+fn main() {
+}
+
diff --git a/src/test/compile-fail/class-method-missing.rs b/src/test/compile-fail/class-method-missing.rs
index ca97a899768..17cf36b73f6 100644
--- a/src/test/compile-fail/class-method-missing.rs
+++ b/src/test/compile-fail/class-method-missing.rs
@@ -17,7 +17,7 @@ struct cat {
 }
 
 impl animal for cat {
-    //~^ ERROR not all trait methods implemented, missing: `eat`
+    //~^ ERROR not all trait items implemented, missing: `eat`
 }
 
 fn cat(in_x : uint) -> cat {
diff --git a/src/test/compile-fail/issue-3344.rs b/src/test/compile-fail/issue-3344.rs
index 293f372866d..b88272ed466 100644
--- a/src/test/compile-fail/issue-3344.rs
+++ b/src/test/compile-fail/issue-3344.rs
@@ -10,7 +10,7 @@
 
 #[deriving(PartialEq)]
 struct thing(uint);
-impl PartialOrd for thing { //~ ERROR not all trait methods implemented, missing: `partial_cmp`
+impl PartialOrd for thing { //~ ERROR not all trait items implemented, missing: `partial_cmp`
     fn le(&self, other: &thing) -> bool { true }
     fn ge(&self, other: &thing) -> bool { true }
 }
diff --git a/src/test/compile-fail/missing-derivable-attr.rs b/src/test/compile-fail/missing-derivable-attr.rs
index 4e45f33fe9b..db960ac3409 100644
--- a/src/test/compile-fail/missing-derivable-attr.rs
+++ b/src/test/compile-fail/missing-derivable-attr.rs
@@ -20,7 +20,7 @@ impl MyEq for int {
     fn eq(&self, other: &int) -> bool { *self == *other }
 }
 
-impl MyEq for A {}  //~ ERROR not all trait methods implemented, missing: `eq`
+impl MyEq for A {}  //~ ERROR not all trait items implemented, missing: `eq`
 
 fn main() {
 }
diff --git a/src/test/run-pass/associated-types-in-default-method.rs b/src/test/run-pass/associated-types-in-default-method.rs
new file mode 100644
index 00000000000..e01b18a64db
--- /dev/null
+++ b/src/test/run-pass/associated-types-in-default-method.rs
@@ -0,0 +1,39 @@
+// 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.
+
+#![feature(associated_types)]
+
+trait Get {
+    type Value;
+    fn get(&self) -> &<Self as Get>::Value;
+    fn grab(&self) -> &<Self as Get>::Value {
+        self.get()
+    }
+}
+
+struct Struct {
+    x: int,
+}
+
+impl Get for Struct {
+    type Value = int;
+    fn get(&self) -> &int {
+        &self.x
+    }
+}
+
+fn main() {
+    let s = Struct {
+        x: 100,
+    };
+    assert_eq!(*s.grab(), 100);
+}
+
+
diff --git a/src/test/run-pass/associated-types-in-fn.rs b/src/test/run-pass/associated-types-in-fn.rs
new file mode 100644
index 00000000000..4ed213e85d8
--- /dev/null
+++ b/src/test/run-pass/associated-types-in-fn.rs
@@ -0,0 +1,39 @@
+// 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.
+
+#![feature(associated_types)]
+
+trait Get {
+    type Value;
+    fn get(&self) -> &<Self as Get>::Value;
+}
+
+struct Struct {
+    x: int,
+}
+
+impl Get for Struct {
+    type Value = int;
+    fn get(&self) -> &int {
+        &self.x
+    }
+}
+
+fn grab<T:Get>(x: &T) -> &<T as Get>::Value {
+    x.get()
+}
+
+fn main() {
+    let s = Struct {
+        x: 100,
+    };
+    assert_eq!(*grab(&s), 100);
+}
+
diff --git a/src/test/run-pass/associated-types-in-impl-generics.rs b/src/test/run-pass/associated-types-in-impl-generics.rs
new file mode 100644
index 00000000000..f6aaaf3b3fa
--- /dev/null
+++ b/src/test/run-pass/associated-types-in-impl-generics.rs
@@ -0,0 +1,47 @@
+// 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.
+
+#![feature(associated_types)]
+
+trait Get {
+    type Value;
+    fn get(&self) -> &<Self as Get>::Value;
+}
+
+struct Struct {
+    x: int,
+}
+
+impl Get for Struct {
+    type Value = int;
+    fn get(&self) -> &int {
+        &self.x
+    }
+}
+
+trait Grab {
+    type U;
+    fn grab(&self) -> &<Self as Grab>::U;
+}
+
+impl<T:Get> Grab for T {
+    type U = <T as Get>::Value;
+    fn grab(&self) -> &<T as Get>::Value {
+        self.get()
+    }
+}
+
+fn main() {
+    let s = Struct {
+        x: 100,
+    };
+    assert_eq!(*s.grab(), 100);
+}
+
diff --git a/src/test/run-pass/associated-types-in-inherent-method.rs b/src/test/run-pass/associated-types-in-inherent-method.rs
new file mode 100644
index 00000000000..34168269246
--- /dev/null
+++ b/src/test/run-pass/associated-types-in-inherent-method.rs
@@ -0,0 +1,41 @@
+// 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.
+
+#![feature(associated_types)]
+
+trait Get {
+    type Value;
+    fn get(&self) -> &<Self as Get>::Value;
+}
+
+struct Struct {
+    x: int,
+}
+
+impl Get for Struct {
+    type Value = int;
+    fn get(&self) -> &int {
+        &self.x
+    }
+}
+
+impl Struct {
+    fn grab<T:Get>(x: &T) -> &<T as Get>::Value {
+        x.get()
+    }
+}
+
+fn main() {
+    let s = Struct {
+        x: 100,
+    };
+    assert_eq!(*Struct::grab(&s), 100);
+}
+
diff --git a/src/test/run-pass/associated-types-simple.rs b/src/test/run-pass/associated-types-simple.rs
new file mode 100644
index 00000000000..82ae0d89b46
--- /dev/null
+++ b/src/test/run-pass/associated-types-simple.rs
@@ -0,0 +1,35 @@
+// 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.
+
+#![feature(associated_types)]
+
+trait Get {
+    type Value;
+    fn get(&self) -> &<Self as Get>::Value;
+}
+
+struct Struct {
+    x: int,
+}
+
+impl Get for Struct {
+    type Value = int;
+    fn get(&self) -> &int {
+        &self.x
+    }
+}
+
+fn main() {
+    let s = Struct {
+        x: 100,
+    };
+    assert_eq!(*s.get(), 100);
+}
+
diff --git a/src/test/run-pass/macro-method-issue-4621.rs b/src/test/run-pass/macro-method-issue-4621.rs
index 99d47e4bfc0..b5400edb41f 100644
--- a/src/test/run-pass/macro-method-issue-4621.rs
+++ b/src/test/run-pass/macro-method-issue-4621.rs
@@ -12,7 +12,7 @@
 
 struct A;
 
-macro_rules! make_thirteen_method {() => (pub fn thirteen(&self)->int {13})}
+macro_rules! make_thirteen_method {() => (fn thirteen(&self)->int {13})}
 impl A { make_thirteen_method!() }
 
 fn main() {