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