src/librustdoc/clean/mod.rs

   1 // ignore-tidy-filelength
   2
   3 //! This module contains the "cleaned" pieces of the AST, and the functions
   4 //! that clean them.
   5
   6 pub mod inline;
   7 pub mod cfg;
   8 mod simplify;
   9 mod auto_trait;
  10 mod blanket_impl;
  11
  12 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
  13 use rustc_target::spec::abi::Abi;
  14 use rustc_typeck::hir_ty_to_ty;
  15 use rustc::infer::region_constraints::{RegionConstraintData, Constraint};
  16 use rustc::middle::resolve_lifetime as rl;
  17 use rustc::middle::lang_items;
  18 use rustc::middle::stability;
  19 use rustc::mir::interpret::{GlobalId, ConstValue};
  20 use rustc::hir;
  21 use rustc::hir::def::{CtorKind, DefKind, Res};
  22 use rustc::hir::def_id::{CrateNum, DefId, CRATE_DEF_INDEX, LOCAL_CRATE};
  23 use rustc::hir::ptr::P;
  24 use rustc::ty::subst::{InternalSubsts, SubstsRef, GenericArgKind};
  25 use rustc::ty::{self, DefIdTree, TyCtxt, Region, RegionVid, Ty, AdtKind};
  26 use rustc::ty::fold::TypeFolder;
  27 use rustc::ty::layout::VariantIdx;
  28 use rustc::util::nodemap::{FxHashMap, FxHashSet};
  29 use syntax::ast::{self, AttrStyle, Ident};
  30 use syntax::attr;
  31 use syntax::ext::base::MacroKind;
  32 use syntax::source_map::DUMMY_SP;
  33 use syntax::symbol::{Symbol, kw, sym};
  34 use syntax::symbol::InternedString;
  35 use syntax_pos::{self, Pos, FileName};
  36
  37 use std::collections::hash_map::Entry;
  38 use std::fmt;
  39 use std::hash::{Hash, Hasher};
  40 use std::default::Default;
  41 use std::{mem, slice, vec};
  42 use std::iter::FromIterator;
  43 use std::rc::Rc;
  44 use std::cell::RefCell;
  45 use std::sync::Arc;
  46 use std::u32;
  47
  48 use crate::core::{self, DocContext, ImplTraitParam};
  49 use crate::doctree;
  50 use crate::html::render::{cache, ExternalLocation};
  51 use crate::html::item_type::ItemType;
  52
  53
  54 use self::cfg::Cfg;
  55 use self::auto_trait::AutoTraitFinder;
  56 use self::blanket_impl::BlanketImplFinder;
  57
  58 pub use self::Type::*;
  59 pub use self::Mutability::*;
  60 pub use self::ItemEnum::*;
  61 pub use self::SelfTy::*;
  62 pub use self::FunctionRetTy::*;
  63 pub use self::Visibility::{Public, Inherited};
  64
  65 thread_local!(pub static MAX_DEF_ID: RefCell<FxHashMap<CrateNum, DefId>> = Default::default());
  66
  67 const FN_OUTPUT_NAME: &'static str = "Output";
  68
  69 // extract the stability index for a node from tcx, if possible
  70 fn get_stability(cx: &DocContext<'_>, def_id: DefId) -> Option<Stability> {
  71     cx.tcx.lookup_stability(def_id).clean(cx)
  72 }
  73
  74 fn get_deprecation(cx: &DocContext<'_>, def_id: DefId) -> Option<Deprecation> {
  75     cx.tcx.lookup_deprecation(def_id).clean(cx)
  76 }
  77
  78 pub trait Clean<T> {
  79     fn clean(&self, cx: &DocContext<'_>) -> T;
  80 }
  81
  82 impl<T: Clean<U>, U> Clean<Vec<U>> for [T] {
  83     fn clean(&self, cx: &DocContext<'_>) -> Vec<U> {
  84         self.iter().map(|x| x.clean(cx)).collect()
  85     }
  86 }
  87
  88 impl<T: Clean<U>, U, V: Idx> Clean<IndexVec<V, U>> for IndexVec<V, T> {
  89     fn clean(&self, cx: &DocContext<'_>) -> IndexVec<V, U> {
  90         self.iter().map(|x| x.clean(cx)).collect()
  91     }
  92 }
  93
  94 impl<T: Clean<U>, U> Clean<U> for P<T> {
  95     fn clean(&self, cx: &DocContext<'_>) -> U {
  96         (**self).clean(cx)
  97     }
  98 }
  99
 100 impl<T: Clean<U>, U> Clean<U> for Rc<T> {
 101     fn clean(&self, cx: &DocContext<'_>) -> U {
 102         (**self).clean(cx)
 103     }
 104 }
 105
 106 impl<T: Clean<U>, U> Clean<Option<U>> for Option<T> {
 107     fn clean(&self, cx: &DocContext<'_>) -> Option<U> {
 108         self.as_ref().map(|v| v.clean(cx))
 109     }
 110 }
 111
 112 impl<T, U> Clean<U> for ty::Binder<T> where T: Clean<U> {
 113     fn clean(&self, cx: &DocContext<'_>) -> U {
 114         self.skip_binder().clean(cx)
 115     }
 116 }
 117
 118 impl<T: Clean<U>, U> Clean<Vec<U>> for P<[T]> {
 119     fn clean(&self, cx: &DocContext<'_>) -> Vec<U> {
 120         self.iter().map(|x| x.clean(cx)).collect()
 121     }
 122 }
 123
 124 #[derive(Clone, Debug)]
 125 pub struct Crate {
 126     pub name: String,
 127     pub version: Option<String>,
 128     pub src: FileName,
 129     pub module: Option<Item>,
 130     pub externs: Vec<(CrateNum, ExternalCrate)>,
 131     pub primitives: Vec<(DefId, PrimitiveType, Attributes)>,
 132     // These are later on moved into `CACHEKEY`, leaving the map empty.
 133     // Only here so that they can be filtered through the rustdoc passes.
 134     pub external_traits: Rc<RefCell<FxHashMap<DefId, Trait>>>,
 135     pub masked_crates: FxHashSet<CrateNum>,
 136     pub collapsed: bool,
 137 }
 138
 139 pub fn krate(mut cx: &mut DocContext<'_>) -> Crate {
 140     use crate::visit_lib::LibEmbargoVisitor;
 141
 142     let krate = cx.tcx.hir().krate();
 143     let module = crate::visit_ast::RustdocVisitor::new(&mut cx).visit(krate);
 144
 145     let mut r = cx.renderinfo.get_mut();
 146     r.deref_trait_did = cx.tcx.lang_items().deref_trait();
 147     r.deref_mut_trait_did = cx.tcx.lang_items().deref_mut_trait();
 148     r.owned_box_did = cx.tcx.lang_items().owned_box();
 149
 150     let mut externs = Vec::new();
 151     for &cnum in cx.tcx.crates().iter() {
 152         externs.push((cnum, cnum.clean(cx)));
 153         // Analyze doc-reachability for extern items
 154         LibEmbargoVisitor::new(&mut cx).visit_lib(cnum);
 155     }
 156     externs.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
 157
 158     // Clean the crate, translating the entire libsyntax AST to one that is
 159     // understood by rustdoc.
 160     let mut module = module.clean(cx);
 161     let mut masked_crates = FxHashSet::default();
 162
 163     match module.inner {
 164         ModuleItem(ref module) => {
 165             for it in &module.items {
 166                 // `compiler_builtins` should be masked too, but we can't apply
 167                 // `#[doc(masked)]` to the injected `extern crate` because it's unstable.
 168                 if it.is_extern_crate()
 169                     && (it.attrs.has_doc_flag(sym::masked)
 170                         || cx.tcx.is_compiler_builtins(it.def_id.krate))
 171                 {
 172                     masked_crates.insert(it.def_id.krate);
 173                 }
 174             }
 175         }
 176         _ => unreachable!(),
 177     }
 178
 179     let ExternalCrate { name, src, primitives, keywords, .. } = LOCAL_CRATE.clean(cx);
 180     {
 181         let m = match module.inner {
 182             ModuleItem(ref mut m) => m,
 183             _ => unreachable!(),
 184         };
 185         m.items.extend(primitives.iter().map(|&(def_id, prim, ref attrs)| {
 186             Item {
 187                 source: Span::empty(),
 188                 name: Some(prim.to_url_str().to_string()),
 189                 attrs: attrs.clone(),
 190                 visibility: Public,
 191                 stability: get_stability(cx, def_id),
 192                 deprecation: get_deprecation(cx, def_id),
 193                 def_id,
 194                 inner: PrimitiveItem(prim),
 195             }
 196         }));
 197         m.items.extend(keywords.into_iter().map(|(def_id, kw, attrs)| {
 198             Item {
 199                 source: Span::empty(),
 200                 name: Some(kw.clone()),
 201                 attrs: attrs,
 202                 visibility: Public,
 203                 stability: get_stability(cx, def_id),
 204                 deprecation: get_deprecation(cx, def_id),
 205                 def_id,
 206                 inner: KeywordItem(kw),
 207             }
 208         }));
 209     }
 210
 211     Crate {
 212         name,
 213         version: None,
 214         src,
 215         module: Some(module),
 216         externs,
 217         primitives,
 218         external_traits: cx.external_traits.clone(),
 219         masked_crates,
 220         collapsed: false,
 221     }
 222 }
 223
 224 #[derive(Clone, Debug)]
 225 pub struct ExternalCrate {
 226     pub name: String,
 227     pub src: FileName,
 228     pub attrs: Attributes,
 229     pub primitives: Vec<(DefId, PrimitiveType, Attributes)>,
 230     pub keywords: Vec<(DefId, String, Attributes)>,
 231 }
 232
 233 impl Clean<ExternalCrate> for CrateNum {
 234     fn clean(&self, cx: &DocContext<'_>) -> ExternalCrate {
 235         let root = DefId { krate: *self, index: CRATE_DEF_INDEX };
 236         let krate_span = cx.tcx.def_span(root);
 237         let krate_src = cx.sess().source_map().span_to_filename(krate_span);
 238
 239         // Collect all inner modules which are tagged as implementations of
 240         // primitives.
 241         //
 242         // Note that this loop only searches the top-level items of the crate,
 243         // and this is intentional. If we were to search the entire crate for an
 244         // item tagged with `#[doc(primitive)]` then we would also have to
 245         // search the entirety of external modules for items tagged
 246         // `#[doc(primitive)]`, which is a pretty inefficient process (decoding
 247         // all that metadata unconditionally).
 248         //
 249         // In order to keep the metadata load under control, the
 250         // `#[doc(primitive)]` feature is explicitly designed to only allow the
 251         // primitive tags to show up as the top level items in a crate.
 252         //
 253         // Also note that this does not attempt to deal with modules tagged
 254         // duplicately for the same primitive. This is handled later on when
 255         // rendering by delegating everything to a hash map.
 256         let as_primitive = |res: Res| {
 257             if let Res::Def(DefKind::Mod, def_id) = res {
 258                 let attrs = cx.tcx.get_attrs(def_id).clean(cx);
 259                 let mut prim = None;
 260                 for attr in attrs.lists(sym::doc) {
 261                     if let Some(v) = attr.value_str() {
 262                         if attr.check_name(sym::primitive) {
 263                             prim = PrimitiveType::from_str(&v.as_str());
 264                             if prim.is_some() {
 265                                 break;
 266                             }
 267                             // FIXME: should warn on unknown primitives?
 268                         }
 269                     }
 270                 }
 271                 return prim.map(|p| (def_id, p, attrs));
 272             }
 273             None
 274         };
 275         let primitives = if root.is_local() {
 276             cx.tcx.hir().krate().module.item_ids.iter().filter_map(|&id| {
 277                 let item = cx.tcx.hir().expect_item(id.id);
 278                 match item.node {
 279                     hir::ItemKind::Mod(_) => {
 280                         as_primitive(Res::Def(
 281                             DefKind::Mod,
 282                             cx.tcx.hir().local_def_id(id.id),
 283                         ))
 284                     }
 285                     hir::ItemKind::Use(ref path, hir::UseKind::Single)
 286                     if item.vis.node.is_pub() => {
 287                         as_primitive(path.res).map(|(_, prim, attrs)| {
 288                             // Pretend the primitive is local.
 289                             (cx.tcx.hir().local_def_id(id.id), prim, attrs)
 290                         })
 291                     }
 292                     _ => None
 293                 }
 294             }).collect()
 295         } else {
 296             cx.tcx.item_children(root).iter().map(|item| item.res)
 297               .filter_map(as_primitive).collect()
 298         };
 299
 300         let as_keyword = |res: Res| {
 301             if let Res::Def(DefKind::Mod, def_id) = res {
 302                 let attrs = cx.tcx.get_attrs(def_id).clean(cx);
 303                 let mut keyword = None;
 304                 for attr in attrs.lists(sym::doc) {
 305                     if let Some(v) = attr.value_str() {
 306                         if attr.check_name(sym::keyword) {
 307                             if v.is_doc_keyword() {
 308                                 keyword = Some(v.to_string());
 309                                 break;
 310                             }
 311                             // FIXME: should warn on unknown keywords?
 312                         }
 313                     }
 314                 }
 315                 return keyword.map(|p| (def_id, p, attrs));
 316             }
 317             None
 318         };
 319         let keywords = if root.is_local() {
 320             cx.tcx.hir().krate().module.item_ids.iter().filter_map(|&id| {
 321                 let item = cx.tcx.hir().expect_item(id.id);
 322                 match item.node {
 323                     hir::ItemKind::Mod(_) => {
 324                         as_keyword(Res::Def(
 325                             DefKind::Mod,
 326                             cx.tcx.hir().local_def_id(id.id),
 327                         ))
 328                     }
 329                     hir::ItemKind::Use(ref path, hir::UseKind::Single)
 330                     if item.vis.node.is_pub() => {
 331                         as_keyword(path.res).map(|(_, prim, attrs)| {
 332                             (cx.tcx.hir().local_def_id(id.id), prim, attrs)
 333                         })
 334                     }
 335                     _ => None
 336                 }
 337             }).collect()
 338         } else {
 339             cx.tcx.item_children(root).iter().map(|item| item.res)
 340               .filter_map(as_keyword).collect()
 341         };
 342
 343         ExternalCrate {
 344             name: cx.tcx.crate_name(*self).to_string(),
 345             src: krate_src,
 346             attrs: cx.tcx.get_attrs(root).clean(cx),
 347             primitives,
 348             keywords,
 349         }
 350     }
 351 }
 352
 353 /// Anything with a source location and set of attributes and, optionally, a
 354 /// name. That is, anything that can be documented. This doesn't correspond
 355 /// directly to the AST's concept of an item; it's a strict superset.
 356 #[derive(Clone)]
 357 pub struct Item {
 358     /// Stringified span
 359     pub source: Span,
 360     /// Not everything has a name. E.g., impls
 361     pub name: Option<String>,
 362     pub attrs: Attributes,
 363     pub inner: ItemEnum,
 364     pub visibility: Visibility,
 365     pub def_id: DefId,
 366     pub stability: Option<Stability>,
 367     pub deprecation: Option<Deprecation>,
 368 }
 369
 370 impl fmt::Debug for Item {
 371     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 372
 373         let fake = MAX_DEF_ID.with(|m| m.borrow().get(&self.def_id.krate)
 374                                    .map(|id| self.def_id >= *id).unwrap_or(false));
 375         let def_id: &dyn fmt::Debug = if fake { &"**FAKE**" } else { &self.def_id };
 376
 377         fmt.debug_struct("Item")
 378             .field("source", &self.source)
 379             .field("name", &self.name)
 380             .field("attrs", &self.attrs)
 381             .field("inner", &self.inner)
 382             .field("visibility", &self.visibility)
 383             .field("def_id", def_id)
 384             .field("stability", &self.stability)
 385             .field("deprecation", &self.deprecation)
 386             .finish()
 387     }
 388 }
 389
 390 impl Item {
 391     /// Finds the `doc` attribute as a NameValue and returns the corresponding
 392     /// value found.
 393     pub fn doc_value(&self) -> Option<&str> {
 394         self.attrs.doc_value()
 395     }
 396     /// Finds all `doc` attributes as NameValues and returns their corresponding values, joined
 397     /// with newlines.
 398     pub fn collapsed_doc_value(&self) -> Option<String> {
 399         self.attrs.collapsed_doc_value()
 400     }
 401
 402     pub fn links(&self) -> Vec<(String, String)> {
 403         self.attrs.links(&self.def_id.krate)
 404     }
 405
 406     pub fn is_crate(&self) -> bool {
 407         match self.inner {
 408             StrippedItem(box ModuleItem(Module { is_crate: true, ..})) |
 409             ModuleItem(Module { is_crate: true, ..}) => true,
 410             _ => false,
 411         }
 412     }
 413     pub fn is_mod(&self) -> bool {
 414         self.type_() == ItemType::Module
 415     }
 416     pub fn is_trait(&self) -> bool {
 417         self.type_() == ItemType::Trait
 418     }
 419     pub fn is_struct(&self) -> bool {
 420         self.type_() == ItemType::Struct
 421     }
 422     pub fn is_enum(&self) -> bool {
 423         self.type_() == ItemType::Enum
 424     }
 425     pub fn is_variant(&self) -> bool {
 426         self.type_() == ItemType::Variant
 427     }
 428     pub fn is_associated_type(&self) -> bool {
 429         self.type_() == ItemType::AssocType
 430     }
 431     pub fn is_associated_const(&self) -> bool {
 432         self.type_() == ItemType::AssocConst
 433     }
 434     pub fn is_method(&self) -> bool {
 435         self.type_() == ItemType::Method
 436     }
 437     pub fn is_ty_method(&self) -> bool {
 438         self.type_() == ItemType::TyMethod
 439     }
 440     pub fn is_typedef(&self) -> bool {
 441         self.type_() == ItemType::Typedef
 442     }
 443     pub fn is_primitive(&self) -> bool {
 444         self.type_() == ItemType::Primitive
 445     }
 446     pub fn is_union(&self) -> bool {
 447         self.type_() == ItemType::Union
 448     }
 449     pub fn is_import(&self) -> bool {
 450         self.type_() == ItemType::Import
 451     }
 452     pub fn is_extern_crate(&self) -> bool {
 453         self.type_() == ItemType::ExternCrate
 454     }
 455     pub fn is_keyword(&self) -> bool {
 456         self.type_() == ItemType::Keyword
 457     }
 458
 459     pub fn is_stripped(&self) -> bool {
 460         match self.inner { StrippedItem(..) => true, _ => false }
 461     }
 462     pub fn has_stripped_fields(&self) -> Option<bool> {
 463         match self.inner {
 464             StructItem(ref _struct) => Some(_struct.fields_stripped),
 465             UnionItem(ref union) => Some(union.fields_stripped),
 466             VariantItem(Variant { kind: VariantKind::Struct(ref vstruct)} ) => {
 467                 Some(vstruct.fields_stripped)
 468             },
 469             _ => None,
 470         }
 471     }
 472
 473     pub fn stability_class(&self) -> Option<String> {
 474         self.stability.as_ref().and_then(|ref s| {
 475             let mut classes = Vec::with_capacity(2);
 476
 477             if s.level == stability::Unstable {
 478                 classes.push("unstable");
 479             }
 480
 481             if s.deprecation.is_some() {
 482                 classes.push("deprecated");
 483             }
 484
 485             if classes.len() != 0 {
 486                 Some(classes.join(" "))
 487             } else {
 488                 None
 489             }
 490         })
 491     }
 492
 493     pub fn stable_since(&self) -> Option<&str> {
 494         self.stability.as_ref().map(|s| &s.since[..])
 495     }
 496
 497     pub fn is_non_exhaustive(&self) -> bool {
 498         self.attrs.other_attrs.iter()
 499             .any(|a| a.check_name(sym::non_exhaustive))
 500     }
 501
 502     /// Returns a documentation-level item type from the item.
 503     pub fn type_(&self) -> ItemType {
 504         ItemType::from(self)
 505     }
 506
 507     /// Returns the info in the item's `#[deprecated]` or `#[rustc_deprecated]` attributes.
 508     ///
 509     /// If the item is not deprecated, returns `None`.
 510     pub fn deprecation(&self) -> Option<&Deprecation> {
 511         self.deprecation
 512             .as_ref()
 513             .or_else(|| self.stability.as_ref().and_then(|s| s.deprecation.as_ref()))
 514     }
 515     pub fn is_default(&self) -> bool {
 516         match self.inner {
 517             ItemEnum::MethodItem(ref meth) => {
 518                 if let Some(defaultness) = meth.defaultness {
 519                     defaultness.has_value() && !defaultness.is_final()
 520                 } else {
 521                     false
 522                 }
 523             }
 524             _ => false,
 525         }
 526     }
 527 }
 528
 529 #[derive(Clone, Debug)]
 530 pub enum ItemEnum {
 531     ExternCrateItem(String, Option<String>),
 532     ImportItem(Import),
 533     StructItem(Struct),
 534     UnionItem(Union),
 535     EnumItem(Enum),
 536     FunctionItem(Function),
 537     ModuleItem(Module),
 538     TypedefItem(Typedef, bool /* is associated type */),
 539     OpaqueTyItem(OpaqueTy, bool /* is associated type */),
 540     StaticItem(Static),
 541     ConstantItem(Constant),
 542     TraitItem(Trait),
 543     TraitAliasItem(TraitAlias),
 544     ImplItem(Impl),
 545     /// A method signature only. Used for required methods in traits (ie,
 546     /// non-default-methods).
 547     TyMethodItem(TyMethod),
 548     /// A method with a body.
 549     MethodItem(Method),
 550     StructFieldItem(Type),
 551     VariantItem(Variant),
 552     /// `fn`s from an extern block
 553     ForeignFunctionItem(Function),
 554     /// `static`s from an extern block
 555     ForeignStaticItem(Static),
 556     /// `type`s from an extern block
 557     ForeignTypeItem,
 558     MacroItem(Macro),
 559     ProcMacroItem(ProcMacro),
 560     PrimitiveItem(PrimitiveType),
 561     AssocConstItem(Type, Option<String>),
 562     AssocTypeItem(Vec<GenericBound>, Option<Type>),
 563     /// An item that has been stripped by a rustdoc pass
 564     StrippedItem(Box<ItemEnum>),
 565     KeywordItem(String),
 566 }
 567
 568 impl ItemEnum {
 569     pub fn is_associated(&self) -> bool {
 570         match *self {
 571             ItemEnum::TypedefItem(_, _) |
 572             ItemEnum::AssocTypeItem(_, _) => true,
 573             _ => false,
 574         }
 575     }
 576 }
 577
 578 #[derive(Clone, Debug)]
 579 pub struct Module {
 580     pub items: Vec<Item>,
 581     pub is_crate: bool,
 582 }
 583
 584 impl Clean<Item> for doctree::Module<'_> {
 585     fn clean(&self, cx: &DocContext<'_>) -> Item {
 586         let name = if self.name.is_some() {
 587             self.name.expect("No name provided").clean(cx)
 588         } else {
 589             String::new()
 590         };
 591
 592         // maintain a stack of mod ids, for doc comment path resolution
 593         // but we also need to resolve the module's own docs based on whether its docs were written
 594         // inside or outside the module, so check for that
 595         let attrs = self.attrs.clean(cx);
 596
 597         let mut items: Vec<Item> = vec![];
 598         items.extend(self.extern_crates.iter().flat_map(|x| x.clean(cx)));
 599         items.extend(self.imports.iter().flat_map(|x| x.clean(cx)));
 600         items.extend(self.structs.iter().map(|x| x.clean(cx)));
 601         items.extend(self.unions.iter().map(|x| x.clean(cx)));
 602         items.extend(self.enums.iter().map(|x| x.clean(cx)));
 603         items.extend(self.fns.iter().map(|x| x.clean(cx)));
 604         items.extend(self.foreigns.iter().map(|x| x.clean(cx)));
 605         items.extend(self.mods.iter().map(|x| x.clean(cx)));
 606         items.extend(self.typedefs.iter().map(|x| x.clean(cx)));
 607         items.extend(self.opaque_tys.iter().map(|x| x.clean(cx)));
 608         items.extend(self.statics.iter().map(|x| x.clean(cx)));
 609         items.extend(self.constants.iter().map(|x| x.clean(cx)));
 610         items.extend(self.traits.iter().map(|x| x.clean(cx)));
 611         items.extend(self.impls.iter().flat_map(|x| x.clean(cx)));
 612         items.extend(self.macros.iter().map(|x| x.clean(cx)));
 613         items.extend(self.proc_macros.iter().map(|x| x.clean(cx)));
 614         items.extend(self.trait_aliases.iter().map(|x| x.clean(cx)));
 615
 616         // determine if we should display the inner contents or
 617         // the outer `mod` item for the source code.
 618         let whence = {
 619             let cm = cx.sess().source_map();
 620             let outer = cm.lookup_char_pos(self.where_outer.lo());
 621             let inner = cm.lookup_char_pos(self.where_inner.lo());
 622             if outer.file.start_pos == inner.file.start_pos {
 623                 // mod foo { ... }
 624                 self.where_outer
 625             } else {
 626                 // mod foo; (and a separate SourceFile for the contents)
 627                 self.where_inner
 628             }
 629         };
 630
 631         Item {
 632             name: Some(name),
 633             attrs,
 634             source: whence.clean(cx),
 635             visibility: self.vis.clean(cx),
 636             stability: cx.stability(self.id).clean(cx),
 637             deprecation: cx.deprecation(self.id).clean(cx),
 638             def_id: cx.tcx.hir().local_def_id(self.id),
 639             inner: ModuleItem(Module {
 640                is_crate: self.is_crate,
 641                items,
 642             })
 643         }
 644     }
 645 }
 646
 647 pub struct ListAttributesIter<'a> {
 648     attrs: slice::Iter<'a, ast::Attribute>,
 649     current_list: vec::IntoIter<ast::NestedMetaItem>,
 650     name: Symbol,
 651 }
 652
 653 impl<'a> Iterator for ListAttributesIter<'a> {
 654     type Item = ast::NestedMetaItem;
 655
 656     fn next(&mut self) -> Option<Self::Item> {
 657         if let Some(nested) = self.current_list.next() {
 658             return Some(nested);
 659         }
 660
 661         for attr in &mut self.attrs {
 662             if let Some(list) = attr.meta_item_list() {
 663                 if attr.check_name(self.name) {
 664                     self.current_list = list.into_iter();
 665                     if let Some(nested) = self.current_list.next() {
 666                         return Some(nested);
 667                     }
 668                 }
 669             }
 670         }
 671
 672         None
 673     }
 674
 675     fn size_hint(&self) -> (usize, Option<usize>) {
 676         let lower = self.current_list.len();
 677         (lower, None)
 678     }
 679 }
 680
 681 pub trait AttributesExt {
 682     /// Finds an attribute as List and returns the list of attributes nested inside.
 683     fn lists(&self, name: Symbol) -> ListAttributesIter<'_>;
 684 }
 685
 686 impl AttributesExt for [ast::Attribute] {
 687     fn lists(&self, name: Symbol) -> ListAttributesIter<'_> {
 688         ListAttributesIter {
 689             attrs: self.iter(),
 690             current_list: Vec::new().into_iter(),
 691             name,
 692         }
 693     }
 694 }
 695
 696 pub trait NestedAttributesExt {
 697     /// Returns `true` if the attribute list contains a specific `Word`
 698     fn has_word(self, word: Symbol) -> bool;
 699 }
 700
 701 impl<I: IntoIterator<Item=ast::NestedMetaItem>> NestedAttributesExt for I {
 702     fn has_word(self, word: Symbol) -> bool {
 703         self.into_iter().any(|attr| attr.is_word() && attr.check_name(word))
 704     }
 705 }
 706
 707 /// A portion of documentation, extracted from a `#[doc]` attribute.
 708 ///
 709 /// Each variant contains the line number within the complete doc-comment where the fragment
 710 /// starts, as well as the Span where the corresponding doc comment or attribute is located.
 711 ///
 712 /// Included files are kept separate from inline doc comments so that proper line-number
 713 /// information can be given when a doctest fails. Sugared doc comments and "raw" doc comments are
 714 /// kept separate because of issue #42760.
 715 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 716 pub enum DocFragment {
 717     /// A doc fragment created from a `///` or `//!` doc comment.
 718     SugaredDoc(usize, syntax_pos::Span, String),
 719     /// A doc fragment created from a "raw" `#[doc=""]` attribute.
 720     RawDoc(usize, syntax_pos::Span, String),
 721     /// A doc fragment created from a `#[doc(include="filename")]` attribute. Contains both the
 722     /// given filename and the file contents.
 723     Include(usize, syntax_pos::Span, String, String),
 724 }
 725
 726 impl DocFragment {
 727     pub fn as_str(&self) -> &str {
 728         match *self {
 729             DocFragment::SugaredDoc(_, _, ref s) => &s[..],
 730             DocFragment::RawDoc(_, _, ref s) => &s[..],
 731             DocFragment::Include(_, _, _, ref s) => &s[..],
 732         }
 733     }
 734
 735     pub fn span(&self) -> syntax_pos::Span {
 736         match *self {
 737             DocFragment::SugaredDoc(_, span, _) |
 738                 DocFragment::RawDoc(_, span, _) |
 739                 DocFragment::Include(_, span, _, _) => span,
 740         }
 741     }
 742 }
 743
 744 impl<'a> FromIterator<&'a DocFragment> for String {
 745     fn from_iter<T>(iter: T) -> Self
 746     where
 747         T: IntoIterator<Item = &'a DocFragment>
 748     {
 749         iter.into_iter().fold(String::new(), |mut acc, frag| {
 750             if !acc.is_empty() {
 751                 acc.push('\n');
 752             }
 753             match *frag {
 754                 DocFragment::SugaredDoc(_, _, ref docs)
 755                     | DocFragment::RawDoc(_, _, ref docs)
 756                     | DocFragment::Include(_, _, _, ref docs) =>
 757                     acc.push_str(docs),
 758             }
 759
 760             acc
 761         })
 762     }
 763 }
 764
 765 #[derive(Clone, Debug, Default)]
 766 pub struct Attributes {
 767     pub doc_strings: Vec<DocFragment>,
 768     pub other_attrs: Vec<ast::Attribute>,
 769     pub cfg: Option<Arc<Cfg>>,
 770     pub span: Option<syntax_pos::Span>,
 771     /// map from Rust paths to resolved defs and potential URL fragments
 772     pub links: Vec<(String, Option<DefId>, Option<String>)>,
 773     pub inner_docs: bool,
 774 }
 775
 776 impl Attributes {
 777     /// Extracts the content from an attribute `#[doc(cfg(content))]`.
 778     fn extract_cfg(mi: &ast::MetaItem) -> Option<&ast::MetaItem> {
 779         use syntax::ast::NestedMetaItem::MetaItem;
 780
 781         if let ast::MetaItemKind::List(ref nmis) = mi.node {
 782             if nmis.len() == 1 {
 783                 if let MetaItem(ref cfg_mi) = nmis[0] {
 784                     if cfg_mi.check_name(sym::cfg) {
 785                         if let ast::MetaItemKind::List(ref cfg_nmis) = cfg_mi.node {
 786                             if cfg_nmis.len() == 1 {
 787                                 if let MetaItem(ref content_mi) = cfg_nmis[0] {
 788                                     return Some(content_mi);
 789                                 }
 790                             }
 791                         }
 792                     }
 793                 }
 794             }
 795         }
 796
 797         None
 798     }
 799
 800     /// Reads a `MetaItem` from within an attribute, looks for whether it is a
 801     /// `#[doc(include="file")]`, and returns the filename and contents of the file as loaded from
 802     /// its expansion.
 803     fn extract_include(mi: &ast::MetaItem)
 804         -> Option<(String, String)>
 805     {
 806         mi.meta_item_list().and_then(|list| {
 807             for meta in list {
 808                 if meta.check_name(sym::include) {
 809                     // the actual compiled `#[doc(include="filename")]` gets expanded to
 810                     // `#[doc(include(file="filename", contents="file contents")]` so we need to
 811                     // look for that instead
 812                     return meta.meta_item_list().and_then(|list| {
 813                         let mut filename: Option<String> = None;
 814                         let mut contents: Option<String> = None;
 815
 816                         for it in list {
 817                             if it.check_name(sym::file) {
 818                                 if let Some(name) = it.value_str() {
 819                                     filename = Some(name.to_string());
 820                                 }
 821                             } else if it.check_name(sym::contents) {
 822                                 if let Some(docs) = it.value_str() {
 823                                     contents = Some(docs.to_string());
 824                                 }
 825                             }
 826                         }
 827
 828                         if let (Some(filename), Some(contents)) = (filename, contents) {
 829                             Some((filename, contents))
 830                         } else {
 831                             None
 832                         }
 833                     });
 834                 }
 835             }
 836
 837             None
 838         })
 839     }
 840
 841     pub fn has_doc_flag(&self, flag: Symbol) -> bool {
 842         for attr in &self.other_attrs {
 843             if !attr.check_name(sym::doc) { continue; }
 844
 845             if let Some(items) = attr.meta_item_list() {
 846                 if items.iter().filter_map(|i| i.meta_item()).any(|it| it.check_name(flag)) {
 847                     return true;
 848                 }
 849             }
 850         }
 851
 852         false
 853     }
 854
 855     pub fn from_ast(diagnostic: &::errors::Handler,
 856                     attrs: &[ast::Attribute]) -> Attributes {
 857         let mut doc_strings = vec![];
 858         let mut sp = None;
 859         let mut cfg = Cfg::True;
 860         let mut doc_line = 0;
 861
 862         let other_attrs = attrs.iter().filter_map(|attr| {
 863             attr.with_desugared_doc(|attr| {
 864                 if attr.check_name(sym::doc) {
 865                     if let Some(mi) = attr.meta() {
 866                         if let Some(value) = mi.value_str() {
 867                             // Extracted #[doc = "..."]
 868                             let value = value.to_string();
 869                             let line = doc_line;
 870                             doc_line += value.lines().count();
 871
 872                             if attr.is_sugared_doc {
 873                                 doc_strings.push(DocFragment::SugaredDoc(line, attr.span, value));
 874                             } else {
 875                                 doc_strings.push(DocFragment::RawDoc(line, attr.span, value));
 876                             }
 877
 878                             if sp.is_none() {
 879                                 sp = Some(attr.span);
 880                             }
 881                             return None;
 882                         } else if let Some(cfg_mi) = Attributes::extract_cfg(&mi) {
 883                             // Extracted #[doc(cfg(...))]
 884                             match Cfg::parse(cfg_mi) {
 885                                 Ok(new_cfg) => cfg &= new_cfg,
 886                                 Err(e) => diagnostic.span_err(e.span, e.msg),
 887                             }
 888                             return None;
 889                         } else if let Some((filename, contents)) = Attributes::extract_include(&mi)
 890                         {
 891                             let line = doc_line;
 892                             doc_line += contents.lines().count();
 893                             doc_strings.push(DocFragment::Include(line,
 894                                                                   attr.span,
 895                                                                   filename,
 896                                                                   contents));
 897                         }
 898                     }
 899                 }
 900                 Some(attr.clone())
 901             })
 902         }).collect();
 903
 904         // treat #[target_feature(enable = "feat")] attributes as if they were
 905         // #[doc(cfg(target_feature = "feat"))] attributes as well
 906         for attr in attrs.lists(sym::target_feature) {
 907             if attr.check_name(sym::enable) {
 908                 if let Some(feat) = attr.value_str() {
 909                     let meta = attr::mk_name_value_item_str(
 910                         Ident::with_dummy_span(sym::target_feature), feat, DUMMY_SP
 911                     );
 912                     if let Ok(feat_cfg) = Cfg::parse(&meta) {
 913                         cfg &= feat_cfg;
 914                     }
 915                 }
 916             }
 917         }
 918
 919         let inner_docs = attrs.iter()
 920                               .filter(|a| a.check_name(sym::doc))
 921                               .next()
 922                               .map_or(true, |a| a.style == AttrStyle::Inner);
 923
 924         Attributes {
 925             doc_strings,
 926             other_attrs,
 927             cfg: if cfg == Cfg::True { None } else { Some(Arc::new(cfg)) },
 928             span: sp,
 929             links: vec![],
 930             inner_docs,
 931         }
 932     }
 933
 934     /// Finds the `doc` attribute as a NameValue and returns the corresponding
 935     /// value found.
 936     pub fn doc_value(&self) -> Option<&str> {
 937         self.doc_strings.first().map(|s| s.as_str())
 938     }
 939
 940     /// Finds all `doc` attributes as NameValues and returns their corresponding values, joined
 941     /// with newlines.
 942     pub fn collapsed_doc_value(&self) -> Option<String> {
 943         if !self.doc_strings.is_empty() {
 944             Some(self.doc_strings.iter().collect())
 945         } else {
 946             None
 947         }
 948     }
 949
 950     /// Gets links as a vector
 951     ///
 952     /// Cache must be populated before call
 953     pub fn links(&self, krate: &CrateNum) -> Vec<(String, String)> {
 954         use crate::html::format::href;
 955
 956         self.links.iter().filter_map(|&(ref s, did, ref fragment)| {
 957             match did {
 958                 Some(did) => {
 959                     if let Some((mut href, ..)) = href(did) {
 960                         if let Some(ref fragment) = *fragment {
 961                             href.push_str("#");
 962                             href.push_str(fragment);
 963                         }
 964                         Some((s.clone(), href))
 965                     } else {
 966                         None
 967                     }
 968                 }
 969                 None => {
 970                     if let Some(ref fragment) = *fragment {
 971                         let cache = cache();
 972                         let url = match cache.extern_locations.get(krate) {
 973                             Some(&(_, ref src, ExternalLocation::Local)) =>
 974                                 src.to_str().expect("invalid file path"),
 975                             Some(&(_, _, ExternalLocation::Remote(ref s))) => s,
 976                             Some(&(_, _, ExternalLocation::Unknown)) | None =>
 977                                 "https://doc.rust-lang.org/nightly",
 978                         };
 979                         // This is a primitive so the url is done "by hand".
 980                         let tail = fragment.find('#').unwrap_or_else(|| fragment.len());
 981                         Some((s.clone(),
 982                               format!("{}{}std/primitive.{}.html{}",
 983                                       url,
 984                                       if !url.ends_with('/') { "/" } else { "" },
 985                                       &fragment[..tail],
 986                                       &fragment[tail..])))
 987                     } else {
 988                         panic!("This isn't a primitive?!");
 989                     }
 990                 }
 991             }
 992         }).collect()
 993     }
 994 }
 995
 996 impl PartialEq for Attributes {
 997     fn eq(&self, rhs: &Self) -> bool {
 998         self.doc_strings == rhs.doc_strings &&
 999         self.cfg == rhs.cfg &&
1000         self.span == rhs.span &&
1001         self.links == rhs.links &&
1002         self.other_attrs.iter().map(|attr| attr.id).eq(rhs.other_attrs.iter().map(|attr| attr.id))
1003     }
1004 }
1005
1006 impl Eq for Attributes {}
1007
1008 impl Hash for Attributes {
1009     fn hash<H: Hasher>(&self, hasher: &mut H) {
1010         self.doc_strings.hash(hasher);
1011         self.cfg.hash(hasher);
1012         self.span.hash(hasher);
1013         self.links.hash(hasher);
1014         for attr in &self.other_attrs {
1015             attr.id.hash(hasher);
1016         }
1017     }
1018 }
1019
1020 impl AttributesExt for Attributes {
1021     fn lists(&self, name: Symbol) -> ListAttributesIter<'_> {
1022         self.other_attrs.lists(name)
1023     }
1024 }
1025
1026 impl Clean<Attributes> for [ast::Attribute] {
1027     fn clean(&self, cx: &DocContext<'_>) -> Attributes {
1028         Attributes::from_ast(cx.sess().diagnostic(), self)
1029     }
1030 }
1031
1032 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1033 pub enum GenericBound {
1034     TraitBound(PolyTrait, hir::TraitBoundModifier),
1035     Outlives(Lifetime),
1036 }
1037
1038 impl GenericBound {
1039     fn maybe_sized(cx: &DocContext<'_>) -> GenericBound {
1040         let did = cx.tcx.require_lang_item(lang_items::SizedTraitLangItem, None);
1041         let empty = cx.tcx.intern_substs(&[]);
1042         let path = external_path(cx, cx.tcx.item_name(did),
1043             Some(did), false, vec![], empty);
1044         inline::record_extern_fqn(cx, did, TypeKind::Trait);
1045         GenericBound::TraitBound(PolyTrait {
1046             trait_: ResolvedPath {
1047                 path,
1048                 param_names: None,
1049                 did,
1050                 is_generic: false,
1051             },
1052             generic_params: Vec::new(),
1053         }, hir::TraitBoundModifier::Maybe)
1054     }
1055
1056     fn is_sized_bound(&self, cx: &DocContext<'_>) -> bool {
1057         use rustc::hir::TraitBoundModifier as TBM;
1058         if let GenericBound::TraitBound(PolyTrait { ref trait_, .. }, TBM::None) = *self {
1059             if trait_.def_id() == cx.tcx.lang_items().sized_trait() {
1060                 return true;
1061             }
1062         }
1063         false
1064     }
1065
1066     fn get_poly_trait(&self) -> Option<PolyTrait> {
1067         if let GenericBound::TraitBound(ref p, _) = *self {
1068             return Some(p.clone())
1069         }
1070         None
1071     }
1072
1073     fn get_trait_type(&self) -> Option<Type> {
1074         if let GenericBound::TraitBound(PolyTrait { ref trait_, .. }, _) = *self {
1075             Some(trait_.clone())
1076         } else {
1077             None
1078         }
1079     }
1080 }
1081
1082 impl Clean<GenericBound> for hir::GenericBound {
1083     fn clean(&self, cx: &DocContext<'_>) -> GenericBound {
1084         match *self {
1085             hir::GenericBound::Outlives(lt) => GenericBound::Outlives(lt.clean(cx)),
1086             hir::GenericBound::Trait(ref t, modifier) => {
1087                 GenericBound::TraitBound(t.clean(cx), modifier)
1088             }
1089         }
1090     }
1091 }
1092
1093 fn external_generic_args(
1094     cx: &DocContext<'_>,
1095     trait_did: Option<DefId>,
1096     has_self: bool,
1097     bindings: Vec<TypeBinding>,
1098     substs: SubstsRef<'_>,
1099 ) -> GenericArgs {
1100     let mut skip_self = has_self;
1101     let mut ty_kind = None;
1102     let args: Vec<_> = substs.iter().filter_map(|kind| match kind.unpack() {
1103         GenericArgKind::Lifetime(lt) => {
1104             lt.clean(cx).and_then(|lt| Some(GenericArg::Lifetime(lt)))
1105         }
1106         GenericArgKind::Type(_) if skip_self => {
1107             skip_self = false;
1108             None
1109         }
1110         GenericArgKind::Type(ty) => {
1111             ty_kind = Some(&ty.kind);
1112             Some(GenericArg::Type(ty.clean(cx)))
1113         }
1114         GenericArgKind::Const(ct) => Some(GenericArg::Const(ct.clean(cx))),
1115     }).collect();
1116
1117     match trait_did {
1118         // Attempt to sugar an external path like Fn<(A, B,), C> to Fn(A, B) -> C
1119         Some(did) if cx.tcx.lang_items().fn_trait_kind(did).is_some() => {
1120             assert!(ty_kind.is_some());
1121             let inputs = match ty_kind {
1122                 Some(ty::Tuple(ref tys)) => tys.iter().map(|t| t.expect_ty().clean(cx)).collect(),
1123                 _ => return GenericArgs::AngleBracketed { args, bindings },
1124             };
1125             let output = None;
1126             // FIXME(#20299) return type comes from a projection now
1127             // match types[1].kind {
1128             //     ty::Tuple(ref v) if v.is_empty() => None, // -> ()
1129             //     _ => Some(types[1].clean(cx))
1130             // };
1131             GenericArgs::Parenthesized { inputs, output }
1132         },
1133         _ => {
1134             GenericArgs::AngleBracketed { args, bindings }
1135         }
1136     }
1137 }
1138
1139 // trait_did should be set to a trait's DefId if called on a TraitRef, in order to sugar
1140 // from Fn<(A, B,), C> to Fn(A, B) -> C
1141 fn external_path(cx: &DocContext<'_>, name: Symbol, trait_did: Option<DefId>, has_self: bool,
1142                  bindings: Vec<TypeBinding>, substs: SubstsRef<'_>) -> Path {
1143     Path {
1144         global: false,
1145         res: Res::Err,
1146         segments: vec![PathSegment {
1147             name: name.as_str().to_string(),
1148             args: external_generic_args(cx, trait_did, has_self, bindings, substs)
1149         }],
1150     }
1151 }
1152
1153 impl<'a, 'tcx> Clean<GenericBound> for (&'a ty::TraitRef<'tcx>, Vec<TypeBinding>) {
1154     fn clean(&self, cx: &DocContext<'_>) -> GenericBound {
1155         let (trait_ref, ref bounds) = *self;
1156         inline::record_extern_fqn(cx, trait_ref.def_id, TypeKind::Trait);
1157         let path = external_path(cx, cx.tcx.item_name(trait_ref.def_id),
1158                                  Some(trait_ref.def_id), true, bounds.clone(), trait_ref.substs);
1159
1160         debug!("ty::TraitRef\n  subst: {:?}\n", trait_ref.substs);
1161
1162         // collect any late bound regions
1163         let mut late_bounds = vec![];
1164         for ty_s in trait_ref.input_types().skip(1) {
1165             if let ty::Tuple(ts) = ty_s.kind {
1166                 for &ty_s in ts {
1167                     if let ty::Ref(ref reg, _, _) = ty_s.expect_ty().kind {
1168                         if let &ty::RegionKind::ReLateBound(..) = *reg {
1169                             debug!("  hit an ReLateBound {:?}", reg);
1170                             if let Some(Lifetime(name)) = reg.clean(cx) {
1171                                 late_bounds.push(GenericParamDef {
1172                                     name,
1173                                     kind: GenericParamDefKind::Lifetime,
1174                                 });
1175                             }
1176                         }
1177                     }
1178                 }
1179             }
1180         }
1181
1182         GenericBound::TraitBound(
1183             PolyTrait {
1184                 trait_: ResolvedPath {
1185                     path,
1186                     param_names: None,
1187                     did: trait_ref.def_id,
1188                     is_generic: false,
1189                 },
1190                 generic_params: late_bounds,
1191             },
1192             hir::TraitBoundModifier::None
1193         )
1194     }
1195 }
1196
1197 impl<'tcx> Clean<GenericBound> for ty::TraitRef<'tcx> {
1198     fn clean(&self, cx: &DocContext<'_>) -> GenericBound {
1199         (self, vec![]).clean(cx)
1200     }
1201 }
1202
1203 impl<'tcx> Clean<Option<Vec<GenericBound>>> for InternalSubsts<'tcx> {
1204     fn clean(&self, cx: &DocContext<'_>) -> Option<Vec<GenericBound>> {
1205         let mut v = Vec::new();
1206         v.extend(self.regions().filter_map(|r| r.clean(cx)).map(GenericBound::Outlives));
1207         v.extend(self.types().map(|t| GenericBound::TraitBound(PolyTrait {
1208             trait_: t.clean(cx),
1209             generic_params: Vec::new(),
1210         }, hir::TraitBoundModifier::None)));
1211         if !v.is_empty() {Some(v)} else {None}
1212     }
1213 }
1214
1215 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1216 pub struct Lifetime(String);
1217
1218 impl Lifetime {
1219     pub fn get_ref<'a>(&'a self) -> &'a str {
1220         let Lifetime(ref s) = *self;
1221         let s: &'a str = s;
1222         s
1223     }
1224
1225     pub fn statik() -> Lifetime {
1226         Lifetime("'static".to_string())
1227     }
1228 }
1229
1230 impl Clean<Lifetime> for hir::Lifetime {
1231     fn clean(&self, cx: &DocContext<'_>) -> Lifetime {
1232         if self.hir_id != hir::DUMMY_HIR_ID {
1233             let def = cx.tcx.named_region(self.hir_id);
1234             match def {
1235                 Some(rl::Region::EarlyBound(_, node_id, _)) |
1236                 Some(rl::Region::LateBound(_, node_id, _)) |
1237                 Some(rl::Region::Free(_, node_id)) => {
1238                     if let Some(lt) = cx.lt_substs.borrow().get(&node_id).cloned() {
1239                         return lt;
1240                     }
1241                 }
1242                 _ => {}
1243             }
1244         }
1245         Lifetime(self.name.ident().to_string())
1246     }
1247 }
1248
1249 impl Clean<Lifetime> for hir::GenericParam {
1250     fn clean(&self, _: &DocContext<'_>) -> Lifetime {
1251         match self.kind {
1252             hir::GenericParamKind::Lifetime { .. } => {
1253                 if self.bounds.len() > 0 {
1254                     let mut bounds = self.bounds.iter().map(|bound| match bound {
1255                         hir::GenericBound::Outlives(lt) => lt,
1256                         _ => panic!(),
1257                     });
1258                     let name = bounds.next().expect("no more bounds").name.ident();
1259                     let mut s = format!("{}: {}", self.name.ident(), name);
1260                     for bound in bounds {
1261                         s.push_str(&format!(" + {}", bound.name.ident()));
1262                     }
1263                     Lifetime(s)
1264                 } else {
1265                     Lifetime(self.name.ident().to_string())
1266                 }
1267             }
1268             _ => panic!(),
1269         }
1270     }
1271 }
1272
1273 impl Clean<Constant> for hir::ConstArg {
1274     fn clean(&self, cx: &DocContext<'_>) -> Constant {
1275         Constant {
1276             type_: cx.tcx.type_of(cx.tcx.hir().body_owner_def_id(self.value.body)).clean(cx),
1277             expr: print_const_expr(cx, self.value.body),
1278         }
1279     }
1280 }
1281
1282 impl Clean<Lifetime> for ty::GenericParamDef {
1283     fn clean(&self, _cx: &DocContext<'_>) -> Lifetime {
1284         Lifetime(self.name.to_string())
1285     }
1286 }
1287
1288 impl Clean<Option<Lifetime>> for ty::RegionKind {
1289     fn clean(&self, cx: &DocContext<'_>) -> Option<Lifetime> {
1290         match *self {
1291             ty::ReStatic => Some(Lifetime::statik()),
1292             ty::ReLateBound(_, ty::BrNamed(_, name)) => Some(Lifetime(name.to_string())),
1293             ty::ReEarlyBound(ref data) => Some(Lifetime(data.name.clean(cx))),
1294
1295             ty::ReLateBound(..) |
1296             ty::ReFree(..) |
1297             ty::ReScope(..) |
1298             ty::ReVar(..) |
1299             ty::RePlaceholder(..) |
1300             ty::ReEmpty |
1301             ty::ReClosureBound(_) |
1302             ty::ReErased => {
1303                 debug!("cannot clean region {:?}", self);
1304                 None
1305             }
1306         }
1307     }
1308 }
1309
1310 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1311 pub enum WherePredicate {
1312     BoundPredicate { ty: Type, bounds: Vec<GenericBound> },
1313     RegionPredicate { lifetime: Lifetime, bounds: Vec<GenericBound> },
1314     EqPredicate { lhs: Type, rhs: Type },
1315 }
1316
1317 impl WherePredicate {
1318     pub fn get_bounds(&self) -> Option<&[GenericBound]> {
1319         match *self {
1320             WherePredicate::BoundPredicate { ref bounds, .. } => Some(bounds),
1321             WherePredicate::RegionPredicate { ref bounds, .. } => Some(bounds),
1322             _ => None,
1323         }
1324     }
1325 }
1326
1327 impl Clean<WherePredicate> for hir::WherePredicate {
1328     fn clean(&self, cx: &DocContext<'_>) -> WherePredicate {
1329         match *self {
1330             hir::WherePredicate::BoundPredicate(ref wbp) => {
1331                 WherePredicate::BoundPredicate {
1332                     ty: wbp.bounded_ty.clean(cx),
1333                     bounds: wbp.bounds.clean(cx)
1334                 }
1335             }
1336
1337             hir::WherePredicate::RegionPredicate(ref wrp) => {
1338                 WherePredicate::RegionPredicate {
1339                     lifetime: wrp.lifetime.clean(cx),
1340                     bounds: wrp.bounds.clean(cx)
1341                 }
1342             }
1343
1344             hir::WherePredicate::EqPredicate(ref wrp) => {
1345                 WherePredicate::EqPredicate {
1346                     lhs: wrp.lhs_ty.clean(cx),
1347                     rhs: wrp.rhs_ty.clean(cx)
1348                 }
1349             }
1350         }
1351     }
1352 }
1353
1354 impl<'a> Clean<Option<WherePredicate>> for ty::Predicate<'a> {
1355     fn clean(&self, cx: &DocContext<'_>) -> Option<WherePredicate> {
1356         use rustc::ty::Predicate;
1357
1358         match *self {
1359             Predicate::Trait(ref pred) => Some(pred.clean(cx)),
1360             Predicate::Subtype(ref pred) => Some(pred.clean(cx)),
1361             Predicate::RegionOutlives(ref pred) => pred.clean(cx),
1362             Predicate::TypeOutlives(ref pred) => pred.clean(cx),
1363             Predicate::Projection(ref pred) => Some(pred.clean(cx)),
1364
1365             Predicate::WellFormed(..) |
1366             Predicate::ObjectSafe(..) |
1367             Predicate::ClosureKind(..) |
1368             Predicate::ConstEvaluatable(..) => panic!("not user writable"),
1369         }
1370     }
1371 }
1372
1373 impl<'a> Clean<WherePredicate> for ty::TraitPredicate<'a> {
1374     fn clean(&self, cx: &DocContext<'_>) -> WherePredicate {
1375         WherePredicate::BoundPredicate {
1376             ty: self.trait_ref.self_ty().clean(cx),
1377             bounds: vec![self.trait_ref.clean(cx)]
1378         }
1379     }
1380 }
1381
1382 impl<'tcx> Clean<WherePredicate> for ty::SubtypePredicate<'tcx> {
1383     fn clean(&self, _cx: &DocContext<'_>) -> WherePredicate {
1384         panic!("subtype predicates are an internal rustc artifact \
1385                 and should not be seen by rustdoc")
1386     }
1387 }
1388
1389 impl<'tcx> Clean<Option<WherePredicate>> for
1390     ty::OutlivesPredicate<ty::Region<'tcx>,ty::Region<'tcx>> {
1391
1392     fn clean(&self, cx: &DocContext<'_>) -> Option<WherePredicate> {
1393         let ty::OutlivesPredicate(ref a, ref b) = *self;
1394
1395         match (a, b) {
1396             (ty::ReEmpty, ty::ReEmpty) => {
1397                 return None;
1398             },
1399             _ => {}
1400         }
1401
1402         Some(WherePredicate::RegionPredicate {
1403             lifetime: a.clean(cx).expect("failed to clean lifetime"),
1404             bounds: vec![GenericBound::Outlives(b.clean(cx).expect("failed to clean bounds"))]
1405         })
1406     }
1407 }
1408
1409 impl<'tcx> Clean<Option<WherePredicate>> for ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>> {
1410     fn clean(&self, cx: &DocContext<'_>) -> Option<WherePredicate> {
1411         let ty::OutlivesPredicate(ref ty, ref lt) = *self;
1412
1413         match lt {
1414             ty::ReEmpty => return None,
1415             _ => {}
1416         }
1417
1418         Some(WherePredicate::BoundPredicate {
1419             ty: ty.clean(cx),
1420             bounds: vec![GenericBound::Outlives(lt.clean(cx).expect("failed to clean lifetimes"))]
1421         })
1422     }
1423 }
1424
1425 impl<'tcx> Clean<WherePredicate> for ty::ProjectionPredicate<'tcx> {
1426     fn clean(&self, cx: &DocContext<'_>) -> WherePredicate {
1427         WherePredicate::EqPredicate {
1428             lhs: self.projection_ty.clean(cx),
1429             rhs: self.ty.clean(cx)
1430         }
1431     }
1432 }
1433
1434 impl<'tcx> Clean<Type> for ty::ProjectionTy<'tcx> {
1435     fn clean(&self, cx: &DocContext<'_>) -> Type {
1436         let trait_ = match self.trait_ref(cx.tcx).clean(cx) {
1437             GenericBound::TraitBound(t, _) => t.trait_,
1438             GenericBound::Outlives(_) => panic!("cleaning a trait got a lifetime"),
1439         };
1440         Type::QPath {
1441             name: cx.tcx.associated_item(self.item_def_id).ident.name.clean(cx),
1442             self_type: box self.self_ty().clean(cx),
1443             trait_: box trait_
1444         }
1445     }
1446 }
1447
1448 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1449 pub enum GenericParamDefKind {
1450     Lifetime,
1451     Type {
1452         did: DefId,
1453         bounds: Vec<GenericBound>,
1454         default: Option<Type>,
1455         synthetic: Option<hir::SyntheticTyParamKind>,
1456     },
1457     Const {
1458         did: DefId,
1459         ty: Type,
1460     },
1461 }
1462
1463 impl GenericParamDefKind {
1464     pub fn is_type(&self) -> bool {
1465         match *self {
1466             GenericParamDefKind::Type { .. } => true,
1467             _ => false,
1468         }
1469     }
1470
1471     pub fn get_type(&self, cx: &DocContext<'_>) -> Option<Type> {
1472         match *self {
1473             GenericParamDefKind::Type { did, .. } => {
1474                 rustc_typeck::checked_type_of(cx.tcx, did, false).map(|t| t.clean(cx))
1475             }
1476             GenericParamDefKind::Const { ref ty, .. } => Some(ty.clone()),
1477             GenericParamDefKind::Lifetime => None,
1478         }
1479     }
1480 }
1481
1482 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
1483 pub struct GenericParamDef {
1484     pub name: String,
1485
1486     pub kind: GenericParamDefKind,
1487 }
1488
1489 impl GenericParamDef {
1490     pub fn is_synthetic_type_param(&self) -> bool {
1491         match self.kind {
1492             GenericParamDefKind::Lifetime |
1493             GenericParamDefKind::Const { .. } => false,
1494             GenericParamDefKind::Type { ref synthetic, .. } => synthetic.is_some(),
1495         }
1496     }
1497
1498     pub fn is_type(&self) -> bool {
1499         self.kind.is_type()
1500     }
1501
1502     pub fn get_type(&self, cx: &DocContext<'_>) -> Option<Type> {
1503         self.kind.get_type(cx)
1504     }
1505
1506     pub fn get_bounds(&self) -> Option<&[GenericBound]> {
1507         match self.kind {
1508             GenericParamDefKind::Type { ref bounds, .. } => Some(bounds),
1509             _ => None,
1510         }
1511     }
1512 }
1513
1514 impl Clean<GenericParamDef> for ty::GenericParamDef {
1515     fn clean(&self, cx: &DocContext<'_>) -> GenericParamDef {
1516         let (name, kind) = match self.kind {
1517             ty::GenericParamDefKind::Lifetime => {
1518                 (self.name.to_string(), GenericParamDefKind::Lifetime)
1519             }
1520             ty::GenericParamDefKind::Type { has_default, synthetic, .. } => {
1521                 let default = if has_default {
1522                     Some(cx.tcx.type_of(self.def_id).clean(cx))
1523                 } else {
1524                     None
1525                 };
1526                 (self.name.clean(cx), GenericParamDefKind::Type {
1527                     did: self.def_id,
1528                     bounds: vec![], // These are filled in from the where-clauses.
1529                     default,
1530                     synthetic,
1531                 })
1532             }
1533             ty::GenericParamDefKind::Const { .. } => {
1534                 (self.name.clean(cx), GenericParamDefKind::Const {
1535                     did: self.def_id,
1536                     ty: cx.tcx.type_of(self.def_id).clean(cx),
1537                 })
1538             }
1539         };
1540
1541         GenericParamDef {
1542             name,
1543             kind,
1544         }
1545     }
1546 }
1547
1548 impl Clean<GenericParamDef> for hir::GenericParam {
1549     fn clean(&self, cx: &DocContext<'_>) -> GenericParamDef {
1550         let (name, kind) = match self.kind {
1551             hir::GenericParamKind::Lifetime { .. } => {
1552                 let name = if self.bounds.len() > 0 {
1553                     let mut bounds = self.bounds.iter().map(|bound| match bound {
1554                         hir::GenericBound::Outlives(lt) => lt,
1555                         _ => panic!(),
1556                     });
1557                     let name = bounds.next().expect("no more bounds").name.ident();
1558                     let mut s = format!("{}: {}", self.name.ident(), name);
1559                     for bound in bounds {
1560                         s.push_str(&format!(" + {}", bound.name.ident()));
1561                     }
1562                     s
1563                 } else {
1564                     self.name.ident().to_string()
1565                 };
1566                 (name, GenericParamDefKind::Lifetime)
1567             }
1568             hir::GenericParamKind::Type { ref default, synthetic } => {
1569                 (self.name.ident().name.clean(cx), GenericParamDefKind::Type {
1570                     did: cx.tcx.hir().local_def_id(self.hir_id),
1571                     bounds: self.bounds.clean(cx),
1572                     default: default.clean(cx),
1573                     synthetic: synthetic,
1574                 })
1575             }
1576             hir::GenericParamKind::Const { ref ty } => {
1577                 (self.name.ident().name.clean(cx), GenericParamDefKind::Const {
1578                     did: cx.tcx.hir().local_def_id(self.hir_id),
1579                     ty: ty.clean(cx),
1580                 })
1581             }
1582         };
1583
1584         GenericParamDef {
1585             name,
1586             kind,
1587         }
1588     }
1589 }
1590
1591 // maybe use a Generic enum and use Vec<Generic>?
1592 #[derive(Clone, PartialEq, Eq, Debug, Default, Hash)]
1593 pub struct Generics {
1594     pub params: Vec<GenericParamDef>,
1595     pub where_predicates: Vec<WherePredicate>,
1596 }
1597
1598 impl Clean<Generics> for hir::Generics {
1599     fn clean(&self, cx: &DocContext<'_>) -> Generics {
1600         // Synthetic type-parameters are inserted after normal ones.
1601         // In order for normal parameters to be able to refer to synthetic ones,
1602         // scans them first.
1603         fn is_impl_trait(param: &hir::GenericParam) -> bool {
1604             match param.kind {
1605                 hir::GenericParamKind::Type { synthetic, .. } => {
1606                     synthetic == Some(hir::SyntheticTyParamKind::ImplTrait)
1607                 }
1608                 _ => false,
1609             }
1610         }
1611         let impl_trait_params = self.params
1612             .iter()
1613             .filter(|param| is_impl_trait(param))
1614             .map(|param| {
1615                 let param: GenericParamDef = param.clean(cx);
1616                 match param.kind {
1617                     GenericParamDefKind::Lifetime => unreachable!(),
1618                     GenericParamDefKind::Type { did, ref bounds, .. } => {
1619                         cx.impl_trait_bounds.borrow_mut().insert(did.into(), bounds.clone());
1620                     }
1621                     GenericParamDefKind::Const { .. } => unreachable!(),
1622                 }
1623                 param
1624             })
1625             .collect::<Vec<_>>();
1626
1627         let mut params = Vec::with_capacity(self.params.len());
1628         for p in self.params.iter().filter(|p| !is_impl_trait(p)) {
1629             let p = p.clean(cx);
1630             params.push(p);
1631         }
1632         params.extend(impl_trait_params);
1633
1634         let mut generics = Generics {
1635             params,
1636             where_predicates: self.where_clause.predicates.clean(cx),
1637         };
1638
1639         // Some duplicates are generated for ?Sized bounds between type params and where
1640         // predicates. The point in here is to move the bounds definitions from type params
1641         // to where predicates when such cases occur.
1642         for where_pred in &mut generics.where_predicates {
1643             match *where_pred {
1644                 WherePredicate::BoundPredicate { ty: Generic(ref name), ref mut bounds } => {
1645                     if bounds.is_empty() {
1646                         for param in &mut generics.params {
1647                             match param.kind {
1648                                 GenericParamDefKind::Lifetime => {}
1649                                 GenericParamDefKind::Type { bounds: ref mut ty_bounds, .. } => {
1650                                     if &param.name == name {
1651                                         mem::swap(bounds, ty_bounds);
1652                                         break
1653                                     }
1654                                 }
1655                                 GenericParamDefKind::Const { .. } => {}
1656                             }
1657                         }
1658                     }
1659                 }
1660                 _ => continue,
1661             }
1662         }
1663         generics
1664     }
1665 }
1666
1667 impl<'a, 'tcx> Clean<Generics> for (&'a ty::Generics,
1668                                     &'a &'tcx ty::GenericPredicates<'tcx>) {
1669     fn clean(&self, cx: &DocContext<'_>) -> Generics {
1670         use self::WherePredicate as WP;
1671         use std::collections::BTreeMap;
1672
1673         let (gens, preds) = *self;
1674
1675         // Don't populate `cx.impl_trait_bounds` before `clean`ning `where` clauses,
1676         // since `Clean for ty::Predicate` would consume them.
1677         let mut impl_trait = BTreeMap::<ImplTraitParam, Vec<GenericBound>>::default();
1678
1679         // Bounds in the type_params and lifetimes fields are repeated in the
1680         // predicates field (see rustc_typeck::collect::ty_generics), so remove
1681         // them.
1682         let stripped_typarams = gens.params.iter()
1683             .filter_map(|param| match param.kind {
1684                 ty::GenericParamDefKind::Lifetime => None,
1685                 ty::GenericParamDefKind::Type { synthetic, .. } => {
1686                     if param.name.as_symbol() == kw::SelfUpper {
1687                         assert_eq!(param.index, 0);
1688                         return None;
1689                     }
1690                     if synthetic == Some(hir::SyntheticTyParamKind::ImplTrait) {
1691                         impl_trait.insert(param.index.into(), vec![]);
1692                         return None;
1693                     }
1694                     Some(param.clean(cx))
1695                 }
1696                 ty::GenericParamDefKind::Const { .. } => None,
1697             }).collect::<Vec<GenericParamDef>>();
1698
1699         // param index -> [(DefId of trait, associated type name, type)]
1700         let mut impl_trait_proj =
1701             FxHashMap::<u32, Vec<(DefId, String, Ty<'tcx>)>>::default();
1702
1703         let where_predicates = preds.predicates.iter()
1704             .flat_map(|(p, _)| {
1705                 let mut projection = None;
1706                 let param_idx = (|| {
1707                     if let Some(trait_ref) = p.to_opt_poly_trait_ref() {
1708                         if let ty::Param(param) = trait_ref.self_ty().kind {
1709                             return Some(param.index);
1710                         }
1711                     } else if let Some(outlives) = p.to_opt_type_outlives() {
1712                         if let ty::Param(param) = outlives.skip_binder().0.kind {
1713                             return Some(param.index);
1714                         }
1715                     } else if let ty::Predicate::Projection(p) = p {
1716                         if let ty::Param(param) = p.skip_binder().projection_ty.self_ty().kind {
1717                             projection = Some(p);
1718                             return Some(param.index);
1719                         }
1720                     }
1721
1722                     None
1723                 })();
1724
1725                 if let Some(param_idx) = param_idx {
1726                     if let Some(b) = impl_trait.get_mut(&param_idx.into()) {
1727                         let p = p.clean(cx)?;
1728
1729                         b.extend(
1730                             p.get_bounds()
1731                                 .into_iter()
1732                                 .flatten()
1733                                 .cloned()
1734                                 .filter(|b| !b.is_sized_bound(cx))
1735                         );
1736
1737                         let proj = projection
1738                             .map(|p| (p.skip_binder().projection_ty.clean(cx), p.skip_binder().ty));
1739                         if let Some(((_, trait_did, name), rhs)) =
1740                             proj.as_ref().and_then(|(lhs, rhs)| Some((lhs.projection()?, rhs)))
1741                         {
1742                             impl_trait_proj
1743                                 .entry(param_idx)
1744                                 .or_default()
1745                                 .push((trait_did, name.to_string(), rhs));
1746                         }
1747
1748                         return None;
1749                     }
1750                 }
1751
1752                 Some(p)
1753             })
1754             .collect::<Vec<_>>();
1755
1756         for (param, mut bounds) in impl_trait {
1757             // Move trait bounds to the front.
1758             bounds.sort_by_key(|b| if let GenericBound::TraitBound(..) = b {
1759                 false
1760             } else {
1761                 true
1762             });
1763
1764             if let crate::core::ImplTraitParam::ParamIndex(idx) = param {
1765                 if let Some(proj) = impl_trait_proj.remove(&idx) {
1766                     for (trait_did, name, rhs) in proj {
1767                         simplify::merge_bounds(
1768                             cx,
1769                             &mut bounds,
1770                             trait_did,
1771                             &name,
1772                             &rhs.clean(cx),
1773                         );
1774                     }
1775                 }
1776             } else {
1777                 unreachable!();
1778             }
1779
1780             cx.impl_trait_bounds.borrow_mut().insert(param, bounds);
1781         }
1782
1783         // Now that `cx.impl_trait_bounds` is populated, we can process
1784         // remaining predicates which could contain `impl Trait`.
1785         let mut where_predicates = where_predicates
1786             .into_iter()
1787             .flat_map(|p| p.clean(cx))
1788             .collect::<Vec<_>>();
1789
1790         // Type parameters and have a Sized bound by default unless removed with
1791         // ?Sized. Scan through the predicates and mark any type parameter with
1792         // a Sized bound, removing the bounds as we find them.
1793         //
1794         // Note that associated types also have a sized bound by default, but we
1795         // don't actually know the set of associated types right here so that's
1796         // handled in cleaning associated types
1797         let mut sized_params = FxHashSet::default();
1798         where_predicates.retain(|pred| {
1799             match *pred {
1800                 WP::BoundPredicate { ty: Generic(ref g), ref bounds } => {
1801                     if bounds.iter().any(|b| b.is_sized_bound(cx)) {
1802                         sized_params.insert(g.clone());
1803                         false
1804                     } else {
1805                         true
1806                     }
1807                 }
1808                 _ => true,
1809             }
1810         });
1811
1812         // Run through the type parameters again and insert a ?Sized
1813         // unbound for any we didn't find to be Sized.
1814         for tp in &stripped_typarams {
1815             if !sized_params.contains(&tp.name) {
1816                 where_predicates.push(WP::BoundPredicate {
1817                     ty: Type::Generic(tp.name.clone()),
1818                     bounds: vec![GenericBound::maybe_sized(cx)],
1819                 })
1820             }
1821         }
1822
1823         // It would be nice to collect all of the bounds on a type and recombine
1824         // them if possible, to avoid e.g., `where T: Foo, T: Bar, T: Sized, T: 'a`
1825         // and instead see `where T: Foo + Bar + Sized + 'a`
1826
1827         Generics {
1828             params: gens.params
1829                         .iter()
1830                         .flat_map(|param| match param.kind {
1831                             ty::GenericParamDefKind::Lifetime => Some(param.clean(cx)),
1832                             ty::GenericParamDefKind::Type { .. } => None,
1833                             ty::GenericParamDefKind::Const { .. } => Some(param.clean(cx)),
1834                         }).chain(simplify::ty_params(stripped_typarams).into_iter())
1835                         .collect(),
1836             where_predicates: simplify::where_clauses(cx, where_predicates),
1837         }
1838     }
1839 }
1840
1841 /// The point of this function is to replace bounds with types.
1842 ///
1843 /// i.e. `[T, U]` when you have the following bounds: `T: Display, U: Option<T>` will return
1844 /// `[Display, Option]` (we just returns the list of the types, we don't care about the
1845 /// wrapped types in here).
1846 fn get_real_types(
1847     generics: &Generics,
1848     arg: &Type,
1849     cx: &DocContext<'_>,
1850     recurse: i32,
1851 ) -> FxHashSet<Type> {
1852     let arg_s = arg.print().to_string();
1853     let mut res = FxHashSet::default();
1854     if recurse >= 10 { // FIXME: remove this whole recurse thing when the recursion bug is fixed
1855         return res;
1856     }
1857     if arg.is_full_generic() {
1858         if let Some(where_pred) = generics.where_predicates.iter().find(|g| {
1859             match g {
1860                 &WherePredicate::BoundPredicate { ref ty, .. } => ty.def_id() == arg.def_id(),
1861                 _ => false,
1862             }
1863         }) {
1864             let bounds = where_pred.get_bounds().unwrap_or_else(|| &[]);
1865             for bound in bounds.iter() {
1866                 match *bound {
1867                     GenericBound::TraitBound(ref poly_trait, _) => {
1868                         for x in poly_trait.generic_params.iter() {
1869                             if !x.is_type() {
1870                                 continue
1871                             }
1872                             if let Some(ty) = x.get_type(cx) {
1873                                 let adds = get_real_types(generics, &ty, cx, recurse + 1);
1874                                 if !adds.is_empty() {
1875                                     res.extend(adds);
1876                                 } else if !ty.is_full_generic() {
1877                                     res.insert(ty);
1878                                 }
1879                             }
1880                         }
1881                     }
1882                     _ => {}
1883                 }
1884             }
1885         }
1886         if let Some(bound) = generics.params.iter().find(|g| {
1887             g.is_type() && g.name == arg_s
1888         }) {
1889             for bound in bound.get_bounds().unwrap_or_else(|| &[]) {
1890                 if let Some(ty) = bound.get_trait_type() {
1891                     let adds = get_real_types(generics, &ty, cx, recurse + 1);
1892                     if !adds.is_empty() {
1893                         res.extend(adds);
1894                     } else if !ty.is_full_generic() {
1895                         res.insert(ty.clone());
1896                     }
1897                 }
1898             }
1899         }
1900     } else {
1901         res.insert(arg.clone());
1902         if let Some(gens) = arg.generics() {
1903             for gen in gens.iter() {
1904                 if gen.is_full_generic() {
1905                     let adds = get_real_types(generics, gen, cx, recurse + 1);
1906                     if !adds.is_empty() {
1907                         res.extend(adds);
1908                     }
1909                 } else {
1910                     res.insert(gen.clone());
1911                 }
1912             }
1913         }
1914     }
1915     res
1916 }
1917
1918 /// Return the full list of types when bounds have been resolved.
1919 ///
1920 /// i.e. `fn foo<A: Display, B: Option<A>>(x: u32, y: B)` will return
1921 /// `[u32, Display, Option]`.
1922 pub fn get_all_types(
1923     generics: &Generics,
1924     decl: &FnDecl,
1925     cx: &DocContext<'_>,
1926 ) -> (Vec<Type>, Vec<Type>) {
1927     let mut all_types = FxHashSet::default();
1928     for arg in decl.inputs.values.iter() {
1929         if arg.type_.is_self_type() {
1930             continue;
1931         }
1932         let args = get_real_types(generics, &arg.type_, cx, 0);
1933         if !args.is_empty() {
1934             all_types.extend(args);
1935         } else {
1936             all_types.insert(arg.type_.clone());
1937         }
1938     }
1939
1940     let ret_types = match decl.output {
1941         FunctionRetTy::Return(ref return_type) => {
1942             let mut ret = get_real_types(generics, &return_type, cx, 0);
1943             if ret.is_empty() {
1944                 ret.insert(return_type.clone());
1945             }
1946             ret.into_iter().collect()
1947         }
1948         _ => Vec::new(),
1949     };
1950     (all_types.into_iter().collect(), ret_types)
1951 }
1952
1953 #[derive(Clone, Debug)]
1954 pub struct Method {
1955     pub generics: Generics,
1956     pub decl: FnDecl,
1957     pub header: hir::FnHeader,
1958     pub defaultness: Option<hir::Defaultness>,
1959     pub all_types: Vec<Type>,
1960     pub ret_types: Vec<Type>,
1961 }
1962
1963 impl<'a> Clean<Method> for (&'a hir::MethodSig, &'a hir::Generics, hir::BodyId,
1964                             Option<hir::Defaultness>) {
1965     fn clean(&self, cx: &DocContext<'_>) -> Method {
1966         let (generics, decl) = enter_impl_trait(cx, || {
1967             (self.1.clean(cx), (&*self.0.decl, self.2).clean(cx))
1968         });
1969         let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
1970         Method {
1971             decl,
1972             generics,
1973             header: self.0.header,
1974             defaultness: self.3,
1975             all_types,
1976             ret_types,
1977         }
1978     }
1979 }
1980
1981 #[derive(Clone, Debug)]
1982 pub struct TyMethod {
1983     pub header: hir::FnHeader,
1984     pub decl: FnDecl,
1985     pub generics: Generics,
1986     pub all_types: Vec<Type>,
1987     pub ret_types: Vec<Type>,
1988 }
1989
1990 #[derive(Clone, Debug)]
1991 pub struct Function {
1992     pub decl: FnDecl,
1993     pub generics: Generics,
1994     pub header: hir::FnHeader,
1995     pub all_types: Vec<Type>,
1996     pub ret_types: Vec<Type>,
1997 }
1998
1999 impl Clean<Item> for doctree::Function<'_> {
2000     fn clean(&self, cx: &DocContext<'_>) -> Item {
2001         let (generics, decl) = enter_impl_trait(cx, || {
2002             (self.generics.clean(cx), (self.decl, self.body).clean(cx))
2003         });
2004
2005         let did = cx.tcx.hir().local_def_id(self.id);
2006         let constness = if cx.tcx.is_min_const_fn(did) {
2007             hir::Constness::Const
2008         } else {
2009             hir::Constness::NotConst
2010         };
2011         let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
2012         Item {
2013             name: Some(self.name.clean(cx)),
2014             attrs: self.attrs.clean(cx),
2015             source: self.whence.clean(cx),
2016             visibility: self.vis.clean(cx),
2017             stability: cx.stability(self.id).clean(cx),
2018             deprecation: cx.deprecation(self.id).clean(cx),
2019             def_id: did,
2020             inner: FunctionItem(Function {
2021                 decl,
2022                 generics,
2023                 header: hir::FnHeader { constness, ..self.header },
2024                 all_types,
2025                 ret_types,
2026             }),
2027         }
2028     }
2029 }
2030
2031 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2032 pub struct FnDecl {
2033     pub inputs: Arguments,
2034     pub output: FunctionRetTy,
2035     pub attrs: Attributes,
2036 }
2037
2038 impl FnDecl {
2039     pub fn self_type(&self) -> Option<SelfTy> {
2040         self.inputs.values.get(0).and_then(|v| v.to_self())
2041     }
2042
2043     /// Returns the sugared return type for an async function.
2044     ///
2045     /// For example, if the return type is `impl std::future::Future<Output = i32>`, this function
2046     /// will return `i32`.
2047     ///
2048     /// # Panics
2049     ///
2050     /// This function will panic if the return type does not match the expected sugaring for async
2051     /// functions.
2052     pub fn sugared_async_return_type(&self) -> FunctionRetTy {
2053         match &self.output {
2054             FunctionRetTy::Return(Type::ImplTrait(bounds)) => {
2055                 match &bounds[0] {
2056                     GenericBound::TraitBound(PolyTrait { trait_, .. }, ..) => {
2057                         let bindings = trait_.bindings().unwrap();
2058                         FunctionRetTy::Return(bindings[0].ty().clone())
2059                     }
2060                     _ => panic!("unexpected desugaring of async function"),
2061                 }
2062             }
2063             _ => panic!("unexpected desugaring of async function"),
2064         }
2065     }
2066 }
2067
2068 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2069 pub struct Arguments {
2070     pub values: Vec<Argument>,
2071 }
2072
2073 impl<'a> Clean<Arguments> for (&'a [hir::Ty], &'a [ast::Ident]) {
2074     fn clean(&self, cx: &DocContext<'_>) -> Arguments {
2075         Arguments {
2076             values: self.0.iter().enumerate().map(|(i, ty)| {
2077                 let mut name = self.1.get(i).map(|ident| ident.to_string())
2078                                             .unwrap_or(String::new());
2079                 if name.is_empty() {
2080                     name = "_".to_string();
2081                 }
2082                 Argument {
2083                     name,
2084                     type_: ty.clean(cx),
2085                 }
2086             }).collect()
2087         }
2088     }
2089 }
2090
2091 impl<'a> Clean<Arguments> for (&'a [hir::Ty], hir::BodyId) {
2092     fn clean(&self, cx: &DocContext<'_>) -> Arguments {
2093         let body = cx.tcx.hir().body(self.1);
2094
2095         Arguments {
2096             values: self.0.iter().enumerate().map(|(i, ty)| {
2097                 Argument {
2098                     name: name_from_pat(&body.params[i].pat),
2099                     type_: ty.clean(cx),
2100                 }
2101             }).collect()
2102         }
2103     }
2104 }
2105
2106 impl<'a, A: Copy> Clean<FnDecl> for (&'a hir::FnDecl, A)
2107     where (&'a [hir::Ty], A): Clean<Arguments>
2108 {
2109     fn clean(&self, cx: &DocContext<'_>) -> FnDecl {
2110         FnDecl {
2111             inputs: (&self.0.inputs[..], self.1).clean(cx),
2112             output: self.0.output.clean(cx),
2113             attrs: Attributes::default(),
2114         }
2115     }
2116 }
2117
2118 impl<'tcx> Clean<FnDecl> for (DefId, ty::PolyFnSig<'tcx>) {
2119     fn clean(&self, cx: &DocContext<'_>) -> FnDecl {
2120         let (did, sig) = *self;
2121         let mut names = if cx.tcx.hir().as_local_hir_id(did).is_some() {
2122             vec![].into_iter()
2123         } else {
2124             cx.tcx.fn_arg_names(did).into_iter()
2125         };
2126
2127         FnDecl {
2128             output: Return(sig.skip_binder().output().clean(cx)),
2129             attrs: Attributes::default(),
2130             inputs: Arguments {
2131                 values: sig.skip_binder().inputs().iter().map(|t| {
2132                     Argument {
2133                         type_: t.clean(cx),
2134                         name: names.next().map_or(String::new(), |name| name.to_string()),
2135                     }
2136                 }).collect(),
2137             },
2138         }
2139     }
2140 }
2141
2142 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2143 pub struct Argument {
2144     pub type_: Type,
2145     pub name: String,
2146 }
2147
2148 #[derive(Clone, PartialEq, Debug)]
2149 pub enum SelfTy {
2150     SelfValue,
2151     SelfBorrowed(Option<Lifetime>, Mutability),
2152     SelfExplicit(Type),
2153 }
2154
2155 impl Argument {
2156     pub fn to_self(&self) -> Option<SelfTy> {
2157         if self.name != "self" {
2158             return None;
2159         }
2160         if self.type_.is_self_type() {
2161             return Some(SelfValue);
2162         }
2163         match self.type_ {
2164             BorrowedRef{ref lifetime, mutability, ref type_} if type_.is_self_type() => {
2165                 Some(SelfBorrowed(lifetime.clone(), mutability))
2166             }
2167             _ => Some(SelfExplicit(self.type_.clone()))
2168         }
2169     }
2170 }
2171
2172 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2173 pub enum FunctionRetTy {
2174     Return(Type),
2175     DefaultReturn,
2176 }
2177
2178 impl Clean<FunctionRetTy> for hir::FunctionRetTy {
2179     fn clean(&self, cx: &DocContext<'_>) -> FunctionRetTy {
2180         match *self {
2181             hir::Return(ref typ) => Return(typ.clean(cx)),
2182             hir::DefaultReturn(..) => DefaultReturn,
2183         }
2184     }
2185 }
2186
2187 impl GetDefId for FunctionRetTy {
2188     fn def_id(&self) -> Option<DefId> {
2189         match *self {
2190             Return(ref ty) => ty.def_id(),
2191             DefaultReturn => None,
2192         }
2193     }
2194 }
2195
2196 #[derive(Clone, Debug)]
2197 pub struct Trait {
2198     pub auto: bool,
2199     pub unsafety: hir::Unsafety,
2200     pub items: Vec<Item>,
2201     pub generics: Generics,
2202     pub bounds: Vec<GenericBound>,
2203     pub is_spotlight: bool,
2204     pub is_auto: bool,
2205 }
2206
2207 impl Clean<Item> for doctree::Trait<'_> {
2208     fn clean(&self, cx: &DocContext<'_>) -> Item {
2209         let attrs = self.attrs.clean(cx);
2210         let is_spotlight = attrs.has_doc_flag(sym::spotlight);
2211         Item {
2212             name: Some(self.name.clean(cx)),
2213             attrs: attrs,
2214             source: self.whence.clean(cx),
2215             def_id: cx.tcx.hir().local_def_id(self.id),
2216             visibility: self.vis.clean(cx),
2217             stability: cx.stability(self.id).clean(cx),
2218             deprecation: cx.deprecation(self.id).clean(cx),
2219             inner: TraitItem(Trait {
2220                 auto: self.is_auto.clean(cx),
2221                 unsafety: self.unsafety,
2222                 items: self.items.iter().map(|ti| ti.clean(cx)).collect(),
2223                 generics: self.generics.clean(cx),
2224                 bounds: self.bounds.clean(cx),
2225                 is_spotlight,
2226                 is_auto: self.is_auto.clean(cx),
2227             }),
2228         }
2229     }
2230 }
2231
2232 #[derive(Clone, Debug)]
2233 pub struct TraitAlias {
2234     pub generics: Generics,
2235     pub bounds: Vec<GenericBound>,
2236 }
2237
2238 impl Clean<Item> for doctree::TraitAlias<'_> {
2239     fn clean(&self, cx: &DocContext<'_>) -> Item {
2240         let attrs = self.attrs.clean(cx);
2241         Item {
2242             name: Some(self.name.clean(cx)),
2243             attrs,
2244             source: self.whence.clean(cx),
2245             def_id: cx.tcx.hir().local_def_id(self.id),
2246             visibility: self.vis.clean(cx),
2247             stability: cx.stability(self.id).clean(cx),
2248             deprecation: cx.deprecation(self.id).clean(cx),
2249             inner: TraitAliasItem(TraitAlias {
2250                 generics: self.generics.clean(cx),
2251                 bounds: self.bounds.clean(cx),
2252             }),
2253         }
2254     }
2255 }
2256
2257 impl Clean<bool> for hir::IsAuto {
2258     fn clean(&self, _: &DocContext<'_>) -> bool {
2259         match *self {
2260             hir::IsAuto::Yes => true,
2261             hir::IsAuto::No => false,
2262         }
2263     }
2264 }
2265
2266 impl Clean<Type> for hir::TraitRef {
2267     fn clean(&self, cx: &DocContext<'_>) -> Type {
2268         resolve_type(cx, self.path.clean(cx), self.hir_ref_id)
2269     }
2270 }
2271
2272 impl Clean<PolyTrait> for hir::PolyTraitRef {
2273     fn clean(&self, cx: &DocContext<'_>) -> PolyTrait {
2274         PolyTrait {
2275             trait_: self.trait_ref.clean(cx),
2276             generic_params: self.bound_generic_params.clean(cx)
2277         }
2278     }
2279 }
2280
2281 impl Clean<Item> for hir::TraitItem {
2282     fn clean(&self, cx: &DocContext<'_>) -> Item {
2283         let inner = match self.node {
2284             hir::TraitItemKind::Const(ref ty, default) => {
2285                 AssocConstItem(ty.clean(cx),
2286                                     default.map(|e| print_const_expr(cx, e)))
2287             }
2288             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Provided(body)) => {
2289                 MethodItem((sig, &self.generics, body, None).clean(cx))
2290             }
2291             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Required(ref names)) => {
2292                 let (generics, decl) = enter_impl_trait(cx, || {
2293                     (self.generics.clean(cx), (&*sig.decl, &names[..]).clean(cx))
2294                 });
2295                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
2296                 TyMethodItem(TyMethod {
2297                     header: sig.header,
2298                     decl,
2299                     generics,
2300                     all_types,
2301                     ret_types,
2302                 })
2303             }
2304             hir::TraitItemKind::Type(ref bounds, ref default) => {
2305                 AssocTypeItem(bounds.clean(cx), default.clean(cx))
2306             }
2307         };
2308         let local_did = cx.tcx.hir().local_def_id(self.hir_id);
2309         Item {
2310             name: Some(self.ident.name.clean(cx)),
2311             attrs: self.attrs.clean(cx),
2312             source: self.span.clean(cx),
2313             def_id: local_did,
2314             visibility: Visibility::Inherited,
2315             stability: get_stability(cx, local_did),
2316             deprecation: get_deprecation(cx, local_did),
2317             inner,
2318         }
2319     }
2320 }
2321
2322 impl Clean<Item> for hir::ImplItem {
2323     fn clean(&self, cx: &DocContext<'_>) -> Item {
2324         let inner = match self.kind {
2325             hir::ImplItemKind::Const(ref ty, expr) => {
2326                 AssocConstItem(ty.clean(cx),
2327                                     Some(print_const_expr(cx, expr)))
2328             }
2329             hir::ImplItemKind::Method(ref sig, body) => {
2330                 MethodItem((sig, &self.generics, body, Some(self.defaultness)).clean(cx))
2331             }
2332             hir::ImplItemKind::TyAlias(ref ty) => TypedefItem(Typedef {
2333                 type_: ty.clean(cx),
2334                 generics: Generics::default(),
2335             }, true),
2336             hir::ImplItemKind::OpaqueTy(ref bounds) => OpaqueTyItem(OpaqueTy {
2337                 bounds: bounds.clean(cx),
2338                 generics: Generics::default(),
2339             }, true),
2340         };
2341         let local_did = cx.tcx.hir().local_def_id(self.hir_id);
2342         Item {
2343             name: Some(self.ident.name.clean(cx)),
2344             source: self.span.clean(cx),
2345             attrs: self.attrs.clean(cx),
2346             def_id: local_did,
2347             visibility: self.vis.clean(cx),
2348             stability: get_stability(cx, local_did),
2349             deprecation: get_deprecation(cx, local_did),
2350             inner,
2351         }
2352     }
2353 }
2354
2355 impl Clean<Item> for ty::AssocItem {
2356     fn clean(&self, cx: &DocContext<'_>) -> Item {
2357         let inner = match self.kind {
2358             ty::AssocKind::Const => {
2359                 let ty = cx.tcx.type_of(self.def_id);
2360                 let default = if self.defaultness.has_value() {
2361                     Some(inline::print_inlined_const(cx, self.def_id))
2362                 } else {
2363                     None
2364                 };
2365                 AssocConstItem(ty.clean(cx), default)
2366             }
2367             ty::AssocKind::Method => {
2368                 let generics = (cx.tcx.generics_of(self.def_id),
2369                                 &cx.tcx.explicit_predicates_of(self.def_id)).clean(cx);
2370                 let sig = cx.tcx.fn_sig(self.def_id);
2371                 let mut decl = (self.def_id, sig).clean(cx);
2372
2373                 if self.method_has_self_argument {
2374                     let self_ty = match self.container {
2375                         ty::ImplContainer(def_id) => {
2376                             cx.tcx.type_of(def_id)
2377                         }
2378                         ty::TraitContainer(_) => cx.tcx.types.self_param,
2379                     };
2380                     let self_arg_ty = *sig.input(0).skip_binder();
2381                     if self_arg_ty == self_ty {
2382                         decl.inputs.values[0].type_ = Generic(String::from("Self"));
2383                     } else if let ty::Ref(_, ty, _) = self_arg_ty.kind {
2384                         if ty == self_ty {
2385                             match decl.inputs.values[0].type_ {
2386                                 BorrowedRef{ref mut type_, ..} => {
2387                                     **type_ = Generic(String::from("Self"))
2388                                 }
2389                                 _ => unreachable!(),
2390                             }
2391                         }
2392                     }
2393                 }
2394
2395                 let provided = match self.container {
2396                     ty::ImplContainer(_) => true,
2397                     ty::TraitContainer(_) => self.defaultness.has_value()
2398                 };
2399                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
2400                 if provided {
2401                     let constness = if cx.tcx.is_min_const_fn(self.def_id) {
2402                         hir::Constness::Const
2403                     } else {
2404                         hir::Constness::NotConst
2405                     };
2406                     let asyncness = cx.tcx.asyncness(self.def_id);
2407                     let defaultness = match self.container {
2408                         ty::ImplContainer(_) => Some(self.defaultness),
2409                         ty::TraitContainer(_) => None,
2410                     };
2411                     MethodItem(Method {
2412                         generics,
2413                         decl,
2414                         header: hir::FnHeader {
2415                             unsafety: sig.unsafety(),
2416                             abi: sig.abi(),
2417                             constness,
2418                             asyncness,
2419                         },
2420                         defaultness,
2421                         all_types,
2422                         ret_types,
2423                     })
2424                 } else {
2425                     TyMethodItem(TyMethod {
2426                         generics,
2427                         decl,
2428                         header: hir::FnHeader {
2429                             unsafety: sig.unsafety(),
2430                             abi: sig.abi(),
2431                             constness: hir::Constness::NotConst,
2432                             asyncness: hir::IsAsync::NotAsync,
2433                         },
2434                         all_types,
2435                         ret_types,
2436                     })
2437                 }
2438             }
2439             ty::AssocKind::Type => {
2440                 let my_name = self.ident.name.clean(cx);
2441
2442                 if let ty::TraitContainer(did) = self.container {
2443                     // When loading a cross-crate associated type, the bounds for this type
2444                     // are actually located on the trait/impl itself, so we need to load
2445                     // all of the generics from there and then look for bounds that are
2446                     // applied to this associated type in question.
2447                     let predicates = cx.tcx.explicit_predicates_of(did);
2448                     let generics = (cx.tcx.generics_of(did), &predicates).clean(cx);
2449                     let mut bounds = generics.where_predicates.iter().filter_map(|pred| {
2450                         let (name, self_type, trait_, bounds) = match *pred {
2451                             WherePredicate::BoundPredicate {
2452                                 ty: QPath { ref name, ref self_type, ref trait_ },
2453                                 ref bounds
2454                             } => (name, self_type, trait_, bounds),
2455                             _ => return None,
2456                         };
2457                         if *name != my_name { return None }
2458                         match **trait_ {
2459                             ResolvedPath { did, .. } if did == self.container.id() => {}
2460                             _ => return None,
2461                         }
2462                         match **self_type {
2463                             Generic(ref s) if *s == "Self" => {}
2464                             _ => return None,
2465                         }
2466                         Some(bounds)
2467                     }).flat_map(|i| i.iter().cloned()).collect::<Vec<_>>();
2468                     // Our Sized/?Sized bound didn't get handled when creating the generics
2469                     // because we didn't actually get our whole set of bounds until just now
2470                     // (some of them may have come from the trait). If we do have a sized
2471                     // bound, we remove it, and if we don't then we add the `?Sized` bound
2472                     // at the end.
2473                     match bounds.iter().position(|b| b.is_sized_bound(cx)) {
2474                         Some(i) => { bounds.remove(i); }
2475                         None => bounds.push(GenericBound::maybe_sized(cx)),
2476                     }
2477
2478                     let ty = if self.defaultness.has_value() {
2479                         Some(cx.tcx.type_of(self.def_id))
2480                     } else {
2481                         None
2482                     };
2483
2484                     AssocTypeItem(bounds, ty.clean(cx))
2485                 } else {
2486                     TypedefItem(Typedef {
2487                         type_: cx.tcx.type_of(self.def_id).clean(cx),
2488                         generics: Generics {
2489                             params: Vec::new(),
2490                             where_predicates: Vec::new(),
2491                         },
2492                     }, true)
2493                 }
2494             }
2495             ty::AssocKind::OpaqueTy => unimplemented!(),
2496         };
2497
2498         let visibility = match self.container {
2499             ty::ImplContainer(_) => self.vis.clean(cx),
2500             ty::TraitContainer(_) => Inherited,
2501         };
2502
2503         Item {
2504             name: Some(self.ident.name.clean(cx)),
2505             visibility,
2506             stability: get_stability(cx, self.def_id),
2507             deprecation: get_deprecation(cx, self.def_id),
2508             def_id: self.def_id,
2509             attrs: inline::load_attrs(cx, self.def_id).clean(cx),
2510             source: cx.tcx.def_span(self.def_id).clean(cx),
2511             inner,
2512         }
2513     }
2514 }
2515
2516 /// A trait reference, which may have higher ranked lifetimes.
2517 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2518 pub struct PolyTrait {
2519     pub trait_: Type,
2520     pub generic_params: Vec<GenericParamDef>,
2521 }
2522
2523 /// A representation of a type suitable for hyperlinking purposes. Ideally, one can get the original
2524 /// type out of the AST/`TyCtxt` given one of these, if more information is needed. Most
2525 /// importantly, it does not preserve mutability or boxes.
2526 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2527 pub enum Type {
2528     /// Structs/enums/traits (most that would be an `hir::TyKind::Path`).
2529     ResolvedPath {
2530         path: Path,
2531         param_names: Option<Vec<GenericBound>>,
2532         did: DefId,
2533         /// `true` if is a `T::Name` path for associated types.
2534         is_generic: bool,
2535     },
2536     /// For parameterized types, so the consumer of the JSON don't go
2537     /// looking for types which don't exist anywhere.
2538     Generic(String),
2539     /// Primitives are the fixed-size numeric types (plus int/usize/float), char,
2540     /// arrays, slices, and tuples.
2541     Primitive(PrimitiveType),
2542     /// `extern "ABI" fn`
2543     BareFunction(Box<BareFunctionDecl>),
2544     Tuple(Vec<Type>),
2545     Slice(Box<Type>),
2546     Array(Box<Type>, String),
2547     Never,
2548     CVarArgs,
2549     RawPointer(Mutability, Box<Type>),
2550     BorrowedRef {
2551         lifetime: Option<Lifetime>,
2552         mutability: Mutability,
2553         type_: Box<Type>,
2554     },
2555
2556     // `<Type as Trait>::Name`
2557     QPath {
2558         name: String,
2559         self_type: Box<Type>,
2560         trait_: Box<Type>
2561     },
2562
2563     // `_`
2564     Infer,
2565
2566     // `impl TraitA + TraitB + ...`
2567     ImplTrait(Vec<GenericBound>),
2568 }
2569
2570 #[derive(Clone, PartialEq, Eq, Hash, Copy, Debug)]
2571 pub enum PrimitiveType {
2572     Isize, I8, I16, I32, I64, I128,
2573     Usize, U8, U16, U32, U64, U128,
2574     F32, F64,
2575     Char,
2576     Bool,
2577     Str,
2578     Slice,
2579     Array,
2580     Tuple,
2581     Unit,
2582     RawPointer,
2583     Reference,
2584     Fn,
2585     Never,
2586     CVarArgs,
2587 }
2588
2589 #[derive(Clone, Copy, Debug)]
2590 pub enum TypeKind {
2591     Enum,
2592     Function,
2593     Module,
2594     Const,
2595     Static,
2596     Struct,
2597     Union,
2598     Trait,
2599     Typedef,
2600     Foreign,
2601     Macro,
2602     Attr,
2603     Derive,
2604     TraitAlias,
2605 }
2606
2607 pub trait GetDefId {
2608     fn def_id(&self) -> Option<DefId>;
2609 }
2610
2611 impl<T: GetDefId> GetDefId for Option<T> {
2612     fn def_id(&self) -> Option<DefId> {
2613         self.as_ref().and_then(|d| d.def_id())
2614     }
2615 }
2616
2617 impl Type {
2618     pub fn primitive_type(&self) -> Option<PrimitiveType> {
2619         match *self {
2620             Primitive(p) | BorrowedRef { type_: box Primitive(p), ..} => Some(p),
2621             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
2622             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
2623             Tuple(ref tys) => if tys.is_empty() {
2624                 Some(PrimitiveType::Unit)
2625             } else {
2626                 Some(PrimitiveType::Tuple)
2627             },
2628             RawPointer(..) => Some(PrimitiveType::RawPointer),
2629             BorrowedRef { type_: box Generic(..), .. } => Some(PrimitiveType::Reference),
2630             BareFunction(..) => Some(PrimitiveType::Fn),
2631             Never => Some(PrimitiveType::Never),
2632             _ => None,
2633         }
2634     }
2635
2636     pub fn is_generic(&self) -> bool {
2637         match *self {
2638             ResolvedPath { is_generic, .. } => is_generic,
2639             _ => false,
2640         }
2641     }
2642
2643     pub fn is_self_type(&self) -> bool {
2644         match *self {
2645             Generic(ref name) => name == "Self",
2646             _ => false
2647         }
2648     }
2649
2650     pub fn generics(&self) -> Option<Vec<Type>> {
2651         match *self {
2652             ResolvedPath { ref path, .. } => {
2653                 path.segments.last().and_then(|seg| {
2654                     if let GenericArgs::AngleBracketed { ref args, .. } = seg.args {
2655                         Some(args.iter().filter_map(|arg| match arg {
2656                             GenericArg::Type(ty) => Some(ty.clone()),
2657                             _ => None,
2658                         }).collect())
2659                     } else {
2660                         None
2661                     }
2662                 })
2663             }
2664             _ => None,
2665         }
2666     }
2667
2668     pub fn bindings(&self) -> Option<&[TypeBinding]> {
2669         match *self {
2670             ResolvedPath { ref path, .. } => {
2671                 path.segments.last().and_then(|seg| {
2672                     if let GenericArgs::AngleBracketed { ref bindings, .. } = seg.args {
2673                         Some(&**bindings)
2674                     } else {
2675                         None
2676                     }
2677                 })
2678             }
2679             _ => None
2680         }
2681     }
2682
2683     pub fn is_full_generic(&self) -> bool {
2684         match *self {
2685             Type::Generic(_) => true,
2686             _ => false,
2687         }
2688     }
2689
2690     pub fn projection(&self) -> Option<(&Type, DefId, &str)> {
2691         let (self_, trait_, name) = match self {
2692             QPath { ref self_type, ref trait_, ref name } => {
2693                 (self_type, trait_, name)
2694             }
2695             _ => return None,
2696         };
2697         let trait_did = match **trait_ {
2698             ResolvedPath { did, .. } => did,
2699             _ => return None,
2700         };
2701         Some((&self_, trait_did, name))
2702     }
2703
2704 }
2705
2706 impl GetDefId for Type {
2707     fn def_id(&self) -> Option<DefId> {
2708         match *self {
2709             ResolvedPath { did, .. } => Some(did),
2710             Primitive(p) => crate::html::render::cache().primitive_locations.get(&p).cloned(),
2711             BorrowedRef { type_: box Generic(..), .. } =>
2712                 Primitive(PrimitiveType::Reference).def_id(),
2713             BorrowedRef { ref type_, .. } => type_.def_id(),
2714             Tuple(ref tys) => if tys.is_empty() {
2715                 Primitive(PrimitiveType::Unit).def_id()
2716             } else {
2717                 Primitive(PrimitiveType::Tuple).def_id()
2718             },
2719             BareFunction(..) => Primitive(PrimitiveType::Fn).def_id(),
2720             Never => Primitive(PrimitiveType::Never).def_id(),
2721             Slice(..) => Primitive(PrimitiveType::Slice).def_id(),
2722             Array(..) => Primitive(PrimitiveType::Array).def_id(),
2723             RawPointer(..) => Primitive(PrimitiveType::RawPointer).def_id(),
2724             QPath { ref self_type, .. } => self_type.def_id(),
2725             _ => None,
2726         }
2727     }
2728 }
2729
2730 impl PrimitiveType {
2731     fn from_str(s: &str) -> Option<PrimitiveType> {
2732         match s {
2733             "isize" => Some(PrimitiveType::Isize),
2734             "i8" => Some(PrimitiveType::I8),
2735             "i16" => Some(PrimitiveType::I16),
2736             "i32" => Some(PrimitiveType::I32),
2737             "i64" => Some(PrimitiveType::I64),
2738             "i128" => Some(PrimitiveType::I128),
2739             "usize" => Some(PrimitiveType::Usize),
2740             "u8" => Some(PrimitiveType::U8),
2741             "u16" => Some(PrimitiveType::U16),
2742             "u32" => Some(PrimitiveType::U32),
2743             "u64" => Some(PrimitiveType::U64),
2744             "u128" => Some(PrimitiveType::U128),
2745             "bool" => Some(PrimitiveType::Bool),
2746             "char" => Some(PrimitiveType::Char),
2747             "str" => Some(PrimitiveType::Str),
2748             "f32" => Some(PrimitiveType::F32),
2749             "f64" => Some(PrimitiveType::F64),
2750             "array" => Some(PrimitiveType::Array),
2751             "slice" => Some(PrimitiveType::Slice),
2752             "tuple" => Some(PrimitiveType::Tuple),
2753             "unit" => Some(PrimitiveType::Unit),
2754             "pointer" => Some(PrimitiveType::RawPointer),
2755             "reference" => Some(PrimitiveType::Reference),
2756             "fn" => Some(PrimitiveType::Fn),
2757             "never" => Some(PrimitiveType::Never),
2758             _ => None,
2759         }
2760     }
2761
2762     pub fn as_str(&self) -> &'static str {
2763         use self::PrimitiveType::*;
2764         match *self {
2765             Isize => "isize",
2766             I8 => "i8",
2767             I16 => "i16",
2768             I32 => "i32",
2769             I64 => "i64",
2770             I128 => "i128",
2771             Usize => "usize",
2772             U8 => "u8",
2773             U16 => "u16",
2774             U32 => "u32",
2775             U64 => "u64",
2776             U128 => "u128",
2777             F32 => "f32",
2778             F64 => "f64",
2779             Str => "str",
2780             Bool => "bool",
2781             Char => "char",
2782             Array => "array",
2783             Slice => "slice",
2784             Tuple => "tuple",
2785             Unit => "unit",
2786             RawPointer => "pointer",
2787             Reference => "reference",
2788             Fn => "fn",
2789             Never => "never",
2790             CVarArgs => "...",
2791         }
2792     }
2793
2794     pub fn to_url_str(&self) -> &'static str {
2795         self.as_str()
2796     }
2797 }
2798
2799 impl From<ast::IntTy> for PrimitiveType {
2800     fn from(int_ty: ast::IntTy) -> PrimitiveType {
2801         match int_ty {
2802             ast::IntTy::Isize => PrimitiveType::Isize,
2803             ast::IntTy::I8 => PrimitiveType::I8,
2804             ast::IntTy::I16 => PrimitiveType::I16,
2805             ast::IntTy::I32 => PrimitiveType::I32,
2806             ast::IntTy::I64 => PrimitiveType::I64,
2807             ast::IntTy::I128 => PrimitiveType::I128,
2808         }
2809     }
2810 }
2811
2812 impl From<ast::UintTy> for PrimitiveType {
2813     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
2814         match uint_ty {
2815             ast::UintTy::Usize => PrimitiveType::Usize,
2816             ast::UintTy::U8 => PrimitiveType::U8,
2817             ast::UintTy::U16 => PrimitiveType::U16,
2818             ast::UintTy::U32 => PrimitiveType::U32,
2819             ast::UintTy::U64 => PrimitiveType::U64,
2820             ast::UintTy::U128 => PrimitiveType::U128,
2821         }
2822     }
2823 }
2824
2825 impl From<ast::FloatTy> for PrimitiveType {
2826     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
2827         match float_ty {
2828             ast::FloatTy::F32 => PrimitiveType::F32,
2829             ast::FloatTy::F64 => PrimitiveType::F64,
2830         }
2831     }
2832 }
2833
2834 impl Clean<Type> for hir::Ty {
2835     fn clean(&self, cx: &DocContext<'_>) -> Type {
2836         use rustc::hir::*;
2837
2838         match self.node {
2839             TyKind::Never => Never,
2840             TyKind::Ptr(ref m) => RawPointer(m.mutbl.clean(cx), box m.ty.clean(cx)),
2841             TyKind::Rptr(ref l, ref m) => {
2842                 let lifetime = if l.is_elided() {
2843                     None
2844                 } else {
2845                     Some(l.clean(cx))
2846                 };
2847                 BorrowedRef {lifetime: lifetime, mutability: m.mutbl.clean(cx),
2848                              type_: box m.ty.clean(cx)}
2849             }
2850             TyKind::Slice(ref ty) => Slice(box ty.clean(cx)),
2851             TyKind::Array(ref ty, ref length) => {
2852                 let def_id = cx.tcx.hir().local_def_id(length.hir_id);
2853                 let param_env = cx.tcx.param_env(def_id);
2854                 let substs = InternalSubsts::identity_for_item(cx.tcx, def_id);
2855                 let cid = GlobalId {
2856                     instance: ty::Instance::new(def_id, substs),
2857                     promoted: None
2858                 };
2859                 let length = match cx.tcx.const_eval(param_env.and(cid)) {
2860                     Ok(length) => print_const(cx, length),
2861                     Err(_) => cx.sess()
2862                                 .source_map()
2863                                 .span_to_snippet(cx.tcx.def_span(def_id))
2864                                 .unwrap_or_else(|_| "_".to_string()),
2865                 };
2866                 Array(box ty.clean(cx), length)
2867             },
2868             TyKind::Tup(ref tys) => Tuple(tys.clean(cx)),
2869             TyKind::Def(item_id, _) => {
2870                 let item = cx.tcx.hir().expect_item(item_id.id);
2871                 if let hir::ItemKind::OpaqueTy(ref ty) = item.node {
2872                     ImplTrait(ty.bounds.clean(cx))
2873                 } else {
2874                     unreachable!()
2875                 }
2876             }
2877             TyKind::Path(hir::QPath::Resolved(None, ref path)) => {
2878                 if let Res::Def(DefKind::TyParam, did) = path.res {
2879                     if let Some(new_ty) = cx.ty_substs.borrow().get(&did).cloned() {
2880                         return new_ty;
2881                     }
2882                     if let Some(bounds) = cx.impl_trait_bounds.borrow_mut().remove(&did.into()) {
2883                         return ImplTrait(bounds);
2884                     }
2885                 }
2886
2887                 let mut alias = None;
2888                 if let Res::Def(DefKind::TyAlias, def_id) = path.res {
2889                     // Substitute private type aliases
2890                     if let Some(hir_id) = cx.tcx.hir().as_local_hir_id(def_id) {
2891                         if !cx.renderinfo.borrow().access_levels.is_exported(def_id) {
2892                             alias = Some(&cx.tcx.hir().expect_item(hir_id).node);
2893                         }
2894                     }
2895                 };
2896
2897                 if let Some(&hir::ItemKind::TyAlias(ref ty, ref generics)) = alias {
2898                     let provided_params = &path.segments.last().expect("segments were empty");
2899                     let mut ty_substs = FxHashMap::default();
2900                     let mut lt_substs = FxHashMap::default();
2901                     let mut ct_substs = FxHashMap::default();
2902                     let generic_args = provided_params.generic_args();
2903                     {
2904                         let mut indices: GenericParamCount = Default::default();
2905                         for param in generics.params.iter() {
2906                             match param.kind {
2907                                 hir::GenericParamKind::Lifetime { .. } => {
2908                                     let mut j = 0;
2909                                     let lifetime = generic_args.args.iter().find_map(|arg| {
2910                                         match arg {
2911                                             hir::GenericArg::Lifetime(lt) => {
2912                                                 if indices.lifetimes == j {
2913                                                     return Some(lt);
2914                                                 }
2915                                                 j += 1;
2916                                                 None
2917                                             }
2918                                             _ => None,
2919                                         }
2920                                     });
2921                                     if let Some(lt) = lifetime.cloned() {
2922                                         if !lt.is_elided() {
2923                                             let lt_def_id =
2924                                                 cx.tcx.hir().local_def_id(param.hir_id);
2925                                             lt_substs.insert(lt_def_id, lt.clean(cx));
2926                                         }
2927                                     }
2928                                     indices.lifetimes += 1;
2929                                 }
2930                                 hir::GenericParamKind::Type { ref default, .. } => {
2931                                     let ty_param_def_id =
2932                                         cx.tcx.hir().local_def_id(param.hir_id);
2933                                     let mut j = 0;
2934                                     let type_ = generic_args.args.iter().find_map(|arg| {
2935                                         match arg {
2936                                             hir::GenericArg::Type(ty) => {
2937                                                 if indices.types == j {
2938                                                     return Some(ty);
2939                                                 }
2940                                                 j += 1;
2941                                                 None
2942                                             }
2943                                             _ => None,
2944                                         }
2945                                     });
2946                                     if let Some(ty) = type_ {
2947                                         ty_substs.insert(ty_param_def_id, ty.clean(cx));
2948                                     } else if let Some(default) = default.clone() {
2949                                         ty_substs.insert(ty_param_def_id,
2950                                                          default.clean(cx));
2951                                     }
2952                                     indices.types += 1;
2953                                 }
2954                                 hir::GenericParamKind::Const { .. } => {
2955                                     let const_param_def_id =
2956                                         cx.tcx.hir().local_def_id(param.hir_id);
2957                                     let mut j = 0;
2958                                     let const_ = generic_args.args.iter().find_map(|arg| {
2959                                         match arg {
2960                                             hir::GenericArg::Const(ct) => {
2961                                                 if indices.consts == j {
2962                                                     return Some(ct);
2963                                                 }
2964                                                 j += 1;
2965                                                 None
2966                                             }
2967                                             _ => None,
2968                                         }
2969                                     });
2970                                     if let Some(ct) = const_ {
2971                                         ct_substs.insert(const_param_def_id, ct.clean(cx));
2972                                     }
2973                                     // FIXME(const_generics:defaults)
2974                                     indices.consts += 1;
2975                                 }
2976                             }
2977                         }
2978                     }
2979                     return cx.enter_alias(ty_substs, lt_substs, ct_substs, || ty.clean(cx));
2980                 }
2981                 resolve_type(cx, path.clean(cx), self.hir_id)
2982             }
2983             TyKind::Path(hir::QPath::Resolved(Some(ref qself), ref p)) => {
2984                 let segments = if p.is_global() { &p.segments[1..] } else { &p.segments };
2985                 let trait_segments = &segments[..segments.len() - 1];
2986                 let trait_path = self::Path {
2987                     global: p.is_global(),
2988                     res: Res::Def(
2989                         DefKind::Trait,
2990                         cx.tcx.associated_item(p.res.def_id()).container.id(),
2991                     ),
2992                     segments: trait_segments.clean(cx),
2993                 };
2994                 Type::QPath {
2995                     name: p.segments.last().expect("segments were empty").ident.name.clean(cx),
2996                     self_type: box qself.clean(cx),
2997                     trait_: box resolve_type(cx, trait_path, self.hir_id)
2998                 }
2999             }
3000             TyKind::Path(hir::QPath::TypeRelative(ref qself, ref segment)) => {
3001                 let mut res = Res::Err;
3002                 let ty = hir_ty_to_ty(cx.tcx, self);
3003                 if let ty::Projection(proj) = ty.kind {
3004                     res = Res::Def(DefKind::Trait, proj.trait_ref(cx.tcx).def_id);
3005                 }
3006                 let trait_path = hir::Path {
3007                     span: self.span,
3008                     res,
3009                     segments: vec![].into(),
3010                 };
3011                 Type::QPath {
3012                     name: segment.ident.name.clean(cx),
3013                     self_type: box qself.clean(cx),
3014                     trait_: box resolve_type(cx, trait_path.clean(cx), self.hir_id)
3015                 }
3016             }
3017             TyKind::TraitObject(ref bounds, ref lifetime) => {
3018                 match bounds[0].clean(cx).trait_ {
3019                     ResolvedPath { path, param_names: None, did, is_generic } => {
3020                         let mut bounds: Vec<self::GenericBound> = bounds[1..].iter().map(|bound| {
3021                             self::GenericBound::TraitBound(bound.clean(cx),
3022                                                            hir::TraitBoundModifier::None)
3023                         }).collect();
3024                         if !lifetime.is_elided() {
3025                             bounds.push(self::GenericBound::Outlives(lifetime.clean(cx)));
3026                         }
3027                         ResolvedPath { path, param_names: Some(bounds), did, is_generic, }
3028                     }
3029                     _ => Infer, // shouldn't happen
3030                 }
3031             }
3032             TyKind::BareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
3033             TyKind::Infer | TyKind::Err => Infer,
3034             TyKind::Typeof(..) => panic!("unimplemented type {:?}", self.node),
3035             TyKind::CVarArgs(_) => CVarArgs,
3036         }
3037     }
3038 }
3039
3040 impl<'tcx> Clean<Type> for Ty<'tcx> {
3041     fn clean(&self, cx: &DocContext<'_>) -> Type {
3042         debug!("cleaning type: {:?}", self);
3043         match self.kind {
3044             ty::Never => Never,
3045             ty::Bool => Primitive(PrimitiveType::Bool),
3046             ty::Char => Primitive(PrimitiveType::Char),
3047             ty::Int(int_ty) => Primitive(int_ty.into()),
3048             ty::Uint(uint_ty) => Primitive(uint_ty.into()),
3049             ty::Float(float_ty) => Primitive(float_ty.into()),
3050             ty::Str => Primitive(PrimitiveType::Str),
3051             ty::Slice(ty) => Slice(box ty.clean(cx)),
3052             ty::Array(ty, n) => {
3053                 let mut n = cx.tcx.lift(&n).expect("array lift failed");
3054                 if let ConstValue::Unevaluated(def_id, substs) = n.val {
3055                     let param_env = cx.tcx.param_env(def_id);
3056                     let cid = GlobalId {
3057                         instance: ty::Instance::new(def_id, substs),
3058                         promoted: None
3059                     };
3060                     if let Ok(new_n) = cx.tcx.const_eval(param_env.and(cid)) {
3061                         n = new_n;
3062                     }
3063                 };
3064                 let n = print_const(cx, n);
3065                 Array(box ty.clean(cx), n)
3066             }
3067             ty::RawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
3068             ty::Ref(r, ty, mutbl) => BorrowedRef {
3069                 lifetime: r.clean(cx),
3070                 mutability: mutbl.clean(cx),
3071                 type_: box ty.clean(cx),
3072             },
3073             ty::FnDef(..) |
3074             ty::FnPtr(_) => {
3075                 let ty = cx.tcx.lift(self).expect("FnPtr lift failed");
3076                 let sig = ty.fn_sig(cx.tcx);
3077                 let local_def_id = cx.tcx.hir().local_def_id_from_node_id(ast::CRATE_NODE_ID);
3078                 BareFunction(box BareFunctionDecl {
3079                     unsafety: sig.unsafety(),
3080                     generic_params: Vec::new(),
3081                     decl: (local_def_id, sig).clean(cx),
3082                     abi: sig.abi(),
3083                 })
3084             }
3085             ty::Adt(def, substs) => {
3086                 let did = def.did;
3087                 let kind = match def.adt_kind() {
3088                     AdtKind::Struct => TypeKind::Struct,
3089                     AdtKind::Union => TypeKind::Union,
3090                     AdtKind::Enum => TypeKind::Enum,
3091                 };
3092                 inline::record_extern_fqn(cx, did, kind);
3093                 let path = external_path(cx, cx.tcx.item_name(did), None, false, vec![], substs);
3094                 ResolvedPath {
3095                     path,
3096                     param_names: None,
3097                     did,
3098                     is_generic: false,
3099                 }
3100             }
3101             ty::Foreign(did) => {
3102                 inline::record_extern_fqn(cx, did, TypeKind::Foreign);
3103                 let path = external_path(cx, cx.tcx.item_name(did),
3104                                          None, false, vec![], InternalSubsts::empty());
3105                 ResolvedPath {
3106                     path: path,
3107                     param_names: None,
3108                     did: did,
3109                     is_generic: false,
3110                 }
3111             }
3112             ty::Dynamic(ref obj, ref reg) => {
3113                 // HACK: pick the first `did` as the `did` of the trait object. Someone
3114                 // might want to implement "native" support for marker-trait-only
3115                 // trait objects.
3116                 let mut dids = obj.principal_def_id().into_iter().chain(obj.auto_traits());
3117                 let did = dids.next().unwrap_or_else(|| {
3118                     panic!("found trait object `{:?}` with no traits?", self)
3119                 });
3120                 let substs = match obj.principal() {
3121                     Some(principal) => principal.skip_binder().substs,
3122                     // marker traits have no substs.
3123                     _ => cx.tcx.intern_substs(&[])
3124                 };
3125
3126                 inline::record_extern_fqn(cx, did, TypeKind::Trait);
3127
3128                 let mut param_names = vec![];
3129                 reg.clean(cx).map(|b| param_names.push(GenericBound::Outlives(b)));
3130                 for did in dids {
3131                     let empty = cx.tcx.intern_substs(&[]);
3132                     let path = external_path(cx, cx.tcx.item_name(did),
3133                         Some(did), false, vec![], empty);
3134                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
3135                     let bound = GenericBound::TraitBound(PolyTrait {
3136                         trait_: ResolvedPath {
3137                             path,
3138                             param_names: None,
3139                             did,
3140                             is_generic: false,
3141                         },
3142                         generic_params: Vec::new(),
3143                     }, hir::TraitBoundModifier::None);
3144                     param_names.push(bound);
3145                 }
3146
3147                 let mut bindings = vec![];
3148                 for pb in obj.projection_bounds() {
3149                     bindings.push(TypeBinding {
3150                         name: cx.tcx.associated_item(pb.item_def_id()).ident.name.clean(cx),
3151                         kind: TypeBindingKind::Equality {
3152                             ty: pb.skip_binder().ty.clean(cx)
3153                         },
3154                     });
3155                 }
3156
3157                 let path = external_path(cx, cx.tcx.item_name(did), Some(did),
3158                     false, bindings, substs);
3159                 ResolvedPath {
3160                     path,
3161                     param_names: Some(param_names),
3162                     did,
3163                     is_generic: false,
3164                 }
3165             }
3166             ty::Tuple(ref t) => {
3167                 Tuple(t.iter().map(|t| t.expect_ty()).collect::<Vec<_>>().clean(cx))
3168             }
3169
3170             ty::Projection(ref data) => data.clean(cx),
3171
3172             ty::Param(ref p) => {
3173                 if let Some(bounds) = cx.impl_trait_bounds.borrow_mut().remove(&p.index.into()) {
3174                     ImplTrait(bounds)
3175                 } else {
3176                     Generic(p.name.to_string())
3177                 }
3178             }
3179
3180             ty::Opaque(def_id, substs) => {
3181                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
3182                 // by looking up the projections associated with the def_id.
3183                 let predicates_of = cx.tcx.explicit_predicates_of(def_id);
3184                 let substs = cx.tcx.lift(&substs).expect("Opaque lift failed");
3185                 let bounds = predicates_of.instantiate(cx.tcx, substs);
3186                 let mut regions = vec![];
3187                 let mut has_sized = false;
3188                 let mut bounds = bounds.predicates.iter().filter_map(|predicate| {
3189                     let trait_ref = if let Some(tr) = predicate.to_opt_poly_trait_ref() {
3190                         tr
3191                     } else if let ty::Predicate::TypeOutlives(pred) = *predicate {
3192                         // these should turn up at the end
3193                         pred.skip_binder().1.clean(cx).map(|r| {
3194                             regions.push(GenericBound::Outlives(r))
3195                         });
3196                         return None;
3197                     } else {
3198                         return None;
3199                     };
3200
3201                     if let Some(sized) = cx.tcx.lang_items().sized_trait() {
3202                         if trait_ref.def_id() == sized {
3203                             has_sized = true;
3204                             return None;
3205                         }
3206                     }
3207
3208                     let bounds = bounds.predicates.iter().filter_map(|pred|
3209                         if let ty::Predicate::Projection(proj) = *pred {
3210                             let proj = proj.skip_binder();
3211                             if proj.projection_ty.trait_ref(cx.tcx) == *trait_ref.skip_binder() {
3212                                 Some(TypeBinding {
3213                                     name: cx.tcx.associated_item(proj.projection_ty.item_def_id)
3214                                                 .ident.name.clean(cx),
3215                                     kind: TypeBindingKind::Equality {
3216                                         ty: proj.ty.clean(cx),
3217                                     },
3218                                 })
3219                             } else {
3220                                 None
3221                             }
3222                         } else {
3223                             None
3224                         }
3225                     ).collect();
3226
3227                     Some((trait_ref.skip_binder(), bounds).clean(cx))
3228                 }).collect::<Vec<_>>();
3229                 bounds.extend(regions);
3230                 if !has_sized && !bounds.is_empty() {
3231                     bounds.insert(0, GenericBound::maybe_sized(cx));
3232                 }
3233                 ImplTrait(bounds)
3234             }
3235
3236             ty::Closure(..) | ty::Generator(..) => Tuple(vec![]), // FIXME(pcwalton)
3237
3238             ty::Bound(..) => panic!("Bound"),
3239             ty::Placeholder(..) => panic!("Placeholder"),
3240             ty::UnnormalizedProjection(..) => panic!("UnnormalizedProjection"),
3241             ty::GeneratorWitness(..) => panic!("GeneratorWitness"),
3242             ty::Infer(..) => panic!("Infer"),
3243             ty::Error => panic!("Error"),
3244         }
3245     }
3246 }
3247
3248 impl<'tcx> Clean<Constant> for ty::Const<'tcx> {
3249     fn clean(&self, cx: &DocContext<'_>) -> Constant {
3250         Constant {
3251             type_: self.ty.clean(cx),
3252             expr: format!("{}", self),
3253         }
3254     }
3255 }
3256
3257 impl Clean<Item> for hir::StructField {
3258     fn clean(&self, cx: &DocContext<'_>) -> Item {
3259         let local_did = cx.tcx.hir().local_def_id(self.hir_id);
3260
3261         Item {
3262             name: Some(self.ident.name).clean(cx),
3263             attrs: self.attrs.clean(cx),
3264             source: self.span.clean(cx),
3265             visibility: self.vis.clean(cx),
3266             stability: get_stability(cx, local_did),
3267             deprecation: get_deprecation(cx, local_did),
3268             def_id: local_did,
3269             inner: StructFieldItem(self.ty.clean(cx)),
3270         }
3271     }
3272 }
3273
3274 impl Clean<Item> for ty::FieldDef {
3275     fn clean(&self, cx: &DocContext<'_>) -> Item {
3276         Item {
3277             name: Some(self.ident.name).clean(cx),
3278             attrs: cx.tcx.get_attrs(self.did).clean(cx),
3279             source: cx.tcx.def_span(self.did).clean(cx),
3280             visibility: self.vis.clean(cx),
3281             stability: get_stability(cx, self.did),
3282             deprecation: get_deprecation(cx, self.did),
3283             def_id: self.did,
3284             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
3285         }
3286     }
3287 }
3288
3289 #[derive(Clone, PartialEq, Eq, Debug)]
3290 pub enum Visibility {
3291     Public,
3292     Inherited,
3293     Crate,
3294     Restricted(DefId, Path),
3295 }
3296
3297 impl Clean<Visibility> for hir::Visibility {
3298     fn clean(&self, cx: &DocContext<'_>) -> Visibility {
3299         match self.node {
3300             hir::VisibilityKind::Public => Visibility::Public,
3301             hir::VisibilityKind::Inherited => Visibility::Inherited,
3302             hir::VisibilityKind::Crate(_) => Visibility::Crate,
3303             hir::VisibilityKind::Restricted { ref path, .. } => {
3304                 let path = path.clean(cx);
3305                 let did = register_res(cx, path.res);
3306                 Visibility::Restricted(did, path)
3307             }
3308         }
3309     }
3310 }
3311
3312 impl Clean<Visibility> for ty::Visibility {
3313     fn clean(&self, _: &DocContext<'_>) -> Visibility {
3314         if *self == ty::Visibility::Public { Public } else { Inherited }
3315     }
3316 }
3317
3318 #[derive(Clone, Debug)]
3319 pub struct Struct {
3320     pub struct_type: doctree::StructType,
3321     pub generics: Generics,
3322     pub fields: Vec<Item>,
3323     pub fields_stripped: bool,
3324 }
3325
3326 #[derive(Clone, Debug)]
3327 pub struct Union {
3328     pub struct_type: doctree::StructType,
3329     pub generics: Generics,
3330     pub fields: Vec<Item>,
3331     pub fields_stripped: bool,
3332 }
3333
3334 impl Clean<Item> for doctree::Struct<'_> {
3335     fn clean(&self, cx: &DocContext<'_>) -> Item {
3336         Item {
3337             name: Some(self.name.clean(cx)),
3338             attrs: self.attrs.clean(cx),
3339             source: self.whence.clean(cx),
3340             def_id: cx.tcx.hir().local_def_id(self.id),
3341             visibility: self.vis.clean(cx),
3342             stability: cx.stability(self.id).clean(cx),
3343             deprecation: cx.deprecation(self.id).clean(cx),
3344             inner: StructItem(Struct {
3345                 struct_type: self.struct_type,
3346                 generics: self.generics.clean(cx),
3347                 fields: self.fields.clean(cx),
3348                 fields_stripped: false,
3349             }),
3350         }
3351     }
3352 }
3353
3354 impl Clean<Item> for doctree::Union<'_> {
3355     fn clean(&self, cx: &DocContext<'_>) -> Item {
3356         Item {
3357             name: Some(self.name.clean(cx)),
3358             attrs: self.attrs.clean(cx),
3359             source: self.whence.clean(cx),
3360             def_id: cx.tcx.hir().local_def_id(self.id),
3361             visibility: self.vis.clean(cx),
3362             stability: cx.stability(self.id).clean(cx),
3363             deprecation: cx.deprecation(self.id).clean(cx),
3364             inner: UnionItem(Union {
3365                 struct_type: self.struct_type,
3366                 generics: self.generics.clean(cx),
3367                 fields: self.fields.clean(cx),
3368                 fields_stripped: false,
3369             }),
3370         }
3371     }
3372 }
3373
3374 /// This is a more limited form of the standard Struct, different in that
3375 /// it lacks the things most items have (name, id, parameterization). Found
3376 /// only as a variant in an enum.
3377 #[derive(Clone, Debug)]
3378 pub struct VariantStruct {
3379     pub struct_type: doctree::StructType,
3380     pub fields: Vec<Item>,
3381     pub fields_stripped: bool,
3382 }
3383
3384 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
3385     fn clean(&self, cx: &DocContext<'_>) -> VariantStruct {
3386         VariantStruct {
3387             struct_type: doctree::struct_type_from_def(self),
3388             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
3389             fields_stripped: false,
3390         }
3391     }
3392 }
3393
3394 #[derive(Clone, Debug)]
3395 pub struct Enum {
3396     pub variants: IndexVec<VariantIdx, Item>,
3397     pub generics: Generics,
3398     pub variants_stripped: bool,
3399 }
3400
3401 impl Clean<Item> for doctree::Enum<'_> {
3402     fn clean(&self, cx: &DocContext<'_>) -> Item {
3403         Item {
3404             name: Some(self.name.clean(cx)),
3405             attrs: self.attrs.clean(cx),
3406             source: self.whence.clean(cx),
3407             def_id: cx.tcx.hir().local_def_id(self.id),
3408             visibility: self.vis.clean(cx),
3409             stability: cx.stability(self.id).clean(cx),
3410             deprecation: cx.deprecation(self.id).clean(cx),
3411             inner: EnumItem(Enum {
3412                 variants: self.variants.iter().map(|v| v.clean(cx)).collect(),
3413                 generics: self.generics.clean(cx),
3414                 variants_stripped: false,
3415             }),
3416         }
3417     }
3418 }
3419
3420 #[derive(Clone, Debug)]
3421 pub struct Variant {
3422     pub kind: VariantKind,
3423 }
3424
3425 impl Clean<Item> for doctree::Variant<'_> {
3426     fn clean(&self, cx: &DocContext<'_>) -> Item {
3427         Item {
3428             name: Some(self.name.clean(cx)),
3429             attrs: self.attrs.clean(cx),
3430             source: self.whence.clean(cx),
3431             visibility: Inherited,
3432             stability: cx.stability(self.id).clean(cx),
3433             deprecation: cx.deprecation(self.id).clean(cx),
3434             def_id: cx.tcx.hir().local_def_id(self.id),
3435             inner: VariantItem(Variant {
3436                 kind: self.def.clean(cx),
3437             }),
3438         }
3439     }
3440 }
3441
3442 impl Clean<Item> for ty::VariantDef {
3443     fn clean(&self, cx: &DocContext<'_>) -> Item {
3444         let kind = match self.ctor_kind {
3445             CtorKind::Const => VariantKind::CLike,
3446             CtorKind::Fn => {
3447                 VariantKind::Tuple(
3448                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
3449                 )
3450             }
3451             CtorKind::Fictive => {
3452                 VariantKind::Struct(VariantStruct {
3453                     struct_type: doctree::Plain,
3454                     fields_stripped: false,
3455                     fields: self.fields.iter().map(|field| {
3456                         Item {
3457                             source: cx.tcx.def_span(field.did).clean(cx),
3458                             name: Some(field.ident.name.clean(cx)),
3459                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
3460                             visibility: field.vis.clean(cx),
3461                             def_id: field.did,
3462                             stability: get_stability(cx, field.did),
3463                             deprecation: get_deprecation(cx, field.did),
3464                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
3465                         }
3466                     }).collect()
3467                 })
3468             }
3469         };
3470         Item {
3471             name: Some(self.ident.clean(cx)),
3472             attrs: inline::load_attrs(cx, self.def_id).clean(cx),
3473             source: cx.tcx.def_span(self.def_id).clean(cx),
3474             visibility: Inherited,
3475             def_id: self.def_id,
3476             inner: VariantItem(Variant { kind }),
3477             stability: get_stability(cx, self.def_id),
3478             deprecation: get_deprecation(cx, self.def_id),
3479         }
3480     }
3481 }
3482
3483 #[derive(Clone, Debug)]
3484 pub enum VariantKind {
3485     CLike,
3486     Tuple(Vec<Type>),
3487     Struct(VariantStruct),
3488 }
3489
3490 impl Clean<VariantKind> for hir::VariantData {
3491     fn clean(&self, cx: &DocContext<'_>) -> VariantKind {
3492         match self {
3493             hir::VariantData::Struct(..) => VariantKind::Struct(self.clean(cx)),
3494             hir::VariantData::Tuple(..) =>
3495                 VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect()),
3496             hir::VariantData::Unit(..) => VariantKind::CLike,
3497         }
3498     }
3499 }
3500
3501 #[derive(Clone, Debug)]
3502 pub struct Span {
3503     pub filename: FileName,
3504     pub loline: usize,
3505     pub locol: usize,
3506     pub hiline: usize,
3507     pub hicol: usize,
3508     pub original: syntax_pos::Span,
3509 }
3510
3511 impl Span {
3512     pub fn empty() -> Span {
3513         Span {
3514             filename: FileName::Anon(0),
3515             loline: 0, locol: 0,
3516             hiline: 0, hicol: 0,
3517             original: syntax_pos::DUMMY_SP,
3518         }
3519     }
3520
3521     pub fn span(&self) -> syntax_pos::Span {
3522         self.original
3523     }
3524 }
3525
3526 impl Clean<Span> for syntax_pos::Span {
3527     fn clean(&self, cx: &DocContext<'_>) -> Span {
3528         if self.is_dummy() {
3529             return Span::empty();
3530         }
3531
3532         let cm = cx.sess().source_map();
3533         let filename = cm.span_to_filename(*self);
3534         let lo = cm.lookup_char_pos(self.lo());
3535         let hi = cm.lookup_char_pos(self.hi());
3536         Span {
3537             filename,
3538             loline: lo.line,
3539             locol: lo.col.to_usize(),
3540             hiline: hi.line,
3541             hicol: hi.col.to_usize(),
3542             original: *self,
3543         }
3544     }
3545 }
3546
3547 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
3548 pub struct Path {
3549     pub global: bool,
3550     pub res: Res,
3551     pub segments: Vec<PathSegment>,
3552 }
3553
3554 impl Path {
3555     pub fn last_name(&self) -> &str {
3556         self.segments.last().expect("segments were empty").name.as_str()
3557     }
3558 }
3559
3560 impl Clean<Path> for hir::Path {
3561     fn clean(&self, cx: &DocContext<'_>) -> Path {
3562         Path {
3563             global: self.is_global(),
3564             res: self.res,
3565             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
3566         }
3567     }
3568 }
3569
3570 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
3571 pub enum GenericArg {
3572     Lifetime(Lifetime),
3573     Type(Type),
3574     Const(Constant),
3575 }
3576
3577 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
3578 pub enum GenericArgs {
3579     AngleBracketed {
3580         args: Vec<GenericArg>,
3581         bindings: Vec<TypeBinding>,
3582     },
3583     Parenthesized {
3584         inputs: Vec<Type>,
3585         output: Option<Type>,
3586     }
3587 }
3588
3589 impl Clean<GenericArgs> for hir::GenericArgs {
3590     fn clean(&self, cx: &DocContext<'_>) -> GenericArgs {
3591         if self.parenthesized {
3592             let output = self.bindings[0].ty().clean(cx);
3593             GenericArgs::Parenthesized {
3594                 inputs: self.inputs().clean(cx),
3595                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
3596             }
3597         } else {
3598             let elide_lifetimes = self.args.iter().all(|arg| match arg {
3599                 hir::GenericArg::Lifetime(lt) => lt.is_elided(),
3600                 _ => true,
3601             });
3602             GenericArgs::AngleBracketed {
3603                 args: self.args.iter().filter_map(|arg| match arg {
3604                     hir::GenericArg::Lifetime(lt) if !elide_lifetimes => {
3605                         Some(GenericArg::Lifetime(lt.clean(cx)))
3606                     }
3607                     hir::GenericArg::Lifetime(_) => None,
3608                     hir::GenericArg::Type(ty) => Some(GenericArg::Type(ty.clean(cx))),
3609                     hir::GenericArg::Const(ct) => Some(GenericArg::Const(ct.clean(cx))),
3610                 }).collect(),
3611                 bindings: self.bindings.clean(cx),
3612             }
3613         }
3614     }
3615 }
3616
3617 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
3618 pub struct PathSegment {
3619     pub name: String,
3620     pub args: GenericArgs,
3621 }
3622
3623 impl Clean<PathSegment> for hir::PathSegment {
3624     fn clean(&self, cx: &DocContext<'_>) -> PathSegment {
3625         PathSegment {
3626             name: self.ident.name.clean(cx),
3627             args: self.generic_args().clean(cx),
3628         }
3629     }
3630 }
3631
3632 fn strip_type(ty: Type) -> Type {
3633     match ty {
3634         Type::ResolvedPath { path, param_names, did, is_generic } => {
3635             Type::ResolvedPath { path: strip_path(&path), param_names, did, is_generic }
3636         }
3637         Type::Tuple(inner_tys) => {
3638             Type::Tuple(inner_tys.iter().map(|t| strip_type(t.clone())).collect())
3639         }
3640         Type::Slice(inner_ty) => Type::Slice(Box::new(strip_type(*inner_ty))),
3641         Type::Array(inner_ty, s) => Type::Array(Box::new(strip_type(*inner_ty)), s),
3642         Type::RawPointer(m, inner_ty) => Type::RawPointer(m, Box::new(strip_type(*inner_ty))),
3643         Type::BorrowedRef { lifetime, mutability, type_ } => {
3644             Type::BorrowedRef { lifetime, mutability, type_: Box::new(strip_type(*type_)) }
3645         }
3646         Type::QPath { name, self_type, trait_ } => {
3647             Type::QPath {
3648                 name,
3649                 self_type: Box::new(strip_type(*self_type)), trait_: Box::new(strip_type(*trait_))
3650             }
3651         }
3652         _ => ty
3653     }
3654 }
3655
3656 fn strip_path(path: &Path) -> Path {
3657     let segments = path.segments.iter().map(|s| {
3658         PathSegment {
3659             name: s.name.clone(),
3660             args: GenericArgs::AngleBracketed {
3661                 args: vec![],
3662                 bindings: vec![],
3663             }
3664         }
3665     }).collect();
3666
3667     Path {
3668         global: path.global,
3669         res: path.res.clone(),
3670         segments,
3671     }
3672 }
3673
3674 fn qpath_to_string(p: &hir::QPath) -> String {
3675     let segments = match *p {
3676         hir::QPath::Resolved(_, ref path) => &path.segments,
3677         hir::QPath::TypeRelative(_, ref segment) => return segment.ident.to_string(),
3678     };
3679
3680     let mut s = String::new();
3681     for (i, seg) in segments.iter().enumerate() {
3682         if i > 0 {
3683             s.push_str("::");
3684         }
3685         if seg.ident.name != kw::PathRoot {
3686             s.push_str(&*seg.ident.as_str());
3687         }
3688     }
3689     s
3690 }
3691
3692 impl Clean<String> for Ident {
3693     #[inline]
3694     fn clean(&self, cx: &DocContext<'_>) -> String {
3695         self.name.clean(cx)
3696     }
3697 }
3698
3699 impl Clean<String> for ast::Name {
3700     #[inline]
3701     fn clean(&self, _: &DocContext<'_>) -> String {
3702         self.to_string()
3703     }
3704 }
3705
3706 impl Clean<String> for InternedString {
3707     #[inline]
3708     fn clean(&self, _: &DocContext<'_>) -> String {
3709         self.to_string()
3710     }
3711 }
3712
3713 #[derive(Clone, Debug)]
3714 pub struct Typedef {
3715     pub type_: Type,
3716     pub generics: Generics,
3717 }
3718
3719 impl Clean<Item> for doctree::Typedef<'_> {
3720     fn clean(&self, cx: &DocContext<'_>) -> Item {
3721         Item {
3722             name: Some(self.name.clean(cx)),
3723             attrs: self.attrs.clean(cx),
3724             source: self.whence.clean(cx),
3725             def_id: cx.tcx.hir().local_def_id(self.id),
3726             visibility: self.vis.clean(cx),
3727             stability: cx.stability(self.id).clean(cx),
3728             deprecation: cx.deprecation(self.id).clean(cx),
3729             inner: TypedefItem(Typedef {
3730                 type_: self.ty.clean(cx),
3731                 generics: self.gen.clean(cx),
3732             }, false),
3733         }
3734     }
3735 }
3736
3737 #[derive(Clone, Debug)]
3738 pub struct OpaqueTy {
3739     pub bounds: Vec<GenericBound>,
3740     pub generics: Generics,
3741 }
3742
3743 impl Clean<Item> for doctree::OpaqueTy<'_> {
3744     fn clean(&self, cx: &DocContext<'_>) -> Item {
3745         Item {
3746             name: Some(self.name.clean(cx)),
3747             attrs: self.attrs.clean(cx),
3748             source: self.whence.clean(cx),
3749             def_id: cx.tcx.hir().local_def_id(self.id),
3750             visibility: self.vis.clean(cx),
3751             stability: cx.stability(self.id).clean(cx),
3752             deprecation: cx.deprecation(self.id).clean(cx),
3753             inner: OpaqueTyItem(OpaqueTy {
3754                 bounds: self.opaque_ty.bounds.clean(cx),
3755                 generics: self.opaque_ty.generics.clean(cx),
3756             }, false),
3757         }
3758     }
3759 }
3760
3761 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
3762 pub struct BareFunctionDecl {
3763     pub unsafety: hir::Unsafety,
3764     pub generic_params: Vec<GenericParamDef>,
3765     pub decl: FnDecl,
3766     pub abi: Abi,
3767 }
3768
3769 impl Clean<BareFunctionDecl> for hir::BareFnTy {
3770     fn clean(&self, cx: &DocContext<'_>) -> BareFunctionDecl {
3771         let (generic_params, decl) = enter_impl_trait(cx, || {
3772             (self.generic_params.clean(cx), (&*self.decl, &self.param_names[..]).clean(cx))
3773         });
3774         BareFunctionDecl {
3775             unsafety: self.unsafety,
3776             abi: self.abi,
3777             decl,
3778             generic_params,
3779         }
3780     }
3781 }
3782
3783 #[derive(Clone, Debug)]
3784 pub struct Static {
3785     pub type_: Type,
3786     pub mutability: Mutability,
3787     /// It's useful to have the value of a static documented, but I have no
3788     /// desire to represent expressions (that'd basically be all of the AST,
3789     /// which is huge!). So, have a string.
3790     pub expr: String,
3791 }
3792
3793 impl Clean<Item> for doctree::Static<'_> {
3794     fn clean(&self, cx: &DocContext<'_>) -> Item {
3795         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
3796         Item {
3797             name: Some(self.name.clean(cx)),
3798             attrs: self.attrs.clean(cx),
3799             source: self.whence.clean(cx),
3800             def_id: cx.tcx.hir().local_def_id(self.id),
3801             visibility: self.vis.clean(cx),
3802             stability: cx.stability(self.id).clean(cx),
3803             deprecation: cx.deprecation(self.id).clean(cx),
3804             inner: StaticItem(Static {
3805                 type_: self.type_.clean(cx),
3806                 mutability: self.mutability.clean(cx),
3807                 expr: print_const_expr(cx, self.expr),
3808             }),
3809         }
3810     }
3811 }
3812
3813 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
3814 pub struct Constant {
3815     pub type_: Type,
3816     pub expr: String,
3817 }
3818
3819 impl Clean<Item> for doctree::Constant<'_> {
3820     fn clean(&self, cx: &DocContext<'_>) -> Item {
3821         Item {
3822             name: Some(self.name.clean(cx)),
3823             attrs: self.attrs.clean(cx),
3824             source: self.whence.clean(cx),
3825             def_id: cx.tcx.hir().local_def_id(self.id),
3826             visibility: self.vis.clean(cx),
3827             stability: cx.stability(self.id).clean(cx),
3828             deprecation: cx.deprecation(self.id).clean(cx),
3829             inner: ConstantItem(Constant {
3830                 type_: self.type_.clean(cx),
3831                 expr: print_const_expr(cx, self.expr),
3832             }),
3833         }
3834     }
3835 }
3836
3837 #[derive(Debug, Clone, PartialEq, Eq, Copy, Hash)]
3838 pub enum Mutability {
3839     Mutable,
3840     Immutable,
3841 }
3842
3843 impl Clean<Mutability> for hir::Mutability {
3844     fn clean(&self, _: &DocContext<'_>) -> Mutability {
3845         match self {
3846             &hir::MutMutable => Mutable,
3847             &hir::MutImmutable => Immutable,
3848         }
3849     }
3850 }
3851
3852 #[derive(Clone, PartialEq, Eq, Copy, Debug, Hash)]
3853 pub enum ImplPolarity {
3854     Positive,
3855     Negative,
3856 }
3857
3858 impl Clean<ImplPolarity> for ty::ImplPolarity {
3859     fn clean(&self, _: &DocContext<'_>) -> ImplPolarity {
3860         match self {
3861             &ty::ImplPolarity::Positive |
3862             // FIXME: do we want to do something else here?
3863             &ty::ImplPolarity::Reservation => ImplPolarity::Positive,
3864             &ty::ImplPolarity::Negative => ImplPolarity::Negative,
3865         }
3866     }
3867 }
3868
3869 #[derive(Clone, Debug)]
3870 pub struct Impl {
3871     pub unsafety: hir::Unsafety,
3872     pub generics: Generics,
3873     pub provided_trait_methods: FxHashSet<String>,
3874     pub trait_: Option<Type>,
3875     pub for_: Type,
3876     pub items: Vec<Item>,
3877     pub polarity: Option<ImplPolarity>,
3878     pub synthetic: bool,
3879     pub blanket_impl: Option<Type>,
3880 }
3881
3882 pub fn get_auto_trait_and_blanket_impls(
3883     cx: &DocContext<'tcx>,
3884     ty: Ty<'tcx>,
3885     param_env_def_id: DefId,
3886 ) -> impl Iterator<Item = Item> {
3887     AutoTraitFinder::new(cx).get_auto_trait_impls(ty, param_env_def_id).into_iter()
3888         .chain(BlanketImplFinder::new(cx).get_blanket_impls(ty, param_env_def_id))
3889 }
3890
3891 impl Clean<Vec<Item>> for doctree::Impl<'_> {
3892     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3893         let mut ret = Vec::new();
3894         let trait_ = self.trait_.clean(cx);
3895         let items = self.items.iter().map(|ii| ii.clean(cx)).collect::<Vec<_>>();
3896         let def_id = cx.tcx.hir().local_def_id(self.id);
3897
3898         // If this impl block is an implementation of the Deref trait, then we
3899         // need to try inlining the target's inherent impl blocks as well.
3900         if trait_.def_id() == cx.tcx.lang_items().deref_trait() {
3901             build_deref_target_impls(cx, &items, &mut ret);
3902         }
3903
3904         let provided = trait_.def_id().map(|did| {
3905             cx.tcx.provided_trait_methods(did)
3906                   .into_iter()
3907                   .map(|meth| meth.ident.to_string())
3908                   .collect()
3909         }).unwrap_or_default();
3910
3911         ret.push(Item {
3912             name: None,
3913             attrs: self.attrs.clean(cx),
3914             source: self.whence.clean(cx),
3915             def_id,
3916             visibility: self.vis.clean(cx),
3917             stability: cx.stability(self.id).clean(cx),
3918             deprecation: cx.deprecation(self.id).clean(cx),
3919             inner: ImplItem(Impl {
3920                 unsafety: self.unsafety,
3921                 generics: self.generics.clean(cx),
3922                 provided_trait_methods: provided,
3923                 trait_,
3924                 for_: self.for_.clean(cx),
3925                 items,
3926                 polarity: Some(cx.tcx.impl_polarity(def_id).clean(cx)),
3927                 synthetic: false,
3928                 blanket_impl: None,
3929             })
3930         });
3931         ret
3932     }
3933 }
3934
3935 fn build_deref_target_impls(cx: &DocContext<'_>,
3936                             items: &[Item],
3937                             ret: &mut Vec<Item>) {
3938     use self::PrimitiveType::*;
3939     let tcx = cx.tcx;
3940
3941     for item in items {
3942         let target = match item.inner {
3943             TypedefItem(ref t, true) => &t.type_,
3944             _ => continue,
3945         };
3946         let primitive = match *target {
3947             ResolvedPath { did, .. } if did.is_local() => continue,
3948             ResolvedPath { did, .. } => {
3949                 ret.extend(inline::build_impls(cx, did, None));
3950                 continue
3951             }
3952             _ => match target.primitive_type() {
3953                 Some(prim) => prim,
3954                 None => continue,
3955             }
3956         };
3957         let did = match primitive {
3958             Isize => tcx.lang_items().isize_impl(),
3959             I8 => tcx.lang_items().i8_impl(),
3960             I16 => tcx.lang_items().i16_impl(),
3961             I32 => tcx.lang_items().i32_impl(),
3962             I64 => tcx.lang_items().i64_impl(),
3963             I128 => tcx.lang_items().i128_impl(),
3964             Usize => tcx.lang_items().usize_impl(),
3965             U8 => tcx.lang_items().u8_impl(),
3966             U16 => tcx.lang_items().u16_impl(),
3967             U32 => tcx.lang_items().u32_impl(),
3968             U64 => tcx.lang_items().u64_impl(),
3969             U128 => tcx.lang_items().u128_impl(),
3970             F32 => tcx.lang_items().f32_impl(),
3971             F64 => tcx.lang_items().f64_impl(),
3972             Char => tcx.lang_items().char_impl(),
3973             Bool => tcx.lang_items().bool_impl(),
3974             Str => tcx.lang_items().str_impl(),
3975             Slice => tcx.lang_items().slice_impl(),
3976             Array => tcx.lang_items().slice_impl(),
3977             Tuple => None,
3978             Unit => None,
3979             RawPointer => tcx.lang_items().const_ptr_impl(),
3980             Reference => None,
3981             Fn => None,
3982             Never => None,
3983             CVarArgs => tcx.lang_items().va_list(),
3984         };
3985         if let Some(did) = did {
3986             if !did.is_local() {
3987                 inline::build_impl(cx, did, None, ret);
3988             }
3989         }
3990     }
3991 }
3992
3993 impl Clean<Vec<Item>> for doctree::ExternCrate<'_> {
3994     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3995
3996         let please_inline = self.vis.node.is_pub() && self.attrs.iter().any(|a| {
3997             a.check_name(sym::doc) && match a.meta_item_list() {
3998                 Some(l) => attr::list_contains_name(&l, sym::inline),
3999                 None => false,
4000             }
4001         });
4002
4003         if please_inline {
4004             let mut visited = FxHashSet::default();
4005
4006             let res = Res::Def(
4007                 DefKind::Mod,
4008                 DefId {
4009                     krate: self.cnum,
4010                     index: CRATE_DEF_INDEX,
4011                 },
4012             );
4013
4014             if let Some(items) = inline::try_inline(
4015                 cx, res, self.name,
4016                 Some(rustc::ty::Attributes::Borrowed(self.attrs)),
4017                 &mut visited
4018             ) {
4019                 return items;
4020             }
4021         }
4022
4023         vec![Item {
4024             name: None,
4025             attrs: self.attrs.clean(cx),
4026             source: self.whence.clean(cx),
4027             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
4028             visibility: self.vis.clean(cx),
4029             stability: None,
4030             deprecation: None,
4031             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
4032         }]
4033     }
4034 }
4035
4036 impl Clean<Vec<Item>> for doctree::Import<'_> {
4037     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
4038         // We consider inlining the documentation of `pub use` statements, but we
4039         // forcefully don't inline if this is not public or if the
4040         // #[doc(no_inline)] attribute is present.
4041         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
4042         let mut denied = !self.vis.node.is_pub() || self.attrs.iter().any(|a| {
4043             a.check_name(sym::doc) && match a.meta_item_list() {
4044                 Some(l) => attr::list_contains_name(&l, sym::no_inline) ||
4045                            attr::list_contains_name(&l, sym::hidden),
4046                 None => false,
4047             }
4048         });
4049         // Also check whether imports were asked to be inlined, in case we're trying to re-export a
4050         // crate in Rust 2018+
4051         let please_inline = self.attrs.lists(sym::doc).has_word(sym::inline);
4052         let path = self.path.clean(cx);
4053         let inner = if self.glob {
4054             if !denied {
4055                 let mut visited = FxHashSet::default();
4056                 if let Some(items) = inline::try_inline_glob(cx, path.res, &mut visited) {
4057                     return items;
4058                 }
4059             }
4060
4061             Import::Glob(resolve_use_source(cx, path))
4062         } else {
4063             let name = self.name;
4064             if !please_inline {
4065                 match path.res {
4066                     Res::Def(DefKind::Mod, did) => {
4067                         if !did.is_local() && did.index == CRATE_DEF_INDEX {
4068                             // if we're `pub use`ing an extern crate root, don't inline it unless we
4069                             // were specifically asked for it
4070                             denied = true;
4071                         }
4072                     }
4073                     _ => {}
4074                 }
4075             }
4076             if !denied {
4077                 let mut visited = FxHashSet::default();
4078                 if let Some(items) = inline::try_inline(
4079                     cx, path.res, name,
4080                     Some(rustc::ty::Attributes::Borrowed(self.attrs)),
4081                     &mut visited
4082                 ) {
4083                     return items;
4084                 }
4085             }
4086             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
4087         };
4088
4089         vec![Item {
4090             name: None,
4091             attrs: self.attrs.clean(cx),
4092             source: self.whence.clean(cx),
4093             def_id: cx.tcx.hir().local_def_id_from_node_id(ast::CRATE_NODE_ID),
4094             visibility: self.vis.clean(cx),
4095             stability: None,
4096             deprecation: None,
4097             inner: ImportItem(inner)
4098         }]
4099     }
4100 }
4101
4102 #[derive(Clone, Debug)]
4103 pub enum Import {
4104     // use source as str;
4105     Simple(String, ImportSource),
4106     // use source::*;
4107     Glob(ImportSource)
4108 }
4109
4110 #[derive(Clone, Debug)]
4111 pub struct ImportSource {
4112     pub path: Path,
4113     pub did: Option<DefId>,
4114 }
4115
4116 impl Clean<Item> for doctree::ForeignItem<'_> {
4117     fn clean(&self, cx: &DocContext<'_>) -> Item {
4118         let inner = match self.kind {
4119             hir::ForeignItemKind::Fn(ref decl, ref names, ref generics) => {
4120                 let abi = cx.tcx.hir().get_foreign_abi(self.id);
4121                 let (generics, decl) = enter_impl_trait(cx, || {
4122                     (generics.clean(cx), (&**decl, &names[..]).clean(cx))
4123                 });
4124                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
4125                 ForeignFunctionItem(Function {
4126                     decl,
4127                     generics,
4128                     header: hir::FnHeader {
4129                         unsafety: hir::Unsafety::Unsafe,
4130                         abi,
4131                         constness: hir::Constness::NotConst,
4132                         asyncness: hir::IsAsync::NotAsync,
4133                     },
4134                     all_types,
4135                     ret_types,
4136                 })
4137             }
4138             hir::ForeignItemKind::Static(ref ty, mutbl) => {
4139                 ForeignStaticItem(Static {
4140                     type_: ty.clean(cx),
4141                     mutability: mutbl.clean(cx),
4142                     expr: String::new(),
4143                 })
4144             }
4145             hir::ForeignItemKind::Type => {
4146                 ForeignTypeItem
4147             }
4148         };
4149
4150         Item {
4151             name: Some(self.name.clean(cx)),
4152             attrs: self.attrs.clean(cx),
4153             source: self.whence.clean(cx),
4154             def_id: cx.tcx.hir().local_def_id(self.id),
4155             visibility: self.vis.clean(cx),
4156             stability: cx.stability(self.id).clean(cx),
4157             deprecation: cx.deprecation(self.id).clean(cx),
4158             inner,
4159         }
4160     }
4161 }
4162
4163 // Utilities
4164
4165 pub trait ToSource {
4166     fn to_src(&self, cx: &DocContext<'_>) -> String;
4167 }
4168
4169 impl ToSource for syntax_pos::Span {
4170     fn to_src(&self, cx: &DocContext<'_>) -> String {
4171         debug!("converting span {:?} to snippet", self.clean(cx));
4172         let sn = match cx.sess().source_map().span_to_snippet(*self) {
4173             Ok(x) => x,
4174             Err(_) => String::new()
4175         };
4176         debug!("got snippet {}", sn);
4177         sn
4178     }
4179 }
4180
4181 fn name_from_pat(p: &hir::Pat) -> String {
4182     use rustc::hir::*;
4183     debug!("trying to get a name from pattern: {:?}", p);
4184
4185     match p.kind {
4186         PatKind::Wild => "_".to_string(),
4187         PatKind::Binding(_, _, ident, _) => ident.to_string(),
4188         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
4189         PatKind::Struct(ref name, ref fields, etc) => {
4190             format!("{} {{ {}{} }}", qpath_to_string(name),
4191                 fields.iter().map(|fp| format!("{}: {}", fp.ident, name_from_pat(&fp.pat)))
4192                              .collect::<Vec<String>>().join(", "),
4193                 if etc { ", .." } else { "" }
4194             )
4195         }
4196         PatKind::Or(ref pats) => {
4197             pats.iter().map(|p| name_from_pat(&**p)).collect::<Vec<String>>().join(" | ")
4198         }
4199         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
4200                                             .collect::<Vec<String>>().join(", ")),
4201         PatKind::Box(ref p) => name_from_pat(&**p),
4202         PatKind::Ref(ref p, _) => name_from_pat(&**p),
4203         PatKind::Lit(..) => {
4204             warn!("tried to get argument name from PatKind::Lit, \
4205                   which is silly in function arguments");
4206             "()".to_string()
4207         },
4208         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
4209                               which is not allowed in function arguments"),
4210         PatKind::Slice(ref begin, ref mid, ref end) => {
4211             let begin = begin.iter().map(|p| name_from_pat(&**p));
4212             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
4213             let end = end.iter().map(|p| name_from_pat(&**p));
4214             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
4215         },
4216     }
4217 }
4218
4219 fn print_const(cx: &DocContext<'_>, n: &ty::Const<'_>) -> String {
4220     match n.val {
4221         ConstValue::Unevaluated(def_id, _) => {
4222             if let Some(hir_id) = cx.tcx.hir().as_local_hir_id(def_id) {
4223                 print_const_expr(cx, cx.tcx.hir().body_owned_by(hir_id))
4224             } else {
4225                 inline::print_inlined_const(cx, def_id)
4226             }
4227         },
4228         _ => {
4229             let mut s = n.to_string();
4230             // array lengths are obviously usize
4231             if s.ends_with("usize") {
4232                 let n = s.len() - "usize".len();
4233                 s.truncate(n);
4234                 if s.ends_with(": ") {
4235                     let n = s.len() - ": ".len();
4236                     s.truncate(n);
4237                 }
4238             }
4239             s
4240         },
4241     }
4242 }
4243
4244 fn print_const_expr(cx: &DocContext<'_>, body: hir::BodyId) -> String {
4245     cx.tcx.hir().hir_to_pretty_string(body.hir_id)
4246 }
4247
4248 /// Given a type Path, resolve it to a Type using the TyCtxt
4249 fn resolve_type(cx: &DocContext<'_>,
4250                 path: Path,
4251                 id: hir::HirId) -> Type {
4252     if id == hir::DUMMY_HIR_ID {
4253         debug!("resolve_type({:?})", path);
4254     } else {
4255         debug!("resolve_type({:?},{:?})", path, id);
4256     }
4257
4258     let is_generic = match path.res {
4259         Res::PrimTy(p) => match p {
4260             hir::Str => return Primitive(PrimitiveType::Str),
4261             hir::Bool => return Primitive(PrimitiveType::Bool),
4262             hir::Char => return Primitive(PrimitiveType::Char),
4263             hir::Int(int_ty) => return Primitive(int_ty.into()),
4264             hir::Uint(uint_ty) => return Primitive(uint_ty.into()),
4265             hir::Float(float_ty) => return Primitive(float_ty.into()),
4266         },
4267         Res::SelfTy(..) if path.segments.len() == 1 => {
4268             return Generic(kw::SelfUpper.to_string());
4269         }
4270         Res::Def(DefKind::TyParam, _) if path.segments.len() == 1 => {
4271             return Generic(format!("{:#}", path.print()));
4272         }
4273         Res::SelfTy(..)
4274         | Res::Def(DefKind::TyParam, _)
4275         | Res::Def(DefKind::AssocTy, _) => true,
4276         _ => false,
4277     };
4278     let did = register_res(&*cx, path.res);
4279     ResolvedPath { path: path, param_names: None, did: did, is_generic: is_generic }
4280 }
4281
4282 pub fn register_res(cx: &DocContext<'_>, res: Res) -> DefId {
4283     debug!("register_res({:?})", res);
4284
4285     let (did, kind) = match res {
4286         Res::Def(DefKind::Fn, i) => (i, TypeKind::Function),
4287         Res::Def(DefKind::TyAlias, i) => (i, TypeKind::Typedef),
4288         Res::Def(DefKind::Enum, i) => (i, TypeKind::Enum),
4289         Res::Def(DefKind::Trait, i) => (i, TypeKind::Trait),
4290         Res::Def(DefKind::Struct, i) => (i, TypeKind::Struct),
4291         Res::Def(DefKind::Union, i) => (i, TypeKind::Union),
4292         Res::Def(DefKind::Mod, i) => (i, TypeKind::Module),
4293         Res::Def(DefKind::ForeignTy, i) => (i, TypeKind::Foreign),
4294         Res::Def(DefKind::Const, i) => (i, TypeKind::Const),
4295         Res::Def(DefKind::Static, i) => (i, TypeKind::Static),
4296         Res::Def(DefKind::Variant, i) => (cx.tcx.parent(i).expect("cannot get parent def id"),
4297                             TypeKind::Enum),
4298         Res::Def(DefKind::Macro(mac_kind), i) => match mac_kind {
4299             MacroKind::Bang => (i, TypeKind::Macro),
4300             MacroKind::Attr => (i, TypeKind::Attr),
4301             MacroKind::Derive => (i, TypeKind::Derive),
4302         },
4303         Res::Def(DefKind::TraitAlias, i) => (i, TypeKind::TraitAlias),
4304         Res::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
4305         Res::SelfTy(_, Some(impl_def_id)) => return impl_def_id,
4306         _ => return res.def_id()
4307     };
4308     if did.is_local() { return did }
4309     inline::record_extern_fqn(cx, did, kind);
4310     if let TypeKind::Trait = kind {
4311         inline::record_extern_trait(cx, did);
4312     }
4313     did
4314 }
4315
4316 fn resolve_use_source(cx: &DocContext<'_>, path: Path) -> ImportSource {
4317     ImportSource {
4318         did: if path.res.opt_def_id().is_none() {
4319             None
4320         } else {
4321             Some(register_res(cx, path.res))
4322         },
4323         path,
4324     }
4325 }
4326
4327 #[derive(Clone, Debug)]
4328 pub struct Macro {
4329     pub source: String,
4330     pub imported_from: Option<String>,
4331 }
4332
4333 impl Clean<Item> for doctree::Macro<'_> {
4334     fn clean(&self, cx: &DocContext<'_>) -> Item {
4335         let name = self.name.clean(cx);
4336         Item {
4337             name: Some(name.clone()),
4338             attrs: self.attrs.clean(cx),
4339             source: self.whence.clean(cx),
4340             visibility: Public,
4341             stability: cx.stability(self.hid).clean(cx),
4342             deprecation: cx.deprecation(self.hid).clean(cx),
4343             def_id: self.def_id,
4344             inner: MacroItem(Macro {
4345                 source: format!("macro_rules! {} {{\n{}}}",
4346                                 name,
4347                                 self.matchers.iter().map(|span| {
4348                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
4349                                 }).collect::<String>()),
4350                 imported_from: self.imported_from.clean(cx),
4351             }),
4352         }
4353     }
4354 }
4355
4356 #[derive(Clone, Debug)]
4357 pub struct ProcMacro {
4358     pub kind: MacroKind,
4359     pub helpers: Vec<String>,
4360 }
4361
4362 impl Clean<Item> for doctree::ProcMacro<'_> {
4363     fn clean(&self, cx: &DocContext<'_>) -> Item {
4364         Item {
4365             name: Some(self.name.clean(cx)),
4366             attrs: self.attrs.clean(cx),
4367             source: self.whence.clean(cx),
4368             visibility: Public,
4369             stability: cx.stability(self.id).clean(cx),
4370             deprecation: cx.deprecation(self.id).clean(cx),
4371             def_id: cx.tcx.hir().local_def_id(self.id),
4372             inner: ProcMacroItem(ProcMacro {
4373                 kind: self.kind,
4374                 helpers: self.helpers.clean(cx),
4375             }),
4376         }
4377     }
4378 }
4379
4380 #[derive(Clone, Debug)]
4381 pub struct Stability {
4382     pub level: stability::StabilityLevel,
4383     pub feature: Option<String>,
4384     pub since: String,
4385     pub deprecation: Option<Deprecation>,
4386     pub unstable_reason: Option<String>,
4387     pub issue: Option<u32>,
4388 }
4389
4390 #[derive(Clone, Debug)]
4391 pub struct Deprecation {
4392     pub since: Option<String>,
4393     pub note: Option<String>,
4394 }
4395
4396 impl Clean<Stability> for attr::Stability {
4397     fn clean(&self, _: &DocContext<'_>) -> Stability {
4398         Stability {
4399             level: stability::StabilityLevel::from_attr_level(&self.level),
4400             feature: Some(self.feature.to_string()).filter(|f| !f.is_empty()),
4401             since: match self.level {
4402                 attr::Stable {ref since} => since.to_string(),
4403                 _ => String::new(),
4404             },
4405             deprecation: self.rustc_depr.as_ref().map(|d| {
4406                 Deprecation {
4407                     note: Some(d.reason.to_string()).filter(|r| !r.is_empty()),
4408                     since: Some(d.since.to_string()).filter(|d| !d.is_empty()),
4409                 }
4410             }),
4411             unstable_reason: match self.level {
4412                 attr::Unstable { reason: Some(ref reason), .. } => Some(reason.to_string()),
4413                 _ => None,
4414             },
4415             issue: match self.level {
4416                 attr::Unstable {issue, ..} => Some(issue),
4417                 _ => None,
4418             }
4419         }
4420     }
4421 }
4422
4423 impl<'a> Clean<Stability> for &'a attr::Stability {
4424     fn clean(&self, dc: &DocContext<'_>) -> Stability {
4425         (**self).clean(dc)
4426     }
4427 }
4428
4429 impl Clean<Deprecation> for attr::Deprecation {
4430     fn clean(&self, _: &DocContext<'_>) -> Deprecation {
4431         Deprecation {
4432             since: self.since.map(|s| s.to_string()).filter(|s| !s.is_empty()),
4433             note: self.note.map(|n| n.to_string()).filter(|n| !n.is_empty()),
4434         }
4435     }
4436 }
4437
4438 /// An type binding on an associated type (e.g., `A = Bar` in `Foo<A = Bar>` or
4439 /// `A: Send + Sync` in `Foo<A: Send + Sync>`).
4440 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
4441 pub struct TypeBinding {
4442     pub name: String,
4443     pub kind: TypeBindingKind,
4444 }
4445
4446 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
4447 pub enum TypeBindingKind {
4448     Equality {
4449         ty: Type,
4450     },
4451     Constraint {
4452         bounds: Vec<GenericBound>,
4453     },
4454 }
4455
4456 impl TypeBinding {
4457     pub fn ty(&self) -> &Type {
4458         match self.kind {
4459             TypeBindingKind::Equality { ref ty } => ty,
4460             _ => panic!("expected equality type binding for parenthesized generic args"),
4461         }
4462     }
4463 }
4464
4465 impl Clean<TypeBinding> for hir::TypeBinding {
4466     fn clean(&self, cx: &DocContext<'_>) -> TypeBinding {
4467         TypeBinding {
4468             name: self.ident.name.clean(cx),
4469             kind: self.kind.clean(cx),
4470         }
4471     }
4472 }
4473
4474 impl Clean<TypeBindingKind> for hir::TypeBindingKind {
4475     fn clean(&self, cx: &DocContext<'_>) -> TypeBindingKind {
4476         match *self {
4477             hir::TypeBindingKind::Equality { ref ty } =>
4478                 TypeBindingKind::Equality {
4479                     ty: ty.clean(cx),
4480                 },
4481             hir::TypeBindingKind::Constraint { ref bounds } =>
4482                 TypeBindingKind::Constraint {
4483                     bounds: bounds.into_iter().map(|b| b.clean(cx)).collect(),
4484                 },
4485         }
4486     }
4487 }
4488
4489 pub fn enter_impl_trait<F, R>(cx: &DocContext<'_>, f: F) -> R
4490 where
4491     F: FnOnce() -> R,
4492 {
4493     let old_bounds = mem::take(&mut *cx.impl_trait_bounds.borrow_mut());
4494     let r = f();
4495     assert!(cx.impl_trait_bounds.borrow().is_empty());
4496     *cx.impl_trait_bounds.borrow_mut() = old_bounds;
4497     r
4498 }
4499
4500 #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
4501 enum RegionTarget<'tcx> {
4502     Region(Region<'tcx>),
4503     RegionVid(RegionVid)
4504 }
4505
4506 #[derive(Default, Debug, Clone)]
4507 struct RegionDeps<'tcx> {
4508     larger: FxHashSet<RegionTarget<'tcx>>,
4509     smaller: FxHashSet<RegionTarget<'tcx>>
4510 }
4511
4512 #[derive(Eq, PartialEq, Hash, Debug)]
4513 enum SimpleBound {
4514     TraitBound(Vec<PathSegment>, Vec<SimpleBound>, Vec<GenericParamDef>, hir::TraitBoundModifier),
4515     Outlives(Lifetime),
4516 }
4517
4518 impl From<GenericBound> for SimpleBound {
4519     fn from(bound: GenericBound) -> Self {
4520         match bound.clone() {
4521             GenericBound::Outlives(l) => SimpleBound::Outlives(l),
4522             GenericBound::TraitBound(t, mod_) => match t.trait_ {
4523                 Type::ResolvedPath { path, param_names, .. } => {
4524                     SimpleBound::TraitBound(path.segments,
4525                                             param_names
4526                                                 .map_or_else(|| Vec::new(), |v| v.iter()
4527                                                         .map(|p| SimpleBound::from(p.clone()))
4528                                                         .collect()),
4529                                             t.generic_params,
4530                                             mod_)
4531                 }
4532                 _ => panic!("Unexpected bound {:?}", bound),
4533             }
4534         }
4535     }
4536 }