Implement existential types

6 files changed, 116 insertions, 22 deletions

diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index bcdad92bc32..1b6b47f5489 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -1394,6 +1394,7 @@ pub enum ImplItemKind {
     Const(P<Ty>, P<Expr>),
     Method(MethodSig, P<Block>),
     Type(P<Ty>),
+    Existential(GenericBounds),
     Macro(Mac),
 }
 
@@ -2132,6 +2133,10 @@ pub enum ItemKind {
     ///
     /// E.g. `type Foo = Bar<u8>;`
     Ty(P<Ty>, Generics),
+    /// An existential type declaration (`existential type`).
+    ///
+    /// E.g. `existential type Foo: Bar + Boo;`
+    Existential(GenericBounds, Generics),
     /// An enum definition (`enum` or `pub enum`).
     ///
     /// E.g. `enum Foo<A, B> { C<A>, D<B> }`
@@ -2183,6 +2188,7 @@ impl ItemKind {
             ItemKind::ForeignMod(..) => "foreign module",
             ItemKind::GlobalAsm(..) => "global asm",
             ItemKind::Ty(..) => "type alias",
+            ItemKind::Existential(..) => "existential type",
             ItemKind::Enum(..) => "enum",
             ItemKind::Struct(..) => "struct",
             ItemKind::Union(..) => "union",
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index 1a73096505f..aef6b8ba5a8 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -419,6 +419,9 @@ declare_features! (
     // Allows macro invocations in `extern {}` blocks
     (active, macros_in_extern, "1.27.0", Some(49476), None),
 
+    // `existential type`
+    (active, existential_type, "1.28.0", Some(34511), None),
+
     // unstable #[target_feature] directives
     (active, arm_target_feature, "1.27.0", Some(44839), None),
     (active, aarch64_target_feature, "1.27.0", Some(44839), None),
@@ -1643,6 +1646,15 @@ impl<'a> Visitor<'a> for PostExpansionVisitor<'a> {
                 gate_feature_post!(&self, decl_macro, i.span, msg);
             }
 
+            ast::ItemKind::Existential(..) => {
+                gate_feature_post!(
+                    &self,
+                    existential_type,
+                    i.span,
+                    "existential types are unstable"
+                );
+            }
+
             _ => {}
         }
 
@@ -1842,6 +1854,15 @@ impl<'a> Visitor<'a> for PostExpansionVisitor<'a> {
                     gate_feature_post!(&self, const_fn, ii.span, "const fn is unstable");
                 }
             }
+            ast::ImplItemKind::Existential(..) => {
+                gate_feature_post!(
+                    &self,
+                    existential_type,
+                    ii.span,
+                    "existential types are unstable"
+                );
+            }
+
             ast::ImplItemKind::Type(_) if !ii.generics.params.is_empty() => {
                 gate_feature_post!(&self, generic_associated_types, ii.span,
                                    "generic associated types are unstable");
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index d9d3febc4fe..9d5982c1e28 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -912,6 +912,10 @@ pub fn noop_fold_item_kind<T: Folder>(i: ItemKind, folder: &mut T) -> ItemKind {
         ItemKind::Ty(t, generics) => {
             ItemKind::Ty(folder.fold_ty(t), folder.fold_generics(generics))
         }
+        ItemKind::Existential(bounds, generics) => ItemKind::Existential(
+            folder.fold_bounds(bounds),
+            folder.fold_generics(generics),
+        ),
         ItemKind::Enum(enum_definition, generics) => {
             let generics = folder.fold_generics(generics);
             let variants = enum_definition.variants.move_map(|x| folder.fold_variant(x));
@@ -1002,6 +1006,9 @@ pub fn noop_fold_impl_item<T: Folder>(i: ImplItem, folder: &mut T)
                                folder.fold_block(body))
             }
             ast::ImplItemKind::Type(ty) => ast::ImplItemKind::Type(folder.fold_ty(ty)),
+            ast::ImplItemKind::Existential(bounds) => {
+                ast::ImplItemKind::Existential(folder.fold_bounds(bounds))
+            },
             ast::ImplItemKind::Macro(mac) => ast::ImplItemKind::Macro(folder.fold_mac(mac))
         },
         span: folder.new_span(i.span),
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 62bb5fbd04f..2eaa56ebeb8 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -63,6 +63,15 @@ use std::mem;
 use std::path::{self, Path, PathBuf};
 use std::slice;
 
