Rollup merge of #94869 - jackh726:gats_extended, r=compiler-errors

Add the generic_associated_types_extended feature

Right now, this only ignore obligations that reference new placeholders in `poly_project_and_unify_type`. In the future, this might do other things, like allowing object-safe GATs.

**This feature is *incomplete* and quite likely unsound. This is mostly just for testing out potential future APIs using a "relaxed" set of rules until we figure out *proper* rules.**

Also drive by cleanup of adding a `ProjectAndUnifyResult` enum instead of using a `Result<Result<Option>>`.

r? `@nikomatsakis`

14 files changed, 261 insertions, 33 deletions

diff --git a/compiler/rustc_feature/src/active.rs b/compiler/rustc_feature/src/active.rs
index 90b35b5a83f..28466315c86 100644
--- a/compiler/rustc_feature/src/active.rs
+++ b/compiler/rustc_feature/src/active.rs
@@ -400,6 +400,8 @@ declare_features! (
     (active, generic_arg_infer, "1.55.0", Some(85077), None),
     /// Allows associated types to be generic, e.g., `type Foo<T>;` (RFC 1598).
     (active, generic_associated_types, "1.23.0", Some(44265), None),
+    /// An extension to the `generic_associated_types` feature, allowing incomplete features.
+    (incomplete, generic_associated_types_extended, "1.61.0", Some(95451), None),
     /// Allows non-trivial generic constants which have to have wfness manually propagated to callers
     (incomplete, generic_const_exprs, "1.56.0", Some(76560), None),
     /// Allows using `..X`, `..=X`, `...X`, and `X..` as a pattern.
diff --git a/compiler/rustc_middle/src/ty/fold.rs b/compiler/rustc_middle/src/ty/fold.rs
index 388109e6512..075928c889d 100644
--- a/compiler/rustc_middle/src/ty/fold.rs
+++ b/compiler/rustc_middle/src/ty/fold.rs
@@ -1379,3 +1379,50 @@ impl<'tcx> TypeVisitor<'tcx> for LateBoundRegionsCollector {
         ControlFlow::CONTINUE
     }
 }
