Auto merge of #46706 - sunjay:gat-lifetimes, r=nikomatsakis

Lifetime Resolution for Generic Associated Types

Tracking Issue: https://github.com/rust-lang/rust/issues/44265

r? @nikomatsakis

This PR implements lifetime resolution for generic associated types. :tada:

## Remaining Work Before Merge

I'm going to go do these things in the next day or so. Please let me know if you spot anything in my changes until then.

- [x] If I'm not mistaken, at least some tests should pass now. I need to go through the tests and re-enable the ones that should work by removing the appropriate `~ ERROR` comments

9 files changed, 155 insertions, 53 deletions

diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index e75762cbacb..188dbe2f1de 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -646,30 +646,77 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
     }
 
     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
-        let tcx = self.tcx;
-        if let hir::TraitItemKind::Method(ref sig, _) = trait_item.node {
-            self.visit_early_late(
-                Some(tcx.hir.get_parent(trait_item.id)),
-                &sig.decl,
-                &trait_item.generics,
-                |this| intravisit::walk_trait_item(this, trait_item),
-            )
-        } else {
-            intravisit::walk_trait_item(self, trait_item);
+        use self::hir::TraitItemKind::*;
+        match trait_item.node {
+            Method(ref sig, _) => {
+                let tcx = self.tcx;
+                self.visit_early_late(
+                    Some(tcx.hir.get_parent(trait_item.id)),
+                    &sig.decl,
+                    &trait_item.generics,
+                    |this| intravisit::walk_trait_item(this, trait_item),
+                );
+            },
+            Type(ref bounds, ref ty) => {
+                let generics = &trait_item.generics;
+                let mut index = self.next_early_index();
+                debug!("visit_ty: index = {}", index);
+                let lifetimes = generics.lifetimes.iter()
+                    .map(|lt_def| Region::early(&self.tcx.hir, &mut index, lt_def))
+                    .collect();
+
+                let next_early_index = index + generics.ty_params.len() as u32;
+                let scope = Scope::Binder { lifetimes, next_early_index, s: self.scope };
+                self.with(scope, |_old_scope, this| {
+                    this.visit_generics(generics);
+                    for bound in bounds {
+                        this.visit_ty_param_bound(bound);
+                    }
+                    if let Some(ty) = ty {
+                        this.visit_ty(ty);
+                    }
+                });
+            },
+            Const(_, _) => {
+                // Only methods and types support generics.
+                assert!(!trait_item.generics.is_parameterized());
+                intravisit::walk_trait_item(self, trait_item);
+            },
         }
     }
 
     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
-        let tcx = self.tcx;
-        if let hir::ImplItemKind::Method(ref sig, _) = impl_item.node {
-            self.visit_early_late(
-                Some(tcx.hir.get_parent(impl_item.id)),
-                &sig.decl,
-                &impl_item.generics,
-                |this| intravisit::walk_impl_item(this, impl_item),
-            )
-        } else {
-            intravisit::walk_impl_item(self, impl_item);
+        use self::hir::ImplItemKind::*;
+        match impl_item.node {
+            Method(ref sig, _) => {
+                let tcx = self.tcx;
+                self.visit_early_late(
+                    Some(tcx.hir.get_parent(impl_item.id)),
+                    &sig.decl,
+                    &impl_item.generics,
+                    |this| intravisit::walk_impl_item(this, impl_item),
+                )
+            },
+            Type(ref ty) => {
+                let generics = &impl_item.generics;
+                let mut index = self.next_early_index();
+                debug!("visit_ty: index = {}", index);
+                let lifetimes = generics.lifetimes.iter()
+                    .map(|lt_def| Region::early(&self.tcx.hir, &mut index, lt_def))
+                    .collect();
+
+                let next_early_index = index + generics.ty_params.len() as u32;
+                let scope = Scope::Binder { lifetimes, next_early_index, s: self.scope };
+                self.with(scope, |_old_scope, this| {
+                    this.visit_generics(generics);
+                    this.visit_ty(ty);
+                });
+            },
+            Const(_, _) => {
+                // Only methods and types support generics.
+                assert!(!impl_item.generics.is_parameterized());
+                intravisit::walk_impl_item(self, impl_item);
+            },
         }
     }
 
diff --git a/src/test/ui/rfc1598-generic-associated-types/construct_with_other_type.rs b/src/test/ui/rfc1598-generic-associated-types/construct_with_other_type.rs
index 208fc2ea089..0d9b487876e 100644
--- a/src/test/ui/rfc1598-generic-associated-types/construct_with_other_type.rs
+++ b/src/test/ui/rfc1598-generic-associated-types/construct_with_other_type.rs
@@ -10,7 +10,8 @@
 
 #![feature(generic_associated_types)]
 
