Auto merge of #52650 - oli-obk:associated_existential_types, r=nikomatsakis

Implement associated existential types

r? @nikomatsakis

no idea if these work with generic traits. I'm going home for the day :rofl:

8 files changed, 186 insertions, 30 deletions

diff --git a/src/librustc/infer/anon_types/mod.rs b/src/librustc/infer/anon_types/mod.rs
index ae4d88704a0..205f8c5ad06 100644
--- a/src/librustc/infer/anon_types/mod.rs
+++ b/src/librustc/infer/anon_types/mod.rs
@@ -691,25 +691,41 @@ impl<'a, 'gcx, 'tcx> Instantiator<'a, 'gcx, 'tcx> {
                     // }
                     // ```
                     if let Some(anon_node_id) = tcx.hir.as_local_node_id(def_id) {
-                        let in_definition_scope = match tcx.hir.expect_item(anon_node_id).node {
-                            // impl trait
-                            hir::ItemKind::Existential(hir::ExistTy {
-                                impl_trait_fn: Some(parent),
-                                ..
-                            }) => parent == self.parent_def_id,
-                            // named existential types
-                            hir::ItemKind::Existential(hir::ExistTy {
-                                impl_trait_fn: None,
-                                ..
-                            }) => may_define_existential_type(
-                                tcx,
-                                self.parent_def_id,
-                                anon_node_id,
-                            ),
-                            _ => {
-                                let anon_parent_node_id = tcx.hir.get_parent(anon_node_id);
-                                self.parent_def_id == tcx.hir.local_def_id(anon_parent_node_id)
+                        let parent_def_id = self.parent_def_id;
+                        let def_scope_default = || {
+                            let anon_parent_node_id = tcx.hir.get_parent(anon_node_id);
+                            parent_def_id == tcx.hir.local_def_id(anon_parent_node_id)
+                        };
+                        let in_definition_scope = match tcx.hir.find(anon_node_id) {
+                            Some(hir::map::NodeItem(item)) => match item.node {
+                                // impl trait
+                                hir::ItemKind::Existential(hir::ExistTy {
+                                    impl_trait_fn: Some(parent),
+                                    ..
+                                }) => parent == self.parent_def_id,
+                                // named existential types
+                                hir::ItemKind::Existential(hir::ExistTy {
+                                    impl_trait_fn: None,
+                                    ..
+                                }) => may_define_existential_type(
+                                    tcx,
+                                    self.parent_def_id,
+                                    anon_node_id,
+                                ),
+                                _ => def_scope_default(),
                             },
+                            Some(hir::map::NodeImplItem(item)) => match item.node {
+                                hir::ImplItemKind::Existential(_) => may_define_existential_type(
+                                    tcx,
+                                    self.parent_def_id,
+                                    anon_node_id,
+                                ),
+                                _ => def_scope_default(),
+                            },
+                            _ => bug!(
+                                "expected (impl) item, found {}",
+                                tcx.hir.node_to_string(anon_node_id),
+                            ),
                         };
                         if in_definition_scope {
                             return self.fold_anon_ty(ty, def_id, substs);
diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs
index 1052d029e0d..1ce60d8f055 100644
--- a/src/librustc/traits/project.rs
+++ b/src/librustc/traits/project.rs
@@ -1502,7 +1502,7 @@ fn confirm_impl_candidate<'cx, 'gcx, 'tcx>(
     let param_env = obligation.param_env;
     let assoc_ty = assoc_ty_def(selcx, impl_def_id, obligation.predicate.item_def_id);
 
-    let ty = if !assoc_ty.item.defaultness.has_value() {
+    if !assoc_ty.item.defaultness.has_value() {
         // This means that the impl is missing a definition for the
         // associated type. This error will be reported by the type
         // checker method `check_impl_items_against_trait`, so here we
@@ -1510,11 +1510,18 @@ fn confirm_impl_candidate<'cx, 'gcx, 'tcx>(
         debug!("confirm_impl_candidate: no associated type {:?} for {:?}",
                assoc_ty.item.ident,
                obligation.predicate);
-        tcx.types.err
+        return Progress {
+            ty: tcx.types.err,
+            obligations: nested,
+        };
+    }
+    let substs = translate_substs(selcx.infcx(), param_env, impl_def_id, substs, assoc_ty.node);
+    let ty = if let ty::AssociatedKind::Existential = assoc_ty.item.kind {
+        let item_substs = Substs::identity_for_item(tcx, assoc_ty.item.def_id);
+        tcx.mk_anon(assoc_ty.item.def_id, item_substs)
     } else {
         tcx.type_of(assoc_ty.item.def_id)
     };
-    let substs = translate_substs(selcx.infcx(), param_env, impl_def_id, substs, assoc_ty.node);
     Progress {
         ty: ty.subst(tcx, substs),
         obligations: nested,
diff --git a/src/librustc/traits/specialize/specialization_graph.rs b/src/librustc/traits/specialize/specialization_graph.rs
index b64e4228be9..6562526a2ea 100644
--- a/src/librustc/traits/specialize/specialization_graph.rs
+++ b/src/librustc/traits/specialize/specialization_graph.rs
@@ -377,9 +377,19 @@ impl<'a, 'gcx, 'tcx> Ancestors {
         trait_def_id: DefId,
     ) -> impl Iterator<Item = NodeItem<ty::AssociatedItem>> + Captures<'gcx> + Captures<'tcx> + 'a {
         self.flat_map(move |node| {
-            node.items(tcx).filter(move |impl_item| {
-                impl_item.kind == trait_item_kind &&
-                tcx.hygienic_eq(impl_item.ident, trait_item_name, trait_def_id)
+            use ty::AssociatedKind::*;
+            node.items(tcx).filter(move |impl_item| match (trait_item_kind, impl_item.kind) {
+                | (Const, Const)
+                | (Method, Method)
+                | (Type, Type)
+                | (Type, Existential)
+                => tcx.hygienic_eq(impl_item.ident, trait_item_name, trait_def_id),
+
+                | (Const, _)
+                | (Method, _)
+                | (Type, _)
+                | (Existential, _)
+                => false,
             }).map(move |item| NodeItem { node: node, item: item })
         })
     }
diff --git a/src/librustc_typeck/check/wfcheck.rs b/src/librustc_typeck/check/wfcheck.rs
index 03ecb945cbd..38743cc9cf6 100644
--- a/src/librustc_typeck/check/wfcheck.rs
+++ b/src/librustc_typeck/check/wfcheck.rs
@@ -211,8 +211,7 @@ fn check_associated_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                 }
             }
             ty::AssociatedKind::Existential => {
-                // FIXME(oli-obk) implement existential types in trait impls
-                unimplemented!()
+                // do nothing, existential types check themselves
             }
         }
 
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 60f89282551..cd84a61bb2c 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -1046,12 +1046,12 @@ fn type_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                     tcx.mk_fn_def(def_id, substs)
                 }
                 ImplItemKind::Const(ref ty, _) => icx.to_ty(ty),
-                ImplItemKind::Existential(ref _bounds) => {
+                ImplItemKind::Existential(_) => {
                     if tcx.impl_trait_ref(tcx.hir.get_parent_did(node_id)).is_none() {
                         report_assoc_ty_on_inherent_impl(tcx, item.span);
                     }
-                    // FIXME(oli-obk) implement existential types in trait impls
-                    unimplemented!()
+
+                    find_existential_constraints(tcx, def_id)
                 }
                 ImplItemKind::Type(ref ty) => {
                     if tcx.impl_trait_ref(tcx.hir.get_parent_did(node_id)).is_none() {
@@ -1186,8 +1186,10 @@ fn find_existential_constraints<'a, 'tcx>(
     }
     impl<'a, 'tcx> ConstraintLocator<'a, 'tcx> {
         fn check(&mut self, def_id: DefId) {
+            trace!("checking {:?}", def_id);
             // don't try to check items that cannot possibly constrain the type
             if !self.tcx.has_typeck_tables(def_id) {
+                trace!("no typeck tables for {:?}", def_id);
                 return;
             }
             let ty = self
@@ -1244,9 +1246,11 @@ fn find_existential_constraints<'a, 'tcx>(
     let mut locator = ConstraintLocator { def_id, tcx, found: None };
     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
     let parent = tcx.hir.get_parent(node_id);
+    trace!("parent_id: {:?}", parent);
     if parent == ast::CRATE_NODE_ID {
         intravisit::walk_crate(&mut locator, tcx.hir.krate());
     } else {
+        trace!("parent: {:?}", tcx.hir.get(parent));
         match tcx.hir.get(parent) {
             NodeItem(ref it) => intravisit::walk_item(&mut locator, it),
             NodeImplItem(ref it) => intravisit::walk_impl_item(&mut locator, it),
@@ -1485,7 +1489,23 @@ fn explicit_predicates_of<'a, 'tcx>(
             &item.generics
         }
 
-        NodeImplItem(item) => &item.generics,
+        NodeImplItem(item) => match item.node {
+            ImplItemKind::Existential(ref bounds) => {
+                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,
+                                            bounds,
+                                            SizedByDefault::Yes,
+                                            tcx.def_span(def_id));
+
+                predicates.extend(bounds.predicates(tcx, anon_ty));
+                &item.generics
+            },
+            _ => &item.generics,
+        }
 
         NodeItem(item) => {
             match item.node {
diff --git a/src/test/ui/impl-trait/associated-existential-type-generic-trait.rs b/src/test/ui/impl-trait/associated-existential-type-generic-trait.rs
new file mode 100644
index 00000000000..c9bf7b87ef4
--- /dev/null
+++ b/src/test/ui/impl-trait/associated-existential-type-generic-trait.rs
@@ -0,0 +1,40 @@
+// 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.
+
+#![feature(existential_type)]
+// compile-pass
+
+trait Bar {}
+struct Dummy<U>(U);
+impl<V> Bar for Dummy<V> {}
+
+trait Foo<T> {
+    type Assoc: Bar;
+    fn foo(t: T) -> Self::Assoc;
+}
+
+impl<W> Foo<W> for i32 {
+    existential type Assoc: Bar;
+    fn foo(w: W) -> Self::Assoc {
+        Dummy(w)
+    }
+}
+
+struct NonGeneric;
+impl Bar for NonGeneric {}
+
+impl<W> Foo<W> for u32 {
+    existential type Assoc: Bar;
+    fn foo(_: W) -> Self::Assoc {
+        NonGeneric
+    }
+}
+
+fn main() {}
diff --git a/src/test/ui/impl-trait/associated-existential-type-trivial.rs b/src/test/ui/impl-trait/associated-existential-type-trivial.rs
new file mode 100644
index 00000000000..78593fe319c
--- /dev/null
+++ b/src/test/ui/impl-trait/associated-existential-type-trivial.rs
@@ -0,0 +1,30 @@
+// 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.
+
+#![feature(existential_type)]
+// compile-pass
+
+trait Bar {}
+struct Dummy;
+impl Bar for Dummy {}
+
+trait Foo {
+    type Assoc: Bar;
+    fn foo() -> Self::Assoc;
+}
+
+impl Foo for i32 {
+    existential type Assoc: Bar;
+    fn foo() -> Self::Assoc {
+        Dummy
+    }
+}
+
+fn main() {}
diff --git a/src/test/ui/impl-trait/associated-existential-type.rs b/src/test/ui/impl-trait/associated-existential-type.rs
new file mode 100644
index 00000000000..d880428411f
--- /dev/null
+++ b/src/test/ui/impl-trait/associated-existential-type.rs
@@ -0,0 +1,34 @@
+// 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.
+
+#![feature(existential_type)]
+// compile-pass
+
+trait Bar {}
+struct Dummy;
+impl Bar for Dummy {}
+
+trait Foo {
+    type Assoc: Bar;
+    fn foo() -> Self::Assoc;
+    fn bar() -> Self::Assoc;
+}
+
+impl Foo for i32 {
+    existential type Assoc: Bar;
+    fn foo() -> Self::Assoc {
+        Dummy
+    }
+    fn bar() -> Self::Assoc {
+        Dummy
+    }
+}
+
+fn main() {}