src/librustdoc/html/render/cache.rs

   1 use std::collections::BTreeMap;
   2
   3 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
   4 use rustc_middle::ty::TyCtxt;
   5 use rustc_span::symbol::Symbol;
   6 use serde::ser::{Serialize, SerializeStruct, Serializer};
   7
   8 use crate::clean;
   9 use crate::clean::types::{
  10     FnDecl, FnRetTy, GenericBound, Generics, GetDefId, Type, WherePredicate,
  11 };
  12 use crate::formats::cache::Cache;
  13 use crate::formats::item_type::ItemType;
  14 use crate::html::markdown::short_markdown_summary;
  15 use crate::html::render::{IndexItem, IndexItemFunctionType, RenderType, TypeWithKind};
  16
  17 /// Indicates where an external crate can be found.
  18 crate enum ExternalLocation {
  19     /// Remote URL root of the external crate
  20     Remote(String),
  21     /// This external crate can be found in the local doc/ folder
  22     Local,
  23     /// The external crate could not be found.
  24     Unknown,
  25 }
  26
  27 /// Builds the search index from the collected metadata
  28 crate fn build_index<'tcx>(krate: &clean::Crate, cache: &mut Cache, tcx: TyCtxt<'tcx>) -> String {
  29     let mut defid_to_pathid = FxHashMap::default();
  30     let mut crate_items = Vec::with_capacity(cache.search_index.len());
  31     let mut crate_paths = vec![];
  32
  33     // Attach all orphan items to the type's definition if the type
  34     // has since been learned.
  35     for &(did, ref item) in &cache.orphan_impl_items {
  36         if let Some(&(ref fqp, _)) = cache.paths.get(&did) {
  37             let desc = item
  38                 .doc_value()
  39                 .map_or_else(String::new, |s| short_markdown_summary(&s, &item.link_names(&cache)));
  40             cache.search_index.push(IndexItem {
  41                 ty: item.type_(),
  42                 name: item.name.unwrap().to_string(),
  43                 path: fqp[..fqp.len() - 1].join("::"),
  44                 desc,
  45                 parent: Some(did),
  46                 parent_idx: None,
  47                 search_type: get_index_search_type(&item, tcx),
  48                 aliases: item.attrs.get_doc_aliases(),
  49             });
  50         }
  51     }
  52
  53     let crate_doc = krate
  54         .module
  55         .doc_value()
  56         .map_or_else(String::new, |s| short_markdown_summary(&s, &krate.module.link_names(&cache)));
  57
  58     let Cache { ref mut search_index, ref paths, .. } = *cache;
  59
  60     // Aliases added through `#[doc(alias = "...")]`. Since a few items can have the same alias,
  61     // we need the alias element to have an array of items.
  62     let mut aliases: BTreeMap<String, Vec<usize>> = BTreeMap::new();
  63
  64     // Sort search index items. This improves the compressibility of the search index.
  65     search_index.sort_unstable_by(|k1, k2| {
  66         // `sort_unstable_by_key` produces lifetime errors
  67         let k1 = (&k1.path, &k1.name, &k1.ty, &k1.parent);
  68         let k2 = (&k2.path, &k2.name, &k2.ty, &k2.parent);
  69         std::cmp::Ord::cmp(&k1, &k2)
  70     });
  71
  72     // Set up alias indexes.
  73     for (i, item) in search_index.iter().enumerate() {
  74         for alias in &item.aliases[..] {
  75             aliases.entry(alias.to_lowercase()).or_insert(Vec::new()).push(i);
  76         }
  77     }
  78
  79     // Reduce `DefId` in paths into smaller sequential numbers,
  80     // and prune the paths that do not appear in the index.
  81     let mut lastpath = String::new();
  82     let mut lastpathid = 0usize;
  83
  84     for item in search_index {
  85         item.parent_idx = item.parent.and_then(|defid| {
  86             if defid_to_pathid.contains_key(&defid) {
  87                 defid_to_pathid.get(&defid).copied()
  88             } else {
  89                 let pathid = lastpathid;
  90                 defid_to_pathid.insert(defid, pathid);
  91                 lastpathid += 1;
  92
  93                 if let Some(&(ref fqp, short)) = paths.get(&defid) {
  94                     crate_paths.push((short, fqp.last().unwrap().clone()));
  95                     Some(pathid)
  96                 } else {
  97                     None
  98                 }
  99             }
 100         });
 101
 102         // Omit the parent path if it is same to that of the prior item.
 103         if lastpath == item.path {
 104             item.path.clear();
 105         } else {
 106             lastpath = item.path.clone();
 107         }
 108         crate_items.push(&*item);
 109     }
 110
 111     struct CrateData<'a> {
 112         doc: String,
 113         items: Vec<&'a IndexItem>,
 114         paths: Vec<(ItemType, String)>,
 115         // The String is alias name and the vec is the list of the elements with this alias.
 116         //
 117         // To be noted: the `usize` elements are indexes to `items`.
 118         aliases: &'a BTreeMap<String, Vec<usize>>,
 119     }
 120
 121     impl<'a> Serialize for CrateData<'a> {
 122         fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
 123         where
 124             S: Serializer,
 125         {
 126             let has_aliases = !self.aliases.is_empty();
 127             let mut crate_data =
 128                 serializer.serialize_struct("CrateData", if has_aliases { 9 } else { 8 })?;
 129             crate_data.serialize_field("doc", &self.doc)?;
 130             crate_data.serialize_field(
 131                 "t",
 132                 &self.items.iter().map(|item| &item.ty).collect::<Vec<_>>(),
 133             )?;
 134             crate_data.serialize_field(
 135                 "n",
 136                 &self.items.iter().map(|item| &item.name).collect::<Vec<_>>(),
 137             )?;
 138             crate_data.serialize_field(
 139                 "q",
 140                 &self.items.iter().map(|item| &item.path).collect::<Vec<_>>(),
 141             )?;
 142             crate_data.serialize_field(
 143                 "d",
 144                 &self.items.iter().map(|item| &item.desc).collect::<Vec<_>>(),
 145             )?;
 146             crate_data.serialize_field(
 147                 "i",
 148                 &self
 149                     .items
 150                     .iter()
 151                     .map(|item| {
 152                         assert_eq!(
 153                             item.parent.is_some(),
 154                             item.parent_idx.is_some(),
 155                             "`{}` is missing idx",
 156                             item.name
 157                         );
 158                         item.parent_idx.map(|x| x + 1).unwrap_or(0)
 159                     })
 160                     .collect::<Vec<_>>(),
 161             )?;
 162             crate_data.serialize_field(
 163                 "f",
 164                 &self.items.iter().map(|item| &item.search_type).collect::<Vec<_>>(),
 165             )?;
 166             crate_data.serialize_field("p", &self.paths)?;
 167             if has_aliases {
 168                 crate_data.serialize_field("a", &self.aliases)?;
 169             }
 170             crate_data.end()
 171         }
 172     }
 173
 174     // Collect the index into a string
 175     format!(
 176         r#""{}":{}"#,
 177         krate.name,
 178         serde_json::to_string(&CrateData {
 179             doc: crate_doc,
 180             items: crate_items,
 181             paths: crate_paths,
 182             aliases: &aliases,
 183         })
 184         .expect("failed serde conversion")
 185         // All these `replace` calls are because we have to go through JS string for JSON content.
 186         .replace(r"\", r"\\")
 187         .replace("'", r"\'")
 188         // We need to escape double quotes for the JSON.
 189         .replace("\\\"", "\\\\\"")
 190     )
 191 }
 192
 193 crate fn get_index_search_type<'tcx>(
 194     item: &clean::Item,
 195     tcx: TyCtxt<'tcx>,
 196 ) -> Option<IndexItemFunctionType> {
 197     let (all_types, ret_types) = match *item.kind {
 198         clean::FunctionItem(ref f) => get_all_types(&f.generics, &f.decl, tcx),
 199         clean::MethodItem(ref m, _) => get_all_types(&m.generics, &m.decl, tcx),
 200         clean::TyMethodItem(ref m) => get_all_types(&m.generics, &m.decl, tcx),
 201         _ => return None,
 202     };
 203
 204     let inputs = all_types
 205         .iter()
 206         .map(|(ty, kind)| TypeWithKind::from((get_index_type(&ty), *kind)))
 207         .filter(|a| a.ty.name.is_some())
 208         .collect();
 209     let output = ret_types
 210         .iter()
 211         .map(|(ty, kind)| TypeWithKind::from((get_index_type(&ty), *kind)))
 212         .filter(|a| a.ty.name.is_some())
 213         .collect::<Vec<_>>();
 214     let output = if output.is_empty() { None } else { Some(output) };
 215
 216     Some(IndexItemFunctionType { inputs, output })
 217 }
 218
 219 fn get_index_type(clean_type: &clean::Type) -> RenderType {
 220     RenderType {
 221         name: get_index_type_name(clean_type, true).map(|s| s.as_str().to_ascii_lowercase()),
 222         generics: get_generics(clean_type),
 223     }
 224 }
 225
 226 fn get_index_type_name(clean_type: &clean::Type, accept_generic: bool) -> Option<Symbol> {
 227     match *clean_type {
 228         clean::ResolvedPath { ref path, .. } => {
 229             let segments = &path.segments;
 230             let path_segment = segments.iter().last().unwrap_or_else(|| {
 231                 panic!(
 232                 "get_index_type_name(clean_type: {:?}, accept_generic: {:?}) had length zero path",
 233                 clean_type, accept_generic
 234             )
 235             });
 236             Some(path_segment.name)
 237         }
 238         clean::DynTrait(ref bounds, _) => get_index_type_name(&bounds[0].trait_, accept_generic),
 239         clean::Generic(s) if accept_generic => Some(s),
 240         clean::Primitive(ref p) => Some(p.as_sym()),
 241         clean::BorrowedRef { ref type_, .. } => get_index_type_name(type_, accept_generic),
 242         clean::Generic(_)
 243         | clean::BareFunction(_)
 244         | clean::Tuple(_)
 245         | clean::Slice(_)
 246         | clean::Array(_, _)
 247         | clean::RawPointer(_, _)
 248         | clean::QPath { .. }
 249         | clean::Infer
 250         | clean::ImplTrait(_) => None,
 251     }
 252 }
 253
 254 /// Return a list of generic parameters for use in the search index.
 255 ///
 256 /// This function replaces bounds with types, so that `T where T: Debug` just becomes `Debug`.
 257 /// It does return duplicates, and that's intentional, since search queries like `Result<usize, usize>`
 258 /// are supposed to match only results where both parameters are `usize`.
 259 fn get_generics(clean_type: &clean::Type) -> Option<Vec<String>> {
 260     clean_type.generics().and_then(|types| {
 261         let r = types
 262             .iter()
 263             .filter_map(|t| {
 264                 get_index_type_name(t, false).map(|name| name.as_str().to_ascii_lowercase())
 265             })
 266             .collect::<Vec<_>>();
 267         if r.is_empty() { None } else { Some(r) }
 268     })
 269 }
 270
 271 /// The point of this function is to replace bounds with types.
 272 ///
 273 /// i.e. `[T, U]` when you have the following bounds: `T: Display, U: Option<T>` will return
 274 /// `[Display, Option]` (we just returns the list of the types, we don't care about the
 275 /// wrapped types in here).
 276 crate fn get_real_types<'tcx>(
 277     generics: &Generics,
 278     arg: &Type,
 279     tcx: TyCtxt<'tcx>,
 280     recurse: i32,
 281     res: &mut FxHashSet<(Type, ItemType)>,
 282 ) -> usize {
 283     fn insert(res: &mut FxHashSet<(Type, ItemType)>, tcx: TyCtxt<'_>, ty: Type) -> usize {
 284         if let Some(kind) = ty.def_id().map(|did| tcx.def_kind(did).into()) {
 285             res.insert((ty, kind));
 286             1
 287         } else if ty.is_primitive() {
 288             // This is a primitive, let's store it as such.
 289             res.insert((ty, ItemType::Primitive));
 290             1
 291         } else {
 292             0
 293         }
 294     }
 295
 296     if recurse >= 10 {
 297         // FIXME: remove this whole recurse thing when the recursion bug is fixed
 298         return 0;
 299     }
 300     let mut nb_added = 0;
 301
 302     if let &Type::Generic(arg_s) = arg {
 303         if let Some(where_pred) = generics.where_predicates.iter().find(|g| match g {
 304             WherePredicate::BoundPredicate { ty, .. } => ty.def_id() == arg.def_id(),
 305             _ => false,
 306         }) {
 307             let bounds = where_pred.get_bounds().unwrap_or_else(|| &[]);
 308             for bound in bounds.iter() {
 309                 if let GenericBound::TraitBound(poly_trait, _) = bound {
 310                     for x in poly_trait.generic_params.iter() {
 311                         if !x.is_type() {
 312                             continue;
 313                         }
 314                         if let Some(ty) = x.get_type() {
 315                             let adds = get_real_types(generics, &ty, tcx, recurse + 1, res);
 316                             nb_added += adds;
 317                             if adds == 0 && !ty.is_full_generic() {
 318                                 nb_added += insert(res, tcx, ty);
 319                             }
 320                         }
 321                     }
 322                 }
 323             }
 324         }
 325         if let Some(bound) = generics.params.iter().find(|g| g.is_type() && g.name == arg_s) {
 326             for bound in bound.get_bounds().unwrap_or(&[]) {
 327                 if let Some(ty) = bound.get_trait_type() {
 328                     let adds = get_real_types(generics, &ty, tcx, recurse + 1, res);
 329                     nb_added += adds;
 330                     if adds == 0 && !ty.is_full_generic() {
 331                         nb_added += insert(res, tcx, ty);
 332                     }
 333                 }
 334             }
 335         }
 336     } else {
 337         nb_added += insert(res, tcx, arg.clone());
 338         if let Some(gens) = arg.generics() {
 339             for gen in gens.iter() {
 340                 if gen.is_full_generic() {
 341                     nb_added += get_real_types(generics, gen, tcx, recurse + 1, res);
 342                 } else {
 343                     nb_added += insert(res, tcx, (*gen).clone());
 344                 }
 345             }
 346         }
 347     }
 348     nb_added
 349 }
 350
 351 /// Return the full list of types when bounds have been resolved.
 352 ///
 353 /// i.e. `fn foo<A: Display, B: Option<A>>(x: u32, y: B)` will return
 354 /// `[u32, Display, Option]`.
 355 crate fn get_all_types<'tcx>(
 356     generics: &Generics,
 357     decl: &FnDecl,
 358     tcx: TyCtxt<'tcx>,
 359 ) -> (Vec<(Type, ItemType)>, Vec<(Type, ItemType)>) {
 360     let mut all_types = FxHashSet::default();
 361     for arg in decl.inputs.values.iter() {
 362         if arg.type_.is_self_type() {
 363             continue;
 364         }
 365         let mut args = FxHashSet::default();
 366         get_real_types(generics, &arg.type_, tcx, 0, &mut args);
 367         if !args.is_empty() {
 368             all_types.extend(args);
 369         } else {
 370             if let Some(kind) = arg.type_.def_id().map(|did| tcx.def_kind(did).into()) {
 371                 all_types.insert((arg.type_.clone(), kind));
 372             }
 373         }
 374     }
 375
 376     let ret_types = match decl.output {
 377         FnRetTy::Return(ref return_type) => {
 378             let mut ret = FxHashSet::default();
 379             get_real_types(generics, &return_type, tcx, 0, &mut ret);
 380             if ret.is_empty() {
 381                 if let Some(kind) = return_type.def_id().map(|did| tcx.def_kind(did).into()) {
 382                     ret.insert((return_type.clone(), kind));
 383                 }
 384             }
 385             ret.into_iter().collect()
 386         }
 387         _ => Vec::new(),
 388     };
 389     (all_types.into_iter().collect(), ret_types)
 390 }