rustc_hir_analysis/collect/
item_bounds.rs
1use rustc_data_structures::fx::{FxIndexMap, FxIndexSet};
2use rustc_hir as hir;
3use rustc_infer::traits::util;
4use rustc_middle::ty::{
5 self, GenericArgs, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt,
6 Upcast, shift_vars,
7};
8use rustc_middle::{bug, span_bug};
9use rustc_span::Span;
10use rustc_span::def_id::{DefId, LocalDefId};
11use tracing::{debug, instrument};
12
13use super::ItemCtxt;
14use super::predicates_of::assert_only_contains_predicates_from;
15use crate::hir_ty_lowering::{HirTyLowerer, PredicateFilter};
16
17fn associated_type_bounds<'tcx>(
25 tcx: TyCtxt<'tcx>,
26 assoc_item_def_id: LocalDefId,
27 hir_bounds: &'tcx [hir::GenericBound<'tcx>],
28 span: Span,
29 filter: PredicateFilter,
30) -> &'tcx [(ty::Clause<'tcx>, Span)] {
31 ty::print::with_reduced_queries!({
32 let item_ty = Ty::new_projection_from_args(
33 tcx,
34 assoc_item_def_id.to_def_id(),
35 GenericArgs::identity_for_item(tcx, assoc_item_def_id),
36 );
37
38 let icx = ItemCtxt::new(tcx, assoc_item_def_id);
39 let mut bounds = Vec::new();
40 icx.lowerer().lower_bounds(item_ty, hir_bounds, &mut bounds, ty::List::empty(), filter);
41 match filter {
43 PredicateFilter::All
44 | PredicateFilter::SelfOnly
45 | PredicateFilter::SelfTraitThatDefines(_)
46 | PredicateFilter::SelfAndAssociatedTypeBounds => {
47 icx.lowerer().add_sized_bound(&mut bounds, item_ty, hir_bounds, None, span);
48 }
49 PredicateFilter::ConstIfConst | PredicateFilter::SelfConstIfConst => {}
51 }
52
53 let trait_def_id = tcx.local_parent(assoc_item_def_id);
54 let trait_predicates = tcx.trait_explicit_predicates_and_bounds(trait_def_id);
55
56 let item_trait_ref = ty::TraitRef::identity(tcx, tcx.parent(assoc_item_def_id.to_def_id()));
57 let bounds_from_parent =
58 trait_predicates.predicates.iter().copied().filter_map(|(clause, span)| {
59 remap_gat_vars_and_recurse_into_nested_projections(
60 tcx,
61 filter,
62 item_trait_ref,
63 assoc_item_def_id,
64 span,
65 clause,
66 )
67 });
68
69 let all_bounds = tcx.arena.alloc_from_iter(bounds.into_iter().chain(bounds_from_parent));
70 debug!(
71 "associated_type_bounds({}) = {:?}",
72 tcx.def_path_str(assoc_item_def_id.to_def_id()),
73 all_bounds
74 );
75
76 assert_only_contains_predicates_from(filter, all_bounds, item_ty);
77
78 all_bounds
79 })
80}
81
82fn remap_gat_vars_and_recurse_into_nested_projections<'tcx>(
96 tcx: TyCtxt<'tcx>,
97 filter: PredicateFilter,
98 item_trait_ref: ty::TraitRef<'tcx>,
99 assoc_item_def_id: LocalDefId,
100 span: Span,
101 clause: ty::Clause<'tcx>,
102) -> Option<(ty::Clause<'tcx>, Span)> {
103 let mut clause_ty = match clause.kind().skip_binder() {
104 ty::ClauseKind::Trait(tr) => tr.self_ty(),
105 ty::ClauseKind::Projection(proj) => proj.projection_term.self_ty(),
106 ty::ClauseKind::TypeOutlives(outlives) => outlives.0,
107 _ => return None,
108 };
109
110 let gat_vars = loop {
111 if let ty::Alias(ty::Projection, alias_ty) = *clause_ty.kind() {
112 if alias_ty.trait_ref(tcx) == item_trait_ref
113 && alias_ty.def_id == assoc_item_def_id.to_def_id()
114 {
115 break &alias_ty.args[item_trait_ref.args.len()..];
118 } else {
119 match filter {
121 PredicateFilter::All => {}
122 PredicateFilter::SelfOnly => {
123 return None;
124 }
125 PredicateFilter::SelfTraitThatDefines(_)
126 | PredicateFilter::SelfConstIfConst
127 | PredicateFilter::SelfAndAssociatedTypeBounds
128 | PredicateFilter::ConstIfConst => {
129 unreachable!(
130 "invalid predicate filter for \
131 `remap_gat_vars_and_recurse_into_nested_projections`"
132 )
133 }
134 }
135
136 clause_ty = alias_ty.self_ty();
137 continue;
138 }
139 }
140
141 return None;
142 };
143
144 if gat_vars.is_empty() {
146 return Some((clause, span));
147 }
148
149 let mut mapping = FxIndexMap::default();
152 let generics = tcx.generics_of(assoc_item_def_id);
153 for (param, var) in std::iter::zip(&generics.own_params, gat_vars) {
154 let existing = match var.unpack() {
155 ty::GenericArgKind::Lifetime(re) => {
156 if let ty::RegionKind::ReBound(ty::INNERMOST, bv) = re.kind() {
157 mapping.insert(bv.var, tcx.mk_param_from_def(param))
158 } else {
159 return None;
160 }
161 }
162 ty::GenericArgKind::Type(ty) => {
163 if let ty::Bound(ty::INNERMOST, bv) = *ty.kind() {
164 mapping.insert(bv.var, tcx.mk_param_from_def(param))
165 } else {
166 return None;
167 }
168 }
169 ty::GenericArgKind::Const(ct) => {
170 if let ty::ConstKind::Bound(ty::INNERMOST, bv) = ct.kind() {
171 mapping.insert(bv, tcx.mk_param_from_def(param))
172 } else {
173 return None;
174 }
175 }
176 };
177
178 if existing.is_some() {
179 return None;
180 }
181 }
182
183 let mut folder =
186 MapAndCompressBoundVars { tcx, binder: ty::INNERMOST, still_bound_vars: vec![], mapping };
187 let pred = clause.kind().skip_binder().fold_with(&mut folder);
188
189 Some((
190 ty::Binder::bind_with_vars(pred, tcx.mk_bound_variable_kinds(&folder.still_bound_vars))
191 .upcast(tcx),
192 span,
193 ))
194}
195
196struct MapAndCompressBoundVars<'tcx> {
203 tcx: TyCtxt<'tcx>,
204 binder: ty::DebruijnIndex,
206 still_bound_vars: Vec<ty::BoundVariableKind>,
209 mapping: FxIndexMap<ty::BoundVar, ty::GenericArg<'tcx>>,
213}
214
215impl<'tcx> TypeFolder<TyCtxt<'tcx>> for MapAndCompressBoundVars<'tcx> {
216 fn cx(&self) -> TyCtxt<'tcx> {
217 self.tcx
218 }
219
220 fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T>
221 where
222 ty::Binder<'tcx, T>: TypeSuperFoldable<TyCtxt<'tcx>>,
223 {
224 self.binder.shift_in(1);
225 let out = t.super_fold_with(self);
226 self.binder.shift_out(1);
227 out
228 }
229
230 fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
231 if !ty.has_bound_vars() {
232 return ty;
233 }
234
235 if let ty::Bound(binder, old_bound) = *ty.kind()
236 && self.binder == binder
237 {
238 let mapped = if let Some(mapped) = self.mapping.get(&old_bound.var) {
239 mapped.expect_ty()
240 } else {
241 let var = ty::BoundVar::from_usize(self.still_bound_vars.len());
244 self.still_bound_vars.push(ty::BoundVariableKind::Ty(old_bound.kind));
245 let mapped = Ty::new_bound(
246 self.tcx,
247 ty::INNERMOST,
248 ty::BoundTy { var, kind: old_bound.kind },
249 );
250 self.mapping.insert(old_bound.var, mapped.into());
251 mapped
252 };
253
254 shift_vars(self.tcx, mapped, self.binder.as_u32())
255 } else {
256 ty.super_fold_with(self)
257 }
258 }
259
260 fn fold_region(&mut self, re: ty::Region<'tcx>) -> ty::Region<'tcx> {
261 if let ty::ReBound(binder, old_bound) = re.kind()
262 && self.binder == binder
263 {
264 let mapped = if let Some(mapped) = self.mapping.get(&old_bound.var) {
265 mapped.expect_region()
266 } else {
267 let var = ty::BoundVar::from_usize(self.still_bound_vars.len());
268 self.still_bound_vars.push(ty::BoundVariableKind::Region(old_bound.kind));
269 let mapped = ty::Region::new_bound(
270 self.tcx,
271 ty::INNERMOST,
272 ty::BoundRegion { var, kind: old_bound.kind },
273 );
274 self.mapping.insert(old_bound.var, mapped.into());
275 mapped
276 };
277
278 shift_vars(self.tcx, mapped, self.binder.as_u32())
279 } else {
280 re
281 }
282 }
283
284 fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
285 if !ct.has_bound_vars() {
286 return ct;
287 }
288
289 if let ty::ConstKind::Bound(binder, old_var) = ct.kind()
290 && self.binder == binder
291 {
292 let mapped = if let Some(mapped) = self.mapping.get(&old_var) {
293 mapped.expect_const()
294 } else {
295 let var = ty::BoundVar::from_usize(self.still_bound_vars.len());
296 self.still_bound_vars.push(ty::BoundVariableKind::Const);
297 let mapped = ty::Const::new_bound(self.tcx, ty::INNERMOST, var);
298 self.mapping.insert(old_var, mapped.into());
299 mapped
300 };
301
302 shift_vars(self.tcx, mapped, self.binder.as_u32())
303 } else {
304 ct.super_fold_with(self)
305 }
306 }
307
308 fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
309 if !p.has_bound_vars() { p } else { p.super_fold_with(self) }
310 }
311}
312
313#[instrument(level = "trace", skip(tcx, item_ty))]
318fn opaque_type_bounds<'tcx>(
319 tcx: TyCtxt<'tcx>,
320 opaque_def_id: LocalDefId,
321 hir_bounds: &'tcx [hir::GenericBound<'tcx>],
322 item_ty: Ty<'tcx>,
323 span: Span,
324 filter: PredicateFilter,
325) -> &'tcx [(ty::Clause<'tcx>, Span)] {
326 ty::print::with_reduced_queries!({
327 let icx = ItemCtxt::new(tcx, opaque_def_id);
328 let mut bounds = Vec::new();
329 icx.lowerer().lower_bounds(item_ty, hir_bounds, &mut bounds, ty::List::empty(), filter);
330 match filter {
332 PredicateFilter::All
333 | PredicateFilter::SelfOnly
334 | PredicateFilter::SelfTraitThatDefines(_)
335 | PredicateFilter::SelfAndAssociatedTypeBounds => {
336 icx.lowerer().add_sized_bound(&mut bounds, item_ty, hir_bounds, None, span);
338 }
339 PredicateFilter::ConstIfConst | PredicateFilter::SelfConstIfConst => {}
341 }
342 debug!(?bounds);
343
344 tcx.arena.alloc_slice(&bounds)
345 })
346}
347
348pub(super) fn explicit_item_bounds(
349 tcx: TyCtxt<'_>,
350 def_id: LocalDefId,
351) -> ty::EarlyBinder<'_, &'_ [(ty::Clause<'_>, Span)]> {
352 explicit_item_bounds_with_filter(tcx, def_id, PredicateFilter::All)
353}
354
355pub(super) fn explicit_item_self_bounds(
356 tcx: TyCtxt<'_>,
357 def_id: LocalDefId,
358) -> ty::EarlyBinder<'_, &'_ [(ty::Clause<'_>, Span)]> {
359 explicit_item_bounds_with_filter(tcx, def_id, PredicateFilter::SelfOnly)
360}
361
362pub(super) fn explicit_item_bounds_with_filter(
363 tcx: TyCtxt<'_>,
364 def_id: LocalDefId,
365 filter: PredicateFilter,
366) -> ty::EarlyBinder<'_, &'_ [(ty::Clause<'_>, Span)]> {
367 match tcx.opt_rpitit_info(def_id.to_def_id()) {
368 Some(ty::ImplTraitInTraitData::Trait { opaque_def_id, .. }) => {
371 let opaque_ty = tcx.hir_node_by_def_id(opaque_def_id.expect_local()).expect_opaque_ty();
372 let bounds =
373 associated_type_bounds(tcx, def_id, opaque_ty.bounds, opaque_ty.span, filter);
374 return ty::EarlyBinder::bind(bounds);
375 }
376 Some(ty::ImplTraitInTraitData::Impl { .. }) => {
377 span_bug!(tcx.def_span(def_id), "RPITIT in impl should not have item bounds")
378 }
379 None => {}
380 }
381
382 let bounds = match tcx.hir_node_by_def_id(def_id) {
383 hir::Node::TraitItem(hir::TraitItem {
384 kind: hir::TraitItemKind::Type(bounds, _),
385 span,
386 ..
387 }) => associated_type_bounds(tcx, def_id, bounds, *span, filter),
388 hir::Node::OpaqueTy(hir::OpaqueTy { bounds, origin, span, .. }) => match origin {
389 rustc_hir::OpaqueTyOrigin::FnReturn {
393 parent,
394 in_trait_or_impl: Some(hir::RpitContext::Trait),
395 }
396 | rustc_hir::OpaqueTyOrigin::AsyncFn {
397 parent,
398 in_trait_or_impl: Some(hir::RpitContext::Trait),
399 } => {
400 let args = GenericArgs::identity_for_item(tcx, def_id);
401 let item_ty = Ty::new_opaque(tcx, def_id.to_def_id(), args);
402 let bounds = &*tcx.arena.alloc_slice(
403 &opaque_type_bounds(tcx, def_id, bounds, item_ty, *span, filter)
404 .to_vec()
405 .fold_with(&mut AssocTyToOpaque { tcx, fn_def_id: parent.to_def_id() }),
406 );
407 assert_only_contains_predicates_from(filter, bounds, item_ty);
408 bounds
409 }
410 rustc_hir::OpaqueTyOrigin::FnReturn {
411 parent: _,
412 in_trait_or_impl: None | Some(hir::RpitContext::TraitImpl),
413 }
414 | rustc_hir::OpaqueTyOrigin::AsyncFn {
415 parent: _,
416 in_trait_or_impl: None | Some(hir::RpitContext::TraitImpl),
417 }
418 | rustc_hir::OpaqueTyOrigin::TyAlias { parent: _, .. } => {
419 let args = GenericArgs::identity_for_item(tcx, def_id);
420 let item_ty = Ty::new_opaque(tcx, def_id.to_def_id(), args);
421 let bounds = opaque_type_bounds(tcx, def_id, bounds, item_ty, *span, filter);
422 assert_only_contains_predicates_from(filter, bounds, item_ty);
423 bounds
424 }
425 },
426 hir::Node::Item(hir::Item { kind: hir::ItemKind::TyAlias(..), .. }) => &[],
427 node => bug!("item_bounds called on {def_id:?} => {node:?}"),
428 };
429
430 ty::EarlyBinder::bind(bounds)
431}
432
433pub(super) fn item_bounds(tcx: TyCtxt<'_>, def_id: DefId) -> ty::EarlyBinder<'_, ty::Clauses<'_>> {
434 tcx.explicit_item_bounds(def_id).map_bound(|bounds| {
435 tcx.mk_clauses_from_iter(util::elaborate(tcx, bounds.iter().map(|&(bound, _span)| bound)))
436 })
437}
438
439pub(super) fn item_self_bounds(
440 tcx: TyCtxt<'_>,
441 def_id: DefId,
442) -> ty::EarlyBinder<'_, ty::Clauses<'_>> {
443 tcx.explicit_item_self_bounds(def_id).map_bound(|bounds| {
444 tcx.mk_clauses_from_iter(
445 util::elaborate(tcx, bounds.iter().map(|&(bound, _span)| bound)).filter_only_self(),
446 )
447 })
448}
449
450pub(super) fn item_non_self_bounds(
453 tcx: TyCtxt<'_>,
454 def_id: DefId,
455) -> ty::EarlyBinder<'_, ty::Clauses<'_>> {
456 let all_bounds: FxIndexSet<_> = tcx.item_bounds(def_id).skip_binder().iter().collect();
457 let own_bounds: FxIndexSet<_> = tcx.item_self_bounds(def_id).skip_binder().iter().collect();
458 if all_bounds.len() == own_bounds.len() {
459 ty::EarlyBinder::bind(ty::ListWithCachedTypeInfo::empty())
460 } else {
461 ty::EarlyBinder::bind(tcx.mk_clauses_from_iter(all_bounds.difference(&own_bounds).copied()))
462 }
463}
464
465pub(super) fn impl_super_outlives(
468 tcx: TyCtxt<'_>,
469 def_id: DefId,
470) -> ty::EarlyBinder<'_, ty::Clauses<'_>> {
471 tcx.impl_trait_header(def_id).expect("expected an impl of trait").trait_ref.map_bound(
472 |trait_ref| {
473 let clause: ty::Clause<'_> = trait_ref.upcast(tcx);
474 tcx.mk_clauses_from_iter(util::elaborate(tcx, [clause]).filter(|clause| {
475 matches!(
476 clause.kind().skip_binder(),
477 ty::ClauseKind::TypeOutlives(_) | ty::ClauseKind::RegionOutlives(_)
478 )
479 }))
480 },
481 )
482}
483
484struct AssocTyToOpaque<'tcx> {
485 tcx: TyCtxt<'tcx>,
486 fn_def_id: DefId,
487}
488
489impl<'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTyToOpaque<'tcx> {
490 fn cx(&self) -> TyCtxt<'tcx> {
491 self.tcx
492 }
493
494 fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
495 if let ty::Alias(ty::Projection, projection_ty) = ty.kind()
496 && let Some(ty::ImplTraitInTraitData::Trait { fn_def_id, .. }) =
497 self.tcx.opt_rpitit_info(projection_ty.def_id)
498 && fn_def_id == self.fn_def_id
499 {
500 self.tcx.type_of(projection_ty.def_id).instantiate(self.tcx, projection_ty.args)
501 } else {
502 ty.super_fold_with(self)
503 }
504 }
505}