src/librustc_metadata/cstore_impl.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use cstore;
  12 use encoder;
  13 use locator;
  14 use schema;
  15
  16 use rustc::middle::cstore::{InlinedItem, CrateStore, CrateSource, LibSource, DepKind, ExternCrate};
  17 use rustc::middle::cstore::{NativeLibrary, LinkMeta, LinkagePreference, LoadedMacro};
  18 use rustc::hir::def::{self, Def};
  19 use rustc::middle::lang_items;
  20 use rustc::session::Session;
  21 use rustc::ty::{self, Ty, TyCtxt};
  22 use rustc::hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX, LOCAL_CRATE};
  23
  24 use rustc::dep_graph::DepNode;
  25 use rustc::hir::map::{DefKey, DefPath, DisambiguatedDefPathData};
  26 use rustc::mir::Mir;
  27 use rustc::util::nodemap::{NodeSet, DefIdMap};
  28 use rustc_back::PanicStrategy;
  29
  30 use syntax::ast;
  31 use syntax::attr;
  32 use syntax::parse::new_parser_from_source_str;
  33 use syntax::symbol::Symbol;
  34 use syntax_pos::{mk_sp, Span};
  35 use rustc::hir::svh::Svh;
  36 use rustc_back::target::Target;
  37 use rustc::hir;
  38
  39 impl<'tcx> CrateStore<'tcx> for cstore::CStore {
  40     fn describe_def(&self, def: DefId) -> Option<Def> {
  41         self.dep_graph.read(DepNode::MetaData(def));
  42         self.get_crate_data(def.krate).get_def(def.index)
  43     }
  44
  45     fn def_span(&self, sess: &Session, def: DefId) -> Span {
  46         self.dep_graph.read(DepNode::MetaData(def));
  47         self.get_crate_data(def.krate).get_span(def.index, sess)
  48     }
  49
  50     fn stability(&self, def: DefId) -> Option<attr::Stability> {
  51         self.dep_graph.read(DepNode::MetaData(def));
  52         self.get_crate_data(def.krate).get_stability(def.index)
  53     }
  54
  55     fn deprecation(&self, def: DefId) -> Option<attr::Deprecation> {
  56         self.dep_graph.read(DepNode::MetaData(def));
  57         self.get_crate_data(def.krate).get_deprecation(def.index)
  58     }
  59
  60     fn visibility(&self, def: DefId) -> ty::Visibility {
  61         self.dep_graph.read(DepNode::MetaData(def));
  62         self.get_crate_data(def.krate).get_visibility(def.index)
  63     }
  64
  65     fn closure_kind(&self, def_id: DefId) -> ty::ClosureKind
  66     {
  67         assert!(!def_id.is_local());
  68         self.dep_graph.read(DepNode::MetaData(def_id));
  69         self.get_crate_data(def_id.krate).closure_kind(def_id.index)
  70     }
  71
  72     fn closure_ty<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> ty::ClosureTy<'tcx> {
  73         assert!(!def_id.is_local());
  74         self.dep_graph.read(DepNode::MetaData(def_id));
  75         self.get_crate_data(def_id.krate).closure_ty(def_id.index, tcx)
  76     }
  77
  78     fn item_variances(&self, def: DefId) -> Vec<ty::Variance> {
  79         self.dep_graph.read(DepNode::MetaData(def));
  80         self.get_crate_data(def.krate).get_item_variances(def.index)
  81     }
  82
  83     fn item_type<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def: DefId)
  84                      -> Ty<'tcx>
  85     {
  86         self.dep_graph.read(DepNode::MetaData(def));
  87         self.get_crate_data(def.krate).get_type(def.index, tcx)
  88     }
  89
  90     fn item_predicates<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def: DefId)
  91                            -> ty::GenericPredicates<'tcx>
  92     {
  93         self.dep_graph.read(DepNode::MetaData(def));
  94         self.get_crate_data(def.krate).get_predicates(def.index, tcx)
  95     }
  96
  97     fn item_super_predicates<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def: DefId)
  98                                  -> ty::GenericPredicates<'tcx>
  99     {
 100         self.dep_graph.read(DepNode::MetaData(def));
 101         self.get_crate_data(def.krate).get_super_predicates(def.index, tcx)
 102     }
 103
 104     fn item_generics<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def: DefId)
 105                          -> ty::Generics<'tcx>
 106     {
 107         self.dep_graph.read(DepNode::MetaData(def));
 108         self.get_crate_data(def.krate).get_generics(def.index, tcx)
 109     }
 110
 111     fn item_attrs(&self, def_id: DefId) -> Vec<ast::Attribute>
 112     {
 113         self.dep_graph.read(DepNode::MetaData(def_id));
 114         self.get_crate_data(def_id.krate).get_item_attrs(def_id.index)
 115     }
 116
 117     fn trait_def<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def: DefId) -> ty::TraitDef
 118     {
 119         self.dep_graph.read(DepNode::MetaData(def));
 120         self.get_crate_data(def.krate).get_trait_def(def.index, tcx)
 121     }
 122
 123     fn adt_def<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def: DefId) -> &'tcx ty::AdtDef
 124     {
 125         self.dep_graph.read(DepNode::MetaData(def));
 126         self.get_crate_data(def.krate).get_adt_def(def.index, tcx)
 127     }
 128
 129     fn fn_arg_names(&self, did: DefId) -> Vec<ast::Name>
 130     {
 131         self.dep_graph.read(DepNode::MetaData(did));
 132         self.get_crate_data(did.krate).get_fn_arg_names(did.index)
 133     }
 134
 135     fn inherent_implementations_for_type(&self, def_id: DefId) -> Vec<DefId>
 136     {
 137         self.dep_graph.read(DepNode::MetaData(def_id));
 138         self.get_crate_data(def_id.krate).get_inherent_implementations_for_type(def_id.index)
 139     }
 140
 141     fn implementations_of_trait(&self, filter: Option<DefId>) -> Vec<DefId>
 142     {
 143         if let Some(def_id) = filter {
 144             self.dep_graph.read(DepNode::MetaData(def_id));
 145         }
 146         let mut result = vec![];
 147         self.iter_crate_data(|_, cdata| {
 148             cdata.get_implementations_for_trait(filter, &mut result)
 149         });
 150         result
 151     }
 152
 153     fn associated_item_def_ids(&self, def_id: DefId) -> Vec<DefId> {
 154         self.dep_graph.read(DepNode::MetaData(def_id));
 155         let mut result = vec![];
 156         self.get_crate_data(def_id.krate)
 157             .each_child_of_item(def_id.index, |child| result.push(child.def.def_id()));
 158         result
 159     }
 160
 161     fn impl_polarity(&self, def: DefId) -> hir::ImplPolarity
 162     {
 163         self.dep_graph.read(DepNode::MetaData(def));
 164         self.get_crate_data(def.krate).get_impl_polarity(def.index)
 165     }
 166
 167     fn impl_trait_ref<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def: DefId)
 168                           -> Option<ty::TraitRef<'tcx>>
 169     {
 170         self.dep_graph.read(DepNode::MetaData(def));
 171         self.get_crate_data(def.krate).get_impl_trait(def.index, tcx)
 172     }
 173
 174     fn custom_coerce_unsized_kind(&self, def: DefId)
 175                                   -> Option<ty::adjustment::CustomCoerceUnsized>
 176     {
 177         self.dep_graph.read(DepNode::MetaData(def));
 178         self.get_crate_data(def.krate).get_custom_coerce_unsized_kind(def.index)
 179     }
 180
 181     fn impl_parent(&self, impl_def: DefId) -> Option<DefId> {
 182         self.dep_graph.read(DepNode::MetaData(impl_def));
 183         self.get_crate_data(impl_def.krate).get_parent_impl(impl_def.index)
 184     }
 185
 186     fn trait_of_item(&self, def_id: DefId) -> Option<DefId> {
 187         self.dep_graph.read(DepNode::MetaData(def_id));
 188         self.get_crate_data(def_id.krate).get_trait_of_item(def_id.index)
 189     }
 190
 191     fn associated_item<'a>(&self, _tcx: TyCtxt<'a, 'tcx, 'tcx>, def: DefId)
 192                            -> Option<ty::AssociatedItem>
 193     {
 194         self.dep_graph.read(DepNode::MetaData(def));
 195         self.get_crate_data(def.krate).get_associated_item(def.index)
 196     }
 197
 198     fn is_const_fn(&self, did: DefId) -> bool
 199     {
 200         self.dep_graph.read(DepNode::MetaData(did));
 201         self.get_crate_data(did.krate).is_const_fn(did.index)
 202     }
 203
 204     fn is_defaulted_trait(&self, trait_def_id: DefId) -> bool
 205     {
 206         self.dep_graph.read(DepNode::MetaData(trait_def_id));
 207         self.get_crate_data(trait_def_id.krate).is_defaulted_trait(trait_def_id.index)
 208     }
 209
 210     fn is_default_impl(&self, impl_did: DefId) -> bool {
 211         self.dep_graph.read(DepNode::MetaData(impl_did));
 212         self.get_crate_data(impl_did.krate).is_default_impl(impl_did.index)
 213     }
 214
 215     fn is_foreign_item(&self, did: DefId) -> bool {
 216         self.get_crate_data(did.krate).is_foreign_item(did.index)
 217     }
 218
 219     fn is_statically_included_foreign_item(&self, def_id: DefId) -> bool
 220     {
 221         self.do_is_statically_included_foreign_item(def_id)
 222     }
 223
 224     fn is_dllimport_foreign_item(&self, def_id: DefId) -> bool {
 225         if def_id.krate == LOCAL_CRATE {
 226             self.dllimport_foreign_items.borrow().contains(&def_id.index)
 227         } else {
 228             self.get_crate_data(def_id.krate).is_dllimport_foreign_item(def_id.index)
 229         }
 230     }
 231
 232     fn dylib_dependency_formats(&self, cnum: CrateNum)
 233                                 -> Vec<(CrateNum, LinkagePreference)>
 234     {
 235         self.get_crate_data(cnum).get_dylib_dependency_formats()
 236     }
 237
 238     fn dep_kind(&self, cnum: CrateNum) -> DepKind
 239     {
 240         self.get_crate_data(cnum).dep_kind.get()
 241     }
 242
 243     fn export_macros(&self, cnum: CrateNum) {
 244         if self.get_crate_data(cnum).dep_kind.get() == DepKind::UnexportedMacrosOnly {
 245             self.get_crate_data(cnum).dep_kind.set(DepKind::MacrosOnly)
 246         }
 247     }
 248
 249     fn lang_items(&self, cnum: CrateNum) -> Vec<(DefIndex, usize)>
 250     {
 251         self.get_crate_data(cnum).get_lang_items()
 252     }
 253
 254     fn missing_lang_items(&self, cnum: CrateNum)
 255                           -> Vec<lang_items::LangItem>
 256     {
 257         self.get_crate_data(cnum).get_missing_lang_items()
 258     }
 259
 260     fn is_staged_api(&self, cnum: CrateNum) -> bool
 261     {
 262         self.get_crate_data(cnum).is_staged_api()
 263     }
 264
 265     fn is_allocator(&self, cnum: CrateNum) -> bool
 266     {
 267         self.get_crate_data(cnum).is_allocator()
 268     }
 269
 270     fn is_panic_runtime(&self, cnum: CrateNum) -> bool
 271     {
 272         self.get_crate_data(cnum).is_panic_runtime()
 273     }
 274
 275     fn is_compiler_builtins(&self, cnum: CrateNum) -> bool {
 276         self.get_crate_data(cnum).is_compiler_builtins()
 277     }
 278
 279     fn panic_strategy(&self, cnum: CrateNum) -> PanicStrategy {
 280         self.get_crate_data(cnum).panic_strategy()
 281     }
 282
 283     fn crate_name(&self, cnum: CrateNum) -> Symbol
 284     {
 285         self.get_crate_data(cnum).name
 286     }
 287
 288     fn original_crate_name(&self, cnum: CrateNum) -> Symbol
 289     {
 290         self.get_crate_data(cnum).name()
 291     }
 292
 293     fn extern_crate(&self, cnum: CrateNum) -> Option<ExternCrate>
 294     {
 295         self.get_crate_data(cnum).extern_crate.get()
 296     }
 297
 298     fn crate_hash(&self, cnum: CrateNum) -> Svh
 299     {
 300         self.get_crate_hash(cnum)
 301     }
 302
 303     fn crate_disambiguator(&self, cnum: CrateNum) -> Symbol
 304     {
 305         self.get_crate_data(cnum).disambiguator()
 306     }
 307
 308     fn plugin_registrar_fn(&self, cnum: CrateNum) -> Option<DefId>
 309     {
 310         self.get_crate_data(cnum).root.plugin_registrar_fn.map(|index| DefId {
 311             krate: cnum,
 312             index: index
 313         })
 314     }
 315
 316     fn derive_registrar_fn(&self, cnum: CrateNum) -> Option<DefId>
 317     {
 318         self.get_crate_data(cnum).root.macro_derive_registrar.map(|index| DefId {
 319             krate: cnum,
 320             index: index
 321         })
 322     }
 323
 324     fn native_libraries(&self, cnum: CrateNum) -> Vec<NativeLibrary>
 325     {
 326         self.get_crate_data(cnum).get_native_libraries()
 327     }
 328
 329     fn exported_symbols(&self, cnum: CrateNum) -> Vec<DefId>
 330     {
 331         self.get_crate_data(cnum).get_exported_symbols()
 332     }
 333
 334     fn is_no_builtins(&self, cnum: CrateNum) -> bool {
 335         self.get_crate_data(cnum).is_no_builtins()
 336     }
 337
 338     fn retrace_path(&self,
 339                     cnum: CrateNum,
 340                     path: &[DisambiguatedDefPathData])
 341                     -> Option<DefId> {
 342         let cdata = self.get_crate_data(cnum);
 343         cdata.def_path_table
 344              .retrace_path(&path)
 345              .map(|index| DefId { krate: cnum, index: index })
 346     }
 347
 348     /// Returns the `DefKey` for a given `DefId`. This indicates the
 349     /// parent `DefId` as well as some idea of what kind of data the
 350     /// `DefId` refers to.
 351     fn def_key(&self, def: DefId) -> DefKey {
 352         // Note: loading the def-key (or def-path) for a def-id is not
 353         // a *read* of its metadata. This is because the def-id is
 354         // really just an interned shorthand for a def-path, which is the
 355         // canonical name for an item.
 356         //
 357         // self.dep_graph.read(DepNode::MetaData(def));
 358         self.get_crate_data(def.krate).def_key(def.index)
 359     }
 360
 361     fn def_path(&self, def: DefId) -> DefPath {
 362         // See `Note` above in `def_key()` for why this read is
 363         // commented out:
 364         //
 365         // self.dep_graph.read(DepNode::MetaData(def));
 366         self.get_crate_data(def.krate).def_path(def.index)
 367     }
 368
 369     fn struct_field_names(&self, def: DefId) -> Vec<ast::Name>
 370     {
 371         self.dep_graph.read(DepNode::MetaData(def));
 372         self.get_crate_data(def.krate).get_struct_field_names(def.index)
 373     }
 374
 375     fn item_children(&self, def_id: DefId) -> Vec<def::Export>
 376     {
 377         self.dep_graph.read(DepNode::MetaData(def_id));
 378         let mut result = vec![];
 379         self.get_crate_data(def_id.krate)
 380             .each_child_of_item(def_id.index, |child| result.push(child));
 381         result
 382     }
 383
 384     fn load_macro(&self, id: DefId, sess: &Session) -> LoadedMacro {
 385         let data = self.get_crate_data(id.krate);
 386         if let Some(ref proc_macros) = data.proc_macros {
 387             return LoadedMacro::ProcMacro(proc_macros[id.index.as_usize() - 1].1.clone());
 388         }
 389
 390         let (name, def) = data.get_macro(id.index);
 391         let source_name = format!("<{} macros>", name);
 392
 393         // NB: Don't use parse_tts_from_source_str because it parses with quote_depth > 0.
 394         let mut parser = new_parser_from_source_str(&sess.parse_sess, source_name, def.body);
 395
 396         let lo = parser.span.lo;
 397         let body = match parser.parse_all_token_trees() {
 398             Ok(body) => body,
 399             Err(mut err) => {
 400                 err.emit();
 401                 sess.abort_if_errors();
 402                 unreachable!();
 403             }
 404         };
 405         let local_span = mk_sp(lo, parser.prev_span.hi);
 406
 407         // Mark the attrs as used
 408         let attrs = data.get_item_attrs(id.index);
 409         for attr in &attrs {
 410             attr::mark_used(attr);
 411         }
 412
 413         let name = data.def_key(id.index).disambiguated_data.data
 414             .get_opt_name().expect("no name in load_macro");
 415         sess.imported_macro_spans.borrow_mut()
 416             .insert(local_span, (name.to_string(), data.get_span(id.index, sess)));
 417
 418         LoadedMacro::MacroRules(ast::MacroDef {
 419             ident: ast::Ident::with_empty_ctxt(name),
 420             id: ast::DUMMY_NODE_ID,
 421             span: local_span,
 422             imported_from: None, // FIXME
 423             allow_internal_unstable: attr::contains_name(&attrs, "allow_internal_unstable"),
 424             attrs: attrs,
 425             body: body,
 426         })
 427     }
 428
 429     fn maybe_get_item_ast<'a>(&'tcx self,
 430                               tcx: TyCtxt<'a, 'tcx, 'tcx>,
 431                               def_id: DefId)
 432                               -> Option<(&'tcx InlinedItem, ast::NodeId)>
 433     {
 434         self.dep_graph.read(DepNode::MetaData(def_id));
 435
 436         match self.inlined_item_cache.borrow().get(&def_id) {
 437             Some(&None) => {
 438                 return None; // Not inlinable
 439             }
 440             Some(&Some(ref cached_inlined_item)) => {
 441                 // Already inline
 442                 debug!("maybe_get_item_ast({}): already inline as node id {}",
 443                           tcx.item_path_str(def_id), cached_inlined_item.item_id);
 444                 return Some((tcx.map.expect_inlined_item(cached_inlined_item.inlined_root),
 445                              cached_inlined_item.item_id));
 446             }
 447             None => {
 448                 // Not seen yet
 449             }
 450         }
 451
 452         debug!("maybe_get_item_ast({}): inlining item", tcx.item_path_str(def_id));
 453
 454         let inlined = self.get_crate_data(def_id.krate).maybe_get_item_ast(tcx, def_id.index);
 455
 456         let cache_inlined_item = |original_def_id, inlined_item_id, inlined_root_node_id| {
 457             let cache_entry = cstore::CachedInlinedItem {
 458                 inlined_root: inlined_root_node_id,
 459                 item_id: inlined_item_id,
 460             };
 461             self.inlined_item_cache
 462                 .borrow_mut()
 463                 .insert(original_def_id, Some(cache_entry));
 464             self.defid_for_inlined_node
 465                 .borrow_mut()
 466                 .insert(inlined_item_id, original_def_id);
 467         };
 468
 469         let find_inlined_item_root = |inlined_item_id| {
 470             let mut node = inlined_item_id;
 471
 472             // If we can't find the inline root after a thousand hops, we can
 473             // be pretty sure there's something wrong with the HIR map.
 474             for _ in 0 .. 1000 {
 475                 let parent_node = tcx.map.get_parent_node(node);
 476                 if parent_node == node {
 477                     return node;
 478                 }
 479                 node = parent_node;
 480             }
 481             bug!("cycle in HIR map parent chain")
 482         };
 483
 484         match inlined {
 485             None => {
 486                 self.inlined_item_cache
 487                     .borrow_mut()
 488                     .insert(def_id, None);
 489             }
 490             Some(&InlinedItem { ref body, .. }) => {
 491                 let inlined_root_node_id = find_inlined_item_root(body.id);
 492                 cache_inlined_item(def_id, inlined_root_node_id, inlined_root_node_id);
 493             }
 494         }
 495
 496         // We can be sure to hit the cache now
 497         return self.maybe_get_item_ast(tcx, def_id);
 498     }
 499
 500     fn local_node_for_inlined_defid(&'tcx self, def_id: DefId) -> Option<ast::NodeId> {
 501         assert!(!def_id.is_local());
 502         match self.inlined_item_cache.borrow().get(&def_id) {
 503             Some(&Some(ref cached_inlined_item)) => {
 504                 Some(cached_inlined_item.item_id)
 505             }
 506             Some(&None) => {
 507                 None
 508             }
 509             _ => {
 510                 bug!("Trying to lookup inlined NodeId for unexpected item");
 511             }
 512         }
 513     }
 514
 515     fn defid_for_inlined_node(&'tcx self, node_id: ast::NodeId) -> Option<DefId> {
 516         self.defid_for_inlined_node.borrow().get(&node_id).map(|x| *x)
 517     }
 518
 519     fn get_item_mir<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def: DefId) -> Mir<'tcx> {
 520         self.dep_graph.read(DepNode::MetaData(def));
 521         self.get_crate_data(def.krate).maybe_get_item_mir(tcx, def.index).unwrap_or_else(|| {
 522             bug!("get_item_mir: missing MIR for {}", tcx.item_path_str(def))
 523         })
 524     }
 525
 526     fn is_item_mir_available(&self, def: DefId) -> bool {
 527         self.dep_graph.read(DepNode::MetaData(def));
 528         self.get_crate_data(def.krate).is_item_mir_available(def.index)
 529     }
 530
 531     fn can_have_local_instance<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, def: DefId) -> bool {
 532         self.dep_graph.read(DepNode::MetaData(def));
 533         def.is_local() || self.get_crate_data(def.krate).can_have_local_instance(tcx, def.index)
 534     }
 535
 536     fn crates(&self) -> Vec<CrateNum>
 537     {
 538         let mut result = vec![];
 539         self.iter_crate_data(|cnum, _| result.push(cnum));
 540         result
 541     }
 542
 543     fn used_libraries(&self) -> Vec<NativeLibrary>
 544     {
 545         self.get_used_libraries().borrow().clone()
 546     }
 547
 548     fn used_link_args(&self) -> Vec<String>
 549     {
 550         self.get_used_link_args().borrow().clone()
 551     }
 552
 553     fn metadata_filename(&self) -> &str
 554     {
 555         locator::METADATA_FILENAME
 556     }
 557
 558     fn metadata_section_name(&self, target: &Target) -> &str
 559     {
 560         locator::meta_section_name(target)
 561     }
 562
 563     fn used_crates(&self, prefer: LinkagePreference) -> Vec<(CrateNum, LibSource)>
 564     {
 565         self.do_get_used_crates(prefer)
 566     }
 567
 568     fn used_crate_source(&self, cnum: CrateNum) -> CrateSource
 569     {
 570         self.get_crate_data(cnum).source.clone()
 571     }
 572
 573     fn extern_mod_stmt_cnum(&self, emod_id: ast::NodeId) -> Option<CrateNum>
 574     {
 575         self.do_extern_mod_stmt_cnum(emod_id)
 576     }
 577
 578     fn encode_metadata<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>,
 579                            reexports: &def::ExportMap,
 580                            link_meta: &LinkMeta,
 581                            reachable: &NodeSet) -> Vec<u8>
 582     {
 583         encoder::encode_metadata(tcx, self, reexports, link_meta, reachable)
 584     }
 585
 586     fn metadata_encoding_version(&self) -> &[u8]
 587     {
 588         schema::METADATA_HEADER
 589     }
 590
 591     /// Returns a map from a sufficiently visible external item (i.e. an external item that is
 592     /// visible from at least one local module) to a sufficiently visible parent (considering
 593     /// modules that re-export the external item to be parents).
 594     fn visible_parent_map<'a>(&'a self) -> ::std::cell::RefMut<'a, DefIdMap<DefId>> {
 595         let mut visible_parent_map = self.visible_parent_map.borrow_mut();
 596         if !visible_parent_map.is_empty() { return visible_parent_map; }
 597
 598         use std::collections::vec_deque::VecDeque;
 599         use std::collections::hash_map::Entry;
 600         for cnum in (1 .. self.next_crate_num().as_usize()).map(CrateNum::new) {
 601             let cdata = self.get_crate_data(cnum);
 602
 603             match cdata.extern_crate.get() {
 604                 // Ignore crates without a corresponding local `extern crate` item.
 605                 Some(extern_crate) if !extern_crate.direct => continue,
 606                 _ => {},
 607             }
 608
 609             let mut bfs_queue = &mut VecDeque::new();
 610             let mut add_child = |bfs_queue: &mut VecDeque<_>, child: def::Export, parent: DefId| {
 611                 let child = child.def.def_id();
 612
 613                 if self.visibility(child) != ty::Visibility::Public {
 614                     return;
 615                 }
 616
 617                 match visible_parent_map.entry(child) {
 618                     Entry::Occupied(mut entry) => {
 619                         // If `child` is defined in crate `cnum`, ensure
 620                         // that it is mapped to a parent in `cnum`.
 621                         if child.krate == cnum && entry.get().krate != cnum {
 622                             entry.insert(parent);
 623                         }
 624                     }
 625                     Entry::Vacant(entry) => {
 626                         entry.insert(parent);
 627                         bfs_queue.push_back(child);
 628                     }
 629                 }
 630             };
 631
 632             bfs_queue.push_back(DefId {
 633                 krate: cnum,
 634                 index: CRATE_DEF_INDEX
 635             });
 636             while let Some(def) = bfs_queue.pop_front() {
 637                 for child in self.item_children(def) {
 638                     add_child(bfs_queue, child, def);
 639                 }
 640             }
 641         }
 642
 643         visible_parent_map
 644     }
 645 }