1 use std::collections::BTreeMap;
3 use std::path::{Path, PathBuf};
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_span::source_map::FileName;
9 use rustc_span::Symbol;
11 use crate::clean::{self, GetDefId};
12 use crate::config::RenderInfo;
13 use crate::fold::DocFolder;
14 use crate::formats::item_type::ItemType;
15 use crate::formats::Impl;
16 use crate::html::markdown::short_markdown_summary;
17 use crate::html::render::cache::{extern_location, get_index_search_type, ExternalLocation};
18 use crate::html::render::IndexItem;
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.
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 a `Arc` instance and shared among the various
28 /// rendering threads.
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.
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>>,
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
44 crate paths: FxHashMap<DefId, (Vec<String>, ItemType)>,
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)>,
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.
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>>,
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::Trait>,
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>>,
73 /// Cache of where external crate documentation can be found.
74 crate extern_locations: FxHashMap<CrateNum, (Symbol, PathBuf, ExternalLocation)>,
76 /// Cache of where documentation for primitives can be found.
77 crate primitive_locations: FxHashMap<clean::PrimitiveType, DefId>,
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>,
84 /// The version of the crate being documented, if given from the `--crate-version` flag.
85 crate crate_version: Option<String>,
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,
91 // Private fields only used when initially crawling a crate to build a cache
93 parent_stack: Vec<DefId>,
94 parent_is_trait_impl: bool,
96 masked_crates: FxHashSet<CrateNum>,
98 crate search_index: Vec<IndexItem>,
99 crate deref_trait_did: Option<DefId>,
100 crate deref_mut_trait_did: Option<DefId>,
101 crate owned_box_did: Option<DefId>,
103 // In rare case where a structure is defined in one module but implemented
104 // in another, if the implementing module is parsed before defining module,
105 // then the fully qualified name of the structure isn't presented in `paths`
106 // yet when its implementation methods are being indexed. Caches such methods
107 // and their parent id here and indexes them at the end of crate parsing.
108 crate orphan_impl_items: Vec<(DefId, clean::Item)>,
110 // Similarly to `orphan_impl_items`, sometimes trait impls are picked up
111 // even though the trait itself is not exported. This can happen if a trait
112 // was defined in function/expression scope, since the impl will be picked
113 // up by `collect-trait-impls` but the trait won't be scraped out in the HIR
114 // crawl. In order to prevent crashes when looking for spotlight traits or
115 // when gathering trait documentation on a type, hold impls here while
116 // folding and add them to the cache later on if we find the trait.
117 orphan_trait_impls: Vec<(DefId, FxHashSet<DefId>, Impl)>,
119 /// Aliases added through `#[doc(alias = "...")]`. Since a few items can have the same alias,
120 /// we need the alias element to have an array of items.
121 crate aliases: BTreeMap<String, Vec<usize>>,
126 render_info: RenderInfo,
127 document_private: bool,
128 extern_html_root_urls: &BTreeMap<String, String>,
130 mut krate: clean::Crate,
131 ) -> (clean::Crate, Cache) {
132 // Crawl the crate to build various caches used for the output
145 external_paths.into_iter().map(|(k, (v, t))| (k, (v, ItemType::from(t)))).collect();
147 let mut cache = Cache {
150 parent_is_trait_impl: false,
153 crate_version: krate.version.take(),
155 traits: krate.external_traits.replace(Default::default()),
159 masked_crates: mem::take(&mut krate.masked_crates),
163 // Cache where all our extern crates are located
164 // FIXME: this part is specific to HTML so it'd be nice to remove it from the common code
165 for &(n, ref e) in &krate.externs {
166 let src_root = match e.src {
167 FileName::Real(ref p) => match p.local_path().parent() {
168 Some(p) => p.to_path_buf(),
169 None => PathBuf::new(),
173 let extern_url = extern_html_root_urls.get(&*e.name.as_str()).map(|u| &**u);
176 .insert(n, (e.name, src_root, extern_location(e, extern_url, &dst)));
178 let did = DefId { krate: n, index: CRATE_DEF_INDEX };
179 cache.external_paths.insert(did, (vec![e.name.to_string()], ItemType::Module));
182 // Cache where all known primitives have their documentation located.
184 // Favor linking to as local extern as possible, so iterate all crates in
185 // reverse topological order.
186 for &(_, ref e) in krate.externs.iter().rev() {
187 for &(def_id, prim) in &e.primitives {
188 cache.primitive_locations.insert(prim, def_id);
191 for &(def_id, prim) in &krate.primitives {
192 cache.primitive_locations.insert(prim, def_id);
195 cache.stack.push(krate.name.to_string());
198 let mut cache_wrapper = CacheWrapper { cache: &mut cache, tmp_cache: Cache::default() };
199 cache_wrapper.fold_crate(krate)
202 for (trait_did, dids, impl_) in cache.orphan_trait_impls.drain(..) {
203 if cache.traits.contains_key(&trait_did) {
205 cache.impls.entry(did).or_default().push(impl_.clone());
214 /// This struct is needed because we need to use an empty `Cache` for all functions requiring
215 /// a `Cache`. If we use the already filled one (`cache` in here), it'll provide information
216 /// about implementations that aren't related to the type being checked.
217 struct CacheWrapper<'a> {
218 cache: &'a mut Cache,
222 impl<'a> DocFolder for CacheWrapper<'a> {
223 fn fold_item(&mut self, item: clean::Item) -> Option<clean::Item> {
224 if item.def_id.is_local() {
225 debug!("folding {} \"{:?}\", id {:?}", item.type_(), item.name, item.def_id);
228 // If this is a stripped module,
229 // we don't want it or its children in the search index.
230 let orig_stripped_mod = match *item.kind {
231 clean::StrippedItem(box clean::ModuleItem(..)) => {
232 mem::replace(&mut self.cache.stripped_mod, true)
234 _ => self.cache.stripped_mod,
237 // If the impl is from a masked crate or references something from a
238 // masked crate then remove it completely.
239 if let clean::ImplItem(ref i) = *item.kind {
240 if self.cache.masked_crates.contains(&item.def_id.krate)
242 .def_id(&self.tmp_cache)
243 .map_or(false, |d| self.cache.masked_crates.contains(&d.krate))
245 .def_id(&self.tmp_cache)
246 .map_or(false, |d| self.cache.masked_crates.contains(&d.krate))
252 // Propagate a trait method's documentation to all implementors of the
254 if let clean::TraitItem(ref t) = *item.kind {
255 self.cache.traits.entry(item.def_id).or_insert_with(|| t.clone());
258 // Collect all the implementors of traits.
259 if let clean::ImplItem(ref i) = *item.kind {
260 if let Some(did) = i.trait_.def_id(&self.tmp_cache) {
261 if i.blanket_impl.is_none() {
266 .push(Impl { impl_item: item.clone() });
271 // Index this method for searching later on.
272 if let Some(ref s) = item.name {
273 let (parent, is_inherent_impl_item) = match *item.kind {
274 clean::StrippedItem(..) => ((None, None), false),
275 clean::AssocConstItem(..) | clean::TypedefItem(_, true)
276 if self.cache.parent_is_trait_impl =>
278 // skip associated items in trait impls
279 ((None, None), false)
281 clean::AssocTypeItem(..)
282 | clean::TyMethodItem(..)
283 | clean::StructFieldItem(..)
284 | clean::VariantItem(..) => (
286 Some(*self.cache.parent_stack.last().expect("parent_stack is empty")),
287 Some(&self.cache.stack[..self.cache.stack.len() - 1]),
291 clean::MethodItem(..) | clean::AssocConstItem(..) => {
292 if self.cache.parent_stack.is_empty() {
293 ((None, None), false)
295 let last = self.cache.parent_stack.last().expect("parent_stack is empty 2");
297 let path = match self.cache.paths.get(&did) {
298 // The current stack not necessarily has correlation
299 // for where the type was defined. On the other
300 // hand, `paths` always has the right
301 // information if present.
308 )) => Some(&fqp[..fqp.len() - 1]),
309 Some(..) => Some(&*self.cache.stack),
312 ((Some(*last), path), true)
315 _ => ((None, Some(&*self.cache.stack)), false),
319 (parent, Some(path)) if is_inherent_impl_item || !self.cache.stripped_mod => {
320 debug_assert!(!item.is_stripped());
322 // A crate has a module at its root, containing all items,
323 // which should not be indexed. The crate-item itself is
324 // inserted later on when serializing the search-index.
325 if item.def_id.index != CRATE_DEF_INDEX {
326 self.cache.search_index.push(IndexItem {
329 path: path.join("::"),
332 .map_or_else(String::new, |x| short_markdown_summary(&x.as_str())),
335 search_type: get_index_search_type(&item, &self.tmp_cache),
338 for alias in item.attrs.get_doc_aliases() {
341 .entry(alias.to_lowercase())
342 .or_insert(Vec::new())
343 .push(self.cache.search_index.len() - 1);
347 (Some(parent), None) if is_inherent_impl_item => {
348 // We have a parent, but we don't know where they're
349 // defined yet. Wait for later to index this item.
350 self.cache.orphan_impl_items.push((parent, item.clone()));
356 // Keep track of the fully qualified path for this item.
357 let pushed = match item.name {
358 Some(n) if !n.is_empty() => {
359 self.cache.stack.push(n.to_string());
366 clean::StructItem(..)
367 | clean::EnumItem(..)
368 | clean::TypedefItem(..)
369 | clean::TraitItem(..)
370 | clean::FunctionItem(..)
371 | clean::ModuleItem(..)
372 | clean::ForeignFunctionItem(..)
373 | clean::ForeignStaticItem(..)
374 | clean::ConstantItem(..)
375 | clean::StaticItem(..)
376 | clean::UnionItem(..)
377 | clean::ForeignTypeItem
378 | clean::MacroItem(..)
379 | clean::ProcMacroItem(..)
380 | clean::VariantItem(..)
381 if !self.cache.stripped_mod =>
383 // Re-exported items mean that the same id can show up twice
384 // in the rustdoc ast that we're looking at. We know,
385 // however, that a re-exported item doesn't show up in the
386 // `public_items` map, so we can skip inserting into the
387 // paths map if there was already an entry present and we're
388 // not a public item.
389 if !self.cache.paths.contains_key(&item.def_id)
390 || self.cache.access_levels.is_public(item.def_id)
392 self.cache.paths.insert(item.def_id, (self.cache.stack.clone(), item.type_()));
395 clean::PrimitiveItem(..) => {
396 self.cache.paths.insert(item.def_id, (self.cache.stack.clone(), item.type_()));
402 // Maintain the parent stack
403 let orig_parent_is_trait_impl = self.cache.parent_is_trait_impl;
404 let parent_pushed = match *item.kind {
406 | clean::EnumItem(..)
407 | clean::ForeignTypeItem
408 | clean::StructItem(..)
409 | clean::UnionItem(..)
410 | clean::VariantItem(..) => {
411 self.cache.parent_stack.push(item.def_id);
412 self.cache.parent_is_trait_impl = false;
415 clean::ImplItem(ref i) => {
416 self.cache.parent_is_trait_impl = i.trait_.is_some();
418 clean::ResolvedPath { did, .. } => {
419 self.cache.parent_stack.push(did);
425 .and_then(|t| self.cache.primitive_locations.get(&t).cloned());
428 self.cache.parent_stack.push(did);
439 // Once we've recursively found all the generics, hoard off all the
440 // implementations elsewhere.
441 let item = self.fold_item_recur(item);
442 let ret = if let clean::Item { kind: box clean::ImplItem(ref i), .. } = item {
443 // Figure out the id of this impl. This may map to a
444 // primitive rather than always to a struct/enum.
445 // Note: matching twice to restrict the lifetime of the `i` borrow.
446 let mut dids = FxHashSet::default();
448 clean::ResolvedPath { did, .. }
449 | clean::BorrowedRef { type_: box clean::ResolvedPath { did, .. }, .. } => {
455 .and_then(|t| self.cache.primitive_locations.get(&t).cloned());
457 if let Some(did) = did {
463 if let Some(generics) = i.trait_.as_ref().and_then(|t| t.generics()) {
464 for bound in generics {
465 if let Some(did) = bound.def_id(&self.tmp_cache) {
470 let impl_item = Impl { impl_item: item };
472 .trait_did(&self.tmp_cache)
473 .map_or(true, |d| self.cache.traits.contains_key(&d))
476 self.cache.impls.entry(did).or_insert(vec![]).push(impl_item.clone());
479 let trait_did = impl_item.trait_did(&self.tmp_cache).expect("no trait did");
480 self.cache.orphan_trait_impls.push((trait_did, dids, impl_item));
488 self.cache.stack.pop().expect("stack already empty");
491 self.cache.parent_stack.pop().expect("parent stack already empty");
493 self.cache.stripped_mod = orig_stripped_mod;
494 self.cache.parent_is_trait_impl = orig_parent_is_trait_impl;