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::{InternalSubsts, SubstsRef};
  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: SubstsRef<'_>) -> 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: SubstsRef<'_>) -> 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 InternalSubsts<'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.hir_id != hir::DUMMY_HIR_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_from_hir_id(self.hir_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_from_hir_id(self.hir_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 attrs: Attributes,
1756 }
1757
1758 impl FnDecl {
1759     pub fn self_type(&self) -> Option<SelfTy> {
1760         self.inputs.values.get(0).and_then(|v| v.to_self())
1761     }
1762
1763     /// Returns the sugared return type for an async function.
1764     ///
1765     /// For example, if the return type is `impl std::future::Future<Output = i32>`, this function
1766     /// will return `i32`.
1767     ///
1768     /// # Panics
1769     ///
1770     /// This function will panic if the return type does not match the expected sugaring for async
1771     /// functions.
1772     pub fn sugared_async_return_type(&self) -> FunctionRetTy {
1773         match &self.output {
1774             FunctionRetTy::Return(Type::ImplTrait(bounds)) => {
1775                 match &bounds[0] {
1776                     GenericBound::TraitBound(PolyTrait { trait_, .. }, ..) => {
1777                         let bindings = trait_.bindings().unwrap();
1778                         FunctionRetTy::Return(bindings[0].ty.clone())
1779                     }
1780                     _ => panic!("unexpected desugaring of async function"),
1781                 }
1782             }
1783             _ => panic!("unexpected desugaring of async function"),
1784         }
1785     }
1786 }
1787
1788 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1789 pub struct Arguments {
1790     pub values: Vec<Argument>,
1791 }
1792
1793 impl<'a> Clean<Arguments> for (&'a [hir::Ty], &'a [ast::Ident]) {
1794     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Arguments {
1795         Arguments {
1796             values: self.0.iter().enumerate().map(|(i, ty)| {
1797                 let mut name = self.1.get(i).map(|ident| ident.to_string())
1798                                             .unwrap_or(String::new());
1799                 if name.is_empty() {
1800                     name = "_".to_string();
1801                 }
1802                 Argument {
1803                     name,
1804                     type_: ty.clean(cx),
1805                 }
1806             }).collect()
1807         }
1808     }
1809 }
1810
1811 impl<'a> Clean<Arguments> for (&'a [hir::Ty], hir::BodyId) {
1812     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Arguments {
1813         let body = cx.tcx.hir().body(self.1);
1814
1815         Arguments {
1816             values: self.0.iter().enumerate().map(|(i, ty)| {
1817                 Argument {
1818                     name: name_from_pat(&body.arguments[i].pat),
1819                     type_: ty.clean(cx),
1820                 }
1821             }).collect()
1822         }
1823     }
1824 }
1825
1826 impl<'a, A: Copy> Clean<FnDecl> for (&'a hir::FnDecl, A)
1827     where (&'a [hir::Ty], A): Clean<Arguments>
1828 {
1829     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> FnDecl {
1830         FnDecl {
1831             inputs: (&self.0.inputs[..], self.1).clean(cx),
1832             output: self.0.output.clean(cx),
1833             attrs: Attributes::default()
1834         }
1835     }
1836 }
1837
1838 impl<'a, 'tcx> Clean<FnDecl> for (DefId, ty::PolyFnSig<'tcx>) {
1839     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> FnDecl {
1840         let (did, sig) = *self;
1841         let mut names = if cx.tcx.hir().as_local_node_id(did).is_some() {
1842             vec![].into_iter()
1843         } else {
1844             cx.tcx.fn_arg_names(did).into_iter()
1845         };
1846
1847         FnDecl {
1848             output: Return(sig.skip_binder().output().clean(cx)),
1849             attrs: Attributes::default(),
1850             inputs: Arguments {
1851                 values: sig.skip_binder().inputs().iter().map(|t| {
1852                     Argument {
1853                         type_: t.clean(cx),
1854                         name: names.next().map_or(String::new(), |name| name.to_string()),
1855                     }
1856                 }).collect(),
1857             },
1858         }
1859     }
1860 }
1861
1862 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1863 pub struct Argument {
1864     pub type_: Type,
1865     pub name: String,
1866 }
1867
1868 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1869 pub enum SelfTy {
1870     SelfValue,
1871     SelfBorrowed(Option<Lifetime>, Mutability),
1872     SelfExplicit(Type),
1873 }
1874
1875 impl Argument {
1876     pub fn to_self(&self) -> Option<SelfTy> {
1877         if self.name != "self" {
1878             return None;
1879         }
1880         if self.type_.is_self_type() {
1881             return Some(SelfValue);
1882         }
1883         match self.type_ {
1884             BorrowedRef{ref lifetime, mutability, ref type_} if type_.is_self_type() => {
1885                 Some(SelfBorrowed(lifetime.clone(), mutability))
1886             }
1887             _ => Some(SelfExplicit(self.type_.clone()))
1888         }
1889     }
1890 }
1891
1892 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1893 pub enum FunctionRetTy {
1894     Return(Type),
1895     DefaultReturn,
1896 }
1897
1898 impl Clean<FunctionRetTy> for hir::FunctionRetTy {
1899     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> FunctionRetTy {
1900         match *self {
1901             hir::Return(ref typ) => Return(typ.clean(cx)),
1902             hir::DefaultReturn(..) => DefaultReturn,
1903         }
1904     }
1905 }
1906
1907 impl GetDefId for FunctionRetTy {
1908     fn def_id(&self) -> Option<DefId> {
1909         match *self {
1910             Return(ref ty) => ty.def_id(),
1911             DefaultReturn => None,
1912         }
1913     }
1914 }
1915
1916 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1917 pub struct Trait {
1918     pub auto: bool,
1919     pub unsafety: hir::Unsafety,
1920     pub items: Vec<Item>,
1921     pub generics: Generics,
1922     pub bounds: Vec<GenericBound>,
1923     pub is_spotlight: bool,
1924     pub is_auto: bool,
1925 }
1926
1927 impl Clean<Item> for doctree::Trait {
1928     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
1929         let attrs = self.attrs.clean(cx);
1930         let is_spotlight = attrs.has_doc_flag("spotlight");
1931         Item {
1932             name: Some(self.name.clean(cx)),
1933             attrs: attrs,
1934             source: self.whence.clean(cx),
1935             def_id: cx.tcx.hir().local_def_id(self.id),
1936             visibility: self.vis.clean(cx),
1937             stability: self.stab.clean(cx),
1938             deprecation: self.depr.clean(cx),
1939             inner: TraitItem(Trait {
1940                 auto: self.is_auto.clean(cx),
1941                 unsafety: self.unsafety,
1942                 items: self.items.clean(cx),
1943                 generics: self.generics.clean(cx),
1944                 bounds: self.bounds.clean(cx),
1945                 is_spotlight,
1946                 is_auto: self.is_auto.clean(cx),
1947             }),
1948         }
1949     }
1950 }
1951
1952 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1953 pub struct TraitAlias {
1954     pub generics: Generics,
1955     pub bounds: Vec<GenericBound>,
1956 }
1957
1958 impl Clean<Item> for doctree::TraitAlias {
1959     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
1960         let attrs = self.attrs.clean(cx);
1961         Item {
1962             name: Some(self.name.clean(cx)),
1963             attrs,
1964             source: self.whence.clean(cx),
1965             def_id: cx.tcx.hir().local_def_id(self.id),
1966             visibility: self.vis.clean(cx),
1967             stability: self.stab.clean(cx),
1968             deprecation: self.depr.clean(cx),
1969             inner: TraitAliasItem(TraitAlias {
1970                 generics: self.generics.clean(cx),
1971                 bounds: self.bounds.clean(cx),
1972             }),
1973         }
1974     }
1975 }
1976
1977 impl Clean<bool> for hir::IsAuto {
1978     fn clean(&self, _: &DocContext<'_, '_, '_>) -> bool {
1979         match *self {
1980             hir::IsAuto::Yes => true,
1981             hir::IsAuto::No => false,
1982         }
1983     }
1984 }
1985
1986 impl Clean<Type> for hir::TraitRef {
1987     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Type {
1988         resolve_type(cx, self.path.clean(cx), self.hir_ref_id)
1989     }
1990 }
1991
1992 impl Clean<PolyTrait> for hir::PolyTraitRef {
1993     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> PolyTrait {
1994         PolyTrait {
1995             trait_: self.trait_ref.clean(cx),
1996             generic_params: self.bound_generic_params.clean(cx)
1997         }
1998     }
1999 }
2000
2001 impl Clean<Item> for hir::TraitItem {
2002     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
2003         let inner = match self.node {
2004             hir::TraitItemKind::Const(ref ty, default) => {
2005                 AssociatedConstItem(ty.clean(cx),
2006                                     default.map(|e| print_const_expr(cx, e)))
2007             }
2008             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Provided(body)) => {
2009                 MethodItem((sig, &self.generics, body).clean(cx))
2010             }
2011             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Required(ref names)) => {
2012                 let (generics, decl) = enter_impl_trait(cx, || {
2013                     (self.generics.clean(cx), (&*sig.decl, &names[..]).clean(cx))
2014                 });
2015                 TyMethodItem(TyMethod {
2016                     header: sig.header,
2017                     decl,
2018                     generics,
2019                 })
2020             }
2021             hir::TraitItemKind::Type(ref bounds, ref default) => {
2022                 AssociatedTypeItem(bounds.clean(cx), default.clean(cx))
2023             }
2024         };
2025         let local_did = cx.tcx.hir().local_def_id_from_hir_id(self.hir_id);
2026         Item {
2027             name: Some(self.ident.name.clean(cx)),
2028             attrs: self.attrs.clean(cx),
2029             source: self.span.clean(cx),
2030             def_id: local_did,
2031             visibility: None,
2032             stability: get_stability(cx, local_did),
2033             deprecation: get_deprecation(cx, local_did),
2034             inner,
2035         }
2036     }
2037 }
2038
2039 impl Clean<Item> for hir::ImplItem {
2040     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
2041         let inner = match self.node {
2042             hir::ImplItemKind::Const(ref ty, expr) => {
2043                 AssociatedConstItem(ty.clean(cx),
2044                                     Some(print_const_expr(cx, expr)))
2045             }
2046             hir::ImplItemKind::Method(ref sig, body) => {
2047                 MethodItem((sig, &self.generics, body).clean(cx))
2048             }
2049             hir::ImplItemKind::Type(ref ty) => TypedefItem(Typedef {
2050                 type_: ty.clean(cx),
2051                 generics: Generics::default(),
2052             }, true),
2053             hir::ImplItemKind::Existential(ref bounds) => ExistentialItem(Existential {
2054                 bounds: bounds.clean(cx),
2055                 generics: Generics::default(),
2056             }, true),
2057         };
2058         let local_did = cx.tcx.hir().local_def_id_from_hir_id(self.hir_id);
2059         Item {
2060             name: Some(self.ident.name.clean(cx)),
2061             source: self.span.clean(cx),
2062             attrs: self.attrs.clean(cx),
2063             def_id: local_did,
2064             visibility: self.vis.clean(cx),
2065             stability: get_stability(cx, local_did),
2066             deprecation: get_deprecation(cx, local_did),
2067             inner,
2068         }
2069     }
2070 }
2071
2072 impl<'tcx> Clean<Item> for ty::AssociatedItem {
2073     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
2074         let inner = match self.kind {
2075             ty::AssociatedKind::Const => {
2076                 let ty = cx.tcx.type_of(self.def_id);
2077                 let default = if self.defaultness.has_value() {
2078                     Some(inline::print_inlined_const(cx, self.def_id))
2079                 } else {
2080                     None
2081                 };
2082                 AssociatedConstItem(ty.clean(cx), default)
2083             }
2084             ty::AssociatedKind::Method => {
2085                 let generics = (cx.tcx.generics_of(self.def_id),
2086                                 &cx.tcx.predicates_of(self.def_id)).clean(cx);
2087                 let sig = cx.tcx.fn_sig(self.def_id);
2088                 let mut decl = (self.def_id, sig).clean(cx);
2089
2090                 if self.method_has_self_argument {
2091                     let self_ty = match self.container {
2092                         ty::ImplContainer(def_id) => {
2093                             cx.tcx.type_of(def_id)
2094                         }
2095                         ty::TraitContainer(_) => cx.tcx.mk_self_type()
2096                     };
2097                     let self_arg_ty = *sig.input(0).skip_binder();
2098                     if self_arg_ty == self_ty {
2099                         decl.inputs.values[0].type_ = Generic(String::from("Self"));
2100                     } else if let ty::Ref(_, ty, _) = self_arg_ty.sty {
2101                         if ty == self_ty {
2102                             match decl.inputs.values[0].type_ {
2103                                 BorrowedRef{ref mut type_, ..} => {
2104                                     **type_ = Generic(String::from("Self"))
2105                                 }
2106                                 _ => unreachable!(),
2107                             }
2108                         }
2109                     }
2110                 }
2111
2112                 let provided = match self.container {
2113                     ty::ImplContainer(_) => true,
2114                     ty::TraitContainer(_) => self.defaultness.has_value()
2115                 };
2116                 if provided {
2117                     let constness = if cx.tcx.is_min_const_fn(self.def_id) {
2118                         hir::Constness::Const
2119                     } else {
2120                         hir::Constness::NotConst
2121                     };
2122                     MethodItem(Method {
2123                         generics,
2124                         decl,
2125                         header: hir::FnHeader {
2126                             unsafety: sig.unsafety(),
2127                             abi: sig.abi(),
2128                             constness,
2129                             asyncness: hir::IsAsync::NotAsync,
2130                         }
2131                     })
2132                 } else {
2133                     TyMethodItem(TyMethod {
2134                         generics,
2135                         decl,
2136                         header: hir::FnHeader {
2137                             unsafety: sig.unsafety(),
2138                             abi: sig.abi(),
2139                             constness: hir::Constness::NotConst,
2140                             asyncness: hir::IsAsync::NotAsync,
2141                         }
2142                     })
2143                 }
2144             }
2145             ty::AssociatedKind::Type => {
2146                 let my_name = self.ident.name.clean(cx);
2147
2148                 if let ty::TraitContainer(did) = self.container {
2149                     // When loading a cross-crate associated type, the bounds for this type
2150                     // are actually located on the trait/impl itself, so we need to load
2151                     // all of the generics from there and then look for bounds that are
2152                     // applied to this associated type in question.
2153                     let predicates = cx.tcx.predicates_of(did);
2154                     let generics = (cx.tcx.generics_of(did), &predicates).clean(cx);
2155                     let mut bounds = generics.where_predicates.iter().filter_map(|pred| {
2156                         let (name, self_type, trait_, bounds) = match *pred {
2157                             WherePredicate::BoundPredicate {
2158                                 ty: QPath { ref name, ref self_type, ref trait_ },
2159                                 ref bounds
2160                             } => (name, self_type, trait_, bounds),
2161                             _ => return None,
2162                         };
2163                         if *name != my_name { return None }
2164                         match **trait_ {
2165                             ResolvedPath { did, .. } if did == self.container.id() => {}
2166                             _ => return None,
2167                         }
2168                         match **self_type {
2169                             Generic(ref s) if *s == "Self" => {}
2170                             _ => return None,
2171                         }
2172                         Some(bounds)
2173                     }).flat_map(|i| i.iter().cloned()).collect::<Vec<_>>();
2174                     // Our Sized/?Sized bound didn't get handled when creating the generics
2175                     // because we didn't actually get our whole set of bounds until just now
2176                     // (some of them may have come from the trait). If we do have a sized
2177                     // bound, we remove it, and if we don't then we add the `?Sized` bound
2178                     // at the end.
2179                     match bounds.iter().position(|b| b.is_sized_bound(cx)) {
2180                         Some(i) => { bounds.remove(i); }
2181                         None => bounds.push(GenericBound::maybe_sized(cx)),
2182                     }
2183
2184                     let ty = if self.defaultness.has_value() {
2185                         Some(cx.tcx.type_of(self.def_id))
2186                     } else {
2187                         None
2188                     };
2189
2190                     AssociatedTypeItem(bounds, ty.clean(cx))
2191                 } else {
2192                     TypedefItem(Typedef {
2193                         type_: cx.tcx.type_of(self.def_id).clean(cx),
2194                         generics: Generics {
2195                             params: Vec::new(),
2196                             where_predicates: Vec::new(),
2197                         },
2198                     }, true)
2199                 }
2200             }
2201             ty::AssociatedKind::Existential => unimplemented!(),
2202         };
2203
2204         let visibility = match self.container {
2205             ty::ImplContainer(_) => self.vis.clean(cx),
2206             ty::TraitContainer(_) => None,
2207         };
2208
2209         Item {
2210             name: Some(self.ident.name.clean(cx)),
2211             visibility,
2212             stability: get_stability(cx, self.def_id),
2213             deprecation: get_deprecation(cx, self.def_id),
2214             def_id: self.def_id,
2215             attrs: inline::load_attrs(cx, self.def_id),
2216             source: cx.tcx.def_span(self.def_id).clean(cx),
2217             inner,
2218         }
2219     }
2220 }
2221
2222 /// A trait reference, which may have higher ranked lifetimes.
2223 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2224 pub struct PolyTrait {
2225     pub trait_: Type,
2226     pub generic_params: Vec<GenericParamDef>,
2227 }
2228
2229 /// A representation of a Type suitable for hyperlinking purposes. Ideally one can get the original
2230 /// type out of the AST/TyCtxt given one of these, if more information is needed. Most importantly
2231 /// it does not preserve mutability or boxes.
2232 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2233 pub enum Type {
2234     /// Structs/enums/traits (most that'd be an `hir::TyKind::Path`).
2235     ResolvedPath {
2236         path: Path,
2237         typarams: Option<Vec<GenericBound>>,
2238         did: DefId,
2239         /// `true` if is a `T::Name` path for associated types.
2240         is_generic: bool,
2241     },
2242     /// For parameterized types, so the consumer of the JSON don't go
2243     /// looking for types which don't exist anywhere.
2244     Generic(String),
2245     /// Primitives are the fixed-size numeric types (plus int/usize/float), char,
2246     /// arrays, slices, and tuples.
2247     Primitive(PrimitiveType),
2248     /// extern "ABI" fn
2249     BareFunction(Box<BareFunctionDecl>),
2250     Tuple(Vec<Type>),
2251     Slice(Box<Type>),
2252     Array(Box<Type>, String),
2253     Never,
2254     CVarArgs,
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     CVarArgs,
2294 }
2295
2296 #[derive(Clone, RustcEncodable, RustcDecodable, Copy, Debug)]
2297 pub enum TypeKind {
2298     Enum,
2299     Function,
2300     Module,
2301     Const,
2302     Static,
2303     Struct,
2304     Union,
2305     Trait,
2306     Variant,
2307     Typedef,
2308     Foreign,
2309     Macro,
2310     Attr,
2311     Derive,
2312     TraitAlias,
2313 }
2314
2315 pub trait GetDefId {
2316     fn def_id(&self) -> Option<DefId>;
2317 }
2318
2319 impl<T: GetDefId> GetDefId for Option<T> {
2320     fn def_id(&self) -> Option<DefId> {
2321         self.as_ref().and_then(|d| d.def_id())
2322     }
2323 }
2324
2325 impl Type {
2326     pub fn primitive_type(&self) -> Option<PrimitiveType> {
2327         match *self {
2328             Primitive(p) | BorrowedRef { type_: box Primitive(p), ..} => Some(p),
2329             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
2330             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
2331             Tuple(ref tys) => if tys.is_empty() {
2332                 Some(PrimitiveType::Unit)
2333             } else {
2334                 Some(PrimitiveType::Tuple)
2335             },
2336             RawPointer(..) => Some(PrimitiveType::RawPointer),
2337             BorrowedRef { type_: box Generic(..), .. } => Some(PrimitiveType::Reference),
2338             BareFunction(..) => Some(PrimitiveType::Fn),
2339             Never => Some(PrimitiveType::Never),
2340             _ => None,
2341         }
2342     }
2343
2344     pub fn is_generic(&self) -> bool {
2345         match *self {
2346             ResolvedPath { is_generic, .. } => is_generic,
2347             _ => false,
2348         }
2349     }
2350
2351     pub fn is_self_type(&self) -> bool {
2352         match *self {
2353             Generic(ref name) => name == "Self",
2354             _ => false
2355         }
2356     }
2357
2358     pub fn generics(&self) -> Option<&[Type]> {
2359         match *self {
2360             ResolvedPath { ref path, .. } => {
2361                 path.segments.last().and_then(|seg| {
2362                     if let GenericArgs::AngleBracketed { ref types, .. } = seg.args {
2363                         Some(&**types)
2364                     } else {
2365                         None
2366                     }
2367                 })
2368             }
2369             _ => None,
2370         }
2371     }
2372
2373     pub fn bindings(&self) -> Option<&[TypeBinding]> {
2374         match *self {
2375             ResolvedPath { ref path, .. } => {
2376                 path.segments.last().and_then(|seg| {
2377                     if let GenericArgs::AngleBracketed { ref bindings, .. } = seg.args {
2378                         Some(&**bindings)
2379                     } else {
2380                         None
2381                     }
2382                 })
2383             }
2384             _ => None
2385         }
2386     }
2387 }
2388
2389 impl GetDefId for Type {
2390     fn def_id(&self) -> Option<DefId> {
2391         match *self {
2392             ResolvedPath { did, .. } => Some(did),
2393             Primitive(p) => crate::html::render::cache().primitive_locations.get(&p).cloned(),
2394             BorrowedRef { type_: box Generic(..), .. } =>
2395                 Primitive(PrimitiveType::Reference).def_id(),
2396             BorrowedRef { ref type_, .. } => type_.def_id(),
2397             Tuple(ref tys) => if tys.is_empty() {
2398                 Primitive(PrimitiveType::Unit).def_id()
2399             } else {
2400                 Primitive(PrimitiveType::Tuple).def_id()
2401             },
2402             BareFunction(..) => Primitive(PrimitiveType::Fn).def_id(),
2403             Never => Primitive(PrimitiveType::Never).def_id(),
2404             Slice(..) => Primitive(PrimitiveType::Slice).def_id(),
2405             Array(..) => Primitive(PrimitiveType::Array).def_id(),
2406             RawPointer(..) => Primitive(PrimitiveType::RawPointer).def_id(),
2407             QPath { ref self_type, .. } => self_type.def_id(),
2408             _ => None,
2409         }
2410     }
2411 }
2412
2413 impl PrimitiveType {
2414     fn from_str(s: &str) -> Option<PrimitiveType> {
2415         match s {
2416             "isize" => Some(PrimitiveType::Isize),
2417             "i8" => Some(PrimitiveType::I8),
2418             "i16" => Some(PrimitiveType::I16),
2419             "i32" => Some(PrimitiveType::I32),
2420             "i64" => Some(PrimitiveType::I64),
2421             "i128" => Some(PrimitiveType::I128),
2422             "usize" => Some(PrimitiveType::Usize),
2423             "u8" => Some(PrimitiveType::U8),
2424             "u16" => Some(PrimitiveType::U16),
2425             "u32" => Some(PrimitiveType::U32),
2426             "u64" => Some(PrimitiveType::U64),
2427             "u128" => Some(PrimitiveType::U128),
2428             "bool" => Some(PrimitiveType::Bool),
2429             "char" => Some(PrimitiveType::Char),
2430             "str" => Some(PrimitiveType::Str),
2431             "f32" => Some(PrimitiveType::F32),
2432             "f64" => Some(PrimitiveType::F64),
2433             "array" => Some(PrimitiveType::Array),
2434             "slice" => Some(PrimitiveType::Slice),
2435             "tuple" => Some(PrimitiveType::Tuple),
2436             "unit" => Some(PrimitiveType::Unit),
2437             "pointer" => Some(PrimitiveType::RawPointer),
2438             "reference" => Some(PrimitiveType::Reference),
2439             "fn" => Some(PrimitiveType::Fn),
2440             "never" => Some(PrimitiveType::Never),
2441             _ => None,
2442         }
2443     }
2444
2445     pub fn as_str(&self) -> &'static str {
2446         use self::PrimitiveType::*;
2447         match *self {
2448             Isize => "isize",
2449             I8 => "i8",
2450             I16 => "i16",
2451             I32 => "i32",
2452             I64 => "i64",
2453             I128 => "i128",
2454             Usize => "usize",
2455             U8 => "u8",
2456             U16 => "u16",
2457             U32 => "u32",
2458             U64 => "u64",
2459             U128 => "u128",
2460             F32 => "f32",
2461             F64 => "f64",
2462             Str => "str",
2463             Bool => "bool",
2464             Char => "char",
2465             Array => "array",
2466             Slice => "slice",
2467             Tuple => "tuple",
2468             Unit => "unit",
2469             RawPointer => "pointer",
2470             Reference => "reference",
2471             Fn => "fn",
2472             Never => "never",
2473             CVarArgs => "...",
2474         }
2475     }
2476
2477     pub fn to_url_str(&self) -> &'static str {
2478         self.as_str()
2479     }
2480 }
2481
2482 impl From<ast::IntTy> for PrimitiveType {
2483     fn from(int_ty: ast::IntTy) -> PrimitiveType {
2484         match int_ty {
2485             ast::IntTy::Isize => PrimitiveType::Isize,
2486             ast::IntTy::I8 => PrimitiveType::I8,
2487             ast::IntTy::I16 => PrimitiveType::I16,
2488             ast::IntTy::I32 => PrimitiveType::I32,
2489             ast::IntTy::I64 => PrimitiveType::I64,
2490             ast::IntTy::I128 => PrimitiveType::I128,
2491         }
2492     }
2493 }
2494
2495 impl From<ast::UintTy> for PrimitiveType {
2496     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
2497         match uint_ty {
2498             ast::UintTy::Usize => PrimitiveType::Usize,
2499             ast::UintTy::U8 => PrimitiveType::U8,
2500             ast::UintTy::U16 => PrimitiveType::U16,
2501             ast::UintTy::U32 => PrimitiveType::U32,
2502             ast::UintTy::U64 => PrimitiveType::U64,
2503             ast::UintTy::U128 => PrimitiveType::U128,
2504         }
2505     }
2506 }
2507
2508 impl From<ast::FloatTy> for PrimitiveType {
2509     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
2510         match float_ty {
2511             ast::FloatTy::F32 => PrimitiveType::F32,
2512             ast::FloatTy::F64 => PrimitiveType::F64,
2513         }
2514     }
2515 }
2516
2517 impl Clean<Type> for hir::Ty {
2518     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Type {
2519         use rustc::hir::*;
2520
2521         match self.node {
2522             TyKind::Never => Never,
2523             TyKind::CVarArgs(_) => CVarArgs,
2524             TyKind::Ptr(ref m) => RawPointer(m.mutbl.clean(cx), box m.ty.clean(cx)),
2525             TyKind::Rptr(ref l, ref m) => {
2526                 let lifetime = if l.is_elided() {
2527                     None
2528                 } else {
2529                     Some(l.clean(cx))
2530                 };
2531                 BorrowedRef {lifetime: lifetime, mutability: m.mutbl.clean(cx),
2532                              type_: box m.ty.clean(cx)}
2533             }
2534             TyKind::Slice(ref ty) => Slice(box ty.clean(cx)),
2535             TyKind::Array(ref ty, ref length) => {
2536                 let def_id = cx.tcx.hir().local_def_id_from_hir_id(length.hir_id);
2537                 let param_env = cx.tcx.param_env(def_id);
2538                 let substs = InternalSubsts::identity_for_item(cx.tcx, def_id);
2539                 let cid = GlobalId {
2540                     instance: ty::Instance::new(def_id, substs),
2541                     promoted: None
2542                 };
2543                 let length = match cx.tcx.const_eval(param_env.and(cid)) {
2544                     Ok(length) => print_const(cx, ty::LazyConst::Evaluated(length)),
2545                     Err(_) => "_".to_string(),
2546                 };
2547                 Array(box ty.clean(cx), length)
2548             },
2549             TyKind::Tup(ref tys) => Tuple(tys.clean(cx)),
2550             TyKind::Def(item_id, _) => {
2551                 let item = cx.tcx.hir().expect_item(item_id.id);
2552                 if let hir::ItemKind::Existential(ref ty) = item.node {
2553                     ImplTrait(ty.bounds.clean(cx))
2554                 } else {
2555                     unreachable!()
2556                 }
2557             }
2558             TyKind::Path(hir::QPath::Resolved(None, ref path)) => {
2559                 if let Some(new_ty) = cx.ty_substs.borrow().get(&path.def).cloned() {
2560                     return new_ty;
2561                 }
2562
2563                 if let Def::TyParam(did) = path.def {
2564                     if let Some(bounds) = cx.impl_trait_bounds.borrow_mut().remove(&did) {
2565                         return ImplTrait(bounds);
2566                     }
2567                 }
2568
2569                 let mut alias = None;
2570                 if let Def::TyAlias(def_id) = path.def {
2571                     // Substitute private type aliases
2572                     if let Some(hir_id) = cx.tcx.hir().as_local_hir_id(def_id) {
2573                         if !cx.renderinfo.borrow().access_levels.is_exported(def_id) {
2574                             alias = Some(&cx.tcx.hir().expect_item_by_hir_id(hir_id).node);
2575                         }
2576                     }
2577                 };
2578
2579                 if let Some(&hir::ItemKind::Ty(ref ty, ref generics)) = alias {
2580                     let provided_params = &path.segments.last().expect("segments were empty");
2581                     let mut ty_substs = FxHashMap::default();
2582                     let mut lt_substs = FxHashMap::default();
2583                     let mut const_substs = FxHashMap::default();
2584                     provided_params.with_generic_args(|generic_args| {
2585                         let mut indices: GenericParamCount = Default::default();
2586                         for param in generics.params.iter() {
2587                             match param.kind {
2588                                 hir::GenericParamKind::Lifetime { .. } => {
2589                                     let mut j = 0;
2590                                     let lifetime = generic_args.args.iter().find_map(|arg| {
2591                                         match arg {
2592                                             hir::GenericArg::Lifetime(lt) => {
2593                                                 if indices.lifetimes == j {
2594                                                     return Some(lt);
2595                                                 }
2596                                                 j += 1;
2597                                                 None
2598                                             }
2599                                             _ => None,
2600                                         }
2601                                     });
2602                                     if let Some(lt) = lifetime.cloned() {
2603                                         if !lt.is_elided() {
2604                                             let lt_def_id =
2605                                                 cx.tcx.hir().local_def_id_from_hir_id(param.hir_id);
2606                                             lt_substs.insert(lt_def_id, lt.clean(cx));
2607                                         }
2608                                     }
2609                                     indices.lifetimes += 1;
2610                                 }
2611                                 hir::GenericParamKind::Type { ref default, .. } => {
2612                                     let ty_param_def =
2613                                         Def::TyParam(
2614                                             cx.tcx.hir().local_def_id_from_hir_id(param.hir_id));
2615                                     let mut j = 0;
2616                                     let type_ = generic_args.args.iter().find_map(|arg| {
2617                                         match arg {
2618                                             hir::GenericArg::Type(ty) => {
2619                                                 if indices.types == j {
2620                                                     return Some(ty);
2621                                                 }
2622                                                 j += 1;
2623                                                 None
2624                                             }
2625                                             _ => None,
2626                                         }
2627                                     });
2628                                     if let Some(ty) = type_.cloned() {
2629                                         ty_substs.insert(ty_param_def, ty.clean(cx));
2630                                     } else if let Some(default) = default.clone() {
2631                                         ty_substs.insert(ty_param_def,
2632                                                          default.into_inner().clean(cx));
2633                                     }
2634                                     indices.types += 1;
2635                                 }
2636                                 hir::GenericParamKind::Const { .. } => {
2637                                     let const_param_def =
2638                                         Def::ConstParam(
2639                                             cx.tcx.hir().local_def_id_from_hir_id(param.hir_id));
2640                                     let mut j = 0;
2641                                     let const_ = generic_args.args.iter().find_map(|arg| {
2642                                         match arg {
2643                                             hir::GenericArg::Const(ct) => {
2644                                                 if indices.consts == j {
2645                                                     return Some(ct);
2646                                                 }
2647                                                 j += 1;
2648                                                 None
2649                                             }
2650                                             _ => None,
2651                                         }
2652                                     });
2653                                     if let Some(ct) = const_.cloned() {
2654                                         const_substs.insert(const_param_def, ct.clean(cx));
2655                                     }
2656                                     // FIXME(const_generics:defaults)
2657                                     indices.consts += 1;
2658                                 }
2659                             }
2660                         }
2661                     });
2662                     return cx.enter_alias(ty_substs, lt_substs, const_substs, || ty.clean(cx));
2663                 }
2664                 resolve_type(cx, path.clean(cx), self.hir_id)
2665             }
2666             TyKind::Path(hir::QPath::Resolved(Some(ref qself), ref p)) => {
2667                 let mut segments: Vec<_> = p.segments.clone().into();
2668                 segments.pop();
2669                 let trait_path = hir::Path {
2670                     span: p.span,
2671                     def: Def::Trait(cx.tcx.associated_item(p.def.def_id()).container.id()),
2672                     segments: segments.into(),
2673                 };
2674                 Type::QPath {
2675                     name: p.segments.last().expect("segments were empty").ident.name.clean(cx),
2676                     self_type: box qself.clean(cx),
2677                     trait_: box resolve_type(cx, trait_path.clean(cx), self.hir_id)
2678                 }
2679             }
2680             TyKind::Path(hir::QPath::TypeRelative(ref qself, ref segment)) => {
2681                 let mut def = Def::Err;
2682                 let ty = hir_ty_to_ty(cx.tcx, self);
2683                 if let ty::Projection(proj) = ty.sty {
2684                     def = Def::Trait(proj.trait_ref(cx.tcx).def_id);
2685                 }
2686                 let trait_path = hir::Path {
2687                     span: self.span,
2688                     def,
2689                     segments: vec![].into(),
2690                 };
2691                 Type::QPath {
2692                     name: segment.ident.name.clean(cx),
2693                     self_type: box qself.clean(cx),
2694                     trait_: box resolve_type(cx, trait_path.clean(cx), self.hir_id)
2695                 }
2696             }
2697             TyKind::TraitObject(ref bounds, ref lifetime) => {
2698                 match bounds[0].clean(cx).trait_ {
2699                     ResolvedPath { path, typarams: None, did, is_generic } => {
2700                         let mut bounds: Vec<self::GenericBound> = bounds[1..].iter().map(|bound| {
2701                             self::GenericBound::TraitBound(bound.clean(cx),
2702                                                            hir::TraitBoundModifier::None)
2703                         }).collect();
2704                         if !lifetime.is_elided() {
2705                             bounds.push(self::GenericBound::Outlives(lifetime.clean(cx)));
2706                         }
2707                         ResolvedPath { path, typarams: Some(bounds), did, is_generic, }
2708                     }
2709                     _ => Infer // shouldn't happen
2710                 }
2711             }
2712             TyKind::BareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
2713             TyKind::Infer | TyKind::Err => Infer,
2714             TyKind::Typeof(..) => panic!("Unimplemented type {:?}", self.node),
2715         }
2716     }
2717 }
2718
2719 impl<'tcx> Clean<Type> for Ty<'tcx> {
2720     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Type {
2721         match self.sty {
2722             ty::Never => Never,
2723             ty::Bool => Primitive(PrimitiveType::Bool),
2724             ty::Char => Primitive(PrimitiveType::Char),
2725             ty::Int(int_ty) => Primitive(int_ty.into()),
2726             ty::Uint(uint_ty) => Primitive(uint_ty.into()),
2727             ty::Float(float_ty) => Primitive(float_ty.into()),
2728             ty::Str => Primitive(PrimitiveType::Str),
2729             ty::Slice(ty) => Slice(box ty.clean(cx)),
2730             ty::Array(ty, n) => {
2731                 let mut n = *cx.tcx.lift(&n).expect("array lift failed");
2732                 if let ty::LazyConst::Unevaluated(def_id, substs) = n {
2733                     let param_env = cx.tcx.param_env(def_id);
2734                     let cid = GlobalId {
2735                         instance: ty::Instance::new(def_id, substs),
2736                         promoted: None
2737                     };
2738                     if let Ok(new_n) = cx.tcx.const_eval(param_env.and(cid)) {
2739                         n = ty::LazyConst::Evaluated(new_n);
2740                     }
2741                 };
2742                 let n = print_const(cx, n);
2743                 Array(box ty.clean(cx), n)
2744             }
2745             ty::RawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
2746             ty::Ref(r, ty, mutbl) => BorrowedRef {
2747                 lifetime: r.clean(cx),
2748                 mutability: mutbl.clean(cx),
2749                 type_: box ty.clean(cx),
2750             },
2751             ty::FnDef(..) |
2752             ty::FnPtr(_) => {
2753                 let ty = cx.tcx.lift(self).expect("FnPtr lift failed");
2754                 let sig = ty.fn_sig(cx.tcx);
2755                 BareFunction(box BareFunctionDecl {
2756                     unsafety: sig.unsafety(),
2757                     generic_params: Vec::new(),
2758                     decl: (cx.tcx.hir().local_def_id(ast::CRATE_NODE_ID), sig).clean(cx),
2759                     abi: sig.abi(),
2760                 })
2761             }
2762             ty::Adt(def, substs) => {
2763                 let did = def.did;
2764                 let kind = match def.adt_kind() {
2765                     AdtKind::Struct => TypeKind::Struct,
2766                     AdtKind::Union => TypeKind::Union,
2767                     AdtKind::Enum => TypeKind::Enum,
2768                 };
2769                 inline::record_extern_fqn(cx, did, kind);
2770                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
2771                                          None, false, vec![], substs);
2772                 ResolvedPath {
2773                     path,
2774                     typarams: None,
2775                     did,
2776                     is_generic: false,
2777                 }
2778             }
2779             ty::Foreign(did) => {
2780                 inline::record_extern_fqn(cx, did, TypeKind::Foreign);
2781                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
2782                                          None, false, vec![], InternalSubsts::empty());
2783                 ResolvedPath {
2784                     path: path,
2785                     typarams: None,
2786                     did: did,
2787                     is_generic: false,
2788                 }
2789             }
2790             ty::Dynamic(ref obj, ref reg) => {
2791                 // HACK: pick the first `did` as the `did` of the trait object. Someone
2792                 // might want to implement "native" support for marker-trait-only
2793                 // trait objects.
2794                 let mut dids = obj.principal_def_id().into_iter().chain(obj.auto_traits());
2795                 let did = dids.next().unwrap_or_else(|| {
2796                     panic!("found trait object `{:?}` with no traits?", self)
2797                 });
2798                 let substs = match obj.principal() {
2799                     Some(principal) => principal.skip_binder().substs,
2800                     // marker traits have no substs.
2801                     _ => cx.tcx.intern_substs(&[])
2802                 };
2803
2804                 inline::record_extern_fqn(cx, did, TypeKind::Trait);
2805
2806                 let mut typarams = vec![];
2807                 reg.clean(cx).map(|b| typarams.push(GenericBound::Outlives(b)));
2808                 for did in dids {
2809                     let empty = cx.tcx.intern_substs(&[]);
2810                     let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
2811                         Some(did), false, vec![], empty);
2812                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
2813                     let bound = GenericBound::TraitBound(PolyTrait {
2814                         trait_: ResolvedPath {
2815                             path,
2816                             typarams: None,
2817                             did,
2818                             is_generic: false,
2819                         },
2820                         generic_params: Vec::new(),
2821                     }, hir::TraitBoundModifier::None);
2822                     typarams.push(bound);
2823                 }
2824
2825                 let mut bindings = vec![];
2826                 for pb in obj.projection_bounds() {
2827                     bindings.push(TypeBinding {
2828                         name: cx.tcx.associated_item(pb.item_def_id()).ident.name.clean(cx),
2829                         ty: pb.skip_binder().ty.clean(cx)
2830                     });
2831                 }
2832
2833                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(), Some(did),
2834                     false, bindings, substs);
2835                 ResolvedPath {
2836                     path,
2837                     typarams: Some(typarams),
2838                     did,
2839                     is_generic: false,
2840                 }
2841             }
2842             ty::Tuple(ref t) => Tuple(t.clean(cx)),
2843
2844             ty::Projection(ref data) => data.clean(cx),
2845
2846             ty::Param(ref p) => Generic(p.name.to_string()),
2847
2848             ty::Opaque(def_id, substs) => {
2849                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
2850                 // by looking up the projections associated with the def_id.
2851                 let predicates_of = cx.tcx.predicates_of(def_id);
2852                 let substs = cx.tcx.lift(&substs).expect("Opaque lift failed");
2853                 let bounds = predicates_of.instantiate(cx.tcx, substs);
2854                 let mut regions = vec![];
2855                 let mut has_sized = false;
2856                 let mut bounds = bounds.predicates.iter().filter_map(|predicate| {
2857                     let trait_ref = if let Some(tr) = predicate.to_opt_poly_trait_ref() {
2858                         tr
2859                     } else if let ty::Predicate::TypeOutlives(pred) = *predicate {
2860                         // these should turn up at the end
2861                         pred.skip_binder().1.clean(cx).map(|r| {
2862                             regions.push(GenericBound::Outlives(r))
2863                         });
2864                         return None;
2865                     } else {
2866                         return None;
2867                     };
2868
2869                     if let Some(sized) = cx.tcx.lang_items().sized_trait() {
2870                         if trait_ref.def_id() == sized {
2871                             has_sized = true;
2872                             return None;
2873                         }
2874                     }
2875
2876                     let bounds = bounds.predicates.iter().filter_map(|pred|
2877                         if let ty::Predicate::Projection(proj) = *pred {
2878                             let proj = proj.skip_binder();
2879                             if proj.projection_ty.trait_ref(cx.tcx) == *trait_ref.skip_binder() {
2880                                 Some(TypeBinding {
2881                                     name: cx.tcx.associated_item(proj.projection_ty.item_def_id)
2882                                                 .ident.name.clean(cx),
2883                                     ty: proj.ty.clean(cx),
2884                                 })
2885                             } else {
2886                                 None
2887                             }
2888                         } else {
2889                             None
2890                         }
2891                     ).collect();
2892
2893                     Some((trait_ref.skip_binder(), bounds).clean(cx))
2894                 }).collect::<Vec<_>>();
2895                 bounds.extend(regions);
2896                 if !has_sized && !bounds.is_empty() {
2897                     bounds.insert(0, GenericBound::maybe_sized(cx));
2898                 }
2899                 ImplTrait(bounds)
2900             }
2901
2902             ty::Closure(..) | ty::Generator(..) => Tuple(vec![]), // FIXME(pcwalton)
2903
2904             ty::Bound(..) => panic!("Bound"),
2905             ty::Placeholder(..) => panic!("Placeholder"),
2906             ty::UnnormalizedProjection(..) => panic!("UnnormalizedProjection"),
2907             ty::GeneratorWitness(..) => panic!("GeneratorWitness"),
2908             ty::Infer(..) => panic!("Infer"),
2909             ty::Error => panic!("Error"),
2910         }
2911     }
2912 }
2913
2914 impl Clean<Item> for hir::StructField {
2915     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
2916         Item {
2917             name: Some(self.ident.name).clean(cx),
2918             attrs: self.attrs.clean(cx),
2919             source: self.span.clean(cx),
2920             visibility: self.vis.clean(cx),
2921             stability: get_stability(cx, cx.tcx.hir().local_def_id(self.id)),
2922             deprecation: get_deprecation(cx, cx.tcx.hir().local_def_id(self.id)),
2923             def_id: cx.tcx.hir().local_def_id(self.id),
2924             inner: StructFieldItem(self.ty.clean(cx)),
2925         }
2926     }
2927 }
2928
2929 impl<'tcx> Clean<Item> for ty::FieldDef {
2930     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
2931         Item {
2932             name: Some(self.ident.name).clean(cx),
2933             attrs: cx.tcx.get_attrs(self.did).clean(cx),
2934             source: cx.tcx.def_span(self.did).clean(cx),
2935             visibility: self.vis.clean(cx),
2936             stability: get_stability(cx, self.did),
2937             deprecation: get_deprecation(cx, self.did),
2938             def_id: self.did,
2939             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
2940         }
2941     }
2942 }
2943
2944 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug)]
2945 pub enum Visibility {
2946     Public,
2947     Inherited,
2948     Crate,
2949     Restricted(DefId, Path),
2950 }
2951
2952 impl Clean<Option<Visibility>> for hir::Visibility {
2953     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Option<Visibility> {
2954         Some(match self.node {
2955             hir::VisibilityKind::Public => Visibility::Public,
2956             hir::VisibilityKind::Inherited => Visibility::Inherited,
2957             hir::VisibilityKind::Crate(_) => Visibility::Crate,
2958             hir::VisibilityKind::Restricted { ref path, .. } => {
2959                 let path = path.clean(cx);
2960                 let did = register_def(cx, path.def);
2961                 Visibility::Restricted(did, path)
2962             }
2963         })
2964     }
2965 }
2966
2967 impl Clean<Option<Visibility>> for ty::Visibility {
2968     fn clean(&self, _: &DocContext<'_, '_, '_>) -> Option<Visibility> {
2969         Some(if *self == ty::Visibility::Public { Public } else { Inherited })
2970     }
2971 }
2972
2973 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2974 pub struct Struct {
2975     pub struct_type: doctree::StructType,
2976     pub generics: Generics,
2977     pub fields: Vec<Item>,
2978     pub fields_stripped: bool,
2979 }
2980
2981 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2982 pub struct Union {
2983     pub struct_type: doctree::StructType,
2984     pub generics: Generics,
2985     pub fields: Vec<Item>,
2986     pub fields_stripped: bool,
2987 }
2988
2989 impl Clean<Item> for doctree::Struct {
2990     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
2991         Item {
2992             name: Some(self.name.clean(cx)),
2993             attrs: self.attrs.clean(cx),
2994             source: self.whence.clean(cx),
2995             def_id: cx.tcx.hir().local_def_id(self.id),
2996             visibility: self.vis.clean(cx),
2997             stability: self.stab.clean(cx),
2998             deprecation: self.depr.clean(cx),
2999             inner: StructItem(Struct {
3000                 struct_type: self.struct_type,
3001                 generics: self.generics.clean(cx),
3002                 fields: self.fields.clean(cx),
3003                 fields_stripped: false,
3004             }),
3005         }
3006     }
3007 }
3008
3009 impl Clean<Item> for doctree::Union {
3010     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
3011         Item {
3012             name: Some(self.name.clean(cx)),
3013             attrs: self.attrs.clean(cx),
3014             source: self.whence.clean(cx),
3015             def_id: cx.tcx.hir().local_def_id(self.id),
3016             visibility: self.vis.clean(cx),
3017             stability: self.stab.clean(cx),
3018             deprecation: self.depr.clean(cx),
3019             inner: UnionItem(Union {
3020                 struct_type: self.struct_type,
3021                 generics: self.generics.clean(cx),
3022                 fields: self.fields.clean(cx),
3023                 fields_stripped: false,
3024             }),
3025         }
3026     }
3027 }
3028
3029 /// This is a more limited form of the standard Struct, different in that
3030 /// it lacks the things most items have (name, id, parameterization). Found
3031 /// only as a variant in an enum.
3032 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3033 pub struct VariantStruct {
3034     pub struct_type: doctree::StructType,
3035     pub fields: Vec<Item>,
3036     pub fields_stripped: bool,
3037 }
3038
3039 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
3040     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> VariantStruct {
3041         VariantStruct {
3042             struct_type: doctree::struct_type_from_def(self),
3043             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
3044             fields_stripped: false,
3045         }
3046     }
3047 }
3048
3049 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3050 pub struct Enum {
3051     pub variants: IndexVec<VariantIdx, Item>,
3052     pub generics: Generics,
3053     pub variants_stripped: bool,
3054 }
3055
3056 impl Clean<Item> for doctree::Enum {
3057     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
3058         Item {
3059             name: Some(self.name.clean(cx)),
3060             attrs: self.attrs.clean(cx),
3061             source: self.whence.clean(cx),
3062             def_id: cx.tcx.hir().local_def_id(self.id),
3063             visibility: self.vis.clean(cx),
3064             stability: self.stab.clean(cx),
3065             deprecation: self.depr.clean(cx),
3066             inner: EnumItem(Enum {
3067                 variants: self.variants.iter().map(|v| v.clean(cx)).collect(),
3068                 generics: self.generics.clean(cx),
3069                 variants_stripped: false,
3070             }),
3071         }
3072     }
3073 }
3074
3075 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3076 pub struct Variant {
3077     pub kind: VariantKind,
3078 }
3079
3080 impl Clean<Item> for doctree::Variant {
3081     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
3082         Item {
3083             name: Some(self.name.clean(cx)),
3084             attrs: self.attrs.clean(cx),
3085             source: self.whence.clean(cx),
3086             visibility: None,
3087             stability: self.stab.clean(cx),
3088             deprecation: self.depr.clean(cx),
3089             def_id: cx.tcx.hir().local_def_id(self.def.id()),
3090             inner: VariantItem(Variant {
3091                 kind: self.def.clean(cx),
3092             }),
3093         }
3094     }
3095 }
3096
3097 impl<'tcx> Clean<Item> for ty::VariantDef {
3098     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
3099         let kind = match self.ctor_kind {
3100             CtorKind::Const => VariantKind::CLike,
3101             CtorKind::Fn => {
3102                 VariantKind::Tuple(
3103                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
3104                 )
3105             }
3106             CtorKind::Fictive => {
3107                 VariantKind::Struct(VariantStruct {
3108                     struct_type: doctree::Plain,
3109                     fields_stripped: false,
3110                     fields: self.fields.iter().map(|field| {
3111                         Item {
3112                             source: cx.tcx.def_span(field.did).clean(cx),
3113                             name: Some(field.ident.name.clean(cx)),
3114                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
3115                             visibility: field.vis.clean(cx),
3116                             def_id: field.did,
3117                             stability: get_stability(cx, field.did),
3118                             deprecation: get_deprecation(cx, field.did),
3119                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
3120                         }
3121                     }).collect()
3122                 })
3123             }
3124         };
3125         Item {
3126             name: Some(self.ident.clean(cx)),
3127             attrs: inline::load_attrs(cx, self.did),
3128             source: cx.tcx.def_span(self.did).clean(cx),
3129             visibility: Some(Inherited),
3130             def_id: self.did,
3131             inner: VariantItem(Variant { kind }),
3132             stability: get_stability(cx, self.did),
3133             deprecation: get_deprecation(cx, self.did),
3134         }
3135     }
3136 }
3137
3138 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3139 pub enum VariantKind {
3140     CLike,
3141     Tuple(Vec<Type>),
3142     Struct(VariantStruct),
3143 }
3144
3145 impl Clean<VariantKind> for hir::VariantData {
3146     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> VariantKind {
3147         if self.is_struct() {
3148             VariantKind::Struct(self.clean(cx))
3149         } else if self.is_unit() {
3150             VariantKind::CLike
3151         } else {
3152             VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect())
3153         }
3154     }
3155 }
3156
3157 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3158 pub struct Span {
3159     pub filename: FileName,
3160     pub loline: usize,
3161     pub locol: usize,
3162     pub hiline: usize,
3163     pub hicol: usize,
3164 }
3165
3166 impl Span {
3167     pub fn empty() -> Span {
3168         Span {
3169             filename: FileName::Anon(0),
3170             loline: 0, locol: 0,
3171             hiline: 0, hicol: 0,
3172         }
3173     }
3174 }
3175
3176 impl Clean<Span> for syntax_pos::Span {
3177     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Span {
3178         if self.is_dummy() {
3179             return Span::empty();
3180         }
3181
3182         let cm = cx.sess().source_map();
3183         let filename = cm.span_to_filename(*self);
3184         let lo = cm.lookup_char_pos(self.lo());
3185         let hi = cm.lookup_char_pos(self.hi());
3186         Span {
3187             filename,
3188             loline: lo.line,
3189             locol: lo.col.to_usize(),
3190             hiline: hi.line,
3191             hicol: hi.col.to_usize(),
3192         }
3193     }
3194 }
3195
3196 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3197 pub struct Path {
3198     pub global: bool,
3199     pub def: Def,
3200     pub segments: Vec<PathSegment>,
3201 }
3202
3203 impl Path {
3204     pub fn last_name(&self) -> &str {
3205         self.segments.last().expect("segments were empty").name.as_str()
3206     }
3207 }
3208
3209 impl Clean<Path> for hir::Path {
3210     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Path {
3211         Path {
3212             global: self.is_global(),
3213             def: self.def,
3214             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
3215         }
3216     }
3217 }
3218
3219 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3220 pub enum GenericArgs {
3221     AngleBracketed {
3222         lifetimes: Vec<Lifetime>,
3223         types: Vec<Type>,
3224         bindings: Vec<TypeBinding>,
3225     },
3226     Parenthesized {
3227         inputs: Vec<Type>,
3228         output: Option<Type>,
3229     }
3230 }
3231
3232 impl Clean<GenericArgs> for hir::GenericArgs {
3233     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> GenericArgs {
3234         if self.parenthesized {
3235             let output = self.bindings[0].ty.clean(cx);
3236             GenericArgs::Parenthesized {
3237                 inputs: self.inputs().clean(cx),
3238                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
3239             }
3240         } else {
3241             let (mut lifetimes, mut types) = (vec![], vec![]);
3242             let mut elided_lifetimes = true;
3243             for arg in &self.args {
3244                 match arg {
3245                     GenericArg::Lifetime(lt) => {
3246                         if !lt.is_elided() {
3247                             elided_lifetimes = false;
3248                         }
3249                         lifetimes.push(lt.clean(cx));
3250                     }
3251                     GenericArg::Type(ty) => {
3252                         types.push(ty.clean(cx));
3253                     }
3254                     GenericArg::Const(..) => {
3255                         unimplemented!() // FIXME(const_generics)
3256                     }
3257                 }
3258             }
3259             GenericArgs::AngleBracketed {
3260                 lifetimes: if elided_lifetimes { vec![] } else { lifetimes },
3261                 types,
3262                 bindings: self.bindings.clean(cx),
3263             }
3264         }
3265     }
3266 }
3267
3268 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3269 pub struct PathSegment {
3270     pub name: String,
3271     pub args: GenericArgs,
3272 }
3273
3274 impl Clean<PathSegment> for hir::PathSegment {
3275     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> PathSegment {
3276         PathSegment {
3277             name: self.ident.name.clean(cx),
3278             args: self.with_generic_args(|generic_args| generic_args.clean(cx))
3279         }
3280     }
3281 }
3282
3283 fn strip_type(ty: Type) -> Type {
3284     match ty {
3285         Type::ResolvedPath { path, typarams, did, is_generic } => {
3286             Type::ResolvedPath { path: strip_path(&path), typarams, did, is_generic }
3287         }
3288         Type::Tuple(inner_tys) => {
3289             Type::Tuple(inner_tys.iter().map(|t| strip_type(t.clone())).collect())
3290         }
3291         Type::Slice(inner_ty) => Type::Slice(Box::new(strip_type(*inner_ty))),
3292         Type::Array(inner_ty, s) => Type::Array(Box::new(strip_type(*inner_ty)), s),
3293         Type::Unique(inner_ty) => Type::Unique(Box::new(strip_type(*inner_ty))),
3294         Type::RawPointer(m, inner_ty) => Type::RawPointer(m, Box::new(strip_type(*inner_ty))),
3295         Type::BorrowedRef { lifetime, mutability, type_ } => {
3296             Type::BorrowedRef { lifetime, mutability, type_: Box::new(strip_type(*type_)) }
3297         }
3298         Type::QPath { name, self_type, trait_ } => {
3299             Type::QPath {
3300                 name,
3301                 self_type: Box::new(strip_type(*self_type)), trait_: Box::new(strip_type(*trait_))
3302             }
3303         }
3304         _ => ty
3305     }
3306 }
3307
3308 fn strip_path(path: &Path) -> Path {
3309     let segments = path.segments.iter().map(|s| {
3310         PathSegment {
3311             name: s.name.clone(),
3312             args: GenericArgs::AngleBracketed {
3313                 lifetimes: Vec::new(),
3314                 types: Vec::new(),
3315                 bindings: Vec::new(),
3316             }
3317         }
3318     }).collect();
3319
3320     Path {
3321         global: path.global,
3322         def: path.def.clone(),
3323         segments,
3324     }
3325 }
3326
3327 fn qpath_to_string(p: &hir::QPath) -> String {
3328     let segments = match *p {
3329         hir::QPath::Resolved(_, ref path) => &path.segments,
3330         hir::QPath::TypeRelative(_, ref segment) => return segment.ident.to_string(),
3331     };
3332
3333     let mut s = String::new();
3334     for (i, seg) in segments.iter().enumerate() {
3335         if i > 0 {
3336             s.push_str("::");
3337         }
3338         if seg.ident.name != keywords::PathRoot.name() {
3339             s.push_str(&*seg.ident.as_str());
3340         }
3341     }
3342     s
3343 }
3344
3345 impl Clean<String> for Ident {
3346     #[inline]
3347     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> String {
3348         self.name.clean(cx)
3349     }
3350 }
3351
3352 impl Clean<String> for ast::Name {
3353     #[inline]
3354     fn clean(&self, _: &DocContext<'_, '_, '_>) -> String {
3355         self.to_string()
3356     }
3357 }
3358
3359 impl Clean<String> for InternedString {
3360     #[inline]
3361     fn clean(&self, _: &DocContext<'_, '_, '_>) -> String {
3362         self.to_string()
3363     }
3364 }
3365
3366 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3367 pub struct Typedef {
3368     pub type_: Type,
3369     pub generics: Generics,
3370 }
3371
3372 impl Clean<Item> for doctree::Typedef {
3373     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
3374         Item {
3375             name: Some(self.name.clean(cx)),
3376             attrs: self.attrs.clean(cx),
3377             source: self.whence.clean(cx),
3378             def_id: cx.tcx.hir().local_def_id(self.id.clone()),
3379             visibility: self.vis.clean(cx),
3380             stability: self.stab.clean(cx),
3381             deprecation: self.depr.clean(cx),
3382             inner: TypedefItem(Typedef {
3383                 type_: self.ty.clean(cx),
3384                 generics: self.gen.clean(cx),
3385             }, false),
3386         }
3387     }
3388 }
3389
3390 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3391 pub struct Existential {
3392     pub bounds: Vec<GenericBound>,
3393     pub generics: Generics,
3394 }
3395
3396 impl Clean<Item> for doctree::Existential {
3397     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
3398         Item {
3399             name: Some(self.name.clean(cx)),
3400             attrs: self.attrs.clean(cx),
3401             source: self.whence.clean(cx),
3402             def_id: cx.tcx.hir().local_def_id(self.id.clone()),
3403             visibility: self.vis.clean(cx),
3404             stability: self.stab.clean(cx),
3405             deprecation: self.depr.clean(cx),
3406             inner: ExistentialItem(Existential {
3407                 bounds: self.exist_ty.bounds.clean(cx),
3408                 generics: self.exist_ty.generics.clean(cx),
3409             }, false),
3410         }
3411     }
3412 }
3413
3414 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3415 pub struct BareFunctionDecl {
3416     pub unsafety: hir::Unsafety,
3417     pub generic_params: Vec<GenericParamDef>,
3418     pub decl: FnDecl,
3419     pub abi: Abi,
3420 }
3421
3422 impl Clean<BareFunctionDecl> for hir::BareFnTy {
3423     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> BareFunctionDecl {
3424         let (generic_params, decl) = enter_impl_trait(cx, || {
3425             (self.generic_params.clean(cx), (&*self.decl, &self.arg_names[..]).clean(cx))
3426         });
3427         BareFunctionDecl {
3428             unsafety: self.unsafety,
3429             abi: self.abi,
3430             decl,
3431             generic_params,
3432         }
3433     }
3434 }
3435
3436 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3437 pub struct Static {
3438     pub type_: Type,
3439     pub mutability: Mutability,
3440     /// It's useful to have the value of a static documented, but I have no
3441     /// desire to represent expressions (that'd basically be all of the AST,
3442     /// which is huge!). So, have a string.
3443     pub expr: String,
3444 }
3445
3446 impl Clean<Item> for doctree::Static {
3447     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
3448         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
3449         Item {
3450             name: Some(self.name.clean(cx)),
3451             attrs: self.attrs.clean(cx),
3452             source: self.whence.clean(cx),
3453             def_id: cx.tcx.hir().local_def_id(self.id),
3454             visibility: self.vis.clean(cx),
3455             stability: self.stab.clean(cx),
3456             deprecation: self.depr.clean(cx),
3457             inner: StaticItem(Static {
3458                 type_: self.type_.clean(cx),
3459                 mutability: self.mutability.clean(cx),
3460                 expr: print_const_expr(cx, self.expr),
3461             }),
3462         }
3463     }
3464 }
3465
3466 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3467 pub struct Constant {
3468     pub type_: Type,
3469     pub expr: String,
3470 }
3471
3472 impl Clean<Item> for doctree::Constant {
3473     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
3474         Item {
3475             name: Some(self.name.clean(cx)),
3476             attrs: self.attrs.clean(cx),
3477             source: self.whence.clean(cx),
3478             def_id: cx.tcx.hir().local_def_id(self.id),
3479             visibility: self.vis.clean(cx),
3480             stability: self.stab.clean(cx),
3481             deprecation: self.depr.clean(cx),
3482             inner: ConstantItem(Constant {
3483                 type_: self.type_.clean(cx),
3484                 expr: print_const_expr(cx, self.expr),
3485             }),
3486         }
3487     }
3488 }
3489
3490 #[derive(Debug, Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Hash)]
3491 pub enum Mutability {
3492     Mutable,
3493     Immutable,
3494 }
3495
3496 impl Clean<Mutability> for hir::Mutability {
3497     fn clean(&self, _: &DocContext<'_, '_, '_>) -> Mutability {
3498         match self {
3499             &hir::MutMutable => Mutable,
3500             &hir::MutImmutable => Immutable,
3501         }
3502     }
3503 }
3504
3505 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Debug, Hash)]
3506 pub enum ImplPolarity {
3507     Positive,
3508     Negative,
3509 }
3510
3511 impl Clean<ImplPolarity> for hir::ImplPolarity {
3512     fn clean(&self, _: &DocContext<'_, '_, '_>) -> ImplPolarity {
3513         match self {
3514             &hir::ImplPolarity::Positive => ImplPolarity::Positive,
3515             &hir::ImplPolarity::Negative => ImplPolarity::Negative,
3516         }
3517     }
3518 }
3519
3520 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3521 pub struct Impl {
3522     pub unsafety: hir::Unsafety,
3523     pub generics: Generics,
3524     pub provided_trait_methods: FxHashSet<String>,
3525     pub trait_: Option<Type>,
3526     pub for_: Type,
3527     pub items: Vec<Item>,
3528     pub polarity: Option<ImplPolarity>,
3529     pub synthetic: bool,
3530     pub blanket_impl: Option<Type>,
3531 }
3532
3533 pub fn get_auto_traits_with_node_id(
3534     cx: &DocContext<'_, '_, '_>,
3535     id: ast::NodeId,
3536     name: String
3537 ) -> Vec<Item> {
3538     let finder = AutoTraitFinder::new(cx);
3539     finder.get_with_node_id(id, name)
3540 }
3541
3542 pub fn get_auto_traits_with_def_id(
3543     cx: &DocContext<'_, '_, '_>,
3544     id: DefId
3545 ) -> Vec<Item> {
3546     let finder = AutoTraitFinder::new(cx);
3547
3548     finder.get_with_def_id(id)
3549 }
3550
3551 pub fn get_blanket_impls_with_node_id(
3552     cx: &DocContext<'_, '_, '_>,
3553     id: ast::NodeId,
3554     name: String
3555 ) -> Vec<Item> {
3556     let finder = BlanketImplFinder::new(cx);
3557     finder.get_with_node_id(id, name)
3558 }
3559
3560 pub fn get_blanket_impls_with_def_id(
3561     cx: &DocContext<'_, '_, '_>,
3562     id: DefId
3563 ) -> Vec<Item> {
3564     let finder = BlanketImplFinder::new(cx);
3565
3566     finder.get_with_def_id(id)
3567 }
3568
3569 impl Clean<Vec<Item>> for doctree::Impl {
3570     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Vec<Item> {
3571         let mut ret = Vec::new();
3572         let trait_ = self.trait_.clean(cx);
3573         let items = self.items.clean(cx);
3574
3575         // If this impl block is an implementation of the Deref trait, then we
3576         // need to try inlining the target's inherent impl blocks as well.
3577         if trait_.def_id() == cx.tcx.lang_items().deref_trait() {
3578             build_deref_target_impls(cx, &items, &mut ret);
3579         }
3580
3581         let provided = trait_.def_id().map(|did| {
3582             cx.tcx.provided_trait_methods(did)
3583                   .into_iter()
3584                   .map(|meth| meth.ident.to_string())
3585                   .collect()
3586         }).unwrap_or_default();
3587
3588         ret.push(Item {
3589             name: None,
3590             attrs: self.attrs.clean(cx),
3591             source: self.whence.clean(cx),
3592             def_id: cx.tcx.hir().local_def_id(self.id),
3593             visibility: self.vis.clean(cx),
3594             stability: self.stab.clean(cx),
3595             deprecation: self.depr.clean(cx),
3596             inner: ImplItem(Impl {
3597                 unsafety: self.unsafety,
3598                 generics: self.generics.clean(cx),
3599                 provided_trait_methods: provided,
3600                 trait_,
3601                 for_: self.for_.clean(cx),
3602                 items,
3603                 polarity: Some(self.polarity.clean(cx)),
3604                 synthetic: false,
3605                 blanket_impl: None,
3606             })
3607         });
3608         ret
3609     }
3610 }
3611
3612 fn build_deref_target_impls(cx: &DocContext<'_, '_, '_>,
3613                             items: &[Item],
3614                             ret: &mut Vec<Item>) {
3615     use self::PrimitiveType::*;
3616     let tcx = cx.tcx;
3617
3618     for item in items {
3619         let target = match item.inner {
3620             TypedefItem(ref t, true) => &t.type_,
3621             _ => continue,
3622         };
3623         let primitive = match *target {
3624             ResolvedPath { did, .. } if did.is_local() => continue,
3625             ResolvedPath { did, .. } => {
3626                 ret.extend(inline::build_impls(cx, did));
3627                 continue
3628             }
3629             _ => match target.primitive_type() {
3630                 Some(prim) => prim,
3631                 None => continue,
3632             }
3633         };
3634         let did = match primitive {
3635             Isize => tcx.lang_items().isize_impl(),
3636             I8 => tcx.lang_items().i8_impl(),
3637             I16 => tcx.lang_items().i16_impl(),
3638             I32 => tcx.lang_items().i32_impl(),
3639             I64 => tcx.lang_items().i64_impl(),
3640             I128 => tcx.lang_items().i128_impl(),
3641             Usize => tcx.lang_items().usize_impl(),
3642             U8 => tcx.lang_items().u8_impl(),
3643             U16 => tcx.lang_items().u16_impl(),
3644             U32 => tcx.lang_items().u32_impl(),
3645             U64 => tcx.lang_items().u64_impl(),
3646             U128 => tcx.lang_items().u128_impl(),
3647             F32 => tcx.lang_items().f32_impl(),
3648             F64 => tcx.lang_items().f64_impl(),
3649             Char => tcx.lang_items().char_impl(),
3650             Bool => None,
3651             Str => tcx.lang_items().str_impl(),
3652             Slice => tcx.lang_items().slice_impl(),
3653             Array => tcx.lang_items().slice_impl(),
3654             Tuple => None,
3655             Unit => None,
3656             RawPointer => tcx.lang_items().const_ptr_impl(),
3657             Reference => None,
3658             Fn => None,
3659             Never => None,
3660             CVarArgs => tcx.lang_items().va_list(),
3661         };
3662         if let Some(did) = did {
3663             if !did.is_local() {
3664                 inline::build_impl(cx, did, ret);
3665             }
3666         }
3667     }
3668 }
3669
3670 impl Clean<Vec<Item>> for doctree::ExternCrate {
3671     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Vec<Item> {
3672
3673         let please_inline = self.vis.node.is_pub() && self.attrs.iter().any(|a| {
3674             a.name() == "doc" && match a.meta_item_list() {
3675                 Some(l) => attr::list_contains_name(&l, "inline"),
3676                 None => false,
3677             }
3678         });
3679
3680         if please_inline {
3681             let mut visited = FxHashSet::default();
3682
3683             let def = Def::Mod(DefId {
3684                 krate: self.cnum,
3685                 index: CRATE_DEF_INDEX,
3686             });
3687
3688             if let Some(items) = inline::try_inline(cx, def, self.name, &mut visited) {
3689                 return items;
3690             }
3691         }
3692
3693         vec![Item {
3694             name: None,
3695             attrs: self.attrs.clean(cx),
3696             source: self.whence.clean(cx),
3697             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
3698             visibility: self.vis.clean(cx),
3699             stability: None,
3700             deprecation: None,
3701             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
3702         }]
3703     }
3704 }
3705
3706 impl Clean<Vec<Item>> for doctree::Import {
3707     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Vec<Item> {
3708         // We consider inlining the documentation of `pub use` statements, but we
3709         // forcefully don't inline if this is not public or if the
3710         // #[doc(no_inline)] attribute is present.
3711         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
3712         let mut denied = !self.vis.node.is_pub() || self.attrs.iter().any(|a| {
3713             a.name() == "doc" && match a.meta_item_list() {
3714                 Some(l) => attr::list_contains_name(&l, "no_inline") ||
3715                            attr::list_contains_name(&l, "hidden"),
3716                 None => false,
3717             }
3718         });
3719         // Also check whether imports were asked to be inlined, in case we're trying to re-export a
3720         // crate in Rust 2018+
3721         let please_inline = self.attrs.lists("doc").has_word("inline");
3722         let path = self.path.clean(cx);
3723         let inner = if self.glob {
3724             if !denied {
3725                 let mut visited = FxHashSet::default();
3726                 if let Some(items) = inline::try_inline_glob(cx, path.def, &mut visited) {
3727                     return items;
3728                 }
3729             }
3730
3731             Import::Glob(resolve_use_source(cx, path))
3732         } else {
3733             let name = self.name;
3734             if !please_inline {
3735                 match path.def {
3736                     Def::Mod(did) => if !did.is_local() && did.index == CRATE_DEF_INDEX {
3737                         // if we're `pub use`ing an extern crate root, don't inline it unless we
3738                         // were specifically asked for it
3739                         denied = true;
3740                     }
3741                     _ => {}
3742                 }
3743             }
3744             if !denied {
3745                 let mut visited = FxHashSet::default();
3746                 if let Some(items) = inline::try_inline(cx, path.def, name, &mut visited) {
3747                     return items;
3748                 }
3749             }
3750             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
3751         };
3752
3753         vec![Item {
3754             name: None,
3755             attrs: self.attrs.clean(cx),
3756             source: self.whence.clean(cx),
3757             def_id: cx.tcx.hir().local_def_id(ast::CRATE_NODE_ID),
3758             visibility: self.vis.clean(cx),
3759             stability: None,
3760             deprecation: None,
3761             inner: ImportItem(inner)
3762         }]
3763     }
3764 }
3765
3766 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3767 pub enum Import {
3768     // use source as str;
3769     Simple(String, ImportSource),
3770     // use source::*;
3771     Glob(ImportSource)
3772 }
3773
3774 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3775 pub struct ImportSource {
3776     pub path: Path,
3777     pub did: Option<DefId>,
3778 }
3779
3780 impl Clean<Vec<Item>> for hir::ForeignMod {
3781     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Vec<Item> {
3782         let mut items = self.items.clean(cx);
3783         for item in &mut items {
3784             if let ForeignFunctionItem(ref mut f) = item.inner {
3785                 f.header.abi = self.abi;
3786             }
3787         }
3788         items
3789     }
3790 }
3791
3792 impl Clean<Item> for hir::ForeignItem {
3793     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
3794         let inner = match self.node {
3795             hir::ForeignItemKind::Fn(ref decl, ref names, ref generics) => {
3796                 let (generics, decl) = enter_impl_trait(cx, || {
3797                     (generics.clean(cx), (&**decl, &names[..]).clean(cx))
3798                 });
3799                 ForeignFunctionItem(Function {
3800                     decl,
3801                     generics,
3802                     header: hir::FnHeader {
3803                         unsafety: hir::Unsafety::Unsafe,
3804                         abi: Abi::Rust,
3805                         constness: hir::Constness::NotConst,
3806                         asyncness: hir::IsAsync::NotAsync,
3807                     },
3808                 })
3809             }
3810             hir::ForeignItemKind::Static(ref ty, mutbl) => {
3811                 ForeignStaticItem(Static {
3812                     type_: ty.clean(cx),
3813                     mutability: if mutbl {Mutable} else {Immutable},
3814                     expr: String::new(),
3815                 })
3816             }
3817             hir::ForeignItemKind::Type => {
3818                 ForeignTypeItem
3819             }
3820         };
3821
3822         Item {
3823             name: Some(self.ident.clean(cx)),
3824             attrs: self.attrs.clean(cx),
3825             source: self.span.clean(cx),
3826             def_id: cx.tcx.hir().local_def_id(self.id),
3827             visibility: self.vis.clean(cx),
3828             stability: get_stability(cx, cx.tcx.hir().local_def_id(self.id)),
3829             deprecation: get_deprecation(cx, cx.tcx.hir().local_def_id(self.id)),
3830             inner,
3831         }
3832     }
3833 }
3834
3835 // Utilities
3836
3837 pub trait ToSource {
3838     fn to_src(&self, cx: &DocContext<'_, '_, '_>) -> String;
3839 }
3840
3841 impl ToSource for syntax_pos::Span {
3842     fn to_src(&self, cx: &DocContext<'_, '_, '_>) -> String {
3843         debug!("converting span {:?} to snippet", self.clean(cx));
3844         let sn = match cx.sess().source_map().span_to_snippet(*self) {
3845             Ok(x) => x,
3846             Err(_) => String::new()
3847         };
3848         debug!("got snippet {}", sn);
3849         sn
3850     }
3851 }
3852
3853 fn name_from_pat(p: &hir::Pat) -> String {
3854     use rustc::hir::*;
3855     debug!("Trying to get a name from pattern: {:?}", p);
3856
3857     match p.node {
3858         PatKind::Wild => "_".to_string(),
3859         PatKind::Binding(_, _, _, ident, _) => ident.to_string(),
3860         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
3861         PatKind::Struct(ref name, ref fields, etc) => {
3862             format!("{} {{ {}{} }}", qpath_to_string(name),
3863                 fields.iter().map(|&Spanned { node: ref fp, .. }|
3864                                   format!("{}: {}", fp.ident, name_from_pat(&*fp.pat)))
3865                              .collect::<Vec<String>>().join(", "),
3866                 if etc { ", .." } else { "" }
3867             )
3868         }
3869         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
3870                                             .collect::<Vec<String>>().join(", ")),
3871         PatKind::Box(ref p) => name_from_pat(&**p),
3872         PatKind::Ref(ref p, _) => name_from_pat(&**p),
3873         PatKind::Lit(..) => {
3874             warn!("tried to get argument name from PatKind::Lit, \
3875                   which is silly in function arguments");
3876             "()".to_string()
3877         },
3878         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
3879                               which is not allowed in function arguments"),
3880         PatKind::Slice(ref begin, ref mid, ref end) => {
3881             let begin = begin.iter().map(|p| name_from_pat(&**p));
3882             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
3883             let end = end.iter().map(|p| name_from_pat(&**p));
3884             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
3885         },
3886     }
3887 }
3888
3889 fn print_const(cx: &DocContext<'_, '_, '_>, n: ty::LazyConst<'_>) -> String {
3890     match n {
3891         ty::LazyConst::Unevaluated(def_id, _) => {
3892             if let Some(node_id) = cx.tcx.hir().as_local_node_id(def_id) {
3893                 print_const_expr(cx, cx.tcx.hir().body_owned_by(node_id))
3894             } else {
3895                 inline::print_inlined_const(cx, def_id)
3896             }
3897         },
3898         ty::LazyConst::Evaluated(n) => {
3899             let mut s = String::new();
3900             ::rustc::mir::fmt_const_val(&mut s, n).expect("fmt_const_val failed");
3901             // array lengths are obviously usize
3902             if s.ends_with("usize") {
3903                 let n = s.len() - "usize".len();
3904                 s.truncate(n);
3905             }
3906             s
3907         },
3908     }
3909 }
3910
3911 fn print_const_expr(cx: &DocContext<'_, '_, '_>, body: hir::BodyId) -> String {
3912     cx.tcx.hir().hir_to_pretty_string(body.hir_id)
3913 }
3914
3915 /// Given a type Path, resolve it to a Type using the TyCtxt
3916 fn resolve_type(cx: &DocContext<'_, '_, '_>,
3917                 path: Path,
3918                 id: hir::HirId) -> Type {
3919     if id == hir::DUMMY_HIR_ID {
3920         debug!("resolve_type({:?})", path);
3921     } else {
3922         debug!("resolve_type({:?},{:?})", path, id);
3923     }
3924
3925     let is_generic = match path.def {
3926         Def::PrimTy(p) => match p {
3927             hir::Str => return Primitive(PrimitiveType::Str),
3928             hir::Bool => return Primitive(PrimitiveType::Bool),
3929             hir::Char => return Primitive(PrimitiveType::Char),
3930             hir::Int(int_ty) => return Primitive(int_ty.into()),
3931             hir::Uint(uint_ty) => return Primitive(uint_ty.into()),
3932             hir::Float(float_ty) => return Primitive(float_ty.into()),
3933         },
3934         Def::SelfTy(..) if path.segments.len() == 1 => {
3935             return Generic(keywords::SelfUpper.name().to_string());
3936         }
3937         Def::TyParam(..) if path.segments.len() == 1 => {
3938             return Generic(format!("{:#}", path));
3939         }
3940         Def::SelfTy(..) | Def::TyParam(..) | Def::AssociatedTy(..) => true,
3941         _ => false,
3942     };
3943     let did = register_def(&*cx, path.def);
3944     ResolvedPath { path: path, typarams: None, did: did, is_generic: is_generic }
3945 }
3946
3947 pub fn register_def(cx: &DocContext<'_, '_, '_>, def: Def) -> DefId {
3948     debug!("register_def({:?})", def);
3949
3950     let (did, kind) = match def {
3951         Def::Fn(i) => (i, TypeKind::Function),
3952         Def::TyAlias(i) => (i, TypeKind::Typedef),
3953         Def::Enum(i) => (i, TypeKind::Enum),
3954         Def::Trait(i) => (i, TypeKind::Trait),
3955         Def::Struct(i) => (i, TypeKind::Struct),
3956         Def::Union(i) => (i, TypeKind::Union),
3957         Def::Mod(i) => (i, TypeKind::Module),
3958         Def::ForeignTy(i) => (i, TypeKind::Foreign),
3959         Def::Const(i) => (i, TypeKind::Const),
3960         Def::Static(i, _) => (i, TypeKind::Static),
3961         Def::Variant(i) => (cx.tcx.parent_def_id(i).expect("cannot get parent def id"),
3962                             TypeKind::Enum),
3963         Def::Macro(i, mac_kind) => match mac_kind {
3964             MacroKind::Bang => (i, TypeKind::Macro),
3965             MacroKind::Attr => (i, TypeKind::Attr),
3966             MacroKind::Derive => (i, TypeKind::Derive),
3967             MacroKind::ProcMacroStub => unreachable!(),
3968         },
3969         Def::TraitAlias(i) => (i, TypeKind::TraitAlias),
3970         Def::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
3971         Def::SelfTy(_, Some(impl_def_id)) => return impl_def_id,
3972         _ => return def.def_id()
3973     };
3974     if did.is_local() { return did }
3975     inline::record_extern_fqn(cx, did, kind);
3976     if let TypeKind::Trait = kind {
3977         inline::record_extern_trait(cx, did);
3978     }
3979     did
3980 }
3981
3982 fn resolve_use_source(cx: &DocContext<'_, '_, '_>, path: Path) -> ImportSource {
3983     ImportSource {
3984         did: if path.def.opt_def_id().is_none() {
3985             None
3986         } else {
3987             Some(register_def(cx, path.def))
3988         },
3989         path,
3990     }
3991 }
3992
3993 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3994 pub struct Macro {
3995     pub source: String,
3996     pub imported_from: Option<String>,
3997 }
3998
3999 impl Clean<Item> for doctree::Macro {
4000     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
4001         let name = self.name.clean(cx);
4002         Item {
4003             name: Some(name.clone()),
4004             attrs: self.attrs.clean(cx),
4005             source: self.whence.clean(cx),
4006             visibility: Some(Public),
4007             stability: self.stab.clean(cx),
4008             deprecation: self.depr.clean(cx),
4009             def_id: self.def_id,
4010             inner: MacroItem(Macro {
4011                 source: format!("macro_rules! {} {{\n{}}}",
4012                                 name,
4013                                 self.matchers.iter().map(|span| {
4014                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
4015                                 }).collect::<String>()),
4016                 imported_from: self.imported_from.clean(cx),
4017             }),
4018         }
4019     }
4020 }
4021
4022 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4023 pub struct ProcMacro {
4024     pub kind: MacroKind,
4025     pub helpers: Vec<String>,
4026 }
4027
4028 impl Clean<Item> for doctree::ProcMacro {
4029     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> Item {
4030         Item {
4031             name: Some(self.name.clean(cx)),
4032             attrs: self.attrs.clean(cx),
4033             source: self.whence.clean(cx),
4034             visibility: Some(Public),
4035             stability: self.stab.clean(cx),
4036             deprecation: self.depr.clean(cx),
4037             def_id: cx.tcx.hir().local_def_id(self.id),
4038             inner: ProcMacroItem(ProcMacro {
4039                 kind: self.kind,
4040                 helpers: self.helpers.clean(cx),
4041             }),
4042         }
4043     }
4044 }
4045
4046 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4047 pub struct Stability {
4048     pub level: stability::StabilityLevel,
4049     pub feature: Option<String>,
4050     pub since: String,
4051     pub deprecation: Option<Deprecation>,
4052     pub unstable_reason: Option<String>,
4053     pub issue: Option<u32>,
4054 }
4055
4056 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4057 pub struct Deprecation {
4058     pub since: Option<String>,
4059     pub note: Option<String>,
4060 }
4061
4062 impl Clean<Stability> for attr::Stability {
4063     fn clean(&self, _: &DocContext<'_, '_, '_>) -> Stability {
4064         Stability {
4065             level: stability::StabilityLevel::from_attr_level(&self.level),
4066             feature: Some(self.feature.to_string()).filter(|f| !f.is_empty()),
4067             since: match self.level {
4068                 attr::Stable {ref since} => since.to_string(),
4069                 _ => String::new(),
4070             },
4071             deprecation: self.rustc_depr.as_ref().map(|d| {
4072                 Deprecation {
4073                     note: Some(d.reason.to_string()).filter(|r| !r.is_empty()),
4074                     since: Some(d.since.to_string()).filter(|d| !d.is_empty()),
4075                 }
4076             }),
4077             unstable_reason: match self.level {
4078                 attr::Unstable { reason: Some(ref reason), .. } => Some(reason.to_string()),
4079                 _ => None,
4080             },
4081             issue: match self.level {
4082                 attr::Unstable {issue, ..} => Some(issue),
4083                 _ => None,
4084             }
4085         }
4086     }
4087 }
4088
4089 impl<'a> Clean<Stability> for &'a attr::Stability {
4090     fn clean(&self, dc: &DocContext<'_, '_, '_>) -> Stability {
4091         (**self).clean(dc)
4092     }
4093 }
4094
4095 impl Clean<Deprecation> for attr::Deprecation {
4096     fn clean(&self, _: &DocContext<'_, '_, '_>) -> Deprecation {
4097         Deprecation {
4098             since: self.since.map(|s| s.to_string()).filter(|s| !s.is_empty()),
4099             note: self.note.map(|n| n.to_string()).filter(|n| !n.is_empty()),
4100         }
4101     }
4102 }
4103
4104 /// An equality constraint on an associated type, e.g., `A = Bar` in `Foo<A = Bar>`
4105 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug, Hash)]
4106 pub struct TypeBinding {
4107     pub name: String,
4108     pub ty: Type
4109 }
4110
4111 impl Clean<TypeBinding> for hir::TypeBinding {
4112     fn clean(&self, cx: &DocContext<'_, '_, '_>) -> TypeBinding {
4113         TypeBinding {
4114             name: self.ident.name.clean(cx),
4115             ty: self.ty.clean(cx)
4116         }
4117     }
4118 }
4119
4120 pub fn def_id_to_path(
4121     cx: &DocContext<'_, '_, '_>,
4122     did: DefId,
4123     name: Option<String>
4124 ) -> Vec<String> {
4125     let crate_name = name.unwrap_or_else(|| cx.tcx.crate_name(did.krate).to_string());
4126     let relative = cx.tcx.def_path(did).data.into_iter().filter_map(|elem| {
4127         // extern blocks have an empty name
4128         let s = elem.data.to_string();
4129         if !s.is_empty() {
4130             Some(s)
4131         } else {
4132             None
4133         }
4134     });
4135     once(crate_name).chain(relative).collect()
4136 }
4137
4138 pub fn enter_impl_trait<F, R>(cx: &DocContext<'_, '_, '_>, f: F) -> R
4139 where
4140     F: FnOnce() -> R,
4141 {
4142     let old_bounds = mem::replace(&mut *cx.impl_trait_bounds.borrow_mut(), Default::default());
4143     let r = f();
4144     assert!(cx.impl_trait_bounds.borrow().is_empty());
4145     *cx.impl_trait_bounds.borrow_mut() = old_bounds;
4146     r
4147 }
4148
4149 // Start of code copied from rust-clippy
4150
4151 pub fn path_to_def_local(tcx: &TyCtxt<'_, '_, '_>, path: &[&str]) -> Option<DefId> {
4152     let krate = tcx.hir().krate();
4153     let mut items = krate.module.item_ids.clone();
4154     let mut path_it = path.iter().peekable();
4155
4156     loop {
4157         let segment = path_it.next()?;
4158
4159         for item_id in mem::replace(&mut items, HirVec::new()).iter() {
4160             let item = tcx.hir().expect_item(item_id.id);
4161             if item.ident.name == *segment {
4162                 if path_it.peek().is_none() {
4163                     return Some(tcx.hir().local_def_id(item_id.id))
4164                 }
4165
4166                 items = match &item.node {
4167                     &hir::ItemKind::Mod(ref m) => m.item_ids.clone(),
4168                     _ => panic!("Unexpected item {:?} in path {:?} path")
4169                 };
4170                 break;
4171             }
4172         }
4173     }
4174 }
4175
4176 pub fn path_to_def(tcx: &TyCtxt<'_, '_, '_>, path: &[&str]) -> Option<DefId> {
4177     let crates = tcx.crates();
4178
4179     let krate = crates
4180         .iter()
4181         .find(|&&krate| tcx.crate_name(krate) == path[0]);
4182
4183     if let Some(krate) = krate {
4184         let krate = DefId {
4185             krate: *krate,
4186             index: CRATE_DEF_INDEX,
4187         };
4188         let mut items = tcx.item_children(krate);
4189         let mut path_it = path.iter().skip(1).peekable();
4190
4191         loop {
4192             let segment = path_it.next()?;
4193
4194             for item in mem::replace(&mut items, Lrc::new(vec![])).iter() {
4195                 if item.ident.name == *segment {
4196                     if path_it.peek().is_none() {
4197                         return match item.def {
4198                             def::Def::Trait(did) => Some(did),
4199                             _ => None,
4200                         }
4201                     }
4202
4203                     items = tcx.item_children(item.def.def_id());
4204                     break;
4205                 }
4206             }
4207         }
4208     } else {
4209         None
4210     }
4211 }
4212
4213 pub fn get_path_for_type<F>(tcx: TyCtxt<'_, '_, '_>, def_id: DefId, def_ctor: F) -> hir::Path
4214 where F: Fn(DefId) -> Def {
4215     #[derive(Debug)]
4216     struct AbsolutePathBuffer {
4217         names: Vec<String>,
4218     }
4219
4220     impl ty::item_path::ItemPathBuffer for AbsolutePathBuffer {
4221         fn root_mode(&self) -> &ty::item_path::RootMode {
4222             const ABSOLUTE: &'static ty::item_path::RootMode = &ty::item_path::RootMode::Absolute;
4223             ABSOLUTE
4224         }
4225
4226         fn push(&mut self, text: &str) {
4227             self.names.push(text.to_owned());
4228         }
4229     }
4230
4231     let mut apb = AbsolutePathBuffer { names: vec![] };
4232
4233     tcx.push_item_path(&mut apb, def_id, false);
4234
4235     hir::Path {
4236         span: DUMMY_SP,
4237         def: def_ctor(def_id),
4238         segments: hir::HirVec::from_vec(apb.names.iter().map(|s| hir::PathSegment {
4239             ident: ast::Ident::from_str(&s),
4240             id: None,
4241             hir_id: None,
4242             def: None,
4243             args: None,
4244             infer_types: false,
4245         }).collect())
4246     }
4247 }
4248
4249 // End of code copied from rust-clippy
4250
4251
4252 #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
4253 enum RegionTarget<'tcx> {
4254     Region(Region<'tcx>),
4255     RegionVid(RegionVid)
4256 }
4257
4258 #[derive(Default, Debug, Clone)]
4259 struct RegionDeps<'tcx> {
4260     larger: FxHashSet<RegionTarget<'tcx>>,
4261     smaller: FxHashSet<RegionTarget<'tcx>>
4262 }
4263
4264 #[derive(Eq, PartialEq, Hash, Debug)]
4265 enum SimpleBound {
4266     TraitBound(Vec<PathSegment>, Vec<SimpleBound>, Vec<GenericParamDef>, hir::TraitBoundModifier),
4267     Outlives(Lifetime),
4268 }
4269
4270 enum AutoTraitResult {
4271     ExplicitImpl,
4272     PositiveImpl(Generics),
4273     NegativeImpl,
4274 }
4275
4276 impl AutoTraitResult {
4277     fn is_auto(&self) -> bool {
4278         match *self {
4279             AutoTraitResult::PositiveImpl(_) | AutoTraitResult::NegativeImpl => true,
4280             _ => false,
4281         }
4282     }
4283 }
4284
4285 impl From<GenericBound> for SimpleBound {
4286     fn from(bound: GenericBound) -> Self {
4287         match bound.clone() {
4288             GenericBound::Outlives(l) => SimpleBound::Outlives(l),
4289             GenericBound::TraitBound(t, mod_) => match t.trait_ {
4290                 Type::ResolvedPath { path, typarams, .. } => {
4291                     SimpleBound::TraitBound(path.segments,
4292                                             typarams
4293                                                 .map_or_else(|| Vec::new(), |v| v.iter()
4294                                                         .map(|p| SimpleBound::from(p.clone()))
4295                                                         .collect()),
4296                                             t.generic_params,
4297                                             mod_)
4298                 }
4299                 _ => panic!("Unexpected bound {:?}", bound),
4300             }
4301         }
4302     }
4303 }