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