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