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