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, CRATE_DEF_INDEX};
   5 use rustc_middle::middle::privacy::AccessLevels;
   6 use rustc_middle::ty::TyCtxt;
   7 use rustc_span::symbol::sym;
   8
   9 use crate::clean::{self, GetDefId, ItemId, PrimitiveType};
  10 use crate::config::RenderOptions;
  11 use crate::fold::DocFolder;
  12 use crate::formats::item_type::ItemType;
  13 use crate::formats::Impl;
  14 use crate::html::markdown::short_markdown_summary;
  15 use crate::html::render::cache::{get_index_search_type, ExternalLocation};
  16 use crate::html::render::IndexItem;
  17
  18 /// This cache is used to store information about the [`clean::Crate`] being
  19 /// rendered in order to provide more useful documentation. This contains
  20 /// information like all implementors of a trait, all traits a type implements,
  21 /// documentation for all known traits, etc.
  22 ///
  23 /// This structure purposefully does not implement `Clone` because it's intended
  24 /// to be a fairly large and expensive structure to clone. Instead this adheres
  25 /// to `Send` so it may be stored in an `Arc` instance and shared among the various
  26 /// rendering threads.
  27 #[derive(Default)]
  28 crate struct Cache {
  29     /// Maps a type ID to all known implementations for that type. This is only
  30     /// recognized for intra-crate `ResolvedPath` types, and is used to print
  31     /// out extra documentation on the page of an enum/struct.
  32     ///
  33     /// The values of the map are a list of implementations and documentation
  34     /// found on that implementation.
  35     crate impls: FxHashMap<DefId, Vec<Impl>>,
  36
  37     /// Maintains a mapping of local crate `DefId`s to the fully qualified name
  38     /// and "short type description" of that node. This is used when generating
  39     /// URLs when a type is being linked to. External paths are not located in
  40     /// this map because the `External` type itself has all the information
  41     /// necessary.
  42     crate paths: FxHashMap<DefId, (Vec<String>, ItemType)>,
  43
  44     /// Similar to `paths`, but only holds external paths. This is only used for
  45     /// generating explicit hyperlinks to other crates.
  46     crate external_paths: FxHashMap<DefId, (Vec<String>, ItemType)>,
  47
  48     /// Maps local `DefId`s of exported types to fully qualified paths.
  49     /// Unlike 'paths', this mapping ignores any renames that occur
  50     /// due to 'use' statements.
  51     ///
  52     /// This map is used when writing out the special 'implementors'
  53     /// javascript file. By using the exact path that the type
  54     /// is declared with, we ensure that each path will be identical
  55     /// to the path used if the corresponding type is inlined. By
  56     /// doing this, we can detect duplicate impls on a trait page, and only display
  57     /// the impl for the inlined type.
  58     crate exact_paths: FxHashMap<DefId, Vec<String>>,
  59
  60     /// This map contains information about all known traits of this crate.
  61     /// Implementations of a crate should inherit the documentation of the
  62     /// parent trait if no extra documentation is specified, and default methods
  63     /// should show up in documentation about trait implementations.
  64     crate traits: FxHashMap<DefId, clean::TraitWithExtraInfo>,
  65
  66     /// When rendering traits, it's often useful to be able to list all
  67     /// implementors of the trait, and this mapping is exactly, that: a mapping
  68     /// of trait ids to the list of known implementors of the trait
  69     crate implementors: FxHashMap<DefId, Vec<Impl>>,
  70
  71     /// Cache of where external crate documentation can be found.
  72     crate extern_locations: FxHashMap<CrateNum, ExternalLocation>,
  73
  74     /// Cache of where documentation for primitives can be found.
  75     crate primitive_locations: FxHashMap<clean::PrimitiveType, DefId>,
  76
  77     // Note that external items for which `doc(hidden)` applies to are shown as
  78     // non-reachable while local items aren't. This is because we're reusing
  79     // the access levels from the privacy check pass.
  80     crate access_levels: AccessLevels<DefId>,
  81
  82     /// The version of the crate being documented, if given from the `--crate-version` flag.
  83     crate crate_version: Option<String>,
  84
  85     /// Whether to document private items.
  86     /// This is stored in `Cache` so it doesn't need to be passed through all rustdoc functions.
  87     crate document_private: bool,
  88
  89     /// Crates marked with [`#[doc(masked)]`][doc_masked].
  90     ///
  91     /// [doc_masked]: https://doc.rust-lang.org/nightly/unstable-book/language-features/doc-masked.html
  92     crate masked_crates: FxHashSet<CrateNum>,
  93
  94     // Private fields only used when initially crawling a crate to build a cache
  95     stack: Vec<String>,
  96     parent_stack: Vec<DefId>,
  97     parent_is_trait_impl: bool,
  98     stripped_mod: bool,
  99
 100     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     crate orphan_impl_items: Vec<(DefId, clean::Item)>,
 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     crate intra_doc_links: FxHashMap<ItemId, Vec<clean::ItemLink>>,
 122     /// Cfg that have been hidden via #![doc(cfg_hide(...))]
 123     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     tcx: TyCtxt<'tcx>,
 130 }
 131
 132 impl Cache {
 133     crate fn new(access_levels: AccessLevels<DefId>, document_private: bool) -> Self {
 134         Cache { access_levels, document_private, ..Cache::default() }
 135     }
 136
 137     /// Populates the `Cache` with more data. The returned `Crate` will be missing some data that was
 138     /// in `krate` due to the data being moved into the `Cache`.
 139     crate fn populate(
 140         &mut self,
 141         mut krate: clean::Crate,
 142         tcx: TyCtxt<'_>,
 143         render_options: &RenderOptions,
 144     ) -> clean::Crate {
 145         // Crawl the crate to build various caches used for the output
 146         debug!(?self.crate_version);
 147         self.traits = krate.external_traits.take();
 148         let RenderOptions { extern_html_root_takes_precedence, output: dst, .. } = render_options;
 149
 150         // Cache where all our extern crates are located
 151         // FIXME: this part is specific to HTML so it'd be nice to remove it from the common code
 152         for &e in &krate.externs {
 153             let name = e.name(tcx);
 154             let extern_url =
 155                 render_options.extern_html_root_urls.get(&*name.as_str()).map(|u| &**u);
 156             let location = e.location(extern_url, *extern_html_root_takes_precedence, dst, tcx);
 157             self.extern_locations.insert(e.crate_num, location);
 158             self.external_paths.insert(e.def_id(), (vec![name.to_string()], ItemType::Module));
 159         }
 160
 161         // FIXME: avoid this clone (requires implementing Default manually)
 162         self.primitive_locations = PrimitiveType::primitive_locations(tcx).clone();
 163         for (prim, &def_id) in &self.primitive_locations {
 164             let crate_name = tcx.crate_name(def_id.krate);
 165             // Recall that we only allow primitive modules to be at the root-level of the crate.
 166             // If that restriction is ever lifted, this will have to include the relative paths instead.
 167             self.external_paths.insert(
 168                 def_id,
 169                 (vec![crate_name.to_string(), prim.as_sym().to_string()], ItemType::Primitive),
 170             );
 171         }
 172
 173         krate = CacheBuilder { tcx, cache: self }.fold_crate(krate);
 174
 175         for (trait_did, dids, impl_) in self.orphan_trait_impls.drain(..) {
 176             if self.traits.contains_key(&trait_did) {
 177                 for did in dids {
 178                     self.impls.entry(did).or_default().push(impl_.clone());
 179                 }
 180             }
 181         }
 182
 183         krate
 184     }
 185 }
 186
 187 impl<'a, 'tcx> DocFolder for CacheBuilder<'a, 'tcx> {
 188     fn fold_item(&mut self, item: clean::Item) -> Option<clean::Item> {
 189         if item.def_id.is_local() {
 190             debug!("folding {} \"{:?}\", id {:?}", item.type_(), item.name, item.def_id);
 191         }
 192
 193         // If this is a stripped module,
 194         // we don't want it or its children in the search index.
 195         let orig_stripped_mod = match *item.kind {
 196             clean::StrippedItem(box clean::ModuleItem(..)) => {
 197                 mem::replace(&mut self.cache.stripped_mod, true)
 198             }
 199             _ => self.cache.stripped_mod,
 200         };
 201
 202         // If the impl is from a masked crate or references something from a
 203         // masked crate then remove it completely.
 204         if let clean::ImplItem(ref i) = *item.kind {
 205             if self.cache.masked_crates.contains(&item.def_id.krate())
 206                 || i.trait_.def_id().map_or(false, |d| self.cache.masked_crates.contains(&d.krate))
 207                 || i.for_.def_id().map_or(false, |d| self.cache.masked_crates.contains(&d.krate))
 208             {
 209                 return None;
 210             }
 211         }
 212
 213         // Propagate a trait method's documentation to all implementors of the
 214         // trait.
 215         if let clean::TraitItem(ref t) = *item.kind {
 216             self.cache.traits.entry(item.def_id.expect_def_id()).or_insert_with(|| {
 217                 clean::TraitWithExtraInfo {
 218                     trait_: t.clone(),
 219                     is_notable: item.attrs.has_doc_flag(sym::notable_trait),
 220                 }
 221             });
 222         }
 223
 224         // Collect all the implementors of traits.
 225         if let clean::ImplItem(ref i) = *item.kind {
 226             if let Some(did) = i.trait_.def_id() {
 227                 if i.blanket_impl.is_none() {
 228                     self.cache
 229                         .implementors
 230                         .entry(did)
 231                         .or_default()
 232                         .push(Impl { impl_item: item.clone() });
 233                 }
 234             }
 235         }
 236
 237         // Index this method for searching later on.
 238         if let Some(ref s) = item.name {
 239             let (parent, is_inherent_impl_item) = match *item.kind {
 240                 clean::StrippedItem(..) => ((None, None), false),
 241                 clean::AssocConstItem(..) | clean::TypedefItem(_, true)
 242                     if self.cache.parent_is_trait_impl =>
 243                 {
 244                     // skip associated items in trait impls
 245                     ((None, None), false)
 246                 }
 247                 clean::AssocTypeItem(..)
 248                 | clean::TyMethodItem(..)
 249                 | clean::StructFieldItem(..)
 250                 | clean::VariantItem(..) => (
 251                     (
 252                         Some(*self.cache.parent_stack.last().expect("parent_stack is empty")),
 253                         Some(&self.cache.stack[..self.cache.stack.len() - 1]),
 254                     ),
 255                     false,
 256                 ),
 257                 clean::MethodItem(..) | clean::AssocConstItem(..) => {
 258                     if self.cache.parent_stack.is_empty() {
 259                         ((None, None), false)
 260                     } else {
 261                         let last = self.cache.parent_stack.last().expect("parent_stack is empty 2");
 262                         let did = *last;
 263                         let path = match self.cache.paths.get(&did) {
 264                             // The current stack not necessarily has correlation
 265                             // for where the type was defined. On the other
 266                             // hand, `paths` always has the right
 267                             // information if present.
 268                             Some(&(
 269                                 ref fqp,
 270                                 ItemType::Trait
 271                                 | ItemType::Struct
 272                                 | ItemType::Union
 273                                 | ItemType::Enum,
 274                             )) => Some(&fqp[..fqp.len() - 1]),
 275                             Some(..) => Some(&*self.cache.stack),
 276                             None => None,
 277                         };
 278                         ((Some(*last), path), true)
 279                     }
 280                 }
 281                 _ => ((None, Some(&*self.cache.stack)), false),
 282             };
 283
 284             match parent {
 285                 (parent, Some(path)) if is_inherent_impl_item || !self.cache.stripped_mod => {
 286                     debug_assert!(!item.is_stripped());
 287
 288                     // A crate has a module at its root, containing all items,
 289                     // which should not be indexed. The crate-item itself is
 290                     // inserted later on when serializing the search-index.
 291                     if item.def_id.index().map_or(false, |idx| idx != CRATE_DEF_INDEX) {
 292                         let desc = item.doc_value().map_or_else(String::new, |x| {
 293                             short_markdown_summary(&x.as_str(), &item.link_names(&self.cache))
 294                         });
 295                         self.cache.search_index.push(IndexItem {
 296                             ty: item.type_(),
 297                             name: s.to_string(),
 298                             path: path.join("::"),
 299                             desc,
 300                             parent,
 301                             parent_idx: None,
 302                             search_type: get_index_search_type(&item, self.tcx),
 303                             aliases: item.attrs.get_doc_aliases(),
 304                         });
 305                     }
 306                 }
 307                 (Some(parent), None) if is_inherent_impl_item => {
 308                     // We have a parent, but we don't know where they're
 309                     // defined yet. Wait for later to index this item.
 310                     self.cache.orphan_impl_items.push((parent, item.clone()));
 311                 }
 312                 _ => {}
 313             }
 314         }
 315
 316         // Keep track of the fully qualified path for this item.
 317         let pushed = match item.name {
 318             Some(n) if !n.is_empty() => {
 319                 self.cache.stack.push(n.to_string());
 320                 true
 321             }
 322             _ => false,
 323         };
 324
 325         match *item.kind {
 326             clean::StructItem(..)
 327             | clean::EnumItem(..)
 328             | clean::TypedefItem(..)
 329             | clean::TraitItem(..)
 330             | clean::TraitAliasItem(..)
 331             | clean::FunctionItem(..)
 332             | clean::ModuleItem(..)
 333             | clean::ForeignFunctionItem(..)
 334             | clean::ForeignStaticItem(..)
 335             | clean::ConstantItem(..)
 336             | clean::StaticItem(..)
 337             | clean::UnionItem(..)
 338             | clean::ForeignTypeItem
 339             | clean::MacroItem(..)
 340             | clean::ProcMacroItem(..)
 341             | clean::VariantItem(..) => {
 342                 if !self.cache.stripped_mod {
 343                     // Re-exported items mean that the same id can show up twice
 344                     // in the rustdoc ast that we're looking at. We know,
 345                     // however, that a re-exported item doesn't show up in the
 346                     // `public_items` map, so we can skip inserting into the
 347                     // paths map if there was already an entry present and we're
 348                     // not a public item.
 349                     if !self.cache.paths.contains_key(&item.def_id.expect_def_id())
 350                         || self.cache.access_levels.is_public(item.def_id.expect_def_id())
 351                     {
 352                         self.cache.paths.insert(
 353                             item.def_id.expect_def_id(),
 354                             (self.cache.stack.clone(), item.type_()),
 355                         );
 356                     }
 357                 }
 358             }
 359             clean::PrimitiveItem(..) => {
 360                 self.cache
 361                     .paths
 362                     .insert(item.def_id.expect_def_id(), (self.cache.stack.clone(), item.type_()));
 363             }
 364
 365             clean::ExternCrateItem { .. }
 366             | clean::ImportItem(..)
 367             | clean::OpaqueTyItem(..)
 368             | clean::ImplItem(..)
 369             | clean::TyMethodItem(..)
 370             | clean::MethodItem(..)
 371             | clean::StructFieldItem(..)
 372             | clean::AssocConstItem(..)
 373             | clean::AssocTypeItem(..)
 374             | clean::StrippedItem(..)
 375             | clean::KeywordItem(..) => {
 376                 // FIXME: Do these need handling?
 377                 // The person writing this comment doesn't know.
 378                 // So would rather leave them to an expert,
 379                 // as at least the list is better than `_ => {}`.
 380             }
 381         }
 382
 383         // Maintain the parent stack
 384         let orig_parent_is_trait_impl = self.cache.parent_is_trait_impl;
 385         let parent_pushed = match *item.kind {
 386             clean::TraitItem(..)
 387             | clean::EnumItem(..)
 388             | clean::ForeignTypeItem
 389             | clean::StructItem(..)
 390             | clean::UnionItem(..)
 391             | clean::VariantItem(..) => {
 392                 self.cache.parent_stack.push(item.def_id.expect_def_id());
 393                 self.cache.parent_is_trait_impl = false;
 394                 true
 395             }
 396             clean::ImplItem(ref i) => {
 397                 self.cache.parent_is_trait_impl = i.trait_.is_some();
 398                 match i.for_ {
 399                     clean::ResolvedPath { did, .. } => {
 400                         self.cache.parent_stack.push(did);
 401                         true
 402                     }
 403                     clean::DynTrait(ref bounds, _)
 404                     | clean::BorrowedRef { type_: box clean::DynTrait(ref bounds, _), .. } => {
 405                         if let Some(did) = bounds[0].trait_.def_id() {
 406                             self.cache.parent_stack.push(did);
 407                             true
 408                         } else {
 409                             false
 410                         }
 411                     }
 412                     ref t => {
 413                         let prim_did = t
 414                             .primitive_type()
 415                             .and_then(|t| self.cache.primitive_locations.get(&t).cloned());
 416                         match prim_did {
 417                             Some(did) => {
 418                                 self.cache.parent_stack.push(did);
 419                                 true
 420                             }
 421                             None => false,
 422                         }
 423                     }
 424                 }
 425             }
 426             _ => false,
 427         };
 428
 429         // Once we've recursively found all the generics, hoard off all the
 430         // implementations elsewhere.
 431         let item = self.fold_item_recur(item);
 432         let ret = if let clean::Item { kind: box clean::ImplItem(ref i), .. } = item {
 433             // Figure out the id of this impl. This may map to a
 434             // primitive rather than always to a struct/enum.
 435             // Note: matching twice to restrict the lifetime of the `i` borrow.
 436             let mut dids = FxHashSet::default();
 437             match i.for_ {
 438                 clean::ResolvedPath { did, .. }
 439                 | clean::BorrowedRef { type_: box clean::ResolvedPath { did, .. }, .. } => {
 440                     dids.insert(did);
 441                 }
 442                 clean::DynTrait(ref bounds, _)
 443                 | clean::BorrowedRef { type_: box clean::DynTrait(ref bounds, _), .. } => {
 444                     if let Some(did) = bounds[0].trait_.def_id() {
 445                         dids.insert(did);
 446                     }
 447                 }
 448                 ref t => {
 449                     let did = t
 450                         .primitive_type()
 451                         .and_then(|t| self.cache.primitive_locations.get(&t).cloned());
 452
 453                     if let Some(did) = did {
 454                         dids.insert(did);
 455                     }
 456                 }
 457             }
 458
 459             if let Some(generics) = i.trait_.as_ref().and_then(|t| t.generics()) {
 460                 for bound in generics {
 461                     if let Some(did) = bound.def_id() {
 462                         dids.insert(did);
 463                     }
 464                 }
 465             }
 466             let impl_item = Impl { impl_item: item };
 467             if impl_item.trait_did().map_or(true, |d| self.cache.traits.contains_key(&d)) {
 468                 for did in dids {
 469                     self.cache.impls.entry(did).or_insert(vec![]).push(impl_item.clone());
 470                 }
 471             } else {
 472                 let trait_did = impl_item.trait_did().expect("no trait did");
 473                 self.cache.orphan_trait_impls.push((trait_did, dids, impl_item));
 474             }
 475             None
 476         } else {
 477             Some(item)
 478         };
 479
 480         if pushed {
 481             self.cache.stack.pop().expect("stack already empty");
 482         }
 483         if parent_pushed {
 484             self.cache.parent_stack.pop().expect("parent stack already empty");
 485         }
 486         self.cache.stripped_mod = orig_stripped_mod;
 487         self.cache.parent_is_trait_impl = orig_parent_is_trait_impl;
 488         ret
 489     }
 490 }