src/librustdoc/html/render/search_index.rs

   1 use std::collections::hash_map::Entry;
   2 use std::collections::BTreeMap;
   3
   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};
   9
  10 use crate::clean;
  11 use crate::clean::types::{
  12     FnRetTy, Function, GenericBound, Generics, ItemId, Type, WherePredicate,
  13 };
  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};
  19
  20 /// Builds the search index from the collected metadata
  21 pub(crate) fn build_index<'tcx>(
  22     krate: &clean::Crate,
  23     cache: &mut Cache,
  24     tcx: TyCtxt<'tcx>,
  25 ) -> String {
  26     let mut itemid_to_pathid = FxHashMap::default();
  27     let mut crate_paths = vec![];
  28
  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) {
  33             let desc = item
  34                 .doc_value()
  35                 .map_or_else(String::new, |s| short_markdown_summary(&s, &item.link_names(cache)));
  36             cache.search_index.push(IndexItem {
  37                 ty: item.type_(),
  38                 name: item.name.unwrap().to_string(),
  39                 path: join_with_double_colon(&fqp[..fqp.len() - 1]),
  40                 desc,
  41                 parent: Some(parent),
  42                 parent_idx: None,
  43                 search_type: get_function_type_for_search(item, tcx, impl_generics.as_ref(), cache),
  44                 aliases: item.attrs.get_doc_aliases(),
  45             });
  46         }
  47     }
  48
  49     let crate_doc = krate
  50         .module
  51         .doc_value()
  52         .map_or_else(String::new, |s| short_markdown_summary(&s, &krate.module.link_names(cache)));
  53
  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();
  57
  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)
  64     });
  65
  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);
  70         }
  71     }
  72
  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;
  77
  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(
  82             ty: &mut RenderType,
  83             cache: &mut Cache,
  84             itemid_to_pathid: &mut FxHashMap<ItemId, usize>,
  85             lastpathid: &mut usize,
  86             crate_paths: &mut Vec<(ItemType, Symbol)>,
  87         ) {
  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);
  91                 }
  92             }
  93             let Cache { ref paths, ref external_paths, .. } = *cache;
  94             let Some(id) = ty.id.clone() else {
  95                 assert!(ty.generics.is_some());
  96                 return;
  97             };
  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))
 102                     {
 103                         (ItemId::DefId(defid), *fqp.last().unwrap(), item_type)
 104                     } else {
 105                         ty.id = None;
 106                         return;
 107                     }
 108                 }
 109                 RenderTypeId::Primitive(primitive) => (
 110                     ItemId::Primitive(primitive, LOCAL_CRATE),
 111                     primitive.as_sym(),
 112                     ItemType::Primitive,
 113                 ),
 114                 RenderTypeId::Index(_) => return,
 115             };
 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);
 121                     *lastpathid += 1;
 122                     crate_paths.push((item_type, path));
 123                     ty.id = Some(RenderTypeId::Index(pathid));
 124                 }
 125             }
 126         }
 127         if let Some(search_type) = &mut item.search_type {
 128             for item in &mut search_type.inputs {
 129                 convert_render_type(
 130                     item,
 131                     cache,
 132                     &mut itemid_to_pathid,
 133                     &mut lastpathid,
 134                     &mut crate_paths,
 135                 );
 136             }
 137             for item in &mut search_type.output {
 138                 convert_render_type(
 139                     item,
 140                     cache,
 141                     &mut itemid_to_pathid,
 142                     &mut lastpathid,
 143                     &mut crate_paths,
 144                 );
 145             }
 146         }
 147     }
 148
 149     let Cache { ref paths, .. } = *cache;
 150
 151     // Then, on parent modules
 152     let crate_items: Vec<&IndexItem> = search_index
 153         .iter_mut()
 154         .map(|item| {
 155             item.parent_idx =
 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);
 161                         lastpathid += 1;
 162
 163                         if let Some(&(ref fqp, short)) = paths.get(&defid) {
 164                             crate_paths.push((short, *fqp.last().unwrap()));
 165                             Some(pathid)
 166                         } else {
 167                             None
 168                         }
 169                     }
 170                 });
 171
 172             // Omit the parent path if it is same to that of the prior item.
 173             if lastpath == &item.path {
 174                 item.path.clear();
 175             } else {
 176                 lastpath = &item.path;
 177             }
 178
 179             &*item
 180         })
 181         .collect();
 182
 183     struct CrateData<'a> {
 184         doc: String,
 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.
 188         //
 189         // To be noted: the `usize` elements are indexes to `items`.
 190         aliases: &'a BTreeMap<String, Vec<usize>>,
 191     }
 192
 193     impl<'a> Serialize for CrateData<'a> {
 194         fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
 195         where
 196             S: Serializer,
 197         {
 198             let has_aliases = !self.aliases.is_empty();
 199             let mut crate_data =
 200                 serializer.serialize_struct("CrateData", if has_aliases { 9 } else { 8 })?;
 201             crate_data.serialize_field("doc", &self.doc)?;
 202             crate_data.serialize_field(
 203                 "t",
 204                 &self.items.iter().map(|item| &item.ty).collect::<Vec<_>>(),
 205             )?;
 206             crate_data.serialize_field(
 207                 "n",
 208                 &self.items.iter().map(|item| &item.name).collect::<Vec<_>>(),
 209             )?;
 210             crate_data.serialize_field(
 211                 "q",
 212                 &self.items.iter().map(|item| &item.path).collect::<Vec<_>>(),
 213             )?;
 214             crate_data.serialize_field(
 215                 "d",
 216                 &self.items.iter().map(|item| &item.desc).collect::<Vec<_>>(),
 217             )?;
 218             crate_data.serialize_field(
 219                 "i",
 220                 &self
 221                     .items
 222                     .iter()
 223                     .map(|item| {
 224                         assert_eq!(
 225                             item.parent.is_some(),
 226                             item.parent_idx.is_some(),
 227                             "`{}` is missing idx",
 228                             item.name
 229                         );
 230                         // 0 is a sentinel, everything else is one-indexed
 231                         item.parent_idx.map(|x| x + 1).unwrap_or(0)
 232                     })
 233                     .collect::<Vec<_>>(),
 234             )?;
 235             crate_data.serialize_field(
 236                 "f",
 237                 &self
 238                     .items
 239                     .iter()
 240                     .map(|item| {
 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),
 245                             None,
 246                         }
 247                         impl<'a> Serialize for FunctionOption<'a> {
 248                             fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
 249                             where
 250                                 S: Serializer,
 251                             {
 252                                 match self {
 253                                     FunctionOption::None => 0.serialize(serializer),
 254                                     FunctionOption::Function(ty) => ty.serialize(serializer),
 255                                 }
 256                             }
 257                         }
 258                         match &item.search_type {
 259                             Some(ty) => FunctionOption::Function(ty),
 260                             None => FunctionOption::None,
 261                         }
 262                     })
 263                     .collect::<Vec<_>>(),
 264             )?;
 265             crate_data.serialize_field(
 266                 "p",
 267                 &self.paths.iter().map(|(it, s)| (it, s.to_string())).collect::<Vec<_>>(),
 268             )?;
 269             if has_aliases {
 270                 crate_data.serialize_field("a", &self.aliases)?;
 271             }
 272             crate_data.end()
 273         }
 274     }
 275
 276     // Collect the index into a string
 277     format!(
 278         r#""{}":{}"#,
 279         krate.name(tcx),
 280         serde_json::to_string(&CrateData {
 281             doc: crate_doc,
 282             items: crate_items,
 283             paths: crate_paths,
 284             aliases: &aliases,
 285         })
 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("\\\"", "\\\\\"")
 292     )
 293 }
 294
 295 pub(crate) fn get_function_type_for_search<'tcx>(
 296     item: &clean::Item,
 297     tcx: TyCtxt<'tcx>,
 298     impl_generics: Option<&(clean::Type, clean::Generics)>,
 299     cache: &Cache,
 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),
 305         _ => return None,
 306     };
 307
 308     inputs.retain(|a| a.id.is_some() || a.generics.is_some());
 309     output.retain(|a| a.id.is_some() || a.generics.is_some());
 310
 311     Some(IndexItemFunctionType { inputs, output })
 312 }
 313
 314 fn get_index_type(clean_type: &clean::Type, generics: Vec<RenderType>) -> RenderType {
 315     RenderType {
 316         id: get_index_type_id(clean_type),
 317         generics: if generics.is_empty() { None } else { Some(generics) },
 318     }
 319 }
 320
 321 fn get_index_type_id(clean_type: &clean::Type) -> Option<RenderTypeId> {
 322     match *clean_type {
 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()))
 327         }
 328         clean::Primitive(p) => Some(RenderTypeId::Primitive(p)),
 329         clean::BorrowedRef { ref type_, .. } | clean::RawPointer(_, ref type_) => {
 330             get_index_type_id(type_)
 331         }
 332         clean::BareFunction(_)
 333         | clean::Generic(_)
 334         | clean::ImplTrait(_)
 335         | clean::Tuple(_)
 336         | clean::Slice(_)
 337         | clean::Array(_, _)
 338         | clean::QPath { .. }
 339         | clean::Infer => None,
 340     }
 341 }
 342
 343 /// The point of this function is to replace bounds with types.
 344 ///
 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.
 347 ///
 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>,
 353     generics: &Generics,
 354     arg: &'a Type,
 355     tcx: TyCtxt<'tcx>,
 356     recurse: usize,
 357     res: &mut Vec<RenderType>,
 358     cache: &Cache,
 359 ) {
 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();
 365
 366         if anonymous {
 367             if generics_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.
 371                 return;
 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.
 375                 //
 376                 // For example:
 377                 //
 378                 // `fn foo<T: Display>(r: Option<T>) {}`
 379                 //
 380                 // In this case, it would contain:
 381                 //
 382                 // ```
 383                 // [{
 384                 //     name: "option",
 385                 //     generics: [{
 386                 //         name: "",
 387                 //         generics: [
 388                 //             name: "Display",
 389                 //             generics: []
 390                 //         }]
 391                 //     }]
 392                 // }]
 393                 // ```
 394                 //
 395                 // After removing the intermediate (unnecessary) type parameter, it'll become:
 396                 //
 397                 // ```
 398                 // [{
 399                 //     name: "option",
 400                 //     generics: [{
 401                 //         name: "Display",
 402                 //         generics: []
 403                 //     }]
 404                 // }]
 405                 // ```
 406                 //
 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());
 410                 return;
 411             }
 412         }
 413         let index_ty = get_index_type(&ty, generics);
 414         if index_ty.id.is_none() && generics_empty {
 415             return;
 416         }
 417         res.push(index_ty);
 418     }
 419
 420     if recurse >= 10 {
 421         // FIXME: remove this whole recurse thing when the recursion bug is fixed
 422         // See #59502 for the original issue.
 423         return;
 424     }
 425
 426     // First, check if it's "Self".
 427     let arg = if let Some(self_) = self_ {
 428         match &*arg {
 429             Type::BorrowedRef { type_, .. } if type_.is_self_type() => self_,
 430             type_ if type_.is_self_type() => self_,
 431             arg => arg,
 432         }
 433     } else {
 434         arg
 435     };
 436
 437     // If this argument is a type parameter and not a trait bound or a type, we need to look
 438     // for its bounds.
 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),
 443             _ => false,
 444         }) {
 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 &param_def.kind {
 451                             clean::GenericParamDefKind::Type { default: Some(ty), .. } => {
 452                                 add_generics_and_bounds_as_types(
 453                                     self_,
 454                                     generics,
 455                                     ty,
 456                                     tcx,
 457                                     recurse + 1,
 458                                     &mut ty_generics,
 459                                     cache,
 460                                 )
 461                             }
 462                             _ => {}
 463                         }
 464                     }
 465                 }
 466             }
 467             insert_ty(res, arg.clone(), ty_generics);
 468         }
 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(
 476                         self_,
 477                         generics,
 478                         &ty,
 479                         tcx,
 480                         recurse + 1,
 481                         &mut ty_generics,
 482                         cache,
 483                     );
 484                 }
 485             }
 486             insert_ty(res, arg.clone(), ty_generics);
 487         }
 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(
 494                     self_,
 495                     generics,
 496                     &ty,
 497                     tcx,
 498                     recurse + 1,
 499                     &mut ty_generics,
 500                     cache,
 501                 );
 502             }
 503         }
 504         insert_ty(res, arg.clone(), ty_generics);
 505     } else {
 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.
 508         //
 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(
 515                     self_,
 516                     generics,
 517                     gen,
 518                     tcx,
 519                     recurse + 1,
 520                     &mut ty_generics,
 521                     cache,
 522                 );
 523             }
 524         }
 525         insert_ty(res, arg.clone(), ty_generics);
 526     }
 527 }
 528
 529 /// Return the full list of types when bounds have been resolved.
 530 ///
 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>(
 534     func: &Function,
 535     tcx: TyCtxt<'tcx>,
 536     impl_generics: Option<&(clean::Type, clean::Generics)>,
 537     cache: &Cache,
 538 ) -> (Vec<RenderType>, Vec<RenderType>) {
 539     let decl = &func.decl;
 540
 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),
 546             (false, false) => {
 547                 let params =
 548                     func.generics.params.iter().chain(&impl_generics.params).cloned().collect();
 549                 let where_predicates = func
 550                     .generics
 551                     .where_predicates
 552                     .iter()
 553                     .chain(&impl_generics.where_predicates)
 554                     .cloned()
 555                     .collect();
 556                 combined_generics = clean::Generics { params, where_predicates };
 557                 (Some(impl_self), &combined_generics)
 558             }
 559         }
 560     } else {
 561         (None, &func.generics)
 562     };
 563
 564     let mut all_types = Vec::new();
 565     for arg in decl.inputs.values.iter() {
 566         let mut args = Vec::new();
 567         add_generics_and_bounds_as_types(self_, generics, &arg.type_, tcx, 0, &mut args, cache);
 568         if !args.is_empty() {
 569             all_types.extend(args);
 570         } else {
 571             all_types.push(get_index_type(&arg.type_, vec![]));
 572         }
 573     }
 574
 575     let mut ret_types = Vec::new();
 576     match decl.output {
 577         FnRetTy::Return(ref return_type) => {
 578             add_generics_and_bounds_as_types(
 579                 self_,
 580                 generics,
 581                 return_type,
 582                 tcx,
 583                 0,
 584                 &mut ret_types,
 585                 cache,
 586             );
 587             if ret_types.is_empty() {
 588                 ret_types.push(get_index_type(return_type, vec![]));
 589             }
 590         }
 591         _ => {}
 592     };
 593     (all_types, ret_types)
 594 }