librustc: Remove `each_path`.

This does not implement lazy symbol resolution yet.

3 files changed, 285 insertions, 257 deletions

diff --git a/src/librustc/metadata/csearch.rs b/src/librustc/metadata/csearch.rs
index 4e902f2d2ec..731dac58294 100644
--- a/src/librustc/metadata/csearch.rs
+++ b/src/librustc/metadata/csearch.rs
@@ -49,16 +49,34 @@ pub fn each_lang_item(cstore: @mut cstore::CStore,
     decoder::each_lang_item(crate_data, f)
 }
 
-/// Iterates over all the paths in the given crate.
-pub fn each_path(cstore: @mut cstore::CStore,
-                 cnum: ast::CrateNum,
-                 f: &fn(&str, decoder::def_like, ast::visibility) -> bool)
-                 -> bool {
+/// Iterates over each child of the given item.
+pub fn each_child_of_item(cstore: @mut cstore::CStore,
+                          def_id: ast::def_id,
+                          callback: &fn(decoder::def_like, ast::ident)) {
+    let crate_data = cstore::get_crate_data(cstore, def_id.crate);
+    let get_crate_data: decoder::GetCrateDataCb = |cnum| {
+        cstore::get_crate_data(cstore, cnum)
+    };
+    decoder::each_child_of_item(cstore.intr,
+                                crate_data,
+                                def_id.node,
+                                get_crate_data,
+                                callback)
+}
+
+/// Iterates over each top-level crate item.
+pub fn each_top_level_item_of_crate(cstore: @mut cstore::CStore,
+                                    cnum: ast::CrateNum,
+                                    callback: &fn(decoder::def_like,
+                                                  ast::ident)) {
     let crate_data = cstore::get_crate_data(cstore, cnum);
     let get_crate_data: decoder::GetCrateDataCb = |cnum| {
         cstore::get_crate_data(cstore, cnum)
     };
-    decoder::each_path(cstore.intr, crate_data, get_crate_data, f)
+    decoder::each_top_level_item_of_crate(cstore.intr,
+                                          crate_data,
+                                          get_crate_data,
+                                          callback)
 }
 
 pub fn get_item_path(tcx: ty::ctxt, def: ast::def_id) -> ast_map::path {
diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index 89e09a7ae1d..e2b12bc5599 100644
--- a/src/librustc/metadata/decoder.rs
+++ b/src/librustc/metadata/decoder.rs
@@ -39,7 +39,7 @@ use syntax::ast_map;
 use syntax::attr;
 use syntax::parse::token::{ident_interner, special_idents};
 use syntax::print::pprust;
-use syntax::{ast, ast_util};
+use syntax::ast;
 use syntax::codemap;
 use syntax::parse::token;
 
@@ -702,33 +702,114 @@ impl<'self> EachItemContext<'self> {
     }
 }
 
-/// Iterates over all the paths in the given crate.
-pub fn each_path(intr: @ident_interner,
-                 cdata: cmd,
-                 get_crate_data: GetCrateDataCb,
-                 f: &fn(&str, def_like, ast::visibility) -> bool)
-                 -> bool {
-    // FIXME #4572: This function needs to be nuked, as it's impossible to
-    // make fast. It's the source of most of the performance problems when
-    // compiling small crates.
+fn each_child_of_item_or_crate(intr: @ident_interner,
+                               cdata: cmd,
+                               item_doc: ebml::Doc,
+                               get_crate_data: GetCrateDataCb,
+                               callback: &fn(def_like, ast::ident)) {
+    // Iterate over all children.
+    let _ = do reader::tagged_docs(item_doc, tag_mod_child) |child_info_doc| {
+        let child_def_id = reader::with_doc_data(child_info_doc,
+                                                 parse_def_id);
+        let child_def_id = translate_def_id(cdata, child_def_id);
+
+        // This item may be in yet another crate if it was the child of a
+        // reexport.
+        let other_crates_items = if child_def_id.crate == cdata.cnum {
+            reader::get_doc(reader::Doc(cdata.data), tag_items)
+        } else {
+            let crate_data = get_crate_data(child_def_id.crate);
+            reader::get_doc(reader::Doc(crate_data.data), tag_items)
+        };
+
+        // Get the item.
+        match maybe_find_item(child_def_id.node, other_crates_items) {
+            None => {}
+            Some(child_item_doc) => {
+                // Hand off the item to the callback.
+                let child_name = item_name(intr, child_item_doc);
+                let def_like = item_to_def_like(child_item_doc,
+                                                child_def_id,
+                                                cdata.cnum);
+                callback(def_like, child_name);
+            }
+        }
+
+        true
+    };
+
+    // Iterate over all reexports.
+    let _ = do each_reexport(item_doc) |reexport_doc| {
+        let def_id_doc = reader::get_doc(reexport_doc,
+                                         tag_items_data_item_reexport_def_id);
+        let child_def_id = reader::with_doc_data(def_id_doc,
+                                                 parse_def_id);
+        let child_def_id = translate_def_id(cdata, child_def_id);
+
+        let name_doc = reader::get_doc(reexport_doc,
+                                       tag_items_data_item_reexport_name);
+        let name = name_doc.as_str_slice();
+
+        // This reexport may be in yet another crate.
+        let other_crates_items = if child_def_id.crate == cdata.cnum {
+            reader::get_doc(reader::Doc(cdata.data), tag_items)
+        } else {
+            let crate_data = get_crate_data(child_def_id.crate);
+            reader::get_doc(reader::Doc(crate_data.data), tag_items)
+        };
+
+        // Get the item.
+        match maybe_find_item(child_def_id.node, other_crates_items) {
+            None => {}
+            Some(child_item_doc) => {
+                // Hand off the item to the callback.
+                let def_like = item_to_def_like(child_item_doc,
+                                                child_def_id,
+                                                cdata.cnum);
+                callback(def_like, token::str_to_ident(name));
+            }
+        }
+
+        true
+    };
+}
 
+/// Iterates over each child of the given item.
+pub fn each_child_of_item(intr: @ident_interner,
+                          cdata: cmd,
+                          id: ast::NodeId,
+                          get_crate_data: GetCrateDataCb,
+                          callback: &fn(def_like, ast::ident)) {
+    // Find the item.
+    let root_doc = reader::Doc(cdata.data);
+    let items = reader::get_doc(root_doc, tag_items);
+    let item_doc = match maybe_find_item(id, items) {
+        None => return,
+        Some(item_doc) => item_doc,
+    };
+
+    each_child_of_item_or_crate(intr,
+                                cdata,
+                                item_doc,
+                                get_crate_data,
+                                callback)
+}
+
+/// Iterates over all the top-level crate items.
+pub fn each_top_level_item_of_crate(intr: @ident_interner,
+                                    cdata: cmd,
+                                    get_crate_data: GetCrateDataCb,
+                                    callback: &fn(def_like, ast::ident)) {
     let root_doc = reader::Doc(cdata.data);
     let misc_info_doc = reader::get_doc(root_doc, tag_misc_info);
     let crate_items_doc = reader::get_doc(misc_info_doc,
                                           tag_misc_info_crate_items);
 
-    let mut path_builder = ~"";
-
-    let mut context = EachItemContext {
-        intr: intr,
-        cdata: cdata,
-        get_crate_data: get_crate_data,
-        path_builder: &mut path_builder,
-        callback: f,
-    };
-
-    // Iterate over all top-level crate items.
-    context.each_child_of_module_or_crate(crate_items_doc)
+    each_child_of_item_or_crate(intr,
+                                cdata,
+                                crate_items_doc,
+                                get_crate_data,
+                                callback)
 }
 
 pub fn get_item_path(cdata: cmd, id: ast::NodeId) -> ast_map::path {
@@ -1268,21 +1349,6 @@ pub fn get_crate_vers(data: @~[u8]) -> @str {
     }
 }
 
-fn iter_crate_items(intr: @ident_interner, cdata: cmd,
-                    get_crate_data: GetCrateDataCb,
-                    proc: &fn(path: &str, ast::def_id)) {
-    do each_path(intr, cdata, get_crate_data) |path_string, def_like, _| {
-        match def_like {
-            dl_impl(*) | dl_field => {}
-            dl_def(def) => {
-                proc(path_string,
-                     ast_util::def_id_of_def(def))
-            }
-        }
-        true
-    };
-}
-
 pub fn list_crate_metadata(intr: @ident_interner, bytes: @~[u8],
                            out: @io::Writer) {
     let hash = get_crate_hash(bytes);
diff --git a/src/librustc/middle/resolve.rs b/src/librustc/middle/resolve.rs
index cb987c69a5b..646658986f7 100644
--- a/src/librustc/middle/resolve.rs
+++ b/src/librustc/middle/resolve.rs
@@ -10,10 +10,11 @@
 
 
 use driver::session::Session;
-use metadata::csearch::{each_path, get_trait_method_def_ids};
+use metadata::csearch::get_trait_method_def_ids;
 use metadata::csearch::get_method_name_and_explicit_self;
 use metadata::csearch::get_static_methods_if_impl;
 use metadata::csearch::{get_type_name_if_impl, get_struct_fields};
+use metadata::csearch;
 use metadata::cstore::find_extern_mod_stmt_cnum;
 use metadata::decoder::{def_like, dl_def, dl_field, dl_impl};
 use middle::lang_items::LanguageItems;
@@ -486,7 +487,7 @@ pub fn Module(parent_link: ParentLink,
         anonymous_children: @mut HashMap::new(),
         import_resolutions: @mut HashMap::new(),
         glob_count: 0,
-        resolved_import_count: 0
+        resolved_import_count: 0,
     }
 }
 
@@ -1629,14 +1630,13 @@ impl Resolver {
         visit::walk_block(visitor, block, new_parent);
     }
 
-    pub fn handle_external_def(@mut self,
-                               def: def,
-                               visibility: ast::visibility,
-                               modules: &mut HashMap<def_id, @mut Module>,
-                               child_name_bindings: @mut NameBindings,
-                               final_ident: &str,
-                               ident: ident,
-                               new_parent: ReducedGraphParent) {
+    fn handle_external_def(@mut self,
+                           def: def,
+                           visibility: ast::visibility,
+                           child_name_bindings: @mut NameBindings,
+                           final_ident: &str,
+                           ident: ident,
+                           new_parent: ReducedGraphParent) {
         let privacy = visibility_to_privacy(visibility);
         match def {
           def_mod(def_id) | def_foreign_mod(def_id) => {
@@ -1645,7 +1645,6 @@ impl Resolver {
                 debug!("(building reduced graph for external crate) \
                         already created module");
                 module_def.def_id = Some(def_id);
-                modules.insert(def_id, module_def);
               }
               Some(_) | None => {
                 debug!("(building reduced graph for \
@@ -1653,42 +1652,11 @@ impl Resolver {
                         %s", final_ident);
                 let parent_link = self.get_parent_link(new_parent, ident);
 
-                // FIXME (#5074): this should be a match on find
-                if !modules.contains_key(&def_id) {
-                    child_name_bindings.define_module(privacy,
-                                                      parent_link,
-                                                      Some(def_id),
-                                                      NormalModuleKind,
-                                                      dummy_sp());
-                    modules.insert(def_id,
-                                   child_name_bindings.get_module());
-                } else {
-                    let existing_module = *modules.get(&def_id);
-
-                    // Create an import resolution to avoid creating cycles in
-                    // the module graph.
-
-                    let resolution = @mut ImportResolution(Public, 0);
-                    resolution.outstanding_references = 0;
-
-                    match existing_module.parent_link {
-                      NoParentLink |
-                      BlockParentLink(*) => {
-                        fail!("can't happen");
-                      }
-                      ModuleParentLink(parent_module, ident) => {
-                        let name_bindings = parent_module.children.get(
-                            &ident);
-                        resolution.type_target =
-                            Some(Target(parent_module, *name_bindings));
-                      }
-                    }
-
-                    debug!("(building reduced graph for external crate) \
-                            ... creating import resolution");
-
-                    new_parent.import_resolutions.insert(ident, resolution);
-                }
+                child_name_bindings.define_module(privacy,
+                                                  parent_link,
+                                                  Some(def_id),
+                                                  NormalModuleKind,
+                                                  dummy_sp());
               }
             }
           }
@@ -1779,184 +1747,160 @@ impl Resolver {
         }
     }
 
-    /**
-     * Builds the reduced graph rooted at the 'use' directive for an external
-     * crate.
-     */
-    pub fn build_reduced_graph_for_external_crate(@mut self,
-                                                  root: @mut Module) {
-        let mut modules = HashMap::new();
-
-        // Create all the items reachable by paths.
-        do each_path(self.session.cstore, root.def_id.unwrap().crate)
-                |path_string, def_like, visibility| {
-
-            debug!("(building reduced graph for external crate) found path \
-                        entry: %s (%?)",
-                    path_string, def_like);
-
-            let mut pieces: ~[&str] = path_string.split_str_iter("::").collect();
-            let final_ident_str = pieces.pop();
-            let final_ident = self.session.ident_of(final_ident_str);
-
-            // Find the module we need, creating modules along the way if we
-            // need to.
-
-            let mut current_module = root;
-            for ident_str in pieces.iter() {
-                let ident = self.session.ident_of(*ident_str);
-                // Create or reuse a graph node for the child.
-                let (child_name_bindings, new_parent) =
-                    self.add_child(ident,
-                                   ModuleReducedGraphParent(current_module),
-                                   OverwriteDuplicates,
-                                   dummy_sp());
-
-                // Define or reuse the module node.
-                match child_name_bindings.type_def {
-                    None => {
-                        debug!("(building reduced graph for external crate) \
-                                autovivifying missing type def %s",
-                                *ident_str);
-                        let parent_link = self.get_parent_link(new_parent,
-                                                               ident);
-                        child_name_bindings.define_module(Public,
-                                                          parent_link,
-                                                          None,
-                                                          NormalModuleKind,
-                                                          dummy_sp());
-                    }
-                    Some(type_ns_def)
-                            if type_ns_def.module_def.is_none() => {
-                        debug!("(building reduced graph for external crate) \
-                                autovivifying missing module def %s",
-                                *ident_str);
-                        let parent_link = self.get_parent_link(new_parent,
-                                                               ident);
-                        child_name_bindings.define_module(Public,
-                                                          parent_link,
-                                                          None,
-                                                          NormalModuleKind,
-                                                          dummy_sp());
+    /// Builds the reduced graph for a single item in an external crate.
+    fn build_reduced_graph_for_external_crate_def(@mut self,
+                                                  root: @mut Module,
+                                                  def_like: def_like,
+                                                  ident: ident) {
+        match def_like {
+            dl_def(def) => {
+                // Add the new child item, if necessary.
+                let optional_module = match def {
+                    def_foreign_mod(*) => Some(root),
+                    _ => {
+                        let (child_name_bindings, new_parent) =
+                            self.add_child(ident,
+                                           ModuleReducedGraphParent(root),
+                                           OverwriteDuplicates,
+                                           dummy_sp());
+
+                        self.handle_external_def(def,
+                                                 public,
+                                                 child_name_bindings,
+                                                 self.session.str_of(ident),
+                                                 ident,
+                                                 new_parent);
+
+                        /*println(fmt!(">>> child item added: %s",
+                                     self.session.str_of(ident)));*/
+
+                        child_name_bindings.get_module_if_available()
                     }
-                    _ => {} // Fall through.
-                }
-
-                current_module = child_name_bindings.get_module();
-            }
-
-            match def_like {
-                dl_def(def) => {
-                    // Add the new child item.
-                    let (child_name_bindings, new_parent) =
-                        self.add_child(final_ident,
-                                       ModuleReducedGraphParent(
-                                            current_module),
-                                       OverwriteDuplicates,
-                                       dummy_sp());
-
-                    self.handle_external_def(def,
-                                             visibility,
-                                             &mut modules,
-                                             child_name_bindings,
-                                             self.session.str_of(
-                                                 final_ident),
-                                             final_ident,
-                                             new_parent);
-                }
-                dl_impl(def) => {
-                    // We only process static methods of impls here.
-                    match get_type_name_if_impl(self.session.cstore, def) {
-                        None => {}
-                        Some(final_ident) => {
-                            let static_methods_opt =
-                                get_static_methods_if_impl(
-                                    self.session.cstore, def);
-                            match static_methods_opt {
-                                Some(ref static_methods) if
-                                    static_methods.len() >= 1 => {
-                                    debug!("(building reduced graph for \
-                                            external crate) processing \
-                                            static methods for type name %s",
-                                            self.session.str_of(
-                                                final_ident));
-
-                                    let (child_name_bindings, new_parent) =
-                                        self.add_child(final_ident,
-                                            ModuleReducedGraphParent(
-                                                            current_module),
-                                            OverwriteDuplicates,
-                                            dummy_sp());
+                };
 
-                                    // Process the static methods. First,
-                                    // create the module.
-                                    let type_module;
-                                    match child_name_bindings.type_def {
-                                        Some(TypeNsDef {
-                                            module_def: Some(module_def),
-                                            _
-                                        }) => {
-                                            // We already have a module. This
-                                            // is OK.
-                                            type_module = module_def;
-
-                                            // Mark it as an impl module if
-                                            // necessary.
-                                            type_module.kind = ImplModuleKind;
-                                        }
-                                        Some(_) | None => {
-                                            let parent_link =
-                                                self.get_parent_link(
-                                                    new_parent, final_ident);
-                                            child_name_bindings.define_module(
-                                                Public,
-                                                parent_link,
-                                                Some(def),
-                                                ImplModuleKind,
-                                                dummy_sp());
-                                            type_module =
-                                                child_name_bindings.
-                                                    get_module();
-                                        }
+                match optional_module {
+                    None => {}
+                    Some(module) => {
+                        do csearch::each_child_of_item(self.session.cstore,
+                                                       def_id_of_def(def))
+                                |def_like, child_ident| {
+                            /*println(fmt!(">>> each_child_of_item: %s %s",
+                                         self.session.str_of(ident),
+                                         self.session.str_of(child_ident)));*/
+                            self.build_reduced_graph_for_external_crate_def(
+                                module,
+                                def_like,
+                                child_ident)
+                        }
+                    }
+                }
+            }
+            dl_impl(def) => {
+                // We only process static methods of impls here.
+                match get_type_name_if_impl(self.session.cstore, def) {
+                    None => {}
+                    Some(final_ident) => {
+                        let static_methods_opt =
+                            get_static_methods_if_impl(self.session.cstore,
+                                                       def);
+                        match static_methods_opt {
+                            Some(ref static_methods) if
+                                static_methods.len() >= 1 => {
+                                debug!("(building reduced graph for \
+                                        external crate) processing \
+                                        static methods for type name %s",
+                                        self.session.str_of(
+                                            final_ident));
+
+                                let (child_name_bindings, new_parent) =
+                                    self.add_child(
+                                        final_ident,
+                                        ModuleReducedGraphParent(root),
+                                        OverwriteDuplicates,
+                                        dummy_sp());
+
+                                // Process the static methods. First,
+                                // create the module.
+                                let type_module;
+                                match child_name_bindings.type_def {
+                                    Some(TypeNsDef {
+                                        module_def: Some(module_def),
+                                        _
+                                    }) => {
+                                        // We already have a module. This
+                                        // is OK.
+                                        type_module = module_def;
+
+                                        // Mark it as an impl module if
+                                        // necessary.
+                                        type_module.kind = ImplModuleKind;
                                     }
-
-                                    // Add each static method to the module.
-                                    let new_parent = ModuleReducedGraphParent(
-                                        type_module);
-                                    for static_method_info in static_methods.iter() {
-                                        let ident = static_method_info.ident;
-                                        debug!("(building reduced graph for \
-                                                 external crate) creating \
-                                                 static method '%s'",
-                                               self.session.str_of(ident));
-
-                                        let (method_name_bindings, _) =
-                                            self.add_child(
-                                                ident,
-                                                new_parent,
-                                                OverwriteDuplicates,
-                                                dummy_sp());
-                                        let def = def_fn(
-                                            static_method_info.def_id,
-                                            static_method_info.purity);
-                                        method_name_bindings.define_value(
-                                            Public, def, dummy_sp());
+                                    Some(_) | None => {
+                                        let parent_link =
+                                            self.get_parent_link(new_parent,
+                                                                 final_ident);
+                                        child_name_bindings.define_module(
+                                            Public,
+                                            parent_link,
+                                            Some(def),
+                                            ImplModuleKind,
+                                            dummy_sp());
+                                        type_module =
+                                            child_name_bindings.
+                                                get_module();
                                     }
                                 }
 
-                                // Otherwise, do nothing.
-                                Some(_) | None => {}
+                                // Add each static method to the module.
+                                let new_parent =
+                                    ModuleReducedGraphParent(type_module);
+                                for static_method_info in
+                                        static_methods.iter() {
+                                    let ident = static_method_info.ident;
+                                    debug!("(building reduced graph for \
+                                             external crate) creating \
+                                             static method '%s'",
+                                           self.session.str_of(ident));
+
+                                    let (method_name_bindings, _) =
+                                        self.add_child(ident,
+                                                       new_parent,
+                                                       OverwriteDuplicates,
+                                                       dummy_sp());
+                                    let def = def_fn(
+                                        static_method_info.def_id,
+                                        static_method_info.purity);
+                                    method_name_bindings.define_value(
+                                        Public,
+                                        def,
+                                        dummy_sp());
+                                }
                             }
+
+                            // Otherwise, do nothing.
+                            Some(_) | None => {}
                         }
                     }
                 }
-                dl_field => {
-                    debug!("(building reduced graph for external crate) \
-                            ignoring field");
-                }
             }
-            true
-        };
+            dl_field => {
+                debug!("(building reduced graph for external crate) \
+                        ignoring field");
+            }
+        }
+    }
+
+    /// Builds the reduced graph rooted at the 'use' directive for an external
+    /// crate.
+    pub fn build_reduced_graph_for_external_crate(@mut self,
+                                                  root: @mut Module) {
+        do csearch::each_top_level_item_of_crate(self.session.cstore,
+                                                 root.def_id.unwrap().crate)
+                |def_like, ident| {
+            self.build_reduced_graph_for_external_crate_def(root,
+                                                            def_like,
+                                                            ident)
+        }
     }
 
     /// Creates and adds an import directive to the given module.