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

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

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

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

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

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

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

cc @rust-lang/lang

6 files changed, 39 insertions, 2 deletions

diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index a8bb255fba4..3f929e6d23a 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -1368,6 +1368,8 @@ pub enum TyKind {
     ObjectSum(P<Ty>, TyParamBounds),
     /// A type like `for<'a> Foo<&'a Bar>`
     PolyTraitRef(TyParamBounds),
+    /// An `impl TraitA+TraitB` type.
+    ImplTrait(TyParamBounds),
     /// No-op; kept solely so that we can pretty-print faithfully
     Paren(P<Ty>),
     /// Unused for now
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index 29da0fb1a27..f550e7d2a05 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -277,7 +277,10 @@ declare_features! (
     (active, cfg_target_has_atomic, "1.9.0", Some(32976)),
 
     // Allows `..` in tuple (struct) patterns
-    (active, dotdot_in_tuple_patterns, "1.10.0", Some(33627))
+    (active, dotdot_in_tuple_patterns, "1.10.0", Some(33627)),
+
+    // Allows `impl Trait` in function return types.
+    (active, conservative_impl_trait, "1.12.0", Some(34511))
 );
 
 declare_features! (
@@ -952,6 +955,10 @@ impl<'a> Visitor for PostExpansionVisitor<'a> {
             ast::TyKind::BareFn(ref bare_fn_ty) => {
                 self.check_abi(bare_fn_ty.abi, ty.span);
             }
+            ast::TyKind::ImplTrait(..) => {
+                gate_feature_post!(&self, conservative_impl_trait, ty.span,
+                                   "`impl Trait` is experimental");
+            }
             _ => {}
         }
         visit::walk_ty(self, ty)
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index ac3d643b185..afc990f498e 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -397,6 +397,9 @@ pub fn noop_fold_ty<T: Folder>(t: P<Ty>, fld: &mut T) -> P<Ty> {
             TyKind::PolyTraitRef(bounds) => {
                 TyKind::PolyTraitRef(bounds.move_map(|b| fld.fold_ty_param_bound(b)))
             }
+            TyKind::ImplTrait(bounds) => {
+                TyKind::ImplTrait(bounds.move_map(|b| fld.fold_ty_param_bound(b)))
+            }
             TyKind::Mac(mac) => {
                 TyKind::Mac(fld.fold_mac(mac))
             }
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index c143e190c6f..1b32632a06f 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -1051,7 +1051,7 @@ impl<'a> Parser<'a> {
     pub fn parse_for_in_type(&mut self) -> PResult<'a, TyKind> {
         /*
         Parses whatever can come after a `for` keyword in a type.
-        The `for` has already been consumed.
+        The `for` hasn't been consumed.
 
         Deprecated:
 
@@ -1091,6 +1091,23 @@ impl<'a> Parser<'a> {
         }
     }
 
+    pub fn parse_impl_trait_type(&mut self) -> PResult<'a, TyKind> {
+        /*
+        Parses whatever can come after a `impl` keyword in a type.
+        The `impl` has already been consumed.
+        */
+
+        let bounds = self.parse_ty_param_bounds(BoundParsingMode::Modified)?;
+
+        if !bounds.iter().any(|b| if let TraitTyParamBound(..) = *b { true } else { false }) {
+            let last_span = self.last_span;
+            self.span_err(last_span, "at least one trait must be specified");
+        }
+
+        Ok(ast::TyKind::ImplTrait(bounds))
+    }
+
+
     pub fn parse_ty_path(&mut self) -> PResult<'a, TyKind> {
         Ok(TyKind::Path(None, self.parse_path(PathStyle::Type)?))
     }
@@ -1406,6 +1423,8 @@ impl<'a> Parser<'a> {
             self.parse_borrowed_pointee()?
         } else if self.check_keyword(keywords::For) {
             self.parse_for_in_type()?
+        } else if self.eat_keyword(keywords::Impl) {
+            self.parse_impl_trait_type()?
         } else if self.token_is_bare_fn_keyword() {
             // BARE FUNCTION
             self.parse_ty_bare_fn(Vec::new())?
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index a619da84b2d..62e55eb78b7 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -1018,6 +1018,9 @@ impl<'a> State<'a> {
             ast::TyKind::PolyTraitRef(ref bounds) => {
                 try!(self.print_bounds("", &bounds[..]));
             }
+            ast::TyKind::ImplTrait(ref bounds) => {
+                try!(self.print_bounds("impl ", &bounds[..]));
+            }
             ast::TyKind::FixedLengthVec(ref ty, ref v) => {
                 try!(word(&mut self.s, "["));
                 try!(self.print_type(&ty));
diff --git a/src/libsyntax/visit.rs b/src/libsyntax/visit.rs
index 1fc4e54d218..6d3cdbdc6da 100644
--- a/src/libsyntax/visit.rs
+++ b/src/libsyntax/visit.rs
@@ -343,6 +343,9 @@ pub fn walk_ty<V: Visitor>(visitor: &mut V, typ: &Ty) {
         TyKind::PolyTraitRef(ref bounds) => {
             walk_list!(visitor, visit_ty_param_bound, bounds);
         }
+        TyKind::ImplTrait(ref bounds) => {
+            walk_list!(visitor, visit_ty_param_bound, bounds);
+        }
         TyKind::Typeof(ref expression) => {
             visitor.visit_expr(expression)
         }