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