Auto merge of #35091 - eddyb:impl-trait, r=nikomatsakis

Implement `impl Trait` in return type position by anonymization.

This is the first step towards implementing `impl Trait` (cc #34511).
`impl Trait` types are only allowed in function and inherent method return types, and capture all named lifetime and type parameters, being invariant over them.
No lifetimes that are not explicitly named lifetime parameters are allowed to escape from the function body.
The exposed traits are only those listed explicitly, i.e. `Foo` and `Clone` in `impl Foo + Clone`, with the exception of "auto traits" (like `Send` or `Sync`) which "leak" the actual contents.

The implementation strategy is anonymization, i.e.:
```rust
fn foo<T>(xs: Vec<T>) -> impl Iterator<Item=impl FnOnce() -> T> {
    xs.into_iter().map(|x| || x)
}

// is represented as:
type A</*invariant over*/ T> where A<T>: Iterator<Item=B<T>>;
type B</*invariant over*/ T> where B<T>: FnOnce() -> T;
fn foo<T>(xs: Vec<T>) -> A<T> {
    xs.into_iter().map(|x| || x): $0 where $0: Iterator<Item=$1>, $1: FnOnce() -> T
}
```
`$0` and `$1` are resolved (to `iter::Map<vec::Iter<T>, closure>` and the closure, respectively) and assigned to `A` and `B`, after checking the body of `foo`. `A` and `B` are *never* resolved for user-facing type equality (typeck), but always for the low-level representation and specialization (trans).

The "auto traits" exception is implemented by collecting bounds like `impl Trait: Send` that have failed for the obscure `impl Trait` type (i.e. `A` or `B` above), pretending they succeeded within the function and trying them again after type-checking the whole crate, by replacing `impl Trait` with the real type.

While passing around values which have explicit lifetime parameters (of the function with `-> impl Trait`) in their type *should* work, regionck appears to assign inference variables in *way* too many cases, and never properly resolving them to either explicit lifetime parameters, or `'static`.
We might not be able to handle lifetime parameters in `impl Trait` without changes to lifetime inference, but type parameters can have arbitrary lifetimes in them from the caller, so most type-generic usecases (or not generic at all) should not run into this problem.

cc @rust-lang/lang

99 files changed, 2788 insertions, 532 deletions

diff --git a/src/librustc/hir/fold.rs b/src/librustc/hir/fold.rs
index 5e0e6622185..dd79e14f077 100644
--- a/src/librustc/hir/fold.rs
+++ b/src/librustc/hir/fold.rs
@@ -375,6 +375,9 @@ pub fn noop_fold_ty<T: Folder>(t: P<Ty>, fld: &mut T) -> P<Ty> {
                 TyPolyTraitRef(bounds) => {
                     TyPolyTraitRef(bounds.move_map(|b| fld.fold_ty_param_bound(b)))
                 }
+                TyImplTrait(bounds) => {
+                    TyImplTrait(bounds.move_map(|b| fld.fold_ty_param_bound(b)))
+                }
             },
             span: fld.new_span(span),
         }
diff --git a/src/librustc/hir/intravisit.rs b/src/librustc/hir/intravisit.rs
index aded220c0cd..1162c290f9c 100644
--- a/src/librustc/hir/intravisit.rs
+++ b/src/librustc/hir/intravisit.rs
@@ -427,6 +427,9 @@ pub fn walk_ty<'v, V: Visitor<'v>>(visitor: &mut V, typ: &'v Ty) {
         TyPolyTraitRef(ref bounds) => {
             walk_list!(visitor, visit_ty_param_bound, bounds);
         }
+        TyImplTrait(ref bounds) => {
+            walk_list!(visitor, visit_ty_param_bound, bounds);
+        }
         TyTypeof(ref expression) => {
             visitor.visit_expr(expression)
         }
diff --git a/src/librustc/hir/lowering.rs b/src/librustc/hir/lowering.rs
index 789b70ccfa4..eb98ed77da7 100644
--- a/src/librustc/hir/lowering.rs
+++ b/src/librustc/hir/lowering.rs
@@ -293,8 +293,10 @@ impl<'a> LoweringContext<'a> {
                     hir::TyTypeof(self.lower_expr(expr))
                 }
                 PolyTraitRef(ref bounds) => {
-                    let bounds = bounds.iter().map(|b| self.lower_ty_param_bound(b)).collect();
-                    hir::TyPolyTraitRef(bounds)
+                    hir::TyPolyTraitRef(self.lower_bounds(bounds))
+                }
+                ImplTrait(ref bounds) => {
+                    hir::TyImplTrait(self.lower_bounds(bounds))
                 }
                 Mac(_) => panic!("TyMac should have been expanded by now."),
             },
diff --git a/src/librustc/hir/map/collector.rs b/src/librustc/hir/map/collector.rs
index b3f222b22e8..b70190181af 100644
--- a/src/librustc/hir/map/collector.rs
+++ b/src/librustc/hir/map/collector.rs
@@ -194,6 +194,14 @@ impl<'ast> Visitor<'ast> for NodeCollector<'ast> {
         });
     }
 
+    fn visit_ty(&mut self, ty: &'ast Ty) {
+        self.insert(ty.id, NodeTy(ty));
+
+        self.with_parent(ty.id, |this| {
+            intravisit::walk_ty(this, ty);
+        });
+    }
+
     fn visit_fn(&mut self, fk: intravisit::FnKind<'ast>, fd: &'ast FnDecl,
                 b: &'ast Block, s: Span, id: NodeId) {
         assert_eq!(self.parent_node, id);
diff --git a/src/librustc/hir/map/def_collector.rs b/src/librustc/hir/map/def_collector.rs
index 58bbd8add26..752b0e9a253 100644
--- a/src/librustc/hir/map/def_collector.rs
+++ b/src/librustc/hir/map/def_collector.rs
@@ -268,6 +268,9 @@ impl<'ast> visit::Visitor for DefCollector<'ast> {
         if let TyKind::FixedLengthVec(_, ref length) = ty.node {
             self.visit_ast_const_integer(length);
         }
+        if let TyKind::ImplTrait(..) = ty.node {
+            self.create_def(ty.id, DefPathData::ImplTrait);
+        }
         visit::walk_ty(self, ty);
     }
 
@@ -428,6 +431,9 @@ impl<'ast> intravisit::Visitor<'ast> for DefCollector<'ast> {
         if let hir::TyFixedLengthVec(_, ref length) = ty.node {
             self.visit_hir_const_integer(length);
         }
+        if let hir::TyImplTrait(..) = ty.node {
+            self.create_def(ty.id, DefPathData::ImplTrait);
+        }
         intravisit::walk_ty(self, ty);
     }
 
diff --git a/src/librustc/hir/map/definitions.rs b/src/librustc/hir/map/definitions.rs
index e3425d7fa61..901a489728e 100644
--- a/src/librustc/hir/map/definitions.rs
+++ b/src/librustc/hir/map/definitions.rs
@@ -215,6 +215,8 @@ pub enum DefPathData {
     Initializer,
     /// Pattern binding
     Binding(InternedString),
+    /// An `impl Trait` type node.
+    ImplTrait
 }
 
 impl Definitions {
@@ -369,6 +371,10 @@ impl DefPathData {
             Initializer => {
                 InternedString::new("{{initializer}}")
             }
+
+            ImplTrait => {
+                InternedString::new("{{impl-Trait}}")
+            }
         }
     }
 
