src/librustc/hir/map/mod.rs

   1 // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 pub use self::Node::*;
  12 use self::MapEntry::*;
  13 use self::collector::NodeCollector;
  14 pub use self::def_collector::{DefCollector, MacroInvocationData};
  15 pub use self::definitions::{Definitions, DefKey, DefPath, DefPathData,
  16                             DisambiguatedDefPathData, DefPathHash};
  17
  18 use dep_graph::{DepGraph, DepNode, DepKind, DepNodeIndex};
  19
  20 use hir::def_id::{CRATE_DEF_INDEX, DefId, DefIndexAddressSpace};
  21
  22 use syntax::abi::Abi;
  23 use syntax::ast::{self, Name, NodeId, CRATE_NODE_ID};
  24 use syntax::codemap::Spanned;
  25 use syntax_pos::Span;
  26
  27 use hir::*;
  28 use hir::print::Nested;
  29 use util::nodemap::{DefIdMap, FxHashMap};
  30
  31 use arena::TypedArena;
  32 use std::cell::RefCell;
  33 use std::io;
  34
  35 pub mod blocks;
  36 mod collector;
  37 mod def_collector;
  38 pub mod definitions;
  39 mod hir_id_validator;
  40
  41 pub const ITEM_LIKE_SPACE: DefIndexAddressSpace = DefIndexAddressSpace::Low;
  42 pub const REGULAR_SPACE: DefIndexAddressSpace = DefIndexAddressSpace::High;
  43
  44 #[derive(Copy, Clone, Debug)]
  45 pub enum Node<'hir> {
  46     NodeItem(&'hir Item),
  47     NodeForeignItem(&'hir ForeignItem),
  48     NodeTraitItem(&'hir TraitItem),
  49     NodeImplItem(&'hir ImplItem),
  50     NodeVariant(&'hir Variant),
  51     NodeField(&'hir StructField),
  52     NodeExpr(&'hir Expr),
  53     NodeStmt(&'hir Stmt),
  54     NodeTy(&'hir Ty),
  55     NodeTraitRef(&'hir TraitRef),
  56     NodeBinding(&'hir Pat),
  57     NodePat(&'hir Pat),
  58     NodeBlock(&'hir Block),
  59     NodeLocal(&'hir Local),
  60
  61     /// NodeStructCtor represents a tuple struct.
  62     NodeStructCtor(&'hir VariantData),
  63
  64     NodeLifetime(&'hir Lifetime),
  65     NodeTyParam(&'hir TyParam),
  66     NodeVisibility(&'hir Visibility),
  67 }
  68
  69 /// Represents an entry and its parent NodeID.
  70 /// The odd layout is to bring down the total size.
  71 #[derive(Copy, Debug)]
  72 enum MapEntry<'hir> {
  73     /// Placeholder for holes in the map.
  74     NotPresent,
  75
  76     /// All the node types, with a parent ID.
  77     EntryItem(NodeId, DepNodeIndex, &'hir Item),
  78     EntryForeignItem(NodeId, DepNodeIndex, &'hir ForeignItem),
  79     EntryTraitItem(NodeId, DepNodeIndex, &'hir TraitItem),
  80     EntryImplItem(NodeId, DepNodeIndex, &'hir ImplItem),
  81     EntryVariant(NodeId, DepNodeIndex, &'hir Variant),
  82     EntryField(NodeId, DepNodeIndex, &'hir StructField),
  83     EntryExpr(NodeId, DepNodeIndex, &'hir Expr),
  84     EntryStmt(NodeId, DepNodeIndex, &'hir Stmt),
  85     EntryTy(NodeId, DepNodeIndex, &'hir Ty),
  86     EntryTraitRef(NodeId, DepNodeIndex, &'hir TraitRef),
  87     EntryBinding(NodeId, DepNodeIndex, &'hir Pat),
  88     EntryPat(NodeId, DepNodeIndex, &'hir Pat),
  89     EntryBlock(NodeId, DepNodeIndex, &'hir Block),
  90     EntryStructCtor(NodeId, DepNodeIndex, &'hir VariantData),
  91     EntryLifetime(NodeId, DepNodeIndex, &'hir Lifetime),
  92     EntryTyParam(NodeId, DepNodeIndex, &'hir TyParam),
  93     EntryVisibility(NodeId, DepNodeIndex, &'hir Visibility),
  94     EntryLocal(NodeId, DepNodeIndex, &'hir Local),
  95
  96     /// Roots for node trees. The DepNodeIndex is the dependency node of the
  97     /// crate's root module.
  98     RootCrate(DepNodeIndex),
  99 }
 100
 101 impl<'hir> Clone for MapEntry<'hir> {
 102     fn clone(&self) -> MapEntry<'hir> {
 103         *self
 104     }
 105 }
 106
 107 impl<'hir> MapEntry<'hir> {
 108     fn parent_node(self) -> Option<NodeId> {
 109         Some(match self {
 110             EntryItem(id, _, _) => id,
 111             EntryForeignItem(id, _, _) => id,
 112             EntryTraitItem(id, _, _) => id,
 113             EntryImplItem(id, _, _) => id,
 114             EntryVariant(id, _, _) => id,
 115             EntryField(id, _, _) => id,
 116             EntryExpr(id, _, _) => id,
 117             EntryStmt(id, _, _) => id,
 118             EntryTy(id, _, _) => id,
 119             EntryTraitRef(id, _, _) => id,
 120             EntryBinding(id, _, _) => id,
 121             EntryPat(id, _, _) => id,
 122             EntryBlock(id, _, _) => id,
 123             EntryStructCtor(id, _, _) => id,
 124             EntryLifetime(id, _, _) => id,
 125             EntryTyParam(id, _, _) => id,
 126             EntryVisibility(id, _, _) => id,
 127             EntryLocal(id, _, _) => id,
 128
 129             NotPresent |
 130             RootCrate(_) => return None,
 131         })
 132     }
 133
 134     fn to_node(self) -> Option<Node<'hir>> {
 135         Some(match self {
 136             EntryItem(_, _, n) => NodeItem(n),
 137             EntryForeignItem(_, _, n) => NodeForeignItem(n),
 138             EntryTraitItem(_, _, n) => NodeTraitItem(n),
 139             EntryImplItem(_, _, n) => NodeImplItem(n),
 140             EntryVariant(_, _, n) => NodeVariant(n),
 141             EntryField(_, _, n) => NodeField(n),
 142             EntryExpr(_, _, n) => NodeExpr(n),
 143             EntryStmt(_, _, n) => NodeStmt(n),
 144             EntryTy(_, _, n) => NodeTy(n),
 145             EntryTraitRef(_, _, n) => NodeTraitRef(n),
 146             EntryBinding(_, _, n) => NodeBinding(n),
 147             EntryPat(_, _, n) => NodePat(n),
 148             EntryBlock(_, _, n) => NodeBlock(n),
 149             EntryStructCtor(_, _, n) => NodeStructCtor(n),
 150             EntryLifetime(_, _, n) => NodeLifetime(n),
 151             EntryTyParam(_, _, n) => NodeTyParam(n),
 152             EntryVisibility(_, _, n) => NodeVisibility(n),
 153             EntryLocal(_, _, n) => NodeLocal(n),
 154
 155             NotPresent |
 156             RootCrate(_) => return None
 157         })
 158     }
 159
 160     fn associated_body(self) -> Option<BodyId> {
 161         match self {
 162             EntryItem(_, _, item) => {
 163                 match item.node {
 164                     ItemConst(_, body) |
 165                     ItemStatic(.., body) |
 166                     ItemFn(_, _, _, _, _, body) => Some(body),
 167                     _ => None,
 168                 }
 169             }
 170
 171             EntryTraitItem(_, _, item) => {
 172                 match item.node {
 173                     TraitItemKind::Const(_, Some(body)) |
 174                     TraitItemKind::Method(_, TraitMethod::Provided(body)) => Some(body),
 175                     _ => None
 176                 }
 177             }
 178
 179             EntryImplItem(_, _, item) => {
 180                 match item.node {
 181                     ImplItemKind::Const(_, body) |
 182                     ImplItemKind::Method(_, body) => Some(body),
 183                     _ => None,
 184                 }
 185             }
 186
 187             EntryExpr(_, _, expr) => {
 188                 match expr.node {
 189                     ExprClosure(.., body, _, _) => Some(body),
 190                     _ => None,
 191                 }
 192             }
 193
 194             _ => None
 195         }
 196     }
 197
 198     fn is_body_owner(self, node_id: NodeId) -> bool {
 199         match self.associated_body() {
 200             Some(b) => b.node_id == node_id,
 201             None => false,
 202         }
 203     }
 204 }
 205
 206 /// Stores a crate and any number of inlined items from other crates.
 207 pub struct Forest {
 208     krate: Crate,
 209     pub dep_graph: DepGraph,
 210     inlined_bodies: TypedArena<Body>
 211 }
 212
 213 impl Forest {
 214     pub fn new(krate: Crate, dep_graph: &DepGraph) -> Forest {
 215         Forest {
 216             krate,
 217             dep_graph: dep_graph.clone(),
 218             inlined_bodies: TypedArena::new()
 219         }
 220     }
 221
 222     pub fn krate<'hir>(&'hir self) -> &'hir Crate {
 223         self.dep_graph.read(DepNode::new_no_params(DepKind::Krate));
 224         &self.krate
 225     }
 226 }
 227
 228 /// Represents a mapping from Node IDs to AST elements and their parent
 229 /// Node IDs
 230 #[derive(Clone)]
 231 pub struct Map<'hir> {
 232     /// The backing storage for all the AST nodes.
 233     pub forest: &'hir Forest,
 234
 235     /// Same as the dep_graph in forest, just available with one fewer
 236     /// deref. This is a gratuitous micro-optimization.
 237     pub dep_graph: DepGraph,
 238
 239     /// NodeIds are sequential integers from 0, so we can be
 240     /// super-compact by storing them in a vector. Not everything with
 241     /// a NodeId is in the map, but empirically the occupancy is about
 242     /// 75-80%, so there's not too much overhead (certainly less than
 243     /// a hashmap, since they (at the time of writing) have a maximum
 244     /// of 75% occupancy).
 245     ///
 246     /// Also, indexing is pretty quick when you've got a vector and
 247     /// plain old integers.
 248     map: Vec<MapEntry<'hir>>,
 249
 250     definitions: Definitions,
 251
 252     /// Bodies inlined from other crates are cached here.
 253     inlined_bodies: RefCell<DefIdMap<&'hir Body>>,
 254
 255     /// The reverse mapping of `node_to_hir_id`.
 256     hir_to_node_id: FxHashMap<HirId, NodeId>,
 257 }
 258
 259 impl<'hir> Map<'hir> {
 260     /// Registers a read in the dependency graph of the AST node with
 261     /// the given `id`. This needs to be called each time a public
 262     /// function returns the HIR for a node -- in other words, when it
 263     /// "reveals" the content of a node to the caller (who might not
 264     /// otherwise have had access to those contents, and hence needs a
 265     /// read recorded). If the function just returns a DefId or
 266     /// NodeId, no actual content was returned, so no read is needed.
 267     pub fn read(&self, id: NodeId) {
 268         let entry = self.map[id.as_usize()];
 269         match entry {
 270             EntryItem(_, dep_node_index, _) |
 271             EntryTraitItem(_, dep_node_index, _) |
 272             EntryImplItem(_, dep_node_index, _) |
 273             EntryVariant(_, dep_node_index, _) |
 274             EntryForeignItem(_, dep_node_index, _) |
 275             EntryField(_, dep_node_index, _) |
 276             EntryStmt(_, dep_node_index, _) |
 277             EntryTy(_, dep_node_index, _) |
 278             EntryTraitRef(_, dep_node_index, _) |
 279             EntryBinding(_, dep_node_index, _) |
 280             EntryPat(_, dep_node_index, _) |
 281             EntryBlock(_, dep_node_index, _) |
 282             EntryStructCtor(_, dep_node_index, _) |
 283             EntryLifetime(_, dep_node_index, _) |
 284             EntryTyParam(_, dep_node_index, _) |
 285             EntryVisibility(_, dep_node_index, _) |
 286             EntryExpr(_, dep_node_index, _) |
 287             EntryLocal(_, dep_node_index, _) |
 288             RootCrate(dep_node_index) => {
 289                 self.dep_graph.read_index(dep_node_index);
 290             }
 291             NotPresent => {
 292                 // Some nodes, notably macro definitions, are not
 293                 // present in the map for whatever reason, but
 294                 // they *do* have def-ids. So if we encounter an
 295                 // empty hole, check for that case.
 296                 if let Some(def_index) = self.definitions.opt_def_index(id) {
 297                     let def_path_hash = self.definitions.def_path_hash(def_index);
 298                     self.dep_graph.read(def_path_hash.to_dep_node(DepKind::Hir));
 299                 } else {
 300                     bug!("called HirMap::read() with invalid NodeId")
 301                 }
 302             }
 303         }
 304     }
 305
 306     #[inline]
 307     pub fn definitions(&self) -> &Definitions {
 308         &self.definitions
 309     }
 310
 311     pub fn def_key(&self, def_id: DefId) -> DefKey {
 312         assert!(def_id.is_local());
 313         self.definitions.def_key(def_id.index)
 314     }
 315
 316     pub fn def_path_from_id(&self, id: NodeId) -> Option<DefPath> {
 317         self.opt_local_def_id(id).map(|def_id| {
 318             self.def_path(def_id)
 319         })
 320     }
 321
 322     pub fn def_path(&self, def_id: DefId) -> DefPath {
 323         assert!(def_id.is_local());
 324         self.definitions.def_path(def_id.index)
 325     }
 326
 327     #[inline]
 328     pub fn local_def_id(&self, node: NodeId) -> DefId {
 329         self.opt_local_def_id(node).unwrap_or_else(|| {
 330             bug!("local_def_id: no entry for `{}`, which has a map of `{:?}`",
 331                  node, self.find_entry(node))
 332         })
 333     }
 334
 335     #[inline]
 336     pub fn opt_local_def_id(&self, node: NodeId) -> Option<DefId> {
 337         self.definitions.opt_local_def_id(node)
 338     }
 339
 340     #[inline]
 341     pub fn as_local_node_id(&self, def_id: DefId) -> Option<NodeId> {
 342         self.definitions.as_local_node_id(def_id)
 343     }
 344
 345     #[inline]
 346     pub fn hir_to_node_id(&self, hir_id: HirId) -> NodeId {
 347         self.hir_to_node_id[&hir_id]
 348     }
 349
 350     #[inline]
 351     pub fn node_to_hir_id(&self, node_id: NodeId) -> HirId {
 352         self.definitions.node_to_hir_id(node_id)
 353     }
 354
 355     #[inline]
 356     pub fn def_index_to_hir_id(&self, def_index: DefIndex) -> HirId {
 357         self.definitions.def_index_to_hir_id(def_index)
 358     }
 359
 360     #[inline]
 361     pub fn def_index_to_node_id(&self, def_index: DefIndex) -> NodeId {
 362         self.definitions.as_local_node_id(DefId::local(def_index)).unwrap()
 363     }
 364
 365     fn entry_count(&self) -> usize {
 366         self.map.len()
 367     }
 368
 369     fn find_entry(&self, id: NodeId) -> Option<MapEntry<'hir>> {
 370         self.map.get(id.as_usize()).cloned()
 371     }
 372
 373     pub fn krate(&self) -> &'hir Crate {
 374         self.forest.krate()
 375     }
 376
 377     pub fn trait_item(&self, id: TraitItemId) -> &'hir TraitItem {
 378         self.read(id.node_id);
 379
 380         // NB: intentionally bypass `self.forest.krate()` so that we
 381         // do not trigger a read of the whole krate here
 382         self.forest.krate.trait_item(id)
 383     }
 384
 385     pub fn impl_item(&self, id: ImplItemId) -> &'hir ImplItem {
 386         self.read(id.node_id);
 387
 388         // NB: intentionally bypass `self.forest.krate()` so that we
 389         // do not trigger a read of the whole krate here
 390         self.forest.krate.impl_item(id)
 391     }
 392
 393     pub fn body(&self, id: BodyId) -> &'hir Body {
 394         self.read(id.node_id);
 395
 396         // NB: intentionally bypass `self.forest.krate()` so that we
 397         // do not trigger a read of the whole krate here
 398         self.forest.krate.body(id)
 399     }
 400
 401     /// Returns the `NodeId` that corresponds to the definition of
 402     /// which this is the body of, i.e. a `fn`, `const` or `static`
 403     /// item (possibly associated), or a closure, or the body itself
 404     /// for embedded constant expressions (e.g. `N` in `[T; N]`).
 405     pub fn body_owner(&self, BodyId { node_id }: BodyId) -> NodeId {
 406         let parent = self.get_parent_node(node_id);
 407         if self.map[parent.as_usize()].is_body_owner(node_id) {
 408             parent
 409         } else {
 410             node_id
 411         }
 412     }
 413
 414     pub fn body_owner_def_id(&self, id: BodyId) -> DefId {
 415         self.local_def_id(self.body_owner(id))
 416     }
 417
 418     /// Given a node id, returns the `BodyId` associated with it,
 419     /// if the node is a body owner, otherwise returns `None`.
 420     pub fn maybe_body_owned_by(&self, id: NodeId) -> Option<BodyId> {
 421         if let Some(entry) = self.find_entry(id) {
 422             if let Some(body_id) = entry.associated_body() {
 423                 // For item-like things and closures, the associated
 424                 // body has its own distinct id, and that is returned
 425                 // by `associated_body`.
 426                 Some(body_id)
 427             } else {
 428                 // For some expressions, the expression is its own body.
 429                 if let EntryExpr(_, _, expr) = entry {
 430                     Some(BodyId { node_id: expr.id })
 431                 } else {
 432                     None
 433                 }
 434             }
 435         } else {
 436             bug!("no entry for id `{}`", id)
 437         }
 438     }
 439
 440     /// Given a body owner's id, returns the `BodyId` associated with it.
 441     pub fn body_owned_by(&self, id: NodeId) -> BodyId {
 442         self.maybe_body_owned_by(id).unwrap_or_else(|| {
 443             span_bug!(self.span(id), "body_owned_by: {} has no associated body",
 444                       self.node_to_string(id));
 445         })
 446     }
 447
 448     pub fn ty_param_owner(&self, id: NodeId) -> NodeId {
 449         match self.get(id) {
 450             NodeItem(&Item { node: ItemTrait(..), .. }) => id,
 451             NodeTyParam(_) => self.get_parent_node(id),
 452             _ => {
 453                 bug!("ty_param_owner: {} not a type parameter",
 454                     self.node_to_string(id))
 455             }
 456         }
 457     }
 458
 459     pub fn ty_param_name(&self, id: NodeId) -> Name {
 460         match self.get(id) {
 461             NodeItem(&Item { node: ItemTrait(..), .. }) => {
 462                 keywords::SelfType.name()
 463             }
 464             NodeTyParam(tp) => tp.name,
 465             _ => {
 466                 bug!("ty_param_name: {} not a type parameter",
 467                     self.node_to_string(id))
 468             }
 469         }
 470     }
 471
 472     pub fn trait_impls(&self, trait_did: DefId) -> &'hir [NodeId] {
 473         self.dep_graph.read(DepNode::new_no_params(DepKind::AllLocalTraitImpls));
 474
 475         // NB: intentionally bypass `self.forest.krate()` so that we
 476         // do not trigger a read of the whole krate here
 477         self.forest.krate.trait_impls.get(&trait_did).map_or(&[], |xs| &xs[..])
 478     }
 479
 480     pub fn trait_default_impl(&self, trait_did: DefId) -> Option<NodeId> {
 481         self.dep_graph.read(DepNode::new_no_params(DepKind::AllLocalTraitImpls));
 482
 483         // NB: intentionally bypass `self.forest.krate()` so that we
 484         // do not trigger a read of the whole krate here
 485         self.forest.krate.trait_default_impl.get(&trait_did).cloned()
 486     }
 487
 488     pub fn trait_is_auto(&self, trait_did: DefId) -> bool {
 489         self.trait_default_impl(trait_did).is_some()
 490     }
 491
 492     /// Get the attributes on the krate. This is preferable to
 493     /// invoking `krate.attrs` because it registers a tighter
 494     /// dep-graph access.
 495     pub fn krate_attrs(&self) -> &'hir [ast::Attribute] {
 496         let def_path_hash = self.definitions.def_path_hash(CRATE_DEF_INDEX);
 497
 498         self.dep_graph.read(def_path_hash.to_dep_node(DepKind::Hir));
 499         &self.forest.krate.attrs
 500     }
 501
 502     /// Retrieve the Node corresponding to `id`, panicking if it cannot
 503     /// be found.
 504     pub fn get(&self, id: NodeId) -> Node<'hir> {
 505         match self.find(id) {
 506             Some(node) => node, // read recorded by `find`
 507             None => bug!("couldn't find node id {} in the AST map", id)
 508         }
 509     }
 510
 511     pub fn get_if_local(&self, id: DefId) -> Option<Node<'hir>> {
 512         self.as_local_node_id(id).map(|id| self.get(id)) // read recorded by `get`
 513     }
 514
 515     /// Retrieve the Node corresponding to `id`, returning None if
 516     /// cannot be found.
 517     pub fn find(&self, id: NodeId) -> Option<Node<'hir>> {
 518         let result = self.find_entry(id).and_then(|x| x.to_node());
 519         if result.is_some() {
 520             self.read(id);
 521         }
 522         result
 523     }
 524
 525     /// Similar to get_parent, returns the parent node id or id if there is no
 526     /// parent. Note that the parent may be CRATE_NODE_ID, which is not itself
 527     /// present in the map -- so passing the return value of get_parent_node to
 528     /// get may actually panic.
 529     /// This function returns the immediate parent in the AST, whereas get_parent
 530     /// returns the enclosing item. Note that this might not be the actual parent
 531     /// node in the AST - some kinds of nodes are not in the map and these will
 532     /// never appear as the parent_node. So you can always walk the parent_nodes
 533     /// from a node to the root of the ast (unless you get the same id back here
 534     /// that can happen if the id is not in the map itself or is just weird).
 535     pub fn get_parent_node(&self, id: NodeId) -> NodeId {
 536         self.find_entry(id).and_then(|x| x.parent_node()).unwrap_or(id)
 537     }
 538
 539     /// Check if the node is an argument. An argument is a local variable whose
 540     /// immediate parent is an item or a closure.
 541     pub fn is_argument(&self, id: NodeId) -> bool {
 542         match self.find(id) {
 543             Some(NodeBinding(_)) => (),
 544             _ => return false,
 545         }
 546         match self.find(self.get_parent_node(id)) {
 547             Some(NodeItem(_)) |
 548             Some(NodeTraitItem(_)) |
 549             Some(NodeImplItem(_)) => true,
 550             Some(NodeExpr(e)) => {
 551                 match e.node {
 552                     ExprClosure(..) => true,
 553                     _ => false,
 554                 }
 555             }
 556             _ => false,
 557         }
 558     }
 559
 560     /// If there is some error when walking the parents (e.g., a node does not
 561     /// have a parent in the map or a node can't be found), then we return the
 562     /// last good node id we found. Note that reaching the crate root (id == 0),
 563     /// is not an error, since items in the crate module have the crate root as
 564     /// parent.
 565     fn walk_parent_nodes<F, F2>(&self,
 566                                 start_id: NodeId,
 567                                 found: F,
 568                                 bail_early: F2)
 569         -> Result<NodeId, NodeId>
 570         where F: Fn(&Node<'hir>) -> bool, F2: Fn(&Node<'hir>) -> bool
 571     {
 572         let mut id = start_id;
 573         loop {
 574             let parent_node = self.get_parent_node(id);
 575             if parent_node == CRATE_NODE_ID {
 576                 return Ok(CRATE_NODE_ID);
 577             }
 578             if parent_node == id {
 579                 return Err(id);
 580             }
 581
 582             let node = self.find_entry(parent_node);
 583             if node.is_none() {
 584                 return Err(id);
 585             }
 586             let node = node.unwrap().to_node();
 587             match node {
 588                 Some(ref node) => {
 589                     if found(node) {
 590                         return Ok(parent_node);
 591                     } else if bail_early(node) {
 592                         return Err(parent_node);
 593                     }
 594                 }
 595                 None => {
 596                     return Err(parent_node);
 597                 }
 598             }
 599             id = parent_node;
 600         }
 601     }
 602
 603     /// Retrieve the NodeId for `id`'s enclosing method, unless there's a
 604     /// `while` or `loop` before reaching it, as block tail returns are not
 605     /// available in them.
 606     ///
 607     /// ```
 608     /// fn foo(x: usize) -> bool {
 609     ///     if x == 1 {
 610     ///         true  // `get_return_block` gets passed the `id` corresponding
 611     ///     } else {  // to this, it will return `foo`'s `NodeId`.
 612     ///         false
 613     ///     }
 614     /// }
 615     /// ```
 616     ///
 617     /// ```
 618     /// fn foo(x: usize) -> bool {
 619     ///     loop {
 620     ///         true  // `get_return_block` gets passed the `id` corresponding
 621     ///     }         // to this, it will return `None`.
 622     ///     false
 623     /// }
 624     /// ```
 625     pub fn get_return_block(&self, id: NodeId) -> Option<NodeId> {
 626         let match_fn = |node: &Node| {
 627             match *node {
 628                 NodeItem(_) |
 629                 NodeForeignItem(_) |
 630                 NodeTraitItem(_) |
 631                 NodeImplItem(_) => true,
 632                 _ => false,
 633             }
 634         };
 635         let match_non_returning_block = |node: &Node| {
 636             match *node {
 637                 NodeExpr(ref expr) => {
 638                     match expr.node {
 639                         ExprWhile(..) | ExprLoop(..) => true,
 640                         _ => false,
 641                     }
 642                 }
 643                 _ => false,
 644             }
 645         };
 646
 647         match self.walk_parent_nodes(id, match_fn, match_non_returning_block) {
 648             Ok(id) => Some(id),
 649             Err(_) => None,
 650         }
 651     }
 652
 653     /// Retrieve the NodeId for `id`'s parent item, or `id` itself if no
 654     /// parent item is in this map. The "parent item" is the closest parent node
 655     /// in the AST which is recorded by the map and is an item, either an item
 656     /// in a module, trait, or impl.
 657     pub fn get_parent(&self, id: NodeId) -> NodeId {
 658         match self.walk_parent_nodes(id, |node| match *node {
 659             NodeItem(_) |
 660             NodeForeignItem(_) |
 661             NodeTraitItem(_) |
 662             NodeImplItem(_) => true,
 663             _ => false,
 664         }, |_| false) {
 665             Ok(id) => id,
 666             Err(id) => id,
 667         }
 668     }
 669
 670     /// Returns the NodeId of `id`'s nearest module parent, or `id` itself if no
 671     /// module parent is in this map.
 672     pub fn get_module_parent(&self, id: NodeId) -> DefId {
 673         let id = match self.walk_parent_nodes(id, |node| match *node {
 674             NodeItem(&Item { node: Item_::ItemMod(_), .. }) => true,
 675             _ => false,
 676         }, |_| false) {
 677             Ok(id) => id,
 678             Err(id) => id,
 679         };
 680         self.local_def_id(id)
 681     }
 682
 683     /// Returns the nearest enclosing scope. A scope is an item or block.
 684     /// FIXME it is not clear to me that all items qualify as scopes - statics
 685     /// and associated types probably shouldn't, for example. Behavior in this
 686     /// regard should be expected to be highly unstable.
 687     pub fn get_enclosing_scope(&self, id: NodeId) -> Option<NodeId> {
 688         match self.walk_parent_nodes(id, |node| match *node {
 689             NodeItem(_) |
 690             NodeForeignItem(_) |
 691             NodeTraitItem(_) |
 692             NodeImplItem(_) |
 693             NodeBlock(_) => true,
 694             _ => false,
 695         }, |_| false) {
 696             Ok(id) => Some(id),
 697             Err(_) => None,
 698         }
 699     }
 700
 701     pub fn get_parent_did(&self, id: NodeId) -> DefId {
 702         self.local_def_id(self.get_parent(id))
 703     }
 704
 705     pub fn get_foreign_abi(&self, id: NodeId) -> Abi {
 706         let parent = self.get_parent(id);
 707         let abi = match self.find_entry(parent) {
 708             Some(EntryItem(_, _, i)) => {
 709                 match i.node {
 710                     ItemForeignMod(ref nm) => Some(nm.abi),
 711                     _ => None
 712                 }
 713             }
 714             _ => None
 715         };
 716         match abi {
 717             Some(abi) => {
 718                 self.read(id); // reveals some of the content of a node
 719                 abi
 720             }
 721             None => bug!("expected foreign mod or inlined parent, found {}",
 722                           self.node_to_string(parent))
 723         }
 724     }
 725
 726     pub fn expect_item(&self, id: NodeId) -> &'hir Item {
 727         match self.find(id) { // read recorded by `find`
 728             Some(NodeItem(item)) => item,
 729             _ => bug!("expected item, found {}", self.node_to_string(id))
 730         }
 731     }
 732
 733     pub fn expect_impl_item(&self, id: NodeId) -> &'hir ImplItem {
 734         match self.find(id) {
 735             Some(NodeImplItem(item)) => item,
 736             _ => bug!("expected impl item, found {}", self.node_to_string(id))
 737         }
 738     }
 739
 740     pub fn expect_trait_item(&self, id: NodeId) -> &'hir TraitItem {
 741         match self.find(id) {
 742             Some(NodeTraitItem(item)) => item,
 743             _ => bug!("expected trait item, found {}", self.node_to_string(id))
 744         }
 745     }
 746
 747     pub fn expect_variant_data(&self, id: NodeId) -> &'hir VariantData {
 748         match self.find(id) {
 749             Some(NodeItem(i)) => {
 750                 match i.node {
 751                     ItemStruct(ref struct_def, _) |
 752                     ItemUnion(ref struct_def, _) => struct_def,
 753                     _ => {
 754                         bug!("struct ID bound to non-struct {}",
 755                              self.node_to_string(id));
 756                     }
 757                 }
 758             }
 759             Some(NodeStructCtor(data)) => data,
 760             Some(NodeVariant(variant)) => &variant.node.data,
 761             _ => {
 762                 bug!("expected struct or variant, found {}",
 763                      self.node_to_string(id));
 764             }
 765         }
 766     }
 767
 768     pub fn expect_variant(&self, id: NodeId) -> &'hir Variant {
 769         match self.find(id) {
 770             Some(NodeVariant(variant)) => variant,
 771             _ => bug!("expected variant, found {}", self.node_to_string(id)),
 772         }
 773     }
 774
 775     pub fn expect_foreign_item(&self, id: NodeId) -> &'hir ForeignItem {
 776         match self.find(id) {
 777             Some(NodeForeignItem(item)) => item,
 778             _ => bug!("expected foreign item, found {}", self.node_to_string(id))
 779         }
 780     }
 781
 782     pub fn expect_expr(&self, id: NodeId) -> &'hir Expr {
 783         match self.find(id) { // read recorded by find
 784             Some(NodeExpr(expr)) => expr,
 785             _ => bug!("expected expr, found {}", self.node_to_string(id))
 786         }
 787     }
 788
 789     pub fn get_inlined_body_untracked(&self, def_id: DefId) -> Option<&'hir Body> {
 790         self.inlined_bodies.borrow().get(&def_id).cloned()
 791     }
 792
 793     pub fn intern_inlined_body(&self, def_id: DefId, body: Body) -> &'hir Body {
 794         let body = self.forest.inlined_bodies.alloc(body);
 795         self.inlined_bodies.borrow_mut().insert(def_id, body);
 796         body
 797     }
 798
 799     /// Returns the name associated with the given NodeId's AST.
 800     pub fn name(&self, id: NodeId) -> Name {
 801         match self.get(id) {
 802             NodeItem(i) => i.name,
 803             NodeForeignItem(i) => i.name,
 804             NodeImplItem(ii) => ii.name,
 805             NodeTraitItem(ti) => ti.name,
 806             NodeVariant(v) => v.node.name,
 807             NodeField(f) => f.name,
 808             NodeLifetime(lt) => lt.name,
 809             NodeTyParam(tp) => tp.name,
 810             NodeBinding(&Pat { node: PatKind::Binding(_,_,l,_), .. }) => l.node,
 811             NodeStructCtor(_) => self.name(self.get_parent(id)),
 812             _ => bug!("no name for {}", self.node_to_string(id))
 813         }
 814     }
 815
 816     /// Given a node ID, get a list of attributes associated with the AST
 817     /// corresponding to the Node ID
 818     pub fn attrs(&self, id: NodeId) -> &'hir [ast::Attribute] {
 819         self.read(id); // reveals attributes on the node
 820         let attrs = match self.find(id) {
 821             Some(NodeItem(i)) => Some(&i.attrs[..]),
 822             Some(NodeForeignItem(fi)) => Some(&fi.attrs[..]),
 823             Some(NodeTraitItem(ref ti)) => Some(&ti.attrs[..]),
 824             Some(NodeImplItem(ref ii)) => Some(&ii.attrs[..]),
 825             Some(NodeVariant(ref v)) => Some(&v.node.attrs[..]),
 826             Some(NodeField(ref f)) => Some(&f.attrs[..]),
 827             Some(NodeExpr(ref e)) => Some(&*e.attrs),
 828             Some(NodeStmt(ref s)) => Some(s.node.attrs()),
 829             // unit/tuple structs take the attributes straight from
 830             // the struct definition.
 831             Some(NodeStructCtor(_)) => {
 832                 return self.attrs(self.get_parent(id));
 833             }
 834             _ => None
 835         };
 836         attrs.unwrap_or(&[])
 837     }
 838
 839     /// Returns an iterator that yields the node id's with paths that
 840     /// match `parts`.  (Requires `parts` is non-empty.)
 841     ///
 842     /// For example, if given `parts` equal to `["bar", "quux"]`, then
 843     /// the iterator will produce node id's for items with paths
 844     /// such as `foo::bar::quux`, `bar::quux`, `other::bar::quux`, and
 845     /// any other such items it can find in the map.
 846     pub fn nodes_matching_suffix<'a>(&'a self, parts: &'a [String])
 847                                  -> NodesMatchingSuffix<'a, 'hir> {
 848         NodesMatchingSuffix {
 849             map: self,
 850             item_name: parts.last().unwrap(),
 851             in_which: &parts[..parts.len() - 1],
 852             idx: CRATE_NODE_ID,
 853         }
 854     }
 855
 856     pub fn span(&self, id: NodeId) -> Span {
 857         self.read(id); // reveals span from node
 858         match self.find_entry(id) {
 859             Some(EntryItem(_, _, item)) => item.span,
 860             Some(EntryForeignItem(_, _, foreign_item)) => foreign_item.span,
 861             Some(EntryTraitItem(_, _, trait_method)) => trait_method.span,
 862             Some(EntryImplItem(_, _, impl_item)) => impl_item.span,
 863             Some(EntryVariant(_, _, variant)) => variant.span,
 864             Some(EntryField(_, _, field)) => field.span,
 865             Some(EntryExpr(_, _, expr)) => expr.span,
 866             Some(EntryStmt(_, _, stmt)) => stmt.span,
 867             Some(EntryTy(_, _, ty)) => ty.span,
 868             Some(EntryTraitRef(_, _, tr)) => tr.path.span,
 869             Some(EntryBinding(_, _, pat)) => pat.span,
 870             Some(EntryPat(_, _, pat)) => pat.span,
 871             Some(EntryBlock(_, _, block)) => block.span,
 872             Some(EntryStructCtor(_, _, _)) => self.expect_item(self.get_parent(id)).span,
 873             Some(EntryLifetime(_, _, lifetime)) => lifetime.span,
 874             Some(EntryTyParam(_, _, ty_param)) => ty_param.span,
 875             Some(EntryVisibility(_, _, &Visibility::Restricted { ref path, .. })) => path.span,
 876             Some(EntryVisibility(_, _, v)) => bug!("unexpected Visibility {:?}", v),
 877             Some(EntryLocal(_, _, local)) => local.span,
 878
 879             Some(RootCrate(_)) => self.forest.krate.span,
 880             Some(NotPresent) | None => {
 881                 // Some nodes, notably macro definitions, are not
 882                 // present in the map for whatever reason, but
 883                 // they *do* have def-ids. So if we encounter an
 884                 // empty hole, check for that case.
 885                 if let Some(def_index) = self.definitions.opt_def_index(id) {
 886                     let def_path_hash = self.definitions.def_path_hash(def_index);
 887                     self.dep_graph.read(def_path_hash.to_dep_node(DepKind::Hir));
 888                     DUMMY_SP
 889                 } else {
 890                     bug!("hir::map::Map::span: id not in map: {:?}", id)
 891                 }
 892             }
 893         }
 894     }
 895
 896     pub fn span_if_local(&self, id: DefId) -> Option<Span> {
 897         self.as_local_node_id(id).map(|id| self.span(id))
 898     }
 899
 900     pub fn node_to_string(&self, id: NodeId) -> String {
 901         node_id_to_string(self, id, true)
 902     }
 903
 904     pub fn node_to_user_string(&self, id: NodeId) -> String {
 905         node_id_to_string(self, id, false)
 906     }
 907
 908     pub fn node_to_pretty_string(&self, id: NodeId) -> String {
 909         print::to_string(self, |s| s.print_node(self.get(id)))
 910     }
 911 }
 912
 913 pub struct NodesMatchingSuffix<'a, 'hir:'a> {
 914     map: &'a Map<'hir>,
 915     item_name: &'a String,
 916     in_which: &'a [String],
 917     idx: NodeId,
 918 }
 919
 920 impl<'a, 'hir> NodesMatchingSuffix<'a, 'hir> {
 921     /// Returns true only if some suffix of the module path for parent
 922     /// matches `self.in_which`.
 923     ///
 924     /// In other words: let `[x_0,x_1,...,x_k]` be `self.in_which`;
 925     /// returns true if parent's path ends with the suffix
 926     /// `x_0::x_1::...::x_k`.
 927     fn suffix_matches(&self, parent: NodeId) -> bool {
 928         let mut cursor = parent;
 929         for part in self.in_which.iter().rev() {
 930             let (mod_id, mod_name) = match find_first_mod_parent(self.map, cursor) {
 931                 None => return false,
 932                 Some((node_id, name)) => (node_id, name),
 933             };
 934             if mod_name != &**part {
 935                 return false;
 936             }
 937             cursor = self.map.get_parent(mod_id);
 938         }
 939         return true;
 940
 941         // Finds the first mod in parent chain for `id`, along with
 942         // that mod's name.
 943         //
 944         // If `id` itself is a mod named `m` with parent `p`, then
 945         // returns `Some(id, m, p)`.  If `id` has no mod in its parent
 946         // chain, then returns `None`.
 947         fn find_first_mod_parent<'a>(map: &'a Map, mut id: NodeId) -> Option<(NodeId, Name)> {
 948             loop {
 949                 match map.find(id) {
 950                     None => return None,
 951                     Some(NodeItem(item)) if item_is_mod(&item) =>
 952                         return Some((id, item.name)),
 953                     _ => {}
 954                 }
 955                 let parent = map.get_parent(id);
 956                 if parent == id { return None }
 957                 id = parent;
 958             }
 959
 960             fn item_is_mod(item: &Item) -> bool {
 961                 match item.node {
 962                     ItemMod(_) => true,
 963                     _ => false,
 964                 }
 965             }
 966         }
 967     }
 968
 969     // We are looking at some node `n` with a given name and parent
 970     // id; do their names match what I am seeking?
 971     fn matches_names(&self, parent_of_n: NodeId, name: Name) -> bool {
 972         name == &**self.item_name && self.suffix_matches(parent_of_n)
 973     }
 974 }
 975
 976 impl<'a, 'hir> Iterator for NodesMatchingSuffix<'a, 'hir> {
 977     type Item = NodeId;
 978
 979     fn next(&mut self) -> Option<NodeId> {
 980         loop {
 981             let idx = self.idx;
 982             if idx.as_usize() >= self.map.entry_count() {
 983                 return None;
 984             }
 985             self.idx = NodeId::from_u32(self.idx.as_u32() + 1);
 986             let name = match self.map.find_entry(idx) {
 987                 Some(EntryItem(_, _, n))       => n.name(),
 988                 Some(EntryForeignItem(_, _, n))=> n.name(),
 989                 Some(EntryTraitItem(_, _, n))  => n.name(),
 990                 Some(EntryImplItem(_, _, n))   => n.name(),
 991                 Some(EntryVariant(_, _, n))    => n.name(),
 992                 Some(EntryField(_, _, n))      => n.name(),
 993                 _ => continue,
 994             };
 995             if self.matches_names(self.map.get_parent(idx), name) {
 996                 return Some(idx)
 997             }
 998         }
 999     }
1000 }
1001
1002 trait Named {
1003     fn name(&self) -> Name;
1004 }
1005
1006 impl<T:Named> Named for Spanned<T> { fn name(&self) -> Name { self.node.name() } }
1007
1008 impl Named for Item { fn name(&self) -> Name { self.name } }
1009 impl Named for ForeignItem { fn name(&self) -> Name { self.name } }
1010 impl Named for Variant_ { fn name(&self) -> Name { self.name } }
1011 impl Named for StructField { fn name(&self) -> Name { self.name } }
1012 impl Named for TraitItem { fn name(&self) -> Name { self.name } }
1013 impl Named for ImplItem { fn name(&self) -> Name { self.name } }
1014
1015 pub fn map_crate<'hir>(forest: &'hir mut Forest,
1016                        definitions: Definitions)
1017                        -> Map<'hir> {
1018     let map = {
1019         let mut collector = NodeCollector::root(&forest.krate,
1020                                                 &forest.dep_graph,
1021                                                 &definitions);
1022         intravisit::walk_crate(&mut collector, &forest.krate);
1023         collector.into_map()
1024     };
1025
1026     if log_enabled!(::log::LogLevel::Debug) {
1027         // This only makes sense for ordered stores; note the
1028         // enumerate to count the number of entries.
1029         let (entries_less_1, _) = map.iter().filter(|&x| {
1030             match *x {
1031                 NotPresent => false,
1032                 _ => true
1033             }
1034         }).enumerate().last().expect("AST map was empty after folding?");
1035
1036         let entries = entries_less_1 + 1;
1037         let vector_length = map.len();
1038         debug!("The AST map has {} entries with a maximum of {}: occupancy {:.1}%",
1039               entries, vector_length, (entries as f64 / vector_length as f64) * 100.);
1040     }
1041
1042     // Build the reverse mapping of `node_to_hir_id`.
1043     let hir_to_node_id = definitions.node_to_hir_id.iter_enumerated()
1044         .map(|(node_id, &hir_id)| (hir_id, node_id)).collect();
1045
1046     let map = Map {
1047         forest,
1048         dep_graph: forest.dep_graph.clone(),
1049         map,
1050         hir_to_node_id,
1051         definitions,
1052         inlined_bodies: RefCell::new(DefIdMap()),
1053     };
1054
1055     hir_id_validator::check_crate(&map);
1056
1057     map
1058 }
1059
1060 /// Identical to the `PpAnn` implementation for `hir::Crate`,
1061 /// except it avoids creating a dependency on the whole crate.
1062 impl<'hir> print::PpAnn for Map<'hir> {
1063     fn nested(&self, state: &mut print::State, nested: print::Nested) -> io::Result<()> {
1064         match nested {
1065             Nested::Item(id) => state.print_item(self.expect_item(id.id)),
1066             Nested::TraitItem(id) => state.print_trait_item(self.trait_item(id)),
1067             Nested::ImplItem(id) => state.print_impl_item(self.impl_item(id)),
1068             Nested::Body(id) => state.print_expr(&self.body(id).value),
1069             Nested::BodyArgPat(id, i) => state.print_pat(&self.body(id).arguments[i].pat)
1070         }
1071     }
1072 }
1073
1074 impl<'a> print::State<'a> {
1075     pub fn print_node(&mut self, node: Node) -> io::Result<()> {
1076         match node {
1077             NodeItem(a)        => self.print_item(&a),
1078             NodeForeignItem(a) => self.print_foreign_item(&a),
1079             NodeTraitItem(a)   => self.print_trait_item(a),
1080             NodeImplItem(a)    => self.print_impl_item(a),
1081             NodeVariant(a)     => self.print_variant(&a),
1082             NodeExpr(a)        => self.print_expr(&a),
1083             NodeStmt(a)        => self.print_stmt(&a),
1084             NodeTy(a)          => self.print_type(&a),
1085             NodeTraitRef(a)    => self.print_trait_ref(&a),
1086             NodeBinding(a)       |
1087             NodePat(a)         => self.print_pat(&a),
1088             NodeBlock(a)       => {
1089                 use syntax::print::pprust::PrintState;
1090
1091                 // containing cbox, will be closed by print-block at }
1092                 self.cbox(print::indent_unit)?;
1093                 // head-ibox, will be closed by print-block after {
1094                 self.ibox(0)?;
1095                 self.print_block(&a)
1096             }
1097             NodeLifetime(a)    => self.print_lifetime(&a),
1098             NodeVisibility(a)  => self.print_visibility(&a),
1099             NodeTyParam(_)     => bug!("cannot print TyParam"),
1100             NodeField(_)       => bug!("cannot print StructField"),
1101             // these cases do not carry enough information in the
1102             // hir_map to reconstruct their full structure for pretty
1103             // printing.
1104             NodeStructCtor(_)  => bug!("cannot print isolated StructCtor"),
1105             NodeLocal(a)       => self.print_local_decl(&a),
1106         }
1107     }
1108 }
1109
1110 fn node_id_to_string(map: &Map, id: NodeId, include_id: bool) -> String {
1111     let id_str = format!(" (id={})", id);
1112     let id_str = if include_id { &id_str[..] } else { "" };
1113
1114     let path_str = || {
1115         // This functionality is used for debugging, try to use TyCtxt to get
1116         // the user-friendly path, otherwise fall back to stringifying DefPath.
1117         ::ty::tls::with_opt(|tcx| {
1118             if let Some(tcx) = tcx {
1119                 tcx.node_path_str(id)
1120             } else if let Some(path) = map.def_path_from_id(id) {
1121                 path.data.into_iter().map(|elem| {
1122                     elem.data.to_string()
1123                 }).collect::<Vec<_>>().join("::")
1124             } else {
1125                 String::from("<missing path>")
1126             }
1127         })
1128     };
1129
1130     match map.find(id) {
1131         Some(NodeItem(item)) => {
1132             let item_str = match item.node {
1133                 ItemExternCrate(..) => "extern crate",
1134                 ItemUse(..) => "use",
1135                 ItemStatic(..) => "static",
1136                 ItemConst(..) => "const",
1137                 ItemFn(..) => "fn",
1138                 ItemMod(..) => "mod",
1139                 ItemForeignMod(..) => "foreign mod",
1140                 ItemGlobalAsm(..) => "global asm",
1141                 ItemTy(..) => "ty",
1142                 ItemEnum(..) => "enum",
1143                 ItemStruct(..) => "struct",
1144                 ItemUnion(..) => "union",
1145                 ItemTrait(..) => "trait",
1146                 ItemImpl(..) => "impl",
1147                 ItemDefaultImpl(..) => "default impl",
1148             };
1149             format!("{} {}{}", item_str, path_str(), id_str)
1150         }
1151         Some(NodeForeignItem(_)) => {
1152             format!("foreign item {}{}", path_str(), id_str)
1153         }
1154         Some(NodeImplItem(ii)) => {
1155             match ii.node {
1156                 ImplItemKind::Const(..) => {
1157                     format!("assoc const {} in {}{}", ii.name, path_str(), id_str)
1158                 }
1159                 ImplItemKind::Method(..) => {
1160                     format!("method {} in {}{}", ii.name, path_str(), id_str)
1161                 }
1162                 ImplItemKind::Type(_) => {
1163                     format!("assoc type {} in {}{}", ii.name, path_str(), id_str)
1164                 }
1165             }
1166         }
1167         Some(NodeTraitItem(ti)) => {
1168             let kind = match ti.node {
1169                 TraitItemKind::Const(..) => "assoc constant",
1170                 TraitItemKind::Method(..) => "trait method",
1171                 TraitItemKind::Type(..) => "assoc type",
1172             };
1173
1174             format!("{} {} in {}{}", kind, ti.name, path_str(), id_str)
1175         }
1176         Some(NodeVariant(ref variant)) => {
1177             format!("variant {} in {}{}",
1178                     variant.node.name,
1179                     path_str(), id_str)
1180         }
1181         Some(NodeField(ref field)) => {
1182             format!("field {} in {}{}",
1183                     field.name,
1184                     path_str(), id_str)
1185         }
1186         Some(NodeExpr(_)) => {
1187             format!("expr {}{}", map.node_to_pretty_string(id), id_str)
1188         }
1189         Some(NodeStmt(_)) => {
1190             format!("stmt {}{}", map.node_to_pretty_string(id), id_str)
1191         }
1192         Some(NodeTy(_)) => {
1193             format!("type {}{}", map.node_to_pretty_string(id), id_str)
1194         }
1195         Some(NodeTraitRef(_)) => {
1196             format!("trait_ref {}{}", map.node_to_pretty_string(id), id_str)
1197         }
1198         Some(NodeBinding(_)) => {
1199             format!("local {}{}", map.node_to_pretty_string(id), id_str)
1200         }
1201         Some(NodePat(_)) => {
1202             format!("pat {}{}", map.node_to_pretty_string(id), id_str)
1203         }
1204         Some(NodeBlock(_)) => {
1205             format!("block {}{}", map.node_to_pretty_string(id), id_str)
1206         }
1207         Some(NodeLocal(_)) => {
1208             format!("local {}{}", map.node_to_pretty_string(id), id_str)
1209         }
1210         Some(NodeStructCtor(_)) => {
1211             format!("struct_ctor {}{}", path_str(), id_str)
1212         }
1213         Some(NodeLifetime(_)) => {
1214             format!("lifetime {}{}", map.node_to_pretty_string(id), id_str)
1215         }
1216         Some(NodeTyParam(ref ty_param)) => {
1217             format!("typaram {:?}{}", ty_param, id_str)
1218         }
1219         Some(NodeVisibility(ref vis)) => {
1220             format!("visibility {:?}{}", vis, id_str)
1221         }
1222         None => {
1223             format!("unknown node{}", id_str)
1224         }
1225     }
1226 }