1 use crate::clean::{self, AttributesExt, GetDefId};
2 use crate::fold::DocFolder;
3 use rustc::middle::privacy::AccessLevels;
4 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
5 use rustc_hir::def_id::{CrateNum, DefId, CRATE_DEF_INDEX};
6 use rustc_span::source_map::FileName;
7 use rustc_span::symbol::sym;
8 use std::collections::BTreeMap;
10 use std::path::{Path, PathBuf};
14 use super::{plain_summary_line, shorten, Impl, IndexItem, IndexItemFunctionType, ItemType};
15 use super::{Generic, RenderInfo, RenderType, TypeWithKind};
17 /// Indicates where an external crate can be found.
18 pub enum ExternalLocation {
19 /// Remote URL root of the external crate
21 /// This external crate can be found in the local doc/ folder
23 /// The external crate could not be found.
27 /// This cache is used to store information about the `clean::Crate` being
28 /// rendered in order to provide more useful documentation. This contains
29 /// information like all implementors of a trait, all traits a type implements,
30 /// documentation for all known traits, etc.
32 /// This structure purposefully does not implement `Clone` because it's intended
33 /// to be a fairly large and expensive structure to clone. Instead this adheres
34 /// to `Send` so it may be stored in a `Arc` instance and shared among the various
35 /// rendering threads.
38 /// Maps a type ID to all known implementations for that type. This is only
39 /// recognized for intra-crate `ResolvedPath` types, and is used to print
40 /// out extra documentation on the page of an enum/struct.
42 /// The values of the map are a list of implementations and documentation
43 /// found on that implementation.
44 pub impls: FxHashMap<DefId, Vec<Impl>>,
46 /// Maintains a mapping of local crate `DefId`s to the fully qualified name
47 /// and "short type description" of that node. This is used when generating
48 /// URLs when a type is being linked to. External paths are not located in
49 /// this map because the `External` type itself has all the information
51 pub paths: FxHashMap<DefId, (Vec<String>, ItemType)>,
53 /// Similar to `paths`, but only holds external paths. This is only used for
54 /// generating explicit hyperlinks to other crates.
55 pub external_paths: FxHashMap<DefId, (Vec<String>, ItemType)>,
57 /// Maps local `DefId`s of exported types to fully qualified paths.
58 /// Unlike 'paths', this mapping ignores any renames that occur
59 /// due to 'use' statements.
61 /// This map is used when writing out the special 'implementors'
62 /// javascript file. By using the exact path that the type
63 /// is declared with, we ensure that each path will be identical
64 /// to the path used if the corresponding type is inlined. By
65 /// doing this, we can detect duplicate impls on a trait page, and only display
66 /// the impl for the inlined type.
67 pub exact_paths: FxHashMap<DefId, Vec<String>>,
69 /// This map contains information about all known traits of this crate.
70 /// Implementations of a crate should inherit the documentation of the
71 /// parent trait if no extra documentation is specified, and default methods
72 /// should show up in documentation about trait implementations.
73 pub traits: FxHashMap<DefId, clean::Trait>,
75 /// When rendering traits, it's often useful to be able to list all
76 /// implementors of the trait, and this mapping is exactly, that: a mapping
77 /// of trait ids to the list of known implementors of the trait
78 pub implementors: FxHashMap<DefId, Vec<Impl>>,
80 /// Cache of where external crate documentation can be found.
81 pub extern_locations: FxHashMap<CrateNum, (String, PathBuf, ExternalLocation)>,
83 /// Cache of where documentation for primitives can be found.
84 pub primitive_locations: FxHashMap<clean::PrimitiveType, DefId>,
86 // Note that external items for which `doc(hidden)` applies to are shown as
87 // non-reachable while local items aren't. This is because we're reusing
88 // the access levels from the privacy check pass.
89 pub access_levels: AccessLevels<DefId>,
91 /// The version of the crate being documented, if given from the `--crate-version` flag.
92 pub crate_version: Option<String>,
94 // Private fields only used when initially crawling a crate to build a cache
96 parent_stack: Vec<DefId>,
97 parent_is_trait_impl: bool,
98 search_index: Vec<IndexItem>,
100 pub deref_trait_did: Option<DefId>,
101 pub deref_mut_trait_did: Option<DefId>,
102 pub owned_box_did: Option<DefId>,
103 masked_crates: FxHashSet<CrateNum>,
105 // In rare case where a structure is defined in one module but implemented
106 // in another, if the implementing module is parsed before defining module,
107 // then the fully qualified name of the structure isn't presented in `paths`
108 // yet when its implementation methods are being indexed. Caches such methods
109 // and their parent id here and indexes them at the end of crate parsing.
110 orphan_impl_items: Vec<(DefId, clean::Item)>,
112 // Similarly to `orphan_impl_items`, sometimes trait impls are picked up
113 // even though the trait itself is not exported. This can happen if a trait
114 // was defined in function/expression scope, since the impl will be picked
115 // up by `collect-trait-impls` but the trait won't be scraped out in the HIR
116 // crawl. In order to prevent crashes when looking for spotlight traits or
117 // when gathering trait documentation on a type, hold impls here while
118 // folding and add them to the cache later on if we find the trait.
119 orphan_trait_impls: Vec<(DefId, FxHashSet<DefId>, Impl)>,
121 /// Aliases added through `#[doc(alias = "...")]`. Since a few items can have the same alias,
122 /// we need the alias element to have an array of items.
123 pub(super) aliases: FxHashMap<String, Vec<IndexItem>>,
128 renderinfo: RenderInfo,
129 extern_html_root_urls: &BTreeMap<String, String>,
131 mut krate: clean::Crate,
132 ) -> (clean::Crate, String, Cache) {
133 // Crawl the crate to build various caches used for the output
146 external_paths.into_iter().map(|(k, (v, t))| (k, (v, ItemType::from(t)))).collect();
148 let mut cache = Cache {
149 impls: Default::default(),
152 paths: Default::default(),
153 implementors: Default::default(),
155 parent_stack: Vec::new(),
156 search_index: Vec::new(),
157 parent_is_trait_impl: false,
158 extern_locations: Default::default(),
159 primitive_locations: Default::default(),
162 crate_version: krate.version.take(),
163 orphan_impl_items: Vec::new(),
164 orphan_trait_impls: Vec::new(),
165 traits: krate.external_traits.replace(Default::default()),
169 masked_crates: mem::take(&mut krate.masked_crates),
170 aliases: Default::default(),
173 // Cache where all our extern crates are located
174 for &(n, ref e) in &krate.externs {
175 let src_root = match e.src {
176 FileName::Real(ref p) => match p.parent() {
177 Some(p) => p.to_path_buf(),
178 None => PathBuf::new(),
182 let extern_url = extern_html_root_urls.get(&e.name).map(|u| &**u);
185 .insert(n, (e.name.clone(), src_root, extern_location(e, extern_url, &dst)));
187 let did = DefId { krate: n, index: CRATE_DEF_INDEX };
188 cache.external_paths.insert(did, (vec![e.name.to_string()], ItemType::Module));
191 // Cache where all known primitives have their documentation located.
193 // Favor linking to as local extern as possible, so iterate all crates in
194 // reverse topological order.
195 for &(_, ref e) in krate.externs.iter().rev() {
196 for &(def_id, prim, _) in &e.primitives {
197 cache.primitive_locations.insert(prim, def_id);
200 for &(def_id, prim, _) in &krate.primitives {
201 cache.primitive_locations.insert(prim, def_id);
204 cache.stack.push(krate.name.clone());
205 krate = cache.fold_crate(krate);
207 for (trait_did, dids, impl_) in cache.orphan_trait_impls.drain(..) {
208 if cache.traits.contains_key(&trait_did) {
210 cache.impls.entry(did).or_insert(vec![]).push(impl_.clone());
215 // Build our search index
216 let index = build_index(&krate, &mut cache);
218 (krate, index, cache)
222 impl DocFolder for Cache {
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.inner {
231 clean::StrippedItem(box clean::ModuleItem(..)) => {
232 mem::replace(&mut self.stripped_mod, true)
234 _ => self.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.inner {
240 if self.masked_crates.contains(&item.def_id.krate)
241 || i.trait_.def_id().map_or(false, |d| self.masked_crates.contains(&d.krate))
242 || i.for_.def_id().map_or(false, |d| self.masked_crates.contains(&d.krate))
248 // Propagate a trait method's documentation to all implementors of the
250 if let clean::TraitItem(ref t) = item.inner {
251 self.traits.entry(item.def_id).or_insert_with(|| t.clone());
254 // Collect all the implementors of traits.
255 if let clean::ImplItem(ref i) = item.inner {
256 if let Some(did) = i.trait_.def_id() {
257 if i.blanket_impl.is_none() {
261 .push(Impl { impl_item: item.clone() });
266 // Index this method for searching later on.
267 if let Some(ref s) = item.name {
268 let (parent, is_inherent_impl_item) = match item.inner {
269 clean::StrippedItem(..) => ((None, None), false),
270 clean::AssocConstItem(..) | clean::TypedefItem(_, true)
271 if self.parent_is_trait_impl =>
273 // skip associated items in trait impls
274 ((None, None), false)
276 clean::AssocTypeItem(..)
277 | clean::TyMethodItem(..)
278 | clean::StructFieldItem(..)
279 | clean::VariantItem(..) => (
281 Some(*self.parent_stack.last().expect("parent_stack is empty")),
282 Some(&self.stack[..self.stack.len() - 1]),
286 clean::MethodItem(..) | clean::AssocConstItem(..) => {
287 if self.parent_stack.is_empty() {
288 ((None, None), false)
290 let last = self.parent_stack.last().expect("parent_stack is empty 2");
292 let path = match self.paths.get(&did) {
293 // The current stack not necessarily has correlation
294 // for where the type was defined. On the other
295 // hand, `paths` always has the right
296 // information if present.
297 Some(&(ref fqp, ItemType::Trait))
298 | Some(&(ref fqp, ItemType::Struct))
299 | Some(&(ref fqp, ItemType::Union))
300 | Some(&(ref fqp, ItemType::Enum)) => Some(&fqp[..fqp.len() - 1]),
301 Some(..) => Some(&*self.stack),
304 ((Some(*last), path), true)
307 _ => ((None, Some(&*self.stack)), false),
311 (parent, Some(path)) if is_inherent_impl_item || (!self.stripped_mod) => {
312 debug_assert!(!item.is_stripped());
314 // A crate has a module at its root, containing all items,
315 // which should not be indexed. The crate-item itself is
316 // inserted later on when serializing the search-index.
317 if item.def_id.index != CRATE_DEF_INDEX {
318 self.search_index.push(IndexItem {
321 path: path.join("::"),
322 desc: shorten(plain_summary_line(item.doc_value())),
325 search_type: get_index_search_type(&item),
329 (Some(parent), None) if is_inherent_impl_item => {
330 // We have a parent, but we don't know where they're
331 // defined yet. Wait for later to index this item.
332 self.orphan_impl_items.push((parent, item.clone()));
338 // Keep track of the fully qualified path for this item.
339 let pushed = match item.name {
340 Some(ref n) if !n.is_empty() => {
341 self.stack.push(n.to_string());
348 clean::StructItem(..)
349 | clean::EnumItem(..)
350 | clean::TypedefItem(..)
351 | clean::TraitItem(..)
352 | clean::FunctionItem(..)
353 | clean::ModuleItem(..)
354 | clean::ForeignFunctionItem(..)
355 | clean::ForeignStaticItem(..)
356 | clean::ConstantItem(..)
357 | clean::StaticItem(..)
358 | clean::UnionItem(..)
359 | clean::ForeignTypeItem
360 | clean::MacroItem(..)
361 | clean::ProcMacroItem(..)
362 | clean::VariantItem(..)
363 if !self.stripped_mod =>
365 // Re-exported items mean that the same id can show up twice
366 // in the rustdoc ast that we're looking at. We know,
367 // however, that a re-exported item doesn't show up in the
368 // `public_items` map, so we can skip inserting into the
369 // paths map if there was already an entry present and we're
370 // not a public item.
371 if !self.paths.contains_key(&item.def_id)
372 || self.access_levels.is_public(item.def_id)
374 self.paths.insert(item.def_id, (self.stack.clone(), item.type_()));
376 self.add_aliases(&item);
379 clean::PrimitiveItem(..) => {
380 self.add_aliases(&item);
381 self.paths.insert(item.def_id, (self.stack.clone(), item.type_()));
387 // Maintain the parent stack
388 let orig_parent_is_trait_impl = self.parent_is_trait_impl;
389 let parent_pushed = match item.inner {
391 | clean::EnumItem(..)
392 | clean::ForeignTypeItem
393 | clean::StructItem(..)
394 | clean::UnionItem(..)
395 | clean::VariantItem(..) => {
396 self.parent_stack.push(item.def_id);
397 self.parent_is_trait_impl = false;
400 clean::ImplItem(ref i) => {
401 self.parent_is_trait_impl = i.trait_.is_some();
403 clean::ResolvedPath { did, .. } => {
404 self.parent_stack.push(did);
410 .and_then(|t| self.primitive_locations.get(&t).cloned());
413 self.parent_stack.push(did);
424 // Once we've recursively found all the generics, hoard off all the
425 // implementations elsewhere.
426 let ret = self.fold_item_recur(item).and_then(|item| {
427 if let clean::Item { inner: clean::ImplItem(_), .. } = item {
428 // Figure out the id of this impl. This may map to a
429 // primitive rather than always to a struct/enum.
430 // Note: matching twice to restrict the lifetime of the `i` borrow.
431 let mut dids = FxHashSet::default();
432 if let clean::Item { inner: clean::ImplItem(ref i), .. } = item {
434 clean::ResolvedPath { did, .. }
435 | clean::BorrowedRef {
436 type_: box clean::ResolvedPath { did, .. }, ..
443 .and_then(|t| self.primitive_locations.get(&t).cloned());
445 if let Some(did) = did {
451 if let Some(generics) = i.trait_.as_ref().and_then(|t| t.generics()) {
452 for bound in generics {
453 if let Some(did) = bound.def_id() {
461 let impl_item = Impl { impl_item: item };
462 if impl_item.trait_did().map_or(true, |d| self.traits.contains_key(&d)) {
464 self.impls.entry(did).or_insert(vec![]).push(impl_item.clone());
467 let trait_did = impl_item.trait_did().expect("no trait did");
468 self.orphan_trait_impls.push((trait_did, dids, impl_item));
477 self.stack.pop().expect("stack already empty");
480 self.parent_stack.pop().expect("parent stack already empty");
482 self.stripped_mod = orig_stripped_mod;
483 self.parent_is_trait_impl = orig_parent_is_trait_impl;
489 fn add_aliases(&mut self, item: &clean::Item) {
490 if item.def_id.index == CRATE_DEF_INDEX {
493 if let Some(ref item_name) = item.name {
497 .map(|p| p.0[..p.0.len() - 1].join("::"))
498 .unwrap_or("std".to_owned());
502 .filter(|a| a.check_name(sym::alias))
503 .filter_map(|a| a.value_str().map(|s| s.to_string().replace("\"", "")))
504 .filter(|v| !v.is_empty())
505 .collect::<FxHashSet<_>>()
508 self.aliases.entry(alias).or_insert(Vec::with_capacity(1)).push(IndexItem {
510 name: item_name.to_string(),
512 desc: shorten(plain_summary_line(item.doc_value())),
515 search_type: get_index_search_type(&item),
522 /// Attempts to find where an external crate is located, given that we're
523 /// rendering in to the specified source destination.
525 e: &clean::ExternalCrate,
526 extern_url: Option<&str>,
528 ) -> ExternalLocation {
529 use ExternalLocation::*;
530 // See if there's documentation generated into the local directory
531 let local_location = dst.join(&e.name);
532 if local_location.is_dir() {
536 if let Some(url) = extern_url {
537 let mut url = url.to_string();
538 if !url.ends_with('/') {
544 // Failing that, see if there's an attribute specifying where to find this
548 .filter(|a| a.check_name(sym::html_root_url))
549 .filter_map(|a| a.value_str())
551 let mut url = url.to_string();
552 if !url.ends_with('/') {
558 .unwrap_or(Unknown) // Well, at least we tried.
561 /// Builds the search index from the collected metadata
562 fn build_index(krate: &clean::Crate, cache: &mut Cache) -> String {
563 let mut defid_to_pathid = FxHashMap::default();
564 let mut crate_items = Vec::with_capacity(cache.search_index.len());
565 let mut crate_paths = vec![];
567 let Cache { ref mut search_index, ref orphan_impl_items, ref paths, .. } = *cache;
569 // Attach all orphan items to the type's definition if the type
570 // has since been learned.
571 for &(did, ref item) in orphan_impl_items {
572 if let Some(&(ref fqp, _)) = paths.get(&did) {
573 search_index.push(IndexItem {
575 name: item.name.clone().unwrap(),
576 path: fqp[..fqp.len() - 1].join("::"),
577 desc: shorten(plain_summary_line(item.doc_value())),
580 search_type: get_index_search_type(&item),
585 // Reduce `DefId` in paths into smaller sequential numbers,
586 // and prune the paths that do not appear in the index.
587 let mut lastpath = String::new();
588 let mut lastpathid = 0usize;
590 for item in search_index {
591 item.parent_idx = item.parent.and_then(|defid| {
592 if defid_to_pathid.contains_key(&defid) {
593 defid_to_pathid.get(&defid).map(|x| *x)
595 let pathid = lastpathid;
596 defid_to_pathid.insert(defid, pathid);
599 if let Some(&(ref fqp, short)) = paths.get(&defid) {
600 crate_paths.push((short, fqp.last().unwrap().clone()));
608 // Omit the parent path if it is same to that of the prior item.
609 if lastpath == item.path {
612 lastpath = item.path.clone();
614 crate_items.push(&*item);
617 let crate_doc = krate
620 .map(|module| shorten(plain_summary_line(module.doc_value())))
621 .unwrap_or(String::new());
624 struct CrateData<'a> {
626 #[serde(rename = "i")]
627 items: Vec<&'a IndexItem>,
628 #[serde(rename = "p")]
629 paths: Vec<(ItemType, String)>,
632 // Collect the index into a string
634 r#"searchIndex["{}"] = {};"#,
636 serde_json::to_string(&CrateData {
641 .expect("failed serde conversion")
645 fn get_index_search_type(item: &clean::Item) -> Option<IndexItemFunctionType> {
646 let (all_types, ret_types) = match item.inner {
647 clean::FunctionItem(ref f) => (&f.all_types, &f.ret_types),
648 clean::MethodItem(ref m) => (&m.all_types, &m.ret_types),
649 clean::TyMethodItem(ref m) => (&m.all_types, &m.ret_types),
653 let inputs = all_types
655 .map(|(ty, kind)| TypeWithKind::from((get_index_type(&ty), *kind)))
656 .filter(|a| a.ty.name.is_some())
658 let output = ret_types
660 .map(|(ty, kind)| TypeWithKind::from((get_index_type(&ty), *kind)))
661 .filter(|a| a.ty.name.is_some())
662 .collect::<Vec<_>>();
663 let output = if output.is_empty() { None } else { Some(output) };
665 Some(IndexItemFunctionType { inputs, output })
668 fn get_index_type(clean_type: &clean::Type) -> RenderType {
670 ty: clean_type.def_id(),
672 name: get_index_type_name(clean_type, true).map(|s| s.to_ascii_lowercase()),
673 generics: get_generics(clean_type),
678 fn get_index_type_name(clean_type: &clean::Type, accept_generic: bool) -> Option<String> {
680 clean::ResolvedPath { ref path, .. } => {
681 let segments = &path.segments;
682 let path_segment = segments.iter().last().unwrap_or_else(|| panic!(
683 "get_index_type_name(clean_type: {:?}, accept_generic: {:?}) had length zero path",
684 clean_type, accept_generic
686 Some(path_segment.name.clone())
688 clean::Generic(ref s) if accept_generic => Some(s.clone()),
689 clean::Primitive(ref p) => Some(format!("{:?}", p)),
690 clean::BorrowedRef { ref type_, .. } => get_index_type_name(type_, accept_generic),
691 // FIXME: add all from clean::Type.
696 fn get_generics(clean_type: &clean::Type) -> Option<Vec<Generic>> {
697 clean_type.generics().and_then(|types| {
701 if let Some(name) = get_index_type_name(t, false) {
702 Some(Generic { name: name.to_ascii_lowercase(), defid: t.def_id(), idx: None })
707 .collect::<Vec<_>>();
708 if r.is_empty() { None } else { Some(r) }