Auto merge of #94081 - oli-obk:lazy_tait_take_two, r=nikomatsakis

Lazy type-alias-impl-trait take two

### user visible change 1: RPIT inference from recursive call sites

Lazy TAIT has an insta-stable change. The following snippet now compiles, because opaque types can now have their hidden type set from wherever the opaque type is mentioned.

```rust
fn bar(b: bool) -> impl std::fmt::Debug {
    if b {
        return 42
    }
    let x: u32 = bar(false); // this errors on stable
    99
}
```

The return type of `bar` stays opaque, you can't do `bar(false) + 42`, you need to actually mention the hidden type.

### user visible change 2: divergence between RPIT and TAIT in return statements

Note that `return` statements and the trailing return expression are special with RPIT (but not TAIT). So

```rust
#![feature(type_alias_impl_trait)]
type Foo = impl std::fmt::Debug;

fn foo(b: bool) -> Foo {
    if b {
        return vec![42];
    }
    std::iter::empty().collect() //~ ERROR `Foo` cannot be built from an iterator
}

fn bar(b: bool) -> impl std::fmt::Debug {
    if b {
        return vec![42]
    }
    std::iter::empty().collect() // Works, magic (accidentally stabilized, not intended)
}
```

But when we are working with the return value of a recursive call, the behavior of RPIT and TAIT is the same:

```rust
type Foo = impl std::fmt::Debug;

fn foo(b: bool) -> Foo {
    if b {
        return vec![];
    }
    let mut x = foo(false);
    x = std::iter::empty().collect(); //~ ERROR `Foo` cannot be built from an iterator
    vec![]
}

fn bar(b: bool) -> impl std::fmt::Debug {
    if b {
        return vec![];
    }
    let mut x = bar(false);
    x = std::iter::empty().collect(); //~ ERROR `impl Debug` cannot be built from an iterator
    vec![]
}
```

### user visible change 3: TAIT does not merge types across branches

In contrast to RPIT, TAIT does not merge types across branches, so the following does not compile.

```rust
type Foo = impl std::fmt::Debug;

fn foo(b: bool) -> Foo {
    if b {
        vec![42_i32]
    } else {
        std::iter::empty().collect()
        //~^ ERROR `Foo` cannot be built from an iterator over elements of type `_`
    }
}
```

It is easy to support, but we should make an explicit decision to include the additional complexity in the implementation (it's not much, see a721052457cf513487fb4266e3ade65c29b272d2 which needs to be reverted to enable this).

### PR formalities

previous attempt: #92007

This PR also includes #92306 and #93783, as they were reverted along with #92007 in #93893

fixes #93411
fixes #88236
fixes #89312
fixes #87340
fixes #86800
fixes #86719
fixes #84073
fixes #83919
fixes #82139
fixes #77987
fixes #74282
fixes #67830
fixes #62742
fixes #54895

8 files changed, 90 insertions, 49 deletions

diff --git a/compiler/rustc_trait_selection/src/opaque_types.rs b/compiler/rustc_trait_selection/src/opaque_types.rs
index c93ff0aa6e2..06287f00fad 100644
--- a/compiler/rustc_trait_selection/src/opaque_types.rs
+++ b/compiler/rustc_trait_selection/src/opaque_types.rs
@@ -5,15 +5,14 @@ use rustc_infer::infer::error_reporting::unexpected_hidden_region_diagnostic;
 use rustc_infer::infer::InferCtxt;
 use rustc_middle::ty::fold::{TypeFoldable, TypeFolder};
 use rustc_middle::ty::subst::{GenericArg, GenericArgKind, InternalSubsts};
-use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt};
+use rustc_middle::ty::{self, OpaqueHiddenType, OpaqueTypeKey, Ty, TyCtxt};
 use rustc_span::Span;
 
 pub trait InferCtxtExt<'tcx> {
     fn infer_opaque_definition_from_instantiation(
         &self,
         opaque_type_key: OpaqueTypeKey<'tcx>,
-        instantiated_ty: Ty<'tcx>,
-        span: Span,
+        instantiated_ty: OpaqueHiddenType<'tcx>,
     ) -> Ty<'tcx>;
 }
 
@@ -33,7 +32,7 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
     /// purpose of this function is to do that translation.
     ///
     /// (*) C1 and C2 were introduced in the comments on
