1use std::fmt;
45use std::ops::ControlFlow;
46use std::sync::Arc;
47
48use rustc_ast_ir::visit::VisitorResult;
49use rustc_ast_ir::{try_visit, walk_visitable_list};
50use rustc_index::{Idx, IndexVec};
51use smallvec::SmallVec;
52use thin_vec::ThinVec;
53
54use crate::inherent::*;
55use crate::{self as ty, Interner, TypeFlags};
56
57pub trait TypeVisitable<I: Interner>: fmt::Debug {
63 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result;
74}
75
76pub trait TypeSuperVisitable<I: Interner>: TypeVisitable<I> {
78 fn super_visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result;
85}
86
87pub trait TypeVisitor<I: Interner>: Sized {
91 #[cfg(feature = "nightly")]
92 type Result: VisitorResult = ();
93
94 #[cfg(not(feature = "nightly"))]
95 type Result: VisitorResult;
96
97 fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
98 t.super_visit_with(self)
99 }
100
101 fn visit_ty(&mut self, t: I::Ty) -> Self::Result {
102 t.super_visit_with(self)
103 }
104
105 fn visit_region(&mut self, r: I::Region) -> Self::Result {
108 if let ty::ReError(guar) = r.kind() {
109 self.visit_error(guar)
110 } else {
111 Self::Result::output()
112 }
113 }
114
115 fn visit_const(&mut self, c: I::Const) -> Self::Result {
116 c.super_visit_with(self)
117 }
118
119 fn visit_predicate(&mut self, p: I::Predicate) -> Self::Result {
120 p.super_visit_with(self)
121 }
122
123 fn visit_clauses(&mut self, p: I::Clauses) -> Self::Result {
124 p.super_visit_with(self)
125 }
126
127 fn visit_error(&mut self, _guar: I::ErrorGuaranteed) -> Self::Result {
128 Self::Result::output()
129 }
130}
131
132impl<I: Interner, T: TypeVisitable<I>, U: TypeVisitable<I>> TypeVisitable<I> for (T, U) {
136 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
137 try_visit!(self.0.visit_with(visitor));
138 self.1.visit_with(visitor)
139 }
140}
141
142impl<I: Interner, A: TypeVisitable<I>, B: TypeVisitable<I>, C: TypeVisitable<I>> TypeVisitable<I>
143 for (A, B, C)
144{
145 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
146 try_visit!(self.0.visit_with(visitor));
147 try_visit!(self.1.visit_with(visitor));
148 self.2.visit_with(visitor)
149 }
150}
151
152impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Option<T> {
153 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
154 match self {
155 Some(v) => v.visit_with(visitor),
156 None => V::Result::output(),
157 }
158 }
159}
160
161impl<I: Interner, T: TypeVisitable<I>, E: TypeVisitable<I>> TypeVisitable<I> for Result<T, E> {
162 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
163 match self {
164 Ok(v) => v.visit_with(visitor),
165 Err(e) => e.visit_with(visitor),
166 }
167 }
168}
169
170impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Arc<T> {
171 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
172 (**self).visit_with(visitor)
173 }
174}
175
176impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Box<T> {
177 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
178 (**self).visit_with(visitor)
179 }
180}
181
182impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Vec<T> {
183 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
184 walk_visitable_list!(visitor, self.iter());
185 V::Result::output()
186 }
187}
188
189impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for ThinVec<T> {
190 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
191 walk_visitable_list!(visitor, self.iter());
192 V::Result::output()
193 }
194}
195
196impl<I: Interner, T: TypeVisitable<I>, const N: usize> TypeVisitable<I> for SmallVec<[T; N]> {
197 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
198 walk_visitable_list!(visitor, self.iter());
199 V::Result::output()
200 }
201}
202
203impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for &[T] {
207 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
208 walk_visitable_list!(visitor, self.iter());
209 V::Result::output()
210 }
211}
212
213impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Box<[T]> {
214 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
215 walk_visitable_list!(visitor, self.iter());
216 V::Result::output()
217 }
218}
219
220impl<I: Interner, T: TypeVisitable<I>, Ix: Idx> TypeVisitable<I> for IndexVec<Ix, T> {
221 fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
222 walk_visitable_list!(visitor, self.iter());
223 V::Result::output()
224 }
225}
226
227pub trait Flags {
228 fn flags(&self) -> TypeFlags;
229 fn outer_exclusive_binder(&self) -> ty::DebruijnIndex;
230}
231
232pub trait TypeVisitableExt<I: Interner>: TypeVisitable<I> {
233 fn has_type_flags(&self, flags: TypeFlags) -> bool;
234
235 fn has_vars_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool;
240
241 fn has_vars_bound_above(&self, binder: ty::DebruijnIndex) -> bool {
244 self.has_vars_bound_at_or_above(binder.shifted_in(1))
245 }
246
247 fn has_escaping_bound_vars(&self) -> bool {
254 self.has_vars_bound_at_or_above(ty::INNERMOST)
255 }
256
257 fn has_aliases(&self) -> bool {
258 self.has_type_flags(TypeFlags::HAS_ALIAS)
259 }
260
261 fn has_opaque_types(&self) -> bool {
262 self.has_type_flags(TypeFlags::HAS_TY_OPAQUE)
263 }
264
265 fn has_coroutines(&self) -> bool {
266 self.has_type_flags(TypeFlags::HAS_TY_COROUTINE)
267 }
268
269 fn references_error(&self) -> bool {
270 self.has_type_flags(TypeFlags::HAS_ERROR)
271 }
272
273 fn error_reported(&self) -> Result<(), I::ErrorGuaranteed>;
274
275 fn has_non_region_param(&self) -> bool {
276 self.has_type_flags(TypeFlags::HAS_PARAM - TypeFlags::HAS_RE_PARAM)
277 }
278
279 fn has_infer_regions(&self) -> bool {
280 self.has_type_flags(TypeFlags::HAS_RE_INFER)
281 }
282
283 fn has_infer_types(&self) -> bool {
284 self.has_type_flags(TypeFlags::HAS_TY_INFER)
285 }
286
287 fn has_non_region_infer(&self) -> bool {
288 self.has_type_flags(TypeFlags::HAS_INFER - TypeFlags::HAS_RE_INFER)
289 }
290
291 fn has_infer(&self) -> bool {
292 self.has_type_flags(TypeFlags::HAS_INFER)
293 }
294
295 fn has_placeholders(&self) -> bool {
296 self.has_type_flags(TypeFlags::HAS_PLACEHOLDER)
297 }
298
299 fn has_non_region_placeholders(&self) -> bool {
300 self.has_type_flags(TypeFlags::HAS_PLACEHOLDER - TypeFlags::HAS_RE_PLACEHOLDER)
301 }
302
303 fn has_param(&self) -> bool {
304 self.has_type_flags(TypeFlags::HAS_PARAM)
305 }
306
307 fn has_free_regions(&self) -> bool {
310 self.has_type_flags(TypeFlags::HAS_FREE_REGIONS)
311 }
312
313 fn has_erased_regions(&self) -> bool {
314 self.has_type_flags(TypeFlags::HAS_RE_ERASED)
315 }
316
317 fn has_erasable_regions(&self) -> bool {
319 self.has_type_flags(TypeFlags::HAS_FREE_REGIONS)
320 }
321
322 fn is_global(&self) -> bool {
326 !self.has_type_flags(TypeFlags::HAS_FREE_LOCAL_NAMES)
327 }
328
329 fn has_bound_regions(&self) -> bool {
331 self.has_type_flags(TypeFlags::HAS_RE_BOUND)
332 }
333 fn has_non_region_bound_vars(&self) -> bool {
335 self.has_type_flags(TypeFlags::HAS_BOUND_VARS - TypeFlags::HAS_RE_BOUND)
336 }
337 fn has_bound_vars(&self) -> bool {
339 self.has_type_flags(TypeFlags::HAS_BOUND_VARS)
340 }
341
342 fn still_further_specializable(&self) -> bool {
346 self.has_type_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE)
347 }
348}
349
350impl<I: Interner, T: TypeVisitable<I>> TypeVisitableExt<I> for T {
351 fn has_type_flags(&self, flags: TypeFlags) -> bool {
352 let res =
353 self.visit_with(&mut HasTypeFlagsVisitor { flags }) == ControlFlow::Break(FoundFlags);
354 res
355 }
356
357 fn has_vars_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool {
358 self.visit_with(&mut HasEscapingVarsVisitor { outer_index: binder }).is_break()
359 }
360
361 fn error_reported(&self) -> Result<(), I::ErrorGuaranteed> {
362 if self.references_error() {
363 if let ControlFlow::Break(guar) = self.visit_with(&mut HasErrorVisitor) {
364 Err(guar)
365 } else {
366 panic!("type flags said there was an error, but now there is not")
367 }
368 } else {
369 Ok(())
370 }
371 }
372}
373
374#[derive(Debug, PartialEq, Eq, Copy, Clone)]
375struct FoundFlags;
376
377struct HasTypeFlagsVisitor {
379 flags: ty::TypeFlags,
380}
381
382impl std::fmt::Debug for HasTypeFlagsVisitor {
383 fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
384 self.flags.fmt(fmt)
385 }
386}
387
388impl<I: Interner> TypeVisitor<I> for HasTypeFlagsVisitor {
399 type Result = ControlFlow<FoundFlags>;
400
401 fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
402 if self.flags.intersects(TypeFlags::HAS_BINDER_VARS) && !t.bound_vars().is_empty() {
406 return ControlFlow::Break(FoundFlags);
407 }
408
409 t.super_visit_with(self)
410 }
411
412 #[inline]
413 fn visit_ty(&mut self, t: I::Ty) -> Self::Result {
414 let flags = t.flags();
416 if flags.intersects(self.flags) {
417 ControlFlow::Break(FoundFlags)
418 } else {
419 ControlFlow::Continue(())
420 }
421 }
422
423 #[inline]
424 fn visit_region(&mut self, r: I::Region) -> Self::Result {
425 let flags = r.flags();
427 if flags.intersects(self.flags) {
428 ControlFlow::Break(FoundFlags)
429 } else {
430 ControlFlow::Continue(())
431 }
432 }
433
434 #[inline]
435 fn visit_const(&mut self, c: I::Const) -> Self::Result {
436 if c.flags().intersects(self.flags) {
438 ControlFlow::Break(FoundFlags)
439 } else {
440 ControlFlow::Continue(())
441 }
442 }
443
444 #[inline]
445 fn visit_predicate(&mut self, predicate: I::Predicate) -> Self::Result {
446 if predicate.flags().intersects(self.flags) {
448 ControlFlow::Break(FoundFlags)
449 } else {
450 ControlFlow::Continue(())
451 }
452 }
453
454 #[inline]
455 fn visit_clauses(&mut self, clauses: I::Clauses) -> Self::Result {
456 if clauses.flags().intersects(self.flags) {
458 ControlFlow::Break(FoundFlags)
459 } else {
460 ControlFlow::Continue(())
461 }
462 }
463
464 #[inline]
465 fn visit_error(&mut self, _guar: <I as Interner>::ErrorGuaranteed) -> Self::Result {
466 if self.flags.intersects(TypeFlags::HAS_ERROR) {
467 ControlFlow::Break(FoundFlags)
468 } else {
469 ControlFlow::Continue(())
470 }
471 }
472}
473
474#[derive(Debug, PartialEq, Eq, Copy, Clone)]
475struct FoundEscapingVars;
476
477struct HasEscapingVarsVisitor {
503 outer_index: ty::DebruijnIndex,
505}
506
507impl<I: Interner> TypeVisitor<I> for HasEscapingVarsVisitor {
508 type Result = ControlFlow<FoundEscapingVars>;
509
510 fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
511 self.outer_index.shift_in(1);
512 let result = t.super_visit_with(self);
513 self.outer_index.shift_out(1);
514 result
515 }
516
517 #[inline]
518 fn visit_ty(&mut self, t: I::Ty) -> Self::Result {
519 if t.outer_exclusive_binder() > self.outer_index {
525 ControlFlow::Break(FoundEscapingVars)
526 } else {
527 ControlFlow::Continue(())
528 }
529 }
530
531 #[inline]
532 fn visit_region(&mut self, r: I::Region) -> Self::Result {
533 if r.outer_exclusive_binder() > self.outer_index {
537 ControlFlow::Break(FoundEscapingVars)
538 } else {
539 ControlFlow::Continue(())
540 }
541 }
542
543 fn visit_const(&mut self, ct: I::Const) -> Self::Result {
544 if ct.outer_exclusive_binder() > self.outer_index {
550 ControlFlow::Break(FoundEscapingVars)
551 } else {
552 ControlFlow::Continue(())
553 }
554 }
555
556 #[inline]
557 fn visit_predicate(&mut self, predicate: I::Predicate) -> Self::Result {
558 if predicate.outer_exclusive_binder() > self.outer_index {
559 ControlFlow::Break(FoundEscapingVars)
560 } else {
561 ControlFlow::Continue(())
562 }
563 }
564
565 #[inline]
566 fn visit_clauses(&mut self, clauses: I::Clauses) -> Self::Result {
567 if clauses.outer_exclusive_binder() > self.outer_index {
568 ControlFlow::Break(FoundEscapingVars)
569 } else {
570 ControlFlow::Continue(())
571 }
572 }
573}
574
575struct HasErrorVisitor;
576
577impl<I: Interner> TypeVisitor<I> for HasErrorVisitor {
578 type Result = ControlFlow<I::ErrorGuaranteed>;
579
580 fn visit_error(&mut self, guar: <I as Interner>::ErrorGuaranteed) -> Self::Result {
581 ControlFlow::Break(guar)
582 }
583}