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