src/libsyntax/fold.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! A Folder represents an AST->AST fold; it accepts an AST piece,
  12 //! and returns a piece of the same type. So, for instance, macro
  13 //! expansion is a Folder that walks over an AST and produces another
  14 //! AST.
  15 //!
  16 //! Note: using a Folder (other than the MacroExpander Folder) on
  17 //! an AST before macro expansion is probably a bad idea. For instance,
  18 //! a folder renaming item names in a module will miss all of those
  19 //! that are created by the expansion of a macro.
  20
  21 use ast::*;
  22 use ast;
  23 use ast_util;
  24 use codemap::{respan, Span, Spanned};
  25 use owned_slice::OwnedSlice;
  26 use parse::token;
  27 use ptr::P;
  28 use std::ptr;
  29 use util::small_vector::SmallVector;
  30
  31 use std::rc::Rc;
  32
  33 // This could have a better place to live.
  34 pub trait MoveMap<T> {
  35     fn move_map<F>(self, f: F) -> Self where F: FnMut(T) -> T;
  36 }
  37
  38 impl<T> MoveMap<T> for Vec<T> {
  39     fn move_map<F>(mut self, mut f: F) -> Vec<T> where F: FnMut(T) -> T {
  40         for p in self.iter_mut() {
  41             unsafe {
  42                 // FIXME(#5016) this shouldn't need to zero to be safe.
  43                 ptr::write(p, f(ptr::read_and_zero(p)));
  44             }
  45         }
  46         self
  47     }
  48 }
  49
  50 impl<T> MoveMap<T> for OwnedSlice<T> {
  51     fn move_map<F>(self, f: F) -> OwnedSlice<T> where F: FnMut(T) -> T {
  52         OwnedSlice::from_vec(self.into_vec().move_map(f))
  53     }
  54 }
  55
  56 pub trait Folder : Sized {
  57     // Any additions to this trait should happen in form
  58     // of a call to a public `noop_*` function that only calls
  59     // out to the folder again, not other `noop_*` functions.
  60     //
  61     // This is a necessary API workaround to the problem of not
  62     // being able to call out to the super default method
  63     // in an overridden default method.
  64
  65     fn fold_crate(&mut self, c: Crate) -> Crate {
  66         noop_fold_crate(c, self)
  67     }
  68
  69     fn fold_meta_items(&mut self, meta_items: Vec<P<MetaItem>>) -> Vec<P<MetaItem>> {
  70         noop_fold_meta_items(meta_items, self)
  71     }
  72
  73     fn fold_meta_item(&mut self, meta_item: P<MetaItem>) -> P<MetaItem> {
  74         noop_fold_meta_item(meta_item, self)
  75     }
  76
  77     fn fold_view_path(&mut self, view_path: P<ViewPath>) -> P<ViewPath> {
  78         noop_fold_view_path(view_path, self)
  79     }
  80
  81     fn fold_view_item(&mut self, vi: ViewItem) -> ViewItem {
  82         noop_fold_view_item(vi, self)
  83     }
  84
  85     fn fold_foreign_item(&mut self, ni: P<ForeignItem>) -> P<ForeignItem> {
  86         noop_fold_foreign_item(ni, self)
  87     }
  88
  89     fn fold_item(&mut self, i: P<Item>) -> SmallVector<P<Item>> {
  90         noop_fold_item(i, self)
  91     }
  92
  93     fn fold_item_simple(&mut self, i: Item) -> Item {
  94         noop_fold_item_simple(i, self)
  95     }
  96
  97     fn fold_struct_field(&mut self, sf: StructField) -> StructField {
  98         noop_fold_struct_field(sf, self)
  99     }
 100
 101     fn fold_item_underscore(&mut self, i: Item_) -> Item_ {
 102         noop_fold_item_underscore(i, self)
 103     }
 104
 105     fn fold_trait_item(&mut self, i: TraitItem) -> SmallVector<TraitItem> {
 106         noop_fold_trait_item(i, self)
 107     }
 108
 109     fn fold_impl_item(&mut self, i: ImplItem) -> SmallVector<ImplItem> {
 110         noop_fold_impl_item(i, self)
 111     }
 112
 113     fn fold_fn_decl(&mut self, d: P<FnDecl>) -> P<FnDecl> {
 114         noop_fold_fn_decl(d, self)
 115     }
 116
 117     fn fold_type_method(&mut self, m: TypeMethod) -> TypeMethod {
 118         noop_fold_type_method(m, self)
 119     }
 120
 121     fn fold_method(&mut self, m: P<Method>) -> SmallVector<P<Method>> {
 122         noop_fold_method(m, self)
 123     }
 124
 125     fn fold_block(&mut self, b: P<Block>) -> P<Block> {
 126         noop_fold_block(b, self)
 127     }
 128
 129     fn fold_stmt(&mut self, s: P<Stmt>) -> SmallVector<P<Stmt>> {
 130         s.and_then(|s| noop_fold_stmt(s, self))
 131     }
 132
 133     fn fold_arm(&mut self, a: Arm) -> Arm {
 134         noop_fold_arm(a, self)
 135     }
 136
 137     fn fold_pat(&mut self, p: P<Pat>) -> P<Pat> {
 138         noop_fold_pat(p, self)
 139     }
 140
 141     fn fold_decl(&mut self, d: P<Decl>) -> SmallVector<P<Decl>> {
 142         noop_fold_decl(d, self)
 143     }
 144
 145     fn fold_expr(&mut self, e: P<Expr>) -> P<Expr> {
 146         e.map(|e| noop_fold_expr(e, self))
 147     }
 148
 149     fn fold_ty(&mut self, t: P<Ty>) -> P<Ty> {
 150         noop_fold_ty(t, self)
 151     }
 152
 153     fn fold_qpath(&mut self, t: P<QPath>) -> P<QPath> {
 154         noop_fold_qpath(t, self)
 155     }
 156
 157     fn fold_ty_binding(&mut self, t: P<TypeBinding>) -> P<TypeBinding> {
 158         noop_fold_ty_binding(t, self)
 159     }
 160
 161     fn fold_mod(&mut self, m: Mod) -> Mod {
 162         noop_fold_mod(m, self)
 163     }
 164
 165     fn fold_foreign_mod(&mut self, nm: ForeignMod) -> ForeignMod {
 166         noop_fold_foreign_mod(nm, self)
 167     }
 168
 169     fn fold_variant(&mut self, v: P<Variant>) -> P<Variant> {
 170         noop_fold_variant(v, self)
 171     }
 172
 173     fn fold_ident(&mut self, i: Ident) -> Ident {
 174         noop_fold_ident(i, self)
 175     }
 176
 177     fn fold_uint(&mut self, i: uint) -> uint {
 178         noop_fold_uint(i, self)
 179     }
 180
 181     fn fold_path(&mut self, p: Path) -> Path {
 182         noop_fold_path(p, self)
 183     }
 184
 185     fn fold_path_parameters(&mut self, p: PathParameters) -> PathParameters {
 186         noop_fold_path_parameters(p, self)
 187     }
 188
 189     fn fold_angle_bracketed_parameter_data(&mut self, p: AngleBracketedParameterData)
 190                                            -> AngleBracketedParameterData
 191     {
 192         noop_fold_angle_bracketed_parameter_data(p, self)
 193     }
 194
 195     fn fold_parenthesized_parameter_data(&mut self, p: ParenthesizedParameterData)
 196                                          -> ParenthesizedParameterData
 197     {
 198         noop_fold_parenthesized_parameter_data(p, self)
 199     }
 200
 201     fn fold_local(&mut self, l: P<Local>) -> P<Local> {
 202         noop_fold_local(l, self)
 203     }
 204
 205     fn fold_mac(&mut self, _mac: Mac) -> Mac {
 206         panic!("fold_mac disabled by default");
 207         // NB: see note about macros above.
 208         // if you really want a folder that
 209         // works on macros, use this
 210         // definition in your trait impl:
 211         // fold::noop_fold_mac(_mac, self)
 212     }
 213
 214     fn fold_explicit_self(&mut self, es: ExplicitSelf) -> ExplicitSelf {
 215         noop_fold_explicit_self(es, self)
 216     }
 217
 218     fn fold_explicit_self_underscore(&mut self, es: ExplicitSelf_) -> ExplicitSelf_ {
 219         noop_fold_explicit_self_underscore(es, self)
 220     }
 221
 222     fn fold_lifetime(&mut self, l: Lifetime) -> Lifetime {
 223         noop_fold_lifetime(l, self)
 224     }
 225
 226     fn fold_lifetime_def(&mut self, l: LifetimeDef) -> LifetimeDef {
 227         noop_fold_lifetime_def(l, self)
 228     }
 229
 230     fn fold_attribute(&mut self, at: Attribute) -> Attribute {
 231         noop_fold_attribute(at, self)
 232     }
 233
 234     fn fold_arg(&mut self, a: Arg) -> Arg {
 235         noop_fold_arg(a, self)
 236     }
 237
 238     fn fold_generics(&mut self, generics: Generics) -> Generics {
 239         noop_fold_generics(generics, self)
 240     }
 241
 242     fn fold_trait_ref(&mut self, p: TraitRef) -> TraitRef {
 243         noop_fold_trait_ref(p, self)
 244     }
 245
 246     fn fold_poly_trait_ref(&mut self, p: PolyTraitRef) -> PolyTraitRef {
 247         noop_fold_poly_trait_ref(p, self)
 248     }
 249
 250     fn fold_struct_def(&mut self, struct_def: P<StructDef>) -> P<StructDef> {
 251         noop_fold_struct_def(struct_def, self)
 252     }
 253
 254     fn fold_lifetimes(&mut self, lts: Vec<Lifetime>) -> Vec<Lifetime> {
 255         noop_fold_lifetimes(lts, self)
 256     }
 257
 258     fn fold_lifetime_defs(&mut self, lts: Vec<LifetimeDef>) -> Vec<LifetimeDef> {
 259         noop_fold_lifetime_defs(lts, self)
 260     }
 261
 262     fn fold_ty_param(&mut self, tp: TyParam) -> TyParam {
 263         noop_fold_ty_param(tp, self)
 264     }
 265
 266     fn fold_ty_params(&mut self, tps: OwnedSlice<TyParam>) -> OwnedSlice<TyParam> {
 267         noop_fold_ty_params(tps, self)
 268     }
 269
 270     fn fold_tt(&mut self, tt: &TokenTree) -> TokenTree {
 271         noop_fold_tt(tt, self)
 272     }
 273
 274     fn fold_tts(&mut self, tts: &[TokenTree]) -> Vec<TokenTree> {
 275         noop_fold_tts(tts, self)
 276     }
 277
 278     fn fold_token(&mut self, t: token::Token) -> token::Token {
 279         noop_fold_token(t, self)
 280     }
 281
 282     fn fold_interpolated(&mut self, nt: token::Nonterminal) -> token::Nonterminal {
 283         noop_fold_interpolated(nt, self)
 284     }
 285
 286     fn fold_opt_lifetime(&mut self, o_lt: Option<Lifetime>) -> Option<Lifetime> {
 287         noop_fold_opt_lifetime(o_lt, self)
 288     }
 289
 290     fn fold_variant_arg(&mut self, va: VariantArg) -> VariantArg {
 291         noop_fold_variant_arg(va, self)
 292     }
 293
 294     fn fold_opt_bounds(&mut self, b: Option<OwnedSlice<TyParamBound>>)
 295                        -> Option<OwnedSlice<TyParamBound>> {
 296         noop_fold_opt_bounds(b, self)
 297     }
 298
 299     fn fold_bounds(&mut self, b: OwnedSlice<TyParamBound>)
 300                        -> OwnedSlice<TyParamBound> {
 301         noop_fold_bounds(b, self)
 302     }
 303
 304     fn fold_ty_param_bound(&mut self, tpb: TyParamBound) -> TyParamBound {
 305         noop_fold_ty_param_bound(tpb, self)
 306     }
 307
 308     fn fold_mt(&mut self, mt: MutTy) -> MutTy {
 309         noop_fold_mt(mt, self)
 310     }
 311
 312     fn fold_field(&mut self, field: Field) -> Field {
 313         noop_fold_field(field, self)
 314     }
 315
 316     fn fold_where_clause(&mut self, where_clause: WhereClause)
 317                          -> WhereClause {
 318         noop_fold_where_clause(where_clause, self)
 319     }
 320
 321     fn fold_where_predicate(&mut self, where_predicate: WherePredicate)
 322                             -> WherePredicate {
 323         noop_fold_where_predicate(where_predicate, self)
 324     }
 325
 326     fn fold_typedef(&mut self, typedef: Typedef) -> Typedef {
 327         noop_fold_typedef(typedef, self)
 328     }
 329
 330     fn fold_associated_type(&mut self, associated_type: AssociatedType)
 331                             -> AssociatedType {
 332         noop_fold_associated_type(associated_type, self)
 333     }
 334
 335     fn new_id(&mut self, i: NodeId) -> NodeId {
 336         i
 337     }
 338
 339     fn new_span(&mut self, sp: Span) -> Span {
 340         sp
 341     }
 342 }
 343
 344 pub fn noop_fold_meta_items<T: Folder>(meta_items: Vec<P<MetaItem>>, fld: &mut T)
 345                                        -> Vec<P<MetaItem>> {
 346     meta_items.move_map(|x| fld.fold_meta_item(x))
 347 }
 348
 349 pub fn noop_fold_view_path<T: Folder>(view_path: P<ViewPath>, fld: &mut T) -> P<ViewPath> {
 350     view_path.map(|Spanned {node, span}| Spanned {
 351         node: match node {
 352             ViewPathSimple(ident, path, node_id) => {
 353                 let id = fld.new_id(node_id);
 354                 ViewPathSimple(ident, fld.fold_path(path), id)
 355             }
 356             ViewPathGlob(path, node_id) => {
 357                 let id = fld.new_id(node_id);
 358                 ViewPathGlob(fld.fold_path(path), id)
 359             }
 360             ViewPathList(path, path_list_idents, node_id) => {
 361                 let id = fld.new_id(node_id);
 362                 ViewPathList(fld.fold_path(path),
 363                              path_list_idents.move_map(|path_list_ident| {
 364                                 Spanned {
 365                                     node: match path_list_ident.node {
 366                                         PathListIdent { id, name } =>
 367                                             PathListIdent {
 368                                                 id: fld.new_id(id),
 369                                                 name: name
 370                                             },
 371                                         PathListMod { id } =>
 372                                             PathListMod { id: fld.new_id(id) }
 373                                     },
 374                                     span: fld.new_span(path_list_ident.span)
 375                                 }
 376                              }),
 377                              id)
 378             }
 379         },
 380         span: fld.new_span(span)
 381     })
 382 }
 383
 384 pub fn noop_fold_arm<T: Folder>(Arm {attrs, pats, guard, body}: Arm, fld: &mut T) -> Arm {
 385     Arm {
 386         attrs: attrs.move_map(|x| fld.fold_attribute(x)),
 387         pats: pats.move_map(|x| fld.fold_pat(x)),
 388         guard: guard.map(|x| fld.fold_expr(x)),
 389         body: fld.fold_expr(body),
 390     }
 391 }
 392
 393 pub fn noop_fold_decl<T: Folder>(d: P<Decl>, fld: &mut T) -> SmallVector<P<Decl>> {
 394     d.and_then(|Spanned {node, span}| match node {
 395         DeclLocal(l) => SmallVector::one(P(Spanned {
 396             node: DeclLocal(fld.fold_local(l)),
 397             span: fld.new_span(span)
 398         })),
 399         DeclItem(it) => fld.fold_item(it).into_iter().map(|i| P(Spanned {
 400             node: DeclItem(i),
 401             span: fld.new_span(span)
 402         })).collect()
 403     })
 404 }
 405
 406 pub fn noop_fold_ty_binding<T: Folder>(b: P<TypeBinding>, fld: &mut T) -> P<TypeBinding> {
 407     b.map(|TypeBinding { id, ident, ty, span }| TypeBinding {
 408         id: fld.new_id(id),
 409         ident: ident,
 410         ty: fld.fold_ty(ty),
 411         span: fld.new_span(span),
 412     })
 413 }
 414
 415 pub fn noop_fold_ty<T: Folder>(t: P<Ty>, fld: &mut T) -> P<Ty> {
 416     t.map(|Ty {id, node, span}| Ty {
 417         id: fld.new_id(id),
 418         node: match node {
 419             TyInfer => node,
 420             TyVec(ty) => TyVec(fld.fold_ty(ty)),
 421             TyPtr(mt) => TyPtr(fld.fold_mt(mt)),
 422             TyRptr(region, mt) => {
 423                 TyRptr(fld.fold_opt_lifetime(region), fld.fold_mt(mt))
 424             }
 425             TyBareFn(f) => {
 426                 TyBareFn(f.map(|BareFnTy {lifetimes, unsafety, abi, decl}| BareFnTy {
 427                     lifetimes: fld.fold_lifetime_defs(lifetimes),
 428                     unsafety: unsafety,
 429                     abi: abi,
 430                     decl: fld.fold_fn_decl(decl)
 431                 }))
 432             }
 433             TyTup(tys) => TyTup(tys.move_map(|ty| fld.fold_ty(ty))),
 434             TyParen(ty) => TyParen(fld.fold_ty(ty)),
 435             TyPath(path, id) => {
 436                 let id = fld.new_id(id);
 437                 TyPath(fld.fold_path(path), id)
 438             }
 439             TyObjectSum(ty, bounds) => {
 440                 TyObjectSum(fld.fold_ty(ty),
 441                             fld.fold_bounds(bounds))
 442             }
 443             TyQPath(qpath) => {
 444                 TyQPath(fld.fold_qpath(qpath))
 445             }
 446             TyFixedLengthVec(ty, e) => {
 447                 TyFixedLengthVec(fld.fold_ty(ty), fld.fold_expr(e))
 448             }
 449             TyTypeof(expr) => {
 450                 TyTypeof(fld.fold_expr(expr))
 451             }
 452             TyPolyTraitRef(bounds) => {
 453                 TyPolyTraitRef(bounds.move_map(|b| fld.fold_ty_param_bound(b)))
 454             }
 455         },
 456         span: fld.new_span(span)
 457     })
 458 }
 459
 460 pub fn noop_fold_qpath<T: Folder>(qpath: P<QPath>, fld: &mut T) -> P<QPath> {
 461     qpath.map(|qpath| {
 462         QPath {
 463             self_type: fld.fold_ty(qpath.self_type),
 464             trait_ref: qpath.trait_ref.map(|tr| fld.fold_trait_ref(tr)),
 465             item_path: PathSegment {
 466                 identifier: fld.fold_ident(qpath.item_path.identifier),
 467                 parameters: fld.fold_path_parameters(qpath.item_path.parameters),
 468             }
 469         }
 470     })
 471 }
 472
 473 pub fn noop_fold_foreign_mod<T: Folder>(ForeignMod {abi, view_items, items}: ForeignMod,
 474                                         fld: &mut T) -> ForeignMod {
 475     ForeignMod {
 476         abi: abi,
 477         view_items: view_items.move_map(|x| fld.fold_view_item(x)),
 478         items: items.move_map(|x| fld.fold_foreign_item(x)),
 479     }
 480 }
 481
 482 pub fn noop_fold_variant<T: Folder>(v: P<Variant>, fld: &mut T) -> P<Variant> {
 483     v.map(|Spanned {node: Variant_ {id, name, attrs, kind, disr_expr, vis}, span}| Spanned {
 484         node: Variant_ {
 485             id: fld.new_id(id),
 486             name: name,
 487             attrs: attrs.move_map(|x| fld.fold_attribute(x)),
 488             kind: match kind {
 489                 TupleVariantKind(variant_args) => {
 490                     TupleVariantKind(variant_args.move_map(|x|
 491                         fld.fold_variant_arg(x)))
 492                 }
 493                 StructVariantKind(struct_def) => {
 494                     StructVariantKind(fld.fold_struct_def(struct_def))
 495                 }
 496             },
 497             disr_expr: disr_expr.map(|e| fld.fold_expr(e)),
 498             vis: vis,
 499         },
 500         span: fld.new_span(span),
 501     })
 502 }
 503
 504 pub fn noop_fold_ident<T: Folder>(i: Ident, _: &mut T) -> Ident {
 505     i
 506 }
 507
 508 pub fn noop_fold_uint<T: Folder>(i: uint, _: &mut T) -> uint {
 509     i
 510 }
 511
 512 pub fn noop_fold_path<T: Folder>(Path {global, segments, span}: Path, fld: &mut T) -> Path {
 513     Path {
 514         global: global,
 515         segments: segments.move_map(|PathSegment {identifier, parameters}| PathSegment {
 516             identifier: fld.fold_ident(identifier),
 517             parameters: fld.fold_path_parameters(parameters),
 518         }),
 519         span: fld.new_span(span)
 520     }
 521 }
 522
 523 pub fn noop_fold_path_parameters<T: Folder>(path_parameters: PathParameters, fld: &mut T)
 524                                             -> PathParameters
 525 {
 526     match path_parameters {
 527         AngleBracketedParameters(data) =>
 528             AngleBracketedParameters(fld.fold_angle_bracketed_parameter_data(data)),
 529         ParenthesizedParameters(data) =>
 530             ParenthesizedParameters(fld.fold_parenthesized_parameter_data(data)),
 531     }
 532 }
 533
 534 pub fn noop_fold_angle_bracketed_parameter_data<T: Folder>(data: AngleBracketedParameterData,
 535                                                            fld: &mut T)
 536                                                            -> AngleBracketedParameterData
 537 {
 538     let AngleBracketedParameterData { lifetimes, types, bindings } = data;
 539     AngleBracketedParameterData { lifetimes: fld.fold_lifetimes(lifetimes),
 540                                   types: types.move_map(|ty| fld.fold_ty(ty)),
 541                                   bindings: bindings.move_map(|b| fld.fold_ty_binding(b)) }
 542 }
 543
 544 pub fn noop_fold_parenthesized_parameter_data<T: Folder>(data: ParenthesizedParameterData,
 545                                                          fld: &mut T)
 546                                                          -> ParenthesizedParameterData
 547 {
 548     let ParenthesizedParameterData { inputs, output } = data;
 549     ParenthesizedParameterData { inputs: inputs.move_map(|ty| fld.fold_ty(ty)),
 550                                  output: output.map(|ty| fld.fold_ty(ty)) }
 551 }
 552
 553 pub fn noop_fold_local<T: Folder>(l: P<Local>, fld: &mut T) -> P<Local> {
 554     l.map(|Local {id, pat, ty, init, source, span}| Local {
 555         id: fld.new_id(id),
 556         ty: ty.map(|t| fld.fold_ty(t)),
 557         pat: fld.fold_pat(pat),
 558         init: init.map(|e| fld.fold_expr(e)),
 559         source: source,
 560         span: fld.new_span(span)
 561     })
 562 }
 563
 564 pub fn noop_fold_attribute<T: Folder>(at: Attribute, fld: &mut T) -> Attribute {
 565     let Spanned {node: Attribute_ {id, style, value, is_sugared_doc}, span} = at;
 566     Spanned {
 567         node: Attribute_ {
 568             id: id,
 569             style: style,
 570             value: fld.fold_meta_item(value),
 571             is_sugared_doc: is_sugared_doc
 572         },
 573         span: fld.new_span(span)
 574     }
 575 }
 576
 577 pub fn noop_fold_explicit_self_underscore<T: Folder>(es: ExplicitSelf_, fld: &mut T)
 578                                                      -> ExplicitSelf_ {
 579     match es {
 580         SelfStatic | SelfValue(_) => es,
 581         SelfRegion(lifetime, m, ident) => {
 582             SelfRegion(fld.fold_opt_lifetime(lifetime), m, ident)
 583         }
 584         SelfExplicit(typ, ident) => {
 585             SelfExplicit(fld.fold_ty(typ), ident)
 586         }
 587     }
 588 }
 589
 590 pub fn noop_fold_explicit_self<T: Folder>(Spanned {span, node}: ExplicitSelf, fld: &mut T)
 591                                           -> ExplicitSelf {
 592     Spanned {
 593         node: fld.fold_explicit_self_underscore(node),
 594         span: fld.new_span(span)
 595     }
 596 }
 597
 598
 599 pub fn noop_fold_mac<T: Folder>(Spanned {node, span}: Mac, fld: &mut T) -> Mac {
 600     Spanned {
 601         node: match node {
 602             MacInvocTT(p, tts, ctxt) => {
 603                 MacInvocTT(fld.fold_path(p), fld.fold_tts(tts.as_slice()), ctxt)
 604             }
 605         },
 606         span: fld.new_span(span)
 607     }
 608 }
 609
 610 pub fn noop_fold_meta_item<T: Folder>(mi: P<MetaItem>, fld: &mut T) -> P<MetaItem> {
 611     mi.map(|Spanned {node, span}| Spanned {
 612         node: match node {
 613             MetaWord(id) => MetaWord(id),
 614             MetaList(id, mis) => {
 615                 MetaList(id, mis.move_map(|e| fld.fold_meta_item(e)))
 616             }
 617             MetaNameValue(id, s) => MetaNameValue(id, s)
 618         },
 619         span: fld.new_span(span)
 620     })
 621 }
 622
 623 pub fn noop_fold_arg<T: Folder>(Arg {id, pat, ty}: Arg, fld: &mut T) -> Arg {
 624     Arg {
 625         id: fld.new_id(id),
 626         pat: fld.fold_pat(pat),
 627         ty: fld.fold_ty(ty)
 628     }
 629 }
 630
 631 pub fn noop_fold_tt<T: Folder>(tt: &TokenTree, fld: &mut T) -> TokenTree {
 632     match *tt {
 633         TtToken(span, ref tok) =>
 634             TtToken(span, fld.fold_token(tok.clone())),
 635         TtDelimited(span, ref delimed) => {
 636             TtDelimited(span, Rc::new(
 637                             Delimited {
 638                                 delim: delimed.delim,
 639                                 open_span: delimed.open_span,
 640                                 tts: fld.fold_tts(delimed.tts.as_slice()),
 641                                 close_span: delimed.close_span,
 642                             }
 643                         ))
 644         },
 645         TtSequence(span, ref seq) =>
 646             TtSequence(span,
 647                        Rc::new(SequenceRepetition {
 648                            tts: fld.fold_tts(seq.tts.as_slice()),
 649                            separator: seq.separator.clone().map(|tok| fld.fold_token(tok)),
 650                            ..**seq
 651                        })),
 652     }
 653 }
 654
 655 pub fn noop_fold_tts<T: Folder>(tts: &[TokenTree], fld: &mut T) -> Vec<TokenTree> {
 656     tts.iter().map(|tt| fld.fold_tt(tt)).collect()
 657 }
 658
 659 // apply ident folder if it's an ident, apply other folds to interpolated nodes
 660 pub fn noop_fold_token<T: Folder>(t: token::Token, fld: &mut T) -> token::Token {
 661     match t {
 662         token::Ident(id, followed_by_colons) => {
 663             token::Ident(fld.fold_ident(id), followed_by_colons)
 664         }
 665         token::Lifetime(id) => token::Lifetime(fld.fold_ident(id)),
 666         token::Interpolated(nt) => token::Interpolated(fld.fold_interpolated(nt)),
 667         token::SubstNt(ident, namep) => {
 668             token::SubstNt(fld.fold_ident(ident), namep)
 669         }
 670         token::MatchNt(name, kind, namep, kindp) => {
 671             token::MatchNt(fld.fold_ident(name), fld.fold_ident(kind), namep, kindp)
 672         }
 673         _ => t
 674     }
 675 }
 676
 677 /// apply folder to elements of interpolated nodes
 678 //
 679 // NB: this can occur only when applying a fold to partially expanded code, where
 680 // parsed pieces have gotten implanted ito *other* macro invocations. This is relevant
 681 // for macro hygiene, but possibly not elsewhere.
 682 //
 683 // One problem here occurs because the types for fold_item, fold_stmt, etc. allow the
 684 // folder to return *multiple* items; this is a problem for the nodes here, because
 685 // they insist on having exactly one piece. One solution would be to mangle the fold
 686 // trait to include one-to-many and one-to-one versions of these entry points, but that
 687 // would probably confuse a lot of people and help very few. Instead, I'm just going
 688 // to put in dynamic checks. I think the performance impact of this will be pretty much
 689 // nonexistent. The danger is that someone will apply a fold to a partially expanded
 690 // node, and will be confused by the fact that their "fold_item" or "fold_stmt" isn't
 691 // getting called on NtItem or NtStmt nodes. Hopefully they'll wind up reading this
 692 // comment, and doing something appropriate.
 693 //
 694 // BTW, design choice: I considered just changing the type of, e.g., NtItem to contain
 695 // multiple items, but decided against it when I looked at parse_item_or_view_item and
 696 // tried to figure out what I would do with multiple items there....
 697 pub fn noop_fold_interpolated<T: Folder>(nt: token::Nonterminal, fld: &mut T)
 698                                          -> token::Nonterminal {
 699     match nt {
 700         token::NtItem(item) =>
 701             token::NtItem(fld.fold_item(item)
 702                           // this is probably okay, because the only folds likely
 703                           // to peek inside interpolated nodes will be renamings/markings,
 704                           // which map single items to single items
 705                           .expect_one("expected fold to produce exactly one item")),
 706         token::NtBlock(block) => token::NtBlock(fld.fold_block(block)),
 707         token::NtStmt(stmt) =>
 708             token::NtStmt(fld.fold_stmt(stmt)
 709                           // this is probably okay, because the only folds likely
 710                           // to peek inside interpolated nodes will be renamings/markings,
 711                           // which map single items to single items
 712                           .expect_one("expected fold to produce exactly one statement")),
 713         token::NtPat(pat) => token::NtPat(fld.fold_pat(pat)),
 714         token::NtExpr(expr) => token::NtExpr(fld.fold_expr(expr)),
 715         token::NtTy(ty) => token::NtTy(fld.fold_ty(ty)),
 716         token::NtIdent(box id, is_mod_name) =>
 717             token::NtIdent(box fld.fold_ident(id), is_mod_name),
 718         token::NtMeta(meta_item) => token::NtMeta(fld.fold_meta_item(meta_item)),
 719         token::NtPath(box path) => token::NtPath(box fld.fold_path(path)),
 720         token::NtTT(tt) => token::NtTT(P(fld.fold_tt(&*tt))),
 721     }
 722 }
 723
 724 pub fn noop_fold_fn_decl<T: Folder>(decl: P<FnDecl>, fld: &mut T) -> P<FnDecl> {
 725     decl.map(|FnDecl {inputs, output, variadic}| FnDecl {
 726         inputs: inputs.move_map(|x| fld.fold_arg(x)),
 727         output: match output {
 728             Return(ty) => Return(fld.fold_ty(ty)),
 729             NoReturn(span) => NoReturn(span)
 730         },
 731         variadic: variadic
 732     })
 733 }
 734
 735 pub fn noop_fold_ty_param_bound<T>(tpb: TyParamBound, fld: &mut T)
 736                                    -> TyParamBound
 737                                    where T: Folder {
 738     match tpb {
 739         TraitTyParamBound(ty, modifier) => TraitTyParamBound(fld.fold_poly_trait_ref(ty), modifier),
 740         RegionTyParamBound(lifetime) => RegionTyParamBound(fld.fold_lifetime(lifetime)),
 741     }
 742 }
 743
 744 pub fn noop_fold_ty_param<T: Folder>(tp: TyParam, fld: &mut T) -> TyParam {
 745     let TyParam {id, ident, bounds, default, span} = tp;
 746     TyParam {
 747         id: fld.new_id(id),
 748         ident: ident,
 749         bounds: fld.fold_bounds(bounds),
 750         default: default.map(|x| fld.fold_ty(x)),
 751         span: span
 752     }
 753 }
 754
 755 pub fn noop_fold_ty_params<T: Folder>(tps: OwnedSlice<TyParam>, fld: &mut T)
 756                                       -> OwnedSlice<TyParam> {
 757     tps.move_map(|tp| fld.fold_ty_param(tp))
 758 }
 759
 760 pub fn noop_fold_lifetime<T: Folder>(l: Lifetime, fld: &mut T) -> Lifetime {
 761     Lifetime {
 762         id: fld.new_id(l.id),
 763         name: l.name,
 764         span: fld.new_span(l.span)
 765     }
 766 }
 767
 768 pub fn noop_fold_lifetime_def<T: Folder>(l: LifetimeDef, fld: &mut T)
 769                                          -> LifetimeDef {
 770     LifetimeDef {
 771         lifetime: fld.fold_lifetime(l.lifetime),
 772         bounds: fld.fold_lifetimes(l.bounds),
 773     }
 774 }
 775
 776 pub fn noop_fold_lifetimes<T: Folder>(lts: Vec<Lifetime>, fld: &mut T) -> Vec<Lifetime> {
 777     lts.move_map(|l| fld.fold_lifetime(l))
 778 }
 779
 780 pub fn noop_fold_lifetime_defs<T: Folder>(lts: Vec<LifetimeDef>, fld: &mut T)
 781                                           -> Vec<LifetimeDef> {
 782     lts.move_map(|l| fld.fold_lifetime_def(l))
 783 }
 784
 785 pub fn noop_fold_opt_lifetime<T: Folder>(o_lt: Option<Lifetime>, fld: &mut T)
 786                                          -> Option<Lifetime> {
 787     o_lt.map(|lt| fld.fold_lifetime(lt))
 788 }
 789
 790 pub fn noop_fold_generics<T: Folder>(Generics {ty_params, lifetimes, where_clause}: Generics,
 791                                      fld: &mut T) -> Generics {
 792     Generics {
 793         ty_params: fld.fold_ty_params(ty_params),
 794         lifetimes: fld.fold_lifetime_defs(lifetimes),
 795         where_clause: fld.fold_where_clause(where_clause),
 796     }
 797 }
 798
 799 pub fn noop_fold_where_clause<T: Folder>(
 800                               WhereClause {id, predicates}: WhereClause,
 801                               fld: &mut T)
 802                               -> WhereClause {
 803     WhereClause {
 804         id: fld.new_id(id),
 805         predicates: predicates.move_map(|predicate| {
 806             fld.fold_where_predicate(predicate)
 807         })
 808     }
 809 }
 810
 811 pub fn noop_fold_where_predicate<T: Folder>(
 812                                  pred: WherePredicate,
 813                                  fld: &mut T)
 814                                  -> WherePredicate {
 815     match pred {
 816         ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{bounded_ty,
 817                                                                      bounds,
 818                                                                      span}) => {
 819             ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate {
 820                 bounded_ty: fld.fold_ty(bounded_ty),
 821                 bounds: bounds.move_map(|x| fld.fold_ty_param_bound(x)),
 822                 span: fld.new_span(span)
 823             })
 824         }
 825         ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate{lifetime,
 826                                                                        bounds,
 827                                                                        span}) => {
 828             ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate {
 829                 span: fld.new_span(span),
 830                 lifetime: fld.fold_lifetime(lifetime),
 831                 bounds: bounds.move_map(|bound| fld.fold_lifetime(bound))
 832             })
 833         }
 834         ast::WherePredicate::EqPredicate(ast::WhereEqPredicate{id,
 835                                                                path,
 836                                                                ty,
 837                                                                span}) => {
 838             ast::WherePredicate::EqPredicate(ast::WhereEqPredicate{
 839                 id: fld.new_id(id),
 840                 path: fld.fold_path(path),
 841                 ty:fld.fold_ty(ty),
 842                 span: fld.new_span(span)
 843             })
 844         }
 845     }
 846 }
 847
 848 pub fn noop_fold_typedef<T>(t: Typedef, folder: &mut T)
 849                             -> Typedef
 850                             where T: Folder {
 851     let new_id = folder.new_id(t.id);
 852     let new_span = folder.new_span(t.span);
 853     let new_attrs = t.attrs.iter().map(|attr| {
 854         folder.fold_attribute((*attr).clone())
 855     }).collect();
 856     let new_ident = folder.fold_ident(t.ident);
 857     let new_type = folder.fold_ty(t.typ);
 858     ast::Typedef {
 859         ident: new_ident,
 860         typ: new_type,
 861         id: new_id,
 862         span: new_span,
 863         vis: t.vis,
 864         attrs: new_attrs,
 865     }
 866 }
 867
 868 pub fn noop_fold_associated_type<T>(at: AssociatedType, folder: &mut T)
 869                                     -> AssociatedType
 870                                     where T: Folder
 871 {
 872     let new_attrs = at.attrs
 873                       .iter()
 874                       .map(|attr| folder.fold_attribute((*attr).clone()))
 875                       .collect();
 876     let new_param = folder.fold_ty_param(at.ty_param);
 877     ast::AssociatedType {
 878         attrs: new_attrs,
 879         ty_param: new_param,
 880     }
 881 }
 882
 883 pub fn noop_fold_struct_def<T: Folder>(struct_def: P<StructDef>, fld: &mut T) -> P<StructDef> {
 884     struct_def.map(|StructDef { fields, ctor_id }| StructDef {
 885         fields: fields.move_map(|f| fld.fold_struct_field(f)),
 886         ctor_id: ctor_id.map(|cid| fld.new_id(cid)),
 887     })
 888 }
 889
 890 pub fn noop_fold_trait_ref<T: Folder>(p: TraitRef, fld: &mut T) -> TraitRef {
 891     let id = fld.new_id(p.ref_id);
 892     let TraitRef {
 893         path,
 894         ref_id: _,
 895     } = p;
 896     ast::TraitRef {
 897         path: fld.fold_path(path),
 898         ref_id: id,
 899     }
 900 }
 901
 902 pub fn noop_fold_poly_trait_ref<T: Folder>(p: PolyTraitRef, fld: &mut T) -> PolyTraitRef {
 903     ast::PolyTraitRef {
 904         bound_lifetimes: fld.fold_lifetime_defs(p.bound_lifetimes),
 905         trait_ref: fld.fold_trait_ref(p.trait_ref)
 906     }
 907 }
 908
 909 pub fn noop_fold_struct_field<T: Folder>(f: StructField, fld: &mut T) -> StructField {
 910     let StructField {node: StructField_ {id, kind, ty, attrs}, span} = f;
 911     Spanned {
 912         node: StructField_ {
 913             id: fld.new_id(id),
 914             kind: kind,
 915             ty: fld.fold_ty(ty),
 916             attrs: attrs.move_map(|a| fld.fold_attribute(a))
 917         },
 918         span: fld.new_span(span)
 919     }
 920 }
 921
 922 pub fn noop_fold_field<T: Folder>(Field {ident, expr, span}: Field, folder: &mut T) -> Field {
 923     Field {
 924         ident: respan(ident.span, folder.fold_ident(ident.node)),
 925         expr: folder.fold_expr(expr),
 926         span: folder.new_span(span)
 927     }
 928 }
 929
 930 pub fn noop_fold_mt<T: Folder>(MutTy {ty, mutbl}: MutTy, folder: &mut T) -> MutTy {
 931     MutTy {
 932         ty: folder.fold_ty(ty),
 933         mutbl: mutbl,
 934     }
 935 }
 936
 937 pub fn noop_fold_opt_bounds<T: Folder>(b: Option<OwnedSlice<TyParamBound>>, folder: &mut T)
 938                                        -> Option<OwnedSlice<TyParamBound>> {
 939     b.map(|bounds| folder.fold_bounds(bounds))
 940 }
 941
 942 fn noop_fold_bounds<T: Folder>(bounds: TyParamBounds, folder: &mut T)
 943                           -> TyParamBounds {
 944     bounds.move_map(|bound| folder.fold_ty_param_bound(bound))
 945 }
 946
 947 fn noop_fold_variant_arg<T: Folder>(VariantArg {id, ty}: VariantArg, folder: &mut T)
 948                                     -> VariantArg {
 949     VariantArg {
 950         id: folder.new_id(id),
 951         ty: folder.fold_ty(ty)
 952     }
 953 }
 954
 955 pub fn noop_fold_view_item<T: Folder>(ViewItem {node, attrs, vis, span}: ViewItem,
 956                                       folder: &mut T) -> ViewItem {
 957     ViewItem {
 958         node: match node {
 959             ViewItemExternCrate(ident, string, node_id) => {
 960                 ViewItemExternCrate(ident, string,
 961                                     folder.new_id(node_id))
 962             }
 963             ViewItemUse(view_path) => {
 964                 ViewItemUse(folder.fold_view_path(view_path))
 965             }
 966         },
 967         attrs: attrs.move_map(|a| folder.fold_attribute(a)),
 968         vis: vis,
 969         span: folder.new_span(span)
 970     }
 971 }
 972
 973 pub fn noop_fold_block<T: Folder>(b: P<Block>, folder: &mut T) -> P<Block> {
 974     b.map(|Block {id, view_items, stmts, expr, rules, span}| Block {
 975         id: folder.new_id(id),
 976         view_items: view_items.move_map(|x| folder.fold_view_item(x)),
 977         stmts: stmts.into_iter().flat_map(|s| folder.fold_stmt(s).into_iter()).collect(),
 978         expr: expr.map(|x| folder.fold_expr(x)),
 979         rules: rules,
 980         span: folder.new_span(span),
 981     })
 982 }
 983
 984 pub fn noop_fold_item_underscore<T: Folder>(i: Item_, folder: &mut T) -> Item_ {
 985     match i {
 986         ItemStatic(t, m, e) => {
 987             ItemStatic(folder.fold_ty(t), m, folder.fold_expr(e))
 988         }
 989         ItemConst(t, e) => {
 990             ItemConst(folder.fold_ty(t), folder.fold_expr(e))
 991         }
 992         ItemFn(decl, unsafety, abi, generics, body) => {
 993             ItemFn(
 994                 folder.fold_fn_decl(decl),
 995                 unsafety,
 996                 abi,
 997                 folder.fold_generics(generics),
 998                 folder.fold_block(body)
 999             )
1000         }
1001         ItemMod(m) => ItemMod(folder.fold_mod(m)),
1002         ItemForeignMod(nm) => ItemForeignMod(folder.fold_foreign_mod(nm)),
1003         ItemTy(t, generics) => {
1004             ItemTy(folder.fold_ty(t), folder.fold_generics(generics))
1005         }
1006         ItemEnum(enum_definition, generics) => {
1007             ItemEnum(
1008                 ast::EnumDef {
1009                     variants: enum_definition.variants.move_map(|x| folder.fold_variant(x)),
1010                 },
1011                 folder.fold_generics(generics))
1012         }
1013         ItemStruct(struct_def, generics) => {
1014             let struct_def = folder.fold_struct_def(struct_def);
1015             ItemStruct(struct_def, folder.fold_generics(generics))
1016         }
1017         ItemImpl(unsafety, polarity, generics, ifce, ty, impl_items) => {
1018             let new_impl_items = impl_items.into_iter().flat_map(|item| {
1019                 folder.fold_impl_item(item).into_iter()
1020             }).collect();
1021             let ifce = match ifce {
1022                 None => None,
1023                 Some(ref trait_ref) => {
1024                     Some(folder.fold_trait_ref((*trait_ref).clone()))
1025                 }
1026             };
1027             ItemImpl(unsafety,
1028                      polarity,
1029                      folder.fold_generics(generics),
1030                      ifce,
1031                      folder.fold_ty(ty),
1032                      new_impl_items)
1033         }
1034         ItemTrait(unsafety, generics, bounds, items) => {
1035             let bounds = folder.fold_bounds(bounds);
1036             let items = items.into_iter().flat_map(|item| {
1037                 folder.fold_trait_item(item).into_iter()
1038             }).collect();
1039             ItemTrait(unsafety,
1040                       folder.fold_generics(generics),
1041                       bounds,
1042                       items)
1043         }
1044         ItemMac(m) => ItemMac(folder.fold_mac(m)),
1045     }
1046 }
1047
1048 pub fn noop_fold_trait_item<T: Folder>(i: TraitItem, folder: &mut T) -> SmallVector<TraitItem> {
1049     match i {
1050         RequiredMethod(m) => {
1051                 SmallVector::one(RequiredMethod(
1052                         folder.fold_type_method(m)))
1053         }
1054         ProvidedMethod(method) => {
1055             folder.fold_method(method).into_iter()
1056                 .map(|m| ProvidedMethod(m)).collect()
1057         }
1058         TypeTraitItem(at) => {
1059             SmallVector::one(TypeTraitItem(P(
1060                         folder.fold_associated_type(
1061                             (*at).clone()))))
1062         }
1063     }
1064 }
1065
1066 pub fn noop_fold_impl_item<T: Folder>(i: ImplItem, folder: &mut T) -> SmallVector<ImplItem> {
1067     match i {
1068         MethodImplItem(ref x) => {
1069             folder.fold_method((*x).clone()).into_iter().map(|m| MethodImplItem(m)).collect()
1070         }
1071         TypeImplItem(ref t) => {
1072             SmallVector::one(TypeImplItem(
1073                     P(folder.fold_typedef((**t).clone()))))
1074         }
1075     }
1076 }
1077
1078 pub fn noop_fold_type_method<T: Folder>(m: TypeMethod, fld: &mut T) -> TypeMethod {
1079     let TypeMethod {
1080         id,
1081         ident,
1082         attrs,
1083         unsafety,
1084         abi,
1085         decl,
1086         generics,
1087         explicit_self,
1088         vis,
1089         span
1090     } = m;
1091     TypeMethod {
1092         id: fld.new_id(id),
1093         ident: fld.fold_ident(ident),
1094         attrs: attrs.move_map(|a| fld.fold_attribute(a)),
1095         unsafety: unsafety,
1096         abi: abi,
1097         decl: fld.fold_fn_decl(decl),
1098         generics: fld.fold_generics(generics),
1099         explicit_self: fld.fold_explicit_self(explicit_self),
1100         vis: vis,
1101         span: fld.new_span(span)
1102     }
1103 }
1104
1105 pub fn noop_fold_mod<T: Folder>(Mod {inner, view_items, items}: Mod, folder: &mut T) -> Mod {
1106     Mod {
1107         inner: folder.new_span(inner),
1108         view_items: view_items.move_map(|x| folder.fold_view_item(x)),
1109         items: items.into_iter().flat_map(|x| folder.fold_item(x).into_iter()).collect(),
1110     }
1111 }
1112
1113 pub fn noop_fold_crate<T: Folder>(Crate {module, attrs, config, mut exported_macros, span}: Crate,
1114                                   folder: &mut T) -> Crate {
1115     let config = folder.fold_meta_items(config);
1116
1117     let mut items = folder.fold_item(P(ast::Item {
1118         ident: token::special_idents::invalid,
1119         attrs: attrs,
1120         id: ast::DUMMY_NODE_ID,
1121         vis: ast::Public,
1122         span: span,
1123         node: ast::ItemMod(module),
1124     })).into_iter();
1125
1126     let (module, attrs, span) = match items.next() {
1127         Some(item) => {
1128             assert!(items.next().is_none(),
1129                     "a crate cannot expand to more than one item");
1130             item.and_then(|ast::Item { attrs, span, node, .. }| {
1131                 match node {
1132                     ast::ItemMod(m) => (m, attrs, span),
1133                     _ => panic!("fold converted a module to not a module"),
1134                 }
1135             })
1136         }
1137         None => (ast::Mod {
1138             inner: span,
1139             view_items: Vec::new(),
1140             items: Vec::new(),
1141         }, Vec::new(), span)
1142     };
1143
1144     for def in exported_macros.iter_mut() {
1145         def.id = folder.new_id(def.id);
1146     }
1147
1148     Crate {
1149         module: module,
1150         attrs: attrs,
1151         config: config,
1152         exported_macros: exported_macros,
1153         span: span,
1154     }
1155 }
1156
1157 // fold one item into possibly many items
1158 pub fn noop_fold_item<T: Folder>(i: P<Item>, folder: &mut T) -> SmallVector<P<Item>> {
1159     SmallVector::one(i.map(|i| folder.fold_item_simple(i)))
1160 }
1161
1162 // fold one item into exactly one item
1163 pub fn noop_fold_item_simple<T: Folder>(Item {id, ident, attrs, node, vis, span}: Item,
1164                                         folder: &mut T) -> Item {
1165     let id = folder.new_id(id);
1166     let node = folder.fold_item_underscore(node);
1167     let ident = match node {
1168         // The node may have changed, recompute the "pretty" impl name.
1169         ItemImpl(_, _, _, ref maybe_trait, ref ty, _) => {
1170             ast_util::impl_pretty_name(maybe_trait, &**ty)
1171         }
1172         _ => ident
1173     };
1174
1175     Item {
1176         id: id,
1177         ident: folder.fold_ident(ident),
1178         attrs: attrs.move_map(|e| folder.fold_attribute(e)),
1179         node: node,
1180         vis: vis,
1181         span: folder.new_span(span)
1182     }
1183 }
1184
1185 pub fn noop_fold_foreign_item<T: Folder>(ni: P<ForeignItem>, folder: &mut T) -> P<ForeignItem> {
1186     ni.map(|ForeignItem {id, ident, attrs, node, span, vis}| ForeignItem {
1187         id: folder.new_id(id),
1188         ident: folder.fold_ident(ident),
1189         attrs: attrs.move_map(|x| folder.fold_attribute(x)),
1190         node: match node {
1191             ForeignItemFn(fdec, generics) => {
1192                 ForeignItemFn(fdec.map(|FnDecl {inputs, output, variadic}| FnDecl {
1193                     inputs: inputs.move_map(|a| folder.fold_arg(a)),
1194                     output: match output {
1195                         Return(ty) => Return(folder.fold_ty(ty)),
1196                         NoReturn(span) => NoReturn(span)
1197                     },
1198                     variadic: variadic
1199                 }), folder.fold_generics(generics))
1200             }
1201             ForeignItemStatic(t, m) => {
1202                 ForeignItemStatic(folder.fold_ty(t), m)
1203             }
1204         },
1205         vis: vis,
1206         span: folder.new_span(span)
1207     })
1208 }
1209
1210 // Default fold over a method.
1211 // Invariant: produces exactly one method.
1212 pub fn noop_fold_method<T: Folder>(m: P<Method>, folder: &mut T) -> SmallVector<P<Method>> {
1213     SmallVector::one(m.map(|Method {id, attrs, node, span}| Method {
1214         id: folder.new_id(id),
1215         attrs: attrs.move_map(|a| folder.fold_attribute(a)),
1216         node: match node {
1217             MethDecl(ident,
1218                      generics,
1219                      abi,
1220                      explicit_self,
1221                      unsafety,
1222                      decl,
1223                      body,
1224                      vis) => {
1225                 MethDecl(folder.fold_ident(ident),
1226                          folder.fold_generics(generics),
1227                          abi,
1228                          folder.fold_explicit_self(explicit_self),
1229                          unsafety,
1230                          folder.fold_fn_decl(decl),
1231                          folder.fold_block(body),
1232                          vis)
1233             },
1234             MethMac(mac) => MethMac(folder.fold_mac(mac)),
1235         },
1236         span: folder.new_span(span)
1237     }))
1238 }
1239
1240 pub fn noop_fold_pat<T: Folder>(p: P<Pat>, folder: &mut T) -> P<Pat> {
1241     p.map(|Pat {id, node, span}| Pat {
1242         id: folder.new_id(id),
1243         node: match node {
1244             PatWild(k) => PatWild(k),
1245             PatIdent(binding_mode, pth1, sub) => {
1246                 PatIdent(binding_mode,
1247                         Spanned{span: folder.new_span(pth1.span),
1248                                 node: folder.fold_ident(pth1.node)},
1249                         sub.map(|x| folder.fold_pat(x)))
1250             }
1251             PatLit(e) => PatLit(folder.fold_expr(e)),
1252             PatEnum(pth, pats) => {
1253                 PatEnum(folder.fold_path(pth),
1254                         pats.map(|pats| pats.move_map(|x| folder.fold_pat(x))))
1255             }
1256             PatStruct(pth, fields, etc) => {
1257                 let pth = folder.fold_path(pth);
1258                 let fs = fields.move_map(|f| {
1259                     Spanned { span: folder.new_span(f.span),
1260                               node: ast::FieldPat {
1261                                   ident: f.node.ident,
1262                                   pat: folder.fold_pat(f.node.pat),
1263                                   is_shorthand: f.node.is_shorthand,
1264                               }}
1265                 });
1266                 PatStruct(pth, fs, etc)
1267             }
1268             PatTup(elts) => PatTup(elts.move_map(|x| folder.fold_pat(x))),
1269             PatBox(inner) => PatBox(folder.fold_pat(inner)),
1270             PatRegion(inner, mutbl) => PatRegion(folder.fold_pat(inner), mutbl),
1271             PatRange(e1, e2) => {
1272                 PatRange(folder.fold_expr(e1), folder.fold_expr(e2))
1273             },
1274             PatVec(before, slice, after) => {
1275                 PatVec(before.move_map(|x| folder.fold_pat(x)),
1276                        slice.map(|x| folder.fold_pat(x)),
1277                        after.move_map(|x| folder.fold_pat(x)))
1278             }
1279             PatMac(mac) => PatMac(folder.fold_mac(mac))
1280         },
1281         span: folder.new_span(span)
1282     })
1283 }
1284
1285 pub fn noop_fold_expr<T: Folder>(Expr {id, node, span}: Expr, folder: &mut T) -> Expr {
1286     Expr {
1287         id: folder.new_id(id),
1288         node: match node {
1289             ExprBox(p, e) => {
1290                 ExprBox(p.map(|e|folder.fold_expr(e)), folder.fold_expr(e))
1291             }
1292             ExprVec(exprs) => {
1293                 ExprVec(exprs.move_map(|x| folder.fold_expr(x)))
1294             }
1295             ExprRepeat(expr, count) => {
1296                 ExprRepeat(folder.fold_expr(expr), folder.fold_expr(count))
1297             }
1298             ExprTup(elts) => ExprTup(elts.move_map(|x| folder.fold_expr(x))),
1299             ExprCall(f, args) => {
1300                 ExprCall(folder.fold_expr(f),
1301                          args.move_map(|x| folder.fold_expr(x)))
1302             }
1303             ExprMethodCall(i, tps, args) => {
1304                 ExprMethodCall(
1305                     respan(i.span, folder.fold_ident(i.node)),
1306                     tps.move_map(|x| folder.fold_ty(x)),
1307                     args.move_map(|x| folder.fold_expr(x)))
1308             }
1309             ExprBinary(binop, lhs, rhs) => {
1310                 ExprBinary(binop,
1311                         folder.fold_expr(lhs),
1312                         folder.fold_expr(rhs))
1313             }
1314             ExprUnary(binop, ohs) => {
1315                 ExprUnary(binop, folder.fold_expr(ohs))
1316             }
1317             ExprLit(l) => ExprLit(l),
1318             ExprCast(expr, ty) => {
1319                 ExprCast(folder.fold_expr(expr), folder.fold_ty(ty))
1320             }
1321             ExprAddrOf(m, ohs) => ExprAddrOf(m, folder.fold_expr(ohs)),
1322             ExprIf(cond, tr, fl) => {
1323                 ExprIf(folder.fold_expr(cond),
1324                        folder.fold_block(tr),
1325                        fl.map(|x| folder.fold_expr(x)))
1326             }
1327             ExprIfLet(pat, expr, tr, fl) => {
1328                 ExprIfLet(folder.fold_pat(pat),
1329                           folder.fold_expr(expr),
1330                           folder.fold_block(tr),
1331                           fl.map(|x| folder.fold_expr(x)))
1332             }
1333             ExprWhile(cond, body, opt_ident) => {
1334                 ExprWhile(folder.fold_expr(cond),
1335                           folder.fold_block(body),
1336                           opt_ident.map(|i| folder.fold_ident(i)))
1337             }
1338             ExprWhileLet(pat, expr, body, opt_ident) => {
1339                 ExprWhileLet(folder.fold_pat(pat),
1340                              folder.fold_expr(expr),
1341                              folder.fold_block(body),
1342                              opt_ident.map(|i| folder.fold_ident(i)))
1343             }
1344             ExprForLoop(pat, iter, body, opt_ident) => {
1345                 ExprForLoop(folder.fold_pat(pat),
1346                             folder.fold_expr(iter),
1347                             folder.fold_block(body),
1348                             opt_ident.map(|i| folder.fold_ident(i)))
1349             }
1350             ExprLoop(body, opt_ident) => {
1351                 ExprLoop(folder.fold_block(body),
1352                         opt_ident.map(|i| folder.fold_ident(i)))
1353             }
1354             ExprMatch(expr, arms, source) => {
1355                 ExprMatch(folder.fold_expr(expr),
1356                         arms.move_map(|x| folder.fold_arm(x)),
1357                         source)
1358             }
1359             ExprClosure(capture_clause, opt_kind, decl, body) => {
1360                 ExprClosure(capture_clause,
1361                             opt_kind,
1362                             folder.fold_fn_decl(decl),
1363                             folder.fold_block(body))
1364             }
1365             ExprBlock(blk) => ExprBlock(folder.fold_block(blk)),
1366             ExprAssign(el, er) => {
1367                 ExprAssign(folder.fold_expr(el), folder.fold_expr(er))
1368             }
1369             ExprAssignOp(op, el, er) => {
1370                 ExprAssignOp(op,
1371                             folder.fold_expr(el),
1372                             folder.fold_expr(er))
1373             }
1374             ExprField(el, ident) => {
1375                 ExprField(folder.fold_expr(el),
1376                           respan(ident.span, folder.fold_ident(ident.node)))
1377             }
1378             ExprTupField(el, ident) => {
1379                 ExprTupField(folder.fold_expr(el),
1380                              respan(ident.span, folder.fold_uint(ident.node)))
1381             }
1382             ExprIndex(el, er) => {
1383                 ExprIndex(folder.fold_expr(el), folder.fold_expr(er))
1384             }
1385             ExprRange(e1, e2) => {
1386                 ExprRange(e1.map(|x| folder.fold_expr(x)),
1387                           e2.map(|x| folder.fold_expr(x)))
1388             }
1389             ExprPath(pth) => ExprPath(folder.fold_path(pth)),
1390             ExprQPath(qpath) => ExprQPath(folder.fold_qpath(qpath)),
1391             ExprBreak(opt_ident) => ExprBreak(opt_ident.map(|x| folder.fold_ident(x))),
1392             ExprAgain(opt_ident) => ExprAgain(opt_ident.map(|x| folder.fold_ident(x))),
1393             ExprRet(e) => ExprRet(e.map(|x| folder.fold_expr(x))),
1394             ExprInlineAsm(InlineAsm {
1395                 inputs,
1396                 outputs,
1397                 asm,
1398                 asm_str_style,
1399                 clobbers,
1400                 volatile,
1401                 alignstack,
1402                 dialect,
1403                 expn_id,
1404             }) => ExprInlineAsm(InlineAsm {
1405                 inputs: inputs.move_map(|(c, input)| {
1406                     (c, folder.fold_expr(input))
1407                 }),
1408                 outputs: outputs.move_map(|(c, out, is_rw)| {
1409                     (c, folder.fold_expr(out), is_rw)
1410                 }),
1411                 asm: asm,
1412                 asm_str_style: asm_str_style,
1413                 clobbers: clobbers,
1414                 volatile: volatile,
1415                 alignstack: alignstack,
1416                 dialect: dialect,
1417                 expn_id: expn_id,
1418             }),
1419             ExprMac(mac) => ExprMac(folder.fold_mac(mac)),
1420             ExprStruct(path, fields, maybe_expr) => {
1421                 ExprStruct(folder.fold_path(path),
1422                         fields.move_map(|x| folder.fold_field(x)),
1423                         maybe_expr.map(|x| folder.fold_expr(x)))
1424             },
1425             ExprParen(ex) => ExprParen(folder.fold_expr(ex))
1426         },
1427         span: folder.new_span(span)
1428     }
1429 }
1430
1431 pub fn noop_fold_stmt<T: Folder>(Spanned {node, span}: Stmt, folder: &mut T)
1432                                  -> SmallVector<P<Stmt>> {
1433     let span = folder.new_span(span);
1434     match node {
1435         StmtDecl(d, id) => {
1436             let id = folder.new_id(id);
1437             folder.fold_decl(d).into_iter().map(|d| P(Spanned {
1438                 node: StmtDecl(d, id),
1439                 span: span
1440             })).collect()
1441         }
1442         StmtExpr(e, id) => {
1443             let id = folder.new_id(id);
1444             SmallVector::one(P(Spanned {
1445                 node: StmtExpr(folder.fold_expr(e), id),
1446                 span: span
1447             }))
1448         }
1449         StmtSemi(e, id) => {
1450             let id = folder.new_id(id);
1451             SmallVector::one(P(Spanned {
1452                 node: StmtSemi(folder.fold_expr(e), id),
1453                 span: span
1454             }))
1455         }
1456         StmtMac(mac, semi) => SmallVector::one(P(Spanned {
1457             node: StmtMac(mac.map(|m| folder.fold_mac(m)), semi),
1458             span: span
1459         }))
1460     }
1461 }
1462
1463 #[cfg(test)]
1464 mod test {
1465     use std::io;
1466     use ast;
1467     use util::parser_testing::{string_to_crate, matches_codepattern};
1468     use parse::token;
1469     use print::pprust;
1470     use fold;
1471     use super::*;
1472
1473     // this version doesn't care about getting comments or docstrings in.
1474     fn fake_print_crate(s: &mut pprust::State,
1475                         krate: &ast::Crate) -> io::IoResult<()> {
1476         s.print_mod(&krate.module, krate.attrs.as_slice())
1477     }
1478
1479     // change every identifier to "zz"
1480     struct ToZzIdentFolder;
1481
1482     impl Folder for ToZzIdentFolder {
1483         fn fold_ident(&mut self, _: ast::Ident) -> ast::Ident {
1484             token::str_to_ident("zz")
1485         }
1486         fn fold_mac(&mut self, mac: ast::Mac) -> ast::Mac {
1487             fold::noop_fold_mac(mac, self)
1488         }
1489     }
1490
1491     // maybe add to expand.rs...
1492     macro_rules! assert_pred {
1493         ($pred:expr, $predname:expr, $a:expr , $b:expr) => (
1494             {
1495                 let pred_val = $pred;
1496                 let a_val = $a;
1497                 let b_val = $b;
1498                 if !(pred_val(a_val.as_slice(),b_val.as_slice())) {
1499                     panic!("expected args satisfying {}, got {} and {}",
1500                           $predname, a_val, b_val);
1501                 }
1502             }
1503         )
1504     }
1505
1506     // make sure idents get transformed everywhere
1507     #[test] fn ident_transformation () {
1508         let mut zz_fold = ToZzIdentFolder;
1509         let ast = string_to_crate(
1510             "#[a] mod b {fn c (d : e, f : g) {h!(i,j,k);l;m}}".to_string());
1511         let folded_crate = zz_fold.fold_crate(ast);
1512         assert_pred!(
1513             matches_codepattern,
1514             "matches_codepattern",
1515             pprust::to_string(|s| fake_print_crate(s, &folded_crate)),
1516             "#[a]mod zz{fn zz(zz:zz,zz:zz){zz!(zz,zz,zz);zz;zz}}".to_string());
1517     }
1518
1519     // even inside macro defs....
1520     #[test] fn ident_transformation_in_defs () {
1521         let mut zz_fold = ToZzIdentFolder;
1522         let ast = string_to_crate(
1523             "macro_rules! a {(b $c:expr $(d $e:token)f+ => \
1524              (g $(d $d $e)+))} ".to_string());
1525         let folded_crate = zz_fold.fold_crate(ast);
1526         assert_pred!(
1527             matches_codepattern,
1528             "matches_codepattern",
1529             pprust::to_string(|s| fake_print_crate(s, &folded_crate)),
1530             "zz!zz((zz$zz:zz$(zz $zz:zz)zz+=>(zz$(zz$zz$zz)+)));".to_string());
1531     }
1532 }