1use std::iter;
2
3use derive_where::derive_where;
4use rustc_ast_ir::Mutability;
5use tracing::{instrument, trace};
6
7use crate::error::{ExpectedFound, TypeError};
8use crate::fold::TypeFoldable;
9use crate::inherent::*;
10use crate::{self as ty, Interner};
11
12pub mod combine;
13pub mod solver_relating;
14
15pub type RelateResult<I, T> = Result<T, TypeError<I>>;
16
17#[derive(Debug, Copy, Clone)]
24pub enum StructurallyRelateAliases {
25 Yes,
26 No,
27}
28
29#[derive_where(Clone, Copy, PartialEq, Eq, Debug, Default; I: Interner)]
37pub enum VarianceDiagInfo<I: Interner> {
38 #[derive_where(default)]
41 None,
42 Invariant {
45 ty: I::Ty,
48 param_index: u32,
51 },
52}
53
54impl<I: Interner> VarianceDiagInfo<I> {
55 pub fn xform(self, other: VarianceDiagInfo<I>) -> VarianceDiagInfo<I> {
58 match self {
60 VarianceDiagInfo::None => other,
61 VarianceDiagInfo::Invariant { .. } => self,
62 }
63 }
64}
65
66pub trait TypeRelation<I: Interner>: Sized {
67 fn cx(&self) -> I;
68
69 fn relate<T: Relate<I>>(&mut self, a: T, b: T) -> RelateResult<I, T> {
71 Relate::relate(self, a, b)
72 }
73
74 #[instrument(skip(self), level = "trace")]
78 fn relate_item_args(
79 &mut self,
80 item_def_id: I::DefId,
81 a_arg: I::GenericArgs,
82 b_arg: I::GenericArgs,
83 ) -> RelateResult<I, I::GenericArgs> {
84 let cx = self.cx();
85 let opt_variances = cx.variances_of(item_def_id);
86 relate_args_with_variances(self, item_def_id, opt_variances, a_arg, b_arg, true)
87 }
88
89 fn relate_with_variance<T: Relate<I>>(
91 &mut self,
92 variance: ty::Variance,
93 info: VarianceDiagInfo<I>,
94 a: T,
95 b: T,
96 ) -> RelateResult<I, T>;
97
98 fn tys(&mut self, a: I::Ty, b: I::Ty) -> RelateResult<I, I::Ty>;
105
106 fn regions(&mut self, a: I::Region, b: I::Region) -> RelateResult<I, I::Region>;
107
108 fn consts(&mut self, a: I::Const, b: I::Const) -> RelateResult<I, I::Const>;
109
110 fn binders<T>(
111 &mut self,
112 a: ty::Binder<I, T>,
113 b: ty::Binder<I, T>,
114 ) -> RelateResult<I, ty::Binder<I, T>>
115 where
116 T: Relate<I>;
117}
118
119pub trait Relate<I: Interner>: TypeFoldable<I> + PartialEq + Copy {
120 fn relate<R: TypeRelation<I>>(relation: &mut R, a: Self, b: Self) -> RelateResult<I, Self>;
121}
122
123#[inline]
127pub fn relate_args_invariantly<I: Interner, R: TypeRelation<I>>(
128 relation: &mut R,
129 a_arg: I::GenericArgs,
130 b_arg: I::GenericArgs,
131) -> RelateResult<I, I::GenericArgs> {
132 relation.cx().mk_args_from_iter(iter::zip(a_arg.iter(), b_arg.iter()).map(|(a, b)| {
133 relation.relate_with_variance(ty::Invariant, VarianceDiagInfo::default(), a, b)
134 }))
135}
136
137pub fn relate_args_with_variances<I: Interner, R: TypeRelation<I>>(
138 relation: &mut R,
139 ty_def_id: I::DefId,
140 variances: I::VariancesOf,
141 a_arg: I::GenericArgs,
142 b_arg: I::GenericArgs,
143 fetch_ty_for_diag: bool,
144) -> RelateResult<I, I::GenericArgs> {
145 let cx = relation.cx();
146
147 let mut cached_ty = None;
148 let params = iter::zip(a_arg.iter(), b_arg.iter()).enumerate().map(|(i, (a, b))| {
149 let variance = variances.get(i).unwrap();
150 let variance_info = if variance == ty::Invariant && fetch_ty_for_diag {
151 let ty = *cached_ty.get_or_insert_with(|| cx.type_of(ty_def_id).instantiate(cx, a_arg));
152 VarianceDiagInfo::Invariant { ty, param_index: i.try_into().unwrap() }
153 } else {
154 VarianceDiagInfo::default()
155 };
156 relation.relate_with_variance(variance, variance_info, a, b)
157 });
158
159 cx.mk_args_from_iter(params)
160}
161
162impl<I: Interner> Relate<I> for ty::FnSig<I> {
163 fn relate<R: TypeRelation<I>>(
164 relation: &mut R,
165 a: ty::FnSig<I>,
166 b: ty::FnSig<I>,
167 ) -> RelateResult<I, ty::FnSig<I>> {
168 let cx = relation.cx();
169
170 if a.c_variadic != b.c_variadic {
171 return Err(TypeError::VariadicMismatch({
172 let a = a.c_variadic;
173 let b = b.c_variadic;
174 ExpectedFound::new(a, b)
175 }));
176 }
177
178 if a.safety != b.safety {
179 return Err(TypeError::SafetyMismatch(ExpectedFound::new(a.safety, b.safety)));
180 }
181
182 if a.abi != b.abi {
183 return Err(TypeError::AbiMismatch(ExpectedFound::new(a.abi, b.abi)));
184 };
185
186 let a_inputs = a.inputs();
187 let b_inputs = b.inputs();
188 if a_inputs.len() != b_inputs.len() {
189 return Err(TypeError::ArgCount);
190 }
191
192 let inputs_and_output = iter::zip(a_inputs.iter(), b_inputs.iter())
193 .map(|(a, b)| ((a, b), false))
194 .chain(iter::once(((a.output(), b.output()), true)))
195 .map(|((a, b), is_output)| {
196 if is_output {
197 relation.relate(a, b)
198 } else {
199 relation.relate_with_variance(
200 ty::Contravariant,
201 VarianceDiagInfo::default(),
202 a,
203 b,
204 )
205 }
206 })
207 .enumerate()
208 .map(|(i, r)| match r {
209 Err(TypeError::Sorts(exp_found) | TypeError::ArgumentSorts(exp_found, _)) => {
210 Err(TypeError::ArgumentSorts(exp_found, i))
211 }
212 Err(TypeError::Mutability | TypeError::ArgumentMutability(_)) => {
213 Err(TypeError::ArgumentMutability(i))
214 }
215 r => r,
216 });
217 Ok(ty::FnSig {
218 inputs_and_output: cx.mk_type_list_from_iter(inputs_and_output)?,
219 c_variadic: a.c_variadic,
220 safety: a.safety,
221 abi: a.abi,
222 })
223 }
224}
225
226impl<I: Interner> Relate<I> for ty::AliasTy<I> {
227 fn relate<R: TypeRelation<I>>(
228 relation: &mut R,
229 a: ty::AliasTy<I>,
230 b: ty::AliasTy<I>,
231 ) -> RelateResult<I, ty::AliasTy<I>> {
232 if a.def_id != b.def_id {
233 Err(TypeError::ProjectionMismatched({
234 let a = a.def_id;
235 let b = b.def_id;
236 ExpectedFound::new(a, b)
237 }))
238 } else {
239 let cx = relation.cx();
240 let args = if let Some(variances) = cx.opt_alias_variances(a.kind(cx), a.def_id) {
241 relate_args_with_variances(
242 relation, a.def_id, variances, a.args, b.args,
243 false, )?
245 } else {
246 relate_args_invariantly(relation, a.args, b.args)?
247 };
248 Ok(ty::AliasTy::new_from_args(relation.cx(), a.def_id, args))
249 }
250 }
251}
252
253impl<I: Interner> Relate<I> for ty::AliasTerm<I> {
254 fn relate<R: TypeRelation<I>>(
255 relation: &mut R,
256 a: ty::AliasTerm<I>,
257 b: ty::AliasTerm<I>,
258 ) -> RelateResult<I, ty::AliasTerm<I>> {
259 if a.def_id != b.def_id {
260 Err(TypeError::ProjectionMismatched({
261 let a = a.def_id;
262 let b = b.def_id;
263 ExpectedFound::new(a, b)
264 }))
265 } else {
266 let args = match a.kind(relation.cx()) {
267 ty::AliasTermKind::OpaqueTy => relate_args_with_variances(
268 relation,
269 a.def_id,
270 relation.cx().variances_of(a.def_id),
271 a.args,
272 b.args,
273 false, )?,
275 ty::AliasTermKind::ProjectionTy
276 | ty::AliasTermKind::WeakTy
277 | ty::AliasTermKind::InherentTy
278 | ty::AliasTermKind::UnevaluatedConst
279 | ty::AliasTermKind::ProjectionConst => {
280 relate_args_invariantly(relation, a.args, b.args)?
281 }
282 };
283 Ok(ty::AliasTerm::new_from_args(relation.cx(), a.def_id, args))
284 }
285 }
286}
287
288impl<I: Interner> Relate<I> for ty::ExistentialProjection<I> {
289 fn relate<R: TypeRelation<I>>(
290 relation: &mut R,
291 a: ty::ExistentialProjection<I>,
292 b: ty::ExistentialProjection<I>,
293 ) -> RelateResult<I, ty::ExistentialProjection<I>> {
294 if a.def_id != b.def_id {
295 Err(TypeError::ProjectionMismatched({
296 let a = a.def_id;
297 let b = b.def_id;
298 ExpectedFound::new(a, b)
299 }))
300 } else {
301 let term = relation.relate_with_variance(
302 ty::Invariant,
303 VarianceDiagInfo::default(),
304 a.term,
305 b.term,
306 )?;
307 let args = relation.relate_with_variance(
308 ty::Invariant,
309 VarianceDiagInfo::default(),
310 a.args,
311 b.args,
312 )?;
313 Ok(ty::ExistentialProjection::new_from_args(relation.cx(), a.def_id, args, term))
314 }
315 }
316}
317
318impl<I: Interner> Relate<I> for ty::TraitRef<I> {
319 fn relate<R: TypeRelation<I>>(
320 relation: &mut R,
321 a: ty::TraitRef<I>,
322 b: ty::TraitRef<I>,
323 ) -> RelateResult<I, ty::TraitRef<I>> {
324 if a.def_id != b.def_id {
326 Err(TypeError::Traits({
327 let a = a.def_id;
328 let b = b.def_id;
329 ExpectedFound::new(a, b)
330 }))
331 } else {
332 let args = relate_args_invariantly(relation, a.args, b.args)?;
333 Ok(ty::TraitRef::new_from_args(relation.cx(), a.def_id, args))
334 }
335 }
336}
337
338impl<I: Interner> Relate<I> for ty::ExistentialTraitRef<I> {
339 fn relate<R: TypeRelation<I>>(
340 relation: &mut R,
341 a: ty::ExistentialTraitRef<I>,
342 b: ty::ExistentialTraitRef<I>,
343 ) -> RelateResult<I, ty::ExistentialTraitRef<I>> {
344 if a.def_id != b.def_id {
346 Err(TypeError::Traits({
347 let a = a.def_id;
348 let b = b.def_id;
349 ExpectedFound::new(a, b)
350 }))
351 } else {
352 let args = relate_args_invariantly(relation, a.args, b.args)?;
353 Ok(ty::ExistentialTraitRef::new_from_args(relation.cx(), a.def_id, args))
354 }
355 }
356}
357
358#[instrument(level = "trace", skip(relation), ret)]
362pub fn structurally_relate_tys<I: Interner, R: TypeRelation<I>>(
363 relation: &mut R,
364 a: I::Ty,
365 b: I::Ty,
366) -> RelateResult<I, I::Ty> {
367 let cx = relation.cx();
368 match (a.kind(), b.kind()) {
369 (ty::Infer(_), _) | (_, ty::Infer(_)) => {
370 panic!("var types encountered in structurally_relate_tys")
372 }
373
374 (ty::Bound(..), _) | (_, ty::Bound(..)) => {
375 panic!("bound types encountered in structurally_relate_tys")
376 }
377
378 (ty::Error(guar), _) | (_, ty::Error(guar)) => Ok(Ty::new_error(cx, guar)),
379
380 (ty::Never, _)
381 | (ty::Char, _)
382 | (ty::Bool, _)
383 | (ty::Int(_), _)
384 | (ty::Uint(_), _)
385 | (ty::Float(_), _)
386 | (ty::Str, _)
387 if a == b =>
388 {
389 Ok(a)
390 }
391
392 (ty::Param(a_p), ty::Param(b_p)) if a_p.index() == b_p.index() => {
393 Ok(a)
396 }
397
398 (ty::Placeholder(p1), ty::Placeholder(p2)) if p1 == p2 => Ok(a),
399
400 (ty::Adt(a_def, a_args), ty::Adt(b_def, b_args)) if a_def == b_def => {
401 let args = relation.relate_item_args(a_def.def_id(), a_args, b_args)?;
402 Ok(Ty::new_adt(cx, a_def, args))
403 }
404
405 (ty::Foreign(a_id), ty::Foreign(b_id)) if a_id == b_id => Ok(Ty::new_foreign(cx, a_id)),
406
407 (ty::Dynamic(a_obj, a_region, a_repr), ty::Dynamic(b_obj, b_region, b_repr))
408 if a_repr == b_repr =>
409 {
410 Ok(Ty::new_dynamic(
411 cx,
412 relation.relate(a_obj, b_obj)?,
413 relation.relate(a_region, b_region)?,
414 a_repr,
415 ))
416 }
417
418 (ty::Coroutine(a_id, a_args), ty::Coroutine(b_id, b_args)) if a_id == b_id => {
419 let args = relate_args_invariantly(relation, a_args, b_args)?;
423 Ok(Ty::new_coroutine(cx, a_id, args))
424 }
425
426 (ty::CoroutineWitness(a_id, a_args), ty::CoroutineWitness(b_id, b_args))
427 if a_id == b_id =>
428 {
429 let args = relate_args_invariantly(relation, a_args, b_args)?;
433 Ok(Ty::new_coroutine_witness(cx, a_id, args))
434 }
435
436 (ty::Closure(a_id, a_args), ty::Closure(b_id, b_args)) if a_id == b_id => {
437 let args = relate_args_invariantly(relation, a_args, b_args)?;
441 Ok(Ty::new_closure(cx, a_id, args))
442 }
443
444 (ty::CoroutineClosure(a_id, a_args), ty::CoroutineClosure(b_id, b_args))
445 if a_id == b_id =>
446 {
447 let args = relate_args_invariantly(relation, a_args, b_args)?;
448 Ok(Ty::new_coroutine_closure(cx, a_id, args))
449 }
450
451 (ty::RawPtr(a_ty, a_mutbl), ty::RawPtr(b_ty, b_mutbl)) => {
452 if a_mutbl != b_mutbl {
453 return Err(TypeError::Mutability);
454 }
455
456 let (variance, info) = match a_mutbl {
457 Mutability::Not => (ty::Covariant, VarianceDiagInfo::None),
458 Mutability::Mut => {
459 (ty::Invariant, VarianceDiagInfo::Invariant { ty: a, param_index: 0 })
460 }
461 };
462
463 let ty = relation.relate_with_variance(variance, info, a_ty, b_ty)?;
464
465 Ok(Ty::new_ptr(cx, ty, a_mutbl))
466 }
467
468 (ty::Ref(a_r, a_ty, a_mutbl), ty::Ref(b_r, b_ty, b_mutbl)) => {
469 if a_mutbl != b_mutbl {
470 return Err(TypeError::Mutability);
471 }
472
473 let (variance, info) = match a_mutbl {
474 Mutability::Not => (ty::Covariant, VarianceDiagInfo::None),
475 Mutability::Mut => {
476 (ty::Invariant, VarianceDiagInfo::Invariant { ty: a, param_index: 0 })
477 }
478 };
479
480 let r = relation.relate(a_r, b_r)?;
481 let ty = relation.relate_with_variance(variance, info, a_ty, b_ty)?;
482
483 Ok(Ty::new_ref(cx, r, ty, a_mutbl))
484 }
485
486 (ty::Array(a_t, sz_a), ty::Array(b_t, sz_b)) => {
487 let t = relation.relate(a_t, b_t)?;
488 match relation.relate(sz_a, sz_b) {
489 Ok(sz) => Ok(Ty::new_array_with_const_len(cx, t, sz)),
490 Err(TypeError::ConstMismatch(_)) => {
491 Err(TypeError::ArraySize(ExpectedFound::new(sz_a, sz_b)))
492 }
493 Err(e) => Err(e),
494 }
495 }
496
497 (ty::Slice(a_t), ty::Slice(b_t)) => {
498 let t = relation.relate(a_t, b_t)?;
499 Ok(Ty::new_slice(cx, t))
500 }
501
502 (ty::Tuple(as_), ty::Tuple(bs)) => {
503 if as_.len() == bs.len() {
504 Ok(Ty::new_tup_from_iter(
505 cx,
506 iter::zip(as_.iter(), bs.iter()).map(|(a, b)| relation.relate(a, b)),
507 )?)
508 } else if !(as_.is_empty() || bs.is_empty()) {
509 Err(TypeError::TupleSize(ExpectedFound::new(as_.len(), bs.len())))
510 } else {
511 Err(TypeError::Sorts(ExpectedFound::new(a, b)))
512 }
513 }
514
515 (ty::FnDef(a_def_id, a_args), ty::FnDef(b_def_id, b_args)) if a_def_id == b_def_id => {
516 let args = relation.relate_item_args(a_def_id, a_args, b_args)?;
517 Ok(Ty::new_fn_def(cx, a_def_id, args))
518 }
519
520 (ty::FnPtr(a_sig_tys, a_hdr), ty::FnPtr(b_sig_tys, b_hdr)) => {
521 let fty = relation.relate(a_sig_tys.with(a_hdr), b_sig_tys.with(b_hdr))?;
522 Ok(Ty::new_fn_ptr(cx, fty))
523 }
524
525 (ty::Alias(a_kind, a_data), ty::Alias(b_kind, b_data)) => {
527 let alias_ty = relation.relate(a_data, b_data)?;
528 assert_eq!(a_kind, b_kind);
529 Ok(Ty::new_alias(cx, a_kind, alias_ty))
530 }
531
532 (ty::Pat(a_ty, a_pat), ty::Pat(b_ty, b_pat)) => {
533 let ty = relation.relate(a_ty, b_ty)?;
534 let pat = relation.relate(a_pat, b_pat)?;
535 Ok(Ty::new_pat(cx, ty, pat))
536 }
537
538 (ty::UnsafeBinder(a_binder), ty::UnsafeBinder(b_binder)) => {
539 Ok(Ty::new_unsafe_binder(cx, relation.binders(*a_binder, *b_binder)?))
540 }
541
542 _ => Err(TypeError::Sorts(ExpectedFound::new(a, b))),
543 }
544}
545
546pub fn structurally_relate_consts<I: Interner, R: TypeRelation<I>>(
553 relation: &mut R,
554 mut a: I::Const,
555 mut b: I::Const,
556) -> RelateResult<I, I::Const> {
557 trace!(
558 "structurally_relate_consts::<{}>(a = {:?}, b = {:?})",
559 std::any::type_name::<R>(),
560 a,
561 b
562 );
563 let cx = relation.cx();
564
565 if cx.features().generic_const_exprs() {
566 a = cx.expand_abstract_consts(a);
567 b = cx.expand_abstract_consts(b);
568 }
569
570 trace!(
571 "structurally_relate_consts::<{}>(normed_a = {:?}, normed_b = {:?})",
572 std::any::type_name::<R>(),
573 a,
574 b
575 );
576
577 let is_match = match (a.kind(), b.kind()) {
581 (ty::ConstKind::Infer(_), _) | (_, ty::ConstKind::Infer(_)) => {
582 panic!("var types encountered in structurally_relate_consts: {:?} {:?}", a, b)
584 }
585
586 (ty::ConstKind::Error(_), _) => return Ok(a),
587 (_, ty::ConstKind::Error(_)) => return Ok(b),
588
589 (ty::ConstKind::Param(a_p), ty::ConstKind::Param(b_p)) if a_p.index() == b_p.index() => {
590 true
593 }
594 (ty::ConstKind::Placeholder(p1), ty::ConstKind::Placeholder(p2)) => p1 == p2,
595 (ty::ConstKind::Value(a_val), ty::ConstKind::Value(b_val)) => {
596 a_val.valtree() == b_val.valtree()
597 }
598
599 (ty::ConstKind::Unevaluated(au), ty::ConstKind::Unevaluated(bu)) if au.def == bu.def => {
603 if cfg!(debug_assertions) {
604 let a_ty = cx.type_of(au.def).instantiate(cx, au.args);
605 let b_ty = cx.type_of(bu.def).instantiate(cx, bu.args);
606 assert_eq!(a_ty, b_ty);
607 }
608
609 let args = relation.relate_with_variance(
610 ty::Invariant,
611 VarianceDiagInfo::default(),
612 au.args,
613 bu.args,
614 )?;
615 return Ok(Const::new_unevaluated(cx, ty::UnevaluatedConst { def: au.def, args }));
616 }
617 (ty::ConstKind::Expr(ae), ty::ConstKind::Expr(be)) => {
618 let expr = relation.relate(ae, be)?;
619 return Ok(Const::new_expr(cx, expr));
620 }
621 _ => false,
622 };
623 if is_match { Ok(a) } else { Err(TypeError::ConstMismatch(ExpectedFound::new(a, b))) }
624}
625
626impl<I: Interner, T: Relate<I>> Relate<I> for ty::Binder<I, T> {
627 fn relate<R: TypeRelation<I>>(
628 relation: &mut R,
629 a: ty::Binder<I, T>,
630 b: ty::Binder<I, T>,
631 ) -> RelateResult<I, ty::Binder<I, T>> {
632 relation.binders(a, b)
633 }
634}
635
636impl<I: Interner> Relate<I> for ty::TraitPredicate<I> {
637 fn relate<R: TypeRelation<I>>(
638 relation: &mut R,
639 a: ty::TraitPredicate<I>,
640 b: ty::TraitPredicate<I>,
641 ) -> RelateResult<I, ty::TraitPredicate<I>> {
642 let trait_ref = relation.relate(a.trait_ref, b.trait_ref)?;
643 if a.polarity != b.polarity {
644 return Err(TypeError::PolarityMismatch(ExpectedFound::new(a.polarity, b.polarity)));
645 }
646 Ok(ty::TraitPredicate { trait_ref, polarity: a.polarity })
647 }
648}