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