-    /// `constrain_opaque_type`. Read that comment for more context.
+    /// `register_member_constraints`. Read that comment for more context.
     ///
     /// # Parameters
     ///
@@ -45,9 +44,12 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
     fn infer_opaque_definition_from_instantiation(
         &self,
         opaque_type_key: OpaqueTypeKey<'tcx>,
-        instantiated_ty: Ty<'tcx>,
-        span: Span,
+        instantiated_ty: OpaqueHiddenType<'tcx>,
     ) -> Ty<'tcx> {
+        if self.is_tainted_by_errors() {
+            return self.tcx.ty_error();
+        }
+
         let OpaqueTypeKey { def_id, substs } = opaque_type_key;
 
         // Use substs to build up a reverse map from regions to their
@@ -65,13 +67,12 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
         // Convert the type from the function into a type valid outside
         // the function, by replacing invalid regions with 'static,
         // after producing an error for each of them.
-        let definition_ty = instantiated_ty.fold_with(&mut ReverseMapper::new(
+        let definition_ty = instantiated_ty.ty.fold_with(&mut ReverseMapper::new(
             self.tcx,
-            self.is_tainted_by_errors(),
             def_id,
             map,
-            instantiated_ty,
-            span,
+            instantiated_ty.ty,
+            instantiated_ty.span,
         ));
         debug!(?definition_ty);
 
@@ -82,10 +83,6 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
 struct ReverseMapper<'tcx> {
     tcx: TyCtxt<'tcx>,
 
-    /// If errors have already been reported in this fn, we suppress
-    /// our own errors because they are sometimes derivative.
-    tainted_by_errors: bool,
-
     opaque_type_def_id: DefId,
     map: FxHashMap<GenericArg<'tcx>, GenericArg<'tcx>>,
     map_missing_regions_to_empty: bool,
@@ -100,7 +97,6 @@ struct ReverseMapper<'tcx> {
 impl<'tcx> ReverseMapper<'tcx> {
     fn new(
         tcx: TyCtxt<'tcx>,
-        tainted_by_errors: bool,
         opaque_type_def_id: DefId,
         map: FxHashMap<GenericArg<'tcx>, GenericArg<'tcx>>,
         hidden_ty: Ty<'tcx>,
@@ -108,7 +104,6 @@ impl<'tcx> ReverseMapper<'tcx> {
     ) -> Self {
         Self {
             tcx,
-            tainted_by_errors,
             opaque_type_def_id,
             map,
             map_missing_regions_to_empty: false,
@@ -167,9 +162,7 @@ impl<'tcx> TypeFolder<'tcx> for ReverseMapper<'tcx> {
         match self.map.get(&r.into()).map(|k| k.unpack()) {
             Some(GenericArgKind::Lifetime(r1)) => r1,
             Some(u) => panic!("region mapped to unexpected kind: {:?}", u),
-            None if self.map_missing_regions_to_empty || self.tainted_by_errors => {
-                self.tcx.lifetimes.re_root_empty
-            }
+            None if self.map_missing_regions_to_empty => self.tcx.lifetimes.re_root_empty,
             None if generics.parent.is_some() => {
                 if let Some(hidden_ty) = self.hidden_ty.take() {
                     unexpected_hidden_region_diagnostic(
diff --git a/compiler/rustc_trait_selection/src/traits/codegen.rs b/compiler/rustc_trait_selection/src/traits/codegen.rs
index a607fb6c1b8..4b6784aee97 100644
--- a/compiler/rustc_trait_selection/src/traits/codegen.rs
+++ b/compiler/rustc_trait_selection/src/traits/codegen.rs
@@ -92,6 +92,12 @@ pub fn codegen_fulfill_obligation<'tcx>(
         });
         let impl_source = drain_fulfillment_cx_or_panic(&infcx, &mut fulfill_cx, impl_source);
 
+        // There should be no opaque types during codegen, they all get revealed.
+        let opaque_types = infcx.inner.borrow_mut().opaque_type_storage.take_opaque_types();
+        if !opaque_types.is_empty() {
+            bug!("{:#?}", opaque_types);
+        }
+
         debug!("Cache miss: {:?} => {:?}", trait_ref, impl_source);
         Ok(&*tcx.arena.alloc(impl_source))
     })
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs
index d65b390af34..39da99ac252 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs
@@ -1294,6 +1294,7 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
             ty::Generator(..) => "generator",
             _ => "function",
         };
+        let span = self.tcx.sess.source_map().guess_head_span(span);
         let mut err = struct_span_err!(
             self.tcx.sess,
             span,
@@ -1673,6 +1674,7 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
             ));
 
             let original_span = err.span.primary_span().unwrap();
+            let original_span = self.tcx.sess.source_map().guess_head_span(original_span);
             let mut span = MultiSpan::from_span(original_span);
 
             let message = outer_generator
diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs
index b61e6873571..d4ec677a0b1 100644
--- a/compiler/rustc_trait_selection/src/traits/project.rs
+++ b/compiler/rustc_trait_selection/src/traits/project.rs
@@ -214,10 +214,21 @@ fn project_and_unify_type<'cx, 'tcx>(
         Err(InProgress) => return Ok(Err(InProgress)),
     };
     debug!(?normalized, ?obligations, "project_and_unify_type result");
-    match infcx
-        .at(&obligation.cause, obligation.param_env)
-        .eq(normalized, obligation.predicate.term)
-    {
+    let actual = obligation.predicate.term;
+    // HACK: lazy TAIT would regress src/test/ui/impl-trait/nested-return-type2.rs, so we add
+    // a back-compat hack hat converts the RPITs into inference vars, just like they were before
+    // lazy TAIT.
+    // This does not affect TAITs in general, as tested in the nested-return-type-tait* tests.
+    let InferOk { value: actual, obligations: new } =
+        selcx.infcx().replace_opaque_types_with_inference_vars(
+            actual,
+            obligation.cause.body_id,
+            obligation.cause.span,
+            obligation.param_env,
+        );
+    obligations.extend(new);
+
+    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)))
diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs
index 0a85676f431..605c9ace5ed 100644
--- a/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs
@@ -3,7 +3,8 @@ use crate::infer::{InferCtxt, InferOk};
 use crate::traits::engine::TraitEngineExt as _;
 use crate::traits::query::type_op::TypeOpOutput;
 use crate::traits::query::Fallible;
-use crate::traits::{ObligationCause, TraitEngine};
+use crate::traits::TraitEngine;
+use rustc_infer::infer::region_constraints::RegionConstraintData;
 use rustc_infer::traits::TraitEngineExt as _;
 use rustc_span::source_map::DUMMY_SP;
 
@@ -31,6 +32,9 @@ where
     G: Fn() -> String,
 {
     type Output = R;
+    /// We can't do any custom error reporting for `CustomTypeOp`, so
+    /// we can use `!` to enforce that the implementation never provides it.
+    type ErrorInfo = !;
 
     /// Processes the operation and all resulting obligations,
     /// returning the final result along with any region constraints
@@ -40,7 +44,7 @@ where
             info!("fully_perform({:?})", self);
         }
 
-        scrape_region_constraints(infcx, || (self.closure)(infcx))
+        Ok(scrape_region_constraints(infcx, || (self.closure)(infcx))?.0)
     }
 }
 
