src/librustdoc/formats/cache.rs

   1 use std::mem;
   2
   3 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
   4 use rustc_hir::def_id::{CrateNum, DefId};
   5 use rustc_middle::ty::{self, TyCtxt};
   6 use rustc_span::Symbol;
   7
   8 use crate::clean::{self, types::ExternalLocation, ExternalCrate, ItemId, PrimitiveType};
   9 use crate::core::DocContext;
  10 use crate::fold::DocFolder;
  11 use crate::formats::item_type::ItemType;
  12 use crate::formats::Impl;
  13 use crate::html::format::join_with_double_colon;
  14 use crate::html::markdown::short_markdown_summary;
  15 use crate::html::render::search_index::get_function_type_for_search;
  16 use crate::html::render::IndexItem;
  17 use crate::visit_lib::RustdocEffectiveVisibilities;
  18
  19 /// This cache is used to store information about the [`clean::Crate`] being
  20 /// rendered in order to provide more useful documentation. This contains
  21 /// information like all implementors of a trait, all traits a type implements,
  22 /// documentation for all known traits, etc.
  23 ///
  24 /// This structure purposefully does not implement `Clone` because it's intended
  25 /// to be a fairly large and expensive structure to clone. Instead this adheres
  26 /// to `Send` so it may be stored in an `Arc` instance and shared among the various
  27 /// rendering threads.
  28 #[derive(Default)]
  29 pub(crate) struct Cache {
  30     /// Maps a type ID to all known implementations for that type. This is only
  31     /// recognized for intra-crate [`clean::Type::Path`]s, and is used to print
  32     /// out extra documentation on the page of an enum/struct.
  33     ///
  34     /// The values of the map are a list of implementations and documentation
  35     /// found on that implementation.
  36     pub(crate) impls: FxHashMap<DefId, Vec<Impl>>,
  37
  38     /// Maintains a mapping of local crate `DefId`s to the fully qualified name
  39     /// and "short type description" of that node. This is used when generating
  40     /// URLs when a type is being linked to. External paths are not located in
  41     /// this map because the `External` type itself has all the information
  42     /// necessary.
  43     pub(crate) paths: FxHashMap<DefId, (Vec<Symbol>, ItemType)>,
  44
  45     /// Similar to `paths`, but only holds external paths. This is only used for
  46     /// generating explicit hyperlinks to other crates.
  47     pub(crate) external_paths: FxHashMap<DefId, (Vec<Symbol>, ItemType)>,
  48
  49     /// Maps local `DefId`s of exported types to fully qualified paths.
  50     /// Unlike 'paths', this mapping ignores any renames that occur
  51     /// due to 'use' statements.
  52     ///
  53     /// This map is used when writing out the special 'implementors'
  54     /// javascript file. By using the exact path that the type
  55     /// is declared with, we ensure that each path will be identical
  56     /// to the path used if the corresponding type is inlined. By
  57     /// doing this, we can detect duplicate impls on a trait page, and only display
  58     /// the impl for the inlined type.
  59     pub(crate) exact_paths: FxHashMap<DefId, Vec<Symbol>>,
  60
  61     /// This map contains information about all known traits of this crate.
  62     /// Implementations of a crate should inherit the documentation of the
  63     /// parent trait if no extra documentation is specified, and default methods
  64     /// should show up in documentation about trait implementations.
  65     pub(crate) traits: FxHashMap<DefId, clean::Trait>,
  66
  67     /// When rendering traits, it's often useful to be able to list all
  68     /// implementors of the trait, and this mapping is exactly, that: a mapping
  69     /// of trait ids to the list of known implementors of the trait
  70     pub(crate) implementors: FxHashMap<DefId, Vec<Impl>>,
  71
  72     /// Cache of where external crate documentation can be found.
  73     pub(crate) extern_locations: FxHashMap<CrateNum, ExternalLocation>,
  74
  75     /// Cache of where documentation for primitives can be found.
  76     pub(crate) primitive_locations: FxHashMap<clean::PrimitiveType, DefId>,
  77
  78     // Note that external items for which `doc(hidden)` applies to are shown as
  79     // non-reachable while local items aren't. This is because we're reusing
  80     // the effective visibilities from the privacy check pass.
  81     pub(crate) effective_visibilities: RustdocEffectiveVisibilities,
  82
  83     /// The version of the crate being documented, if given from the `--crate-version` flag.
  84     pub(crate) crate_version: Option<String>,
  85
  86     /// Whether to document private items.
  87     /// This is stored in `Cache` so it doesn't need to be passed through all rustdoc functions.
  88     pub(crate) document_private: bool,
  89
  90     /// Crates marked with [`#[doc(masked)]`][doc_masked].
  91     ///
  92     /// [doc_masked]: https://doc.rust-lang.org/nightly/unstable-book/language-features/doc-masked.html
  93     pub(crate) masked_crates: FxHashSet<CrateNum>,
  94
  95     // Private fields only used when initially crawling a crate to build a cache
  96     stack: Vec<Symbol>,
  97     parent_stack: Vec<ParentStackItem>,
  98     stripped_mod: bool,
  99
 100     pub(crate) search_index: Vec<IndexItem>,
 101
 102     // In rare case where a structure is defined in one module but implemented
 103     // in another, if the implementing module is parsed before defining module,
 104     // then the fully qualified name of the structure isn't presented in `paths`
 105     // yet when its implementation methods are being indexed. Caches such methods
 106     // and their parent id here and indexes them at the end of crate parsing.
 107     pub(crate) orphan_impl_items: Vec<OrphanImplItem>,
 108
 109     // Similarly to `orphan_impl_items`, sometimes trait impls are picked up
 110     // even though the trait itself is not exported. This can happen if a trait
 111     // was defined in function/expression scope, since the impl will be picked
 112     // up by `collect-trait-impls` but the trait won't be scraped out in the HIR
 113     // crawl. In order to prevent crashes when looking for notable traits or
 114     // when gathering trait documentation on a type, hold impls here while
 115     // folding and add them to the cache later on if we find the trait.
 116     orphan_trait_impls: Vec<(DefId, FxHashSet<DefId>, Impl)>,
 117
 118     /// All intra-doc links resolved so far.
 119     ///
 120     /// Links are indexed by the DefId of the item they document.
 121     pub(crate) intra_doc_links: FxHashMap<ItemId, Vec<clean::ItemLink>>,
 122     /// Cfg that have been hidden via #![doc(cfg_hide(...))]
 123     pub(crate) hidden_cfg: FxHashSet<clean::cfg::Cfg>,
 124 }
 125
 126 /// This struct is used to wrap the `cache` and `tcx` in order to run `DocFolder`.
 127 struct CacheBuilder<'a, 'tcx> {
 128     cache: &'a mut Cache,
 129     /// This field is used to prevent duplicated impl blocks.
 130     impl_ids: FxHashMap<DefId, FxHashSet<DefId>>,
 131     tcx: TyCtxt<'tcx>,
 132 }
 133
 134 impl Cache {
 135     pub(crate) fn new(document_private: bool) -> Self {
 136         Cache { document_private, ..Cache::default() }
 137     }
 138
 139     /// Populates the `Cache` with more data. The returned `Crate` will be missing some data that was
 140     /// in `krate` due to the data being moved into the `Cache`.
 141     pub(crate) fn populate(cx: &mut DocContext<'_>, mut krate: clean::Crate) -> clean::Crate {
 142         let tcx = cx.tcx;
 143
 144         // Crawl the crate to build various caches used for the output
 145         debug!(?cx.cache.crate_version);
 146         cx.cache.traits = krate.external_traits.take();
 147
 148         // Cache where all our extern crates are located
 149         // FIXME: this part is specific to HTML so it'd be nice to remove it from the common code
 150         for &crate_num in cx.tcx.crates(()) {
 151             let e = ExternalCrate { crate_num };
 152
 153             let name = e.name(tcx);
 154             let render_options = &cx.render_options;
 155             let extern_url = render_options.extern_html_root_urls.get(name.as_str()).map(|u| &**u);
 156             let extern_url_takes_precedence = render_options.extern_html_root_takes_precedence;
 157             let dst = &render_options.output;
 158             let location = e.location(extern_url, extern_url_takes_precedence, dst, tcx);
 159             cx.cache.extern_locations.insert(e.crate_num, location);
 160             cx.cache.external_paths.insert(e.def_id(), (vec![name], ItemType::Module));
 161         }
 162
 163         // FIXME: avoid this clone (requires implementing Default manually)
 164         cx.cache.primitive_locations = PrimitiveType::primitive_locations(tcx).clone();
 165         for (prim, &def_id) in &cx.cache.primitive_locations {
 166             let crate_name = tcx.crate_name(def_id.krate);
 167             // Recall that we only allow primitive modules to be at the root-level of the crate.
 168             // If that restriction is ever lifted, this will have to include the relative paths instead.
 169             cx.cache
 170                 .external_paths
 171                 .insert(def_id, (vec![crate_name, prim.as_sym()], ItemType::Primitive));
 172         }
 173
 174         let (krate, mut impl_ids) = {
 175             let mut cache_builder =
 176                 CacheBuilder { tcx, cache: &mut cx.cache, impl_ids: FxHashMap::default() };
 177             krate = cache_builder.fold_crate(krate);
 178             (krate, cache_builder.impl_ids)
 179         };
 180
 181         for (trait_did, dids, impl_) in cx.cache.orphan_trait_impls.drain(..) {
 182             if cx.cache.traits.contains_key(&trait_did) {
 183                 for did in dids {
 184                     if impl_ids.entry(did).or_default().insert(impl_.def_id()) {
 185                         cx.cache.impls.entry(did).or_default().push(impl_.clone());
 186                     }
 187                 }
 188             }
 189         }
 190
 191         krate
 192     }
 193 }
 194
 195 impl<'a, 'tcx> DocFolder for CacheBuilder<'a, 'tcx> {
 196     fn fold_item(&mut self, item: clean::Item) -> Option<clean::Item> {
 197         if item.item_id.is_local() {
 198             debug!("folding {} \"{:?}\", id {:?}", item.type_(), item.name, item.item_id);
 199         }
 200
 201         // If this is a stripped module,
 202         // we don't want it or its children in the search index.
 203         let orig_stripped_mod = match *item.kind {
 204             clean::StrippedItem(box clean::ModuleItem(..)) => {
 205                 mem::replace(&mut self.cache.stripped_mod, true)
 206             }
 207             _ => self.cache.stripped_mod,
 208         };
 209
 210         // If the impl is from a masked crate or references something from a
 211         // masked crate then remove it completely.
 212         if let clean::ImplItem(ref i) = *item.kind {
 213             if self.cache.masked_crates.contains(&item.item_id.krate())
 214                 || i.trait_
 215                     .as_ref()
 216                     .map_or(false, |t| self.cache.masked_crates.contains(&t.def_id().krate))
 217                 || i.for_
 218                     .def_id(self.cache)
 219                     .map_or(false, |d| self.cache.masked_crates.contains(&d.krate))
 220             {
 221                 return None;
 222             }
 223         }
 224
 225         // Propagate a trait method's documentation to all implementors of the
 226         // trait.
 227         if let clean::TraitItem(ref t) = *item.kind {
 228             self.cache.traits.entry(item.item_id.expect_def_id()).or_insert_with(|| (**t).clone());
 229         }
 230
 231         // Collect all the implementors of traits.
 232         if let clean::ImplItem(ref i) = *item.kind {
 233             if let Some(trait_) = &i.trait_ {
 234                 if !i.kind.is_blanket() {
 235                     self.cache
 236                         .implementors
 237                         .entry(trait_.def_id())
 238                         .or_default()
 239                         .push(Impl { impl_item: item.clone() });
 240                 }
 241             }
 242         }
 243
 244         // Index this method for searching later on.
 245         if let Some(s) = item.name.or_else(|| {
 246             if item.is_stripped() {
 247                 None
 248             } else if let clean::ImportItem(ref i) = *item.kind &&
 249                 let clean::ImportKind::Simple(s) = i.kind {
 250                 Some(s)
 251             } else {
 252                 None
 253             }
 254         }) {
 255             let (parent, is_inherent_impl_item) = match *item.kind {
 256                 clean::StrippedItem(..) => ((None, None), false),
 257                 clean::AssocConstItem(..) | clean::AssocTypeItem(..)
 258                     if self
 259                         .cache
 260                         .parent_stack
 261                         .last()
 262                         .map_or(false, |parent| parent.is_trait_impl()) =>
 263                 {
 264                     // skip associated items in trait impls
 265                     ((None, None), false)
 266                 }
 267                 clean::TyMethodItem(..)
 268                 | clean::TyAssocConstItem(..)
 269                 | clean::TyAssocTypeItem(..)
 270                 | clean::StructFieldItem(..)
 271                 | clean::VariantItem(..) => (
 272                     (
 273                         Some(
 274                             self.cache
 275                                 .parent_stack
 276                                 .last()
 277                                 .expect("parent_stack is empty")
 278                                 .item_id()
 279                                 .expect_def_id(),
 280                         ),
 281                         Some(&self.cache.stack[..self.cache.stack.len() - 1]),
 282                     ),
 283                     false,
 284                 ),
 285                 clean::MethodItem(..) | clean::AssocConstItem(..) | clean::AssocTypeItem(..) => {
 286                     if self.cache.parent_stack.is_empty() {
 287                         ((None, None), false)
 288                     } else {
 289                         let last = self.cache.parent_stack.last().expect("parent_stack is empty 2");
 290                         let did = match &*last {
 291                             ParentStackItem::Impl { for_, .. } => for_.def_id(&self.cache),
 292                             ParentStackItem::Type(item_id) => item_id.as_def_id(),
 293                         };
 294                         let path = match did.and_then(|did| self.cache.paths.get(&did)) {
 295                             // The current stack not necessarily has correlation
 296                             // for where the type was defined. On the other
 297                             // hand, `paths` always has the right
 298                             // information if present.
 299                             Some((fqp, _)) => Some(&fqp[..fqp.len() - 1]),
 300                             None => None,
 301                         };
 302                         ((did, path), true)
 303                     }
 304                 }
 305                 _ => ((None, Some(&*self.cache.stack)), false),
 306             };
 307
 308             match parent {
 309                 (parent, Some(path)) if is_inherent_impl_item || !self.cache.stripped_mod => {
 310                     debug_assert!(!item.is_stripped());
 311
 312                     // A crate has a module at its root, containing all items,
 313                     // which should not be indexed. The crate-item itself is
 314                     // inserted later on when serializing the search-index.
 315                     if item.item_id.as_def_id().map_or(false, |idx| !idx.is_crate_root()) {
 316                         let desc = item.doc_value().map_or_else(String::new, |x| {
 317                             short_markdown_summary(x.as_str(), &item.link_names(self.cache))
 318                         });
 319                         let ty = item.type_();
 320                         if ty != ItemType::StructField
 321                             || u16::from_str_radix(s.as_str(), 10).is_err()
 322                         {
 323                             // In case this is a field from a tuple struct, we don't add it into
 324                             // the search index because its name is something like "0", which is
 325                             // not useful for rustdoc search.
 326                             self.cache.search_index.push(IndexItem {
 327                                 ty,
 328                                 name: s,
 329                                 path: join_with_double_colon(path),
 330                                 desc,
 331                                 parent,
 332                                 parent_idx: None,
 333                                 search_type: get_function_type_for_search(
 334                                     &item,
 335                                     self.tcx,
 336                                     clean_impl_generics(self.cache.parent_stack.last()).as_ref(),
 337                                     self.cache,
 338                                 ),
 339                                 aliases: item.attrs.get_doc_aliases(),
 340                             });
 341                         }
 342                     }
 343                 }
 344                 (Some(parent), None) if is_inherent_impl_item => {
 345                     // We have a parent, but we don't know where they're
 346                     // defined yet. Wait for later to index this item.
 347                     let impl_generics = clean_impl_generics(self.cache.parent_stack.last());
 348                     self.cache.orphan_impl_items.push(OrphanImplItem {
 349                         parent,
 350                         item: item.clone(),
 351                         impl_generics,
 352                     });
 353                 }
 354                 _ => {}
 355             }
 356         }
 357
 358         // Keep track of the fully qualified path for this item.
 359         let pushed = match item.name {
 360             Some(n) if !n.is_empty() => {
 361                 self.cache.stack.push(n);
 362                 true
 363             }
 364             _ => false,
 365         };
 366
 367         match *item.kind {
 368             clean::StructItem(..)
 369             | clean::EnumItem(..)
 370             | clean::TypedefItem(..)
 371             | clean::TraitItem(..)
 372             | clean::TraitAliasItem(..)
 373             | clean::FunctionItem(..)
 374             | clean::ModuleItem(..)
 375             | clean::ForeignFunctionItem(..)
 376             | clean::ForeignStaticItem(..)
 377             | clean::ConstantItem(..)
 378             | clean::StaticItem(..)
 379             | clean::UnionItem(..)
 380             | clean::ForeignTypeItem
 381             | clean::MacroItem(..)
 382             | clean::ProcMacroItem(..)
 383             | clean::VariantItem(..) => {
 384                 if !self.cache.stripped_mod {
 385                     // Re-exported items mean that the same id can show up twice
 386                     // in the rustdoc ast that we're looking at. We know,
 387                     // however, that a re-exported item doesn't show up in the
 388                     // `public_items` map, so we can skip inserting into the
 389                     // paths map if there was already an entry present and we're
 390                     // not a public item.
 391                     if !self.cache.paths.contains_key(&item.item_id.expect_def_id())
 392                         || self
 393                             .cache
 394                             .effective_visibilities
 395                             .is_directly_public(self.tcx, item.item_id.expect_def_id())
 396                     {
 397                         self.cache.paths.insert(
 398                             item.item_id.expect_def_id(),
 399                             (self.cache.stack.clone(), item.type_()),
 400                         );
 401                     }
 402                 }
 403             }
 404             clean::PrimitiveItem(..) => {
 405                 self.cache
 406                     .paths
 407                     .insert(item.item_id.expect_def_id(), (self.cache.stack.clone(), item.type_()));
 408             }
 409
 410             clean::ExternCrateItem { .. }
 411             | clean::ImportItem(..)
 412             | clean::OpaqueTyItem(..)
 413             | clean::ImplItem(..)
 414             | clean::TyMethodItem(..)
 415             | clean::MethodItem(..)
 416             | clean::StructFieldItem(..)
 417             | clean::TyAssocConstItem(..)
 418             | clean::AssocConstItem(..)
 419             | clean::TyAssocTypeItem(..)
 420             | clean::AssocTypeItem(..)
 421             | clean::StrippedItem(..)
 422             | clean::KeywordItem => {
 423                 // FIXME: Do these need handling?
 424                 // The person writing this comment doesn't know.
 425                 // So would rather leave them to an expert,
 426                 // as at least the list is better than `_ => {}`.
 427             }
 428         }
 429
 430         // Maintain the parent stack.
 431         let (item, parent_pushed) = match *item.kind {
 432             clean::TraitItem(..)
 433             | clean::EnumItem(..)
 434             | clean::ForeignTypeItem
 435             | clean::StructItem(..)
 436             | clean::UnionItem(..)
 437             | clean::VariantItem(..)
 438             | clean::ImplItem(..) => {
 439                 self.cache.parent_stack.push(ParentStackItem::new(&item));
 440                 (self.fold_item_recur(item), true)
 441             }
 442             _ => (self.fold_item_recur(item), false),
 443         };
 444
 445         // Once we've recursively found all the generics, hoard off all the
 446         // implementations elsewhere.
 447         let ret = if let clean::Item { kind: box clean::ImplItem(ref i), .. } = item {
 448             // Figure out the id of this impl. This may map to a
 449             // primitive rather than always to a struct/enum.
 450             // Note: matching twice to restrict the lifetime of the `i` borrow.
 451             let mut dids = FxHashSet::default();
 452             match i.for_ {
 453                 clean::Type::Path { ref path }
 454                 | clean::BorrowedRef { type_: box clean::Type::Path { ref path }, .. } => {
 455                     dids.insert(path.def_id());
 456                     if let Some(generics) = path.generics() &&
 457                         let ty::Adt(adt, _) = self.tcx.type_of(path.def_id()).kind() &&
 458                         adt.is_fundamental() {
 459                         for ty in generics {
 460                             if let Some(did) = ty.def_id(self.cache) {
 461                                 dids.insert(did);
 462                             }
 463                         }
 464                     }
 465                 }
 466                 clean::DynTrait(ref bounds, _)
 467                 | clean::BorrowedRef { type_: box clean::DynTrait(ref bounds, _), .. } => {
 468                     dids.insert(bounds[0].trait_.def_id());
 469                 }
 470                 ref t => {
 471                     let did = t
 472                         .primitive_type()
 473                         .and_then(|t| self.cache.primitive_locations.get(&t).cloned());
 474
 475                     if let Some(did) = did {
 476                         dids.insert(did);
 477                     }
 478                 }
 479             }
 480
 481             if let Some(generics) = i.trait_.as_ref().and_then(|t| t.generics()) {
 482                 for bound in generics {
 483                     if let Some(did) = bound.def_id(self.cache) {
 484                         dids.insert(did);
 485                     }
 486                 }
 487             }
 488             let impl_item = Impl { impl_item: item };
 489             if impl_item.trait_did().map_or(true, |d| self.cache.traits.contains_key(&d)) {
 490                 for did in dids {
 491                     if self.impl_ids.entry(did).or_default().insert(impl_item.def_id()) {
 492                         self.cache
 493                             .impls
 494                             .entry(did)
 495                             .or_insert_with(Vec::new)
 496                             .push(impl_item.clone());
 497                     }
 498                 }
 499             } else {
 500                 let trait_did = impl_item.trait_did().expect("no trait did");
 501                 self.cache.orphan_trait_impls.push((trait_did, dids, impl_item));
 502             }
 503             None
 504         } else {
 505             Some(item)
 506         };
 507
 508         if pushed {
 509             self.cache.stack.pop().expect("stack already empty");
 510         }
 511         if parent_pushed {
 512             self.cache.parent_stack.pop().expect("parent stack already empty");
 513         }
 514         self.cache.stripped_mod = orig_stripped_mod;
 515         ret
 516     }
 517 }
 518
 519 pub(crate) struct OrphanImplItem {
 520     pub(crate) parent: DefId,
 521     pub(crate) item: clean::Item,
 522     pub(crate) impl_generics: Option<(clean::Type, clean::Generics)>,
 523 }
 524
 525 /// Information about trait and type parents is tracked while traversing the item tree to build
 526 /// the cache.
 527 ///
 528 /// We don't just store `Item` in there, because `Item` contains the list of children being
 529 /// traversed and it would be wasteful to clone all that. We also need the item id, so just
 530 /// storing `ItemKind` won't work, either.
 531 enum ParentStackItem {
 532     Impl {
 533         for_: clean::Type,
 534         trait_: Option<clean::Path>,
 535         generics: clean::Generics,
 536         kind: clean::ImplKind,
 537         item_id: ItemId,
 538     },
 539     Type(ItemId),
 540 }
 541
 542 impl ParentStackItem {
 543     fn new(item: &clean::Item) -> Self {
 544         match &*item.kind {
 545             clean::ItemKind::ImplItem(box clean::Impl { for_, trait_, generics, kind, .. }) => {
 546                 ParentStackItem::Impl {
 547                     for_: for_.clone(),
 548                     trait_: trait_.clone(),
 549                     generics: generics.clone(),
 550                     kind: kind.clone(),
 551                     item_id: item.item_id,
 552                 }
 553             }
 554             _ => ParentStackItem::Type(item.item_id),
 555         }
 556     }
 557     fn is_trait_impl(&self) -> bool {
 558         matches!(self, ParentStackItem::Impl { trait_: Some(..), .. })
 559     }
 560     fn item_id(&self) -> ItemId {
 561         match self {
 562             ParentStackItem::Impl { item_id, .. } => *item_id,
 563             ParentStackItem::Type(item_id) => *item_id,
 564         }
 565     }
 566 }
 567
 568 fn clean_impl_generics(item: Option<&ParentStackItem>) -> Option<(clean::Type, clean::Generics)> {
 569     if let Some(ParentStackItem::Impl { for_, generics, kind: clean::ImplKind::Normal, .. }) = item
 570     {
 571         Some((for_.clone(), generics.clone()))
 572     } else {
 573         None
 574     }
 575 }