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::{
11 FnRetTy, Function, GenericBound, Generics, ItemId, Type, WherePredicate,
13 use crate::formats::cache::{Cache, OrphanImplItem};
14 use crate::formats::item_type::ItemType;
15 use crate::html::format::join_with_double_colon;
16 use crate::html::markdown::short_markdown_summary;
17 use crate::html::render::{IndexItem, IndexItemFunctionType, RenderType, RenderTypeId};
19 /// Builds the search index from the collected metadata
20 pub(crate) fn build_index<'tcx>(
25 let mut itemid_to_pathid = FxHashMap::default();
26 let mut primitives = FxHashMap::default();
27 let mut crate_paths = vec![];
29 // Attach all orphan items to the type's definition if the type
30 // has since been learned.
31 for &OrphanImplItem { parent, ref item, ref impl_generics } in &cache.orphan_impl_items {
32 if let Some((fqp, _)) = cache.paths.get(&parent) {
35 .map_or_else(String::new, |s| short_markdown_summary(&s, &item.link_names(cache)));
36 cache.search_index.push(IndexItem {
38 name: item.name.unwrap(),
39 path: join_with_double_colon(&fqp[..fqp.len() - 1]),
43 search_type: get_function_type_for_search(item, tcx, impl_generics.as_ref(), cache),
44 aliases: item.attrs.get_doc_aliases(),
52 .map_or_else(String::new, |s| short_markdown_summary(&s, &krate.module.link_names(cache)));
54 // Aliases added through `#[doc(alias = "...")]`. Since a few items can have the same alias,
55 // we need the alias element to have an array of items.
56 let mut aliases: BTreeMap<String, Vec<usize>> = BTreeMap::new();
58 // Sort search index items. This improves the compressibility of the search index.
59 cache.search_index.sort_unstable_by(|k1, k2| {
60 // `sort_unstable_by_key` produces lifetime errors
61 let k1 = (&k1.path, k1.name.as_str(), &k1.ty, &k1.parent);
62 let k2 = (&k2.path, k2.name.as_str(), &k2.ty, &k2.parent);
63 std::cmp::Ord::cmp(&k1, &k2)
66 // Set up alias indexes.
67 for (i, item) in cache.search_index.iter().enumerate() {
68 for alias in &item.aliases[..] {
69 aliases.entry(alias.as_str().to_lowercase()).or_default().push(i);
73 // Reduce `DefId` in paths into smaller sequential numbers,
74 // and prune the paths that do not appear in the index.
75 let mut lastpath = "";
76 let mut lastpathid = 0usize;
78 // First, on function signatures
79 let mut search_index = std::mem::replace(&mut cache.search_index, Vec::new());
80 for item in search_index.iter_mut() {
81 fn insert_into_map<F: std::hash::Hash + Eq>(
83 map: &mut FxHashMap<F, usize>,
85 lastpathid: &mut usize,
86 crate_paths: &mut Vec<(ItemType, Symbol)>,
90 match map.entry(itemid) {
91 Entry::Occupied(entry) => ty.id = Some(RenderTypeId::Index(*entry.get())),
92 Entry::Vacant(entry) => {
93 let pathid = *lastpathid;
96 crate_paths.push((item_type, path));
97 ty.id = Some(RenderTypeId::Index(pathid));
102 fn convert_render_type(
105 itemid_to_pathid: &mut FxHashMap<ItemId, usize>,
106 primitives: &mut FxHashMap<Symbol, usize>,
107 lastpathid: &mut usize,
108 crate_paths: &mut Vec<(ItemType, Symbol)>,
110 if let Some(generics) = &mut ty.generics {
111 for item in generics {
122 let Cache { ref paths, ref external_paths, .. } = *cache;
123 let Some(id) = ty.id.clone() else {
124 assert!(ty.generics.is_some());
128 RenderTypeId::DefId(defid) => {
129 if let Some(&(ref fqp, item_type)) =
130 paths.get(&defid).or_else(|| external_paths.get(&defid))
135 ItemId::DefId(defid),
139 *fqp.last().unwrap(),
145 RenderTypeId::Primitive(primitive) => {
146 let sym = primitive.as_sym();
157 RenderTypeId::Index(_) => {}
160 if let Some(search_type) = &mut item.search_type {
161 for item in &mut search_type.inputs {
165 &mut itemid_to_pathid,
171 for item in &mut search_type.output {
175 &mut itemid_to_pathid,
184 let Cache { ref paths, .. } = *cache;
186 // Then, on parent modules
187 let crate_items: Vec<&IndexItem> = search_index
191 item.parent.and_then(|defid| match itemid_to_pathid.entry(ItemId::DefId(defid)) {
192 Entry::Occupied(entry) => Some(*entry.get()),
193 Entry::Vacant(entry) => {
194 let pathid = lastpathid;
195 entry.insert(pathid);
198 if let Some(&(ref fqp, short)) = paths.get(&defid) {
199 crate_paths.push((short, *fqp.last().unwrap()));
207 // Omit the parent path if it is same to that of the prior item.
208 if lastpath == &item.path {
211 lastpath = &item.path;
218 struct CrateData<'a> {
220 items: Vec<&'a IndexItem>,
221 paths: Vec<(ItemType, Symbol)>,
222 // The String is alias name and the vec is the list of the elements with this alias.
224 // To be noted: the `usize` elements are indexes to `items`.
225 aliases: &'a BTreeMap<String, Vec<usize>>,
228 impl<'a> Serialize for CrateData<'a> {
229 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
233 let has_aliases = !self.aliases.is_empty();
235 serializer.serialize_struct("CrateData", if has_aliases { 9 } else { 8 })?;
236 crate_data.serialize_field("doc", &self.doc)?;
237 crate_data.serialize_field(
239 &self.items.iter().map(|item| &item.ty).collect::<Vec<_>>(),
241 crate_data.serialize_field(
243 &self.items.iter().map(|item| item.name.as_str()).collect::<Vec<_>>(),
245 crate_data.serialize_field(
247 &self.items.iter().map(|item| &item.path).collect::<Vec<_>>(),
249 crate_data.serialize_field(
251 &self.items.iter().map(|item| &item.desc).collect::<Vec<_>>(),
253 crate_data.serialize_field(
260 item.parent.is_some(),
261 item.parent_idx.is_some(),
262 "`{}` is missing idx",
265 // 0 is a sentinel, everything else is one-indexed
266 item.parent_idx.map(|x| x + 1).unwrap_or(0)
268 .collect::<Vec<_>>(),
270 crate_data.serialize_field(
276 // Fake option to get `0` out as a sentinel instead of `null`.
277 // We want to use `0` because it's three less bytes.
278 enum FunctionOption<'a> {
279 Function(&'a IndexItemFunctionType),
282 impl<'a> Serialize for FunctionOption<'a> {
283 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
288 FunctionOption::None => 0.serialize(serializer),
289 FunctionOption::Function(ty) => ty.serialize(serializer),
293 match &item.search_type {
294 Some(ty) => FunctionOption::Function(ty),
295 None => FunctionOption::None,
298 .collect::<Vec<_>>(),
300 crate_data.serialize_field(
302 &self.paths.iter().map(|(it, s)| (it, s.as_str())).collect::<Vec<_>>(),
305 crate_data.serialize_field("a", &self.aliases)?;
311 // Collect the index into a string
315 serde_json::to_string(&CrateData {
321 .expect("failed serde conversion")
322 // All these `replace` calls are because we have to go through JS string for JSON content.
323 .replace('\\', r"\\")
324 .replace('\'', r"\'")
325 // We need to escape double quotes for the JSON.
326 .replace("\\\"", "\\\\\"")
330 pub(crate) fn get_function_type_for_search<'tcx>(
333 impl_generics: Option<&(clean::Type, clean::Generics)>,
335 ) -> Option<IndexItemFunctionType> {
336 let (mut inputs, mut output) = match *item.kind {
337 clean::FunctionItem(ref f) => get_fn_inputs_and_outputs(f, tcx, impl_generics, cache),
338 clean::MethodItem(ref m, _) => get_fn_inputs_and_outputs(m, tcx, impl_generics, cache),
339 clean::TyMethodItem(ref m) => get_fn_inputs_and_outputs(m, tcx, impl_generics, cache),
343 inputs.retain(|a| a.id.is_some() || a.generics.is_some());
344 output.retain(|a| a.id.is_some() || a.generics.is_some());
346 Some(IndexItemFunctionType { inputs, output })
349 fn get_index_type(clean_type: &clean::Type, generics: Vec<RenderType>) -> RenderType {
351 id: get_index_type_id(clean_type),
352 generics: if generics.is_empty() { None } else { Some(generics) },
356 fn get_index_type_id(clean_type: &clean::Type) -> Option<RenderTypeId> {
358 clean::Type::Path { ref path, .. } => Some(RenderTypeId::DefId(path.def_id())),
359 clean::DynTrait(ref bounds, _) => {
360 bounds.get(0).map(|b| RenderTypeId::DefId(b.trait_.def_id()))
362 clean::Primitive(p) => Some(RenderTypeId::Primitive(p)),
363 clean::BorrowedRef { ref type_, .. } | clean::RawPointer(_, ref type_) => {
364 get_index_type_id(type_)
366 clean::BareFunction(_)
368 | clean::ImplTrait(_)
372 | clean::QPath { .. }
373 | clean::Infer => None,
377 /// The point of this function is to replace bounds with types.
379 /// i.e. `[T, U]` when you have the following bounds: `T: Display, U: Option<T>` will return
380 /// `[Display, Option]`. If a type parameter has no trait bound, it is discarded.
382 /// Important note: It goes through generics recursively. So if you have
383 /// `T: Option<Result<(), ()>>`, it'll go into `Option` and then into `Result`.
384 #[instrument(level = "trace", skip(tcx, res, cache))]
385 fn add_generics_and_bounds_as_types<'tcx, 'a>(
386 self_: Option<&'a Type>,
391 res: &mut Vec<RenderType>,
394 fn insert_ty(res: &mut Vec<RenderType>, ty: Type, mut generics: Vec<RenderType>) {
395 // generics and impl trait are both identified by their generics,
396 // rather than a type name itself
397 let anonymous = ty.is_full_generic() || ty.is_impl_trait();
398 let generics_empty = generics.is_empty();
402 // This is a type parameter with no trait bounds (for example: `T` in
403 // `fn f<T>(p: T)`, so not useful for the rustdoc search because we would end up
404 // with an empty type with an empty name. Let's just discard it.
406 } else if generics.len() == 1 {
407 // In this case, no need to go through an intermediate state if the type parameter
408 // contains only one trait bound.
412 // `fn foo<T: Display>(r: Option<T>) {}`
414 // In this case, it would contain:
429 // After removing the intermediate (unnecessary) type parameter, it'll become:
441 // To be noted that it can work if there is ONLY ONE trait bound, otherwise we still
442 // need to keep it as is!
443 res.push(generics.pop().unwrap());
447 let index_ty = get_index_type(&ty, generics);
448 if index_ty.id.is_none() && generics_empty {
455 // FIXME: remove this whole recurse thing when the recursion bug is fixed
456 // See #59502 for the original issue.
460 // First, check if it's "Self".
461 let arg = if let Some(self_) = self_ {
463 Type::BorrowedRef { type_, .. } if type_.is_self_type() => self_,
464 type_ if type_.is_self_type() => self_,
471 // If this argument is a type parameter and not a trait bound or a type, we need to look
473 if let Type::Generic(arg_s) = *arg {
474 // First we check if the bounds are in a `where` predicate...
475 if let Some(where_pred) = generics.where_predicates.iter().find(|g| match g {
476 WherePredicate::BoundPredicate { ty, .. } => ty.def_id(cache) == arg.def_id(cache),
479 let mut ty_generics = Vec::new();
480 let bounds = where_pred.get_bounds().unwrap_or_else(|| &[]);
481 for bound in bounds.iter() {
482 if let GenericBound::TraitBound(poly_trait, _) = bound {
483 for param_def in poly_trait.generic_params.iter() {
484 match ¶m_def.kind {
485 clean::GenericParamDefKind::Type { default: Some(ty), .. } => {
486 add_generics_and_bounds_as_types(
501 insert_ty(res, arg.clone(), ty_generics);
503 // Otherwise we check if the trait bounds are "inlined" like `T: Option<u32>`...
504 if let Some(bound) = generics.params.iter().find(|g| g.is_type() && g.name == arg_s) {
505 let mut ty_generics = Vec::new();
506 for bound in bound.get_bounds().unwrap_or(&[]) {
507 if let Some(path) = bound.get_trait_path() {
508 let ty = Type::Path { path };
509 add_generics_and_bounds_as_types(
520 insert_ty(res, arg.clone(), ty_generics);
522 } else if let Type::ImplTrait(ref bounds) = *arg {
523 let mut ty_generics = Vec::new();
524 for bound in bounds {
525 if let Some(path) = bound.get_trait_path() {
526 let ty = Type::Path { path };
527 add_generics_and_bounds_as_types(
538 insert_ty(res, arg.clone(), ty_generics);
540 // This is not a type parameter. So for example if we have `T, U: Option<T>`, and we're
541 // looking at `Option`, we enter this "else" condition, otherwise if it's `T`, we don't.
543 // So in here, we can add it directly and look for its own type parameters (so for `Option`,
544 // we will look for them but not for `T`).
545 let mut ty_generics = Vec::new();
546 if let Some(arg_generics) = arg.generics() {
547 for gen in arg_generics.iter() {
548 add_generics_and_bounds_as_types(
559 insert_ty(res, arg.clone(), ty_generics);
563 /// Return the full list of types when bounds have been resolved.
565 /// i.e. `fn foo<A: Display, B: Option<A>>(x: u32, y: B)` will return
566 /// `[u32, Display, Option]`.
567 fn get_fn_inputs_and_outputs<'tcx>(
570 impl_generics: Option<&(clean::Type, clean::Generics)>,
572 ) -> (Vec<RenderType>, Vec<RenderType>) {
573 let decl = &func.decl;
575 let combined_generics;
576 let (self_, generics) = if let Some((impl_self, impl_generics)) = impl_generics {
577 match (impl_generics.is_empty(), func.generics.is_empty()) {
578 (true, _) => (Some(impl_self), &func.generics),
579 (_, true) => (Some(impl_self), impl_generics),
582 func.generics.params.iter().chain(&impl_generics.params).cloned().collect();
583 let where_predicates = func
587 .chain(&impl_generics.where_predicates)
590 combined_generics = clean::Generics { params, where_predicates };
591 (Some(impl_self), &combined_generics)
595 (None, &func.generics)
598 let mut all_types = Vec::new();
599 for arg in decl.inputs.values.iter() {
600 let mut args = Vec::new();
601 add_generics_and_bounds_as_types(self_, generics, &arg.type_, tcx, 0, &mut args, cache);
602 if !args.is_empty() {
603 all_types.extend(args);
605 all_types.push(get_index_type(&arg.type_, vec![]));
609 let mut ret_types = Vec::new();
611 FnRetTy::Return(ref return_type) => {
612 add_generics_and_bounds_as_types(
621 if ret_types.is_empty() {
622 ret_types.push(get_index_type(return_type, vec![]));
627 (all_types, ret_types)