1 use std
::collections
::BTreeMap
;
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}
;
9 use crate::clean
::types
::{
10 FnDecl
, FnRetTy
, GenericBound
, Generics
, GetDefId
, Type
, WherePredicate
,
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}
;
17 /// Indicates where an external crate can be found.
18 crate enum ExternalLocation
{
19 /// Remote URL root of the external crate
21 /// This external crate can be found in the local doc/ folder
23 /// The external crate could not be found.
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
![];
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
) {
39 .map_or_else(String
::new
, |s
| short_markdown_summary(&s
, &item
.link_names(&cache
)));
40 cache
.search_index
.push(IndexItem
{
42 name
: item
.name
.unwrap().to_string(),
43 path
: fqp
[..fqp
.len() - 1].join("::"),
47 search_type
: get_index_search_type(&item
, tcx
),
48 aliases
: item
.attrs
.get_doc_aliases(),
56 .map_or_else(String
::new
, |s
| short_markdown_summary(&s
, &krate
.module
.link_names(&cache
)));
58 let Cache { ref mut search_index, ref paths, .. }
= *cache
;
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();
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
)
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
);
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
;
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()
89 let pathid
= lastpathid
;
90 defid_to_pathid
.insert(defid
, pathid
);
93 if let Some(&(ref fqp
, short
)) = paths
.get(&defid
) {
94 crate_paths
.push((short
, fqp
.last().unwrap().clone()));
102 // Omit the parent path if it is same to that of the prior item.
103 if lastpath
== item
.path
{
106 lastpath
= item
.path
.clone();
108 crate_items
.push(&*item
);
111 struct CrateData
<'a
> {
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.
117 // To be noted: the `usize` elements are indexes to `items`.
118 aliases
: &'a BTreeMap
<String
, Vec
<usize>>,
121 impl<'a
> Serialize
for CrateData
<'a
> {
122 fn serialize
<S
>(&self, serializer
: S
) -> Result
<S
::Ok
, S
::Error
>
126 let has_aliases
= !self.aliases
.is_empty();
128 serializer
.serialize_struct("CrateData", if has_aliases { 9 }
else { 8 }
)?
;
129 crate_data
.serialize_field("doc", &self.doc
)?
;
130 crate_data
.serialize_field(
132 &self.items
.iter().map(|item
| &item
.ty
).collect
::<Vec
<_
>>(),
134 crate_data
.serialize_field(
136 &self.items
.iter().map(|item
| &item
.name
).collect
::<Vec
<_
>>(),
138 crate_data
.serialize_field(
140 &self.items
.iter().map(|item
| &item
.path
).collect
::<Vec
<_
>>(),
142 crate_data
.serialize_field(
144 &self.items
.iter().map(|item
| &item
.desc
).collect
::<Vec
<_
>>(),
146 crate_data
.serialize_field(
153 item
.parent
.is_some(),
154 item
.parent_idx
.is_some(),
155 "`{}` is missing idx",
158 item
.parent_idx
.map(|x
| x
+ 1).unwrap_or(0)
160 .collect
::<Vec
<_
>>(),
162 crate_data
.serialize_field(
164 &self.items
.iter().map(|item
| &item
.search_type
).collect
::<Vec
<_
>>(),
166 crate_data
.serialize_field("p", &self.paths
)?
;
168 crate_data
.serialize_field("a", &self.aliases
)?
;
174 // Collect the index into a string
178 serde_json
::to_string(&CrateData
{
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
"\\")
188 // We need to escape double quotes for the JSON.
189 .replace("\\\"", "\\\\\"")
193 crate fn get_index_search_type
<'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
),
204 let inputs
= all_types
206 .map(|(ty
, kind
)| TypeWithKind
::from((get_index_type(&ty
), *kind
)))
207 .filter(|a
| a
.ty
.name
.is_some())
209 let output
= ret_types
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) }
;
216 Some(IndexItemFunctionType { inputs, output }
)
219 fn get_index_type(clean_type
: &clean
::Type
) -> RenderType
{
221 name
: get_index_type_name(clean_type
, true).map(|s
| s
.as_str().to_ascii_lowercase()),
222 generics
: get_generics(clean_type
),
226 fn get_index_type_name(clean_type
: &clean
::Type
, accept_generic
: bool
) -> Option
<Symbol
> {
228 clean
::ResolvedPath { ref path, .. }
=> {
229 let segments
= &path
.segments
;
230 let path_segment
= segments
.iter().last().unwrap_or_else(|| {
232 "get_index_type_name(clean_type: {:?}, accept_generic: {:?}) had length zero path",
233 clean_type
, accept_generic
236 Some(path_segment
.name
)
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
),
243 | clean
::BareFunction(_
)
248 | clean
::RawPointer(_
, _
)
249 | clean
::QPath { .. }
251 | clean
::ImplTrait(_
) => None
,
255 /// Return a list of generic parameters for use in the search index.
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
>> {
261 clean_type
.generics().and_then(|types
| {
265 get_index_type_name(t
, false).map(|name
| name
.as_str().to_ascii_lowercase())
267 .collect
::<Vec
<_
>>();
268 if r
.is_empty() { None }
else { Some(r) }
272 /// The point of this function is to replace bounds with types.
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
>(
282 res
: &mut FxHashSet
<(Type
, ItemType
)>,
284 fn insert(res
: &mut FxHashSet
<(Type
, ItemType
)>, tcx
: TyCtxt
<'_
>, ty
: Type
) -> usize {
285 if let Some(kind
) = ty
.def_id().map(|did
| tcx
.def_kind(did
).into()) {
286 res
.insert((ty
, kind
));
288 } else if ty
.is_primitive() {
289 // This is a primitive, let's store it as such.
290 res
.insert((ty
, ItemType
::Primitive
));
298 // FIXME: remove this whole recurse thing when the recursion bug is fixed
301 let mut nb_added
= 0;
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(),
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() {
315 if let Some(ty
) = x
.get_type() {
316 let adds
= get_real_types(generics
, &ty
, tcx
, recurse
+ 1, res
);
318 if adds
== 0 && !ty
.is_full_generic() {
319 nb_added
+= insert(res
, tcx
, ty
);
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
);
331 if adds
== 0 && !ty
.is_full_generic() {
332 nb_added
+= insert(res
, tcx
, ty
);
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
);
344 nb_added
+= insert(res
, tcx
, (*gen
).clone());
352 /// Return the full list of types when bounds have been resolved.
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
>(
360 ) -> (Vec
<(Type
, ItemType
)>, Vec
<(Type
, ItemType
)>) {
361 let mut all_types
= FxHashSet
::default();
362 for arg
in decl
.inputs
.values
.iter() {
363 if arg
.type_
.is_self_type() {
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
);
371 if let Some(kind
) = arg
.type_
.def_id().map(|did
| tcx
.def_kind(did
).into()) {
372 all_types
.insert((arg
.type_
.clone(), kind
));
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
);
382 if let Some(kind
) = return_type
.def_id().map(|did
| tcx
.def_kind(did
).into()) {
383 ret
.insert((return_type
.clone(), kind
));
386 ret
.into_iter().collect()
390 (all_types
.into_iter().collect(), ret_types
)