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