src/librustdoc/clean/types.rs

   1 use std::cell::RefCell;
   2 use std::default::Default;
   3 use std::fmt;
   4 use std::hash::{Hash, Hasher};
   5 use std::iter::FromIterator;
   6 use std::lazy::SyncOnceCell as OnceCell;
   7 use std::rc::Rc;
   8 use std::sync::Arc;
   9 use std::{slice, vec};
  10
  11 use rustc_ast::attr;
  12 use rustc_ast::util::comments::beautify_doc_string;
  13 use rustc_ast::{self as ast, AttrStyle};
  14 use rustc_ast::{FloatTy, IntTy, UintTy};
  15 use rustc_attr::{ConstStability, Deprecation, Stability, StabilityLevel};
  16 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  17 use rustc_feature::UnstableFeatures;
  18 use rustc_hir as hir;
  19 use rustc_hir::def::{CtorKind, Res};
  20 use rustc_hir::def_id::{CrateNum, DefId};
  21 use rustc_hir::lang_items::LangItem;
  22 use rustc_hir::Mutability;
  23 use rustc_index::vec::IndexVec;
  24 use rustc_middle::ty::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, SymbolStr};
  29 use rustc_span::{self, FileName, Loc};
  30 use rustc_target::abi::VariantIdx;
  31 use rustc_target::spec::abi::Abi;
  32 use smallvec::{smallvec, SmallVec};
  33
  34 use crate::clean::cfg::Cfg;
  35 use crate::clean::external_path;
  36 use crate::clean::inline;
  37 use crate::clean::types::Type::{QPath, ResolvedPath};
  38 use crate::clean::Clean;
  39 use crate::core::DocContext;
  40 use crate::doctree;
  41 use crate::formats::cache::Cache;
  42 use crate::formats::item_type::ItemType;
  43 use crate::html::render::cache::ExternalLocation;
  44
  45 use self::FnRetTy::*;
  46 use self::ItemKind::*;
  47 use self::SelfTy::*;
  48 use self::Type::*;
  49
  50 thread_local!(crate static MAX_DEF_ID: RefCell<FxHashMap<CrateNum, DefId>> = Default::default());
  51
  52 #[derive(Clone, Debug)]
  53 crate struct Crate {
  54     crate name: Symbol,
  55     crate version: Option<String>,
  56     crate src: FileName,
  57     crate module: Option<Item>,
  58     crate externs: Vec<(CrateNum, ExternalCrate)>,
  59     crate primitives: Vec<(DefId, PrimitiveType)>,
  60     // These are later on moved into `CACHEKEY`, leaving the map empty.
  61     // Only here so that they can be filtered through the rustdoc passes.
  62     crate external_traits: Rc<RefCell<FxHashMap<DefId, Trait>>>,
  63     crate masked_crates: FxHashSet<CrateNum>,
  64     crate collapsed: bool,
  65 }
  66
  67 #[derive(Clone, Debug)]
  68 crate struct ExternalCrate {
  69     crate name: Symbol,
  70     crate src: FileName,
  71     crate attrs: Attributes,
  72     crate primitives: Vec<(DefId, PrimitiveType)>,
  73     crate keywords: Vec<(DefId, Symbol)>,
  74 }
  75
  76 /// Anything with a source location and set of attributes and, optionally, a
  77 /// name. That is, anything that can be documented. This doesn't correspond
  78 /// directly to the AST's concept of an item; it's a strict superset.
  79 #[derive(Clone)]
  80 crate struct Item {
  81     /// Stringified span
  82     crate source: Span,
  83     /// Not everything has a name. E.g., impls
  84     crate name: Option<Symbol>,
  85     crate attrs: Box<Attributes>,
  86     crate visibility: Visibility,
  87     crate kind: Box<ItemKind>,
  88     crate def_id: DefId,
  89 }
  90
  91 // `Item` is used a lot. Make sure it doesn't unintentionally get bigger.
  92 #[cfg(target_arch = "x86_64")]
  93 rustc_data_structures::static_assert_size!(Item, 48);
  94
  95 impl fmt::Debug for Item {
  96     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
  97         let def_id: &dyn fmt::Debug = if self.is_fake() { &"**FAKE**" } else { &self.def_id };
  98
  99         fmt.debug_struct("Item")
 100             .field("source", &self.source)
 101             .field("name", &self.name)
 102             .field("attrs", &self.attrs)
 103             .field("kind", &self.kind)
 104             .field("visibility", &self.visibility)
 105             .field("def_id", def_id)
 106             .finish()
 107     }
 108 }
 109
 110 impl Item {
 111     crate fn stability<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Option<&'tcx Stability> {
 112         if self.is_fake() { None } else { tcx.lookup_stability(self.def_id) }
 113     }
 114
 115     crate fn const_stability<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Option<&'tcx ConstStability> {
 116         if self.is_fake() { None } else { tcx.lookup_const_stability(self.def_id) }
 117     }
 118
 119     crate fn deprecation(&self, tcx: TyCtxt<'_>) -> Option<Deprecation> {
 120         if self.is_fake() { None } else { tcx.lookup_deprecation(self.def_id) }
 121     }
 122
 123     /// Finds the `doc` attribute as a NameValue and returns the corresponding
 124     /// value found.
 125     crate fn doc_value(&self) -> Option<String> {
 126         self.attrs.doc_value()
 127     }
 128
 129     /// Convenience wrapper around [`Self::from_def_id_and_parts`] which converts
 130     /// `hir_id` to a [`DefId`]
 131     pub fn from_hir_id_and_parts(
 132         hir_id: hir::HirId,
 133         name: Option<Symbol>,
 134         kind: ItemKind,
 135         cx: &DocContext<'_>,
 136     ) -> Item {
 137         Item::from_def_id_and_parts(cx.tcx.hir().local_def_id(hir_id).to_def_id(), name, kind, cx)
 138     }
 139
 140     pub fn from_def_id_and_parts(
 141         def_id: DefId,
 142         name: Option<Symbol>,
 143         kind: ItemKind,
 144         cx: &DocContext<'_>,
 145     ) -> Item {
 146         debug!("name={:?}, def_id={:?}", name, def_id);
 147
 148         // `span_if_local()` lies about functions and only gives the span of the function signature
 149         let source = def_id.as_local().map_or_else(
 150             || cx.tcx.def_span(def_id),
 151             |local| {
 152                 let hir = cx.tcx.hir();
 153                 hir.span_with_body(hir.local_def_id_to_hir_id(local))
 154             },
 155         );
 156
 157         Item {
 158             def_id,
 159             kind: box kind,
 160             name,
 161             source: source.clean(cx),
 162             attrs: box cx.tcx.get_attrs(def_id).clean(cx),
 163             visibility: cx.tcx.visibility(def_id).clean(cx),
 164         }
 165     }
 166
 167     /// Finds all `doc` attributes as NameValues and returns their corresponding values, joined
 168     /// with newlines.
 169     crate fn collapsed_doc_value(&self) -> Option<String> {
 170         self.attrs.collapsed_doc_value()
 171     }
 172
 173     crate fn links(&self, cache: &Cache) -> Vec<RenderedLink> {
 174         self.attrs.links(&self.def_id.krate, cache)
 175     }
 176
 177     crate fn is_crate(&self) -> bool {
 178         matches!(
 179             *self.kind,
 180             StrippedItem(box ModuleItem(Module { is_crate: true, .. }))
 181                 | ModuleItem(Module { is_crate: true, .. })
 182         )
 183     }
 184     crate fn is_mod(&self) -> bool {
 185         self.type_() == ItemType::Module
 186     }
 187     crate fn is_trait(&self) -> bool {
 188         self.type_() == ItemType::Trait
 189     }
 190     crate fn is_struct(&self) -> bool {
 191         self.type_() == ItemType::Struct
 192     }
 193     crate fn is_enum(&self) -> bool {
 194         self.type_() == ItemType::Enum
 195     }
 196     crate fn is_variant(&self) -> bool {
 197         self.type_() == ItemType::Variant
 198     }
 199     crate fn is_associated_type(&self) -> bool {
 200         self.type_() == ItemType::AssocType
 201     }
 202     crate fn is_associated_const(&self) -> bool {
 203         self.type_() == ItemType::AssocConst
 204     }
 205     crate fn is_method(&self) -> bool {
 206         self.type_() == ItemType::Method
 207     }
 208     crate fn is_ty_method(&self) -> bool {
 209         self.type_() == ItemType::TyMethod
 210     }
 211     crate fn is_typedef(&self) -> bool {
 212         self.type_() == ItemType::Typedef
 213     }
 214     crate fn is_primitive(&self) -> bool {
 215         self.type_() == ItemType::Primitive
 216     }
 217     crate fn is_union(&self) -> bool {
 218         self.type_() == ItemType::Union
 219     }
 220     crate fn is_import(&self) -> bool {
 221         self.type_() == ItemType::Import
 222     }
 223     crate fn is_extern_crate(&self) -> bool {
 224         self.type_() == ItemType::ExternCrate
 225     }
 226     crate fn is_keyword(&self) -> bool {
 227         self.type_() == ItemType::Keyword
 228     }
 229     crate fn is_stripped(&self) -> bool {
 230         match *self.kind {
 231             StrippedItem(..) => true,
 232             ImportItem(ref i) => !i.should_be_displayed,
 233             _ => false,
 234         }
 235     }
 236     crate fn has_stripped_fields(&self) -> Option<bool> {
 237         match *self.kind {
 238             StructItem(ref _struct) => Some(_struct.fields_stripped),
 239             UnionItem(ref union) => Some(union.fields_stripped),
 240             VariantItem(Variant::Struct(ref vstruct)) => Some(vstruct.fields_stripped),
 241             _ => None,
 242         }
 243     }
 244
 245     crate fn stability_class(&self, tcx: TyCtxt<'_>) -> Option<String> {
 246         self.stability(tcx).as_ref().and_then(|ref s| {
 247             let mut classes = Vec::with_capacity(2);
 248
 249             if s.level.is_unstable() {
 250                 classes.push("unstable");
 251             }
 252
 253             // FIXME: what about non-staged API items that are deprecated?
 254             if self.deprecation(tcx).is_some() {
 255                 classes.push("deprecated");
 256             }
 257
 258             if !classes.is_empty() { Some(classes.join(" ")) } else { None }
 259         })
 260     }
 261
 262     crate fn stable_since(&self, tcx: TyCtxt<'_>) -> Option<SymbolStr> {
 263         match self.stability(tcx)?.level {
 264             StabilityLevel::Stable { since, .. } => Some(since.as_str()),
 265             StabilityLevel::Unstable { .. } => None,
 266         }
 267     }
 268
 269     crate fn const_stable_since(&self, tcx: TyCtxt<'_>) -> Option<SymbolStr> {
 270         match self.const_stability(tcx)?.level {
 271             StabilityLevel::Stable { since, .. } => Some(since.as_str()),
 272             StabilityLevel::Unstable { .. } => None,
 273         }
 274     }
 275
 276     crate fn is_non_exhaustive(&self) -> bool {
 277         self.attrs.other_attrs.iter().any(|a| a.has_name(sym::non_exhaustive))
 278     }
 279
 280     /// Returns a documentation-level item type from the item.
 281     crate fn type_(&self) -> ItemType {
 282         ItemType::from(self)
 283     }
 284
 285     crate fn is_default(&self) -> bool {
 286         match *self.kind {
 287             ItemKind::MethodItem(_, Some(defaultness)) => {
 288                 defaultness.has_value() && !defaultness.is_final()
 289             }
 290             _ => false,
 291         }
 292     }
 293
 294     /// See the documentation for [`next_def_id()`].
 295     ///
 296     /// [`next_def_id()`]: DocContext::next_def_id()
 297     crate fn is_fake(&self) -> bool {
 298         MAX_DEF_ID.with(|m| {
 299             m.borrow().get(&self.def_id.krate).map(|id| self.def_id >= *id).unwrap_or(false)
 300         })
 301     }
 302 }
 303
 304 #[derive(Clone, Debug)]
 305 crate enum ItemKind {
 306     ExternCrateItem(Symbol, Option<Symbol>),
 307     ImportItem(Import),
 308     StructItem(Struct),
 309     UnionItem(Union),
 310     EnumItem(Enum),
 311     FunctionItem(Function),
 312     ModuleItem(Module),
 313     TypedefItem(Typedef, bool /* is associated type */),
 314     OpaqueTyItem(OpaqueTy),
 315     StaticItem(Static),
 316     ConstantItem(Constant),
 317     TraitItem(Trait),
 318     TraitAliasItem(TraitAlias),
 319     ImplItem(Impl),
 320     /// A method signature only. Used for required methods in traits (ie,
 321     /// non-default-methods).
 322     TyMethodItem(Function),
 323     /// A method with a body.
 324     MethodItem(Function, Option<hir::Defaultness>),
 325     StructFieldItem(Type),
 326     VariantItem(Variant),
 327     /// `fn`s from an extern block
 328     ForeignFunctionItem(Function),
 329     /// `static`s from an extern block
 330     ForeignStaticItem(Static),
 331     /// `type`s from an extern block
 332     ForeignTypeItem,
 333     MacroItem(Macro),
 334     ProcMacroItem(ProcMacro),
 335     PrimitiveItem(PrimitiveType),
 336     AssocConstItem(Type, Option<String>),
 337     /// An associated item in a trait or trait impl.
 338     ///
 339     /// The bounds may be non-empty if there is a `where` clause.
 340     /// The `Option<Type>` is the default concrete type (e.g. `trait Trait { type Target = usize; }`)
 341     AssocTypeItem(Vec<GenericBound>, Option<Type>),
 342     /// An item that has been stripped by a rustdoc pass
 343     StrippedItem(Box<ItemKind>),
 344     KeywordItem(Symbol),
 345 }
 346
 347 impl ItemKind {
 348     /// Some items contain others such as structs (for their fields) and Enums
 349     /// (for their variants). This method returns those contained items.
 350     crate fn inner_items(&self) -> impl Iterator<Item = &Item> {
 351         match self {
 352             StructItem(s) => s.fields.iter(),
 353             UnionItem(u) => u.fields.iter(),
 354             VariantItem(Variant::Struct(v)) => v.fields.iter(),
 355             EnumItem(e) => e.variants.iter(),
 356             TraitItem(t) => t.items.iter(),
 357             ImplItem(i) => i.items.iter(),
 358             ModuleItem(m) => m.items.iter(),
 359             ExternCrateItem(_, _)
 360             | ImportItem(_)
 361             | FunctionItem(_)
 362             | TypedefItem(_, _)
 363             | OpaqueTyItem(_)
 364             | StaticItem(_)
 365             | ConstantItem(_)
 366             | TraitAliasItem(_)
 367             | TyMethodItem(_)
 368             | MethodItem(_, _)
 369             | StructFieldItem(_)
 370             | VariantItem(_)
 371             | ForeignFunctionItem(_)
 372             | ForeignStaticItem(_)
 373             | ForeignTypeItem
 374             | MacroItem(_)
 375             | ProcMacroItem(_)
 376             | PrimitiveItem(_)
 377             | AssocConstItem(_, _)
 378             | AssocTypeItem(_, _)
 379             | StrippedItem(_)
 380             | KeywordItem(_) => [].iter(),
 381         }
 382     }
 383
 384     crate fn is_type_alias(&self) -> bool {
 385         matches!(self, ItemKind::TypedefItem(..) | ItemKind::AssocTypeItem(..))
 386     }
 387 }
 388
 389 #[derive(Clone, Debug)]
 390 crate struct Module {
 391     crate items: Vec<Item>,
 392     crate is_crate: bool,
 393 }
 394
 395 crate struct ListAttributesIter<'a> {
 396     attrs: slice::Iter<'a, ast::Attribute>,
 397     current_list: vec::IntoIter<ast::NestedMetaItem>,
 398     name: Symbol,
 399 }
 400
 401 impl<'a> Iterator for ListAttributesIter<'a> {
 402     type Item = ast::NestedMetaItem;
 403
 404     fn next(&mut self) -> Option<Self::Item> {
 405         if let Some(nested) = self.current_list.next() {
 406             return Some(nested);
 407         }
 408
 409         for attr in &mut self.attrs {
 410             if let Some(list) = attr.meta_item_list() {
 411                 if attr.has_name(self.name) {
 412                     self.current_list = list.into_iter();
 413                     if let Some(nested) = self.current_list.next() {
 414                         return Some(nested);
 415                     }
 416                 }
 417             }
 418         }
 419
 420         None
 421     }
 422
 423     fn size_hint(&self) -> (usize, Option<usize>) {
 424         let lower = self.current_list.len();
 425         (lower, None)
 426     }
 427 }
 428
 429 crate trait AttributesExt {
 430     /// Finds an attribute as List and returns the list of attributes nested inside.
 431     fn lists(&self, name: Symbol) -> ListAttributesIter<'_>;
 432 }
 433
 434 impl AttributesExt for [ast::Attribute] {
 435     fn lists(&self, name: Symbol) -> ListAttributesIter<'_> {
 436         ListAttributesIter { attrs: self.iter(), current_list: Vec::new().into_iter(), name }
 437     }
 438 }
 439
 440 crate trait NestedAttributesExt {
 441     /// Returns `true` if the attribute list contains a specific `Word`
 442     fn has_word(self, word: Symbol) -> bool;
 443     fn get_word_attr(self, word: Symbol) -> (Option<ast::NestedMetaItem>, bool);
 444 }
 445
 446 impl<I: Iterator<Item = ast::NestedMetaItem> + IntoIterator<Item = ast::NestedMetaItem>>
 447     NestedAttributesExt for I
 448 {
 449     fn has_word(self, word: Symbol) -> bool {
 450         self.into_iter().any(|attr| attr.is_word() && attr.has_name(word))
 451     }
 452
 453     fn get_word_attr(mut self, word: Symbol) -> (Option<ast::NestedMetaItem>, bool) {
 454         match self.find(|attr| attr.is_word() && attr.has_name(word)) {
 455             Some(a) => (Some(a), true),
 456             None => (None, false),
 457         }
 458     }
 459 }
 460
 461 /// A portion of documentation, extracted from a `#[doc]` attribute.
 462 ///
 463 /// Each variant contains the line number within the complete doc-comment where the fragment
 464 /// starts, as well as the Span where the corresponding doc comment or attribute is located.
 465 ///
 466 /// Included files are kept separate from inline doc comments so that proper line-number
 467 /// information can be given when a doctest fails. Sugared doc comments and "raw" doc comments are
 468 /// kept separate because of issue #42760.
 469 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 470 crate struct DocFragment {
 471     crate line: usize,
 472     crate span: rustc_span::Span,
 473     /// The module this doc-comment came from.
 474     ///
 475     /// This allows distinguishing between the original documentation and a pub re-export.
 476     /// If it is `None`, the item was not re-exported.
 477     crate parent_module: Option<DefId>,
 478     crate doc: Symbol,
 479     crate kind: DocFragmentKind,
 480     crate need_backline: bool,
 481     crate indent: usize,
 482 }
 483
 484 #[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
 485 crate enum DocFragmentKind {
 486     /// A doc fragment created from a `///` or `//!` doc comment.
 487     SugaredDoc,
 488     /// A doc fragment created from a "raw" `#[doc=""]` attribute.
 489     RawDoc,
 490     /// A doc fragment created from a `#[doc(include="filename")]` attribute. Contains both the
 491     /// given filename and the file contents.
 492     Include { filename: Symbol },
 493 }
 494
 495 // The goal of this function is to apply the `DocFragment` transformations that are required when
 496 // transforming into the final markdown. So the transformations in here are:
 497 //
 498 // * Applying the computed indent to each lines in each doc fragment (a `DocFragment` can contain
 499 //   multiple lines in case of `#[doc = ""]`).
 500 // * Adding backlines between `DocFragment`s and adding an extra one if required (stored in the
 501 //   `need_backline` field).
 502 fn add_doc_fragment(out: &mut String, frag: &DocFragment) {
 503     let s = frag.doc.as_str();
 504     let mut iter = s.lines().peekable();
 505     while let Some(line) = iter.next() {
 506         if line.chars().any(|c| !c.is_whitespace()) {
 507             assert!(line.len() >= frag.indent);
 508             out.push_str(&line[frag.indent..]);
 509         } else {
 510             out.push_str(line);
 511         }
 512         if iter.peek().is_some() {
 513             out.push('\n');
 514         }
 515     }
 516     if frag.need_backline {
 517         out.push('\n');
 518     }
 519 }
 520
 521 impl<'a> FromIterator<&'a DocFragment> for String {
 522     fn from_iter<T>(iter: T) -> Self
 523     where
 524         T: IntoIterator<Item = &'a DocFragment>,
 525     {
 526         let mut prev_kind: Option<DocFragmentKind> = None;
 527         iter.into_iter().fold(String::new(), |mut acc, frag| {
 528             if !acc.is_empty()
 529                 && prev_kind
 530                     .take()
 531                     .map(|p| matches!(p, DocFragmentKind::Include { .. }) && p != frag.kind)
 532                     .unwrap_or(false)
 533             {
 534                 acc.push('\n');
 535             }
 536             add_doc_fragment(&mut acc, &frag);
 537             prev_kind = Some(frag.kind);
 538             acc
 539         })
 540     }
 541 }
 542
 543 #[derive(Clone, Debug, Default)]
 544 crate struct Attributes {
 545     crate doc_strings: Vec<DocFragment>,
 546     crate other_attrs: Vec<ast::Attribute>,
 547     crate cfg: Option<Arc<Cfg>>,
 548     crate span: Option<rustc_span::Span>,
 549     /// map from Rust paths to resolved defs and potential URL fragments
 550     crate links: Vec<ItemLink>,
 551     crate inner_docs: bool,
 552 }
 553
 554 #[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
 555 /// A link that has not yet been rendered.
 556 ///
 557 /// This link will be turned into a rendered link by [`Attributes::links`]
 558 crate struct ItemLink {
 559     /// The original link written in the markdown
 560     pub(crate) link: String,
 561     /// The link text displayed in the HTML.
 562     ///
 563     /// This may not be the same as `link` if there was a disambiguator
 564     /// in an intra-doc link (e.g. \[`fn@f`\])
 565     pub(crate) link_text: String,
 566     pub(crate) did: Option<DefId>,
 567     /// The url fragment to append to the link
 568     pub(crate) fragment: Option<String>,
 569 }
 570
 571 pub struct RenderedLink {
 572     /// The text the link was original written as.
 573     ///
 574     /// This could potentially include disambiguators and backticks.
 575     pub(crate) original_text: String,
 576     /// The text to display in the HTML
 577     pub(crate) new_text: String,
 578     /// The URL to put in the `href`
 579     pub(crate) href: String,
 580 }
 581
 582 impl Attributes {
 583     /// Extracts the content from an attribute `#[doc(cfg(content))]`.
 584     crate fn extract_cfg(mi: &ast::MetaItem) -> Option<&ast::MetaItem> {
 585         use rustc_ast::NestedMetaItem::MetaItem;
 586
 587         if let ast::MetaItemKind::List(ref nmis) = mi.kind {
 588             if nmis.len() == 1 {
 589                 if let MetaItem(ref cfg_mi) = nmis[0] {
 590                     if cfg_mi.has_name(sym::cfg) {
 591                         if let ast::MetaItemKind::List(ref cfg_nmis) = cfg_mi.kind {
 592                             if cfg_nmis.len() == 1 {
 593                                 if let MetaItem(ref content_mi) = cfg_nmis[0] {
 594                                     return Some(content_mi);
 595                                 }
 596                             }
 597                         }
 598                     }
 599                 }
 600             }
 601         }
 602
 603         None
 604     }
 605
 606     /// Reads a `MetaItem` from within an attribute, looks for whether it is a
 607     /// `#[doc(include="file")]`, and returns the filename and contents of the file as loaded from
 608     /// its expansion.
 609     crate fn extract_include(mi: &ast::MetaItem) -> Option<(Symbol, Symbol)> {
 610         mi.meta_item_list().and_then(|list| {
 611             for meta in list {
 612                 if meta.has_name(sym::include) {
 613                     // the actual compiled `#[doc(include="filename")]` gets expanded to
 614                     // `#[doc(include(file="filename", contents="file contents")]` so we need to
 615                     // look for that instead
 616                     return meta.meta_item_list().and_then(|list| {
 617                         let mut filename: Option<Symbol> = None;
 618                         let mut contents: Option<Symbol> = None;
 619
 620                         for it in list {
 621                             if it.has_name(sym::file) {
 622                                 if let Some(name) = it.value_str() {
 623                                     filename = Some(name);
 624                                 }
 625                             } else if it.has_name(sym::contents) {
 626                                 if let Some(docs) = it.value_str() {
 627                                     contents = Some(docs);
 628                                 }
 629                             }
 630                         }
 631
 632                         if let (Some(filename), Some(contents)) = (filename, contents) {
 633                             Some((filename, contents))
 634                         } else {
 635                             None
 636                         }
 637                     });
 638                 }
 639             }
 640
 641             None
 642         })
 643     }
 644
 645     crate fn has_doc_flag(&self, flag: Symbol) -> bool {
 646         for attr in &self.other_attrs {
 647             if !attr.has_name(sym::doc) {
 648                 continue;
 649             }
 650
 651             if let Some(items) = attr.meta_item_list() {
 652                 if items.iter().filter_map(|i| i.meta_item()).any(|it| it.has_name(flag)) {
 653                     return true;
 654                 }
 655             }
 656         }
 657
 658         false
 659     }
 660
 661     crate fn from_ast(
 662         diagnostic: &::rustc_errors::Handler,
 663         attrs: &[ast::Attribute],
 664         additional_attrs: Option<(&[ast::Attribute], DefId)>,
 665     ) -> Attributes {
 666         let mut doc_strings: Vec<DocFragment> = vec![];
 667         let mut sp = None;
 668         let mut cfg = Cfg::True;
 669         let mut doc_line = 0;
 670
 671         fn update_need_backline(doc_strings: &mut Vec<DocFragment>, frag: &DocFragment) {
 672             if let Some(prev) = doc_strings.last_mut() {
 673                 if matches!(prev.kind, DocFragmentKind::Include { .. })
 674                     || prev.kind != frag.kind
 675                     || prev.parent_module != frag.parent_module
 676                 {
 677                     // add a newline for extra padding between segments
 678                     prev.need_backline = prev.kind == DocFragmentKind::SugaredDoc
 679                         || prev.kind == DocFragmentKind::RawDoc
 680                 } else {
 681                     prev.need_backline = true;
 682                 }
 683             }
 684         }
 685
 686         let clean_attr = |(attr, parent_module): (&ast::Attribute, _)| {
 687             if let Some(value) = attr.doc_str() {
 688                 trace!("got doc_str={:?}", value);
 689                 let value = beautify_doc_string(value);
 690                 let kind = if attr.is_doc_comment() {
 691                     DocFragmentKind::SugaredDoc
 692                 } else {
 693                     DocFragmentKind::RawDoc
 694                 };
 695
 696                 let line = doc_line;
 697                 doc_line += value.as_str().lines().count();
 698                 let frag = DocFragment {
 699                     line,
 700                     span: attr.span,
 701                     doc: value,
 702                     kind,
 703                     parent_module,
 704                     need_backline: false,
 705                     indent: 0,
 706                 };
 707
 708                 update_need_backline(&mut doc_strings, &frag);
 709
 710                 doc_strings.push(frag);
 711
 712                 if sp.is_none() {
 713                     sp = Some(attr.span);
 714                 }
 715                 None
 716             } else {
 717                 if attr.has_name(sym::doc) {
 718                     if let Some(mi) = attr.meta() {
 719                         if let Some(cfg_mi) = Attributes::extract_cfg(&mi) {
 720                             // Extracted #[doc(cfg(...))]
 721                             match Cfg::parse(cfg_mi) {
 722                                 Ok(new_cfg) => cfg &= new_cfg,
 723                                 Err(e) => diagnostic.span_err(e.span, e.msg),
 724                             }
 725                         } else if let Some((filename, contents)) = Attributes::extract_include(&mi)
 726                         {
 727                             let line = doc_line;
 728                             doc_line += contents.as_str().lines().count();
 729                             let frag = DocFragment {
 730                                 line,
 731                                 span: attr.span,
 732                                 doc: contents,
 733                                 kind: DocFragmentKind::Include { filename },
 734                                 parent_module,
 735                                 need_backline: false,
 736                                 indent: 0,
 737                             };
 738                             update_need_backline(&mut doc_strings, &frag);
 739                             doc_strings.push(frag);
 740                         }
 741                     }
 742                 }
 743                 Some(attr.clone())
 744             }
 745         };
 746
 747         // Additional documentation should be shown before the original documentation
 748         let other_attrs = additional_attrs
 749             .into_iter()
 750             .map(|(attrs, id)| attrs.iter().map(move |attr| (attr, Some(id))))
 751             .flatten()
 752             .chain(attrs.iter().map(|attr| (attr, None)))
 753             .filter_map(clean_attr)
 754             .collect();
 755
 756         // treat #[target_feature(enable = "feat")] attributes as if they were
 757         // #[doc(cfg(target_feature = "feat"))] attributes as well
 758         for attr in attrs.lists(sym::target_feature) {
 759             if attr.has_name(sym::enable) {
 760                 if let Some(feat) = attr.value_str() {
 761                     let meta = attr::mk_name_value_item_str(
 762                         Ident::with_dummy_span(sym::target_feature),
 763                         feat,
 764                         DUMMY_SP,
 765                     );
 766                     if let Ok(feat_cfg) = Cfg::parse(&meta) {
 767                         cfg &= feat_cfg;
 768                     }
 769                 }
 770             }
 771         }
 772
 773         let inner_docs = attrs
 774             .iter()
 775             .find(|a| a.doc_str().is_some())
 776             .map_or(true, |a| a.style == AttrStyle::Inner);
 777
 778         Attributes {
 779             doc_strings,
 780             other_attrs,
 781             cfg: if cfg == Cfg::True { None } else { Some(Arc::new(cfg)) },
 782             span: sp,
 783             links: vec![],
 784             inner_docs,
 785         }
 786     }
 787
 788     /// Finds the `doc` attribute as a NameValue and returns the corresponding
 789     /// value found.
 790     crate fn doc_value(&self) -> Option<String> {
 791         let mut iter = self.doc_strings.iter();
 792
 793         let ori = iter.next()?;
 794         let mut out = String::new();
 795         add_doc_fragment(&mut out, &ori);
 796         while let Some(new_frag) = iter.next() {
 797             if matches!(ori.kind, DocFragmentKind::Include { .. })
 798                 || new_frag.kind != ori.kind
 799                 || new_frag.parent_module != ori.parent_module
 800             {
 801                 break;
 802             }
 803             add_doc_fragment(&mut out, &new_frag);
 804         }
 805         if out.is_empty() { None } else { Some(out) }
 806     }
 807
 808     /// Return the doc-comments on this item, grouped by the module they came from.
 809     ///
 810     /// The module can be different if this is a re-export with added documentation.
 811     crate fn collapsed_doc_value_by_module_level(&self) -> FxHashMap<Option<DefId>, String> {
 812         let mut ret = FxHashMap::default();
 813
 814         for new_frag in self.doc_strings.iter() {
 815             let out = ret.entry(new_frag.parent_module).or_default();
 816             add_doc_fragment(out, &new_frag);
 817         }
 818         ret
 819     }
 820
 821     /// Finds all `doc` attributes as NameValues and returns their corresponding values, joined
 822     /// with newlines.
 823     crate fn collapsed_doc_value(&self) -> Option<String> {
 824         if self.doc_strings.is_empty() { None } else { Some(self.doc_strings.iter().collect()) }
 825     }
 826
 827     /// Gets links as a vector
 828     ///
 829     /// Cache must be populated before call
 830     crate fn links(&self, krate: &CrateNum, cache: &Cache) -> Vec<RenderedLink> {
 831         use crate::html::format::href;
 832         use crate::html::render::CURRENT_DEPTH;
 833
 834         self.links
 835             .iter()
 836             .filter_map(|ItemLink { link: s, link_text, did, fragment }| {
 837                 match *did {
 838                     Some(did) => {
 839                         if let Some((mut href, ..)) = href(did, cache) {
 840                             if let Some(ref fragment) = *fragment {
 841                                 href.push('#');
 842                                 href.push_str(fragment);
 843                             }
 844                             Some(RenderedLink {
 845                                 original_text: s.clone(),
 846                                 new_text: link_text.clone(),
 847                                 href,
 848                             })
 849                         } else {
 850                             None
 851                         }
 852                     }
 853                     None => {
 854                         if let Some(ref fragment) = *fragment {
 855                             let url = match cache.extern_locations.get(krate) {
 856                                 Some(&(_, _, ExternalLocation::Local)) => {
 857                                     let depth = CURRENT_DEPTH.with(|l| l.get());
 858                                     "../".repeat(depth)
 859                                 }
 860                                 Some(&(_, _, ExternalLocation::Remote(ref s))) => s.to_string(),
 861                                 Some(&(_, _, ExternalLocation::Unknown)) | None => String::from(
 862                                     // NOTE: intentionally doesn't pass crate name to avoid having
 863                                     // different primitive links between crates
 864                                     if UnstableFeatures::from_environment(None).is_nightly_build() {
 865                                         "https://doc.rust-lang.org/nightly"
 866                                     } else {
 867                                         "https://doc.rust-lang.org"
 868                                     },
 869                                 ),
 870                             };
 871                             // This is a primitive so the url is done "by hand".
 872                             let tail = fragment.find('#').unwrap_or_else(|| fragment.len());
 873                             Some(RenderedLink {
 874                                 original_text: s.clone(),
 875                                 new_text: link_text.clone(),
 876                                 href: format!(
 877                                     "{}{}std/primitive.{}.html{}",
 878                                     url,
 879                                     if !url.ends_with('/') { "/" } else { "" },
 880                                     &fragment[..tail],
 881                                     &fragment[tail..]
 882                                 ),
 883                             })
 884                         } else {
 885                             panic!("This isn't a primitive?!");
 886                         }
 887                     }
 888                 }
 889             })
 890             .collect()
 891     }
 892
 893     crate fn get_doc_aliases(&self) -> FxHashSet<String> {
 894         self.other_attrs
 895             .lists(sym::doc)
 896             .filter(|a| a.has_name(sym::alias))
 897             .filter_map(|a| a.value_str().map(|s| s.to_string()))
 898             .filter(|v| !v.is_empty())
 899             .collect::<FxHashSet<_>>()
 900     }
 901 }
 902
 903 impl PartialEq for Attributes {
 904     fn eq(&self, rhs: &Self) -> bool {
 905         self.doc_strings == rhs.doc_strings
 906             && self.cfg == rhs.cfg
 907             && self.span == rhs.span
 908             && self.links == rhs.links
 909             && self
 910                 .other_attrs
 911                 .iter()
 912                 .map(|attr| attr.id)
 913                 .eq(rhs.other_attrs.iter().map(|attr| attr.id))
 914     }
 915 }
 916
 917 impl Eq for Attributes {}
 918
 919 impl Hash for Attributes {
 920     fn hash<H: Hasher>(&self, hasher: &mut H) {
 921         self.doc_strings.hash(hasher);
 922         self.cfg.hash(hasher);
 923         self.span.hash(hasher);
 924         self.links.hash(hasher);
 925         for attr in &self.other_attrs {
 926             attr.id.hash(hasher);
 927         }
 928     }
 929 }
 930
 931 impl AttributesExt for Attributes {
 932     fn lists(&self, name: Symbol) -> ListAttributesIter<'_> {
 933         self.other_attrs.lists(name)
 934     }
 935 }
 936
 937 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 938 crate enum GenericBound {
 939     TraitBound(PolyTrait, hir::TraitBoundModifier),
 940     Outlives(Lifetime),
 941 }
 942
 943 impl GenericBound {
 944     crate fn maybe_sized(cx: &DocContext<'_>) -> GenericBound {
 945         let did = cx.tcx.require_lang_item(LangItem::Sized, None);
 946         let empty = cx.tcx.intern_substs(&[]);
 947         let path = external_path(cx, cx.tcx.item_name(did), Some(did), false, vec![], empty);
 948         inline::record_extern_fqn(cx, did, TypeKind::Trait);
 949         GenericBound::TraitBound(
 950             PolyTrait {
 951                 trait_: ResolvedPath { path, param_names: None, did, is_generic: false },
 952                 generic_params: Vec::new(),
 953             },
 954             hir::TraitBoundModifier::Maybe,
 955         )
 956     }
 957
 958     crate fn is_sized_bound(&self, cx: &DocContext<'_>) -> bool {
 959         use rustc_hir::TraitBoundModifier as TBM;
 960         if let GenericBound::TraitBound(PolyTrait { ref trait_, .. }, TBM::None) = *self {
 961             if trait_.def_id(&cx.cache) == cx.tcx.lang_items().sized_trait() {
 962                 return true;
 963             }
 964         }
 965         false
 966     }
 967
 968     crate fn get_poly_trait(&self) -> Option<PolyTrait> {
 969         if let GenericBound::TraitBound(ref p, _) = *self {
 970             return Some(p.clone());
 971         }
 972         None
 973     }
 974
 975     crate fn get_trait_type(&self) -> Option<Type> {
 976         if let GenericBound::TraitBound(PolyTrait { ref trait_, .. }, _) = *self {
 977             Some(trait_.clone())
 978         } else {
 979             None
 980         }
 981     }
 982 }
 983
 984 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 985 crate struct Lifetime(pub Symbol);
 986
 987 impl Lifetime {
 988     crate fn get_ref(&self) -> SymbolStr {
 989         self.0.as_str()
 990     }
 991
 992     crate fn statik() -> Lifetime {
 993         Lifetime(kw::StaticLifetime)
 994     }
 995
 996     crate fn elided() -> Lifetime {
 997         Lifetime(kw::UnderscoreLifetime)
 998     }
 999 }
