clippy_utils/ty/
mod.rs

1//! Util methods for [`rustc_middle::ty`]
2
3#![allow(clippy::module_name_repetitions)]
4
5use core::ops::ControlFlow;
6use itertools::Itertools;
7use rustc_abi::VariantIdx;
8use rustc_ast::ast::Mutability;
9use rustc_data_structures::fx::{FxHashMap, FxHashSet};
10use rustc_hir as hir;
11use rustc_hir::def::{CtorKind, CtorOf, DefKind, Res};
12use rustc_hir::def_id::DefId;
13use rustc_hir::{Expr, FnDecl, LangItem, TyKind};
14use rustc_hir_analysis::lower_ty;
15use rustc_infer::infer::TyCtxtInferExt;
16use rustc_lint::LateContext;
17use rustc_middle::mir::ConstValue;
18use rustc_middle::mir::interpret::Scalar;
19use rustc_middle::traits::EvaluationResult;
20use rustc_middle::ty::layout::ValidityRequirement;
21use rustc_middle::ty::{
22    self, AdtDef, AliasTy, AssocItem, AssocTag, Binder, BoundRegion, FnSig, GenericArg, GenericArgKind, GenericArgsRef,
23    GenericParamDefKind, IntTy, Region, RegionKind, TraitRef, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable,
24    TypeVisitable, TypeVisitableExt, TypeVisitor, UintTy, Upcast, VariantDef, VariantDiscr,
25};
26use rustc_span::symbol::Ident;
27use rustc_span::{DUMMY_SP, Span, Symbol, sym};
28use rustc_trait_selection::traits::query::evaluate_obligation::InferCtxtExt as _;
29use rustc_trait_selection::traits::query::normalize::QueryNormalizeExt;
30use rustc_trait_selection::traits::{Obligation, ObligationCause};
31use std::assert_matches::debug_assert_matches;
32use std::collections::hash_map::Entry;
33use std::iter;
34
35use crate::path_res;
36use crate::paths::{PathNS, lookup_path_str};
37
38mod type_certainty;
39pub use type_certainty::expr_type_is_certain;
40
41/// Lower a [`hir::Ty`] to a [`rustc_middle::ty::Ty`].
42pub fn ty_from_hir_ty<'tcx>(cx: &LateContext<'tcx>, hir_ty: &hir::Ty<'tcx>) -> Ty<'tcx> {
43    cx.maybe_typeck_results()
44        .and_then(|results| {
45            if results.hir_owner == hir_ty.hir_id.owner {
46                results.node_type_opt(hir_ty.hir_id)
47            } else {
48                None
49            }
50        })
51        .unwrap_or_else(|| lower_ty(cx.tcx, hir_ty))
52}
53
54/// Checks if the given type implements copy.
55pub fn is_copy<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
56    cx.type_is_copy_modulo_regions(ty)
57}
58
59/// This checks whether a given type is known to implement Debug.
60pub fn has_debug_impl<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
61    cx.tcx
62        .get_diagnostic_item(sym::Debug)
63        .is_some_and(|debug| implements_trait(cx, ty, debug, &[]))
64}
65
66/// Checks whether a type can be partially moved.
67pub fn can_partially_move_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
68    if has_drop(cx, ty) || is_copy(cx, ty) {
69        return false;
70    }
71    match ty.kind() {
72        ty::Param(_) => false,
73        ty::Adt(def, subs) => def.all_fields().any(|f| !is_copy(cx, f.ty(cx.tcx, subs))),
74        _ => true,
75    }
76}
77
78/// Walks into `ty` and returns `true` if any inner type is an instance of the given adt
79/// constructor.
80pub fn contains_adt_constructor<'tcx>(ty: Ty<'tcx>, adt: AdtDef<'tcx>) -> bool {
81    ty.walk().any(|inner| match inner.kind() {
82        GenericArgKind::Type(inner_ty) => inner_ty.ty_adt_def() == Some(adt),
83        GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => false,
84    })
85}
86
87/// Walks into `ty` and returns `true` if any inner type is an instance of the given type, or adt
88/// constructor of the same type.
89///
90/// This method also recurses into opaque type predicates, so call it with `impl Trait<U>` and `U`
91/// will also return `true`.
92pub fn contains_ty_adt_constructor_opaque<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>, needle: Ty<'tcx>) -> bool {
93    fn contains_ty_adt_constructor_opaque_inner<'tcx>(
94        cx: &LateContext<'tcx>,
95        ty: Ty<'tcx>,
96        needle: Ty<'tcx>,
97        seen: &mut FxHashSet<DefId>,
98    ) -> bool {
99        ty.walk().any(|inner| match inner.kind() {
100            GenericArgKind::Type(inner_ty) => {
101                if inner_ty == needle {
102                    return true;
103                }
104
105                if inner_ty.ty_adt_def() == needle.ty_adt_def() {
106                    return true;
107                }
108
109                if let ty::Alias(ty::Opaque, AliasTy { def_id, .. }) = *inner_ty.kind() {
110                    if !seen.insert(def_id) {
111                        return false;
112                    }
113
114                    for (predicate, _span) in cx.tcx.explicit_item_self_bounds(def_id).iter_identity_copied() {
115                        match predicate.kind().skip_binder() {
116                            // For `impl Trait<U>`, it will register a predicate of `T: Trait<U>`, so we go through
117                            // and check substitutions to find `U`.
118                            ty::ClauseKind::Trait(trait_predicate) => {
119                                if trait_predicate
120                                    .trait_ref
121                                    .args
122                                    .types()
123                                    .skip(1) // Skip the implicit `Self` generic parameter
124                                    .any(|ty| contains_ty_adt_constructor_opaque_inner(cx, ty, needle, seen))
125                                {
126                                    return true;
127                                }
128                            },
129                            // For `impl Trait<Assoc=U>`, it will register a predicate of `<T as Trait>::Assoc = U`,
130                            // so we check the term for `U`.
131                            ty::ClauseKind::Projection(projection_predicate) => {
132                                if let ty::TermKind::Ty(ty) = projection_predicate.term.kind()
133                                    && contains_ty_adt_constructor_opaque_inner(cx, ty, needle, seen)
134                                {
135                                    return true;
136                                }
137                            },
138                            _ => (),
139                        }
140                    }
141                }
142
143                false
144            },
145            GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => false,
146        })
147    }
148
149    // A hash set to ensure that the same opaque type (`impl Trait` in RPIT or TAIT) is not
150    // visited twice.
151    let mut seen = FxHashSet::default();
152    contains_ty_adt_constructor_opaque_inner(cx, ty, needle, &mut seen)
153}
154
155/// Resolves `<T as Iterator>::Item` for `T`
156/// Do not invoke without first verifying that the type implements `Iterator`
157pub fn get_iterator_item_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
158    cx.tcx
159        .get_diagnostic_item(sym::Iterator)
160        .and_then(|iter_did| cx.get_associated_type(ty, iter_did, sym::Item))
161}
162
163/// Get the diagnostic name of a type, e.g. `sym::HashMap`. To check if a type
164/// implements a trait marked with a diagnostic item use [`implements_trait`].
165///
166/// For a further exploitation what diagnostic items are see [diagnostic items] in
167/// rustc-dev-guide.
168///
169/// [Diagnostic Items]: https://rustc-dev-guide.rust-lang.org/diagnostics/diagnostic-items.html
170pub fn get_type_diagnostic_name(cx: &LateContext<'_>, ty: Ty<'_>) -> Option<Symbol> {
171    match ty.kind() {
172        ty::Adt(adt, _) => cx.tcx.get_diagnostic_name(adt.did()),
173        _ => None,
174    }
175}
176
177/// Returns true if `ty` is a type on which calling `Clone` through a function instead of
178/// as a method, such as `Arc::clone()` is considered idiomatic.
179///
180/// Lints should avoid suggesting to replace instances of `ty::Clone()` by `.clone()` for objects
181/// of those types.
182pub fn should_call_clone_as_function(cx: &LateContext<'_>, ty: Ty<'_>) -> bool {
183    matches!(
184        get_type_diagnostic_name(cx, ty),
185        Some(sym::Arc | sym::ArcWeak | sym::Rc | sym::RcWeak)
186    )
187}
188
189/// If `ty` is known to have a `iter` or `iter_mut` method, returns a symbol representing the type.
190pub fn has_iter_method(cx: &LateContext<'_>, probably_ref_ty: Ty<'_>) -> Option<Symbol> {
191    // FIXME: instead of this hard-coded list, we should check if `<adt>::iter`
192    // exists and has the desired signature. Unfortunately FnCtxt is not exported
193    // so we can't use its `lookup_method` method.
194    let into_iter_collections: &[Symbol] = &[
195        sym::Vec,
196        sym::Option,
197        sym::Result,
198        sym::BTreeMap,
199        sym::BTreeSet,
200        sym::VecDeque,
201        sym::LinkedList,
202        sym::BinaryHeap,
203        sym::HashSet,
204        sym::HashMap,
205        sym::PathBuf,
206        sym::Path,
207        sym::Receiver,
208    ];
209
210    let ty_to_check = match probably_ref_ty.kind() {
211        ty::Ref(_, ty_to_check, _) => *ty_to_check,
212        _ => probably_ref_ty,
213    };
214
215    let def_id = match ty_to_check.kind() {
216        ty::Array(..) => return Some(sym::array),
217        ty::Slice(..) => return Some(sym::slice),
218        ty::Adt(adt, _) => adt.did(),
219        _ => return None,
220    };
221
222    for &name in into_iter_collections {
223        if cx.tcx.is_diagnostic_item(name, def_id) {
224            return Some(cx.tcx.item_name(def_id));
225        }
226    }
227    None
228}
229
230/// Checks whether a type implements a trait.
231/// The function returns false in case the type contains an inference variable.
232///
233/// See [Common tools for writing lints] for an example how to use this function and other options.
234///
235/// [Common tools for writing lints]: https://github.com/rust-lang/rust-clippy/blob/master/book/src/development/common_tools_writing_lints.md#checking-if-a-type-implements-a-specific-trait
236pub fn implements_trait<'tcx>(
237    cx: &LateContext<'tcx>,
238    ty: Ty<'tcx>,
239    trait_id: DefId,
240    args: &[GenericArg<'tcx>],
241) -> bool {
242    implements_trait_with_env_from_iter(
243        cx.tcx,
244        cx.typing_env(),
245        ty,
246        trait_id,
247        None,
248        args.iter().map(|&x| Some(x)),
249    )
250}
251
252/// Same as `implements_trait` but allows using a `ParamEnv` different from the lint context.
253///
254/// The `callee_id` argument is used to determine whether this is a function call in a `const fn`
255/// environment, used for checking const traits.
256pub fn implements_trait_with_env<'tcx>(
257    tcx: TyCtxt<'tcx>,
258    typing_env: ty::TypingEnv<'tcx>,
259    ty: Ty<'tcx>,
260    trait_id: DefId,
261    callee_id: Option<DefId>,
262    args: &[GenericArg<'tcx>],
263) -> bool {
264    implements_trait_with_env_from_iter(tcx, typing_env, ty, trait_id, callee_id, args.iter().map(|&x| Some(x)))
265}
266
267/// Same as `implements_trait_from_env` but takes the arguments as an iterator.
268pub fn implements_trait_with_env_from_iter<'tcx>(
269    tcx: TyCtxt<'tcx>,
270    typing_env: ty::TypingEnv<'tcx>,
271    ty: Ty<'tcx>,
272    trait_id: DefId,
273    callee_id: Option<DefId>,
274    args: impl IntoIterator<Item = impl Into<Option<GenericArg<'tcx>>>>,
275) -> bool {
276    // Clippy shouldn't have infer types
277    assert!(!ty.has_infer());
278
279    // If a `callee_id` is passed, then we assert that it is a body owner
280    // through calling `body_owner_kind`, which would panic if the callee
281    // does not have a body.
282    if let Some(callee_id) = callee_id {
283        let _ = tcx.hir_body_owner_kind(callee_id);
284    }
285
286    let ty = tcx.erase_regions(ty);
287    if ty.has_escaping_bound_vars() {
288        return false;
289    }
290
291    let (infcx, param_env) = tcx.infer_ctxt().build_with_typing_env(typing_env);
292    let args = args
293        .into_iter()
294        .map(|arg| arg.into().unwrap_or_else(|| infcx.next_ty_var(DUMMY_SP).into()))
295        .collect::<Vec<_>>();
296
297    let trait_ref = TraitRef::new(tcx, trait_id, [GenericArg::from(ty)].into_iter().chain(args));
298
299    debug_assert_matches!(
300        tcx.def_kind(trait_id),
301        DefKind::Trait | DefKind::TraitAlias,
302        "`DefId` must belong to a trait or trait alias"
303    );
304    #[cfg(debug_assertions)]
305    assert_generic_args_match(tcx, trait_id, trait_ref.args);
306
307    let obligation = Obligation {
308        cause: ObligationCause::dummy(),
309        param_env,
310        recursion_depth: 0,
311        predicate: trait_ref.upcast(tcx),
312    };
313    infcx
314        .evaluate_obligation(&obligation)
315        .is_ok_and(EvaluationResult::must_apply_modulo_regions)
316}
317
318/// Checks whether this type implements `Drop`.
319pub fn has_drop<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
320    match ty.ty_adt_def() {
321        Some(def) => def.has_dtor(cx.tcx),
322        None => false,
323    }
324}
325
326// Returns whether the type has #[must_use] attribute
327pub fn is_must_use_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
328    match ty.kind() {
329        ty::Adt(adt, _) => cx.tcx.has_attr(adt.did(), sym::must_use),
330        ty::Foreign(did) => cx.tcx.has_attr(*did, sym::must_use),
331        ty::Slice(ty) | ty::Array(ty, _) | ty::RawPtr(ty, _) | ty::Ref(_, ty, _) => {
332            // for the Array case we don't need to care for the len == 0 case
333            // because we don't want to lint functions returning empty arrays
334            is_must_use_ty(cx, *ty)
335        },
336        ty::Tuple(args) => args.iter().any(|ty| is_must_use_ty(cx, ty)),
337        ty::Alias(ty::Opaque, AliasTy { def_id, .. }) => {
338            for (predicate, _) in cx.tcx.explicit_item_self_bounds(def_id).skip_binder() {
339                if let ty::ClauseKind::Trait(trait_predicate) = predicate.kind().skip_binder()
340                    && cx.tcx.has_attr(trait_predicate.trait_ref.def_id, sym::must_use)
341                {
342                    return true;
343                }
344            }
345            false
346        },
347        ty::Dynamic(binder, _, _) => {
348            for predicate in *binder {
349                if let ty::ExistentialPredicate::Trait(ref trait_ref) = predicate.skip_binder()
350                    && cx.tcx.has_attr(trait_ref.def_id, sym::must_use)
351                {
352                    return true;
353                }
354            }
355            false
356        },
357        _ => false,
358    }
359}
360
361/// Returns `true` if the given type is a non aggregate primitive (a `bool` or `char`, any
362/// integer or floating-point number type).
363///
364/// For checking aggregation of primitive types (e.g. tuples and slices of primitive type) see
365/// `is_recursively_primitive_type`
366pub fn is_non_aggregate_primitive_type(ty: Ty<'_>) -> bool {
367    matches!(ty.kind(), ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_))
368}
369
370/// Returns `true` if the given type is a primitive (a `bool` or `char`, any integer or
371/// floating-point number type, a `str`, or an array, slice, or tuple of those types).
372pub fn is_recursively_primitive_type(ty: Ty<'_>) -> bool {
373    match *ty.kind() {
374        ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Str => true,
375        ty::Ref(_, inner, _) if inner.is_str() => true,
376        ty::Array(inner_type, _) | ty::Slice(inner_type) => is_recursively_primitive_type(inner_type),
377        ty::Tuple(inner_types) => inner_types.iter().all(is_recursively_primitive_type),
378        _ => false,
379    }
380}
381
382/// Checks if the type is a reference equals to a diagnostic item
383pub fn is_type_ref_to_diagnostic_item(cx: &LateContext<'_>, ty: Ty<'_>, diag_item: Symbol) -> bool {
384    match ty.kind() {
385        ty::Ref(_, ref_ty, _) => match ref_ty.kind() {
386            ty::Adt(adt, _) => cx.tcx.is_diagnostic_item(diag_item, adt.did()),
387            _ => false,
388        },
389        _ => false,
390    }
391}
392
393/// Checks if the type is equal to a diagnostic item. To check if a type implements a
394/// trait marked with a diagnostic item use [`implements_trait`].
395///
396/// For a further exploitation what diagnostic items are see [diagnostic items] in
397/// rustc-dev-guide.
398///
399/// ---
400///
401/// If you change the signature, remember to update the internal lint `MatchTypeOnDiagItem`
402///
403/// [Diagnostic Items]: https://rustc-dev-guide.rust-lang.org/diagnostics/diagnostic-items.html
404pub fn is_type_diagnostic_item(cx: &LateContext<'_>, ty: Ty<'_>, diag_item: Symbol) -> bool {
405    match ty.kind() {
406        ty::Adt(adt, _) => cx.tcx.is_diagnostic_item(diag_item, adt.did()),
407        _ => false,
408    }
409}
410
411/// Checks if the type is equal to a lang item.
412///
413/// Returns `false` if the `LangItem` is not defined.
414pub fn is_type_lang_item(cx: &LateContext<'_>, ty: Ty<'_>, lang_item: LangItem) -> bool {
415    match ty.kind() {
416        ty::Adt(adt, _) => cx.tcx.lang_items().get(lang_item) == Some(adt.did()),
417        _ => false,
418    }
419}
420
421/// Return `true` if the passed `typ` is `isize` or `usize`.
422pub fn is_isize_or_usize(typ: Ty<'_>) -> bool {
423    matches!(typ.kind(), ty::Int(IntTy::Isize) | ty::Uint(UintTy::Usize))
424}
425
426/// Checks if the drop order for a type matters.
427///
428/// Some std types implement drop solely to deallocate memory. For these types, and composites
429/// containing them, changing the drop order won't result in any observable side effects.
430pub fn needs_ordered_drop<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
431    fn needs_ordered_drop_inner<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>, seen: &mut FxHashSet<Ty<'tcx>>) -> bool {
432        if !seen.insert(ty) {
433            return false;
434        }
435        if !ty.has_significant_drop(cx.tcx, cx.typing_env()) {
436            false
437        }
438        // Check for std types which implement drop, but only for memory allocation.
439        else if is_type_lang_item(cx, ty, LangItem::OwnedBox)
440            || matches!(
441                get_type_diagnostic_name(cx, ty),
442                Some(sym::HashSet | sym::Rc | sym::Arc | sym::cstring_type | sym::RcWeak | sym::ArcWeak)
443            )
444        {
445            // Check all of the generic arguments.
446            if let ty::Adt(_, subs) = ty.kind() {
447                subs.types().any(|ty| needs_ordered_drop_inner(cx, ty, seen))
448            } else {
449                true
450            }
451        } else if !cx
452            .tcx
453            .lang_items()
454            .drop_trait()
455            .is_some_and(|id| implements_trait(cx, ty, id, &[]))
456        {
457            // This type doesn't implement drop, so no side effects here.
458            // Check if any component type has any.
459            match ty.kind() {
460                ty::Tuple(fields) => fields.iter().any(|ty| needs_ordered_drop_inner(cx, ty, seen)),
461                ty::Array(ty, _) => needs_ordered_drop_inner(cx, *ty, seen),
462                ty::Adt(adt, subs) => adt
463                    .all_fields()
464                    .map(|f| f.ty(cx.tcx, subs))
465                    .any(|ty| needs_ordered_drop_inner(cx, ty, seen)),
466                _ => true,
467            }
468        } else {
469            true
470        }
471    }
472
473    needs_ordered_drop_inner(cx, ty, &mut FxHashSet::default())
474}
475
476/// Peels off all references on the type. Returns the underlying type, the number of references
477/// removed, and whether the pointer is ultimately mutable or not.
478pub fn peel_mid_ty_refs_is_mutable(ty: Ty<'_>) -> (Ty<'_>, usize, Mutability) {
479    fn f(ty: Ty<'_>, count: usize, mutability: Mutability) -> (Ty<'_>, usize, Mutability) {
480        match ty.kind() {
481            ty::Ref(_, ty, Mutability::Mut) => f(*ty, count + 1, mutability),
482            ty::Ref(_, ty, Mutability::Not) => f(*ty, count + 1, Mutability::Not),
483            _ => (ty, count, mutability),
484        }
485    }
486    f(ty, 0, Mutability::Mut)
487}
488
489/// Returns `true` if the given type is an `unsafe` function.
490pub fn type_is_unsafe_function<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
491    match ty.kind() {
492        ty::FnDef(..) | ty::FnPtr(..) => ty.fn_sig(cx.tcx).safety().is_unsafe(),
493        _ => false,
494    }
495}
496
497/// Returns the base type for HIR references and pointers.
498pub fn walk_ptrs_hir_ty<'tcx>(ty: &'tcx hir::Ty<'tcx>) -> &'tcx hir::Ty<'tcx> {
499    match ty.kind {
500        TyKind::Ptr(ref mut_ty) | TyKind::Ref(_, ref mut_ty) => walk_ptrs_hir_ty(mut_ty.ty),
501        _ => ty,
502    }
503}
504
505/// Returns the base type for references and raw pointers, and count reference
506/// depth.
507pub fn walk_ptrs_ty_depth(ty: Ty<'_>) -> (Ty<'_>, usize) {
508    fn inner(ty: Ty<'_>, depth: usize) -> (Ty<'_>, usize) {
509        match ty.kind() {
510            ty::Ref(_, ty, _) => inner(*ty, depth + 1),
511            _ => (ty, depth),
512        }
513    }
514    inner(ty, 0)
515}
516
517/// Returns `true` if types `a` and `b` are same types having same `Const` generic args,
518/// otherwise returns `false`
519pub fn same_type_and_consts<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
520    match (&a.kind(), &b.kind()) {
521        (&ty::Adt(did_a, args_a), &ty::Adt(did_b, args_b)) => {
522            if did_a != did_b {
523                return false;
524            }
525
526            args_a
527                .iter()
528                .zip(args_b.iter())
529                .all(|(arg_a, arg_b)| match (arg_a.kind(), arg_b.kind()) {
530                    (GenericArgKind::Const(inner_a), GenericArgKind::Const(inner_b)) => inner_a == inner_b,
531                    (GenericArgKind::Type(type_a), GenericArgKind::Type(type_b)) => {
532                        same_type_and_consts(type_a, type_b)
533                    },
534                    _ => true,
535                })
536        },
537        _ => a == b,
538    }
539}
540
541/// Checks if a given type looks safe to be uninitialized.
542pub fn is_uninit_value_valid_for_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
543    let typing_env = cx.typing_env().with_post_analysis_normalized(cx.tcx);
544    cx.tcx
545        .check_validity_requirement((ValidityRequirement::Uninit, typing_env.as_query_input(ty)))
546        .unwrap_or_else(|_| is_uninit_value_valid_for_ty_fallback(cx, ty))
547}
548
549/// A fallback for polymorphic types, which are not supported by `check_validity_requirement`.
550fn is_uninit_value_valid_for_ty_fallback<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
551    match *ty.kind() {
552        // The array length may be polymorphic, let's try the inner type.
553        ty::Array(component, _) => is_uninit_value_valid_for_ty(cx, component),
554        // Peek through tuples and try their fallbacks.
555        ty::Tuple(types) => types.iter().all(|ty| is_uninit_value_valid_for_ty(cx, ty)),
556        // Unions are always fine right now.
557        // This includes MaybeUninit, the main way people use uninitialized memory.
558        ty::Adt(adt, _) if adt.is_union() => true,
559        // Types (e.g. `UnsafeCell<MaybeUninit<T>>`) that recursively contain only types that can be uninit
560        // can themselves be uninit too.
561        // This purposefully ignores enums as they may have a discriminant that can't be uninit.
562        ty::Adt(adt, args) if adt.is_struct() => adt
563            .all_fields()
564            .all(|field| is_uninit_value_valid_for_ty(cx, field.ty(cx.tcx, args))),
565        // For the rest, conservatively assume that they cannot be uninit.
566        _ => false,
567    }
568}
569
570/// Gets an iterator over all predicates which apply to the given item.
571pub fn all_predicates_of(tcx: TyCtxt<'_>, id: DefId) -> impl Iterator<Item = &(ty::Clause<'_>, Span)> {
572    let mut next_id = Some(id);
573    iter::from_fn(move || {
574        next_id.take().map(|id| {
575            let preds = tcx.predicates_of(id);
576            next_id = preds.parent;
577            preds.predicates.iter()
578        })
579    })
580    .flatten()
581}
582
583/// A signature for a function like type.
584#[derive(Clone, Copy)]
585pub enum ExprFnSig<'tcx> {
586    Sig(Binder<'tcx, FnSig<'tcx>>, Option<DefId>),
587    Closure(Option<&'tcx FnDecl<'tcx>>, Binder<'tcx, FnSig<'tcx>>),
588    Trait(Binder<'tcx, Ty<'tcx>>, Option<Binder<'tcx, Ty<'tcx>>>, Option<DefId>),
589}
590impl<'tcx> ExprFnSig<'tcx> {
591    /// Gets the argument type at the given offset. This will return `None` when the index is out of
592    /// bounds only for variadic functions, otherwise this will panic.
593    pub fn input(self, i: usize) -> Option<Binder<'tcx, Ty<'tcx>>> {
594        match self {
595            Self::Sig(sig, _) => {
596                if sig.c_variadic() {
597                    sig.inputs().map_bound(|inputs| inputs.get(i).copied()).transpose()
598                } else {
599                    Some(sig.input(i))
600                }
601            },
602            Self::Closure(_, sig) => Some(sig.input(0).map_bound(|ty| ty.tuple_fields()[i])),
603            Self::Trait(inputs, _, _) => Some(inputs.map_bound(|ty| ty.tuple_fields()[i])),
604        }
605    }
606
607    /// Gets the argument type at the given offset. For closures this will also get the type as
608    /// written. This will return `None` when the index is out of bounds only for variadic
609    /// functions, otherwise this will panic.
610    pub fn input_with_hir(self, i: usize) -> Option<(Option<&'tcx hir::Ty<'tcx>>, Binder<'tcx, Ty<'tcx>>)> {
611        match self {
612            Self::Sig(sig, _) => {
613                if sig.c_variadic() {
614                    sig.inputs()
615                        .map_bound(|inputs| inputs.get(i).copied())
616                        .transpose()
617                        .map(|arg| (None, arg))
618                } else {
619                    Some((None, sig.input(i)))
620                }
621            },
622            Self::Closure(decl, sig) => Some((
623                decl.and_then(|decl| decl.inputs.get(i)),
624                sig.input(0).map_bound(|ty| ty.tuple_fields()[i]),
625            )),
626            Self::Trait(inputs, _, _) => Some((None, inputs.map_bound(|ty| ty.tuple_fields()[i]))),
627        }
628    }
629
630    /// Gets the result type, if one could be found. Note that the result type of a trait may not be
631    /// specified.
632    pub fn output(self) -> Option<Binder<'tcx, Ty<'tcx>>> {
633        match self {
634            Self::Sig(sig, _) | Self::Closure(_, sig) => Some(sig.output()),
635            Self::Trait(_, output, _) => output,
636        }
637    }
638
639    pub fn predicates_id(&self) -> Option<DefId> {
640        if let ExprFnSig::Sig(_, id) | ExprFnSig::Trait(_, _, id) = *self {
641            id
642        } else {
643            None
644        }
645    }
646}
647
648/// If the expression is function like, get the signature for it.
649pub fn expr_sig<'tcx>(cx: &LateContext<'tcx>, expr: &Expr<'_>) -> Option<ExprFnSig<'tcx>> {
650    if let Res::Def(DefKind::Fn | DefKind::Ctor(_, CtorKind::Fn) | DefKind::AssocFn, id) = path_res(cx, expr) {
651        Some(ExprFnSig::Sig(cx.tcx.fn_sig(id).instantiate_identity(), Some(id)))
652    } else {
653        ty_sig(cx, cx.typeck_results().expr_ty_adjusted(expr).peel_refs())
654    }
655}
656
657/// If the type is function like, get the signature for it.
658pub fn ty_sig<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<ExprFnSig<'tcx>> {
659    if let Some(boxed_ty) = ty.boxed_ty() {
660        return ty_sig(cx, boxed_ty);
661    }
662    match *ty.kind() {
663        ty::Closure(id, subs) => {
664            let decl = id
665                .as_local()
666                .and_then(|id| cx.tcx.hir_fn_decl_by_hir_id(cx.tcx.local_def_id_to_hir_id(id)));
667            Some(ExprFnSig::Closure(decl, subs.as_closure().sig()))
668        },
669        ty::FnDef(id, subs) => Some(ExprFnSig::Sig(cx.tcx.fn_sig(id).instantiate(cx.tcx, subs), Some(id))),
670        ty::Alias(ty::Opaque, AliasTy { def_id, args, .. }) => sig_from_bounds(
671            cx,
672            ty,
673            cx.tcx.item_self_bounds(def_id).iter_instantiated(cx.tcx, args),
674            cx.tcx.opt_parent(def_id),
675        ),
676        ty::FnPtr(sig_tys, hdr) => Some(ExprFnSig::Sig(sig_tys.with(hdr), None)),
677        ty::Dynamic(bounds, _, _) => {
678            let lang_items = cx.tcx.lang_items();
679            match bounds.principal() {
680                Some(bound)
681                    if Some(bound.def_id()) == lang_items.fn_trait()
682                        || Some(bound.def_id()) == lang_items.fn_once_trait()
683                        || Some(bound.def_id()) == lang_items.fn_mut_trait() =>
684                {
685                    let output = bounds
686                        .projection_bounds()
687                        .find(|p| lang_items.fn_once_output().is_some_and(|id| id == p.item_def_id()))
688                        .map(|p| p.map_bound(|p| p.term.expect_type()));
689                    Some(ExprFnSig::Trait(bound.map_bound(|b| b.args.type_at(0)), output, None))
690                },
691                _ => None,
692            }
693        },
694        ty::Alias(ty::Projection, proj) => match cx.tcx.try_normalize_erasing_regions(cx.typing_env(), ty) {
695            Ok(normalized_ty) if normalized_ty != ty => ty_sig(cx, normalized_ty),
696            _ => sig_for_projection(cx, proj).or_else(|| sig_from_bounds(cx, ty, cx.param_env.caller_bounds(), None)),
697        },
698        ty::Param(_) => sig_from_bounds(cx, ty, cx.param_env.caller_bounds(), None),
699        _ => None,
700    }
701}
702
703fn sig_from_bounds<'tcx>(
704    cx: &LateContext<'tcx>,
705    ty: Ty<'tcx>,
706    predicates: impl IntoIterator<Item = ty::Clause<'tcx>>,
707    predicates_id: Option<DefId>,
708) -> Option<ExprFnSig<'tcx>> {
709    let mut inputs = None;
710    let mut output = None;
711    let lang_items = cx.tcx.lang_items();
712
713    for pred in predicates {
714        match pred.kind().skip_binder() {
715            ty::ClauseKind::Trait(p)
716                if (lang_items.fn_trait() == Some(p.def_id())
717                    || lang_items.fn_mut_trait() == Some(p.def_id())
718                    || lang_items.fn_once_trait() == Some(p.def_id()))
719                    && p.self_ty() == ty =>
720            {
721                let i = pred.kind().rebind(p.trait_ref.args.type_at(1));
722                if inputs.is_some_and(|inputs| i != inputs) {
723                    // Multiple different fn trait impls. Is this even allowed?
724                    return None;
725                }
726                inputs = Some(i);
727            },
728            ty::ClauseKind::Projection(p)
729                if Some(p.projection_term.def_id) == lang_items.fn_once_output()
730                    && p.projection_term.self_ty() == ty =>
731            {
732                if output.is_some() {
733                    // Multiple different fn trait impls. Is this even allowed?
734                    return None;
735                }
736                output = Some(pred.kind().rebind(p.term.expect_type()));
737            },
738            _ => (),
739        }
740    }
741
742    inputs.map(|ty| ExprFnSig::Trait(ty, output, predicates_id))
743}
744
745fn sig_for_projection<'tcx>(cx: &LateContext<'tcx>, ty: AliasTy<'tcx>) -> Option<ExprFnSig<'tcx>> {
746    let mut inputs = None;
747    let mut output = None;
748    let lang_items = cx.tcx.lang_items();
749
750    for (pred, _) in cx
751        .tcx
752        .explicit_item_bounds(ty.def_id)
753        .iter_instantiated_copied(cx.tcx, ty.args)
754    {
755        match pred.kind().skip_binder() {
756            ty::ClauseKind::Trait(p)
757                if (lang_items.fn_trait() == Some(p.def_id())
758                    || lang_items.fn_mut_trait() == Some(p.def_id())
759                    || lang_items.fn_once_trait() == Some(p.def_id())) =>
760            {
761                let i = pred.kind().rebind(p.trait_ref.args.type_at(1));
762
763                if inputs.is_some_and(|inputs| inputs != i) {
764                    // Multiple different fn trait impls. Is this even allowed?
765                    return None;
766                }
767                inputs = Some(i);
768            },
769            ty::ClauseKind::Projection(p) if Some(p.projection_term.def_id) == lang_items.fn_once_output() => {
770                if output.is_some() {
771                    // Multiple different fn trait impls. Is this even allowed?
772                    return None;
773                }
774                output = pred.kind().rebind(p.term.as_type()).transpose();
775            },
776            _ => (),
777        }
778    }
779
780    inputs.map(|ty| ExprFnSig::Trait(ty, output, None))
781}
782
783#[derive(Clone, Copy)]
784pub enum EnumValue {
785    Unsigned(u128),
786    Signed(i128),
787}
788impl core::ops::Add<u32> for EnumValue {
789    type Output = Self;
790    fn add(self, n: u32) -> Self::Output {
791        match self {
792            Self::Unsigned(x) => Self::Unsigned(x + u128::from(n)),
793            Self::Signed(x) => Self::Signed(x + i128::from(n)),
794        }
795    }
796}
797
798/// Attempts to read the given constant as though it were an enum value.
799pub fn read_explicit_enum_value(tcx: TyCtxt<'_>, id: DefId) -> Option<EnumValue> {
800    if let Ok(ConstValue::Scalar(Scalar::Int(value))) = tcx.const_eval_poly(id) {
801        match tcx.type_of(id).instantiate_identity().kind() {
802            ty::Int(_) => Some(EnumValue::Signed(value.to_int(value.size()))),
803            ty::Uint(_) => Some(EnumValue::Unsigned(value.to_uint(value.size()))),
804            _ => None,
805        }
806    } else {
807        None
808    }
809}
810
811/// Gets the value of the given variant.
812pub fn get_discriminant_value(tcx: TyCtxt<'_>, adt: AdtDef<'_>, i: VariantIdx) -> EnumValue {
813    let variant = &adt.variant(i);
814    match variant.discr {
815        VariantDiscr::Explicit(id) => read_explicit_enum_value(tcx, id).unwrap(),
816        VariantDiscr::Relative(x) => match adt.variant((i.as_usize() - x as usize).into()).discr {
817            VariantDiscr::Explicit(id) => read_explicit_enum_value(tcx, id).unwrap() + x,
818            VariantDiscr::Relative(_) => EnumValue::Unsigned(x.into()),
819        },
820    }
821}
822
823/// Check if the given type is either `core::ffi::c_void`, `std::os::raw::c_void`, or one of the
824/// platform specific `libc::<platform>::c_void` types in libc.
825pub fn is_c_void(cx: &LateContext<'_>, ty: Ty<'_>) -> bool {
826    if let ty::Adt(adt, _) = ty.kind()
827        && let &[krate, .., name] = &*cx.get_def_path(adt.did())
828        && let sym::libc | sym::core | sym::std = krate
829        && name == sym::c_void
830    {
831        true
832    } else {
833        false
834    }
835}
836
837pub fn for_each_top_level_late_bound_region<B>(
838    ty: Ty<'_>,
839    f: impl FnMut(BoundRegion) -> ControlFlow<B>,
840) -> ControlFlow<B> {
841    struct V<F> {
842        index: u32,
843        f: F,
844    }
845    impl<'tcx, B, F: FnMut(BoundRegion) -> ControlFlow<B>> TypeVisitor<TyCtxt<'tcx>> for V<F> {
846        type Result = ControlFlow<B>;
847        fn visit_region(&mut self, r: Region<'tcx>) -> Self::Result {
848            if let RegionKind::ReBound(idx, bound) = r.kind()
849                && idx.as_u32() == self.index
850            {
851                (self.f)(bound)
852            } else {
853                ControlFlow::Continue(())
854            }
855        }
856        fn visit_binder<T: TypeFoldable<TyCtxt<'tcx>>>(&mut self, t: &Binder<'tcx, T>) -> Self::Result {
857            self.index += 1;
858            let res = t.super_visit_with(self);
859            self.index -= 1;
860            res
861        }
862    }
863    ty.visit_with(&mut V { index: 0, f })
864}
865
866pub struct AdtVariantInfo {
867    pub ind: usize,
868    pub size: u64,
869
870    /// (ind, size)
871    pub fields_size: Vec<(usize, u64)>,
872}
873
874impl AdtVariantInfo {
875    /// Returns ADT variants ordered by size
876    pub fn new<'tcx>(cx: &LateContext<'tcx>, adt: AdtDef<'tcx>, subst: GenericArgsRef<'tcx>) -> Vec<Self> {
877        let mut variants_size = adt
878            .variants()
879            .iter()
880            .enumerate()
881            .map(|(i, variant)| {
882                let mut fields_size = variant
883                    .fields
884                    .iter()
885                    .enumerate()
886                    .map(|(i, f)| (i, approx_ty_size(cx, f.ty(cx.tcx, subst))))
887                    .collect::<Vec<_>>();
888                fields_size.sort_by(|(_, a_size), (_, b_size)| (a_size.cmp(b_size)));
889
890                Self {
891                    ind: i,
892                    size: fields_size.iter().map(|(_, size)| size).sum(),
893                    fields_size,
894                }
895            })
896            .collect::<Vec<_>>();
897        variants_size.sort_by(|a, b| (b.size.cmp(&a.size)));
898        variants_size
899    }
900}
901
902/// Gets the struct or enum variant from the given `Res`
903pub fn adt_and_variant_of_res<'tcx>(cx: &LateContext<'tcx>, res: Res) -> Option<(AdtDef<'tcx>, &'tcx VariantDef)> {
904    match res {
905        Res::Def(DefKind::Struct, id) => {
906            let adt = cx.tcx.adt_def(id);
907            Some((adt, adt.non_enum_variant()))
908        },
909        Res::Def(DefKind::Variant, id) => {
910            let adt = cx.tcx.adt_def(cx.tcx.parent(id));
911            Some((adt, adt.variant_with_id(id)))
912        },
913        Res::Def(DefKind::Ctor(CtorOf::Struct, _), id) => {
914            let adt = cx.tcx.adt_def(cx.tcx.parent(id));
915            Some((adt, adt.non_enum_variant()))
916        },
917        Res::Def(DefKind::Ctor(CtorOf::Variant, _), id) => {
918            let var_id = cx.tcx.parent(id);
919            let adt = cx.tcx.adt_def(cx.tcx.parent(var_id));
920            Some((adt, adt.variant_with_id(var_id)))
921        },
922        Res::SelfCtor(id) => {
923            let adt = cx.tcx.type_of(id).instantiate_identity().ty_adt_def().unwrap();
924            Some((adt, adt.non_enum_variant()))
925        },
926        _ => None,
927    }
928}
929
930/// Comes up with an "at least" guesstimate for the type's size, not taking into
931/// account the layout of type parameters.
932pub fn approx_ty_size<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> u64 {
933    use rustc_middle::ty::layout::LayoutOf;
934    match (cx.layout_of(ty).map(|layout| layout.size.bytes()), ty.kind()) {
935        (Ok(size), _) => size,
936        (Err(_), ty::Tuple(list)) => list.iter().map(|t| approx_ty_size(cx, t)).sum(),
937        (Err(_), ty::Array(t, n)) => n.try_to_target_usize(cx.tcx).unwrap_or_default() * approx_ty_size(cx, *t),
938        (Err(_), ty::Adt(def, subst)) if def.is_struct() => def
939            .variants()
940            .iter()
941            .map(|v| {
942                v.fields
943                    .iter()
944                    .map(|field| approx_ty_size(cx, field.ty(cx.tcx, subst)))
945                    .sum::<u64>()
946            })
947            .sum(),
948        (Err(_), ty::Adt(def, subst)) if def.is_enum() => def
949            .variants()
950            .iter()
951            .map(|v| {
952                v.fields
953                    .iter()
954                    .map(|field| approx_ty_size(cx, field.ty(cx.tcx, subst)))
955                    .sum::<u64>()
956            })
957            .max()
958            .unwrap_or_default(),
959        (Err(_), ty::Adt(def, subst)) if def.is_union() => def
960            .variants()
961            .iter()
962            .map(|v| {
963                v.fields
964                    .iter()
965                    .map(|field| approx_ty_size(cx, field.ty(cx.tcx, subst)))
966                    .max()
967                    .unwrap_or_default()
968            })
969            .max()
970            .unwrap_or_default(),
971        (Err(_), _) => 0,
972    }
973}
974
975/// Asserts that the given arguments match the generic parameters of the given item.
976#[allow(dead_code)]
977fn assert_generic_args_match<'tcx>(tcx: TyCtxt<'tcx>, did: DefId, args: &[GenericArg<'tcx>]) {
978    let g = tcx.generics_of(did);
979    let parent = g.parent.map(|did| tcx.generics_of(did));
980    let count = g.parent_count + g.own_params.len();
981    let params = parent
982        .map_or([].as_slice(), |p| p.own_params.as_slice())
983        .iter()
984        .chain(&g.own_params)
985        .map(|x| &x.kind);
986
987    assert!(
988        count == args.len(),
989        "wrong number of arguments for `{did:?}`: expected `{count}`, found {}\n\
990            note: the expected arguments are: `[{}]`\n\
991            the given arguments are: `{args:#?}`",
992        args.len(),
993        params.clone().map(GenericParamDefKind::descr).format(", "),
994    );
995
996    if let Some((idx, (param, arg))) =
997        params
998            .clone()
999            .zip(args.iter().map(|&x| x.kind()))
1000            .enumerate()
1001            .find(|(_, (param, arg))| match (param, arg) {
1002                (GenericParamDefKind::Lifetime, GenericArgKind::Lifetime(_))
1003                | (GenericParamDefKind::Type { .. }, GenericArgKind::Type(_))
1004                | (GenericParamDefKind::Const { .. }, GenericArgKind::Const(_)) => false,
1005                (
1006                    GenericParamDefKind::Lifetime
1007                    | GenericParamDefKind::Type { .. }
1008                    | GenericParamDefKind::Const { .. },
1009                    _,
1010                ) => true,
1011            })
1012    {
1013        panic!(
1014            "incorrect argument for `{did:?}` at index `{idx}`: expected a {}, found `{arg:?}`\n\
1015                note: the expected arguments are `[{}]`\n\
1016                the given arguments are `{args:#?}`",
1017            param.descr(),
1018            params.clone().map(GenericParamDefKind::descr).format(", "),
1019        );
1020    }
1021}
1022
1023/// Returns whether `ty` is never-like; i.e., `!` (never) or an enum with zero variants.
1024pub fn is_never_like(ty: Ty<'_>) -> bool {
1025    ty.is_never() || (ty.is_enum() && ty.ty_adt_def().is_some_and(|def| def.variants().is_empty()))
1026}
1027
1028/// Makes the projection type for the named associated type in the given impl or trait impl.
1029///
1030/// This function is for associated types which are "known" to exist, and as such, will only return
1031/// `None` when debug assertions are disabled in order to prevent ICE's. With debug assertions
1032/// enabled this will check that the named associated type exists, the correct number of
1033/// arguments are given, and that the correct kinds of arguments are given (lifetime,
1034/// constant or type). This will not check if type normalization would succeed.
1035pub fn make_projection<'tcx>(
1036    tcx: TyCtxt<'tcx>,
1037    container_id: DefId,
1038    assoc_ty: Symbol,
1039    args: impl IntoIterator<Item = impl Into<GenericArg<'tcx>>>,
1040) -> Option<AliasTy<'tcx>> {
1041    fn helper<'tcx>(
1042        tcx: TyCtxt<'tcx>,
1043        container_id: DefId,
1044        assoc_ty: Symbol,
1045        args: GenericArgsRef<'tcx>,
1046    ) -> Option<AliasTy<'tcx>> {
1047        let Some(assoc_item) = tcx.associated_items(container_id).find_by_ident_and_kind(
1048            tcx,
1049            Ident::with_dummy_span(assoc_ty),
1050            AssocTag::Type,
1051            container_id,
1052        ) else {
1053            debug_assert!(false, "type `{assoc_ty}` not found in `{container_id:?}`");
1054            return None;
1055        };
1056        #[cfg(debug_assertions)]
1057        assert_generic_args_match(tcx, assoc_item.def_id, args);
1058
1059        Some(AliasTy::new_from_args(tcx, assoc_item.def_id, args))
1060    }
1061    helper(
1062        tcx,
1063        container_id,
1064        assoc_ty,
1065        tcx.mk_args_from_iter(args.into_iter().map(Into::into)),
1066    )
1067}
1068
1069/// Normalizes the named associated type in the given impl or trait impl.
1070///
1071/// This function is for associated types which are "known" to be valid with the given
1072/// arguments, and as such, will only return `None` when debug assertions are disabled in order
1073/// to prevent ICE's. With debug assertions enabled this will check that type normalization
1074/// succeeds as well as everything checked by `make_projection`.
1075pub fn make_normalized_projection<'tcx>(
1076    tcx: TyCtxt<'tcx>,
1077    typing_env: ty::TypingEnv<'tcx>,
1078    container_id: DefId,
1079    assoc_ty: Symbol,
1080    args: impl IntoIterator<Item = impl Into<GenericArg<'tcx>>>,
1081) -> Option<Ty<'tcx>> {
1082    fn helper<'tcx>(tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>, ty: AliasTy<'tcx>) -> Option<Ty<'tcx>> {
1083        #[cfg(debug_assertions)]
1084        if let Some((i, arg)) = ty
1085            .args
1086            .iter()
1087            .enumerate()
1088            .find(|(_, arg)| arg.has_escaping_bound_vars())
1089        {
1090            debug_assert!(
1091                false,
1092                "args contain late-bound region at index `{i}` which can't be normalized.\n\
1093                    use `TyCtxt::instantiate_bound_regions_with_erased`\n\
1094                    note: arg is `{arg:#?}`",
1095            );
1096            return None;
1097        }
1098        match tcx.try_normalize_erasing_regions(typing_env, Ty::new_projection_from_args(tcx, ty.def_id, ty.args)) {
1099            Ok(ty) => Some(ty),
1100            Err(e) => {
1101                debug_assert!(false, "failed to normalize type `{ty}`: {e:#?}");
1102                None
1103            },
1104        }
1105    }
1106    helper(tcx, typing_env, make_projection(tcx, container_id, assoc_ty, args)?)
1107}
1108
1109/// Helper to check if given type has inner mutability such as [`std::cell::Cell`] or
1110/// [`std::cell::RefCell`].
1111#[derive(Default, Debug)]
1112pub struct InteriorMut<'tcx> {
1113    ignored_def_ids: FxHashSet<DefId>,
1114    ignore_pointers: bool,
1115    tys: FxHashMap<Ty<'tcx>, Option<&'tcx ty::List<Ty<'tcx>>>>,
1116}
1117
1118impl<'tcx> InteriorMut<'tcx> {
1119    pub fn new(tcx: TyCtxt<'tcx>, ignore_interior_mutability: &[String]) -> Self {
1120        let ignored_def_ids = ignore_interior_mutability
1121            .iter()
1122            .flat_map(|ignored_ty| lookup_path_str(tcx, PathNS::Type, ignored_ty))
1123            .collect();
1124
1125        Self {
1126            ignored_def_ids,
1127            ..Self::default()
1128        }
1129    }
1130
1131    pub fn without_pointers(tcx: TyCtxt<'tcx>, ignore_interior_mutability: &[String]) -> Self {
1132        Self {
1133            ignore_pointers: true,
1134            ..Self::new(tcx, ignore_interior_mutability)
1135        }
1136    }
1137
1138    /// Check if given type has interior mutability such as [`std::cell::Cell`] or
1139    /// [`std::cell::RefCell`] etc. and if it does, returns a chain of types that causes
1140    /// this type to be interior mutable
1141    pub fn interior_mut_ty_chain(&mut self, cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<&'tcx ty::List<Ty<'tcx>>> {
1142        match self.tys.entry(ty) {
1143            Entry::Occupied(o) => return *o.get(),
1144            // Temporarily insert a `None` to break cycles
1145            Entry::Vacant(v) => v.insert(None),
1146        };
1147
1148        let chain = match *ty.kind() {
1149            ty::RawPtr(inner_ty, _) if !self.ignore_pointers => self.interior_mut_ty_chain(cx, inner_ty),
1150            ty::Ref(_, inner_ty, _) | ty::Slice(inner_ty) => self.interior_mut_ty_chain(cx, inner_ty),
1151            ty::Array(inner_ty, size) if size.try_to_target_usize(cx.tcx) != Some(0) => {
1152                self.interior_mut_ty_chain(cx, inner_ty)
1153            },
1154            ty::Tuple(fields) => fields.iter().find_map(|ty| self.interior_mut_ty_chain(cx, ty)),
1155            ty::Adt(def, _) if def.is_unsafe_cell() => Some(ty::List::empty()),
1156            ty::Adt(def, args) => {
1157                let is_std_collection = matches!(
1158                    cx.tcx.get_diagnostic_name(def.did()),
1159                    Some(
1160                        sym::LinkedList
1161                            | sym::Vec
1162                            | sym::VecDeque
1163                            | sym::BTreeMap
1164                            | sym::BTreeSet
1165                            | sym::HashMap
1166                            | sym::HashSet
1167                            | sym::Arc
1168                            | sym::Rc
1169                    )
1170                );
1171
1172                if is_std_collection || def.is_box() {
1173                    // Include the types from std collections that are behind pointers internally
1174                    args.types().find_map(|ty| self.interior_mut_ty_chain(cx, ty))
1175                } else if self.ignored_def_ids.contains(&def.did()) || def.is_phantom_data() {
1176                    None
1177                } else {
1178                    def.all_fields()
1179                        .find_map(|f| self.interior_mut_ty_chain(cx, f.ty(cx.tcx, args)))
1180                }
1181            },
1182            ty::Alias(ty::Projection, _) => match cx.tcx.try_normalize_erasing_regions(cx.typing_env(), ty) {
1183                Ok(normalized_ty) if ty != normalized_ty => self.interior_mut_ty_chain(cx, normalized_ty),
1184                _ => None,
1185            },
1186            _ => None,
1187        };
1188
1189        chain.map(|chain| {
1190            let list = cx.tcx.mk_type_list_from_iter(chain.iter().chain([ty]));
1191            self.tys.insert(ty, Some(list));
1192            list
1193        })
1194    }
1195
1196    /// Check if given type has interior mutability such as [`std::cell::Cell`] or
1197    /// [`std::cell::RefCell`] etc.
1198    pub fn is_interior_mut_ty(&mut self, cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
1199        self.interior_mut_ty_chain(cx, ty).is_some()
1200    }
1201}
1202
1203pub fn make_normalized_projection_with_regions<'tcx>(
1204    tcx: TyCtxt<'tcx>,
1205    typing_env: ty::TypingEnv<'tcx>,
1206    container_id: DefId,
1207    assoc_ty: Symbol,
1208    args: impl IntoIterator<Item = impl Into<GenericArg<'tcx>>>,
1209) -> Option<Ty<'tcx>> {
1210    fn helper<'tcx>(tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>, ty: AliasTy<'tcx>) -> Option<Ty<'tcx>> {
1211        #[cfg(debug_assertions)]
1212        if let Some((i, arg)) = ty
1213            .args
1214            .iter()
1215            .enumerate()
1216            .find(|(_, arg)| arg.has_escaping_bound_vars())
1217        {
1218            debug_assert!(
1219                false,
1220                "args contain late-bound region at index `{i}` which can't be normalized.\n\
1221                    use `TyCtxt::instantiate_bound_regions_with_erased`\n\
1222                    note: arg is `{arg:#?}`",
1223            );
1224            return None;
1225        }
1226        let cause = ObligationCause::dummy();
1227        let (infcx, param_env) = tcx.infer_ctxt().build_with_typing_env(typing_env);
1228        match infcx
1229            .at(&cause, param_env)
1230            .query_normalize(Ty::new_projection_from_args(tcx, ty.def_id, ty.args))
1231        {
1232            Ok(ty) => Some(ty.value),
1233            Err(e) => {
1234                debug_assert!(false, "failed to normalize type `{ty}`: {e:#?}");
1235                None
1236            },
1237        }
1238    }
1239    helper(tcx, typing_env, make_projection(tcx, container_id, assoc_ty, args)?)
1240}
1241
1242pub fn normalize_with_regions<'tcx>(tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
1243    let cause = ObligationCause::dummy();
1244    let (infcx, param_env) = tcx.infer_ctxt().build_with_typing_env(typing_env);
1245    infcx
1246        .at(&cause, param_env)
1247        .query_normalize(ty)
1248        .map_or(ty, |ty| ty.value)
1249}
1250
1251/// Checks if the type is `core::mem::ManuallyDrop<_>`
1252pub fn is_manually_drop(ty: Ty<'_>) -> bool {
1253    ty.ty_adt_def().is_some_and(AdtDef::is_manually_drop)
1254}
1255
1256/// Returns the deref chain of a type, starting with the type itself.
1257pub fn deref_chain<'cx, 'tcx>(cx: &'cx LateContext<'tcx>, ty: Ty<'tcx>) -> impl Iterator<Item = Ty<'tcx>> + 'cx {
1258    iter::successors(Some(ty), |&ty| {
1259        if let Some(deref_did) = cx.tcx.lang_items().deref_trait()
1260            && implements_trait(cx, ty, deref_did, &[])
1261        {
1262            make_normalized_projection(cx.tcx, cx.typing_env(), deref_did, sym::Target, [ty])
1263        } else {
1264            None
1265        }
1266    })
1267}
1268
1269/// Checks if a Ty<'_> has some inherent method Symbol.
1270///
1271/// This does not look for impls in the type's `Deref::Target` type.
1272/// If you need this, you should wrap this call in `clippy_utils::ty::deref_chain().any(...)`.
1273pub fn get_adt_inherent_method<'a>(cx: &'a LateContext<'_>, ty: Ty<'_>, method_name: Symbol) -> Option<&'a AssocItem> {
1274    if let Some(ty_did) = ty.ty_adt_def().map(AdtDef::did) {
1275        cx.tcx.inherent_impls(ty_did).iter().find_map(|&did| {
1276            cx.tcx
1277                .associated_items(did)
1278                .filter_by_name_unhygienic(method_name)
1279                .next()
1280                .filter(|item| item.as_tag() == AssocTag::Fn)
1281        })
1282    } else {
1283        None
1284    }
1285}
1286
1287/// Gets the type of a field by name.
1288pub fn get_field_by_name<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, name: Symbol) -> Option<Ty<'tcx>> {
1289    match *ty.kind() {
1290        ty::Adt(def, args) if def.is_union() || def.is_struct() => def
1291            .non_enum_variant()
1292            .fields
1293            .iter()
1294            .find(|f| f.name == name)
1295            .map(|f| f.ty(tcx, args)),
1296        ty::Tuple(args) => name.as_str().parse::<usize>().ok().and_then(|i| args.get(i).copied()),
1297        _ => None,
1298    }
1299}
1300
1301/// Check if `ty` is an `Option` and return its argument type if it is.
1302pub fn option_arg_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
1303    match ty.kind() {
1304        ty::Adt(adt, args) => cx
1305            .tcx
1306            .is_diagnostic_item(sym::Option, adt.did())
1307            .then(|| args.type_at(0)),
1308        _ => None,
1309    }
1310}
1311
1312/// Check if a Ty<'_> of `Iterator` contains any mutable access to non-owning types by checking if
1313/// it contains fields of mutable references or pointers, or references/pointers to non-`Freeze`
1314/// types, or `PhantomData` types containing any of the previous. This can be used to check whether
1315/// skipping iterating over an iterator will change its behavior.
1316pub fn has_non_owning_mutable_access<'tcx>(cx: &LateContext<'tcx>, iter_ty: Ty<'tcx>) -> bool {
1317    fn normalize_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
1318        cx.tcx.try_normalize_erasing_regions(cx.typing_env(), ty).unwrap_or(ty)
1319    }
1320
1321    /// Check if `ty` contains mutable references or equivalent, which includes:
1322    /// - A mutable reference/pointer.
1323    /// - A reference/pointer to a non-`Freeze` type.
1324    /// - A `PhantomData` type containing any of the previous.
1325    fn has_non_owning_mutable_access_inner<'tcx>(
1326        cx: &LateContext<'tcx>,
1327        phantoms: &mut FxHashSet<Ty<'tcx>>,
1328        ty: Ty<'tcx>,
1329    ) -> bool {
1330        match ty.kind() {
1331            ty::Adt(adt_def, args) if adt_def.is_phantom_data() => {
1332                phantoms.insert(ty)
1333                    && args
1334                        .types()
1335                        .any(|arg_ty| has_non_owning_mutable_access_inner(cx, phantoms, arg_ty))
1336            },
1337            ty::Adt(adt_def, args) => adt_def.all_fields().any(|field| {
1338                has_non_owning_mutable_access_inner(cx, phantoms, normalize_ty(cx, field.ty(cx.tcx, args)))
1339            }),
1340            ty::Array(elem_ty, _) | ty::Slice(elem_ty) => has_non_owning_mutable_access_inner(cx, phantoms, *elem_ty),
1341            ty::RawPtr(pointee_ty, mutability) | ty::Ref(_, pointee_ty, mutability) => {
1342                mutability.is_mut() || !pointee_ty.is_freeze(cx.tcx, cx.typing_env())
1343            },
1344            ty::Closure(_, closure_args) => {
1345                matches!(closure_args.types().next_back(), Some(captures) if has_non_owning_mutable_access_inner(cx, phantoms, captures))
1346            },
1347            ty::Tuple(tuple_args) => tuple_args
1348                .iter()
1349                .any(|arg_ty| has_non_owning_mutable_access_inner(cx, phantoms, arg_ty)),
1350            _ => false,
1351        }
1352    }
1353
1354    let mut phantoms = FxHashSet::default();
1355    has_non_owning_mutable_access_inner(cx, &mut phantoms, iter_ty)
1356}
1357
1358/// Check if `ty` is slice-like, i.e., `&[T]`, `[T; N]`, or `Vec<T>`.
1359pub fn is_slice_like<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
1360    ty.is_slice()
1361        || ty.is_array()
1362        || matches!(ty.kind(), ty::Adt(adt_def, _) if cx.tcx.is_diagnostic_item(sym::Vec, adt_def.did()))
1363}
1364
1365/// Gets the index of a field by name.
1366pub fn get_field_idx_by_name(ty: Ty<'_>, name: Symbol) -> Option<usize> {
1367    match *ty.kind() {
1368        ty::Adt(def, _) if def.is_union() || def.is_struct() => {
1369            def.non_enum_variant().fields.iter().position(|f| f.name == name)
1370        },
1371        ty::Tuple(_) => name.as_str().parse::<usize>().ok(),
1372        _ => None,
1373    }
1374}