src/librustdoc/html/render/cache.rs

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