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