Auto merge of #36214 - jseyfried:stackless_expansion, r=nrc

macros: stackless expansion

After this PR, macro expansion cannot overflow the stack unless the expanded crate is too deep to fold.
Everything but the stackless placeholder expansion commit is also groundwork for macro modularization.

r? @nrc or @eddyb

12 files changed, 941 insertions, 733 deletions

diff --git a/src/librustc_driver/driver.rs b/src/librustc_driver/driver.rs
index 2d4bd6af6d4..ba6c4b9b84c 100644
--- a/src/librustc_driver/driver.rs
+++ b/src/librustc_driver/driver.rs
@@ -555,7 +555,7 @@ pub struct ExpansionResult<'a> {
 /// Returns `None` if we're aborting after handling -W help.
 pub fn phase_2_configure_and_expand<'a, F>(sess: &Session,
                                            cstore: &CStore,
-                                           mut krate: ast::Crate,
+                                           krate: ast::Crate,
                                            registry: Option<Registry>,
                                            crate_name: &'a str,
                                            addl_plugins: Option<Vec<String>>,
@@ -566,21 +566,9 @@ pub fn phase_2_configure_and_expand<'a, F>(sess: &Session,
 {
     let time_passes = sess.time_passes();
 
-    // strip before anything else because crate metadata may use #[cfg_attr]
-    // and so macros can depend on configuration variables, such as
-    //
-    //   #[macro_use] #[cfg(foo)]
-    //   mod bar { macro_rules! baz!(() => {{}}) }
-    //
-    // baz! should not use this definition unless foo is enabled.
-
-    krate = time(time_passes, "configuration", || {
-        let (krate, features) =
-            syntax::config::strip_unconfigured_items(krate, &sess.parse_sess, sess.opts.test);
-        // these need to be set "early" so that expansion sees `quote` if enabled.
-        *sess.features.borrow_mut() = features;
-        krate
-    });
+    let (mut krate, features) = syntax::config::features(krate, &sess.parse_sess, sess.opts.test);
+    // these need to be set "early" so that expansion sees `quote` if enabled.
+    *sess.features.borrow_mut() = features;
 
     *sess.crate_types.borrow_mut() = collect_crate_types(sess, &krate.attrs);
     *sess.crate_disambiguator.borrow_mut() =
diff --git a/src/libsyntax/config.rs b/src/libsyntax/config.rs
index 69a97917652..3f5b294cc04 100644
--- a/src/libsyntax/config.rs
+++ b/src/libsyntax/config.rs
@@ -10,11 +10,10 @@
 
 use attr::HasAttrs;
 use feature_gate::{emit_feature_err, EXPLAIN_STMT_ATTR_SYNTAX, Features, get_features, GateIssue};
-use fold::Folder;
 use {fold, attr};
 use ast;
 use codemap::{Spanned, respan};
-use parse::{ParseSess, token};
+use parse::ParseSess;
 use ptr::P;
 
 use util::small_vector::SmallVector;
@@ -27,8 +26,51 @@ pub struct StripUnconfigured<'a> {
     pub features: Option<&'a Features>,
 }
 
+// `cfg_attr`-process the crate's attributes and compute the crate's features.
+pub fn features(mut krate: ast::Crate, sess: &ParseSess, should_test: bool)
+                -> (ast::Crate, Features) {
+    let features;
+    {
+        let mut strip_unconfigured = StripUnconfigured {
+            config: &krate.config.clone(),
+            should_test: should_test,
+            sess: sess,
+            features: None,
+        };
+
+        let unconfigured_attrs = krate.attrs.clone();
+        let err_count = sess.span_diagnostic.err_count();
+        if let Some(attrs) = strip_unconfigured.configure(krate.attrs) {
+            krate.attrs = attrs;
+        } else { // the entire crate is unconfigured
+            krate.attrs = Vec::new();
+            krate.module.items = Vec::new();
+            return (krate, Features::new());
+        }
+
+        features = get_features(&sess.span_diagnostic, &krate.attrs);
+
+        // Avoid reconfiguring malformed `cfg_attr`s
+        if err_count == sess.span_diagnostic.err_count() {
+            strip_unconfigured.features = Some(&features);
+            strip_unconfigured.configure(unconfigured_attrs);
+        }
+    }
+
+    (krate, features)
+}
+
+macro_rules! configure {
+    ($this:ident, $node:ident) => {
+        match $this.configure($node) {
+            Some(node) => node,
+            None => return Default::default(),
+        }
+    }
+}
+
 impl<'a> StripUnconfigured<'a> {
-    fn configure<T: HasAttrs>(&mut self, node: T) -> Option<T> {
+    pub fn configure<T: HasAttrs>(&mut self, node: T) -> Option<T> {
         let node = self.process_cfg_attrs(node);
         if self.in_cfg(node.attrs()) { Some(node) } else { None }
     }
@@ -123,65 +165,35 @@ impl<'a> StripUnconfigured<'a> {
             }
         }
     }
