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