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.
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.
11 pub use self::Node
::*;
12 pub use self::PathElem
::*;
13 use self::MapEntry
::*;
14 use self::collector
::NodeCollector
;
15 pub use self::definitions
::{Definitions, DefKey, DefPath, DefPathData, DisambiguatedDefPathData}
;
17 use dep_graph
::{DepGraph, DepNode}
;
19 use middle
::cstore
::InlinedItem
;
20 use middle
::cstore
::InlinedItem
as II
;
21 use middle
::def_id
::DefId
;
24 use syntax
::ast
::{self, Name, NodeId, DUMMY_NODE_ID}
;
25 use syntax
::codemap
::{Span, Spanned}
;
26 use syntax
::parse
::token
;
28 use rustc_front
::hir
::*;
29 use rustc_front
::fold
::Folder
;
30 use rustc_front
::intravisit
;
31 use rustc_front
::print
::pprust
;
33 use arena
::TypedArena
;
34 use std
::cell
::RefCell
;
45 #[derive(Clone, Copy, PartialEq, Debug)]
52 pub fn name(&self) -> Name
{
54 PathMod(name
) | PathName(name
) => name
59 impl fmt
::Display
for PathElem
{
60 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
61 write
!(f
, "{}", self.name())
66 pub struct LinkedPathNode
<'a
> {
71 #[derive(Copy, Clone)]
72 pub struct LinkedPath
<'a
>(Option
<&'a LinkedPathNode
<'a
>>);
74 impl<'a
> LinkedPath
<'a
> {
75 pub fn empty() -> LinkedPath
<'a
> {
79 pub fn from(node
: &'a LinkedPathNode
) -> LinkedPath
<'a
> {
80 LinkedPath(Some(node
))
84 impl<'a
> Iterator
for LinkedPath
<'a
> {
87 fn next(&mut self) -> Option
<PathElem
> {
98 /// The type of the iterator used by with_path.
99 pub type PathElems
<'a
, 'b
> = iter
::Chain
<iter
::Cloned
<slice
::Iter
<'a
, PathElem
>>, LinkedPath
<'b
>>;
101 pub fn path_to_string
<PI
: Iterator
<Item
=PathElem
>>(path
: PI
) -> String
{
102 let itr
= token
::get_ident_interner();
104 path
.fold(String
::new(), |mut s
, e
| {
105 let e
= itr
.get(e
.name());
114 #[derive(Copy, Clone, Debug)]
115 pub enum Node
<'ast
> {
116 NodeItem(&'ast Item
),
117 NodeForeignItem(&'ast ForeignItem
),
118 NodeTraitItem(&'ast TraitItem
),
119 NodeImplItem(&'ast ImplItem
),
120 NodeVariant(&'ast Variant
),
121 NodeExpr(&'ast Expr
),
122 NodeStmt(&'ast Stmt
),
123 NodeLocal(&'ast Pat
),
125 NodeBlock(&'ast Block
),
127 /// NodeStructCtor represents a tuple struct.
128 NodeStructCtor(&'ast VariantData
),
130 NodeLifetime(&'ast Lifetime
),
131 NodeTyParam(&'ast TyParam
)
134 /// Represents an entry and its parent NodeID.
135 /// The odd layout is to bring down the total size.
136 #[derive(Copy, Debug)]
137 pub enum MapEntry
<'ast
> {
138 /// Placeholder for holes in the map.
141 /// All the node types, with a parent ID.
142 EntryItem(NodeId
, &'ast Item
),
143 EntryForeignItem(NodeId
, &'ast ForeignItem
),
144 EntryTraitItem(NodeId
, &'ast TraitItem
),
145 EntryImplItem(NodeId
, &'ast ImplItem
),
146 EntryVariant(NodeId
, &'ast Variant
),
147 EntryExpr(NodeId
, &'ast Expr
),
148 EntryStmt(NodeId
, &'ast Stmt
),
149 EntryLocal(NodeId
, &'ast Pat
),
150 EntryPat(NodeId
, &'ast Pat
),
151 EntryBlock(NodeId
, &'ast Block
),
152 EntryStructCtor(NodeId
, &'ast VariantData
),
153 EntryLifetime(NodeId
, &'ast Lifetime
),
154 EntryTyParam(NodeId
, &'ast TyParam
),
156 /// Roots for node trees.
158 RootInlinedParent(&'ast InlinedParent
)
161 impl<'ast
> Clone
for MapEntry
<'ast
> {
162 fn clone(&self) -> MapEntry
<'ast
> {
168 pub struct InlinedParent
{
173 impl<'ast
> MapEntry
<'ast
> {
174 fn from_node(p
: NodeId
, node
: Node
<'ast
>) -> MapEntry
<'ast
> {
176 NodeItem(n
) => EntryItem(p
, n
),
177 NodeForeignItem(n
) => EntryForeignItem(p
, n
),
178 NodeTraitItem(n
) => EntryTraitItem(p
, n
),
179 NodeImplItem(n
) => EntryImplItem(p
, n
),
180 NodeVariant(n
) => EntryVariant(p
, n
),
181 NodeExpr(n
) => EntryExpr(p
, n
),
182 NodeStmt(n
) => EntryStmt(p
, n
),
183 NodeLocal(n
) => EntryLocal(p
, n
),
184 NodePat(n
) => EntryPat(p
, n
),
185 NodeBlock(n
) => EntryBlock(p
, n
),
186 NodeStructCtor(n
) => EntryStructCtor(p
, n
),
187 NodeLifetime(n
) => EntryLifetime(p
, n
),
188 NodeTyParam(n
) => EntryTyParam(p
, n
),
192 fn parent_node(self) -> Option
<NodeId
> {
194 EntryItem(id
, _
) => id
,
195 EntryForeignItem(id
, _
) => id
,
196 EntryTraitItem(id
, _
) => id
,
197 EntryImplItem(id
, _
) => id
,
198 EntryVariant(id
, _
) => id
,
199 EntryExpr(id
, _
) => id
,
200 EntryStmt(id
, _
) => id
,
201 EntryLocal(id
, _
) => id
,
202 EntryPat(id
, _
) => id
,
203 EntryBlock(id
, _
) => id
,
204 EntryStructCtor(id
, _
) => id
,
205 EntryLifetime(id
, _
) => id
,
206 EntryTyParam(id
, _
) => id
,
211 fn to_node(self) -> Option
<Node
<'ast
>> {
213 EntryItem(_
, n
) => NodeItem(n
),
214 EntryForeignItem(_
, n
) => NodeForeignItem(n
),
215 EntryTraitItem(_
, n
) => NodeTraitItem(n
),
216 EntryImplItem(_
, n
) => NodeImplItem(n
),
217 EntryVariant(_
, n
) => NodeVariant(n
),
218 EntryExpr(_
, n
) => NodeExpr(n
),
219 EntryStmt(_
, n
) => NodeStmt(n
),
220 EntryLocal(_
, n
) => NodeLocal(n
),
221 EntryPat(_
, n
) => NodePat(n
),
222 EntryBlock(_
, n
) => NodeBlock(n
),
223 EntryStructCtor(_
, n
) => NodeStructCtor(n
),
224 EntryLifetime(_
, n
) => NodeLifetime(n
),
225 EntryTyParam(_
, n
) => NodeTyParam(n
),
231 /// Stores a crate and any number of inlined items from other crates.
234 pub dep_graph
: DepGraph
,
235 inlined_items
: TypedArena
<InlinedParent
>
239 pub fn new(krate
: Crate
, dep_graph
: DepGraph
) -> Forest
{
242 dep_graph
: dep_graph
,
243 inlined_items
: TypedArena
::new()
247 pub fn krate
<'ast
>(&'ast
self) -> &'ast Crate
{
248 self.dep_graph
.read(DepNode
::Krate
);
253 /// Represents a mapping from Node IDs to AST elements and their parent
256 pub struct Map
<'ast
> {
257 /// The backing storage for all the AST nodes.
258 pub forest
: &'ast Forest
,
260 /// Same as the dep_graph in forest, just available with one fewer
261 /// deref. This is a gratuitious micro-optimization.
262 pub dep_graph
: DepGraph
,
264 /// NodeIds are sequential integers from 0, so we can be
265 /// super-compact by storing them in a vector. Not everything with
266 /// a NodeId is in the map, but empirically the occupancy is about
267 /// 75-80%, so there's not too much overhead (certainly less than
268 /// a hashmap, since they (at the time of writing) have a maximum
269 /// of 75% occupancy).
271 /// Also, indexing is pretty quick when you've got a vector and
272 /// plain old integers.
273 map
: RefCell
<Vec
<MapEntry
<'ast
>>>,
275 definitions
: RefCell
<Definitions
>,
278 impl<'ast
> Map
<'ast
> {
279 /// Registers a read in the dependency graph of the AST node with
280 /// the given `id`. This needs to be called each time a public
281 /// function returns the HIR for a node -- in other words, when it
282 /// "reveals" the content of a node to the caller (who might not
283 /// otherwise have had access to those contents, and hence needs a
284 /// read recorded). If the function just returns a DefId or
285 /// NodeId, no actual content was returned, so no read is needed.
286 fn read(&self, id
: NodeId
) {
287 self.dep_graph
.read(self.dep_node(id
));
290 fn dep_node(&self, id0
: NodeId
) -> DepNode
{
291 let map
= self.map
.borrow();
294 match map
[id
as usize] {
295 EntryItem(_
, item
) => {
296 let def_id
= self.local_def_id(item
.id
);
299 // You would expect that `item.id == id`, but this
300 // is not always the case. In particular, for a
301 // ViewPath item like `use self::{mem, foo}`, we
302 // map the ids for `mem` and `foo` to the
303 // enclosing view path item. This seems mega super
304 // ultra wrong, but then who am I to judge?
306 return DepNode
::Hir(def_id
);
309 EntryForeignItem(p
, _
) |
310 EntryTraitItem(p
, _
) |
311 EntryImplItem(p
, _
) |
318 EntryStructCtor(p
, _
) |
319 EntryLifetime(p
, _
) |
320 EntryTyParam(p
, _
) =>
324 RootInlinedParent(_
) => // FIXME(#2369) clarify story about cross-crate dep tracking
325 return DepNode
::Krate
,
328 // Some nodes, notably struct fields, are not
329 // present in the map for whatever reason, but
330 // they *do* have def-ids. So if we encounter an
331 // empty hole, check for that case.
332 return self.opt_local_def_id(id
)
333 .map(|def_id
| DepNode
::Hir(def_id
))
335 panic
!("Walking parents from `{}` \
336 led to `NotPresent` at `{}`",
343 pub fn num_local_def_ids(&self) -> usize {
344 self.definitions
.borrow().len()
347 pub fn def_key(&self, def_id
: DefId
) -> DefKey
{
348 assert
!(def_id
.is_local());
349 self.definitions
.borrow().def_key(def_id
.index
)
352 pub fn def_path_from_id(&self, id
: NodeId
) -> DefPath
{
353 self.def_path(self.local_def_id(id
))
356 pub fn def_path(&self, def_id
: DefId
) -> DefPath
{
357 assert
!(def_id
.is_local());
358 self.definitions
.borrow().def_path(def_id
.index
)
361 pub fn local_def_id(&self, node
: NodeId
) -> DefId
{
362 self.opt_local_def_id(node
).unwrap_or_else(|| {
363 panic
!("local_def_id: no entry for `{}`, which has a map of `{:?}`",
364 node
, self.find_entry(node
))
368 pub fn opt_local_def_id(&self, node
: NodeId
) -> Option
<DefId
> {
369 self.definitions
.borrow().opt_local_def_id(node
)
372 pub fn as_local_node_id(&self, def_id
: DefId
) -> Option
<NodeId
> {
373 self.definitions
.borrow().as_local_node_id(def_id
)
376 fn entry_count(&self) -> usize {
377 self.map
.borrow().len()
380 fn find_entry(&self, id
: NodeId
) -> Option
<MapEntry
<'ast
>> {
381 self.map
.borrow().get(id
as usize).cloned()
384 pub fn krate(&self) -> &'ast Crate
{
388 /// Retrieve the Node corresponding to `id`, panicking if it cannot
390 pub fn get(&self, id
: NodeId
) -> Node
<'ast
> {
391 match self.find(id
) {
392 Some(node
) => node
, // read recorded by `find`
393 None
=> panic
!("couldn't find node id {} in the AST map", id
)
397 pub fn get_if_local(&self, id
: DefId
) -> Option
<Node
<'ast
>> {
398 self.as_local_node_id(id
).map(|id
| self.get(id
)) // read recorded by `get`
401 /// Retrieve the Node corresponding to `id`, returning None if
403 pub fn find(&self, id
: NodeId
) -> Option
<Node
<'ast
>> {
404 let result
= self.find_entry(id
).and_then(|x
| x
.to_node());
405 if result
.is_some() {
411 /// Similar to get_parent, returns the parent node id or id if there is no
413 /// This function returns the immediate parent in the AST, whereas get_parent
414 /// returns the enclosing item. Note that this might not be the actual parent
415 /// node in the AST - some kinds of nodes are not in the map and these will
416 /// never appear as the parent_node. So you can always walk the parent_nodes
417 /// from a node to the root of the ast (unless you get the same id back here
418 /// that can happen if the id is not in the map itself or is just weird).
419 pub fn get_parent_node(&self, id
: NodeId
) -> NodeId
{
420 self.find_entry(id
).and_then(|x
| x
.parent_node()).unwrap_or(id
)
423 /// Check if the node is an argument. An argument is a local variable whose
424 /// immediate parent is an item or a closure.
425 pub fn is_argument(&self, id
: NodeId
) -> bool
{
426 match self.find(id
) {
427 Some(NodeLocal(_
)) => (),
430 match self.find(self.get_parent_node(id
)) {
432 Some(NodeTraitItem(_
)) |
433 Some(NodeImplItem(_
)) => true,
434 Some(NodeExpr(e
)) => {
436 ExprClosure(..) => true,
444 /// If there is some error when walking the parents (e.g., a node does not
445 /// have a parent in the map or a node can't be found), then we return the
446 /// last good node id we found. Note that reaching the crate root (id == 0),
447 /// is not an error, since items in the crate module have the crate root as
449 fn walk_parent_nodes
<F
>(&self, start_id
: NodeId
, found
: F
) -> Result
<NodeId
, NodeId
>
450 where F
: Fn(&Node
<'ast
>) -> bool
452 let mut id
= start_id
;
454 let parent_node
= self.get_parent_node(id
);
455 if parent_node
== 0 {
458 if parent_node
== id
{
462 let node
= self.find_entry(parent_node
);
466 let node
= node
.unwrap().to_node();
470 return Ok(parent_node
);
474 return Err(parent_node
);
481 /// Retrieve the NodeId for `id`'s parent item, or `id` itself if no
482 /// parent item is in this map. The "parent item" is the closest parent node
483 /// in the AST which is recorded by the map and is an item, either an item
484 /// in a module, trait, or impl.
485 pub fn get_parent(&self, id
: NodeId
) -> NodeId
{
486 match self.walk_parent_nodes(id
, |node
| match *node
{
490 NodeImplItem(_
) => true,
498 /// Returns the nearest enclosing scope. A scope is an item or block.
499 /// FIXME it is not clear to me that all items qualify as scopes - statics
500 /// and associated types probably shouldn't, for example. Behaviour in this
501 /// regard should be expected to be highly unstable.
502 pub fn get_enclosing_scope(&self, id
: NodeId
) -> Option
<NodeId
> {
503 match self.walk_parent_nodes(id
, |node
| match *node
{
508 NodeBlock(_
) => true,
516 pub fn get_parent_did(&self, id
: NodeId
) -> DefId
{
517 let parent
= self.get_parent(id
);
518 match self.find_entry(parent
) {
519 Some(RootInlinedParent(&InlinedParent {ii: II::TraitItem(did, _), ..}
)) => did
,
520 Some(RootInlinedParent(&InlinedParent {ii: II::ImplItem(did, _), ..}
)) => did
,
521 _
=> self.local_def_id(parent
)
525 pub fn get_foreign_abi(&self, id
: NodeId
) -> Abi
{
526 let parent
= self.get_parent(id
);
527 let abi
= match self.find_entry(parent
) {
528 Some(EntryItem(_
, i
)) => {
530 ItemForeignMod(ref nm
) => Some(nm
.abi
),
534 /// Wrong but OK, because the only inlined foreign items are intrinsics.
535 Some(RootInlinedParent(_
)) => Some(Abi
::RustIntrinsic
),
540 self.read(id
); // reveals some of the content of a node
543 None
=> panic
!("expected foreign mod or inlined parent, found {}",
544 self.node_to_string(parent
))
548 pub fn get_foreign_vis(&self, id
: NodeId
) -> Visibility
{
549 let vis
= self.expect_foreign_item(id
).vis
; // read recorded by `expect_foreign_item`
550 match self.find(self.get_parent(id
)) { // read recorded by `find`
551 Some(NodeItem(i
)) => vis
.inherit_from(i
.vis
),
556 pub fn expect_item(&self, id
: NodeId
) -> &'ast Item
{
557 match self.find(id
) { // read recorded by `find`
558 Some(NodeItem(item
)) => item
,
559 _
=> panic
!("expected item, found {}", self.node_to_string(id
))
563 pub fn expect_trait_item(&self, id
: NodeId
) -> &'ast TraitItem
{
564 match self.find(id
) {
565 Some(NodeTraitItem(item
)) => item
,
566 _
=> panic
!("expected trait item, found {}", self.node_to_string(id
))
570 pub fn expect_struct(&self, id
: NodeId
) -> &'ast VariantData
{
571 match self.find(id
) {
572 Some(NodeItem(i
)) => {
574 ItemStruct(ref struct_def
, _
) => struct_def
,
575 _
=> panic
!("struct ID bound to non-struct")
578 Some(NodeVariant(variant
)) => {
579 if variant
.node
.data
.is_struct() {
582 panic
!("struct ID bound to enum variant that isn't struct-like")
585 _
=> panic
!(format
!("expected struct, found {}", self.node_to_string(id
))),
589 pub fn expect_variant(&self, id
: NodeId
) -> &'ast Variant
{
590 match self.find(id
) {
591 Some(NodeVariant(variant
)) => variant
,
592 _
=> panic
!(format
!("expected variant, found {}", self.node_to_string(id
))),
596 pub fn expect_foreign_item(&self, id
: NodeId
) -> &'ast ForeignItem
{
597 match self.find(id
) {
598 Some(NodeForeignItem(item
)) => item
,
599 _
=> panic
!("expected foreign item, found {}", self.node_to_string(id
))
603 pub fn expect_expr(&self, id
: NodeId
) -> &'ast Expr
{
604 match self.find(id
) { // read recorded by find
605 Some(NodeExpr(expr
)) => expr
,
606 _
=> panic
!("expected expr, found {}", self.node_to_string(id
))
610 /// returns the name associated with the given NodeId's AST
611 pub fn get_path_elem(&self, id
: NodeId
) -> PathElem
{
612 let node
= self.get(id
);
616 ItemMod(_
) | ItemForeignMod(_
) => {
619 _
=> PathName(item
.name
)
622 NodeForeignItem(i
) => PathName(i
.name
),
623 NodeImplItem(ii
) => PathName(ii
.name
),
624 NodeTraitItem(ti
) => PathName(ti
.name
),
625 NodeVariant(v
) => PathName(v
.node
.name
),
626 NodeLifetime(lt
) => PathName(lt
.name
),
627 NodeTyParam(tp
) => PathName(tp
.name
),
628 NodeLocal(&Pat { node: PatKind::Ident(_,l,_), .. }
) => {
629 PathName(l
.node
.name
)
631 _
=> panic
!("no path elem for {:?}", node
)
635 pub fn with_path
<T
, F
>(&self, id
: NodeId
, f
: F
) -> T
where
636 F
: FnOnce(PathElems
) -> T
,
638 self.with_path_next(id
, LinkedPath
::empty(), f
)
641 pub fn path_to_string(&self, id
: NodeId
) -> String
{
642 self.with_path(id
, |path
| path_to_string(path
))
645 fn path_to_str_with_name(&self, id
: NodeId
, name
: Name
) -> String
{
646 self.with_path(id
, |path
| {
647 path_to_string(path
.chain(Some(PathName(name
))))
651 fn with_path_next
<T
, F
>(&self, id
: NodeId
, next
: LinkedPath
, f
: F
) -> T
where
652 F
: FnOnce(PathElems
) -> T
,
654 // This function reveals the name of the item and hence is a
655 // kind of read. This is inefficient, since it walks ancestors
656 // and we are walking them anyhow, but whatever.
659 let parent
= self.get_parent(id
);
660 let parent
= match self.find_entry(id
) {
661 Some(EntryForeignItem(..)) => {
662 // Anonymous extern items go in the parent scope.
663 self.get_parent(parent
)
665 // But tuple struct ctors don't have names, so use the path of its
666 // parent, the struct item. Similarly with closure expressions.
667 Some(EntryStructCtor(..)) | Some(EntryExpr(..)) => {
668 return self.with_path_next(parent
, next
, f
);
673 match self.find_entry(id
) {
674 Some(RootInlinedParent(data
)) => {
675 f(data
.path
.iter().cloned().chain(next
))
677 _
=> f([].iter().cloned().chain(next
))
680 self.with_path_next(parent
, LinkedPath
::from(&LinkedPathNode
{
681 node
: self.get_path_elem(id
),
687 /// Given a node ID, get a list of attributes associated with the AST
688 /// corresponding to the Node ID
689 pub fn attrs(&self, id
: NodeId
) -> &'ast
[ast
::Attribute
] {
690 self.read(id
); // reveals attributes on the node
691 let attrs
= match self.find(id
) {
692 Some(NodeItem(i
)) => Some(&i
.attrs
[..]),
693 Some(NodeForeignItem(fi
)) => Some(&fi
.attrs
[..]),
694 Some(NodeTraitItem(ref ti
)) => Some(&ti
.attrs
[..]),
695 Some(NodeImplItem(ref ii
)) => Some(&ii
.attrs
[..]),
696 Some(NodeVariant(ref v
)) => Some(&v
.node
.attrs
[..]),
697 // unit/tuple structs take the attributes straight from
698 // the struct definition.
699 Some(NodeStructCtor(_
)) => {
700 return self.attrs(self.get_parent(id
));
707 /// Returns an iterator that yields the node id's with paths that
708 /// match `parts`. (Requires `parts` is non-empty.)
710 /// For example, if given `parts` equal to `["bar", "quux"]`, then
711 /// the iterator will produce node id's for items with paths
712 /// such as `foo::bar::quux`, `bar::quux`, `other::bar::quux`, and
713 /// any other such items it can find in the map.
714 pub fn nodes_matching_suffix
<'a
>(&'a
self, parts
: &'a
[String
])
715 -> NodesMatchingSuffix
<'a
, 'ast
> {
716 NodesMatchingSuffix
{
718 item_name
: parts
.last().unwrap(),
719 in_which
: &parts
[..parts
.len() - 1],
724 pub fn opt_span(&self, id
: NodeId
) -> Option
<Span
> {
725 let sp
= match self.find(id
) {
726 Some(NodeItem(item
)) => item
.span
,
727 Some(NodeForeignItem(foreign_item
)) => foreign_item
.span
,
728 Some(NodeTraitItem(trait_method
)) => trait_method
.span
,
729 Some(NodeImplItem(ref impl_item
)) => impl_item
.span
,
730 Some(NodeVariant(variant
)) => variant
.span
,
731 Some(NodeExpr(expr
)) => expr
.span
,
732 Some(NodeStmt(stmt
)) => stmt
.span
,
733 Some(NodeLocal(pat
)) => pat
.span
,
734 Some(NodePat(pat
)) => pat
.span
,
735 Some(NodeBlock(block
)) => block
.span
,
736 Some(NodeStructCtor(_
)) => self.expect_item(self.get_parent(id
)).span
,
737 Some(NodeTyParam(ty_param
)) => ty_param
.span
,
743 pub fn span(&self, id
: NodeId
) -> Span
{
744 self.read(id
); // reveals span from node
746 .unwrap_or_else(|| panic
!("AstMap.span: could not find span for id {:?}", id
))
749 pub fn span_if_local(&self, id
: DefId
) -> Option
<Span
> {
750 self.as_local_node_id(id
).map(|id
| self.span(id
))
753 pub fn def_id_span(&self, def_id
: DefId
, fallback
: Span
) -> Span
{
754 if let Some(node_id
) = self.as_local_node_id(def_id
) {
755 self.opt_span(node_id
).unwrap_or(fallback
)
761 pub fn node_to_string(&self, id
: NodeId
) -> String
{
762 node_id_to_string(self, id
, true)
765 pub fn node_to_user_string(&self, id
: NodeId
) -> String
{
766 node_id_to_string(self, id
, false)
770 pub struct NodesMatchingSuffix
<'a
, 'ast
:'a
> {
772 item_name
: &'a String
,
773 in_which
: &'a
[String
],
777 impl<'a
, 'ast
> NodesMatchingSuffix
<'a
, 'ast
> {
778 /// Returns true only if some suffix of the module path for parent
779 /// matches `self.in_which`.
781 /// In other words: let `[x_0,x_1,...,x_k]` be `self.in_which`;
782 /// returns true if parent's path ends with the suffix
783 /// `x_0::x_1::...::x_k`.
784 fn suffix_matches(&self, parent
: NodeId
) -> bool
{
785 let mut cursor
= parent
;
786 for part
in self.in_which
.iter().rev() {
787 let (mod_id
, mod_name
) = match find_first_mod_parent(self.map
, cursor
) {
788 None
=> return false,
789 Some((node_id
, name
)) => (node_id
, name
),
791 if &part
[..] != mod_name
.as_str() {
794 cursor
= self.map
.get_parent(mod_id
);
798 // Finds the first mod in parent chain for `id`, along with
801 // If `id` itself is a mod named `m` with parent `p`, then
802 // returns `Some(id, m, p)`. If `id` has no mod in its parent
803 // chain, then returns `None`.
804 fn find_first_mod_parent
<'a
>(map
: &'a Map
, mut id
: NodeId
) -> Option
<(NodeId
, Name
)> {
808 Some(NodeItem(item
)) if item_is_mod(&item
) =>
809 return Some((id
, item
.name
)),
812 let parent
= map
.get_parent(id
);
813 if parent
== id { return None }
817 fn item_is_mod(item
: &Item
) -> bool
{
826 // We are looking at some node `n` with a given name and parent
827 // id; do their names match what I am seeking?
828 fn matches_names(&self, parent_of_n
: NodeId
, name
: Name
) -> bool
{
829 name
.as_str() == &self.item_name
[..] &&
830 self.suffix_matches(parent_of_n
)
834 impl<'a
, 'ast
> Iterator
for NodesMatchingSuffix
<'a
, 'ast
> {
837 fn next(&mut self) -> Option
<NodeId
> {
840 if idx
as usize >= self.map
.entry_count() {
844 let name
= match self.map
.find_entry(idx
) {
845 Some(EntryItem(_
, n
)) => n
.name(),
846 Some(EntryForeignItem(_
, n
))=> n
.name(),
847 Some(EntryTraitItem(_
, n
)) => n
.name(),
848 Some(EntryImplItem(_
, n
)) => n
.name(),
849 Some(EntryVariant(_
, n
)) => n
.name(),
852 if self.matches_names(self.map
.get_parent(idx
), name
) {
860 fn name(&self) -> Name
;
863 impl<T
:Named
> Named
for Spanned
<T
> { fn name(&self) -> Name { self.node.name() }
}
865 impl Named
for Item { fn name(&self) -> Name { self.name }
}
866 impl Named
for ForeignItem { fn name(&self) -> Name { self.name }
}
867 impl Named
for Variant_ { fn name(&self) -> Name { self.name }
}
868 impl Named
for TraitItem { fn name(&self) -> Name { self.name }
}
869 impl Named
for ImplItem { fn name(&self) -> Name { self.name }
}
872 fn new_id(&self, id
: NodeId
) -> NodeId
{
875 fn new_def_id(&self, def_id
: DefId
) -> DefId
{
878 fn new_span(&self, span
: Span
) -> Span
{
883 /// A Folder that updates IDs and Span's according to fold_ops.
884 struct IdAndSpanUpdater
<F
> {
888 impl<F
: FoldOps
> Folder
for IdAndSpanUpdater
<F
> {
889 fn new_id(&mut self, id
: NodeId
) -> NodeId
{
890 self.fold_ops
.new_id(id
)
893 fn new_span(&mut self, span
: Span
) -> Span
{
894 self.fold_ops
.new_span(span
)
898 pub fn map_crate
<'ast
>(forest
: &'ast
mut Forest
) -> Map
<'ast
> {
899 let (map
, definitions
) = {
900 let mut collector
= NodeCollector
::root(&forest
.krate
);
901 intravisit
::walk_crate(&mut collector
, &forest
.krate
);
902 (collector
.map
, collector
.definitions
)
905 if log_enabled
!(::log
::DEBUG
) {
906 // This only makes sense for ordered stores; note the
907 // enumerate to count the number of entries.
908 let (entries_less_1
, _
) = map
.iter().filter(|&x
| {
913 }).enumerate().last().expect("AST map was empty after folding?");
915 let entries
= entries_less_1
+ 1;
916 let vector_length
= map
.len();
917 debug
!("The AST map has {} entries with a maximum of {}: occupancy {:.1}%",
918 entries
, vector_length
, (entries
as f64 / vector_length
as f64) * 100.);
923 dep_graph
: forest
.dep_graph
.clone(),
924 map
: RefCell
::new(map
),
925 definitions
: RefCell
::new(definitions
),
929 /// Used for items loaded from external crate that are being inlined into this
931 pub fn map_decoded_item
<'ast
, F
: FoldOps
>(map
: &Map
<'ast
>,
932 parent_path
: Vec
<PathElem
>,
933 parent_def_path
: DefPath
,
936 -> &'ast InlinedItem
{
937 let mut fld
= IdAndSpanUpdater { fold_ops: fold_ops }
;
939 II
::Item(i
) => II
::Item(i
.map(|i
| fld
.fold_item(i
))),
940 II
::TraitItem(d
, ti
) => {
941 II
::TraitItem(fld
.fold_ops
.new_def_id(d
),
942 ti
.map(|ti
| fld
.fold_trait_item(ti
)))
944 II
::ImplItem(d
, ii
) => {
945 II
::ImplItem(fld
.fold_ops
.new_def_id(d
),
946 ii
.map(|ii
| fld
.fold_impl_item(ii
)))
948 II
::Foreign(i
) => II
::Foreign(i
.map(|i
| fld
.fold_foreign_item(i
)))
951 let ii_parent
= map
.forest
.inlined_items
.alloc(InlinedParent
{
956 let ii_parent_id
= fld
.new_id(DUMMY_NODE_ID
);
958 NodeCollector
::extend(
963 mem
::replace(&mut *map
.map
.borrow_mut(), vec
![]),
964 mem
::replace(&mut *map
.definitions
.borrow_mut(), Definitions
::new()));
965 ii_parent
.ii
.visit(&mut collector
);
967 *map
.map
.borrow_mut() = collector
.map
;
968 *map
.definitions
.borrow_mut() = collector
.definitions
;
973 pub trait NodePrinter
{
974 fn print_node(&mut self, node
: &Node
) -> io
::Result
<()>;
977 impl<'a
> NodePrinter
for pprust
::State
<'a
> {
978 fn print_node(&mut self, node
: &Node
) -> io
::Result
<()> {
980 NodeItem(a
) => self.print_item(&a
),
981 NodeForeignItem(a
) => self.print_foreign_item(&a
),
982 NodeTraitItem(a
) => self.print_trait_item(a
),
983 NodeImplItem(a
) => self.print_impl_item(a
),
984 NodeVariant(a
) => self.print_variant(&a
),
985 NodeExpr(a
) => self.print_expr(&a
),
986 NodeStmt(a
) => self.print_stmt(&a
),
987 NodePat(a
) => self.print_pat(&a
),
988 NodeBlock(a
) => self.print_block(&a
),
989 NodeLifetime(a
) => self.print_lifetime(&a
),
990 NodeTyParam(_
) => panic
!("cannot print TyParam"),
991 // these cases do not carry enough information in the
992 // ast_map to reconstruct their full structure for pretty
994 NodeLocal(_
) => panic
!("cannot print isolated Local"),
995 NodeStructCtor(_
) => panic
!("cannot print isolated StructCtor"),
1000 fn node_id_to_string(map
: &Map
, id
: NodeId
, include_id
: bool
) -> String
{
1001 let id_str
= format
!(" (id={})", id
);
1002 let id_str
= if include_id { &id_str[..] }
else { "" }
;
1004 match map
.find(id
) {
1005 Some(NodeItem(item
)) => {
1006 let path_str
= map
.path_to_str_with_name(id
, item
.name
);
1007 let item_str
= match item
.node
{
1008 ItemExternCrate(..) => "extern crate",
1009 ItemUse(..) => "use",
1010 ItemStatic(..) => "static",
1011 ItemConst(..) => "const",
1013 ItemMod(..) => "mod",
1014 ItemForeignMod(..) => "foreign mod",
1016 ItemEnum(..) => "enum",
1017 ItemStruct(..) => "struct",
1018 ItemTrait(..) => "trait",
1019 ItemImpl(..) => "impl",
1020 ItemDefaultImpl(..) => "default impl",
1022 format
!("{} {}{}", item_str
, path_str
, id_str
)
1024 Some(NodeForeignItem(item
)) => {
1025 let path_str
= map
.path_to_str_with_name(id
, item
.name
);
1026 format
!("foreign item {}{}", path_str
, id_str
)
1028 Some(NodeImplItem(ii
)) => {
1030 ImplItemKind
::Const(..) => {
1031 format
!("assoc const {} in {}{}",
1033 map
.path_to_string(id
),
1036 ImplItemKind
::Method(..) => {
1037 format
!("method {} in {}{}",
1039 map
.path_to_string(id
), id_str
)
1041 ImplItemKind
::Type(_
) => {
1042 format
!("assoc type {} in {}{}",
1044 map
.path_to_string(id
),
1049 Some(NodeTraitItem(ti
)) => {
1050 let kind
= match ti
.node
{
1051 ConstTraitItem(..) => "assoc constant",
1052 MethodTraitItem(..) => "trait method",
1053 TypeTraitItem(..) => "assoc type",
1056 format
!("{} {} in {}{}",
1059 map
.path_to_string(id
),
1062 Some(NodeVariant(ref variant
)) => {
1063 format
!("variant {} in {}{}",
1065 map
.path_to_string(id
), id_str
)
1067 Some(NodeExpr(ref expr
)) => {
1068 format
!("expr {}{}", pprust
::expr_to_string(&expr
), id_str
)
1070 Some(NodeStmt(ref stmt
)) => {
1071 format
!("stmt {}{}", pprust
::stmt_to_string(&stmt
), id_str
)
1073 Some(NodeLocal(ref pat
)) => {
1074 format
!("local {}{}", pprust
::pat_to_string(&pat
), id_str
)
1076 Some(NodePat(ref pat
)) => {
1077 format
!("pat {}{}", pprust
::pat_to_string(&pat
), id_str
)
1079 Some(NodeBlock(ref block
)) => {
1080 format
!("block {}{}", pprust
::block_to_string(&block
), id_str
)
1082 Some(NodeStructCtor(_
)) => {
1083 format
!("struct_ctor {}{}", map
.path_to_string(id
), id_str
)
1085 Some(NodeLifetime(ref l
)) => {
1086 format
!("lifetime {}{}",
1087 pprust
::lifetime_to_string(&l
), id_str
)
1089 Some(NodeTyParam(ref ty_param
)) => {
1090 format
!("typaram {:?}{}", ty_param
, id_str
)
1093 format
!("unknown node{}", id_str
)