1use rustc_data_structures::fx::FxHashMap;
2use rustc_errors::ErrorGuaranteed;
3use rustc_infer::infer::relate::{
4 PredicateEmittingRelation, Relate, RelateResult, StructurallyRelateAliases, TypeRelation,
5};
6use rustc_infer::infer::{InferCtxt, NllRegionVariableOrigin};
7use rustc_infer::traits::Obligation;
8use rustc_infer::traits::solve::Goal;
9use rustc_middle::mir::ConstraintCategory;
10use rustc_middle::span_bug;
11use rustc_middle::traits::ObligationCause;
12use rustc_middle::traits::query::NoSolution;
13use rustc_middle::ty::fold::FnMutDelegate;
14use rustc_middle::ty::relate::combine::{super_combine_consts, super_combine_tys};
15use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitableExt};
16use rustc_span::{Span, Symbol, sym};
17use tracing::{debug, instrument};
18
19use crate::constraints::OutlivesConstraint;
20use crate::diagnostics::UniverseInfo;
21use crate::renumber::RegionCtxt;
22use crate::type_check::{InstantiateOpaqueType, Locations, TypeChecker};
23
24impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
25 #[instrument(skip(self), level = "debug")]
34 pub(super) fn relate_types(
35 &mut self,
36 a: Ty<'tcx>,
37 v: ty::Variance,
38 b: Ty<'tcx>,
39 locations: Locations,
40 category: ConstraintCategory<'tcx>,
41 ) -> Result<(), NoSolution> {
42 NllTypeRelating::new(self, locations, category, UniverseInfo::relate(a, b), v)
43 .relate(a, b)?;
44 Ok(())
45 }
46
47 pub(super) fn eq_args(
49 &mut self,
50 a: ty::GenericArgsRef<'tcx>,
51 b: ty::GenericArgsRef<'tcx>,
52 locations: Locations,
53 category: ConstraintCategory<'tcx>,
54 ) -> Result<(), NoSolution> {
55 NllTypeRelating::new(self, locations, category, UniverseInfo::other(), ty::Invariant)
56 .relate(a, b)?;
57 Ok(())
58 }
59}
60
61struct NllTypeRelating<'a, 'b, 'tcx> {
62 type_checker: &'a mut TypeChecker<'b, 'tcx>,
63
64 locations: Locations,
66
67 category: ConstraintCategory<'tcx>,
69
70 universe_info: UniverseInfo<'tcx>,
73
74 ambient_variance: ty::Variance,
81
82 ambient_variance_info: ty::VarianceDiagInfo<TyCtxt<'tcx>>,
83}
84
85impl<'a, 'b, 'tcx> NllTypeRelating<'a, 'b, 'tcx> {
86 fn new(
87 type_checker: &'a mut TypeChecker<'b, 'tcx>,
88 locations: Locations,
89 category: ConstraintCategory<'tcx>,
90 universe_info: UniverseInfo<'tcx>,
91 ambient_variance: ty::Variance,
92 ) -> Self {
93 Self {
94 type_checker,
95 locations,
96 category,
97 universe_info,
98 ambient_variance,
99 ambient_variance_info: ty::VarianceDiagInfo::default(),
100 }
101 }
102
103 fn ambient_covariance(&self) -> bool {
104 match self.ambient_variance {
105 ty::Covariant | ty::Invariant => true,
106 ty::Contravariant | ty::Bivariant => false,
107 }
108 }
109
110 fn ambient_contravariance(&self) -> bool {
111 match self.ambient_variance {
112 ty::Contravariant | ty::Invariant => true,
113 ty::Covariant | ty::Bivariant => false,
114 }
115 }
116
117 fn relate_opaques(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, ()> {
118 let infcx = self.type_checker.infcx;
119 debug_assert!(!infcx.next_trait_solver());
120 let mut enable_subtyping = |ty, opaque_is_expected| {
128 let ty_vid = infcx.next_ty_var_id_in_universe(self.span(), ty::UniverseIndex::ROOT);
129
130 let variance = if opaque_is_expected {
131 self.ambient_variance
132 } else {
133 self.ambient_variance.xform(ty::Contravariant)
134 };
135
136 self.type_checker.infcx.instantiate_ty_var(
137 self,
138 opaque_is_expected,
139 ty_vid,
140 variance,
141 ty,
142 )?;
143 Ok(infcx.resolve_vars_if_possible(Ty::new_infer(infcx.tcx, ty::TyVar(ty_vid))))
144 };
145
146 let (a, b) = match (a.kind(), b.kind()) {
147 (&ty::Alias(ty::Opaque, ..), _) => (a, enable_subtyping(b, true)?),
148 (_, &ty::Alias(ty::Opaque, ..)) => (enable_subtyping(a, false)?, b),
149 _ => unreachable!(
150 "expected at least one opaque type in `relate_opaques`, got {a} and {b}."
151 ),
152 };
153 self.register_goals(infcx.handle_opaque_type(a, b, self.span(), self.param_env())?);
154 Ok(())
155 }
156
157 fn enter_forall<T, U>(
158 &mut self,
159 binder: ty::Binder<'tcx, T>,
160 f: impl FnOnce(&mut Self, T) -> U,
161 ) -> U
162 where
163 T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,
164 {
165 let value = if let Some(inner) = binder.no_bound_vars() {
166 inner
167 } else {
168 let infcx = self.type_checker.infcx;
169 let mut lazy_universe = None;
170 let delegate = FnMutDelegate {
171 regions: &mut |br: ty::BoundRegion| {
172 let universe = lazy_universe.unwrap_or_else(|| {
176 let universe = self.create_next_universe();
177 lazy_universe = Some(universe);
178 universe
179 });
180
181 let placeholder = ty::PlaceholderRegion { universe, bound: br };
182 debug!(?placeholder);
183 let placeholder_reg = self.next_placeholder_region(placeholder);
184 debug!(?placeholder_reg);
185
186 placeholder_reg
187 },
188 types: &mut |_bound_ty: ty::BoundTy| {
189 unreachable!("we only replace regions in nll_relate, not types")
190 },
191 consts: &mut |_bound_var: ty::BoundVar| {
192 unreachable!("we only replace regions in nll_relate, not consts")
193 },
194 };
195
196 infcx.tcx.replace_bound_vars_uncached(binder, delegate)
197 };
198
199 debug!(?value);
200 f(self, value)
201 }
202
203 #[instrument(skip(self), level = "debug")]
204 fn instantiate_binder_with_existentials<T>(&mut self, binder: ty::Binder<'tcx, T>) -> T
205 where
206 T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,
207 {
208 if let Some(inner) = binder.no_bound_vars() {
209 return inner;
210 }
211
212 let infcx = self.type_checker.infcx;
213 let mut reg_map = FxHashMap::default();
214 let delegate = FnMutDelegate {
215 regions: &mut |br: ty::BoundRegion| {
216 if let Some(ex_reg_var) = reg_map.get(&br) {
217 *ex_reg_var
218 } else {
219 let ex_reg_var = self.next_existential_region_var(true, br.kind.get_name());
220 debug!(?ex_reg_var);
221 reg_map.insert(br, ex_reg_var);
222
223 ex_reg_var
224 }
225 },
226 types: &mut |_bound_ty: ty::BoundTy| {
227 unreachable!("we only replace regions in nll_relate, not types")
228 },
229 consts: &mut |_bound_var: ty::BoundVar| {
230 unreachable!("we only replace regions in nll_relate, not consts")
231 },
232 };
233
234 let replaced = infcx.tcx.replace_bound_vars_uncached(binder, delegate);
235 debug!(?replaced);
236
237 replaced
238 }
239
240 fn create_next_universe(&mut self) -> ty::UniverseIndex {
241 let universe = self.type_checker.infcx.create_next_universe();
242 self.type_checker.constraints.universe_causes.insert(universe, self.universe_info.clone());
243 universe
244 }
245
246 #[instrument(skip(self), level = "debug")]
247 fn next_existential_region_var(
248 &mut self,
249 from_forall: bool,
250 name: Option<Symbol>,
251 ) -> ty::Region<'tcx> {
252 let origin = NllRegionVariableOrigin::Existential { from_forall };
253
254 let reg_var =
255 self.type_checker.infcx.next_nll_region_var(origin, || RegionCtxt::Existential(name));
256
257 reg_var
258 }
259
260 #[instrument(skip(self), level = "debug")]
261 fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx> {
262 let reg =
263 self.type_checker.constraints.placeholder_region(self.type_checker.infcx, placeholder);
264
265 let reg_info = match placeholder.bound.kind {
266 ty::BoundRegionKind::Anon => sym::anon,
267 ty::BoundRegionKind::Named(_, name) => name,
268 ty::BoundRegionKind::ClosureEnv => sym::env,
269 };
270
271 if cfg!(debug_assertions) {
272 let mut var_to_origin = self.type_checker.infcx.reg_var_to_origin.borrow_mut();
273 let new = RegionCtxt::Placeholder(reg_info);
274 let prev = var_to_origin.insert(reg.as_var(), new);
275 if let Some(prev) = prev {
276 assert_eq!(new, prev);
277 }
278 }
279
280 reg
281 }
282
283 fn push_outlives(
284 &mut self,
285 sup: ty::Region<'tcx>,
286 sub: ty::Region<'tcx>,
287 info: ty::VarianceDiagInfo<TyCtxt<'tcx>>,
288 ) {
289 let sub = self.type_checker.universal_regions.to_region_vid(sub);
290 let sup = self.type_checker.universal_regions.to_region_vid(sup);
291 self.type_checker.constraints.outlives_constraints.push(OutlivesConstraint {
292 sup,
293 sub,
294 locations: self.locations,
295 span: self.locations.span(self.type_checker.body),
296 category: self.category,
297 variance_info: info,
298 from_closure: false,
299 });
300 }
301}
302
303impl<'b, 'tcx> TypeRelation<TyCtxt<'tcx>> for NllTypeRelating<'_, 'b, 'tcx> {
304 fn cx(&self) -> TyCtxt<'tcx> {
305 self.type_checker.infcx.tcx
306 }
307
308 #[instrument(skip(self, info), level = "trace", ret)]
309 fn relate_with_variance<T: Relate<TyCtxt<'tcx>>>(
310 &mut self,
311 variance: ty::Variance,
312 info: ty::VarianceDiagInfo<TyCtxt<'tcx>>,
313 a: T,
314 b: T,
315 ) -> RelateResult<'tcx, T> {
316 let old_ambient_variance = self.ambient_variance;
317 self.ambient_variance = self.ambient_variance.xform(variance);
318 self.ambient_variance_info = self.ambient_variance_info.xform(info);
319
320 debug!(?self.ambient_variance);
321 let r = if self.ambient_variance == ty::Bivariant { Ok(a) } else { self.relate(a, b) };
323
324 self.ambient_variance = old_ambient_variance;
325
326 r
327 }
328
329 #[instrument(skip(self), level = "debug")]
330 fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
331 let infcx = self.type_checker.infcx;
332
333 let a = self.type_checker.infcx.shallow_resolve(a);
334 assert!(!b.has_non_region_infer(), "unexpected inference var {:?}", b);
335
336 if a == b {
337 return Ok(a);
338 }
339
340 match (a.kind(), b.kind()) {
341 (_, &ty::Infer(ty::TyVar(_))) => {
342 span_bug!(
343 self.span(),
344 "should not be relating type variables on the right in MIR typeck"
345 );
346 }
347
348 (&ty::Infer(ty::TyVar(a_vid)), _) => {
349 infcx.instantiate_ty_var(self, true, a_vid, self.ambient_variance, b)?
350 }
351
352 (
353 &ty::Alias(ty::Opaque, ty::AliasTy { def_id: a_def_id, .. }),
354 &ty::Alias(ty::Opaque, ty::AliasTy { def_id: b_def_id, .. }),
355 ) if a_def_id == b_def_id || infcx.next_trait_solver() => {
356 super_combine_tys(&infcx.infcx, self, a, b).map(|_| ()).or_else(|err| {
357 assert!(!self.type_checker.infcx.next_trait_solver());
361 self.cx().dcx().span_delayed_bug(
362 self.span(),
363 "failure to relate an opaque to itself should result in an error later on",
364 );
365 if a_def_id.is_local() { self.relate_opaques(a, b) } else { Err(err) }
366 })?;
367 }
368 (&ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }), _)
369 | (_, &ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }))
370 if def_id.is_local() && !self.type_checker.infcx.next_trait_solver() =>
371 {
372 self.relate_opaques(a, b)?;
373 }
374
375 _ => {
376 debug!(?a, ?b, ?self.ambient_variance);
377
378 super_combine_tys(&self.type_checker.infcx.infcx, self, a, b)?;
380 }
381 }
382
383 Ok(a)
384 }
385
386 #[instrument(skip(self), level = "trace")]
387 fn regions(
388 &mut self,
389 a: ty::Region<'tcx>,
390 b: ty::Region<'tcx>,
391 ) -> RelateResult<'tcx, ty::Region<'tcx>> {
392 debug!(?self.ambient_variance);
393
394 if self.ambient_covariance() {
395 self.push_outlives(a, b, self.ambient_variance_info);
397 }
398
399 if self.ambient_contravariance() {
400 self.push_outlives(b, a, self.ambient_variance_info);
402 }
403
404 Ok(a)
405 }
406
407 fn consts(
408 &mut self,
409 a: ty::Const<'tcx>,
410 b: ty::Const<'tcx>,
411 ) -> RelateResult<'tcx, ty::Const<'tcx>> {
412 let a = self.type_checker.infcx.shallow_resolve_const(a);
413 assert!(!a.has_non_region_infer(), "unexpected inference var {:?}", a);
414 assert!(!b.has_non_region_infer(), "unexpected inference var {:?}", b);
415
416 super_combine_consts(&self.type_checker.infcx.infcx, self, a, b)
417 }
418
419 #[instrument(skip(self), level = "trace")]
420 fn binders<T>(
421 &mut self,
422 a: ty::Binder<'tcx, T>,
423 b: ty::Binder<'tcx, T>,
424 ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
425 where
426 T: Relate<TyCtxt<'tcx>>,
427 {
428 debug!(?self.ambient_variance);
448
449 if let (Some(a), Some(b)) = (a.no_bound_vars(), b.no_bound_vars()) {
450 self.relate(a, b)?;
452 return Ok(ty::Binder::dummy(a));
453 }
454
455 match self.ambient_variance {
456 ty::Covariant => {
457 self.enter_forall(b, |this, b| {
466 let a = this.instantiate_binder_with_existentials(a);
467 this.relate(a, b)
468 })?;
469 }
470
471 ty::Contravariant => {
472 self.enter_forall(a, |this, a| {
481 let b = this.instantiate_binder_with_existentials(b);
482 this.relate(a, b)
483 })?;
484 }
485
486 ty::Invariant => {
487 self.enter_forall(b, |this, b| {
496 let a = this.instantiate_binder_with_existentials(a);
497 this.relate(a, b)
498 })?;
499 self.enter_forall(a, |this, a| {
502 let b = this.instantiate_binder_with_existentials(b);
503 this.relate(a, b)
504 })?;
505 }
506
507 ty::Bivariant => {}
508 }
509
510 Ok(a)
511 }
512}
513
514impl<'b, 'tcx> PredicateEmittingRelation<InferCtxt<'tcx>> for NllTypeRelating<'_, 'b, 'tcx> {
515 fn span(&self) -> Span {
516 self.locations.span(self.type_checker.body)
517 }
518
519 fn structurally_relate_aliases(&self) -> StructurallyRelateAliases {
520 StructurallyRelateAliases::No
521 }
522
523 fn param_env(&self) -> ty::ParamEnv<'tcx> {
524 self.type_checker.infcx.param_env
525 }
526
527 fn register_predicates(
528 &mut self,
529 obligations: impl IntoIterator<Item: ty::Upcast<TyCtxt<'tcx>, ty::Predicate<'tcx>>>,
530 ) {
531 let tcx = self.cx();
532 let param_env = self.param_env();
533 self.register_goals(
534 obligations.into_iter().map(|to_pred| Goal::new(tcx, param_env, to_pred)),
535 );
536 }
537
538 fn register_goals(
539 &mut self,
540 obligations: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>,
541 ) {
542 let _: Result<_, ErrorGuaranteed> = self.type_checker.fully_perform_op(
543 self.locations,
544 self.category,
545 InstantiateOpaqueType {
546 obligations: obligations
547 .into_iter()
548 .map(|goal| {
549 Obligation::new(
550 self.cx(),
551 ObligationCause::dummy_with_span(self.span()),
552 goal.param_env,
553 goal.predicate,
554 )
555 })
556 .collect(),
557 base_universe: None,
559 region_constraints: None,
560 },
561 );
562 }
563
564 fn register_alias_relate_predicate(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) {
565 self.register_predicates([ty::Binder::dummy(match self.ambient_variance {
566 ty::Covariant => ty::PredicateKind::AliasRelate(
567 a.into(),
568 b.into(),
569 ty::AliasRelationDirection::Subtype,
570 ),
571 ty::Contravariant => ty::PredicateKind::AliasRelate(
573 b.into(),
574 a.into(),
575 ty::AliasRelationDirection::Subtype,
576 ),
577 ty::Invariant => ty::PredicateKind::AliasRelate(
578 a.into(),
579 b.into(),
580 ty::AliasRelationDirection::Equate,
581 ),
582 ty::Bivariant => {
583 unreachable!("cannot defer an alias-relate goal with Bivariant variance (yet?)")
584 }
585 })]);
586 }
587}