rustc_middle/
thir.rs

1//! THIR datatypes and definitions. See the [rustc dev guide] for more info.
2//!
3//! If you compare the THIR [`ExprKind`] to [`hir::ExprKind`], you will see it is
4//! a good bit simpler. In fact, a number of the more straight-forward
5//! MIR simplifications are already done in the lowering to THIR. For
6//! example, method calls and overloaded operators are absent: they are
7//! expected to be converted into [`ExprKind::Call`] instances.
8//!
9//! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/thir.html
10
11use std::cmp::Ordering;
12use std::fmt;
13use std::ops::Index;
14use std::sync::Arc;
15
16use rustc_abi::{FieldIdx, Integer, Size, VariantIdx};
17use rustc_ast::{AsmMacro, InlineAsmOptions, InlineAsmTemplatePiece};
18use rustc_hir as hir;
19use rustc_hir::def_id::DefId;
20use rustc_hir::{BindingMode, ByRef, HirId, MatchSource, RangeEnd};
21use rustc_index::{IndexVec, newtype_index};
22use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeVisitable};
23use rustc_span::def_id::LocalDefId;
24use rustc_span::{ErrorGuaranteed, Span, Symbol};
25use rustc_target::asm::InlineAsmRegOrRegClass;
26use tracing::instrument;
27
28use crate::middle::region;
29use crate::mir::interpret::AllocId;
30use crate::mir::{self, AssignOp, BinOp, BorrowKind, FakeReadCause, UnOp};
31use crate::thir::visit::for_each_immediate_subpat;
32use crate::ty::adjustment::PointerCoercion;
33use crate::ty::layout::IntegerExt;
34use crate::ty::{
35    self, AdtDef, CanonicalUserType, CanonicalUserTypeAnnotation, FnSig, GenericArgsRef, List, Ty,
36    TyCtxt, UpvarArgs,
37};
38
39pub mod visit;
40
41macro_rules! thir_with_elements {
42    (
43        $($name:ident: $id:ty => $value:ty => $format:literal,)*
44    ) => {
45        $(
46            newtype_index! {
47                #[derive(HashStable)]
48                #[debug_format = $format]
49                pub struct $id {}
50            }
51        )*
52
53        // Note: Making `Thir` implement `Clone` is useful for external tools that need access to
54        // THIR bodies even after the `Steal` query result has been stolen.
55        // One such tool is https://github.com/rust-corpus/qrates/.
56        /// A container for a THIR body.
57        ///
58        /// This can be indexed directly by any THIR index (e.g. [`ExprId`]).
59        #[derive(Debug, HashStable, Clone)]
60        pub struct Thir<'tcx> {
61            pub body_type: BodyTy<'tcx>,
62            $(
63                pub $name: IndexVec<$id, $value>,
64            )*
65        }
66
67        impl<'tcx> Thir<'tcx> {
68            pub fn new(body_type: BodyTy<'tcx>) -> Thir<'tcx> {
69                Thir {
70                    body_type,
71                    $(
72                        $name: IndexVec::new(),
73                    )*
74                }
75            }
76        }
77
78        $(
79            impl<'tcx> Index<$id> for Thir<'tcx> {
80                type Output = $value;
81                fn index(&self, index: $id) -> &Self::Output {
82                    &self.$name[index]
83                }
84            }
85        )*
86    }
87}
88
89thir_with_elements! {
90    arms: ArmId => Arm<'tcx> => "a{}",
91    blocks: BlockId => Block => "b{}",
92    exprs: ExprId => Expr<'tcx> => "e{}",
93    stmts: StmtId => Stmt<'tcx> => "s{}",
94    params: ParamId => Param<'tcx> => "p{}",
95}
96
97#[derive(Debug, HashStable, Clone)]
98pub enum BodyTy<'tcx> {
99    Const(Ty<'tcx>),
100    Fn(FnSig<'tcx>),
101    GlobalAsm(Ty<'tcx>),
102}
103
104/// Description of a type-checked function parameter.
105#[derive(Clone, Debug, HashStable)]
106pub struct Param<'tcx> {
107    /// The pattern that appears in the parameter list, or None for implicit parameters.
108    pub pat: Option<Box<Pat<'tcx>>>,
109    /// The possibly inferred type.
110    pub ty: Ty<'tcx>,
111    /// Span of the explicitly provided type, or None if inferred for closures.
112    pub ty_span: Option<Span>,
113    /// Whether this param is `self`, and how it is bound.
114    pub self_kind: Option<hir::ImplicitSelfKind>,
115    /// HirId for lints.
116    pub hir_id: Option<HirId>,
117}
118
119#[derive(Copy, Clone, Debug, HashStable)]
120pub enum LintLevel {
121    Inherited,
122    Explicit(HirId),
123}
124
125#[derive(Clone, Debug, HashStable)]
126pub struct Block {
127    /// Whether the block itself has a label. Used by `label: {}`
128    /// and `try` blocks.
129    ///
130    /// This does *not* include labels on loops, e.g. `'label: loop {}`.
131    pub targeted_by_break: bool,
132    pub region_scope: region::Scope,
133    /// The span of the block, including the opening braces,
134    /// the label, and the `unsafe` keyword, if present.
135    pub span: Span,
136    /// The statements in the blocK.
137    pub stmts: Box<[StmtId]>,
138    /// The trailing expression of the block, if any.
139    pub expr: Option<ExprId>,
140    pub safety_mode: BlockSafety,
141}
142
143type UserTy<'tcx> = Option<Box<CanonicalUserType<'tcx>>>;
144
145#[derive(Clone, Debug, HashStable)]
146pub struct AdtExpr<'tcx> {
147    /// The ADT we're constructing.
148    pub adt_def: AdtDef<'tcx>,
149    /// The variant of the ADT.
150    pub variant_index: VariantIdx,
151    pub args: GenericArgsRef<'tcx>,
152
153    /// Optional user-given args: for something like `let x =
154    /// Bar::<T> { ... }`.
155    pub user_ty: UserTy<'tcx>,
156
157    pub fields: Box<[FieldExpr]>,
158    /// The base, e.g. `Foo {x: 1, ..base}`.
159    pub base: AdtExprBase<'tcx>,
160}
161
162#[derive(Clone, Debug, HashStable)]
163pub enum AdtExprBase<'tcx> {
164    /// A struct expression where all the fields are explicitly enumerated: `Foo { a, b }`.
165    None,
166    /// A struct expression with a "base", an expression of the same type as the outer struct that
167    /// will be used to populate any fields not explicitly mentioned: `Foo { ..base }`
168    Base(FruInfo<'tcx>),
169    /// A struct expression with a `..` tail but no "base" expression. The values from the struct
170    /// fields' default values will be used to populate any fields not explicitly mentioned:
171    /// `Foo { .. }`.
172    DefaultFields(Box<[Ty<'tcx>]>),
173}
174
175#[derive(Clone, Debug, HashStable)]
176pub struct ClosureExpr<'tcx> {
177    pub closure_id: LocalDefId,
178    pub args: UpvarArgs<'tcx>,
179    pub upvars: Box<[ExprId]>,
180    pub movability: Option<hir::Movability>,
181    pub fake_reads: Vec<(ExprId, FakeReadCause, HirId)>,
182}
183
184#[derive(Clone, Debug, HashStable)]
185pub struct InlineAsmExpr<'tcx> {
186    pub asm_macro: AsmMacro,
187    pub template: &'tcx [InlineAsmTemplatePiece],
188    pub operands: Box<[InlineAsmOperand<'tcx>]>,
189    pub options: InlineAsmOptions,
190    pub line_spans: &'tcx [Span],
191}
192
193#[derive(Copy, Clone, Debug, HashStable)]
194pub enum BlockSafety {
195    Safe,
196    /// A compiler-generated unsafe block
197    BuiltinUnsafe,
198    /// An `unsafe` block. The `HirId` is the ID of the block.
199    ExplicitUnsafe(HirId),
200}
201
202#[derive(Clone, Debug, HashStable)]
203pub struct Stmt<'tcx> {
204    pub kind: StmtKind<'tcx>,
205}
206
207#[derive(Clone, Debug, HashStable)]
208pub enum StmtKind<'tcx> {
209    /// An expression with a trailing semicolon.
210    Expr {
211        /// The scope for this statement; may be used as lifetime of temporaries.
212        scope: region::Scope,
213
214        /// The expression being evaluated in this statement.
215        expr: ExprId,
216    },
217
218    /// A `let` binding.
219    Let {
220        /// The scope for variables bound in this `let`; it covers this and
221        /// all the remaining statements in the block.
222        remainder_scope: region::Scope,
223
224        /// The scope for the initialization itself; might be used as
225        /// lifetime of temporaries.
226        init_scope: region::Scope,
227
228        /// `let <PAT> = ...`
229        ///
230        /// If a type annotation is included, it is added as an ascription pattern.
231        pattern: Box<Pat<'tcx>>,
232
233        /// `let pat: ty = <INIT>`
234        initializer: Option<ExprId>,
235
236        /// `let pat: ty = <INIT> else { <ELSE> }`
237        else_block: Option<BlockId>,
238
239        /// The lint level for this `let` statement.
240        lint_level: LintLevel,
241
242        /// Span of the `let <PAT> = <INIT>` part.
243        span: Span,
244    },
245}
246
247#[derive(Clone, Debug, Copy, PartialEq, Eq, Hash, HashStable, TyEncodable, TyDecodable)]
248pub struct LocalVarId(pub HirId);
249
250/// A THIR expression.
251#[derive(Clone, Debug, HashStable)]
252pub struct Expr<'tcx> {
253    /// kind of expression
254    pub kind: ExprKind<'tcx>,
255
256    /// The type of this expression
257    pub ty: Ty<'tcx>,
258
259    /// The lifetime of this expression if it should be spilled into a
260    /// temporary
261    pub temp_lifetime: TempLifetime,
262
263    /// span of the expression in the source
264    pub span: Span,
265}
266
267/// Temporary lifetime information for THIR expressions
268#[derive(Clone, Copy, Debug, HashStable)]
269pub struct TempLifetime {
270    /// Lifetime for temporaries as expected.
271    /// This should be `None` in a constant context.
272    pub temp_lifetime: Option<region::Scope>,
273    /// If `Some(lt)`, indicates that the lifetime of this temporary will change to `lt` in a future edition.
274    /// If `None`, then no changes are expected, or lints are disabled.
275    pub backwards_incompatible: Option<region::Scope>,
276}
277
278#[derive(Clone, Debug, HashStable)]
279pub enum ExprKind<'tcx> {
280    /// `Scope`s are used to explicitly mark destruction scopes,
281    /// and to track the `HirId` of the expressions within the scope.
282    Scope {
283        region_scope: region::Scope,
284        lint_level: LintLevel,
285        value: ExprId,
286    },
287    /// A `box <value>` expression.
288    Box {
289        value: ExprId,
290    },
291    /// An `if` expression.
292    If {
293        if_then_scope: region::Scope,
294        cond: ExprId,
295        /// `then` is always `ExprKind::Block`.
296        then: ExprId,
297        /// If present, the `else_opt` expr is always `ExprKind::Block` (for
298        /// `else`) or `ExprKind::If` (for `else if`).
299        else_opt: Option<ExprId>,
300    },
301    /// A function call. Method calls and overloaded operators are converted to plain function calls.
302    Call {
303        /// The type of the function. This is often a [`FnDef`] or a [`FnPtr`].
304        ///
305        /// [`FnDef`]: ty::TyKind::FnDef
306        /// [`FnPtr`]: ty::TyKind::FnPtr
307        ty: Ty<'tcx>,
308        /// The function itself.
309        fun: ExprId,
310        /// The arguments passed to the function.
311        ///
312        /// Note: in some cases (like calling a closure), the function call `f(...args)` gets
313        /// rewritten as a call to a function trait method (e.g. `FnOnce::call_once(f, (...args))`).
314        args: Box<[ExprId]>,
315        /// Whether this is from an overloaded operator rather than a
316        /// function call from HIR. `true` for overloaded function call.
317        from_hir_call: bool,
318        /// The span of the function, without the dot and receiver
319        /// (e.g. `foo(a, b)` in `x.foo(a, b)`).
320        fn_span: Span,
321    },
322    /// A use expression `x.use`.
323    ByUse {
324        /// The expression on which use is applied.
325        expr: ExprId,
326        /// The span of use, without the dot and receiver
327        /// (e.g. `use` in `x.use`).
328        span: Span,
329    },
330    /// A *non-overloaded* dereference.
331    Deref {
332        arg: ExprId,
333    },
334    /// A *non-overloaded* binary operation.
335    Binary {
336        op: BinOp,
337        lhs: ExprId,
338        rhs: ExprId,
339    },
340    /// A logical operation. This is distinct from `BinaryOp` because
341    /// the operands need to be lazily evaluated.
342    LogicalOp {
343        op: LogicalOp,
344        lhs: ExprId,
345        rhs: ExprId,
346    },
347    /// A *non-overloaded* unary operation. Note that here the deref (`*`)
348    /// operator is represented by `ExprKind::Deref`.
349    Unary {
350        op: UnOp,
351        arg: ExprId,
352    },
353    /// A cast: `<source> as <type>`. The type we cast to is the type of
354    /// the parent expression.
355    Cast {
356        source: ExprId,
357    },
358    /// Forces its contents to be treated as a value expression, not a place
359    /// expression. This is inserted in some places where an operation would
360    /// otherwise be erased completely (e.g. some no-op casts), but we still
361    /// need to ensure that its operand is treated as a value and not a place.
362    Use {
363        source: ExprId,
364    },
365    /// A coercion from `!` to any type.
366    NeverToAny {
367        source: ExprId,
368    },
369    /// A pointer coercion. More information can be found in [`PointerCoercion`].
370    /// Pointer casts that cannot be done by coercions are represented by [`ExprKind::Cast`].
371    PointerCoercion {
372        cast: PointerCoercion,
373        source: ExprId,
374        /// Whether this coercion is written with an `as` cast in the source code.
375        is_from_as_cast: bool,
376    },
377    /// A `loop` expression.
378    Loop {
379        body: ExprId,
380    },
381    /// A `#[loop_match] loop { state = 'blk: { match state { ... } } }` expression.
382    LoopMatch {
383        /// The state variable that is updated.
384        /// The `match_data.scrutinee` is the same variable, but with a different span.
385        state: ExprId,
386        region_scope: region::Scope,
387        match_data: Box<LoopMatchMatchData>,
388    },
389    /// Special expression representing the `let` part of an `if let` or similar construct
390    /// (including `if let` guards in match arms, and let-chains formed by `&&`).
391    ///
392    /// This isn't considered a real expression in surface Rust syntax, so it can
393    /// only appear in specific situations, such as within the condition of an `if`.
394    ///
395    /// (Not to be confused with [`StmtKind::Let`], which is a normal `let` statement.)
396    Let {
397        expr: ExprId,
398        pat: Box<Pat<'tcx>>,
399    },
400    /// A `match` expression.
401    Match {
402        scrutinee: ExprId,
403        arms: Box<[ArmId]>,
404        match_source: MatchSource,
405    },
406    /// A block.
407    Block {
408        block: BlockId,
409    },
410    /// An assignment: `lhs = rhs`.
411    Assign {
412        lhs: ExprId,
413        rhs: ExprId,
414    },
415    /// A *non-overloaded* operation assignment, e.g. `lhs += rhs`.
416    AssignOp {
417        op: AssignOp,
418        lhs: ExprId,
419        rhs: ExprId,
420    },
421    /// Access to a field of a struct, a tuple, an union, or an enum.
422    Field {
423        lhs: ExprId,
424        /// Variant containing the field.
425        variant_index: VariantIdx,
426        /// This can be a named (`.foo`) or unnamed (`.0`) field.
427        name: FieldIdx,
428    },
429    /// A *non-overloaded* indexing operation.
430    Index {
431        lhs: ExprId,
432        index: ExprId,
433    },
434    /// A local variable.
435    VarRef {
436        id: LocalVarId,
437    },
438    /// Used to represent upvars mentioned in a closure/coroutine
439    UpvarRef {
440        /// DefId of the closure/coroutine
441        closure_def_id: DefId,
442
443        /// HirId of the root variable
444        var_hir_id: LocalVarId,
445    },
446    /// A borrow, e.g. `&arg`.
447    Borrow {
448        borrow_kind: BorrowKind,
449        arg: ExprId,
450    },
451    /// A `&raw [const|mut] $place_expr` raw borrow resulting in type `*[const|mut] T`.
452    RawBorrow {
453        mutability: hir::Mutability,
454        arg: ExprId,
455    },
456    /// A `break` expression.
457    Break {
458        label: region::Scope,
459        value: Option<ExprId>,
460    },
461    /// A `continue` expression.
462    Continue {
463        label: region::Scope,
464    },
465    /// A `#[const_continue] break` expression.
466    ConstContinue {
467        label: region::Scope,
468        value: ExprId,
469    },
470    /// A `return` expression.
471    Return {
472        value: Option<ExprId>,
473    },
474    /// A `become` expression.
475    Become {
476        value: ExprId,
477    },
478    /// An inline `const` block, e.g. `const {}`.
479    ConstBlock {
480        did: DefId,
481        args: GenericArgsRef<'tcx>,
482    },
483    /// An array literal constructed from one repeated element, e.g. `[1; 5]`.
484    Repeat {
485        value: ExprId,
486        count: ty::Const<'tcx>,
487    },
488    /// An array, e.g. `[a, b, c, d]`.
489    Array {
490        fields: Box<[ExprId]>,
491    },
492    /// A tuple, e.g. `(a, b, c, d)`.
493    Tuple {
494        fields: Box<[ExprId]>,
495    },
496    /// An ADT constructor, e.g. `Foo {x: 1, y: 2}`.
497    Adt(Box<AdtExpr<'tcx>>),
498    /// A type ascription on a place.
499    PlaceTypeAscription {
500        source: ExprId,
501        /// Type that the user gave to this expression
502        user_ty: UserTy<'tcx>,
503        user_ty_span: Span,
504    },
505    /// A type ascription on a value, e.g. `type_ascribe!(42, i32)` or `42 as i32`.
506    ValueTypeAscription {
507        source: ExprId,
508        /// Type that the user gave to this expression
509        user_ty: UserTy<'tcx>,
510        user_ty_span: Span,
511    },
512    /// An unsafe binder cast on a place, e.g. `unwrap_binder!(*ptr)`.
513    PlaceUnwrapUnsafeBinder {
514        source: ExprId,
515    },
516    /// An unsafe binder cast on a value, e.g. `unwrap_binder!(rvalue())`,
517    /// which makes a temporary.
518    ValueUnwrapUnsafeBinder {
519        source: ExprId,
520    },
521    /// Construct an unsafe binder, e.g. `wrap_binder(&ref)`.
522    WrapUnsafeBinder {
523        source: ExprId,
524    },
525    /// A closure definition.
526    Closure(Box<ClosureExpr<'tcx>>),
527    /// A literal.
528    Literal {
529        lit: hir::Lit,
530        neg: bool,
531    },
532    /// For literals that don't correspond to anything in the HIR
533    NonHirLiteral {
534        lit: ty::ScalarInt,
535        user_ty: UserTy<'tcx>,
536    },
537    /// A literal of a ZST type.
538    ZstLiteral {
539        user_ty: UserTy<'tcx>,
540    },
541    /// Associated constants and named constants
542    NamedConst {
543        def_id: DefId,
544        args: GenericArgsRef<'tcx>,
545        user_ty: UserTy<'tcx>,
546    },
547    ConstParam {
548        param: ty::ParamConst,
549        def_id: DefId,
550    },
551    // FIXME improve docs for `StaticRef` by distinguishing it from `NamedConst`
552    /// A literal containing the address of a `static`.
553    ///
554    /// This is only distinguished from `Literal` so that we can register some
555    /// info for diagnostics.
556    StaticRef {
557        alloc_id: AllocId,
558        ty: Ty<'tcx>,
559        def_id: DefId,
560    },
561    /// Inline assembly, i.e. `asm!()`.
562    InlineAsm(Box<InlineAsmExpr<'tcx>>),
563    /// Field offset (`offset_of!`)
564    OffsetOf {
565        container: Ty<'tcx>,
566        fields: &'tcx List<(VariantIdx, FieldIdx)>,
567    },
568    /// An expression taking a reference to a thread local.
569    ThreadLocalRef(DefId),
570    /// A `yield` expression.
571    Yield {
572        value: ExprId,
573    },
574}
575
576/// Represents the association of a field identifier and an expression.
577///
578/// This is used in struct constructors.
579#[derive(Clone, Debug, HashStable)]
580pub struct FieldExpr {
581    pub name: FieldIdx,
582    pub expr: ExprId,
583}
584
585#[derive(Clone, Debug, HashStable)]
586pub struct FruInfo<'tcx> {
587    pub base: ExprId,
588    pub field_types: Box<[Ty<'tcx>]>,
589}
590
591/// A `match` arm.
592#[derive(Clone, Debug, HashStable)]
593pub struct Arm<'tcx> {
594    pub pattern: Box<Pat<'tcx>>,
595    pub guard: Option<ExprId>,
596    pub body: ExprId,
597    pub lint_level: LintLevel,
598    pub scope: region::Scope,
599    pub span: Span,
600}
601
602/// The `match` part of a `#[loop_match]`
603#[derive(Clone, Debug, HashStable)]
604pub struct LoopMatchMatchData {
605    pub scrutinee: ExprId,
606    pub arms: Box<[ArmId]>,
607    pub span: Span,
608}
609
610#[derive(Copy, Clone, Debug, HashStable)]
611pub enum LogicalOp {
612    /// The `&&` operator.
613    And,
614    /// The `||` operator.
615    Or,
616}
617
618#[derive(Clone, Debug, HashStable)]
619pub enum InlineAsmOperand<'tcx> {
620    In {
621        reg: InlineAsmRegOrRegClass,
622        expr: ExprId,
623    },
624    Out {
625        reg: InlineAsmRegOrRegClass,
626        late: bool,
627        expr: Option<ExprId>,
628    },
629    InOut {
630        reg: InlineAsmRegOrRegClass,
631        late: bool,
632        expr: ExprId,
633    },
634    SplitInOut {
635        reg: InlineAsmRegOrRegClass,
636        late: bool,
637        in_expr: ExprId,
638        out_expr: Option<ExprId>,
639    },
640    Const {
641        value: mir::Const<'tcx>,
642        span: Span,
643    },
644    SymFn {
645        value: ExprId,
646    },
647    SymStatic {
648        def_id: DefId,
649    },
650    Label {
651        block: BlockId,
652    },
653}
654
655#[derive(Clone, Debug, HashStable, TypeVisitable)]
656pub struct FieldPat<'tcx> {
657    pub field: FieldIdx,
658    pub pattern: Pat<'tcx>,
659}
660
661#[derive(Clone, Debug, HashStable, TypeVisitable)]
662pub struct Pat<'tcx> {
663    pub ty: Ty<'tcx>,
664    pub span: Span,
665    pub kind: PatKind<'tcx>,
666}
667
668impl<'tcx> Pat<'tcx> {
669    pub fn simple_ident(&self) -> Option<Symbol> {
670        match self.kind {
671            PatKind::Binding {
672                name, mode: BindingMode(ByRef::No, _), subpattern: None, ..
673            } => Some(name),
674            _ => None,
675        }
676    }
677
678    /// Call `f` on every "binding" in a pattern, e.g., on `a` in
679    /// `match foo() { Some(a) => (), None => () }`
680    pub fn each_binding(&self, mut f: impl FnMut(Symbol, ByRef, Ty<'tcx>, Span)) {
681        self.walk_always(|p| {
682            if let PatKind::Binding { name, mode, ty, .. } = p.kind {
683                f(name, mode.0, ty, p.span);
684            }
685        });
686    }
687
688    /// Walk the pattern in left-to-right order.
689    ///
690    /// If `it(pat)` returns `false`, the children are not visited.
691    pub fn walk(&self, mut it: impl FnMut(&Pat<'tcx>) -> bool) {
692        self.walk_(&mut it)
693    }
694
695    fn walk_(&self, it: &mut impl FnMut(&Pat<'tcx>) -> bool) {
696        if !it(self) {
697            return;
698        }
699
700        for_each_immediate_subpat(self, |p| p.walk_(it));
701    }
702
703    /// Whether the pattern has a `PatKind::Error` nested within.
704    pub fn pat_error_reported(&self) -> Result<(), ErrorGuaranteed> {
705        let mut error = None;
706        self.walk(|pat| {
707            if let PatKind::Error(e) = pat.kind
708                && error.is_none()
709            {
710                error = Some(e);
711            }
712            error.is_none()
713        });
714        match error {
715            None => Ok(()),
716            Some(e) => Err(e),
717        }
718    }
719
720    /// Walk the pattern in left-to-right order.
721    ///
722    /// If you always want to recurse, prefer this method over `walk`.
723    pub fn walk_always(&self, mut it: impl FnMut(&Pat<'tcx>)) {
724        self.walk(|p| {
725            it(p);
726            true
727        })
728    }
729
730    /// Whether this a never pattern.
731    pub fn is_never_pattern(&self) -> bool {
732        let mut is_never_pattern = false;
733        self.walk(|pat| match &pat.kind {
734            PatKind::Never => {
735                is_never_pattern = true;
736                false
737            }
738            PatKind::Or { pats } => {
739                is_never_pattern = pats.iter().all(|p| p.is_never_pattern());
740                false
741            }
742            _ => true,
743        });
744        is_never_pattern
745    }
746}
747
748#[derive(Clone, Debug, HashStable, TypeVisitable)]
749pub struct Ascription<'tcx> {
750    pub annotation: CanonicalUserTypeAnnotation<'tcx>,
751    /// Variance to use when relating the `user_ty` to the **type of the value being
752    /// matched**. Typically, this is `Variance::Covariant`, since the value being matched must
753    /// have a type that is some subtype of the ascribed type.
754    ///
755    /// Note that this variance does not apply for any bindings within subpatterns. The type
756    /// assigned to those bindings must be exactly equal to the `user_ty` given here.
757    ///
758    /// The only place where this field is not `Covariant` is when matching constants, where
759    /// we currently use `Contravariant` -- this is because the constant type just needs to
760    /// be "comparable" to the type of the input value. So, for example:
761    ///
762    /// ```text
763    /// match x { "foo" => .. }
764    /// ```
765    ///
766    /// requires that `&'static str <: T_x`, where `T_x` is the type of `x`. Really, we should
767    /// probably be checking for a `PartialEq` impl instead, but this preserves the behavior
768    /// of the old type-check for now. See #57280 for details.
769    pub variance: ty::Variance,
770}
771
772#[derive(Clone, Debug, HashStable, TypeVisitable)]
773pub enum PatKind<'tcx> {
774    /// A missing pattern, e.g. for an anonymous param in a bare fn like `fn f(u32)`.
775    Missing,
776
777    /// A wildcard pattern: `_`.
778    Wild,
779
780    AscribeUserType {
781        ascription: Ascription<'tcx>,
782        subpattern: Box<Pat<'tcx>>,
783    },
784
785    /// `x`, `ref x`, `x @ P`, etc.
786    Binding {
787        name: Symbol,
788        #[type_visitable(ignore)]
789        mode: BindingMode,
790        #[type_visitable(ignore)]
791        var: LocalVarId,
792        ty: Ty<'tcx>,
793        subpattern: Option<Box<Pat<'tcx>>>,
794
795        /// Is this the leftmost occurrence of the binding, i.e., is `var` the
796        /// `HirId` of this pattern?
797        ///
798        /// (The same binding can occur multiple times in different branches of
799        /// an or-pattern, but only one of them will be primary.)
800        is_primary: bool,
801    },
802
803    /// `Foo(...)` or `Foo{...}` or `Foo`, where `Foo` is a variant name from an ADT with
804    /// multiple variants.
805    Variant {
806        adt_def: AdtDef<'tcx>,
807        args: GenericArgsRef<'tcx>,
808        variant_index: VariantIdx,
809        subpatterns: Vec<FieldPat<'tcx>>,
810    },
811
812    /// `(...)`, `Foo(...)`, `Foo{...}`, or `Foo`, where `Foo` is a variant name from an ADT with
813    /// a single variant.
814    Leaf {
815        subpatterns: Vec<FieldPat<'tcx>>,
816    },
817
818    /// `box P`, `&P`, `&mut P`, etc.
819    Deref {
820        subpattern: Box<Pat<'tcx>>,
821    },
822
823    /// Deref pattern, written `box P` for now.
824    DerefPattern {
825        subpattern: Box<Pat<'tcx>>,
826        /// Whether the pattern scrutinee needs to be borrowed in order to call `Deref::deref` or
827        /// `DerefMut::deref_mut`, and if so, which. This is `ByRef::No` for deref patterns on
828        /// boxes; they are lowered using a built-in deref rather than a method call, thus they
829        /// don't borrow the scrutinee.
830        #[type_visitable(ignore)]
831        borrow: ByRef,
832    },
833
834    /// One of the following:
835    /// * `&str` (represented as a valtree), which will be handled as a string pattern and thus
836    ///   exhaustiveness checking will detect if you use the same string twice in different
837    ///   patterns.
838    /// * integer, bool, char or float (represented as a valtree), which will be handled by
839    ///   exhaustiveness to cover exactly its own value, similar to `&str`, but these values are
840    ///   much simpler.
841    /// * `String`, if `string_deref_patterns` is enabled.
842    Constant {
843        value: mir::Const<'tcx>,
844    },
845
846    /// Pattern obtained by converting a constant (inline or named) to its pattern
847    /// representation using `const_to_pat`. This is used for unsafety checking.
848    ExpandedConstant {
849        /// [DefId] of the constant item.
850        def_id: DefId,
851        /// The pattern that the constant lowered to.
852        ///
853        /// HACK: we need to keep the `DefId` of inline constants around for unsafety checking;
854        /// therefore when a range pattern contains inline constants, we re-wrap the range pattern
855        /// with the `ExpandedConstant` nodes that correspond to the range endpoints. Hence
856        /// `subpattern` may actually be a range pattern, and `def_id` be the constant for one of
857        /// its endpoints.
858        subpattern: Box<Pat<'tcx>>,
859    },
860
861    Range(Arc<PatRange<'tcx>>),
862
863    /// Matches against a slice, checking the length and extracting elements.
864    /// irrefutable when there is a slice pattern and both `prefix` and `suffix` are empty.
865    /// e.g., `&[ref xs @ ..]`.
866    Slice {
867        prefix: Box<[Pat<'tcx>]>,
868        slice: Option<Box<Pat<'tcx>>>,
869        suffix: Box<[Pat<'tcx>]>,
870    },
871
872    /// Fixed match against an array; irrefutable.
873    Array {
874        prefix: Box<[Pat<'tcx>]>,
875        slice: Option<Box<Pat<'tcx>>>,
876        suffix: Box<[Pat<'tcx>]>,
877    },
878
879    /// An or-pattern, e.g. `p | q`.
880    /// Invariant: `pats.len() >= 2`.
881    Or {
882        pats: Box<[Pat<'tcx>]>,
883    },
884
885    /// A never pattern `!`.
886    Never,
887
888    /// An error has been encountered during lowering. We probably shouldn't report more lints
889    /// related to this pattern.
890    Error(ErrorGuaranteed),
891}
892
893/// A range pattern.
894/// The boundaries must be of the same type and that type must be numeric.
895#[derive(Clone, Debug, PartialEq, HashStable, TypeVisitable)]
896pub struct PatRange<'tcx> {
897    /// Must not be `PosInfinity`.
898    pub lo: PatRangeBoundary<'tcx>,
899    /// Must not be `NegInfinity`.
900    pub hi: PatRangeBoundary<'tcx>,
901    #[type_visitable(ignore)]
902    pub end: RangeEnd,
903    pub ty: Ty<'tcx>,
904}
905
906impl<'tcx> PatRange<'tcx> {
907    /// Whether this range covers the full extent of possible values (best-effort, we ignore floats).
908    #[inline]
909    pub fn is_full_range(&self, tcx: TyCtxt<'tcx>) -> Option<bool> {
910        let (min, max, size, bias) = match *self.ty.kind() {
911            ty::Char => (0, std::char::MAX as u128, Size::from_bits(32), 0),
912            ty::Int(ity) => {
913                let size = Integer::from_int_ty(&tcx, ity).size();
914                let max = size.truncate(u128::MAX);
915                let bias = 1u128 << (size.bits() - 1);
916                (0, max, size, bias)
917            }
918            ty::Uint(uty) => {
919                let size = Integer::from_uint_ty(&tcx, uty).size();
920                let max = size.unsigned_int_max();
921                (0, max, size, 0)
922            }
923            _ => return None,
924        };
925
926        // We want to compare ranges numerically, but the order of the bitwise representation of
927        // signed integers does not match their numeric order. Thus, to correct the ordering, we
928        // need to shift the range of signed integers to correct the comparison. This is achieved by
929        // XORing with a bias (see pattern/deconstruct_pat.rs for another pertinent example of this
930        // pattern).
931        //
932        // Also, for performance, it's important to only do the second `try_to_bits` if necessary.
933        let lo_is_min = match self.lo {
934            PatRangeBoundary::NegInfinity => true,
935            PatRangeBoundary::Finite(value) => {
936                let lo = value.try_to_bits(size).unwrap() ^ bias;
937                lo <= min
938            }
939            PatRangeBoundary::PosInfinity => false,
940        };
941        if lo_is_min {
942            let hi_is_max = match self.hi {
943                PatRangeBoundary::NegInfinity => false,
944                PatRangeBoundary::Finite(value) => {
945                    let hi = value.try_to_bits(size).unwrap() ^ bias;
946                    hi > max || hi == max && self.end == RangeEnd::Included
947                }
948                PatRangeBoundary::PosInfinity => true,
949            };
950            if hi_is_max {
951                return Some(true);
952            }
953        }
954        Some(false)
955    }
956
957    #[inline]
958    pub fn contains(
959        &self,
960        value: mir::Const<'tcx>,
961        tcx: TyCtxt<'tcx>,
962        typing_env: ty::TypingEnv<'tcx>,
963    ) -> Option<bool> {
964        use Ordering::*;
965        debug_assert_eq!(self.ty, value.ty());
966        let ty = self.ty;
967        let value = PatRangeBoundary::Finite(value);
968        // For performance, it's important to only do the second comparison if necessary.
969        Some(
970            match self.lo.compare_with(value, ty, tcx, typing_env)? {
971                Less | Equal => true,
972                Greater => false,
973            } && match value.compare_with(self.hi, ty, tcx, typing_env)? {
974                Less => true,
975                Equal => self.end == RangeEnd::Included,
976                Greater => false,
977            },
978        )
979    }
980
981    #[inline]
982    pub fn overlaps(
983        &self,
984        other: &Self,
985        tcx: TyCtxt<'tcx>,
986        typing_env: ty::TypingEnv<'tcx>,
987    ) -> Option<bool> {
988        use Ordering::*;
989        debug_assert_eq!(self.ty, other.ty);
990        // For performance, it's important to only do the second comparison if necessary.
991        Some(
992            match other.lo.compare_with(self.hi, self.ty, tcx, typing_env)? {
993                Less => true,
994                Equal => self.end == RangeEnd::Included,
995                Greater => false,
996            } && match self.lo.compare_with(other.hi, self.ty, tcx, typing_env)? {
997                Less => true,
998                Equal => other.end == RangeEnd::Included,
999                Greater => false,
1000            },
1001        )
1002    }
1003}
1004
1005impl<'tcx> fmt::Display for PatRange<'tcx> {
1006    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1007        if let PatRangeBoundary::Finite(value) = &self.lo {
1008            write!(f, "{value}")?;
1009        }
1010        if let PatRangeBoundary::Finite(value) = &self.hi {
1011            write!(f, "{}", self.end)?;
1012            write!(f, "{value}")?;
1013        } else {
1014            // `0..` is parsed as an inclusive range, we must display it correctly.
1015            write!(f, "..")?;
1016        }
1017        Ok(())
1018    }
1019}
1020
1021/// A (possibly open) boundary of a range pattern.
1022/// If present, the const must be of a numeric type.
1023#[derive(Copy, Clone, Debug, PartialEq, HashStable, TypeVisitable)]
1024pub enum PatRangeBoundary<'tcx> {
1025    Finite(mir::Const<'tcx>),
1026    NegInfinity,
1027    PosInfinity,
1028}
1029
1030impl<'tcx> PatRangeBoundary<'tcx> {
1031    #[inline]
1032    pub fn is_finite(self) -> bool {
1033        matches!(self, Self::Finite(..))
1034    }
1035    #[inline]
1036    pub fn as_finite(self) -> Option<mir::Const<'tcx>> {
1037        match self {
1038            Self::Finite(value) => Some(value),
1039            Self::NegInfinity | Self::PosInfinity => None,
1040        }
1041    }
1042    pub fn eval_bits(
1043        self,
1044        ty: Ty<'tcx>,
1045        tcx: TyCtxt<'tcx>,
1046        typing_env: ty::TypingEnv<'tcx>,
1047    ) -> u128 {
1048        match self {
1049            Self::Finite(value) => value.eval_bits(tcx, typing_env),
1050            Self::NegInfinity => {
1051                // Unwrap is ok because the type is known to be numeric.
1052                ty.numeric_min_and_max_as_bits(tcx).unwrap().0
1053            }
1054            Self::PosInfinity => {
1055                // Unwrap is ok because the type is known to be numeric.
1056                ty.numeric_min_and_max_as_bits(tcx).unwrap().1
1057            }
1058        }
1059    }
1060
1061    #[instrument(skip(tcx, typing_env), level = "debug", ret)]
1062    pub fn compare_with(
1063        self,
1064        other: Self,
1065        ty: Ty<'tcx>,
1066        tcx: TyCtxt<'tcx>,
1067        typing_env: ty::TypingEnv<'tcx>,
1068    ) -> Option<Ordering> {
1069        use PatRangeBoundary::*;
1070        match (self, other) {
1071            // When comparing with infinities, we must remember that `0u8..` and `0u8..=255`
1072            // describe the same range. These two shortcuts are ok, but for the rest we must check
1073            // bit values.
1074            (PosInfinity, PosInfinity) => return Some(Ordering::Equal),
1075            (NegInfinity, NegInfinity) => return Some(Ordering::Equal),
1076
1077            // This code is hot when compiling matches with many ranges. So we
1078            // special-case extraction of evaluated scalars for speed, for types where
1079            // we can do scalar comparisons. E.g. `unicode-normalization` has
1080            // many ranges such as '\u{037A}'..='\u{037F}', and chars can be compared
1081            // in this way.
1082            (Finite(a), Finite(b)) if matches!(ty.kind(), ty::Int(_) | ty::Uint(_) | ty::Char) => {
1083                if let (Some(a), Some(b)) = (a.try_to_scalar_int(), b.try_to_scalar_int()) {
1084                    let sz = ty.primitive_size(tcx);
1085                    let cmp = match ty.kind() {
1086                        ty::Uint(_) | ty::Char => a.to_uint(sz).cmp(&b.to_uint(sz)),
1087                        ty::Int(_) => a.to_int(sz).cmp(&b.to_int(sz)),
1088                        _ => unreachable!(),
1089                    };
1090                    return Some(cmp);
1091                }
1092            }
1093            _ => {}
1094        }
1095
1096        let a = self.eval_bits(ty, tcx, typing_env);
1097        let b = other.eval_bits(ty, tcx, typing_env);
1098
1099        match ty.kind() {
1100            ty::Float(ty::FloatTy::F16) => {
1101                use rustc_apfloat::Float;
1102                let a = rustc_apfloat::ieee::Half::from_bits(a);
1103                let b = rustc_apfloat::ieee::Half::from_bits(b);
1104                a.partial_cmp(&b)
1105            }
1106            ty::Float(ty::FloatTy::F32) => {
1107                use rustc_apfloat::Float;
1108                let a = rustc_apfloat::ieee::Single::from_bits(a);
1109                let b = rustc_apfloat::ieee::Single::from_bits(b);
1110                a.partial_cmp(&b)
1111            }
1112            ty::Float(ty::FloatTy::F64) => {
1113                use rustc_apfloat::Float;
1114                let a = rustc_apfloat::ieee::Double::from_bits(a);
1115                let b = rustc_apfloat::ieee::Double::from_bits(b);
1116                a.partial_cmp(&b)
1117            }
1118            ty::Float(ty::FloatTy::F128) => {
1119                use rustc_apfloat::Float;
1120                let a = rustc_apfloat::ieee::Quad::from_bits(a);
1121                let b = rustc_apfloat::ieee::Quad::from_bits(b);
1122                a.partial_cmp(&b)
1123            }
1124            ty::Int(ity) => {
1125                let size = rustc_abi::Integer::from_int_ty(&tcx, *ity).size();
1126                let a = size.sign_extend(a) as i128;
1127                let b = size.sign_extend(b) as i128;
1128                Some(a.cmp(&b))
1129            }
1130            ty::Uint(_) | ty::Char => Some(a.cmp(&b)),
1131            _ => bug!(),
1132        }
1133    }
1134}
1135
1136// Some nodes are used a lot. Make sure they don't unintentionally get bigger.
1137#[cfg(target_pointer_width = "64")]
1138mod size_asserts {
1139    use rustc_data_structures::static_assert_size;
1140
1141    use super::*;
1142    // tidy-alphabetical-start
1143    static_assert_size!(Block, 48);
1144    static_assert_size!(Expr<'_>, 72);
1145    static_assert_size!(ExprKind<'_>, 40);
1146    static_assert_size!(Pat<'_>, 64);
1147    static_assert_size!(PatKind<'_>, 48);
1148    static_assert_size!(Stmt<'_>, 48);
1149    static_assert_size!(StmtKind<'_>, 48);
1150    // tidy-alphabetical-end
1151}