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