compiler/rustc_middle/src/hir/map/mod.rs

   1 use self::collector::NodeCollector;
   2
   3 use crate::hir::{Owner, OwnerNodes};
   4 use crate::ty::query::Providers;
   5 use crate::ty::TyCtxt;
   6 use rustc_ast as ast;
   7 use rustc_data_structures::svh::Svh;
   8 use rustc_hir::def::{DefKind, Res};
   9 use rustc_hir::def_id::{CrateNum, DefId, LocalDefId, CRATE_DEF_INDEX, LOCAL_CRATE};
  10 use rustc_hir::definitions::{DefKey, DefPath, Definitions};
  11 use rustc_hir::intravisit;
  12 use rustc_hir::itemlikevisit::ItemLikeVisitor;
  13 use rustc_hir::*;
  14 use rustc_index::vec::IndexVec;
  15 use rustc_span::hygiene::MacroKind;
  16 use rustc_span::source_map::Spanned;
  17 use rustc_span::symbol::{kw, Ident, Symbol};
  18 use rustc_span::Span;
  19 use rustc_target::spec::abi::Abi;
  20
  21 pub mod blocks;
  22 mod collector;
  23
  24 /// Represents an entry and its parent `HirId`.
  25 #[derive(Copy, Clone, Debug)]
  26 pub struct Entry<'hir> {
  27     parent: HirId,
  28     node: Node<'hir>,
  29 }
  30
  31 impl<'hir> Entry<'hir> {
  32     fn parent_node(self) -> Option<HirId> {
  33         match self.node {
  34             Node::Crate(_) | Node::MacroDef(_) => None,
  35             _ => Some(self.parent),
  36         }
  37     }
  38 }
  39
  40 fn fn_decl<'hir>(node: Node<'hir>) -> Option<&'hir FnDecl<'hir>> {
  41     match node {
  42         Node::Item(Item { kind: ItemKind::Fn(sig, _, _), .. })
  43         | Node::TraitItem(TraitItem { kind: TraitItemKind::Fn(sig, _), .. })
  44         | Node::ImplItem(ImplItem { kind: ImplItemKind::Fn(sig, _), .. }) => Some(&sig.decl),
  45         Node::Expr(Expr { kind: ExprKind::Closure(_, fn_decl, ..), .. }) => Some(fn_decl),
  46         _ => None,
  47     }
  48 }
  49
  50 fn fn_sig<'hir>(node: Node<'hir>) -> Option<&'hir FnSig<'hir>> {
  51     match &node {
  52         Node::Item(Item { kind: ItemKind::Fn(sig, _, _), .. })
  53         | Node::TraitItem(TraitItem { kind: TraitItemKind::Fn(sig, _), .. })
  54         | Node::ImplItem(ImplItem { kind: ImplItemKind::Fn(sig, _), .. }) => Some(sig),
  55         _ => None,
  56     }
  57 }
  58
  59 pub fn associated_body<'hir>(node: Node<'hir>) -> Option<BodyId> {
  60     match node {
  61         Node::Item(Item {
  62             kind: ItemKind::Const(_, body) | ItemKind::Static(.., body) | ItemKind::Fn(.., body),
  63             ..
  64         })
  65         | Node::TraitItem(TraitItem {
  66             kind:
  67                 TraitItemKind::Const(_, Some(body)) | TraitItemKind::Fn(_, TraitFn::Provided(body)),
  68             ..
  69         })
  70         | Node::ImplItem(ImplItem {
  71             kind: ImplItemKind::Const(_, body) | ImplItemKind::Fn(_, body),
  72             ..
  73         })
  74         | Node::Expr(Expr { kind: ExprKind::Closure(.., body, _, _), .. }) => Some(*body),
  75
  76         Node::AnonConst(constant) => Some(constant.body),
  77
  78         _ => None,
  79     }
  80 }
  81
  82 fn is_body_owner<'hir>(node: Node<'hir>, hir_id: HirId) -> bool {
  83     match associated_body(node) {
  84         Some(b) => b.hir_id == hir_id,
  85         None => false,
  86     }
  87 }
  88
  89 pub(super) struct HirOwnerData<'hir> {
  90     pub(super) signature: Option<&'hir Owner<'hir>>,
  91     pub(super) with_bodies: Option<&'hir mut OwnerNodes<'hir>>,
  92 }
  93
  94 pub struct IndexedHir<'hir> {
  95     /// The SVH of the local crate.
  96     pub crate_hash: Svh,
  97
  98     pub(super) map: IndexVec<LocalDefId, HirOwnerData<'hir>>,
  99 }
 100
 101 #[derive(Copy, Clone)]
 102 pub struct Map<'hir> {
 103     pub(super) tcx: TyCtxt<'hir>,
 104 }
 105
 106 /// An iterator that walks up the ancestor tree of a given `HirId`.
 107 /// Constructed using `tcx.hir().parent_iter(hir_id)`.
 108 pub struct ParentHirIterator<'map, 'hir> {
 109     current_id: HirId,
 110     map: &'map Map<'hir>,
 111 }
 112
 113 impl<'hir> Iterator for ParentHirIterator<'_, 'hir> {
 114     type Item = (HirId, Node<'hir>);
 115
 116     fn next(&mut self) -> Option<Self::Item> {
 117         if self.current_id == CRATE_HIR_ID {
 118             return None;
 119         }
 120         loop {
 121             // There are nodes that do not have entries, so we need to skip them.
 122             let parent_id = self.map.get_parent_node(self.current_id);
 123
 124             if parent_id == self.current_id {
 125                 self.current_id = CRATE_HIR_ID;
 126                 return None;
 127             }
 128
 129             self.current_id = parent_id;
 130             if let Some(entry) = self.map.find_entry(parent_id) {
 131                 return Some((parent_id, entry.node));
 132             }
 133             // If this `HirId` doesn't have an `Entry`, skip it and look for its `parent_id`.
 134         }
 135     }
 136 }
 137
 138 impl<'hir> Map<'hir> {
 139     pub fn krate(&self) -> &'hir Crate<'hir> {
 140         self.tcx.hir_crate(LOCAL_CRATE)
 141     }
 142
 143     #[inline]
 144     pub fn definitions(&self) -> &'hir Definitions {
 145         &self.tcx.definitions
 146     }
 147
 148     pub fn def_key(&self, def_id: LocalDefId) -> DefKey {
 149         self.tcx.definitions.def_key(def_id)
 150     }
 151
 152     pub fn def_path_from_hir_id(&self, id: HirId) -> Option<DefPath> {
 153         self.opt_local_def_id(id).map(|def_id| self.def_path(def_id))
 154     }
 155
 156     pub fn def_path(&self, def_id: LocalDefId) -> DefPath {
 157         self.tcx.definitions.def_path(def_id)
 158     }
 159
 160     #[inline]
 161     pub fn local_def_id(&self, hir_id: HirId) -> LocalDefId {
 162         self.opt_local_def_id(hir_id).unwrap_or_else(|| {
 163             bug!(
 164                 "local_def_id: no entry for `{:?}`, which has a map of `{:?}`",
 165                 hir_id,
 166                 self.find_entry(hir_id)
 167             )
 168         })
 169     }
 170
 171     #[inline]
 172     pub fn opt_local_def_id(&self, hir_id: HirId) -> Option<LocalDefId> {
 173         self.tcx.definitions.opt_hir_id_to_local_def_id(hir_id)
 174     }
 175
 176     #[inline]
 177     pub fn local_def_id_to_hir_id(&self, def_id: LocalDefId) -> HirId {
 178         self.tcx.definitions.local_def_id_to_hir_id(def_id)
 179     }
 180
 181     #[inline]
 182     pub fn opt_local_def_id_to_hir_id(&self, def_id: LocalDefId) -> Option<HirId> {
 183         self.tcx.definitions.opt_local_def_id_to_hir_id(def_id)
 184     }
 185
 186     pub fn def_kind(&self, local_def_id: LocalDefId) -> DefKind {
 187         // FIXME(eddyb) support `find` on the crate root.
 188         if local_def_id.to_def_id().index == CRATE_DEF_INDEX {
 189             return DefKind::Mod;
 190         }
 191
 192         let hir_id = self.local_def_id_to_hir_id(local_def_id);
 193         match self.get(hir_id) {
 194             Node::Item(item) => match item.kind {
 195                 ItemKind::Static(..) => DefKind::Static,
 196                 ItemKind::Const(..) => DefKind::Const,
 197                 ItemKind::Fn(..) => DefKind::Fn,
 198                 ItemKind::Mod(..) => DefKind::Mod,
 199                 ItemKind::OpaqueTy(..) => DefKind::OpaqueTy,
 200                 ItemKind::TyAlias(..) => DefKind::TyAlias,
 201                 ItemKind::Enum(..) => DefKind::Enum,
 202                 ItemKind::Struct(..) => DefKind::Struct,
 203                 ItemKind::Union(..) => DefKind::Union,
 204                 ItemKind::Trait(..) => DefKind::Trait,
 205                 ItemKind::TraitAlias(..) => DefKind::TraitAlias,
 206                 ItemKind::ExternCrate(_) => DefKind::ExternCrate,
 207                 ItemKind::Use(..) => DefKind::Use,
 208                 ItemKind::ForeignMod(..) => DefKind::ForeignMod,
 209                 ItemKind::GlobalAsm(..) => DefKind::GlobalAsm,
 210                 ItemKind::Impl { .. } => DefKind::Impl,
 211             },
 212             Node::ForeignItem(item) => match item.kind {
 213                 ForeignItemKind::Fn(..) => DefKind::Fn,
 214                 ForeignItemKind::Static(..) => DefKind::Static,
 215                 ForeignItemKind::Type => DefKind::ForeignTy,
 216             },
 217             Node::TraitItem(item) => match item.kind {
 218                 TraitItemKind::Const(..) => DefKind::AssocConst,
 219                 TraitItemKind::Fn(..) => DefKind::AssocFn,
 220                 TraitItemKind::Type(..) => DefKind::AssocTy,
 221             },
 222             Node::ImplItem(item) => match item.kind {
 223                 ImplItemKind::Const(..) => DefKind::AssocConst,
 224                 ImplItemKind::Fn(..) => DefKind::AssocFn,
 225                 ImplItemKind::TyAlias(..) => DefKind::AssocTy,
 226             },
 227             Node::Variant(_) => DefKind::Variant,
 228             Node::Ctor(variant_data) => {
 229                 // FIXME(eddyb) is this even possible, if we have a `Node::Ctor`?
 230                 assert_ne!(variant_data.ctor_hir_id(), None);
 231
 232                 let ctor_of = match self.find(self.get_parent_node(hir_id)) {
 233                     Some(Node::Item(..)) => def::CtorOf::Struct,
 234                     Some(Node::Variant(..)) => def::CtorOf::Variant,
 235                     _ => unreachable!(),
 236                 };
 237                 DefKind::Ctor(ctor_of, def::CtorKind::from_hir(variant_data))
 238             }
 239             Node::AnonConst(_) => DefKind::AnonConst,
 240             Node::Field(_) => DefKind::Field,
 241             Node::Expr(expr) => match expr.kind {
 242                 ExprKind::Closure(.., None) => DefKind::Closure,
 243                 ExprKind::Closure(.., Some(_)) => DefKind::Generator,
 244                 _ => bug!("def_kind: unsupported node: {}", self.node_to_string(hir_id)),
 245             },
 246             Node::MacroDef(_) => DefKind::Macro(MacroKind::Bang),
 247             Node::GenericParam(param) => match param.kind {
 248                 GenericParamKind::Lifetime { .. } => DefKind::LifetimeParam,
 249                 GenericParamKind::Type { .. } => DefKind::TyParam,
 250                 GenericParamKind::Const { .. } => DefKind::ConstParam,
 251             },
 252             Node::Stmt(_)
 253             | Node::PathSegment(_)
 254             | Node::Ty(_)
 255             | Node::TraitRef(_)
 256             | Node::Pat(_)
 257             | Node::Binding(_)
 258             | Node::Local(_)
 259             | Node::Param(_)
 260             | Node::Arm(_)
 261             | Node::Lifetime(_)
 262             | Node::Visibility(_)
 263             | Node::Block(_)
 264             | Node::Crate(_) => bug!("def_kind: unsupported node: {}", self.node_to_string(hir_id)),
 265         }
 266     }
 267
 268     fn find_entry(&self, id: HirId) -> Option<Entry<'hir>> {
 269         if id.local_id == ItemLocalId::from_u32(0) {
 270             let owner = self.tcx.hir_owner(id.owner);
 271             owner.map(|owner| Entry { parent: owner.parent, node: owner.node })
 272         } else {
 273             let owner = self.tcx.hir_owner_nodes(id.owner);
 274             owner.and_then(|owner| {
 275                 let node = owner.nodes[id.local_id].as_ref();
 276                 // FIXME(eddyb) use a single generic type insted of having both
 277                 // `Entry` and `ParentedNode`, which are effectively the same.
 278                 // Alternatively, rewrite code using `Entry` to use `ParentedNode`.
 279                 node.map(|node| Entry {
 280                     parent: HirId { owner: id.owner, local_id: node.parent },
 281                     node: node.node,
 282                 })
 283             })
 284         }
 285     }
 286
 287     fn get_entry(&self, id: HirId) -> Entry<'hir> {
 288         self.find_entry(id).unwrap()
 289     }
 290
 291     pub fn item(&self, id: HirId) -> &'hir Item<'hir> {
 292         match self.find(id).unwrap() {
 293             Node::Item(item) => item,
 294             _ => bug!(),
 295         }
 296     }
 297
 298     pub fn trait_item(&self, id: TraitItemId) -> &'hir TraitItem<'hir> {
 299         match self.find(id.hir_id).unwrap() {
 300             Node::TraitItem(item) => item,
 301             _ => bug!(),
 302         }
 303     }
 304
 305     pub fn impl_item(&self, id: ImplItemId) -> &'hir ImplItem<'hir> {
 306         match self.find(id.hir_id).unwrap() {
 307             Node::ImplItem(item) => item,
 308             _ => bug!(),
 309         }
 310     }
 311
 312     pub fn body(&self, id: BodyId) -> &'hir Body<'hir> {
 313         self.tcx.hir_owner_nodes(id.hir_id.owner).unwrap().bodies.get(&id.hir_id.local_id).unwrap()
 314     }
 315
 316     pub fn fn_decl_by_hir_id(&self, hir_id: HirId) -> Option<&'hir FnDecl<'hir>> {
 317         if let Some(node) = self.find(hir_id) {
 318             fn_decl(node)
 319         } else {
 320             bug!("no node for hir_id `{}`", hir_id)
 321         }
 322     }
 323
 324     pub fn fn_sig_by_hir_id(&self, hir_id: HirId) -> Option<&'hir FnSig<'hir>> {
 325         if let Some(node) = self.find(hir_id) {
 326             fn_sig(node)
 327         } else {
 328             bug!("no node for hir_id `{}`", hir_id)
 329         }
 330     }
 331
 332     pub fn enclosing_body_owner(&self, hir_id: HirId) -> HirId {
 333         for (parent, _) in self.parent_iter(hir_id) {
 334             if let Some(body) = self.maybe_body_owned_by(parent) {
 335                 return self.body_owner(body);
 336             }
 337         }
 338
 339         bug!("no `enclosing_body_owner` for hir_id `{}`", hir_id);
 340     }
 341
 342     /// Returns the `HirId` that corresponds to the definition of
 343     /// which this is the body of, i.e., a `fn`, `const` or `static`
 344     /// item (possibly associated), a closure, or a `hir::AnonConst`.
 345     pub fn body_owner(&self, BodyId { hir_id }: BodyId) -> HirId {
 346         let parent = self.get_parent_node(hir_id);
 347         assert!(self.find(parent).map_or(false, |n| is_body_owner(n, hir_id)));
 348         parent
 349     }
 350
 351     pub fn body_owner_def_id(&self, id: BodyId) -> LocalDefId {
 352         self.local_def_id(self.body_owner(id))
 353     }
 354
 355     /// Given a `HirId`, returns the `BodyId` associated with it,
 356     /// if the node is a body owner, otherwise returns `None`.
 357     pub fn maybe_body_owned_by(&self, hir_id: HirId) -> Option<BodyId> {
 358         self.find(hir_id).map(associated_body).flatten()
 359     }
 360
 361     /// Given a body owner's id, returns the `BodyId` associated with it.
 362     pub fn body_owned_by(&self, id: HirId) -> BodyId {
 363         self.maybe_body_owned_by(id).unwrap_or_else(|| {
 364             span_bug!(
 365                 self.span(id),
 366                 "body_owned_by: {} has no associated body",
 367                 self.node_to_string(id)
 368             );
 369         })
 370     }
 371
 372     pub fn body_param_names(&self, id: BodyId) -> impl Iterator<Item = Ident> + 'hir {
 373         self.body(id).params.iter().map(|arg| match arg.pat.kind {
 374             PatKind::Binding(_, _, ident, _) => ident,
 375             _ => Ident::new(kw::Invalid, rustc_span::DUMMY_SP),
 376         })
 377     }
 378
 379     /// Returns the `BodyOwnerKind` of this `LocalDefId`.
 380     ///
 381     /// Panics if `LocalDefId` does not have an associated body.
 382     pub fn body_owner_kind(&self, id: HirId) -> BodyOwnerKind {
 383         match self.get(id) {
 384             Node::Item(&Item { kind: ItemKind::Const(..), .. })
 385             | Node::TraitItem(&TraitItem { kind: TraitItemKind::Const(..), .. })
 386             | Node::ImplItem(&ImplItem { kind: ImplItemKind::Const(..), .. })
 387             | Node::AnonConst(_) => BodyOwnerKind::Const,
 388             Node::Ctor(..)
 389             | Node::Item(&Item { kind: ItemKind::Fn(..), .. })
 390             | Node::TraitItem(&TraitItem { kind: TraitItemKind::Fn(..), .. })
 391             | Node::ImplItem(&ImplItem { kind: ImplItemKind::Fn(..), .. }) => BodyOwnerKind::Fn,
 392             Node::Item(&Item { kind: ItemKind::Static(_, m, _), .. }) => BodyOwnerKind::Static(m),
 393             Node::Expr(&Expr { kind: ExprKind::Closure(..), .. }) => BodyOwnerKind::Closure,
 394             node => bug!("{:#?} is not a body node", node),
 395         }
 396     }
 397
 398     /// Returns the `ConstContext` of the body associated with this `LocalDefId`.
 399     ///
 400     /// Panics if `LocalDefId` does not have an associated body.
 401     pub fn body_const_context(&self, did: LocalDefId) -> Option<ConstContext> {
 402         let hir_id = self.local_def_id_to_hir_id(did);
 403         let ccx = match self.body_owner_kind(hir_id) {
 404             BodyOwnerKind::Const => ConstContext::Const,
 405             BodyOwnerKind::Static(mt) => ConstContext::Static(mt),
 406
 407             BodyOwnerKind::Fn if self.tcx.is_constructor(did.to_def_id()) => return None,
 408             BodyOwnerKind::Fn if self.tcx.is_const_fn_raw(did.to_def_id()) => ConstContext::ConstFn,
 409             BodyOwnerKind::Fn | BodyOwnerKind::Closure => return None,
 410         };
 411
 412         Some(ccx)
 413     }
 414
 415     pub fn ty_param_owner(&self, id: HirId) -> HirId {
 416         match self.get(id) {
 417             Node::Item(&Item { kind: ItemKind::Trait(..) | ItemKind::TraitAlias(..), .. }) => id,
 418             Node::GenericParam(_) => self.get_parent_node(id),
 419             _ => bug!("ty_param_owner: {} not a type parameter", self.node_to_string(id)),
 420         }
 421     }
 422
 423     pub fn ty_param_name(&self, id: HirId) -> Symbol {
 424         match self.get(id) {
 425             Node::Item(&Item { kind: ItemKind::Trait(..) | ItemKind::TraitAlias(..), .. }) => {
 426                 kw::SelfUpper
 427             }
 428             Node::GenericParam(param) => param.name.ident().name,
 429             _ => bug!("ty_param_name: {} not a type parameter", self.node_to_string(id)),
 430         }
 431     }
 432
 433     pub fn trait_impls(&self, trait_did: DefId) -> &'hir [HirId] {
 434         self.tcx.all_local_trait_impls(LOCAL_CRATE).get(&trait_did).map_or(&[], |xs| &xs[..])
 435     }
 436
 437     /// Gets the attributes on the crate. This is preferable to
 438     /// invoking `krate.attrs` because it registers a tighter
 439     /// dep-graph access.
 440     pub fn krate_attrs(&self) -> &'hir [ast::Attribute] {
 441         match self.get_entry(CRATE_HIR_ID).node {
 442             Node::Crate(item) => item.attrs,
 443             _ => bug!(),
 444         }
 445     }
 446
 447     pub fn get_module(&self, module: LocalDefId) -> (&'hir Mod<'hir>, Span, HirId) {
 448         let hir_id = self.local_def_id_to_hir_id(module);
 449         match self.get_entry(hir_id).node {
 450             Node::Item(&Item { span, kind: ItemKind::Mod(ref m), .. }) => (m, span, hir_id),
 451             Node::Crate(item) => (&item.module, item.span, hir_id),
 452             node => panic!("not a module: {:?}", node),
 453         }
 454     }
 455
 456     pub fn visit_item_likes_in_module<V>(&self, module: LocalDefId, visitor: &mut V)
 457     where
 458         V: ItemLikeVisitor<'hir>,
 459     {
 460         let module = self.tcx.hir_module_items(module);
 461
 462         for id in &module.items {
 463             visitor.visit_item(self.expect_item(*id));
 464         }
 465
 466         for id in &module.trait_items {
 467             visitor.visit_trait_item(self.expect_trait_item(id.hir_id));
 468         }
 469
 470         for id in &module.impl_items {
 471             visitor.visit_impl_item(self.expect_impl_item(id.hir_id));
 472         }
 473     }
 474
 475     /// Retrieves the `Node` corresponding to `id`, panicking if it cannot be found.
 476     pub fn get(&self, id: HirId) -> Node<'hir> {
 477         self.find(id).unwrap_or_else(|| bug!("couldn't find hir id {} in the HIR map", id))
 478     }
 479
 480     pub fn get_if_local(&self, id: DefId) -> Option<Node<'hir>> {
 481         id.as_local().and_then(|id| self.find(self.local_def_id_to_hir_id(id)))
 482     }
 483
 484     pub fn get_generics(&self, id: DefId) -> Option<&'hir Generics<'hir>> {
 485         self.get_if_local(id).and_then(|node| match &node {
 486             Node::ImplItem(impl_item) => Some(&impl_item.generics),
 487             Node::TraitItem(trait_item) => Some(&trait_item.generics),
 488             Node::Item(Item {
 489                 kind:
 490                     ItemKind::Fn(_, generics, _)
 491                     | ItemKind::TyAlias(_, generics)
 492                     | ItemKind::Enum(_, generics)
 493                     | ItemKind::Struct(_, generics)
 494                     | ItemKind::Union(_, generics)
 495                     | ItemKind::Trait(_, _, generics, ..)
 496                     | ItemKind::TraitAlias(generics, _)
 497                     | ItemKind::Impl { generics, .. },
 498                 ..
 499             }) => Some(generics),
 500             _ => None,
 501         })
 502     }
 503
 504     /// Retrieves the `Node` corresponding to `id`, returning `None` if cannot be found.
 505     pub fn find(&self, hir_id: HirId) -> Option<Node<'hir>> {
 506         self.find_entry(hir_id).and_then(|entry| {
 507             if let Node::Crate(..) = entry.node { None } else { Some(entry.node) }
 508         })
 509     }
 510
 511     /// Similar to `get_parent`; returns the parent HIR Id, or just `hir_id` if there
 512     /// is no parent. Note that the parent may be `CRATE_HIR_ID`, which is not itself
 513     /// present in the map, so passing the return value of `get_parent_node` to
 514     /// `get` may in fact panic.
 515     /// This function returns the immediate parent in the HIR, whereas `get_parent`
 516     /// returns the enclosing item. Note that this might not be the actual parent
 517     /// node in the HIR -- some kinds of nodes are not in the map and these will
 518     /// never appear as the parent node. Thus, you can always walk the parent nodes
 519     /// from a node to the root of the HIR (unless you get back the same ID here,
 520     /// which can happen if the ID is not in the map itself or is just weird).
 521     pub fn get_parent_node(&self, hir_id: HirId) -> HirId {
 522         self.get_entry(hir_id).parent_node().unwrap_or(hir_id)
 523     }
 524
 525     /// Returns an iterator for the nodes in the ancestor tree of the `current_id`
 526     /// until the crate root is reached. Prefer this over your own loop using `get_parent_node`.
 527     pub fn parent_iter(&self, current_id: HirId) -> ParentHirIterator<'_, 'hir> {
 528         ParentHirIterator { current_id, map: self }
 529     }
 530
 531     /// Checks if the node is an argument. An argument is a local variable whose
 532     /// immediate parent is an item or a closure.
 533     pub fn is_argument(&self, id: HirId) -> bool {
 534         match self.find(id) {
 535             Some(Node::Binding(_)) => (),
 536             _ => return false,
 537         }
 538         matches!(
 539             self.find(self.get_parent_node(id)),
 540             Some(
 541                 Node::Item(_)
 542                 | Node::TraitItem(_)
 543                 | Node::ImplItem(_)
 544                 | Node::Expr(Expr { kind: ExprKind::Closure(..), .. }),
 545             )
 546         )
 547     }
 548
 549     /// Whether the expression pointed at by `hir_id` belongs to a `const` evaluation context.
 550     /// Used exclusively for diagnostics, to avoid suggestion function calls.
 551     pub fn is_inside_const_context(&self, hir_id: HirId) -> bool {
 552         self.body_const_context(self.local_def_id(self.enclosing_body_owner(hir_id))).is_some()
 553     }
 554
 555     /// Whether `hir_id` corresponds to a `mod` or a crate.
 556     pub fn is_hir_id_module(&self, hir_id: HirId) -> bool {
 557         matches!(
 558             self.get_entry(hir_id).node,
 559             Node::Item(Item { kind: ItemKind::Mod(_), .. }) | Node::Crate(..)
 560         )
 561     }
 562
 563     /// Retrieves the `HirId` for `id`'s enclosing method, unless there's a
 564     /// `while` or `loop` before reaching it, as block tail returns are not
 565     /// available in them.
 566     ///
 567     /// ```
 568     /// fn foo(x: usize) -> bool {
 569     ///     if x == 1 {
 570     ///         true  // If `get_return_block` gets passed the `id` corresponding
 571     ///     } else {  // to this, it will return `foo`'s `HirId`.
 572     ///         false
 573     ///     }
 574     /// }
 575     /// ```
 576     ///
 577     /// ```
 578     /// fn foo(x: usize) -> bool {
 579     ///     loop {
 580     ///         true  // If `get_return_block` gets passed the `id` corresponding
 581     ///     }         // to this, it will return `None`.
 582     ///     false
 583     /// }
 584     /// ```
 585     pub fn get_return_block(&self, id: HirId) -> Option<HirId> {
 586         let mut iter = self.parent_iter(id).peekable();
 587         let mut ignore_tail = false;
 588         if let Some(entry) = self.find_entry(id) {
 589             if let Node::Expr(Expr { kind: ExprKind::Ret(_), .. }) = entry.node {
 590                 // When dealing with `return` statements, we don't care about climbing only tail
 591                 // expressions.
 592                 ignore_tail = true;
 593             }
 594         }
 595         while let Some((hir_id, node)) = iter.next() {
 596             if let (Some((_, next_node)), false) = (iter.peek(), ignore_tail) {
 597                 match next_node {
 598                     Node::Block(Block { expr: None, .. }) => return None,
 599                     // The current node is not the tail expression of its parent.
 600                     Node::Block(Block { expr: Some(e), .. }) if hir_id != e.hir_id => return None,
 601                     _ => {}
 602                 }
 603             }
 604             match node {
 605                 Node::Item(_)
 606                 | Node::ForeignItem(_)
 607                 | Node::TraitItem(_)
 608                 | Node::Expr(Expr { kind: ExprKind::Closure(..), .. })
 609                 | Node::ImplItem(_) => return Some(hir_id),
 610                 // Ignore `return`s on the first iteration
 611                 Node::Expr(Expr { kind: ExprKind::Loop(..) | ExprKind::Ret(..), .. })
 612                 | Node::Local(_) => {
 613                     return None;
 614                 }
 615                 _ => {}
 616             }
 617         }
 618         None
 619     }
 620
 621     /// Retrieves the `HirId` for `id`'s parent item, or `id` itself if no
 622     /// parent item is in this map. The "parent item" is the closest parent node
 623     /// in the HIR which is recorded by the map and is an item, either an item
 624     /// in a module, trait, or impl.
 625     pub fn get_parent_item(&self, hir_id: HirId) -> HirId {
 626         for (hir_id, node) in self.parent_iter(hir_id) {
 627             match node {
 628                 Node::Crate(_)
 629                 | Node::Item(_)
 630                 | Node::ForeignItem(_)
 631                 | Node::TraitItem(_)
 632                 | Node::ImplItem(_) => return hir_id,
 633                 _ => {}
 634             }
 635         }
 636         hir_id
 637     }
 638
 639     /// Returns the `HirId` of `id`'s nearest module parent, or `id` itself if no
 640     /// module parent is in this map.
 641     pub(super) fn get_module_parent_node(&self, hir_id: HirId) -> HirId {
 642         for (hir_id, node) in self.parent_iter(hir_id) {
 643             if let Node::Item(&Item { kind: ItemKind::Mod(_), .. }) = node {
 644                 return hir_id;
 645             }
 646         }
 647         CRATE_HIR_ID
 648     }
 649
 650     /// When on a match arm tail expression or on a match arm, give back the enclosing `match`
 651     /// expression.
 652     ///
 653     /// Used by error reporting when there's a type error in a match arm caused by the `match`
 654     /// expression needing to be unit.
 655     pub fn get_match_if_cause(&self, hir_id: HirId) -> Option<&'hir Expr<'hir>> {
 656         for (_, node) in self.parent_iter(hir_id) {
 657             match node {
 658                 Node::Item(_)
 659                 | Node::ForeignItem(_)
 660                 | Node::TraitItem(_)
 661                 | Node::ImplItem(_)
 662                 | Node::Stmt(Stmt { kind: StmtKind::Local(_), .. }) => break,
 663                 Node::Expr(expr @ Expr { kind: ExprKind::Match(..), .. }) => return Some(expr),
 664                 _ => {}
 665             }
 666         }
 667         None
 668     }
 669
 670     /// Returns the nearest enclosing scope. A scope is roughly an item or block.
 671     pub fn get_enclosing_scope(&self, hir_id: HirId) -> Option<HirId> {
 672         for (hir_id, node) in self.parent_iter(hir_id) {
 673             if let Node::Item(Item {
 674                 kind:
 675                     ItemKind::Fn(..)
 676                     | ItemKind::Const(..)
 677                     | ItemKind::Static(..)
 678                     | ItemKind::Mod(..)
 679                     | ItemKind::Enum(..)
 680                     | ItemKind::Struct(..)
 681                     | ItemKind::Union(..)
 682                     | ItemKind::Trait(..)
 683                     | ItemKind::Impl { .. },
 684                 ..
 685             })
 686             | Node::ForeignItem(ForeignItem { kind: ForeignItemKind::Fn(..), .. })
 687             | Node::TraitItem(TraitItem { kind: TraitItemKind::Fn(..), .. })
 688             | Node::ImplItem(ImplItem { kind: ImplItemKind::Fn(..), .. })
 689             | Node::Block(_) = node
 690             {
 691                 return Some(hir_id);
 692             }
 693         }
 694         None
 695     }
 696
 697     /// Returns the defining scope for an opaque type definition.
 698     pub fn get_defining_scope(&self, id: HirId) -> HirId {
 699         let mut scope = id;
 700         loop {
 701             scope = self.get_enclosing_scope(scope).unwrap_or(CRATE_HIR_ID);
 702             if scope == CRATE_HIR_ID {
 703                 return CRATE_HIR_ID;
 704             }
 705             match self.get(scope) {
 706                 Node::Block(_) => {}
 707                 _ => break,
 708             }
 709         }
 710         scope
 711     }
 712
 713     pub fn get_parent_did(&self, id: HirId) -> LocalDefId {
 714         self.local_def_id(self.get_parent_item(id))
 715     }
 716
 717     pub fn get_foreign_abi(&self, hir_id: HirId) -> Abi {
 718         let parent = self.get_parent_item(hir_id);
 719         if let Some(entry) = self.find_entry(parent) {
 720             if let Entry {
 721                 node: Node::Item(Item { kind: ItemKind::ForeignMod(ref nm), .. }), ..
 722             } = entry
 723             {
 724                 return nm.abi;
 725             }
 726         }
 727         bug!("expected foreign mod or inlined parent, found {}", self.node_to_string(parent))
 728     }
 729
 730     pub fn expect_item(&self, id: HirId) -> &'hir Item<'hir> {
 731         match self.find(id) {
 732             Some(Node::Item(item)) => item,
 733             _ => bug!("expected item, found {}", self.node_to_string(id)),
 734         }
 735     }
 736
 737     pub fn expect_impl_item(&self, id: HirId) -> &'hir ImplItem<'hir> {
 738         match self.find(id) {
 739             Some(Node::ImplItem(item)) => item,
 740             _ => bug!("expected impl item, found {}", self.node_to_string(id)),
 741         }
 742     }
 743
 744     pub fn expect_trait_item(&self, id: HirId) -> &'hir TraitItem<'hir> {
 745         match self.find(id) {
 746             Some(Node::TraitItem(item)) => item,
 747             _ => bug!("expected trait item, found {}", self.node_to_string(id)),
 748         }
 749     }
 750
 751     pub fn expect_variant_data(&self, id: HirId) -> &'hir VariantData<'hir> {
 752         match self.find(id) {
 753             Some(
 754                 Node::Ctor(vd)
 755                 | Node::Item(Item { kind: ItemKind::Struct(vd, _) | ItemKind::Union(vd, _), .. }),
 756             ) => vd,
 757             Some(Node::Variant(variant)) => &variant.data,
 758             _ => bug!("expected struct or variant, found {}", self.node_to_string(id)),
 759         }
 760     }
 761
 762     pub fn expect_variant(&self, id: HirId) -> &'hir Variant<'hir> {
 763         match self.find(id) {
 764             Some(Node::Variant(variant)) => variant,
 765             _ => bug!("expected variant, found {}", self.node_to_string(id)),
 766         }
 767     }
 768
 769     pub fn expect_foreign_item(&self, id: HirId) -> &'hir ForeignItem<'hir> {
 770         match self.find(id) {
 771             Some(Node::ForeignItem(item)) => item,
 772             _ => bug!("expected foreign item, found {}", self.node_to_string(id)),
 773         }
 774     }
 775
 776     pub fn expect_expr(&self, id: HirId) -> &'hir Expr<'hir> {
 777         match self.find(id) {
 778             Some(Node::Expr(expr)) => expr,
 779             _ => bug!("expected expr, found {}", self.node_to_string(id)),
 780         }
 781     }
 782
 783     pub fn opt_name(&self, id: HirId) -> Option<Symbol> {
 784         Some(match self.get(id) {
 785             Node::Item(i) => i.ident.name,
 786             Node::ForeignItem(fi) => fi.ident.name,
 787             Node::ImplItem(ii) => ii.ident.name,
 788             Node::TraitItem(ti) => ti.ident.name,
 789             Node::Variant(v) => v.ident.name,
 790             Node::Field(f) => f.ident.name,
 791             Node::Lifetime(lt) => lt.name.ident().name,
 792             Node::GenericParam(param) => param.name.ident().name,
 793             Node::Binding(&Pat { kind: PatKind::Binding(_, _, l, _), .. }) => l.name,
 794             Node::Ctor(..) => self.name(self.get_parent_item(id)),
 795             _ => return None,
 796         })
 797     }
 798
 799     pub fn name(&self, id: HirId) -> Symbol {
 800         match self.opt_name(id) {
 801             Some(name) => name,
 802             None => bug!("no name for {}", self.node_to_string(id)),
 803         }
 804     }
 805
 806     /// Given a node ID, gets a list of attributes associated with the AST
 807     /// corresponding to the node-ID.
 808     pub fn attrs(&self, id: HirId) -> &'hir [ast::Attribute] {
 809         let attrs = self.find_entry(id).map(|entry| match entry.node {
 810             Node::Param(a) => &a.attrs[..],
 811             Node::Local(l) => &l.attrs[..],
 812             Node::Item(i) => &i.attrs[..],
 813             Node::ForeignItem(fi) => &fi.attrs[..],
 814             Node::TraitItem(ref ti) => &ti.attrs[..],
 815             Node::ImplItem(ref ii) => &ii.attrs[..],
 816             Node::Variant(ref v) => &v.attrs[..],
 817             Node::Field(ref f) => &f.attrs[..],
 818             Node::Expr(ref e) => &*e.attrs,
 819             Node::Stmt(ref s) => s.kind.attrs(|id| self.item(id.id)),
 820             Node::Arm(ref a) => &*a.attrs,
 821             Node::GenericParam(param) => &param.attrs[..],
 822             // Unit/tuple structs/variants take the attributes straight from
 823             // the struct/variant definition.
 824             Node::Ctor(..) => self.attrs(self.get_parent_item(id)),
 825             Node::Crate(item) => &item.attrs[..],
 826             Node::MacroDef(def) => def.attrs,
 827             Node::AnonConst(..)
 828             | Node::PathSegment(..)
 829             | Node::Ty(..)
 830             | Node::Pat(..)
 831             | Node::Binding(..)
 832             | Node::TraitRef(..)
 833             | Node::Block(..)
 834             | Node::Lifetime(..)
 835             | Node::Visibility(..) => &[],
 836         });
 837         attrs.unwrap_or(&[])
 838     }
 839
 840     /// Gets the span of the definition of the specified HIR node.
 841     /// This is used by `tcx.get_span`
 842     pub fn span(&self, hir_id: HirId) -> Span {
 843         match self.find_entry(hir_id).map(|entry| entry.node) {
 844             Some(Node::Param(param)) => param.span,
 845             Some(Node::Item(item)) => match &item.kind {
 846                 ItemKind::Fn(sig, _, _) => sig.span,
 847                 _ => item.span,
 848             },
 849             Some(Node::ForeignItem(foreign_item)) => foreign_item.span,
 850             Some(Node::TraitItem(trait_item)) => match &trait_item.kind {
 851                 TraitItemKind::Fn(sig, _) => sig.span,
 852                 _ => trait_item.span,
 853             },
 854             Some(Node::ImplItem(impl_item)) => match &impl_item.kind {
 855                 ImplItemKind::Fn(sig, _) => sig.span,
 856                 _ => impl_item.span,
 857             },
 858             Some(Node::Variant(variant)) => variant.span,
 859             Some(Node::Field(field)) => field.span,
 860             Some(Node::AnonConst(constant)) => self.body(constant.body).value.span,
 861             Some(Node::Expr(expr)) => expr.span,
 862             Some(Node::Stmt(stmt)) => stmt.span,
 863             Some(Node::PathSegment(seg)) => seg.ident.span,
 864             Some(Node::Ty(ty)) => ty.span,
 865             Some(Node::TraitRef(tr)) => tr.path.span,
 866             Some(Node::Binding(pat)) => pat.span,
 867             Some(Node::Pat(pat)) => pat.span,
 868             Some(Node::Arm(arm)) => arm.span,
 869             Some(Node::Block(block)) => block.span,
 870             Some(Node::Ctor(..)) => match self.find(self.get_parent_node(hir_id)) {
 871                 Some(Node::Item(item)) => item.span,
 872                 Some(Node::Variant(variant)) => variant.span,
 873                 _ => unreachable!(),
 874             },
 875             Some(Node::Lifetime(lifetime)) => lifetime.span,
 876             Some(Node::GenericParam(param)) => param.span,
 877             Some(Node::Visibility(&Spanned {
 878                 node: VisibilityKind::Restricted { ref path, .. },
 879                 ..
 880             })) => path.span,
 881             Some(Node::Visibility(v)) => bug!("unexpected Visibility {:?}", v),
 882             Some(Node::Local(local)) => local.span,
 883             Some(Node::MacroDef(macro_def)) => macro_def.span,
 884             Some(Node::Crate(item)) => item.span,
 885             None => bug!("hir::map::Map::span: id not in map: {:?}", hir_id),
 886         }
 887     }
 888
 889     /// Like `hir.span()`, but includes the body of function items
 890     /// (instead of just the function header)
 891     pub fn span_with_body(&self, hir_id: HirId) -> Span {
 892         match self.find_entry(hir_id).map(|entry| entry.node) {
 893             Some(Node::TraitItem(item)) => item.span,
 894             Some(Node::ImplItem(impl_item)) => impl_item.span,
 895             Some(Node::Item(item)) => item.span,
 896             Some(_) => self.span(hir_id),
 897             _ => bug!("hir::map::Map::span_with_body: id not in map: {:?}", hir_id),
 898         }
 899     }
 900
 901     pub fn span_if_local(&self, id: DefId) -> Option<Span> {
 902         id.as_local().map(|id| self.span(self.local_def_id_to_hir_id(id)))
 903     }
 904
 905     pub fn res_span(&self, res: Res) -> Option<Span> {
 906         match res {
 907             Res::Err => None,
 908             Res::Local(id) => Some(self.span(id)),
 909             res => self.span_if_local(res.opt_def_id()?),
 910         }
 911     }
 912
 913     /// Get a representation of this `id` for debugging purposes.
 914     /// NOTE: Do NOT use this in diagnostics!
 915     pub fn node_to_string(&self, id: HirId) -> String {
 916         hir_id_to_string(self, id)
 917     }
 918 }
 919
 920 impl<'hir> intravisit::Map<'hir> for Map<'hir> {
 921     fn find(&self, hir_id: HirId) -> Option<Node<'hir>> {
 922         self.find(hir_id)
 923     }
 924
 925     fn body(&self, id: BodyId) -> &'hir Body<'hir> {
 926         self.body(id)
 927     }
 928
 929     fn item(&self, id: HirId) -> &'hir Item<'hir> {
 930         self.item(id)
 931     }
 932
 933     fn trait_item(&self, id: TraitItemId) -> &'hir TraitItem<'hir> {
 934         self.trait_item(id)
 935     }
 936
 937     fn impl_item(&self, id: ImplItemId) -> &'hir ImplItem<'hir> {
 938         self.impl_item(id)
 939     }
 940 }
 941
 942 trait Named {
 943     fn name(&self) -> Symbol;
 944 }
 945
 946 impl<T: Named> Named for Spanned<T> {
 947     fn name(&self) -> Symbol {
 948         self.node.name()
 949     }
 950 }
 951
 952 impl Named for Item<'_> {
 953     fn name(&self) -> Symbol {
 954         self.ident.name
 955     }
 956 }
 957 impl Named for ForeignItem<'_> {
 958     fn name(&self) -> Symbol {
 959         self.ident.name
 960     }
 961 }
 962 impl Named for Variant<'_> {
 963     fn name(&self) -> Symbol {
 964         self.ident.name
 965     }
 966 }
 967 impl Named for StructField<'_> {
 968     fn name(&self) -> Symbol {
 969         self.ident.name
 970     }
 971 }
 972 impl Named for TraitItem<'_> {
 973     fn name(&self) -> Symbol {
 974         self.ident.name
 975     }
 976 }
 977 impl Named for ImplItem<'_> {
 978     fn name(&self) -> Symbol {
 979         self.ident.name
 980     }
 981 }
 982
 983 pub(super) fn index_hir<'tcx>(tcx: TyCtxt<'tcx>, cnum: CrateNum) -> &'tcx IndexedHir<'tcx> {
 984     assert_eq!(cnum, LOCAL_CRATE);
 985
 986     let _prof_timer = tcx.sess.prof.generic_activity("build_hir_map");
 987
 988     let (map, crate_hash) = {
 989         let hcx = tcx.create_stable_hashing_context();
 990
 991         let mut collector =
 992             NodeCollector::root(tcx.sess, &**tcx.arena, tcx.untracked_crate, &tcx.definitions, hcx);
 993         intravisit::walk_crate(&mut collector, tcx.untracked_crate);
 994
 995         let crate_disambiguator = tcx.sess.local_crate_disambiguator();
 996         let cmdline_args = tcx.sess.opts.dep_tracking_hash();
 997         collector.finalize_and_compute_crate_hash(crate_disambiguator, &*tcx.cstore, cmdline_args)
 998     };
 999
1000     tcx.arena.alloc(IndexedHir { crate_hash, map })
1001 }
1002
1003 fn hir_id_to_string(map: &Map<'_>, id: HirId) -> String {
1004     let id_str = format!(" (hir_id={})", id);
1005
1006     let path_str = || {
1007         // This functionality is used for debugging, try to use `TyCtxt` to get
1008         // the user-friendly path, otherwise fall back to stringifying `DefPath`.
1009         crate::ty::tls::with_opt(|tcx| {
1010             if let Some(tcx) = tcx {
1011                 let def_id = map.local_def_id(id);
1012                 tcx.def_path_str(def_id.to_def_id())
1013             } else if let Some(path) = map.def_path_from_hir_id(id) {
1014                 path.data.into_iter().map(|elem| elem.to_string()).collect::<Vec<_>>().join("::")
1015             } else {
1016                 String::from("<missing path>")
1017             }
1018         })
1019     };
1020
1021     let span_str = || map.tcx.sess.source_map().span_to_snippet(map.span(id)).unwrap_or_default();
1022     let node_str = |prefix| format!("{} {}{}", prefix, span_str(), id_str);
1023
1024     match map.find(id) {
1025         Some(Node::Item(item)) => {
1026             let item_str = match item.kind {
1027                 ItemKind::ExternCrate(..) => "extern crate",
1028                 ItemKind::Use(..) => "use",
1029                 ItemKind::Static(..) => "static",
1030                 ItemKind::Const(..) => "const",
1031                 ItemKind::Fn(..) => "fn",
1032                 ItemKind::Mod(..) => "mod",
1033                 ItemKind::ForeignMod(..) => "foreign mod",
1034                 ItemKind::GlobalAsm(..) => "global asm",
1035                 ItemKind::TyAlias(..) => "ty",
1036                 ItemKind::OpaqueTy(..) => "opaque type",
1037                 ItemKind::Enum(..) => "enum",
1038                 ItemKind::Struct(..) => "struct",
1039                 ItemKind::Union(..) => "union",
1040                 ItemKind::Trait(..) => "trait",
1041                 ItemKind::TraitAlias(..) => "trait alias",
1042                 ItemKind::Impl { .. } => "impl",
1043             };
1044             format!("{} {}{}", item_str, path_str(), id_str)
1045         }
1046         Some(Node::ForeignItem(_)) => format!("foreign item {}{}", path_str(), id_str),
1047         Some(Node::ImplItem(ii)) => match ii.kind {
1048             ImplItemKind::Const(..) => {
1049                 format!("assoc const {} in {}{}", ii.ident, path_str(), id_str)
1050             }
1051             ImplItemKind::Fn(..) => format!("method {} in {}{}", ii.ident, path_str(), id_str),
1052             ImplItemKind::TyAlias(_) => {
1053                 format!("assoc type {} in {}{}", ii.ident, path_str(), id_str)
1054             }
1055         },
1056         Some(Node::TraitItem(ti)) => {
1057             let kind = match ti.kind {
1058                 TraitItemKind::Const(..) => "assoc constant",
1059                 TraitItemKind::Fn(..) => "trait method",
1060                 TraitItemKind::Type(..) => "assoc type",
1061             };
1062
1063             format!("{} {} in {}{}", kind, ti.ident, path_str(), id_str)
1064         }
1065         Some(Node::Variant(ref variant)) => {
1066             format!("variant {} in {}{}", variant.ident, path_str(), id_str)
1067         }
1068         Some(Node::Field(ref field)) => {
1069             format!("field {} in {}{}", field.ident, path_str(), id_str)
1070         }
1071         Some(Node::AnonConst(_)) => node_str("const"),
1072         Some(Node::Expr(_)) => node_str("expr"),
1073         Some(Node::Stmt(_)) => node_str("stmt"),
1074         Some(Node::PathSegment(_)) => node_str("path segment"),
1075         Some(Node::Ty(_)) => node_str("type"),
1076         Some(Node::TraitRef(_)) => node_str("trait ref"),
1077         Some(Node::Binding(_)) => node_str("local"),
1078         Some(Node::Pat(_)) => node_str("pat"),
1079         Some(Node::Param(_)) => node_str("param"),
1080         Some(Node::Arm(_)) => node_str("arm"),
1081         Some(Node::Block(_)) => node_str("block"),
1082         Some(Node::Local(_)) => node_str("local"),
1083         Some(Node::Ctor(..)) => format!("ctor {}{}", path_str(), id_str),
1084         Some(Node::Lifetime(_)) => node_str("lifetime"),
1085         Some(Node::GenericParam(ref param)) => format!("generic_param {:?}{}", param, id_str),
1086         Some(Node::Visibility(ref vis)) => format!("visibility {:?}{}", vis, id_str),
1087         Some(Node::MacroDef(_)) => format!("macro {}{}", path_str(), id_str),
1088         Some(Node::Crate(..)) => String::from("root_crate"),
1089         None => format!("unknown node{}", id_str),
1090     }
1091 }
1092
1093 pub fn provide(providers: &mut Providers) {
1094     providers.def_kind = |tcx, def_id| tcx.hir().def_kind(def_id.expect_local());
1095 }