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