Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

4 files changed, 952 insertions, 0 deletions

diff --git a/src/librustdoc/formats/cache.rs b/src/librustdoc/formats/cache.rs
new file mode 100644
index 000000000..2b2691e53
--- /dev/null
+++ b/src/librustdoc/formats/cache.rs
@@ -0,0 +1,569 @@
+use std::mem;
+
+use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_hir::def_id::{CrateNum, DefId};
+use rustc_middle::middle::privacy::AccessLevels;
+use rustc_middle::ty::{self, TyCtxt};
+use rustc_span::{sym, Symbol};
+
+use crate::clean::{self, types::ExternalLocation, ExternalCrate, ItemId, PrimitiveType};
+use crate::core::DocContext;
+use crate::fold::DocFolder;
+use crate::formats::item_type::ItemType;
+use crate::formats::Impl;
+use crate::html::format::join_with_double_colon;
+use crate::html::markdown::short_markdown_summary;
+use crate::html::render::search_index::get_function_type_for_search;
+use crate::html::render::IndexItem;
+
+/// This cache is used to store information about the [`clean::Crate`] being
+/// rendered in order to provide more useful documentation. This contains
+/// information like all implementors of a trait, all traits a type implements,
+/// documentation for all known traits, etc.
+///
+/// This structure purposefully does not implement `Clone` because it's intended
+/// to be a fairly large and expensive structure to clone. Instead this adheres
+/// to `Send` so it may be stored in an `Arc` instance and shared among the various
+/// rendering threads.
+#[derive(Default)]
+pub(crate) struct Cache {
+    /// Maps a type ID to all known implementations for that type. This is only
+    /// recognized for intra-crate [`clean::Type::Path`]s, and is used to print
+    /// out extra documentation on the page of an enum/struct.
+    ///
+    /// The values of the map are a list of implementations and documentation
+    /// found on that implementation.
+    pub(crate) impls: FxHashMap<DefId, Vec<Impl>>,
+
+    /// Maintains a mapping of local crate `DefId`s to the fully qualified name
+    /// and "short type description" of that node. This is used when generating
+    /// URLs when a type is being linked to. External paths are not located in
+    /// this map because the `External` type itself has all the information
+    /// necessary.
+    pub(crate) paths: FxHashMap<DefId, (Vec<Symbol>, ItemType)>,
+
+    /// Similar to `paths`, but only holds external paths. This is only used for
+    /// generating explicit hyperlinks to other crates.
+    pub(crate) external_paths: FxHashMap<DefId, (Vec<Symbol>, ItemType)>,
+
+    /// Maps local `DefId`s of exported types to fully qualified paths.
+    /// Unlike 'paths', this mapping ignores any renames that occur
+    /// due to 'use' statements.
+    ///
+    /// This map is used when writing out the special 'implementors'
+    /// javascript file. By using the exact path that the type
+    /// is declared with, we ensure that each path will be identical
+    /// to the path used if the corresponding type is inlined. By
+    /// doing this, we can detect duplicate impls on a trait page, and only display
+    /// the impl for the inlined type.
+    pub(crate) exact_paths: FxHashMap<DefId, Vec<Symbol>>,
+
+    /// This map contains information about all known traits of this crate.
+    /// Implementations of a crate should inherit the documentation of the
+    /// parent trait if no extra documentation is specified, and default methods
+    /// should show up in documentation about trait implementations.
+    pub(crate) traits: FxHashMap<DefId, clean::TraitWithExtraInfo>,
+
+    /// When rendering traits, it's often useful to be able to list all
+    /// implementors of the trait, and this mapping is exactly, that: a mapping
+    /// of trait ids to the list of known implementors of the trait
+    pub(crate) implementors: FxHashMap<DefId, Vec<Impl>>,
+
+    /// Cache of where external crate documentation can be found.
+    pub(crate) extern_locations: FxHashMap<CrateNum, ExternalLocation>,
+
+    /// Cache of where documentation for primitives can be found.
+    pub(crate) primitive_locations: FxHashMap<clean::PrimitiveType, DefId>,
+
+    // Note that external items for which `doc(hidden)` applies to are shown as
+    // non-reachable while local items aren't. This is because we're reusing
+    // the access levels from the privacy check pass.
+    pub(crate) access_levels: AccessLevels<DefId>,
+
+    /// The version of the crate being documented, if given from the `--crate-version` flag.
+    pub(crate) crate_version: Option<String>,
+
+    /// Whether to document private items.
+    /// This is stored in `Cache` so it doesn't need to be passed through all rustdoc functions.
+    pub(crate) document_private: bool,
+
+    /// Crates marked with [`#[doc(masked)]`][doc_masked].
+    ///
+    /// [doc_masked]: https://doc.rust-lang.org/nightly/unstable-book/language-features/doc-masked.html
+    pub(crate) masked_crates: FxHashSet<CrateNum>,
+
+    // Private fields only used when initially crawling a crate to build a cache
+    stack: Vec<Symbol>,
+    parent_stack: Vec<ParentStackItem>,
+    stripped_mod: bool,
+
+    pub(crate) search_index: Vec<IndexItem>,
+
+    // In rare case where a structure is defined in one module but implemented
+    // in another, if the implementing module is parsed before defining module,
+    // then the fully qualified name of the structure isn't presented in `paths`
+    // yet when its implementation methods are being indexed. Caches such methods
+    // and their parent id here and indexes them at the end of crate parsing.
+    pub(crate) orphan_impl_items: Vec<OrphanImplItem>,
+
+    // Similarly to `orphan_impl_items`, sometimes trait impls are picked up
+    // even though the trait itself is not exported. This can happen if a trait
+    // was defined in function/expression scope, since the impl will be picked
+    // up by `collect-trait-impls` but the trait won't be scraped out in the HIR
+    // crawl. In order to prevent crashes when looking for notable traits or
+    // when gathering trait documentation on a type, hold impls here while
+    // folding and add them to the cache later on if we find the trait.
+    orphan_trait_impls: Vec<(DefId, FxHashSet<DefId>, Impl)>,
+
+    /// All intra-doc links resolved so far.
+    ///
+    /// Links are indexed by the DefId of the item they document.
+    pub(crate) intra_doc_links: FxHashMap<ItemId, Vec<clean::ItemLink>>,
+    /// Cfg that have been hidden via #![doc(cfg_hide(...))]
+    pub(crate) hidden_cfg: FxHashSet<clean::cfg::Cfg>,
+}
+
+/// This struct is used to wrap the `cache` and `tcx` in order to run `DocFolder`.
+struct CacheBuilder<'a, 'tcx> {
+    cache: &'a mut Cache,
+    /// This field is used to prevent duplicated impl blocks.
+    impl_ids: FxHashMap<DefId, FxHashSet<DefId>>,
+    tcx: TyCtxt<'tcx>,
+}
+
+impl Cache {
+    pub(crate) fn new(access_levels: AccessLevels<DefId>, document_private: bool) -> Self {
+        Cache { access_levels, document_private, ..Cache::default() }
+    }
+
+    /// Populates the `Cache` with more data. The returned `Crate` will be missing some data that was
+    /// in `krate` due to the data being moved into the `Cache`.
+    pub(crate) fn populate(cx: &mut DocContext<'_>, mut krate: clean::Crate) -> clean::Crate {
+        let tcx = cx.tcx;
+
+        // Crawl the crate to build various caches used for the output
+        debug!(?cx.cache.crate_version);
+        cx.cache.traits = krate.external_traits.take();
+
+        // Cache where all our extern crates are located
+        // FIXME: this part is specific to HTML so it'd be nice to remove it from the common code
+        for &crate_num in cx.tcx.crates(()) {
+            let e = ExternalCrate { crate_num };
+
+            let name = e.name(tcx);
+            let render_options = &cx.render_options;
+            let extern_url = render_options.extern_html_root_urls.get(name.as_str()).map(|u| &**u);
+            let extern_url_takes_precedence = render_options.extern_html_root_takes_precedence;
+            let dst = &render_options.output;
+            let location = e.location(extern_url, extern_url_takes_precedence, dst, tcx);
+            cx.cache.extern_locations.insert(e.crate_num, location);
+            cx.cache.external_paths.insert(e.def_id(), (vec![name], ItemType::Module));
+        }
+
+        // FIXME: avoid this clone (requires implementing Default manually)
+        cx.cache.primitive_locations = PrimitiveType::primitive_locations(tcx).clone();
+        for (prim, &def_id) in &cx.cache.primitive_locations {
+            let crate_name = tcx.crate_name(def_id.krate);
+            // Recall that we only allow primitive modules to be at the root-level of the crate.
+            // If that restriction is ever lifted, this will have to include the relative paths instead.
+            cx.cache
+                .external_paths
+                .insert(def_id, (vec![crate_name, prim.as_sym()], ItemType::Primitive));
+        }
+
+        let (krate, mut impl_ids) = {
+            let mut cache_builder =
+                CacheBuilder { tcx, cache: &mut cx.cache, impl_ids: FxHashMap::default() };
+            krate = cache_builder.fold_crate(krate);
+            (krate, cache_builder.impl_ids)
+        };
+
+        for (trait_did, dids, impl_) in cx.cache.orphan_trait_impls.drain(..) {
+            if cx.cache.traits.contains_key(&trait_did) {
+                for did in dids {
+                    if impl_ids.entry(did).or_default().insert(impl_.def_id()) {
+                        cx.cache.impls.entry(did).or_default().push(impl_.clone());
+                    }
+                }
+            }
+        }
+
+        krate
+    }
+}
+
+impl<'a, 'tcx> DocFolder for CacheBuilder<'a, 'tcx> {
+    fn fold_item(&mut self, item: clean::Item) -> Option<clean::Item> {
+        if item.item_id.is_local() {
+            debug!("folding {} \"{:?}\", id {:?}", item.type_(), item.name, item.item_id);
+        }
+
+        // If this is a stripped module,
+        // we don't want it or its children in the search index.
+        let orig_stripped_mod = match *item.kind {
+            clean::StrippedItem(box clean::ModuleItem(..)) => {
+                mem::replace(&mut self.cache.stripped_mod, true)
+            }
+            _ => self.cache.stripped_mod,
+        };
+
+        // If the impl is from a masked crate or references something from a
+        // masked crate then remove it completely.
+        if let clean::ImplItem(ref i) = *item.kind {
+            if self.cache.masked_crates.contains(&item.item_id.krate())
+                || i.trait_
+                    .as_ref()
+                    .map_or(false, |t| self.cache.masked_crates.contains(&t.def_id().krate))
+                || i.for_
+                    .def_id(self.cache)
+                    .map_or(false, |d| self.cache.masked_crates.contains(&d.krate))
+            {
+                return None;
+            }
+        }
+
+        // Propagate a trait method's documentation to all implementors of the
+        // trait.
+        if let clean::TraitItem(ref t) = *item.kind {
+            self.cache.traits.entry(item.item_id.expect_def_id()).or_insert_with(|| {
+                clean::TraitWithExtraInfo {
+                    trait_: t.clone(),
+                    is_notable: item.attrs.has_doc_flag(sym::notable_trait),
+                }
+            });
+        }
+
+        // Collect all the implementors of traits.
+        if let clean::ImplItem(ref i) = *item.kind {
+            if let Some(trait_) = &i.trait_ {
+                if !i.kind.is_blanket() {
+                    self.cache
+                        .implementors
+                        .entry(trait_.def_id())
+                        .or_default()
+                        .push(Impl { impl_item: item.clone() });
+                }
+            }
+        }
+
+        // Index this method for searching later on.
+        if let Some(ref s) = item.name.or_else(|| {
+            if item.is_stripped() {
+                None
+            } else if let clean::ImportItem(ref i) = *item.kind &&
+                let clean::ImportKind::Simple(s) = i.kind {
+                Some(s)
+            } else {
+                None
+            }
+        }) {
+            let (parent, is_inherent_impl_item) = match *item.kind {
+                clean::StrippedItem(..) => ((None, None), false),
+                clean::AssocConstItem(..) | clean::AssocTypeItem(..)
+                    if self
+                        .cache
+                        .parent_stack
+                        .last()
+                        .map_or(false, |parent| parent.is_trait_impl()) =>
+                {
+                    // skip associated items in trait impls
+                    ((None, None), false)
+                }
+                clean::TyMethodItem(..)
+                | clean::TyAssocConstItem(..)
+                | clean::TyAssocTypeItem(..)
+                | clean::StructFieldItem(..)
+                | clean::VariantItem(..) => (
+                    (
+                        Some(
+                            self.cache
+                                .parent_stack
+                                .last()
+                                .expect("parent_stack is empty")
+                                .item_id()
+                                .expect_def_id(),
+                        ),
+                        Some(&self.cache.stack[..self.cache.stack.len() - 1]),
+                    ),
+                    false,
+                ),
+                clean::MethodItem(..) | clean::AssocConstItem(..) | clean::AssocTypeItem(..) => {
+                    if self.cache.parent_stack.is_empty() {
+                        ((None, None), false)
+                    } else {
+                        let last = self.cache.parent_stack.last().expect("parent_stack is empty 2");
+                        let did = match &*last {
+                            ParentStackItem::Impl { for_, .. } => for_.def_id(&self.cache),
+                            ParentStackItem::Type(item_id) => item_id.as_def_id(),
+                        };
+                        let path = match did.and_then(|did| self.cache.paths.get(&did)) {
+                            // The current stack not necessarily has correlation
+                            // for where the type was defined. On the other
+                            // hand, `paths` always has the right
+                            // information if present.
+                            Some(&(ref fqp, _)) => Some(&fqp[..fqp.len() - 1]),
+                            None => None,
+                        };
+                        ((did, path), true)
+                    }
+                }
+                _ => ((None, Some(&*self.cache.stack)), false),
+            };
+
+            match parent {
+                (parent, Some(path)) if is_inherent_impl_item || !self.cache.stripped_mod => {
+                    debug_assert!(!item.is_stripped());
+
+                    // A crate has a module at its root, containing all items,
+                    // which should not be indexed. The crate-item itself is
+                    // inserted later on when serializing the search-index.
+                    if item.item_id.as_def_id().map_or(false, |idx| !idx.is_crate_root()) {
+                        let desc = item.doc_value().map_or_else(String::new, |x| {
+                            short_markdown_summary(x.as_str(), &item.link_names(self.cache))
+                        });
+                        self.cache.search_index.push(IndexItem {
+                            ty: item.type_(),
+                            name: s.to_string(),
+                            path: join_with_double_colon(path),
+                            desc,
+                            parent,
+                            parent_idx: None,
+                            search_type: get_function_type_for_search(
+                                &item,
+                                self.tcx,
+                                clean_impl_generics(self.cache.parent_stack.last()).as_ref(),
+                                self.cache,
+                            ),
+                            aliases: item.attrs.get_doc_aliases(),
+                        });
+                    }
+                }
+                (Some(parent), None) if is_inherent_impl_item => {
+                    // We have a parent, but we don't know where they're
+                    // defined yet. Wait for later to index this item.
+                    let impl_generics = clean_impl_generics(self.cache.parent_stack.last());
+                    self.cache.orphan_impl_items.push(OrphanImplItem {
+                        parent,
+                        item: item.clone(),
+                        impl_generics,
+                    });
+                }
+                _ => {}
+            }
+        }
+
+        // Keep track of the fully qualified path for this item.
+        let pushed = match item.name {
+            Some(n) if !n.is_empty() => {
+                self.cache.stack.push(n);
+                true
+            }
+            _ => false,
+        };
+
+        match *item.kind {
+            clean::StructItem(..)
+            | clean::EnumItem(..)
+            | clean::TypedefItem(..)
+            | clean::TraitItem(..)
+            | clean::TraitAliasItem(..)
+            | clean::FunctionItem(..)
+            | clean::ModuleItem(..)
+            | clean::ForeignFunctionItem(..)
+            | clean::ForeignStaticItem(..)
+            | clean::ConstantItem(..)
+            | clean::StaticItem(..)
+            | clean::UnionItem(..)
+            | clean::ForeignTypeItem
+            | clean::MacroItem(..)
+            | clean::ProcMacroItem(..)
+            | clean::VariantItem(..) => {
+                if !self.cache.stripped_mod {
+                    // Re-exported items mean that the same id can show up twice
+                    // in the rustdoc ast that we're looking at. We know,
+                    // however, that a re-exported item doesn't show up in the
+                    // `public_items` map, so we can skip inserting into the
+                    // paths map if there was already an entry present and we're
+                    // not a public item.
+                    if !self.cache.paths.contains_key(&item.item_id.expect_def_id())
+                        || self.cache.access_levels.is_public(item.item_id.expect_def_id())
+                    {
+                        self.cache.paths.insert(
+                            item.item_id.expect_def_id(),
+                            (self.cache.stack.clone(), item.type_()),
+                        );
+                    }
+                }
+            }
+            clean::PrimitiveItem(..) => {
+                self.cache
+                    .paths
+                    .insert(item.item_id.expect_def_id(), (self.cache.stack.clone(), item.type_()));
+            }
+
+            clean::ExternCrateItem { .. }
+            | clean::ImportItem(..)
+            | clean::OpaqueTyItem(..)
+            | clean::ImplItem(..)
+            | clean::TyMethodItem(..)
+            | clean::MethodItem(..)
+            | clean::StructFieldItem(..)
+            | clean::TyAssocConstItem(..)
+            | clean::AssocConstItem(..)
+            | clean::TyAssocTypeItem(..)
+            | clean::AssocTypeItem(..)
+            | clean::StrippedItem(..)
+            | clean::KeywordItem => {
+                // FIXME: Do these need handling?
+                // The person writing this comment doesn't know.
+                // So would rather leave them to an expert,
+                // as at least the list is better than `_ => {}`.
+            }
+        }
+
+        // Maintain the parent stack.
+        let (item, parent_pushed) = match *item.kind {
+            clean::TraitItem(..)
+            | clean::EnumItem(..)
+            | clean::ForeignTypeItem
+            | clean::StructItem(..)
+            | clean::UnionItem(..)
+            | clean::VariantItem(..)
+            | clean::ImplItem(..) => {
+                self.cache.parent_stack.push(ParentStackItem::new(&item));
+                (self.fold_item_recur(item), true)
+            }
+            _ => (self.fold_item_recur(item), false),
+        };
+
+        // Once we've recursively found all the generics, hoard off all the
+        // implementations elsewhere.
+        let ret = if let clean::Item { kind: box clean::ImplItem(ref i), .. } = item {
+            // Figure out the id of this impl. This may map to a
+            // primitive rather than always to a struct/enum.
+            // Note: matching twice to restrict the lifetime of the `i` borrow.
+            let mut dids = FxHashSet::default();
+            match i.for_ {
+                clean::Type::Path { ref path }
+                | clean::BorrowedRef { type_: box clean::Type::Path { ref path }, .. } => {
+                    dids.insert(path.def_id());
+                    if let Some(generics) = path.generics() &&
+                        let ty::Adt(adt, _) = self.tcx.type_of(path.def_id()).kind() &&
+                        adt.is_fundamental() {
+                        for ty in generics {
+                            if let Some(did) = ty.def_id(self.cache) {
+                                dids.insert(did);
+                            }
+                        }
+                    }
+                }
+                clean::DynTrait(ref bounds, _)
+                | clean::BorrowedRef { type_: box clean::DynTrait(ref bounds, _), .. } => {
+                    dids.insert(bounds[0].trait_.def_id());
+                }
+                ref t => {
+                    let did = t
+                        .primitive_type()
+                        .and_then(|t| self.cache.primitive_locations.get(&t).cloned());
+
+                    if let Some(did) = did {
+                        dids.insert(did);
+                    }
+                }
+            }
+
+            if let Some(generics) = i.trait_.as_ref().and_then(|t| t.generics()) {
+                for bound in generics {
+                    if let Some(did) = bound.def_id(self.cache) {
+                        dids.insert(did);
+                    }
+                }
+            }
+            let impl_item = Impl { impl_item: item };
+            if impl_item.trait_did().map_or(true, |d| self.cache.traits.contains_key(&d)) {
+                for did in dids {
+                    if self.impl_ids.entry(did).or_default().insert(impl_item.def_id()) {
+                        self.cache
+                            .impls
+                            .entry(did)
+                            .or_insert_with(Vec::new)
+                            .push(impl_item.clone());
+                    }
+                }
+            } else {
+                let trait_did = impl_item.trait_did().expect("no trait did");
+                self.cache.orphan_trait_impls.push((trait_did, dids, impl_item));
+            }
+            None
+        } else {
+            Some(item)
+        };
+
+        if pushed {
+            self.cache.stack.pop().expect("stack already empty");
+        }
+        if parent_pushed {
+            self.cache.parent_stack.pop().expect("parent stack already empty");
+        }
+        self.cache.stripped_mod = orig_stripped_mod;
+        ret
+    }
+}
+
+pub(crate) struct OrphanImplItem {
+    pub(crate) parent: DefId,
+    pub(crate) item: clean::Item,
+    pub(crate) impl_generics: Option<(clean::Type, clean::Generics)>,
+}
+
+/// Information about trait and type parents is tracked while traversing the item tree to build
+/// the cache.
+///
+/// We don't just store `Item` in there, because `Item` contains the list of children being
+/// traversed and it would be wasteful to clone all that. We also need the item id, so just
+/// storing `ItemKind` won't work, either.
+enum ParentStackItem {
+    Impl {
+        for_: clean::Type,
+        trait_: Option<clean::Path>,
+        generics: clean::Generics,
+        kind: clean::ImplKind,
+        item_id: ItemId,
+    },
+    Type(ItemId),
+}
+
+impl ParentStackItem {
+    fn new(item: &clean::Item) -> Self {
+        match &*item.kind {
+            clean::ItemKind::ImplItem(box clean::Impl { for_, trait_, generics, kind, .. }) => {
+                ParentStackItem::Impl {
+                    for_: for_.clone(),
+                    trait_: trait_.clone(),
+                    generics: generics.clone(),
+                    kind: kind.clone(),
+                    item_id: item.item_id,
+                }
+            }
+            _ => ParentStackItem::Type(item.item_id),
+        }
+    }
+    fn is_trait_impl(&self) -> bool {
+        matches!(self, ParentStackItem::Impl { trait_: Some(..), .. })
+    }
+    fn item_id(&self) -> ItemId {
+        match self {
+            ParentStackItem::Impl { item_id, .. } => *item_id,
+            ParentStackItem::Type(item_id) => *item_id,
+        }
+    }
+}
+
+fn clean_impl_generics(item: Option<&ParentStackItem>) -> Option<(clean::Type, clean::Generics)> {
+    if let Some(ParentStackItem::Impl { for_, generics, kind: clean::ImplKind::Normal, .. }) = item
+    {
+        Some((for_.clone(), generics.clone()))
+    } else {
+        None
+    }
+}
diff --git a/src/librustdoc/formats/item_type.rs b/src/librustdoc/formats/item_type.rs
new file mode 100644
index 000000000..0a7ee2005
--- /dev/null
+++ b/src/librustdoc/formats/item_type.rs
@@ -0,0 +1,185 @@
+//! Item types.
+
+use std::fmt;
+
+use serde::{Serialize, Serializer};
+
+use rustc_hir::def::DefKind;
+use rustc_span::hygiene::MacroKind;
+
+use crate::clean;
+
+/// Item type. Corresponds to `clean::ItemEnum` variants.
+///
+/// The search index uses item types encoded as smaller numbers which equal to
+/// discriminants. JavaScript then is used to decode them into the original value.
+/// Consequently, every change to this type should be synchronized to
+/// the `itemTypes` mapping table in `html/static/js/search.js`.
+///
+/// In addition, code in `html::render` uses this enum to generate CSS classes, page prefixes, and
+/// module headings. If you are adding to this enum and want to ensure that the sidebar also prints
+/// a heading, edit the listing in `html/render.rs`, function `sidebar_module`. This uses an
+/// ordering based on a helper function inside `item_module`, in the same file.
+#[derive(Copy, PartialEq, Eq, Hash, Clone, Debug, PartialOrd, Ord)]
+pub(crate) enum ItemType {
+    Module = 0,
+    ExternCrate = 1,
+    Import = 2,
+    Struct = 3,
+    Enum = 4,
+    Function = 5,
+    Typedef = 6,
+    Static = 7,
+    Trait = 8,
+    Impl = 9,
+    TyMethod = 10,
+    Method = 11,
+    StructField = 12,
+    Variant = 13,
+    Macro = 14,
+    Primitive = 15,
+    AssocType = 16,
+    Constant = 17,
+    AssocConst = 18,
+    Union = 19,
+    ForeignType = 20,
+    Keyword = 21,
+    OpaqueTy = 22,
+    ProcAttribute = 23,
+    ProcDerive = 24,
+    TraitAlias = 25,
+}
+
+impl Serialize for ItemType {
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        (*self as u8).serialize(serializer)
+    }
+}
+
+impl<'a> From<&'a clean::Item> for ItemType {
+    fn from(item: &'a clean::Item) -> ItemType {
+        let kind = match *item.kind {
+            clean::StrippedItem(box ref item) => item,
+            ref kind => kind,
+        };
+
+        match *kind {
+            clean::ModuleItem(..) => ItemType::Module,
+            clean::ExternCrateItem { .. } => ItemType::ExternCrate,
+            clean::ImportItem(..) => ItemType::Import,
+            clean::StructItem(..) => ItemType::Struct,
+            clean::UnionItem(..) => ItemType::Union,
+            clean::EnumItem(..) => ItemType::Enum,
+            clean::FunctionItem(..) => ItemType::Function,
+            clean::TypedefItem(..) => ItemType::Typedef,
+            clean::OpaqueTyItem(..) => ItemType::OpaqueTy,
+            clean::StaticItem(..) => ItemType::Static,
+            clean::ConstantItem(..) => ItemType::Constant,
+            clean::TraitItem(..) => ItemType::Trait,
+            clean::ImplItem(..) => ItemType::Impl,
+            clean::TyMethodItem(..) => ItemType::TyMethod,
+            clean::MethodItem(..) => ItemType::Method,
+            clean::StructFieldItem(..) => ItemType::StructField,
+            clean::VariantItem(..) => ItemType::Variant,
+            clean::ForeignFunctionItem(..) => ItemType::Function, // no ForeignFunction
+            clean::ForeignStaticItem(..) => ItemType::Static,     // no ForeignStatic
+            clean::MacroItem(..) => ItemType::Macro,
+            clean::PrimitiveItem(..) => ItemType::Primitive,
+            clean::TyAssocConstItem(..) | clean::AssocConstItem(..) => ItemType::AssocConst,
+            clean::TyAssocTypeItem(..) | clean::AssocTypeItem(..) => ItemType::AssocType,
+            clean::ForeignTypeItem => ItemType::ForeignType,
+            clean::KeywordItem => ItemType::Keyword,
+            clean::TraitAliasItem(..) => ItemType::TraitAlias,
+            clean::ProcMacroItem(ref mac) => match mac.kind {
+                MacroKind::Bang => ItemType::Macro,
+                MacroKind::Attr => ItemType::ProcAttribute,
+                MacroKind::Derive => ItemType::ProcDerive,
+            },
+            clean::StrippedItem(..) => unreachable!(),
+        }
+    }
+}
+
+impl From<DefKind> for ItemType {
+    fn from(other: DefKind) -> Self {
+        match other {
+            DefKind::Enum => Self::Enum,
+            DefKind::Fn => Self::Function,
+            DefKind::Mod => Self::Module,
+            DefKind::Const => Self::Constant,
+            DefKind::Static(_) => Self::Static,
+            DefKind::Struct => Self::Struct,
+            DefKind::Union => Self::Union,
+            DefKind::Trait => Self::Trait,
+            DefKind::TyAlias => Self::Typedef,
+            DefKind::TraitAlias => Self::TraitAlias,
+            DefKind::Macro(kind) => match kind {
+                MacroKind::Bang => ItemType::Macro,
+                MacroKind::Attr => ItemType::ProcAttribute,
+                MacroKind::Derive => ItemType::ProcDerive,
+            },
+            DefKind::ForeignTy
+            | DefKind::Variant
+            | DefKind::AssocTy
+            | DefKind::TyParam
+            | DefKind::ConstParam
+            | DefKind::Ctor(..)
+            | DefKind::AssocFn
+            | DefKind::AssocConst
+            | DefKind::ExternCrate
+            | DefKind::Use
+            | DefKind::ForeignMod
+            | DefKind::AnonConst
+            | DefKind::InlineConst
+            | DefKind::OpaqueTy
+            | DefKind::Field
+            | DefKind::LifetimeParam
+            | DefKind::GlobalAsm
+            | DefKind::Impl
+            | DefKind::Closure
+            | DefKind::Generator => Self::ForeignType,
+        }
+    }
+}
+
+impl ItemType {
+    pub(crate) fn as_str(&self) -> &'static str {
+        match *self {
+            ItemType::Module => "mod",
+            ItemType::ExternCrate => "externcrate",
+            ItemType::Import => "import",
+            ItemType::Struct => "struct",
+            ItemType::Union => "union",
+            ItemType::Enum => "enum",
+            ItemType::Function => "fn",
+            ItemType::Typedef => "type",
+            ItemType::Static => "static",
+            ItemType::Trait => "trait",
+            ItemType::Impl => "impl",
+            ItemType::TyMethod => "tymethod",
+            ItemType::Method => "method",
+            ItemType::StructField => "structfield",
+            ItemType::Variant => "variant",
+            ItemType::Macro => "macro",
+            ItemType::Primitive => "primitive",
+            ItemType::AssocType => "associatedtype",
+            ItemType::Constant => "constant",
+            ItemType::AssocConst => "associatedconstant",
+            ItemType::ForeignType => "foreigntype",
+            ItemType::Keyword => "keyword",
+            ItemType::OpaqueTy => "opaque",
+            ItemType::ProcAttribute => "attr",
+            ItemType::ProcDerive => "derive",
+            ItemType::TraitAlias => "traitalias",
+        }
+    }
+}
+
+impl fmt::Display for ItemType {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.write_str(self.as_str())
+    }
+}
diff --git a/src/librustdoc/formats/mod.rs b/src/librustdoc/formats/mod.rs
new file mode 100644
index 000000000..b236bd7be
--- /dev/null
+++ b/src/librustdoc/formats/mod.rs
@@ -0,0 +1,101 @@
+pub(crate) mod cache;
+pub(crate) mod item_type;
+pub(crate) mod renderer;
+
+use rustc_hir::def_id::DefId;
+
+pub(crate) use renderer::{run_format, FormatRenderer};
+
+use crate::clean::{self, ItemId};
+use crate::html::render::Context;
+
+/// Specifies whether rendering directly implemented trait items or ones from a certain Deref
+/// impl.
+pub(crate) enum AssocItemRender<'a> {
+    All,
+    DerefFor { trait_: &'a clean::Path, type_: &'a clean::Type, deref_mut_: bool },
+}
+
+/// For different handling of associated items from the Deref target of a type rather than the type
+/// itself.
+#[derive(Copy, Clone, PartialEq)]
+pub(crate) enum RenderMode {
+    Normal,
+    ForDeref { mut_: bool },
+}
+
+/// Metadata about implementations for a type or trait.
+#[derive(Clone, Debug)]
+pub(crate) struct Impl {
+    pub(crate) impl_item: clean::Item,
+}
+
+impl Impl {
+    pub(crate) fn inner_impl(&self) -> &clean::Impl {
+        match *self.impl_item.kind {
+            clean::ImplItem(ref impl_) => impl_,
+            _ => panic!("non-impl item found in impl"),
+        }
+    }
+
+    pub(crate) fn trait_did(&self) -> Option<DefId> {
+        self.inner_impl().trait_.as_ref().map(|t| t.def_id())
+    }
+
+    /// This function is used to extract a `DefId` to be used as a key for the `Cache::impls` field.
+    ///
+    /// It allows to prevent having duplicated implementations showing up (the biggest issue was
+    /// with blanket impls).
+    ///
+    /// It panics if `self` is a `ItemId::Primitive`.
+    pub(crate) fn def_id(&self) -> DefId {
+        match self.impl_item.item_id {
+            ItemId::Blanket { impl_id, .. } => impl_id,
+            ItemId::Auto { trait_, .. } => trait_,
+            ItemId::DefId(def_id) => def_id,
+            ItemId::Primitive(_, _) => {
+                panic!(
+                    "Unexpected ItemId::Primitive in expect_def_id: {:?}",
+                    self.impl_item.item_id
+                )
+            }
+        }
+    }
+
+    // Returns true if this is an implementation on a "local" type, meaning:
+    // the type is in the current crate, or the type and the trait are both
+    // re-exported by the current crate.
+    pub(crate) fn is_on_local_type(&self, cx: &Context<'_>) -> bool {
+        let cache = cx.cache();
+        let for_type = &self.inner_impl().for_;
+        if let Some(for_type_did) = for_type.def_id(cache) {
+            // The "for" type is local if it's in the paths for the current crate.
+            if cache.paths.contains_key(&for_type_did) {
+                return true;
+            }
+            if let Some(trait_did) = self.trait_did() {
+                // The "for" type and the trait are from the same crate. That could
+                // be different from the current crate, for instance when both were
+                // re-exported from some other crate. But they are local with respect to
+                // each other.
+                if for_type_did.krate == trait_did.krate {
+                    return true;
+                }
+                // Hack: many traits and types in std are re-exported from
+                // core or alloc. In general, rustdoc is capable of recognizing
+                // these implementations as being on local types. However, in at
+                // least one case (https://github.com/rust-lang/rust/issues/97610),
+                // rustdoc gets confused and labels an implementation as being on
+                // a foreign type. To make sure that confusion doesn't pass on to
+                // the reader, consider all implementations in std, core, and alloc
+                // to be on local types.
+                let crate_name = cx.tcx().crate_name(trait_did.krate);
+                if matches!(crate_name.as_str(), "std" | "core" | "alloc") {
+                    return true;
+                }
+            }
+            return false;
+        };
+        true
+    }
+}
diff --git a/src/librustdoc/formats/renderer.rs b/src/librustdoc/formats/renderer.rs
new file mode 100644
index 000000000..62ba984ac
--- /dev/null
+++ b/src/librustdoc/formats/renderer.rs
@@ -0,0 +1,97 @@
+use rustc_middle::ty::TyCtxt;
+use rustc_span::Symbol;
+
+use crate::clean;
+use crate::config::RenderOptions;
+use crate::error::Error;
+use crate::formats::cache::Cache;
+
+/// Allows for different backends to rustdoc to be used with the `run_format()` function. Each
+/// backend renderer has hooks for initialization, documenting an item, entering and exiting a
+/// module, and cleanup/finalizing output.
+pub(crate) trait FormatRenderer<'tcx>: Sized {
+    /// Gives a description of the renderer. Used for performance profiling.
+    fn descr() -> &'static str;
+
+    /// Whether to call `item` recursively for modules
+    ///
+    /// This is true for html, and false for json. See #80664
+    const RUN_ON_MODULE: bool;
+
+    /// Sets up any state required for the renderer. When this is called the cache has already been
+    /// populated.
+    fn init(
+        krate: clean::Crate,
+        options: RenderOptions,
+        cache: Cache,
+        tcx: TyCtxt<'tcx>,
+    ) -> Result<(Self, clean::Crate), Error>;
+
+    /// Make a new renderer to render a child of the item currently being rendered.
+    fn make_child_renderer(&self) -> Self;
+
+    /// Renders a single non-module item. This means no recursive sub-item rendering is required.
+    fn item(&mut self, item: clean::Item) -> Result<(), Error>;
+
+    /// Renders a module (should not handle recursing into children).
+    fn mod_item_in(&mut self, item: &clean::Item) -> Result<(), Error>;
+
+    /// Runs after recursively rendering all sub-items of a module.
+    fn mod_item_out(&mut self) -> Result<(), Error> {
+        Ok(())
+    }
+
+    /// Post processing hook for cleanup and dumping output to files.
+    fn after_krate(&mut self) -> Result<(), Error>;
+
+    fn cache(&self) -> &Cache;
+}
+
+/// Main method for rendering a crate.
+pub(crate) fn run_format<'tcx, T: FormatRenderer<'tcx>>(
+    krate: clean::Crate,
+    options: RenderOptions,
+    cache: Cache,
+    tcx: TyCtxt<'tcx>,
+) -> Result<(), Error> {
+    let prof = &tcx.sess.prof;
+
+    let emit_crate = options.should_emit_crate();
+    let (mut format_renderer, krate) = prof
+        .extra_verbose_generic_activity("create_renderer", T::descr())
+        .run(|| T::init(krate, options, cache, tcx))?;
+
+    if !emit_crate {
+        return Ok(());
+    }
+
+    // Render the crate documentation
+    let mut work = vec![(format_renderer.make_child_renderer(), krate.module)];
+
+    let unknown = Symbol::intern("<unknown item>");
+    while let Some((mut cx, item)) = work.pop() {
+        if item.is_mod() && T::RUN_ON_MODULE {
+            // modules are special because they add a namespace. We also need to
+            // recurse into the items of the module as well.
+            let _timer =
+                prof.generic_activity_with_arg("render_mod_item", item.name.unwrap().to_string());
+
+            cx.mod_item_in(&item)?;
+            let (clean::StrippedItem(box clean::ModuleItem(module)) | clean::ModuleItem(module)) = *item.kind
+            else { unreachable!() };
+            for it in module.items {
+                debug!("Adding {:?} to worklist", it.name);
+                work.push((cx.make_child_renderer(), it));
+            }
+
+            cx.mod_item_out()?;
+        // FIXME: checking `item.name.is_some()` is very implicit and leads to lots of special
+        // cases. Use an explicit match instead.
+        } else if item.name.is_some() && !item.is_extern_crate() {
+            prof.generic_activity_with_arg("render_item", item.name.unwrap_or(unknown).as_str())
+                .run(|| cx.item(item))?;
+        }
+    }
+    prof.extra_verbose_generic_activity("renderer_after_krate", T::descr())
+        .run(|| format_renderer.after_krate())
+}