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