@@ -55,12 +59,11 @@ where
 
 /// Executes `op` and then scrapes out all the "old style" region
 /// constraints that result, creating query-region-constraints.
-fn scrape_region_constraints<'tcx, Op: super::TypeOp<'tcx, Output = R>, R>(
+pub fn scrape_region_constraints<'tcx, Op: super::TypeOp<'tcx, Output = R>, R>(
     infcx: &InferCtxt<'_, 'tcx>,
     op: impl FnOnce() -> Fallible<InferOk<'tcx, R>>,
-) -> Fallible<TypeOpOutput<'tcx, Op>> {
+) -> Fallible<(TypeOpOutput<'tcx, Op>, RegionConstraintData<'tcx>)> {
     let mut fulfill_cx = <dyn TraitEngine<'_>>::new(infcx.tcx);
-    let dummy_body_id = ObligationCause::dummy().body_id;
 
     // During NLL, we expect that nobody will register region
     // obligations **except** as part of a custom type op (and, at the
@@ -75,7 +78,6 @@ fn scrape_region_constraints<'tcx, Op: super::TypeOp<'tcx, Output = R>, R>(
     );
 
     let InferOk { value, obligations } = infcx.commit_if_ok(|_| op())?;
-    debug_assert!(obligations.iter().all(|o| o.cause.body_id == dummy_body_id));
     fulfill_cx.register_predicate_obligations(infcx, obligations);
     let errors = fulfill_cx.select_all_or_error(infcx);
     if !errors.is_empty() {
@@ -99,12 +101,18 @@ fn scrape_region_constraints<'tcx, Op: super::TypeOp<'tcx, Output = R>, R>(
     );
 
     if region_constraints.is_empty() {
-        Ok(TypeOpOutput { output: value, constraints: None, canonicalized_query: None })
+        Ok((
+            TypeOpOutput { output: value, constraints: None, error_info: None },
+            region_constraint_data,
+        ))
     } else {
-        Ok(TypeOpOutput {
-            output: value,
-            constraints: Some(Rc::new(region_constraints)),
-            canonicalized_query: None,
-        })
+        Ok((
+            TypeOpOutput {
+                output: value,
+                constraints: Some(Rc::new(region_constraints)),
+                error_info: None,
+            },
+            region_constraint_data,
+        ))
     }
 }
diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/mod.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/mod.rs
index d662f61e2cf..1e72dd69339 100644
--- a/compiler/rustc_trait_selection/src/traits/query/type_op/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/type_op/mod.rs
@@ -28,6 +28,7 @@ pub use rustc_middle::traits::query::type_op::*;
 /// cannot be completed).
 pub trait TypeOp<'tcx>: Sized + fmt::Debug {
     type Output;
+    type ErrorInfo;
 
     /// Processes the operation and all resulting obligations,
     /// returning the final result along with any region constraints
@@ -41,9 +42,8 @@ pub struct TypeOpOutput<'tcx, Op: TypeOp<'tcx>> {
     pub output: Op::Output,
     /// Any region constraints from performing the type op.
     pub constraints: Option<Rc<QueryRegionConstraints<'tcx>>>,
-    /// The canonicalized form of the query.
-    /// This for error reporting to be able to rerun the query.
-    pub canonicalized_query: Option<Canonical<'tcx, Op>>,
+    /// Used for error reporting to be able to rerun the query
+    pub error_info: Option<Op::ErrorInfo>,
 }
 
 /// "Query type ops" are type ops that are implemented using a
@@ -119,10 +119,11 @@ where
     Q: QueryTypeOp<'tcx>,
 {
     type Output = Q::QueryResponse;
+    type ErrorInfo = Canonical<'tcx, ParamEnvAnd<'tcx, Q>>;
 
     fn fully_perform(self, infcx: &InferCtxt<'_, 'tcx>) -> Fallible<TypeOpOutput<'tcx, Self>> {
         let mut region_constraints = QueryRegionConstraints::default();
-        let (output, canonicalized_query, mut obligations, _) =
+        let (output, error_info, mut obligations, _) =
             Q::fully_perform_into(self, infcx, &mut region_constraints)?;
 
         // Typically, instantiating NLL query results does not
@@ -160,6 +161,6 @@ where
         let region_constraints =
             if region_constraints.is_empty() { None } else { Some(Rc::new(region_constraints)) };
 
-        Ok(TypeOpOutput { output, constraints: region_constraints, canonicalized_query })
+        Ok(TypeOpOutput { output, constraints: region_constraints, error_info })
     }
 }
