diff options
Diffstat (limited to 'compiler/rustc_borrowck/src')
25 files changed, 2069 insertions, 1994 deletions
diff --git a/compiler/rustc_borrowck/src/dataflow.rs b/compiler/rustc_borrowck/src/dataflow.rs index 57db2e9fb57..d3f6c01ab8c 100644 --- a/compiler/rustc_borrowck/src/dataflow.rs +++ b/compiler/rustc_borrowck/src/dataflow.rs @@ -1,7 +1,6 @@ use std::fmt; use rustc_data_structures::fx::FxIndexMap; -use rustc_data_structures::graph; use rustc_index::bit_set::{DenseBitSet, MixedBitSet}; use rustc_middle::mir::{ self, BasicBlock, Body, CallReturnPlaces, Location, Place, TerminatorEdges, @@ -317,9 +316,8 @@ impl<'tcx> PoloniusOutOfScopePrecomputer<'_, 'tcx> { loans_out_of_scope_at_location: FxIndexMap::default(), }; for (loan_idx, loan_data) in borrow_set.iter_enumerated() { - let issuing_region = loan_data.region; let loan_issued_at = loan_data.reserve_location; - prec.precompute_loans_out_of_scope(loan_idx, issuing_region, loan_issued_at); + prec.precompute_loans_out_of_scope(loan_idx, loan_issued_at); } prec.loans_out_of_scope_at_location @@ -328,45 +326,7 @@ impl<'tcx> PoloniusOutOfScopePrecomputer<'_, 'tcx> { /// Loans are in scope while they are live: whether they are contained within any live region. /// In the location-insensitive analysis, a loan will be contained in a region if the issuing /// region can reach it in the subset graph. So this is a reachability problem. - fn precompute_loans_out_of_scope( - &mut self, - loan_idx: BorrowIndex, - issuing_region: RegionVid, - loan_issued_at: Location, - ) { - let sccs = self.regioncx.constraint_sccs(); - let universal_regions = self.regioncx.universal_regions(); - - // The loop below was useful for the location-insensitive analysis but shouldn't be - // impactful in the location-sensitive case. It seems that it does, however, as without it a - // handful of tests fail. That likely means some liveness or outlives data related to choice - // regions is missing - // FIXME: investigate the impact of loans traversing applied member constraints and why some - // tests fail otherwise. - // - // We first handle the cases where the loan doesn't go out of scope, depending on the - // issuing region's successors. - for successor in graph::depth_first_search(&self.regioncx.region_graph(), issuing_region) { - // Via applied member constraints - // - // The issuing region can flow into the choice regions, and they are either: - // - placeholders or free regions themselves, - // - or also transitively outlive a free region. - // - // That is to say, if there are applied member constraints here, the loan escapes the - // function and cannot go out of scope. We could early return here. - // - // For additional insurance via fuzzing and crater, we verify that the constraint's min - // choice indeed escapes the function. In the future, we could e.g. turn this check into - // a debug assert and early return as an optimization. - let scc = sccs.scc(successor); - for constraint in self.regioncx.applied_member_constraints(scc) { - if universal_regions.is_universal_region(constraint.min_choice) { - return; - } - } - } - + fn precompute_loans_out_of_scope(&mut self, loan_idx: BorrowIndex, loan_issued_at: Location) { let first_block = loan_issued_at.block; let first_bb_data = &self.body.basic_blocks[first_block]; diff --git a/compiler/rustc_borrowck/src/diagnostics/explain_borrow.rs b/compiler/rustc_borrowck/src/diagnostics/explain_borrow.rs index fdca6b56540..fda96dde826 100644 --- a/compiler/rustc_borrowck/src/diagnostics/explain_borrow.rs +++ b/compiler/rustc_borrowck/src/diagnostics/explain_borrow.rs @@ -565,7 +565,7 @@ impl<'tcx> MirBorrowckCtxt<'_, '_, 'tcx> { let (blame_constraint, path) = self.regioncx.best_blame_constraint( borrow_region, NllRegionVariableOrigin::FreeRegion, - |r| self.regioncx.provides_universal_region(r, borrow_region, outlived_region), + outlived_region, ); let BlameConstraint { category, from_closure, cause, .. } = blame_constraint; diff --git a/compiler/rustc_borrowck/src/diagnostics/mod.rs b/compiler/rustc_borrowck/src/diagnostics/mod.rs index b67dba3af96..5642cdf87fd 100644 --- a/compiler/rustc_borrowck/src/diagnostics/mod.rs +++ b/compiler/rustc_borrowck/src/diagnostics/mod.rs @@ -6,7 +6,9 @@ use rustc_abi::{FieldIdx, VariantIdx}; use rustc_data_structures::fx::FxIndexMap; use rustc_errors::{Applicability, Diag, EmissionGuarantee, MultiSpan, listify}; use rustc_hir::def::{CtorKind, Namespace}; -use rustc_hir::{self as hir, CoroutineKind, LangItem}; +use rustc_hir::{ + self as hir, CoroutineKind, GenericBound, LangItem, WhereBoundPredicate, WherePredicateKind, +}; use rustc_index::{IndexSlice, IndexVec}; use rustc_infer::infer::{BoundRegionConversionTime, NllRegionVariableOrigin}; use rustc_infer::traits::SelectionError; @@ -658,25 +660,66 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { /// Add a note to region errors and borrow explanations when higher-ranked regions in predicates /// implicitly introduce an "outlives `'static`" constraint. + /// + /// This is very similar to `fn suggest_static_lifetime_for_gat_from_hrtb` which handles this + /// note for failed type tests instead of outlives errors. fn add_placeholder_from_predicate_note<G: EmissionGuarantee>( &self, - err: &mut Diag<'_, G>, + diag: &mut Diag<'_, G>, path: &[OutlivesConstraint<'tcx>], ) { - let predicate_span = path.iter().find_map(|constraint| { + let tcx = self.infcx.tcx; + let Some((gat_hir_id, generics)) = path.iter().find_map(|constraint| { let outlived = constraint.sub; if let Some(origin) = self.regioncx.definitions.get(outlived) - && let NllRegionVariableOrigin::Placeholder(_) = origin.origin - && let ConstraintCategory::Predicate(span) = constraint.category + && let NllRegionVariableOrigin::Placeholder(placeholder) = origin.origin + && let Some(id) = placeholder.bound.kind.get_id() + && let Some(placeholder_id) = id.as_local() + && let gat_hir_id = tcx.local_def_id_to_hir_id(placeholder_id) + && let Some(generics_impl) = + tcx.parent_hir_node(tcx.parent_hir_id(gat_hir_id)).generics() { - Some(span) + Some((gat_hir_id, generics_impl)) } else { None } - }); + }) else { + return; + }; - if let Some(span) = predicate_span { - err.span_note(span, "due to current limitations in the borrow checker, this implies a `'static` lifetime"); + // Look for the where-bound which introduces the placeholder. + // As we're using the HIR, we need to handle both `for<'a> T: Trait<'a>` + // and `T: for<'a> Trait`<'a>. + for pred in generics.predicates { + let WherePredicateKind::BoundPredicate(WhereBoundPredicate { + bound_generic_params, + bounds, + .. + }) = pred.kind + else { + continue; + }; + if bound_generic_params + .iter() + .rfind(|bgp| tcx.local_def_id_to_hir_id(bgp.def_id) == gat_hir_id) + .is_some() + { + diag.span_note(pred.span, fluent::borrowck_limitations_implies_static); + return; + } + for bound in bounds.iter() { + if let GenericBound::Trait(bound) = bound { + if bound + .bound_generic_params + .iter() + .rfind(|bgp| tcx.local_def_id_to_hir_id(bgp.def_id) == gat_hir_id) + .is_some() + { + diag.span_note(bound.span, fluent::borrowck_limitations_implies_static); + return; + } + } + } } } diff --git a/compiler/rustc_borrowck/src/diagnostics/move_errors.rs b/compiler/rustc_borrowck/src/diagnostics/move_errors.rs index af71db69483..0b3151fd8b8 100644 --- a/compiler/rustc_borrowck/src/diagnostics/move_errors.rs +++ b/compiler/rustc_borrowck/src/diagnostics/move_errors.rs @@ -518,7 +518,7 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { .with_span_help( self.get_closure_bound_clause_span(*def_id), "`Fn` and `FnMut` closures require captured values to be able to be \ - consumed multiple times, but an `FnOnce` consume them only once", + consumed multiple times, but `FnOnce` closures may consume them only once", ) } _ => { diff --git a/compiler/rustc_borrowck/src/diagnostics/mutability_errors.rs b/compiler/rustc_borrowck/src/diagnostics/mutability_errors.rs index 5d9416b59fc..ea264c8064a 100644 --- a/compiler/rustc_borrowck/src/diagnostics/mutability_errors.rs +++ b/compiler/rustc_borrowck/src/diagnostics/mutability_errors.rs @@ -3,6 +3,7 @@ use core::ops::ControlFlow; +use either::Either; use hir::{ExprKind, Param}; use rustc_abi::FieldIdx; use rustc_errors::{Applicability, Diag}; @@ -12,15 +13,16 @@ use rustc_middle::bug; use rustc_middle::hir::place::PlaceBase; use rustc_middle::mir::visit::PlaceContext; use rustc_middle::mir::{ - self, BindingForm, Local, LocalDecl, LocalInfo, LocalKind, Location, Mutability, Place, - PlaceRef, ProjectionElem, + self, BindingForm, Body, BorrowKind, Local, LocalDecl, LocalInfo, LocalKind, Location, + Mutability, Operand, Place, PlaceRef, ProjectionElem, RawPtrKind, Rvalue, Statement, + StatementKind, TerminatorKind, }; use rustc_middle::ty::{self, InstanceKind, Ty, TyCtxt, Upcast}; use rustc_span::{BytePos, DesugaringKind, Span, Symbol, kw, sym}; use rustc_trait_selection::error_reporting::InferCtxtErrorExt; use rustc_trait_selection::infer::InferCtxtExt; use rustc_trait_selection::traits; -use tracing::debug; +use tracing::{debug, trace}; use crate::diagnostics::BorrowedContentSource; use crate::{MirBorrowckCtxt, session_diagnostics}; @@ -31,6 +33,33 @@ pub(crate) enum AccessKind { Mutate, } +/// Finds all statements that assign directly to local (i.e., X = ...) and returns their +/// locations. +fn find_assignments(body: &Body<'_>, local: Local) -> Vec<Location> { + use rustc_middle::mir::visit::Visitor; + + struct FindLocalAssignmentVisitor { + needle: Local, + locations: Vec<Location>, + } + + impl<'tcx> Visitor<'tcx> for FindLocalAssignmentVisitor { + fn visit_local(&mut self, local: Local, place_context: PlaceContext, location: Location) { + if self.needle != local { + return; + } + + if place_context.is_place_assignment() { + self.locations.push(location); + } + } + } + + let mut visitor = FindLocalAssignmentVisitor { needle: local, locations: vec![] }; + visitor.visit_body(body); + visitor.locations +} + impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { pub(crate) fn report_mutability_error( &mut self, @@ -384,7 +413,7 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { } } - // Also suggest adding mut for upvars + // Also suggest adding mut for upvars. PlaceRef { local, projection: [proj_base @ .., ProjectionElem::Field(upvar_index, _)], @@ -438,9 +467,8 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { } } - // complete hack to approximate old AST-borrowck - // diagnostic: if the span starts with a mutable borrow of - // a local variable, then just suggest the user remove it. + // Complete hack to approximate old AST-borrowck diagnostic: if the span starts + // with a mutable borrow of a local variable, then just suggest the user remove it. PlaceRef { local: _, projection: [] } if self .infcx @@ -677,12 +705,13 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { /// - is the trait from the local crate? If not, we can't suggest changing signatures /// - `Span` of the argument in the trait definition fn is_error_in_trait(&self, local: Local) -> (bool, bool, Option<Span>) { + let tcx = self.infcx.tcx; if self.body.local_kind(local) != LocalKind::Arg { return (false, false, None); } let my_def = self.body.source.def_id(); let Some(td) = - self.infcx.tcx.impl_of_assoc(my_def).and_then(|x| self.infcx.tcx.trait_id_of_impl(x)) + tcx.trait_impl_of_assoc(my_def).and_then(|id| self.infcx.tcx.trait_id_of_impl(id)) else { return (false, false, None); }; @@ -768,7 +797,7 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { ); } - // point to span of upvar making closure call require mutable borrow + // Point to span of upvar making closure call that requires a mutable borrow fn show_mutating_upvar( &self, tcx: TyCtxt<'_>, @@ -824,7 +853,7 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { } else { bug!("not an upvar") }; - // sometimes we deliberately don't store the name of a place when coming from a macro in + // Sometimes we deliberately don't store the name of a place when coming from a macro in // another crate. We generally want to limit those diagnostics a little, to hide // implementation details (such as those from pin!() or format!()). In that case show a // slightly different error message, or none at all if something else happened. In other @@ -935,8 +964,8 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { let def_id = tcx.hir_enclosing_body_owner(fn_call_id); let mut look_at_return = true; - // If the HIR node is a function or method call gets the def ID - // of the called function or method and the span and args of the call expr + // If the HIR node is a function or method call, get the DefId + // of the callee function or method, the span, and args of the call expr let get_call_details = || { let hir::Node::Expr(hir::Expr { hir_id, kind, .. }) = node else { return None; @@ -1050,7 +1079,7 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { let mut cur_expr = expr; while let ExprKind::MethodCall(path_segment, recv, _, _) = cur_expr.kind { if path_segment.ident.name == sym::iter { - // check `_ty` has `iter_mut` method + // Check that the type has an `iter_mut` method. let res = self .infcx .tcx @@ -1080,38 +1109,6 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { } } - /// Finds all statements that assign directly to local (i.e., X = ...) and returns their - /// locations. - fn find_assignments(&self, local: Local) -> Vec<Location> { - use rustc_middle::mir::visit::Visitor; - - struct FindLocalAssignmentVisitor { - needle: Local, - locations: Vec<Location>, - } - - impl<'tcx> Visitor<'tcx> for FindLocalAssignmentVisitor { - fn visit_local( - &mut self, - local: Local, - place_context: PlaceContext, - location: Location, - ) { - if self.needle != local { - return; - } - - if place_context.is_place_assignment() { - self.locations.push(location); - } - } - } - - let mut visitor = FindLocalAssignmentVisitor { needle: local, locations: vec![] }; - visitor.visit_body(self.body); - visitor.locations - } - fn suggest_make_local_mut(&self, err: &mut Diag<'_>, local: Local, name: Symbol) { let local_decl = &self.body.local_decls[local]; @@ -1121,7 +1118,7 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { let (is_trait_sig, is_local, local_trait) = self.is_error_in_trait(local); if is_trait_sig && !is_local { - // Do not suggest to change the signature when the trait comes from another crate. + // Do not suggest changing the signature when the trait comes from another crate. err.span_label( local_decl.source_info.span, format!("this is an immutable {pointer_desc}"), @@ -1130,11 +1127,11 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { } let decl_span = local_decl.source_info.span; - let amp_mut_sugg = match *local_decl.local_info() { + let (amp_mut_sugg, local_var_ty_info) = match *local_decl.local_info() { LocalInfo::User(mir::BindingForm::ImplicitSelf(_)) => { let (span, suggestion) = suggest_ampmut_self(self.infcx.tcx, decl_span); let additional = local_trait.map(|span| suggest_ampmut_self(self.infcx.tcx, span)); - Some(AmpMutSugg { has_sugg: true, span, suggestion, additional }) + (AmpMutSugg::Type { span, suggestion, additional }, None) } LocalInfo::User(mir::BindingForm::Var(mir::VarBindingForm { @@ -1142,79 +1139,54 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { opt_ty_info, .. })) => { - // check if the RHS is from desugaring + // Check if the RHS is from desugaring. + let first_assignment = find_assignments(&self.body, local).first().copied(); + let first_assignment_stmt = first_assignment + .and_then(|loc| self.body[loc.block].statements.get(loc.statement_index)); + trace!(?first_assignment_stmt); let opt_assignment_rhs_span = - self.find_assignments(local).first().map(|&location| { - if let Some(mir::Statement { - source_info: _, - kind: - mir::StatementKind::Assign(box ( - _, - mir::Rvalue::Use(mir::Operand::Copy(place)), - )), - .. - }) = self.body[location.block].statements.get(location.statement_index) - { - self.body.local_decls[place.local].source_info.span - } else { - self.body.source_info(location).span - } - }); - match opt_assignment_rhs_span.and_then(|s| s.desugaring_kind()) { - // on for loops, RHS points to the iterator part - Some(DesugaringKind::ForLoop) => { - let span = opt_assignment_rhs_span.unwrap(); - self.suggest_similar_mut_method_for_for_loop(err, span); + first_assignment.map(|loc| self.body.source_info(loc).span); + let mut source_span = opt_assignment_rhs_span; + if let Some(mir::Statement { + source_info: _, + kind: + mir::StatementKind::Assign(box (_, mir::Rvalue::Use(mir::Operand::Copy(place)))), + .. + }) = first_assignment_stmt + { + let local_span = self.body.local_decls[place.local].source_info.span; + // `&self` in async functions have a `desugaring_kind`, but the local we assign + // it with does not, so use the local_span for our checks later. + source_span = Some(local_span); + if let Some(DesugaringKind::ForLoop) = local_span.desugaring_kind() { + // On for loops, RHS points to the iterator part. + self.suggest_similar_mut_method_for_for_loop(err, local_span); err.span_label( - span, + local_span, format!("this iterator yields `{pointer_sigil}` {pointer_desc}s",), ); - None - } - // don't create labels for compiler-generated spans - Some(_) => None, - // don't create labels for the span not from user's code - None if opt_assignment_rhs_span - .is_some_and(|span| self.infcx.tcx.sess.source_map().is_imported(span)) => - { - None - } - None => { - if name != kw::SelfLower { - suggest_ampmut( - self.infcx.tcx, - local_decl.ty, - decl_span, - opt_assignment_rhs_span, - opt_ty_info, - ) - } else { - match local_decl.local_info() { - LocalInfo::User(mir::BindingForm::Var(mir::VarBindingForm { - opt_ty_info: None, - .. - })) => { - let (span, sugg) = - suggest_ampmut_self(self.infcx.tcx, decl_span); - Some(AmpMutSugg { - has_sugg: true, - span, - suggestion: sugg, - additional: None, - }) - } - // explicit self (eg `self: &'a Self`) - _ => suggest_ampmut( - self.infcx.tcx, - local_decl.ty, - decl_span, - opt_assignment_rhs_span, - opt_ty_info, - ), - } - } + return; } } + + // Don't create labels for compiler-generated spans or spans not from users' code. + if source_span.is_some_and(|s| { + s.desugaring_kind().is_some() || self.infcx.tcx.sess.source_map().is_imported(s) + }) { + return; + } + + // This could be because we're in an `async fn`. + if name == kw::SelfLower && opt_ty_info.is_none() { + let (span, suggestion) = suggest_ampmut_self(self.infcx.tcx, decl_span); + (AmpMutSugg::Type { span, suggestion, additional: None }, None) + } else if let Some(sugg) = + suggest_ampmut(self.infcx, self.body(), first_assignment_stmt) + { + (sugg, opt_ty_info) + } else { + return; + } } LocalInfo::User(mir::BindingForm::Var(mir::VarBindingForm { @@ -1222,181 +1194,238 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { .. })) => { let pattern_span: Span = local_decl.source_info.span; - suggest_ref_mut(self.infcx.tcx, pattern_span).map(|span| AmpMutSugg { - has_sugg: true, - span, - suggestion: "mut ".to_owned(), - additional: None, - }) + let Some(span) = suggest_ref_mut(self.infcx.tcx, pattern_span) else { + return; + }; + (AmpMutSugg::Type { span, suggestion: "mut ".to_owned(), additional: None }, None) } _ => unreachable!(), }; - match amp_mut_sugg { - Some(AmpMutSugg { - has_sugg: true, - span: err_help_span, - suggestion: suggested_code, - additional, - }) => { - let mut sugg = vec![(err_help_span, suggested_code)]; - if let Some(s) = additional { - sugg.push(s); - } + let mut suggest = |suggs: Vec<_>, applicability, extra| { + if suggs.iter().any(|(span, _)| self.infcx.tcx.sess.source_map().is_imported(*span)) { + return; + } - if sugg.iter().all(|(span, _)| !self.infcx.tcx.sess.source_map().is_imported(*span)) - { - err.multipart_suggestion_verbose( - format!( - "consider changing this to be a mutable {pointer_desc}{}", - if is_trait_sig { - " in the `impl` method and the `trait` definition" - } else { - "" - } - ), - sugg, - Applicability::MachineApplicable, - ); + err.multipart_suggestion_verbose( + format!( + "consider changing this to be a mutable {pointer_desc}{}{extra}", + if is_trait_sig { + " in the `impl` method and the `trait` definition" + } else { + "" + } + ), + suggs, + applicability, + ); + }; + + let (mut sugg, add_type_annotation_if_not_exists) = match amp_mut_sugg { + AmpMutSugg::Type { span, suggestion, additional } => { + let mut sugg = vec![(span, suggestion)]; + sugg.extend(additional); + suggest(sugg, Applicability::MachineApplicable, ""); + return; + } + AmpMutSugg::MapGetMut { span, suggestion } => { + if self.infcx.tcx.sess.source_map().is_imported(span) { + return; } + err.multipart_suggestion_verbose( + "consider using `get_mut`", + vec![(span, suggestion)], + Applicability::MaybeIncorrect, + ); + return; } - Some(AmpMutSugg { - has_sugg: false, span: err_label_span, suggestion: message, .. - }) => { - let def_id = self.body.source.def_id(); - let hir_id = if let Some(local_def_id) = def_id.as_local() - && let Some(body) = self.infcx.tcx.hir_maybe_body_owned_by(local_def_id) - { - BindingFinder { span: err_label_span }.visit_body(&body).break_value() - } else { - None - }; + AmpMutSugg::Expr { span, suggestion } => { + // `Expr` suggestions should change type annotations if they already exist (probably immut), + // but do not add new type annotations. + (vec![(span, suggestion)], false) + } + AmpMutSugg::ChangeBinding => (vec![], true), + }; - if let Some(hir_id) = hir_id - && let hir::Node::LetStmt(local) = self.infcx.tcx.hir_node(hir_id) - { - let tables = self.infcx.tcx.typeck(def_id.as_local().unwrap()); - if let Some(clone_trait) = self.infcx.tcx.lang_items().clone_trait() - && let Some(expr) = local.init - && let ty = tables.node_type_opt(expr.hir_id) - && let Some(ty) = ty - && let ty::Ref(..) = ty.kind() + // Find a binding's type to make mutable. + let (binding_exists, span) = match local_var_ty_info { + // If this is a variable binding with an explicit type, + // then we will suggest changing it to be mutable. + // This is `Applicability::MachineApplicable`. + Some(ty_span) => (true, ty_span), + + // Otherwise, we'll suggest *adding* an annotated type, we'll suggest + // the RHS's type for that. + // This is `Applicability::HasPlaceholders`. + None => (false, decl_span), + }; + + if !binding_exists && !add_type_annotation_if_not_exists { + suggest(sugg, Applicability::MachineApplicable, ""); + return; + } + + // If the binding already exists and is a reference with an explicit + // lifetime, then we can suggest adding ` mut`. This is special-cased from + // the path without an explicit lifetime. + let (sugg_span, sugg_str, suggest_now) = if let Ok(src) = self.infcx.tcx.sess.source_map().span_to_snippet(span) + && src.starts_with("&'") + // Note that `&' a T` is invalid so this is correct. + && let Some(ws_pos) = src.find(char::is_whitespace) + { + let span = span.with_lo(span.lo() + BytePos(ws_pos as u32)).shrink_to_lo(); + (span, " mut".to_owned(), true) + // If there is already a binding, we modify it to be `mut`. + } else if binding_exists { + // Shrink the span to just after the `&` in `&variable`. + let span = span.with_lo(span.lo() + BytePos(1)).shrink_to_lo(); + (span, "mut ".to_owned(), true) + } else { + // Otherwise, suggest that the user annotates the binding; We provide the + // type of the local. + let ty = local_decl.ty.builtin_deref(true).unwrap(); + + (span, format!("{}mut {}", if local_decl.ty.is_ref() { "&" } else { "*" }, ty), false) + }; + + if suggest_now { + // Suggest changing `&x` to `&mut x` and changing `&T` to `&mut T` at the same time. + let has_change = !sugg.is_empty(); + sugg.push((sugg_span, sugg_str)); + suggest( + sugg, + Applicability::MachineApplicable, + // FIXME(fee1-dead) this somehow doesn't fire + if has_change { " and changing the binding's type" } else { "" }, + ); + return; + } else if !sugg.is_empty() { + suggest(sugg, Applicability::MachineApplicable, ""); + return; + } + + let def_id = self.body.source.def_id(); + let hir_id = if let Some(local_def_id) = def_id.as_local() + && let Some(body) = self.infcx.tcx.hir_maybe_body_owned_by(local_def_id) + { + BindingFinder { span: sugg_span }.visit_body(&body).break_value() + } else { + None + }; + let node = hir_id.map(|hir_id| self.infcx.tcx.hir_node(hir_id)); + + let Some(hir::Node::LetStmt(local)) = node else { + err.span_label( + sugg_span, + format!("consider changing this binding's type to be: `{sugg_str}`"), + ); + return; + }; + + let tables = self.infcx.tcx.typeck(def_id.as_local().unwrap()); + if let Some(clone_trait) = self.infcx.tcx.lang_items().clone_trait() + && let Some(expr) = local.init + && let ty = tables.node_type_opt(expr.hir_id) + && let Some(ty) = ty + && let ty::Ref(..) = ty.kind() + { + match self + .infcx + .type_implements_trait_shallow(clone_trait, ty.peel_refs(), self.infcx.param_env) + .as_deref() + { + Some([]) => { + // FIXME: This error message isn't useful, since we're just + // vaguely suggesting to clone a value that already + // implements `Clone`. + // + // A correct suggestion here would take into account the fact + // that inference may be affected by missing types on bindings, + // etc., to improve "tests/ui/borrowck/issue-91206.stderr", for + // example. + } + None => { + if let hir::ExprKind::MethodCall(segment, _rcvr, [], span) = expr.kind + && segment.ident.name == sym::clone { - match self - .infcx - .type_implements_trait_shallow( - clone_trait, - ty.peel_refs(), - self.infcx.param_env, - ) - .as_deref() - { - Some([]) => { - // FIXME: This error message isn't useful, since we're just - // vaguely suggesting to clone a value that already - // implements `Clone`. - // - // A correct suggestion here would take into account the fact - // that inference may be affected by missing types on bindings, - // etc., to improve "tests/ui/borrowck/issue-91206.stderr", for - // example. - } - None => { - if let hir::ExprKind::MethodCall(segment, _rcvr, [], span) = - expr.kind - && segment.ident.name == sym::clone - { - err.span_help( - span, - format!( - "`{}` doesn't implement `Clone`, so this call clones \ + err.span_help( + span, + format!( + "`{}` doesn't implement `Clone`, so this call clones \ the reference `{ty}`", - ty.peel_refs(), - ), - ); - } - // The type doesn't implement Clone. - let trait_ref = ty::Binder::dummy(ty::TraitRef::new( - self.infcx.tcx, - clone_trait, - [ty.peel_refs()], - )); - let obligation = traits::Obligation::new( - self.infcx.tcx, - traits::ObligationCause::dummy(), - self.infcx.param_env, - trait_ref, - ); - self.infcx.err_ctxt().suggest_derive( - &obligation, - err, - trait_ref.upcast(self.infcx.tcx), - ); - } - Some(errors) => { - if let hir::ExprKind::MethodCall(segment, _rcvr, [], span) = - expr.kind - && segment.ident.name == sym::clone - { - err.span_help( - span, - format!( - "`{}` doesn't implement `Clone` because its \ + ty.peel_refs(), + ), + ); + } + // The type doesn't implement Clone. + let trait_ref = ty::Binder::dummy(ty::TraitRef::new( + self.infcx.tcx, + clone_trait, + [ty.peel_refs()], + )); + let obligation = traits::Obligation::new( + self.infcx.tcx, + traits::ObligationCause::dummy(), + self.infcx.param_env, + trait_ref, + ); + self.infcx.err_ctxt().suggest_derive( + &obligation, + err, + trait_ref.upcast(self.infcx.tcx), + ); + } + Some(errors) => { + if let hir::ExprKind::MethodCall(segment, _rcvr, [], span) = expr.kind + && segment.ident.name == sym::clone + { + err.span_help( + span, + format!( + "`{}` doesn't implement `Clone` because its \ implementations trait bounds could not be met, so \ this call clones the reference `{ty}`", - ty.peel_refs(), - ), - ); - err.note(format!( - "the following trait bounds weren't met: {}", - errors - .iter() - .map(|e| e.obligation.predicate.to_string()) - .collect::<Vec<_>>() - .join("\n"), - )); - } - // The type doesn't implement Clone because of unmet obligations. - for error in errors { - if let traits::FulfillmentErrorCode::Select( - traits::SelectionError::Unimplemented, - ) = error.code - && let ty::PredicateKind::Clause(ty::ClauseKind::Trait( - pred, - )) = error.obligation.predicate.kind().skip_binder() - { - self.infcx.err_ctxt().suggest_derive( - &error.obligation, - err, - error.obligation.predicate.kind().rebind(pred), - ); - } - } - } - } + ty.peel_refs(), + ), + ); + err.note(format!( + "the following trait bounds weren't met: {}", + errors + .iter() + .map(|e| e.obligation.predicate.to_string()) + .collect::<Vec<_>>() + .join("\n"), + )); } - let (changing, span, sugg) = match local.ty { - Some(ty) => ("changing", ty.span, message), - None => { - ("specifying", local.pat.span.shrink_to_hi(), format!(": {message}")) + // The type doesn't implement Clone because of unmet obligations. + for error in errors { + if let traits::FulfillmentErrorCode::Select( + traits::SelectionError::Unimplemented, + ) = error.code + && let ty::PredicateKind::Clause(ty::ClauseKind::Trait(pred)) = + error.obligation.predicate.kind().skip_binder() + { + self.infcx.err_ctxt().suggest_derive( + &error.obligation, + err, + error.obligation.predicate.kind().rebind(pred), + ); } - }; - err.span_suggestion_verbose( - span, - format!("consider {changing} this binding's type"), - sugg, - Applicability::HasPlaceholders, - ); - } else { - err.span_label( - err_label_span, - format!("consider changing this binding's type to be: `{message}`"), - ); + } } } - None => {} } + let (changing, span, sugg) = match local.ty { + Some(ty) => ("changing", ty.span, sugg_str), + None => ("specifying", local.pat.span.shrink_to_hi(), format!(": {sugg_str}")), + }; + err.span_suggestion_verbose( + span, + format!("consider {changing} this binding's type"), + sugg, + Applicability::HasPlaceholders, + ); } } @@ -1463,11 +1492,25 @@ fn suggest_ampmut_self(tcx: TyCtxt<'_>, span: Span) -> (Span, String) { } } -struct AmpMutSugg { - has_sugg: bool, - span: Span, - suggestion: String, - additional: Option<(Span, String)>, +enum AmpMutSugg { + /// Type suggestion. Changes `&self` to `&mut self`, `x: &T` to `x: &mut T`, + /// `ref x` to `ref mut x`, etc. + Type { + span: Span, + suggestion: String, + additional: Option<(Span, String)>, + }, + /// Suggestion for expressions, `&x` to `&mut x`, `&x[i]` to `&mut x[i]`, etc. + Expr { + span: Span, + suggestion: String, + }, + /// Suggests `.get_mut` in the case of `&map[&key]` for Hash/BTreeMap. + MapGetMut { + span: Span, + suggestion: String, + }, + ChangeBinding, } // When we want to suggest a user change a local variable to be a `&mut`, there @@ -1486,110 +1529,111 @@ struct AmpMutSugg { // This implementation attempts to emulate AST-borrowck prioritization // by trying (3.), then (2.) and finally falling back on (1.). fn suggest_ampmut<'tcx>( - tcx: TyCtxt<'tcx>, - decl_ty: Ty<'tcx>, - decl_span: Span, - opt_assignment_rhs_span: Option<Span>, - opt_ty_info: Option<Span>, + infcx: &crate::BorrowckInferCtxt<'tcx>, + body: &Body<'tcx>, + opt_assignment_rhs_stmt: Option<&Statement<'tcx>>, ) -> Option<AmpMutSugg> { - // if there is a RHS and it starts with a `&` from it, then check if it is + let tcx = infcx.tcx; + // If there is a RHS and it starts with a `&` from it, then check if it is // mutable, and if not, put suggest putting `mut ` to make it mutable. - // we don't have to worry about lifetime annotations here because they are + // We don't have to worry about lifetime annotations here because they are // not valid when taking a reference. For example, the following is not valid Rust: // // let x: &i32 = &'a 5; // ^^ lifetime annotation not allowed // - if let Some(rhs_span) = opt_assignment_rhs_span - && let Ok(rhs_str) = tcx.sess.source_map().span_to_snippet(rhs_span) - && let Some(rhs_str_no_amp) = rhs_str.strip_prefix('&') + if let Some(rhs_stmt) = opt_assignment_rhs_stmt + && let StatementKind::Assign(box (lhs, rvalue)) = &rhs_stmt.kind + && let mut rhs_span = rhs_stmt.source_info.span + && let Ok(mut rhs_str) = tcx.sess.source_map().span_to_snippet(rhs_span) { - // Suggest changing `&raw const` to `&raw mut` if applicable. - if rhs_str_no_amp.trim_start().strip_prefix("raw const").is_some() { - let const_idx = rhs_str.find("const").unwrap() as u32; - let const_span = rhs_span - .with_lo(rhs_span.lo() + BytePos(const_idx)) - .with_hi(rhs_span.lo() + BytePos(const_idx + "const".len() as u32)); - - return Some(AmpMutSugg { - has_sugg: true, - span: const_span, - suggestion: "mut".to_owned(), - additional: None, - }); + let mut rvalue = rvalue; + + // Take some special care when handling `let _x = &*_y`: + // We want to know if this is part of an overloaded index, so `let x = &a[0]`, + // or whether this is a usertype ascription (`let _x: &T = y`). + if let Rvalue::Ref(_, BorrowKind::Shared, place) = rvalue + && place.projection.len() == 1 + && place.projection[0] == ProjectionElem::Deref + && let Some(assign) = find_assignments(&body, place.local).first() + { + // If this is a usertype ascription (`let _x: &T = _y`) then pierce through it as either we want + // to suggest `&mut` on the expression (handled here) or we return `None` and let the caller + // suggest `&mut` on the type if the expression seems fine (e.g. `let _x: &T = &mut _y`). + if let Some(user_ty_projs) = body.local_decls[lhs.local].user_ty.as_ref() + && let [user_ty_proj] = user_ty_projs.contents.as_slice() + && user_ty_proj.projs.is_empty() + && let Either::Left(rhs_stmt_new) = body.stmt_at(*assign) + && let StatementKind::Assign(box (_, rvalue_new)) = &rhs_stmt_new.kind + && let rhs_span_new = rhs_stmt_new.source_info.span + && let Ok(rhs_str_new) = tcx.sess.source_map().span_to_snippet(rhs_span) + { + (rvalue, rhs_span, rhs_str) = (rvalue_new, rhs_span_new, rhs_str_new); + } + + if let Either::Right(call) = body.stmt_at(*assign) + && let TerminatorKind::Call { + func: Operand::Constant(box const_operand), args, .. + } = &call.kind + && let ty::FnDef(method_def_id, method_args) = *const_operand.ty().kind() + && let Some(trait_) = tcx.trait_of_assoc(method_def_id) + && tcx.is_lang_item(trait_, hir::LangItem::Index) + { + let trait_ref = ty::TraitRef::from_assoc( + tcx, + tcx.require_lang_item(hir::LangItem::IndexMut, rhs_span), + method_args, + ); + // The type only implements `Index` but not `IndexMut`, we must not suggest `&mut`. + if !infcx + .type_implements_trait(trait_ref.def_id, trait_ref.args, infcx.param_env) + .must_apply_considering_regions() + { + // Suggest `get_mut` if type is a `BTreeMap` or `HashMap`. + if let ty::Adt(def, _) = trait_ref.self_ty().kind() + && [sym::BTreeMap, sym::HashMap] + .into_iter() + .any(|s| tcx.is_diagnostic_item(s, def.did())) + && let [map, key] = &**args + && let Ok(map) = tcx.sess.source_map().span_to_snippet(map.span) + && let Ok(key) = tcx.sess.source_map().span_to_snippet(key.span) + { + let span = rhs_span; + let suggestion = format!("{map}.get_mut({key}).unwrap()"); + return Some(AmpMutSugg::MapGetMut { span, suggestion }); + } + return None; + } + } } - // Figure out if rhs already is `&mut`. - let is_mut = if let Some(rest) = rhs_str_no_amp.trim_start().strip_prefix("mut") { - match rest.chars().next() { - // e.g. `&mut x` - Some(c) if c.is_whitespace() => true, - // e.g. `&mut(x)` - Some('(') => true, - // e.g. `&mut{x}` - Some('{') => true, - // e.g. `&mutablevar` - _ => false, + let sugg = match rvalue { + Rvalue::Ref(_, BorrowKind::Shared, _) if let Some(ref_idx) = rhs_str.find('&') => { + // Shrink the span to just after the `&` in `&variable`. + Some(( + rhs_span.with_lo(rhs_span.lo() + BytePos(ref_idx as u32 + 1)).shrink_to_lo(), + "mut ".to_owned(), + )) } - } else { - false + Rvalue::RawPtr(RawPtrKind::Const, _) if let Some(const_idx) = rhs_str.find("const") => { + // Suggest changing `&raw const` to `&raw mut` if applicable. + let const_idx = const_idx as u32; + Some(( + rhs_span + .with_lo(rhs_span.lo() + BytePos(const_idx)) + .with_hi(rhs_span.lo() + BytePos(const_idx + "const".len() as u32)), + "mut".to_owned(), + )) + } + _ => None, }; - // if the reference is already mutable then there is nothing we can do - // here. - if !is_mut { - // shrink the span to just after the `&` in `&variable` - let span = rhs_span.with_lo(rhs_span.lo() + BytePos(1)).shrink_to_lo(); - - // FIXME(Ezrashaw): returning is bad because we still might want to - // update the annotated type, see #106857. - return Some(AmpMutSugg { - has_sugg: true, - span, - suggestion: "mut ".to_owned(), - additional: None, - }); + + if let Some((span, suggestion)) = sugg { + return Some(AmpMutSugg::Expr { span, suggestion }); } } - let (binding_exists, span) = match opt_ty_info { - // if this is a variable binding with an explicit type, - // then we will suggest changing it to be mutable. - // this is `Applicability::MachineApplicable`. - Some(ty_span) => (true, ty_span), - - // otherwise, we'll suggest *adding* an annotated type, we'll suggest - // the RHS's type for that. - // this is `Applicability::HasPlaceholders`. - None => (false, decl_span), - }; - - // if the binding already exists and is a reference with an explicit - // lifetime, then we can suggest adding ` mut`. this is special-cased from - // the path without an explicit lifetime. - if let Ok(src) = tcx.sess.source_map().span_to_snippet(span) - && src.starts_with("&'") - // note that `& 'a T` is invalid so this is correct. - && let Some(ws_pos) = src.find(char::is_whitespace) - { - let span = span.with_lo(span.lo() + BytePos(ws_pos as u32)).shrink_to_lo(); - Some(AmpMutSugg { has_sugg: true, span, suggestion: " mut".to_owned(), additional: None }) - // if there is already a binding, we modify it to be `mut` - } else if binding_exists { - // shrink the span to just after the `&` in `&variable` - let span = span.with_lo(span.lo() + BytePos(1)).shrink_to_lo(); - Some(AmpMutSugg { has_sugg: true, span, suggestion: "mut ".to_owned(), additional: None }) - } else { - // otherwise, suggest that the user annotates the binding; we provide the - // type of the local. - let ty = decl_ty.builtin_deref(true).unwrap(); - - Some(AmpMutSugg { - has_sugg: false, - span, - suggestion: format!("{}mut {}", if decl_ty.is_ref() { "&" } else { "*" }, ty), - additional: None, - }) - } + Some(AmpMutSugg::ChangeBinding) } /// If the type is a `Coroutine`, `Closure`, or `CoroutineClosure` diff --git a/compiler/rustc_borrowck/src/diagnostics/opaque_types.rs b/compiler/rustc_borrowck/src/diagnostics/opaque_types.rs index 83fe4a9f98f..99913626418 100644 --- a/compiler/rustc_borrowck/src/diagnostics/opaque_types.rs +++ b/compiler/rustc_borrowck/src/diagnostics/opaque_types.rs @@ -13,6 +13,8 @@ use rustc_middle::mir::{self, ConstraintCategory, Location}; use rustc_middle::ty::{ self, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor, }; +use rustc_span::Span; +use rustc_trait_selection::error_reporting::infer::region::unexpected_hidden_region_diagnostic; use rustc_trait_selection::errors::impl_trait_overcapture_suggestion; use crate::MirBorrowckCtxt; @@ -26,13 +28,61 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { if errors.is_empty() { return; } + + let infcx = self.infcx; let mut guar = None; + let mut last_unexpected_hidden_region: Option<(Span, Ty<'_>, ty::OpaqueTypeKey<'tcx>)> = + None; for error in errors { guar = Some(match error { - DeferredOpaqueTypeError::InvalidOpaqueTypeArgs(err) => err.report(self.infcx), + DeferredOpaqueTypeError::InvalidOpaqueTypeArgs(err) => err.report(infcx), DeferredOpaqueTypeError::LifetimeMismatchOpaqueParam(err) => { - self.infcx.dcx().emit_err(err) + infcx.dcx().emit_err(err) + } + DeferredOpaqueTypeError::UnexpectedHiddenRegion { + opaque_type_key, + hidden_type, + member_region, + } => { + let named_ty = + self.regioncx.name_regions_for_member_constraint(infcx.tcx, hidden_type.ty); + let named_key = self + .regioncx + .name_regions_for_member_constraint(infcx.tcx, opaque_type_key); + let named_region = + self.regioncx.name_regions_for_member_constraint(infcx.tcx, member_region); + let diag = unexpected_hidden_region_diagnostic( + infcx, + self.mir_def_id(), + hidden_type.span, + named_ty, + named_region, + named_key, + ); + if last_unexpected_hidden_region + != Some((hidden_type.span, named_ty, named_key)) + { + last_unexpected_hidden_region = + Some((hidden_type.span, named_ty, named_key)); + diag.emit() + } else { + diag.delay_as_bug() + } } + DeferredOpaqueTypeError::NonDefiningUseInDefiningScope { + span, + opaque_type_key, + } => infcx.dcx().span_err( + span, + format!( + "non-defining use of `{}` in the defining scope", + Ty::new_opaque( + infcx.tcx, + opaque_type_key.def_id.to_def_id(), + opaque_type_key.args + ) + ), + ), }); } let guar = guar.unwrap(); @@ -193,10 +243,9 @@ impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for FindOpaqueRegion<'_, 'tcx> { let opaque_region_vid = self.regioncx.to_region_vid(opaque_region); // Find a path between the borrow region and our opaque capture. - if let Some((path, _)) = - self.regioncx.find_constraint_paths_between_regions(self.borrow_region, |r| { - r == opaque_region_vid - }) + if let Some(path) = self + .regioncx + .constraint_path_between_regions(self.borrow_region, opaque_region_vid) { for constraint in path { // If we find a call in this path, then check if it defines the opaque. diff --git a/compiler/rustc_borrowck/src/diagnostics/region_errors.rs b/compiler/rustc_borrowck/src/diagnostics/region_errors.rs index 2b74f1a48f7..bec4c934502 100644 --- a/compiler/rustc_borrowck/src/diagnostics/region_errors.rs +++ b/compiler/rustc_borrowck/src/diagnostics/region_errors.rs @@ -23,7 +23,6 @@ use rustc_trait_selection::error_reporting::infer::nice_region_error::{ self, HirTraitObjectVisitor, NiceRegionError, TraitObjectVisitor, find_anon_type, find_param_with_region, suggest_adding_lifetime_params, }; -use rustc_trait_selection::error_reporting::infer::region::unexpected_hidden_region_diagnostic; use rustc_trait_selection::infer::InferCtxtExt; use rustc_trait_selection::traits::{Obligation, ObligationCtxt}; use tracing::{debug, instrument, trace}; @@ -62,7 +61,7 @@ impl<'tcx> ConstraintDescription for ConstraintCategory<'tcx> { | ConstraintCategory::Boring | ConstraintCategory::BoringNoLocation | ConstraintCategory::Internal - | ConstraintCategory::IllegalUniverse => "", + | ConstraintCategory::OutlivesUnnameablePlaceholder(..) => "", } } } @@ -105,18 +104,6 @@ pub(crate) enum RegionErrorKind<'tcx> { /// A generic bound failure for a type test (`T: 'a`). TypeTestError { type_test: TypeTest<'tcx> }, - /// An unexpected hidden region for an opaque type. - UnexpectedHiddenRegion { - /// The span for the member constraint. - span: Span, - /// The hidden type. - hidden_ty: Ty<'tcx>, - /// The opaque type. - key: ty::OpaqueTypeKey<'tcx>, - /// The unexpected region. - member_region: ty::Region<'tcx>, - }, - /// Higher-ranked subtyping error. BoundUniversalRegionError { /// The placeholder free region. @@ -215,7 +202,6 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { diag: &mut Diag<'_>, lower_bound: RegionVid, ) { - let mut suggestions = vec![]; let tcx = self.infcx.tcx; // find generic associated types in the given region 'lower_bound' @@ -237,9 +223,11 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { .collect::<Vec<_>>(); debug!(?gat_id_and_generics); - // find higher-ranked trait bounds bounded to the generic associated types + // Look for the where-bound which introduces the placeholder. + // As we're using the HIR, we need to handle both `for<'a> T: Trait<'a>` + // and `T: for<'a> Trait`<'a>. let mut hrtb_bounds = vec![]; - gat_id_and_generics.iter().flatten().for_each(|(gat_hir_id, generics)| { + gat_id_and_generics.iter().flatten().for_each(|&(gat_hir_id, generics)| { for pred in generics.predicates { let BoundPredicate(WhereBoundPredicate { bound_generic_params, bounds, .. }) = pred.kind @@ -248,17 +236,32 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { }; if bound_generic_params .iter() - .rfind(|bgp| tcx.local_def_id_to_hir_id(bgp.def_id) == *gat_hir_id) + .rfind(|bgp| tcx.local_def_id_to_hir_id(bgp.def_id) == gat_hir_id) .is_some() { for bound in *bounds { hrtb_bounds.push(bound); } + } else { + for bound in *bounds { + if let Trait(trait_bound) = bound { + if trait_bound + .bound_generic_params + .iter() + .rfind(|bgp| tcx.local_def_id_to_hir_id(bgp.def_id) == gat_hir_id) + .is_some() + { + hrtb_bounds.push(bound); + return; + } + } + } } } }); debug!(?hrtb_bounds); + let mut suggestions = vec![]; hrtb_bounds.iter().for_each(|bound| { let Trait(PolyTraitRef { trait_ref, span: trait_span, .. }) = bound else { return; @@ -307,11 +310,7 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { pub(crate) fn report_region_errors(&mut self, nll_errors: RegionErrors<'tcx>) { // Iterate through all the errors, producing a diagnostic for each one. The diagnostics are // buffered in the `MirBorrowckCtxt`. - let mut outlives_suggestion = OutlivesSuggestionBuilder::default(); - let mut last_unexpected_hidden_region: Option<(Span, Ty<'_>, ty::OpaqueTypeKey<'tcx>)> = - None; - for (nll_error, _) in nll_errors.into_iter() { match nll_error { RegionErrorKind::TypeTestError { type_test } => { @@ -362,30 +361,6 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { } } - RegionErrorKind::UnexpectedHiddenRegion { span, hidden_ty, key, member_region } => { - let named_ty = - self.regioncx.name_regions_for_member_constraint(self.infcx.tcx, hidden_ty); - let named_key = - self.regioncx.name_regions_for_member_constraint(self.infcx.tcx, key); - let named_region = self - .regioncx - .name_regions_for_member_constraint(self.infcx.tcx, member_region); - let diag = unexpected_hidden_region_diagnostic( - self.infcx, - self.mir_def_id(), - span, - named_ty, - named_region, - named_key, - ); - if last_unexpected_hidden_region != Some((span, named_ty, named_key)) { - self.buffer_error(diag); - last_unexpected_hidden_region = Some((span, named_ty, named_key)); - } else { - diag.delay_as_bug(); - } - } - RegionErrorKind::BoundUniversalRegionError { longer_fr, placeholder, @@ -394,11 +369,15 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { let error_vid = self.regioncx.region_from_element(longer_fr, &error_element); // Find the code to blame for the fact that `longer_fr` outlives `error_fr`. - let (_, cause) = self.regioncx.find_outlives_blame_span( - longer_fr, - NllRegionVariableOrigin::Placeholder(placeholder), - error_vid, - ); + let cause = self + .regioncx + .best_blame_constraint( + longer_fr, + NllRegionVariableOrigin::Placeholder(placeholder), + error_vid, + ) + .0 + .cause; let universe = placeholder.universe; let universe_info = self.regioncx.universe_info(universe); @@ -454,9 +433,8 @@ impl<'infcx, 'tcx> MirBorrowckCtxt<'_, 'infcx, 'tcx> { ) { debug!("report_region_error(fr={:?}, outlived_fr={:?})", fr, outlived_fr); - let (blame_constraint, path) = self.regioncx.best_blame_constraint(fr, fr_origin, |r| { - self.regioncx.provides_universal_region(r, fr, outlived_fr) - }); + let (blame_constraint, path) = + self.regioncx.best_blame_constraint(fr, fr_origin, outlived_fr); let BlameConstraint { category, cause, variance_info, .. } = blame_constraint; debug!("report_region_error: category={:?} {:?} {:?}", category, cause, variance_info); diff --git a/compiler/rustc_borrowck/src/handle_placeholders.rs b/compiler/rustc_borrowck/src/handle_placeholders.rs index 34599ac55b8..94379cdebf7 100644 --- a/compiler/rustc_borrowck/src/handle_placeholders.rs +++ b/compiler/rustc_borrowck/src/handle_placeholders.rs @@ -1,7 +1,6 @@ //! Logic for lowering higher-kinded outlives constraints //! (with placeholders and universes) and turn them into regular //! outlives constraints. - use rustc_data_structures::frozen::Frozen; use rustc_data_structures::fx::FxIndexMap; use rustc_data_structures::graph::scc; @@ -10,12 +9,11 @@ use rustc_index::IndexVec; use rustc_infer::infer::RegionVariableOrigin; use rustc_middle::mir::ConstraintCategory; use rustc_middle::ty::{RegionVid, UniverseIndex}; -use tracing::debug; +use tracing::{debug, trace}; use crate::constraints::{ConstraintSccIndex, OutlivesConstraintSet}; use crate::consumers::OutlivesConstraint; use crate::diagnostics::UniverseInfo; -use crate::member_constraints::MemberConstraintSet; use crate::region_infer::values::{LivenessValues, PlaceholderIndices}; use crate::region_infer::{ConstraintSccs, RegionDefinition, Representative, TypeTest}; use crate::ty::VarianceDiagInfo; @@ -30,7 +28,6 @@ pub(crate) struct LoweredConstraints<'tcx> { pub(crate) constraint_sccs: Sccs<RegionVid, ConstraintSccIndex>, pub(crate) definitions: Frozen<IndexVec<RegionVid, RegionDefinition<'tcx>>>, pub(crate) scc_annotations: IndexVec<ConstraintSccIndex, RegionTracker>, - pub(crate) member_constraints: MemberConstraintSet<'tcx, RegionVid>, pub(crate) outlives_constraints: Frozen<OutlivesConstraintSet<'tcx>>, pub(crate) type_tests: Vec<TypeTest<'tcx>>, pub(crate) liveness_constraints: LivenessValues, @@ -64,18 +61,71 @@ impl scc::Annotations<RegionVid> for SccAnnotations<'_, '_, RegionTracker> { type SccIdx = ConstraintSccIndex; } +#[derive(Copy, Debug, Clone, PartialEq, Eq)] +enum PlaceholderReachability { + /// This SCC reaches no placeholders. + NoPlaceholders, + /// This SCC reaches at least one placeholder. + Placeholders { + /// The largest-universed placeholder we can reach + max_universe: (UniverseIndex, RegionVid), + + /// The placeholder with the smallest ID + min_placeholder: RegionVid, + + /// The placeholder with the largest ID + max_placeholder: RegionVid, + }, +} + +impl PlaceholderReachability { + /// Merge the reachable placeholders of two graph components. + fn merge(self, other: PlaceholderReachability) -> PlaceholderReachability { + use PlaceholderReachability::*; + match (self, other) { + (NoPlaceholders, NoPlaceholders) => NoPlaceholders, + (NoPlaceholders, p @ Placeholders { .. }) + | (p @ Placeholders { .. }, NoPlaceholders) => p, + ( + Placeholders { + min_placeholder: min_pl, + max_placeholder: max_pl, + max_universe: max_u, + }, + Placeholders { min_placeholder, max_placeholder, max_universe }, + ) => Placeholders { + min_placeholder: min_pl.min(min_placeholder), + max_placeholder: max_pl.max(max_placeholder), + max_universe: max_u.max(max_universe), + }, + } + } + + fn max_universe(&self) -> Option<(UniverseIndex, RegionVid)> { + match self { + Self::NoPlaceholders => None, + Self::Placeholders { max_universe, .. } => Some(*max_universe), + } + } + + /// If we have reached placeholders, determine if they can + /// be named from this universe. + fn can_be_named_by(&self, from: UniverseIndex) -> bool { + self.max_universe() + .is_none_or(|(max_placeholder_universe, _)| from.can_name(max_placeholder_universe)) + } +} + /// An annotation for region graph SCCs that tracks /// the values of its elements. This annotates a single SCC. #[derive(Copy, Debug, Clone)] pub(crate) struct RegionTracker { - /// The largest universe of a placeholder reached from this SCC. - /// This includes placeholders within this SCC. - max_placeholder_universe_reached: UniverseIndex, + reachable_placeholders: PlaceholderReachability, /// The largest universe nameable from this SCC. /// It is the smallest nameable universes of all - /// existential regions reachable from it. - max_nameable_universe: UniverseIndex, + /// existential regions reachable from it. Small Rvids are preferred. + max_nameable_universe: (UniverseIndex, RegionVid), /// The representative Region Variable Id for this SCC. pub(crate) representative: Representative, @@ -83,69 +133,82 @@ pub(crate) struct RegionTracker { impl RegionTracker { pub(crate) fn new(rvid: RegionVid, definition: &RegionDefinition<'_>) -> Self { - let placeholder_universe = + let reachable_placeholders = if matches!(definition.origin, NllRegionVariableOrigin::Placeholder(_)) { - definition.universe + PlaceholderReachability::Placeholders { + max_universe: (definition.universe, rvid), + min_placeholder: rvid, + max_placeholder: rvid, + } } else { - UniverseIndex::ROOT + PlaceholderReachability::NoPlaceholders }; Self { - max_placeholder_universe_reached: placeholder_universe, - max_nameable_universe: definition.universe, + reachable_placeholders, + max_nameable_universe: (definition.universe, rvid), representative: Representative::new(rvid, definition), } } /// The largest universe this SCC can name. It's the smallest - /// largest nameable uninverse of any reachable region. + /// largest nameable universe of any reachable region, or + /// `max_nameable(r) = min (max_nameable(r') for r' reachable from r)` pub(crate) fn max_nameable_universe(self) -> UniverseIndex { - self.max_nameable_universe + self.max_nameable_universe.0 } - fn merge_min_max_seen(&mut self, other: &Self) { - self.max_placeholder_universe_reached = std::cmp::max( - self.max_placeholder_universe_reached, - other.max_placeholder_universe_reached, - ); - - self.max_nameable_universe = - std::cmp::min(self.max_nameable_universe, other.max_nameable_universe); - } - - /// Returns `true` if during the annotated SCC reaches a placeholder - /// with a universe larger than the smallest nameable universe of any - /// reachable existential region. - pub(crate) fn has_incompatible_universes(&self) -> bool { - self.max_nameable_universe().cannot_name(self.max_placeholder_universe_reached) + pub(crate) fn max_placeholder_universe_reached(self) -> UniverseIndex { + if let Some((universe, _)) = self.reachable_placeholders.max_universe() { + universe + } else { + UniverseIndex::ROOT + } } /// Determine if the tracked universes of the two SCCs are compatible. pub(crate) fn universe_compatible_with(&self, other: Self) -> bool { + // HACK: We first check whether we can name the highest existential universe + // of `other`. This only exists to avoid errors in case that scc already + // depends on a placeholder it cannot name itself. self.max_nameable_universe().can_name(other.max_nameable_universe()) - || self.max_nameable_universe().can_name(other.max_placeholder_universe_reached) + || other.reachable_placeholders.can_be_named_by(self.max_nameable_universe()) + } + + /// If this SCC reaches a placeholder it can't name, return it. + fn unnameable_placeholder(&self) -> Option<(UniverseIndex, RegionVid)> { + self.reachable_placeholders.max_universe().filter(|&(placeholder_universe, _)| { + !self.max_nameable_universe().can_name(placeholder_universe) + }) } } impl scc::Annotation for RegionTracker { - fn merge_scc(mut self, other: Self) -> Self { - self.representative = self.representative.merge_scc(other.representative); - self.merge_min_max_seen(&other); - self + fn merge_scc(self, other: Self) -> Self { + trace!("{:?} << {:?}", self.representative, other.representative); + + Self { + representative: self.representative.min(other.representative), + max_nameable_universe: self.max_nameable_universe.min(other.max_nameable_universe), + reachable_placeholders: self.reachable_placeholders.merge(other.reachable_placeholders), + } } - fn merge_reached(mut self, other: Self) -> Self { - // No update to in-component values, only add seen values. - self.merge_min_max_seen(&other); - self + fn merge_reached(self, other: Self) -> Self { + Self { + max_nameable_universe: self.max_nameable_universe.min(other.max_nameable_universe), + reachable_placeholders: self.reachable_placeholders.merge(other.reachable_placeholders), + representative: self.representative, + } } } /// Determines if the region variable definitions contain /// placeholders, and compute them for later use. -fn region_definitions<'tcx>( - universal_regions: &UniversalRegions<'tcx>, +// FIXME: This is also used by opaque type handling. Move it to a separate file. +pub(super) fn region_definitions<'tcx>( infcx: &BorrowckInferCtxt<'tcx>, + universal_regions: &UniversalRegions<'tcx>, ) -> (Frozen<IndexVec<RegionVid, RegionDefinition<'tcx>>>, bool) { let var_infos = infcx.get_region_var_infos(); // Create a RegionDefinition for each inference variable. This happens here because @@ -209,14 +272,13 @@ pub(crate) fn compute_sccs_applying_placeholder_outlives_constraints<'tcx>( infcx: &BorrowckInferCtxt<'tcx>, ) -> LoweredConstraints<'tcx> { let universal_regions = &universal_region_relations.universal_regions; - let (definitions, has_placeholders) = region_definitions(universal_regions, infcx); + let (definitions, has_placeholders) = region_definitions(infcx, universal_regions); let MirTypeckRegionConstraints { placeholder_indices, placeholder_index_to_region: _, liveness_constraints, mut outlives_constraints, - member_constraints, universe_causes, type_tests, } = constraints; @@ -242,7 +304,6 @@ pub(crate) fn compute_sccs_applying_placeholder_outlives_constraints<'tcx>( return LoweredConstraints { type_tests, - member_constraints, constraint_sccs, scc_annotations: scc_annotations.scc_to_annotation, definitions, @@ -279,7 +340,6 @@ pub(crate) fn compute_sccs_applying_placeholder_outlives_constraints<'tcx>( constraint_sccs, definitions, scc_annotations, - member_constraints, outlives_constraints: Frozen::freeze(outlives_constraints), type_tests, liveness_constraints, @@ -310,28 +370,52 @@ fn rewrite_placeholder_outlives<'tcx>( let annotation = annotations[scc]; - // If this SCC participates in a universe violation, - // e.g. if it reaches a region with a universe smaller than - // the largest region reached, add a requirement that it must - // outlive `'static`. - if annotation.has_incompatible_universes() { - // Optimisation opportunity: this will add more constraints than - // needed for correctness, since an SCC upstream of another with - // a universe violation will "infect" its downstream SCCs to also - // outlive static. - let scc_representative_outlives_static = OutlivesConstraint { - sup: annotation.representative.rvid(), - sub: fr_static, - category: ConstraintCategory::IllegalUniverse, - locations: Locations::All(rustc_span::DUMMY_SP), - span: rustc_span::DUMMY_SP, - variance_info: VarianceDiagInfo::None, - from_closure: false, - }; - outlives_constraints.push(scc_representative_outlives_static); - added_constraints = true; - debug!("Added {:?}: 'static!", annotation.representative.rvid()); - } + let Some((max_u, max_u_rvid)) = annotation.unnameable_placeholder() else { + continue; + }; + + debug!( + "Placeholder universe {max_u:?} is too large for its SCC, represented by {:?}", + annotation.representative + ); + + // We only add one `r: 'static` constraint per SCC, where `r` is the SCC representative. + // That constraint is annotated with some placeholder `unnameable` where + // `unnameable` is unnameable from `r` and there is a path in the constraint graph + // between them. + // + // There is one exception; if some other region in this SCC can't name `'r`, then + // we pick the region with the smallest universe in the SCC, so that a path can + // always start in `'r` to find a motivation that isn't cyclic. + let blame_to = if annotation.representative.rvid() == max_u_rvid { + // Assertion: the region that lowered our universe is an existential one and we are a placeholder! + + // The SCC's representative is not nameable from some region + // that ends up in the SCC. + let small_universed_rvid = annotation.max_nameable_universe.1; + debug!( + "{small_universed_rvid:?} lowered our universe to {:?}", + annotation.max_nameable_universe() + ); + small_universed_rvid + } else { + // `max_u_rvid` is not nameable by the SCC's representative. + max_u_rvid + }; + + // FIXME: if we can extract a useful blame span here, future error + // reporting and constraint search can be simplified. + + added_constraints = true; + outlives_constraints.push(OutlivesConstraint { + sup: annotation.representative.rvid(), + sub: fr_static, + category: ConstraintCategory::OutlivesUnnameablePlaceholder(blame_to), + locations: Locations::All(rustc_span::DUMMY_SP), + span: rustc_span::DUMMY_SP, + variance_info: VarianceDiagInfo::None, + from_closure: false, + }); } added_constraints } diff --git a/compiler/rustc_borrowck/src/lib.rs b/compiler/rustc_borrowck/src/lib.rs index d76d6a04e6e..ce78ae203a4 100644 --- a/compiler/rustc_borrowck/src/lib.rs +++ b/compiler/rustc_borrowck/src/lib.rs @@ -78,7 +78,6 @@ mod dataflow; mod def_use; mod diagnostics; mod handle_placeholders; -mod member_constraints; mod nll; mod path_utils; mod place_ext; @@ -301,7 +300,7 @@ fn do_mir_borrowck<'tcx>( def: LocalDefId, ) -> PropagatedBorrowCheckResults<'tcx> { let tcx = root_cx.tcx; - let infcx = BorrowckInferCtxt::new(tcx, def); + let infcx = BorrowckInferCtxt::new(tcx, def, root_cx.root_def_id()); let (input_body, promoted) = tcx.mir_promoted(def); let input_body: &Body<'_> = &input_body.borrow(); let input_promoted: &IndexSlice<_, _> = &promoted.borrow(); @@ -335,9 +334,10 @@ fn do_mir_borrowck<'tcx>( // Run the MIR type-checker. let MirTypeckResults { - constraints, + mut constraints, universal_region_relations, - opaque_type_values, + region_bound_pairs, + known_type_outlives_obligations, polonius_context, } = type_check::type_check( root_cx, @@ -352,6 +352,17 @@ fn do_mir_borrowck<'tcx>( Rc::clone(&location_map), ); + let opaque_type_errors = region_infer::opaque_types::handle_opaque_type_uses( + root_cx, + &infcx, + &body, + &universal_region_relations, + ®ion_bound_pairs, + &known_type_outlives_obligations, + &location_map, + &mut constraints, + ); + // Compute non-lexical lifetimes using the constraints computed // by typechecking the MIR body. let nll::NllOutput { @@ -375,8 +386,6 @@ fn do_mir_borrowck<'tcx>( polonius_context, ); - let opaque_type_errors = regioncx.infer_opaque_types(root_cx, &infcx, opaque_type_values); - // Dump MIR results into a file, if that is enabled. This lets us // write unit-tests, as well as helping with debugging. nll::dump_nll_mir(&infcx, body, ®ioncx, &opt_closure_req, &borrow_set); @@ -581,12 +590,13 @@ fn get_flow_results<'a, 'tcx>( pub(crate) struct BorrowckInferCtxt<'tcx> { pub(crate) infcx: InferCtxt<'tcx>, - pub(crate) reg_var_to_origin: RefCell<FxIndexMap<ty::RegionVid, RegionCtxt>>, + pub(crate) root_def_id: LocalDefId, pub(crate) param_env: ParamEnv<'tcx>, + pub(crate) reg_var_to_origin: RefCell<FxIndexMap<ty::RegionVid, RegionCtxt>>, } impl<'tcx> BorrowckInferCtxt<'tcx> { - pub(crate) fn new(tcx: TyCtxt<'tcx>, def_id: LocalDefId) -> Self { + pub(crate) fn new(tcx: TyCtxt<'tcx>, def_id: LocalDefId, root_def_id: LocalDefId) -> Self { let typing_mode = if tcx.use_typing_mode_borrowck() { TypingMode::borrowck(tcx, def_id) } else { @@ -594,7 +604,12 @@ impl<'tcx> BorrowckInferCtxt<'tcx> { }; let infcx = tcx.infer_ctxt().build(typing_mode); let param_env = tcx.param_env(def_id); - BorrowckInferCtxt { infcx, reg_var_to_origin: RefCell::new(Default::default()), param_env } + BorrowckInferCtxt { + infcx, + root_def_id, + reg_var_to_origin: RefCell::new(Default::default()), + param_env, + } } pub(crate) fn next_region_var<F>( diff --git a/compiler/rustc_borrowck/src/member_constraints.rs b/compiler/rustc_borrowck/src/member_constraints.rs deleted file mode 100644 index bdd0f6fe11e..00000000000 --- a/compiler/rustc_borrowck/src/member_constraints.rs +++ /dev/null @@ -1,226 +0,0 @@ -use std::hash::Hash; -use std::ops::Index; - -use rustc_data_structures::fx::FxIndexMap; -use rustc_index::{IndexSlice, IndexVec}; -use rustc_middle::ty::{self, Ty}; -use rustc_span::Span; -use tracing::instrument; - -/// Compactly stores a set of `R0 member of [R1...Rn]` constraints, -/// indexed by the region `R0`. -#[derive(Debug)] -pub(crate) struct MemberConstraintSet<'tcx, R> -where - R: Copy + Eq, -{ - /// Stores the first "member" constraint for a given `R0`. This is an - /// index into the `constraints` vector below. - first_constraints: FxIndexMap<R, NllMemberConstraintIndex>, - - /// Stores the data about each `R0 member of [R1..Rn]` constraint. - /// These are organized into a linked list, so each constraint - /// contains the index of the next constraint with the same `R0`. - constraints: IndexVec<NllMemberConstraintIndex, MemberConstraint<'tcx>>, - - /// Stores the `R1..Rn` regions for *all* sets. For any given - /// constraint, we keep two indices so that we can pull out a - /// slice. - choice_regions: Vec<ty::RegionVid>, -} - -/// Represents a `R0 member of [R1..Rn]` constraint -#[derive(Debug)] -pub(crate) struct MemberConstraint<'tcx> { - next_constraint: Option<NllMemberConstraintIndex>, - - /// The span where the hidden type was instantiated. - pub(crate) definition_span: Span, - - /// The hidden type in which `R0` appears. (Used in error reporting.) - pub(crate) hidden_ty: Ty<'tcx>, - - pub(crate) key: ty::OpaqueTypeKey<'tcx>, - - /// The region `R0`. - pub(crate) member_region_vid: ty::RegionVid, - - /// Index of `R1` in `choice_regions` vector from `MemberConstraintSet`. - start_index: usize, - - /// Index of `Rn` in `choice_regions` vector from `MemberConstraintSet`. - end_index: usize, -} - -rustc_index::newtype_index! { - #[debug_format = "MemberConstraintIndex({})"] - pub(crate) struct NllMemberConstraintIndex {} -} - -impl Default for MemberConstraintSet<'_, ty::RegionVid> { - fn default() -> Self { - Self { - first_constraints: Default::default(), - constraints: Default::default(), - choice_regions: Default::default(), - } - } -} - -impl<'tcx> MemberConstraintSet<'tcx, ty::RegionVid> { - pub(crate) fn is_empty(&self) -> bool { - self.constraints.is_empty() - } - - /// Pushes a member constraint into the set. - #[instrument(level = "debug", skip(self))] - pub(crate) fn add_member_constraint( - &mut self, - key: ty::OpaqueTypeKey<'tcx>, - hidden_ty: Ty<'tcx>, - definition_span: Span, - member_region_vid: ty::RegionVid, - choice_regions: &[ty::RegionVid], - ) { - let next_constraint = self.first_constraints.get(&member_region_vid).cloned(); - let start_index = self.choice_regions.len(); - self.choice_regions.extend(choice_regions); - let end_index = self.choice_regions.len(); - let constraint_index = self.constraints.push(MemberConstraint { - next_constraint, - member_region_vid, - definition_span, - hidden_ty, - key, - start_index, - end_index, - }); - self.first_constraints.insert(member_region_vid, constraint_index); - } -} - -impl<'tcx, R1> MemberConstraintSet<'tcx, R1> -where - R1: Copy + Hash + Eq, -{ - /// Remap the "member region" key using `map_fn`, producing a new - /// member constraint set. This is used in the NLL code to map from - /// the original `RegionVid` to an scc index. In some cases, we - /// may have multiple `R1` values mapping to the same `R2` key -- that - /// is ok, the two sets will be merged. - pub(crate) fn into_mapped<R2>( - self, - mut map_fn: impl FnMut(R1) -> R2, - ) -> MemberConstraintSet<'tcx, R2> - where - R2: Copy + Hash + Eq, - { - // We can re-use most of the original data, just tweaking the - // linked list links a bit. - // - // For example if we had two keys `Ra` and `Rb` that both now - // wind up mapped to the same key `S`, we would append the - // linked list for `Ra` onto the end of the linked list for - // `Rb` (or vice versa) -- this basically just requires - // rewriting the final link from one list to point at the other - // other (see `append_list`). - - let MemberConstraintSet { first_constraints, mut constraints, choice_regions } = self; - - let mut first_constraints2 = FxIndexMap::default(); - first_constraints2.reserve(first_constraints.len()); - - for (r1, start1) in first_constraints { - let r2 = map_fn(r1); - if let Some(&start2) = first_constraints2.get(&r2) { - append_list(&mut constraints, start1, start2); - } - first_constraints2.insert(r2, start1); - } - - MemberConstraintSet { first_constraints: first_constraints2, constraints, choice_regions } - } -} - -impl<'tcx, R> MemberConstraintSet<'tcx, R> -where - R: Copy + Hash + Eq, -{ - pub(crate) fn all_indices(&self) -> impl Iterator<Item = NllMemberConstraintIndex> { - self.constraints.indices() - } - - /// Iterate down the constraint indices associated with a given - /// peek-region. You can then use `choice_regions` and other - /// methods to access data. - pub(crate) fn indices( - &self, - member_region_vid: R, - ) -> impl Iterator<Item = NllMemberConstraintIndex> { - let mut next = self.first_constraints.get(&member_region_vid).cloned(); - std::iter::from_fn(move || -> Option<NllMemberConstraintIndex> { - if let Some(current) = next { - next = self.constraints[current].next_constraint; - Some(current) - } else { - None - } - }) - } - - /// Returns the "choice regions" for a given member - /// constraint. This is the `R1..Rn` from a constraint like: - /// - /// ```text - /// R0 member of [R1..Rn] - /// ``` - pub(crate) fn choice_regions(&self, pci: NllMemberConstraintIndex) -> &[ty::RegionVid] { - let MemberConstraint { start_index, end_index, .. } = &self.constraints[pci]; - &self.choice_regions[*start_index..*end_index] - } -} - -impl<'tcx, R> Index<NllMemberConstraintIndex> for MemberConstraintSet<'tcx, R> -where - R: Copy + Eq, -{ - type Output = MemberConstraint<'tcx>; - - fn index(&self, i: NllMemberConstraintIndex) -> &MemberConstraint<'tcx> { - &self.constraints[i] - } -} - -/// Given a linked list starting at `source_list` and another linked -/// list starting at `target_list`, modify `target_list` so that it is -/// followed by `source_list`. -/// -/// Before: -/// -/// ```text -/// target_list: A -> B -> C -> (None) -/// source_list: D -> E -> F -> (None) -/// ``` -/// -/// After: -/// -/// ```text -/// target_list: A -> B -> C -> D -> E -> F -> (None) -/// ``` -fn append_list( - constraints: &mut IndexSlice<NllMemberConstraintIndex, MemberConstraint<'_>>, - target_list: NllMemberConstraintIndex, - source_list: NllMemberConstraintIndex, -) { - let mut p = target_list; - loop { - let r = &mut constraints[p]; - match r.next_constraint { - Some(q) => p = q, - None => { - r.next_constraint = Some(source_list); - return; - } - } - } -} diff --git a/compiler/rustc_borrowck/src/region_infer/graphviz.rs b/compiler/rustc_borrowck/src/region_infer/graphviz.rs index b2f67c43125..526e1850c2e 100644 --- a/compiler/rustc_borrowck/src/region_infer/graphviz.rs +++ b/compiler/rustc_borrowck/src/region_infer/graphviz.rs @@ -12,9 +12,13 @@ use rustc_middle::ty::UniverseIndex; use super::*; fn render_outlives_constraint(constraint: &OutlivesConstraint<'_>) -> String { - match constraint.locations { - Locations::All(_) => "All(...)".to_string(), - Locations::Single(loc) => format!("{loc:?}"), + if let ConstraintCategory::OutlivesUnnameablePlaceholder(unnameable) = constraint.category { + format!("{unnameable:?} unnameable") + } else { + match constraint.locations { + Locations::All(_) => "All(...)".to_string(), + Locations::Single(loc) => format!("{loc:?}"), + } } } diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs index b0c31ac9601..9990f4cb3f2 100644 --- a/compiler/rustc_borrowck/src/region_infer/mod.rs +++ b/compiler/rustc_borrowck/src/region_infer/mod.rs @@ -1,11 +1,9 @@ -use std::cell::OnceCell; use std::collections::VecDeque; use std::rc::Rc; -use rustc_data_structures::binary_search_util; use rustc_data_structures::frozen::Frozen; use rustc_data_structures::fx::{FxIndexMap, FxIndexSet}; -use rustc_data_structures::graph::scc::{self, Sccs}; +use rustc_data_structures::graph::scc::Sccs; use rustc_errors::Diag; use rustc_hir::def_id::CRATE_DEF_ID; use rustc_index::IndexVec; @@ -24,15 +22,13 @@ use rustc_span::hygiene::DesugaringKind; use rustc_span::{DUMMY_SP, Span}; use tracing::{Level, debug, enabled, instrument, trace}; -use crate::constraints::graph::{self, NormalConstraintGraph, RegionGraph}; +use crate::constraints::graph::NormalConstraintGraph; use crate::constraints::{ConstraintSccIndex, OutlivesConstraint, OutlivesConstraintSet}; use crate::dataflow::BorrowIndex; use crate::diagnostics::{RegionErrorKind, RegionErrors, UniverseInfo}; use crate::handle_placeholders::{LoweredConstraints, RegionTracker}; -use crate::member_constraints::{MemberConstraintSet, NllMemberConstraintIndex}; use crate::polonius::LiveLoans; use crate::polonius::legacy::PoloniusOutput; -use crate::region_infer::reverse_sccs::ReverseSccGraph; use crate::region_infer::values::{LivenessValues, RegionElement, RegionValues, ToElementIndex}; use crate::type_check::Locations; use crate::type_check::free_region_relations::UniversalRegionRelations; @@ -78,18 +74,6 @@ impl Representative { } } -impl scc::Annotation for Representative { - fn merge_scc(self, other: Self) -> Self { - // Just pick the smallest one. Note that we order by tag first! - std::cmp::min(self, other) - } - - // For reachability, we do nothing since the representative doesn't change. - fn merge_reached(self, _other: Self) -> Self { - self - } -} - pub(crate) type ConstraintSccs = Sccs<RegionVid, ConstraintSccIndex>; pub struct RegionInferenceContext<'tcx> { @@ -120,20 +104,6 @@ pub struct RegionInferenceContext<'tcx> { scc_annotations: IndexVec<ConstraintSccIndex, RegionTracker>, - /// Reverse of the SCC constraint graph -- i.e., an edge `A -> B` exists if - /// `B: A`. This is used to compute the universal regions that are required - /// to outlive a given SCC. - rev_scc_graph: OnceCell<ReverseSccGraph>, - - /// The "R0 member of [R1..Rn]" constraints, indexed by SCC. - member_constraints: Rc<MemberConstraintSet<'tcx, ConstraintSccIndex>>, - - /// Records the member constraints that we applied to each scc. - /// This is useful for error reporting. Once constraint - /// propagation is done, this vector is sorted according to - /// `member_region_scc`. - member_constraints_applied: Vec<AppliedMemberConstraint>, - /// Map universe indexes to information on why we created it. universe_causes: FxIndexMap<ty::UniverseIndex, UniverseInfo<'tcx>>, @@ -150,32 +120,6 @@ pub struct RegionInferenceContext<'tcx> { universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>, } -/// Each time that `apply_member_constraint` is successful, it appends -/// one of these structs to the `member_constraints_applied` field. -/// This is used in error reporting to trace out what happened. -/// -/// The way that `apply_member_constraint` works is that it effectively -/// adds a new lower bound to the SCC it is analyzing: so you wind up -/// with `'R: 'O` where `'R` is the pick-region and `'O` is the -/// minimal viable option. -#[derive(Debug)] -pub(crate) struct AppliedMemberConstraint { - /// The SCC that was affected. (The "member region".) - /// - /// The vector if `AppliedMemberConstraint` elements is kept sorted - /// by this field. - pub(crate) member_region_scc: ConstraintSccIndex, - - /// The "best option" that `apply_member_constraint` found -- this was - /// added as an "ad-hoc" lower-bound to `member_region_scc`. - pub(crate) min_choice: ty::RegionVid, - - /// The "member constraint index" -- we can find out details about - /// the constraint from - /// `set.member_constraints[member_constraint_index]`. - pub(crate) member_constraint_index: NllMemberConstraintIndex, -} - #[derive(Debug)] pub(crate) struct RegionDefinition<'tcx> { /// What kind of variable is this -- a free region? existential @@ -268,7 +212,6 @@ enum Trace<'a, 'tcx> { StartRegion, FromGraph(&'a OutlivesConstraint<'tcx>), FromStatic(RegionVid), - FromMember(RegionVid, RegionVid, Span), NotVisited, } @@ -363,7 +306,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { liveness_constraints, universe_causes, placeholder_indices, - member_constraints, } = lowered_constraints; debug!("universal_regions: {:#?}", universal_region_relations.universal_regions); @@ -385,9 +327,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { scc_values.merge_liveness(scc, region, &liveness_constraints); } - let member_constraints = - Rc::new(member_constraints.into_mapped(|r| constraint_sccs.scc(r))); - let mut result = Self { definitions, liveness_constraints, @@ -395,9 +334,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { constraint_graph, constraint_sccs, scc_annotations, - rev_scc_graph: OnceCell::new(), - member_constraints, - member_constraints_applied: Vec::new(), universe_causes, scc_values, type_tests, @@ -550,19 +486,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { self.scc_values.placeholders_contained_in(scc) } - /// Once region solving has completed, this function will return the member constraints that - /// were applied to the value of a given SCC `scc`. See `AppliedMemberConstraint`. - pub(crate) fn applied_member_constraints( - &self, - scc: ConstraintSccIndex, - ) -> &[AppliedMemberConstraint] { - binary_search_util::binary_search_slice( - &self.member_constraints_applied, - |applied| applied.member_region_scc, - &scc, - ) - } - /// Performs region inference and report errors if we see any /// unsatisfiable constraints. If this is a closure, returns the /// region requirements to propagate to our creator, if any. @@ -607,12 +530,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { debug!(?errors_buffer); - if errors_buffer.is_empty() { - self.check_member_constraints(infcx, &mut errors_buffer); - } - - debug!(?errors_buffer); - let outlives_requirements = outlives_requirements.unwrap_or_default(); if outlives_requirements.is_empty() { @@ -642,146 +559,15 @@ impl<'tcx> RegionInferenceContext<'tcx> { }); // To propagate constraints, we walk the DAG induced by the - // SCC. For each SCC, we visit its successors and compute + // SCC. For each SCC `A`, we visit its successors and compute // their values, then we union all those values to get our // own. - for scc in self.constraint_sccs.all_sccs() { - self.compute_value_for_scc(scc); - } - - // Sort the applied member constraints so we can binary search - // through them later. - self.member_constraints_applied.sort_by_key(|applied| applied.member_region_scc); - } - - /// Computes the value of the SCC `scc_a`, which has not yet been - /// computed, by unioning the values of its successors. - /// Assumes that all successors have been computed already - /// (which is assured by iterating over SCCs in dependency order). - #[instrument(skip(self), level = "debug")] - fn compute_value_for_scc(&mut self, scc_a: ConstraintSccIndex) { - // Walk each SCC `B` such that `A: B`... - for &scc_b in self.constraint_sccs.successors(scc_a) { - debug!(?scc_b); - self.scc_values.add_region(scc_a, scc_b); - } - - // Now take member constraints into account. - let member_constraints = Rc::clone(&self.member_constraints); - for m_c_i in member_constraints.indices(scc_a) { - self.apply_member_constraint(scc_a, m_c_i, member_constraints.choice_regions(m_c_i)); - } - - debug!(value = ?self.scc_values.region_value_str(scc_a)); - } - - /// Invoked for each `R0 member of [R1..Rn]` constraint. - /// - /// `scc` is the SCC containing R0, and `choice_regions` are the - /// `R1..Rn` regions -- they are always known to be universal - /// regions (and if that's not true, we just don't attempt to - /// enforce the constraint). - /// - /// The current value of `scc` at the time the method is invoked - /// is considered a *lower bound*. If possible, we will modify - /// the constraint to set it equal to one of the option regions. - /// If we make any changes, returns true, else false. - /// - /// This function only adds the member constraints to the region graph, - /// it does not check them. They are later checked in - /// `check_member_constraints` after the region graph has been computed. - #[instrument(skip(self, member_constraint_index), level = "debug")] - fn apply_member_constraint( - &mut self, - scc: ConstraintSccIndex, - member_constraint_index: NllMemberConstraintIndex, - choice_regions: &[ty::RegionVid], - ) { - // Create a mutable vector of the options. We'll try to winnow - // them down. - let mut choice_regions: Vec<ty::RegionVid> = choice_regions.to_vec(); - - // Convert to the SCC representative: sometimes we have inference - // variables in the member constraint that wind up equated with - // universal regions. The scc representative is the minimal numbered - // one from the corresponding scc so it will be the universal region - // if one exists. - for c_r in &mut choice_regions { - let scc = self.constraint_sccs.scc(*c_r); - *c_r = self.scc_representative(scc); - } - - // If the member region lives in a higher universe, we currently choose - // the most conservative option by leaving it unchanged. - if !self.max_nameable_universe(scc).is_root() { - return; - } - - // The existing value for `scc` is a lower-bound. This will - // consist of some set `{P} + {LB}` of points `{P}` and - // lower-bound free regions `{LB}`. As each choice region `O` - // is a free region, it will outlive the points. But we can - // only consider the option `O` if `O: LB`. - choice_regions.retain(|&o_r| { - self.scc_values - .universal_regions_outlived_by(scc) - .all(|lb| self.universal_region_relations.outlives(o_r, lb)) - }); - debug!(?choice_regions, "after lb"); - - // Now find all the *upper bounds* -- that is, each UB is a - // free region that must outlive the member region `R0` (`UB: - // R0`). Therefore, we need only keep an option `O` if `UB: O` - // for all UB. - let universal_region_relations = &self.universal_region_relations; - for ub in self.reverse_scc_graph().upper_bounds(scc) { - debug!(?ub); - choice_regions.retain(|&o_r| universal_region_relations.outlives(ub, o_r)); - } - debug!(?choice_regions, "after ub"); - - // At this point we can pick any member of `choice_regions` and would like to choose - // it to be a small as possible. To avoid potential non-determinism we will pick the - // smallest such choice. - // - // Because universal regions are only partially ordered (i.e, not every two regions are - // comparable), we will ignore any region that doesn't compare to all others when picking - // the minimum choice. - // - // For example, consider `choice_regions = ['static, 'a, 'b, 'c, 'd, 'e]`, where - // `'static: 'a, 'static: 'b, 'a: 'c, 'b: 'c, 'c: 'd, 'c: 'e`. - // `['d, 'e]` are ignored because they do not compare - the same goes for `['a, 'b]`. - let totally_ordered_subset = choice_regions.iter().copied().filter(|&r1| { - choice_regions.iter().all(|&r2| { - self.universal_region_relations.outlives(r1, r2) - || self.universal_region_relations.outlives(r2, r1) - }) - }); - // Now we're left with `['static, 'c]`. Pick `'c` as the minimum! - let Some(min_choice) = totally_ordered_subset.reduce(|r1, r2| { - let r1_outlives_r2 = self.universal_region_relations.outlives(r1, r2); - let r2_outlives_r1 = self.universal_region_relations.outlives(r2, r1); - match (r1_outlives_r2, r2_outlives_r1) { - (true, true) => r1.min(r2), - (true, false) => r2, - (false, true) => r1, - (false, false) => bug!("incomparable regions in total order"), + for scc_a in self.constraint_sccs.all_sccs() { + // Walk each SCC `B` such that `A: B`... + for &scc_b in self.constraint_sccs.successors(scc_a) { + debug!(?scc_b); + self.scc_values.add_region(scc_a, scc_b); } - }) else { - debug!("no unique minimum choice"); - return; - }; - - // As we require `'scc: 'min_choice`, we have definitely already computed - // its `scc_values` at this point. - let min_choice_scc = self.constraint_sccs.scc(min_choice); - debug!(?min_choice, ?min_choice_scc); - if self.scc_values.add_region(scc, min_choice_scc) { - self.member_constraints_applied.push(AppliedMemberConstraint { - member_region_scc: scc, - min_choice, - member_constraint_index, - }); } } @@ -1487,11 +1273,9 @@ impl<'tcx> RegionInferenceContext<'tcx> { { debug!("try_propagate_universal_region_error: fr_minus={:?}", fr_minus); - let blame_span_category = self.find_outlives_blame_span( - longer_fr, - NllRegionVariableOrigin::FreeRegion, - shorter_fr, - ); + let blame_constraint = self + .best_blame_constraint(longer_fr, NllRegionVariableOrigin::FreeRegion, shorter_fr) + .0; // Grow `shorter_fr` until we find some non-local regions. (We // always will.) We'll call them `shorter_fr+` -- they're ever @@ -1504,8 +1288,8 @@ impl<'tcx> RegionInferenceContext<'tcx> { propagated_outlives_requirements.push(ClosureOutlivesRequirement { subject: ClosureOutlivesSubject::Region(fr_minus), outlived_free_region: fr, - blame_span: blame_span_category.1.span, - category: blame_span_category.0, + blame_span: blame_constraint.cause.span, + category: blame_constraint.category, }); } return RegionRelationCheckResult::Propagated; @@ -1544,118 +1328,67 @@ impl<'tcx> RegionInferenceContext<'tcx> { } } - #[instrument(level = "debug", skip(self, infcx, errors_buffer))] - fn check_member_constraints( - &self, - infcx: &InferCtxt<'tcx>, - errors_buffer: &mut RegionErrors<'tcx>, - ) { - let member_constraints = Rc::clone(&self.member_constraints); - for m_c_i in member_constraints.all_indices() { - debug!(?m_c_i); - let m_c = &member_constraints[m_c_i]; - let member_region_vid = m_c.member_region_vid; - debug!( - ?member_region_vid, - value = ?self.region_value_str(member_region_vid), - ); - let choice_regions = member_constraints.choice_regions(m_c_i); - debug!(?choice_regions); - - // Did the member region wind up equal to any of the option regions? - if let Some(o) = - choice_regions.iter().find(|&&o_r| self.eval_equal(o_r, m_c.member_region_vid)) - { - debug!("evaluated as equal to {:?}", o); - continue; - } - - // If not, report an error. - let member_region = ty::Region::new_var(infcx.tcx, member_region_vid); - errors_buffer.push(RegionErrorKind::UnexpectedHiddenRegion { - span: m_c.definition_span, - hidden_ty: m_c.hidden_ty, - key: m_c.key, - member_region, - }); - } - } - - /// We have a constraint `fr1: fr2` that is not satisfied, where - /// `fr2` represents some universal region. Here, `r` is some - /// region where we know that `fr1: r` and this function has the - /// job of determining whether `r` is "to blame" for the fact that - /// `fr1: fr2` is required. - /// - /// This is true under two conditions: - /// - /// - `r == fr2` - /// - `fr2` is `'static` and `r` is some placeholder in a universe - /// that cannot be named by `fr1`; in that case, we will require - /// that `fr1: 'static` because it is the only way to `fr1: r` to - /// be satisfied. (See `add_incompatible_universe`.) - pub(crate) fn provides_universal_region( + pub(crate) fn constraint_path_between_regions( &self, - r: RegionVid, - fr1: RegionVid, - fr2: RegionVid, - ) -> bool { - debug!("provides_universal_region(r={:?}, fr1={:?}, fr2={:?})", r, fr1, fr2); - let result = { - r == fr2 || { - fr2 == self.universal_regions().fr_static && self.cannot_name_placeholder(fr1, r) - } - }; - debug!("provides_universal_region: result = {:?}", result); - result - } - - /// If `r2` represents a placeholder region, then this returns - /// `true` if `r1` cannot name that placeholder in its - /// value; otherwise, returns `false`. - pub(crate) fn cannot_name_placeholder(&self, r1: RegionVid, r2: RegionVid) -> bool { - match self.definitions[r2].origin { - NllRegionVariableOrigin::Placeholder(placeholder) => { - let r1_universe = self.definitions[r1].universe; - debug!( - "cannot_name_value_of: universe1={r1_universe:?} placeholder={:?}", - placeholder - ); - r1_universe.cannot_name(placeholder.universe) - } - - NllRegionVariableOrigin::FreeRegion | NllRegionVariableOrigin::Existential { .. } => { - false - } + from_region: RegionVid, + to_region: RegionVid, + ) -> Option<Vec<OutlivesConstraint<'tcx>>> { + if from_region == to_region { + bug!("Tried to find a path between {from_region:?} and itself!"); } - } - - /// Finds a good `ObligationCause` to blame for the fact that `fr1` outlives `fr2`. - pub(crate) fn find_outlives_blame_span( - &self, - fr1: RegionVid, - fr1_origin: NllRegionVariableOrigin, - fr2: RegionVid, - ) -> (ConstraintCategory<'tcx>, ObligationCause<'tcx>) { - let BlameConstraint { category, cause, .. } = self - .best_blame_constraint(fr1, fr1_origin, |r| self.provides_universal_region(r, fr1, fr2)) - .0; - (category, cause) + self.constraint_path_to(from_region, |to| to == to_region, true).map(|o| o.0) } /// Walks the graph of constraints (where `'a: 'b` is considered - /// an edge `'a -> 'b`) to find all paths from `from_region` to - /// `to_region`. The paths are accumulated into the vector - /// `results`. The paths are stored as a series of - /// `ConstraintIndex` values -- in other words, a list of *edges*. + /// an edge `'a -> 'b`) to find a path from `from_region` to + /// `to_region`. /// /// Returns: a series of constraints as well as the region `R` /// that passed the target test. + /// If `include_static_outlives_all` is `true`, then the synthetic + /// outlives constraints `'static -> a` for every region `a` are + /// considered in the search, otherwise they are ignored. #[instrument(skip(self, target_test), ret)] - pub(crate) fn find_constraint_paths_between_regions( + pub(crate) fn constraint_path_to( + &self, + from_region: RegionVid, + target_test: impl Fn(RegionVid) -> bool, + include_placeholder_static: bool, + ) -> Option<(Vec<OutlivesConstraint<'tcx>>, RegionVid)> { + self.find_constraint_path_between_regions_inner( + true, + from_region, + &target_test, + include_placeholder_static, + ) + .or_else(|| { + self.find_constraint_path_between_regions_inner( + false, + from_region, + &target_test, + include_placeholder_static, + ) + }) + } + + /// The constraints we get from equating the hidden type of each use of an opaque + /// with its final concrete type may end up getting preferred over other, potentially + /// longer constraint paths. + /// + /// Given that we compute the final concrete type by relying on this existing constraint + /// path, this can easily end up hiding the actual reason for why we require these regions + /// to be equal. + /// + /// To handle this, we first look at the path while ignoring these constraints and then + /// retry while considering them. This is not perfect, as the `from_region` may have already + /// been partially related to its argument region, so while we rely on a member constraint + /// to get a complete path, the most relevant step of that path already existed before then. + fn find_constraint_path_between_regions_inner( &self, + ignore_opaque_type_constraints: bool, from_region: RegionVid, target_test: impl Fn(RegionVid) -> bool, + include_placeholder_static: bool, ) -> Option<(Vec<OutlivesConstraint<'tcx>>, RegionVid)> { let mut context = IndexVec::from_elem(Trace::NotVisited, &self.definitions); context[from_region] = Trace::StartRegion; @@ -1670,7 +1403,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { while let Some(r) = deque.pop_front() { debug!( - "find_constraint_paths_between_regions: from_region={:?} r={:?} value={}", + "constraint_path_to: from_region={:?} r={:?} value={}", from_region, r, self.region_value_str(r), @@ -1704,20 +1437,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { result.push(c); } - Trace::FromMember(sup, sub, span) => { - let c = OutlivesConstraint { - sup, - sub, - locations: Locations::All(span), - span, - category: ConstraintCategory::OpaqueType, - variance_info: ty::VarianceDiagInfo::default(), - from_closure: false, - }; - p = c.sup; - result.push(c); - } - Trace::StartRegion => { result.reverse(); return Some((result, r)); @@ -1756,23 +1475,24 @@ impl<'tcx> RegionInferenceContext<'tcx> { let edges = self.constraint_graph.outgoing_edges_from_graph(r, &self.constraints); // This loop can be hot. for constraint in edges { - if matches!(constraint.category, ConstraintCategory::IllegalUniverse) { - debug!("Ignoring illegal universe constraint: {constraint:?}"); - continue; + match constraint.category { + ConstraintCategory::OutlivesUnnameablePlaceholder(_) + if !include_placeholder_static => + { + debug!("Ignoring illegal placeholder constraint: {constraint:?}"); + continue; + } + ConstraintCategory::OpaqueType if ignore_opaque_type_constraints => { + debug!("Ignoring member constraint: {constraint:?}"); + continue; + } + _ => {} } + debug_assert_eq!(constraint.sup, r); handle_trace(constraint.sub, Trace::FromGraph(constraint)); } } - - // Member constraints can also give rise to `'r: 'x` edges that - // were not part of the graph initially, so watch out for those. - // (But they are extremely rare; this loop is very cold.) - for constraint in self.applied_member_constraints(self.constraint_sccs.scc(r)) { - let sub = constraint.min_choice; - let p_c = &self.member_constraints[constraint.member_constraint_index]; - handle_trace(sub, Trace::FromMember(r, sub, p_c.definition_span)); - } } None @@ -1783,37 +1503,10 @@ impl<'tcx> RegionInferenceContext<'tcx> { pub(crate) fn find_sub_region_live_at(&self, fr1: RegionVid, location: Location) -> RegionVid { trace!(scc = ?self.constraint_sccs.scc(fr1)); trace!(universe = ?self.max_nameable_universe(self.constraint_sccs.scc(fr1))); - self.find_constraint_paths_between_regions(fr1, |r| { - // First look for some `r` such that `fr1: r` and `r` is live at `location` + self.constraint_path_to(fr1, |r| { trace!(?r, liveness_constraints=?self.liveness_constraints.pretty_print_live_points(r)); self.liveness_constraints.is_live_at(r, location) - }) - .or_else(|| { - // If we fail to find that, we may find some `r` such that - // `fr1: r` and `r` is a placeholder from some universe - // `fr1` cannot name. This would force `fr1` to be - // `'static`. - self.find_constraint_paths_between_regions(fr1, |r| { - self.cannot_name_placeholder(fr1, r) - }) - }) - .or_else(|| { - // If we fail to find THAT, it may be that `fr1` is a - // placeholder that cannot "fit" into its SCC. In that - // case, there should be some `r` where `fr1: r` and `fr1` is a - // placeholder that `r` cannot name. We can blame that - // edge. - // - // Remember that if `R1: R2`, then the universe of R1 - // must be able to name the universe of R2, because R2 will - // be at least `'empty(Universe(R2))`, and `R1` must be at - // larger than that. - self.find_constraint_paths_between_regions(fr1, |r| { - self.cannot_name_placeholder(r, fr1) - }) - }) - .map(|(_path, r)| r) - .unwrap() + }, true).unwrap().1 } /// Get the region outlived by `longer_fr` and live at `element`. @@ -1857,22 +1550,38 @@ impl<'tcx> RegionInferenceContext<'tcx> { /// creating a constraint path that forces `R` to outlive /// `from_region`, and then finding the best choices within that /// path to blame. - #[instrument(level = "debug", skip(self, target_test))] + #[instrument(level = "debug", skip(self))] pub(crate) fn best_blame_constraint( &self, from_region: RegionVid, from_region_origin: NllRegionVariableOrigin, - target_test: impl Fn(RegionVid) -> bool, + to_region: RegionVid, ) -> (BlameConstraint<'tcx>, Vec<OutlivesConstraint<'tcx>>) { - // Find all paths - let (path, target_region) = self - .find_constraint_paths_between_regions(from_region, target_test) - .or_else(|| { - self.find_constraint_paths_between_regions(from_region, |r| { - self.cannot_name_placeholder(from_region, r) - }) - }) - .unwrap(); + assert!(from_region != to_region, "Trying to blame a region for itself!"); + + let path = self.constraint_path_between_regions(from_region, to_region).unwrap(); + + // If we are passing through a constraint added because we reached an unnameable placeholder `'unnameable`, + // redirect search towards `'unnameable`. + let due_to_placeholder_outlives = path.iter().find_map(|c| { + if let ConstraintCategory::OutlivesUnnameablePlaceholder(unnameable) = c.category { + Some(unnameable) + } else { + None + } + }); + + // Edge case: it's possible that `'from_region` is an unnameable placeholder. + let path = if let Some(unnameable) = due_to_placeholder_outlives + && unnameable != from_region + { + // We ignore the extra edges due to unnameable placeholders to get + // an explanation that was present in the original constraint graph. + self.constraint_path_to(from_region, |r| r == unnameable, false).unwrap().0 + } else { + path + }; + debug!( "path={:#?}", path.iter() @@ -1980,7 +1689,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { ConstraintCategory::Cast { unsize_to: Some(unsize_ty), is_implicit_coercion: true, - } if target_region == self.universal_regions().fr_static + } if to_region == self.universal_regions().fr_static // Mirror the note's condition, to minimize how often this diverts blame. && let ty::Adt(_, args) = unsize_ty.kind() && args.iter().any(|arg| arg.as_type().is_some_and(|ty| ty.is_trait())) @@ -2018,7 +1727,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { // specific, and are not used for relations that would make sense to blame. ConstraintCategory::BoringNoLocation => 6, // Do not blame internal constraints. - ConstraintCategory::IllegalUniverse => 7, + ConstraintCategory::OutlivesUnnameablePlaceholder(_) => 7, ConstraintCategory::Internal => 8, }; @@ -2055,6 +1764,14 @@ impl<'tcx> RegionInferenceContext<'tcx> { path[best_choice] }; + assert!( + !matches!( + best_constraint.category, + ConstraintCategory::OutlivesUnnameablePlaceholder(_) + ), + "Illegal placeholder constraint blamed; should have redirected to other region relation" + ); + let blame_constraint = BlameConstraint { category: best_constraint.category, from_closure: best_constraint.from_closure, @@ -2104,11 +1821,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { &self.constraint_sccs } - /// Access to the region graph, built from the outlives constraints. - pub(crate) fn region_graph(&self) -> RegionGraph<'_, 'tcx, graph::Normal> { - self.constraint_graph.region_graph(&self.constraints, self.universal_regions().fr_static) - } - /// Returns the representative `RegionVid` for a given SCC. /// See `RegionTracker` for how a region variable ID is chosen. /// diff --git a/compiler/rustc_borrowck/src/region_infer/opaque_types.rs b/compiler/rustc_borrowck/src/region_infer/opaque_types.rs deleted file mode 100644 index 23c4554aa15..00000000000 --- a/compiler/rustc_borrowck/src/region_infer/opaque_types.rs +++ /dev/null @@ -1,299 +0,0 @@ -use rustc_data_structures::fx::FxIndexMap; -use rustc_infer::infer::{InferCtxt, NllRegionVariableOrigin}; -use rustc_macros::extension; -use rustc_middle::ty::{ - self, DefiningScopeKind, OpaqueHiddenType, OpaqueTypeKey, Ty, TyCtxt, TypeFoldable, - TypeVisitableExt, fold_regions, -}; -use rustc_span::Span; -use rustc_trait_selection::opaque_types::{ - InvalidOpaqueTypeArgs, check_opaque_type_parameter_valid, -}; -use tracing::{debug, instrument}; - -use super::RegionInferenceContext; -use crate::BorrowCheckRootCtxt; -use crate::session_diagnostics::LifetimeMismatchOpaqueParam; -use crate::universal_regions::RegionClassification; - -pub(crate) enum DeferredOpaqueTypeError<'tcx> { - InvalidOpaqueTypeArgs(InvalidOpaqueTypeArgs<'tcx>), - LifetimeMismatchOpaqueParam(LifetimeMismatchOpaqueParam<'tcx>), -} - -impl<'tcx> RegionInferenceContext<'tcx> { - /// Resolve any opaque types that were encountered while borrow checking - /// this item. This is then used to get the type in the `type_of` query. - /// - /// For example consider `fn f<'a>(x: &'a i32) -> impl Sized + 'a { x }`. - /// This is lowered to give HIR something like - /// - /// type f<'a>::_Return<'_x> = impl Sized + '_x; - /// fn f<'a>(x: &'a i32) -> f<'a>::_Return<'a> { x } - /// - /// When checking the return type record the type from the return and the - /// type used in the return value. In this case they might be `_Return<'1>` - /// and `&'2 i32` respectively. - /// - /// Once we to this method, we have completed region inference and want to - /// call `infer_opaque_definition_from_instantiation` to get the inferred - /// type of `_Return<'_x>`. `infer_opaque_definition_from_instantiation` - /// compares lifetimes directly, so we need to map the inference variables - /// back to concrete lifetimes: `'static`, `ReEarlyParam` or `ReLateParam`. - /// - /// First we map the regions in the generic parameters `_Return<'1>` to - /// their `external_name` giving `_Return<'a>`. This step is a bit involved. - /// See the [rustc-dev-guide chapter] for more info. - /// - /// Then we map all the lifetimes in the concrete type to an equal - /// universal region that occurs in the opaque type's args, in this case - /// this would result in `&'a i32`. We only consider regions in the args - /// in case there is an equal region that does not. For example, this should - /// be allowed: - /// `fn f<'a: 'b, 'b: 'a>(x: *mut &'b i32) -> impl Sized + 'a { x }` - /// - /// This will then allow `infer_opaque_definition_from_instantiation` to - /// determine that `_Return<'_x> = &'_x i32`. - /// - /// There's a slight complication around closures. Given - /// `fn f<'a: 'a>() { || {} }` the closure's type is something like - /// `f::<'a>::{{closure}}`. The region parameter from f is essentially - /// ignored by type checking so ends up being inferred to an empty region. - /// Calling `universal_upper_bound` for such a region gives `fr_fn_body`, - /// which has no `external_name` in which case we use `'{erased}` as the - /// region to pass to `infer_opaque_definition_from_instantiation`. - /// - /// [rustc-dev-guide chapter]: - /// https://rustc-dev-guide.rust-lang.org/opaque-types-region-infer-restrictions.html - #[instrument(level = "debug", skip(self, root_cx, infcx))] - pub(crate) fn infer_opaque_types( - &self, - root_cx: &mut BorrowCheckRootCtxt<'tcx>, - infcx: &InferCtxt<'tcx>, - opaque_ty_decls: FxIndexMap<OpaqueTypeKey<'tcx>, OpaqueHiddenType<'tcx>>, - ) -> Vec<DeferredOpaqueTypeError<'tcx>> { - let mut errors = Vec::new(); - let mut decls_modulo_regions: FxIndexMap<OpaqueTypeKey<'tcx>, (OpaqueTypeKey<'tcx>, Span)> = - FxIndexMap::default(); - - for (opaque_type_key, concrete_type) in opaque_ty_decls { - debug!(?opaque_type_key, ?concrete_type); - - let mut arg_regions: Vec<(ty::RegionVid, ty::Region<'_>)> = - vec![(self.universal_regions().fr_static, infcx.tcx.lifetimes.re_static)]; - - let opaque_type_key = - opaque_type_key.fold_captured_lifetime_args(infcx.tcx, |region| { - // Use the SCC representative instead of directly using `region`. - // See [rustc-dev-guide chapter] § "Strict lifetime equality". - let scc = self.constraint_sccs.scc(region.as_var()); - let vid = self.scc_representative(scc); - let named = match self.definitions[vid].origin { - // Iterate over all universal regions in a consistent order and find the - // *first* equal region. This makes sure that equal lifetimes will have - // the same name and simplifies subsequent handling. - // See [rustc-dev-guide chapter] § "Semantic lifetime equality". - NllRegionVariableOrigin::FreeRegion => self - .universal_regions() - .universal_regions_iter() - .filter(|&ur| { - // See [rustc-dev-guide chapter] § "Closure restrictions". - !matches!( - self.universal_regions().region_classification(ur), - Some(RegionClassification::External) - ) - }) - .find(|&ur| self.universal_region_relations.equal(vid, ur)) - .map(|ur| self.definitions[ur].external_name.unwrap()), - NllRegionVariableOrigin::Placeholder(placeholder) => { - Some(ty::Region::new_placeholder(infcx.tcx, placeholder)) - } - NllRegionVariableOrigin::Existential { .. } => None, - } - .unwrap_or_else(|| { - ty::Region::new_error_with_message( - infcx.tcx, - concrete_type.span, - "opaque type with non-universal region args", - ) - }); - - arg_regions.push((vid, named)); - named - }); - debug!(?opaque_type_key, ?arg_regions); - - let concrete_type = fold_regions(infcx.tcx, concrete_type, |region, _| { - arg_regions - .iter() - .find(|&&(arg_vid, _)| self.eval_equal(region.as_var(), arg_vid)) - .map(|&(_, arg_named)| arg_named) - .unwrap_or(infcx.tcx.lifetimes.re_erased) - }); - debug!(?concrete_type); - - let ty = match infcx - .infer_opaque_definition_from_instantiation(opaque_type_key, concrete_type) - { - Ok(ty) => ty, - Err(err) => { - errors.push(DeferredOpaqueTypeError::InvalidOpaqueTypeArgs(err)); - continue; - } - }; - - // Sometimes, when the hidden type is an inference variable, it can happen that - // the hidden type becomes the opaque type itself. In this case, this was an opaque - // usage of the opaque type and we can ignore it. This check is mirrored in typeck's - // writeback. - if !infcx.next_trait_solver() { - if let ty::Alias(ty::Opaque, alias_ty) = ty.kind() - && alias_ty.def_id == opaque_type_key.def_id.to_def_id() - && alias_ty.args == opaque_type_key.args - { - continue; - } - } - - root_cx.add_concrete_opaque_type( - opaque_type_key.def_id, - OpaqueHiddenType { span: concrete_type.span, ty }, - ); - - // Check that all opaque types have the same region parameters if they have the same - // non-region parameters. This is necessary because within the new solver we perform - // various query operations modulo regions, and thus could unsoundly select some impls - // that don't hold. - if let Some((prev_decl_key, prev_span)) = decls_modulo_regions.insert( - infcx.tcx.erase_regions(opaque_type_key), - (opaque_type_key, concrete_type.span), - ) && let Some((arg1, arg2)) = std::iter::zip( - prev_decl_key.iter_captured_args(infcx.tcx).map(|(_, arg)| arg), - opaque_type_key.iter_captured_args(infcx.tcx).map(|(_, arg)| arg), - ) - .find(|(arg1, arg2)| arg1 != arg2) - { - errors.push(DeferredOpaqueTypeError::LifetimeMismatchOpaqueParam( - LifetimeMismatchOpaqueParam { - arg: arg1, - prev: arg2, - span: prev_span, - prev_span: concrete_type.span, - }, - )); - } - } - - errors - } - - /// Map the regions in the type to named regions. This is similar to what - /// `infer_opaque_types` does, but can infer any universal region, not only - /// ones from the args for the opaque type. It also doesn't double check - /// that the regions produced are in fact equal to the named region they are - /// replaced with. This is fine because this function is only to improve the - /// region names in error messages. - /// - /// This differs from `MirBorrowckCtxt::name_regions` since it is particularly - /// lax with mapping region vids that are *shorter* than a universal region to - /// that universal region. This is useful for member region constraints since - /// we want to suggest a universal region name to capture even if it's technically - /// not equal to the error region. - pub(crate) fn name_regions_for_member_constraint<T>(&self, tcx: TyCtxt<'tcx>, ty: T) -> T - where - T: TypeFoldable<TyCtxt<'tcx>>, - { - fold_regions(tcx, ty, |region, _| match region.kind() { - ty::ReVar(vid) => { - let scc = self.constraint_sccs.scc(vid); - - // Special handling of higher-ranked regions. - if !self.max_nameable_universe(scc).is_root() { - match self.scc_values.placeholders_contained_in(scc).enumerate().last() { - // If the region contains a single placeholder then they're equal. - Some((0, placeholder)) => { - return ty::Region::new_placeholder(tcx, placeholder); - } - - // Fallback: this will produce a cryptic error message. - _ => return region, - } - } - - // Find something that we can name - let upper_bound = self.approx_universal_upper_bound(vid); - if let Some(universal_region) = self.definitions[upper_bound].external_name { - return universal_region; - } - - // Nothing exact found, so we pick a named upper bound, if there's only one. - // If there's >1 universal region, then we probably are dealing w/ an intersection - // region which cannot be mapped back to a universal. - // FIXME: We could probably compute the LUB if there is one. - let scc = self.constraint_sccs.scc(vid); - let upper_bounds: Vec<_> = self - .reverse_scc_graph() - .upper_bounds(scc) - .filter_map(|vid| self.definitions[vid].external_name) - .filter(|r| !r.is_static()) - .collect(); - match &upper_bounds[..] { - [universal_region] => *universal_region, - _ => region, - } - } - _ => region, - }) - } -} - -#[extension(pub trait InferCtxtExt<'tcx>)] -impl<'tcx> InferCtxt<'tcx> { - /// Given the fully resolved, instantiated type for an opaque - /// type, i.e., the value of an inference variable like C1 or C2 - /// (*), computes the "definition type" for an opaque type - /// definition -- that is, the inferred value of `Foo1<'x>` or - /// `Foo2<'x>` that we would conceptually use in its definition: - /// ```ignore (illustrative) - /// type Foo1<'x> = impl Bar<'x> = AAA; // <-- this type AAA - /// type Foo2<'x> = impl Bar<'x> = BBB; // <-- or this type BBB - /// fn foo<'a, 'b>(..) -> (Foo1<'a>, Foo2<'b>) { .. } - /// ``` - /// Note that these values are defined in terms of a distinct set of - /// generic parameters (`'x` instead of `'a`) from C1 or C2. The main - /// purpose of this function is to do that translation. - /// - /// (*) C1 and C2 were introduced in the comments on - /// `register_member_constraints`. Read that comment for more context. - /// - /// # Parameters - /// - /// - `def_id`, the `impl Trait` type - /// - `args`, the args used to instantiate this opaque type - /// - `instantiated_ty`, the inferred type C1 -- fully resolved, lifted version of - /// `opaque_defn.concrete_ty` - #[instrument(level = "debug", skip(self))] - fn infer_opaque_definition_from_instantiation( - &self, - opaque_type_key: OpaqueTypeKey<'tcx>, - instantiated_ty: OpaqueHiddenType<'tcx>, - ) -> Result<Ty<'tcx>, InvalidOpaqueTypeArgs<'tcx>> { - check_opaque_type_parameter_valid( - self, - opaque_type_key, - instantiated_ty.span, - DefiningScopeKind::MirBorrowck, - )?; - - let definition_ty = instantiated_ty - .remap_generic_params_to_declaration_params( - opaque_type_key, - self.tcx, - DefiningScopeKind::MirBorrowck, - ) - .ty; - - definition_ty.error_reported()?; - Ok(definition_ty) - } -} diff --git a/compiler/rustc_borrowck/src/region_infer/opaque_types/member_constraints.rs b/compiler/rustc_borrowck/src/region_infer/opaque_types/member_constraints.rs new file mode 100644 index 00000000000..667fc440ac0 --- /dev/null +++ b/compiler/rustc_borrowck/src/region_infer/opaque_types/member_constraints.rs @@ -0,0 +1,194 @@ +use rustc_data_structures::fx::FxHashMap; +use rustc_hir::def_id::DefId; +use rustc_middle::bug; +use rustc_middle::ty::{ + self, GenericArgsRef, Region, RegionVid, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, + TypeVisitor, +}; +use tracing::{debug, instrument}; + +use super::DefiningUse; +use super::region_ctxt::RegionCtxt; +use crate::constraints::ConstraintSccIndex; + +pub(super) fn apply_member_constraints<'tcx>( + rcx: &mut RegionCtxt<'_, 'tcx>, + defining_uses: &[DefiningUse<'tcx>], +) { + // Start by collecting the member constraints of all defining uses. + // + // Applying member constraints can influence other member constraints, + // so we first collect and then apply them. + let mut member_constraints = Default::default(); + for defining_use in defining_uses { + let mut visitor = CollectMemberConstraintsVisitor { + rcx, + defining_use, + member_constraints: &mut member_constraints, + }; + defining_use.hidden_type.ty.visit_with(&mut visitor); + } + + // Now walk over the region graph, visiting the smallest regions first and then all + // regions which have to outlive that one. + // + // Whenever we encounter a member region, we mutate the value of this SCC. This is + // as if we'd introduce new outlives constraints. However, we discard these region + // values after we've inferred the hidden types of opaques and apply the region + // constraints by simply equating the actual hidden type with the inferred one. + debug!(?member_constraints); + for scc_a in rcx.constraint_sccs.all_sccs() { + debug!(?scc_a); + // Start by adding the region values required by outlives constraints. This + // matches how we compute the final region values in `fn compute_regions`. + // + // We need to do this here to get a lower bound when applying member constraints. + // This propagates the region values added by previous member constraints. + for &scc_b in rcx.constraint_sccs.successors(scc_a) { + debug!(?scc_b); + rcx.scc_values.add_region(scc_a, scc_b); + } + + for defining_use in member_constraints.get(&scc_a).into_iter().flatten() { + apply_member_constraint(rcx, scc_a, &defining_use.arg_regions); + } + } +} + +#[instrument(level = "debug", skip(rcx))] +fn apply_member_constraint<'tcx>( + rcx: &mut RegionCtxt<'_, 'tcx>, + member: ConstraintSccIndex, + arg_regions: &[RegionVid], +) { + // If the member region lives in a higher universe, we currently choose + // the most conservative option by leaving it unchanged. + if !rcx.max_placeholder_universe_reached(member).is_root() { + return; + } + + // The existing value of `'member` is a lower-bound. If its is already larger than + // some universal region, we cannot equate it with that region. Said differently, we + // ignore choice regions which are smaller than this member region. + let mut choice_regions = arg_regions + .iter() + .copied() + .map(|r| rcx.representative(r).rvid()) + .filter(|&choice_region| { + rcx.scc_values.universal_regions_outlived_by(member).all(|lower_bound| { + rcx.universal_region_relations.outlives(choice_region, lower_bound) + }) + }) + .collect::<Vec<_>>(); + debug!(?choice_regions, "after enforcing lower-bound"); + + // Now find all the *upper bounds* -- that is, each UB is a + // free region that must outlive the member region `R0` (`UB: + // R0`). Therefore, we need only keep an option `O` if `UB: O` + // for all UB. + // + // If we have a requirement `'upper_bound: 'member`, equating `'member` + // with some region `'choice` means we now also require `'upper_bound: 'choice`. + // Avoid choice regions for which this does not hold. + for ub in rcx.rev_scc_graph.upper_bounds(member) { + choice_regions + .retain(|&choice_region| rcx.universal_region_relations.outlives(ub, choice_region)); + } + debug!(?choice_regions, "after enforcing upper-bound"); + + // At this point we can pick any member of `choice_regions` and would like to choose + // it to be a small as possible. To avoid potential non-determinism we will pick the + // smallest such choice. + // + // Because universal regions are only partially ordered (i.e, not every two regions are + // comparable), we will ignore any region that doesn't compare to all others when picking + // the minimum choice. + // + // For example, consider `choice_regions = ['static, 'a, 'b, 'c, 'd, 'e]`, where + // `'static: 'a, 'static: 'b, 'a: 'c, 'b: 'c, 'c: 'd, 'c: 'e`. + // `['d, 'e]` are ignored because they do not compare - the same goes for `['a, 'b]`. + let totally_ordered_subset = choice_regions.iter().copied().filter(|&r1| { + choice_regions.iter().all(|&r2| { + rcx.universal_region_relations.outlives(r1, r2) + || rcx.universal_region_relations.outlives(r2, r1) + }) + }); + // Now we're left with `['static, 'c]`. Pick `'c` as the minimum! + let Some(min_choice) = totally_ordered_subset.reduce(|r1, r2| { + let r1_outlives_r2 = rcx.universal_region_relations.outlives(r1, r2); + let r2_outlives_r1 = rcx.universal_region_relations.outlives(r2, r1); + match (r1_outlives_r2, r2_outlives_r1) { + (true, true) => r1.min(r2), + (true, false) => r2, + (false, true) => r1, + (false, false) => bug!("incomparable regions in total order"), + } + }) else { + debug!("no unique minimum choice"); + return; + }; + + debug!(?min_choice); + // Lift the member region to be at least as large as this `min_choice` by directly + // mutating the `scc_values` as we compute it. This acts as if we've added a + // `'member: 'min_choice` while not recomputing sccs. This means different sccs + // may now actually be equal. + let min_choice_scc = rcx.constraint_sccs.scc(min_choice); + rcx.scc_values.add_region(member, min_choice_scc); +} + +struct CollectMemberConstraintsVisitor<'a, 'b, 'tcx> { + rcx: &'a RegionCtxt<'a, 'tcx>, + defining_use: &'b DefiningUse<'tcx>, + member_constraints: &'a mut FxHashMap<ConstraintSccIndex, Vec<&'b DefiningUse<'tcx>>>, +} +impl<'tcx> CollectMemberConstraintsVisitor<'_, '_, 'tcx> { + fn cx(&self) -> TyCtxt<'tcx> { + self.rcx.infcx.tcx + } + fn visit_closure_args(&mut self, def_id: DefId, args: GenericArgsRef<'tcx>) { + let generics = self.cx().generics_of(def_id); + for arg in args.iter().skip(generics.parent_count) { + arg.visit_with(self); + } + } +} +impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for CollectMemberConstraintsVisitor<'_, '_, 'tcx> { + fn visit_region(&mut self, r: Region<'tcx>) { + match r.kind() { + ty::ReBound(..) => return, + ty::ReVar(vid) => { + let scc = self.rcx.constraint_sccs.scc(vid); + self.member_constraints.entry(scc).or_default().push(self.defining_use); + } + _ => unreachable!(), + } + } + + fn visit_ty(&mut self, ty: Ty<'tcx>) { + if !ty.flags().intersects(ty::TypeFlags::HAS_FREE_REGIONS) { + return; + } + + match *ty.kind() { + ty::Closure(def_id, args) + | ty::CoroutineClosure(def_id, args) + | ty::Coroutine(def_id, args) => self.visit_closure_args(def_id, args), + + ty::Alias(kind, ty::AliasTy { def_id, args, .. }) + if let Some(variances) = self.cx().opt_alias_variances(kind, def_id) => + { + // Skip lifetime parameters that are not captured, since they do + // not need member constraints registered for them; we'll erase + // them (and hopefully in the future replace them with placeholders). + for (&v, arg) in std::iter::zip(variances, args.iter()) { + if v != ty::Bivariant { + arg.visit_with(self) + } + } + } + + _ => ty.super_visit_with(self), + } + } +} diff --git a/compiler/rustc_borrowck/src/region_infer/opaque_types/mod.rs b/compiler/rustc_borrowck/src/region_infer/opaque_types/mod.rs new file mode 100644 index 00000000000..bee82e17835 --- /dev/null +++ b/compiler/rustc_borrowck/src/region_infer/opaque_types/mod.rs @@ -0,0 +1,697 @@ +use std::iter; +use std::rc::Rc; + +use rustc_data_structures::frozen::Frozen; +use rustc_data_structures::fx::FxIndexMap; +use rustc_hir::def_id::DefId; +use rustc_infer::infer::outlives::env::RegionBoundPairs; +use rustc_infer::infer::{InferCtxt, NllRegionVariableOrigin, OpaqueTypeStorageEntries}; +use rustc_infer::traits::ObligationCause; +use rustc_macros::extension; +use rustc_middle::mir::{Body, ConstraintCategory}; +use rustc_middle::ty::{ + self, DefiningScopeKind, FallibleTypeFolder, GenericArg, GenericArgsRef, OpaqueHiddenType, + OpaqueTypeKey, Region, RegionVid, Ty, TyCtxt, TypeFoldable, TypeSuperFoldable, + TypeVisitableExt, fold_regions, +}; +use rustc_mir_dataflow::points::DenseLocationMap; +use rustc_span::Span; +use rustc_trait_selection::opaque_types::{ + NonDefiningUseReason, opaque_type_has_defining_use_args, +}; +use rustc_trait_selection::solve::NoSolution; +use rustc_trait_selection::traits::query::type_op::custom::CustomTypeOp; +use tracing::{debug, instrument}; + +use super::reverse_sccs::ReverseSccGraph; +use crate::consumers::RegionInferenceContext; +use crate::session_diagnostics::LifetimeMismatchOpaqueParam; +use crate::type_check::canonical::fully_perform_op_raw; +use crate::type_check::free_region_relations::UniversalRegionRelations; +use crate::type_check::{Locations, MirTypeckRegionConstraints}; +use crate::universal_regions::{RegionClassification, UniversalRegions}; +use crate::{BorrowCheckRootCtxt, BorrowckInferCtxt}; + +mod member_constraints; +mod region_ctxt; + +use member_constraints::apply_member_constraints; +use region_ctxt::RegionCtxt; + +/// We defer errors from [fn handle_opaque_type_uses] and only report them +/// if there are no `RegionErrors`. If there are region errors, it's likely +/// that errors here are caused by them and don't need to be handled separately. +pub(crate) enum DeferredOpaqueTypeError<'tcx> { + InvalidOpaqueTypeArgs(NonDefiningUseReason<'tcx>), + LifetimeMismatchOpaqueParam(LifetimeMismatchOpaqueParam<'tcx>), + UnexpectedHiddenRegion { + /// The opaque type. + opaque_type_key: OpaqueTypeKey<'tcx>, + /// The hidden type containing the member region. + hidden_type: OpaqueHiddenType<'tcx>, + /// The unexpected region. + member_region: Region<'tcx>, + }, + NonDefiningUseInDefiningScope { + span: Span, + opaque_type_key: OpaqueTypeKey<'tcx>, + }, +} + +/// This looks at all uses of opaque types in their defining scope inside +/// of this function. +/// +/// It first uses all defining uses to compute the actual concrete type of each +/// opaque type definition. +/// +/// We then apply this inferred type to actually check all uses of the opaque. +pub(crate) fn handle_opaque_type_uses<'tcx>( + root_cx: &mut BorrowCheckRootCtxt<'tcx>, + infcx: &BorrowckInferCtxt<'tcx>, + body: &Body<'tcx>, + universal_region_relations: &Frozen<UniversalRegionRelations<'tcx>>, + region_bound_pairs: &RegionBoundPairs<'tcx>, + known_type_outlives_obligations: &[ty::PolyTypeOutlivesPredicate<'tcx>], + location_map: &Rc<DenseLocationMap>, + constraints: &mut MirTypeckRegionConstraints<'tcx>, +) -> Vec<DeferredOpaqueTypeError<'tcx>> { + let tcx = infcx.tcx; + let opaque_types = infcx.clone_opaque_types(); + if opaque_types.is_empty() { + return Vec::new(); + } + + // We need to eagerly map all regions to NLL vars here, as we need to make sure we've + // introduced nll vars for all used placeholders. + // + // We need to resolve inference vars as even though we're in MIR typeck, we may still + // encounter inference variables, e.g. when checking user types. + let opaque_types_storage_num_entries = infcx.inner.borrow_mut().opaque_types().num_entries(); + let opaque_types = opaque_types + .into_iter() + .map(|entry| { + fold_regions(tcx, infcx.resolve_vars_if_possible(entry), |r, _| { + let vid = if let ty::RePlaceholder(placeholder) = r.kind() { + constraints.placeholder_region(infcx, placeholder).as_var() + } else { + universal_region_relations.universal_regions.to_region_vid(r) + }; + Region::new_var(tcx, vid) + }) + }) + .collect::<Vec<_>>(); + + debug!(?opaque_types); + + let errors = compute_concrete_opaque_types( + root_cx, + infcx, + constraints, + universal_region_relations, + Rc::clone(location_map), + &opaque_types, + ); + + if !errors.is_empty() { + return errors; + } + + let errors = apply_computed_concrete_opaque_types( + root_cx, + infcx, + body, + &universal_region_relations.universal_regions, + region_bound_pairs, + known_type_outlives_obligations, + constraints, + &opaque_types, + ); + + detect_opaque_types_added_while_handling_opaque_types(infcx, opaque_types_storage_num_entries); + + errors +} + +/// Maps an NLL var to a deterministically chosen equal universal region. +/// +/// See the corresponding [rustc-dev-guide chapter] for more details. This +/// ignores changes to the region values due to member constraints. Applying +/// member constraints does not impact the result of this function. +/// +/// [rustc-dev-guide chapter]: https://rustc-dev-guide.rust-lang.org/borrow_check/opaque-types-region-inference-restrictions.html +fn nll_var_to_universal_region<'tcx>( + rcx: &RegionCtxt<'_, 'tcx>, + r: RegionVid, +) -> Option<Region<'tcx>> { + // Use the SCC representative instead of directly using `region`. + // See [rustc-dev-guide chapter] § "Strict lifetime equality". + let vid = rcx.representative(r).rvid(); + match rcx.definitions[vid].origin { + // Iterate over all universal regions in a consistent order and find the + // *first* equal region. This makes sure that equal lifetimes will have + // the same name and simplifies subsequent handling. + // See [rustc-dev-guide chapter] § "Semantic lifetime equality". + NllRegionVariableOrigin::FreeRegion => rcx + .universal_regions() + .universal_regions_iter() + .filter(|&ur| { + // See [rustc-dev-guide chapter] § "Closure restrictions". + !matches!( + rcx.universal_regions().region_classification(ur), + Some(RegionClassification::External) + ) + }) + .find(|&ur| rcx.universal_region_relations.equal(vid, ur)) + .map(|ur| rcx.definitions[ur].external_name.unwrap()), + NllRegionVariableOrigin::Placeholder(placeholder) => { + Some(ty::Region::new_placeholder(rcx.infcx.tcx, placeholder)) + } + // If `r` were equal to any universal region, its SCC representative + // would have been set to a free region. + NllRegionVariableOrigin::Existential { .. } => None, + } +} + +#[derive(Debug)] +struct DefiningUse<'tcx> { + /// The opaque type using non NLL vars. This uses the actual + /// free regions and placeholders. This is necessary + /// to interact with code outside of `rustc_borrowck`. + opaque_type_key: OpaqueTypeKey<'tcx>, + arg_regions: Vec<RegionVid>, + hidden_type: OpaqueHiddenType<'tcx>, +} + +/// This computes the actual hidden types of the opaque types and maps them to their +/// definition sites. Outside of registering the computed concrete types this function +/// does not mutate the current borrowck state. +/// +/// While it may fail to infer the hidden type and return errors, we always apply +/// the computed concrete hidden type to all opaque type uses to check whether they +/// are correct. This is necessary to support non-defining uses of opaques in their +/// defining scope. +/// +/// It also means that this whole function is not really soundness critical as we +/// recheck all uses of the opaques regardless. +fn compute_concrete_opaque_types<'tcx>( + root_cx: &mut BorrowCheckRootCtxt<'tcx>, + infcx: &BorrowckInferCtxt<'tcx>, + constraints: &MirTypeckRegionConstraints<'tcx>, + universal_region_relations: &Frozen<UniversalRegionRelations<'tcx>>, + location_map: Rc<DenseLocationMap>, + opaque_types: &[(OpaqueTypeKey<'tcx>, OpaqueHiddenType<'tcx>)], +) -> Vec<DeferredOpaqueTypeError<'tcx>> { + let mut errors = Vec::new(); + // When computing the hidden type we need to track member constraints. + // We don't mutate the region graph used by `fn compute_regions` but instead + // manually track region information via a `RegionCtxt`. We discard this + // information at the end of this function. + let mut rcx = RegionCtxt::new(infcx, universal_region_relations, location_map, constraints); + + // We start by checking each use of an opaque type during type check and + // check whether the generic arguments of the opaque type are fully + // universal, if so, it's a defining use. + let defining_uses = collect_defining_uses(root_cx, &mut rcx, opaque_types, &mut errors); + + // We now compute and apply member constraints for all regions in the hidden + // types of each defining use. This mutates the region values of the `rcx` which + // is used when mapping the defining uses to the definition site. + apply_member_constraints(&mut rcx, &defining_uses); + + // After applying member constraints, we now check whether all member regions ended + // up equal to one of their choice regions and compute the actual concrete type of + // the opaque type definition. This is stored in the `root_cx`. + compute_concrete_types_from_defining_uses(root_cx, &rcx, &defining_uses, &mut errors); + errors +} + +#[instrument(level = "debug", skip_all, ret)] +fn collect_defining_uses<'tcx>( + root_cx: &mut BorrowCheckRootCtxt<'tcx>, + rcx: &mut RegionCtxt<'_, 'tcx>, + opaque_types: &[(OpaqueTypeKey<'tcx>, OpaqueHiddenType<'tcx>)], + errors: &mut Vec<DeferredOpaqueTypeError<'tcx>>, +) -> Vec<DefiningUse<'tcx>> { + let infcx = rcx.infcx; + let mut defining_uses = vec![]; + for &(opaque_type_key, hidden_type) in opaque_types { + let non_nll_opaque_type_key = opaque_type_key.fold_captured_lifetime_args(infcx.tcx, |r| { + nll_var_to_universal_region(&rcx, r.as_var()).unwrap_or(r) + }); + if let Err(err) = opaque_type_has_defining_use_args( + infcx, + non_nll_opaque_type_key, + hidden_type.span, + DefiningScopeKind::MirBorrowck, + ) { + // A non-defining use. This is a hard error on stable and gets ignored + // with `TypingMode::Borrowck`. + if infcx.tcx.use_typing_mode_borrowck() { + match err { + NonDefiningUseReason::Tainted(guar) => root_cx.add_concrete_opaque_type( + opaque_type_key.def_id, + OpaqueHiddenType::new_error(infcx.tcx, guar), + ), + _ => debug!(?non_nll_opaque_type_key, ?err, "ignoring non-defining use"), + } + } else { + errors.push(DeferredOpaqueTypeError::InvalidOpaqueTypeArgs(err)); + } + continue; + } + + // We use the original `opaque_type_key` to compute the `arg_regions`. + let arg_regions = iter::once(rcx.universal_regions().fr_static) + .chain( + opaque_type_key + .iter_captured_args(infcx.tcx) + .filter_map(|(_, arg)| arg.as_region()) + .map(Region::as_var), + ) + .collect(); + defining_uses.push(DefiningUse { + opaque_type_key: non_nll_opaque_type_key, + arg_regions, + hidden_type, + }); + } + + defining_uses +} + +fn compute_concrete_types_from_defining_uses<'tcx>( + root_cx: &mut BorrowCheckRootCtxt<'tcx>, + rcx: &RegionCtxt<'_, 'tcx>, + defining_uses: &[DefiningUse<'tcx>], + errors: &mut Vec<DeferredOpaqueTypeError<'tcx>>, +) { + let infcx = rcx.infcx; + let tcx = infcx.tcx; + let mut decls_modulo_regions: FxIndexMap<OpaqueTypeKey<'tcx>, (OpaqueTypeKey<'tcx>, Span)> = + FxIndexMap::default(); + for &DefiningUse { opaque_type_key, ref arg_regions, hidden_type } in defining_uses { + // After applying member constraints, we now map all regions in the hidden type + // to the `arg_regions` of this defining use. In case a region in the hidden type + // ended up not being equal to any such region, we error. + let hidden_type = + match hidden_type.try_fold_with(&mut ToArgRegionsFolder::new(rcx, arg_regions)) { + Ok(hidden_type) => hidden_type, + Err(r) => { + errors.push(DeferredOpaqueTypeError::UnexpectedHiddenRegion { + hidden_type, + opaque_type_key, + member_region: ty::Region::new_var(tcx, r), + }); + let guar = tcx.dcx().span_delayed_bug( + hidden_type.span, + "opaque type with non-universal region args", + ); + ty::OpaqueHiddenType::new_error(tcx, guar) + } + }; + + // Now that we mapped the member regions to their final value, + // map the arguments of the opaque type key back to the parameters + // of the opaque type definition. + let ty = infcx + .infer_opaque_definition_from_instantiation(opaque_type_key, hidden_type) + .unwrap_or_else(|_| { + Ty::new_error_with_message( + rcx.infcx.tcx, + hidden_type.span, + "deferred invalid opaque type args", + ) + }); + + // Sometimes, when the hidden type is an inference variable, it can happen that + // the hidden type becomes the opaque type itself. In this case, this was an opaque + // usage of the opaque type and we can ignore it. This check is mirrored in typeck's + // writeback. + if !rcx.infcx.tcx.use_typing_mode_borrowck() { + if let ty::Alias(ty::Opaque, alias_ty) = ty.kind() + && alias_ty.def_id == opaque_type_key.def_id.to_def_id() + && alias_ty.args == opaque_type_key.args + { + continue; + } + } + + // Check that all opaque types have the same region parameters if they have the same + // non-region parameters. This is necessary because within the new solver we perform + // various query operations modulo regions, and thus could unsoundly select some impls + // that don't hold. + // + // FIXME(-Znext-solver): This isn't necessary after all. We can remove this check again. + if let Some((prev_decl_key, prev_span)) = decls_modulo_regions.insert( + rcx.infcx.tcx.erase_regions(opaque_type_key), + (opaque_type_key, hidden_type.span), + ) && let Some((arg1, arg2)) = std::iter::zip( + prev_decl_key.iter_captured_args(infcx.tcx).map(|(_, arg)| arg), + opaque_type_key.iter_captured_args(infcx.tcx).map(|(_, arg)| arg), + ) + .find(|(arg1, arg2)| arg1 != arg2) + { + errors.push(DeferredOpaqueTypeError::LifetimeMismatchOpaqueParam( + LifetimeMismatchOpaqueParam { + arg: arg1, + prev: arg2, + span: prev_span, + prev_span: hidden_type.span, + }, + )); + } + root_cx.add_concrete_opaque_type( + opaque_type_key.def_id, + OpaqueHiddenType { span: hidden_type.span, ty }, + ); + } +} + +/// A folder to map the regions in the hidden type to their corresponding `arg_regions`. +/// +/// This folder has to differentiate between member regions and other regions in the hidden +/// type. Member regions have to be equal to one of the `arg_regions` while other regions simply +/// get treated as an existential region in the opaque if they are not. Existential +/// regions are currently represented using `'erased`. +struct ToArgRegionsFolder<'a, 'tcx> { + rcx: &'a RegionCtxt<'a, 'tcx>, + // When folding closure args or bivariant alias arguments, we simply + // ignore non-member regions. However, we still need to map member + // regions to their arg region even if its in a closure argument. + // + // See tests/ui/type-alias-impl-trait/closure_wf_outlives.rs for an example. + erase_unknown_regions: bool, + arg_regions: &'a [RegionVid], +} + +impl<'a, 'tcx> ToArgRegionsFolder<'a, 'tcx> { + fn new( + rcx: &'a RegionCtxt<'a, 'tcx>, + arg_regions: &'a [RegionVid], + ) -> ToArgRegionsFolder<'a, 'tcx> { + ToArgRegionsFolder { rcx, erase_unknown_regions: false, arg_regions } + } + + fn fold_non_member_arg(&mut self, arg: GenericArg<'tcx>) -> GenericArg<'tcx> { + let prev = self.erase_unknown_regions; + self.erase_unknown_regions = true; + let res = arg.try_fold_with(self).unwrap(); + self.erase_unknown_regions = prev; + res + } + + fn fold_closure_args( + &mut self, + def_id: DefId, + args: GenericArgsRef<'tcx>, + ) -> Result<GenericArgsRef<'tcx>, RegionVid> { + let generics = self.cx().generics_of(def_id); + self.cx().mk_args_from_iter(args.iter().enumerate().map(|(index, arg)| { + if index < generics.parent_count { + Ok(self.fold_non_member_arg(arg)) + } else { + arg.try_fold_with(self) + } + })) + } +} +impl<'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for ToArgRegionsFolder<'_, 'tcx> { + type Error = RegionVid; + fn cx(&self) -> TyCtxt<'tcx> { + self.rcx.infcx.tcx + } + + fn try_fold_region(&mut self, r: Region<'tcx>) -> Result<Region<'tcx>, RegionVid> { + match r.kind() { + // ignore bound regions, keep visiting + ty::ReBound(_, _) => Ok(r), + _ => { + let r = r.as_var(); + if let Some(arg_region) = self + .arg_regions + .iter() + .copied() + .find(|&arg_vid| self.rcx.eval_equal(r, arg_vid)) + .and_then(|r| nll_var_to_universal_region(self.rcx, r)) + { + Ok(arg_region) + } else if self.erase_unknown_regions { + Ok(self.cx().lifetimes.re_erased) + } else { + Err(r) + } + } + } + } + + fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, RegionVid> { + if !ty.flags().intersects(ty::TypeFlags::HAS_FREE_REGIONS) { + return Ok(ty); + } + + let tcx = self.cx(); + Ok(match *ty.kind() { + ty::Closure(def_id, args) => { + Ty::new_closure(tcx, def_id, self.fold_closure_args(def_id, args)?) + } + + ty::CoroutineClosure(def_id, args) => { + Ty::new_coroutine_closure(tcx, def_id, self.fold_closure_args(def_id, args)?) + } + + ty::Coroutine(def_id, args) => { + Ty::new_coroutine(tcx, def_id, self.fold_closure_args(def_id, args)?) + } + + ty::Alias(kind, ty::AliasTy { def_id, args, .. }) + if let Some(variances) = tcx.opt_alias_variances(kind, def_id) => + { + let args = tcx.mk_args_from_iter(std::iter::zip(variances, args.iter()).map( + |(&v, s)| { + if v == ty::Bivariant { + Ok(self.fold_non_member_arg(s)) + } else { + s.try_fold_with(self) + } + }, + ))?; + ty::AliasTy::new_from_args(tcx, def_id, args).to_ty(tcx) + } + + _ => ty.try_super_fold_with(self)?, + }) + } +} + +/// This function is what actually applies member constraints to the borrowck +/// state. It is also responsible to check all uses of the opaques in their +/// defining scope. +/// +/// It does this by equating the hidden type of each use with the instantiated final +/// hidden type of the opaque. +fn apply_computed_concrete_opaque_types<'tcx>( + root_cx: &mut BorrowCheckRootCtxt<'tcx>, + infcx: &BorrowckInferCtxt<'tcx>, + body: &Body<'tcx>, + universal_regions: &UniversalRegions<'tcx>, + region_bound_pairs: &RegionBoundPairs<'tcx>, + known_type_outlives_obligations: &[ty::PolyTypeOutlivesPredicate<'tcx>], + constraints: &mut MirTypeckRegionConstraints<'tcx>, + opaque_types: &[(OpaqueTypeKey<'tcx>, OpaqueHiddenType<'tcx>)], +) -> Vec<DeferredOpaqueTypeError<'tcx>> { + let tcx = infcx.tcx; + let mut errors = Vec::new(); + for &(key, hidden_type) in opaque_types { + let Some(expected) = root_cx.get_concrete_opaque_type(key.def_id) else { + assert!(tcx.use_typing_mode_borrowck(), "non-defining use in defining scope"); + errors.push(DeferredOpaqueTypeError::NonDefiningUseInDefiningScope { + span: hidden_type.span, + opaque_type_key: key, + }); + let guar = tcx.dcx().span_delayed_bug( + hidden_type.span, + "non-defining use in the defining scope with no defining uses", + ); + root_cx.add_concrete_opaque_type(key.def_id, OpaqueHiddenType::new_error(tcx, guar)); + continue; + }; + + // We erase all non-member region of the opaque and need to treat these as existentials. + let expected = ty::fold_regions(tcx, expected.instantiate(tcx, key.args), |re, _dbi| { + match re.kind() { + ty::ReErased => infcx.next_nll_region_var( + NllRegionVariableOrigin::Existential { name: None }, + || crate::RegionCtxt::Existential(None), + ), + _ => re, + } + }); + + // We now simply equate the expected with the actual hidden type. + let locations = Locations::All(hidden_type.span); + if let Err(guar) = fully_perform_op_raw( + infcx, + body, + universal_regions, + region_bound_pairs, + known_type_outlives_obligations, + constraints, + locations, + ConstraintCategory::OpaqueType, + CustomTypeOp::new( + |ocx| { + let cause = ObligationCause::misc( + hidden_type.span, + body.source.def_id().expect_local(), + ); + // We need to normalize both types in the old solver before equatingt them. + let actual_ty = ocx.normalize(&cause, infcx.param_env, hidden_type.ty); + let expected_ty = ocx.normalize(&cause, infcx.param_env, expected.ty); + ocx.eq(&cause, infcx.param_env, actual_ty, expected_ty).map_err(|_| NoSolution) + }, + "equating opaque types", + ), + ) { + root_cx.add_concrete_opaque_type(key.def_id, OpaqueHiddenType::new_error(tcx, guar)); + } + } + errors +} + +/// In theory `apply_concrete_opaque_types` could introduce new uses of opaque types. +/// We do not check these new uses so this could be unsound. +/// +/// We detect any new uses and simply delay a bug if they occur. If this results in +/// an ICE we can properly handle this, but we haven't encountered any such test yet. +/// +/// See the related comment in `FnCtxt::detect_opaque_types_added_during_writeback`. +fn detect_opaque_types_added_while_handling_opaque_types<'tcx>( + infcx: &InferCtxt<'tcx>, + opaque_types_storage_num_entries: OpaqueTypeStorageEntries, +) { + for (key, hidden_type) in infcx + .inner + .borrow_mut() + .opaque_types() + .opaque_types_added_since(opaque_types_storage_num_entries) + { + let opaque_type_string = infcx.tcx.def_path_str(key.def_id); + let msg = format!("unexpected cyclic definition of `{opaque_type_string}`"); + infcx.dcx().span_delayed_bug(hidden_type.span, msg); + } + + let _ = infcx.take_opaque_types(); +} + +impl<'tcx> RegionInferenceContext<'tcx> { + /// Map the regions in the type to named regions. This is similar to what + /// `infer_opaque_types` does, but can infer any universal region, not only + /// ones from the args for the opaque type. It also doesn't double check + /// that the regions produced are in fact equal to the named region they are + /// replaced with. This is fine because this function is only to improve the + /// region names in error messages. + /// + /// This differs from `MirBorrowckCtxt::name_regions` since it is particularly + /// lax with mapping region vids that are *shorter* than a universal region to + /// that universal region. This is useful for member region constraints since + /// we want to suggest a universal region name to capture even if it's technically + /// not equal to the error region. + pub(crate) fn name_regions_for_member_constraint<T>(&self, tcx: TyCtxt<'tcx>, ty: T) -> T + where + T: TypeFoldable<TyCtxt<'tcx>>, + { + fold_regions(tcx, ty, |region, _| match region.kind() { + ty::ReVar(vid) => { + let scc = self.constraint_sccs.scc(vid); + + // Special handling of higher-ranked regions. + if !self.max_nameable_universe(scc).is_root() { + match self.scc_values.placeholders_contained_in(scc).enumerate().last() { + // If the region contains a single placeholder then they're equal. + Some((0, placeholder)) => { + return ty::Region::new_placeholder(tcx, placeholder); + } + + // Fallback: this will produce a cryptic error message. + _ => return region, + } + } + + // Find something that we can name + let upper_bound = self.approx_universal_upper_bound(vid); + if let Some(universal_region) = self.definitions[upper_bound].external_name { + return universal_region; + } + + // Nothing exact found, so we pick a named upper bound, if there's only one. + // If there's >1 universal region, then we probably are dealing w/ an intersection + // region which cannot be mapped back to a universal. + // FIXME: We could probably compute the LUB if there is one. + let scc = self.constraint_sccs.scc(vid); + let rev_scc_graph = + ReverseSccGraph::compute(&self.constraint_sccs, self.universal_regions()); + let upper_bounds: Vec<_> = rev_scc_graph + .upper_bounds(scc) + .filter_map(|vid| self.definitions[vid].external_name) + .filter(|r| !r.is_static()) + .collect(); + match &upper_bounds[..] { + [universal_region] => *universal_region, + _ => region, + } + } + _ => region, + }) + } +} + +#[extension(pub trait InferCtxtExt<'tcx>)] +impl<'tcx> InferCtxt<'tcx> { + /// Given the fully resolved, instantiated type for an opaque + /// type, i.e., the value of an inference variable like C1 or C2 + /// (*), computes the "definition type" for an opaque type + /// definition -- that is, the inferred value of `Foo1<'x>` or + /// `Foo2<'x>` that we would conceptually use in its definition: + /// ```ignore (illustrative) + /// type Foo1<'x> = impl Bar<'x> = AAA; // <-- this type AAA + /// type Foo2<'x> = impl Bar<'x> = BBB; // <-- or this type BBB + /// fn foo<'a, 'b>(..) -> (Foo1<'a>, Foo2<'b>) { .. } + /// ``` + /// Note that these values are defined in terms of a distinct set of + /// generic parameters (`'x` instead of `'a`) from C1 or C2. The main + /// purpose of this function is to do that translation. + /// + /// (*) C1 and C2 were introduced in the comments on + /// `register_member_constraints`. Read that comment for more context. + /// + /// # Parameters + /// + /// - `def_id`, the `impl Trait` type + /// - `args`, the args used to instantiate this opaque type + /// - `instantiated_ty`, the inferred type C1 -- fully resolved, lifted version of + /// `opaque_defn.concrete_ty` + #[instrument(level = "debug", skip(self))] + fn infer_opaque_definition_from_instantiation( + &self, + opaque_type_key: OpaqueTypeKey<'tcx>, + instantiated_ty: OpaqueHiddenType<'tcx>, + ) -> Result<Ty<'tcx>, NonDefiningUseReason<'tcx>> { + opaque_type_has_defining_use_args( + self, + opaque_type_key, + instantiated_ty.span, + DefiningScopeKind::MirBorrowck, + )?; + + let definition_ty = instantiated_ty + .remap_generic_params_to_declaration_params( + opaque_type_key, + self.tcx, + DefiningScopeKind::MirBorrowck, + ) + .ty; + + definition_ty.error_reported()?; + Ok(definition_ty) + } +} diff --git a/compiler/rustc_borrowck/src/region_infer/opaque_types/region_ctxt.rs b/compiler/rustc_borrowck/src/region_infer/opaque_types/region_ctxt.rs new file mode 100644 index 00000000000..88326e4eebf --- /dev/null +++ b/compiler/rustc_borrowck/src/region_infer/opaque_types/region_ctxt.rs @@ -0,0 +1,114 @@ +use std::rc::Rc; + +use rustc_data_structures::frozen::Frozen; +use rustc_index::IndexVec; +use rustc_infer::infer::NllRegionVariableOrigin; +use rustc_middle::ty::{RegionVid, UniverseIndex}; +use rustc_mir_dataflow::points::DenseLocationMap; + +use crate::BorrowckInferCtxt; +use crate::constraints::ConstraintSccIndex; +use crate::handle_placeholders::{SccAnnotations, region_definitions}; +use crate::region_infer::reverse_sccs::ReverseSccGraph; +use crate::region_infer::values::RegionValues; +use crate::region_infer::{ConstraintSccs, RegionDefinition, RegionTracker, Representative}; +use crate::type_check::MirTypeckRegionConstraints; +use crate::type_check::free_region_relations::UniversalRegionRelations; +use crate::universal_regions::UniversalRegions; + +/// A slimmed down version of [crate::region_infer::RegionInferenceContext] used +/// only by opaque type handling. +pub(super) struct RegionCtxt<'a, 'tcx> { + pub(super) infcx: &'a BorrowckInferCtxt<'tcx>, + pub(super) definitions: Frozen<IndexVec<RegionVid, RegionDefinition<'tcx>>>, + pub(super) universal_region_relations: &'a UniversalRegionRelations<'tcx>, + pub(super) constraint_sccs: ConstraintSccs, + pub(super) scc_annotations: IndexVec<ConstraintSccIndex, RegionTracker>, + pub(super) rev_scc_graph: ReverseSccGraph, + pub(super) scc_values: RegionValues<ConstraintSccIndex>, +} + +impl<'a, 'tcx> RegionCtxt<'a, 'tcx> { + /// Creates a new `RegionCtxt` used to compute defining opaque type uses. + /// + /// This does not yet propagate region values. This is instead done lazily + /// when applying member constraints. + pub(super) fn new( + infcx: &'a BorrowckInferCtxt<'tcx>, + universal_region_relations: &'a Frozen<UniversalRegionRelations<'tcx>>, + location_map: Rc<DenseLocationMap>, + constraints: &MirTypeckRegionConstraints<'tcx>, + ) -> RegionCtxt<'a, 'tcx> { + let universal_regions = &universal_region_relations.universal_regions; + let (definitions, _has_placeholders) = region_definitions(infcx, universal_regions); + let mut scc_annotations = SccAnnotations::init(&definitions); + let constraint_sccs = ConstraintSccs::new_with_annotation( + &constraints + .outlives_constraints + .graph(definitions.len()) + .region_graph(&constraints.outlives_constraints, universal_regions.fr_static), + &mut scc_annotations, + ); + let scc_annotations = scc_annotations.scc_to_annotation; + + // Unlike the `RegionInferenceContext`, we only care about free regions + // and fully ignore liveness and placeholders. + let placeholder_indices = Default::default(); + let mut scc_values = + RegionValues::new(location_map, universal_regions.len(), placeholder_indices); + for variable in definitions.indices() { + let scc = constraint_sccs.scc(variable); + match definitions[variable].origin { + NllRegionVariableOrigin::FreeRegion => { + scc_values.add_element(scc, variable); + } + _ => {} + } + } + + let rev_scc_graph = ReverseSccGraph::compute(&constraint_sccs, universal_regions); + RegionCtxt { + infcx, + definitions, + universal_region_relations, + constraint_sccs, + scc_annotations, + rev_scc_graph, + scc_values, + } + } + + pub(super) fn representative(&self, vid: RegionVid) -> Representative { + let scc = self.constraint_sccs.scc(vid); + self.scc_annotations[scc].representative + } + + pub(crate) fn max_placeholder_universe_reached( + &self, + scc: ConstraintSccIndex, + ) -> UniverseIndex { + self.scc_annotations[scc].max_placeholder_universe_reached() + } + + pub(super) fn universal_regions(&self) -> &UniversalRegions<'tcx> { + &self.universal_region_relations.universal_regions + } + + pub(super) fn eval_equal(&self, r1_vid: RegionVid, r2_vid: RegionVid) -> bool { + let r1 = self.constraint_sccs.scc(r1_vid); + let r2 = self.constraint_sccs.scc(r2_vid); + + if r1 == r2 { + return true; + } + + let universal_outlives = |sub, sup| { + self.scc_values.universal_regions_outlived_by(sub).all(|r1| { + self.scc_values + .universal_regions_outlived_by(sup) + .any(|r2| self.universal_region_relations.outlives(r2, r1)) + }) + }; + universal_outlives(r1, r2) && universal_outlives(r2, r1) + } +} diff --git a/compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs b/compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs index 604265f8940..e8da85eccef 100644 --- a/compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs +++ b/compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs @@ -5,7 +5,6 @@ use rustc_data_structures::graph; use rustc_data_structures::graph::vec_graph::VecGraph; use rustc_middle::ty::RegionVid; -use crate::RegionInferenceContext; use crate::constraints::ConstraintSccIndex; use crate::region_infer::ConstraintSccs; use crate::universal_regions::UniversalRegions; @@ -57,12 +56,3 @@ impl ReverseSccGraph { .filter(move |r| duplicates.insert(*r)) } } - -impl RegionInferenceContext<'_> { - /// Return the reverse graph of the region SCCs, initialising it if needed. - pub(super) fn reverse_scc_graph(&self) -> &ReverseSccGraph { - self.rev_scc_graph.get_or_init(|| { - ReverseSccGraph::compute(&self.constraint_sccs, self.universal_regions()) - }) - } -} diff --git a/compiler/rustc_borrowck/src/root_cx.rs b/compiler/rustc_borrowck/src/root_cx.rs index 9b1d12aede5..4e90ae391bb 100644 --- a/compiler/rustc_borrowck/src/root_cx.rs +++ b/compiler/rustc_borrowck/src/root_cx.rs @@ -2,7 +2,7 @@ use rustc_abi::FieldIdx; use rustc_data_structures::fx::FxHashMap; use rustc_hir::def_id::LocalDefId; use rustc_middle::bug; -use rustc_middle::ty::{OpaqueHiddenType, Ty, TyCtxt, TypeVisitableExt}; +use rustc_middle::ty::{EarlyBinder, OpaqueHiddenType, Ty, TyCtxt, TypeVisitableExt}; use rustc_span::ErrorGuaranteed; use smallvec::SmallVec; @@ -19,7 +19,7 @@ pub(super) struct BorrowCheckRootCtxt<'tcx> { tainted_by_errors: Option<ErrorGuaranteed>, /// This should be `None` during normal compilation. See [`crate::consumers`] for more /// information on how this is used. - pub(crate) consumer: Option<BorrowckConsumer<'tcx>>, + pub consumer: Option<BorrowckConsumer<'tcx>>, } impl<'tcx> BorrowCheckRootCtxt<'tcx> { @@ -38,6 +38,10 @@ impl<'tcx> BorrowCheckRootCtxt<'tcx> { } } + pub(super) fn root_def_id(&self) -> LocalDefId { + self.root_def_id + } + /// Collect all defining uses of opaque types inside of this typeck root. This /// expects the hidden type to be mapped to the definition parameters of the opaque /// and errors if we end up with distinct hidden types. @@ -67,6 +71,13 @@ impl<'tcx> BorrowCheckRootCtxt<'tcx> { } } + pub(super) fn get_concrete_opaque_type( + &mut self, + def_id: LocalDefId, + ) -> Option<EarlyBinder<'tcx, OpaqueHiddenType<'tcx>>> { + self.concrete_opaque_types.0.get(&def_id).map(|ty| EarlyBinder::bind(*ty)) + } + pub(super) fn set_tainted_by_errors(&mut self, guar: ErrorGuaranteed) { self.tainted_by_errors = Some(guar); } diff --git a/compiler/rustc_borrowck/src/type_check/canonical.rs b/compiler/rustc_borrowck/src/type_check/canonical.rs index b3fa786a517..2627ed899a9 100644 --- a/compiler/rustc_borrowck/src/type_check/canonical.rs +++ b/compiler/rustc_borrowck/src/type_check/canonical.rs @@ -2,8 +2,9 @@ use std::fmt; use rustc_errors::ErrorGuaranteed; use rustc_infer::infer::canonical::Canonical; +use rustc_infer::infer::outlives::env::RegionBoundPairs; use rustc_middle::bug; -use rustc_middle::mir::ConstraintCategory; +use rustc_middle::mir::{Body, ConstraintCategory}; use rustc_middle::ty::{self, Ty, TyCtxt, TypeFoldable, Upcast}; use rustc_span::Span; use rustc_span::def_id::DefId; @@ -14,7 +15,68 @@ use rustc_trait_selection::traits::query::type_op::{self, TypeOpOutput}; use tracing::{debug, instrument}; use super::{Locations, NormalizeLocation, TypeChecker}; +use crate::BorrowckInferCtxt; use crate::diagnostics::ToUniverseInfo; +use crate::type_check::{MirTypeckRegionConstraints, constraint_conversion}; +use crate::universal_regions::UniversalRegions; + +#[instrument(skip(infcx, constraints, op), level = "trace")] +pub(crate) fn fully_perform_op_raw<'tcx, R: fmt::Debug, Op>( + infcx: &BorrowckInferCtxt<'tcx>, + body: &Body<'tcx>, + universal_regions: &UniversalRegions<'tcx>, + region_bound_pairs: &RegionBoundPairs<'tcx>, + known_type_outlives_obligations: &[ty::PolyTypeOutlivesPredicate<'tcx>], + constraints: &mut MirTypeckRegionConstraints<'tcx>, + locations: Locations, + category: ConstraintCategory<'tcx>, + op: Op, +) -> Result<R, ErrorGuaranteed> +where + Op: type_op::TypeOp<'tcx, Output = R>, + Op::ErrorInfo: ToUniverseInfo<'tcx>, +{ + let old_universe = infcx.universe(); + + let TypeOpOutput { output, constraints: query_constraints, error_info } = + op.fully_perform(infcx, infcx.root_def_id, locations.span(body))?; + if cfg!(debug_assertions) { + let data = infcx.take_and_reset_region_constraints(); + if !data.is_empty() { + panic!("leftover region constraints: {data:#?}"); + } + } + + debug!(?output, ?query_constraints); + + if let Some(data) = query_constraints { + constraint_conversion::ConstraintConversion::new( + infcx, + universal_regions, + region_bound_pairs, + known_type_outlives_obligations, + locations, + locations.span(body), + category, + constraints, + ) + .convert_all(data); + } + + // If the query has created new universes and errors are going to be emitted, register the + // cause of these new universes for improved diagnostics. + let universe = infcx.universe(); + if old_universe != universe + && let Some(error_info) = error_info + { + let universe_info = error_info.to_universe_info(old_universe); + for u in (old_universe + 1)..=universe { + constraints.universe_causes.insert(u, universe_info.clone()); + } + } + + Ok(output) +} impl<'a, 'tcx> TypeChecker<'a, 'tcx> { /// Given some operation `op` that manipulates types, proves @@ -38,36 +100,17 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> { Op: type_op::TypeOp<'tcx, Output = R>, Op::ErrorInfo: ToUniverseInfo<'tcx>, { - let old_universe = self.infcx.universe(); - - let TypeOpOutput { output, constraints, error_info } = - op.fully_perform(self.infcx, locations.span(self.body))?; - if cfg!(debug_assertions) { - let data = self.infcx.take_and_reset_region_constraints(); - if !data.is_empty() { - panic!("leftover region constraints: {data:#?}"); - } - } - - debug!(?output, ?constraints); - - if let Some(data) = constraints { - self.push_region_constraints(locations, category, data); - } - - // If the query has created new universes and errors are going to be emitted, register the - // cause of these new universes for improved diagnostics. - let universe = self.infcx.universe(); - if old_universe != universe - && let Some(error_info) = error_info - { - let universe_info = error_info.to_universe_info(old_universe); - for u in (old_universe + 1)..=universe { - self.constraints.universe_causes.insert(u, universe_info.clone()); - } - } - - Ok(output) + fully_perform_op_raw( + self.infcx, + self.body, + self.universal_regions, + self.region_bound_pairs, + self.known_type_outlives_obligations, + self.constraints, + locations, + category, + op, + ) } pub(super) fn instantiate_canonical<T>( diff --git a/compiler/rustc_borrowck/src/type_check/constraint_conversion.rs b/compiler/rustc_borrowck/src/type_check/constraint_conversion.rs index 9bb96b94506..703223e2e54 100644 --- a/compiler/rustc_borrowck/src/type_check/constraint_conversion.rs +++ b/compiler/rustc_borrowck/src/type_check/constraint_conversion.rs @@ -1,10 +1,10 @@ use rustc_data_structures::fx::FxHashSet; use rustc_hir::def_id::LocalDefId; +use rustc_infer::infer::SubregionOrigin; use rustc_infer::infer::canonical::QueryRegionConstraints; use rustc_infer::infer::outlives::env::RegionBoundPairs; use rustc_infer::infer::outlives::obligations::{TypeOutlives, TypeOutlivesDelegate}; use rustc_infer::infer::region_constraints::{GenericKind, VerifyBound}; -use rustc_infer::infer::{InferCtxt, SubregionOrigin}; use rustc_infer::traits::query::type_op::DeeplyNormalize; use rustc_middle::bug; use rustc_middle::ty::{ @@ -18,10 +18,12 @@ use crate::constraints::OutlivesConstraint; use crate::region_infer::TypeTest; use crate::type_check::{Locations, MirTypeckRegionConstraints}; use crate::universal_regions::UniversalRegions; -use crate::{ClosureOutlivesSubject, ClosureRegionRequirements, ConstraintCategory}; +use crate::{ + BorrowckInferCtxt, ClosureOutlivesSubject, ClosureRegionRequirements, ConstraintCategory, +}; pub(crate) struct ConstraintConversion<'a, 'tcx> { - infcx: &'a InferCtxt<'tcx>, + infcx: &'a BorrowckInferCtxt<'tcx>, universal_regions: &'a UniversalRegions<'tcx>, /// Each RBP `GK: 'a` is assumed to be true. These encode /// relationships like `T: 'a` that are added via implicit bounds @@ -34,7 +36,6 @@ pub(crate) struct ConstraintConversion<'a, 'tcx> { /// logic expecting to see (e.g.) `ReStatic`, and if we supplied /// our special inference variable there, we would mess that up. region_bound_pairs: &'a RegionBoundPairs<'tcx>, - param_env: ty::ParamEnv<'tcx>, known_type_outlives_obligations: &'a [ty::PolyTypeOutlivesPredicate<'tcx>], locations: Locations, span: Span, @@ -45,10 +46,9 @@ pub(crate) struct ConstraintConversion<'a, 'tcx> { impl<'a, 'tcx> ConstraintConversion<'a, 'tcx> { pub(crate) fn new( - infcx: &'a InferCtxt<'tcx>, + infcx: &'a BorrowckInferCtxt<'tcx>, universal_regions: &'a UniversalRegions<'tcx>, region_bound_pairs: &'a RegionBoundPairs<'tcx>, - param_env: ty::ParamEnv<'tcx>, known_type_outlives_obligations: &'a [ty::PolyTypeOutlivesPredicate<'tcx>], locations: Locations, span: Span, @@ -59,7 +59,6 @@ impl<'a, 'tcx> ConstraintConversion<'a, 'tcx> { infcx, universal_regions, region_bound_pairs, - param_env, known_type_outlives_obligations, locations, span, @@ -286,8 +285,11 @@ impl<'a, 'tcx> ConstraintConversion<'a, 'tcx> { ConstraintCategory<'tcx>, )>, ) -> Ty<'tcx> { - match self.param_env.and(DeeplyNormalize { value: ty }).fully_perform(self.infcx, self.span) - { + match self.infcx.param_env.and(DeeplyNormalize { value: ty }).fully_perform( + self.infcx, + self.infcx.root_def_id, + self.span, + ) { Ok(TypeOpOutput { output: ty, constraints, .. }) => { // FIXME(higher_ranked_auto): What should we do with the assumptions here? if let Some(QueryRegionConstraints { outlives, assumptions: _ }) = constraints { diff --git a/compiler/rustc_borrowck/src/type_check/free_region_relations.rs b/compiler/rustc_borrowck/src/type_check/free_region_relations.rs index f642d34ea67..7bf2df91470 100644 --- a/compiler/rustc_borrowck/src/type_check/free_region_relations.rs +++ b/compiler/rustc_borrowck/src/type_check/free_region_relations.rs @@ -2,9 +2,9 @@ use rustc_data_structures::frozen::Frozen; use rustc_data_structures::transitive_relation::{TransitiveRelation, TransitiveRelationBuilder}; use rustc_hir::def::DefKind; use rustc_infer::infer::canonical::QueryRegionConstraints; +use rustc_infer::infer::outlives; use rustc_infer::infer::outlives::env::RegionBoundPairs; use rustc_infer::infer::region_constraints::GenericKind; -use rustc_infer::infer::{InferCtxt, outlives}; use rustc_infer::traits::query::type_op::DeeplyNormalize; use rustc_middle::mir::ConstraintCategory; use rustc_middle::traits::query::OutlivesBound; @@ -14,6 +14,7 @@ use rustc_trait_selection::traits::query::type_op::{self, TypeOp}; use tracing::{debug, instrument}; use type_op::TypeOpOutput; +use crate::BorrowckInferCtxt; use crate::type_check::{Locations, MirTypeckRegionConstraints, constraint_conversion}; use crate::universal_regions::UniversalRegions; @@ -47,14 +48,12 @@ pub(crate) struct CreateResult<'tcx> { } pub(crate) fn create<'tcx>( - infcx: &InferCtxt<'tcx>, - param_env: ty::ParamEnv<'tcx>, + infcx: &BorrowckInferCtxt<'tcx>, universal_regions: UniversalRegions<'tcx>, constraints: &mut MirTypeckRegionConstraints<'tcx>, ) -> CreateResult<'tcx> { UniversalRegionRelationsBuilder { infcx, - param_env, constraints, universal_regions, region_bound_pairs: Default::default(), @@ -177,8 +176,7 @@ impl UniversalRegionRelations<'_> { } struct UniversalRegionRelationsBuilder<'a, 'tcx> { - infcx: &'a InferCtxt<'tcx>, - param_env: ty::ParamEnv<'tcx>, + infcx: &'a BorrowckInferCtxt<'tcx>, universal_regions: UniversalRegions<'tcx>, constraints: &'a mut MirTypeckRegionConstraints<'tcx>, @@ -205,7 +203,7 @@ impl<'tcx> UniversalRegionRelationsBuilder<'_, 'tcx> { // Insert the `'a: 'b` we know from the predicates. // This does not consider the type-outlives. - let param_env = self.param_env; + let param_env = self.infcx.param_env; self.add_outlives_bounds(outlives::explicit_outlives_bounds(param_env)); // - outlives is reflexive, so `'r: 'r` for every region `'r` @@ -263,7 +261,7 @@ impl<'tcx> UniversalRegionRelationsBuilder<'_, 'tcx> { let TypeOpOutput { output: norm_ty, constraints: constraints_normalize, .. } = param_env .and(DeeplyNormalize { value: ty }) - .fully_perform(self.infcx, span) + .fully_perform(self.infcx, self.infcx.root_def_id, span) .unwrap_or_else(|guar| TypeOpOutput { output: Ty::new_error(self.infcx.tcx, guar), constraints: None, @@ -298,8 +296,9 @@ impl<'tcx> UniversalRegionRelationsBuilder<'_, 'tcx> { // Add implied bounds from impl header. if matches!(tcx.def_kind(defining_ty_def_id), DefKind::AssocFn | DefKind::AssocConst) { for &(ty, _) in tcx.assumed_wf_types(tcx.local_parent(defining_ty_def_id)) { - let result: Result<_, ErrorGuaranteed> = - param_env.and(DeeplyNormalize { value: ty }).fully_perform(self.infcx, span); + let result: Result<_, ErrorGuaranteed> = param_env + .and(DeeplyNormalize { value: ty }) + .fully_perform(self.infcx, self.infcx.root_def_id, span); let Ok(TypeOpOutput { output: norm_ty, constraints: c, .. }) = result else { continue; }; @@ -318,7 +317,6 @@ impl<'tcx> UniversalRegionRelationsBuilder<'_, 'tcx> { self.infcx, &self.universal_regions, &self.region_bound_pairs, - param_env, &known_type_outlives_obligations, Locations::All(span), span, @@ -353,10 +351,11 @@ impl<'tcx> UniversalRegionRelationsBuilder<'_, 'tcx> { output: normalized_outlives, constraints: constraints_normalize, error_info: _, - }) = self - .param_env - .and(DeeplyNormalize { value: outlives }) - .fully_perform(self.infcx, span) + }) = self.infcx.param_env.and(DeeplyNormalize { value: outlives }).fully_perform( + self.infcx, + self.infcx.root_def_id, + span, + ) else { self.infcx.dcx().delayed_bug(format!("could not normalize {outlives:?}")); return; @@ -381,9 +380,10 @@ impl<'tcx> UniversalRegionRelationsBuilder<'_, 'tcx> { span: Span, ) -> Option<&'tcx QueryRegionConstraints<'tcx>> { let TypeOpOutput { output: bounds, constraints, .. } = self + .infcx .param_env .and(type_op::ImpliedOutlivesBounds { ty }) - .fully_perform(self.infcx, span) + .fully_perform(self.infcx, self.infcx.root_def_id, span) .map_err(|_: ErrorGuaranteed| debug!("failed to compute implied bounds {:?}", ty)) .ok()?; debug!(?bounds, ?constraints); diff --git a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs index 5d30fa71e92..b704d8f0a76 100644 --- a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs +++ b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs @@ -640,7 +640,7 @@ impl<'tcx> LivenessContext<'_, '_, 'tcx> { let op = typeck.infcx.param_env.and(DropckOutlives { dropped_ty }); - match op.fully_perform(typeck.infcx, DUMMY_SP) { + match op.fully_perform(typeck.infcx, typeck.root_cx.root_def_id(), DUMMY_SP) { Ok(TypeOpOutput { output, constraints, .. }) => { DropData { dropck_result: output, region_constraint_data: constraints } } diff --git a/compiler/rustc_borrowck/src/type_check/mod.rs b/compiler/rustc_borrowck/src/type_check/mod.rs index c3aa205d5aa..0d363935f14 100644 --- a/compiler/rustc_borrowck/src/type_check/mod.rs +++ b/compiler/rustc_borrowck/src/type_check/mod.rs @@ -26,8 +26,7 @@ use rustc_middle::ty::adjustment::PointerCoercion; use rustc_middle::ty::cast::CastTy; use rustc_middle::ty::{ self, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations, CoroutineArgsExt, - GenericArgsRef, OpaqueHiddenType, OpaqueTypeKey, RegionVid, Ty, TyCtxt, TypeVisitableExt, - UserArgs, UserTypeAnnotationIndex, fold_regions, + GenericArgsRef, Ty, TyCtxt, TypeVisitableExt, UserArgs, UserTypeAnnotationIndex, fold_regions, }; use rustc_middle::{bug, span_bug}; use rustc_mir_dataflow::move_paths::MoveData; @@ -35,6 +34,7 @@ use rustc_mir_dataflow::points::DenseLocationMap; use rustc_span::def_id::CRATE_DEF_ID; use rustc_span::source_map::Spanned; use rustc_span::{Span, sym}; +use rustc_trait_selection::infer::InferCtxtExt; use rustc_trait_selection::traits::query::type_op::custom::scrape_region_constraints; use rustc_trait_selection::traits::query::type_op::{TypeOp, TypeOpOutput}; use tracing::{debug, instrument, trace}; @@ -42,7 +42,6 @@ use tracing::{debug, instrument, trace}; use crate::borrow_set::BorrowSet; use crate::constraints::{OutlivesConstraint, OutlivesConstraintSet}; use crate::diagnostics::UniverseInfo; -use crate::member_constraints::MemberConstraintSet; use crate::polonius::legacy::{PoloniusFacts, PoloniusLocationTable}; use crate::polonius::{PoloniusContext, PoloniusLivenessContext}; use crate::region_infer::TypeTest; @@ -67,12 +66,11 @@ macro_rules! span_mirbug { }) } -mod canonical; +pub(crate) mod canonical; mod constraint_conversion; pub(crate) mod free_region_relations; mod input_output; pub(crate) mod liveness; -mod opaque_types; mod relate_tys; /// Type checks the given `mir` in the context of the inference @@ -114,7 +112,6 @@ pub(crate) fn type_check<'tcx>( placeholder_index_to_region: IndexVec::default(), liveness_constraints: LivenessValues::with_specific_points(Rc::clone(&location_map)), outlives_constraints: OutlivesConstraintSet::default(), - member_constraints: MemberConstraintSet::default(), type_tests: Vec::default(), universe_causes: FxIndexMap::default(), }; @@ -124,7 +121,7 @@ pub(crate) fn type_check<'tcx>( region_bound_pairs, normalized_inputs_and_output, known_type_outlives_obligations, - } = free_region_relations::create(infcx, infcx.param_env, universal_regions, &mut constraints); + } = free_region_relations::create(infcx, universal_regions, &mut constraints); let pre_obligations = infcx.take_registered_region_obligations(); assert!( @@ -170,9 +167,6 @@ pub(crate) fn type_check<'tcx>( liveness::generate(&mut typeck, &location_map, move_data); - let opaque_type_values = - opaque_types::take_opaques_and_register_member_constraints(&mut typeck); - // We're done with typeck, we can finalize the polonius liveness context for region inference. let polonius_context = typeck.polonius_liveness.take().map(|liveness_context| { PoloniusContext::create_from_liveness( @@ -187,7 +181,6 @@ pub(crate) fn type_check<'tcx>( if let Some(guar) = universal_region_relations.universal_regions.encountered_re_error() { debug!("encountered an error region; removing constraints!"); constraints.outlives_constraints = Default::default(); - constraints.member_constraints = Default::default(); constraints.type_tests = Default::default(); root_cx.set_tainted_by_errors(guar); infcx.set_tainted_by_errors(guar); @@ -196,7 +189,8 @@ pub(crate) fn type_check<'tcx>( MirTypeckResults { constraints, universal_region_relations, - opaque_type_values, + region_bound_pairs, + known_type_outlives_obligations, polonius_context, } } @@ -245,7 +239,8 @@ struct TypeChecker<'a, 'tcx> { pub(crate) struct MirTypeckResults<'tcx> { pub(crate) constraints: MirTypeckRegionConstraints<'tcx>, pub(crate) universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>, - pub(crate) opaque_type_values: FxIndexMap<OpaqueTypeKey<'tcx>, OpaqueHiddenType<'tcx>>, + pub(crate) region_bound_pairs: Frozen<RegionBoundPairs<'tcx>>, + pub(crate) known_type_outlives_obligations: Frozen<Vec<ty::PolyTypeOutlivesPredicate<'tcx>>>, pub(crate) polonius_context: Option<PoloniusContext>, } @@ -277,8 +272,6 @@ pub(crate) struct MirTypeckRegionConstraints<'tcx> { pub(crate) outlives_constraints: OutlivesConstraintSet<'tcx>, - pub(crate) member_constraints: MemberConstraintSet<'tcx, RegionVid>, - pub(crate) universe_causes: FxIndexMap<ty::UniverseIndex, UniverseInfo<'tcx>>, pub(crate) type_tests: Vec<TypeTest<'tcx>>, @@ -287,7 +280,7 @@ pub(crate) struct MirTypeckRegionConstraints<'tcx> { impl<'tcx> MirTypeckRegionConstraints<'tcx> { /// Creates a `Region` for a given `PlaceholderRegion`, or returns the /// region that corresponds to a previously created one. - fn placeholder_region( + pub(crate) fn placeholder_region( &mut self, infcx: &InferCtxt<'tcx>, placeholder: ty::PlaceholderRegion, @@ -380,14 +373,6 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> { self.body } - fn to_region_vid(&mut self, r: ty::Region<'tcx>) -> RegionVid { - if let ty::RePlaceholder(placeholder) = r.kind() { - self.constraints.placeholder_region(self.infcx, placeholder).as_var() - } else { - self.universal_regions.to_region_vid(r) - } - } - fn unsized_feature_enabled(&self) -> bool { self.tcx().features().unsized_fn_params() } @@ -424,7 +409,6 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> { self.infcx, self.universal_regions, self.region_bound_pairs, - self.infcx.param_env, self.known_type_outlives_obligations, locations, locations.span(self.body), @@ -1471,68 +1455,79 @@ impl<'a, 'tcx> Visitor<'tcx> for TypeChecker<'a, 'tcx> { } CastKind::PtrToPtr => { let ty_from = op.ty(self.body, tcx); - let cast_ty_from = CastTy::from_ty(ty_from); - let cast_ty_to = CastTy::from_ty(*ty); - match (cast_ty_from, cast_ty_to) { - (Some(CastTy::Ptr(src)), Some(CastTy::Ptr(dst))) => { - let src_tail = self.struct_tail(src.ty, location); - let dst_tail = self.struct_tail(dst.ty, location); - - // This checks (lifetime part of) vtable validity for pointer casts, - // which is irrelevant when there are aren't principal traits on - // both sides (aka only auto traits). - // - // Note that other checks (such as denying `dyn Send` -> `dyn - // Debug`) are in `rustc_hir_typeck`. - if let ty::Dynamic(src_tty, _src_lt, ty::Dyn) = *src_tail.kind() - && let ty::Dynamic(dst_tty, dst_lt, ty::Dyn) = *dst_tail.kind() - && src_tty.principal().is_some() - && dst_tty.principal().is_some() - { - // Remove auto traits. - // Auto trait checks are handled in `rustc_hir_typeck` as FCW. - let src_obj = Ty::new_dynamic( - tcx, - tcx.mk_poly_existential_predicates( - &src_tty.without_auto_traits().collect::<Vec<_>>(), - ), - // FIXME: Once we disallow casting `*const dyn Trait + 'short` - // to `*const dyn Trait + 'long`, then this can just be `src_lt`. - dst_lt, - ty::Dyn, - ); - let dst_obj = Ty::new_dynamic( - tcx, - tcx.mk_poly_existential_predicates( - &dst_tty.without_auto_traits().collect::<Vec<_>>(), - ), - dst_lt, - ty::Dyn, - ); - - debug!(?src_tty, ?dst_tty, ?src_obj, ?dst_obj); - - self.sub_types( - src_obj, - dst_obj, - location.to_locations(), - ConstraintCategory::Cast { - is_implicit_coercion: false, - unsize_to: None, - }, - ) - .unwrap(); - } - } - _ => { - span_mirbug!( - self, - rvalue, - "Invalid PtrToPtr cast {:?} -> {:?}", - ty_from, - ty - ) - } + let Some(CastTy::Ptr(src)) = CastTy::from_ty(ty_from) else { + unreachable!(); + }; + let Some(CastTy::Ptr(dst)) = CastTy::from_ty(*ty) else { + unreachable!(); + }; + + if self.infcx.type_is_sized_modulo_regions(self.infcx.param_env, dst.ty) { + // Wide to thin ptr cast. This may even occur in an env with + // impossible predicates, such as `where dyn Trait: Sized`. + // In this case, we don't want to fall into the case below, + // since the types may not actually be equatable, but it's + // fine to perform this operation in an impossible env. + let trait_ref = ty::TraitRef::new( + tcx, + tcx.require_lang_item(LangItem::Sized, self.last_span), + [dst.ty], + ); + self.prove_trait_ref( + trait_ref, + location.to_locations(), + ConstraintCategory::Cast { + is_implicit_coercion: true, + unsize_to: None, + }, + ); + } else if let ty::Dynamic(src_tty, _src_lt, ty::Dyn) = + *self.struct_tail(src.ty, location).kind() + && let ty::Dynamic(dst_tty, dst_lt, ty::Dyn) = + *self.struct_tail(dst.ty, location).kind() + && src_tty.principal().is_some() + && dst_tty.principal().is_some() + { + // This checks (lifetime part of) vtable validity for pointer casts, + // which is irrelevant when there are aren't principal traits on + // both sides (aka only auto traits). + // + // Note that other checks (such as denying `dyn Send` -> `dyn + // Debug`) are in `rustc_hir_typeck`. + + // Remove auto traits. + // Auto trait checks are handled in `rustc_hir_typeck` as FCW. + let src_obj = Ty::new_dynamic( + tcx, + tcx.mk_poly_existential_predicates( + &src_tty.without_auto_traits().collect::<Vec<_>>(), + ), + // FIXME: Once we disallow casting `*const dyn Trait + 'short` + // to `*const dyn Trait + 'long`, then this can just be `src_lt`. + dst_lt, + ty::Dyn, + ); + let dst_obj = Ty::new_dynamic( + tcx, + tcx.mk_poly_existential_predicates( + &dst_tty.without_auto_traits().collect::<Vec<_>>(), + ), + dst_lt, + ty::Dyn, + ); + + debug!(?src_tty, ?dst_tty, ?src_obj, ?dst_obj); + + self.sub_types( + src_obj, + dst_obj, + location.to_locations(), + ConstraintCategory::Cast { + is_implicit_coercion: false, + unsize_to: None, + }, + ) + .unwrap(); } } CastKind::Transmute => { @@ -1773,10 +1768,7 @@ impl<'a, 'tcx> Visitor<'tcx> for TypeChecker<'a, 'tcx> { locations, ); - assert!(!matches!( - tcx.impl_of_assoc(def_id).map(|imp| tcx.def_kind(imp)), - Some(DefKind::Impl { of_trait: true }) - )); + assert_eq!(tcx.trait_impl_of_assoc(def_id), None); self.prove_predicates( args.types().map(|ty| ty::ClauseKind::WellFormed(ty.into())), locations, @@ -1898,7 +1890,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> { if !output_ty .is_privately_uninhabited(self.tcx(), self.infcx.typing_env(self.infcx.param_env)) { - span_mirbug!(self, term, "call to converging function {:?} w/o dest", sig); + span_mirbug!(self, term, "call to non-diverging function {:?} w/o dest", sig); } } else { let dest_ty = destination.ty(self.body, tcx).ty; @@ -2477,12 +2469,12 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> { args: GenericArgsRef<'tcx>, locations: Locations, ) -> ty::InstantiatedPredicates<'tcx> { + let root_def_id = self.root_cx.root_def_id(); if let Some(closure_requirements) = &self.root_cx.closure_requirements(def_id) { constraint_conversion::ConstraintConversion::new( self.infcx, self.universal_regions, self.region_bound_pairs, - self.infcx.param_env, self.known_type_outlives_obligations, locations, self.body.span, // irrelevant; will be overridden. @@ -2492,9 +2484,8 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> { .apply_closure_requirements(closure_requirements, def_id, args); } - // Now equate closure args to regions inherited from `typeck_root_def_id`. Fixes #98589. - let typeck_root_def_id = tcx.typeck_root_def_id(self.body.source.def_id()); - let typeck_root_args = ty::GenericArgs::identity_for_item(tcx, typeck_root_def_id); + // Now equate closure args to regions inherited from `root_def_id`. Fixes #98589. + let typeck_root_args = ty::GenericArgs::identity_for_item(tcx, root_def_id); let parent_args = match tcx.def_kind(def_id) { // We don't want to dispatch on 3 different kind of closures here, so take @@ -2569,17 +2560,14 @@ impl<'tcx> TypeOp<'tcx> for InstantiateOpaqueType<'tcx> { fn fully_perform( mut self, infcx: &InferCtxt<'tcx>, + root_def_id: LocalDefId, span: Span, ) -> Result<TypeOpOutput<'tcx, Self>, ErrorGuaranteed> { - let (mut output, region_constraints) = scrape_region_constraints( - infcx, - |ocx| { + let (mut output, region_constraints) = + scrape_region_constraints(infcx, root_def_id, "InstantiateOpaqueType", span, |ocx| { ocx.register_obligations(self.obligations.clone()); Ok(()) - }, - "InstantiateOpaqueType", - span, - )?; + })?; self.region_constraints = Some(region_constraints); output.error_info = Some(self); Ok(output) diff --git a/compiler/rustc_borrowck/src/type_check/opaque_types.rs b/compiler/rustc_borrowck/src/type_check/opaque_types.rs deleted file mode 100644 index 5a422483eef..00000000000 --- a/compiler/rustc_borrowck/src/type_check/opaque_types.rs +++ /dev/null @@ -1,333 +0,0 @@ -use std::iter; - -use rustc_data_structures::fx::FxIndexMap; -use rustc_middle::span_bug; -use rustc_middle::ty::{ - self, GenericArgKind, OpaqueHiddenType, OpaqueTypeKey, Ty, TyCtxt, TypeSuperVisitable, - TypeVisitable, TypeVisitableExt, TypeVisitor, fold_regions, -}; -use tracing::{debug, trace}; - -use super::{MemberConstraintSet, TypeChecker}; - -/// Once we're done with typechecking the body, we take all the opaque types -/// defined by this function and add their 'member constraints'. -pub(super) fn take_opaques_and_register_member_constraints<'tcx>( - typeck: &mut TypeChecker<'_, 'tcx>, -) -> FxIndexMap<OpaqueTypeKey<'tcx>, OpaqueHiddenType<'tcx>> { - let infcx = typeck.infcx; - // Annoying: to invoke `typeck.to_region_vid`, we need access to - // `typeck.constraints`, but we also want to be mutating - // `typeck.member_constraints`. For now, just swap out the value - // we want and replace at the end. - let mut member_constraints = std::mem::take(&mut typeck.constraints.member_constraints); - let opaque_types = infcx - .take_opaque_types() - .into_iter() - .map(|(opaque_type_key, hidden_type)| { - let hidden_type = infcx.resolve_vars_if_possible(hidden_type); - register_member_constraints( - typeck, - &mut member_constraints, - opaque_type_key, - hidden_type, - ); - trace!("finalized opaque type {:?} to {:#?}", opaque_type_key, hidden_type.ty.kind()); - if hidden_type.has_non_region_infer() { - span_bug!(hidden_type.span, "could not resolve {:?}", hidden_type.ty); - } - - // Convert all regions to nll vars. - let (opaque_type_key, hidden_type) = - fold_regions(infcx.tcx, (opaque_type_key, hidden_type), |r, _| { - ty::Region::new_var(infcx.tcx, typeck.to_region_vid(r)) - }); - - (opaque_type_key, hidden_type) - }) - .collect(); - assert!(typeck.constraints.member_constraints.is_empty()); - typeck.constraints.member_constraints = member_constraints; - opaque_types -} - -/// Given the map `opaque_types` containing the opaque -/// `impl Trait` types whose underlying, hidden types are being -/// inferred, this method adds constraints to the regions -/// appearing in those underlying hidden types to ensure that they -/// at least do not refer to random scopes within the current -/// function. These constraints are not (quite) sufficient to -/// guarantee that the regions are actually legal values; that -/// final condition is imposed after region inference is done. -/// -/// # The Problem -/// -/// Let's work through an example to explain how it works. Assume -/// the current function is as follows: -/// -/// ```text -/// fn foo<'a, 'b>(..) -> (impl Bar<'a>, impl Bar<'b>) -/// ``` -/// -/// Here, we have two `impl Trait` types whose values are being -/// inferred (the `impl Bar<'a>` and the `impl -/// Bar<'b>`). Conceptually, this is sugar for a setup where we -/// define underlying opaque types (`Foo1`, `Foo2`) and then, in -/// the return type of `foo`, we *reference* those definitions: -/// -/// ```text -/// type Foo1<'x> = impl Bar<'x>; -/// type Foo2<'x> = impl Bar<'x>; -/// fn foo<'a, 'b>(..) -> (Foo1<'a>, Foo2<'b>) { .. } -/// // ^^^^ ^^ -/// // | | -/// // | args -/// // def_id -/// ``` -/// -/// As indicating in the comments above, each of those references -/// is (in the compiler) basically generic parameters (`args`) -/// applied to the type of a suitable `def_id` (which identifies -/// `Foo1` or `Foo2`). -/// -/// Now, at this point in compilation, what we have done is to -/// replace each of the references (`Foo1<'a>`, `Foo2<'b>`) with -/// fresh inference variables C1 and C2. We wish to use the values -/// of these variables to infer the underlying types of `Foo1` and -/// `Foo2`. That is, this gives rise to higher-order (pattern) unification -/// constraints like: -/// -/// ```text -/// for<'a> (Foo1<'a> = C1) -/// for<'b> (Foo1<'b> = C2) -/// ``` -/// -/// For these equation to be satisfiable, the types `C1` and `C2` -/// can only refer to a limited set of regions. For example, `C1` -/// can only refer to `'static` and `'a`, and `C2` can only refer -/// to `'static` and `'b`. The job of this function is to impose that -/// constraint. -/// -/// Up to this point, C1 and C2 are basically just random type -/// inference variables, and hence they may contain arbitrary -/// regions. In fact, it is fairly likely that they do! Consider -/// this possible definition of `foo`: -/// -/// ```text -/// fn foo<'a, 'b>(x: &'a i32, y: &'b i32) -> (impl Bar<'a>, impl Bar<'b>) { -/// (&*x, &*y) -/// } -/// ``` -/// -/// Here, the values for the concrete types of the two impl -/// traits will include inference variables: -/// -/// ```text -/// &'0 i32 -/// &'1 i32 -/// ``` -/// -/// Ordinarily, the subtyping rules would ensure that these are -/// sufficiently large. But since `impl Bar<'a>` isn't a specific -/// type per se, we don't get such constraints by default. This -/// is where this function comes into play. It adds extra -/// constraints to ensure that all the regions which appear in the -/// inferred type are regions that could validly appear. -/// -/// This is actually a bit of a tricky constraint in general. We -/// want to say that each variable (e.g., `'0`) can only take on -/// values that were supplied as arguments to the opaque type -/// (e.g., `'a` for `Foo1<'a>`) or `'static`, which is always in -/// scope. We don't have a constraint quite of this kind in the current -/// region checker. -/// -/// # The Solution -/// -/// We generally prefer to make `<=` constraints, since they -/// integrate best into the region solver. To do that, we find the -/// "minimum" of all the arguments that appear in the args: that -/// is, some region which is less than all the others. In the case -/// of `Foo1<'a>`, that would be `'a` (it's the only choice, after -/// all). Then we apply that as a least bound to the variables -/// (e.g., `'a <= '0`). -/// -/// In some cases, there is no minimum. Consider this example: -/// -/// ```text -/// fn baz<'a, 'b>() -> impl Trait<'a, 'b> { ... } -/// ``` -/// -/// Here we would report a more complex "in constraint", like `'r -/// in ['a, 'b, 'static]` (where `'r` is some region appearing in -/// the hidden type). -/// -/// # Constrain regions, not the hidden concrete type -/// -/// Note that generating constraints on each region `Rc` is *not* -/// the same as generating an outlives constraint on `Tc` itself. -/// For example, if we had a function like this: -/// -/// ``` -/// # #![feature(type_alias_impl_trait)] -/// # fn main() {} -/// # trait Foo<'a> {} -/// # impl<'a, T> Foo<'a> for (&'a u32, T) {} -/// fn foo<'a, T>(x: &'a u32, y: T) -> impl Foo<'a> { -/// (x, y) -/// } -/// -/// // Equivalent to: -/// # mod dummy { use super::*; -/// type FooReturn<'a, T> = impl Foo<'a>; -/// #[define_opaque(FooReturn)] -/// fn foo<'a, T>(x: &'a u32, y: T) -> FooReturn<'a, T> { -/// (x, y) -/// } -/// # } -/// ``` -/// -/// then the hidden type `Tc` would be `(&'0 u32, T)` (where `'0` -/// is an inference variable). If we generated a constraint that -/// `Tc: 'a`, then this would incorrectly require that `T: 'a` -- -/// but this is not necessary, because the opaque type we -/// create will be allowed to reference `T`. So we only generate a -/// constraint that `'0: 'a`. -fn register_member_constraints<'tcx>( - typeck: &mut TypeChecker<'_, 'tcx>, - member_constraints: &mut MemberConstraintSet<'tcx, ty::RegionVid>, - opaque_type_key: OpaqueTypeKey<'tcx>, - OpaqueHiddenType { span, ty: hidden_ty }: OpaqueHiddenType<'tcx>, -) { - let tcx = typeck.tcx(); - let hidden_ty = typeck.infcx.resolve_vars_if_possible(hidden_ty); - debug!(?hidden_ty); - - let variances = tcx.variances_of(opaque_type_key.def_id); - debug!(?variances); - - // For a case like `impl Foo<'a, 'b>`, we would generate a constraint - // `'r in ['a, 'b, 'static]` for each region `'r` that appears in the - // hidden type (i.e., it must be equal to `'a`, `'b`, or `'static`). - // - // `conflict1` and `conflict2` are the two region bounds that we - // detected which were unrelated. They are used for diagnostics. - - // Create the set of choice regions: each region in the hidden - // type can be equal to any of the region parameters of the - // opaque type definition. - let fr_static = typeck.universal_regions.fr_static; - let choice_regions: Vec<_> = opaque_type_key - .args - .iter() - .enumerate() - .filter(|(i, _)| variances[*i] == ty::Invariant) - .filter_map(|(_, arg)| match arg.kind() { - GenericArgKind::Lifetime(r) => Some(typeck.to_region_vid(r)), - GenericArgKind::Type(_) | GenericArgKind::Const(_) => None, - }) - .chain(iter::once(fr_static)) - .collect(); - - // FIXME(#42940): This should use the `FreeRegionsVisitor`, but that's - // not currently sound until we have existential regions. - hidden_ty.visit_with(&mut ConstrainOpaqueTypeRegionVisitor { - tcx, - op: |r| { - member_constraints.add_member_constraint( - opaque_type_key, - hidden_ty, - span, - typeck.to_region_vid(r), - &choice_regions, - ) - }, - }); -} - -/// Visitor that requires that (almost) all regions in the type visited outlive -/// `least_region`. We cannot use `push_outlives_components` because regions in -/// closure signatures are not included in their outlives components. We need to -/// ensure all regions outlive the given bound so that we don't end up with, -/// say, `ReVar` appearing in a return type and causing ICEs when other -/// functions end up with region constraints involving regions from other -/// functions. -/// -/// We also cannot use `for_each_free_region` because for closures it includes -/// the regions parameters from the enclosing item. -/// -/// We ignore any type parameters because impl trait values are assumed to -/// capture all the in-scope type parameters. -struct ConstrainOpaqueTypeRegionVisitor<'tcx, OP: FnMut(ty::Region<'tcx>)> { - tcx: TyCtxt<'tcx>, - op: OP, -} - -impl<'tcx, OP> TypeVisitor<TyCtxt<'tcx>> for ConstrainOpaqueTypeRegionVisitor<'tcx, OP> -where - OP: FnMut(ty::Region<'tcx>), -{ - fn visit_region(&mut self, r: ty::Region<'tcx>) { - match r.kind() { - // ignore bound regions, keep visiting - ty::ReBound(_, _) => {} - _ => (self.op)(r), - } - } - - fn visit_ty(&mut self, ty: Ty<'tcx>) { - // We're only interested in types involving regions - if !ty.flags().intersects(ty::TypeFlags::HAS_FREE_REGIONS) { - return; - } - - match *ty.kind() { - ty::Closure(_, args) => { - // Skip lifetime parameters of the enclosing item(s) - - for upvar in args.as_closure().upvar_tys() { - upvar.visit_with(self); - } - args.as_closure().sig_as_fn_ptr_ty().visit_with(self); - } - - ty::CoroutineClosure(_, args) => { - // Skip lifetime parameters of the enclosing item(s) - - for upvar in args.as_coroutine_closure().upvar_tys() { - upvar.visit_with(self); - } - - args.as_coroutine_closure().signature_parts_ty().visit_with(self); - } - - ty::Coroutine(_, args) => { - // Skip lifetime parameters of the enclosing item(s) - // Also skip the witness type, because that has no free regions. - - for upvar in args.as_coroutine().upvar_tys() { - upvar.visit_with(self); - } - args.as_coroutine().return_ty().visit_with(self); - args.as_coroutine().yield_ty().visit_with(self); - args.as_coroutine().resume_ty().visit_with(self); - } - - ty::Alias(kind, ty::AliasTy { def_id, args, .. }) - if let Some(variances) = self.tcx.opt_alias_variances(kind, def_id) => - { - // Skip lifetime parameters that are not captured, since they do - // not need member constraints registered for them; we'll erase - // them (and hopefully in the future replace them with placeholders). - for (v, s) in std::iter::zip(variances, args.iter()) { - if *v != ty::Bivariant { - s.visit_with(self); - } - } - } - - _ => { - ty.super_visit_with(self); - } - } - } -} diff --git a/compiler/rustc_borrowck/src/type_check/relate_tys.rs b/compiler/rustc_borrowck/src/type_check/relate_tys.rs index 84ca9bad2c1..7ac2dff12f7 100644 --- a/compiler/rustc_borrowck/src/type_check/relate_tys.rs +++ b/compiler/rustc_borrowck/src/type_check/relate_tys.rs @@ -124,8 +124,13 @@ impl<'a, 'b, 'tcx> NllTypeRelating<'a, 'b, 'tcx> { // by using `ty_vid rel B` and then finally and end by equating `ty_vid` to // the opaque. let mut enable_subtyping = |ty, opaque_is_expected| { - let ty_vid = infcx.next_ty_var_id_in_universe(self.span(), ty::UniverseIndex::ROOT); - + // We create the fresh inference variable in the highest universe. + // In theory we could limit it to the highest universe in the args of + // the opaque but that isn't really worth the effort. + // + // We'll make sure that the opaque type can actually name everything + // in its hidden type later on. + let ty_vid = infcx.next_ty_vid(self.span()); let variance = if opaque_is_expected { self.ambient_variance } else { |