src/librustc/hir/mod.rs

   1 //! HIR datatypes. See the [rustc guide] for more info.
   2 //!
   3 //! [rustc guide]: https://rust-lang.github.io/rustc-guide/hir.html
   4
   5 pub use self::BlockCheckMode::*;
   6 pub use self::FunctionRetTy::*;
   7 pub use self::PrimTy::*;
   8 pub use self::UnOp::*;
   9 pub use self::UnsafeSource::*;
  10
  11 use crate::hir::def::{Res, DefKind};
  12 use crate::hir::def_id::{DefId, DefIndex, LocalDefId, CRATE_DEF_INDEX};
  13 use crate::hir::ptr::P;
  14 use crate::mir::mono::Linkage;
  15 use crate::ty::AdtKind;
  16 use crate::ty::query::Providers;
  17 use crate::util::nodemap::{NodeMap, FxHashSet};
  18
  19 use errors::FatalError;
  20 use syntax_pos::{Span, DUMMY_SP, MultiSpan};
  21 use syntax::source_map::Spanned;
  22 use syntax::ast::{self, CrateSugar, Ident, Name, NodeId, AsmDialect};
  23 use syntax::ast::{Attribute, Label, LitKind, StrStyle, FloatTy, IntTy, UintTy};
  24 pub use syntax::ast::{Mutability, Constness, Unsafety, Movability, CaptureBy, IsAuto, ImplPolarity};
  25 use syntax::attr::{InlineAttr, OptimizeAttr};
  26 use syntax::symbol::{Symbol, kw};
  27 use syntax::tokenstream::TokenStream;
  28 use syntax::util::parser::ExprPrecedence;
  29 use rustc_target::spec::abi::Abi;
  30 use rustc_data_structures::sync::{par_for_each_in, Send, Sync};
  31 use rustc_data_structures::thin_vec::ThinVec;
  32 use rustc_macros::HashStable;
  33 use rustc_serialize::{self, Encoder, Encodable, Decoder, Decodable};
  34 use std::collections::{BTreeSet, BTreeMap};
  35 use std::fmt;
  36 use smallvec::SmallVec;
  37
  38 /// HIR doesn't commit to a concrete storage type and has its own alias for a vector.
  39 /// It can be `Vec`, `P<[T]>` or potentially `Box<[T]>`, or some other container with similar
  40 /// behavior. Unlike AST, HIR is mostly a static structure, so we can use an owned slice instead
  41 /// of `Vec` to avoid keeping extra capacity.
  42 pub type HirVec<T> = P<[T]>;
  43
  44 macro_rules! hir_vec {
  45     ($elem:expr; $n:expr) => (
  46         $crate::hir::HirVec::from(vec![$elem; $n])
  47     );
  48     ($($x:expr),*) => (
  49         $crate::hir::HirVec::from(vec![$($x),*])
  50     );
  51 }
  52
  53 pub mod check_attr;
  54 pub mod def;
  55 pub mod def_id;
  56 pub mod intravisit;
  57 pub mod itemlikevisit;
  58 pub mod lowering;
  59 pub mod map;
  60 pub mod pat_util;
  61 pub mod print;
  62 pub mod ptr;
  63 pub mod upvars;
  64
  65 /// Uniquely identifies a node in the HIR of the current crate. It is
  66 /// composed of the `owner`, which is the `DefIndex` of the directly enclosing
  67 /// `hir::Item`, `hir::TraitItem`, or `hir::ImplItem` (i.e., the closest "item-like"),
  68 /// and the `local_id` which is unique within the given owner.
  69 ///
  70 /// This two-level structure makes for more stable values: One can move an item
  71 /// around within the source code, or add or remove stuff before it, without
  72 /// the `local_id` part of the `HirId` changing, which is a very useful property in
  73 /// incremental compilation where we have to persist things through changes to
  74 /// the code base.
  75 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, PartialOrd, Ord)]
  76 pub struct HirId {
  77     pub owner: DefIndex,
  78     pub local_id: ItemLocalId,
  79 }
  80
  81 impl HirId {
  82     pub fn owner_def_id(self) -> DefId {
  83         DefId::local(self.owner)
  84     }
  85
  86     pub fn owner_local_def_id(self) -> LocalDefId {
  87         LocalDefId::from_def_id(DefId::local(self.owner))
  88     }
  89 }
  90
  91 impl rustc_serialize::UseSpecializedEncodable for HirId {
  92     fn default_encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
  93         let HirId {
  94             owner,
  95             local_id,
  96         } = *self;
  97
  98         owner.encode(s)?;
  99         local_id.encode(s)?;
 100         Ok(())
 101     }
 102 }
 103
 104 impl rustc_serialize::UseSpecializedDecodable for HirId {
 105     fn default_decode<D: Decoder>(d: &mut D) -> Result<HirId, D::Error> {
 106         let owner = DefIndex::decode(d)?;
 107         let local_id = ItemLocalId::decode(d)?;
 108
 109         Ok(HirId {
 110             owner,
 111             local_id
 112         })
 113     }
 114 }
 115
 116 impl fmt::Display for HirId {
 117     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 118         write!(f, "{:?}", self)
 119     }
 120 }
 121
 122 // Hack to ensure that we don't try to access the private parts of `ItemLocalId` in this module.
 123 mod item_local_id_inner {
 124     use rustc_index::vec::Idx;
 125     use rustc_macros::HashStable;
 126     rustc_index::newtype_index! {
 127         /// An `ItemLocalId` uniquely identifies something within a given "item-like";
 128         /// that is, within a `hir::Item`, `hir::TraitItem`, or `hir::ImplItem`. There is no
 129         /// guarantee that the numerical value of a given `ItemLocalId` corresponds to
 130         /// the node's position within the owning item in any way, but there is a
 131         /// guarantee that the `LocalItemId`s within an owner occupy a dense range of
 132         /// integers starting at zero, so a mapping that maps all or most nodes within
 133         /// an "item-like" to something else can be implemented by a `Vec` instead of a
 134         /// tree or hash map.
 135         pub struct ItemLocalId {
 136             derive [HashStable]
 137         }
 138     }
 139 }
 140
 141 pub use self::item_local_id_inner::ItemLocalId;
 142
 143 /// The `HirId` corresponding to `CRATE_NODE_ID` and `CRATE_DEF_INDEX`.
 144 pub const CRATE_HIR_ID: HirId = HirId {
 145     owner: CRATE_DEF_INDEX,
 146     local_id: ItemLocalId::from_u32_const(0)
 147 };
 148
 149 pub const DUMMY_HIR_ID: HirId = HirId {
 150     owner: CRATE_DEF_INDEX,
 151     local_id: DUMMY_ITEM_LOCAL_ID,
 152 };
 153
 154 pub const DUMMY_ITEM_LOCAL_ID: ItemLocalId = ItemLocalId::MAX;
 155
 156 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, HashStable)]
 157 pub struct Lifetime {
 158     pub hir_id: HirId,
 159     pub span: Span,
 160
 161     /// Either "`'a`", referring to a named lifetime definition,
 162     /// or "``" (i.e., `kw::Invalid`), for elision placeholders.
 163     ///
 164     /// HIR lowering inserts these placeholders in type paths that
 165     /// refer to type definitions needing lifetime parameters,
 166     /// `&T` and `&mut T`, and trait objects without `... + 'a`.
 167     pub name: LifetimeName,
 168 }
 169
 170 #[derive(Debug, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy, HashStable)]
 171 pub enum ParamName {
 172     /// Some user-given name like `T` or `'x`.
 173     Plain(Ident),
 174
 175     /// Synthetic name generated when user elided a lifetime in an impl header.
 176     ///
 177     /// E.g., the lifetimes in cases like these:
 178     ///
 179     ///     impl Foo for &u32
 180     ///     impl Foo<'_> for u32
 181     ///
 182     /// in that case, we rewrite to
 183     ///
 184     ///     impl<'f> Foo for &'f u32
 185     ///     impl<'f> Foo<'f> for u32
 186     ///
 187     /// where `'f` is something like `Fresh(0)`. The indices are
 188     /// unique per impl, but not necessarily continuous.
 189     Fresh(usize),
 190
 191     /// Indicates an illegal name was given and an error has been
 192     /// reported (so we should squelch other derived errors). Occurs
 193     /// when, e.g., `'_` is used in the wrong place.
 194     Error,
 195 }
 196
 197 impl ParamName {
 198     pub fn ident(&self) -> Ident {
 199         match *self {
 200             ParamName::Plain(ident) => ident,
 201             ParamName::Fresh(_) |
 202             ParamName::Error => Ident::with_dummy_span(kw::UnderscoreLifetime),
 203         }
 204     }
 205
 206     pub fn modern(&self) -> ParamName {
 207         match *self {
 208             ParamName::Plain(ident) => ParamName::Plain(ident.modern()),
 209             param_name => param_name,
 210         }
 211     }
 212 }
 213
 214 #[derive(Debug, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy, HashStable)]
 215 pub enum LifetimeName {
 216     /// User-given names or fresh (synthetic) names.
 217     Param(ParamName),
 218
 219     /// User wrote nothing (e.g., the lifetime in `&u32`).
 220     Implicit,
 221
 222     /// Implicit lifetime in a context like `dyn Foo`. This is
 223     /// distinguished from implicit lifetimes elsewhere because the
 224     /// lifetime that they default to must appear elsewhere within the
 225     /// enclosing type.  This means that, in an `impl Trait` context, we
 226     /// don't have to create a parameter for them. That is, `impl
 227     /// Trait<Item = &u32>` expands to an opaque type like `type
 228     /// Foo<'a> = impl Trait<Item = &'a u32>`, but `impl Trait<item =
 229     /// dyn Bar>` expands to `type Foo = impl Trait<Item = dyn Bar +
 230     /// 'static>`. The latter uses `ImplicitObjectLifetimeDefault` so
 231     /// that surrounding code knows not to create a lifetime
 232     /// parameter.
 233     ImplicitObjectLifetimeDefault,
 234
 235     /// Indicates an error during lowering (usually `'_` in wrong place)
 236     /// that was already reported.
 237     Error,
 238
 239     /// User wrote specifies `'_`.
 240     Underscore,
 241
 242     /// User wrote `'static`.
 243     Static,
 244 }
 245
 246 impl LifetimeName {
 247     pub fn ident(&self) -> Ident {
 248         match *self {
 249             LifetimeName::ImplicitObjectLifetimeDefault
 250                 | LifetimeName::Implicit
 251                 | LifetimeName::Error => Ident::invalid(),
 252             LifetimeName::Underscore => Ident::with_dummy_span(kw::UnderscoreLifetime),
 253             LifetimeName::Static => Ident::with_dummy_span(kw::StaticLifetime),
 254             LifetimeName::Param(param_name) => param_name.ident(),
 255         }
 256     }
 257
 258     pub fn is_elided(&self) -> bool {
 259         match self {
 260             LifetimeName::ImplicitObjectLifetimeDefault
 261             | LifetimeName::Implicit
 262             | LifetimeName::Underscore => true,
 263
 264             // It might seem surprising that `Fresh(_)` counts as
 265             // *not* elided -- but this is because, as far as the code
 266             // in the compiler is concerned -- `Fresh(_)` variants act
 267             // equivalently to "some fresh name". They correspond to
 268             // early-bound regions on an impl, in other words.
 269             LifetimeName::Error | LifetimeName::Param(_) | LifetimeName::Static => false,
 270         }
 271     }
 272
 273     fn is_static(&self) -> bool {
 274         self == &LifetimeName::Static
 275     }
 276
 277     pub fn modern(&self) -> LifetimeName {
 278         match *self {
 279             LifetimeName::Param(param_name) => LifetimeName::Param(param_name.modern()),
 280             lifetime_name => lifetime_name,
 281         }
 282     }
 283 }
 284
 285 impl fmt::Display for Lifetime {
 286     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 287         self.name.ident().fmt(f)
 288     }
 289 }
 290
 291 impl fmt::Debug for Lifetime {
 292     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 293         write!(f,
 294                "lifetime({}: {})",
 295                self.hir_id,
 296                print::to_string(print::NO_ANN, |s| s.print_lifetime(self)))
 297     }
 298 }
 299
 300 impl Lifetime {
 301     pub fn is_elided(&self) -> bool {
 302         self.name.is_elided()
 303     }
 304
 305     pub fn is_static(&self) -> bool {
 306         self.name.is_static()
 307     }
 308 }
 309
 310 /// A `Path` is essentially Rust's notion of a name; for instance,
 311 /// `std::cmp::PartialEq`. It's represented as a sequence of identifiers,
 312 /// along with a bunch of supporting information.
 313 #[derive(RustcEncodable, RustcDecodable, HashStable)]
 314 pub struct Path {
 315     pub span: Span,
 316     /// The resolution for the path.
 317     pub res: Res,
 318     /// The segments in the path: the things separated by `::`.
 319     pub segments: HirVec<PathSegment>,
 320 }
 321
 322 impl Path {
 323     pub fn is_global(&self) -> bool {
 324         !self.segments.is_empty() && self.segments[0].ident.name == kw::PathRoot
 325     }
 326 }
 327
 328 impl fmt::Debug for Path {
 329     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 330         write!(f, "path({})", self)
 331     }
 332 }
 333
 334 impl fmt::Display for Path {
 335     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 336         write!(f, "{}", print::to_string(print::NO_ANN, |s| s.print_path(self, false)))
 337     }
 338 }
 339
 340 /// A segment of a path: an identifier, an optional lifetime, and a set of
 341 /// types.
 342 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 343 pub struct PathSegment {
 344     /// The identifier portion of this path segment.
 345     #[stable_hasher(project(name))]
 346     pub ident: Ident,
 347     // `id` and `res` are optional. We currently only use these in save-analysis,
 348     // any path segments without these will not have save-analysis info and
 349     // therefore will not have 'jump to def' in IDEs, but otherwise will not be
 350     // affected. (In general, we don't bother to get the defs for synthesized
 351     // segments, only for segments which have come from the AST).
 352     pub hir_id: Option<HirId>,
 353     pub res: Option<Res>,
 354
 355     /// Type/lifetime parameters attached to this path. They come in
 356     /// two flavors: `Path<A,B,C>` and `Path(A,B) -> C`. Note that
 357     /// this is more than just simple syntactic sugar; the use of
 358     /// parens affects the region binding rules, so we preserve the
 359     /// distinction.
 360     pub args: Option<P<GenericArgs>>,
 361
 362     /// Whether to infer remaining type parameters, if any.
 363     /// This only applies to expression and pattern paths, and
 364     /// out of those only the segments with no type parameters
 365     /// to begin with, e.g., `Vec::new` is `<Vec<..>>::new::<..>`.
 366     pub infer_args: bool,
 367 }
 368
 369 impl PathSegment {
 370     /// Converts an identifier to the corresponding segment.
 371     pub fn from_ident(ident: Ident) -> PathSegment {
 372         PathSegment {
 373             ident,
 374             hir_id: None,
 375             res: None,
 376             infer_args: true,
 377             args: None,
 378         }
 379     }
 380
 381     pub fn new(
 382         ident: Ident,
 383         hir_id: Option<HirId>,
 384         res: Option<Res>,
 385         args: GenericArgs,
 386         infer_args: bool,
 387     ) -> Self {
 388         PathSegment {
 389             ident,
 390             hir_id,
 391             res,
 392             infer_args,
 393             args: if args.is_empty() {
 394                 None
 395             } else {
 396                 Some(P(args))
 397             }
 398         }
 399     }
 400
 401     pub fn generic_args(&self) -> &GenericArgs {
 402         if let Some(ref args) = self.args {
 403             args
 404         } else {
 405             const DUMMY: &GenericArgs = &GenericArgs::none();
 406             DUMMY
 407         }
 408     }
 409 }
 410
 411 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 412 pub struct ConstArg {
 413     pub value: AnonConst,
 414     pub span: Span,
 415 }
 416
 417 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 418 pub enum GenericArg {
 419     Lifetime(Lifetime),
 420     Type(Ty),
 421     Const(ConstArg),
 422 }
 423
 424 impl GenericArg {
 425     pub fn span(&self) -> Span {
 426         match self {
 427             GenericArg::Lifetime(l) => l.span,
 428             GenericArg::Type(t) => t.span,
 429             GenericArg::Const(c) => c.span,
 430         }
 431     }
 432
 433     pub fn id(&self) -> HirId {
 434         match self {
 435             GenericArg::Lifetime(l) => l.hir_id,
 436             GenericArg::Type(t) => t.hir_id,
 437             GenericArg::Const(c) => c.value.hir_id,
 438         }
 439     }
 440
 441     pub fn is_const(&self) -> bool {
 442         match self {
 443             GenericArg::Const(_) => true,
 444             _ => false,
 445         }
 446     }
 447 }
 448
 449 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 450 pub struct GenericArgs {
 451     /// The generic arguments for this path segment.
 452     pub args: HirVec<GenericArg>,
 453     /// Bindings (equality constraints) on associated types, if present.
 454     /// E.g., `Foo<A = Bar>`.
 455     pub bindings: HirVec<TypeBinding>,
 456     /// Were arguments written in parenthesized form `Fn(T) -> U`?
 457     /// This is required mostly for pretty-printing and diagnostics,
 458     /// but also for changing lifetime elision rules to be "function-like".
 459     pub parenthesized: bool,
 460 }
 461
 462 impl GenericArgs {
 463     pub const fn none() -> Self {
 464         Self {
 465             args: HirVec::new(),
 466             bindings: HirVec::new(),
 467             parenthesized: false,
 468         }
 469     }
 470
 471     pub fn is_empty(&self) -> bool {
 472         self.args.is_empty() && self.bindings.is_empty() && !self.parenthesized
 473     }
 474
 475     pub fn inputs(&self) -> &[Ty] {
 476         if self.parenthesized {
 477             for arg in &self.args {
 478                 match arg {
 479                     GenericArg::Lifetime(_) => {}
 480                     GenericArg::Type(ref ty) => {
 481                         if let TyKind::Tup(ref tys) = ty.kind {
 482                             return tys;
 483                         }
 484                         break;
 485                     }
 486                     GenericArg::Const(_) => {}
 487                 }
 488             }
 489         }
 490         bug!("GenericArgs::inputs: not a `Fn(T) -> U`");
 491     }
 492
 493     pub fn own_counts(&self) -> GenericParamCount {
 494         // We could cache this as a property of `GenericParamCount`, but
 495         // the aim is to refactor this away entirely eventually and the
 496         // presence of this method will be a constant reminder.
 497         let mut own_counts: GenericParamCount = Default::default();
 498
 499         for arg in &self.args {
 500             match arg {
 501                 GenericArg::Lifetime(_) => own_counts.lifetimes += 1,
 502                 GenericArg::Type(_) => own_counts.types += 1,
 503                 GenericArg::Const(_) => own_counts.consts += 1,
 504             };
 505         }
 506
 507         own_counts
 508     }
 509 }
 510
 511 /// A modifier on a bound, currently this is only used for `?Sized`, where the
 512 /// modifier is `Maybe`. Negative bounds should also be handled here.
 513 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, HashStable)]
 514 pub enum TraitBoundModifier {
 515     None,
 516     Maybe,
 517 }
 518
 519 /// The AST represents all type param bounds as types.
 520 /// `typeck::collect::compute_bounds` matches these against
 521 /// the "special" built-in traits (see `middle::lang_items`) and
 522 /// detects `Copy`, `Send` and `Sync`.
 523 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 524 pub enum GenericBound {
 525     Trait(PolyTraitRef, TraitBoundModifier),
 526     Outlives(Lifetime),
 527 }
 528
 529 impl GenericBound {
 530     pub fn span(&self) -> Span {
 531         match self {
 532             &GenericBound::Trait(ref t, ..) => t.span,
 533             &GenericBound::Outlives(ref l) => l.span,
 534         }
 535     }
 536 }
 537
 538 pub type GenericBounds = HirVec<GenericBound>;
 539
 540 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug, HashStable)]
 541 pub enum LifetimeParamKind {
 542     // Indicates that the lifetime definition was explicitly declared (e.g., in
 543     // `fn foo<'a>(x: &'a u8) -> &'a u8 { x }`).
 544     Explicit,
 545
 546     // Indicates that the lifetime definition was synthetically added
 547     // as a result of an in-band lifetime usage (e.g., in
 548     // `fn foo(x: &'a u8) -> &'a u8 { x }`).
 549     InBand,
 550
 551     // Indication that the lifetime was elided (e.g., in both cases in
 552     // `fn foo(x: &u8) -> &'_ u8 { x }`).
 553     Elided,
 554
 555     // Indication that the lifetime name was somehow in error.
 556     Error,
 557 }
 558
 559 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 560 pub enum GenericParamKind {
 561     /// A lifetime definition (e.g., `'a: 'b + 'c + 'd`).
 562     Lifetime {
 563         kind: LifetimeParamKind,
 564     },
 565     Type {
 566         default: Option<P<Ty>>,
 567         synthetic: Option<SyntheticTyParamKind>,
 568     },
 569     Const {
 570         ty: P<Ty>,
 571     }
 572 }
 573
 574 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 575 pub struct GenericParam {
 576     pub hir_id: HirId,
 577     pub name: ParamName,
 578     pub attrs: HirVec<Attribute>,
 579     pub bounds: GenericBounds,
 580     pub span: Span,
 581     pub pure_wrt_drop: bool,
 582     pub kind: GenericParamKind,
 583 }
 584
 585 #[derive(Default)]
 586 pub struct GenericParamCount {
 587     pub lifetimes: usize,
 588     pub types: usize,
 589     pub consts: usize,
 590 }
 591
 592 /// Represents lifetimes and type parameters attached to a declaration
 593 /// of a function, enum, trait, etc.
 594 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 595 pub struct Generics {
 596     pub params: HirVec<GenericParam>,
 597     pub where_clause: WhereClause,
 598     pub span: Span,
 599 }
 600
 601 impl Generics {
 602     pub const fn empty() -> Generics {
 603         Generics {
 604             params: HirVec::new(),
 605             where_clause: WhereClause {
 606                 predicates: HirVec::new(),
 607                 span: DUMMY_SP,
 608             },
 609             span: DUMMY_SP,
 610         }
 611     }
 612
 613     pub fn own_counts(&self) -> GenericParamCount {
 614         // We could cache this as a property of `GenericParamCount`, but
 615         // the aim is to refactor this away entirely eventually and the
 616         // presence of this method will be a constant reminder.
 617         let mut own_counts: GenericParamCount = Default::default();
 618
 619         for param in &self.params {
 620             match param.kind {
 621                 GenericParamKind::Lifetime { .. } => own_counts.lifetimes += 1,
 622                 GenericParamKind::Type { .. } => own_counts.types += 1,
 623                 GenericParamKind::Const { .. } => own_counts.consts += 1,
 624             };
 625         }
 626
 627         own_counts
 628     }
 629
 630     pub fn get_named(&self, name: Symbol) -> Option<&GenericParam> {
 631         for param in &self.params {
 632             if name == param.name.ident().name {
 633                 return Some(param);
 634             }
 635         }
 636         None
 637     }
 638
 639     pub fn spans(&self) -> MultiSpan {
 640         if self.params.is_empty() {
 641             self.span.into()
 642         } else {
 643             self.params.iter().map(|p| p.span).collect::<Vec<Span>>().into()
 644         }
 645     }
 646 }
 647
 648 /// Synthetic type parameters are converted to another form during lowering; this allows
 649 /// us to track the original form they had, and is useful for error messages.
 650 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, HashStable)]
 651 pub enum SyntheticTyParamKind {
 652     ImplTrait
 653 }
 654
 655 /// A where-clause in a definition.
 656 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 657 pub struct WhereClause {
 658     pub predicates: HirVec<WherePredicate>,
 659     // Only valid if predicates isn't empty.
 660     span: Span,
 661 }
 662
 663 impl WhereClause {
 664     pub fn span(&self) -> Option<Span> {
 665         if self.predicates.is_empty() {
 666             None
 667         } else {
 668             Some(self.span)
 669         }
 670     }
 671
 672     /// The `WhereClause` under normal circumstances points at either the predicates or the empty
 673     /// space where the `where` clause should be. Only of use for diagnostic suggestions.
 674     pub fn span_for_predicates_or_empty_place(&self) -> Span {
 675         self.span
 676     }
 677 }
 678
 679 /// A single predicate in a where-clause.
 680 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 681 pub enum WherePredicate {
 682     /// A type binding (e.g., `for<'c> Foo: Send + Clone + 'c`).
 683     BoundPredicate(WhereBoundPredicate),
 684     /// A lifetime predicate (e.g., `'a: 'b + 'c`).
 685     RegionPredicate(WhereRegionPredicate),
 686     /// An equality predicate (unsupported).
 687     EqPredicate(WhereEqPredicate),
 688 }
 689
 690 impl WherePredicate {
 691     pub fn span(&self) -> Span {
 692         match self {
 693             &WherePredicate::BoundPredicate(ref p) => p.span,
 694             &WherePredicate::RegionPredicate(ref p) => p.span,
 695             &WherePredicate::EqPredicate(ref p) => p.span,
 696         }
 697     }
 698 }
 699
 700 /// A type bound (e.g., `for<'c> Foo: Send + Clone + 'c`).
 701 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 702 pub struct WhereBoundPredicate {
 703     pub span: Span,
 704     /// Any generics from a `for` binding.
 705     pub bound_generic_params: HirVec<GenericParam>,
 706     /// The type being bounded.
 707     pub bounded_ty: P<Ty>,
 708     /// Trait and lifetime bounds (e.g., `Clone + Send + 'static`).
 709     pub bounds: GenericBounds,
 710 }
 711
 712 /// A lifetime predicate (e.g., `'a: 'b + 'c`).
 713 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 714 pub struct WhereRegionPredicate {
 715     pub span: Span,
 716     pub lifetime: Lifetime,
 717     pub bounds: GenericBounds,
 718 }
 719
 720 /// An equality predicate (e.g., `T = int`); currently unsupported.
 721 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 722 pub struct WhereEqPredicate {
 723     pub hir_id: HirId,
 724     pub span: Span,
 725     pub lhs_ty: P<Ty>,
 726     pub rhs_ty: P<Ty>,
 727 }
 728
 729 #[derive(RustcEncodable, RustcDecodable, Debug)]
 730 pub struct ModuleItems {
 731     // Use BTreeSets here so items are in the same order as in the
 732     // list of all items in Crate
 733     pub items: BTreeSet<HirId>,
 734     pub trait_items: BTreeSet<TraitItemId>,
 735     pub impl_items: BTreeSet<ImplItemId>,
 736 }
 737
 738 /// The top-level data structure that stores the entire contents of
 739 /// the crate currently being compiled.
 740 ///
 741 /// For more details, see the [rustc guide].
 742 ///
 743 /// [rustc guide]: https://rust-lang.github.io/rustc-guide/hir.html
 744 #[derive(RustcEncodable, RustcDecodable, Debug)]
 745 pub struct Crate {
 746     pub module: Mod,
 747     pub attrs: HirVec<Attribute>,
 748     pub span: Span,
 749     pub exported_macros: HirVec<MacroDef>,
 750     // Attributes from non-exported macros, kept only for collecting the library feature list.
 751     pub non_exported_macro_attrs: HirVec<Attribute>,
 752
 753     // N.B., we use a `BTreeMap` here so that `visit_all_items` iterates
 754     // over the ids in increasing order. In principle it should not
 755     // matter what order we visit things in, but in *practice* it
 756     // does, because it can affect the order in which errors are
 757     // detected, which in turn can make compile-fail tests yield
 758     // slightly different results.
 759     pub items: BTreeMap<HirId, Item>,
 760
 761     pub trait_items: BTreeMap<TraitItemId, TraitItem>,
 762     pub impl_items: BTreeMap<ImplItemId, ImplItem>,
 763     pub bodies: BTreeMap<BodyId, Body>,
 764     pub trait_impls: BTreeMap<DefId, Vec<HirId>>,
 765
 766     /// A list of the body ids written out in the order in which they
 767     /// appear in the crate. If you're going to process all the bodies
 768     /// in the crate, you should iterate over this list rather than the keys
 769     /// of bodies.
 770     pub body_ids: Vec<BodyId>,
 771
 772     /// A list of modules written out in the order in which they
 773     /// appear in the crate. This includes the main crate module.
 774     pub modules: BTreeMap<HirId, ModuleItems>,
 775 }
 776
 777 impl Crate {
 778     pub fn item(&self, id: HirId) -> &Item {
 779         &self.items[&id]
 780     }
 781
 782     pub fn trait_item(&self, id: TraitItemId) -> &TraitItem {
 783         &self.trait_items[&id]
 784     }
 785
 786     pub fn impl_item(&self, id: ImplItemId) -> &ImplItem {
 787         &self.impl_items[&id]
 788     }
 789
 790     /// Visits all items in the crate in some deterministic (but
 791     /// unspecified) order. If you just need to process every item,
 792     /// but don't care about nesting, this method is the best choice.
 793     ///
 794     /// If you do care about nesting -- usually because your algorithm
 795     /// follows lexical scoping rules -- then you want a different
 796     /// approach. You should override `visit_nested_item` in your
 797     /// visitor and then call `intravisit::walk_crate` instead.
 798     pub fn visit_all_item_likes<'hir, V>(&'hir self, visitor: &mut V)
 799         where V: itemlikevisit::ItemLikeVisitor<'hir>
 800     {
 801         for (_, item) in &self.items {
 802             visitor.visit_item(item);
 803         }
 804
 805         for (_, trait_item) in &self.trait_items {
 806             visitor.visit_trait_item(trait_item);
 807         }
 808
 809         for (_, impl_item) in &self.impl_items {
 810             visitor.visit_impl_item(impl_item);
 811         }
 812     }
 813
 814     /// A parallel version of `visit_all_item_likes`.
 815     pub fn par_visit_all_item_likes<'hir, V>(&'hir self, visitor: &V)
 816         where V: itemlikevisit::ParItemLikeVisitor<'hir> + Sync + Send
 817     {
 818         parallel!({
 819             par_for_each_in(&self.items, |(_, item)| {
 820                 visitor.visit_item(item);
 821             });
 822         }, {
 823             par_for_each_in(&self.trait_items, |(_, trait_item)| {
 824                 visitor.visit_trait_item(trait_item);
 825             });
 826         }, {
 827             par_for_each_in(&self.impl_items, |(_, impl_item)| {
 828                 visitor.visit_impl_item(impl_item);
 829             });
 830         });
 831     }
 832
 833     pub fn body(&self, id: BodyId) -> &Body {
 834         &self.bodies[&id]
 835     }
 836 }
 837
 838 /// A macro definition, in this crate or imported from another.
 839 ///
 840 /// Not parsed directly, but created on macro import or `macro_rules!` expansion.
 841 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 842 pub struct MacroDef {
 843     pub name: Name,
 844     pub vis: Visibility,
 845     pub attrs: HirVec<Attribute>,
 846     pub hir_id: HirId,
 847     pub span: Span,
 848     pub body: TokenStream,
 849     pub legacy: bool,
 850 }
 851
 852 /// A block of statements `{ .. }`, which may have a label (in this case the
 853 /// `targeted_by_break` field will be `true`) and may be `unsafe` by means of
 854 /// the `rules` being anything but `DefaultBlock`.
 855 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 856 pub struct Block {
 857     /// Statements in a block.
 858     pub stmts: HirVec<Stmt>,
 859     /// An expression at the end of the block
 860     /// without a semicolon, if any.
 861     pub expr: Option<P<Expr>>,
 862     #[stable_hasher(ignore)]
 863     pub hir_id: HirId,
 864     /// Distinguishes between `unsafe { ... }` and `{ ... }`.
 865     pub rules: BlockCheckMode,
 866     pub span: Span,
 867     /// If true, then there may exist `break 'a` values that aim to
 868     /// break out of this block early.
 869     /// Used by `'label: {}` blocks and by `try {}` blocks.
 870     pub targeted_by_break: bool,
 871 }
 872
 873 #[derive(RustcEncodable, RustcDecodable, HashStable)]
 874 pub struct Pat {
 875     #[stable_hasher(ignore)]
 876     pub hir_id: HirId,
 877     pub kind: PatKind,
 878     pub span: Span,
 879 }
 880
 881 impl fmt::Debug for Pat {
 882     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 883         write!(f, "pat({}: {})", self.hir_id,
 884                print::to_string(print::NO_ANN, |s| s.print_pat(self)))
 885     }
 886 }
 887
 888 impl Pat {
 889     // FIXME(#19596) this is a workaround, but there should be a better way
 890     fn walk_short_(&self, it: &mut impl FnMut(&Pat) -> bool) -> bool {
 891         if !it(self) {
 892             return false;
 893         }
 894
 895         use PatKind::*;
 896         match &self.kind {
 897             Wild | Lit(_) | Range(..) | Binding(.., None) | Path(_) => true,
 898             Box(s) | Ref(s, _) | Binding(.., Some(s)) => s.walk_short_(it),
 899             Struct(_, fields, _) => fields.iter().all(|field| field.pat.walk_short_(it)),
 900             TupleStruct(_, s, _) | Tuple(s, _) | Or(s) => s.iter().all(|p| p.walk_short_(it)),
 901             Slice(before, slice, after) => {
 902                 before.iter()
 903                       .chain(slice.iter())
 904                       .chain(after.iter())
 905                       .all(|p| p.walk_short_(it))
 906             }
 907         }
 908     }
 909
 910     /// Walk the pattern in left-to-right order,
 911     /// short circuiting (with `.all(..)`) if `false` is returned.
 912     ///
 913     /// Note that when visiting e.g. `Tuple(ps)`,
 914     /// if visiting `ps[0]` returns `false`,
 915     /// then `ps[1]` will not be visited.
 916     pub fn walk_short(&self, mut it: impl FnMut(&Pat) -> bool) -> bool {
 917         self.walk_short_(&mut it)
 918     }
 919
 920     // FIXME(#19596) this is a workaround, but there should be a better way
 921     fn walk_(&self, it: &mut impl FnMut(&Pat) -> bool) {
 922         if !it(self) {
 923             return;
 924         }
 925
 926         use PatKind::*;
 927         match &self.kind {
 928             Wild | Lit(_) | Range(..) | Binding(.., None) | Path(_) => {},
 929             Box(s) | Ref(s, _) | Binding(.., Some(s)) => s.walk_(it),
 930             Struct(_, fields, _) => fields.iter().for_each(|field| field.pat.walk_(it)),
 931             TupleStruct(_, s, _) | Tuple(s, _) | Or(s) => s.iter().for_each(|p| p.walk_(it)),
 932             Slice(before, slice, after) => {
 933                 before.iter()
 934                       .chain(slice.iter())
 935                       .chain(after.iter())
 936                       .for_each(|p| p.walk_(it))
 937             }
 938         }
 939     }
 940
 941     /// Walk the pattern in left-to-right order.
 942     ///
 943     /// If `it(pat)` returns `false`, the children are not visited.
 944     pub fn walk(&self, mut it: impl FnMut(&Pat) -> bool) {
 945         self.walk_(&mut it)
 946     }
 947 }
 948
 949 /// A single field in a struct pattern.
 950 ///
 951 /// Patterns like the fields of Foo `{ x, ref y, ref mut z }`
 952 /// are treated the same as` x: x, y: ref y, z: ref mut z`,
 953 /// except `is_shorthand` is true.
 954 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
 955 pub struct FieldPat {
 956     #[stable_hasher(ignore)]
 957     pub hir_id: HirId,
 958     /// The identifier for the field.
 959     #[stable_hasher(project(name))]
 960     pub ident: Ident,
 961     /// The pattern the field is destructured to.
 962     pub pat: P<Pat>,
 963     pub is_shorthand: bool,
 964     pub span: Span,
 965 }
 966
 967 /// Explicit binding annotations given in the HIR for a binding. Note
 968 /// that this is not the final binding *mode* that we infer after type
 969 /// inference.
 970 #[derive(Copy, Clone, PartialEq, RustcEncodable, RustcDecodable, Debug, HashStable)]
 971 pub enum BindingAnnotation {
 972     /// No binding annotation given: this means that the final binding mode
 973     /// will depend on whether we have skipped through a `&` reference
 974     /// when matching. For example, the `x` in `Some(x)` will have binding
 975     /// mode `None`; if you do `let Some(x) = &Some(22)`, it will
 976     /// ultimately be inferred to be by-reference.
 977     ///
 978     /// Note that implicit reference skipping is not implemented yet (#42640).
 979     Unannotated,
 980
 981     /// Annotated with `mut x` -- could be either ref or not, similar to `None`.
 982     Mutable,
 983
 984     /// Annotated as `ref`, like `ref x`
 985     Ref,
 986
 987     /// Annotated as `ref mut x`.
 988     RefMut,
 989 }
 990
 991 #[derive(Copy, Clone, PartialEq, RustcEncodable, RustcDecodable, Debug, HashStable)]
 992 pub enum RangeEnd {
 993     Included,
 994     Excluded,
 995 }
 996
 997 impl fmt::Display for RangeEnd {
 998     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 999         f.write_str(match self {
1000             RangeEnd::Included => "..=",
1001             RangeEnd::Excluded => "..",
1002         })
1003     }
1004 }
1005
1006 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1007 pub enum PatKind {
1008     /// Represents a wildcard pattern (i.e., `_`).
1009     Wild,
1010
1011     /// A fresh binding `ref mut binding @ OPT_SUBPATTERN`.
1012     /// The `HirId` is the canonical ID for the variable being bound,
1013     /// (e.g., in `Ok(x) | Err(x)`, both `x` use the same canonical ID),
1014     /// which is the pattern ID of the first `x`.
1015     Binding(BindingAnnotation, HirId, Ident, Option<P<Pat>>),
1016
1017     /// A struct or struct variant pattern (e.g., `Variant {x, y, ..}`).
1018     /// The `bool` is `true` in the presence of a `..`.
1019     Struct(QPath, HirVec<FieldPat>, bool),
1020
1021     /// A tuple struct/variant pattern `Variant(x, y, .., z)`.
1022     /// If the `..` pattern fragment is present, then `Option<usize>` denotes its position.
1023     /// `0 <= position <= subpats.len()`
1024     TupleStruct(QPath, HirVec<P<Pat>>, Option<usize>),
1025
1026     /// An or-pattern `A | B | C`.
1027     /// Invariant: `pats.len() >= 2`.
1028     Or(HirVec<P<Pat>>),
1029
1030     /// A path pattern for an unit struct/variant or a (maybe-associated) constant.
1031     Path(QPath),
1032
1033     /// A tuple pattern (e.g., `(a, b)`).
1034     /// If the `..` pattern fragment is present, then `Option<usize>` denotes its position.
1035     /// `0 <= position <= subpats.len()`
1036     Tuple(HirVec<P<Pat>>, Option<usize>),
1037
1038     /// A `box` pattern.
1039     Box(P<Pat>),
1040
1041     /// A reference pattern (e.g., `&mut (a, b)`).
1042     Ref(P<Pat>, Mutability),
1043
1044     /// A literal.
1045     Lit(P<Expr>),
1046
1047     /// A range pattern (e.g., `1..=2` or `1..2`).
1048     Range(P<Expr>, P<Expr>, RangeEnd),
1049
1050     /// `[a, b, ..i, y, z]` is represented as:
1051     ///     `PatKind::Slice(box [a, b], Some(i), box [y, z])`.
1052     Slice(HirVec<P<Pat>>, Option<P<Pat>>, HirVec<P<Pat>>),
1053 }
1054
1055 #[derive(Copy, Clone, PartialEq, RustcEncodable, RustcDecodable, Debug, HashStable)]
1056 pub enum BinOpKind {
1057     /// The `+` operator (addition).
1058     Add,
1059     /// The `-` operator (subtraction).
1060     Sub,
1061     /// The `*` operator (multiplication).
1062     Mul,
1063     /// The `/` operator (division).
1064     Div,
1065     /// The `%` operator (modulus).
1066     Rem,
1067     /// The `&&` operator (logical and).
1068     And,
1069     /// The `||` operator (logical or).
1070     Or,
1071     /// The `^` operator (bitwise xor).
1072     BitXor,
1073     /// The `&` operator (bitwise and).
1074     BitAnd,
1075     /// The `|` operator (bitwise or).
1076     BitOr,
1077     /// The `<<` operator (shift left).
1078     Shl,
1079     /// The `>>` operator (shift right).
1080     Shr,
1081     /// The `==` operator (equality).
1082     Eq,
1083     /// The `<` operator (less than).
1084     Lt,
1085     /// The `<=` operator (less than or equal to).
1086     Le,
1087     /// The `!=` operator (not equal to).
1088     Ne,
1089     /// The `>=` operator (greater than or equal to).
1090     Ge,
1091     /// The `>` operator (greater than).
1092     Gt,
1093 }
1094
1095 impl BinOpKind {
1096     pub fn as_str(self) -> &'static str {
1097         match self {
1098             BinOpKind::Add => "+",
1099             BinOpKind::Sub => "-",
1100             BinOpKind::Mul => "*",
1101             BinOpKind::Div => "/",
1102             BinOpKind::Rem => "%",
1103             BinOpKind::And => "&&",
1104             BinOpKind::Or => "||",
1105             BinOpKind::BitXor => "^",
1106             BinOpKind::BitAnd => "&",
1107             BinOpKind::BitOr => "|",
1108             BinOpKind::Shl => "<<",
1109             BinOpKind::Shr => ">>",
1110             BinOpKind::Eq => "==",
1111             BinOpKind::Lt => "<",
1112             BinOpKind::Le => "<=",
1113             BinOpKind::Ne => "!=",
1114             BinOpKind::Ge => ">=",
1115             BinOpKind::Gt => ">",
1116         }
1117     }
1118
1119     pub fn is_lazy(self) -> bool {
1120         match self {
1121             BinOpKind::And | BinOpKind::Or => true,
1122             _ => false,
1123         }
1124     }
1125
1126     pub fn is_shift(self) -> bool {
1127         match self {
1128             BinOpKind::Shl | BinOpKind::Shr => true,
1129             _ => false,
1130         }
1131     }
1132
1133     pub fn is_comparison(self) -> bool {
1134         match self {
1135             BinOpKind::Eq |
1136             BinOpKind::Lt |
1137             BinOpKind::Le |
1138             BinOpKind::Ne |
1139             BinOpKind::Gt |
1140             BinOpKind::Ge => true,
1141             BinOpKind::And |
1142             BinOpKind::Or |
1143             BinOpKind::Add |
1144             BinOpKind::Sub |
1145             BinOpKind::Mul |
1146             BinOpKind::Div |
1147             BinOpKind::Rem |
1148             BinOpKind::BitXor |
1149             BinOpKind::BitAnd |
1150             BinOpKind::BitOr |
1151             BinOpKind::Shl |
1152             BinOpKind::Shr => false,
1153         }
1154     }
1155
1156     /// Returns `true` if the binary operator takes its arguments by value.
1157     pub fn is_by_value(self) -> bool {
1158         !self.is_comparison()
1159     }
1160 }
1161
1162 impl Into<ast::BinOpKind> for BinOpKind {
1163     fn into(self) -> ast::BinOpKind {
1164         match self {
1165             BinOpKind::Add => ast::BinOpKind::Add,
1166             BinOpKind::Sub => ast::BinOpKind::Sub,
1167             BinOpKind::Mul => ast::BinOpKind::Mul,
1168             BinOpKind::Div => ast::BinOpKind::Div,
1169             BinOpKind::Rem => ast::BinOpKind::Rem,
1170             BinOpKind::And => ast::BinOpKind::And,
1171             BinOpKind::Or => ast::BinOpKind::Or,
1172             BinOpKind::BitXor => ast::BinOpKind::BitXor,
1173             BinOpKind::BitAnd => ast::BinOpKind::BitAnd,
1174             BinOpKind::BitOr => ast::BinOpKind::BitOr,
1175             BinOpKind::Shl => ast::BinOpKind::Shl,
1176             BinOpKind::Shr => ast::BinOpKind::Shr,
1177             BinOpKind::Eq => ast::BinOpKind::Eq,
1178             BinOpKind::Lt => ast::BinOpKind::Lt,
1179             BinOpKind::Le => ast::BinOpKind::Le,
1180             BinOpKind::Ne => ast::BinOpKind::Ne,
1181             BinOpKind::Ge => ast::BinOpKind::Ge,
1182             BinOpKind::Gt => ast::BinOpKind::Gt,
1183         }
1184     }
1185 }
1186
1187 pub type BinOp = Spanned<BinOpKind>;
1188
1189 #[derive(Copy, Clone, PartialEq, RustcEncodable, RustcDecodable, Debug, HashStable)]
1190 pub enum UnOp {
1191     /// The `*` operator (deferencing).
1192     UnDeref,
1193     /// The `!` operator (logical negation).
1194     UnNot,
1195     /// The `-` operator (negation).
1196     UnNeg,
1197 }
1198
1199 impl UnOp {
1200     pub fn as_str(self) -> &'static str {
1201         match self {
1202             UnDeref => "*",
1203             UnNot => "!",
1204             UnNeg => "-",
1205         }
1206     }
1207
1208     /// Returns `true` if the unary operator takes its argument by value.
1209     pub fn is_by_value(self) -> bool {
1210         match self {
1211             UnNeg | UnNot => true,
1212             _ => false,
1213         }
1214     }
1215 }
1216
1217 /// A statement.
1218 #[derive(RustcEncodable, RustcDecodable, HashStable)]
1219 pub struct Stmt {
1220     pub hir_id: HirId,
1221     pub kind: StmtKind,
1222     pub span: Span,
1223 }
1224
1225 impl fmt::Debug for Stmt {
1226     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1227         write!(f, "stmt({}: {})", self.hir_id,
1228                print::to_string(print::NO_ANN, |s| s.print_stmt(self)))
1229     }
1230 }
1231
1232 /// The contents of a statement.
1233 #[derive(RustcEncodable, RustcDecodable, HashStable)]
1234 pub enum StmtKind {
1235     /// A local (`let`) binding.
1236     Local(P<Local>),
1237
1238     /// An item binding.
1239     Item(ItemId),
1240
1241     /// An expression without a trailing semi-colon (must have unit type).
1242     Expr(P<Expr>),
1243
1244     /// An expression with a trailing semi-colon (may have any type).
1245     Semi(P<Expr>),
1246 }
1247
1248 impl StmtKind {
1249     pub fn attrs(&self) -> &[Attribute] {
1250         match *self {
1251             StmtKind::Local(ref l) => &l.attrs,
1252             StmtKind::Item(_) => &[],
1253             StmtKind::Expr(ref e) |
1254             StmtKind::Semi(ref e) => &e.attrs,
1255         }
1256     }
1257 }
1258
1259 /// Represents a `let` statement (i.e., `let <pat>:<ty> = <expr>;`).
1260 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1261 pub struct Local {
1262     pub pat: P<Pat>,
1263     /// Type annotation, if any (otherwise the type will be inferred).
1264     pub ty: Option<P<Ty>>,
1265     /// Initializer expression to set the value, if any.
1266     pub init: Option<P<Expr>>,
1267     pub hir_id: HirId,
1268     pub span: Span,
1269     pub attrs: ThinVec<Attribute>,
1270     /// Can be `ForLoopDesugar` if the `let` statement is part of a `for` loop
1271     /// desugaring. Otherwise will be `Normal`.
1272     pub source: LocalSource,
1273 }
1274
1275 /// Represents a single arm of a `match` expression, e.g.
1276 /// `<pat> (if <guard>) => <body>`.
1277 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1278 pub struct Arm {
1279     #[stable_hasher(ignore)]
1280     pub hir_id: HirId,
1281     pub span: Span,
1282     pub attrs: HirVec<Attribute>,
1283     /// If this pattern and the optional guard matches, then `body` is evaluated.
1284     pub pat: P<Pat>,
1285     /// Optional guard clause.
1286     pub guard: Option<Guard>,
1287     /// The expression the arm evaluates to if this arm matches.
1288     pub body: P<Expr>,
1289 }
1290
1291 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1292 pub enum Guard {
1293     If(P<Expr>),
1294 }
1295
1296 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1297 pub struct Field {
1298     #[stable_hasher(ignore)]
1299     pub hir_id: HirId,
1300     pub ident: Ident,
1301     pub expr: P<Expr>,
1302     pub span: Span,
1303     pub is_shorthand: bool,
1304 }
1305
1306 #[derive(Copy, Clone, PartialEq, RustcEncodable, RustcDecodable, Debug, HashStable)]
1307 pub enum BlockCheckMode {
1308     DefaultBlock,
1309     UnsafeBlock(UnsafeSource),
1310     PushUnsafeBlock(UnsafeSource),
1311     PopUnsafeBlock(UnsafeSource),
1312 }
1313
1314 #[derive(Copy, Clone, PartialEq, RustcEncodable, RustcDecodable, Debug, HashStable)]
1315 pub enum UnsafeSource {
1316     CompilerGenerated,
1317     UserProvided,
1318 }
1319
1320 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, RustcEncodable, RustcDecodable, Hash, Debug)]
1321 pub struct BodyId {
1322     pub hir_id: HirId,
1323 }
1324
1325 /// The body of a function, closure, or constant value. In the case of
1326 /// a function, the body contains not only the function body itself
1327 /// (which is an expression), but also the argument patterns, since
1328 /// those are something that the caller doesn't really care about.
1329 ///
1330 /// # Examples
1331 ///
1332 /// ```
1333 /// fn foo((x, y): (u32, u32)) -> u32 {
1334 ///     x + y
1335 /// }
1336 /// ```
1337 ///
1338 /// Here, the `Body` associated with `foo()` would contain:
1339 ///
1340 /// - an `params` array containing the `(x, y)` pattern
1341 /// - a `value` containing the `x + y` expression (maybe wrapped in a block)
1342 /// - `generator_kind` would be `None`
1343 ///
1344 /// All bodies have an **owner**, which can be accessed via the HIR
1345 /// map using `body_owner_def_id()`.
1346 #[derive(RustcEncodable, RustcDecodable, Debug)]
1347 pub struct Body {
1348     pub params: HirVec<Param>,
1349     pub value: Expr,
1350     pub generator_kind: Option<GeneratorKind>,
1351 }
1352
1353 impl Body {
1354     pub fn id(&self) -> BodyId {
1355         BodyId {
1356             hir_id: self.value.hir_id,
1357         }
1358     }
1359
1360     pub fn generator_kind(&self) -> Option<GeneratorKind> {
1361         self.generator_kind
1362     }
1363 }
1364
1365 /// The type of source expression that caused this generator to be created.
1366 #[derive(Clone, PartialEq, Eq, HashStable, RustcEncodable, RustcDecodable, Debug, Copy)]
1367 pub enum GeneratorKind {
1368     /// An explicit `async` block or the body of an async function.
1369     Async(AsyncGeneratorKind),
1370
1371     /// A generator literal created via a `yield` inside a closure.
1372     Gen,
1373 }
1374
1375 impl fmt::Display for GeneratorKind {
1376     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1377         match self {
1378             GeneratorKind::Async(k) => fmt::Display::fmt(k, f),
1379             GeneratorKind::Gen => f.write_str("generator"),
1380         }
1381     }
1382 }
1383
1384 /// In the case of a generator created as part of an async construct,
1385 /// which kind of async construct caused it to be created?
1386 ///
1387 /// This helps error messages but is also used to drive coercions in
1388 /// type-checking (see #60424).
1389 #[derive(Clone, PartialEq, Eq, HashStable, RustcEncodable, RustcDecodable, Debug, Copy)]
1390 pub enum AsyncGeneratorKind {
1391     /// An explicit `async` block written by the user.
1392     Block,
1393
1394     /// An explicit `async` block written by the user.
1395     Closure,
1396
1397     /// The `async` block generated as the body of an async function.
1398     Fn,
1399 }
1400
1401 impl fmt::Display for AsyncGeneratorKind {
1402     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1403         f.write_str(match self {
1404             AsyncGeneratorKind::Block => "`async` block",
1405             AsyncGeneratorKind::Closure => "`async` closure body",
1406             AsyncGeneratorKind::Fn => "`async fn` body",
1407         })
1408     }
1409 }
1410
1411 #[derive(Copy, Clone, Debug)]
1412 pub enum BodyOwnerKind {
1413     /// Functions and methods.
1414     Fn,
1415
1416     /// Closures
1417     Closure,
1418
1419     /// Constants and associated constants.
1420     Const,
1421
1422     /// Initializer of a `static` item.
1423     Static(Mutability),
1424 }
1425
1426 impl BodyOwnerKind {
1427     pub fn is_fn_or_closure(self) -> bool {
1428         match self {
1429             BodyOwnerKind::Fn | BodyOwnerKind::Closure => true,
1430             BodyOwnerKind::Const | BodyOwnerKind::Static(_) => false,
1431         }
1432     }
1433 }
1434
1435 /// A literal.
1436 pub type Lit = Spanned<LitKind>;
1437
1438 /// A constant (expression) that's not an item or associated item,
1439 /// but needs its own `DefId` for type-checking, const-eval, etc.
1440 /// These are usually found nested inside types (e.g., array lengths)
1441 /// or expressions (e.g., repeat counts), and also used to define
1442 /// explicit discriminant values for enum variants.
1443 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug, HashStable)]
1444 pub struct AnonConst {
1445     pub hir_id: HirId,
1446     pub body: BodyId,
1447 }
1448
1449 /// An expression.
1450 #[derive(RustcEncodable, RustcDecodable)]
1451 pub struct Expr {
1452     pub hir_id: HirId,
1453     pub kind: ExprKind,
1454     pub attrs: ThinVec<Attribute>,
1455     pub span: Span,
1456 }
1457
1458 // `Expr` is used a lot. Make sure it doesn't unintentionally get bigger.
1459 #[cfg(target_arch = "x86_64")]
1460 static_assert_size!(Expr, 64);
1461
1462 impl Expr {
1463     pub fn precedence(&self) -> ExprPrecedence {
1464         match self.kind {
1465             ExprKind::Box(_) => ExprPrecedence::Box,
1466             ExprKind::Array(_) => ExprPrecedence::Array,
1467             ExprKind::Call(..) => ExprPrecedence::Call,
1468             ExprKind::MethodCall(..) => ExprPrecedence::MethodCall,
1469             ExprKind::Tup(_) => ExprPrecedence::Tup,
1470             ExprKind::Binary(op, ..) => ExprPrecedence::Binary(op.node.into()),
1471             ExprKind::Unary(..) => ExprPrecedence::Unary,
1472             ExprKind::Lit(_) => ExprPrecedence::Lit,
1473             ExprKind::Type(..) | ExprKind::Cast(..) => ExprPrecedence::Cast,
1474             ExprKind::DropTemps(ref expr, ..) => expr.precedence(),
1475             ExprKind::Loop(..) => ExprPrecedence::Loop,
1476             ExprKind::Match(..) => ExprPrecedence::Match,
1477             ExprKind::Closure(..) => ExprPrecedence::Closure,
1478             ExprKind::Block(..) => ExprPrecedence::Block,
1479             ExprKind::Assign(..) => ExprPrecedence::Assign,
1480             ExprKind::AssignOp(..) => ExprPrecedence::AssignOp,
1481             ExprKind::Field(..) => ExprPrecedence::Field,
1482             ExprKind::Index(..) => ExprPrecedence::Index,
1483             ExprKind::Path(..) => ExprPrecedence::Path,
1484             ExprKind::AddrOf(..) => ExprPrecedence::AddrOf,
1485             ExprKind::Break(..) => ExprPrecedence::Break,
1486             ExprKind::Continue(..) => ExprPrecedence::Continue,
1487             ExprKind::Ret(..) => ExprPrecedence::Ret,
1488             ExprKind::InlineAsm(..) => ExprPrecedence::InlineAsm,
1489             ExprKind::Struct(..) => ExprPrecedence::Struct,
1490             ExprKind::Repeat(..) => ExprPrecedence::Repeat,
1491             ExprKind::Yield(..) => ExprPrecedence::Yield,
1492             ExprKind::Err => ExprPrecedence::Err,
1493         }
1494     }
1495
1496     pub fn is_place_expr(&self) -> bool {
1497          match self.kind {
1498             ExprKind::Path(QPath::Resolved(_, ref path)) => {
1499                 match path.res {
1500                     Res::Local(..)
1501                     | Res::Def(DefKind::Static, _)
1502                     | Res::Err => true,
1503                     _ => false,
1504                 }
1505             }
1506
1507             ExprKind::Type(ref e, _) => {
1508                 e.is_place_expr()
1509             }
1510
1511             ExprKind::Unary(UnDeref, _) |
1512             ExprKind::Field(..) |
1513             ExprKind::Index(..) => {
1514                 true
1515             }
1516
1517             // Partially qualified paths in expressions can only legally
1518             // refer to associated items which are always rvalues.
1519             ExprKind::Path(QPath::TypeRelative(..)) |
1520
1521             ExprKind::Call(..) |
1522             ExprKind::MethodCall(..) |
1523             ExprKind::Struct(..) |
1524             ExprKind::Tup(..) |
1525             ExprKind::Match(..) |
1526             ExprKind::Closure(..) |
1527             ExprKind::Block(..) |
1528             ExprKind::Repeat(..) |
1529             ExprKind::Array(..) |
1530             ExprKind::Break(..) |
1531             ExprKind::Continue(..) |
1532             ExprKind::Ret(..) |
1533             ExprKind::Loop(..) |
1534             ExprKind::Assign(..) |
1535             ExprKind::InlineAsm(..) |
1536             ExprKind::AssignOp(..) |
1537             ExprKind::Lit(_) |
1538             ExprKind::Unary(..) |
1539             ExprKind::Box(..) |
1540             ExprKind::AddrOf(..) |
1541             ExprKind::Binary(..) |
1542             ExprKind::Yield(..) |
1543             ExprKind::Cast(..) |
1544             ExprKind::DropTemps(..) |
1545             ExprKind::Err => {
1546                 false
1547             }
1548         }
1549     }
1550
1551     /// If `Self.kind` is `ExprKind::DropTemps(expr)`, drill down until we get a non-`DropTemps`
1552     /// `Expr`. This is used in suggestions to ignore this `ExprKind` as it is semantically
1553     /// silent, only signaling the ownership system. By doing this, suggestions that check the
1554     /// `ExprKind` of any given `Expr` for presentation don't have to care about `DropTemps`
1555     /// beyond remembering to call this function before doing analysis on it.
1556     pub fn peel_drop_temps(&self) -> &Self {
1557         let mut expr = self;
1558         while let ExprKind::DropTemps(inner) = &expr.kind {
1559             expr = inner;
1560         }
1561         expr
1562     }
1563 }
1564
1565 impl fmt::Debug for Expr {
1566     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1567         write!(f, "expr({}: {})", self.hir_id,
1568                print::to_string(print::NO_ANN, |s| s.print_expr(self)))
1569     }
1570 }
1571
1572 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1573 pub enum ExprKind {
1574     /// A `box x` expression.
1575     Box(P<Expr>),
1576     /// An array (e.g., `[a, b, c, d]`).
1577     Array(HirVec<Expr>),
1578     /// A function call.
1579     ///
1580     /// The first field resolves to the function itself (usually an `ExprKind::Path`),
1581     /// and the second field is the list of arguments.
1582     /// This also represents calling the constructor of
1583     /// tuple-like ADTs such as tuple structs and enum variants.
1584     Call(P<Expr>, HirVec<Expr>),
1585     /// A method call (e.g., `x.foo::<'static, Bar, Baz>(a, b, c, d)`).
1586     ///
1587     /// The `PathSegment`/`Span` represent the method name and its generic arguments
1588     /// (within the angle brackets).
1589     /// The first element of the vector of `Expr`s is the expression that evaluates
1590     /// to the object on which the method is being called on (the receiver),
1591     /// and the remaining elements are the rest of the arguments.
1592     /// Thus, `x.foo::<Bar, Baz>(a, b, c, d)` is represented as
1593     /// `ExprKind::MethodCall(PathSegment { foo, [Bar, Baz] }, [x, a, b, c, d])`.
1594     ///
1595     /// To resolve the called method to a `DefId`, call [`type_dependent_def_id`] with
1596     /// the `hir_id` of the `MethodCall` node itself.
1597     ///
1598     /// [`type_dependent_def_id`]: ../ty/struct.TypeckTables.html#method.type_dependent_def_id
1599     MethodCall(P<PathSegment>, Span, HirVec<Expr>),
1600     /// A tuple (e.g., `(a, b, c, d)`).
1601     Tup(HirVec<Expr>),
1602     /// A binary operation (e.g., `a + b`, `a * b`).
1603     Binary(BinOp, P<Expr>, P<Expr>),
1604     /// A unary operation (e.g., `!x`, `*x`).
1605     Unary(UnOp, P<Expr>),
1606     /// A literal (e.g., `1`, `"foo"`).
1607     Lit(Lit),
1608     /// A cast (e.g., `foo as f64`).
1609     Cast(P<Expr>, P<Ty>),
1610     /// A type reference (e.g., `Foo`).
1611     Type(P<Expr>, P<Ty>),
1612     /// Wraps the expression in a terminating scope.
1613     /// This makes it semantically equivalent to `{ let _t = expr; _t }`.
1614     ///
1615     /// This construct only exists to tweak the drop order in HIR lowering.
1616     /// An example of that is the desugaring of `for` loops.
1617     DropTemps(P<Expr>),
1618     /// A conditionless loop (can be exited with `break`, `continue`, or `return`).
1619     ///
1620     /// I.e., `'label: loop { <block> }`.
1621     Loop(P<Block>, Option<Label>, LoopSource),
1622     /// A `match` block, with a source that indicates whether or not it is
1623     /// the result of a desugaring, and if so, which kind.
1624     Match(P<Expr>, HirVec<Arm>, MatchSource),
1625     /// A closure (e.g., `move |a, b, c| {a + b + c}`).
1626     ///
1627     /// The `Span` is the argument block `|...|`.
1628     ///
1629     /// This may also be a generator literal or an `async block` as indicated by the
1630     /// `Option<Movability>`.
1631     Closure(CaptureBy, P<FnDecl>, BodyId, Span, Option<Movability>),
1632     /// A block (e.g., `'label: { ... }`).
1633     Block(P<Block>, Option<Label>),
1634
1635     /// An assignment (e.g., `a = foo()`).
1636     Assign(P<Expr>, P<Expr>),
1637     /// An assignment with an operator.
1638     ///
1639     /// E.g., `a += 1`.
1640     AssignOp(BinOp, P<Expr>, P<Expr>),
1641     /// Access of a named (e.g., `obj.foo`) or unnamed (e.g., `obj.0`) struct or tuple field.
1642     Field(P<Expr>, Ident),
1643     /// An indexing operation (`foo[2]`).
1644     Index(P<Expr>, P<Expr>),
1645
1646     /// Path to a definition, possibly containing lifetime or type parameters.
1647     Path(QPath),
1648
1649     /// A referencing operation (i.e., `&a` or `&mut a`).
1650     AddrOf(Mutability, P<Expr>),
1651     /// A `break`, with an optional label to break.
1652     Break(Destination, Option<P<Expr>>),
1653     /// A `continue`, with an optional label.
1654     Continue(Destination),
1655     /// A `return`, with an optional value to be returned.
1656     Ret(Option<P<Expr>>),
1657
1658     /// Inline assembly (from `asm!`), with its outputs and inputs.
1659     InlineAsm(P<InlineAsm>),
1660
1661     /// A struct or struct-like variant literal expression.
1662     ///
1663     /// E.g., `Foo {x: 1, y: 2}`, or `Foo {x: 1, .. base}`,
1664     /// where `base` is the `Option<Expr>`.
1665     Struct(P<QPath>, HirVec<Field>, Option<P<Expr>>),
1666
1667     /// An array literal constructed from one repeated element.
1668     ///
1669     /// E.g., `[1; 5]`. The first expression is the element
1670     /// to be repeated; the second is the number of times to repeat it.
1671     Repeat(P<Expr>, AnonConst),
1672
1673     /// A suspension point for generators (i.e., `yield <expr>`).
1674     Yield(P<Expr>, YieldSource),
1675
1676     /// A placeholder for an expression that wasn't syntactically well formed in some way.
1677     Err,
1678 }
1679
1680 /// Represents an optionally `Self`-qualified value/type path or associated extension.
1681 ///
1682 /// To resolve the path to a `DefId`, call [`qpath_res`].
1683 ///
1684 /// [`qpath_res`]: ../ty/struct.TypeckTables.html#method.qpath_res
1685 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1686 pub enum QPath {
1687     /// Path to a definition, optionally "fully-qualified" with a `Self`
1688     /// type, if the path points to an associated item in a trait.
1689     ///
1690     /// E.g., an unqualified path like `Clone::clone` has `None` for `Self`,
1691     /// while `<Vec<T> as Clone>::clone` has `Some(Vec<T>)` for `Self`,
1692     /// even though they both have the same two-segment `Clone::clone` `Path`.
1693     Resolved(Option<P<Ty>>, P<Path>),
1694
1695     /// Type-related paths (e.g., `<T>::default` or `<T>::Output`).
1696     /// Will be resolved by type-checking to an associated item.
1697     ///
1698     /// UFCS source paths can desugar into this, with `Vec::new` turning into
1699     /// `<Vec>::new`, and `T::X::Y::method` into `<<<T>::X>::Y>::method`,
1700     /// the `X` and `Y` nodes each being a `TyKind::Path(QPath::TypeRelative(..))`.
1701     TypeRelative(P<Ty>, P<PathSegment>)
1702 }
1703
1704 /// Hints at the original code for a let statement.
1705 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, Debug, HashStable)]
1706 pub enum LocalSource {
1707     /// A `match _ { .. }`.
1708     Normal,
1709     /// A desugared `for _ in _ { .. }` loop.
1710     ForLoopDesugar,
1711     /// When lowering async functions, we create locals within the `async move` so that
1712     /// all parameters are dropped after the future is polled.
1713     ///
1714     /// ```ignore (pseudo-Rust)
1715     /// async fn foo(<pattern> @ x: Type) {
1716     ///     async move {
1717     ///         let <pattern> = x;
1718     ///     }
1719     /// }
1720     /// ```
1721     AsyncFn,
1722     /// A desugared `<expr>.await`.
1723     AwaitDesugar,
1724 }
1725
1726 /// Hints at the original code for a `match _ { .. }`.
1727 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, HashStable)]
1728 pub enum MatchSource {
1729     /// A `match _ { .. }`.
1730     Normal,
1731     /// An `if _ { .. }` (optionally with `else { .. }`).
1732     IfDesugar {
1733         contains_else_clause: bool,
1734     },
1735     /// An `if let _ = _ { .. }` (optionally with `else { .. }`).
1736     IfLetDesugar {
1737         contains_else_clause: bool,
1738     },
1739     /// A `while _ { .. }` (which was desugared to a `loop { match _ { .. } }`).
1740     WhileDesugar,
1741     /// A `while let _ = _ { .. }` (which was desugared to a
1742     /// `loop { match _ { .. } }`).
1743     WhileLetDesugar,
1744     /// A desugared `for _ in _ { .. }` loop.
1745     ForLoopDesugar,
1746     /// A desugared `?` operator.
1747     TryDesugar,
1748     /// A desugared `<expr>.await`.
1749     AwaitDesugar,
1750 }
1751
1752 impl MatchSource {
1753     pub fn name(self) -> &'static str {
1754         use MatchSource::*;
1755         match self {
1756             Normal => "match",
1757             IfDesugar { .. } | IfLetDesugar { .. } => "if",
1758             WhileDesugar | WhileLetDesugar => "while",
1759             ForLoopDesugar => "for",
1760             TryDesugar => "?",
1761             AwaitDesugar => ".await",
1762         }
1763     }
1764 }
1765
1766 /// The loop type that yielded an `ExprKind::Loop`.
1767 #[derive(Copy, Clone, PartialEq, RustcEncodable, RustcDecodable, Debug, HashStable)]
1768 pub enum LoopSource {
1769     /// A `loop { .. }` loop.
1770     Loop,
1771     /// A `while _ { .. }` loop.
1772     While,
1773     /// A `while let _ = _ { .. }` loop.
1774     WhileLet,
1775     /// A `for _ in _ { .. }` loop.
1776     ForLoop,
1777 }
1778
1779 impl LoopSource {
1780     pub fn name(self) -> &'static str {
1781         match self {
1782             LoopSource::Loop => "loop",
1783             LoopSource::While | LoopSource::WhileLet => "while",
1784             LoopSource::ForLoop => "for",
1785         }
1786     }
1787 }
1788
1789 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, Debug, HashStable)]
1790 pub enum LoopIdError {
1791     OutsideLoopScope,
1792     UnlabeledCfInWhileCondition,
1793     UnresolvedLabel,
1794 }
1795
1796 impl fmt::Display for LoopIdError {
1797     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1798         f.write_str(match self {
1799             LoopIdError::OutsideLoopScope => "not inside loop scope",
1800             LoopIdError::UnlabeledCfInWhileCondition =>
1801                 "unlabeled control flow (break or continue) in while condition",
1802             LoopIdError::UnresolvedLabel => "label not found",
1803         })
1804     }
1805 }
1806
1807 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, Debug, HashStable)]
1808 pub struct Destination {
1809     // This is `Some(_)` iff there is an explicit user-specified `label
1810     pub label: Option<Label>,
1811
1812     // These errors are caught and then reported during the diagnostics pass in
1813     // librustc_passes/loops.rs
1814     pub target_id: Result<HirId, LoopIdError>,
1815 }
1816
1817 /// The yield kind that caused an `ExprKind::Yield`.
1818 #[derive(Copy, Clone, PartialEq, Eq, Debug, RustcEncodable, RustcDecodable, HashStable)]
1819 pub enum YieldSource {
1820     /// An `<expr>.await`.
1821     Await,
1822     /// A plain `yield`.
1823     Yield,
1824 }
1825
1826 impl fmt::Display for YieldSource {
1827     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1828         f.write_str(match self {
1829             YieldSource::Await => "`await`",
1830             YieldSource::Yield => "`yield`",
1831         })
1832     }
1833 }
1834
1835 // N.B., if you change this, you'll probably want to change the corresponding
1836 // type structure in middle/ty.rs as well.
1837 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1838 pub struct MutTy {
1839     pub ty: P<Ty>,
1840     pub mutbl: Mutability,
1841 }
1842
1843 /// Represents a function's signature in a trait declaration,
1844 /// trait implementation, or a free function.
1845 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1846 pub struct FnSig {
1847     pub header: FnHeader,
1848     pub decl: P<FnDecl>,
1849 }
1850
1851 // The bodies for items are stored "out of line", in a separate
1852 // hashmap in the `Crate`. Here we just record the node-id of the item
1853 // so it can fetched later.
1854 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, RustcEncodable, RustcDecodable, Debug)]
1855 pub struct TraitItemId {
1856     pub hir_id: HirId,
1857 }
1858
1859 /// Represents an item declaration within a trait declaration,
1860 /// possibly including a default implementation. A trait item is
1861 /// either required (meaning it doesn't have an implementation, just a
1862 /// signature) or provided (meaning it has a default implementation).
1863 #[derive(RustcEncodable, RustcDecodable, Debug)]
1864 pub struct TraitItem {
1865     pub ident: Ident,
1866     pub hir_id: HirId,
1867     pub attrs: HirVec<Attribute>,
1868     pub generics: Generics,
1869     pub kind: TraitItemKind,
1870     pub span: Span,
1871 }
1872
1873 /// Represents a trait method's body (or just argument names).
1874 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1875 pub enum TraitMethod {
1876     /// No default body in the trait, just a signature.
1877     Required(HirVec<Ident>),
1878
1879     /// Both signature and body are provided in the trait.
1880     Provided(BodyId),
1881 }
1882
1883 /// Represents a trait method or associated constant or type
1884 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1885 pub enum TraitItemKind {
1886     /// An associated constant with an optional value (otherwise `impl`s must contain a value).
1887     Const(P<Ty>, Option<BodyId>),
1888     /// A method with an optional body.
1889     Method(FnSig, TraitMethod),
1890     /// An associated type with (possibly empty) bounds and optional concrete
1891     /// type.
1892     Type(GenericBounds, Option<P<Ty>>),
1893 }
1894
1895 // The bodies for items are stored "out of line", in a separate
1896 // hashmap in the `Crate`. Here we just record the node-id of the item
1897 // so it can fetched later.
1898 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, RustcEncodable, RustcDecodable, Debug)]
1899 pub struct ImplItemId {
1900     pub hir_id: HirId,
1901 }
1902
1903 /// Represents anything within an `impl` block.
1904 #[derive(RustcEncodable, RustcDecodable, Debug)]
1905 pub struct ImplItem {
1906     pub ident: Ident,
1907     pub hir_id: HirId,
1908     pub vis: Visibility,
1909     pub defaultness: Defaultness,
1910     pub attrs: HirVec<Attribute>,
1911     pub generics: Generics,
1912     pub kind: ImplItemKind,
1913     pub span: Span,
1914 }
1915
1916 /// Represents various kinds of content within an `impl`.
1917 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1918 pub enum ImplItemKind {
1919     /// An associated constant of the given type, set to the constant result
1920     /// of the expression.
1921     Const(P<Ty>, BodyId),
1922     /// A method implementation with the given signature and body.
1923     Method(FnSig, BodyId),
1924     /// An associated type.
1925     TyAlias(P<Ty>),
1926     /// An associated `type = impl Trait`.
1927     OpaqueTy(GenericBounds),
1928 }
1929
1930 /// Bind a type to an associated type (i.e., `A = Foo`).
1931 ///
1932 /// Bindings like `A: Debug` are represented as a special type `A =
1933 /// $::Debug` that is understood by the astconv code.
1934 ///
1935 /// FIXME(alexreg): why have a separate type for the binding case,
1936 /// wouldn't it be better to make the `ty` field an enum like the
1937 /// following?
1938 ///
1939 /// ```
1940 /// enum TypeBindingKind {
1941 ///    Equals(...),
1942 ///    Binding(...),
1943 /// }
1944 /// ```
1945 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1946 pub struct TypeBinding {
1947     pub hir_id: HirId,
1948     #[stable_hasher(project(name))]
1949     pub ident: Ident,
1950     pub kind: TypeBindingKind,
1951     pub span: Span,
1952 }
1953
1954 // Represents the two kinds of type bindings.
1955 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
1956 pub enum TypeBindingKind {
1957     /// E.g., `Foo<Bar: Send>`.
1958     Constraint {
1959         bounds: HirVec<GenericBound>,
1960     },
1961     /// E.g., `Foo<Bar = ()>`.
1962     Equality {
1963         ty: P<Ty>,
1964     },
1965 }
1966
1967 impl TypeBinding {
1968     pub fn ty(&self) -> &Ty {
1969         match self.kind {
1970             TypeBindingKind::Equality { ref ty } => ty,
1971             _ => bug!("expected equality type binding for parenthesized generic args"),
1972         }
1973     }
1974 }
1975
1976 #[derive(RustcEncodable, RustcDecodable)]
1977 pub struct Ty {
1978     pub hir_id: HirId,
1979     pub kind: TyKind,
1980     pub span: Span,
1981 }
1982
1983 impl fmt::Debug for Ty {
1984     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1985         write!(f, "type({})",
1986                print::to_string(print::NO_ANN, |s| s.print_type(self)))
1987     }
1988 }
1989
1990 /// Not represented directly in the AST; referred to by name through a `ty_path`.
1991 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, HashStable)]
1992 pub enum PrimTy {
1993     Int(IntTy),
1994     Uint(UintTy),
1995     Float(FloatTy),
1996     Str,
1997     Bool,
1998     Char,
1999 }
2000
2001 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2002 pub struct BareFnTy {
2003     pub unsafety: Unsafety,
2004     pub abi: Abi,
2005     pub generic_params: HirVec<GenericParam>,
2006     pub decl: P<FnDecl>,
2007     pub param_names: HirVec<Ident>,
2008 }
2009
2010 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2011 pub struct OpaqueTy {
2012     pub generics: Generics,
2013     pub bounds: GenericBounds,
2014     pub impl_trait_fn: Option<DefId>,
2015     pub origin: OpaqueTyOrigin,
2016 }
2017
2018 /// From whence the opaque type came.
2019 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, Debug, HashStable)]
2020 pub enum OpaqueTyOrigin {
2021     /// `type Foo = impl Trait;`
2022     TypeAlias,
2023     /// `-> impl Trait`
2024     FnReturn,
2025     /// `async fn`
2026     AsyncFn,
2027 }
2028
2029 /// The various kinds of types recognized by the compiler.
2030 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2031 pub enum TyKind {
2032     /// A variable length slice (i.e., `[T]`).
2033     Slice(P<Ty>),
2034     /// A fixed length array (i.e., `[T; n]`).
2035     Array(P<Ty>, AnonConst),
2036     /// A raw pointer (i.e., `*const T` or `*mut T`).
2037     Ptr(MutTy),
2038     /// A reference (i.e., `&'a T` or `&'a mut T`).
2039     Rptr(Lifetime, MutTy),
2040     /// A bare function (e.g., `fn(usize) -> bool`).
2041     BareFn(P<BareFnTy>),
2042     /// The never type (`!`).
2043     Never,
2044     /// A tuple (`(A, B, C, D, ...)`).
2045     Tup(HirVec<Ty>),
2046     /// A path to a type definition (`module::module::...::Type`), or an
2047     /// associated type (e.g., `<Vec<T> as Trait>::Type` or `<T>::Target`).
2048     ///
2049     /// Type parameters may be stored in each `PathSegment`.
2050     Path(QPath),
2051     /// A type definition itself. This is currently only used for the `type Foo = impl Trait`
2052     /// item that `impl Trait` in return position desugars to.
2053     ///
2054     /// The generic argument list contains the lifetimes (and in the future possibly parameters)
2055     /// that are actually bound on the `impl Trait`.
2056     Def(ItemId, HirVec<GenericArg>),
2057     /// A trait object type `Bound1 + Bound2 + Bound3`
2058     /// where `Bound` is a trait or a lifetime.
2059     TraitObject(HirVec<PolyTraitRef>, Lifetime),
2060     /// Unused for now.
2061     Typeof(AnonConst),
2062     /// `TyKind::Infer` means the type should be inferred instead of it having been
2063     /// specified. This can appear anywhere in a type.
2064     Infer,
2065     /// Placeholder for a type that has failed to be defined.
2066     Err,
2067 }
2068
2069 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, Debug, HashStable, PartialEq)]
2070 pub struct InlineAsmOutput {
2071     pub constraint: Symbol,
2072     pub is_rw: bool,
2073     pub is_indirect: bool,
2074     pub span: Span,
2075 }
2076
2077 // NOTE(eddyb) This is used within MIR as well, so unlike the rest of the HIR,
2078 // it needs to be `Clone` and use plain `Vec<T>` instead of `HirVec<T>`.
2079 #[derive(Clone, RustcEncodable, RustcDecodable, Debug, HashStable, PartialEq)]
2080 pub struct InlineAsmInner {
2081     pub asm: Symbol,
2082     pub asm_str_style: StrStyle,
2083     pub outputs: Vec<InlineAsmOutput>,
2084     pub inputs: Vec<Symbol>,
2085     pub clobbers: Vec<Symbol>,
2086     pub volatile: bool,
2087     pub alignstack: bool,
2088     pub dialect: AsmDialect,
2089 }
2090
2091 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2092 pub struct InlineAsm {
2093     pub inner: InlineAsmInner,
2094     pub outputs_exprs: HirVec<Expr>,
2095     pub inputs_exprs: HirVec<Expr>,
2096 }
2097
2098 /// Represents a parameter in a function header.
2099 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2100 pub struct Param {
2101     pub attrs: HirVec<Attribute>,
2102     pub hir_id: HirId,
2103     pub pat: P<Pat>,
2104     pub span: Span,
2105 }
2106
2107 /// Represents the header (not the body) of a function declaration.
2108 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2109 pub struct FnDecl {
2110     /// The types of the function's parameters.
2111     ///
2112     /// Additional argument data is stored in the function's [body](Body::parameters).
2113     pub inputs: HirVec<Ty>,
2114     pub output: FunctionRetTy,
2115     pub c_variadic: bool,
2116     /// Does the function have an implicit self?
2117     pub implicit_self: ImplicitSelfKind,
2118 }
2119
2120 /// Represents what type of implicit self a function has, if any.
2121 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, Debug, HashStable)]
2122 pub enum ImplicitSelfKind {
2123     /// Represents a `fn x(self);`.
2124     Imm,
2125     /// Represents a `fn x(mut self);`.
2126     Mut,
2127     /// Represents a `fn x(&self);`.
2128     ImmRef,
2129     /// Represents a `fn x(&mut self);`.
2130     MutRef,
2131     /// Represents when a function does not have a self argument or
2132     /// when a function has a `self: X` argument.
2133     None
2134 }
2135
2136 impl ImplicitSelfKind {
2137     /// Does this represent an implicit self?
2138     pub fn has_implicit_self(&self) -> bool {
2139         match *self {
2140             ImplicitSelfKind::None => false,
2141             _ => true,
2142         }
2143     }
2144 }
2145
2146 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, HashStable,
2147          Ord, RustcEncodable, RustcDecodable, Debug)]
2148 pub enum IsAsync {
2149     Async,
2150     NotAsync,
2151 }
2152
2153 #[derive(Copy, Clone, PartialEq, RustcEncodable, RustcDecodable, Debug, HashStable)]
2154 pub enum Defaultness {
2155     Default { has_value: bool },
2156     Final,
2157 }
2158
2159 impl Defaultness {
2160     pub fn has_value(&self) -> bool {
2161         match *self {
2162             Defaultness::Default { has_value, .. } => has_value,
2163             Defaultness::Final => true,
2164         }
2165     }
2166
2167     pub fn is_final(&self) -> bool {
2168         *self == Defaultness::Final
2169     }
2170
2171     pub fn is_default(&self) -> bool {
2172         match *self {
2173             Defaultness::Default { .. } => true,
2174             _ => false,
2175         }
2176     }
2177 }
2178
2179 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2180 pub enum FunctionRetTy {
2181     /// Return type is not specified.
2182     ///
2183     /// Functions default to `()` and
2184     /// closures default to inference. Span points to where return
2185     /// type would be inserted.
2186     DefaultReturn(Span),
2187     /// Everything else.
2188     Return(P<Ty>),
2189 }
2190
2191 impl fmt::Display for FunctionRetTy {
2192     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2193         match self {
2194             Return(ref ty) => print::to_string(print::NO_ANN, |s| s.print_type(ty)).fmt(f),
2195             DefaultReturn(_) => "()".fmt(f),
2196         }
2197     }
2198 }
2199
2200 impl FunctionRetTy {
2201     pub fn span(&self) -> Span {
2202         match *self {
2203             DefaultReturn(span) => span,
2204             Return(ref ty) => ty.span,
2205         }
2206     }
2207 }
2208
2209 #[derive(RustcEncodable, RustcDecodable, Debug)]
2210 pub struct Mod {
2211     /// A span from the first token past `{` to the last token until `}`.
2212     /// For `mod foo;`, the inner span ranges from the first token
2213     /// to the last token in the external file.
2214     pub inner: Span,
2215     pub item_ids: HirVec<ItemId>,
2216 }
2217
2218 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2219 pub struct ForeignMod {
2220     pub abi: Abi,
2221     pub items: HirVec<ForeignItem>,
2222 }
2223
2224 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2225 pub struct GlobalAsm {
2226     pub asm: Symbol,
2227 }
2228
2229 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2230 pub struct EnumDef {
2231     pub variants: HirVec<Variant>,
2232 }
2233
2234 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2235 pub struct Variant {
2236     /// Name of the variant.
2237     #[stable_hasher(project(name))]
2238     pub ident: Ident,
2239     /// Attributes of the variant.
2240     pub attrs: HirVec<Attribute>,
2241     /// Id of the variant (not the constructor, see `VariantData::ctor_hir_id()`).
2242     pub id: HirId,
2243     /// Fields and constructor id of the variant.
2244     pub data: VariantData,
2245     /// Explicit discriminant (e.g., `Foo = 1`).
2246     pub disr_expr: Option<AnonConst>,
2247     /// Span
2248     pub span: Span
2249 }
2250
2251 #[derive(Copy, Clone, PartialEq, RustcEncodable, RustcDecodable, Debug, HashStable)]
2252 pub enum UseKind {
2253     /// One import, e.g., `use foo::bar` or `use foo::bar as baz`.
2254     /// Also produced for each element of a list `use`, e.g.
2255     /// `use foo::{a, b}` lowers to `use foo::a; use foo::b;`.
2256     Single,
2257
2258     /// Glob import, e.g., `use foo::*`.
2259     Glob,
2260
2261     /// Degenerate list import, e.g., `use foo::{a, b}` produces
2262     /// an additional `use foo::{}` for performing checks such as
2263     /// unstable feature gating. May be removed in the future.
2264     ListStem,
2265 }
2266
2267 /// References to traits in impls.
2268 ///
2269 /// `resolve` maps each `TraitRef`'s `ref_id` to its defining trait; that's all
2270 /// that the `ref_id` is for. Note that `ref_id`'s value is not the `HirId` of the
2271 /// trait being referred to but just a unique `HirId` that serves as a key
2272 /// within the resolution map.
2273 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2274 pub struct TraitRef {
2275     pub path: P<Path>,
2276     // Don't hash the `ref_id`. It is tracked via the thing it is used to access.
2277     #[stable_hasher(ignore)]
2278     pub hir_ref_id: HirId,
2279 }
2280
2281 impl TraitRef {
2282     /// Gets the `DefId` of the referenced trait. It _must_ actually be a trait or trait alias.
2283     pub fn trait_def_id(&self) -> DefId {
2284         match self.path.res {
2285             Res::Def(DefKind::Trait, did) => did,
2286             Res::Def(DefKind::TraitAlias, did) => did,
2287             Res::Err => {
2288                 FatalError.raise();
2289             }
2290             _ => unreachable!(),
2291         }
2292     }
2293 }
2294
2295 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2296 pub struct PolyTraitRef {
2297     /// The `'a` in `<'a> Foo<&'a T>`.
2298     pub bound_generic_params: HirVec<GenericParam>,
2299
2300     /// The `Foo<&'a T>` in `<'a> Foo<&'a T>`.
2301     pub trait_ref: TraitRef,
2302
2303     pub span: Span,
2304 }
2305
2306 pub type Visibility = Spanned<VisibilityKind>;
2307
2308 #[derive(RustcEncodable, RustcDecodable, Debug)]
2309 pub enum VisibilityKind {
2310     Public,
2311     Crate(CrateSugar),
2312     Restricted { path: P<Path>, hir_id: HirId },
2313     Inherited,
2314 }
2315
2316 impl VisibilityKind {
2317     pub fn is_pub(&self) -> bool {
2318         match *self {
2319             VisibilityKind::Public => true,
2320             _ => false
2321         }
2322     }
2323
2324     pub fn is_pub_restricted(&self) -> bool {
2325         match *self {
2326             VisibilityKind::Public |
2327             VisibilityKind::Inherited => false,
2328             VisibilityKind::Crate(..) |
2329             VisibilityKind::Restricted { .. } => true,
2330         }
2331     }
2332
2333     pub fn descr(&self) -> &'static str {
2334         match *self {
2335             VisibilityKind::Public => "public",
2336             VisibilityKind::Inherited => "private",
2337             VisibilityKind::Crate(..) => "crate-visible",
2338             VisibilityKind::Restricted { .. } => "restricted",
2339         }
2340     }
2341 }
2342
2343 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2344 pub struct StructField {
2345     pub span: Span,
2346     #[stable_hasher(project(name))]
2347     pub ident: Ident,
2348     pub vis: Visibility,
2349     pub hir_id: HirId,
2350     pub ty: P<Ty>,
2351     pub attrs: HirVec<Attribute>,
2352 }
2353
2354 impl StructField {
2355     // Still necessary in couple of places
2356     pub fn is_positional(&self) -> bool {
2357         let first = self.ident.as_str().as_bytes()[0];
2358         first >= b'0' && first <= b'9'
2359     }
2360 }
2361
2362 /// Fields and constructor IDs of enum variants and structs.
2363 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2364 pub enum VariantData {
2365     /// A struct variant.
2366     ///
2367     /// E.g., `Bar { .. }` as in `enum Foo { Bar { .. } }`.
2368     Struct(HirVec<StructField>, /* recovered */ bool),
2369     /// A tuple variant.
2370     ///
2371     /// E.g., `Bar(..)` as in `enum Foo { Bar(..) }`.
2372     Tuple(HirVec<StructField>, HirId),
2373     /// A unit variant.
2374     ///
2375     /// E.g., `Bar = ..` as in `enum Foo { Bar = .. }`.
2376     Unit(HirId),
2377 }
2378
2379 impl VariantData {
2380     /// Return the fields of this variant.
2381     pub fn fields(&self) -> &[StructField] {
2382         match *self {
2383             VariantData::Struct(ref fields, ..) | VariantData::Tuple(ref fields, ..) => fields,
2384             _ => &[],
2385         }
2386     }
2387
2388     /// Return the `HirId` of this variant's constructor, if it has one.
2389     pub fn ctor_hir_id(&self) -> Option<HirId> {
2390         match *self {
2391             VariantData::Struct(_, _) => None,
2392             VariantData::Tuple(_, hir_id) | VariantData::Unit(hir_id) => Some(hir_id),
2393         }
2394     }
2395 }
2396
2397 // The bodies for items are stored "out of line", in a separate
2398 // hashmap in the `Crate`. Here we just record the node-id of the item
2399 // so it can fetched later.
2400 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, Debug)]
2401 pub struct ItemId {
2402     pub id: HirId,
2403 }
2404
2405 /// An item
2406 ///
2407 /// The name might be a dummy name in case of anonymous items
2408 #[derive(RustcEncodable, RustcDecodable, Debug)]
2409 pub struct Item {
2410     pub ident: Ident,
2411     pub hir_id: HirId,
2412     pub attrs: HirVec<Attribute>,
2413     pub kind: ItemKind,
2414     pub vis: Visibility,
2415     pub span: Span,
2416 }
2417
2418 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, Debug, HashStable)]
2419 pub struct FnHeader {
2420     pub unsafety: Unsafety,
2421     pub constness: Constness,
2422     pub asyncness: IsAsync,
2423     pub abi: Abi,
2424 }
2425
2426 impl FnHeader {
2427     pub fn is_const(&self) -> bool {
2428         match &self.constness {
2429             Constness::Const => true,
2430             _ => false,
2431         }
2432     }
2433 }
2434
2435 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2436 pub enum ItemKind {
2437     /// An `extern crate` item, with optional *original* crate name if the crate was renamed.
2438     ///
2439     /// E.g., `extern crate foo` or `extern crate foo_bar as foo`.
2440     ExternCrate(Option<Name>),
2441
2442     /// `use foo::bar::*;` or `use foo::bar::baz as quux;`
2443     ///
2444     /// or just
2445     ///
2446     /// `use foo::bar::baz;` (with `as baz` implicitly on the right).
2447     Use(P<Path>, UseKind),
2448
2449     /// A `static` item.
2450     Static(P<Ty>, Mutability, BodyId),
2451     /// A `const` item.
2452     Const(P<Ty>, BodyId),
2453     /// A function declaration.
2454     Fn(FnSig, Generics, BodyId),
2455     /// A module.
2456     Mod(Mod),
2457     /// An external module, e.g. `extern { .. }`.
2458     ForeignMod(ForeignMod),
2459     /// Module-level inline assembly (from `global_asm!`).
2460     GlobalAsm(P<GlobalAsm>),
2461     /// A type alias, e.g., `type Foo = Bar<u8>`.
2462     TyAlias(P<Ty>, Generics),
2463     /// An opaque `impl Trait` type alias, e.g., `type Foo = impl Bar;`.
2464     OpaqueTy(OpaqueTy),
2465     /// An enum definition, e.g., `enum Foo<A, B> {C<A>, D<B>}`.
2466     Enum(EnumDef, Generics),
2467     /// A struct definition, e.g., `struct Foo<A> {x: A}`.
2468     Struct(VariantData, Generics),
2469     /// A union definition, e.g., `union Foo<A, B> {x: A, y: B}`.
2470     Union(VariantData, Generics),
2471     /// A trait definition.
2472     Trait(IsAuto, Unsafety, Generics, GenericBounds, HirVec<TraitItemRef>),
2473     /// A trait alias.
2474     TraitAlias(Generics, GenericBounds),
2475
2476     /// An implementation, e.g., `impl<A> Trait for Foo { .. }`.
2477     Impl(Unsafety,
2478          ImplPolarity,
2479          Defaultness,
2480          Generics,
2481          Option<TraitRef>, // (optional) trait this impl implements
2482          P<Ty>, // self
2483          HirVec<ImplItemRef>),
2484 }
2485
2486 impl ItemKind {
2487     pub fn descriptive_variant(&self) -> &str {
2488         match *self {
2489             ItemKind::ExternCrate(..) => "extern crate",
2490             ItemKind::Use(..) => "use",
2491             ItemKind::Static(..) => "static item",
2492             ItemKind::Const(..) => "constant item",
2493             ItemKind::Fn(..) => "function",
2494             ItemKind::Mod(..) => "module",
2495             ItemKind::ForeignMod(..) => "foreign module",
2496             ItemKind::GlobalAsm(..) => "global asm",
2497             ItemKind::TyAlias(..) => "type alias",
2498             ItemKind::OpaqueTy(..) => "opaque type",
2499             ItemKind::Enum(..) => "enum",
2500             ItemKind::Struct(..) => "struct",
2501             ItemKind::Union(..) => "union",
2502             ItemKind::Trait(..) => "trait",
2503             ItemKind::TraitAlias(..) => "trait alias",
2504             ItemKind::Impl(..) => "impl",
2505         }
2506     }
2507
2508     pub fn adt_kind(&self) -> Option<AdtKind> {
2509         match *self {
2510             ItemKind::Struct(..) => Some(AdtKind::Struct),
2511             ItemKind::Union(..) => Some(AdtKind::Union),
2512             ItemKind::Enum(..) => Some(AdtKind::Enum),
2513             _ => None,
2514         }
2515     }
2516
2517     pub fn generics(&self) -> Option<&Generics> {
2518         Some(match *self {
2519             ItemKind::Fn(_, ref generics, _) |
2520             ItemKind::TyAlias(_, ref generics) |
2521             ItemKind::OpaqueTy(OpaqueTy { ref generics, impl_trait_fn: None, .. }) |
2522             ItemKind::Enum(_, ref generics) |
2523             ItemKind::Struct(_, ref generics) |
2524             ItemKind::Union(_, ref generics) |
2525             ItemKind::Trait(_, _, ref generics, _, _) |
2526             ItemKind::Impl(_, _, _, ref generics, _, _, _)=> generics,
2527             _ => return None
2528         })
2529     }
2530 }
2531
2532 /// A reference from an trait to one of its associated items. This
2533 /// contains the item's id, naturally, but also the item's name and
2534 /// some other high-level details (like whether it is an associated
2535 /// type or method, and whether it is public). This allows other
2536 /// passes to find the impl they want without loading the ID (which
2537 /// means fewer edges in the incremental compilation graph).
2538 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2539 pub struct TraitItemRef {
2540     pub id: TraitItemId,
2541     #[stable_hasher(project(name))]
2542     pub ident: Ident,
2543     pub kind: AssocItemKind,
2544     pub span: Span,
2545     pub defaultness: Defaultness,
2546 }
2547
2548 /// A reference from an impl to one of its associated items. This
2549 /// contains the item's ID, naturally, but also the item's name and
2550 /// some other high-level details (like whether it is an associated
2551 /// type or method, and whether it is public). This allows other
2552 /// passes to find the impl they want without loading the ID (which
2553 /// means fewer edges in the incremental compilation graph).
2554 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2555 pub struct ImplItemRef {
2556     pub id: ImplItemId,
2557     #[stable_hasher(project(name))]
2558     pub ident: Ident,
2559     pub kind: AssocItemKind,
2560     pub span: Span,
2561     pub vis: Visibility,
2562     pub defaultness: Defaultness,
2563 }
2564
2565 #[derive(Copy, Clone, PartialEq, RustcEncodable, RustcDecodable, Debug, HashStable)]
2566 pub enum AssocItemKind {
2567     Const,
2568     Method { has_self: bool },
2569     Type,
2570     OpaqueTy,
2571 }
2572
2573 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2574 pub struct ForeignItem {
2575     #[stable_hasher(project(name))]
2576     pub ident: Ident,
2577     pub attrs: HirVec<Attribute>,
2578     pub kind: ForeignItemKind,
2579     pub hir_id: HirId,
2580     pub span: Span,
2581     pub vis: Visibility,
2582 }
2583
2584 /// An item within an `extern` block.
2585 #[derive(RustcEncodable, RustcDecodable, Debug, HashStable)]
2586 pub enum ForeignItemKind {
2587     /// A foreign function.
2588     Fn(P<FnDecl>, HirVec<Ident>, Generics),
2589     /// A foreign static item (`static ext: u8`).
2590     Static(P<Ty>, Mutability),
2591     /// A foreign type.
2592     Type,
2593 }
2594
2595 impl ForeignItemKind {
2596     pub fn descriptive_variant(&self) -> &str {
2597         match *self {
2598             ForeignItemKind::Fn(..) => "foreign function",
2599             ForeignItemKind::Static(..) => "foreign static item",
2600             ForeignItemKind::Type => "foreign type",
2601         }
2602     }
2603 }
2604
2605 /// A variable captured by a closure.
2606 #[derive(Debug, Copy, Clone, RustcEncodable, RustcDecodable, HashStable)]
2607 pub struct Upvar {
2608     // First span where it is accessed (there can be multiple).
2609     pub span: Span
2610 }
2611
2612 pub type CaptureModeMap = NodeMap<CaptureBy>;
2613
2614  // The TraitCandidate's import_ids is empty if the trait is defined in the same module, and
2615  // has length > 0 if the trait is found through an chain of imports, starting with the
2616  // import/use statement in the scope where the trait is used.
2617 #[derive(Clone, Debug)]
2618 pub struct TraitCandidate {
2619     pub def_id: DefId,
2620     pub import_ids: SmallVec<[NodeId; 1]>,
2621 }
2622
2623 // Trait method resolution
2624 pub type TraitMap = NodeMap<Vec<TraitCandidate>>;
2625
2626 // Map from the NodeId of a glob import to a list of items which are actually
2627 // imported.
2628 pub type GlobMap = NodeMap<FxHashSet<Name>>;
2629
2630 pub fn provide(providers: &mut Providers<'_>) {
2631     check_attr::provide(providers);
2632     map::provide(providers);
2633     upvars::provide(providers);
2634 }
2635
2636 #[derive(Clone, RustcEncodable, RustcDecodable, HashStable)]
2637 pub struct CodegenFnAttrs {
2638     pub flags: CodegenFnAttrFlags,
2639     /// Parsed representation of the `#[inline]` attribute
2640     pub inline: InlineAttr,
2641     /// Parsed representation of the `#[optimize]` attribute
2642     pub optimize: OptimizeAttr,
2643     /// The `#[export_name = "..."]` attribute, indicating a custom symbol a
2644     /// function should be exported under
2645     pub export_name: Option<Symbol>,
2646     /// The `#[link_name = "..."]` attribute, indicating a custom symbol an
2647     /// imported function should be imported as. Note that `export_name`
2648     /// probably isn't set when this is set, this is for foreign items while
2649     /// `#[export_name]` is for Rust-defined functions.
2650     pub link_name: Option<Symbol>,
2651     /// The `#[link_ordinal = "..."]` attribute, indicating an ordinal an
2652     /// imported function has in the dynamic library. Note that this must not
2653     /// be set when `link_name` is set. This is for foreign items with the
2654     /// "raw-dylib" kind.
2655     pub link_ordinal: Option<usize>,
2656     /// The `#[target_feature(enable = "...")]` attribute and the enabled
2657     /// features (only enabled features are supported right now).
2658     pub target_features: Vec<Symbol>,
2659     /// The `#[linkage = "..."]` attribute and the value we found.
2660     pub linkage: Option<Linkage>,
2661     /// The `#[link_section = "..."]` attribute, or what executable section this
2662     /// should be placed in.
2663     pub link_section: Option<Symbol>,
2664 }
2665
2666 bitflags! {
2667     #[derive(RustcEncodable, RustcDecodable, HashStable)]
2668     pub struct CodegenFnAttrFlags: u32 {
2669         /// `#[cold]`: a hint to LLVM that this function, when called, is never on
2670         /// the hot path.
2671         const COLD                      = 1 << 0;
2672         /// `#[rustc_allocator]`: a hint to LLVM that the pointer returned from this
2673         /// function is never null.
2674         const ALLOCATOR                 = 1 << 1;
2675         /// `#[unwind]`: an indicator that this function may unwind despite what
2676         /// its ABI signature may otherwise imply.
2677         const UNWIND                    = 1 << 2;
2678         /// `#[rust_allocator_nounwind]`, an indicator that an imported FFI
2679         /// function will never unwind. Probably obsolete by recent changes with
2680         /// #[unwind], but hasn't been removed/migrated yet
2681         const RUSTC_ALLOCATOR_NOUNWIND  = 1 << 3;
2682         /// `#[naked]`: an indicator to LLVM that no function prologue/epilogue
2683         /// should be generated.
2684         const NAKED                     = 1 << 4;
2685         /// `#[no_mangle]`: an indicator that the function's name should be the same
2686         /// as its symbol.
2687         const NO_MANGLE                 = 1 << 5;
2688         /// `#[rustc_std_internal_symbol]`: an indicator that this symbol is a
2689         /// "weird symbol" for the standard library in that it has slightly
2690         /// different linkage, visibility, and reachability rules.
2691         const RUSTC_STD_INTERNAL_SYMBOL = 1 << 6;
2692         /// `#[no_debug]`: an indicator that no debugging information should be
2693         /// generated for this function by LLVM.
2694         const NO_DEBUG                  = 1 << 7;
2695         /// `#[thread_local]`: indicates a static is actually a thread local
2696         /// piece of memory
2697         const THREAD_LOCAL              = 1 << 8;
2698         /// `#[used]`: indicates that LLVM can't eliminate this function (but the
2699         /// linker can!).
2700         const USED                      = 1 << 9;
2701         /// `#[ffi_returns_twice]`, indicates that an extern function can return
2702         /// multiple times
2703         const FFI_RETURNS_TWICE         = 1 << 10;
2704         /// `#[track_caller]`: allow access to the caller location
2705         const TRACK_CALLER              = 1 << 11;
2706     }
2707 }
2708
2709 impl CodegenFnAttrs {
2710     pub fn new() -> CodegenFnAttrs {
2711         CodegenFnAttrs {
2712             flags: CodegenFnAttrFlags::empty(),
2713             inline: InlineAttr::None,
2714             optimize: OptimizeAttr::None,
2715             export_name: None,
2716             link_name: None,
2717             link_ordinal: None,
2718             target_features: vec![],
2719             linkage: None,
2720             link_section: None,
2721         }
2722     }
2723
2724     /// Returns `true` if `#[inline]` or `#[inline(always)]` is present.
2725     pub fn requests_inline(&self) -> bool {
2726         match self.inline {
2727             InlineAttr::Hint | InlineAttr::Always => true,
2728             InlineAttr::None | InlineAttr::Never => false,
2729         }
2730     }
2731
2732     /// Returns `true` if it looks like this symbol needs to be exported, for example:
2733     ///
2734     /// * `#[no_mangle]` is present
2735     /// * `#[export_name(...)]` is present
2736     /// * `#[linkage]` is present
2737     pub fn contains_extern_indicator(&self) -> bool {
2738         self.flags.contains(CodegenFnAttrFlags::NO_MANGLE) ||
2739             self.export_name.is_some() ||
2740             match self.linkage {
2741                 // These are private, so make sure we don't try to consider
2742                 // them external.
2743                 None |
2744                 Some(Linkage::Internal) |
2745                 Some(Linkage::Private) => false,
2746                 Some(_) => true,
2747             }
2748     }
2749 }
2750
2751 #[derive(Copy, Clone, Debug)]
2752 pub enum Node<'hir> {
2753     Param(&'hir Param),
2754     Item(&'hir Item),
2755     ForeignItem(&'hir ForeignItem),
2756     TraitItem(&'hir TraitItem),
2757     ImplItem(&'hir ImplItem),
2758     Variant(&'hir Variant),
2759     Field(&'hir StructField),
2760     AnonConst(&'hir AnonConst),
2761     Expr(&'hir Expr),
2762     Stmt(&'hir Stmt),
2763     PathSegment(&'hir PathSegment),
2764     Ty(&'hir Ty),
2765     TraitRef(&'hir TraitRef),
2766     Binding(&'hir Pat),
2767     Pat(&'hir Pat),
2768     Arm(&'hir Arm),
2769     Block(&'hir Block),
2770     Local(&'hir Local),
2771     MacroDef(&'hir MacroDef),
2772
2773     /// `Ctor` refers to the constructor of an enum variant or struct. Only tuple or unit variants
2774     /// with synthesized constructors.
2775     Ctor(&'hir VariantData),
2776
2777     Lifetime(&'hir Lifetime),
2778     GenericParam(&'hir GenericParam),
2779     Visibility(&'hir Visibility),
2780
2781     Crate,
2782 }
2783
2784 impl Node<'_> {
2785     pub fn ident(&self) -> Option<Ident> {
2786         match self {
2787             Node::TraitItem(TraitItem { ident, .. }) |
2788             Node::ImplItem(ImplItem { ident, .. }) |
2789             Node::ForeignItem(ForeignItem { ident, .. }) |
2790             Node::Item(Item { ident, .. }) => Some(*ident),
2791             _ => None,
2792         }
2793     }
2794 }