src/libsyntax/ast_map.rs

   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 use abi::AbiSet;
  12 use ast::*;
  13 use ast;
  14 use ast_util;
  15 use codemap::Span;
  16 use diagnostic::SpanHandler;
  17 use fold::Folder;
  18 use fold;
  19 use parse::token::{get_ident_interner, IdentInterner};
  20 use print::pprust;
  21 use util::small_vector::SmallVector;
  22
  23 use std::logging;
  24 use std::cell::RefCell;
  25 use extra::smallintmap::SmallIntMap;
  26
  27 #[deriving(Clone, Eq)]
  28 pub enum PathElem {
  29     PathMod(Ident),
  30     PathName(Ident),
  31
  32     // A pretty name can come from an `impl` block. We attempt to select a
  33     // reasonable name for debuggers to see, but to guarantee uniqueness with
  34     // other paths the hash should also be taken into account during symbol
  35     // generation.
  36     PathPrettyName(Ident, u64),
  37 }
  38
  39 impl PathElem {
  40     pub fn ident(&self) -> Ident {
  41         match *self {
  42             PathMod(ident)            |
  43             PathName(ident)           |
  44             PathPrettyName(ident, _) => ident
  45         }
  46     }
  47 }
  48
  49 pub type Path = ~[PathElem];
  50
  51 pub fn path_to_str_with_sep(p: &[PathElem], sep: &str, itr: @IdentInterner)
  52                             -> ~str {
  53     let strs = p.map(|e| {
  54         match *e {
  55             PathMod(s) | PathName(s) | PathPrettyName(s, _) => {
  56                 itr.get(s.name)
  57             }
  58         }
  59     });
  60     strs.connect(sep)
  61 }
  62
  63 pub fn path_ident_to_str(p: &Path, i: Ident, itr: @IdentInterner) -> ~str {
  64     if p.is_empty() {
  65         itr.get(i.name).into_owned()
  66     } else {
  67         let string = itr.get(i.name);
  68         format!("{}::{}", path_to_str(*p, itr), string.as_slice())
  69     }
  70 }
  71
  72 pub fn path_to_str(p: &[PathElem], itr: @IdentInterner) -> ~str {
  73     path_to_str_with_sep(p, "::", itr)
  74 }
  75
  76 pub fn path_elem_to_str(pe: PathElem, itr: @IdentInterner) -> ~str {
  77     match pe {
  78         PathMod(s) | PathName(s) | PathPrettyName(s, _) => {
  79             itr.get(s.name).into_owned()
  80         }
  81     }
  82 }
  83
  84 /// write a "pretty" version of `ty` to `out`. This is designed so
  85 /// that symbols of `impl`'d methods give some hint of where they came
  86 /// from, even if it's hard to read (previously they would all just be
  87 /// listed as `__extensions__::method_name::hash`, with no indication
  88 /// of the type).
  89 // FIXME: these dollar signs and the names in general are actually a
  90 //      relic of $ being one of the very few valid symbol names on
  91 //      unix. These kinds of details shouldn't be exposed way up here
  92 //      in the ast.
  93 fn pretty_ty(ty: &Ty, itr: @IdentInterner, out: &mut ~str) {
  94     let (prefix, subty) = match ty.node {
  95         TyUniq(ty) => ("$UP$", &*ty),
  96         TyBox(ty) => ("$SP$", &*ty),
  97         TyPtr(MutTy { ty, mutbl }) => (if mutbl == MutMutable {"$RPmut$"} else {"$RP$"},
  98                                        &*ty),
  99         TyRptr(_, MutTy { ty, mutbl }) => (if mutbl == MutMutable {"$BPmut$"} else {"$BP$"},
 100                                            &*ty),
 101
 102         TyVec(ty) => ("$VEC$", &*ty),
 103         TyFixedLengthVec(ty, _) => ("$FIXEDVEC$", &*ty),
 104
 105         // these can't be represented as <prefix><contained ty>, so
 106         // need custom handling.
 107         TyNil => { out.push_str("$NIL$"); return }
 108         TyPath(ref path, _, _) => {
 109             out.push_str(itr.get(path.segments
 110                                      .last()
 111                                      .unwrap()
 112                                      .identifier
 113                                      .name).as_slice());
 114             return
 115         }
 116         TyTup(ref tys) => {
 117             out.push_str(format!("$TUP_{}$", tys.len()));
 118             for subty in tys.iter() {
 119                 pretty_ty(*subty, itr, out);
 120                 out.push_char('$');
 121             }
 122             return
 123         }
 124
 125         // meh, better than nothing.
 126         TyBot => { out.push_str("$BOT$"); return }
 127         TyClosure(..) => { out.push_str("$CLOSURE$"); return }
 128         TyBareFn(..) => { out.push_str("$FN$"); return }
 129         TyTypeof(..) => { out.push_str("$TYPEOF$"); return }
 130         TyInfer(..) => { out.push_str("$INFER$"); return }
 131
 132     };
 133
 134     out.push_str(prefix);
 135     pretty_ty(subty, itr, out);
 136 }
 137
 138 pub fn impl_pretty_name(trait_ref: &Option<TraitRef>, ty: &Ty) -> PathElem {
 139     let itr = get_ident_interner();
 140
 141     let hash = (trait_ref, ty).hash();
 142     let mut pretty;
 143     match *trait_ref {
 144         None => pretty = ~"",
 145         Some(ref trait_ref) => {
 146             pretty = itr.get(trait_ref.path.segments.last().unwrap().identifier.name)
 147                         .into_owned();
 148             pretty.push_char('$');
 149         }
 150     };
 151     pretty_ty(ty, itr, &mut pretty);
 152
 153     PathPrettyName(Ident::new(itr.gensym(pretty)), hash)
 154 }
 155
 156 #[deriving(Clone)]
 157 pub enum Node {
 158     NodeItem(@Item, @Path),
 159     NodeForeignItem(@ForeignItem, AbiSet, Visibility, @Path),
 160     NodeTraitMethod(@TraitMethod, DefId /* trait did */,
 161                     @Path /* path to the trait */),
 162     NodeMethod(@Method, DefId /* impl did */, @Path /* path to the impl */),
 163
 164     /// NodeVariant represents a variant of an enum, e.g., for
 165     /// `enum A { B, C, D }`, there would be a NodeItem for `A`, and a
 166     /// NodeVariant item for each of `B`, `C`, and `D`.
 167     NodeVariant(P<Variant>, @Item, @Path),
 168     NodeExpr(@Expr),
 169     NodeStmt(@Stmt),
 170     NodeArg(@Pat),
 171     NodeLocal(@Pat),
 172     NodeBlock(P<Block>),
 173
 174     /// NodeStructCtor represents a tuple struct.
 175     NodeStructCtor(@StructDef, @Item, @Path),
 176     NodeCalleeScope(@Expr)
 177 }
 178
 179 impl Node {
 180     pub fn with_attrs<T>(&self, f: |Option<&[Attribute]>| -> T) -> T {
 181         let attrs = match *self {
 182             NodeItem(i, _) => Some(i.attrs.as_slice()),
 183             NodeForeignItem(fi, _, _, _) => Some(fi.attrs.as_slice()),
 184             NodeTraitMethod(tm, _, _) => match *tm {
 185                 Required(ref type_m) => Some(type_m.attrs.as_slice()),
 186                 Provided(m) => Some(m.attrs.as_slice())
 187             },
 188             NodeMethod(m, _, _) => Some(m.attrs.as_slice()),
 189             NodeVariant(ref v, _, _) => Some(v.node.attrs.as_slice()),
 190             // unit/tuple structs take the attributes straight from
 191             // the struct definition.
 192             NodeStructCtor(_, strct, _) => Some(strct.attrs.as_slice()),
 193             _ => None
 194         };
 195         f(attrs)
 196     }
 197 }
 198
 199 pub struct Map {
 200     /// NodeIds are sequential integers from 0, so we can be
 201     /// super-compact by storing them in a vector. Not everything with
 202     /// a NodeId is in the map, but empirically the occupancy is about
 203     /// 75-80%, so there's not too much overhead (certainly less than
 204     /// a hashmap, since they (at the time of writing) have a maximum
 205     /// of 75% occupancy). (The additional overhead of the Option<>
 206     /// inside the SmallIntMap could be removed by adding an extra
 207     /// empty variant to Node and storing a vector here, but that was
 208     /// found to not make much difference.)
 209     ///
 210     /// Also, indexing is pretty quick when you've got a vector and
 211     /// plain old integers.
 212     priv map: @RefCell<SmallIntMap<Node>>
 213 }
 214
 215 impl Map {
 216     /// Retrieve the Node corresponding to `id`, failing if it cannot
 217     /// be found.
 218     pub fn get(&self, id: ast::NodeId) -> Node {
 219         let map = self.map.borrow();
 220         *map.get().get(&(id as uint))
 221     }
 222     /// Retrieve the Node corresponding to `id`, returning None if
 223     /// cannot be found.
 224     pub fn find(&self, id: ast::NodeId) -> Option<Node> {
 225         let map = self.map.borrow();
 226         map.get().find(&(id as uint)).map(|&n| n)
 227     }
 228 }
 229
 230 pub trait FoldOps {
 231     fn new_id(&self, id: ast::NodeId) -> ast::NodeId {
 232         id
 233     }
 234     fn new_span(&self, span: Span) -> Span {
 235         span
 236     }
 237 }
 238
 239 pub struct Ctx<F> {
 240     map: Map,
 241     path: Path,
 242     diag: @SpanHandler,
 243     fold_ops: F
 244 }
 245
 246 impl<F> Ctx<F> {
 247     fn insert(&self, id: ast::NodeId, node: Node) {
 248         let mut map = self.map.map.borrow_mut();
 249         map.get().insert(id as uint, node);
 250     }
 251 }
 252
 253 impl<F: FoldOps> Folder for Ctx<F> {
 254     fn new_id(&mut self, id: ast::NodeId) -> ast::NodeId {
 255         self.fold_ops.new_id(id)
 256     }
 257
 258     fn new_span(&mut self, span: Span) -> Span {
 259         self.fold_ops.new_span(span)
 260     }
 261
 262     fn fold_item(&mut self, i: @Item) -> SmallVector<@Item> {
 263         // clone is FIXME #2543
 264         let item_path = @self.path.clone();
 265         self.path.push(match i.node {
 266             ItemImpl(_, ref maybe_trait, ty, _) => {
 267                 // Right now the ident on impls is __extensions__ which isn't
 268                 // very pretty when debugging, so attempt to select a better
 269                 // name to use.
 270                 impl_pretty_name(maybe_trait, ty)
 271             }
 272             ItemMod(_) | ItemForeignMod(_) => PathMod(i.ident),
 273             _ => PathName(i.ident)
 274         });
 275
 276         let i = fold::noop_fold_item(i, self).expect_one("expected one item");
 277         self.insert(i.id, NodeItem(i, item_path));
 278
 279         match i.node {
 280             ItemImpl(_, _, _, ref ms) => {
 281                 // clone is FIXME #2543
 282                 let p = @self.path.clone();
 283                 let impl_did = ast_util::local_def(i.id);
 284                 for &m in ms.iter() {
 285                     self.insert(m.id, NodeMethod(m, impl_did, p));
 286                 }
 287
 288             }
 289             ItemEnum(ref enum_definition, _) => {
 290                 // clone is FIXME #2543
 291                 let p = @self.path.clone();
 292                 for &v in enum_definition.variants.iter() {
 293                     self.insert(v.node.id, NodeVariant(v, i, p));
 294                 }
 295             }
 296             ItemForeignMod(ref nm) => {
 297                 for nitem in nm.items.iter() {
 298                     // Compute the visibility for this native item.
 299                     let visibility = nitem.vis.inherit_from(i.vis);
 300
 301                     self.insert(nitem.id,
 302                                 // Anonymous extern mods go in the parent scope.
 303                                 NodeForeignItem(*nitem, nm.abis, visibility, item_path));
 304                 }
 305             }
 306             ItemStruct(struct_def, _) => {
 307                 // If this is a tuple-like struct, register the constructor.
 308                 match struct_def.ctor_id {
 309                     None => {}
 310                     Some(ctor_id) => {
 311                         // clone is FIXME #2543
 312                         let p = @self.path.clone();
 313                         self.insert(ctor_id, NodeStructCtor(struct_def, i, p));
 314                     }
 315                 }
 316             }
 317             ItemTrait(_, ref traits, ref methods) => {
 318                 for t in traits.iter() {
 319                     self.insert(t.ref_id, NodeItem(i, item_path));
 320                 }
 321
 322                 // clone is FIXME #2543
 323                 let p = @self.path.clone();
 324                 for tm in methods.iter() {
 325                     let d_id = ast_util::local_def(i.id);
 326                     match *tm {
 327                         Required(ref m) => {
 328                             self.insert(m.id, NodeTraitMethod(@(*tm).clone(), d_id, p));
 329                         }
 330                         Provided(m) => {
 331                             self.insert(m.id, NodeTraitMethod(@Provided(m), d_id, p));
 332                         }
 333                     }
 334                 }
 335             }
 336             _ => {}
 337         }
 338
 339         self.path.pop().unwrap();
 340
 341         SmallVector::one(i)
 342     }
 343
 344     fn fold_pat(&mut self, pat: @Pat) -> @Pat {
 345         let pat = fold::noop_fold_pat(pat, self);
 346         match pat.node {
 347             PatIdent(..) => {
 348                 // Note: this is at least *potentially* a pattern...
 349                 self.insert(pat.id, NodeLocal(pat));
 350             }
 351             _ => {}
 352         }
 353
 354         pat
 355     }
 356
 357     fn fold_expr(&mut self, expr: @Expr) -> @Expr {
 358         let expr = fold::noop_fold_expr(expr, self);
 359
 360         self.insert(expr.id, NodeExpr(expr));
 361
 362         // Expressions which are or might be calls:
 363         {
 364             let r = expr.get_callee_id();
 365             for callee_id in r.iter() {
 366                 self.insert(*callee_id, NodeCalleeScope(expr));
 367             }
 368         }
 369
 370         expr
 371     }
 372
 373     fn fold_stmt(&mut self, stmt: &Stmt) -> SmallVector<@Stmt> {
 374         let stmt = fold::noop_fold_stmt(stmt, self).expect_one("expected one statement");
 375         self.insert(ast_util::stmt_id(stmt), NodeStmt(stmt));
 376         SmallVector::one(stmt)
 377     }
 378
 379     fn fold_method(&mut self, m: @Method) -> @Method {
 380         self.path.push(PathName(m.ident));
 381         let m = fold::noop_fold_method(m, self);
 382         self.path.pop();
 383         m
 384     }
 385
 386     fn fold_fn_decl(&mut self, decl: &FnDecl) -> P<FnDecl> {
 387         let decl = fold::noop_fold_fn_decl(decl, self);
 388         for a in decl.inputs.iter() {
 389             self.insert(a.id, NodeArg(a.pat));
 390         }
 391         decl
 392     }
 393
 394     fn fold_block(&mut self, block: P<Block>) -> P<Block> {
 395         let block = fold::noop_fold_block(block, self);
 396         self.insert(block.id, NodeBlock(block));
 397         block
 398     }
 399 }
 400
 401 pub fn map_crate<F: 'static + FoldOps>(diag: @SpanHandler, c: Crate,
 402                                        fold_ops: F) -> (Crate, Map) {
 403     let mut cx = Ctx {
 404         map: Map { map: @RefCell::new(SmallIntMap::new()) },
 405         path: ~[],
 406         diag: diag,
 407         fold_ops: fold_ops
 408     };
 409     let crate = cx.fold_crate(c);
 410
 411     if log_enabled!(logging::DEBUG) {
 412         let map = cx.map.map.borrow();
 413         // this only makes sense for ordered stores; note the
 414         // enumerate to count the number of entries.
 415         let (entries_less_1, (largest_id, _)) =
 416             map.get().iter().enumerate().last().expect("AST map was empty after folding?");
 417
 418         let entries = entries_less_1 + 1;
 419         let vector_length = largest_id + 1;
 420         debug!("The AST map has {} entries with a maximum of {}: occupancy {:.1}%",
 421               entries, vector_length, (entries as f64 / vector_length as f64) * 100.);
 422     }
 423
 424     (crate, cx.map)
 425 }
 426
 427 // Used for items loaded from external crate that are being inlined into this
 428 // crate.  The `path` should be the path to the item but should not include
 429 // the item itself.
 430 pub fn map_decoded_item<F: 'static + FoldOps>(diag: @SpanHandler,
 431                                               map: Map,
 432                                               path: Path,
 433                                               fold_ops: F,
 434                                               fold_ii: |&mut Ctx<F>| -> InlinedItem)
 435                                               -> InlinedItem {
 436     // I believe it is ok for the local IDs of inlined items from other crates
 437     // to overlap with the local ids from this crate, so just generate the ids
 438     // starting from 0.
 439     let mut cx = Ctx {
 440         map: map,
 441         path: path.clone(),
 442         diag: diag,
 443         fold_ops: fold_ops
 444     };
 445
 446     let ii = fold_ii(&mut cx);
 447
 448     // Methods get added to the AST map when their impl is visited.  Since we
 449     // don't decode and instantiate the impl, but just the method, we have to
 450     // add it to the table now. Likewise with foreign items.
 451     match ii {
 452         IIItem(..) => {} // fallthrough
 453         IIForeign(i) => {
 454             cx.insert(i.id, NodeForeignItem(i,
 455                                             AbiSet::Intrinsic(),
 456                                             i.vis,    // Wrong but OK
 457                                             @path));
 458         }
 459         IIMethod(impl_did, is_provided, m) => {
 460             let entry = if is_provided {
 461                 NodeTraitMethod(@Provided(m), impl_did, @path)
 462             } else {
 463                 NodeMethod(m, impl_did, @path)
 464             };
 465             cx.insert(m.id, entry);
 466         }
 467     }
 468
 469     ii
 470 }
 471
 472 pub fn node_id_to_str(map: Map, id: NodeId, itr: @IdentInterner) -> ~str {
 473     match map.find(id) {
 474       None => {
 475         format!("unknown node (id={})", id)
 476       }
 477       Some(NodeItem(item, path)) => {
 478         let path_str = path_ident_to_str(path, item.ident, itr);
 479         let item_str = match item.node {
 480             ItemStatic(..) => ~"static",
 481             ItemFn(..) => ~"fn",
 482             ItemMod(..) => ~"mod",
 483             ItemForeignMod(..) => ~"foreign mod",
 484             ItemTy(..) => ~"ty",
 485             ItemEnum(..) => ~"enum",
 486             ItemStruct(..) => ~"struct",
 487             ItemTrait(..) => ~"trait",
 488             ItemImpl(..) => ~"impl",
 489             ItemMac(..) => ~"macro"
 490         };
 491         format!("{} {} (id={})", item_str, path_str, id)
 492       }
 493       Some(NodeForeignItem(item, abi, _, path)) => {
 494         format!("foreign item {} with abi {:?} (id={})",
 495              path_ident_to_str(path, item.ident, itr), abi, id)
 496       }
 497       Some(NodeMethod(m, _, path)) => {
 498         let name = itr.get(m.ident.name);
 499         format!("method {} in {} (id={})",
 500              name.as_slice(), path_to_str(*path, itr), id)
 501       }
 502       Some(NodeTraitMethod(ref tm, _, path)) => {
 503         let m = ast_util::trait_method_to_ty_method(&**tm);
 504         let name = itr.get(m.ident.name);
 505         format!("method {} in {} (id={})",
 506              name.as_slice(), path_to_str(*path, itr), id)
 507       }
 508       Some(NodeVariant(ref variant, _, path)) => {
 509         let name = itr.get(variant.node.name.name);
 510         format!("variant {} in {} (id={})",
 511              name.as_slice(),
 512              path_to_str(*path, itr), id)
 513       }
 514       Some(NodeExpr(expr)) => {
 515         format!("expr {} (id={})", pprust::expr_to_str(expr, itr), id)
 516       }
 517       Some(NodeCalleeScope(expr)) => {
 518         format!("callee_scope {} (id={})", pprust::expr_to_str(expr, itr), id)
 519       }
 520       Some(NodeStmt(stmt)) => {
 521         format!("stmt {} (id={})",
 522              pprust::stmt_to_str(stmt, itr), id)
 523       }
 524       Some(NodeArg(pat)) => {
 525         format!("arg {} (id={})", pprust::pat_to_str(pat, itr), id)
 526       }
 527       Some(NodeLocal(pat)) => {
 528         format!("local {} (id={})", pprust::pat_to_str(pat, itr), id)
 529       }
 530       Some(NodeBlock(block)) => {
 531         format!("block {} (id={})", pprust::block_to_str(block, itr), id)
 532       }
 533       Some(NodeStructCtor(_, _, path)) => {
 534         format!("struct_ctor {} (id={})", path_to_str(*path, itr), id)
 535       }
 536     }
 537 }
 538
 539 pub fn node_item_query<Result>(items: Map, id: NodeId, query: |@Item| -> Result, error_msg: ~str)
 540                        -> Result {
 541     match items.find(id) {
 542         Some(NodeItem(it, _)) => query(it),
 543         _ => fail!("{}", error_msg)
 544     }
 545 }
 546
 547 pub fn node_span(items: Map, id: ast::NodeId) -> Span {
 548     match items.find(id) {
 549         Some(NodeItem(item, _)) => item.span,
 550         Some(NodeForeignItem(foreign_item, _, _, _)) => foreign_item.span,
 551         Some(NodeTraitMethod(trait_method, _, _)) => {
 552             match *trait_method {
 553                 Required(ref type_method) => type_method.span,
 554                 Provided(ref method) => method.span,
 555             }
 556         }
 557         Some(NodeMethod(method, _, _)) => method.span,
 558         Some(NodeVariant(variant, _, _)) => variant.span,
 559         Some(NodeExpr(expr)) => expr.span,
 560         Some(NodeStmt(stmt)) => stmt.span,
 561         Some(NodeArg(pat)) | Some(NodeLocal(pat)) => pat.span,
 562         Some(NodeBlock(block)) => block.span,
 563         Some(NodeStructCtor(_, item, _)) => item.span,
 564         Some(NodeCalleeScope(expr)) => expr.span,
 565         None => fail!("node_span: could not find id {}", id),
 566     }
 567 }