-}
-
-// Support conditional compilation by transforming the AST, stripping out
-// any items that do not belong in the current configuration
-pub fn strip_unconfigured_items(mut krate: ast::Crate, sess: &ParseSess, should_test: bool)
-                                -> (ast::Crate, Features) {
-    let features;
-    {
-        let mut strip_unconfigured = StripUnconfigured {
-            config: &krate.config.clone(),
-            should_test: should_test,
-            sess: sess,
-            features: None,
-        };
-
-        let err_count = sess.span_diagnostic.err_count();
-        let krate_attrs = strip_unconfigured.configure(krate.attrs.clone()).unwrap_or_default();
-        features = get_features(&sess.span_diagnostic, &krate_attrs);
-        if err_count < sess.span_diagnostic.err_count() {
-            krate.attrs = krate_attrs.clone(); // Avoid reconfiguring malformed `cfg_attr`s
-        }
-
-        strip_unconfigured.features = Some(&features);
-        krate = strip_unconfigured.fold_crate(krate);
-        krate.attrs = krate_attrs;
-    }
 
-    (krate, features)
-}
-
-impl<'a> fold::Folder for StripUnconfigured<'a> {
-    fn fold_foreign_mod(&mut self, foreign_mod: ast::ForeignMod) -> ast::ForeignMod {
+    pub fn configure_foreign_mod(&mut self, foreign_mod: ast::ForeignMod) -> ast::ForeignMod {
         ast::ForeignMod {
             abi: foreign_mod.abi,
-            items: foreign_mod.items.into_iter().filter_map(|item| {
-                self.configure(item).map(|item| fold::noop_fold_foreign_item(item, self))
-            }).collect(),
+            items: foreign_mod.items.into_iter().filter_map(|item| self.configure(item)).collect(),
         }
     }
 
-    fn fold_item_kind(&mut self, item: ast::ItemKind) -> ast::ItemKind {
-        let fold_struct = |this: &mut Self, vdata| match vdata {
+    fn configure_variant_data(&mut self, vdata: ast::VariantData) -> ast::VariantData {
+        match vdata {
             ast::VariantData::Struct(fields, id) => {
-                let fields = fields.into_iter().filter_map(|field| this.configure(field));
+                let fields = fields.into_iter().filter_map(|field| self.configure(field));
                 ast::VariantData::Struct(fields.collect(), id)
             }
             ast::VariantData::Tuple(fields, id) => {
-                let fields = fields.into_iter().filter_map(|field| this.configure(field));
+                let fields = fields.into_iter().filter_map(|field| self.configure(field));
                 ast::VariantData::Tuple(fields.collect(), id)
             }
             ast::VariantData::Unit(id) => ast::VariantData::Unit(id)
-        };
+        }
+    }
 
-        let item = match item {
+    pub fn configure_item_kind(&mut self, item: ast::ItemKind) -> ast::ItemKind {
+        match item {
             ast::ItemKind::Struct(def, generics) => {
-                ast::ItemKind::Struct(fold_struct(self, def), generics)
+                ast::ItemKind::Struct(self.configure_variant_data(def), generics)
             }
             ast::ItemKind::Union(def, generics) => {
-                ast::ItemKind::Union(fold_struct(self, def), generics)
+                ast::ItemKind::Union(self.configure_variant_data(def), generics)
             }
             ast::ItemKind::Enum(def, generics) => {
                 let variants = def.variants.into_iter().filter_map(|v| {
@@ -190,7 +202,7 @@ impl<'a> fold::Folder for StripUnconfigured<'a> {
                             node: ast::Variant_ {
                                 name: v.node.name,
                                 attrs: v.node.attrs,
-                                data: fold_struct(self, v.node.data),
+                                data: self.configure_variant_data(v.node.data),
                                 disr_expr: v.node.disr_expr,
                             },
                             span: v.span
@@ -202,12 +214,19 @@ impl<'a> fold::Folder for StripUnconfigured<'a> {
                 }, generics)
             }
             item => item,
-        };
+        }
+    }
 
-        fold::noop_fold_item_kind(item, self)
+    pub fn configure_expr_kind(&mut self, expr_kind: ast::ExprKind) -> ast::ExprKind {
+        if let ast::ExprKind::Match(m, arms) = expr_kind {
+            let arms = arms.into_iter().filter_map(|a| self.configure(a)).collect();
+            ast::ExprKind::Match(m, arms)
+        } else {
+            expr_kind
+        }
     }
 
-    fn fold_expr(&mut self, expr: P<ast::Expr>) -> P<ast::Expr> {
+    pub fn configure_expr(&mut self, expr: P<ast::Expr>) -> P<ast::Expr> {
         self.visit_stmt_or_expr_attrs(expr.attrs());
 
         // If an expr is valid to cfg away it will have been removed by the
@@ -222,64 +241,64 @@ impl<'a> fold::Folder for StripUnconfigured<'a> {
             self.sess.span_diagnostic.span_err(attr.span, msg);
         }
 
-        let expr = self.process_cfg_attrs(expr);
-        fold_expr(self, expr)
+        self.process_cfg_attrs(expr)
     }
 
-    fn fold_opt_expr(&mut self, expr: P<ast::Expr>) -> Option<P<ast::Expr>> {
-        self.configure(expr).map(|expr| fold_expr(self, expr))
+    pub fn configure_stmt(&mut self, stmt: ast::Stmt) -> Option<ast::Stmt> {
+        self.visit_stmt_or_expr_attrs(stmt.attrs());
+        self.configure(stmt)
     }
+}
 
-    fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVector<ast::Stmt> {
-        self.visit_stmt_or_expr_attrs(stmt.attrs());
-        self.configure(stmt).map(|stmt| fold::noop_fold_stmt(stmt, self))
-                            .unwrap_or(SmallVector::zero())
+impl<'a> fold::Folder for StripUnconfigured<'a> {
+    fn fold_foreign_mod(&mut self, foreign_mod: ast::ForeignMod) -> ast::ForeignMod {
+        let foreign_mod = self.configure_foreign_mod(foreign_mod);
+        fold::noop_fold_foreign_mod(foreign_mod, self)
     }
 
-    fn fold_mac(&mut self, mac: ast::Mac) -> ast::Mac {
-        fold::noop_fold_mac(mac, self)
+    fn fold_item_kind(&mut self, item: ast::ItemKind) -> ast::ItemKind {
+        let item = self.configure_item_kind(item);
+        fold::noop_fold_item_kind(item, self)
+    }
+
+    fn fold_expr(&mut self, expr: P<ast::Expr>) -> P<ast::Expr> {
+        let mut expr = self.configure_expr(expr).unwrap();
+        expr.node = self.configure_expr_kind(expr.node);
+        P(fold::noop_fold_expr(expr, self))
+    }
+
+    fn fold_opt_expr(&mut self, expr: P<ast::Expr>) -> Option<P<ast::Expr>> {
+        let mut expr = configure!(self, expr).unwrap();
+        expr.node = self.configure_expr_kind(expr.node);
+        Some(P(fold::noop_fold_expr(expr, self)))
+    }
+
+    fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVector<ast::Stmt> {
+        match self.configure_stmt(stmt) {
+            Some(stmt) => fold::noop_fold_stmt(stmt, self),
+            None => return SmallVector::zero(),
+        }
     }
 
     fn fold_item(&mut self, item: P<ast::Item>) -> SmallVector<P<ast::Item>> {
-        self.configure(item).map(|item| fold::noop_fold_item(item, self))
-                            .unwrap_or(SmallVector::zero())
+        fold::noop_fold_item(configure!(self, item), self)
     }
 
     fn fold_impl_item(&mut self, item: ast::ImplItem) -> SmallVector<ast::ImplItem> {
-        self.configure(item).map(|item| fold::noop_fold_impl_item(item, self))
-                            .unwrap_or(SmallVector::zero())
+        fold::noop_fold_impl_item(configure!(self, item), self)
     }
 
     fn fold_trait_item(&mut self, item: ast::TraitItem) -> SmallVector<ast::TraitItem> {
-        self.configure(item).map(|item| fold::noop_fold_trait_item(item, self))
-                            .unwrap_or(SmallVector::zero())
+        fold::noop_fold_trait_item(configure!(self, item), self)
     }
 
-    fn fold_interpolated(&mut self, nt: token::Nonterminal) -> token::Nonterminal {
+    fn fold_mac(&mut self, mac: ast::Mac) -> ast::Mac {
         // Don't configure interpolated AST (c.f. #34171).
         // Interpolated AST will get configured once the surrounding tokens are parsed.
-        nt
+        mac
     }
 }
 
-fn fold_expr(folder: &mut StripUnconfigured, expr: P<ast::Expr>) -> P<ast::Expr> {
-    expr.map(|ast::Expr {id, span, node, attrs}| {
-        fold::noop_fold_expr(ast::Expr {
-            id: id,
-            node: match node {
-                ast::ExprKind::Match(m, arms) => {
-                    ast::ExprKind::Match(m, arms.into_iter()
-                                        .filter_map(|a| folder.configure(a))
-                                        .collect())
-                }
-                _ => node
-            },
-            span: span,
-            attrs: attrs,
-        }, folder)
-    })
-}
-
 fn is_cfg(attr: &ast::Attribute) -> bool {
     attr.check_name("cfg")
 }
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 3b1c01319c4..edd38ea23e2 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -24,12 +24,14 @@ use parse::parser;
 use parse::token;
 use parse::token::{InternedString, intern, str_to_ident};
 use ptr::P;
+use std_inject;
 use util::small_vector::SmallVector;
 use util::lev_distance::find_best_match_for_name;
 use fold::Folder;
 use feature_gate;
 
 use std::collections::{HashMap, HashSet};
+use std::path::PathBuf;
 use std::rc::Rc;
 use tokenstream;
 
@@ -90,16 +92,6 @@ impl Annotatable {
             _ => panic!("expected Item")
         }
     }
-
-    pub fn fold_with<F: Folder>(self, folder: &mut F) -> SmallVector<Self> {
-        match self {
-            Annotatable::Item(item) => folder.fold_item(item).map(Annotatable::Item),
-            Annotatable::ImplItem(item) =>
-                folder.fold_impl_item(item.unwrap()).map(|item| Annotatable::ImplItem(P(item))),
-            Annotatable::TraitItem(item) =>
-                folder.fold_trait_item(item.unwrap()).map(|item| Annotatable::TraitItem(P(item))),
-        }
-    }
 }
 
 // A more flexible ItemDecorator.
@@ -472,19 +464,6 @@ pub enum SyntaxExtension {
 
 pub type NamedSyntaxExtension = (Name, SyntaxExtension);
 
-pub struct BlockInfo {
-    /// Should macros escape from this scope?
-    pub macros_escape: bool,
-}
-
-impl BlockInfo {
-    pub fn new() -> BlockInfo {
-        BlockInfo {
-            macros_escape: false,
-        }
-    }
-}
-
 /// The base map of methods for expanding syntax extension
 /// AST nodes into full ASTs
 fn initial_syntax_expander_table<'feat>(ecfg: &expand::ExpansionConfig<'feat>)
@@ -595,16 +574,11 @@ pub struct ExtCtxt<'a> {
     pub crate_root: Option<&'static str>,
     pub loader: &'a mut MacroLoader,
 
-    pub mod_path: Vec<ast::Ident> ,
     pub exported_macros: Vec<ast::MacroDef>,
 
     pub syntax_env: SyntaxEnv,
     pub derive_modes: HashMap<InternedString, Box<MultiItemModifier>>,
     pub recursion_count: usize,
-
-    pub filename: Option<String>,
-    pub mod_path_stack: Vec<InternedString>,
-    pub in_block: bool,
 }
 
 impl<'a> ExtCtxt<'a> {
@@ -612,23 +586,17 @@ impl<'a> ExtCtxt<'a> {
                ecfg: expand::ExpansionConfig<'a>,
                loader: &'a mut MacroLoader)
                -> ExtCtxt<'a> {
-        let env = initial_syntax_expander_table(&ecfg);
         ExtCtxt {
+            syntax_env: initial_syntax_expander_table(&ecfg),
             parse_sess: parse_sess,
             cfg: cfg,
             backtrace: NO_EXPANSION,
-            mod_path: Vec::new(),
             ecfg: ecfg,
             crate_root: None,
             exported_macros: Vec::new(),
             loader: loader,
-            syntax_env: env,
             derive_modes: HashMap::new(),
             recursion_count: 0,
-
-            filename: None,
-            mod_path_stack: Vec::new(),
-            in_block: false,
         }
     }
 
@@ -677,16 +645,7 @@ impl<'a> ExtCtxt<'a> {
         last_macro.expect("missing expansion backtrace")
     }
 
-    pub fn mod_push(&mut self, i: ast::Ident) { self.mod_path.push(i); }
-    pub fn mod_pop(&mut self) { self.mod_path.pop().unwrap(); }
-    pub fn mod_path(&self) -> Vec<ast::Ident> {
-        let mut v = Vec::new();
-        v.push(token::str_to_ident(&self.ecfg.crate_name));
-        v.extend(self.mod_path.iter().cloned());
-        return v;
-    }
     pub fn bt_push(&mut self, ei: ExpnInfo) {
-        self.recursion_count += 1;
         if self.recursion_count > self.ecfg.recursion_limit {
             self.span_fatal(ei.call_site,
                             &format!("recursion limit reached while expanding the macro `{}`",
@@ -700,17 +659,7 @@ impl<'a> ExtCtxt<'a> {
             callee: ei.callee
         });
     }
-    pub fn bt_pop(&mut self) {
-        match self.backtrace {
-            NO_EXPANSION => self.bug("tried to pop without a push"),
-            expn_id => {
-                self.recursion_count -= 1;
-                self.backtrace = self.codemap().with_expn_info(expn_id, |expn_info| {
-                    expn_info.map_or(NO_EXPANSION, |ei| ei.call_site.expn_id)
-                });
-            }
-        }
-    }
+    pub fn bt_pop(&mut self) {}
 
     pub fn insert_macro(&mut self, def: ast::MacroDef) {
         if def.export {
@@ -829,6 +778,28 @@ impl<'a> ExtCtxt<'a> {
             }
         }
     }
+
+    pub fn initialize(&mut self, user_exts: Vec<NamedSyntaxExtension>, krate: &ast::Crate) {
+        if std_inject::no_core(&krate) {
+            self.crate_root = None;
+        } else if std_inject::no_std(&krate) {
+            self.crate_root = Some("core");
+        } else {
+            self.crate_root = Some("std");
+        }
+
+        for (name, extension) in user_exts {
+            self.syntax_env.insert(name, extension);
+        }
+
+        self.syntax_env.current_module = Module(0);
+        let mut paths = ModulePaths {
+            mod_path: vec![token::str_to_ident(&self.ecfg.crate_name)],
+            directory: PathBuf::from(self.parse_sess.codemap().span_to_filename(krate.span)),
+        };
+        paths.directory.pop();
+        self.syntax_env.module_data[0].paths = Rc::new(paths);
+    }
 }
 
 /// Extract a string literal from the macro expanded version of `expr`,
@@ -915,79 +886,97 @@ pub fn get_exprs_from_tts(cx: &mut ExtCtxt,
 ///
 /// This environment maps Names to SyntaxExtensions.
 pub struct SyntaxEnv {
-    chain: Vec<MapChainFrame>,
+    module_data: Vec<ModuleData>,
+    pub current_module: Module,
+
     /// All bang-style macro/extension names
     /// encountered so far; to be used for diagnostics in resolve
     pub names: HashSet<Name>,
 }
 
-// impl question: how to implement it? Initially, the
-// env will contain only macros, so it might be painful
-// to add an empty frame for every context. Let's just
-// get it working, first....
+#[derive(Copy, Clone, PartialEq, Eq)]
+pub struct Module(u32);
 
-// NB! the mutability of the underlying maps means that
-// if expansion is out-of-order, a deeper scope may be
-// able to refer to a macro that was added to an enclosing
-// scope lexically later than the deeper scope.
+struct ModuleData {
+    parent: Module,
+    paths: Rc<ModulePaths>,
+    macros: HashMap<Name, Rc<SyntaxExtension>>,
+    macros_escape: bool,
+    in_block: bool,
+}
 
-struct MapChainFrame {
-    info: BlockInfo,
-    map: HashMap<Name, Rc<SyntaxExtension>>,
+#[derive(Clone)]
+pub struct ModulePaths {
+    pub mod_path: Vec<ast::Ident>,
+    pub directory: PathBuf,
 }
 
 impl SyntaxEnv {
     fn new() -> SyntaxEnv {
-        let mut map = SyntaxEnv { chain: Vec::new() , names: HashSet::new()};
-        map.push_frame();
-        map
+        let mut env = SyntaxEnv {
+            current_module: Module(0),
+            module_data: Vec::new(),
+            names: HashSet::new(),
+        };
+        let paths = Rc::new(ModulePaths { mod_path: Vec::new(), directory: PathBuf::new() });
+        env.add_module(false, false, paths);
+        env
     }
 
-    pub fn push_frame(&mut self) {
-        self.chain.push(MapChainFrame {
-            info: BlockInfo::new(),
-            map: HashMap::new(),
-        });
+    fn data(&self, module: Module) -> &ModuleData {
+        &self.module_data[module.0 as usize]
     }
 
-    pub fn pop_frame(&mut self) {
-        assert!(self.chain.len() > 1, "too many pops on MapChain!");
-        self.chain.pop();
+    pub fn paths(&self) -> Rc<ModulePaths> {
+        self.data(self.current_module).paths.clone()
     }
 
-    fn find_escape_frame(&mut self) -> &mut MapChainFrame {
-        for (i, frame) in self.chain.iter_mut().enumerate().rev() {
-            if !frame.info.macros_escape || i == 0 {
-                return frame
-            }
-        }
-        unreachable!()
+    pub fn in_block(&self) -> bool {
+        self.data(self.current_module).in_block
     }
 
-    pub fn find(&self, k: Name) -> Option<Rc<SyntaxExtension>> {
-        for frame in self.chain.iter().rev() {
-            if let Some(v) = frame.map.get(&k) {
-                return Some(v.clone());
+    pub fn add_module(&mut self, macros_escape: bool, in_block: bool, paths: Rc<ModulePaths>)
+                      -> Module {
+        let data = ModuleData {
+            parent: self.current_module,
+            paths: paths,
+            macros: HashMap::new(),
+            macros_escape: macros_escape,
+            in_block: in_block,
+        };
+
+        self.module_data.push(data);
+        Module(self.module_data.len() as u32 - 1)
+    }
+
+    pub fn find(&self, name: Name) -> Option<Rc<SyntaxExtension>> {
+        let mut module = self.current_module;
+        let mut module_data;
+        loop {
+            module_data = self.data(module);
+            if let Some(ext) = module_data.macros.get(&name) {
+                return Some(ext.clone());
             }
+            if module == module_data.parent {
+                return None;
+            }
+            module = module_data.parent;
         }
-        None
     }
 
-    pub fn insert(&mut self, k: Name, v: SyntaxExtension) {
-        if let NormalTT(..) = v {
-            self.names.insert(k);
+    pub fn insert(&mut self, name: Name, ext: SyntaxExtension) {
+        if let NormalTT(..) = ext {
+            self.names.insert(name);
         }
-        self.find_escape_frame().map.insert(k, Rc::new(v));
-    }
 
-    pub fn info(&mut self) -> &mut BlockInfo {
-        let last_chain_index = self.chain.len() - 1;
-        &mut self.chain[last_chain_index].info
+        let mut module = self.current_module;
+        while self.data(module).macros_escape {
+            module = self.data(module).parent;
+        }
+        self.module_data[module.0 as usize].macros.insert(name, Rc::new(ext));
     }
 
     pub fn is_crate_root(&mut self) -> bool {
-        // The first frame is pushed in `SyntaxEnv::new()` and the second frame is
-        // pushed when folding the crate root pseudo-module (c.f. noop_fold_crate).
-        self.chain.len() <= 2
+        self.current_module == Module(0)
     }
 }
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index d06b77a5b05..4715eda8374 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -9,11 +9,12 @@
 // except according to those terms.
 
 use ast::{Block, Crate, Ident, Mac_, PatKind};
-use ast::{MacStmtStyle, Stmt, StmtKind, ItemKind};
+use ast::{MacStmtStyle, StmtKind, ItemKind};
 use ast;
 use ext::hygiene::Mark;
+use ext::placeholders::{self, placeholder, PlaceholderExpander};
 use attr::{self, HasAttrs};
-use codemap::{dummy_spanned, ExpnInfo, NameAndSpan, MacroBang, MacroAttribute};
+use codemap::{ExpnInfo, NameAndSpan, MacroBang, MacroAttribute};
 use syntax_pos::{self, Span, ExpnId};
 use config::StripUnconfigured;
 use ext::base::*;
@@ -24,150 +25,310 @@ use parse::token::{intern, keywords};
 use ptr::P;
 use tokenstream::TokenTree;
 use util::small_vector::SmallVector;
-use visit;
-use visit::Visitor;
-use std_inject;
 
-// A trait for AST nodes and AST node lists into which macro invocations may expand.
-trait MacroGenerable: Sized {
-    // Expand the given MacResult using its appropriate `make_*` method.
-    fn make_with<'a>(result: Box<MacResult + 'a>) -> Option<Self>;
+use std::mem;
+use std::path::PathBuf;
+use std::rc::Rc;
+
+macro_rules! expansions {
+    ($($kind:ident: $ty:ty [$($vec:ident, $ty_elt:ty)*], $kind_name:expr, .$make:ident,
+            $(.$fold:ident)*  $(lift .$fold_elt:ident)*;)*) => {
+        #[derive(Copy, Clone)]
+        pub enum ExpansionKind { OptExpr, $( $kind, )*  }
+        pub enum Expansion { OptExpr(Option<P<ast::Expr>>), $( $kind($ty), )* }
+
+        impl ExpansionKind {
+            fn name(self) -> &'static str {
+                match self {
+                    ExpansionKind::OptExpr => "expression",
+                    $( ExpansionKind::$kind => $kind_name, )*
+                }
+            }
 
-    // Fold this node or list of nodes using the given folder.
-    fn fold_with<F: Folder>(self, folder: &mut F) -> Self;
-    fn visit_with<V: Visitor>(&self, visitor: &mut V);
+            fn make_from<'a>(self, result: Box<MacResult + 'a>) -> Option<Expansion> {
+                match self {
+                    ExpansionKind::OptExpr => result.make_expr().map(Some).map(Expansion::OptExpr),
+                    $( ExpansionKind::$kind => result.$make().map(Expansion::$kind), )*
+                }
+            }
+        }
 
-    // The user-friendly name of the node type (e.g. "expression", "item", etc.) for diagnostics.
-    fn kind_name() -> &'static str;
+        impl Expansion {
+            pub fn make_opt_expr(self) -> Option<P<ast::Expr>> {
+                match self {
+                    Expansion::OptExpr(expr) => expr,
+                    _ => panic!("Expansion::make_* called on the wrong kind of expansion"),
+                }
+            }
+            $( pub fn $make(self) -> $ty {
+                match self {
+                    Expansion::$kind(ast) => ast,
+                    _ => panic!("Expansion::make_* called on the wrong kind of expansion"),
+                }
+            } )*
+
+            pub fn fold_with<F: Folder>(self, folder: &mut F) -> Self {
+                use self::Expansion::*;
+                match self {
+                    OptExpr(expr) => OptExpr(expr.and_then(|expr| folder.fold_opt_expr(expr))),
+                    $($( $kind(ast) => $kind(folder.$fold(ast)), )*)*
+                    $($( $kind(ast) => {
+                        $kind(ast.into_iter().flat_map(|ast| folder.$fold_elt(ast)).collect())
+                    }, )*)*
+                }
+            }
+        }
 
-    // Return a placeholder expansion to allow compilation to continue after an erroring expansion.
-    fn dummy(span: Span) -> Self {
-        Self::make_with(DummyResult::any(span)).unwrap()
+        impl<'a, 'b> Folder for MacroExpander<'a, 'b> {
+            fn fold_opt_expr(&mut self, expr: P<ast::Expr>) -> Option<P<ast::Expr>> {
+                self.expand(Expansion::OptExpr(Some(expr))).make_opt_expr()
+            }
+            $($(fn $fold(&mut self, node: $ty) -> $ty {
+                self.expand(Expansion::$kind(node)).$make()
+            })*)*
+            $($(fn $fold_elt(&mut self, node: $ty_elt) -> $ty {
+                self.expand(Expansion::$kind(SmallVector::one(node))).$make()
+            })*)*
+        }
     }
 }
 
-macro_rules! impl_macro_generable {
-    ($($ty:ty: $kind_name:expr, .$make:ident,
-               $(.$fold:ident)*  $(lift .$fold_elt:ident)*,
-               $(.$visit:ident)* $(lift .$visit_elt:ident)*;)*) => { $(
-        impl MacroGenerable for $ty {
-            fn kind_name() -> &'static str { $kind_name }
-            fn make_with<'a>(result: Box<MacResult + 'a>) -> Option<Self> { result.$make() }
-            fn fold_with<F: Folder>(self, folder: &mut F) -> Self {
-                $( folder.$fold(self) )*
-                $( self.into_iter().flat_map(|item| folder. $fold_elt (item)).collect() )*
-            }
-            fn visit_with<V: Visitor>(&self, visitor: &mut V) {
-                $( visitor.$visit(self) )*
-                $( for item in self.as_slice() { visitor. $visit_elt (item) } )*
-            }
+expansions! {
+    Expr: P<ast::Expr> [], "expression", .make_expr, .fold_expr;
+    Pat: P<ast::Pat>   [], "pattern",    .make_pat,  .fold_pat;
+    Ty: P<ast::Ty>     [], "type",       .make_ty,   .fold_ty;
+    Stmts: SmallVector<ast::Stmt> [SmallVector, ast::Stmt],
+        "statement",  .make_stmts,       lift .fold_stmt;
+    Items: SmallVector<P<ast::Item>> [SmallVector, P<ast::Item>],
+        "item",       .make_items,       lift .fold_item;
+    TraitItems: SmallVector<ast::TraitItem> [SmallVector, ast::TraitItem],
+        "trait item", .make_trait_items, lift .fold_trait_item;
+    ImplItems: SmallVector<ast::ImplItem> [SmallVector, ast::ImplItem],
+        "impl item",  .make_impl_items,  lift .fold_impl_item;
+}
+
+impl ExpansionKind {
+    fn dummy(self, span: Span) -> Expansion {
+        self.make_from(DummyResult::any(span)).unwrap()
+    }
+
+    fn expect_from_annotatables<I: IntoIterator<Item = Annotatable>>(self, items: I) -> Expansion {
+        let items = items.into_iter();
+        match self {
+            ExpansionKind::Items =>
+                Expansion::Items(items.map(Annotatable::expect_item).collect()),
+            ExpansionKind::ImplItems =>
+                Expansion::ImplItems(items.map(Annotatable::expect_impl_item).collect()),
+            ExpansionKind::TraitItems =>
+                Expansion::TraitItems(items.map(Annotatable::expect_trait_item).collect()),
+            _ => unreachable!(),
         }
-    )* }
+    }
 }
 
-impl_macro_generable! {
-    P<ast::Expr>: "expression", .make_expr, .fold_expr, .visit_expr;
-    P<ast::Pat>:  "pattern",    .make_pat,  .fold_pat,  .visit_pat;
-    P<ast::Ty>:   "type",       .make_ty,   .fold_ty,   .visit_ty;
-    SmallVector<ast::Stmt>: "statement", .make_stmts, lift .fold_stmt, lift .visit_stmt;
-    SmallVector<P<ast::Item>>: "item",   .make_items, lift .fold_item, lift .visit_item;
-    SmallVector<ast::TraitItem>:
-        "trait item", .make_trait_items, lift .fold_trait_item, lift .visit_trait_item;
-    SmallVector<ast::ImplItem>:
-        "impl item",  .make_impl_items,  lift .fold_impl_item,  lift .visit_impl_item;
+pub struct Invocation {
+    kind: InvocationKind,
+    expansion_kind: ExpansionKind,
+    mark: Mark,
+    module: Module,
+    backtrace: ExpnId,
+    depth: usize,
 }
 
-impl MacroGenerable for Option<P<ast::Expr>> {
-    fn kind_name() -> &'static str { "expression" }
-    fn make_with<'a>(result: Box<MacResult + 'a>) -> Option<Self> {
-        result.make_expr().map(Some)
+enum InvocationKind {
+    Bang {
+        attrs: Vec<ast::Attribute>,
+        mac: ast::Mac,
+        ident: Option<Ident>,
+        span: Span,
+    },
+    Attr {
+        attr: ast::Attribute,
+        item: Annotatable,
+    },
+}
+
+pub struct MacroExpander<'a, 'b:'a> {
+    pub cx: &'a mut ExtCtxt<'b>,
+    pub single_step: bool,
+    pub keep_macs: bool,
+}
+
+impl<'a, 'b> MacroExpander<'a, 'b> {
+    pub fn new(cx: &'a mut ExtCtxt<'b>,
+               single_step: bool,
+               keep_macs: bool) -> MacroExpander<'a, 'b> {
+        MacroExpander {
+            cx: cx,
+            single_step: single_step,
+            keep_macs: keep_macs
+        }
     }
-    fn fold_with<F: Folder>(self, folder: &mut F) -> Self {
-        self.and_then(|expr| folder.fold_opt_expr(expr))
+
+    fn expand_crate(&mut self, mut krate: ast::Crate) -> ast::Crate {
+        let err_count = self.cx.parse_sess.span_diagnostic.err_count();
+
+        let items = Expansion::Items(SmallVector::many(krate.module.items));
+        krate.module.items = self.expand(items).make_items().into();
+        krate.exported_macros = self.cx.exported_macros.clone();
+
+        if self.cx.parse_sess.span_diagnostic.err_count() > err_count {
+            self.cx.parse_sess.span_diagnostic.abort_if_errors();
+        }
+
+        krate
     }
-    fn visit_with<V: Visitor>(&self, visitor: &mut V) {
-        self.as_ref().map(|expr| visitor.visit_expr(expr));
+
+    // Fully expand all the invocations in `expansion`.
+    fn expand(&mut self, expansion: Expansion) -> Expansion {
+        self.cx.recursion_count = 0;
+        let (expansion, mut invocations) = self.collect_invocations(expansion);
+        invocations.reverse();
+
+        let mut expansions = vec![vec![(0, expansion)]];
+        while let Some(invoc) = invocations.pop() {
+            let Invocation { mark, module, depth, backtrace, .. } = invoc;
+            self.cx.syntax_env.current_module = module;
+            self.cx.recursion_count = depth;
+            self.cx.backtrace = backtrace;
+
+            let expansion = self.expand_invoc(invoc);
+
+            self.cx.syntax_env.current_module = module;
+            self.cx.recursion_count = depth + 1;
+            let (expansion, new_invocations) = self.collect_invocations(expansion);
+
+            if expansions.len() == depth {
+                expansions.push(Vec::new());
+            }
+            expansions[depth].push((mark.as_u32(), expansion));
+            if !self.single_step {
+                invocations.extend(new_invocations.into_iter().rev());
+            }
+        }
+
+        let mut placeholder_expander = PlaceholderExpander::new();
+        while let Some(expansions) = expansions.pop() {
+            for (mark, expansion) in expansions.into_iter().rev() {
+                let expansion = expansion.fold_with(&mut placeholder_expander);
+                placeholder_expander.add(mark, expansion);
+            }
+        }
+
+        placeholder_expander.remove(0)
+    }
+
+    fn collect_invocations(&mut self, expansion: Expansion) -> (Expansion, Vec<Invocation>) {
+        let crate_config = mem::replace(&mut self.cx.cfg, Vec::new());
+        let result = {
+            let mut collector = InvocationCollector {
+                cfg: StripUnconfigured {
+                    config: &crate_config,
+                    should_test: self.cx.ecfg.should_test,
+                    sess: self.cx.parse_sess,
+                    features: self.cx.ecfg.features,
+                },
+                cx: self.cx,
+                invocations: Vec::new(),
+            };
+            (expansion.fold_with(&mut collector), collector.invocations)
+        };
+
+        self.cx.cfg = crate_config;
+        result
     }
-}
 
-pub fn expand_expr(expr: ast::Expr, fld: &mut MacroExpander) -> P<ast::Expr> {
-    match expr.node {
-        // expr_mac should really be expr_ext or something; it's the
-        // entry-point for all syntax extensions.
-        ast::ExprKind::Mac(mac) => {
-            return expand_mac_invoc(mac, None, expr.attrs.into(), expr.span, fld);
+    fn expand_invoc(&mut self, invoc: Invocation) -> Expansion {
+        match invoc.kind {
+            InvocationKind::Bang { .. } => self.expand_bang_invoc(invoc),
+            InvocationKind::Attr { .. } => self.expand_attr_invoc(invoc),
         }
-        _ => P(noop_fold_expr(expr, fld)),
     }
-}
 
-struct MacroScopePlaceholder;
-impl MacResult for MacroScopePlaceholder {
-    fn make_items(self: Box<Self>) -> Option<SmallVector<P<ast::Item>>> {
-        Some(SmallVector::one(P(ast::Item {
-            ident: keywords::Invalid.ident(),
-            attrs: Vec::new(),
-            id: ast::DUMMY_NODE_ID,
-            node: ast::ItemKind::Mac(dummy_spanned(ast::Mac_ {
-                path: ast::Path { span: syntax_pos::DUMMY_SP, global: false, segments: Vec::new() },
-                tts: Vec::new(),
-            })),
-            vis: ast::Visibility::Inherited,
-            span: syntax_pos::DUMMY_SP,
-        })))
+    fn expand_attr_invoc(&mut self, invoc: Invocation) -> Expansion {
+        let Invocation { expansion_kind: kind, .. } = invoc;
+        let (attr, item) = match invoc.kind {
+            InvocationKind::Attr { attr, item } => (attr, item),
+            _ => unreachable!(),
+        };
+
+        let extension = match self.cx.syntax_env.find(intern(&attr.name())) {
+            Some(extension) => extension,
+            None => unreachable!(),
+        };
+
+        attr::mark_used(&attr);
+        self.cx.bt_push(ExpnInfo {
+            call_site: attr.span,
+            callee: NameAndSpan {
+                format: MacroAttribute(intern(&attr.name())),
+                span: Some(attr.span),
+                allow_internal_unstable: false,
+            }
+        });
+
+        match *extension {
+            MultiModifier(ref mac) => {
+                let item = mac.expand(self.cx, attr.span, &attr.node.value, item);
+                kind.expect_from_annotatables(item)
+            }
+            MultiDecorator(ref mac) => {
+                let mut items = Vec::new();
+                mac.expand(self.cx, attr.span, &attr.node.value, &item,
+                           &mut |item| items.push(item));
+                items.push(item);
+                kind.expect_from_annotatables(items)
+            }
+            _ => unreachable!(),
+        }
     }
-}
 
-/// Expand a macro invocation. Returns the result of expansion.
-fn expand_mac_invoc<T>(mac: ast::Mac, ident: Option<Ident>, attrs: Vec<ast::Attribute>, span: Span,
-                       fld: &mut MacroExpander) -> T
-    where T: MacroGenerable,
-{
-    // It would almost certainly be cleaner to pass the whole macro invocation in,
-    // rather than pulling it apart and marking the tts and the ctxt separately.
-    let Mac_ { path, tts, .. } = mac.node;
-    let mark = Mark::fresh();
-
-    fn mac_result<'a>(path: &ast::Path, ident: Option<Ident>, tts: Vec<TokenTree>, mark: Mark,
-                      attrs: Vec<ast::Attribute>, call_site: Span, fld: &'a mut MacroExpander)
-                      -> Option<Box<MacResult + 'a>> {
+    /// Expand a macro invocation. Returns the result of expansion.
+    fn expand_bang_invoc(&mut self, invoc: Invocation) -> Expansion {
+        let Invocation { mark, expansion_kind: kind, .. } = invoc;
+        let (attrs, mac, ident, span) = match invoc.kind {
+            InvocationKind::Bang { attrs, mac, ident, span } => (attrs, mac, ident, span),
+            _ => unreachable!(),
+        };
+        let Mac_ { path, tts, .. } = mac.node;
+
         // Detect use of feature-gated or invalid attributes on macro invoations
         // since they will not be detected after macro expansion.
         for attr in attrs.iter() {
-            feature_gate::check_attribute(&attr, &fld.cx.parse_sess.span_diagnostic,
-                                          &fld.cx.parse_sess.codemap(),
-                                          &fld.cx.ecfg.features.unwrap());
+            feature_gate::check_attribute(&attr, &self.cx.parse_sess.span_diagnostic,
+                                          &self.cx.parse_sess.codemap(),
+                                          &self.cx.ecfg.features.unwrap());
         }
 
         if path.segments.len() > 1 || path.global || !path.segments[0].parameters.is_empty() {
-            fld.cx.span_err(path.span, "expected macro name without module separators");
-            return None;
+            self.cx.span_err(path.span, "expected macro name without module separators");
+            return kind.dummy(span);
         }
 
         let extname = path.segments[0].identifier.name;
-        let extension = if let Some(extension) = fld.cx.syntax_env.find(extname) {
+        let extension = if let Some(extension) = self.cx.syntax_env.find(extname) {
             extension
         } else {
-            let mut err = fld.cx.struct_span_err(path.span,
-                                                 &format!("macro undefined: '{}!'", &extname));
-            fld.cx.suggest_macro_name(&extname.as_str(), &mut err);
+            let mut err =
+                self.cx.struct_span_err(path.span, &format!("macro undefined: '{}!'", &extname));
+            self.cx.suggest_macro_name(&extname.as_str(), &mut err);
             err.emit();
-            return None;
+            return kind.dummy(span);
         };
 
         let ident = ident.unwrap_or(keywords::Invalid.ident());
         let marked_tts = mark_tts(&tts, mark);
-        match *extension {
+        let opt_expanded = match *extension {
             NormalTT(ref expandfun, exp_span, allow_internal_unstable) => {
                 if ident.name != keywords::Invalid.name() {
                     let msg =
                         format!("macro {}! expects no ident argument, given '{}'", extname, ident);
-                    fld.cx.span_err(path.span, &msg);
-                    return None;
+                    self.cx.span_err(path.span, &msg);
+                    return kind.dummy(span);
                 }
 
-                fld.cx.bt_push(ExpnInfo {
-                    call_site: call_site,
+                self.cx.bt_push(ExpnInfo {
+                    call_site: span,
                     callee: NameAndSpan {
                         format: MacroBang(extname),
                         span: exp_span,
@@ -175,18 +336,18 @@ fn expand_mac_invoc<T>(mac: ast::Mac, ident: Option<Ident>, attrs: Vec<ast::Attr
                     },
                 });
 
-                Some(expandfun.expand(fld.cx, call_site, &marked_tts))
+                kind.make_from(expandfun.expand(self.cx, span, &marked_tts))
             }
 
             IdentTT(ref expander, tt_span, allow_internal_unstable) => {
                 if ident.name == keywords::Invalid.name() {
-                    fld.cx.span_err(path.span,
+                    self.cx.span_err(path.span,
                                     &format!("macro {}! expects an ident argument", extname));
-                    return None;
+                    return kind.dummy(span);
                 };
 
-                fld.cx.bt_push(ExpnInfo {
-                    call_site: call_site,
+                self.cx.bt_push(ExpnInfo {
+                    call_site: span,
                     callee: NameAndSpan {
                         format: MacroBang(extname),
                         span: tt_span,
@@ -194,18 +355,18 @@ fn expand_mac_invoc<T>(mac: ast::Mac, ident: Option<Ident>, attrs: Vec<ast::Attr
                     }
                 });
 
-                Some(expander.expand(fld.cx, call_site, ident, marked_tts))
+                kind.make_from(expander.expand(self.cx, span, ident, marked_tts))
             }
 
             MacroRulesTT => {
                 if ident.name == keywords::Invalid.name() {
-                    fld.cx.span_err(path.span,
+                    self.cx.span_err(path.span,
                                     &format!("macro {}! expects an ident argument", extname));
-                    return None;
+                    return kind.dummy(span);
                 };
 
-                fld.cx.bt_push(ExpnInfo {
-                    call_site: call_site,
+                self.cx.bt_push(ExpnInfo {
+                    call_site: span,
                     callee: NameAndSpan {
                         format: MacroBang(extname),
                         span: None,
@@ -218,7 +379,7 @@ fn expand_mac_invoc<T>(mac: ast::Mac, ident: Option<Ident>, attrs: Vec<ast::Attr
                 let def = ast::MacroDef {
                     ident: ident,
                     id: ast::DUMMY_NODE_ID,
-                    span: call_site,
+                    span: span,
                     imported_from: None,
                     use_locally: true,
                     body: marked_tts,
@@ -227,427 +388,332 @@ fn expand_mac_invoc<T>(mac: ast::Mac, ident: Option<Ident>, attrs: Vec<ast::Attr
                     attrs: attrs,
                 };
 
-                fld.cx.insert_macro(def.clone());
+                self.cx.insert_macro(def.clone());
 
-                // macro_rules! has a side effect, but expands to nothing.
                 // If keep_macs is true, expands to a MacEager::items instead.
-                if fld.keep_macs {
-                    Some(MacEager::items(SmallVector::one(P(ast::Item {
-                        ident: def.ident,
-                        attrs: def.attrs.clone(),
-                        id: ast::DUMMY_NODE_ID,
-                        node: ast::ItemKind::Mac(ast::Mac {
-                            span: def.span,
-                            node: ast::Mac_ {
-                                path: path.clone(),
-                                tts: def.body.clone(),
-                            }
-                        }),
-                        vis: ast::Visibility::Inherited,
-                        span: def.span,
-                    }))))
+                if self.keep_macs {
+                    Some(placeholders::reconstructed_macro_rules(&def, &path))
                 } else {
-                    Some(Box::new(MacroScopePlaceholder))
+                    Some(placeholders::macro_scope_placeholder())
                 }
             }
 
             MultiDecorator(..) | MultiModifier(..) => {
-                fld.cx.span_err(path.span,
-                                &format!("`{}` can only be used in attributes", extname));
-                None
+                self.cx.span_err(path.span,
+                                 &format!("`{}` can only be used in attributes", extname));
+                return kind.dummy(span);
             }
-        }
-    }
+        };
 
-    let opt_expanded = T::make_with(match mac_result(&path, ident, tts, mark, attrs, span, fld) {
-        Some(result) => result,
-        None => return T::dummy(span),
-    });
-
-    let expanded = if let Some(expanded) = opt_expanded {
-        expanded
-    } else {
-        let msg = format!("non-{kind} macro in {kind} position: {name}",
-                          name = path.segments[0].identifier.name, kind = T::kind_name());
-        fld.cx.span_err(path.span, &msg);
-        return T::dummy(span);
-    };
-
-    let marked = expanded.fold_with(&mut Marker { mark: mark, expn_id: Some(fld.cx.backtrace()) });
-    let configured = marked.fold_with(&mut fld.strip_unconfigured());
-    fld.load_macros(&configured);
-
-    let fully_expanded = if fld.single_step {
-        configured
-    } else {
-        configured.fold_with(fld)
-    };
-
-    fld.cx.bt_pop();
-    fully_expanded
-}
+        let expanded = if let Some(expanded) = opt_expanded {
+            expanded
+        } else {
+            let msg = format!("non-{kind} macro in {kind} position: {name}",
+                              name = path.segments[0].identifier.name, kind = kind.name());
+            self.cx.span_err(path.span, &msg);
+            return kind.dummy(span);
+        };
 
-// eval $e with a new exts frame.
-// must be a macro so that $e isn't evaluated too early.
-macro_rules! with_exts_frame {
-    ($extsboxexpr:expr,$macros_escape:expr,$e:expr) =>
-    ({$extsboxexpr.push_frame();
-      $extsboxexpr.info().macros_escape = $macros_escape;
-      let result = $e;
-      $extsboxexpr.pop_frame();
-      result
-     })
+        expanded.fold_with(&mut Marker {
+            mark: mark,
+            expn_id: Some(self.cx.backtrace()),
+        })
+    }
 }
 
-// When we enter a module, record it, for the sake of `module!`
-pub fn expand_item(it: P<ast::Item>, fld: &mut MacroExpander)
-                   -> SmallVector<P<ast::Item>> {
-    expand_annotatable(Annotatable::Item(it), fld)
-        .into_iter().map(|i| i.expect_item()).collect()
+struct InvocationCollector<'a, 'b: 'a> {
+    cx: &'a mut ExtCtxt<'b>,
+    cfg: StripUnconfigured<'a>,
+    invocations: Vec<Invocation>,
 }
 
-// does this attribute list contain "macro_use" ?
-fn contains_macro_use(fld: &mut MacroExpander, attrs: &[ast::Attribute]) -> bool {
-    for attr in attrs {
-        let mut is_use = attr.check_name("macro_use");
-        if attr.check_name("macro_escape") {
-            let mut err =
-                fld.cx.struct_span_warn(attr.span,
-                                        "macro_escape is a deprecated synonym for macro_use");
-            is_use = true;
-            if let ast::AttrStyle::Inner = attr.node.style {
-                err.help("consider an outer attribute, \
-                          #[macro_use] mod ...").emit();
-            } else {
-                err.emit();
-            }
-        };
-
-        if is_use {
-            if !attr.is_word() {
-              fld.cx.span_err(attr.span, "arguments to macro_use are not allowed here");
-            }
-            return true;
+macro_rules! fully_configure {
+    ($this:ident, $node:ident, $noop_fold:ident) => {
+        match $noop_fold($node, &mut $this.cfg).pop() {
+            Some(node) => node,
+            None => return SmallVector::zero(),
         }
     }
-    false
 }
 
-/// Expand a stmt
-fn expand_stmt(stmt: Stmt, fld: &mut MacroExpander) -> SmallVector<Stmt> {
-    let (mac, style, attrs) = match stmt.node {
-        StmtKind::Mac(mac) => mac.unwrap(),
-        _ => return noop_fold_stmt(stmt, fld)
-    };
-
-    let mut fully_expanded: SmallVector<ast::Stmt> =
-        expand_mac_invoc(mac, None, attrs.into(), stmt.span, fld);
-
-    // If this is a macro invocation with a semicolon, then apply that
-    // semicolon to the final statement produced by expansion.
-    if style == MacStmtStyle::Semicolon {
-        if let Some(stmt) = fully_expanded.pop() {
-            fully_expanded.push(stmt.add_trailing_semicolon());
-        }
+impl<'a, 'b> InvocationCollector<'a, 'b> {
+    fn collect(&mut self, expansion_kind: ExpansionKind, kind: InvocationKind) -> Expansion {
+        let mark = Mark::fresh();
+        self.invocations.push(Invocation {
+            kind: kind,
+            expansion_kind: expansion_kind,
+            mark: mark,
+            module: self.cx.syntax_env.current_module,
+            backtrace: self.cx.backtrace,
+            depth: self.cx.recursion_count,
+        });
+        placeholder(expansion_kind, mark.as_u32())
     }
 
-    fully_expanded
-}
+    fn collect_bang(
+        &mut self, mac: ast::Mac, attrs: Vec<ast::Attribute>, span: Span, kind: ExpansionKind,
+    ) -> Expansion {
+        self.collect(kind, InvocationKind::Bang { attrs: attrs, mac: mac, ident: None, span: span })
+    }
 
-fn expand_pat(p: P<ast::Pat>, fld: &mut MacroExpander) -> P<ast::Pat> {
-    match p.node {
-        PatKind::Mac(_) => {}
-        _ => return noop_fold_pat(p, fld)
+    fn collect_attr(&mut self, attr: ast::Attribute, item: Annotatable, kind: ExpansionKind)
+                    -> Expansion {
+        self.collect(kind, InvocationKind::Attr { attr: attr, item: item })
     }
-    p.and_then(|ast::Pat {node, span, ..}| {
-        match node {
-            PatKind::Mac(mac) => expand_mac_invoc(mac, None, Vec::new(), span, fld),
-            _ => unreachable!()
-        }
-    })
-}
 
-fn expand_multi_modified(a: Annotatable, fld: &mut MacroExpander) -> SmallVector<Annotatable> {
-    match a {
-        Annotatable::Item(it) => match it.node {
-            ast::ItemKind::Mac(..) => {
-                if match it.node {
-                    ItemKind::Mac(ref mac) => mac.node.path.segments.is_empty(),
-                    _ => unreachable!(),
-                } {
-                    return SmallVector::one(Annotatable::Item(it));
+    // If `item` is an attr invocation, remove and return the macro attribute.
+    fn classify_item<T: HasAttrs>(&self, mut item: T) -> (T, Option<ast::Attribute>) {
+        let mut attr = None;
+        item = item.map_attrs(|mut attrs| {
+            for i in 0..attrs.len() {
+                if let Some(extension) = self.cx.syntax_env.find(intern(&attrs[i].name())) {
+                    match *extension {
+                        MultiModifier(..) | MultiDecorator(..) => {
+                            attr = Some(attrs.remove(i));
+                            break;
+                        }
+                        _ => {}
+                    }
                 }
-                it.and_then(|it| match it.node {
-                    ItemKind::Mac(mac) =>
-                        expand_mac_invoc(mac, Some(it.ident), it.attrs, it.span, fld),
-                    _ => unreachable!(),
-                })
             }
-            ast::ItemKind::Mod(_) | ast::ItemKind::ForeignMod(_) => {
-                let valid_ident =
-                    it.ident.name != keywords::Invalid.name();
-
-                if valid_ident {
-                    fld.cx.mod_push(it.ident);
-                }
-                let macro_use = contains_macro_use(fld, &it.attrs);
-                let result = with_exts_frame!(fld.cx.syntax_env,
-                                              macro_use,
-                                              noop_fold_item(it, fld));
-                if valid_ident {
-                    fld.cx.mod_pop();
+            attrs
+        });
+        (item, attr)
+    }
+
+    // does this attribute list contain "macro_use" ?
+    fn contains_macro_use(&mut self, attrs: &[ast::Attribute]) -> bool {
+        for attr in attrs {
+            let mut is_use = attr.check_name("macro_use");
+            if attr.check_name("macro_escape") {
+                let msg = "macro_escape is a deprecated synonym for macro_use";
+                let mut err = self.cx.struct_span_warn(attr.span, msg);
+                is_use = true;
+                if let ast::AttrStyle::Inner = attr.node.style {
+                    err.help("consider an outer attribute, #[macro_use] mod ...").emit();
+                } else {
+                    err.emit();
                 }
-                result
-            },
-            _ => noop_fold_item(it, fld),
-        }.into_iter().map(|i| Annotatable::Item(i)).collect(),
+            };
 
-        Annotatable::TraitItem(it) => {
-            expand_trait_item(it.unwrap(), fld).into_iter().
-                map(|it| Annotatable::TraitItem(P(it))).collect()
+            if is_use {
+                if !attr.is_word() {
+                    self.cx.span_err(attr.span, "arguments to macro_use are not allowed here");
+                }
+                return true;
+            }
         }
+        false
+    }
 
-        Annotatable::ImplItem(ii) => {
-            expand_impl_item(ii.unwrap(), fld).into_iter().
-                map(|ii| Annotatable::ImplItem(P(ii))).collect()
-        }
+    fn configure<T: HasAttrs>(&mut self, node: T) -> Option<T> {
+        self.cfg.configure(node)
     }
 }
 
-fn expand_annotatable(mut item: Annotatable, fld: &mut MacroExpander) -> SmallVector<Annotatable> {
-    let mut multi_modifier = None;
-    item = item.map_attrs(|mut attrs| {
-        for i in 0..attrs.len() {
-            if let Some(extension) = fld.cx.syntax_env.find(intern(&attrs[i].name())) {
-                match *extension {
-                    MultiModifier(..) | MultiDecorator(..) => {
-                        multi_modifier = Some((attrs.remove(i), extension));
-                        break;
-                    }
-                    _ => {}
-                }
-            }
-        }
-        attrs
-    });
-
-    match multi_modifier {
-        None => expand_multi_modified(item, fld),
-        Some((attr, extension)) => {
-            attr::mark_used(&attr);
-            fld.cx.bt_push(ExpnInfo {
-                call_site: attr.span,
-                callee: NameAndSpan {
-                    format: MacroAttribute(intern(&attr.name())),
-                    span: Some(attr.span),
-                    allow_internal_unstable: false,
-                }
-            });
-
-            let modified = match *extension {
-                MultiModifier(ref mac) => mac.expand(fld.cx, attr.span, &attr.node.value, item),
-                MultiDecorator(ref mac) => {
-                    let mut items = Vec::new();
-                    mac.expand(fld.cx, attr.span, &attr.node.value, &item,
-                               &mut |item| items.push(item));
-                    items.push(item);
-                    items
-                }
-                _ => unreachable!(),
-            };
-
-            fld.cx.bt_pop();
-            let configured = modified.into_iter().flat_map(|it| {
-                it.fold_with(&mut fld.strip_unconfigured())
-            }).collect::<SmallVector<_>>();
+impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
+    fn fold_expr(&mut self, expr: P<ast::Expr>) -> P<ast::Expr> {
+        let mut expr = self.cfg.configure_expr(expr).unwrap();
+        expr.node = self.cfg.configure_expr_kind(expr.node);
 
-            configured.into_iter().flat_map(|it| expand_annotatable(it, fld)).collect()
+        if let ast::ExprKind::Mac(mac) = expr.node {
+            self.collect_bang(mac, expr.attrs.into(), expr.span, ExpansionKind::Expr).make_expr()
+        } else {
+            P(noop_fold_expr(expr, self))
         }
     }
-}
 
-fn expand_impl_item(ii: ast::ImplItem, fld: &mut MacroExpander)
-                 -> SmallVector<ast::ImplItem> {
-    match ii.node {
-        ast::ImplItemKind::Macro(mac) => {
-            expand_mac_invoc(mac, None, ii.attrs, ii.span, fld)
+    fn fold_opt_expr(&mut self, expr: P<ast::Expr>) -> Option<P<ast::Expr>> {
+        let mut expr = configure!(self, expr).unwrap();
+        expr.node = self.cfg.configure_expr_kind(expr.node);
+
+        if let ast::ExprKind::Mac(mac) = expr.node {
+            self.collect_bang(mac, expr.attrs.into(), expr.span, ExpansionKind::OptExpr)
+                .make_opt_expr()
+        } else {
+            Some(P(noop_fold_expr(expr, self)))
         }
-        _ => fold::noop_fold_impl_item(ii, fld)
     }
-}
 
-fn expand_trait_item(ti: ast::TraitItem, fld: &mut MacroExpander)
-                     -> SmallVector<ast::TraitItem> {
-    match ti.node {
-        ast::TraitItemKind::Macro(mac) => {
-            expand_mac_invoc(mac, None, ti.attrs, ti.span, fld)
+    fn fold_pat(&mut self, pat: P<ast::Pat>) -> P<ast::Pat> {
+        match pat.node {
+            PatKind::Mac(_) => {}
+            _ => return noop_fold_pat(pat, self),
         }
-        _ => fold::noop_fold_trait_item(ti, fld)
+
+        pat.and_then(|pat| match pat.node {
+            PatKind::Mac(mac) =>
+                self.collect_bang(mac, Vec::new(), pat.span, ExpansionKind::Pat).make_pat(),
+            _ => unreachable!(),
+        })
     }
-}
 
-pub fn expand_type(t: P<ast::Ty>, fld: &mut MacroExpander) -> P<ast::Ty> {
-    let t = match t.node.clone() {
-        ast::TyKind::Mac(mac) => {
-            expand_mac_invoc(mac, None, Vec::new(), t.span, fld)
-        }
-        _ => t
-    };
+    fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVector<ast::Stmt> {
+        let stmt = match self.cfg.configure_stmt(stmt) {
+            Some(stmt) => stmt,
+            None => return SmallVector::zero(),
+        };
 
-    fold::noop_fold_ty(t, fld)
-}
+        let (mac, style, attrs) = match stmt.node {
+            StmtKind::Mac(mac) => mac.unwrap(),
+            _ => return noop_fold_stmt(stmt, self),
+        };
 
-/// A tree-folder that performs macro expansion
-pub struct MacroExpander<'a, 'b:'a> {
-    pub cx: &'a mut ExtCtxt<'b>,
-    pub single_step: bool,
-    pub keep_macs: bool,
-}
+        let mut placeholder =
+            self.collect_bang(mac, attrs.into(), stmt.span, ExpansionKind::Stmts).make_stmts();
 
-impl<'a, 'b> MacroExpander<'a, 'b> {
-    pub fn new(cx: &'a mut ExtCtxt<'b>,
-               single_step: bool,
-               keep_macs: bool) -> MacroExpander<'a, 'b> {
-        MacroExpander {
-            cx: cx,
-            single_step: single_step,
-            keep_macs: keep_macs
+        // If this is a macro invocation with a semicolon, then apply that
+        // semicolon to the final statement produced by expansion.
+        if style == MacStmtStyle::Semicolon {
+            if let Some(stmt) = placeholder.pop() {
+                placeholder.push(stmt.add_trailing_semicolon());
+            }
         }
+
+        placeholder
     }
 
-    fn strip_unconfigured(&mut self) -> StripUnconfigured {
-        StripUnconfigured {
-            config: &self.cx.cfg,
-            should_test: self.cx.ecfg.should_test,
-            sess: self.cx.parse_sess,
-            features: self.cx.ecfg.features,
-        }
+    fn fold_block(&mut self, block: P<Block>) -> P<Block> {
+        let paths = self.cx.syntax_env.paths();
+        let module = self.cx.syntax_env.add_module(false, true, paths);
+        let orig_module = mem::replace(&mut self.cx.syntax_env.current_module, module);
+        let result = noop_fold_block(block, self);
+        self.cx.syntax_env.current_module = orig_module;
+        result
     }
 
-    fn load_macros<T: MacroGenerable>(&mut self, node: &T) {
-        struct MacroLoadingVisitor<'a, 'b: 'a>{
-            cx: &'a mut ExtCtxt<'b>,
-            at_crate_root: bool,
+    fn fold_item(&mut self, item: P<ast::Item>) -> SmallVector<P<ast::Item>> {
+        let item = configure!(self, item);
+
+        let (item, attr) = self.classify_item(item);
+        if let Some(attr) = attr {
+            let item = Annotatable::Item(fully_configure!(self, item, noop_fold_item));
+            return self.collect_attr(attr, item, ExpansionKind::Items).make_items();
         }
 
-        impl<'a, 'b> Visitor for MacroLoadingVisitor<'a, 'b> {
-            fn visit_mac(&mut self, _: &ast::Mac) {}
-            fn visit_item(&mut self, item: &ast::Item) {
-                if let ast::ItemKind::ExternCrate(..) = item.node {
-                    // We need to error on `#[macro_use] extern crate` when it isn't at the
-                    // crate root, because `$crate` won't work properly.
-                    for def in self.cx.loader.load_crate(item, self.at_crate_root) {
-                        match def {
-                            LoadedMacro::Def(def) => self.cx.insert_macro(def),
-                            LoadedMacro::CustomDerive(name, ext) => {
-                                self.cx.insert_custom_derive(&name, ext, item.span);
-                            }
-                        }
+        match item.node {
+            ast::ItemKind::Mac(..) => {
+                if match item.node {
+                    ItemKind::Mac(ref mac) => mac.node.path.segments.is_empty(),
+                    _ => unreachable!(),
+                } {
+                    return SmallVector::one(item);
+                }
+
+                item.and_then(|item| match item.node {
+                    ItemKind::Mac(mac) => {
+                        self.collect(ExpansionKind::Items, InvocationKind::Bang {
+                            mac: mac,
+                            attrs: item.attrs,
+                            ident: Some(item.ident),
+                            span: item.span,
+                        }).make_items()
                     }
+                    _ => unreachable!(),
+                })
+            }
+            ast::ItemKind::Mod(ast::Mod { inner, .. }) => {
+                let mut paths = (*self.cx.syntax_env.paths()).clone();
+                paths.mod_path.push(item.ident);
+
+                // Detect if this is an inline module (`mod m { ... }` as opposed to `mod m;`).
+                // In the non-inline case, `inner` is never the dummy span (c.f. `parse_item_mod`).
+                // Thus, if `inner` is the dummy span, we know the module is inline.
+                let inline_module = item.span.contains(inner) || inner == syntax_pos::DUMMY_SP;
+
+                if inline_module {
+                    paths.directory.push(&*{
+                        ::attr::first_attr_value_str_by_name(&item.attrs, "path")
+                            .unwrap_or(item.ident.name.as_str())
+                    });
                 } else {
-                    let at_crate_root = ::std::mem::replace(&mut self.at_crate_root, false);
-                    visit::walk_item(self, item);
-                    self.at_crate_root = at_crate_root;
+                    paths.directory =
+                        PathBuf::from(self.cx.parse_sess.codemap().span_to_filename(inner));
+                    paths.directory.pop();
                 }
-            }
-            fn visit_block(&mut self, block: &ast::Block) {
-                let at_crate_root = ::std::mem::replace(&mut self.at_crate_root, false);
-                visit::walk_block(self, block);
-                self.at_crate_root = at_crate_root;
-            }
-        }
 
-        node.visit_with(&mut MacroLoadingVisitor {
-            at_crate_root: self.cx.syntax_env.is_crate_root(),
-            cx: self.cx,
-        });
-    }
-}
-
-impl<'a, 'b> Folder for MacroExpander<'a, 'b> {
-    fn fold_crate(&mut self, c: Crate) -> Crate {
-        self.cx.filename = Some(self.cx.parse_sess.codemap().span_to_filename(c.span));
-        noop_fold_crate(c, self)
-    }
-
-    fn fold_expr(&mut self, expr: P<ast::Expr>) -> P<ast::Expr> {
-        expr.and_then(|expr| expand_expr(expr, self))
+                let macro_use = self.contains_macro_use(&item.attrs);
+                let in_block = self.cx.syntax_env.in_block();
+                let module = self.cx.syntax_env.add_module(macro_use, in_block, Rc::new(paths));
+                let module = mem::replace(&mut self.cx.syntax_env.current_module, module);
+                let result = noop_fold_item(item, self);
+                self.cx.syntax_env.current_module = module;
+                result
+            },
+            ast::ItemKind::ExternCrate(..) => {
+                // We need to error on `#[macro_use] extern crate` when it isn't at the
+                // crate root, because `$crate` won't work properly.
+                let is_crate_root = self.cx.syntax_env.is_crate_root();
+                for def in self.cx.loader.load_crate(&*item, is_crate_root) {
+                    match def {
+                        LoadedMacro::Def(def) => self.cx.insert_macro(def),
+                        LoadedMacro::CustomDerive(name, ext) => {
+                            self.cx.insert_custom_derive(&name, ext, item.span);
+                        }
+                    }
+                }
+                SmallVector::one(item)
+            },
+            _ => noop_fold_item(item, self),
+        }
     }
 
-    fn fold_opt_expr(&mut self, expr: P<ast::Expr>) -> Option<P<ast::Expr>> {
-        expr.and_then(|expr| match expr.node {
-            ast::ExprKind::Mac(mac) =>
-                expand_mac_invoc(mac, None, expr.attrs.into(), expr.span, self),
-            _ => Some(expand_expr(expr, self)),
-        })
-    }
+    fn fold_trait_item(&mut self, item: ast::TraitItem) -> SmallVector<ast::TraitItem> {
+        let item = configure!(self, item);
 
-    fn fold_pat(&mut self, pat: P<ast::Pat>) -> P<ast::Pat> {
-        expand_pat(pat, self)
-    }
+        let (item, attr) = self.classify_item(item);
+        if let Some(attr) = attr {
+            let item =
+                Annotatable::TraitItem(P(fully_configure!(self, item, noop_fold_trait_item)));
+            return self.collect_attr(attr, item, ExpansionKind::TraitItems).make_trait_items()
+        }
 
-    fn fold_item(&mut self, item: P<ast::Item>) -> SmallVector<P<ast::Item>> {
-        use std::mem::replace;
-        let result;
-        if let ast::ItemKind::Mod(ast::Mod { inner, .. }) = item.node {
-            if item.span.contains(inner) {
-                self.push_mod_path(item.ident, &item.attrs);
-                result = expand_item(item, self);
-                self.pop_mod_path();
-            } else {
-                let filename = if inner != syntax_pos::DUMMY_SP {
-                    Some(self.cx.parse_sess.codemap().span_to_filename(inner))
-                } else { None };
-                let orig_filename = replace(&mut self.cx.filename, filename);
-                let orig_mod_path_stack = replace(&mut self.cx.mod_path_stack, Vec::new());
-                result = expand_item(item, self);
-                self.cx.filename = orig_filename;
-                self.cx.mod_path_stack = orig_mod_path_stack;
+        match item.node {
+            ast::TraitItemKind::Macro(mac) => {
+                let ast::TraitItem { attrs, span, .. } = item;
+                self.collect_bang(mac, attrs, span, ExpansionKind::TraitItems).make_trait_items()
             }
-        } else {
-            result = expand_item(item, self);
+            _ => fold::noop_fold_trait_item(item, self),
         }
-        result
     }
 
-    fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVector<ast::Stmt> {
-        expand_stmt(stmt, self)
-    }
-
-    fn fold_block(&mut self, block: P<Block>) -> P<Block> {
-        let was_in_block = ::std::mem::replace(&mut self.cx.in_block, true);
-        let result = with_exts_frame!(self.cx.syntax_env, false, noop_fold_block(block, self));
-        self.cx.in_block = was_in_block;
-        result
-    }
+    fn fold_impl_item(&mut self, item: ast::ImplItem) -> SmallVector<ast::ImplItem> {
+        let item = configure!(self, item);
 
-    fn fold_trait_item(&mut self, i: ast::TraitItem) -> SmallVector<ast::TraitItem> {
-        expand_annotatable(Annotatable::TraitItem(P(i)), self)
-            .into_iter().map(|i| i.expect_trait_item()).collect()
-    }
+        let (item, attr) = self.classify_item(item);
+        if let Some(attr) = attr {
+            let item = Annotatable::ImplItem(P(fully_configure!(self, item, noop_fold_impl_item)));
+            return self.collect_attr(attr, item, ExpansionKind::ImplItems).make_impl_items();
+        }
 
-    fn fold_impl_item(&mut self, i: ast::ImplItem) -> SmallVector<ast::ImplItem> {
-        expand_annotatable(Annotatable::ImplItem(P(i)), self)
-            .into_iter().map(|i| i.expect_impl_item()).collect()
+        match item.node {
+            ast::ImplItemKind::Macro(mac) => {
+                let ast::ImplItem { attrs, span, .. } = item;
+                self.collect_bang(mac, attrs, span, ExpansionKind::ImplItems).make_impl_items()
+            }
+            _ => fold::noop_fold_impl_item(item, self),
+        }
     }
 
     fn fold_ty(&mut self, ty: P<ast::Ty>) -> P<ast::Ty> {
-        expand_type(ty, self)
+        let ty = match ty.node {
+            ast::TyKind::Mac(_) => ty.unwrap(),
+            _ => return fold::noop_fold_ty(ty, self),
+        };
+
+        match ty.node {
+            ast::TyKind::Mac(mac) =>
+                self.collect_bang(mac, Vec::new(), ty.span, ExpansionKind::Ty).make_ty(),
+            _ => unreachable!(),
+        }
     }
-}
 
-impl<'a, 'b> MacroExpander<'a, 'b> {
-    fn push_mod_path(&mut self, id: Ident, attrs: &[ast::Attribute]) {
-        let default_path = id.name.as_str();
-        let file_path = match ::attr::first_attr_value_str_by_name(attrs, "path") {
-            Some(d) => d,
-            None => default_path,
-        };
-        self.cx.mod_path_stack.push(file_path)
+    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 pop_mod_path(&mut self) {
-        self.cx.mod_path_stack.pop().unwrap();
+    fn fold_item_kind(&mut self, item: ast::ItemKind) -> ast::ItemKind {
+        noop_fold_item_kind(self.cfg.configure_item_kind(item), self)
     }
 }
 
@@ -699,42 +765,17 @@ impl<'feat> ExpansionConfig<'feat> {
 pub fn expand_crate(cx: &mut ExtCtxt,
                     user_exts: Vec<NamedSyntaxExtension>,
                     c: Crate) -> Crate {
-    let mut expander = MacroExpander::new(cx, false, false);
-    expand_crate_with_expander(&mut expander, user_exts, c)
+    cx.initialize(user_exts, &c);
+    cx.expander().expand_crate(c)
 }
 
 // Expands crate using supplied MacroExpander - allows for
 // non-standard expansion behaviour (e.g. step-wise).
 pub fn expand_crate_with_expander(expander: &mut MacroExpander,
                                   user_exts: Vec<NamedSyntaxExtension>,
-                                  mut c: Crate) -> Crate {
-    if std_inject::no_core(&c) {
-        expander.cx.crate_root = None;
-    } else if std_inject::no_std(&c) {
-        expander.cx.crate_root = Some("core");
-    } else {
-        expander.cx.crate_root = Some("std");
-    }
-
-    // User extensions must be added before expander.load_macros is called,
-    // so that macros from external crates shadow user defined extensions.
-    for (name, extension) in user_exts {
-        expander.cx.syntax_env.insert(name, extension);
-    }
-
-    let items = SmallVector::many(c.module.items);
-    expander.load_macros(&items);
-    c.module.items = items.into();
-
-    let err_count = expander.cx.parse_sess.span_diagnostic.err_count();
-    let mut ret = expander.fold_crate(c);
-    ret.exported_macros = expander.cx.exported_macros.clone();
-
-    if expander.cx.parse_sess.span_diagnostic.err_count() > err_count {
-        expander.cx.parse_sess.span_diagnostic.abort_if_errors();
-    }
-
-    ret
+                                  c: Crate) -> Crate {
+    expander.cx.initialize(user_exts, &c);
+    expander.expand_crate(c)
 }
 
 // A Marker adds the given mark to the syntax context and
diff --git a/src/libsyntax/ext/hygiene.rs b/src/libsyntax/ext/hygiene.rs
index ade165e0ef9..27e8eab62e1 100644
--- a/src/libsyntax/ext/hygiene.rs
+++ b/src/libsyntax/ext/hygiene.rs
@@ -40,6 +40,10 @@ impl Mark {
             ::std::mem::replace(&mut data.next_mark, next_mark)
         })
     }
+
+    pub fn as_u32(&self) -> u32 {
+        self.0
+    }
 }
 
 struct HygieneData {
diff --git a/src/libsyntax/ext/placeholders.rs b/src/libsyntax/ext/placeholders.rs
new file mode 100644
index 00000000000..abadcf867b1
--- /dev/null
+++ b/src/libsyntax/ext/placeholders.rs
@@ -0,0 +1,175 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use ast;
+use codemap::{DUMMY_SP, dummy_spanned};
+use ext::expand::{Expansion, ExpansionKind};
+use fold::*;
+use parse::token::keywords;
+use ptr::P;
+use util::small_vector::SmallVector;
+
+use std::collections::HashMap;
+
+pub fn placeholder(kind: ExpansionKind, id: ast::NodeId) -> Expansion {
+    fn mac_placeholder() -> ast::Mac {
+        dummy_spanned(ast::Mac_ {
+            path: ast::Path { span: DUMMY_SP, global: false, segments: Vec::new() },
+            tts: Vec::new(),
+        })
+    }
+
+    let ident = keywords::Invalid.ident();
+    let attrs = Vec::new();
+    let vis = ast::Visibility::Inherited;
+    let span = DUMMY_SP;
+    let expr_placeholder = || P(ast::Expr {
+        id: id, span: span,
+        attrs: ast::ThinVec::new(),
+        node: ast::ExprKind::Mac(mac_placeholder()),
+    });
+
+    match kind {
+        ExpansionKind::Expr => Expansion::Expr(expr_placeholder()),
+        ExpansionKind::OptExpr => Expansion::OptExpr(Some(expr_placeholder())),
+        ExpansionKind::Items => Expansion::Items(SmallVector::one(P(ast::Item {
+            id: id, span: span, ident: ident, vis: vis, attrs: attrs,
+            node: ast::ItemKind::Mac(mac_placeholder()),
+        }))),
+        ExpansionKind::TraitItems => Expansion::TraitItems(SmallVector::one(ast::TraitItem {
+            id: id, span: span, ident: ident, attrs: attrs,
+            node: ast::TraitItemKind::Macro(mac_placeholder()),
+        })),
+        ExpansionKind::ImplItems => Expansion::ImplItems(SmallVector::one(ast::ImplItem {
+            id: id, span: span, ident: ident, vis: vis, attrs: attrs,
+            node: ast::ImplItemKind::Macro(mac_placeholder()),
+            defaultness: ast::Defaultness::Final,
+        })),
+        ExpansionKind::Pat => Expansion::Pat(P(ast::Pat {
+            id: id, span: span, node: ast::PatKind::Mac(mac_placeholder()),
+        })),
+        ExpansionKind::Ty => Expansion::Ty(P(ast::Ty {
+            id: id, span: span, node: ast::TyKind::Mac(mac_placeholder()),
+        })),
+        ExpansionKind::Stmts => Expansion::Stmts(SmallVector::one({
+            let mac = P((mac_placeholder(), ast::MacStmtStyle::Braces, ast::ThinVec::new()));
+            ast::Stmt { id: id, span: span, node: ast::StmtKind::Mac(mac) }
+        })),
+    }
+}
+
+pub fn macro_scope_placeholder() -> Expansion {
+    placeholder(ExpansionKind::Items, ast::DUMMY_NODE_ID)
+}
+
+pub struct PlaceholderExpander {
+    expansions: HashMap<ast::NodeId, Expansion>,
+}
+
+impl PlaceholderExpander {
+    pub fn new() -> Self {
+        PlaceholderExpander {
+            expansions: HashMap::new(),
+        }
+    }
+
+    pub fn add(&mut self, id: ast::NodeId, expansion: Expansion) {
+        self.expansions.insert(id, expansion);
+    }
+
+    pub fn remove(&mut self, id: ast::NodeId) -> Expansion {
+        self.expansions.remove(&id).unwrap()
+    }
+}
+
+impl Folder for PlaceholderExpander {
+    fn fold_item(&mut self, item: P<ast::Item>) -> SmallVector<P<ast::Item>> {
+        match item.node {
+            // Scope placeholder
+            ast::ItemKind::Mac(_) if item.id == ast::DUMMY_NODE_ID => SmallVector::one(item),
+            ast::ItemKind::Mac(_) => self.remove(item.id).make_items(),
+            _ => noop_fold_item(item, self),
+        }
+    }
+
+    fn fold_trait_item(&mut self, item: ast::TraitItem) -> SmallVector<ast::TraitItem> {
+        match item.node {
+            ast::TraitItemKind::Macro(_) => self.remove(item.id).make_trait_items(),
+            _ => noop_fold_trait_item(item, self),
+        }
+    }
+
+    fn fold_impl_item(&mut self, item: ast::ImplItem) -> SmallVector<ast::ImplItem> {
+        match item.node {
+            ast::ImplItemKind::Macro(_) => self.remove(item.id).make_impl_items(),
+            _ => noop_fold_impl_item(item, self),
+        }
+    }
+
+    fn fold_expr(&mut self, expr: P<ast::Expr>) -> P<ast::Expr> {
+        match expr.node {
+            ast::ExprKind::Mac(_) => self.remove(expr.id).make_expr(),
+            _ => expr.map(|expr| noop_fold_expr(expr, self)),
+        }
+    }
+
+    fn fold_opt_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),
+        }
+    }
+
+    fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVector<ast::Stmt> {
+        let (style, mut expansion) = match stmt.node {
+            ast::StmtKind::Mac(mac) => (mac.1, self.remove(stmt.id).make_stmts()),
+            _ => return noop_fold_stmt(stmt, self),
+        };
+
+        if style == ast::MacStmtStyle::Semicolon {
+            if let Some(stmt) = expansion.pop() {
+                expansion.push(stmt.add_trailing_semicolon());
+            }
+        }
+
+        expansion
+    }
+
+    fn fold_pat(&mut self, pat: P<ast::Pat>) -> P<ast::Pat> {
+        match pat.node {
+            ast::PatKind::Mac(_) => self.remove(pat.id).make_pat(),
+            _ => noop_fold_pat(pat, self),
+        }
+    }
+
+    fn fold_ty(&mut self, ty: P<ast::Ty>) -> P<ast::Ty> {
+        match ty.node {
+            ast::TyKind::Mac(_) => self.remove(ty.id).make_ty(),
+            _ => noop_fold_ty(ty, self),
+        }
+    }
+}
+
+pub fn reconstructed_macro_rules(def: &ast::MacroDef, path: &ast::Path) -> Expansion {
+    Expansion::Items(SmallVector::one(P(ast::Item {
+        ident: def.ident,
+        attrs: def.attrs.clone(),
+        id: ast::DUMMY_NODE_ID,
+        node: ast::ItemKind::Mac(ast::Mac {
+            span: def.span,
+            node: ast::Mac_ {
+                path: path.clone(),
+                tts: def.body.clone(),
+            }
+        }),
+        vis: ast::Visibility::Inherited,
+        span: def.span,
+    })))
+}
diff --git a/src/libsyntax/ext/source_util.rs b/src/libsyntax/ext/source_util.rs
index 97cb09991ec..105b2261117 100644
--- a/src/libsyntax/ext/source_util.rs
+++ b/src/libsyntax/ext/source_util.rs
@@ -74,11 +74,9 @@ pub fn expand_stringify(cx: &mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTre
 pub fn expand_mod(cx: &mut ExtCtxt, sp: Span, tts: &[tokenstream::TokenTree])
                   -> Box<base::MacResult+'static> {
     base::check_zero_tts(cx, sp, tts, "module_path!");
-    let string = cx.mod_path()
-                   .iter()
-                   .map(|x| x.to_string())
-                   .collect::<Vec<String>>()
-                   .join("::");
+    let paths = cx.syntax_env.paths();
+    let string = paths.mod_path.iter().map(|x| x.to_string()).collect::<Vec<String>>().join("::");
+
     base::MacEager::expr(cx.expr_str(
             sp,
             token::intern_and_get_ident(&string[..])))
diff --git a/src/libsyntax/ext/tt/macro_rules.rs b/src/libsyntax/ext/tt/macro_rules.rs
index d197741e9a3..ed80ec9cbc4 100644
--- a/src/libsyntax/ext/tt/macro_rules.rs
+++ b/src/libsyntax/ext/tt/macro_rules.rs
@@ -211,9 +211,8 @@ fn generic_extension<'cx>(cx: &'cx ExtCtxt,
                                            imported_from,
                                            rhs);
                 let mut p = Parser::new(cx.parse_sess(), cx.cfg(), Box::new(trncbr));
-                p.filename = cx.filename.clone();
-                p.mod_path_stack = cx.mod_path_stack.clone();
-                p.restrictions = match cx.in_block {
+                p.directory = cx.syntax_env.paths().directory.clone();
+                p.restrictions = match cx.syntax_env.in_block() {
                     true => Restrictions::NO_NONINLINE_MOD,
                     false => Restrictions::empty(),
                 };
diff --git a/src/libsyntax/lib.rs b/src/libsyntax/lib.rs
index 65bc9f34c90..4a2c9aff2d2 100644
--- a/src/libsyntax/lib.rs
+++ b/src/libsyntax/lib.rs
@@ -104,6 +104,7 @@ pub mod abi;
 pub mod ast;
 pub mod attr;
 pub mod codemap;
+#[macro_use]
 pub mod config;
 pub mod entry;
 pub mod feature_gate;
@@ -126,6 +127,7 @@ pub mod ext {
     pub mod base;
     pub mod build;
     pub mod expand;
+    pub mod placeholders;
     pub mod hygiene;
     pub mod proc_macro_shim;
     pub mod quote;
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index ec9dc1bae5a..6a0e40edded 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -264,8 +264,7 @@ pub struct Parser<'a> {
     /// extra detail when the same error is seen twice
     pub obsolete_set: HashSet<ObsoleteSyntax>,
     /// Used to determine the path to externally loaded source files
-    pub filename: Option<String>,
-    pub mod_path_stack: Vec<InternedString>,
+    pub directory: PathBuf,
     /// Stack of open delimiters and their spans. Used for error message.
     pub open_braces: Vec<(token::DelimToken, Span)>,
     /// Flag if this parser "owns" the directory that it is currently parsing
@@ -346,9 +345,11 @@ impl<'a> Parser<'a> {
     {
         let tok0 = rdr.real_token();
         let span = tok0.sp;
-        let filename = if span != syntax_pos::DUMMY_SP {
-            Some(sess.codemap().span_to_filename(span))
-        } else { None };
+        let mut directory = match span {
+            syntax_pos::DUMMY_SP => PathBuf::new(),
+            _ => PathBuf::from(sess.codemap().span_to_filename(span)),
+        };
+        directory.pop();
         let placeholder = TokenAndSpan {
             tok: token::Underscore,
             sp: span,
@@ -377,8 +378,7 @@ impl<'a> Parser<'a> {
             quote_depth: 0,
             parsing_token_tree: false,
             obsolete_set: HashSet::new(),
-            mod_path_stack: Vec::new(),
-            filename: filename,
+            directory: directory,
             open_braces: Vec::new(),
             owns_directory: true,
             root_module_name: None,
@@ -5306,27 +5306,24 @@ impl<'a> Parser<'a> {
             let (m, attrs) = self.eval_src_mod(id, &outer_attrs, id_span)?;
             Ok((id, m, Some(attrs)))
         } else {
-            self.push_mod_path(id, &outer_attrs);
+            let directory = self.directory.clone();
+            self.push_directory(id, &outer_attrs);
             self.expect(&token::OpenDelim(token::Brace))?;
             let mod_inner_lo = self.span.lo;
             let attrs = self.parse_inner_attributes()?;
             let m = self.parse_mod_items(&token::CloseDelim(token::Brace), mod_inner_lo)?;
-            self.pop_mod_path();
+            self.directory = directory;
             Ok((id, ItemKind::Mod(m), Some(attrs)))
         }
     }
 
-    fn push_mod_path(&mut self, id: Ident, attrs: &[Attribute]) {
+    fn push_directory(&mut self, id: Ident, attrs: &[Attribute]) {
         let default_path = self.id_to_interned_str(id);
         let file_path = match ::attr::first_attr_value_str_by_name(attrs, "path") {
             Some(d) => d,
             None => default_path,
         };
-        self.mod_path_stack.push(file_path)
-    }
-
-    fn pop_mod_path(&mut self) {
-        self.mod_path_stack.pop().unwrap();
+        self.directory.push(&*file_path)
     }
 
     pub fn submod_path_from_attr(attrs: &[ast::Attribute], dir_path: &Path) -> Option<PathBuf> {
@@ -5374,18 +5371,11 @@ impl<'a> Parser<'a> {
                    id: ast::Ident,
                    outer_attrs: &[ast::Attribute],
                    id_sp: Span) -> PResult<'a, ModulePathSuccess> {
-        let mut prefix = PathBuf::from(self.filename.as_ref().unwrap());
-        prefix.pop();
-        let mut dir_path = prefix;
-        for part in &self.mod_path_stack {
-            dir_path.push(&**part);
-        }
-
-        if let Some(p) = Parser::submod_path_from_attr(outer_attrs, &dir_path) {
+        if let Some(p) = Parser::submod_path_from_attr(outer_attrs, &self.directory) {
             return Ok(ModulePathSuccess { path: p, owns_directory: true });
         }
 
-        let paths = Parser::default_submod_path(id, &dir_path, self.sess.codemap());
+        let paths = Parser::default_submod_path(id, &self.directory, self.sess.codemap());
 
         if self.restrictions.contains(Restrictions::NO_NONINLINE_MOD) {
             let msg =
@@ -5400,8 +5390,8 @@ impl<'a> Parser<'a> {
         } else if !self.owns_directory {
             let mut err = self.diagnostic().struct_span_err(id_sp,
                 "cannot declare a new module at this location");
-            let this_module = match self.mod_path_stack.last() {
-                Some(name) => name.to_string(),
+            let this_module = match self.directory.file_name() {
+                Some(file_name) => file_name.to_str().unwrap().to_owned(),
                 None => self.root_module_name.as_ref().unwrap().clone(),
             };
             err.span_note(id_sp,
diff --git a/src/libsyntax/test.rs b/src/libsyntax/test.rs
index 6155ad729a2..3108296e778 100644
--- a/src/libsyntax/test.rs
+++ b/src/libsyntax/test.rs
@@ -300,14 +300,11 @@ fn generate_test_harness(sess: &ParseSess,
         }
     });
 
-    let mut fold = TestHarnessGenerator {
+    TestHarnessGenerator {
         cx: cx,
         tests: Vec::new(),
         tested_submods: Vec::new(),
-    };
-    let res = fold.fold_crate(krate);
-    fold.cx.ext_cx.bt_pop();
-    return res;
+    }.fold_crate(krate)
 }
 
 /// Craft a span that will be ignored by the stability lint's
diff --git a/src/libsyntax/util/small_vector.rs b/src/libsyntax/util/small_vector.rs
index 893646f121f..373dfc4ddfa 100644
--- a/src/libsyntax/util/small_vector.rs
+++ b/src/libsyntax/util/small_vector.rs
@@ -29,6 +29,12 @@ enum SmallVectorRepr<T> {
     Many(Vec<T>),
 }
 
+impl<T> Default for SmallVector<T> {
+    fn default() -> Self {
+        SmallVector { repr: Zero }
+    }
+}
+
 impl<T> Into<Vec<T>> for SmallVector<T> {
     fn into(self) -> Vec<T> {
         match self.repr {