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