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