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