src/librustdoc/clean/mod.rs

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