Overhaul `syntax::fold::Folder`.

This commit changes `syntax::fold::Folder` from a functional style
(where most methods take a `T` and produce a new `T`) to a more
imperative style (where most methods take and modify a `&mut T`), and
renames it `syntax::mut_visit::MutVisitor`.

The first benefit is speed. The functional style does not require any
reallocations, due to the use of `P::map` and
`MoveMap::move_{,flat_}map`. However, every field in the AST must be
overwritten; even those fields that are unchanged are overwritten with
the same value. This causes a lot of unnecessary memory writes. The
imperative style reduces instruction counts by 1--3% across a wide range
of workloads, particularly incremental workloads.

The second benefit is conciseness; the imperative style is usually more
concise. E.g. compare the old functional style:
```
fn fold_abc(&mut self, abc: ABC) {
    ABC {
        a: fold_a(abc.a),
        b: fold_b(abc.b),
        c: abc.c,
    }
}
```
with the imperative style:
```
fn visit_abc(&mut self, ABC { a, b, c: _ }: &mut ABC) {
    visit_a(a);
    visit_b(b);
}
```
(The reductions get larger in more complex examples.)

Overall, the patch removes over 200 lines of code -- even though the new
code has more comments -- and a lot of the remaining lines have fewer
characters.

Some notes:

- The old style used methods called `fold_*`. The new style mostly uses
  methods called `visit_*`, but there are a few methods that map a `T`
  to something other than a `T`, which are called `flat_map_*` (`T` maps
  to multiple `T`s) or `filter_map_*` (`T` maps to 0 or 1 `T`s).

- `move_map.rs`/`MoveMap`/`move_map`/`move_flat_map` are renamed
  `map_in_place.rs`/`MapInPlace`/`map_in_place`/`flat_map_in_place` to
  reflect their slightly changed signatures.

- Although this commit renames the `fold` module as `mut_visit`, it
  keeps it in the `fold.rs` file, so as not to confuse git. The next
  commit will rename the file.

5 files changed, 218 insertions, 212 deletions

diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 09e7e57f78c..b53068f5bc2 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -8,7 +8,7 @@ use edition::Edition;
 use errors::{DiagnosticBuilder, DiagnosticId};
 use ext::expand::{self, AstFragment, Invocation};
 use ext::hygiene::{self, Mark, SyntaxContext, Transparency};
-use fold::{self, Folder};
+use mut_visit::{self, MutVisitor};
 use parse::{self, parser, DirectoryOwnership};
 use parse::token;
 use ptr::P;
@@ -47,15 +47,14 @@ impl HasAttrs for Annotatable {
         }
     }
 
-    fn map_attrs<F: FnOnce(Vec<Attribute>) -> Vec<Attribute>>(self, f: F) -> Self {
+    fn visit_attrs<F: FnOnce(&mut Vec<Attribute>)>(&mut self, f: F) {
         match self {
-            Annotatable::Item(item) => Annotatable::Item(item.map_attrs(f)),
-            Annotatable::TraitItem(trait_item) => Annotatable::TraitItem(trait_item.map_attrs(f)),
-            Annotatable::ImplItem(impl_item) => Annotatable::ImplItem(impl_item.map_attrs(f)),
-            Annotatable::ForeignItem(foreign_item) =>
-                Annotatable::ForeignItem(foreign_item.map_attrs(f)),
-            Annotatable::Stmt(stmt) => Annotatable::Stmt(stmt.map_attrs(f)),
-            Annotatable::Expr(expr) => Annotatable::Expr(expr.map_attrs(f)),
+            Annotatable::Item(item) => item.visit_attrs(f),
+            Annotatable::TraitItem(trait_item) => trait_item.visit_attrs(f),
+            Annotatable::ImplItem(impl_item) => impl_item.visit_attrs(f),
+            Annotatable::ForeignItem(foreign_item) => foreign_item.visit_attrs(f),
+            Annotatable::Stmt(stmt) => stmt.visit_attrs(f),
+            Annotatable::Expr(expr) => expr.visit_attrs(f),
         }
     }
 }
@@ -263,24 +262,24 @@ impl<F> TTMacroExpander for F
     ) -> Box<dyn MacResult+'cx> {
         struct AvoidInterpolatedIdents;
 