diff --git a/src/librustc/hir/map/mod.rs b/src/librustc/hir/map/mod.rs
index 86d29a6fc71..7e82a4a05a7 100644
--- a/src/librustc/hir/map/mod.rs
+++ b/src/librustc/hir/map/mod.rs
@@ -50,6 +50,7 @@ pub enum Node<'ast> {
     NodeVariant(&'ast Variant),
     NodeExpr(&'ast Expr),
     NodeStmt(&'ast Stmt),
+    NodeTy(&'ast Ty),
     NodeLocal(&'ast Pat),
     NodePat(&'ast Pat),
     NodeBlock(&'ast Block),
@@ -76,6 +77,7 @@ pub enum MapEntry<'ast> {
     EntryVariant(NodeId, &'ast Variant),
     EntryExpr(NodeId, &'ast Expr),
     EntryStmt(NodeId, &'ast Stmt),
+    EntryTy(NodeId, &'ast Ty),
     EntryLocal(NodeId, &'ast Pat),
     EntryPat(NodeId, &'ast Pat),
     EntryBlock(NodeId, &'ast Block),
@@ -104,6 +106,7 @@ impl<'ast> MapEntry<'ast> {
             NodeVariant(n) => EntryVariant(p, n),
             NodeExpr(n) => EntryExpr(p, n),
             NodeStmt(n) => EntryStmt(p, n),
+            NodeTy(n) => EntryTy(p, n),
             NodeLocal(n) => EntryLocal(p, n),
             NodePat(n) => EntryPat(p, n),
             NodeBlock(n) => EntryBlock(p, n),
@@ -122,6 +125,7 @@ impl<'ast> MapEntry<'ast> {
             EntryVariant(id, _) => id,
             EntryExpr(id, _) => id,
             EntryStmt(id, _) => id,
+            EntryTy(id, _) => id,
             EntryLocal(id, _) => id,
             EntryPat(id, _) => id,
             EntryBlock(id, _) => id,
@@ -144,6 +148,7 @@ impl<'ast> MapEntry<'ast> {
             EntryVariant(_, n) => NodeVariant(n),
             EntryExpr(_, n) => NodeExpr(n),
             EntryStmt(_, n) => NodeStmt(n),
+            EntryTy(_, n) => NodeTy(n),
             EntryLocal(_, n) => NodeLocal(n),
             EntryPat(_, n) => NodePat(n),
             EntryBlock(_, n) => NodeBlock(n),
@@ -257,6 +262,7 @@ impl<'ast> Map<'ast> {
                     EntryVariant(p, _) |
                     EntryExpr(p, _) |
                     EntryStmt(p, _) |
+                EntryTy(p, _) |
                     EntryLocal(p, _) |
                     EntryPat(p, _) |
                     EntryBlock(p, _) |
@@ -297,6 +303,7 @@ impl<'ast> Map<'ast> {
                     EntryVariant(p, _) |
                     EntryExpr(p, _) |
                     EntryStmt(p, _) |
+                    EntryTy(p, _) |
                     EntryLocal(p, _) |
                     EntryPat(p, _) |
                     EntryBlock(p, _) |
@@ -680,6 +687,7 @@ impl<'ast> Map<'ast> {
             Some(NodeVariant(variant)) => variant.span,
             Some(NodeExpr(expr)) => expr.span,
             Some(NodeStmt(stmt)) => stmt.span,
+            Some(NodeTy(ty)) => ty.span,
             Some(NodeLocal(pat)) => pat.span,
             Some(NodePat(pat)) => pat.span,
             Some(NodeBlock(block)) => block.span,
@@ -971,6 +979,7 @@ impl<'a> NodePrinter for pprust::State<'a> {
             NodeVariant(a)     => self.print_variant(&a),
             NodeExpr(a)        => self.print_expr(&a),
             NodeStmt(a)        => self.print_stmt(&a),
+            NodeTy(a)          => self.print_type(&a),
             NodePat(a)         => self.print_pat(&a),
             NodeBlock(a)       => self.print_block(&a),
             NodeLifetime(a)    => self.print_lifetime(&a),
@@ -1059,6 +1068,9 @@ fn node_id_to_string(map: &Map, id: NodeId, include_id: bool) -> String {
         Some(NodeStmt(ref stmt)) => {
             format!("stmt {}{}", pprust::stmt_to_string(&stmt), id_str)
         }
+        Some(NodeTy(ref ty)) => {
+            format!("type {}{}", pprust::ty_to_string(&ty), id_str)
+        }
         Some(NodeLocal(ref pat)) => {
             format!("local {}{}", pprust::pat_to_string(&pat), id_str)
         }
diff --git a/src/librustc/hir/mod.rs b/src/librustc/hir/mod.rs
index 9212fda6502..707ef987c2c 100644
--- a/src/librustc/hir/mod.rs
+++ b/src/librustc/hir/mod.rs
@@ -1132,6 +1132,8 @@ pub enum Ty_ {
     TyObjectSum(P<Ty>, TyParamBounds),
     /// A type like `for<'a> Foo<&'a Bar>`
     TyPolyTraitRef(TyParamBounds),
+    /// An `impl TraitA+TraitB` type.
+    TyImplTrait(TyParamBounds),
     /// Unused for now
     TyTypeof(P<Expr>),
     /// TyInfer means the type should be inferred instead of it having been
diff --git a/src/librustc/hir/print.rs b/src/librustc/hir/print.rs
index 5f2fac5c01b..6dedae5ccd7 100644
--- a/src/librustc/hir/print.rs
+++ b/src/librustc/hir/print.rs
@@ -536,6 +536,9 @@ impl<'a> State<'a> {
             hir::TyPolyTraitRef(ref bounds) => {
                 self.print_bounds("", &bounds[..])?;
             }
+            hir::TyImplTrait(ref bounds) => {
+                self.print_bounds("impl ", &bounds[..])?;
+            }
             hir::TyFixedLengthVec(ref ty, ref v) => {
                 word(&mut self.s, "[")?;
                 self.print_type(&ty)?;
diff --git a/src/librustc/infer/freshen.rs b/src/librustc/infer/freshen.rs
index 880661a882a..1fb4e59e131 100644
--- a/src/librustc/infer/freshen.rs
+++ b/src/librustc/infer/freshen.rs
@@ -170,7 +170,8 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
             ty::TyClosure(..) |
             ty::TyTuple(..) |
             ty::TyProjection(..) |
-            ty::TyParam(..) => {
+            ty::TyParam(..) |
+            ty::TyAnon(..) => {
                 t.super_fold_with(self)
             }
         }
diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index be9adf7085c..697478015cb 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -34,7 +34,7 @@ use ty::{self, Ty, TyCtxt};
 use ty::error::{ExpectedFound, TypeError, UnconstrainedNumeric};
 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
 use ty::relate::{Relate, RelateResult, TypeRelation};
-use traits::{self, PredicateObligations, ProjectionMode};
+use traits::{self, PredicateObligations, Reveal};
 use rustc_data_structures::unify::{self, UnificationTable};
 use std::cell::{Cell, RefCell, Ref, RefMut};
 use std::fmt;
@@ -147,8 +147,8 @@ pub struct InferCtxt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 
     // Sadly, the behavior of projection varies a bit depending on the
     // stage of compilation. The specifics are given in the
-    // documentation for `ProjectionMode`.
-    projection_mode: ProjectionMode,
+    // documentation for `Reveal`.
+    projection_mode: Reveal,
 
     // When an error occurs, we want to avoid reporting "derived"
     // errors that are due to this original failure. Normally, we
@@ -459,7 +459,7 @@ pub struct InferCtxtBuilder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     arenas: ty::CtxtArenas<'tcx>,
     tables: Option<RefCell<ty::Tables<'tcx>>>,
     param_env: Option<ty::ParameterEnvironment<'gcx>>,
-    projection_mode: ProjectionMode,
+    projection_mode: Reveal,
     normalize: bool
 }
 
@@ -467,7 +467,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'gcx> {
     pub fn infer_ctxt(self,
                       tables: Option<ty::Tables<'tcx>>,
                       param_env: Option<ty::ParameterEnvironment<'gcx>>,
-                      projection_mode: ProjectionMode)
+                      projection_mode: Reveal)
                       -> InferCtxtBuilder<'a, 'gcx, 'tcx> {
         InferCtxtBuilder {
             global_tcx: self,
@@ -479,7 +479,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'gcx> {
         }
     }
 
-    pub fn normalizing_infer_ctxt(self, projection_mode: ProjectionMode)
+    pub fn normalizing_infer_ctxt(self, projection_mode: Reveal)
                                   -> InferCtxtBuilder<'a, 'gcx, 'tcx> {
         InferCtxtBuilder {
             global_tcx: self,
@@ -509,7 +509,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'gcx> {
             projection_cache: RefCell::new(traits::ProjectionCache::new()),
             reported_trait_errors: RefCell::new(FnvHashSet()),
             normalize: false,
-            projection_mode: ProjectionMode::AnyFinal,
+            projection_mode: Reveal::NotSpecializable,
             tainted_by_errors_flag: Cell::new(false),
             err_count_on_creation: self.sess.err_count(),
             obligations_in_snapshot: Cell::new(false),
@@ -641,7 +641,7 @@ impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
             return value;
         }
 
-        self.infer_ctxt(None, None, ProjectionMode::Any).enter(|infcx| {
+        self.infer_ctxt(None, None, Reveal::All).enter(|infcx| {
             value.trans_normalize(&infcx)
         })
     }
@@ -659,7 +659,7 @@ impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
             return value;
         }
 
-        self.infer_ctxt(None, Some(env.clone()), ProjectionMode::Any).enter(|infcx| {
+        self.infer_ctxt(None, Some(env.clone()), Reveal::All).enter(|infcx| {
             value.trans_normalize(&infcx)
        })
     }
@@ -736,7 +736,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         Ok(self.tcx.erase_regions(&result))
     }
 
-    pub fn projection_mode(&self) -> ProjectionMode {
+    pub fn projection_mode(&self) -> Reveal {
         self.projection_mode
     }
 
diff --git a/src/librustc/middle/intrinsicck.rs b/src/librustc/middle/intrinsicck.rs
index d753381d71e..15f2f21ef25 100644
--- a/src/librustc/middle/intrinsicck.rs
+++ b/src/librustc/middle/intrinsicck.rs
@@ -12,7 +12,7 @@ use dep_graph::DepNode;
 use hir::def::Def;
 use hir::def_id::DefId;
 use infer::InferCtxt;
-use traits::ProjectionMode;
+use traits::Reveal;
 use ty::{self, Ty, TyCtxt};
 use ty::layout::{LayoutError, Pointer, SizeSkeleton};
 
@@ -36,7 +36,7 @@ struct ItemVisitor<'a, 'tcx: 'a> {
 impl<'a, 'tcx> ItemVisitor<'a, 'tcx> {
     fn visit_const(&mut self, item_id: ast::NodeId, expr: &hir::Expr) {
         let param_env = ty::ParameterEnvironment::for_item(self.tcx, item_id);
-        self.tcx.infer_ctxt(None, Some(param_env), ProjectionMode::Any).enter(|infcx| {
+        self.tcx.infer_ctxt(None, Some(param_env), Reveal::All).enter(|infcx| {
             let mut visitor = ExprVisitor {
                 infcx: &infcx
             };
@@ -114,7 +114,7 @@ impl<'a, 'gcx, 'tcx> ExprVisitor<'a, 'gcx, 'tcx> {
 impl<'a, 'tcx, 'v> Visitor<'v> for ItemVisitor<'a, 'tcx> {
     // const, static and N in [T; N].
     fn visit_expr(&mut self, expr: &hir::Expr) {
-        self.tcx.infer_ctxt(None, None, ProjectionMode::Any).enter(|infcx| {
+        self.tcx.infer_ctxt(None, None, Reveal::All).enter(|infcx| {
             let mut visitor = ExprVisitor {
                 infcx: &infcx
             };
@@ -144,7 +144,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for ItemVisitor<'a, 'tcx> {
             span_bug!(s, "intrinsicck: closure outside of function")
         }
         let param_env = ty::ParameterEnvironment::for_item(self.tcx, id);
-        self.tcx.infer_ctxt(None, Some(param_env), ProjectionMode::Any).enter(|infcx| {
+        self.tcx.infer_ctxt(None, Some(param_env), Reveal::All).enter(|infcx| {
             let mut visitor = ExprVisitor {
                 infcx: &infcx
             };
diff --git a/src/librustc/middle/liveness.rs b/src/librustc/middle/liveness.rs
index 1222b5f42a1..f62c9a5d882 100644
--- a/src/librustc/middle/liveness.rs
+++ b/src/librustc/middle/liveness.rs
@@ -113,7 +113,7 @@ use dep_graph::DepNode;
 use hir::def::*;
 use hir::pat_util;
 use ty::{self, TyCtxt, ParameterEnvironment};
-use traits::{self, ProjectionMode};
+use traits::{self, Reveal};
 use ty::subst::Subst;
 use lint;
 use util::nodemap::NodeMap;
@@ -1484,7 +1484,7 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> {
                 let param_env = ParameterEnvironment::for_item(self.ir.tcx, id);
                 let t_ret_subst = t_ret.subst(self.ir.tcx, &param_env.free_substs);
                 let is_nil = self.ir.tcx.infer_ctxt(None, Some(param_env),
-                                                    ProjectionMode::Any).enter(|infcx| {
+                                                    Reveal::All).enter(|infcx| {
                     let cause = traits::ObligationCause::dummy();
                     traits::fully_normalize(&infcx, cause, &t_ret_subst).unwrap().is_nil()
                 });
diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index aa74fb2e02f..76c73f12f4e 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -832,7 +832,10 @@ fn insert_late_bound_lifetimes(map: &mut NamedRegionMap,
         constrained_by_input.visit_ty(&arg.ty);
     }
 
-    let mut appears_in_output = AllCollector { regions: FnvHashSet() };
+    let mut appears_in_output = AllCollector {
+        regions: FnvHashSet(),
+        impl_trait: false
+    };
     intravisit::walk_fn_ret_ty(&mut appears_in_output, &decl.output);
 
     debug!("insert_late_bound_lifetimes: constrained_by_input={:?}",
@@ -842,7 +845,10 @@ fn insert_late_bound_lifetimes(map: &mut NamedRegionMap,
     //
     // Subtle point: because we disallow nested bindings, we can just
     // ignore binders here and scrape up all names we see.
-    let mut appears_in_where_clause = AllCollector { regions: FnvHashSet() };
+    let mut appears_in_where_clause = AllCollector {
+        regions: FnvHashSet(),
+        impl_trait: false
+    };
     for ty_param in generics.ty_params.iter() {
         walk_list!(&mut appears_in_where_clause,
                    visit_ty_param_bound,
@@ -864,12 +870,16 @@ fn insert_late_bound_lifetimes(map: &mut NamedRegionMap,
     // Late bound regions are those that:
     // - appear in the inputs
     // - do not appear in the where-clauses
+    // - are not implicitly captured by `impl Trait`
     for lifetime in &generics.lifetimes {
         let name = lifetime.lifetime.name;
 
         // appears in the where clauses? early-bound.
         if appears_in_where_clause.regions.contains(&name) { continue; }
 
+        // any `impl Trait` in the return type? early-bound.
+        if appears_in_output.impl_trait { continue; }
+
         // does not appear in the inputs, but appears in the return
         // type? eventually this will be early-bound, but for now we
         // just mark it so we can issue warnings.
@@ -932,12 +942,20 @@ fn insert_late_bound_lifetimes(map: &mut NamedRegionMap,
 
     struct AllCollector {
         regions: FnvHashSet<ast::Name>,
+        impl_trait: bool
     }
 
     impl<'v> Visitor<'v> for AllCollector {
         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
             self.regions.insert(lifetime_ref.name);
         }
+
+        fn visit_ty(&mut self, ty: &hir::Ty) {
+            if let hir::TyImplTrait(_) = ty.node {
+                self.impl_trait = true;
+            }
+            intravisit::walk_ty(self, ty);
+        }
     }
 }
 
diff --git a/src/librustc/traits/coherence.rs b/src/librustc/traits/coherence.rs
index 4344eb1ebf6..37193d45e68 100644
--- a/src/librustc/traits/coherence.rs
+++ b/src/librustc/traits/coherence.rs
@@ -281,7 +281,7 @@ fn ty_is_local_constructor(tcx: TyCtxt, ty: Ty, infer_is_local: InferIsLocal)->
             true
         }
 
-        ty::TyClosure(..) => {
+        ty::TyClosure(..) | ty::TyAnon(..) => {
             bug!("ty_is_local invoked on unexpected type: {:?}", ty)
         }
     }
diff --git a/src/librustc/traits/error_reporting.rs b/src/librustc/traits/error_reporting.rs
index 62a31133a54..09b5a34fdf3 100644
--- a/src/librustc/traits/error_reporting.rs
+++ b/src/librustc/traits/error_reporting.rs
@@ -211,6 +211,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                 ty::TyTuple(..) => Some(12),
                 ty::TyProjection(..) => Some(13),
                 ty::TyParam(..) => Some(14),
+                ty::TyAnon(..) => Some(15),
                 ty::TyInfer(..) | ty::TyError => None
             }
         }
diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index 23ffa4db96f..5ba7b914d65 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -10,7 +10,8 @@
 
 use dep_graph::DepGraph;
 use infer::{InferCtxt, InferOk};
-use ty::{self, Ty, TypeFoldable, ToPolyTraitRef, TyCtxt};
+use ty::{self, Ty, TypeFoldable, ToPolyTraitRef, TyCtxt, ToPredicate};
+use ty::subst::{Substs, Subst};
 use rustc_data_structures::obligation_forest::{ObligationForest, Error};
 use rustc_data_structures::obligation_forest::{ForestObligation, ObligationProcessor};
 use std::marker::PhantomData;
@@ -22,10 +23,9 @@ use util::nodemap::{FnvHashSet, NodeMap};
 use super::CodeAmbiguity;
 use super::CodeProjectionError;
 use super::CodeSelectionError;
-use super::FulfillmentError;
-use super::FulfillmentErrorCode;
-use super::ObligationCause;
-use super::PredicateObligation;
+use super::{FulfillmentError, FulfillmentErrorCode, SelectionError};
+use super::{ObligationCause, BuiltinDerivedObligation};
+use super::{PredicateObligation, TraitObligation, Obligation};
 use super::project;
 use super::select::SelectionContext;
 use super::Unimplemented;
@@ -51,6 +51,7 @@ pub struct GlobalFulfilledPredicates<'tcx> {
 /// along. Once all type inference constraints have been generated, the
 /// method `select_all_or_error` can be used to report any remaining
 /// ambiguous cases as errors.
+
 pub struct FulfillmentContext<'tcx> {
     // A list of all obligations that have been registered with this
     // fulfillment context.
@@ -84,6 +85,10 @@ pub struct FulfillmentContext<'tcx> {
     // obligations (otherwise, it's easy to fail to walk to a
     // particular node-id).
     region_obligations: NodeMap<Vec<RegionObligation<'tcx>>>,
+
+    // A list of obligations that need to be deferred to
+    // a later time for them to be properly fulfilled.
+    deferred_obligations: Vec<DeferredObligation<'tcx>>,
 }
 
 #[derive(Clone)]
@@ -99,6 +104,90 @@ pub struct PendingPredicateObligation<'tcx> {
     pub stalled_on: Vec<Ty<'tcx>>,
 }
 
+/// An obligation which cannot be fulfilled in the context
+/// it was registered in, such as auto trait obligations on
+/// `impl Trait`, which require the concrete type to be
+/// available, only guaranteed after finishing type-checking.
+#[derive(Clone, Debug)]
+pub struct DeferredObligation<'tcx> {
+    pub predicate: ty::PolyTraitPredicate<'tcx>,
+    pub cause: ObligationCause<'tcx>
+}
+
+impl<'a, 'gcx, 'tcx> DeferredObligation<'tcx> {
+    /// If possible, create a `DeferredObligation` from
+    /// a trait predicate which had failed selection,
+    /// but could succeed later.
+    pub fn from_select_error(tcx: TyCtxt<'a, 'gcx, 'tcx>,
+                             obligation: &TraitObligation<'tcx>,
+                             selection_err: &SelectionError<'tcx>)
+                             -> Option<DeferredObligation<'tcx>> {
+        if let Unimplemented = *selection_err {
+            if DeferredObligation::must_defer(tcx, &obligation.predicate) {
+                return Some(DeferredObligation {
+                    predicate: obligation.predicate.clone(),
+                    cause: obligation.cause.clone()
+                });
+            }
+        }
+
+        None
+    }
+
+    /// Returns true if the given trait predicate can be
+    /// fulfilled at a later time.
+    pub fn must_defer(tcx: TyCtxt<'a, 'gcx, 'tcx>,
+                      predicate: &ty::PolyTraitPredicate<'tcx>)
+                      -> bool {
+        // Auto trait obligations on `impl Trait`.
+        if tcx.trait_has_default_impl(predicate.def_id()) {
+            let substs = predicate.skip_binder().trait_ref.substs;
+            if substs.types.as_slice().len() == 1 && substs.regions.is_empty() {
+                if let ty::TyAnon(..) = predicate.skip_binder().self_ty().sty {
+                    return true;
+                }
+            }
+        }
+
+        false
+    }
+
+    /// If possible, return the nested obligations required
+    /// to fulfill this obligation.
+    pub fn try_select(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>)
+                      -> Option<Vec<PredicateObligation<'tcx>>> {
+        if let ty::TyAnon(def_id, substs) = self.predicate.skip_binder().self_ty().sty {
+            // We can resolve the `impl Trait` to its concrete type.
+            if let Some(ty_scheme) = tcx.opt_lookup_item_type(def_id) {
+                let concrete_ty = ty_scheme.ty.subst(tcx, substs);
+                let concrete_substs = Substs::new_trait(vec![], vec![], concrete_ty);
+                let predicate = ty::TraitRef {
+                    def_id: self.predicate.def_id(),
+                    substs: tcx.mk_substs(concrete_substs)
+                }.to_predicate();
+
+                let original_obligation = Obligation::new(self.cause.clone(),
+                                                          self.predicate.clone());
+                let cause = original_obligation.derived_cause(BuiltinDerivedObligation);
+                return Some(vec![Obligation::new(cause, predicate)]);
+            }
+        }
+
+        None
+    }
+
+    /// Return the `PredicateObligation` this was created from.
+    pub fn to_obligation(&self) -> PredicateObligation<'tcx> {
+        let predicate = ty::Predicate::Trait(self.predicate.clone());
+        Obligation::new(self.cause.clone(), predicate)
+    }
+
+    /// Return an error as if this obligation had failed.
+    pub fn to_error(&self) -> FulfillmentError<'tcx> {
+        FulfillmentError::new(self.to_obligation(), CodeSelectionError(Unimplemented))
+    }
+}
+
 impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
     /// Creates a new fulfillment context.
     pub fn new() -> FulfillmentContext<'tcx> {
@@ -106,6 +195,7 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
             predicates: ObligationForest::new(),
             rfc1592_obligations: Vec::new(),
             region_obligations: NodeMap(),
+            deferred_obligations: vec![],
         }
     }
 
@@ -224,10 +314,16 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
     {
         self.select_where_possible(infcx)?;
 
+        // Fail all of the deferred obligations that haven't
+        // been otherwise removed from the context.
+        let deferred_errors = self.deferred_obligations.iter()
+                                  .map(|d| d.to_error());
+
         let errors: Vec<_> =
             self.predicates.to_errors(CodeAmbiguity)
                            .into_iter()
                            .map(|e| to_fulfillment_error(e))
+                           .chain(deferred_errors)
                            .collect();
         if errors.is_empty() {
             Ok(())
@@ -248,6 +344,10 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
         self.predicates.pending_obligations()
     }
 
+    pub fn take_deferred_obligations(&mut self) -> Vec<DeferredObligation<'tcx>> {
+        mem::replace(&mut self.deferred_obligations, vec![])
+    }
+
     /// Attempts to select obligations using `selcx`. If `only_new_obligations` is true, then it
     /// only attempts to select obligations that haven't been seen before.
     fn select(&mut self, selcx: &mut SelectionContext<'a, 'gcx, 'tcx>)
@@ -261,9 +361,10 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
 
             // Process pending obligations.
             let outcome = self.predicates.process_obligations(&mut FulfillProcessor {
-                    selcx: selcx,
-                    region_obligations: &mut self.region_obligations,
-                    rfc1592_obligations: &mut self.rfc1592_obligations
+                selcx: selcx,
+                region_obligations: &mut self.region_obligations,
+                rfc1592_obligations: &mut self.rfc1592_obligations,
+                deferred_obligations: &mut self.deferred_obligations
             });
             debug!("select: outcome={:?}", outcome);
 
@@ -298,7 +399,8 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
 struct FulfillProcessor<'a, 'b: 'a, 'gcx: 'tcx, 'tcx: 'b> {
     selcx: &'a mut SelectionContext<'b, 'gcx, 'tcx>,
     region_obligations: &'a mut NodeMap<Vec<RegionObligation<'tcx>>>,
-    rfc1592_obligations: &'a mut Vec<PredicateObligation<'tcx>>
+    rfc1592_obligations: &'a mut Vec<PredicateObligation<'tcx>>,
+    deferred_obligations: &'a mut Vec<DeferredObligation<'tcx>>
 }
 
 impl<'a, 'b, 'gcx, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'gcx, 'tcx> {
@@ -312,7 +414,8 @@ impl<'a, 'b, 'gcx, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'gcx,
         process_predicate(self.selcx,
                           obligation,
                           self.region_obligations,
-                          self.rfc1592_obligations)
+                          self.rfc1592_obligations,
+                          self.deferred_obligations)
             .map(|os| os.map(|os| os.into_iter().map(|o| PendingPredicateObligation {
                 obligation: o,
                 stalled_on: vec![]
@@ -354,7 +457,8 @@ fn process_predicate<'a, 'gcx, 'tcx>(
     selcx: &mut SelectionContext<'a, 'gcx, 'tcx>,
     pending_obligation: &mut PendingPredicateObligation<'tcx>,
     region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>,
-    rfc1592_obligations: &mut Vec<PredicateObligation<'tcx>>)
+    rfc1592_obligations: &mut Vec<PredicateObligation<'tcx>>,
+    deferred_obligations: &mut Vec<DeferredObligation<'tcx>>)
     -> Result<Option<Vec<PredicateObligation<'tcx>>>,
               FulfillmentErrorCode<'tcx>>
 {
@@ -422,7 +526,22 @@ fn process_predicate<'a, 'gcx, 'tcx>(
                 Err(selection_err) => {
                     info!("selecting trait `{:?}` at depth {} yielded Err",
                           data, obligation.recursion_depth);
-                    Err(CodeSelectionError(selection_err))
+
+                    let defer = DeferredObligation::from_select_error(selcx.tcx(),
+                                                                      &trait_obligation,
+                                                                      &selection_err);
+                    if let Some(deferred_obligation) = defer {
+                        if let Some(nested) = deferred_obligation.try_select(selcx.tcx()) {
+                            Ok(Some(nested))
+                        } else {
+                            // Pretend that the obligation succeeded,
+                            // but record it for later.
+                            deferred_obligations.push(deferred_obligation);
+                            Ok(Some(vec![]))
+                        }
+                    } else {
+                        Err(CodeSelectionError(selection_err))
+                    }
                 }
             }
         }
@@ -629,6 +748,12 @@ impl<'a, 'gcx, 'tcx> GlobalFulfilledPredicates<'gcx> {
             // already has the required read edges, so we don't need
             // to add any more edges here.
             if data.is_global() {
+                // Don't cache predicates which were fulfilled
+                // by deferring them for later fulfillment.
+                if DeferredObligation::must_defer(tcx, data) {
+                    return;
+                }
+
                 if let Some(data) = tcx.lift_to_global(data) {
                     if self.set.insert(data.clone()) {
                         debug!("add_if_global: global predicate `{:?}` added", data);
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index 17aa6544fe7..dc0807ba38f 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -30,9 +30,10 @@ pub use self::coherence::orphan_check;
 pub use self::coherence::overlapping_impls;
 pub use self::coherence::OrphanCheckErr;
 pub use self::fulfill::{FulfillmentContext, GlobalFulfilledPredicates, RegionObligation};
+pub use self::fulfill::DeferredObligation;
 pub use self::project::MismatchedProjectionTypes;
 pub use self::project::{normalize, normalize_projection_type, Normalized};
-pub use self::project::{ProjectionCache, ProjectionCacheSnapshot, ProjectionMode};
+pub use self::project::{ProjectionCache, ProjectionCacheSnapshot, Reveal};
 pub use self::object_safety::ObjectSafetyViolation;
 pub use self::object_safety::MethodViolationCode;
 pub use self::select::{EvaluationCache, SelectionContext, SelectionCache};
@@ -435,7 +436,7 @@ pub fn normalize_param_env_or_error<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     let elaborated_env = unnormalized_env.with_caller_bounds(predicates);
 
-    tcx.infer_ctxt(None, Some(elaborated_env), ProjectionMode::AnyFinal).enter(|infcx| {
+    tcx.infer_ctxt(None, Some(elaborated_env), Reveal::NotSpecializable).enter(|infcx| {
         let predicates = match fully_normalize(&infcx, cause,
                                                &infcx.parameter_environment.caller_bounds) {
             Ok(predicates) => predicates,
diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs
index 30faf1a5f8b..aed4f439324 100644
--- a/src/librustc/traits/project.rs
+++ b/src/librustc/traits/project.rs
@@ -38,7 +38,7 @@ use std::rc::Rc;
 /// Depending on the stage of compilation, we want projection to be
 /// more or less conservative.
 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
-pub enum ProjectionMode {
+pub enum Reveal {
     /// FIXME (#32205)
     /// At coherence-checking time, we're still constructing the
     /// specialization graph, and thus we only project
@@ -67,7 +67,7 @@ pub enum ProjectionMode {
     ///
     /// The projection would succeed if `Output` had been defined
     /// directly in the impl for `u8`.
-    Topmost,
+    ExactMatch,
 
     /// At type-checking time, we refuse to project any associated
     /// type that is marked `default`. Non-`default` ("final") types
@@ -91,36 +91,22 @@ pub enum ProjectionMode {
     /// fn main() {
     ///     let <() as Assoc>::Output = true;
     /// }
-    AnyFinal,
+    NotSpecializable,
 
-    /// At trans time, all projections will succeed.
-    Any,
-}
-
-impl ProjectionMode {
-    pub fn is_topmost(&self) -> bool {
-        match *self {
-            ProjectionMode::Topmost => true,
-            _ => false,
-        }
-    }
-
-    pub fn is_any_final(&self) -> bool {
-        match *self {
-            ProjectionMode::AnyFinal => true,
-            _ => false,
-        }
-    }
-
-    pub fn is_any(&self) -> bool {
-        match *self {
-            ProjectionMode::Any => true,
-            _ => false,
-        }
-    }
+    /// At trans time, all monomorphic projections will succeed.
+    /// Also, `impl Trait` is normalized to the concrete type,
+    /// which has to be already collected by type-checking.
+    ///
+    /// NOTE: As `impl Trait`'s concrete type should *never*
+    /// be observable directly by the user, `Reveal::All`
+    /// should not be used by checks which may expose
+    /// type equality or type contents to the user.
+    /// There are some exceptions, e.g. around OIBITS and
+    /// transmute-checking, which expose some details, but
+    /// not the whole concrete type of the `impl Trait`.
+    All,
 }
 
-
 pub type PolyProjectionObligation<'tcx> =
     Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>;
 
@@ -322,6 +308,17 @@ impl<'a, 'b, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for AssociatedTypeNormalizer<'a,
 
         let ty = ty.super_fold_with(self);
         match ty.sty {
+            ty::TyAnon(def_id, substs) if !substs.has_escaping_regions() => { // (*)
+                // Only normalize `impl Trait` after type-checking, usually in trans.
+                if self.selcx.projection_mode() == Reveal::All {
+                    let generic_ty = self.tcx().lookup_item_type(def_id).ty;
+                    let concrete_ty = generic_ty.subst(self.tcx(), substs);
+                    self.fold_ty(concrete_ty)
+                } else {
+                    ty
+                }
+            }
+
             ty::TyProjection(ref data) if !data.has_escaping_regions() => { // (*)
 
                 // (*) This is kind of hacky -- we need to be able to
@@ -797,8 +794,11 @@ fn assemble_candidates_from_trait_def<'cx, 'gcx, 'tcx>(
     debug!("assemble_candidates_from_trait_def(..)");
 
     // Check whether the self-type is itself a projection.
-    let trait_ref = match obligation_trait_ref.self_ty().sty {
-        ty::TyProjection(ref data) => data.trait_ref.clone(),
+    let (def_id, substs) = match obligation_trait_ref.self_ty().sty {
+        ty::TyProjection(ref data) => {
+            (data.trait_ref.def_id, data.trait_ref.substs)
+        }
+        ty::TyAnon(def_id, substs) => (def_id, substs),
         ty::TyInfer(ty::TyVar(_)) => {
             // If the self-type is an inference variable, then it MAY wind up
             // being a projected type, so induce an ambiguity.
@@ -809,8 +809,8 @@ fn assemble_candidates_from_trait_def<'cx, 'gcx, 'tcx>(
     };
 
     // If so, extract what we know from the trait and try to come up with a good answer.
-    let trait_predicates = selcx.tcx().lookup_predicates(trait_ref.def_id);
-    let bounds = trait_predicates.instantiate(selcx.tcx(), trait_ref.substs);
+    let trait_predicates = selcx.tcx().lookup_predicates(def_id);
+    let bounds = trait_predicates.instantiate(selcx.tcx(), substs);
     let bounds = elaborate_predicates(selcx.tcx(), bounds.predicates.into_vec());
     assemble_candidates_from_predicates(selcx,
                                         obligation,
@@ -902,7 +902,7 @@ fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx>(
 
                 candidate_set.vec.push(ProjectionTyCandidate::Select);
             }
-            super::VtableImpl(ref impl_data) if !selcx.projection_mode().is_any() => {
+            super::VtableImpl(ref impl_data) => {
                 // We have to be careful when projecting out of an
                 // impl because of specialization. If we are not in
                 // trans (i.e., projection mode is not "any"), and the
@@ -926,37 +926,43 @@ fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx>(
                                                  impl_data.impl_def_id,
                                                  obligation.predicate.item_name);
                 let new_candidate = if let Some(node_item) = opt_node_item {
-                    if node_item.node.is_from_trait() {
-                        if node_item.item.ty.is_some() {
-                            // The impl inherited a `type Foo =
-                            // Bar` given in the trait, which is
-                            // implicitly default. No candidate.
-                            None
-                        } else {
-                            // The impl did not specify `type` and neither
-                            // did the trait:
-                            //
-                            // ```rust
-                            // trait Foo { type T; }
-                            // impl Foo for Bar { }
-                            // ```
-                            //
-                            // This is an error, but it will be
-                            // reported in `check_impl_items_against_trait`.
-                            // We accept it here but will flag it as
-                            // an error when we confirm the candidate
-                            // (which will ultimately lead to `normalize_to_error`
-                            // being invoked).
+                    let is_default = if node_item.node.is_from_trait() {
+                        // If true, the impl inherited a `type Foo = Bar`
+                        // given in the trait, which is implicitly default.
+                        // Otherwise, the impl did not specify `type` and
+                        // neither did the trait:
+                        //
+                        // ```rust
+                        // trait Foo { type T; }
+                        // impl Foo for Bar { }
+                        // ```
+                        //
+                        // This is an error, but it will be
+                        // reported in `check_impl_items_against_trait`.
+                        // We accept it here but will flag it as
+                        // an error when we confirm the candidate
+                        // (which will ultimately lead to `normalize_to_error`
+                        // being invoked).
+                        node_item.item.ty.is_some()
+                    } else {
+                        node_item.item.defaultness.is_default()
+                    };
+
+                    // Only reveal a specializable default if we're past type-checking
+                    // and the obligations is monomorphic, otherwise passes such as
+                    // transmute checking and polymorphic MIR optimizations could
+                    // get a result which isn't correct for all monomorphizations.
+                    if !is_default {
+                        Some(ProjectionTyCandidate::Select)
+                    } else if selcx.projection_mode() == Reveal::All {
+                        assert!(!poly_trait_ref.needs_infer());
+                        if !poly_trait_ref.needs_subst() {
                             Some(ProjectionTyCandidate::Select)
+                        } else {
+                            None
                         }
-                    } else if node_item.item.defaultness.is_default() {
-                        // The impl specified `default type Foo =
-                        // Bar`. No candidate.
-                        None
                     } else {
-                        // The impl specified `type Foo = Bar`
-                        // with no default. Add a candidate.
-                        Some(ProjectionTyCandidate::Select)
+                        None
                     }
                 } else {
                     // This is saying that neither the trait nor
@@ -1006,11 +1012,6 @@ fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx>(
                 };
                 candidate_set.vec.extend(new_candidate);
             }
-            super::VtableImpl(_) => {
-                // In trans mode, we can just project out of impls, no prob.
-                assert!(selcx.projection_mode().is_any());
-                candidate_set.vec.push(ProjectionTyCandidate::Select);
-            }
             super::VtableParam(..) => {
                 // This case tell us nothing about the value of an
                 // associated type. Consider:
@@ -1332,7 +1333,7 @@ fn confirm_impl_candidate<'cx, 'gcx, 'tcx>(
 /// starting from the given impl.
 ///
 /// Based on the "projection mode", this lookup may in fact only examine the
-/// topmost impl. See the comments for `ProjectionMode` for more details.
+/// topmost impl. See the comments for `Reveal` for more details.
 fn assoc_ty_def<'cx, 'gcx, 'tcx>(
     selcx: &SelectionContext<'cx, 'gcx, 'tcx>,
     impl_def_id: DefId,
@@ -1341,7 +1342,7 @@ fn assoc_ty_def<'cx, 'gcx, 'tcx>(
 {
     let trait_def_id = selcx.tcx().impl_trait_ref(impl_def_id).unwrap().def_id;
 
-    if selcx.projection_mode().is_topmost() {
+    if selcx.projection_mode() == Reveal::ExactMatch {
         let impl_node = specialization_graph::Node::Impl(impl_def_id);
         for item in impl_node.items(selcx.tcx()) {
             if let ty::TypeTraitItem(assoc_ty) = item {
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 7a20b43b8f2..2df492e507b 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -23,7 +23,7 @@ use super::{PredicateObligation, TraitObligation, ObligationCause};
 use super::{ObligationCauseCode, BuiltinDerivedObligation, ImplDerivedObligation};
 use super::{SelectionError, Unimplemented, OutputTypeParameterMismatch};
 use super::{ObjectCastObligation, Obligation};
-use super::ProjectionMode;
+use super::Reveal;
 use super::TraitNotObjectSafe;
 use super::Selection;
 use super::SelectionResult;
@@ -343,7 +343,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         self.infcx
     }
 
-    pub fn projection_mode(&self) -> ProjectionMode {
+    pub fn projection_mode(&self) -> Reveal {
         self.infcx.projection_mode()
     }
 
@@ -1158,20 +1158,17 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
 
         // before we go into the whole skolemization thing, just
         // quickly check if the self-type is a projection at all.
-        let trait_def_id = match obligation.predicate.0.trait_ref.self_ty().sty {
-            ty::TyProjection(ref data) => data.trait_ref.def_id,
+        match obligation.predicate.0.trait_ref.self_ty().sty {
+            ty::TyProjection(_) | ty::TyAnon(..) => {}
             ty::TyInfer(ty::TyVar(_)) => {
                 span_bug!(obligation.cause.span,
                     "Self=_ should have been handled by assemble_candidates");
             }
-            _ => { return; }
-        };
-
-        debug!("assemble_candidates_for_projected_tys: trait_def_id={:?}",
-               trait_def_id);
+            _ => return
+        }
 
         let result = self.probe(|this, snapshot| {
-            this.match_projection_obligation_against_bounds_from_trait(obligation,
+            this.match_projection_obligation_against_definition_bounds(obligation,
                                                                        snapshot)
         });
 
@@ -1180,7 +1177,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         }
     }
 
-    fn match_projection_obligation_against_bounds_from_trait(
+    fn match_projection_obligation_against_definition_bounds(
         &mut self,
         obligation: &TraitObligation<'tcx>,
         snapshot: &infer::CombinedSnapshot)
@@ -1190,28 +1187,29 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             self.infcx().resolve_type_vars_if_possible(&obligation.predicate);
         let (skol_trait_predicate, skol_map) =
             self.infcx().skolemize_late_bound_regions(&poly_trait_predicate, snapshot);
-        debug!("match_projection_obligation_against_bounds_from_trait: \
+        debug!("match_projection_obligation_against_definition_bounds: \
                 skol_trait_predicate={:?} skol_map={:?}",
                skol_trait_predicate,
                skol_map);
 
-        let projection_trait_ref = match skol_trait_predicate.trait_ref.self_ty().sty {
-            ty::TyProjection(ref data) => &data.trait_ref,
+        let (def_id, substs) = match skol_trait_predicate.trait_ref.self_ty().sty {
+            ty::TyProjection(ref data) => (data.trait_ref.def_id, data.trait_ref.substs),
+            ty::TyAnon(def_id, substs) => (def_id, substs),
             _ => {
                 span_bug!(
                     obligation.cause.span,
-                    "match_projection_obligation_against_bounds_from_trait() called \
+                    "match_projection_obligation_against_definition_bounds() called \
                      but self-ty not a projection: {:?}",
                     skol_trait_predicate.trait_ref.self_ty());
             }
         };
-        debug!("match_projection_obligation_against_bounds_from_trait: \
-                projection_trait_ref={:?}",
-               projection_trait_ref);
+        debug!("match_projection_obligation_against_definition_bounds: \
+                def_id={:?}, substs={:?}",
+               def_id, substs);
 
-        let trait_predicates = self.tcx().lookup_predicates(projection_trait_ref.def_id);
-        let bounds = trait_predicates.instantiate(self.tcx(), projection_trait_ref.substs);
-        debug!("match_projection_obligation_against_bounds_from_trait: \
+        let item_predicates = self.tcx().lookup_predicates(def_id);
+        let bounds = item_predicates.instantiate(self.tcx(), substs);
+        debug!("match_projection_obligation_against_definition_bounds: \
                 bounds={:?}",
                bounds);
 
@@ -1226,7 +1224,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                                                     &skol_map,
                                                     snapshot)));
 
-        debug!("match_projection_obligation_against_bounds_from_trait: \
+        debug!("match_projection_obligation_against_definition_bounds: \
                 matching_bound={:?}",
                matching_bound);
         match matching_bound {
@@ -1472,7 +1470,8 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                     }
                 }
                 ty::TyParam(..) |
-                ty::TyProjection(..) => {
+                ty::TyProjection(..) |
+                ty::TyAnon(..) => {
                     // In these cases, we don't know what the actual
                     // type is.  Therefore, we cannot break it down
                     // into its constituent types. So we don't
@@ -1796,7 +1795,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 }))
             }
 
-            ty::TyProjection(_) | ty::TyParam(_) => None,
+            ty::TyProjection(_) | ty::TyParam(_) | ty::TyAnon(..) => None,
             ty::TyInfer(ty::TyVar(_)) => Ambiguous,
 
             ty::TyInfer(ty::FreshTy(_))
@@ -1842,7 +1841,8 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 Where(ty::Binder(tys.to_vec()))
             }
 
-            ty::TyStruct(..) | ty::TyEnum(..) | ty::TyProjection(..) | ty::TyParam(..) => {
+            ty::TyStruct(..) | ty::TyEnum(..) |
+            ty::TyProjection(..) | ty::TyParam(..) | ty::TyAnon(..) => {
                 // Fallback to whatever user-defined impls exist in this case.
                 None
             }
@@ -1893,6 +1893,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             ty::TyTrait(..) |
             ty::TyParam(..) |
             ty::TyProjection(..) |
+            ty::TyAnon(..) |
             ty::TyInfer(ty::TyVar(_)) |
             ty::TyInfer(ty::FreshTy(_)) |
             ty::TyInfer(ty::FreshIntTy(_)) |
@@ -2073,7 +2074,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     {
         self.in_snapshot(|this, snapshot| {
             let result =
-                this.match_projection_obligation_against_bounds_from_trait(obligation,
+                this.match_projection_obligation_against_definition_bounds(obligation,
                                                                            snapshot);
             assert!(result);
         })
@@ -2127,7 +2128,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                           obligation)
             };
 
-            let cause = self.derived_cause(obligation, BuiltinDerivedObligation);
+            let cause = obligation.derived_cause(BuiltinDerivedObligation);
             self.collect_predicates_for_types(cause,
                                               obligation.recursion_depth+1,
                                               trait_def,
@@ -2207,7 +2208,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     {
         debug!("vtable_default_impl: nested={:?}", nested);
 
-        let cause = self.derived_cause(obligation, BuiltinDerivedObligation);
+        let cause = obligation.derived_cause(BuiltinDerivedObligation);
         let mut obligations = self.collect_predicates_for_types(
             cause,
             obligation.recursion_depth+1,
@@ -2218,7 +2219,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             let poly_trait_ref = obligation.predicate.to_poly_trait_ref();
             let (trait_ref, skol_map) =
                 this.infcx().skolemize_late_bound_regions(&poly_trait_ref, snapshot);
-            let cause = this.derived_cause(obligation, ImplDerivedObligation);
+            let cause = obligation.derived_cause(ImplDerivedObligation);
             this.impl_or_trait_obligations(cause,
                                            obligation.recursion_depth + 1,
                                            trait_def_id,
@@ -2253,7 +2254,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 this.rematch_impl(impl_def_id, obligation,
                                   snapshot);
             debug!("confirm_impl_candidate substs={:?}", substs);
-            let cause = this.derived_cause(obligation, ImplDerivedObligation);
+            let cause = obligation.derived_cause(ImplDerivedObligation);
             this.vtable_impl(impl_def_id, substs, cause,
                              obligation.recursion_depth + 1,
                              skol_map, snapshot)
@@ -2906,12 +2907,13 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             }).collect();
         self.infcx().plug_leaks(skol_map, snapshot, &predicates)
     }
+}
 
+impl<'tcx> TraitObligation<'tcx> {
     #[allow(unused_comparisons)]
-    fn derived_cause(&self,
-                     obligation: &TraitObligation<'tcx>,
-                     variant: fn(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>)
-                     -> ObligationCause<'tcx>
+    pub fn derived_cause(&self,
+                        variant: fn(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>)
+                        -> ObligationCause<'tcx>
     {
         /*!
          * Creates a cause for obligations that are derived from
@@ -2923,6 +2925,8 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
          * reporting.
          */
 
+        let obligation = self;
+
         // NOTE(flaper87): As of now, it keeps track of the whole error
         // chain. Ideally, we should have a way to configure this either
         // by using -Z verbose or just a CLI argument.
diff --git a/src/librustc/traits/specialize/mod.rs b/src/librustc/traits/specialize/mod.rs
index 9348def1311..38cccb9753d 100644
--- a/src/librustc/traits/specialize/mod.rs
+++ b/src/librustc/traits/specialize/mod.rs
@@ -25,7 +25,7 @@ use hir::def_id::DefId;
 use infer::{InferCtxt, TypeOrigin};
 use middle::region;
 use ty::subst::{Subst, Substs};
-use traits::{self, ProjectionMode, ObligationCause, Normalized};
+use traits::{self, Reveal, ObligationCause, Normalized};
 use ty::{self, TyCtxt};
 use syntax_pos::DUMMY_SP;
 
@@ -151,7 +151,7 @@ pub fn specializes<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                              .unwrap()
                              .subst(tcx, &penv.free_substs);
 
-    let result = tcx.normalizing_infer_ctxt(ProjectionMode::Topmost).enter(|mut infcx| {
+    let result = tcx.normalizing_infer_ctxt(Reveal::ExactMatch).enter(|mut infcx| {
         // Normalize the trait reference, adding any obligations
         // that arise into the impl1 assumptions.
         let Normalized { value: impl1_trait_ref, obligations: normalization_obligations } = {
diff --git a/src/librustc/traits/specialize/specialization_graph.rs b/src/librustc/traits/specialize/specialization_graph.rs
index ae7deb48f86..a47cd23c64a 100644
--- a/src/librustc/traits/specialize/specialization_graph.rs
+++ b/src/librustc/traits/specialize/specialization_graph.rs
@@ -14,7 +14,7 @@ use std::rc::Rc;
 use super::{OverlapError, specializes};
 
 use hir::def_id::DefId;
-use traits::{self, ProjectionMode};
+use traits::{self, Reveal};
 use ty::{self, TyCtxt, ImplOrTraitItem, TraitDef, TypeFoldable};
 use ty::fast_reject::{self, SimplifiedType};
 use syntax::ast::Name;
@@ -111,8 +111,7 @@ impl<'a, 'gcx, 'tcx> Children {
             let possible_sibling = *slot;
 
             let tcx = tcx.global_tcx();
-            let (le, ge) = tcx.infer_ctxt(None, None,
-                                          ProjectionMode::Topmost).enter(|infcx| {
+            let (le, ge) = tcx.infer_ctxt(None, None, Reveal::ExactMatch).enter(|infcx| {
                 let overlap = traits::overlapping_impls(&infcx,
                                                         possible_sibling,
                                                         impl_def_id);
diff --git a/src/librustc/traits/structural_impls.rs b/src/librustc/traits/structural_impls.rs
index e210d2da94c..022566642f6 100644
--- a/src/librustc/traits/structural_impls.rs
+++ b/src/librustc/traits/structural_impls.rs
@@ -14,6 +14,7 @@ use ty::{Lift, TyCtxt};
 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
 
 use std::fmt;
+use std::rc::Rc;
 
 // structural impls for the structs in traits
 
@@ -162,6 +163,86 @@ impl<'a, 'tcx> Lift<'tcx> for traits::SelectionError<'a> {
     }
 }
 
+impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCauseCode<'a> {
+    type Lifted = traits::ObligationCauseCode<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        match *self {
+            super::MiscObligation => Some(super::MiscObligation),
+            super::SliceOrArrayElem => Some(super::SliceOrArrayElem),
+            super::TupleElem => Some(super::TupleElem),
+            super::ProjectionWf(proj) => tcx.lift(&proj).map(super::ProjectionWf),
+            super::ItemObligation(def_id) => Some(super::ItemObligation(def_id)),
+            super::ReferenceOutlivesReferent(ty) => {
+                tcx.lift(&ty).map(super::ReferenceOutlivesReferent)
+            }
+            super::ObjectCastObligation(ty) => {
+                tcx.lift(&ty).map(super::ObjectCastObligation)
+            }
+            super::AssignmentLhsSized => Some(super::AssignmentLhsSized),
+            super::StructInitializerSized => Some(super::StructInitializerSized),
+            super::VariableType(id) => Some(super::VariableType(id)),
+            super::ReturnType => Some(super::ReturnType),
+            super::RepeatVec => Some(super::RepeatVec),
+            super::ClosureCapture(node_id, span, bound) => {
+                Some(super::ClosureCapture(node_id, span, bound))
+            }
+            super::FieldSized => Some(super::FieldSized),
+            super::ConstSized => Some(super::ConstSized),
+            super::SharedStatic => Some(super::SharedStatic),
+            super::BuiltinDerivedObligation(ref cause) => {
+                tcx.lift(cause).map(super::BuiltinDerivedObligation)
+            }
+            super::ImplDerivedObligation(ref cause) => {
+                tcx.lift(cause).map(super::ImplDerivedObligation)
+            }
+            super::CompareImplMethodObligation => {
+                Some(super::CompareImplMethodObligation)
+            }
+        }
+    }
+}
+
+impl<'a, 'tcx> Lift<'tcx> for traits::DerivedObligationCause<'a> {
+    type Lifted = traits::DerivedObligationCause<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        tcx.lift(&self.parent_trait_ref).and_then(|trait_ref| {
+            tcx.lift(&*self.parent_code).map(|code| {
+                traits::DerivedObligationCause {
+                    parent_trait_ref: trait_ref,
+                    parent_code: Rc::new(code)
+                }
+            })
+        })
+    }
+}
+
+impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCause<'a> {
+    type Lifted = traits::ObligationCause<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        tcx.lift(&self.code).map(|code| {
+            traits::ObligationCause {
+                span: self.span,
+                body_id: self.body_id,
+                code: code,
+            }
+        })
+    }
+}
+
+impl<'a, 'tcx> Lift<'tcx> for traits::DeferredObligation<'a> {
+    type Lifted = traits::DeferredObligation<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        tcx.lift(&self.predicate).and_then(|predicate| {
+            tcx.lift(&self.cause).map(|cause| {
+                traits::DeferredObligation {
+                    predicate: predicate,
+                    cause: cause
+                }
+            })
+        })
+    }
+}
+
 // For trans only.
 impl<'a, 'tcx> Lift<'tcx> for traits::Vtable<'a, ()> {
     type Lifted = traits::Vtable<'tcx, ()>;
@@ -361,3 +442,103 @@ impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Normalized<'tcx, T> {
         self.value.visit_with(visitor) || self.obligations.visit_with(visitor)
     }
 }
+
+impl<'tcx> TypeFoldable<'tcx> for traits::ObligationCauseCode<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        match *self {
+            super::MiscObligation |
+            super::SliceOrArrayElem |
+            super::TupleElem |
+            super::ItemObligation(_) |
+            super::AssignmentLhsSized |
+            super::StructInitializerSized |
+            super::VariableType(_) |
+            super::ReturnType |
+            super::RepeatVec |
+            super::ClosureCapture(..) |
+            super::FieldSized |
+            super::ConstSized |
+            super::SharedStatic |
+            super::CompareImplMethodObligation => self.clone(),
+
+            super::ProjectionWf(proj) => super::ProjectionWf(proj.fold_with(folder)),
+            super::ReferenceOutlivesReferent(ty) => {
+                super::ReferenceOutlivesReferent(ty.fold_with(folder))
+            }
+            super::ObjectCastObligation(ty) => {
+                super::ObjectCastObligation(ty.fold_with(folder))
+            }
+            super::BuiltinDerivedObligation(ref cause) => {
+                super::BuiltinDerivedObligation(cause.fold_with(folder))
+            }
+            super::ImplDerivedObligation(ref cause) => {
+                super::ImplDerivedObligation(cause.fold_with(folder))
+            }
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        match *self {
+            super::MiscObligation |
+            super::SliceOrArrayElem |
+            super::TupleElem |
+            super::ItemObligation(_) |
+            super::AssignmentLhsSized |
+            super::StructInitializerSized |
+            super::VariableType(_) |
+            super::ReturnType |
+            super::RepeatVec |
+            super::ClosureCapture(..) |
+            super::FieldSized |
+            super::ConstSized |
+            super::SharedStatic |
+            super::CompareImplMethodObligation => false,
+
+            super::ProjectionWf(proj) => proj.visit_with(visitor),
+            super::ReferenceOutlivesReferent(ty) => ty.visit_with(visitor),
+            super::ObjectCastObligation(ty) => ty.visit_with(visitor),
+            super::BuiltinDerivedObligation(ref cause) => cause.visit_with(visitor),
+            super::ImplDerivedObligation(ref cause) => cause.visit_with(visitor)
+        }
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for traits::DerivedObligationCause<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        traits::DerivedObligationCause {
+            parent_trait_ref: self.parent_trait_ref.fold_with(folder),
+            parent_code: self.parent_code.fold_with(folder)
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        self.parent_trait_ref.visit_with(visitor) || self.parent_code.visit_with(visitor)
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for traits::ObligationCause<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        traits::ObligationCause {
+            span: self.span,
+            body_id: self.body_id,
+            code: self.code.fold_with(folder),
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        self.code.visit_with(visitor)
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for traits::DeferredObligation<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        traits::DeferredObligation {
+            predicate: self.predicate.fold_with(folder),
+            cause: self.cause.fold_with(folder)
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        self.predicate.visit_with(visitor) || self.cause.visit_with(visitor)
+    }
+}
diff --git a/src/librustc/ty/contents.rs b/src/librustc/ty/contents.rs
index 14b0a807098..8da7568c558 100644
--- a/src/librustc/ty/contents.rs
+++ b/src/librustc/ty/contents.rs
@@ -240,7 +240,8 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
                 }
 
                 ty::TyProjection(..) |
-                ty::TyParam(_) => {
+                ty::TyParam(_) |
+                ty::TyAnon(..) => {
                     TC::All
                 }
 
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index a816d26edad..13401e91265 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -1016,7 +1016,7 @@ impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
         sty_debug_print!(
             self,
             TyEnum, TyBox, TyArray, TySlice, TyRawPtr, TyRef, TyFnDef, TyFnPtr,
-            TyTrait, TyStruct, TyClosure, TyTuple, TyParam, TyInfer, TyProjection);
+            TyTrait, TyStruct, TyClosure, TyTuple, TyParam, TyInfer, TyProjection, TyAnon);
 
         println!("Substs interner: #{}", self.interners.substs.borrow().len());
         println!("BareFnTy interner: #{}", self.interners.bare_fn.borrow().len());
@@ -1355,6 +1355,10 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         self.mk_param(def.space, def.index, def.name)
     }
 
+    pub fn mk_anon(self, def_id: DefId, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
+        self.mk_ty(TyAnon(def_id, substs))
+    }
+
     pub fn trait_items(self, trait_did: DefId) -> Rc<Vec<ty::ImplOrTraitItem<'gcx>>> {
         self.trait_items_cache.memoize(trait_did, || {
             let def_ids = self.trait_item_def_ids(trait_did);
diff --git a/src/librustc/ty/error.rs b/src/librustc/ty/error.rs
index bddc2dbdb7e..66165ec6ff7 100644
--- a/src/librustc/ty/error.rs
+++ b/src/librustc/ty/error.rs
@@ -247,6 +247,7 @@ impl<'a, 'gcx, 'lcx, 'tcx> ty::TyS<'tcx> {
                     "type parameter".to_string()
                 }
             }
+            ty::TyAnon(..) => "anonymized type".to_string(),
             ty::TyError => "type error".to_string(),
         }
     }
diff --git a/src/librustc/ty/fast_reject.rs b/src/librustc/ty/fast_reject.rs
index 25f3552b565..e6f2ba8b650 100644
--- a/src/librustc/ty/fast_reject.rs
+++ b/src/librustc/ty/fast_reject.rs
@@ -30,6 +30,7 @@ pub enum SimplifiedType {
     TraitSimplifiedType(DefId),
     StructSimplifiedType(DefId),
     ClosureSimplifiedType(DefId),
+    AnonSimplifiedType(DefId),
     FunctionSimplifiedType(usize),
     ParameterSimplifiedType,
 }
@@ -98,6 +99,9 @@ pub fn simplify_type<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
                 None
             }
         }
+        ty::TyAnon(def_id, _) => {
+            Some(AnonSimplifiedType(def_id))
+        }
         ty::TyInfer(_) | ty::TyError => None,
     }
 }
diff --git a/src/librustc/ty/flags.rs b/src/librustc/ty/flags.rs
index 44b450784ed..85b7d66a2eb 100644
--- a/src/librustc/ty/flags.rs
+++ b/src/librustc/ty/flags.rs
@@ -110,6 +110,11 @@ impl FlagComputation {
                 self.add_projection_ty(data);
             }
 
+            &ty::TyAnon(_, substs) => {
+                self.add_flags(TypeFlags::HAS_PROJECTION);
+                self.add_substs(substs);
+            }
+
             &ty::TyTrait(box ty::TraitTy { ref principal, ref bounds }) => {
                 let mut computation = FlagComputation::new();
                 computation.add_substs(principal.0.substs);
diff --git a/src/librustc/ty/fold.rs b/src/librustc/ty/fold.rs
index b334964bf48..3580013c2a9 100644
--- a/src/librustc/ty/fold.rs
+++ b/src/librustc/ty/fold.rs
@@ -695,7 +695,7 @@ impl<'tcx> TypeVisitor<'tcx> for LateBoundRegionsCollector {
         // in the normalized form
         if self.just_constrained {
             match t.sty {
-                ty::TyProjection(..) => { return false; }
+                ty::TyProjection(..) | ty::TyAnon(..) => { return false; }
                 _ => { }
             }
         }
diff --git a/src/librustc/ty/item_path.rs b/src/librustc/ty/item_path.rs
index 74c05feb6d1..bfe6303d8a3 100644
--- a/src/librustc/ty/item_path.rs
+++ b/src/librustc/ty/item_path.rs
@@ -188,7 +188,8 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             data @ DefPathData::Initializer |
             data @ DefPathData::MacroDef(..) |
             data @ DefPathData::ClosureExpr |
-            data @ DefPathData::Binding(..) => {
+            data @ DefPathData::Binding(..) |
+            data @ DefPathData::ImplTrait => {
                 let parent_def_id = self.parent_def_id(def_id).unwrap();
                 self.push_item_path(buffer, parent_def_id);
                 buffer.push(&data.as_interned_str());
@@ -345,6 +346,7 @@ pub fn characteristic_def_id_of_type(ty: Ty) -> Option<DefId> {
         ty::TyFnPtr(_) |
         ty::TyProjection(_) |
         ty::TyParam(_) |
+        ty::TyAnon(..) |
         ty::TyInfer(_) |
         ty::TyError |
         ty::TyFloat(_) => None,
diff --git a/src/librustc/ty/layout.rs b/src/librustc/ty/layout.rs
index 27ed88e929e..d73e412f55f 100644
--- a/src/librustc/ty/layout.rs
+++ b/src/librustc/ty/layout.rs
@@ -558,8 +558,7 @@ impl<'a, 'gcx, 'tcx> Struct {
             (&Univariant { non_zero: true, .. }, &ty::TyStruct(def, substs)) => {
                 let fields = &def.struct_variant().fields;
                 assert_eq!(fields.len(), 1);
-                let ty = normalize_associated_type(infcx, fields[0].ty(tcx, substs));
-                match *ty.layout(infcx)? {
+                match *fields[0].ty(tcx, substs).layout(infcx)? {
                     // FIXME(eddyb) also allow floating-point types here.
                     Scalar { value: Int(_), non_zero: false } |
                     Scalar { value: Pointer, non_zero: false } => {
@@ -577,7 +576,7 @@ impl<'a, 'gcx, 'tcx> Struct {
             (_, &ty::TyStruct(def, substs)) => {
                 Struct::non_zero_field_path(infcx, def.struct_variant().fields
                                                       .iter().map(|field| {
-                    normalize_associated_type(infcx, field.ty(tcx, substs))
+                    field.ty(tcx, substs)
                 }))
             }
 
@@ -595,6 +594,14 @@ impl<'a, 'gcx, 'tcx> Struct {
                 Struct::non_zero_field_path(infcx, Some(ety).into_iter())
             }
 
+            (_, &ty::TyProjection(_)) | (_, &ty::TyAnon(..)) => {
+                let normalized = normalize_associated_type(infcx, ty);
+                if ty == normalized {
+                    return Ok(None);
+                }
+                return Struct::non_zero_field_in_type(infcx, normalized);
+            }
+
             // Anything else is not a non-zero type.
             _ => Ok(None)
         }
@@ -762,8 +769,9 @@ fn normalize_associated_type<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 impl<'a, 'gcx, 'tcx> Layout {
     pub fn compute_uncached(ty: Ty<'gcx>,
                             infcx: &InferCtxt<'a, 'gcx, 'tcx>)
-                            -> Result<Layout, LayoutError<'gcx>> {
+                            -> Result<&'gcx Layout, LayoutError<'gcx>> {
         let tcx = infcx.tcx.global_tcx();
+        let success = |layout| Ok(tcx.intern_layout(layout));
         let dl = &tcx.data_layout;
         assert!(!ty.has_infer_types());
 
@@ -795,6 +803,7 @@ impl<'a, 'gcx, 'tcx> Layout {
                 if pointee.is_sized(tcx, &infcx.parameter_environment, DUMMY_SP) {
                     Scalar { value: Pointer, non_zero: non_zero }
                 } else {
+                    let pointee = normalize_associated_type(infcx, pointee);
                     let unsized_part = tcx.struct_tail(pointee);
                     let meta = match unsized_part.sty {
                         ty::TySlice(_) | ty::TyStr => {
@@ -860,7 +869,7 @@ impl<'a, 'gcx, 'tcx> Layout {
                     let element = ty.simd_type(tcx);
                     match *element.layout(infcx)? {
                         Scalar { value, .. } => {
-                            return Ok(Vector {
+                            return success(Vector {
                                 element: value,
                                 count: ty.simd_size(tcx) as u64
                             });
@@ -873,8 +882,7 @@ impl<'a, 'gcx, 'tcx> Layout {
                     }
                 }
                 let fields = def.struct_variant().fields.iter().map(|field| {
-                    normalize_associated_type(infcx, field.ty(tcx, substs))
-                        .layout(infcx)
+                    field.ty(tcx, substs).layout(infcx)
                 });
                 let packed = tcx.lookup_packed(def.did);
                 let mut st = Struct::new(dl, packed);
@@ -914,7 +922,7 @@ impl<'a, 'gcx, 'tcx> Layout {
 
                     let mut st = Struct::new(dl, false);
                     st.extend(dl, drop_flag.iter().map(Ok), ty)?;
-                    return Ok(Univariant { variant: st, non_zero: false });
+                    return success(Univariant { variant: st, non_zero: false });
                 }
 
                 if !dtor && def.variants.iter().all(|v| v.fields.is_empty()) {
@@ -927,7 +935,7 @@ impl<'a, 'gcx, 'tcx> Layout {
                     }
 
                     let (discr, signed) = Integer::repr_discr(tcx, hint, min, max);
-                    return Ok(CEnum {
+                    return success(CEnum {
                         discr: discr,
                         signed: signed,
                         min: min as u64,
@@ -950,19 +958,16 @@ impl<'a, 'gcx, 'tcx> Layout {
                     // (Typechecking will reject discriminant-sizing attrs.)
                     assert_eq!(hint, attr::ReprAny);
                     let fields = def.variants[0].fields.iter().map(|field| {
-                        normalize_associated_type(infcx, field.ty(tcx, substs))
-                            .layout(infcx)
+                        field.ty(tcx, substs).layout(infcx)
                     });
                     let mut st = Struct::new(dl, false);
                     st.extend(dl, fields.chain(drop_flag.iter().map(Ok)), ty)?;
-                    return Ok(Univariant { variant: st, non_zero: false });
+                    return success(Univariant { variant: st, non_zero: false });
                 }
 
                 // Cache the substituted and normalized variant field types.
                 let variants = def.variants.iter().map(|v| {
-                    v.fields.iter().map(|field| {
-                        normalize_associated_type(infcx, field.ty(tcx, substs))
-                    }).collect::<Vec<_>>()
+                    v.fields.iter().map(|field| field.ty(tcx, substs)).collect::<Vec<_>>()
                 }).collect::<Vec<_>>();
 
                 if !dtor && variants.len() == 2 && hint == attr::ReprAny {
@@ -982,7 +987,7 @@ impl<'a, 'gcx, 'tcx> Layout {
                         if path == &[0] && variants[discr].len() == 1 {
                             match *variants[discr][0].layout(infcx)? {
                                 Scalar { value, .. } => {
-                                    return Ok(RawNullablePointer {
+                                    return success(RawNullablePointer {
                                         nndiscr: discr as u64,
                                         value: value
                                     });
@@ -998,10 +1003,8 @@ impl<'a, 'gcx, 'tcx> Layout {
                         path.push(0); // For GEP through a pointer.
                         path.reverse();
                         let mut st = Struct::new(dl, false);
-                        st.extend(dl, variants[discr].iter().map(|ty| {
-                            ty.layout(infcx)
-                        }), ty)?;
-                        return Ok(StructWrappedNullablePointer {
+                        st.extend(dl, variants[discr].iter().map(|ty| ty.layout(infcx)), ty)?;
+                        return success(StructWrappedNullablePointer {
                             nndiscr: discr as u64,
                             nonnull: st,
                             discrfield: path
@@ -1105,7 +1108,14 @@ impl<'a, 'gcx, 'tcx> Layout {
             }
 
             // Types with no meaningful known layout.
-            ty::TyProjection(_) | ty::TyParam(_) => {
+            ty::TyProjection(_) | ty::TyAnon(..) => {
+                let normalized = normalize_associated_type(infcx, ty);
+                if ty == normalized {
+                    return Err(LayoutError::Unknown(ty));
+                }
+                return normalized.layout(infcx);
+            }
+            ty::TyParam(_) => {
                 return Err(LayoutError::Unknown(ty));
             }
             ty::TyInfer(_) | ty::TyError => {
@@ -1113,7 +1123,7 @@ impl<'a, 'gcx, 'tcx> Layout {
             }
         };
 
-        Ok(layout)
+        success(layout)
     }
 
     /// Returns true if the layout corresponds to an unsized type.
@@ -1272,8 +1282,7 @@ impl<'a, 'gcx, 'tcx> SizeSkeleton<'gcx> {
                 // Get a zero-sized variant or a pointer newtype.
                 let zero_or_ptr_variant = |i: usize| {
                     let fields = def.variants[i].fields.iter().map(|field| {
-                        let ty = normalize_associated_type(infcx, &field.ty(tcx, substs));
-                        SizeSkeleton::compute(ty, infcx)
+                        SizeSkeleton::compute(field.ty(tcx, substs), infcx)
                     });
                     let mut ptr = None;
                     for field in fields {
@@ -1323,6 +1332,15 @@ impl<'a, 'gcx, 'tcx> SizeSkeleton<'gcx> {
                 }
             }
 
+            ty::TyProjection(_) | ty::TyAnon(..) => {
+                let normalized = normalize_associated_type(infcx, ty);
+                if ty == normalized {
+                    Err(err)
+                } else {
+                    SizeSkeleton::compute(normalized, infcx)
+                }
+            }
+
             _ => Err(err)
         }
     }
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index a7c53419892..8e89b3c6087 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -1404,9 +1404,13 @@ impl<'a, 'tcx> ParameterEnvironment<'tcx> {
                     }
                 }
             }
-            Some(ast_map::NodeExpr(..)) => {
+            Some(ast_map::NodeExpr(expr)) => {
                 // This is a convenience to allow closures to work.
-                ParameterEnvironment::for_item(tcx, tcx.map.get_parent(id))
+                if let hir::ExprClosure(..) = expr.node {
+                    ParameterEnvironment::for_item(tcx, tcx.map.get_parent(id))
+                } else {
+                    tcx.empty_parameter_environment()
+                }
             }
             Some(ast_map::NodeForeignItem(item)) => {
                 let def_id = tcx.map.local_def_id(id);
@@ -1885,7 +1889,7 @@ impl<'a, 'tcx> AdtDefData<'tcx, 'tcx> {
                 }
             }
 
-            TyProjection(..) => {
+            TyProjection(..) | TyAnon(..) => {
                 // must calculate explicitly.
                 // FIXME: consider special-casing always-Sized projections
                 vec![ty]
diff --git a/src/librustc/ty/outlives.rs b/src/librustc/ty/outlives.rs
index 9ae3325c258..df907c26f71 100644
--- a/src/librustc/ty/outlives.rs
+++ b/src/librustc/ty/outlives.rs
@@ -174,6 +174,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
             ty::TyEnum(..) |        // OutlivesNominalType
             ty::TyStruct(..) |      // OutlivesNominalType
             ty::TyBox(..) |         // OutlivesNominalType (ish)
+            ty::TyAnon(..) |        // OutlivesNominalType (ish)
             ty::TyStr |             // OutlivesScalar (ish)
             ty::TyArray(..) |       // ...
             ty::TySlice(..) |       // ...
diff --git a/src/librustc/ty/relate.rs b/src/librustc/ty/relate.rs
index 80c727f0221..f9263947c03 100644
--- a/src/librustc/ty/relate.rs
+++ b/src/librustc/ty/relate.rs
@@ -582,6 +582,13 @@ pub fn super_relate_tys<'a, 'gcx, 'tcx, R>(relation: &mut R,
             Ok(tcx.mk_projection(projection_ty.trait_ref, projection_ty.item_name))
         }
 
+        (&ty::TyAnon(a_def_id, a_substs), &ty::TyAnon(b_def_id, b_substs))
+            if a_def_id == b_def_id =>
+        {
+            let substs = relate_substs(relation, None, a_substs, b_substs)?;
+            Ok(tcx.mk_anon(a_def_id, substs))
+        }
+
         _ =>
         {
             Err(TypeError::Sorts(expected_found(relation, &a, &b)))
diff --git a/src/librustc/ty/structural_impls.rs b/src/librustc/ty/structural_impls.rs
index 16a54c20925..8c10806fda7 100644
--- a/src/librustc/ty/structural_impls.rs
+++ b/src/librustc/ty/structural_impls.rs
@@ -115,16 +115,26 @@ impl<'tcx, A: Copy+Lift<'tcx>, B: Copy+Lift<'tcx>> Lift<'tcx> for ty::OutlivesPr
     }
 }
 
+impl<'a, 'tcx> Lift<'tcx> for ty::ProjectionTy<'a> {
+    type Lifted = ty::ProjectionTy<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
+                             -> Option<ty::ProjectionTy<'tcx>> {
+        tcx.lift(&self.trait_ref).map(|trait_ref| {
+            ty::ProjectionTy {
+                trait_ref: trait_ref,
+                item_name: self.item_name
+            }
+        })
+    }
+}
+
 impl<'a, 'tcx> Lift<'tcx> for ty::ProjectionPredicate<'a> {
     type Lifted = ty::ProjectionPredicate<'tcx>;
     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
                              -> Option<ty::ProjectionPredicate<'tcx>> {
-        tcx.lift(&(self.projection_ty.trait_ref, self.ty)).map(|(trait_ref, ty)| {
+        tcx.lift(&(self.projection_ty, self.ty)).map(|(projection_ty, ty)| {
             ty::ProjectionPredicate {
-                projection_ty: ty::ProjectionTy {
-                    trait_ref: trait_ref,
-                    item_name: self.projection_ty.item_name
-                },
+                projection_ty: projection_ty,
                 ty: ty
             }
         })
@@ -485,6 +495,7 @@ impl<'tcx> TypeFoldable<'tcx> for Ty<'tcx> {
             ty::TyStruct(did, substs) => ty::TyStruct(did, substs.fold_with(folder)),
             ty::TyClosure(did, substs) => ty::TyClosure(did, substs.fold_with(folder)),
             ty::TyProjection(ref data) => ty::TyProjection(data.fold_with(folder)),
+            ty::TyAnon(did, substs) => ty::TyAnon(did, substs.fold_with(folder)),
             ty::TyBool | ty::TyChar | ty::TyStr | ty::TyInt(_) |
             ty::TyUint(_) | ty::TyFloat(_) | ty::TyError | ty::TyInfer(_) |
             ty::TyParam(..) => self.sty.clone(),
@@ -513,6 +524,7 @@ impl<'tcx> TypeFoldable<'tcx> for Ty<'tcx> {
             ty::TyStruct(_did, ref substs) => substs.visit_with(visitor),
             ty::TyClosure(_did, ref substs) => substs.visit_with(visitor),
             ty::TyProjection(ref data) => data.visit_with(visitor),
+            ty::TyAnon(_, ref substs) => substs.visit_with(visitor),
             ty::TyBool | ty::TyChar | ty::TyStr | ty::TyInt(_) |
             ty::TyUint(_) | ty::TyFloat(_) | ty::TyError | ty::TyInfer(_) |
             ty::TyParam(..) => false,
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 7c69618068a..912cb39face 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -166,6 +166,12 @@ pub enum TypeVariants<'tcx> {
     /// `<T as Trait<..>>::N`.
     TyProjection(ProjectionTy<'tcx>),
 
+    /// Anonymized (`impl Trait`) type found in a return type.
+    /// The DefId comes from the `impl Trait` ast::Ty node, and the
+    /// substitutions are for the generics of the function in question.
+    /// After typeck, the concrete type can be found in the `tcache` map.
+    TyAnon(DefId, &'tcx Substs<'tcx>),
+
     /// A type parameter; for example, `T` in `fn f<T>(x: T) {}
     TyParam(ParamTy),
 
@@ -1232,7 +1238,8 @@ impl<'a, 'gcx, 'tcx> TyS<'tcx> {
                 v
             }
             TyEnum(_, substs) |
-            TyStruct(_, substs) => {
+            TyStruct(_, substs) |
+            TyAnon(_, substs) => {
                 substs.regions.as_slice().to_vec()
             }
             TyClosure(_, ref substs) => {
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index d9ffe36ea47..e7bcfbfd823 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -14,7 +14,7 @@ use hir::def_id::DefId;
 use ty::subst;
 use infer::InferCtxt;
 use hir::pat_util;
-use traits::{self, ProjectionMode};
+use traits::{self, Reveal};
 use ty::{self, Ty, TyCtxt, TypeAndMut, TypeFlags, TypeFoldable};
 use ty::{Disr, ParameterEnvironment};
 use ty::fold::TypeVisitor;
@@ -137,8 +137,7 @@ impl<'tcx> ParameterEnvironment<'tcx> {
                                        self_type: Ty<'tcx>, span: Span)
                                        -> Result<(),CopyImplementationError> {
         // FIXME: (@jroesch) float this code up
-        tcx.infer_ctxt(None, Some(self.clone()),
-                       ProjectionMode::Topmost).enter(|infcx| {
+        tcx.infer_ctxt(None, Some(self.clone()), Reveal::ExactMatch).enter(|infcx| {
             let adt = match self_type.sty {
                 ty::TyStruct(struct_def, substs) => {
                     for field in struct_def.all_fields() {
@@ -438,6 +437,7 @@ impl<'a, 'gcx, 'tcx> TypeVisitor<'tcx> for TypeIdHasher<'a, 'gcx, 'tcx> {
             TyRawPtr(m) |
             TyRef(_, m) => self.hash(m.mutbl),
             TyClosure(def_id, _) |
+            TyAnon(def_id, _) |
             TyFnDef(def_id, _, _) => self.def_id(def_id),
             TyFnPtr(f) => {
                 self.hash(f.unsafety);
@@ -533,7 +533,7 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
                    param_env: &ParameterEnvironment<'tcx>,
                    bound: ty::BuiltinBound, span: Span) -> bool
     {
-        tcx.infer_ctxt(None, Some(param_env.clone()), ProjectionMode::Topmost).enter(|infcx| {
+        tcx.infer_ctxt(None, Some(param_env.clone()), Reveal::ExactMatch).enter(|infcx| {
             traits::type_known_to_meet_builtin_bound(&infcx, self, bound, span)
         })
     }
@@ -560,7 +560,7 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
             }) => Some(true),
 
             TyArray(..) | TySlice(_) | TyTrait(..) | TyTuple(..) |
-            TyClosure(..) | TyEnum(..) | TyStruct(..) |
+            TyClosure(..) | TyEnum(..) | TyStruct(..) | TyAnon(..) |
             TyProjection(..) | TyParam(..) | TyInfer(..) | TyError => None
         }.unwrap_or_else(|| !self.impls_bound(tcx, param_env, ty::BoundCopy, span));
 
@@ -601,7 +601,7 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
             TyStr | TyTrait(..) | TySlice(_) => Some(false),
 
             TyEnum(..) | TyStruct(..) | TyProjection(..) | TyParam(..) |
-            TyInfer(..) | TyError => None
+            TyInfer(..) | TyAnon(..) | TyError => None
         }.unwrap_or_else(|| self.impls_bound(tcx, param_env, ty::BoundSized, span));
 
         if !self.has_param_types() && !self.has_self_ty() {
@@ -627,7 +627,6 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
         }
 
         let layout = Layout::compute_uncached(self, infcx)?;
-        let layout = tcx.intern_layout(layout);
         if can_cache {
             tcx.layout_cache.borrow_mut().insert(self, layout);
         }
diff --git a/src/librustc/ty/walk.rs b/src/librustc/ty/walk.rs
index fa7c9b78231..ebc2642678b 100644
--- a/src/librustc/ty/walk.rs
+++ b/src/librustc/ty/walk.rs
@@ -88,7 +88,8 @@ fn push_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, parent_ty: Ty<'tcx>) {
             }).collect::<Vec<_>>());
         }
         ty::TyEnum(_, ref substs) |
-        ty::TyStruct(_, ref substs) => {
+        ty::TyStruct(_, ref substs) |
+        ty::TyAnon(_, ref substs) => {
             push_reversed(stack, substs.types.as_slice());
         }
         ty::TyClosure(_, ref substs) => {
diff --git a/src/librustc/ty/wf.rs b/src/librustc/ty/wf.rs
index 37ba936d2f4..f6ddfe60d40 100644
--- a/src/librustc/ty/wf.rs
+++ b/src/librustc/ty/wf.rs
@@ -383,6 +383,12 @@ impl<'a, 'gcx, 'tcx> WfPredicates<'a, 'gcx, 'tcx> {
                     // types appearing in the fn signature
                 }
 
+                ty::TyAnon(..) => {
+                    // all of the requirements on type parameters
+                    // should've been checked by the instantiation
+                    // of whatever returned this exact `impl Trait`.
+                }
+
                 ty::TyTrait(ref data) => {
                     // WfObject
                     //
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 60977a80946..a17c0106813 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -907,6 +907,37 @@ impl<'tcx> fmt::Display for ty::TypeVariants<'tcx> {
             }
             TyTrait(ref data) => write!(f, "{}", data),
             ty::TyProjection(ref data) => write!(f, "{}", data),
+            ty::TyAnon(def_id, substs) => {
+                ty::tls::with(|tcx| {
+                    // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
+                    // by looking up the projections associated with the def_id.
+                    let item_predicates = tcx.lookup_predicates(def_id);
+                    let substs = tcx.lift(&substs).unwrap_or_else(|| {
+                        tcx.mk_substs(subst::Substs::empty())
+                    });
+                    let bounds = item_predicates.instantiate(tcx, substs);
+
+                    let mut first = true;
+                    let mut is_sized = false;
+                    write!(f, "impl")?;
+                    for predicate in bounds.predicates.into_vec() {
+                        if let Some(trait_ref) = predicate.to_opt_poly_trait_ref() {
+                            // Don't print +Sized, but rather +?Sized if absent.
+                            if Some(trait_ref.def_id()) == tcx.lang_items.sized_trait() {
+                                is_sized = true;
+                                continue;
+                            }
+
+                            write!(f, "{}{}", if first { " " } else { "+" }, trait_ref)?;
+                            first = false;
+                        }
+                    }
+                    if !is_sized {
+                        write!(f, "{}?Sized", if first { " " } else { "+" })?;
+                    }
+                    Ok(())
+                })
+            }
             TyStr => write!(f, "str"),
             TyClosure(did, substs) => ty::tls::with(|tcx| {
                 write!(f, "[closure")?;
diff --git a/src/librustc_const_eval/check_match.rs b/src/librustc_const_eval/check_match.rs
index 5fe4830c365..3e88dec8cb2 100644
--- a/src/librustc_const_eval/check_match.rs
+++ b/src/librustc_const_eval/check_match.rs
@@ -25,7 +25,7 @@ use rustc::middle::expr_use_visitor::{LoanCause, MutateMode};
 use rustc::middle::expr_use_visitor as euv;
 use rustc::middle::mem_categorization::{cmt};
 use rustc::hir::pat_util::*;
-use rustc::traits::ProjectionMode;
+use rustc::traits::Reveal;
 use rustc::ty::*;
 use rustc::ty;
 use std::cmp::Ordering;
@@ -1133,7 +1133,7 @@ fn check_legality_of_move_bindings(cx: &MatchCheckCtxt,
                 let pat_ty = cx.tcx.node_id_to_type(p.id);
                 //FIXME: (@jroesch) this code should be floated up as well
                 cx.tcx.infer_ctxt(None, Some(cx.param_env.clone()),
-                                  ProjectionMode::AnyFinal).enter(|infcx| {
+                                  Reveal::NotSpecializable).enter(|infcx| {
                     if infcx.type_moves_by_default(pat_ty, pat.span) {
                         check_move(p, sub.as_ref().map(|p| &**p));
                     }
@@ -1149,7 +1149,7 @@ fn check_legality_of_move_bindings(cx: &MatchCheckCtxt,
 fn check_for_mutation_in_guard<'a, 'tcx>(cx: &'a MatchCheckCtxt<'a, 'tcx>,
                                          guard: &hir::Expr) {
     cx.tcx.infer_ctxt(None, Some(cx.param_env.clone()),
-                      ProjectionMode::AnyFinal).enter(|infcx| {
+                      Reveal::NotSpecializable).enter(|infcx| {
         let mut checker = MutationChecker {
             cx: cx,
         };
diff --git a/src/librustc_const_eval/eval.rs b/src/librustc_const_eval/eval.rs
index 9c9453ae3d3..73b54c4374f 100644
--- a/src/librustc_const_eval/eval.rs
+++ b/src/librustc_const_eval/eval.rs
@@ -24,7 +24,7 @@ use rustc::hir::def_id::DefId;
 use rustc::hir::pat_util::def_to_path;
 use rustc::ty::{self, Ty, TyCtxt, subst};
 use rustc::ty::util::IntTypeExt;
-use rustc::traits::ProjectionMode;
+use rustc::traits::Reveal;
 use rustc::util::common::ErrorReported;
 use rustc::util::nodemap::NodeMap;
 use rustc::lint;
@@ -1055,7 +1055,7 @@ fn resolve_trait_associated_const<'a, 'tcx: 'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
            trait_ref);
 
     tcx.populate_implementations_for_trait_if_necessary(trait_ref.def_id());
-    tcx.infer_ctxt(None, None, ProjectionMode::AnyFinal).enter(|infcx| {
+    tcx.infer_ctxt(None, None, Reveal::NotSpecializable).enter(|infcx| {
         let mut selcx = traits::SelectionContext::new(&infcx);
         let obligation = traits::Obligation::new(traits::ObligationCause::dummy(),
                                                  trait_ref.to_poly_trait_predicate());
@@ -1073,9 +1073,9 @@ fn resolve_trait_associated_const<'a, 'tcx: 'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         };
 
         // NOTE: this code does not currently account for specialization, but when
-        // it does so, it should hook into the ProjectionMode to determine when the
+        // it does so, it should hook into the Reveal to determine when the
         // constant should resolve; this will also require plumbing through to this
-        // function whether we are in "trans mode" to pick the right ProjectionMode
+        // function whether we are in "trans mode" to pick the right Reveal
         // when constructing the inference context above.
         match selection {
             traits::VtableImpl(ref impl_data) => {
diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index 2b0bd14d83f..30fe38a0603 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -22,7 +22,7 @@ use rustc::middle::resolve_lifetime;
 use rustc::middle::stability;
 use rustc::ty::subst;
 use rustc::ty::subst::Subst;
-use rustc::traits::ProjectionMode;
+use rustc::traits::Reveal;
 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
 use rustc::infer::{self, InferOk, InferResult, TypeOrigin};
 use rustc_metadata::cstore::CStore;
@@ -141,7 +141,7 @@ fn test_env<F>(source_string: &str,
                              index,
                              "test_crate",
                              |tcx| {
-        tcx.infer_ctxt(None, None, ProjectionMode::AnyFinal).enter(|infcx| {
+        tcx.infer_ctxt(None, None, Reveal::NotSpecializable).enter(|infcx| {
 
             body(Env { infcx: &infcx });
             let free_regions = FreeRegionMap::new();
diff --git a/src/librustc_lint/builtin.rs b/src/librustc_lint/builtin.rs
index 49dad2d0f6d..d8ec79fb060 100644
--- a/src/librustc_lint/builtin.rs
+++ b/src/librustc_lint/builtin.rs
@@ -35,7 +35,7 @@ use rustc::cfg;
 use rustc::ty::subst::Substs;
 use rustc::ty::{self, Ty, TyCtxt};
 use rustc::ty::adjustment;
-use rustc::traits::{self, ProjectionMode};
+use rustc::traits::{self, Reveal};
 use rustc::hir::map as hir_map;
 use util::nodemap::{NodeSet};
 use lint::{Level, LateContext, LintContext, LintArray, Lint};
@@ -911,7 +911,7 @@ impl LateLintPass for UnconditionalRecursion {
                     let node_id = tcx.map.as_local_node_id(method.def_id).unwrap();
 
                     let param_env = Some(ty::ParameterEnvironment::for_item(tcx, node_id));
-                    tcx.infer_ctxt(None, param_env, ProjectionMode::AnyFinal).enter(|infcx| {
+                    tcx.infer_ctxt(None, param_env, Reveal::NotSpecializable).enter(|infcx| {
                         let mut selcx = traits::SelectionContext::new(&infcx);
                         match selcx.select(&obligation) {
                             // The method comes from a `T: Trait` bound.
diff --git a/src/librustc_lint/types.rs b/src/librustc_lint/types.rs
index f688bd80ee9..b9861c309db 100644
--- a/src/librustc_lint/types.rs
+++ b/src/librustc_lint/types.rs
@@ -14,7 +14,7 @@ use rustc::hir::def_id::DefId;
 use rustc::ty::subst::Substs;
 use rustc::ty::{self, Ty, TyCtxt};
 use rustc::ty::layout::{Layout, Primitive};
-use rustc::traits::ProjectionMode;
+use rustc::traits::Reveal;
 use middle::const_val::ConstVal;
 use rustc_const_eval::eval_const_expr_partial;
 use rustc_const_eval::EvalHint::ExprTypeChecked;
@@ -596,7 +596,7 @@ impl<'a, 'tcx> ImproperCTypesVisitor<'a, 'tcx> {
             }
 
             ty::TyParam(..) | ty::TyInfer(..) | ty::TyError |
-            ty::TyClosure(..) | ty::TyProjection(..) |
+            ty::TyClosure(..) | ty::TyProjection(..) | ty::TyAnon(..) |
             ty::TyFnDef(..) => {
                 bug!("Unexpected type in foreign function")
             }
@@ -697,7 +697,7 @@ impl LateLintPass for VariantSizeDifferences {
         if let hir::ItemEnum(ref enum_definition, ref gens) = it.node {
             if gens.ty_params.is_empty() {  // sizes only make sense for non-generic types
                 let t = cx.tcx.node_id_to_type(it.id);
-                let layout = cx.tcx.normalizing_infer_ctxt(ProjectionMode::Any).enter(|infcx| {
+                let layout = cx.tcx.normalizing_infer_ctxt(Reveal::All).enter(|infcx| {
                     let ty = cx.tcx.erase_regions(&t);
                     ty.layout(&infcx).unwrap_or_else(|e| {
                         bug!("failed to get layout for `{}`: {}", t, e)
diff --git a/src/librustc_metadata/def_key.rs b/src/librustc_metadata/def_key.rs
index 2444d669f7f..285ca2e4d4d 100644
--- a/src/librustc_metadata/def_key.rs
+++ b/src/librustc_metadata/def_key.rs
@@ -41,6 +41,7 @@ pub enum DefPathData {
     StructCtor,
     Initializer,
     Binding,
+    ImplTrait,
 }
 
 pub fn simplify_def_key(key: hir_map::DefKey) -> DefKey {
@@ -72,6 +73,7 @@ fn simplify_def_path_data(data: hir_map::DefPathData) -> DefPathData {
         hir_map::DefPathData::StructCtor => DefPathData::StructCtor,
         hir_map::DefPathData::Initializer => DefPathData::Initializer,
         hir_map::DefPathData::Binding(_) => DefPathData::Binding,
+        hir_map::DefPathData::ImplTrait => DefPathData::ImplTrait,
     }
 }
 
@@ -103,5 +105,6 @@ fn recover_def_path_data(data: DefPathData, name: Option<InternedString>) -> hir
         DefPathData::StructCtor => hir_map::DefPathData::StructCtor,
         DefPathData::Initializer => hir_map::DefPathData::Initializer,
         DefPathData::Binding => hir_map::DefPathData::Binding(name.unwrap()),
+        DefPathData::ImplTrait => hir_map::DefPathData::ImplTrait,
     }
 }
diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs
index 4e754abe2ae..cc1d07b33c7 100644
--- a/src/librustc_metadata/encoder.rs
+++ b/src/librustc_metadata/encoder.rs
@@ -1390,6 +1390,20 @@ impl<'a, 'b, 'c, 'tcx> Visitor<'tcx> for EncodeVisitor<'a, 'b, 'c, 'tcx> {
         intravisit::walk_foreign_item(self, ni);
         encode_info_for_foreign_item(self.ecx, self.rbml_w_for_visit_item, ni, self.index);
     }
+    fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
+        intravisit::walk_ty(self, ty);
+
+        if let hir::TyImplTrait(_) = ty.node {
+            let rbml_w = &mut *self.rbml_w_for_visit_item;
+            let def_id = self.ecx.tcx.map.local_def_id(ty.id);
+            let _task = self.index.record(def_id, rbml_w);
+            rbml_w.start_tag(tag_items_data_item);
+            encode_def_id_and_key(self.ecx, rbml_w, def_id);
+            encode_family(rbml_w, 'y');
+            encode_bounds_and_type_for_item(rbml_w, self.ecx, self.index, ty.id);
+            rbml_w.end_tag();
+        }
+    }
 }
 
 fn encode_info_for_items<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
diff --git a/src/librustc_metadata/tydecode.rs b/src/librustc_metadata/tydecode.rs
index 119640af463..1dcec35adb2 100644
--- a/src/librustc_metadata/tydecode.rs
+++ b/src/librustc_metadata/tydecode.rs
@@ -445,6 +445,13 @@ impl<'a,'tcx> TyDecoder<'a,'tcx> {
                 let name = token::intern(&self.parse_str(']'));
                 return tcx.mk_projection(trait_ref, name);
             }
+            'A' => {
+                assert_eq!(self.next(), '[');
+                let def_id = self.parse_def();
+                let substs = self.parse_substs();
+                assert_eq!(self.next(), ']');
+                return self.tcx.mk_anon(def_id, self.tcx.mk_substs(substs));
+            }
             'e' => {
                 return tcx.types.err;
             }
diff --git a/src/librustc_metadata/tyencode.rs b/src/librustc_metadata/tyencode.rs
index 3484a8b75dd..c2e91eba0d2 100644
--- a/src/librustc_metadata/tyencode.rs
+++ b/src/librustc_metadata/tyencode.rs
@@ -170,6 +170,11 @@ pub fn enc_ty<'a, 'tcx>(w: &mut Cursor<Vec<u8>>, cx: &ctxt<'a, 'tcx>, t: Ty<'tcx
             enc_trait_ref(w, cx, data.trait_ref);
             write!(w, "{}]", data.item_name);
         }
+        ty::TyAnon(def_id, substs) => {
+            write!(w, "A[{}|", (cx.ds)(cx.tcx, def_id));
+            enc_substs(w, cx, substs);
+            write!(w, "]");
+        }
         ty::TyError => {
             write!(w, "e");
         }
diff --git a/src/librustc_mir/mir_map.rs b/src/librustc_mir/mir_map.rs
index 42a643b8af6..5e92a057da3 100644
--- a/src/librustc_mir/mir_map.rs
+++ b/src/librustc_mir/mir_map.rs
@@ -27,7 +27,7 @@ use hair::cx::Cx;
 
 use rustc::mir::mir_map::MirMap;
 use rustc::infer::InferCtxtBuilder;
-use rustc::traits::ProjectionMode;
+use rustc::traits::Reveal;
 use rustc::ty::{self, Ty, TyCtxt};
 use rustc::ty::subst::Substs;
 use rustc::hir;
@@ -103,7 +103,7 @@ impl<'a, 'gcx, 'tcx> BuildMir<'a, 'gcx> {
         let def_id = self.tcx.map.local_def_id(src.item_id());
         CxBuilder {
             src: src,
-            infcx: self.tcx.infer_ctxt(None, Some(param_env), ProjectionMode::AnyFinal),
+            infcx: self.tcx.infer_ctxt(None, Some(param_env), Reveal::NotSpecializable),
             def_id: def_id,
             map: self.map
         }
diff --git a/src/librustc_mir/transform/qualify_consts.rs b/src/librustc_mir/transform/qualify_consts.rs
index c061f2d5620..7ebc72bcc5f 100644
--- a/src/librustc_mir/transform/qualify_consts.rs
+++ b/src/librustc_mir/transform/qualify_consts.rs
@@ -21,7 +21,7 @@ use rustc::hir;
 use rustc::hir::def_id::DefId;
 use rustc::hir::intravisit::FnKind;
 use rustc::hir::map::blocks::FnLikeNode;
-use rustc::traits::{self, ProjectionMode};
+use rustc::traits::{self, Reveal};
 use rustc::ty::{self, TyCtxt, Ty};
 use rustc::ty::cast::CastTy;
 use rustc::mir::repr::*;
@@ -992,7 +992,7 @@ impl<'tcx> MirMapPass<'tcx> for QualifyAndPromoteConstants {
             // Statics must be Sync.
             if mode == Mode::Static {
                 let ty = mir.return_ty.unwrap();
-                tcx.infer_ctxt(None, None, ProjectionMode::AnyFinal).enter(|infcx| {
+                tcx.infer_ctxt(None, None, Reveal::NotSpecializable).enter(|infcx| {
                     let cause = traits::ObligationCause::new(mir.span, id, traits::SharedStatic);
                     let mut fulfillment_cx = traits::FulfillmentContext::new();
                     fulfillment_cx.register_builtin_bound(&infcx, ty, ty::BoundSync, cause);
diff --git a/src/librustc_mir/transform/type_check.rs b/src/librustc_mir/transform/type_check.rs
index c8556d5e0d8..52f41741b08 100644
--- a/src/librustc_mir/transform/type_check.rs
+++ b/src/librustc_mir/transform/type_check.rs
@@ -12,7 +12,7 @@
 #![allow(unreachable_code)]
 
 use rustc::infer::{self, InferCtxt, InferOk};
-use rustc::traits::{self, ProjectionMode};
+use rustc::traits::{self, Reveal};
 use rustc::ty::fold::TypeFoldable;
 use rustc::ty::{self, Ty, TyCtxt};
 use rustc::mir::repr::*;
@@ -695,7 +695,7 @@ impl<'tcx> MirPass<'tcx> for TypeckMir {
             return;
         }
         let param_env = ty::ParameterEnvironment::for_item(tcx, src.item_id());
-        tcx.infer_ctxt(None, Some(param_env), ProjectionMode::AnyFinal).enter(|infcx| {
+        tcx.infer_ctxt(None, Some(param_env), Reveal::NotSpecializable).enter(|infcx| {
             let mut checker = TypeChecker::new(&infcx);
             {
                 let mut verifier = TypeVerifier::new(&mut checker, mir);
diff --git a/src/librustc_passes/consts.rs b/src/librustc_passes/consts.rs
index fc55118c9f4..37e42cdea1b 100644
--- a/src/librustc_passes/consts.rs
+++ b/src/librustc_passes/consts.rs
@@ -39,7 +39,7 @@ use rustc::middle::expr_use_visitor as euv;
 use rustc::middle::mem_categorization as mc;
 use rustc::middle::mem_categorization::Categorization;
 use rustc::ty::{self, Ty, TyCtxt};
-use rustc::traits::ProjectionMode;
+use rustc::traits::Reveal;
 use rustc::util::common::ErrorReported;
 use rustc::util::nodemap::NodeMap;
 use rustc::middle::const_qualif::ConstQualif;
@@ -96,7 +96,7 @@ impl<'a, 'gcx> CheckCrateVisitor<'a, 'gcx> {
         };
 
         self.tcx
-            .infer_ctxt(None, Some(param_env), ProjectionMode::AnyFinal)
+            .infer_ctxt(None, Some(param_env), Reveal::NotSpecializable)
             .enter(|infcx| f(&mut euv::ExprUseVisitor::new(self, &infcx)))
     }
 
diff --git a/src/librustc_passes/rvalues.rs b/src/librustc_passes/rvalues.rs
index 2a5dc50cae9..782ee34edd4 100644
--- a/src/librustc_passes/rvalues.rs
+++ b/src/librustc_passes/rvalues.rs
@@ -15,7 +15,7 @@ use rustc::dep_graph::DepNode;
 use rustc::middle::expr_use_visitor as euv;
 use rustc::middle::mem_categorization as mc;
 use rustc::ty::{self, TyCtxt, ParameterEnvironment};
-use rustc::traits::ProjectionMode;
+use rustc::traits::Reveal;
 
 use rustc::hir;
 use rustc::hir::intravisit;
@@ -41,7 +41,7 @@ impl<'a, 'tcx, 'v> intravisit::Visitor<'v> for RvalueContext<'a, 'tcx> {
         // FIXME (@jroesch) change this to be an inference context
         let param_env = ParameterEnvironment::for_item(self.tcx, fn_id);
         self.tcx.infer_ctxt(None, Some(param_env.clone()),
-                            ProjectionMode::AnyFinal).enter(|infcx| {
+                            Reveal::NotSpecializable).enter(|infcx| {
             let mut delegate = RvalueContextDelegate {
                 tcx: infcx.tcx,
                 param_env: &param_env
diff --git a/src/librustc_trans/_match.rs b/src/librustc_trans/_match.rs
index f7fd970f37f..29b3f6ce52f 100644
--- a/src/librustc_trans/_match.rs
+++ b/src/librustc_trans/_match.rs
@@ -217,7 +217,7 @@ use type_of;
 use Disr;
 use value::Value;
 use rustc::ty::{self, Ty, TyCtxt};
-use rustc::traits::ProjectionMode;
+use rustc::traits::Reveal;
 use session::config::NoDebugInfo;
 use util::common::indenter;
 use util::nodemap::FnvHashMap;
@@ -1471,7 +1471,7 @@ fn is_discr_reassigned(bcx: Block, discr: &hir::Expr, body: &hir::Expr) -> bool
         field: field,
         reassigned: false
     };
-    bcx.tcx().normalizing_infer_ctxt(ProjectionMode::Any).enter(|infcx| {
+    bcx.tcx().normalizing_infer_ctxt(Reveal::All).enter(|infcx| {
         let mut visitor = euv::ExprUseVisitor::new(&mut rc, &infcx);
         visitor.walk_expr(body);
     });
diff --git a/src/librustc_trans/collector.rs b/src/librustc_trans/collector.rs
index 58b49f6944f..4a6dbb2bdae 100644
--- a/src/librustc_trans/collector.rs
+++ b/src/librustc_trans/collector.rs
@@ -796,6 +796,7 @@ fn find_drop_glue_neighbors<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
         ty::TyProjection(_) |
         ty::TyParam(_)      |
         ty::TyInfer(_)      |
+        ty::TyAnon(..)      |
         ty::TyError         => {
             bug!("encountered unexpected type");
         }
diff --git a/src/librustc_trans/common.rs b/src/librustc_trans/common.rs
index b3729cc23f6..dea5a1560e1 100644
--- a/src/librustc_trans/common.rs
+++ b/src/librustc_trans/common.rs
@@ -40,7 +40,7 @@ use type_::Type;
 use value::Value;
 use rustc::ty::{self, Ty, TyCtxt};
 use rustc::ty::layout::Layout;
-use rustc::traits::{self, SelectionContext, ProjectionMode};
+use rustc::traits::{self, SelectionContext, Reveal};
 use rustc::ty::fold::TypeFoldable;
 use rustc::hir;
 use util::nodemap::NodeMap;
@@ -128,7 +128,7 @@ pub fn type_pair_fields<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, ty: Ty<'tcx>)
 pub fn type_is_imm_pair<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, ty: Ty<'tcx>)
                                   -> bool {
     let tcx = ccx.tcx();
-    let layout = tcx.normalizing_infer_ctxt(ProjectionMode::Any).enter(|infcx| {
+    let layout = tcx.normalizing_infer_ctxt(Reveal::All).enter(|infcx| {
         match ty.layout(&infcx) {
             Ok(layout) => layout,
             Err(err) => {
@@ -1136,7 +1136,7 @@ pub fn fulfill_obligation<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
 
         // Do the initial selection for the obligation. This yields the
         // shallow result we are looking for -- that is, what specific impl.
-        tcx.normalizing_infer_ctxt(ProjectionMode::Any).enter(|infcx| {
+        tcx.normalizing_infer_ctxt(Reveal::All).enter(|infcx| {
             let mut selcx = SelectionContext::new(&infcx);
 
             let obligation_cause = traits::ObligationCause::misc(span,
@@ -1195,7 +1195,7 @@ pub fn normalize_and_test_predicates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     debug!("normalize_and_test_predicates(predicates={:?})",
            predicates);
 
-    tcx.normalizing_infer_ctxt(ProjectionMode::Any).enter(|infcx| {
+    tcx.normalizing_infer_ctxt(Reveal::All).enter(|infcx| {
         let mut selcx = SelectionContext::new(&infcx);
         let mut fulfill_cx = traits::FulfillmentContext::new();
         let cause = traits::ObligationCause::dummy();
diff --git a/src/librustc_trans/debuginfo/type_names.rs b/src/librustc_trans/debuginfo/type_names.rs
index 63f460e4693..bee2667c71f 100644
--- a/src/librustc_trans/debuginfo/type_names.rs
+++ b/src/librustc_trans/debuginfo/type_names.rs
@@ -150,6 +150,7 @@ pub fn push_debuginfo_type_name<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
         ty::TyError |
         ty::TyInfer(_) |
         ty::TyProjection(..) |
+        ty::TyAnon(..) |
         ty::TyParam(_) => {
             bug!("debuginfo: Trying to create type name for \
                 unexpected type: {:?}", t);
diff --git a/src/librustc_trans/glue.rs b/src/librustc_trans/glue.rs
index 6bc48546dfa..93e5f4ba1e2 100644
--- a/src/librustc_trans/glue.rs
+++ b/src/librustc_trans/glue.rs
@@ -115,7 +115,7 @@ pub fn get_drop_glue_type<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     match t.sty {
         ty::TyBox(typ) if !type_needs_drop(tcx, typ)
                          && type_is_sized(tcx, typ) => {
-            tcx.normalizing_infer_ctxt(traits::ProjectionMode::Any).enter(|infcx| {
+            tcx.normalizing_infer_ctxt(traits::Reveal::All).enter(|infcx| {
                 let layout = t.layout(&infcx).unwrap();
                 if layout.size(&tcx.data_layout).bytes() == 0 {
                     // `Box<ZeroSizeType>` does not allocate.
diff --git a/src/librustc_trans/meth.rs b/src/librustc_trans/meth.rs
index ac6af8d66e1..3d6093d4d69 100644
--- a/src/librustc_trans/meth.rs
+++ b/src/librustc_trans/meth.rs
@@ -17,7 +17,7 @@ use llvm::{ValueRef, get_params};
 use rustc::hir::def_id::DefId;
 use rustc::ty::subst::{FnSpace, Subst, Substs};
 use rustc::ty::subst;
-use rustc::traits::{self, ProjectionMode};
+use rustc::traits::{self, Reveal};
 use abi::FnType;
 use base::*;
 use build::*;
@@ -321,7 +321,7 @@ pub fn get_impl_method<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     match trait_def.ancestors(impl_def_id).fn_defs(tcx, name).next() {
         Some(node_item) => {
-            let substs = tcx.normalizing_infer_ctxt(ProjectionMode::Any).enter(|infcx| {
+            let substs = tcx.normalizing_infer_ctxt(Reveal::All).enter(|infcx| {
                 let substs = traits::translate_substs(&infcx, impl_def_id,
                                                       substs, node_item.node);
                 tcx.lift(&substs).unwrap_or_else(|| {
diff --git a/src/librustc_trans/trans_item.rs b/src/librustc_trans/trans_item.rs
index d0e00a6d593..187ffe353fd 100644
--- a/src/librustc_trans/trans_item.rs
+++ b/src/librustc_trans/trans_item.rs
@@ -536,7 +536,8 @@ pub fn push_unique_type_name<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         ty::TyError |
         ty::TyInfer(_) |
         ty::TyProjection(..) |
-        ty::TyParam(_) => {
+        ty::TyParam(_) |
+        ty::TyAnon(..) => {
             bug!("debuginfo: Trying to create type name for \
                   unexpected type: {:?}", t);
         }
diff --git a/src/librustc_trans/type_of.rs b/src/librustc_trans/type_of.rs
index e5acb9b6699..cde53f6fa89 100644
--- a/src/librustc_trans/type_of.rs
+++ b/src/librustc_trans/type_of.rs
@@ -16,7 +16,7 @@ use abi::FnType;
 use adt;
 use common::*;
 use machine;
-use rustc::traits::ProjectionMode;
+use rustc::traits::Reveal;
 use rustc::ty::{self, Ty, TypeFoldable};
 
 use type_::Type;
@@ -112,7 +112,8 @@ pub fn sizing_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>) -> Typ
             }
         }
 
-        ty::TyProjection(..) | ty::TyInfer(..) | ty::TyParam(..) | ty::TyError => {
+        ty::TyProjection(..) | ty::TyInfer(..) | ty::TyParam(..) |
+        ty::TyAnon(..) | ty::TyError => {
             bug!("fictitious type {:?} in sizing_type_of()", t)
         }
         ty::TySlice(_) | ty::TyTrait(..) | ty::TyStr => bug!()
@@ -123,7 +124,7 @@ pub fn sizing_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>) -> Typ
     cx.llsizingtypes().borrow_mut().insert(t, llsizingty);
 
     // FIXME(eddyb) Temporary sanity check for ty::layout.
-    let layout = cx.tcx().normalizing_infer_ctxt(ProjectionMode::Any).enter(|infcx| {
+    let layout = cx.tcx().normalizing_infer_ctxt(Reveal::All).enter(|infcx| {
         t.layout(&infcx)
     });
     match layout {
@@ -339,10 +340,11 @@ pub fn in_memory_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>) ->
           }
       }
 
-      ty::TyInfer(..) => bug!("type_of with TyInfer"),
-      ty::TyProjection(..) => bug!("type_of with TyProjection"),
-      ty::TyParam(..) => bug!("type_of with ty_param"),
-      ty::TyError => bug!("type_of with TyError"),
+      ty::TyInfer(..) |
+      ty::TyProjection(..) |
+      ty::TyParam(..) |
+      ty::TyAnon(..) |
+      ty::TyError => bug!("type_of with {:?}", t),
     };
 
     debug!("--> mapped t={:?} to llty={:?}", t, llty);
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 07595c5dbe1..ad61b5b0b51 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -56,6 +56,7 @@ use hir::print as pprust;
 use middle::resolve_lifetime as rl;
 use rustc::lint;
 use rustc::ty::subst::{FnSpace, TypeSpace, SelfSpace, Subst, Substs, ParamSpace};
+use rustc::ty::subst::VecPerParamSpace;
 use rustc::traits;
 use rustc::ty::{self, Ty, TyCtxt, ToPredicate, TypeFoldable};
 use rustc::ty::wf::object_region_bounds;
@@ -64,6 +65,7 @@ use require_c_abi_if_variadic;
 use rscope::{self, UnelidableRscope, RegionScope, ElidableRscope,
              ObjectLifetimeDefaultRscope, ShiftedRscope, BindingRscope,
              ElisionFailureInfo, ElidedLifetime};
+use rscope::{AnonTypeScope, MaybeWithAnonTypes};
 use util::common::{ErrorReported, FN_OUTPUT_NAME};
 use util::nodemap::{NodeMap, FnvHashSet};
 
@@ -634,20 +636,21 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
 
     fn convert_ty_with_lifetime_elision(&self,
                                         elided_lifetime: ElidedLifetime,
-                                        ty: &hir::Ty)
+                                        ty: &hir::Ty,
+                                        anon_scope: Option<AnonTypeScope>)
                                         -> Ty<'tcx>
     {
         match elided_lifetime {
             Ok(implied_output_region) => {
                 let rb = ElidableRscope::new(implied_output_region);
-                self.ast_ty_to_ty(&rb, ty)
+                self.ast_ty_to_ty(&MaybeWithAnonTypes::new(rb, anon_scope), ty)
             }
             Err(param_lifetimes) => {
                 // All regions must be explicitly specified in the output
                 // if the lifetime elision rules do not apply. This saves
                 // the user from potentially-confusing errors.
                 let rb = UnelidableRscope::new(param_lifetimes);
-                self.ast_ty_to_ty(&rb, ty)
+                self.ast_ty_to_ty(&MaybeWithAnonTypes::new(rb, anon_scope), ty)
             }
         }
     }
@@ -664,7 +667,8 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
         let region_substs =
             self.create_region_substs(rscope, span, decl_generics, Vec::new());
 
-        let binding_rscope = BindingRscope::new();
+        let anon_scope = rscope.anon_type_scope();
+        let binding_rscope = MaybeWithAnonTypes::new(BindingRscope::new(), anon_scope);
         let inputs =
             data.inputs.iter()
                        .map(|a_t| self.ast_ty_arg_to_ty(&binding_rscope, decl_generics,
@@ -678,7 +682,9 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
 
         let (output, output_span) = match data.output {
             Some(ref output_ty) => {
-                (self.convert_ty_with_lifetime_elision(implied_output_region, &output_ty),
+                (self.convert_ty_with_lifetime_elision(implied_output_region,
+                                                       &output_ty,
+                                                       anon_scope),
                  output_ty.span)
             }
             None => {
@@ -1702,7 +1708,14 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
             }
             hir::TyBareFn(ref bf) => {
                 require_c_abi_if_variadic(tcx, &bf.decl, bf.abi, ast_ty.span);
-                let bare_fn_ty = self.ty_of_bare_fn(bf.unsafety, bf.abi, &bf.decl);
+                let anon_scope = rscope.anon_type_scope();
+                let (bare_fn_ty, _) =
+                    self.ty_of_method_or_bare_fn(bf.unsafety,
+                                                 bf.abi,
+                                                 None,
+                                                 &bf.decl,
+                                                 anon_scope,
+                                                 anon_scope);
 
                 // Find any late-bound regions declared in return type that do
                 // not appear in the arguments. These are not wellformed.
@@ -1745,6 +1758,34 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
             hir::TyPolyTraitRef(ref bounds) => {
                 self.conv_ty_poly_trait_ref(rscope, ast_ty.span, bounds)
             }
+            hir::TyImplTrait(ref bounds) => {
+                use collect::{compute_bounds, SizedByDefault};
+
+                // Create the anonymized type.
+                let def_id = tcx.map.local_def_id(ast_ty.id);
+                if let Some(anon_scope) = rscope.anon_type_scope() {
+                    let substs = anon_scope.fresh_substs(tcx);
+                    let ty = tcx.mk_anon(tcx.map.local_def_id(ast_ty.id), substs);
+
+                    // Collect the bounds, i.e. the `A+B+'c` in `impl A+B+'c`.
+                    let bounds = compute_bounds(self, ty, bounds,
+                                                SizedByDefault::Yes,
+                                                Some(anon_scope),
+                                                ast_ty.span);
+                    let predicates = bounds.predicates(tcx, ty);
+                    let predicates = tcx.lift_to_global(&predicates).unwrap();
+                    tcx.predicates.borrow_mut().insert(def_id, ty::GenericPredicates {
+                        predicates: VecPerParamSpace::new(vec![], vec![], predicates)
+                    });
+
+                    ty
+                } else {
+                    span_err!(tcx.sess, ast_ty.span, E0562,
+                              "`impl Trait` not allowed outside of function \
+                               and inherent method return types");
+                    tcx.types.err
+                }
+            }
             hir::TyPath(ref maybe_qself, ref path) => {
                 debug!("ast_ty_to_ty: maybe_qself={:?} path={:?}", maybe_qself, path);
                 let path_res = tcx.expect_resolution(ast_ty.id);
@@ -1809,36 +1850,40 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
 
     pub fn ty_of_method(&self,
                         sig: &hir::MethodSig,
-                        untransformed_self_ty: Ty<'tcx>)
+                        untransformed_self_ty: Ty<'tcx>,
+                        anon_scope: Option<AnonTypeScope>)
                         -> (&'tcx ty::BareFnTy<'tcx>, ty::ExplicitSelfCategory) {
-        let (bare_fn_ty, optional_explicit_self_category) =
-            self.ty_of_method_or_bare_fn(sig.unsafety,
-                                         sig.abi,
-                                         Some(untransformed_self_ty),
-                                         &sig.decl);
-        (bare_fn_ty, optional_explicit_self_category)
+        self.ty_of_method_or_bare_fn(sig.unsafety,
+                                     sig.abi,
+                                     Some(untransformed_self_ty),
+                                     &sig.decl,
+                                     None,
+                                     anon_scope)
     }
 
     pub fn ty_of_bare_fn(&self,
                          unsafety: hir::Unsafety,
                          abi: abi::Abi,
-                         decl: &hir::FnDecl)
+                         decl: &hir::FnDecl,
+                         anon_scope: Option<AnonTypeScope>)
                          -> &'tcx ty::BareFnTy<'tcx> {
-        self.ty_of_method_or_bare_fn(unsafety, abi, None, decl).0
+        self.ty_of_method_or_bare_fn(unsafety, abi, None, decl, None, anon_scope).0
     }
 
-    fn ty_of_method_or_bare_fn<'a>(&self,
-                                   unsafety: hir::Unsafety,
-                                   abi: abi::Abi,
-                                   opt_untransformed_self_ty: Option<Ty<'tcx>>,
-                                   decl: &hir::FnDecl)
-                                   -> (&'tcx ty::BareFnTy<'tcx>, ty::ExplicitSelfCategory)
+    fn ty_of_method_or_bare_fn(&self,
+                               unsafety: hir::Unsafety,
+                               abi: abi::Abi,
+                               opt_untransformed_self_ty: Option<Ty<'tcx>>,
+                               decl: &hir::FnDecl,
+                               arg_anon_scope: Option<AnonTypeScope>,
+                               ret_anon_scope: Option<AnonTypeScope>)
+                               -> (&'tcx ty::BareFnTy<'tcx>, ty::ExplicitSelfCategory)
     {
         debug!("ty_of_method_or_bare_fn");
 
         // New region names that appear inside of the arguments of the function
         // declaration are bound to that function type.
-        let rb = rscope::BindingRscope::new();
+        let rb = MaybeWithAnonTypes::new(BindingRscope::new(), arg_anon_scope);
 
         // `implied_output_region` is the region that will be assumed for any
         // region parameters in the return type. In accordance with the rules for
@@ -1876,7 +1921,8 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
         let output_ty = match decl.output {
             hir::Return(ref output) =>
                 ty::FnConverging(self.convert_ty_with_lifetime_elision(implied_output_region,
-                                                                       &output)),
+                                                                       &output,
+                                                                       ret_anon_scope)),
             hir::DefaultReturn(..) => ty::FnConverging(self.tcx().mk_nil()),
             hir::NoReturn(..) => ty::FnDiverging
         };
diff --git a/src/librustc_typeck/check/compare_method.rs b/src/librustc_typeck/check/compare_method.rs
index 140fabce76b..e6ddc6ad693 100644
--- a/src/librustc_typeck/check/compare_method.rs
+++ b/src/librustc_typeck/check/compare_method.rs
@@ -11,7 +11,7 @@
 use middle::free_region::FreeRegionMap;
 use rustc::infer::{self, InferOk, TypeOrigin};
 use rustc::ty;
-use rustc::traits::{self, ProjectionMode};
+use rustc::traits::{self, Reveal};
 use rustc::ty::error::ExpectedFound;
 use rustc::ty::subst::{self, Subst, Substs, VecPerParamSpace};
 use rustc::hir::map::Node;
@@ -213,7 +213,7 @@ pub fn compare_impl_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
         return;
     }
 
-    tcx.infer_ctxt(None, None, ProjectionMode::AnyFinal).enter(|mut infcx| {
+    tcx.infer_ctxt(None, None, Reveal::NotSpecializable).enter(|mut infcx| {
         let mut fulfillment_cx = traits::FulfillmentContext::new();
 
         // Normalize the associated types in the trait_bounds.
@@ -433,7 +433,7 @@ pub fn compare_const_impl<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
            impl_trait_ref);
 
     let tcx = ccx.tcx;
-    tcx.infer_ctxt(None, None, ProjectionMode::AnyFinal).enter(|infcx| {
+    tcx.infer_ctxt(None, None, Reveal::NotSpecializable).enter(|infcx| {
         let mut fulfillment_cx = traits::FulfillmentContext::new();
 
         // The below is for the most part highly similar to the procedure
diff --git a/src/librustc_typeck/check/dropck.rs b/src/librustc_typeck/check/dropck.rs
index 56e4108153e..f65e15430da 100644
--- a/src/librustc_typeck/check/dropck.rs
+++ b/src/librustc_typeck/check/dropck.rs
@@ -17,7 +17,7 @@ use rustc::infer;
 use middle::region;
 use rustc::ty::subst::{self, Subst};
 use rustc::ty::{self, Ty, TyCtxt};
-use rustc::traits::{self, ProjectionMode};
+use rustc::traits::{self, Reveal};
 use util::nodemap::FnvHashSet;
 
 use syntax::ast;
@@ -84,7 +84,7 @@ fn ensure_drop_params_and_item_params_correspond<'a, 'tcx>(
     // check that the impl type can be made to match the trait type.
 
     let impl_param_env = ty::ParameterEnvironment::for_item(tcx, self_type_node_id);
-    tcx.infer_ctxt(None, Some(impl_param_env), ProjectionMode::AnyFinal).enter(|infcx| {
+    tcx.infer_ctxt(None, Some(impl_param_env), Reveal::NotSpecializable).enter(|infcx| {
         let tcx = infcx.tcx;
         let mut fulfillment_cx = traits::FulfillmentContext::new();
 
@@ -499,7 +499,7 @@ fn iterate_over_potentially_unsafe_regions_in_type<'a, 'b, 'gcx, 'tcx>(
         }
 
         // these are always dtorck
-        ty::TyTrait(..) | ty::TyProjection(_) => bug!(),
+        ty::TyTrait(..) | ty::TyProjection(_) | ty::TyAnon(..) => bug!(),
     }
 }
 
@@ -509,7 +509,7 @@ fn has_dtor_of_interest<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
         ty::TyEnum(def, _) | ty::TyStruct(def, _) => {
             def.is_dtorck(tcx)
         }
-        ty::TyTrait(..) | ty::TyProjection(..) => {
+        ty::TyTrait(..) | ty::TyProjection(..) | ty::TyAnon(..) => {
             debug!("ty: {:?} isn't known, and therefore is a dropck type", ty);
             true
         },
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index 648d1f42fb5..99f1b13d4e4 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -786,16 +786,19 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
             debug!("assemble_projection_candidates: step={:?}",
                    step);
 
-            let projection_trait_ref = match step.self_ty.sty {
-                ty::TyProjection(ref data) => &data.trait_ref,
+            let (def_id, substs) = match step.self_ty.sty {
+                ty::TyProjection(ref data) => {
+                    (data.trait_ref.def_id, data.trait_ref.substs)
+                }
+                ty::TyAnon(def_id, substs) => (def_id, substs),
                 _ => continue,
             };
 
-            debug!("assemble_projection_candidates: projection_trait_ref={:?}",
-                   projection_trait_ref);
+            debug!("assemble_projection_candidates: def_id={:?} substs={:?}",
+                   def_id, substs);
 
-            let trait_predicates = self.tcx.lookup_predicates(projection_trait_ref.def_id);
-            let bounds = trait_predicates.instantiate(self.tcx, projection_trait_ref.substs);
+            let trait_predicates = self.tcx.lookup_predicates(def_id);
+            let bounds = trait_predicates.instantiate(self.tcx, substs);
             let predicates = bounds.predicates.into_vec();
             debug!("assemble_projection_candidates: predicates={:?}",
                    predicates);
@@ -806,9 +809,8 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
             {
                 let bound = self.erase_late_bound_regions(&poly_bound);
 
-                debug!("assemble_projection_candidates: projection_trait_ref={:?} bound={:?}",
-                       projection_trait_ref,
-                       bound);
+                debug!("assemble_projection_candidates: def_id={:?} substs={:?} bound={:?}",
+                       def_id, substs, bound);
 
                 if self.can_equate(&step.self_ty, &bound.self_ty()).is_ok() {
                     let xform_self_ty = self.xform_self_ty(&item,
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 36fdba37061..c2c93161ce7 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -89,14 +89,14 @@ use hir::def_id::DefId;
 use hir::pat_util;
 use rustc::infer::{self, InferCtxt, InferOk, TypeOrigin, TypeTrace, type_variable};
 use rustc::ty::subst::{self, Subst, Substs, VecPerParamSpace, ParamSpace};
-use rustc::traits::{self, ProjectionMode};
+use rustc::traits::{self, Reveal};
 use rustc::ty::{GenericPredicates, TypeScheme};
 use rustc::ty::{ParamTy, ParameterEnvironment};
 use rustc::ty::{LvaluePreference, NoPreference, PreferMutLvalue};
 use rustc::ty::{self, ToPolyTraitRef, Ty, TyCtxt, Visibility};
 use rustc::ty::{MethodCall, MethodCallee};
 use rustc::ty::adjustment;
-use rustc::ty::fold::TypeFoldable;
+use rustc::ty::fold::{BottomUpFolder, TypeFoldable};
 use rustc::ty::util::{Representability, IntTypeExt};
 use require_c_abi_if_variadic;
 use rscope::{ElisionFailureInfo, RegionScope};
@@ -172,6 +172,16 @@ pub struct Inherited<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     deferred_call_resolutions: RefCell<DefIdMap<Vec<DeferredCallResolutionHandler<'gcx, 'tcx>>>>,
 
     deferred_cast_checks: RefCell<Vec<cast::CastCheck<'tcx>>>,
+
+    // Anonymized types found in explicit return types and their
+    // associated fresh inference variable. Writeback resolves these
+    // variables to get the concrete type, which can be used to
+    // deanonymize TyAnon, after typeck is done with all functions.
+    anon_types: RefCell<DefIdMap<Ty<'tcx>>>,
+
+    // Obligations which will have to be checked at the end of
+    // type-checking, after all functions have been inferred.
+    deferred_obligations: RefCell<Vec<traits::DeferredObligation<'tcx>>>,
 }
 
 impl<'a, 'gcx, 'tcx> Deref for Inherited<'a, 'gcx, 'tcx> {
@@ -384,13 +394,14 @@ pub struct InheritedBuilder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 }
 
 impl<'a, 'gcx, 'tcx> CrateCtxt<'a, 'gcx> {
-    pub fn inherited(&'a self, param_env: Option<ty::ParameterEnvironment<'gcx>>)
+    pub fn inherited(&'a self, id: ast::NodeId)
                      -> InheritedBuilder<'a, 'gcx, 'tcx> {
+        let param_env = ParameterEnvironment::for_item(self.tcx, id);
         InheritedBuilder {
             ccx: self,
             infcx: self.tcx.infer_ctxt(Some(ty::Tables::empty()),
-                                       param_env,
-                                       ProjectionMode::AnyFinal)
+                                       Some(param_env),
+                                       Reveal::NotSpecializable)
         }
     }
 }
@@ -408,6 +419,8 @@ impl<'a, 'gcx, 'tcx> InheritedBuilder<'a, 'gcx, 'tcx> {
                 locals: RefCell::new(NodeMap()),
                 deferred_call_resolutions: RefCell::new(DefIdMap()),
                 deferred_cast_checks: RefCell::new(Vec::new()),
+                anon_types: RefCell::new(DefIdMap()),
+                deferred_obligations: RefCell::new(Vec::new()),
             })
         })
     }
@@ -442,7 +455,7 @@ impl<'a, 'tcx> Visitor<'tcx> for CheckItemTypesVisitor<'a, 'tcx> {
     fn visit_ty(&mut self, t: &'tcx hir::Ty) {
         match t.node {
             hir::TyFixedLengthVec(_, ref expr) => {
-                check_const_in_type(self.ccx, &expr, self.ccx.tcx.types.usize);
+                check_const_with_type(self.ccx, &expr, self.ccx.tcx.types.usize, expr.id);
             }
             _ => {}
         }
@@ -475,6 +488,31 @@ pub fn check_item_bodies(ccx: &CrateCtxt) -> CompileResult {
     ccx.tcx.sess.track_errors(|| {
         let mut visit = CheckItemBodiesVisitor { ccx: ccx };
         ccx.tcx.visit_all_items_in_krate(DepNode::TypeckItemBody, &mut visit);
+
+        // Process deferred obligations, now that all functions
+        // bodies have been fully inferred.
+        for (&item_id, obligations) in ccx.deferred_obligations.borrow().iter() {
+            // Use the same DepNode as for the body of the original function/item.
+            let def_id = ccx.tcx.map.local_def_id(item_id);
+            let _task = ccx.tcx.dep_graph.in_task(DepNode::TypeckItemBody(def_id));
+
+            let param_env = ParameterEnvironment::for_item(ccx.tcx, item_id);
+            ccx.tcx.infer_ctxt(None, Some(param_env),
+                               Reveal::NotSpecializable).enter(|infcx| {
+                let mut fulfillment_cx = traits::FulfillmentContext::new();
+                for obligation in obligations.iter().map(|o| o.to_obligation()) {
+                    fulfillment_cx.register_predicate_obligation(&infcx, obligation);
+                }
+
+                if let Err(errors) = fulfillment_cx.select_all_or_error(&infcx) {
+                    infcx.report_fulfillment_errors(&errors);
+                }
+
+                if let Err(errors) = fulfillment_cx.select_rfc1592_obligations(&infcx) {
+                    infcx.report_fulfillment_errors_as_warnings(&errors, item_id);
+                }
+            });
+        }
     })
 }
 
@@ -501,17 +539,14 @@ pub fn check_drop_impls(ccx: &CrateCtxt) -> CompileResult {
 fn check_bare_fn<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                            decl: &'tcx hir::FnDecl,
                            body: &'tcx hir::Block,
-                           fn_id: ast::NodeId,
-                           fn_span: Span,
-                           raw_fty: Ty<'tcx>,
-                           param_env: ty::ParameterEnvironment<'tcx>)
-{
+                           fn_id: ast::NodeId) {
+    let raw_fty = ccx.tcx.lookup_item_type(ccx.tcx.map.local_def_id(fn_id)).ty;
     let fn_ty = match raw_fty.sty {
         ty::TyFnDef(_, _, f) => f,
         _ => span_bug!(body.span, "check_bare_fn: function type expected")
     };
 
-    ccx.inherited(Some(param_env)).enter(|inh| {
+    ccx.inherited(fn_id).enter(|inh| {
         // Compute the fty from point of view of inside fn.
         let fn_scope = inh.tcx.region_maps.call_site_extent(fn_id, body.id);
         let fn_sig =
@@ -529,8 +564,8 @@ fn check_bare_fn<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
         fcx.check_casts();
         fcx.select_all_obligations_or_error(); // Casts can introduce new obligations.
 
-        fcx.regionck_fn(fn_id, fn_span, decl, body);
-        fcx.resolve_type_vars_in_fn(decl, body);
+        fcx.regionck_fn(fn_id, decl, body);
+        fcx.resolve_type_vars_in_fn(decl, body, fn_id);
     });
 }
 
@@ -631,32 +666,29 @@ fn check_fn<'a, 'gcx, 'tcx>(inherited: &'a Inherited<'a, 'gcx, 'tcx>,
                             body: &'gcx hir::Block)
                             -> FnCtxt<'a, 'gcx, 'tcx>
 {
-    let arg_tys = &fn_sig.inputs;
-    let ret_ty = fn_sig.output;
+    let mut fn_sig = fn_sig.clone();
 
-    debug!("check_fn(arg_tys={:?}, ret_ty={:?}, fn_id={})",
-           arg_tys,
-           ret_ty,
-           fn_id);
+    debug!("check_fn(sig={:?}, fn_id={})", fn_sig, fn_id);
 
     // Create the function context.  This is either derived from scratch or,
     // in the case of function expressions, based on the outer context.
-    let fcx = FnCtxt::new(inherited, ret_ty, body.id);
+    let mut fcx = FnCtxt::new(inherited, fn_sig.output, body.id);
     *fcx.ps.borrow_mut() = UnsafetyState::function(unsafety, unsafety_id);
 
-    if let ty::FnConverging(ret_ty) = ret_ty {
-        fcx.require_type_is_sized(ret_ty, decl.output.span(), traits::ReturnType);
-    }
-
-    debug!("fn-sig-map: fn_id={} fn_sig={:?}", fn_id, fn_sig);
-
-    inherited.tables.borrow_mut().liberated_fn_sigs.insert(fn_id, fn_sig.clone());
+    fn_sig.output = match fcx.ret_ty {
+        ty::FnConverging(orig_ret_ty) => {
+            fcx.require_type_is_sized(orig_ret_ty, decl.output.span(), traits::ReturnType);
+            ty::FnConverging(fcx.instantiate_anon_types(&orig_ret_ty))
+        }
+        ty::FnDiverging => ty::FnDiverging
+    };
+    fcx.ret_ty = fn_sig.output;
 
     {
         let mut visit = GatherLocalsVisitor { fcx: &fcx, };
 
         // Add formal parameters.
-        for (arg_ty, input) in arg_tys.iter().zip(&decl.inputs) {
+        for (arg_ty, input) in fn_sig.inputs.iter().zip(&decl.inputs) {
             // The type of the argument must be well-formed.
             //
             // NB -- this is now checked in wfcheck, but that
@@ -672,21 +704,20 @@ fn check_fn<'a, 'gcx, 'tcx>(inherited: &'a Inherited<'a, 'gcx, 'tcx>,
             });
 
             // Check the pattern.
-            fcx.check_pat(&input.pat, *arg_ty);
+            fcx.check_pat(&input.pat, arg_ty);
+            fcx.write_ty(input.id, arg_ty);
         }
 
         visit.visit_block(body);
     }
 
-    fcx.check_block_with_expected(body, match ret_ty {
+    inherited.tables.borrow_mut().liberated_fn_sigs.insert(fn_id, fn_sig);
+
+    fcx.check_block_with_expected(body, match fcx.ret_ty {
         ty::FnConverging(result_type) => ExpectHasType(result_type),
         ty::FnDiverging => NoExpectation
     });
 
-    for (input, arg) in decl.inputs.iter().zip(arg_tys) {
-        fcx.write_ty(input.id, arg);
-    }
-
     fcx
 }
 
@@ -708,7 +739,7 @@ pub fn check_item_type<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx hir::Item) {
     match it.node {
       // Consts can play a role in type-checking, so they are included here.
       hir::ItemStatic(_, _, ref e) |
-      hir::ItemConst(_, ref e) => check_const(ccx, it.span, &e, it.id),
+      hir::ItemConst(_, ref e) => check_const(ccx, &e, it.id),
       hir::ItemEnum(ref enum_definition, _) => {
         check_enum_variants(ccx,
                             it.span,
@@ -787,23 +818,18 @@ pub fn check_item_body<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx hir::Item) {
     let _indenter = indenter();
     match it.node {
       hir::ItemFn(ref decl, _, _, _, _, ref body) => {
-        let fn_pty = ccx.tcx.lookup_item_type(ccx.tcx.map.local_def_id(it.id));
-        let param_env = ParameterEnvironment::for_item(ccx.tcx, it.id);
-        check_bare_fn(ccx, &decl, &body, it.id, it.span, fn_pty.ty, param_env);
+        check_bare_fn(ccx, &decl, &body, it.id);
       }
       hir::ItemImpl(_, _, _, _, _, ref impl_items) => {
         debug!("ItemImpl {} with id {}", it.name, it.id);
 
-        let impl_pty = ccx.tcx.lookup_item_type(ccx.tcx.map.local_def_id(it.id));
-
         for impl_item in impl_items {
             match impl_item.node {
                 hir::ImplItemKind::Const(_, ref expr) => {
-                    check_const(ccx, impl_item.span, &expr, impl_item.id)
+                    check_const(ccx, &expr, impl_item.id)
                 }
                 hir::ImplItemKind::Method(ref sig, ref body) => {
-                    check_method_body(ccx, &impl_pty.generics, sig, body,
-                                      impl_item.id, impl_item.span);
+                    check_bare_fn(ccx, &sig.decl, body, impl_item.id);
                 }
                 hir::ImplItemKind::Type(_) => {
                     // Nothing to do here.
@@ -812,17 +838,15 @@ pub fn check_item_body<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx hir::Item) {
         }
       }
       hir::ItemTrait(_, _, _, ref trait_items) => {
-        let trait_def = ccx.tcx.lookup_trait_def(ccx.tcx.map.local_def_id(it.id));
         for trait_item in trait_items {
             match trait_item.node {
                 hir::ConstTraitItem(_, Some(ref expr)) => {
-                    check_const(ccx, trait_item.span, &expr, trait_item.id)
+                    check_const(ccx, &expr, trait_item.id)
                 }
                 hir::MethodTraitItem(ref sig, Some(ref body)) => {
                     check_trait_fn_not_const(ccx, trait_item.span, sig.constness);
 
-                    check_method_body(ccx, &trait_def.generics, sig, body,
-                                      trait_item.id, trait_item.span);
+                    check_bare_fn(ccx, &sig.decl, body, trait_item.id);
                 }
                 hir::MethodTraitItem(ref sig, None) => {
                     check_trait_fn_not_const(ccx, trait_item.span, sig.constness);
@@ -899,29 +923,6 @@ fn check_on_unimplemented<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
     }
 }
 
-/// Type checks a method body.
-///
-/// # Parameters
-///
-/// * `item_generics`: generics defined on the impl/trait that contains
-///   the method
-/// * `self_bound`: bound for the `Self` type parameter, if any
-/// * `method`: the method definition
-fn check_method_body<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
-                               item_generics: &ty::Generics<'tcx>,
-                               sig: &'tcx hir::MethodSig,
-                               body: &'tcx hir::Block,
-                               id: ast::NodeId, span: Span) {
-    debug!("check_method_body(item_generics={:?}, id={})",
-            item_generics, id);
-    let param_env = ParameterEnvironment::for_item(ccx.tcx, id);
-
-    let fty = ccx.tcx.node_id_to_type(id);
-    debug!("check_method_body: fty={:?}", fty);
-
-    check_bare_fn(ccx, &sig.decl, body, id, span, fty, param_env);
-}
-
 fn report_forbidden_specialization<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                              impl_item: &hir::ImplItem,
                                              parent_impl: DefId)
@@ -1160,30 +1161,39 @@ fn check_impl_items_against_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
     }
 }
 
-/// Checks a constant appearing in a type. At the moment this is just the
-/// length expression in a fixed-length vector, but someday it might be
-/// extended to type-level numeric literals.
-fn check_const_in_type<'a,'tcx>(ccx: &'a CrateCtxt<'a,'tcx>,
-                                expr: &'tcx hir::Expr,
-                                expected_type: Ty<'tcx>) {
-    ccx.inherited(None).enter(|inh| {
+/// Checks a constant with a given type.
+fn check_const_with_type<'a, 'tcx>(ccx: &'a CrateCtxt<'a, 'tcx>,
+                                   expr: &'tcx hir::Expr,
+                                   expected_type: Ty<'tcx>,
+                                   id: ast::NodeId) {
+    ccx.inherited(id).enter(|inh| {
         let fcx = FnCtxt::new(&inh, ty::FnConverging(expected_type), expr.id);
-        fcx.check_const_with_ty(expr.span, expr, expected_type);
+        fcx.require_type_is_sized(expected_type, expr.span, traits::ConstSized);
+
+        // Gather locals in statics (because of block expressions).
+        // This is technically unnecessary because locals in static items are forbidden,
+        // but prevents type checking from blowing up before const checking can properly
+        // emit an error.
+        GatherLocalsVisitor { fcx: &fcx }.visit_expr(expr);
+
+        fcx.check_expr_coercable_to_type(expr, expected_type);
+
+        fcx.select_all_obligations_and_apply_defaults();
+        fcx.closure_analyze_const(expr);
+        fcx.select_obligations_where_possible();
+        fcx.check_casts();
+        fcx.select_all_obligations_or_error();
+
+        fcx.regionck_expr(expr);
+        fcx.resolve_type_vars_in_expr(expr, id);
     });
 }
 
-fn check_const<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
-                        sp: Span,
-                        e: &'tcx hir::Expr,
-                        id: ast::NodeId) {
-    let param_env = ParameterEnvironment::for_item(ccx.tcx, id);
-    ccx.inherited(Some(param_env)).enter(|inh| {
-        let rty = ccx.tcx.node_id_to_type(id);
-        let fcx = FnCtxt::new(&inh, ty::FnConverging(rty), e.id);
-        let declty = fcx.tcx.lookup_item_type(ccx.tcx.map.local_def_id(id)).ty;
-        fcx.require_type_is_sized(declty, e.span, traits::ConstSized);
-        fcx.check_const_with_ty(sp, e, declty);
-    });
+fn check_const<'a, 'tcx>(ccx: &CrateCtxt<'a,'tcx>,
+                         expr: &'tcx hir::Expr,
+                         id: ast::NodeId) {
+    let decl_ty = ccx.tcx.lookup_item_type(ccx.tcx.map.local_def_id(id)).ty;
+    check_const_with_type(ccx, expr, decl_ty, id);
 }
 
 /// Checks whether a type can be represented in memory. In particular, it
@@ -1252,45 +1262,40 @@ pub fn check_enum_variants<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
             "unsupported representation for zero-variant enum");
     }
 
-    ccx.inherited(None).enter(|inh| {
-        let rty = ccx.tcx.node_id_to_type(id);
-        let fcx = FnCtxt::new(&inh, ty::FnConverging(rty), id);
-
-        let repr_type_ty = ccx.tcx.enum_repr_type(Some(&hint)).to_ty(ccx.tcx);
-        for v in vs {
-            if let Some(ref e) = v.node.disr_expr {
-                fcx.check_const_with_ty(e.span, e, repr_type_ty);
-            }
+    let repr_type_ty = ccx.tcx.enum_repr_type(Some(&hint)).to_ty(ccx.tcx);
+    for v in vs {
+        if let Some(ref e) = v.node.disr_expr {
+            check_const_with_type(ccx, e, repr_type_ty, e.id);
         }
+    }
 
-        let def_id = ccx.tcx.map.local_def_id(id);
-
-        let variants = &ccx.tcx.lookup_adt_def(def_id).variants;
-        let mut disr_vals: Vec<ty::Disr> = Vec::new();
-        for (v, variant) in vs.iter().zip(variants.iter()) {
-            let current_disr_val = variant.disr_val;
+    let def_id = ccx.tcx.map.local_def_id(id);
 
-            // Check for duplicate discriminant values
-            if let Some(i) = disr_vals.iter().position(|&x| x == current_disr_val) {
-                let variant_i_node_id = ccx.tcx.map.as_local_node_id(variants[i].did).unwrap();
-                let variant_i = ccx.tcx.map.expect_variant(variant_i_node_id);
-                let i_span = match variant_i.node.disr_expr {
-                    Some(ref expr) => expr.span,
-                    None => ccx.tcx.map.span(variant_i_node_id)
-                };
-                let span = match v.node.disr_expr {
-                    Some(ref expr) => expr.span,
-                    None => v.span
-                };
-                struct_span_err!(ccx.tcx.sess, span, E0081,
-                                 "discriminant value `{}` already exists", disr_vals[i])
-                    .span_label(i_span, &format!("first use of `{}`", disr_vals[i]))
-                    .span_label(span , &format!("enum already has `{}`", disr_vals[i]))
-                    .emit();
-            }
-            disr_vals.push(current_disr_val);
+    let variants = &ccx.tcx.lookup_adt_def(def_id).variants;
+    let mut disr_vals: Vec<ty::Disr> = Vec::new();
+    for (v, variant) in vs.iter().zip(variants.iter()) {
+        let current_disr_val = variant.disr_val;
+
+        // Check for duplicate discriminant values
+        if let Some(i) = disr_vals.iter().position(|&x| x == current_disr_val) {
+            let variant_i_node_id = ccx.tcx.map.as_local_node_id(variants[i].did).unwrap();
+            let variant_i = ccx.tcx.map.expect_variant(variant_i_node_id);
+            let i_span = match variant_i.node.disr_expr {
+                Some(ref expr) => expr.span,
+                None => ccx.tcx.map.span(variant_i_node_id)
+            };
+            let span = match v.node.disr_expr {
+                Some(ref expr) => expr.span,
+                None => v.span
+            };
+            struct_span_err!(ccx.tcx.sess, span, E0081,
+                             "discriminant value `{}` already exists", disr_vals[i])
+                .span_label(i_span, &format!("first use of `{}`", disr_vals[i]))
+                .span_label(span , &format!("enum already has `{}`", disr_vals[i]))
+                .emit();
         }
-    });
+        disr_vals.push(current_disr_val);
+    }
 
     check_representable(ccx.tcx, sp, id, "enum");
 }
@@ -1623,6 +1628,41 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         }
     }
 
+    /// Replace all anonymized types with fresh inference variables
+    /// and record them for writeback.
+    fn instantiate_anon_types<T: TypeFoldable<'tcx>>(&self, value: &T) -> T {
+        value.fold_with(&mut BottomUpFolder { tcx: self.tcx, fldop: |ty| {
+            if let ty::TyAnon(def_id, substs) = ty.sty {
+                // Use the same type variable if the exact same TyAnon appears more
+                // than once in the return type (e.g. if it's pased to a type alias).
+                if let Some(ty_var) = self.anon_types.borrow().get(&def_id) {
+                    return ty_var;
+                }
+                let ty_var = self.next_ty_var();
+                self.anon_types.borrow_mut().insert(def_id, ty_var);
+
+                let item_predicates = self.tcx.lookup_predicates(def_id);
+                let bounds = item_predicates.instantiate(self.tcx, substs);
+
+                let span = self.tcx.map.def_id_span(def_id, codemap::DUMMY_SP);
+                for predicate in bounds.predicates {
+                    // Change the predicate to refer to the type variable,
+                    // which will be the concrete type, instead of the TyAnon.
+                    // This also instantiates nested `impl Trait`.
+                    let predicate = self.instantiate_anon_types(&predicate);
+
+                    // Require that the predicate holds for the concrete type.
+                    let cause = traits::ObligationCause::new(span, self.body_id,
+                                                             traits::ReturnType);
+                    self.register_predicate(traits::Obligation::new(cause, predicate));
+                }
+
+                ty_var
+            } else {
+                ty
+            }
+        }})
+    }
 
     fn normalize_associated_types_in<T>(&self, span: Span, value: &T) -> T
         where T : TypeFoldable<'tcx>
@@ -2190,6 +2230,12 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         self.select_all_obligations_and_apply_defaults();
 
         let mut fulfillment_cx = self.fulfillment_cx.borrow_mut();
+
+        // Steal the deferred obligations before the fulfillment
+        // context can turn all of them into errors.
+        let obligations = fulfillment_cx.take_deferred_obligations();
+        self.deferred_obligations.borrow_mut().extend(obligations);
+
         match fulfillment_cx.select_all_or_error(self) {
             Ok(()) => { }
             Err(errors) => { self.report_fulfillment_errors(&errors); }
@@ -3998,29 +4044,6 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         *self.ps.borrow_mut() = prev;
     }
 
-
-    fn check_const_with_ty(&self,
-                           _: Span,
-                           e: &'gcx hir::Expr,
-                           declty: Ty<'tcx>) {
-        // Gather locals in statics (because of block expressions).
-        // This is technically unnecessary because locals in static items are forbidden,
-        // but prevents type checking from blowing up before const checking can properly
-        // emit an error.
-        GatherLocalsVisitor { fcx: self }.visit_expr(e);
-
-        self.check_expr_coercable_to_type(e, declty);
-
-        self.select_all_obligations_and_apply_defaults();
-        self.closure_analyze_const(e);
-        self.select_obligations_where_possible();
-        self.check_casts();
-        self.select_all_obligations_or_error();
-
-        self.regionck_expr(e);
-        self.resolve_type_vars_in_expr(e);
-    }
-
     // Returns the type parameter count and the type for the given definition.
     fn type_scheme_and_predicates_for_def(&self,
                                           sp: Span,
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index 5a7038a0569..f3a6442f35d 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -141,7 +141,6 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
 
     pub fn regionck_fn(&self,
                        fn_id: ast::NodeId,
-                       fn_span: Span,
                        decl: &hir::FnDecl,
                        blk: &hir::Block) {
         debug!("regionck_fn(id={})", fn_id);
@@ -149,7 +148,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
 
         if self.err_count_since_creation() == 0 {
             // regionck assumes typeck succeeded
-            rcx.visit_fn_body(fn_id, decl, blk, fn_span);
+            rcx.visit_fn_body(fn_id, decl, blk, self.tcx.map.span(fn_id));
         }
 
         rcx.free_region_map.relate_free_regions_from_predicates(
diff --git a/src/librustc_typeck/check/wfcheck.rs b/src/librustc_typeck/check/wfcheck.rs
index 34a91b22981..e2080906ca2 100644
--- a/src/librustc_typeck/check/wfcheck.rs
+++ b/src/librustc_typeck/check/wfcheck.rs
@@ -209,9 +209,8 @@ impl<'ccx, 'gcx> CheckTypeWellFormedVisitor<'ccx, 'gcx> {
 
     fn for_id<'tcx>(&self, id: ast::NodeId, span: Span)
                     -> CheckWfFcxBuilder<'ccx, 'gcx, 'tcx> {
-        let param_env = ty::ParameterEnvironment::for_item(self.ccx.tcx, id);
         CheckWfFcxBuilder {
-            inherited: self.ccx.inherited(Some(param_env)),
+            inherited: self.ccx.inherited(id),
             code: self.code.clone(),
             id: id,
             span: span
diff --git a/src/librustc_typeck/check/writeback.rs b/src/librustc_typeck/check/writeback.rs
index 42893e40024..9026920e7f4 100644
--- a/src/librustc_typeck/check/writeback.rs
+++ b/src/librustc_typeck/check/writeback.rs
@@ -18,7 +18,9 @@ use hir::def_id::DefId;
 use rustc::ty::{self, Ty, TyCtxt, MethodCall, MethodCallee};
 use rustc::ty::adjustment;
 use rustc::ty::fold::{TypeFolder,TypeFoldable};
+use rustc::ty::subst::ParamSpace;
 use rustc::infer::{InferCtxt, FixupError};
+use rustc::util::nodemap::DefIdMap;
 use write_substs_to_tcx;
 use write_ty_to_tcx;
 
@@ -35,7 +37,7 @@ use rustc::hir::{self, PatKind};
 // Entry point functions
 
 impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
-    pub fn resolve_type_vars_in_expr(&self, e: &hir::Expr) {
+    pub fn resolve_type_vars_in_expr(&self, e: &hir::Expr, item_id: ast::NodeId) {
         assert_eq!(self.writeback_errors.get(), false);
         let mut wbcx = WritebackCx::new(self);
         wbcx.visit_expr(e);
@@ -43,9 +45,13 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         wbcx.visit_closures();
         wbcx.visit_liberated_fn_sigs();
         wbcx.visit_fru_field_types();
+        wbcx.visit_deferred_obligations(item_id);
     }
 
-    pub fn resolve_type_vars_in_fn(&self, decl: &hir::FnDecl, blk: &hir::Block) {
+    pub fn resolve_type_vars_in_fn(&self,
+                                   decl: &hir::FnDecl,
+                                   blk: &hir::Block,
+                                   item_id: ast::NodeId) {
         assert_eq!(self.writeback_errors.get(), false);
         let mut wbcx = WritebackCx::new(self);
         wbcx.visit_block(blk);
@@ -62,6 +68,8 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         wbcx.visit_closures();
         wbcx.visit_liberated_fn_sigs();
         wbcx.visit_fru_field_types();
+        wbcx.visit_anon_types();
+        wbcx.visit_deferred_obligations(item_id);
     }
 }
 
@@ -75,11 +83,48 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
 
 struct WritebackCx<'cx, 'gcx: 'cx+'tcx, 'tcx: 'cx> {
     fcx: &'cx FnCtxt<'cx, 'gcx, 'tcx>,
+
+    // Mapping from free regions of the function to the
+    // early-bound versions of them, visible from the
+    // outside of the function. This is needed by, and
+    // only populated if there are any `impl Trait`.
+    free_to_bound_regions: DefIdMap<ty::Region>
 }
 
 impl<'cx, 'gcx, 'tcx> WritebackCx<'cx, 'gcx, 'tcx> {
     fn new(fcx: &'cx FnCtxt<'cx, 'gcx, 'tcx>) -> WritebackCx<'cx, 'gcx, 'tcx> {
-        WritebackCx { fcx: fcx }
+        let mut wbcx = WritebackCx {
+            fcx: fcx,
+            free_to_bound_regions: DefIdMap()
+        };
+
+        // Only build the reverse mapping if `impl Trait` is used.
+        if fcx.anon_types.borrow().is_empty() {
+            return wbcx;
+        }
+
+        let free_substs = fcx.parameter_environment.free_substs;
+        for &space in &ParamSpace::all() {
+            for (i, r) in free_substs.regions.get_slice(space).iter().enumerate() {
+                match *r {
+                    ty::ReFree(ty::FreeRegion {
+                        bound_region: ty::BoundRegion::BrNamed(def_id, name, _), ..
+                    }) => {
+                        let bound_region = ty::ReEarlyBound(ty::EarlyBoundRegion {
+                            space: space,
+                            index: i as u32,
+                            name: name,
+                        });
+                        wbcx.free_to_bound_regions.insert(def_id, bound_region);
+                    }
+                    _ => {
+                        bug!("{:?} is not a free region for an early-bound lifetime", r);
+                    }
+                }
+            }
+        }
+
+        wbcx
     }
 
     fn tcx(&self) -> TyCtxt<'cx, 'gcx, 'tcx> {
@@ -255,6 +300,58 @@ impl<'cx, 'gcx, 'tcx> WritebackCx<'cx, 'gcx, 'tcx> {
         }
     }
 
+    fn visit_anon_types(&self) {
+        if self.fcx.writeback_errors.get() {
+            return
+        }
+
+        let gcx = self.tcx().global_tcx();
+        for (&def_id, &concrete_ty) in self.fcx.anon_types.borrow().iter() {
+            let reason = ResolvingAnonTy(def_id);
+            let inside_ty = self.resolve(&concrete_ty, reason);
+
+            // Convert the type from the function into a type valid outside
+            // the function, by replacing free regions with early-bound ones.
+            let outside_ty = gcx.fold_regions(&inside_ty, &mut false, |r, _| {
+                match r {
+                    // 'static is valid everywhere.
+                    ty::ReStatic => ty::ReStatic,
+
+                    // Free regions that come from early-bound regions are valid.
+                    ty::ReFree(ty::FreeRegion {
+                        bound_region: ty::BoundRegion::BrNamed(def_id, _, _), ..
+                    }) if self.free_to_bound_regions.contains_key(&def_id) => {
+                        self.free_to_bound_regions[&def_id]
+                    }
+
+                    ty::ReFree(_) |
+                    ty::ReEarlyBound(_) |
+                    ty::ReLateBound(..) |
+                    ty::ReScope(_) |
+                    ty::ReSkolemized(..) => {
+                        let span = reason.span(self.tcx());
+                        span_err!(self.tcx().sess, span, E0564,
+                                  "only named lifetimes are allowed in `impl Trait`, \
+                                   but `{}` was found in the type `{}`", r, inside_ty);
+                        ty::ReStatic
+                    }
+
+                    ty::ReVar(_) |
+                    ty::ReEmpty |
+                    ty::ReErased => {
+                        let span = reason.span(self.tcx());
+                        span_bug!(span, "invalid region in impl Trait: {:?}", r);
+                    }
+                }
+            });
+
+            gcx.tcache.borrow_mut().insert(def_id, ty::TypeScheme {
+                ty: outside_ty,
+                generics: ty::Generics::empty()
+            });
+        }
+    }
+
     fn visit_node_id(&self, reason: ResolveReason, id: ast::NodeId) {
         // Resolve any borrowings for the node with id `id`
         self.visit_adjustments(reason, id);
@@ -353,6 +450,19 @@ impl<'cx, 'gcx, 'tcx> WritebackCx<'cx, 'gcx, 'tcx> {
         }
     }
 
+    fn visit_deferred_obligations(&self, item_id: ast::NodeId) {
+        let deferred_obligations = self.fcx.deferred_obligations.borrow();
+        let obligations: Vec<_> = deferred_obligations.iter().map(|obligation| {
+            let reason = ResolvingDeferredObligation(obligation.cause.span);
+            self.resolve(obligation, reason)
+        }).collect();
+
+        if !obligations.is_empty() {
+            assert!(self.fcx.ccx.deferred_obligations.borrow_mut()
+                                .insert(item_id, obligations).is_none());
+        }
+    }
+
     fn resolve<T>(&self, x: &T, reason: ResolveReason) -> T::Lifted
         where T: TypeFoldable<'tcx> + ty::Lift<'gcx>
     {
@@ -369,7 +479,7 @@ impl<'cx, 'gcx, 'tcx> WritebackCx<'cx, 'gcx, 'tcx> {
 ///////////////////////////////////////////////////////////////////////////
 // Resolution reason.
 
-#[derive(Copy, Clone)]
+#[derive(Copy, Clone, Debug)]
 enum ResolveReason {
     ResolvingExpr(Span),
     ResolvingLocal(Span),
@@ -377,7 +487,9 @@ enum ResolveReason {
     ResolvingUpvar(ty::UpvarId),
     ResolvingClosure(DefId),
     ResolvingFnSig(ast::NodeId),
-    ResolvingFieldTypes(ast::NodeId)
+    ResolvingFieldTypes(ast::NodeId),
+    ResolvingAnonTy(DefId),
+    ResolvingDeferredObligation(Span),
 }
 
 impl<'a, 'gcx, 'tcx> ResolveReason {
@@ -395,13 +507,11 @@ impl<'a, 'gcx, 'tcx> ResolveReason {
             ResolvingFieldTypes(id) => {
                 tcx.map.span(id)
             }
-            ResolvingClosure(did) => {
-                if let Some(node_id) = tcx.map.as_local_node_id(did) {
-                    tcx.expr_span(node_id)
-                } else {
-                    DUMMY_SP
-                }
+            ResolvingClosure(did) |
+            ResolvingAnonTy(did) => {
+                tcx.map.def_id_span(did, DUMMY_SP)
             }
+            ResolvingDeferredObligation(span) => span
         }
     }
 }
@@ -474,14 +584,23 @@ impl<'cx, 'gcx, 'tcx> Resolver<'cx, 'gcx, 'tcx> {
                               "cannot determine a type for this closure")
                 }
 
-                ResolvingFnSig(id) | ResolvingFieldTypes(id) => {
+                ResolvingFnSig(_) |
+                ResolvingFieldTypes(_) |
+                ResolvingDeferredObligation(_) => {
                     // any failures here should also fail when
                     // resolving the patterns, closure types, or
                     // something else.
                     let span = self.reason.span(self.tcx);
                     self.tcx.sess.delay_span_bug(
                         span,
-                        &format!("cannot resolve some aspect of data for {:?}", id));
+                        &format!("cannot resolve some aspect of data for {:?}: {}",
+                                 self.reason, e));
+                }
+
+                ResolvingAnonTy(_) => {
+                    let span = self.reason.span(self.tcx);
+                    span_err!(self.tcx.sess, span, E0563,
+                              "cannot determine a type for this `impl Trait`: {}", e)
                 }
             }
         }
diff --git a/src/librustc_typeck/coherence/mod.rs b/src/librustc_typeck/coherence/mod.rs
index 7a923cd29d0..13deac57330 100644
--- a/src/librustc_typeck/coherence/mod.rs
+++ b/src/librustc_typeck/coherence/mod.rs
@@ -19,7 +19,7 @@ use hir::def_id::DefId;
 use middle::lang_items::UnsizeTraitLangItem;
 use rustc::ty::subst::{self, Subst};
 use rustc::ty::{self, TyCtxt, TypeFoldable};
-use rustc::traits::{self, ProjectionMode};
+use rustc::traits::{self, Reveal};
 use rustc::ty::{ImplOrTraitItemId, ConstTraitItemId};
 use rustc::ty::{MethodTraitItemId, TypeTraitItemId, ParameterEnvironment};
 use rustc::ty::{Ty, TyBool, TyChar, TyEnum, TyError};
@@ -27,7 +27,7 @@ use rustc::ty::{TyParam, TyRawPtr};
 use rustc::ty::{TyRef, TyStruct, TyTrait, TyTuple};
 use rustc::ty::{TyStr, TyArray, TySlice, TyFloat, TyInfer, TyInt};
 use rustc::ty::{TyUint, TyClosure, TyBox, TyFnDef, TyFnPtr};
-use rustc::ty::TyProjection;
+use rustc::ty::{TyProjection, TyAnon};
 use rustc::ty::util::CopyImplementationError;
 use middle::free_region::FreeRegionMap;
 use CrateCtxt;
@@ -89,7 +89,7 @@ impl<'a, 'gcx, 'tcx> CoherenceChecker<'a, 'gcx, 'tcx> {
                 None
             }
 
-            TyInfer(..) | TyClosure(..) => {
+            TyInfer(..) | TyClosure(..) | TyAnon(..) => {
                 // `ty` comes from a user declaration so we should only expect types
                 // that the user can type
                 span_bug!(
@@ -399,7 +399,7 @@ impl<'a, 'gcx, 'tcx> CoherenceChecker<'a, 'gcx, 'tcx> {
             debug!("check_implementations_of_coerce_unsized: {:?} -> {:?} (free)",
                    source, target);
 
-            tcx.infer_ctxt(None, Some(param_env), ProjectionMode::Topmost).enter(|infcx| {
+            tcx.infer_ctxt(None, Some(param_env), Reveal::ExactMatch).enter(|infcx| {
                 let origin = TypeOrigin::Misc(span);
                 let check_mutbl = |mt_a: ty::TypeAndMut<'gcx>, mt_b: ty::TypeAndMut<'gcx>,
                                    mk_ptr: &Fn(Ty<'gcx>) -> Ty<'gcx>| {
@@ -536,7 +536,7 @@ fn enforce_trait_manually_implementable(tcx: TyCtxt, sp: Span, trait_def_id: Def
 
 pub fn check_coherence(ccx: &CrateCtxt) {
     let _task = ccx.tcx.dep_graph.in_task(DepNode::Coherence);
-    ccx.tcx.infer_ctxt(None, None, ProjectionMode::Topmost).enter(|infcx| {
+    ccx.tcx.infer_ctxt(None, None, Reveal::ExactMatch).enter(|infcx| {
         CoherenceChecker {
             crate_context: ccx,
             inference_context: infcx,
diff --git a/src/librustc_typeck/coherence/overlap.rs b/src/librustc_typeck/coherence/overlap.rs
index 54bd141304d..46a9ef8d5ba 100644
--- a/src/librustc_typeck/coherence/overlap.rs
+++ b/src/librustc_typeck/coherence/overlap.rs
@@ -13,7 +13,7 @@
 //! constructor provide a method with the same name.
 
 use hir::def_id::DefId;
-use rustc::traits::{self, ProjectionMode};
+use rustc::traits::{self, Reveal};
 use rustc::ty::{self, TyCtxt};
 use syntax::ast;
 use rustc::dep_graph::DepNode;
@@ -84,7 +84,7 @@ impl<'cx, 'tcx> OverlapChecker<'cx, 'tcx> {
 
         for (i, &impl1_def_id) in impls.iter().enumerate() {
             for &impl2_def_id in &impls[(i+1)..] {
-                self.tcx.infer_ctxt(None, None, ProjectionMode::Topmost).enter(|infcx| {
+                self.tcx.infer_ctxt(None, None, Reveal::ExactMatch).enter(|infcx| {
                     if traits::overlapping_impls(&infcx, impl1_def_id, impl2_def_id).is_some() {
                         self.check_for_common_items_in_impls(impl1_def_id, impl2_def_id)
                     }
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index f68d902ef36..75bfad053a3 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -564,13 +564,17 @@ fn convert_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
     let ty_generic_predicates =
         ty_generic_predicates_for_fn(ccx, &sig.generics, rcvr_ty_predicates);
 
-    let (fty, explicit_self_category) =
+    let (fty, explicit_self_category) = {
+        let anon_scope = match container {
+            ImplContainer(_) => Some(AnonTypeScope::new(&ty_generics)),
+            TraitContainer(_) => None
+        };
         AstConv::ty_of_method(&ccx.icx(&(rcvr_ty_predicates, &sig.generics)),
-                              sig,
-                              untransformed_rcvr_ty);
+                              sig, untransformed_rcvr_ty, anon_scope)
+    };
 
     let def_id = ccx.tcx.map.local_def_id(id);
-    let substs = mk_item_substs(ccx, &ty_generics);
+    let substs = mk_item_substs(ccx.tcx, &ty_generics);
 
     let ty_method = ty::Method::new(name,
                                     ty_generics,
@@ -961,7 +965,7 @@ fn convert_variant_ctor<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                 .map(|field| field.unsubst_ty())
                 .collect();
             let def_id = tcx.map.local_def_id(ctor_id);
-            let substs = mk_item_substs(ccx, &scheme.generics);
+            let substs = mk_item_substs(tcx, &scheme.generics);
             tcx.mk_fn_def(def_id, substs, tcx.mk_bare_fn(ty::BareFnTy {
                 unsafety: hir::Unsafety::Normal,
                 abi: abi::Abi::Rust,
@@ -1190,10 +1194,11 @@ fn ensure_super_predicates_step(ccx: &CrateCtxt,
         // Convert the bounds that follow the colon, e.g. `Bar+Zed` in `trait Foo : Bar+Zed`.
         let self_param_ty = tcx.mk_self_type();
         let superbounds1 = compute_bounds(&ccx.icx(scope),
-                                    self_param_ty,
-                                    bounds,
-                                    SizedByDefault::No,
-                                    item.span);
+                                          self_param_ty,
+                                          bounds,
+                                          SizedByDefault::No,
+                                          None,
+                                          item.span);
 
         let superbounds1 = superbounds1.predicates(tcx, self_param_ty);
 
@@ -1403,6 +1408,7 @@ fn convert_trait_predicates<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &hir::Item)
                                         assoc_ty,
                                         bounds,
                                         SizedByDefault::Yes,
+                                        None,
                                         trait_item.span);
 
             bounds.predicates(ccx.tcx, assoc_ty).into_iter()
@@ -1460,9 +1466,10 @@ fn compute_type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
         }
         hir::ItemFn(ref decl, unsafety, _, abi, ref generics, _) => {
             let ty_generics = ty_generics_for_fn(ccx, generics, &ty::Generics::empty());
-            let tofd = AstConv::ty_of_bare_fn(&ccx.icx(generics), unsafety, abi, &decl);
+            let tofd = AstConv::ty_of_bare_fn(&ccx.icx(generics), unsafety, abi, &decl,
+                                              Some(AnonTypeScope::new(&ty_generics)));
             let def_id = ccx.tcx.map.local_def_id(it.id);
-            let substs = mk_item_substs(ccx, &ty_generics);
+            let substs = mk_item_substs(tcx, &ty_generics);
             let ty = tcx.mk_fn_def(def_id, substs, tofd);
             ty::TypeScheme { ty: ty, generics: ty_generics }
         }
@@ -1474,14 +1481,14 @@ fn compute_type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
         hir::ItemEnum(ref ei, ref generics) => {
             let def = convert_enum_def(ccx, it, ei);
             let ty_generics = ty_generics_for_type(ccx, generics);
-            let substs = mk_item_substs(ccx, &ty_generics);
+            let substs = mk_item_substs(tcx, &ty_generics);
             let t = tcx.mk_enum(def, substs);
             ty::TypeScheme { ty: t, generics: ty_generics }
         }
         hir::ItemStruct(ref si, ref generics) => {
             let def = convert_struct_def(ccx, it, si);
             let ty_generics = ty_generics_for_type(ccx, generics);
-            let substs = mk_item_substs(ccx, &ty_generics);
+            let substs = mk_item_substs(tcx, &ty_generics);
             let t = tcx.mk_struct(def, substs);
             ty::TypeScheme { ty: t, generics: ty_generics }
         }
@@ -1694,10 +1701,10 @@ fn ty_generic_predicates_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
 }
 
 // Add the Sized bound, unless the type parameter is marked as `?Sized`.
-fn add_unsized_bound<'tcx>(astconv: &AstConv<'tcx, 'tcx>,
-                           bounds: &mut ty::BuiltinBounds,
-                           ast_bounds: &[hir::TyParamBound],
-                           span: Span)
+fn add_unsized_bound<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
+                                       bounds: &mut ty::BuiltinBounds,
+                                       ast_bounds: &[hir::TyParamBound],
+                                       span: Span)
 {
     let tcx = astconv.tcx();
 
@@ -1775,6 +1782,7 @@ fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
                                     param_ty,
                                     &param.bounds,
                                     SizedByDefault::Yes,
+                                    None,
                                     param.span);
         let predicates = bounds.predicates(ccx.tcx, param_ty);
         result.predicates.extend(space, predicates.into_iter());
@@ -2038,34 +2046,52 @@ fn compute_object_lifetime_default<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
     }
 }
 
-enum SizedByDefault { Yes, No, }
+pub enum SizedByDefault { Yes, No, }
 
 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
 /// built-in trait (formerly known as kind): Send.
-fn compute_bounds<'tcx>(astconv: &AstConv<'tcx, 'tcx>,
-                        param_ty: ty::Ty<'tcx>,
-                        ast_bounds: &[hir::TyParamBound],
-                        sized_by_default: SizedByDefault,
-                        span: Span)
-                        -> Bounds<'tcx>
+pub fn compute_bounds<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
+                                        param_ty: ty::Ty<'tcx>,
+                                        ast_bounds: &[hir::TyParamBound],
+                                        sized_by_default: SizedByDefault,
+                                        anon_scope: Option<AnonTypeScope>,
+                                        span: Span)
+                                        -> Bounds<'tcx>
 {
-    let mut bounds =
-        conv_param_bounds(astconv,
-                          span,
-                          param_ty,
-                          ast_bounds);
+    let tcx = astconv.tcx();
+    let PartitionedBounds {
+        mut builtin_bounds,
+        trait_bounds,
+        region_bounds
+    } = partition_bounds(tcx, span, &ast_bounds);
 
     if let SizedByDefault::Yes = sized_by_default {
-        add_unsized_bound(astconv,
-                          &mut bounds.builtin_bounds,
-                          ast_bounds,
-                          span);
+        add_unsized_bound(astconv, &mut builtin_bounds, ast_bounds, span);
     }
 
-    bounds.trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
+    let mut projection_bounds = vec![];
 
-    bounds
+    let rscope = MaybeWithAnonTypes::new(ExplicitRscope, anon_scope);
+    let mut trait_bounds: Vec<_> = trait_bounds.iter().map(|&bound| {
+        astconv.instantiate_poly_trait_ref(&rscope,
+                                           bound,
+                                           Some(param_ty),
+                                           &mut projection_bounds)
+    }).collect();
+
+    let region_bounds = region_bounds.into_iter().map(|r| {
+        ast_region_to_region(tcx, r)
+    }).collect();
+
+    trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
+
+    Bounds {
+        region_bounds: region_bounds,
+        builtin_bounds: builtin_bounds,
+        trait_bounds: trait_bounds,
+        projection_bounds: projection_bounds,
+    }
 }
 
 /// Converts a specific TyParamBound from the AST into a set of
@@ -2098,11 +2124,11 @@ fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx, 'tcx>,
     }
 }
 
-fn conv_poly_trait_ref<'tcx>(astconv: &AstConv<'tcx, 'tcx>,
-                             param_ty: Ty<'tcx>,
-                             trait_ref: &hir::PolyTraitRef,
-                             projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
-                             -> ty::PolyTraitRef<'tcx>
+fn conv_poly_trait_ref<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
+                                         param_ty: Ty<'tcx>,
+                                         trait_ref: &hir::PolyTraitRef,
+                                         projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
+                                         -> ty::PolyTraitRef<'tcx>
 {
     AstConv::instantiate_poly_trait_ref(astconv,
                                         &ExplicitRscope,
@@ -2111,42 +2137,6 @@ fn conv_poly_trait_ref<'tcx>(astconv: &AstConv<'tcx, 'tcx>,
                                         projections)
 }
 
-fn conv_param_bounds<'a,'tcx>(astconv: &AstConv<'tcx, 'tcx>,
-                              span: Span,
-                              param_ty: ty::Ty<'tcx>,
-                              ast_bounds: &[hir::TyParamBound])
-                              -> Bounds<'tcx>
-{
-    let tcx = astconv.tcx();
-    let PartitionedBounds {
-        builtin_bounds,
-        trait_bounds,
-        region_bounds
-    } = partition_bounds(tcx, span, &ast_bounds);
-
-    let mut projection_bounds = Vec::new();
-
-    let trait_bounds: Vec<ty::PolyTraitRef> =
-        trait_bounds.iter()
-                    .map(|bound| conv_poly_trait_ref(astconv,
-                                                     param_ty,
-                                                     *bound,
-                                                     &mut projection_bounds))
-                    .collect();
-
-    let region_bounds: Vec<ty::Region> =
-        region_bounds.into_iter()
-                     .map(|r| ast_region_to_region(tcx, r))
-                     .collect();
-
-    Bounds {
-        region_bounds: region_bounds,
-        builtin_bounds: builtin_bounds,
-        trait_bounds: trait_bounds,
-        projection_bounds: projection_bounds,
-    }
-}
-
 fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
     ccx: &CrateCtxt<'a, 'tcx>,
     id: DefId,
@@ -2194,7 +2184,7 @@ fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
         }
     }
 
-    let substs = mk_item_substs(ccx, &ty_generics);
+    let substs = mk_item_substs(ccx.tcx, &ty_generics);
     let t_fn = ccx.tcx.mk_fn_def(id, substs, ccx.tcx.mk_bare_fn(ty::BareFnTy {
         abi: abi,
         unsafety: hir::Unsafety::Unsafe,
@@ -2209,19 +2199,19 @@ fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
     }
 }
 
-fn mk_item_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
-                            ty_generics: &ty::Generics<'tcx>)
-                            -> &'tcx Substs<'tcx>
+pub fn mk_item_substs<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
+                                      ty_generics: &ty::Generics)
+                                      -> &'tcx Substs<'tcx>
 {
     let types =
         ty_generics.types.map(
-            |def| ccx.tcx.mk_param_from_def(def));
+            |def| tcx.mk_param_from_def(def));
 
     let regions =
         ty_generics.regions.map(
             |def| def.to_early_bound_region());
 
-    ccx.tcx.mk_substs(Substs::new(types, regions))
+    tcx.mk_substs(Substs::new(types, regions))
 }
 
 /// Checks that all the type parameters on an impl
diff --git a/src/librustc_typeck/constrained_type_params.rs b/src/librustc_typeck/constrained_type_params.rs
index 7909584bfab..7d3bd095a3a 100644
--- a/src/librustc_typeck/constrained_type_params.rs
+++ b/src/librustc_typeck/constrained_type_params.rs
@@ -45,7 +45,7 @@ struct ParameterCollector {
 impl<'tcx> TypeVisitor<'tcx> for ParameterCollector {
     fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
         match t.sty {
-            ty::TyProjection(..) if !self.include_nonconstraining => {
+            ty::TyProjection(..) | ty::TyAnon(..) if !self.include_nonconstraining => {
                 // projections are not injective
                 return false;
             }
diff --git a/src/librustc_typeck/diagnostics.rs b/src/librustc_typeck/diagnostics.rs
index 64b27857d2c..7b78e83b801 100644
--- a/src/librustc_typeck/diagnostics.rs
+++ b/src/librustc_typeck/diagnostics.rs
@@ -4084,4 +4084,9 @@ register_diagnostics! {
     E0513, // no type for local variable ..
     E0521, // redundant default implementations of trait
     E0533, // `{}` does not name a unit variant, unit struct or a constant
+    E0562, // `impl Trait` not allowed outside of function
+           // and inherent method return types
+    E0563, // cannot determine a type for this `impl Trait`: {}
+    E0564, // only named lifetimes are allowed in `impl Trait`,
+           // but `{}` was found in the type `{}`
 }
diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs
index a31961a157b..0dd4bc41439 100644
--- a/src/librustc_typeck/lib.rs
+++ b/src/librustc_typeck/lib.rs
@@ -107,7 +107,7 @@ use hir::map as hir_map;
 use rustc::infer::TypeOrigin;
 use rustc::ty::subst::Substs;
 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
-use rustc::traits::ProjectionMode;
+use rustc::traits::{self, Reveal};
 use session::{config, CompileResult};
 use util::common::time;
 
@@ -150,6 +150,11 @@ pub struct CrateCtxt<'a, 'tcx: 'a> {
     pub stack: RefCell<Vec<collect::AstConvRequest>>,
 
     pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
+
+    /// Obligations which will have to be checked at the end of
+    /// type-checking, after all functions have been inferred.
+    /// The key is the NodeId of the item the obligations were from.
+    pub deferred_obligations: RefCell<NodeMap<Vec<traits::DeferredObligation<'tcx>>>>,
 }
 
 // Functions that write types into the node type table
@@ -190,7 +195,7 @@ fn require_same_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                 t1: Ty<'tcx>,
                                 t2: Ty<'tcx>)
                                 -> bool {
-    ccx.tcx.infer_ctxt(None, None, ProjectionMode::AnyFinal).enter(|infcx| {
+    ccx.tcx.infer_ctxt(None, None, Reveal::NotSpecializable).enter(|infcx| {
         if let Err(err) = infcx.eq_types(false, origin.clone(), t1, t2) {
             infcx.report_mismatched_types(origin, t1, t2, err);
             false
@@ -328,7 +333,8 @@ pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>)
         ast_ty_to_ty_cache: RefCell::new(NodeMap()),
         all_traits: RefCell::new(None),
         stack: RefCell::new(Vec::new()),
-        tcx: tcx
+        tcx: tcx,
+        deferred_obligations: RefCell::new(NodeMap()),
     };
 
     // this ensures that later parts of type checking can assume that items
diff --git a/src/librustc_typeck/rscope.rs b/src/librustc_typeck/rscope.rs
index 336a6170868..58d1ec9d02a 100644
--- a/src/librustc_typeck/rscope.rs
+++ b/src/librustc_typeck/rscope.rs
@@ -9,7 +9,8 @@
 // except according to those terms.
 
 
-use rustc::ty;
+use rustc::ty::{self, TyCtxt};
+use rustc::ty::subst::Substs;
 
 use std::cell::Cell;
 use syntax_pos::Span;
@@ -50,6 +51,79 @@ pub trait RegionScope {
     /// computing `object_lifetime_default` (in particular, in legacy
     /// modes, it may not be relevant).
     fn base_object_lifetime_default(&self, span: Span) -> ty::Region;
+
+    /// If this scope allows anonymized types, return the generics in
+    /// scope, that anonymized types will close over. For example,
+    /// if you have a function like:
+    ///
+    ///     fn foo<'a, T>() -> impl Trait { ... }
+    ///
+    /// then, for the rscope that is used when handling the return type,
+    /// `anon_type_scope()` would return a `Some(AnonTypeScope {...})`,
+    /// on which `.fresh_substs(...)` can be used to obtain identity
+    /// Substs for `'a` and `T`, to track them in `TyAnon`. This property
+    /// is controlled by the region scope because it's fine-grained enough
+    /// to allow restriction of anonymized types to the syntactical extent
+    /// of a function's return type.
+    fn anon_type_scope(&self) -> Option<AnonTypeScope> {
+        None
+    }
+}
+
+#[derive(Copy, Clone)]
+pub struct AnonTypeScope<'a> {
+    generics: &'a ty::Generics<'a>
+}
+
+impl<'a, 'b, 'gcx, 'tcx> AnonTypeScope<'a> {
+    pub fn new(generics: &'a ty::Generics<'a>) -> AnonTypeScope<'a> {
+        AnonTypeScope {
+            generics: generics
+        }
+    }
+
+    pub fn fresh_substs(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> &'tcx Substs<'tcx> {
+        use collect::mk_item_substs;
+
+        mk_item_substs(tcx, self.generics)
+    }
+}
+
+/// A scope wrapper which optionally allows anonymized types.
+#[derive(Copy, Clone)]
+pub struct MaybeWithAnonTypes<'a, R> {
+    base_scope: R,
+    anon_scope: Option<AnonTypeScope<'a>>
+}
+
+impl<'a, R: RegionScope> MaybeWithAnonTypes<'a, R>  {
+    pub fn new(base_scope: R, anon_scope: Option<AnonTypeScope<'a>>) -> Self {
+        MaybeWithAnonTypes {
+            base_scope: base_scope,
+            anon_scope: anon_scope
+        }
+    }
+}
+
+impl<'a, R: RegionScope> RegionScope for MaybeWithAnonTypes<'a, R> {
+    fn object_lifetime_default(&self, span: Span) -> Option<ty::Region> {
+        self.base_scope.object_lifetime_default(span)
+    }
+
+    fn anon_regions(&self,
+                    span: Span,
+                    count: usize)
+                    -> Result<Vec<ty::Region>, Option<Vec<ElisionFailureInfo>>> {
+        self.base_scope.anon_regions(span, count)
+    }
+
+    fn base_object_lifetime_default(&self, span: Span) -> ty::Region {
+        self.base_scope.base_object_lifetime_default(span)
+    }
+
+    fn anon_type_scope(&self) -> Option<AnonTypeScope> {
+        self.anon_scope
+    }
 }
 
 // A scope in which all regions must be explicitly named. This is used
@@ -221,6 +295,10 @@ impl<'r> RegionScope for ObjectLifetimeDefaultRscope<'r> {
     {
         self.base_scope.anon_regions(span, count)
     }
+
+    fn anon_type_scope(&self) -> Option<AnonTypeScope> {
+        self.base_scope.anon_type_scope()
+    }
 }
 
 /// A scope which simply shifts the Debruijn index of other scopes
@@ -262,4 +340,8 @@ impl<'r> RegionScope for ShiftedRscope<'r> {
             }
         }
     }
+
+    fn anon_type_scope(&self) -> Option<AnonTypeScope> {
+        self.base_scope.anon_type_scope()
+    }
 }
diff --git a/src/librustc_typeck/variance/constraints.rs b/src/librustc_typeck/variance/constraints.rs
index 01a310da25d..b9e0b4a10ea 100644
--- a/src/librustc_typeck/variance/constraints.rs
+++ b/src/librustc_typeck/variance/constraints.rs
@@ -326,7 +326,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
                 /* leaf type -- noop */
             }
 
-            ty::TyClosure(..) => {
+            ty::TyClosure(..) | ty::TyAnon(..) => {
                 bug!("Unexpected closure type in variance computation");
             }
 
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index 26ea4890b30..73bc647fa9f 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -1492,6 +1492,9 @@ pub enum Type {
 
     // for<'a> Foo(&'a)
     PolyTraitRef(Vec<TyParamBound>),
+
+    // impl TraitA+TraitB
+    ImplTrait(Vec<TyParamBound>),
 }
 
 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Copy, Debug)]
@@ -1777,6 +1780,7 @@ impl Clean<Type> for hir::Ty {
             }
             TyBareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
             TyPolyTraitRef(ref bounds) => PolyTraitRef(bounds.clean(cx)),
+            TyImplTrait(ref bounds) => ImplTrait(bounds.clean(cx)),
             TyInfer => Infer,
             TyTypeof(..) => panic!("Unimplemented type {:?}", self.node),
         }
@@ -1863,6 +1867,18 @@ impl<'tcx> Clean<Type> for ty::Ty<'tcx> {
 
             ty::TyParam(ref p) => Generic(p.name.to_string()),
 
+            ty::TyAnon(def_id, substs) => {
+                // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
+                // by looking up the projections associated with the def_id.
+                let item_predicates = cx.tcx().lookup_predicates(def_id);
+                let substs = cx.tcx().lift(&substs).unwrap();
+                let bounds = item_predicates.instantiate(cx.tcx(), substs);
+                let predicates = bounds.predicates.into_vec();
+                ImplTrait(predicates.into_iter().filter_map(|predicate| {
+                    predicate.to_opt_poly_trait_ref().clean(cx)
+                }).collect())
+            }
+
             ty::TyClosure(..) => Tuple(vec![]), // FIXME(pcwalton)
 
             ty::TyInfer(..) => panic!("TyInfer"),
diff --git a/src/librustdoc/html/format.rs b/src/librustdoc/html/format.rs
index eed2615175b..854ca57e855 100644
--- a/src/librustdoc/html/format.rs
+++ b/src/librustdoc/html/format.rs
@@ -539,6 +539,16 @@ impl fmt::Display for clean::Type {
                 }
                 Ok(())
             }
+            clean::ImplTrait(ref bounds) => {
+                write!(f, "impl ")?;
+                for (i, bound) in bounds.iter().enumerate() {
+                    if i != 0 {
+                        write!(f, " + ")?;
+                    }
+                    write!(f, "{}", *bound)?;
+                }
+                Ok(())
+            }
             // It's pretty unsightly to look at `<A as B>::C` in output, and
             // we've got hyperlinking on our side, so try to avoid longer
             // notation as much as possible by making `C` a hyperlink to trait
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index a8bb255fba4..3f929e6d23a 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -1368,6 +1368,8 @@ pub enum TyKind {
     ObjectSum(P<Ty>, TyParamBounds),
     /// A type like `for<'a> Foo<&'a Bar>`
     PolyTraitRef(TyParamBounds),
+    /// An `impl TraitA+TraitB` type.
+    ImplTrait(TyParamBounds),
     /// No-op; kept solely so that we can pretty-print faithfully
     Paren(P<Ty>),
     /// Unused for now
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index 29da0fb1a27..f550e7d2a05 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -277,7 +277,10 @@ declare_features! (
     (active, cfg_target_has_atomic, "1.9.0", Some(32976)),
 
     // Allows `..` in tuple (struct) patterns
-    (active, dotdot_in_tuple_patterns, "1.10.0", Some(33627))
+    (active, dotdot_in_tuple_patterns, "1.10.0", Some(33627)),
+
+    // Allows `impl Trait` in function return types.
+    (active, conservative_impl_trait, "1.12.0", Some(34511))
 );
 
 declare_features! (
@@ -952,6 +955,10 @@ impl<'a> Visitor for PostExpansionVisitor<'a> {
             ast::TyKind::BareFn(ref bare_fn_ty) => {
                 self.check_abi(bare_fn_ty.abi, ty.span);
             }
+            ast::TyKind::ImplTrait(..) => {
+                gate_feature_post!(&self, conservative_impl_trait, ty.span,
+                                   "`impl Trait` is experimental");
+            }
             _ => {}
         }
         visit::walk_ty(self, ty)
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index ac3d643b185..afc990f498e 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -397,6 +397,9 @@ pub fn noop_fold_ty<T: Folder>(t: P<Ty>, fld: &mut T) -> P<Ty> {
             TyKind::PolyTraitRef(bounds) => {
                 TyKind::PolyTraitRef(bounds.move_map(|b| fld.fold_ty_param_bound(b)))
             }
+            TyKind::ImplTrait(bounds) => {
+                TyKind::ImplTrait(bounds.move_map(|b| fld.fold_ty_param_bound(b)))
+            }
             TyKind::Mac(mac) => {
                 TyKind::Mac(fld.fold_mac(mac))
             }
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index c143e190c6f..1b32632a06f 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -1051,7 +1051,7 @@ impl<'a> Parser<'a> {
     pub fn parse_for_in_type(&mut self) -> PResult<'a, TyKind> {
         /*
         Parses whatever can come after a `for` keyword in a type.
-        The `for` has already been consumed.
+        The `for` hasn't been consumed.
 
         Deprecated:
 
@@ -1091,6 +1091,23 @@ impl<'a> Parser<'a> {
         }
     }
 
+    pub fn parse_impl_trait_type(&mut self) -> PResult<'a, TyKind> {
+        /*
+        Parses whatever can come after a `impl` keyword in a type.
+        The `impl` has already been consumed.
+        */
+
+        let bounds = self.parse_ty_param_bounds(BoundParsingMode::Modified)?;
+
+        if !bounds.iter().any(|b| if let TraitTyParamBound(..) = *b { true } else { false }) {
+            let last_span = self.last_span;
+            self.span_err(last_span, "at least one trait must be specified");
+        }
+
+        Ok(ast::TyKind::ImplTrait(bounds))
+    }
+
+
     pub fn parse_ty_path(&mut self) -> PResult<'a, TyKind> {
         Ok(TyKind::Path(None, self.parse_path(PathStyle::Type)?))
     }
@@ -1406,6 +1423,8 @@ impl<'a> Parser<'a> {
             self.parse_borrowed_pointee()?
         } else if self.check_keyword(keywords::For) {
             self.parse_for_in_type()?
+        } else if self.eat_keyword(keywords::Impl) {
+            self.parse_impl_trait_type()?
         } else if self.token_is_bare_fn_keyword() {
             // BARE FUNCTION
             self.parse_ty_bare_fn(Vec::new())?
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index a619da84b2d..62e55eb78b7 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -1018,6 +1018,9 @@ impl<'a> State<'a> {
             ast::TyKind::PolyTraitRef(ref bounds) => {
                 try!(self.print_bounds("", &bounds[..]));
             }
+            ast::TyKind::ImplTrait(ref bounds) => {
+                try!(self.print_bounds("impl ", &bounds[..]));
+            }
             ast::TyKind::FixedLengthVec(ref ty, ref v) => {
                 try!(word(&mut self.s, "["));
                 try!(self.print_type(&ty));
diff --git a/src/libsyntax/visit.rs b/src/libsyntax/visit.rs
index 1fc4e54d218..6d3cdbdc6da 100644
--- a/src/libsyntax/visit.rs
+++ b/src/libsyntax/visit.rs
@@ -343,6 +343,9 @@ pub fn walk_ty<V: Visitor>(visitor: &mut V, typ: &Ty) {
         TyKind::PolyTraitRef(ref bounds) => {
             walk_list!(visitor, visit_ty_param_bound, bounds);
         }
+        TyKind::ImplTrait(ref bounds) => {
+            walk_list!(visitor, visit_ty_param_bound, bounds);
+        }
         TyKind::Typeof(ref expression) => {
             visitor.visit_expr(expression)
         }
diff --git a/src/test/compile-fail/impl-trait/auto-trait-leak.rs b/src/test/compile-fail/impl-trait/auto-trait-leak.rs
new file mode 100644
index 00000000000..2c78ce2db29
--- /dev/null
+++ b/src/test/compile-fail/impl-trait/auto-trait-leak.rs
@@ -0,0 +1,70 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// ignore-tidy-linelength
+
+#![feature(conservative_impl_trait)]
+
+use std::cell::Cell;
+use std::rc::Rc;
+
+// Fast path, main can see the concrete type returned.
+fn before() -> impl Fn(i32) {
+    let p = Rc::new(Cell::new(0));
+    move |x| p.set(x)
+}
+
+fn send<T: Send>(_: T) {}
+
+fn main() {
+    send(before());
+    //~^ ERROR the trait bound `std::rc::Rc<std::cell::Cell<i32>>: std::marker::Send` is not satisfied
+    //~| NOTE `std::rc::Rc<std::cell::Cell<i32>>` cannot be sent between threads safely
+    //~| NOTE required because it appears within the type `[closure
+    //~| NOTE required because it appears within the type `impl std::ops::Fn<(i32,)>`
+    //~| NOTE required by `send`
+
+    send(after());
+    //~^ ERROR the trait bound `std::rc::Rc<std::cell::Cell<i32>>: std::marker::Send` is not satisfied
+    //~| NOTE `std::rc::Rc<std::cell::Cell<i32>>` cannot be sent between threads safely
+    //~| NOTE required because it appears within the type `[closure
+    //~| NOTE required because it appears within the type `impl std::ops::Fn<(i32,)>`
+    //~| NOTE required by `send`
+}
+
+// Deferred path, main has to wait until typeck finishes,
+// to check if the return type of after is Send.
+fn after() -> impl Fn(i32) {
+    let p = Rc::new(Cell::new(0));
+    move |x| p.set(x)
+}
+
+// Cycles should work as the deferred obligations are
+// independently resolved and only require the concrete
+// return type, which can't depend on the obligation.
+fn cycle1() -> impl Clone {
+    send(cycle2().clone());
+    //~^ ERROR the trait bound `std::rc::Rc<std::string::String>: std::marker::Send` is not satisfied
+    //~| NOTE `std::rc::Rc<std::string::String>` cannot be sent between threads safely
+    //~| NOTE required because it appears within the type `impl std::clone::Clone`
+    //~| NOTE required by `send`
+
+    Rc::new(Cell::new(5))
+}
+
+fn cycle2() -> impl Clone {
+    send(cycle1().clone());
+    //~^ ERROR the trait bound `std::rc::Rc<std::cell::Cell<i32>>: std::marker::Send` is not satisfied
+    //~| NOTE `std::rc::Rc<std::cell::Cell<i32>>` cannot be sent between threads safely
+    //~| NOTE required because it appears within the type `impl std::clone::Clone`
+    //~| NOTE required by `send`
+
+    Rc::new(String::from("foo"))
+}
diff --git a/src/test/compile-fail/impl-trait/disallowed-2.rs b/src/test/compile-fail/impl-trait/disallowed-2.rs
new file mode 100644
index 00000000000..46b3106ab8d
--- /dev/null
+++ b/src/test/compile-fail/impl-trait/disallowed-2.rs
@@ -0,0 +1,18 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(conservative_impl_trait)]
+
+fn main() {
+    let _: impl Fn() = || {};
+    //~^ ERROR `impl Trait` not allowed outside of function and inherent method return types
+    let _ = || -> impl Fn() { || {} };
+    //~^ ERROR `impl Trait` not allowed outside of function and inherent method return types
+}
diff --git a/src/test/compile-fail/impl-trait/disallowed.rs b/src/test/compile-fail/impl-trait/disallowed.rs
new file mode 100644
index 00000000000..09aba5d8c91
--- /dev/null
+++ b/src/test/compile-fail/impl-trait/disallowed.rs
@@ -0,0 +1,61 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(conservative_impl_trait)]
+
+fn arguments(_: impl Fn(),
+//~^ ERROR `impl Trait` not allowed outside of function and inherent method return types
+             _: Vec<impl Clone>) {}
+//~^ ERROR `impl Trait` not allowed outside of function and inherent method return types
+
+type Factory<R> = impl Fn() -> R;
+//~^ ERROR `impl Trait` not allowed outside of function and inherent method return types
+
+type GlobalFactory<R> = fn() -> impl FnOnce() -> R;
+//~^ ERROR `impl Trait` not allowed outside of function and inherent method return types
+
+trait LazyToString {
+    fn lazy_to_string<'a>(&'a self) -> impl Fn() -> String;
+    //~^ ERROR `impl Trait` not allowed outside of function and inherent method return types
+}
+
+// Note that the following impl doesn't error, because the trait is invalid.
+impl LazyToString for String {
+    fn lazy_to_string<'a>(&'a self) -> impl Fn() -> String {
+        || self.clone()
+    }
+}
+
+#[derive(Copy, Clone)]
+struct Lazy<T>(T);
+
+impl std::ops::Add<Lazy<i32>> for Lazy<i32> {
+    type Output = impl Fn() -> Lazy<i32>;
+    //~^ ERROR `impl Trait` not allowed outside of function and inherent method return types
+
+    fn add(self, other: Lazy<i32>) -> Self::Output {
+        move || Lazy(self.0 + other.0)
+    }
+}
+
+impl<F> std::ops::Add<F>
+for impl Fn() -> Lazy<i32>
+//~^ ERROR `impl Trait` not allowed outside of function and inherent method return types
+where F: Fn() -> impl FnOnce() -> i32
+//~^ ERROR `impl Trait` not allowed outside of function and inherent method return types
+{
+    type Output = Self;
+
+    fn add(self, other: F) -> Self::Output {
+        move || Lazy(self().0 + other()())
+    }
+}
+
+fn main() {}
diff --git a/src/test/compile-fail/impl-trait/equality.rs b/src/test/compile-fail/impl-trait/equality.rs
new file mode 100644
index 00000000000..59ad1132b35
--- /dev/null
+++ b/src/test/compile-fail/impl-trait/equality.rs
@@ -0,0 +1,89 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(conservative_impl_trait, specialization)]
+
+trait Foo: Copy + ToString {}
+
+impl<T: Copy + ToString> Foo for T {}
+
+fn hide<T: Foo>(x: T) -> impl Foo {
+    x
+}
+
+fn two(x: bool) -> impl Foo {
+    if x {
+        return 1_i32;
+    }
+    0_u32
+    //~^ ERROR mismatched types
+    //~| expected i32, found u32
+}
+
+fn sum_to(n: u32) -> impl Foo {
+    if n == 0 {
+        0
+    } else {
+        n + sum_to(n - 1)
+        //~^ ERROR the trait bound `u32: std::ops::Add<impl Foo>` is not satisfied
+    }
+}
+
+trait Leak: Sized {
+    type T;
+    fn leak(self) -> Self::T;
+}
+impl<T> Leak for T {
+    default type T = ();
+    default fn leak(self) -> Self::T { panic!() }
+}
+impl Leak for i32 {
+    type T = i32;
+    fn leak(self) -> i32 { self }
+}
+
+trait CheckIfSend: Sized {
+    type T: Default;
+    fn check(self) -> Self::T { Default::default() }
+}
+impl<T> CheckIfSend for T {
+    default type T = ();
+}
+impl<T: Send> CheckIfSend for T {
+    type T = bool;
+}
+
+fn main() {
+    let _: u32 = hide(0_u32);
+    //~^ ERROR mismatched types
+    //~| expected type `u32`
+    //~| found type `impl Foo`
+    //~| expected u32, found anonymized type
+
+    let _: i32 = Leak::leak(hide(0_i32));
+    //~^ ERROR mismatched types
+    //~| expected type `i32`
+    //~| found type `<impl Foo as Leak>::T`
+    //~| expected i32, found associated type
+
+    let _: bool = CheckIfSend::check(hide(0_i32));
+    //~^ ERROR mismatched types
+    //~| expected type `bool`
+    //~| found type `<impl Foo as CheckIfSend>::T`
+    //~| expected bool, found associated type
+
+    let mut x = (hide(0_u32), hide(0_i32));
+    x = (x.1,
+    //~^ ERROR mismatched types
+    //~| expected u32, found i32
+         x.0);
+    //~^ ERROR mismatched types
+    //~| expected i32, found u32
+}
diff --git a/src/test/compile-fail/impl-trait/feature-gate.rs b/src/test/compile-fail/impl-trait/feature-gate.rs
new file mode 100644
index 00000000000..8239b06f2b4
--- /dev/null
+++ b/src/test/compile-fail/impl-trait/feature-gate.rs
@@ -0,0 +1,14 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+fn foo() -> impl Fn() { || {} }
+//~^ ERROR `impl Trait` is experimental
+
+fn main() {}
diff --git a/src/test/compile-fail/impl-trait/lifetimes.rs b/src/test/compile-fail/impl-trait/lifetimes.rs
new file mode 100644
index 00000000000..9d9f6bf7297
--- /dev/null
+++ b/src/test/compile-fail/impl-trait/lifetimes.rs
@@ -0,0 +1,43 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(conservative_impl_trait)]
+
+// Helper creating a fake borrow, captured by the impl Trait.
+fn borrow<'a, T>(_: &'a mut T) -> impl Copy { () }
+
+fn stack() -> impl Copy {
+    //~^ ERROR only named lifetimes are allowed in `impl Trait`
+    let x = 0;
+    &x
+}
+
+fn late_bound(x: &i32) -> impl Copy {
+    //~^ ERROR only named lifetimes are allowed in `impl Trait`
+    x
+}
+
+// FIXME(#34511) Should work but doesn't at the moment,
+// region-checking needs an overhault to support this.
+fn early_bound<'a>(x: &'a i32) -> impl Copy {
+    //~^ ERROR only named lifetimes are allowed in `impl Trait`
+    x
+}
+
+fn ambiguous<'a, 'b>(x: &'a [u32], y: &'b [u32]) -> impl Iterator<Item=u32> {
+    //~^ ERROR only named lifetimes are allowed in `impl Trait`
+    if x.len() < y.len() {
+        x.iter().cloned()
+    } else {
+        y.iter().cloned()
+    }
+}
+
+fn main() {}
diff --git a/src/test/compile-fail/impl-trait/loan-extend.rs b/src/test/compile-fail/impl-trait/loan-extend.rs
new file mode 100644
index 00000000000..ceaa8f4eed7
--- /dev/null
+++ b/src/test/compile-fail/impl-trait/loan-extend.rs
@@ -0,0 +1,23 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(conservative_impl_trait)]
+
+// Helper creating a fake borrow, captured by the impl Trait.
+fn borrow<'a, T>(_: &'a mut T) -> impl Copy { () }
+
+fn main() {
+    //~^ NOTE reference must be valid for the block
+    let long;
+    let mut short = 0;
+    //~^ NOTE but borrowed value is only valid for the block suffix following statement 1
+    long = borrow(&mut short);
+    //~^ ERROR `short` does not live long enough
+}
diff --git a/src/test/compile-fail/transmute-different-sizes.rs b/src/test/compile-fail/transmute-different-sizes.rs
index df87a7bbdc9..5fab271efce 100644
--- a/src/test/compile-fail/transmute-different-sizes.rs
+++ b/src/test/compile-fail/transmute-different-sizes.rs
@@ -11,6 +11,7 @@
 // Tests that `transmute` cannot be called on types of different size.
 
 #![allow(warnings)]
+#![feature(specialization)]
 
 use std::mem::transmute;
 
@@ -24,4 +25,15 @@ unsafe fn g<T>(x: &T) {
     //~^ ERROR transmute called with differently sized types
 }
 
+trait Specializable { type Output; }
+
+impl<T> Specializable for T {
+    default type Output = u16;
+}
+
+unsafe fn specializable<T>(x: u16) -> <T as Specializable>::Output {
+    transmute(x)
+    //~^ ERROR transmute called with differently sized types
+}
+
 fn main() {}
diff --git a/src/test/run-pass/impl-trait/auto-trait-leak.rs b/src/test/run-pass/impl-trait/auto-trait-leak.rs
new file mode 100644
index 00000000000..c1201e7fa4f
--- /dev/null
+++ b/src/test/run-pass/impl-trait/auto-trait-leak.rs
@@ -0,0 +1,44 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(conservative_impl_trait)]
+
+// Fast path, main can see the concrete type returned.
+fn before() -> impl FnMut(i32) {
+    let mut p = Box::new(0);
+    move |x| *p = x
+}
+
+fn send<T: Send>(_: T) {}
+
+fn main() {
+    send(before());
+    send(after());
+}
+
+// Deferred path, main has to wait until typeck finishes,
+// to check if the return type of after is Send.
+fn after() -> impl FnMut(i32) {
+    let mut p = Box::new(0);
+    move |x| *p = x
+}
+
+// Cycles should work as the deferred obligations are
+// independently resolved and only require the concrete
+// return type, which can't depend on the obligation.
+fn cycle1() -> impl Clone {
+    send(cycle2().clone());
+    5
+}
+
+fn cycle2() -> impl Clone {
+    send(cycle1().clone());
+    String::from("foo")
+}
diff --git a/src/test/run-pass/impl-trait/equality.rs b/src/test/run-pass/impl-trait/equality.rs
new file mode 100644
index 00000000000..72b0e588ff4
--- /dev/null
+++ b/src/test/run-pass/impl-trait/equality.rs
@@ -0,0 +1,43 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(conservative_impl_trait, specialization)]
+
+trait Foo: std::fmt::Debug + Eq {}
+
+impl<T: std::fmt::Debug + Eq> Foo for T {}
+
+fn hide<T: Foo>(x: T) -> impl Foo {
+    x
+}
+
+trait Leak<T>: Sized {
+    fn leak(self) -> T;
+}
+impl<T, U> Leak<T> for U {
+    default fn leak(self) -> T { panic!("type mismatch") }
+}
+impl<T> Leak<T> for T {
+    fn leak(self) -> T { self }
+}
+
+fn lucky_seven() -> impl Fn(usize) -> u8 {
+    let a = [1, 2, 3, 4, 5, 6, 7];
+    move |i| a[i]
+}
+
+fn main() {
+    assert_eq!(hide(42), hide(42));
+
+    assert_eq!(std::mem::size_of_val(&hide([0_u8; 5])), 5);
+    assert_eq!(std::mem::size_of_val(&lucky_seven()), 7);
+
+    assert_eq!(Leak::<i32>::leak(hide(5_i32)), 5_i32);
+}
diff --git a/src/test/run-pass/impl-trait/example-calendar.rs b/src/test/run-pass/impl-trait/example-calendar.rs
new file mode 100644
index 00000000000..2a9af26881c
--- /dev/null
+++ b/src/test/run-pass/impl-trait/example-calendar.rs
@@ -0,0 +1,929 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(conservative_impl_trait, fn_traits, step_trait, unboxed_closures)]
+
+//! Derived from: <https://raw.githubusercontent.com/quickfur/dcal/master/dcal.d>.
+//!
+//! Originally converted to Rust by [Daniel Keep](https://github.com/DanielKeep).
+
+use std::fmt::Write;
+use std::mem;
+
+/// Date representation.
+#[derive(Copy, Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
+struct NaiveDate(i32, u32, u32);
+
+impl NaiveDate {
+    pub fn from_ymd(y: i32, m: u32, d: u32) -> NaiveDate {
+        assert!(1 <= m && m <= 12, "m = {:?}", m);
+        assert!(1 <= d && d <= NaiveDate(y, m, 1).days_in_month(), "d = {:?}", d);
+        NaiveDate(y, m, d)
+    }
+
+    pub fn year(&self) -> i32 {
+        self.0
+    }
+
+    pub fn month(&self) -> u32 {
+        self.1
+    }
+
+    pub fn day(&self) -> u32 {
+        self.2
+    }
+
+    pub fn succ(&self) -> NaiveDate {
+        let (mut y, mut m, mut d, n) = (
+            self.year(), self.month(), self.day()+1, self.days_in_month());
+        if d > n {
+            d = 1;
+            m += 1;
+        }
+        if m > 12 {
+            m = 1;
+            y += 1;
+        }
+        NaiveDate::from_ymd(y, m, d)
+    }
+
+    pub fn weekday(&self) -> Weekday {
+        use Weekday::*;
+
+        // 0 = Sunday
+        let year = self.year();
+        let dow_jan_1 = (year*365 + ((year-1) / 4) - ((year-1) / 100) + ((year-1) / 400)) % 7;
+        let dow = (dow_jan_1 + (self.day_of_year() as i32 - 1)) % 7;
+        [Sun, Mon, Tue, Wed, Thu, Fri, Sat][dow as usize]
+    }
+
+    pub fn isoweekdate(&self) -> (i32, u32, Weekday) {
+        let first_dow_mon_0 = self.year_first_day_of_week().num_days_from_monday();
+
+        // Work out this date's DOtY and week number, not including year adjustment.
+        let doy_0 = self.day_of_year() - 1;
+        let mut week_mon_0: i32 = ((first_dow_mon_0 + doy_0) / 7) as i32;
+
+        if self.first_week_in_prev_year() {
+            week_mon_0 -= 1;
+        }
+
+        let weeks_in_year = self.last_week_number();
+
+        // Work out the final result.
+        // If the week is -1 or >= weeks_in_year, we will need to adjust the year.
+        let year = self.year();
+        let wd = self.weekday();
+
+        if week_mon_0 < 0 {
+            (year - 1, NaiveDate::from_ymd(year - 1, 1, 1).last_week_number(), wd)
+        } else if week_mon_0 >= weeks_in_year as i32 {
+            (year + 1, (week_mon_0 + 1 - weeks_in_year as i32) as u32, wd)
+        } else {
+            (year, (week_mon_0 + 1) as u32, wd)
+        }
+    }
+
+    fn first_week_in_prev_year(&self) -> bool {
+        let first_dow_mon_0 = self.year_first_day_of_week().num_days_from_monday();
+
+        // Any day in the year *before* the first Monday of that year
+        // is considered to be in the last week of the previous year,
+        // assuming the first week has *less* than four days in it.
+        // Adjust the week appropriately.
+        ((7 - first_dow_mon_0) % 7) < 4
+    }
+
+    fn year_first_day_of_week(&self) -> Weekday {
+        NaiveDate::from_ymd(self.year(), 1, 1).weekday()
+    }
+
+    fn weeks_in_year(&self) -> u32 {
+        let days_in_last_week = self.year_first_day_of_week().num_days_from_monday() + 1;
+        if days_in_last_week >= 4 { 53 } else { 52 }
+    }
+
+    fn last_week_number(&self) -> u32 {
+        let wiy = self.weeks_in_year();
+        if self.first_week_in_prev_year() { wiy - 1 } else { wiy }
+    }
+
+    fn day_of_year(&self) -> u32 {
+        (1..self.1).map(|m| NaiveDate::from_ymd(self.year(), m, 1).days_in_month())
+            .fold(0, |a,b| a+b) + self.day()
+    }
+
+    fn is_leap_year(&self) -> bool {
+        let year = self.year();
+        if year % 4 != 0 {
+            return false
+        } else if year % 100 != 0 {
+            return true
+        } else if year % 400 != 0 {
+            return false
+        } else {
+            return true
+        }
+    }
+
+    fn days_in_month(&self) -> u32 {
+        match self.month() {
+            /* Jan */ 1 => 31,
+            /* Feb */ 2 => if self.is_leap_year() { 29 } else { 28 },
+            /* Mar */ 3 => 31,
+            /* Apr */ 4 => 30,
+            /* May */ 5 => 31,
+            /* Jun */ 6 => 30,
+            /* Jul */ 7 => 31,
+            /* Aug */ 8 => 31,
+            /* Sep */ 9 => 30,
+            /* Oct */ 10 => 31,
+            /* Nov */ 11 => 30,
+            /* Dec */ 12 => 31,
+            _ => unreachable!()
+        }
+    }
+}
+
+impl<'a, 'b> std::ops::Add<&'b NaiveDate> for &'a NaiveDate {
+    type Output = NaiveDate;
+
+    fn add(self, other: &'b NaiveDate) -> NaiveDate {
+        assert_eq!(*other, NaiveDate(0, 0, 1));
+        self.succ()
+    }
+}
+
+impl std::iter::Step for NaiveDate {
+    fn step(&self, by: &Self) -> Option<Self> {
+        Some(self + by)
+    }
+
+    fn steps_between(_: &Self, _: &Self, _: &Self) -> Option<usize> {
+        unimplemented!()
+    }
+
+    fn steps_between_by_one(_: &Self, _: &Self) -> Option<usize> {
+        unimplemented!()
+    }
+
+    fn is_negative(&self) -> bool {
+        false
+    }
+
+    fn replace_one(&mut self) -> Self {
+        mem::replace(self, NaiveDate(0, 0, 1))
+    }
+
+    fn replace_zero(&mut self) -> Self {
+        mem::replace(self, NaiveDate(0, 0, 0))
+    }
+
+    fn add_one(&self) -> Self {
+        self.succ()
+    }
+
+    fn sub_one(&self) -> Self {
+        unimplemented!()
+    }
+}
+
+#[derive(Copy, Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
+pub enum Weekday {
+    Mon,
+    Tue,
+    Wed,
+    Thu,
+    Fri,
+    Sat,
+    Sun,
+}
+
+impl Weekday {
+    pub fn num_days_from_monday(&self) -> u32 {
+        use Weekday::*;
+        match *self {
+            Mon => 0,
+            Tue => 1,
+            Wed => 2,
+            Thu => 3,
+            Fri => 4,
+            Sat => 5,
+            Sun => 6,
+        }
+    }
+
+    pub fn num_days_from_sunday(&self) -> u32 {
+        use Weekday::*;
+        match *self {
+            Sun => 0,
+            Mon => 1,
+            Tue => 2,
+            Wed => 3,
+            Thu => 4,
+            Fri => 5,
+            Sat => 6,
+        }
+    }
+}
+
+/// Wrapper for zero-sized closures.
+// HACK(eddyb) Only needed because closures can't implement Copy.
+struct Fn0<F>(std::marker::PhantomData<F>);
+
+impl<F> Copy for Fn0<F> {}
+impl<F> Clone for Fn0<F> {
+    fn clone(&self) -> Self { *self }
+}
+
+impl<F: FnOnce<A>, A> FnOnce<A> for Fn0<F> {
+    type Output = F::Output;
+
+    extern "rust-call" fn call_once(self, args: A) -> Self::Output {
+        let f = unsafe { std::mem::uninitialized::<F>() };
+        f.call_once(args)
+    }
+}
+
+impl<F: FnMut<A>, A> FnMut<A> for Fn0<F> {
+    extern "rust-call" fn call_mut(&mut self, args: A) -> Self::Output {
+        let mut f = unsafe { std::mem::uninitialized::<F>() };
+        f.call_mut(args)
+    }
+}
+
+trait AsFn0<A>: Sized {
+    fn copyable(self) -> Fn0<Self>;
+}
+
+impl<F: FnMut<A>, A> AsFn0<A> for F {
+    fn copyable(self) -> Fn0<Self> {
+        assert_eq!(std::mem::size_of::<F>(), 0);
+        Fn0(std::marker::PhantomData)
+    }
+}
+
+/// GroupBy implementation.
+struct GroupBy<It: Iterator, F> {
+    it: std::iter::Peekable<It>,
+    f: F,
+}
+
+impl<It, F> Clone for GroupBy<It, F>
+where It: Iterator + Clone, It::Item: Clone, F: Clone {
+    fn clone(&self) -> GroupBy<It, F> {
+        GroupBy {
+            it: self.it.clone(),
+            f: self.f.clone()
+        }
+    }
+}
+
+impl<'a, G, It: 'a, F: 'a> Iterator for GroupBy<It, F>
+where It: Iterator + Clone,
+      It::Item: Clone,
+      F: Clone + FnMut(&It::Item) -> G,
+      G: Eq + Clone
+{
+    type Item = (G, InGroup<std::iter::Peekable<It>, F, G>);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.it.peek().map(&mut self.f).map(|key| {
+            let start = self.it.clone();
+            while let Some(k) = self.it.peek().map(&mut self.f) {
+                if key != k {
+                    break;
+                }
+                self.it.next();
+            }
+
+            (key.clone(), InGroup {
+                it: start,
+                f: self.f.clone(),
+                g: key
+            })
+        })
+    }
+}
+
+#[derive(Copy, Clone)]
+struct InGroup<It, F, G> {
+    it: It,
+    f: F,
+    g: G
+}
+
+impl<It: Iterator, F: FnMut(&It::Item) -> G, G: Eq> Iterator for InGroup<It, F, G> {
+    type Item = It::Item;
+
+    fn next(&mut self) -> Option<It::Item> {
+        self.it.next().and_then(|x| {
+            if (self.f)(&x) == self.g { Some(x) } else { None }
+        })
+    }
+}
+
+trait IteratorExt: Iterator + Sized {
+    fn group_by<G, F>(self, f: F) -> GroupBy<Self, Fn0<F>>
+    where F: FnMut(&Self::Item) -> G,
+          G: Eq
+    {
+        GroupBy {
+            it: self.peekable(),
+            f: f.copyable(),
+        }
+    }
+
+    fn join(mut self, sep: &str) -> String
+    where Self::Item: std::fmt::Display {
+        let mut s = String::new();
+        if let Some(e) = self.next() {
+            write!(s, "{}", e);
+            for e in self {
+                s.push_str(sep);
+                write!(s, "{}", e);
+            }
+        }
+        s
+    }
+
+    // HACK(eddyb) Only needed because `impl Trait` can't be
+    // used with trait methods: `.foo()` becomes `.__(foo)`.
+    fn __<F, R>(self, f: F) -> R
+    where F: FnOnce(Self) -> R {
+        f(self)
+    }
+}
+
+impl<It> IteratorExt for It where It: Iterator {}
+
+///
+/// Generates an iterator that yields exactly n spaces.
+///
+fn spaces(n: usize) -> std::iter::Take<std::iter::Repeat<char>> {
+    std::iter::repeat(' ').take(n)
+}
+
+fn test_spaces() {
+    assert_eq!(spaces(0).collect::<String>(), "");
+    assert_eq!(spaces(10).collect::<String>(), "          ")
+}
+
+///
+/// Returns an iterator of dates in a given year.
+///
+fn dates_in_year(year: i32) -> impl Iterator<Item=NaiveDate>+Clone {
+    InGroup {
+        it: NaiveDate::from_ymd(year, 1, 1)..,
+        f: (|d: &NaiveDate| d.year()).copyable(),
+        g: year
+    }
+}
+
+fn test_dates_in_year() {
+    {
+        let mut dates = dates_in_year(2013);
+        assert_eq!(dates.next(), Some(NaiveDate::from_ymd(2013, 1, 1)));
+
+        // Check increment
+        assert_eq!(dates.next(), Some(NaiveDate::from_ymd(2013, 1, 2)));
+
+        // Check monthly rollover
+        for _ in 3..31 {
+            assert!(dates.next() != None);
+        }
+
+        assert_eq!(dates.next(), Some(NaiveDate::from_ymd(2013, 1, 31)));
+        assert_eq!(dates.next(), Some(NaiveDate::from_ymd(2013, 2, 1)));
+    }
+
+    {
+        // Check length of year
+        let mut dates = dates_in_year(2013);
+        for _ in 0..365 {
+            assert!(dates.next() != None);
+        }
+        assert_eq!(dates.next(), None);
+    }
+
+    {
+        // Check length of leap year
+        let mut dates = dates_in_year(1984);
+        for _ in 0..366 {
+            assert!(dates.next() != None);
+        }
+        assert_eq!(dates.next(), None);
+    }
+}
+
+///
+/// Convenience trait for verifying that a given type iterates over
+/// `NaiveDate`s.
+///
+trait DateIterator: Iterator<Item=NaiveDate> + Clone {}
+impl<It> DateIterator for It where It: Iterator<Item=NaiveDate> + Clone {}
+
+fn test_group_by() {
+    let input = [
+        [1, 1],
+        [1, 1],
+        [1, 2],
+        [2, 2],
+        [2, 3],
+        [2, 3],
+        [3, 3]
+    ];
+
+    let by_x = input.iter().cloned().group_by(|a| a[0]);
+    let expected_1: &[&[[i32; 2]]] = &[
+        &[[1, 1], [1, 1], [1, 2]],
+        &[[2, 2], [2, 3], [2, 3]],
+        &[[3, 3]]
+    ];
+    for ((_, a), b) in by_x.zip(expected_1.iter().cloned()) {
+        assert_eq!(&a.collect::<Vec<_>>()[..], b);
+    }
+
+    let by_y = input.iter().cloned().group_by(|a| a[1]);
+    let expected_2: &[&[[i32; 2]]] = &[
+        &[[1, 1], [1, 1]],
+        &[[1, 2], [2, 2]],
+        &[[2, 3], [2, 3], [3, 3]]
+    ];
+    for ((_, a), b) in by_y.zip(expected_2.iter().cloned()) {
+        assert_eq!(&a.collect::<Vec<_>>()[..], b);
+    }
+}
+
+///
+/// Groups an iterator of dates by month.
+///
+fn by_month<It>(it: It)
+                ->  impl Iterator<Item=(u32, impl Iterator<Item=NaiveDate> + Clone)> + Clone
+where It: Iterator<Item=NaiveDate> + Clone {
+    it.group_by(|d| d.month())
+}
+
+fn test_by_month() {
+    let mut months = dates_in_year(2013).__(by_month);
+    for (month, (_, mut date)) in (1..13).zip(&mut months) {
+        assert_eq!(date.nth(0).unwrap(), NaiveDate::from_ymd(2013, month, 1));
+    }
+    assert!(months.next().is_none());
+}
+
+///
+/// Groups an iterator of dates by week.
+///
+fn by_week<It>(it: It)
+               -> impl Iterator<Item=(u32, impl DateIterator)> + Clone
+where It: DateIterator {
+    // We go forward one day because `isoweekdate` considers the week to start on a Monday.
+    it.group_by(|d| d.succ().isoweekdate().1)
+}
+
+fn test_isoweekdate() {
+    fn weeks_uniq(year: i32) -> Vec<((i32, u32), u32)> {
+        let mut weeks = dates_in_year(year).map(|d| d.isoweekdate())
+            .map(|(y,w,_)| (y,w));
+        let mut result = vec![];
+        let mut accum = (weeks.next().unwrap(), 1);
+        for yw in weeks {
+            if accum.0 == yw {
+                accum.1 += 1;
+            } else {
+                result.push(accum);
+                accum = (yw, 1);
+            }
+        }
+        result.push(accum);
+        result
+    }
+
+    let wu_1984 = weeks_uniq(1984);
+    assert_eq!(&wu_1984[..2], &[((1983, 52), 1), ((1984, 1), 7)]);
+    assert_eq!(&wu_1984[wu_1984.len()-2..], &[((1984, 52), 7), ((1985, 1), 1)]);
+
+    let wu_2013 = weeks_uniq(2013);
+    assert_eq!(&wu_2013[..2], &[((2013, 1), 6), ((2013, 2), 7)]);
+    assert_eq!(&wu_2013[wu_2013.len()-2..], &[((2013, 52), 7), ((2014, 1), 2)]);
+
+    let wu_2015 = weeks_uniq(2015);
+    assert_eq!(&wu_2015[..2], &[((2015, 1), 4), ((2015, 2), 7)]);
+    assert_eq!(&wu_2015[wu_2015.len()-2..], &[((2015, 52), 7), ((2015, 53), 4)]);
+}
+
+fn test_by_week() {
+    let mut weeks = dates_in_year(2013).__(by_week);
+    assert_eq!(
+        &*weeks.next().unwrap().1.collect::<Vec<_>>(),
+        &[
+            NaiveDate::from_ymd(2013, 1, 1),
+            NaiveDate::from_ymd(2013, 1, 2),
+            NaiveDate::from_ymd(2013, 1, 3),
+            NaiveDate::from_ymd(2013, 1, 4),
+            NaiveDate::from_ymd(2013, 1, 5),
+        ]
+    );
+    assert_eq!(
+        &*weeks.next().unwrap().1.collect::<Vec<_>>(),
+        &[
+            NaiveDate::from_ymd(2013, 1, 6),
+            NaiveDate::from_ymd(2013, 1, 7),
+            NaiveDate::from_ymd(2013, 1, 8),
+            NaiveDate::from_ymd(2013, 1, 9),
+            NaiveDate::from_ymd(2013, 1, 10),
+            NaiveDate::from_ymd(2013, 1, 11),
+            NaiveDate::from_ymd(2013, 1, 12),
+        ]
+    );
+    assert_eq!(weeks.next().unwrap().1.nth(0).unwrap(), NaiveDate::from_ymd(2013, 1, 13));
+}
+
+/// The number of columns per day in the formatted output.
+const COLS_PER_DAY: u32 = 3;
+
+/// The number of columns per week in the formatted output.
+const COLS_PER_WEEK: u32 = 7 * COLS_PER_DAY;
+
+///
+/// Formats an iterator of weeks into an iterator of strings.
+///
+fn format_weeks<It>(it: It) -> impl Iterator<Item=String>
+where It: Iterator, It::Item: DateIterator {
+    it.map(|week| {
+        let mut buf = String::with_capacity((COLS_PER_DAY * COLS_PER_WEEK + 2) as usize);
+
+        // Format each day into its own cell and append to target string.
+        let mut last_day = 0;
+        let mut first = true;
+        for d in week {
+            last_day = d.weekday().num_days_from_sunday();
+
+            // Insert enough filler to align the first day with its respective day-of-week.
+            if first {
+                buf.extend(spaces((COLS_PER_DAY * last_day) as usize));
+                first = false;
+            }
+
+            write!(buf, " {:>2}", d.day());
+        }
+
+        // Insert more filler at the end to fill up the remainder of the week,
+        // if its a short week (e.g. at the end of the month).
+        buf.extend(spaces((COLS_PER_DAY * (6 - last_day)) as usize));
+        buf
+    })
+}
+
+fn test_format_weeks() {
+    let jan_2013 = dates_in_year(2013)
+        .__(by_month).next() // pick January 2013 for testing purposes
+        // NOTE: This `map` is because `next` returns an `Option<_>`.
+        .map(|(_, month)|
+            month.__(by_week)
+                 .map(|(_, weeks)| weeks)
+                 .__(format_weeks)
+                 .join("\n"));
+
+    assert_eq!(
+        jan_2013.as_ref().map(|s| &**s),
+        Some("        1  2  3  4  5\n\
+           \x20 6  7  8  9 10 11 12\n\
+           \x2013 14 15 16 17 18 19\n\
+           \x2020 21 22 23 24 25 26\n\
+           \x2027 28 29 30 31      ")
+    );
+}
+
+///
+/// Formats the name of a month, centered on COLS_PER_WEEK.
+///
+fn month_title(month: u32) -> String {
+    const MONTH_NAMES: &'static [&'static str] = &[
+        "January", "February", "March", "April", "May", "June",
+        "July", "August", "September", "October", "November", "December"
+    ];
+    assert_eq!(MONTH_NAMES.len(), 12);
+
+    // Determine how many spaces before and after the month name
+    // we need to center it over the formatted weeks in the month.
+    let name = MONTH_NAMES[(month - 1) as usize];
+    assert!(name.len() < COLS_PER_WEEK as usize);
+    let before = (COLS_PER_WEEK as usize - name.len()) / 2;
+    let after = COLS_PER_WEEK as usize - name.len() - before;
+
+    // NOTE: Being slightly more verbose to avoid extra allocations.
+    let mut result = String::with_capacity(COLS_PER_WEEK as usize);
+    result.extend(spaces(before));
+    result.push_str(name);
+    result.extend(spaces(after));
+    result
+}
+
+fn test_month_title() {
+    assert_eq!(month_title(1).len(), COLS_PER_WEEK as usize);
+}
+
+///
+/// Formats a month.
+///
+fn format_month<It: DateIterator>(it: It) -> impl Iterator<Item=String> {
+    let mut month_days = it.peekable();
+    let title = month_title(month_days.peek().unwrap().month());
+
+    Some(title).into_iter()
+        .chain(month_days.__(by_week)
+            .map(|(_, week)| week)
+            .__(format_weeks))
+}
+
+fn test_format_month() {
+    let month_fmt = dates_in_year(2013)
+        .__(by_month).next() // Pick January as a test case
+        .map(|(_, days)| days.into_iter()
+            .__(format_month)
+            .join("\n"));
+
+    assert_eq!(
+        month_fmt.as_ref().map(|s| &**s),
+        Some("       January       \n\
+           \x20       1  2  3  4  5\n\
+           \x20 6  7  8  9 10 11 12\n\
+           \x2013 14 15 16 17 18 19\n\
+           \x2020 21 22 23 24 25 26\n\
+           \x2027 28 29 30 31      ")
+    );
+}
+
+
+///
+/// Formats an iterator of months.
+///
+fn format_months<It>(it: It) -> impl Iterator<Item=impl Iterator<Item=String>>
+where It: Iterator, It::Item: DateIterator {
+    it.map(format_month)
+}
+
+///
+/// Takes an iterator of iterators of strings; the sub-iterators are consumed
+/// in lock-step, with their elements joined together.
+///
+trait PasteBlocks: Iterator + Sized
+where Self::Item: Iterator<Item=String> {
+    fn paste_blocks(self, sep_width: usize) -> PasteBlocksIter<Self::Item> {
+        PasteBlocksIter {
+            iters: self.collect(),
+            cache: vec![],
+            col_widths: None,
+            sep_width: sep_width,
+        }
+    }
+}
+
+impl<It> PasteBlocks for It where It: Iterator, It::Item: Iterator<Item=String> {}
+
+struct PasteBlocksIter<StrIt>
+where StrIt: Iterator<Item=String> {
+    iters: Vec<StrIt>,
+    cache: Vec<Option<String>>,
+    col_widths: Option<Vec<usize>>,
+    sep_width: usize,
+}
+
+impl<StrIt> Iterator for PasteBlocksIter<StrIt>
+where StrIt: Iterator<Item=String> {
+    type Item = String;
+
+    fn next(&mut self) -> Option<String> {
+        self.cache.clear();
+
+        // `cache` is now the next line from each iterator.
+        self.cache.extend(self.iters.iter_mut().map(|it| it.next()));
+
+        // If every line in `cache` is `None`, we have nothing further to do.
+        if self.cache.iter().all(|e| e.is_none()) { return None }
+
+        // Get the column widths if we haven't already.
+        let col_widths = match self.col_widths {
+            Some(ref v) => &**v,
+            None => {
+                self.col_widths = Some(self.cache.iter()
+                    .map(|ms| ms.as_ref().map(|s| s.len()).unwrap_or(0))
+                    .collect());
+                &**self.col_widths.as_ref().unwrap()
+            }
+        };
+
+        // Fill in any `None`s with spaces.
+        let mut parts = col_widths.iter().cloned().zip(self.cache.iter_mut())
+            .map(|(w,ms)| ms.take().unwrap_or_else(|| spaces(w).collect()));
+
+        // Join them all together.
+        let first = parts.next().unwrap_or(String::new());
+        let sep_width = self.sep_width;
+        Some(parts.fold(first, |mut accum, next| {
+            accum.extend(spaces(sep_width));
+            accum.push_str(&next);
+            accum
+        }))
+    }
+}
+
+fn test_paste_blocks() {
+    let row = dates_in_year(2013)
+        .__(by_month).map(|(_, days)| days)
+        .take(3)
+        .__(format_months)
+        .paste_blocks(1)
+        .join("\n");
+    assert_eq!(
+        &*row,
+        "       January              February                March        \n\
+      \x20       1  2  3  4  5                  1  2                  1  2\n\
+      \x20 6  7  8  9 10 11 12   3  4  5  6  7  8  9   3  4  5  6  7  8  9\n\
+      \x2013 14 15 16 17 18 19  10 11 12 13 14 15 16  10 11 12 13 14 15 16\n\
+      \x2020 21 22 23 24 25 26  17 18 19 20 21 22 23  17 18 19 20 21 22 23\n\
+      \x2027 28 29 30 31        24 25 26 27 28        24 25 26 27 28 29 30\n\
+      \x20                                            31                  "
+    );
+}
+
+///
+/// Produces an iterator that yields `n` elements at a time.
+///
+trait Chunks: Iterator + Sized {
+    fn chunks(self, n: usize) -> ChunksIter<Self> {
+        assert!(n > 0);
+        ChunksIter {
+            it: self,
+            n: n,
+        }
+    }
+}
+
+impl<It> Chunks for It where It: Iterator {}
+
+struct ChunksIter<It>
+where It: Iterator {
+    it: It,
+    n: usize,
+}
+
+// NOTE: `chunks` in Rust is more-or-less impossible without overhead of some kind.
+// Aliasing rules mean you need to add dynamic borrow checking, and the design of
+// `Iterator` means that you need to have the iterator's state kept in an allocation
+// that is jointly owned by the iterator itself and the sub-iterator.
+// As such, I've chosen to cop-out and just heap-allocate each chunk.
+
+impl<It> Iterator for ChunksIter<It>
+where It: Iterator {
+    type Item = Vec<It::Item>;
+
+    fn next(&mut self) -> Option<Vec<It::Item>> {
+        let first = match self.it.next() {
+            Some(e) => e,
+            None => return None
+        };
+
+        let mut result = Vec::with_capacity(self.n);
+        result.push(first);
+
+        Some((&mut self.it).take(self.n-1)
+            .fold(result, |mut acc, next| { acc.push(next); acc }))
+    }
+}
+
+fn test_chunks() {
+    let r = &[1, 2, 3, 4, 5, 6, 7];
+    let c = r.iter().cloned().chunks(3).collect::<Vec<_>>();
+    assert_eq!(&*c, &[vec![1, 2, 3], vec![4, 5, 6], vec![7]]);
+}
+
+///
+/// Formats a year.
+///
+fn format_year(year: i32, months_per_row: usize) -> String {
+    const COL_SPACING: usize = 1;
+
+    // Start by generating all dates for the given year.
+    dates_in_year(year)
+
+        // Group them by month and throw away month number.
+        .__(by_month).map(|(_, days)| days)
+
+        // Group the months into horizontal rows.
+        .chunks(months_per_row)
+
+        // Format each row
+        .map(|r| r.into_iter()
+            // By formatting each month
+            .__(format_months)
+
+            // Horizontally pasting each respective month's lines together.
+            .paste_blocks(COL_SPACING)
+            .join("\n")
+        )
+
+        // Insert a blank line between each row
+        .join("\n\n")
+}
+
+fn test_format_year() {
+    const MONTHS_PER_ROW: usize = 3;
+
+    macro_rules! assert_eq_cal {
+        ($lhs:expr, $rhs:expr) => {
+            if $lhs != $rhs {
+                println!("got:\n```\n{}\n```\n", $lhs.replace(" ", "."));
+                println!("expected:\n```\n{}\n```", $rhs.replace(" ", "."));
+                panic!("calendars didn't match!");
+            }
+        }
+    }
+
+    assert_eq_cal!(&format_year(1984, MONTHS_PER_ROW), "\
+\x20      January              February                March        \n\
+\x20 1  2  3  4  5  6  7            1  2  3  4               1  2  3\n\
+\x20 8  9 10 11 12 13 14   5  6  7  8  9 10 11   4  5  6  7  8  9 10\n\
+\x2015 16 17 18 19 20 21  12 13 14 15 16 17 18  11 12 13 14 15 16 17\n\
+\x2022 23 24 25 26 27 28  19 20 21 22 23 24 25  18 19 20 21 22 23 24\n\
+\x2029 30 31              26 27 28 29           25 26 27 28 29 30 31\n\
+\n\
+\x20       April                  May                  June         \n\
+\x20 1  2  3  4  5  6  7         1  2  3  4  5                  1  2\n\
+\x20 8  9 10 11 12 13 14   6  7  8  9 10 11 12   3  4  5  6  7  8  9\n\
+\x2015 16 17 18 19 20 21  13 14 15 16 17 18 19  10 11 12 13 14 15 16\n\
+\x2022 23 24 25 26 27 28  20 21 22 23 24 25 26  17 18 19 20 21 22 23\n\
+\x2029 30                 27 28 29 30 31        24 25 26 27 28 29 30\n\
+\n\
+\x20       July                 August               September      \n\
+\x20 1  2  3  4  5  6  7            1  2  3  4                     1\n\
+\x20 8  9 10 11 12 13 14   5  6  7  8  9 10 11   2  3  4  5  6  7  8\n\
+\x2015 16 17 18 19 20 21  12 13 14 15 16 17 18   9 10 11 12 13 14 15\n\
+\x2022 23 24 25 26 27 28  19 20 21 22 23 24 25  16 17 18 19 20 21 22\n\
+\x2029 30 31              26 27 28 29 30 31     23 24 25 26 27 28 29\n\
+\x20                                            30                  \n\
+\n\
+\x20      October              November              December       \n\
+\x20    1  2  3  4  5  6               1  2  3                     1\n\
+\x20 7  8  9 10 11 12 13   4  5  6  7  8  9 10   2  3  4  5  6  7  8\n\
+\x2014 15 16 17 18 19 20  11 12 13 14 15 16 17   9 10 11 12 13 14 15\n\
+\x2021 22 23 24 25 26 27  18 19 20 21 22 23 24  16 17 18 19 20 21 22\n\
+\x2028 29 30 31           25 26 27 28 29 30     23 24 25 26 27 28 29\n\
+\x20                                            30 31               ");
+
+    assert_eq_cal!(&format_year(2015, MONTHS_PER_ROW), "\
+\x20      January              February                March        \n\
+\x20             1  2  3   1  2  3  4  5  6  7   1  2  3  4  5  6  7\n\
+\x20 4  5  6  7  8  9 10   8  9 10 11 12 13 14   8  9 10 11 12 13 14\n\
+\x2011 12 13 14 15 16 17  15 16 17 18 19 20 21  15 16 17 18 19 20 21\n\
+\x2018 19 20 21 22 23 24  22 23 24 25 26 27 28  22 23 24 25 26 27 28\n\
+\x2025 26 27 28 29 30 31                        29 30 31            \n\
+\n\
+\x20       April                  May                  June         \n\
+\x20          1  2  3  4                  1  2      1  2  3  4  5  6\n\
+\x20 5  6  7  8  9 10 11   3  4  5  6  7  8  9   7  8  9 10 11 12 13\n\
+\x2012 13 14 15 16 17 18  10 11 12 13 14 15 16  14 15 16 17 18 19 20\n\
+\x2019 20 21 22 23 24 25  17 18 19 20 21 22 23  21 22 23 24 25 26 27\n\
+\x2026 27 28 29 30        24 25 26 27 28 29 30  28 29 30            \n\
+\x20                      31                                        \n\
+\n\
+\x20       July                 August               September      \n\
+\x20          1  2  3  4                     1         1  2  3  4  5\n\
+\x20 5  6  7  8  9 10 11   2  3  4  5  6  7  8   6  7  8  9 10 11 12\n\
+\x2012 13 14 15 16 17 18   9 10 11 12 13 14 15  13 14 15 16 17 18 19\n\
+\x2019 20 21 22 23 24 25  16 17 18 19 20 21 22  20 21 22 23 24 25 26\n\
+\x2026 27 28 29 30 31     23 24 25 26 27 28 29  27 28 29 30         \n\
+\x20                      30 31                                     \n\
+\n\
+\x20      October              November              December       \n\
+\x20             1  2  3   1  2  3  4  5  6  7         1  2  3  4  5\n\
+\x20 4  5  6  7  8  9 10   8  9 10 11 12 13 14   6  7  8  9 10 11 12\n\
+\x2011 12 13 14 15 16 17  15 16 17 18 19 20 21  13 14 15 16 17 18 19\n\
+\x2018 19 20 21 22 23 24  22 23 24 25 26 27 28  20 21 22 23 24 25 26\n\
+\x2025 26 27 28 29 30 31  29 30                 27 28 29 30 31      ");
+}
+
+fn main() {
+    // Run tests.
+    test_spaces();
+    test_dates_in_year();
+    test_group_by();
+    test_by_month();
+    test_isoweekdate();
+    test_by_week();
+    test_format_weeks();
+    test_month_title();
+    test_format_month();
+    test_paste_blocks();
+    test_chunks();
+    test_format_year();
+}
diff --git a/src/test/run-pass/impl-trait/example-st.rs b/src/test/run-pass/impl-trait/example-st.rs
new file mode 100644
index 00000000000..461d4cf4ff0
--- /dev/null
+++ b/src/test/run-pass/impl-trait/example-st.rs
@@ -0,0 +1,40 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(conservative_impl_trait, question_mark)]
+
+struct State;
+type Error = ();
+
+trait Bind<F> {
+    type Output;
+    fn bind(self, f: F) -> Self::Output;
+}
+
+fn bind<T, U, A, B, F>(mut a: A, mut f: F)
+                       -> impl FnMut(&mut State) -> Result<U, Error>
+where F: FnMut(T) -> B,
+      A: FnMut(&mut State) -> Result<T, Error>,
+      B: FnMut(&mut State) -> Result<U, Error>
+{
+    move |state | {
+        let r = a(state)?;
+        f(r)(state)
+    }
+}
+
+fn atom<T>(x: T) -> impl FnMut(&mut State) -> Result<T, Error> {
+    let mut x = Some(x);
+    move |_| x.take().map_or(Err(()), Ok)
+}
+
+fn main() {
+    assert_eq!(bind(atom(5), |x| atom(x > 4))(&mut State), Ok(true));
+}
diff --git a/src/test/run-pass/transmute-specialization.rs b/src/test/run-pass/transmute-specialization.rs
new file mode 100644
index 00000000000..823def32270
--- /dev/null
+++ b/src/test/run-pass/transmute-specialization.rs
@@ -0,0 +1,23 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(specialization)]
+
+trait Specializable { type Output; }
+
+impl<T> Specializable for T {
+    default type Output = u16;
+}
+
+fn main() {
+    unsafe {
+        std::mem::transmute::<u16, <() as Specializable>::Output>(0);
+    }
+}