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::symbol::Symbol;
   7 use serde::ser::{Serialize, SerializeStruct, Serializer};
   8
   9 use crate::clean;
  10 use crate::clean::types::{
  11     FnRetTy, Function, GenericBound, Generics, ItemId, Type, WherePredicate,
  12 };
  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};
  18
  19 /// Builds the search index from the collected metadata
  20 pub(crate) fn build_index<'tcx>(
  21     krate: &clean::Crate,
  22     cache: &mut Cache,
  23     tcx: TyCtxt<'tcx>,
  24 ) -> String {
  25     let mut itemid_to_pathid = FxHashMap::default();
  26     let mut primitives = 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 insert_into_map<F: std::hash::Hash + Eq>(
  82             ty: &mut RenderType,
  83             map: &mut FxHashMap<F, usize>,
  84             itemid: F,
  85             lastpathid: &mut usize,
  86             crate_paths: &mut Vec<(ItemType, Symbol)>,
  87             item_type: ItemType,
  88             path: Symbol,
  89         ) {
  90             match map.entry(itemid) {
  91                 Entry::Occupied(entry) => ty.id = Some(RenderTypeId::Index(*entry.get())),
  92                 Entry::Vacant(entry) => {
  93                     let pathid = *lastpathid;
  94                     entry.insert(pathid);
  95                     *lastpathid += 1;
  96                     crate_paths.push((item_type, path));
  97                     ty.id = Some(RenderTypeId::Index(pathid));
  98                 }
  99             }
 100         }
 101
 102         fn convert_render_type(
 103             ty: &mut RenderType,
 104             cache: &mut Cache,
 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)>,
 109         ) {
 110             if let Some(generics) = &mut ty.generics {
 111                 for item in generics {
 112                     convert_render_type(
 113                         item,
 114                         cache,
 115                         itemid_to_pathid,
 116                         primitives,
 117                         lastpathid,
 118                         crate_paths,
 119                     );
 120                 }
 121             }
 122             let Cache { ref paths, ref external_paths, .. } = *cache;
 123             let Some(id) = ty.id.clone() else {
 124                 assert!(ty.generics.is_some());
 125                 return;
 126             };
 127             match id {
 128                 RenderTypeId::DefId(defid) => {
 129                     if let Some(&(ref fqp, item_type)) =
 130                         paths.get(&defid).or_else(|| external_paths.get(&defid))
 131                     {
 132                         insert_into_map(
 133                             ty,
 134                             itemid_to_pathid,
 135                             ItemId::DefId(defid),
 136                             lastpathid,
 137                             crate_paths,
 138                             item_type,
 139                             *fqp.last().unwrap(),
 140                         );
 141                     } else {
 142                         ty.id = None;
 143                     }
 144                 }
 145                 RenderTypeId::Primitive(primitive) => {
 146                     let sym = primitive.as_sym();
 147                     insert_into_map(
 148                         ty,
 149                         primitives,
 150                         sym,
 151                         lastpathid,
 152                         crate_paths,
 153                         ItemType::Primitive,
 154                         sym,
 155                     );
 156                 }
 157                 RenderTypeId::Index(_) => {}
 158             }
 159         }
 160         if let Some(search_type) = &mut item.search_type {
 161             for item in &mut search_type.inputs {
 162                 convert_render_type(
 163                     item,
 164                     cache,
 165                     &mut itemid_to_pathid,
 166                     &mut primitives,
 167                     &mut lastpathid,
 168                     &mut crate_paths,
 169                 );
 170             }
 171             for item in &mut search_type.output {
 172                 convert_render_type(
 173                     item,
 174                     cache,
 175                     &mut itemid_to_pathid,
 176                     &mut primitives,
 177                     &mut lastpathid,
 178                     &mut crate_paths,
 179                 );
 180             }
 181         }
 182     }
 183
 184     let Cache { ref paths, .. } = *cache;
 185
 186     // Then, on parent modules
 187     let crate_items: Vec<&IndexItem> = search_index
 188         .iter_mut()
 189         .map(|item| {
 190             item.parent_idx =
 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);
 196                         lastpathid += 1;
 197
 198                         if let Some(&(ref fqp, short)) = paths.get(&defid) {
 199                             crate_paths.push((short, *fqp.last().unwrap()));
 200                             Some(pathid)
 201                         } else {
 202                             None
 203                         }
 204                     }
 205                 });
 206
 207             // Omit the parent path if it is same to that of the prior item.
 208             if lastpath == &item.path {
 209                 item.path.clear();
 210             } else {
 211                 lastpath = &item.path;
 212             }
 213
 214             &*item
 215         })
 216         .collect();
 217
 218     struct CrateData<'a> {
 219         doc: String,
 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.
 223         //
 224         // To be noted: the `usize` elements are indexes to `items`.
 225         aliases: &'a BTreeMap<String, Vec<usize>>,
 226     }
 227
 228     impl<'a> Serialize for CrateData<'a> {
 229         fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
 230         where
 231             S: Serializer,
 232         {
 233             let has_aliases = !self.aliases.is_empty();
 234             let mut crate_data =
 235                 serializer.serialize_struct("CrateData", if has_aliases { 9 } else { 8 })?;
 236             crate_data.serialize_field("doc", &self.doc)?;
 237             crate_data.serialize_field(
 238                 "t",
 239                 &self.items.iter().map(|item| &item.ty).collect::<Vec<_>>(),
 240             )?;
 241             crate_data.serialize_field(
 242                 "n",
 243                 &self.items.iter().map(|item| &item.name).collect::<Vec<_>>(),
 244             )?;
 245             crate_data.serialize_field(
 246                 "q",
 247                 &self.items.iter().map(|item| &item.path).collect::<Vec<_>>(),
 248             )?;
 249             crate_data.serialize_field(
 250                 "d",
 251                 &self.items.iter().map(|item| &item.desc).collect::<Vec<_>>(),
 252             )?;
 253             crate_data.serialize_field(
 254                 "i",
 255                 &self
 256                     .items
 257                     .iter()
 258                     .map(|item| {
 259                         assert_eq!(
 260                             item.parent.is_some(),
 261                             item.parent_idx.is_some(),
 262                             "`{}` is missing idx",
 263                             item.name
 264                         );
 265                         // 0 is a sentinel, everything else is one-indexed
 266                         item.parent_idx.map(|x| x + 1).unwrap_or(0)
 267                     })
 268                     .collect::<Vec<_>>(),
 269             )?;
 270             crate_data.serialize_field(
 271                 "f",
 272                 &self
 273                     .items
 274                     .iter()
 275                     .map(|item| {
 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),
 280                             None,
 281                         }
 282                         impl<'a> Serialize for FunctionOption<'a> {
 283                             fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
 284                             where
 285                                 S: Serializer,
 286                             {
 287                                 match self {
 288                                     FunctionOption::None => 0.serialize(serializer),
 289                                     FunctionOption::Function(ty) => ty.serialize(serializer),
 290                                 }
 291                             }
 292                         }
 293                         match &item.search_type {
 294                             Some(ty) => FunctionOption::Function(ty),
 295                             None => FunctionOption::None,
 296                         }
 297                     })
 298                     .collect::<Vec<_>>(),
 299             )?;
 300             crate_data.serialize_field(
 301                 "p",
 302                 &self.paths.iter().map(|(it, s)| (it, s.to_string())).collect::<Vec<_>>(),
 303             )?;
 304             if has_aliases {
 305                 crate_data.serialize_field("a", &self.aliases)?;
 306             }
 307             crate_data.end()
 308         }
 309     }
 310
 311     // Collect the index into a string
 312     format!(
 313         r#""{}":{}"#,
 314         krate.name(tcx),
 315         serde_json::to_string(&CrateData {
 316             doc: crate_doc,
 317             items: crate_items,
 318             paths: crate_paths,
 319             aliases: &aliases,
 320         })
 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("\\\"", "\\\\\"")
 327     )
 328 }
 329
 330 pub(crate) fn get_function_type_for_search<'tcx>(
 331     item: &clean::Item,
 332     tcx: TyCtxt<'tcx>,
 333     impl_generics: Option<&(clean::Type, clean::Generics)>,
 334     cache: &Cache,
 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),
 340         _ => return None,
 341     };
 342
 343     inputs.retain(|a| a.id.is_some() || a.generics.is_some());
 344     output.retain(|a| a.id.is_some() || a.generics.is_some());
 345
 346     Some(IndexItemFunctionType { inputs, output })
 347 }
 348
 349 fn get_index_type(clean_type: &clean::Type, generics: Vec<RenderType>) -> RenderType {
 350     RenderType {
 351         id: get_index_type_id(clean_type),
 352         generics: if generics.is_empty() { None } else { Some(generics) },
 353     }
 354 }
 355
 356 fn get_index_type_id(clean_type: &clean::Type) -> Option<RenderTypeId> {
 357     match *clean_type {
 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()))
 361         }
 362         clean::Primitive(p) => Some(RenderTypeId::Primitive(p)),
 363         clean::BorrowedRef { ref type_, .. } | clean::RawPointer(_, ref type_) => {
 364             get_index_type_id(type_)
 365         }
 366         clean::BareFunction(_)
 367         | clean::Generic(_)
 368         | clean::ImplTrait(_)
 369         | clean::Tuple(_)
 370         | clean::Slice(_)
 371         | clean::Array(_, _)
 372         | clean::QPath { .. }
 373         | clean::Infer => None,
 374     }
 375 }
 376
 377 /// The point of this function is to replace bounds with types.
 378 ///
 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.
 381 ///
 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>,
 387     generics: &Generics,
 388     arg: &'a Type,
 389     tcx: TyCtxt<'tcx>,
 390     recurse: usize,
 391     res: &mut Vec<RenderType>,
 392     cache: &Cache,
 393 ) {
 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();
 399
 400         if anonymous {
 401             if generics_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.
 405                 return;
 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.
 409                 //
 410                 // For example:
 411                 //
 412                 // `fn foo<T: Display>(r: Option<T>) {}`
 413                 //
 414                 // In this case, it would contain:
 415                 //
 416                 // ```
 417                 // [{
 418                 //     name: "option",
 419                 //     generics: [{
 420                 //         name: "",
 421                 //         generics: [
 422                 //             name: "Display",
 423                 //             generics: []
 424                 //         }]
 425                 //     }]
 426                 // }]
 427                 // ```
 428                 //
 429                 // After removing the intermediate (unnecessary) type parameter, it'll become:
 430                 //
 431                 // ```
 432                 // [{
 433                 //     name: "option",
 434                 //     generics: [{
 435                 //         name: "Display",
 436                 //         generics: []
 437                 //     }]
 438                 // }]
 439                 // ```
 440                 //
 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());
 444                 return;
 445             }
 446         }
 447         let index_ty = get_index_type(&ty, generics);
 448         if index_ty.id.is_none() && generics_empty {
 449             return;
 450         }
 451         res.push(index_ty);
 452     }
 453
 454     if recurse >= 10 {
 455         // FIXME: remove this whole recurse thing when the recursion bug is fixed
 456         // See #59502 for the original issue.
 457         return;
 458     }
 459
 460     // First, check if it's "Self".
 461     let arg = if let Some(self_) = self_ {
 462         match &*arg {
 463             Type::BorrowedRef { type_, .. } if type_.is_self_type() => self_,
 464             type_ if type_.is_self_type() => self_,
 465             arg => arg,
 466         }
 467     } else {
 468         arg
 469     };
 470
 471     // If this argument is a type parameter and not a trait bound or a type, we need to look
 472     // for its bounds.
 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),
 477             _ => false,
 478         }) {
 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 &param_def.kind {
 485                             clean::GenericParamDefKind::Type { default: Some(ty), .. } => {
 486                                 add_generics_and_bounds_as_types(
 487                                     self_,
 488                                     generics,
 489                                     ty,
 490                                     tcx,
 491                                     recurse + 1,
 492                                     &mut ty_generics,
 493                                     cache,
 494                                 )
 495                             }
 496                             _ => {}
 497                         }
 498                     }
 499                 }
 500             }
 501             insert_ty(res, arg.clone(), ty_generics);
 502         }
 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(
 510                         self_,
 511                         generics,
 512                         &ty,
 513                         tcx,
 514                         recurse + 1,
 515                         &mut ty_generics,
 516                         cache,
 517                     );
 518                 }
 519             }
 520             insert_ty(res, arg.clone(), ty_generics);
 521         }
 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(
 528                     self_,
 529                     generics,
 530                     &ty,
 531                     tcx,
 532                     recurse + 1,
 533                     &mut ty_generics,
 534                     cache,
 535                 );
 536             }
 537         }
 538         insert_ty(res, arg.clone(), ty_generics);
 539     } else {
 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.
 542         //
 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(
 549                     self_,
 550                     generics,
 551                     gen,
 552                     tcx,
 553                     recurse + 1,
 554                     &mut ty_generics,
 555                     cache,
 556                 );
 557             }
 558         }
 559         insert_ty(res, arg.clone(), ty_generics);
 560     }
 561 }
 562
 563 /// Return the full list of types when bounds have been resolved.
 564 ///
 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>(
 568     func: &Function,
 569     tcx: TyCtxt<'tcx>,
 570     impl_generics: Option<&(clean::Type, clean::Generics)>,
 571     cache: &Cache,
 572 ) -> (Vec<RenderType>, Vec<RenderType>) {
 573     let decl = &func.decl;
 574
 575     let combined_generics;
 576     let (self_, generics) = if let Some(&(ref impl_self, ref 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),
 580             (false, false) => {
 581                 let params =
 582                     func.generics.params.iter().chain(&impl_generics.params).cloned().collect();
 583                 let where_predicates = func
 584                     .generics
 585                     .where_predicates
 586                     .iter()
 587                     .chain(&impl_generics.where_predicates)
 588                     .cloned()
 589                     .collect();
 590                 combined_generics = clean::Generics { params, where_predicates };
 591                 (Some(impl_self), &combined_generics)
 592             }
 593         }
 594     } else {
 595         (None, &func.generics)
 596     };
 597
 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);
 604         } else {
 605             all_types.push(get_index_type(&arg.type_, vec![]));
 606         }
 607     }
 608
 609     let mut ret_types = Vec::new();
 610     match decl.output {
 611         FnRetTy::Return(ref return_type) => {
 612             add_generics_and_bounds_as_types(
 613                 self_,
 614                 generics,
 615                 return_type,
 616                 tcx,
 617                 0,
 618                 &mut ret_types,
 619                 cache,
 620             );
 621             if ret_types.is_empty() {
 622                 ret_types.push(get_index_type(return_type, vec![]));
 623             }
 624         }
 625         _ => {}
 626     };
 627     (all_types, ret_types)
 628 }