Auto merge of #138785 - lcnr:typing-mode-borrowck, r=compiler-errors,oli-obk

add `TypingMode::Borrowck`

Shares the first commit with #138499, doesn't really matter which PR to land first :blush: :grin:

Introduces `TypingMode::Borrowck` which unlike `TypingMode::Analysis`, uses the hidden type computed by HIR typeck as the initial value of opaques instead of an unconstrained infer var. This is a part of https://github.com/rust-lang/types-team/issues/129.

Using this new `TypingMode` is unfortunately a breaking change for now, see tests/ui/impl-trait/non-defining-uses/as-projection-term.rs. Using an inference variable as the initial value results in non-defining uses in the defining scope. We therefore only enable it if with `-Znext-solver=globally` or `-Ztyping-mode-borrowck`

To do that the PR contains the following changes:
- `TypeckResults::concrete_opaque_type` are already mapped to the definition of the opaque type
  - writeback now checks that the non-lifetime parameters of the opaque are universal
  - for this, `fn check_opaque_type_parameter_valid` is moved from `rustc_borrowck` to `rustc_trait_selection`
- we add a new `query type_of_opaque_hir_typeck` which, using the same visitors as MIR typeck, attempts to merge the hidden types from HIR typeck from all defining scopes
  - done by adding a `DefiningScopeKind` flag to toggle between using borrowck and HIR typeck
  - the visitors stop checking that the MIR type matches the HIR type. This is trivial as the HIR type are now used as the initial hidden types of the opaque. This check is useful as a safeguard when not using `TypingMode::Borrowck`, but adding it to the new structure is annoying and it's not soundness critical, so I intend to not add it back.
- add a `TypingMode::Borrowck`  which behaves just like `TypingMode::Analysis` except when normalizing opaque types
   - it uses `type_of_opaque_hir_typeck(opaque)` as the initial value after replacing its regions with new inference vars
   - it uses structural lookup in the new solver

fixes #112201, fixes #132335, fixes #137751

r? `@compiler-errors` `@oli-obk`

8 files changed, 203 insertions, 2 deletions

diff --git a/compiler/rustc_trait_selection/src/errors.rs b/compiler/rustc_trait_selection/src/errors.rs
index b30390a9330..9f7bfe5101a 100644
--- a/compiler/rustc_trait_selection/src/errors.rs
+++ b/compiler/rustc_trait_selection/src/errors.rs
@@ -12,7 +12,7 @@ use rustc_hir::intravisit::{Visitor, VisitorExt, walk_ty};
 use rustc_hir::{self as hir, AmbigArg, FnRetTy, GenericParamKind, IsAnonInPath, Node};
 use rustc_macros::{Diagnostic, Subdiagnostic};
 use rustc_middle::ty::print::{PrintTraitRefExt as _, TraitRefPrintOnlyTraitPath};
-use rustc_middle::ty::{self, Binder, ClosureKind, FnSig, Region, Ty, TyCtxt};
+use rustc_middle::ty::{self, Binder, ClosureKind, FnSig, GenericArg, Region, Ty, TyCtxt};
 use rustc_span::{BytePos, Ident, Span, Symbol, kw};
 
 use crate::error_reporting::infer::ObligationCauseAsDiagArg;
@@ -1922,3 +1922,14 @@ impl Subdiagnostic for AddPreciseCapturingForOvercapture {
         }
     }
 }
+
+#[derive(Diagnostic)]
+#[diag(trait_selection_opaque_type_non_generic_param, code = E0792)]
+pub(crate) struct NonGenericOpaqueTypeParam<'a, 'tcx> {
+    pub ty: GenericArg<'tcx>,
+    pub kind: &'a str,
+    #[primary_span]
+    pub span: Span,
+    #[label]
+    pub param_span: Span,
+}
diff --git a/compiler/rustc_trait_selection/src/lib.rs b/compiler/rustc_trait_selection/src/lib.rs
index b18fb0fb8fd..93c11805304 100644
--- a/compiler/rustc_trait_selection/src/lib.rs
+++ b/compiler/rustc_trait_selection/src/lib.rs
@@ -36,6 +36,7 @@
 pub mod error_reporting;
 pub mod errors;
 pub mod infer;
+pub mod opaque_types;
 pub mod regions;
 pub mod solve;
 pub mod traits;