1000
1001 #[derive(Clone, Debug)]
1002 crate enum WherePredicate {
1003     BoundPredicate { ty: Type, bounds: Vec<GenericBound> },
1004     RegionPredicate { lifetime: Lifetime, bounds: Vec<GenericBound> },
1005     EqPredicate { lhs: Type, rhs: Type },
1006 }
1007
1008 impl WherePredicate {
1009     crate fn get_bounds(&self) -> Option<&[GenericBound]> {
1010         match *self {
1011             WherePredicate::BoundPredicate { ref bounds, .. } => Some(bounds),
1012             WherePredicate::RegionPredicate { ref bounds, .. } => Some(bounds),
1013             _ => None,
1014         }
1015     }
1016 }
1017
1018 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1019 crate enum GenericParamDefKind {
1020     Lifetime,
1021     Type {
1022         did: DefId,
1023         bounds: Vec<GenericBound>,
1024         default: Option<Type>,
1025         synthetic: Option<hir::SyntheticTyParamKind>,
1026     },
1027     Const {
1028         did: DefId,
1029         ty: Type,
1030     },
1031 }
1032
1033 impl GenericParamDefKind {
1034     crate fn is_type(&self) -> bool {
1035         matches!(self, GenericParamDefKind::Type { .. })
1036     }
1037
1038     // FIXME(eddyb) this either returns the default of a type parameter, or the
1039     // type of a `const` parameter. It seems that the intention is to *visit*
1040     // any embedded types, but `get_type` seems to be the wrong name for that.
1041     crate fn get_type(&self) -> Option<Type> {
1042         match self {
1043             GenericParamDefKind::Type { default, .. } => default.clone(),
1044             GenericParamDefKind::Const { ty, .. } => Some(ty.clone()),
1045             GenericParamDefKind::Lifetime => None,
1046         }
1047     }
1048 }
1049
1050 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1051 crate struct GenericParamDef {
1052     crate name: Symbol,
1053     crate kind: GenericParamDefKind,
1054 }
1055
1056 impl GenericParamDef {
1057     crate fn is_synthetic_type_param(&self) -> bool {
1058         match self.kind {
1059             GenericParamDefKind::Lifetime | GenericParamDefKind::Const { .. } => false,
1060             GenericParamDefKind::Type { ref synthetic, .. } => synthetic.is_some(),
1061         }
1062     }
1063
1064     crate fn is_type(&self) -> bool {
1065         self.kind.is_type()
1066     }
1067
1068     crate fn get_type(&self) -> Option<Type> {
1069         self.kind.get_type()
1070     }
1071
1072     crate fn get_bounds(&self) -> Option<&[GenericBound]> {
1073         match self.kind {
1074             GenericParamDefKind::Type { ref bounds, .. } => Some(bounds),
1075             _ => None,
1076         }
1077     }
1078 }
1079
1080 // maybe use a Generic enum and use Vec<Generic>?
1081 #[derive(Clone, Debug, Default)]
1082 crate struct Generics {
1083     crate params: Vec<GenericParamDef>,
1084     crate where_predicates: Vec<WherePredicate>,
1085 }
1086
1087 #[derive(Clone, Debug)]
1088 crate struct Function {
1089     crate decl: FnDecl,
1090     crate generics: Generics,
1091     crate header: hir::FnHeader,
1092     crate all_types: Vec<(Type, TypeKind)>,
1093     crate ret_types: Vec<(Type, TypeKind)>,
1094 }
1095
1096 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1097 crate struct FnDecl {
1098     crate inputs: Arguments,
1099     crate output: FnRetTy,
1100     crate c_variadic: bool,
1101     crate attrs: Attributes,
1102 }
1103
1104 impl FnDecl {
1105     crate fn self_type(&self) -> Option<SelfTy> {
1106         self.inputs.values.get(0).and_then(|v| v.to_self())
1107     }
1108
1109     /// Returns the sugared return type for an async function.
1110     ///
1111     /// For example, if the return type is `impl std::future::Future<Output = i32>`, this function
1112     /// will return `i32`.
1113     ///
1114     /// # Panics
1115     ///
1116     /// This function will panic if the return type does not match the expected sugaring for async
1117     /// functions.
1118     crate fn sugared_async_return_type(&self) -> FnRetTy {
1119         match &self.output {
1120             FnRetTy::Return(Type::ImplTrait(bounds)) => match &bounds[0] {
1121                 GenericBound::TraitBound(PolyTrait { trait_, .. }, ..) => {
1122                     let bindings = trait_.bindings().unwrap();
1123                     FnRetTy::Return(bindings[0].ty().clone())
1124                 }
1125                 _ => panic!("unexpected desugaring of async function"),
1126             },
1127             _ => panic!("unexpected desugaring of async function"),
1128         }
1129     }
1130 }
1131
1132 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1133 crate struct Arguments {
1134     crate values: Vec<Argument>,
1135 }
1136
1137 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1138 crate struct Argument {
1139     crate type_: Type,
1140     crate name: Symbol,
1141 }
1142
1143 #[derive(Clone, PartialEq, Debug)]
1144 crate enum SelfTy {
1145     SelfValue,
1146     SelfBorrowed(Option<Lifetime>, Mutability),
1147     SelfExplicit(Type),
1148 }
1149
1150 impl Argument {
1151     crate fn to_self(&self) -> Option<SelfTy> {
1152         if self.name != kw::SelfLower {
1153             return None;
1154         }
1155         if self.type_.is_self_type() {
1156             return Some(SelfValue);
1157         }
1158         match self.type_ {
1159             BorrowedRef { ref lifetime, mutability, ref type_ } if type_.is_self_type() => {
1160                 Some(SelfBorrowed(lifetime.clone(), mutability))
1161             }
1162             _ => Some(SelfExplicit(self.type_.clone())),
1163         }
1164     }
1165 }
1166
1167 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1168 crate enum FnRetTy {
1169     Return(Type),
1170     DefaultReturn,
1171 }
1172
1173 impl GetDefId for FnRetTy {
1174     fn def_id(&self, cache: &Cache) -> Option<DefId> {
1175         match *self {
1176             Return(ref ty) => ty.def_id(cache),
1177             DefaultReturn => None,
1178         }
1179     }
1180 }
1181
1182 #[derive(Clone, Debug)]
1183 crate struct Trait {
1184     crate unsafety: hir::Unsafety,
1185     crate items: Vec<Item>,
1186     crate generics: Generics,
1187     crate bounds: Vec<GenericBound>,
1188     crate is_spotlight: bool,
1189     crate is_auto: bool,
1190 }
1191
1192 #[derive(Clone, Debug)]
1193 crate struct TraitAlias {
1194     crate generics: Generics,
1195     crate bounds: Vec<GenericBound>,
1196 }
1197
1198 /// A trait reference, which may have higher ranked lifetimes.
1199 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1200 crate struct PolyTrait {
1201     crate trait_: Type,
1202     crate generic_params: Vec<GenericParamDef>,
1203 }
1204
1205 /// A representation of a type suitable for hyperlinking purposes. Ideally, one can get the original
1206 /// type out of the AST/`TyCtxt` given one of these, if more information is needed. Most
1207 /// importantly, it does not preserve mutability or boxes.
1208 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1209 crate enum Type {
1210     /// Structs/enums/traits (most that would be an `hir::TyKind::Path`).
1211     ResolvedPath {
1212         path: Path,
1213         param_names: Option<Vec<GenericBound>>,
1214         did: DefId,
1215         /// `true` if is a `T::Name` path for associated types.
1216         is_generic: bool,
1217     },
1218     /// For parameterized types, so the consumer of the JSON don't go
1219     /// looking for types which don't exist anywhere.
1220     Generic(Symbol),
1221     /// Primitives are the fixed-size numeric types (plus int/usize/float), char,
1222     /// arrays, slices, and tuples.
1223     Primitive(PrimitiveType),
1224     /// `extern "ABI" fn`
1225     BareFunction(Box<BareFunctionDecl>),
1226     Tuple(Vec<Type>),
1227     Slice(Box<Type>),
1228     /// The `String` field is about the size or the constant representing the array's length.
1229     Array(Box<Type>, String),
1230     Never,
1231     RawPointer(Mutability, Box<Type>),
1232     BorrowedRef {
1233         lifetime: Option<Lifetime>,
1234         mutability: Mutability,
1235         type_: Box<Type>,
1236     },
1237
1238     // `<Type as Trait>::Name`
1239     QPath {
1240         name: Symbol,
1241         self_type: Box<Type>,
1242         trait_: Box<Type>,
1243     },
1244
1245     // `_`
1246     Infer,
1247
1248     // `impl TraitA + TraitB + ...`
1249     ImplTrait(Vec<GenericBound>),
1250 }
1251
1252 #[derive(Clone, PartialEq, Eq, Hash, Copy, Debug)]
1253 /// N.B. this has to be different from `hir::PrimTy` because it also includes types that aren't
1254 /// paths, like `Unit`.
1255 crate enum PrimitiveType {
1256     Isize,
1257     I8,
1258     I16,
1259     I32,
1260     I64,
1261     I128,
1262     Usize,
1263     U8,
1264     U16,
1265     U32,
1266     U64,
1267     U128,
1268     F32,
1269     F64,
1270     Char,
1271     Bool,
1272     Str,
1273     Slice,
1274     Array,
1275     Tuple,
1276     Unit,
1277     RawPointer,
1278     Reference,
1279     Fn,
1280     Never,
1281 }
1282
1283 #[derive(Clone, PartialEq, Eq, Hash, Copy, Debug)]
1284 crate enum TypeKind {
1285     Enum,
1286     Function,
1287     Module,
1288     Const,
1289     Static,
1290     Struct,
1291     Union,
1292     Trait,
1293     Typedef,
1294     Foreign,
1295     Macro,
1296     Attr,
1297     Derive,
1298     TraitAlias,
1299 }
1300
1301 crate trait GetDefId {
1302     fn def_id(&self, cache: &Cache) -> Option<DefId>;
1303 }
1304
1305 impl<T: GetDefId> GetDefId for Option<T> {
1306     fn def_id(&self, cache: &Cache) -> Option<DefId> {
1307         self.as_ref().and_then(|d| d.def_id(cache))
1308     }
1309 }
1310
1311 impl Type {
1312     crate fn primitive_type(&self) -> Option<PrimitiveType> {
1313         match *self {
1314             Primitive(p) | BorrowedRef { type_: box Primitive(p), .. } => Some(p),
1315             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
1316             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
1317             Tuple(ref tys) => {
1318                 if tys.is_empty() {
1319                     Some(PrimitiveType::Unit)
1320                 } else {
1321                     Some(PrimitiveType::Tuple)
1322                 }
1323             }
1324             RawPointer(..) => Some(PrimitiveType::RawPointer),
1325             BorrowedRef { type_: box Generic(..), .. } => Some(PrimitiveType::Reference),
1326             BareFunction(..) => Some(PrimitiveType::Fn),
1327             Never => Some(PrimitiveType::Never),
1328             _ => None,
1329         }
1330     }
1331
1332     crate fn is_generic(&self) -> bool {
1333         match *self {
1334             ResolvedPath { is_generic, .. } => is_generic,
1335             _ => false,
1336         }
1337     }
1338
1339     crate fn is_self_type(&self) -> bool {
1340         match *self {
1341             Generic(name) => name == kw::SelfUpper,
1342             _ => false,
1343         }
1344     }
1345
1346     crate fn generics(&self) -> Option<Vec<Type>> {
1347         match *self {
1348             ResolvedPath { ref path, .. } => path.segments.last().and_then(|seg| {
1349                 if let GenericArgs::AngleBracketed { ref args, .. } = seg.args {
1350                     Some(
1351                         args.iter()
1352                             .filter_map(|arg| match arg {
1353                                 GenericArg::Type(ty) => Some(ty.clone()),
1354                                 _ => None,
1355                             })
1356                             .collect(),
1357                     )
1358                 } else {
1359                     None
1360                 }
1361             }),
1362             _ => None,
1363         }
1364     }
1365
1366     crate fn bindings(&self) -> Option<&[TypeBinding]> {
1367         match *self {
1368             ResolvedPath { ref path, .. } => path.segments.last().and_then(|seg| {
1369                 if let GenericArgs::AngleBracketed { ref bindings, .. } = seg.args {
1370                     Some(&**bindings)
1371                 } else {
1372                     None
1373                 }
1374             }),
1375             _ => None,
1376         }
1377     }
1378
1379     crate fn is_full_generic(&self) -> bool {
1380         matches!(self, Type::Generic(_))
1381     }
1382
1383     crate fn projection(&self) -> Option<(&Type, DefId, Symbol)> {
1384         let (self_, trait_, name) = match self {
1385             QPath { self_type, trait_, name } => (self_type, trait_, name),
1386             _ => return None,
1387         };
1388         let trait_did = match **trait_ {
1389             ResolvedPath { did, .. } => did,
1390             _ => return None,
1391         };
1392         Some((&self_, trait_did, *name))
1393     }
1394 }
1395
1396 impl GetDefId for Type {
1397     fn def_id(&self, cache: &Cache) -> Option<DefId> {
1398         match *self {
1399             ResolvedPath { did, .. } => Some(did),
1400             Primitive(p) => cache.primitive_locations.get(&p).cloned(),
1401             BorrowedRef { type_: box Generic(..), .. } => {
1402                 Primitive(PrimitiveType::Reference).def_id(cache)
1403             }
1404             BorrowedRef { ref type_, .. } => type_.def_id(cache),
1405             Tuple(ref tys) => {
1406                 if tys.is_empty() {
1407                     Primitive(PrimitiveType::Unit).def_id(cache)
1408                 } else {
1409                     Primitive(PrimitiveType::Tuple).def_id(cache)
1410                 }
1411             }
1412             BareFunction(..) => Primitive(PrimitiveType::Fn).def_id(cache),
1413             Never => Primitive(PrimitiveType::Never).def_id(cache),
1414             Slice(..) => Primitive(PrimitiveType::Slice).def_id(cache),
1415             Array(..) => Primitive(PrimitiveType::Array).def_id(cache),
1416             RawPointer(..) => Primitive(PrimitiveType::RawPointer).def_id(cache),
1417             QPath { ref self_type, .. } => self_type.def_id(cache),
1418             _ => None,
1419         }
1420     }
1421 }
1422
1423 impl PrimitiveType {
1424     crate fn from_hir(prim: hir::PrimTy) -> PrimitiveType {
1425         match prim {
1426             hir::PrimTy::Int(IntTy::Isize) => PrimitiveType::Isize,
1427             hir::PrimTy::Int(IntTy::I8) => PrimitiveType::I8,
1428             hir::PrimTy::Int(IntTy::I16) => PrimitiveType::I16,
1429             hir::PrimTy::Int(IntTy::I32) => PrimitiveType::I32,
1430             hir::PrimTy::Int(IntTy::I64) => PrimitiveType::I64,
1431             hir::PrimTy::Int(IntTy::I128) => PrimitiveType::I128,
1432             hir::PrimTy::Uint(UintTy::Usize) => PrimitiveType::Usize,
1433             hir::PrimTy::Uint(UintTy::U8) => PrimitiveType::U8,
1434             hir::PrimTy::Uint(UintTy::U16) => PrimitiveType::U16,
1435             hir::PrimTy::Uint(UintTy::U32) => PrimitiveType::U32,
1436             hir::PrimTy::Uint(UintTy::U64) => PrimitiveType::U64,
1437             hir::PrimTy::Uint(UintTy::U128) => PrimitiveType::U128,
1438             hir::PrimTy::Float(FloatTy::F32) => PrimitiveType::F32,
1439             hir::PrimTy::Float(FloatTy::F64) => PrimitiveType::F64,
1440             hir::PrimTy::Str => PrimitiveType::Str,
1441             hir::PrimTy::Bool => PrimitiveType::Bool,
1442             hir::PrimTy::Char => PrimitiveType::Char,
1443         }
1444     }
1445
1446     crate fn from_symbol(s: Symbol) -> Option<PrimitiveType> {
1447         match s {
1448             sym::isize => Some(PrimitiveType::Isize),
1449             sym::i8 => Some(PrimitiveType::I8),
1450             sym::i16 => Some(PrimitiveType::I16),
1451             sym::i32 => Some(PrimitiveType::I32),
1452             sym::i64 => Some(PrimitiveType::I64),
1453             sym::i128 => Some(PrimitiveType::I128),
1454             sym::usize => Some(PrimitiveType::Usize),
1455             sym::u8 => Some(PrimitiveType::U8),
1456             sym::u16 => Some(PrimitiveType::U16),
1457             sym::u32 => Some(PrimitiveType::U32),
1458             sym::u64 => Some(PrimitiveType::U64),
1459             sym::u128 => Some(PrimitiveType::U128),
1460             sym::bool => Some(PrimitiveType::Bool),
1461             sym::char => Some(PrimitiveType::Char),
1462             sym::str => Some(PrimitiveType::Str),
1463             sym::f32 => Some(PrimitiveType::F32),
1464             sym::f64 => Some(PrimitiveType::F64),
1465             sym::array => Some(PrimitiveType::Array),
1466             sym::slice => Some(PrimitiveType::Slice),
1467             sym::tuple => Some(PrimitiveType::Tuple),
1468             sym::unit => Some(PrimitiveType::Unit),
1469             sym::pointer => Some(PrimitiveType::RawPointer),
1470             sym::reference => Some(PrimitiveType::Reference),
1471             kw::Fn => Some(PrimitiveType::Fn),
1472             sym::never => Some(PrimitiveType::Never),
1473             _ => None,
1474         }
1475     }
1476
1477     crate fn as_str(&self) -> &'static str {
1478         use self::PrimitiveType::*;
1479         match *self {
1480             Isize => "isize",
1481             I8 => "i8",
1482             I16 => "i16",
1483             I32 => "i32",
1484             I64 => "i64",
1485             I128 => "i128",
1486             Usize => "usize",
1487             U8 => "u8",
1488             U16 => "u16",
1489             U32 => "u32",
1490             U64 => "u64",
1491             U128 => "u128",
1492             F32 => "f32",
1493             F64 => "f64",
1494             Str => "str",
1495             Bool => "bool",
1496             Char => "char",
1497             Array => "array",
1498             Slice => "slice",
1499             Tuple => "tuple",
1500             Unit => "unit",
1501             RawPointer => "pointer",
1502             Reference => "reference",
1503             Fn => "fn",
1504             Never => "never",
1505         }
1506     }
1507
1508     crate fn impls(&self, tcx: TyCtxt<'_>) -> &'static SmallVec<[DefId; 4]> {
1509         Self::all_impls(tcx).get(self).expect("missing impl for primitive type")
1510     }
1511
1512     crate fn all_impls(tcx: TyCtxt<'_>) -> &'static FxHashMap<PrimitiveType, SmallVec<[DefId; 4]>> {
1513         static CELL: OnceCell<FxHashMap<PrimitiveType, SmallVec<[DefId; 4]>>> = OnceCell::new();
1514
1515         CELL.get_or_init(move || {
1516             use self::PrimitiveType::*;
1517
1518             /// A macro to create a FxHashMap.
1519             ///
1520             /// Example:
1521             ///
1522             /// ```
1523             /// let letters = map!{"a" => "b", "c" => "d"};
1524             /// ```
1525             ///
1526             /// Trailing commas are allowed.
1527             /// Commas between elements are required (even if the expression is a block).
1528             macro_rules! map {
1529                 ($( $key: expr => $val: expr ),* $(,)*) => {{
1530                     let mut map = ::rustc_data_structures::fx::FxHashMap::default();
1531                     $( map.insert($key, $val); )*
1532                     map
1533                 }}
1534             }
1535
1536             let single = |a: Option<DefId>| a.into_iter().collect();
1537             let both = |a: Option<DefId>, b: Option<DefId>| -> SmallVec<_> {
1538                 a.into_iter().chain(b).collect()
1539             };
1540
1541             let lang_items = tcx.lang_items();
1542             map! {
1543                 Isize => single(lang_items.isize_impl()),
1544                 I8 => single(lang_items.i8_impl()),
1545                 I16 => single(lang_items.i16_impl()),
1546                 I32 => single(lang_items.i32_impl()),
1547                 I64 => single(lang_items.i64_impl()),
1548                 I128 => single(lang_items.i128_impl()),
1549                 Usize => single(lang_items.usize_impl()),
1550                 U8 => single(lang_items.u8_impl()),
1551                 U16 => single(lang_items.u16_impl()),
1552                 U32 => single(lang_items.u32_impl()),
1553                 U64 => single(lang_items.u64_impl()),
1554                 U128 => single(lang_items.u128_impl()),
1555                 F32 => both(lang_items.f32_impl(), lang_items.f32_runtime_impl()),
1556                 F64 => both(lang_items.f64_impl(), lang_items.f64_runtime_impl()),
1557                 Char => single(lang_items.char_impl()),
1558                 Bool => single(lang_items.bool_impl()),
1559                 Str => both(lang_items.str_impl(), lang_items.str_alloc_impl()),
1560                 Slice => {
1561                     lang_items
1562                         .slice_impl()
1563                         .into_iter()
1564                         .chain(lang_items.slice_u8_impl())
1565                         .chain(lang_items.slice_alloc_impl())
1566                         .chain(lang_items.slice_u8_alloc_impl())
1567                         .collect()
1568                 },
1569                 Array => single(lang_items.array_impl()),
1570                 Tuple => smallvec![],
1571                 Unit => smallvec![],
1572                 RawPointer => {
1573                     lang_items
1574                         .const_ptr_impl()
1575                         .into_iter()
1576                         .chain(lang_items.mut_ptr_impl())
1577                         .chain(lang_items.const_slice_ptr_impl())
1578                         .chain(lang_items.mut_slice_ptr_impl())
1579                         .collect()
1580                 },
1581                 Reference => smallvec![],
1582                 Fn => smallvec![],
1583                 Never => smallvec![],
1584             }
1585         })
1586     }
1587
1588     crate fn to_url_str(&self) -> &'static str {
1589         self.as_str()
1590     }
1591
1592     crate fn as_sym(&self) -> Symbol {
1593         use PrimitiveType::*;
1594         match self {
1595             Isize => sym::isize,
1596             I8 => sym::i8,
1597             I16 => sym::i16,
1598             I32 => sym::i32,
1599             I64 => sym::i64,
1600             I128 => sym::i128,
1601             Usize => sym::usize,
1602             U8 => sym::u8,
1603             U16 => sym::u16,
1604             U32 => sym::u32,
1605             U64 => sym::u64,
1606             U128 => sym::u128,
1607             F32 => sym::f32,
1608             F64 => sym::f64,
1609             Str => sym::str,
1610             Bool => sym::bool,
1611             Char => sym::char,
1612             Array => sym::array,
1613             Slice => sym::slice,
1614             Tuple => sym::tuple,
1615             Unit => sym::unit,
1616             RawPointer => sym::pointer,
1617             Reference => sym::reference,
1618             Fn => kw::Fn,
1619             Never => sym::never,
1620         }
1621     }
1622 }
1623
1624 impl From<ast::IntTy> for PrimitiveType {
1625     fn from(int_ty: ast::IntTy) -> PrimitiveType {
1626         match int_ty {
1627             ast::IntTy::Isize => PrimitiveType::Isize,
1628             ast::IntTy::I8 => PrimitiveType::I8,
1629             ast::IntTy::I16 => PrimitiveType::I16,
1630             ast::IntTy::I32 => PrimitiveType::I32,
1631             ast::IntTy::I64 => PrimitiveType::I64,
1632             ast::IntTy::I128 => PrimitiveType::I128,
1633         }
1634     }
1635 }
1636
1637 impl From<ast::UintTy> for PrimitiveType {
1638     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
1639         match uint_ty {
1640             ast::UintTy::Usize => PrimitiveType::Usize,
1641             ast::UintTy::U8 => PrimitiveType::U8,
1642             ast::UintTy::U16 => PrimitiveType::U16,
1643             ast::UintTy::U32 => PrimitiveType::U32,
1644             ast::UintTy::U64 => PrimitiveType::U64,
1645             ast::UintTy::U128 => PrimitiveType::U128,
1646         }
1647     }
1648 }
1649
1650 impl From<ast::FloatTy> for PrimitiveType {
1651     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
1652         match float_ty {
1653             ast::FloatTy::F32 => PrimitiveType::F32,
1654             ast::FloatTy::F64 => PrimitiveType::F64,
1655         }
1656     }
1657 }
1658
1659 impl From<hir::PrimTy> for PrimitiveType {
1660     fn from(prim_ty: hir::PrimTy) -> PrimitiveType {
1661         match prim_ty {
1662             hir::PrimTy::Int(int_ty) => int_ty.into(),
1663             hir::PrimTy::Uint(uint_ty) => uint_ty.into(),
1664             hir::PrimTy::Float(float_ty) => float_ty.into(),
1665             hir::PrimTy::Str => PrimitiveType::Str,
1666             hir::PrimTy::Bool => PrimitiveType::Bool,
1667             hir::PrimTy::Char => PrimitiveType::Char,
1668         }
1669     }
1670 }
1671
1672 #[derive(Copy, Clone, Debug)]
1673 crate enum Visibility {
1674     Public,
1675     Inherited,
1676     Restricted(DefId),
1677 }
1678
1679 impl Visibility {
1680     crate fn is_public(&self) -> bool {
1681         matches!(self, Visibility::Public)
1682     }
1683 }
1684
1685 #[derive(Clone, Debug)]
1686 crate struct Struct {
1687     crate struct_type: CtorKind,
1688     crate generics: Generics,
1689     crate fields: Vec<Item>,
1690     crate fields_stripped: bool,
1691 }
1692
1693 #[derive(Clone, Debug)]
1694 crate struct Union {
1695     crate generics: Generics,
1696     crate fields: Vec<Item>,
1697     crate fields_stripped: bool,
1698 }
1699
1700 /// This is a more limited form of the standard Struct, different in that
1701 /// it lacks the things most items have (name, id, parameterization). Found
1702 /// only as a variant in an enum.
1703 #[derive(Clone, Debug)]
1704 crate struct VariantStruct {
1705     crate struct_type: CtorKind,
1706     crate fields: Vec<Item>,
1707     crate fields_stripped: bool,
1708 }
1709
1710 #[derive(Clone, Debug)]
1711 crate struct Enum {
1712     crate variants: IndexVec<VariantIdx, Item>,
1713     crate generics: Generics,
1714     crate variants_stripped: bool,
1715 }
1716
1717 #[derive(Clone, Debug)]
1718 crate enum Variant {
1719     CLike,
1720     Tuple(Vec<Type>),
1721     Struct(VariantStruct),
1722 }
1723
1724 /// Small wrapper around `rustc_span::Span` that adds helper methods and enforces calling `source_callsite`.
1725 #[derive(Clone, Debug)]
1726 crate struct Span(rustc_span::Span);
1727
1728 impl Span {
1729     crate fn from_rustc_span(sp: rustc_span::Span) -> Self {
1730         // Get the macro invocation instead of the definition,
1731         // in case the span is result of a macro expansion.
1732         // (See rust-lang/rust#39726)
1733         Self(sp.source_callsite())
1734     }
1735
1736     crate fn dummy() -> Self {
1737         Self(rustc_span::DUMMY_SP)
1738     }
1739
1740     crate fn span(&self) -> rustc_span::Span {
1741         self.0
1742     }
1743
1744     crate fn filename(&self, sess: &Session) -> FileName {
1745         sess.source_map().span_to_filename(self.0)
1746     }
1747
1748     crate fn lo(&self, sess: &Session) -> Loc {
1749         sess.source_map().lookup_char_pos(self.0.lo())
1750     }
1751
1752     crate fn hi(&self, sess: &Session) -> Loc {
1753         sess.source_map().lookup_char_pos(self.0.hi())
1754     }
1755
1756     crate fn cnum(&self, sess: &Session) -> CrateNum {
1757         // FIXME: is there a time when the lo and hi crate would be different?
1758         self.lo(sess).file.cnum
1759     }
1760 }
1761
1762 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1763 crate struct Path {
1764     crate global: bool,
1765     crate res: Res,
1766     crate segments: Vec<PathSegment>,
1767 }
1768
1769 impl Path {
1770     crate fn last(&self) -> Symbol {
1771         self.segments.last().expect("segments were empty").name
1772     }
1773
1774     crate fn last_name(&self) -> SymbolStr {
1775         self.segments.last().expect("segments were empty").name.as_str()
1776     }
1777
1778     crate fn whole_name(&self) -> String {
1779         String::from(if self.global { "::" } else { "" })
1780             + &self.segments.iter().map(|s| s.name.to_string()).collect::<Vec<_>>().join("::")
1781     }
1782 }
1783
1784 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1785 crate enum GenericArg {
1786     Lifetime(Lifetime),
1787     Type(Type),
1788     Const(Constant),
1789 }
1790
1791 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1792 crate enum GenericArgs {
1793     AngleBracketed { args: Vec<GenericArg>, bindings: Vec<TypeBinding> },
1794     Parenthesized { inputs: Vec<Type>, output: Option<Type> },
1795 }
1796
1797 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1798 crate struct PathSegment {
1799     crate name: Symbol,
1800     crate args: GenericArgs,
1801 }
1802
1803 #[derive(Clone, Debug)]
1804 crate struct Typedef {
1805     crate type_: Type,
1806     crate generics: Generics,
1807     /// `type_` can come from either the HIR or from metadata. If it comes from HIR, it may be a type
1808     /// alias instead of the final type. This will always have the final type, regardless of whether
1809     /// `type_` came from HIR or from metadata.
1810     ///
1811     /// If `item_type.is_none()`, `type_` is guarenteed to come from metadata (and therefore hold the
1812     /// final type).
1813     crate item_type: Option<Type>,
1814 }
1815
1816 impl GetDefId for Typedef {
1817     fn def_id(&self, cache: &Cache) -> Option<DefId> {
1818         self.type_.def_id(cache)
1819     }
1820 }
1821
1822 #[derive(Clone, Debug)]
1823 crate struct OpaqueTy {
1824     crate bounds: Vec<GenericBound>,
1825     crate generics: Generics,
1826 }
1827
1828 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1829 crate struct BareFunctionDecl {
1830     crate unsafety: hir::Unsafety,
1831     crate generic_params: Vec<GenericParamDef>,
1832     crate decl: FnDecl,
1833     crate abi: Abi,
1834 }
1835
1836 #[derive(Clone, Debug)]
1837 crate struct Static {
1838     crate type_: Type,
1839     crate mutability: Mutability,
1840     /// It's useful to have the value of a static documented, but I have no
1841     /// desire to represent expressions (that'd basically be all of the AST,
1842     /// which is huge!). So, have a string.
1843     crate expr: String,
1844 }
1845
1846 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
1847 crate struct Constant {
1848     crate type_: Type,
1849     crate expr: String,
1850     crate value: Option<String>,
1851     crate is_literal: bool,
1852 }
1853
1854 #[derive(Clone, Debug)]
1855 crate struct Impl {
1856     crate unsafety: hir::Unsafety,
1857     crate generics: Generics,
1858     crate provided_trait_methods: FxHashSet<Symbol>,
1859     crate trait_: Option<Type>,
1860     crate for_: Type,
1861     crate items: Vec<Item>,
1862     crate negative_polarity: bool,
1863     crate synthetic: bool,
1864     crate blanket_impl: Option<Type>,
1865 }
1866
1867 #[derive(Clone, Debug)]
1868 crate struct Import {
1869     crate kind: ImportKind,
1870     crate source: ImportSource,
1871     crate should_be_displayed: bool,
1872 }
1873
1874 impl Import {
1875     crate fn new_simple(name: Symbol, source: ImportSource, should_be_displayed: bool) -> Self {
1876         Self { kind: ImportKind::Simple(name), source, should_be_displayed }
1877     }
1878
1879     crate fn new_glob(source: ImportSource, should_be_displayed: bool) -> Self {
1880         Self { kind: ImportKind::Glob, source, should_be_displayed }
1881     }
1882 }
1883
1884 #[derive(Clone, Debug)]
1885 crate enum ImportKind {
1886     // use source as str;
1887     Simple(Symbol),
1888     // use source::*;
1889     Glob,
1890 }
1891
1892 #[derive(Clone, Debug)]
1893 crate struct ImportSource {
1894     crate path: Path,
1895     crate did: Option<DefId>,
1896 }
1897
1898 #[derive(Clone, Debug)]
1899 crate struct Macro {
1900     crate source: String,
1901     crate imported_from: Option<Symbol>,
1902 }
1903
1904 #[derive(Clone, Debug)]
1905 crate struct ProcMacro {
1906     crate kind: MacroKind,
1907     crate helpers: Vec<Symbol>,
1908 }
1909
1910 /// An type binding on an associated type (e.g., `A = Bar` in `Foo<A = Bar>` or
1911 /// `A: Send + Sync` in `Foo<A: Send + Sync>`).
1912 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1913 crate struct TypeBinding {
1914     crate name: Symbol,
1915     crate kind: TypeBindingKind,
1916 }
1917
1918 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1919 crate enum TypeBindingKind {
1920     Equality { ty: Type },
1921     Constraint { bounds: Vec<GenericBound> },
1922 }
1923
1924 impl TypeBinding {
1925     crate fn ty(&self) -> &Type {
1926         match self.kind {
1927             TypeBindingKind::Equality { ref ty } => ty,
1928             _ => panic!("expected equality type binding for parenthesized generic args"),
1929         }
1930     }
1931 }