src/libsyntax/ast_util.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 ast::*;
  12 use ast;
  13 use ast_util;
  14 use codemap::Span;
  15 use opt_vec;
  16 use parse::token;
  17 use print::pprust;
  18 use visit::Visitor;
  19 use visit;
  20
  21 use std::cell::{Cell, RefCell};
  22 use std::cmp;
  23 use collections::HashMap;
  24 use std::u32;
  25 use std::local_data;
  26 use std::vec_ng::Vec;
  27
  28 pub fn path_name_i(idents: &[Ident]) -> ~str {
  29     // FIXME: Bad copies (#2543 -- same for everything else that says "bad")
  30     idents.map(|i| {
  31         token::get_ident(*i).get().to_str()
  32     }).connect("::")
  33 }
  34
  35 // totally scary function: ignores all but the last element, should have
  36 // a different name
  37 pub fn path_to_ident(path: &Path) -> Ident {
  38     path.segments.last().unwrap().identifier
  39 }
  40
  41 pub fn local_def(id: NodeId) -> DefId {
  42     ast::DefId { krate: LOCAL_CRATE, node: id }
  43 }
  44
  45 pub fn is_local(did: ast::DefId) -> bool { did.krate == LOCAL_CRATE }
  46
  47 pub fn stmt_id(s: &Stmt) -> NodeId {
  48     match s.node {
  49       StmtDecl(_, id) => id,
  50       StmtExpr(_, id) => id,
  51       StmtSemi(_, id) => id,
  52       StmtMac(..) => fail!("attempted to analyze unexpanded stmt")
  53     }
  54 }
  55
  56 pub fn variant_def_ids(d: Def) -> Option<(DefId, DefId)> {
  57     match d {
  58       DefVariant(enum_id, var_id, _) => {
  59           Some((enum_id, var_id))
  60       }
  61       _ => None
  62     }
  63 }
  64
  65 pub fn def_id_of_def(d: Def) -> DefId {
  66     match d {
  67         DefFn(id, _) | DefStaticMethod(id, _, _) | DefMod(id) |
  68         DefForeignMod(id) | DefStatic(id, _) |
  69         DefVariant(_, id, _) | DefTy(id) | DefTyParam(id, _) |
  70         DefUse(id) | DefStruct(id) | DefTrait(id) | DefMethod(id, _) => {
  71             id
  72         }
  73         DefArg(id, _) | DefLocal(id, _) | DefSelfTy(id)
  74         | DefUpvar(id, _, _, _) | DefBinding(id, _) | DefRegion(id)
  75         | DefTyParamBinder(id) | DefLabel(id) => {
  76             local_def(id)
  77         }
  78
  79         DefPrimTy(_) => fail!()
  80     }
  81 }
  82
  83 pub fn binop_to_str(op: BinOp) -> &'static str {
  84     match op {
  85         BiAdd => "+",
  86         BiSub => "-",
  87         BiMul => "*",
  88         BiDiv => "/",
  89         BiRem => "%",
  90         BiAnd => "&&",
  91         BiOr => "||",
  92         BiBitXor => "^",
  93         BiBitAnd => "&",
  94         BiBitOr => "|",
  95         BiShl => "<<",
  96         BiShr => ">>",
  97         BiEq => "==",
  98         BiLt => "<",
  99         BiLe => "<=",
 100         BiNe => "!=",
 101         BiGe => ">=",
 102         BiGt => ">"
 103     }
 104 }
 105
 106 pub fn lazy_binop(b: BinOp) -> bool {
 107     match b {
 108       BiAnd => true,
 109       BiOr => true,
 110       _ => false
 111     }
 112 }
 113
 114 pub fn is_shift_binop(b: BinOp) -> bool {
 115     match b {
 116       BiShl => true,
 117       BiShr => true,
 118       _ => false
 119     }
 120 }
 121
 122 pub fn unop_to_str(op: UnOp) -> &'static str {
 123     match op {
 124       UnBox => "@",
 125       UnUniq => "~",
 126       UnDeref => "*",
 127       UnNot => "!",
 128       UnNeg => "-",
 129     }
 130 }
 131
 132 pub fn is_path(e: @Expr) -> bool {
 133     return match e.node { ExprPath(_) => true, _ => false };
 134 }
 135
 136 pub fn int_ty_to_str(t: IntTy) -> ~str {
 137     match t {
 138         TyI => ~"",
 139         TyI8 => ~"i8",
 140         TyI16 => ~"i16",
 141         TyI32 => ~"i32",
 142         TyI64 => ~"i64"
 143     }
 144 }
 145
 146 pub fn int_ty_max(t: IntTy) -> u64 {
 147     match t {
 148         TyI8 => 0x80u64,
 149         TyI16 => 0x8000u64,
 150         TyI | TyI32 => 0x80000000u64, // actually ni about TyI
 151         TyI64 => 0x8000000000000000u64
 152     }
 153 }
 154
 155 pub fn uint_ty_to_str(t: UintTy) -> ~str {
 156     match t {
 157         TyU => ~"u",
 158         TyU8 => ~"u8",
 159         TyU16 => ~"u16",
 160         TyU32 => ~"u32",
 161         TyU64 => ~"u64"
 162     }
 163 }
 164
 165 pub fn uint_ty_max(t: UintTy) -> u64 {
 166     match t {
 167         TyU8 => 0xffu64,
 168         TyU16 => 0xffffu64,
 169         TyU | TyU32 => 0xffffffffu64, // actually ni about TyU
 170         TyU64 => 0xffffffffffffffffu64
 171     }
 172 }
 173
 174 pub fn float_ty_to_str(t: FloatTy) -> ~str {
 175     match t { TyF32 => ~"f32", TyF64 => ~"f64" }
 176 }
 177
 178 pub fn is_call_expr(e: @Expr) -> bool {
 179     match e.node { ExprCall(..) => true, _ => false }
 180 }
 181
 182 pub fn block_from_expr(e: @Expr) -> P<Block> {
 183     P(Block {
 184         view_items: Vec::new(),
 185         stmts: Vec::new(),
 186         expr: Some(e),
 187         id: e.id,
 188         rules: DefaultBlock,
 189         span: e.span
 190     })
 191 }
 192
 193 pub fn ident_to_path(s: Span, identifier: Ident) -> Path {
 194     ast::Path {
 195         span: s,
 196         global: false,
 197         segments: vec!(
 198             ast::PathSegment {
 199                 identifier: identifier,
 200                 lifetimes: opt_vec::Empty,
 201                 types: opt_vec::Empty,
 202             }
 203         ),
 204     }
 205 }
 206
 207 pub fn ident_to_pat(id: NodeId, s: Span, i: Ident) -> @Pat {
 208     @ast::Pat { id: id,
 209                 node: PatIdent(BindByValue(MutImmutable), ident_to_path(s, i), None),
 210                 span: s }
 211 }
 212
 213 pub fn is_unguarded(a: &Arm) -> bool {
 214     match a.guard {
 215       None => true,
 216       _    => false
 217     }
 218 }
 219
 220 pub fn unguarded_pat(a: &Arm) -> Option<Vec<@Pat> > {
 221     if is_unguarded(a) {
 222         Some(/* FIXME (#2543) */ a.pats.clone())
 223     } else {
 224         None
 225     }
 226 }
 227
 228 /// Generate a "pretty" name for an `impl` from its type and trait.
 229 /// This is designed so that symbols of `impl`'d methods give some
 230 /// hint of where they came from, (previously they would all just be
 231 /// listed as `__extensions__::method_name::hash`, with no indication
 232 /// of the type).
 233 pub fn impl_pretty_name(trait_ref: &Option<TraitRef>, ty: &Ty) -> Ident {
 234     let mut pretty = pprust::ty_to_str(ty);
 235     match *trait_ref {
 236         Some(ref trait_ref) => {
 237             pretty.push_char('.');
 238             pretty.push_str(pprust::path_to_str(&trait_ref.path));
 239         }
 240         None => {}
 241     }
 242     token::gensym_ident(pretty)
 243 }
 244
 245 pub fn public_methods(ms: Vec<@Method> ) -> Vec<@Method> {
 246     ms.move_iter().filter(|m| {
 247         match m.vis {
 248             Public => true,
 249             _   => false
 250         }
 251     }).collect()
 252 }
 253
 254 // extract a TypeMethod from a TraitMethod. if the TraitMethod is
 255 // a default, pull out the useful fields to make a TypeMethod
 256 pub fn trait_method_to_ty_method(method: &TraitMethod) -> TypeMethod {
 257     match *method {
 258         Required(ref m) => (*m).clone(),
 259         Provided(ref m) => {
 260             TypeMethod {
 261                 ident: m.ident,
 262                 attrs: m.attrs.clone(),
 263                 purity: m.purity,
 264                 decl: m.decl,
 265                 generics: m.generics.clone(),
 266                 explicit_self: m.explicit_self,
 267                 id: m.id,
 268                 span: m.span,
 269             }
 270         }
 271     }
 272 }
 273
 274 pub fn split_trait_methods(trait_methods: &[TraitMethod])
 275     -> (Vec<TypeMethod> , Vec<@Method> ) {
 276     let mut reqd = Vec::new();
 277     let mut provd = Vec::new();
 278     for trt_method in trait_methods.iter() {
 279         match *trt_method {
 280             Required(ref tm) => reqd.push((*tm).clone()),
 281             Provided(m) => provd.push(m)
 282         }
 283     };
 284     (reqd, provd)
 285 }
 286
 287 pub fn struct_field_visibility(field: ast::StructField) -> Visibility {
 288     match field.node.kind {
 289         ast::NamedField(_, visibility) => visibility,
 290         ast::UnnamedField => ast::Public
 291     }
 292 }
 293
 294 /// Maps a binary operator to its precedence
 295 pub fn operator_prec(op: ast::BinOp) -> uint {
 296   match op {
 297       // 'as' sits here with 12
 298       BiMul | BiDiv | BiRem     => 11u,
 299       BiAdd | BiSub             => 10u,
 300       BiShl | BiShr             =>  9u,
 301       BiBitAnd                  =>  8u,
 302       BiBitXor                  =>  7u,
 303       BiBitOr                   =>  6u,
 304       BiLt | BiLe | BiGe | BiGt =>  4u,
 305       BiEq | BiNe               =>  3u,
 306       BiAnd                     =>  2u,
 307       BiOr                      =>  1u
 308   }
 309 }
 310
 311 /// Precedence of the `as` operator, which is a binary operator
 312 /// not appearing in the prior table.
 313 pub static as_prec: uint = 12u;
 314
 315 pub fn empty_generics() -> Generics {
 316     Generics {lifetimes: opt_vec::Empty,
 317               ty_params: opt_vec::Empty}
 318 }
 319
 320 // ______________________________________________________________________
 321 // Enumerating the IDs which appear in an AST
 322
 323 #[deriving(Encodable, Decodable)]
 324 pub struct IdRange {
 325     min: NodeId,
 326     max: NodeId,
 327 }
 328
 329 impl IdRange {
 330     pub fn max() -> IdRange {
 331         IdRange {
 332             min: u32::MAX,
 333             max: u32::MIN,
 334         }
 335     }
 336
 337     pub fn empty(&self) -> bool {
 338         self.min >= self.max
 339     }
 340
 341     pub fn add(&mut self, id: NodeId) {
 342         self.min = cmp::min(self.min, id);
 343         self.max = cmp::max(self.max, id + 1);
 344     }
 345 }
 346
 347 pub trait IdVisitingOperation {
 348     fn visit_id(&self, node_id: NodeId);
 349 }
 350
 351 pub struct IdVisitor<'a, O> {
 352     operation: &'a O,
 353     pass_through_items: bool,
 354     visited_outermost: bool,
 355 }
 356
 357 impl<'a, O: IdVisitingOperation> IdVisitor<'a, O> {
 358     fn visit_generics_helper(&self, generics: &Generics) {
 359         for type_parameter in generics.ty_params.iter() {
 360             self.operation.visit_id(type_parameter.id)
 361         }
 362         for lifetime in generics.lifetimes.iter() {
 363             self.operation.visit_id(lifetime.id)
 364         }
 365     }
 366 }
 367
 368 impl<'a, O: IdVisitingOperation> Visitor<()> for IdVisitor<'a, O> {
 369     fn visit_mod(&mut self,
 370                  module: &Mod,
 371                  _: Span,
 372                  node_id: NodeId,
 373                  env: ()) {
 374         self.operation.visit_id(node_id);
 375         visit::walk_mod(self, module, env)
 376     }
 377
 378     fn visit_view_item(&mut self, view_item: &ViewItem, env: ()) {
 379         match view_item.node {
 380             ViewItemExternMod(_, _, node_id) => {
 381                 self.operation.visit_id(node_id)
 382             }
 383             ViewItemUse(ref view_paths) => {
 384                 for view_path in view_paths.iter() {
 385                     match view_path.node {
 386                         ViewPathSimple(_, _, node_id) |
 387                         ViewPathGlob(_, node_id) => {
 388                             self.operation.visit_id(node_id)
 389                         }
 390                         ViewPathList(_, ref paths, node_id) => {
 391                             self.operation.visit_id(node_id);
 392                             for path in paths.iter() {
 393                                 self.operation.visit_id(path.node.id)
 394                             }
 395                         }
 396                     }
 397                 }
 398             }
 399         }
 400         visit::walk_view_item(self, view_item, env)
 401     }
 402
 403     fn visit_foreign_item(&mut self, foreign_item: &ForeignItem, env: ()) {
 404         self.operation.visit_id(foreign_item.id);
 405         visit::walk_foreign_item(self, foreign_item, env)
 406     }
 407
 408     fn visit_item(&mut self, item: &Item, env: ()) {
 409         if !self.pass_through_items {
 410             if self.visited_outermost {
 411                 return
 412             } else {
 413                 self.visited_outermost = true
 414             }
 415         }
 416
 417         self.operation.visit_id(item.id);
 418         match item.node {
 419             ItemEnum(ref enum_definition, _) => {
 420                 for variant in enum_definition.variants.iter() {
 421                     self.operation.visit_id(variant.node.id)
 422                 }
 423             }
 424             _ => {}
 425         }
 426
 427         visit::walk_item(self, item, env);
 428
 429         self.visited_outermost = false
 430     }
 431
 432     fn visit_local(&mut self, local: &Local, env: ()) {
 433         self.operation.visit_id(local.id);
 434         visit::walk_local(self, local, env)
 435     }
 436
 437     fn visit_block(&mut self, block: &Block, env: ()) {
 438         self.operation.visit_id(block.id);
 439         visit::walk_block(self, block, env)
 440     }
 441
 442     fn visit_stmt(&mut self, statement: &Stmt, env: ()) {
 443         self.operation.visit_id(ast_util::stmt_id(statement));
 444         visit::walk_stmt(self, statement, env)
 445     }
 446
 447     fn visit_pat(&mut self, pattern: &Pat, env: ()) {
 448         self.operation.visit_id(pattern.id);
 449         visit::walk_pat(self, pattern, env)
 450     }
 451
 452
 453     fn visit_expr(&mut self, expression: &Expr, env: ()) {
 454         self.operation.visit_id(expression.id);
 455         visit::walk_expr(self, expression, env)
 456     }
 457
 458     fn visit_ty(&mut self, typ: &Ty, env: ()) {
 459         self.operation.visit_id(typ.id);
 460         match typ.node {
 461             TyPath(_, _, id) => self.operation.visit_id(id),
 462             _ => {}
 463         }
 464         visit::walk_ty(self, typ, env)
 465     }
 466
 467     fn visit_generics(&mut self, generics: &Generics, env: ()) {
 468         self.visit_generics_helper(generics);
 469         visit::walk_generics(self, generics, env)
 470     }
 471
 472     fn visit_fn(&mut self,
 473                 function_kind: &visit::FnKind,
 474                 function_declaration: &FnDecl,
 475                 block: &Block,
 476                 span: Span,
 477                 node_id: NodeId,
 478                 env: ()) {
 479         if !self.pass_through_items {
 480             match *function_kind {
 481                 visit::FkMethod(..) if self.visited_outermost => return,
 482                 visit::FkMethod(..) => self.visited_outermost = true,
 483                 _ => {}
 484             }
 485         }
 486
 487         self.operation.visit_id(node_id);
 488
 489         match *function_kind {
 490             visit::FkItemFn(_, generics, _, _) |
 491             visit::FkMethod(_, generics, _) => {
 492                 self.visit_generics_helper(generics)
 493             }
 494             visit::FkFnBlock => {}
 495         }
 496
 497         for argument in function_declaration.inputs.iter() {
 498             self.operation.visit_id(argument.id)
 499         }
 500
 501         visit::walk_fn(self,
 502                         function_kind,
 503                         function_declaration,
 504                         block,
 505                         span,
 506                         node_id,
 507                         env);
 508
 509         if !self.pass_through_items {
 510             match *function_kind {
 511                 visit::FkMethod(..) => self.visited_outermost = false,
 512                 _ => {}
 513             }
 514         }
 515     }
 516
 517     fn visit_struct_field(&mut self, struct_field: &StructField, env: ()) {
 518         self.operation.visit_id(struct_field.node.id);
 519         visit::walk_struct_field(self, struct_field, env)
 520     }
 521
 522     fn visit_struct_def(&mut self,
 523                         struct_def: &StructDef,
 524                         ident: ast::Ident,
 525                         generics: &ast::Generics,
 526                         id: NodeId,
 527                         _: ()) {
 528         self.operation.visit_id(id);
 529         struct_def.ctor_id.map(|ctor_id| self.operation.visit_id(ctor_id));
 530         visit::walk_struct_def(self, struct_def, ident, generics, id, ());
 531     }
 532
 533     fn visit_trait_method(&mut self, tm: &ast::TraitMethod, _: ()) {
 534         match *tm {
 535             ast::Required(ref m) => self.operation.visit_id(m.id),
 536             ast::Provided(ref m) => self.operation.visit_id(m.id),
 537         }
 538         visit::walk_trait_method(self, tm, ());
 539     }
 540 }
 541
 542 pub fn visit_ids_for_inlined_item<O: IdVisitingOperation>(item: &InlinedItem,
 543                                                           operation: &O) {
 544     let mut id_visitor = IdVisitor {
 545         operation: operation,
 546         pass_through_items: true,
 547         visited_outermost: false,
 548     };
 549
 550     visit::walk_inlined_item(&mut id_visitor, item, ());
 551 }
 552
 553 struct IdRangeComputingVisitor {
 554     result: Cell<IdRange>,
 555 }
 556
 557 impl IdVisitingOperation for IdRangeComputingVisitor {
 558     fn visit_id(&self, id: NodeId) {
 559         let mut id_range = self.result.get();
 560         id_range.add(id);
 561         self.result.set(id_range)
 562     }
 563 }
 564
 565 pub fn compute_id_range_for_inlined_item(item: &InlinedItem) -> IdRange {
 566     let visitor = IdRangeComputingVisitor {
 567         result: Cell::new(IdRange::max())
 568     };
 569     visit_ids_for_inlined_item(item, &visitor);
 570     visitor.result.get()
 571 }
 572
 573 pub fn is_item_impl(item: @ast::Item) -> bool {
 574     match item.node {
 575         ItemImpl(..) => true,
 576         _            => false
 577     }
 578 }
 579
 580 pub fn walk_pat(pat: &Pat, it: |&Pat| -> bool) -> bool {
 581     if !it(pat) {
 582         return false;
 583     }
 584
 585     match pat.node {
 586         PatIdent(_, _, Some(p)) => walk_pat(p, it),
 587         PatStruct(_, ref fields, _) => {
 588             fields.iter().advance(|f| walk_pat(f.pat, |p| it(p)))
 589         }
 590         PatEnum(_, Some(ref s)) | PatTup(ref s) => {
 591             s.iter().advance(|&p| walk_pat(p, |p| it(p)))
 592         }
 593         PatUniq(s) | PatRegion(s) => {
 594             walk_pat(s, it)
 595         }
 596         PatVec(ref before, ref slice, ref after) => {
 597             before.iter().advance(|&p| walk_pat(p, |p| it(p))) &&
 598                 slice.iter().advance(|&p| walk_pat(p, |p| it(p))) &&
 599                 after.iter().advance(|&p| walk_pat(p, |p| it(p)))
 600         }
 601         PatWild | PatWildMulti | PatLit(_) | PatRange(_, _) | PatIdent(_, _, _) |
 602         PatEnum(_, _) => {
 603             true
 604         }
 605     }
 606 }
 607
 608 pub trait EachViewItem {
 609     fn each_view_item(&self, f: |&ast::ViewItem| -> bool) -> bool;
 610 }
 611
 612 struct EachViewItemData<'a> {
 613     callback: 'a |&ast::ViewItem| -> bool,
 614 }
 615
 616 impl<'a> Visitor<()> for EachViewItemData<'a> {
 617     fn visit_view_item(&mut self, view_item: &ast::ViewItem, _: ()) {
 618         let _ = (self.callback)(view_item);
 619     }
 620 }
 621
 622 impl EachViewItem for ast::Crate {
 623     fn each_view_item(&self, f: |&ast::ViewItem| -> bool) -> bool {
 624         let mut visit = EachViewItemData {
 625             callback: f,
 626         };
 627         visit::walk_crate(&mut visit, self, ());
 628         true
 629     }
 630 }
 631
 632 pub fn view_path_id(p: &ViewPath) -> NodeId {
 633     match p.node {
 634         ViewPathSimple(_, _, id) | ViewPathGlob(_, id)
 635         | ViewPathList(_, _, id) => id
 636     }
 637 }
 638
 639 /// Returns true if the given struct def is tuple-like; i.e. that its fields
 640 /// are unnamed.
 641 pub fn struct_def_is_tuple_like(struct_def: &ast::StructDef) -> bool {
 642     struct_def.ctor_id.is_some()
 643 }
 644
 645 /// Returns true if the given pattern consists solely of an identifier
 646 /// and false otherwise.
 647 pub fn pat_is_ident(pat: @ast::Pat) -> bool {
 648     match pat.node {
 649         ast::PatIdent(..) => true,
 650         _ => false,
 651     }
 652 }
 653
 654 // HYGIENE FUNCTIONS
 655
 656 /// Extend a syntax context with a given mark
 657 pub fn new_mark(m:Mrk, tail:SyntaxContext) -> SyntaxContext {
 658     new_mark_internal(m,tail,get_sctable())
 659 }
 660
 661 // Extend a syntax context with a given mark and table
 662 // FIXME #8215 : currently pub to allow testing
 663 pub fn new_mark_internal(m: Mrk, tail: SyntaxContext, table: &SCTable)
 664                          -> SyntaxContext {
 665     let key = (tail,m);
 666     // FIXME #5074 : can't use more natural style because we're missing
 667     // flow-sensitivity. Results in two lookups on a hash table hit.
 668     // also applies to new_rename_internal, below.
 669     // let try_lookup = table.mark_memo.find(&key);
 670     let mut mark_memo = table.mark_memo.borrow_mut();
 671     match mark_memo.get().contains_key(&key) {
 672         false => {
 673             let new_idx = {
 674                 let mut table = table.table.borrow_mut();
 675                 idx_push(table.get(), Mark(m,tail))
 676             };
 677             mark_memo.get().insert(key,new_idx);
 678             new_idx
 679         }
 680         true => {
 681             match mark_memo.get().find(&key) {
 682                 None => fail!("internal error: key disappeared 2013042901"),
 683                 Some(idxptr) => {*idxptr}
 684             }
 685         }
 686     }
 687 }
 688
 689 /// Extend a syntax context with a given rename
 690 pub fn new_rename(id:Ident, to:Name, tail:SyntaxContext) -> SyntaxContext {
 691     new_rename_internal(id, to, tail, get_sctable())
 692 }
 693
 694 // Extend a syntax context with a given rename and sctable
 695 // FIXME #8215 : currently pub to allow testing
 696 pub fn new_rename_internal(id: Ident,
 697                            to: Name,
 698                            tail: SyntaxContext,
 699                            table: &SCTable)
 700                            -> SyntaxContext {
 701     let key = (tail,id,to);
 702     // FIXME #5074
 703     //let try_lookup = table.rename_memo.find(&key);
 704     let mut rename_memo = table.rename_memo.borrow_mut();
 705     match rename_memo.get().contains_key(&key) {
 706         false => {
 707             let new_idx = {
 708                 let mut table = table.table.borrow_mut();
 709                 idx_push(table.get(), Rename(id,to,tail))
 710             };
 711             rename_memo.get().insert(key,new_idx);
 712             new_idx
 713         }
 714         true => {
 715             match rename_memo.get().find(&key) {
 716                 None => fail!("internal error: key disappeared 2013042902"),
 717                 Some(idxptr) => {*idxptr}
 718             }
 719         }
 720     }
 721 }
 722
 723 /// Make a fresh syntax context table with EmptyCtxt in slot zero
 724 /// and IllegalCtxt in slot one.
 725 // FIXME #8215 : currently pub to allow testing
 726 pub fn new_sctable_internal() -> SCTable {
 727     SCTable {
 728         table: RefCell::new(vec!(EmptyCtxt,IllegalCtxt)),
 729         mark_memo: RefCell::new(HashMap::new()),
 730         rename_memo: RefCell::new(HashMap::new()),
 731     }
 732 }
 733
 734 // fetch the SCTable from TLS, create one if it doesn't yet exist.
 735 pub fn get_sctable() -> @SCTable {
 736     local_data_key!(sctable_key: @@SCTable)
 737     match local_data::get(sctable_key, |k| k.map(|k| *k)) {
 738         None => {
 739             let new_table = @@new_sctable_internal();
 740             local_data::set(sctable_key,new_table);
 741             *new_table
 742         },
 743         Some(intr) => *intr
 744     }
 745 }
 746
 747 /// print out an SCTable for debugging
 748 pub fn display_sctable(table : &SCTable) {
 749     error!("SC table:");
 750     let table = table.table.borrow();
 751     for (idx,val) in table.get().iter().enumerate() {
 752         error!("{:4u} : {:?}",idx,val);
 753     }
 754 }
 755
 756
 757 /// Add a value to the end of a vec, return its index
 758 fn idx_push<T>(vec: &mut Vec<T> , val: T) -> u32 {
 759     vec.push(val);
 760     (vec.len() - 1) as u32
 761 }
 762
 763 /// Resolve a syntax object to a name, per MTWT.
 764 pub fn mtwt_resolve(id : Ident) -> Name {
 765     let resolve_table = get_resolve_table();
 766     let mut resolve_table = resolve_table.borrow_mut();
 767     resolve_internal(id, get_sctable(), resolve_table.get())
 768 }
 769
 770 // FIXME #8215: must be pub for testing
 771 pub type ResolveTable = HashMap<(Name,SyntaxContext),Name>;
 772
 773 // okay, I admit, putting this in TLS is not so nice:
 774 // fetch the SCTable from TLS, create one if it doesn't yet exist.
 775 pub fn get_resolve_table() -> @RefCell<ResolveTable> {
 776     local_data_key!(resolve_table_key: @@RefCell<ResolveTable>)
 777     match local_data::get(resolve_table_key, |k| k.map(|k| *k)) {
 778         None => {
 779             let new_table = @@RefCell::new(HashMap::new());
 780             local_data::set(resolve_table_key, new_table);
 781             *new_table
 782         },
 783         Some(intr) => *intr
 784     }
 785 }
 786
 787 // Resolve a syntax object to a name, per MTWT.
 788 // adding memoization to possibly resolve 500+ seconds in resolve for librustc (!)
 789 // FIXME #8215 : currently pub to allow testing
 790 pub fn resolve_internal(id : Ident,
 791                         table : &SCTable,
 792                         resolve_table : &mut ResolveTable) -> Name {
 793     let key = (id.name,id.ctxt);
 794     match resolve_table.contains_key(&key) {
 795         false => {
 796             let resolved = {
 797                 let result = {
 798                     let table = table.table.borrow();
 799                     *table.get().get(id.ctxt as uint)
 800                 };
 801                 match result {
 802                     EmptyCtxt => id.name,
 803                     // ignore marks here:
 804                     Mark(_,subctxt) =>
 805                         resolve_internal(Ident{name:id.name, ctxt: subctxt},table,resolve_table),
 806                     // do the rename if necessary:
 807                     Rename(Ident{name,ctxt},toname,subctxt) => {
 808                         let resolvedfrom =
 809                             resolve_internal(Ident{name:name,ctxt:ctxt},table,resolve_table);
 810                         let resolvedthis =
 811                             resolve_internal(Ident{name:id.name,ctxt:subctxt},table,resolve_table);
 812                         if (resolvedthis == resolvedfrom)
 813                             && (marksof(ctxt,resolvedthis,table)
 814                                 == marksof(subctxt,resolvedthis,table)) {
 815                             toname
 816                         } else {
 817                             resolvedthis
 818                         }
 819                     }
 820                     IllegalCtxt() => fail!("expected resolvable context, got IllegalCtxt")
 821                 }
 822             };
 823             resolve_table.insert(key,resolved);
 824             resolved
 825         }
 826         true => {
 827             // it's guaranteed to be there, because we just checked that it was
 828             // there and we never remove anything from the table:
 829             *(resolve_table.find(&key).unwrap())
 830         }
 831     }
 832 }
 833
 834 /// Compute the marks associated with a syntax context.
 835 pub fn mtwt_marksof(ctxt: SyntaxContext, stopname: Name) -> Vec<Mrk> {
 836     marksof(ctxt, stopname, get_sctable())
 837 }
 838
 839 // the internal function for computing marks
 840 // it's not clear to me whether it's better to use a [] mutable
 841 // vector or a cons-list for this.
 842 pub fn marksof(ctxt: SyntaxContext, stopname: Name, table: &SCTable) -> Vec<Mrk> {
 843     let mut result = Vec::new();
 844     let mut loopvar = ctxt;
 845     loop {
 846         let table_entry = {
 847             let table = table.table.borrow();
 848             *table.get().get(loopvar as uint)
 849         };
 850         match table_entry {
 851             EmptyCtxt => {
 852                 return result;
 853             },
 854             Mark(mark, tl) => {
 855                 xorPush(&mut result, mark);
 856                 loopvar = tl;
 857             },
 858             Rename(_,name,tl) => {
 859                 // see MTWT for details on the purpose of the stopname.
 860                 // short version: it prevents duplication of effort.
 861                 if name == stopname {
 862                     return result;
 863                 } else {
 864                     loopvar = tl;
 865                 }
 866             }
 867             IllegalCtxt => fail!("expected resolvable context, got IllegalCtxt")
 868         }
 869     }
 870 }
 871
 872 /// Return the outer mark for a context with a mark at the outside.
 873 /// FAILS when outside is not a mark.
 874 pub fn mtwt_outer_mark(ctxt: SyntaxContext) -> Mrk {
 875     let sctable = get_sctable();
 876     let table = sctable.table.borrow();
 877     match *table.get().get(ctxt as uint) {
 878         ast::Mark(mrk,_) => mrk,
 879         _ => fail!("can't retrieve outer mark when outside is not a mark")
 880     }
 881 }
 882
 883 /// Push a name... unless it matches the one on top, in which
 884 /// case pop and discard (so two of the same marks cancel)
 885 pub fn xorPush(marks: &mut Vec<Mrk> , mark: Mrk) {
 886     if (marks.len() > 0) && (getLast(marks) == mark) {
 887         marks.pop().unwrap();
 888     } else {
 889         marks.push(mark);
 890     }
 891 }
 892
 893 // get the last element of a mutable array.
 894 // FIXME #4903: , must be a separate procedure for now.
 895 pub fn getLast(arr: &Vec<Mrk> ) -> Mrk {
 896     *arr.last().unwrap()
 897 }
 898
 899 // are two paths equal when compared unhygienically?
 900 // since I'm using this to replace ==, it seems appropriate
 901 // to compare the span, global, etc. fields as well.
 902 pub fn path_name_eq(a : &ast::Path, b : &ast::Path) -> bool {
 903     (a.span == b.span)
 904     && (a.global == b.global)
 905     && (segments_name_eq(a.segments.as_slice(), b.segments.as_slice()))
 906 }
 907
 908 // are two arrays of segments equal when compared unhygienically?
 909 pub fn segments_name_eq(a : &[ast::PathSegment], b : &[ast::PathSegment]) -> bool {
 910     if a.len() != b.len() {
 911         false
 912     } else {
 913         for (idx,seg) in a.iter().enumerate() {
 914             if (seg.identifier.name != b[idx].identifier.name)
 915                 // FIXME #7743: ident -> name problems in lifetime comparison?
 916                 || (seg.lifetimes != b[idx].lifetimes)
 917                 // can types contain idents?
 918                 || (seg.types != b[idx].types) {
 919                 return false;
 920             }
 921         }
 922         true
 923     }
 924 }
 925
 926 // Returns true if this literal is a string and false otherwise.
 927 pub fn lit_is_str(lit: @Lit) -> bool {
 928     match lit.node {
 929         LitStr(..) => true,
 930         _ => false,
 931     }
 932 }
 933
 934
 935 #[cfg(test)]
 936 mod test {
 937     use ast::*;
 938     use super::*;
 939     use opt_vec;
 940     use collections::HashMap;
 941
 942     use std::vec_ng::Vec;
 943
 944     fn ident_to_segment(id : &Ident) -> PathSegment {
 945         PathSegment {identifier:id.clone(),
 946                      lifetimes: opt_vec::Empty,
 947                      types: opt_vec::Empty}
 948     }
 949
 950     #[test] fn idents_name_eq_test() {
 951         assert!(segments_name_eq([Ident{name:3,ctxt:4},
 952                                    Ident{name:78,ctxt:82}].map(ident_to_segment),
 953                                  [Ident{name:3,ctxt:104},
 954                                    Ident{name:78,ctxt:182}].map(ident_to_segment)));
 955         assert!(!segments_name_eq([Ident{name:3,ctxt:4},
 956                                     Ident{name:78,ctxt:82}].map(ident_to_segment),
 957                                   [Ident{name:3,ctxt:104},
 958                                     Ident{name:77,ctxt:182}].map(ident_to_segment)));
 959     }
 960
 961     #[test] fn xorpush_test () {
 962         let mut s = Vec::new();
 963         xorPush(&mut s, 14);
 964         assert_eq!(s.clone(), vec!(14));
 965         xorPush(&mut s, 14);
 966         assert_eq!(s.clone(), Vec::new());
 967         xorPush(&mut s, 14);
 968         assert_eq!(s.clone(), vec!(14));
 969         xorPush(&mut s, 15);
 970         assert_eq!(s.clone(), vec!(14, 15));
 971         xorPush(&mut s, 16);
 972         assert_eq!(s.clone(), vec!(14, 15, 16));
 973         xorPush(&mut s, 16);
 974         assert_eq!(s.clone(), vec!(14, 15));
 975         xorPush(&mut s, 15);
 976         assert_eq!(s.clone(), vec!(14));
 977     }
 978
 979     fn id(n: Name, s: SyntaxContext) -> Ident {
 980         Ident {name: n, ctxt: s}
 981     }
 982
 983     // because of the SCTable, I now need a tidy way of
 984     // creating syntax objects. Sigh.
 985     #[deriving(Clone, Eq, Show)]
 986     enum TestSC {
 987         M(Mrk),
 988         R(Ident,Name)
 989     }
 990
 991     // unfold a vector of TestSC values into a SCTable,
 992     // returning the resulting index
 993     fn unfold_test_sc(tscs : Vec<TestSC> , tail: SyntaxContext, table: &SCTable)
 994         -> SyntaxContext {
 995         tscs.rev_iter().fold(tail, |tail : SyntaxContext, tsc : &TestSC|
 996                   {match *tsc {
 997                       M(mrk) => new_mark_internal(mrk,tail,table),
 998                       R(ident,name) => new_rename_internal(ident,name,tail,table)}})
 999     }
