src/libsyntax/ast_map/mod.rs

   1 // Copyright 2012-2013 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
  15 use abi;
  16 use ast::*;
  17 use ast_util;
  18 use codemap::{DUMMY_SP, Span, Spanned};
  19 use fold::Folder;
  20 use parse::token;
  21 use print::pprust;
  22 use ptr::P;
  23 use visit::{self, Visitor};
  24
  25 use arena::TypedArena;
  26 use std::cell::RefCell;
  27 use std::fmt;
  28 use std::io::IoResult;
  29 use std::iter::{self, repeat};
  30 use std::mem;
  31 use std::slice;
  32
  33 pub mod blocks;
  34
  35 #[derive(Clone, Copy, PartialEq, Show)]
  36 pub enum PathElem {
  37     PathMod(Name),
  38     PathName(Name)
  39 }
  40
  41 impl PathElem {
  42     pub fn name(&self) -> Name {
  43         match *self {
  44             PathMod(name) | PathName(name) => name
  45         }
  46     }
  47 }
  48
  49 impl fmt::String for PathElem {
  50     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  51         let slot = token::get_name(self.name());
  52         write!(f, "{}", slot)
  53     }
  54 }
  55
  56 #[derive(Clone)]
  57 struct LinkedPathNode<'a> {
  58     node: PathElem,
  59     next: LinkedPath<'a>,
  60 }
  61
  62 type LinkedPath<'a> = Option<&'a LinkedPathNode<'a>>;
  63
  64 impl<'a> Iterator for LinkedPath<'a> {
  65     type Item = PathElem;
  66
  67     fn next(&mut self) -> Option<PathElem> {
  68         match *self {
  69             Some(node) => {
  70                 *self = node.next;
  71                 Some(node.node)
  72             }
  73             None => None
  74         }
  75     }
  76 }
  77
  78 // HACK(eddyb) move this into libstd (value wrapper for slice::Iter).
  79 #[derive(Clone)]
  80 pub struct Values<'a, T:'a>(pub slice::Iter<'a, T>);
  81
  82 impl<'a, T: Copy> Iterator for Values<'a, T> {
  83     type Item = T;
  84
  85     fn next(&mut self) -> Option<T> {
  86         let &mut Values(ref mut items) = self;
  87         items.next().map(|&x| x)
  88     }
  89 }
  90
  91 /// The type of the iterator used by with_path.
  92 pub type PathElems<'a, 'b> = iter::Chain<Values<'a, PathElem>, LinkedPath<'b>>;
  93
  94 pub fn path_to_string<PI: Iterator<Item=PathElem>>(path: PI) -> String {
  95     let itr = token::get_ident_interner();
  96
  97     path.fold(String::new(), |mut s, e| {
  98         let e = itr.get(e.name());
  99         if !s.is_empty() {
 100             s.push_str("::");
 101         }
 102         s.push_str(&e[]);
 103         s
 104     }).to_string()
 105 }
 106
 107 #[derive(Copy, Show)]
 108 pub enum Node<'ast> {
 109     NodeItem(&'ast Item),
 110     NodeViewItem(&'ast ViewItem),
 111     NodeForeignItem(&'ast ForeignItem),
 112     NodeTraitItem(&'ast TraitItem),
 113     NodeImplItem(&'ast ImplItem),
 114     NodeVariant(&'ast Variant),
 115     NodeExpr(&'ast Expr),
 116     NodeStmt(&'ast Stmt),
 117     NodeArg(&'ast Pat),
 118     NodeLocal(&'ast Pat),
 119     NodePat(&'ast Pat),
 120     NodeBlock(&'ast Block),
 121
 122     /// NodeStructCtor represents a tuple struct.
 123     NodeStructCtor(&'ast StructDef),
 124
 125     NodeLifetime(&'ast Lifetime),
 126 }
 127
 128 /// Represents an entry and its parent Node ID
 129 /// The odd layout is to bring down the total size.
 130 #[derive(Copy, Show)]
 131 enum MapEntry<'ast> {
 132     /// Placeholder for holes in the map.
 133     NotPresent,
 134
 135     /// All the node types, with a parent ID.
 136     EntryItem(NodeId, &'ast Item),
 137     EntryViewItem(NodeId, &'ast ViewItem),
 138     EntryForeignItem(NodeId, &'ast ForeignItem),
 139     EntryTraitItem(NodeId, &'ast TraitItem),
 140     EntryImplItem(NodeId, &'ast ImplItem),
 141     EntryVariant(NodeId, &'ast Variant),
 142     EntryExpr(NodeId, &'ast Expr),
 143     EntryStmt(NodeId, &'ast Stmt),
 144     EntryArg(NodeId, &'ast Pat),
 145     EntryLocal(NodeId, &'ast Pat),
 146     EntryPat(NodeId, &'ast Pat),
 147     EntryBlock(NodeId, &'ast Block),
 148     EntryStructCtor(NodeId, &'ast StructDef),
 149     EntryLifetime(NodeId, &'ast Lifetime),
 150
 151     /// Roots for node trees.
 152     RootCrate,
 153     RootInlinedParent(&'ast InlinedParent)
 154 }
 155
 156 impl<'ast> Clone for MapEntry<'ast> {
 157     fn clone(&self) -> MapEntry<'ast> {
 158         *self
 159     }
 160 }
 161
 162 #[derive(Show)]
 163 struct InlinedParent {
 164     path: Vec<PathElem>,
 165     ii: InlinedItem
 166 }
 167
 168 impl<'ast> MapEntry<'ast> {
 169     fn from_node(p: NodeId, node: Node<'ast>) -> MapEntry<'ast> {
 170         match node {
 171             NodeItem(n) => EntryItem(p, n),
 172             NodeViewItem(n) => EntryViewItem(p, n),
 173             NodeForeignItem(n) => EntryForeignItem(p, n),
 174             NodeTraitItem(n) => EntryTraitItem(p, n),
 175             NodeImplItem(n) => EntryImplItem(p, n),
 176             NodeVariant(n) => EntryVariant(p, n),
 177             NodeExpr(n) => EntryExpr(p, n),
 178             NodeStmt(n) => EntryStmt(p, n),
 179             NodeArg(n) => EntryArg(p, n),
 180             NodeLocal(n) => EntryLocal(p, n),
 181             NodePat(n) => EntryPat(p, n),
 182             NodeBlock(n) => EntryBlock(p, n),
 183             NodeStructCtor(n) => EntryStructCtor(p, n),
 184             NodeLifetime(n) => EntryLifetime(p, n)
 185         }
 186     }
 187
 188     fn parent(self) -> Option<NodeId> {
 189         Some(match self {
 190             EntryItem(id, _) => id,
 191             EntryViewItem(id, _) => id,
 192             EntryForeignItem(id, _) => id,
 193             EntryTraitItem(id, _) => id,
 194             EntryImplItem(id, _) => id,
 195             EntryVariant(id, _) => id,
 196             EntryExpr(id, _) => id,
 197             EntryStmt(id, _) => id,
 198             EntryArg(id, _) => id,
 199             EntryLocal(id, _) => id,
 200             EntryPat(id, _) => id,
 201             EntryBlock(id, _) => id,
 202             EntryStructCtor(id, _) => id,
 203             EntryLifetime(id, _) => id,
 204             _ => return None
 205         })
 206     }
 207
 208     fn to_node(self) -> Option<Node<'ast>> {
 209         Some(match self {
 210             EntryItem(_, n) => NodeItem(n),
 211             EntryViewItem(_, n) => NodeViewItem(n),
 212             EntryForeignItem(_, n) => NodeForeignItem(n),
 213             EntryTraitItem(_, n) => NodeTraitItem(n),
 214             EntryImplItem(_, n) => NodeImplItem(n),
 215             EntryVariant(_, n) => NodeVariant(n),
 216             EntryExpr(_, n) => NodeExpr(n),
 217             EntryStmt(_, n) => NodeStmt(n),
 218             EntryArg(_, n) => NodeArg(n),
 219             EntryLocal(_, n) => NodeLocal(n),
 220             EntryPat(_, n) => NodePat(n),
 221             EntryBlock(_, n) => NodeBlock(n),
 222             EntryStructCtor(_, n) => NodeStructCtor(n),
 223             EntryLifetime(_, n) => NodeLifetime(n),
 224             _ => return None
 225         })
 226     }
 227 }
 228
 229 /// Stores a crate and any number of inlined items from other crates.
 230 pub struct Forest {
 231     krate: Crate,
 232     inlined_items: TypedArena<InlinedParent>
 233 }
 234
 235 impl Forest {
 236     pub fn new(krate: Crate) -> Forest {
 237         Forest {
 238             krate: krate,
 239             inlined_items: TypedArena::new()
 240         }
 241     }
 242
 243     pub fn krate<'ast>(&'ast self) -> &'ast Crate {
 244         &self.krate
 245     }
 246 }
 247
 248 /// Represents a mapping from Node IDs to AST elements and their parent
 249 /// Node IDs
 250 pub struct Map<'ast> {
 251     /// The backing storage for all the AST nodes.
 252     forest: &'ast Forest,
 253
 254     /// NodeIds are sequential integers from 0, so we can be
 255     /// super-compact by storing them in a vector. Not everything with
 256     /// a NodeId is in the map, but empirically the occupancy is about
 257     /// 75-80%, so there's not too much overhead (certainly less than
 258     /// a hashmap, since they (at the time of writing) have a maximum
 259     /// of 75% occupancy).
 260     ///
 261     /// Also, indexing is pretty quick when you've got a vector and
 262     /// plain old integers.
 263     map: RefCell<Vec<MapEntry<'ast>>>
 264 }
 265
 266 impl<'ast> Map<'ast> {
 267     fn entry_count(&self) -> uint {
 268         self.map.borrow().len()
 269     }
 270
 271     fn find_entry(&self, id: NodeId) -> Option<MapEntry<'ast>> {
 272         self.map.borrow().get(id as uint).map(|e| *e)
 273     }
 274
 275     pub fn krate(&self) -> &'ast Crate {
 276         &self.forest.krate
 277     }
 278
 279     /// Retrieve the Node corresponding to `id`, panicking if it cannot
 280     /// be found.
 281     pub fn get(&self, id: NodeId) -> Node<'ast> {
 282         match self.find(id) {
 283             Some(node) => node,
 284             None => panic!("couldn't find node id {} in the AST map", id)
 285         }
 286     }
 287
 288     /// Retrieve the Node corresponding to `id`, returning None if
 289     /// cannot be found.
 290     pub fn find(&self, id: NodeId) -> Option<Node<'ast>> {
 291         self.find_entry(id).and_then(|x| x.to_node())
 292     }
 293
 294     /// Retrieve the parent NodeId for `id`, or `id` itself if no
 295     /// parent is registered in this map.
 296     pub fn get_parent(&self, id: NodeId) -> NodeId {
 297         self.find_entry(id).and_then(|x| x.parent()).unwrap_or(id)
 298     }
 299
 300     pub fn get_parent_did(&self, id: NodeId) -> DefId {
 301         let parent = self.get_parent(id);
 302         match self.find_entry(parent) {
 303             Some(RootInlinedParent(&InlinedParent {ii: IITraitItem(did, _), ..})) => did,
 304             Some(RootInlinedParent(&InlinedParent {ii: IIImplItem(did, _), ..})) => did,
 305             _ => ast_util::local_def(parent)
 306         }
 307     }
 308
 309     pub fn get_foreign_abi(&self, id: NodeId) -> abi::Abi {
 310         let parent = self.get_parent(id);
 311         let abi = match self.find_entry(parent) {
 312             Some(EntryItem(_, i)) => {
 313                 match i.node {
 314                     ItemForeignMod(ref nm) => Some(nm.abi),
 315                     _ => None
 316                 }
 317             }
 318             /// Wrong but OK, because the only inlined foreign items are intrinsics.
 319             Some(RootInlinedParent(_)) => Some(abi::RustIntrinsic),
 320             _ => None
 321         };
 322         match abi {
 323             Some(abi) => abi,
 324             None => panic!("expected foreign mod or inlined parent, found {}",
 325                           self.node_to_string(parent))
 326         }
 327     }
 328
 329     pub fn get_foreign_vis(&self, id: NodeId) -> Visibility {
 330         let vis = self.expect_foreign_item(id).vis;
 331         match self.find(self.get_parent(id)) {
 332             Some(NodeItem(i)) => vis.inherit_from(i.vis),
 333             _ => vis
 334         }
 335     }
 336
 337     pub fn expect_item(&self, id: NodeId) -> &'ast Item {
 338         match self.find(id) {
 339             Some(NodeItem(item)) => item,
 340             _ => panic!("expected item, found {}", self.node_to_string(id))
 341         }
 342     }
 343
 344     pub fn expect_view_item(&self, id: NodeId) -> &'ast ViewItem {
 345         match self.find(id) {
 346             Some(NodeViewItem(view_item)) => view_item,
 347             _ => panic!("expected view item, found {}", self.node_to_string(id))
 348         }
 349     }
 350
 351     pub fn expect_struct(&self, id: NodeId) -> &'ast StructDef {
 352         match self.find(id) {
 353             Some(NodeItem(i)) => {
 354                 match i.node {
 355                     ItemStruct(ref struct_def, _) => &**struct_def,
 356                     _ => panic!("struct ID bound to non-struct")
 357                 }
 358             }
 359             Some(NodeVariant(variant)) => {
 360                 match variant.node.kind {
 361                     StructVariantKind(ref struct_def) => &**struct_def,
 362                     _ => panic!("struct ID bound to enum variant that isn't struct-like"),
 363                 }
 364             }
 365             _ => panic!(format!("expected struct, found {}", self.node_to_string(id))),
 366         }
 367     }
 368
 369     pub fn expect_variant(&self, id: NodeId) -> &'ast Variant {
 370         match self.find(id) {
 371             Some(NodeVariant(variant)) => variant,
 372             _ => panic!(format!("expected variant, found {}", self.node_to_string(id))),
 373         }
 374     }
 375
 376     pub fn expect_foreign_item(&self, id: NodeId) -> &'ast ForeignItem {
 377         match self.find(id) {
 378             Some(NodeForeignItem(item)) => item,
 379             _ => panic!("expected foreign item, found {}", self.node_to_string(id))
 380         }
 381     }
 382
 383     pub fn expect_expr(&self, id: NodeId) -> &'ast Expr {
 384         match self.find(id) {
 385             Some(NodeExpr(expr)) => expr,
 386             _ => panic!("expected expr, found {}", self.node_to_string(id))
 387         }
 388     }
 389
 390     /// returns the name associated with the given NodeId's AST
 391     pub fn get_path_elem(&self, id: NodeId) -> PathElem {
 392         let node = self.get(id);
 393         match node {
 394             NodeItem(item) => {
 395                 match item.node {
 396                     ItemMod(_) | ItemForeignMod(_) => {
 397                         PathMod(item.ident.name)
 398                     }
 399                     _ => PathName(item.ident.name)
 400                 }
 401             }
 402             NodeForeignItem(i) => PathName(i.ident.name),
 403             NodeImplItem(ii) => {
 404                 match *ii {
 405                     MethodImplItem(ref m) => {
 406                         match m.node {
 407                             MethDecl(ident, _, _, _, _, _, _, _) => {
 408                                 PathName(ident.name)
 409                             }
 410                             MethMac(_) => {
 411                                 panic!("no path elem for {:?}", node)
 412                             }
 413                         }
 414                     }
 415                     TypeImplItem(ref t) => PathName(t.ident.name),
 416                 }
 417             },
 418             NodeTraitItem(tm) => match *tm {
 419                 RequiredMethod(ref m) => PathName(m.ident.name),
 420                 ProvidedMethod(ref m) => {
 421                     match m.node {
 422                         MethDecl(ident, _, _, _, _, _, _, _) => {
 423                             PathName(ident.name)
 424                         }
 425                         MethMac(_) => panic!("no path elem for {:?}", node),
 426                     }
 427                 }
 428                 TypeTraitItem(ref m) => {
 429                     PathName(m.ty_param.ident.name)
 430                 }
 431             },
 432             NodeVariant(v) => PathName(v.node.name.name),
 433             _ => panic!("no path elem for {:?}", node)
 434         }
 435     }
 436
 437     pub fn with_path<T, F>(&self, id: NodeId, f: F) -> T where
 438         F: FnOnce(PathElems) -> T,
 439     {
 440         self.with_path_next(id, None, f)
 441     }
 442
 443     pub fn path_to_string(&self, id: NodeId) -> String {
 444         self.with_path(id, |path| path_to_string(path))
 445     }
 446
 447     fn path_to_str_with_ident(&self, id: NodeId, i: Ident) -> String {
 448         self.with_path(id, |path| {
 449             path_to_string(path.chain(Some(PathName(i.name)).into_iter()))
 450         })
 451     }
 452
 453     fn with_path_next<T, F>(&self, id: NodeId, next: LinkedPath, f: F) -> T where
 454         F: FnOnce(PathElems) -> T,
 455     {
 456         let parent = self.get_parent(id);
 457         let parent = match self.find_entry(id) {
 458             Some(EntryForeignItem(..)) | Some(EntryVariant(..)) => {
 459                 // Anonymous extern items, enum variants and struct ctors
 460                 // go in the parent scope.
 461                 self.get_parent(parent)
 462             }
 463             // But tuple struct ctors don't have names, so use the path of its
 464             // parent, the struct item. Similarly with closure expressions.
 465             Some(EntryStructCtor(..)) | Some(EntryExpr(..)) => {
 466                 return self.with_path_next(parent, next, f);
 467             }
 468             _ => parent
 469         };
 470         if parent == id {
 471             match self.find_entry(id) {
 472                 Some(RootInlinedParent(data)) => {
 473                     f(Values(data.path.iter()).chain(next))
 474                 }
 475                 _ => f(Values([].iter()).chain(next))
 476             }
 477         } else {
 478             self.with_path_next(parent, Some(&LinkedPathNode {
 479                 node: self.get_path_elem(id),
 480                 next: next
 481             }), f)
 482         }
 483     }
 484
 485     /// Given a node ID and a closure, apply the closure to the array
 486     /// of attributes associated with the AST corresponding to the Node ID
 487     pub fn with_attrs<T, F>(&self, id: NodeId, f: F) -> T where
 488         F: FnOnce(Option<&[Attribute]>) -> T,
 489     {
 490         let attrs = match self.get(id) {
 491             NodeItem(i) => Some(&i.attrs[]),
 492             NodeForeignItem(fi) => Some(&fi.attrs[]),
 493             NodeTraitItem(ref tm) => match **tm {
 494                 RequiredMethod(ref type_m) => Some(&type_m.attrs[]),
 495                 ProvidedMethod(ref m) => Some(&m.attrs[]),
 496                 TypeTraitItem(ref typ) => Some(&typ.attrs[]),
 497             },
 498             NodeImplItem(ref ii) => {
 499                 match **ii {
 500                     MethodImplItem(ref m) => Some(&m.attrs[]),
 501                     TypeImplItem(ref t) => Some(&t.attrs[]),
 502                 }
 503             }
 504             NodeVariant(ref v) => Some(&v.node.attrs[]),
 505             // unit/tuple structs take the attributes straight from
 506             // the struct definition.
 507             // FIXME(eddyb) make this work again (requires access to the map).
 508             NodeStructCtor(_) => {
 509                 return self.with_attrs(self.get_parent(id), f);
 510             }
 511             _ => None
 512         };
 513         f(attrs)
 514     }
 515
 516     /// Returns an iterator that yields the node id's with paths that
 517     /// match `parts`.  (Requires `parts` is non-empty.)
 518     ///
 519     /// For example, if given `parts` equal to `["bar", "quux"]`, then
 520     /// the iterator will produce node id's for items with paths
 521     /// such as `foo::bar::quux`, `bar::quux`, `other::bar::quux`, and
 522     /// any other such items it can find in the map.
 523     pub fn nodes_matching_suffix<'a>(&'a self, parts: &'a [String])
 524                                  -> NodesMatchingSuffix<'a, 'ast> {
 525         NodesMatchingSuffix {
 526             map: self,
 527             item_name: parts.last().unwrap(),
 528             in_which: &parts[..(parts.len() - 1)],
 529             idx: 0,
 530         }
 531     }
 532
 533     pub fn opt_span(&self, id: NodeId) -> Option<Span> {
 534         let sp = match self.find(id) {
 535             Some(NodeItem(item)) => item.span,
 536             Some(NodeViewItem(item)) => item.span,
 537             Some(NodeForeignItem(foreign_item)) => foreign_item.span,
 538             Some(NodeTraitItem(trait_method)) => {
 539                 match *trait_method {
 540                     RequiredMethod(ref type_method) => type_method.span,
 541                     ProvidedMethod(ref method) => method.span,
 542                     TypeTraitItem(ref typedef) => typedef.ty_param.span,
 543                 }
 544             }
 545             Some(NodeImplItem(ref impl_item)) => {
 546                 match **impl_item {
 547                     MethodImplItem(ref method) => method.span,
 548                     TypeImplItem(ref typedef) => typedef.span,
 549                 }
 550             }
 551             Some(NodeVariant(variant)) => variant.span,
 552             Some(NodeExpr(expr)) => expr.span,
 553             Some(NodeStmt(stmt)) => stmt.span,
 554             Some(NodeArg(pat)) | Some(NodeLocal(pat)) => pat.span,
 555             Some(NodePat(pat)) => pat.span,
 556             Some(NodeBlock(block)) => block.span,
 557             Some(NodeStructCtor(_)) => self.expect_item(self.get_parent(id)).span,
 558             _ => return None,
 559         };
 560         Some(sp)
 561     }
 562
 563     pub fn span(&self, id: NodeId) -> Span {
 564         self.opt_span(id)
 565             .unwrap_or_else(|| panic!("AstMap.span: could not find span for id {:?}", id))
 566     }
 567
 568     pub fn def_id_span(&self, def_id: DefId, fallback: Span) -> Span {
 569         if def_id.krate == LOCAL_CRATE {
 570             self.opt_span(def_id.node).unwrap_or(fallback)
 571         } else {
 572             fallback
 573         }
 574     }
 575
 576     pub fn node_to_string(&self, id: NodeId) -> String {
 577         node_id_to_string(self, id, true)
 578     }
 579
 580     pub fn node_to_user_string(&self, id: NodeId) -> String {
 581         node_id_to_string(self, id, false)
 582     }
 583 }
 584
 585 pub struct NodesMatchingSuffix<'a, 'ast:'a> {
 586     map: &'a Map<'ast>,
 587     item_name: &'a String,
 588     in_which: &'a [String],
 589     idx: NodeId,
 590 }
 591
 592 impl<'a, 'ast> NodesMatchingSuffix<'a, 'ast> {
 593     /// Returns true only if some suffix of the module path for parent
 594     /// matches `self.in_which`.
 595     ///
 596     /// In other words: let `[x_0,x_1,...,x_k]` be `self.in_which`;
 597     /// returns true if parent's path ends with the suffix
 598     /// `x_0::x_1::...::x_k`.
 599     fn suffix_matches(&self, parent: NodeId) -> bool {
 600         let mut cursor = parent;
 601         for part in self.in_which.iter().rev() {
 602             let (mod_id, mod_name) = match find_first_mod_parent(self.map, cursor) {
 603                 None => return false,
 604                 Some((node_id, name)) => (node_id, name),
 605             };
 606             if &part[] != mod_name.as_str() {
 607                 return false;
 608             }
 609             cursor = self.map.get_parent(mod_id);
 610         }
 611         return true;
 612
 613         // Finds the first mod in parent chain for `id`, along with
 614         // that mod's name.
 615         //
 616         // If `id` itself is a mod named `m` with parent `p`, then
 617         // returns `Some(id, m, p)`.  If `id` has no mod in its parent
 618         // chain, then returns `None`.
 619         fn find_first_mod_parent<'a>(map: &'a Map, mut id: NodeId) -> Option<(NodeId, Name)> {
 620             loop {
 621                 match map.find(id) {
 622                     None => return None,
 623                     Some(NodeItem(item)) if item_is_mod(&*item) =>
 624                         return Some((id, item.ident.name)),
 625                     _ => {}
 626                 }
 627                 let parent = map.get_parent(id);
 628                 if parent == id { return None }
 629                 id = parent;
 630             }
 631
 632             fn item_is_mod(item: &Item) -> bool {
 633                 match item.node {
 634                     ItemMod(_) => true,
 635                     _ => false,
 636                 }
 637             }
 638         }
 639     }
 640
 641     // We are looking at some node `n` with a given name and parent
 642     // id; do their names match what I am seeking?
 643     fn matches_names(&self, parent_of_n: NodeId, name: Name) -> bool {
 644         name.as_str() == &self.item_name[] &&
 645             self.suffix_matches(parent_of_n)
 646     }
 647 }
 648
 649 impl<'a, 'ast> Iterator for NodesMatchingSuffix<'a, 'ast> {
 650     type Item = NodeId;
 651
 652     fn next(&mut self) -> Option<NodeId> {
 653         loop {
 654             let idx = self.idx;
 655             if idx as uint >= self.map.entry_count() {
 656                 return None;
 657             }
 658             self.idx += 1;
 659             let (p, name) = match self.map.find_entry(idx) {
 660                 Some(EntryItem(p, n))       => (p, n.name()),
 661                 Some(EntryForeignItem(p, n))=> (p, n.name()),
 662                 Some(EntryTraitItem(p, n))  => (p, n.name()),
 663                 Some(EntryImplItem(p, n))   => (p, n.name()),
 664                 Some(EntryVariant(p, n))    => (p, n.name()),
 665                 _ => continue,
 666             };
 667             if self.matches_names(p, name) {
 668                 return Some(idx)
 669             }
 670         }
 671     }
 672 }
 673
 674 trait Named {
 675     fn name(&self) -> Name;
 676 }
 677
 678 impl<T:Named> Named for Spanned<T> { fn name(&self) -> Name { self.node.name() } }
 679
 680 impl Named for Item { fn name(&self) -> Name { self.ident.name } }
 681 impl Named for ForeignItem { fn name(&self) -> Name { self.ident.name } }
 682 impl Named for Variant_ { fn name(&self) -> Name { self.name.name } }
 683 impl Named for TraitItem {
 684     fn name(&self) -> Name {
 685         match *self {
 686             RequiredMethod(ref tm) => tm.ident.name,
 687             ProvidedMethod(ref m) => m.name(),
 688             TypeTraitItem(ref at) => at.ty_param.ident.name,
 689         }
 690     }
 691 }
 692 impl Named for ImplItem {
 693     fn name(&self) -> Name {
 694         match *self {
 695             MethodImplItem(ref m) => m.name(),
 696             TypeImplItem(ref td) => td.ident.name,
 697         }
 698     }
 699 }
 700 impl Named for Method {
 701     fn name(&self) -> Name {
 702         match self.node {
 703             MethDecl(i, _, _, _, _, _, _, _) => i.name,
 704             MethMac(_) => panic!("encountered unexpanded method macro."),
 705         }
 706     }
 707 }
 708
 709 pub trait FoldOps {
 710     fn new_id(&self, id: NodeId) -> NodeId {
 711         id
 712     }
 713     fn new_def_id(&self, def_id: DefId) -> DefId {
 714         def_id
 715     }
 716     fn new_span(&self, span: Span) -> Span {
 717         span
 718     }
 719 }
 720
 721 /// A Folder that updates IDs and Span's according to fold_ops.
 722 struct IdAndSpanUpdater<F> {
 723     fold_ops: F
 724 }
 725
 726 impl<F: FoldOps> Folder for IdAndSpanUpdater<F> {
 727     fn new_id(&mut self, id: NodeId) -> NodeId {
 728         self.fold_ops.new_id(id)
 729     }
 730
 731     fn new_span(&mut self, span: Span) -> Span {
 732         self.fold_ops.new_span(span)
 733     }
 734 }
 735
 736 /// A Visitor that walks over an AST and collects Node's into an AST Map.
 737 struct NodeCollector<'ast> {
 738     map: Vec<MapEntry<'ast>>,
 739     /// The node in which we are currently mapping (an item or a method).
 740     parent: NodeId
 741 }
 742
 743 impl<'ast> NodeCollector<'ast> {
 744     fn insert_entry(&mut self, id: NodeId, entry: MapEntry<'ast>) {
 745         debug!("ast_map: {:?} => {:?}", id, entry);
 746         let len = self.map.len();
 747         if id as uint >= len {
 748             self.map.extend(repeat(NotPresent).take(id as uint - len + 1));
 749         }
 750         self.map[id as uint] = entry;
 751     }
 752
 753     fn insert(&mut self, id: NodeId, node: Node<'ast>) {
 754         let entry = MapEntry::from_node(self.parent, node);
 755         self.insert_entry(id, entry);
 756     }
 757
 758     fn visit_fn_decl(&mut self, decl: &'ast FnDecl) {
 759         for a in decl.inputs.iter() {
 760             self.insert(a.id, NodeArg(&*a.pat));
 761         }
 762     }
 763 }
 764
 765 impl<'ast> Visitor<'ast> for NodeCollector<'ast> {
 766     fn visit_item(&mut self, i: &'ast Item) {
 767         self.insert(i.id, NodeItem(i));
 768         let parent = self.parent;
 769         self.parent = i.id;
 770         match i.node {
 771             ItemImpl(_, _, _, _, _, ref impl_items) => {
 772                 for impl_item in impl_items.iter() {
 773                     match *impl_item {
 774                         MethodImplItem(ref m) => {
 775                             self.insert(m.id, NodeImplItem(impl_item));
 776                         }
 777                         TypeImplItem(ref t) => {
 778                             self.insert(t.id, NodeImplItem(impl_item));
 779                         }
 780                     }
 781                 }
 782             }
 783             ItemEnum(ref enum_definition, _) => {
 784                 for v in enum_definition.variants.iter() {
 785                     self.insert(v.node.id, NodeVariant(&**v));
 786                 }
 787             }
 788             ItemForeignMod(ref nm) => {
 789                 for nitem in nm.items.iter() {
 790                     self.insert(nitem.id, NodeForeignItem(&**nitem));
 791                 }
 792             }
 793             ItemStruct(ref struct_def, _) => {
 794                 // If this is a tuple-like struct, register the constructor.
 795                 match struct_def.ctor_id {
 796                     Some(ctor_id) => {
 797                         self.insert(ctor_id, NodeStructCtor(&**struct_def));
 798                     }
 799                     None => {}
 800                 }
 801             }
 802             ItemTrait(_, _, ref bounds, ref trait_items) => {
 803                 for b in bounds.iter() {
 804                     if let TraitTyParamBound(ref t, TraitBoundModifier::None) = *b {
 805                         self.insert(t.trait_ref.ref_id, NodeItem(i));
 806                     }
 807                 }
 808
 809                 for tm in trait_items.iter() {
 810                     match *tm {
 811                         RequiredMethod(ref m) => {
 812                             self.insert(m.id, NodeTraitItem(tm));
 813                         }
 814                         ProvidedMethod(ref m) => {
 815                             self.insert(m.id, NodeTraitItem(tm));
 816                         }
 817                         TypeTraitItem(ref typ) => {
 818                             self.insert(typ.ty_param.id, NodeTraitItem(tm));
 819                         }
 820                     }
 821                 }
 822             }
 823             _ => {}
 824         }
 825         visit::walk_item(self, i);
 826         self.parent = parent;
 827     }
 828
 829     fn visit_view_item(&mut self, item: &'ast ViewItem) {
 830         self.insert(item.id(), NodeViewItem(item));
 831         visit::walk_view_item(self, item);
 832     }
 833
 834     fn visit_pat(&mut self, pat: &'ast Pat) {
 835         self.insert(pat.id, match pat.node {
 836             // Note: this is at least *potentially* a pattern...
 837             PatIdent(..) => NodeLocal(pat),
 838             _ => NodePat(pat)
 839         });
 840         visit::walk_pat(self, pat);
 841     }
 842
 843     fn visit_expr(&mut self, expr: &'ast Expr) {
 844         self.insert(expr.id, NodeExpr(expr));
 845         visit::walk_expr(self, expr);
 846     }
 847
 848     fn visit_stmt(&mut self, stmt: &'ast Stmt) {
 849         self.insert(ast_util::stmt_id(stmt), NodeStmt(stmt));
 850         visit::walk_stmt(self, stmt);
 851     }
 852
 853     fn visit_ty_method(&mut self, m: &'ast TypeMethod) {
 854         let parent = self.parent;
 855         self.parent = m.id;
 856         self.visit_fn_decl(&*m.decl);
 857         visit::walk_ty_method(self, m);
 858         self.parent = parent;
 859     }
 860
 861     fn visit_fn(&mut self, fk: visit::FnKind<'ast>, fd: &'ast FnDecl,
 862                 b: &'ast Block, s: Span, id: NodeId) {
 863         match fk {
 864             visit::FkMethod(..) => {
 865                 let parent = self.parent;
 866                 self.parent = id;
 867                 self.visit_fn_decl(fd);
 868                 visit::walk_fn(self, fk, fd, b, s);
 869                 self.parent = parent;
 870             }
 871             _ => {
 872                 self.visit_fn_decl(fd);
 873                 visit::walk_fn(self, fk, fd, b, s);
 874             }
 875         }
 876     }
 877
 878     fn visit_ty(&mut self, ty: &'ast Ty) {
 879         match ty.node {
 880             TyBareFn(ref fd) => {
 881                 self.visit_fn_decl(&*fd.decl);
 882             }
 883             _ => {}
 884         }
 885         visit::walk_ty(self, ty);
 886     }
 887
 888     fn visit_block(&mut self, block: &'ast Block) {
 889         self.insert(block.id, NodeBlock(block));
 890         visit::walk_block(self, block);
 891     }
 892
 893     fn visit_lifetime_ref(&mut self, lifetime: &'ast Lifetime) {
 894         self.insert(lifetime.id, NodeLifetime(lifetime));
 895     }
 896
 897     fn visit_lifetime_def(&mut self, def: &'ast LifetimeDef) {
 898         self.visit_lifetime_ref(&def.lifetime);
 899     }
 900 }
 901
 902 pub fn map_crate<'ast, F: FoldOps>(forest: &'ast mut Forest, fold_ops: F) -> Map<'ast> {
 903     // Replace the crate with an empty one to take it out.
 904     let krate = mem::replace(&mut forest.krate, Crate {
 905         module: Mod {
 906             inner: DUMMY_SP,
 907             view_items: vec![],
 908             items: vec![],
 909         },
 910         attrs: vec![],
 911         config: vec![],
 912         exported_macros: vec![],
 913         span: DUMMY_SP
 914     });
 915     forest.krate = IdAndSpanUpdater { fold_ops: fold_ops }.fold_crate(krate);
 916
 917     let mut collector = NodeCollector {
 918         map: vec![],
 919         parent: CRATE_NODE_ID
 920     };
 921     collector.insert_entry(CRATE_NODE_ID, RootCrate);
 922     visit::walk_crate(&mut collector, &forest.krate);
 923     let map = collector.map;
 924
 925     if log_enabled!(::log::DEBUG) {
 926         // This only makes sense for ordered stores; note the
 927         // enumerate to count the number of entries.
 928         let (entries_less_1, _) = map.iter().filter(|&x| {
 929             match *x {
 930                 NotPresent => false,
 931                 _ => true
 932             }
 933         }).enumerate().last().expect("AST map was empty after folding?");
 934
 935         let entries = entries_less_1 + 1;
 936         let vector_length = map.len();
 937         debug!("The AST map has {} entries with a maximum of {}: occupancy {:.1}%",
 938               entries, vector_length, (entries as f64 / vector_length as f64) * 100.);
 939     }
 940
 941     Map {
 942         forest: forest,
 943         map: RefCell::new(map)
 944     }
 945 }
 946
 947 /// Used for items loaded from external crate that are being inlined into this
 948 /// crate.  The `path` should be the path to the item but should not include
 949 /// the item itself.
 950 pub fn map_decoded_item<'ast, F: FoldOps>(map: &Map<'ast>,
 951                                           path: Vec<PathElem>,
 952                                           ii: InlinedItem,
 953                                           fold_ops: F)
 954                                           -> &'ast InlinedItem {
 955     let mut fld = IdAndSpanUpdater { fold_ops: fold_ops };
 956     let ii = match ii {
 957         IIItem(i) => IIItem(fld.fold_item(i).expect_one("expected one item")),
 958         IITraitItem(d, ti) => match ti {
 959             ProvidedMethod(m) => {
 960                 IITraitItem(fld.fold_ops.new_def_id(d),
 961                             ProvidedMethod(fld.fold_method(m)
 962                                               .expect_one("expected one method")))
 963             }
 964             RequiredMethod(ty_m) => {
 965                 IITraitItem(fld.fold_ops.new_def_id(d),
 966                             RequiredMethod(fld.fold_type_method(ty_m)))
 967             }
 968             TypeTraitItem(at) => {
 969                 IITraitItem(
 970                     fld.fold_ops.new_def_id(d),
 971                     TypeTraitItem(P(fld.fold_associated_type((*at).clone()))))
 972             }
 973         },
 974         IIImplItem(d, m) => match m {
 975             MethodImplItem(m) => {
 976                 IIImplItem(fld.fold_ops.new_def_id(d),
 977                            MethodImplItem(fld.fold_method(m)
 978                                              .expect_one("expected one method")))
 979             }
 980             TypeImplItem(t) => {
 981                 IIImplItem(fld.fold_ops.new_def_id(d),
 982                            TypeImplItem(P(fld.fold_typedef((*t).clone()))))
 983             }
 984         },
 985         IIForeign(i) => IIForeign(fld.fold_foreign_item(i))
 986     };
 987
 988     let ii_parent = map.forest.inlined_items.alloc(InlinedParent {
 989         path: path,
 990         ii: ii
 991     });
 992
 993     let mut collector = NodeCollector {
 994         map: mem::replace(&mut *map.map.borrow_mut(), vec![]),
 995         parent: fld.new_id(DUMMY_NODE_ID)
 996     };
 997     let ii_parent_id = collector.parent;
 998     collector.insert_entry(ii_parent_id, RootInlinedParent(ii_parent));
 999     visit::walk_inlined_item(&mut collector, &ii_parent.ii);
1000
1001     // Methods get added to the AST map when their impl is visited.  Since we
1002     // don't decode and instantiate the impl, but just the method, we have to
1003     // add it to the table now. Likewise with foreign items.
1004     match ii_parent.ii {
1005         IIItem(_) => {}
1006         IITraitItem(_, ref trait_item) => {
1007             let trait_item_id = match *trait_item {
1008                 ProvidedMethod(ref m) => m.id,
1009                 RequiredMethod(ref m) => m.id,
1010                 TypeTraitItem(ref ty) => ty.ty_param.id,
1011             };
1012
1013             collector.insert(trait_item_id, NodeTraitItem(trait_item));
1014         }
1015         IIImplItem(_, ref impl_item) => {
1016             let impl_item_id = match *impl_item {
1017                 MethodImplItem(ref m) => m.id,
1018                 TypeImplItem(ref ti) => ti.id,
1019             };
1020
1021             collector.insert(impl_item_id, NodeImplItem(impl_item));
1022         }
1023         IIForeign(ref i) => {
1024             collector.insert(i.id, NodeForeignItem(&**i));
1025         }
1026     }
1027     *map.map.borrow_mut() = collector.map;
1028     &ii_parent.ii
1029 }
1030
1031 pub trait NodePrinter {
1032     fn print_node(&mut self, node: &Node) -> IoResult<()>;
1033 }
1034
1035 impl<'a> NodePrinter for pprust::State<'a> {
1036     fn print_node(&mut self, node: &Node) -> IoResult<()> {
1037         match *node {
1038             NodeItem(a)        => self.print_item(&*a),
1039             NodeViewItem(a)    => self.print_view_item(&*a),
1040             NodeForeignItem(a) => self.print_foreign_item(&*a),
1041             NodeTraitItem(a)   => self.print_trait_method(&*a),
1042             NodeImplItem(a)    => self.print_impl_item(&*a),
1043             NodeVariant(a)     => self.print_variant(&*a),
1044             NodeExpr(a)        => self.print_expr(&*a),
1045             NodeStmt(a)        => self.print_stmt(&*a),
1046             NodePat(a)         => self.print_pat(&*a),
1047             NodeBlock(a)       => self.print_block(&*a),
1048             NodeLifetime(a)    => self.print_lifetime(&*a),
1049
1050             // these cases do not carry enough information in the
1051             // ast_map to reconstruct their full structure for pretty
1052             // printing.
1053             NodeLocal(_)       => panic!("cannot print isolated Local"),
1054             NodeArg(_)         => panic!("cannot print isolated Arg"),
1055             NodeStructCtor(_)  => panic!("cannot print isolated StructCtor"),
1056         }
1057     }
1058 }
1059
1060 fn node_id_to_string(map: &Map, id: NodeId, include_id: bool) -> String {
1061     let id_str = format!(" (id={})", id);
1062     let id_str = if include_id { &id_str[] } else { "" };
1063
1064     match map.find(id) {
1065         Some(NodeItem(item)) => {
1066             let path_str = map.path_to_str_with_ident(id, item.ident);
1067             let item_str = match item.node {
1068                 ItemStatic(..) => "static",
1069                 ItemConst(..) => "const",
1070                 ItemFn(..) => "fn",
1071                 ItemMod(..) => "mod",
1072                 ItemForeignMod(..) => "foreign mod",
1073                 ItemTy(..) => "ty",
1074                 ItemEnum(..) => "enum",
1075                 ItemStruct(..) => "struct",
1076                 ItemTrait(..) => "trait",
1077                 ItemImpl(..) => "impl",
1078                 ItemMac(..) => "macro"
1079             };
1080             format!("{} {}{}", item_str, path_str, id_str)
1081         }
1082         Some(NodeViewItem(item)) => {
1083             format!("view item {}{}", pprust::view_item_to_string(&*item), id_str)
1084         }
1085         Some(NodeForeignItem(item)) => {
1086             let path_str = map.path_to_str_with_ident(id, item.ident);
1087             format!("foreign item {}{}", path_str, id_str)
1088         }
1089         Some(NodeImplItem(ref ii)) => {
1090             match **ii {
1091                 MethodImplItem(ref m) => {
1092                     match m.node {
1093                         MethDecl(ident, _, _, _, _, _, _, _) =>
1094                             format!("method {} in {}{}",
1095                                     token::get_ident(ident),
1096                                     map.path_to_string(id), id_str),
1097                         MethMac(ref mac) =>
1098                             format!("method macro {}{}",
1099                                     pprust::mac_to_string(mac), id_str)
1100                     }
1101                 }
1102                 TypeImplItem(ref t) => {
1103                     format!("typedef {} in {}{}",
1104                             token::get_ident(t.ident),
1105                             map.path_to_string(id),
1106                             id_str)
1107                 }
1108             }
1109         }
1110         Some(NodeTraitItem(ref tm)) => {
1111             match **tm {
1112                 RequiredMethod(_) | ProvidedMethod(_) => {
1113                     let m = ast_util::trait_item_to_ty_method(&**tm);
1114                     format!("method {} in {}{}",
1115                             token::get_ident(m.ident),
1116                             map.path_to_string(id),
1117                             id_str)
1118                 }
1119                 TypeTraitItem(ref t) => {
1120                     format!("type item {} in {}{}",
1121                             token::get_ident(t.ty_param.ident),
1122                             map.path_to_string(id),
1123                             id_str)
1124                 }
1125             }
1126         }
1127         Some(NodeVariant(ref variant)) => {
1128             format!("variant {} in {}{}",
1129                     token::get_ident(variant.node.name),
1130                     map.path_to_string(id), id_str)
1131         }
1132         Some(NodeExpr(ref expr)) => {
1133             format!("expr {}{}", pprust::expr_to_string(&**expr), id_str)
1134         }
1135         Some(NodeStmt(ref stmt)) => {
1136             format!("stmt {}{}", pprust::stmt_to_string(&**stmt), id_str)
1137         }
1138         Some(NodeArg(ref pat)) => {
1139             format!("arg {}{}", pprust::pat_to_string(&**pat), id_str)
1140         }
1141         Some(NodeLocal(ref pat)) => {
1142             format!("local {}{}", pprust::pat_to_string(&**pat), id_str)
1143         }
1144         Some(NodePat(ref pat)) => {
1145             format!("pat {}{}", pprust::pat_to_string(&**pat), id_str)
1146         }
1147         Some(NodeBlock(ref block)) => {
1148             format!("block {}{}", pprust::block_to_string(&**block), id_str)
1149         }
1150         Some(NodeStructCtor(_)) => {
1151             format!("struct_ctor {}{}", map.path_to_string(id), id_str)
1152         }
1153         Some(NodeLifetime(ref l)) => {
1154             format!("lifetime {}{}",
1155                     pprust::lifetime_to_string(&**l), id_str)
1156         }
1157         None => {
1158             format!("unknown node{}", id_str)
1159         }
1160     }
1161 }