1 use std::mem;
2
3 use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexSet};
4 use rustc_hir::def_id::{CrateNum, DefId, DefIdMap, DefIdSet};
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: DefIdMap<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: DefIdMap<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, FxIndexSet<clean::ItemLink>>,
122 /// Cfg that have been hidden via #![doc(cfg_hide(...))]
123 pub(crate) hidden_cfg: FxHashSet<clean::cfg::Cfg>,
124
125 /// Contains the list of `DefId`s which have been inlined. It is used when generating files
126 /// to check if a stripped item should get its file generated or not: if it's inside a
127 /// `#[doc(hidden)]` item or a private one and not inlined, it shouldn't get a file.
128 pub(crate) inlined_items: DefIdSet,
129 }
130
131 /// This struct is used to wrap the `cache` and `tcx` in order to run `DocFolder`.
132 struct CacheBuilder<'a, 'tcx> {
133 cache: &'a mut Cache,
134 /// This field is used to prevent duplicated impl blocks.
135 impl_ids: DefIdMap<DefIdSet>,
136 tcx: TyCtxt<'tcx>,
137 }
138
139 impl Cache {
new(document_private: bool) -> Self140 pub(crate) fn new(document_private: bool) -> Self {
141 Cache { document_private, ..Cache::default() }
142 }
143
144 /// Populates the `Cache` with more data. The returned `Crate` will be missing some data that was
145 /// in `krate` due to the data being moved into the `Cache`.
populate(cx: &mut DocContext<'_>, mut krate: clean::Crate) -> clean::Crate146 pub(crate) fn populate(cx: &mut DocContext<'_>, mut krate: clean::Crate) -> clean::Crate {
147 let tcx = cx.tcx;
148
149 // Crawl the crate to build various caches used for the output
150 debug!(?cx.cache.crate_version);
151 cx.cache.traits = krate.external_traits.take();
152
153 // Cache where all our extern crates are located
154 // FIXME: this part is specific to HTML so it'd be nice to remove it from the common code
155 for &crate_num in tcx.crates(()) {
156 let e = ExternalCrate { crate_num };
157
158 let name = e.name(tcx);
159 let render_options = &cx.render_options;
160 let extern_url = render_options.extern_html_root_urls.get(name.as_str()).map(|u| &**u);
161 let extern_url_takes_precedence = render_options.extern_html_root_takes_precedence;
162 let dst = &render_options.output;
163 let location = e.location(extern_url, extern_url_takes_precedence, dst, tcx);
164 cx.cache.extern_locations.insert(e.crate_num, location);
165 cx.cache.external_paths.insert(e.def_id(), (vec![name], ItemType::Module));
166 }
167
168 // FIXME: avoid this clone (requires implementing Default manually)
169 cx.cache.primitive_locations = PrimitiveType::primitive_locations(tcx).clone();
170 for (prim, &def_id) in &cx.cache.primitive_locations {
171 let crate_name = tcx.crate_name(def_id.krate);
172 // Recall that we only allow primitive modules to be at the root-level of the crate.
173 // If that restriction is ever lifted, this will have to include the relative paths instead.
174 cx.cache
175 .external_paths
176 .insert(def_id, (vec![crate_name, prim.as_sym()], ItemType::Primitive));
177 }
178
179 let (krate, mut impl_ids) = {
180 let mut cache_builder =
181 CacheBuilder { tcx, cache: &mut cx.cache, impl_ids: Default::default() };
182 krate = cache_builder.fold_crate(krate);
183 (krate, cache_builder.impl_ids)
184 };
185
186 for (trait_did, dids, impl_) in cx.cache.orphan_trait_impls.drain(..) {
187 if cx.cache.traits.contains_key(&trait_did) {
188 for did in dids {
189 if impl_ids.entry(did).or_default().insert(impl_.def_id()) {
190 cx.cache.impls.entry(did).or_default().push(impl_.clone());
191 }
192 }
193 }
194 }
195
196 krate
197 }
198 }
199
200 impl<'a, 'tcx> DocFolder for CacheBuilder<'a, 'tcx> {
fold_item(&mut self, item: clean::Item) -> Option<clean::Item>201 fn fold_item(&mut self, item: clean::Item) -> Option<clean::Item> {
202 if item.item_id.is_local() {
203 let is_stripped = matches!(*item.kind, clean::ItemKind::StrippedItem(..));
204 debug!(
205 "folding {} (stripped: {is_stripped:?}) \"{:?}\", id {:?}",
206 item.type_(),
207 item.name,
208 item.item_id
209 );
210 }
211
212 // If this is a stripped module,
213 // we don't want it or its children in the search index.
214 let orig_stripped_mod = match *item.kind {
215 clean::StrippedItem(box clean::ModuleItem(..)) => {
216 mem::replace(&mut self.cache.stripped_mod, true)
217 }
218 _ => self.cache.stripped_mod,
219 };
220
221 // If the impl is from a masked crate or references something from a
222 // masked crate then remove it completely.
223 if let clean::ImplItem(ref i) = *item.kind {
224 if self.cache.masked_crates.contains(&item.item_id.krate())
225 || i.trait_
226 .as_ref()
227 .map_or(false, |t| self.cache.masked_crates.contains(&t.def_id().krate))
228 || i.for_
229 .def_id(self.cache)
230 .map_or(false, |d| self.cache.masked_crates.contains(&d.krate))
231 {
232 return None;
233 }
234 }
235
236 // Propagate a trait method's documentation to all implementors of the
237 // trait.
238 if let clean::TraitItem(ref t) = *item.kind {
239 self.cache.traits.entry(item.item_id.expect_def_id()).or_insert_with(|| (**t).clone());
240 }
241
242 // Collect all the implementors of traits.
243 if let clean::ImplItem(ref i) = *item.kind &&
244 let Some(trait_) = &i.trait_ &&
245 !i.kind.is_blanket()
246 {
247 self.cache
248 .implementors
249 .entry(trait_.def_id())
250 .or_default()
251 .push(Impl { impl_item: item.clone() });
252 }
253
254 // Index this method for searching later on.
255 if let Some(s) = item.name.or_else(|| {
256 if item.is_stripped() {
257 None
258 } else if let clean::ImportItem(ref i) = *item.kind &&
259 let clean::ImportKind::Simple(s) = i.kind {
260 Some(s)
261 } else {
262 None
263 }
264 }) {
265 let (parent, is_inherent_impl_item) = match *item.kind {
266 clean::StrippedItem(..) => ((None, None), false),
267 clean::AssocConstItem(..) | clean::AssocTypeItem(..)
268 if self
269 .cache
270 .parent_stack
271 .last()
272 .map_or(false, |parent| parent.is_trait_impl()) =>
273 {
274 // skip associated items in trait impls
275 ((None, None), false)
276 }
277 clean::TyMethodItem(..)
278 | clean::TyAssocConstItem(..)
279 | clean::TyAssocTypeItem(..)
280 | clean::StructFieldItem(..)
281 | clean::VariantItem(..) => (
282 (
283 Some(
284 self.cache
285 .parent_stack
286 .last()
287 .expect("parent_stack is empty")
288 .item_id()
289 .expect_def_id(),
290 ),
291 Some(&self.cache.stack[..self.cache.stack.len() - 1]),
292 ),
293 false,
294 ),
295 clean::MethodItem(..) | clean::AssocConstItem(..) | clean::AssocTypeItem(..) => {
296 if self.cache.parent_stack.is_empty() {
297 ((None, None), false)
298 } else {
299 let last = self.cache.parent_stack.last().expect("parent_stack is empty 2");
300 let did = match &*last {
301 ParentStackItem::Impl {
302 // impl Trait for &T { fn method(self); }
303 //
304 // When generating a function index with the above shape, we want it
305 // associated with `T`, not with the primitive reference type. It should
306 // show up as `T::method`, rather than `reference::method`, in the search
307 // results page.
308 for_: clean::Type::BorrowedRef { type_, .. },
309 ..
310 } => type_.def_id(&self.cache),
311 ParentStackItem::Impl { for_, .. } => for_.def_id(&self.cache),
312 ParentStackItem::Type(item_id) => item_id.as_def_id(),
313 };
314 let path = did
315 .and_then(|did| self.cache.paths.get(&did))
316 // The current stack not necessarily has correlation
317 // for where the type was defined. On the other
318 // hand, `paths` always has the right
319 // information if present.
320 .map(|(fqp, _)| &fqp[..fqp.len() - 1]);
321 ((did, path), true)
322 }
323 }
324 _ => ((None, Some(&*self.cache.stack)), false),
325 };
326
327 match parent {
328 (parent, Some(path)) if is_inherent_impl_item || !self.cache.stripped_mod => {
329 debug_assert!(!item.is_stripped());
330
331 // A crate has a module at its root, containing all items,
332 // which should not be indexed. The crate-item itself is
333 // inserted later on when serializing the search-index.
334 if item.item_id.as_def_id().map_or(false, |idx| !idx.is_crate_root()) {
335 let desc =
336 short_markdown_summary(&item.doc_value(), &item.link_names(self.cache));
337 let ty = item.type_();
338 if ty != ItemType::StructField
339 || u16::from_str_radix(s.as_str(), 10).is_err()
340 {
341 // In case this is a field from a tuple struct, we don't add it into
342 // the search index because its name is something like "0", which is
343 // not useful for rustdoc search.
344 self.cache.search_index.push(IndexItem {
345 ty,
346 name: s,
347 path: join_with_double_colon(path),
348 desc,
349 parent,
350 parent_idx: None,
351 search_type: get_function_type_for_search(
352 &item,
353 self.tcx,
354 clean_impl_generics(self.cache.parent_stack.last()).as_ref(),
355 self.cache,
356 ),
357 aliases: item.attrs.get_doc_aliases(),
358 deprecation: item.deprecation(self.tcx),
359 });
360 }
361 }
362 }
363 (Some(parent), None) if is_inherent_impl_item => {
364 // We have a parent, but we don't know where they're
365 // defined yet. Wait for later to index this item.
366 let impl_generics = clean_impl_generics(self.cache.parent_stack.last());
367 self.cache.orphan_impl_items.push(OrphanImplItem {
368 parent,
369 item: item.clone(),
370 impl_generics,
371 });
372 }
373 _ => {}
374 }
375 }
376
377 // Keep track of the fully qualified path for this item.
378 let pushed = match item.name {
379 Some(n) if !n.is_empty() => {
380 self.cache.stack.push(n);
381 true
382 }
383 _ => false,
384 };
385
386 match *item.kind {
387 clean::StructItem(..)
388 | clean::EnumItem(..)
389 | clean::TypedefItem(..)
390 | clean::TraitItem(..)
391 | clean::TraitAliasItem(..)
392 | clean::FunctionItem(..)
393 | clean::ModuleItem(..)
394 | clean::ForeignFunctionItem(..)
395 | clean::ForeignStaticItem(..)
396 | clean::ConstantItem(..)
397 | clean::StaticItem(..)
398 | clean::UnionItem(..)
399 | clean::ForeignTypeItem
400 | clean::MacroItem(..)
401 | clean::ProcMacroItem(..)
402 | clean::VariantItem(..) => {
403 if !self.cache.stripped_mod {
404 // Re-exported items mean that the same id can show up twice
405 // in the rustdoc ast that we're looking at. We know,
406 // however, that a re-exported item doesn't show up in the
407 // `public_items` map, so we can skip inserting into the
408 // paths map if there was already an entry present and we're
409 // not a public item.
410 if !self.cache.paths.contains_key(&item.item_id.expect_def_id())
411 || self
412 .cache
413 .effective_visibilities
414 .is_directly_public(self.tcx, item.item_id.expect_def_id())
415 {
416 self.cache.paths.insert(
417 item.item_id.expect_def_id(),
418 (self.cache.stack.clone(), item.type_()),
419 );
420 }
421 }
422 }
423 clean::PrimitiveItem(..) => {
424 self.cache
425 .paths
426 .insert(item.item_id.expect_def_id(), (self.cache.stack.clone(), item.type_()));
427 }
428
429 clean::ExternCrateItem { .. }
430 | clean::ImportItem(..)
431 | clean::OpaqueTyItem(..)
432 | clean::ImplItem(..)
433 | clean::TyMethodItem(..)
434 | clean::MethodItem(..)
435 | clean::StructFieldItem(..)
436 | clean::TyAssocConstItem(..)
437 | clean::AssocConstItem(..)
438 | clean::TyAssocTypeItem(..)
439 | clean::AssocTypeItem(..)
440 | clean::StrippedItem(..)
441 | clean::KeywordItem => {
442 // FIXME: Do these need handling?
443 // The person writing this comment doesn't know.
444 // So would rather leave them to an expert,
445 // as at least the list is better than `_ => {}`.
446 }
447 }
448
449 // Maintain the parent stack.
450 let (item, parent_pushed) = match *item.kind {
451 clean::TraitItem(..)
452 | clean::EnumItem(..)
453 | clean::ForeignTypeItem
454 | clean::StructItem(..)
455 | clean::UnionItem(..)
456 | clean::VariantItem(..)
457 | clean::ImplItem(..) => {
458 self.cache.parent_stack.push(ParentStackItem::new(&item));
459 (self.fold_item_recur(item), true)
460 }
461 _ => (self.fold_item_recur(item), false),
462 };
463
464 // Once we've recursively found all the generics, hoard off all the
465 // implementations elsewhere.
466 let ret = if let clean::Item { kind: box clean::ImplItem(ref i), .. } = item {
467 // Figure out the id of this impl. This may map to a
468 // primitive rather than always to a struct/enum.
469 // Note: matching twice to restrict the lifetime of the `i` borrow.
470 let mut dids = FxHashSet::default();
471 match i.for_ {
472 clean::Type::Path { ref path }
473 | clean::BorrowedRef { type_: box clean::Type::Path { ref path }, .. } => {
474 dids.insert(path.def_id());
475 if let Some(generics) = path.generics() &&
476 let ty::Adt(adt, _) = self.tcx.type_of(path.def_id()).subst_identity().kind() &&
477 adt.is_fundamental() {
478 for ty in generics {
479 if let Some(did) = ty.def_id(self.cache) {
480 dids.insert(did);
481 }
482 }
483 }
484 }
485 clean::DynTrait(ref bounds, _)
486 | clean::BorrowedRef { type_: box clean::DynTrait(ref bounds, _), .. } => {
487 dids.insert(bounds[0].trait_.def_id());
488 }
489 ref t => {
490 let did = t
491 .primitive_type()
492 .and_then(|t| self.cache.primitive_locations.get(&t).cloned());
493
494 if let Some(did) = did {
495 dids.insert(did);
496 }
497 }
498 }
499
500 if let Some(generics) = i.trait_.as_ref().and_then(|t| t.generics()) {
501 for bound in generics {
502 if let Some(did) = bound.def_id(self.cache) {
503 dids.insert(did);
504 }
505 }
506 }
507 let impl_item = Impl { impl_item: item };
508 if impl_item.trait_did().map_or(true, |d| self.cache.traits.contains_key(&d)) {
509 for did in dids {
510 if self.impl_ids.entry(did).or_default().insert(impl_item.def_id()) {
511 self.cache
512 .impls
513 .entry(did)
514 .or_insert_with(Vec::new)
515 .push(impl_item.clone());
516 }
517 }
518 } else {
519 let trait_did = impl_item.trait_did().expect("no trait did");
520 self.cache.orphan_trait_impls.push((trait_did, dids, impl_item));
521 }
522 None
523 } else {
524 Some(item)
525 };
526
527 if pushed {
528 self.cache.stack.pop().expect("stack already empty");
529 }
530 if parent_pushed {
531 self.cache.parent_stack.pop().expect("parent stack already empty");
532 }
533 self.cache.stripped_mod = orig_stripped_mod;
534 ret
535 }
536 }
537
538 pub(crate) struct OrphanImplItem {
539 pub(crate) parent: DefId,
540 pub(crate) item: clean::Item,
541 pub(crate) impl_generics: Option<(clean::Type, clean::Generics)>,
542 }
543
544 /// Information about trait and type parents is tracked while traversing the item tree to build
545 /// the cache.
546 ///
547 /// We don't just store `Item` in there, because `Item` contains the list of children being
548 /// traversed and it would be wasteful to clone all that. We also need the item id, so just
549 /// storing `ItemKind` won't work, either.
550 enum ParentStackItem {
551 Impl {
552 for_: clean::Type,
553 trait_: Option<clean::Path>,
554 generics: clean::Generics,
555 kind: clean::ImplKind,
556 item_id: ItemId,
557 },
558 Type(ItemId),
559 }
560
561 impl ParentStackItem {
new(item: &clean::Item) -> Self562 fn new(item: &clean::Item) -> Self {
563 match &*item.kind {
564 clean::ItemKind::ImplItem(box clean::Impl { for_, trait_, generics, kind, .. }) => {
565 ParentStackItem::Impl {
566 for_: for_.clone(),
567 trait_: trait_.clone(),
568 generics: generics.clone(),
569 kind: kind.clone(),
570 item_id: item.item_id,
571 }
572 }
573 _ => ParentStackItem::Type(item.item_id),
574 }
575 }
is_trait_impl(&self) -> bool576 fn is_trait_impl(&self) -> bool {
577 matches!(self, ParentStackItem::Impl { trait_: Some(..), .. })
578 }
item_id(&self) -> ItemId579 fn item_id(&self) -> ItemId {
580 match self {
581 ParentStackItem::Impl { item_id, .. } => *item_id,
582 ParentStackItem::Type(item_id) => *item_id,
583 }
584 }
585 }
586
clean_impl_generics(item: Option<&ParentStackItem>) -> Option<(clean::Type, clean::Generics)>587 fn clean_impl_generics(item: Option<&ParentStackItem>) -> Option<(clean::Type, clean::Generics)> {
588 if let Some(ParentStackItem::Impl { for_, generics, kind: clean::ImplKind::Normal, .. }) = item
589 {
590 Some((for_.clone(), generics.clone()))
591 } else {
592 None
593 }
594 }
595