Add a reachability checker, only export metadata for reachable items

Closes #1934

3 files changed, 146 insertions, 7 deletions

diff --git a/src/rustc/metadata/encoder.rs b/src/rustc/metadata/encoder.rs
index 8ae7b6e3592..ab6a8dea04c 100644
--- a/src/rustc/metadata/encoder.rs
+++ b/src/rustc/metadata/encoder.rs
@@ -27,7 +27,9 @@ export encode_def_id;
 
 type abbrev_map = map::hashmap<ty::t, tyencode::ty_abbrev>;
 
-type encode_ctxt = {ccx: crate_ctxt, type_abbrevs: abbrev_map};
+type encode_ctxt = {ccx: crate_ctxt,
+                    type_abbrevs: abbrev_map,
+                    reachable: reachable::map};
 
 // Path table encoding
 fn encode_name(ebml_w: ebml::writer, name: str) {
@@ -73,11 +75,11 @@ fn encode_native_module_item_paths(ebml_w: ebml::writer, nmod: native_mod,
     }
 }
 
-fn encode_module_item_paths(ebml_w: ebml::writer, module: _mod, path: [str],
-                            &index: [entry<str>]) {
+fn encode_module_item_paths(ebml_w: ebml::writer, ecx: @encode_ctxt,
+                            module: _mod, path: [str], &index: [entry<str>]) {
     // FIXME factor out add_to_index/start/encode_name/encode_def_id/end ops
     for it: @item in module.items {
-        if !ast_util::is_exported(it.ident, module) { cont; }
+        if !ecx.reachable.contains_key(it.id) { cont; }
         alt it.node {
           item_const(_, _) {
             add_to_index(ebml_w, path, index, it.ident);
@@ -92,7 +94,8 @@ fn encode_module_item_paths(ebml_w: ebml::writer, module: _mod, path: [str],
             ebml_w.start_tag(tag_paths_data_mod);
             encode_name(ebml_w, it.ident);
             encode_def_id(ebml_w, local_def(it.id));
-            encode_module_item_paths(ebml_w, _mod, path + [it.ident], index);
+            encode_module_item_paths(ebml_w, ecx, _mod, path + [it.ident],
+                                     index);
             ebml_w.end_tag();
           }
           item_native_mod(nmod) {
@@ -151,7 +154,7 @@ fn encode_item_paths(ebml_w: ebml::writer, ecx: @encode_ctxt, crate: @crate)
     let index: [entry<str>] = [];
     let path: [str] = [];
     ebml_w.start_tag(tag_paths);
-    encode_module_item_paths(ebml_w, crate.node.module, path, index);
+    encode_module_item_paths(ebml_w, ecx, crate.node.module, path, index);
     encode_reexport_paths(ebml_w, ecx, index);
     ebml_w.end_tag();
     ret index;
@@ -334,6 +337,12 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::writer, item: @item,
     }
 
     let tcx = ecx.ccx.tcx;
+    let must_write = alt item.node {
+      item_enum(_, _) | item_res(_, _, _, _, _) { true }
+      _ { false }
+    };
+    if !must_write && !ecx.reachable.contains_key(item.id) { ret; }
+
     alt item.node {
       item_const(_, _) {
         ebml_w.start_tag(tag_items_data_item);
@@ -488,6 +497,7 @@ fn encode_info_for_item(ecx: @encode_ctxt, ebml_w: ebml::writer, item: @item,
 
 fn encode_info_for_native_item(ecx: @encode_ctxt, ebml_w: ebml::writer,
                                nitem: @native_item, path: ast_map::path) {
+    if !ecx.reachable.contains_key(nitem.id) { ret; }
     ebml_w.start_tag(tag_items_data_item);
     alt nitem.node {
       native_item_fn(fn_decl, tps) {
@@ -723,8 +733,11 @@ fn encode_hash(ebml_w: ebml::writer, hash: str) {
 
 fn encode_metadata(cx: crate_ctxt, crate: @crate) -> [u8] {
 
+    let reachable = reachable::find_reachable(cx, crate.node.module);
     let abbrevs = ty::new_ty_hash();
-    let ecx = @{ccx: cx, type_abbrevs: abbrevs};
+    let ecx = @{ccx: cx,
+                type_abbrevs: abbrevs,
+                reachable: reachable};
 
     let buf = io::mk_mem_buffer();
     let buf_w = io::mem_buffer_writer(buf);
diff --git a/src/rustc/metadata/reachable.rs b/src/rustc/metadata/reachable.rs
new file mode 100644
index 00000000000..e85d4098fde
--- /dev/null
+++ b/src/rustc/metadata/reachable.rs
@@ -0,0 +1,125 @@
+// Finds items that are externally reachable, to determine which items
+// need to have their metadata (and possibly their AST) serialized.
+// All items that can be referred to through an exported name are
+// reachable, and when a reachable thing is inline or generic, it
+// makes all other generics or inline functions that it references
+// reachable as well.
+
+import middle::{resolve, ast_map, typeck};
+import syntax::ast::*;
+import syntax::visit;
+import syntax::ast_util::def_id_of_def;
+import front::attr;
+
+export map, find_reachable;
+
+type map = std::map::map<node_id, ()>;
+
+type ctx = {ccx: middle::trans::common::crate_ctxt,
+            rmap: map};
+
+fn find_reachable(ccx: middle::trans::common::crate_ctxt, crate_mod: _mod)
+    -> map {
+    let rmap = std::map::new_int_hash();
+    traverse_public_mod({ccx: ccx, rmap: rmap}, crate_mod);
+    rmap
+}
+
+fn traverse_exports(cx: ctx, vis: [@view_item]) -> bool {
+    let found_export = false;
+    for vi in vis {
+        alt vi.node {
+          view_item_export(vps) {
+            found_export = true;
+            for vp in vps {
+                alt vp.node {
+                  view_path_simple(_, _, id) | view_path_glob(_, id) |
+                  view_path_list(_, _, id) {
+                    traverse_export(cx, id);
+                  }
+                }
+            }
+          }
+          _ {}
+        }
+    }
+    found_export
+}
+
+fn traverse_export(cx: ctx, exp_id: node_id) {
+    option::may(cx.ccx.exp_map.find(exp_id)) {|defs|
+        for def in defs { traverse_def_id(cx, def.id); }
+    }
+}
+
+fn traverse_def_id(cx: ctx, did: def_id) {
+    if did.crate != local_crate { ret; }
+    alt cx.ccx.tcx.items.get(did.node) {
+      ast_map::node_item(item, _) { traverse_public_item(cx, item); }
+      ast_map::node_method(_, impl_id, _) { traverse_def_id(cx, impl_id); }
+      ast_map::node_native_item(item, _) { cx.rmap.insert(item.id, ()); }
+      ast_map::node_variant(v, _, _) { cx.rmap.insert(v.node.id, ()); }
+      _ {}
+    }
+}
+
+fn traverse_public_mod(cx: ctx, m: _mod) {
+    if !traverse_exports(cx, m.view_items) {
+        // No exports, so every local item is exported
+        for item in m.items { traverse_public_item(cx, item); }
+    }
+}
+
+fn traverse_public_item(cx: ctx, item: @item) {
+    if cx.rmap.contains_key(item.id) { ret; }
+    cx.rmap.insert(item.id, ());
+    alt item.node {
+      item_mod(m) { traverse_public_mod(cx, m); }
+      item_native_mod(nm) {
+          if !traverse_exports(cx, nm.view_items) {
+              for item in nm.items { cx.rmap.insert(item.id, ()); }
+          }
+      }
+      item_res(_, tps, blk, _, _) | item_fn(_, tps, blk) {
+        if tps.len() > 0u ||
+           attr::find_inline_attr(item.attrs) != attr::ia_none {
+            traverse_inline_body(cx, blk);
+        }
+      }
+      item_impl(tps, _, _, ms) {
+        for m in ms {
+            if tps.len() > 0u || m.tps.len() > 0u ||
+               attr::find_inline_attr(m.attrs) != attr::ia_none {
+                traverse_inline_body(cx, m.body);
+            }
+        }
+      }
+      item_class(_tps, _items, _) {} // FIXME handle these when stable
+      item_const(_, _) | item_ty(_, _) | item_enum(_, _) | item_iface(_, _) {}
+    }
+}
+
+fn traverse_inline_body(cx: ctx, body: blk) {
+    fn traverse_expr(e: @expr, cx: ctx, v: visit::vt<ctx>) {
+        alt e.node {
+          expr_path(_) {
+            traverse_def_id(cx, def_id_of_def(cx.ccx.tcx.def_map.get(e.id)));
+          }
+          expr_field(_, _, _) {
+            alt cx.ccx.maps.method_map.find(e.id) {
+              some(typeck::method_static(did)) { traverse_def_id(cx, did); }
+              _ {}
+            }
+          }
+          _ {}
+        }
+        visit::visit_expr(e, cx, v);
+    }
+    // Ignore nested items
+    fn traverse_item(_i: @item, _cx: ctx, _v: visit::vt<ctx>) {}
+    visit::visit_block(body, cx, visit::mk_vt(@{
+        visit_expr: traverse_expr,
+        visit_item: traverse_item
+        with *visit::default_visitor()
+    }));
+}
diff --git a/src/rustc/rustc.rc b/src/rustc/rustc.rc
index a8b398066ec..837e1675679 100644
--- a/src/rustc/rustc.rc
+++ b/src/rustc/rustc.rc
@@ -128,6 +128,7 @@ mod metadata {
     mod creader;
     mod cstore;
     mod csearch;
+    mod reachable;
 }
 
 mod driver {