<commit_before>//! This module contains `TyKind` and its major components.

#![allow(rustc::usage_of_ty_tykind)]

use self::InferTy::*;
use self::TyKind::*;

use crate::infer::canonical::Canonical;
use crate::middle::region;
use crate::mir::interpret::ConstValue;
use crate::mir::interpret::Scalar;
use crate::mir::Promoted;
use crate::ty::layout::VariantIdx;
use crate::ty::subst::{GenericArgKind, InternalSubsts, Subst, SubstsRef};
use crate::ty::{
    self, AdtDef, DefIdTree, Discr, Ty, TyCtxt, TypeFlags, TypeFoldable, WithConstness,
};
use crate::ty::{List, ParamEnv, ParamEnvAnd, TyS};
use polonius_engine::Atom;
use rustc_ast::ast::{self, Ident};
use rustc_data_structures::captures::Captures;
use rustc_hir as hir;
use rustc_hir::def_id::DefId;
use rustc_index::vec::Idx;
use rustc_macros::HashStable;
use rustc_span::symbol::{kw, Symbol};
use rustc_target::spec::abi;
use smallvec::SmallVec;
use std::borrow::Cow;
use std::cmp::Ordering;
use std::marker::PhantomData;
use std::ops::Range;

#[derive(
    Clone,
    Copy,
    PartialEq,
    Eq,
    PartialOrd,
    Ord,
    Hash,
    Debug,
    RustcEncodable,
    RustcDecodable,
    HashStable,
    TypeFoldable,
    Lift
)]
pub struct TypeAndMut<'tcx> {
    pub ty: Ty<'tcx>,
    pub mutbl: hir::Mutability,
}

#[derive(
    Clone,
    PartialEq,
    PartialOrd,
    Eq,
    Ord,
    Hash,
    RustcEncodable,
    RustcDecodable,
    Copy,
    HashStable
)]
/// A "free" region `fr` can be interpreted as "some region
/// at least as big as the scope `fr.scope`".
pub struct FreeRegion {
    pub scope: DefId,
    pub bound_region: BoundRegion,
}

#[derive(
    Clone,
    PartialEq,
    PartialOrd,
    Eq,
    Ord,
    Hash,
    RustcEncodable,
    RustcDecodable,
    Copy,
    HashStable
)]
pub enum BoundRegion {
    /// An anonymous region parameter for a given fn (&T)
    BrAnon(u32),

    /// Named region parameters for functions (a in &'a T)
    ///
    /// The `DefId` is needed to distinguish free regions in
    /// the event of shadowing.
    BrNamed(DefId, Symbol),

    /// Anonymous region for the implicit env pointer parameter
    /// to a closure
    BrEnv,
}

impl BoundRegion {
    pub fn is_named(&self) -> bool {
        match *self {
            BoundRegion::BrNamed(_, name) => name != kw::UnderscoreLifetime,
            _ => false,
        }
    }

    /// When canonicalizing, we replace unbound inference variables and free
    /// regions with anonymous late bound regions. This method asserts that
    /// we have an anonymous late bound region, which hence may refer to
    /// a canonical variable.
    pub fn assert_bound_var(&self) -> BoundVar {
        match *self {
            BoundRegion::BrAnon(var) => BoundVar::from_u32(var),
            _ => bug!("bound region is not anonymous"),
        }
    }
}

