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