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