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