1use std::fmt::Debug;
2use std::hash::Hash;
3use std::iter;
4use std::marker::PhantomData;
5
6use rustc_ast_ir::Mutability;
7#[cfg(feature = "nightly")]
8use rustc_data_structures::fingerprint::Fingerprint;
9#[cfg(feature = "nightly")]
10use rustc_data_structures::stable_hasher::{HashStable, StableHasher, ToStableHashKey};
11#[cfg(feature = "nightly")]
12use rustc_macros::{Decodable_NoContext, Encodable_NoContext, HashStable_NoContext};
13
14use crate::inherent::*;
15use crate::visit::TypeVisitableExt as _;
16use crate::{self as ty, Interner};
17
18#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
20#[cfg_attr(
21 feature = "nightly",
22 derive(Encodable_NoContext, Decodable_NoContext, HashStable_NoContext)
23)]
24pub enum SimplifiedType<DefId> {
25 Bool,
26 Char,
27 Int(ty::IntTy),
28 Uint(ty::UintTy),
29 Float(ty::FloatTy),
30 Adt(DefId),
31 Foreign(DefId),
32 Str,
33 Array,
34 Slice,
35 Ref(Mutability),
36 Ptr(Mutability),
37 Never,
38 Tuple(usize),
39 MarkerTraitObject,
42 Trait(DefId),
43 Closure(DefId),
44 Coroutine(DefId),
45 CoroutineWitness(DefId),
46 Function(usize),
47 UnsafeBinder,
48 Placeholder,
49 Error,
50}
51
52#[cfg(feature = "nightly")]
53impl<HCX: Clone, DefId: HashStable<HCX>> ToStableHashKey<HCX> for SimplifiedType<DefId> {
54 type KeyType = Fingerprint;
55
56 #[inline]
57 fn to_stable_hash_key(&self, hcx: &HCX) -> Fingerprint {
58 let mut hasher = StableHasher::new();
59 let mut hcx: HCX = hcx.clone();
60 self.hash_stable(&mut hcx, &mut hasher);
61 hasher.finish()
62 }
63}
64
65#[derive(PartialEq, Eq, Debug, Clone, Copy)]
78pub enum TreatParams {
79 InstantiateWithInfer,
82 AsRigid,
88}
89
90pub fn simplify_type<I: Interner>(
112 cx: I,
113 ty: I::Ty,
114 treat_params: TreatParams,
115) -> Option<SimplifiedType<I::DefId>> {
116 match ty.kind() {
117 ty::Bool => Some(SimplifiedType::Bool),
118 ty::Char => Some(SimplifiedType::Char),
119 ty::Int(int_type) => Some(SimplifiedType::Int(int_type)),
120 ty::Uint(uint_type) => Some(SimplifiedType::Uint(uint_type)),
121 ty::Float(float_type) => Some(SimplifiedType::Float(float_type)),
122 ty::Adt(def, _) => Some(SimplifiedType::Adt(def.def_id())),
123 ty::Str => Some(SimplifiedType::Str),
124 ty::Array(..) => Some(SimplifiedType::Array),
125 ty::Slice(..) => Some(SimplifiedType::Slice),
126 ty::Pat(ty, ..) => simplify_type(cx, ty, treat_params),
127 ty::RawPtr(_, mutbl) => Some(SimplifiedType::Ptr(mutbl)),
128 ty::Dynamic(trait_info, ..) => match trait_info.principal_def_id() {
129 Some(principal_def_id) if !cx.trait_is_auto(principal_def_id) => {
130 Some(SimplifiedType::Trait(principal_def_id))
131 }
132 _ => Some(SimplifiedType::MarkerTraitObject),
133 },
134 ty::Ref(_, _, mutbl) => Some(SimplifiedType::Ref(mutbl)),
135 ty::FnDef(def_id, _) | ty::Closure(def_id, _) | ty::CoroutineClosure(def_id, _) => {
136 Some(SimplifiedType::Closure(def_id))
137 }
138 ty::Coroutine(def_id, _) => Some(SimplifiedType::Coroutine(def_id)),
139 ty::CoroutineWitness(def_id, _) => Some(SimplifiedType::CoroutineWitness(def_id)),
140 ty::Never => Some(SimplifiedType::Never),
141 ty::Tuple(tys) => Some(SimplifiedType::Tuple(tys.len())),
142 ty::FnPtr(sig_tys, _hdr) => {
143 Some(SimplifiedType::Function(sig_tys.skip_binder().inputs().len()))
144 }
145 ty::UnsafeBinder(_) => Some(SimplifiedType::UnsafeBinder),
146 ty::Placeholder(..) => Some(SimplifiedType::Placeholder),
147 ty::Param(_) => match treat_params {
148 TreatParams::AsRigid => Some(SimplifiedType::Placeholder),
149 TreatParams::InstantiateWithInfer => None,
150 },
151 ty::Alias(..) => match treat_params {
152 TreatParams::AsRigid if !ty.has_non_region_infer() => Some(SimplifiedType::Placeholder),
157 TreatParams::AsRigid | TreatParams::InstantiateWithInfer => None,
158 },
159 ty::Foreign(def_id) => Some(SimplifiedType::Foreign(def_id)),
160 ty::Error(_) => Some(SimplifiedType::Error),
161 ty::Bound(..) | ty::Infer(_) => None,
162 }
163}
164
165impl<DefId> SimplifiedType<DefId> {
166 pub fn def(self) -> Option<DefId> {
167 match self {
168 SimplifiedType::Adt(d)
169 | SimplifiedType::Foreign(d)
170 | SimplifiedType::Trait(d)
171 | SimplifiedType::Closure(d)
172 | SimplifiedType::Coroutine(d)
173 | SimplifiedType::CoroutineWitness(d) => Some(d),
174 _ => None,
175 }
176 }
177}
178
179#[derive(Debug, Clone, Copy)]
190pub struct DeepRejectCtxt<
191 I: Interner,
192 const INSTANTIATE_LHS_WITH_INFER: bool,
193 const INSTANTIATE_RHS_WITH_INFER: bool,
194> {
195 _interner: PhantomData<I>,
196}
197
198impl<I: Interner> DeepRejectCtxt<I, false, false> {
199 pub fn relate_rigid_rigid(_interner: I) -> DeepRejectCtxt<I, false, false> {
201 DeepRejectCtxt { _interner: PhantomData }
202 }
203}
204
205impl<I: Interner> DeepRejectCtxt<I, true, true> {
206 pub fn relate_infer_infer(_interner: I) -> DeepRejectCtxt<I, true, true> {
208 DeepRejectCtxt { _interner: PhantomData }
209 }
210}
211
212impl<I: Interner> DeepRejectCtxt<I, false, true> {
213 pub fn relate_rigid_infer(_interner: I) -> DeepRejectCtxt<I, false, true> {
215 DeepRejectCtxt { _interner: PhantomData }
216 }
217}
218
219impl<I: Interner, const INSTANTIATE_LHS_WITH_INFER: bool, const INSTANTIATE_RHS_WITH_INFER: bool>
220 DeepRejectCtxt<I, INSTANTIATE_LHS_WITH_INFER, INSTANTIATE_RHS_WITH_INFER>
221{
222 const STARTING_DEPTH: usize = 8;
225
226 pub fn args_may_unify(
227 self,
228 obligation_args: I::GenericArgs,
229 impl_args: I::GenericArgs,
230 ) -> bool {
231 self.args_may_unify_inner(obligation_args, impl_args, Self::STARTING_DEPTH)
232 }
233
234 pub fn types_may_unify(self, lhs: I::Ty, rhs: I::Ty) -> bool {
235 if lhs == rhs {
236 return true;
237 }
238 self.types_may_unify_inner(lhs, rhs, Self::STARTING_DEPTH)
239 }
240
241 fn args_may_unify_inner(
242 self,
243 obligation_args: I::GenericArgs,
244 impl_args: I::GenericArgs,
245 depth: usize,
246 ) -> bool {
247 iter::zip(obligation_args.iter(), impl_args.iter()).all(|(obl, imp)| {
251 match (obl.kind(), imp.kind()) {
252 (ty::GenericArgKind::Lifetime(_), ty::GenericArgKind::Lifetime(_)) => true,
254 (ty::GenericArgKind::Type(obl), ty::GenericArgKind::Type(imp)) => {
255 self.types_may_unify_inner(obl, imp, depth)
256 }
257 (ty::GenericArgKind::Const(obl), ty::GenericArgKind::Const(imp)) => {
258 self.consts_may_unify_inner(obl, imp)
259 }
260 _ => panic!("kind mismatch: {obl:?} {imp:?}"),
261 }
262 })
263 }
264
265 fn types_may_unify_inner(self, lhs: I::Ty, rhs: I::Ty, depth: usize) -> bool {
266 match rhs.kind() {
267 ty::Param(_) => {
270 if INSTANTIATE_RHS_WITH_INFER {
271 return true;
272 }
273 }
274 ty::Error(_) | ty::Alias(..) | ty::Bound(..) => return true,
275 ty::Infer(var) => return self.var_and_ty_may_unify(var, lhs),
276
277 ty::Bool
280 | ty::Char
281 | ty::Int(_)
282 | ty::Uint(_)
283 | ty::Float(_)
284 | ty::Adt(..)
285 | ty::Str
286 | ty::Array(..)
287 | ty::Slice(..)
288 | ty::RawPtr(..)
289 | ty::Dynamic(..)
290 | ty::Pat(..)
291 | ty::Ref(..)
292 | ty::Never
293 | ty::Tuple(..)
294 | ty::FnDef(..)
295 | ty::FnPtr(..)
296 | ty::Closure(..)
297 | ty::CoroutineClosure(..)
298 | ty::Coroutine(..)
299 | ty::CoroutineWitness(..)
300 | ty::Foreign(_)
301 | ty::Placeholder(_)
302 | ty::UnsafeBinder(_) => {}
303 };
304
305 let Some(depth) = depth.checked_sub(1) else {
315 return true;
316 };
317
318 match lhs.kind() {
320 ty::Ref(_, lhs_ty, lhs_mutbl) => match rhs.kind() {
321 ty::Ref(_, rhs_ty, rhs_mutbl) => {
322 lhs_mutbl == rhs_mutbl && self.types_may_unify_inner(lhs_ty, rhs_ty, depth)
323 }
324 _ => false,
325 },
326
327 ty::Adt(lhs_def, lhs_args) => match rhs.kind() {
328 ty::Adt(rhs_def, rhs_args) => {
329 lhs_def == rhs_def && self.args_may_unify_inner(lhs_args, rhs_args, depth)
330 }
331 _ => false,
332 },
333
334 ty::Param(lhs) => {
337 INSTANTIATE_LHS_WITH_INFER
338 || match rhs.kind() {
339 ty::Param(rhs) => lhs == rhs,
340 _ => false,
341 }
342 }
343
344 ty::Placeholder(lhs) => {
346 matches!(rhs.kind(), ty::Placeholder(rhs) if lhs == rhs)
347 }
348
349 ty::Infer(var) => self.var_and_ty_may_unify(var, rhs),
350
351 ty::Alias(..) => true,
357
358 ty::Int(_)
359 | ty::Uint(_)
360 | ty::Float(_)
361 | ty::Str
362 | ty::Bool
363 | ty::Char
364 | ty::Never
365 | ty::Foreign(_) => lhs == rhs,
366
367 ty::Tuple(lhs) => match rhs.kind() {
368 ty::Tuple(rhs) => {
369 lhs.len() == rhs.len()
370 && iter::zip(lhs.iter(), rhs.iter())
371 .all(|(lhs, rhs)| self.types_may_unify_inner(lhs, rhs, depth))
372 }
373 _ => false,
374 },
375
376 ty::Array(lhs_ty, lhs_len) => match rhs.kind() {
377 ty::Array(rhs_ty, rhs_len) => {
378 self.types_may_unify_inner(lhs_ty, rhs_ty, depth)
379 && self.consts_may_unify_inner(lhs_len, rhs_len)
380 }
381 _ => false,
382 },
383
384 ty::RawPtr(lhs_ty, lhs_mutbl) => match rhs.kind() {
385 ty::RawPtr(rhs_ty, rhs_mutbl) => {
386 lhs_mutbl == rhs_mutbl && self.types_may_unify_inner(lhs_ty, rhs_ty, depth)
387 }
388 _ => false,
389 },
390
391 ty::Slice(lhs_ty) => {
392 matches!(rhs.kind(), ty::Slice(rhs_ty) if self.types_may_unify_inner(lhs_ty, rhs_ty, depth))
393 }
394
395 ty::Dynamic(lhs_preds, ..) => {
396 matches!(rhs.kind(), ty::Dynamic(rhs_preds, ..) if
400 lhs_preds.principal_def_id() == rhs_preds.principal_def_id()
401 )
402 }
403
404 ty::FnPtr(lhs_sig_tys, lhs_hdr) => match rhs.kind() {
405 ty::FnPtr(rhs_sig_tys, rhs_hdr) => {
406 let lhs_sig_tys = lhs_sig_tys.skip_binder().inputs_and_output;
407 let rhs_sig_tys = rhs_sig_tys.skip_binder().inputs_and_output;
408
409 lhs_hdr == rhs_hdr
410 && lhs_sig_tys.len() == rhs_sig_tys.len()
411 && iter::zip(lhs_sig_tys.iter(), rhs_sig_tys.iter())
412 .all(|(lhs, rhs)| self.types_may_unify_inner(lhs, rhs, depth))
413 }
414 _ => false,
415 },
416
417 ty::Bound(..) => true,
418
419 ty::FnDef(lhs_def_id, lhs_args) => match rhs.kind() {
420 ty::FnDef(rhs_def_id, rhs_args) => {
421 lhs_def_id == rhs_def_id && self.args_may_unify_inner(lhs_args, rhs_args, depth)
422 }
423 _ => false,
424 },
425
426 ty::Closure(lhs_def_id, lhs_args) => match rhs.kind() {
427 ty::Closure(rhs_def_id, rhs_args) => {
428 lhs_def_id == rhs_def_id && self.args_may_unify_inner(lhs_args, rhs_args, depth)
429 }
430 _ => false,
431 },
432
433 ty::CoroutineClosure(lhs_def_id, lhs_args) => match rhs.kind() {
434 ty::CoroutineClosure(rhs_def_id, rhs_args) => {
435 lhs_def_id == rhs_def_id && self.args_may_unify_inner(lhs_args, rhs_args, depth)
436 }
437 _ => false,
438 },
439
440 ty::Coroutine(lhs_def_id, lhs_args) => match rhs.kind() {
441 ty::Coroutine(rhs_def_id, rhs_args) => {
442 lhs_def_id == rhs_def_id && self.args_may_unify_inner(lhs_args, rhs_args, depth)
443 }
444 _ => false,
445 },
446
447 ty::CoroutineWitness(lhs_def_id, lhs_args) => match rhs.kind() {
448 ty::CoroutineWitness(rhs_def_id, rhs_args) => {
449 lhs_def_id == rhs_def_id && self.args_may_unify_inner(lhs_args, rhs_args, depth)
450 }
451 _ => false,
452 },
453
454 ty::Pat(lhs_ty, _) => {
455 matches!(rhs.kind(), ty::Pat(rhs_ty, _) if self.types_may_unify_inner(lhs_ty, rhs_ty, depth))
457 }
458
459 ty::UnsafeBinder(lhs_ty) => match rhs.kind() {
460 ty::UnsafeBinder(rhs_ty) => {
461 self.types_may_unify(lhs_ty.skip_binder(), rhs_ty.skip_binder())
462 }
463 _ => false,
464 },
465
466 ty::Error(..) => true,
467 }
468 }
469
470 fn consts_may_unify_inner(self, lhs: I::Const, rhs: I::Const) -> bool {
473 match rhs.kind() {
474 ty::ConstKind::Param(_) => {
475 if INSTANTIATE_RHS_WITH_INFER {
476 return true;
477 }
478 }
479
480 ty::ConstKind::Expr(_)
481 | ty::ConstKind::Unevaluated(_)
482 | ty::ConstKind::Error(_)
483 | ty::ConstKind::Infer(_)
484 | ty::ConstKind::Bound(..) => {
485 return true;
486 }
487
488 ty::ConstKind::Value(..) | ty::ConstKind::Placeholder(_) => {}
489 };
490
491 match lhs.kind() {
492 ty::ConstKind::Value(lhs_val) => match rhs.kind() {
493 ty::ConstKind::Value(rhs_val) => lhs_val.valtree() == rhs_val.valtree(),
494 _ => false,
495 },
496
497 ty::ConstKind::Param(lhs) => {
498 INSTANTIATE_LHS_WITH_INFER
499 || match rhs.kind() {
500 ty::ConstKind::Param(rhs) => lhs == rhs,
501 _ => false,
502 }
503 }
504
505 ty::ConstKind::Placeholder(lhs) => {
507 matches!(rhs.kind(), ty::ConstKind::Placeholder(rhs) if lhs == rhs)
508 }
509
510 ty::ConstKind::Expr(_) | ty::ConstKind::Unevaluated(_) | ty::ConstKind::Error(_) => {
513 true
514 }
515
516 ty::ConstKind::Infer(_) | ty::ConstKind::Bound(..) => true,
517 }
518 }
519
520 fn var_and_ty_may_unify(self, var: ty::InferTy, ty: I::Ty) -> bool {
521 if !ty.is_known_rigid() {
522 return true;
523 }
524
525 match var {
526 ty::IntVar(_) => ty.is_integral(),
527 ty::FloatVar(_) => ty.is_floating_point(),
528 _ => true,
529 }
530 }
531}