Auto merge of #51414 - oli-obk:impl_trait_type_def, r=pnkfelix

Add existential type definitions

Note: this does not allow creating named existential types, it just desugars `impl Trait` to a less (but still very) hacky version of actual `existential type` items.

r? @nikomatsakis

49 files changed, 646 insertions, 288 deletions

diff --git a/src/librustc/hir/def.rs b/src/librustc/hir/def.rs
index fd14be592be..7c10292061f 100644
--- a/src/librustc/hir/def.rs
+++ b/src/librustc/hir/def.rs
@@ -37,6 +37,7 @@ pub enum Def {
     Enum(DefId),
     Variant(DefId),
     Trait(DefId),
+    Existential(DefId),
     TyAlias(DefId),
     TyForeign(DefId),
     TraitAlias(DefId),
@@ -234,6 +235,7 @@ impl Def {
             Def::AssociatedTy(id) | Def::TyParam(id) | Def::Struct(id) | Def::StructCtor(id, ..) |
             Def::Union(id) | Def::Trait(id) | Def::Method(id) | Def::Const(id) |
             Def::AssociatedConst(id) | Def::Macro(id, ..) |
+            Def::Existential(id) |
             Def::GlobalAsm(id) | Def::TyForeign(id) => {
                 id
             }
@@ -260,6 +262,7 @@ impl Def {
             Def::VariantCtor(.., CtorKind::Const) => "unit variant",
             Def::VariantCtor(.., CtorKind::Fictive) => "struct variant",
             Def::Enum(..) => "enum",
+            Def::Existential(..) => "existential type",
             Def::TyAlias(..) => "type alias",
             Def::TraitAlias(..) => "trait alias",
             Def::AssociatedTy(..) => "associated type",
diff --git a/src/librustc/hir/intravisit.rs b/src/librustc/hir/intravisit.rs
index 5471568d0af..12ccb329e06 100644
--- a/src/librustc/hir/intravisit.rs
+++ b/src/librustc/hir/intravisit.rs
@@ -502,6 +502,14 @@ pub fn walk_item<'v, V: Visitor<'v>>(visitor: &mut V, item: &'v Item) {
             visitor.visit_ty(typ);
             visitor.visit_generics(type_parameters)
         }
+        ItemExistential(ExistTy {ref generics, ref bounds, impl_trait_fn}) => {
+            visitor.visit_id(item.id);
+            walk_generics(visitor, generics);
+            walk_list!(visitor, visit_ty_param_bound, bounds);
+            if let Some(impl_trait_fn) = impl_trait_fn {
+                visitor.visit_def_mention(Def::Fn(impl_trait_fn))
+            }
+        }
         ItemEnum(ref enum_definition, ref type_parameters) => {
             visitor.visit_generics(type_parameters);
             // visit_enum_def() takes care of visiting the Item's NodeId
@@ -596,10 +604,9 @@ pub fn walk_ty<'v, V: Visitor<'v>>(visitor: &mut V, typ: &'v Ty) {
             }
             visitor.visit_lifetime(lifetime);
         }
-        TyImplTraitExistential(ref existty, ref lifetimes) => {
-            let ExistTy { ref generics, ref bounds } = *existty;
-            walk_generics(visitor, generics);
-            walk_list!(visitor, visit_ty_param_bound, bounds);
+        TyImplTraitExistential(item_id, def_id, ref lifetimes) => {
+            visitor.visit_def_mention(Def::Existential(def_id));
+            visitor.visit_nested_item(item_id);
             walk_list!(visitor, visit_lifetime, lifetimes);
         }
         TyTypeof(ref expression) => {
diff --git a/src/librustc/hir/lowering.rs b/src/librustc/hir/lowering.rs
index f31af7785a5..dd12edb7302 100644
--- a/src/librustc/hir/lowering.rs
+++ b/src/librustc/hir/lowering.rs
@@ -182,7 +182,9 @@ enum ImplTraitContext {
     /// Treat `impl Trait` as shorthand for a new universal existential parameter.
     /// Example: `fn foo() -> impl Debug`, where `impl Debug` is conceptually
     /// equivalent to a fresh existential parameter like `abstract type T; fn foo() -> T`.
-    Existential,
+    ///
+    /// We store a DefId here so we can look up necessary information later
+    Existential(DefId),
 
     /// `impl Trait` is not accepted in this position.
     Disallowed,
@@ -238,6 +240,7 @@ enum ParamMode {
     Optional,
 }
 
+#[derive(Debug)]
 struct LoweredNodeId {
     node_id: NodeId,
     hir_id: hir::HirId,
@@ -488,16 +491,16 @@ impl<'a> LoweringContext<'a> {
         }
     }
 
-    fn with_hir_id_owner<F>(&mut self, owner: NodeId, f: F)
+    fn with_hir_id_owner<F, T>(&mut self, owner: NodeId, f: F) -> T
     where
-        F: FnOnce(&mut Self),
+        F: FnOnce(&mut Self) -> T,
     {
         let counter = self.item_local_id_counters
             .insert(owner, HIR_ID_COUNTER_LOCKED)
             .unwrap();
         let def_index = self.resolver.definitions().opt_def_index(owner).unwrap();
         self.current_hir_id_owner.push((def_index, counter));
-        f(self);
+        let ret = f(self);
         let (new_def_index, new_counter) = self.current_hir_id_owner.pop().unwrap();
 
         debug_assert!(def_index == new_def_index);
@@ -507,6 +510,7 @@ impl<'a> LoweringContext<'a> {
             .insert(owner, new_counter)
             .unwrap();
         debug_assert!(prev == HIR_ID_COUNTER_LOCKED);
+        ret
     }
 
     /// This method allocates a new HirId for the given NodeId and stores it in
@@ -530,7 +534,10 @@ impl<'a> LoweringContext<'a> {
 
     fn lower_node_id_with_owner(&mut self, ast_node_id: NodeId, owner: NodeId) -> LoweredNodeId {
         self.lower_node_id_generic(ast_node_id, |this| {
-            let local_id_counter = this.item_local_id_counters.get_mut(&owner).unwrap();
+            let local_id_counter = this
+                .item_local_id_counters
+                .get_mut(&owner)
+                .expect("called lower_node_id_with_owner before allocate_hir_id_counter");
             let local_id = *local_id_counter;
 
             // We want to be sure not to modify the counter in the map while it
@@ -539,7 +546,12 @@ impl<'a> LoweringContext<'a> {
             debug_assert!(local_id != HIR_ID_COUNTER_LOCKED);
 
             *local_id_counter += 1;
-            let def_index = this.resolver.definitions().opt_def_index(owner).unwrap();
+            let def_index = this
+                .resolver
+                .definitions()
+                .opt_def_index(owner)
+                .expect("You forgot to call `create_def_with_parent` or are lowering node ids \
+                         that do not belong to the current owner");
 
             hir::HirId {
                 owner: def_index,
@@ -1120,26 +1132,93 @@ impl<'a> LoweringContext<'a> {
             TyKind::ImplTrait(ref bounds) => {
                 let span = t.span;
                 match itctx {
-                    ImplTraitContext::Existential => {
-                        let def_index = self.resolver.definitions().opt_def_index(t.id).unwrap();
-                        let hir_bounds = self.lower_bounds(bounds, itctx);
-                        let (lifetimes, lifetime_defs) =
-                            self.lifetimes_from_impl_trait_bounds(def_index, &hir_bounds);
+                    ImplTraitContext::Existential(fn_def_id) => {
+
+                        // We need to manually repeat the code of `next_id` because the lowering
+                        // needs to happen while the owner_id is pointing to the item itself,
+                        // because items are their own owners
+                        let exist_ty_node_id = self.sess.next_node_id();
+
+                        // Make sure we know that some funky desugaring has been going on here.
+                        // This is a first: there is code in other places like for loop
+                        // desugaring that explicitly states that we don't want to track that.
+                        // Not tracking it makes lints in rustc and clippy very fragile as
+                        // frequently opened issues show.
+                        let exist_ty_span = self.allow_internal_unstable(
+                            CompilerDesugaringKind::ExistentialReturnType,
+                            t.span,
+                        );
 
-                        hir::TyImplTraitExistential(
-                            hir::ExistTy {
+                        // Pull a new definition from the ether
+                        let exist_ty_def_index = self
+                            .resolver
+                            .definitions()
+                            .create_def_with_parent(
+                            fn_def_id.index,
+                            exist_ty_node_id,
+                            DefPathData::ExistentialImplTrait,
+                            DefIndexAddressSpace::High,
+                            Mark::root(),
+                            exist_ty_span,
+                        );
+
+                        // the `t` is just for printing debug messages
+                        self.allocate_hir_id_counter(exist_ty_node_id, t);
+
+                        let hir_bounds = self.with_hir_id_owner(exist_ty_node_id, |lctx| {
+                            lctx.lower_bounds(bounds, itctx)
+                        });
+
+                        let (lifetimes, lifetime_defs) = self.lifetimes_from_impl_trait_bounds(
+                            exist_ty_node_id,
+                            exist_ty_def_index,
+                            &hir_bounds,
+                        );
+
+                        self.with_hir_id_owner(exist_ty_node_id, |lctx| {
+                            let exist_ty_item_kind = hir::ItemExistential(hir::ExistTy {
                                 generics: hir::Generics {
                                     params: lifetime_defs,
                                     where_clause: hir::WhereClause {
-                                        id: self.next_id().node_id,
+                                        id: lctx.next_id().node_id,
                                         predicates: Vec::new().into(),
                                     },
                                     span,
                                 },
                                 bounds: hir_bounds,
-                            },
-                            lifetimes,
-                        )
+                                impl_trait_fn: Some(fn_def_id),
+                            });
+                            let exist_ty_id = lctx.lower_node_id(exist_ty_node_id);
+                            // Generate an `existential type Foo: Trait;` declaration
+                            trace!("creating existential type with id {:#?}", exist_ty_id);
+                            // Set the name to `impl Bound1 + Bound2`
+                            let exist_ty_name = Symbol::intern(&pprust::ty_to_string(t));
+
+                            trace!("exist ty def index: {:#?}", exist_ty_def_index);
+                            let exist_ty_item = hir::Item {
+                                id: exist_ty_id.node_id,
+                                hir_id: exist_ty_id.hir_id,
+                                name: exist_ty_name,
+                                attrs: Default::default(),
+                                node: exist_ty_item_kind,
+                                vis: hir::Visibility::Inherited,
+                                span: exist_ty_span,
+                            };
+
+                            // Insert the item into the global list. This usually happens
+                            // automatically for all AST items. But this existential type item
+                            // does not actually exist in the AST.
+                            lctx.items.insert(exist_ty_id.node_id, exist_ty_item);
+
+                            // `impl Trait` now just becomes `Foo<'a, 'b, ..>`
+                            hir::TyImplTraitExistential(
+                                hir::ItemId {
+                                    id: exist_ty_id.node_id
+                                },
+                                DefId::local(exist_ty_def_index),
+                                lifetimes,
+                            )
+                        })
                     }
                     ImplTraitContext::Universal(def_id) => {
                         let def_node_id = self.next_id().node_id;
@@ -1148,7 +1227,7 @@ impl<'a> LoweringContext<'a> {
                         let def_index = self.resolver.definitions().create_def_with_parent(
                             def_id.index,
                             def_node_id,
-                            DefPathData::ImplTrait,
+                            DefPathData::UniversalImplTrait,
                             DefIndexAddressSpace::High,
                             Mark::root(),
                             span,
@@ -1203,6 +1282,7 @@ impl<'a> LoweringContext<'a> {
 
     fn lifetimes_from_impl_trait_bounds(
         &mut self,
+        exist_ty_id: NodeId,
         parent_index: DefIndex,
         bounds: &hir::TyParamBounds,
     ) -> (HirVec<hir::Lifetime>, HirVec<hir::GenericParam>) {
@@ -1212,6 +1292,7 @@ impl<'a> LoweringContext<'a> {
         struct ImplTraitLifetimeCollector<'r, 'a: 'r> {
             context: &'r mut LoweringContext<'a>,
             parent: DefIndex,
+            exist_ty_id: NodeId,
             collect_elided_lifetimes: bool,
             currently_bound_lifetimes: Vec<hir::LifetimeName>,
             already_defined_lifetimes: HashSet<hir::LifetimeName>,
@@ -1306,7 +1387,11 @@ impl<'a> LoweringContext<'a> {
                         name,
                     });
 
-                    let def_node_id = self.context.next_id().node_id;
+                    // We need to manually create the ids here, because the
+                    // definitions will go into the explicit `existential type`
+                    // declaration and thus need to have their owner set to that item
+                    let def_node_id = self.context.sess.next_node_id();
+                    let _ = self.context.lower_node_id_with_owner(def_node_id, self.exist_ty_id);
                     self.context.resolver.definitions().create_def_with_parent(
                         self.parent,
                         def_node_id,
@@ -1318,7 +1403,7 @@ impl<'a> LoweringContext<'a> {
                     let def_lifetime = hir::Lifetime {
                         id: def_node_id,
                         span: lifetime.span,
-                        name: name,
+                        name,
                     };
                     self.output_lifetime_params
                         .push(hir::GenericParam::Lifetime(hir::LifetimeDef {
@@ -1334,6 +1419,7 @@ impl<'a> LoweringContext<'a> {
         let mut lifetime_collector = ImplTraitLifetimeCollector {
             context: self,
             parent: parent_index,
+            exist_ty_id,
             collect_elided_lifetimes: true,
             currently_bound_lifetimes: Vec::new(),
             already_defined_lifetimes: HashSet::new(),
@@ -1772,8 +1858,8 @@ impl<'a> LoweringContext<'a> {
                 .collect(),
             output: match decl.output {
                 FunctionRetTy::Ty(ref ty) => match fn_def_id {
-                    Some(_) if impl_trait_return_allow => {
-                        hir::Return(self.lower_ty(ty, ImplTraitContext::Existential))
+                    Some(def_id) if impl_trait_return_allow => {
+                        hir::Return(self.lower_ty(ty, ImplTraitContext::Existential(def_id)))
                     }
                     _ => hir::Return(self.lower_ty(ty, ImplTraitContext::Disallowed)),
                 },
diff --git a/src/librustc/hir/map/def_collector.rs b/src/librustc/hir/map/def_collector.rs
index 03b6dc1676f..48d959b4f8e 100644
--- a/src/librustc/hir/map/def_collector.rs
+++ b/src/librustc/hir/map/def_collector.rs
@@ -88,7 +88,7 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
         debug!("visit_item: {:?}", i);
 
         // Pick the def data. This need not be unique, but the more
-        // information we encapsulate into
+        // information we encapsulate into, the better
         let def_data = match i.node {
             ItemKind::Impl(..) => DefPathData::Impl,
             ItemKind::Trait(..) => DefPathData::Trait(i.ident.name.as_interned_str()),
@@ -256,9 +256,6 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
     fn visit_ty(&mut self, ty: &'a Ty) {
         match ty.node {
             TyKind::Mac(..) => return self.visit_macro_invoc(ty.id),
-            TyKind::ImplTrait(..) => {
-                self.create_def(ty.id, DefPathData::ImplTrait, REGULAR_SPACE, ty.span);
-            }
             _ => {}
         }
         visit::walk_ty(self, ty);
diff --git a/src/librustc/hir/map/definitions.rs b/src/librustc/hir/map/definitions.rs
index 838be076a0b..99023a16867 100644
--- a/src/librustc/hir/map/definitions.rs
+++ b/src/librustc/hir/map/definitions.rs
@@ -210,30 +210,9 @@ impl DefKey {
         } = self.disambiguated_data;
 
         ::std::mem::discriminant(data).hash(&mut hasher);
-        match *data {
-            DefPathData::TypeNs(name) |
-            DefPathData::Trait(name) |
-            DefPathData::AssocTypeInTrait(name) |
-            DefPathData::AssocTypeInImpl(name) |
-            DefPathData::ValueNs(name) |
-            DefPathData::Module(name) |
-            DefPathData::MacroDef(name) |
-            DefPathData::TypeParam(name) |
-            DefPathData::LifetimeDef(name) |
-            DefPathData::EnumVariant(name) |
-            DefPathData::Field(name) |
-            DefPathData::GlobalMetaData(name) => {
-                name.hash(&mut hasher);
-            }
-
-            DefPathData::Impl |
-            DefPathData::CrateRoot |
-            DefPathData::Misc |
-            DefPathData::ClosureExpr |
-            DefPathData::StructCtor |
-            DefPathData::AnonConst |
-            DefPathData::ImplTrait => {}
-        };
+        if let Some(name) = data.get_opt_name() {
+            name.hash(&mut hasher);
+        }
 
         disambiguator.hash(&mut hasher);
 
@@ -390,8 +369,10 @@ pub enum DefPathData {
     StructCtor,
     /// A constant expression (see {ast,hir}::AnonConst).
     AnonConst,
-    /// An `impl Trait` type node.
-    ImplTrait,
+    /// An `impl Trait` type node in argument position.
+    UniversalImplTrait,
+    /// An `impl Trait` type node in return position.
+    ExistentialImplTrait,
 
     /// GlobalMetaData identifies a piece of crate metadata that is global to
     /// a whole crate (as opposed to just one item). GlobalMetaData components
@@ -655,7 +636,8 @@ impl DefPathData {
             ClosureExpr |
             StructCtor |
             AnonConst |
-            ImplTrait => None
+            ExistentialImplTrait |
+            UniversalImplTrait => None
         }
     }
 
@@ -685,7 +667,8 @@ impl DefPathData {
             ClosureExpr => "{{closure}}",
             StructCtor => "{{constructor}}",
             AnonConst => "{{constant}}",
-            ImplTrait => "{{impl-Trait}}",
+            ExistentialImplTrait => "{{exist-impl-Trait}}",
+            UniversalImplTrait => "{{univ-impl-Trait}}",
         };
 
         Symbol::intern(s).as_interned_str()
diff --git a/src/librustc/hir/map/hir_id_validator.rs b/src/librustc/hir/map/hir_id_validator.rs
index a4c93111583..b90bca84ed6 100644
--- a/src/librustc/hir/map/hir_id_validator.rs
+++ b/src/librustc/hir/map/hir_id_validator.rs
@@ -96,7 +96,7 @@ impl<'a, 'hir: 'a> HirIdValidator<'a, 'hir> {
                       .keys()
                       .map(|local_id| local_id.as_usize())
                       .max()
-                      .unwrap();
+                      .expect("owning item has no entry");
 
         if max != self.hir_ids_seen.len() - 1 {
             // Collect the missing ItemLocalIds
@@ -113,6 +113,8 @@ impl<'a, 'hir: 'a> HirIdValidator<'a, 'hir> {
                     local_id: ItemLocalId(local_id as u32),
                 };
 
+                trace!("missing hir id {:#?}", hir_id);
+
                 // We are already in ICE mode here, so doing a linear search
                 // should be fine.
                 let (node_id, _) = self.hir_map
@@ -121,7 +123,7 @@ impl<'a, 'hir: 'a> HirIdValidator<'a, 'hir> {
                                        .iter()
                                        .enumerate()
                                        .find(|&(_, &entry)| hir_id == entry)
-                                       .unwrap();
+                                       .expect("no node_to_hir_id entry");
                 let node_id = NodeId::new(node_id);
                 missing_items.push(format!("[local_id: {}, node:{}]",
                                            local_id,
@@ -146,7 +148,7 @@ impl<'a, 'hir: 'a> intravisit::Visitor<'hir> for HirIdValidator<'a, 'hir> {
     }
 
     fn visit_id(&mut self, node_id: NodeId) {
-        let owner = self.owner_def_index.unwrap();
+        let owner = self.owner_def_index.expect("no owner_def_index");
         let stable_id = self.hir_map.definitions().node_to_hir_id[node_id];
 
         if stable_id == hir::DUMMY_HIR_ID {
diff --git a/src/librustc/hir/map/mod.rs b/src/librustc/hir/map/mod.rs
index d6de2f57e92..9df55e52061 100644
--- a/src/librustc/hir/map/mod.rs
+++ b/src/librustc/hir/map/mod.rs
@@ -398,6 +398,7 @@ impl<'hir> Map<'hir> {
                     ItemFn(..) => Some(Def::Fn(def_id())),
                     ItemMod(..) => Some(Def::Mod(def_id())),
                     ItemGlobalAsm(..) => Some(Def::GlobalAsm(def_id())),
+                    ItemExistential(..) => Some(Def::Existential(def_id())),
                     ItemTy(..) => Some(Def::TyAlias(def_id())),
                     ItemEnum(..) => Some(Def::Enum(def_id())),
                     ItemStruct(..) => Some(Def::Struct(def_id())),
@@ -767,7 +768,7 @@ impl<'hir> Map<'hir> {
 
     /// Retrieve the NodeId for `id`'s parent item, or `id` itself if no
     /// parent item is in this map. The "parent item" is the closest parent node
-    /// in the AST which is recorded by the map and is an item, either an item
+    /// in the HIR which is recorded by the map and is an item, either an item
     /// in a module, trait, or impl.
     pub fn get_parent(&self, id: NodeId) -> NodeId {
         match self.walk_parent_nodes(id, |node| match *node {
@@ -1250,6 +1251,7 @@ fn node_id_to_string(map: &Map, id: NodeId, include_id: bool) -> String {
                 ItemForeignMod(..) => "foreign mod",
                 ItemGlobalAsm(..) => "global asm",
                 ItemTy(..) => "ty",
+                ItemExistential(..) => "existential",
                 ItemEnum(..) => "enum",
                 ItemStruct(..) => "struct",
                 ItemUnion(..) => "union",
diff --git a/src/librustc/hir/mod.rs b/src/librustc/hir/mod.rs
index a0952720945..833090c3ee0 100644
--- a/src/librustc/hir/mod.rs
+++ b/src/librustc/hir/mod.rs
@@ -1693,6 +1693,7 @@ pub struct BareFnTy {
 pub struct ExistTy {
     pub generics: Generics,
     pub bounds: TyParamBounds,
+    pub impl_trait_fn: Option<DefId>,
 }
 
 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
@@ -1723,15 +1724,15 @@ pub enum Ty_ {
     /// An existentially quantified (there exists a type satisfying) `impl
     /// Bound1 + Bound2 + Bound3` type where `Bound` is a trait or a lifetime.
     ///
-    /// The `ExistTy` structure emulates an
-    /// `abstract type Foo<'a, 'b>: MyTrait<'a, 'b>;`.
+    /// The `Item` is the generated
+    /// `existential type Foo<'a, 'b>: MyTrait<'a, 'b>;`.
     ///
     /// The `HirVec<Lifetime>` is the list of lifetimes applied as parameters
     /// to the `abstract type`, e.g. the `'c` and `'d` in `-> Foo<'c, 'd>`.
     /// This list is only a list of lifetimes and not type parameters
     /// because all in-scope type parameters are captured by `impl Trait`,
     /// so they are resolved directly through the parent `Generics`.
-    TyImplTraitExistential(ExistTy, HirVec<Lifetime>),
+    TyImplTraitExistential(ItemId, DefId, HirVec<Lifetime>),
     /// Unused for now
     TyTypeof(AnonConst),
     /// TyInfer means the type should be inferred instead of it having been
@@ -2091,6 +2092,8 @@ pub enum Item_ {
     ItemGlobalAsm(P<GlobalAsm>),
     /// A type alias, e.g. `type Foo = Bar<u8>`
     ItemTy(P<Ty>, Generics),
+    /// A type alias, e.g. `type Foo = Bar<u8>`
+    ItemExistential(ExistTy),
     /// An enum definition, e.g. `enum Foo<A, B> {C<A>, D<B>}`
     ItemEnum(EnumDef, Generics),
     /// A struct definition, e.g. `struct Foo<A> {x: A}`
@@ -2124,6 +2127,7 @@ impl Item_ {
             ItemForeignMod(..) => "foreign module",
             ItemGlobalAsm(..) => "global asm",
             ItemTy(..) => "type alias",
+            ItemExistential(..) => "existential type",
             ItemEnum(..) => "enum",
             ItemStruct(..) => "struct",
             ItemUnion(..) => "union",
diff --git a/src/librustc/hir/print.rs b/src/librustc/hir/print.rs
index 2cf627fdc16..1beef3f715e 100644
--- a/src/librustc/hir/print.rs
+++ b/src/librustc/hir/print.rs
@@ -58,6 +58,9 @@ pub trait PpAnn {
     fn post(&self, _state: &mut State, _node: AnnNode) -> io::Result<()> {
         Ok(())
     }
+    fn try_fetch_item(&self, _: ast::NodeId) -> Option<&hir::Item> {
+        None
+    }
 }
 
 pub struct NoAnn;
@@ -65,6 +68,9 @@ impl PpAnn for NoAnn {}
 pub const NO_ANN: &'static dyn PpAnn = &NoAnn;
 
 impl PpAnn for hir::Crate {
+    fn try_fetch_item(&self, item: ast::NodeId) -> Option<&hir::Item> {
+        Some(self.item(item))
+    }
     fn nested(&self, state: &mut State, nested: Nested) -> io::Result<()> {
         match nested {
             Nested::Item(id) => state.print_item(self.item(id.id)),
@@ -413,8 +419,14 @@ impl<'a> State<'a> {
                     self.print_lifetime(lifetime)?;
                 }
             }
-            hir::TyImplTraitExistential(ref existty, ref _lifetimes) => {
-                self.print_bounds("impl", &existty.bounds[..])?;
+            hir::TyImplTraitExistential(hir_id, _def_id, ref _lifetimes) => {
+                match self.ann.try_fetch_item(hir_id.id).map(|it| &it.node) {
+                    None => self.word_space("impl {{Trait}}")?,
+                    Some(&hir::ItemExistential(ref exist_ty)) => {
+                        self.print_bounds("impl", &exist_ty.bounds)?;
+                    },
+                    other => bug!("impl Trait pointed to {:#?}", other),
+                }
             }
             hir::TyArray(ref ty, ref length) => {
                 self.s.word("[")?;
@@ -636,6 +648,31 @@ impl<'a> State<'a> {
                 self.s.word(";")?;
                 self.end()?; // end the outer ibox
             }
+            hir::ItemExistential(ref exist) => {
+                self.ibox(indent_unit)?;
+                self.ibox(0)?;
+                self.word_nbsp(&visibility_qualified(&item.vis, "existential type"))?;
+                self.print_name(item.name)?;
+                self.print_generic_params(&exist.generics.params)?;
+                self.end()?; // end the inner ibox
+
+                self.print_where_clause(&exist.generics.where_clause)?;
+                self.s.space()?;
+                self.word_space(":")?;
+                let mut real_bounds = Vec::with_capacity(exist.bounds.len());
+                for b in exist.bounds.iter() {
+                    if let TraitTyParamBound(ref ptr, hir::TraitBoundModifier::Maybe) = *b {
+                        self.s.space()?;
+                        self.word_space("for ?")?;
+                        self.print_trait_ref(&ptr.trait_ref)?;
+                    } else {
+                        real_bounds.push(b.clone());
+                    }
+                }
+                self.print_bounds(":", &real_bounds[..])?;
+                self.s.word(";")?;
+                self.end()?; // end the outer ibox
+            }
             hir::ItemEnum(ref enum_definition, ref params) => {
                 self.print_enum_def(enum_definition, params, item.name, item.span, &item.vis)?;
             }
diff --git a/src/librustc/ich/impls_hir.rs b/src/librustc/ich/impls_hir.rs
index a781fc7240a..ed259b28545 100644
--- a/src/librustc/ich/impls_hir.rs
+++ b/src/librustc/ich/impls_hir.rs
@@ -310,6 +310,7 @@ impl_stable_hash_for!(struct hir::BareFnTy {
 
 impl_stable_hash_for!(struct hir::ExistTy {
     generics,
+    impl_trait_fn,
     bounds
 });
 
@@ -323,7 +324,7 @@ impl_stable_hash_for!(enum hir::Ty_ {
     TyTup(ts),
     TyPath(qpath),
     TyTraitObject(trait_refs, lifetime),
-    TyImplTraitExistential(existty, lifetimes),
+    TyImplTraitExistential(existty, def_id, lifetimes),
     TyTypeof(body_id),
     TyErr,
     TyInfer
@@ -889,6 +890,7 @@ impl_stable_hash_for!(enum hir::Item_ {
     ItemForeignMod(foreign_mod),
     ItemGlobalAsm(global_asm),
     ItemTy(ty, generics),
+    ItemExistential(exist),
     ItemEnum(enum_def, generics),
     ItemStruct(variant_data, generics),
     ItemUnion(variant_data, generics),
@@ -1046,6 +1048,7 @@ impl_stable_hash_for!(enum hir::def::Def {
     Struct(def_id),
     Union(def_id),
     Enum(def_id),
+    Existential(def_id),
     Variant(def_id),
     Trait(def_id),
     TyAlias(def_id),
diff --git a/src/librustc/ich/impls_syntax.rs b/src/librustc/ich/impls_syntax.rs
index 3a37c1c18c8..7b14831cf95 100644
--- a/src/librustc/ich/impls_syntax.rs
+++ b/src/librustc/ich/impls_syntax.rs
@@ -411,6 +411,7 @@ impl_stable_hash_for!(enum ::syntax_pos::hygiene::ExpnFormat {
 impl_stable_hash_for!(enum ::syntax_pos::hygiene::CompilerDesugaringKind {
     DotFill,
     QuestionMark,
+    ExistentialReturnType,
     Catch
 });
 
diff --git a/src/librustc/infer/anon_types/mod.rs b/src/librustc/infer/anon_types/mod.rs
index a7879025eea..f068a54ce44 100644
--- a/src/librustc/infer/anon_types/mod.rs
+++ b/src/librustc/infer/anon_types/mod.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 use hir::def_id::DefId;
+use hir;
 use infer::{self, InferCtxt, InferOk, TypeVariableOrigin};
 use infer::outlives::free_region_map::FreeRegionRelations;
 use rustc_data_structures::fx::FxHashMap;
@@ -689,8 +690,16 @@ impl<'a, 'gcx, 'tcx> Instantiator<'a, 'gcx, 'tcx> {
                     // }
                     // ```
                     if let Some(anon_node_id) = tcx.hir.as_local_node_id(def_id) {
-                        let anon_parent_node_id = tcx.hir.get_parent(anon_node_id);
-                        let anon_parent_def_id = tcx.hir.local_def_id(anon_parent_node_id);
+                        let anon_parent_def_id = match tcx.hir.expect_item(anon_node_id).node {
+                            hir::ItemExistential(hir::ExistTy {
+                                impl_trait_fn: Some(parent),
+                                ..
+                            }) => parent,
+                            _ => {
+                                let anon_parent_node_id = tcx.hir.get_parent(anon_node_id);
+                                tcx.hir.local_def_id(anon_parent_node_id)
+                            },
+                        };
                         if self.parent_def_id == anon_parent_def_id {
                             return self.fold_anon_ty(ty, def_id, substs);
                         }
diff --git a/src/librustc/middle/reachable.rs b/src/librustc/middle/reachable.rs
index 6b47a90079a..40cf78edaec 100644
--- a/src/librustc/middle/reachable.rs
+++ b/src/librustc/middle/reachable.rs
@@ -267,6 +267,7 @@ impl<'a, 'tcx> ReachableContext<'a, 'tcx> {
                     // inherently and their children are already in the
                     // worklist, as determined by the privacy pass
                     hir::ItemExternCrate(_) | hir::ItemUse(..) |
+                    hir::ItemExistential(..) |
                     hir::ItemTy(..) | hir::ItemStatic(..) |
                     hir::ItemMod(..) | hir::ItemForeignMod(..) |
                     hir::ItemImpl(..) | hir::ItemTrait(..) | hir::ItemTraitAlias(..) |
diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index 781d48e2123..13fe9a6eef3 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -499,7 +499,13 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                 };
                 self.with(scope, |_, this| intravisit::walk_item(this, item));
             }
+            hir::ItemExistential(hir::ExistTy { impl_trait_fn: Some(_), .. }) => {
+                // currently existential type declarations are just generated from impl Trait
+                // items. doing anything on this node is irrelevant, as we currently don't need
+                // it.
+            }
             hir::ItemTy(_, ref generics)
+            | hir::ItemExistential(hir::ExistTy { impl_trait_fn: None, ref generics, .. })
             | hir::ItemEnum(_, ref generics)
             | hir::ItemStruct(_, ref generics)
             | hir::ItemUnion(_, ref generics)
@@ -613,7 +619,7 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                 };
                 self.with(scope, |_, this| this.visit_ty(&mt.ty));
             }
-            hir::TyImplTraitExistential(ref exist_ty, ref lifetimes) => {
+            hir::TyImplTraitExistential(item_id, _, ref lifetimes) => {
                 // Resolve the lifetimes that are applied to the existential type.
                 // These are resolved in the current scope.
                 // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
@@ -655,10 +661,13 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                 // `abstract type MyAnonTy<'b>: MyTrait<'b>;`
                 //                          ^            ^ this gets resolved in the scope of
                 //                                         the exist_ty generics
-                let hir::ExistTy {
-                    ref generics,
-                    ref bounds,
-                } = *exist_ty;
+                let (generics, bounds) = match self.tcx.hir.expect_item(item_id.id).node {
+                    hir::ItemExistential(hir::ExistTy{ ref generics, ref bounds, .. }) => (
+                        generics,
+                        bounds,
+                    ),
+                    ref i => bug!("impl Trait pointed to non-existential type?? {:#?}", i),
+                };
 
                 // We want to start our early-bound indices at the end of the parent scope,
                 // not including any parent `impl Trait`s.
diff --git a/src/librustc/traits/query/normalize.rs b/src/librustc/traits/query/normalize.rs
index f08b95f59fa..d0ae0bdac8c 100644
--- a/src/librustc/traits/query/normalize.rs
+++ b/src/librustc/traits/query/normalize.rs
@@ -123,6 +123,11 @@ impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for QueryNormalizer<'cx, 'gcx, 'tcx
                         let generic_ty = self.tcx().type_of(def_id);
                         let concrete_ty = generic_ty.subst(self.tcx(), substs);
                         self.anon_depth += 1;
+                        if concrete_ty == ty {
+                            println!("generic_ty: {:#?}", generic_ty);
+                            println!("substs {:#?}", substs);
+                        }
+                        assert_ne!(concrete_ty, ty, "infinite recursion");
                         let folded_ty = self.fold_ty(concrete_ty);
                         self.anon_depth -= 1;
                         folded_ty
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 4fb5602971c..6cbf4fad02c 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -427,6 +427,10 @@ pub struct TypeckTables<'tcx> {
     /// its where clauses and parameter types. These are then
     /// read-again by borrowck.
     pub free_region_map: FreeRegionMap<'tcx>,
+
+    /// All the existential types that are restricted to concrete types
+    /// by this function
+    pub concrete_existential_types: FxHashMap<DefId, Ty<'tcx>>,
 }
 
 impl<'tcx> TypeckTables<'tcx> {
@@ -449,6 +453,7 @@ impl<'tcx> TypeckTables<'tcx> {
             used_trait_imports: Lrc::new(DefIdSet()),
             tainted_by_errors: false,
             free_region_map: FreeRegionMap::new(),
+            concrete_existential_types: FxHashMap(),
         }
     }
 
@@ -746,6 +751,7 @@ impl<'a, 'gcx> HashStable<StableHashingContext<'a>> for TypeckTables<'gcx> {
             ref used_trait_imports,
             tainted_by_errors,
             ref free_region_map,
+            ref concrete_existential_types,
         } = *self;
 
         hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
@@ -786,6 +792,7 @@ impl<'a, 'gcx> HashStable<StableHashingContext<'a>> for TypeckTables<'gcx> {
             used_trait_imports.hash_stable(hcx, hasher);
             tainted_by_errors.hash_stable(hcx, hasher);
             free_region_map.hash_stable(hcx, hasher);
+            concrete_existential_types.hash_stable(hcx, hasher);
         })
     }
 }
diff --git a/src/librustc/ty/item_path.rs b/src/librustc/ty/item_path.rs
index 87ace45a905..d858ba7acf7 100644
--- a/src/librustc/ty/item_path.rs
+++ b/src/librustc/ty/item_path.rs
@@ -221,7 +221,8 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             data @ DefPathData::AnonConst |
             data @ DefPathData::MacroDef(..) |
             data @ DefPathData::ClosureExpr |
-            data @ DefPathData::ImplTrait |
+            data @ DefPathData::ExistentialImplTrait |
+            data @ DefPathData::UniversalImplTrait |
             data @ DefPathData::GlobalMetaData(..) => {
                 let parent_def_id = self.parent_def_id(def_id).unwrap();
                 self.push_item_path(buffer, parent_def_id);
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 2758503c60c..229e5606afa 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -2857,6 +2857,12 @@ fn trait_of_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> Option
 fn param_env<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                        def_id: DefId)
                        -> ParamEnv<'tcx> {
+
+    // The param_env of an existential type is its parent's param_env
+    if let Some(Def::Existential(_)) = tcx.describe_def(def_id) {
+        let parent = tcx.parent_def_id(def_id).expect("impl trait item w/o a parent");
+        return param_env(tcx, parent);
+    }
     // Compute the bounds on Self and the type parameters.
 
     let bounds = tcx.predicates_of(def_id).instantiate_identity(tcx);
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 4e7df0cac12..e9a9c4567bb 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -291,7 +291,8 @@ impl PrintContext {
                     DefPathData::Field(_) |
                     DefPathData::StructCtor |
                     DefPathData::AnonConst |
-                    DefPathData::ImplTrait |
+                    DefPathData::ExistentialImplTrait |
+                    DefPathData::UniversalImplTrait |
                     DefPathData::GlobalMetaData(_) => {
                         // if we're making a symbol for something, there ought
                         // to be a value or type-def or something in there
diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index 17e0472bda9..5679cb4b610 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -256,6 +256,7 @@ impl<'a, 'gcx, 'tcx> Env<'a, 'gcx, 'tcx> {
                 hir::ItemFn(..) |
                 hir::ItemForeignMod(..) |
                 hir::ItemGlobalAsm(..) |
+                hir::ItemExistential(..) |
                 hir::ItemTy(..) => None,
 
                 hir::ItemEnum(..) |
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index fd00cde375b..9e4f695d28f 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -419,6 +419,7 @@ impl<'tcx> EntryKind<'tcx> {
             EntryKind::ForeignFn(_) => Def::Fn(did),
             EntryKind::Method(_) => Def::Method(did),
             EntryKind::Type => Def::TyAlias(did),
+            EntryKind::Existential => Def::Existential(did),
             EntryKind::AssociatedType(_) => Def::AssociatedTy(did),
             EntryKind::Mod(_) => Def::Mod(did),
             EntryKind::Variant(_) => Def::Variant(did),
diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs
index ab30ff7f072..33d4df1c3a5 100644
--- a/src/librustc_metadata/encoder.rs
+++ b/src/librustc_metadata/encoder.rs
@@ -1060,6 +1060,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> {
             hir::ItemForeignMod(_) => EntryKind::ForeignMod,
             hir::ItemGlobalAsm(..) => EntryKind::GlobalAsm,
             hir::ItemTy(..) => EntryKind::Type,
+            hir::ItemExistential(..) => EntryKind::Existential,
             hir::ItemEnum(..) => EntryKind::Enum(get_repr_options(&tcx, def_id)),
             hir::ItemStruct(ref struct_def, _) => {
                 let variant = tcx.adt_def(def_id).non_enum_variant();
@@ -1187,6 +1188,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> {
                 hir::ItemConst(..) |
                 hir::ItemFn(..) |
                 hir::ItemTy(..) |
+                hir::ItemExistential(..) |
                 hir::ItemEnum(..) |
                 hir::ItemStruct(..) |
                 hir::ItemUnion(..) |
@@ -1210,6 +1212,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> {
                 hir::ItemStruct(..) |
                 hir::ItemUnion(..) |
                 hir::ItemImpl(..) |
+                hir::ItemExistential(..) |
                 hir::ItemTrait(..) => Some(self.encode_generics(def_id)),
                 _ => None,
             },
@@ -1222,6 +1225,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> {
                 hir::ItemStruct(..) |
                 hir::ItemUnion(..) |
                 hir::ItemImpl(..) |
+                hir::ItemExistential(..) |
                 hir::ItemTrait(..) => Some(self.encode_predicates(def_id)),
                 _ => None,
             },
@@ -1301,28 +1305,6 @@ impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> {
         }
     }
 
-    fn encode_info_for_anon_ty(&mut self, def_id: DefId) -> Entry<'tcx> {
-        debug!("IsolatedEncoder::encode_info_for_anon_ty({:?})", def_id);
-        let tcx = self.tcx;
-        Entry {
-            kind: EntryKind::Type,
-            visibility: self.lazy(&ty::Visibility::Public),
-            span: self.lazy(&tcx.def_span(def_id)),
-            attributes: LazySeq::empty(),
-            children: LazySeq::empty(),
-            stability: None,
-            deprecation: None,
-
-            ty: Some(self.encode_item_type(def_id)),
-            inherent_impls: LazySeq::empty(),
-            variances: LazySeq::empty(),
-            generics: Some(self.encode_generics(def_id)),
-            predicates: Some(self.encode_predicates(def_id)),
-
-            mir: None,
-        }
-    }
-
     fn encode_info_for_closure(&mut self, def_id: DefId) -> Entry<'tcx> {
         debug!("IsolatedEncoder::encode_info_for_closure({:?})", def_id);
         let tcx = self.tcx;
@@ -1672,10 +1654,6 @@ impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
 
     fn encode_info_for_ty(&mut self, ty: &hir::Ty) {
         match ty.node {
-            hir::TyImplTraitExistential(..) => {
-                let def_id = self.tcx.hir.local_def_id(ty.id);
-                self.record(def_id, IsolatedEncoder::encode_info_for_anon_ty, def_id);
-            }
             hir::TyArray(_, ref length) => {
                 let def_id = self.tcx.hir.local_def_id(length.id);
                 self.record(def_id, IsolatedEncoder::encode_info_for_anon_const, def_id);
@@ -1710,6 +1688,7 @@ impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
             hir::ItemExternCrate(..) |
             hir::ItemUse(..) |
             hir::ItemTy(..) |
+            hir::ItemExistential(..) |
             hir::ItemTraitAlias(..) => {
                 // no sub-item recording needed in these cases
             }
diff --git a/src/librustc_metadata/schema.rs b/src/librustc_metadata/schema.rs
index 2e89ea6d2c1..21d6d15457a 100644
--- a/src/librustc_metadata/schema.rs
+++ b/src/librustc_metadata/schema.rs
@@ -304,6 +304,7 @@ pub enum EntryKind<'tcx> {
     ForeignType,
     GlobalAsm,
     Type,
+    Existential,
     Enum(ReprOptions),
     Field,
     Variant(Lazy<VariantData<'tcx>>),
@@ -336,6 +337,7 @@ impl<'a, 'gcx> HashStable<StableHashingContext<'a>> for EntryKind<'gcx> {
             EntryKind::GlobalAsm        |
             EntryKind::ForeignType      |
             EntryKind::Field |
+            EntryKind::Existential |
             EntryKind::Type => {
                 // Nothing else to hash here.
             }
diff --git a/src/librustc_mir/monomorphize/collector.rs b/src/librustc_mir/monomorphize/collector.rs
index a8a50c50f59..1fb12172838 100644
--- a/src/librustc_mir/monomorphize/collector.rs
+++ b/src/librustc_mir/monomorphize/collector.rs
@@ -944,6 +944,7 @@ impl<'b, 'a, 'v> ItemLikeVisitor<'v> for RootCollector<'b, 'a, 'v> {
             hir::ItemTy(..)          |
             hir::ItemTrait(..)       |
             hir::ItemTraitAlias(..)  |
+            hir::ItemExistential(..) |
             hir::ItemMod(..)         => {
                 // Nothing to do, just keep recursing...
             }
diff --git a/src/librustc_privacy/lib.rs b/src/librustc_privacy/lib.rs
index 308c5b9f201..291092015b5 100644
--- a/src/librustc_privacy/lib.rs
+++ b/src/librustc_privacy/lib.rs
@@ -160,6 +160,7 @@ impl<'a, 'tcx> Visitor<'tcx> for EmbargoVisitor<'a, 'tcx> {
             hir::ItemGlobalAsm(..) | hir::ItemFn(..) | hir::ItemMod(..) |
             hir::ItemStatic(..) | hir::ItemStruct(..) |
             hir::ItemTrait(..) | hir::ItemTraitAlias(..) |
+            hir::ItemExistential(..) |
             hir::ItemTy(..) | hir::ItemUnion(..) | hir::ItemUse(..) => {
                 if item.vis == hir::Public { self.prev_level } else { None }
             }
@@ -212,6 +213,7 @@ impl<'a, 'tcx> Visitor<'tcx> for EmbargoVisitor<'a, 'tcx> {
                     }
                 }
             }
+            hir::ItemExistential(..) |
             hir::ItemUse(..) | hir::ItemStatic(..) | hir::ItemConst(..) |
             hir::ItemGlobalAsm(..) | hir::ItemTy(..) | hir::ItemMod(..) | hir::ItemTraitAlias(..) |
             hir::ItemFn(..) | hir::ItemExternCrate(..) => {}
@@ -227,6 +229,8 @@ impl<'a, 'tcx> Visitor<'tcx> for EmbargoVisitor<'a, 'tcx> {
             hir::ItemUse(..) => {}
             // The interface is empty
             hir::ItemGlobalAsm(..) => {}
+            // Checked by visit_ty
+            hir::ItemExistential(..) => {}
             // Visit everything
             hir::ItemConst(..) | hir::ItemStatic(..) |
             hir::ItemFn(..) | hir::ItemTy(..) => {
@@ -388,10 +392,10 @@ impl<'a, 'tcx> Visitor<'tcx> for EmbargoVisitor<'a, 'tcx> {
     }
 
     fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
-        if let hir::TyImplTraitExistential(..) = ty.node {
-            if self.get(ty.id).is_some() {
-                // Reach the (potentially private) type and the API being exposed.
-                self.reach(ty.id).ty().predicates();
+        if let hir::TyImplTraitExistential(item_id, _, _) = ty.node {
+            if self.get(item_id.id).is_some() {
+                // Reach the (potentially private) type and the API being exposed
+                self.reach(item_id.id).ty().predicates();
             }
         }
 
@@ -436,6 +440,10 @@ impl<'b, 'a, 'tcx> ReachEverythingInTheInterfaceVisitor<'b, 'a, 'tcx> {
 
     fn ty(&mut self) -> &mut Self {
         let ty = self.ev.tcx.type_of(self.item_def_id);
+        self.walk_ty(ty)
+    }
+
+    fn walk_ty(&mut self, ty: Ty<'tcx>) -> &mut Self {
         ty.visit_with(self);
         if let ty::TyFnDef(def_id, _) = ty.sty {
             if def_id == self.item_def_id {
@@ -1546,6 +1554,8 @@ impl<'a, 'tcx> Visitor<'tcx> for PrivateItemsInPublicInterfacesVisitor<'a, 'tcx>
             hir::ItemUse(..) => {}
             // No subitems
             hir::ItemGlobalAsm(..) => {}
+            // Checked in visit_ty
+            hir::ItemExistential(..) => {}
             // Subitems of these items have inherited publicity
             hir::ItemConst(..) | hir::ItemStatic(..) | hir::ItemFn(..) |
             hir::ItemTy(..) => {
@@ -1644,13 +1654,14 @@ impl<'a, 'tcx> Visitor<'tcx> for PrivateItemsInPublicInterfacesVisitor<'a, 'tcx>
     }
 
     fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
-        if let hir::TyImplTraitExistential(..) = ty.node {
+        if let hir::TyImplTraitExistential(ref exist_item, _, _) = ty.node {
             // Check the traits being exposed, as they're separate,
             // e.g. `impl Iterator<Item=T>` has two predicates,
             // `X: Iterator` and `<X as Iterator>::Item == T`,
             // where `X` is the `impl Iterator<Item=T>` itself,
             // stored in `predicates_of`, not in the `Ty` itself.
-            self.check(ty.id, self.inner_visibility).predicates();
+
+            self.check(exist_item.id, self.inner_visibility).predicates();
         }
 
         intravisit::walk_ty(self, ty);
diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index 2471430798e..a2b2096ccaa 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -205,6 +205,7 @@ fn resolve_struct_error<'sess, 'a>(resolver: &'sess Resolver,
                 Def::AssociatedTy(..) | Def::PrimTy(..) | Def::Fn(..) | Def::Const(..) |
                 Def::Static(..) | Def::StructCtor(..) | Def::VariantCtor(..) | Def::Method(..) |
                 Def::AssociatedConst(..) | Def::Local(..) | Def::Upvar(..) | Def::Label(..) |
+                Def::Existential(..) |
                 Def::Macro(..) | Def::GlobalAsm(..) | Def::Err =>
                     bug!("TypeParametersFromOuterFunction should only be used with Def::SelfTy or \
                          Def::TyParam")
diff --git a/src/librustc_save_analysis/lib.rs b/src/librustc_save_analysis/lib.rs
index 64dcd3e5175..f9510970e43 100644
--- a/src/librustc_save_analysis/lib.rs
+++ b/src/librustc_save_analysis/lib.rs
@@ -749,6 +749,7 @@ impl<'l, 'tcx: 'l> SaveContext<'l, 'tcx> {
             HirDef::TraitAlias(def_id) |
             HirDef::AssociatedTy(def_id) |
             HirDef::Trait(def_id) |
+            HirDef::Existential(def_id) |
             HirDef::TyParam(def_id) => {
                 let span = self.span_from_span(sub_span);
                 Some(Ref {
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index f2e32286e9e..18911b47ed1 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -1118,8 +1118,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
             hir::TyTraitObject(ref bounds, ref lifetime) => {
                 self.conv_object_ty_poly_trait_ref(ast_ty.span, bounds, lifetime)
             }
-            hir::TyImplTraitExistential(_, ref lifetimes) => {
-                let def_id = tcx.hir.local_def_id(ast_ty.id);
+            hir::TyImplTraitExistential(_, def_id, ref lifetimes) => {
                 self.impl_trait_ty_to_ty(def_id, lifetimes)
             }
             hir::TyPath(hir::QPath::Resolved(ref maybe_qself, ref path)) => {
@@ -1171,9 +1170,14 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
         result_ty
     }
 
-    pub fn impl_trait_ty_to_ty(&self, def_id: DefId, lifetimes: &[hir::Lifetime]) -> Ty<'tcx> {
+    pub fn impl_trait_ty_to_ty(
+        &self,
+        def_id: DefId,
+        lifetimes: &[hir::Lifetime],
+    ) -> Ty<'tcx> {
         debug!("impl_trait_ty_to_ty(def_id={:?}, lifetimes={:?})", def_id, lifetimes);
         let tcx = self.tcx();
+
         let generics = tcx.generics_of(def_id);
 
         debug!("impl_trait_ty_to_ty: generics={:?}", generics);
@@ -1198,7 +1202,9 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
         });
         debug!("impl_trait_ty_to_ty: final substs = {:?}", substs);
 
-        tcx.mk_anon(def_id, substs)
+        let ty = tcx.mk_anon(def_id, substs);
+        debug!("impl_trait_ty_to_ty: {}", ty);
+        ty
     }
 
     pub fn ty_of_arg(&self,
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 7dcd6d1a3b3..d68fc67073e 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -1013,7 +1013,7 @@ fn check_fn<'a, 'gcx, 'tcx>(inherited: &'a Inherited<'a, 'gcx, 'tcx>,
     debug!("check_fn(sig={:?}, fn_id={}, param_env={:?})", fn_sig, fn_id, param_env);
 
     // Create the function context.  This is either derived from scratch or,
-    // in the case of function expressions, based on the outer context.
+    // in the case of closures, based on the outer context.
     let mut fcx = FnCtxt::new(inherited, param_env, body.value.id);
     *fcx.ps.borrow_mut() = UnsafetyState::function(fn_sig.unsafety, fn_id);
 
diff --git a/src/librustc_typeck/check/writeback.rs b/src/librustc_typeck/check/writeback.rs
index f295d1763c4..f7d1e407945 100644
--- a/src/librustc_typeck/check/writeback.rs
+++ b/src/librustc_typeck/check/writeback.rs
@@ -43,7 +43,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();
+        wbcx.visit_anon_types(body.value.span);
         wbcx.visit_cast_types();
         wbcx.visit_free_region_map();
         wbcx.visit_user_provided_tys();
@@ -385,18 +385,28 @@ impl<'cx, 'gcx, 'tcx> WritebackCx<'cx, 'gcx, 'tcx> {
         }
     }
 
-    fn visit_anon_types(&mut self) {
-        let gcx = self.tcx().global_tcx();
+    fn visit_anon_types(&mut self, span: Span) {
         for (&def_id, anon_defn) in self.fcx.anon_types.borrow().iter() {
-            let node_id = gcx.hir.as_local_node_id(def_id).unwrap();
+            let node_id = self.tcx().hir.as_local_node_id(def_id).unwrap();
             let instantiated_ty = self.resolve(&anon_defn.concrete_ty, &node_id);
             let definition_ty = self.fcx.infer_anon_definition_from_instantiation(
                 def_id,
                 anon_defn,
                 instantiated_ty,
             );
-            let hir_id = self.tcx().hir.node_to_hir_id(node_id);
-            self.tables.node_types_mut().insert(hir_id, definition_ty);
+            let old = self.tables.concrete_existential_types.insert(def_id, definition_ty);
+            if let Some(old) = old {
+                if old != definition_ty {
+                    span_bug!(
+                        span,
+                        "visit_anon_types tried to write \
+                        different types for the same existential type: {:?}, {:?}, {:?}",
+                        def_id,
+                        definition_ty,
+                        old,
+                    );
+                }
+            }
         }
     }
 
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 05256be6ec9..fe55ca66379 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -131,15 +131,6 @@ impl<'a, 'tcx> Visitor<'tcx> for CollectItemTypesVisitor<'a, 'tcx> {
         intravisit::walk_expr(self, expr);
     }
 
-    fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
-        if let hir::TyImplTraitExistential(..) = ty.node {
-            let def_id = self.tcx.hir.local_def_id(ty.id);
-            self.tcx.generics_of(def_id);
-            self.tcx.predicates_of(def_id);
-        }
-        intravisit::walk_ty(self, ty);
-    }
-
     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
         convert_trait_item(self.tcx, trait_item.id);
         intravisit::walk_trait_item(self, trait_item);
@@ -420,6 +411,7 @@ fn convert_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, item_id: ast::NodeId) {
                 convert_variant_ctor(tcx, struct_def.id());
             }
         },
+        hir::ItemExistential(..) |
         hir::ItemTy(..) | hir::ItemStatic(..) | hir::ItemConst(..) | hir::ItemFn(..) => {
             tcx.generics_of(def_id);
             tcx.type_of(def_id);
@@ -803,18 +795,12 @@ fn generics_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         NodeExpr(&hir::Expr { node: hir::ExprClosure(..), .. }) => {
             Some(tcx.closure_base_def_id(def_id))
         }
-        NodeTy(&hir::Ty { node: hir::TyImplTraitExistential(..), .. }) => {
-            let mut parent_id = node_id;
-            loop {
-                match tcx.hir.get(parent_id) {
-                    NodeItem(_) | NodeImplItem(_) | NodeTraitItem(_) => break,
-                    _ => {
-                        parent_id = tcx.hir.get_parent_node(parent_id);
-                    }
-                }
+        NodeItem(item) => {
+            match item.node {
+                ItemExistential(hir::ExistTy { impl_trait_fn, .. }) => impl_trait_fn,
+                _ => None,
             }
-            Some(tcx.hir.local_def_id(parent_id))
-        }
+        },
         _ => None
     };
 
@@ -835,6 +821,7 @@ fn generics_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                 ItemTy(_, ref generics) |
                 ItemEnum(_, ref generics) |
                 ItemStruct(_, ref generics) |
+                ItemExistential(hir::ExistTy { ref generics, .. }) |
                 ItemUnion(_, ref generics) => {
                     allow_defaults = true;
                     generics
@@ -875,8 +862,8 @@ fn generics_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
             }
         }
 
-        NodeTy(&hir::Ty { node: hir::TyImplTraitExistential(ref exist_ty, _), .. }) => {
-            &exist_ty.generics
+        NodeTy(&hir::Ty { node: hir::TyImplTraitExistential(..), .. }) => {
+            bug!("impl Trait is desugared to existential type items");
         }
 
         _ => &no_generics,
@@ -1056,6 +1043,12 @@ fn type_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                     let substs = Substs::identity_for_item(tcx, def_id);
                     tcx.mk_adt(def, substs)
                 }
+                // this is only reachable once we have named existential types
+                ItemExistential(hir::ExistTy { impl_trait_fn: None, .. }) => unimplemented!(),
+                // existential types desugared from impl Trait
+                ItemExistential(hir::ExistTy { impl_trait_fn: Some(owner), .. }) => {
+                    tcx.typeck_tables_of(owner).concrete_existential_types[&def_id]
+                },
                 ItemTrait(..) | ItemTraitAlias(..) |
                 ItemMod(..) |
                 ItemForeignMod(..) |
@@ -1130,12 +1123,6 @@ fn type_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
             icx.to_ty(ty)
         }
 
-        NodeTy(&hir::Ty { node: TyImplTraitExistential(..), .. }) => {
-            let owner = tcx.hir.get_parent_did(node_id);
-            let hir_id = tcx.hir.node_to_hir_id(node_id);
-            tcx.typeck_tables_of(owner).node_id_to_type(hir_id)
-        }
-
         x => {
             bug!("unexpected sort of node in type_of_def_id(): {:?}", x);
         }
@@ -1353,6 +1340,24 @@ pub fn explicit_predicates_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                     }, items));
                     generics
                 }
+                ItemExistential(ref exist_ty) => {
+                    let substs = Substs::identity_for_item(tcx, def_id);
+                    let anon_ty = tcx.mk_anon(def_id, substs);
+
+                    // Collect the bounds, i.e. the `A+B+'c` in `impl A+B+'c`.
+                    let bounds = compute_bounds(&icx,
+                                                anon_ty,
+                                                &exist_ty.bounds,
+                                                SizedByDefault::Yes,
+                                                tcx.def_span(def_id));
+
+                    let predicates = bounds.predicates(tcx, anon_ty);
+
+                    return ty::GenericPredicates {
+                        parent: None,
+                        predicates: predicates
+                    };
+                }
 
                 _ => &no_generics,
             }
@@ -1366,31 +1371,6 @@ pub fn explicit_predicates_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
             }
         }
 
-        NodeTy(&Ty { node: TyImplTraitExistential(ref exist_ty, _), span, .. }) => {
-            let substs = Substs::identity_for_item(tcx, def_id);
-            let anon_ty = tcx.mk_anon(def_id, substs);
-
-            debug!("explicit_predicates_of: anon_ty={:?}", anon_ty);
-
-            // Collect the bounds, i.e. the `A+B+'c` in `impl A+B+'c`.
-            let bounds = compute_bounds(&icx,
-                                        anon_ty,
-                                        &exist_ty.bounds,
-                                        SizedByDefault::Yes,
-                                        span);
-
-            debug!("explicit_predicates_of: bounds={:?}", bounds);
-
-            let predicates = bounds.predicates(tcx, anon_ty);
-
-            debug!("explicit_predicates_of: predicates={:?}", predicates);
-
-            return ty::GenericPredicates {
-                parent: None,
-                predicates: predicates
-            };
-        }
-
         _ => &no_generics,
     };
 
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index 8d3cf223509..852a4479199 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -2939,7 +2939,14 @@ impl Clean<Type> for hir::Ty {
                 }
             }
             TyBareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
-            TyImplTraitExistential(ref exist_ty, ref _lts) => ImplTrait(exist_ty.bounds.clean(cx)),
+            TyImplTraitExistential(hir_id, _, _) => {
+                match cx.tcx.hir.expect_item(hir_id.id).node {
+                    hir::ItemExistential(ref exist_ty) => {
+                        ImplTrait(exist_ty.bounds.clean(cx))
+                    },
+                    ref other => panic!("impl Trait pointed to {:#?}", other),
+                }
+            },
             TyInfer | TyErr => Infer,
             TyTypeof(..) => panic!("Unimplemented type {:?}", self.node),
         }
diff --git a/src/librustdoc/visit_ast.rs b/src/librustdoc/visit_ast.rs
index 44b41439511..10b1a2e1e0b 100644
--- a/src/librustdoc/visit_ast.rs
+++ b/src/librustdoc/visit_ast.rs
@@ -564,6 +564,9 @@ impl<'a, 'tcx, 'rcx> RustdocVisitor<'a, 'tcx, 'rcx> {
                     om.impls.push(i);
                 }
             },
+            hir::ItemExistential(_) => {
+                // FIXME(oli-obk): actually generate docs for real existential items
+            }
         }
     }
 
diff --git a/src/libsyntax_pos/hygiene.rs b/src/libsyntax_pos/hygiene.rs
index 1365ac396ff..6dd910fba82 100644
--- a/src/libsyntax_pos/hygiene.rs
+++ b/src/libsyntax_pos/hygiene.rs
@@ -489,6 +489,10 @@ pub enum CompilerDesugaringKind {
     DotFill,
     QuestionMark,
     Catch,
+    /// Desugaring of an `impl Trait` in return type position
+    /// to an `existential type Foo: Trait;` + replacing the
+    /// `impl Trait` with `Foo`.
+    ExistentialReturnType,
 }
 
 impl CompilerDesugaringKind {
@@ -498,6 +502,7 @@ impl CompilerDesugaringKind {
             DotFill => "...",
             QuestionMark => "?",
             Catch => "do catch",
+            ExistentialReturnType => "existental type",
         };
         Symbol::intern(s)
     }
diff --git a/src/test/incremental/hashes/function_interfaces.rs b/src/test/incremental/hashes/function_interfaces.rs
index 09cc5380d27..03860ae2122 100644
--- a/src/test/incremental/hashes/function_interfaces.rs
+++ b/src/test/incremental/hashes/function_interfaces.rs
@@ -284,7 +284,7 @@ pub fn change_return_impl_trait() -> impl Clone {
 }
 
 #[cfg(not(cfail1))]
-#[rustc_clean(cfg = "cfail2", except = "Hir, HirBody")]
+#[rustc_clean(cfg = "cfail2")]
 #[rustc_clean(cfg = "cfail3")]
 pub fn change_return_impl_trait() -> impl Copy {
     0u32
diff --git a/src/test/run-pass/impl-trait/auxiliary/xcrate.rs b/src/test/run-pass/impl-trait/auxiliary/xcrate.rs
index c27a2dd89d5..6e2944e8400 100644
--- a/src/test/run-pass/impl-trait/auxiliary/xcrate.rs
+++ b/src/test/run-pass/impl-trait/auxiliary/xcrate.rs
@@ -23,3 +23,7 @@ pub fn return_closure_accessing_internal_fn() -> impl Fn() -> u32 {
         some_internal_fn() + 1
     }
 }
+
+pub fn return_internal_fn() -> impl Fn() -> u32 {
+    some_internal_fn
+}
diff --git a/src/test/run-pass/impl-trait/bounds_regression.rs b/src/test/run-pass/impl-trait/bounds_regression.rs
new file mode 100644
index 00000000000..cc931a68edd
--- /dev/null
+++ b/src/test/run-pass/impl-trait/bounds_regression.rs
@@ -0,0 +1,32 @@
+// Copyright 2018 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.
+
+pub trait FakeGenerator {
+    type Yield;
+    type Return;
+}
+
+pub trait FakeFuture {
+    type Output;
+}
+
+pub fn future_from_generator<
+    T: FakeGenerator<Yield = ()>
+>(x: T) -> impl FakeFuture<Output = T::Return> {
+    GenFuture(x)
+}
+
+struct GenFuture<T: FakeGenerator<Yield = ()>>(T);
+
+impl<T: FakeGenerator<Yield = ()>> FakeFuture for GenFuture<T> {
+    type Output = T::Return;
+}
+
+fn main() {}
diff --git a/src/test/run-pass/impl-trait/example-calendar.rs b/src/test/run-pass/impl-trait/example-calendar.rs
index e3b7322e48b..fce31256db4 100644
--- a/src/test/run-pass/impl-trait/example-calendar.rs
+++ b/src/test/run-pass/impl-trait/example-calendar.rs
@@ -14,8 +14,6 @@
 #![feature(fn_traits,
            step_trait,
            unboxed_closures,
-           copy_closures,
-           clone_closures
 )]
 
 //! Derived from: <https://raw.githubusercontent.com/quickfur/dcal/master/dcal.d>.
diff --git a/src/test/run-pass/impl-trait/existential-minimal.rs b/src/test/run-pass/impl-trait/existential-minimal.rs
new file mode 100644
index 00000000000..4e9d786dda0
--- /dev/null
+++ b/src/test/run-pass/impl-trait/existential-minimal.rs
@@ -0,0 +1,13 @@
+// Copyright 2018 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 main() {}
+
+fn foo() -> impl std::fmt::Debug { "cake" }
diff --git a/src/test/run-pass/impl-trait/nesting.rs b/src/test/run-pass/impl-trait/nesting.rs
new file mode 100644
index 00000000000..73e6c1c0d1d
--- /dev/null
+++ b/src/test/run-pass/impl-trait/nesting.rs
@@ -0,0 +1,22 @@
+// Copyright 2018 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<T>(t: T) -> impl Into<[T; { const FOO: usize = 1; FOO }]> {
+    [t]
+}
+
+fn bar() -> impl Into<[u8; { const FOO: usize = 1; FOO }]> {
+    [99]
+}
+
+fn main() {
+    println!("{:?}", foo(42).into());
+    println!("{:?}", bar().into());
+}
diff --git a/src/test/run-pass/impl-trait/xcrate_simple.rs b/src/test/run-pass/impl-trait/xcrate_simple.rs
new file mode 100644
index 00000000000..8d4086cc880
--- /dev/null
+++ b/src/test/run-pass/impl-trait/xcrate_simple.rs
@@ -0,0 +1,17 @@
+// 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.
+
+// aux-build:xcrate.rs
+
+extern crate xcrate;
+
+fn main() {
+    xcrate::return_internal_fn()();
+}
diff --git a/src/test/ui/impl-trait/auto-trait-leak.rs b/src/test/ui/impl-trait/auto-trait-leak.rs
index 54d54875764..abb3682a498 100644
--- a/src/test/ui/impl-trait/auto-trait-leak.rs
+++ b/src/test/ui/impl-trait/auto-trait-leak.rs
@@ -13,27 +13,9 @@
 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
-
-    send(after());
-    //~^ ERROR the trait bound `std::rc::Rc<std::cell::Cell<i32>>: std::marker::Send` is not satisfied
-}
-
-// 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
@@ -41,7 +23,9 @@ fn after() -> impl Fn(i32) {
 // return type, which can't depend on the obligation.
 fn cycle1() -> impl Clone {
     //~^ ERROR cycle detected
+    //~| ERROR cycle detected
     send(cycle2().clone());
+    //~^ ERROR Send` is not satisfied
 
     Rc::new(Cell::new(5))
 }
diff --git a/src/test/ui/impl-trait/auto-trait-leak.stderr b/src/test/ui/impl-trait/auto-trait-leak.stderr
index efa9a58d633..4537c96c4ab 100644
--- a/src/test/ui/impl-trait/auto-trait-leak.stderr
+++ b/src/test/ui/impl-trait/auto-trait-leak.stderr
@@ -1,58 +1,65 @@
-error[E0277]: the trait bound `std::rc::Rc<std::cell::Cell<i32>>: std::marker::Send` is not satisfied in `impl std::ops::Fn<(i32,)>`
-  --> $DIR/auto-trait-leak.rs:25:5
+error[E0391]: cycle detected when processing `cycle1::{{exist-impl-Trait}}`
+  --> $DIR/auto-trait-leak.rs:24:16
    |
-LL |     send(before());
-   |     ^^^^ `std::rc::Rc<std::cell::Cell<i32>>` cannot be sent between threads safely
+LL | fn cycle1() -> impl Clone {
+   |                ^^^^^^^^^^
    |
-   = help: within `impl std::ops::Fn<(i32,)>`, the trait `std::marker::Send` is not implemented for `std::rc::Rc<std::cell::Cell<i32>>`
-   = note: required because it appears within the type `[closure@$DIR/auto-trait-leak.rs:19:5: 19:22 p:std::rc::Rc<std::cell::Cell<i32>>]`
-   = note: required because it appears within the type `impl std::ops::Fn<(i32,)>`
-note: required by `send`
-  --> $DIR/auto-trait-leak.rs:22:1
+note: ...which requires processing `cycle1`...
+  --> $DIR/auto-trait-leak.rs:24:1
    |
-LL | fn send<T: Send>(_: T) {}
-   | ^^^^^^^^^^^^^^^^^^^^^^
-
-error[E0277]: the trait bound `std::rc::Rc<std::cell::Cell<i32>>: std::marker::Send` is not satisfied in `impl std::ops::Fn<(i32,)>`
-  --> $DIR/auto-trait-leak.rs:28:5
-   |
-LL |     send(after());
-   |     ^^^^ `std::rc::Rc<std::cell::Cell<i32>>` cannot be sent between threads safely
+LL | fn cycle1() -> impl Clone {
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^
+note: ...which requires evaluating trait selection obligation `impl std::clone::Clone: std::marker::Send`...
+note: ...which requires processing `cycle2::{{exist-impl-Trait}}`...
+  --> $DIR/auto-trait-leak.rs:33:16
    |
-   = help: within `impl std::ops::Fn<(i32,)>`, the trait `std::marker::Send` is not implemented for `std::rc::Rc<std::cell::Cell<i32>>`
-   = note: required because it appears within the type `[closure@$DIR/auto-trait-leak.rs:36:5: 36:22 p:std::rc::Rc<std::cell::Cell<i32>>]`
-   = note: required because it appears within the type `impl std::ops::Fn<(i32,)>`
-note: required by `send`
-  --> $DIR/auto-trait-leak.rs:22:1
+LL | fn cycle2() -> impl Clone {
+   |                ^^^^^^^^^^
+note: ...which requires processing `cycle2`...
+  --> $DIR/auto-trait-leak.rs:33:1
    |
-LL | fn send<T: Send>(_: T) {}
-   | ^^^^^^^^^^^^^^^^^^^^^^
+LL | fn cycle2() -> impl Clone {
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^
+note: ...which requires evaluating trait selection obligation `impl std::clone::Clone: std::marker::Send`...
+   = note: ...which again requires processing `cycle1::{{exist-impl-Trait}}`, completing the cycle
 
-error[E0391]: cycle detected when processing `cycle1`
-  --> $DIR/auto-trait-leak.rs:42:1
+error[E0391]: cycle detected when processing `cycle1::{{exist-impl-Trait}}`
+  --> $DIR/auto-trait-leak.rs:24:16
    |
 LL | fn cycle1() -> impl Clone {
-   | ^^^^^^^^^^^^^^^^^^^^^^^^^
+   |                ^^^^^^^^^^
    |
+note: ...which requires processing `cycle1`...
+  --> $DIR/auto-trait-leak.rs:24:1
+   |
+LL | fn cycle1() -> impl Clone {
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^
 note: ...which requires evaluating trait selection obligation `impl std::clone::Clone: std::marker::Send`...
-note: ...which requires processing `cycle2::{{impl-Trait}}`...
-  --> $DIR/auto-trait-leak.rs:49:16
+note: ...which requires processing `cycle2::{{exist-impl-Trait}}`...
+  --> $DIR/auto-trait-leak.rs:33:16
    |
 LL | fn cycle2() -> impl Clone {
    |                ^^^^^^^^^^
 note: ...which requires processing `cycle2`...
-  --> $DIR/auto-trait-leak.rs:49:1
+  --> $DIR/auto-trait-leak.rs:33:1
    |
 LL | fn cycle2() -> impl Clone {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^
-note: ...which requires evaluating trait selection obligation `impl std::clone::Clone: std::marker::Send`...
-note: ...which requires processing `cycle1::{{impl-Trait}}`...
-  --> $DIR/auto-trait-leak.rs:42:16
+   = note: ...which again requires processing `cycle1::{{exist-impl-Trait}}`, completing the cycle
+
+error[E0277]: the trait bound `std::rc::Rc<std::string::String>: std::marker::Send` is not satisfied in `impl std::clone::Clone`
+  --> $DIR/auto-trait-leak.rs:27:5
    |
-LL | fn cycle1() -> impl Clone {
-   |                ^^^^^^^^^^
-   = note: ...which again requires processing `cycle1`, completing the cycle
-note: cycle used when type-checking all item bodies
+LL |     send(cycle2().clone());
+   |     ^^^^ `std::rc::Rc<std::string::String>` cannot be sent between threads safely
+   |
+   = help: within `impl std::clone::Clone`, the trait `std::marker::Send` is not implemented for `std::rc::Rc<std::string::String>`
+   = note: required because it appears within the type `impl std::clone::Clone`
+note: required by `send`
+  --> $DIR/auto-trait-leak.rs:16:1
+   |
+LL | fn send<T: Send>(_: T) {}
+   | ^^^^^^^^^^^^^^^^^^^^^^
 
 error: aborting due to 3 previous errors
 
diff --git a/src/test/ui/impl-trait/auto-trait-leak2.rs b/src/test/ui/impl-trait/auto-trait-leak2.rs
new file mode 100644
index 00000000000..16310e67f1b
--- /dev/null
+++ b/src/test/ui/impl-trait/auto-trait-leak2.rs
@@ -0,0 +1,38 @@
+// 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
+
+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
+
+    send(after());
+    //~^ ERROR the trait bound `std::rc::Rc<std::cell::Cell<i32>>: std::marker::Send` is not satisfied
+}
+
+// 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)
+}
+
diff --git a/src/test/ui/impl-trait/auto-trait-leak2.stderr b/src/test/ui/impl-trait/auto-trait-leak2.stderr
new file mode 100644
index 00000000000..59623aed3d2
--- /dev/null
+++ b/src/test/ui/impl-trait/auto-trait-leak2.stderr
@@ -0,0 +1,33 @@
+error[E0277]: the trait bound `std::rc::Rc<std::cell::Cell<i32>>: std::marker::Send` is not satisfied in `impl std::ops::Fn<(i32,)>`
+  --> $DIR/auto-trait-leak2.rs:25:5
+   |
+LL |     send(before());
+   |     ^^^^ `std::rc::Rc<std::cell::Cell<i32>>` cannot be sent between threads safely
+   |
+   = help: within `impl std::ops::Fn<(i32,)>`, the trait `std::marker::Send` is not implemented for `std::rc::Rc<std::cell::Cell<i32>>`
+   = note: required because it appears within the type `[closure@$DIR/auto-trait-leak2.rs:19:5: 19:22 p:std::rc::Rc<std::cell::Cell<i32>>]`
+   = note: required because it appears within the type `impl std::ops::Fn<(i32,)>`
+note: required by `send`
+  --> $DIR/auto-trait-leak2.rs:22:1
+   |
+LL | fn send<T: Send>(_: T) {}
+   | ^^^^^^^^^^^^^^^^^^^^^^
+
+error[E0277]: the trait bound `std::rc::Rc<std::cell::Cell<i32>>: std::marker::Send` is not satisfied in `impl std::ops::Fn<(i32,)>`
+  --> $DIR/auto-trait-leak2.rs:28:5
+   |
+LL |     send(after());
+   |     ^^^^ `std::rc::Rc<std::cell::Cell<i32>>` cannot be sent between threads safely
+   |
+   = help: within `impl std::ops::Fn<(i32,)>`, the trait `std::marker::Send` is not implemented for `std::rc::Rc<std::cell::Cell<i32>>`
+   = note: required because it appears within the type `[closure@$DIR/auto-trait-leak2.rs:36:5: 36:22 p:std::rc::Rc<std::cell::Cell<i32>>]`
+   = note: required because it appears within the type `impl std::ops::Fn<(i32,)>`
+note: required by `send`
+  --> $DIR/auto-trait-leak2.rs:22:1
+   |
+LL | fn send<T: Send>(_: T) {}
+   | ^^^^^^^^^^^^^^^^^^^^^^
+
+error: aborting due to 2 previous errors
+
+For more information about this error, try `rustc --explain E0277`.
diff --git a/src/test/ui/impl-trait/equality.rs b/src/test/ui/impl-trait/equality.rs
index b65e477f21f..71fccc022b7 100644
--- a/src/test/ui/impl-trait/equality.rs
+++ b/src/test/ui/impl-trait/equality.rs
@@ -50,23 +50,4 @@ impl Leak for i32 {
 }
 
 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 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/ui/impl-trait/equality.stderr b/src/test/ui/impl-trait/equality.stderr
index 0f310df0714..e277d4e28cb 100644
--- a/src/test/ui/impl-trait/equality.stderr
+++ b/src/test/ui/impl-trait/equality.stderr
@@ -15,43 +15,7 @@ LL |         n + sum_to(n - 1)
    |
    = help: the trait `std::ops::Add<impl Foo>` is not implemented for `u32`
 
-error[E0308]: mismatched types
-  --> $DIR/equality.rs:53:18
-   |
-LL |     let _: u32 = hide(0_u32);
-   |                  ^^^^^^^^^^^ expected u32, found anonymized type
-   |
-   = note: expected type `u32`
-              found type `impl Foo`
-
-error[E0308]: mismatched types
-  --> $DIR/equality.rs:59:18
-   |
-LL |     let _: i32 = Leak::leak(hide(0_i32));
-   |                  ^^^^^^^^^^^^^^^^^^^^^^^ expected i32, found associated type
-   |
-   = note: expected type `i32`
-              found type `<impl Foo as Leak>::T`
-
-error[E0308]: mismatched types
-  --> $DIR/equality.rs:66:10
-   |
-LL |     x = (x.1,
-   |          ^^^ expected u32, found i32
-   |
-   = note: expected type `impl Foo` (u32)
-              found type `impl Foo` (i32)
-
-error[E0308]: mismatched types
-  --> $DIR/equality.rs:69:10
-   |
-LL |          x.0);
-   |          ^^^ expected i32, found u32
-   |
-   = note: expected type `impl Foo` (i32)
-              found type `impl Foo` (u32)
-
-error: aborting due to 6 previous errors
+error: aborting due to 2 previous errors
 
 Some errors occurred: E0277, E0308.
 For more information about an error, try `rustc --explain E0277`.
diff --git a/src/test/ui/impl-trait/equality2.rs b/src/test/ui/impl-trait/equality2.rs
new file mode 100644
index 00000000000..ec3dc15d846
--- /dev/null
+++ b/src/test/ui/impl-trait/equality2.rs
@@ -0,0 +1,54 @@
+// 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 Foo: Copy + ToString {}
+
+impl<T: Copy + ToString> Foo for T {}
+
+fn hide<T: Foo>(x: T) -> impl Foo {
+    x
+}
+
+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 }
+}
+
+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 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/ui/impl-trait/equality2.stderr b/src/test/ui/impl-trait/equality2.stderr
new file mode 100644
index 00000000000..e4ff2f68247
--- /dev/null
+++ b/src/test/ui/impl-trait/equality2.stderr
@@ -0,0 +1,39 @@
+error[E0308]: mismatched types
+  --> $DIR/equality2.rs:35:18
+   |
+LL |     let _: u32 = hide(0_u32);
+   |                  ^^^^^^^^^^^ expected u32, found anonymized type
+   |
+   = note: expected type `u32`
+              found type `impl Foo`
+
+error[E0308]: mismatched types
+  --> $DIR/equality2.rs:41:18
+   |
+LL |     let _: i32 = Leak::leak(hide(0_i32));
+   |                  ^^^^^^^^^^^^^^^^^^^^^^^ expected i32, found associated type
+   |
+   = note: expected type `i32`
+              found type `<impl Foo as Leak>::T`
+
+error[E0308]: mismatched types
+  --> $DIR/equality2.rs:48:10
+   |
+LL |     x = (x.1,
+   |          ^^^ expected u32, found i32
+   |
+   = note: expected type `impl Foo` (u32)
+              found type `impl Foo` (i32)
+
+error[E0308]: mismatched types
+  --> $DIR/equality2.rs:51:10
+   |
+LL |          x.0);
+   |          ^^^ expected i32, found u32
+   |
+   = note: expected type `impl Foo` (i32)
+              found type `impl Foo` (u32)
+
+error: aborting due to 4 previous errors
+
+For more information about this error, try `rustc --explain E0308`.