typeck: record `impl Trait` concrete resolutions.

10 files changed, 1224 insertions, 96 deletions

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/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_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_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 57e58a98b53..ad61b5b0b51 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -1763,25 +1763,28 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
 
                 // Create the anonymized type.
                 let def_id = tcx.map.local_def_id(ast_ty.id);
-                let substs = if let Some(anon_scope) = rscope.anon_type_scope() {
-                    anon_scope.fresh_substs(tcx)
+                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.mk_substs(Substs::empty())
-                };
-                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, ast_ty.span);
-                let predicates = tcx.lift_to_global(&bounds.predicates(tcx, ty)).unwrap();
-                let predicates = ty::GenericPredicates {
-                    predicates: VecPerParamSpace::new(vec![], vec![], predicates)
-                };
-                tcx.predicates.borrow_mut().insert(def_id, predicates);
-
-                ty
+                    tcx.types.err
+                }
             }
             hir::TyPath(ref maybe_qself, ref path) => {
                 debug!("ast_ty_to_ty: maybe_qself={:?} path={:?}", maybe_qself, path);
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index f4c8032c1d1..1734dec7e72 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -96,7 +96,7 @@ 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,12 @@ 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>>>,
 }
 
 impl<'a, 'gcx, 'tcx> Deref for Inherited<'a, 'gcx, 'tcx> {
@@ -408,6 +414,7 @@ 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()),
             })
         })
     }
@@ -631,32 +638,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 +676,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
 }
 
@@ -1623,6 +1626,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>
diff --git a/src/librustc_typeck/check/writeback.rs b/src/librustc_typeck/check/writeback.rs
index 42893e40024..7458e3b9bc7 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;
 
@@ -62,6 +64,7 @@ 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();
     }
 }
 
@@ -75,11 +78,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 +295,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);
@@ -377,7 +469,8 @@ enum ResolveReason {
     ResolvingUpvar(ty::UpvarId),
     ResolvingClosure(DefId),
     ResolvingFnSig(ast::NodeId),
-    ResolvingFieldTypes(ast::NodeId)
+    ResolvingFieldTypes(ast::NodeId),
+    ResolvingAnonTy(DefId),
 }
 
 impl<'a, 'gcx, 'tcx> ResolveReason {
@@ -395,12 +488,9 @@ 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)
             }
         }
     }
@@ -483,6 +573,12 @@ impl<'cx, 'gcx, 'tcx> Resolver<'cx, 'gcx, 'tcx> {
                         span,
                         &format!("cannot resolve some aspect of data for {:?}", id));
                 }
+
+                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/collect.rs b/src/librustc_typeck/collect.rs
index 7c52ea5f3c9..75bfad053a3 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -1194,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);
 
@@ -1407,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()
@@ -1780,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());
@@ -2052,25 +2055,43 @@ 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![];
+
+    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
+    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
@@ -2116,42 +2137,6 @@ fn conv_poly_trait_ref<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>,
                                         projections)
 }
 
-fn conv_param_bounds<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, '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,
diff --git a/src/librustc_typeck/diagnostics.rs b/src/librustc_typeck/diagnostics.rs
index 49c35d1b7ef..7b78e83b801 100644
--- a/src/librustc_typeck/diagnostics.rs
+++ b/src/librustc_typeck/diagnostics.rs
@@ -4086,4 +4086,7 @@ register_diagnostics! {
     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/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));
+}