auto merge of #9088 : nikomatsakis/rust/issue-6304-AST-tree-not-DAG, r=catamorphism

Ensures that each AST node has a unique id. Fixes numerous bugs in macro expansion and deriving. Add two
representative tests.

Fixes #7971
Fixes #6304
Fixes #8367
Fixes #8754
Fixes #8852
Fixes #2543
Fixes #7654

9 files changed, 40 insertions, 67 deletions

diff --git a/src/libsyntax/ext/asm.rs b/src/libsyntax/ext/asm.rs
index 3937cd8e416..b350ef7bb08 100644
--- a/src/libsyntax/ext/asm.rs
+++ b/src/libsyntax/ext/asm.rs
@@ -76,7 +76,7 @@ pub fn expand_asm(cx: @ExtCtxt, sp: Span, tts: &[ast::token_tree])
                     p.expect(&token::RPAREN);
 
                     let out = @ast::Expr {
-                        id: cx.next_id(),
+                        id: ast::DUMMY_NODE_ID,
                         span: out.span,
                         node: ast::ExprAddrOf(ast::MutMutable, out)
                     };
@@ -172,7 +172,7 @@ pub fn expand_asm(cx: @ExtCtxt, sp: Span, tts: &[ast::token_tree])
     }
 
     MRExpr(@ast::Expr {
-        id: cx.next_id(),
+        id: ast::DUMMY_NODE_ID,
         node: ast::ExprInlineAsm(ast::inline_asm {
             asm: asm,
             clobbers: cons.to_managed(),
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 3d5d62aeadf..48a13646686 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -319,9 +319,6 @@ impl ExtCtxt {
         self.print_backtrace();
         self.parse_sess.span_diagnostic.handler().bug(msg);
     }
-    pub fn next_id(&self) -> ast::NodeId {
-        parse::next_node_id(self.parse_sess)
-    }
     pub fn trace_macros(&self) -> bool {
         *self.trace_mac
     }
diff --git a/src/libsyntax/ext/build.rs b/src/libsyntax/ext/build.rs
index 339583ed426..6cb5a93a313 100644
--- a/src/libsyntax/ext/build.rs
+++ b/src/libsyntax/ext/build.rs
@@ -13,7 +13,6 @@ use ast::Ident;
 use ast;
 use ast_util;
 use codemap::{Span, respan, dummy_sp};
-use fold;
 use ext::base::ExtCtxt;
 use ext::quote::rt::*;
 use opt_vec;
@@ -277,7 +276,7 @@ impl AstBuilder for @ExtCtxt {
 
     fn ty(&self, span: Span, ty: ast::ty_) -> ast::Ty {
         ast::Ty {
-            id: self.next_id(),
+            id: ast::DUMMY_NODE_ID,
             span: span,
             node: ty
         }
@@ -286,7 +285,7 @@ impl AstBuilder for @ExtCtxt {
     fn ty_path(&self, path: ast::Path, bounds: Option<OptVec<ast::TyParamBound>>)
               -> ast::Ty {
         self.ty(path.span,
-                ast::ty_path(path, bounds, self.next_id()))
+                ast::ty_path(path, bounds, ast::DUMMY_NODE_ID))
     }
 
     // Might need to take bounds as an argument in the future, if you ever want
@@ -340,14 +339,14 @@ impl AstBuilder for @ExtCtxt {
 
     fn ty_nil(&self) -> ast::Ty {
         ast::Ty {
-            id: self.next_id(),
+            id: ast::DUMMY_NODE_ID,
             node: ast::ty_nil,
             span: dummy_sp(),
         }
     }
 
     fn typaram(&self, id: ast::Ident, bounds: OptVec<ast::TyParamBound>) -> ast::TyParam {
-        ast::TyParam { ident: id, id: self.next_id(), bounds: bounds }
+        ast::TyParam { ident: id, id: ast::DUMMY_NODE_ID, bounds: bounds }
     }
 
     // these are strange, and probably shouldn't be used outside of
@@ -377,7 +376,7 @@ impl AstBuilder for @ExtCtxt {
     fn trait_ref(&self, path: ast::Path) -> ast::trait_ref {
         ast::trait_ref {
             path: path,
-            ref_id: self.next_id()
+            ref_id: ast::DUMMY_NODE_ID
         }
     }
 
@@ -386,11 +385,11 @@ impl AstBuilder for @ExtCtxt {
     }
 
     fn lifetime(&self, span: Span, ident: ast::Ident) -> ast::Lifetime {
-        ast::Lifetime { id: self.next_id(), span: span, ident: ident }
+        ast::Lifetime { id: ast::DUMMY_NODE_ID, span: span, ident: ident }
     }
 
     fn stmt_expr(&self, expr: @ast::Expr) -> @ast::Stmt {
-        @respan(expr.span, ast::StmtSemi(expr, self.next_id()))
+        @respan(expr.span, ast::StmtSemi(expr, ast::DUMMY_NODE_ID))
     }
 
     fn stmt_let(&self, sp: Span, mutbl: bool, ident: ast::Ident, ex: @ast::Expr) -> @ast::Stmt {
@@ -400,11 +399,11 @@ impl AstBuilder for @ExtCtxt {
             ty: self.ty_infer(sp),
             pat: pat,
             init: Some(ex),
-            id: self.next_id(),
+            id: ast::DUMMY_NODE_ID,
             span: sp,
         };
         let decl = respan(sp, ast::DeclLocal(local));
-        @respan(sp, ast::StmtDecl(@decl, self.next_id()))
+        @respan(sp, ast::StmtDecl(@decl, ast::DUMMY_NODE_ID))
     }
 
     fn stmt_let_typed(&self,
@@ -420,11 +419,11 @@ impl AstBuilder for @ExtCtxt {
             ty: typ,
             pat: pat,
             init: Some(ex),
-            id: self.next_id(),
+            id: ast::DUMMY_NODE_ID,
             span: sp,
         };
         let decl = respan(sp, ast::DeclLocal(local));
-        @respan(sp, ast::StmtDecl(@decl, self.next_id()))
+        @respan(sp, ast::StmtDecl(@decl, ast::DUMMY_NODE_ID))
     }
 
     fn block(&self, span: Span, stmts: ~[@ast::Stmt], expr: Option<@Expr>) -> ast::Block {
@@ -443,7 +442,7 @@ impl AstBuilder for @ExtCtxt {
                view_items: view_items,
                stmts: stmts,
                expr: expr,
-               id: self.next_id(),
+               id: ast::DUMMY_NODE_ID,
                rules: ast::DefaultBlock,
                span: span,
            }
@@ -451,7 +450,7 @@ impl AstBuilder for @ExtCtxt {
 
     fn expr(&self, span: Span, node: ast::Expr_) -> @ast::Expr {
         @ast::Expr {
-            id: self.next_id(),
+            id: ast::DUMMY_NODE_ID,
             node: node,
             span: span,
         }
@@ -470,7 +469,7 @@ impl AstBuilder for @ExtCtxt {
 
     fn expr_binary(&self, sp: Span, op: ast::BinOp,
                    lhs: @ast::Expr, rhs: @ast::Expr) -> @ast::Expr {
-        self.expr(sp, ast::ExprBinary(self.next_id(), op, lhs, rhs))
+        self.expr(sp, ast::ExprBinary(ast::DUMMY_NODE_ID, op, lhs, rhs))
     }
 
     fn expr_deref(&self, sp: Span, e: @ast::Expr) -> @ast::Expr {
@@ -478,7 +477,7 @@ impl AstBuilder for @ExtCtxt {
     }
     fn expr_unary(&self, sp: Span, op: ast::UnOp, e: @ast::Expr)
         -> @ast::Expr {
-        self.expr(sp, ast::ExprUnary(self.next_id(), op, e))
+        self.expr(sp, ast::ExprUnary(ast::DUMMY_NODE_ID, op, e))
     }
 
     fn expr_managed(&self, sp: Span, e: @ast::Expr) -> @ast::Expr {
@@ -512,7 +511,7 @@ impl AstBuilder for @ExtCtxt {
                         ident: ast::Ident,
                         args: ~[@ast::Expr]) -> @ast::Expr {
         self.expr(span,
-                  ast::ExprMethodCall(self.next_id(), expr, ident, ~[], args, ast::NoSugar))
+                  ast::ExprMethodCall(ast::DUMMY_NODE_ID, expr, ident, ~[], args, ast::NoSugar))
     }
     fn expr_block(&self, b: ast::Block) -> @ast::Expr {
         self.expr(b.span, ast::ExprBlock(b))
@@ -583,7 +582,7 @@ impl AstBuilder for @ExtCtxt {
 
 
     fn pat(&self, span: Span, pat: ast::Pat_) -> @ast::Pat {
-        @ast::Pat { id: self.next_id(), node: pat, span: span }
+        @ast::Pat { id: ast::DUMMY_NODE_ID, node: pat, span: span }
     }
     fn pat_wild(&self, span: Span) -> @ast::Pat {
         self.pat(span, ast::PatWild)
@@ -695,7 +694,7 @@ impl AstBuilder for @ExtCtxt {
             is_mutbl: false,
             ty: ty,
             pat: arg_pat,
-            id: self.next_id()
+            id: ast::DUMMY_NODE_ID
         }
     }
 
@@ -714,7 +713,7 @@ impl AstBuilder for @ExtCtxt {
         // Rust coding conventions
         @ast::item { ident: name,
                     attrs: attrs,
-                    id: self.next_id(),
+                    id: ast::DUMMY_NODE_ID,
                     node: node,
                     vis: ast::public,
                     span: span }
@@ -755,7 +754,7 @@ impl AstBuilder for @ExtCtxt {
 
     fn variant(&self, span: Span, name: Ident, tys: ~[ast::Ty]) -> ast::variant {
         let args = tys.move_iter().map(|ty| {
-            ast::variant_arg { ty: ty, id: self.next_id() }
+            ast::variant_arg { ty: ty, id: ast::DUMMY_NODE_ID }
         }).collect();
 
         respan(span,
@@ -763,7 +762,7 @@ impl AstBuilder for @ExtCtxt {
                    name: name,
                    attrs: ~[],
                    kind: ast::tuple_variant_kind(args),
-                   id: self.next_id(),
+                   id: ast::DUMMY_NODE_ID,
                    disr_expr: None,
                    vis: ast::public
                })
@@ -860,43 +859,20 @@ impl AstBuilder for @ExtCtxt {
     fn view_use_list(&self, sp: Span, vis: ast::visibility,
                      path: ~[ast::Ident], imports: &[ast::Ident]) -> ast::view_item {
         let imports = do imports.map |id| {
-            respan(sp, ast::path_list_ident_ { name: *id, id: self.next_id() })
+            respan(sp, ast::path_list_ident_ { name: *id, id: ast::DUMMY_NODE_ID })
         };
 
         self.view_use(sp, vis,
                       ~[@respan(sp,
                                 ast::view_path_list(self.path(sp, path),
                                                     imports,
-                                                    self.next_id()))])
+                                                    ast::DUMMY_NODE_ID))])
     }
 
     fn view_use_glob(&self, sp: Span,
                      vis: ast::visibility, path: ~[ast::Ident]) -> ast::view_item {
         self.view_use(sp, vis,
                       ~[@respan(sp,
-                                ast::view_path_glob(self.path(sp, path), self.next_id()))])
-    }
-}
-
-
-pub trait Duplicate {
-    //
-    // Duplication functions
-    //
-    // These functions just duplicate AST nodes.
-    //
-
-    fn duplicate(&self, cx: @ExtCtxt) -> Self;
-}
-
-impl Duplicate for @ast::Expr {
-    fn duplicate(&self, cx: @ExtCtxt) -> @ast::Expr {
-        let folder = fold::default_ast_fold();
-        let folder = @fold::AstFoldFns {
-            new_id: |_| cx.next_id(),
-            ..*folder
-        };
-        let folder = fold::make_fold(folder);
-        folder.fold_expr(*self)
+                                ast::view_path_glob(self.path(sp, path), ast::DUMMY_NODE_ID))])
     }
 }
diff --git a/src/libsyntax/ext/concat_idents.rs b/src/libsyntax/ext/concat_idents.rs
index 16e54093a14..0ca18f1208d 100644
--- a/src/libsyntax/ext/concat_idents.rs
+++ b/src/libsyntax/ext/concat_idents.rs
@@ -35,7 +35,7 @@ pub fn expand_syntax_ext(cx: @ExtCtxt, sp: Span, tts: &[ast::token_tree])
     let res = str_to_ident(res_str);
 
     let e = @ast::Expr {
-        id: cx.next_id(),
+        id: ast::DUMMY_NODE_ID,
         node: ast::ExprPath(
             ast::Path {
                  span: sp,
diff --git a/src/libsyntax/ext/deriving/generic.rs b/src/libsyntax/ext/deriving/generic.rs
index 8221be1bbcb..9222d8160ee 100644
--- a/src/libsyntax/ext/deriving/generic.rs
+++ b/src/libsyntax/ext/deriving/generic.rs
@@ -539,9 +539,9 @@ impl<'self> MethodDef<'self> {
             purity: ast::impure_fn,
             decl: fn_decl,
             body: body_block,
-            id: cx.next_id(),
+            id: ast::DUMMY_NODE_ID,
             span: span,
-            self_id: cx.next_id(),
+            self_id: ast::DUMMY_NODE_ID,
             vis: ast::inherited,
         }
     }
diff --git a/src/libsyntax/ext/deriving/rand.rs b/src/libsyntax/ext/deriving/rand.rs
index 8afd99e80af..56f92246d8f 100644
--- a/src/libsyntax/ext/deriving/rand.rs
+++ b/src/libsyntax/ext/deriving/rand.rs
@@ -12,7 +12,7 @@ use ast;
 use ast::{MetaItem, item, Expr, Ident};
 use codemap::Span;
 use ext::base::ExtCtxt;
-use ext::build::{AstBuilder, Duplicate};
+use ext::build::{AstBuilder};
 use ext::deriving::generic::*;
 
 use std::vec;
@@ -62,7 +62,7 @@ fn rand_substructure(cx: @ExtCtxt, span: Span, substr: &Substructure) -> @Expr {
     let rand_call = || {
         cx.expr_call_global(span,
                             rand_ident.clone(),
-                            ~[ rng[0].duplicate(cx) ])
+                            ~[ rng[0] ])
     };
 
     return match *substr.fields {
@@ -86,7 +86,7 @@ fn rand_substructure(cx: @ExtCtxt, span: Span, substr: &Substructure) -> @Expr {
             // ::std::rand::Rand::rand(rng)
             let rv_call = cx.expr_call(span,
                                        rand_name,
-                                       ~[ rng[0].duplicate(cx) ]);
+                                       ~[ rng[0] ]);
 
             // need to specify the uint-ness of the random number
             let uint_ty = cx.ty_ident(span, cx.ident_of("uint"));
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index 50a14c0fd71..80fd7971efd 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -406,8 +406,8 @@ pub fn expand_stmt(extsbox: @mut SyntaxEnv,
             let marked_ctxt = new_mark(fm,ctxt);
             let expanded = match expandfun(cx, mac.span, marked_tts, marked_ctxt) {
                 MRExpr(e) =>
-                    @codemap::Spanned { node: StmtExpr(e, cx.next_id()),
-                                    span: e.span},
+                    @codemap::Spanned { node: StmtExpr(e, ast::DUMMY_NODE_ID),
+                                        span: e.span},
                 MRAny(_,_,stmt_mkr) => stmt_mkr(),
                 _ => cx.span_fatal(
                     pth.span,
@@ -1365,8 +1365,8 @@ pub fn fun_to_ctxt_folder<T : 'static + CtxtFn>(cf: @T) -> @AstFoldFns {
         match *m {
             mac_invoc_tt(ref path, ref tts, ctxt) =>
             (mac_invoc_tt(fld.fold_path(path),
-                         fold_tts(*tts,fld),
-                         cf.f(ctxt)),
+                          fold_tts(*tts,fld),
+                          cf.f(ctxt)),
             sp)
         }
 
diff --git a/src/libsyntax/ext/ifmt.rs b/src/libsyntax/ext/ifmt.rs
index b63b829a392..b7722ffc297 100644
--- a/src/libsyntax/ext/ifmt.rs
+++ b/src/libsyntax/ext/ifmt.rs
@@ -550,7 +550,7 @@ impl Context {
         for &method in self.method_statics.iter() {
             let decl = respan(self.fmtsp, ast::DeclItem(method));
             lets.push(@respan(self.fmtsp,
-                              ast::StmtDecl(@decl, self.ecx.next_id())));
+                              ast::StmtDecl(@decl, ast::DUMMY_NODE_ID)));
         }
 
         // Next, build up the static array which will become our precompiled
@@ -581,7 +581,7 @@ impl Context {
         let unnamed = self.ecx.attribute(self.fmtsp, unnamed);
         let item = self.ecx.item(self.fmtsp, static_name, ~[unnamed], st);
         let decl = respan(self.fmtsp, ast::DeclItem(item));
-        lets.push(@respan(self.fmtsp, ast::StmtDecl(@decl, self.ecx.next_id())));
+        lets.push(@respan(self.fmtsp, ast::StmtDecl(@decl, ast::DUMMY_NODE_ID)));
 
         // Right now there is a bug such that for the expression:
         //      foo(bar(&1))
@@ -631,7 +631,7 @@ impl Context {
            view_items: ~[],
            stmts: ~[],
            expr: Some(result),
-           id: self.ecx.next_id(),
+           id: ast::DUMMY_NODE_ID,
            rules: ast::UnsafeBlock,
            span: self.fmtsp,
         });
diff --git a/src/libsyntax/ext/log_syntax.rs b/src/libsyntax/ext/log_syntax.rs
index adc246ab89a..52807009073 100644
--- a/src/libsyntax/ext/log_syntax.rs
+++ b/src/libsyntax/ext/log_syntax.rs
@@ -30,7 +30,7 @@ pub fn expand_syntax_ext(cx: @ExtCtxt,
 
     //trivial expression
     MRExpr(@ast::Expr {
-        id: cx.next_id(),
+        id: ast::DUMMY_NODE_ID,
         node: ast::ExprLit(@codemap::Spanned {
             node: ast::lit_nil,
             span: sp