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::{kw, Symbol};
   7 use serde::ser::{Serialize, SerializeStruct, Serializer};
   8
   9 use crate::clean;
  10 use crate::clean::types::{FnRetTy, Function, GenericBound, Generics, Type, WherePredicate};
  11 use crate::formats::cache::{Cache, OrphanImplItem};
  12 use crate::formats::item_type::ItemType;
  13 use crate::html::format::join_with_double_colon;
  14 use crate::html::markdown::short_markdown_summary;
  15 use crate::html::render::{IndexItem, IndexItemFunctionType, RenderType, TypeWithKind};
  16
  17 /// Builds the search index from the collected metadata
  18 pub(crate) fn build_index<'tcx>(
  19     krate: &clean::Crate,
  20     cache: &mut Cache,
  21     tcx: TyCtxt<'tcx>,
  22 ) -> String {
  23     let mut defid_to_pathid = FxHashMap::default();
  24     let mut crate_paths = vec![];
  25
  26     // Attach all orphan items to the type's definition if the type
  27     // has since been learned.
  28     for &OrphanImplItem { parent, ref item, ref impl_generics } in &cache.orphan_impl_items {
  29         if let Some(&(ref fqp, _)) = cache.paths.get(&parent) {
  30             let desc = item
  31                 .doc_value()
  32                 .map_or_else(String::new, |s| short_markdown_summary(&s, &item.link_names(cache)));
  33             cache.search_index.push(IndexItem {
  34                 ty: item.type_(),
  35                 name: item.name.unwrap().to_string(),
  36                 path: join_with_double_colon(&fqp[..fqp.len() - 1]),
  37                 desc,
  38                 parent: Some(parent),
  39                 parent_idx: None,
  40                 search_type: get_function_type_for_search(item, tcx, impl_generics.as_ref(), cache),
  41                 aliases: item.attrs.get_doc_aliases(),
  42             });
  43         }
  44     }
  45
  46     let crate_doc = krate
  47         .module
  48         .doc_value()
  49         .map_or_else(String::new, |s| short_markdown_summary(&s, &krate.module.link_names(cache)));
  50
  51     let Cache { ref mut search_index, ref paths, .. } = *cache;
  52
  53     // Aliases added through `#[doc(alias = "...")]`. Since a few items can have the same alias,
  54     // we need the alias element to have an array of items.
  55     let mut aliases: BTreeMap<String, Vec<usize>> = BTreeMap::new();
  56
  57     // Sort search index items. This improves the compressibility of the search index.
  58     search_index.sort_unstable_by(|k1, k2| {
  59         // `sort_unstable_by_key` produces lifetime errors
  60         let k1 = (&k1.path, &k1.name, &k1.ty, &k1.parent);
  61         let k2 = (&k2.path, &k2.name, &k2.ty, &k2.parent);
  62         std::cmp::Ord::cmp(&k1, &k2)
  63     });
  64
  65     // Set up alias indexes.
  66     for (i, item) in search_index.iter().enumerate() {
  67         for alias in &item.aliases[..] {
  68             aliases.entry(alias.as_str().to_lowercase()).or_default().push(i);
  69         }
  70     }
  71
  72     // Reduce `DefId` in paths into smaller sequential numbers,
  73     // and prune the paths that do not appear in the index.
  74     let mut lastpath = "";
  75     let mut lastpathid = 0usize;
  76
  77     let crate_items: Vec<&IndexItem> = search_index
  78         .iter_mut()
  79         .map(|item| {
  80             item.parent_idx = item.parent.and_then(|defid| match defid_to_pathid.entry(defid) {
  81                 Entry::Occupied(entry) => Some(*entry.get()),
  82                 Entry::Vacant(entry) => {
  83                     let pathid = lastpathid;
  84                     entry.insert(pathid);
  85                     lastpathid += 1;
  86
  87                     if let Some(&(ref fqp, short)) = paths.get(&defid) {
  88                         crate_paths.push((short, *fqp.last().unwrap()));
  89                         Some(pathid)
  90                     } else {
  91                         None
  92                     }
  93                 }
  94             });
  95
  96             // Omit the parent path if it is same to that of the prior item.
  97             if lastpath == &item.path {
  98                 item.path.clear();
  99             } else {
 100                 lastpath = &item.path;
 101             }
 102
 103             &*item
 104         })
 105         .collect();
 106
 107     struct CrateData<'a> {
 108         doc: String,
 109         items: Vec<&'a IndexItem>,
 110         paths: Vec<(ItemType, Symbol)>,
 111         // The String is alias name and the vec is the list of the elements with this alias.
 112         //
 113         // To be noted: the `usize` elements are indexes to `items`.
 114         aliases: &'a BTreeMap<String, Vec<usize>>,
 115     }
 116
 117     impl<'a> Serialize for CrateData<'a> {
 118         fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
 119         where
 120             S: Serializer,
 121         {
 122             let has_aliases = !self.aliases.is_empty();
 123             let mut crate_data =
 124                 serializer.serialize_struct("CrateData", if has_aliases { 9 } else { 8 })?;
 125             crate_data.serialize_field("doc", &self.doc)?;
 126             crate_data.serialize_field(
 127                 "t",
 128                 &self.items.iter().map(|item| &item.ty).collect::<Vec<_>>(),
 129             )?;
 130             crate_data.serialize_field(
 131                 "n",
 132                 &self.items.iter().map(|item| &item.name).collect::<Vec<_>>(),
 133             )?;
 134             crate_data.serialize_field(
 135                 "q",
 136                 &self.items.iter().map(|item| &item.path).collect::<Vec<_>>(),
 137             )?;
 138             crate_data.serialize_field(
 139                 "d",
 140                 &self.items.iter().map(|item| &item.desc).collect::<Vec<_>>(),
 141             )?;
 142             crate_data.serialize_field(
 143                 "i",
 144                 &self
 145                     .items
 146                     .iter()
 147                     .map(|item| {
 148                         assert_eq!(
 149                             item.parent.is_some(),
 150                             item.parent_idx.is_some(),
 151                             "`{}` is missing idx",
 152                             item.name
 153                         );
 154                         item.parent_idx.map(|x| x + 1).unwrap_or(0)
 155                     })
 156                     .collect::<Vec<_>>(),
 157             )?;
 158             crate_data.serialize_field(
 159                 "f",
 160                 &self.items.iter().map(|item| &item.search_type).collect::<Vec<_>>(),
 161             )?;
 162             crate_data.serialize_field(
 163                 "p",
 164                 &self.paths.iter().map(|(it, s)| (it, s.to_string())).collect::<Vec<_>>(),
 165             )?;
 166             if has_aliases {
 167                 crate_data.serialize_field("a", &self.aliases)?;
 168             }
 169             crate_data.end()
 170         }
 171     }
 172
 173     // Collect the index into a string
 174     format!(
 175         r#""{}":{}"#,
 176         krate.name(tcx),
 177         serde_json::to_string(&CrateData {
 178             doc: crate_doc,
 179             items: crate_items,
 180             paths: crate_paths,
 181             aliases: &aliases,
 182         })
 183         .expect("failed serde conversion")
 184         // All these `replace` calls are because we have to go through JS string for JSON content.
 185         .replace('\\', r"\\")
 186         .replace('\'', r"\'")
 187         // We need to escape double quotes for the JSON.
 188         .replace("\\\"", "\\\\\"")
 189     )
 190 }
 191
 192 pub(crate) fn get_function_type_for_search<'tcx>(
 193     item: &clean::Item,
 194     tcx: TyCtxt<'tcx>,
 195     impl_generics: Option<&(clean::Type, clean::Generics)>,
 196     cache: &Cache,
 197 ) -> Option<IndexItemFunctionType> {
 198     let (mut inputs, mut output) = match *item.kind {
 199         clean::FunctionItem(ref f) => get_fn_inputs_and_outputs(f, tcx, impl_generics, cache),
 200         clean::MethodItem(ref m, _) => get_fn_inputs_and_outputs(m, tcx, impl_generics, cache),
 201         clean::TyMethodItem(ref m) => get_fn_inputs_and_outputs(m, tcx, impl_generics, cache),
 202         _ => return None,
 203     };
 204
 205     inputs.retain(|a| a.ty.name.is_some());
 206     output.retain(|a| a.ty.name.is_some());
 207
 208     Some(IndexItemFunctionType { inputs, output })
 209 }
 210
 211 fn get_index_type(clean_type: &clean::Type, generics: Vec<TypeWithKind>) -> RenderType {
 212     RenderType {
 213         name: get_index_type_name(clean_type).map(|s| s.as_str().to_ascii_lowercase()),
 214         generics: if generics.is_empty() { None } else { Some(generics) },
 215     }
 216 }
 217
 218 fn get_index_type_name(clean_type: &clean::Type) -> Option<Symbol> {
 219     match *clean_type {
 220         clean::Type::Path { ref path, .. } => {
 221             let path_segment = path.segments.last().unwrap();
 222             Some(path_segment.name)
 223         }
 224         clean::DynTrait(ref bounds, _) => {
 225             let path = &bounds[0].trait_;
 226             Some(path.segments.last().unwrap().name)
 227         }
 228         // We return an empty name because we don't care about the generic name itself.
 229         clean::Generic(_) | clean::ImplTrait(_) => Some(kw::Empty),
 230         clean::Primitive(ref p) => Some(p.as_sym()),
 231         clean::BorrowedRef { ref type_, .. } | clean::RawPointer(_, ref type_) => {
 232             get_index_type_name(type_)
 233         }
 234         clean::BareFunction(_)
 235         | clean::Tuple(_)
 236         | clean::Slice(_)
 237         | clean::Array(_, _)
 238         | clean::QPath { .. }
 239         | clean::Infer => None,
 240     }
 241 }
 242
 243 /// The point of this function is to replace bounds with types.
 244 ///
 245 /// i.e. `[T, U]` when you have the following bounds: `T: Display, U: Option<T>` will return
 246 /// `[Display, Option]`. If a type parameter has no trait bound, it is discarded.
 247 ///
 248 /// Important note: It goes through generics recursively. So if you have
 249 /// `T: Option<Result<(), ()>>`, it'll go into `Option` and then into `Result`.
 250 #[instrument(level = "trace", skip(tcx, res, cache))]
 251 fn add_generics_and_bounds_as_types<'tcx, 'a>(
 252     self_: Option<&'a Type>,
 253     generics: &Generics,
 254     arg: &'a Type,
 255     tcx: TyCtxt<'tcx>,
 256     recurse: usize,
 257     res: &mut Vec<TypeWithKind>,
 258     cache: &Cache,
 259 ) {
 260     fn insert_ty(
 261         res: &mut Vec<TypeWithKind>,
 262         tcx: TyCtxt<'_>,
 263         ty: Type,
 264         mut generics: Vec<TypeWithKind>,
 265         cache: &Cache,
 266     ) {
 267         // generics and impl trait are both identified by their generics,
 268         // rather than a type name itself
 269         let anonymous = ty.is_full_generic() || ty.is_impl_trait();
 270         let generics_empty = generics.is_empty();
 271
 272         if anonymous {
 273             if generics_empty {
 274                 // This is a type parameter with no trait bounds (for example: `T` in
 275                 // `fn f<T>(p: T)`, so not useful for the rustdoc search because we would end up
 276                 // with an empty type with an empty name. Let's just discard it.
 277                 return;
 278             } else if generics.len() == 1 {
 279                 // In this case, no need to go through an intermediate state if the type parameter
 280                 // contains only one trait bound.
 281                 //
 282                 // For example:
 283                 //
 284                 // `fn foo<T: Display>(r: Option<T>) {}`
 285                 //
 286                 // In this case, it would contain:
 287                 //
 288                 // ```
 289                 // [{
 290                 //     name: "option",
 291                 //     generics: [{
 292                 //         name: "",
 293                 //         generics: [
 294                 //             name: "Display",
 295                 //             generics: []
 296                 //         }]
 297                 //     }]
 298                 // }]
 299                 // ```
 300                 //
 301                 // After removing the intermediate (unnecessary) type parameter, it'll become:
 302                 //
 303                 // ```
 304                 // [{
 305                 //     name: "option",
 306                 //     generics: [{
 307                 //         name: "Display",
 308                 //         generics: []
 309                 //     }]
 310                 // }]
 311                 // ```
 312                 //
 313                 // To be noted that it can work if there is ONLY ONE trait bound, otherwise we still
 314                 // need to keep it as is!
 315                 res.push(generics.pop().unwrap());
 316                 return;
 317             }
 318         }
 319         let mut index_ty = get_index_type(&ty, generics);
 320         if index_ty.name.as_ref().map(|s| s.is_empty() && generics_empty).unwrap_or(true) {
 321             return;
 322         }
 323         if anonymous {
 324             // We remove the name of the full generic because we have no use for it.
 325             index_ty.name = Some(String::new());
 326             res.push(TypeWithKind::from((index_ty, ItemType::Generic)));
 327         } else if let Some(kind) = ty.def_id(cache).map(|did| tcx.def_kind(did).into()) {
 328             res.push(TypeWithKind::from((index_ty, kind)));
 329         } else if ty.is_primitive() {
 330             // This is a primitive, let's store it as such.
 331             res.push(TypeWithKind::from((index_ty, ItemType::Primitive)));
 332         }
 333     }
 334
 335     if recurse >= 10 {
 336         // FIXME: remove this whole recurse thing when the recursion bug is fixed
 337         // See #59502 for the original issue.
 338         return;
 339     }
 340
 341     // First, check if it's "Self".
 342     let arg = if let Some(self_) = self_ {
 343         match &*arg {
 344             Type::BorrowedRef { type_, .. } if type_.is_self_type() => self_,
 345             type_ if type_.is_self_type() => self_,
 346             arg => arg,
 347         }
 348     } else {
 349         arg
 350     };
 351
 352     // If this argument is a type parameter and not a trait bound or a type, we need to look
 353     // for its bounds.
 354     if let Type::Generic(arg_s) = *arg {
 355         // First we check if the bounds are in a `where` predicate...
 356         if let Some(where_pred) = generics.where_predicates.iter().find(|g| match g {
 357             WherePredicate::BoundPredicate { ty, .. } => ty.def_id(cache) == arg.def_id(cache),
 358             _ => false,
 359         }) {
 360             let mut ty_generics = Vec::new();
 361             let bounds = where_pred.get_bounds().unwrap_or_else(|| &[]);
 362             for bound in bounds.iter() {
 363                 if let GenericBound::TraitBound(poly_trait, _) = bound {
 364                     for param_def in poly_trait.generic_params.iter() {
 365                         match &param_def.kind {
 366                             clean::GenericParamDefKind::Type { default: Some(ty), .. } => {
 367                                 add_generics_and_bounds_as_types(
 368                                     self_,
 369                                     generics,
 370                                     ty,
 371                                     tcx,
 372                                     recurse + 1,
 373                                     &mut ty_generics,
 374                                     cache,
 375                                 )
 376                             }
 377                             _ => {}
 378                         }
 379                     }
 380                 }
 381             }
 382             insert_ty(res, tcx, arg.clone(), ty_generics, cache);
 383         }
 384         // Otherwise we check if the trait bounds are "inlined" like `T: Option<u32>`...
 385         if let Some(bound) = generics.params.iter().find(|g| g.is_type() && g.name == arg_s) {
 386             let mut ty_generics = Vec::new();
 387             for bound in bound.get_bounds().unwrap_or(&[]) {
 388                 if let Some(path) = bound.get_trait_path() {
 389                     let ty = Type::Path { path };
 390                     add_generics_and_bounds_as_types(
 391                         self_,
 392                         generics,
 393                         &ty,
 394                         tcx,
 395                         recurse + 1,
 396                         &mut ty_generics,
 397                         cache,
 398                     );
 399                 }
 400             }
 401             insert_ty(res, tcx, arg.clone(), ty_generics, cache);
 402         }
 403     } else if let Type::ImplTrait(ref bounds) = *arg {
 404         let mut ty_generics = Vec::new();
 405         for bound in bounds {
 406             if let Some(path) = bound.get_trait_path() {
 407                 let ty = Type::Path { path };
 408                 add_generics_and_bounds_as_types(
 409                     self_,
 410                     generics,
 411                     &ty,
 412                     tcx,
 413                     recurse + 1,
 414                     &mut ty_generics,
 415                     cache,
 416                 );
 417             }
 418         }
 419         insert_ty(res, tcx, arg.clone(), ty_generics, cache);
 420     } else {
 421         // This is not a type parameter. So for example if we have `T, U: Option<T>`, and we're
 422         // looking at `Option`, we enter this "else" condition, otherwise if it's `T`, we don't.
 423         //
 424         // So in here, we can add it directly and look for its own type parameters (so for `Option`,
 425         // we will look for them but not for `T`).
 426         let mut ty_generics = Vec::new();
 427         if let Some(arg_generics) = arg.generics() {
 428             for gen in arg_generics.iter() {
 429                 add_generics_and_bounds_as_types(
 430                     self_,
 431                     generics,
 432                     gen,
 433                     tcx,
 434                     recurse + 1,
 435                     &mut ty_generics,
 436                     cache,
 437                 );
 438             }
 439         }
 440         insert_ty(res, tcx, arg.clone(), ty_generics, cache);
 441     }
 442 }
 443
 444 /// Return the full list of types when bounds have been resolved.
 445 ///
 446 /// i.e. `fn foo<A: Display, B: Option<A>>(x: u32, y: B)` will return
 447 /// `[u32, Display, Option]`.
 448 fn get_fn_inputs_and_outputs<'tcx>(
 449     func: &Function,
 450     tcx: TyCtxt<'tcx>,
 451     impl_generics: Option<&(clean::Type, clean::Generics)>,
 452     cache: &Cache,
 453 ) -> (Vec<TypeWithKind>, Vec<TypeWithKind>) {
 454     let decl = &func.decl;
 455
 456     let combined_generics;
 457     let (self_, generics) = if let Some(&(ref impl_self, ref impl_generics)) = impl_generics {
 458         match (impl_generics.is_empty(), func.generics.is_empty()) {
 459             (true, _) => (Some(impl_self), &func.generics),
 460             (_, true) => (Some(impl_self), impl_generics),
 461             (false, false) => {
 462                 let mut params = func.generics.params.clone();
 463                 params.extend(impl_generics.params.clone());
 464                 let mut where_predicates = func.generics.where_predicates.clone();
 465                 where_predicates.extend(impl_generics.where_predicates.clone());
 466                 combined_generics = clean::Generics { params, where_predicates };
 467                 (Some(impl_self), &combined_generics)
 468             }
 469         }
 470     } else {
 471         (None, &func.generics)
 472     };
 473
 474     let mut all_types = Vec::new();
 475     for arg in decl.inputs.values.iter() {
 476         let mut args = Vec::new();
 477         add_generics_and_bounds_as_types(self_, generics, &arg.type_, tcx, 0, &mut args, cache);
 478         if !args.is_empty() {
 479             all_types.extend(args);
 480         } else {
 481             if let Some(kind) = arg.type_.def_id(cache).map(|did| tcx.def_kind(did).into()) {
 482                 all_types.push(TypeWithKind::from((get_index_type(&arg.type_, vec![]), kind)));
 483             }
 484         }
 485     }
 486
 487     let mut ret_types = Vec::new();
 488     match decl.output {
 489         FnRetTy::Return(ref return_type) => {
 490             add_generics_and_bounds_as_types(
 491                 self_,
 492                 generics,
 493                 return_type,
 494                 tcx,
 495                 0,
 496                 &mut ret_types,
 497                 cache,
 498             );
 499             if ret_types.is_empty() {
 500                 if let Some(kind) = return_type.def_id(cache).map(|did| tcx.def_kind(did).into()) {
 501                     ret_types.push(TypeWithKind::from((get_index_type(return_type, vec![]), kind)));
 502                 }
 503             }
 504         }
 505         _ => {}
 506     };
 507     (all_types, ret_types)
 508 }