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;
  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::iter;
  25 use std::slice;
  26
  27 pub mod blocks;
  28
  29 #[deriving(Clone, PartialEq)]
  30 pub enum PathElem {
  31     PathMod(Name),
  32     PathName(Name)
  33 }
  34
  35 impl PathElem {
  36     pub fn name(&self) -> Name {
  37         match *self {
  38             PathMod(name) | PathName(name) => name
  39         }
  40     }
  41 }
  42
  43 impl fmt::Show for PathElem {
  44     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  45         let slot = token::get_name(self.name());
  46         write!(f, "{}", slot)
  47     }
  48 }
  49
  50 #[deriving(Clone)]
  51 struct LinkedPathNode<'a> {
  52     node: PathElem,
  53     next: LinkedPath<'a>,
  54 }
  55
  56 type LinkedPath<'a> = Option<&'a LinkedPathNode<'a>>;
  57
  58 impl<'a> Iterator<PathElem> for LinkedPath<'a> {
  59     fn next(&mut self) -> Option<PathElem> {
  60         match *self {
  61             Some(node) => {
  62                 *self = node.next;
  63                 Some(node.node)
  64             }
  65             None => None
  66         }
  67     }
  68 }
  69
  70 // HACK(eddyb) move this into libstd (value wrapper for slice::Items).
  71 #[deriving(Clone)]
  72 pub struct Values<'a, T>(pub slice::Items<'a, T>);
  73
  74 impl<'a, T: Copy> Iterator<T> for Values<'a, T> {
  75     fn next(&mut self) -> Option<T> {
  76         let &Values(ref mut items) = self;
  77         items.next().map(|&x| x)
  78     }
  79 }
  80
  81 /// The type of the iterator used by with_path.
  82 pub type PathElems<'a, 'b> = iter::Chain<Values<'a, PathElem>, LinkedPath<'b>>;
  83
  84 pub fn path_to_string<PI: Iterator<PathElem>>(mut path: PI) -> String {
  85     let itr = token::get_ident_interner();
  86
  87     path.fold(String::new(), |mut s, e| {
  88         let e = itr.get(e.name());
  89         if !s.is_empty() {
  90             s.push_str("::");
  91         }
  92         s.push_str(e.as_slice());
  93         s
  94     }).to_string()
  95 }
  96
  97 #[deriving(Clone)]
  98 pub enum Node {
  99     NodeItem(Gc<Item>),
 100     NodeForeignItem(Gc<ForeignItem>),
 101     NodeTraitMethod(Gc<TraitMethod>),
 102     NodeMethod(Gc<Method>),
 103     NodeVariant(P<Variant>),
 104     NodeExpr(Gc<Expr>),
 105     NodeStmt(Gc<Stmt>),
 106     NodeArg(Gc<Pat>),
 107     NodeLocal(Gc<Pat>),
 108     NodePat(Gc<Pat>),
 109     NodeBlock(P<Block>),
 110
 111     /// NodeStructCtor represents a tuple struct.
 112     NodeStructCtor(Gc<StructDef>),
 113
 114     NodeLifetime(Gc<Lifetime>),
 115 }
 116
 117 /// Represents an entry and its parent Node ID
 118 /// The odd layout is to bring down the total size.
 119 #[deriving(Clone)]
 120 enum MapEntry {
 121     /// Placeholder for holes in the map.
 122     NotPresent,
 123
 124     /// All the node types, with a parent ID.
 125     EntryItem(NodeId, Gc<Item>),
 126     EntryForeignItem(NodeId, Gc<ForeignItem>),
 127     EntryTraitMethod(NodeId, Gc<TraitMethod>),
 128     EntryMethod(NodeId, Gc<Method>),
 129     EntryVariant(NodeId, P<Variant>),
 130     EntryExpr(NodeId, Gc<Expr>),
 131     EntryStmt(NodeId, Gc<Stmt>),
 132     EntryArg(NodeId, Gc<Pat>),
 133     EntryLocal(NodeId, Gc<Pat>),
 134     EntryPat(NodeId, Gc<Pat>),
 135     EntryBlock(NodeId, P<Block>),
 136     EntryStructCtor(NodeId, Gc<StructDef>),
 137     EntryLifetime(NodeId, Gc<Lifetime>),
 138
 139     /// Roots for node trees.
 140     RootCrate,
 141     RootInlinedParent(P<InlinedParent>)
 142 }
 143
 144 struct InlinedParent {
 145     path: Vec<PathElem> ,
 146     /// Required by NodeTraitMethod and NodeMethod.
 147     def_id: DefId
 148 }
 149
 150 impl MapEntry {
 151     fn parent(&self) -> Option<NodeId> {
 152         Some(match *self {
 153             EntryItem(id, _) => id,
 154             EntryForeignItem(id, _) => id,
 155             EntryTraitMethod(id, _) => id,
 156             EntryMethod(id, _) => id,
 157             EntryVariant(id, _) => id,
 158             EntryExpr(id, _) => id,
 159             EntryStmt(id, _) => id,
 160             EntryArg(id, _) => id,
 161             EntryLocal(id, _) => id,
 162             EntryPat(id, _) => id,
 163             EntryBlock(id, _) => id,
 164             EntryStructCtor(id, _) => id,
 165             EntryLifetime(id, _) => id,
 166             _ => return None
 167         })
 168     }
 169
 170     fn to_node(&self) -> Option<Node> {
 171         Some(match *self {
 172             EntryItem(_, p) => NodeItem(p),
 173             EntryForeignItem(_, p) => NodeForeignItem(p),
 174             EntryTraitMethod(_, p) => NodeTraitMethod(p),
 175             EntryMethod(_, p) => NodeMethod(p),
 176             EntryVariant(_, p) => NodeVariant(p),
 177             EntryExpr(_, p) => NodeExpr(p),
 178             EntryStmt(_, p) => NodeStmt(p),
 179             EntryArg(_, p) => NodeArg(p),
 180             EntryLocal(_, p) => NodeLocal(p),
 181             EntryPat(_, p) => NodePat(p),
 182             EntryBlock(_, p) => NodeBlock(p),
 183             EntryStructCtor(_, p) => NodeStructCtor(p),
 184             EntryLifetime(_, p) => NodeLifetime(p),
 185             _ => return None
 186         })
 187     }
 188 }
 189
 190 /// Represents a mapping from Node IDs to AST elements and their parent
 191 /// Node IDs
 192 pub struct Map {
 193     /// NodeIds are sequential integers from 0, so we can be
 194     /// super-compact by storing them in a vector. Not everything with
 195     /// a NodeId is in the map, but empirically the occupancy is about
 196     /// 75-80%, so there's not too much overhead (certainly less than
 197     /// a hashmap, since they (at the time of writing) have a maximum
 198     /// of 75% occupancy).
 199     ///
 200     /// Also, indexing is pretty quick when you've got a vector and
 201     /// plain old integers.
 202     map: RefCell<Vec<MapEntry> >
 203 }
 204
 205 impl Map {
 206     fn find_entry(&self, id: NodeId) -> Option<MapEntry> {
 207         let map = self.map.borrow();
 208         if map.len() > id as uint {
 209             Some(*map.get(id as uint))
 210         } else {
 211             None
 212         }
 213     }
 214
 215     /// Retrieve the Node corresponding to `id`, failing if it cannot
 216     /// be found.
 217     pub fn get(&self, id: NodeId) -> Node {
 218         match self.find(id) {
 219             Some(node) => node,
 220             None => fail!("couldn't find node id {} in the AST map", id)
 221         }
 222     }
 223
 224     /// Retrieve the Node corresponding to `id`, returning None if
 225     /// cannot be found.
 226     pub fn find(&self, id: NodeId) -> Option<Node> {
 227         self.find_entry(id).and_then(|x| x.to_node())
 228     }
 229
 230     /// Retrieve the parent NodeId for `id`, or `id` itself if no
 231     /// parent is registered in this map.
 232     pub fn get_parent(&self, id: NodeId) -> NodeId {
 233         self.find_entry(id).and_then(|x| x.parent()).unwrap_or(id)
 234     }
 235
 236     pub fn get_parent_did(&self, id: NodeId) -> DefId {
 237         let parent = self.get_parent(id);
 238         match self.find_entry(parent) {
 239             Some(RootInlinedParent(data)) => data.def_id,
 240             _ => ast_util::local_def(parent)
 241         }
 242     }
 243
 244     pub fn get_foreign_abi(&self, id: NodeId) -> abi::Abi {
 245         let parent = self.get_parent(id);
 246         let abi = match self.find_entry(parent) {
 247             Some(EntryItem(_, i)) => match i.node {
 248                 ItemForeignMod(ref nm) => Some(nm.abi),
 249                 _ => None
 250             },
 251             /// Wrong but OK, because the only inlined foreign items are intrinsics.
 252             Some(RootInlinedParent(_)) => Some(abi::RustIntrinsic),
 253             _ => None
 254         };
 255         match abi {
 256             Some(abi) => abi,
 257             None => fail!("expected foreign mod or inlined parent, found {}",
 258                           self.node_to_string(parent))
 259         }
 260     }
 261
 262     pub fn get_foreign_vis(&self, id: NodeId) -> Visibility {
 263         let vis = self.expect_foreign_item(id).vis;
 264         match self.find(self.get_parent(id)) {
 265             Some(NodeItem(i)) => vis.inherit_from(i.vis),
 266             _ => vis
 267         }
 268     }
 269
 270     pub fn expect_item(&self, id: NodeId) -> Gc<Item> {
 271         match self.find(id) {
 272             Some(NodeItem(item)) => item,
 273             _ => fail!("expected item, found {}", self.node_to_string(id))
 274         }
 275     }
 276
 277     pub fn expect_struct(&self, id: NodeId) -> Gc<StructDef> {
 278         match self.find(id) {
 279             Some(NodeItem(i)) => {
 280                 match i.node {
 281                     ItemStruct(struct_def, _) => struct_def,
 282                     _ => fail!("struct ID bound to non-struct")
 283                 }
 284             }
 285             Some(NodeVariant(ref variant)) => {
 286                 match (*variant).node.kind {
 287                     StructVariantKind(struct_def) => struct_def,
 288                     _ => fail!("struct ID bound to enum variant that isn't struct-like"),
 289                 }
 290             }
 291             _ => fail!(format!("expected struct, found {}", self.node_to_string(id))),
 292         }
 293     }
 294
 295     pub fn expect_variant(&self, id: NodeId) -> P<Variant> {
 296         match self.find(id) {
 297             Some(NodeVariant(variant)) => variant,
 298             _ => fail!(format!("expected variant, found {}", self.node_to_string(id))),
 299         }
 300     }
 301
 302     pub fn expect_foreign_item(&self, id: NodeId) -> Gc<ForeignItem> {
 303         match self.find(id) {
 304             Some(NodeForeignItem(item)) => item,
 305             _ => fail!("expected foreign item, found {}", self.node_to_string(id))
 306         }
 307     }
 308
 309     /// returns the name associated with the given NodeId's AST
 310     pub fn get_path_elem(&self, id: NodeId) -> PathElem {
 311         let node = self.get(id);
 312         match node {
 313             NodeItem(item) => {
 314                 match item.node {
 315                     ItemMod(_) | ItemForeignMod(_) => {
 316                         PathMod(item.ident.name)
 317                     }
 318                     _ => PathName(item.ident.name)
 319                 }
 320             }
 321             NodeForeignItem(i) => PathName(i.ident.name),
 322             NodeMethod(m) => match m.node {
 323                 MethDecl(ident, _, _, _, _, _, _, _) => PathName(ident.name),
 324                 MethMac(_) => fail!("no path elem for {:?}", node)
 325             },
 326             NodeTraitMethod(tm) => match *tm {
 327                 Required(ref m) => PathName(m.ident.name),
 328                 Provided(m) => match m.node {
 329                     MethDecl(ident, _, _, _, _, _, _, _) => {
 330                         PathName(ident.name)
 331                     }
 332                     MethMac(_) => fail!("no path elem for {:?}", node),
 333                 }
 334             },
 335             NodeVariant(v) => PathName(v.node.name.name),
 336             _ => fail!("no path elem for {:?}", node)
 337         }
 338     }
 339
 340     pub fn with_path<T>(&self, id: NodeId, f: |PathElems| -> T) -> T {
 341         self.with_path_next(id, None, f)
 342     }
 343
 344     pub fn path_to_string(&self, id: NodeId) -> String {
 345         self.with_path(id, |path| path_to_string(path))
 346     }
 347
 348     fn path_to_str_with_ident(&self, id: NodeId, i: Ident) -> String {
 349         self.with_path(id, |path| {
 350             path_to_string(path.chain(Some(PathName(i.name)).move_iter()))
 351         })
 352     }
 353
 354     fn with_path_next<T>(&self, id: NodeId, next: LinkedPath, f: |PathElems| -> T) -> T {
 355         let parent = self.get_parent(id);
 356         let parent = match self.find_entry(id) {
 357             Some(EntryForeignItem(..)) | Some(EntryVariant(..)) => {
 358                 // Anonymous extern items, enum variants and struct ctors
 359                 // go in the parent scope.
 360                 self.get_parent(parent)
 361             }
 362             // But tuple struct ctors don't have names, so use the path of its
 363             // parent, the struct item. Similarly with closure expressions.
 364             Some(EntryStructCtor(..)) | Some(EntryExpr(..)) => {
 365                 return self.with_path_next(parent, next, f);
 366             }
 367             _ => parent
 368         };
 369         if parent == id {
 370             match self.find_entry(id) {
 371                 Some(RootInlinedParent(data)) => {
 372                     f(Values(data.path.iter()).chain(next))
 373                 }
 374                 _ => f(Values([].iter()).chain(next))
 375             }
 376         } else {
 377             self.with_path_next(parent, Some(&LinkedPathNode {
 378                 node: self.get_path_elem(id),
 379                 next: next
 380             }), f)
 381         }
 382     }
 383
 384     /// Given a node ID and a closure, apply the closure to the array
 385     /// of attributes associated with the AST corresponding to the Node ID
 386     pub fn with_attrs<T>(&self, id: NodeId, f: |Option<&[Attribute]>| -> T) -> T {
 387         let node = self.get(id);
 388         let attrs = match node {
 389             NodeItem(ref i) => Some(i.attrs.as_slice()),
 390             NodeForeignItem(ref fi) => Some(fi.attrs.as_slice()),
 391             NodeTraitMethod(ref tm) => match **tm {
 392                 Required(ref type_m) => Some(type_m.attrs.as_slice()),
 393                 Provided(ref m) => Some(m.attrs.as_slice())
 394             },
 395             NodeMethod(ref m) => Some(m.attrs.as_slice()),
 396             NodeVariant(ref v) => Some(v.node.attrs.as_slice()),
 397             // unit/tuple structs take the attributes straight from
 398             // the struct definition.
 399             // FIXME(eddyb) make this work again (requires access to the map).
 400             NodeStructCtor(_) => {
 401                 return self.with_attrs(self.get_parent(id), f);
 402             }
 403             _ => None
 404         };
 405         f(attrs)
 406     }
 407
 408     pub fn opt_span(&self, id: NodeId) -> Option<Span> {
 409         let sp = match self.find(id) {
 410             Some(NodeItem(item)) => item.span,
 411             Some(NodeForeignItem(foreign_item)) => foreign_item.span,
 412             Some(NodeTraitMethod(trait_method)) => {
 413                 match *trait_method {
 414                     Required(ref type_method) => type_method.span,
 415                     Provided(ref method) => method.span,
 416                 }
 417             }
 418             Some(NodeMethod(method)) => method.span,
 419             Some(NodeVariant(variant)) => variant.span,
 420             Some(NodeExpr(expr)) => expr.span,
 421             Some(NodeStmt(stmt)) => stmt.span,
 422             Some(NodeArg(pat)) | Some(NodeLocal(pat)) => pat.span,
 423             Some(NodePat(pat)) => pat.span,
 424             Some(NodeBlock(block)) => block.span,
 425             Some(NodeStructCtor(_)) => self.expect_item(self.get_parent(id)).span,
 426             _ => return None,
 427         };
 428         Some(sp)
 429     }
 430
 431     pub fn span(&self, id: NodeId) -> Span {
 432         self.opt_span(id)
 433             .unwrap_or_else(|| fail!("AstMap.span: could not find span for id {}", id))
 434     }
 435
 436     pub fn node_to_string(&self, id: NodeId) -> String {
 437         node_id_to_string(self, id)
 438     }
 439 }
 440
 441 pub trait FoldOps {
 442     fn new_id(&self, id: NodeId) -> NodeId {
 443         id
 444     }
 445     fn new_span(&self, span: Span) -> Span {
 446         span
 447     }
 448 }
 449
 450 /// A Folder that walks over an AST and constructs a Node ID Map. Its
 451 /// fold_ops argument has the opportunity to replace Node IDs and spans.
 452 pub struct Ctx<'a, F> {
 453     map: &'a Map,
 454     /// The node in which we are currently mapping (an item or a method).
 455     /// When equal to DUMMY_NODE_ID, the next mapped node becomes the parent.
 456     parent: NodeId,
 457     fold_ops: F
 458 }
 459
 460 impl<'a, F> Ctx<'a, F> {
 461     fn insert(&self, id: NodeId, entry: MapEntry) {
 462         (*self.map.map.borrow_mut()).grow_set(id as uint, &NotPresent, entry);
 463     }
 464 }
 465
 466 impl<'a, F: FoldOps> Folder for Ctx<'a, F> {
 467     fn new_id(&mut self, id: NodeId) -> NodeId {
 468         let id = self.fold_ops.new_id(id);
 469         if self.parent == DUMMY_NODE_ID {
 470             self.parent = id;
 471         }
 472         id
 473     }
 474
 475     fn new_span(&mut self, span: Span) -> Span {
 476         self.fold_ops.new_span(span)
 477     }
 478
 479     fn fold_item(&mut self, i: Gc<Item>) -> SmallVector<Gc<Item>> {
 480         let parent = self.parent;
 481         self.parent = DUMMY_NODE_ID;
 482
 483         let i = fold::noop_fold_item(&*i, self).expect_one("expected one item");
 484         assert_eq!(self.parent, i.id);
 485
 486         match i.node {
 487             ItemImpl(_, _, _, ref ms) => {
 488                 for &m in ms.iter() {
 489                     self.insert(m.id, EntryMethod(self.parent, m));
 490                 }
 491             }
 492             ItemEnum(ref enum_definition, _) => {
 493                 for &v in enum_definition.variants.iter() {
 494                     self.insert(v.node.id, EntryVariant(self.parent, v));
 495                 }
 496             }
 497             ItemForeignMod(ref nm) => {
 498                 for nitem in nm.items.iter() {
 499                     self.insert(nitem.id, EntryForeignItem(self.parent,
 500                                                            nitem.clone()));
 501                 }
 502             }
 503             ItemStruct(ref struct_def, _) => {
 504                 // If this is a tuple-like struct, register the constructor.
 505                 match struct_def.ctor_id {
 506                     Some(ctor_id) => {
 507                         self.insert(ctor_id, EntryStructCtor(self.parent,
 508                                                              struct_def.clone()));
 509                     }
 510                     None => {}
 511                 }
 512             }
 513             ItemTrait(_, _, ref traits, ref methods) => {
 514                 for t in traits.iter() {
 515                     self.insert(t.ref_id, EntryItem(self.parent, i));
 516                 }
 517
 518                 for tm in methods.iter() {
 519                     match *tm {
 520                         Required(ref m) => {
 521                             self.insert(m.id, EntryTraitMethod(self.parent,
 522                                                                box(GC) (*tm).clone()));
 523                         }
 524                         Provided(m) => {
 525                             self.insert(m.id, EntryTraitMethod(self.parent,
 526                                                                box(GC) Provided(m)));
 527                         }
 528                     }
 529                 }
 530             }
 531             _ => {}
 532         }
 533
 534         self.parent = parent;
 535         self.insert(i.id, EntryItem(self.parent, i));
 536
 537         SmallVector::one(i)
 538     }
 539
 540     fn fold_pat(&mut self, pat: Gc<Pat>) -> Gc<Pat> {
 541         let pat = fold::noop_fold_pat(pat, self);
 542         match pat.node {
 543             PatIdent(..) => {
 544                 // Note: this is at least *potentially* a pattern...
 545                 self.insert(pat.id, EntryLocal(self.parent, pat));
 546             }
 547             _ => {
 548                 self.insert(pat.id, EntryPat(self.parent, pat));
 549             }
 550         }
 551
 552         pat
 553     }
 554
 555     fn fold_expr(&mut self, expr: Gc<Expr>) -> Gc<Expr> {
 556         let expr = fold::noop_fold_expr(expr, self);
 557
 558         self.insert(expr.id, EntryExpr(self.parent, expr));
 559
 560         expr
 561     }
 562
 563     fn fold_stmt(&mut self, stmt: &Stmt) -> SmallVector<Gc<Stmt>> {
 564         let stmt = fold::noop_fold_stmt(stmt, self).expect_one("expected one statement");
 565         self.insert(ast_util::stmt_id(&*stmt), EntryStmt(self.parent, stmt));
 566         SmallVector::one(stmt)
 567     }
 568
 569     fn fold_type_method(&mut self, m: &TypeMethod) -> TypeMethod {
 570         let parent = self.parent;
 571         self.parent = DUMMY_NODE_ID;
 572         let m = fold::noop_fold_type_method(m, self);
 573         assert_eq!(self.parent, m.id);
 574         self.parent = parent;
 575         m
 576     }
 577
 578     fn fold_method(&mut self, m: Gc<Method>) -> SmallVector<Gc<Method>> {
 579         let parent = self.parent;
 580         self.parent = DUMMY_NODE_ID;
 581         let m = fold::noop_fold_method(&*m, self).expect_one(
 582             "noop_fold_method must produce exactly one method");
 583         assert_eq!(self.parent, m.id);
 584         self.parent = parent;
 585         SmallVector::one(m)
 586     }
 587
 588     fn fold_fn_decl(&mut self, decl: &FnDecl) -> P<FnDecl> {
 589         let decl = fold::noop_fold_fn_decl(decl, self);
 590         for a in decl.inputs.iter() {
 591             self.insert(a.id, EntryArg(self.parent, a.pat));
 592         }
 593         decl
 594     }
 595
 596     fn fold_block(&mut self, block: P<Block>) -> P<Block> {
 597         let block = fold::noop_fold_block(block, self);
 598         self.insert(block.id, EntryBlock(self.parent, block));
 599         block
 600     }
 601
 602     fn fold_lifetime(&mut self, lifetime: &Lifetime) -> Lifetime {
 603         let lifetime = fold::noop_fold_lifetime(lifetime, self);
 604         self.insert(lifetime.id, EntryLifetime(self.parent, box(GC) lifetime));
 605         lifetime
 606     }
 607
 608     fn fold_mac(&mut self, mac: &Mac) -> Mac {
 609         fold::noop_fold_mac(mac, self)
 610     }
 611 }
 612
 613 pub fn map_crate<F: FoldOps>(krate: Crate, fold_ops: F) -> (Crate, Map) {
 614     let map = Map { map: RefCell::new(Vec::new()) };
 615     let krate = {
 616         let mut cx = Ctx {
 617             map: &map,
 618             parent: CRATE_NODE_ID,
 619             fold_ops: fold_ops
 620         };
 621         cx.insert(CRATE_NODE_ID, RootCrate);
 622         cx.fold_crate(krate)
 623     };
 624
 625     if log_enabled!(::log::DEBUG) {
 626         let map = map.map.borrow();
 627         // This only makes sense for ordered stores; note the
 628         // enumerate to count the number of entries.
 629         let (entries_less_1, _) = (*map).iter().filter(|&x| {
 630             match *x {
 631                 NotPresent => false,
 632                 _ => true
 633             }
 634         }).enumerate().last().expect("AST map was empty after folding?");
 635
 636         let entries = entries_less_1 + 1;
 637         let vector_length = (*map).len();
 638         debug!("The AST map has {} entries with a maximum of {}: occupancy {:.1}%",
 639               entries, vector_length, (entries as f64 / vector_length as f64) * 100.);
 640     }
 641
 642     (krate, map)
 643 }
 644
 645 /// Used for items loaded from external crate that are being inlined into this
 646 /// crate.  The `path` should be the path to the item but should not include
 647 /// the item itself.
 648 pub fn map_decoded_item<F: FoldOps>(map: &Map,
 649                                     path: Vec<PathElem> ,
 650                                     fold_ops: F,
 651                                     fold: |&mut Ctx<F>| -> InlinedItem)
 652                                     -> InlinedItem {
 653     let mut cx = Ctx {
 654         map: map,
 655         parent: DUMMY_NODE_ID,
 656         fold_ops: fold_ops
 657     };
 658
 659     // Generate a NodeId for the RootInlinedParent inserted below.
 660     cx.new_id(DUMMY_NODE_ID);
 661
 662     // Methods get added to the AST map when their impl is visited.  Since we
 663     // don't decode and instantiate the impl, but just the method, we have to
 664     // add it to the table now. Likewise with foreign items.
 665     let mut def_id = DefId { krate: LOCAL_CRATE, node: DUMMY_NODE_ID };
 666     let ii = fold(&mut cx);
 667     match ii {
 668         IIItem(_) => {}
 669         IIMethod(impl_did, is_provided, m) => {
 670             let entry = if is_provided {
 671                 EntryTraitMethod(cx.parent, box(GC) Provided(m))
 672             } else {
 673                 EntryMethod(cx.parent, m)
 674             };
 675             cx.insert(m.id, entry);
 676             def_id = impl_did;
 677         }
 678         IIForeign(i) => {
 679             cx.insert(i.id, EntryForeignItem(cx.parent, i));
 680         }
 681     }
 682
 683     cx.insert(cx.parent, RootInlinedParent(P(InlinedParent {
 684         path: path,
 685         def_id: def_id
 686     })));
 687
 688     ii
 689 }
 690
 691 fn node_id_to_string(map: &Map, id: NodeId) -> String {
 692     match map.find(id) {
 693         Some(NodeItem(item)) => {
 694             let path_str = map.path_to_str_with_ident(id, item.ident);
 695             let item_str = match item.node {
 696                 ItemStatic(..) => "static",
 697                 ItemFn(..) => "fn",
 698                 ItemMod(..) => "mod",
 699                 ItemForeignMod(..) => "foreign mod",
 700                 ItemTy(..) => "ty",
 701                 ItemEnum(..) => "enum",
 702                 ItemStruct(..) => "struct",
 703                 ItemTrait(..) => "trait",
 704                 ItemImpl(..) => "impl",
 705                 ItemMac(..) => "macro"
 706             };
 707             format!("{} {} (id={})", item_str, path_str, id)
 708         }
 709         Some(NodeForeignItem(item)) => {
 710             let path_str = map.path_to_str_with_ident(id, item.ident);
 711             format!("foreign item {} (id={})", path_str, id)
 712         }
 713         Some(NodeMethod(m)) => match m.node {
 714             MethDecl(ident, _, _, _, _, _, _, _) =>
 715                 format!("method {} in {} (id={})",
 716                         token::get_ident(ident),
 717                         map.path_to_string(id), id),
 718             MethMac(ref mac) =>
 719                 format!("method macro {} (id={})",
 720                         pprust::mac_to_string(mac), id)
 721         },
 722         Some(NodeTraitMethod(ref tm)) => {
 723             let m = ast_util::trait_method_to_ty_method(&**tm);
 724             format!("method {} in {} (id={})",
 725                     token::get_ident(m.ident),
 726                     map.path_to_string(id), id)
 727         }
 728         Some(NodeVariant(ref variant)) => {
 729             format!("variant {} in {} (id={})",
 730                     token::get_ident(variant.node.name),
 731                     map.path_to_string(id), id)
 732         }
 733         Some(NodeExpr(ref expr)) => {
 734             format!("expr {} (id={})", pprust::expr_to_string(&**expr), id)
 735         }
 736         Some(NodeStmt(ref stmt)) => {
 737             format!("stmt {} (id={})", pprust::stmt_to_string(&**stmt), id)
 738         }
 739         Some(NodeArg(ref pat)) => {
 740             format!("arg {} (id={})", pprust::pat_to_string(&**pat), id)
 741         }
 742         Some(NodeLocal(ref pat)) => {
 743             format!("local {} (id={})", pprust::pat_to_string(&**pat), id)
 744         }
 745         Some(NodePat(ref pat)) => {
 746             format!("pat {} (id={})", pprust::pat_to_string(&**pat), id)
 747         }
 748         Some(NodeBlock(ref block)) => {
 749             format!("block {} (id={})", pprust::block_to_string(&**block), id)
 750         }
 751         Some(NodeStructCtor(_)) => {
 752             format!("struct_ctor {} (id={})", map.path_to_string(id), id)
 753         }
 754         Some(NodeLifetime(ref l)) => {
 755             format!("lifetime {} (id={})",
 756                     pprust::lifetime_to_string(&**l), id)
 757         }
 758         None => {
 759             format!("unknown node (id={})", id)
 760         }
 761     }
 762 }