src/libsyntax/ext/expand.rs

   1 // Copyright 2012-2014 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, ExprMac, PatMac};
  12 use ast::{Local, Ident, MacInvocTT};
  13 use ast::{ItemMac, MacStmtWithSemicolon, Mrk, Stmt, StmtDecl, StmtMac};
  14 use ast::{StmtExpr, StmtSemi};
  15 use ast::TokenTree;
  16 use ast;
  17 use ast_util::path_to_ident;
  18 use ext::mtwt;
  19 use ext::build::AstBuilder;
  20 use attr;
  21 use attr::AttrMetaMethods;
  22 use codemap;
  23 use codemap::{Span, Spanned, ExpnInfo, NameAndSpan, MacroBang, MacroAttribute};
  24 use ext::base::*;
  25 use feature_gate::{Features};
  26 use fold;
  27 use fold::*;
  28 use parse;
  29 use parse::token::{fresh_mark, fresh_name, intern};
  30 use parse::token;
  31 use ptr::P;
  32 use util::small_vector::SmallVector;
  33 use visit;
  34 use visit::Visitor;
  35 use std_inject;
  36
  37 pub fn expand_type(t: P<ast::Ty>,
  38                    fld: &mut MacroExpander,
  39                    impl_ty: Option<P<ast::Ty>>)
  40                    -> P<ast::Ty> {
  41     debug!("expanding type {:?} with impl_ty {:?}", t, impl_ty);
  42     let t = match (t.node.clone(), impl_ty) {
  43         // Expand uses of `Self` in impls to the concrete type.
  44         (ast::Ty_::TyPath(ref path, _), Some(ref impl_ty)) => {
  45             let path_as_ident = path_to_ident(path);
  46             // Note unhygenic comparison here. I think this is correct, since
  47             // even though `Self` is almost just a type parameter, the treatment
  48             // for this expansion is as if it were a keyword.
  49             if path_as_ident.is_some() &&
  50                path_as_ident.unwrap().name == token::special_idents::type_self.name {
  51                 impl_ty.clone()
  52             } else {
  53                 t
  54             }
  55         }
  56         _ => t
  57     };
  58     fold::noop_fold_ty(t, fld)
  59 }
  60
  61 pub fn expand_expr(e: P<ast::Expr>, fld: &mut MacroExpander) -> P<ast::Expr> {
  62     e.and_then(|ast::Expr {id, node, span}| match node {
  63         // expr_mac should really be expr_ext or something; it's the
  64         // entry-point for all syntax extensions.
  65         ast::ExprMac(mac) => {
  66             let expanded_expr = match expand_mac_invoc(mac, span,
  67                                                        |r| r.make_expr(),
  68                                                        mark_expr, fld) {
  69                 Some(expr) => expr,
  70                 None => {
  71                     return DummyResult::raw_expr(span);
  72                 }
  73             };
  74
  75             // Keep going, outside-in.
  76             //
  77             let fully_expanded = fld.fold_expr(expanded_expr);
  78             fld.cx.bt_pop();
  79
  80             fully_expanded.map(|e| ast::Expr {
  81                 id: ast::DUMMY_NODE_ID,
  82                 node: e.node,
  83                 span: span,
  84             })
  85         }
  86
  87         ast::ExprWhile(cond, body, opt_ident) => {
  88             let cond = fld.fold_expr(cond);
  89             let (body, opt_ident) = expand_loop_block(body, opt_ident, fld);
  90             fld.cx.expr(span, ast::ExprWhile(cond, body, opt_ident))
  91         }
  92
  93         // Desugar ExprWhileLet
  94         // From: `[opt_ident]: while let <pat> = <expr> <body>`
  95         ast::ExprWhileLet(pat, expr, body, opt_ident) => {
  96             // to:
  97             //
  98             //   [opt_ident]: loop {
  99             //     match <expr> {
 100             //       <pat> => <body>,
 101             //       _ => break
 102             //     }
 103             //   }
 104
 105             // `<pat> => <body>`
 106             let pat_arm = {
 107                 let body_expr = fld.cx.expr_block(body);
 108                 fld.cx.arm(pat.span, vec![pat], body_expr)
 109             };
 110
 111             // `_ => break`
 112             let break_arm = {
 113                 let pat_under = fld.cx.pat_wild(span);
 114                 let break_expr = fld.cx.expr_break(span);
 115                 fld.cx.arm(span, vec![pat_under], break_expr)
 116             };
 117
 118             // `match <expr> { ... }`
 119             let arms = vec![pat_arm, break_arm];
 120             let match_expr = fld.cx.expr(span,
 121                                     ast::ExprMatch(expr, arms, ast::MatchSource::WhileLetDesugar));
 122
 123             // `[opt_ident]: loop { ... }`
 124             let loop_block = fld.cx.block_expr(match_expr);
 125             let (loop_block, opt_ident) = expand_loop_block(loop_block, opt_ident, fld);
 126             fld.cx.expr(span, ast::ExprLoop(loop_block, opt_ident))
 127         }
 128
 129         // Desugar ExprIfLet
 130         // From: `if let <pat> = <expr> <body> [<elseopt>]`
 131         ast::ExprIfLet(pat, expr, body, mut elseopt) => {
 132             // to:
 133             //
 134             //   match <expr> {
 135             //     <pat> => <body>,
 136             //     [_ if <elseopt_if_cond> => <elseopt_if_body>,]
 137             //     _ => [<elseopt> | ()]
 138             //   }
 139
 140             // `<pat> => <body>`
 141             let pat_arm = {
 142                 let body_expr = fld.cx.expr_block(body);
 143                 fld.cx.arm(pat.span, vec![pat], body_expr)
 144             };
 145
 146             // `[_ if <elseopt_if_cond> => <elseopt_if_body>,]`
 147             let else_if_arms = {
 148                 let mut arms = vec![];
 149                 loop {
 150                     let elseopt_continue = elseopt
 151                         .and_then(|els| els.and_then(|els| match els.node {
 152                         // else if
 153                         ast::ExprIf(cond, then, elseopt) => {
 154                             let pat_under = fld.cx.pat_wild(span);
 155                             arms.push(ast::Arm {
 156                                 attrs: vec![],
 157                                 pats: vec![pat_under],
 158                                 guard: Some(cond),
 159                                 body: fld.cx.expr_block(then)
 160                             });
 161                             elseopt.map(|elseopt| (elseopt, true))
 162                         }
 163                         _ => Some((P(els), false))
 164                     }));
 165                     match elseopt_continue {
 166                         Some((e, true)) => {
 167                             elseopt = Some(e);
 168                         }
 169                         Some((e, false)) => {
 170                             elseopt = Some(e);
 171                             break;
 172                         }
 173                         None => {
 174                             elseopt = None;
 175                             break;
 176                         }
 177                     }
 178                 }
 179                 arms
 180             };
 181
 182             let contains_else_clause = elseopt.is_some();
 183
 184             // `_ => [<elseopt> | ()]`
 185             let else_arm = {
 186                 let pat_under = fld.cx.pat_wild(span);
 187                 let else_expr = elseopt.unwrap_or_else(|| fld.cx.expr_tuple(span, vec![]));
 188                 fld.cx.arm(span, vec![pat_under], else_expr)
 189             };
 190
 191             let mut arms = Vec::with_capacity(else_if_arms.len() + 2);
 192             arms.push(pat_arm);
 193             arms.extend(else_if_arms.into_iter());
 194             arms.push(else_arm);
 195
 196             let match_expr = fld.cx.expr(span,
 197                                          ast::ExprMatch(expr, arms,
 198                                                 ast::MatchSource::IfLetDesugar {
 199                                                     contains_else_clause: contains_else_clause,
 200                                                 }));
 201             fld.fold_expr(match_expr)
 202         }
 203
 204         // Desugar support for ExprIfLet in the ExprIf else position
 205         ast::ExprIf(cond, blk, elseopt) => {
 206             let elseopt = elseopt.map(|els| els.and_then(|els| match els.node {
 207                 ast::ExprIfLet(..) => {
 208                     // wrap the if-let expr in a block
 209                     let span = els.span;
 210                     let blk = P(ast::Block {
 211                         stmts: vec![],
 212                         expr: Some(P(els)),
 213                         id: ast::DUMMY_NODE_ID,
 214                         rules: ast::DefaultBlock,
 215                         span: span
 216                     });
 217                     fld.cx.expr_block(blk)
 218                 }
 219                 _ => P(els)
 220             }));
 221             let if_expr = fld.cx.expr(span, ast::ExprIf(cond, blk, elseopt));
 222             if_expr.map(|e| noop_fold_expr(e, fld))
 223         }
 224
 225         ast::ExprLoop(loop_block, opt_ident) => {
 226             let (loop_block, opt_ident) = expand_loop_block(loop_block, opt_ident, fld);
 227             fld.cx.expr(span, ast::ExprLoop(loop_block, opt_ident))
 228         }
 229
 230         // Desugar ExprForLoop
 231         // From: `[opt_ident]: for <pat> in <head> <body>`
 232         ast::ExprForLoop(pat, head, body, opt_ident) => {
 233             // to:
 234             //
 235             //   {
 236             //     let result = match ::std::iter::IntoIterator::into_iter(<head>) {
 237             //       mut iter => {
 238             //         [opt_ident]: loop {
 239             //           match ::std::iter::Iterator::next(&mut iter) {
 240             //             ::std::option::Option::Some(<pat>) => <body>,
 241             //             ::std::option::Option::None => break
 242             //           }
 243             //         }
 244             //       }
 245             //     };
 246             //     result
 247             //   }
 248
 249             // expand <head>
 250             let head = fld.fold_expr(head);
 251
 252             // create an hygienic ident
 253             let iter = {
 254                 let ident = fld.cx.ident_of("iter");
 255                 let new_ident = fresh_name(&ident);
 256                 let rename = (ident, new_ident);
 257                 let mut rename_list = vec![rename];
 258                 let mut rename_fld = IdentRenamer{ renames: &mut rename_list };
 259
 260                 rename_fld.fold_ident(ident)
 261             };
 262
 263             let pat_span = pat.span;
 264             // `:;std::option::Option::Some(<pat>) => <body>`
 265             let pat_arm = {
 266                 let body_expr = fld.cx.expr_block(body);
 267                 let some_pat = fld.cx.pat_some(pat_span, pat);
 268
 269                 fld.cx.arm(pat_span, vec![some_pat], body_expr)
 270             };
 271
 272             // `::std::option::Option::None => break`
 273             let break_arm = {
 274                 let break_expr = fld.cx.expr_break(span);
 275
 276                 fld.cx.arm(span, vec![fld.cx.pat_none(span)], break_expr)
 277             };
 278
 279             // `match ::std::iter::Iterator::next(&mut iter) { ... }`
 280             let match_expr = {
 281                 let next_path = {
 282                     let strs = vec![
 283                         fld.cx.ident_of_std("core"),
 284                         fld.cx.ident_of("iter"),
 285                         fld.cx.ident_of("Iterator"),
 286                         fld.cx.ident_of("next"),
 287                     ];
 288
 289                     fld.cx.path_global(span, strs)
 290                 };
 291                 let ref_mut_iter = fld.cx.expr_mut_addr_of(span, fld.cx.expr_ident(span, iter));
 292                 let next_expr =
 293                     fld.cx.expr_call(span, fld.cx.expr_path(next_path), vec![ref_mut_iter]);
 294                 let arms = vec![pat_arm, break_arm];
 295
 296                 fld.cx.expr(pat_span,
 297                             ast::ExprMatch(next_expr, arms, ast::MatchSource::ForLoopDesugar))
 298             };
 299
 300             // `[opt_ident]: loop { ... }`
 301             let loop_block = fld.cx.block_expr(match_expr);
 302             let (loop_block, opt_ident) = expand_loop_block(loop_block, opt_ident, fld);
 303             let loop_expr = fld.cx.expr(span, ast::ExprLoop(loop_block, opt_ident));
 304
 305             // `mut iter => { ... }`
 306             let iter_arm = {
 307                 let iter_pat =
 308                     fld.cx.pat_ident_binding_mode(span, iter, ast::BindByValue(ast::MutMutable));
 309                 fld.cx.arm(span, vec![iter_pat], loop_expr)
 310             };
 311
 312             // `match ::std::iter::IntoIterator::into_iter(<head>) { ... }`
 313             let into_iter_expr = {
 314                 let into_iter_path = {
 315                     let strs = vec![
 316                         fld.cx.ident_of_std("core"),
 317                         fld.cx.ident_of("iter"),
 318                         fld.cx.ident_of("IntoIterator"),
 319                         fld.cx.ident_of("into_iter"),
 320                     ];
 321
 322                     fld.cx.path_global(span, strs)
 323                 };
 324
 325                 fld.cx.expr_call(span, fld.cx.expr_path(into_iter_path), vec![head])
 326             };
 327
 328             let match_expr = fld.cx.expr_match(span, into_iter_expr, vec![iter_arm]);
 329
 330             // `{ let result = ...; result }`
 331             let result_ident = token::gensym_ident("result");
 332             fld.cx.expr_block(
 333                 fld.cx.block_all(
 334                     span,
 335                     vec![fld.cx.stmt_let(span, false, result_ident, match_expr)],
 336                     Some(fld.cx.expr_ident(span, result_ident))))
 337         }
 338
 339         ast::ExprClosure(capture_clause, fn_decl, block) => {
 340             let (rewritten_fn_decl, rewritten_block)
 341                 = expand_and_rename_fn_decl_and_block(fn_decl, block, fld);
 342             let new_node = ast::ExprClosure(capture_clause,
 343                                             rewritten_fn_decl,
 344                                             rewritten_block);
 345             P(ast::Expr{id:id, node: new_node, span: fld.new_span(span)})
 346         }
 347
 348         _ => {
 349             P(noop_fold_expr(ast::Expr {
 350                 id: id,
 351                 node: node,
 352                 span: span
 353             }, fld))
 354         }
 355     })
 356 }
 357
 358 /// Expand a (not-ident-style) macro invocation. Returns the result
 359 /// of expansion and the mark which must be applied to the result.
 360 /// Our current interface doesn't allow us to apply the mark to the
 361 /// result until after calling make_expr, make_items, etc.
 362 fn expand_mac_invoc<T, F, G>(mac: ast::Mac, span: codemap::Span,
 363                              parse_thunk: F,
 364                              mark_thunk: G,
 365                              fld: &mut MacroExpander)
 366                              -> Option<T> where
 367     F: for<'a> FnOnce(Box<MacResult+'a>) -> Option<T>,
 368     G: FnOnce(T, Mrk) -> T,
 369 {
 370     match mac.node {
 371         // it would almost certainly be cleaner to pass the whole
 372         // macro invocation in, rather than pulling it apart and
 373         // marking the tts and the ctxt separately. This also goes
 374         // for the other three macro invocation chunks of code
 375         // in this file.
 376         // Token-tree macros:
 377         MacInvocTT(pth, tts, _) => {
 378             if pth.segments.len() > 1 {
 379                 fld.cx.span_err(pth.span,
 380                                 "expected macro name without module \
 381                                 separators");
 382                 // let compilation continue
 383                 return None;
 384             }
 385             let extname = pth.segments[0].identifier;
 386             let extnamestr = token::get_ident(extname);
 387             match fld.cx.syntax_env.find(&extname.name) {
 388                 None => {
 389                     fld.cx.span_err(
 390                         pth.span,
 391                         &format!("macro undefined: '{}!'",
 392                                 &extnamestr)[]);
 393
 394                     // let compilation continue
 395                     None
 396                 }
 397                 Some(rc) => match *rc {
 398                     NormalTT(ref expandfun, exp_span) => {
 399                         fld.cx.bt_push(ExpnInfo {
 400                                 call_site: span,
 401                                 callee: NameAndSpan {
 402                                     name: extnamestr.to_string(),
 403                                     format: MacroBang,
 404                                     span: exp_span,
 405                                 },
 406                             });
 407                         let fm = fresh_mark();
 408                         let marked_before = mark_tts(&tts[..], fm);
 409
 410                         // The span that we pass to the expanders we want to
 411                         // be the root of the call stack. That's the most
 412                         // relevant span and it's the actual invocation of
 413                         // the macro.
 414                         let mac_span = fld.cx.original_span();
 415
 416                         let opt_parsed = {
 417                             let expanded = expandfun.expand(fld.cx,
 418                                                             mac_span,
 419                                                             &marked_before[..]);
 420                             parse_thunk(expanded)
 421                         };
 422                         let parsed = match opt_parsed {
 423                             Some(e) => e,
 424                             None => {
 425                                 fld.cx.span_err(
 426                                     pth.span,
 427                                     &format!("non-expression macro in expression position: {}",
 428                                             &extnamestr[..]
 429                                             )[]);
 430                                 return None;
 431                             }
 432                         };
 433                         Some(mark_thunk(parsed,fm))
 434                     }
 435                     _ => {
 436                         fld.cx.span_err(
 437                             pth.span,
 438                             &format!("'{}' is not a tt-style macro",
 439                                     &extnamestr)[]);
 440                         None
 441                     }
 442                 }
 443             }
 444         }
 445     }
 446 }
 447
 448 /// Rename loop label and expand its loop body
 449 ///
 450 /// The renaming procedure for loop is different in the sense that the loop
 451 /// body is in a block enclosed by loop head so the renaming of loop label
 452 /// must be propagated to the enclosed context.
 453 fn expand_loop_block(loop_block: P<Block>,
 454                      opt_ident: Option<Ident>,
 455                      fld: &mut MacroExpander) -> (P<Block>, Option<Ident>) {
 456     match opt_ident {
 457         Some(label) => {
 458             let new_label = fresh_name(&label);
 459             let rename = (label, new_label);
 460
 461             // The rename *must not* be added to the pending list of current
 462             // syntax context otherwise an unrelated `break` or `continue` in
 463             // the same context will pick that up in the deferred renaming pass
 464             // and be renamed incorrectly.
 465             let mut rename_list = vec!(rename);
 466             let mut rename_fld = IdentRenamer{renames: &mut rename_list};
 467             let renamed_ident = rename_fld.fold_ident(label);
 468
 469             // The rename *must* be added to the enclosed syntax context for
 470             // `break` or `continue` to pick up because by definition they are
 471             // in a block enclosed by loop head.
 472             fld.cx.syntax_env.push_frame();
 473             fld.cx.syntax_env.info().pending_renames.push(rename);
 474             let expanded_block = expand_block_elts(loop_block, fld);
 475             fld.cx.syntax_env.pop_frame();
 476
 477             (expanded_block, Some(renamed_ident))
 478         }
 479         None => (fld.fold_block(loop_block), opt_ident)
 480     }
 481 }
 482
 483 // eval $e with a new exts frame.
 484 // must be a macro so that $e isn't evaluated too early.
 485 macro_rules! with_exts_frame {
 486     ($extsboxexpr:expr,$macros_escape:expr,$e:expr) =>
 487     ({$extsboxexpr.push_frame();
 488       $extsboxexpr.info().macros_escape = $macros_escape;
 489       let result = $e;
 490       $extsboxexpr.pop_frame();
 491       result
 492      })
 493 }
 494
 495 // When we enter a module, record it, for the sake of `module!`
 496 pub fn expand_item(it: P<ast::Item>, fld: &mut MacroExpander)
 497                    -> SmallVector<P<ast::Item>> {
 498     let it = expand_item_modifiers(it, fld);
 499
 500     expand_annotatable(Annotatable::Item(it), fld)
 501         .into_iter().map(|i| i.expect_item()).collect()
 502 }
 503
 504 fn expand_item_modifiers(mut it: P<ast::Item>, fld: &mut MacroExpander)
 505                          -> P<ast::Item> {
 506     // partition the attributes into ItemModifiers and others
 507     let (modifiers, other_attrs) = modifiers(&it.attrs, fld);
 508
 509     // update the attrs, leave everything else alone. Is this mutation really a good idea?
 510     it = P(ast::Item {
 511         attrs: other_attrs,
 512         ..(*it).clone()
 513     });
 514
 515     if modifiers.is_empty() {
 516         let it = expand_item_multi_modifier(Annotatable::Item(it), fld);
 517         return it.expect_item();
 518     }
 519
 520     for attr in &modifiers {
 521         let mname = attr.name();
 522
 523         match fld.cx.syntax_env.find(&intern(&mname)) {
 524             Some(rc) => match *rc {
 525                 Modifier(ref mac) => {
 526                     attr::mark_used(attr);
 527                     fld.cx.bt_push(ExpnInfo {
 528                         call_site: attr.span,
 529                         callee: NameAndSpan {
 530                             name: mname.to_string(),
 531                             format: MacroAttribute,
 532                             span: None,
 533                         }
 534                     });
 535                     it = mac.expand(fld.cx, attr.span, &*attr.node.value, it);
 536                     fld.cx.bt_pop();
 537                 }
 538                 _ => unreachable!()
 539             },
 540             _ => unreachable!()
 541         }
 542     }
 543
 544     // Expansion may have added new ItemModifiers.
 545     // It is possible, that an item modifier could expand to a multi-modifier or
 546     // vice versa. In this case we will expand all modifiers before multi-modifiers,
 547     // which might give an odd ordering. However, I think it is unlikely that the
 548     // two kinds will be mixed, and I old-style multi-modifiers should be deprecated
 549     // anyway.
 550     expand_item_modifiers(it, fld)
 551 }
 552
 553 /// Expand item_underscore
 554 fn expand_item_underscore(item: ast::Item_, fld: &mut MacroExpander) -> ast::Item_ {
 555     match item {
 556         ast::ItemFn(decl, fn_style, abi, generics, body) => {
 557             let (rewritten_fn_decl, rewritten_body)
 558                 = expand_and_rename_fn_decl_and_block(decl, body, fld);
 559             let expanded_generics = fold::noop_fold_generics(generics,fld);
 560             ast::ItemFn(rewritten_fn_decl, fn_style, abi, expanded_generics, rewritten_body)
 561         }
 562         _ => noop_fold_item_underscore(item, fld)
 563     }
 564 }
 565
 566 // does this attribute list contain "macro_use" ?
 567 fn contains_macro_use(fld: &mut MacroExpander, attrs: &[ast::Attribute]) -> bool {
 568     for attr in attrs {
 569         let mut is_use = attr.check_name("macro_use");
 570         if attr.check_name("macro_escape") {
 571             fld.cx.span_warn(attr.span, "macro_escape is a deprecated synonym for macro_use");
 572             is_use = true;
 573             if let ast::AttrInner = attr.node.style {
 574                 fld.cx.span_help(attr.span, "consider an outer attribute, \
 575                                              #[macro_use] mod ...");
 576             }
 577         };
 578
 579         if is_use {
 580             match attr.node.value.node {
 581                 ast::MetaWord(..) => (),
 582                 _ => fld.cx.span_err(attr.span, "arguments to macro_use are not allowed here"),
 583             }
 584             return true;
 585         }
 586     }
 587     false
 588 }
 589
 590 // Support for item-position macro invocations, exactly the same
 591 // logic as for expression-position macro invocations.
 592 pub fn expand_item_mac(it: P<ast::Item>,
 593                        fld: &mut MacroExpander) -> SmallVector<P<ast::Item>> {
 594     let (extname, path_span, tts) = match it.node {
 595         ItemMac(codemap::Spanned {
 596             node: MacInvocTT(ref pth, ref tts, _),
 597             ..
 598         }) => {
 599             (pth.segments[0].identifier, pth.span, (*tts).clone())
 600         }
 601         _ => fld.cx.span_bug(it.span, "invalid item macro invocation")
 602     };
 603
 604     let extnamestr = token::get_ident(extname);
 605     let fm = fresh_mark();
 606     let items = {
 607         let expanded = match fld.cx.syntax_env.find(&extname.name) {
 608             None => {
 609                 fld.cx.span_err(path_span,
 610                                 &format!("macro undefined: '{}!'",
 611                                         extnamestr)[]);
 612                 // let compilation continue
 613                 return SmallVector::zero();
 614             }
 615
 616             Some(rc) => match *rc {
 617                 NormalTT(ref expander, span) => {
 618                     if it.ident.name != parse::token::special_idents::invalid.name {
 619                         fld.cx
 620                             .span_err(path_span,
 621                                       &format!("macro {}! expects no ident argument, \
 622                                         given '{}'",
 623                                       extnamestr,
 624                                       token::get_ident(it.ident))[]);
 625                         return SmallVector::zero();
 626                     }
 627                     fld.cx.bt_push(ExpnInfo {
 628                         call_site: it.span,
 629                         callee: NameAndSpan {
 630                             name: extnamestr.to_string(),
 631                             format: MacroBang,
 632                             span: span
 633                         }
 634                     });
 635                     // mark before expansion:
 636                     let marked_before = mark_tts(&tts[..], fm);
 637                     expander.expand(fld.cx, it.span, &marked_before[..])
 638                 }
 639                 IdentTT(ref expander, span) => {
 640                     if it.ident.name == parse::token::special_idents::invalid.name {
 641                         fld.cx.span_err(path_span,
 642                                         &format!("macro {}! expects an ident argument",
 643                                                 &extnamestr)[]);
 644                         return SmallVector::zero();
 645                     }
 646                     fld.cx.bt_push(ExpnInfo {
 647                         call_site: it.span,
 648                         callee: NameAndSpan {
 649                             name: extnamestr.to_string(),
 650                             format: MacroBang,
 651                             span: span
 652                         }
 653                     });
 654                     // mark before expansion:
 655                     let marked_tts = mark_tts(&tts[..], fm);
 656                     expander.expand(fld.cx, it.span, it.ident, marked_tts)
 657                 }
 658                 MacroRulesTT => {
 659                     if it.ident.name == parse::token::special_idents::invalid.name {
 660                         fld.cx.span_err(path_span,
 661                                         &format!("macro_rules! expects an ident argument")
 662                                         []);
 663                         return SmallVector::zero();
 664                     }
 665                     fld.cx.bt_push(ExpnInfo {
 666                         call_site: it.span,
 667                         callee: NameAndSpan {
 668                             name: extnamestr.to_string(),
 669                             format: MacroBang,
 670                             span: None,
 671                         }
 672                     });
 673                     // DON'T mark before expansion.
 674
 675                     let def = ast::MacroDef {
 676                         ident: it.ident,
 677                         attrs: it.attrs.clone(),
 678                         id: ast::DUMMY_NODE_ID,
 679                         span: it.span,
 680                         imported_from: None,
 681                         export: attr::contains_name(&it.attrs, "macro_export"),
 682                         use_locally: true,
 683                         body: tts,
 684                     };
 685                     fld.cx.insert_macro(def);
 686
 687                     // macro_rules! has a side effect but expands to nothing.
 688                     fld.cx.bt_pop();
 689                     return SmallVector::zero();
 690                 }
 691                 _ => {
 692                     fld.cx.span_err(it.span,
 693                                     &format!("{}! is not legal in item position",
 694                                             &extnamestr)[]);
 695                     return SmallVector::zero();
 696                 }
 697             }
 698         };
 699
 700         expanded.make_items()
 701     };
 702
 703     let items = match items {
 704         Some(items) => {
 705             items.into_iter()
 706                 .map(|i| mark_item(i, fm))
 707                 .flat_map(|i| fld.fold_item(i).into_iter())
 708                 .collect()
 709         }
 710         None => {
 711             fld.cx.span_err(path_span,
 712                             &format!("non-item macro in item position: {}",
 713                                     &extnamestr)[]);
 714             return SmallVector::zero();
 715         }
 716     };
 717
 718     fld.cx.bt_pop();
 719     items
 720 }
 721
 722 /// Expand a stmt
 723 fn expand_stmt(s: Stmt, fld: &mut MacroExpander) -> SmallVector<P<Stmt>> {
 724     let (mac, style) = match s.node {
 725         StmtMac(mac, style) => (mac, style),
 726         _ => return expand_non_macro_stmt(s, fld)
 727     };
 728     let expanded_stmt = match expand_mac_invoc(mac.and_then(|m| m), s.span,
 729                                                 |r| r.make_stmt(),
 730                                                 mark_stmt, fld) {
 731         Some(stmt) => stmt,
 732         None => {
 733             return SmallVector::zero();
 734         }
 735     };
 736
 737     // Keep going, outside-in.
 738     let fully_expanded = fld.fold_stmt(expanded_stmt);
 739     fld.cx.bt_pop();
 740
 741     if style == MacStmtWithSemicolon {
 742         fully_expanded.into_iter().map(|s| s.map(|Spanned {node, span}| {
 743             Spanned {
 744                 node: match node {
 745                     StmtExpr(e, stmt_id) => StmtSemi(e, stmt_id),
 746                     _ => node /* might already have a semi */
 747                 },
 748                 span: span
 749             }
 750         })).collect()
 751     } else {
 752         fully_expanded
 753     }
 754 }
 755
 756 // expand a non-macro stmt. this is essentially the fallthrough for
 757 // expand_stmt, above.
 758 fn expand_non_macro_stmt(Spanned {node, span: stmt_span}: Stmt, fld: &mut MacroExpander)
 759                          -> SmallVector<P<Stmt>> {
 760     // is it a let?
 761     match node {
 762         StmtDecl(decl, node_id) => decl.and_then(|Spanned {node: decl, span}| match decl {
 763             DeclLocal(local) => {
 764                 // take it apart:
 765                 let rewritten_local = local.map(|Local {id, pat, ty, init, source, span}| {
 766                     // expand the ty since TyFixedLengthVec contains an Expr
 767                     // and thus may have a macro use
 768                     let expanded_ty = ty.map(|t| fld.fold_ty(t));
 769                     // expand the pat (it might contain macro uses):
 770                     let expanded_pat = fld.fold_pat(pat);
 771                     // find the PatIdents in the pattern:
 772                     // oh dear heaven... this is going to include the enum
 773                     // names, as well... but that should be okay, as long as
 774                     // the new names are gensyms for the old ones.
 775                     // generate fresh names, push them to a new pending list
 776                     let idents = pattern_bindings(&*expanded_pat);
 777                     let mut new_pending_renames =
 778                         idents.iter().map(|ident| (*ident, fresh_name(ident))).collect();
 779                     // rewrite the pattern using the new names (the old
 780                     // ones have already been applied):
 781                     let rewritten_pat = {
 782                         // nested binding to allow borrow to expire:
 783                         let mut rename_fld = IdentRenamer{renames: &mut new_pending_renames};
 784                         rename_fld.fold_pat(expanded_pat)
 785                     };
 786                     // add them to the existing pending renames:
 787                     fld.cx.syntax_env.info().pending_renames
 788                           .extend(new_pending_renames.into_iter());
 789                     Local {
 790                         id: id,
 791                         ty: expanded_ty,
 792                         pat: rewritten_pat,
 793                         // also, don't forget to expand the init:
 794                         init: init.map(|e| fld.fold_expr(e)),
 795                         source: source,
 796                         span: span
 797                     }
 798                 });
 799                 SmallVector::one(P(Spanned {
 800                     node: StmtDecl(P(Spanned {
 801                             node: DeclLocal(rewritten_local),
 802                             span: span
 803                         }),
 804                         node_id),
 805                     span: stmt_span
 806                 }))
 807             }
 808             _ => {
 809                 noop_fold_stmt(Spanned {
 810                     node: StmtDecl(P(Spanned {
 811                             node: decl,
 812                             span: span
 813                         }),
 814                         node_id),
 815                     span: stmt_span
 816                 }, fld)
 817             }
 818         }),
 819         _ => {
 820             noop_fold_stmt(Spanned {
 821                 node: node,
 822                 span: stmt_span
 823             }, fld)
 824         }
 825     }
 826 }
 827
 828 // expand the arm of a 'match', renaming for macro hygiene
 829 fn expand_arm(arm: ast::Arm, fld: &mut MacroExpander) -> ast::Arm {
 830     // expand pats... they might contain macro uses:
 831     let expanded_pats = arm.pats.move_map(|pat| fld.fold_pat(pat));
 832     if expanded_pats.len() == 0 {
 833         panic!("encountered match arm with 0 patterns");
 834     }
 835     // all of the pats must have the same set of bindings, so use the
 836     // first one to extract them and generate new names:
 837     let idents = pattern_bindings(&*expanded_pats[0]);
 838     let new_renames = idents.into_iter().map(|id| (id, fresh_name(&id))).collect();
 839     // apply the renaming, but only to the PatIdents:
 840     let mut rename_pats_fld = PatIdentRenamer{renames:&new_renames};
 841     let rewritten_pats = expanded_pats.move_map(|pat| rename_pats_fld.fold_pat(pat));
 842     // apply renaming and then expansion to the guard and the body:
 843     let mut rename_fld = IdentRenamer{renames:&new_renames};
 844     let rewritten_guard =
 845         arm.guard.map(|g| fld.fold_expr(rename_fld.fold_expr(g)));
 846     let rewritten_body = fld.fold_expr(rename_fld.fold_expr(arm.body));
 847     ast::Arm {
 848         attrs: fold::fold_attrs(arm.attrs, fld),
 849         pats: rewritten_pats,
 850         guard: rewritten_guard,
 851         body: rewritten_body,
 852     }
 853 }
 854
 855 /// A visitor that extracts the PatIdent (binding) paths
 856 /// from a given thingy and puts them in a mutable
 857 /// array
 858 #[derive(Clone)]
 859 struct PatIdentFinder {
 860     ident_accumulator: Vec<ast::Ident>
 861 }
 862
 863 impl<'v> Visitor<'v> for PatIdentFinder {
 864     fn visit_pat(&mut self, pattern: &ast::Pat) {
 865         match *pattern {
 866             ast::Pat { id: _, node: ast::PatIdent(_, ref path1, ref inner), span: _ } => {
 867                 self.ident_accumulator.push(path1.node);
 868                 // visit optional subpattern of PatIdent:
 869                 if let Some(ref subpat) = *inner {
 870                     self.visit_pat(&**subpat)
 871                 }
 872             }
 873             // use the default traversal for non-PatIdents
 874             _ => visit::walk_pat(self, pattern)
 875         }
 876     }
 877 }
 878
 879 /// find the PatIdent paths in a pattern
 880 fn pattern_bindings(pat: &ast::Pat) -> Vec<ast::Ident> {
 881     let mut name_finder = PatIdentFinder{ident_accumulator:Vec::new()};
 882     name_finder.visit_pat(pat);
 883     name_finder.ident_accumulator
 884 }
 885
 886 /// find the PatIdent paths in a
 887 fn fn_decl_arg_bindings(fn_decl: &ast::FnDecl) -> Vec<ast::Ident> {
 888     let mut pat_idents = PatIdentFinder{ident_accumulator:Vec::new()};
 889     for arg in &fn_decl.inputs {
 890         pat_idents.visit_pat(&*arg.pat);
 891     }
 892     pat_idents.ident_accumulator
 893 }
 894
 895 // expand a block. pushes a new exts_frame, then calls expand_block_elts
 896 pub fn expand_block(blk: P<Block>, fld: &mut MacroExpander) -> P<Block> {
 897     // see note below about treatment of exts table
 898     with_exts_frame!(fld.cx.syntax_env,false,
 899                      expand_block_elts(blk, fld))
 900 }
 901
 902 // expand the elements of a block.
 903 pub fn expand_block_elts(b: P<Block>, fld: &mut MacroExpander) -> P<Block> {
 904     b.map(|Block {id, stmts, expr, rules, span}| {
 905         let new_stmts = stmts.into_iter().flat_map(|x| {
 906             // perform all pending renames
 907             let renamed_stmt = {
 908                 let pending_renames = &mut fld.cx.syntax_env.info().pending_renames;
 909                 let mut rename_fld = IdentRenamer{renames:pending_renames};
 910                 rename_fld.fold_stmt(x).expect_one("rename_fold didn't return one value")
 911             };
 912             // expand macros in the statement
 913             fld.fold_stmt(renamed_stmt).into_iter()
 914         }).collect();
 915         let new_expr = expr.map(|x| {
 916             let expr = {
 917                 let pending_renames = &mut fld.cx.syntax_env.info().pending_renames;
 918                 let mut rename_fld = IdentRenamer{renames:pending_renames};
 919                 rename_fld.fold_expr(x)
 920             };
 921             fld.fold_expr(expr)
 922         });
 923         Block {
 924             id: fld.new_id(id),
 925             stmts: new_stmts,
 926             expr: new_expr,
 927             rules: rules,
 928             span: span
 929         }
 930     })
 931 }
 932
 933 fn expand_pat(p: P<ast::Pat>, fld: &mut MacroExpander) -> P<ast::Pat> {
 934     match p.node {
 935         PatMac(_) => {}
 936         _ => return noop_fold_pat(p, fld)
 937     }
 938     p.map(|ast::Pat {node, span, ..}| {
 939         let (pth, tts) = match node {
 940             PatMac(mac) => match mac.node {
 941                 MacInvocTT(pth, tts, _) => {
 942                     (pth, tts)
 943                 }
 944             },
 945             _ => unreachable!()
 946         };
 947         if pth.segments.len() > 1 {
 948             fld.cx.span_err(pth.span, "expected macro name without module separators");
 949             return DummyResult::raw_pat(span);
 950         }
 951         let extname = pth.segments[0].identifier;
 952         let extnamestr = token::get_ident(extname);
 953         let marked_after = match fld.cx.syntax_env.find(&extname.name) {
 954             None => {
 955                 fld.cx.span_err(pth.span,
 956                                 &format!("macro undefined: '{}!'",
 957                                         extnamestr)[]);
 958                 // let compilation continue
 959                 return DummyResult::raw_pat(span);
 960             }
 961
 962             Some(rc) => match *rc {
 963                 NormalTT(ref expander, tt_span) => {
 964                     fld.cx.bt_push(ExpnInfo {
 965                         call_site: span,
 966                         callee: NameAndSpan {
 967                             name: extnamestr.to_string(),
 968                             format: MacroBang,
 969                             span: tt_span
 970                         }
 971                     });
 972
 973                     let fm = fresh_mark();
 974                     let marked_before = mark_tts(&tts[..], fm);
 975                     let mac_span = fld.cx.original_span();
 976                     let expanded = match expander.expand(fld.cx,
 977                                         mac_span,
 978                                         &marked_before[..]).make_pat() {
 979                         Some(e) => e,
 980                         None => {
 981                             fld.cx.span_err(
 982                                 pth.span,
 983                                 &format!(
 984                                     "non-pattern macro in pattern position: {}",
 985                                     &extnamestr
 986                                     )[]
 987                             );
 988                             return DummyResult::raw_pat(span);
 989                         }
 990                     };
 991
 992                     // mark after:
 993                     mark_pat(expanded,fm)
 994                 }
 995                 _ => {
 996                     fld.cx.span_err(span,
 997                                     &format!("{}! is not legal in pattern position",
 998                                             &extnamestr)[]);
 999                     return DummyResult::raw_pat(span);
1000                 }
1001             }
1002         };
1003
1004         let fully_expanded =
1005             fld.fold_pat(marked_after).node.clone();
1006         fld.cx.bt_pop();
1007
1008         ast::Pat {
1009             id: ast::DUMMY_NODE_ID,
1010             node: fully_expanded,
1011             span: span
1012         }
1013     })
1014 }
1015
1016 /// A tree-folder that applies every rename in its (mutable) list
1017 /// to every identifier, including both bindings and varrefs
1018 /// (and lots of things that will turn out to be neither)
1019 pub struct IdentRenamer<'a> {
1020     renames: &'a mtwt::RenameList,
1021 }
1022
1023 impl<'a> Folder for IdentRenamer<'a> {
1024     fn fold_ident(&mut self, id: Ident) -> Ident {
1025         Ident {
1026             name: id.name,
1027             ctxt: mtwt::apply_renames(self.renames, id.ctxt),
1028         }
1029     }
1030     fn fold_mac(&mut self, mac: ast::Mac) -> ast::Mac {
1031         fold::noop_fold_mac(mac, self)
1032     }
1033 }
1034
1035 /// A tree-folder that applies every rename in its list to
1036 /// the idents that are in PatIdent patterns. This is more narrowly
1037 /// focused than IdentRenamer, and is needed for FnDecl,
1038 /// where we want to rename the args but not the fn name or the generics etc.
1039 pub struct PatIdentRenamer<'a> {
1040     renames: &'a mtwt::RenameList,
1041 }
1042
1043 impl<'a> Folder for PatIdentRenamer<'a> {
1044     fn fold_pat(&mut self, pat: P<ast::Pat>) -> P<ast::Pat> {
1045         match pat.node {
1046             ast::PatIdent(..) => {},
1047             _ => return noop_fold_pat(pat, self)
1048         }
1049
1050         pat.map(|ast::Pat {id, node, span}| match node {
1051             ast::PatIdent(binding_mode, Spanned{span: sp, node: ident}, sub) => {
1052                 let new_ident = Ident{name: ident.name,
1053                                       ctxt: mtwt::apply_renames(self.renames, ident.ctxt)};
1054                 let new_node =
1055                     ast::PatIdent(binding_mode,
1056                                   Spanned{span: self.new_span(sp), node: new_ident},
1057                                   sub.map(|p| self.fold_pat(p)));
1058                 ast::Pat {
1059                     id: id,
1060                     node: new_node,
1061                     span: self.new_span(span)
1062                 }
1063             },
1064             _ => unreachable!()
1065         })
1066     }
1067     fn fold_mac(&mut self, mac: ast::Mac) -> ast::Mac {
1068         fold::noop_fold_mac(mac, self)
1069     }
1070 }
1071
1072 fn expand_annotatable(a: Annotatable,
1073                       fld: &mut MacroExpander)
1074                       -> SmallVector<Annotatable> {
1075     let a = expand_item_multi_modifier(a, fld);
1076
1077     let mut decorator_items = SmallVector::zero();
1078     let mut new_attrs = Vec::new();
1079     for attr in a.attrs() {
1080         let mname = attr.name();
1081
1082         match fld.cx.syntax_env.find(&intern(&mname)) {
1083             Some(rc) => match *rc {
1084                 Decorator(ref dec) => {
1085                     let it = match a {
1086                         Annotatable::Item(ref it) => it,
1087                         // ItemDecorators are only implemented for Items.
1088                         _ => break,
1089                     };
1090
1091                     attr::mark_used(attr);
1092
1093                     fld.cx.bt_push(ExpnInfo {
1094                         call_site: attr.span,
1095                         callee: NameAndSpan {
1096                             name: mname.to_string(),
1097                             format: MacroAttribute,
1098                             span: None
1099                         }
1100                     });
1101
1102                     // we'd ideally decorator_items.push_all(expand_item(item, fld)),
1103                     // but that double-mut-borrows fld
1104                     let mut items: SmallVector<P<ast::Item>> = SmallVector::zero();
1105                     dec.expand(fld.cx, attr.span, &*attr.node.value, &**it,
1106                                &mut |item| items.push(item));
1107                     decorator_items.extend(
1108                         items.into_iter()
1109                              .flat_map(|item| expand_item(item, fld).into_iter()));
1110
1111                     fld.cx.bt_pop();
1112                 }
1113                 _ => new_attrs.push((*attr).clone()),
1114             },
1115             _ => new_attrs.push((*attr).clone()),
1116         }
1117     }
1118
1119     let mut new_items: SmallVector<Annotatable> = match a {
1120         Annotatable::Item(it) => match it.node {
1121             ast::ItemMac(..) => {
1122                 expand_item_mac(it, fld).into_iter().map(|i| Annotatable::Item(i)).collect()
1123             }
1124             ast::ItemMod(_) | ast::ItemForeignMod(_) => {
1125                 let valid_ident =
1126                     it.ident.name != parse::token::special_idents::invalid.name;
1127
1128                 if valid_ident {
1129                     fld.cx.mod_push(it.ident);
1130                 }
1131                 let macro_use = contains_macro_use(fld, &new_attrs[..]);
1132                 let result = with_exts_frame!(fld.cx.syntax_env,
1133                                               macro_use,
1134                                               noop_fold_item(it, fld));
1135                 if valid_ident {
1136                     fld.cx.mod_pop();
1137                 }
1138                 result.into_iter().map(|i| Annotatable::Item(i)).collect()
1139             },
1140             _ => {
1141                 let it = P(ast::Item {
1142                     attrs: new_attrs,
1143                     ..(*it).clone()
1144                 });
1145                 noop_fold_item(it, fld).into_iter().map(|i| Annotatable::Item(i)).collect()
1146             }
1147         },
1148         Annotatable::TraitItem(it) => match it {
1149             ast::TraitItem::ProvidedMethod(m) => {
1150                 expand_method(m, fld).into_iter().map(|m|
1151                     Annotatable::TraitItem(ast::TraitItem::ProvidedMethod(m))).collect()
1152             }
1153             ast::TraitItem::RequiredMethod(m) => {
1154                 SmallVector::one(Annotatable::TraitItem(
1155                     ast::TraitItem::RequiredMethod(fld.fold_type_method(m))))
1156             }
1157             ast::TraitItem::TypeTraitItem(t) => {
1158                 SmallVector::one(Annotatable::TraitItem(
1159                     ast::TraitItem::TypeTraitItem(P(fld.fold_associated_type((*t).clone())))))
1160             }
1161         },
1162         Annotatable::ImplItem(it) => match it {
1163             ast::ImplItem::MethodImplItem(m) => {
1164                 expand_method(m, fld).into_iter().map(|m|
1165                     Annotatable::ImplItem(ast::ImplItem::MethodImplItem(m))).collect()
1166             }
1167             ast::ImplItem::TypeImplItem(t) => {
1168                 SmallVector::one(Annotatable::ImplItem(
1169                     ast::ImplItem::TypeImplItem(P(fld.fold_typedef((*t).clone())))))
1170             }
1171         }
1172     };
1173
1174     new_items.push_all(decorator_items.into_iter().map(|i| Annotatable::Item(i)).collect());
1175     new_items
1176 }
1177
1178 fn expand_trait_item(i: ast::TraitItem,
1179                      fld: &mut MacroExpander)
1180                      -> SmallVector<ast::TraitItem> {
1181     expand_annotatable(Annotatable::TraitItem(i), fld)
1182         .into_iter().map(|i| i.expect_trait_item()).collect()
1183
1184 }
1185
1186 fn expand_impl_item(i: ast::ImplItem,
1187                     fld: &mut MacroExpander)
1188                     -> SmallVector<ast::ImplItem> {
1189     expand_annotatable(Annotatable::ImplItem(i), fld)
1190         .into_iter().map(|i| i.expect_impl_item()).collect()
1191 }
1192
1193 // partition the attributes into ItemModifiers and others
1194 fn modifiers(attrs: &Vec<ast::Attribute>,
1195              fld: &MacroExpander)
1196              -> (Vec<ast::Attribute>, Vec<ast::Attribute>) {
1197     attrs.iter().cloned().partition(|attr| {
1198         match fld.cx.syntax_env.find(&intern(&attr.name())) {
1199             Some(rc) => match *rc {
1200                 Modifier(_) => true,
1201                 _ => false
1202             },
1203             _ => false
1204         }
1205     })
1206 }
1207
1208 // partition the attributes into MultiModifiers and others
1209 fn multi_modifiers(attrs: &[ast::Attribute],
1210                    fld: &MacroExpander)
1211                    -> (Vec<ast::Attribute>, Vec<ast::Attribute>) {
1212     attrs.iter().cloned().partition(|attr| {
1213         match fld.cx.syntax_env.find(&intern(&attr.name())) {
1214             Some(rc) => match *rc {
1215                 MultiModifier(_) => true,
1216                 _ => false
1217             },
1218             _ => false
1219         }
1220     })
1221 }
1222
1223 fn expand_item_multi_modifier(mut it: Annotatable,
1224                               fld: &mut MacroExpander)
1225                               -> Annotatable {
1226     let (modifiers, other_attrs) = multi_modifiers(it.attrs(), fld);
1227
1228     // Update the attrs, leave everything else alone. Is this mutation really a good idea?
1229     it = it.fold_attrs(other_attrs);
1230
1231     if modifiers.is_empty() {
1232         return it
1233     }
1234
1235     for attr in &modifiers {
1236         let mname = attr.name();
1237
1238         match fld.cx.syntax_env.find(&intern(&mname)) {
1239             Some(rc) => match *rc {
1240                 MultiModifier(ref mac) => {
1241                     attr::mark_used(attr);
1242                     fld.cx.bt_push(ExpnInfo {
1243                         call_site: attr.span,
1244                         callee: NameAndSpan {
1245                             name: mname.to_string(),
1246                             format: MacroAttribute,
1247                             span: None,
1248                         }
1249                     });
1250                     it = mac.expand(fld.cx, attr.span, &*attr.node.value, it);
1251                     fld.cx.bt_pop();
1252                 }
1253                 _ => unreachable!()
1254             },
1255             _ => unreachable!()
1256         }
1257     }
1258
1259     // Expansion may have added new ItemModifiers.
1260     expand_item_multi_modifier(it, fld)
1261 }
1262
1263 // expand a method
1264 fn expand_method(m: P<ast::Method>, fld: &mut MacroExpander) -> SmallVector<P<ast::Method>> {
1265     m.and_then(|m| match m.node {
1266         ast::MethDecl(ident,
1267                       generics,
1268                       abi,
1269                       explicit_self,
1270                       fn_style,
1271                       decl,
1272                       body,
1273                       vis) => {
1274             let id = fld.new_id(m.id);
1275             let (rewritten_fn_decl, rewritten_body)
1276                 = expand_and_rename_fn_decl_and_block(decl, body, fld);
1277             SmallVector::one(P(ast::Method {
1278                     attrs: fold::fold_attrs(m.attrs, fld),
1279                     id: id,
1280                     span: fld.new_span(m.span),
1281                     node: ast::MethDecl(fld.fold_ident(ident),
1282                                         noop_fold_generics(generics, fld),
1283                                         abi,
1284                                         fld.fold_explicit_self(explicit_self),
1285                                         fn_style,
1286                                         rewritten_fn_decl,
1287                                         rewritten_body,
1288                                         vis)
1289                 }))
1290         },
1291         ast::MethMac(mac) => {
1292             let maybe_new_methods =
1293                 expand_mac_invoc(mac, m.span,
1294                                  |r| r.make_methods(),
1295                                  |meths, mark| meths.move_map(|m| mark_method(m, mark)),
1296                                  fld);
1297
1298             match maybe_new_methods {
1299                 Some(methods) => {
1300                     // expand again if necessary
1301                     let new_methods = methods.into_iter()
1302                                              .flat_map(|m| fld.fold_method(m).into_iter())
1303                                              .collect();
1304                     fld.cx.bt_pop();
1305                     new_methods
1306                 }
1307                 None => SmallVector::zero()
1308             }
1309         }
1310     })
1311 }
1312
1313 /// Given a fn_decl and a block and a MacroExpander, expand the fn_decl, then use the
1314 /// PatIdents in its arguments to perform renaming in the FnDecl and
1315 /// the block, returning both the new FnDecl and the new Block.
1316 fn expand_and_rename_fn_decl_and_block(fn_decl: P<ast::FnDecl>, block: P<ast::Block>,
1317                                        fld: &mut MacroExpander)
1318     -> (P<ast::FnDecl>, P<ast::Block>) {
1319     let expanded_decl = fld.fold_fn_decl(fn_decl);
1320     let idents = fn_decl_arg_bindings(&*expanded_decl);
1321     let renames =
1322         idents.iter().map(|id : &ast::Ident| (*id,fresh_name(id))).collect();
1323     // first, a renamer for the PatIdents, for the fn_decl:
1324     let mut rename_pat_fld = PatIdentRenamer{renames: &renames};
1325     let rewritten_fn_decl = rename_pat_fld.fold_fn_decl(expanded_decl);
1326     // now, a renamer for *all* idents, for the body:
1327     let mut rename_fld = IdentRenamer{renames: &renames};
1328     let rewritten_body = fld.fold_block(rename_fld.fold_block(block));
1329     (rewritten_fn_decl,rewritten_body)
1330 }
1331
1332 /// A tree-folder that performs macro expansion
1333 pub struct MacroExpander<'a, 'b:'a> {
1334     pub cx: &'a mut ExtCtxt<'b>,
1335     // The type of the impl currently being expanded.
1336     current_impl_type: Option<P<ast::Ty>>,
1337 }
1338
1339 impl<'a, 'b> MacroExpander<'a, 'b> {
1340     pub fn new(cx: &'a mut ExtCtxt<'b>) -> MacroExpander<'a, 'b> {
1341         MacroExpander { cx: cx, current_impl_type: None }
1342     }
1343 }
1344
1345 impl<'a, 'b> Folder for MacroExpander<'a, 'b> {
1346     fn fold_expr(&mut self, expr: P<ast::Expr>) -> P<ast::Expr> {
1347         expand_expr(expr, self)
1348     }
1349
1350     fn fold_pat(&mut self, pat: P<ast::Pat>) -> P<ast::Pat> {
1351         expand_pat(pat, self)
1352     }
1353
1354     fn fold_item(&mut self, item: P<ast::Item>) -> SmallVector<P<ast::Item>> {
1355         let prev_type = self.current_impl_type.clone();
1356         if let ast::Item_::ItemImpl(_, _, _, _, ref ty, _) = item.node {
1357             self.current_impl_type = Some(ty.clone());
1358         }
1359
1360         let result = expand_item(item, self);
1361         self.current_impl_type = prev_type;
1362         result
1363     }
1364
1365     fn fold_item_underscore(&mut self, item: ast::Item_) -> ast::Item_ {
1366         expand_item_underscore(item, self)
1367     }
1368
1369     fn fold_stmt(&mut self, stmt: P<ast::Stmt>) -> SmallVector<P<ast::Stmt>> {
1370         stmt.and_then(|stmt| expand_stmt(stmt, self))
1371     }
1372
1373     fn fold_block(&mut self, block: P<Block>) -> P<Block> {
1374         expand_block(block, self)
1375     }
1376
1377     fn fold_arm(&mut self, arm: ast::Arm) -> ast::Arm {
1378         expand_arm(arm, self)
1379     }
1380
1381     fn fold_trait_item(&mut self, i: ast::TraitItem) -> SmallVector<ast::TraitItem> {
1382         expand_trait_item(i, self)
1383     }
1384
1385     fn fold_impl_item(&mut self, i: ast::ImplItem) -> SmallVector<ast::ImplItem> {
1386         expand_impl_item(i, self)
1387     }
1388
1389     fn fold_method(&mut self, method: P<ast::Method>) -> SmallVector<P<ast::Method>> {
1390         expand_method(method, self)
1391     }
1392
1393     fn fold_ty(&mut self, t: P<ast::Ty>) -> P<ast::Ty> {
1394         let impl_type = self.current_impl_type.clone();
1395         expand_type(t, self, impl_type)
1396     }
1397
1398     fn new_span(&mut self, span: Span) -> Span {
1399         new_span(self.cx, span)
1400     }
1401 }
1402
1403 fn new_span(cx: &ExtCtxt, sp: Span) -> Span {
1404     /* this discards information in the case of macro-defining macros */
1405     Span {
1406         lo: sp.lo,
1407         hi: sp.hi,
1408         expn_id: cx.backtrace(),
1409     }
1410 }
1411
1412 pub struct ExpansionConfig<'feat> {
1413     pub crate_name: String,
1414     pub features: Option<&'feat Features>,
1415     pub recursion_limit: usize,
1416 }
1417
1418 impl<'feat> ExpansionConfig<'feat> {
1419     pub fn default(crate_name: String) -> ExpansionConfig<'static> {
1420         ExpansionConfig {
1421             crate_name: crate_name,
1422             features: None,
1423             recursion_limit: 64,
1424         }
1425     }
1426
1427     pub fn enable_quotes(&self) -> bool {
1428         match self.features {
1429             Some(&Features { allow_quote: true, .. }) => true,
1430             _ => false,
1431         }
1432     }
1433
1434     pub fn enable_asm(&self) -> bool {
1435         match self.features {
1436             Some(&Features { allow_asm: true, .. }) => true,
1437             _ => false,
1438         }
1439     }
1440
1441     pub fn enable_log_syntax(&self) -> bool {
1442         match self.features {
1443             Some(&Features { allow_log_syntax: true, .. }) => true,
1444             _ => false,
1445         }
1446     }
1447
1448     pub fn enable_concat_idents(&self) -> bool {
1449         match self.features {
1450             Some(&Features { allow_concat_idents: true, .. }) => true,
1451             _ => false,
1452         }
1453     }
1454
1455     pub fn enable_trace_macros(&self) -> bool {
1456         match self.features {
1457             Some(&Features { allow_trace_macros: true, .. }) => true,
1458             _ => false,
1459         }
1460     }
1461 }
1462
1463 pub fn expand_crate<'feat>(parse_sess: &parse::ParseSess,
1464                            cfg: ExpansionConfig<'feat>,
1465                            // these are the macros being imported to this crate:
1466                            imported_macros: Vec<ast::MacroDef>,
1467                            user_exts: Vec<NamedSyntaxExtension>,
1468                            c: Crate) -> Crate {
1469     let mut cx = ExtCtxt::new(parse_sess, c.config.clone(), cfg);
1470     cx.use_std = std_inject::use_std(&c);
1471
1472     let mut expander = MacroExpander::new(&mut cx);
1473
1474     for def in imported_macros {
1475         expander.cx.insert_macro(def);
1476     }
1477
1478     for (name, extension) in user_exts {
1479         expander.cx.syntax_env.insert(name, extension);
1480     }
1481
1482     let mut ret = expander.fold_crate(c);
1483     ret.exported_macros = expander.cx.exported_macros.clone();
1484     parse_sess.span_diagnostic.handler().abort_if_errors();
1485     return ret;
1486 }
1487
1488 // HYGIENIC CONTEXT EXTENSION:
1489 // all of these functions are for walking over
1490 // ASTs and making some change to the context of every
1491 // element that has one. a CtxtFn is a trait-ified
1492 // version of a closure in (SyntaxContext -> SyntaxContext).
1493 // the ones defined here include:
1494 // Marker - add a mark to a context
1495
1496 // A Marker adds the given mark to the syntax context
1497 struct Marker { mark: Mrk }
1498
1499 impl Folder for Marker {
1500     fn fold_ident(&mut self, id: Ident) -> Ident {
1501         ast::Ident {
1502             name: id.name,
1503             ctxt: mtwt::apply_mark(self.mark, id.ctxt)
1504         }
1505     }
1506     fn fold_mac(&mut self, Spanned {node, span}: ast::Mac) -> ast::Mac {
1507         Spanned {
1508             node: match node {
1509                 MacInvocTT(path, tts, ctxt) => {
1510                     MacInvocTT(self.fold_path(path),
1511                                self.fold_tts(&tts[..]),
1512                                mtwt::apply_mark(self.mark, ctxt))
1513                 }
1514             },
1515             span: span,
1516         }
1517     }
1518 }
1519
1520 // apply a given mark to the given token trees. Used prior to expansion of a macro.
1521 fn mark_tts(tts: &[TokenTree], m: Mrk) -> Vec<TokenTree> {
1522     noop_fold_tts(tts, &mut Marker{mark:m})
1523 }
1524
1525 // apply a given mark to the given expr. Used following the expansion of a macro.
1526 fn mark_expr(expr: P<ast::Expr>, m: Mrk) -> P<ast::Expr> {
1527     Marker{mark:m}.fold_expr(expr)
1528 }
1529
1530 // apply a given mark to the given pattern. Used following the expansion of a macro.
1531 fn mark_pat(pat: P<ast::Pat>, m: Mrk) -> P<ast::Pat> {
1532     Marker{mark:m}.fold_pat(pat)
1533 }
1534
1535 // apply a given mark to the given stmt. Used following the expansion of a macro.
1536 fn mark_stmt(expr: P<ast::Stmt>, m: Mrk) -> P<ast::Stmt> {
1537     Marker{mark:m}.fold_stmt(expr)
1538         .expect_one("marking a stmt didn't return exactly one stmt")
1539 }
1540
1541 // apply a given mark to the given item. Used following the expansion of a macro.
1542 fn mark_item(expr: P<ast::Item>, m: Mrk) -> P<ast::Item> {
1543     Marker{mark:m}.fold_item(expr)
1544         .expect_one("marking an item didn't return exactly one item")
1545 }
1546
1547 // apply a given mark to the given item. Used following the expansion of a macro.
1548 fn mark_method(expr: P<ast::Method>, m: Mrk) -> P<ast::Method> {
1549     Marker{mark:m}.fold_method(expr)
1550         .expect_one("marking an item didn't return exactly one method")
1551 }
1552
1553 /// Check that there are no macro invocations left in the AST:
1554 pub fn check_for_macros(sess: &parse::ParseSess, krate: &ast::Crate) {
1555     visit::walk_crate(&mut MacroExterminator{sess:sess}, krate);
1556 }
1557
1558 /// A visitor that ensures that no macro invocations remain in an AST.
1559 struct MacroExterminator<'a>{
1560     sess: &'a parse::ParseSess
1561 }
1562
1563 impl<'a, 'v> Visitor<'v> for MacroExterminator<'a> {
1564     fn visit_mac(&mut self, mac: &ast::Mac) {
1565         self.sess.span_diagnostic.span_bug(mac.span,
1566                                            "macro exterminator: expected AST \
1567                                            with no macro invocations");
1568     }
1569 }
1570
1571
1572 #[cfg(test)]
1573 mod test {
1574     use super::{pattern_bindings, expand_crate};
1575     use super::{PatIdentFinder, IdentRenamer, PatIdentRenamer, ExpansionConfig};
1576     use ast;
1577     use ast::Name;
1578     use codemap;
1579     use ext::mtwt;
1580     use fold::Folder;
1581     use parse;
1582     use parse::token;
1583     use util::parser_testing::{string_to_parser};
1584     use util::parser_testing::{string_to_pat, string_to_crate, strs_to_idents};
1585     use visit;
1586     use visit::Visitor;
1587
1588     // a visitor that extracts the paths
1589     // from a given thingy and puts them in a mutable
1590     // array (passed in to the traversal)
1591     #[derive(Clone)]
1592     struct PathExprFinderContext {
1593         path_accumulator: Vec<ast::Path> ,
1594     }
1595
1596     impl<'v> Visitor<'v> for PathExprFinderContext {
1597         fn visit_expr(&mut self, expr: &ast::Expr) {
1598             match expr.node {
1599                 ast::ExprPath(ref p) => {
1600                     self.path_accumulator.push(p.clone());
1601                     // not calling visit_path, but it should be fine.
1602                 }
1603                 _ => visit::walk_expr(self, expr)
1604             }
1605         }
1606     }
1607
1608     // find the variable references in a crate
1609     fn crate_varrefs(the_crate : &ast::Crate) -> Vec<ast::Path> {
1610         let mut path_finder = PathExprFinderContext{path_accumulator:Vec::new()};
1611         visit::walk_crate(&mut path_finder, the_crate);
1612         path_finder.path_accumulator
1613     }
1614
1615     /// A Visitor that extracts the identifiers from a thingy.
1616     // as a side note, I'm starting to want to abstract over these....
1617     struct IdentFinder {
1618         ident_accumulator: Vec<ast::Ident>
1619     }
1620
1621     impl<'v> Visitor<'v> for IdentFinder {
1622         fn visit_ident(&mut self, _: codemap::Span, id: ast::Ident){
1623             self.ident_accumulator.push(id);
1624         }
1625     }
1626
1627     /// Find the idents in a crate
1628     fn crate_idents(the_crate: &ast::Crate) -> Vec<ast::Ident> {
1629         let mut ident_finder = IdentFinder{ident_accumulator: Vec::new()};
1630         visit::walk_crate(&mut ident_finder, the_crate);
1631         ident_finder.ident_accumulator
1632     }
1633
1634     // these following tests are quite fragile, in that they don't test what
1635     // *kind* of failure occurs.
1636
1637     fn test_ecfg() -> ExpansionConfig<'static> {
1638         ExpansionConfig::default("test".to_string())
1639     }
1640
1641     // make sure that macros can't escape fns
1642     #[should_fail]
1643     #[test] fn macros_cant_escape_fns_test () {
1644         let src = "fn bogus() {macro_rules! z (() => (3+4));}\
1645                    fn inty() -> i32 { z!() }".to_string();
1646         let sess = parse::new_parse_sess();
1647         let crate_ast = parse::parse_crate_from_source_str(
1648             "<test>".to_string(),
1649             src,
1650             Vec::new(), &sess);
1651         // should fail:
1652         expand_crate(&sess,test_ecfg(),vec!(),vec!(),crate_ast);
1653     }
1654
1655     // make sure that macros can't escape modules
1656     #[should_fail]
1657     #[test] fn macros_cant_escape_mods_test () {
1658         let src = "mod foo {macro_rules! z (() => (3+4));}\
1659                    fn inty() -> i32 { z!() }".to_string();
1660         let sess = parse::new_parse_sess();
1661         let crate_ast = parse::parse_crate_from_source_str(
1662             "<test>".to_string(),
1663             src,
1664             Vec::new(), &sess);
1665         expand_crate(&sess,test_ecfg(),vec!(),vec!(),crate_ast);
1666     }
1667
1668     // macro_use modules should allow macros to escape
1669     #[test] fn macros_can_escape_flattened_mods_test () {
1670         let src = "#[macro_use] mod foo {macro_rules! z (() => (3+4));}\
1671                    fn inty() -> i32 { z!() }".to_string();
1672         let sess = parse::new_parse_sess();
1673         let crate_ast = parse::parse_crate_from_source_str(
1674             "<test>".to_string(),
1675             src,
1676             Vec::new(), &sess);
1677         expand_crate(&sess, test_ecfg(), vec!(), vec!(), crate_ast);
1678     }
1679
1680     fn expand_crate_str(crate_str: String) -> ast::Crate {
1681         let ps = parse::new_parse_sess();
1682         let crate_ast = string_to_parser(&ps, crate_str).parse_crate_mod();
1683         // the cfg argument actually does matter, here...
1684         expand_crate(&ps,test_ecfg(),vec!(),vec!(),crate_ast)
1685     }
1686
1687     // find the pat_ident paths in a crate
1688     fn crate_bindings(the_crate : &ast::Crate) -> Vec<ast::Ident> {
1689         let mut name_finder = PatIdentFinder{ident_accumulator:Vec::new()};
1690         visit::walk_crate(&mut name_finder, the_crate);
1691         name_finder.ident_accumulator
1692     }
1693
1694     #[test] fn macro_tokens_should_match(){
1695         expand_crate_str(
1696             "macro_rules! m((a)=>(13)) ;fn main(){m!(a);}".to_string());
1697     }
1698
1699     // should be able to use a bound identifier as a literal in a macro definition:
1700     #[test] fn self_macro_parsing(){
1701         expand_crate_str(
1702             "macro_rules! foo ((zz) => (287;));
1703             fn f(zz: i32) {foo!(zz);}".to_string()
1704             );
1705     }
1706
1707     // renaming tests expand a crate and then check that the bindings match
1708     // the right varrefs. The specification of the test case includes the
1709     // text of the crate, and also an array of arrays.  Each element in the
1710     // outer array corresponds to a binding in the traversal of the AST
1711     // induced by visit.  Each of these arrays contains a list of indexes,
1712     // interpreted as the varrefs in the varref traversal that this binding
1713     // should match.  So, for instance, in a program with two bindings and
1714     // three varrefs, the array ~[~[1,2],~[0]] would indicate that the first
1715     // binding should match the second two varrefs, and the second binding
1716     // should match the first varref.
1717     //
1718     // Put differently; this is a sparse representation of a boolean matrix
1719     // indicating which bindings capture which identifiers.
1720     //
1721     // Note also that this matrix is dependent on the implicit ordering of
1722     // the bindings and the varrefs discovered by the name-finder and the path-finder.
1723     //
1724     // The comparisons are done post-mtwt-resolve, so we're comparing renamed
1725     // names; differences in marks don't matter any more.
1726     //
1727     // oog... I also want tests that check "bound-identifier-=?". That is,
1728     // not just "do these have the same name", but "do they have the same
1729     // name *and* the same marks"? Understanding this is really pretty painful.
1730     // in principle, you might want to control this boolean on a per-varref basis,
1731     // but that would make things even harder to understand, and might not be
1732     // necessary for thorough testing.
1733     type RenamingTest = (&'static str, Vec<Vec<usize>>, bool);
1734
1735     #[test]
1736     fn automatic_renaming () {
1737         let tests: Vec<RenamingTest> =
1738             vec!(// b & c should get new names throughout, in the expr too:
1739                 ("fn a() -> i32 { let b = 13; let c = b; b+c }",
1740                  vec!(vec!(0,1),vec!(2)), false),
1741                 // both x's should be renamed (how is this causing a bug?)
1742                 ("fn main () {let x: i32 = 13;x;}",
1743                  vec!(vec!(0)), false),
1744                 // the use of b after the + should be renamed, the other one not:
1745                 ("macro_rules! f (($x:ident) => (b + $x)); fn a() -> i32 { let b = 13; f!(b)}",
1746                  vec!(vec!(1)), false),
1747                 // the b before the plus should not be renamed (requires marks)
1748                 ("macro_rules! f (($x:ident) => ({let b=9; ($x + b)})); fn a() -> i32 { f!(b)}",
1749                  vec!(vec!(1)), false),
1750                 // the marks going in and out of letty should cancel, allowing that $x to
1751                 // capture the one following the semicolon.
1752                 // this was an awesome test case, and caught a *lot* of bugs.
1753                 ("macro_rules! letty(($x:ident) => (let $x = 15;));
1754                   macro_rules! user(($x:ident) => ({letty!($x); $x}));
1755                   fn main() -> i32 {user!(z)}",
1756                  vec!(vec!(0)), false)
1757                 );
1758         for (idx,s) in tests.iter().enumerate() {
1759             run_renaming_test(s,idx);
1760         }
1761     }
1762
1763     // no longer a fixme #8062: this test exposes a *potential* bug; our system does
1764     // not behave exactly like MTWT, but a conversation with Matthew Flatt
1765     // suggests that this can only occur in the presence of local-expand, which
1766     // we have no plans to support. ... unless it's needed for item hygiene....
1767     #[ignore]
1768     #[test] fn issue_8062(){
1769         run_renaming_test(
1770             &("fn main() {let hrcoo = 19; macro_rules! getx(()=>(hrcoo)); getx!();}",
1771               vec!(vec!(0)), true), 0)
1772     }
1773
1774     // FIXME #6994:
1775     // the z flows into and out of two macros (g & f) along one path, and one
1776     // (just g) along the other, so the result of the whole thing should
1777     // be "let z_123 = 3; z_123"
1778     #[ignore]
1779     #[test] fn issue_6994(){
1780         run_renaming_test(
1781             &("macro_rules! g (($x:ident) =>
1782               ({macro_rules! f(($y:ident)=>({let $y=3;$x}));f!($x)}));
1783               fn a(){g!(z)}",
1784               vec!(vec!(0)),false),
1785             0)
1786     }
1787
1788     // match variable hygiene. Should expand into
1789     // fn z() {match 8 {x_1 => {match 9 {x_2 | x_2 if x_2 == x_1 => x_2 + x_1}}}}
1790     #[test] fn issue_9384(){
1791         run_renaming_test(
1792             &("macro_rules! bad_macro (($ex:expr) => ({match 9 {x | x if x == $ex => x + $ex}}));
1793               fn z() {match 8 {x => bad_macro!(x)}}",
1794               // NB: the third "binding" is the repeat of the second one.
1795               vec!(vec!(1,3),vec!(0,2),vec!(0,2)),
1796               true),
1797             0)
1798     }
1799
1800     // interpolated nodes weren't getting labeled.
1801     // should expand into
1802     // fn main(){let g1_1 = 13; g1_1}}
1803     #[test] fn pat_expand_issue_15221(){
1804         run_renaming_test(
1805             &("macro_rules! inner ( ($e:pat ) => ($e));
1806               macro_rules! outer ( ($e:pat ) => (inner!($e)));
1807               fn main() { let outer!(g) = 13; g;}",
1808               vec!(vec!(0)),
1809               true),
1810             0)
1811     }
1812
1813     // create a really evil test case where a $x appears inside a binding of $x
1814     // but *shouldn't* bind because it was inserted by a different macro....
1815     // can't write this test case until we have macro-generating macros.
1816
1817     // method arg hygiene
1818     // method expands to fn get_x(&self_0, x_1: i32) {self_0 + self_2 + x_3 + x_1}
1819     #[test] fn method_arg_hygiene(){
1820         run_renaming_test(
1821             &("macro_rules! inject_x (()=>(x));
1822               macro_rules! inject_self (()=>(self));
1823               struct A;
1824               impl A{fn get_x(&self, x: i32) {self + inject_self!() + inject_x!() + x;} }",
1825               vec!(vec!(0),vec!(3)),
1826               true),
1827             0)
1828     }
1829
1830     // ooh, got another bite?
1831     // expands to struct A; impl A {fn thingy(&self_1) {self_1;}}
1832     #[test] fn method_arg_hygiene_2(){
1833         run_renaming_test(
1834             &("struct A;
1835               macro_rules! add_method (($T:ty) =>
1836               (impl $T {  fn thingy(&self) {self;} }));
1837               add_method!(A);",
1838               vec!(vec!(0)),
1839               true),
1840             0)
1841     }
1842
1843     // item fn hygiene
1844     // expands to fn q(x_1: i32){fn g(x_2: i32){x_2 + x_1};}
1845     #[test] fn issue_9383(){
1846         run_renaming_test(
1847             &("macro_rules! bad_macro (($ex:expr) => (fn g(x: i32){ x + $ex }));
1848               fn q(x: i32) { bad_macro!(x); }",
1849               vec!(vec!(1),vec!(0)),true),
1850             0)
1851     }
1852
1853     // closure arg hygiene (ExprClosure)
1854     // expands to fn f(){(|x_1 : i32| {(x_2 + x_1)})(3);}
1855     #[test] fn closure_arg_hygiene(){
1856         run_renaming_test(
1857             &("macro_rules! inject_x (()=>(x));
1858             fn f(){(|x : i32| {(inject_x!() + x)})(3);}",
1859               vec!(vec!(1)),
1860               true),
1861             0)
1862     }
1863
1864     // macro_rules in method position. Sadly, unimplemented.
1865     #[test] fn macro_in_method_posn(){
1866         expand_crate_str(
1867             "macro_rules! my_method (() => (fn thirteen(&self) -> i32 {13}));
1868             struct A;
1869             impl A{ my_method!(); }
1870             fn f(){A.thirteen;}".to_string());
1871     }
1872
1873     // another nested macro
1874     // expands to impl Entries {fn size_hint(&self_1) {self_1;}
1875     #[test] fn item_macro_workaround(){
1876         run_renaming_test(
1877             &("macro_rules! item { ($i:item) => {$i}}
1878               struct Entries;
1879               macro_rules! iterator_impl {
1880               () => { item!( impl Entries { fn size_hint(&self) { self;}});}}
1881               iterator_impl! { }",
1882               vec!(vec!(0)), true),
1883             0)
1884     }
1885
1886     // run one of the renaming tests
1887     fn run_renaming_test(t: &RenamingTest, test_idx: usize) {
1888         let invalid_name = token::special_idents::invalid.name;
1889         let (teststr, bound_connections, bound_ident_check) = match *t {
1890             (ref str,ref conns, bic) => (str.to_string(), conns.clone(), bic)
1891         };
1892         let cr = expand_crate_str(teststr.to_string());
1893         let bindings = crate_bindings(&cr);
1894         let varrefs = crate_varrefs(&cr);
1895
1896         // must be one check clause for each binding:
1897         assert_eq!(bindings.len(),bound_connections.len());
1898         for (binding_idx,shouldmatch) in bound_connections.iter().enumerate() {
1899             let binding_name = mtwt::resolve(bindings[binding_idx]);
1900             let binding_marks = mtwt::marksof(bindings[binding_idx].ctxt, invalid_name);
1901             // shouldmatch can't name varrefs that don't exist:
1902             assert!((shouldmatch.len() == 0) ||
1903                     (varrefs.len() > *shouldmatch.iter().max().unwrap()));
1904             for (idx,varref) in varrefs.iter().enumerate() {
1905                 let print_hygiene_debug_info = || {
1906                     // good lord, you can't make a path with 0 segments, can you?
1907                     let final_varref_ident = match varref.segments.last() {
1908                         Some(pathsegment) => pathsegment.identifier,
1909                         None => panic!("varref with 0 path segments?")
1910                     };
1911                     let varref_name = mtwt::resolve(final_varref_ident);
1912                     let varref_idents : Vec<ast::Ident>
1913                         = varref.segments.iter().map(|s| s.identifier)
1914                         .collect();
1915                     println!("varref #{}: {:?}, resolves to {}",idx, varref_idents, varref_name);
1916                     let string = token::get_ident(final_varref_ident);
1917                     println!("varref's first segment's string: \"{}\"", &string[..]);
1918                     println!("binding #{}: {}, resolves to {}",
1919                              binding_idx, bindings[binding_idx], binding_name);
1920                     mtwt::with_sctable(|x| mtwt::display_sctable(x));
1921                 };
1922                 if shouldmatch.contains(&idx) {
1923                     // it should be a path of length 1, and it should
1924                     // be free-identifier=? or bound-identifier=? to the given binding
1925                     assert_eq!(varref.segments.len(),1);
1926                     let varref_name = mtwt::resolve(varref.segments[0].identifier);
1927                     let varref_marks = mtwt::marksof(varref.segments[0]
1928                                                            .identifier
1929                                                            .ctxt,
1930                                                      invalid_name);
1931                     if !(varref_name==binding_name) {
1932                         println!("uh oh, should match but doesn't:");
1933                         print_hygiene_debug_info();
1934                     }
1935                     assert_eq!(varref_name,binding_name);
1936                     if bound_ident_check {
1937                         // we're checking bound-identifier=?, and the marks
1938                         // should be the same, too:
1939                         assert_eq!(varref_marks,binding_marks.clone());
1940                     }
1941                 } else {
1942                     let varref_name = mtwt::resolve(varref.segments[0].identifier);
1943                     let fail = (varref.segments.len() == 1)
1944                         && (varref_name == binding_name);
1945                     // temp debugging:
1946                     if fail {
1947                         println!("failure on test {}",test_idx);
1948                         println!("text of test case: \"{}\"", teststr);
1949                         println!("");
1950                         println!("uh oh, matches but shouldn't:");
1951                         print_hygiene_debug_info();
1952                     }
1953                     assert!(!fail);
1954                 }
1955             }
1956         }
1957     }
1958
1959     #[test] fn fmt_in_macro_used_inside_module_macro() {
1960         let crate_str = "macro_rules! fmt_wrap(($b:expr)=>($b.to_string()));
1961 macro_rules! foo_module (() => (mod generated { fn a() { let xx = 147; fmt_wrap!(xx);}}));
1962 foo_module!();
1963 ".to_string();
1964         let cr = expand_crate_str(crate_str);
1965         // find the xx binding
1966         let bindings = crate_bindings(&cr);
1967         let cxbinds: Vec<&ast::Ident> =
1968             bindings.iter().filter(|b| {
1969                 let ident = token::get_ident(**b);
1970                 let string = &ident[..];
1971                 "xx" == string
1972             }).collect();
1973         let cxbinds: &[&ast::Ident] = &cxbinds[..];
1974         let cxbind = match cxbinds {
1975             [b] => b,
1976             _ => panic!("expected just one binding for ext_cx")
1977         };
1978         let resolved_binding = mtwt::resolve(*cxbind);
1979         let varrefs = crate_varrefs(&cr);
1980
1981         // the xx binding should bind all of the xx varrefs:
1982         for (idx,v) in varrefs.iter().filter(|p| {
1983             p.segments.len() == 1
1984             && "xx" == &token::get_ident(p.segments[0].identifier)[]
1985         }).enumerate() {
1986             if mtwt::resolve(v.segments[0].identifier) != resolved_binding {
1987                 println!("uh oh, xx binding didn't match xx varref:");
1988                 println!("this is xx varref \\# {}", idx);
1989                 println!("binding: {}", cxbind);
1990                 println!("resolves to: {}", resolved_binding);
1991                 println!("varref: {}", v.segments[0].identifier);
1992                 println!("resolves to: {}",
1993                          mtwt::resolve(v.segments[0].identifier));
1994                 mtwt::with_sctable(|x| mtwt::display_sctable(x));
1995             }
1996             assert_eq!(mtwt::resolve(v.segments[0].identifier),
1997                        resolved_binding);
1998         };
1999     }
2000
2001     #[test]
2002     fn pat_idents(){
2003         let pat = string_to_pat(
2004             "(a,Foo{x:c @ (b,9),y:Bar(4,d)})".to_string());
2005         let idents = pattern_bindings(&*pat);
2006         assert_eq!(idents, strs_to_idents(vec!("a","c","b","d")));
2007     }
2008
2009     // test the list of identifier patterns gathered by the visitor. Note that
2010     // 'None' is listed as an identifier pattern because we don't yet know that
2011     // it's the name of a 0-ary variant, and that 'i' appears twice in succession.
2012     #[test]
2013     fn crate_bindings_test(){
2014         let the_crate = string_to_crate("fn main (a: i32) -> i32 {|b| {
2015         match 34 {None => 3, Some(i) | i => j, Foo{k:z,l:y} => \"banana\"}} }".to_string());
2016         let idents = crate_bindings(&the_crate);
2017         assert_eq!(idents, strs_to_idents(vec!("a","b","None","i","i","z","y")));
2018     }
2019
2020     // test the IdentRenamer directly
2021     #[test]
2022     fn ident_renamer_test () {
2023         let the_crate = string_to_crate("fn f(x: i32){let x = x; x}".to_string());
2024         let f_ident = token::str_to_ident("f");
2025         let x_ident = token::str_to_ident("x");
2026         let int_ident = token::str_to_ident("i32");
2027         let renames = vec!((x_ident,Name(16)));
2028         let mut renamer = IdentRenamer{renames: &renames};
2029         let renamed_crate = renamer.fold_crate(the_crate);
2030         let idents = crate_idents(&renamed_crate);
2031         let resolved : Vec<ast::Name> = idents.iter().map(|id| mtwt::resolve(*id)).collect();
2032         assert_eq!(resolved,vec!(f_ident.name,Name(16),int_ident.name,Name(16),Name(16),Name(16)));
2033     }
2034
2035     // test the PatIdentRenamer; only PatIdents get renamed
2036     #[test]
2037     fn pat_ident_renamer_test () {
2038         let the_crate = string_to_crate("fn f(x: i32){let x = x; x}".to_string());
2039         let f_ident = token::str_to_ident("f");
2040         let x_ident = token::str_to_ident("x");
2041         let int_ident = token::str_to_ident("i32");
2042         let renames = vec!((x_ident,Name(16)));
2043         let mut renamer = PatIdentRenamer{renames: &renames};
2044         let renamed_crate = renamer.fold_crate(the_crate);
2045         let idents = crate_idents(&renamed_crate);
2046         let resolved : Vec<ast::Name> = idents.iter().map(|id| mtwt::resolve(*id)).collect();
2047         let x_name = x_ident.name;
2048         assert_eq!(resolved,vec!(f_ident.name,Name(16),int_ident.name,Name(16),x_name,x_name));
2049     }
2050
2051
2052 }