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