1 use std::collections::hash_map::Entry;
2 use std::collections::BTreeMap;
4 use rustc_data_structures::fx::FxHashMap;
5 use rustc_middle::ty::TyCtxt;
6 use rustc_span::symbol::Symbol;
7 use serde::ser::{Serialize, SerializeStruct, Serializer};
10 use crate::clean::types::{FnDecl, FnRetTy, GenericBound, Generics, Type, WherePredicate};
11 use crate::formats::cache::Cache;
12 use crate::formats::item_type::ItemType;
13 use crate::html::markdown::short_markdown_summary;
14 use crate::html::render::{IndexItem, IndexItemFunctionType, RenderType, TypeWithKind};
16 /// Indicates where an external crate can be found.
17 crate enum ExternalLocation {
18 /// Remote URL root of the external crate
20 /// This external crate can be found in the local doc/ folder
22 /// The external crate could not be found.
26 /// Builds the search index from the collected metadata
27 crate fn build_index<'tcx>(krate: &clean::Crate, cache: &mut Cache, tcx: TyCtxt<'tcx>) -> String {
28 let mut defid_to_pathid = FxHashMap::default();
29 let mut crate_items = Vec::with_capacity(cache.search_index.len());
30 let mut crate_paths = vec![];
32 // Attach all orphan items to the type's definition if the type
33 // has since been learned.
34 for &(did, ref item) in &cache.orphan_impl_items {
35 if let Some(&(ref fqp, _)) = cache.paths.get(&did) {
38 .map_or_else(String::new, |s| short_markdown_summary(&s, &item.link_names(cache)));
39 cache.search_index.push(IndexItem {
41 name: item.name.unwrap().to_string(),
42 path: fqp[..fqp.len() - 1].join("::"),
46 search_type: get_index_search_type(item, tcx),
47 aliases: item.attrs.get_doc_aliases(),
55 .map_or_else(String::new, |s| short_markdown_summary(&s, &krate.module.link_names(cache)));
57 let Cache { ref mut search_index, ref paths, .. } = *cache;
59 // Aliases added through `#[doc(alias = "...")]`. Since a few items can have the same alias,
60 // we need the alias element to have an array of items.
61 let mut aliases: BTreeMap<String, Vec<usize>> = BTreeMap::new();
63 // Sort search index items. This improves the compressibility of the search index.
64 search_index.sort_unstable_by(|k1, k2| {
65 // `sort_unstable_by_key` produces lifetime errors
66 let k1 = (&k1.path, &k1.name, &k1.ty, &k1.parent);
67 let k2 = (&k2.path, &k2.name, &k2.ty, &k2.parent);
68 std::cmp::Ord::cmp(&k1, &k2)
71 // Set up alias indexes.
72 for (i, item) in search_index.iter().enumerate() {
73 for alias in &item.aliases[..] {
74 aliases.entry(alias.to_lowercase()).or_insert_with(Vec::new).push(i);
78 // Reduce `DefId` in paths into smaller sequential numbers,
79 // and prune the paths that do not appear in the index.
80 let mut lastpath = String::new();
81 let mut lastpathid = 0usize;
83 for item in search_index {
84 item.parent_idx = item.parent.and_then(|defid| match defid_to_pathid.entry(defid) {
85 Entry::Occupied(entry) => Some(*entry.get()),
86 Entry::Vacant(entry) => {
87 let pathid = lastpathid;
91 if let Some(&(ref fqp, short)) = paths.get(&defid) {
92 crate_paths.push((short, fqp.last().unwrap().clone()));
100 // Omit the parent path if it is same to that of the prior item.
101 if lastpath == item.path {
104 lastpath = item.path.clone();
106 crate_items.push(&*item);
109 struct CrateData<'a> {
111 items: Vec<&'a IndexItem>,
112 paths: Vec<(ItemType, String)>,
113 // The String is alias name and the vec is the list of the elements with this alias.
115 // To be noted: the `usize` elements are indexes to `items`.
116 aliases: &'a BTreeMap<String, Vec<usize>>,
119 impl<'a> Serialize for CrateData<'a> {
120 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
124 let has_aliases = !self.aliases.is_empty();
126 serializer.serialize_struct("CrateData", if has_aliases { 9 } else { 8 })?;
127 crate_data.serialize_field("doc", &self.doc)?;
128 crate_data.serialize_field(
130 &self.items.iter().map(|item| &item.ty).collect::<Vec<_>>(),
132 crate_data.serialize_field(
134 &self.items.iter().map(|item| &item.name).collect::<Vec<_>>(),
136 crate_data.serialize_field(
138 &self.items.iter().map(|item| &item.path).collect::<Vec<_>>(),
140 crate_data.serialize_field(
142 &self.items.iter().map(|item| &item.desc).collect::<Vec<_>>(),
144 crate_data.serialize_field(
151 item.parent.is_some(),
152 item.parent_idx.is_some(),
153 "`{}` is missing idx",
156 item.parent_idx.map(|x| x + 1).unwrap_or(0)
158 .collect::<Vec<_>>(),
160 crate_data.serialize_field(
162 &self.items.iter().map(|item| &item.search_type).collect::<Vec<_>>(),
164 crate_data.serialize_field("p", &self.paths)?;
166 crate_data.serialize_field("a", &self.aliases)?;
172 // Collect the index into a string
176 serde_json::to_string(&CrateData {
182 .expect("failed serde conversion")
183 // All these `replace` calls are because we have to go through JS string for JSON content.
184 .replace(r"\", r"\\")
186 // We need to escape double quotes for the JSON.
187 .replace("\\\"", "\\\\\"")
191 crate fn get_index_search_type<'tcx>(
194 ) -> Option<IndexItemFunctionType> {
195 let (mut inputs, mut output) = match *item.kind {
196 clean::FunctionItem(ref f) => get_all_types(&f.generics, &f.decl, tcx),
197 clean::MethodItem(ref m, _) => get_all_types(&m.generics, &m.decl, tcx),
198 clean::TyMethodItem(ref m) => get_all_types(&m.generics, &m.decl, tcx),
202 inputs.retain(|a| a.ty.name.is_some());
203 output.retain(|a| a.ty.name.is_some());
204 let output = if output.is_empty() { None } else { Some(output) };
206 Some(IndexItemFunctionType { inputs, output })
209 fn get_index_type(clean_type: &clean::Type, generics: Vec<TypeWithKind>) -> RenderType {
211 name: get_index_type_name(clean_type, true).map(|s| s.as_str().to_ascii_lowercase()),
212 generics: if generics.is_empty() { None } else { Some(generics) },
216 fn get_index_type_name(clean_type: &clean::Type, accept_generic: bool) -> Option<Symbol> {
218 clean::ResolvedPath { ref path, .. } => {
219 let path_segment = path.segments.last().unwrap();
220 Some(path_segment.name)
222 clean::DynTrait(ref bounds, _) => {
223 let path = &bounds[0].trait_;
224 Some(path.segments.last().unwrap().name)
226 clean::Generic(s) if accept_generic => Some(s),
227 clean::Primitive(ref p) => Some(p.as_sym()),
228 clean::BorrowedRef { ref type_, .. } => get_index_type_name(type_, accept_generic),
230 | clean::BareFunction(_)
234 | clean::RawPointer(_, _)
235 | clean::QPath { .. }
237 | clean::ImplTrait(_) => None,
241 /// The point of this function is to replace bounds with types.
243 /// i.e. `[T, U]` when you have the following bounds: `T: Display, U: Option<T>` will return
244 /// `[Display, Option]` (we just returns the list of the types, we don't care about the
245 /// wrapped types in here).
246 crate fn get_real_types<'tcx>(
251 res: &mut Vec<TypeWithKind>,
254 res: &mut Vec<TypeWithKind>,
257 mut generics: Vec<TypeWithKind>,
259 let is_full_generic = ty.is_full_generic();
261 if is_full_generic && generics.len() == 1 {
262 // In this case, no need to go through an intermediate state if the generics
263 // contains only one element.
267 // fn foo<T: Display>(r: Option<T>) {}
269 // In this case, it would contain:
284 // After removing the intermediate (unnecessary) full generic, it'll become:
296 // To be noted that it can work if there is ONLY ONE generic, otherwise we still
297 // need to keep it as is!
298 res.push(generics.pop().unwrap());
301 let mut index_ty = get_index_type(&ty, generics);
302 if index_ty.name.as_ref().map(|s| s.is_empty()).unwrap_or(true) {
306 // We remove the name of the full generic because we have no use for it.
307 index_ty.name = Some(String::new());
308 res.push(TypeWithKind::from((index_ty, ItemType::Generic)));
309 } else if let Some(kind) = ty.def_id_no_primitives().map(|did| tcx.def_kind(did).into()) {
310 res.push(TypeWithKind::from((index_ty, kind)));
311 } else if ty.is_primitive() {
312 // This is a primitive, let's store it as such.
313 res.push(TypeWithKind::from((index_ty, ItemType::Primitive)));
318 // FIXME: remove this whole recurse thing when the recursion bug is fixed
322 if let Type::Generic(arg_s) = *arg {
323 if let Some(where_pred) = generics.where_predicates.iter().find(|g| match g {
324 WherePredicate::BoundPredicate { ty, .. } => {
325 ty.def_id_no_primitives() == arg.def_id_no_primitives()
329 let mut ty_generics = Vec::new();
330 let bounds = where_pred.get_bounds().unwrap_or_else(|| &[]);
331 for bound in bounds.iter() {
332 if let GenericBound::TraitBound(poly_trait, _) = bound {
333 for x in poly_trait.generic_params.iter() {
337 if let Some(ty) = x.get_type() {
338 get_real_types(generics, &ty, tcx, recurse + 1, &mut ty_generics);
343 insert_ty(res, tcx, arg.clone(), ty_generics);
345 if let Some(bound) = generics.params.iter().find(|g| g.is_type() && g.name == arg_s) {
346 let mut ty_generics = Vec::new();
347 for bound in bound.get_bounds().unwrap_or(&[]) {
348 if let Some(path) = bound.get_trait_path() {
349 let ty = Type::ResolvedPath { did: path.def_id(), path };
350 get_real_types(generics, &ty, tcx, recurse + 1, &mut ty_generics);
353 insert_ty(res, tcx, arg.clone(), ty_generics);
356 let mut ty_generics = Vec::new();
357 if let Some(arg_generics) = arg.generics() {
358 for gen in arg_generics.iter() {
359 get_real_types(generics, gen, tcx, recurse + 1, &mut ty_generics);
362 insert_ty(res, tcx, arg.clone(), ty_generics);
366 /// Return the full list of types when bounds have been resolved.
368 /// i.e. `fn foo<A: Display, B: Option<A>>(x: u32, y: B)` will return
369 /// `[u32, Display, Option]`.
370 crate fn get_all_types<'tcx>(
374 ) -> (Vec<TypeWithKind>, Vec<TypeWithKind>) {
375 let mut all_types = Vec::new();
376 for arg in decl.inputs.values.iter() {
377 if arg.type_.is_self_type() {
380 // FIXME: performance wise, it'd be much better to move `args` declaration outside of the
381 // loop and replace this line with `args.clear()`.
382 let mut args = Vec::new();
383 get_real_types(generics, &arg.type_, tcx, 0, &mut args);
384 if !args.is_empty() {
385 // FIXME: once back to performance improvements, replace this line with:
386 // `all_types.extend(args.drain(..));`.
387 all_types.extend(args);
389 if let Some(kind) = arg.type_.def_id_no_primitives().map(|did| tcx.def_kind(did).into())
391 all_types.push(TypeWithKind::from((get_index_type(&arg.type_, vec![]), kind)));
396 let mut ret_types = Vec::new();
398 FnRetTy::Return(ref return_type) => {
399 get_real_types(generics, return_type, tcx, 0, &mut ret_types);
400 if ret_types.is_empty() {
402 return_type.def_id_no_primitives().map(|did| tcx.def_kind(did).into())
404 ret_types.push(TypeWithKind::from((get_index_type(return_type, vec![]), kind)));
410 (all_types, ret_types)