/// N.B., if you change this, you'll probably want to change the corresponding
/// AST structure in `librustc_ast/ast.rs` as well.
#[derive(
    Clone,
    PartialEq,
    Eq,
    PartialOrd,
    Ord,
    Hash,
    RustcEncodable,
    RustcDecodable,
    HashStable,
    Debug
)]
#[rustc_diagnostic_item = "TyKind"]
pub enum TyKind<'tcx> {
    /// The primitive boolean type. Written as `bool`.
    Bool,

    /// The primitive character type; holds a Unicode scalar value
    /// (a non-surrogate code point). Written as `char`.
    Char,

    /// A primitive signed integer type. For example, `i32`.
    Int(ast::IntTy),

    /// A primitive unsigned integer type. For example, `u32`.
    Uint(ast::UintTy),

    /// A primitive floating-point type. For example, `f64`.
    Float(ast::FloatTy),

    /// Structures, enumerations and unions.
    ///
    /// InternalSubsts here, possibly against intuition, *may* contain `Param`s.
    /// That is, even after substitution it is possible that there are type
    /// variables. This happens when the `Adt` corresponds to an ADT
    /// definition and not a concrete use of it.
    Adt(&'tcx AdtDef, SubstsRef<'tcx>),

    /// An unsized FFI type that is opaque to Rust. Written as `extern type T`.
    Foreign(DefId),

    /// The pointee of a string slice. Written as `str`.
    Str,

    /// An array with the given length. Written as `[T; n]`.
    Array(Ty<'tcx>, &'tcx ty::Const<'tcx>),

    /// The pointee of an array slice. Written as `[T]`.
    Slice(Ty<'tcx>),

    /// A raw pointer. Written as `*mut T` or `*const T`
    RawPtr(TypeAndMut<'tcx>),

    /// A reference; a pointer with an associated lifetime. Written as
    /// `&'a mut T` or `&'a T`.
    Ref(Region<'tcx>, Ty<'tcx>, hir::Mutability),

    /// The anonymous type of a function declaration/definition. Each
    /// function has a unique type, which is output (for a function
    /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`.
    ///
    /// For example the type of `bar` here:
    ///
    /// ```rust
    /// fn foo() -> i32 { 1 }
    /// let bar = foo; // bar: fn() -> i32 {foo}
    /// ```
    FnDef(DefId, SubstsRef<'tcx>),

    /// A pointer to a function. Written as `fn() -> i32`.
    ///
    /// For example the type of `bar` here:
    ///
    /// ```rust
    /// fn foo() -> i32 { 1 }
    /// let bar: fn() -> i32 = foo;
    /// ```
    FnPtr(PolyFnSig<'tcx>),

    /// A trait, defined with `trait`.
    Dynamic(Binder<&'tcx List<ExistentialPredicate<'tcx>>>, ty::Region<'tcx>),

    /// The anonymous type of a closure. Used to represent the type of
    /// `|a| a`.
    Closure(DefId, SubstsRef<'tcx>),

    /// The anonymous type of a generator. Used to represent the type of
    /// `|a| yield a`.
    Generator(DefId, SubstsRef<'tcx>, hir::Movability),

    /// A type representin the types stored inside a generator.
    /// This should only appear in GeneratorInteriors.
    GeneratorWitness(Binder<&'tcx List<Ty<'tcx>>>),

    /// The never type `!`
    Never,

    /// A tuple type. For example, `(i32, bool)`.
    /// Use `TyS::tuple_fields` to iterate over the field types.
    Tuple(SubstsRef<'tcx>),

    /// The projection of an associated type. For example,
    /// `<T as Trait<..>>::N`.
    Projection(ProjectionTy<'tcx>),

    /// A placeholder type used when we do not have enough information
    /// to normalize the projection of an associated type to an
    /// existing concrete type. Currently only used with chalk-engine.
    UnnormalizedProjection(ProjectionTy<'tcx>),

    /// Opaque (`impl Trait`) type found in a return type.
    /// The `DefId` comes either from
    /// * the `impl Trait` ast::Ty node,
    /// * or the `type Foo = impl Trait` declaration
    /// The substitutions are for the generics of the function in question.
    /// After typeck, the concrete type can be found in the `types` map.
    Opaque(DefId, SubstsRef<'tcx>),

    /// A type parameter; for example, `T` in `fn f<T>(x: T) {}
    Param(ParamTy),

    /// Bound type variable, used only when preparing a trait query.
    Bound(ty::DebruijnIndex, BoundTy),

    /// A placeholder type - universally quantified higher-ranked type.
    Placeholder(ty::PlaceholderType),

    /// A type variable used during type checking.
    Infer(InferTy),

    /// A placeholder for a type which could not be computed; this is
    /// propagated to avoid useless error messages.
    Error,
}

// `TyKind` is used a lot. Make sure it doesn't unintentionally get bigger.
#[cfg(target_arch = "x86_64")]
static_assert_size!(TyKind<'_>, 24);

/// A closure can be modeled as a struct that looks like:
///
///     struct Closure<'l0...'li, T0...Tj, CK, CS, U>(...U);
///
/// where:
///
/// - 'l0...'li and T0...Tj are the generic parameters
///   in scope on the function that defined the closure,
/// - CK represents the *closure kind* (Fn vs FnMut vs FnOnce). This
///   is rather hackily encoded via a scalar type. See
///   `TyS::to_opt_closure_kind` for details.
/// - CS represents the *closure signature*, representing as a `fn()`
///   type. For example, `fn(u32, u32) -> u32` would mean that the closure
///   implements `CK<(u32, u32), Output = u32>`, where `CK` is the trait
///   specified above.
/// - U is a type parameter representing the types of its upvars, tupled up
///   (borrowed, if appropriate; that is, if an U field represents a by-ref upvar,
///    and the up-var has the type `Foo`, then that field of U will be `&Foo`).
///
/// So, for example, given this function:
///
///     fn foo<'a, T>(data: &'a mut T) {
///          do(|| data.count += 1)
///     }
///
/// the type of the closure would be something like:
///
///     struct Closure<'a, T, U>(...U);
///
/// Note that the type of the upvar is not specified in the struct.
/// You may wonder how the impl would then be able to use the upvar,
/// if it doesn't know it's type? The answer is that the impl is
/// (conceptually) not fully generic over Closure but rather tied to
/// instances with the expected upvar types:
///
///     impl<'b, 'a, T> FnMut() for Closure<'a, T, (&'b mut &'a mut T,)> {
///         ...
///     }
///
/// You can see that the *impl* fully specified the type of the upvar
/// and thus knows full well that `data` has type `&'b mut &'a mut T`.
/// (Here, I am assuming that `data` is mut-borrowed.)
///
/// Now, the last question you may ask is: Why include the upvar types
/// in an extra type parameter? The reason for this design is that the
/// upvar types can reference lifetimes that are internal to the
/// creating function. In my example above, for example, the lifetime
/// `'b` represents the scope of the closure itself; this is some
/// subset of `foo`, probably just the scope of the call to the to
/// `do()`. If we just had the lifetime/type parameters from the
/// enclosing function, we couldn't name this lifetime `'b`. Note that
/// there can also be lifetimes in the types of the upvars themselves,
/// if one of them happens to be a reference to something that the
/// creating fn owns.
///
/// OK, you say, so why not create a more minimal set of parameters
/// that just includes the extra lifetime parameters? The answer is
/// primarily that it would be hard --- we don't know at the time when
/// we create the closure type what the full types of the upvars are,
/// nor do we know which are borrowed and which are not. In this
/// design, we can just supply a fresh type parameter and figure that
/// out later.
///
/// All right, you say, but why include the type parameters from the
/// original function then? The answer is that codegen may need them
/// when monomorphizing, and they may not appear in the upvars. A
/// closure could capture no variables but still make use of some
/// in-scope type parameter with a bound (e.g., if our example above
/// had an extra `U: Default`, and the closure called `U::default()`).
///
/// There is another reason. This design (implicitly) prohibits
/// closures from capturing themselves (except via a trait
/// object). This simplifies closure inference considerably, since it
/// means that when we infer the kind of a closure or its upvars, we
/// don't have to handle cycles where the decisions we make for
/// closure C wind up influencing the decisions we ought to make for
/// closure C (which would then require fixed point iteration to
/// handle). Plus it fixes an ICE. :P
///
/// ## Generators
///
/// Generators are handled similarly in `GeneratorSubsts`.  The set of
/// type parameters is similar, but `CK` and `CS` are replaced by the
/// following type parameters:
///
/// * `GS`: The generator's "resume type", which is the type of the
///   argument passed to `resume`, and the type of `yield` expressions
///   inside the generator.
/// * `GY`: The "yield type", which is the type of values passed to
///   `yield` inside the generator.
/// * `GR`: The "return type", which is the type of value returned upon
///   completion of the generator.
/// * `GW`: The "generator witness".
#[derive(Copy, Clone, Debug, TypeFoldable)]
pub struct ClosureSubsts<'tcx> {
    /// Lifetime and type parameters from the enclosing function,
    /// concatenated with a tuple containing the types of the upvars.
    ///
    /// These are separated out because codegen wants to pass them around
    /// when monomorphizing.
    pub substs: SubstsRef<'tcx>,
}

/// Struct returned by `split()`. Note that these are subslices of the
/// parent slice and not canonical substs themselves.
struct SplitClosureSubsts<'tcx> {
    // FIXME(eddyb) maybe replace these with `GenericArg` to avoid having
    // `GenericArg::expect_ty` called on all of them when only one is used.
    closure_kind_ty: Ty<'tcx>,
    closure_sig_as_fn_ptr_ty: Ty<'tcx>,
    tupled_upvars_ty: Ty<'tcx>,
}

impl<'tcx> ClosureSubsts<'tcx> {
    /// Divides the closure substs into their respective
    /// components. Single source of truth with respect to the
    /// ordering.
    fn split(self) -> SplitClosureSubsts<'tcx> {
        let parent_len = self.substs.len() - 3;
        SplitClosureSubsts {
            closure_kind_ty: self.substs.type_at(parent_len),
            closure_sig_as_fn_ptr_ty: self.substs.type_at(parent_len + 1),
            tupled_upvars_ty: self.substs.type_at(parent_len + 2),
        }
    }

    /// Returns `true` only if enough of the synthetic types are known to
    /// allow using all of the methods on `ClosureSubsts` without panicking.
    ///
    /// Used primarily by `ty::print::pretty` to be able to handle closure
    /// types that haven't had their synthetic types substituted in.
    pub fn is_valid(self) -> bool {
        self.substs.len() >= 3 && matches!(self.split().tupled_upvars_ty.kind, Tuple(_))
    }

    #[inline]
    pub fn upvar_tys(self) -> impl Iterator<Item = Ty<'tcx>> + 'tcx {
        let upvars = match self.split().tupled_upvars_ty.kind {
            Tuple(upvars) => upvars,
            _ => bug!("upvars should be tupled"),
        };
        upvars.iter().map(|t| {
            if let GenericArgKind::Type(ty) = t.unpack() {
                ty
            } else {
                bug!("upvar should be type")
            }
        })
    }

    /// Returns the closure kind for this closure; may return a type
    /// variable during inference. To get the closure kind during
    /// inference, use `infcx.closure_kind(substs)`.
    pub fn kind_ty(self) -> Ty<'tcx> {
        self.split().closure_kind_ty
    }

    /// Returns the `fn` pointer type representing the closure signature for this
    /// closure.
    // FIXME(eddyb) this should be unnecessary, as the shallowly resolved
    // type is known at the time of the creation of `ClosureSubsts`,
    // see `rustc_typeck::check::closure`.
    pub fn sig_as_fn_ptr_ty(self) -> Ty<'tcx> {
        self.split().closure_sig_as_fn_ptr_ty
    }

    /// Returns the closure kind for this closure; only usable outside
    /// of an inference context, because in that context we know that
    /// there are no type variables.
    ///
    /// If you have an inference context, use `infcx.closure_kind()`.
    pub fn kind(self) -> ty::ClosureKind {
        self.split().closure_kind_ty.to_opt_closure_kind().unwrap()
    }

    /// Extracts the signature from the closure.
    pub fn sig(self) -> ty::PolyFnSig<'tcx> {
        let ty = self.sig_as_fn_ptr_ty();
        match ty.kind {
            ty::FnPtr(sig) => sig,
            _ => bug!("closure_sig_as_fn_ptr_ty is not a fn-ptr: {:?}", ty.kind),
        }
    }
}

/// Similar to `ClosureSubsts`; see the above documentation for more.
#[derive(Copy, Clone, Debug, TypeFoldable)]
pub struct GeneratorSubsts<'tcx> {
    pub substs: SubstsRef<'tcx>,
}

struct SplitGeneratorSubsts<'tcx> {
    // FIXME(eddyb) maybe replace these with `GenericArg` to avoid having
    // `GenericArg::expect_ty` called on all of them when only one is used.
    resume_ty: Ty<'tcx>,
    yield_ty: Ty<'tcx>,
    return_ty: Ty<'tcx>,
    witness: Ty<'tcx>,
    tupled_upvars_ty: Ty<'tcx>,
}

impl<'tcx> GeneratorSubsts<'tcx> {
    fn split(self) -> SplitGeneratorSubsts<'tcx> {
        let parent_len = self.substs.len() - 5;
        SplitGeneratorSubsts {
            resume_ty: self.substs.type_at(parent_len),
            yield_ty: self.substs.type_at(parent_len + 1),
            return_ty: self.substs.type_at(parent_len + 2),
            witness: self.substs.type_at(parent_len + 3),
            tupled_upvars_ty: self.substs.type_at(parent_len + 4),
        }
    }

    /// Returns `true` only if enough of the synthetic types are known to
    /// allow using all of the methods on `GeneratorSubsts` without panicking.
    ///
    /// Used primarily by `ty::print::pretty` to be able to handle generator
    /// types that haven't had their synthetic types substituted in.
    pub fn is_valid(self) -> bool {
        self.substs.len() >= 5 && matches!(self.split().tupled_upvars_ty.kind, Tuple(_))
    }

    /// This describes the types that can be contained in a generator.
    /// It will be a type variable initially and unified in the last stages of typeck of a body.
    /// It contains a tuple of all the types that could end up on a generator frame.
    /// The state transformation MIR pass may only produce layouts which mention types
    /// in this tuple. Upvars are not counted here.
    pub fn witness(self) -> Ty<'tcx> {
        self.split().witness
    }

    #[inline]
    pub fn upvar_tys(self) -> impl Iterator<Item = Ty<'tcx>> + 'tcx {
        let upvars = match self.split().tupled_upvars_ty.kind {
            Tuple(upvars) => upvars,
            _ => bug!("upvars should be tupled"),
        };
        upvars.iter().map(|t| {
            if let GenericArgKind::Type(ty) = t.unpack() {
                ty
            } else {
                bug!("upvar should be type")
            }
        })
    }

    /// Returns the type representing the resume type of the generator.
    pub fn resume_ty(self) -> Ty<'tcx> {
        self.split().resume_ty
    }

    /// Returns the type representing the yield type of the generator.
    pub fn yield_ty(self) -> Ty<'tcx> {
        self.split().yield_ty
    }

    /// Returns the type representing the return type of the generator.
    pub fn return_ty(self) -> Ty<'tcx> {
        self.split().return_ty
    }

    /// Returns the "generator signature", which consists of its yield
    /// and return types.
    ///
    /// N.B., some bits of the code prefers to see this wrapped in a
    /// binder, but it never contains bound regions. Probably this
    /// function should be removed.
    pub fn poly_sig(self) -> PolyGenSig<'tcx> {
        ty::Binder::dummy(self.sig())
    }

    /// Returns the "generator signature", which consists of its resume, yield
    /// and return types.
    pub fn sig(self) -> GenSig<'tcx> {
        ty::GenSig {
            resume_ty: self.resume_ty(),
            yield_ty: self.yield_ty(),
            return_ty: self.return_ty(),
        }
    }
}