-//FIXME(#44265): "undeclared lifetime" errors will be addressed in a follow-up PR
+//FIXME(#44265): "lifetime parameters are not allowed on this type" errors will be addressed in a
+//follow-up PR
 
 trait Foo {
     type Bar<'a, 'b>;
@@ -22,8 +23,7 @@ trait Baz {
 
 impl<T> Baz for T where T: Foo {
     type Quux<'a> = <T as Foo>::Bar<'a, 'static>;
-    //~^ ERROR undeclared lifetime
-    //~| ERROR lifetime parameters are not allowed on this type [E0110]
+    //~^ ERROR lifetime parameters are not allowed on this type [E0110]
 }
 
 fn main() {}
diff --git a/src/test/ui/rfc1598-generic-associated-types/construct_with_other_type.stderr b/src/test/ui/rfc1598-generic-associated-types/construct_with_other_type.stderr
index 6a2047d10e6..e74592fa9ff 100644
--- a/src/test/ui/rfc1598-generic-associated-types/construct_with_other_type.stderr
+++ b/src/test/ui/rfc1598-generic-associated-types/construct_with_other_type.stderr
@@ -1,14 +1,8 @@
-error[E0261]: use of undeclared lifetime name `'a`
-  --> $DIR/construct_with_other_type.rs:24:37
-   |
-24 |     type Quux<'a> = <T as Foo>::Bar<'a, 'static>;
-   |                                     ^^ undeclared lifetime
-
 error[E0110]: lifetime parameters are not allowed on this type
-  --> $DIR/construct_with_other_type.rs:24:37
+  --> $DIR/construct_with_other_type.rs:25:37
    |
-24 |     type Quux<'a> = <T as Foo>::Bar<'a, 'static>;
+25 |     type Quux<'a> = <T as Foo>::Bar<'a, 'static>;
    |                                     ^^ lifetime parameter not allowed on this type
 
-error: aborting due to 2 previous errors
+error: aborting due to previous error
 
diff --git a/src/test/ui/rfc1598-generic-associated-types/generic-associated-types-where.rs b/src/test/ui/rfc1598-generic-associated-types/generic-associated-types-where.rs
index eec061bc96b..9b59b24b105 100644
--- a/src/test/ui/rfc1598-generic-associated-types/generic-associated-types-where.rs
+++ b/src/test/ui/rfc1598-generic-associated-types/generic-associated-types-where.rs
@@ -13,8 +13,6 @@
 // Checking the interaction with this other feature
 #![feature(associated_type_defaults)]
 
-//FIXME(#44265): "undeclared lifetime" errors will be addressed in a follow-up PR
-
 use std::fmt::{Display, Debug};
 
 trait Foo {
@@ -32,7 +30,6 @@ impl Foo for Bar {
     type Assoc2<T> = Vec<T>;
     type Assoc3<T> where T: Iterator = Vec<T>;
     type WithDefault<'a, T> = &'a Iterator<T>;
-    //~^ ERROR undeclared lifetime
     type NoGenerics = ::std::cell::Cell<i32>;
 }
 
diff --git a/src/test/ui/rfc1598-generic-associated-types/generic-associated-types-where.stderr b/src/test/ui/rfc1598-generic-associated-types/generic-associated-types-where.stderr
index b99cb2a1830..bb55d86f620 100644
--- a/src/test/ui/rfc1598-generic-associated-types/generic-associated-types-where.stderr
+++ b/src/test/ui/rfc1598-generic-associated-types/generic-associated-types-where.stderr
@@ -1,8 +1,2 @@
-error[E0261]: use of undeclared lifetime name `'a`
-  --> $DIR/generic-associated-types-where.rs:34:32
-   |
-34 |     type WithDefault<'a, T> = &'a Iterator<T>;
-   |                                ^^ undeclared lifetime
-
 error: cannot continue compilation due to previous error
 
diff --git a/src/test/ui/rfc1598-generic-associated-types/generic_associated_type_undeclared_lifetimes.rs b/src/test/ui/rfc1598-generic-associated-types/generic_associated_type_undeclared_lifetimes.rs
new file mode 100644
index 00000000000..263b3cb42eb
--- /dev/null
+++ b/src/test/ui/rfc1598-generic-associated-types/generic_associated_type_undeclared_lifetimes.rs
@@ -0,0 +1,31 @@
+// Copyright 2012 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(generic_associated_types)]
+
+use std::ops::Deref;
+
+//FIXME(#44265): "lifetime parameters are not allowed on this type" errors will be addressed in a
+//follow-up PR
+
+trait Iterable {
+    type Item<'a>;
+    type Iter<'a>: Iterator<Item = Self::Item<'a>>
+    //~^ ERROR lifetime parameters are not allowed on this type [E0110]
+        + Deref<Target = Self::Item<'b>>;
+    //~^ ERROR undeclared lifetime
+    //~| ERROR lifetime parameters are not allowed on this type [E0110]
+
+    fn iter<'a>(&'a self) -> Self::Iter<'undeclared>;
+    //~^ ERROR undeclared lifetime
+    //~| ERROR lifetime parameters are not allowed on this type [E0110]
+}
+
+fn main() {}
diff --git a/src/test/ui/rfc1598-generic-associated-types/generic_associated_type_undeclared_lifetimes.stderr b/src/test/ui/rfc1598-generic-associated-types/generic_associated_type_undeclared_lifetimes.stderr
new file mode 100644
index 00000000000..587be7113ce
--- /dev/null
+++ b/src/test/ui/rfc1598-generic-associated-types/generic_associated_type_undeclared_lifetimes.stderr
@@ -0,0 +1,32 @@
+error[E0261]: use of undeclared lifetime name `'b`
+  --> $DIR/generic_associated_type_undeclared_lifetimes.rs:22:37
+   |
+22 |         + Deref<Target = Self::Item<'b>>;
+   |                                     ^^ undeclared lifetime
+
+error[E0261]: use of undeclared lifetime name `'undeclared`
+  --> $DIR/generic_associated_type_undeclared_lifetimes.rs:26:41
+   |
+26 |     fn iter<'a>(&'a self) -> Self::Iter<'undeclared>;
+   |                                         ^^^^^^^^^^^ undeclared lifetime
+
+error[E0110]: lifetime parameters are not allowed on this type
+  --> $DIR/generic_associated_type_undeclared_lifetimes.rs:20:47
+   |
+20 |     type Iter<'a>: Iterator<Item = Self::Item<'a>>
+   |                                               ^^ lifetime parameter not allowed on this type
+
+error[E0110]: lifetime parameters are not allowed on this type
+  --> $DIR/generic_associated_type_undeclared_lifetimes.rs:22:37
+   |
+22 |         + Deref<Target = Self::Item<'b>>;
+   |                                     ^^ lifetime parameter not allowed on this type
+
+error[E0110]: lifetime parameters are not allowed on this type
+  --> $DIR/generic_associated_type_undeclared_lifetimes.rs:26:41
+   |
+26 |     fn iter<'a>(&'a self) -> Self::Iter<'undeclared>;
+   |                                         ^^^^^^^^^^^ lifetime parameter not allowed on this type
+
+error: aborting due to 5 previous errors
+
diff --git a/src/test/ui/rfc1598-generic-associated-types/iterable.rs b/src/test/ui/rfc1598-generic-associated-types/iterable.rs
index 219554b587a..1287ddaf7f7 100644
--- a/src/test/ui/rfc1598-generic-associated-types/iterable.rs
+++ b/src/test/ui/rfc1598-generic-associated-types/iterable.rs
@@ -10,13 +10,20 @@
 
 #![feature(generic_associated_types)]
 
