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
25pub(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
57pub(crate) fn build_index(
59 krate: &clean::Crate,
60 cache: &mut Cache,
61 tcx: TyCtxt<'_>,
62) -> SerializedSearchIndex {
63 let mut itemid_to_pathid = FxHashMap::default();
65 let mut primitives = FxHashMap::default();
66 let mut associated_types = FxHashMap::default();
67
68 let mut crate_paths: Vec<(ItemType, Vec<Symbol>, Option<Vec<Symbol>>, bool)> = vec![];
70
71 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 let mut aliases: BTreeMap<String, Vec<usize>> = BTreeMap::new();
106
107 cache.search_index.sort_unstable_by(|k1, k2| {
109 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 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 let mut lastpath = "";
126 let mut lastpathid = 0isize;
127
128 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 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 .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 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 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 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 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 if lastpath == item.path {
438 item.path.clear();
439 } else {
440 lastpath = &item.path;
441 }
442
443 &*item
444 })
445 .collect();
446
447 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 aliases: &'a BTreeMap<String, Vec<usize>>,
478 associated_item_disambiguators: &'a Vec<(usize, String)>,
480 desc_index: String,
483 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 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 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 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 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", ¶m_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 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 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 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 Symbol(Symbol),
925 Anonymous(isize),
927 AssociatedType(DefId, Symbol),
930}
931
932#[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 return;
957 }
958
959 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 match *arg {
971 Type::Generic(arg_s) => {
972 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 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 res.push(RenderType { id: None, generics: Some(type_bounds), bindings: None });
1052 } else {
1053 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 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 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 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 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
1370fn 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
1381fn 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}