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