X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=compiler%2Frustc_hir_analysis%2Fsrc%2Fcollect%2Flifetimes.rs;h=6ee7aa9cdac6b8ebc65b56a45732131aedc85768;hb=6c95805a34a1a3a9c52a3bea7f680373ee07290c;hp=3d07f3fbc674dbb3d32ba541a95cf0c5c0309698;hpb=19c780ab1361efdb2a416f035e87dd9140d63901;p=rust.git diff --git a/compiler/rustc_hir_analysis/src/collect/lifetimes.rs b/compiler/rustc_hir_analysis/src/collect/lifetimes.rs index 3d07f3fbc67..6ee7aa9cdac 100644 --- a/compiler/rustc_hir_analysis/src/collect/lifetimes.rs +++ b/compiler/rustc_hir_analysis/src/collect/lifetimes.rs @@ -18,7 +18,7 @@ use rustc_middle::hir::map::Map; use rustc_middle::hir::nested_filter; use rustc_middle::middle::resolve_lifetime::*; -use rustc_middle::ty::{self, DefIdTree, TyCtxt}; +use rustc_middle::ty::{self, DefIdTree, TyCtxt, TypeSuperVisitable, TypeVisitor}; use rustc_span::def_id::DefId; use rustc_span::symbol::{sym, Ident}; use rustc_span::Span; @@ -94,11 +94,6 @@ struct LifetimeContext<'a, 'tcx> { tcx: TyCtxt<'tcx>, map: &'a mut NamedRegionMap, scope: ScopeRef<'a>, - - /// Indicates that we only care about the definition of a trait. This should - /// be false if the `Item` we are resolving lifetimes for is not a trait or - /// we eventually need lifetimes resolve for trait items. - trait_definition_only: bool, } #[derive(Debug)] @@ -166,7 +161,9 @@ enum Scope<'a> { s: ScopeRef<'a>, }, - Root, + Root { + opt_parent_item: Option, + }, } #[derive(Copy, Clone, Debug)] @@ -214,95 +211,58 @@ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { .field("s", &"..") .finish(), Scope::TraitRefBoundary { s: _ } => f.debug_struct("TraitRefBoundary").finish(), - Scope::Root => f.debug_struct("Root").finish(), + Scope::Root { opt_parent_item } => { + f.debug_struct("Root").field("opt_parent_item", &opt_parent_item).finish() + } } } } type ScopeRef<'a> = &'a Scope<'a>; -const ROOT_SCOPE: ScopeRef<'static> = &Scope::Root; - pub(crate) fn provide(providers: &mut ty::query::Providers) { *providers = ty::query::Providers { - resolve_lifetimes_trait_definition, resolve_lifetimes, - named_region_map: |tcx, id| resolve_lifetimes_for(tcx, id).defs.get(&id), + named_region_map: |tcx, id| tcx.resolve_lifetimes(id).defs.get(&id), is_late_bound_map, object_lifetime_default, - late_bound_vars_map: |tcx, id| resolve_lifetimes_for(tcx, id).late_bound_vars.get(&id), + late_bound_vars_map: |tcx, id| tcx.resolve_lifetimes(id).late_bound_vars.get(&id), ..*providers }; } -/// Like `resolve_lifetimes`, but does not resolve lifetimes for trait items. -/// Also does not generate any diagnostics. -/// -/// This is ultimately a subset of the `resolve_lifetimes` work. It effectively -/// resolves lifetimes only within the trait "header" -- that is, the trait -/// and supertrait list. In contrast, `resolve_lifetimes` resolves all the -/// lifetimes within the trait and its items. There is room to refactor this, -/// for example to resolve lifetimes for each trait item in separate queries, -/// but it's convenient to do the entire trait at once because the lifetimes -/// from the trait definition are in scope within the trait items as well. -/// -/// The reason for this separate call is to resolve what would otherwise -/// be a cycle. Consider this example: -/// -/// ```ignore UNSOLVED (maybe @jackh726 knows what lifetime parameter to give Sub) -/// trait Base<'a> { -/// type BaseItem; -/// } -/// trait Sub<'b>: for<'a> Base<'a> { -/// type SubItem: Sub; -/// } -/// ``` -/// -/// When we resolve `Sub` and all its items, we also have to resolve `Sub`. -/// To figure out the index of `'b`, we have to know about the supertraits -/// of `Sub` so that we can determine that the `for<'a>` will be in scope. -/// (This is because we -- currently at least -- flatten all the late-bound -/// lifetimes into a single binder.) This requires us to resolve the -/// *trait definition* of `Sub`; basically just enough lifetime information -/// to look at the supertraits. -#[instrument(level = "debug", skip(tcx))] -fn resolve_lifetimes_trait_definition( - tcx: TyCtxt<'_>, - local_def_id: LocalDefId, -) -> ResolveLifetimes { - convert_named_region_map(do_resolve(tcx, local_def_id, true)) -} - /// Computes the `ResolveLifetimes` map that contains data for an entire `Item`. /// You should not read the result of this query directly, but rather use /// `named_region_map`, `is_late_bound_map`, etc. #[instrument(level = "debug", skip(tcx))] -fn resolve_lifetimes(tcx: TyCtxt<'_>, local_def_id: LocalDefId) -> ResolveLifetimes { - convert_named_region_map(do_resolve(tcx, local_def_id, false)) -} - -fn do_resolve( - tcx: TyCtxt<'_>, - local_def_id: LocalDefId, - trait_definition_only: bool, -) -> NamedRegionMap { - let item = tcx.hir().expect_item(local_def_id); +fn resolve_lifetimes(tcx: TyCtxt<'_>, local_def_id: hir::OwnerId) -> ResolveLifetimes { let mut named_region_map = NamedRegionMap { defs: Default::default(), late_bound_vars: Default::default() }; let mut visitor = LifetimeContext { tcx, map: &mut named_region_map, - scope: ROOT_SCOPE, - trait_definition_only, + scope: &Scope::Root { opt_parent_item: None }, }; - visitor.visit_item(item); - - named_region_map -} + match tcx.hir().owner(local_def_id) { + hir::OwnerNode::Item(item) => visitor.visit_item(item), + hir::OwnerNode::ForeignItem(item) => visitor.visit_foreign_item(item), + hir::OwnerNode::TraitItem(item) => { + let scope = + Scope::Root { opt_parent_item: Some(tcx.local_parent(item.owner_id.def_id)) }; + visitor.scope = &scope; + visitor.visit_trait_item(item) + } + hir::OwnerNode::ImplItem(item) => { + let scope = + Scope::Root { opt_parent_item: Some(tcx.local_parent(item.owner_id.def_id)) }; + visitor.scope = &scope; + visitor.visit_impl_item(item) + } + hir::OwnerNode::Crate(_) => {} + } -fn convert_named_region_map(named_region_map: NamedRegionMap) -> ResolveLifetimes { let mut rl = ResolveLifetimes::default(); for (hir_id, v) in named_region_map.defs { @@ -319,53 +279,6 @@ fn convert_named_region_map(named_region_map: NamedRegionMap) -> ResolveLifetime rl } -/// Given `any` owner (structs, traits, trait methods, etc.), does lifetime resolution. -/// There are two important things this does. -/// First, we have to resolve lifetimes for -/// the entire *`Item`* that contains this owner, because that's the largest "scope" -/// where we can have relevant lifetimes. -/// Second, if we are asking for lifetimes in a trait *definition*, we use `resolve_lifetimes_trait_definition` -/// instead of `resolve_lifetimes`, which does not descend into the trait items and does not emit diagnostics. -/// This allows us to avoid cycles. Importantly, if we ask for lifetimes for lifetimes that have an owner -/// other than the trait itself (like the trait methods or associated types), then we just use the regular -/// `resolve_lifetimes`. -fn resolve_lifetimes_for<'tcx>(tcx: TyCtxt<'tcx>, def_id: hir::OwnerId) -> &'tcx ResolveLifetimes { - let item_id = item_for(tcx, def_id.def_id); - let local_def_id = item_id.owner_id.def_id; - if item_id.owner_id == def_id { - let item = tcx.hir().item(item_id); - match item.kind { - hir::ItemKind::Trait(..) => tcx.resolve_lifetimes_trait_definition(local_def_id), - _ => tcx.resolve_lifetimes(local_def_id), - } - } else { - tcx.resolve_lifetimes(local_def_id) - } -} - -/// Finds the `Item` that contains the given `LocalDefId` -fn item_for(tcx: TyCtxt<'_>, local_def_id: LocalDefId) -> hir::ItemId { - match tcx.hir().find_by_def_id(local_def_id) { - Some(Node::Item(item)) => { - return item.item_id(); - } - _ => {} - } - let item = { - let hir_id = tcx.hir().local_def_id_to_hir_id(local_def_id); - let mut parent_iter = tcx.hir().parent_iter(hir_id); - loop { - let node = parent_iter.next().map(|n| n.1); - match node { - Some(hir::Node::Item(item)) => break item.item_id(), - Some(hir::Node::Crate(_)) | None => bug!("Called `item_for` on an Item."), - _ => {} - } - } - }; - item -} - fn late_region_as_bound_region<'tcx>(tcx: TyCtxt<'tcx>, region: &Region) -> ty::BoundVariableKind { match region { Region::LateBound(_, _, def_id) => { @@ -383,7 +296,7 @@ fn poly_trait_ref_binder_info(&mut self) -> (Vec, BinderS let mut supertrait_lifetimes = vec![]; loop { match scope { - Scope::Body { .. } | Scope::Root => { + Scope::Body { .. } | Scope::Root { .. } => { break (vec![], BinderScopeType::Normal); } @@ -414,21 +327,12 @@ fn poly_trait_ref_binder_info(&mut self) -> (Vec, BinderS } } impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> { - type NestedFilter = nested_filter::All; + type NestedFilter = nested_filter::OnlyBodies; fn nested_visit_map(&mut self) -> Self::Map { self.tcx.hir() } - // We want to nest trait/impl items in their parent, but nothing else. - fn visit_nested_item(&mut self, _: hir::ItemId) {} - - fn visit_trait_item_ref(&mut self, ii: &'tcx hir::TraitItemRef) { - if !self.trait_definition_only { - intravisit::walk_trait_item_ref(self, ii) - } - } - fn visit_nested_body(&mut self, body: hir::BodyId) { let body = self.tcx.hir().body(body); self.with(Scope::Body { id: body.id(), s: self.scope }, |this| { @@ -548,7 +452,9 @@ fn visit_item(&mut self, item: &'tcx hir::Item<'tcx>) { intravisit::walk_item(this, item) }); } - hir::ItemKind::OpaqueTy(hir::OpaqueTy { .. }) => { + hir::ItemKind::OpaqueTy(hir::OpaqueTy { + origin: hir::OpaqueTyOrigin::TyAlias, .. + }) => { // Opaque types are visited when we visit the // `TyKind::OpaqueDef`, so that they have the lifetimes from // their parent opaque_ty in scope. @@ -557,34 +463,53 @@ fn visit_item(&mut self, item: &'tcx hir::Item<'tcx>) { // their owner, we can keep going until we find the Item that owns that. We then // conservatively add all resolved lifetimes. Otherwise we run into problems in // cases like `type Foo<'a> = impl Bar`. - for (_hir_id, node) in self.tcx.hir().parent_iter(item.owner_id.into()) { - match node { - hir::Node::Item(parent_item) => { - let resolved_lifetimes: &ResolveLifetimes = self.tcx.resolve_lifetimes( - item_for(self.tcx, parent_item.owner_id.def_id).owner_id.def_id, - ); - // We need to add *all* deps, since opaque tys may want them from *us* - for (&owner, defs) in resolved_lifetimes.defs.iter() { - defs.iter().for_each(|(&local_id, region)| { - self.map.defs.insert(hir::HirId { owner, local_id }, *region); - }); - } - for (&owner, late_bound_vars) in - resolved_lifetimes.late_bound_vars.iter() - { - late_bound_vars.iter().for_each(|(&local_id, late_bound_vars)| { - self.record_late_bound_vars( - hir::HirId { owner, local_id }, - late_bound_vars.clone(), - ); - }); - } - break; + let parent_item = self.tcx.hir().get_parent_item(item.hir_id()); + let resolved_lifetimes: &ResolveLifetimes = self.tcx.resolve_lifetimes(parent_item); + // We need to add *all* deps, since opaque tys may want them from *us* + for (&owner, defs) in resolved_lifetimes.defs.iter() { + defs.iter().for_each(|(&local_id, region)| { + self.map.defs.insert(hir::HirId { owner, local_id }, *region); + }); + } + for (&owner, late_bound_vars) in resolved_lifetimes.late_bound_vars.iter() { + late_bound_vars.iter().for_each(|(&local_id, late_bound_vars)| { + self.record_late_bound_vars( + hir::HirId { owner, local_id }, + late_bound_vars.clone(), + ); + }); + } + } + hir::ItemKind::OpaqueTy(hir::OpaqueTy { + origin: hir::OpaqueTyOrigin::FnReturn(_) | hir::OpaqueTyOrigin::AsyncFn(_), + generics, + .. + }) => { + // We want to start our early-bound indices at the end of the parent scope, + // not including any parent `impl Trait`s. + let mut lifetimes = FxIndexMap::default(); + debug!(?generics.params); + for param in generics.params { + match param.kind { + GenericParamKind::Lifetime { .. } => { + let (def_id, reg) = Region::early(self.tcx.hir(), ¶m); + lifetimes.insert(def_id, reg); } - hir::Node::Crate(_) => bug!("No Item about an OpaqueTy"), - _ => {} + GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => {} } } + + let scope = Scope::Binder { + hir_id: item.hir_id(), + lifetimes, + s: self.scope, + scope_type: BinderScopeType::Normal, + where_bound_origin: None, + }; + self.with(scope, |this| { + let scope = Scope::TraitRefBoundary { s: this.scope }; + this.with(scope, |this| intravisit::walk_item(this, item)) + }); } hir::ItemKind::TyAlias(_, ref generics) | hir::ItemKind::Enum(_, ref generics) @@ -609,7 +534,7 @@ fn visit_item(&mut self, item: &'tcx hir::Item<'tcx>) { hir_id: item.hir_id(), lifetimes, scope_type: BinderScopeType::Normal, - s: ROOT_SCOPE, + s: self.scope, where_bound_origin: None, }; self.with(scope, |this| { @@ -712,7 +637,7 @@ fn visit_ty(&mut self, ty: &'tcx hir::Ty<'tcx>) { // ^ ^ this gets resolved in the scope of // the opaque_ty generics let opaque_ty = self.tcx.hir().item(item_id); - let (generics, bounds) = match opaque_ty.kind { + match opaque_ty.kind { hir::ItemKind::OpaqueTy(hir::OpaqueTy { origin: hir::OpaqueTyOrigin::TyAlias, .. @@ -733,10 +658,8 @@ fn visit_ty(&mut self, ty: &'tcx hir::Ty<'tcx>) { } hir::ItemKind::OpaqueTy(hir::OpaqueTy { origin: hir::OpaqueTyOrigin::FnReturn(..) | hir::OpaqueTyOrigin::AsyncFn(..), - ref generics, - bounds, .. - }) => (generics, bounds), + }) => {} ref i => bug!("`impl Trait` pointed to non-opaque type?? {:#?}", i), }; @@ -766,65 +689,28 @@ fn visit_ty(&mut self, ty: &'tcx hir::Ty<'tcx>) { // Ensure that the parent of the def is an item, not HRTB let parent_id = self.tcx.hir().get_parent_node(hir_id); if !parent_id.is_owner() { - if !self.trait_definition_only { - struct_span_err!( - self.tcx.sess, - lifetime.span, - E0657, - "`impl Trait` can only capture lifetimes \ - bound at the fn or impl level" - ) - .emit(); - } + struct_span_err!( + self.tcx.sess, + lifetime.span, + E0657, + "`impl Trait` can only capture lifetimes bound at the fn or impl level" + ) + .emit(); self.uninsert_lifetime_on_error(lifetime, def.unwrap()); } if let hir::Node::Item(hir::Item { kind: hir::ItemKind::OpaqueTy { .. }, .. }) = self.tcx.hir().get(parent_id) { - if !self.trait_definition_only { - let mut err = self.tcx.sess.struct_span_err( - lifetime.span, - "higher kinded lifetime bounds on nested opaque types are not supported yet", - ); - err.span_note(self.tcx.def_span(def_id), "lifetime declared here"); - err.emit(); - } + let mut err = self.tcx.sess.struct_span_err( + lifetime.span, + "higher kinded lifetime bounds on nested opaque types are not supported yet", + ); + err.span_note(self.tcx.def_span(def_id), "lifetime declared here"); + err.emit(); self.uninsert_lifetime_on_error(lifetime, def.unwrap()); } } - - // We want to start our early-bound indices at the end of the parent scope, - // not including any parent `impl Trait`s. - let mut lifetimes = FxIndexMap::default(); - debug!(?generics.params); - for param in generics.params { - match param.kind { - GenericParamKind::Lifetime { .. } => { - let (def_id, reg) = Region::early(self.tcx.hir(), ¶m); - lifetimes.insert(def_id, reg); - } - GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => {} - } - } - self.record_late_bound_vars(ty.hir_id, vec![]); - - let scope = Scope::Binder { - hir_id: ty.hir_id, - lifetimes, - s: self.scope, - scope_type: BinderScopeType::Normal, - where_bound_origin: None, - }; - self.with(scope, |this| { - let scope = Scope::TraitRefBoundary { s: this.scope }; - this.with(scope, |this| { - this.visit_generics(generics); - for bound in bounds { - this.visit_param_bound(bound); - } - }) - }); } _ => intravisit::walk_ty(self, ty), } @@ -1193,12 +1079,7 @@ fn with(&mut self, wrap_scope: Scope<'_>, f: F) F: for<'b> FnOnce(&mut LifetimeContext<'b, 'tcx>), { let LifetimeContext { tcx, map, .. } = self; - let mut this = LifetimeContext { - tcx: *tcx, - map, - scope: &wrap_scope, - trait_definition_only: self.trait_definition_only, - }; + let mut this = LifetimeContext { tcx: *tcx, map, scope: &wrap_scope }; let span = debug_span!("scope", scope = ?TruncatedScopeDebug(&this.scope)); { let _enter = span.enter(); @@ -1303,7 +1184,13 @@ fn resolve_lifetime_ref( scope = s; } - Scope::Root => { + Scope::Root { opt_parent_item } => { + if let Some(parent_item) = opt_parent_item + && let parent_generics = self.tcx.generics_of(parent_item) + && parent_generics.param_def_id_to_index.contains_key(®ion_def_id.to_def_id()) + { + break Some(Region::EarlyBound(region_def_id.to_def_id())); + } break None; } @@ -1417,7 +1304,7 @@ fn resolve_lifetime_ref( err.emit(); return; } - Scope::Root => break, + Scope::Root { .. } => break, Scope::Binder { s, .. } | Scope::Body { s, .. } | Scope::Elision { s, .. } @@ -1495,7 +1382,7 @@ fn visit_segment_args( let mut scope = self.scope; loop { match *scope { - Scope::Root => break false, + Scope::Root { .. } => break false, Scope::Body { .. } => break true, @@ -1732,7 +1619,7 @@ fn resolve_object_lifetime_default(&mut self, lifetime_ref: &'tcx hir::Lifetime) scope = s; } - Scope::Root | Scope::Elision { .. } => break Region::Static, + Scope::Root { .. } | Scope::Elision { .. } => break Region::Static, Scope::Body { .. } | Scope::ObjectLifetimeDefault { lifetime: None, .. } => return, @@ -1781,7 +1668,7 @@ fn is_late_bound_map(tcx: TyCtxt<'_>, def_id: LocalDefId) -> Option<&FxIndexSet< let mut late_bound = FxIndexSet::default(); - let mut constrained_by_input = ConstrainedCollector::default(); + let mut constrained_by_input = ConstrainedCollector { regions: Default::default(), tcx }; for arg_ty in decl.inputs { constrained_by_input.visit_ty(arg_ty); } @@ -1834,12 +1721,65 @@ fn is_late_bound_map(tcx: TyCtxt<'_>, def_id: LocalDefId) -> Option<&FxIndexSet< debug!(?late_bound); return Some(tcx.arena.alloc(late_bound)); - #[derive(Default)] - struct ConstrainedCollector { + /// Visits a `ty::Ty` collecting information about what generic parameters are constrained. + /// + /// The visitor does not operate on `hir::Ty` so that it can be called on the rhs of a `type Alias<...> = ...;` + /// which may live in a separate crate so there would not be any hir available. Instead we use the `type_of` + /// query to obtain a `ty::Ty` which will be present even in cross crate scenarios. It also naturally + /// handles cycle detection as we go through the query system. + /// + /// This is necessary in the first place for the following case: + /// ``` + /// type Alias<'a, T> = >::Assoc; + /// fn foo<'a>(_: Alias<'a, ()>) -> Alias<'a, ()> { ... } + /// ``` + /// + /// If we conservatively considered `'a` unconstrained then we could break users who had written code before + /// we started correctly handling aliases. If we considered `'a` constrained then it would become late bound + /// causing an error during astconv as the `'a` is not constrained by the input type `<() as Trait<'a>>::Assoc` + /// but appears in the output type `<() as Trait<'a>>::Assoc`. + /// + /// We must therefore "look into" the `Alias` to see whether we should consider `'a` constrained or not. + /// + /// See #100508 #85533 #47511 for additional context + struct ConstrainedCollectorPostAstConv { + arg_is_constrained: Box<[bool]>, + } + + use std::ops::ControlFlow; + use ty::Ty; + impl<'tcx> TypeVisitor<'tcx> for ConstrainedCollectorPostAstConv { + fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow { + match t.kind() { + ty::Param(param_ty) => { + self.arg_is_constrained[param_ty.index as usize] = true; + } + ty::Projection(_) => return ControlFlow::Continue(()), + _ => (), + } + t.super_visit_with(self) + } + + fn visit_const(&mut self, _: ty::Const<'tcx>) -> ControlFlow { + ControlFlow::Continue(()) + } + + fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow { + debug!("r={:?}", r.kind()); + if let ty::RegionKind::ReEarlyBound(region) = r.kind() { + self.arg_is_constrained[region.index as usize] = true; + } + + ControlFlow::Continue(()) + } + } + + struct ConstrainedCollector<'tcx> { + tcx: TyCtxt<'tcx>, regions: FxHashSet, } - impl<'v> Visitor<'v> for ConstrainedCollector { + impl<'v> Visitor<'v> for ConstrainedCollector<'_> { fn visit_ty(&mut self, ty: &'v hir::Ty<'v>) { match ty.kind { hir::TyKind::Path( @@ -1850,6 +1790,47 @@ fn visit_ty(&mut self, ty: &'v hir::Ty<'v>) { // (defined above) } + hir::TyKind::Path(hir::QPath::Resolved( + None, + hir::Path { res: Res::Def(DefKind::TyAlias, alias_def), segments, span }, + )) => { + // See comments on `ConstrainedCollectorPostAstConv` for why this arm does not just consider + // substs to be unconstrained. + let generics = self.tcx.generics_of(alias_def); + let mut walker = ConstrainedCollectorPostAstConv { + arg_is_constrained: vec![false; generics.params.len()].into_boxed_slice(), + }; + walker.visit_ty(self.tcx.type_of(alias_def)); + + match segments.last() { + Some(hir::PathSegment { args: Some(args), .. }) => { + let tcx = self.tcx; + for constrained_arg in + args.args.iter().enumerate().flat_map(|(n, arg)| { + match walker.arg_is_constrained.get(n) { + Some(true) => Some(arg), + Some(false) => None, + None => { + tcx.sess.delay_span_bug( + *span, + format!( + "Incorrect generic arg count for alias {:?}", + alias_def + ), + ); + None + } + } + }) + { + self.visit_generic_arg(constrained_arg); + } + } + Some(_) => (), + None => bug!("Path with no segments or self type"), + } + } + hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) => { // consider only the lifetimes on the final // segment; I am not sure it's even currently