+
+/// Finds the max universe present
+pub struct MaxUniverse {
+    max_universe: ty::UniverseIndex,
+}
+
+impl MaxUniverse {
+    pub fn new() -> Self {
+        MaxUniverse { max_universe: ty::UniverseIndex::ROOT }
+    }
+
+    pub fn max_universe(self) -> ty::UniverseIndex {
+        self.max_universe
+    }
+}
+
+impl<'tcx> TypeVisitor<'tcx> for MaxUniverse {
+    fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+        if let ty::Placeholder(placeholder) = t.kind() {
+            self.max_universe = ty::UniverseIndex::from_u32(
+                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
+            );
+        }
+
+        t.super_visit_with(self)
+    }
+
+    fn visit_const(&mut self, c: ty::consts::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
+        if let ty::ConstKind::Placeholder(placeholder) = c.val() {
+            self.max_universe = ty::UniverseIndex::from_u32(
+                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
+            );
+        }
+
+        c.super_visit_with(self)
+    }
+
+    fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
+        if let ty::RePlaceholder(placeholder) = *r {
+            self.max_universe = ty::UniverseIndex::from_u32(
+                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
+            );
+        }
+
+        ControlFlow::CONTINUE
+    }
+}
diff --git a/compiler/rustc_span/src/symbol.rs b/compiler/rustc_span/src/symbol.rs
index 84dbad846dd..ee29a1e96eb 100644
--- a/compiler/rustc_span/src/symbol.rs
+++ b/compiler/rustc_span/src/symbol.rs
@@ -722,6 +722,7 @@ symbols! {
         generators,
         generic_arg_infer,
         generic_associated_types,
+        generic_associated_types_extended,
         generic_const_exprs,
         generic_param_attrs,
         get_context,
diff --git a/compiler/rustc_trait_selection/src/traits/auto_trait.rs b/compiler/rustc_trait_selection/src/traits/auto_trait.rs
index 36eddf7784b..d95512bb88f 100644
--- a/compiler/rustc_trait_selection/src/traits/auto_trait.rs
+++ b/compiler/rustc_trait_selection/src/traits/auto_trait.rs
@@ -5,6 +5,7 @@ use super::*;
 
 use crate::infer::region_constraints::{Constraint, RegionConstraintData};
 use crate::infer::InferCtxt;
+use crate::traits::project::ProjectAndUnifyResult;
 use rustc_middle::ty::fold::TypeFolder;
 use rustc_middle::ty::{Region, RegionVid, Term};
 
@@ -751,7 +752,7 @@ impl<'tcx> AutoTraitFinder<'tcx> {
                     debug!("Projecting and unifying projection predicate {:?}", predicate);
 
                     match project::poly_project_and_unify_type(select, &obligation.with(p)) {
-                        Err(e) => {
+                        ProjectAndUnifyResult::MismatchedProjectionTypes(e) => {
                             debug!(
                                 "evaluate_nested_obligations: Unable to unify predicate \
                                  '{:?}' '{:?}', bailing out",
@@ -759,11 +760,11 @@ impl<'tcx> AutoTraitFinder<'tcx> {
                             );
                             return false;
                         }
-                        Ok(Err(project::InProgress)) => {
+                        ProjectAndUnifyResult::Recursive => {
                             debug!("evaluate_nested_obligations: recursive projection predicate");
                             return false;
                         }
-                        Ok(Ok(Some(v))) => {
+                        ProjectAndUnifyResult::Holds(v) => {
                             // We only care about sub-obligations
                             // when we started out trying to unify
                             // some inference variables. See the comment above
@@ -782,7 +783,7 @@ impl<'tcx> AutoTraitFinder<'tcx> {
                                 }
                             }
                         }
-                        Ok(Ok(None)) => {
+                        ProjectAndUnifyResult::FailedNormalization => {
                             // It's ok not to make progress when have no inference variables -
                             // in that case, we were only performing unification to check if an
                             // error occurred (which would indicate that it's impossible for our
diff --git a/compiler/rustc_trait_selection/src/traits/fulfill.rs b/compiler/rustc_trait_selection/src/traits/fulfill.rs
index 1b862834467..d0b8b0281c5 100644
--- a/compiler/rustc_trait_selection/src/traits/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/traits/fulfill.rs
@@ -14,7 +14,7 @@ use rustc_middle::ty::{self, Binder, Const, Ty, TypeFoldable};
 use std::marker::PhantomData;
 
 use super::const_evaluatable;
-use super::project;
+use super::project::{self, ProjectAndUnifyResult};
 use super::select::SelectionContext;
 use super::wf;
 use super::CodeAmbiguity;
@@ -753,8 +753,8 @@ impl<'a, 'b, 'tcx> FulfillProcessor<'a, 'b, 'tcx> {
         }
 
         match project::poly_project_and_unify_type(self.selcx, &project_obligation) {
-            Ok(Ok(Some(os))) => ProcessResult::Changed(mk_pending(os)),
-            Ok(Ok(None)) => {
+            ProjectAndUnifyResult::Holds(os) => ProcessResult::Changed(mk_pending(os)),
+            ProjectAndUnifyResult::FailedNormalization => {
                 stalled_on.clear();
                 stalled_on.extend(substs_infer_vars(
                     self.selcx,
@@ -763,10 +763,12 @@ impl<'a, 'b, 'tcx> FulfillProcessor<'a, 'b, 'tcx> {
                 ProcessResult::Unchanged
             }
             // Let the caller handle the recursion
-            Ok(Err(project::InProgress)) => ProcessResult::Changed(mk_pending(vec![
+            ProjectAndUnifyResult::Recursive => ProcessResult::Changed(mk_pending(vec![
                 project_obligation.with(project_obligation.predicate.to_predicate(tcx)),
             ])),
-            Err(e) => ProcessResult::Error(CodeProjectionError(e)),
+            ProjectAndUnifyResult::MismatchedProjectionTypes(e) => {
+                ProcessResult::Error(CodeProjectionError(e))
+            }
         }
     }
 }
diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs
index d4ec677a0b1..2251f992e4d 100644
--- a/compiler/rustc_trait_selection/src/traits/project.rs
+++ b/compiler/rustc_trait_selection/src/traits/project.rs
@@ -28,7 +28,7 @@ use rustc_hir::def_id::DefId;
 use rustc_hir::lang_items::LangItem;
 use rustc_infer::infer::resolve::OpportunisticRegionResolver;
 use rustc_middle::traits::select::OverflowError;
-use rustc_middle::ty::fold::{TypeFoldable, TypeFolder};
+use rustc_middle::ty::fold::{MaxUniverse, TypeFoldable, TypeFolder};
 use rustc_middle::ty::subst::Subst;
 use rustc_middle::ty::{self, Term, ToPredicate, Ty, TyCtxt};
 use rustc_span::symbol::sym;
@@ -144,6 +144,18 @@ impl<'tcx> ProjectionCandidateSet<'tcx> {
     }
 }
 
+/// Takes the place of a
+/// Result<
+///     Result<Option<Vec<PredicateObligation<'tcx>>>, InProgress>,
+///     MismatchedProjectionTypes<'tcx>,
+/// >
+pub(super) enum ProjectAndUnifyResult<'tcx> {
+    Holds(Vec<PredicateObligation<'tcx>>),
+    FailedNormalization,
+    Recursive,
+    MismatchedProjectionTypes(MismatchedProjectionTypes<'tcx>),
+}
+
 /// Evaluates constraints of the form:
 ///
 ///     for<...> <T as Trait>::U == V
@@ -167,19 +179,47 @@ impl<'tcx> ProjectionCandidateSet<'tcx> {
 pub(super) fn poly_project_and_unify_type<'cx, 'tcx>(
     selcx: &mut SelectionContext<'cx, 'tcx>,
     obligation: &PolyProjectionObligation<'tcx>,
-) -> Result<
-    Result<Option<Vec<PredicateObligation<'tcx>>>, InProgress>,
-    MismatchedProjectionTypes<'tcx>,
-> {
+) -> ProjectAndUnifyResult<'tcx> {
     let infcx = selcx.infcx();
-    infcx.commit_if_ok(|_snapshot| {
+    let r = infcx.commit_if_ok(|_snapshot| {
+        let old_universe = infcx.universe();
         let placeholder_predicate =
             infcx.replace_bound_vars_with_placeholders(obligation.predicate);
+        let new_universe = infcx.universe();
 
         let placeholder_obligation = obligation.with(placeholder_predicate);
-        let result = project_and_unify_type(selcx, &placeholder_obligation)?;
-        Ok(result)
-    })
+        match project_and_unify_type(selcx, &placeholder_obligation) {
+            ProjectAndUnifyResult::MismatchedProjectionTypes(e) => Err(e),
+            ProjectAndUnifyResult::Holds(obligations)
+                if old_universe != new_universe
+                    && selcx.tcx().features().generic_associated_types_extended =>
+            {
+                // If the `generic_associated_types_extended` feature is active, then we ignore any
+                // obligations references lifetimes from any universe greater than or equal to the
+                // universe just created. Otherwise, we can end up with something like `for<'a> I: 'a`,
+                // which isn't quite what we want. Ideally, we want either an implied
+                // `for<'a where I: 'a> I: 'a` or we want to "lazily" check these hold when we
+                // substitute concrete regions. There is design work to be done here; until then,
+                // however, this allows experimenting potential GAT features without running into
+                // well-formedness issues.
+                let new_obligations = obligations
+                    .into_iter()
+                    .filter(|obligation| {
+                        let mut visitor = MaxUniverse::new();
+                        obligation.predicate.visit_with(&mut visitor);
+                        visitor.max_universe() < new_universe
+                    })
+                    .collect();
+                Ok(ProjectAndUnifyResult::Holds(new_obligations))
+            }
+            other => Ok(other),
+        }
+    });
+
+    match r {
+        Ok(inner) => inner,
+        Err(err) => ProjectAndUnifyResult::MismatchedProjectionTypes(err),
+    }
 }
 
 /// Evaluates constraints of the form:
@@ -189,15 +229,11 @@ pub(super) fn poly_project_and_unify_type<'cx, 'tcx>(
 /// If successful, this may result in additional obligations.
 ///
 /// See [poly_project_and_unify_type] for an explanation of the return value.
+#[tracing::instrument(level = "debug", skip(selcx))]
 fn project_and_unify_type<'cx, 'tcx>(
     selcx: &mut SelectionContext<'cx, 'tcx>,
     obligation: &ProjectionObligation<'tcx>,
-) -> Result<
-    Result<Option<Vec<PredicateObligation<'tcx>>>, InProgress>,
-    MismatchedProjectionTypes<'tcx>,
-> {
-    debug!(?obligation, "project_and_unify_type");
-
+) -> ProjectAndUnifyResult<'tcx> {
     let mut obligations = vec![];
 
     let infcx = selcx.infcx();
@@ -210,8 +246,8 @@ fn project_and_unify_type<'cx, 'tcx>(
         &mut obligations,
     ) {
         Ok(Some(n)) => n,
-        Ok(None) => return Ok(Ok(None)),
-        Err(InProgress) => return Ok(Err(InProgress)),
+        Ok(None) => return ProjectAndUnifyResult::FailedNormalization,
+        Err(InProgress) => return ProjectAndUnifyResult::Recursive,
     };
     debug!(?normalized, ?obligations, "project_and_unify_type result");
     let actual = obligation.predicate.term;
@@ -231,11 +267,11 @@ fn project_and_unify_type<'cx, 'tcx>(
     match infcx.at(&obligation.cause, obligation.param_env).eq(normalized, actual) {
         Ok(InferOk { obligations: inferred_obligations, value: () }) => {
             obligations.extend(inferred_obligations);
-            Ok(Ok(Some(obligations)))
+            ProjectAndUnifyResult::Holds(obligations)
         }
         Err(err) => {
-            debug!("project_and_unify_type: equating types encountered error {:?}", err);
-            Err(MismatchedProjectionTypes { err })
+            debug!("equating types encountered error {:?}", err);
+            ProjectAndUnifyResult::MismatchedProjectionTypes(MismatchedProjectionTypes { err })
         }
     }
 }
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 42f17721f9b..4f033d45c1f 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -21,6 +21,7 @@ use super::{
 
 use crate::infer::{InferCtxt, InferOk, TypeFreshener};
 use crate::traits::error_reporting::InferCtxtExt;
+use crate::traits::project::ProjectAndUnifyResult;
 use crate::traits::project::ProjectionCacheKeyExt;
 use crate::traits::ProjectionCacheKey;
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
@@ -525,7 +526,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     let data = bound_predicate.rebind(data);
                     let project_obligation = obligation.with(data);
                     match project::poly_project_and_unify_type(self, &project_obligation) {
-                        Ok(Ok(Some(mut subobligations))) => {
+                        ProjectAndUnifyResult::Holds(mut subobligations) => {
                             'compute_res: {
                                 // If we've previously marked this projection as 'complete', then
                                 // use the final cached result (either `EvaluatedToOk` or
@@ -573,9 +574,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                 res
                             }
                         }
-                        Ok(Ok(None)) => Ok(EvaluatedToAmbig),
-                        Ok(Err(project::InProgress)) => Ok(EvaluatedToRecur),
-                        Err(_) => Ok(EvaluatedToErr),
+                        ProjectAndUnifyResult::FailedNormalization => Ok(EvaluatedToAmbig),
+                        ProjectAndUnifyResult::Recursive => Ok(EvaluatedToRecur),
+                        ProjectAndUnifyResult::MismatchedProjectionTypes(_) => Ok(EvaluatedToErr),
                     }
                 }
 
diff --git a/src/test/ui/feature-gates/feature-gate-generic_associated_types_extended.rs b/src/test/ui/feature-gates/feature-gate-generic_associated_types_extended.rs
new file mode 100644
index 00000000000..258b8cd35c7
--- /dev/null
+++ b/src/test/ui/feature-gates/feature-gate-generic_associated_types_extended.rs
@@ -0,0 +1,6 @@
+#![feature(generic_associated_types)]
+
+// This feature doesn't *currently* fire on any specific code; it's just a
+// behavior change. Future changes might.
+#[rustc_error] //~ the
+fn main() {}
diff --git a/src/test/ui/feature-gates/feature-gate-generic_associated_types_extended.stderr b/src/test/ui/feature-gates/feature-gate-generic_associated_types_extended.stderr
new file mode 100644
index 00000000000..6a5eba38cac
--- /dev/null
+++ b/src/test/ui/feature-gates/feature-gate-generic_associated_types_extended.stderr
@@ -0,0 +1,11 @@
+error[E0658]: the `#[rustc_error]` attribute is just used for rustc unit tests and will never be stable
+  --> $DIR/feature-gate-generic_associated_types_extended.rs:5:1
+   |
+LL | #[rustc_error]
+   | ^^^^^^^^^^^^^^
+   |
+   = help: add `#![feature(rustc_attrs)]` to the crate attributes to enable
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0658`.
diff --git a/src/test/ui/generic-associated-types/extended/lending_iterator.base.nll.stderr b/src/test/ui/generic-associated-types/extended/lending_iterator.base.nll.stderr
new file mode 100644
index 00000000000..3da7794b3d2
--- /dev/null
+++ b/src/test/ui/generic-associated-types/extended/lending_iterator.base.nll.stderr
@@ -0,0 +1,12 @@
+error[E0276]: impl has stricter requirements than trait
+  --> $DIR/lending_iterator.rs:14:45
+   |
+LL |     fn from_iter<T: for<'x> LendingIterator<Item<'x> = A>>(iter: T) -> Self;
+   |     ------------------------------------------------------------------------ definition of `from_iter` from trait
+...
+LL |     fn from_iter<I: for<'x> LendingIterator<Item<'x> = A>>(mut iter: I) -> Self {
+   |                                             ^^^^^^^^^^^^ impl has extra requirement `I: 'x`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0276`.
diff --git a/src/test/ui/generic-associated-types/extended/lending_iterator.base.stderr b/src/test/ui/generic-associated-types/extended/lending_iterator.base.stderr
new file mode 100644
index 00000000000..c5588b0912b
--- /dev/null
+++ b/src/test/ui/generic-associated-types/extended/lending_iterator.base.stderr
@@ -0,0 +1,26 @@
+error[E0276]: impl has stricter requirements than trait
+  --> $DIR/lending_iterator.rs:14:45
+   |
+LL |     fn from_iter<T: for<'x> LendingIterator<Item<'x> = A>>(iter: T) -> Self;
+   |     ------------------------------------------------------------------------ definition of `from_iter` from trait
+...
+LL |     fn from_iter<I: for<'x> LendingIterator<Item<'x> = A>>(mut iter: I) -> Self {
+   |                                             ^^^^^^^^^^^^ impl has extra requirement `I: 'x`
+
+error[E0311]: the parameter type `Self` may not live long enough
+  --> $DIR/lending_iterator.rs:35:9
+   |
+LL |         <B as FromLendingIterator<A>>::from_iter(self)
+   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   |
+   = help: consider adding an explicit lifetime bound `Self: 'a`...
+   = note: ...so that the type `Self` will meet its required lifetime bounds...
+note: ...that is required by this bound
+  --> $DIR/lending_iterator.rs:10:45
+   |
+LL |     fn from_iter<T: for<'x> LendingIterator<Item<'x> = A>>(iter: T) -> Self;
+   |                                             ^^^^^^^^^^^^
+
+error: aborting due to 2 previous errors
+
+For more information about this error, try `rustc --explain E0276`.
diff --git a/src/test/ui/generic-associated-types/extended/lending_iterator.rs b/src/test/ui/generic-associated-types/extended/lending_iterator.rs
new file mode 100644
index 00000000000..df11ab21249
--- /dev/null
+++ b/src/test/ui/generic-associated-types/extended/lending_iterator.rs
@@ -0,0 +1,40 @@
+// revisions: base extended
+//[base] check-fail
+//[extended] check-pass
+
+#![feature(generic_associated_types)]
+#![cfg_attr(extended, feature(generic_associated_types_extended))]
+#![cfg_attr(extended, allow(incomplete_features))]
+
+pub trait FromLendingIterator<A>: Sized {
+    fn from_iter<T: for<'x> LendingIterator<Item<'x> = A>>(iter: T) -> Self;
+}
+
+impl<A> FromLendingIterator<A> for Vec<A> {
+    fn from_iter<I: for<'x> LendingIterator<Item<'x> = A>>(mut iter: I) -> Self {
+        //[base]~^ impl has stricter
+        let mut v = vec![];
+        while let Some(item) = iter.next() {
+            v.push(item);
+        }
+        v
+    }
+}
+
+pub trait LendingIterator {
+    type Item<'z>
+    where
+        Self: 'z;
+    fn next(&mut self) -> Option<Self::Item<'_>>;
+
+    fn collect<A, B: FromLendingIterator<A>>(self) -> B
+    where
+        Self: Sized,
+        Self: for<'q> LendingIterator<Item<'q> = A>,
+    {
+        <B as FromLendingIterator<A>>::from_iter(self)
+        //[base]~^ the parameter type
+    }
+}
+
+fn main() {}
diff --git a/src/test/ui/generic-associated-types/extended/lending_iterator_2.base.stderr b/src/test/ui/generic-associated-types/extended/lending_iterator_2.base.stderr
new file mode 100644
index 00000000000..6c2a624ca11
--- /dev/null
+++ b/src/test/ui/generic-associated-types/extended/lending_iterator_2.base.stderr
@@ -0,0 +1,12 @@
+error[E0276]: impl has stricter requirements than trait
+  --> $DIR/lending_iterator_2.rs:14:45
+   |
+LL |     fn from_iter<T: for<'x> LendingIterator<Item<'x> = A>>(iter: T) -> Self;
+   |     ------------------------------------------------------------------------ definition of `from_iter` from trait
+...
+LL |     fn from_iter<I: for<'x> LendingIterator<Item<'x> = A>>(mut iter: I) -> Self {
+   |                                             ^^^^^^^^^^^^ impl has extra requirement `I: 'x`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0276`.
diff --git a/src/test/ui/generic-associated-types/extended/lending_iterator_2.rs b/src/test/ui/generic-associated-types/extended/lending_iterator_2.rs
new file mode 100644
index 00000000000..3c4a2184db9
--- /dev/null
+++ b/src/test/ui/generic-associated-types/extended/lending_iterator_2.rs
@@ -0,0 +1,31 @@
+// revisions: base extended
+//[base] check-fail
+//[extended] check-pass
+
+#![feature(generic_associated_types)]
+#![cfg_attr(extended, feature(generic_associated_types_extended))]
+#![cfg_attr(extended, allow(incomplete_features))]
+
+pub trait FromLendingIterator<A>: Sized {
+    fn from_iter<T: for<'x> LendingIterator<Item<'x> = A>>(iter: T) -> Self;
+}
+
+impl<A> FromLendingIterator<A> for Vec<A> {
+    fn from_iter<I: for<'x> LendingIterator<Item<'x> = A>>(mut iter: I) -> Self {
+        //[base]~^ impl has stricter
+        let mut v = vec![];
+        while let Some(item) = iter.next() {
+            v.push(item);
+        }
+        v
+    }
+}
+
+pub trait LendingIterator {
+    type Item<'a>
+    where
+        Self: 'a;
+    fn next(&mut self) -> Option<Self::Item<'_>>;
+}
+
+fn main() {}