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.
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.
19 use util::small_vector::SmallVector;
21 use std::cell::RefCell;
23 use std::gc::{Gc, GC};
29 #[deriving(Clone, PartialEq)]
36 pub fn name(&self) -> Name {
38 PathMod(name) | PathName(name) => name
43 impl fmt::Show for PathElem {
44 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
45 let slot = token::get_name(self.name());
51 struct LinkedPathNode<'a> {
56 type LinkedPath<'a> = Option<&'a LinkedPathNode<'a>>;
58 impl<'a> Iterator<PathElem> for LinkedPath<'a> {
59 fn next(&mut self) -> Option<PathElem> {
70 // HACK(eddyb) move this into libstd (value wrapper for slice::Items).
72 pub struct Values<'a, T>(pub slice::Items<'a, T>);
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)
81 /// The type of the iterator used by with_path.
82 pub type PathElems<'a, 'b> = iter::Chain<Values<'a, PathElem>, LinkedPath<'b>>;
84 pub fn path_to_string<PI: Iterator<PathElem>>(mut path: PI) -> String {
85 let itr = token::get_ident_interner();
87 path.fold(String::new(), |mut s, e| {
88 let e = itr.get(e.name());
92 s.push_str(e.as_slice());
100 NodeForeignItem(Gc<ForeignItem>),
101 NodeTraitMethod(Gc<TraitMethod>),
102 NodeMethod(Gc<Method>),
103 NodeVariant(P<Variant>),
111 /// NodeStructCtor represents a tuple struct.
112 NodeStructCtor(Gc<StructDef>),
114 NodeLifetime(Gc<Lifetime>),
117 /// Represents an entry and its parent Node ID
118 /// The odd layout is to bring down the total size.
121 /// Placeholder for holes in the map.
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>),
139 /// Roots for node trees.
141 RootInlinedParent(P<InlinedParent>)
144 struct InlinedParent {
145 path: Vec<PathElem> ,
146 /// Required by NodeTraitMethod and NodeMethod.
151 fn parent(&self) -> Option<NodeId> {
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,
170 fn to_node(&self) -> Option<Node> {
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),
190 /// Represents a mapping from Node IDs to AST elements and their parent
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).
200 /// Also, indexing is pretty quick when you've got a vector and
201 /// plain old integers.
202 map: RefCell<Vec<MapEntry> >
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))
215 /// Retrieve the Node corresponding to `id`, failing if it cannot
217 pub fn get(&self, id: NodeId) -> Node {
218 match self.find(id) {
220 None => fail!("couldn't find node id {} in the AST map", id)
224 /// Retrieve the Node corresponding to `id`, returning None if
226 pub fn find(&self, id: NodeId) -> Option<Node> {
227 self.find_entry(id).and_then(|x| x.to_node())
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)
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)
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),
251 /// Wrong but OK, because the only inlined foreign items are intrinsics.
252 Some(RootInlinedParent(_)) => Some(abi::RustIntrinsic),
257 None => fail!("expected foreign mod or inlined parent, found {}",
258 self.node_to_string(parent))
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),
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))
277 pub fn expect_struct(&self, id: NodeId) -> Gc<StructDef> {
278 match self.find(id) {
279 Some(NodeItem(i)) => {
281 ItemStruct(struct_def, _) => struct_def,
282 _ => fail!("struct ID bound to non-struct")
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"),
291 _ => fail!(format!("expected struct, found {}", self.node_to_string(id))),
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))),
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))
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);
315 ItemMod(_) | ItemForeignMod(_) => {
316 PathMod(item.ident.name)
318 _ => PathName(item.ident.name)
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)
326 NodeTraitMethod(tm) => match *tm {
327 Required(ref m) => PathName(m.ident.name),
328 Provided(m) => match m.node {
329 MethDecl(ident, _, _, _, _, _, _) => PathName(ident.name),
330 MethMac(_) => fail!("no path elem for {:?}", node),
333 NodeVariant(v) => PathName(v.node.name.name),
334 _ => fail!("no path elem for {:?}", node)
338 pub fn with_path<T>(&self, id: NodeId, f: |PathElems| -> T) -> T {
339 self.with_path_next(id, None, f)
342 pub fn path_to_string(&self, id: NodeId) -> String {
343 self.with_path(id, |path| path_to_string(path))
346 fn path_to_str_with_ident(&self, id: NodeId, i: Ident) -> String {
347 self.with_path(id, |path| {
348 path_to_string(path.chain(Some(PathName(i.name)).move_iter()))
352 fn with_path_next<T>(&self, id: NodeId, next: LinkedPath, f: |PathElems| -> T) -> T {
353 let parent = self.get_parent(id);
354 let parent = match self.find_entry(id) {
355 Some(EntryForeignItem(..)) | Some(EntryVariant(..)) => {
356 // Anonymous extern items, enum variants and struct ctors
357 // go in the parent scope.
358 self.get_parent(parent)
360 // But tuple struct ctors don't have names, so use the path of its
361 // parent, the struct item. Similarly with closure expressions.
362 Some(EntryStructCtor(..)) | Some(EntryExpr(..)) => {
363 return self.with_path_next(parent, next, f);
368 match self.find_entry(id) {
369 Some(RootInlinedParent(data)) => {
370 f(Values(data.path.iter()).chain(next))
372 _ => f(Values([].iter()).chain(next))
375 self.with_path_next(parent, Some(&LinkedPathNode {
376 node: self.get_path_elem(id),
382 /// Given a node ID and a closure, apply the closure to the array
383 /// of attributes associated with the AST corresponding to the Node ID
384 pub fn with_attrs<T>(&self, id: NodeId, f: |Option<&[Attribute]>| -> T) -> T {
385 let node = self.get(id);
386 let attrs = match node {
387 NodeItem(ref i) => Some(i.attrs.as_slice()),
388 NodeForeignItem(ref fi) => Some(fi.attrs.as_slice()),
389 NodeTraitMethod(ref tm) => match **tm {
390 Required(ref type_m) => Some(type_m.attrs.as_slice()),
391 Provided(ref m) => Some(m.attrs.as_slice())
393 NodeMethod(ref m) => Some(m.attrs.as_slice()),
394 NodeVariant(ref v) => Some(v.node.attrs.as_slice()),
395 // unit/tuple structs take the attributes straight from
396 // the struct definition.
397 // FIXME(eddyb) make this work again (requires access to the map).
398 NodeStructCtor(_) => {
399 return self.with_attrs(self.get_parent(id), f);
406 pub fn opt_span(&self, id: NodeId) -> Option<Span> {
407 let sp = match self.find(id) {
408 Some(NodeItem(item)) => item.span,
409 Some(NodeForeignItem(foreign_item)) => foreign_item.span,
410 Some(NodeTraitMethod(trait_method)) => {
411 match *trait_method {
412 Required(ref type_method) => type_method.span,
413 Provided(ref method) => method.span,
416 Some(NodeMethod(method)) => method.span,
417 Some(NodeVariant(variant)) => variant.span,
418 Some(NodeExpr(expr)) => expr.span,
419 Some(NodeStmt(stmt)) => stmt.span,
420 Some(NodeArg(pat)) | Some(NodeLocal(pat)) => pat.span,
421 Some(NodePat(pat)) => pat.span,
422 Some(NodeBlock(block)) => block.span,
423 Some(NodeStructCtor(_)) => self.expect_item(self.get_parent(id)).span,
429 pub fn span(&self, id: NodeId) -> Span {
431 .unwrap_or_else(|| fail!("AstMap.span: could not find span for id {}", id))
434 pub fn node_to_string(&self, id: NodeId) -> String {
435 node_id_to_string(self, id)
440 fn new_id(&self, id: NodeId) -> NodeId {
443 fn new_span(&self, span: Span) -> Span {
448 /// A Folder that walks over an AST and constructs a Node ID Map. Its
449 /// fold_ops argument has the opportunity to replace Node IDs and spans.
450 pub struct Ctx<'a, F> {
452 /// The node in which we are currently mapping (an item or a method).
453 /// When equal to DUMMY_NODE_ID, the next mapped node becomes the parent.
458 impl<'a, F> Ctx<'a, F> {
459 fn insert(&self, id: NodeId, entry: MapEntry) {
460 (*self.map.map.borrow_mut()).grow_set(id as uint, &NotPresent, entry);
464 impl<'a, F: FoldOps> Folder for Ctx<'a, F> {
465 fn new_id(&mut self, id: NodeId) -> NodeId {
466 let id = self.fold_ops.new_id(id);
467 if self.parent == DUMMY_NODE_ID {
473 fn new_span(&mut self, span: Span) -> Span {
474 self.fold_ops.new_span(span)
477 fn fold_item(&mut self, i: Gc<Item>) -> SmallVector<Gc<Item>> {
478 let parent = self.parent;
479 self.parent = DUMMY_NODE_ID;
481 let i = fold::noop_fold_item(&*i, self).expect_one("expected one item");
482 assert_eq!(self.parent, i.id);
485 ItemImpl(_, _, _, ref ms) => {
486 for &m in ms.iter() {
487 self.insert(m.id, EntryMethod(self.parent, m));
490 ItemEnum(ref enum_definition, _) => {
491 for &v in enum_definition.variants.iter() {
492 self.insert(v.node.id, EntryVariant(self.parent, v));
495 ItemForeignMod(ref nm) => {
496 for nitem in nm.items.iter() {
497 self.insert(nitem.id, EntryForeignItem(self.parent,
501 ItemStruct(ref struct_def, _) => {
502 // If this is a tuple-like struct, register the constructor.
503 match struct_def.ctor_id {
505 self.insert(ctor_id, EntryStructCtor(self.parent,
506 struct_def.clone()));
511 ItemTrait(_, _, ref traits, ref methods) => {
512 for t in traits.iter() {
513 self.insert(t.ref_id, EntryItem(self.parent, i));
516 for tm in methods.iter() {
519 self.insert(m.id, EntryTraitMethod(self.parent,
520 box(GC) (*tm).clone()));
523 self.insert(m.id, EntryTraitMethod(self.parent,
524 box(GC) Provided(m)));
532 self.parent = parent;
533 self.insert(i.id, EntryItem(self.parent, i));
538 fn fold_pat(&mut self, pat: Gc<Pat>) -> Gc<Pat> {
539 let pat = fold::noop_fold_pat(pat, self);
542 // Note: this is at least *potentially* a pattern...
543 self.insert(pat.id, EntryLocal(self.parent, pat));
546 self.insert(pat.id, EntryPat(self.parent, pat));
553 fn fold_expr(&mut self, expr: Gc<Expr>) -> Gc<Expr> {
554 let expr = fold::noop_fold_expr(expr, self);
556 self.insert(expr.id, EntryExpr(self.parent, expr));
561 fn fold_stmt(&mut self, stmt: &Stmt) -> SmallVector<Gc<Stmt>> {
562 let stmt = fold::noop_fold_stmt(stmt, self).expect_one("expected one statement");
563 self.insert(ast_util::stmt_id(&*stmt), EntryStmt(self.parent, stmt));
564 SmallVector::one(stmt)
567 fn fold_type_method(&mut self, m: &TypeMethod) -> TypeMethod {
568 let parent = self.parent;
569 self.parent = DUMMY_NODE_ID;
570 let m = fold::noop_fold_type_method(m, self);
571 assert_eq!(self.parent, m.id);
572 self.parent = parent;
576 fn fold_method(&mut self, m: Gc<Method>) -> SmallVector<Gc<Method>> {
577 let parent = self.parent;
578 self.parent = DUMMY_NODE_ID;
579 let m = fold::noop_fold_method(&*m, self).expect_one(
580 "noop_fold_method must produce exactly one method");
581 assert_eq!(self.parent, m.id);
582 self.parent = parent;
586 fn fold_fn_decl(&mut self, decl: &FnDecl) -> P<FnDecl> {
587 let decl = fold::noop_fold_fn_decl(decl, self);
588 for a in decl.inputs.iter() {
589 self.insert(a.id, EntryArg(self.parent, a.pat));
594 fn fold_block(&mut self, block: P<Block>) -> P<Block> {
595 let block = fold::noop_fold_block(block, self);
596 self.insert(block.id, EntryBlock(self.parent, block));
600 fn fold_lifetime(&mut self, lifetime: &Lifetime) -> Lifetime {
601 let lifetime = fold::noop_fold_lifetime(lifetime, self);
602 self.insert(lifetime.id, EntryLifetime(self.parent, box(GC) lifetime));
606 fn fold_mac(&mut self, mac: &Mac) -> Mac {
607 fold::fold_mac(mac, self)
611 pub fn map_crate<F: FoldOps>(krate: Crate, fold_ops: F) -> (Crate, Map) {
612 let map = Map { map: RefCell::new(Vec::new()) };
616 parent: CRATE_NODE_ID,
619 cx.insert(CRATE_NODE_ID, RootCrate);
623 if log_enabled!(::log::DEBUG) {
624 let map = map.map.borrow();
625 // This only makes sense for ordered stores; note the
626 // enumerate to count the number of entries.
627 let (entries_less_1, _) = (*map).iter().filter(|&x| {
632 }).enumerate().last().expect("AST map was empty after folding?");
634 let entries = entries_less_1 + 1;
635 let vector_length = (*map).len();
636 debug!("The AST map has {} entries with a maximum of {}: occupancy {:.1}%",
637 entries, vector_length, (entries as f64 / vector_length as f64) * 100.);
643 /// Used for items loaded from external crate that are being inlined into this
644 /// crate. The `path` should be the path to the item but should not include
646 pub fn map_decoded_item<F: FoldOps>(map: &Map,
647 path: Vec<PathElem> ,
649 fold: |&mut Ctx<F>| -> InlinedItem)
653 parent: DUMMY_NODE_ID,
657 // Generate a NodeId for the RootInlinedParent inserted below.
658 cx.new_id(DUMMY_NODE_ID);
660 // Methods get added to the AST map when their impl is visited. Since we
661 // don't decode and instantiate the impl, but just the method, we have to
662 // add it to the table now. Likewise with foreign items.
663 let mut def_id = DefId { krate: LOCAL_CRATE, node: DUMMY_NODE_ID };
664 let ii = fold(&mut cx);
667 IIMethod(impl_did, is_provided, m) => {
668 let entry = if is_provided {
669 EntryTraitMethod(cx.parent, box(GC) Provided(m))
671 EntryMethod(cx.parent, m)
673 cx.insert(m.id, entry);
677 cx.insert(i.id, EntryForeignItem(cx.parent, i));
681 cx.insert(cx.parent, RootInlinedParent(P(InlinedParent {
689 fn node_id_to_string(map: &Map, id: NodeId) -> String {
691 Some(NodeItem(item)) => {
692 let path_str = map.path_to_str_with_ident(id, item.ident);
693 let item_str = match item.node {
694 ItemStatic(..) => "static",
696 ItemMod(..) => "mod",
697 ItemForeignMod(..) => "foreign mod",
699 ItemEnum(..) => "enum",
700 ItemStruct(..) => "struct",
701 ItemTrait(..) => "trait",
702 ItemImpl(..) => "impl",
703 ItemMac(..) => "macro"
705 format!("{} {} (id={})", item_str, path_str, id)
707 Some(NodeForeignItem(item)) => {
708 let path_str = map.path_to_str_with_ident(id, item.ident);
709 format!("foreign item {} (id={})", path_str, id)
711 Some(NodeMethod(m)) => match m.node {
712 MethDecl(ident, _, _, _, _, _, _) =>
713 format!("method {} in {} (id={})",
714 token::get_ident(ident),
715 map.path_to_string(id), id),
717 format!("method macro {} (id={})",
718 pprust::mac_to_string(mac), id)
720 Some(NodeTraitMethod(ref tm)) => {
721 let m = ast_util::trait_method_to_ty_method(&**tm);
722 format!("method {} in {} (id={})",
723 token::get_ident(m.ident),
724 map.path_to_string(id), id)
726 Some(NodeVariant(ref variant)) => {
727 format!("variant {} in {} (id={})",
728 token::get_ident(variant.node.name),
729 map.path_to_string(id), id)
731 Some(NodeExpr(ref expr)) => {
732 format!("expr {} (id={})", pprust::expr_to_string(&**expr), id)
734 Some(NodeStmt(ref stmt)) => {
735 format!("stmt {} (id={})", pprust::stmt_to_string(&**stmt), id)
737 Some(NodeArg(ref pat)) => {
738 format!("arg {} (id={})", pprust::pat_to_string(&**pat), id)
740 Some(NodeLocal(ref pat)) => {
741 format!("local {} (id={})", pprust::pat_to_string(&**pat), id)
743 Some(NodePat(ref pat)) => {
744 format!("pat {} (id={})", pprust::pat_to_string(&**pat), id)
746 Some(NodeBlock(ref block)) => {
747 format!("block {} (id={})", pprust::block_to_string(&**block), id)
749 Some(NodeStructCtor(_)) => {
750 format!("struct_ctor {} (id={})", map.path_to_string(id), id)
752 Some(NodeLifetime(ref l)) => {
753 format!("lifetime {} (id={})",
754 pprust::lifetime_to_string(&**l), id)
757 format!("unknown node (id={})", id)