-        impl Folder for AvoidInterpolatedIdents {
-            fn fold_tt(&mut self, tt: tokenstream::TokenTree) -> tokenstream::TokenTree {
-                if let tokenstream::TokenTree::Token(_, token::Interpolated(ref nt)) = tt {
+        impl MutVisitor for AvoidInterpolatedIdents {
+            fn visit_tt(&mut self, tt: &mut tokenstream::TokenTree) {
+                if let tokenstream::TokenTree::Token(_, token::Interpolated(nt)) = tt {
                     if let token::NtIdent(ident, is_raw) = nt.0 {
-                        return tokenstream::TokenTree::Token(ident.span,
-                                                             token::Ident(ident, is_raw));
+                        *tt = tokenstream::TokenTree::Token(ident.span,
+                                                            token::Ident(ident, is_raw));
                     }
                 }
-                fold::noop_fold_tt(tt, self)
+                mut_visit::noop_visit_tt(tt, self)
             }
 
-            fn fold_mac(&mut self, mac: ast::Mac) -> ast::Mac {
-                fold::noop_fold_mac(mac, self)
+            fn visit_mac(&mut self, mac: &mut ast::Mac) {
+                mut_visit::noop_visit_mac(mac, self)
             }
         }
 
         let input: Vec<_> =
-            input.trees().map(|tt| AvoidInterpolatedIdents.fold_tt(tt)).collect();
+            input.trees().map(|mut tt| { AvoidInterpolatedIdents.visit_tt(&mut tt); tt }).collect();
         (*self)(ecx, span, &input)
     }
 }
@@ -981,17 +980,14 @@ impl<'a> ExtCtxt<'a> {
 /// compilation on error, merely emits a non-fatal error and returns None.
 pub fn expr_to_spanned_string<'a>(
     cx: &'a mut ExtCtxt,
-    expr: P<ast::Expr>,
+    mut expr: P<ast::Expr>,
     err_msg: &str,
 ) -> Result<Spanned<(Symbol, ast::StrStyle)>, Option<DiagnosticBuilder<'a>>> {
     // Update `expr.span`'s ctxt now in case expr is an `include!` macro invocation.
-    let expr = expr.map(|mut expr| {
-        expr.span = expr.span.apply_mark(cx.current_expansion.mark);
-        expr
-    });
+    expr.span = expr.span.apply_mark(cx.current_expansion.mark);
 
     // we want to be able to handle e.g., `concat!("foo", "bar")`
-    let expr = cx.expander().fold_expr(expr);
+    cx.expander().visit_expr(&mut expr);
     Err(match expr.node {
         ast::ExprKind::Lit(ref l) => match l.node {
             ast::LitKind::Str(s, style) => return Ok(respan(expr.span, (s, style))),
@@ -1055,7 +1051,9 @@ pub fn get_exprs_from_tts(cx: &mut ExtCtxt,
     let mut p = cx.new_parser_from_tts(tts);
     let mut es = Vec::new();
     while p.token != token::Eof {
-        es.push(cx.expander().fold_expr(panictry!(p.parse_expr())));
+        let mut expr = panictry!(p.parse_expr());
+        cx.expander().visit_expr(&mut expr);
+        es.push(expr);
         if p.eat(&token::Comma) {
             continue;
         }
diff --git a/src/libsyntax/ext/derive.rs b/src/libsyntax/ext/derive.rs
index 7ef09ce5fbd..fa8cf6c496a 100644
--- a/src/libsyntax/ext/derive.rs
+++ b/src/libsyntax/ext/derive.rs
@@ -40,7 +40,7 @@ pub fn collect_derives(cx: &mut ExtCtxt, attrs: &mut Vec<ast::Attribute>) -> Vec
     result
 }
 
-pub fn add_derived_markers<T>(cx: &mut ExtCtxt, span: Span, traits: &[ast::Path], item: T) -> T
+pub fn add_derived_markers<T>(cx: &mut ExtCtxt, span: Span, traits: &[ast::Path], item: &mut T)
     where T: HasAttrs,
 {
     let (mut names, mut pretty_name) = (FxHashSet::default(), "derive(".to_owned());
@@ -64,7 +64,7 @@ pub fn add_derived_markers<T>(cx: &mut ExtCtxt, span: Span, traits: &[ast::Path]
     });
 
     let span = span.with_ctxt(cx.backtrace());
-    item.map_attrs(|mut attrs| {
+    item.visit_attrs(|attrs| {
         if names.contains(&Symbol::intern("Eq")) && names.contains(&Symbol::intern("PartialEq")) {
             let meta = cx.meta_word(span, Symbol::intern("structural_match"));
             attrs.push(cx.attribute(span, meta));
@@ -73,6 +73,5 @@ pub fn add_derived_markers<T>(cx: &mut ExtCtxt, span: Span, traits: &[ast::Path]
             let meta = cx.meta_word(span, Symbol::intern("rustc_copy_clone_marker"));
             attrs.push(cx.attribute(span, meta));
         }
-        attrs
-    })
+    });
 }
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index 2effd910e85..a0ccce98659 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -9,7 +9,7 @@ use ext::derive::{add_derived_markers, collect_derives};
 use ext::hygiene::{self, Mark, SyntaxContext};
 use ext::placeholders::{placeholder, PlaceholderExpander};
 use feature_gate::{self, Features, GateIssue, is_builtin_attr, emit_feature_err};
-use fold::*;
+use mut_visit::*;
 use parse::{DirectoryOwnership, PResult, ParseSess};
 use parse::token::{self, Token};
 use parse::parser::Parser;
@@ -21,11 +21,13 @@ use syntax_pos::{Span, DUMMY_SP, FileName};
 use syntax_pos::hygiene::ExpnFormat;
 use tokenstream::{TokenStream, TokenTree};
 use visit::{self, Visitor};
+use util::map_in_place::MapInPlace;
 
 use rustc_data_structures::fx::FxHashMap;
 use std::fs;
 use std::io::ErrorKind;
 use std::{iter, mem};
+use std::ops::DerefMut;
 use std::rc::Rc;
 use std::path::PathBuf;
 
@@ -35,8 +37,8 @@ macro_rules! ast_fragments {
             $kind_name:expr;
             // FIXME: HACK: this should be `$(one ...)?` and `$(many ...)?` but `?` macro
             // repetition was removed from 2015 edition in #51587 because of ambiguities.
-            $(one fn $fold_ast:ident; fn $visit_ast:ident;)*
-            $(many fn $fold_ast_elt:ident; fn $visit_ast_elt:ident;)*
+            $(one fn $mut_visit_ast:ident; fn $visit_ast:ident;)*
+            $(many fn $flat_map_ast_elt:ident; fn $visit_ast_elt:ident;)*
             fn $make_ast:ident;
         })*
     ) => {
@@ -86,16 +88,20 @@ macro_rules! ast_fragments {
                 }
             })*
 
-            pub fn fold_with<F: Folder>(self, folder: &mut F) -> Self {
+            pub fn mut_visit_with<F: MutVisitor>(&mut self, vis: &mut F) {
                 match self {
-                    AstFragment::OptExpr(expr) =>
-                        AstFragment::OptExpr(expr.and_then(|expr| folder.fold_opt_expr(expr))),
-                    $($(AstFragment::$Kind(ast) =>
-                        AstFragment::$Kind(folder.$fold_ast(ast)),)*)*
+                    AstFragment::OptExpr(opt_expr) => {
+                        visit_clobber(opt_expr, |opt_expr| {
+                            if let Some(expr) = opt_expr {
+                                vis.filter_map_expr(expr)
+                            } else {
+                                None
+                            }
+                        });
+                    }
+                    $($(AstFragment::$Kind(ast) => vis.$mut_visit_ast(ast),)*)*
                     $($(AstFragment::$Kind(ast) =>
-                        AstFragment::$Kind(ast.into_iter()
-                                              .flat_map(|ast| folder.$fold_ast_elt(ast))
-                                              .collect()),)*)*
+                        ast.flat_map_in_place(|ast| vis.$flat_map_ast_elt(ast)),)*)*
                 }
             }
 
@@ -111,14 +117,14 @@ macro_rules! ast_fragments {
             }
         }
 
-        impl<'a, 'b> Folder for MacroExpander<'a, 'b> {
-            fn fold_opt_expr(&mut self, expr: P<ast::Expr>) -> Option<P<ast::Expr>> {
+        impl<'a, 'b> MutVisitor for MacroExpander<'a, 'b> {
+            fn filter_map_expr(&mut self, expr: P<ast::Expr>) -> Option<P<ast::Expr>> {
                 self.expand_fragment(AstFragment::OptExpr(Some(expr))).make_opt_expr()
             }
-            $($(fn $fold_ast(&mut self, ast: $AstTy) -> $AstTy {
-                self.expand_fragment(AstFragment::$Kind(ast)).$make_ast()
+            $($(fn $mut_visit_ast(&mut self, ast: &mut $AstTy) {
+                visit_clobber(ast, |ast| self.expand_fragment(AstFragment::$Kind(ast)).$make_ast());
             })*)*
-            $($(fn $fold_ast_elt(&mut self, ast_elt: <$AstTy as IntoIterator>::Item) -> $AstTy {
+            $($(fn $flat_map_ast_elt(&mut self, ast_elt: <$AstTy as IntoIterator>::Item) -> $AstTy {
                 self.expand_fragment(AstFragment::$Kind(smallvec![ast_elt])).$make_ast()
             })*)*
         }
@@ -133,23 +139,23 @@ macro_rules! ast_fragments {
 }
 
 ast_fragments! {
-    Expr(P<ast::Expr>) { "expression"; one fn fold_expr; fn visit_expr; fn make_expr; }
-    Pat(P<ast::Pat>) { "pattern"; one fn fold_pat; fn visit_pat; fn make_pat; }
-    Ty(P<ast::Ty>) { "type"; one fn fold_ty; fn visit_ty; fn make_ty; }
+    Expr(P<ast::Expr>) { "expression"; one fn visit_expr; fn visit_expr; fn make_expr; }
+    Pat(P<ast::Pat>) { "pattern"; one fn visit_pat; fn visit_pat; fn make_pat; }
+    Ty(P<ast::Ty>) { "type"; one fn visit_ty; fn visit_ty; fn make_ty; }
     Stmts(SmallVec<[ast::Stmt; 1]>) {
-        "statement"; many fn fold_stmt; fn visit_stmt; fn make_stmts;
+        "statement"; many fn flat_map_stmt; fn visit_stmt; fn make_stmts;
     }
     Items(SmallVec<[P<ast::Item>; 1]>) {
-        "item"; many fn fold_item; fn visit_item; fn make_items;
+        "item"; many fn flat_map_item; fn visit_item; fn make_items;
     }
     TraitItems(SmallVec<[ast::TraitItem; 1]>) {
-        "trait item"; many fn fold_trait_item; fn visit_trait_item; fn make_trait_items;
+        "trait item"; many fn flat_map_trait_item; fn visit_trait_item; fn make_trait_items;
     }
     ImplItems(SmallVec<[ast::ImplItem; 1]>) {
-        "impl item"; many fn fold_impl_item; fn visit_impl_item; fn make_impl_items;
+        "impl item"; many fn flat_map_impl_item; fn visit_impl_item; fn make_impl_items;
     }
     ForeignItems(SmallVec<[ast::ForeignItem; 1]>) {
-        "foreign item"; many fn fold_foreign_item; fn visit_foreign_item; fn make_foreign_items;
+        "foreign item"; many fn flat_map_foreign_item; fn visit_foreign_item; fn make_foreign_items;
     }
 }
 
@@ -297,7 +303,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
         self.cx.current_expansion.depth = 0;
 
         // Collect all macro invocations and replace them with placeholders.
-        let (fragment_with_placeholders, mut invocations)
+        let (mut fragment_with_placeholders, mut invocations)
             = self.collect_invocations(input_fragment, &[]);
 
         // Optimization: if we resolve all imports now,
@@ -369,10 +375,10 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
                         err.emit();
                     }
 
-                    let item = self.fully_configure(item)
-                        .map_attrs(|mut attrs| { attrs.retain(|a| a.path != "derive"); attrs });
-                    let item_with_markers =
-                        add_derived_markers(&mut self.cx, item.span(), &traits, item.clone());
+                    let mut item = self.fully_configure(item);
+                    item.visit_attrs(|attrs| attrs.retain(|a| a.path != "derive"));
+                    let mut item_with_markers = item.clone();
+                    add_derived_markers(&mut self.cx, item.span(), &traits, &mut item_with_markers);
                     let derives = derives.entry(invoc.expansion_data.mark).or_default();
 
                     derives.reserve(traits.len());
@@ -427,7 +433,8 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
                                          expanded_fragment, derives);
             }
         }
-        fragment_with_placeholders.fold_with(&mut placeholder_expander)
+        fragment_with_placeholders.mut_visit_with(&mut placeholder_expander);
+        fragment_with_placeholders
     }
 
     fn resolve_imports(&mut self) {
@@ -440,12 +447,12 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
     /// them with "placeholders" - dummy macro invocations with specially crafted `NodeId`s.
     /// Then call into resolver that builds a skeleton ("reduced graph") of the fragment and
     /// prepares data for resolving paths of macro invocations.
-    fn collect_invocations(&mut self, fragment: AstFragment, derives: &[Mark])
+    fn collect_invocations(&mut self, mut fragment: AstFragment, derives: &[Mark])
                            -> (AstFragment, Vec<Invocation>) {
         // Resolve `$crate`s in the fragment for pretty-printing.
         self.cx.resolver.resolve_dollar_crates(&fragment);
 
-        let (fragment_with_placeholders, invocations) = {
+        let invocations = {
             let mut collector = InvocationCollector {
                 cfg: StripUnconfigured {
                     sess: self.cx.parse_sess,
@@ -455,16 +462,16 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
                 invocations: Vec::new(),
                 monotonic: self.monotonic,
             };
-            (fragment.fold_with(&mut collector), collector.invocations)
+            fragment.mut_visit_with(&mut collector);
+            collector.invocations
         };
 
         if self.monotonic {
             self.cx.resolver.visit_ast_fragment_with_placeholders(
-                self.cx.current_expansion.mark, &fragment_with_placeholders, derives
-            );
+                self.cx.current_expansion.mark, &fragment, derives);
         }
 
-        (fragment_with_placeholders, invocations)
+        (fragment, invocations)
     }
 
     fn fully_configure(&mut self, item: Annotatable) -> Annotatable {
@@ -476,24 +483,25 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
         // we know that fold result vector will contain exactly one element
         match item {
             Annotatable::Item(item) => {
-                Annotatable::Item(cfg.fold_item(item).pop().unwrap())
+                Annotatable::Item(cfg.flat_map_item(item).pop().unwrap())
             }
             Annotatable::TraitItem(item) => {
-                Annotatable::TraitItem(item.map(|item| cfg.fold_trait_item(item).pop().unwrap()))
+                Annotatable::TraitItem(
+                    item.map(|item| cfg.flat_map_trait_item(item).pop().unwrap()))
             }
             Annotatable::ImplItem(item) => {
-                Annotatable::ImplItem(item.map(|item| cfg.fold_impl_item(item).pop().unwrap()))
+                Annotatable::ImplItem(item.map(|item| cfg.flat_map_impl_item(item).pop().unwrap()))
             }
             Annotatable::ForeignItem(item) => {
                 Annotatable::ForeignItem(
-                    item.map(|item| cfg.fold_foreign_item(item).pop().unwrap())
+                    item.map(|item| cfg.flat_map_foreign_item(item).pop().unwrap())
                 )
             }
             Annotatable::Stmt(stmt) => {
-                Annotatable::Stmt(stmt.map(|stmt| cfg.fold_stmt(stmt).pop().unwrap()))
+                Annotatable::Stmt(stmt.map(|stmt| cfg.flat_map_stmt(stmt).pop().unwrap()))
             }
-            Annotatable::Expr(expr) => {
-                Annotatable::Expr(cfg.fold_expr(expr))
+            Annotatable::Expr(mut expr) => {
+                Annotatable::Expr({ cfg.visit_expr(&mut expr); expr })
             }
         }
     }
@@ -535,7 +543,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
                          invoc: Invocation,
                          ext: &SyntaxExtension)
                          -> Option<AstFragment> {
-        let (attr, item) = match invoc.kind {
+        let (attr, mut item) = match invoc.kind {
             InvocationKind::Attr { attr, item, .. } => (attr?, item),
             _ => unreachable!(),
         };
@@ -558,7 +566,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
         match *ext {
             NonMacroAttr { .. } => {
                 attr::mark_known(&attr);
-                let item = item.map_attrs(|mut attrs| { attrs.push(attr); attrs });
+                item.visit_attrs(|attrs| attrs.push(attr));
                 Some(invoc.fragment_kind.expect_from_annotatables(iter::once(item)))
             }
             MultiModifier(ref mac) => {
@@ -1113,34 +1121,32 @@ impl<'a, 'b> InvocationCollector<'a, 'b> {
     }
 
     /// If `item` is an attr invocation, remove and return the macro attribute and derive traits.
-    fn classify_item<T>(&mut self, mut item: T)
-                        -> (Option<ast::Attribute>, Vec<Path>, T, /* after_derive */ bool)
+    fn classify_item<T>(&mut self, item: &mut T)
+                        -> (Option<ast::Attribute>, Vec<Path>, /* after_derive */ bool)
         where T: HasAttrs,
     {
         let (mut attr, mut traits, mut after_derive) = (None, Vec::new(), false);
 
-        item = item.map_attrs(|mut attrs| {
+        item.visit_attrs(|mut attrs| {
             attr = self.find_attr_invoc(&mut attrs, &mut after_derive);
             traits = collect_derives(&mut self.cx, &mut attrs);
-            attrs
         });
 
-        (attr, traits, item, after_derive)
+        (attr, traits, after_derive)
     }
 
-    /// Alternative of `classify_item()` that ignores `#[derive]` so invocations fallthrough
+    /// Alternative to `classify_item()` that ignores `#[derive]` so invocations fallthrough
     /// to the unused-attributes lint (making it an error on statements and expressions
     /// is a breaking change)
-    fn classify_nonitem<T: HasAttrs>(&mut self, mut item: T)
-                                     -> (Option<ast::Attribute>, T, /* after_derive */ bool) {
+    fn classify_nonitem<T: HasAttrs>(&mut self, nonitem: &mut T)
+                                     -> (Option<ast::Attribute>, /* after_derive */ bool) {
         let (mut attr, mut after_derive) = (None, false);
 
-        item = item.map_attrs(|mut attrs| {
+        nonitem.visit_attrs(|mut attrs| {
             attr = self.find_attr_invoc(&mut attrs, &mut after_derive);
-            attrs
         });
 
-        (attr, item, after_derive)
+        (attr, after_derive)
     }
 
     fn configure<T: HasAttrs>(&mut self, node: T) -> Option<T> {
@@ -1173,14 +1179,14 @@ impl<'a, 'b> InvocationCollector<'a, 'b> {
     }
 }
 
-impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
-    fn fold_expr(&mut self, expr: P<ast::Expr>) -> P<ast::Expr> {
-        let expr = self.cfg.configure_expr(expr);
-        expr.map(|mut expr| {
-            expr.node = self.cfg.configure_expr_kind(expr.node);
+impl<'a, 'b> MutVisitor for InvocationCollector<'a, 'b> {
+    fn visit_expr(&mut self, expr: &mut P<ast::Expr>) {
+        self.cfg.configure_expr(expr);
+        visit_clobber(expr.deref_mut(), |mut expr| {
+            self.cfg.configure_expr_kind(&mut expr.node);
 
             // ignore derives so they remain unused
-            let (attr, expr, after_derive) = self.classify_nonitem(expr);
+            let (attr, after_derive) = self.classify_nonitem(&mut expr);
 
             if attr.is_some() {
                 // Collect the invoc regardless of whether or not attributes are permitted here
@@ -1189,7 +1195,7 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
 
                 // AstFragmentKind::Expr requires the macro to emit an expression.
                 return self.collect_attr(attr, vec![], Annotatable::Expr(P(expr)),
-                                         AstFragmentKind::Expr, after_derive)
+                                          AstFragmentKind::Expr, after_derive)
                     .make_expr()
                     .into_inner()
             }
@@ -1200,18 +1206,19 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
                     .make_expr()
                     .into_inner()
             } else {
-                noop_fold_expr(expr, self)
+                noop_visit_expr(&mut expr, self);
+                expr
             }
-        })
+        });
     }
 
-    fn fold_opt_expr(&mut self, expr: P<ast::Expr>) -> Option<P<ast::Expr>> {
+    fn filter_map_expr(&mut self, expr: P<ast::Expr>) -> Option<P<ast::Expr>> {
         let expr = configure!(self, expr);
         expr.filter_map(|mut expr| {
-            expr.node = self.cfg.configure_expr_kind(expr.node);
+            self.cfg.configure_expr_kind(&mut expr.node);
 
             // Ignore derives so they remain unused.
-            let (attr, expr, after_derive) = self.classify_nonitem(expr);
+            let (attr, after_derive) = self.classify_nonitem(&mut expr);
 
             if attr.is_some() {
                 attr.as_ref().map(|a| self.cfg.maybe_emit_expr_attr_err(a));
@@ -1228,44 +1235,45 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
                     .make_opt_expr()
                     .map(|expr| expr.into_inner())
             } else {
-                Some(noop_fold_expr(expr, self))
+                Some({ noop_visit_expr(&mut expr, self); expr })
             }
         })
     }
 
-    fn fold_pat(&mut self, pat: P<ast::Pat>) -> P<ast::Pat> {
-        let pat = self.cfg.configure_pat(pat);
+    fn visit_pat(&mut self, pat: &mut P<ast::Pat>) {
+        self.cfg.configure_pat(pat);
         match pat.node {
             PatKind::Mac(_) => {}
-            _ => return noop_fold_pat(pat, self),
+            _ => return noop_visit_pat(pat, self),
         }
 
-        pat.and_then(|pat| match pat.node {
-            PatKind::Mac(mac) => self.collect_bang(mac, pat.span, AstFragmentKind::Pat).make_pat(),
-            _ => unreachable!(),
-        })
+        visit_clobber(pat, |mut pat| {
+            match mem::replace(&mut pat.node, PatKind::Wild) {
+                PatKind::Mac(mac) =>
+                    self.collect_bang(mac, pat.span, AstFragmentKind::Pat).make_pat(),
+                _ => unreachable!(),
+            }
+        });
     }
 
-    fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVec<[ast::Stmt; 1]> {
+    fn flat_map_stmt(&mut self, stmt: ast::Stmt) -> SmallVec<[ast::Stmt; 1]> {
         let mut stmt = configure!(self, stmt);
 
         // we'll expand attributes on expressions separately
         if !stmt.is_expr() {
-            let (attr, derives, stmt_, after_derive) = if stmt.is_item() {
-                self.classify_item(stmt)
+            let (attr, derives, after_derive) = if stmt.is_item() {
+                self.classify_item(&mut stmt)
             } else {
                 // ignore derives on non-item statements so it falls through
                 // to the unused-attributes lint
-                let (attr, stmt, after_derive) = self.classify_nonitem(stmt);
-                (attr, vec![], stmt, after_derive)
+                let (attr, after_derive) = self.classify_nonitem(&mut stmt);
+                (attr, vec![], after_derive)
             };
 
             if attr.is_some() || !derives.is_empty() {
-                return self.collect_attr(attr, derives, Annotatable::Stmt(P(stmt_)),
+                return self.collect_attr(attr, derives, Annotatable::Stmt(P(stmt)),
                                          AstFragmentKind::Stmts, after_derive).make_stmts();
             }
-
-            stmt = stmt_;
         }
 
         if let StmtKind::Mac(mac) = stmt.node {
@@ -1287,24 +1295,23 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
 
         // The placeholder expander gives ids to statements, so we avoid folding the id here.
         let ast::Stmt { id, node, span } = stmt;
-        noop_fold_stmt_kind(node, self).into_iter().map(|node| {
+        noop_flat_map_stmt_kind(node, self).into_iter().map(|node| {
             ast::Stmt { id, node, span }
         }).collect()
 
     }
 
-    fn fold_block(&mut self, block: P<Block>) -> P<Block> {
+    fn visit_block(&mut self, block: &mut P<Block>) {
         let old_directory_ownership = self.cx.current_expansion.directory_ownership;
         self.cx.current_expansion.directory_ownership = DirectoryOwnership::UnownedViaBlock;
-        let result = noop_fold_block(block, self);
+        noop_visit_block(block, self);
         self.cx.current_expansion.directory_ownership = old_directory_ownership;
-        result
     }
 
-    fn fold_item(&mut self, item: P<ast::Item>) -> SmallVec<[P<ast::Item>; 1]> {
-        let item = configure!(self, item);
+    fn flat_map_item(&mut self, item: P<ast::Item>) -> SmallVec<[P<ast::Item>; 1]> {
+        let mut item = configure!(self, item);
 
-        let (attr, traits, item, after_derive) = self.classify_item(item);
+        let (attr, traits, after_derive) = self.classify_item(&mut item);
         if attr.is_some() || !traits.is_empty() {
             return self.collect_attr(attr, traits, Annotatable::Item(item),
                                      AstFragmentKind::Items, after_derive).make_items();
@@ -1326,7 +1333,7 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
             }
             ast::ItemKind::Mod(ast::Mod { inner, .. }) => {
                 if item.ident == keywords::Invalid.ident() {
-                    return noop_fold_item(item, self);
+                    return noop_flat_map_item(item, self);
                 }
 
                 let orig_directory_ownership = self.cx.current_expansion.directory_ownership;
@@ -1366,20 +1373,20 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
 
                 let orig_module =
                     mem::replace(&mut self.cx.current_expansion.module, Rc::new(module));
-                let result = noop_fold_item(item, self);
+                let result = noop_flat_map_item(item, self);
                 self.cx.current_expansion.module = orig_module;
                 self.cx.current_expansion.directory_ownership = orig_directory_ownership;
                 result
             }
 
-            _ => noop_fold_item(item, self),
+            _ => noop_flat_map_item(item, self),
         }
     }
 
-    fn fold_trait_item(&mut self, item: ast::TraitItem) -> SmallVec<[ast::TraitItem; 1]> {
-        let item = configure!(self, item);
+    fn flat_map_trait_item(&mut self, item: ast::TraitItem) -> SmallVec<[ast::TraitItem; 1]> {
+        let mut item = configure!(self, item);
 
-        let (attr, traits, item, after_derive) = self.classify_item(item);
+        let (attr, traits, after_derive) = self.classify_item(&mut item);
         if attr.is_some() || !traits.is_empty() {
             return self.collect_attr(attr, traits, Annotatable::TraitItem(P(item)),
                                      AstFragmentKind::TraitItems, after_derive).make_trait_items()
@@ -1391,14 +1398,14 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
                 self.check_attributes(&attrs);
                 self.collect_bang(mac, span, AstFragmentKind::TraitItems).make_trait_items()
             }
-            _ => noop_fold_trait_item(item, self),
+            _ => noop_flat_map_trait_item(item, self),
         }
     }
 
-    fn fold_impl_item(&mut self, item: ast::ImplItem) -> SmallVec<[ast::ImplItem; 1]> {
-        let item = configure!(self, item);
+    fn flat_map_impl_item(&mut self, item: ast::ImplItem) -> SmallVec<[ast::ImplItem; 1]> {
+        let mut item = configure!(self, item);
 
-        let (attr, traits, item, after_derive) = self.classify_item(item);
+        let (attr, traits, after_derive) = self.classify_item(&mut item);
         if attr.is_some() || !traits.is_empty() {
             return self.collect_attr(attr, traits, Annotatable::ImplItem(P(item)),
                                      AstFragmentKind::ImplItems, after_derive).make_impl_items();
@@ -1410,30 +1417,34 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
                 self.check_attributes(&attrs);
                 self.collect_bang(mac, span, AstFragmentKind::ImplItems).make_impl_items()
             }
-            _ => noop_fold_impl_item(item, self),
+            _ => noop_flat_map_impl_item(item, self),
         }
     }
 
-    fn fold_ty(&mut self, ty: P<ast::Ty>) -> P<ast::Ty> {
-        let ty = match ty.node {
-            ast::TyKind::Mac(_) => ty.into_inner(),
-            _ => return noop_fold_ty(ty, self),
+    fn visit_ty(&mut self, ty: &mut P<ast::Ty>) {
+        match ty.node {
+            ast::TyKind::Mac(_) => {}
+            _ => return noop_visit_ty(ty, self),
         };
 
-        match ty.node {
-            ast::TyKind::Mac(mac) => self.collect_bang(mac, ty.span, AstFragmentKind::Ty).make_ty(),
-            _ => unreachable!(),
-        }
+        visit_clobber(ty, |mut ty| {
+            match mem::replace(&mut ty.node, ast::TyKind::Err) {
+                ast::TyKind::Mac(mac) =>
+                    self.collect_bang(mac, ty.span, AstFragmentKind::Ty).make_ty(),
+                _ => unreachable!(),
+            }
+        });
     }
 
-    fn fold_foreign_mod(&mut self, foreign_mod: ast::ForeignMod) -> ast::ForeignMod {
-        noop_fold_foreign_mod(self.cfg.configure_foreign_mod(foreign_mod), self)
+    fn visit_foreign_mod(&mut self, foreign_mod: &mut ast::ForeignMod) {
+        self.cfg.configure_foreign_mod(foreign_mod);
+        noop_visit_foreign_mod(foreign_mod, self);
     }
 
-    fn fold_foreign_item(&mut self, foreign_item: ast::ForeignItem)
+    fn flat_map_foreign_item(&mut self, mut foreign_item: ast::ForeignItem)
         -> SmallVec<[ast::ForeignItem; 1]>
     {
-        let (attr, traits, foreign_item, after_derive) = self.classify_item(foreign_item);
+        let (attr, traits, after_derive) = self.classify_item(&mut foreign_item);
 
         if attr.is_some() || !traits.is_empty() {
             return self.collect_attr(attr, traits, Annotatable::ForeignItem(P(foreign_item)),
@@ -1447,38 +1458,41 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
                 .make_foreign_items();
         }
 
-        noop_fold_foreign_item(foreign_item, self)
+        noop_flat_map_foreign_item(foreign_item, self)
     }
 
-    fn fold_item_kind(&mut self, item: ast::ItemKind) -> ast::ItemKind {
+    fn visit_item_kind(&mut self, item: &mut ast::ItemKind) {
         match item {
-            ast::ItemKind::MacroDef(..) => item,
-            _ => noop_fold_item_kind(self.cfg.configure_item_kind(item), self),
+            ast::ItemKind::MacroDef(..) => {}
+            _ => {
+                self.cfg.configure_item_kind(item);
+                noop_visit_item_kind(item, self);
+            }
         }
     }
 
-    fn fold_generic_param(&mut self, param: ast::GenericParam) -> ast::GenericParam {
+    fn visit_generic_param(&mut self, param: &mut ast::GenericParam) {
         self.cfg.disallow_cfg_on_generic_param(&param);
-        noop_fold_generic_param(param, self)
+        noop_visit_generic_param(param, self)
     }
 
-    fn fold_attribute(&mut self, at: ast::Attribute) -> ast::Attribute {
+    fn visit_attribute(&mut self, at: &mut ast::Attribute) {
         // turn `#[doc(include="filename")]` attributes into `#[doc(include(file="filename",
         // contents="file contents")]` attributes
         if !at.check_name("doc") {
-            return noop_fold_attribute(at, self);
+            return noop_visit_attribute(at, self);
         }
 
         if let Some(list) = at.meta_item_list() {
             if !list.iter().any(|it| it.check_name("include")) {
-                return noop_fold_attribute(at, self);
+                return noop_visit_attribute(at, self);
             }
 
             let mut items = vec![];
 
-            for it in list {
+            for mut it in list {
                 if !it.check_name("include") {
-                    items.push(noop_fold_meta_list_item(it, self));
+                    items.push({ noop_visit_meta_list_item(&mut it, self); it });
                     continue;
                 }
 
@@ -1487,7 +1501,7 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
                     self.check_attribute(&at);
                     if self.cx.parse_sess.span_diagnostic.err_count() > err_count {
                         // avoid loading the file if they haven't enabled the feature
-                        return noop_fold_attribute(at, self);
+                        return noop_visit_attribute(at, self);
                     }
 
                     let filename = self.cx.root_path.join(file.to_string());
@@ -1582,20 +1596,18 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
 
             let meta = attr::mk_list_item(DUMMY_SP, Ident::from_str("doc"), items);
             match at.style {
-                ast::AttrStyle::Inner => attr::mk_spanned_attr_inner(at.span, at.id, meta),
-                ast::AttrStyle::Outer => attr::mk_spanned_attr_outer(at.span, at.id, meta),
+                ast::AttrStyle::Inner => *at = attr::mk_spanned_attr_inner(at.span, at.id, meta),
+                ast::AttrStyle::Outer => *at = attr::mk_spanned_attr_outer(at.span, at.id, meta),
             }
         } else {
-            noop_fold_attribute(at, self)
+            noop_visit_attribute(at, self)
         }
     }
 
-    fn new_id(&mut self, id: ast::NodeId) -> ast::NodeId {
+    fn visit_id(&mut self, id: &mut ast::NodeId) {
         if self.monotonic {
-            assert_eq!(id, ast::DUMMY_NODE_ID);
-            self.cx.resolver.next_node_id()
-        } else {
-            id
+            debug_assert_eq!(*id, ast::DUMMY_NODE_ID);
+            *id = self.cx.resolver.next_node_id()
         }
     }
 }
@@ -1660,12 +1672,12 @@ impl<'feat> ExpansionConfig<'feat> {
 #[derive(Debug)]
 pub struct Marker(pub Mark);
 
-impl Folder for Marker {
-    fn new_span(&mut self, span: Span) -> Span {
-        span.apply_mark(self.0)
+impl MutVisitor for Marker {
+    fn visit_span(&mut self, span: &mut Span) {
+        *span = span.apply_mark(self.0)
     }
 
-    fn fold_mac(&mut self, mac: ast::Mac) -> ast::Mac {
-        noop_fold_mac(mac, self)
+    fn visit_mac(&mut self, mac: &mut ast::Mac) {
+        noop_visit_mac(mac, self)
     }
 }
diff --git a/src/libsyntax/ext/placeholders.rs b/src/libsyntax/ext/placeholders.rs
index 0928bc80404..23b34c2660b 100644
--- a/src/libsyntax/ext/placeholders.rs
+++ b/src/libsyntax/ext/placeholders.rs
@@ -4,12 +4,11 @@ use ext::base::ExtCtxt;
 use ext::expand::{AstFragment, AstFragmentKind};
 use ext::hygiene::Mark;
 use tokenstream::TokenStream;
-use fold::*;
+use mut_visit::*;
 use ptr::P;
 use smallvec::SmallVec;
 use symbol::keywords;
 use ThinVec;
-use util::move_map::MoveMap;
 
 use rustc_data_structures::fx::FxHashMap;
 
@@ -85,8 +84,8 @@ impl<'a, 'b> PlaceholderExpander<'a, 'b> {
         }
     }
 
-    pub fn add(&mut self, id: ast::NodeId, fragment: AstFragment, derives: Vec<Mark>) {
-        let mut fragment = fragment.fold_with(self);
+    pub fn add(&mut self, id: ast::NodeId, mut fragment: AstFragment, derives: Vec<Mark>) {
+        fragment.mut_visit_with(self);
         if let AstFragment::Items(mut items) = fragment {
             for derive in derives {
                 match self.remove(NodeId::placeholder_from_mark(derive)) {
@@ -104,56 +103,56 @@ impl<'a, 'b> PlaceholderExpander<'a, 'b> {
     }
 }
 
-impl<'a, 'b> Folder for PlaceholderExpander<'a, 'b> {
-    fn fold_item(&mut self, item: P<ast::Item>) -> SmallVec<[P<ast::Item>; 1]> {
+impl<'a, 'b> MutVisitor for PlaceholderExpander<'a, 'b> {
+    fn flat_map_item(&mut self, item: P<ast::Item>) -> SmallVec<[P<ast::Item>; 1]> {
         match item.node {
             ast::ItemKind::Mac(_) => return self.remove(item.id).make_items(),
             ast::ItemKind::MacroDef(_) => return smallvec![item],
             _ => {}
         }
 
-        noop_fold_item(item, self)
+        noop_flat_map_item(item, self)
     }
 
-    fn fold_trait_item(&mut self, item: ast::TraitItem) -> SmallVec<[ast::TraitItem; 1]> {
+    fn flat_map_trait_item(&mut self, item: ast::TraitItem) -> SmallVec<[ast::TraitItem; 1]> {
         match item.node {
             ast::TraitItemKind::Macro(_) => self.remove(item.id).make_trait_items(),
-            _ => noop_fold_trait_item(item, self),
+            _ => noop_flat_map_trait_item(item, self),
         }
     }
 
-    fn fold_impl_item(&mut self, item: ast::ImplItem) -> SmallVec<[ast::ImplItem; 1]> {
+    fn flat_map_impl_item(&mut self, item: ast::ImplItem) -> SmallVec<[ast::ImplItem; 1]> {
         match item.node {
             ast::ImplItemKind::Macro(_) => self.remove(item.id).make_impl_items(),
-            _ => noop_fold_impl_item(item, self),
+            _ => noop_flat_map_impl_item(item, self),
         }
     }
 
-    fn fold_foreign_item(&mut self, item: ast::ForeignItem) -> SmallVec<[ast::ForeignItem; 1]> {
+    fn flat_map_foreign_item(&mut self, item: ast::ForeignItem) -> SmallVec<[ast::ForeignItem; 1]> {
         match item.node {
             ast::ForeignItemKind::Macro(_) => self.remove(item.id).make_foreign_items(),
-            _ => noop_fold_foreign_item(item, self),
+            _ => noop_flat_map_foreign_item(item, self),
         }
     }
 
-    fn fold_expr(&mut self, expr: P<ast::Expr>) -> P<ast::Expr> {
+    fn visit_expr(&mut self, expr: &mut P<ast::Expr>) {
         match expr.node {
-            ast::ExprKind::Mac(_) => self.remove(expr.id).make_expr(),
-            _ => expr.map(|expr| noop_fold_expr(expr, self)),
+            ast::ExprKind::Mac(_) => *expr = self.remove(expr.id).make_expr(),
+            _ => noop_visit_expr(expr, self),
         }
     }
 
-    fn fold_opt_expr(&mut self, expr: P<ast::Expr>) -> Option<P<ast::Expr>> {
+    fn filter_map_expr(&mut self, expr: P<ast::Expr>) -> Option<P<ast::Expr>> {
         match expr.node {
             ast::ExprKind::Mac(_) => self.remove(expr.id).make_opt_expr(),
-            _ => noop_fold_opt_expr(expr, self),
+            _ => noop_filter_map_expr(expr, self),
         }
     }
 
-    fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVec<[ast::Stmt; 1]> {
+    fn flat_map_stmt(&mut self, stmt: ast::Stmt) -> SmallVec<[ast::Stmt; 1]> {
         let (style, mut stmts) = match stmt.node {
             ast::StmtKind::Mac(mac) => (mac.1, self.remove(stmt.id).make_stmts()),
-            _ => return noop_fold_stmt(stmt, self),
+            _ => return noop_flat_map_stmt(stmt, self),
         };
 
         if style == ast::MacStmtStyle::Semicolon {
@@ -165,44 +164,40 @@ impl<'a, 'b> Folder for PlaceholderExpander<'a, 'b> {
         stmts
     }
 
-    fn fold_pat(&mut self, pat: P<ast::Pat>) -> P<ast::Pat> {
+    fn visit_pat(&mut self, pat: &mut P<ast::Pat>) {
         match pat.node {
-            ast::PatKind::Mac(_) => self.remove(pat.id).make_pat(),
-            _ => noop_fold_pat(pat, self),
+            ast::PatKind::Mac(_) => *pat = self.remove(pat.id).make_pat(),
+            _ => noop_visit_pat(pat, self),
         }
     }
 
-    fn fold_ty(&mut self, ty: P<ast::Ty>) -> P<ast::Ty> {
+    fn visit_ty(&mut self, ty: &mut P<ast::Ty>) {
         match ty.node {
-            ast::TyKind::Mac(_) => self.remove(ty.id).make_ty(),
-            _ => noop_fold_ty(ty, self),
+            ast::TyKind::Mac(_) => *ty = self.remove(ty.id).make_ty(),
+            _ => noop_visit_ty(ty, self),
         }
     }
 
-    fn fold_block(&mut self, block: P<ast::Block>) -> P<ast::Block> {
-        noop_fold_block(block, self).map(|mut block| {
-            block.stmts = block.stmts.move_map(|mut stmt| {
-                if self.monotonic {
-                    assert_eq!(stmt.id, ast::DUMMY_NODE_ID);
-                    stmt.id = self.cx.resolver.next_node_id();
-                }
-                stmt
-            });
+    fn visit_block(&mut self, block: &mut P<ast::Block>) {
+        noop_visit_block(block, self);
 
-            block
-        })
+        for stmt in block.stmts.iter_mut() {
+            if self.monotonic {
+                assert_eq!(stmt.id, ast::DUMMY_NODE_ID);
+                stmt.id = self.cx.resolver.next_node_id();
+            }
+        }
     }
 
-    fn fold_mod(&mut self, module: ast::Mod) -> ast::Mod {
-        let mut module = noop_fold_mod(module, self);
+    fn visit_mod(&mut self, module: &mut ast::Mod) {
+        noop_visit_mod(module, self);
         module.items.retain(|item| match item.node {
             ast::ItemKind::Mac(_) if !self.cx.ecfg.keep_macs => false, // remove macro definitions
             _ => true,
         });
-        module
     }
 
-    fn fold_mac(&mut self, mac: ast::Mac) -> ast::Mac {
-        mac
+    fn visit_mac(&mut self, _mac: &mut ast::Mac) {
+        // Do nothing.
     }
 }
diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs
index 0ef2d3b749d..08f34b22328 100644
--- a/src/libsyntax/ext/tt/transcribe.rs
+++ b/src/libsyntax/ext/tt/transcribe.rs
@@ -3,7 +3,7 @@ use ext::base::ExtCtxt;
 use ext::expand::Marker;
 use ext::tt::macro_parser::{NamedMatch, MatchedSeq, MatchedNonterminal};
 use ext::tt::quoted;
-use fold::noop_fold_tt;
+use mut_visit::noop_visit_tt;
 use parse::token::{self, Token, NtTT};
 use smallvec::SmallVec;
 use syntax_pos::DUMMY_SP;
@@ -170,7 +170,9 @@ pub fn transcribe(cx: &ExtCtxt,
             }
             quoted::TokenTree::Token(sp, tok) => {
                 let mut marker = Marker(cx.current_expansion.mark);
-                result.push(noop_fold_tt(TokenTree::Token(sp, tok), &mut marker).into())
+                let mut tt = TokenTree::Token(sp, tok);
+                noop_visit_tt(&mut tt, &mut marker);
+                result.push(tt.into());
             }
             quoted::TokenTree::MetaVarDecl(..) => panic!("unexpected `TokenTree::MetaVarDecl"),
         }