]>
Commit | Line | Data |
---|---|---|
dfeec247 | 1 | use std::collections::BTreeMap; |
60c5eb7d | 2 | |
6a06907d XL |
3 | use rustc_data_structures::fx::{FxHashMap, FxHashSet}; |
4 | use rustc_middle::ty::TyCtxt; | |
17df50a5 | 5 | use rustc_span::symbol::Symbol; |
6a06907d | 6 | use serde::ser::{Serialize, SerializeStruct, Serializer}; |
e74abb32 | 7 | |
cdc7bbd5 | 8 | use crate::clean; |
6a06907d | 9 | use crate::clean::types::{ |
17df50a5 | 10 | FnDecl, FnRetTy, GenericBound, Generics, GetDefId, Type, WherePredicate, |
6a06907d | 11 | }; |
3dfed10e XL |
12 | use crate::formats::cache::Cache; |
13 | use crate::formats::item_type::ItemType; | |
fc512014 | 14 | use crate::html::markdown::short_markdown_summary; |
136023e0 | 15 | use crate::html::render::{IndexItem, IndexItemFunctionType, RenderType, TypeWithKind}; |
e74abb32 XL |
16 | |
17 | /// Indicates where an external crate can be found. | |
fc512014 | 18 | crate enum ExternalLocation { |
e74abb32 XL |
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 | ||
e74abb32 | 27 | /// Builds the search index from the collected metadata |
6a06907d | 28 | crate fn build_index<'tcx>(krate: &clean::Crate, cache: &mut Cache, tcx: TyCtxt<'tcx>) -> String { |
74b04a01 | 29 | let mut defid_to_pathid = FxHashMap::default(); |
e74abb32 | 30 | let mut crate_items = Vec::with_capacity(cache.search_index.len()); |
60c5eb7d | 31 | let mut crate_paths = vec![]; |
e74abb32 | 32 | |
e74abb32 XL |
33 | // Attach all orphan items to the type's definition if the type |
34 | // has since been learned. | |
5869c6ff XL |
35 | for &(did, ref item) in &cache.orphan_impl_items { |
36 | if let Some(&(ref fqp, _)) = cache.paths.get(&did) { | |
136023e0 XL |
37 | let desc = item |
38 | .doc_value() | |
39 | .map_or_else(String::new, |s| short_markdown_summary(&s, &item.link_names(&cache))); | |
5869c6ff | 40 | cache.search_index.push(IndexItem { |
e74abb32 | 41 | ty: item.type_(), |
fc512014 | 42 | name: item.name.unwrap().to_string(), |
e74abb32 | 43 | path: fqp[..fqp.len() - 1].join("::"), |
136023e0 | 44 | desc, |
17df50a5 | 45 | parent: Some(did.into()), |
e74abb32 | 46 | parent_idx: None, |
136023e0 | 47 | search_type: get_index_search_type(&item, tcx), |
cdc7bbd5 | 48 | aliases: item.attrs.get_doc_aliases(), |
e74abb32 XL |
49 | }); |
50 | } | |
51 | } | |
52 | ||
136023e0 XL |
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 | ||
cdc7bbd5 XL |
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 | } | |
5869c6ff | 78 | |
74b04a01 | 79 | // Reduce `DefId` in paths into smaller sequential numbers, |
e74abb32 XL |
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 { | |
ba9703b0 | 85 | item.parent_idx = item.parent.and_then(|defid| { |
74b04a01 | 86 | if defid_to_pathid.contains_key(&defid) { |
ba9703b0 | 87 | defid_to_pathid.get(&defid).copied() |
e74abb32 XL |
88 | } else { |
89 | let pathid = lastpathid; | |
74b04a01 | 90 | defid_to_pathid.insert(defid, pathid); |
e74abb32 XL |
91 | lastpathid += 1; |
92 | ||
ba9703b0 XL |
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 | } | |
e74abb32 XL |
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 | } | |
60c5eb7d | 108 | crate_items.push(&*item); |
e74abb32 XL |
109 | } |
110 | ||
60c5eb7d XL |
111 | struct CrateData<'a> { |
112 | doc: String, | |
60c5eb7d | 113 | items: Vec<&'a IndexItem>, |
60c5eb7d | 114 | paths: Vec<(ItemType, String)>, |
f9f354fc XL |
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`. | |
f9f354fc | 118 | aliases: &'a BTreeMap<String, Vec<usize>>, |
60c5eb7d | 119 | } |
e74abb32 | 120 | |
6a06907d XL |
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 | ||
e74abb32 | 174 | // Collect the index into a string |
60c5eb7d | 175 | format!( |
ba9703b0 | 176 | r#""{}":{}"#, |
60c5eb7d XL |
177 | krate.name, |
178 | serde_json::to_string(&CrateData { | |
179 | doc: crate_doc, | |
180 | items: crate_items, | |
181 | paths: crate_paths, | |
cdc7bbd5 | 182 | aliases: &aliases, |
60c5eb7d | 183 | }) |
dfeec247 | 184 | .expect("failed serde conversion") |
ba9703b0 XL |
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("\\\"", "\\\\\"") | |
60c5eb7d | 190 | ) |
e74abb32 XL |
191 | } |
192 | ||
6a06907d | 193 | crate fn get_index_search_type<'tcx>( |
5869c6ff | 194 | item: &clean::Item, |
6a06907d | 195 | tcx: TyCtxt<'tcx>, |
5869c6ff XL |
196 | ) -> Option<IndexItemFunctionType> { |
197 | let (all_types, ret_types) = match *item.kind { | |
6a06907d XL |
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), | |
e74abb32 XL |
201 | _ => return None, |
202 | }; | |
203 | ||
ba9703b0 XL |
204 | let inputs = all_types |
205 | .iter() | |
136023e0 | 206 | .map(|(ty, kind)| TypeWithKind::from((get_index_type(&ty), *kind))) |
ba9703b0 XL |
207 | .filter(|a| a.ty.name.is_some()) |
208 | .collect(); | |
dfeec247 XL |
209 | let output = ret_types |
210 | .iter() | |
136023e0 | 211 | .map(|(ty, kind)| TypeWithKind::from((get_index_type(&ty), *kind))) |
ba9703b0 | 212 | .filter(|a| a.ty.name.is_some()) |
dfeec247 XL |
213 | .collect::<Vec<_>>(); |
214 | let output = if output.is_empty() { None } else { Some(output) }; | |
e74abb32 XL |
215 | |
216 | Some(IndexItemFunctionType { inputs, output }) | |
217 | } | |
218 | ||
136023e0 | 219 | fn get_index_type(clean_type: &clean::Type) -> RenderType { |
ba9703b0 | 220 | RenderType { |
fc512014 | 221 | name: get_index_type_name(clean_type, true).map(|s| s.as_str().to_ascii_lowercase()), |
136023e0 | 222 | generics: get_generics(clean_type), |
ba9703b0 | 223 | } |
e74abb32 XL |
224 | } |
225 | ||
fc512014 | 226 | fn get_index_type_name(clean_type: &clean::Type, accept_generic: bool) -> Option<Symbol> { |
e74abb32 XL |
227 | match *clean_type { |
228 | clean::ResolvedPath { ref path, .. } => { | |
229 | let segments = &path.segments; | |
3dfed10e XL |
230 | let path_segment = segments.iter().last().unwrap_or_else(|| { |
231 | panic!( | |
e74abb32 XL |
232 | "get_index_type_name(clean_type: {:?}, accept_generic: {:?}) had length zero path", |
233 | clean_type, accept_generic | |
3dfed10e XL |
234 | ) |
235 | }); | |
fc512014 | 236 | Some(path_segment.name) |
e74abb32 | 237 | } |
136023e0 | 238 | clean::DynTrait(ref bounds, _) => get_index_type_name(&bounds[0].trait_, accept_generic), |
fc512014 XL |
239 | clean::Generic(s) if accept_generic => Some(s), |
240 | clean::Primitive(ref p) => Some(p.as_sym()), | |
e74abb32 | 241 | clean::BorrowedRef { ref type_, .. } => get_index_type_name(type_, accept_generic), |
5869c6ff XL |
242 | clean::Generic(_) |
243 | | clean::BareFunction(_) | |
244 | | clean::Tuple(_) | |
245 | | clean::Slice(_) | |
246 | | clean::Array(_, _) | |
247 | | clean::Never | |
248 | | clean::RawPointer(_, _) | |
249 | | clean::QPath { .. } | |
250 | | clean::Infer | |
251 | | clean::ImplTrait(_) => None, | |
e74abb32 XL |
252 | } |
253 | } | |
254 | ||
136023e0 XL |
255 | /// Return a list of generic parameters for use in the search index. |
256 | /// | |
257 | /// This function replaces bounds with types, so that `T where T: Debug` just becomes `Debug`. | |
258 | /// It does return duplicates, and that's intentional, since search queries like `Result<usize, usize>` | |
259 | /// are supposed to match only results where both parameters are `usize`. | |
260 | fn get_generics(clean_type: &clean::Type) -> Option<Vec<String>> { | |
dfeec247 XL |
261 | clean_type.generics().and_then(|types| { |
262 | let r = types | |
263 | .iter() | |
ba9703b0 | 264 | .filter_map(|t| { |
136023e0 | 265 | get_index_type_name(t, false).map(|name| name.as_str().to_ascii_lowercase()) |
ba9703b0 | 266 | }) |
dfeec247 XL |
267 | .collect::<Vec<_>>(); |
268 | if r.is_empty() { None } else { Some(r) } | |
269 | }) | |
e74abb32 | 270 | } |
6a06907d XL |
271 | |
272 | /// The point of this function is to replace bounds with types. | |
273 | /// | |
274 | /// i.e. `[T, U]` when you have the following bounds: `T: Display, U: Option<T>` will return | |
275 | /// `[Display, Option]` (we just returns the list of the types, we don't care about the | |
276 | /// wrapped types in here). | |
277 | crate fn get_real_types<'tcx>( | |
278 | generics: &Generics, | |
279 | arg: &Type, | |
280 | tcx: TyCtxt<'tcx>, | |
281 | recurse: i32, | |
cdc7bbd5 | 282 | res: &mut FxHashSet<(Type, ItemType)>, |
6a06907d | 283 | ) -> usize { |
cdc7bbd5 | 284 | fn insert(res: &mut FxHashSet<(Type, ItemType)>, tcx: TyCtxt<'_>, ty: Type) -> usize { |
6a06907d XL |
285 | if let Some(kind) = ty.def_id().map(|did| tcx.def_kind(did).into()) { |
286 | res.insert((ty, kind)); | |
287 | 1 | |
288 | } else if ty.is_primitive() { | |
289 | // This is a primitive, let's store it as such. | |
cdc7bbd5 | 290 | res.insert((ty, ItemType::Primitive)); |
6a06907d XL |
291 | 1 |
292 | } else { | |
293 | 0 | |
294 | } | |
295 | } | |
296 | ||
297 | if recurse >= 10 { | |
298 | // FIXME: remove this whole recurse thing when the recursion bug is fixed | |
299 | return 0; | |
300 | } | |
301 | let mut nb_added = 0; | |
302 | ||
303 | if let &Type::Generic(arg_s) = arg { | |
304 | if let Some(where_pred) = generics.where_predicates.iter().find(|g| match g { | |
305 | WherePredicate::BoundPredicate { ty, .. } => ty.def_id() == arg.def_id(), | |
306 | _ => false, | |
307 | }) { | |
308 | let bounds = where_pred.get_bounds().unwrap_or_else(|| &[]); | |
309 | for bound in bounds.iter() { | |
310 | if let GenericBound::TraitBound(poly_trait, _) = bound { | |
311 | for x in poly_trait.generic_params.iter() { | |
312 | if !x.is_type() { | |
313 | continue; | |
314 | } | |
315 | if let Some(ty) = x.get_type() { | |
316 | let adds = get_real_types(generics, &ty, tcx, recurse + 1, res); | |
317 | nb_added += adds; | |
318 | if adds == 0 && !ty.is_full_generic() { | |
319 | nb_added += insert(res, tcx, ty); | |
320 | } | |
321 | } | |
322 | } | |
323 | } | |
324 | } | |
325 | } | |
326 | if let Some(bound) = generics.params.iter().find(|g| g.is_type() && g.name == arg_s) { | |
327 | for bound in bound.get_bounds().unwrap_or(&[]) { | |
328 | if let Some(ty) = bound.get_trait_type() { | |
329 | let adds = get_real_types(generics, &ty, tcx, recurse + 1, res); | |
330 | nb_added += adds; | |
331 | if adds == 0 && !ty.is_full_generic() { | |
332 | nb_added += insert(res, tcx, ty); | |
333 | } | |
334 | } | |
335 | } | |
336 | } | |
337 | } else { | |
338 | nb_added += insert(res, tcx, arg.clone()); | |
339 | if let Some(gens) = arg.generics() { | |
340 | for gen in gens.iter() { | |
341 | if gen.is_full_generic() { | |
342 | nb_added += get_real_types(generics, gen, tcx, recurse + 1, res); | |
343 | } else { | |
344 | nb_added += insert(res, tcx, (*gen).clone()); | |
345 | } | |
346 | } | |
347 | } | |
348 | } | |
349 | nb_added | |
350 | } | |
351 | ||
352 | /// Return the full list of types when bounds have been resolved. | |
353 | /// | |
354 | /// i.e. `fn foo<A: Display, B: Option<A>>(x: u32, y: B)` will return | |
355 | /// `[u32, Display, Option]`. | |
356 | crate fn get_all_types<'tcx>( | |
357 | generics: &Generics, | |
358 | decl: &FnDecl, | |
359 | tcx: TyCtxt<'tcx>, | |
cdc7bbd5 | 360 | ) -> (Vec<(Type, ItemType)>, Vec<(Type, ItemType)>) { |
6a06907d XL |
361 | let mut all_types = FxHashSet::default(); |
362 | for arg in decl.inputs.values.iter() { | |
363 | if arg.type_.is_self_type() { | |
364 | continue; | |
365 | } | |
366 | let mut args = FxHashSet::default(); | |
367 | get_real_types(generics, &arg.type_, tcx, 0, &mut args); | |
368 | if !args.is_empty() { | |
369 | all_types.extend(args); | |
370 | } else { | |
371 | if let Some(kind) = arg.type_.def_id().map(|did| tcx.def_kind(did).into()) { | |
372 | all_types.insert((arg.type_.clone(), kind)); | |
373 | } | |
374 | } | |
375 | } | |
376 | ||
377 | let ret_types = match decl.output { | |
378 | FnRetTy::Return(ref return_type) => { | |
379 | let mut ret = FxHashSet::default(); | |
380 | get_real_types(generics, &return_type, tcx, 0, &mut ret); | |
381 | if ret.is_empty() { | |
382 | if let Some(kind) = return_type.def_id().map(|did| tcx.def_kind(did).into()) { | |
383 | ret.insert((return_type.clone(), kind)); | |
384 | } | |
385 | } | |
386 | ret.into_iter().collect() | |
387 | } | |
388 | _ => Vec::new(), | |
389 | }; | |
390 | (all_types.into_iter().collect(), ret_types) | |
391 | } |