Skip to main content

clippy_utils/ty/
mod.rs

1//! Util methods for [`rustc_middle::ty`]
2
3#![expect(clippy::module_name_repetitions)]
4
5use core::ops::ControlFlow;
6use itertools::Itertools as _;
7use rustc_abi::{BackendRepr, FieldsShape, VariantIdx, Variants};
8use rustc_ast::ast::Mutability;
9use rustc_attr_ir::lang_items::LangItem;
10use rustc_data_structures::fx::{FxHashMap, FxHashSet};
11use rustc_errors::pluralize;
12use rustc_hir as hir;
13use rustc_hir::def::{CtorKind, CtorOf, DefKind, Res};
14use rustc_hir::def_id::DefId;
15use rustc_hir::{Expr, ExprKind, FnDecl};
16use rustc_hir_analysis::lower_ty;
17use rustc_infer::infer::TyCtxtInferExt as _;
18use rustc_lint::LateContext;
19use rustc_lint::unused::must_use::{IsTyMustUse, MustUsePath, is_ty_must_use};
20use rustc_middle::mir::ConstValue;
21use rustc_middle::mir::interpret::Scalar;
22use rustc_middle::traits::EvaluationResult;
23use rustc_middle::ty::adjustment::{Adjust, Adjustment, DerefAdjustKind};
24use rustc_middle::ty::layout::{LayoutError, LayoutOf as _, TyAndLayout};
25use rustc_middle::ty::{
26    self, AdtDef, AliasTy, AssocItem, AssocTag, Binder, BoundRegion, BoundVarIndexKind, CallerBoundsIterator as _,
27    FnSig, GenericArg, GenericArgKind, GenericArgs, IntTy, ProjectionAliasTy, Region, RegionKind, TraitRef, Ty, TyCtxt,
28    TypeSuperVisitable as _, TypeVisitable, TypeVisitableExt as _, TypeVisitor, UintTy, Unnormalized, VariantDef,
29    VariantDiscr,
30};
31use rustc_span::symbol::Ident;
32use rustc_span::{DUMMY_SP, Span, Symbol};
33use rustc_trait_selection::traits::query::evaluate_obligation::InferCtxtExt as _;
34use rustc_trait_selection::traits::query::normalize::QueryNormalizeExt as _;
35use rustc_trait_selection::traits::{Obligation, ObligationCause};
36use std::collections::hash_map::Entry;
37use std::{debug_assert_matches, iter, mem};
38
39use crate::paths::{PathNS, lookup_path_str};
40use crate::res::{MaybeDef as _, MaybeQPath as _};
41use crate::{over, sym};
42
43mod type_certainty;
44pub use type_certainty::expr_type_is_certain;
45
46/// Lower a [`hir::Ty`] to a [`rustc_middle::ty::Ty`].
47pub fn ty_from_hir_ty<'tcx>(cx: &LateContext<'tcx>, hir_ty: &hir::Ty<'tcx>) -> Ty<'tcx> {
48    cx.typeck_results
49        .filter(|results| results.hir_owner == hir_ty.hir_id.owner)
50        .and_then(|results| results.node_type_opt(hir_ty.hir_id))
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
74            .all_fields()
75            .any(|f| !is_copy(cx, f.ty(cx.tcx, *subs).skip_norm_wip())),
76        _ => true,
77    }
78}
79
80/// Walks into `ty` and returns `true` if any inner type is an instance of the given adt
81/// constructor.
82pub fn contains_adt_constructor<'tcx>(ty: Ty<'tcx>, adt: AdtDef<'tcx>) -> bool {
83    ty.walk().any(|inner| match inner.kind() {
84        GenericArgKind::Type(inner_ty) => inner_ty.ty_adt_def() == Some(adt),
85        GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => false,
86    })
87}
88
89/// Walks into `ty` and returns `true` if any inner type is an instance of the given type, or adt
90/// constructor of the same type.
91///
92/// This method also recurses into opaque type predicates, so call it with `impl Trait<U>` and `U`
93/// will also return `true`.
94pub fn contains_ty_adt_constructor_opaque<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>, needle: Ty<'tcx>) -> bool {
95    fn contains_ty_adt_constructor_opaque_inner<'tcx>(
96        cx: &LateContext<'tcx>,
97        ty: Ty<'tcx>,
98        needle: Ty<'tcx>,
99        seen: &mut FxHashSet<DefId>,
100    ) -> bool {
101        ty.walk().any(|inner| match inner.kind() {
102            GenericArgKind::Type(inner_ty) => {
103                if inner_ty == needle {
104                    return true;
105                }
106
107                if inner_ty.ty_adt_def() == needle.ty_adt_def() {
108                    return true;
109                }
110
111                if let ty::Alias(
112                    _,
113                    AliasTy {
114                        kind: ty::Opaque { def_id },
115                        ..
116                    },
117                ) = *inner_ty.kind()
118                {
119                    if !seen.insert(def_id) {
120                        return false;
121                    }
122
123                    for (predicate, _span) in cx
124                        .tcx
125                        .explicit_item_self_bounds(def_id)
126                        .iter_identity_copied()
127                        .map(Unnormalized::skip_norm_wip)
128                    {
129                        match predicate.kind().skip_binder() {
130                            // For `impl Trait<U>`, it will register a predicate of `T: Trait<U>`, so we go through
131                            // and check substitutions to find `U`.
132                            ty::ClauseKind::Trait(trait_predicate)
133                                if trait_predicate
134                                    .trait_ref
135                                    .args
136                                    .types()
137                                    .skip(1) // Skip the implicit `Self` generic parameter
138                                    .any(|ty| contains_ty_adt_constructor_opaque_inner(cx, ty, needle, seen)) =>
139                            {
140                                return true;
141                            },
142                            // For `impl Trait<Assoc=U>`, it will register a predicate of `<T as Trait>::Assoc = U`,
143                            // so we check the term for `U`.
144                            ty::ClauseKind::Projection(projection_predicate) => {
145                                if let ty::TermKind::Ty(ty) = projection_predicate.term.kind()
146                                    && contains_ty_adt_constructor_opaque_inner(cx, ty, needle, seen)
147                                {
148                                    return true;
149                                }
150                            },
151                            _ => (),
152                        }
153                    }
154                }
155
156                false
157            },
158            GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => false,
159        })
160    }
161
162    // A hash set to ensure that the same opaque type (`impl Trait` in RPIT or TAIT) is not
163    // visited twice.
164    let mut seen = FxHashSet::default();
165    contains_ty_adt_constructor_opaque_inner(cx, ty, needle, &mut seen)
166}
167
168/// Resolves `<T as Iterator>::Item` for `T`
169/// Do not invoke without first verifying that the type implements `Iterator`
170pub fn get_iterator_item_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
171    cx.tcx
172        .get_diagnostic_item(sym::Iterator)
173        .and_then(|iter_did| cx.get_associated_type(ty, iter_did, sym::Item))
174}
175
176/// Returns true if `ty` is a type on which calling `Clone` through a function instead of
177/// as a method, such as `Arc::clone()` is considered idiomatic.
178///
179/// Lints should avoid suggesting to replace instances of `ty::Clone()` by `.clone()` for objects
180/// of those types.
181pub fn should_call_clone_as_function(cx: &LateContext<'_>, ty: Ty<'_>) -> bool {
182    matches!(
183        ty.opt_diag_name(cx),
184        Some(sym::Arc | sym::ArcWeak | sym::Rc | sym::RcWeak)
185    )
186}
187
188/// If `ty` is known to have a `iter` or `iter_mut` method, returns a symbol representing the type.
189pub fn has_iter_method(cx: &LateContext<'_>, probably_ref_ty: Ty<'_>) -> Option<Symbol> {
190    // FIXME: instead of this hard-coded list, we should check if `<adt>::iter`
191    // exists and has the desired signature. Unfortunately FnCtxt is not exported
192    // so we can't use its `lookup_method` method.
193    let into_iter_collections: &[Symbol] = &[
194        sym::Vec,
195        sym::Option,
196        sym::Result,
197        sym::BTreeMap,
198        sym::BTreeSet,
199        sym::VecDeque,
200        sym::LinkedList,
201        sym::BinaryHeap,
202        sym::HashSet,
203        sym::HashMap,
204        sym::PathBuf,
205        sym::Path,
206        sym::MpscReceiver,
207        sym::MpmcReceiver,
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/HEAD/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_and_anonymize_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
296    let trait_ref = TraitRef::new(tcx, trait_id, [GenericArg::from(ty)].into_iter().chain(args));
297
298    debug_assert_matches!(
299        tcx.def_kind(trait_id),
300        DefKind::Trait | DefKind::TraitAlias,
301        "`DefId` must belong to a trait or trait alias"
302    );
303    #[cfg(debug_assertions)]
304    assert_generic_args_match(tcx, trait_id, trait_ref.args.as_slice());
305
306    let obligation = Obligation::new(tcx, ObligationCause::dummy(), param_env, trait_ref);
307    infcx
308        .evaluate_obligation(&obligation)
309        .is_ok_and(EvaluationResult::must_apply_modulo_regions)
310}
311
312/// Checks whether this type implements `Drop`.
313pub fn has_drop<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
314    ty.ty_adt_def().is_some_and(|def| def.has_dtor(cx.tcx))
315}
316
317/// Returns whether the `ty` has `#[must_use]` attribute, or acts like it does according to the
318/// compiler determination. For example, if `ty` is a `Result`/`ControlFlow` whose `Err`/`Break`
319/// payload is an uninhabited type, the `Ok`/`Continue` payload type will be used instead.
320///
321/// The [`MustUsePath`] can be used to describe the type through [`describe_must_use_type`].
322pub fn opt_must_use_path<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<MustUsePath> {
323    // `is_ty_must_use` requires an expression, whose `hir_id` will be used to determine whether
324    // certain types are visibly uninhabited from the module containing the expression.
325    // `cx.last_node_with_lint_attrs` is initialized to the crate/module `hir_id` when linting
326    // a new crate/module. If it is overriden, it is with an `hir_id` pertaining to the same
327    // create/module. We can use this in a dummy expression instead of asking all callers
328    // to provide a local `hir_id` which would not add more information.
329    let dummy_expr = Expr {
330        hir_id: cx.last_node_with_lint_attrs,
331        span: DUMMY_SP,
332        kind: ExprKind::Ret(None),
333    };
334    match is_ty_must_use(cx, ty, &dummy_expr) {
335        IsTyMustUse::Yes(path) => Some(path),
336        _ => None,
337    }
338}
339
340/// Describe a [`MustUsePath`] returned by [`opt_must_use_path`].
341pub fn describe_must_use_type(cx: &LateContext<'_>, path: &MustUsePath) -> String {
342    describe_must_use_type_inner(cx, path, "", "", 1)
343}
344
345// This is a rip-off from the compiler's `rustc_lint/src/unused/must_use.rs`
346fn describe_must_use_type_inner(
347    cx: &LateContext<'_>,
348    path: &MustUsePath,
349    descr_pre: &str,
350    descr_post: &str,
351    plural_len: usize,
352) -> String {
353    let plural_suffix = pluralize!(plural_len);
354
355    match path {
356        MustUsePath::Boxed(path) => {
357            let descr_pre = &format!("{descr_pre}boxed ");
358            describe_must_use_type_inner(cx, path, descr_pre, descr_post, plural_len)
359        },
360        MustUsePath::Pinned(path) => {
361            let descr_pre = &format!("{descr_pre}pinned ");
362            describe_must_use_type_inner(cx, path, descr_pre, descr_post, plural_len)
363        },
364        MustUsePath::Opaque(path) => {
365            let descr_pre = &format!("{descr_pre}implementer{plural_suffix} of ");
366            describe_must_use_type_inner(cx, path, descr_pre, descr_post, plural_len)
367        },
368        MustUsePath::TraitObject(path) => {
369            let descr_post = &format!(" trait object{plural_suffix}{descr_post}");
370            describe_must_use_type_inner(cx, path, descr_pre, descr_post, plural_len)
371        },
372        MustUsePath::TupleElement(elems) => elems
373            .iter()
374            .map(|(index, path)| {
375                let descr_post = &format!(" in tuple element {index}");
376                describe_must_use_type_inner(cx, path, descr_pre, descr_post, plural_len)
377            })
378            .join(", "),
379        MustUsePath::Result(path) => {
380            let descr_post = &format!(" in a `Result` with an uninhabited error{descr_post}");
381            describe_must_use_type_inner(cx, path, descr_pre, descr_post, plural_len)
382        },
383        MustUsePath::ControlFlow(path) => {
384            let descr_post = &format!(" in a `ControlFlow` with an uninhabited break{descr_post}");
385            describe_must_use_type_inner(cx, path, descr_pre, descr_post, plural_len)
386        },
387        MustUsePath::Array(path, len) => {
388            let descr_pre = &format!("{descr_pre}array{plural_suffix} of ");
389            describe_must_use_type_inner(
390                cx,
391                path,
392                descr_pre,
393                descr_post,
394                plural_len.saturating_add(usize::try_from(*len).unwrap_or(usize::MAX)),
395            )
396        },
397        MustUsePath::Closure(_) => {
398            format!(
399                "{descr_pre}{} closure{plural_suffix}{descr_post}",
400                if plural_len == 1 {
401                    "one".to_string()
402                } else {
403                    plural_len.to_string()
404                }
405            )
406        },
407        MustUsePath::Coroutine(_) => {
408            format!(
409                "{descr_pre}{} coroutine{plural_suffix}{descr_post}",
410                if plural_len == 1 {
411                    "one".to_string()
412                } else {
413                    plural_len.to_string()
414                }
415            )
416        },
417        MustUsePath::Def(_, def_id, _) => {
418            format!(
419                "{descr_pre}`{}`{plural_suffix}{descr_post}",
420                cx.tcx.def_path_str(*def_id)
421            )
422        },
423    }
424}
425
426/// Returns `true` if the given type is a non aggregate primitive (a `bool` or `char`, any
427/// integer or floating-point number type).
428///
429/// For checking aggregation of primitive types (e.g. tuples and slices of primitive type) see
430/// `is_recursively_primitive_type`
431pub fn is_non_aggregate_primitive_type(ty: Ty<'_>) -> bool {
432    matches!(ty.kind(), ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_))
433}
434
435/// Returns `true` if the given type is a primitive (a `bool` or `char`, any integer or
436/// floating-point number type, a `str`, or an array, slice, or tuple of those types).
437pub fn is_recursively_primitive_type(ty: Ty<'_>) -> bool {
438    match *ty.kind() {
439        ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Str => true,
440        ty::Ref(_, inner, _) if inner.is_str() => true,
441        ty::Array(inner_type, _) | ty::Slice(inner_type) => is_recursively_primitive_type(inner_type),
442        ty::Tuple(inner_types) => inner_types.iter().all(is_recursively_primitive_type),
443        _ => false,
444    }
445}
446
447/// Return `true` if the passed `typ` is `isize` or `usize`.
448pub fn is_isize_or_usize(typ: Ty<'_>) -> bool {
449    matches!(typ.kind(), ty::Int(IntTy::Isize) | ty::Uint(UintTy::Usize))
450}
451
452/// Checks if the drop order for a type matters.
453///
454/// Some std types implement drop solely to deallocate memory. For these types, and composites
455/// containing them, changing the drop order won't result in any observable side effects.
456pub fn needs_ordered_drop<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
457    fn needs_ordered_drop_inner<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>, seen: &mut FxHashSet<Ty<'tcx>>) -> bool {
458        if !seen.insert(ty) {
459            return false;
460        }
461        if !ty.has_significant_drop(cx.tcx, cx.typing_env()) {
462            false
463        }
464        // Check for std types which implement drop, but only for memory allocation.
465        else if ty.is_lang_item(cx, LangItem::OwnedBox)
466            || matches!(
467                ty.opt_diag_name(cx),
468                Some(sym::HashSet | sym::Rc | sym::Arc | sym::cstring_type | sym::RcWeak | sym::ArcWeak)
469            )
470        {
471            // Check all of the generic arguments.
472            if let ty::Adt(_, subs) = ty.kind() {
473                subs.types().any(|ty| needs_ordered_drop_inner(cx, ty, seen))
474            } else {
475                true
476            }
477        } else if !cx
478            .tcx
479            .lang_items()
480            .drop_trait()
481            .is_some_and(|id| implements_trait(cx, ty, id, &[]))
482        {
483            // This type doesn't implement drop, so no side effects here.
484            // Check if any component type has any.
485            match ty.kind() {
486                ty::Tuple(fields) => fields.iter().any(|ty| needs_ordered_drop_inner(cx, ty, seen)),
487                ty::Array(ty, _) => needs_ordered_drop_inner(cx, *ty, seen),
488                ty::Adt(adt, subs) => adt
489                    .all_fields()
490                    .map(|f| f.ty(cx.tcx, *subs).skip_norm_wip())
491                    .any(|ty| needs_ordered_drop_inner(cx, ty, seen)),
492                _ => true,
493            }
494        } else {
495            true
496        }
497    }
498
499    needs_ordered_drop_inner(cx, ty, &mut FxHashSet::default())
500}
501
502/// Returns `true` if `ty` denotes an `unsafe fn`.
503pub fn is_unsafe_fn<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
504    ty.is_fn() && ty.fn_sig(cx.tcx).safety().is_unsafe()
505}
506
507/// Peels off all references on the type. Returns the underlying type, the number of references
508/// removed, and, if there were any such references, whether the pointer is ultimately mutable or
509/// not.
510pub fn peel_and_count_ty_refs(mut ty: Ty<'_>) -> (Ty<'_>, usize, Option<Mutability>) {
511    let mut count = 0;
512    let mut mutbl = None;
513    while let ty::Ref(_, dest_ty, m) = ty.kind() {
514        ty = *dest_ty;
515        count += 1;
516        mutbl.replace(mutbl.map_or(*m, |mutbl: Mutability| mutbl.min(*m)));
517    }
518    (ty, count, mutbl)
519}
520
521/// Peels off `n` references on the type. Returns the underlying type and, if any references
522/// were removed, whether the pointer is ultimately mutable or not.
523pub fn peel_n_ty_refs(mut ty: Ty<'_>, n: usize) -> (Ty<'_>, Option<Mutability>) {
524    let mut mutbl = None;
525    for _ in 0..n {
526        if let ty::Ref(_, dest_ty, m) = ty.kind() {
527            ty = *dest_ty;
528            mutbl.replace(mutbl.map_or(*m, |mutbl: Mutability| mutbl.min(*m)));
529        } else {
530            break;
531        }
532    }
533    (ty, mutbl)
534}
535
536/// Checks whether `a` and `b` are same types having same `Const` generic args, but ignores
537/// lifetimes.
538///
539/// For example, the function would return `true` for
540/// - `u32` and `u32`
541/// - `[u8; N]` and `[u8; M]`, if `N=M`
542/// - `Option<T>` and `Option<U>`, if `same_type_modulo_regions(T, U)` holds
543/// - `&'a str` and `&'b str`
544///
545/// and `false` for:
546/// - `Result<u32, String>` and `Result<usize, String>`
547pub fn same_type_modulo_regions<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
548    match (a.kind(), b.kind()) {
549        (ty::Adt(did_a, args_a), ty::Adt(did_b, args_b)) => {
550            if did_a != did_b {
551                return false;
552            }
553
554            iter::zip(*args_a, *args_b).all(|(arg_a, arg_b)| match (arg_a.kind(), arg_b.kind()) {
555                (GenericArgKind::Const(inner_a), GenericArgKind::Const(inner_b)) => inner_a == inner_b,
556                (GenericArgKind::Type(type_a), GenericArgKind::Type(type_b)) => {
557                    same_type_modulo_regions(type_a, type_b)
558                },
559                _ => true,
560            })
561        },
562        (ty::Ref(_, a, mut_a), ty::Ref(_, b, mut_b)) => mut_a == mut_b && same_type_modulo_regions(*a, *b),
563        (ty::Tuple(as_), ty::Tuple(bs)) => over(as_, bs, |a, b| same_type_modulo_regions(*a, *b)),
564        (ty::Array(a, na), ty::Array(b, nb)) => na == nb && same_type_modulo_regions(*a, *b),
565        _ => a == b,
566    }
567}
568
569/// Checks if a given type looks safe to be uninitialized.
570pub fn is_uninit_value_valid_for_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
571    match cx.layout_of(ty) {
572        Ok(layout) => is_uninit_value_valid_for_layout(cx, layout),
573        // The type layout is either not concrete enough yet or too large, fall back to structural check instead
574        Err(LayoutError::TooGeneric(_) | LayoutError::SizeOverflow(_)) => is_uninit_value_valid_for_ty_fallback(cx, ty),
575        Err(_) => false,
576    }
577}
578
579fn is_uninit_value_valid_for_layout<'tcx>(cx: &LateContext<'tcx>, layout: TyAndLayout<'tcx>) -> bool {
580    // ZSTs contribute no bytes to the vector buffer
581    if layout.layout.is_zst() {
582        return true;
583    }
584
585    match layout.layout.backend_repr {
586        BackendRepr::Scalar(s) => s.is_uninit_valid(),
587        BackendRepr::ScalarPair { a, b, .. } => a.is_uninit_valid() && b.is_uninit_valid(),
588        BackendRepr::SimdVector { element, count: _ } | BackendRepr::SimdScalableVector { element, .. } => {
589            element.is_uninit_valid()
590        },
591        // Here validity is determined by the structural fields instead.
592        BackendRepr::Memory { .. } => match &layout.layout.variants {
593            Variants::Single { .. } => match &layout.layout.fields {
594                FieldsShape::Primitive => {
595                    debug_assert!(false, "Both Scalar primitives and ! should be handled above.");
596                    false
597                },
598                // Arrays are valid if empty, or if their elements are valid.
599                FieldsShape::Array { count, .. } => {
600                    if *count == 0 {
601                        true
602                    } else {
603                        is_uninit_value_valid_for_layout(cx, layout.field(cx, 0))
604                    }
605                },
606                // Structs like types are valid only if all fields are valid.
607                FieldsShape::Arbitrary { offsets, .. } => {
608                    (0..offsets.len()).all(|i| is_uninit_value_valid_for_layout(cx, layout.field(cx, i)))
609                },
610                // Unions are valid if at least one field is valid.
611                FieldsShape::Union(count) => {
612                    (0..count.get()).any(|i| is_uninit_value_valid_for_layout(cx, layout.field(cx, i)))
613                },
614            },
615            // Types with no valid variants must be uninhabited
616            Variants::Empty => true,
617            // Enum like with multiple inhabited variants have a discriminant, they cannot be uninitialized.
618            Variants::Multiple { .. } => false,
619        },
620    }
621}
622
623/// Fallback for polymorphic types where `layout_of` fails
624fn is_uninit_value_valid_for_ty_fallback<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
625    let ty::PseudoCanonicalInput { typing_env, value: ty } = cx
626        .typing_env()
627        .with_post_analysis_normalized_invalidating_rigid_aliases(cx.tcx, ty);
628
629    match *ty.kind() {
630        // The array length may be polymorphic, let's try the inner type.
631        ty::Array(component, len) => {
632            // Zero-length arrays are always valid
633            if len.try_to_target_usize(cx.tcx) == Some(0) {
634                return true;
635            }
636            is_uninit_value_valid_for_ty(cx, component)
637        },
638        // Peek through tuples and try their fallbacks.
639        ty::Tuple(types) => types.iter().all(|ty| is_uninit_value_valid_for_ty(cx, ty)),
640        // For Unions, check if any field is uninit
641        ty::Adt(adt, args) if adt.is_union() => adt.all_fields().any(|field| {
642            let unnormalized_field_ty = field.ty(cx.tcx, args);
643            let Ok(field_ty) = cx.tcx.try_normalize_erasing_regions(typing_env, unnormalized_field_ty) else {
644                debug_assert!(
645                    false,
646                    "failed to normalize field type `{unnormalized_field_ty:?}`, ParamEnv is likely set incorrectly."
647                );
648                return false;
649            };
650            is_uninit_value_valid_for_ty(cx, field_ty)
651        }),
652        // Types (e.g. `UnsafeCell<MaybeUninit<T>>`) that recursively contain only types that can be uninit
653        // can themselves be uninit too.
654        // This also applies for single variant enums, whose validity is determined by their fields.
655        ty::Adt(adt, args) if adt.is_struct() || adt.variants().len() == 1 => adt.all_fields().all(|field| {
656            let unnormalized_field_ty = field.ty(cx.tcx, args);
657            let Ok(field_ty) = cx.tcx.try_normalize_erasing_regions(typing_env, unnormalized_field_ty) else {
658                debug_assert!(
659                    false,
660                    "failed to normalize field type `{unnormalized_field_ty:?}`, ParamEnv is likely set incorrectly."
661                );
662                return false;
663            };
664
665            is_uninit_value_valid_for_ty(cx, field_ty)
666        }),
667        // Without a usable whole type layout,
668        // conservatively reject remaining enum cases
669        ty::Adt(adt, _) if adt.is_enum() => false,
670        // Conservatively reject remaining types
671        _ => false,
672    }
673}
674
675/// Gets an iterator over all clauses which apply to the given item.
676pub fn all_clauses_of(tcx: TyCtxt<'_>, id: DefId) -> impl Iterator<Item = &(ty::Clause<'_>, Span)> {
677    let mut next_id = Some(id);
678    iter::from_fn(move || {
679        next_id.take().map(|id| {
680            let gen_clauses = tcx.clauses_of(id);
681            next_id = gen_clauses.parent;
682            gen_clauses.clauses.iter()
683        })
684    })
685    .flatten()
686}
687
688/// A signature for a function like type.
689#[derive(Clone, Copy, Debug)]
690pub enum ExprFnSig<'tcx> {
691    Sig(Binder<'tcx, FnSig<'tcx>>, Option<DefId>),
692    Closure(Option<&'tcx FnDecl<'tcx>>, Binder<'tcx, FnSig<'tcx>>),
693    Trait(Binder<'tcx, Ty<'tcx>>, Option<Binder<'tcx, Ty<'tcx>>>, Option<DefId>),
694}
695impl<'tcx> ExprFnSig<'tcx> {
696    /// Gets the argument type at the given offset. This will return `None` when the index is out of
697    /// bounds only for variadic functions, otherwise this will panic.
698    pub fn input(self, i: usize) -> Option<Binder<'tcx, Ty<'tcx>>> {
699        match self {
700            Self::Sig(sig, _) => {
701                if sig.c_variadic() {
702                    sig.inputs().map_bound(|inputs| inputs.get(i).copied()).transpose()
703                } else {
704                    Some(sig.input(i))
705                }
706            },
707            Self::Closure(_, sig) => Some(sig.input(0).map_bound(|ty| ty.tuple_fields()[i])),
708            Self::Trait(inputs, _, _) => Some(inputs.map_bound(|ty| ty.tuple_fields()[i])),
709        }
710    }
711
712    /// Gets the argument type at the given offset. For closures this will also get the type as
713    /// written. This will return `None` when the index is out of bounds only for variadic
714    /// functions, otherwise this will panic.
715    pub fn input_with_hir(self, i: usize) -> Option<(Option<&'tcx hir::Ty<'tcx>>, Binder<'tcx, Ty<'tcx>>)> {
716        match self {
717            Self::Sig(sig, _) => {
718                if sig.c_variadic() {
719                    sig.inputs()
720                        .map_bound(|inputs| inputs.get(i).copied())
721                        .transpose()
722                        .map(|arg| (None, arg))
723                } else {
724                    Some((None, sig.input(i)))
725                }
726            },
727            Self::Closure(decl, sig) => Some((
728                decl.and_then(|decl| decl.inputs.get(i)),
729                sig.input(0).map_bound(|ty| ty.tuple_fields()[i]),
730            )),
731            Self::Trait(inputs, _, _) => Some((None, inputs.map_bound(|ty| ty.tuple_fields()[i]))),
732        }
733    }
734
735    /// Gets the result type, if one could be found. Note that the result type of a trait may not be
736    /// specified.
737    pub fn output(self) -> Option<Binder<'tcx, Ty<'tcx>>> {
738        match self {
739            Self::Sig(sig, _) | Self::Closure(_, sig) => Some(sig.output()),
740            Self::Trait(_, output, _) => output,
741        }
742    }
743
744    /// Gets the `DefId` of the item whose predicates apply to this signature, if one could be found.
745    pub fn predicates_id(&self) -> Option<DefId> {
746        if let ExprFnSig::Sig(_, id) | ExprFnSig::Trait(_, _, id) = *self {
747            id
748        } else {
749            None
750        }
751    }
752}
753
754/// If the expression is function like, get the signature for it.
755pub fn expr_sig<'tcx>(cx: &LateContext<'tcx>, expr: &Expr<'_>) -> Option<ExprFnSig<'tcx>> {
756    if let Res::Def(DefKind::Fn | DefKind::Ctor(_, CtorKind::Fn) | DefKind::AssocFn, id) = expr.res(cx) {
757        Some(ExprFnSig::Sig(
758            cx.tcx.fn_sig(id).instantiate_identity().skip_norm_wip(),
759            Some(id),
760        ))
761    } else {
762        ty_sig(cx, cx.typeck_results().expr_ty_adjusted(expr).peel_refs())
763    }
764}
765
766/// If the type is function like, get the signature for it.
767pub fn ty_sig<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<ExprFnSig<'tcx>> {
768    if let Some(boxed_ty) = ty.boxed_ty() {
769        return ty_sig(cx, boxed_ty);
770    }
771    match *ty.kind() {
772        ty::Closure(id, subs) => {
773            let decl = id
774                .as_local()
775                .and_then(|id| cx.tcx.hir_fn_decl_by_hir_id(cx.tcx.local_def_id_to_hir_id(id)));
776            Some(ExprFnSig::Closure(decl, subs.as_closure().sig()))
777        },
778        ty::FnDef(id, subs) => Some(ExprFnSig::Sig(
779            cx.tcx
780                .fn_sig(id)
781                .instantiate(cx.tcx, subs.no_bound_vars().unwrap())
782                .skip_norm_wip(),
783            Some(id),
784        )),
785        ty::Alias(
786            _,
787            AliasTy {
788                kind: ty::Opaque { def_id },
789                args,
790                ..
791            },
792        ) => sig_from_bounds(
793            cx,
794            ty,
795            cx.tcx
796                .item_self_bounds(def_id)
797                .iter_instantiated(cx.tcx, args)
798                .map(|clause| cx.tcx.normalize_erasing_regions(cx.typing_env(), clause)),
799            cx.tcx.opt_parent(def_id),
800        ),
801        ty::FnPtr(sig_tys, hdr) => Some(ExprFnSig::Sig(sig_tys.with(hdr), None)),
802        ty::Dynamic(bounds, _) => {
803            let lang_items = cx.tcx.lang_items();
804            match bounds.principal() {
805                Some(bound)
806                    if Some(bound.def_id()) == lang_items.fn_trait()
807                        || Some(bound.def_id()) == lang_items.fn_once_trait()
808                        || Some(bound.def_id()) == lang_items.fn_mut_trait() =>
809                {
810                    let output = bounds
811                        .projection_bounds()
812                        .find(|p| lang_items.fn_once_output().is_some_and(|id| id == p.item_def_id()))
813                        .map(|p| p.map_bound(|p| p.term.expect_type()));
814                    Some(ExprFnSig::Trait(bound.map_bound(|b| b.args.type_at(0)), output, None))
815                },
816                _ => None,
817            }
818        },
819        ty::Alias(_, alias) if let Some(proj) = alias.try_to_projection() => match cx
820            .tcx
821            .try_normalize_erasing_regions(cx.typing_env(), Unnormalized::new_wip(ty))
822        {
823            Ok(normalized_ty) if normalized_ty != ty => ty_sig(cx, normalized_ty),
824            _ => sig_for_projection(cx, proj)
825                .or_else(|| sig_from_bounds(cx, ty, cx.param_env.caller_bounds().all_clauses(cx.tcx).iter(), None)),
826        },
827        ty::Param(_) => sig_from_bounds(cx, ty, cx.param_env.caller_bounds().all_clauses(cx.tcx).iter(), None),
828        _ => None,
829    }
830}
831
832fn sig_from_bounds<'tcx>(
833    cx: &LateContext<'tcx>,
834    ty: Ty<'tcx>,
835    clauses: impl IntoIterator<Item = ty::Clause<'tcx>>,
836    predicates_id: Option<DefId>,
837) -> Option<ExprFnSig<'tcx>> {
838    let mut inputs = None;
839    let mut output = None;
840    let lang_items = cx.tcx.lang_items();
841
842    for clause in clauses {
843        match clause.kind().skip_binder() {
844            ty::ClauseKind::Trait(p)
845                if (lang_items.fn_trait() == Some(p.def_id())
846                    || lang_items.fn_mut_trait() == Some(p.def_id())
847                    || lang_items.fn_once_trait() == Some(p.def_id()))
848                    && p.self_ty() == ty =>
849            {
850                let i = clause.kind().rebind(p.trait_ref.args.type_at(1));
851                if inputs.is_some_and(|inputs| i != inputs) {
852                    // Multiple different fn trait impls. Is this even allowed?
853                    return None;
854                }
855                inputs = Some(i);
856            },
857            ty::ClauseKind::Projection(p)
858                if Some(p.projection_term.expect_projection_def_id()) == lang_items.fn_once_output()
859                    && p.projection_term.self_ty() == ty =>
860            {
861                if output.is_some() {
862                    // Multiple different fn trait impls. Is this even allowed?
863                    return None;
864                }
865                output = Some(clause.kind().rebind(p.term.expect_type()));
866            },
867            _ => (),
868        }
869    }
870
871    inputs.map(|ty| ExprFnSig::Trait(ty, output, predicates_id))
872}
873
874fn sig_for_projection<'tcx>(cx: &LateContext<'tcx>, ty: ProjectionAliasTy<'tcx>) -> Option<ExprFnSig<'tcx>> {
875    let mut inputs = None;
876    let mut output = None;
877    let lang_items = cx.tcx.lang_items();
878
879    for (pred, _) in cx
880        .tcx
881        .explicit_item_bounds(ty.kind)
882        .iter_instantiated_copied(cx.tcx, ty.args)
883        .map(Unnormalized::skip_norm_wip)
884    {
885        match pred.kind().skip_binder() {
886            ty::ClauseKind::Trait(p)
887                if (lang_items.fn_trait() == Some(p.def_id())
888                    || lang_items.fn_mut_trait() == Some(p.def_id())
889                    || lang_items.fn_once_trait() == Some(p.def_id())) =>
890            {
891                let i = pred.kind().rebind(p.trait_ref.args.type_at(1));
892
893                if inputs.is_some_and(|inputs| inputs != i) {
894                    // Multiple different fn trait impls. Is this even allowed?
895                    return None;
896                }
897                inputs = Some(i);
898            },
899            ty::ClauseKind::Projection(p)
900                if Some(p.projection_term.expect_projection_def_id()) == lang_items.fn_once_output() =>
901            {
902                if output.is_some() {
903                    // Multiple different fn trait impls. Is this even allowed?
904                    return None;
905                }
906                output = pred.kind().rebind(p.term.as_type()).transpose();
907            },
908            _ => (),
909        }
910    }
911
912    inputs.map(|ty| ExprFnSig::Trait(ty, output, None))
913}
914
915#[derive(Clone, Copy)]
916pub enum EnumValue {
917    Unsigned(u128),
918    Signed(i128),
919}
920impl core::ops::Add<u32> for EnumValue {
921    type Output = Self;
922    fn add(self, n: u32) -> Self::Output {
923        match self {
924            Self::Unsigned(x) => Self::Unsigned(x + u128::from(n)),
925            Self::Signed(x) => Self::Signed(x + i128::from(n)),
926        }
927    }
928}
929
930/// Attempts to read the given constant as though it were an enum value.
931pub fn read_explicit_enum_value(tcx: TyCtxt<'_>, id: DefId) -> Option<EnumValue> {
932    if let Ok(ConstValue::Scalar(Scalar::Int(value))) = tcx.const_eval_poly(id) {
933        match tcx.type_of(id).instantiate_identity().skip_norm_wip().kind() {
934            ty::Int(_) => Some(EnumValue::Signed(value.to_int(value.size()))),
935            ty::Uint(_) => Some(EnumValue::Unsigned(value.to_uint(value.size()))),
936            _ => None,
937        }
938    } else {
939        None
940    }
941}
942
943/// Gets the value of the given variant.
944pub fn get_discriminant_value(tcx: TyCtxt<'_>, adt: AdtDef<'_>, i: VariantIdx) -> EnumValue {
945    let variant = &adt.variant(i);
946    match variant.discr {
947        VariantDiscr::Explicit(id) => read_explicit_enum_value(tcx, id).unwrap(),
948        VariantDiscr::Relative(x) => match adt.variant((i.as_usize() - x as usize).into()).discr {
949            VariantDiscr::Explicit(id) => read_explicit_enum_value(tcx, id).unwrap() + x,
950            VariantDiscr::Relative(_) => EnumValue::Unsigned(x.into()),
951        },
952    }
953}
954
955/// Check if the given type is either `core::ffi::c_void`, `std::os::raw::c_void`, or one of the
956/// platform specific `libc::<platform>::c_void` types in libc.
957pub fn is_c_void(cx: &LateContext<'_>, ty: Ty<'_>) -> bool {
958    if let ty::Adt(adt, _) = ty.kind()
959        && let &[krate, .., name] = &*cx.get_def_path(adt.did())
960        && let sym::libc | sym::core | sym::std = krate
961        && name == sym::c_void
962    {
963        true
964    } else {
965        false
966    }
967}
968
969/// Calls `f` for each late-bound region in `ty` that is bound by the enclosing binder.
970///
971/// This ignores regions bound by nested binders.
972pub fn for_each_top_level_late_bound_region<'cx, B>(
973    ty: Ty<'cx>,
974    f: impl FnMut(BoundRegion<'cx>) -> ControlFlow<B>,
975) -> ControlFlow<B> {
976    struct V<F> {
977        index: u32,
978        f: F,
979    }
980    impl<'tcx, B, F: FnMut(BoundRegion<'tcx>) -> ControlFlow<B>> TypeVisitor<TyCtxt<'tcx>> for V<F> {
981        type Result = ControlFlow<B>;
982        fn visit_region(&mut self, r: Region<'tcx>) -> Self::Result {
983            if let RegionKind::ReBound(BoundVarIndexKind::Bound(idx), bound) = r.kind()
984                && idx.as_u32() == self.index
985            {
986                (self.f)(bound)
987            } else {
988                ControlFlow::Continue(())
989            }
990        }
991        fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, t: &Binder<'tcx, T>) -> Self::Result {
992            self.index += 1;
993            let res = t.super_visit_with(self);
994            self.index -= 1;
995            res
996        }
997    }
998    ty.visit_with(&mut V { index: 0, f })
999}
1000
1001pub struct AdtVariantInfo {
1002    pub ind: usize,
1003    pub size: u64,
1004
1005    /// (ind, size)
1006    pub fields_size: Vec<(usize, u64)>,
1007}
1008
1009impl AdtVariantInfo {
1010    /// Returns ADT variants ordered by size
1011    pub fn new<'tcx>(cx: &LateContext<'tcx>, adt: AdtDef<'tcx>, subst: GenericArgs<'tcx>) -> Vec<Self> {
1012        let mut variants_size = adt
1013            .variants()
1014            .iter()
1015            .enumerate()
1016            .map(|(i, variant)| {
1017                let mut fields_size = variant
1018                    .fields
1019                    .iter()
1020                    .enumerate()
1021                    .map(|(i, f)| (i, approx_ty_size(cx, f.ty(cx.tcx, subst).skip_norm_wip())))
1022                    .collect::<Vec<_>>();
1023                fields_size.sort_by_key(|(_, a_size)| *a_size);
1024
1025                Self {
1026                    ind: i,
1027                    size: fields_size.iter().map(|(_, size)| size).sum(),
1028                    fields_size,
1029                }
1030            })
1031            .collect::<Vec<_>>();
1032        variants_size.sort_by_key(|b| std::cmp::Reverse(b.size));
1033        variants_size
1034    }
1035}
1036
1037/// Gets the struct or enum variant from the given `Res`
1038pub fn adt_and_variant_of_res<'tcx>(cx: &LateContext<'tcx>, res: Res) -> Option<(AdtDef<'tcx>, &'tcx VariantDef)> {
1039    match res {
1040        Res::Def(DefKind::Struct, id) => {
1041            let adt = cx.tcx.adt_def(id);
1042            Some((adt, adt.non_enum_variant()))
1043        },
1044        Res::Def(DefKind::Variant, id) => {
1045            let adt = cx.tcx.adt_def(cx.tcx.parent(id));
1046            Some((adt, adt.variant_with_id(id)))
1047        },
1048        Res::Def(DefKind::Ctor(CtorOf::Struct, _), id) => {
1049            let adt = cx.tcx.adt_def(cx.tcx.parent(id));
1050            Some((adt, adt.non_enum_variant()))
1051        },
1052        Res::Def(DefKind::Ctor(CtorOf::Variant, _), id) => {
1053            let var_id = cx.tcx.parent(id);
1054            let adt = cx.tcx.adt_def(cx.tcx.parent(var_id));
1055            Some((adt, adt.variant_with_id(var_id)))
1056        },
1057        Res::SelfCtor(id) => {
1058            let adt = cx
1059                .tcx
1060                .type_of(id)
1061                .instantiate_identity()
1062                .skip_norm_wip()
1063                .ty_adt_def()
1064                .unwrap();
1065            Some((adt, adt.non_enum_variant()))
1066        },
1067        _ => None,
1068    }
1069}
1070
1071/// Comes up with an "at least" guesstimate for the type's size, not taking into
1072/// account the layout of type parameters.
1073pub fn approx_ty_size<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> u64 {
1074    use rustc_middle::ty::layout::LayoutOf as _;
1075    match (cx.layout_of(ty).map(|layout| layout.size.bytes()), ty.kind()) {
1076        (Ok(size), _) => size,
1077        (Err(_), ty::Tuple(list)) => list.iter().map(|t| approx_ty_size(cx, t)).sum(),
1078        (Err(_), ty::Array(t, n)) => n.try_to_target_usize(cx.tcx).unwrap_or_default() * approx_ty_size(cx, *t),
1079        (Err(_), ty::Adt(def, subst)) if def.is_struct() => def
1080            .variants()
1081            .iter()
1082            .map(|v| {
1083                v.fields
1084                    .iter()
1085                    .map(|field| approx_ty_size(cx, field.ty(cx.tcx, *subst).skip_norm_wip()))
1086                    .sum::<u64>()
1087            })
1088            .sum(),
1089        (Err(_), ty::Adt(def, subst)) if def.is_enum() => def
1090            .variants()
1091            .iter()
1092            .map(|v| {
1093                v.fields
1094                    .iter()
1095                    .map(|field| approx_ty_size(cx, field.ty(cx.tcx, *subst).skip_norm_wip()))
1096                    .sum::<u64>()
1097            })
1098            .max()
1099            .unwrap_or_default(),
1100        (Err(_), ty::Adt(def, subst)) if def.is_union() => def
1101            .variants()
1102            .iter()
1103            .map(|v| {
1104                v.fields
1105                    .iter()
1106                    .map(|field| approx_ty_size(cx, field.ty(cx.tcx, *subst).skip_norm_wip()))
1107                    .max()
1108                    .unwrap_or_default()
1109            })
1110            .max()
1111            .unwrap_or_default(),
1112        (Err(_), _) => 0,
1113    }
1114}
1115
1116#[cfg(debug_assertions)]
1117/// Asserts that the given arguments match the generic parameters of the given item.
1118fn assert_generic_args_match<'tcx>(tcx: TyCtxt<'tcx>, did: DefId, args: &[GenericArg<'tcx>]) {
1119    use itertools::Itertools as _;
1120    let g = tcx.generics_of(did);
1121    let parent = g.parent.map(|did| tcx.generics_of(did));
1122    let count = g.parent_count + g.own_params.len();
1123    let params = parent
1124        .map_or([].as_slice(), |p| p.own_params.as_slice())
1125        .iter()
1126        .chain(&g.own_params)
1127        .map(|x| &x.kind);
1128
1129    assert!(
1130        count == args.len(),
1131        "wrong number of arguments for `{did:?}`: expected `{count}`, found {}\n\
1132            note: the expected arguments are: `[{}]`\n\
1133            the given arguments are: `{args:#?}`",
1134        args.len(),
1135        params.clone().map(ty::GenericParamDefKind::descr).format(", "),
1136    );
1137
1138    if let Some((idx, (param, arg))) =
1139        params
1140            .clone()
1141            .zip(args.iter().map(|&x| x.kind()))
1142            .enumerate()
1143            .find(|(_, (param, arg))| match (param, arg) {
1144                (ty::GenericParamDefKind::Lifetime, GenericArgKind::Lifetime(_))
1145                | (ty::GenericParamDefKind::Type { .. }, GenericArgKind::Type(_))
1146                | (ty::GenericParamDefKind::Const { .. }, GenericArgKind::Const(_)) => false,
1147                (
1148                    ty::GenericParamDefKind::Lifetime
1149                    | ty::GenericParamDefKind::Type { .. }
1150                    | ty::GenericParamDefKind::Const { .. },
1151                    _,
1152                ) => true,
1153            })
1154    {
1155        panic!(
1156            "incorrect argument for `{did:?}` at index `{idx}`: expected a {}, found `{arg:?}`\n\
1157                note: the expected arguments are `[{}]`\n\
1158                the given arguments are `{args:#?}`",
1159            param.descr(),
1160            params.clone().map(ty::GenericParamDefKind::descr).format(", "),
1161        );
1162    }
1163}
1164
1165/// Returns whether `ty` is never-like; i.e., `!` (never) or an enum with zero variants.
1166pub fn is_never_like(ty: Ty<'_>) -> bool {
1167    ty.is_never() || (ty.is_enum() && ty.ty_adt_def().is_some_and(|def| def.variants().is_empty()))
1168}
1169
1170/// Makes the projection type for the named associated type in the given impl or trait impl.
1171///
1172/// This function is for associated types which are "known" to exist, and as such, will only return
1173/// `None` when debug assertions are disabled in order to prevent ICE's. With debug assertions
1174/// enabled this will check that the named associated type exists, the correct number of
1175/// arguments are given, and that the correct kinds of arguments are given (lifetime,
1176/// constant or type). This will not check if type normalization would succeed.
1177pub fn make_projection<'tcx>(
1178    tcx: TyCtxt<'tcx>,
1179    container_id: DefId,
1180    assoc_ty: Symbol,
1181    args: impl IntoIterator<Item = impl Into<GenericArg<'tcx>>>,
1182) -> Option<AliasTy<'tcx>> {
1183    fn helper<'tcx>(
1184        tcx: TyCtxt<'tcx>,
1185        container_id: DefId,
1186        assoc_ty: Symbol,
1187        args: GenericArgs<'tcx>,
1188    ) -> Option<AliasTy<'tcx>> {
1189        let Some(assoc_item) = tcx.associated_items(container_id).find_by_ident_and_kind(
1190            tcx,
1191            Ident::with_dummy_span(assoc_ty),
1192            AssocTag::Type,
1193            container_id,
1194        ) else {
1195            debug_assert!(false, "type `{assoc_ty}` not found in `{container_id:?}`");
1196            return None;
1197        };
1198        #[cfg(debug_assertions)]
1199        assert_generic_args_match(tcx, assoc_item.def_id, args.as_slice());
1200
1201        let kind = if let DefKind::Impl { of_trait: false } = tcx.def_kind(tcx.parent(assoc_item.def_id)) {
1202            ty::AliasTyKind::Inherent {
1203                def_id: assoc_item.def_id,
1204            }
1205        } else {
1206            ty::AliasTyKind::Projection {
1207                def_id: assoc_item.def_id,
1208            }
1209        };
1210
1211        Some(AliasTy::new_from_args(tcx, kind, args))
1212    }
1213    helper(
1214        tcx,
1215        container_id,
1216        assoc_ty,
1217        tcx.mk_args_from_iter(args.into_iter().map(Into::into)),
1218    )
1219}
1220
1221/// Normalizes the named associated type in the given impl or trait impl.
1222///
1223/// This function is for associated types which are "known" to be valid with the given
1224/// arguments, and as such, will only return `None` when debug assertions are disabled in order
1225/// to prevent ICE's. With debug assertions enabled this will check that type normalization
1226/// succeeds as well as everything checked by `make_projection`.
1227pub fn make_normalized_projection<'tcx>(
1228    tcx: TyCtxt<'tcx>,
1229    typing_env: ty::TypingEnv<'tcx>,
1230    container_id: DefId,
1231    assoc_ty: Symbol,
1232    args: impl IntoIterator<Item = impl Into<GenericArg<'tcx>>>,
1233) -> Option<Ty<'tcx>> {
1234    fn helper<'tcx>(tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>, ty: AliasTy<'tcx>) -> Option<Ty<'tcx>> {
1235        #[cfg(debug_assertions)]
1236        if let Some((i, arg)) = ty
1237            .args
1238            .iter()
1239            .enumerate()
1240            .find(|(_, arg)| arg.has_escaping_bound_vars())
1241        {
1242            debug_assert!(
1243                false,
1244                "args contain late-bound region at index `{i}` which can't be normalized.\n\
1245                    use `TyCtxt::instantiate_bound_regions_with_erased`\n\
1246                    note: arg is `{arg:#?}`",
1247            );
1248            return None;
1249        }
1250        match tcx.try_normalize_erasing_regions(
1251            typing_env,
1252            Unnormalized::new_wip(Ty::new_alias(tcx, ty::IsRigid::No, ty)),
1253        ) {
1254            Ok(ty) => Some(ty),
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
1264/// Helper to check if given type has inner mutability such as [`std::cell::Cell`] or
1265/// [`std::cell::RefCell`].
1266#[derive(Default, Debug)]
1267pub struct InteriorMut<'tcx> {
1268    ignored_def_ids: FxHashSet<DefId>,
1269    ignore_pointers: bool,
1270    tys: FxHashMap<Ty<'tcx>, Option<&'tcx ty::List<Ty<'tcx>>>>,
1271}
1272
1273impl<'tcx> InteriorMut<'tcx> {
1274    pub fn new(tcx: TyCtxt<'tcx>, ignore_interior_mutability: &[String]) -> Self {
1275        let ignored_def_ids = ignore_interior_mutability
1276            .iter()
1277            .flat_map(|ignored_ty| lookup_path_str(tcx, PathNS::Type, ignored_ty))
1278            .collect();
1279
1280        Self {
1281            ignored_def_ids,
1282            ..Self::default()
1283        }
1284    }
1285
1286    /// Creates a new [`InteriorMut`] instance that ignores raw pointers.
1287    pub fn without_pointers(tcx: TyCtxt<'tcx>, ignore_interior_mutability: &[String]) -> Self {
1288        Self {
1289            ignore_pointers: true,
1290            ..Self::new(tcx, ignore_interior_mutability)
1291        }
1292    }
1293
1294    /// Check if given type has interior mutability such as [`std::cell::Cell`] or
1295    /// [`std::cell::RefCell`] etc. and if it does, returns a chain of types that causes
1296    /// this type to be interior mutable.  False negatives may be expected for infinitely recursive
1297    /// types, and `None` will be returned there.
1298    pub fn interior_mut_ty_chain(&mut self, cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<&'tcx ty::List<Ty<'tcx>>> {
1299        self.interior_mut_ty_chain_inner(cx, ty, 0)
1300    }
1301
1302    fn interior_mut_ty_chain_inner(
1303        &mut self,
1304        cx: &LateContext<'tcx>,
1305        ty: Ty<'tcx>,
1306        depth: usize,
1307    ) -> Option<&'tcx ty::List<Ty<'tcx>>> {
1308        if !cx.tcx.recursion_limit().value_within_limit(depth) {
1309            return None;
1310        }
1311
1312        match self.tys.entry(ty) {
1313            Entry::Occupied(o) => return *o.get(),
1314            // Temporarily insert a `None` to break cycles
1315            Entry::Vacant(v) => v.insert(None),
1316        };
1317        let depth = depth + 1;
1318
1319        let chain = match *ty.kind() {
1320            ty::RawPtr(inner_ty, _) if !self.ignore_pointers => self.interior_mut_ty_chain_inner(cx, inner_ty, depth),
1321            ty::Ref(_, inner_ty, _) | ty::Slice(inner_ty) => self.interior_mut_ty_chain_inner(cx, inner_ty, depth),
1322            ty::Array(inner_ty, size) if size.try_to_target_usize(cx.tcx) != Some(0) => {
1323                self.interior_mut_ty_chain_inner(cx, inner_ty, depth)
1324            },
1325            ty::Tuple(fields) => fields
1326                .iter()
1327                .find_map(|ty| self.interior_mut_ty_chain_inner(cx, ty, depth)),
1328            ty::Adt(def, _) if def.is_unsafe_cell() => Some(ty::List::empty()),
1329            ty::Adt(def, args) => {
1330                let is_std_collection = matches!(
1331                    cx.tcx.get_diagnostic_name(def.did()),
1332                    Some(
1333                        sym::LinkedList
1334                            | sym::Vec
1335                            | sym::VecDeque
1336                            | sym::BTreeMap
1337                            | sym::BTreeSet
1338                            | sym::HashMap
1339                            | sym::HashSet
1340                            | sym::Arc
1341                            | sym::Rc
1342                    )
1343                );
1344
1345                if is_std_collection || def.is_box() {
1346                    // Include the types from std collections that are behind pointers internally
1347                    args.types()
1348                        .find_map(|ty| self.interior_mut_ty_chain_inner(cx, ty, depth))
1349                } else if self.ignored_def_ids.contains(&def.did()) || def.is_phantom_data() {
1350                    None
1351                } else {
1352                    def.all_fields()
1353                        .find_map(|f| self.interior_mut_ty_chain_inner(cx, f.ty(cx.tcx, args).skip_norm_wip(), depth))
1354                }
1355            },
1356            ty::Alias(
1357                _,
1358                AliasTy {
1359                    kind: ty::Projection { .. },
1360                    ..
1361                },
1362            ) => match cx
1363                .tcx
1364                .try_normalize_erasing_regions(cx.typing_env(), Unnormalized::new_wip(ty))
1365            {
1366                Ok(normalized_ty) if ty != normalized_ty => self.interior_mut_ty_chain_inner(cx, normalized_ty, depth),
1367                _ => None,
1368            },
1369            _ => None,
1370        };
1371
1372        chain.map(|chain| {
1373            let list = cx.tcx.mk_type_list_from_iter(chain.iter().chain([ty]));
1374            self.tys.insert(ty, Some(list));
1375            list
1376        })
1377    }
1378
1379    /// Check if given type has interior mutability such as [`std::cell::Cell`] or
1380    /// [`std::cell::RefCell`] etc.
1381    pub fn is_interior_mut_ty(&mut self, cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
1382        self.interior_mut_ty_chain(cx, ty).is_some()
1383    }
1384}
1385
1386/// Tries to normalize a projection type without erasing regions.
1387///
1388/// Returns `None` if the projection can't be built or normalized.
1389/// With `debug_assertions` enabled, this will panic instead of returning `None`.
1390pub fn make_normalized_projection_with_regions<'tcx>(
1391    tcx: TyCtxt<'tcx>,
1392    typing_env: ty::TypingEnv<'tcx>,
1393    container_id: DefId,
1394    assoc_ty: Symbol,
1395    args: impl IntoIterator<Item = impl Into<GenericArg<'tcx>>>,
1396) -> Option<Ty<'tcx>> {
1397    fn helper<'tcx>(tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>, ty: AliasTy<'tcx>) -> Option<Ty<'tcx>> {
1398        #[cfg(debug_assertions)]
1399        if let Some((i, arg)) = ty
1400            .args
1401            .iter()
1402            .enumerate()
1403            .find(|(_, arg)| arg.has_escaping_bound_vars())
1404        {
1405            debug_assert!(
1406                false,
1407                "args contain late-bound region at index `{i}` which can't be normalized.\n\
1408                    use `TyCtxt::instantiate_bound_regions_with_erased`\n\
1409                    note: arg is `{arg:#?}`",
1410            );
1411            return None;
1412        }
1413        let cause = ObligationCause::dummy();
1414        let (infcx, param_env) = tcx.infer_ctxt().build_with_typing_env(typing_env);
1415        match infcx
1416            .at(&cause, param_env)
1417            .query_normalize(Ty::new_alias(tcx, ty::IsRigid::No, ty))
1418        {
1419            Ok(ty) => Some(ty.value),
1420            Err(e) => {
1421                debug_assert!(false, "failed to normalize type `{ty}`: {e:#?}");
1422                None
1423            },
1424        }
1425    }
1426    helper(tcx, typing_env, make_projection(tcx, container_id, assoc_ty, args)?)
1427}
1428
1429/// Normalizes the given type, without erasing regions.
1430/// If normalization fails it falls back to returning the original un-normalized type.
1431pub fn normalize_with_regions<'tcx>(tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
1432    let cause = ObligationCause::dummy();
1433    let (infcx, param_env) = tcx.infer_ctxt().build_with_typing_env(typing_env);
1434    infcx
1435        .at(&cause, param_env)
1436        .query_normalize(ty)
1437        .map_or(ty, |ty| ty.value)
1438}
1439
1440/// Checks if the type is `core::mem::ManuallyDrop<_>`
1441pub fn is_manually_drop(ty: Ty<'_>) -> bool {
1442    ty.ty_adt_def().is_some_and(AdtDef::is_manually_drop)
1443}
1444
1445/// Returns the deref chain of a type, starting with the type itself.
1446pub fn deref_chain<'cx, 'tcx>(cx: &'cx LateContext<'tcx>, ty: Ty<'tcx>) -> impl Iterator<Item = Ty<'tcx>> + 'cx {
1447    iter::successors(Some(ty), |&ty| {
1448        if let Some(deref_did) = cx.tcx.lang_items().deref_trait()
1449            && implements_trait(cx, ty, deref_did, &[])
1450        {
1451            make_normalized_projection(cx.tcx, cx.typing_env(), deref_did, sym::Target, [ty])
1452        } else {
1453            None
1454        }
1455    })
1456}
1457
1458/// Checks if a Ty<'_> has some inherent method Symbol.
1459///
1460/// This does not look for impls in the type's `Deref::Target` type.
1461/// If you need this, you should wrap this call in `clippy_utils::ty::deref_chain().any(...)`.
1462pub fn get_adt_inherent_method<'a>(cx: &'a LateContext<'_>, ty: Ty<'_>, method_name: Symbol) -> Option<&'a AssocItem> {
1463    let ty_did = ty.ty_adt_def().map(AdtDef::did)?;
1464    cx.tcx.inherent_impls(ty_did).iter().find_map(|&did| {
1465        cx.tcx
1466            .associated_items(did)
1467            .filter_by_name_unhygienic_and_kind(method_name, AssocTag::Fn)
1468            .next()
1469    })
1470}
1471
1472/// Gets the type of a field by name.
1473pub fn get_field_by_name<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, name: Symbol) -> Option<Ty<'tcx>> {
1474    match *ty.kind() {
1475        ty::Adt(def, args) if def.is_union() || def.is_struct() => def
1476            .non_enum_variant()
1477            .fields
1478            .iter()
1479            .find(|f| f.name == name)
1480            .map(|f| f.ty(tcx, args).skip_norm_wip()),
1481        ty::Tuple(args) => name.as_str().parse::<usize>().ok().and_then(|i| args.get(i).copied()),
1482        _ => None,
1483    }
1484}
1485
1486/// Attempts to find the field's `DefId` by name.
1487/// Returns `None` if the type is not an ADT or the field is not found.
1488pub fn get_field_def_id_by_name(ty: Ty<'_>, name: Symbol) -> Option<DefId> {
1489    ty.ty_adt_def()?
1490        .all_fields()
1491        .find_map(|field| if field.name == name { Some(field.did) } else { None })
1492}
1493
1494/// Check if `ty` is an `Option` and return its argument type if it is.
1495pub fn option_arg_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
1496    match *ty.kind() {
1497        ty::Adt(adt, args)
1498            if let [arg] = *args.as_slice()
1499                && let Some(arg) = arg.as_type()
1500                && adt.is_diag_item(cx, sym::Option) =>
1501        {
1502            Some(arg)
1503        },
1504        _ => None,
1505    }
1506}
1507
1508/// Check if `ty` is an `Option<T>` or a `Result<T, E>` and return its argument type (`T`) if it is.
1509pub fn option_or_result_arg_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
1510    match ty.kind() {
1511        ty::Adt(adt, args) if matches!(adt.opt_diag_name(cx), Some(sym::Option | sym::Result)) => Some(args.type_at(0)),
1512        _ => None,
1513    }
1514}
1515
1516/// Check if a Ty<'_> of `Iterator` contains any mutable access to non-owning types by checking if
1517/// it contains fields of mutable references or pointers, or references/pointers to non-`Freeze`
1518/// types, or `PhantomData` types containing any of the previous. This can be used to check whether
1519/// skipping iterating over an iterator will change its behavior.
1520pub fn has_non_owning_mutable_access<'tcx>(cx: &LateContext<'tcx>, iter_ty: Ty<'tcx>) -> bool {
1521    fn normalize_ty<'tcx>(cx: &LateContext<'tcx>, ty: Unnormalized<'tcx, Ty<'tcx>>) -> Ty<'tcx> {
1522        cx.tcx
1523            .try_normalize_erasing_regions(cx.typing_env(), ty)
1524            .unwrap_or(ty.skip_norm_wip())
1525    }
1526
1527    /// Check if `ty` contains mutable references or equivalent, which includes:
1528    /// - A mutable reference/pointer.
1529    /// - A reference/pointer to a non-`Freeze` type.
1530    /// - A `PhantomData` type containing any of the previous.
1531    fn has_non_owning_mutable_access_inner<'tcx>(
1532        cx: &LateContext<'tcx>,
1533        visited: &mut FxHashSet<Ty<'tcx>>,
1534        ty: Ty<'tcx>,
1535    ) -> bool {
1536        // Avoid cycles and repeated work by skipping types that have already been visited during this traversal.
1537        if !visited.insert(ty) {
1538            return false;
1539        }
1540        match ty.kind() {
1541            ty::Adt(adt_def, args) if adt_def.is_phantom_data() => args
1542                .types()
1543                .any(|arg_ty| has_non_owning_mutable_access_inner(cx, visited, arg_ty)),
1544            ty::Adt(adt_def, args) => adt_def.all_fields().any(|field| {
1545                has_non_owning_mutable_access_inner(cx, visited, normalize_ty(cx, field.ty(cx.tcx, *args)))
1546            }),
1547            ty::Array(elem_ty, _) | ty::Slice(elem_ty) => has_non_owning_mutable_access_inner(cx, visited, *elem_ty),
1548            ty::RawPtr(pointee_ty, mutability) | ty::Ref(_, pointee_ty, mutability) => {
1549                mutability.is_mut() || !pointee_ty.is_freeze(cx.tcx, cx.typing_env())
1550            },
1551            ty::Closure(_, closure_args) => {
1552                matches!(closure_args.types().next_back(),
1553                         Some(captures) if has_non_owning_mutable_access_inner(cx, visited, captures))
1554            },
1555            ty::Tuple(tuple_args) => tuple_args
1556                .iter()
1557                .any(|arg_ty| has_non_owning_mutable_access_inner(cx, visited, arg_ty)),
1558            _ => false,
1559        }
1560    }
1561
1562    has_non_owning_mutable_access_inner(cx, &mut FxHashSet::default(), iter_ty)
1563}
1564
1565/// Check if `ty` is slice-like, i.e., `&[T]`, `[T; N]`, or `Vec<T>`.
1566pub fn is_slice_like<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> bool {
1567    ty.is_slice() || ty.is_array() || ty.is_diag_item(cx, sym::Vec)
1568}
1569
1570/// Attempts to find the field's index by name, for unions, structs and tuples.
1571/// Note: for tuples, `name` is just parsed as an index.
1572pub fn get_field_idx_by_name(ty: Ty<'_>, name: Symbol) -> Option<usize> {
1573    match *ty.kind() {
1574        ty::Adt(def, _) if def.is_union() || def.is_struct() => {
1575            def.non_enum_variant().fields.iter().position(|f| f.name == name)
1576        },
1577        ty::Tuple(_) => name.as_str().parse::<usize>().ok(),
1578        _ => None,
1579    }
1580}
1581
1582/// Checks if the adjustments contain a mutable dereference of a `ManuallyDrop<_>`.
1583pub fn adjust_derefs_manually_drop<'tcx>(adjustments: &'tcx [Adjustment<'tcx>], mut ty: Ty<'tcx>) -> bool {
1584    adjustments.iter().any(|a| {
1585        let ty = mem::replace(&mut ty, a.target);
1586        matches!(a.kind, Adjust::Deref(DerefAdjustKind::Overloaded(op)) if op.mutbl == Mutability::Mut)
1587            && is_manually_drop(ty)
1588    })
1589}