rustdoc/html/render/
search_index.rs

1pub(crate) mod encode;
2mod serde;
3
4use std::collections::BTreeSet;
5use std::collections::hash_map::Entry;
6use std::path::Path;
7use std::string::FromUtf8Error;
8use std::{io, iter};
9
10use ::serde::de::{self, Deserializer, Error as _};
11use ::serde::ser::{SerializeSeq, Serializer};
12use ::serde::{Deserialize, Serialize};
13use rustc_ast::join_path_syms;
14use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexMap};
15use rustc_data_structures::thin_vec::ThinVec;
16use rustc_hir::attrs::AttributeKind;
17use rustc_hir::find_attr;
18use rustc_middle::ty::TyCtxt;
19use rustc_span::def_id::DefId;
20use rustc_span::sym;
21use rustc_span::symbol::{Symbol, kw};
22use stringdex::internals as stringdex_internals;
23use tracing::instrument;
24
25use crate::clean::types::{Function, Generics, ItemId, Type, WherePredicate};
26use crate::clean::{self, utils};
27use crate::config::ShouldMerge;
28use crate::error::Error;
29use crate::formats::cache::{Cache, OrphanImplItem};
30use crate::formats::item_type::ItemType;
31use crate::html::markdown::short_markdown_summary;
32use crate::html::render::{self, IndexItem, IndexItemFunctionType, RenderType, RenderTypeId};
33
34#[derive(Clone, Debug, Default, Deserialize, Serialize)]
35pub(crate) struct SerializedSearchIndex {
36    // data from disk
37    names: Vec<String>,
38    path_data: Vec<Option<PathData>>,
39    entry_data: Vec<Option<EntryData>>,
40    descs: Vec<String>,
41    function_data: Vec<Option<IndexItemFunctionType>>,
42    alias_pointers: Vec<Option<usize>>,
43    // inverted index for concrete types and generics
44    type_data: Vec<Option<TypeData>>,
45    /// inverted index of generics
46    ///
47    /// - The outermost list has one entry per alpha-normalized generic.
48    ///
49    /// - The second layer is sorted by number of types that appear in the
50    ///   type signature. The search engine iterates over these in order from
51    ///   smallest to largest. Functions with less stuff in their type
52    ///   signature are more likely to be what the user wants, because we never
53    ///   show functions that are *missing* parts of the query, so removing..
54    ///
55    /// - The final layer is the list of functions.
56    generic_inverted_index: Vec<Vec<Vec<u32>>>,
57    // generated in-memory backref cache
58    #[serde(skip)]
59    crate_paths_index: FxHashMap<(ItemType, Vec<Symbol>), usize>,
60}
61
62impl SerializedSearchIndex {
63    fn load(doc_root: &Path, resource_suffix: &str) -> Result<SerializedSearchIndex, Error> {
64        let mut names: Vec<String> = Vec::new();
65        let mut path_data: Vec<Option<PathData>> = Vec::new();
66        let mut entry_data: Vec<Option<EntryData>> = Vec::new();
67        let mut descs: Vec<String> = Vec::new();
68        let mut function_data: Vec<Option<IndexItemFunctionType>> = Vec::new();
69        let mut type_data: Vec<Option<TypeData>> = Vec::new();
70        let mut alias_pointers: Vec<Option<usize>> = Vec::new();
71
72        let mut generic_inverted_index: Vec<Vec<Vec<u32>>> = Vec::new();
73
74        match perform_read_strings(resource_suffix, doc_root, "name", &mut names) {
75            Ok(()) => {
76                perform_read_serde(resource_suffix, doc_root, "path", &mut path_data)?;
77                perform_read_serde(resource_suffix, doc_root, "entry", &mut entry_data)?;
78                perform_read_strings(resource_suffix, doc_root, "desc", &mut descs)?;
79                perform_read_serde(resource_suffix, doc_root, "function", &mut function_data)?;
80                perform_read_serde(resource_suffix, doc_root, "type", &mut type_data)?;
81                perform_read_serde(resource_suffix, doc_root, "alias", &mut alias_pointers)?;
82                perform_read_postings(
83                    resource_suffix,
84                    doc_root,
85                    "generic_inverted_index",
86                    &mut generic_inverted_index,
87                )?;
88            }
89            Err(_) => {
90                names.clear();
91            }
92        }
93        fn perform_read_strings(
94            resource_suffix: &str,
95            doc_root: &Path,
96            column_name: &str,
97            column: &mut Vec<String>,
98        ) -> Result<(), Error> {
99            let root_path = doc_root.join(format!("search.index/root{resource_suffix}.js"));
100            let column_path = doc_root.join(format!("search.index/{column_name}/"));
101
102            let mut consume = |_, cell: &[u8]| {
103                column.push(String::from_utf8(cell.to_vec())?);
104                Ok::<_, FromUtf8Error>(())
105            };
106
107            stringdex_internals::read_data_from_disk_column(
108                root_path,
109                column_name.as_bytes(),
110                column_path.clone(),
111                &mut consume,
112            )
113            .map_err(|error| Error {
114                file: column_path,
115                error: format!("failed to read column from disk: {error}"),
116            })
117        }
118        fn perform_read_serde(
119            resource_suffix: &str,
120            doc_root: &Path,
121            column_name: &str,
122            column: &mut Vec<Option<impl for<'de> Deserialize<'de> + 'static>>,
123        ) -> Result<(), Error> {
124            let root_path = doc_root.join(format!("search.index/root{resource_suffix}.js"));
125            let column_path = doc_root.join(format!("search.index/{column_name}/"));
126
127            let mut consume = |_, cell: &[u8]| {
128                if cell.is_empty() {
129                    column.push(None);
130                } else {
131                    column.push(Some(serde_json::from_slice(cell)?));
132                }
133                Ok::<_, serde_json::Error>(())
134            };
135
136            stringdex_internals::read_data_from_disk_column(
137                root_path,
138                column_name.as_bytes(),
139                column_path.clone(),
140                &mut consume,
141            )
142            .map_err(|error| Error {
143                file: column_path,
144                error: format!("failed to read column from disk: {error}"),
145            })
146        }
147        fn perform_read_postings(
148            resource_suffix: &str,
149            doc_root: &Path,
150            column_name: &str,
151            column: &mut Vec<Vec<Vec<u32>>>,
152        ) -> Result<(), Error> {
153            let root_path = doc_root.join(format!("search.index/root{resource_suffix}.js"));
154            let column_path = doc_root.join(format!("search.index/{column_name}/"));
155
156            fn consumer(
157                column: &mut Vec<Vec<Vec<u32>>>,
158            ) -> impl FnMut(u32, &[u8]) -> io::Result<()> {
159                |_, cell| {
160                    let mut postings = Vec::new();
161                    encode::read_postings_from_string(&mut postings, cell);
162                    column.push(postings);
163                    Ok(())
164                }
165            }
166
167            stringdex_internals::read_data_from_disk_column(
168                root_path,
169                column_name.as_bytes(),
170                column_path.clone(),
171                &mut consumer(column),
172            )
173            .map_err(|error| Error {
174                file: column_path,
175                error: format!("failed to read column from disk: {error}"),
176            })
177        }
178
179        assert_eq!(names.len(), path_data.len());
180        assert_eq!(path_data.len(), entry_data.len());
181        assert_eq!(entry_data.len(), descs.len());
182        assert_eq!(descs.len(), function_data.len());
183        assert_eq!(function_data.len(), type_data.len());
184        assert_eq!(type_data.len(), alias_pointers.len());
185
186        // generic_inverted_index is not the same length as other columns,
187        // because it's actually a completely different set of objects
188
189        let mut crate_paths_index: FxHashMap<(ItemType, Vec<Symbol>), usize> = FxHashMap::default();
190        for (i, (name, path_data)) in names.iter().zip(path_data.iter()).enumerate() {
191            if let Some(path_data) = path_data {
192                let full_path = if path_data.module_path.is_empty() {
193                    vec![Symbol::intern(name)]
194                } else {
195                    let mut full_path = path_data.module_path.to_vec();
196                    full_path.push(Symbol::intern(name));
197                    full_path
198                };
199                crate_paths_index.insert((path_data.ty, full_path), i);
200            }
201        }
202
203        Ok(SerializedSearchIndex {
204            names,
205            path_data,
206            entry_data,
207            descs,
208            function_data,
209            type_data,
210            alias_pointers,
211            generic_inverted_index,
212            crate_paths_index,
213        })
214    }
215    fn push(
216        &mut self,
217        name: String,
218        path_data: Option<PathData>,
219        entry_data: Option<EntryData>,
220        desc: String,
221        function_data: Option<IndexItemFunctionType>,
222        type_data: Option<TypeData>,
223        alias_pointer: Option<usize>,
224    ) -> usize {
225        let index = self.names.len();
226        assert_eq!(self.names.len(), self.path_data.len());
227        if let Some(path_data) = &path_data
228            && let name = Symbol::intern(&name)
229            && let fqp = if path_data.module_path.is_empty() {
230                vec![name]
231            } else {
232                let mut v = path_data.module_path.clone();
233                v.push(name);
234                v
235            }
236            && let Some(&other_path) = self.crate_paths_index.get(&(path_data.ty, fqp))
237            && self.path_data.get(other_path).map_or(false, Option::is_some)
238        {
239            self.path_data.push(None);
240        } else {
241            self.path_data.push(path_data);
242        }
243        self.names.push(name);
244        assert_eq!(self.entry_data.len(), self.descs.len());
245        self.entry_data.push(entry_data);
246        assert_eq!(self.descs.len(), self.function_data.len());
247        self.descs.push(desc);
248        assert_eq!(self.function_data.len(), self.type_data.len());
249        self.function_data.push(function_data);
250        assert_eq!(self.type_data.len(), self.alias_pointers.len());
251        self.type_data.push(type_data);
252        self.alias_pointers.push(alias_pointer);
253        index
254    }
255    /// Add potential search result to the database and return the row ID.
256    ///
257    /// The returned ID can be used to attach more data to the search result.
258    fn add_entry(&mut self, name: Symbol, entry_data: EntryData, desc: String) -> usize {
259        let fqp = if let Some(module_path_index) = entry_data.module_path {
260            self.path_data[module_path_index]
261                .as_ref()
262                .unwrap()
263                .module_path
264                .iter()
265                .copied()
266                .chain([Symbol::intern(&self.names[module_path_index]), name])
267                .collect()
268        } else {
269            vec![name]
270        };
271        // If a path with the same name already exists, but no entry does,
272        // we can fill in the entry without having to allocate a new row ID.
273        //
274        // Because paths and entries both share the same index, using the same
275        // ID saves space by making the tree smaller.
276        if let Some(&other_path) = self.crate_paths_index.get(&(entry_data.ty, fqp))
277            && self.entry_data[other_path].is_none()
278            && self.descs[other_path].is_empty()
279        {
280            self.entry_data[other_path] = Some(entry_data);
281            self.descs[other_path] = desc;
282            other_path
283        } else {
284            self.push(name.as_str().to_string(), None, Some(entry_data), desc, None, None, None)
285        }
286    }
287    fn push_path(&mut self, name: String, path_data: PathData) -> usize {
288        self.push(name, Some(path_data), None, String::new(), None, None, None)
289    }
290    fn push_type(&mut self, name: String, path_data: PathData, type_data: TypeData) -> usize {
291        self.push(name, Some(path_data), None, String::new(), None, Some(type_data), None)
292    }
293    fn push_alias(&mut self, name: String, alias_pointer: usize) -> usize {
294        self.push(name, None, None, String::new(), None, None, Some(alias_pointer))
295    }
296
297    fn get_id_by_module_path(&mut self, path: &[Symbol]) -> usize {
298        let ty = if path.len() == 1 { ItemType::ExternCrate } else { ItemType::Module };
299        match self.crate_paths_index.entry((ty, path.to_vec())) {
300            Entry::Occupied(index) => *index.get(),
301            Entry::Vacant(slot) => {
302                slot.insert(self.path_data.len());
303                let (name, module_path) = path.split_last().unwrap();
304                self.push_path(
305                    name.as_str().to_string(),
306                    PathData { ty, module_path: module_path.to_vec(), exact_module_path: None },
307                )
308            }
309        }
310    }
311
312    pub(crate) fn union(mut self, other: &SerializedSearchIndex) -> SerializedSearchIndex {
313        let other_entryid_offset = self.names.len();
314        let mut map_other_pathid_to_self_pathid = Vec::new();
315        let mut skips = FxHashSet::default();
316        for (other_pathid, other_path_data) in other.path_data.iter().enumerate() {
317            if let Some(other_path_data) = other_path_data {
318                let name = Symbol::intern(&other.names[other_pathid]);
319                let fqp =
320                    other_path_data.module_path.iter().copied().chain(iter::once(name)).collect();
321                let self_pathid = other_entryid_offset + other_pathid;
322                let self_pathid = match self.crate_paths_index.entry((other_path_data.ty, fqp)) {
323                    Entry::Vacant(slot) => {
324                        slot.insert(self_pathid);
325                        self_pathid
326                    }
327                    Entry::Occupied(existing_entryid) => {
328                        skips.insert(other_pathid);
329                        let self_pathid = *existing_entryid.get();
330                        let new_type_data = match (
331                            self.type_data[self_pathid].take(),
332                            other.type_data[other_pathid].as_ref(),
333                        ) {
334                            (Some(self_type_data), None) => Some(self_type_data),
335                            (None, Some(other_type_data)) => Some(TypeData {
336                                search_unbox: other_type_data.search_unbox,
337                                inverted_function_inputs_index: other_type_data
338                                    .inverted_function_inputs_index
339                                    .iter()
340                                    .cloned()
341                                    .map(|mut list: Vec<u32>| {
342                                        for fnid in &mut list {
343                                            assert!(
344                                                other.function_data
345                                                    [usize::try_from(*fnid).unwrap()]
346                                                .is_some(),
347                                            );
348                                            // this is valid because we call `self.push()` once, exactly, for every entry,
349                                            // even if we're just pushing a tombstone
350                                            *fnid += u32::try_from(other_entryid_offset).unwrap();
351                                        }
352                                        list
353                                    })
354                                    .collect(),
355                                inverted_function_output_index: other_type_data
356                                    .inverted_function_output_index
357                                    .iter()
358                                    .cloned()
359                                    .map(|mut list: Vec<u32>| {
360                                        for fnid in &mut list {
361                                            assert!(
362                                                other.function_data
363                                                    [usize::try_from(*fnid).unwrap()]
364                                                .is_some(),
365                                            );
366                                            // this is valid because we call `self.push()` once, exactly, for every entry,
367                                            // even if we're just pushing a tombstone
368                                            *fnid += u32::try_from(other_entryid_offset).unwrap();
369                                        }
370                                        list
371                                    })
372                                    .collect(),
373                            }),
374                            (Some(mut self_type_data), Some(other_type_data)) => {
375                                for (size, other_list) in other_type_data
376                                    .inverted_function_inputs_index
377                                    .iter()
378                                    .enumerate()
379                                {
380                                    while self_type_data.inverted_function_inputs_index.len()
381                                        <= size
382                                    {
383                                        self_type_data
384                                            .inverted_function_inputs_index
385                                            .push(Vec::new());
386                                    }
387                                    self_type_data.inverted_function_inputs_index[size].extend(
388                                        other_list.iter().copied().map(|fnid| {
389                                            assert!(
390                                                other.function_data[usize::try_from(fnid).unwrap()]
391                                                    .is_some(),
392                                            );
393                                            // this is valid because we call `self.push()` once, exactly, for every entry,
394                                            // even if we're just pushing a tombstone
395                                            fnid + u32::try_from(other_entryid_offset).unwrap()
396                                        }),
397                                    )
398                                }
399                                for (size, other_list) in other_type_data
400                                    .inverted_function_output_index
401                                    .iter()
402                                    .enumerate()
403                                {
404                                    while self_type_data.inverted_function_output_index.len()
405                                        <= size
406                                    {
407                                        self_type_data
408                                            .inverted_function_output_index
409                                            .push(Vec::new());
410                                    }
411                                    self_type_data.inverted_function_output_index[size].extend(
412                                        other_list.iter().copied().map(|fnid| {
413                                            assert!(
414                                                other.function_data[usize::try_from(fnid).unwrap()]
415                                                    .is_some(),
416                                            );
417                                            // this is valid because we call `self.push()` once, exactly, for every entry,
418                                            // even if we're just pushing a tombstone
419                                            fnid + u32::try_from(other_entryid_offset).unwrap()
420                                        }),
421                                    )
422                                }
423                                Some(self_type_data)
424                            }
425                            (None, None) => None,
426                        };
427                        self.type_data[self_pathid] = new_type_data;
428                        self_pathid
429                    }
430                };
431                map_other_pathid_to_self_pathid.push(self_pathid);
432            } else {
433                // if this gets used, we want it to crash
434                // this should be impossible as a valid index, since some of the
435                // memory must be used for stuff other than the list
436                map_other_pathid_to_self_pathid.push(!0);
437            }
438        }
439        for other_entryid in 0..other.names.len() {
440            if skips.contains(&other_entryid) {
441                // we push tombstone entries to keep the IDs lined up
442                self.push(String::new(), None, None, String::new(), None, None, None);
443            } else {
444                self.push(
445                    other.names[other_entryid].clone(),
446                    other.path_data[other_entryid].clone(),
447                    other.entry_data[other_entryid].as_ref().map(|other_entry_data| EntryData {
448                        parent: other_entry_data
449                            .parent
450                            .map(|parent| map_other_pathid_to_self_pathid[parent])
451                            .clone(),
452                        module_path: other_entry_data
453                            .module_path
454                            .map(|path| map_other_pathid_to_self_pathid[path])
455                            .clone(),
456                        exact_module_path: other_entry_data
457                            .exact_module_path
458                            .map(|exact_path| map_other_pathid_to_self_pathid[exact_path])
459                            .clone(),
460                        krate: map_other_pathid_to_self_pathid[other_entry_data.krate],
461                        ..other_entry_data.clone()
462                    }),
463                    other.descs[other_entryid].clone(),
464                    other.function_data[other_entryid].clone().map(|mut func| {
465                        fn map_fn_sig_item(
466                            map_other_pathid_to_self_pathid: &Vec<usize>,
467                            ty: &mut RenderType,
468                        ) {
469                            match ty.id {
470                                None => {}
471                                Some(RenderTypeId::Index(generic)) if generic < 0 => {}
472                                Some(RenderTypeId::Index(id)) => {
473                                    let id = usize::try_from(id).unwrap();
474                                    let id = map_other_pathid_to_self_pathid[id];
475                                    assert!(id != !0);
476                                    ty.id = Some(RenderTypeId::Index(isize::try_from(id).unwrap()));
477                                }
478                                _ => unreachable!(),
479                            }
480                            if let Some(generics) = &mut ty.generics {
481                                for generic in generics {
482                                    map_fn_sig_item(map_other_pathid_to_self_pathid, generic);
483                                }
484                            }
485                            if let Some(bindings) = &mut ty.bindings {
486                                for (param, constraints) in bindings {
487                                    *param = match *param {
488                                        param @ RenderTypeId::Index(generic) if generic < 0 => {
489                                            param
490                                        }
491                                        RenderTypeId::Index(id) => {
492                                            let id = usize::try_from(id).unwrap();
493                                            let id = map_other_pathid_to_self_pathid[id];
494                                            assert!(id != !0);
495                                            RenderTypeId::Index(isize::try_from(id).unwrap())
496                                        }
497                                        _ => unreachable!(),
498                                    };
499                                    for constraint in constraints {
500                                        map_fn_sig_item(
501                                            map_other_pathid_to_self_pathid,
502                                            constraint,
503                                        );
504                                    }
505                                }
506                            }
507                        }
508                        for input in &mut func.inputs {
509                            map_fn_sig_item(&map_other_pathid_to_self_pathid, input);
510                        }
511                        for output in &mut func.output {
512                            map_fn_sig_item(&map_other_pathid_to_self_pathid, output);
513                        }
514                        for clause in &mut func.where_clause {
515                            for entry in clause {
516                                map_fn_sig_item(&map_other_pathid_to_self_pathid, entry);
517                            }
518                        }
519                        func
520                    }),
521                    other.type_data[other_entryid].as_ref().map(|type_data| TypeData {
522                        inverted_function_inputs_index: type_data
523                            .inverted_function_inputs_index
524                            .iter()
525                            .cloned()
526                            .map(|mut list| {
527                                for fnid in &mut list {
528                                    assert!(
529                                        other.function_data[usize::try_from(*fnid).unwrap()]
530                                            .is_some(),
531                                    );
532                                    // this is valid because we call `self.push()` once, exactly, for every entry,
533                                    // even if we're just pushing a tombstone
534                                    *fnid += u32::try_from(other_entryid_offset).unwrap();
535                                }
536                                list
537                            })
538                            .collect(),
539                        inverted_function_output_index: type_data
540                            .inverted_function_output_index
541                            .iter()
542                            .cloned()
543                            .map(|mut list| {
544                                for fnid in &mut list {
545                                    assert!(
546                                        other.function_data[usize::try_from(*fnid).unwrap()]
547                                            .is_some(),
548                                    );
549                                    // this is valid because we call `self.push()` once, exactly, for every entry,
550                                    // even if we're just pushing a tombstone
551                                    *fnid += u32::try_from(other_entryid_offset).unwrap();
552                                }
553                                list
554                            })
555                            .collect(),
556                        search_unbox: type_data.search_unbox,
557                    }),
558                    other.alias_pointers[other_entryid]
559                        .map(|alias_pointer| alias_pointer + other_entryid_offset),
560                );
561            }
562        }
563        if other.generic_inverted_index.len() > self.generic_inverted_index.len() {
564            self.generic_inverted_index.resize(other.generic_inverted_index.len(), Vec::new());
565        }
566        for (other_generic_inverted_index, self_generic_inverted_index) in
567            iter::zip(&other.generic_inverted_index, &mut self.generic_inverted_index)
568        {
569            if other_generic_inverted_index.len() > self_generic_inverted_index.len() {
570                self_generic_inverted_index.resize(other_generic_inverted_index.len(), Vec::new());
571            }
572            for (other_list, self_list) in
573                iter::zip(other_generic_inverted_index, self_generic_inverted_index)
574            {
575                self_list.extend(
576                    other_list
577                        .iter()
578                        .copied()
579                        .map(|fnid| fnid + u32::try_from(other_entryid_offset).unwrap()),
580                );
581            }
582        }
583        self
584    }
585
586    pub(crate) fn sort(self) -> SerializedSearchIndex {
587        let mut idlist: Vec<usize> = (0..self.names.len()).collect();
588        // nameless entries are tombstones, and will be removed after sorting
589        // sort shorter names first, so that we can present them in order out of search.js
590        idlist.sort_by_key(|&id| {
591            (
592                self.names[id].is_empty(),
593                self.names[id].len(),
594                &self.names[id],
595                self.entry_data[id].as_ref().map_or("", |entry| self.names[entry.krate].as_str()),
596                self.path_data[id].as_ref().map_or(&[][..], |entry| &entry.module_path[..]),
597            )
598        });
599        let map = FxHashMap::from_iter(
600            idlist.iter().enumerate().map(|(new_id, &old_id)| (old_id, new_id)),
601        );
602        let mut new = SerializedSearchIndex::default();
603        for &id in &idlist {
604            if self.names[id].is_empty() {
605                break;
606            }
607            new.push(
608                self.names[id].clone(),
609                self.path_data[id].clone(),
610                self.entry_data[id].as_ref().map(
611                    |EntryData {
612                         krate,
613                         ty,
614                         module_path,
615                         exact_module_path,
616                         parent,
617                         trait_parent,
618                         deprecated,
619                         unstable,
620                         associated_item_disambiguator,
621                     }| EntryData {
622                        krate: *map.get(krate).unwrap(),
623                        ty: *ty,
624                        module_path: module_path.and_then(|path_id| map.get(&path_id).copied()),
625                        exact_module_path: exact_module_path
626                            .and_then(|path_id| map.get(&path_id).copied()),
627                        parent: parent.and_then(|path_id| map.get(&path_id).copied()),
628                        trait_parent: trait_parent.and_then(|path_id| map.get(&path_id).copied()),
629                        deprecated: *deprecated,
630                        unstable: *unstable,
631                        associated_item_disambiguator: associated_item_disambiguator.clone(),
632                    },
633                ),
634                self.descs[id].clone(),
635                self.function_data[id].clone().map(|mut func| {
636                    fn map_fn_sig_item(map: &FxHashMap<usize, usize>, ty: &mut RenderType) {
637                        match ty.id {
638                            None => {}
639                            Some(RenderTypeId::Index(generic)) if generic < 0 => {}
640                            Some(RenderTypeId::Index(id)) => {
641                                let id = usize::try_from(id).unwrap();
642                                let id = *map.get(&id).unwrap();
643                                assert!(id != !0);
644                                ty.id = Some(RenderTypeId::Index(isize::try_from(id).unwrap()));
645                            }
646                            _ => unreachable!(),
647                        }
648                        if let Some(generics) = &mut ty.generics {
649                            for generic in generics {
650                                map_fn_sig_item(map, generic);
651                            }
652                        }
653                        if let Some(bindings) = &mut ty.bindings {
654                            for (param, constraints) in bindings {
655                                *param = match *param {
656                                    param @ RenderTypeId::Index(generic) if generic < 0 => param,
657                                    RenderTypeId::Index(id) => {
658                                        let id = usize::try_from(id).unwrap();
659                                        let id = *map.get(&id).unwrap();
660                                        assert!(id != !0);
661                                        RenderTypeId::Index(isize::try_from(id).unwrap())
662                                    }
663                                    _ => unreachable!(),
664                                };
665                                for constraint in constraints {
666                                    map_fn_sig_item(map, constraint);
667                                }
668                            }
669                        }
670                    }
671                    for input in &mut func.inputs {
672                        map_fn_sig_item(&map, input);
673                    }
674                    for output in &mut func.output {
675                        map_fn_sig_item(&map, output);
676                    }
677                    for clause in &mut func.where_clause {
678                        for entry in clause {
679                            map_fn_sig_item(&map, entry);
680                        }
681                    }
682                    func
683                }),
684                self.type_data[id].as_ref().map(
685                    |TypeData {
686                         search_unbox,
687                         inverted_function_inputs_index,
688                         inverted_function_output_index,
689                     }| {
690                        let inverted_function_inputs_index: Vec<Vec<u32>> =
691                            inverted_function_inputs_index
692                                .iter()
693                                .cloned()
694                                .map(|mut list| {
695                                    for id in &mut list {
696                                        *id = u32::try_from(
697                                            *map.get(&usize::try_from(*id).unwrap()).unwrap(),
698                                        )
699                                        .unwrap();
700                                    }
701                                    list.sort();
702                                    list
703                                })
704                                .collect();
705                        let inverted_function_output_index: Vec<Vec<u32>> =
706                            inverted_function_output_index
707                                .iter()
708                                .cloned()
709                                .map(|mut list| {
710                                    for id in &mut list {
711                                        *id = u32::try_from(
712                                            *map.get(&usize::try_from(*id).unwrap()).unwrap(),
713                                        )
714                                        .unwrap();
715                                    }
716                                    list.sort();
717                                    list
718                                })
719                                .collect();
720                        TypeData {
721                            search_unbox: *search_unbox,
722                            inverted_function_inputs_index,
723                            inverted_function_output_index,
724                        }
725                    },
726                ),
727                self.alias_pointers[id].and_then(|alias| {
728                    if self.names[alias].is_empty() { None } else { map.get(&alias).copied() }
729                }),
730            );
731        }
732        new.generic_inverted_index = self
733            .generic_inverted_index
734            .into_iter()
735            .map(|mut postings| {
736                for list in postings.iter_mut() {
737                    let mut new_list: Vec<u32> = list
738                        .iter()
739                        .copied()
740                        .filter_map(|id| u32::try_from(*map.get(&usize::try_from(id).ok()?)?).ok())
741                        .collect();
742                    new_list.sort();
743                    *list = new_list;
744                }
745                postings
746            })
747            .collect();
748        new
749    }
750
751    pub(crate) fn write_to(self, doc_root: &Path, resource_suffix: &str) -> Result<(), Error> {
752        let SerializedSearchIndex {
753            names,
754            path_data,
755            entry_data,
756            descs,
757            function_data,
758            type_data,
759            alias_pointers,
760            generic_inverted_index,
761            crate_paths_index: _,
762        } = self;
763        let mut serialized_root = Vec::new();
764        serialized_root.extend_from_slice(br#"rr_('{"normalizedName":{"I":""#);
765        let normalized_names = names
766            .iter()
767            .map(|name| {
768                if name.contains("_") {
769                    name.replace("_", "").to_ascii_lowercase()
770                } else {
771                    name.to_ascii_lowercase()
772                }
773            })
774            .collect::<Vec<String>>();
775        let names_search_tree = stringdex_internals::tree::encode_search_tree_ukkonen(
776            normalized_names.iter().map(|name| name.as_bytes()),
777        );
778        let dir_path = doc_root.join(format!("search.index/"));
779        let _ = std::fs::remove_dir_all(&dir_path); // if already missing, no problem
780        stringdex_internals::write_tree_to_disk(
781            &names_search_tree,
782            &dir_path,
783            &mut serialized_root,
784        )
785        .map_err(|error| Error {
786            file: dir_path,
787            error: format!("failed to write name tree to disk: {error}"),
788        })?;
789        std::mem::drop(names_search_tree);
790        serialized_root.extend_from_slice(br#"","#);
791        serialized_root.extend_from_slice(&perform_write_strings(
792            doc_root,
793            "normalizedName",
794            normalized_names.into_iter(),
795        )?);
796        serialized_root.extend_from_slice(br#"},"crateNames":{"#);
797        let mut crates: Vec<&[u8]> = entry_data
798            .iter()
799            .filter_map(|entry_data| Some(names[entry_data.as_ref()?.krate].as_bytes()))
800            .collect();
801        crates.sort();
802        crates.dedup();
803        serialized_root.extend_from_slice(&perform_write_strings(
804            doc_root,
805            "crateNames",
806            crates.into_iter(),
807        )?);
808        serialized_root.extend_from_slice(br#"},"name":{"#);
809        serialized_root.extend_from_slice(&perform_write_strings(doc_root, "name", names.iter())?);
810        serialized_root.extend_from_slice(br#"},"path":{"#);
811        serialized_root.extend_from_slice(&perform_write_serde(doc_root, "path", path_data)?);
812        serialized_root.extend_from_slice(br#"},"entry":{"#);
813        serialized_root.extend_from_slice(&perform_write_serde(doc_root, "entry", entry_data)?);
814        serialized_root.extend_from_slice(br#"},"desc":{"#);
815        serialized_root.extend_from_slice(&perform_write_strings(
816            doc_root,
817            "desc",
818            descs.into_iter(),
819        )?);
820        serialized_root.extend_from_slice(br#"},"function":{"#);
821        serialized_root.extend_from_slice(&perform_write_serde(
822            doc_root,
823            "function",
824            function_data,
825        )?);
826        serialized_root.extend_from_slice(br#"},"type":{"#);
827        serialized_root.extend_from_slice(&perform_write_serde(doc_root, "type", type_data)?);
828        serialized_root.extend_from_slice(br#"},"alias":{"#);
829        serialized_root.extend_from_slice(&perform_write_serde(doc_root, "alias", alias_pointers)?);
830        serialized_root.extend_from_slice(br#"},"generic_inverted_index":{"#);
831        serialized_root.extend_from_slice(&perform_write_postings(
832            doc_root,
833            "generic_inverted_index",
834            generic_inverted_index,
835        )?);
836        serialized_root.extend_from_slice(br#"}}')"#);
837        fn perform_write_strings(
838            doc_root: &Path,
839            dirname: &str,
840            mut column: impl Iterator<Item = impl AsRef<[u8]> + Clone> + ExactSizeIterator,
841        ) -> Result<Vec<u8>, Error> {
842            let dir_path = doc_root.join(format!("search.index/{dirname}"));
843            stringdex_internals::write_data_to_disk(&mut column, &dir_path).map_err(|error| Error {
844                file: dir_path,
845                error: format!("failed to write column to disk: {error}"),
846            })
847        }
848        fn perform_write_serde(
849            doc_root: &Path,
850            dirname: &str,
851            column: Vec<Option<impl Serialize>>,
852        ) -> Result<Vec<u8>, Error> {
853            perform_write_strings(
854                doc_root,
855                dirname,
856                column.into_iter().map(|value| {
857                    if let Some(value) = value {
858                        serde_json::to_vec(&value).unwrap()
859                    } else {
860                        Vec::new()
861                    }
862                }),
863            )
864        }
865        fn perform_write_postings(
866            doc_root: &Path,
867            dirname: &str,
868            column: Vec<Vec<Vec<u32>>>,
869        ) -> Result<Vec<u8>, Error> {
870            perform_write_strings(
871                doc_root,
872                dirname,
873                column.into_iter().map(|postings| {
874                    let mut buf = Vec::new();
875                    encode::write_postings_to_string(&postings, &mut buf);
876                    buf
877                }),
878            )
879        }
880        std::fs::write(
881            doc_root.join(format!("search.index/root{resource_suffix}.js")),
882            serialized_root,
883        )
884        .map_err(|error| Error {
885            file: doc_root.join(format!("search.index/root{resource_suffix}.js")),
886            error: format!("failed to write root to disk: {error}"),
887        })?;
888        Ok(())
889    }
890}
891
892#[derive(Clone, Debug)]
893struct EntryData {
894    krate: usize,
895    ty: ItemType,
896    module_path: Option<usize>,
897    exact_module_path: Option<usize>,
898    parent: Option<usize>,
899    trait_parent: Option<usize>,
900    deprecated: bool,
901    unstable: bool,
902    associated_item_disambiguator: Option<String>,
903}
904
905impl Serialize for EntryData {
906    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
907    where
908        S: Serializer,
909    {
910        let mut seq = serializer.serialize_seq(None)?;
911        seq.serialize_element(&self.krate)?;
912        seq.serialize_element(&self.ty)?;
913        seq.serialize_element(&self.module_path.map(|id| id + 1).unwrap_or(0))?;
914        seq.serialize_element(&self.exact_module_path.map(|id| id + 1).unwrap_or(0))?;
915        seq.serialize_element(&self.parent.map(|id| id + 1).unwrap_or(0))?;
916        seq.serialize_element(&self.trait_parent.map(|id| id + 1).unwrap_or(0))?;
917        seq.serialize_element(&if self.deprecated { 1 } else { 0 })?;
918        seq.serialize_element(&if self.unstable { 1 } else { 0 })?;
919        if let Some(disambig) = &self.associated_item_disambiguator {
920            seq.serialize_element(&disambig)?;
921        }
922        seq.end()
923    }
924}
925
926impl<'de> Deserialize<'de> for EntryData {
927    fn deserialize<D>(deserializer: D) -> Result<EntryData, D::Error>
928    where
929        D: Deserializer<'de>,
930    {
931        struct EntryDataVisitor;
932        impl<'de> de::Visitor<'de> for EntryDataVisitor {
933            type Value = EntryData;
934            fn expecting(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
935                write!(formatter, "path data")
936            }
937            fn visit_seq<A: de::SeqAccess<'de>>(self, mut v: A) -> Result<EntryData, A::Error> {
938                let krate: usize =
939                    v.next_element()?.ok_or_else(|| A::Error::missing_field("krate"))?;
940                let ty: ItemType =
941                    v.next_element()?.ok_or_else(|| A::Error::missing_field("ty"))?;
942                let module_path: SerializedOptional32 =
943                    v.next_element()?.ok_or_else(|| A::Error::missing_field("module_path"))?;
944                let exact_module_path: SerializedOptional32 = v
945                    .next_element()?
946                    .ok_or_else(|| A::Error::missing_field("exact_module_path"))?;
947                let parent: SerializedOptional32 =
948                    v.next_element()?.ok_or_else(|| A::Error::missing_field("parent"))?;
949                let trait_parent: SerializedOptional32 =
950                    v.next_element()?.ok_or_else(|| A::Error::missing_field("trait_parent"))?;
951
952                let deprecated: u32 = v.next_element()?.unwrap_or(0);
953                let unstable: u32 = v.next_element()?.unwrap_or(0);
954                let associated_item_disambiguator: Option<String> = v.next_element()?;
955                Ok(EntryData {
956                    krate,
957                    ty,
958                    module_path: Option::<i32>::from(module_path).map(|path| path as usize),
959                    exact_module_path: Option::<i32>::from(exact_module_path)
960                        .map(|path| path as usize),
961                    parent: Option::<i32>::from(parent).map(|path| path as usize),
962                    trait_parent: Option::<i32>::from(trait_parent).map(|path| path as usize),
963                    deprecated: deprecated != 0,
964                    unstable: unstable != 0,
965                    associated_item_disambiguator,
966                })
967            }
968        }
969        deserializer.deserialize_any(EntryDataVisitor)
970    }
971}
972
973#[derive(Clone, Debug)]
974struct PathData {
975    ty: ItemType,
976    module_path: Vec<Symbol>,
977    exact_module_path: Option<Vec<Symbol>>,
978}
979
980impl Serialize for PathData {
981    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
982    where
983        S: Serializer,
984    {
985        let mut seq = serializer.serialize_seq(None)?;
986        seq.serialize_element(&self.ty)?;
987        seq.serialize_element(&if self.module_path.is_empty() {
988            String::new()
989        } else {
990            join_path_syms(&self.module_path)
991        })?;
992        if let Some(ref path) = self.exact_module_path {
993            seq.serialize_element(&if path.is_empty() {
994                String::new()
995            } else {
996                join_path_syms(path)
997            })?;
998        }
999        seq.end()
1000    }
1001}
1002
1003impl<'de> Deserialize<'de> for PathData {
1004    fn deserialize<D>(deserializer: D) -> Result<PathData, D::Error>
1005    where
1006        D: Deserializer<'de>,
1007    {
1008        struct PathDataVisitor;
1009        impl<'de> de::Visitor<'de> for PathDataVisitor {
1010            type Value = PathData;
1011            fn expecting(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1012                write!(formatter, "path data")
1013            }
1014            fn visit_seq<A: de::SeqAccess<'de>>(self, mut v: A) -> Result<PathData, A::Error> {
1015                let ty: ItemType =
1016                    v.next_element()?.ok_or_else(|| A::Error::missing_field("ty"))?;
1017                let module_path: String =
1018                    v.next_element()?.ok_or_else(|| A::Error::missing_field("module_path"))?;
1019                let exact_module_path: Option<String> =
1020                    v.next_element()?.and_then(SerializedOptionalString::into);
1021                Ok(PathData {
1022                    ty,
1023                    module_path: if module_path.is_empty() {
1024                        vec![]
1025                    } else {
1026                        module_path.split("::").map(Symbol::intern).collect()
1027                    },
1028                    exact_module_path: exact_module_path.map(|path| {
1029                        if path.is_empty() {
1030                            vec![]
1031                        } else {
1032                            path.split("::").map(Symbol::intern).collect()
1033                        }
1034                    }),
1035                })
1036            }
1037        }
1038        deserializer.deserialize_any(PathDataVisitor)
1039    }
1040}
1041
1042#[derive(Clone, Debug)]
1043struct TypeData {
1044    /// If set to "true", the generics can be matched without having to
1045    /// mention the type itself. The truth table, assuming `Unboxable`
1046    /// has `search_unbox = true` and `Inner` has `search_unbox = false`
1047    ///
1048    /// | **query**          | `Unboxable<Inner>` | `Inner` | `Inner<Unboxable>` |
1049    /// |--------------------|--------------------|---------|--------------------|
1050    /// | `Inner`            | yes                | yes     | yes                |
1051    /// | `Unboxable`        | yes                | no      | no                 |
1052    /// | `Unboxable<Inner>` | yes                | no      | no                 |
1053    /// | `Inner<Unboxable>` | no                 | no      | yes                |
1054    search_unbox: bool,
1055    /// List of functions that mention this type in their type signature,
1056    /// on the left side of the `->` arrow.
1057    ///
1058    /// - The outer layer is sorted by number of types that appear in the
1059    ///   type signature. The search engine iterates over these in order from
1060    ///   smallest to largest. Functions with less stuff in their type
1061    ///   signature are more likely to be what the user wants, because we never
1062    ///   show functions that are *missing* parts of the query, so removing..
1063    ///
1064    /// - The inner layer is the list of functions.
1065    inverted_function_inputs_index: Vec<Vec<u32>>,
1066    /// List of functions that mention this type in their type signature,
1067    /// on the right side of the `->` arrow.
1068    inverted_function_output_index: Vec<Vec<u32>>,
1069}
1070
1071impl Serialize for TypeData {
1072    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1073    where
1074        S: Serializer,
1075    {
1076        let mut seq = serializer.serialize_seq(None)?;
1077        let mut buf = Vec::new();
1078        encode::write_postings_to_string(&self.inverted_function_inputs_index, &mut buf);
1079        let mut serialized_result = Vec::new();
1080        stringdex_internals::encode::write_base64_to_bytes(&buf, &mut serialized_result).unwrap();
1081        seq.serialize_element(&str::from_utf8(&serialized_result).unwrap())?;
1082        buf.clear();
1083        serialized_result.clear();
1084        encode::write_postings_to_string(&self.inverted_function_output_index, &mut buf);
1085        stringdex_internals::encode::write_base64_to_bytes(&buf, &mut serialized_result).unwrap();
1086        seq.serialize_element(&str::from_utf8(&serialized_result).unwrap())?;
1087        if self.search_unbox {
1088            seq.serialize_element(&1)?;
1089        }
1090        seq.end()
1091    }
1092}
1093
1094impl<'de> Deserialize<'de> for TypeData {
1095    fn deserialize<D>(deserializer: D) -> Result<TypeData, D::Error>
1096    where
1097        D: Deserializer<'de>,
1098    {
1099        struct TypeDataVisitor;
1100        impl<'de> de::Visitor<'de> for TypeDataVisitor {
1101            type Value = TypeData;
1102            fn expecting(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1103                write!(formatter, "type data")
1104            }
1105            fn visit_none<E>(self) -> Result<TypeData, E> {
1106                Ok(TypeData {
1107                    inverted_function_inputs_index: vec![],
1108                    inverted_function_output_index: vec![],
1109                    search_unbox: false,
1110                })
1111            }
1112            fn visit_seq<A: de::SeqAccess<'de>>(self, mut v: A) -> Result<TypeData, A::Error> {
1113                let inverted_function_inputs_index: String =
1114                    v.next_element()?.unwrap_or(String::new());
1115                let inverted_function_output_index: String =
1116                    v.next_element()?.unwrap_or(String::new());
1117                let search_unbox: u32 = v.next_element()?.unwrap_or(0);
1118                let mut idx: Vec<u8> = Vec::new();
1119                stringdex_internals::decode::read_base64_from_bytes(
1120                    inverted_function_inputs_index.as_bytes(),
1121                    &mut idx,
1122                )
1123                .unwrap();
1124                let mut inverted_function_inputs_index = Vec::new();
1125                encode::read_postings_from_string(&mut inverted_function_inputs_index, &idx);
1126                idx.clear();
1127                stringdex_internals::decode::read_base64_from_bytes(
1128                    inverted_function_output_index.as_bytes(),
1129                    &mut idx,
1130                )
1131                .unwrap();
1132                let mut inverted_function_output_index = Vec::new();
1133                encode::read_postings_from_string(&mut inverted_function_output_index, &idx);
1134                Ok(TypeData {
1135                    inverted_function_inputs_index,
1136                    inverted_function_output_index,
1137                    search_unbox: search_unbox == 1,
1138                })
1139            }
1140        }
1141        deserializer.deserialize_any(TypeDataVisitor)
1142    }
1143}
1144
1145enum SerializedOptionalString {
1146    None,
1147    Some(String),
1148}
1149
1150impl From<SerializedOptionalString> for Option<String> {
1151    fn from(me: SerializedOptionalString) -> Option<String> {
1152        match me {
1153            SerializedOptionalString::Some(string) => Some(string),
1154            SerializedOptionalString::None => None,
1155        }
1156    }
1157}
1158
1159impl Serialize for SerializedOptionalString {
1160    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1161    where
1162        S: Serializer,
1163    {
1164        match self {
1165            SerializedOptionalString::Some(string) => string.serialize(serializer),
1166            SerializedOptionalString::None => 0.serialize(serializer),
1167        }
1168    }
1169}
1170impl<'de> Deserialize<'de> for SerializedOptionalString {
1171    fn deserialize<D>(deserializer: D) -> Result<SerializedOptionalString, D::Error>
1172    where
1173        D: Deserializer<'de>,
1174    {
1175        struct SerializedOptionalStringVisitor;
1176        impl<'de> de::Visitor<'de> for SerializedOptionalStringVisitor {
1177            type Value = SerializedOptionalString;
1178            fn expecting(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1179                write!(formatter, "0 or string")
1180            }
1181            fn visit_u64<E: de::Error>(self, v: u64) -> Result<SerializedOptionalString, E> {
1182                if v != 0 {
1183                    return Err(E::missing_field("not 0"));
1184                }
1185                Ok(SerializedOptionalString::None)
1186            }
1187            fn visit_string<E: de::Error>(self, v: String) -> Result<SerializedOptionalString, E> {
1188                Ok(SerializedOptionalString::Some(v))
1189            }
1190            fn visit_str<E: de::Error>(self, v: &str) -> Result<SerializedOptionalString, E> {
1191                Ok(SerializedOptionalString::Some(v.to_string()))
1192            }
1193        }
1194        deserializer.deserialize_any(SerializedOptionalStringVisitor)
1195    }
1196}
1197
1198enum SerializedOptional32 {
1199    None,
1200    Some(i32),
1201}
1202
1203impl From<SerializedOptional32> for Option<i32> {
1204    fn from(me: SerializedOptional32) -> Option<i32> {
1205        match me {
1206            SerializedOptional32::Some(number) => Some(number),
1207            SerializedOptional32::None => None,
1208        }
1209    }
1210}
1211
1212impl Serialize for SerializedOptional32 {
1213    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1214    where
1215        S: Serializer,
1216    {
1217        match self {
1218            &SerializedOptional32::Some(number) if number < 0 => number.serialize(serializer),
1219            &SerializedOptional32::Some(number) => (number + 1).serialize(serializer),
1220            &SerializedOptional32::None => 0.serialize(serializer),
1221        }
1222    }
1223}
1224impl<'de> Deserialize<'de> for SerializedOptional32 {
1225    fn deserialize<D>(deserializer: D) -> Result<SerializedOptional32, D::Error>
1226    where
1227        D: Deserializer<'de>,
1228    {
1229        struct SerializedOptional32Visitor;
1230        impl<'de> de::Visitor<'de> for SerializedOptional32Visitor {
1231            type Value = SerializedOptional32;
1232            fn expecting(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1233                write!(formatter, "integer")
1234            }
1235            fn visit_i64<E: de::Error>(self, v: i64) -> Result<SerializedOptional32, E> {
1236                Ok(match v {
1237                    0 => SerializedOptional32::None,
1238                    v if v < 0 => SerializedOptional32::Some(v as i32),
1239                    v => SerializedOptional32::Some(v as i32 - 1),
1240                })
1241            }
1242            fn visit_u64<E: de::Error>(self, v: u64) -> Result<SerializedOptional32, E> {
1243                Ok(match v {
1244                    0 => SerializedOptional32::None,
1245                    v => SerializedOptional32::Some(v as i32 - 1),
1246                })
1247            }
1248        }
1249        deserializer.deserialize_any(SerializedOptional32Visitor)
1250    }
1251}
1252
1253/// Builds the search index from the collected metadata
1254pub(crate) fn build_index(
1255    krate: &clean::Crate,
1256    cache: &mut Cache,
1257    tcx: TyCtxt<'_>,
1258    doc_root: &Path,
1259    resource_suffix: &str,
1260    should_merge: &ShouldMerge,
1261) -> Result<SerializedSearchIndex, Error> {
1262    let mut search_index = std::mem::take(&mut cache.search_index);
1263
1264    // Attach all orphan items to the type's definition if the type
1265    // has since been learned.
1266    for &OrphanImplItem { impl_id, parent, trait_parent, ref item, ref impl_generics } in
1267        &cache.orphan_impl_items
1268    {
1269        if let Some((fqp, _)) = cache.paths.get(&parent) {
1270            let desc = short_markdown_summary(&item.doc_value(), &item.link_names(cache));
1271            search_index.push(IndexItem {
1272                ty: item.type_(),
1273                defid: item.item_id.as_def_id(),
1274                name: item.name.unwrap(),
1275                module_path: fqp[..fqp.len() - 1].to_vec(),
1276                desc,
1277                parent: Some(parent),
1278                parent_idx: None,
1279                trait_parent,
1280                trait_parent_idx: None,
1281                exact_module_path: None,
1282                impl_id,
1283                search_type: get_function_type_for_search(
1284                    item,
1285                    tcx,
1286                    impl_generics.as_ref(),
1287                    Some(parent),
1288                    cache,
1289                ),
1290                aliases: item.attrs.get_doc_aliases(),
1291                is_deprecated: item.is_deprecated(tcx),
1292                is_unstable: item.is_unstable(),
1293            });
1294        }
1295    }
1296
1297    // Sort search index items. This improves the compressibility of the search index.
1298    search_index.sort_unstable_by(|k1, k2| {
1299        // `sort_unstable_by_key` produces lifetime errors
1300        // HACK(rustdoc): should not be sorting `CrateNum` or `DefIndex`, this will soon go away, too
1301        let k1 =
1302            (&k1.module_path, k1.name.as_str(), &k1.ty, k1.parent.map(|id| (id.index, id.krate)));
1303        let k2 =
1304            (&k2.module_path, k2.name.as_str(), &k2.ty, k2.parent.map(|id| (id.index, id.krate)));
1305        Ord::cmp(&k1, &k2)
1306    });
1307
1308    // Now, convert to an on-disk search index format
1309    //
1310    // if there's already a search index, load it into memory and add the new entries to it
1311    // otherwise, do nothing
1312    let mut serialized_index = if should_merge.read_rendered_cci {
1313        SerializedSearchIndex::load(doc_root, resource_suffix)?
1314    } else {
1315        SerializedSearchIndex::default()
1316    };
1317
1318    // The crate always goes first in this list
1319    let crate_name = krate.name(tcx);
1320    let crate_doc =
1321        short_markdown_summary(&krate.module.doc_value(), &krate.module.link_names(cache));
1322    let crate_idx = {
1323        let crate_path = (ItemType::ExternCrate, vec![crate_name]);
1324        match serialized_index.crate_paths_index.entry(crate_path) {
1325            Entry::Occupied(index) => {
1326                let index = *index.get();
1327                serialized_index.descs[index] = crate_doc;
1328                for type_data in serialized_index.type_data.iter_mut() {
1329                    if let Some(TypeData {
1330                        inverted_function_inputs_index,
1331                        inverted_function_output_index,
1332                        ..
1333                    }) = type_data
1334                    {
1335                        for list in inverted_function_inputs_index
1336                            .iter_mut()
1337                            .chain(inverted_function_output_index.iter_mut())
1338                        {
1339                            list.retain(|fnid| {
1340                                serialized_index.entry_data[usize::try_from(*fnid).unwrap()]
1341                                    .as_ref()
1342                                    .unwrap()
1343                                    .krate
1344                                    != index
1345                            });
1346                        }
1347                    }
1348                }
1349                for i in (index + 1)..serialized_index.entry_data.len() {
1350                    // if this crate has been built before, replace its stuff with new
1351                    if let Some(EntryData { krate, .. }) = serialized_index.entry_data[i]
1352                        && krate == index
1353                    {
1354                        serialized_index.entry_data[i] = None;
1355                        serialized_index.descs[i] = String::new();
1356                        serialized_index.function_data[i] = None;
1357                        if serialized_index.path_data[i].is_none() {
1358                            serialized_index.names[i] = String::new();
1359                        }
1360                    }
1361                    if let Some(alias_pointer) = serialized_index.alias_pointers[i]
1362                        && serialized_index.entry_data[alias_pointer].is_none()
1363                    {
1364                        serialized_index.alias_pointers[i] = None;
1365                        if serialized_index.path_data[i].is_none()
1366                            && serialized_index.entry_data[i].is_none()
1367                        {
1368                            serialized_index.names[i] = String::new();
1369                        }
1370                    }
1371                }
1372                index
1373            }
1374            Entry::Vacant(slot) => {
1375                let krate = serialized_index.names.len();
1376                slot.insert(krate);
1377                serialized_index.push(
1378                    crate_name.as_str().to_string(),
1379                    Some(PathData {
1380                        ty: ItemType::ExternCrate,
1381                        module_path: vec![],
1382                        exact_module_path: None,
1383                    }),
1384                    Some(EntryData {
1385                        krate,
1386                        ty: ItemType::ExternCrate,
1387                        module_path: None,
1388                        exact_module_path: None,
1389                        parent: None,
1390                        trait_parent: None,
1391                        deprecated: false,
1392                        unstable: false,
1393                        associated_item_disambiguator: None,
1394                    }),
1395                    crate_doc,
1396                    None,
1397                    None,
1398                    None,
1399                );
1400                krate
1401            }
1402        }
1403    };
1404
1405    // First, populate associated item parents and trait parents
1406    let crate_items: Vec<&mut IndexItem> = search_index
1407        .iter_mut()
1408        .map(|item| {
1409            let mut defid_to_rowid = |defid, check_external: bool| {
1410                cache
1411                    .paths
1412                    .get(&defid)
1413                    .or_else(|| check_external.then(|| cache.external_paths.get(&defid)).flatten())
1414                    .map(|&(ref fqp, ty)| {
1415                        let pathid = serialized_index.names.len();
1416                        match serialized_index.crate_paths_index.entry((ty, fqp.clone())) {
1417                            Entry::Occupied(entry) => *entry.get(),
1418                            Entry::Vacant(entry) => {
1419                                entry.insert(pathid);
1420                                let (name, path) = fqp.split_last().unwrap();
1421                                serialized_index.push_path(
1422                                    name.as_str().to_string(),
1423                                    PathData {
1424                                        ty,
1425                                        module_path: path.to_vec(),
1426                                        exact_module_path: if let Some(exact_path) =
1427                                            cache.exact_paths.get(&defid)
1428                                            && let Some((name2, exact_path)) =
1429                                                exact_path.split_last()
1430                                            && name == name2
1431                                        {
1432                                            Some(exact_path.to_vec())
1433                                        } else {
1434                                            None
1435                                        },
1436                                    },
1437                                );
1438                                usize::try_from(pathid).unwrap()
1439                            }
1440                        }
1441                    })
1442            };
1443            item.parent_idx = item.parent.and_then(|p| defid_to_rowid(p, false));
1444            item.trait_parent_idx = item.trait_parent.and_then(|p| defid_to_rowid(p, true));
1445
1446            if let Some(defid) = item.defid
1447                && item.parent_idx.is_none()
1448            {
1449                // If this is a re-export, retain the original path.
1450                // Associated items don't use this.
1451                // Their parent carries the exact fqp instead.
1452                let exact_fqp = cache
1453                    .exact_paths
1454                    .get(&defid)
1455                    .or_else(|| cache.external_paths.get(&defid).map(|(fqp, _)| fqp));
1456                item.exact_module_path = exact_fqp.and_then(|fqp| {
1457                    // Re-exports only count if the name is exactly the same.
1458                    // This is a size optimization, since it means we only need
1459                    // to store the name once (and the path is re-used for everything
1460                    // exported from this same module). It's also likely to Do
1461                    // What I Mean, since if a re-export changes the name, it might
1462                    // also be a change in semantic meaning.
1463                    if fqp.last() != Some(&item.name) {
1464                        return None;
1465                    }
1466                    let path = if item.ty == ItemType::Macro
1467                        && find_attr!(tcx.get_all_attrs(defid), AttributeKind::MacroExport { .. })
1468                    {
1469                        // `#[macro_export]` always exports to the crate root.
1470                        vec![tcx.crate_name(defid.krate)]
1471                    } else {
1472                        if fqp.len() < 2 {
1473                            return None;
1474                        }
1475                        fqp[..fqp.len() - 1].to_vec()
1476                    };
1477                    if path == item.module_path {
1478                        return None;
1479                    }
1480                    Some(path)
1481                });
1482            } else if let Some(parent_idx) = item.parent_idx {
1483                let i = usize::try_from(parent_idx).unwrap();
1484                item.module_path =
1485                    serialized_index.path_data[i].as_ref().unwrap().module_path.clone();
1486                item.exact_module_path =
1487                    serialized_index.path_data[i].as_ref().unwrap().exact_module_path.clone();
1488            }
1489
1490            &mut *item
1491        })
1492        .collect();
1493
1494    // Now, find anywhere that the same name is used for two different items
1495    // these need a disambiguator hash for lints
1496    let mut associated_item_duplicates = FxHashMap::<(usize, ItemType, Symbol), usize>::default();
1497    for item in crate_items.iter().map(|x| &*x) {
1498        if item.impl_id.is_some()
1499            && let Some(parent_idx) = item.parent_idx
1500        {
1501            let count =
1502                associated_item_duplicates.entry((parent_idx, item.ty, item.name)).or_insert(0);
1503            *count += 1;
1504        }
1505    }
1506
1507    // now populate the actual entries, type data, and function data
1508    for item in crate_items {
1509        assert_eq!(
1510            item.parent.is_some(),
1511            item.parent_idx.is_some(),
1512            "`{}` is missing idx",
1513            item.name
1514        );
1515
1516        let module_path = Some(serialized_index.get_id_by_module_path(&item.module_path));
1517        let exact_module_path = item
1518            .exact_module_path
1519            .as_ref()
1520            .map(|path| serialized_index.get_id_by_module_path(path));
1521
1522        let new_entry_id = serialized_index.add_entry(
1523            item.name,
1524            EntryData {
1525                ty: item.ty,
1526                parent: item.parent_idx,
1527                trait_parent: item.trait_parent_idx,
1528                module_path,
1529                exact_module_path,
1530                deprecated: item.is_deprecated,
1531                unstable: item.is_unstable,
1532                associated_item_disambiguator: if let Some(impl_id) = item.impl_id
1533                    && let Some(parent_idx) = item.parent_idx
1534                    && associated_item_duplicates
1535                        .get(&(parent_idx, item.ty, item.name))
1536                        .copied()
1537                        .unwrap_or(0)
1538                        > 1
1539                {
1540                    Some(render::get_id_for_impl(tcx, ItemId::DefId(impl_id)))
1541                } else {
1542                    None
1543                },
1544                krate: crate_idx,
1545            },
1546            item.desc.to_string(),
1547        );
1548
1549        // Aliases
1550        // -------
1551        for alias in &item.aliases[..] {
1552            serialized_index.push_alias(alias.as_str().to_string(), new_entry_id);
1553        }
1554
1555        // Function signature reverse index
1556        // --------------------------------
1557        fn insert_into_map(
1558            ty: ItemType,
1559            path: &[Symbol],
1560            exact_path: Option<&[Symbol]>,
1561            search_unbox: bool,
1562            serialized_index: &mut SerializedSearchIndex,
1563            used_in_function_signature: &mut BTreeSet<isize>,
1564        ) -> RenderTypeId {
1565            let pathid = serialized_index.names.len();
1566            let pathid = match serialized_index.crate_paths_index.entry((ty, path.to_vec())) {
1567                Entry::Occupied(entry) => {
1568                    let id = *entry.get();
1569                    if serialized_index.type_data[id].as_mut().is_none() {
1570                        serialized_index.type_data[id] = Some(TypeData {
1571                            search_unbox,
1572                            inverted_function_inputs_index: Vec::new(),
1573                            inverted_function_output_index: Vec::new(),
1574                        });
1575                    } else if search_unbox {
1576                        serialized_index.type_data[id].as_mut().unwrap().search_unbox = true;
1577                    }
1578                    id
1579                }
1580                Entry::Vacant(entry) => {
1581                    entry.insert(pathid);
1582                    let (name, path) = path.split_last().unwrap();
1583                    serialized_index.push_type(
1584                        name.to_string(),
1585                        PathData {
1586                            ty,
1587                            module_path: path.to_vec(),
1588                            exact_module_path: if let Some(exact_path) = exact_path
1589                                && let Some((name2, exact_path)) = exact_path.split_last()
1590                                && name == name2
1591                            {
1592                                Some(exact_path.to_vec())
1593                            } else {
1594                                None
1595                            },
1596                        },
1597                        TypeData {
1598                            inverted_function_inputs_index: Vec::new(),
1599                            inverted_function_output_index: Vec::new(),
1600                            search_unbox,
1601                        },
1602                    );
1603                    pathid
1604                }
1605            };
1606            used_in_function_signature.insert(isize::try_from(pathid).unwrap());
1607            RenderTypeId::Index(isize::try_from(pathid).unwrap())
1608        }
1609
1610        fn convert_render_type_id(
1611            id: RenderTypeId,
1612            cache: &mut Cache,
1613            serialized_index: &mut SerializedSearchIndex,
1614            used_in_function_signature: &mut BTreeSet<isize>,
1615            tcx: TyCtxt<'_>,
1616        ) -> Option<RenderTypeId> {
1617            use crate::clean::PrimitiveType;
1618            let Cache { ref paths, ref external_paths, ref exact_paths, .. } = *cache;
1619            let search_unbox = match id {
1620                RenderTypeId::Mut => false,
1621                RenderTypeId::DefId(defid) => {
1622                    utils::has_doc_flag(tcx, defid, |d| d.search_unbox.is_some())
1623                }
1624                RenderTypeId::Primitive(
1625                    PrimitiveType::Reference | PrimitiveType::RawPointer | PrimitiveType::Tuple,
1626                ) => true,
1627                RenderTypeId::Primitive(..) => false,
1628                RenderTypeId::AssociatedType(..) => false,
1629                // this bool is only used by `insert_into_map`, so it doesn't matter what we set here
1630                // because Index means we've already inserted into the map
1631                RenderTypeId::Index(_) => false,
1632            };
1633            match id {
1634                RenderTypeId::Mut => Some(insert_into_map(
1635                    ItemType::Keyword,
1636                    &[kw::Mut],
1637                    None,
1638                    search_unbox,
1639                    serialized_index,
1640                    used_in_function_signature,
1641                )),
1642                RenderTypeId::DefId(defid) => {
1643                    if let Some(&(ref fqp, item_type)) =
1644                        paths.get(&defid).or_else(|| external_paths.get(&defid))
1645                    {
1646                        if tcx.lang_items().fn_mut_trait() == Some(defid)
1647                            || tcx.lang_items().fn_once_trait() == Some(defid)
1648                            || tcx.lang_items().fn_trait() == Some(defid)
1649                        {
1650                            let name = *fqp.last().unwrap();
1651                            // Make absolutely sure we use this single, correct path,
1652                            // because search.js needs to match. If we don't do this,
1653                            // there are three different paths that these traits may
1654                            // appear to come from.
1655                            Some(insert_into_map(
1656                                item_type,
1657                                &[sym::core, sym::ops, name],
1658                                Some(&[sym::core, sym::ops, name]),
1659                                search_unbox,
1660                                serialized_index,
1661                                used_in_function_signature,
1662                            ))
1663                        } else {
1664                            let exact_fqp = exact_paths
1665                                .get(&defid)
1666                                .or_else(|| external_paths.get(&defid).map(|(fqp, _)| fqp))
1667                                .map(|v| &v[..])
1668                                // Re-exports only count if the name is exactly the same.
1669                                // This is a size optimization, since it means we only need
1670                                // to store the name once (and the path is re-used for everything
1671                                // exported from this same module). It's also likely to Do
1672                                // What I Mean, since if a re-export changes the name, it might
1673                                // also be a change in semantic meaning.
1674                                .filter(|this_fqp| this_fqp.last() == fqp.last());
1675                            Some(insert_into_map(
1676                                item_type,
1677                                fqp,
1678                                exact_fqp,
1679                                search_unbox,
1680                                serialized_index,
1681                                used_in_function_signature,
1682                            ))
1683                        }
1684                    } else {
1685                        None
1686                    }
1687                }
1688                RenderTypeId::Primitive(primitive) => {
1689                    let sym = primitive.as_sym();
1690                    Some(insert_into_map(
1691                        ItemType::Primitive,
1692                        &[sym],
1693                        None,
1694                        search_unbox,
1695                        serialized_index,
1696                        used_in_function_signature,
1697                    ))
1698                }
1699                RenderTypeId::Index(index) => {
1700                    used_in_function_signature.insert(index);
1701                    Some(id)
1702                }
1703                RenderTypeId::AssociatedType(sym) => Some(insert_into_map(
1704                    ItemType::AssocType,
1705                    &[sym],
1706                    None,
1707                    search_unbox,
1708                    serialized_index,
1709                    used_in_function_signature,
1710                )),
1711            }
1712        }
1713
1714        fn convert_render_type(
1715            ty: &mut RenderType,
1716            cache: &mut Cache,
1717            serialized_index: &mut SerializedSearchIndex,
1718            used_in_function_signature: &mut BTreeSet<isize>,
1719            tcx: TyCtxt<'_>,
1720        ) {
1721            if let Some(generics) = &mut ty.generics {
1722                for item in generics {
1723                    convert_render_type(
1724                        item,
1725                        cache,
1726                        serialized_index,
1727                        used_in_function_signature,
1728                        tcx,
1729                    );
1730                }
1731            }
1732            if let Some(bindings) = &mut ty.bindings {
1733                bindings.retain_mut(|(associated_type, constraints)| {
1734                    let converted_associated_type = convert_render_type_id(
1735                        *associated_type,
1736                        cache,
1737                        serialized_index,
1738                        used_in_function_signature,
1739                        tcx,
1740                    );
1741                    let Some(converted_associated_type) = converted_associated_type else {
1742                        return false;
1743                    };
1744                    *associated_type = converted_associated_type;
1745                    for constraint in constraints {
1746                        convert_render_type(
1747                            constraint,
1748                            cache,
1749                            serialized_index,
1750                            used_in_function_signature,
1751                            tcx,
1752                        );
1753                    }
1754                    true
1755                });
1756            }
1757            let Some(id) = ty.id else {
1758                assert!(ty.generics.is_some());
1759                return;
1760            };
1761            ty.id = convert_render_type_id(
1762                id,
1763                cache,
1764                serialized_index,
1765                used_in_function_signature,
1766                tcx,
1767            );
1768            use crate::clean::PrimitiveType;
1769            // These cases are added to the inverted index, but not actually included
1770            // in the signature. There's a matching set of cases in the
1771            // `unifyFunctionTypeIsMatchCandidate` function, for the slow path.
1772            match id {
1773                // typeNameIdOfArrayOrSlice
1774                RenderTypeId::Primitive(PrimitiveType::Array | PrimitiveType::Slice) => {
1775                    insert_into_map(
1776                        ItemType::Primitive,
1777                        &[Symbol::intern("[]")],
1778                        None,
1779                        false,
1780                        serialized_index,
1781                        used_in_function_signature,
1782                    );
1783                }
1784                RenderTypeId::Primitive(PrimitiveType::Tuple | PrimitiveType::Unit) => {
1785                    // typeNameIdOfArrayOrSlice
1786                    insert_into_map(
1787                        ItemType::Primitive,
1788                        &[Symbol::intern("()")],
1789                        None,
1790                        false,
1791                        serialized_index,
1792                        used_in_function_signature,
1793                    );
1794                }
1795                // typeNameIdOfHof
1796                RenderTypeId::Primitive(PrimitiveType::Fn) => {
1797                    insert_into_map(
1798                        ItemType::Primitive,
1799                        &[Symbol::intern("->")],
1800                        None,
1801                        false,
1802                        serialized_index,
1803                        used_in_function_signature,
1804                    );
1805                }
1806                RenderTypeId::DefId(did)
1807                    if tcx.lang_items().fn_mut_trait() == Some(did)
1808                        || tcx.lang_items().fn_once_trait() == Some(did)
1809                        || tcx.lang_items().fn_trait() == Some(did) =>
1810                {
1811                    insert_into_map(
1812                        ItemType::Primitive,
1813                        &[Symbol::intern("->")],
1814                        None,
1815                        false,
1816                        serialized_index,
1817                        used_in_function_signature,
1818                    );
1819                }
1820                // not special
1821                _ => {}
1822            }
1823        }
1824        if let Some(search_type) = &mut item.search_type {
1825            let mut used_in_function_inputs = BTreeSet::new();
1826            let mut used_in_function_output = BTreeSet::new();
1827            for item in &mut search_type.inputs {
1828                convert_render_type(
1829                    item,
1830                    cache,
1831                    &mut serialized_index,
1832                    &mut used_in_function_inputs,
1833                    tcx,
1834                );
1835            }
1836            for item in &mut search_type.output {
1837                convert_render_type(
1838                    item,
1839                    cache,
1840                    &mut serialized_index,
1841                    &mut used_in_function_output,
1842                    tcx,
1843                );
1844            }
1845            let used_in_constraints = search_type
1846                .where_clause
1847                .iter_mut()
1848                .map(|constraint| {
1849                    let mut used_in_constraint = BTreeSet::new();
1850                    for trait_ in constraint {
1851                        convert_render_type(
1852                            trait_,
1853                            cache,
1854                            &mut serialized_index,
1855                            &mut used_in_constraint,
1856                            tcx,
1857                        );
1858                    }
1859                    used_in_constraint
1860                })
1861                .collect::<Vec<_>>();
1862            loop {
1863                let mut inserted_any = false;
1864                for (i, used_in_constraint) in used_in_constraints.iter().enumerate() {
1865                    let id = !(i as isize);
1866                    if used_in_function_inputs.contains(&id)
1867                        && !used_in_function_inputs.is_superset(&used_in_constraint)
1868                    {
1869                        used_in_function_inputs.extend(used_in_constraint.iter().copied());
1870                        inserted_any = true;
1871                    }
1872                    if used_in_function_output.contains(&id)
1873                        && !used_in_function_output.is_superset(&used_in_constraint)
1874                    {
1875                        used_in_function_output.extend(used_in_constraint.iter().copied());
1876                        inserted_any = true;
1877                    }
1878                }
1879                if !inserted_any {
1880                    break;
1881                }
1882            }
1883            let search_type_size = search_type.size() +
1884                // Artificially give struct fields a size of 8 instead of their real
1885                // size of 2. This is because search.js sorts them to the end, so
1886                // by pushing them down, we prevent them from blocking real 2-arity functions.
1887                //
1888                // The number 8 is arbitrary. We want it big, but not enormous,
1889                // because the postings list has to fill in an empty array for each
1890                // unoccupied size.
1891                if item.ty.is_fn_like() { 0 } else { 16 };
1892            serialized_index.function_data[new_entry_id] = Some(search_type.clone());
1893
1894            #[derive(Clone, Copy)]
1895            enum InvertedIndexType {
1896                Inputs,
1897                Output,
1898            }
1899            impl InvertedIndexType {
1900                fn from_type_data(self, type_data: &mut TypeData) -> &mut Vec<Vec<u32>> {
1901                    match self {
1902                        Self::Inputs => &mut type_data.inverted_function_inputs_index,
1903                        Self::Output => &mut type_data.inverted_function_output_index,
1904                    }
1905                }
1906            }
1907
1908            let mut process_used_in_function =
1909                |used_in_function: BTreeSet<isize>, index_type: InvertedIndexType| {
1910                    for index in used_in_function {
1911                        let postings = if index >= 0 {
1912                            assert!(serialized_index.path_data[index as usize].is_some());
1913                            index_type.from_type_data(
1914                                serialized_index.type_data[index as usize].as_mut().unwrap(),
1915                            )
1916                        } else {
1917                            let generic_id = index.unsigned_abs() - 1;
1918                            if generic_id >= serialized_index.generic_inverted_index.len() {
1919                                serialized_index
1920                                    .generic_inverted_index
1921                                    .resize(generic_id + 1, Vec::new());
1922                            }
1923                            &mut serialized_index.generic_inverted_index[generic_id]
1924                        };
1925                        if search_type_size >= postings.len() {
1926                            postings.resize(search_type_size + 1, Vec::new());
1927                        }
1928                        let posting = &mut postings[search_type_size];
1929                        if posting.last() != Some(&(new_entry_id as u32)) {
1930                            posting.push(new_entry_id as u32);
1931                        }
1932                    }
1933                };
1934
1935            process_used_in_function(used_in_function_inputs, InvertedIndexType::Inputs);
1936            process_used_in_function(used_in_function_output, InvertedIndexType::Output);
1937        }
1938    }
1939
1940    Ok(serialized_index.sort())
1941}
1942
1943pub(crate) fn get_function_type_for_search(
1944    item: &clean::Item,
1945    tcx: TyCtxt<'_>,
1946    impl_generics: Option<&(clean::Type, clean::Generics)>,
1947    parent: Option<DefId>,
1948    cache: &Cache,
1949) -> Option<IndexItemFunctionType> {
1950    let mut trait_info = None;
1951    let impl_or_trait_generics = impl_generics.or_else(|| {
1952        if let Some(def_id) = parent
1953            && let Some(trait_) = cache.traits.get(&def_id)
1954            && let Some((path, _)) =
1955                cache.paths.get(&def_id).or_else(|| cache.external_paths.get(&def_id))
1956        {
1957            let path = clean::Path {
1958                res: rustc_hir::def::Res::Def(rustc_hir::def::DefKind::Trait, def_id),
1959                segments: path
1960                    .iter()
1961                    .map(|name| clean::PathSegment {
1962                        name: *name,
1963                        args: clean::GenericArgs::AngleBracketed {
1964                            args: ThinVec::new(),
1965                            constraints: ThinVec::new(),
1966                        },
1967                    })
1968                    .collect(),
1969            };
1970            trait_info = Some((clean::Type::Path { path }, trait_.generics.clone()));
1971            Some(trait_info.as_ref().unwrap())
1972        } else {
1973            None
1974        }
1975    });
1976    let (mut inputs, mut output, param_names, where_clause) = match item.kind {
1977        clean::ForeignFunctionItem(ref f, _)
1978        | clean::FunctionItem(ref f)
1979        | clean::MethodItem(ref f, _)
1980        | clean::RequiredMethodItem(ref f) => {
1981            get_fn_inputs_and_outputs(f, tcx, impl_or_trait_generics, cache)
1982        }
1983        clean::ConstantItem(ref c) => make_nullary_fn(&c.type_),
1984        clean::StaticItem(ref s) => make_nullary_fn(&s.type_),
1985        clean::StructFieldItem(ref t) if let Some(parent) = parent => {
1986            let mut rgen: FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)> =
1987                Default::default();
1988            let output = get_index_type(t, vec![], &mut rgen);
1989            let input = RenderType {
1990                id: Some(RenderTypeId::DefId(parent)),
1991                generics: None,
1992                bindings: None,
1993            };
1994            (vec![input], vec![output], vec![], vec![])
1995        }
1996        _ => return None,
1997    };
1998
1999    inputs.retain(|a| a.id.is_some() || a.generics.is_some());
2000    output.retain(|a| a.id.is_some() || a.generics.is_some());
2001
2002    Some(IndexItemFunctionType { inputs, output, where_clause, param_names })
2003}
2004
2005fn get_index_type(
2006    clean_type: &clean::Type,
2007    generics: Vec<RenderType>,
2008    rgen: &mut FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)>,
2009) -> RenderType {
2010    RenderType {
2011        id: get_index_type_id(clean_type, rgen),
2012        generics: if generics.is_empty() { None } else { Some(generics) },
2013        bindings: None,
2014    }
2015}
2016
2017fn get_index_type_id(
2018    clean_type: &clean::Type,
2019    rgen: &mut FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)>,
2020) -> Option<RenderTypeId> {
2021    use rustc_hir::def::{DefKind, Res};
2022    match *clean_type {
2023        clean::Type::Path { ref path, .. } => Some(RenderTypeId::DefId(path.def_id())),
2024        clean::DynTrait(ref bounds, _) => {
2025            bounds.first().map(|b| RenderTypeId::DefId(b.trait_.def_id()))
2026        }
2027        clean::Primitive(p) => Some(RenderTypeId::Primitive(p)),
2028        clean::BorrowedRef { .. } => Some(RenderTypeId::Primitive(clean::PrimitiveType::Reference)),
2029        clean::RawPointer { .. } => Some(RenderTypeId::Primitive(clean::PrimitiveType::RawPointer)),
2030        // The type parameters are converted to generics in `simplify_fn_type`
2031        clean::Slice(_) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Slice)),
2032        clean::Array(_, _) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Array)),
2033        clean::BareFunction(_) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Fn)),
2034        clean::Tuple(ref n) if n.is_empty() => {
2035            Some(RenderTypeId::Primitive(clean::PrimitiveType::Unit))
2036        }
2037        clean::Tuple(_) => Some(RenderTypeId::Primitive(clean::PrimitiveType::Tuple)),
2038        clean::QPath(ref data) => {
2039            if data.self_type.is_self_type()
2040                && let Some(clean::Path { res: Res::Def(DefKind::Trait, trait_), .. }) = data.trait_
2041            {
2042                let idx = -isize::try_from(rgen.len() + 1).unwrap();
2043                let (idx, _) = rgen
2044                    .entry(SimplifiedParam::AssociatedType(trait_, data.assoc.name))
2045                    .or_insert_with(|| (idx, Vec::new()));
2046                Some(RenderTypeId::Index(*idx))
2047            } else {
2048                None
2049            }
2050        }
2051        // Not supported yet
2052        clean::Type::Pat(..)
2053        | clean::Generic(_)
2054        | clean::SelfTy
2055        | clean::ImplTrait(_)
2056        | clean::Infer
2057        | clean::UnsafeBinder(_) => None,
2058    }
2059}
2060
2061#[derive(Clone, Copy, Eq, Hash, PartialEq)]
2062enum SimplifiedParam {
2063    // other kinds of type parameters are identified by their name
2064    Symbol(Symbol),
2065    // every argument-position impl trait is its own type parameter
2066    Anonymous(isize),
2067    // in a trait definition, the associated types are all bound to
2068    // their own type parameter
2069    AssociatedType(DefId, Symbol),
2070}
2071
2072/// The point of this function is to lower generics and types into the simplified form that the
2073/// frontend search engine can use.
2074///
2075/// For example, `[T, U, i32]]` where you have the bounds: `T: Display, U: Option<T>` will return
2076/// `[-1, -2, i32] where -1: Display, -2: Option<-1>`. If a type parameter has no trait bound, it
2077/// will still get a number. If a constraint is present but not used in the actual types, it will
2078/// not be added to the map.
2079///
2080/// This function also works recursively.
2081#[instrument(level = "trace", skip(tcx, rgen, cache))]
2082fn simplify_fn_type<'a, 'tcx>(
2083    self_: Option<&'a Type>,
2084    generics: &Generics,
2085    arg: &'a Type,
2086    tcx: TyCtxt<'tcx>,
2087    recurse: usize,
2088    rgen: &mut FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)>,
2089    is_return: bool,
2090    cache: &Cache,
2091) -> Option<RenderType> {
2092    if recurse >= 10 {
2093        // FIXME: remove this whole recurse thing when the recursion bug is fixed
2094        // See #59502 for the original issue.
2095        return None;
2096    }
2097
2098    // First, check if it's "Self".
2099    let (is_self, arg) = if let Some(self_) = self_
2100        && arg.is_self_type()
2101    {
2102        (true, self_)
2103    } else {
2104        (false, arg)
2105    };
2106
2107    // If this argument is a type parameter and not a trait bound or a type, we need to look
2108    // for its bounds.
2109    match *arg {
2110        Type::Generic(arg_s) => {
2111            // First we check if the bounds are in a `where` predicate...
2112            let where_bounds = generics
2113                .where_predicates
2114                .iter()
2115                .filter_map(|g| {
2116                    if let WherePredicate::BoundPredicate { ty, bounds, .. } = g
2117                        && *ty == *arg
2118                    {
2119                        Some(bounds)
2120                    } else {
2121                        None
2122                    }
2123                })
2124                .flatten();
2125            // Otherwise we check if the trait bounds are "inlined" like `T: Option<u32>`...
2126            let inline_bounds = generics
2127                .params
2128                .iter()
2129                .find(|g| g.is_type() && g.name == arg_s)
2130                .and_then(|bound| bound.get_bounds())
2131                .into_iter()
2132                .flatten();
2133
2134            let type_bounds = where_bounds
2135                .chain(inline_bounds)
2136                .filter_map(
2137                    |bound| if let Some(path) = bound.get_trait_path() { Some(path) } else { None },
2138                )
2139                .filter_map(|path| {
2140                    let ty = Type::Path { path };
2141                    simplify_fn_type(self_, generics, &ty, tcx, recurse + 1, rgen, is_return, cache)
2142                })
2143                .collect();
2144
2145            Some(if let Some((idx, _)) = rgen.get(&SimplifiedParam::Symbol(arg_s)) {
2146                RenderType { id: Some(RenderTypeId::Index(*idx)), generics: None, bindings: None }
2147            } else {
2148                let idx = -isize::try_from(rgen.len() + 1).unwrap();
2149                rgen.insert(SimplifiedParam::Symbol(arg_s), (idx, type_bounds));
2150                RenderType { id: Some(RenderTypeId::Index(idx)), generics: None, bindings: None }
2151            })
2152        }
2153        Type::ImplTrait(ref bounds) => {
2154            let type_bounds = bounds
2155                .iter()
2156                .filter_map(|bound| bound.get_trait_path())
2157                .filter_map(|path| {
2158                    let ty = Type::Path { path };
2159                    simplify_fn_type(self_, generics, &ty, tcx, recurse + 1, rgen, is_return, cache)
2160                })
2161                .collect::<Vec<_>>();
2162            Some(if is_return && !type_bounds.is_empty() {
2163                // In return position, `impl Trait` is a unique thing.
2164                RenderType { id: None, generics: Some(type_bounds), bindings: None }
2165            } else {
2166                // In parameter position, `impl Trait` is the same as an unnamed generic parameter.
2167                let idx = -isize::try_from(rgen.len() + 1).unwrap();
2168                rgen.insert(SimplifiedParam::Anonymous(idx), (idx, type_bounds));
2169                RenderType { id: Some(RenderTypeId::Index(idx)), generics: None, bindings: None }
2170            })
2171        }
2172        Type::Slice(ref ty) => {
2173            let ty_generics =
2174                simplify_fn_type(self_, generics, ty, tcx, recurse + 1, rgen, is_return, cache)
2175                    .into_iter()
2176                    .collect();
2177            Some(get_index_type(arg, ty_generics, rgen))
2178        }
2179        Type::Array(ref ty, _) => {
2180            let ty_generics =
2181                simplify_fn_type(self_, generics, ty, tcx, recurse + 1, rgen, is_return, cache)
2182                    .into_iter()
2183                    .collect();
2184            Some(get_index_type(arg, ty_generics, rgen))
2185        }
2186        Type::Tuple(ref tys) => {
2187            let ty_generics = tys
2188                .iter()
2189                .filter_map(|ty| {
2190                    simplify_fn_type(self_, generics, ty, tcx, recurse + 1, rgen, is_return, cache)
2191                })
2192                .collect();
2193            Some(get_index_type(arg, ty_generics, rgen))
2194        }
2195        Type::BareFunction(ref bf) => {
2196            let ty_generics = bf
2197                .decl
2198                .inputs
2199                .iter()
2200                .map(|arg| &arg.type_)
2201                .filter_map(|ty| {
2202                    simplify_fn_type(self_, generics, ty, tcx, recurse + 1, rgen, is_return, cache)
2203                })
2204                .collect();
2205            // The search index, for simplicity's sake, represents fn pointers and closures
2206            // the same way: as a tuple for the parameters, and an associated type for the
2207            // return type.
2208            let ty_output = simplify_fn_type(
2209                self_,
2210                generics,
2211                &bf.decl.output,
2212                tcx,
2213                recurse + 1,
2214                rgen,
2215                is_return,
2216                cache,
2217            )
2218            .into_iter()
2219            .collect();
2220            let ty_bindings = vec![(RenderTypeId::AssociatedType(sym::Output), ty_output)];
2221            Some(RenderType {
2222                id: get_index_type_id(arg, rgen),
2223                bindings: Some(ty_bindings),
2224                generics: Some(ty_generics),
2225            })
2226        }
2227        Type::BorrowedRef { lifetime: _, mutability, ref type_ }
2228        | Type::RawPointer(mutability, ref type_) => {
2229            let mut ty_generics = Vec::new();
2230            if mutability.is_mut() {
2231                ty_generics.push(RenderType {
2232                    id: Some(RenderTypeId::Mut),
2233                    generics: None,
2234                    bindings: None,
2235                });
2236            }
2237            if let Some(ty) =
2238                simplify_fn_type(self_, generics, type_, tcx, recurse + 1, rgen, is_return, cache)
2239            {
2240                ty_generics.push(ty);
2241            }
2242            Some(get_index_type(arg, ty_generics, rgen))
2243        }
2244        _ => {
2245            // This is not a type parameter. So for example if we have `T, U: Option<T>`, and we're
2246            // looking at `Option`, we enter this "else" condition, otherwise if it's `T`, we don't.
2247            //
2248            // So in here, we can add it directly and look for its own type parameters (so for `Option`,
2249            // we will look for them but not for `T`).
2250            let mut ty_generics = Vec::new();
2251            let mut ty_constraints = Vec::new();
2252            if let Some(arg_generics) = arg.generic_args() {
2253                ty_generics = arg_generics
2254                    .into_iter()
2255                    .filter_map(|param| match param {
2256                        clean::GenericArg::Type(ty) => Some(ty),
2257                        _ => None,
2258                    })
2259                    .filter_map(|ty| {
2260                        simplify_fn_type(
2261                            self_,
2262                            generics,
2263                            &ty,
2264                            tcx,
2265                            recurse + 1,
2266                            rgen,
2267                            is_return,
2268                            cache,
2269                        )
2270                    })
2271                    .collect();
2272                for constraint in arg_generics.constraints() {
2273                    simplify_fn_constraint(
2274                        self_,
2275                        generics,
2276                        &constraint,
2277                        tcx,
2278                        recurse + 1,
2279                        &mut ty_constraints,
2280                        rgen,
2281                        is_return,
2282                        cache,
2283                    );
2284                }
2285            }
2286            // Every trait associated type on self gets assigned to a type parameter index
2287            // this same one is used later for any appearances of these types
2288            //
2289            // for example, Iterator::next is:
2290            //
2291            //     trait Iterator {
2292            //         fn next(&mut self) -> Option<Self::Item>
2293            //     }
2294            //
2295            // Self is technically just Iterator, but we want to pretend it's more like this:
2296            //
2297            //     fn next<T>(self: Iterator<Item=T>) -> Option<T>
2298            if is_self
2299                && let Type::Path { path } = arg
2300                && let def_id = path.def_id()
2301                && let Some(trait_) = cache.traits.get(&def_id)
2302                && trait_.items.iter().any(|at| at.is_required_associated_type())
2303            {
2304                for assoc_ty in &trait_.items {
2305                    if let clean::ItemKind::RequiredAssocTypeItem(_generics, bounds) =
2306                        &assoc_ty.kind
2307                        && let Some(name) = assoc_ty.name
2308                    {
2309                        let idx = -isize::try_from(rgen.len() + 1).unwrap();
2310                        let (idx, stored_bounds) = rgen
2311                            .entry(SimplifiedParam::AssociatedType(def_id, name))
2312                            .or_insert_with(|| (idx, Vec::new()));
2313                        let idx = *idx;
2314                        if stored_bounds.is_empty() {
2315                            // Can't just pass stored_bounds to simplify_fn_type,
2316                            // because it also accepts rgen as a parameter.
2317                            // Instead, have it fill in this local, then copy it into the map afterward.
2318                            let type_bounds = bounds
2319                                .iter()
2320                                .filter_map(|bound| bound.get_trait_path())
2321                                .filter_map(|path| {
2322                                    let ty = Type::Path { path };
2323                                    simplify_fn_type(
2324                                        self_,
2325                                        generics,
2326                                        &ty,
2327                                        tcx,
2328                                        recurse + 1,
2329                                        rgen,
2330                                        is_return,
2331                                        cache,
2332                                    )
2333                                })
2334                                .collect();
2335                            let stored_bounds = &mut rgen
2336                                .get_mut(&SimplifiedParam::AssociatedType(def_id, name))
2337                                .unwrap()
2338                                .1;
2339                            if stored_bounds.is_empty() {
2340                                *stored_bounds = type_bounds;
2341                            }
2342                        }
2343                        ty_constraints.push((
2344                            RenderTypeId::AssociatedType(name),
2345                            vec![RenderType {
2346                                id: Some(RenderTypeId::Index(idx)),
2347                                generics: None,
2348                                bindings: None,
2349                            }],
2350                        ))
2351                    }
2352                }
2353            }
2354            let id = get_index_type_id(arg, rgen);
2355            if id.is_some() || !ty_generics.is_empty() {
2356                Some(RenderType {
2357                    id,
2358                    bindings: if ty_constraints.is_empty() { None } else { Some(ty_constraints) },
2359                    generics: if ty_generics.is_empty() { None } else { Some(ty_generics) },
2360                })
2361            } else {
2362                None
2363            }
2364        }
2365    }
2366}
2367
2368fn simplify_fn_constraint<'a>(
2369    self_: Option<&'a Type>,
2370    generics: &Generics,
2371    constraint: &'a clean::AssocItemConstraint,
2372    tcx: TyCtxt<'_>,
2373    recurse: usize,
2374    res: &mut Vec<(RenderTypeId, Vec<RenderType>)>,
2375    rgen: &mut FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)>,
2376    is_return: bool,
2377    cache: &Cache,
2378) {
2379    let mut ty_constraints = Vec::new();
2380    let ty_constrained_assoc = RenderTypeId::AssociatedType(constraint.assoc.name);
2381    for param in &constraint.assoc.args {
2382        match param {
2383            clean::GenericArg::Type(arg) => {
2384                ty_constraints.extend(simplify_fn_type(
2385                    self_,
2386                    generics,
2387                    &arg,
2388                    tcx,
2389                    recurse + 1,
2390                    rgen,
2391                    is_return,
2392                    cache,
2393                ));
2394            }
2395            clean::GenericArg::Lifetime(_)
2396            | clean::GenericArg::Const(_)
2397            | clean::GenericArg::Infer => {}
2398        }
2399    }
2400    for constraint in constraint.assoc.args.constraints() {
2401        simplify_fn_constraint(
2402            self_,
2403            generics,
2404            &constraint,
2405            tcx,
2406            recurse + 1,
2407            res,
2408            rgen,
2409            is_return,
2410            cache,
2411        );
2412    }
2413    match &constraint.kind {
2414        clean::AssocItemConstraintKind::Equality { term } => {
2415            if let clean::Term::Type(arg) = &term {
2416                ty_constraints.extend(simplify_fn_type(
2417                    self_,
2418                    generics,
2419                    arg,
2420                    tcx,
2421                    recurse + 1,
2422                    rgen,
2423                    is_return,
2424                    cache,
2425                ));
2426            }
2427        }
2428        clean::AssocItemConstraintKind::Bound { bounds } => {
2429            for bound in &bounds[..] {
2430                if let Some(path) = bound.get_trait_path() {
2431                    let ty = Type::Path { path };
2432                    ty_constraints.extend(simplify_fn_type(
2433                        self_,
2434                        generics,
2435                        &ty,
2436                        tcx,
2437                        recurse + 1,
2438                        rgen,
2439                        is_return,
2440                        cache,
2441                    ));
2442                }
2443            }
2444        }
2445    }
2446    res.push((ty_constrained_assoc, ty_constraints));
2447}
2448
2449/// Create a fake nullary function.
2450///
2451/// Used to allow type-based search on constants and statics.
2452fn make_nullary_fn(
2453    clean_type: &clean::Type,
2454) -> (Vec<RenderType>, Vec<RenderType>, Vec<Option<Symbol>>, Vec<Vec<RenderType>>) {
2455    let mut rgen: FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)> = Default::default();
2456    let output = get_index_type(clean_type, vec![], &mut rgen);
2457    (vec![], vec![output], vec![], vec![])
2458}
2459
2460/// Return the full list of types when bounds have been resolved.
2461///
2462/// i.e. `fn foo<A: Display, B: Option<A>>(x: u32, y: B)` will return
2463/// `[u32, Display, Option]`.
2464fn get_fn_inputs_and_outputs(
2465    func: &Function,
2466    tcx: TyCtxt<'_>,
2467    impl_or_trait_generics: Option<&(clean::Type, clean::Generics)>,
2468    cache: &Cache,
2469) -> (Vec<RenderType>, Vec<RenderType>, Vec<Option<Symbol>>, Vec<Vec<RenderType>>) {
2470    let decl = &func.decl;
2471
2472    let mut rgen: FxIndexMap<SimplifiedParam, (isize, Vec<RenderType>)> = Default::default();
2473
2474    let combined_generics;
2475    let (self_, generics) = if let Some((impl_self, impl_generics)) = impl_or_trait_generics {
2476        match (impl_generics.is_empty(), func.generics.is_empty()) {
2477            (true, _) => (Some(impl_self), &func.generics),
2478            (_, true) => (Some(impl_self), impl_generics),
2479            (false, false) => {
2480                let params =
2481                    func.generics.params.iter().chain(&impl_generics.params).cloned().collect();
2482                let where_predicates = func
2483                    .generics
2484                    .where_predicates
2485                    .iter()
2486                    .chain(&impl_generics.where_predicates)
2487                    .cloned()
2488                    .collect();
2489                combined_generics = clean::Generics { params, where_predicates };
2490                (Some(impl_self), &combined_generics)
2491            }
2492        }
2493    } else {
2494        (None, &func.generics)
2495    };
2496
2497    let param_types = decl
2498        .inputs
2499        .iter()
2500        .filter_map(|param| {
2501            simplify_fn_type(self_, generics, &param.type_, tcx, 0, &mut rgen, false, cache)
2502        })
2503        .collect();
2504
2505    let ret_types = simplify_fn_type(self_, generics, &decl.output, tcx, 0, &mut rgen, true, cache)
2506        .into_iter()
2507        .collect();
2508
2509    let mut simplified_params = rgen.into_iter().collect::<Vec<_>>();
2510    simplified_params.sort_by_key(|(_, (idx, _))| -idx);
2511    (
2512        param_types,
2513        ret_types,
2514        simplified_params
2515            .iter()
2516            .map(|(name, (_idx, _traits))| match name {
2517                SimplifiedParam::Symbol(name) => Some(*name),
2518                SimplifiedParam::Anonymous(_) => None,
2519                SimplifiedParam::AssociatedType(def_id, name) => {
2520                    Some(Symbol::intern(&format!("{}::{}", tcx.item_name(*def_id), name)))
2521                }
2522            })
2523            .collect(),
2524        simplified_params.into_iter().map(|(_name, (_idx, traits))| traits).collect(),
2525    )
2526}
rustdoc/html/render/search_index.rs

rustdoc/html/render/
search_index.rs
