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