diff --git a/compiler/rustc_trait_selection/src/opaque_types.rs b/compiler/rustc_trait_selection/src/opaque_types.rs
new file mode 100644
index 00000000000..c7b8f063196
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/opaque_types.rs
@@ -0,0 +1,182 @@
+use rustc_data_structures::fx::FxIndexMap;
+use rustc_hir::OpaqueTyOrigin;
+use rustc_hir::def_id::LocalDefId;
+use rustc_infer::infer::outlives::env::OutlivesEnvironment;
+use rustc_infer::infer::{InferCtxt, TyCtxtInferExt};
+use rustc_middle::ty::{
+    self, DefiningScopeKind, GenericArgKind, GenericArgs, OpaqueTypeKey, TyCtxt, TypeVisitableExt,
+    TypingMode, fold_regions,
+};
+use rustc_span::{ErrorGuaranteed, Span};
+
+use crate::errors::NonGenericOpaqueTypeParam;
+use crate::regions::OutlivesEnvironmentBuildExt;
+use crate::traits::ObligationCtxt;
+
+/// Opaque type parameter validity check as documented in the [rustc-dev-guide chapter].
+///
+/// [rustc-dev-guide chapter]:
+/// https://rustc-dev-guide.rust-lang.org/opaque-types-region-infer-restrictions.html
+pub fn check_opaque_type_parameter_valid<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    opaque_type_key: OpaqueTypeKey<'tcx>,
+    span: Span,
+    defining_scope_kind: DefiningScopeKind,
+) -> Result<(), ErrorGuaranteed> {
+    let tcx = infcx.tcx;
+    let opaque_generics = tcx.generics_of(opaque_type_key.def_id);
+    let opaque_env = LazyOpaqueTyEnv::new(tcx, opaque_type_key.def_id);
+    let mut seen_params: FxIndexMap<_, Vec<_>> = FxIndexMap::default();
+
+    // Avoid duplicate errors in case the opaque has already been malformed in
+    // HIR typeck.
+    if let DefiningScopeKind::MirBorrowck = defining_scope_kind {
+        if let Err(guar) = infcx
+            .tcx
+            .type_of_opaque_hir_typeck(opaque_type_key.def_id)
+            .instantiate_identity()
+            .error_reported()
+        {
+            return Err(guar);
+        }
+    }
+
+    for (i, arg) in opaque_type_key.iter_captured_args(tcx) {
+        let arg_is_param = match arg.unpack() {
+            GenericArgKind::Lifetime(lt) => match defining_scope_kind {
+                DefiningScopeKind::HirTypeck => continue,
+                DefiningScopeKind::MirBorrowck => {
+                    matches!(*lt, ty::ReEarlyParam(_) | ty::ReLateParam(_))
+                        || (lt.is_static() && opaque_env.param_equal_static(i))
+                }
+            },
+            GenericArgKind::Type(ty) => matches!(ty.kind(), ty::Param(_)),
+            GenericArgKind::Const(ct) => matches!(ct.kind(), ty::ConstKind::Param(_)),
+        };
+
+        if arg_is_param {
+            // Register if the same lifetime appears multiple times in the generic args.
+            // There is an exception when the opaque type *requires* the lifetimes to be equal.
+            // See [rustc-dev-guide chapter] § "An exception to uniqueness rule".
+            let seen_where = seen_params.entry(arg).or_default();
+            if !seen_where.first().is_some_and(|&prev_i| opaque_env.params_equal(i, prev_i)) {
+                seen_where.push(i);
+            }
+        } else {
+            // Prevent `fn foo() -> Foo<u32>` from being defining.
+            let opaque_param = opaque_generics.param_at(i, tcx);
+            let kind = opaque_param.kind.descr();
+
+            opaque_env.param_is_error(i)?;
+
+            return Err(infcx.dcx().emit_err(NonGenericOpaqueTypeParam {
+                ty: arg,
+                kind,
+                span,
+                param_span: tcx.def_span(opaque_param.def_id),
+            }));
+        }
+    }
+
+    for (_, indices) in seen_params {
+        if indices.len() > 1 {
+            let descr = opaque_generics.param_at(indices[0], tcx).kind.descr();
+            let spans: Vec<_> = indices
+                .into_iter()
+                .map(|i| tcx.def_span(opaque_generics.param_at(i, tcx).def_id))
+                .collect();
+            return Err(infcx
+                .dcx()
+                .struct_span_err(span, "non-defining opaque type use in defining scope")
+                .with_span_note(spans, format!("{descr} used multiple times"))
+                .emit());
+        }
+    }
+
+    Ok(())
+}
+
+/// Computes if an opaque type requires a lifetime parameter to be equal to
+/// another one or to the `'static` lifetime.
+/// These requirements are derived from the explicit and implied bounds.
+struct LazyOpaqueTyEnv<'tcx> {
+    tcx: TyCtxt<'tcx>,
+    def_id: LocalDefId,
+
+    /// Equal parameters will have the same name. Computed Lazily.
+    /// Example:
+    ///     `type Opaque<'a: 'static, 'b: 'c, 'c: 'b> = impl Sized;`
+    ///     Identity args: `['a, 'b, 'c]`
+    ///     Canonical args: `['static, 'b, 'b]`
+    canonical_args: std::cell::OnceCell<ty::GenericArgsRef<'tcx>>,
+}
+
+impl<'tcx> LazyOpaqueTyEnv<'tcx> {
+    fn new(tcx: TyCtxt<'tcx>, def_id: LocalDefId) -> Self {
+        Self { tcx, def_id, canonical_args: std::cell::OnceCell::new() }
+    }
+
+    fn param_equal_static(&self, param_index: usize) -> bool {
+        self.get_canonical_args()[param_index].expect_region().is_static()
+    }
+
+    fn params_equal(&self, param1: usize, param2: usize) -> bool {
+        let canonical_args = self.get_canonical_args();
+        canonical_args[param1] == canonical_args[param2]
+    }
+
+    fn param_is_error(&self, param_index: usize) -> Result<(), ErrorGuaranteed> {
+        self.get_canonical_args()[param_index].error_reported()
+    }
+
+    fn get_canonical_args(&self) -> ty::GenericArgsRef<'tcx> {
+        if let Some(&canonical_args) = self.canonical_args.get() {
+            return canonical_args;
+        }
+
+        let &Self { tcx, def_id, .. } = self;
+        let origin = tcx.local_opaque_ty_origin(def_id);
+        let parent = match origin {
+            OpaqueTyOrigin::FnReturn { parent, .. }
+            | OpaqueTyOrigin::AsyncFn { parent, .. }
+            | OpaqueTyOrigin::TyAlias { parent, .. } => parent,
+        };
+        let param_env = tcx.param_env(parent);
+        let args = GenericArgs::identity_for_item(tcx, parent).extend_to(
+            tcx,
+            def_id.to_def_id(),
+            |param, _| {
+                tcx.map_opaque_lifetime_to_parent_lifetime(param.def_id.expect_local()).into()
+            },
+        );
+
+        // FIXME(#132279): It feels wrong to use `non_body_analysis` here given that we're
+        // in a body here.
+        let infcx = tcx.infer_ctxt().build(TypingMode::non_body_analysis());
+        let ocx = ObligationCtxt::new(&infcx);
+
+        let wf_tys = ocx.assumed_wf_types(param_env, parent).unwrap_or_else(|_| {
+            tcx.dcx().span_delayed_bug(tcx.def_span(def_id), "error getting implied bounds");
+            Default::default()
+        });
+        let outlives_env = OutlivesEnvironment::new(&infcx, parent, param_env, wf_tys);
+
+        let mut seen = vec![tcx.lifetimes.re_static];
+        let canonical_args = fold_regions(tcx, args, |r1, _| {
+            if r1.is_error() {
+                r1
+            } else if let Some(&r2) = seen.iter().find(|&&r2| {
+                let free_regions = outlives_env.free_region_map();
+                free_regions.sub_free_regions(tcx, r1, r2)
+                    && free_regions.sub_free_regions(tcx, r2, r1)
+            }) {
+                r2
+            } else {
+                seen.push(r1);
+                r1
+            }
+        });
+        self.canonical_args.set(canonical_args).unwrap();
+        canonical_args
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/delegate.rs b/compiler/rustc_trait_selection/src/solve/delegate.rs
index f2725411e13..e0b425fa739 100644
--- a/compiler/rustc_trait_selection/src/solve/delegate.rs
+++ b/compiler/rustc_trait_selection/src/solve/delegate.rs
@@ -195,6 +195,7 @@ impl<'tcx> rustc_next_trait_solver::delegate::SolverDelegate for SolverDelegate<
             match self.typing_mode() {
                 TypingMode::Coherence
                 | TypingMode::Analysis { .. }
+                | TypingMode::Borrowck { .. }
                 | TypingMode::PostBorrowckAnalysis { .. } => false,
                 TypingMode::PostAnalysis => {
                     let poly_trait_ref = self.resolve_vars_if_possible(goal_trait_ref);
diff --git a/compiler/rustc_trait_selection/src/traits/normalize.rs b/compiler/rustc_trait_selection/src/traits/normalize.rs
index ad62b456ad4..4ac45172a0e 100644
--- a/compiler/rustc_trait_selection/src/traits/normalize.rs
+++ b/compiler/rustc_trait_selection/src/traits/normalize.rs
@@ -130,6 +130,7 @@ pub(super) fn needs_normalization<'tcx, T: TypeVisitable<TyCtxt<'tcx>>>(
         // FIXME(#132279): We likely want to reveal opaques during post borrowck analysis
         TypingMode::Coherence
         | TypingMode::Analysis { .. }
+        | TypingMode::Borrowck { .. }
         | TypingMode::PostBorrowckAnalysis { .. } => flags.remove(ty::TypeFlags::HAS_TY_OPAQUE),
         TypingMode::PostAnalysis => {}
     }
@@ -226,6 +227,7 @@ impl<'a, 'b, 'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTypeNormalizer<'a, 'b, 'tcx
                     // FIXME(#132279): We likely want to reveal opaques during post borrowck analysis
                     TypingMode::Coherence
                     | TypingMode::Analysis { .. }
+                    | TypingMode::Borrowck { .. }
                     | TypingMode::PostBorrowckAnalysis { .. } => ty.super_fold_with(self),
                     TypingMode::PostAnalysis => {
                         let recursion_limit = self.cx().recursion_limit();
diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs
index 6057b66c483..349569d750e 100644
--- a/compiler/rustc_trait_selection/src/traits/project.rs
+++ b/compiler/rustc_trait_selection/src/traits/project.rs
@@ -952,6 +952,7 @@ fn assemble_candidates_from_impls<'cx, 'tcx>(
                             match selcx.infcx.typing_mode() {
                                 TypingMode::Coherence
                                 | TypingMode::Analysis { .. }
+                                | TypingMode::Borrowck { .. }
                                 | TypingMode::PostBorrowckAnalysis { .. } => {
                                     debug!(
                                         assoc_ty = ?selcx.tcx().def_path_str(node_item.item.def_id),
diff --git a/compiler/rustc_trait_selection/src/traits/query/normalize.rs b/compiler/rustc_trait_selection/src/traits/query/normalize.rs
index 165c63f3745..5dbb4382fd1 100644
--- a/compiler/rustc_trait_selection/src/traits/query/normalize.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/normalize.rs
@@ -216,6 +216,7 @@ impl<'a, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'a, 'tcx> {
                 match self.infcx.typing_mode() {
                     TypingMode::Coherence
                     | TypingMode::Analysis { .. }
+                    | TypingMode::Borrowck { .. }
                     | TypingMode::PostBorrowckAnalysis { .. } => ty.try_super_fold_with(self)?,
 
                     TypingMode::PostAnalysis => {
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 42c598e538d..56ff46e89e7 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -1446,6 +1446,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         match self.infcx.typing_mode() {
             TypingMode::Coherence => {}
             TypingMode::Analysis { .. }
+            | TypingMode::Borrowck { .. }
             | TypingMode::PostBorrowckAnalysis { .. }
             | TypingMode::PostAnalysis => return Ok(()),
         }
@@ -1491,7 +1492,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             // However, if we disqualify *all* goals from being cached, perf suffers.
             // This is likely fixed by better caching in general in the new solver.
             // See: <https://github.com/rust-lang/rust/issues/132064>.
-            TypingMode::Analysis { defining_opaque_types } => {
+            TypingMode::Analysis { defining_opaque_types }
+            | TypingMode::Borrowck { defining_opaque_types } => {
                 defining_opaque_types.is_empty() || !pred.has_opaque_types()
             }
             // The hidden types of `defined_opaque_types` is not local to the current