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 use self::def_collector::DefCollector;
  15 pub use self::definitions::{Definitions, DefKey, DefPath, DefPathData,
  16                             DisambiguatedDefPathData, InlinedRootPath};
  17
  18 use dep_graph::{DepGraph, DepNode};
  19
  20 use middle::cstore::InlinedItem;
  21 use middle::cstore::InlinedItem as II;
  22 use hir::def_id::{CRATE_DEF_INDEX, DefId, DefIndex};
  23
  24 use syntax::abi::Abi;
  25 use syntax::ast::{self, Name, NodeId, DUMMY_NODE_ID, };
  26 use syntax::codemap::Spanned;
  27 use syntax_pos::Span;
  28
  29 use hir::*;
  30 use hir::fold::Folder;
  31 use hir::print as pprust;
  32
  33 use arena::TypedArena;
  34 use std::cell::RefCell;
  35 use std::cmp;
  36 use std::io;
  37 use std::mem;
  38
  39 pub mod blocks;
  40 mod collector;
  41 mod def_collector;
  42 pub mod definitions;
  43
  44 #[derive(Copy, Clone, Debug)]
  45 pub enum Node<'ast> {
  46     NodeItem(&'ast Item),
  47     NodeForeignItem(&'ast ForeignItem),
  48     NodeTraitItem(&'ast TraitItem),
  49     NodeImplItem(&'ast ImplItem),
  50     NodeVariant(&'ast Variant),
  51     NodeExpr(&'ast Expr),
  52     NodeStmt(&'ast Stmt),
  53     NodeLocal(&'ast Pat),
  54     NodePat(&'ast Pat),
  55     NodeBlock(&'ast Block),
  56
  57     /// NodeStructCtor represents a tuple struct.
  58     NodeStructCtor(&'ast VariantData),
  59
  60     NodeLifetime(&'ast Lifetime),
  61     NodeTyParam(&'ast TyParam)
  62 }
  63
  64 /// Represents an entry and its parent NodeID.
  65 /// The odd layout is to bring down the total size.
  66 #[derive(Copy, Debug)]
  67 pub enum MapEntry<'ast> {
  68     /// Placeholder for holes in the map.
  69     NotPresent,
  70
  71     /// All the node types, with a parent ID.
  72     EntryItem(NodeId, &'ast Item),
  73     EntryForeignItem(NodeId, &'ast ForeignItem),
  74     EntryTraitItem(NodeId, &'ast TraitItem),
  75     EntryImplItem(NodeId, &'ast ImplItem),
  76     EntryVariant(NodeId, &'ast Variant),
  77     EntryExpr(NodeId, &'ast Expr),
  78     EntryStmt(NodeId, &'ast Stmt),
  79     EntryLocal(NodeId, &'ast Pat),
  80     EntryPat(NodeId, &'ast Pat),
  81     EntryBlock(NodeId, &'ast Block),
  82     EntryStructCtor(NodeId, &'ast VariantData),
  83     EntryLifetime(NodeId, &'ast Lifetime),
  84     EntryTyParam(NodeId, &'ast TyParam),
  85
  86     /// Roots for node trees.
  87     RootCrate,
  88     RootInlinedParent(&'ast InlinedItem)
  89 }
  90
  91 impl<'ast> Clone for MapEntry<'ast> {
  92     fn clone(&self) -> MapEntry<'ast> {
  93         *self
  94     }
  95 }
  96
  97 impl<'ast> MapEntry<'ast> {
  98     fn from_node(p: NodeId, node: Node<'ast>) -> MapEntry<'ast> {
  99         match node {
 100             NodeItem(n) => EntryItem(p, n),
 101             NodeForeignItem(n) => EntryForeignItem(p, n),
 102             NodeTraitItem(n) => EntryTraitItem(p, n),
 103             NodeImplItem(n) => EntryImplItem(p, n),
 104             NodeVariant(n) => EntryVariant(p, n),
 105             NodeExpr(n) => EntryExpr(p, n),
 106             NodeStmt(n) => EntryStmt(p, n),
 107             NodeLocal(n) => EntryLocal(p, n),
 108             NodePat(n) => EntryPat(p, n),
 109             NodeBlock(n) => EntryBlock(p, n),
 110             NodeStructCtor(n) => EntryStructCtor(p, n),
 111             NodeLifetime(n) => EntryLifetime(p, n),
 112             NodeTyParam(n) => EntryTyParam(p, n),
 113         }
 114     }
 115
 116     fn parent_node(self) -> Option<NodeId> {
 117         Some(match self {
 118             EntryItem(id, _) => id,
 119             EntryForeignItem(id, _) => id,
 120             EntryTraitItem(id, _) => id,
 121             EntryImplItem(id, _) => id,
 122             EntryVariant(id, _) => id,
 123             EntryExpr(id, _) => id,
 124             EntryStmt(id, _) => id,
 125             EntryLocal(id, _) => id,
 126             EntryPat(id, _) => id,
 127             EntryBlock(id, _) => id,
 128             EntryStructCtor(id, _) => id,
 129             EntryLifetime(id, _) => id,
 130             EntryTyParam(id, _) => id,
 131
 132             NotPresent |
 133             RootCrate |
 134             RootInlinedParent(_) => return None,
 135         })
 136     }
 137
 138     fn to_node(self) -> Option<Node<'ast>> {
 139         Some(match self {
 140             EntryItem(_, n) => NodeItem(n),
 141             EntryForeignItem(_, n) => NodeForeignItem(n),
 142             EntryTraitItem(_, n) => NodeTraitItem(n),
 143             EntryImplItem(_, n) => NodeImplItem(n),
 144             EntryVariant(_, n) => NodeVariant(n),
 145             EntryExpr(_, n) => NodeExpr(n),
 146             EntryStmt(_, n) => NodeStmt(n),
 147             EntryLocal(_, n) => NodeLocal(n),
 148             EntryPat(_, n) => NodePat(n),
 149             EntryBlock(_, n) => NodeBlock(n),
 150             EntryStructCtor(_, n) => NodeStructCtor(n),
 151             EntryLifetime(_, n) => NodeLifetime(n),
 152             EntryTyParam(_, n) => NodeTyParam(n),
 153             _ => return None
 154         })
 155     }
 156 }
 157
 158 /// Stores a crate and any number of inlined items from other crates.
 159 pub struct Forest {
 160     krate: Crate,
 161     pub dep_graph: DepGraph,
 162     inlined_items: TypedArena<InlinedItem>
 163 }
 164
 165 impl Forest {
 166     pub fn new(krate: Crate, dep_graph: &DepGraph) -> Forest {
 167         Forest {
 168             krate: krate,
 169             dep_graph: dep_graph.clone(),
 170             inlined_items: TypedArena::new()
 171         }
 172     }
 173
 174     pub fn krate<'ast>(&'ast self) -> &'ast Crate {
 175         self.dep_graph.read(DepNode::Krate);
 176         &self.krate
 177     }
 178 }
 179
 180 /// Represents a mapping from Node IDs to AST elements and their parent
 181 /// Node IDs
 182 #[derive(Clone)]
 183 pub struct Map<'ast> {
 184     /// The backing storage for all the AST nodes.
 185     pub forest: &'ast Forest,
 186
 187     /// Same as the dep_graph in forest, just available with one fewer
 188     /// deref. This is a gratuitious micro-optimization.
 189     pub dep_graph: DepGraph,
 190
 191     /// NodeIds are sequential integers from 0, so we can be
 192     /// super-compact by storing them in a vector. Not everything with
 193     /// a NodeId is in the map, but empirically the occupancy is about
 194     /// 75-80%, so there's not too much overhead (certainly less than
 195     /// a hashmap, since they (at the time of writing) have a maximum
 196     /// of 75% occupancy).
 197     ///
 198     /// Also, indexing is pretty quick when you've got a vector and
 199     /// plain old integers.
 200     map: RefCell<Vec<MapEntry<'ast>>>,
 201
 202     definitions: RefCell<Definitions>,
 203
 204     /// All NodeIds that are numerically greater or equal to this value come
 205     /// from inlined items.
 206     local_node_id_watermark: NodeId,
 207
 208     /// All def-indices that are numerically greater or equal to this value come
 209     /// from inlined items.
 210     local_def_id_watermark: usize,
 211 }
 212
 213 impl<'ast> Map<'ast> {
 214     pub fn is_inlined_def_id(&self, id: DefId) -> bool {
 215         id.is_local() && id.index.as_usize() >= self.local_def_id_watermark
 216     }
 217
 218     pub fn is_inlined_node_id(&self, id: NodeId) -> bool {
 219         id >= self.local_node_id_watermark
 220     }
 221
 222     /// Registers a read in the dependency graph of the AST node with
 223     /// the given `id`. This needs to be called each time a public
 224     /// function returns the HIR for a node -- in other words, when it
 225     /// "reveals" the content of a node to the caller (who might not
 226     /// otherwise have had access to those contents, and hence needs a
 227     /// read recorded). If the function just returns a DefId or
 228     /// NodeId, no actual content was returned, so no read is needed.
 229     fn read(&self, id: NodeId) {
 230         self.dep_graph.read(self.dep_node(id));
 231     }
 232
 233     fn dep_node(&self, id0: NodeId) -> DepNode<DefId> {
 234         let map = self.map.borrow();
 235         let mut id = id0;
 236         loop {
 237             match map[id as usize] {
 238                 EntryItem(_, item) => {
 239                     let def_id = self.local_def_id(item.id);
 240                     // NB                          ^~~~~~~
 241                     //
 242                     // You would expect that `item.id == id`, but this
 243                     // is not always the case. In particular, for a
 244                     // ViewPath item like `use self::{mem, foo}`, we
 245                     // map the ids for `mem` and `foo` to the
 246                     // enclosing view path item. This seems mega super
 247                     // ultra wrong, but then who am I to judge?
 248                     // -nmatsakis
 249                     return DepNode::Hir(def_id);
 250                 }
 251
 252                 EntryForeignItem(p, _) |
 253                 EntryTraitItem(p, _) |
 254                 EntryImplItem(p, _) |
 255                 EntryVariant(p, _) |
 256                 EntryExpr(p, _) |
 257                 EntryStmt(p, _) |
 258                 EntryLocal(p, _) |
 259                 EntryPat(p, _) |
 260                 EntryBlock(p, _) |
 261                 EntryStructCtor(p, _) |
 262                 EntryLifetime(p, _) |
 263                 EntryTyParam(p, _) =>
 264                     id = p,
 265
 266                 RootCrate |
 267                 RootInlinedParent(_) =>
 268                     // FIXME(#32015) clarify story about cross-crate dep tracking
 269                     return DepNode::Krate,
 270
 271                 NotPresent =>
 272                     // Some nodes, notably struct fields, are not
 273                     // present in the map for whatever reason, but
 274                     // they *do* have def-ids. So if we encounter an
 275                     // empty hole, check for that case.
 276                     return self.opt_local_def_id(id)
 277                                .map(|def_id| DepNode::Hir(def_id))
 278                                .unwrap_or_else(|| {
 279                                    bug!("Walking parents from `{}` \
 280                                          led to `NotPresent` at `{}`",
 281                                         id0, id)
 282                                }),
 283             }
 284         }
 285     }
 286
 287     pub fn num_local_def_ids(&self) -> usize {
 288         self.definitions.borrow().len()
 289     }
 290
 291     pub fn def_key(&self, def_id: DefId) -> DefKey {
 292         assert!(def_id.is_local());
 293         self.definitions.borrow().def_key(def_id.index)
 294     }
 295
 296     pub fn def_path_from_id(&self, id: NodeId) -> Option<DefPath> {
 297         self.opt_local_def_id(id).map(|def_id| {
 298             self.def_path(def_id)
 299         })
 300     }
 301
 302     pub fn def_path(&self, def_id: DefId) -> DefPath {
 303         assert!(def_id.is_local());
 304         self.definitions.borrow().def_path(def_id.index)
 305     }
 306
 307     pub fn def_index_for_def_key(&self, def_key: DefKey) -> Option<DefIndex> {
 308         self.definitions.borrow().def_index_for_def_key(def_key)
 309     }
 310
 311     pub fn local_def_id(&self, node: NodeId) -> DefId {
 312         self.opt_local_def_id(node).unwrap_or_else(|| {
 313             bug!("local_def_id: no entry for `{}`, which has a map of `{:?}`",
 314                  node, self.find_entry(node))
 315         })
 316     }
 317
 318     pub fn opt_local_def_id(&self, node: NodeId) -> Option<DefId> {
 319         self.definitions.borrow().opt_local_def_id(node)
 320     }
 321
 322     pub fn as_local_node_id(&self, def_id: DefId) -> Option<NodeId> {
 323         self.definitions.borrow().as_local_node_id(def_id)
 324     }
 325
 326     fn entry_count(&self) -> usize {
 327         self.map.borrow().len()
 328     }
 329
 330     fn find_entry(&self, id: NodeId) -> Option<MapEntry<'ast>> {
 331         self.map.borrow().get(id as usize).cloned()
 332     }
 333
 334     pub fn krate(&self) -> &'ast Crate {
 335         self.forest.krate()
 336     }
 337
 338     /// Get the attributes on the krate. This is preferable to
 339     /// invoking `krate.attrs` because it registers a tighter
 340     /// dep-graph access.
 341     pub fn krate_attrs(&self) -> &'ast [ast::Attribute] {
 342         let crate_root_def_id = DefId::local(CRATE_DEF_INDEX);
 343         self.dep_graph.read(DepNode::Hir(crate_root_def_id));
 344         &self.forest.krate.attrs
 345     }
 346
 347     /// Retrieve the Node corresponding to `id`, panicking if it cannot
 348     /// be found.
 349     pub fn get(&self, id: NodeId) -> Node<'ast> {
 350         match self.find(id) {
 351             Some(node) => node, // read recorded by `find`
 352             None => bug!("couldn't find node id {} in the AST map", id)
 353         }
 354     }
 355
 356     pub fn get_if_local(&self, id: DefId) -> Option<Node<'ast>> {
 357         self.as_local_node_id(id).map(|id| self.get(id)) // read recorded by `get`
 358     }
 359
 360     /// Retrieve the Node corresponding to `id`, returning None if
 361     /// cannot be found.
 362     pub fn find(&self, id: NodeId) -> Option<Node<'ast>> {
 363         let result = self.find_entry(id).and_then(|x| x.to_node());
 364         if result.is_some() {
 365             self.read(id);
 366         }
 367         result
 368     }
 369
 370     /// Similar to get_parent, returns the parent node id or id if there is no
 371     /// parent.
 372     /// This function returns the immediate parent in the AST, whereas get_parent
 373     /// returns the enclosing item. Note that this might not be the actual parent
 374     /// node in the AST - some kinds of nodes are not in the map and these will
 375     /// never appear as the parent_node. So you can always walk the parent_nodes
 376     /// from a node to the root of the ast (unless you get the same id back here
 377     /// that can happen if the id is not in the map itself or is just weird).
 378     pub fn get_parent_node(&self, id: NodeId) -> NodeId {
 379         self.find_entry(id).and_then(|x| x.parent_node()).unwrap_or(id)
 380     }
 381
 382     /// Check if the node is an argument. An argument is a local variable whose
 383     /// immediate parent is an item or a closure.
 384     pub fn is_argument(&self, id: NodeId) -> bool {
 385         match self.find(id) {
 386             Some(NodeLocal(_)) => (),
 387             _ => return false,
 388         }
 389         match self.find(self.get_parent_node(id)) {
 390             Some(NodeItem(_)) |
 391             Some(NodeTraitItem(_)) |
 392             Some(NodeImplItem(_)) => true,
 393             Some(NodeExpr(e)) => {
 394                 match e.node {
 395                     ExprClosure(..) => true,
 396                     _ => false,
 397                 }
 398             }
 399             _ => false,
 400         }
 401     }
 402
 403     /// If there is some error when walking the parents (e.g., a node does not
 404     /// have a parent in the map or a node can't be found), then we return the
 405     /// last good node id we found. Note that reaching the crate root (id == 0),
 406     /// is not an error, since items in the crate module have the crate root as
 407     /// parent.
 408     fn walk_parent_nodes<F>(&self, start_id: NodeId, found: F) -> Result<NodeId, NodeId>
 409         where F: Fn(&Node<'ast>) -> bool
 410     {
 411         let mut id = start_id;
 412         loop {
 413             let parent_node = self.get_parent_node(id);
 414             if parent_node == 0 {
 415                 return Ok(0);
 416             }
 417             if parent_node == id {
 418                 return Err(id);
 419             }
 420
 421             let node = self.find_entry(parent_node);
 422             if node.is_none() {
 423                 return Err(id);
 424             }
 425             let node = node.unwrap().to_node();
 426             match node {
 427                 Some(ref node) => {
 428                     if found(node) {
 429                         return Ok(parent_node);
 430                     }
 431                 }
 432                 None => {
 433                     return Err(parent_node);
 434                 }
 435             }
 436             id = parent_node;
 437         }
 438     }
 439
 440     /// Retrieve the NodeId for `id`'s parent item, or `id` itself if no
 441     /// parent item is in this map. The "parent item" is the closest parent node
 442     /// in the AST which is recorded by the map and is an item, either an item
 443     /// in a module, trait, or impl.
 444     pub fn get_parent(&self, id: NodeId) -> NodeId {
 445         match self.walk_parent_nodes(id, |node| match *node {
 446             NodeItem(_) |
 447             NodeForeignItem(_) |
 448             NodeTraitItem(_) |
 449             NodeImplItem(_) => true,
 450             _ => false,
 451         }) {
 452             Ok(id) => id,
 453             Err(id) => id,
 454         }
 455     }
 456
 457     /// Returns the NodeId of `id`'s nearest module parent, or `id` itself if no
 458     /// module parent is in this map.
 459     pub fn get_module_parent(&self, id: NodeId) -> NodeId {
 460         match self.walk_parent_nodes(id, |node| match *node {
 461             NodeItem(&Item { node: Item_::ItemMod(_), .. }) => true,
 462             _ => false,
 463         }) {
 464             Ok(id) => id,
 465             Err(id) => id,
 466         }
 467     }
 468
 469     /// Returns the nearest enclosing scope. A scope is an item or block.
 470     /// FIXME it is not clear to me that all items qualify as scopes - statics
 471     /// and associated types probably shouldn't, for example. Behaviour in this
 472     /// regard should be expected to be highly unstable.
 473     pub fn get_enclosing_scope(&self, id: NodeId) -> Option<NodeId> {
 474         match self.walk_parent_nodes(id, |node| match *node {
 475             NodeItem(_) |
 476             NodeForeignItem(_) |
 477             NodeTraitItem(_) |
 478             NodeImplItem(_) |
 479             NodeBlock(_) => true,
 480             _ => false,
 481         }) {
 482             Ok(id) => Some(id),
 483             Err(_) => None,
 484         }
 485     }
 486
 487     pub fn get_parent_did(&self, id: NodeId) -> DefId {
 488         let parent = self.get_parent(id);
 489         match self.find_entry(parent) {
 490             Some(RootInlinedParent(&II::TraitItem(did, _))) |
 491             Some(RootInlinedParent(&II::ImplItem(did, _))) => did,
 492             _ => self.local_def_id(parent)
 493         }
 494     }
 495
 496     pub fn get_foreign_abi(&self, id: NodeId) -> Abi {
 497         let parent = self.get_parent(id);
 498         let abi = match self.find_entry(parent) {
 499             Some(EntryItem(_, i)) => {
 500                 match i.node {
 501                     ItemForeignMod(ref nm) => Some(nm.abi),
 502                     _ => None
 503                 }
 504             }
 505             /// Wrong but OK, because the only inlined foreign items are intrinsics.
 506             Some(RootInlinedParent(_)) => Some(Abi::RustIntrinsic),
 507             _ => None
 508         };
 509         match abi {
 510             Some(abi) => {
 511                 self.read(id); // reveals some of the content of a node
 512                 abi
 513             }
 514             None => bug!("expected foreign mod or inlined parent, found {}",
 515                           self.node_to_string(parent))
 516         }
 517     }
 518
 519     pub fn expect_item(&self, id: NodeId) -> &'ast Item {
 520         match self.find(id) { // read recorded by `find`
 521             Some(NodeItem(item)) => item,
 522             _ => bug!("expected item, found {}", self.node_to_string(id))
 523         }
 524     }
 525
 526     pub fn expect_trait_item(&self, id: NodeId) -> &'ast TraitItem {
 527         match self.find(id) {
 528             Some(NodeTraitItem(item)) => item,
 529             _ => bug!("expected trait item, found {}", self.node_to_string(id))
 530         }
 531     }
 532
 533     pub fn expect_struct(&self, id: NodeId) -> &'ast VariantData {
 534         match self.find(id) {
 535             Some(NodeItem(i)) => {
 536                 match i.node {
 537                     ItemStruct(ref struct_def, _) => struct_def,
 538                     _ => bug!("struct ID bound to non-struct")
 539                 }
 540             }
 541             Some(NodeVariant(variant)) => {
 542                 if variant.node.data.is_struct() {
 543                     &variant.node.data
 544                 } else {
 545                     bug!("struct ID bound to enum variant that isn't struct-like")
 546                 }
 547             }
 548             _ => bug!("expected struct, found {}", self.node_to_string(id)),
 549         }
 550     }
 551
 552     pub fn expect_variant(&self, id: NodeId) -> &'ast Variant {
 553         match self.find(id) {
 554             Some(NodeVariant(variant)) => variant,
 555             _ => bug!("expected variant, found {}", self.node_to_string(id)),
 556         }
 557     }
 558
 559     pub fn expect_foreign_item(&self, id: NodeId) -> &'ast ForeignItem {
 560         match self.find(id) {
 561             Some(NodeForeignItem(item)) => item,
 562             _ => bug!("expected foreign item, found {}", self.node_to_string(id))
 563         }
 564     }
 565
 566     pub fn expect_expr(&self, id: NodeId) -> &'ast Expr {
 567         match self.find(id) { // read recorded by find
 568             Some(NodeExpr(expr)) => expr,
 569             _ => bug!("expected expr, found {}", self.node_to_string(id))
 570         }
 571     }
 572
 573     pub fn expect_inlined_item(&self, id: NodeId) -> &'ast InlinedItem {
 574         match self.find_entry(id) {
 575             Some(RootInlinedParent(inlined_item)) => inlined_item,
 576             _ => bug!("expected inlined item, found {}", self.node_to_string(id)),
 577         }
 578     }
 579
 580     /// Returns the name associated with the given NodeId's AST.
 581     pub fn name(&self, id: NodeId) -> Name {
 582         match self.get(id) {
 583             NodeItem(i) => i.name,
 584             NodeForeignItem(i) => i.name,
 585             NodeImplItem(ii) => ii.name,
 586             NodeTraitItem(ti) => ti.name,
 587             NodeVariant(v) => v.node.name,
 588             NodeLifetime(lt) => lt.name,
 589             NodeTyParam(tp) => tp.name,
 590             NodeLocal(&Pat { node: PatKind::Binding(_,l,_), .. }) => l.node,
 591             NodeStructCtor(_) => self.name(self.get_parent(id)),
 592             _ => bug!("no name for {}", self.node_to_string(id))
 593         }
 594     }
 595
 596     /// Given a node ID, get a list of attributes associated with the AST
 597     /// corresponding to the Node ID
 598     pub fn attrs(&self, id: NodeId) -> &'ast [ast::Attribute] {
 599         self.read(id); // reveals attributes on the node
 600         let attrs = match self.find(id) {
 601             Some(NodeItem(i)) => Some(&i.attrs[..]),
 602             Some(NodeForeignItem(fi)) => Some(&fi.attrs[..]),
 603             Some(NodeTraitItem(ref ti)) => Some(&ti.attrs[..]),
 604             Some(NodeImplItem(ref ii)) => Some(&ii.attrs[..]),
 605             Some(NodeVariant(ref v)) => Some(&v.node.attrs[..]),
 606             Some(NodeExpr(ref e)) => Some(&*e.attrs),
 607             Some(NodeStmt(ref s)) => Some(s.node.attrs()),
 608             // unit/tuple structs take the attributes straight from
 609             // the struct definition.
 610             Some(NodeStructCtor(_)) => {
 611                 return self.attrs(self.get_parent(id));
 612             }
 613             _ => None
 614         };
 615         attrs.unwrap_or(&[])
 616     }
 617
 618     /// Returns an iterator that yields the node id's with paths that
 619     /// match `parts`.  (Requires `parts` is non-empty.)
 620     ///
 621     /// For example, if given `parts` equal to `["bar", "quux"]`, then
 622     /// the iterator will produce node id's for items with paths
 623     /// such as `foo::bar::quux`, `bar::quux`, `other::bar::quux`, and
 624     /// any other such items it can find in the map.
 625     pub fn nodes_matching_suffix<'a>(&'a self, parts: &'a [String])
 626                                  -> NodesMatchingSuffix<'a, 'ast> {
 627         NodesMatchingSuffix {
 628             map: self,
 629             item_name: parts.last().unwrap(),
 630             in_which: &parts[..parts.len() - 1],
 631             idx: 0,
 632         }
 633     }
 634
 635     pub fn opt_span(&self, id: NodeId) -> Option<Span> {
 636         let sp = match self.find(id) {
 637             Some(NodeItem(item)) => item.span,
 638             Some(NodeForeignItem(foreign_item)) => foreign_item.span,
 639             Some(NodeTraitItem(trait_method)) => trait_method.span,
 640             Some(NodeImplItem(ref impl_item)) => impl_item.span,
 641             Some(NodeVariant(variant)) => variant.span,
 642             Some(NodeExpr(expr)) => expr.span,
 643             Some(NodeStmt(stmt)) => stmt.span,
 644             Some(NodeLocal(pat)) => pat.span,
 645             Some(NodePat(pat)) => pat.span,
 646             Some(NodeBlock(block)) => block.span,
 647             Some(NodeStructCtor(_)) => self.expect_item(self.get_parent(id)).span,
 648             Some(NodeTyParam(ty_param)) => ty_param.span,
 649             _ => return None,
 650         };
 651         Some(sp)
 652     }
 653
 654     pub fn span(&self, id: NodeId) -> Span {
 655         self.read(id); // reveals span from node
 656         self.opt_span(id)
 657             .unwrap_or_else(|| bug!("AstMap.span: could not find span for id {:?}", id))
 658     }
 659
 660     pub fn span_if_local(&self, id: DefId) -> Option<Span> {
 661         self.as_local_node_id(id).map(|id| self.span(id))
 662     }
 663
 664     pub fn def_id_span(&self, def_id: DefId, fallback: Span) -> Span {
 665         if let Some(node_id) = self.as_local_node_id(def_id) {
 666             self.opt_span(node_id).unwrap_or(fallback)
 667         } else {
 668             fallback
 669         }
 670     }
 671
 672     pub fn node_to_string(&self, id: NodeId) -> String {
 673         node_id_to_string(self, id, true)
 674     }
 675
 676     pub fn node_to_user_string(&self, id: NodeId) -> String {
 677         node_id_to_string(self, id, false)
 678     }
 679 }
 680
 681 pub struct NodesMatchingSuffix<'a, 'ast:'a> {
 682     map: &'a Map<'ast>,
 683     item_name: &'a String,
 684     in_which: &'a [String],
 685     idx: NodeId,
 686 }
 687
 688 impl<'a, 'ast> NodesMatchingSuffix<'a, 'ast> {
 689     /// Returns true only if some suffix of the module path for parent
 690     /// matches `self.in_which`.
 691     ///
 692     /// In other words: let `[x_0,x_1,...,x_k]` be `self.in_which`;
 693     /// returns true if parent's path ends with the suffix
 694     /// `x_0::x_1::...::x_k`.
 695     fn suffix_matches(&self, parent: NodeId) -> bool {
 696         let mut cursor = parent;
 697         for part in self.in_which.iter().rev() {
 698             let (mod_id, mod_name) = match find_first_mod_parent(self.map, cursor) {
 699                 None => return false,
 700                 Some((node_id, name)) => (node_id, name),
 701             };
 702             if &part[..] != mod_name.as_str() {
 703                 return false;
 704             }
 705             cursor = self.map.get_parent(mod_id);
 706         }
 707         return true;
 708
 709         // Finds the first mod in parent chain for `id`, along with
 710         // that mod's name.
 711         //
 712         // If `id` itself is a mod named `m` with parent `p`, then
 713         // returns `Some(id, m, p)`.  If `id` has no mod in its parent
 714         // chain, then returns `None`.
 715         fn find_first_mod_parent<'a>(map: &'a Map, mut id: NodeId) -> Option<(NodeId, Name)> {
 716             loop {
 717                 match map.find(id) {
 718                     None => return None,
 719                     Some(NodeItem(item)) if item_is_mod(&item) =>
 720                         return Some((id, item.name)),
 721                     _ => {}
 722                 }
 723                 let parent = map.get_parent(id);
 724                 if parent == id { return None }
 725                 id = parent;
 726             }
 727
 728             fn item_is_mod(item: &Item) -> bool {
 729                 match item.node {
 730                     ItemMod(_) => true,
 731                     _ => false,
 732                 }
 733             }
 734         }
 735     }
 736
 737     // We are looking at some node `n` with a given name and parent
 738     // id; do their names match what I am seeking?
 739     fn matches_names(&self, parent_of_n: NodeId, name: Name) -> bool {
 740         name.as_str() == &self.item_name[..] &&
 741             self.suffix_matches(parent_of_n)
 742     }
 743 }
 744
 745 impl<'a, 'ast> Iterator for NodesMatchingSuffix<'a, 'ast> {
 746     type Item = NodeId;
 747
 748     fn next(&mut self) -> Option<NodeId> {
 749         loop {
 750             let idx = self.idx;
 751             if idx as usize >= self.map.entry_count() {
 752                 return None;
 753             }
 754             self.idx += 1;
 755             let name = match self.map.find_entry(idx) {
 756                 Some(EntryItem(_, n))       => n.name(),
 757                 Some(EntryForeignItem(_, n))=> n.name(),
 758                 Some(EntryTraitItem(_, n))  => n.name(),
 759                 Some(EntryImplItem(_, n))   => n.name(),
 760                 Some(EntryVariant(_, n))    => n.name(),
 761                 _ => continue,
 762             };
 763             if self.matches_names(self.map.get_parent(idx), name) {
 764                 return Some(idx)
 765             }
 766         }
 767     }
 768 }
 769
 770 trait Named {
 771     fn name(&self) -> Name;
 772 }
 773
 774 impl<T:Named> Named for Spanned<T> { fn name(&self) -> Name { self.node.name() } }
 775
 776 impl Named for Item { fn name(&self) -> Name { self.name } }
 777 impl Named for ForeignItem { fn name(&self) -> Name { self.name } }
 778 impl Named for Variant_ { fn name(&self) -> Name { self.name } }
 779 impl Named for TraitItem { fn name(&self) -> Name { self.name } }
 780 impl Named for ImplItem { fn name(&self) -> Name { self.name } }
 781
 782 pub trait FoldOps {
 783     fn new_id(&self, id: NodeId) -> NodeId {
 784         id
 785     }
 786     fn new_def_id(&self, def_id: DefId) -> DefId {
 787         def_id
 788     }
 789     fn new_span(&self, span: Span) -> Span {
 790         span
 791     }
 792 }
 793
 794 /// A Folder that updates IDs and Span's according to fold_ops.
 795 pub struct IdAndSpanUpdater<F> {
 796     fold_ops: F,
 797     min_id_assigned: NodeId,
 798     max_id_assigned: NodeId,
 799 }
 800
 801 impl<F: FoldOps> IdAndSpanUpdater<F> {
 802     pub fn new(fold_ops: F) -> IdAndSpanUpdater<F> {
 803         IdAndSpanUpdater {
 804             fold_ops: fold_ops,
 805             min_id_assigned: ::std::u32::MAX,
 806             max_id_assigned: ::std::u32::MIN,
 807         }
 808     }
 809
 810     pub fn id_range(&self) -> intravisit::IdRange {
 811         intravisit::IdRange {
 812             min: self.min_id_assigned,
 813             max: self.max_id_assigned + 1,
 814         }
 815     }
 816 }
 817
 818 impl<F: FoldOps> Folder for IdAndSpanUpdater<F> {
 819     fn new_id(&mut self, id: NodeId) -> NodeId {
 820         let id = self.fold_ops.new_id(id);
 821
 822         self.min_id_assigned = cmp::min(self.min_id_assigned, id);
 823         self.max_id_assigned = cmp::max(self.max_id_assigned, id);
 824
 825         id
 826     }
 827
 828     fn new_span(&mut self, span: Span) -> Span {
 829         self.fold_ops.new_span(span)
 830     }
 831 }
 832
 833 pub fn map_crate<'ast>(forest: &'ast mut Forest,
 834                        definitions: Definitions)
 835                        -> Map<'ast> {
 836     let mut collector = NodeCollector::root(&forest.krate);
 837     intravisit::walk_crate(&mut collector, &forest.krate);
 838     let map = collector.map;
 839
 840     if log_enabled!(::log::DEBUG) {
 841         // This only makes sense for ordered stores; note the
 842         // enumerate to count the number of entries.
 843         let (entries_less_1, _) = map.iter().filter(|&x| {
 844             match *x {
 845                 NotPresent => false,
 846                 _ => true
 847             }
 848         }).enumerate().last().expect("AST map was empty after folding?");
 849
 850         let entries = entries_less_1 + 1;
 851         let vector_length = map.len();
 852         debug!("The AST map has {} entries with a maximum of {}: occupancy {:.1}%",
 853               entries, vector_length, (entries as f64 / vector_length as f64) * 100.);
 854     }
 855
 856     let local_node_id_watermark = map.len() as NodeId;
 857     let local_def_id_watermark = definitions.len();
 858
 859     Map {
 860         forest: forest,
 861         dep_graph: forest.dep_graph.clone(),
 862         map: RefCell::new(map),
 863         definitions: RefCell::new(definitions),
 864         local_node_id_watermark: local_node_id_watermark,
 865         local_def_id_watermark: local_def_id_watermark,
 866     }
 867 }
 868
 869 /// Used for items loaded from external crate that are being inlined into this
 870 /// crate.
 871 pub fn map_decoded_item<'ast, F: FoldOps>(map: &Map<'ast>,
 872                                           parent_def_path: DefPath,
 873                                           parent_def_id: DefId,
 874                                           ii: InlinedItem,
 875                                           fold_ops: F)
 876                                           -> &'ast InlinedItem {
 877     let mut fld = IdAndSpanUpdater::new(fold_ops);
 878     let ii = match ii {
 879         II::Item(i) => II::Item(i.map(|i| fld.fold_item(i))),
 880         II::TraitItem(d, ti) => {
 881             II::TraitItem(fld.fold_ops.new_def_id(d),
 882                           ti.map(|ti| fld.fold_trait_item(ti)))
 883         }
 884         II::ImplItem(d, ii) => {
 885             II::ImplItem(fld.fold_ops.new_def_id(d),
 886                          ii.map(|ii| fld.fold_impl_item(ii)))
 887         }
 888         II::Foreign(i) => II::Foreign(i.map(|i| fld.fold_foreign_item(i)))
 889     };
 890
 891     let ii = map.forest.inlined_items.alloc(ii);
 892     let ii_parent_id = fld.new_id(DUMMY_NODE_ID);
 893
 894     // Assert that the ii_parent_id is the last NodeId in our reserved range
 895     assert!(ii_parent_id == fld.max_id_assigned);
 896     // Assert that we did not violate the invariant that all inlined HIR items
 897     // have NodeIds greater than or equal to `local_node_id_watermark`
 898     assert!(fld.min_id_assigned >= map.local_node_id_watermark);
 899
 900     let defs = &mut *map.definitions.borrow_mut();
 901     let mut def_collector = DefCollector::extend(ii_parent_id,
 902                                                  parent_def_path.clone(),
 903                                                  parent_def_id,
 904                                                  defs);
 905     def_collector.walk_item(ii, map.krate());
 906
 907     let mut collector = NodeCollector::extend(map.krate(),
 908                                               ii,
 909                                               ii_parent_id,
 910                                               parent_def_path,
 911                                               parent_def_id,
 912                                               mem::replace(&mut *map.map.borrow_mut(), vec![]));
 913     ii.visit(&mut collector);
 914     *map.map.borrow_mut() = collector.map;
 915
 916     ii
 917 }
 918
 919 pub trait NodePrinter {
 920     fn print_node(&mut self, node: &Node) -> io::Result<()>;
 921 }
 922
 923 impl<'a> NodePrinter for pprust::State<'a> {
 924     fn print_node(&mut self, node: &Node) -> io::Result<()> {
 925         match *node {
 926             NodeItem(a)        => self.print_item(&a),
 927             NodeForeignItem(a) => self.print_foreign_item(&a),
 928             NodeTraitItem(a)   => self.print_trait_item(a),
 929             NodeImplItem(a)    => self.print_impl_item(a),
 930             NodeVariant(a)     => self.print_variant(&a),
 931             NodeExpr(a)        => self.print_expr(&a),
 932             NodeStmt(a)        => self.print_stmt(&a),
 933             NodePat(a)         => self.print_pat(&a),
 934             NodeBlock(a)       => self.print_block(&a),
 935             NodeLifetime(a)    => self.print_lifetime(&a),
 936             NodeTyParam(_)     => bug!("cannot print TyParam"),
 937             // these cases do not carry enough information in the
 938             // ast_map to reconstruct their full structure for pretty
 939             // printing.
 940             NodeLocal(_)       => bug!("cannot print isolated Local"),
 941             NodeStructCtor(_)  => bug!("cannot print isolated StructCtor"),
 942         }
 943     }
 944 }
 945
 946 fn node_id_to_string(map: &Map, id: NodeId, include_id: bool) -> String {
 947     let id_str = format!(" (id={})", id);
 948     let id_str = if include_id { &id_str[..] } else { "" };
 949
 950     let path_str = || {
 951         // This functionality is used for debugging, try to use TyCtxt to get
 952         // the user-friendly path, otherwise fall back to stringifying DefPath.
 953         ::ty::tls::with_opt(|tcx| {
 954             if let Some(tcx) = tcx {
 955                 tcx.node_path_str(id)
 956             } else if let Some(path) = map.def_path_from_id(id) {
 957                 path.data.into_iter().map(|elem| {
 958                     elem.data.to_string()
 959                 }).collect::<Vec<_>>().join("::")
 960             } else {
 961                 String::from("<missing path>")
 962             }
 963         })
 964     };
 965
 966     match map.find(id) {
 967         Some(NodeItem(item)) => {
 968             let item_str = match item.node {
 969                 ItemExternCrate(..) => "extern crate",
 970                 ItemUse(..) => "use",
 971                 ItemStatic(..) => "static",
 972                 ItemConst(..) => "const",
 973                 ItemFn(..) => "fn",
 974                 ItemMod(..) => "mod",
 975                 ItemForeignMod(..) => "foreign mod",
 976                 ItemTy(..) => "ty",
 977                 ItemEnum(..) => "enum",
 978                 ItemStruct(..) => "struct",
 979                 ItemTrait(..) => "trait",
 980                 ItemImpl(..) => "impl",
 981                 ItemDefaultImpl(..) => "default impl",
 982             };
 983             format!("{} {}{}", item_str, path_str(), id_str)
 984         }
 985         Some(NodeForeignItem(_)) => {
 986             format!("foreign item {}{}", path_str(), id_str)
 987         }
 988         Some(NodeImplItem(ii)) => {
 989             match ii.node {
 990                 ImplItemKind::Const(..) => {
 991                     format!("assoc const {} in {}{}", ii.name, path_str(), id_str)
 992                 }
 993                 ImplItemKind::Method(..) => {
 994                     format!("method {} in {}{}", ii.name, path_str(), id_str)
 995                 }
 996                 ImplItemKind::Type(_) => {
 997                     format!("assoc type {} in {}{}", ii.name, path_str(), id_str)
 998                 }
 999             }
1000         }
1001         Some(NodeTraitItem(ti)) => {
1002             let kind = match ti.node {
1003                 ConstTraitItem(..) => "assoc constant",
1004                 MethodTraitItem(..) => "trait method",
1005                 TypeTraitItem(..) => "assoc type",
1006             };
1007
1008             format!("{} {} in {}{}", kind, ti.name, path_str(), id_str)
1009         }
1010         Some(NodeVariant(ref variant)) => {
1011             format!("variant {} in {}{}",
1012                     variant.node.name,
1013                     path_str(), id_str)
1014         }
1015         Some(NodeExpr(ref expr)) => {
1016             format!("expr {}{}", pprust::expr_to_string(&expr), id_str)
1017         }
1018         Some(NodeStmt(ref stmt)) => {
1019             format!("stmt {}{}", pprust::stmt_to_string(&stmt), id_str)
1020         }
1021         Some(NodeLocal(ref pat)) => {
1022             format!("local {}{}", pprust::pat_to_string(&pat), id_str)
1023         }
1024         Some(NodePat(ref pat)) => {
1025             format!("pat {}{}", pprust::pat_to_string(&pat), id_str)
1026         }
1027         Some(NodeBlock(ref block)) => {
1028             format!("block {}{}", pprust::block_to_string(&block), id_str)
1029         }
1030         Some(NodeStructCtor(_)) => {
1031             format!("struct_ctor {}{}", path_str(), id_str)
1032         }
1033         Some(NodeLifetime(ref l)) => {
1034             format!("lifetime {}{}",
1035                     pprust::lifetime_to_string(&l), id_str)
1036         }
1037         Some(NodeTyParam(ref ty_param)) => {
1038             format!("typaram {:?}{}", ty_param, id_str)
1039         }
1040         None => {
1041             format!("unknown node{}", id_str)
1042         }
1043     }
1044 }