src/libsyntax/ext/expand.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::{Block, Crate, DeclLocal, Expr_, ExprMac, SyntaxContext};
  12 use ast::{Local, Ident, mac_invoc_tt};
  13 use ast::{item_mac, Mrk, Stmt, StmtDecl, StmtMac, StmtExpr, StmtSemi};
  14 use ast::{token_tree};
  15 use ast;
  16 use ast_util::{mtwt_outer_mark, new_rename, new_mark};
  17 use ext::build::AstBuilder;
  18 use attr;
  19 use attr::AttrMetaMethods;
  20 use codemap;
  21 use codemap::{Span, Spanned, ExpnInfo, NameAndSpan};
  22 use ext::base::*;
  23 use fold::*;
  24 use opt_vec;
  25 use parse;
  26 use parse::{parse_item_from_source_str};
  27 use parse::token;
  28 use parse::token::{fresh_mark, fresh_name, ident_to_str, intern};
  29 use visit;
  30 use visit::Visitor;
  31
  32 use std::vec;
  33
  34 pub fn expand_expr(extsbox: @mut SyntaxEnv,
  35                    cx: @ExtCtxt,
  36                    e: @ast::Expr,
  37                    fld: &MacroExpander)
  38                    -> @ast::Expr {
  39     match e.node {
  40         // expr_mac should really be expr_ext or something; it's the
  41         // entry-point for all syntax extensions.
  42         ExprMac(ref mac) => {
  43             match (*mac).node {
  44                 // it would almost certainly be cleaner to pass the whole
  45                 // macro invocation in, rather than pulling it apart and
  46                 // marking the tts and the ctxt separately. This also goes
  47                 // for the other three macro invocation chunks of code
  48                 // in this file.
  49                 // Token-tree macros:
  50                 mac_invoc_tt(ref pth, ref tts, ctxt) => {
  51                     if (pth.segments.len() > 1u) {
  52                         cx.span_fatal(
  53                             pth.span,
  54                             format!("expected macro name without module \
  55                                   separators"));
  56                     }
  57                     let extname = &pth.segments[0].identifier;
  58                     let extnamestr = ident_to_str(extname);
  59                     // leaving explicit deref here to highlight unbox op:
  60                     match (*extsbox).find(&extname.name) {
  61                         None => {
  62                             cx.span_fatal(
  63                                 pth.span,
  64                                 format!("macro undefined: '{}'", extnamestr))
  65                         }
  66                         Some(@SE(NormalTT(expandfun, exp_span))) => {
  67                             cx.bt_push(ExpnInfo {
  68                                 call_site: e.span,
  69                                 callee: NameAndSpan {
  70                                     name: extnamestr,
  71                                     span: exp_span,
  72                                 },
  73                             });
  74                             let fm = fresh_mark();
  75                             // mark before:
  76                             let marked_before = mark_tts(*tts,fm);
  77                             let marked_ctxt = new_mark(fm, ctxt);
  78
  79                             // The span that we pass to the expanders we want to
  80                             // be the root of the call stack. That's the most
  81                             // relevant span and it's the actual invocation of
  82                             // the macro.
  83                             let mac_span = original_span(cx);
  84
  85                             let expanded =
  86                                 match expandfun.expand(cx,
  87                                                        mac_span.call_site,
  88                                                        marked_before,
  89                                                        marked_ctxt) {
  90                                     MRExpr(e) => e,
  91                                     MRAny(any_macro) => any_macro.make_expr(),
  92                                     _ => {
  93                                         cx.span_fatal(
  94                                             pth.span,
  95                                             format!(
  96                                                 "non-expr macro in expr pos: {}",
  97                                                 extnamestr
  98                                             )
  99                                         )
 100                                     }
 101                                 };
 102                             // mark after:
 103                             let marked_after = mark_expr(expanded,fm);
 104
 105                             // Keep going, outside-in.
 106                             //
 107                             // XXX(pcwalton): Is it necessary to clone the
 108                             // node here?
 109                             let fully_expanded =
 110                                 fld.fold_expr(marked_after).node.clone();
 111                             cx.bt_pop();
 112
 113                             @ast::Expr {
 114                                 id: ast::DUMMY_NODE_ID,
 115                                 node: fully_expanded,
 116                                 span: e.span,
 117                             }
 118                         }
 119                         _ => {
 120                             cx.span_fatal(
 121                                 pth.span,
 122                                 format!("'{}' is not a tt-style macro", extnamestr)
 123                             )
 124                         }
 125                     }
 126                 }
 127             }
 128         }
 129
 130         // Desugar expr_for_loop
 131         // From: `['<ident>:] for <src_pat> in <src_expr> <src_loop_block>`
 132         // FIXME #6993 : change type of opt_ident to Option<Name>
 133         ast::ExprForLoop(src_pat, src_expr, ref src_loop_block, opt_ident) => {
 134             // Expand any interior macros etc.
 135             // NB: we don't fold pats yet. Curious.
 136             let src_expr = fld.fold_expr(src_expr).clone();
 137             let src_loop_block = fld.fold_block(src_loop_block).clone();
 138
 139             let span = e.span;
 140
 141             pub fn mk_expr(_: @ExtCtxt, span: Span, node: Expr_)
 142                            -> @ast::Expr {
 143                 @ast::Expr {
 144                     id: ast::DUMMY_NODE_ID,
 145                     node: node,
 146                     span: span,
 147                 }
 148             }
 149
 150             fn mk_block(_: @ExtCtxt,
 151                         stmts: &[@ast::Stmt],
 152                         expr: Option<@ast::Expr>,
 153                         span: Span)
 154                         -> ast::Block {
 155                 ast::Block {
 156                     view_items: ~[],
 157                     stmts: stmts.to_owned(),
 158                     expr: expr,
 159                     id: ast::DUMMY_NODE_ID,
 160                     rules: ast::DefaultBlock,
 161                     span: span,
 162                 }
 163             }
 164
 165             fn mk_simple_path(ident: ast::Ident, span: Span) -> ast::Path {
 166                 ast::Path {
 167                     span: span,
 168                     global: false,
 169                     segments: ~[
 170                         ast::PathSegment {
 171                             identifier: ident,
 172                             lifetime: None,
 173                             types: opt_vec::Empty,
 174                         }
 175                     ],
 176                 }
 177             }
 178
 179             // to:
 180             //
 181             // {
 182             //   let _i = &mut <src_expr>;
 183             //   ['<ident>:] loop {
 184             //       match i.next() {
 185             //           None => break,
 186             //           Some(<src_pat>) => <src_loop_block>
 187             //       }
 188             //   }
 189             // }
 190
 191             let local_ident = token::gensym_ident("i");
 192             let next_ident = cx.ident_of("next");
 193             let none_ident = cx.ident_of("None");
 194
 195             let local_path = cx.path_ident(span, local_ident);
 196             let some_path = cx.path_ident(span, cx.ident_of("Some"));
 197
 198             // `let i = &mut <src_expr>`
 199             let iter_decl_stmt = cx.stmt_let(span, false, local_ident,
 200                                              cx.expr_mut_addr_of(span, src_expr));
 201
 202             // `None => break ['<ident>];`
 203             let none_arm = {
 204                 // FIXME #6993: this map goes away:
 205                 let break_expr = cx.expr(span, ast::ExprBreak(opt_ident.map(|x| x.name)));
 206                 let none_pat = cx.pat_ident(span, none_ident);
 207                 cx.arm(span, ~[none_pat], break_expr)
 208             };
 209
 210             // `Some(<src_pat>) => <src_loop_block>`
 211             let some_arm =
 212                 cx.arm(span,
 213                        ~[cx.pat_enum(span, some_path, ~[src_pat])],
 214                        cx.expr_block(src_loop_block));
 215
 216             // `match i.next() { ... }`
 217             let match_expr = {
 218                 let next_call_expr =
 219                     cx.expr_method_call(span, cx.expr_path(local_path), next_ident, ~[]);
 220
 221                 cx.expr_match(span, next_call_expr, ~[none_arm, some_arm])
 222             };
 223
 224             // ['ident:] loop { ... }
 225             let loop_expr = cx.expr(span,
 226                                     ast::ExprLoop(cx.block_expr(match_expr), opt_ident));
 227
 228             // `{ let ... ;  loop { ... } }`
 229             let block = cx.block(span,
 230                                  ~[iter_decl_stmt],
 231                                  Some(loop_expr));
 232
 233             @ast::Expr {
 234                 id: ast::DUMMY_NODE_ID,
 235                 node: ast::ExprBlock(block),
 236                 span: span,
 237             }
 238         }
 239
 240         _ => noop_fold_expr(e, fld)
 241     }
 242 }
 243
 244 // This is a secondary mechanism for invoking syntax extensions on items:
 245 // "decorator" attributes, such as #[auto_encode]. These are invoked by an
 246 // attribute prefixing an item, and are interpreted by feeding the item
 247 // through the named attribute _as a syntax extension_ and splicing in the
 248 // resulting item vec into place in favour of the decorator. Note that
 249 // these do _not_ work for macro extensions, just ItemDecorator ones.
 250 //
 251 // NB: there is some redundancy between this and expand_item, below, and
 252 // they might benefit from some amount of semantic and language-UI merger.
 253 pub fn expand_mod_items(extsbox: @mut SyntaxEnv,
 254                         cx: @ExtCtxt,
 255                         module_: &ast::_mod,
 256                         fld: &MacroExpander)
 257                         -> ast::_mod {
 258     // Fold the contents first:
 259     let module_ = noop_fold_mod(module_, fld);
 260
 261     // For each item, look through the attributes.  If any of them are
 262     // decorated with "item decorators", then use that function to transform
 263     // the item into a new set of items.
 264     let new_items = do vec::flat_map(module_.items) |item| {
 265         do item.attrs.rev_iter().fold(~[*item]) |items, attr| {
 266             let mname = attr.name();
 267
 268             match (*extsbox).find(&intern(mname)) {
 269               Some(@SE(ItemDecorator(dec_fn))) => {
 270                   cx.bt_push(ExpnInfo {
 271                       call_site: attr.span,
 272                       callee: NameAndSpan {
 273                           name: mname,
 274                           span: None
 275                       }
 276                   });
 277                   let r = dec_fn(cx, attr.span, attr.node.value, items);
 278                   cx.bt_pop();
 279                   r
 280               },
 281               _ => items,
 282             }
 283         }
 284     };
 285
 286     ast::_mod {
 287         items: new_items,
 288         ..module_
 289     }
 290 }
 291
 292 // eval $e with a new exts frame:
 293 macro_rules! with_exts_frame (
 294     ($extsboxexpr:expr,$macros_escape:expr,$e:expr) =>
 295     ({let extsbox = $extsboxexpr;
 296       let oldexts = *extsbox;
 297       *extsbox = oldexts.push_frame();
 298       extsbox.insert(intern(special_block_name),
 299                      @BlockInfo(BlockInfo{macros_escape:$macros_escape,pending_renames:@mut ~[]}));
 300       let result = $e;
 301       *extsbox = oldexts;
 302       result
 303      })
 304 )
 305
 306 static special_block_name : &'static str = " block";
 307
 308 // When we enter a module, record it, for the sake of `module!`
 309 pub fn expand_item(extsbox: @mut SyntaxEnv,
 310                    cx: @ExtCtxt,
 311                    it: @ast::item,
 312                    fld: &MacroExpander)
 313                    -> Option<@ast::item> {
 314     match it.node {
 315         ast::item_mac(*) => expand_item_mac(extsbox, cx, it, fld),
 316         ast::item_mod(_) | ast::item_foreign_mod(_) => {
 317             cx.mod_push(it.ident);
 318             let macro_escape = contains_macro_escape(it.attrs);
 319             let result = with_exts_frame!(extsbox,
 320                                           macro_escape,
 321                                           noop_fold_item(it, fld));
 322             cx.mod_pop();
 323             result
 324         },
 325         _ => noop_fold_item(it, fld)
 326     }
 327 }
 328
 329 // does this attribute list contain "macro_escape" ?
 330 pub fn contains_macro_escape(attrs: &[ast::Attribute]) -> bool {
 331     attr::contains_name(attrs, "macro_escape")
 332 }
 333
 334 // Support for item-position macro invocations, exactly the same
 335 // logic as for expression-position macro invocations.
 336 pub fn expand_item_mac(extsbox: @mut SyntaxEnv,
 337                        cx: @ExtCtxt,
 338                        it: @ast::item,
 339                        fld: &MacroExpander)
 340                        -> Option<@ast::item> {
 341     let (pth, tts, ctxt) = match it.node {
 342         item_mac(codemap::Spanned {
 343             node: mac_invoc_tt(ref pth, ref tts, ctxt),
 344             _
 345         }) => {
 346             (pth, (*tts).clone(), ctxt)
 347         }
 348         _ => cx.span_bug(it.span, "invalid item macro invocation")
 349     };
 350
 351     let extname = &pth.segments[0].identifier;
 352     let extnamestr = ident_to_str(extname);
 353     let fm = fresh_mark();
 354     let expanded = match (*extsbox).find(&extname.name) {
 355         None => cx.span_fatal(pth.span,
 356                               format!("macro undefined: '{}!'", extnamestr)),
 357
 358         Some(@SE(NormalTT(expander, span))) => {
 359             if it.ident.name != parse::token::special_idents::invalid.name {
 360                 cx.span_fatal(pth.span,
 361                               format!("macro {}! expects no ident argument, \
 362                                     given '{}'", extnamestr,
 363                                    ident_to_str(&it.ident)));
 364             }
 365             cx.bt_push(ExpnInfo {
 366                 call_site: it.span,
 367                 callee: NameAndSpan {
 368                     name: extnamestr,
 369                     span: span
 370                 }
 371             });
 372             // mark before expansion:
 373             let marked_before = mark_tts(tts,fm);
 374             let marked_ctxt = new_mark(fm,ctxt);
 375             expander.expand(cx, it.span, marked_before, marked_ctxt)
 376         }
 377         Some(@SE(IdentTT(expander, span))) => {
 378             if it.ident.name == parse::token::special_idents::invalid.name {
 379                 cx.span_fatal(pth.span,
 380                               format!("macro {}! expects an ident argument",
 381                                    extnamestr));
 382             }
 383             cx.bt_push(ExpnInfo {
 384                 call_site: it.span,
 385                 callee: NameAndSpan {
 386                     name: extnamestr,
 387                     span: span
 388                 }
 389             });
 390             // mark before expansion:
 391             let marked_tts = mark_tts(tts,fm);
 392             let marked_ctxt = new_mark(fm,ctxt);
 393             expander.expand(cx, it.span, it.ident, marked_tts, marked_ctxt)
 394         }
 395         _ => cx.span_fatal(
 396             it.span, format!("{}! is not legal in item position", extnamestr))
 397     };
 398
 399     let maybe_it = match expanded {
 400         MRItem(it) => {
 401             mark_item(it,fm)
 402                 .and_then(|i| fld.fold_item(i))
 403         }
 404         MRExpr(_) => {
 405             cx.span_fatal(pth.span, format!("expr macro in item position: {}", extnamestr))
 406         }
 407         MRAny(any_macro) => {
 408             any_macro.make_item()
 409                      .and_then(|i| mark_item(i,fm))
 410                      .and_then(|i| fld.fold_item(i))
 411         }
 412         MRDef(ref mdef) => {
 413             // yikes... no idea how to apply the mark to this. I'm afraid
 414             // we're going to have to wait-and-see on this one.
 415             insert_macro(*extsbox,intern(mdef.name), @SE((*mdef).ext));
 416             None
 417         }
 418     };
 419     cx.bt_pop();
 420     return maybe_it;
 421 }
 422
 423
 424 // insert a macro into the innermost frame that doesn't have the
 425 // macro_escape tag.
 426 fn insert_macro(exts: SyntaxEnv, name: ast::Name, transformer: @Transformer) {
 427     let is_non_escaping_block =
 428         |t : &@Transformer| -> bool{
 429         match t {
 430             &@BlockInfo(BlockInfo {macros_escape:false,_}) => true,
 431             &@BlockInfo(BlockInfo {_}) => false,
 432             _ => fail!("special identifier {:?} was bound to a non-BlockInfo",
 433                         special_block_name)
 434         }
 435     };
 436     exts.insert_into_frame(name,transformer,intern(special_block_name),
 437                            is_non_escaping_block)
 438 }
 439
 440 // expand a stmt
 441 pub fn expand_stmt(extsbox: @mut SyntaxEnv,
 442                    cx: @ExtCtxt,
 443                    s: &Stmt,
 444                    fld: &MacroExpander)
 445                    -> Option<@Stmt> {
 446     // why the copying here and not in expand_expr?
 447     // looks like classic changed-in-only-one-place
 448     let (pth, tts, semi, ctxt) = match s.node {
 449         StmtMac(ref mac, semi) => {
 450             match mac.node {
 451                 mac_invoc_tt(ref pth, ref tts, ctxt) => {
 452                     (pth, (*tts).clone(), semi, ctxt)
 453                 }
 454             }
 455         }
 456         _ => return expand_non_macro_stmt(*extsbox, s, fld)
 457     };
 458     if (pth.segments.len() > 1u) {
 459         cx.span_fatal(pth.span,
 460                       "expected macro name without module separators");
 461     }
 462     let extname = &pth.segments[0].identifier;
 463     let extnamestr = ident_to_str(extname);
 464     let fully_expanded: @ast::Stmt = match (*extsbox).find(&extname.name) {
 465         None => {
 466             cx.span_fatal(pth.span, format!("macro undefined: '{}'", extnamestr))
 467         }
 468
 469         Some(@SE(NormalTT(expandfun, exp_span))) => {
 470             cx.bt_push(ExpnInfo {
 471                 call_site: s.span,
 472                 callee: NameAndSpan {
 473                     name: extnamestr,
 474                     span: exp_span,
 475                 }
 476             });
 477             let fm = fresh_mark();
 478             // mark before expansion:
 479             let marked_tts = mark_tts(tts,fm);
 480             let marked_ctxt = new_mark(fm,ctxt);
 481
 482             // See the comment in expand_expr for why we want the original span,
 483             // not the current mac.span.
 484             let mac_span = original_span(cx);
 485
 486             let expanded = match expandfun.expand(cx,
 487                                                   mac_span.call_site,
 488                                                   marked_tts,
 489                                                   marked_ctxt) {
 490                 MRExpr(e) => {
 491                     @codemap::Spanned {
 492                         node: StmtExpr(e, ast::DUMMY_NODE_ID),
 493                         span: e.span,
 494                     }
 495                 }
 496                 MRAny(any_macro) => any_macro.make_stmt(),
 497                 _ => cx.span_fatal(
 498                     pth.span,
 499                     format!("non-stmt macro in stmt pos: {}", extnamestr))
 500             };
 501             let marked_after = mark_stmt(expanded,fm);
 502
 503             // Keep going, outside-in.
 504             let fully_expanded = match fld.fold_stmt(marked_after) {
 505                 Some(stmt) => {
 506                     let fully_expanded = &stmt.node;
 507                     cx.bt_pop();
 508                     @Spanned {
 509                         span: stmt.span,
 510                         node: (*fully_expanded).clone(),
 511                     }
 512                 }
 513                 None => {
 514                     cx.span_fatal(pth.span,
 515                                   "macro didn't expand to a statement")
 516                 }
 517             };
 518
 519             fully_expanded
 520         }
 521
 522         _ => {
 523             cx.span_fatal(pth.span,
 524                           format!("'{}' is not a tt-style macro", extnamestr))
 525         }
 526     };
 527
 528     match fully_expanded.node {
 529         StmtExpr(e, stmt_id) if semi => {
 530             Some(@Spanned {
 531                 span: fully_expanded.span,
 532                 node: StmtSemi(e, stmt_id),
 533             })
 534         }
 535         _ => Some(fully_expanded), /* might already have a semi */
 536     }
 537 }
 538
 539 // expand a non-macro stmt. this is essentially the fallthrough for
 540 // expand_stmt, above.
 541 fn expand_non_macro_stmt(exts: SyntaxEnv, s: &Stmt, fld: &MacroExpander)
 542                          -> Option<@Stmt> {
 543     // is it a let?
 544     match s.node {
 545         StmtDecl(@Spanned {
 546             node: DeclLocal(ref local),
 547             span: stmt_span
 548         },
 549         node_id) => {
 550             let block_info = get_block_info(exts);
 551             let pending_renames = block_info.pending_renames;
 552
 553             // take it apart:
 554             let @Local{is_mutbl:is_mutbl,
 555                        ty:_,
 556                        pat:pat,
 557                        init:init,
 558                        id:id,
 559                        span:span
 560                       } = *local;
 561             // types can't be copied automatically because of the owned ptr in ty_tup...
 562             let ty = local.ty.clone();
 563             // expand the pat (it might contain exprs... #:(o)>
 564             let expanded_pat = fld.fold_pat(pat);
 565             // find the pat_idents in the pattern:
 566             // oh dear heaven... this is going to include the enum names, as well....
 567             // ... but that should be okay, as long as the new names are gensyms
 568             // for the old ones.
 569             let idents = @mut ~[];
 570             let name_finder = new_name_finder(idents);
 571             name_finder.visit_pat(expanded_pat,());
 572             // generate fresh names, push them to a new pending list
 573             let new_pending_renames = @mut ~[];
 574             for ident in idents.iter() {
 575                 let new_name = fresh_name(ident);
 576                 new_pending_renames.push((*ident,new_name));
 577             }
 578             let rename_fld = renames_to_fold(new_pending_renames);
 579             // rewrite the pattern using the new names (the old ones
 580             // have already been applied):
 581             let rewritten_pat = rename_fld.fold_pat(expanded_pat);
 582             // add them to the existing pending renames:
 583             for pr in new_pending_renames.iter() {pending_renames.push(*pr)}
 584             // also, don't forget to expand the init:
 585             let new_init_opt = init.map(|e| fld.fold_expr(e));
 586             let rewritten_local =
 587                 @Local {
 588                     is_mutbl: is_mutbl,
 589                     ty: ty,
 590                     pat: rewritten_pat,
 591                     init: new_init_opt,
 592                     id: id,
 593                     span: span,
 594                 };
 595             Some(@Spanned {
 596                 node: StmtDecl(@Spanned {
 597                         node: DeclLocal(rewritten_local),
 598                         span: stmt_span
 599                     },
 600                     node_id),
 601                 span: span
 602             })
 603         },
 604         _ => noop_fold_stmt(s, fld),
 605     }
 606 }
 607
 608 // a visitor that extracts the pat_ident paths
 609 // from a given thingy and puts them in a mutable
 610 // array (passed in to the traversal)
 611 #[deriving(Clone)]
 612 struct NewNameFinderContext {
 613     ident_accumulator: @mut ~[ast::Ident],
 614 }
 615
 616 impl Visitor<()> for NewNameFinderContext {
 617     fn visit_pat(&mut self, pattern: @ast::Pat, _: ()) {
 618         match *pattern {
 619             // we found a pat_ident!
 620             ast::Pat {
 621                 id: _,
 622                 node: ast::PatIdent(_, ref path, ref inner),
 623                 span: _
 624             } => {
 625                 match path {
 626                     // a path of length one:
 627                     &ast::Path {
 628                         global: false,
 629                         span: _,
 630                         segments: [
 631                             ast::PathSegment {
 632                                 identifier: id,
 633                                 lifetime: _,
 634                                 types: _
 635                             }
 636                         ]
 637                     } => self.ident_accumulator.push(id),
 638                     // I believe these must be enums...
 639                     _ => ()
 640                 }
 641                 // visit optional subpattern of pat_ident:
 642                 for subpat in inner.iter() {
 643                     self.visit_pat(*subpat, ())
 644                 }
 645             }
 646             // use the default traversal for non-pat_idents
 647             _ => visit::walk_pat(self, pattern, ())
 648         }
 649     }
 650
 651     fn visit_ty(&mut self, typ: &ast::Ty, _: ()) {
 652         visit::walk_ty(self, typ, ())
 653     }
 654
 655 }
 656
 657 // a visitor that extracts the paths
 658 // from a given thingy and puts them in a mutable
 659 // array (passed in to the traversal)
 660 #[deriving(Clone)]
 661 struct NewPathExprFinderContext {
 662     path_accumulator: @mut ~[ast::Path],
 663 }
 664
 665 impl Visitor<()> for NewPathExprFinderContext {
 666
 667     fn visit_expr(&mut self, expr: @ast::Expr, _: ()) {
 668         match *expr {
 669             ast::Expr{id:_,span:_,node:ast::ExprPath(ref p)} => {
 670                 self.path_accumulator.push(p.clone());
 671                 // not calling visit_path, should be fine.
 672             }
 673             _ => visit::walk_expr(self,expr,())
 674         }
 675     }
 676
 677     fn visit_ty(&mut self, typ: &ast::Ty, _: ()) {
 678         visit::walk_ty(self, typ, ())
 679     }
 680
 681 }
 682
 683 // return a visitor that extracts the pat_ident paths
 684 // from a given thingy and puts them in a mutable
 685 // array (passed in to the traversal)
 686 pub fn new_name_finder(idents: @mut ~[ast::Ident]) -> @mut Visitor<()> {
 687     let context = @mut NewNameFinderContext {
 688         ident_accumulator: idents,
 689     };
 690     context as @mut Visitor<()>
 691 }
 692
 693 // return a visitor that extracts the paths
 694 // from a given pattern and puts them in a mutable
 695 // array (passed in to the traversal)
 696 pub fn new_path_finder(paths: @mut ~[ast::Path]) -> @mut Visitor<()> {
 697     let context = @mut NewPathExprFinderContext {
 698         path_accumulator: paths,
 699     };
 700     context as @mut Visitor<()>
 701 }
 702
 703 // expand a block. pushes a new exts_frame, then calls expand_block_elts
 704 pub fn expand_block(extsbox: @mut SyntaxEnv,
 705                     _: @ExtCtxt,
 706                     blk: &Block,
 707                     fld: &MacroExpander)
 708                     -> Block {
 709     // see note below about treatment of exts table
 710     with_exts_frame!(extsbox,false,
 711                      expand_block_elts(*extsbox, blk, fld))
 712 }
 713
 714 // expand the elements of a block.
 715 pub fn expand_block_elts(exts: SyntaxEnv, b: &Block, fld: &MacroExpander)
 716                          -> Block {
 717     let block_info = get_block_info(exts);
 718     let pending_renames = block_info.pending_renames;
 719     let rename_fld = renames_to_fold(pending_renames);
 720     let new_view_items = b.view_items.map(|x| fld.fold_view_item(x));
 721     let mut new_stmts = ~[];
 722     for x in b.stmts.iter() {
 723         match fld.fold_stmt(mustbesome(rename_fld.fold_stmt(*x))) {
 724             Some(s) => new_stmts.push(s),
 725             None => ()
 726         }
 727     }
 728     let new_expr = b.expr.map(|x| fld.fold_expr(rename_fld.fold_expr(x)));
 729     Block{
 730         view_items: new_view_items,
 731         stmts: new_stmts,
 732         expr: new_expr,
 733         id: fld.new_id(b.id),
 734         rules: b.rules,
 735         span: b.span,
 736     }
 737 }
 738
 739 // rename_fold should never return "None".
 740 // (basically, just .get() with a better message...)
 741 fn mustbesome<T>(val : Option<T>) -> T {
 742     match val {
 743         Some(v) => v,
 744         None => fail!("rename_fold returned None")
 745     }
 746 }
 747
 748 // get the (innermost) BlockInfo from an exts stack
 749 fn get_block_info(exts : SyntaxEnv) -> BlockInfo {
 750     match exts.find_in_topmost_frame(&intern(special_block_name)) {
 751         Some(@BlockInfo(bi)) => bi,
 752         _ => fail!("special identifier {:?} was bound to a non-BlockInfo",
 753                     @" block")
 754     }
 755 }
 756
 757 struct IdentRenamer {
 758     renames: @mut ~[(ast::Ident,ast::Name)],
 759 }
 760
 761 impl ast_fold for IdentRenamer {
 762     fn fold_ident(&self, id: ast::Ident) -> ast::Ident {
 763         let new_ctxt = self.renames.iter().fold(id.ctxt, |ctxt, &(from, to)| {
 764             new_rename(from, to, ctxt)
 765         });
 766         ast::Ident {
 767             name: id.name,
 768             ctxt: new_ctxt,
 769         }
 770     }
 771 }
 772
 773 // given a mutable list of renames, return a tree-folder that applies those
 774 // renames.
 775 pub fn renames_to_fold(renames: @mut ~[(ast::Ident,ast::Name)]) -> @ast_fold {
 776     @IdentRenamer {
 777         renames: renames,
 778     } as @ast_fold
 779 }
 780
 781 // perform a bunch of renames
 782 fn apply_pending_renames(folder : @ast_fold, stmt : ast::Stmt) -> @ast::Stmt {
 783     match folder.fold_stmt(&stmt) {
 784         Some(s) => s,
 785         None => fail!("renaming of stmt produced None")
 786     }
 787 }
 788
 789
 790
 791 pub fn new_span(cx: @ExtCtxt, sp: Span) -> Span {
 792     /* this discards information in the case of macro-defining macros */
 793     Span {
 794         lo: sp.lo,
 795         hi: sp.hi,
 796         expn_info: cx.backtrace(),
 797     }
 798 }
 799
 800 // FIXME (#2247): this is a moderately bad kludge to inject some macros into
 801 // the default compilation environment in that it injects strings, rather than
 802 // syntax elements.
 803
 804 pub fn std_macros() -> @str {
 805     return
 806 @"mod __std_macros {
 807     #[macro_escape];
 808     #[doc(hidden)];
 809
 810     macro_rules! ignore (($($x:tt)*) => (()))
 811
 812     macro_rules! log(
 813         ($lvl:expr, $($arg:tt)+) => ({
 814             let lvl = $lvl;
 815             if lvl <= __log_level() {
 816                 format_args!(|args| {
 817                     ::std::logging::log(lvl, args)
 818                 }, $($arg)+)
 819             }
 820         })
 821     )
 822     macro_rules! error( ($($arg:tt)*) => (log!(1u32, $($arg)*)) )
 823     macro_rules! warn ( ($($arg:tt)*) => (log!(2u32, $($arg)*)) )
 824     macro_rules! info ( ($($arg:tt)*) => (log!(3u32, $($arg)*)) )
 825     macro_rules! debug( ($($arg:tt)*) => (
 826         if cfg!(not(ndebug)) { log!(4u32, $($arg)*) }
 827     ))
 828
 829     macro_rules! fail(
 830         () => (
 831             fail!(\"explicit failure\")
 832         );
 833         ($fmt:expr) => (
 834             ::std::sys::FailWithCause::fail_with($fmt, file!(), line!())
 835         );
 836         ($fmt:expr, $($arg:tt)*) => (
 837             ::std::sys::FailWithCause::fail_with(format!($fmt, $($arg)*), file!(), line!())
 838         )
 839     )
 840
 841     macro_rules! assert(
 842         ($cond:expr) => {
 843             if !$cond {
 844                 ::std::sys::FailWithCause::fail_with(
 845                     \"assertion failed: \" + stringify!($cond), file!(), line!())
 846             }
 847         };
 848         ($cond:expr, $msg:expr) => {
 849             if !$cond {
 850                 ::std::sys::FailWithCause::fail_with($msg, file!(), line!())
 851             }
 852         };
 853         ($cond:expr, $( $arg:expr ),+) => {
 854             if !$cond {
 855                 ::std::sys::FailWithCause::fail_with(format!( $($arg),+ ), file!(), line!())
 856             }
 857         }
 858     )
 859
 860     macro_rules! assert_eq (
 861         ($given:expr , $expected:expr) => (
 862             {
 863                 let given_val = &($given);
 864                 let expected_val = &($expected);
 865                 // check both directions of equality....
 866                 if !((*given_val == *expected_val) &&
 867                      (*expected_val == *given_val)) {
 868                     fail!(\"assertion failed: `(left == right) && (right == \
 869                              left)` (left: `{:?}`, right: `{:?}`)\",
 870                            *given_val, *expected_val);
 871                 }
 872             }
 873         )
 874     )
 875
 876     macro_rules! assert_approx_eq (
 877         ($given:expr , $expected:expr) => (
 878             {
 879                 use std::cmp::ApproxEq;
 880
 881                 let given_val = $given;
 882                 let expected_val = $expected;
 883                 // check both directions of equality....
 884                 if !(
 885                     given_val.approx_eq(&expected_val) &&
 886                     expected_val.approx_eq(&given_val)
 887                 ) {
 888                     fail!(\"left: {:?} does not approximately equal right: {:?}\",
 889                            given_val, expected_val);
 890                 }
 891             }
 892         );
 893         ($given:expr , $expected:expr , $epsilon:expr) => (
 894             {
 895                 use std::cmp::ApproxEq;
 896
 897                 let given_val = $given;
 898                 let expected_val = $expected;
 899                 let epsilon_val = $epsilon;
 900                 // check both directions of equality....
 901                 if !(
 902                     given_val.approx_eq_eps(&expected_val, &epsilon_val) &&
 903                     expected_val.approx_eq_eps(&given_val, &epsilon_val)
 904                 ) {
 905                     fail!(\"left: {:?} does not approximately equal right: \
 906                              {:?} with epsilon: {:?}\",
 907                           given_val, expected_val, epsilon_val);
 908                 }
 909             }
 910         )
 911     )
 912
 913     // FIXME(#6266): change the /* to /** when attributes are supported on macros
 914     // (Though even then—is it going to work according to the clear intent here?)
 915     /*
 916     A utility macro for indicating unreachable code. It will fail if
 917     executed. This is occasionally useful to put after loops that never
 918     terminate normally, but instead directly return from a function.
 919
 920     # Example
 921
 922     ```rust
 923     fn choose_weighted_item(v: &[Item]) -> Item {
 924         assert!(!v.is_empty());
 925         let mut so_far = 0u;
 926         for v.each |item| {
 927             so_far += item.weight;
 928             if so_far > 100 {
 929                 return item;
 930             }
 931         }
 932         // The above loop always returns, so we must hint to the
 933         // type checker that it isn't possible to get down here
 934         unreachable!();
 935     }
 936     ```
 937
 938     */
 939     macro_rules! unreachable (() => (
 940         fail!(\"internal error: entered unreachable code\");
 941     ))
 942
 943     macro_rules! condition (
 944
 945         { pub $c:ident: $input:ty -> $out:ty; } => {
 946
 947             pub mod $c {
 948                 #[allow(unused_imports)];
 949                 #[allow(non_uppercase_statics)];
 950                 #[allow(missing_doc)];
 951
 952                 use super::*;
 953
 954                 local_data_key!(key: @::std::condition::Handler<$input, $out>)
 955
 956                 pub static cond :
 957                     ::std::condition::Condition<$input,$out> =
 958                     ::std::condition::Condition {
 959                         name: stringify!($c),
 960                         key: key
 961                     };
 962             }
 963         };
 964
 965         { $c:ident: $input:ty -> $out:ty; } => {
 966
 967             mod $c {
 968                 #[allow(unused_imports)];
 969                 #[allow(non_uppercase_statics)];
 970
 971                 use super::*;
 972
 973                 local_data_key!(key: @::std::condition::Handler<$input, $out>)
 974
 975                 pub static cond :
 976                     ::std::condition::Condition<$input,$out> =
 977                     ::std::condition::Condition {
 978                         name: stringify!($c),
 979                         key: key
 980                     };
 981             }
 982         }
 983     )
 984
 985     macro_rules! format(($($arg:tt)*) => (
 986         format_args!(::std::fmt::format, $($arg)*)
 987     ))
 988     macro_rules! write(($dst:expr, $($arg:tt)*) => (
 989         format_args!(|args| { ::std::fmt::write($dst, args) }, $($arg)*)
 990     ))
 991     macro_rules! writeln(($dst:expr, $($arg:tt)*) => (
 992         format_args!(|args| { ::std::fmt::writeln($dst, args) }, $($arg)*)
 993     ))
 994     macro_rules! print (
 995         ($($arg:tt)*) => (format_args!(::std::rt::io::stdio::print_args, $($arg)*))
 996     )
 997     macro_rules! println (
 998         ($($arg:tt)*) => (format_args!(::std::rt::io::stdio::println_args, $($arg)*))
 999     )
1000
1001     macro_rules! local_data_key (
1002         ($name:ident: $ty:ty) => (
1003             static $name: ::std::local_data::Key<$ty> = &::std::local_data::Key;
1004         );
1005         (pub $name:ident: $ty:ty) => (
1006             pub static $name: ::std::local_data::Key<$ty> = &::std::local_data::Key;
1007         )
1008     )
1009
1010     // externfn! declares a wrapper for an external function.
1011     // It is intended to be used like:
1012     //
1013     // externfn!(#[nolink]
1014     //           fn memcmp(cx: *u8, ct: *u8, n: u32) -> u32)
1015     //
1016     // Due to limitations in the macro parser, this pattern must be
1017     // implemented with 4 distinct patterns (with attrs / without
1018     // attrs CROSS with args / without ARGS).
1019     //
1020     // Also, this macro grammar allows for any number of return types
1021     // because I couldn't figure out the syntax to specify at most one.
1022     macro_rules! externfn(
1023         (fn $name:ident () $(-> $ret_ty:ty),*) => (
1024             pub unsafe fn $name() $(-> $ret_ty),* {
1025                 // Note: to avoid obscure bug in macros, keep these
1026                 // attributes *internal* to the fn
1027                 #[fixed_stack_segment];
1028                 #[inline(never)];
1029                 #[allow(missing_doc)];
1030
1031                 return $name();
1032
1033                 extern {
1034                     fn $name() $(-> $ret_ty),*;
1035                 }
1036             }
1037         );
1038         (fn $name:ident ($($arg_name:ident : $arg_ty:ty),*) $(-> $ret_ty:ty),*) => (
1039             pub unsafe fn $name($($arg_name : $arg_ty),*) $(-> $ret_ty),* {
1040                 // Note: to avoid obscure bug in macros, keep these
1041                 // attributes *internal* to the fn
1042                 #[fixed_stack_segment];
1043                 #[inline(never)];
1044                 #[allow(missing_doc)];
1045
1046                 return $name($($arg_name),*);
1047
1048                 extern {
1049                     fn $name($($arg_name : $arg_ty),*) $(-> $ret_ty),*;
1050                 }
1051             }
1052         );
1053         ($($attrs:attr)* fn $name:ident () $(-> $ret_ty:ty),*) => (
1054             pub unsafe fn $name() $(-> $ret_ty),* {
1055                 // Note: to avoid obscure bug in macros, keep these
1056                 // attributes *internal* to the fn
1057                 #[fixed_stack_segment];
1058                 #[inline(never)];
1059                 #[allow(missing_doc)];
1060
1061                 return $name();
1062
1063                 $($attrs)*
1064                 extern {
1065                     fn $name() $(-> $ret_ty),*;
1066                 }
1067             }
1068         );
1069         ($($attrs:attr)* fn $name:ident ($($arg_name:ident : $arg_ty:ty),*) $(-> $ret_ty:ty),*) => (
1070             pub unsafe fn $name($($arg_name : $arg_ty),*) $(-> $ret_ty),* {
1071                 // Note: to avoid obscure bug in macros, keep these
1072                 // attributes *internal* to the fn
1073                 #[fixed_stack_segment];
1074                 #[inline(never)];
1075                 #[allow(missing_doc)];
1076
1077                 return $name($($arg_name),*);
1078
1079                 $($attrs)*
1080                 extern {
1081                     fn $name($($arg_name : $arg_ty),*) $(-> $ret_ty),*;
1082                 }
1083             }
1084         )
1085     )
1086
1087 }";
1088 }
1089
1090 struct Injector {
1091     sm: @ast::item,
1092 }
1093
1094 impl ast_fold for Injector {
1095     fn fold_mod(&self, module: &ast::_mod) -> ast::_mod {
1096         // Just inject the standard macros at the start of the first module
1097         // in the crate: that is, at the start of the crate file itself.
1098         let items = vec::append(~[ self.sm ], module.items);
1099         ast::_mod {
1100             items: items,
1101             ..(*module).clone() // FIXME #2543: Bad copy.
1102         }
1103     }
1104 }
1105
1106 // add a bunch of macros as though they were placed at the head of the
1107 // program (ick). This should run before cfg stripping.
1108 pub fn inject_std_macros(parse_sess: @mut parse::ParseSess,
1109                          cfg: ast::CrateConfig,
1110                          c: Crate)
1111                          -> Crate {
1112     let sm = match parse_item_from_source_str(@"<std-macros>",
1113                                               std_macros(),
1114                                               cfg.clone(),
1115                                               ~[],
1116                                               parse_sess) {
1117         Some(item) => item,
1118         None => fail!("expected core macros to parse correctly")
1119     };
1120
1121     let injector = @Injector {
1122         sm: sm,
1123     } as @ast_fold;
1124     injector.fold_crate(c)
1125 }
1126
1127 struct NoOpFolder {
1128     contents: (),
1129 }
1130
1131 impl ast_fold for NoOpFolder {}
1132
1133 struct MacroExpander {
1134     extsbox: @mut SyntaxEnv,
1135     cx: @ExtCtxt,
1136 }
1137
1138 impl ast_fold for MacroExpander {
1139     fn fold_expr(&self, expr: @ast::Expr) -> @ast::Expr {
1140         expand_expr(self.extsbox,
1141                     self.cx,
1142                     expr,
1143                     self)
1144     }
1145
1146     fn fold_mod(&self, module: &ast::_mod) -> ast::_mod {
1147         expand_mod_items(self.extsbox,
1148                          self.cx,
1149                          module,
1150                          self)
1151     }
1152
1153     fn fold_item(&self, item: @ast::item) -> Option<@ast::item> {
1154         expand_item(self.extsbox,
1155                     self.cx,
1156                     item,
1157                     self)
1158     }
1159
1160     fn fold_stmt(&self, stmt: &ast::Stmt) -> Option<@ast::Stmt> {
1161         expand_stmt(self.extsbox,
1162                     self.cx,
1163                     stmt,
1164                     self)
1165     }
1166
1167     fn fold_block(&self, block: &ast::Block) -> ast::Block {
1168         expand_block(self.extsbox,
1169                      self.cx,
1170                      block,
1171                      self)
1172     }
1173
1174     fn new_span(&self, span: Span) -> Span {
1175         new_span(self.cx, span)
1176     }
1177 }
1178
1179 pub fn expand_crate(parse_sess: @mut parse::ParseSess,
1180                     cfg: ast::CrateConfig,
1181                     c: Crate) -> Crate {
1182     // adding *another* layer of indirection here so that the block
1183     // visitor can swap out one exts table for another for the duration
1184     // of the block.  The cleaner alternative would be to thread the
1185     // exts table through the fold, but that would require updating
1186     // every method/element of AstFoldFns in fold.rs.
1187     let extsbox = syntax_expander_table();
1188     let cx = ExtCtxt::new(parse_sess, cfg.clone());
1189     let expander = @MacroExpander {
1190         extsbox: @mut extsbox,
1191         cx: cx,
1192     } as @ast_fold;
1193
1194     let ret = expander.fold_crate(c);
1195     parse_sess.span_diagnostic.handler().abort_if_errors();
1196     return ret;
1197 }
1198
1199 // HYGIENIC CONTEXT EXTENSION:
1200 // all of these functions are for walking over
1201 // ASTs and making some change to the context of every
1202 // element that has one. a CtxtFn is a trait-ified
1203 // version of a closure in (SyntaxContext -> SyntaxContext).
1204 // the ones defined here include:
1205 // Renamer - add a rename to a context
1206 // MultiRenamer - add a set of renames to a context
1207 // Marker - add a mark to a context
1208 // Repainter - replace a context (maybe Replacer would be a better name?)
1209
1210 // a function in SyntaxContext -> SyntaxContext
1211 pub trait CtxtFn{
1212     fn f(&self, ast::SyntaxContext) -> ast::SyntaxContext;
1213 }
1214
1215 // a renamer adds a rename to the syntax context
1216 pub struct Renamer {
1217     from : ast::Ident,
1218     to : ast::Name
1219 }
1220
1221 impl CtxtFn for Renamer {
1222     fn f(&self, ctxt : ast::SyntaxContext) -> ast::SyntaxContext {
1223         new_rename(self.from,self.to,ctxt)
1224     }
1225 }
1226
1227 // a renamer that performs a whole bunch of renames
1228 pub struct MultiRenamer {
1229     renames : @mut ~[(ast::Ident,ast::Name)]
1230 }
1231
1232 impl CtxtFn for MultiRenamer {
1233     fn f(&self, starting_ctxt : ast::SyntaxContext) -> ast::SyntaxContext {
1234         // the individual elements are memoized... it would
1235         // also be possible to memoize on the whole list at once.
1236         self.renames.iter().fold(starting_ctxt,|ctxt,&(from,to)| {
1237             new_rename(from,to,ctxt)
1238         })
1239     }
1240 }
1241
1242 // a marker adds the given mark to the syntax context
1243 pub struct Marker { mark : Mrk }
1244
1245 impl CtxtFn for Marker {
1246     fn f(&self, ctxt : ast::SyntaxContext) -> ast::SyntaxContext {
1247         new_mark(self.mark,ctxt)
1248     }
1249 }
1250
1251 // a repainter just replaces the given context with the one it's closed over
1252 pub struct Repainter { ctxt : SyntaxContext }
1253
1254 impl CtxtFn for Repainter {
1255     fn f(&self, _ctxt : ast::SyntaxContext) -> ast::SyntaxContext {
1256         self.ctxt
1257     }
1258 }
1259
1260 pub struct ContextWrapper {
1261     context_function: @CtxtFn,
1262 }
1263
1264 impl ast_fold for ContextWrapper {
1265     fn fold_ident(&self, id: ast::Ident) -> ast::Ident {
1266         let ast::Ident {
1267             name,
1268             ctxt
1269         } = id;
1270         ast::Ident {
1271             name: name,
1272             ctxt: self.context_function.f(ctxt),
1273         }
1274     }
1275     fn fold_mac(&self, m: &ast::mac) -> ast::mac {
1276         let macro = match m.node {
1277             mac_invoc_tt(ref path, ref tts, ctxt) => {
1278                 mac_invoc_tt(self.fold_path(path),
1279                              fold_tts(*tts, self),
1280                              self.context_function.f(ctxt))
1281             }
1282         };
1283         Spanned {
1284             node: macro,
1285             span: m.span,
1286         }
1287     }
1288 }
1289
1290 // given a function from ctxts to ctxts, produce
1291 // an ast_fold that applies that function to all ctxts:
1292 pub fn fun_to_ctxt_folder<T : 'static + CtxtFn>(cf: @T) -> @ContextWrapper {
1293     @ContextWrapper {
1294         context_function: cf as @CtxtFn,
1295     }
1296 }
1297
1298 // just a convenience:
1299 pub fn new_mark_folder(m: Mrk) -> @ContextWrapper {
1300     fun_to_ctxt_folder(@Marker{mark:m})
1301 }
1302
1303 pub fn new_rename_folder(from: ast::Ident, to: ast::Name) -> @ContextWrapper {
1304     fun_to_ctxt_folder(@Renamer{from:from,to:to})
1305 }
1306
1307 // apply a given mark to the given token trees. Used prior to expansion of a macro.
1308 fn mark_tts(tts : &[token_tree], m : Mrk) -> ~[token_tree] {
1309     fold_tts(tts,new_mark_folder(m))
1310 }
1311
1312 // apply a given mark to the given expr. Used following the expansion of a macro.
1313 fn mark_expr(expr : @ast::Expr, m : Mrk) -> @ast::Expr {
1314     new_mark_folder(m).fold_expr(expr)
1315 }
1316
1317 // apply a given mark to the given stmt. Used following the expansion of a macro.
1318 fn mark_stmt(expr : &ast::Stmt, m : Mrk) -> @ast::Stmt {
1319     new_mark_folder(m).fold_stmt(expr).unwrap()
1320 }
1321
1322 // apply a given mark to the given item. Used following the expansion of a macro.
1323 fn mark_item(expr : @ast::item, m : Mrk) -> Option<@ast::item> {
1324     new_mark_folder(m).fold_item(expr)
1325 }
1326
1327 // replace all contexts in a given expr with the given mark. Used
1328 // for capturing macros
1329 pub fn replace_ctxts(expr : @ast::Expr, ctxt : SyntaxContext) -> @ast::Expr {
1330     fun_to_ctxt_folder(@Repainter{ctxt:ctxt}).fold_expr(expr)
1331 }
1332
1333 // take the mark from the given ctxt (that has a mark at the outside),
1334 // and apply it to everything in the token trees, thereby cancelling
1335 // that mark.
1336 pub fn mtwt_cancel_outer_mark(tts: &[ast::token_tree], ctxt: ast::SyntaxContext)
1337     -> ~[ast::token_tree] {
1338     let outer_mark = mtwt_outer_mark(ctxt);
1339     mark_tts(tts,outer_mark)
1340 }
1341
1342 fn original_span(cx: @ExtCtxt) -> @codemap::ExpnInfo {
1343     let mut relevant_info = cx.backtrace();
1344     let mut einfo = relevant_info.unwrap();
1345     loop {
1346         match relevant_info {
1347             None => { break }
1348             Some(e) => {
1349                 einfo = e;
1350                 relevant_info = einfo.call_site.expn_info;
1351             }
1352         }
1353     }
1354     return einfo;
1355 }
1356
1357 #[cfg(test)]
1358 mod test {
1359     use super::*;
1360     use ast;
1361     use ast::{Attribute_, AttrOuter, MetaWord, EMPTY_CTXT};
1362     use ast_util::{get_sctable, mtwt_marksof, mtwt_resolve, new_rename};
1363     use ast_util;
1364     use codemap;
1365     use codemap::Spanned;
1366     use fold;
1367     use parse;
1368     use parse::token::{fresh_mark, gensym, intern, get_ident_interner, ident_to_str};
1369     use parse::token;
1370     use print::pprust;
1371     use std;
1372     use util::parser_testing::{string_to_crate, string_to_crate_and_sess};
1373     use util::parser_testing::{string_to_pat, string_to_tts, strs_to_idents};
1374     use visit;
1375
1376     // make sure that fail! is present
1377     #[test] fn fail_exists_test () {
1378         let src = @"fn main() { fail!(\"something appropriately gloomy\");}";
1379         let sess = parse::new_parse_sess(None);
1380         let crate_ast = parse::parse_crate_from_source_str(
1381             @"<test>",
1382             src,
1383             ~[],sess);
1384         let crate_ast = inject_std_macros(sess, ~[], crate_ast);
1385         // don't bother with striping, doesn't affect fail!.
1386         expand_crate(sess,~[],crate_ast);
1387     }
1388
1389     // these following tests are quite fragile, in that they don't test what
1390     // *kind* of failure occurs.
1391
1392     // make sure that macros can leave scope
1393     #[should_fail]
1394     #[test] fn macros_cant_escape_fns_test () {
1395         let src = @"fn bogus() {macro_rules! z (() => (3+4))}\
1396                     fn inty() -> int { z!() }";
1397         let sess = parse::new_parse_sess(None);
1398         let crate_ast = parse::parse_crate_from_source_str(
1399             @"<test>",
1400             src,
1401             ~[],sess);
1402         // should fail:
1403         expand_crate(sess,~[],crate_ast);
1404     }
1405
1406     // make sure that macros can leave scope for modules
1407     #[should_fail]
1408     #[test] fn macros_cant_escape_mods_test () {
1409         let src = @"mod foo {macro_rules! z (() => (3+4))}\
1410                     fn inty() -> int { z!() }";
1411         let sess = parse::new_parse_sess(None);
1412         let crate_ast = parse::parse_crate_from_source_str(
1413             @"<test>",
1414             src,
1415             ~[],sess);
1416         // should fail:
1417         expand_crate(sess,~[],crate_ast);
1418     }
1419
1420     // macro_escape modules shouldn't cause macros to leave scope
1421     #[test] fn macros_can_escape_flattened_mods_test () {
1422         let src = @"#[macro_escape] mod foo {macro_rules! z (() => (3+4))}\
1423                     fn inty() -> int { z!() }";
1424         let sess = parse::new_parse_sess(None);
1425         let crate_ast = parse::parse_crate_from_source_str(
1426             @"<test>",
1427             src,
1428             ~[], sess);
1429         // should fail:
1430         expand_crate(sess,~[],crate_ast);
1431     }
1432
1433     #[test] fn std_macros_must_parse () {
1434         let src = super::std_macros();
1435         let sess = parse::new_parse_sess(None);
1436         let cfg = ~[];
1437         let item_ast = parse::parse_item_from_source_str(
1438             @"<test>",
1439             src,
1440             cfg,~[],sess);
1441         match item_ast {
1442             Some(_) => (), // success
1443             None => fail!("expected this to parse")
1444         }
1445     }
1446
1447     #[test] fn test_contains_flatten (){
1448         let attr1 = make_dummy_attr (@"foo");
1449         let attr2 = make_dummy_attr (@"bar");
1450         let escape_attr = make_dummy_attr (@"macro_escape");
1451         let attrs1 = ~[attr1, escape_attr, attr2];
1452         assert_eq!(contains_macro_escape (attrs1),true);
1453         let attrs2 = ~[attr1,attr2];
1454         assert_eq!(contains_macro_escape (attrs2),false);
1455     }
1456
1457     // make a MetaWord outer attribute with the given name
1458     fn make_dummy_attr(s: @str) -> ast::Attribute {
1459         Spanned {
1460             span:codemap::dummy_sp(),
1461             node: Attribute_ {
1462                 style: AttrOuter,
1463                 value: @Spanned {
1464                     node: MetaWord(s),
1465                     span: codemap::dummy_sp(),
1466                 },
1467                 is_sugared_doc: false,
1468             }
1469         }
1470     }
1471
1472     #[test] fn cancel_outer_mark_test(){
1473         let invalid_name = token::special_idents::invalid.name;
1474         let ident_str = @"x";
1475         let tts = string_to_tts(ident_str);
1476         let fm = fresh_mark();
1477         let marked_once = fold::fold_tts(tts,new_mark_folder(fm));
1478         assert_eq!(marked_once.len(),1);
1479         let marked_once_ctxt =
1480             match marked_once[0] {
1481                 ast::tt_tok(_,token::IDENT(id,_)) => id.ctxt,
1482                 _ => fail!(format!("unexpected shape for marked tts: {:?}",marked_once[0]))
1483             };
1484         assert_eq!(mtwt_marksof(marked_once_ctxt,invalid_name),~[fm]);
1485         let remarked = mtwt_cancel_outer_mark(marked_once,marked_once_ctxt);
1486         assert_eq!(remarked.len(),1);
1487         match remarked[0] {
1488             ast::tt_tok(_,token::IDENT(id,_)) =>
1489             assert_eq!(mtwt_marksof(id.ctxt,invalid_name),~[]),
1490             _ => fail!(format!("unexpected shape for marked tts: {:?}",remarked[0]))
1491         }
1492     }
1493
1494     #[test]
1495     fn renaming () {
1496         let item_ast = string_to_crate(@"fn f() -> int { a }");
1497         let a_name = intern("a");
1498         let a2_name = gensym("a2");
1499         let renamer = new_rename_folder(ast::Ident{name:a_name,ctxt:EMPTY_CTXT},
1500                                         a2_name);
1501         let renamed_ast = renamer.fold_crate(item_ast.clone());
1502         let varrefs = @mut ~[];
1503         visit::walk_crate(&mut new_path_finder(varrefs), &renamed_ast, ());
1504         match varrefs {
1505             @[ast::Path{segments:[ref seg],_}] =>
1506                 assert_eq!(mtwt_resolve(seg.identifier),a2_name),
1507             _ => assert_eq!(0,1)
1508         }
1509
1510         // try a double-rename, with pending_renames.
1511         let a3_name = gensym("a3");
1512         // a context that renames from ("a",empty) to "a2" :
1513         let ctxt2 = new_rename(ast::Ident::new(a_name),a2_name,EMPTY_CTXT);
1514         let pending_renames = @mut ~[(ast::Ident::new(a_name),a2_name),
1515                                      (ast::Ident{name:a_name,ctxt:ctxt2},a3_name)];
1516         let double_renamed = renames_to_fold(pending_renames).fold_crate(item_ast);
1517         let varrefs = @mut ~[];
1518         visit::walk_crate(&mut new_path_finder(varrefs), &double_renamed, ());
1519         match varrefs {
1520             @[ast::Path{segments:[ref seg],_}] =>
1521                 assert_eq!(mtwt_resolve(seg.identifier),a3_name),
1522             _ => assert_eq!(0,1)
1523         }
1524     }
1525
1526     fn fake_print_crate(crate: &ast::Crate) {
1527         let out = @mut std::rt::io::stderr() as @mut std::rt::io::Writer;
1528         let s = pprust::rust_printer(out, get_ident_interner());
1529         pprust::print_crate_(s, crate);
1530     }
1531
1532     fn expand_crate_str(crate_str: @str) -> ast::Crate {
1533         let (crate_ast,ps) = string_to_crate_and_sess(crate_str);
1534         // the cfg argument actually does matter, here...
1535         expand_crate(ps,~[],crate_ast)
1536     }
1537
1538     //fn expand_and_resolve(crate_str: @str) -> ast::crate {
1539         //let expanded_ast = expand_crate_str(crate_str);
1540         // println(format!("expanded: {:?}\n",expanded_ast));
1541         //mtwt_resolve_crate(expanded_ast)
1542     //}
1543     //fn expand_and_resolve_and_pretty_print (crate_str : @str) -> ~str {
1544         //let resolved_ast = expand_and_resolve(crate_str);
1545         //pprust::to_str(&resolved_ast,fake_print_crate,get_ident_interner())
1546     //}
1547
1548     #[test] fn macro_tokens_should_match(){
1549         expand_crate_str(@"macro_rules! m((a)=>(13)) fn main(){m!(a);}");
1550     }
1551
1552     // renaming tests expand a crate and then check that the bindings match
1553     // the right varrefs. The specification of the test case includes the
1554     // text of the crate, and also an array of arrays.  Each element in the
1555     // outer array corresponds to a binding in the traversal of the AST
1556     // induced by visit.  Each of these arrays contains a list of indexes,
1557     // interpreted as the varrefs in the varref traversal that this binding
1558     // should match.  So, for instance, in a program with two bindings and
1559     // three varrefs, the array ~[~[1,2],~[0]] would indicate that the first
1560     // binding should match the second two varrefs, and the second binding
1561     // should match the first varref.
1562     //
1563     // The comparisons are done post-mtwt-resolve, so we're comparing renamed
1564     // names; differences in marks don't matter any more.
1565     //
1566     // oog... I also want tests that check "binding-identifier-=?". That is,
1567     // not just "do these have the same name", but "do they have the same
1568     // name *and* the same marks"? Understanding this is really pretty painful.
1569     // in principle, you might want to control this boolean on a per-varref basis,
1570     // but that would make things even harder to understand, and might not be
1571     // necessary for thorough testing.
1572     type renaming_test = (&'static str, ~[~[uint]], bool);
1573
1574     #[test]
1575     fn automatic_renaming () {
1576         let tests : ~[renaming_test] =
1577             ~[// b & c should get new names throughout, in the expr too:
1578                 ("fn a() -> int { let b = 13; let c = b; b+c }",
1579                  ~[~[0,1],~[2]], false),
1580                 // both x's should be renamed (how is this causing a bug?)
1581                 ("fn main () {let x : int = 13;x;}",
1582                  ~[~[0]], false),
1583                 // the use of b after the + should be renamed, the other one not:
1584                 ("macro_rules! f (($x:ident) => (b + $x)) fn a() -> int { let b = 13; f!(b)}",
1585                  ~[~[1]], false),
1586                 // the b before the plus should not be renamed (requires marks)
1587                 ("macro_rules! f (($x:ident) => ({let b=9; ($x + b)})) fn a() -> int { f!(b)}",
1588                  ~[~[1]], false),
1589                 // the marks going in and out of letty should cancel, allowing that $x to
1590                 // capture the one following the semicolon.
1591                 // this was an awesome test case, and caught a *lot* of bugs.
1592                 ("macro_rules! letty(($x:ident) => (let $x = 15;))
1593                   macro_rules! user(($x:ident) => ({letty!($x); $x}))
1594                   fn main() -> int {user!(z)}",
1595                  ~[~[0]], false),
1596                 // no longer a fixme #8062: this test exposes a *potential* bug; our system does
1597                 // not behave exactly like MTWT, but a conversation with Matthew Flatt
1598                 // suggests that this can only occur in the presence of local-expand, which
1599                 // we have no plans to support.
1600                 // ("fn main() {let hrcoo = 19; macro_rules! getx(()=>(hrcoo)); getx!();}",
1601                 // ~[~[0]], true)
1602                 // FIXME #6994: the next string exposes the bug referred to in issue 6994, so I'm
1603                 // commenting it out.
1604                 // the z flows into and out of two macros (g & f) along one path, and one
1605                 // (just g) along the other, so the result of the whole thing should
1606                 // be "let z_123 = 3; z_123"
1607                 //"macro_rules! g (($x:ident) =>
1608                 //   ({macro_rules! f(($y:ident)=>({let $y=3;$x}));f!($x)}))
1609                 //   fn a(){g!(z)}"
1610                 // create a really evil test case where a $x appears inside a binding of $x
1611                 // but *shouldnt* bind because it was inserted by a different macro....
1612                 // can't write this test case until we have macro-generating macros.
1613             ];
1614         for (idx,s) in tests.iter().enumerate() {
1615             run_renaming_test(s,idx);
1616         }
1617     }
1618
1619     // run one of the renaming tests
1620     fn run_renaming_test(t : &renaming_test, test_idx: uint) {
1621         let invalid_name = token::special_idents::invalid.name;
1622         let (teststr, bound_connections, bound_ident_check) = match *t {
1623             (ref str,ref conns, bic) => (str.to_managed(), conns.clone(), bic)
1624         };
1625         let cr = expand_crate_str(teststr.to_managed());
1626         // find the bindings:
1627         let bindings = @mut ~[];
1628         visit::walk_crate(&mut new_name_finder(bindings),&cr,());
1629         // find the varrefs:
1630         let varrefs = @mut ~[];
1631         visit::walk_crate(&mut new_path_finder(varrefs),&cr,());
1632         // must be one check clause for each binding:
1633         assert_eq!(bindings.len(),bound_connections.len());
1634         for (binding_idx,shouldmatch) in bound_connections.iter().enumerate() {
1635             let binding_name = mtwt_resolve(bindings[binding_idx]);
1636             let binding_marks = mtwt_marksof(bindings[binding_idx].ctxt,invalid_name);
1637             // shouldmatch can't name varrefs that don't exist:
1638             assert!((shouldmatch.len() == 0) ||
1639                     (varrefs.len() > *shouldmatch.iter().max().unwrap()));
1640             for (idx,varref) in varrefs.iter().enumerate() {
1641                 if shouldmatch.contains(&idx) {
1642                     // it should be a path of length 1, and it should
1643                     // be free-identifier=? or bound-identifier=? to the given binding
1644                     assert_eq!(varref.segments.len(),1);
1645                     let varref_name = mtwt_resolve(varref.segments[0].identifier);
1646                     let varref_marks = mtwt_marksof(varref.segments[0].identifier.ctxt,
1647                                                     invalid_name);
1648                     if (!(varref_name==binding_name)){
1649                         println("uh oh, should match but doesn't:");
1650                         println!("varref: {:?}",varref);
1651                         println!("binding: {:?}", bindings[binding_idx]);
1652                         ast_util::display_sctable(get_sctable());
1653                     }
1654                     assert_eq!(varref_name,binding_name);
1655                     if (bound_ident_check) {
1656                         // we're checking bound-identifier=?, and the marks
1657                         // should be the same, too:
1658                         assert_eq!(varref_marks,binding_marks.clone());
1659                     }
1660                 } else {
1661                     let fail = (varref.segments.len() == 1)
1662                         && (mtwt_resolve(varref.segments[0].identifier) == binding_name);
1663                     // temp debugging:
1664                     if (fail) {
1665                         println!("failure on test {}",test_idx);
1666                         println!("text of test case: \"{}\"", teststr);
1667                         println!("");
1668                         println!("uh oh, matches but shouldn't:");
1669                         println!("varref: {:?}",varref);
1670                         // good lord, you can't make a path with 0 segments, can you?
1671                         println!("varref's first segment's uint: {}, and string: \"{}\"",
1672                                  varref.segments[0].identifier.name,
1673                                  ident_to_str(&varref.segments[0].identifier));
1674                         println!("binding: {:?}", bindings[binding_idx]);
1675                         ast_util::display_sctable(get_sctable());
1676                     }
1677                     assert!(!fail);
1678                 }
1679             }
1680         }
1681     }
1682
1683     #[test] fn fmt_in_macro_used_inside_module_macro() {
1684         let crate_str = @"macro_rules! fmt_wrap(($b:expr)=>($b.to_str()))
1685 macro_rules! foo_module (() => (mod generated { fn a() { let xx = 147; fmt_wrap!(xx);}}))
1686 foo_module!()
1687 ";
1688         let cr = expand_crate_str(crate_str);
1689         // find the xx binding
1690         let bindings = @mut ~[];
1691         visit::walk_crate(&mut new_name_finder(bindings), &cr, ());
1692         let cxbinds : ~[&ast::Ident] =
1693             bindings.iter().filter(|b|{@"xx" == (ident_to_str(*b))}).collect();
1694         let cxbind = match cxbinds {
1695             [b] => b,
1696             _ => fail!("expected just one binding for ext_cx")
1697         };
1698         let resolved_binding = mtwt_resolve(*cxbind);
1699         // find all the xx varrefs:
1700         let varrefs = @mut ~[];
1701         visit::walk_crate(&mut new_path_finder(varrefs), &cr, ());
1702         // the xx binding should bind all of the xx varrefs:
1703         for (idx,v) in varrefs.iter().filter(|p|{ p.segments.len() == 1
1704                                           && (@"xx" == (ident_to_str(&p.segments[0].identifier)))
1705                                      }).enumerate() {
1706             if (mtwt_resolve(v.segments[0].identifier) != resolved_binding) {
1707                 println("uh oh, xx binding didn't match xx varref:");
1708                 println!("this is xx varref \\# {:?}",idx);
1709                 println!("binding: {:?}",cxbind);
1710                 println!("resolves to: {:?}",resolved_binding);
1711                 println!("varref: {:?}",v.segments[0].identifier);
1712                 println!("resolves to: {:?}",
1713                          mtwt_resolve(v.segments[0].identifier));
1714                 let table = get_sctable();
1715                 println("SC table:");
1716                 for (idx,val) in table.table.iter().enumerate() {
1717                     println!("{:4u} : {:?}",idx,val);
1718                 }
1719             }
1720             assert_eq!(mtwt_resolve(v.segments[0].identifier),resolved_binding);
1721         };
1722     }
1723
1724     #[test]
1725     fn pat_idents(){
1726         let pat = string_to_pat(@"(a,Foo{x:c @ (b,9),y:Bar(4,d)})");
1727         let idents = @mut ~[];
1728         let pat_idents = new_name_finder(idents);
1729         pat_idents.visit_pat(pat, ());
1730         assert_eq!(idents, @mut strs_to_idents(~["a","c","b","d"]));
1731     }
1732
1733 }