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::def_id::LOCAL_CRATE;
7 use rustc_span::symbol::Symbol;
8 use serde::ser::{Serialize, SerializeStruct, Serializer};
11 use crate::clean::types::{
12 FnRetTy, Function, GenericBound, Generics, ItemId, Type, WherePredicate,
14 use crate::formats::cache::{Cache, OrphanImplItem};
15 use crate::formats::item_type::ItemType;
16 use crate::html::format::join_with_double_colon;
17 use crate::html::markdown::short_markdown_summary;
18 use crate::html::render::{IndexItem, IndexItemFunctionType, RenderType, RenderTypeId};
20 /// Builds the search index from the collected metadata
21 pub(crate) fn build_index<'tcx>(
26 let mut itemid_to_pathid = 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(&(ref 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().to_string(),
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, &k1.ty, &k1.parent);
62 let k2 = (&k2.path, &k2.name, &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 convert_render_type(
84 itemid_to_pathid: &mut FxHashMap<ItemId, usize>,
85 lastpathid: &mut usize,
86 crate_paths: &mut Vec<(ItemType, Symbol)>,
88 if let Some(generics) = &mut ty.generics {
89 for item in generics {
90 convert_render_type(item, cache, itemid_to_pathid, lastpathid, crate_paths);
93 let Cache { ref paths, ref external_paths, .. } = *cache;
94 let Some(id) = ty.id.clone() else {
95 assert!(ty.generics.is_some());
98 let (itemid, path, item_type) = match id {
99 RenderTypeId::DefId(defid) => {
100 if let Some(&(ref fqp, item_type)) =
101 paths.get(&defid).or_else(|| external_paths.get(&defid))
103 (ItemId::DefId(defid), *fqp.last().unwrap(), item_type)
109 RenderTypeId::Primitive(primitive) => (
110 ItemId::Primitive(primitive, LOCAL_CRATE),
114 RenderTypeId::Index(_) => return,
116 match itemid_to_pathid.entry(itemid) {
117 Entry::Occupied(entry) => ty.id = Some(RenderTypeId::Index(*entry.get())),
118 Entry::Vacant(entry) => {
119 let pathid = *lastpathid;
120 entry.insert(pathid);
122 crate_paths.push((item_type, path));
123 ty.id = Some(RenderTypeId::Index(pathid));
127 if let Some(search_type) = &mut item.search_type {
128 for item in &mut search_type.inputs {
132 &mut itemid_to_pathid,
137 for item in &mut search_type.output {
141 &mut itemid_to_pathid,
149 let Cache { ref paths, .. } = *cache;
151 // Then, on parent modules
152 let crate_items: Vec<&IndexItem> = search_index
156 item.parent.and_then(|defid| match itemid_to_pathid.entry(ItemId::DefId(defid)) {
157 Entry::Occupied(entry) => Some(*entry.get()),
158 Entry::Vacant(entry) => {
159 let pathid = lastpathid;
160 entry.insert(pathid);
163 if let Some(&(ref fqp, short)) = paths.get(&defid) {
164 crate_paths.push((short, *fqp.last().unwrap()));
172 // Omit the parent path if it is same to that of the prior item.
173 if lastpath == &item.path {
176 lastpath = &item.path;
183 struct CrateData<'a> {
185 items: Vec<&'a IndexItem>,
186 paths: Vec<(ItemType, Symbol)>,
187 // The String is alias name and the vec is the list of the elements with this alias.
189 // To be noted: the `usize` elements are indexes to `items`.
190 aliases: &'a BTreeMap<String, Vec<usize>>,
193 impl<'a> Serialize for CrateData<'a> {
194 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
198 let has_aliases = !self.aliases.is_empty();
200 serializer.serialize_struct("CrateData", if has_aliases { 9 } else { 8 })?;
201 crate_data.serialize_field("doc", &self.doc)?;
202 crate_data.serialize_field(
204 &self.items.iter().map(|item| &item.ty).collect::<Vec<_>>(),
206 crate_data.serialize_field(
208 &self.items.iter().map(|item| &item.name).collect::<Vec<_>>(),
210 crate_data.serialize_field(
212 &self.items.iter().map(|item| &item.path).collect::<Vec<_>>(),
214 crate_data.serialize_field(
216 &self.items.iter().map(|item| &item.desc).collect::<Vec<_>>(),
218 crate_data.serialize_field(
225 item.parent.is_some(),
226 item.parent_idx.is_some(),
227 "`{}` is missing idx",
230 // 0 is a sentinel, everything else is one-indexed
231 item.parent_idx.map(|x| x + 1).unwrap_or(0)
233 .collect::<Vec<_>>(),
235 crate_data.serialize_field(
241 // Fake option to get `0` out as a sentinel instead of `null`.
242 // We want to use `0` because it's three less bytes.
243 enum FunctionOption<'a> {
244 Function(&'a IndexItemFunctionType),
247 impl<'a> Serialize for FunctionOption<'a> {
248 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
253 FunctionOption::None => 0.serialize(serializer),
254 FunctionOption::Function(ty) => ty.serialize(serializer),
258 match &item.search_type {
259 Some(ty) => FunctionOption::Function(ty),
260 None => FunctionOption::None,
263 .collect::<Vec<_>>(),
265 crate_data.serialize_field(
267 &self.paths.iter().map(|(it, s)| (it, s.to_string())).collect::<Vec<_>>(),
270 crate_data.serialize_field("a", &self.aliases)?;
276 // Collect the index into a string
280 serde_json::to_string(&CrateData {
286 .expect("failed serde conversion")
287 // All these `replace` calls are because we have to go through JS string for JSON content.
288 .replace('\\', r"\\")
289 .replace('\'', r"\'")
290 // We need to escape double quotes for the JSON.
291 .replace("\\\"", "\\\\\"")
295 pub(crate) fn get_function_type_for_search<'tcx>(
298 impl_generics: Option<&(clean::Type, clean::Generics)>,
300 ) -> Option<IndexItemFunctionType> {
301 let (mut inputs, mut output) = match *item.kind {
302 clean::FunctionItem(ref f) => get_fn_inputs_and_outputs(f, tcx, impl_generics, cache),
303 clean::MethodItem(ref m, _) => get_fn_inputs_and_outputs(m, tcx, impl_generics, cache),
304 clean::TyMethodItem(ref m) => get_fn_inputs_and_outputs(m, tcx, impl_generics, cache),
308 inputs.retain(|a| a.id.is_some() || a.generics.is_some());
309 output.retain(|a| a.id.is_some() || a.generics.is_some());
311 Some(IndexItemFunctionType { inputs, output })
314 fn get_index_type(clean_type: &clean::Type, generics: Vec<RenderType>) -> RenderType {
316 id: get_index_type_id(clean_type),
317 generics: if generics.is_empty() { None } else { Some(generics) },
321 fn get_index_type_id(clean_type: &clean::Type) -> Option<RenderTypeId> {
323 clean::Type::Path { ref path, .. } => Some(RenderTypeId::DefId(path.def_id())),
324 clean::DynTrait(ref bounds, _) => {
325 let path = &bounds[0].trait_;
326 Some(RenderTypeId::DefId(path.def_id()))
328 clean::Primitive(p) => Some(RenderTypeId::Primitive(p)),
329 clean::BorrowedRef { ref type_, .. } | clean::RawPointer(_, ref type_) => {
330 get_index_type_id(type_)
332 clean::BareFunction(_)
334 | clean::ImplTrait(_)
338 | clean::QPath { .. }
339 | clean::Infer => None,
343 /// The point of this function is to replace bounds with types.
345 /// i.e. `[T, U]` when you have the following bounds: `T: Display, U: Option<T>` will return
346 /// `[Display, Option]`. If a type parameter has no trait bound, it is discarded.
348 /// Important note: It goes through generics recursively. So if you have
349 /// `T: Option<Result<(), ()>>`, it'll go into `Option` and then into `Result`.
350 #[instrument(level = "trace", skip(tcx, res, cache))]
351 fn add_generics_and_bounds_as_types<'tcx, 'a>(
352 self_: Option<&'a Type>,
357 res: &mut Vec<RenderType>,
360 fn insert_ty(res: &mut Vec<RenderType>, ty: Type, mut generics: Vec<RenderType>) {
361 // generics and impl trait are both identified by their generics,
362 // rather than a type name itself
363 let anonymous = ty.is_full_generic() || ty.is_impl_trait();
364 let generics_empty = generics.is_empty();
368 // This is a type parameter with no trait bounds (for example: `T` in
369 // `fn f<T>(p: T)`, so not useful for the rustdoc search because we would end up
370 // with an empty type with an empty name. Let's just discard it.
372 } else if generics.len() == 1 {
373 // In this case, no need to go through an intermediate state if the type parameter
374 // contains only one trait bound.
378 // `fn foo<T: Display>(r: Option<T>) {}`
380 // In this case, it would contain:
395 // After removing the intermediate (unnecessary) type parameter, it'll become:
407 // To be noted that it can work if there is ONLY ONE trait bound, otherwise we still
408 // need to keep it as is!
409 res.push(generics.pop().unwrap());
413 let index_ty = get_index_type(&ty, generics);
414 if index_ty.id.is_none() && generics_empty {
421 // FIXME: remove this whole recurse thing when the recursion bug is fixed
422 // See #59502 for the original issue.
426 // First, check if it's "Self".
427 let arg = if let Some(self_) = self_ {
429 Type::BorrowedRef { type_, .. } if type_.is_self_type() => self_,
430 type_ if type_.is_self_type() => self_,
437 // If this argument is a type parameter and not a trait bound or a type, we need to look
439 if let Type::Generic(arg_s) = *arg {
440 // First we check if the bounds are in a `where` predicate...
441 if let Some(where_pred) = generics.where_predicates.iter().find(|g| match g {
442 WherePredicate::BoundPredicate { ty, .. } => ty.def_id(cache) == arg.def_id(cache),
445 let mut ty_generics = Vec::new();
446 let bounds = where_pred.get_bounds().unwrap_or_else(|| &[]);
447 for bound in bounds.iter() {
448 if let GenericBound::TraitBound(poly_trait, _) = bound {
449 for param_def in poly_trait.generic_params.iter() {
450 match ¶m_def.kind {
451 clean::GenericParamDefKind::Type { default: Some(ty), .. } => {
452 add_generics_and_bounds_as_types(
467 insert_ty(res, arg.clone(), ty_generics);
469 // Otherwise we check if the trait bounds are "inlined" like `T: Option<u32>`...
470 if let Some(bound) = generics.params.iter().find(|g| g.is_type() && g.name == arg_s) {
471 let mut ty_generics = Vec::new();
472 for bound in bound.get_bounds().unwrap_or(&[]) {
473 if let Some(path) = bound.get_trait_path() {
474 let ty = Type::Path { path };
475 add_generics_and_bounds_as_types(
486 insert_ty(res, arg.clone(), ty_generics);
488 } else if let Type::ImplTrait(ref bounds) = *arg {
489 let mut ty_generics = Vec::new();
490 for bound in bounds {
491 if let Some(path) = bound.get_trait_path() {
492 let ty = Type::Path { path };
493 add_generics_and_bounds_as_types(
504 insert_ty(res, arg.clone(), ty_generics);
506 // This is not a type parameter. So for example if we have `T, U: Option<T>`, and we're
507 // looking at `Option`, we enter this "else" condition, otherwise if it's `T`, we don't.
509 // So in here, we can add it directly and look for its own type parameters (so for `Option`,
510 // we will look for them but not for `T`).
511 let mut ty_generics = Vec::new();
512 if let Some(arg_generics) = arg.generics() {
513 for gen in arg_generics.iter() {
514 add_generics_and_bounds_as_types(
525 insert_ty(res, arg.clone(), ty_generics);
529 /// Return the full list of types when bounds have been resolved.
531 /// i.e. `fn foo<A: Display, B: Option<A>>(x: u32, y: B)` will return
532 /// `[u32, Display, Option]`.
533 fn get_fn_inputs_and_outputs<'tcx>(
536 impl_generics: Option<&(clean::Type, clean::Generics)>,
538 ) -> (Vec<RenderType>, Vec<RenderType>) {
539 let decl = &func.decl;
541 let combined_generics;
542 let (self_, generics) = if let Some(&(ref impl_self, ref impl_generics)) = impl_generics {
543 match (impl_generics.is_empty(), func.generics.is_empty()) {
544 (true, _) => (Some(impl_self), &func.generics),
545 (_, true) => (Some(impl_self), impl_generics),
547 let mut params = func.generics.params.clone();
548 params.extend(impl_generics.params.clone());
549 let mut where_predicates = func.generics.where_predicates.clone();
550 where_predicates.extend(impl_generics.where_predicates.clone());
551 combined_generics = clean::Generics { params, where_predicates };
552 (Some(impl_self), &combined_generics)
556 (None, &func.generics)
559 let mut all_types = Vec::new();
560 for arg in decl.inputs.values.iter() {
561 let mut args = Vec::new();
562 add_generics_and_bounds_as_types(self_, generics, &arg.type_, tcx, 0, &mut args, cache);
563 if !args.is_empty() {
564 all_types.extend(args);
566 all_types.push(get_index_type(&arg.type_, vec![]));
570 let mut ret_types = Vec::new();
572 FnRetTy::Return(ref return_type) => {
573 add_generics_and_bounds_as_types(
582 if ret_types.is_empty() {
583 ret_types.push(get_index_type(return_type, vec![]));
588 (all_types, ret_types)