diff --git a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
index 3e7a2252318..cf472813e9e 100644
--- a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
@@ -256,6 +256,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         };
 
         if obligation.predicate.skip_binder().self_ty().is_ty_var() {
+            debug!(ty = ?obligation.predicate.skip_binder().self_ty(), "ambiguous inference var or opaque type");
             // Self is a type variable (e.g., `_: AsRef<str>`).
             //
             // This is somewhat problematic, as the current scheme can't really
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 72d156067a1..42f17721f9b 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -33,6 +33,7 @@ use rustc_middle::dep_graph::{DepKind, DepNodeIndex};
 use rustc_middle::mir::interpret::ErrorHandled;
 use rustc_middle::thir::abstract_const::NotConstEvaluatable;
 use rustc_middle::ty::fast_reject::{self, TreatParams};
+use rustc_middle::ty::fold::BottomUpFolder;
 use rustc_middle::ty::print::with_no_trimmed_paths;
 use rustc_middle::ty::relate::TypeRelation;
 use rustc_middle::ty::subst::{GenericArgKind, Subst, SubstsRef};
@@ -1313,6 +1314,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
     }
 
+    #[instrument(skip(self, param_env, cache_fresh_trait_pred, dep_node), level = "debug")]
     fn insert_candidate_cache(
         &mut self,
         mut param_env: ty::ParamEnv<'tcx>,
@@ -1353,6 +1355,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     /// a projection, look at the bounds of `T::Bar`, see if we can find a
     /// `Baz` bound. We return indexes into the list returned by
     /// `tcx.item_bounds` for any applicable bounds.
+    #[instrument(level = "debug", skip(self))]
     fn match_projection_obligation_against_definition_bounds(
         &mut self,
         obligation: &TraitObligation<'tcx>,
@@ -1360,10 +1363,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let poly_trait_predicate = self.infcx().resolve_vars_if_possible(obligation.predicate);
         let placeholder_trait_predicate =
             self.infcx().replace_bound_vars_with_placeholders(poly_trait_predicate);
-        debug!(
-            ?placeholder_trait_predicate,
-            "match_projection_obligation_against_definition_bounds"
-        );
+        debug!(?placeholder_trait_predicate);
 
         let tcx = self.infcx.tcx;
         let (def_id, substs) = match *placeholder_trait_predicate.trait_ref.self_ty().kind() {
@@ -1414,7 +1414,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             })
             .collect();
 
-        debug!(?matching_bounds, "match_projection_obligation_against_definition_bounds");
+        debug!(?matching_bounds);
         matching_bounds
     }
 