-//FIXME(#44265): "undeclared lifetime" errors will be addressed in a follow-up PR
+use std::ops::Deref;
+
+//FIXME(#44265): "lifetime parameters are not allowed on this type" errors will be addressed in a
+//follow-up PR
 
 trait Iterable {
     type Item<'a>;
     type Iter<'a>: Iterator<Item = Self::Item<'a>>;
-    //~^ ERROR undeclared lifetime
-    //~| ERROR lifetime parameters are not allowed on this type [E0110]
+    //~^ ERROR lifetime parameters are not allowed on this type [E0110]
+
+    // This weird type tests that we can use universal function call syntax to access the Item on
+    // Self::Iter which we have declared to be an Iterator
+    type Iter2<'a>: Deref<Target = <Self::Iter<'a> as Iterator>::Item>;
+    //~^ ERROR lifetime parameters are not allowed on this type [E0110]
 
     fn iter<'a>(&'a self) -> Self::Iter<'a>;
     //~^ ERROR lifetime parameters are not allowed on this type [E0110]
diff --git a/src/test/ui/rfc1598-generic-associated-types/iterable.stderr b/src/test/ui/rfc1598-generic-associated-types/iterable.stderr
index fb91d38ba7a..d12ca5e5d4e 100644
--- a/src/test/ui/rfc1598-generic-associated-types/iterable.stderr
+++ b/src/test/ui/rfc1598-generic-associated-types/iterable.stderr
@@ -1,19 +1,19 @@
-error[E0261]: use of undeclared lifetime name `'a`
-  --> $DIR/iterable.rs:17:47
+error[E0110]: lifetime parameters are not allowed on this type
+  --> $DIR/iterable.rs:20:47
    |
-17 |     type Iter<'a>: Iterator<Item = Self::Item<'a>>;
-   |                                               ^^ undeclared lifetime
+20 |     type Iter<'a>: Iterator<Item = Self::Item<'a>>;
+   |                                               ^^ lifetime parameter not allowed on this type
 
 error[E0110]: lifetime parameters are not allowed on this type
-  --> $DIR/iterable.rs:17:47
+  --> $DIR/iterable.rs:25:48
    |
-17 |     type Iter<'a>: Iterator<Item = Self::Item<'a>>;
-   |                                               ^^ lifetime parameter not allowed on this type
+25 |     type Iter2<'a>: Deref<Target = <Self::Iter<'a> as Iterator>::Item>;
+   |                                                ^^ lifetime parameter not allowed on this type
 
 error[E0110]: lifetime parameters are not allowed on this type
-  --> $DIR/iterable.rs:21:41
+  --> $DIR/iterable.rs:28:41
    |
-21 |     fn iter<'a>(&'a self) -> Self::Iter<'a>;
+28 |     fn iter<'a>(&'a self) -> Self::Iter<'a>;
    |                                         ^^ lifetime parameter not allowed on this type
 
 error: aborting due to 3 previous errors