impl<'tcx> GeneratorSubsts<'tcx> {
    /// Generator has not been resumed yet.
    pub const UNRESUMED: usize = 0;
    /// Generator has returned or is completed.
    pub const RETURNED: usize = 1;
    /// Generator has been poisoned.
    pub const POISONED: usize = 2;

    const UNRESUMED_NAME: &'static str = "Unresumed";
    const RETURNED_NAME: &'static str = "Returned";
    const POISONED_NAME: &'static str = "Panicked";

    /// The valid variant indices of this generator.
    #[inline]
    pub fn variant_range(&self, def_id: DefId, tcx: TyCtxt<'tcx>) -> Range<VariantIdx> {
        // FIXME requires optimized MIR
        let num_variants = tcx.generator_layout(def_id).variant_fields.len();
        VariantIdx::new(0)..VariantIdx::new(num_variants)
    }

    /// The discriminant for the given variant. Panics if the `variant_index` is
    /// out of range.
    #[inline]
    pub fn discriminant_for_variant(
        &self,
        def_id: DefId,
        tcx: TyCtxt<'tcx>,
        variant_index: VariantIdx,
    ) -> Discr<'tcx> {
        // Generators don't support explicit discriminant values, so they are
        // the same as the variant index.
        assert!(self.variant_range(def_id, tcx).contains(&variant_index));
        Discr { val: variant_index.as_usize() as u128, ty: self.discr_ty(tcx) }
    }

    /// The set of all discriminants for the generator, enumerated with their
    /// variant indices.
    #[inline]
    pub fn discriminants(
        self,
        def_id: DefId,
        tcx: TyCtxt<'tcx>,
    ) -> impl Iterator<Item = (VariantIdx, Discr<'tcx>)> + Captures<'tcx> {
        self.variant_range(def_id, tcx).map(move |index| {
            (index, Discr { val: index.as_usize() as u128, ty: self.discr_ty(tcx) })
        })
    }

    /// Calls `f` with a reference to the name of the enumerator for the given
    /// variant `v`.
    #[inline]
    pub fn variant_name(self, v: VariantIdx) -> Cow<'static, str> {
        match v.as_usize() {
            Self::UNRESUMED => Cow::from(Self::UNRESUMED_NAME),
            Self::RETURNED => Cow::from(Self::RETURNED_NAME),
            Self::POISONED => Cow::from(Self::POISONED_NAME),
            _ => Cow::from(format!("Suspend{}", v.as_usize() - 3)),
        }
    }

    /// The type of the state discriminant used in the generator type.
    #[inline]
    pub fn discr_ty(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
        tcx.types.u32
    }

    /// This returns the types of the MIR locals which had to be stored across suspension points.
    /// It is calculated in rustc_mir::transform::generator::StateTransform.
    /// All the types here must be in the tuple in GeneratorInterior.
    ///
    /// The locals are grouped by their variant number. Note that some locals may
    /// be repeated in multiple variants.
    #[inline]
    pub fn state_tys(
        self,
        def_id: DefId,
        tcx: TyCtxt<'tcx>,
    ) -> impl Iterator<Item = impl Iterator<Item = Ty<'tcx>> + Captures<'tcx>> {
        let layout = tcx.generator_layout(def_id);
        layout.variant_fields.iter().map(move |variant| {
            variant.iter().map(move |field| layout.field_tys[*field].subst(tcx, self.substs))
        })
    }

    /// This is the types of the fields of a generator which are not stored in a
    /// variant.
    #[inline]
    pub fn prefix_tys(self) -> impl Iterator<Item = Ty<'tcx>> {
        self.upvar_tys()
    }
}

