]> git.proxmox.com Git - rustc.git/blob - src/librustc/hir/map/mod.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc / hir / map / mod.rs
1 // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 pub use self::Node::*;
12 use self::MapEntry::*;
13 use self::collector::NodeCollector;
14 pub use self::definitions::{Definitions, DefKey, DefPath, DefPathData,
15 DisambiguatedDefPathData, InlinedRootPath};
16
17 use dep_graph::{DepGraph, DepNode};
18
19 use middle::cstore::InlinedItem;
20 use middle::cstore::InlinedItem as II;
21 use hir::def_id::{CRATE_DEF_INDEX, DefId};
22
23 use syntax::abi::Abi;
24 use syntax::ast::{self, Name, NodeId, DUMMY_NODE_ID};
25 use syntax::attr::ThinAttributesExt;
26 use syntax::codemap::{Span, Spanned};
27
28 use hir::*;
29 use hir::fold::Folder;
30 use hir::print as pprust;
31
32 use arena::TypedArena;
33 use std::cell::RefCell;
34 use std::io;
35 use std::mem;
36
37 pub mod blocks;
38 mod collector;
39 pub mod definitions;
40
41 #[derive(Copy, Clone, Debug)]
42 pub enum Node<'ast> {
43 NodeItem(&'ast Item),
44 NodeForeignItem(&'ast ForeignItem),
45 NodeTraitItem(&'ast TraitItem),
46 NodeImplItem(&'ast ImplItem),
47 NodeVariant(&'ast Variant),
48 NodeExpr(&'ast Expr),
49 NodeStmt(&'ast Stmt),
50 NodeLocal(&'ast Pat),
51 NodePat(&'ast Pat),
52 NodeBlock(&'ast Block),
53
54 /// NodeStructCtor represents a tuple struct.
55 NodeStructCtor(&'ast VariantData),
56
57 NodeLifetime(&'ast Lifetime),
58 NodeTyParam(&'ast TyParam)
59 }
60
61 /// Represents an entry and its parent NodeID.
62 /// The odd layout is to bring down the total size.
63 #[derive(Copy, Debug)]
64 pub enum MapEntry<'ast> {
65 /// Placeholder for holes in the map.
66 NotPresent,
67
68 /// All the node types, with a parent ID.
69 EntryItem(NodeId, &'ast Item),
70 EntryForeignItem(NodeId, &'ast ForeignItem),
71 EntryTraitItem(NodeId, &'ast TraitItem),
72 EntryImplItem(NodeId, &'ast ImplItem),
73 EntryVariant(NodeId, &'ast Variant),
74 EntryExpr(NodeId, &'ast Expr),
75 EntryStmt(NodeId, &'ast Stmt),
76 EntryLocal(NodeId, &'ast Pat),
77 EntryPat(NodeId, &'ast Pat),
78 EntryBlock(NodeId, &'ast Block),
79 EntryStructCtor(NodeId, &'ast VariantData),
80 EntryLifetime(NodeId, &'ast Lifetime),
81 EntryTyParam(NodeId, &'ast TyParam),
82
83 /// Roots for node trees.
84 RootCrate,
85 RootInlinedParent(&'ast InlinedItem)
86 }
87
88 impl<'ast> Clone for MapEntry<'ast> {
89 fn clone(&self) -> MapEntry<'ast> {
90 *self
91 }
92 }
93
94 impl<'ast> MapEntry<'ast> {
95 fn from_node(p: NodeId, node: Node<'ast>) -> MapEntry<'ast> {
96 match node {
97 NodeItem(n) => EntryItem(p, n),
98 NodeForeignItem(n) => EntryForeignItem(p, n),
99 NodeTraitItem(n) => EntryTraitItem(p, n),
100 NodeImplItem(n) => EntryImplItem(p, n),
101 NodeVariant(n) => EntryVariant(p, n),
102 NodeExpr(n) => EntryExpr(p, n),
103 NodeStmt(n) => EntryStmt(p, n),
104 NodeLocal(n) => EntryLocal(p, n),
105 NodePat(n) => EntryPat(p, n),
106 NodeBlock(n) => EntryBlock(p, n),
107 NodeStructCtor(n) => EntryStructCtor(p, n),
108 NodeLifetime(n) => EntryLifetime(p, n),
109 NodeTyParam(n) => EntryTyParam(p, n),
110 }
111 }
112
113 fn parent_node(self) -> Option<NodeId> {
114 Some(match self {
115 EntryItem(id, _) => id,
116 EntryForeignItem(id, _) => id,
117 EntryTraitItem(id, _) => id,
118 EntryImplItem(id, _) => id,
119 EntryVariant(id, _) => id,
120 EntryExpr(id, _) => id,
121 EntryStmt(id, _) => id,
122 EntryLocal(id, _) => id,
123 EntryPat(id, _) => id,
124 EntryBlock(id, _) => id,
125 EntryStructCtor(id, _) => id,
126 EntryLifetime(id, _) => id,
127 EntryTyParam(id, _) => id,
128 _ => return None
129 })
130 }
131
132 fn to_node(self) -> Option<Node<'ast>> {
133 Some(match self {
134 EntryItem(_, n) => NodeItem(n),
135 EntryForeignItem(_, n) => NodeForeignItem(n),
136 EntryTraitItem(_, n) => NodeTraitItem(n),
137 EntryImplItem(_, n) => NodeImplItem(n),
138 EntryVariant(_, n) => NodeVariant(n),
139 EntryExpr(_, n) => NodeExpr(n),
140 EntryStmt(_, n) => NodeStmt(n),
141 EntryLocal(_, n) => NodeLocal(n),
142 EntryPat(_, n) => NodePat(n),
143 EntryBlock(_, n) => NodeBlock(n),
144 EntryStructCtor(_, n) => NodeStructCtor(n),
145 EntryLifetime(_, n) => NodeLifetime(n),
146 EntryTyParam(_, n) => NodeTyParam(n),
147 _ => return None
148 })
149 }
150 }
151
152 /// Stores a crate and any number of inlined items from other crates.
153 pub struct Forest {
154 krate: Crate,
155 pub dep_graph: DepGraph,
156 inlined_items: TypedArena<InlinedItem>
157 }
158
159 impl Forest {
160 pub fn new(krate: Crate, dep_graph: DepGraph) -> Forest {
161 Forest {
162 krate: krate,
163 dep_graph: dep_graph,
164 inlined_items: TypedArena::new()
165 }
166 }
167
168 pub fn krate<'ast>(&'ast self) -> &'ast Crate {
169 self.dep_graph.read(DepNode::Krate);
170 &self.krate
171 }
172 }
173
174 /// Represents a mapping from Node IDs to AST elements and their parent
175 /// Node IDs
176 #[derive(Clone)]
177 pub struct Map<'ast> {
178 /// The backing storage for all the AST nodes.
179 pub forest: &'ast Forest,
180
181 /// Same as the dep_graph in forest, just available with one fewer
182 /// deref. This is a gratuitious micro-optimization.
183 pub dep_graph: DepGraph,
184
185 /// NodeIds are sequential integers from 0, so we can be
186 /// super-compact by storing them in a vector. Not everything with
187 /// a NodeId is in the map, but empirically the occupancy is about
188 /// 75-80%, so there's not too much overhead (certainly less than
189 /// a hashmap, since they (at the time of writing) have a maximum
190 /// of 75% occupancy).
191 ///
192 /// Also, indexing is pretty quick when you've got a vector and
193 /// plain old integers.
194 map: RefCell<Vec<MapEntry<'ast>>>,
195
196 definitions: RefCell<Definitions>,
197 }
198
199 impl<'ast> Map<'ast> {
200 /// Registers a read in the dependency graph of the AST node with
201 /// the given `id`. This needs to be called each time a public
202 /// function returns the HIR for a node -- in other words, when it
203 /// "reveals" the content of a node to the caller (who might not
204 /// otherwise have had access to those contents, and hence needs a
205 /// read recorded). If the function just returns a DefId or
206 /// NodeId, no actual content was returned, so no read is needed.
207 fn read(&self, id: NodeId) {
208 self.dep_graph.read(self.dep_node(id));
209 }
210
211 fn dep_node(&self, id0: NodeId) -> DepNode<DefId> {
212 let map = self.map.borrow();
213 let mut id = id0;
214 loop {
215 match map[id as usize] {
216 EntryItem(_, item) => {
217 let def_id = self.local_def_id(item.id);
218 // NB ^~~~~~~
219 //
220 // You would expect that `item.id == id`, but this
221 // is not always the case. In particular, for a
222 // ViewPath item like `use self::{mem, foo}`, we
223 // map the ids for `mem` and `foo` to the
224 // enclosing view path item. This seems mega super
225 // ultra wrong, but then who am I to judge?
226 // -nmatsakis
227 return DepNode::Hir(def_id);
228 }
229
230 EntryForeignItem(p, _) |
231 EntryTraitItem(p, _) |
232 EntryImplItem(p, _) |
233 EntryVariant(p, _) |
234 EntryExpr(p, _) |
235 EntryStmt(p, _) |
236 EntryLocal(p, _) |
237 EntryPat(p, _) |
238 EntryBlock(p, _) |
239 EntryStructCtor(p, _) |
240 EntryLifetime(p, _) |
241 EntryTyParam(p, _) =>
242 id = p,
243
244 RootCrate |
245 RootInlinedParent(_) =>
246 // FIXME(#32015) clarify story about cross-crate dep tracking
247 return DepNode::Krate,
248
249 NotPresent =>
250 // Some nodes, notably struct fields, are not
251 // present in the map for whatever reason, but
252 // they *do* have def-ids. So if we encounter an
253 // empty hole, check for that case.
254 return self.opt_local_def_id(id)
255 .map(|def_id| DepNode::Hir(def_id))
256 .unwrap_or_else(|| {
257 bug!("Walking parents from `{}` \
258 led to `NotPresent` at `{}`",
259 id0, id)
260 }),
261 }
262 }
263 }
264
265 pub fn num_local_def_ids(&self) -> usize {
266 self.definitions.borrow().len()
267 }
268
269 pub fn def_key(&self, def_id: DefId) -> DefKey {
270 assert!(def_id.is_local());
271 self.definitions.borrow().def_key(def_id.index)
272 }
273
274 pub fn def_path_from_id(&self, id: NodeId) -> Option<DefPath> {
275 self.opt_local_def_id(id).map(|def_id| {
276 self.def_path(def_id)
277 })
278 }
279
280 pub fn def_path(&self, def_id: DefId) -> DefPath {
281 assert!(def_id.is_local());
282 self.definitions.borrow().def_path(def_id.index)
283 }
284
285 pub fn retrace_path(&self, path: &DefPath) -> Option<DefId> {
286 self.definitions.borrow().retrace_path(path)
287 .map(DefId::local)
288 }
289
290 pub fn local_def_id(&self, node: NodeId) -> DefId {
291 self.opt_local_def_id(node).unwrap_or_else(|| {
292 bug!("local_def_id: no entry for `{}`, which has a map of `{:?}`",
293 node, self.find_entry(node))
294 })
295 }
296
297 pub fn opt_local_def_id(&self, node: NodeId) -> Option<DefId> {
298 self.definitions.borrow().opt_local_def_id(node)
299 }
300
301 pub fn as_local_node_id(&self, def_id: DefId) -> Option<NodeId> {
302 self.definitions.borrow().as_local_node_id(def_id)
303 }
304
305 fn entry_count(&self) -> usize {
306 self.map.borrow().len()
307 }
308
309 fn find_entry(&self, id: NodeId) -> Option<MapEntry<'ast>> {
310 self.map.borrow().get(id as usize).cloned()
311 }
312
313 pub fn krate(&self) -> &'ast Crate {
314 self.forest.krate()
315 }
316
317 /// Get the attributes on the krate. This is preferable to
318 /// invoking `krate.attrs` because it registers a tighter
319 /// dep-graph access.
320 pub fn krate_attrs(&self) -> &'ast [ast::Attribute] {
321 let crate_root_def_id = DefId::local(CRATE_DEF_INDEX);
322 self.dep_graph.read(DepNode::Hir(crate_root_def_id));
323 &self.forest.krate.attrs
324 }
325
326 /// Retrieve the Node corresponding to `id`, panicking if it cannot
327 /// be found.
328 pub fn get(&self, id: NodeId) -> Node<'ast> {
329 match self.find(id) {
330 Some(node) => node, // read recorded by `find`
331 None => bug!("couldn't find node id {} in the AST map", id)
332 }
333 }
334
335 pub fn get_if_local(&self, id: DefId) -> Option<Node<'ast>> {
336 self.as_local_node_id(id).map(|id| self.get(id)) // read recorded by `get`
337 }
338
339 /// Retrieve the Node corresponding to `id`, returning None if
340 /// cannot be found.
341 pub fn find(&self, id: NodeId) -> Option<Node<'ast>> {
342 let result = self.find_entry(id).and_then(|x| x.to_node());
343 if result.is_some() {
344 self.read(id);
345 }
346 result
347 }
348
349 /// Similar to get_parent, returns the parent node id or id if there is no
350 /// parent.
351 /// This function returns the immediate parent in the AST, whereas get_parent
352 /// returns the enclosing item. Note that this might not be the actual parent
353 /// node in the AST - some kinds of nodes are not in the map and these will
354 /// never appear as the parent_node. So you can always walk the parent_nodes
355 /// from a node to the root of the ast (unless you get the same id back here
356 /// that can happen if the id is not in the map itself or is just weird).
357 pub fn get_parent_node(&self, id: NodeId) -> NodeId {
358 self.find_entry(id).and_then(|x| x.parent_node()).unwrap_or(id)
359 }
360
361 /// Check if the node is an argument. An argument is a local variable whose
362 /// immediate parent is an item or a closure.
363 pub fn is_argument(&self, id: NodeId) -> bool {
364 match self.find(id) {
365 Some(NodeLocal(_)) => (),
366 _ => return false,
367 }
368 match self.find(self.get_parent_node(id)) {
369 Some(NodeItem(_)) |
370 Some(NodeTraitItem(_)) |
371 Some(NodeImplItem(_)) => true,
372 Some(NodeExpr(e)) => {
373 match e.node {
374 ExprClosure(..) => true,
375 _ => false,
376 }
377 }
378 _ => false,
379 }
380 }
381
382 /// If there is some error when walking the parents (e.g., a node does not
383 /// have a parent in the map or a node can't be found), then we return the
384 /// last good node id we found. Note that reaching the crate root (id == 0),
385 /// is not an error, since items in the crate module have the crate root as
386 /// parent.
387 fn walk_parent_nodes<F>(&self, start_id: NodeId, found: F) -> Result<NodeId, NodeId>
388 where F: Fn(&Node<'ast>) -> bool
389 {
390 let mut id = start_id;
391 loop {
392 let parent_node = self.get_parent_node(id);
393 if parent_node == 0 {
394 return Ok(0);
395 }
396 if parent_node == id {
397 return Err(id);
398 }
399
400 let node = self.find_entry(parent_node);
401 if node.is_none() {
402 return Err(id);
403 }
404 let node = node.unwrap().to_node();
405 match node {
406 Some(ref node) => {
407 if found(node) {
408 return Ok(parent_node);
409 }
410 }
411 None => {
412 return Err(parent_node);
413 }
414 }
415 id = parent_node;
416 }
417 }
418
419 /// Retrieve the NodeId for `id`'s parent item, or `id` itself if no
420 /// parent item is in this map. The "parent item" is the closest parent node
421 /// in the AST which is recorded by the map and is an item, either an item
422 /// in a module, trait, or impl.
423 pub fn get_parent(&self, id: NodeId) -> NodeId {
424 match self.walk_parent_nodes(id, |node| match *node {
425 NodeItem(_) |
426 NodeForeignItem(_) |
427 NodeTraitItem(_) |
428 NodeImplItem(_) => true,
429 _ => false,
430 }) {
431 Ok(id) => id,
432 Err(id) => id,
433 }
434 }
435
436 /// Returns the NodeId of `id`'s nearest module parent, or `id` itself if no
437 /// module parent is in this map.
438 pub fn get_module_parent(&self, id: NodeId) -> NodeId {
439 match self.walk_parent_nodes(id, |node| match *node {
440 NodeItem(&Item { node: Item_::ItemMod(_), .. }) => true,
441 _ => false,
442 }) {
443 Ok(id) => id,
444 Err(id) => id,
445 }
446 }
447
448 /// Returns the nearest enclosing scope. A scope is an item or block.
449 /// FIXME it is not clear to me that all items qualify as scopes - statics
450 /// and associated types probably shouldn't, for example. Behaviour in this
451 /// regard should be expected to be highly unstable.
452 pub fn get_enclosing_scope(&self, id: NodeId) -> Option<NodeId> {
453 match self.walk_parent_nodes(id, |node| match *node {
454 NodeItem(_) |
455 NodeForeignItem(_) |
456 NodeTraitItem(_) |
457 NodeImplItem(_) |
458 NodeBlock(_) => true,
459 _ => false,
460 }) {
461 Ok(id) => Some(id),
462 Err(_) => None,
463 }
464 }
465
466 pub fn get_parent_did(&self, id: NodeId) -> DefId {
467 let parent = self.get_parent(id);
468 match self.find_entry(parent) {
469 Some(RootInlinedParent(&II::TraitItem(did, _))) |
470 Some(RootInlinedParent(&II::ImplItem(did, _))) => did,
471 _ => self.local_def_id(parent)
472 }
473 }
474
475 pub fn get_foreign_abi(&self, id: NodeId) -> Abi {
476 let parent = self.get_parent(id);
477 let abi = match self.find_entry(parent) {
478 Some(EntryItem(_, i)) => {
479 match i.node {
480 ItemForeignMod(ref nm) => Some(nm.abi),
481 _ => None
482 }
483 }
484 /// Wrong but OK, because the only inlined foreign items are intrinsics.
485 Some(RootInlinedParent(_)) => Some(Abi::RustIntrinsic),
486 _ => None
487 };
488 match abi {
489 Some(abi) => {
490 self.read(id); // reveals some of the content of a node
491 abi
492 }
493 None => bug!("expected foreign mod or inlined parent, found {}",
494 self.node_to_string(parent))
495 }
496 }
497
498 pub fn expect_item(&self, id: NodeId) -> &'ast Item {
499 match self.find(id) { // read recorded by `find`
500 Some(NodeItem(item)) => item,
501 _ => bug!("expected item, found {}", self.node_to_string(id))
502 }
503 }
504
505 pub fn expect_trait_item(&self, id: NodeId) -> &'ast TraitItem {
506 match self.find(id) {
507 Some(NodeTraitItem(item)) => item,
508 _ => bug!("expected trait item, found {}", self.node_to_string(id))
509 }
510 }
511
512 pub fn expect_struct(&self, id: NodeId) -> &'ast VariantData {
513 match self.find(id) {
514 Some(NodeItem(i)) => {
515 match i.node {
516 ItemStruct(ref struct_def, _) => struct_def,
517 _ => bug!("struct ID bound to non-struct")
518 }
519 }
520 Some(NodeVariant(variant)) => {
521 if variant.node.data.is_struct() {
522 &variant.node.data
523 } else {
524 bug!("struct ID bound to enum variant that isn't struct-like")
525 }
526 }
527 _ => bug!("expected struct, found {}", self.node_to_string(id)),
528 }
529 }
530
531 pub fn expect_variant(&self, id: NodeId) -> &'ast Variant {
532 match self.find(id) {
533 Some(NodeVariant(variant)) => variant,
534 _ => bug!("expected variant, found {}", self.node_to_string(id)),
535 }
536 }
537
538 pub fn expect_foreign_item(&self, id: NodeId) -> &'ast ForeignItem {
539 match self.find(id) {
540 Some(NodeForeignItem(item)) => item,
541 _ => bug!("expected foreign item, found {}", self.node_to_string(id))
542 }
543 }
544
545 pub fn expect_expr(&self, id: NodeId) -> &'ast Expr {
546 match self.find(id) { // read recorded by find
547 Some(NodeExpr(expr)) => expr,
548 _ => bug!("expected expr, found {}", self.node_to_string(id))
549 }
550 }
551
552 /// Returns the name associated with the given NodeId's AST.
553 pub fn name(&self, id: NodeId) -> Name {
554 match self.get(id) {
555 NodeItem(i) => i.name,
556 NodeForeignItem(i) => i.name,
557 NodeImplItem(ii) => ii.name,
558 NodeTraitItem(ti) => ti.name,
559 NodeVariant(v) => v.node.name,
560 NodeLifetime(lt) => lt.name,
561 NodeTyParam(tp) => tp.name,
562 NodeLocal(&Pat { node: PatKind::Ident(_,l,_), .. }) => {
563 l.node.name
564 },
565 NodeStructCtor(_) => self.name(self.get_parent(id)),
566 _ => bug!("no name for {}", self.node_to_string(id))
567 }
568 }
569
570 /// Given a node ID, get a list of attributes associated with the AST
571 /// corresponding to the Node ID
572 pub fn attrs(&self, id: NodeId) -> &'ast [ast::Attribute] {
573 self.read(id); // reveals attributes on the node
574 let attrs = match self.find(id) {
575 Some(NodeItem(i)) => Some(&i.attrs[..]),
576 Some(NodeForeignItem(fi)) => Some(&fi.attrs[..]),
577 Some(NodeTraitItem(ref ti)) => Some(&ti.attrs[..]),
578 Some(NodeImplItem(ref ii)) => Some(&ii.attrs[..]),
579 Some(NodeVariant(ref v)) => Some(&v.node.attrs[..]),
580 Some(NodeExpr(ref e)) => Some(e.attrs.as_attr_slice()),
581 Some(NodeStmt(ref s)) => Some(s.node.attrs()),
582 // unit/tuple structs take the attributes straight from
583 // the struct definition.
584 Some(NodeStructCtor(_)) => {
585 return self.attrs(self.get_parent(id));
586 }
587 _ => None
588 };
589 attrs.unwrap_or(&[])
590 }
591
592 /// Returns an iterator that yields the node id's with paths that
593 /// match `parts`. (Requires `parts` is non-empty.)
594 ///
595 /// For example, if given `parts` equal to `["bar", "quux"]`, then
596 /// the iterator will produce node id's for items with paths
597 /// such as `foo::bar::quux`, `bar::quux`, `other::bar::quux`, and
598 /// any other such items it can find in the map.
599 pub fn nodes_matching_suffix<'a>(&'a self, parts: &'a [String])
600 -> NodesMatchingSuffix<'a, 'ast> {
601 NodesMatchingSuffix {
602 map: self,
603 item_name: parts.last().unwrap(),
604 in_which: &parts[..parts.len() - 1],
605 idx: 0,
606 }
607 }
608
609 pub fn opt_span(&self, id: NodeId) -> Option<Span> {
610 let sp = match self.find(id) {
611 Some(NodeItem(item)) => item.span,
612 Some(NodeForeignItem(foreign_item)) => foreign_item.span,
613 Some(NodeTraitItem(trait_method)) => trait_method.span,
614 Some(NodeImplItem(ref impl_item)) => impl_item.span,
615 Some(NodeVariant(variant)) => variant.span,
616 Some(NodeExpr(expr)) => expr.span,
617 Some(NodeStmt(stmt)) => stmt.span,
618 Some(NodeLocal(pat)) => pat.span,
619 Some(NodePat(pat)) => pat.span,
620 Some(NodeBlock(block)) => block.span,
621 Some(NodeStructCtor(_)) => self.expect_item(self.get_parent(id)).span,
622 Some(NodeTyParam(ty_param)) => ty_param.span,
623 _ => return None,
624 };
625 Some(sp)
626 }
627
628 pub fn span(&self, id: NodeId) -> Span {
629 self.read(id); // reveals span from node
630 self.opt_span(id)
631 .unwrap_or_else(|| bug!("AstMap.span: could not find span for id {:?}", id))
632 }
633
634 pub fn span_if_local(&self, id: DefId) -> Option<Span> {
635 self.as_local_node_id(id).map(|id| self.span(id))
636 }
637
638 pub fn def_id_span(&self, def_id: DefId, fallback: Span) -> Span {
639 if let Some(node_id) = self.as_local_node_id(def_id) {
640 self.opt_span(node_id).unwrap_or(fallback)
641 } else {
642 fallback
643 }
644 }
645
646 pub fn node_to_string(&self, id: NodeId) -> String {
647 node_id_to_string(self, id, true)
648 }
649
650 pub fn node_to_user_string(&self, id: NodeId) -> String {
651 node_id_to_string(self, id, false)
652 }
653 }
654
655 pub struct NodesMatchingSuffix<'a, 'ast:'a> {
656 map: &'a Map<'ast>,
657 item_name: &'a String,
658 in_which: &'a [String],
659 idx: NodeId,
660 }
661
662 impl<'a, 'ast> NodesMatchingSuffix<'a, 'ast> {
663 /// Returns true only if some suffix of the module path for parent
664 /// matches `self.in_which`.
665 ///
666 /// In other words: let `[x_0,x_1,...,x_k]` be `self.in_which`;
667 /// returns true if parent's path ends with the suffix
668 /// `x_0::x_1::...::x_k`.
669 fn suffix_matches(&self, parent: NodeId) -> bool {
670 let mut cursor = parent;
671 for part in self.in_which.iter().rev() {
672 let (mod_id, mod_name) = match find_first_mod_parent(self.map, cursor) {
673 None => return false,
674 Some((node_id, name)) => (node_id, name),
675 };
676 if &part[..] != mod_name.as_str() {
677 return false;
678 }
679 cursor = self.map.get_parent(mod_id);
680 }
681 return true;
682
683 // Finds the first mod in parent chain for `id`, along with
684 // that mod's name.
685 //
686 // If `id` itself is a mod named `m` with parent `p`, then
687 // returns `Some(id, m, p)`. If `id` has no mod in its parent
688 // chain, then returns `None`.
689 fn find_first_mod_parent<'a>(map: &'a Map, mut id: NodeId) -> Option<(NodeId, Name)> {
690 loop {
691 match map.find(id) {
692 None => return None,
693 Some(NodeItem(item)) if item_is_mod(&item) =>
694 return Some((id, item.name)),
695 _ => {}
696 }
697 let parent = map.get_parent(id);
698 if parent == id { return None }
699 id = parent;
700 }
701
702 fn item_is_mod(item: &Item) -> bool {
703 match item.node {
704 ItemMod(_) => true,
705 _ => false,
706 }
707 }
708 }
709 }
710
711 // We are looking at some node `n` with a given name and parent
712 // id; do their names match what I am seeking?
713 fn matches_names(&self, parent_of_n: NodeId, name: Name) -> bool {
714 name.as_str() == &self.item_name[..] &&
715 self.suffix_matches(parent_of_n)
716 }
717 }
718
719 impl<'a, 'ast> Iterator for NodesMatchingSuffix<'a, 'ast> {
720 type Item = NodeId;
721
722 fn next(&mut self) -> Option<NodeId> {
723 loop {
724 let idx = self.idx;
725 if idx as usize >= self.map.entry_count() {
726 return None;
727 }
728 self.idx += 1;
729 let name = match self.map.find_entry(idx) {
730 Some(EntryItem(_, n)) => n.name(),
731 Some(EntryForeignItem(_, n))=> n.name(),
732 Some(EntryTraitItem(_, n)) => n.name(),
733 Some(EntryImplItem(_, n)) => n.name(),
734 Some(EntryVariant(_, n)) => n.name(),
735 _ => continue,
736 };
737 if self.matches_names(self.map.get_parent(idx), name) {
738 return Some(idx)
739 }
740 }
741 }
742 }
743
744 trait Named {
745 fn name(&self) -> Name;
746 }
747
748 impl<T:Named> Named for Spanned<T> { fn name(&self) -> Name { self.node.name() } }
749
750 impl Named for Item { fn name(&self) -> Name { self.name } }
751 impl Named for ForeignItem { fn name(&self) -> Name { self.name } }
752 impl Named for Variant_ { fn name(&self) -> Name { self.name } }
753 impl Named for TraitItem { fn name(&self) -> Name { self.name } }
754 impl Named for ImplItem { fn name(&self) -> Name { self.name } }
755
756 pub trait FoldOps {
757 fn new_id(&self, id: NodeId) -> NodeId {
758 id
759 }
760 fn new_def_id(&self, def_id: DefId) -> DefId {
761 def_id
762 }
763 fn new_span(&self, span: Span) -> Span {
764 span
765 }
766 }
767
768 /// A Folder that updates IDs and Span's according to fold_ops.
769 struct IdAndSpanUpdater<F> {
770 fold_ops: F
771 }
772
773 impl<F: FoldOps> Folder for IdAndSpanUpdater<F> {
774 fn new_id(&mut self, id: NodeId) -> NodeId {
775 self.fold_ops.new_id(id)
776 }
777
778 fn new_span(&mut self, span: Span) -> Span {
779 self.fold_ops.new_span(span)
780 }
781 }
782
783 pub fn map_crate<'ast>(forest: &'ast mut Forest) -> Map<'ast> {
784 let (map, definitions) = {
785 let mut collector = NodeCollector::root(&forest.krate);
786 intravisit::walk_crate(&mut collector, &forest.krate);
787 (collector.map, collector.definitions)
788 };
789
790 if log_enabled!(::log::DEBUG) {
791 // This only makes sense for ordered stores; note the
792 // enumerate to count the number of entries.
793 let (entries_less_1, _) = map.iter().filter(|&x| {
794 match *x {
795 NotPresent => false,
796 _ => true
797 }
798 }).enumerate().last().expect("AST map was empty after folding?");
799
800 let entries = entries_less_1 + 1;
801 let vector_length = map.len();
802 debug!("The AST map has {} entries with a maximum of {}: occupancy {:.1}%",
803 entries, vector_length, (entries as f64 / vector_length as f64) * 100.);
804 }
805
806 Map {
807 forest: forest,
808 dep_graph: forest.dep_graph.clone(),
809 map: RefCell::new(map),
810 definitions: RefCell::new(definitions),
811 }
812 }
813
814 /// Used for items loaded from external crate that are being inlined into this
815 /// crate.
816 pub fn map_decoded_item<'ast, F: FoldOps>(map: &Map<'ast>,
817 parent_def_path: DefPath,
818 parent_def_id: DefId,
819 ii: InlinedItem,
820 fold_ops: F)
821 -> &'ast InlinedItem {
822 let mut fld = IdAndSpanUpdater { fold_ops: fold_ops };
823 let ii = match ii {
824 II::Item(i) => II::Item(i.map(|i| fld.fold_item(i))),
825 II::TraitItem(d, ti) => {
826 II::TraitItem(fld.fold_ops.new_def_id(d),
827 ti.map(|ti| fld.fold_trait_item(ti)))
828 }
829 II::ImplItem(d, ii) => {
830 II::ImplItem(fld.fold_ops.new_def_id(d),
831 ii.map(|ii| fld.fold_impl_item(ii)))
832 }
833 II::Foreign(i) => II::Foreign(i.map(|i| fld.fold_foreign_item(i)))
834 };
835
836 let ii = map.forest.inlined_items.alloc(ii);
837
838 let ii_parent_id = fld.new_id(DUMMY_NODE_ID);
839 let mut collector =
840 NodeCollector::extend(
841 map.krate(),
842 ii,
843 ii_parent_id,
844 parent_def_path,
845 parent_def_id,
846 mem::replace(&mut *map.map.borrow_mut(), vec![]),
847 mem::replace(&mut *map.definitions.borrow_mut(), Definitions::new()));
848 ii.visit(&mut collector);
849
850 *map.map.borrow_mut() = collector.map;
851 *map.definitions.borrow_mut() = collector.definitions;
852
853 ii
854 }
855
856 pub trait NodePrinter {
857 fn print_node(&mut self, node: &Node) -> io::Result<()>;
858 }
859
860 impl<'a> NodePrinter for pprust::State<'a> {
861 fn print_node(&mut self, node: &Node) -> io::Result<()> {
862 match *node {
863 NodeItem(a) => self.print_item(&a),
864 NodeForeignItem(a) => self.print_foreign_item(&a),
865 NodeTraitItem(a) => self.print_trait_item(a),
866 NodeImplItem(a) => self.print_impl_item(a),
867 NodeVariant(a) => self.print_variant(&a),
868 NodeExpr(a) => self.print_expr(&a),
869 NodeStmt(a) => self.print_stmt(&a),
870 NodePat(a) => self.print_pat(&a),
871 NodeBlock(a) => self.print_block(&a),
872 NodeLifetime(a) => self.print_lifetime(&a),
873 NodeTyParam(_) => bug!("cannot print TyParam"),
874 // these cases do not carry enough information in the
875 // ast_map to reconstruct their full structure for pretty
876 // printing.
877 NodeLocal(_) => bug!("cannot print isolated Local"),
878 NodeStructCtor(_) => bug!("cannot print isolated StructCtor"),
879 }
880 }
881 }
882
883 fn node_id_to_string(map: &Map, id: NodeId, include_id: bool) -> String {
884 let id_str = format!(" (id={})", id);
885 let id_str = if include_id { &id_str[..] } else { "" };
886
887 let path_str = || {
888 // This functionality is used for debugging, try to use TyCtxt to get
889 // the user-friendly path, otherwise fall back to stringifying DefPath.
890 ::ty::tls::with_opt(|tcx| {
891 if let Some(tcx) = tcx {
892 tcx.node_path_str(id)
893 } else if let Some(path) = map.def_path_from_id(id) {
894 path.data.into_iter().map(|elem| {
895 elem.data.to_string()
896 }).collect::<Vec<_>>().join("::")
897 } else {
898 String::from("<missing path>")
899 }
900 })
901 };
902
903 match map.find(id) {
904 Some(NodeItem(item)) => {
905 let item_str = match item.node {
906 ItemExternCrate(..) => "extern crate",
907 ItemUse(..) => "use",
908 ItemStatic(..) => "static",
909 ItemConst(..) => "const",
910 ItemFn(..) => "fn",
911 ItemMod(..) => "mod",
912 ItemForeignMod(..) => "foreign mod",
913 ItemTy(..) => "ty",
914 ItemEnum(..) => "enum",
915 ItemStruct(..) => "struct",
916 ItemTrait(..) => "trait",
917 ItemImpl(..) => "impl",
918 ItemDefaultImpl(..) => "default impl",
919 };
920 format!("{} {}{}", item_str, path_str(), id_str)
921 }
922 Some(NodeForeignItem(_)) => {
923 format!("foreign item {}{}", path_str(), id_str)
924 }
925 Some(NodeImplItem(ii)) => {
926 match ii.node {
927 ImplItemKind::Const(..) => {
928 format!("assoc const {} in {}{}", ii.name, path_str(), id_str)
929 }
930 ImplItemKind::Method(..) => {
931 format!("method {} in {}{}", ii.name, path_str(), id_str)
932 }
933 ImplItemKind::Type(_) => {
934 format!("assoc type {} in {}{}", ii.name, path_str(), id_str)
935 }
936 }
937 }
938 Some(NodeTraitItem(ti)) => {
939 let kind = match ti.node {
940 ConstTraitItem(..) => "assoc constant",
941 MethodTraitItem(..) => "trait method",
942 TypeTraitItem(..) => "assoc type",
943 };
944
945 format!("{} {} in {}{}", kind, ti.name, path_str(), id_str)
946 }
947 Some(NodeVariant(ref variant)) => {
948 format!("variant {} in {}{}",
949 variant.node.name,
950 path_str(), id_str)
951 }
952 Some(NodeExpr(ref expr)) => {
953 format!("expr {}{}", pprust::expr_to_string(&expr), id_str)
954 }
955 Some(NodeStmt(ref stmt)) => {
956 format!("stmt {}{}", pprust::stmt_to_string(&stmt), id_str)
957 }
958 Some(NodeLocal(ref pat)) => {
959 format!("local {}{}", pprust::pat_to_string(&pat), id_str)
960 }
961 Some(NodePat(ref pat)) => {
962 format!("pat {}{}", pprust::pat_to_string(&pat), id_str)
963 }
964 Some(NodeBlock(ref block)) => {
965 format!("block {}{}", pprust::block_to_string(&block), id_str)
966 }
967 Some(NodeStructCtor(_)) => {
968 format!("struct_ctor {}{}", path_str(), id_str)
969 }
970 Some(NodeLifetime(ref l)) => {
971 format!("lifetime {}{}",
972 pprust::lifetime_to_string(&l), id_str)
973 }
974 Some(NodeTyParam(ref ty_param)) => {
975 format!("typaram {:?}{}", ty_param, id_str)
976 }
977 None => {
978 format!("unknown node{}", id_str)
979 }
980 }
981 }