1000
1001     // gather a SyntaxContext back into a vector of TestSCs
1002     fn refold_test_sc(mut sc: SyntaxContext, table : &SCTable) -> Vec<TestSC> {
1003         let mut result = Vec::new();
1004         loop {
1005             let table = table.table.borrow();
1006             match *table.get().get(sc as uint) {
1007                 EmptyCtxt => {return result;},
1008                 Mark(mrk,tail) => {
1009                     result.push(M(mrk));
1010                     sc = tail;
1011                     continue;
1012                 },
1013                 Rename(id,name,tail) => {
1014                     result.push(R(id,name));
1015                     sc = tail;
1016                     continue;
1017                 }
1018                 IllegalCtxt => fail!("expected resolvable context, got IllegalCtxt")
1019             }
1020         }
1021     }
1022
1023     #[test] fn test_unfold_refold(){
1024         let mut t = new_sctable_internal();
1025
1026         let test_sc = vec!(M(3),R(id(101,0),14),M(9));
1027         assert_eq!(unfold_test_sc(test_sc.clone(),EMPTY_CTXT,&mut t),4);
1028         {
1029             let table = t.table.borrow();
1030             assert!(*table.get().get(2) == Mark(9,0));
1031             assert!(*table.get().get(3) == Rename(id(101,0),14,2));
1032             assert!(*table.get().get(4) == Mark(3,3));
1033         }
1034         assert_eq!(refold_test_sc(4,&t),test_sc);
1035     }
1036
1037     // extend a syntax context with a sequence of marks given
1038     // in a vector. v[0] will be the outermost mark.
1039     fn unfold_marks(mrks: Vec<Mrk> , tail: SyntaxContext, table: &SCTable)
1040                     -> SyntaxContext {
1041         mrks.rev_iter().fold(tail, |tail:SyntaxContext, mrk:&Mrk|
1042                    {new_mark_internal(*mrk,tail,table)})
1043     }
1044
1045     #[test] fn unfold_marks_test() {
1046         let mut t = new_sctable_internal();
1047
1048         assert_eq!(unfold_marks(vec!(3,7),EMPTY_CTXT,&mut t),3);
1049         {
1050             let table = t.table.borrow();
1051             assert!(*table.get().get(2) == Mark(7,0));
1052             assert!(*table.get().get(3) == Mark(3,2));
1053         }
1054     }
1055
1056     #[test] fn test_marksof () {
1057         let stopname = 242;
1058         let name1 = 243;
1059         let mut t = new_sctable_internal();
1060         assert_eq!(marksof (EMPTY_CTXT,stopname,&t),Vec::new());
1061         // FIXME #5074: ANF'd to dodge nested calls
1062         { let ans = unfold_marks(vec!(4,98),EMPTY_CTXT,&mut t);
1063          assert_eq! (marksof (ans,stopname,&t),vec!(4,98));}
1064         // does xoring work?
1065         { let ans = unfold_marks(vec!(5,5,16),EMPTY_CTXT,&mut t);
1066          assert_eq! (marksof (ans,stopname,&t), vec!(16));}
1067         // does nested xoring work?
1068         { let ans = unfold_marks(vec!(5,10,10,5,16),EMPTY_CTXT,&mut t);
1069          assert_eq! (marksof (ans, stopname,&t), vec!(16));}
1070         // rename where stop doesn't match:
1071         { let chain = vec!(M(9),
1072                         R(id(name1,
1073                              new_mark_internal (4, EMPTY_CTXT,&mut t)),
1074                           100101102),
1075                         M(14));
1076          let ans = unfold_test_sc(chain,EMPTY_CTXT,&mut t);
1077          assert_eq! (marksof (ans, stopname, &t), vec!(9,14));}
1078         // rename where stop does match
1079         { let name1sc = new_mark_internal(4, EMPTY_CTXT, &mut t);
1080          let chain = vec!(M(9),
1081                        R(id(name1, name1sc),
1082                          stopname),
1083                        M(14));
1084          let ans = unfold_test_sc(chain,EMPTY_CTXT,&mut t);
1085          assert_eq! (marksof (ans, stopname, &t), vec!(9)); }
1086     }
1087
1088
1089     #[test] fn resolve_tests () {
1090         let a = 40;
1091         let mut t = new_sctable_internal();
1092         let mut rt = HashMap::new();
1093         // - ctxt is MT
1094         assert_eq!(resolve_internal(id(a,EMPTY_CTXT),&mut t, &mut rt),a);
1095         // - simple ignored marks
1096         { let sc = unfold_marks(vec!(1,2,3),EMPTY_CTXT,&mut t);
1097          assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt),a);}
1098         // - orthogonal rename where names don't match
1099         { let sc = unfold_test_sc(vec!(R(id(50,EMPTY_CTXT),51),M(12)),EMPTY_CTXT,&mut t);
1100          assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt),a);}
1101         // - rename where names do match, but marks don't
1102         { let sc1 = new_mark_internal(1,EMPTY_CTXT,&mut t);
1103          let sc = unfold_test_sc(vec!(R(id(a,sc1),50),
1104                                    M(1),
1105                                    M(2)),
1106                                  EMPTY_CTXT,&mut t);
1107         assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt), a);}
1108         // - rename where names and marks match
1109         { let sc1 = unfold_test_sc(vec!(M(1),M(2)),EMPTY_CTXT,&mut t);
1110          let sc = unfold_test_sc(vec!(R(id(a,sc1),50),M(1),M(2)),EMPTY_CTXT,&mut t);
1111          assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt), 50); }
1112         // - rename where names and marks match by literal sharing
1113         { let sc1 = unfold_test_sc(vec!(M(1),M(2)),EMPTY_CTXT,&mut t);
1114          let sc = unfold_test_sc(vec!(R(id(a,sc1),50)),sc1,&mut t);
1115          assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt), 50); }
1116         // - two renames of the same var.. can only happen if you use
1117         // local-expand to prevent the inner binding from being renamed
1118         // during the rename-pass caused by the first:
1119         println!("about to run bad test");
1120         { let sc = unfold_test_sc(vec!(R(id(a,EMPTY_CTXT),50),
1121                                     R(id(a,EMPTY_CTXT),51)),
1122                                   EMPTY_CTXT,&mut t);
1123          assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt), 51); }
1124         // the simplest double-rename:
1125         { let a_to_a50 = new_rename_internal(id(a,EMPTY_CTXT),50,EMPTY_CTXT,&mut t);
1126          let a50_to_a51 = new_rename_internal(id(a,a_to_a50),51,a_to_a50,&mut t);
1127          assert_eq!(resolve_internal(id(a,a50_to_a51),&mut t, &mut rt),51);
1128          // mark on the outside doesn't stop rename:
1129          let sc = new_mark_internal(9,a50_to_a51,&mut t);
1130          assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt),51);
1131          // but mark on the inside does:
1132          let a50_to_a51_b = unfold_test_sc(vec!(R(id(a,a_to_a50),51),
1133                                               M(9)),
1134                                            a_to_a50,
1135                                            &mut t);
1136          assert_eq!(resolve_internal(id(a,a50_to_a51_b),&mut t, &mut rt),50);}
1137     }
1138
1139     #[test] fn mtwt_resolve_test(){
1140         let a = 40;
1141         assert_eq!(mtwt_resolve(id(a,EMPTY_CTXT)),a);
1142     }
1143
1144
1145     #[test] fn hashing_tests () {
1146         let mut t = new_sctable_internal();
1147         assert_eq!(new_mark_internal(12,EMPTY_CTXT,&mut t),2);
1148         assert_eq!(new_mark_internal(13,EMPTY_CTXT,&mut t),3);
1149         // using the same one again should result in the same index:
1150         assert_eq!(new_mark_internal(12,EMPTY_CTXT,&mut t),2);
1151         // I'm assuming that the rename table will behave the same....
1152     }
1153
1154     #[test] fn resolve_table_hashing_tests() {
1155         let mut t = new_sctable_internal();
1156         let mut rt = HashMap::new();
1157         assert_eq!(rt.len(),0);
1158         resolve_internal(id(30,EMPTY_CTXT),&mut t, &mut rt);
1159         assert_eq!(rt.len(),1);
1160         resolve_internal(id(39,EMPTY_CTXT),&mut t, &mut rt);
1161         assert_eq!(rt.len(),2);
1162         resolve_internal(id(30,EMPTY_CTXT),&mut t, &mut rt);
1163         assert_eq!(rt.len(),2);
1164     }
1165
1166 }