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_index::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,
 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.kind {
 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.kind {
 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.kind {
 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.kind {
 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,
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 c_variadic: bool,
2036     pub attrs: Attributes,
2037 }
2038
2039 impl FnDecl {
2040     pub fn self_type(&self) -> Option<SelfTy> {
2041         self.inputs.values.get(0).and_then(|v| v.to_self())
2042     }
2043
2044     /// Returns the sugared return type for an async function.
2045     ///
2046     /// For example, if the return type is `impl std::future::Future<Output = i32>`, this function
2047     /// will return `i32`.
2048     ///
2049     /// # Panics
2050     ///
2051     /// This function will panic if the return type does not match the expected sugaring for async
2052     /// functions.
2053     pub fn sugared_async_return_type(&self) -> FunctionRetTy {
2054         match &self.output {
2055             FunctionRetTy::Return(Type::ImplTrait(bounds)) => {
2056                 match &bounds[0] {
2057                     GenericBound::TraitBound(PolyTrait { trait_, .. }, ..) => {
2058                         let bindings = trait_.bindings().unwrap();
2059                         FunctionRetTy::Return(bindings[0].ty().clone())
2060                     }
2061                     _ => panic!("unexpected desugaring of async function"),
2062                 }
2063             }
2064             _ => panic!("unexpected desugaring of async function"),
2065         }
2066     }
2067 }
2068
2069 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2070 pub struct Arguments {
2071     pub values: Vec<Argument>,
2072 }
2073
2074 impl<'a> Clean<Arguments> for (&'a [hir::Ty], &'a [ast::Ident]) {
2075     fn clean(&self, cx: &DocContext<'_>) -> Arguments {
2076         Arguments {
2077             values: self.0.iter().enumerate().map(|(i, ty)| {
2078                 let mut name = self.1.get(i).map(|ident| ident.to_string())
2079                                             .unwrap_or(String::new());
2080                 if name.is_empty() {
2081                     name = "_".to_string();
2082                 }
2083                 Argument {
2084                     name,
2085                     type_: ty.clean(cx),
2086                 }
2087             }).collect()
2088         }
2089     }
2090 }
2091
2092 impl<'a> Clean<Arguments> for (&'a [hir::Ty], hir::BodyId) {
2093     fn clean(&self, cx: &DocContext<'_>) -> Arguments {
2094         let body = cx.tcx.hir().body(self.1);
2095
2096         Arguments {
2097             values: self.0.iter().enumerate().map(|(i, ty)| {
2098                 Argument {
2099                     name: name_from_pat(&body.params[i].pat),
2100                     type_: ty.clean(cx),
2101                 }
2102             }).collect()
2103         }
2104     }
2105 }
2106
2107 impl<'a, A: Copy> Clean<FnDecl> for (&'a hir::FnDecl, A)
2108     where (&'a [hir::Ty], A): Clean<Arguments>
2109 {
2110     fn clean(&self, cx: &DocContext<'_>) -> FnDecl {
2111         FnDecl {
2112             inputs: (&self.0.inputs[..], self.1).clean(cx),
2113             output: self.0.output.clean(cx),
2114             c_variadic: self.0.c_variadic,
2115             attrs: Attributes::default(),
2116         }
2117     }
2118 }
2119
2120 impl<'tcx> Clean<FnDecl> for (DefId, ty::PolyFnSig<'tcx>) {
2121     fn clean(&self, cx: &DocContext<'_>) -> FnDecl {
2122         let (did, sig) = *self;
2123         let mut names = if cx.tcx.hir().as_local_hir_id(did).is_some() {
2124             vec![].into_iter()
2125         } else {
2126             cx.tcx.fn_arg_names(did).into_iter()
2127         };
2128
2129         FnDecl {
2130             output: Return(sig.skip_binder().output().clean(cx)),
2131             attrs: Attributes::default(),
2132             c_variadic: sig.skip_binder().c_variadic,
2133             inputs: Arguments {
2134                 values: sig.skip_binder().inputs().iter().map(|t| {
2135                     Argument {
2136                         type_: t.clean(cx),
2137                         name: names.next().map_or(String::new(), |name| name.to_string()),
2138                     }
2139                 }).collect(),
2140             },
2141         }
2142     }
2143 }
2144
2145 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2146 pub struct Argument {
2147     pub type_: Type,
2148     pub name: String,
2149 }
2150
2151 #[derive(Clone, PartialEq, Debug)]
2152 pub enum SelfTy {
2153     SelfValue,
2154     SelfBorrowed(Option<Lifetime>, Mutability),
2155     SelfExplicit(Type),
2156 }
2157
2158 impl Argument {
2159     pub fn to_self(&self) -> Option<SelfTy> {
2160         if self.name != "self" {
2161             return None;
2162         }
2163         if self.type_.is_self_type() {
2164             return Some(SelfValue);
2165         }
2166         match self.type_ {
2167             BorrowedRef{ref lifetime, mutability, ref type_} if type_.is_self_type() => {
2168                 Some(SelfBorrowed(lifetime.clone(), mutability))
2169             }
2170             _ => Some(SelfExplicit(self.type_.clone()))
2171         }
2172     }
2173 }
2174
2175 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2176 pub enum FunctionRetTy {
2177     Return(Type),
2178     DefaultReturn,
2179 }
2180
2181 impl Clean<FunctionRetTy> for hir::FunctionRetTy {
2182     fn clean(&self, cx: &DocContext<'_>) -> FunctionRetTy {
2183         match *self {
2184             hir::Return(ref typ) => Return(typ.clean(cx)),
2185             hir::DefaultReturn(..) => DefaultReturn,
2186         }
2187     }
2188 }
2189
2190 impl GetDefId for FunctionRetTy {
2191     fn def_id(&self) -> Option<DefId> {
2192         match *self {
2193             Return(ref ty) => ty.def_id(),
2194             DefaultReturn => None,
2195         }
2196     }
2197 }
2198
2199 #[derive(Clone, Debug)]
2200 pub struct Trait {
2201     pub auto: bool,
2202     pub unsafety: hir::Unsafety,
2203     pub items: Vec<Item>,
2204     pub generics: Generics,
2205     pub bounds: Vec<GenericBound>,
2206     pub is_spotlight: bool,
2207     pub is_auto: bool,
2208 }
2209
2210 impl Clean<Item> for doctree::Trait<'_> {
2211     fn clean(&self, cx: &DocContext<'_>) -> Item {
2212         let attrs = self.attrs.clean(cx);
2213         let is_spotlight = attrs.has_doc_flag(sym::spotlight);
2214         Item {
2215             name: Some(self.name.clean(cx)),
2216             attrs,
2217             source: self.whence.clean(cx),
2218             def_id: cx.tcx.hir().local_def_id(self.id),
2219             visibility: self.vis.clean(cx),
2220             stability: cx.stability(self.id).clean(cx),
2221             deprecation: cx.deprecation(self.id).clean(cx),
2222             inner: TraitItem(Trait {
2223                 auto: self.is_auto.clean(cx),
2224                 unsafety: self.unsafety,
2225                 items: self.items.iter().map(|ti| ti.clean(cx)).collect(),
2226                 generics: self.generics.clean(cx),
2227                 bounds: self.bounds.clean(cx),
2228                 is_spotlight,
2229                 is_auto: self.is_auto.clean(cx),
2230             }),
2231         }
2232     }
2233 }
2234
2235 #[derive(Clone, Debug)]
2236 pub struct TraitAlias {
2237     pub generics: Generics,
2238     pub bounds: Vec<GenericBound>,
2239 }
2240
2241 impl Clean<Item> for doctree::TraitAlias<'_> {
2242     fn clean(&self, cx: &DocContext<'_>) -> Item {
2243         let attrs = self.attrs.clean(cx);
2244         Item {
2245             name: Some(self.name.clean(cx)),
2246             attrs,
2247             source: self.whence.clean(cx),
2248             def_id: cx.tcx.hir().local_def_id(self.id),
2249             visibility: self.vis.clean(cx),
2250             stability: cx.stability(self.id).clean(cx),
2251             deprecation: cx.deprecation(self.id).clean(cx),
2252             inner: TraitAliasItem(TraitAlias {
2253                 generics: self.generics.clean(cx),
2254                 bounds: self.bounds.clean(cx),
2255             }),
2256         }
2257     }
2258 }
2259
2260 impl Clean<bool> for hir::IsAuto {
2261     fn clean(&self, _: &DocContext<'_>) -> bool {
2262         match *self {
2263             hir::IsAuto::Yes => true,
2264             hir::IsAuto::No => false,
2265         }
2266     }
2267 }
2268
2269 impl Clean<Type> for hir::TraitRef {
2270     fn clean(&self, cx: &DocContext<'_>) -> Type {
2271         resolve_type(cx, self.path.clean(cx), self.hir_ref_id)
2272     }
2273 }
2274
2275 impl Clean<PolyTrait> for hir::PolyTraitRef {
2276     fn clean(&self, cx: &DocContext<'_>) -> PolyTrait {
2277         PolyTrait {
2278             trait_: self.trait_ref.clean(cx),
2279             generic_params: self.bound_generic_params.clean(cx)
2280         }
2281     }
2282 }
2283
2284 impl Clean<Item> for hir::TraitItem {
2285     fn clean(&self, cx: &DocContext<'_>) -> Item {
2286         let inner = match self.kind {
2287             hir::TraitItemKind::Const(ref ty, default) => {
2288                 AssocConstItem(ty.clean(cx),
2289                                     default.map(|e| print_const_expr(cx, e)))
2290             }
2291             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Provided(body)) => {
2292                 MethodItem((sig, &self.generics, body, None).clean(cx))
2293             }
2294             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Required(ref names)) => {
2295                 let (generics, decl) = enter_impl_trait(cx, || {
2296                     (self.generics.clean(cx), (&*sig.decl, &names[..]).clean(cx))
2297                 });
2298                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
2299                 TyMethodItem(TyMethod {
2300                     header: sig.header,
2301                     decl,
2302                     generics,
2303                     all_types,
2304                     ret_types,
2305                 })
2306             }
2307             hir::TraitItemKind::Type(ref bounds, ref default) => {
2308                 AssocTypeItem(bounds.clean(cx), default.clean(cx))
2309             }
2310         };
2311         let local_did = cx.tcx.hir().local_def_id(self.hir_id);
2312         Item {
2313             name: Some(self.ident.name.clean(cx)),
2314             attrs: self.attrs.clean(cx),
2315             source: self.span.clean(cx),
2316             def_id: local_did,
2317             visibility: Visibility::Inherited,
2318             stability: get_stability(cx, local_did),
2319             deprecation: get_deprecation(cx, local_did),
2320             inner,
2321         }
2322     }
2323 }
2324
2325 impl Clean<Item> for hir::ImplItem {
2326     fn clean(&self, cx: &DocContext<'_>) -> Item {
2327         let inner = match self.kind {
2328             hir::ImplItemKind::Const(ref ty, expr) => {
2329                 AssocConstItem(ty.clean(cx),
2330                                     Some(print_const_expr(cx, expr)))
2331             }
2332             hir::ImplItemKind::Method(ref sig, body) => {
2333                 MethodItem((sig, &self.generics, body, Some(self.defaultness)).clean(cx))
2334             }
2335             hir::ImplItemKind::TyAlias(ref ty) => TypedefItem(Typedef {
2336                 type_: ty.clean(cx),
2337                 generics: Generics::default(),
2338             }, true),
2339             hir::ImplItemKind::OpaqueTy(ref bounds) => OpaqueTyItem(OpaqueTy {
2340                 bounds: bounds.clean(cx),
2341                 generics: Generics::default(),
2342             }, true),
2343         };
2344         let local_did = cx.tcx.hir().local_def_id(self.hir_id);
2345         Item {
2346             name: Some(self.ident.name.clean(cx)),
2347             source: self.span.clean(cx),
2348             attrs: self.attrs.clean(cx),
2349             def_id: local_did,
2350             visibility: self.vis.clean(cx),
2351             stability: get_stability(cx, local_did),
2352             deprecation: get_deprecation(cx, local_did),
2353             inner,
2354         }
2355     }
2356 }
2357
2358 impl Clean<Item> for ty::AssocItem {
2359     fn clean(&self, cx: &DocContext<'_>) -> Item {
2360         let inner = match self.kind {
2361             ty::AssocKind::Const => {
2362                 let ty = cx.tcx.type_of(self.def_id);
2363                 let default = if self.defaultness.has_value() {
2364                     Some(inline::print_inlined_const(cx, self.def_id))
2365                 } else {
2366                     None
2367                 };
2368                 AssocConstItem(ty.clean(cx), default)
2369             }
2370             ty::AssocKind::Method => {
2371                 let generics = (cx.tcx.generics_of(self.def_id),
2372                                 &cx.tcx.explicit_predicates_of(self.def_id)).clean(cx);
2373                 let sig = cx.tcx.fn_sig(self.def_id);
2374                 let mut decl = (self.def_id, sig).clean(cx);
2375
2376                 if self.method_has_self_argument {
2377                     let self_ty = match self.container {
2378                         ty::ImplContainer(def_id) => {
2379                             cx.tcx.type_of(def_id)
2380                         }
2381                         ty::TraitContainer(_) => cx.tcx.types.self_param,
2382                     };
2383                     let self_arg_ty = *sig.input(0).skip_binder();
2384                     if self_arg_ty == self_ty {
2385                         decl.inputs.values[0].type_ = Generic(String::from("Self"));
2386                     } else if let ty::Ref(_, ty, _) = self_arg_ty.kind {
2387                         if ty == self_ty {
2388                             match decl.inputs.values[0].type_ {
2389                                 BorrowedRef{ref mut type_, ..} => {
2390                                     **type_ = Generic(String::from("Self"))
2391                                 }
2392                                 _ => unreachable!(),
2393                             }
2394                         }
2395                     }
2396                 }
2397
2398                 let provided = match self.container {
2399                     ty::ImplContainer(_) => true,
2400                     ty::TraitContainer(_) => self.defaultness.has_value()
2401                 };
2402                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
2403                 if provided {
2404                     let constness = if cx.tcx.is_min_const_fn(self.def_id) {
2405                         hir::Constness::Const
2406                     } else {
2407                         hir::Constness::NotConst
2408                     };
2409                     let asyncness = cx.tcx.asyncness(self.def_id);
2410                     let defaultness = match self.container {
2411                         ty::ImplContainer(_) => Some(self.defaultness),
2412                         ty::TraitContainer(_) => None,
2413                     };
2414                     MethodItem(Method {
2415                         generics,
2416                         decl,
2417                         header: hir::FnHeader {
2418                             unsafety: sig.unsafety(),
2419                             abi: sig.abi(),
2420                             constness,
2421                             asyncness,
2422                         },
2423                         defaultness,
2424                         all_types,
2425                         ret_types,
2426                     })
2427                 } else {
2428                     TyMethodItem(TyMethod {
2429                         generics,
2430                         decl,
2431                         header: hir::FnHeader {
2432                             unsafety: sig.unsafety(),
2433                             abi: sig.abi(),
2434                             constness: hir::Constness::NotConst,
2435                             asyncness: hir::IsAsync::NotAsync,
2436                         },
2437                         all_types,
2438                         ret_types,
2439                     })
2440                 }
2441             }
2442             ty::AssocKind::Type => {
2443                 let my_name = self.ident.name.clean(cx);
2444
2445                 if let ty::TraitContainer(did) = self.container {
2446                     // When loading a cross-crate associated type, the bounds for this type
2447                     // are actually located on the trait/impl itself, so we need to load
2448                     // all of the generics from there and then look for bounds that are
2449                     // applied to this associated type in question.
2450                     let predicates = cx.tcx.explicit_predicates_of(did);
2451                     let generics = (cx.tcx.generics_of(did), &predicates).clean(cx);
2452                     let mut bounds = generics.where_predicates.iter().filter_map(|pred| {
2453                         let (name, self_type, trait_, bounds) = match *pred {
2454                             WherePredicate::BoundPredicate {
2455                                 ty: QPath { ref name, ref self_type, ref trait_ },
2456                                 ref bounds
2457                             } => (name, self_type, trait_, bounds),
2458                             _ => return None,
2459                         };
2460                         if *name != my_name { return None }
2461                         match **trait_ {
2462                             ResolvedPath { did, .. } if did == self.container.id() => {}
2463                             _ => return None,
2464                         }
2465                         match **self_type {
2466                             Generic(ref s) if *s == "Self" => {}
2467                             _ => return None,
2468                         }
2469                         Some(bounds)
2470                     }).flat_map(|i| i.iter().cloned()).collect::<Vec<_>>();
2471                     // Our Sized/?Sized bound didn't get handled when creating the generics
2472                     // because we didn't actually get our whole set of bounds until just now
2473                     // (some of them may have come from the trait). If we do have a sized
2474                     // bound, we remove it, and if we don't then we add the `?Sized` bound
2475                     // at the end.
2476                     match bounds.iter().position(|b| b.is_sized_bound(cx)) {
2477                         Some(i) => { bounds.remove(i); }
2478                         None => bounds.push(GenericBound::maybe_sized(cx)),
2479                     }
2480
2481                     let ty = if self.defaultness.has_value() {
2482                         Some(cx.tcx.type_of(self.def_id))
2483                     } else {
2484                         None
2485                     };
2486
2487                     AssocTypeItem(bounds, ty.clean(cx))
2488                 } else {
2489                     TypedefItem(Typedef {
2490                         type_: cx.tcx.type_of(self.def_id).clean(cx),
2491                         generics: Generics {
2492                             params: Vec::new(),
2493                             where_predicates: Vec::new(),
2494                         },
2495                     }, true)
2496                 }
2497             }
2498             ty::AssocKind::OpaqueTy => unimplemented!(),
2499         };
2500
2501         let visibility = match self.container {
2502             ty::ImplContainer(_) => self.vis.clean(cx),
2503             ty::TraitContainer(_) => Inherited,
2504         };
2505
2506         Item {
2507             name: Some(self.ident.name.clean(cx)),
2508             visibility,
2509             stability: get_stability(cx, self.def_id),
2510             deprecation: get_deprecation(cx, self.def_id),
2511             def_id: self.def_id,
2512             attrs: inline::load_attrs(cx, self.def_id).clean(cx),
2513             source: cx.tcx.def_span(self.def_id).clean(cx),
2514             inner,
2515         }
2516     }
2517 }
2518
2519 /// A trait reference, which may have higher ranked lifetimes.
2520 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2521 pub struct PolyTrait {
2522     pub trait_: Type,
2523     pub generic_params: Vec<GenericParamDef>,
2524 }
2525
2526 /// A representation of a type suitable for hyperlinking purposes. Ideally, one can get the original
2527 /// type out of the AST/`TyCtxt` given one of these, if more information is needed. Most
2528 /// importantly, it does not preserve mutability or boxes.
2529 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
2530 pub enum Type {
2531     /// Structs/enums/traits (most that would be an `hir::TyKind::Path`).
2532     ResolvedPath {
2533         path: Path,
2534         param_names: Option<Vec<GenericBound>>,
2535         did: DefId,
2536         /// `true` if is a `T::Name` path for associated types.
2537         is_generic: bool,
2538     },
2539     /// For parameterized types, so the consumer of the JSON don't go
2540     /// looking for types which don't exist anywhere.
2541     Generic(String),
2542     /// Primitives are the fixed-size numeric types (plus int/usize/float), char,
2543     /// arrays, slices, and tuples.
2544     Primitive(PrimitiveType),
2545     /// `extern "ABI" fn`
2546     BareFunction(Box<BareFunctionDecl>),
2547     Tuple(Vec<Type>),
2548     Slice(Box<Type>),
2549     Array(Box<Type>, String),
2550     Never,
2551     RawPointer(Mutability, Box<Type>),
2552     BorrowedRef {
2553         lifetime: Option<Lifetime>,
2554         mutability: Mutability,
2555         type_: Box<Type>,
2556     },
2557
2558     // `<Type as Trait>::Name`
2559     QPath {
2560         name: String,
2561         self_type: Box<Type>,
2562         trait_: Box<Type>
2563     },
2564
2565     // `_`
2566     Infer,
2567
2568     // `impl TraitA + TraitB + ...`
2569     ImplTrait(Vec<GenericBound>),
2570 }
2571
2572 #[derive(Clone, PartialEq, Eq, Hash, Copy, Debug)]
2573 pub enum PrimitiveType {
2574     Isize, I8, I16, I32, I64, I128,
2575     Usize, U8, U16, U32, U64, U128,
2576     F32, F64,
2577     Char,
2578     Bool,
2579     Str,
2580     Slice,
2581     Array,
2582     Tuple,
2583     Unit,
2584     RawPointer,
2585     Reference,
2586     Fn,
2587     Never,
2588 }
2589
2590 #[derive(Clone, Copy, Debug)]
2591 pub enum TypeKind {
2592     Enum,
2593     Function,
2594     Module,
2595     Const,
2596     Static,
2597     Struct,
2598     Union,
2599     Trait,
2600     Typedef,
2601     Foreign,
2602     Macro,
2603     Attr,
2604     Derive,
2605     TraitAlias,
2606 }
2607
2608 pub trait GetDefId {
2609     fn def_id(&self) -> Option<DefId>;
2610 }
2611
2612 impl<T: GetDefId> GetDefId for Option<T> {
2613     fn def_id(&self) -> Option<DefId> {
2614         self.as_ref().and_then(|d| d.def_id())
2615     }
2616 }
2617
2618 impl Type {
2619     pub fn primitive_type(&self) -> Option<PrimitiveType> {
2620         match *self {
2621             Primitive(p) | BorrowedRef { type_: box Primitive(p), ..} => Some(p),
2622             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
2623             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
2624             Tuple(ref tys) => if tys.is_empty() {
2625                 Some(PrimitiveType::Unit)
2626             } else {
2627                 Some(PrimitiveType::Tuple)
2628             },
2629             RawPointer(..) => Some(PrimitiveType::RawPointer),
2630             BorrowedRef { type_: box Generic(..), .. } => Some(PrimitiveType::Reference),
2631             BareFunction(..) => Some(PrimitiveType::Fn),
2632             Never => Some(PrimitiveType::Never),
2633             _ => None,
2634         }
2635     }
2636
2637     pub fn is_generic(&self) -> bool {
2638         match *self {
2639             ResolvedPath { is_generic, .. } => is_generic,
2640             _ => false,
2641         }
2642     }
2643
2644     pub fn is_self_type(&self) -> bool {
2645         match *self {
2646             Generic(ref name) => name == "Self",
2647             _ => false
2648         }
2649     }
2650
2651     pub fn generics(&self) -> Option<Vec<Type>> {
2652         match *self {
2653             ResolvedPath { ref path, .. } => {
2654                 path.segments.last().and_then(|seg| {
2655                     if let GenericArgs::AngleBracketed { ref args, .. } = seg.args {
2656                         Some(args.iter().filter_map(|arg| match arg {
2657                             GenericArg::Type(ty) => Some(ty.clone()),
2658                             _ => None,
2659                         }).collect())
2660                     } else {
2661                         None
2662                     }
2663                 })
2664             }
2665             _ => None,
2666         }
2667     }
2668
2669     pub fn bindings(&self) -> Option<&[TypeBinding]> {
2670         match *self {
2671             ResolvedPath { ref path, .. } => {
2672                 path.segments.last().and_then(|seg| {
2673                     if let GenericArgs::AngleBracketed { ref bindings, .. } = seg.args {
2674                         Some(&**bindings)
2675                     } else {
2676                         None
2677                     }
2678                 })
2679             }
2680             _ => None
2681         }
2682     }
2683
2684     pub fn is_full_generic(&self) -> bool {
2685         match *self {
2686             Type::Generic(_) => true,
2687             _ => false,
2688         }
2689     }
2690
2691     pub fn projection(&self) -> Option<(&Type, DefId, &str)> {
2692         let (self_, trait_, name) = match self {
2693             QPath { ref self_type, ref trait_, ref name } => {
2694                 (self_type, trait_, name)
2695             }
2696             _ => return None,
2697         };
2698         let trait_did = match **trait_ {
2699             ResolvedPath { did, .. } => did,
2700             _ => return None,
2701         };
2702         Some((&self_, trait_did, name))
2703     }
2704
2705 }
2706
2707 impl GetDefId for Type {
2708     fn def_id(&self) -> Option<DefId> {
2709         match *self {
2710             ResolvedPath { did, .. } => Some(did),
2711             Primitive(p) => crate::html::render::cache().primitive_locations.get(&p).cloned(),
2712             BorrowedRef { type_: box Generic(..), .. } =>
2713                 Primitive(PrimitiveType::Reference).def_id(),
2714             BorrowedRef { ref type_, .. } => type_.def_id(),
2715             Tuple(ref tys) => if tys.is_empty() {
2716                 Primitive(PrimitiveType::Unit).def_id()
2717             } else {
2718                 Primitive(PrimitiveType::Tuple).def_id()
2719             },
2720             BareFunction(..) => Primitive(PrimitiveType::Fn).def_id(),
2721             Never => Primitive(PrimitiveType::Never).def_id(),
2722             Slice(..) => Primitive(PrimitiveType::Slice).def_id(),
2723             Array(..) => Primitive(PrimitiveType::Array).def_id(),
2724             RawPointer(..) => Primitive(PrimitiveType::RawPointer).def_id(),
2725             QPath { ref self_type, .. } => self_type.def_id(),
2726             _ => None,
2727         }
2728     }
2729 }
2730
2731 impl PrimitiveType {
2732     fn from_str(s: &str) -> Option<PrimitiveType> {
2733         match s {
2734             "isize" => Some(PrimitiveType::Isize),
2735             "i8" => Some(PrimitiveType::I8),
2736             "i16" => Some(PrimitiveType::I16),
2737             "i32" => Some(PrimitiveType::I32),
2738             "i64" => Some(PrimitiveType::I64),
2739             "i128" => Some(PrimitiveType::I128),
2740             "usize" => Some(PrimitiveType::Usize),
2741             "u8" => Some(PrimitiveType::U8),
2742             "u16" => Some(PrimitiveType::U16),
2743             "u32" => Some(PrimitiveType::U32),
2744             "u64" => Some(PrimitiveType::U64),
2745             "u128" => Some(PrimitiveType::U128),
2746             "bool" => Some(PrimitiveType::Bool),
2747             "char" => Some(PrimitiveType::Char),
2748             "str" => Some(PrimitiveType::Str),
2749             "f32" => Some(PrimitiveType::F32),
2750             "f64" => Some(PrimitiveType::F64),
2751             "array" => Some(PrimitiveType::Array),
2752             "slice" => Some(PrimitiveType::Slice),
2753             "tuple" => Some(PrimitiveType::Tuple),
2754             "unit" => Some(PrimitiveType::Unit),
2755             "pointer" => Some(PrimitiveType::RawPointer),
2756             "reference" => Some(PrimitiveType::Reference),
2757             "fn" => Some(PrimitiveType::Fn),
2758             "never" => Some(PrimitiveType::Never),
2759             _ => None,
2760         }
2761     }
2762
2763     pub fn as_str(&self) -> &'static str {
2764         use self::PrimitiveType::*;
2765         match *self {
2766             Isize => "isize",
2767             I8 => "i8",
2768             I16 => "i16",
2769             I32 => "i32",
2770             I64 => "i64",
2771             I128 => "i128",
2772             Usize => "usize",
2773             U8 => "u8",
2774             U16 => "u16",
2775             U32 => "u32",
2776             U64 => "u64",
2777             U128 => "u128",
2778             F32 => "f32",
2779             F64 => "f64",
2780             Str => "str",
2781             Bool => "bool",
2782             Char => "char",
2783             Array => "array",
2784             Slice => "slice",
2785             Tuple => "tuple",
2786             Unit => "unit",
2787             RawPointer => "pointer",
2788             Reference => "reference",
2789             Fn => "fn",
2790             Never => "never",
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.kind {
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, 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.kind {
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).kind);
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.kind),
3035         }
3036     }
3037 }
3038
3039 impl<'tcx> Clean<Type> for Ty<'tcx> {
3040     fn clean(&self, cx: &DocContext<'_>) -> Type {
3041         debug!("cleaning type: {:?}", self);
3042         match self.kind {
3043             ty::Never => Never,
3044             ty::Bool => Primitive(PrimitiveType::Bool),
3045             ty::Char => Primitive(PrimitiveType::Char),
3046             ty::Int(int_ty) => Primitive(int_ty.into()),
3047             ty::Uint(uint_ty) => Primitive(uint_ty.into()),
3048             ty::Float(float_ty) => Primitive(float_ty.into()),
3049             ty::Str => Primitive(PrimitiveType::Str),
3050             ty::Slice(ty) => Slice(box ty.clean(cx)),
3051             ty::Array(ty, n) => {
3052                 let mut n = cx.tcx.lift(&n).expect("array lift failed");
3053                 if let ConstValue::Unevaluated(def_id, substs) = n.val {
3054                     let param_env = cx.tcx.param_env(def_id);
3055                     let cid = GlobalId {
3056                         instance: ty::Instance::new(def_id, substs),
3057                         promoted: None
3058                     };
3059                     if let Ok(new_n) = cx.tcx.const_eval(param_env.and(cid)) {
3060                         n = new_n;
3061                     }
3062                 };
3063                 let n = print_const(cx, n);
3064                 Array(box ty.clean(cx), n)
3065             }
3066             ty::RawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
3067             ty::Ref(r, ty, mutbl) => BorrowedRef {
3068                 lifetime: r.clean(cx),
3069                 mutability: mutbl.clean(cx),
3070                 type_: box ty.clean(cx),
3071             },
3072             ty::FnDef(..) |
3073             ty::FnPtr(_) => {
3074                 let ty = cx.tcx.lift(self).expect("FnPtr lift failed");
3075                 let sig = ty.fn_sig(cx.tcx);
3076                 let local_def_id = cx.tcx.hir().local_def_id_from_node_id(ast::CRATE_NODE_ID);
3077                 BareFunction(box BareFunctionDecl {
3078                     unsafety: sig.unsafety(),
3079                     generic_params: Vec::new(),
3080                     decl: (local_def_id, sig).clean(cx),
3081                     abi: sig.abi(),
3082                 })
3083             }
3084             ty::Adt(def, substs) => {
3085                 let did = def.did;
3086                 let kind = match def.adt_kind() {
3087                     AdtKind::Struct => TypeKind::Struct,
3088                     AdtKind::Union => TypeKind::Union,
3089                     AdtKind::Enum => TypeKind::Enum,
3090                 };
3091                 inline::record_extern_fqn(cx, did, kind);
3092                 let path = external_path(cx, cx.tcx.item_name(did), None, false, vec![], substs);
3093                 ResolvedPath {
3094                     path,
3095                     param_names: None,
3096                     did,
3097                     is_generic: false,
3098                 }
3099             }
3100             ty::Foreign(did) => {
3101                 inline::record_extern_fqn(cx, did, TypeKind::Foreign);
3102                 let path = external_path(cx, cx.tcx.item_name(did),
3103                                          None, false, vec![], InternalSubsts::empty());
3104                 ResolvedPath {
3105                     path,
3106                     param_names: None,
3107                     did,
3108                     is_generic: false,
3109                 }
3110             }
3111             ty::Dynamic(ref obj, ref reg) => {
3112                 // HACK: pick the first `did` as the `did` of the trait object. Someone
3113                 // might want to implement "native" support for marker-trait-only
3114                 // trait objects.
3115                 let mut dids = obj.principal_def_id().into_iter().chain(obj.auto_traits());
3116                 let did = dids.next().unwrap_or_else(|| {
3117                     panic!("found trait object `{:?}` with no traits?", self)
3118                 });
3119                 let substs = match obj.principal() {
3120                     Some(principal) => principal.skip_binder().substs,
3121                     // marker traits have no substs.
3122                     _ => cx.tcx.intern_substs(&[])
3123                 };
3124
3125                 inline::record_extern_fqn(cx, did, TypeKind::Trait);
3126
3127                 let mut param_names = vec![];
3128                 reg.clean(cx).map(|b| param_names.push(GenericBound::Outlives(b)));
3129                 for did in dids {
3130                     let empty = cx.tcx.intern_substs(&[]);
3131                     let path = external_path(cx, cx.tcx.item_name(did),
3132                         Some(did), false, vec![], empty);
3133                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
3134                     let bound = GenericBound::TraitBound(PolyTrait {
3135                         trait_: ResolvedPath {
3136                             path,
3137                             param_names: None,
3138                             did,
3139                             is_generic: false,
3140                         },
3141                         generic_params: Vec::new(),
3142                     }, hir::TraitBoundModifier::None);
3143                     param_names.push(bound);
3144                 }
3145
3146                 let mut bindings = vec![];
3147                 for pb in obj.projection_bounds() {
3148                     bindings.push(TypeBinding {
3149                         name: cx.tcx.associated_item(pb.item_def_id()).ident.name.clean(cx),
3150                         kind: TypeBindingKind::Equality {
3151                             ty: pb.skip_binder().ty.clean(cx)
3152                         },
3153                     });
3154                 }
3155
3156                 let path = external_path(cx, cx.tcx.item_name(did), Some(did),
3157                     false, bindings, substs);
3158                 ResolvedPath {
3159                     path,
3160                     param_names: Some(param_names),
3161                     did,
3162                     is_generic: false,
3163                 }
3164             }
3165             ty::Tuple(ref t) => {
3166                 Tuple(t.iter().map(|t| t.expect_ty()).collect::<Vec<_>>().clean(cx))
3167             }
3168
3169             ty::Projection(ref data) => data.clean(cx),
3170
3171             ty::Param(ref p) => {
3172                 if let Some(bounds) = cx.impl_trait_bounds.borrow_mut().remove(&p.index.into()) {
3173                     ImplTrait(bounds)
3174                 } else {
3175                     Generic(p.name.to_string())
3176                 }
3177             }
3178
3179             ty::Opaque(def_id, substs) => {
3180                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
3181                 // by looking up the projections associated with the def_id.
3182                 let predicates_of = cx.tcx.explicit_predicates_of(def_id);
3183                 let substs = cx.tcx.lift(&substs).expect("Opaque lift failed");
3184                 let bounds = predicates_of.instantiate(cx.tcx, substs);
3185                 let mut regions = vec![];
3186                 let mut has_sized = false;
3187                 let mut bounds = bounds.predicates.iter().filter_map(|predicate| {
3188                     let trait_ref = if let Some(tr) = predicate.to_opt_poly_trait_ref() {
3189                         tr
3190                     } else if let ty::Predicate::TypeOutlives(pred) = *predicate {
3191                         // these should turn up at the end
3192                         pred.skip_binder().1.clean(cx).map(|r| {
3193                             regions.push(GenericBound::Outlives(r))
3194                         });
3195                         return None;
3196                     } else {
3197                         return None;
3198                     };
3199
3200                     if let Some(sized) = cx.tcx.lang_items().sized_trait() {
3201                         if trait_ref.def_id() == sized {
3202                             has_sized = true;
3203                             return None;
3204                         }
3205                     }
3206
3207                     let bounds = bounds.predicates.iter().filter_map(|pred|
3208                         if let ty::Predicate::Projection(proj) = *pred {
3209                             let proj = proj.skip_binder();
3210                             if proj.projection_ty.trait_ref(cx.tcx) == *trait_ref.skip_binder() {
3211                                 Some(TypeBinding {
3212                                     name: cx.tcx.associated_item(proj.projection_ty.item_def_id)
3213                                                 .ident.name.clean(cx),
3214                                     kind: TypeBindingKind::Equality {
3215                                         ty: proj.ty.clean(cx),
3216                                     },
3217                                 })
3218                             } else {
3219                                 None
3220                             }
3221                         } else {
3222                             None
3223                         }
3224                     ).collect();
3225
3226                     Some((trait_ref.skip_binder(), bounds).clean(cx))
3227                 }).collect::<Vec<_>>();
3228                 bounds.extend(regions);
3229                 if !has_sized && !bounds.is_empty() {
3230                     bounds.insert(0, GenericBound::maybe_sized(cx));
3231                 }
3232                 ImplTrait(bounds)
3233             }
3234
3235             ty::Closure(..) | ty::Generator(..) => Tuple(vec![]), // FIXME(pcwalton)
3236
3237             ty::Bound(..) => panic!("Bound"),
3238             ty::Placeholder(..) => panic!("Placeholder"),
3239             ty::UnnormalizedProjection(..) => panic!("UnnormalizedProjection"),
3240             ty::GeneratorWitness(..) => panic!("GeneratorWitness"),
3241             ty::Infer(..) => panic!("Infer"),
3242             ty::Error => panic!("Error"),
3243         }
3244     }
3245 }
3246
3247 impl<'tcx> Clean<Constant> for ty::Const<'tcx> {
3248     fn clean(&self, cx: &DocContext<'_>) -> Constant {
3249         Constant {
3250             type_: self.ty.clean(cx),
3251             expr: format!("{}", self),
3252         }
3253     }
3254 }
3255
3256 impl Clean<Item> for hir::StructField {
3257     fn clean(&self, cx: &DocContext<'_>) -> Item {
3258         let local_did = cx.tcx.hir().local_def_id(self.hir_id);
3259
3260         Item {
3261             name: Some(self.ident.name).clean(cx),
3262             attrs: self.attrs.clean(cx),
3263             source: self.span.clean(cx),
3264             visibility: self.vis.clean(cx),
3265             stability: get_stability(cx, local_did),
3266             deprecation: get_deprecation(cx, local_did),
3267             def_id: local_did,
3268             inner: StructFieldItem(self.ty.clean(cx)),
3269         }
3270     }
3271 }
3272
3273 impl Clean<Item> for ty::FieldDef {
3274     fn clean(&self, cx: &DocContext<'_>) -> Item {
3275         Item {
3276             name: Some(self.ident.name).clean(cx),
3277             attrs: cx.tcx.get_attrs(self.did).clean(cx),
3278             source: cx.tcx.def_span(self.did).clean(cx),
3279             visibility: self.vis.clean(cx),
3280             stability: get_stability(cx, self.did),
3281             deprecation: get_deprecation(cx, self.did),
3282             def_id: self.did,
3283             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
3284         }
3285     }
3286 }
3287
3288 #[derive(Clone, PartialEq, Eq, Debug)]
3289 pub enum Visibility {
3290     Public,
3291     Inherited,
3292     Crate,
3293     Restricted(DefId, Path),
3294 }
3295
3296 impl Clean<Visibility> for hir::Visibility {
3297     fn clean(&self, cx: &DocContext<'_>) -> Visibility {
3298         match self.node {
3299             hir::VisibilityKind::Public => Visibility::Public,
3300             hir::VisibilityKind::Inherited => Visibility::Inherited,
3301             hir::VisibilityKind::Crate(_) => Visibility::Crate,
3302             hir::VisibilityKind::Restricted { ref path, .. } => {
3303                 let path = path.clean(cx);
3304                 let did = register_res(cx, path.res);
3305                 Visibility::Restricted(did, path)
3306             }
3307         }
3308     }
3309 }
3310
3311 impl Clean<Visibility> for ty::Visibility {
3312     fn clean(&self, _: &DocContext<'_>) -> Visibility {
3313         if *self == ty::Visibility::Public { Public } else { Inherited }
3314     }
3315 }
3316
3317 #[derive(Clone, Debug)]
3318 pub struct Struct {
3319     pub struct_type: doctree::StructType,
3320     pub generics: Generics,
3321     pub fields: Vec<Item>,
3322     pub fields_stripped: bool,
3323 }
3324
3325 #[derive(Clone, Debug)]
3326 pub struct Union {
3327     pub struct_type: doctree::StructType,
3328     pub generics: Generics,
3329     pub fields: Vec<Item>,
3330     pub fields_stripped: bool,
3331 }
3332
3333 impl Clean<Item> for doctree::Struct<'_> {
3334     fn clean(&self, cx: &DocContext<'_>) -> Item {
3335         Item {
3336             name: Some(self.name.clean(cx)),
3337             attrs: self.attrs.clean(cx),
3338             source: self.whence.clean(cx),
3339             def_id: cx.tcx.hir().local_def_id(self.id),
3340             visibility: self.vis.clean(cx),
3341             stability: cx.stability(self.id).clean(cx),
3342             deprecation: cx.deprecation(self.id).clean(cx),
3343             inner: StructItem(Struct {
3344                 struct_type: self.struct_type,
3345                 generics: self.generics.clean(cx),
3346                 fields: self.fields.clean(cx),
3347                 fields_stripped: false,
3348             }),
3349         }
3350     }
3351 }
3352
3353 impl Clean<Item> for doctree::Union<'_> {
3354     fn clean(&self, cx: &DocContext<'_>) -> Item {
3355         Item {
3356             name: Some(self.name.clean(cx)),
3357             attrs: self.attrs.clean(cx),
3358             source: self.whence.clean(cx),
3359             def_id: cx.tcx.hir().local_def_id(self.id),
3360             visibility: self.vis.clean(cx),
3361             stability: cx.stability(self.id).clean(cx),
3362             deprecation: cx.deprecation(self.id).clean(cx),
3363             inner: UnionItem(Union {
3364                 struct_type: self.struct_type,
3365                 generics: self.generics.clean(cx),
3366                 fields: self.fields.clean(cx),
3367                 fields_stripped: false,
3368             }),
3369         }
3370     }
3371 }
3372
3373 /// This is a more limited form of the standard Struct, different in that
3374 /// it lacks the things most items have (name, id, parameterization). Found
3375 /// only as a variant in an enum.
3376 #[derive(Clone, Debug)]
3377 pub struct VariantStruct {
3378     pub struct_type: doctree::StructType,
3379     pub fields: Vec<Item>,
3380     pub fields_stripped: bool,
3381 }
3382
3383 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
3384     fn clean(&self, cx: &DocContext<'_>) -> VariantStruct {
3385         VariantStruct {
3386             struct_type: doctree::struct_type_from_def(self),
3387             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
3388             fields_stripped: false,
3389         }
3390     }
3391 }
3392
3393 #[derive(Clone, Debug)]
3394 pub struct Enum {
3395     pub variants: IndexVec<VariantIdx, Item>,
3396     pub generics: Generics,
3397     pub variants_stripped: bool,
3398 }
3399
3400 impl Clean<Item> for doctree::Enum<'_> {
3401     fn clean(&self, cx: &DocContext<'_>) -> Item {
3402         Item {
3403             name: Some(self.name.clean(cx)),
3404             attrs: self.attrs.clean(cx),
3405             source: self.whence.clean(cx),
3406             def_id: cx.tcx.hir().local_def_id(self.id),
3407             visibility: self.vis.clean(cx),
3408             stability: cx.stability(self.id).clean(cx),
3409             deprecation: cx.deprecation(self.id).clean(cx),
3410             inner: EnumItem(Enum {
3411                 variants: self.variants.iter().map(|v| v.clean(cx)).collect(),
3412                 generics: self.generics.clean(cx),
3413                 variants_stripped: false,
3414             }),
3415         }
3416     }
3417 }
3418
3419 #[derive(Clone, Debug)]
3420 pub struct Variant {
3421     pub kind: VariantKind,
3422 }
3423
3424 impl Clean<Item> for doctree::Variant<'_> {
3425     fn clean(&self, cx: &DocContext<'_>) -> Item {
3426         Item {
3427             name: Some(self.name.clean(cx)),
3428             attrs: self.attrs.clean(cx),
3429             source: self.whence.clean(cx),
3430             visibility: Inherited,
3431             stability: cx.stability(self.id).clean(cx),
3432             deprecation: cx.deprecation(self.id).clean(cx),
3433             def_id: cx.tcx.hir().local_def_id(self.id),
3434             inner: VariantItem(Variant {
3435                 kind: self.def.clean(cx),
3436             }),
3437         }
3438     }
3439 }
3440
3441 impl Clean<Item> for ty::VariantDef {
3442     fn clean(&self, cx: &DocContext<'_>) -> Item {
3443         let kind = match self.ctor_kind {
3444             CtorKind::Const => VariantKind::CLike,
3445             CtorKind::Fn => {
3446                 VariantKind::Tuple(
3447                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
3448                 )
3449             }
3450             CtorKind::Fictive => {
3451                 VariantKind::Struct(VariantStruct {
3452                     struct_type: doctree::Plain,
3453                     fields_stripped: false,
3454                     fields: self.fields.iter().map(|field| {
3455                         Item {
3456                             source: cx.tcx.def_span(field.did).clean(cx),
3457                             name: Some(field.ident.name.clean(cx)),
3458                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
3459                             visibility: field.vis.clean(cx),
3460                             def_id: field.did,
3461                             stability: get_stability(cx, field.did),
3462                             deprecation: get_deprecation(cx, field.did),
3463                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
3464                         }
3465                     }).collect()
3466                 })
3467             }
3468         };
3469         Item {
3470             name: Some(self.ident.clean(cx)),
3471             attrs: inline::load_attrs(cx, self.def_id).clean(cx),
3472             source: cx.tcx.def_span(self.def_id).clean(cx),
3473             visibility: Inherited,
3474             def_id: self.def_id,
3475             inner: VariantItem(Variant { kind }),
3476             stability: get_stability(cx, self.def_id),
3477             deprecation: get_deprecation(cx, self.def_id),
3478         }
3479     }
3480 }
3481
3482 #[derive(Clone, Debug)]
3483 pub enum VariantKind {
3484     CLike,
3485     Tuple(Vec<Type>),
3486     Struct(VariantStruct),
3487 }
3488
3489 impl Clean<VariantKind> for hir::VariantData {
3490     fn clean(&self, cx: &DocContext<'_>) -> VariantKind {
3491         match self {
3492             hir::VariantData::Struct(..) => VariantKind::Struct(self.clean(cx)),
3493             hir::VariantData::Tuple(..) =>
3494                 VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect()),
3495             hir::VariantData::Unit(..) => VariantKind::CLike,
3496         }
3497     }
3498 }
3499
3500 #[derive(Clone, Debug)]
3501 pub struct Span {
3502     pub filename: FileName,
3503     pub loline: usize,
3504     pub locol: usize,
3505     pub hiline: usize,
3506     pub hicol: usize,
3507     pub original: syntax_pos::Span,
3508 }
3509
3510 impl Span {
3511     pub fn empty() -> Span {
3512         Span {
3513             filename: FileName::Anon(0),
3514             loline: 0, locol: 0,
3515             hiline: 0, hicol: 0,
3516             original: syntax_pos::DUMMY_SP,
3517         }
3518     }
3519
3520     pub fn span(&self) -> syntax_pos::Span {
3521         self.original
3522     }
3523 }
3524
3525 impl Clean<Span> for syntax_pos::Span {
3526     fn clean(&self, cx: &DocContext<'_>) -> Span {
3527         if self.is_dummy() {
3528             return Span::empty();
3529         }
3530
3531         let cm = cx.sess().source_map();
3532         let filename = cm.span_to_filename(*self);
3533         let lo = cm.lookup_char_pos(self.lo());
3534         let hi = cm.lookup_char_pos(self.hi());
3535         Span {
3536             filename,
3537             loline: lo.line,
3538             locol: lo.col.to_usize(),
3539             hiline: hi.line,
3540             hicol: hi.col.to_usize(),
3541             original: *self,
3542         }
3543     }
3544 }
3545
3546 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
3547 pub struct Path {
3548     pub global: bool,
3549     pub res: Res,
3550     pub segments: Vec<PathSegment>,
3551 }
3552
3553 impl Path {
3554     pub fn last_name(&self) -> &str {
3555         self.segments.last().expect("segments were empty").name.as_str()
3556     }
3557 }
3558
3559 impl Clean<Path> for hir::Path {
3560     fn clean(&self, cx: &DocContext<'_>) -> Path {
3561         Path {
3562             global: self.is_global(),
3563             res: self.res,
3564             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
3565         }
3566     }
3567 }
3568
3569 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
3570 pub enum GenericArg {
3571     Lifetime(Lifetime),
3572     Type(Type),
3573     Const(Constant),
3574 }
3575
3576 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
3577 pub enum GenericArgs {
3578     AngleBracketed {
3579         args: Vec<GenericArg>,
3580         bindings: Vec<TypeBinding>,
3581     },
3582     Parenthesized {
3583         inputs: Vec<Type>,
3584         output: Option<Type>,
3585     }
3586 }
3587
3588 impl Clean<GenericArgs> for hir::GenericArgs {
3589     fn clean(&self, cx: &DocContext<'_>) -> GenericArgs {
3590         if self.parenthesized {
3591             let output = self.bindings[0].ty().clean(cx);
3592             GenericArgs::Parenthesized {
3593                 inputs: self.inputs().clean(cx),
3594                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
3595             }
3596         } else {
3597             let elide_lifetimes = self.args.iter().all(|arg| match arg {
3598                 hir::GenericArg::Lifetime(lt) => lt.is_elided(),
3599                 _ => true,
3600             });
3601             GenericArgs::AngleBracketed {
3602                 args: self.args.iter().filter_map(|arg| match arg {
3603                     hir::GenericArg::Lifetime(lt) if !elide_lifetimes => {
3604                         Some(GenericArg::Lifetime(lt.clean(cx)))
3605                     }
3606                     hir::GenericArg::Lifetime(_) => None,
3607                     hir::GenericArg::Type(ty) => Some(GenericArg::Type(ty.clean(cx))),
3608                     hir::GenericArg::Const(ct) => Some(GenericArg::Const(ct.clean(cx))),
3609                 }).collect(),
3610                 bindings: self.bindings.clean(cx),
3611             }
3612         }
3613     }
3614 }
3615
3616 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
3617 pub struct PathSegment {
3618     pub name: String,
3619     pub args: GenericArgs,
3620 }
3621
3622 impl Clean<PathSegment> for hir::PathSegment {
3623     fn clean(&self, cx: &DocContext<'_>) -> PathSegment {
3624         PathSegment {
3625             name: self.ident.name.clean(cx),
3626             args: self.generic_args().clean(cx),
3627         }
3628     }
3629 }
3630
3631 fn strip_type(ty: Type) -> Type {
3632     match ty {
3633         Type::ResolvedPath { path, param_names, did, is_generic } => {
3634             Type::ResolvedPath { path: strip_path(&path), param_names, did, is_generic }
3635         }
3636         Type::Tuple(inner_tys) => {
3637             Type::Tuple(inner_tys.iter().map(|t| strip_type(t.clone())).collect())
3638         }
3639         Type::Slice(inner_ty) => Type::Slice(Box::new(strip_type(*inner_ty))),
3640         Type::Array(inner_ty, s) => Type::Array(Box::new(strip_type(*inner_ty)), s),
3641         Type::RawPointer(m, inner_ty) => Type::RawPointer(m, Box::new(strip_type(*inner_ty))),
3642         Type::BorrowedRef { lifetime, mutability, type_ } => {
3643             Type::BorrowedRef { lifetime, mutability, type_: Box::new(strip_type(*type_)) }
3644         }
3645         Type::QPath { name, self_type, trait_ } => {
3646             Type::QPath {
3647                 name,
3648                 self_type: Box::new(strip_type(*self_type)), trait_: Box::new(strip_type(*trait_))
3649             }
3650         }
3651         _ => ty
3652     }
3653 }
3654
3655 fn strip_path(path: &Path) -> Path {
3656     let segments = path.segments.iter().map(|s| {
3657         PathSegment {
3658             name: s.name.clone(),
3659             args: GenericArgs::AngleBracketed {
3660                 args: vec![],
3661                 bindings: vec![],
3662             }
3663         }
3664     }).collect();
3665
3666     Path {
3667         global: path.global,
3668         res: path.res.clone(),
3669         segments,
3670     }
3671 }
3672
3673 fn qpath_to_string(p: &hir::QPath) -> String {
3674     let segments = match *p {
3675         hir::QPath::Resolved(_, ref path) => &path.segments,
3676         hir::QPath::TypeRelative(_, ref segment) => return segment.ident.to_string(),
3677     };
3678
3679     let mut s = String::new();
3680     for (i, seg) in segments.iter().enumerate() {
3681         if i > 0 {
3682             s.push_str("::");
3683         }
3684         if seg.ident.name != kw::PathRoot {
3685             s.push_str(&*seg.ident.as_str());
3686         }
3687     }
3688     s
3689 }
3690
3691 impl Clean<String> for Ident {
3692     #[inline]
3693     fn clean(&self, cx: &DocContext<'_>) -> String {
3694         self.name.clean(cx)
3695     }
3696 }
3697
3698 impl Clean<String> for ast::Name {
3699     #[inline]
3700     fn clean(&self, _: &DocContext<'_>) -> String {
3701         self.to_string()
3702     }
3703 }
3704
3705 impl Clean<String> for InternedString {
3706     #[inline]
3707     fn clean(&self, _: &DocContext<'_>) -> String {
3708         self.to_string()
3709     }
3710 }
3711
3712 #[derive(Clone, Debug)]
3713 pub struct Typedef {
3714     pub type_: Type,
3715     pub generics: Generics,
3716 }
3717
3718 impl Clean<Item> for doctree::Typedef<'_> {
3719     fn clean(&self, cx: &DocContext<'_>) -> Item {
3720         Item {
3721             name: Some(self.name.clean(cx)),
3722             attrs: self.attrs.clean(cx),
3723             source: self.whence.clean(cx),
3724             def_id: cx.tcx.hir().local_def_id(self.id),
3725             visibility: self.vis.clean(cx),
3726             stability: cx.stability(self.id).clean(cx),
3727             deprecation: cx.deprecation(self.id).clean(cx),
3728             inner: TypedefItem(Typedef {
3729                 type_: self.ty.clean(cx),
3730                 generics: self.gen.clean(cx),
3731             }, false),
3732         }
3733     }
3734 }
3735
3736 #[derive(Clone, Debug)]
3737 pub struct OpaqueTy {
3738     pub bounds: Vec<GenericBound>,
3739     pub generics: Generics,
3740 }
3741
3742 impl Clean<Item> for doctree::OpaqueTy<'_> {
3743     fn clean(&self, cx: &DocContext<'_>) -> Item {
3744         Item {
3745             name: Some(self.name.clean(cx)),
3746             attrs: self.attrs.clean(cx),
3747             source: self.whence.clean(cx),
3748             def_id: cx.tcx.hir().local_def_id(self.id),
3749             visibility: self.vis.clean(cx),
3750             stability: cx.stability(self.id).clean(cx),
3751             deprecation: cx.deprecation(self.id).clean(cx),
3752             inner: OpaqueTyItem(OpaqueTy {
3753                 bounds: self.opaque_ty.bounds.clean(cx),
3754                 generics: self.opaque_ty.generics.clean(cx),
3755             }, false),
3756         }
3757     }
3758 }
3759
3760 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
3761 pub struct BareFunctionDecl {
3762     pub unsafety: hir::Unsafety,
3763     pub generic_params: Vec<GenericParamDef>,
3764     pub decl: FnDecl,
3765     pub abi: Abi,
3766 }
3767
3768 impl Clean<BareFunctionDecl> for hir::BareFnTy {
3769     fn clean(&self, cx: &DocContext<'_>) -> BareFunctionDecl {
3770         let (generic_params, decl) = enter_impl_trait(cx, || {
3771             (self.generic_params.clean(cx), (&*self.decl, &self.param_names[..]).clean(cx))
3772         });
3773         BareFunctionDecl {
3774             unsafety: self.unsafety,
3775             abi: self.abi,
3776             decl,
3777             generic_params,
3778         }
3779     }
3780 }
3781
3782 #[derive(Clone, Debug)]
3783 pub struct Static {
3784     pub type_: Type,
3785     pub mutability: Mutability,
3786     /// It's useful to have the value of a static documented, but I have no
3787     /// desire to represent expressions (that'd basically be all of the AST,
3788     /// which is huge!). So, have a string.
3789     pub expr: String,
3790 }
3791
3792 impl Clean<Item> for doctree::Static<'_> {
3793     fn clean(&self, cx: &DocContext<'_>) -> Item {
3794         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
3795         Item {
3796             name: Some(self.name.clean(cx)),
3797             attrs: self.attrs.clean(cx),
3798             source: self.whence.clean(cx),
3799             def_id: cx.tcx.hir().local_def_id(self.id),
3800             visibility: self.vis.clean(cx),
3801             stability: cx.stability(self.id).clean(cx),
3802             deprecation: cx.deprecation(self.id).clean(cx),
3803             inner: StaticItem(Static {
3804                 type_: self.type_.clean(cx),
3805                 mutability: self.mutability.clean(cx),
3806                 expr: print_const_expr(cx, self.expr),
3807             }),
3808         }
3809     }
3810 }
3811
3812 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
3813 pub struct Constant {
3814     pub type_: Type,
3815     pub expr: String,
3816 }
3817
3818 impl Clean<Item> for doctree::Constant<'_> {
3819     fn clean(&self, cx: &DocContext<'_>) -> Item {
3820         Item {
3821             name: Some(self.name.clean(cx)),
3822             attrs: self.attrs.clean(cx),
3823             source: self.whence.clean(cx),
3824             def_id: cx.tcx.hir().local_def_id(self.id),
3825             visibility: self.vis.clean(cx),
3826             stability: cx.stability(self.id).clean(cx),
3827             deprecation: cx.deprecation(self.id).clean(cx),
3828             inner: ConstantItem(Constant {
3829                 type_: self.type_.clean(cx),
3830                 expr: print_const_expr(cx, self.expr),
3831             }),
3832         }
3833     }
3834 }
3835
3836 #[derive(Debug, Clone, PartialEq, Eq, Copy, Hash)]
3837 pub enum Mutability {
3838     Mutable,
3839     Immutable,
3840 }
3841
3842 impl Clean<Mutability> for hir::Mutability {
3843     fn clean(&self, _: &DocContext<'_>) -> Mutability {
3844         match self {
3845             &hir::MutMutable => Mutable,
3846             &hir::MutImmutable => Immutable,
3847         }
3848     }
3849 }
3850
3851 #[derive(Clone, PartialEq, Eq, Copy, Debug, Hash)]
3852 pub enum ImplPolarity {
3853     Positive,
3854     Negative,
3855 }
3856
3857 impl Clean<ImplPolarity> for ty::ImplPolarity {
3858     fn clean(&self, _: &DocContext<'_>) -> ImplPolarity {
3859         match self {
3860             &ty::ImplPolarity::Positive |
3861             // FIXME: do we want to do something else here?
3862             &ty::ImplPolarity::Reservation => ImplPolarity::Positive,
3863             &ty::ImplPolarity::Negative => ImplPolarity::Negative,
3864         }
3865     }
3866 }
3867
3868 #[derive(Clone, Debug)]
3869 pub struct Impl {
3870     pub unsafety: hir::Unsafety,
3871     pub generics: Generics,
3872     pub provided_trait_methods: FxHashSet<String>,
3873     pub trait_: Option<Type>,
3874     pub for_: Type,
3875     pub items: Vec<Item>,
3876     pub polarity: Option<ImplPolarity>,
3877     pub synthetic: bool,
3878     pub blanket_impl: Option<Type>,
3879 }
3880
3881 pub fn get_auto_trait_and_blanket_impls(
3882     cx: &DocContext<'tcx>,
3883     ty: Ty<'tcx>,
3884     param_env_def_id: DefId,
3885 ) -> impl Iterator<Item = Item> {
3886     AutoTraitFinder::new(cx).get_auto_trait_impls(ty, param_env_def_id).into_iter()
3887         .chain(BlanketImplFinder::new(cx).get_blanket_impls(ty, param_env_def_id))
3888 }
3889
3890 impl Clean<Vec<Item>> for doctree::Impl<'_> {
3891     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3892         let mut ret = Vec::new();
3893         let trait_ = self.trait_.clean(cx);
3894         let items = self.items.iter().map(|ii| ii.clean(cx)).collect::<Vec<_>>();
3895         let def_id = cx.tcx.hir().local_def_id(self.id);
3896
3897         // If this impl block is an implementation of the Deref trait, then we
3898         // need to try inlining the target's inherent impl blocks as well.
3899         if trait_.def_id() == cx.tcx.lang_items().deref_trait() {
3900             build_deref_target_impls(cx, &items, &mut ret);
3901         }
3902
3903         let provided = trait_.def_id().map(|did| {
3904             cx.tcx.provided_trait_methods(did)
3905                   .into_iter()
3906                   .map(|meth| meth.ident.to_string())
3907                   .collect()
3908         }).unwrap_or_default();
3909
3910         ret.push(Item {
3911             name: None,
3912             attrs: self.attrs.clean(cx),
3913             source: self.whence.clean(cx),
3914             def_id,
3915             visibility: self.vis.clean(cx),
3916             stability: cx.stability(self.id).clean(cx),
3917             deprecation: cx.deprecation(self.id).clean(cx),
3918             inner: ImplItem(Impl {
3919                 unsafety: self.unsafety,
3920                 generics: self.generics.clean(cx),
3921                 provided_trait_methods: provided,
3922                 trait_,
3923                 for_: self.for_.clean(cx),
3924                 items,
3925                 polarity: Some(cx.tcx.impl_polarity(def_id).clean(cx)),
3926                 synthetic: false,
3927                 blanket_impl: None,
3928             })
3929         });
3930         ret
3931     }
3932 }
3933
3934 fn build_deref_target_impls(cx: &DocContext<'_>,
3935                             items: &[Item],
3936                             ret: &mut Vec<Item>) {
3937     use self::PrimitiveType::*;
3938     let tcx = cx.tcx;
3939
3940     for item in items {
3941         let target = match item.inner {
3942             TypedefItem(ref t, true) => &t.type_,
3943             _ => continue,
3944         };
3945         let primitive = match *target {
3946             ResolvedPath { did, .. } if did.is_local() => continue,
3947             ResolvedPath { did, .. } => {
3948                 ret.extend(inline::build_impls(cx, did, None));
3949                 continue
3950             }
3951             _ => match target.primitive_type() {
3952                 Some(prim) => prim,
3953                 None => continue,
3954             }
3955         };
3956         let did = match primitive {
3957             Isize => tcx.lang_items().isize_impl(),
3958             I8 => tcx.lang_items().i8_impl(),
3959             I16 => tcx.lang_items().i16_impl(),
3960             I32 => tcx.lang_items().i32_impl(),
3961             I64 => tcx.lang_items().i64_impl(),
3962             I128 => tcx.lang_items().i128_impl(),
3963             Usize => tcx.lang_items().usize_impl(),
3964             U8 => tcx.lang_items().u8_impl(),
3965             U16 => tcx.lang_items().u16_impl(),
3966             U32 => tcx.lang_items().u32_impl(),
3967             U64 => tcx.lang_items().u64_impl(),
3968             U128 => tcx.lang_items().u128_impl(),
3969             F32 => tcx.lang_items().f32_impl(),
3970             F64 => tcx.lang_items().f64_impl(),
3971             Char => tcx.lang_items().char_impl(),
3972             Bool => tcx.lang_items().bool_impl(),
3973             Str => tcx.lang_items().str_impl(),
3974             Slice => tcx.lang_items().slice_impl(),
3975             Array => tcx.lang_items().slice_impl(),
3976             Tuple => None,
3977             Unit => None,
3978             RawPointer => tcx.lang_items().const_ptr_impl(),
3979             Reference => None,
3980             Fn => None,
3981             Never => None,
3982         };
3983         if let Some(did) = did {
3984             if !did.is_local() {
3985                 inline::build_impl(cx, did, None, ret);
3986             }
3987         }
3988     }
3989 }
3990
3991 impl Clean<Vec<Item>> for doctree::ExternCrate<'_> {
3992     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3993
3994         let please_inline = self.vis.node.is_pub() && self.attrs.iter().any(|a| {
3995             a.check_name(sym::doc) && match a.meta_item_list() {
3996                 Some(l) => attr::list_contains_name(&l, sym::inline),
3997                 None => false,
3998             }
3999         });
4000
4001         if please_inline {
4002             let mut visited = FxHashSet::default();
4003
4004             let res = Res::Def(
4005                 DefKind::Mod,
4006                 DefId {
4007                     krate: self.cnum,
4008                     index: CRATE_DEF_INDEX,
4009                 },
4010             );
4011
4012             if let Some(items) = inline::try_inline(
4013                 cx, res, self.name,
4014                 Some(rustc::ty::Attributes::Borrowed(self.attrs)),
4015                 &mut visited
4016             ) {
4017                 return items;
4018             }
4019         }
4020
4021         vec![Item {
4022             name: None,
4023             attrs: self.attrs.clean(cx),
4024             source: self.whence.clean(cx),
4025             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
4026             visibility: self.vis.clean(cx),
4027             stability: None,
4028             deprecation: None,
4029             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
4030         }]
4031     }
4032 }
4033
4034 impl Clean<Vec<Item>> for doctree::Import<'_> {
4035     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
4036         // We consider inlining the documentation of `pub use` statements, but we
4037         // forcefully don't inline if this is not public or if the
4038         // #[doc(no_inline)] attribute is present.
4039         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
4040         let mut denied = !self.vis.node.is_pub() || self.attrs.iter().any(|a| {
4041             a.check_name(sym::doc) && match a.meta_item_list() {
4042                 Some(l) => attr::list_contains_name(&l, sym::no_inline) ||
4043                            attr::list_contains_name(&l, sym::hidden),
4044                 None => false,
4045             }
4046         });
4047         // Also check whether imports were asked to be inlined, in case we're trying to re-export a
4048         // crate in Rust 2018+
4049         let please_inline = self.attrs.lists(sym::doc).has_word(sym::inline);
4050         let path = self.path.clean(cx);
4051         let inner = if self.glob {
4052             if !denied {
4053                 let mut visited = FxHashSet::default();
4054                 if let Some(items) = inline::try_inline_glob(cx, path.res, &mut visited) {
4055                     return items;
4056                 }
4057             }
4058
4059             Import::Glob(resolve_use_source(cx, path))
4060         } else {
4061             let name = self.name;
4062             if !please_inline {
4063                 match path.res {
4064                     Res::Def(DefKind::Mod, did) => {
4065                         if !did.is_local() && did.index == CRATE_DEF_INDEX {
4066                             // if we're `pub use`ing an extern crate root, don't inline it unless we
4067                             // were specifically asked for it
4068                             denied = true;
4069                         }
4070                     }
4071                     _ => {}
4072                 }
4073             }
4074             if !denied {
4075                 let mut visited = FxHashSet::default();
4076                 if let Some(items) = inline::try_inline(
4077                     cx, path.res, name,
4078                     Some(rustc::ty::Attributes::Borrowed(self.attrs)),
4079                     &mut visited
4080                 ) {
4081                     return items;
4082                 }
4083             }
4084             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
4085         };
4086
4087         vec![Item {
4088             name: None,
4089             attrs: self.attrs.clean(cx),
4090             source: self.whence.clean(cx),
4091             def_id: cx.tcx.hir().local_def_id_from_node_id(ast::CRATE_NODE_ID),
4092             visibility: self.vis.clean(cx),
4093             stability: None,
4094             deprecation: None,
4095             inner: ImportItem(inner)
4096         }]
4097     }
4098 }
4099
4100 #[derive(Clone, Debug)]
4101 pub enum Import {
4102     // use source as str;
4103     Simple(String, ImportSource),
4104     // use source::*;
4105     Glob(ImportSource)
4106 }
4107
4108 #[derive(Clone, Debug)]
4109 pub struct ImportSource {
4110     pub path: Path,
4111     pub did: Option<DefId>,
4112 }
4113
4114 impl Clean<Item> for doctree::ForeignItem<'_> {
4115     fn clean(&self, cx: &DocContext<'_>) -> Item {
4116         let inner = match self.kind {
4117             hir::ForeignItemKind::Fn(ref decl, ref names, ref generics) => {
4118                 let abi = cx.tcx.hir().get_foreign_abi(self.id);
4119                 let (generics, decl) = enter_impl_trait(cx, || {
4120                     (generics.clean(cx), (&**decl, &names[..]).clean(cx))
4121                 });
4122                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
4123                 ForeignFunctionItem(Function {
4124                     decl,
4125                     generics,
4126                     header: hir::FnHeader {
4127                         unsafety: hir::Unsafety::Unsafe,
4128                         abi,
4129                         constness: hir::Constness::NotConst,
4130                         asyncness: hir::IsAsync::NotAsync,
4131                     },
4132                     all_types,
4133                     ret_types,
4134                 })
4135             }
4136             hir::ForeignItemKind::Static(ref ty, mutbl) => {
4137                 ForeignStaticItem(Static {
4138                     type_: ty.clean(cx),
4139                     mutability: mutbl.clean(cx),
4140                     expr: String::new(),
4141                 })
4142             }
4143             hir::ForeignItemKind::Type => {
4144                 ForeignTypeItem
4145             }
4146         };
4147
4148         Item {
4149             name: Some(self.name.clean(cx)),
4150             attrs: self.attrs.clean(cx),
4151             source: self.whence.clean(cx),
4152             def_id: cx.tcx.hir().local_def_id(self.id),
4153             visibility: self.vis.clean(cx),
4154             stability: cx.stability(self.id).clean(cx),
4155             deprecation: cx.deprecation(self.id).clean(cx),
4156             inner,
4157         }
4158     }
4159 }
4160
4161 // Utilities
4162
4163 pub trait ToSource {
4164     fn to_src(&self, cx: &DocContext<'_>) -> String;
4165 }
4166
4167 impl ToSource for syntax_pos::Span {
4168     fn to_src(&self, cx: &DocContext<'_>) -> String {
4169         debug!("converting span {:?} to snippet", self.clean(cx));
4170         let sn = match cx.sess().source_map().span_to_snippet(*self) {
4171             Ok(x) => x,
4172             Err(_) => String::new()
4173         };
4174         debug!("got snippet {}", sn);
4175         sn
4176     }
4177 }
4178
4179 fn name_from_pat(p: &hir::Pat) -> String {
4180     use rustc::hir::*;
4181     debug!("trying to get a name from pattern: {:?}", p);
4182
4183     match p.kind {
4184         PatKind::Wild => "_".to_string(),
4185         PatKind::Binding(_, _, ident, _) => ident.to_string(),
4186         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
4187         PatKind::Struct(ref name, ref fields, etc) => {
4188             format!("{} {{ {}{} }}", qpath_to_string(name),
4189                 fields.iter().map(|fp| format!("{}: {}", fp.ident, name_from_pat(&fp.pat)))
4190                              .collect::<Vec<String>>().join(", "),
4191                 if etc { ", .." } else { "" }
4192             )
4193         }
4194         PatKind::Or(ref pats) => {
4195             pats.iter().map(|p| name_from_pat(&**p)).collect::<Vec<String>>().join(" | ")
4196         }
4197         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
4198                                             .collect::<Vec<String>>().join(", ")),
4199         PatKind::Box(ref p) => name_from_pat(&**p),
4200         PatKind::Ref(ref p, _) => name_from_pat(&**p),
4201         PatKind::Lit(..) => {
4202             warn!("tried to get argument name from PatKind::Lit, \
4203                   which is silly in function arguments");
4204             "()".to_string()
4205         },
4206         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
4207                               which is not allowed in function arguments"),
4208         PatKind::Slice(ref begin, ref mid, ref end) => {
4209             let begin = begin.iter().map(|p| name_from_pat(&**p));
4210             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
4211             let end = end.iter().map(|p| name_from_pat(&**p));
4212             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
4213         },
4214     }
4215 }
4216
4217 fn print_const(cx: &DocContext<'_>, n: &ty::Const<'_>) -> String {
4218     match n.val {
4219         ConstValue::Unevaluated(def_id, _) => {
4220             if let Some(hir_id) = cx.tcx.hir().as_local_hir_id(def_id) {
4221                 print_const_expr(cx, cx.tcx.hir().body_owned_by(hir_id))
4222             } else {
4223                 inline::print_inlined_const(cx, def_id)
4224             }
4225         },
4226         _ => {
4227             let mut s = n.to_string();
4228             // array lengths are obviously usize
4229             if s.ends_with("usize") {
4230                 let n = s.len() - "usize".len();
4231                 s.truncate(n);
4232                 if s.ends_with(": ") {
4233                     let n = s.len() - ": ".len();
4234                     s.truncate(n);
4235                 }
4236             }
4237             s
4238         },
4239     }
4240 }
4241
4242 fn print_const_expr(cx: &DocContext<'_>, body: hir::BodyId) -> String {
4243     cx.tcx.hir().hir_to_pretty_string(body.hir_id)
4244 }
4245
4246 /// Given a type Path, resolve it to a Type using the TyCtxt
4247 fn resolve_type(cx: &DocContext<'_>,
4248                 path: Path,
4249                 id: hir::HirId) -> Type {
4250     if id == hir::DUMMY_HIR_ID {
4251         debug!("resolve_type({:?})", path);
4252     } else {
4253         debug!("resolve_type({:?},{:?})", path, id);
4254     }
4255
4256     let is_generic = match path.res {
4257         Res::PrimTy(p) => match p {
4258             hir::Str => return Primitive(PrimitiveType::Str),
4259             hir::Bool => return Primitive(PrimitiveType::Bool),
4260             hir::Char => return Primitive(PrimitiveType::Char),
4261             hir::Int(int_ty) => return Primitive(int_ty.into()),
4262             hir::Uint(uint_ty) => return Primitive(uint_ty.into()),
4263             hir::Float(float_ty) => return Primitive(float_ty.into()),
4264         },
4265         Res::SelfTy(..) if path.segments.len() == 1 => {
4266             return Generic(kw::SelfUpper.to_string());
4267         }
4268         Res::Def(DefKind::TyParam, _) if path.segments.len() == 1 => {
4269             return Generic(format!("{:#}", path.print()));
4270         }
4271         Res::SelfTy(..)
4272         | Res::Def(DefKind::TyParam, _)
4273         | Res::Def(DefKind::AssocTy, _) => true,
4274         _ => false,
4275     };
4276     let did = register_res(&*cx, path.res);
4277     ResolvedPath { path, param_names: None, did, is_generic }
4278 }
4279
4280 pub fn register_res(cx: &DocContext<'_>, res: Res) -> DefId {
4281     debug!("register_res({:?})", res);
4282
4283     let (did, kind) = match res {
4284         Res::Def(DefKind::Fn, i) => (i, TypeKind::Function),
4285         Res::Def(DefKind::TyAlias, i) => (i, TypeKind::Typedef),
4286         Res::Def(DefKind::Enum, i) => (i, TypeKind::Enum),
4287         Res::Def(DefKind::Trait, i) => (i, TypeKind::Trait),
4288         Res::Def(DefKind::Struct, i) => (i, TypeKind::Struct),
4289         Res::Def(DefKind::Union, i) => (i, TypeKind::Union),
4290         Res::Def(DefKind::Mod, i) => (i, TypeKind::Module),
4291         Res::Def(DefKind::ForeignTy, i) => (i, TypeKind::Foreign),
4292         Res::Def(DefKind::Const, i) => (i, TypeKind::Const),
4293         Res::Def(DefKind::Static, i) => (i, TypeKind::Static),
4294         Res::Def(DefKind::Variant, i) => (cx.tcx.parent(i).expect("cannot get parent def id"),
4295                             TypeKind::Enum),
4296         Res::Def(DefKind::Macro(mac_kind), i) => match mac_kind {
4297             MacroKind::Bang => (i, TypeKind::Macro),
4298             MacroKind::Attr => (i, TypeKind::Attr),
4299             MacroKind::Derive => (i, TypeKind::Derive),
4300         },
4301         Res::Def(DefKind::TraitAlias, i) => (i, TypeKind::TraitAlias),
4302         Res::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
4303         Res::SelfTy(_, Some(impl_def_id)) => return impl_def_id,
4304         _ => return res.def_id()
4305     };
4306     if did.is_local() { return did }
4307     inline::record_extern_fqn(cx, did, kind);
4308     if let TypeKind::Trait = kind {
4309         inline::record_extern_trait(cx, did);
4310     }
4311     did
4312 }
4313
4314 fn resolve_use_source(cx: &DocContext<'_>, path: Path) -> ImportSource {
4315     ImportSource {
4316         did: if path.res.opt_def_id().is_none() {
4317             None
4318         } else {
4319             Some(register_res(cx, path.res))
4320         },
4321         path,
4322     }
4323 }
4324
4325 #[derive(Clone, Debug)]
4326 pub struct Macro {
4327     pub source: String,
4328     pub imported_from: Option<String>,
4329 }
4330
4331 impl Clean<Item> for doctree::Macro<'_> {
4332     fn clean(&self, cx: &DocContext<'_>) -> Item {
4333         let name = self.name.clean(cx);
4334         Item {
4335             name: Some(name.clone()),
4336             attrs: self.attrs.clean(cx),
4337             source: self.whence.clean(cx),
4338             visibility: Public,
4339             stability: cx.stability(self.hid).clean(cx),
4340             deprecation: cx.deprecation(self.hid).clean(cx),
4341             def_id: self.def_id,
4342             inner: MacroItem(Macro {
4343                 source: format!("macro_rules! {} {{\n{}}}",
4344                                 name,
4345                                 self.matchers.iter().map(|span| {
4346                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
4347                                 }).collect::<String>()),
4348                 imported_from: self.imported_from.clean(cx),
4349             }),
4350         }
4351     }
4352 }
4353
4354 #[derive(Clone, Debug)]
4355 pub struct ProcMacro {
4356     pub kind: MacroKind,
4357     pub helpers: Vec<String>,
4358 }
4359
4360 impl Clean<Item> for doctree::ProcMacro<'_> {
4361     fn clean(&self, cx: &DocContext<'_>) -> Item {
4362         Item {
4363             name: Some(self.name.clean(cx)),
4364             attrs: self.attrs.clean(cx),
4365             source: self.whence.clean(cx),
4366             visibility: Public,
4367             stability: cx.stability(self.id).clean(cx),
4368             deprecation: cx.deprecation(self.id).clean(cx),
4369             def_id: cx.tcx.hir().local_def_id(self.id),
4370             inner: ProcMacroItem(ProcMacro {
4371                 kind: self.kind,
4372                 helpers: self.helpers.clean(cx),
4373             }),
4374         }
4375     }
4376 }
4377
4378 #[derive(Clone, Debug)]
4379 pub struct Stability {
4380     pub level: stability::StabilityLevel,
4381     pub feature: Option<String>,
4382     pub since: String,
4383     pub deprecation: Option<Deprecation>,
4384     pub unstable_reason: Option<String>,
4385     pub issue: Option<u32>,
4386 }
4387
4388 #[derive(Clone, Debug)]
4389 pub struct Deprecation {
4390     pub since: Option<String>,
4391     pub note: Option<String>,
4392 }
4393
4394 impl Clean<Stability> for attr::Stability {
4395     fn clean(&self, _: &DocContext<'_>) -> Stability {
4396         Stability {
4397             level: stability::StabilityLevel::from_attr_level(&self.level),
4398             feature: Some(self.feature.to_string()).filter(|f| !f.is_empty()),
4399             since: match self.level {
4400                 attr::Stable {ref since} => since.to_string(),
4401                 _ => String::new(),
4402             },
4403             deprecation: self.rustc_depr.as_ref().map(|d| {
4404                 Deprecation {
4405                     note: Some(d.reason.to_string()).filter(|r| !r.is_empty()),
4406                     since: Some(d.since.to_string()).filter(|d| !d.is_empty()),
4407                 }
4408             }),
4409             unstable_reason: match self.level {
4410                 attr::Unstable { reason: Some(ref reason), .. } => Some(reason.to_string()),
4411                 _ => None,
4412             },
4413             issue: match self.level {
4414                 attr::Unstable {issue, ..} => Some(issue),
4415                 _ => None,
4416             }
4417         }
4418     }
4419 }
4420
4421 impl<'a> Clean<Stability> for &'a attr::Stability {
4422     fn clean(&self, dc: &DocContext<'_>) -> Stability {
4423         (**self).clean(dc)
4424     }
4425 }
4426
4427 impl Clean<Deprecation> for attr::Deprecation {
4428     fn clean(&self, _: &DocContext<'_>) -> Deprecation {
4429         Deprecation {
4430             since: self.since.map(|s| s.to_string()).filter(|s| !s.is_empty()),
4431             note: self.note.map(|n| n.to_string()).filter(|n| !n.is_empty()),
4432         }
4433     }
4434 }
4435
4436 /// An type binding on an associated type (e.g., `A = Bar` in `Foo<A = Bar>` or
4437 /// `A: Send + Sync` in `Foo<A: Send + Sync>`).
4438 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
4439 pub struct TypeBinding {
4440     pub name: String,
4441     pub kind: TypeBindingKind,
4442 }
4443
4444 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
4445 pub enum TypeBindingKind {
4446     Equality {
4447         ty: Type,
4448     },
4449     Constraint {
4450         bounds: Vec<GenericBound>,
4451     },
4452 }
4453
4454 impl TypeBinding {
4455     pub fn ty(&self) -> &Type {
4456         match self.kind {
4457             TypeBindingKind::Equality { ref ty } => ty,
4458             _ => panic!("expected equality type binding for parenthesized generic args"),
4459         }
4460     }
4461 }
4462
4463 impl Clean<TypeBinding> for hir::TypeBinding {
4464     fn clean(&self, cx: &DocContext<'_>) -> TypeBinding {
4465         TypeBinding {
4466             name: self.ident.name.clean(cx),
4467             kind: self.kind.clean(cx),
4468         }
4469     }
4470 }
4471
4472 impl Clean<TypeBindingKind> for hir::TypeBindingKind {
4473     fn clean(&self, cx: &DocContext<'_>) -> TypeBindingKind {
4474         match *self {
4475             hir::TypeBindingKind::Equality { ref ty } =>
4476                 TypeBindingKind::Equality {
4477                     ty: ty.clean(cx),
4478                 },
4479             hir::TypeBindingKind::Constraint { ref bounds } =>
4480                 TypeBindingKind::Constraint {
4481                     bounds: bounds.into_iter().map(|b| b.clean(cx)).collect(),
4482                 },
4483         }
4484     }
4485 }
4486
4487 pub fn enter_impl_trait<F, R>(cx: &DocContext<'_>, f: F) -> R
4488 where
4489     F: FnOnce() -> R,
4490 {
4491     let old_bounds = mem::take(&mut *cx.impl_trait_bounds.borrow_mut());
4492     let r = f();
4493     assert!(cx.impl_trait_bounds.borrow().is_empty());
4494     *cx.impl_trait_bounds.borrow_mut() = old_bounds;
4495     r
4496 }
4497
4498 #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
4499 enum RegionTarget<'tcx> {
4500     Region(Region<'tcx>),
4501     RegionVid(RegionVid)
4502 }
4503
4504 #[derive(Default, Debug, Clone)]
4505 struct RegionDeps<'tcx> {
4506     larger: FxHashSet<RegionTarget<'tcx>>,
4507     smaller: FxHashSet<RegionTarget<'tcx>>
4508 }
4509
4510 #[derive(Eq, PartialEq, Hash, Debug)]
4511 enum SimpleBound {
4512     TraitBound(Vec<PathSegment>, Vec<SimpleBound>, Vec<GenericParamDef>, hir::TraitBoundModifier),
4513     Outlives(Lifetime),
4514 }
4515
4516 impl From<GenericBound> for SimpleBound {
4517     fn from(bound: GenericBound) -> Self {
4518         match bound.clone() {
4519             GenericBound::Outlives(l) => SimpleBound::Outlives(l),
4520             GenericBound::TraitBound(t, mod_) => match t.trait_ {
4521                 Type::ResolvedPath { path, param_names, .. } => {
4522                     SimpleBound::TraitBound(path.segments,
4523                                             param_names
4524                                                 .map_or_else(|| Vec::new(), |v| v.iter()
4525                                                         .map(|p| SimpleBound::from(p.clone()))
4526                                                         .collect()),
4527                                             t.generic_params,
4528                                             mod_)
4529                 }
4530                 _ => panic!("Unexpected bound {:?}", bound),
4531             }
4532         }
4533     }
4534 }