+#[derive(Debug)]
+/// Whether the type alias or associated type is a concrete type or an existential type
+pub enum AliasKind {
+    /// Just a new name for the same type
+    Weak(P<Ty>),
+    /// Only trait impls of the type will be usable, not the actual type itself
+    Existential(GenericBounds),
+}
+
 bitflags! {
     struct Restrictions: u8 {
         const STMT_EXPR         = 1 << 0;
@@ -5502,16 +5511,13 @@ impl<'a> Parser<'a> {
         let lo = self.span;
         let vis = self.parse_visibility(false)?;
         let defaultness = self.parse_defaultness();
-        let (name, node, generics) = if self.eat_keyword(keywords::Type) {
-            // This parses the grammar:
-            //     ImplItemAssocTy = Ident ["<"...">"] ["where" ...] "=" Ty ";"
-            let name = self.parse_ident()?;
-            let mut generics = self.parse_generics()?;
-            generics.where_clause = self.parse_where_clause()?;
-            self.expect(&token::Eq)?;
-            let typ = self.parse_ty()?;
-            self.expect(&token::Semi)?;
-            (name, ast::ImplItemKind::Type(typ), generics)
+        let (name, node, generics) = if let Some(type_) = self.eat_type() {
+            let (name, alias, generics) = type_?;
+            let kind = match alias {
+                AliasKind::Weak(typ) => ast::ImplItemKind::Type(typ),
+                AliasKind::Existential(bounds) => ast::ImplItemKind::Existential(bounds),
+            };
+            (name, kind, generics)
         } else if self.is_const_item() {
             // This parses the grammar:
             //     ImplItemConst = "const" Ident ":" Ty "=" Expr ";"
@@ -6563,14 +6569,43 @@ impl<'a> Parser<'a> {
     }
 
     /// Parse type Foo = Bar;
-    fn parse_item_type(&mut self) -> PResult<'a, ItemInfo> {
+    /// or
+    /// existential type Foo: Bar;
+    /// or
+    /// return None without modifying the parser state
+    fn eat_type(&mut self) -> Option<PResult<'a, (Ident, AliasKind, ast::Generics)>> {
+        // This parses the grammar:
+        //     Ident ["<"...">"] ["where" ...] ("=" | ":") Ty ";"
+        if self.check_keyword(keywords::Type) ||
+           self.check_keyword(keywords::Existential) &&
+                self.look_ahead(1, |t| t.is_keyword(keywords::Type)) {
+            let existential = self.eat_keyword(keywords::Existential);
+            assert!(self.eat_keyword(keywords::Type));
+            Some(self.parse_existential_or_alias(existential))
+        } else {
+            None
+        }
+    }
+
+    /// Parse type alias or existential type
+    fn parse_existential_or_alias(
+        &mut self,
+        existential: bool,
+    ) -> PResult<'a, (Ident, AliasKind, ast::Generics)> {
         let ident = self.parse_ident()?;
         let mut tps = self.parse_generics()?;
         tps.where_clause = self.parse_where_clause()?;
-        self.expect(&token::Eq)?;
-        let ty = self.parse_ty()?;
+        let alias = if existential {
+            self.expect(&token::Colon)?;
+            let bounds = self.parse_generic_bounds()?;
+            AliasKind::Existential(bounds)
+        } else {
+            self.expect(&token::Eq)?;
+            let ty = self.parse_ty()?;
+            AliasKind::Weak(ty)
+        };
         self.expect(&token::Semi)?;
-        Ok((ident, ItemKind::Ty(ty, tps), None))
+        Ok((ident, alias, tps))
     }
 
     /// Parse the part of an "enum" decl following the '{'
@@ -6926,15 +6961,19 @@ impl<'a> Parser<'a> {
                                     maybe_append(attrs, extra_attrs));
             return Ok(Some(item));
         }
-        if self.eat_keyword(keywords::Type) {
+        if let Some(type_) = self.eat_type() {
+            let (ident, alias, generics) = type_?;
             // TYPE ITEM
-            let (ident, item_, extra_attrs) = self.parse_item_type()?;
+            let item_ = match alias {
+                AliasKind::Weak(ty) => ItemKind::Ty(ty, generics),
+                AliasKind::Existential(bounds) => ItemKind::Existential(bounds, generics),
+            };
             let prev_span = self.prev_span;
             let item = self.mk_item(lo.to(prev_span),
                                     ident,
                                     item_,
                                     visibility,
-                                    maybe_append(attrs, extra_attrs));
+                                    attrs);
             return Ok(Some(item));
         }
         if self.eat_keyword(keywords::Enum) {
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index b0a9003a456..de68780ef2c 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -1280,9 +1280,7 @@ impl<'a> State<'a> {
                 self.end()?;
             }
             ast::ItemKind::Ty(ref ty, ref generics) => {
-                self.ibox(INDENT_UNIT)?;
-                self.ibox(0)?;
-                self.word_nbsp(&visibility_qualified(&item.vis, "type"))?;
+                self.head(&visibility_qualified(&item.vis, "type"))?;
                 self.print_ident(item.ident)?;
                 self.print_generic_params(&generics.params)?;
                 self.end()?; // end the inner ibox
@@ -1294,6 +1292,18 @@ impl<'a> State<'a> {
                 self.s.word(";")?;
                 self.end()?; // end the outer ibox
             }
+            ast::ItemKind::Existential(ref bounds, ref generics) => {
+                self.head(&visibility_qualified(&item.vis, "existential type"))?;
+                self.print_ident(item.ident)?;
+                self.print_generic_params(&generics.params)?;
+                self.end()?; // end the inner ibox
+
+                self.print_where_clause(&generics.where_clause)?;
+                self.s.space()?;
+                self.print_type_bounds(":", bounds)?;
+                self.s.word(";")?;
+                self.end()?; // end the outer ibox
+            }
             ast::ItemKind::Enum(ref enum_definition, ref params) => {
                 self.print_enum_def(
                     enum_definition,
@@ -1501,8 +1511,8 @@ impl<'a> State<'a> {
         }
     }
 
-    pub fn print_defaultness(&mut self, defatulness: ast::Defaultness) -> io::Result<()> {
-        if let ast::Defaultness::Default = defatulness {
+    pub fn print_defaultness(&mut self, defaultness: ast::Defaultness) -> io::Result<()> {
+        if let ast::Defaultness::Default = defaultness {
             try!(self.word_nbsp("default"));
         }
         Ok(())
@@ -1650,6 +1660,10 @@ impl<'a> State<'a> {
             ast::ImplItemKind::Type(ref ty) => {
                 self.print_associated_type(ii.ident, None, Some(ty))?;
             }
+            ast::ImplItemKind::Existential(ref bounds) => {
+                self.word_space("existential")?;
+                self.print_associated_type(ii.ident, Some(bounds), None)?;
+            }
             ast::ImplItemKind::Macro(ref mac) => {
                 self.print_mac(mac)?;
                 match mac.node.delim {
diff --git a/src/libsyntax/visit.rs b/src/libsyntax/visit.rs
index 9211a2383b6..51be129737e 100644
--- a/src/libsyntax/visit.rs
+++ b/src/libsyntax/visit.rs
@@ -252,6 +252,10 @@ pub fn walk_item<'a, V: Visitor<'a>>(visitor: &mut V, item: &'a Item) {
             visitor.visit_ty(typ);
             visitor.visit_generics(type_parameters)
         }
+        ItemKind::Existential(ref bounds, ref type_parameters) => {
+            walk_list!(visitor, visit_param_bound, bounds);
+            visitor.visit_generics(type_parameters)
+        }
         ItemKind::Enum(ref enum_definition, ref type_parameters) => {
             visitor.visit_generics(type_parameters);
             visitor.visit_enum_def(enum_definition, type_parameters, item.id, item.span)
@@ -600,6 +604,9 @@ pub fn walk_impl_item<'a, V: Visitor<'a>>(visitor: &mut V, impl_item: &'a ImplIt
         ImplItemKind::Type(ref ty) => {
             visitor.visit_ty(ty);
         }
+        ImplItemKind::Existential(ref bounds) => {
+            walk_list!(visitor, visit_param_bound, bounds);
+        }
         ImplItemKind::Macro(ref mac) => {
             visitor.visit_mac(mac);
         }