#[derive(Debug, Copy, Clone)]
pub enum UpvarSubsts<'tcx> {
    Closure(SubstsRef<'tcx>),
    Generator(SubstsRef<'tcx>),
}

impl<'tcx> UpvarSubsts<'tcx> {
    #[inline]
    pub fn upvar_tys(self) -> impl Iterator<Item = Ty<'tcx>> + 'tcx {
        let tupled_upvars_ty = match self {
            UpvarSubsts::Closure(substs) => substs.as_closure().split().tupled_upvars_ty,
            UpvarSubsts::Generator(substs) => substs.as_generator().split().tupled_upvars_ty,
        };
        let upvars = match tupled_upvars_ty.kind {
            Tuple(upvars) => upvars,
            _ => bug!("upvars should be tupled"),
        };
        upvars.iter().map(|t| {
            if let GenericArgKind::Type(ty) = t.unpack() {
                ty
            } else {
                bug!("upvar should be type")
            }
        })
    }
}

#[derive(Debug, Copy, Clone, PartialEq, PartialOrd, Ord, Eq, Hash, RustcEncodable, RustcDecodable)]
#[derive(HashStable, TypeFoldable)]
pub enum ExistentialPredicate<'tcx> {
    /// E.g., `Iterator`.
    Trait(ExistentialTraitRef<'tcx>),
    /// E.g., `Iterator::Item = T`.
    Projection(ExistentialProjection<'tcx>),
    /// E.g., `Send`.
    AutoTrait(DefId),
}

impl<'tcx> ExistentialPredicate<'tcx> {
    /// Compares via an ordering that will not change if modules are reordered or other changes are
    /// made to the tree. In particular, this ordering is preserved across incremental compilations.
    pub fn stable_cmp(&self, tcx: TyCtxt<'tcx>, other: &Self) -> Ordering {
        use self::ExistentialPredicate::*;
        match (*self, *other) {
            (Trait(_), Trait(_)) => Ordering::Equal,<commit_msg>rustc: make {Closure,Generator}Substs::split as cheap as possible.<commit_after>//! This module contains `TyKind` and its major components.

#![allow(rustc::usage_of_ty_tykind)]

use self::InferTy::*;
use self::TyKind::*;

use crate::infer::canonical::Canonical;
use crate::middle::region;
use crate::mir::interpret::ConstValue;
use crate::mir::interpret::Scalar;
use crate::mir::Promoted;
use crate::ty::layout::VariantIdx;
use crate::ty::subst::{GenericArg, InternalSubsts, Subst, SubstsRef};
use crate::ty::{
    self, AdtDef, DefIdTree, Discr, Ty, TyCtxt, TypeFlags, TypeFoldable, WithConstness,
};
use crate::ty::{List, ParamEnv, ParamEnvAnd, TyS};
use polonius_engine::Atom;
use rustc_ast::ast::{self, Ident};
use rustc_data_structures::captures::Captures;
use rustc_hir as hir;
use rustc_hir::def_id::DefId;
use rustc_index::vec::Idx;
use rustc_macros::HashStable;
use rustc_span::symbol::{kw, Symbol};
use rustc_target::spec::abi;
use smallvec::SmallVec;
use std::borrow::Cow;
use std::cmp::Ordering;
use std::marker::PhantomData;
use std::ops::Range;

#[derive(
    Clone,
    Copy,
    PartialEq,
    Eq,
    PartialOrd,
    Ord,
    Hash,
    Debug,
    RustcEncodable,
    RustcDecodable,
    HashStable,
    TypeFoldable,
    Lift
)]
pub struct TypeAndMut<'tcx> {
    pub ty: Ty<'tcx>,
    pub mutbl: hir::Mutability,
}

#[derive(
    Clone,
    PartialEq,
    PartialOrd,
    Eq,
    Ord,
    Hash,
    RustcEncodable,
    RustcDecodable,
    Copy,
    HashStable
)]
/// A "free" region `fr` can be interpreted as "some region
/// at least as big as the scope `fr.scope`".
pub struct FreeRegion {
    pub scope: DefId,
    pub bound_region: BoundRegion,
}

