syntax: use an index in CodeMap instead of Gc for ExpnInfo.

9 files changed, 123 insertions, 113 deletions

diff --git a/src/libsyntax/codemap.rs b/src/libsyntax/codemap.rs
index 2f30108c27b..7fe044b0fc8 100644
--- a/src/libsyntax/codemap.rs
+++ b/src/libsyntax/codemap.rs
@@ -25,7 +25,6 @@ source code snippets, etc.
 
 use serialize::{Encodable, Decodable, Encoder, Decoder};
 use std::cell::RefCell;
-use std::gc::Gc;
 use std::rc::Rc;
 
 pub trait Pos {
@@ -93,10 +92,10 @@ pub struct Span {
     pub hi: BytePos,
     /// Information about where the macro came from, if this piece of
     /// code was created by a macro expansion.
-    pub expn_info: Option<Gc<ExpnInfo>>
+    pub expn_id: ExpnId
 }
 
-pub static DUMMY_SP: Span = Span { lo: BytePos(0), hi: BytePos(0), expn_info: None };
+pub static DUMMY_SP: Span = Span { lo: BytePos(0), hi: BytePos(0), expn_id: NO_EXPANSION };
 
 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash, Show)]
 pub struct Spanned<T> {
@@ -140,17 +139,19 @@ pub fn dummy_spanned<T>(t: T) -> Spanned<T> {
 
 /* assuming that we're not in macro expansion */
 pub fn mk_sp(lo: BytePos, hi: BytePos) -> Span {
-    Span {lo: lo, hi: hi, expn_info: None}
+    Span {lo: lo, hi: hi, expn_id: NO_EXPANSION}
 }
 
 /// Return the span itself if it doesn't come from a macro expansion,
 /// otherwise return the call site span up to the `enclosing_sp` by
 /// following the `expn_info` chain.
-pub fn original_sp(sp: Span, enclosing_sp: Span) -> Span {
-    match (sp.expn_info, enclosing_sp.expn_info) {
+pub fn original_sp(cm: &CodeMap, sp: Span, enclosing_sp: Span) -> Span {
+    let call_site1 = cm.with_expn_info(sp.expn_id, |ei| ei.map(|ei| ei.call_site));
+    let call_site2 = cm.with_expn_info(enclosing_sp.expn_id, |ei| ei.map(|ei| ei.call_site));
+    match (call_site1, call_site2) {
         (None, _) => sp,
-        (Some(expn1), Some(expn2)) if expn1.call_site == expn2.call_site => sp,
-        (Some(expn1), _) => original_sp(expn1.call_site, enclosing_sp),
+        (Some(call_site1), Some(call_site2)) if call_site1 == call_site2 => sp,
+        (Some(call_site1), _) => original_sp(cm, call_site1, enclosing_sp),
     }
 }
 
@@ -222,6 +223,11 @@ pub struct ExpnInfo {
     pub callee: NameAndSpan
 }
 
+#[deriving(PartialEq, Eq, Clone, Show, Hash)]
+pub struct ExpnId(u32);
+
+pub static NO_EXPANSION: ExpnId = ExpnId(-1);
+
 pub type FileName = String;
 
 pub struct FileLines {
@@ -299,13 +305,15 @@ impl FileMap {
 }
 
 pub struct CodeMap {
-    pub files: RefCell<Vec<Rc<FileMap>>>
+    pub files: RefCell<Vec<Rc<FileMap>>>,
+    expansions: RefCell<Vec<ExpnInfo>>
 }
 
 impl CodeMap {
     pub fn new() -> CodeMap {
         CodeMap {
             files: RefCell::new(Vec::new()),
+            expansions: RefCell::new(Vec::new()),
         }
     }
 
@@ -527,6 +535,19 @@ impl CodeMap {
             col: chpos - linechpos
         }
     }
+
+    pub fn record_expansion(&self, expn_info: ExpnInfo) -> ExpnId {
+        let mut expansions = self.expansions.borrow_mut();
+        expansions.push(expn_info);
+        ExpnId(expansions.len().to_u32().expect("too many ExpnInfo's!") - 1)
+    }
+
+    pub fn with_expn_info<T>(&self, id: ExpnId, f: |Option<&ExpnInfo>| -> T) -> T {
+        match id {
+            NO_EXPANSION => f(None),
+            ExpnId(i) => f(Some(&(*self.expansions.borrow())[i as uint]))
+        }
+    }
 }
 
 #[cfg(test)]
diff --git a/src/libsyntax/diagnostic.rs b/src/libsyntax/diagnostic.rs
index faa3946b74d..f33c768d647 100644
--- a/src/libsyntax/diagnostic.rs
+++ b/src/libsyntax/diagnostic.rs
@@ -389,7 +389,7 @@ fn emit(dst: &mut EmitterWriter, cm: &codemap::CodeMap, rsp: RenderSpan,
         // we want to tell compiletest/runtest to look at the last line of the
         // span (since `custom_highlight_lines` displays an arrow to the end of
         // the span)
-        let span_end = Span { lo: sp.hi, hi: sp.hi, expn_info: sp.expn_info};
+        let span_end = Span { lo: sp.hi, hi: sp.hi, expn_id: sp.expn_id};
         let ses = cm.span_to_string(span_end);
         try!(print_diagnostic(dst, ses.as_slice(), lvl, msg, code));
         if rsp.is_full_span() {
@@ -523,24 +523,24 @@ fn print_macro_backtrace(w: &mut EmitterWriter,
                          cm: &codemap::CodeMap,
                          sp: Span)
                          -> io::IoResult<()> {
-    for ei in sp.expn_info.iter() {
-        let ss = ei.callee
-                   .span
-                   .as_ref()
-                   .map_or("".to_string(), |span| cm.span_to_string(*span));
-        let (pre, post) = match ei.callee.format {
-            codemap::MacroAttribute => ("#[", "]"),
-            codemap::MacroBang => ("", "!")
-        };
-        try!(print_diagnostic(w, ss.as_slice(), Note,
-                              format!("in expansion of {}{}{}", pre,
-                                      ei.callee.name,
-                                      post).as_slice(), None));
-        let ss = cm.span_to_string(ei.call_site);
-        try!(print_diagnostic(w, ss.as_slice(), Note, "expansion site", None));
-        try!(print_macro_backtrace(w, cm, ei.call_site));
-    }
-    Ok(())
+    let cs = try!(cm.with_expn_info(sp.expn_id, |expn_info| match expn_info {
+        Some(ei) => {
+            let ss = ei.callee.span.map_or(String::new(), |span| cm.span_to_string(span));
+            let (pre, post) = match ei.callee.format {
+                codemap::MacroAttribute => ("#[", "]"),
+                codemap::MacroBang => ("", "!")
+            };
+            try!(print_diagnostic(w, ss.as_slice(), Note,
+                                  format!("in expansion of {}{}{}", pre,
+                                          ei.callee.name,
+                                          post).as_slice(), None));
+            let ss = cm.span_to_string(ei.call_site);
+            try!(print_diagnostic(w, ss.as_slice(), Note, "expansion site", None));
+            Ok(Some(ei.call_site))
+        }
+        None => Ok(None)
+    }));
+    cs.map_or(Ok(()), |call_site| print_macro_backtrace(w, cm, call_site))
 }
 
 pub fn expect<T>(diag: &SpanHandler, opt: Option<T>, msg: || -> String) -> T {
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 773daa4a4c5..be0ab63e50d 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -11,7 +11,7 @@
 use ast;
 use ast::Name;
 use codemap;
-use codemap::{CodeMap, Span, ExpnInfo};
+use codemap::{CodeMap, Span, ExpnId, ExpnInfo, NO_EXPANSION};
 use ext;
 use ext::expand;
 use parse;
@@ -24,7 +24,6 @@ use ext::mtwt;
 use fold::Folder;
 
 use std::collections::HashMap;
-use std::gc::{Gc, GC};
 use std::rc::Rc;
 
 // new-style macro! tt code:
@@ -457,7 +456,7 @@ fn initial_syntax_expander_table() -> SyntaxEnv {
 pub struct ExtCtxt<'a> {
     pub parse_sess: &'a parse::ParseSess,
     pub cfg: ast::CrateConfig,
-    pub backtrace: Option<Gc<ExpnInfo>>,
+    pub backtrace: ExpnId,
     pub ecfg: expand::ExpansionConfig,
 
     pub mod_path: Vec<ast::Ident> ,
@@ -473,7 +472,7 @@ impl<'a> ExtCtxt<'a> {
         ExtCtxt {
             parse_sess: parse_sess,
             cfg: cfg,
-            backtrace: None,
+            backtrace: NO_EXPANSION,
             mod_path: Vec::new(),
             ecfg: ecfg,
             trace_mac: false,
@@ -501,13 +500,49 @@ impl<'a> ExtCtxt<'a> {
     pub fn parse_sess(&self) -> &'a parse::ParseSess { self.parse_sess }
     pub fn cfg(&self) -> ast::CrateConfig { self.cfg.clone() }
     pub fn call_site(&self) -> Span {
-        match self.backtrace {
+        self.codemap().with_expn_info(self.backtrace, |ei| match ei {
             Some(expn_info) => expn_info.call_site,
             None => self.bug("missing top span")
-        }
+        })
     }
     pub fn print_backtrace(&self) { }
-    pub fn backtrace(&self) -> Option<Gc<ExpnInfo>> { self.backtrace }
+    pub fn backtrace(&self) -> ExpnId { self.backtrace }
+    pub fn original_span(&self) -> Span {
+        let mut expn_id = self.backtrace;
+        let mut call_site = None;
+        loop {
+            match self.codemap().with_expn_info(expn_id, |ei| ei.map(|ei| ei.call_site)) {
+                None => break,
+                Some(cs) => {
+                    call_site = Some(cs);
+                    expn_id = cs.expn_id;
+                }
+            }
+        }
+        call_site.expect("missing expansion backtrace")
+    }
+    pub fn original_span_in_file(&self) -> Span {
+        let mut expn_id = self.backtrace;
+        let mut call_site = None;
+        loop {
+            let expn_info = self.codemap().with_expn_info(expn_id, |ei| {
+                ei.map(|ei| (ei.call_site, ei.callee.name.as_slice() == "include"))
+            });
+            match expn_info {
+                None => break,
+                Some((cs, is_include)) => {
+                    if is_include {
+                        // Don't recurse into file using "include!".
+                        break;
+                    }
+                    call_site = Some(cs);
+                    expn_id = cs.expn_id;
+                }
+            }
+        }
+        call_site.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> {
@@ -516,22 +551,22 @@ impl<'a> ExtCtxt<'a> {
         v.extend(self.mod_path.iter().map(|a| *a));
         return v;
     }
-    pub fn bt_push(&mut self, ei: codemap::ExpnInfo) {
-        match ei {
-            ExpnInfo {call_site: cs, callee: ref callee} => {
-                self.backtrace =
-                    Some(box(GC) ExpnInfo {
-                        call_site: Span {lo: cs.lo, hi: cs.hi,
-                                         expn_info: self.backtrace.clone()},
-                        callee: (*callee).clone()
-                    });
-            }
-        }
+    pub fn bt_push(&mut self, ei: ExpnInfo) {
+        let mut call_site = ei.call_site;
+        call_site.expn_id = self.backtrace;
+        self.backtrace = self.codemap().record_expansion(ExpnInfo {
+            call_site: call_site,
+            callee: ei.callee
+        });
     }
     pub fn bt_pop(&mut self) {
         match self.backtrace {
-            Some(expn_info) => self.backtrace = expn_info.call_site.expn_info,
-            _ => self.bug("tried to pop without a push")
+            NO_EXPANSION => self.bug("tried to pop without a push"),
+            expn_id => {
+                self.backtrace = self.codemap().with_expn_info(expn_id, |expn_info| {
+                    expn_info.map_or(NO_EXPANSION, |ei| ei.call_site.expn_id)
+                });
+            }
         }
     }
     /// Emit `msg` attached to `sp`, and stop compilation immediately.
diff --git a/src/libsyntax/ext/build.rs b/src/libsyntax/ext/build.rs
index 7b2613d4e8b..16ecd83180e 100644
--- a/src/libsyntax/ext/build.rs
+++ b/src/libsyntax/ext/build.rs
@@ -573,7 +573,7 @@ impl<'a> AstBuilder for ExtCtxt<'a> {
         let field_span = Span {
             lo: sp.lo - Pos::from_uint(field_name.get().len()),
             hi: sp.hi,
-            expn_info: sp.expn_info,
+            expn_id: sp.expn_id,
         };
 
         let id = Spanned { node: ident, span: field_span };
@@ -583,7 +583,7 @@ impl<'a> AstBuilder for ExtCtxt<'a> {
         let field_span = Span {
             lo: sp.lo - Pos::from_uint(idx.to_string().len()),
             hi: sp.hi,
-            expn_info: sp.expn_info,
+            expn_id: sp.expn_id,
         };
 
         let id = Spanned { node: idx, span: field_span };
diff --git a/src/libsyntax/ext/deriving/generic/mod.rs b/src/libsyntax/ext/deriving/generic/mod.rs
index ff249495bd7..142adc9b721 100644
--- a/src/libsyntax/ext/deriving/generic/mod.rs
+++ b/src/libsyntax/ext/deriving/generic/mod.rs
@@ -181,7 +181,6 @@
 //! ~~~
 
 use std::cell::RefCell;
-use std::gc::GC;
 use std::vec;
 
 use abi::Abi;
@@ -1169,7 +1168,7 @@ impl<'a> TraitDef<'a> {
             None => cx.span_bug(self.span, "trait with empty path in generic `deriving`"),
             Some(name) => *name
         };
-        to_set.expn_info = Some(box(GC) codemap::ExpnInfo {
+        to_set.expn_id = cx.codemap().record_expansion(codemap::ExpnInfo {
             call_site: to_set,
             callee: codemap::NameAndSpan {
                 name: format!("deriving({})", trait_name),
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index 4ff9912645a..f81fc909a74 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -30,8 +30,6 @@ use util::small_vector::SmallVector;
 use visit;
 use visit::Visitor;
 
-use std::gc::Gc;
-
 enum Either<L,R> {
     Left(L),
     Right(R)
@@ -161,11 +159,11 @@ fn expand_mac_invoc<T>(mac: ast::Mac, span: codemap::Span,
                         // be the root of the call stack. That's the most
                         // relevant span and it's the actual invocation of
                         // the macro.
-                        let mac_span = original_span(fld.cx);
+                        let mac_span = fld.cx.original_span();
 
                         let opt_parsed = {
                             let expanded = expandfun.expand(fld.cx,
-                                                            mac_span.call_site,
+                                                            mac_span,
                                                             marked_before.as_slice());
                             parse_thunk(expanded)
                         };
@@ -759,9 +757,9 @@ fn expand_pat(p: P<ast::Pat>, fld: &mut MacroExpander) -> P<ast::Pat> {
 
                     let fm = fresh_mark();
                     let marked_before = mark_tts(tts.as_slice(), fm);
-                    let mac_span = original_span(fld.cx);
+                    let mac_span = fld.cx.original_span();
                     let expanded = match expander.expand(fld.cx,
-                                        mac_span.call_site,
+                                        mac_span,
                                         marked_before.as_slice()).make_pat() {
                         Some(e) => e,
                         None => {
@@ -969,7 +967,7 @@ fn new_span(cx: &ExtCtxt, sp: Span) -> Span {
     Span {
         lo: sp.lo,
         hi: sp.hi,
-        expn_info: cx.backtrace(),
+        expn_id: cx.backtrace(),
     }
 }
 
@@ -1083,21 +1081,6 @@ fn mark_method(expr: P<ast::Method>, m: Mrk) -> P<ast::Method> {
         .expect_one("marking an item didn't return exactly one method")
 }
 
-fn original_span(cx: &ExtCtxt) -> Gc<codemap::ExpnInfo> {
-    let mut relevant_info = cx.backtrace();
-    let mut einfo = relevant_info.unwrap();
-    loop {
-        match relevant_info {
-            None => { break }
-            Some(e) => {
-                einfo = e;
-                relevant_info = einfo.call_site.expn_info;
-            }
-        }
-    }
-    return einfo;
-}
-
 /// Check that there are no macro invocations left in the AST:
 pub fn check_for_macros(sess: &parse::ParseSess, krate: &ast::Crate) {
     visit::walk_crate(&mut MacroExterminator{sess:sess}, krate);
diff --git a/src/libsyntax/ext/source_util.rs b/src/libsyntax/ext/source_util.rs
index 5cc0ec4a122..41967b0680c 100644
--- a/src/libsyntax/ext/source_util.rs
+++ b/src/libsyntax/ext/source_util.rs
@@ -11,7 +11,6 @@
 use ast;
 use codemap;
 use codemap::{Pos, Span};
-use codemap::{ExpnInfo, NameAndSpan};
 use ext::base::*;
 use ext::base;
 use ext::build::AstBuilder;
@@ -19,7 +18,6 @@ use parse;
 use parse::token;
 use print::pprust;
 
-use std::gc::Gc;
 use std::io::File;
 use std::rc::Rc;
 
@@ -32,10 +30,10 @@ pub fn expand_line(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
                    -> Box<base::MacResult+'static> {
     base::check_zero_tts(cx, sp, tts, "line!");
 
-    let topmost = topmost_expn_info(cx.backtrace().unwrap());
-    let loc = cx.codemap().lookup_char_pos(topmost.call_site.lo);
+    let topmost = cx.original_span_in_file();
+    let loc = cx.codemap().lookup_char_pos(topmost.lo);
 
-    base::MacExpr::new(cx.expr_uint(topmost.call_site, loc.line))
+    base::MacExpr::new(cx.expr_uint(topmost, loc.line))
 }
 
 /* col!(): expands to the current column number */
@@ -43,9 +41,9 @@ pub fn expand_col(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
                   -> Box<base::MacResult+'static> {
     base::check_zero_tts(cx, sp, tts, "col!");
 
-    let topmost = topmost_expn_info(cx.backtrace().unwrap());
-    let loc = cx.codemap().lookup_char_pos(topmost.call_site.lo);
-    base::MacExpr::new(cx.expr_uint(topmost.call_site, loc.col.to_uint()))
+    let topmost = cx.original_span_in_file();
+    let loc = cx.codemap().lookup_char_pos(topmost.lo);
+    base::MacExpr::new(cx.expr_uint(topmost, loc.col.to_uint()))
 }
 
 /// file!(): expands to the current filename */
@@ -55,10 +53,10 @@ pub fn expand_file(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
                    -> Box<base::MacResult+'static> {
     base::check_zero_tts(cx, sp, tts, "file!");
 
-    let topmost = topmost_expn_info(cx.backtrace().unwrap());
-    let loc = cx.codemap().lookup_char_pos(topmost.call_site.lo);
+    let topmost = cx.original_span_in_file();
+    let loc = cx.codemap().lookup_char_pos(topmost.lo);
     let filename = token::intern_and_get_ident(loc.file.name.as_slice());
-    base::MacExpr::new(cx.expr_str(topmost.call_site, filename))
+    base::MacExpr::new(cx.expr_str(topmost, filename))
 }
 
 pub fn expand_stringify(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
@@ -162,32 +160,6 @@ pub fn expand_include_bin(cx: &mut ExtCtxt, sp: Span, tts: &[ast::TokenTree])
     }
 }
 
-// recur along an ExpnInfo chain to find the original expression
-fn topmost_expn_info(expn_info: Gc<codemap::ExpnInfo>) -> Gc<codemap::ExpnInfo> {
-    match *expn_info {
-        ExpnInfo { call_site: ref call_site, .. } => {
-            match call_site.expn_info {
-                Some(next_expn_info) => {
-                    match *next_expn_info {
-                        ExpnInfo {
-                            callee: NameAndSpan { name: ref name, .. },
-                            ..
-                        } => {
-                            // Don't recurse into file using "include!"
-                            if "include" == name.as_slice() {
-                                expn_info
-                            } else {
-                                topmost_expn_info(next_expn_info)
-                            }
-                        }
-                    }
-                },
-                None => expn_info
-            }
-        }
-    }
-}
-
 // resolve a file-system path to an absolute file-system path (if it
 // isn't already)
 fn res_rel_file(cx: &mut ExtCtxt, sp: codemap::Span, arg: &Path) -> Path {
diff --git a/src/libsyntax/lib.rs b/src/libsyntax/lib.rs
index 457d77efb70..153b3cc90d6 100644
--- a/src/libsyntax/lib.rs
+++ b/src/libsyntax/lib.rs
@@ -23,7 +23,7 @@
        html_favicon_url = "http://www.rust-lang.org/favicon.ico",
        html_root_url = "http://doc.rust-lang.org/master/")]
 
-#![feature(macro_rules, globs, managed_boxes, default_type_params, phase)]
+#![feature(macro_rules, globs, default_type_params, phase)]
 #![feature(quote, struct_variant, unsafe_destructor, import_shadowing)]
 #![allow(deprecated)]
 
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index ff4fd41fbd7..7c0564c28d1 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -3590,7 +3590,7 @@ impl<'a> Parser<'a> {
                                     let span_with_semi = Span {
                                         lo: span.lo,
                                         hi: self.last_span.hi,
-                                        expn_info: span.expn_info,
+                                        expn_id: span.expn_id,
                                     };
                                     stmts.push(P(Spanned {
                                         node: StmtSemi(e, stmt_id),