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