src/librustdoc/formats/cache.rs

   1 use std::collections::BTreeMap;
   2 use std::mem;
   3 use std::path::Path;
   4
   5 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
   6 use rustc_hir::def_id::{CrateNum, DefId, CRATE_DEF_INDEX};
   7 use rustc_middle::middle::privacy::AccessLevels;
   8 use rustc_middle::ty::TyCtxt;
   9 use rustc_span::symbol::sym;
  10
  11 use crate::clean::{self, GetDefId, ItemId};
  12 use crate::fold::DocFolder;
  13 use crate::formats::item_type::ItemType;
  14 use crate::formats::Impl;
  15 use crate::html::markdown::short_markdown_summary;
  16 use crate::html::render::cache::{get_index_search_type, ExternalLocation};
  17 use crate::html::render::IndexItem;
  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 a `Arc` instance and shared among the various
  27 /// rendering threads.
  28 #[derive(Default)]
  29 crate struct Cache {
  30     /// Maps a type ID to all known implementations for that type. This is only
  31     /// recognized for intra-crate `ResolvedPath` types, 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     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     crate paths: FxHashMap<DefId, (Vec<String>, ItemType)>,
  44
  45     /// Similar to `paths`, but only holds external paths. This is only used for
  46     /// generating explicit hyperlinks to other crates.
  47     crate external_paths: FxHashMap<DefId, (Vec<String>, 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     crate exact_paths: FxHashMap<DefId, Vec<String>>,
  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     crate traits: FxHashMap<DefId, clean::TraitWithExtraInfo>,
  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     crate implementors: FxHashMap<DefId, Vec<Impl>>,
  71
  72     /// Cache of where external crate documentation can be found.
  73     crate extern_locations: FxHashMap<CrateNum, ExternalLocation>,
  74
  75     /// Cache of where documentation for primitives can be found.
  76     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 access levels from the privacy check pass.
  81     crate access_levels: AccessLevels<DefId>,
  82
  83     /// The version of the crate being documented, if given from the `--crate-version` flag.
  84     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     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     crate masked_crates: FxHashSet<CrateNum>,
  94
  95     // Private fields only used when initially crawling a crate to build a cache
  96     stack: Vec<String>,
  97     parent_stack: Vec<DefId>,
  98     parent_is_trait_impl: bool,
  99     stripped_mod: bool,
 100
 101     crate search_index: Vec<IndexItem>,
 102     crate deref_trait_did: Option<DefId>,
 103     crate deref_mut_trait_did: Option<DefId>,
 104     crate owned_box_did: Option<DefId>,
 105
 106     // In rare case where a structure is defined in one module but implemented
 107     // in another, if the implementing module is parsed before defining module,
 108     // then the fully qualified name of the structure isn't presented in `paths`
 109     // yet when its implementation methods are being indexed. Caches such methods
 110     // and their parent id here and indexes them at the end of crate parsing.
 111     crate orphan_impl_items: Vec<(DefId, clean::Item)>,
 112
 113     // Similarly to `orphan_impl_items`, sometimes trait impls are picked up
 114     // even though the trait itself is not exported. This can happen if a trait
 115     // was defined in function/expression scope, since the impl will be picked
 116     // up by `collect-trait-impls` but the trait won't be scraped out in the HIR
 117     // crawl. In order to prevent crashes when looking for notable traits or
 118     // when gathering trait documentation on a type, hold impls here while
 119     // folding and add them to the cache later on if we find the trait.
 120     orphan_trait_impls: Vec<(DefId, FxHashSet<DefId>, Impl)>,
 121
 122     /// All intra-doc links resolved so far.
 123     ///
 124     /// Links are indexed by the DefId of the item they document.
 125     crate intra_doc_links: FxHashMap<ItemId, Vec<clean::ItemLink>>,
 126 }
 127
 128 /// This struct is used to wrap the `cache` and `tcx` in order to run `DocFolder`.
 129 struct CacheBuilder<'a, 'tcx> {
 130     cache: &'a mut Cache,
 131     tcx: TyCtxt<'tcx>,
 132 }
 133
 134 impl Cache {
 135     crate fn new(access_levels: AccessLevels<DefId>, document_private: bool) -> Self {
 136         Cache { access_levels, 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     crate fn populate(
 142         &mut self,
 143         mut krate: clean::Crate,
 144         tcx: TyCtxt<'_>,
 145         extern_html_root_urls: &BTreeMap<String, String>,
 146         dst: &Path,
 147     ) -> clean::Crate {
 148         // Crawl the crate to build various caches used for the output
 149         debug!(?self.crate_version);
 150         self.traits = krate.external_traits.take();
 151
 152         // Cache where all our extern crates are located
 153         // FIXME: this part is specific to HTML so it'd be nice to remove it from the common code
 154         for &e in &krate.externs {
 155             let name = e.name(tcx);
 156             let extern_url = extern_html_root_urls.get(&*name.as_str()).map(|u| &**u);
 157             self.extern_locations.insert(e.crate_num, e.location(extern_url, &dst, tcx));
 158             self.external_paths.insert(e.def_id(), (vec![name.to_string()], ItemType::Module));
 159         }
 160
 161         // Cache where all known primitives have their documentation located.
 162         //
 163         // Favor linking to as local extern as possible, so iterate all crates in
 164         // reverse topological order.
 165         for &e in krate.externs.iter().rev() {
 166             for &(def_id, prim) in &e.primitives(tcx) {
 167                 self.primitive_locations.insert(prim, def_id);
 168             }
 169         }
 170         for &(def_id, prim) in &krate.primitives {
 171             self.primitive_locations.insert(prim, def_id);
 172         }
 173
 174         krate = CacheBuilder { tcx, cache: self }.fold_crate(krate);
 175
 176         for (trait_did, dids, impl_) in self.orphan_trait_impls.drain(..) {
 177             if self.traits.contains_key(&trait_did) {
 178                 for did in dids {
 179                     self.impls.entry(did).or_default().push(impl_.clone());
 180                 }
 181             }
 182         }
 183
 184         krate
 185     }
 186 }
 187
 188 impl<'a, 'tcx> DocFolder for CacheBuilder<'a, 'tcx> {
 189     fn fold_item(&mut self, item: clean::Item) -> Option<clean::Item> {
 190         if item.def_id.is_local() {
 191             debug!("folding {} \"{:?}\", id {:?}", item.type_(), item.name, item.def_id);
 192         }
 193
 194         // If this is a stripped module,
 195         // we don't want it or its children in the search index.
 196         let orig_stripped_mod = match *item.kind {
 197             clean::StrippedItem(box clean::ModuleItem(..)) => {
 198                 mem::replace(&mut self.cache.stripped_mod, true)
 199             }
 200             _ => self.cache.stripped_mod,
 201         };
 202
 203         // If the impl is from a masked crate or references something from a
 204         // masked crate then remove it completely.
 205         if let clean::ImplItem(ref i) = *item.kind {
 206             if self.cache.masked_crates.contains(&item.def_id.krate())
 207                 || i.trait_.def_id().map_or(false, |d| self.cache.masked_crates.contains(&d.krate))
 208                 || i.for_.def_id().map_or(false, |d| self.cache.masked_crates.contains(&d.krate))
 209             {
 210                 return None;
 211             }
 212         }
 213
 214         // Propagate a trait method's documentation to all implementors of the
 215         // trait.
 216         if let clean::TraitItem(ref t) = *item.kind {
 217             self.cache.traits.entry(item.def_id.expect_def_id()).or_insert_with(|| {
 218                 clean::TraitWithExtraInfo {
 219                     trait_: t.clone(),
 220                     is_notable: item.attrs.has_doc_flag(sym::notable_trait),
 221                 }
 222             });
 223         }
 224
 225         // Collect all the implementors of traits.
 226         if let clean::ImplItem(ref i) = *item.kind {
 227             if let Some(did) = i.trait_.def_id() {
 228                 if i.blanket_impl.is_none() {
 229                     self.cache
 230                         .implementors
 231                         .entry(did.into())
 232                         .or_default()
 233                         .push(Impl { impl_item: item.clone() });
 234                 }
 235             }
 236         }
 237
 238         // Index this method for searching later on.
 239         if let Some(ref s) = item.name {
 240             let (parent, is_inherent_impl_item) = match *item.kind {
 241                 clean::StrippedItem(..) => ((None, None), false),
 242                 clean::AssocConstItem(..) | clean::TypedefItem(_, true)
 243                     if self.cache.parent_is_trait_impl =>
 244                 {
 245                     // skip associated items in trait impls
 246                     ((None, None), false)
 247                 }
 248                 clean::AssocTypeItem(..)
 249                 | clean::TyMethodItem(..)
 250                 | clean::StructFieldItem(..)
 251                 | clean::VariantItem(..) => (
 252                     (
 253                         Some(*self.cache.parent_stack.last().expect("parent_stack is empty")),
 254                         Some(&self.cache.stack[..self.cache.stack.len() - 1]),
 255                     ),
 256                     false,
 257                 ),
 258                 clean::MethodItem(..) | clean::AssocConstItem(..) => {
 259                     if self.cache.parent_stack.is_empty() {
 260                         ((None, None), false)
 261                     } else {
 262                         let last = self.cache.parent_stack.last().expect("parent_stack is empty 2");
 263                         let did = *last;
 264                         let path = match self.cache.paths.get(&did) {
 265                             // The current stack not necessarily has correlation
 266                             // for where the type was defined. On the other
 267                             // hand, `paths` always has the right
 268                             // information if present.
 269                             Some(&(
 270                                 ref fqp,
 271                                 ItemType::Trait
 272                                 | ItemType::Struct
 273                                 | ItemType::Union
 274                                 | ItemType::Enum,
 275                             )) => Some(&fqp[..fqp.len() - 1]),
 276                             Some(..) => Some(&*self.cache.stack),
 277                             None => None,
 278                         };
 279                         ((Some(*last), path), true)
 280                     }
 281                 }
 282                 _ => ((None, Some(&*self.cache.stack)), false),
 283             };
 284
 285             match parent {
 286                 (parent, Some(path)) if is_inherent_impl_item || !self.cache.stripped_mod => {
 287                     debug_assert!(!item.is_stripped());
 288
 289                     // A crate has a module at its root, containing all items,
 290                     // which should not be indexed. The crate-item itself is
 291                     // inserted later on when serializing the search-index.
 292                     if item.def_id.index().map_or(false, |idx| idx != CRATE_DEF_INDEX) {
 293                         let desc = item.doc_value().map_or_else(String::new, |x| {
 294                             short_markdown_summary(&x.as_str(), &item.link_names(&self.cache))
 295                         });
 296                         self.cache.search_index.push(IndexItem {
 297                             ty: item.type_(),
 298                             name: s.to_string(),
 299                             path: path.join("::"),
 300                             desc,
 301                             parent,
 302                             parent_idx: None,
 303                             search_type: get_index_search_type(&item, self.tcx),
 304                             aliases: item.attrs.get_doc_aliases(),
 305                         });
 306                     }
 307                 }
 308                 (Some(parent), None) if is_inherent_impl_item => {
 309                     // We have a parent, but we don't know where they're
 310                     // defined yet. Wait for later to index this item.
 311                     self.cache.orphan_impl_items.push((parent, item.clone()));
 312                 }
 313                 _ => {}
 314             }
 315         }
 316
 317         // Keep track of the fully qualified path for this item.
 318         let pushed = match item.name {
 319             Some(n) if !n.is_empty() => {
 320                 self.cache.stack.push(n.to_string());
 321                 true
 322             }
 323             _ => false,
 324         };
 325
 326         match *item.kind {
 327             clean::StructItem(..)
 328             | clean::EnumItem(..)
 329             | clean::TypedefItem(..)
 330             | clean::TraitItem(..)
 331             | clean::TraitAliasItem(..)
 332             | clean::FunctionItem(..)
 333             | clean::ModuleItem(..)
 334             | clean::ForeignFunctionItem(..)
 335             | clean::ForeignStaticItem(..)
 336             | clean::ConstantItem(..)
 337             | clean::StaticItem(..)
 338             | clean::UnionItem(..)
 339             | clean::ForeignTypeItem
 340             | clean::MacroItem(..)
 341             | clean::ProcMacroItem(..)
 342             | clean::VariantItem(..) => {
 343                 if !self.cache.stripped_mod {
 344                     // Re-exported items mean that the same id can show up twice
 345                     // in the rustdoc ast that we're looking at. We know,
 346                     // however, that a re-exported item doesn't show up in the
 347                     // `public_items` map, so we can skip inserting into the
 348                     // paths map if there was already an entry present and we're
 349                     // not a public item.
 350                     if !self.cache.paths.contains_key(&item.def_id.expect_def_id())
 351                         || self.cache.access_levels.is_public(item.def_id.expect_def_id())
 352                     {
 353                         self.cache.paths.insert(
 354                             item.def_id.expect_def_id(),
 355                             (self.cache.stack.clone(), item.type_()),
 356                         );
 357                     }
 358                 }
 359             }
 360             clean::PrimitiveItem(..) => {
 361                 self.cache
 362                     .paths
 363                     .insert(item.def_id.expect_def_id(), (self.cache.stack.clone(), item.type_()));
 364             }
 365
 366             clean::ExternCrateItem { .. }
 367             | clean::ImportItem(..)
 368             | clean::OpaqueTyItem(..)
 369             | clean::ImplItem(..)
 370             | clean::TyMethodItem(..)
 371             | clean::MethodItem(..)
 372             | clean::StructFieldItem(..)
 373             | clean::AssocConstItem(..)
 374             | clean::AssocTypeItem(..)
 375             | clean::StrippedItem(..)
 376             | clean::KeywordItem(..) => {
 377                 // FIXME: Do these need handling?
 378                 // The person writing this comment doesn't know.
 379                 // So would rather leave them to an expert,
 380                 // as at least the list is better than `_ => {}`.
 381             }
 382         }
 383
 384         // Maintain the parent stack
 385         let orig_parent_is_trait_impl = self.cache.parent_is_trait_impl;
 386         let parent_pushed = match *item.kind {
 387             clean::TraitItem(..)
 388             | clean::EnumItem(..)
 389             | clean::ForeignTypeItem
 390             | clean::StructItem(..)
 391             | clean::UnionItem(..)
 392             | clean::VariantItem(..) => {
 393                 self.cache.parent_stack.push(item.def_id.expect_def_id());
 394                 self.cache.parent_is_trait_impl = false;
 395                 true
 396             }
 397             clean::ImplItem(ref i) => {
 398                 self.cache.parent_is_trait_impl = i.trait_.is_some();
 399                 match i.for_ {
 400                     clean::ResolvedPath { did, .. } => {
 401                         self.cache.parent_stack.push(did);
 402                         true
 403                     }
 404                     clean::DynTrait(ref bounds, _)
 405                     | clean::BorrowedRef { type_: box clean::DynTrait(ref bounds, _), .. } => {
 406                         if let Some(did) = bounds[0].trait_.def_id() {
 407                             self.cache.parent_stack.push(did);
 408                             true
 409                         } else {
 410                             false
 411                         }
 412                     }
 413                     ref t => {
 414                         let prim_did = t
 415                             .primitive_type()
 416                             .and_then(|t| self.cache.primitive_locations.get(&t).cloned());
 417                         match prim_did {
 418                             Some(did) => {
 419                                 self.cache.parent_stack.push(did);
 420                                 true
 421                             }
 422                             None => false,
 423                         }
 424                     }
 425                 }
 426             }
 427             _ => false,
 428         };
 429
 430         // Once we've recursively found all the generics, hoard off all the
 431         // implementations elsewhere.
 432         let item = self.fold_item_recur(item);
 433         let ret = if let clean::Item { kind: box clean::ImplItem(ref i), .. } = item {
 434             // Figure out the id of this impl. This may map to a
 435             // primitive rather than always to a struct/enum.
 436             // Note: matching twice to restrict the lifetime of the `i` borrow.
 437             let mut dids = FxHashSet::default();
 438             match i.for_ {
 439                 clean::ResolvedPath { did, .. }
 440                 | clean::BorrowedRef { type_: box clean::ResolvedPath { did, .. }, .. } => {
 441                     dids.insert(did);
 442                 }
 443                 clean::DynTrait(ref bounds, _)
 444                 | clean::BorrowedRef { type_: box clean::DynTrait(ref bounds, _), .. } => {
 445                     if let Some(did) = bounds[0].trait_.def_id() {
 446                         dids.insert(did);
 447                     }
 448                 }
 449                 ref t => {
 450                     let did = t
 451                         .primitive_type()
 452                         .and_then(|t| self.cache.primitive_locations.get(&t).cloned());
 453
 454                     if let Some(did) = did {
 455                         dids.insert(did);
 456                     }
 457                 }
 458             }
 459
 460             if let Some(generics) = i.trait_.as_ref().and_then(|t| t.generics()) {
 461                 for bound in generics {
 462                     if let Some(did) = bound.def_id() {
 463                         dids.insert(did);
 464                     }
 465                 }
 466             }
 467             let impl_item = Impl { impl_item: item };
 468             if impl_item.trait_did().map_or(true, |d| self.cache.traits.contains_key(&d)) {
 469                 for did in dids {
 470                     self.cache.impls.entry(did).or_insert(vec![]).push(impl_item.clone());
 471                 }
 472             } else {
 473                 let trait_did = impl_item.trait_did().expect("no trait did");
 474                 self.cache.orphan_trait_impls.push((trait_did, dids, impl_item));
 475             }
 476             None
 477         } else {
 478             Some(item)
 479         };
 480
 481         if pushed {
 482             self.cache.stack.pop().expect("stack already empty");
 483         }
 484         if parent_pushed {
 485             self.cache.parent_stack.pop().expect("parent stack already empty");
 486         }
 487         self.cache.stripped_mod = orig_stripped_mod;
 488         self.cache.parent_is_trait_impl = orig_parent_is_trait_impl;
 489         ret
 490     }
 491 }