#[derive(
    Clone,
    PartialEq,
    PartialOrd,
    Eq,
    Ord,
    Hash,
    RustcEncodable,
    RustcDecodable,
    Copy,
    HashStable
)]
pub enum BoundRegion {
    /// An anonymous region parameter for a given fn (&T)
    BrAnon(u32),

    /// Named region parameters for functions (a in &'a T)
    ///
    /// The `DefId` is needed to distinguish free regions in
    /// the event of shadowing.
    BrNamed(DefId, Symbol),

    /// Anonymous region for the implicit env pointer parameter
    /// to a closure
    BrEnv,
}

impl BoundRegion {
    pub fn is_named(&self) -> bool {
        match *self {
            BoundRegion::BrNamed(_, name) => name != kw::UnderscoreLifetime,
            _ => false,
        }
    }

    /// When canonicalizing, we replace unbound inference variables and free
    /// regions with anonymous late bound regions. This method asserts that
    /// we have an anonymous late bound region, which hence may refer to
    /// a canonical variable.
    pub fn assert_bound_var(&self) -> BoundVar {
        match *self {
            BoundRegion::BrAnon(var) => BoundVar::from_u32(var),
            _ => bug!("bound region is not anonymous"),
        }
    }
}

/// N.B., if you change this, you'll probably want to change the corresponding
/// AST structure in `librustc_ast/ast.rs` as well.
#[derive(
    Clone,
    PartialEq,
    Eq,
    PartialOrd,
    Ord,
    Hash,
    RustcEncodable,
    RustcDecodable,
    HashStable,
    Debug
)]
#[rustc_diagnostic_item = "TyKind"]
pub enum TyKind<'tcx> {
    /// The primitive boolean type. Written as `bool`.
    Bool,

    /// The primitive character type; holds a Unicode scalar value
    /// (a non-surrogate code point). Written as `char`.
    Char,

    /// A primitive signed integer type. For example, `i32`.
    Int(ast::IntTy),

    /// A primitive unsigned integer type. For example, `u32`.
    Uint(ast::UintTy),

    /// A primitive floating-point type. For example, `f64`.
    Float(ast::FloatTy),

    /// Structures, enumerations and unions.
    ///
    /// InternalSubsts here, possibly against intuition, *may* contain `Param`s.
    /// That is, even after substitution it is possible that there are type
    /// variables. This happens when the `Adt` corresponds to an ADT
    /// definition and not a concrete use of it.
    Adt(&'tcx AdtDef, SubstsRef<'tcx>),

    /// An unsized FFI type that is opaque to Rust. Written as `extern type T`.
    Foreign(DefId),

    /// The pointee of a string slice. Written as `str`.
    Str,

    /// An array with the given length. Written as `[T; n]`.
    Array(Ty<'tcx>, &'tcx ty::Const<'tcx>),

    /// The pointee of an array slice. Written as `[T]`.
    Slice(Ty<'tcx>),

    /// A raw pointer. Written as `*mut T` or `*const T`
    RawPtr(TypeAndMut<'tcx>),

    /// A reference; a pointer with an associated lifetime. Written as
    /// `&'a mut T` or `&'a T`.
    Ref(Region<'tcx>, Ty<'tcx>, hir::Mutability),

    /// The anonymous type of a function declaration/definition. Each
    /// function has a unique type, which is output (for a function
    /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`.
    ///
    /// For example the type of `bar` here:
    ///
    /// ```rust
    /// fn foo() -> i32 { 1 }
    /// let bar = foo; // bar: fn() -> i32 {foo}
    /// ```
    FnDef(DefId, SubstsRef<'tcx>),

    /// A pointer to a function. Written as `fn() -> i32`.
    ///
    /// For example the type of `bar` here:
    ///
    /// ```rust
    /// fn foo() -> i32 { 1 }
    /// let bar: fn() -> i32 = foo;
    /// ```
    FnPtr(PolyFnSig<'tcx>),

    /// A trait, defined with `trait`.
    Dynamic(Binder<&'tcx List<ExistentialPredicate<'tcx>>>, ty::Region<'tcx>),

    /// The anonymous type of a closure. Used to represent the type of
    /// `|a| a`.
    Closure(DefId, SubstsRef<'tcx>),

    /// The anonymous type of a generator. Used to represent the type of
    /// `|a| yield a`.
    Generator(DefId, SubstsRef<'tcx>, hir::Movability),

    /// A type representin the types stored inside a generator.
    /// This should only appear in GeneratorInteriors.
    GeneratorWitness(Binder<&'tcx List<Ty<'tcx>>>),

    /// The never type `!`
    Never,

    /// A tuple type. For example, `(i32, bool)`.
    /// Use `TyS::tuple_fields` to iterate over the field types.
    Tuple(SubstsRef<'tcx>),

    /// The projection of an associated type. For example,
    /// `<T as Trait<..>>::N`.
    Projection(ProjectionTy<'tcx>),

    /// A placeholder type used when we do not have enough information
    /// to normalize the projection of an associated type to an
    /// existing concrete type. Currently only used with chalk-engine.
    UnnormalizedProjection(ProjectionTy<'tcx>),

    /// Opaque (`impl Trait`) type found in a return type.
    /// The `DefId` comes either from
    /// * the `impl Trait` ast::Ty node,
    /// * or the `type Foo = impl Trait` declaration
    /// The substitutions are for the generics of the function in question.
    /// After typeck, the concrete type can be found in the `types` map.
    Opaque(DefId, SubstsRef<'tcx>),

    /// A type parameter; for example, `T` in `fn f<T>(x: T) {}
    Param(ParamTy),

    /// Bound type variable, used only when preparing a trait query.
    Bound(ty::DebruijnIndex, BoundTy),

    /// A placeholder type - universally quantified higher-ranked type.
    Placeholder(ty::PlaceholderType),

    /// A type variable used during type checking.
    Infer(InferTy),

    /// A placeholder for a type which could not be computed; this is
    /// propagated to avoid useless error messages.
    Error,
}

// `TyKind` is used a lot. Make sure it doesn't unintentionally get bigger.
#[cfg(target_arch = "x86_64")]
static_assert_size!(TyKind<'_>, 24);

/// A closure can be modeled as a struct that looks like:
///
///     struct Closure<'l0...'li, T0...Tj, CK, CS, U>(...U);
///
/// where:
///
/// - 'l0...'li and T0...Tj are the generic parameters
///   in scope on the function that defined the closure,
/// - CK represents the *closure kind* (Fn vs FnMut vs FnOnce). This
///   is rather hackily encoded via a scalar type. See
///   `TyS::to_opt_closure_kind` for details.
/// - CS represents the *closure signature*, representing as a `fn()`
///   type. For example, `fn(u32, u32) -> u32` would mean that the closure
///   implements `CK<(u32, u32), Output = u32>`, where `CK` is the trait
///   specified above.
/// - U is a type parameter representing the types of its upvars, tupled up
///   (borrowed, if appropriate; that is, if an U field represents a by-ref upvar,
///    and the up-var has the type `Foo`, then that field of U will be `&Foo`).
///
/// So, for example, given this function:
///
///     fn foo<'a, T>(data: &'a mut T) {
///          do(|| data.count += 1)
///     }
///
/// the type of the closure would be something like:
///
///     struct Closure<'a, T, U>(...U);
///
/// Note that the type of the upvar is not specified in the struct.
/// You may wonder how the impl would then be able to use the upvar,
/// if it doesn't know it's type? The answer is that the impl is
/// (conceptually) not fully generic over Closure but rather tied to
/// instances with the expected upvar types:
///
///     impl<'b, 'a, T> FnMut() for Closure<'a, T, (&'b mut &'a mut T,)> {
///         ...
///     }
///
/// You can see that the *impl* fully specified the type of the upvar
/// and thus knows full well that `data` has type `&'b mut &'a mut T`.
/// (Here, I am assuming that `data` is mut-borrowed.)
///
/// Now, the last question you may ask is: Why include the upvar types
/// in an extra type parameter? The reason for this design is that the
/// upvar types can reference lifetimes that are internal to the
/// creating function. In my example above, for example, the lifetime
/// `'b` represents the scope of the closure itself; this is some
/// subset of `foo`, probably just the scope of the call to the to
/// `do()`. If we just had the lifetime/type parameters from the
/// enclosing function, we couldn't name this lifetime `'b`. Note that
/// there can also be lifetimes in the types of the upvars themselves,
/// if one of them happens to be a reference to something that the
/// creating fn owns.
///
/// OK, you say, so why not create a more minimal set of parameters
/// that just includes the extra lifetime parameters? The answer is
/// primarily that it would be hard --- we don't know at the time when
/// we create the closure type what the full types of the upvars are,
/// nor do we know which are borrowed and which are not. In this
/// design, we can just supply a fresh type parameter and figure that
/// out later.
///
/// All right, you say, but why include the type parameters from the
/// original function then? The answer is that codegen may need them
/// when monomorphizing, and they may not appear in the upvars. A
/// closure could capture no variables but still make use of some
/// in-scope type parameter with a bound (e.g., if our example above
/// had an extra `U: Default`, and the closure called `U::default()`).
///
/// There is another reason. This design (implicitly) prohibits
/// closures from capturing themselves (except via a trait
/// object). This simplifies closure inference considerably, since it
/// means that when we infer the kind of a closure or its upvars, we
/// don't have to handle cycles where the decisions we make for
/// closure C wind up influencing the decisions we ought to make for
/// closure C (which would then require fixed point iteration to
/// handle). Plus it fixes an ICE. :P
///
/// ## Generators
///
/// Generators are handled similarly in `GeneratorSubsts`.  The set of
/// type parameters is similar, but `CK` and `CS` are replaced by the
/// following type parameters:
///
/// * `GS`: The generator's "resume type", which is the type of the
///   argument passed to `resume`, and the type of `yield` expressions
///   inside the generator.
/// * `GY`: The "yield type", which is the type of values passed to
///   `yield` inside the generator.
/// * `GR`: The "return type", which is the type of value returned upon
///   completion of the generator.
/// * `GW`: The "generator witness".
#[derive(Copy, Clone, Debug, TypeFoldable)]
pub struct ClosureSubsts<'tcx> {
    /// Lifetime and type parameters from the enclosing function,
    /// concatenated with a tuple containing the types of the upvars.
    ///
    /// These are separated out because codegen wants to pass them around
    /// when monomorphizing.
    pub substs: SubstsRef<'tcx>,
}

/// Struct returned by `split()`. Note that these are subslices of the
/// parent slice and not canonical substs themselves.
struct SplitClosureSubsts<'tcx> {
    closure_kind_ty: GenericArg<'tcx>,
    closure_sig_as_fn_ptr_ty: GenericArg<'tcx>,
    tupled_upvars_ty: GenericArg<'tcx>,
}

impl<'tcx> ClosureSubsts<'tcx> {
    /// Divides the closure substs into their respective
    /// components. Single source of truth with respect to the
    /// ordering.
    fn split(self) -> SplitClosureSubsts<'tcx> {
        match self.substs[..] {
            [.., closure_kind_ty, closure_sig_as_fn_ptr_ty, tupled_upvars_ty] => {
                SplitClosureSubsts { closure_kind_ty, closure_sig_as_fn_ptr_ty, tupled_upvars_ty }
            }
            _ => bug!("closure substs missing synthetics"),
        }
    }

    /// Returns `true` only if enough of the synthetic types are known to
    /// allow using all of the methods on `ClosureSubsts` without panicking.
    ///
    /// Used primarily by `ty::print::pretty` to be able to handle closure
    /// types that haven't had their synthetic types substituted in.
    pub fn is_valid(self) -> bool {
        self.substs.len() >= 3 && matches!(self.split().tupled_upvars_ty.expect_ty().kind, Tuple(_))
    }

    #[inline]
    pub fn upvar_tys(self) -> impl Iterator<Item = Ty<'tcx>> + 'tcx {
        self.split().tupled_upvars_ty.expect_ty().tuple_fields()
    }

    /// Returns the closure kind for this closure; may return a type
    /// variable during inference. To get the closure kind during
    /// inference, use `infcx.closure_kind(substs)`.
    pub fn kind_ty(self) -> Ty<'tcx> {
        self.split().closure_kind_ty.expect_ty()
    }

    /// Returns the `fn` pointer type representing the closure signature for this
    /// closure.
    // FIXME(eddyb) this should be unnecessary, as the shallowly resolved
    // type is known at the time of the creation of `ClosureSubsts`,
    // see `rustc_typeck::check::closure`.
    pub fn sig_as_fn_ptr_ty(self) -> Ty<'tcx> {
        self.split().closure_sig_as_fn_ptr_ty.expect_ty()
    }

    /// Returns the closure kind for this closure; only usable outside
    /// of an inference context, because in that context we know that
    /// there are no type variables.
    ///
    /// If you have an inference context, use `infcx.closure_kind()`.
    pub fn kind(self) -> ty::ClosureKind {
        self.kind_ty().to_opt_closure_kind().unwrap()
    }

    /// Extracts the signature from the closure.
    pub fn sig(self) -> ty::PolyFnSig<'tcx> {
        let ty = self.sig_as_fn_ptr_ty();
        match ty.kind {
            ty::FnPtr(sig) => sig,
            _ => bug!("closure_sig_as_fn_ptr_ty is not a fn-ptr: {:?}", ty.kind),
        }
    }
}

/// Similar to `ClosureSubsts`; see the above documentation for more.
#[derive(Copy, Clone, Debug, TypeFoldable)]
pub struct GeneratorSubsts<'tcx> {
    pub substs: SubstsRef<'tcx>,
}

struct SplitGeneratorSubsts<'tcx> {
    resume_ty: GenericArg<'tcx>,
    yield_ty: GenericArg<'tcx>,
    return_ty: GenericArg<'tcx>,
    witness: GenericArg<'tcx>,
    tupled_upvars_ty: GenericArg<'tcx>,
}

impl<'tcx> GeneratorSubsts<'tcx> {
    fn split(self) -> SplitGeneratorSubsts<'tcx> {
        match self.substs[..] {
            [.., resume_ty, yield_ty, return_ty, witness, tupled_upvars_ty] => {
                SplitGeneratorSubsts { resume_ty, yield_ty, return_ty, witness, tupled_upvars_ty }
            }
            _ => bug!("generator substs missing synthetics"),
        }
    }

    /// Returns `true` only if enough of the synthetic types are known to
    /// allow using all of the methods on `GeneratorSubsts` without panicking.
    ///
    /// Used primarily by `ty::print::pretty` to be able to handle generator
    /// types that haven't had their synthetic types substituted in.
    pub fn is_valid(self) -> bool {
        self.substs.len() >= 5 && matches!(self.split().tupled_upvars_ty.expect_ty().kind, Tuple(_))
    }

    /// This describes the types that can be contained in a generator.
    /// It will be a type variable initially and unified in the last stages of typeck of a body.
    /// It contains a tuple of all the types that could end up on a generator frame.
    /// The state transformation MIR pass may only produce layouts which mention types
    /// in this tuple. Upvars are not counted here.
    pub fn witness(self) -> Ty<'tcx> {
        self.split().witness.expect_ty()
    }

    #[inline]
    pub fn upvar_tys(self) -> impl Iterator<Item = Ty<'tcx>> + 'tcx {
        self.split().tupled_upvars_ty.expect_ty().tuple_fields()
    }

    /// Returns the type representing the resume type of the generator.
    pub fn resume_ty(self) -> Ty<'tcx> {
        self.split().resume_ty.expect_ty()
    }

    /// Returns the type representing the yield type of the generator.
    pub fn yield_ty(self) -> Ty<'tcx> {
        self.split().yield_ty.expect_ty()
    }

    /// Returns the type representing the return type of the generator.
    pub fn return_ty(self) -> Ty<'tcx> {
        self.split().return_ty.expect_ty()
    }

    /// Returns the "generator signature", which consists of its yield
    /// and return types.
    ///
    /// N.B., some bits of the code prefers to see this wrapped in a
    /// binder, but it never contains bound regions. Probably this
    /// function should be removed.
    pub fn poly_sig(self) -> PolyGenSig<'tcx> {
        ty::Binder::dummy(self.sig())
    }

    /// Returns the "generator signature", which consists of its resume, yield
    /// and return types.
    pub fn sig(self) -> GenSig<'tcx> {
        ty::GenSig {
            resume_ty: self.resume_ty(),
            yield_ty: self.yield_ty(),
            return_ty: self.return_ty(),
        }
    }
}

