diff options
| -rw-r--r-- | compiler/rustc_typeck/src/check/wfcheck.rs | 81 |
1 files changed, 62 insertions, 19 deletions
diff --git a/compiler/rustc_typeck/src/check/wfcheck.rs b/compiler/rustc_typeck/src/check/wfcheck.rs index d6f983d5465..d18682f5b62 100644 --- a/compiler/rustc_typeck/src/check/wfcheck.rs +++ b/compiler/rustc_typeck/src/check/wfcheck.rs @@ -263,9 +263,24 @@ pub fn check_trait_item(tcx: TyCtxt<'_>, def_id: LocalDefId) { /// Require that the user writes where clauses on GATs for the implicit /// outlives bounds involving trait parameters in trait functions and /// lifetimes passed as GAT substs. See `self-outlives-lint` test. +/// +/// We use the following trait as an example throughout this function: +/// ```rust,ignore (this code fails due to this lint) +/// trait IntoIter { +/// type Iter<'a>: Iterator<Item = Self::Item<'a>>; +/// type Item<'a>; +/// fn into_iter<'a>(&'a self) -> Self::Iter<'a>; +/// } /// ``` fn check_gat_where_clauses(tcx: TyCtxt<'_>, associated_items: &[hir::TraitItemRef]) { + // Associates every GAT's def_id to a list of possibly missing bounds detected by this lint. let mut required_bounds_by_item = FxHashMap::default(); + + // Loop over all GATs together, because if this lint suggests adding a where-clause bound + // to one GAT, it might then require us to an additional bound on another GAT. + // In our `IntoIter` example, we discover a missing `Self: 'a` bound on `Iter<'a>`, which + // then in a second loop adds a `Self: 'a` bound to `Item` due to the relationship between + // those GATs. loop { let mut should_continue = false; for gat_item in associated_items { @@ -276,14 +291,18 @@ fn check_gat_where_clauses(tcx: TyCtxt<'_>, associated_items: &[hir::TraitItemRe continue; } let gat_generics = tcx.generics_of(gat_def_id); + // FIXME(jackh726): we can also warn in the more general case if gat_generics.params.is_empty() { continue; } + // Gather the bounds with which all other items inside of this trait constrain the GAT. + // This is calculated by taking the intersection of the bounds that each item + // constrains the GAT with individually. let mut new_required_bounds: Option<FxHashSet<ty::Predicate<'_>>> = None; for item in associated_items { let item_def_id = item.id.def_id; - // Skip our own GAT, since it would blow away the required bounds + // Skip our own GAT, since it does not constrain itself at all. if item_def_id == gat_def_id { continue; } @@ -292,7 +311,11 @@ fn check_gat_where_clauses(tcx: TyCtxt<'_>, associated_items: &[hir::TraitItemRe let param_env = tcx.param_env(item_def_id); let item_required_bounds = match item.kind { + // In our example, this corresponds to `into_iter` method hir::AssocItemKind::Fn { .. } => { + // For methods, we check the function signature's return type for any GATs + // to constrain. In the `into_iter` case, we see that the return type + // `Self::Iter<'a>` is a GAT we want to gather any potential missing bounds from. let sig: ty::FnSig<'_> = tcx.liberate_late_bound_regions( item_def_id.to_def_id(), tcx.fn_sig(item_def_id), @@ -302,11 +325,14 @@ fn check_gat_where_clauses(tcx: TyCtxt<'_>, associated_items: &[hir::TraitItemRe param_env, item_hir_id, sig.output(), + // We also assume that all of the function signature's parameter types + // are well formed. &sig.inputs().iter().copied().collect(), gat_def_id, gat_generics, ) } + // In our example, this corresponds to the `Iter` and `Item` associated types hir::AssocItemKind::Type => { // If our associated item is a GAT with missing bounds, add them to // the param-env here. This allows this GAT to propagate missing bounds @@ -316,6 +342,7 @@ fn check_gat_where_clauses(tcx: TyCtxt<'_>, associated_items: &[hir::TraitItemRe param_env, required_bounds_by_item.get(&item_def_id), ); + // FIXME(compiler-errors): Do we want to add a assoc ty default to the wf_tys? gather_gat_bounds( tcx, param_env, @@ -333,9 +360,11 @@ fn check_gat_where_clauses(tcx: TyCtxt<'_>, associated_items: &[hir::TraitItemRe }; if let Some(item_required_bounds) = item_required_bounds { - // Take the intersection of the new_required_bounds and the item_required_bounds - // for this item. This is why we use an Option<_>, since we need to distinguish - // the empty set of bounds from the uninitialized set of bounds. + // Take the intersection of the required bounds for this GAT, and + // the item_required_bounds which are the ones implied by just + // this item alone. + // This is why we use an Option<_>, since we need to distinguish + // the empty set of bounds from the _uninitialized_ set of bounds. if let Some(new_required_bounds) = &mut new_required_bounds { new_required_bounds.retain(|b| item_required_bounds.contains(b)); } else { @@ -346,14 +375,17 @@ fn check_gat_where_clauses(tcx: TyCtxt<'_>, associated_items: &[hir::TraitItemRe if let Some(new_required_bounds) = new_required_bounds { let required_bounds = required_bounds_by_item.entry(gat_def_id).or_default(); - if new_required_bounds != *required_bounds { - *required_bounds = new_required_bounds; + if new_required_bounds.into_iter().any(|p| required_bounds.insert(p)) { // Iterate until our required_bounds no longer change // Since they changed here, we should continue the loop should_continue = true; } } } + // We know that this loop will eventually halt, since we only set `should_continue` if the + // `required_bounds` for this item grows. Since we are not creating any new region or type + // variables, the set of all region and type bounds that we could ever insert are limited + // by the number of unique types and regions we observe in a given item. if !should_continue { break; } @@ -422,8 +454,7 @@ fn check_gat_where_clauses(tcx: TyCtxt<'_>, associated_items: &[hir::TraitItemRe } } -/// Add a new set of predicates to the caller_bounds of an existing param_env, -/// and normalize the param_env afterwards +/// Add a new set of predicates to the caller_bounds of an existing param_env. fn augment_param_env<'tcx>( tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>, @@ -444,6 +475,16 @@ fn augment_param_env<'tcx>( ty::ParamEnv::new(bounds, param_env.reveal(), param_env.constness()) } +/// We use the following trait as an example throughout this function. +/// Specifically, let's assume that `to_check` here is the return type +/// of `into_iter`, and the GAT we are checking this for is `Iter`. +/// ```rust,ignore (this code fails due to this lint) +/// trait IntoIter { +/// type Iter<'a>: Iterator<Item = Self::Item<'a>>; +/// type Item<'a>; +/// fn into_iter<'a>(&'a self) -> Self::Iter<'a>; +/// } +/// ``` fn gather_gat_bounds<'tcx, T: TypeFoldable<'tcx>>( tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>, @@ -453,13 +494,13 @@ fn gather_gat_bounds<'tcx, T: TypeFoldable<'tcx>>( gat_def_id: LocalDefId, gat_generics: &'tcx ty::Generics, ) -> Option<FxHashSet<ty::Predicate<'tcx>>> { - // The bounds we that we would require from this function + // The bounds we that we would require from `to_check` let mut bounds = FxHashSet::default(); let (regions, types) = GATSubstCollector::visit(tcx, gat_def_id.to_def_id(), to_check); // If both regions and types are empty, then this GAT isn't in the - // return type, and we shouldn't try to do clause analysis + // set of types we are checking, and we shouldn't try to do clause analysis // (particularly, doing so would end up with an empty set of clauses, // since the current method would require none, and we take the // intersection of requirements of all methods) @@ -474,18 +515,18 @@ fn gather_gat_bounds<'tcx, T: TypeFoldable<'tcx>>( if let ty::ReStatic = **region_a { continue; } - // For each region argument (e.g., 'a in our example), check for a - // relationship to the type arguments (e.g., Self). If there is an + // For each region argument (e.g., `'a` in our example), check for a + // relationship to the type arguments (e.g., `Self`). If there is an // outlives relationship (`Self: 'a`), then we want to ensure that is // reflected in a where clause on the GAT itself. for (ty, ty_idx) in &types { - // In our example, requires that Self: 'a + // In our example, requires that `Self: 'a` if ty_known_to_outlive(tcx, item_hir, param_env, &wf_tys, *ty, *region_a) { debug!(?ty_idx, ?region_a_idx); debug!("required clause: {} must outlive {}", ty, region_a); // Translate into the generic parameters of the GAT. In - // our example, the type was Self, which will also be - // Self in the GAT. + // our example, the type was `Self`, which will also be + // `Self` in the GAT. let ty_param = gat_generics.param_at(*ty_idx, tcx); let ty_param = tcx .mk_ty(ty::Param(ty::ParamTy { index: ty_param.index, name: ty_param.name })); @@ -507,11 +548,13 @@ fn gather_gat_bounds<'tcx, T: TypeFoldable<'tcx>>( } } - // For each region argument (e.g., 'a in our example), also check for a - // relationship to the other region arguments. If there is an - // outlives relationship, then we want to ensure that is - // reflected in a where clause on the GAT itself. + // For each region argument (e.g., `'a` in our example), also check for a + // relationship to the other region arguments. If there is an outlives + // relationship, then we want to ensure that is reflected in the where clause + // on the GAT itself. for (region_b, region_b_idx) in ®ions { + // Again, skip `'static` because it outlives everything. Also, we trivially + // know that a region outlives itself. if ty::ReStatic == **region_b || region_a == region_b { continue; } |