rustdoc/html/render/
search_index.rs

1pub(crate) mod encode;
2
3use std::collections::hash_map::Entry;
4use std::collections::{BTreeMap, VecDeque};
5
6use encode::{bitmap_to_string, write_vlqhex_to_string};
7use rustc_data_structures::fx::{FxHashMap, FxIndexMap};
8use rustc_middle::ty::TyCtxt;
9use rustc_span::def_id::DefId;
10use rustc_span::sym;
11use rustc_span::symbol::{Symbol, kw};
12use serde::ser::{Serialize, SerializeSeq, SerializeStruct, Serializer};
13use thin_vec::ThinVec;
14use tracing::instrument;
15
16use crate::clean::types::{Function, Generics, ItemId, Type, WherePredicate};
17use crate::clean::{self, utils};
18use crate::formats::cache::{Cache, OrphanImplItem};
19use crate::formats::item_type::ItemType;
20use crate::html::format::join_with_double_colon;
21use crate::html::markdown::short_markdown_summary;
22use crate::html::render::ordered_json::OrderedJson;
23use crate::html::render::{self, IndexItem, IndexItemFunctionType, RenderType, RenderTypeId};
24
25/// The serialized search description sharded version
26///
27/// The `index` is a JSON-encoded list of names and other information.
28///
29/// The desc has newlined descriptions, split up by size into 128KiB shards.
30/// For example, `(4, "foo\nbar\nbaz\nquux")`.
31///
32/// There is no single, optimal size for these shards, because it depends on
33/// configuration values that we can't predict or control, such as the version
34/// of HTTP used (HTTP/1.1 would work better with larger files, while HTTP/2
35/// and 3 are more agnostic), transport compression (gzip, zstd, etc), whether
36/// the search query is going to produce a large number of results or a small
37/// number, the bandwidth delay product of the network...
38///
39/// Gzipping some standard library descriptions to guess what transport
40/// compression will do, the compressed file sizes can be as small as 4.9KiB
41/// or as large as 18KiB (ignoring the final 1.9KiB shard of leftovers).
42/// A "reasonable" range for files is for them to be bigger than 1KiB,
43/// since that's about the amount of data that can be transferred in a
44/// single TCP packet, and 64KiB, the maximum amount of data that
45/// TCP can transfer in a single round trip without extensions.
46///
47/// [1]: https://en.wikipedia.org/wiki/Maximum_transmission_unit#MTUs_for_common_media
48/// [2]: https://en.wikipedia.org/wiki/Sliding_window_protocol#Basic_concept
49/// [3]: https://learn.microsoft.com/en-us/troubleshoot/windows-server/networking/description-tcp-features
50pub(crate) struct SerializedSearchIndex {
51    pub(crate) index: OrderedJson,
52    pub(crate) desc: Vec<(usize, String)>,
53}
54
55const DESC_INDEX_SHARD_LEN: usize = 128 * 1024;
56
57/// Builds the search index from the collected metadata
58pub(crate) fn build_index(
59    krate: &clean::Crate,
60    cache: &mut Cache,
61    tcx: TyCtxt<'_>,
62) -> SerializedSearchIndex {
63    // Maps from ID to position in the `crate_paths` array.
64    let mut itemid_to_pathid = FxHashMap::default();
65    let mut primitives = FxHashMap::default();
66    let mut associated_types = FxHashMap::default();
67
68    // item type, display path, re-exported internal path
69    let mut crate_paths: Vec<(ItemType, Vec<Symbol>, Option<Vec<Symbol>>, bool)> = vec![];
70
71    // Attach all orphan items to the type's definition if the type
72    // has since been learned.
73    for &OrphanImplItem { impl_id, parent, ref item, ref impl_generics } in &cache.orphan_impl_items
74    {
75        if let Some((fqp, _)) = cache.paths.get(&parent) {
76            let desc = short_markdown_summary(&item.doc_value(), &item.link_names(cache));
77            cache.search_index.push(IndexItem {
78                ty: item.type_(),
79                defid: item.item_id.as_def_id(),
80                name: item.name.unwrap(),
81                path: join_with_double_colon(&fqp[..fqp.len() - 1]),
82                desc,
83                parent: Some(parent),
84                parent_idx: None,
85                exact_path: None,
86                impl_id,
87                search_type: get_function_type_for_search(
88                    item,
89                    tcx,
90                    impl_generics.as_ref(),
91                    Some(parent),
92                    cache,
93                ),
94                aliases: item.attrs.get_doc_aliases(),
95                deprecation: item.deprecation(tcx),
96            });
97        }
98    }
99
100    let crate_doc =
101        short_markdown_summary(&krate.module.doc_value(), &krate.module.link_names(cache));
102
103    // Aliases added through `#[doc(alias = "...")]`. Since a few items can have the same alias,
104    // we need the alias element to have an array of items.
105    let mut aliases: BTreeMap<String, Vec<usize>> = BTreeMap::new();
106
107    // Sort search index items. This improves the compressibility of the search index.
108    cache.search_index.sort_unstable_by(|k1, k2| {
109        // `sort_unstable_by_key` produces lifetime errors
110        // HACK(rustdoc): should not be sorting `CrateNum` or `DefIndex`, this will soon go away, too
111        let k1 = (&k1.path, k1.name.as_str(), &k1.ty, k1.parent.map(|id| (id.index, id.krate)));
112        let k2 = (&k2.path, k2.name.as_str(), &k2.ty, k2.parent.map(|id| (id.index, id.krate)));
113        Ord::cmp(&k1, &k2)
114    });
115
116    // Set up alias indexes.
117    for (i, item) in cache.search_index.iter().enumerate() {
118        for alias in &item.aliases[..] {
119            aliases.entry(alias.as_str().to_lowercase()).or_default().push(i);
120        }
121    }
122
123    // Reduce `DefId` in paths into smaller sequential numbers,
124    // and prune the paths that do not appear in the index.
125    let mut lastpath = "";
126    let mut lastpathid = 0isize;
127
128    // First, on function signatures
129    let mut search_index = std::mem::take(&mut cache.search_index);
130    for item in search_index.iter_mut() {
131        fn insert_into_map<F: std::hash::Hash + Eq>(
132            map: &mut FxHashMap<F, isize>,
133            itemid: F,
134            lastpathid: &mut isize,
135            crate_paths: &mut Vec<(ItemType, Vec<Symbol>, Option<Vec<Symbol>>, bool)>,
136            item_type: ItemType,
137            path: &[Symbol],
138            exact_path: Option<&[Symbol]>,
139            search_unbox: bool,
140        ) -> RenderTypeId {
141            match map.entry(itemid) {
142                Entry::Occupied(entry) => RenderTypeId::Index(*entry.get()),
143                Entry::Vacant(entry) => {
144                    let pathid = *lastpathid;
145                    entry.insert(pathid);
146                    *lastpathid += 1;
147                    crate_paths.push((
148                        item_type,
149                        path.to_vec(),
150                        exact_path.map(|path| path.to_vec()),
151                        search_unbox,
152                    ));
153                    RenderTypeId::Index(pathid)
154                }
155            }
156        }
157
158        fn convert_render_type_id(
159            id: RenderTypeId,
160            cache: &mut Cache,
161            itemid_to_pathid: &mut FxHashMap<ItemId, isize>,
162            primitives: &mut FxHashMap<Symbol, isize>,
163            associated_types: &mut FxHashMap<Symbol, isize>,
164            lastpathid: &mut isize,
165            crate_paths: &mut Vec<(ItemType, Vec<Symbol>, Option<Vec<Symbol>>, bool)>,
166            tcx: TyCtxt<'_>,
167        ) -> Option<RenderTypeId> {
168            use crate::clean::PrimitiveType;
169            let Cache { ref paths, ref external_paths, ref exact_paths, .. } = *cache;
170            let search_unbox = match id {
171                RenderTypeId::Mut => false,
172                RenderTypeId::DefId(defid) => utils::has_doc_flag(tcx, defid, sym::search_unbox),
173                RenderTypeId::Primitive(PrimitiveType::Reference | PrimitiveType::Tuple) => true,
174                RenderTypeId::Primitive(..) => false,
175                RenderTypeId::AssociatedType(..) => false,
176                // this bool is only used by `insert_into_map`, so it doesn't matter what we set here
177                // because Index means we've already inserted into the map
178                RenderTypeId::Index(_) => false,
179            };
180            match id {
181                RenderTypeId::Mut => Some(insert_into_map(
182                    primitives,
183                    kw::Mut,
184                    lastpathid,
185                    crate_paths,
186                    ItemType::Keyword,
187                    &[kw::Mut],
188                    None,
189                    search_unbox,
190                )),
191                RenderTypeId::DefId(defid) => {
192                    if let Some(&(ref fqp, item_type)) =
193                        paths.get(&defid).or_else(|| external_paths.get(&defid))
194                    {
195                        let exact_fqp = exact_paths
196                            .get(&defid)
197                            .or_else(|| external_paths.get(&defid).map(|(fqp, _)| fqp))
198                            // Re-exports only count if the name is exactly the same.
199                            // This is a size optimization, since it means we only need
200                            // to store the name once (and the path is re-used for everything
201                            // exported from this same module). It's also likely to Do
202                            // What I Mean, since if a re-export changes the name, it might
203                            // also be a change in semantic meaning.
204                            .filter(|this_fqp| this_fqp.last() == fqp.last());
205                        Some(insert_into_map(
206                            itemid_to_pathid,
207                            ItemId::DefId(defid),
208                            lastpathid,
209                            crate_paths,
210                            item_type,
211                            fqp,
212                            exact_fqp.map(|x| &x[..]).filter(|exact_fqp| exact_fqp != fqp),
213                            search_unbox,
214                        ))
215                    } else {
216                        None
217                    }
218                }
219                RenderTypeId::Primitive(primitive) => {
220                    let sym = primitive.as_sym();
221                    Some(insert_into_map(
222                        primitives,
223                        sym,
224                        lastpathid,
225                        crate_paths,
226                        ItemType::Primitive,
227                        &[sym],
228                        None,
229                        search_unbox,
230                    ))
231                }
232                RenderTypeId::Index(_) => Some(id),
233                RenderTypeId::AssociatedType(sym) => Some(insert_into_map(
234                    associated_types,
235                    sym,
236                    lastpathid,
237                    crate_paths,
238                    ItemType::AssocType,
239                    &[sym],
240                    None,
241                    search_unbox,
242                )),
243            }
244        }
245
246        fn convert_render_type(
247            ty: &mut RenderType,
248            cache: &mut Cache,
249            itemid_to_pathid: &mut FxHashMap<ItemId, isize>,
250            primitives: &mut FxHashMap<Symbol, isize>,
251            associated_types: &mut FxHashMap<Symbol, isize>,
252            lastpathid: &mut isize,
253            crate_paths: &mut Vec<(ItemType, Vec<Symbol>, Option<Vec<Symbol>>, bool)>,
254            tcx: TyCtxt<'_>,
255        ) {
256            if let Some(generics) = &mut ty.generics {
257                for item in generics {
258                    convert_render_type(
259                        item,
260                        cache,
261                        itemid_to_pathid,
262                        primitives,
263                        associated_types,
264                        lastpathid,
265                        crate_paths,
266                        tcx,
267                    );
268                }
269            }
270            if let Some(bindings) = &mut ty.bindings {
271                bindings.retain_mut(|(associated_type, constraints)| {
272                    let converted_associated_type = convert_render_type_id(
273                        *associated_type,
274                        cache,
275                        itemid_to_pathid,
276                        primitives,
277                        associated_types,
278                        lastpathid,
279                        crate_paths,
280                        tcx,
281                    );
282                    let Some(converted_associated_type) = converted_associated_type else {
283                        return false;
284                    };
285                    *associated_type = converted_associated_type;
286                    for constraint in constraints {
287                        convert_render_type(
288                            constraint,
289                            cache,
290                            itemid_to_pathid,
291                            primitives,
292                            associated_types,
293                            lastpathid,
294                            crate_paths,
295                            tcx,
296                        );
297                    }
298                    true
299                });
300            }
301            let Some(id) = ty.id else {
302                assert!(ty.generics.is_some());
303                return;
304            };
305            ty.id = convert_render_type_id(
306                id,
307                cache,
308                itemid_to_pathid,
309                primitives,
310                associated_types,
311                lastpathid,
312                crate_paths,
313                tcx,
314            );
315        }
316        if let Some(search_type) = &mut item.search_type {
317            for item in &mut search_type.inputs {
318                convert_render_type(
319                    item,
320                    cache,
321                    &mut itemid_to_pathid,
322                    &mut primitives,
323                    &mut associated_types,
324                    &mut lastpathid,
325                    &mut crate_paths,
326                    tcx,
327                );
328            }
329            for item in &mut search_type.output {
330                convert_render_type(
331                    item,
332                    cache,
333                    &mut itemid_to_pathid,
334                    &mut primitives,
335                    &mut associated_types,
336                    &mut lastpathid,
337                    &mut crate_paths,
338                    tcx,
339                );
340            }
341            for constraint in &mut search_type.where_clause {
342                for trait_ in &mut constraint[..] {
343                    convert_render_type(
344                        trait_,
345                        cache,
346                        &mut itemid_to_pathid,
347                        &mut primitives,
348                        &mut associated_types,
349                        &mut lastpathid,
350                        &mut crate_paths,
351                        tcx,
352                    );
353                }
354            }
355        }
356    }
357
358    let Cache { ref paths, ref exact_paths, ref external_paths, .. } = *cache;
359
360    // Then, on parent modules
361    let crate_items: Vec<&IndexItem> = search_index
362        .iter_mut()
363        .map(|item| {
364            item.parent_idx =
365                item.parent.and_then(|defid| match itemid_to_pathid.entry(ItemId::DefId(defid)) {
366                    Entry::Occupied(entry) => Some(*entry.get()),
367                    Entry::Vacant(entry) => {
368                        let pathid = lastpathid;
369                        entry.insert(pathid);
370                        lastpathid += 1;
371
372                        if let Some(&(ref fqp, short)) = paths.get(&defid) {
373                            let exact_fqp = exact_paths
374                                .get(&defid)
375                                .or_else(|| external_paths.get(&defid).map(|(fqp, _)| fqp))
376                                .filter(|exact_fqp| {
377                                    exact_fqp.last() == Some(&item.name) && *exact_fqp != fqp
378                                });
379                            crate_paths.push((
380                                short,
381                                fqp.clone(),
382                                exact_fqp.cloned(),
383                                utils::has_doc_flag(tcx, defid, sym::search_unbox),
384                            ));
385                            Some(pathid)
386                        } else {
387                            None
388                        }
389                    }
390                });
391
392            if let Some(defid) = item.defid
393                && item.parent_idx.is_none()
394            {
395                // If this is a re-export, retain the original path.
396                // Associated items don't use this.
397                // Their parent carries the exact fqp instead.
398                let exact_fqp = exact_paths
399                    .get(&defid)
400                    .or_else(|| external_paths.get(&defid).map(|(fqp, _)| fqp));
401                item.exact_path = exact_fqp.and_then(|fqp| {
402                    // Re-exports only count if the name is exactly the same.
403                    // This is a size optimization, since it means we only need
404                    // to store the name once (and the path is re-used for everything
405                    // exported from this same module). It's also likely to Do
406                    // What I Mean, since if a re-export changes the name, it might
407                    // also be a change in semantic meaning.
408                    if fqp.last() != Some(&item.name) {
409                        return None;
410                    }
411                    let path =
412                        if item.ty == ItemType::Macro && tcx.has_attr(defid, sym::macro_export) {
413                            // `#[macro_export]` always exports to the crate root.
414                            tcx.crate_name(defid.krate).to_string()
415                        } else {
416                            if fqp.len() < 2 {
417                                return None;
418                            }
419                            join_with_double_colon(&fqp[..fqp.len() - 1])
420                        };
421                    if path == item.path {
422                        return None;
423                    }
424                    Some(path)
425                });
426            } else if let Some(parent_idx) = item.parent_idx {
427                let i = <isize as TryInto<usize>>::try_into(parent_idx).unwrap();
428                item.path = {
429                    let p = &crate_paths[i].1;
430                    join_with_double_colon(&p[..p.len() - 1])
431                };
432                item.exact_path =
433                    crate_paths[i].2.as_ref().map(|xp| join_with_double_colon(&xp[..xp.len() - 1]));
434            }
435
436            // Omit the parent path if it is same to that of the prior item.
437            if lastpath == item.path {
438                item.path.clear();
439            } else {
440                lastpath = &item.path;
441            }
442
443            &*item
444        })
445        .collect();
446
447    // Find associated items that need disambiguators
448    let mut associated_item_duplicates = FxHashMap::<(isize, ItemType, Symbol), usize>::default();
449
450    for &item in &crate_items {
451        if item.impl_id.is_some()
452            && let Some(parent_idx) = item.parent_idx
453        {
454            let count =
455                associated_item_duplicates.entry((parent_idx, item.ty, item.name)).or_insert(0);
456            *count += 1;
457        }
458    }
459
460    let associated_item_disambiguators = crate_items
461        .iter()
462        .enumerate()
463        .filter_map(|(index, item)| {
464            let impl_id = ItemId::DefId(item.impl_id?);
465            let parent_idx = item.parent_idx?;
466            let count = *associated_item_duplicates.get(&(parent_idx, item.ty, item.name))?;
467            if count > 1 { Some((index, render::get_id_for_impl(tcx, impl_id))) } else { None }
468        })
469        .collect::<Vec<_>>();
470
471    struct CrateData<'a> {
472        items: Vec<&'a IndexItem>,
473        paths: Vec<(ItemType, Vec<Symbol>, Option<Vec<Symbol>>, bool)>,
474        // The String is alias name and the vec is the list of the elements with this alias.
475        //
476        // To be noted: the `usize` elements are indexes to `items`.
477        aliases: &'a BTreeMap<String, Vec<usize>>,
478        // Used when a type has more than one impl with an associated item with the same name.
479        associated_item_disambiguators: &'a Vec<(usize, String)>,
480        // A list of shard lengths encoded as vlqhex. See the comment in write_vlqhex_to_string
481        // for information on the format.
482        desc_index: String,
483        // A list of items with no description. This is eventually turned into a bitmap.
484        empty_desc: Vec<u32>,
485    }
486
487    struct Paths {
488        ty: ItemType,
489        name: Symbol,
490        path: Option<usize>,
491        exact_path: Option<usize>,
492        search_unbox: bool,
493    }
494
495    impl Serialize for Paths {
496        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
497        where
498            S: Serializer,
499        {
500            let mut seq = serializer.serialize_seq(None)?;
501            seq.serialize_element(&self.ty)?;
502            seq.serialize_element(self.name.as_str())?;
503            if let Some(ref path) = self.path {
504                seq.serialize_element(path)?;
505            }
506            if let Some(ref path) = self.exact_path {
507                assert!(self.path.is_some());
508                seq.serialize_element(path)?;
509            }
510            if self.search_unbox {
511                if self.path.is_none() {
512                    seq.serialize_element(&None::<u8>)?;
513                }
514                if self.exact_path.is_none() {
515                    seq.serialize_element(&None::<u8>)?;
516                }
517                seq.serialize_element(&1)?;
518            }
519            seq.end()
520        }
521    }
522
523    impl Serialize for CrateData<'_> {
524        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
525        where
526            S: Serializer,
527        {
528            let mut extra_paths = FxHashMap::default();
529            // We need to keep the order of insertion, hence why we use an `IndexMap`. Then we will
530            // insert these "extra paths" (which are paths of items from external crates) into the
531            // `full_paths` list at the end.
532            let mut revert_extra_paths = FxIndexMap::default();
533            let mut mod_paths = FxHashMap::default();
534            for (index, item) in self.items.iter().enumerate() {
535                if item.path.is_empty() {
536                    continue;
537                }
538                mod_paths.insert(&item.path, index);
539            }
540            let mut paths = Vec::with_capacity(self.paths.len());
541            for &(ty, ref path, ref exact, search_unbox) in &self.paths {
542                if path.len() < 2 {
543                    paths.push(Paths {
544                        ty,
545                        name: path[0],
546                        path: None,
547                        exact_path: None,
548                        search_unbox,
549                    });
550                    continue;
551                }
552                let full_path = join_with_double_colon(&path[..path.len() - 1]);
553                let full_exact_path = exact
554                    .as_ref()
555                    .filter(|exact| exact.last() == path.last() && exact.len() >= 2)
556                    .map(|exact| join_with_double_colon(&exact[..exact.len() - 1]));
557                let exact_path = extra_paths.len() + self.items.len();
558                let exact_path = full_exact_path.as_ref().map(|full_exact_path| match extra_paths
559                    .entry(full_exact_path.clone())
560                {
561                    Entry::Occupied(entry) => *entry.get(),
562                    Entry::Vacant(entry) => {
563                        if let Some(index) = mod_paths.get(&full_exact_path) {
564                            return *index;
565                        }
566                        entry.insert(exact_path);
567                        if !revert_extra_paths.contains_key(&exact_path) {
568                            revert_extra_paths.insert(exact_path, full_exact_path.clone());
569                        }
570                        exact_path
571                    }
572                });
573                if let Some(index) = mod_paths.get(&full_path) {
574                    paths.push(Paths {
575                        ty,
576                        name: *path.last().unwrap(),
577                        path: Some(*index),
578                        exact_path,
579                        search_unbox,
580                    });
581                    continue;
582                }
583                // It means it comes from an external crate so the item and its path will be
584                // stored into another array.
585                //
586                // `index` is put after the last `mod_paths`
587                let index = extra_paths.len() + self.items.len();
588                match extra_paths.entry(full_path.clone()) {
589                    Entry::Occupied(entry) => {
590                        paths.push(Paths {
591                            ty,
592                            name: *path.last().unwrap(),
593                            path: Some(*entry.get()),
594                            exact_path,
595                            search_unbox,
596                        });
597                    }
598                    Entry::Vacant(entry) => {
599                        entry.insert(index);
600                        if !revert_extra_paths.contains_key(&index) {
601                            revert_extra_paths.insert(index, full_path);
602                        }
603                        paths.push(Paths {
604                            ty,
605                            name: *path.last().unwrap(),
606                            path: Some(index),
607                            exact_path,
608                            search_unbox,
609                        });
610                    }
611                }
612            }
613
614            // Direct exports use adjacent arrays for the current crate's items,
615            // but re-exported exact paths don't.
616            let mut re_exports = Vec::new();
617            for (item_index, item) in self.items.iter().enumerate() {
618                if let Some(exact_path) = item.exact_path.as_ref() {
619                    if let Some(path_index) = mod_paths.get(&exact_path) {
620                        re_exports.push((item_index, *path_index));
621                    } else {
622                        let path_index = extra_paths.len() + self.items.len();
623                        let path_index = match extra_paths.entry(exact_path.clone()) {
624                            Entry::Occupied(entry) => *entry.get(),
625                            Entry::Vacant(entry) => {
626                                entry.insert(path_index);
627                                if !revert_extra_paths.contains_key(&path_index) {
628                                    revert_extra_paths.insert(path_index, exact_path.clone());
629                                }
630                                path_index
631                            }
632                        };
633                        re_exports.push((item_index, path_index));
634                    }
635                }
636            }
637
638            let mut names = Vec::with_capacity(self.items.len());
639            let mut types = String::with_capacity(self.items.len());
640            let mut full_paths = Vec::with_capacity(self.items.len());
641            let mut parents = String::with_capacity(self.items.len());
642            let mut parents_backref_queue = VecDeque::new();
643            let mut functions = String::with_capacity(self.items.len());
644            let mut deprecated = Vec::with_capacity(self.items.len());
645
646            let mut type_backref_queue = VecDeque::new();
647
648            let mut last_name = None;
649            for (index, item) in self.items.iter().enumerate() {
650                let n = item.ty as u8;
651                let c = char::from(n + b'A');
652                assert!(c <= 'z', "item types must fit within ASCII printables");
653                types.push(c);
654
655                assert_eq!(
656                    item.parent.is_some(),
657                    item.parent_idx.is_some(),
658                    "`{}` is missing idx",
659                    item.name
660                );
661                assert!(
662                    parents_backref_queue.len() <= 16,
663                    "the string encoding only supports 16 slots of lookback"
664                );
665                let parent: i32 = item.parent_idx.map(|x| x + 1).unwrap_or(0).try_into().unwrap();
666                if let Some(idx) = parents_backref_queue.iter().position(|p: &i32| *p == parent) {
667                    parents.push(
668                        char::try_from('0' as u32 + u32::try_from(idx).unwrap())
669                            .expect("last possible value is '?'"),
670                    );
671                } else if parent == 0 {
672                    write_vlqhex_to_string(parent, &mut parents);
673                } else {
674                    parents_backref_queue.push_front(parent);
675                    write_vlqhex_to_string(parent, &mut parents);
676                    if parents_backref_queue.len() > 16 {
677                        parents_backref_queue.pop_back();
678                    }
679                }
680
681                if Some(item.name.as_str()) == last_name {
682                    names.push("");
683                } else {
684                    names.push(item.name.as_str());
685                    last_name = Some(item.name.as_str());
686                }
687
688                if !item.path.is_empty() {
689                    full_paths.push((index, &item.path));
690                }
691
692                match &item.search_type {
693                    Some(ty) => ty.write_to_string(&mut functions, &mut type_backref_queue),
694                    None => functions.push('`'),
695                }
696
697                if item.deprecation.is_some() {
698                    // bitmasks always use 1-indexing for items, with 0 as the crate itself
699                    deprecated.push(u32::try_from(index + 1).unwrap());
700                }
701            }
702
703            for (index, path) in &revert_extra_paths {
704                full_paths.push((*index, path));
705            }
706
707            let param_names: Vec<(usize, String)> = {
708                let mut prev = Vec::new();
709                let mut result = Vec::new();
710                for (index, item) in self.items.iter().enumerate() {
711                    if let Some(ty) = &item.search_type
712                        && let my =
713                            ty.param_names.iter().map(|sym| sym.as_str()).collect::<Vec<_>>()
714                        && my != prev
715                    {
716                        result.push((index, my.join(",")));
717                        prev = my;
718                    }
719                }
720                result
721            };
722
723            let has_aliases = !self.aliases.is_empty();
724            let mut crate_data =
725                serializer.serialize_struct("CrateData", if has_aliases { 13 } else { 12 })?;
726            crate_data.serialize_field("t", &types)?;
727            crate_data.serialize_field("n", &names)?;
728            crate_data.serialize_field("q", &full_paths)?;
729            crate_data.serialize_field("i", &parents)?;
730            crate_data.serialize_field("f", &functions)?;
731            crate_data.serialize_field("D", &self.desc_index)?;
732            crate_data.serialize_field("p", &paths)?;
733            crate_data.serialize_field("r", &re_exports)?;
734            crate_data.serialize_field("b", &self.associated_item_disambiguators)?;
735            crate_data.serialize_field("c", &bitmap_to_string(&deprecated))?;
736            crate_data.serialize_field("e", &bitmap_to_string(&self.empty_desc))?;
737            crate_data.serialize_field("P", &param_names)?;
738            if has_aliases {
739                crate_data.serialize_field("a", &self.aliases)?;
740            }
741            crate_data.end()
742        }
743    }
744
745    let (empty_desc, desc) = {
746        let mut empty_desc = Vec::new();
747        let mut result = Vec::new();
748        let mut set = String::new();
749        let mut len: usize = 0;
750        let mut item_index: u32 = 0;
751        for desc in std::iter::once(&crate_doc).chain(crate_items.iter().map(|item| &item.desc)) {
752            if desc.is_empty() {
753                empty_desc.push(item_index);
754                item_index += 1;
755                continue;
756            }
757            if set.len() >= DESC_INDEX_SHARD_LEN {
758                result.push((len, std::mem::take(&mut set)));
759                len = 0;
760            } else if len != 0 {
761                set.push('\n');
762            }
763            set.push_str(desc);
764            len += 1;
765            item_index += 1;
766        }
767        result.push((len, std::mem::take(&mut set)));
768        (empty_desc, result)
769    };
770
771    let desc_index = {
772        let mut desc_index = String::with_capacity(desc.len() * 4);
773        for &(len, _) in desc.iter() {
774            write_vlqhex_to_string(len.try_into().unwrap(), &mut desc_index);
775        }
776        desc_index
777    };
778
779    assert_eq!(
780        crate_items.len() + 1,
781        desc.iter().map(|(len, _)| *len).sum::<usize>() + empty_desc.len()
782    );
783
784    // The index, which is actually used to search, is JSON
785    // It uses `JSON.parse(..)` to actually load, since JSON
786    // parses faster than the full JavaScript syntax.
787    let crate_name = krate.name(tcx);
788    let data = CrateData {
789        items: crate_items,
790        paths: crate_paths,
791        aliases: &aliases,
792        associated_item_disambiguators: &associated_item_disambiguators,
793        desc_index,
794        empty_desc,
795    };
796    let index = OrderedJson::array_unsorted([
797        OrderedJson::serialize(crate_name.as_str()).unwrap(),
798        OrderedJson::serialize(data).unwrap(),
799    ]);
800    SerializedSearchIndex { index, desc }
801}
802
803pub(crate) fn get_function_type_for_search(
804    item: &clean::Item,
805    tcx: TyCtxt<'_>,
806    impl_generics: Option<&(clean::Type, clean::Generics)>,
807    parent: Option<DefId>,
808    cache: &Cache,
809) -> Option<IndexItemFunctionType> {
810    let mut trait_info = None;
811    let impl_or_trait_generics = impl_generics.or_else(|| {
812        if let Some(def_id) = parent
813            && let Some(trait_) = cache.traits.get(&def_id)
814            && let Some((path, _)) =
815                cache.paths.get(&def_id).or_else(|| cache.external_paths.get(&def_id))
816        {
817            let path = clean::Path {
818                res: rustc_hir::def::Res::Def(rustc_hir::def::DefKind::Trait, def_id),
819                segments: path
820                    .iter()
821                    .map(|name| clean::PathSegment {
822                        name: *name,
823                        args: clean::GenericArgs::AngleBracketed {
824                            args: ThinVec::new(),
825                            constraints: ThinVec::new(),
826                        },
827                    })
828                    .collect(),
829            };
830            trait_info = Some((clean::Type::Path { path }, trait_.generics.clone()));
831            Some(trait_info.as_ref().unwrap())
832        } else {
833            None
834        }
835    });
836    let (mut inputs, mut output, param_names, where_clause) = match item.kind {
837        clean::ForeignFunctionItem(ref f, _)
838        | clean::FunctionItem(ref f)
839        | clean::MethodItem(ref f, _)
840        | clean::RequiredMethodItem(ref f) => {
841            get_fn_inputs_and_outputs(f, tcx, impl_or_trait_generics, cache)
842        }
843        clean::ConstantItem(ref c) => make_nullary_fn(&c.type_),
844        clean::StaticItem(ref s) => make_nullary_fn(&s.type_),
845        clean::StructFieldItem(ref t) if let Some(parent) = parent => {
846            let mut rgen: FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)> =
847                Default::default();
848            let output = get_index_type(t, vec![], &mut rgen);
849            let input = RenderType {
850                id: Some(RenderTypeId::DefId(parent)),
851                generics: None,
852                bindings: None,
853            };
854            (vec![input], vec![output], vec![], vec![])
855        }
856        _ => return None,
857    };
858
859    inputs.retain(|a| a.id.is_some() || a.generics.is_some());
860    output.retain(|a| a.id.is_some() || a.generics.is_some());
861
862    Some(IndexItemFunctionType { inputs, output, where_clause, param_names })
863}
864
865fn get_index_type(
866    clean_type: &clean::Type,
867    generics: Vec<RenderType>,
868    rgen: &mut FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)>,
869) -> RenderType {
870    RenderType {
871        id: get_index_type_id(clean_type, rgen),
872        generics: if generics.is_empty() { None } else { Some(generics) },
873        bindings: None,
874    }
875}
876
877fn get_index_type_id(
878    clean_type: &clean::Type,
879    rgen: &mut FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)>,
880) -> Option<RenderTypeId> {
881    use rustc_hir::def::{DefKind, Res};
882    match *clean_type {
883        clean::Type::Path { ref path, .. } => Some(RenderTypeId::DefId(path.def_id())),
884        clean::DynTrait(ref bounds, _) => {
885            bounds.first().map(|b| RenderTypeId::DefId(b.trait_.def_id()))
886        }
887        clean::Primitive(p) => Some(RenderTypeId::Primitive(p)),
888        clean::BorrowedRef { .. } => Some(RenderTypeId::Primitive(clean::PrimitiveType::Reference)),
889        clean::RawPointer(_, ref type_) => get_index_type_id(type_, rgen),
890        // The type parameters are converted to generics in `simplify_fn_type`
891        clean::Slice(_) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Slice)),
892        clean::Array(_, _) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Array)),
893        clean::BareFunction(_) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Fn)),
894        clean::Tuple(ref n) if n.is_empty() => {
895            Some(RenderTypeId::Primitive(clean::PrimitiveType::Unit))
896        }
897        clean::Tuple(_) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Tuple)),
898        clean::QPath(ref data) => {
899            if data.self_type.is_self_type()
900                && let Some(clean::Path { res: Res::Def(DefKind::Trait, trait_), .. }) = data.trait_
901            {
902                let idx = -isize::try_from(rgen.len() + 1).unwrap();
903                let (idx, _) = rgen
904                    .entry(SimplifiedParam::AssociatedType(trait_, data.assoc.name))
905                    .or_insert_with(|| (idx, Vec::new()));
906                Some(RenderTypeId::Index(*idx))
907            } else {
908                None
909            }
910        }
911        // Not supported yet
912        clean::Type::Pat(..)
913        | clean::Generic(_)
914        | clean::SelfTy
915        | clean::ImplTrait(_)
916        | clean::Infer
917        | clean::UnsafeBinder(_) => None,
918    }
919}
920
921#[derive(Clone, Copy, Eq, Hash, PartialEq)]
922enum SimplifiedParam {
923    // other kinds of type parameters are identified by their name
924    Symbol(Symbol),
925    // every argument-position impl trait is its own type parameter
926    Anonymous(isize),
927    // in a trait definition, the associated types are all bound to
928    // their own type parameter
929    AssociatedType(DefId, Symbol),
930}
931
932/// The point of this function is to lower generics and types into the simplified form that the
933/// frontend search engine can use.
934///
935/// For example, `[T, U, i32]]` where you have the bounds: `T: Display, U: Option<T>` will return
936/// `[-1, -2, i32] where -1: Display, -2: Option<-1>`. If a type parameter has no traid bound, it
937/// will still get a number. If a constraint is present but not used in the actual types, it will
938/// not be added to the map.
939///
940/// This function also works recursively.
941#[instrument(level = "trace", skip(tcx, res, rgen, cache))]
942fn simplify_fn_type<'a, 'tcx>(
943    self_: Option<&'a Type>,
944    generics: &Generics,
945    arg: &'a Type,
946    tcx: TyCtxt<'tcx>,
947    recurse: usize,
948    res: &mut Vec<RenderType>,
949    rgen: &mut FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)>,
950    is_return: bool,
951    cache: &Cache,
952) {
953    if recurse >= 10 {
954        // FIXME: remove this whole recurse thing when the recursion bug is fixed
955        // See #59502 for the original issue.
956        return;
957    }
958
959    // First, check if it's "Self".
960    let (is_self, arg) = if let Some(self_) = self_
961        && arg.is_self_type()
962    {
963        (true, self_)
964    } else {
965        (false, arg)
966    };
967
968    // If this argument is a type parameter and not a trait bound or a type, we need to look
969    // for its bounds.
970    match *arg {
971        Type::Generic(arg_s) => {
972            // First we check if the bounds are in a `where` predicate...
973            let mut type_bounds = Vec::new();
974            for where_pred in generics.where_predicates.iter().filter(|g| match g {
975                WherePredicate::BoundPredicate { ty, .. } => *ty == *arg,
976                _ => false,
977            }) {
978                let bounds = where_pred.get_bounds().unwrap_or(&[]);
979                for bound in bounds.iter() {
980                    if let Some(path) = bound.get_trait_path() {
981                        let ty = Type::Path { path };
982                        simplify_fn_type(
983                            self_,
984                            generics,
985                            &ty,
986                            tcx,
987                            recurse + 1,
988                            &mut type_bounds,
989                            rgen,
990                            is_return,
991                            cache,
992                        );
993                    }
994                }
995            }
996            // Otherwise we check if the trait bounds are "inlined" like `T: Option<u32>`...
997            if let Some(bound) = generics.params.iter().find(|g| g.is_type() && g.name == arg_s) {
998                for bound in bound.get_bounds().unwrap_or(&[]) {
999                    if let Some(path) = bound.get_trait_path() {
1000                        let ty = Type::Path { path };
1001                        simplify_fn_type(
1002                            self_,
1003                            generics,
1004                            &ty,
1005                            tcx,
1006                            recurse + 1,
1007                            &mut type_bounds,
1008                            rgen,
1009                            is_return,
1010                            cache,
1011                        );
1012                    }
1013                }
1014            }
1015            if let Some((idx, _)) = rgen.get(&SimplifiedParam::Symbol(arg_s)) {
1016                res.push(RenderType {
1017                    id: Some(RenderTypeId::Index(*idx)),
1018                    generics: None,
1019                    bindings: None,
1020                });
1021            } else {
1022                let idx = -isize::try_from(rgen.len() + 1).unwrap();
1023                rgen.insert(SimplifiedParam::Symbol(arg_s), (idx, type_bounds));
1024                res.push(RenderType {
1025                    id: Some(RenderTypeId::Index(idx)),
1026                    generics: None,
1027                    bindings: None,
1028                });
1029            }
1030        }
1031        Type::ImplTrait(ref bounds) => {
1032            let mut type_bounds = Vec::new();
1033            for bound in bounds {
1034                if let Some(path) = bound.get_trait_path() {
1035                    let ty = Type::Path { path };
1036                    simplify_fn_type(
1037                        self_,
1038                        generics,
1039                        &ty,
1040                        tcx,
1041                        recurse + 1,
1042                        &mut type_bounds,
1043                        rgen,
1044                        is_return,
1045                        cache,
1046                    );
1047                }
1048            }
1049            if is_return && !type_bounds.is_empty() {
1050                // In return position, `impl Trait` is a unique thing.
1051                res.push(RenderType { id: None, generics: Some(type_bounds), bindings: None });
1052            } else {
1053                // In parameter position, `impl Trait` is the same as an unnamed generic parameter.
1054                let idx = -isize::try_from(rgen.len() + 1).unwrap();
1055                rgen.insert(SimplifiedParam::Anonymous(idx), (idx, type_bounds));
1056                res.push(RenderType {
1057                    id: Some(RenderTypeId::Index(idx)),
1058                    generics: None,
1059                    bindings: None,
1060                });
1061            }
1062        }
1063        Type::Slice(ref ty) => {
1064            let mut ty_generics = Vec::new();
1065            simplify_fn_type(
1066                self_,
1067                generics,
1068                ty,
1069                tcx,
1070                recurse + 1,
1071                &mut ty_generics,
1072                rgen,
1073                is_return,
1074                cache,
1075            );
1076            res.push(get_index_type(arg, ty_generics, rgen));
1077        }
1078        Type::Array(ref ty, _) => {
1079            let mut ty_generics = Vec::new();
1080            simplify_fn_type(
1081                self_,
1082                generics,
1083                ty,
1084                tcx,
1085                recurse + 1,
1086                &mut ty_generics,
1087                rgen,
1088                is_return,
1089                cache,
1090            );
1091            res.push(get_index_type(arg, ty_generics, rgen));
1092        }
1093        Type::Tuple(ref tys) => {
1094            let mut ty_generics = Vec::new();
1095            for ty in tys {
1096                simplify_fn_type(
1097                    self_,
1098                    generics,
1099                    ty,
1100                    tcx,
1101                    recurse + 1,
1102                    &mut ty_generics,
1103                    rgen,
1104                    is_return,
1105                    cache,
1106                );
1107            }
1108            res.push(get_index_type(arg, ty_generics, rgen));
1109        }
1110        Type::BareFunction(ref bf) => {
1111            let mut ty_generics = Vec::new();
1112            for ty in bf.decl.inputs.values.iter().map(|arg| &arg.type_) {
1113                simplify_fn_type(
1114                    self_,
1115                    generics,
1116                    ty,
1117                    tcx,
1118                    recurse + 1,
1119                    &mut ty_generics,
1120                    rgen,
1121                    is_return,
1122                    cache,
1123                );
1124            }
1125            // The search index, for simplicity's sake, represents fn pointers and closures
1126            // the same way: as a tuple for the parameters, and an associated type for the
1127            // return type.
1128            let mut ty_output = Vec::new();
1129            simplify_fn_type(
1130                self_,
1131                generics,
1132                &bf.decl.output,
1133                tcx,
1134                recurse + 1,
1135                &mut ty_output,
1136                rgen,
1137                is_return,
1138                cache,
1139            );
1140            let ty_bindings = vec![(RenderTypeId::AssociatedType(sym::Output), ty_output)];
1141            res.push(RenderType {
1142                id: get_index_type_id(arg, rgen),
1143                bindings: Some(ty_bindings),
1144                generics: Some(ty_generics),
1145            });
1146        }
1147        Type::BorrowedRef { lifetime: _, mutability, ref type_ } => {
1148            let mut ty_generics = Vec::new();
1149            if mutability.is_mut() {
1150                ty_generics.push(RenderType {
1151                    id: Some(RenderTypeId::Mut),
1152                    generics: None,
1153                    bindings: None,
1154                });
1155            }
1156            simplify_fn_type(
1157                self_,
1158                generics,
1159                type_,
1160                tcx,
1161                recurse + 1,
1162                &mut ty_generics,
1163                rgen,
1164                is_return,
1165                cache,
1166            );
1167            res.push(get_index_type(arg, ty_generics, rgen));
1168        }
1169        _ => {
1170            // This is not a type parameter. So for example if we have `T, U: Option<T>`, and we're
1171            // looking at `Option`, we enter this "else" condition, otherwise if it's `T`, we don't.
1172            //
1173            // So in here, we can add it directly and look for its own type parameters (so for `Option`,
1174            // we will look for them but not for `T`).
1175            let mut ty_generics = Vec::new();
1176            let mut ty_constraints = Vec::new();
1177            if let Some(arg_generics) = arg.generic_args() {
1178                for ty in arg_generics.into_iter().filter_map(|param| match param {
1179                    clean::GenericArg::Type(ty) => Some(ty),
1180                    _ => None,
1181                }) {
1182                    simplify_fn_type(
1183                        self_,
1184                        generics,
1185                        &ty,
1186                        tcx,
1187                        recurse + 1,
1188                        &mut ty_generics,
1189                        rgen,
1190                        is_return,
1191                        cache,
1192                    );
1193                }
1194                for constraint in arg_generics.constraints() {
1195                    simplify_fn_constraint(
1196                        self_,
1197                        generics,
1198                        &constraint,
1199                        tcx,
1200                        recurse + 1,
1201                        &mut ty_constraints,
1202                        rgen,
1203                        is_return,
1204                        cache,
1205                    );
1206                }
1207            }
1208            // Every trait associated type on self gets assigned to a type parameter index
1209            // this same one is used later for any appearances of these types
1210            //
1211            // for example, Iterator::next is:
1212            //
1213            //     trait Iterator {
1214            //         fn next(&mut self) -> Option<Self::Item>
1215            //     }
1216            //
1217            // Self is technically just Iterator, but we want to pretend it's more like this:
1218            //
1219            //     fn next<T>(self: Iterator<Item=T>) -> Option<T>
1220            if is_self
1221                && let Type::Path { path } = arg
1222                && let def_id = path.def_id()
1223                && let Some(trait_) = cache.traits.get(&def_id)
1224                && trait_.items.iter().any(|at| at.is_required_associated_type())
1225            {
1226                for assoc_ty in &trait_.items {
1227                    if let clean::ItemKind::RequiredAssocTypeItem(_generics, bounds) =
1228                        &assoc_ty.kind
1229                        && let Some(name) = assoc_ty.name
1230                    {
1231                        let idx = -isize::try_from(rgen.len() + 1).unwrap();
1232                        let (idx, stored_bounds) = rgen
1233                            .entry(SimplifiedParam::AssociatedType(def_id, name))
1234                            .or_insert_with(|| (idx, Vec::new()));
1235                        let idx = *idx;
1236                        if stored_bounds.is_empty() {
1237                            // Can't just pass stored_bounds to simplify_fn_type,
1238                            // because it also accepts rgen as a parameter.
1239                            // Instead, have it fill in this local, then copy it into the map afterward.
1240                            let mut type_bounds = Vec::new();
1241                            for bound in bounds {
1242                                if let Some(path) = bound.get_trait_path() {
1243                                    let ty = Type::Path { path };
1244                                    simplify_fn_type(
1245                                        self_,
1246                                        generics,
1247                                        &ty,
1248                                        tcx,
1249                                        recurse + 1,
1250                                        &mut type_bounds,
1251                                        rgen,
1252                                        is_return,
1253                                        cache,
1254                                    );
1255                                }
1256                            }
1257                            let stored_bounds = &mut rgen
1258                                .get_mut(&SimplifiedParam::AssociatedType(def_id, name))
1259                                .unwrap()
1260                                .1;
1261                            if stored_bounds.is_empty() {
1262                                *stored_bounds = type_bounds;
1263                            }
1264                        }
1265                        ty_constraints.push((
1266                            RenderTypeId::AssociatedType(name),
1267                            vec![RenderType {
1268                                id: Some(RenderTypeId::Index(idx)),
1269                                generics: None,
1270                                bindings: None,
1271                            }],
1272                        ))
1273                    }
1274                }
1275            }
1276            let id = get_index_type_id(arg, rgen);
1277            if id.is_some() || !ty_generics.is_empty() {
1278                res.push(RenderType {
1279                    id,
1280                    bindings: if ty_constraints.is_empty() { None } else { Some(ty_constraints) },
1281                    generics: if ty_generics.is_empty() { None } else { Some(ty_generics) },
1282                });
1283            }
1284        }
1285    }
1286}
1287
1288fn simplify_fn_constraint<'a>(
1289    self_: Option<&'a Type>,
1290    generics: &Generics,
1291    constraint: &'a clean::AssocItemConstraint,
1292    tcx: TyCtxt<'_>,
1293    recurse: usize,
1294    res: &mut Vec<(RenderTypeId, Vec<RenderType>)>,
1295    rgen: &mut FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)>,
1296    is_return: bool,
1297    cache: &Cache,
1298) {
1299    let mut ty_constraints = Vec::new();
1300    let ty_constrained_assoc = RenderTypeId::AssociatedType(constraint.assoc.name);
1301    for param in &constraint.assoc.args {
1302        match param {
1303            clean::GenericArg::Type(arg) => simplify_fn_type(
1304                self_,
1305                generics,
1306                &arg,
1307                tcx,
1308                recurse + 1,
1309                &mut ty_constraints,
1310                rgen,
1311                is_return,
1312                cache,
1313            ),
1314            clean::GenericArg::Lifetime(_)
1315            | clean::GenericArg::Const(_)
1316            | clean::GenericArg::Infer => {}
1317        }
1318    }
1319    for constraint in constraint.assoc.args.constraints() {
1320        simplify_fn_constraint(
1321            self_,
1322            generics,
1323            &constraint,
1324            tcx,
1325            recurse + 1,
1326            res,
1327            rgen,
1328            is_return,
1329            cache,
1330        );
1331    }
1332    match &constraint.kind {
1333        clean::AssocItemConstraintKind::Equality { term } => {
1334            if let clean::Term::Type(arg) = &term {
1335                simplify_fn_type(
1336                    self_,
1337                    generics,
1338                    arg,
1339                    tcx,
1340                    recurse + 1,
1341                    &mut ty_constraints,
1342                    rgen,
1343                    is_return,
1344                    cache,
1345                );
1346            }
1347        }
1348        clean::AssocItemConstraintKind::Bound { bounds } => {
1349            for bound in &bounds[..] {
1350                if let Some(path) = bound.get_trait_path() {
1351                    let ty = Type::Path { path };
1352                    simplify_fn_type(
1353                        self_,
1354                        generics,
1355                        &ty,
1356                        tcx,
1357                        recurse + 1,
1358                        &mut ty_constraints,
1359                        rgen,
1360                        is_return,
1361                        cache,
1362                    );
1363                }
1364            }
1365        }
1366    }
1367    res.push((ty_constrained_assoc, ty_constraints));
1368}
1369
1370/// Create a fake nullary function.
1371///
1372/// Used to allow type-based search on constants and statics.
1373fn make_nullary_fn(
1374    clean_type: &clean::Type,
1375) -> (Vec<RenderType>, Vec<RenderType>, Vec<Symbol>, Vec<Vec<RenderType>>) {
1376    let mut rgen: FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)> = Default::default();
1377    let output = get_index_type(clean_type, vec![], &mut rgen);
1378    (vec![], vec![output], vec![], vec![])
1379}
1380
1381/// Return the full list of types when bounds have been resolved.
1382///
1383/// i.e. `fn foo<A: Display, B: Option<A>>(x: u32, y: B)` will return
1384/// `[u32, Display, Option]`.
1385fn get_fn_inputs_and_outputs(
1386    func: &Function,
1387    tcx: TyCtxt<'_>,
1388    impl_or_trait_generics: Option<&(clean::Type, clean::Generics)>,
1389    cache: &Cache,
1390) -> (Vec<RenderType>, Vec<RenderType>, Vec<Symbol>, Vec<Vec<RenderType>>) {
1391    let decl = &func.decl;
1392
1393    let mut rgen: FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)> = Default::default();
1394
1395    let combined_generics;
1396    let (self_, generics) = if let Some((impl_self, impl_generics)) = impl_or_trait_generics {
1397        match (impl_generics.is_empty(), func.generics.is_empty()) {
1398            (true, _) => (Some(impl_self), &func.generics),
1399            (_, true) => (Some(impl_self), impl_generics),
1400            (false, false) => {
1401                let params =
1402                    func.generics.params.iter().chain(&impl_generics.params).cloned().collect();
1403                let where_predicates = func
1404                    .generics
1405                    .where_predicates
1406                    .iter()
1407                    .chain(&impl_generics.where_predicates)
1408                    .cloned()
1409                    .collect();
1410                combined_generics = clean::Generics { params, where_predicates };
1411                (Some(impl_self), &combined_generics)
1412            }
1413        }
1414    } else {
1415        (None, &func.generics)
1416    };
1417
1418    let mut arg_types = Vec::new();
1419    for arg in decl.inputs.values.iter() {
1420        simplify_fn_type(
1421            self_,
1422            generics,
1423            &arg.type_,
1424            tcx,
1425            0,
1426            &mut arg_types,
1427            &mut rgen,
1428            false,
1429            cache,
1430        );
1431    }
1432
1433    let mut ret_types = Vec::new();
1434    simplify_fn_type(self_, generics, &decl.output, tcx, 0, &mut ret_types, &mut rgen, true, cache);
1435
1436    let mut simplified_params = rgen.into_iter().collect::<Vec<_>>();
1437    simplified_params.sort_by_key(|(_, (idx, _))| -idx);
1438    (
1439        arg_types,
1440        ret_types,
1441        simplified_params
1442            .iter()
1443            .map(|(name, (_idx, _traits))| match name {
1444                SimplifiedParam::Symbol(name) => *name,
1445                SimplifiedParam::Anonymous(_) => kw::Empty,
1446                SimplifiedParam::AssociatedType(def_id, name) => {
1447                    Symbol::intern(&format!("{}::{}", tcx.item_name(*def_id), name))
1448                }
1449            })
1450            .collect(),
1451        simplified_params.into_iter().map(|(_name, (_idx, traits))| traits).collect(),
1452    )
1453}