impl<'tcx> GeneratorSubsts<'tcx> {
    /// Generator has not been resumed yet.
    pub const UNRESUMED: usize = 0;
    /// Generator has returned or is completed.
    pub const RETURNED: usize = 1;
    /// Generator has been poisoned.
    pub const POISONED: usize = 2;

    const UNRESUMED_NAME: &'static str = "Unresumed";
    const RETURNED_NAME: &'static str = "Returned";
    const POISONED_NAME: &'static str = "Panicked";

    /// The valid variant indices of this generator.
    #[inline]
    pub fn variant_range(&self, def_id: DefId, tcx: TyCtxt<'tcx>) -> Range<VariantIdx> {
        // FIXME requires optimized MIR
        let num_variants = tcx.generator_layout(def_id).variant_fields.len();
        VariantIdx::new(0)..VariantIdx::new(num_variants)
    }

    /// The discriminant for the given variant. Panics if the `variant_index` is
    /// out of range.
    #[inline]
    pub fn discriminant_for_variant(
        &self,
        def_id: DefId,
        tcx: TyCtxt<'tcx>,
        variant_index: VariantIdx,
    ) -> Discr<'tcx> {
        // Generators don't support explicit discriminant values, so they are
        // the same as the variant index.
        assert!(self.variant_range(def_id, tcx).contains(&variant_index));
        Discr { val: variant_index.as_usize() as u128, ty: self.discr_ty(tcx) }
    }

    /// The set of all discriminants for the generator, enumerated with their
    /// variant indices.
    #[inline]
    pub fn discriminants(
        self,
        def_id: DefId,
        tcx: TyCtxt<'tcx>,
    ) -> impl Iterator<Item = (VariantIdx, Discr<'tcx>)> + Captures<'tcx> {
        self.variant_range(def_id, tcx).map(move |index| {
            (index, Discr { val: index.as_usize() as u128, ty: self.discr_ty(tcx) })
        })
    }

    /// Calls `f` with a reference to the name of the enumerator for the given
    /// variant `v`.
    #[inline]
    pub fn variant_name(self, v: VariantIdx) -> Cow<'static, str> {
        match v.as_usize() {
            Self::UNRESUMED => Cow::from(Self::UNRESUMED_NAME),
            Self::RETURNED => Cow::from(Self::RETURNED_NAME),
            Self::POISONED => Cow::from(Self::POISONED_NAME),
            _ => Cow::from(format!("Suspend{}", v.as_usize() - 3)),
        }
    }

    /// The type of the state discriminant used in the generator type.
    #[inline]
    pub fn discr_ty(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
        tcx.types.u32
    }

    /// This returns the types of the MIR locals which had to be stored across suspension points.
    /// It is calculated in rustc_mir::transform::generator::StateTransform.
    /// All the types here must be in the tuple in GeneratorInterior.
    ///
    /// The locals are grouped by their variant number. Note that some locals may
    /// be repeated in multiple variants.
    #[inline]
    pub fn state_tys(
        self,
        def_id: DefId,
        tcx: TyCtxt<'tcx>,
    ) -> impl Iterator<Item = impl Iterator<Item = Ty<'tcx>> + Captures<'tcx>> {
        let layout = tcx.generator_layout(def_id);
        layout.variant_fields.iter().map(move |variant| {
            variant.iter().map(move |field| layout.field_tys[*field].subst(tcx, self.substs))
        })
    }

    /// This is the types of the fields of a generator which are not stored in a
    /// variant.
    #[inline]
    pub fn prefix_tys(self) -> impl Iterator<Item = Ty<'tcx>> {
        self.upvar_tys()
    }
}