@@ -1444,6 +1444,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         });
         self.infcx
             .at(&obligation.cause, obligation.param_env)
+            .define_opaque_types(false)
             .sup(ty::Binder::dummy(placeholder_trait_ref), trait_bound)
             .map(|InferOk { obligations: _, value: () }| {
                 // This method is called within a probe, so we can't have
@@ -1506,6 +1507,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let is_match = self
             .infcx
             .at(&obligation.cause, obligation.param_env)
+            .define_opaque_types(false)
             .sup(obligation.predicate, infer_projection)
             .map_or(false, |InferOk { obligations, value: () }| {
                 self.evaluate_predicates_recursively(
@@ -2081,11 +2083,22 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         match self.match_impl(impl_def_id, obligation) {
             Ok(substs) => substs,
             Err(()) => {
-                bug!(
-                    "Impl {:?} was matchable against {:?} but now is not",
-                    impl_def_id,
-                    obligation
+                self.infcx.tcx.sess.delay_span_bug(
+                    obligation.cause.span,
+                    &format!(
+                        "Impl {:?} was matchable against {:?} but now is not",
+                        impl_def_id, obligation
+                    ),
                 );
+                let value = self.infcx.fresh_substs_for_item(obligation.cause.span, impl_def_id);
+                let err = self.tcx().ty_error();
+                let value = value.fold_with(&mut BottomUpFolder {
+                    tcx: self.tcx(),
+                    ty_op: |_| err,
+                    lt_op: |l| l,
+                    ct_op: |c| c,
+                });
+                Normalized { value, obligations: vec![] }
             }
         }
     }
@@ -2137,6 +2150,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let InferOk { obligations, .. } = self
             .infcx
             .at(&cause, obligation.param_env)
+            .define_opaque_types(false)
             .eq(placeholder_obligation_trait_ref, impl_trait_ref)
             .map_err(|e| debug!("match_impl: failed eq_trait_refs due to `{}`", e))?;
         nested_obligations.extend(obligations);
@@ -2220,6 +2234,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     ) -> Result<Vec<PredicateObligation<'tcx>>, ()> {
         self.infcx
             .at(&obligation.cause, obligation.param_env)
+            // We don't want predicates for opaque types to just match all other types,
+            // if there is an obligation on the opaque type, then that obligation must be met
+            // opaquely. Otherwise we'd match any obligation to the opaque type and then error
+            // out later.
+            .define_opaque_types(false)
             .sup(obligation.predicate.to_poly_trait_ref(), poly_trait_ref)
             .map(|InferOk { obligations, .. }| obligations)
             .map_err(|_| ())