src/librustdoc/clean/types.rs

   1 use std::cell::RefCell;
   2 use std::default::Default;
   3 use std::hash::{Hash, Hasher};
   4 use std::lazy::SyncOnceCell as OnceCell;
   5 use std::path::PathBuf;
   6 use std::rc::Rc;
   7 use std::sync::Arc;
   8 use std::{slice, vec};
   9
  10 use arrayvec::ArrayVec;
  11
  12 use rustc_ast::attr;
  13 use rustc_ast::util::comments::beautify_doc_string;
  14 use rustc_ast::{self as ast, AttrStyle};
  15 use rustc_attr::{ConstStability, Deprecation, Stability, StabilityLevel};
  16 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  17 use rustc_data_structures::thin_vec::ThinVec;
  18 use rustc_hir as hir;
  19 use rustc_hir::def::{CtorKind, DefKind, Res};
  20 use rustc_hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX, LOCAL_CRATE};
  21 use rustc_hir::lang_items::LangItem;
  22 use rustc_hir::{BodyId, Mutability};
  23 use rustc_index::vec::IndexVec;
  24 use rustc_middle::ty::{self, TyCtxt};
  25 use rustc_session::Session;
  26 use rustc_span::hygiene::MacroKind;
  27 use rustc_span::source_map::DUMMY_SP;
  28 use rustc_span::symbol::{kw, sym, Ident, Symbol};
  29 use rustc_span::{self, FileName, Loc};
  30 use rustc_target::abi::VariantIdx;
  31 use rustc_target::spec::abi::Abi;
  32
  33 use crate::clean::cfg::Cfg;
  34 use crate::clean::external_path;
  35 use crate::clean::inline::{self, print_inlined_const};
  36 use crate::clean::utils::{is_literal_expr, print_const_expr, print_evaluated_const};
  37 use crate::clean::Clean;
  38 use crate::core::DocContext;
  39 use crate::formats::cache::Cache;
  40 use crate::formats::item_type::ItemType;
  41 use crate::html::render::cache::ExternalLocation;
  42 use crate::html::render::Context;
  43
  44 crate use self::FnRetTy::*;
  45 crate use self::ItemKind::*;
  46 crate use self::SelfTy::*;
  47 crate use self::Type::{
  48     Array, BareFunction, BorrowedRef, DynTrait, Generic, ImplTrait, Infer, Primitive, QPath,
  49     RawPointer, Slice, Tuple,
  50 };
  51 crate use self::Visibility::{Inherited, Public};
  52
  53 crate type ItemIdSet = FxHashSet<ItemId>;
  54
  55 #[derive(Debug, Clone, PartialEq, Eq, Hash, Copy)]
  56 crate enum ItemId {
  57     /// A "normal" item that uses a [`DefId`] for identification.
  58     DefId(DefId),
  59     /// Identifier that is used for auto traits.
  60     Auto { trait_: DefId, for_: DefId },
  61     /// Identifier that is used for blanket implementations.
  62     Blanket { impl_id: DefId, for_: DefId },
  63     /// Identifier for primitive types.
  64     Primitive(PrimitiveType, CrateNum),
  65 }
  66
  67 impl ItemId {
  68     #[inline]
  69     crate fn is_local(self) -> bool {
  70         match self {
  71             ItemId::Auto { for_: id, .. }
  72             | ItemId::Blanket { for_: id, .. }
  73             | ItemId::DefId(id) => id.is_local(),
  74             ItemId::Primitive(_, krate) => krate == LOCAL_CRATE,
  75         }
  76     }
  77
  78     #[inline]
  79     #[track_caller]
  80     crate fn expect_def_id(self) -> DefId {
  81         self.as_def_id()
  82             .unwrap_or_else(|| panic!("ItemId::expect_def_id: `{:?}` isn't a DefId", self))
  83     }
  84
  85     #[inline]
  86     crate fn as_def_id(self) -> Option<DefId> {
  87         match self {
  88             ItemId::DefId(id) => Some(id),
  89             _ => None,
  90         }
  91     }
  92
  93     #[inline]
  94     crate fn krate(self) -> CrateNum {
  95         match self {
  96             ItemId::Auto { for_: id, .. }
  97             | ItemId::Blanket { for_: id, .. }
  98             | ItemId::DefId(id) => id.krate,
  99             ItemId::Primitive(_, krate) => krate,
 100         }
 101     }
 102
 103     #[inline]
 104     crate fn index(self) -> Option<DefIndex> {
 105         match self {
 106             ItemId::DefId(id) => Some(id.index),
 107             _ => None,
 108         }
 109     }
 110 }
 111
 112 impl From<DefId> for ItemId {
 113     fn from(id: DefId) -> Self {
 114         Self::DefId(id)
 115     }
 116 }
 117
 118 /// The crate currently being documented.
 119 #[derive(Clone, Debug)]
 120 crate struct Crate {
 121     crate module: Item,
 122     crate primitives: ThinVec<(DefId, PrimitiveType)>,
 123     /// Only here so that they can be filtered through the rustdoc passes.
 124     crate external_traits: Rc<RefCell<FxHashMap<DefId, TraitWithExtraInfo>>>,
 125 }
 126
 127 // `Crate` is frequently moved by-value. Make sure it doesn't unintentionally get bigger.
 128 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
 129 rustc_data_structures::static_assert_size!(Crate, 72);
 130
 131 impl Crate {
 132     crate fn name(&self, tcx: TyCtxt<'_>) -> Symbol {
 133         ExternalCrate::LOCAL.name(tcx)
 134     }
 135
 136     crate fn src(&self, tcx: TyCtxt<'_>) -> FileName {
 137         ExternalCrate::LOCAL.src(tcx)
 138     }
 139 }
 140
 141 /// This struct is used to wrap additional information added by rustdoc on a `trait` item.
 142 #[derive(Clone, Debug)]
 143 crate struct TraitWithExtraInfo {
 144     crate trait_: Trait,
 145     crate is_notable: bool,
 146 }
 147
 148 #[derive(Copy, Clone, Debug)]
 149 crate struct ExternalCrate {
 150     crate crate_num: CrateNum,
 151 }
 152
 153 impl ExternalCrate {
 154     const LOCAL: Self = Self { crate_num: LOCAL_CRATE };
 155
 156     #[inline]
 157     crate fn def_id(&self) -> DefId {
 158         DefId { krate: self.crate_num, index: CRATE_DEF_INDEX }
 159     }
 160
 161     crate fn src(&self, tcx: TyCtxt<'_>) -> FileName {
 162         let krate_span = tcx.def_span(self.def_id());
 163         tcx.sess.source_map().span_to_filename(krate_span)
 164     }
 165
 166     crate fn name(&self, tcx: TyCtxt<'_>) -> Symbol {
 167         tcx.crate_name(self.crate_num)
 168     }
 169
 170     crate fn src_root(&self, tcx: TyCtxt<'_>) -> PathBuf {
 171         match self.src(tcx) {
 172             FileName::Real(ref p) => match p.local_path_if_available().parent() {
 173                 Some(p) => p.to_path_buf(),
 174                 None => PathBuf::new(),
 175             },
 176             _ => PathBuf::new(),
 177         }
 178     }
 179
 180     /// Attempts to find where an external crate is located, given that we're
 181     /// rendering in to the specified source destination.
 182     crate fn location(
 183         &self,
 184         extern_url: Option<&str>,
 185         extern_url_takes_precedence: bool,
 186         dst: &std::path::Path,
 187         tcx: TyCtxt<'_>,
 188     ) -> ExternalLocation {
 189         use ExternalLocation::*;
 190
 191         fn to_remote(url: impl ToString) -> ExternalLocation {
 192             let mut url = url.to_string();
 193             if !url.ends_with('/') {
 194                 url.push('/');
 195             }
 196             Remote(url)
 197         }
 198
 199         // See if there's documentation generated into the local directory
 200         // WARNING: since rustdoc creates these directories as it generates documentation, this check is only accurate before rendering starts.
 201         // Make sure to call `location()` by that time.
 202         let local_location = dst.join(self.name(tcx).as_str());
 203         if local_location.is_dir() {
 204             return Local;
 205         }
 206
 207         if extern_url_takes_precedence {
 208             if let Some(url) = extern_url {
 209                 return to_remote(url);
 210             }
 211         }
 212
 213         // Failing that, see if there's an attribute specifying where to find this
 214         // external crate
 215         let did = DefId { krate: self.crate_num, index: CRATE_DEF_INDEX };
 216         tcx.get_attrs(did)
 217             .lists(sym::doc)
 218             .filter(|a| a.has_name(sym::html_root_url))
 219             .filter_map(|a| a.value_str())
 220             .map(to_remote)
 221             .next()
 222             .or_else(|| extern_url.map(to_remote)) // NOTE: only matters if `extern_url_takes_precedence` is false
 223             .unwrap_or(Unknown) // Well, at least we tried.
 224     }
 225
 226     crate fn keywords(&self, tcx: TyCtxt<'_>) -> ThinVec<(DefId, Symbol)> {
 227         let root = self.def_id();
 228
 229         let as_keyword = |res: Res<!>| {
 230             if let Res::Def(DefKind::Mod, def_id) = res {
 231                 let attrs = tcx.get_attrs(def_id);
 232                 let mut keyword = None;
 233                 for attr in attrs.lists(sym::doc) {
 234                     if attr.has_name(sym::keyword) {
 235                         if let Some(v) = attr.value_str() {
 236                             keyword = Some(v);
 237                             break;
 238                         }
 239                     }
 240                 }
 241                 return keyword.map(|p| (def_id, p));
 242             }
 243             None
 244         };
 245         if root.is_local() {
 246             tcx.hir()
 247                 .root_module()
 248                 .item_ids
 249                 .iter()
 250                 .filter_map(|&id| {
 251                     let item = tcx.hir().item(id);
 252                     match item.kind {
 253                         hir::ItemKind::Mod(_) => {
 254                             as_keyword(Res::Def(DefKind::Mod, id.def_id.to_def_id()))
 255                         }
 256                         hir::ItemKind::Use(path, hir::UseKind::Single)
 257                             if tcx.visibility(id.def_id).is_public() =>
 258                         {
 259                             as_keyword(path.res.expect_non_local())
 260                                 .map(|(_, prim)| (id.def_id.to_def_id(), prim))
 261                         }
 262                         _ => None,
 263                     }
 264                 })
 265                 .collect()
 266         } else {
 267             tcx.item_children(root).iter().map(|item| item.res).filter_map(as_keyword).collect()
 268         }
 269     }
 270
 271     crate fn primitives(&self, tcx: TyCtxt<'_>) -> ThinVec<(DefId, PrimitiveType)> {
 272         let root = self.def_id();
 273
 274         // Collect all inner modules which are tagged as implementations of
 275         // primitives.
 276         //
 277         // Note that this loop only searches the top-level items of the crate,
 278         // and this is intentional. If we were to search the entire crate for an
 279         // item tagged with `#[doc(primitive)]` then we would also have to
 280         // search the entirety of external modules for items tagged
 281         // `#[doc(primitive)]`, which is a pretty inefficient process (decoding
 282         // all that metadata unconditionally).
 283         //
 284         // In order to keep the metadata load under control, the
 285         // `#[doc(primitive)]` feature is explicitly designed to only allow the
 286         // primitive tags to show up as the top level items in a crate.
 287         //
 288         // Also note that this does not attempt to deal with modules tagged
 289         // duplicately for the same primitive. This is handled later on when
 290         // rendering by delegating everything to a hash map.
 291         let as_primitive = |res: Res<!>| {
 292             if let Res::Def(DefKind::Mod, def_id) = res {
 293                 let attrs = tcx.get_attrs(def_id);
 294                 let mut prim = None;
 295                 for attr in attrs.lists(sym::doc) {
 296                     if let Some(v) = attr.value_str() {
 297                         if attr.has_name(sym::primitive) {
 298                             prim = PrimitiveType::from_symbol(v);
 299                             if prim.is_some() {
 300                                 break;
 301                             }
 302                             // FIXME: should warn on unknown primitives?
 303                         }
 304                     }
 305                 }
 306                 return prim.map(|p| (def_id, p));
 307             }
 308             None
 309         };
 310
 311         if root.is_local() {
 312             tcx.hir()
 313                 .root_module()
 314                 .item_ids
 315                 .iter()
 316                 .filter_map(|&id| {
 317                     let item = tcx.hir().item(id);
 318                     match item.kind {
 319                         hir::ItemKind::Mod(_) => {
 320                             as_primitive(Res::Def(DefKind::Mod, id.def_id.to_def_id()))
 321                         }
 322                         hir::ItemKind::Use(path, hir::UseKind::Single)
 323                             if tcx.visibility(id.def_id).is_public() =>
 324                         {
 325                             as_primitive(path.res.expect_non_local()).map(|(_, prim)| {
 326                                 // Pretend the primitive is local.
 327                                 (id.def_id.to_def_id(), prim)
 328                             })
 329                         }
 330                         _ => None,
 331                     }
 332                 })
 333                 .collect()
 334         } else {
 335             tcx.item_children(root).iter().map(|item| item.res).filter_map(as_primitive).collect()
 336         }
 337     }
 338 }
 339
 340 /// Anything with a source location and set of attributes and, optionally, a
 341 /// name. That is, anything that can be documented. This doesn't correspond
 342 /// directly to the AST's concept of an item; it's a strict superset.
 343 #[derive(Clone, Debug)]
 344 crate struct Item {
 345     /// The name of this item.
 346     /// Optional because not every item has a name, e.g. impls.
 347     crate name: Option<Symbol>,
 348     crate attrs: Box<Attributes>,
 349     crate visibility: Visibility,
 350     /// Information about this item that is specific to what kind of item it is.
 351     /// E.g., struct vs enum vs function.
 352     crate kind: Box<ItemKind>,
 353     crate def_id: ItemId,
 354
 355     crate cfg: Option<Arc<Cfg>>,
 356 }
 357
 358 // `Item` is used a lot. Make sure it doesn't unintentionally get bigger.
 359 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
 360 rustc_data_structures::static_assert_size!(Item, 56);
 361
 362 crate fn rustc_span(def_id: DefId, tcx: TyCtxt<'_>) -> Span {
 363     Span::new(def_id.as_local().map_or_else(
 364         || tcx.def_span(def_id),
 365         |local| {
 366             let hir = tcx.hir();
 367             hir.span_with_body(hir.local_def_id_to_hir_id(local))
 368         },
 369     ))
 370 }
 371
 372 impl Item {
 373     crate fn stability<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Option<&'tcx Stability> {
 374         self.def_id.as_def_id().and_then(|did| tcx.lookup_stability(did))
 375     }
 376
 377     crate fn const_stability<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Option<ConstStability> {
 378         self.def_id.as_def_id().and_then(|did| tcx.lookup_const_stability(did)).map(|cs| *cs)
 379     }
 380
 381     crate fn deprecation(&self, tcx: TyCtxt<'_>) -> Option<Deprecation> {
 382         self.def_id.as_def_id().and_then(|did| tcx.lookup_deprecation(did))
 383     }
 384
 385     crate fn inner_docs(&self, tcx: TyCtxt<'_>) -> bool {
 386         self.def_id.as_def_id().map(|did| tcx.get_attrs(did).inner_docs()).unwrap_or(false)
 387     }
 388
 389     crate fn span(&self, tcx: TyCtxt<'_>) -> Span {
 390         let kind = match &*self.kind {
 391             ItemKind::StrippedItem(k) => k,
 392             _ => &*self.kind,
 393         };
 394         match kind {
 395             ItemKind::ModuleItem(Module { span, .. }) => *span,
 396             ItemKind::ImplItem(Impl { kind: ImplKind::Auto, .. }) => Span::dummy(),
 397             ItemKind::ImplItem(Impl { kind: ImplKind::Blanket(_), .. }) => {
 398                 if let ItemId::Blanket { impl_id, .. } = self.def_id {
 399                     rustc_span(impl_id, tcx)
 400                 } else {
 401                     panic!("blanket impl item has non-blanket ID")
 402                 }
 403             }
 404             _ => {
 405                 self.def_id.as_def_id().map(|did| rustc_span(did, tcx)).unwrap_or_else(Span::dummy)
 406             }
 407         }
 408     }
 409
 410     crate fn attr_span(&self, tcx: TyCtxt<'_>) -> rustc_span::Span {
 411         crate::passes::span_of_attrs(&self.attrs).unwrap_or_else(|| self.span(tcx).inner())
 412     }
 413
 414     /// Finds the `doc` attribute as a NameValue and returns the corresponding
 415     /// value found.
 416     crate fn doc_value(&self) -> Option<String> {
 417         self.attrs.doc_value()
 418     }
 419
 420     /// Convenience wrapper around [`Self::from_def_id_and_parts`] which converts
 421     /// `hir_id` to a [`DefId`]
 422     pub fn from_hir_id_and_parts(
 423         hir_id: hir::HirId,
 424         name: Option<Symbol>,
 425         kind: ItemKind,
 426         cx: &mut DocContext<'_>,
 427     ) -> Item {
 428         Item::from_def_id_and_parts(cx.tcx.hir().local_def_id(hir_id).to_def_id(), name, kind, cx)
 429     }
 430
 431     pub fn from_def_id_and_parts(
 432         def_id: DefId,
 433         name: Option<Symbol>,
 434         kind: ItemKind,
 435         cx: &mut DocContext<'_>,
 436     ) -> Item {
 437         let ast_attrs = cx.tcx.get_attrs(def_id);
 438
 439         Self::from_def_id_and_attrs_and_parts(
 440             def_id,
 441             name,
 442             kind,
 443             box ast_attrs.clean(cx),
 444             cx,
 445             ast_attrs.cfg(cx.tcx, &cx.cache.hidden_cfg),
 446         )
 447     }
 448
 449     pub fn from_def_id_and_attrs_and_parts(
 450         def_id: DefId,
 451         name: Option<Symbol>,
 452         kind: ItemKind,
 453         attrs: Box<Attributes>,
 454         cx: &mut DocContext<'_>,
 455         cfg: Option<Arc<Cfg>>,
 456     ) -> Item {
 457         trace!("name={:?}, def_id={:?}", name, def_id);
 458
 459         Item {
 460             def_id: def_id.into(),
 461             kind: box kind,
 462             name,
 463             attrs,
 464             visibility: cx.tcx.visibility(def_id).clean(cx),
 465             cfg,
 466         }
 467     }
 468
 469     /// Finds all `doc` attributes as NameValues and returns their corresponding values, joined
 470     /// with newlines.
 471     crate fn collapsed_doc_value(&self) -> Option<String> {
 472         self.attrs.collapsed_doc_value()
 473     }
 474
 475     crate fn links(&self, cx: &Context<'_>) -> Vec<RenderedLink> {
 476         use crate::html::format::href;
 477
 478         cx.cache()
 479             .intra_doc_links
 480             .get(&self.def_id)
 481             .map_or(&[][..], |v| v.as_slice())
 482             .iter()
 483             .filter_map(|ItemLink { link: s, link_text, did, ref fragment }| {
 484                 debug!(?did);
 485                 if let Ok((mut href, ..)) = href(*did, cx) {
 486                     debug!(?href);
 487                     if let Some(ref fragment) = *fragment {
 488                         href.push('#');
 489                         href.push_str(fragment);
 490                     }
 491                     Some(RenderedLink {
 492                         original_text: s.clone(),
 493                         new_text: link_text.clone(),
 494                         href,
 495                     })
 496                 } else {
 497                     None
 498                 }
 499             })
 500             .collect()
 501     }
 502
 503     /// Find a list of all link names, without finding their href.
 504     ///
 505     /// This is used for generating summary text, which does not include
 506     /// the link text, but does need to know which `[]`-bracketed names
 507     /// are actually links.
 508     crate fn link_names(&self, cache: &Cache) -> Vec<RenderedLink> {
 509         cache
 510             .intra_doc_links
 511             .get(&self.def_id)
 512             .map_or(&[][..], |v| v.as_slice())
 513             .iter()
 514             .map(|ItemLink { link: s, link_text, .. }| RenderedLink {
 515                 original_text: s.clone(),
 516                 new_text: link_text.clone(),
 517                 href: String::new(),
 518             })
 519             .collect()
 520     }
 521
 522     crate fn is_crate(&self) -> bool {
 523         self.is_mod() && self.def_id.as_def_id().map_or(false, |did| did.index == CRATE_DEF_INDEX)
 524     }
 525     crate fn is_mod(&self) -> bool {
 526         self.type_() == ItemType::Module
 527     }
 528     crate fn is_trait(&self) -> bool {
 529         self.type_() == ItemType::Trait
 530     }
 531     crate fn is_struct(&self) -> bool {
 532         self.type_() == ItemType::Struct
 533     }
 534     crate fn is_enum(&self) -> bool {
 535         self.type_() == ItemType::Enum
 536     }
 537     crate fn is_variant(&self) -> bool {
 538         self.type_() == ItemType::Variant
 539     }
 540     crate fn is_associated_type(&self) -> bool {
 541         self.type_() == ItemType::AssocType
 542     }
 543     crate fn is_associated_const(&self) -> bool {
 544         self.type_() == ItemType::AssocConst
 545     }
 546     crate fn is_method(&self) -> bool {
 547         self.type_() == ItemType::Method
 548     }
 549     crate fn is_ty_method(&self) -> bool {
 550         self.type_() == ItemType::TyMethod
 551     }
 552     crate fn is_typedef(&self) -> bool {
 553         self.type_() == ItemType::Typedef
 554     }
 555     crate fn is_primitive(&self) -> bool {
 556         self.type_() == ItemType::Primitive
 557     }
 558     crate fn is_union(&self) -> bool {
 559         self.type_() == ItemType::Union
 560     }
 561     crate fn is_import(&self) -> bool {
 562         self.type_() == ItemType::Import
 563     }
 564     crate fn is_extern_crate(&self) -> bool {
 565         self.type_() == ItemType::ExternCrate
 566     }
 567     crate fn is_keyword(&self) -> bool {
 568         self.type_() == ItemType::Keyword
 569     }
 570     crate fn is_stripped(&self) -> bool {
 571         match *self.kind {
 572             StrippedItem(..) => true,
 573             ImportItem(ref i) => !i.should_be_displayed,
 574             _ => false,
 575         }
 576     }
 577     crate fn has_stripped_fields(&self) -> Option<bool> {
 578         match *self.kind {
 579             StructItem(ref _struct) => Some(_struct.fields_stripped),
 580             UnionItem(ref union) => Some(union.fields_stripped),
 581             VariantItem(Variant::Struct(ref vstruct)) => Some(vstruct.fields_stripped),
 582             _ => None,
 583         }
 584     }
 585
 586     crate fn stability_class(&self, tcx: TyCtxt<'_>) -> Option<String> {
 587         self.stability(tcx).as_ref().and_then(|s| {
 588             let mut classes = Vec::with_capacity(2);
 589
 590             if s.level.is_unstable() {
 591                 classes.push("unstable");
 592             }
 593
 594             // FIXME: what about non-staged API items that are deprecated?
 595             if self.deprecation(tcx).is_some() {
 596                 classes.push("deprecated");
 597             }
 598
 599             if !classes.is_empty() { Some(classes.join(" ")) } else { None }
 600         })
 601     }
 602
 603     crate fn stable_since(&self, tcx: TyCtxt<'_>) -> Option<Symbol> {
 604         match self.stability(tcx)?.level {
 605             StabilityLevel::Stable { since, .. } => Some(since),
 606             StabilityLevel::Unstable { .. } => None,
 607         }
 608     }
 609
 610     crate fn const_stable_since(&self, tcx: TyCtxt<'_>) -> Option<Symbol> {
 611         match self.const_stability(tcx)?.level {
 612             StabilityLevel::Stable { since, .. } => Some(since),
 613             StabilityLevel::Unstable { .. } => None,
 614         }
 615     }
 616
 617     crate fn is_non_exhaustive(&self) -> bool {
 618         self.attrs.other_attrs.iter().any(|a| a.has_name(sym::non_exhaustive))
 619     }
 620
 621     /// Returns a documentation-level item type from the item.
 622     crate fn type_(&self) -> ItemType {
 623         ItemType::from(self)
 624     }
 625
 626     crate fn is_default(&self) -> bool {
 627         match *self.kind {
 628             ItemKind::MethodItem(_, Some(defaultness)) => {
 629                 defaultness.has_value() && !defaultness.is_final()
 630             }
 631             _ => false,
 632         }
 633     }
 634 }
 635
 636 #[derive(Clone, Debug)]
 637 crate enum ItemKind {
 638     ExternCrateItem {
 639         /// The crate's name, *not* the name it's imported as.
 640         src: Option<Symbol>,
 641     },
 642     ImportItem(Import),
 643     StructItem(Struct),
 644     UnionItem(Union),
 645     EnumItem(Enum),
 646     FunctionItem(Function),
 647     ModuleItem(Module),
 648     TypedefItem(Typedef, bool /* is associated type */),
 649     OpaqueTyItem(OpaqueTy),
 650     StaticItem(Static),
 651     ConstantItem(Constant),
 652     TraitItem(Trait),
 653     TraitAliasItem(TraitAlias),
 654     ImplItem(Impl),
 655     /// A method signature only. Used for required methods in traits (ie,
 656     /// non-default-methods).
 657     TyMethodItem(Function),
 658     /// A method with a body.
 659     MethodItem(Function, Option<hir::Defaultness>),
 660     StructFieldItem(Type),
 661     VariantItem(Variant),
 662     /// `fn`s from an extern block
 663     ForeignFunctionItem(Function),
 664     /// `static`s from an extern block
 665     ForeignStaticItem(Static),
 666     /// `type`s from an extern block
 667     ForeignTypeItem,
 668     MacroItem(Macro),
 669     ProcMacroItem(ProcMacro),
 670     PrimitiveItem(PrimitiveType),
 671     AssocConstItem(Type, Option<ConstantKind>),
 672     /// An associated item in a trait or trait impl.
 673     ///
 674     /// The bounds may be non-empty if there is a `where` clause.
 675     /// The `Option<Type>` is the default concrete type (e.g. `trait Trait { type Target = usize; }`)
 676     AssocTypeItem(Vec<GenericBound>, Option<Type>),
 677     /// An item that has been stripped by a rustdoc pass
 678     StrippedItem(Box<ItemKind>),
 679     KeywordItem(Symbol),
 680 }
 681
 682 impl ItemKind {
 683     /// Some items contain others such as structs (for their fields) and Enums
 684     /// (for their variants). This method returns those contained items.
 685     crate fn inner_items(&self) -> impl Iterator<Item = &Item> {
 686         match self {
 687             StructItem(s) => s.fields.iter(),
 688             UnionItem(u) => u.fields.iter(),
 689             VariantItem(Variant::Struct(v)) => v.fields.iter(),
 690             VariantItem(Variant::Tuple(v)) => v.iter(),
 691             EnumItem(e) => e.variants.iter(),
 692             TraitItem(t) => t.items.iter(),
 693             ImplItem(i) => i.items.iter(),
 694             ModuleItem(m) => m.items.iter(),
 695             ExternCrateItem { .. }
 696             | ImportItem(_)
 697             | FunctionItem(_)
 698             | TypedefItem(_, _)
 699             | OpaqueTyItem(_)
 700             | StaticItem(_)
 701             | ConstantItem(_)
 702             | TraitAliasItem(_)
 703             | TyMethodItem(_)
 704             | MethodItem(_, _)
 705             | StructFieldItem(_)
 706             | VariantItem(_)
 707             | ForeignFunctionItem(_)
 708             | ForeignStaticItem(_)
 709             | ForeignTypeItem
 710             | MacroItem(_)
 711             | ProcMacroItem(_)
 712             | PrimitiveItem(_)
 713             | AssocConstItem(_, _)
 714             | AssocTypeItem(_, _)
 715             | StrippedItem(_)
 716             | KeywordItem(_) => [].iter(),
 717         }
 718     }
 719 }
 720
 721 #[derive(Clone, Debug)]
 722 crate struct Module {
 723     crate items: Vec<Item>,
 724     crate span: Span,
 725 }
 726
 727 crate struct ListAttributesIter<'a> {
 728     attrs: slice::Iter<'a, ast::Attribute>,
 729     current_list: vec::IntoIter<ast::NestedMetaItem>,
 730     name: Symbol,
 731 }
 732
 733 impl<'a> Iterator for ListAttributesIter<'a> {
 734     type Item = ast::NestedMetaItem;
 735
 736     fn next(&mut self) -> Option<Self::Item> {
 737         if let Some(nested) = self.current_list.next() {
 738             return Some(nested);
 739         }
 740
 741         for attr in &mut self.attrs {
 742             if let Some(list) = attr.meta_item_list() {
 743                 if attr.has_name(self.name) {
 744                     self.current_list = list.into_iter();
 745                     if let Some(nested) = self.current_list.next() {
 746                         return Some(nested);
 747                     }
 748                 }
 749             }
 750         }
 751
 752         None
 753     }
 754
 755     fn size_hint(&self) -> (usize, Option<usize>) {
 756         let lower = self.current_list.len();
 757         (lower, None)
 758     }
 759 }
 760
 761 crate trait AttributesExt {
 762     /// Finds an attribute as List and returns the list of attributes nested inside.
 763     fn lists(&self, name: Symbol) -> ListAttributesIter<'_>;
 764
 765     fn span(&self) -> Option<rustc_span::Span>;
 766
 767     fn inner_docs(&self) -> bool;
 768
 769     fn other_attrs(&self) -> Vec<ast::Attribute>;
 770
 771     fn cfg(&self, tcx: TyCtxt<'_>, hidden_cfg: &FxHashSet<Cfg>) -> Option<Arc<Cfg>>;
 772 }
 773
 774 impl AttributesExt for [ast::Attribute] {
 775     fn lists(&self, name: Symbol) -> ListAttributesIter<'_> {
 776         ListAttributesIter { attrs: self.iter(), current_list: Vec::new().into_iter(), name }
 777     }
 778
 779     /// Return the span of the first doc-comment, if it exists.
 780     fn span(&self) -> Option<rustc_span::Span> {
 781         self.iter().find(|attr| attr.doc_str().is_some()).map(|attr| attr.span)
 782     }
 783
 784     /// Returns whether the first doc-comment is an inner attribute.
 785     ///
 786     //// If there are no doc-comments, return true.
 787     /// FIXME(#78591): Support both inner and outer attributes on the same item.
 788     fn inner_docs(&self) -> bool {
 789         self.iter().find(|a| a.doc_str().is_some()).map_or(true, |a| a.style == AttrStyle::Inner)
 790     }
 791
 792     fn other_attrs(&self) -> Vec<ast::Attribute> {
 793         self.iter().filter(|attr| attr.doc_str().is_none()).cloned().collect()
 794     }
 795
 796     fn cfg(&self, tcx: TyCtxt<'_>, hidden_cfg: &FxHashSet<Cfg>) -> Option<Arc<Cfg>> {
 797         let sess = tcx.sess;
 798         let doc_cfg_active = tcx.features().doc_cfg;
 799         let doc_auto_cfg_active = tcx.features().doc_auto_cfg;
 800
 801         fn single<T: IntoIterator>(it: T) -> Option<T::Item> {
 802             let mut iter = it.into_iter();
 803             let item = iter.next()?;
 804             if iter.next().is_some() {
 805                 return None;
 806             }
 807             Some(item)
 808         }
 809
 810         let mut cfg = if doc_cfg_active || doc_auto_cfg_active {
 811             let mut doc_cfg = self
 812                 .iter()
 813                 .filter(|attr| attr.has_name(sym::doc))
 814                 .flat_map(|attr| attr.meta_item_list().unwrap_or_else(Vec::new))
 815                 .filter(|attr| attr.has_name(sym::cfg))
 816                 .peekable();
 817             if doc_cfg.peek().is_some() && doc_cfg_active {
 818                 doc_cfg
 819                     .filter_map(|attr| Cfg::parse(attr.meta_item()?).ok())
 820                     .fold(Cfg::True, |cfg, new_cfg| cfg & new_cfg)
 821             } else if doc_auto_cfg_active {
 822                 self.iter()
 823                     .filter(|attr| attr.has_name(sym::cfg))
 824                     .filter_map(|attr| single(attr.meta_item_list()?))
 825                     .filter_map(|attr| Cfg::parse(attr.meta_item()?).ok())
 826                     .filter(|cfg| !hidden_cfg.contains(cfg))
 827                     .fold(Cfg::True, |cfg, new_cfg| cfg & new_cfg)
 828             } else {
 829                 Cfg::True
 830             }
 831         } else {
 832             Cfg::True
 833         };
 834
 835         for attr in self.iter() {
 836             // #[doc]
 837             if attr.doc_str().is_none() && attr.has_name(sym::doc) {
 838                 // #[doc(...)]
 839                 if let Some(list) = attr.meta().as_ref().and_then(|mi| mi.meta_item_list()) {
 840                     for item in list {
 841                         // #[doc(hidden)]
 842                         if !item.has_name(sym::cfg) {
 843                             continue;
 844                         }
 845                         // #[doc(cfg(...))]
 846                         if let Some(cfg_mi) = item
 847                             .meta_item()
 848                             .and_then(|item| rustc_expand::config::parse_cfg(item, sess))
 849                         {
 850                             match Cfg::parse(cfg_mi) {
 851                                 Ok(new_cfg) => cfg &= new_cfg,
 852                                 Err(e) => sess.span_err(e.span, e.msg),
 853                             }
 854                         }
 855                     }
 856                 }
 857             }
 858         }
 859
 860         // treat #[target_feature(enable = "feat")] attributes as if they were
 861         // #[doc(cfg(target_feature = "feat"))] attributes as well
 862         for attr in self.lists(sym::target_feature) {
 863             if attr.has_name(sym::enable) {
 864                 if let Some(feat) = attr.value_str() {
 865                     let meta = attr::mk_name_value_item_str(
 866                         Ident::with_dummy_span(sym::target_feature),
 867                         feat,
 868                         DUMMY_SP,
 869                     );
 870                     if let Ok(feat_cfg) = Cfg::parse(&meta) {
 871                         cfg &= feat_cfg;
 872                     }
 873                 }
 874             }
 875         }
 876
 877         if cfg == Cfg::True { None } else { Some(Arc::new(cfg)) }
 878     }
 879 }
 880
 881 crate trait NestedAttributesExt {
 882     /// Returns `true` if the attribute list contains a specific `Word`
 883     fn has_word(self, word: Symbol) -> bool;
 884     fn get_word_attr(self, word: Symbol) -> Option<ast::NestedMetaItem>;
 885 }
 886
 887 impl<I: Iterator<Item = ast::NestedMetaItem> + IntoIterator<Item = ast::NestedMetaItem>>
 888     NestedAttributesExt for I
 889 {
 890     fn has_word(self, word: Symbol) -> bool {
 891         self.into_iter().any(|attr| attr.is_word() && attr.has_name(word))
 892     }
 893
 894     fn get_word_attr(mut self, word: Symbol) -> Option<ast::NestedMetaItem> {
 895         self.find(|attr| attr.is_word() && attr.has_name(word))
 896     }
 897 }
 898
 899 /// A portion of documentation, extracted from a `#[doc]` attribute.
 900 ///
 901 /// Each variant contains the line number within the complete doc-comment where the fragment
 902 /// starts, as well as the Span where the corresponding doc comment or attribute is located.
 903 ///
 904 /// Included files are kept separate from inline doc comments so that proper line-number
 905 /// information can be given when a doctest fails. Sugared doc comments and "raw" doc comments are
 906 /// kept separate because of issue #42760.
 907 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 908 crate struct DocFragment {
 909     crate span: rustc_span::Span,
 910     /// The module this doc-comment came from.
 911     ///
 912     /// This allows distinguishing between the original documentation and a pub re-export.
 913     /// If it is `None`, the item was not re-exported.
 914     crate parent_module: Option<DefId>,
 915     crate doc: Symbol,
 916     crate kind: DocFragmentKind,
 917     crate indent: usize,
 918 }
 919
 920 // `DocFragment` is used a lot. Make sure it doesn't unintentionally get bigger.
 921 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
 922 rustc_data_structures::static_assert_size!(DocFragment, 32);
 923
 924 #[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
 925 crate enum DocFragmentKind {
 926     /// A doc fragment created from a `///` or `//!` doc comment.
 927     SugaredDoc,
 928     /// A doc fragment created from a "raw" `#[doc=""]` attribute.
 929     RawDoc,
 930 }
 931
 932 /// The goal of this function is to apply the `DocFragment` transformation that is required when
 933 /// transforming into the final Markdown, which is applying the computed indent to each line in
 934 /// each doc fragment (a `DocFragment` can contain multiple lines in case of `#[doc = ""]`).
 935 ///
 936 /// Note: remove the trailing newline where appropriate
 937 fn add_doc_fragment(out: &mut String, frag: &DocFragment) {
 938     let s = frag.doc.as_str();
 939     let mut iter = s.lines();
 940     if s == "" {
 941         out.push('\n');
 942         return;
 943     }
 944     while let Some(line) = iter.next() {
 945         if line.chars().any(|c| !c.is_whitespace()) {
 946             assert!(line.len() >= frag.indent);
 947             out.push_str(&line[frag.indent..]);
 948         } else {
 949             out.push_str(line);
 950         }
 951         out.push('\n');
 952     }
 953 }
 954
 955 /// Collapse a collection of [`DocFragment`]s into one string,
 956 /// handling indentation and newlines as needed.
 957 crate fn collapse_doc_fragments(doc_strings: &[DocFragment]) -> String {
 958     let mut acc = String::new();
 959     for frag in doc_strings {
 960         add_doc_fragment(&mut acc, frag);
 961     }
 962     acc.pop();
 963     acc
 964 }
 965
 966 /// A link that has not yet been rendered.
 967 ///
 968 /// This link will be turned into a rendered link by [`Item::links`].
 969 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 970 crate struct ItemLink {
 971     /// The original link written in the markdown
 972     pub(crate) link: String,
 973     /// The link text displayed in the HTML.
 974     ///
 975     /// This may not be the same as `link` if there was a disambiguator
 976     /// in an intra-doc link (e.g. \[`fn@f`\])
 977     pub(crate) link_text: String,
 978     pub(crate) did: DefId,
 979     /// The url fragment to append to the link
 980     pub(crate) fragment: Option<String>,
 981 }
 982
 983 pub struct RenderedLink {
 984     /// The text the link was original written as.
 985     ///
 986     /// This could potentially include disambiguators and backticks.
 987     pub(crate) original_text: String,
 988     /// The text to display in the HTML
 989     pub(crate) new_text: String,
 990     /// The URL to put in the `href`
 991     pub(crate) href: String,
 992 }
 993
 994 /// The attributes on an [`Item`], including attributes like `#[derive(...)]` and `#[inline]`,
 995 /// as well as doc comments.
 996 #[derive(Clone, Debug, Default)]
 997 crate struct Attributes {
 998     crate doc_strings: Vec<DocFragment>,
 999     crate other_attrs: Vec<ast::Attribute>,
1000 }
1001
1002 impl Attributes {
1003     crate fn lists(&self, name: Symbol) -> ListAttributesIter<'_> {
1004         self.other_attrs.lists(name)
1005     }
1006
1007     crate fn has_doc_flag(&self, flag: Symbol) -> bool {
1008         for attr in &self.other_attrs {
1009             if !attr.has_name(sym::doc) {
1010                 continue;
1011             }
1012
1013             if let Some(items) = attr.meta_item_list() {
1014                 if items.iter().filter_map(|i| i.meta_item()).any(|it| it.has_name(flag)) {
1015                     return true;
1016                 }
1017             }
1018         }
1019
1020         false
1021     }
1022
1023     crate fn from_ast(
1024         attrs: &[ast::Attribute],
1025         additional_attrs: Option<(&[ast::Attribute], DefId)>,
1026     ) -> Attributes {
1027         let mut doc_strings: Vec<DocFragment> = vec![];
1028         let clean_attr = |(attr, parent_module): (&ast::Attribute, Option<DefId>)| {
1029             if let Some(value) = attr.doc_str() {
1030                 trace!("got doc_str={:?}", value);
1031                 let value = beautify_doc_string(value);
1032                 let kind = if attr.is_doc_comment() {
1033                     DocFragmentKind::SugaredDoc
1034                 } else {
1035                     DocFragmentKind::RawDoc
1036                 };
1037
1038                 let frag =
1039                     DocFragment { span: attr.span, doc: value, kind, parent_module, indent: 0 };
1040
1041                 doc_strings.push(frag);
1042
1043                 None
1044             } else {
1045                 Some(attr.clone())
1046             }
1047         };
1048
1049         // Additional documentation should be shown before the original documentation
1050         let other_attrs = additional_attrs
1051             .into_iter()
1052             .map(|(attrs, id)| attrs.iter().map(move |attr| (attr, Some(id))))
1053             .flatten()
1054             .chain(attrs.iter().map(|attr| (attr, None)))
1055             .filter_map(clean_attr)
1056             .collect();
1057
1058         Attributes { doc_strings, other_attrs }
1059     }
1060
1061     /// Finds the `doc` attribute as a NameValue and returns the corresponding
1062     /// value found.
1063     crate fn doc_value(&self) -> Option<String> {
1064         let mut iter = self.doc_strings.iter();
1065
1066         let ori = iter.next()?;
1067         let mut out = String::new();
1068         add_doc_fragment(&mut out, ori);
1069         for new_frag in iter {
1070             if new_frag.kind != ori.kind || new_frag.parent_module != ori.parent_module {
1071                 break;
1072             }
1073             add_doc_fragment(&mut out, new_frag);
1074         }
1075         out.pop();
1076         if out.is_empty() { None } else { Some(out) }
1077     }
1078
1079     /// Return the doc-comments on this item, grouped by the module they came from.
1080     ///
1081     /// The module can be different if this is a re-export with added documentation.
1082     crate fn collapsed_doc_value_by_module_level(&self) -> FxHashMap<Option<DefId>, String> {
1083         let mut ret = FxHashMap::default();
1084         if self.doc_strings.len() == 0 {
1085             return ret;
1086         }
1087         let last_index = self.doc_strings.len() - 1;
1088
1089         for (i, new_frag) in self.doc_strings.iter().enumerate() {
1090             let out = ret.entry(new_frag.parent_module).or_default();
1091             add_doc_fragment(out, new_frag);
1092             if i == last_index {
1093                 out.pop();
1094             }
1095         }
1096         ret
1097     }
1098
1099     /// Finds all `doc` attributes as NameValues and returns their corresponding values, joined
1100     /// with newlines.
1101     crate fn collapsed_doc_value(&self) -> Option<String> {
1102         if self.doc_strings.is_empty() {
1103             None
1104         } else {
1105             Some(collapse_doc_fragments(&self.doc_strings))
1106         }
1107     }
1108
1109     crate fn get_doc_aliases(&self) -> Box<[Symbol]> {
1110         let mut aliases = FxHashSet::default();
1111
1112         for attr in self.other_attrs.lists(sym::doc).filter(|a| a.has_name(sym::alias)) {
1113             if let Some(values) = attr.meta_item_list() {
1114                 for l in values {
1115                     match l.literal().unwrap().kind {
1116                         ast::LitKind::Str(s, _) => {
1117                             aliases.insert(s);
1118                         }
1119                         _ => unreachable!(),
1120                     }
1121                 }
1122             } else {
1123                 aliases.insert(attr.value_str().unwrap());
1124             }
1125         }
1126         aliases.into_iter().collect::<Vec<_>>().into()
1127     }
1128 }
1129
1130 impl PartialEq for Attributes {
1131     fn eq(&self, rhs: &Self) -> bool {
1132         self.doc_strings == rhs.doc_strings
1133             && self
1134                 .other_attrs
1135                 .iter()
1136                 .map(|attr| attr.id)
1137                 .eq(rhs.other_attrs.iter().map(|attr| attr.id))
1138     }
1139 }
1140
1141 impl Eq for Attributes {}
1142
1143 impl Hash for Attributes {
1144     fn hash<H: Hasher>(&self, hasher: &mut H) {
1145         self.doc_strings.hash(hasher);
1146         for attr in &self.other_attrs {
1147             attr.id.hash(hasher);
1148         }
1149     }
1150 }
1151
1152 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1153 crate enum GenericBound {
1154     TraitBound(PolyTrait, hir::TraitBoundModifier),
1155     Outlives(Lifetime),
1156 }
1157
1158 impl GenericBound {
1159     crate fn maybe_sized(cx: &mut DocContext<'_>) -> GenericBound {
1160         let did = cx.tcx.require_lang_item(LangItem::Sized, None);
1161         let empty = cx.tcx.intern_substs(&[]);
1162         let path = external_path(cx, did, false, vec![], empty);
1163         inline::record_extern_fqn(cx, did, ItemType::Trait);
1164         GenericBound::TraitBound(
1165             PolyTrait { trait_: path, generic_params: Vec::new() },
1166             hir::TraitBoundModifier::Maybe,
1167         )
1168     }
1169
1170     crate fn is_sized_bound(&self, cx: &DocContext<'_>) -> bool {
1171         use rustc_hir::TraitBoundModifier as TBM;
1172         if let GenericBound::TraitBound(PolyTrait { ref trait_, .. }, TBM::None) = *self {
1173             if Some(trait_.def_id()) == cx.tcx.lang_items().sized_trait() {
1174                 return true;
1175             }
1176         }
1177         false
1178     }
1179
1180     crate fn get_poly_trait(&self) -> Option<PolyTrait> {
1181         if let GenericBound::TraitBound(ref p, _) = *self {
1182             return Some(p.clone());
1183         }
1184         None
1185     }
1186
1187     crate fn get_trait_path(&self) -> Option<Path> {
1188         if let GenericBound::TraitBound(PolyTrait { ref trait_, .. }, _) = *self {
1189             Some(trait_.clone())
1190         } else {
1191             None
1192         }
1193     }
1194 }
1195
1196 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1197 crate struct Lifetime(pub Symbol);
1198
1199 impl Lifetime {
1200     crate fn statik() -> Lifetime {
1201         Lifetime(kw::StaticLifetime)
1202     }
1203
1204     crate fn elided() -> Lifetime {
1205         Lifetime(kw::UnderscoreLifetime)
1206     }
1207 }
1208
1209 #[derive(Clone, Debug)]
1210 crate enum WherePredicate {
1211     BoundPredicate { ty: Type, bounds: Vec<GenericBound>, bound_params: Vec<Lifetime> },
1212     RegionPredicate { lifetime: Lifetime, bounds: Vec<GenericBound> },
1213     EqPredicate { lhs: Type, rhs: Type },
1214 }
1215
1216 impl WherePredicate {
1217     crate fn get_bounds(&self) -> Option<&[GenericBound]> {
1218         match *self {
1219             WherePredicate::BoundPredicate { ref bounds, .. } => Some(bounds),
1220             WherePredicate::RegionPredicate { ref bounds, .. } => Some(bounds),
1221             _ => None,
1222         }
1223     }
1224 }
1225
1226 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1227 crate enum GenericParamDefKind {
1228     Lifetime { outlives: Vec<Lifetime> },
1229     Type { did: DefId, bounds: Vec<GenericBound>, default: Option<Box<Type>>, synthetic: bool },
1230     Const { did: DefId, ty: Box<Type>, default: Option<Box<String>> },
1231 }
1232
1233 impl GenericParamDefKind {
1234     crate fn is_type(&self) -> bool {
1235         matches!(self, GenericParamDefKind::Type { .. })
1236     }
1237 }
1238
1239 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1240 crate struct GenericParamDef {
1241     crate name: Symbol,
1242     crate kind: GenericParamDefKind,
1243 }
1244
1245 // `GenericParamDef` is used in many places. Make sure it doesn't unintentionally get bigger.
1246 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
1247 rustc_data_structures::static_assert_size!(GenericParamDef, 56);
1248
1249 impl GenericParamDef {
1250     crate fn is_synthetic_type_param(&self) -> bool {
1251         match self.kind {
1252             GenericParamDefKind::Lifetime { .. } | GenericParamDefKind::Const { .. } => false,
1253             GenericParamDefKind::Type { synthetic, .. } => synthetic,
1254         }
1255     }
1256
1257     crate fn is_type(&self) -> bool {
1258         self.kind.is_type()
1259     }
1260
1261     crate fn get_bounds(&self) -> Option<&[GenericBound]> {
1262         match self.kind {
1263             GenericParamDefKind::Type { ref bounds, .. } => Some(bounds),
1264             _ => None,
1265         }
1266     }
1267 }
1268
1269 // maybe use a Generic enum and use Vec<Generic>?
1270 #[derive(Clone, Debug, Default)]
1271 crate struct Generics {
1272     crate params: Vec<GenericParamDef>,
1273     crate where_predicates: Vec<WherePredicate>,
1274 }
1275
1276 #[derive(Clone, Debug)]
1277 crate struct Function {
1278     crate decl: FnDecl,
1279     crate generics: Generics,
1280     crate header: hir::FnHeader,
1281 }
1282
1283 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1284 crate struct FnDecl {
1285     crate inputs: Arguments,
1286     crate output: FnRetTy,
1287     crate c_variadic: bool,
1288 }
1289
1290 impl FnDecl {
1291     crate fn self_type(&self) -> Option<SelfTy> {
1292         self.inputs.values.get(0).and_then(|v| v.to_self())
1293     }
1294
1295     /// Returns the sugared return type for an async function.
1296     ///
1297     /// For example, if the return type is `impl std::future::Future<Output = i32>`, this function
1298     /// will return `i32`.
1299     ///
1300     /// # Panics
1301     ///
1302     /// This function will panic if the return type does not match the expected sugaring for async
1303     /// functions.
1304     crate fn sugared_async_return_type(&self) -> FnRetTy {
1305         match &self.output {
1306             FnRetTy::Return(Type::ImplTrait(bounds)) => match &bounds[0] {
1307                 GenericBound::TraitBound(PolyTrait { trait_, .. }, ..) => {
1308                     let bindings = trait_.bindings().unwrap();
1309                     FnRetTy::Return(bindings[0].ty().clone())
1310                 }
1311                 _ => panic!("unexpected desugaring of async function"),
1312             },
1313             _ => panic!("unexpected desugaring of async function"),
1314         }
1315     }
1316 }
1317
1318 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1319 crate struct Arguments {
1320     crate values: Vec<Argument>,
1321 }
1322
1323 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1324 crate struct Argument {
1325     crate type_: Type,
1326     crate name: Symbol,
1327     /// This field is used to represent "const" arguments from the `rustc_legacy_const_generics`
1328     /// feature. More information in <https://github.com/rust-lang/rust/issues/83167>.
1329     crate is_const: bool,
1330 }
1331
1332 #[derive(Clone, PartialEq, Debug)]
1333 crate enum SelfTy {
1334     SelfValue,
1335     SelfBorrowed(Option<Lifetime>, Mutability),
1336     SelfExplicit(Type),
1337 }
1338
1339 impl Argument {
1340     crate fn to_self(&self) -> Option<SelfTy> {
1341         if self.name != kw::SelfLower {
1342             return None;
1343         }
1344         if self.type_.is_self_type() {
1345             return Some(SelfValue);
1346         }
1347         match self.type_ {
1348             BorrowedRef { ref lifetime, mutability, ref type_ } if type_.is_self_type() => {
1349                 Some(SelfBorrowed(lifetime.clone(), mutability))
1350             }
1351             _ => Some(SelfExplicit(self.type_.clone())),
1352         }
1353     }
1354 }
1355
1356 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1357 crate enum FnRetTy {
1358     Return(Type),
1359     DefaultReturn,
1360 }
1361
1362 impl FnRetTy {
1363     crate fn as_return(&self) -> Option<&Type> {
1364         match self {
1365             Return(ret) => Some(ret),
1366             DefaultReturn => None,
1367         }
1368     }
1369 }
1370
1371 #[derive(Clone, Debug)]
1372 crate struct Trait {
1373     crate unsafety: hir::Unsafety,
1374     crate items: Vec<Item>,
1375     crate generics: Generics,
1376     crate bounds: Vec<GenericBound>,
1377     crate is_auto: bool,
1378 }
1379
1380 #[derive(Clone, Debug)]
1381 crate struct TraitAlias {
1382     crate generics: Generics,
1383     crate bounds: Vec<GenericBound>,
1384 }
1385
1386 /// A trait reference, which may have higher ranked lifetimes.
1387 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1388 crate struct PolyTrait {
1389     crate trait_: Path,
1390     crate generic_params: Vec<GenericParamDef>,
1391 }
1392
1393 /// Rustdoc's representation of types, mostly based on the [`hir::Ty`].
1394 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1395 crate enum Type {
1396     /// A named type, which could be a trait.
1397     ///
1398     /// This is mostly Rustdoc's version of [`hir::Path`].
1399     /// It has to be different because Rustdoc's [`PathSegment`] can contain cleaned generics.
1400     Path { path: Path },
1401     /// A `dyn Trait` object: `dyn for<'a> Trait<'a> + Send + 'static`
1402     DynTrait(Vec<PolyTrait>, Option<Lifetime>),
1403     /// A type parameter.
1404     Generic(Symbol),
1405     /// A primitive (aka, builtin) type.
1406     Primitive(PrimitiveType),
1407     /// A function pointer: `extern "ABI" fn(...) -> ...`
1408     BareFunction(Box<BareFunctionDecl>),
1409     /// A tuple type: `(i32, &str)`.
1410     Tuple(Vec<Type>),
1411     /// A slice type (does *not* include the `&`): `[i32]`
1412     Slice(Box<Type>),
1413     /// An array type.
1414     ///
1415     /// The `String` field is a stringified version of the array's length parameter.
1416     Array(Box<Type>, String),
1417     /// A raw pointer type: `*const i32`, `*mut i32`
1418     RawPointer(Mutability, Box<Type>),
1419     /// A reference type: `&i32`, `&'a mut Foo`
1420     BorrowedRef { lifetime: Option<Lifetime>, mutability: Mutability, type_: Box<Type> },
1421
1422     /// A qualified path to an associated item: `<Type as Trait>::Name`
1423     QPath {
1424         name: Symbol,
1425         self_type: Box<Type>,
1426         /// FIXME: This is a hack that should be removed; see [this discussion][1].
1427         ///
1428         /// [1]: https://github.com/rust-lang/rust/pull/85479#discussion_r635729093
1429         self_def_id: Option<DefId>,
1430         trait_: Path,
1431     },
1432
1433     /// A type that is inferred: `_`
1434     Infer,
1435
1436     /// An `impl Trait`: `impl TraitA + TraitB + ...`
1437     ImplTrait(Vec<GenericBound>),
1438 }
1439
1440 // `Type` is used a lot. Make sure it doesn't unintentionally get bigger.
1441 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
1442 rustc_data_structures::static_assert_size!(Type, 72);
1443
1444 impl Type {
1445     /// When comparing types for equality, it can help to ignore `&` wrapping.
1446     crate fn without_borrowed_ref(&self) -> &Type {
1447         let mut result = self;
1448         while let Type::BorrowedRef { type_, .. } = result {
1449             result = &*type_;
1450         }
1451         result
1452     }
1453
1454     /// Check if two types are "potentially the same".
1455     /// This is different from `Eq`, because it knows that things like
1456     /// `Placeholder` are possible matches for everything.
1457     crate fn is_same(&self, other: &Self, cache: &Cache) -> bool {
1458         match (self, other) {
1459             // Recursive cases.
1460             (Type::Tuple(a), Type::Tuple(b)) => {
1461                 a.len() == b.len() && a.iter().zip(b).all(|(a, b)| a.is_same(&b, cache))
1462             }
1463             (Type::Slice(a), Type::Slice(b)) => a.is_same(&b, cache),
1464             (Type::Array(a, al), Type::Array(b, bl)) => al == bl && a.is_same(&b, cache),
1465             (Type::RawPointer(mutability, type_), Type::RawPointer(b_mutability, b_type_)) => {
1466                 mutability == b_mutability && type_.is_same(&b_type_, cache)
1467             }
1468             (
1469                 Type::BorrowedRef { mutability, type_, .. },
1470                 Type::BorrowedRef { mutability: b_mutability, type_: b_type_, .. },
1471             ) => mutability == b_mutability && type_.is_same(&b_type_, cache),
1472             // Placeholders and generics are equal to all other types.
1473             (Type::Infer, _) | (_, Type::Infer) => true,
1474             (Type::Generic(_), _) | (_, Type::Generic(_)) => true,
1475             // Other cases, such as primitives, just use recursion.
1476             (a, b) => a
1477                 .def_id(cache)
1478                 .and_then(|a| Some((a, b.def_id(cache)?)))
1479                 .map(|(a, b)| a == b)
1480                 .unwrap_or(false),
1481         }
1482     }
1483
1484     crate fn primitive_type(&self) -> Option<PrimitiveType> {
1485         match *self {
1486             Primitive(p) | BorrowedRef { type_: box Primitive(p), .. } => Some(p),
1487             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
1488             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
1489             Tuple(ref tys) => {
1490                 if tys.is_empty() {
1491                     Some(PrimitiveType::Unit)
1492                 } else {
1493                     Some(PrimitiveType::Tuple)
1494                 }
1495             }
1496             RawPointer(..) => Some(PrimitiveType::RawPointer),
1497             BareFunction(..) => Some(PrimitiveType::Fn),
1498             _ => None,
1499         }
1500     }
1501
1502     /// Checks if this is a `T::Name` path for an associated type.
1503     crate fn is_assoc_ty(&self) -> bool {
1504         match self {
1505             Type::Path { path, .. } => path.is_assoc_ty(),
1506             _ => false,
1507         }
1508     }
1509
1510     crate fn is_self_type(&self) -> bool {
1511         match *self {
1512             Generic(name) => name == kw::SelfUpper,
1513             _ => false,
1514         }
1515     }
1516
1517     crate fn generics(&self) -> Option<Vec<&Type>> {
1518         match self {
1519             Type::Path { path, .. } => path.generics(),
1520             _ => None,
1521         }
1522     }
1523
1524     crate fn is_full_generic(&self) -> bool {
1525         matches!(self, Type::Generic(_))
1526     }
1527
1528     crate fn is_primitive(&self) -> bool {
1529         self.primitive_type().is_some()
1530     }
1531
1532     crate fn projection(&self) -> Option<(&Type, DefId, Symbol)> {
1533         let (self_, trait_, name) = match self {
1534             QPath { self_type, trait_, name, .. } => (self_type, trait_, name),
1535             _ => return None,
1536         };
1537         Some((&self_, trait_.def_id(), *name))
1538     }
1539
1540     fn inner_def_id(&self, cache: Option<&Cache>) -> Option<DefId> {
1541         let t: PrimitiveType = match *self {
1542             Type::Path { ref path } => return Some(path.def_id()),
1543             DynTrait(ref bounds, _) => return Some(bounds[0].trait_.def_id()),
1544             Primitive(p) => return cache.and_then(|c| c.primitive_locations.get(&p).cloned()),
1545             BorrowedRef { type_: box Generic(..), .. } => PrimitiveType::Reference,
1546             BorrowedRef { ref type_, .. } => return type_.inner_def_id(cache),
1547             Tuple(ref tys) => {
1548                 if tys.is_empty() {
1549                     PrimitiveType::Unit
1550                 } else {
1551                     PrimitiveType::Tuple
1552                 }
1553             }
1554             BareFunction(..) => PrimitiveType::Fn,
1555             Slice(..) => PrimitiveType::Slice,
1556             Array(..) => PrimitiveType::Array,
1557             RawPointer(..) => PrimitiveType::RawPointer,
1558             QPath { ref self_type, .. } => return self_type.inner_def_id(cache),
1559             Generic(_) | Infer | ImplTrait(_) => return None,
1560         };
1561         cache.and_then(|c| Primitive(t).def_id(c))
1562     }
1563
1564     /// Use this method to get the [DefId] of a [clean] AST node, including [PrimitiveType]s.
1565     ///
1566     /// See [`Self::def_id_no_primitives`] for more.
1567     ///
1568     /// [clean]: crate::clean
1569     crate fn def_id(&self, cache: &Cache) -> Option<DefId> {
1570         self.inner_def_id(Some(cache))
1571     }
1572
1573     /// Use this method to get the [`DefId`] of a [`clean`] AST node.
1574     /// This will return [`None`] when called on a primitive [`clean::Type`].
1575     /// Use [`Self::def_id`] if you want to include primitives.
1576     ///
1577     /// [`clean`]: crate::clean
1578     /// [`clean::Type`]: crate::clean::Type
1579     // FIXME: get rid of this function and always use `def_id`
1580     crate fn def_id_no_primitives(&self) -> Option<DefId> {
1581         self.inner_def_id(None)
1582     }
1583 }
1584
1585 /// A primitive (aka, builtin) type.
1586 ///
1587 /// This represents things like `i32`, `str`, etc.
1588 ///
1589 /// N.B. This has to be different from [`hir::PrimTy`] because it also includes types that aren't
1590 /// paths, like [`Self::Unit`].
1591 #[derive(Clone, PartialEq, Eq, Hash, Copy, Debug)]
1592 crate enum PrimitiveType {
1593     Isize,
1594     I8,
1595     I16,
1596     I32,
1597     I64,
1598     I128,
1599     Usize,
1600     U8,
1601     U16,
1602     U32,
1603     U64,
1604     U128,
1605     F32,
1606     F64,
1607     Char,
1608     Bool,
1609     Str,
1610     Slice,
1611     Array,
1612     Tuple,
1613     Unit,
1614     RawPointer,
1615     Reference,
1616     Fn,
1617     Never,
1618 }
1619
1620 impl PrimitiveType {
1621     crate fn from_hir(prim: hir::PrimTy) -> PrimitiveType {
1622         use ast::{FloatTy, IntTy, UintTy};
1623         match prim {
1624             hir::PrimTy::Int(IntTy::Isize) => PrimitiveType::Isize,
1625             hir::PrimTy::Int(IntTy::I8) => PrimitiveType::I8,
1626             hir::PrimTy::Int(IntTy::I16) => PrimitiveType::I16,
1627             hir::PrimTy::Int(IntTy::I32) => PrimitiveType::I32,
1628             hir::PrimTy::Int(IntTy::I64) => PrimitiveType::I64,
1629             hir::PrimTy::Int(IntTy::I128) => PrimitiveType::I128,
1630             hir::PrimTy::Uint(UintTy::Usize) => PrimitiveType::Usize,
1631             hir::PrimTy::Uint(UintTy::U8) => PrimitiveType::U8,
1632             hir::PrimTy::Uint(UintTy::U16) => PrimitiveType::U16,
1633             hir::PrimTy::Uint(UintTy::U32) => PrimitiveType::U32,
1634             hir::PrimTy::Uint(UintTy::U64) => PrimitiveType::U64,
1635             hir::PrimTy::Uint(UintTy::U128) => PrimitiveType::U128,
1636             hir::PrimTy::Float(FloatTy::F32) => PrimitiveType::F32,
1637             hir::PrimTy::Float(FloatTy::F64) => PrimitiveType::F64,
1638             hir::PrimTy::Str => PrimitiveType::Str,
1639             hir::PrimTy::Bool => PrimitiveType::Bool,
1640             hir::PrimTy::Char => PrimitiveType::Char,
1641         }
1642     }
1643
1644     crate fn from_symbol(s: Symbol) -> Option<PrimitiveType> {
1645         match s {
1646             sym::isize => Some(PrimitiveType::Isize),
1647             sym::i8 => Some(PrimitiveType::I8),
1648             sym::i16 => Some(PrimitiveType::I16),
1649             sym::i32 => Some(PrimitiveType::I32),
1650             sym::i64 => Some(PrimitiveType::I64),
1651             sym::i128 => Some(PrimitiveType::I128),
1652             sym::usize => Some(PrimitiveType::Usize),
1653             sym::u8 => Some(PrimitiveType::U8),
1654             sym::u16 => Some(PrimitiveType::U16),
1655             sym::u32 => Some(PrimitiveType::U32),
1656             sym::u64 => Some(PrimitiveType::U64),
1657             sym::u128 => Some(PrimitiveType::U128),
1658             sym::bool => Some(PrimitiveType::Bool),
1659             sym::char => Some(PrimitiveType::Char),
1660             sym::str => Some(PrimitiveType::Str),
1661             sym::f32 => Some(PrimitiveType::F32),
1662             sym::f64 => Some(PrimitiveType::F64),
1663             sym::array => Some(PrimitiveType::Array),
1664             sym::slice => Some(PrimitiveType::Slice),
1665             sym::tuple => Some(PrimitiveType::Tuple),
1666             sym::unit => Some(PrimitiveType::Unit),
1667             sym::pointer => Some(PrimitiveType::RawPointer),
1668             sym::reference => Some(PrimitiveType::Reference),
1669             kw::Fn => Some(PrimitiveType::Fn),
1670             sym::never => Some(PrimitiveType::Never),
1671             _ => None,
1672         }
1673     }
1674
1675     crate fn impls(&self, tcx: TyCtxt<'_>) -> &'static ArrayVec<DefId, 4> {
1676         Self::all_impls(tcx).get(self).expect("missing impl for primitive type")
1677     }
1678
1679     crate fn all_impls(tcx: TyCtxt<'_>) -> &'static FxHashMap<PrimitiveType, ArrayVec<DefId, 4>> {
1680         static CELL: OnceCell<FxHashMap<PrimitiveType, ArrayVec<DefId, 4>>> = OnceCell::new();
1681
1682         CELL.get_or_init(move || {
1683             use self::PrimitiveType::*;
1684
1685             let single = |a: Option<DefId>| a.into_iter().collect();
1686             let both = |a: Option<DefId>, b: Option<DefId>| -> ArrayVec<_, 4> {
1687                 a.into_iter().chain(b).collect()
1688             };
1689
1690             let lang_items = tcx.lang_items();
1691             map! {
1692                 Isize => single(lang_items.isize_impl()),
1693                 I8 => single(lang_items.i8_impl()),
1694                 I16 => single(lang_items.i16_impl()),
1695                 I32 => single(lang_items.i32_impl()),
1696                 I64 => single(lang_items.i64_impl()),
1697                 I128 => single(lang_items.i128_impl()),
1698                 Usize => single(lang_items.usize_impl()),
1699                 U8 => single(lang_items.u8_impl()),
1700                 U16 => single(lang_items.u16_impl()),
1701                 U32 => single(lang_items.u32_impl()),
1702                 U64 => single(lang_items.u64_impl()),
1703                 U128 => single(lang_items.u128_impl()),
1704                 F32 => both(lang_items.f32_impl(), lang_items.f32_runtime_impl()),
1705                 F64 => both(lang_items.f64_impl(), lang_items.f64_runtime_impl()),
1706                 Char => single(lang_items.char_impl()),
1707                 Bool => single(lang_items.bool_impl()),
1708                 Str => both(lang_items.str_impl(), lang_items.str_alloc_impl()),
1709                 Slice => {
1710                     lang_items
1711                         .slice_impl()
1712                         .into_iter()
1713                         .chain(lang_items.slice_u8_impl())
1714                         .chain(lang_items.slice_alloc_impl())
1715                         .chain(lang_items.slice_u8_alloc_impl())
1716                         .collect()
1717                 },
1718                 Array => single(lang_items.array_impl()),
1719                 Tuple => ArrayVec::new(),
1720                 Unit => ArrayVec::new(),
1721                 RawPointer => {
1722                     lang_items
1723                         .const_ptr_impl()
1724                         .into_iter()
1725                         .chain(lang_items.mut_ptr_impl())
1726                         .chain(lang_items.const_slice_ptr_impl())
1727                         .chain(lang_items.mut_slice_ptr_impl())
1728                         .collect()
1729                 },
1730                 Reference => ArrayVec::new(),
1731                 Fn => ArrayVec::new(),
1732                 Never => ArrayVec::new(),
1733             }
1734         })
1735     }
1736
1737     crate fn as_sym(&self) -> Symbol {
1738         use PrimitiveType::*;
1739         match self {
1740             Isize => sym::isize,
1741             I8 => sym::i8,
1742             I16 => sym::i16,
1743             I32 => sym::i32,
1744             I64 => sym::i64,
1745             I128 => sym::i128,
1746             Usize => sym::usize,
1747             U8 => sym::u8,
1748             U16 => sym::u16,
1749             U32 => sym::u32,
1750             U64 => sym::u64,
1751             U128 => sym::u128,
1752             F32 => sym::f32,
1753             F64 => sym::f64,
1754             Str => sym::str,
1755             Bool => sym::bool,
1756             Char => sym::char,
1757             Array => sym::array,
1758             Slice => sym::slice,
1759             Tuple => sym::tuple,
1760             Unit => sym::unit,
1761             RawPointer => sym::pointer,
1762             Reference => sym::reference,
1763             Fn => kw::Fn,
1764             Never => sym::never,
1765         }
1766     }
1767
1768     /// Returns the DefId of the module with `doc(primitive)` for this primitive type.
1769     /// Panics if there is no such module.
1770     ///
1771     /// This gives precedence to primitives defined in the current crate, and deprioritizes primitives defined in `core`,
1772     /// but otherwise, if multiple crates define the same primitive, there is no guarantee of which will be picked.
1773     /// In particular, if a crate depends on both `std` and another crate that also defines `doc(primitive)`, then
1774     /// it's entirely random whether `std` or the other crate is picked. (no_std crates are usually fine unless multiple dependencies define a primitive.)
1775     crate fn primitive_locations(tcx: TyCtxt<'_>) -> &FxHashMap<PrimitiveType, DefId> {
1776         static PRIMITIVE_LOCATIONS: OnceCell<FxHashMap<PrimitiveType, DefId>> = OnceCell::new();
1777         PRIMITIVE_LOCATIONS.get_or_init(|| {
1778             let mut primitive_locations = FxHashMap::default();
1779             // NOTE: technically this misses crates that are only passed with `--extern` and not loaded when checking the crate.
1780             // This is a degenerate case that I don't plan to support.
1781             for &crate_num in tcx.crates(()) {
1782                 let e = ExternalCrate { crate_num };
1783                 let crate_name = e.name(tcx);
1784                 debug!(?crate_num, ?crate_name);
1785                 for &(def_id, prim) in &e.primitives(tcx) {
1786                     // HACK: try to link to std instead where possible
1787                     if crate_name == sym::core && primitive_locations.contains_key(&prim) {
1788                         continue;
1789                     }
1790                     primitive_locations.insert(prim, def_id);
1791                 }
1792             }
1793             let local_primitives = ExternalCrate { crate_num: LOCAL_CRATE }.primitives(tcx);
1794             for (def_id, prim) in local_primitives {
1795                 primitive_locations.insert(prim, def_id);
1796             }
1797             primitive_locations
1798         })
1799     }
1800 }
1801
1802 impl From<ast::IntTy> for PrimitiveType {
1803     fn from(int_ty: ast::IntTy) -> PrimitiveType {
1804         match int_ty {
1805             ast::IntTy::Isize => PrimitiveType::Isize,
1806             ast::IntTy::I8 => PrimitiveType::I8,
1807             ast::IntTy::I16 => PrimitiveType::I16,
1808             ast::IntTy::I32 => PrimitiveType::I32,
1809             ast::IntTy::I64 => PrimitiveType::I64,
1810             ast::IntTy::I128 => PrimitiveType::I128,
1811         }
1812     }
1813 }
1814
1815 impl From<ast::UintTy> for PrimitiveType {
1816     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
1817         match uint_ty {
1818             ast::UintTy::Usize => PrimitiveType::Usize,
1819             ast::UintTy::U8 => PrimitiveType::U8,
1820             ast::UintTy::U16 => PrimitiveType::U16,
1821             ast::UintTy::U32 => PrimitiveType::U32,
1822             ast::UintTy::U64 => PrimitiveType::U64,
1823             ast::UintTy::U128 => PrimitiveType::U128,
1824         }
1825     }
1826 }
1827
1828 impl From<ast::FloatTy> for PrimitiveType {
1829     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
1830         match float_ty {
1831             ast::FloatTy::F32 => PrimitiveType::F32,
1832             ast::FloatTy::F64 => PrimitiveType::F64,
1833         }
1834     }
1835 }
1836
1837 impl From<ty::IntTy> for PrimitiveType {
1838     fn from(int_ty: ty::IntTy) -> PrimitiveType {
1839         match int_ty {
1840             ty::IntTy::Isize => PrimitiveType::Isize,
1841             ty::IntTy::I8 => PrimitiveType::I8,
1842             ty::IntTy::I16 => PrimitiveType::I16,
1843             ty::IntTy::I32 => PrimitiveType::I32,
1844             ty::IntTy::I64 => PrimitiveType::I64,
1845             ty::IntTy::I128 => PrimitiveType::I128,
1846         }
1847     }
1848 }
1849
1850 impl From<ty::UintTy> for PrimitiveType {
1851     fn from(uint_ty: ty::UintTy) -> PrimitiveType {
1852         match uint_ty {
1853             ty::UintTy::Usize => PrimitiveType::Usize,
1854             ty::UintTy::U8 => PrimitiveType::U8,
1855             ty::UintTy::U16 => PrimitiveType::U16,
1856             ty::UintTy::U32 => PrimitiveType::U32,
1857             ty::UintTy::U64 => PrimitiveType::U64,
1858             ty::UintTy::U128 => PrimitiveType::U128,
1859         }
1860     }
1861 }
1862
1863 impl From<ty::FloatTy> for PrimitiveType {
1864     fn from(float_ty: ty::FloatTy) -> PrimitiveType {
1865         match float_ty {
1866             ty::FloatTy::F32 => PrimitiveType::F32,
1867             ty::FloatTy::F64 => PrimitiveType::F64,
1868         }
1869     }
1870 }
1871
1872 impl From<hir::PrimTy> for PrimitiveType {
1873     fn from(prim_ty: hir::PrimTy) -> PrimitiveType {
1874         match prim_ty {
1875             hir::PrimTy::Int(int_ty) => int_ty.into(),
1876             hir::PrimTy::Uint(uint_ty) => uint_ty.into(),
1877             hir::PrimTy::Float(float_ty) => float_ty.into(),
1878             hir::PrimTy::Str => PrimitiveType::Str,
1879             hir::PrimTy::Bool => PrimitiveType::Bool,
1880             hir::PrimTy::Char => PrimitiveType::Char,
1881         }
1882     }
1883 }
1884
1885 #[derive(Copy, Clone, Debug)]
1886 crate enum Visibility {
1887     /// `pub`
1888     Public,
1889     /// Visibility inherited from parent.
1890     ///
1891     /// For example, this is the visibility of private items and of enum variants.
1892     Inherited,
1893     /// `pub(crate)`, `pub(super)`, or `pub(in path::to::somewhere)`
1894     Restricted(DefId),
1895 }
1896
1897 impl Visibility {
1898     crate fn is_public(&self) -> bool {
1899         matches!(self, Visibility::Public)
1900     }
1901 }
1902
1903 #[derive(Clone, Debug)]
1904 crate struct Struct {
1905     crate struct_type: CtorKind,
1906     crate generics: Generics,
1907     crate fields: Vec<Item>,
1908     crate fields_stripped: bool,
1909 }
1910
1911 #[derive(Clone, Debug)]
1912 crate struct Union {
1913     crate generics: Generics,
1914     crate fields: Vec<Item>,
1915     crate fields_stripped: bool,
1916 }
1917
1918 /// This is a more limited form of the standard Struct, different in that
1919 /// it lacks the things most items have (name, id, parameterization). Found
1920 /// only as a variant in an enum.
1921 #[derive(Clone, Debug)]
1922 crate struct VariantStruct {
1923     crate struct_type: CtorKind,
1924     crate fields: Vec<Item>,
1925     crate fields_stripped: bool,
1926 }
1927
1928 #[derive(Clone, Debug)]
1929 crate struct Enum {
1930     crate variants: IndexVec<VariantIdx, Item>,
1931     crate generics: Generics,
1932     crate variants_stripped: bool,
1933 }
1934
1935 #[derive(Clone, Debug)]
1936 crate enum Variant {
1937     CLike,
1938     Tuple(Vec<Item>),
1939     Struct(VariantStruct),
1940 }
1941
1942 /// Small wrapper around [`rustc_span::Span`] that adds helper methods
1943 /// and enforces calling [`rustc_span::Span::source_callsite()`].
1944 #[derive(Copy, Clone, Debug)]
1945 crate struct Span(rustc_span::Span);
1946
1947 impl Span {
1948     /// Wraps a [`rustc_span::Span`]. In case this span is the result of a macro expansion, the
1949     /// span will be updated to point to the macro invocation instead of the macro definition.
1950     ///
1951     /// (See rust-lang/rust#39726)
1952     crate fn new(sp: rustc_span::Span) -> Self {
1953         Self(sp.source_callsite())
1954     }
1955
1956     crate fn inner(&self) -> rustc_span::Span {
1957         self.0
1958     }
1959
1960     crate fn dummy() -> Self {
1961         Self(rustc_span::DUMMY_SP)
1962     }
1963
1964     crate fn is_dummy(&self) -> bool {
1965         self.0.is_dummy()
1966     }
1967
1968     crate fn filename(&self, sess: &Session) -> FileName {
1969         sess.source_map().span_to_filename(self.0)
1970     }
1971
1972     crate fn lo(&self, sess: &Session) -> Loc {
1973         sess.source_map().lookup_char_pos(self.0.lo())
1974     }
1975
1976     crate fn hi(&self, sess: &Session) -> Loc {
1977         sess.source_map().lookup_char_pos(self.0.hi())
1978     }
1979
1980     crate fn cnum(&self, sess: &Session) -> CrateNum {
1981         // FIXME: is there a time when the lo and hi crate would be different?
1982         self.lo(sess).file.cnum
1983     }
1984 }
1985
1986 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1987 crate struct Path {
1988     crate res: Res,
1989     crate segments: Vec<PathSegment>,
1990 }
1991
1992 impl Path {
1993     crate fn def_id(&self) -> DefId {
1994         self.res.def_id()
1995     }
1996
1997     crate fn last(&self) -> Symbol {
1998         self.segments.last().expect("segments were empty").name
1999     }
2000
2001     crate fn whole_name(&self) -> String {
2002         self.segments
2003             .iter()
2004             .map(|s| if s.name == kw::PathRoot { String::new() } else { s.name.to_string() })
2005             .intersperse("::".into())
2006             .collect()
2007     }
2008
2009     /// Checks if this is a `T::Name` path for an associated type.
2010     crate fn is_assoc_ty(&self) -> bool {
2011         match self.res {
2012             Res::SelfTy(..) if self.segments.len() != 1 => true,
2013             Res::Def(DefKind::TyParam, _) if self.segments.len() != 1 => true,
2014             Res::Def(DefKind::AssocTy, _) => true,
2015             _ => false,
2016         }
2017     }
2018
2019     crate fn generics(&self) -> Option<Vec<&Type>> {
2020         self.segments.last().and_then(|seg| {
2021             if let GenericArgs::AngleBracketed { ref args, .. } = seg.args {
2022                 Some(
2023                     args.iter()
2024                         .filter_map(|arg| match arg {
2025                             GenericArg::Type(ty) => Some(ty),
2026                             _ => None,
2027                         })
2028                         .collect(),
2029                 )
2030             } else {
2031                 None
2032             }
2033         })
2034     }
2035
2036     crate fn bindings(&self) -> Option<&[TypeBinding]> {
2037         self.segments.last().and_then(|seg| {
2038             if let GenericArgs::AngleBracketed { ref bindings, .. } = seg.args {
2039                 Some(&**bindings)
2040             } else {
2041                 None
2042             }
2043         })
2044     }
2045 }
2046
2047 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2048 crate enum GenericArg {
2049     Lifetime(Lifetime),
2050     Type(Type),
2051     Const(Box<Constant>),
2052     Infer,
2053 }
2054
2055 // `GenericArg` can occur many times in a single `Path`, so make sure it
2056 // doesn't increase in size unexpectedly.
2057 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
2058 rustc_data_structures::static_assert_size!(GenericArg, 80);
2059
2060 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2061 crate enum GenericArgs {
2062     AngleBracketed { args: Vec<GenericArg>, bindings: Vec<TypeBinding> },
2063     Parenthesized { inputs: Vec<Type>, output: Option<Box<Type>> },
2064 }
2065
2066 // `GenericArgs` is in every `PathSegment`, so its size can significantly
2067 // affect rustdoc's memory usage.
2068 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
2069 rustc_data_structures::static_assert_size!(GenericArgs, 56);
2070
2071 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2072 crate struct PathSegment {
2073     crate name: Symbol,
2074     crate args: GenericArgs,
2075 }
2076
2077 // `PathSegment` usually occurs multiple times in every `Path`, so its size can
2078 // significantly affect rustdoc's memory usage.
2079 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
2080 rustc_data_structures::static_assert_size!(PathSegment, 64);
2081
2082 #[derive(Clone, Debug)]
2083 crate struct Typedef {
2084     crate type_: Type,
2085     crate generics: Generics,
2086     /// `type_` can come from either the HIR or from metadata. If it comes from HIR, it may be a type
2087     /// alias instead of the final type. This will always have the final type, regardless of whether
2088     /// `type_` came from HIR or from metadata.
2089     ///
2090     /// If `item_type.is_none()`, `type_` is guarenteed to come from metadata (and therefore hold the
2091     /// final type).
2092     crate item_type: Option<Type>,
2093 }
2094
2095 #[derive(Clone, Debug)]
2096 crate struct OpaqueTy {
2097     crate bounds: Vec<GenericBound>,
2098     crate generics: Generics,
2099 }
2100
2101 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2102 crate struct BareFunctionDecl {
2103     crate unsafety: hir::Unsafety,
2104     crate generic_params: Vec<GenericParamDef>,
2105     crate decl: FnDecl,
2106     crate abi: Abi,
2107 }
2108
2109 #[derive(Clone, Debug)]
2110 crate struct Static {
2111     crate type_: Type,
2112     crate mutability: Mutability,
2113     crate expr: Option<BodyId>,
2114 }
2115
2116 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
2117 crate struct Constant {
2118     crate type_: Type,
2119     crate kind: ConstantKind,
2120 }
2121
2122 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
2123 crate enum ConstantKind {
2124     /// This is the wrapper around `ty::Const` for a non-local constant. Because it doesn't have a
2125     /// `BodyId`, we need to handle it on its own.
2126     ///
2127     /// Note that `ty::Const` includes generic parameters, and may not always be uniquely identified
2128     /// by a DefId. So this field must be different from `Extern`.
2129     TyConst { expr: String },
2130     /// A constant (expression) that's not an item or associated item. These are usually found
2131     /// nested inside types (e.g., array lengths) or expressions (e.g., repeat counts), and also
2132     /// used to define explicit discriminant values for enum variants.
2133     Anonymous { body: BodyId },
2134     /// A constant from a different crate.
2135     Extern { def_id: DefId },
2136     /// `const FOO: u32 = ...;`
2137     Local { def_id: DefId, body: BodyId },
2138 }
2139
2140 impl Constant {
2141     crate fn expr(&self, tcx: TyCtxt<'_>) -> String {
2142         self.kind.expr(tcx)
2143     }
2144
2145     crate fn value(&self, tcx: TyCtxt<'_>) -> Option<String> {
2146         self.kind.value(tcx)
2147     }
2148
2149     crate fn is_literal(&self, tcx: TyCtxt<'_>) -> bool {
2150         self.kind.is_literal(tcx)
2151     }
2152 }
2153
2154 impl ConstantKind {
2155     crate fn expr(&self, tcx: TyCtxt<'_>) -> String {
2156         match *self {
2157             ConstantKind::TyConst { ref expr } => expr.clone(),
2158             ConstantKind::Extern { def_id } => print_inlined_const(tcx, def_id),
2159             ConstantKind::Local { body, .. } | ConstantKind::Anonymous { body } => {
2160                 print_const_expr(tcx, body)
2161             }
2162         }
2163     }
2164
2165     crate fn value(&self, tcx: TyCtxt<'_>) -> Option<String> {
2166         match *self {
2167             ConstantKind::TyConst { .. } | ConstantKind::Anonymous { .. } => None,
2168             ConstantKind::Extern { def_id } | ConstantKind::Local { def_id, .. } => {
2169                 print_evaluated_const(tcx, def_id)
2170             }
2171         }
2172     }
2173
2174     crate fn is_literal(&self, tcx: TyCtxt<'_>) -> bool {
2175         match *self {
2176             ConstantKind::TyConst { .. } => false,
2177             ConstantKind::Extern { def_id } => def_id.as_local().map_or(false, |def_id| {
2178                 is_literal_expr(tcx, tcx.hir().local_def_id_to_hir_id(def_id))
2179             }),
2180             ConstantKind::Local { body, .. } | ConstantKind::Anonymous { body } => {
2181                 is_literal_expr(tcx, body.hir_id)
2182             }
2183         }
2184     }
2185 }
2186
2187 #[derive(Clone, Debug)]
2188 crate struct Impl {
2189     crate unsafety: hir::Unsafety,
2190     crate generics: Generics,
2191     crate trait_: Option<Path>,
2192     crate for_: Type,
2193     crate items: Vec<Item>,
2194     crate polarity: ty::ImplPolarity,
2195     crate kind: ImplKind,
2196 }
2197
2198 impl Impl {
2199     crate fn provided_trait_methods(&self, tcx: TyCtxt<'_>) -> FxHashSet<Symbol> {
2200         self.trait_
2201             .as_ref()
2202             .map(|t| t.def_id())
2203             .map(|did| tcx.provided_trait_methods(did).map(|meth| meth.ident.name).collect())
2204             .unwrap_or_default()
2205     }
2206 }
2207
2208 #[derive(Clone, Debug)]
2209 crate enum ImplKind {
2210     Normal,
2211     Auto,
2212     Blanket(Box<Type>),
2213 }
2214
2215 impl ImplKind {
2216     crate fn is_auto(&self) -> bool {
2217         matches!(self, ImplKind::Auto)
2218     }
2219
2220     crate fn is_blanket(&self) -> bool {
2221         matches!(self, ImplKind::Blanket(_))
2222     }
2223
2224     crate fn as_blanket_ty(&self) -> Option<&Type> {
2225         match self {
2226             ImplKind::Blanket(ty) => Some(ty),
2227             _ => None,
2228         }
2229     }
2230 }
2231
2232 #[derive(Clone, Debug)]
2233 crate struct Import {
2234     crate kind: ImportKind,
2235     crate source: ImportSource,
2236     crate should_be_displayed: bool,
2237 }
2238
2239 impl Import {
2240     crate fn new_simple(name: Symbol, source: ImportSource, should_be_displayed: bool) -> Self {
2241         Self { kind: ImportKind::Simple(name), source, should_be_displayed }
2242     }
2243
2244     crate fn new_glob(source: ImportSource, should_be_displayed: bool) -> Self {
2245         Self { kind: ImportKind::Glob, source, should_be_displayed }
2246     }
2247 }
2248
2249 #[derive(Clone, Debug)]
2250 crate enum ImportKind {
2251     // use source as str;
2252     Simple(Symbol),
2253     // use source::*;
2254     Glob,
2255 }
2256
2257 #[derive(Clone, Debug)]
2258 crate struct ImportSource {
2259     crate path: Path,
2260     crate did: Option<DefId>,
2261 }
2262
2263 #[derive(Clone, Debug)]
2264 crate struct Macro {
2265     crate source: String,
2266 }
2267
2268 #[derive(Clone, Debug)]
2269 crate struct ProcMacro {
2270     crate kind: MacroKind,
2271     crate helpers: Vec<Symbol>,
2272 }
2273
2274 /// An type binding on an associated type (e.g., `A = Bar` in `Foo<A = Bar>` or
2275 /// `A: Send + Sync` in `Foo<A: Send + Sync>`).
2276 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2277 crate struct TypeBinding {
2278     crate name: Symbol,
2279     crate kind: TypeBindingKind,
2280 }
2281
2282 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2283 crate enum TypeBindingKind {
2284     Equality { ty: Type },
2285     Constraint { bounds: Vec<GenericBound> },
2286 }
2287
2288 impl TypeBinding {
2289     crate fn ty(&self) -> &Type {
2290         match self.kind {
2291             TypeBindingKind::Equality { ref ty } => ty,
2292             _ => panic!("expected equality type binding for parenthesized generic args"),
2293         }
2294     }
2295 }
2296
2297 /// The type, lifetime, or constant that a private type alias's parameter should be
2298 /// replaced with when expanding a use of that type alias.
2299 ///
2300 /// For example:
2301 ///
2302 /// ```
2303 /// type PrivAlias<T> = Vec<T>;
2304 ///
2305 /// pub fn public_fn() -> PrivAlias<i32> { vec![] }
2306 /// ```
2307 ///
2308 /// `public_fn`'s docs will show it as returning `Vec<i32>`, since `PrivAlias` is private.
2309 /// [`SubstParam`] is used to record that `T` should be mapped to `i32`.
2310 crate enum SubstParam {
2311     Type(Type),
2312     Lifetime(Lifetime),
2313     Constant(Constant),
2314 }
2315
2316 impl SubstParam {
2317     crate fn as_ty(&self) -> Option<&Type> {
2318         if let Self::Type(ty) = self { Some(ty) } else { None }
2319     }
2320
2321     crate fn as_lt(&self) -> Option<&Lifetime> {
2322         if let Self::Lifetime(lt) = self { Some(lt) } else { None }
2323     }
2324 }