#[derive(Debug, Copy, Clone)]
pub enum UpvarSubsts<'tcx> {
    Closure(SubstsRef<'tcx>),
    Generator(SubstsRef<'tcx>),
}

impl<'tcx> UpvarSubsts<'tcx> {
    #[inline]
    pub fn upvar_tys(self) -> impl Iterator<Item = Ty<'tcx>> + 'tcx {
        let tupled_upvars_ty = match self {
            UpvarSubsts::Closure(substs) => substs.as_closure().split().tupled_upvars_ty,
            UpvarSubsts::Generator(substs) => substs.as_generator().split().tupled_upvars_ty,
        };
        tupled_upvars_ty.expect_ty().tuple_fields()
    }
}

#[derive(Debug, Copy, Clone, PartialEq, PartialOrd, Ord, Eq, Hash, RustcEncodable, RustcDecodable)]
#[derive(HashStable, TypeFoldable)]
pub enum ExistentialPredicate<'tcx> {
    /// E.g., `Iterator`.
    Trait(ExistentialTraitRef<'tcx>),
    /// E.g., `Iterator::Item = T`.
    Projection(ExistentialProjection<'tcx>),
    /// E.g., `Send`.
    AutoTrait(DefId),
}

impl<'tcx> ExistentialPredicate<'tcx> {
    /// Compares via an ordering that will not change if modules are reordered or other changes are
    /// made to the tree. In particular, this ordering is preserved across incremental compilations.
    pub fn stable_cmp(&self, tcx: TyCtxt<'tcx>, other: &Self) -> Ordering {
        use self::ExistentialPredicate::*;
        match (*self, *other) {
            (Trait(_), Trait(_)) => Ordering::Equal,
{'fraction_non_alphanumeric': 0.1322209608670508, 'fraction_numerical': 0.0029986934264356244, 'mean_word_length': 2.6091527520098947, 'pattern_counts': {'":': 0, '<': 205, '<?xml version=': 0, '>': 313, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4974473', 'n_tokens_mistral': 14590, 'n_tokens_neox': 14536, 'n_words': 5043}