src/librustdoc/clean/mod.rs

   1 //! This module contains the "cleaned" pieces of the AST, and the functions
   2 //! that clean them.
   3
   4 pub mod inline;
   5 pub mod cfg;
   6 mod simplify;
   7 mod auto_trait;
   8 mod blanket_impl;
   9 pub mod def_ctor;
  10
  11 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
  12 use rustc_data_structures::sync::Lrc;
  13 use rustc_target::spec::abi::Abi;
  14 use rustc_typeck::hir_ty_to_ty;
  15 use rustc::infer::region_constraints::{RegionConstraintData, Constraint};
  16 use rustc::middle::resolve_lifetime as rl;
  17 use rustc::middle::lang_items;
  18 use rustc::middle::stability;
  19 use rustc::mir::interpret::GlobalId;
  20 use rustc::hir::{self, GenericArg, HirVec};
  21 use rustc::hir::def::{self, Def, CtorKind};
  22 use rustc::hir::def_id::{CrateNum, DefId, CRATE_DEF_INDEX, LOCAL_CRATE};
  23 use rustc::ty::subst::Substs;
  24 use rustc::ty::{self, TyCtxt, Region, RegionVid, Ty, AdtKind};
  25 use rustc::ty::fold::TypeFolder;
  26 use rustc::ty::layout::VariantIdx;
  27 use rustc::util::nodemap::{FxHashMap, FxHashSet};
  28 use syntax::ast::{self, AttrStyle, Ident};
  29 use syntax::attr;
  30 use syntax::ext::base::MacroKind;
  31 use syntax::source_map::{dummy_spanned, Spanned};
  32 use syntax::ptr::P;
  33 use syntax::symbol::keywords::{self, Keyword};
  34 use syntax::symbol::InternedString;
  35 use syntax_pos::{self, DUMMY_SP, Pos, FileName};
  36
  37 use std::collections::hash_map::Entry;
  38 use std::fmt;
  39 use std::hash::{Hash, Hasher};
  40 use std::default::Default;
  41 use std::{mem, slice, vec};
  42 use std::iter::{FromIterator, once};
  43 use std::rc::Rc;
  44 use std::str::FromStr;
  45 use std::cell::RefCell;
  46 use std::sync::Arc;
  47 use std::u32;
  48
  49 use parking_lot::ReentrantMutex;
  50
  51 use core::{self, DocContext};
  52 use doctree;
  53 use visit_ast;
  54 use html::render::{cache, ExternalLocation};
  55 use html::item_type::ItemType;
  56
  57 use self::cfg::Cfg;
  58 use self::auto_trait::AutoTraitFinder;
  59 use self::blanket_impl::BlanketImplFinder;
  60
  61 pub use self::Type::*;
  62 pub use self::Mutability::*;
  63 pub use self::ItemEnum::*;
  64 pub use self::SelfTy::*;
  65 pub use self::FunctionRetTy::*;
  66 pub use self::Visibility::{Public, Inherited};
  67
  68 thread_local!(pub static MAX_DEF_ID: RefCell<FxHashMap<CrateNum, DefId>> = Default::default());
  69
  70 const FN_OUTPUT_NAME: &'static str = "Output";
  71
  72 // extract the stability index for a node from tcx, if possible
  73 fn get_stability(cx: &DocContext, def_id: DefId) -> Option<Stability> {
  74     cx.tcx.lookup_stability(def_id).clean(cx)
  75 }
  76
  77 fn get_deprecation(cx: &DocContext, def_id: DefId) -> Option<Deprecation> {
  78     cx.tcx.lookup_deprecation(def_id).clean(cx)
  79 }
  80
  81 pub trait Clean<T> {
  82     fn clean(&self, cx: &DocContext) -> T;
  83 }
  84
  85 impl<T: Clean<U>, U> Clean<Vec<U>> for [T] {
  86     fn clean(&self, cx: &DocContext) -> Vec<U> {
  87         self.iter().map(|x| x.clean(cx)).collect()
  88     }
  89 }
  90
  91 impl<T: Clean<U>, U, V: Idx> Clean<IndexVec<V, U>> for IndexVec<V, T> {
  92     fn clean(&self, cx: &DocContext) -> IndexVec<V, U> {
  93         self.iter().map(|x| x.clean(cx)).collect()
  94     }
  95 }
  96
  97 impl<T: Clean<U>, U> Clean<U> for P<T> {
  98     fn clean(&self, cx: &DocContext) -> U {
  99         (**self).clean(cx)
 100     }
 101 }
 102
 103 impl<T: Clean<U>, U> Clean<U> for Rc<T> {
 104     fn clean(&self, cx: &DocContext) -> U {
 105         (**self).clean(cx)
 106     }
 107 }
 108
 109 impl<T: Clean<U>, U> Clean<Option<U>> for Option<T> {
 110     fn clean(&self, cx: &DocContext) -> Option<U> {
 111         self.as_ref().map(|v| v.clean(cx))
 112     }
 113 }
 114
 115 impl<T, U> Clean<U> for ty::Binder<T> where T: Clean<U> {
 116     fn clean(&self, cx: &DocContext) -> U {
 117         self.skip_binder().clean(cx)
 118     }
 119 }
 120
 121 impl<T: Clean<U>, U> Clean<Vec<U>> for P<[T]> {
 122     fn clean(&self, cx: &DocContext) -> Vec<U> {
 123         self.iter().map(|x| x.clean(cx)).collect()
 124     }
 125 }
 126
 127 #[derive(Clone, Debug)]
 128 pub struct Crate {
 129     pub name: String,
 130     pub version: Option<String>,
 131     pub src: FileName,
 132     pub module: Option<Item>,
 133     pub externs: Vec<(CrateNum, ExternalCrate)>,
 134     pub primitives: Vec<(DefId, PrimitiveType, Attributes)>,
 135     // These are later on moved into `CACHEKEY`, leaving the map empty.
 136     // Only here so that they can be filtered through the rustdoc passes.
 137     pub external_traits: Arc<ReentrantMutex<RefCell<FxHashMap<DefId, Trait>>>>,
 138     pub masked_crates: FxHashSet<CrateNum>,
 139 }
 140
 141 impl<'a, 'tcx, 'rcx> Clean<Crate> for visit_ast::RustdocVisitor<'a, 'tcx, 'rcx> {
 142     fn clean(&self, cx: &DocContext) -> Crate {
 143         use ::visit_lib::LibEmbargoVisitor;
 144
 145         {
 146             let mut r = cx.renderinfo.borrow_mut();
 147             r.deref_trait_did = cx.tcx.lang_items().deref_trait();
 148             r.deref_mut_trait_did = cx.tcx.lang_items().deref_mut_trait();
 149             r.owned_box_did = cx.tcx.lang_items().owned_box();
 150         }
 151
 152         let mut externs = Vec::new();
 153         for &cnum in cx.tcx.crates().iter() {
 154             externs.push((cnum, cnum.clean(cx)));
 155             // Analyze doc-reachability for extern items
 156             LibEmbargoVisitor::new(cx).visit_lib(cnum);
 157         }
 158         externs.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
 159
 160         // Clean the crate, translating the entire libsyntax AST to one that is
 161         // understood by rustdoc.
 162         let mut module = self.module.clean(cx);
 163         let mut masked_crates = FxHashSet::default();
 164
 165         match module.inner {
 166             ModuleItem(ref module) => {
 167                 for it in &module.items {
 168                     // `compiler_builtins` should be masked too, but we can't apply
 169                     // `#[doc(masked)]` to the injected `extern crate` because it's unstable.
 170                     if it.is_extern_crate()
 171                         && (it.attrs.has_doc_flag("masked")
 172                             || self.cx.tcx.is_compiler_builtins(it.def_id.krate))
 173                     {
 174                         masked_crates.insert(it.def_id.krate);
 175                     }
 176                 }
 177             }
 178             _ => unreachable!(),
 179         }
 180
 181         let ExternalCrate { name, src, primitives, keywords, .. } = LOCAL_CRATE.clean(cx);
 182         {
 183             let m = match module.inner {
 184                 ModuleItem(ref mut m) => m,
 185                 _ => unreachable!(),
 186             };
 187             m.items.extend(primitives.iter().map(|&(def_id, prim, ref attrs)| {
 188                 Item {
 189                     source: Span::empty(),
 190                     name: Some(prim.to_url_str().to_string()),
 191                     attrs: attrs.clone(),
 192                     visibility: Some(Public),
 193                     stability: get_stability(cx, def_id),
 194                     deprecation: get_deprecation(cx, def_id),
 195                     def_id,
 196                     inner: PrimitiveItem(prim),
 197                 }
 198             }));
 199             m.items.extend(keywords.into_iter().map(|(def_id, kw, attrs)| {
 200                 Item {
 201                     source: Span::empty(),
 202                     name: Some(kw.clone()),
 203                     attrs: attrs,
 204                     visibility: Some(Public),
 205                     stability: get_stability(cx, def_id),
 206                     deprecation: get_deprecation(cx, def_id),
 207                     def_id,
 208                     inner: KeywordItem(kw),
 209                 }
 210             }));
 211         }
 212
 213         Crate {
 214             name,
 215             version: None,
 216             src,
 217             module: Some(module),
 218             externs,
 219             primitives,
 220             external_traits: cx.external_traits.clone(),
 221             masked_crates,
 222         }
 223     }
 224 }
 225
 226 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
 227 pub struct ExternalCrate {
 228     pub name: String,
 229     pub src: FileName,
 230     pub attrs: Attributes,
 231     pub primitives: Vec<(DefId, PrimitiveType, Attributes)>,
 232     pub keywords: Vec<(DefId, String, Attributes)>,
 233 }
 234
 235 impl Clean<ExternalCrate> for CrateNum {
 236     fn clean(&self, cx: &DocContext) -> ExternalCrate {
 237         let root = DefId { krate: *self, index: CRATE_DEF_INDEX };
 238         let krate_span = cx.tcx.def_span(root);
 239         let krate_src = cx.sess().source_map().span_to_filename(krate_span);
 240
 241         // Collect all inner modules which are tagged as implementations of
 242         // primitives.
 243         //
 244         // Note that this loop only searches the top-level items of the crate,
 245         // and this is intentional. If we were to search the entire crate for an
 246         // item tagged with `#[doc(primitive)]` then we would also have to
 247         // search the entirety of external modules for items tagged
 248         // `#[doc(primitive)]`, which is a pretty inefficient process (decoding
 249         // all that metadata unconditionally).
 250         //
 251         // In order to keep the metadata load under control, the
 252         // `#[doc(primitive)]` feature is explicitly designed to only allow the
 253         // primitive tags to show up as the top level items in a crate.
 254         //
 255         // Also note that this does not attempt to deal with modules tagged
 256         // duplicately for the same primitive. This is handled later on when
 257         // rendering by delegating everything to a hash map.
 258         let as_primitive = |def: Def| {
 259             if let Def::Mod(def_id) = def {
 260                 let attrs = cx.tcx.get_attrs(def_id).clean(cx);
 261                 let mut prim = None;
 262                 for attr in attrs.lists("doc") {
 263                     if let Some(v) = attr.value_str() {
 264                         if attr.check_name("primitive") {
 265                             prim = PrimitiveType::from_str(&v.as_str());
 266                             if prim.is_some() {
 267                                 break;
 268                             }
 269                             // FIXME: should warn on unknown primitives?
 270                         }
 271                     }
 272                 }
 273                 return prim.map(|p| (def_id, p, attrs));
 274             }
 275             None
 276         };
 277         let primitives = if root.is_local() {
 278             cx.tcx.hir().krate().module.item_ids.iter().filter_map(|&id| {
 279                 let item = cx.tcx.hir().expect_item(id.id);
 280                 match item.node {
 281                     hir::ItemKind::Mod(_) => {
 282                         as_primitive(Def::Mod(cx.tcx.hir().local_def_id(id.id)))
 283                     }
 284                     hir::ItemKind::Use(ref path, hir::UseKind::Single)
 285                     if item.vis.node.is_pub() => {
 286                         as_primitive(path.def).map(|(_, prim, attrs)| {
 287                             // Pretend the primitive is local.
 288                             (cx.tcx.hir().local_def_id(id.id), prim, attrs)
 289                         })
 290                     }
 291                     _ => None
 292                 }
 293             }).collect()
 294         } else {
 295             cx.tcx.item_children(root).iter().map(|item| item.def)
 296               .filter_map(as_primitive).collect()
 297         };
 298
 299         let as_keyword = |def: Def| {
 300             if let Def::Mod(def_id) = def {
 301                 let attrs = cx.tcx.get_attrs(def_id).clean(cx);
 302                 let mut keyword = None;
 303                 for attr in attrs.lists("doc") {
 304                     if let Some(v) = attr.value_str() {
 305                         if attr.check_name("keyword") {
 306                             keyword = Keyword::from_str(&v.as_str()).ok()
 307                                                                     .map(|x| x.name().to_string());
 308                             if keyword.is_some() {
 309                                 break
 310                             }
 311                             // FIXME: should warn on unknown keywords?
 312                         }
 313                     }
 314                 }
 315                 return keyword.map(|p| (def_id, p, attrs));
 316             }
 317             None
 318         };
 319         let keywords = if root.is_local() {
 320             cx.tcx.hir().krate().module.item_ids.iter().filter_map(|&id| {
 321                 let item = cx.tcx.hir().expect_item(id.id);
 322                 match item.node {
 323                     hir::ItemKind::Mod(_) => {
 324                         as_keyword(Def::Mod(cx.tcx.hir().local_def_id(id.id)))
 325                     }
 326                     hir::ItemKind::Use(ref path, hir::UseKind::Single)
 327                     if item.vis.node.is_pub() => {
 328                         as_keyword(path.def).map(|(_, prim, attrs)| {
 329                             (cx.tcx.hir().local_def_id(id.id), prim, attrs)
 330                         })
 331                     }
 332                     _ => None
 333                 }
 334             }).collect()
 335         } else {
 336             cx.tcx.item_children(root).iter().map(|item| item.def)
 337               .filter_map(as_keyword).collect()
 338         };
 339
 340         ExternalCrate {
 341             name: cx.tcx.crate_name(*self).to_string(),
 342             src: krate_src,
 343             attrs: cx.tcx.get_attrs(root).clean(cx),
 344             primitives,
 345             keywords,
 346         }
 347     }
 348 }
 349
 350 /// Anything with a source location and set of attributes and, optionally, a
 351 /// name. That is, anything that can be documented. This doesn't correspond
 352 /// directly to the AST's concept of an item; it's a strict superset.
 353 #[derive(Clone, RustcEncodable, RustcDecodable)]
 354 pub struct Item {
 355     /// Stringified span
 356     pub source: Span,
 357     /// Not everything has a name. E.g., impls
 358     pub name: Option<String>,
 359     pub attrs: Attributes,
 360     pub inner: ItemEnum,
 361     pub visibility: Option<Visibility>,
 362     pub def_id: DefId,
 363     pub stability: Option<Stability>,
 364     pub deprecation: Option<Deprecation>,
 365 }
 366
 367 impl fmt::Debug for Item {
 368     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 369
 370         let fake = MAX_DEF_ID.with(|m| m.borrow().get(&self.def_id.krate)
 371                                    .map(|id| self.def_id >= *id).unwrap_or(false));
 372         let def_id: &dyn fmt::Debug = if fake { &"**FAKE**" } else { &self.def_id };
 373
 374         fmt.debug_struct("Item")
 375             .field("source", &self.source)
 376             .field("name", &self.name)
 377             .field("attrs", &self.attrs)
 378             .field("inner", &self.inner)
 379             .field("visibility", &self.visibility)
 380             .field("def_id", def_id)
 381             .field("stability", &self.stability)
 382             .field("deprecation", &self.deprecation)
 383             .finish()
 384     }
 385 }
 386
 387 impl Item {
 388     /// Finds the `doc` attribute as a NameValue and returns the corresponding
 389     /// value found.
 390     pub fn doc_value<'a>(&'a self) -> Option<&'a str> {
 391         self.attrs.doc_value()
 392     }
 393     /// Finds all `doc` attributes as NameValues and returns their corresponding values, joined
 394     /// with newlines.
 395     pub fn collapsed_doc_value(&self) -> Option<String> {
 396         self.attrs.collapsed_doc_value()
 397     }
 398
 399     pub fn links(&self) -> Vec<(String, String)> {
 400         self.attrs.links(&self.def_id.krate)
 401     }
 402
 403     pub fn is_crate(&self) -> bool {
 404         match self.inner {
 405             StrippedItem(box ModuleItem(Module { is_crate: true, ..})) |
 406             ModuleItem(Module { is_crate: true, ..}) => true,
 407             _ => false,
 408         }
 409     }
 410     pub fn is_mod(&self) -> bool {
 411         self.type_() == ItemType::Module
 412     }
 413     pub fn is_trait(&self) -> bool {
 414         self.type_() == ItemType::Trait
 415     }
 416     pub fn is_struct(&self) -> bool {
 417         self.type_() == ItemType::Struct
 418     }
 419     pub fn is_enum(&self) -> bool {
 420         self.type_() == ItemType::Enum
 421     }
 422     pub fn is_associated_type(&self) -> bool {
 423         self.type_() == ItemType::AssociatedType
 424     }
 425     pub fn is_associated_const(&self) -> bool {
 426         self.type_() == ItemType::AssociatedConst
 427     }
 428     pub fn is_method(&self) -> bool {
 429         self.type_() == ItemType::Method
 430     }
 431     pub fn is_ty_method(&self) -> bool {
 432         self.type_() == ItemType::TyMethod
 433     }
 434     pub fn is_typedef(&self) -> bool {
 435         self.type_() == ItemType::Typedef
 436     }
 437     pub fn is_primitive(&self) -> bool {
 438         self.type_() == ItemType::Primitive
 439     }
 440     pub fn is_union(&self) -> bool {
 441         self.type_() == ItemType::Union
 442     }
 443     pub fn is_import(&self) -> bool {
 444         self.type_() == ItemType::Import
 445     }
 446     pub fn is_extern_crate(&self) -> bool {
 447         self.type_() == ItemType::ExternCrate
 448     }
 449     pub fn is_keyword(&self) -> bool {
 450         self.type_() == ItemType::Keyword
 451     }
 452
 453     pub fn is_stripped(&self) -> bool {
 454         match self.inner { StrippedItem(..) => true, _ => false }
 455     }
 456     pub fn has_stripped_fields(&self) -> Option<bool> {
 457         match self.inner {
 458             StructItem(ref _struct) => Some(_struct.fields_stripped),
 459             UnionItem(ref union) => Some(union.fields_stripped),
 460             VariantItem(Variant { kind: VariantKind::Struct(ref vstruct)} ) => {
 461                 Some(vstruct.fields_stripped)
 462             },
 463             _ => None,
 464         }
 465     }
 466
 467     pub fn stability_class(&self) -> Option<String> {
 468         self.stability.as_ref().and_then(|ref s| {
 469             let mut classes = Vec::with_capacity(2);
 470
 471             if s.level == stability::Unstable {
 472                 classes.push("unstable");
 473             }
 474
 475             if s.deprecation.is_some() {
 476                 classes.push("deprecated");
 477             }
 478
 479             if classes.len() != 0 {
 480                 Some(classes.join(" "))
 481             } else {
 482                 None
 483             }
 484         })
 485     }
 486
 487     pub fn stable_since(&self) -> Option<&str> {
 488         self.stability.as_ref().map(|s| &s.since[..])
 489     }
 490
 491     pub fn is_non_exhaustive(&self) -> bool {
 492         self.attrs.other_attrs.iter()
 493             .any(|a| a.name().as_str() == "non_exhaustive")
 494     }
 495
 496     /// Returns a documentation-level item type from the item.
 497     pub fn type_(&self) -> ItemType {
 498         ItemType::from(self)
 499     }
 500
 501     /// Returns the info in the item's `#[deprecated]` or `#[rustc_deprecated]` attributes.
 502     ///
 503     /// If the item is not deprecated, returns `None`.
 504     pub fn deprecation(&self) -> Option<&Deprecation> {
 505         self.deprecation
 506             .as_ref()
 507             .or_else(|| self.stability.as_ref().and_then(|s| s.deprecation.as_ref()))
 508     }
 509 }
 510
 511 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
 512 pub enum ItemEnum {
 513     ExternCrateItem(String, Option<String>),
 514     ImportItem(Import),
 515     StructItem(Struct),
 516     UnionItem(Union),
 517     EnumItem(Enum),
 518     FunctionItem(Function),
 519     ModuleItem(Module),
 520     TypedefItem(Typedef, bool /* is associated type */),
 521     ExistentialItem(Existential, bool /* is associated type */),
 522     StaticItem(Static),
 523     ConstantItem(Constant),
 524     TraitItem(Trait),
 525     TraitAliasItem(TraitAlias),
 526     ImplItem(Impl),
 527     /// A method signature only. Used for required methods in traits (ie,
 528     /// non-default-methods).
 529     TyMethodItem(TyMethod),
 530     /// A method with a body.
 531     MethodItem(Method),
 532     StructFieldItem(Type),
 533     VariantItem(Variant),
 534     /// `fn`s from an extern block
 535     ForeignFunctionItem(Function),
 536     /// `static`s from an extern block
 537     ForeignStaticItem(Static),
 538     /// `type`s from an extern block
 539     ForeignTypeItem,
 540     MacroItem(Macro),
 541     ProcMacroItem(ProcMacro),
 542     PrimitiveItem(PrimitiveType),
 543     AssociatedConstItem(Type, Option<String>),
 544     AssociatedTypeItem(Vec<GenericBound>, Option<Type>),
 545     /// An item that has been stripped by a rustdoc pass
 546     StrippedItem(Box<ItemEnum>),
 547     KeywordItem(String),
 548 }
 549
 550 impl ItemEnum {
 551     pub fn generics(&self) -> Option<&Generics> {
 552         Some(match *self {
 553             ItemEnum::StructItem(ref s) => &s.generics,
 554             ItemEnum::EnumItem(ref e) => &e.generics,
 555             ItemEnum::FunctionItem(ref f) => &f.generics,
 556             ItemEnum::TypedefItem(ref t, _) => &t.generics,
 557             ItemEnum::ExistentialItem(ref t, _) => &t.generics,
 558             ItemEnum::TraitItem(ref t) => &t.generics,
 559             ItemEnum::ImplItem(ref i) => &i.generics,
 560             ItemEnum::TyMethodItem(ref i) => &i.generics,
 561             ItemEnum::MethodItem(ref i) => &i.generics,
 562             ItemEnum::ForeignFunctionItem(ref f) => &f.generics,
 563             ItemEnum::TraitAliasItem(ref ta) => &ta.generics,
 564             _ => return None,
 565         })
 566     }
 567
 568     pub fn is_associated(&self) -> bool {
 569         match *self {
 570             ItemEnum::TypedefItem(_, _) |
 571             ItemEnum::AssociatedTypeItem(_, _) => true,
 572             _ => false,
 573         }
 574     }
 575 }
 576
 577 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
 578 pub struct Module {
 579     pub items: Vec<Item>,
 580     pub is_crate: bool,
 581 }
 582
 583 impl Clean<Item> for doctree::Module {
 584     fn clean(&self, cx: &DocContext) -> Item {
 585         let name = if self.name.is_some() {
 586             self.name.expect("No name provided").clean(cx)
 587         } else {
 588             String::new()
 589         };
 590
 591         // maintain a stack of mod ids, for doc comment path resolution
 592         // but we also need to resolve the module's own docs based on whether its docs were written
 593         // inside or outside the module, so check for that
 594         let attrs = self.attrs.clean(cx);
 595
 596         let mut items: Vec<Item> = vec![];
 597         items.extend(self.extern_crates.iter().flat_map(|x| x.clean(cx)));
 598         items.extend(self.imports.iter().flat_map(|x| x.clean(cx)));
 599         items.extend(self.structs.iter().map(|x| x.clean(cx)));
 600         items.extend(self.unions.iter().map(|x| x.clean(cx)));
 601         items.extend(self.enums.iter().map(|x| x.clean(cx)));
 602         items.extend(self.fns.iter().map(|x| x.clean(cx)));
 603         items.extend(self.foreigns.iter().flat_map(|x| x.clean(cx)));
 604         items.extend(self.mods.iter().map(|x| x.clean(cx)));
 605         items.extend(self.typedefs.iter().map(|x| x.clean(cx)));
 606         items.extend(self.existentials.iter().map(|x| x.clean(cx)));
 607         items.extend(self.statics.iter().map(|x| x.clean(cx)));
 608         items.extend(self.constants.iter().map(|x| x.clean(cx)));
 609         items.extend(self.traits.iter().map(|x| x.clean(cx)));
 610         items.extend(self.impls.iter().flat_map(|x| x.clean(cx)));
 611         items.extend(self.macros.iter().map(|x| x.clean(cx)));
 612         items.extend(self.proc_macros.iter().map(|x| x.clean(cx)));
 613         items.extend(self.trait_aliases.iter().map(|x| x.clean(cx)));
 614
 615         // determine if we should display the inner contents or
 616         // the outer `mod` item for the source code.
 617         let whence = {
 618             let cm = cx.sess().source_map();
 619             let outer = cm.lookup_char_pos(self.where_outer.lo());
 620             let inner = cm.lookup_char_pos(self.where_inner.lo());
 621             if outer.file.start_pos == inner.file.start_pos {
 622                 // mod foo { ... }
 623                 self.where_outer
 624             } else {
 625                 // mod foo; (and a separate SourceFile for the contents)
 626                 self.where_inner
 627             }
 628         };
 629
 630         Item {
 631             name: Some(name),
 632             attrs,
 633             source: whence.clean(cx),
 634             visibility: self.vis.clean(cx),
 635             stability: self.stab.clean(cx),
 636             deprecation: self.depr.clean(cx),
 637             def_id: cx.tcx.hir().local_def_id(self.id),
 638             inner: ModuleItem(Module {
 639                is_crate: self.is_crate,
 640                items,
 641             })
 642         }
 643     }
 644 }
 645
 646 pub struct ListAttributesIter<'a> {
 647     attrs: slice::Iter<'a, ast::Attribute>,
 648     current_list: vec::IntoIter<ast::NestedMetaItem>,
 649     name: &'a str
 650 }
 651
 652 impl<'a> Iterator for ListAttributesIter<'a> {
 653     type Item = ast::NestedMetaItem;
 654
 655     fn next(&mut self) -> Option<Self::Item> {
 656         if let Some(nested) = self.current_list.next() {
 657             return Some(nested);
 658         }
 659
 660         for attr in &mut self.attrs {
 661             if let Some(list) = attr.meta_item_list() {
 662                 if attr.check_name(self.name) {
 663                     self.current_list = list.into_iter();
 664                     if let Some(nested) = self.current_list.next() {
 665                         return Some(nested);
 666                     }
 667                 }
 668             }
 669         }
 670
 671         None
 672     }
 673
 674     fn size_hint(&self) -> (usize, Option<usize>) {
 675         let lower = self.current_list.len();
 676         (lower, None)
 677     }
 678 }
 679
 680 pub trait AttributesExt {
 681     /// Finds an attribute as List and returns the list of attributes nested inside.
 682     fn lists<'a>(&'a self, name: &'a str) -> ListAttributesIter<'a>;
 683 }
 684
 685 impl AttributesExt for [ast::Attribute] {
 686     fn lists<'a>(&'a self, name: &'a str) -> ListAttributesIter<'a> {
 687         ListAttributesIter {
 688             attrs: self.iter(),
 689             current_list: Vec::new().into_iter(),
 690             name,
 691         }
 692     }
 693 }
 694
 695 pub trait NestedAttributesExt {
 696     /// Returns `true` if the attribute list contains a specific `Word`
 697     fn has_word(self, word: &str) -> bool;
 698 }
 699
 700 impl<I: IntoIterator<Item=ast::NestedMetaItem>> NestedAttributesExt for I {
 701     fn has_word(self, word: &str) -> bool {
 702         self.into_iter().any(|attr| attr.is_word() && attr.check_name(word))
 703     }
 704 }
 705
 706 /// A portion of documentation, extracted from a `#[doc]` attribute.
 707 ///
 708 /// Each variant contains the line number within the complete doc-comment where the fragment
 709 /// starts, as well as the Span where the corresponding doc comment or attribute is located.
 710 ///
 711 /// Included files are kept separate from inline doc comments so that proper line-number
 712 /// information can be given when a doctest fails. Sugared doc comments and "raw" doc comments are
 713 /// kept separate because of issue #42760.
 714 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
 715 pub enum DocFragment {
 716     /// A doc fragment created from a `///` or `//!` doc comment.
 717     SugaredDoc(usize, syntax_pos::Span, String),
 718     /// A doc fragment created from a "raw" `#[doc=""]` attribute.
 719     RawDoc(usize, syntax_pos::Span, String),
 720     /// A doc fragment created from a `#[doc(include="filename")]` attribute. Contains both the
 721     /// given filename and the file contents.
 722     Include(usize, syntax_pos::Span, String, String),
 723 }
 724
 725 impl DocFragment {
 726     pub fn as_str(&self) -> &str {
 727         match *self {
 728             DocFragment::SugaredDoc(_, _, ref s) => &s[..],
 729             DocFragment::RawDoc(_, _, ref s) => &s[..],
 730             DocFragment::Include(_, _, _, ref s) => &s[..],
 731         }
 732     }
 733
 734     pub fn span(&self) -> syntax_pos::Span {
 735         match *self {
 736             DocFragment::SugaredDoc(_, span, _) |
 737                 DocFragment::RawDoc(_, span, _) |
 738                 DocFragment::Include(_, span, _, _) => span,
 739         }
 740     }
 741 }
 742
 743 impl<'a> FromIterator<&'a DocFragment> for String {
 744     fn from_iter<T>(iter: T) -> Self
 745     where
 746         T: IntoIterator<Item = &'a DocFragment>
 747     {
 748         iter.into_iter().fold(String::new(), |mut acc, frag| {
 749             if !acc.is_empty() {
 750                 acc.push('\n');
 751             }
 752             match *frag {
 753                 DocFragment::SugaredDoc(_, _, ref docs)
 754                     | DocFragment::RawDoc(_, _, ref docs)
 755                     | DocFragment::Include(_, _, _, ref docs) =>
 756                     acc.push_str(docs),
 757             }
 758
 759             acc
 760         })
 761     }
 762 }
 763
 764 #[derive(Clone, RustcEncodable, RustcDecodable, Debug, Default)]
 765 pub struct Attributes {
 766     pub doc_strings: Vec<DocFragment>,
 767     pub other_attrs: Vec<ast::Attribute>,
 768     pub cfg: Option<Arc<Cfg>>,
 769     pub span: Option<syntax_pos::Span>,
 770     /// map from Rust paths to resolved defs and potential URL fragments
 771     pub links: Vec<(String, Option<DefId>, Option<String>)>,
 772     pub inner_docs: bool,
 773 }
 774
 775 impl Attributes {
 776     /// Extracts the content from an attribute `#[doc(cfg(content))]`.
 777     fn extract_cfg(mi: &ast::MetaItem) -> Option<&ast::MetaItem> {
 778         use syntax::ast::NestedMetaItemKind::MetaItem;
 779
 780         if let ast::MetaItemKind::List(ref nmis) = mi.node {
 781             if nmis.len() == 1 {
 782                 if let MetaItem(ref cfg_mi) = nmis[0].node {
 783                     if cfg_mi.check_name("cfg") {
 784                         if let ast::MetaItemKind::List(ref cfg_nmis) = cfg_mi.node {
 785                             if cfg_nmis.len() == 1 {
 786                                 if let MetaItem(ref content_mi) = cfg_nmis[0].node {
 787                                     return Some(content_mi);
 788                                 }
 789                             }
 790                         }
 791                     }
 792                 }
 793             }
 794         }
 795
 796         None
 797     }
 798
 799     /// Reads a `MetaItem` from within an attribute, looks for whether it is a
 800     /// `#[doc(include="file")]`, and returns the filename and contents of the file as loaded from
 801     /// its expansion.
 802     fn extract_include(mi: &ast::MetaItem)
 803         -> Option<(String, String)>
 804     {
 805         mi.meta_item_list().and_then(|list| {
 806             for meta in list {
 807                 if meta.check_name("include") {
 808                     // the actual compiled `#[doc(include="filename")]` gets expanded to
 809                     // `#[doc(include(file="filename", contents="file contents")]` so we need to
 810                     // look for that instead
 811                     return meta.meta_item_list().and_then(|list| {
 812                         let mut filename: Option<String> = None;
 813                         let mut contents: Option<String> = None;
 814
 815                         for it in list {
 816                             if it.check_name("file") {
 817                                 if let Some(name) = it.value_str() {
 818                                     filename = Some(name.to_string());
 819                                 }
 820                             } else if it.check_name("contents") {
 821                                 if let Some(docs) = it.value_str() {
 822                                     contents = Some(docs.to_string());
 823                                 }
 824                             }
 825                         }
 826
 827                         if let (Some(filename), Some(contents)) = (filename, contents) {
 828                             Some((filename, contents))
 829                         } else {
 830                             None
 831                         }
 832                     });
 833                 }
 834             }
 835
 836             None
 837         })
 838     }
 839
 840     pub fn has_doc_flag(&self, flag: &str) -> bool {
 841         for attr in &self.other_attrs {
 842             if !attr.check_name("doc") { continue; }
 843
 844             if let Some(items) = attr.meta_item_list() {
 845                 if items.iter().filter_map(|i| i.meta_item()).any(|it| it.check_name(flag)) {
 846                     return true;
 847                 }
 848             }
 849         }
 850
 851         false
 852     }
 853
 854     pub fn from_ast(diagnostic: &::errors::Handler,
 855                     attrs: &[ast::Attribute]) -> Attributes {
 856         let mut doc_strings = vec![];
 857         let mut sp = None;
 858         let mut cfg = Cfg::True;
 859         let mut doc_line = 0;
 860
 861         let other_attrs = attrs.iter().filter_map(|attr| {
 862             attr.with_desugared_doc(|attr| {
 863                 if attr.check_name("doc") {
 864                     if let Some(mi) = attr.meta() {
 865                         if let Some(value) = mi.value_str() {
 866                             // Extracted #[doc = "..."]
 867                             let value = value.to_string();
 868                             let line = doc_line;
 869                             doc_line += value.lines().count();
 870
 871                             if attr.is_sugared_doc {
 872                                 doc_strings.push(DocFragment::SugaredDoc(line, attr.span, value));
 873                             } else {
 874                                 doc_strings.push(DocFragment::RawDoc(line, attr.span, value));
 875                             }
 876
 877                             if sp.is_none() {
 878                                 sp = Some(attr.span);
 879                             }
 880                             return None;
 881                         } else if let Some(cfg_mi) = Attributes::extract_cfg(&mi) {
 882                             // Extracted #[doc(cfg(...))]
 883                             match Cfg::parse(cfg_mi) {
 884                                 Ok(new_cfg) => cfg &= new_cfg,
 885                                 Err(e) => diagnostic.span_err(e.span, e.msg),
 886                             }
 887                             return None;
 888                         } else if let Some((filename, contents)) = Attributes::extract_include(&mi)
 889                         {
 890                             let line = doc_line;
 891                             doc_line += contents.lines().count();
 892                             doc_strings.push(DocFragment::Include(line,
 893                                                                   attr.span,
 894                                                                   filename,
 895                                                                   contents));
 896                         }
 897                     }
 898                 }
 899                 Some(attr.clone())
 900             })
 901         }).collect();
 902
 903         // treat #[target_feature(enable = "feat")] attributes as if they were
 904         // #[doc(cfg(target_feature = "feat"))] attributes as well
 905         for attr in attrs.lists("target_feature") {
 906             if attr.check_name("enable") {
 907                 if let Some(feat) = attr.value_str() {
 908                     let meta = attr::mk_name_value_item_str(Ident::from_str("target_feature"),
 909                                                             dummy_spanned(feat));
 910                     if let Ok(feat_cfg) = Cfg::parse(&meta) {
 911                         cfg &= feat_cfg;
 912                     }
 913                 }
 914             }
 915         }
 916
 917         let inner_docs = attrs.iter()
 918                               .filter(|a| a.check_name("doc"))
 919                               .next()
 920                               .map_or(true, |a| a.style == AttrStyle::Inner);
 921
 922         Attributes {
 923             doc_strings,
 924             other_attrs,
 925             cfg: if cfg == Cfg::True { None } else { Some(Arc::new(cfg)) },
 926             span: sp,
 927             links: vec![],
 928             inner_docs,
 929         }
 930     }
 931
 932     /// Finds the `doc` attribute as a NameValue and returns the corresponding
 933     /// value found.
 934     pub fn doc_value<'a>(&'a self) -> Option<&'a str> {
 935         self.doc_strings.first().map(|s| s.as_str())
 936     }
 937
 938     /// Finds all `doc` attributes as NameValues and returns their corresponding values, joined
 939     /// with newlines.
 940     pub fn collapsed_doc_value(&self) -> Option<String> {
 941         if !self.doc_strings.is_empty() {
 942             Some(self.doc_strings.iter().collect())
 943         } else {
 944             None
 945         }
 946     }
 947
 948     /// Gets links as a vector
 949     ///
 950     /// Cache must be populated before call
 951     pub fn links(&self, krate: &CrateNum) -> Vec<(String, String)> {
 952         use html::format::href;
 953         self.links.iter().filter_map(|&(ref s, did, ref fragment)| {
 954             match did {
 955                 Some(did) => {
 956                     if let Some((mut href, ..)) = href(did) {
 957                         if let Some(ref fragment) = *fragment {
 958                             href.push_str("#");
 959                             href.push_str(fragment);
 960                         }
 961                         Some((s.clone(), href))
 962                     } else {
 963                         None
 964                     }
 965                 }
 966                 None => {
 967                     if let Some(ref fragment) = *fragment {
 968                         let cache = cache();
 969                         let url = match cache.extern_locations.get(krate) {
 970                             Some(&(_, ref src, ExternalLocation::Local)) =>
 971                                 src.to_str().expect("invalid file path"),
 972                             Some(&(_, _, ExternalLocation::Remote(ref s))) => s,
 973                             Some(&(_, _, ExternalLocation::Unknown)) | None =>
 974                                 "https://doc.rust-lang.org/nightly",
 975                         };
 976                         // This is a primitive so the url is done "by hand".
 977                         Some((s.clone(),
 978                               format!("{}{}std/primitive.{}.html",
 979                                       url,
 980                                       if !url.ends_with('/') { "/" } else { "" },
 981                                       fragment)))
 982                     } else {
 983                         panic!("This isn't a primitive?!");
 984                     }
 985                 }
 986             }
 987         }).collect()
 988     }
 989 }
 990
 991 impl PartialEq for Attributes {
 992     fn eq(&self, rhs: &Self) -> bool {
 993         self.doc_strings == rhs.doc_strings &&
 994         self.cfg == rhs.cfg &&
 995         self.span == rhs.span &&
 996         self.links == rhs.links &&
 997         self.other_attrs.iter().map(|attr| attr.id).eq(rhs.other_attrs.iter().map(|attr| attr.id))
 998     }
 999 }
1000
1001 impl Eq for Attributes {}
1002
1003 impl Hash for Attributes {
1004     fn hash<H: Hasher>(&self, hasher: &mut H) {
1005         self.doc_strings.hash(hasher);
1006         self.cfg.hash(hasher);
1007         self.span.hash(hasher);
1008         self.links.hash(hasher);
1009         for attr in &self.other_attrs {
1010             attr.id.hash(hasher);
1011         }
1012     }
1013 }
1014
1015 impl AttributesExt for Attributes {
1016     fn lists<'a>(&'a self, name: &'a str) -> ListAttributesIter<'a> {
1017         self.other_attrs.lists(name)
1018     }
1019 }
1020
1021 impl Clean<Attributes> for [ast::Attribute] {
1022     fn clean(&self, cx: &DocContext) -> Attributes {
1023         Attributes::from_ast(cx.sess().diagnostic(), self)
1024     }
1025 }
1026
1027 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1028 pub enum GenericBound {
1029     TraitBound(PolyTrait, hir::TraitBoundModifier),
1030     Outlives(Lifetime),
1031 }
1032
1033 impl GenericBound {
1034     fn maybe_sized(cx: &DocContext) -> GenericBound {
1035         let did = cx.tcx.require_lang_item(lang_items::SizedTraitLangItem);
1036         let empty = cx.tcx.intern_substs(&[]);
1037         let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
1038             Some(did), false, vec![], empty);
1039         inline::record_extern_fqn(cx, did, TypeKind::Trait);
1040         GenericBound::TraitBound(PolyTrait {
1041             trait_: ResolvedPath {
1042                 path,
1043                 typarams: None,
1044                 did,
1045                 is_generic: false,
1046             },
1047             generic_params: Vec::new(),
1048         }, hir::TraitBoundModifier::Maybe)
1049     }
1050
1051     fn is_sized_bound(&self, cx: &DocContext) -> bool {
1052         use rustc::hir::TraitBoundModifier as TBM;
1053         if let GenericBound::TraitBound(PolyTrait { ref trait_, .. }, TBM::None) = *self {
1054             if trait_.def_id() == cx.tcx.lang_items().sized_trait() {
1055                 return true;
1056             }
1057         }
1058         false
1059     }
1060
1061     fn get_poly_trait(&self) -> Option<PolyTrait> {
1062         if let GenericBound::TraitBound(ref p, _) = *self {
1063             return Some(p.clone())
1064         }
1065         None
1066     }
1067
1068     fn get_trait_type(&self) -> Option<Type> {
1069         if let GenericBound::TraitBound(PolyTrait { ref trait_, .. }, _) = *self {
1070             return Some(trait_.clone());
1071         }
1072         None
1073     }
1074 }
1075
1076 impl Clean<GenericBound> for hir::GenericBound {
1077     fn clean(&self, cx: &DocContext) -> GenericBound {
1078         match *self {
1079             hir::GenericBound::Outlives(lt) => GenericBound::Outlives(lt.clean(cx)),
1080             hir::GenericBound::Trait(ref t, modifier) => {
1081                 GenericBound::TraitBound(t.clean(cx), modifier)
1082             }
1083         }
1084     }
1085 }
1086
1087 fn external_generic_args(cx: &DocContext, trait_did: Option<DefId>, has_self: bool,
1088                         bindings: Vec<TypeBinding>, substs: &Substs) -> GenericArgs {
1089     let lifetimes = substs.regions().filter_map(|v| v.clean(cx)).collect();
1090     let types = substs.types().skip(has_self as usize).collect::<Vec<_>>();
1091
1092     match trait_did {
1093         // Attempt to sugar an external path like Fn<(A, B,), C> to Fn(A, B) -> C
1094         Some(did) if cx.tcx.lang_items().fn_trait_kind(did).is_some() => {
1095             assert_eq!(types.len(), 1);
1096             let inputs = match types[0].sty {
1097                 ty::Tuple(ref tys) => tys.iter().map(|t| t.clean(cx)).collect(),
1098                 _ => {
1099                     return GenericArgs::AngleBracketed {
1100                         lifetimes,
1101                         types: types.clean(cx),
1102                         bindings,
1103                     }
1104                 }
1105             };
1106             let output = None;
1107             // FIXME(#20299) return type comes from a projection now
1108             // match types[1].sty {
1109             //     ty::Tuple(ref v) if v.is_empty() => None, // -> ()
1110             //     _ => Some(types[1].clean(cx))
1111             // };
1112             GenericArgs::Parenthesized {
1113                 inputs,
1114                 output,
1115             }
1116         },
1117         _ => {
1118             GenericArgs::AngleBracketed {
1119                 lifetimes,
1120                 types: types.clean(cx),
1121                 bindings,
1122             }
1123         }
1124     }
1125 }
1126
1127 // trait_did should be set to a trait's DefId if called on a TraitRef, in order to sugar
1128 // from Fn<(A, B,), C> to Fn(A, B) -> C
1129 fn external_path(cx: &DocContext, name: &str, trait_did: Option<DefId>, has_self: bool,
1130                  bindings: Vec<TypeBinding>, substs: &Substs) -> Path {
1131     Path {
1132         global: false,
1133         def: Def::Err,
1134         segments: vec![PathSegment {
1135             name: name.to_string(),
1136             args: external_generic_args(cx, trait_did, has_self, bindings, substs)
1137         }],
1138     }
1139 }
1140
1141 impl<'a, 'tcx> Clean<GenericBound> for (&'a ty::TraitRef<'tcx>, Vec<TypeBinding>) {
1142     fn clean(&self, cx: &DocContext) -> GenericBound {
1143         let (trait_ref, ref bounds) = *self;
1144         inline::record_extern_fqn(cx, trait_ref.def_id, TypeKind::Trait);
1145         let path = external_path(cx, &cx.tcx.item_name(trait_ref.def_id).as_str(),
1146                                  Some(trait_ref.def_id), true, bounds.clone(), trait_ref.substs);
1147
1148         debug!("ty::TraitRef\n  subst: {:?}\n", trait_ref.substs);
1149
1150         // collect any late bound regions
1151         let mut late_bounds = vec![];
1152         for ty_s in trait_ref.input_types().skip(1) {
1153             if let ty::Tuple(ts) = ty_s.sty {
1154                 for &ty_s in ts {
1155                     if let ty::Ref(ref reg, _, _) = ty_s.sty {
1156                         if let &ty::RegionKind::ReLateBound(..) = *reg {
1157                             debug!("  hit an ReLateBound {:?}", reg);
1158                             if let Some(Lifetime(name)) = reg.clean(cx) {
1159                                 late_bounds.push(GenericParamDef {
1160                                     name,
1161                                     kind: GenericParamDefKind::Lifetime,
1162                                 });
1163                             }
1164                         }
1165                     }
1166                 }
1167             }
1168         }
1169
1170         GenericBound::TraitBound(
1171             PolyTrait {
1172                 trait_: ResolvedPath {
1173                     path,
1174                     typarams: None,
1175                     did: trait_ref.def_id,
1176                     is_generic: false,
1177                 },
1178                 generic_params: late_bounds,
1179             },
1180             hir::TraitBoundModifier::None
1181         )
1182     }
1183 }
1184
1185 impl<'tcx> Clean<GenericBound> for ty::TraitRef<'tcx> {
1186     fn clean(&self, cx: &DocContext) -> GenericBound {
1187         (self, vec![]).clean(cx)
1188     }
1189 }
1190
1191 impl<'tcx> Clean<Option<Vec<GenericBound>>> for Substs<'tcx> {
1192     fn clean(&self, cx: &DocContext) -> Option<Vec<GenericBound>> {
1193         let mut v = Vec::new();
1194         v.extend(self.regions().filter_map(|r| r.clean(cx)).map(GenericBound::Outlives));
1195         v.extend(self.types().map(|t| GenericBound::TraitBound(PolyTrait {
1196             trait_: t.clean(cx),
1197             generic_params: Vec::new(),
1198         }, hir::TraitBoundModifier::None)));
1199         if !v.is_empty() {Some(v)} else {None}
1200     }
1201 }
1202
1203 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1204 pub struct Lifetime(String);
1205
1206 impl Lifetime {
1207     pub fn get_ref<'a>(&'a self) -> &'a str {
1208         let Lifetime(ref s) = *self;
1209         let s: &'a str = s;
1210         s
1211     }
1212
1213     pub fn statik() -> Lifetime {
1214         Lifetime("'static".to_string())
1215     }
1216 }
1217
1218 impl Clean<Lifetime> for hir::Lifetime {
1219     fn clean(&self, cx: &DocContext) -> Lifetime {
1220         if self.id != ast::DUMMY_NODE_ID {
1221             let def = cx.tcx.named_region(self.hir_id);
1222             match def {
1223                 Some(rl::Region::EarlyBound(_, node_id, _)) |
1224                 Some(rl::Region::LateBound(_, node_id, _)) |
1225                 Some(rl::Region::Free(_, node_id)) => {
1226                     if let Some(lt) = cx.lt_substs.borrow().get(&node_id).cloned() {
1227                         return lt;
1228                     }
1229                 }
1230                 _ => {}
1231             }
1232         }
1233         Lifetime(self.name.ident().to_string())
1234     }
1235 }
1236
1237 impl Clean<Lifetime> for hir::GenericParam {
1238     fn clean(&self, _: &DocContext) -> Lifetime {
1239         match self.kind {
1240             hir::GenericParamKind::Lifetime { .. } => {
1241                 if self.bounds.len() > 0 {
1242                     let mut bounds = self.bounds.iter().map(|bound| match bound {
1243                         hir::GenericBound::Outlives(lt) => lt,
1244                         _ => panic!(),
1245                     });
1246                     let name = bounds.next().expect("no more bounds").name.ident();
1247                     let mut s = format!("{}: {}", self.name.ident(), name);
1248                     for bound in bounds {
1249                         s.push_str(&format!(" + {}", bound.name.ident()));
1250                     }
1251                     Lifetime(s)
1252                 } else {
1253                     Lifetime(self.name.ident().to_string())
1254                 }
1255             }
1256             _ => panic!(),
1257         }
1258     }
1259 }
1260
1261 impl Clean<Constant> for hir::ConstArg {
1262     fn clean(&self, cx: &DocContext) -> Constant {
1263         Constant {
1264             type_: cx.tcx.type_of(cx.tcx.hir().body_owner_def_id(self.value.body)).clean(cx),
1265             expr: print_const_expr(cx, self.value.body),
1266         }
1267     }
1268 }
1269
1270 impl<'tcx> Clean<Lifetime> for ty::GenericParamDef {
1271     fn clean(&self, _cx: &DocContext) -> Lifetime {
1272         Lifetime(self.name.to_string())
1273     }
1274 }
1275
1276 impl Clean<Option<Lifetime>> for ty::RegionKind {
1277     fn clean(&self, cx: &DocContext) -> Option<Lifetime> {
1278         match *self {
1279             ty::ReStatic => Some(Lifetime::statik()),
1280             ty::ReLateBound(_, ty::BrNamed(_, name)) => Some(Lifetime(name.to_string())),
1281             ty::ReEarlyBound(ref data) => Some(Lifetime(data.name.clean(cx))),
1282
1283             ty::ReLateBound(..) |
1284             ty::ReFree(..) |
1285             ty::ReScope(..) |
1286             ty::ReVar(..) |
1287             ty::RePlaceholder(..) |
1288             ty::ReEmpty |
1289             ty::ReClosureBound(_) |
1290             ty::ReErased => {
1291                 debug!("Cannot clean region {:?}", self);
1292                 None
1293             }
1294         }
1295     }
1296 }
1297
1298 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1299 pub enum WherePredicate {
1300     BoundPredicate { ty: Type, bounds: Vec<GenericBound> },
1301     RegionPredicate { lifetime: Lifetime, bounds: Vec<GenericBound> },
1302     EqPredicate { lhs: Type, rhs: Type },
1303 }
1304
1305 impl Clean<WherePredicate> for hir::WherePredicate {
1306     fn clean(&self, cx: &DocContext) -> WherePredicate {
1307         match *self {
1308             hir::WherePredicate::BoundPredicate(ref wbp) => {
1309                 WherePredicate::BoundPredicate {
1310                     ty: wbp.bounded_ty.clean(cx),
1311                     bounds: wbp.bounds.clean(cx)
1312                 }
1313             }
1314
1315             hir::WherePredicate::RegionPredicate(ref wrp) => {
1316                 WherePredicate::RegionPredicate {
1317                     lifetime: wrp.lifetime.clean(cx),
1318                     bounds: wrp.bounds.clean(cx)
1319                 }
1320             }
1321
1322             hir::WherePredicate::EqPredicate(ref wrp) => {
1323                 WherePredicate::EqPredicate {
1324                     lhs: wrp.lhs_ty.clean(cx),
1325                     rhs: wrp.rhs_ty.clean(cx)
1326                 }
1327             }
1328         }
1329     }
1330 }
1331
1332 impl<'a> Clean<Option<WherePredicate>> for ty::Predicate<'a> {
1333     fn clean(&self, cx: &DocContext) -> Option<WherePredicate> {
1334         use rustc::ty::Predicate;
1335
1336         match *self {
1337             Predicate::Trait(ref pred) => Some(pred.clean(cx)),
1338             Predicate::Subtype(ref pred) => Some(pred.clean(cx)),
1339             Predicate::RegionOutlives(ref pred) => pred.clean(cx),
1340             Predicate::TypeOutlives(ref pred) => pred.clean(cx),
1341             Predicate::Projection(ref pred) => Some(pred.clean(cx)),
1342
1343             Predicate::WellFormed(..) |
1344             Predicate::ObjectSafe(..) |
1345             Predicate::ClosureKind(..) |
1346             Predicate::ConstEvaluatable(..) => panic!("not user writable"),
1347         }
1348     }
1349 }
1350
1351 impl<'a> Clean<WherePredicate> for ty::TraitPredicate<'a> {
1352     fn clean(&self, cx: &DocContext) -> WherePredicate {
1353         WherePredicate::BoundPredicate {
1354             ty: self.trait_ref.self_ty().clean(cx),
1355             bounds: vec![self.trait_ref.clean(cx)]
1356         }
1357     }
1358 }
1359
1360 impl<'tcx> Clean<WherePredicate> for ty::SubtypePredicate<'tcx> {
1361     fn clean(&self, _cx: &DocContext) -> WherePredicate {
1362         panic!("subtype predicates are an internal rustc artifact \
1363                 and should not be seen by rustdoc")
1364     }
1365 }
1366
1367 impl<'tcx> Clean<Option<WherePredicate>> for
1368     ty::OutlivesPredicate<ty::Region<'tcx>,ty::Region<'tcx>> {
1369
1370     fn clean(&self, cx: &DocContext) -> Option<WherePredicate> {
1371         let ty::OutlivesPredicate(ref a, ref b) = *self;
1372
1373         match (a, b) {
1374             (ty::ReEmpty, ty::ReEmpty) => {
1375                 return None;
1376             },
1377             _ => {}
1378         }
1379
1380         Some(WherePredicate::RegionPredicate {
1381             lifetime: a.clean(cx).expect("failed to clean lifetime"),
1382             bounds: vec![GenericBound::Outlives(b.clean(cx).expect("failed to clean bounds"))]
1383         })
1384     }
1385 }
1386
1387 impl<'tcx> Clean<Option<WherePredicate>> for ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>> {
1388     fn clean(&self, cx: &DocContext) -> Option<WherePredicate> {
1389         let ty::OutlivesPredicate(ref ty, ref lt) = *self;
1390
1391         match lt {
1392             ty::ReEmpty => return None,
1393             _ => {}
1394         }
1395
1396         Some(WherePredicate::BoundPredicate {
1397             ty: ty.clean(cx),
1398             bounds: vec![GenericBound::Outlives(lt.clean(cx).expect("failed to clean lifetimes"))]
1399         })
1400     }
1401 }
1402
1403 impl<'tcx> Clean<WherePredicate> for ty::ProjectionPredicate<'tcx> {
1404     fn clean(&self, cx: &DocContext) -> WherePredicate {
1405         WherePredicate::EqPredicate {
1406             lhs: self.projection_ty.clean(cx),
1407             rhs: self.ty.clean(cx)
1408         }
1409     }
1410 }
1411
1412 impl<'tcx> Clean<Type> for ty::ProjectionTy<'tcx> {
1413     fn clean(&self, cx: &DocContext) -> Type {
1414         let trait_ = match self.trait_ref(cx.tcx).clean(cx) {
1415             GenericBound::TraitBound(t, _) => t.trait_,
1416             GenericBound::Outlives(_) => panic!("cleaning a trait got a lifetime"),
1417         };
1418         Type::QPath {
1419             name: cx.tcx.associated_item(self.item_def_id).ident.name.clean(cx),
1420             self_type: box self.self_ty().clean(cx),
1421             trait_: box trait_
1422         }
1423     }
1424 }
1425
1426 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1427 pub enum GenericParamDefKind {
1428     Lifetime,
1429     Type {
1430         did: DefId,
1431         bounds: Vec<GenericBound>,
1432         default: Option<Type>,
1433         synthetic: Option<hir::SyntheticTyParamKind>,
1434     },
1435     Const {
1436         did: DefId,
1437         ty: Type,
1438     },
1439 }
1440
1441 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1442 pub struct GenericParamDef {
1443     pub name: String,
1444
1445     pub kind: GenericParamDefKind,
1446 }
1447
1448 impl GenericParamDef {
1449     pub fn is_synthetic_type_param(&self) -> bool {
1450         match self.kind {
1451             GenericParamDefKind::Lifetime |
1452             GenericParamDefKind::Const { .. } => {
1453                 false
1454             }
1455             GenericParamDefKind::Type { ref synthetic, .. } => synthetic.is_some(),
1456         }
1457     }
1458 }
1459
1460 impl<'tcx> Clean<GenericParamDef> for ty::GenericParamDef {
1461     fn clean(&self, cx: &DocContext) -> GenericParamDef {
1462         let (name, kind) = match self.kind {
1463             ty::GenericParamDefKind::Lifetime => {
1464                 (self.name.to_string(), GenericParamDefKind::Lifetime)
1465             }
1466             ty::GenericParamDefKind::Type { has_default, .. } => {
1467                 cx.renderinfo.borrow_mut().external_typarams
1468                              .insert(self.def_id, self.name.clean(cx));
1469                 let default = if has_default {
1470                     Some(cx.tcx.type_of(self.def_id).clean(cx))
1471                 } else {
1472                     None
1473                 };
1474                 (self.name.clean(cx), GenericParamDefKind::Type {
1475                     did: self.def_id,
1476                     bounds: vec![], // These are filled in from the where-clauses.
1477                     default,
1478                     synthetic: None,
1479                 })
1480             }
1481         };
1482
1483         GenericParamDef {
1484             name,
1485             kind,
1486         }
1487     }
1488 }
1489
1490 impl Clean<GenericParamDef> for hir::GenericParam {
1491     fn clean(&self, cx: &DocContext) -> GenericParamDef {
1492         let (name, kind) = match self.kind {
1493             hir::GenericParamKind::Lifetime { .. } => {
1494                 let name = if self.bounds.len() > 0 {
1495                     let mut bounds = self.bounds.iter().map(|bound| match bound {
1496                         hir::GenericBound::Outlives(lt) => lt,
1497                         _ => panic!(),
1498                     });
1499                     let name = bounds.next().expect("no more bounds").name.ident();
1500                     let mut s = format!("{}: {}", self.name.ident(), name);
1501                     for bound in bounds {
1502                         s.push_str(&format!(" + {}", bound.name.ident()));
1503                     }
1504                     s
1505                 } else {
1506                     self.name.ident().to_string()
1507                 };
1508                 (name, GenericParamDefKind::Lifetime)
1509             }
1510             hir::GenericParamKind::Type { ref default, synthetic } => {
1511                 (self.name.ident().name.clean(cx), GenericParamDefKind::Type {
1512                     did: cx.tcx.hir().local_def_id(self.id),
1513                     bounds: self.bounds.clean(cx),
1514                     default: default.clean(cx),
1515                     synthetic: synthetic,
1516                 })
1517             }
1518             hir::GenericParamKind::Const { ref ty } => {
1519                 (self.name.ident().name.clean(cx), GenericParamDefKind::Const {
1520                     did: cx.tcx.hir().local_def_id(self.id),
1521                     ty: ty.clean(cx),
1522                 })
1523             }
1524         };
1525
1526         GenericParamDef {
1527             name,
1528             kind,
1529         }
1530     }
1531 }
1532
1533 // maybe use a Generic enum and use Vec<Generic>?
1534 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Default, Hash)]
1535 pub struct Generics {
1536     pub params: Vec<GenericParamDef>,
1537     pub where_predicates: Vec<WherePredicate>,
1538 }
1539
1540 impl Clean<Generics> for hir::Generics {
1541     fn clean(&self, cx: &DocContext) -> Generics {
1542         // Synthetic type-parameters are inserted after normal ones.
1543         // In order for normal parameters to be able to refer to synthetic ones,
1544         // scans them first.
1545         fn is_impl_trait(param: &hir::GenericParam) -> bool {
1546             match param.kind {
1547                 hir::GenericParamKind::Type { synthetic, .. } => {
1548                     synthetic == Some(hir::SyntheticTyParamKind::ImplTrait)
1549                 }
1550                 _ => false,
1551             }
1552         }
1553         let impl_trait_params = self.params
1554             .iter()
1555             .filter(|param| is_impl_trait(param))
1556             .map(|param| {
1557                 let param: GenericParamDef = param.clean(cx);
1558                 match param.kind {
1559                     GenericParamDefKind::Lifetime => unreachable!(),
1560                     GenericParamDefKind::Type { did, ref bounds, .. } => {
1561                         cx.impl_trait_bounds.borrow_mut().insert(did, bounds.clone());
1562                     }
1563                     GenericParamDefKind::Const { .. } => unreachable!(),
1564                 }
1565                 param
1566             })
1567             .collect::<Vec<_>>();
1568
1569         let mut params = Vec::with_capacity(self.params.len());
1570         for p in self.params.iter().filter(|p| !is_impl_trait(p)) {
1571             let p = p.clean(cx);
1572             params.push(p);
1573         }
1574         params.extend(impl_trait_params);
1575
1576         let mut generics = Generics {
1577             params,
1578             where_predicates: self.where_clause.predicates.clean(cx),
1579         };
1580
1581         // Some duplicates are generated for ?Sized bounds between type params and where
1582         // predicates. The point in here is to move the bounds definitions from type params
1583         // to where predicates when such cases occur.
1584         for where_pred in &mut generics.where_predicates {
1585             match *where_pred {
1586                 WherePredicate::BoundPredicate { ty: Generic(ref name), ref mut bounds } => {
1587                     if bounds.is_empty() {
1588                         for param in &mut generics.params {
1589                             match param.kind {
1590                                 GenericParamDefKind::Lifetime => {}
1591                                 GenericParamDefKind::Type { bounds: ref mut ty_bounds, .. } => {
1592                                     if &param.name == name {
1593                                         mem::swap(bounds, ty_bounds);
1594                                         break
1595                                     }
1596                                 }
1597                                 GenericParamDefKind::Const { .. } => {}
1598                             }
1599                         }
1600                     }
1601                 }
1602                 _ => continue,
1603             }
1604         }
1605         generics
1606     }
1607 }
1608
1609 impl<'a, 'tcx> Clean<Generics> for (&'a ty::Generics,
1610                                     &'a Lrc<ty::GenericPredicates<'tcx>>) {
1611     fn clean(&self, cx: &DocContext) -> Generics {
1612         use self::WherePredicate as WP;
1613
1614         let (gens, preds) = *self;
1615
1616         // Bounds in the type_params and lifetimes fields are repeated in the
1617         // predicates field (see rustc_typeck::collect::ty_generics), so remove
1618         // them.
1619         let stripped_typarams = gens.params.iter().filter_map(|param| match param.kind {
1620             ty::GenericParamDefKind::Lifetime => None,
1621             ty::GenericParamDefKind::Type { .. } => {
1622                 if param.name == keywords::SelfUpper.name().as_str() {
1623                     assert_eq!(param.index, 0);
1624                     return None;
1625                 }
1626                 Some(param.clean(cx))
1627             }
1628         }).collect::<Vec<GenericParamDef>>();
1629
1630         let mut where_predicates = preds.predicates.iter()
1631             .flat_map(|(p, _)| p.clean(cx))
1632             .collect::<Vec<_>>();
1633
1634         // Type parameters and have a Sized bound by default unless removed with
1635         // ?Sized. Scan through the predicates and mark any type parameter with
1636         // a Sized bound, removing the bounds as we find them.
1637         //
1638         // Note that associated types also have a sized bound by default, but we
1639         // don't actually know the set of associated types right here so that's
1640         // handled in cleaning associated types
1641         let mut sized_params = FxHashSet::default();
1642         where_predicates.retain(|pred| {
1643             match *pred {
1644                 WP::BoundPredicate { ty: Generic(ref g), ref bounds } => {
1645                     if bounds.iter().any(|b| b.is_sized_bound(cx)) {
1646                         sized_params.insert(g.clone());
1647                         false
1648                     } else {
1649                         true
1650                     }
1651                 }
1652                 _ => true,
1653             }
1654         });
1655
1656         // Run through the type parameters again and insert a ?Sized
1657         // unbound for any we didn't find to be Sized.
1658         for tp in &stripped_typarams {
1659             if !sized_params.contains(&tp.name) {
1660                 where_predicates.push(WP::BoundPredicate {
1661                     ty: Type::Generic(tp.name.clone()),
1662                     bounds: vec![GenericBound::maybe_sized(cx)],
1663                 })
1664             }
1665         }
1666
1667         // It would be nice to collect all of the bounds on a type and recombine
1668         // them if possible, to avoid e.g., `where T: Foo, T: Bar, T: Sized, T: 'a`
1669         // and instead see `where T: Foo + Bar + Sized + 'a`
1670
1671         Generics {
1672             params: gens.params
1673                         .iter()
1674                         .flat_map(|param| match param.kind {
1675                             ty::GenericParamDefKind::Lifetime => Some(param.clean(cx)),
1676                             ty::GenericParamDefKind::Type { .. } => None,
1677                         }).chain(simplify::ty_params(stripped_typarams).into_iter())
1678                         .collect(),
1679             where_predicates: simplify::where_clauses(cx, where_predicates),
1680         }
1681     }
1682 }
1683
1684 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1685 pub struct Method {
1686     pub generics: Generics,
1687     pub decl: FnDecl,
1688     pub header: hir::FnHeader,
1689 }
1690
1691 impl<'a> Clean<Method> for (&'a hir::MethodSig, &'a hir::Generics, hir::BodyId) {
1692     fn clean(&self, cx: &DocContext) -> Method {
1693         let (generics, decl) = enter_impl_trait(cx, || {
1694             (self.1.clean(cx), (&*self.0.decl, self.2).clean(cx))
1695         });
1696         Method {
1697             decl,
1698             generics,
1699             header: self.0.header,
1700         }
1701     }
1702 }
1703
1704 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1705 pub struct TyMethod {
1706     pub header: hir::FnHeader,
1707     pub decl: FnDecl,
1708     pub generics: Generics,
1709 }
1710
1711 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1712 pub struct Function {
1713     pub decl: FnDecl,
1714     pub generics: Generics,
1715     pub header: hir::FnHeader,
1716 }
1717
1718 impl Clean<Item> for doctree::Function {
1719     fn clean(&self, cx: &DocContext) -> Item {
1720         let (generics, decl) = enter_impl_trait(cx, || {
1721             (self.generics.clean(cx), (&self.decl, self.body).clean(cx))
1722         });
1723
1724         let did = cx.tcx.hir().local_def_id(self.id);
1725         let constness = if cx.tcx.is_min_const_fn(did) {
1726             hir::Constness::Const
1727         } else {
1728             hir::Constness::NotConst
1729         };
1730         Item {
1731             name: Some(self.name.clean(cx)),
1732             attrs: self.attrs.clean(cx),
1733             source: self.whence.clean(cx),
1734             visibility: self.vis.clean(cx),
1735             stability: self.stab.clean(cx),
1736             deprecation: self.depr.clean(cx),
1737             def_id: did,
1738             inner: FunctionItem(Function {
1739                 decl,
1740                 generics,
1741                 header: hir::FnHeader { constness, ..self.header },
1742             }),
1743         }
1744     }
1745 }
1746
1747 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1748 pub struct FnDecl {
1749     pub inputs: Arguments,
1750     pub output: FunctionRetTy,
1751     pub variadic: bool,
1752     pub attrs: Attributes,
1753 }
1754
1755 impl FnDecl {
1756     pub fn self_type(&self) -> Option<SelfTy> {
1757         self.inputs.values.get(0).and_then(|v| v.to_self())
1758     }
1759
1760     /// Returns the sugared return type for an async function.
1761     ///
1762     /// For example, if the return type is `impl std::future::Future<Output = i32>`, this function
1763     /// will return `i32`.
1764     ///
1765     /// # Panics
1766     ///
1767     /// This function will panic if the return type does not match the expected sugaring for async
1768     /// functions.
1769     pub fn sugared_async_return_type(&self) -> FunctionRetTy {
1770         match &self.output {
1771             FunctionRetTy::Return(Type::ImplTrait(bounds)) => {
1772                 match &bounds[0] {
1773                     GenericBound::TraitBound(PolyTrait { trait_, .. }, ..) => {
1774                         let bindings = trait_.bindings().unwrap();
1775                         FunctionRetTy::Return(bindings[0].ty.clone())
1776                     }
1777                     _ => panic!("unexpected desugaring of async function"),
1778                 }
1779             }
1780             _ => panic!("unexpected desugaring of async function"),
1781         }
1782     }
1783 }
1784
1785 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1786 pub struct Arguments {
1787     pub values: Vec<Argument>,
1788 }
1789
1790 impl<'a> Clean<Arguments> for (&'a [hir::Ty], &'a [ast::Ident]) {
1791     fn clean(&self, cx: &DocContext) -> Arguments {
1792         Arguments {
1793             values: self.0.iter().enumerate().map(|(i, ty)| {
1794                 let mut name = self.1.get(i).map(|ident| ident.to_string())
1795                                             .unwrap_or(String::new());
1796                 if name.is_empty() {
1797                     name = "_".to_string();
1798                 }
1799                 Argument {
1800                     name,
1801                     type_: ty.clean(cx),
1802                 }
1803             }).collect()
1804         }
1805     }
1806 }
1807
1808 impl<'a> Clean<Arguments> for (&'a [hir::Ty], hir::BodyId) {
1809     fn clean(&self, cx: &DocContext) -> Arguments {
1810         let body = cx.tcx.hir().body(self.1);
1811
1812         Arguments {
1813             values: self.0.iter().enumerate().map(|(i, ty)| {
1814                 Argument {
1815                     name: name_from_pat(&body.arguments[i].pat),
1816                     type_: ty.clean(cx),
1817                 }
1818             }).collect()
1819         }
1820     }
1821 }
1822
1823 impl<'a, A: Copy> Clean<FnDecl> for (&'a hir::FnDecl, A)
1824     where (&'a [hir::Ty], A): Clean<Arguments>
1825 {
1826     fn clean(&self, cx: &DocContext) -> FnDecl {
1827         FnDecl {
1828             inputs: (&self.0.inputs[..], self.1).clean(cx),
1829             output: self.0.output.clean(cx),
1830             variadic: self.0.variadic,
1831             attrs: Attributes::default()
1832         }
1833     }
1834 }
1835
1836 impl<'a, 'tcx> Clean<FnDecl> for (DefId, ty::PolyFnSig<'tcx>) {
1837     fn clean(&self, cx: &DocContext) -> FnDecl {
1838         let (did, sig) = *self;
1839         let mut names = if cx.tcx.hir().as_local_node_id(did).is_some() {
1840             vec![].into_iter()
1841         } else {
1842             cx.tcx.fn_arg_names(did).into_iter()
1843         };
1844
1845         FnDecl {
1846             output: Return(sig.skip_binder().output().clean(cx)),
1847             attrs: Attributes::default(),
1848             variadic: sig.skip_binder().variadic,
1849             inputs: Arguments {
1850                 values: sig.skip_binder().inputs().iter().map(|t| {
1851                     Argument {
1852                         type_: t.clean(cx),
1853                         name: names.next().map_or(String::new(), |name| name.to_string()),
1854                     }
1855                 }).collect(),
1856             },
1857         }
1858     }
1859 }
1860
1861 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1862 pub struct Argument {
1863     pub type_: Type,
1864     pub name: String,
1865 }
1866
1867 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1868 pub enum SelfTy {
1869     SelfValue,
1870     SelfBorrowed(Option<Lifetime>, Mutability),
1871     SelfExplicit(Type),
1872 }
1873
1874 impl Argument {
1875     pub fn to_self(&self) -> Option<SelfTy> {
1876         if self.name != "self" {
1877             return None;
1878         }
1879         if self.type_.is_self_type() {
1880             return Some(SelfValue);
1881         }
1882         match self.type_ {
1883             BorrowedRef{ref lifetime, mutability, ref type_} if type_.is_self_type() => {
1884                 Some(SelfBorrowed(lifetime.clone(), mutability))
1885             }
1886             _ => Some(SelfExplicit(self.type_.clone()))
1887         }
1888     }
1889 }
1890
1891 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1892 pub enum FunctionRetTy {
1893     Return(Type),
1894     DefaultReturn,
1895 }
1896
1897 impl Clean<FunctionRetTy> for hir::FunctionRetTy {
1898     fn clean(&self, cx: &DocContext) -> FunctionRetTy {
1899         match *self {
1900             hir::Return(ref typ) => Return(typ.clean(cx)),
1901             hir::DefaultReturn(..) => DefaultReturn,
1902         }
1903     }
1904 }
1905
1906 impl GetDefId for FunctionRetTy {
1907     fn def_id(&self) -> Option<DefId> {
1908         match *self {
1909             Return(ref ty) => ty.def_id(),
1910             DefaultReturn => None,
1911         }
1912     }
1913 }
1914
1915 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1916 pub struct Trait {
1917     pub auto: bool,
1918     pub unsafety: hir::Unsafety,
1919     pub items: Vec<Item>,
1920     pub generics: Generics,
1921     pub bounds: Vec<GenericBound>,
1922     pub is_spotlight: bool,
1923     pub is_auto: bool,
1924 }
1925
1926 impl Clean<Item> for doctree::Trait {
1927     fn clean(&self, cx: &DocContext) -> Item {
1928         let attrs = self.attrs.clean(cx);
1929         let is_spotlight = attrs.has_doc_flag("spotlight");
1930         Item {
1931             name: Some(self.name.clean(cx)),
1932             attrs: attrs,
1933             source: self.whence.clean(cx),
1934             def_id: cx.tcx.hir().local_def_id(self.id),
1935             visibility: self.vis.clean(cx),
1936             stability: self.stab.clean(cx),
1937             deprecation: self.depr.clean(cx),
1938             inner: TraitItem(Trait {
1939                 auto: self.is_auto.clean(cx),
1940                 unsafety: self.unsafety,
1941                 items: self.items.clean(cx),
1942                 generics: self.generics.clean(cx),
1943                 bounds: self.bounds.clean(cx),
1944                 is_spotlight,
1945                 is_auto: self.is_auto.clean(cx),
1946             }),
1947         }
1948     }
1949 }
1950
1951 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1952 pub struct TraitAlias {
1953     pub generics: Generics,
1954     pub bounds: Vec<GenericBound>,
1955 }
1956
1957 impl Clean<Item> for doctree::TraitAlias {
1958     fn clean(&self, cx: &DocContext) -> Item {
1959         let attrs = self.attrs.clean(cx);
1960         Item {
1961             name: Some(self.name.clean(cx)),
1962             attrs,
1963             source: self.whence.clean(cx),
1964             def_id: cx.tcx.hir().local_def_id(self.id),
1965             visibility: self.vis.clean(cx),
1966             stability: self.stab.clean(cx),
1967             deprecation: self.depr.clean(cx),
1968             inner: TraitAliasItem(TraitAlias {
1969                 generics: self.generics.clean(cx),
1970                 bounds: self.bounds.clean(cx),
1971             }),
1972         }
1973     }
1974 }
1975
1976 impl Clean<bool> for hir::IsAuto {
1977     fn clean(&self, _: &DocContext) -> bool {
1978         match *self {
1979             hir::IsAuto::Yes => true,
1980             hir::IsAuto::No => false,
1981         }
1982     }
1983 }
1984
1985 impl Clean<Type> for hir::TraitRef {
1986     fn clean(&self, cx: &DocContext) -> Type {
1987         resolve_type(cx, self.path.clean(cx), self.ref_id)
1988     }
1989 }
1990
1991 impl Clean<PolyTrait> for hir::PolyTraitRef {
1992     fn clean(&self, cx: &DocContext) -> PolyTrait {
1993         PolyTrait {
1994             trait_: self.trait_ref.clean(cx),
1995             generic_params: self.bound_generic_params.clean(cx)
1996         }
1997     }
1998 }
1999
2000 impl Clean<Item> for hir::TraitItem {
2001     fn clean(&self, cx: &DocContext) -> Item {
2002         let inner = match self.node {
2003             hir::TraitItemKind::Const(ref ty, default) => {
2004                 AssociatedConstItem(ty.clean(cx),
2005                                     default.map(|e| print_const_expr(cx, e)))
2006             }
2007             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Provided(body)) => {
2008                 MethodItem((sig, &self.generics, body).clean(cx))
2009             }
2010             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Required(ref names)) => {
2011                 let (generics, decl) = enter_impl_trait(cx, || {
2012                     (self.generics.clean(cx), (&*sig.decl, &names[..]).clean(cx))
2013                 });
2014                 TyMethodItem(TyMethod {
2015                     header: sig.header,
2016                     decl,
2017                     generics,
2018                 })
2019             }
2020             hir::TraitItemKind::Type(ref bounds, ref default) => {
2021                 AssociatedTypeItem(bounds.clean(cx), default.clean(cx))
2022             }
2023         };
2024         Item {
2025             name: Some(self.ident.name.clean(cx)),
2026             attrs: self.attrs.clean(cx),
2027             source: self.span.clean(cx),
2028             def_id: cx.tcx.hir().local_def_id(self.id),
2029             visibility: None,
2030             stability: get_stability(cx, cx.tcx.hir().local_def_id(self.id)),
2031             deprecation: get_deprecation(cx, cx.tcx.hir().local_def_id(self.id)),
2032             inner,
2033         }
2034     }
2035 }
2036
2037 impl Clean<Item> for hir::ImplItem {
2038     fn clean(&self, cx: &DocContext) -> Item {
2039         let inner = match self.node {
2040             hir::ImplItemKind::Const(ref ty, expr) => {
2041                 AssociatedConstItem(ty.clean(cx),
2042                                     Some(print_const_expr(cx, expr)))
2043             }
2044             hir::ImplItemKind::Method(ref sig, body) => {
2045                 MethodItem((sig, &self.generics, body).clean(cx))
2046             }
2047             hir::ImplItemKind::Type(ref ty) => TypedefItem(Typedef {
2048                 type_: ty.clean(cx),
2049                 generics: Generics::default(),
2050             }, true),
2051             hir::ImplItemKind::Existential(ref bounds) => ExistentialItem(Existential {
2052                 bounds: bounds.clean(cx),
2053                 generics: Generics::default(),
2054             }, true),
2055         };
2056         Item {
2057             name: Some(self.ident.name.clean(cx)),
2058             source: self.span.clean(cx),
2059             attrs: self.attrs.clean(cx),
2060             def_id: cx.tcx.hir().local_def_id(self.id),
2061             visibility: self.vis.clean(cx),
2062             stability: get_stability(cx, cx.tcx.hir().local_def_id(self.id)),
2063             deprecation: get_deprecation(cx, cx.tcx.hir().local_def_id(self.id)),
2064             inner,
2065         }
2066     }
2067 }
2068
2069 impl<'tcx> Clean<Item> for ty::AssociatedItem {
2070     fn clean(&self, cx: &DocContext) -> Item {
2071         let inner = match self.kind {
2072             ty::AssociatedKind::Const => {
2073                 let ty = cx.tcx.type_of(self.def_id);
2074                 let default = if self.defaultness.has_value() {
2075                     Some(inline::print_inlined_const(cx, self.def_id))
2076                 } else {
2077                     None
2078                 };
2079                 AssociatedConstItem(ty.clean(cx), default)
2080             }
2081             ty::AssociatedKind::Method => {
2082                 let generics = (cx.tcx.generics_of(self.def_id),
2083                                 &cx.tcx.predicates_of(self.def_id)).clean(cx);
2084                 let sig = cx.tcx.fn_sig(self.def_id);
2085                 let mut decl = (self.def_id, sig).clean(cx);
2086
2087                 if self.method_has_self_argument {
2088                     let self_ty = match self.container {
2089                         ty::ImplContainer(def_id) => {
2090                             cx.tcx.type_of(def_id)
2091                         }
2092                         ty::TraitContainer(_) => cx.tcx.mk_self_type()
2093                     };
2094                     let self_arg_ty = *sig.input(0).skip_binder();
2095                     if self_arg_ty == self_ty {
2096                         decl.inputs.values[0].type_ = Generic(String::from("Self"));
2097                     } else if let ty::Ref(_, ty, _) = self_arg_ty.sty {
2098                         if ty == self_ty {
2099                             match decl.inputs.values[0].type_ {
2100                                 BorrowedRef{ref mut type_, ..} => {
2101                                     **type_ = Generic(String::from("Self"))
2102                                 }
2103                                 _ => unreachable!(),
2104                             }
2105                         }
2106                     }
2107                 }
2108
2109                 let provided = match self.container {
2110                     ty::ImplContainer(_) => true,
2111                     ty::TraitContainer(_) => self.defaultness.has_value()
2112                 };
2113                 if provided {
2114                     let constness = if cx.tcx.is_min_const_fn(self.def_id) {
2115                         hir::Constness::Const
2116                     } else {
2117                         hir::Constness::NotConst
2118                     };
2119                     MethodItem(Method {
2120                         generics,
2121                         decl,
2122                         header: hir::FnHeader {
2123                             unsafety: sig.unsafety(),
2124                             abi: sig.abi(),
2125                             constness,
2126                             asyncness: hir::IsAsync::NotAsync,
2127                         }
2128                     })
2129                 } else {
2130                     TyMethodItem(TyMethod {
2131                         generics,
2132                         decl,
2133                         header: hir::FnHeader {
2134                             unsafety: sig.unsafety(),
2135                             abi: sig.abi(),
2136                             constness: hir::Constness::NotConst,
2137                             asyncness: hir::IsAsync::NotAsync,
2138                         }
2139                     })
2140                 }
2141             }
2142             ty::AssociatedKind::Type => {
2143                 let my_name = self.ident.name.clean(cx);
2144
2145                 if let ty::TraitContainer(did) = self.container {
2146                     // When loading a cross-crate associated type, the bounds for this type
2147                     // are actually located on the trait/impl itself, so we need to load
2148                     // all of the generics from there and then look for bounds that are
2149                     // applied to this associated type in question.
2150                     let predicates = cx.tcx.predicates_of(did);
2151                     let generics = (cx.tcx.generics_of(did), &predicates).clean(cx);
2152                     let mut bounds = generics.where_predicates.iter().filter_map(|pred| {
2153                         let (name, self_type, trait_, bounds) = match *pred {
2154                             WherePredicate::BoundPredicate {
2155                                 ty: QPath { ref name, ref self_type, ref trait_ },
2156                                 ref bounds
2157                             } => (name, self_type, trait_, bounds),
2158                             _ => return None,
2159                         };
2160                         if *name != my_name { return None }
2161                         match **trait_ {
2162                             ResolvedPath { did, .. } if did == self.container.id() => {}
2163                             _ => return None,
2164                         }
2165                         match **self_type {
2166                             Generic(ref s) if *s == "Self" => {}
2167                             _ => return None,
2168                         }
2169                         Some(bounds)
2170                     }).flat_map(|i| i.iter().cloned()).collect::<Vec<_>>();
2171                     // Our Sized/?Sized bound didn't get handled when creating the generics
2172                     // because we didn't actually get our whole set of bounds until just now
2173                     // (some of them may have come from the trait). If we do have a sized
2174                     // bound, we remove it, and if we don't then we add the `?Sized` bound
2175                     // at the end.
2176                     match bounds.iter().position(|b| b.is_sized_bound(cx)) {
2177                         Some(i) => { bounds.remove(i); }
2178                         None => bounds.push(GenericBound::maybe_sized(cx)),
2179                     }
2180
2181                     let ty = if self.defaultness.has_value() {
2182                         Some(cx.tcx.type_of(self.def_id))
2183                     } else {
2184                         None
2185                     };
2186
2187                     AssociatedTypeItem(bounds, ty.clean(cx))
2188                 } else {
2189                     TypedefItem(Typedef {
2190                         type_: cx.tcx.type_of(self.def_id).clean(cx),
2191                         generics: Generics {
2192                             params: Vec::new(),
2193                             where_predicates: Vec::new(),
2194                         },
2195                     }, true)
2196                 }
2197             }
2198             ty::AssociatedKind::Existential => unimplemented!(),
2199         };
2200
2201         let visibility = match self.container {
2202             ty::ImplContainer(_) => self.vis.clean(cx),
2203             ty::TraitContainer(_) => None,
2204         };
2205
2206         Item {
2207             name: Some(self.ident.name.clean(cx)),
2208             visibility,
2209             stability: get_stability(cx, self.def_id),
2210             deprecation: get_deprecation(cx, self.def_id),
2211             def_id: self.def_id,
2212             attrs: inline::load_attrs(cx, self.def_id),
2213             source: cx.tcx.def_span(self.def_id).clean(cx),
2214             inner,
2215         }
2216     }
2217 }
2218
2219 /// A trait reference, which may have higher ranked lifetimes.
2220 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2221 pub struct PolyTrait {
2222     pub trait_: Type,
2223     pub generic_params: Vec<GenericParamDef>,
2224 }
2225
2226 /// A representation of a Type suitable for hyperlinking purposes. Ideally one can get the original
2227 /// type out of the AST/TyCtxt given one of these, if more information is needed. Most importantly
2228 /// it does not preserve mutability or boxes.
2229 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2230 pub enum Type {
2231     /// Structs/enums/traits (most that'd be an `hir::TyKind::Path`).
2232     ResolvedPath {
2233         path: Path,
2234         typarams: Option<Vec<GenericBound>>,
2235         did: DefId,
2236         /// `true` if is a `T::Name` path for associated types.
2237         is_generic: bool,
2238     },
2239     /// For parameterized types, so the consumer of the JSON don't go
2240     /// looking for types which don't exist anywhere.
2241     Generic(String),
2242     /// Primitives are the fixed-size numeric types (plus int/usize/float), char,
2243     /// arrays, slices, and tuples.
2244     Primitive(PrimitiveType),
2245     /// extern "ABI" fn
2246     BareFunction(Box<BareFunctionDecl>),
2247     Tuple(Vec<Type>),
2248     Slice(Box<Type>),
2249     Array(Box<Type>, String),
2250     Never,
2251     Unique(Box<Type>),
2252     RawPointer(Mutability, Box<Type>),
2253     BorrowedRef {
2254         lifetime: Option<Lifetime>,
2255         mutability: Mutability,
2256         type_: Box<Type>,
2257     },
2258
2259     // <Type as Trait>::Name
2260     QPath {
2261         name: String,
2262         self_type: Box<Type>,
2263         trait_: Box<Type>
2264     },
2265
2266     // _
2267     Infer,
2268
2269     // impl TraitA+TraitB
2270     ImplTrait(Vec<GenericBound>),
2271 }
2272
2273 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Copy, Debug)]
2274 pub enum PrimitiveType {
2275     Isize, I8, I16, I32, I64, I128,
2276     Usize, U8, U16, U32, U64, U128,
2277     F32, F64,
2278     Char,
2279     Bool,
2280     Str,
2281     Slice,
2282     Array,
2283     Tuple,
2284     Unit,
2285     RawPointer,
2286     Reference,
2287     Fn,
2288     Never,
2289 }
2290
2291 #[derive(Clone, RustcEncodable, RustcDecodable, Copy, Debug)]
2292 pub enum TypeKind {
2293     Enum,
2294     Function,
2295     Module,
2296     Const,
2297     Static,
2298     Struct,
2299     Union,
2300     Trait,
2301     Variant,
2302     Typedef,
2303     Foreign,
2304     Macro,
2305     Attr,
2306     Derive,
2307     TraitAlias,
2308 }
2309
2310 pub trait GetDefId {
2311     fn def_id(&self) -> Option<DefId>;
2312 }
2313
2314 impl<T: GetDefId> GetDefId for Option<T> {
2315     fn def_id(&self) -> Option<DefId> {
2316         self.as_ref().and_then(|d| d.def_id())
2317     }
2318 }
2319
2320 impl Type {
2321     pub fn primitive_type(&self) -> Option<PrimitiveType> {
2322         match *self {
2323             Primitive(p) | BorrowedRef { type_: box Primitive(p), ..} => Some(p),
2324             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
2325             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
2326             Tuple(ref tys) => if tys.is_empty() {
2327                 Some(PrimitiveType::Unit)
2328             } else {
2329                 Some(PrimitiveType::Tuple)
2330             },
2331             RawPointer(..) => Some(PrimitiveType::RawPointer),
2332             BorrowedRef { type_: box Generic(..), .. } => Some(PrimitiveType::Reference),
2333             BareFunction(..) => Some(PrimitiveType::Fn),
2334             Never => Some(PrimitiveType::Never),
2335             _ => None,
2336         }
2337     }
2338
2339     pub fn is_generic(&self) -> bool {
2340         match *self {
2341             ResolvedPath { is_generic, .. } => is_generic,
2342             _ => false,
2343         }
2344     }
2345
2346     pub fn is_self_type(&self) -> bool {
2347         match *self {
2348             Generic(ref name) => name == "Self",
2349             _ => false
2350         }
2351     }
2352
2353     pub fn generics(&self) -> Option<&[Type]> {
2354         match *self {
2355             ResolvedPath { ref path, .. } => {
2356                 path.segments.last().and_then(|seg| {
2357                     if let GenericArgs::AngleBracketed { ref types, .. } = seg.args {
2358                         Some(&**types)
2359                     } else {
2360                         None
2361                     }
2362                 })
2363             }
2364             _ => None,
2365         }
2366     }
2367
2368     pub fn bindings(&self) -> Option<&[TypeBinding]> {
2369         match *self {
2370             ResolvedPath { ref path, .. } => {
2371                 path.segments.last().and_then(|seg| {
2372                     if let GenericArgs::AngleBracketed { ref bindings, .. } = seg.args {
2373                         Some(&**bindings)
2374                     } else {
2375                         None
2376                     }
2377                 })
2378             }
2379             _ => None
2380         }
2381     }
2382 }
2383
2384 impl GetDefId for Type {
2385     fn def_id(&self) -> Option<DefId> {
2386         match *self {
2387             ResolvedPath { did, .. } => Some(did),
2388             Primitive(p) => ::html::render::cache().primitive_locations.get(&p).cloned(),
2389             BorrowedRef { type_: box Generic(..), .. } =>
2390                 Primitive(PrimitiveType::Reference).def_id(),
2391             BorrowedRef { ref type_, .. } => type_.def_id(),
2392             Tuple(ref tys) => if tys.is_empty() {
2393                 Primitive(PrimitiveType::Unit).def_id()
2394             } else {
2395                 Primitive(PrimitiveType::Tuple).def_id()
2396             },
2397             BareFunction(..) => Primitive(PrimitiveType::Fn).def_id(),
2398             Never => Primitive(PrimitiveType::Never).def_id(),
2399             Slice(..) => Primitive(PrimitiveType::Slice).def_id(),
2400             Array(..) => Primitive(PrimitiveType::Array).def_id(),
2401             RawPointer(..) => Primitive(PrimitiveType::RawPointer).def_id(),
2402             QPath { ref self_type, .. } => self_type.def_id(),
2403             _ => None,
2404         }
2405     }
2406 }
2407
2408 impl PrimitiveType {
2409     fn from_str(s: &str) -> Option<PrimitiveType> {
2410         match s {
2411             "isize" => Some(PrimitiveType::Isize),
2412             "i8" => Some(PrimitiveType::I8),
2413             "i16" => Some(PrimitiveType::I16),
2414             "i32" => Some(PrimitiveType::I32),
2415             "i64" => Some(PrimitiveType::I64),
2416             "i128" => Some(PrimitiveType::I128),
2417             "usize" => Some(PrimitiveType::Usize),
2418             "u8" => Some(PrimitiveType::U8),
2419             "u16" => Some(PrimitiveType::U16),
2420             "u32" => Some(PrimitiveType::U32),
2421             "u64" => Some(PrimitiveType::U64),
2422             "u128" => Some(PrimitiveType::U128),
2423             "bool" => Some(PrimitiveType::Bool),
2424             "char" => Some(PrimitiveType::Char),
2425             "str" => Some(PrimitiveType::Str),
2426             "f32" => Some(PrimitiveType::F32),
2427             "f64" => Some(PrimitiveType::F64),
2428             "array" => Some(PrimitiveType::Array),
2429             "slice" => Some(PrimitiveType::Slice),
2430             "tuple" => Some(PrimitiveType::Tuple),
2431             "unit" => Some(PrimitiveType::Unit),
2432             "pointer" => Some(PrimitiveType::RawPointer),
2433             "reference" => Some(PrimitiveType::Reference),
2434             "fn" => Some(PrimitiveType::Fn),
2435             "never" => Some(PrimitiveType::Never),
2436             _ => None,
2437         }
2438     }
2439
2440     pub fn as_str(&self) -> &'static str {
2441         use self::PrimitiveType::*;
2442         match *self {
2443             Isize => "isize",
2444             I8 => "i8",
2445             I16 => "i16",
2446             I32 => "i32",
2447             I64 => "i64",
2448             I128 => "i128",
2449             Usize => "usize",
2450             U8 => "u8",
2451             U16 => "u16",
2452             U32 => "u32",
2453             U64 => "u64",
2454             U128 => "u128",
2455             F32 => "f32",
2456             F64 => "f64",
2457             Str => "str",
2458             Bool => "bool",
2459             Char => "char",
2460             Array => "array",
2461             Slice => "slice",
2462             Tuple => "tuple",
2463             Unit => "unit",
2464             RawPointer => "pointer",
2465             Reference => "reference",
2466             Fn => "fn",
2467             Never => "never",
2468         }
2469     }
2470
2471     pub fn to_url_str(&self) -> &'static str {
2472         self.as_str()
2473     }
2474 }
2475
2476 impl From<ast::IntTy> for PrimitiveType {
2477     fn from(int_ty: ast::IntTy) -> PrimitiveType {
2478         match int_ty {
2479             ast::IntTy::Isize => PrimitiveType::Isize,
2480             ast::IntTy::I8 => PrimitiveType::I8,
2481             ast::IntTy::I16 => PrimitiveType::I16,
2482             ast::IntTy::I32 => PrimitiveType::I32,
2483             ast::IntTy::I64 => PrimitiveType::I64,
2484             ast::IntTy::I128 => PrimitiveType::I128,
2485         }
2486     }
2487 }
2488
2489 impl From<ast::UintTy> for PrimitiveType {
2490     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
2491         match uint_ty {
2492             ast::UintTy::Usize => PrimitiveType::Usize,
2493             ast::UintTy::U8 => PrimitiveType::U8,
2494             ast::UintTy::U16 => PrimitiveType::U16,
2495             ast::UintTy::U32 => PrimitiveType::U32,
2496             ast::UintTy::U64 => PrimitiveType::U64,
2497             ast::UintTy::U128 => PrimitiveType::U128,
2498         }
2499     }
2500 }
2501
2502 impl From<ast::FloatTy> for PrimitiveType {
2503     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
2504         match float_ty {
2505             ast::FloatTy::F32 => PrimitiveType::F32,
2506             ast::FloatTy::F64 => PrimitiveType::F64,
2507         }
2508     }
2509 }
2510
2511 impl Clean<Type> for hir::Ty {
2512     fn clean(&self, cx: &DocContext) -> Type {
2513         use rustc::hir::*;
2514
2515         match self.node {
2516             TyKind::Never => Never,
2517             TyKind::Ptr(ref m) => RawPointer(m.mutbl.clean(cx), box m.ty.clean(cx)),
2518             TyKind::Rptr(ref l, ref m) => {
2519                 let lifetime = if l.is_elided() {
2520                     None
2521                 } else {
2522                     Some(l.clean(cx))
2523                 };
2524                 BorrowedRef {lifetime: lifetime, mutability: m.mutbl.clean(cx),
2525                              type_: box m.ty.clean(cx)}
2526             }
2527             TyKind::Slice(ref ty) => Slice(box ty.clean(cx)),
2528             TyKind::Array(ref ty, ref length) => {
2529                 let def_id = cx.tcx.hir().local_def_id(length.id);
2530                 let param_env = cx.tcx.param_env(def_id);
2531                 let substs = Substs::identity_for_item(cx.tcx, def_id);
2532                 let cid = GlobalId {
2533                     instance: ty::Instance::new(def_id, substs),
2534                     promoted: None
2535                 };
2536                 let length = match cx.tcx.const_eval(param_env.and(cid)) {
2537                     Ok(length) => print_const(cx, ty::LazyConst::Evaluated(length)),
2538                     Err(_) => "_".to_string(),
2539                 };
2540                 Array(box ty.clean(cx), length)
2541             },
2542             TyKind::Tup(ref tys) => Tuple(tys.clean(cx)),
2543             TyKind::Def(item_id, _) => {
2544                 let item = cx.tcx.hir().expect_item(item_id.id);
2545                 if let hir::ItemKind::Existential(ref ty) = item.node {
2546                     ImplTrait(ty.bounds.clean(cx))
2547                 } else {
2548                     unreachable!()
2549                 }
2550             }
2551             TyKind::Path(hir::QPath::Resolved(None, ref path)) => {
2552                 if let Some(new_ty) = cx.ty_substs.borrow().get(&path.def).cloned() {
2553                     return new_ty;
2554                 }
2555
2556                 if let Def::TyParam(did) = path.def {
2557                     if let Some(bounds) = cx.impl_trait_bounds.borrow_mut().remove(&did) {
2558                         return ImplTrait(bounds);
2559                     }
2560                 }
2561
2562                 let mut alias = None;
2563                 if let Def::TyAlias(def_id) = path.def {
2564                     // Substitute private type aliases
2565                     if let Some(node_id) = cx.tcx.hir().as_local_node_id(def_id) {
2566                         if !cx.renderinfo.borrow().access_levels.is_exported(def_id) {
2567                             alias = Some(&cx.tcx.hir().expect_item(node_id).node);
2568                         }
2569                     }
2570                 };
2571
2572                 if let Some(&hir::ItemKind::Ty(ref ty, ref generics)) = alias {
2573                     let provided_params = &path.segments.last().expect("segments were empty");
2574                     let mut ty_substs = FxHashMap::default();
2575                     let mut lt_substs = FxHashMap::default();
2576                     let mut const_substs = FxHashMap::default();
2577                     provided_params.with_generic_args(|generic_args| {
2578                         let mut indices: GenericParamCount = Default::default();
2579                         for param in generics.params.iter() {
2580                             match param.kind {
2581                                 hir::GenericParamKind::Lifetime { .. } => {
2582                                     let mut j = 0;
2583                                     let lifetime = generic_args.args.iter().find_map(|arg| {
2584                                         match arg {
2585                                             hir::GenericArg::Lifetime(lt) => {
2586                                                 if indices.lifetimes == j {
2587                                                     return Some(lt);
2588                                                 }
2589                                                 j += 1;
2590                                                 None
2591                                             }
2592                                             _ => None,
2593                                         }
2594                                     });
2595                                     if let Some(lt) = lifetime.cloned() {
2596                                         if !lt.is_elided() {
2597                                             let lt_def_id =
2598                                                 cx.tcx.hir().local_def_id(param.id);
2599                                             lt_substs.insert(lt_def_id, lt.clean(cx));
2600                                         }
2601                                     }
2602                                     indices.lifetimes += 1;
2603                                 }
2604                                 hir::GenericParamKind::Type { ref default, .. } => {
2605                                     let ty_param_def =
2606                                         Def::TyParam(cx.tcx.hir().local_def_id(param.id));
2607                                     let mut j = 0;
2608                                     let type_ = generic_args.args.iter().find_map(|arg| {
2609                                         match arg {
2610                                             hir::GenericArg::Type(ty) => {
2611                                                 if indices.types == j {
2612                                                     return Some(ty);
2613                                                 }
2614                                                 j += 1;
2615                                                 None
2616                                             }
2617                                             _ => None,
2618                                         }
2619                                     });
2620                                     if let Some(ty) = type_.cloned() {
2621                                         ty_substs.insert(ty_param_def, ty.clean(cx));
2622                                     } else if let Some(default) = default.clone() {
2623                                         ty_substs.insert(ty_param_def,
2624                                                          default.into_inner().clean(cx));
2625                                     }
2626                                     indices.types += 1;
2627                                 }
2628                                 hir::GenericParamKind::Const { .. } => {
2629                                     let const_param_def =
2630                                         Def::ConstParam(cx.tcx.hir().local_def_id(param.id));
2631                                     let mut j = 0;
2632                                     let const_ = generic_args.args.iter().find_map(|arg| {
2633                                         match arg {
2634                                             hir::GenericArg::Const(ct) => {
2635                                                 if indices.consts == j {
2636                                                     return Some(ct);
2637                                                 }
2638                                                 j += 1;
2639                                                 None
2640                                             }
2641                                             _ => None,
2642                                         }
2643                                     });
2644                                     if let Some(ct) = const_.cloned() {
2645                                         const_substs.insert(const_param_def, ct.clean(cx));
2646                                     }
2647                                     // FIXME(const_generics:defaults)
2648                                     indices.consts += 1;
2649                                 }
2650                             }
2651                         }
2652                     });
2653                     return cx.enter_alias(ty_substs, lt_substs, const_substs, || ty.clean(cx));
2654                 }
2655                 resolve_type(cx, path.clean(cx), self.id)
2656             }
2657             TyKind::Path(hir::QPath::Resolved(Some(ref qself), ref p)) => {
2658                 let mut segments: Vec<_> = p.segments.clone().into();
2659                 segments.pop();
2660                 let trait_path = hir::Path {
2661                     span: p.span,
2662                     def: Def::Trait(cx.tcx.associated_item(p.def.def_id()).container.id()),
2663                     segments: segments.into(),
2664                 };
2665                 Type::QPath {
2666                     name: p.segments.last().expect("segments were empty").ident.name.clean(cx),
2667                     self_type: box qself.clean(cx),
2668                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
2669                 }
2670             }
2671             TyKind::Path(hir::QPath::TypeRelative(ref qself, ref segment)) => {
2672                 let mut def = Def::Err;
2673                 let ty = hir_ty_to_ty(cx.tcx, self);
2674                 if let ty::Projection(proj) = ty.sty {
2675                     def = Def::Trait(proj.trait_ref(cx.tcx).def_id);
2676                 }
2677                 let trait_path = hir::Path {
2678                     span: self.span,
2679                     def,
2680                     segments: vec![].into(),
2681                 };
2682                 Type::QPath {
2683                     name: segment.ident.name.clean(cx),
2684                     self_type: box qself.clean(cx),
2685                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
2686                 }
2687             }
2688             TyKind::TraitObject(ref bounds, ref lifetime) => {
2689                 match bounds[0].clean(cx).trait_ {
2690                     ResolvedPath { path, typarams: None, did, is_generic } => {
2691                         let mut bounds: Vec<self::GenericBound> = bounds[1..].iter().map(|bound| {
2692                             self::GenericBound::TraitBound(bound.clean(cx),
2693                                                            hir::TraitBoundModifier::None)
2694                         }).collect();
2695                         if !lifetime.is_elided() {
2696                             bounds.push(self::GenericBound::Outlives(lifetime.clean(cx)));
2697                         }
2698                         ResolvedPath { path, typarams: Some(bounds), did, is_generic, }
2699                     }
2700                     _ => Infer // shouldn't happen
2701                 }
2702             }
2703             TyKind::BareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
2704             TyKind::Infer | TyKind::Err => Infer,
2705             TyKind::Typeof(..) => panic!("Unimplemented type {:?}", self.node),
2706         }
2707     }
2708 }
2709
2710 impl<'tcx> Clean<Type> for Ty<'tcx> {
2711     fn clean(&self, cx: &DocContext) -> Type {
2712         match self.sty {
2713             ty::Never => Never,
2714             ty::Bool => Primitive(PrimitiveType::Bool),
2715             ty::Char => Primitive(PrimitiveType::Char),
2716             ty::Int(int_ty) => Primitive(int_ty.into()),
2717             ty::Uint(uint_ty) => Primitive(uint_ty.into()),
2718             ty::Float(float_ty) => Primitive(float_ty.into()),
2719             ty::Str => Primitive(PrimitiveType::Str),
2720             ty::Slice(ty) => Slice(box ty.clean(cx)),
2721             ty::Array(ty, n) => {
2722                 let mut n = *cx.tcx.lift(&n).expect("array lift failed");
2723                 if let ty::LazyConst::Unevaluated(def_id, substs) = n {
2724                     let param_env = cx.tcx.param_env(def_id);
2725                     let cid = GlobalId {
2726                         instance: ty::Instance::new(def_id, substs),
2727                         promoted: None
2728                     };
2729                     if let Ok(new_n) = cx.tcx.const_eval(param_env.and(cid)) {
2730                         n = ty::LazyConst::Evaluated(new_n);
2731                     }
2732                 };
2733                 let n = print_const(cx, n);
2734                 Array(box ty.clean(cx), n)
2735             }
2736             ty::RawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
2737             ty::Ref(r, ty, mutbl) => BorrowedRef {
2738                 lifetime: r.clean(cx),
2739                 mutability: mutbl.clean(cx),
2740                 type_: box ty.clean(cx),
2741             },
2742             ty::FnDef(..) |
2743             ty::FnPtr(_) => {
2744                 let ty = cx.tcx.lift(self).expect("FnPtr lift failed");
2745                 let sig = ty.fn_sig(cx.tcx);
2746                 BareFunction(box BareFunctionDecl {
2747                     unsafety: sig.unsafety(),
2748                     generic_params: Vec::new(),
2749                     decl: (cx.tcx.hir().local_def_id(ast::CRATE_NODE_ID), sig).clean(cx),
2750                     abi: sig.abi(),
2751                 })
2752             }
2753             ty::Adt(def, substs) => {
2754                 let did = def.did;
2755                 let kind = match def.adt_kind() {
2756                     AdtKind::Struct => TypeKind::Struct,
2757                     AdtKind::Union => TypeKind::Union,
2758                     AdtKind::Enum => TypeKind::Enum,
2759                 };
2760                 inline::record_extern_fqn(cx, did, kind);
2761                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
2762                                          None, false, vec![], substs);
2763                 ResolvedPath {
2764                     path,
2765                     typarams: None,
2766                     did,
2767                     is_generic: false,
2768                 }
2769             }
2770             ty::Foreign(did) => {
2771                 inline::record_extern_fqn(cx, did, TypeKind::Foreign);
2772                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
2773                                          None, false, vec![], Substs::empty());
2774                 ResolvedPath {
2775                     path: path,
2776                     typarams: None,
2777                     did: did,
2778                     is_generic: false,
2779                 }
2780             }
2781             ty::Dynamic(ref obj, ref reg) => {
2782                 // HACK: pick the first `did` as the `did` of the trait object. Someone
2783                 // might want to implement "native" support for marker-trait-only
2784                 // trait objects.
2785                 let mut dids = obj.principal_def_id().into_iter().chain(obj.auto_traits());
2786                 let did = dids.next().unwrap_or_else(|| {
2787                     panic!("found trait object `{:?}` with no traits?", self)
2788                 });
2789                 let substs = match obj.principal() {
2790                     Some(principal) => principal.skip_binder().substs,
2791                     // marker traits have no substs.
2792                     _ => cx.tcx.intern_substs(&[])
2793                 };
2794
2795                 inline::record_extern_fqn(cx, did, TypeKind::Trait);
2796
2797                 let mut typarams = vec![];
2798                 reg.clean(cx).map(|b| typarams.push(GenericBound::Outlives(b)));
2799                 for did in dids {
2800                     let empty = cx.tcx.intern_substs(&[]);
2801                     let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
2802                         Some(did), false, vec![], empty);
2803                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
2804                     let bound = GenericBound::TraitBound(PolyTrait {
2805                         trait_: ResolvedPath {
2806                             path,
2807                             typarams: None,
2808                             did,
2809                             is_generic: false,
2810                         },
2811                         generic_params: Vec::new(),
2812                     }, hir::TraitBoundModifier::None);
2813                     typarams.push(bound);
2814                 }
2815
2816                 let mut bindings = vec![];
2817                 for pb in obj.projection_bounds() {
2818                     bindings.push(TypeBinding {
2819                         name: cx.tcx.associated_item(pb.item_def_id()).ident.name.clean(cx),
2820                         ty: pb.skip_binder().ty.clean(cx)
2821                     });
2822                 }
2823
2824                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(), Some(did),
2825                     false, bindings, substs);
2826                 ResolvedPath {
2827                     path,
2828                     typarams: Some(typarams),
2829                     did,
2830                     is_generic: false,
2831                 }
2832             }
2833             ty::Tuple(ref t) => Tuple(t.clean(cx)),
2834
2835             ty::Projection(ref data) => data.clean(cx),
2836
2837             ty::Param(ref p) => Generic(p.name.to_string()),
2838
2839             ty::Opaque(def_id, substs) => {
2840                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
2841                 // by looking up the projections associated with the def_id.
2842                 let predicates_of = cx.tcx.predicates_of(def_id);
2843                 let substs = cx.tcx.lift(&substs).expect("Opaque lift failed");
2844                 let bounds = predicates_of.instantiate(cx.tcx, substs);
2845                 let mut regions = vec![];
2846                 let mut has_sized = false;
2847                 let mut bounds = bounds.predicates.iter().filter_map(|predicate| {
2848                     let trait_ref = if let Some(tr) = predicate.to_opt_poly_trait_ref() {
2849                         tr
2850                     } else if let ty::Predicate::TypeOutlives(pred) = *predicate {
2851                         // these should turn up at the end
2852                         pred.skip_binder().1.clean(cx).map(|r| {
2853                             regions.push(GenericBound::Outlives(r))
2854                         });
2855                         return None;
2856                     } else {
2857                         return None;
2858                     };
2859
2860                     if let Some(sized) = cx.tcx.lang_items().sized_trait() {
2861                         if trait_ref.def_id() == sized {
2862                             has_sized = true;
2863                             return None;
2864                         }
2865                     }
2866
2867                     let bounds = bounds.predicates.iter().filter_map(|pred|
2868                         if let ty::Predicate::Projection(proj) = *pred {
2869                             let proj = proj.skip_binder();
2870                             if proj.projection_ty.trait_ref(cx.tcx) == *trait_ref.skip_binder() {
2871                                 Some(TypeBinding {
2872                                     name: cx.tcx.associated_item(proj.projection_ty.item_def_id)
2873                                                 .ident.name.clean(cx),
2874                                     ty: proj.ty.clean(cx),
2875                                 })
2876                             } else {
2877                                 None
2878                             }
2879                         } else {
2880                             None
2881                         }
2882                     ).collect();
2883
2884                     Some((trait_ref.skip_binder(), bounds).clean(cx))
2885                 }).collect::<Vec<_>>();
2886                 bounds.extend(regions);
2887                 if !has_sized && !bounds.is_empty() {
2888                     bounds.insert(0, GenericBound::maybe_sized(cx));
2889                 }
2890                 ImplTrait(bounds)
2891             }
2892
2893             ty::Closure(..) | ty::Generator(..) => Tuple(vec![]), // FIXME(pcwalton)
2894
2895             ty::Bound(..) => panic!("Bound"),
2896             ty::Placeholder(..) => panic!("Placeholder"),
2897             ty::UnnormalizedProjection(..) => panic!("UnnormalizedProjection"),
2898             ty::GeneratorWitness(..) => panic!("GeneratorWitness"),
2899             ty::Infer(..) => panic!("Infer"),
2900             ty::Error => panic!("Error"),
2901         }
2902     }
2903 }
2904
2905 impl Clean<Item> for hir::StructField {
2906     fn clean(&self, cx: &DocContext) -> Item {
2907         Item {
2908             name: Some(self.ident.name).clean(cx),
2909             attrs: self.attrs.clean(cx),
2910             source: self.span.clean(cx),
2911             visibility: self.vis.clean(cx),
2912             stability: get_stability(cx, cx.tcx.hir().local_def_id(self.id)),
2913             deprecation: get_deprecation(cx, cx.tcx.hir().local_def_id(self.id)),
2914             def_id: cx.tcx.hir().local_def_id(self.id),
2915             inner: StructFieldItem(self.ty.clean(cx)),
2916         }
2917     }
2918 }
2919
2920 impl<'tcx> Clean<Item> for ty::FieldDef {
2921     fn clean(&self, cx: &DocContext) -> Item {
2922         Item {
2923             name: Some(self.ident.name).clean(cx),
2924             attrs: cx.tcx.get_attrs(self.did).clean(cx),
2925             source: cx.tcx.def_span(self.did).clean(cx),
2926             visibility: self.vis.clean(cx),
2927             stability: get_stability(cx, self.did),
2928             deprecation: get_deprecation(cx, self.did),
2929             def_id: self.did,
2930             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
2931         }
2932     }
2933 }
2934
2935 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug)]
2936 pub enum Visibility {
2937     Public,
2938     Inherited,
2939     Crate,
2940     Restricted(DefId, Path),
2941 }
2942
2943 impl Clean<Option<Visibility>> for hir::Visibility {
2944     fn clean(&self, cx: &DocContext) -> Option<Visibility> {
2945         Some(match self.node {
2946             hir::VisibilityKind::Public => Visibility::Public,
2947             hir::VisibilityKind::Inherited => Visibility::Inherited,
2948             hir::VisibilityKind::Crate(_) => Visibility::Crate,
2949             hir::VisibilityKind::Restricted { ref path, .. } => {
2950                 let path = path.clean(cx);
2951                 let did = register_def(cx, path.def);
2952                 Visibility::Restricted(did, path)
2953             }
2954         })
2955     }
2956 }
2957
2958 impl Clean<Option<Visibility>> for ty::Visibility {
2959     fn clean(&self, _: &DocContext) -> Option<Visibility> {
2960         Some(if *self == ty::Visibility::Public { Public } else { Inherited })
2961     }
2962 }
2963
2964 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2965 pub struct Struct {
2966     pub struct_type: doctree::StructType,
2967     pub generics: Generics,
2968     pub fields: Vec<Item>,
2969     pub fields_stripped: bool,
2970 }
2971
2972 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2973 pub struct Union {
2974     pub struct_type: doctree::StructType,
2975     pub generics: Generics,
2976     pub fields: Vec<Item>,
2977     pub fields_stripped: bool,
2978 }
2979
2980 impl Clean<Item> for doctree::Struct {
2981     fn clean(&self, cx: &DocContext) -> Item {
2982         Item {
2983             name: Some(self.name.clean(cx)),
2984             attrs: self.attrs.clean(cx),
2985             source: self.whence.clean(cx),
2986             def_id: cx.tcx.hir().local_def_id(self.id),
2987             visibility: self.vis.clean(cx),
2988             stability: self.stab.clean(cx),
2989             deprecation: self.depr.clean(cx),
2990             inner: StructItem(Struct {
2991                 struct_type: self.struct_type,
2992                 generics: self.generics.clean(cx),
2993                 fields: self.fields.clean(cx),
2994                 fields_stripped: false,
2995             }),
2996         }
2997     }
2998 }
2999
3000 impl Clean<Item> for doctree::Union {
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(self.id),
3007             visibility: self.vis.clean(cx),
3008             stability: self.stab.clean(cx),
3009             deprecation: self.depr.clean(cx),
3010             inner: UnionItem(Union {
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 /// This is a more limited form of the standard Struct, different in that
3021 /// it lacks the things most items have (name, id, parameterization). Found
3022 /// only as a variant in an enum.
3023 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3024 pub struct VariantStruct {
3025     pub struct_type: doctree::StructType,
3026     pub fields: Vec<Item>,
3027     pub fields_stripped: bool,
3028 }
3029
3030 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
3031     fn clean(&self, cx: &DocContext) -> VariantStruct {
3032         VariantStruct {
3033             struct_type: doctree::struct_type_from_def(self),
3034             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
3035             fields_stripped: false,
3036         }
3037     }
3038 }
3039
3040 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3041 pub struct Enum {
3042     pub variants: IndexVec<VariantIdx, Item>,
3043     pub generics: Generics,
3044     pub variants_stripped: bool,
3045 }
3046
3047 impl Clean<Item> for doctree::Enum {
3048     fn clean(&self, cx: &DocContext) -> Item {
3049         Item {
3050             name: Some(self.name.clean(cx)),
3051             attrs: self.attrs.clean(cx),
3052             source: self.whence.clean(cx),
3053             def_id: cx.tcx.hir().local_def_id(self.id),
3054             visibility: self.vis.clean(cx),
3055             stability: self.stab.clean(cx),
3056             deprecation: self.depr.clean(cx),
3057             inner: EnumItem(Enum {
3058                 variants: self.variants.iter().map(|v| v.clean(cx)).collect(),
3059                 generics: self.generics.clean(cx),
3060                 variants_stripped: false,
3061             }),
3062         }
3063     }
3064 }
3065
3066 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3067 pub struct Variant {
3068     pub kind: VariantKind,
3069 }
3070
3071 impl Clean<Item> for doctree::Variant {
3072     fn clean(&self, cx: &DocContext) -> Item {
3073         Item {
3074             name: Some(self.name.clean(cx)),
3075             attrs: self.attrs.clean(cx),
3076             source: self.whence.clean(cx),
3077             visibility: None,
3078             stability: self.stab.clean(cx),
3079             deprecation: self.depr.clean(cx),
3080             def_id: cx.tcx.hir().local_def_id(self.def.id()),
3081             inner: VariantItem(Variant {
3082                 kind: self.def.clean(cx),
3083             }),
3084         }
3085     }
3086 }
3087
3088 impl<'tcx> Clean<Item> for ty::VariantDef {
3089     fn clean(&self, cx: &DocContext) -> Item {
3090         let kind = match self.ctor_kind {
3091             CtorKind::Const => VariantKind::CLike,
3092             CtorKind::Fn => {
3093                 VariantKind::Tuple(
3094                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
3095                 )
3096             }
3097             CtorKind::Fictive => {
3098                 VariantKind::Struct(VariantStruct {
3099                     struct_type: doctree::Plain,
3100                     fields_stripped: false,
3101                     fields: self.fields.iter().map(|field| {
3102                         Item {
3103                             source: cx.tcx.def_span(field.did).clean(cx),
3104                             name: Some(field.ident.name.clean(cx)),
3105                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
3106                             visibility: field.vis.clean(cx),
3107                             def_id: field.did,
3108                             stability: get_stability(cx, field.did),
3109                             deprecation: get_deprecation(cx, field.did),
3110                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
3111                         }
3112                     }).collect()
3113                 })
3114             }
3115         };
3116         Item {
3117             name: Some(self.ident.clean(cx)),
3118             attrs: inline::load_attrs(cx, self.did),
3119             source: cx.tcx.def_span(self.did).clean(cx),
3120             visibility: Some(Inherited),
3121             def_id: self.did,
3122             inner: VariantItem(Variant { kind }),
3123             stability: get_stability(cx, self.did),
3124             deprecation: get_deprecation(cx, self.did),
3125         }
3126     }
3127 }
3128
3129 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3130 pub enum VariantKind {
3131     CLike,
3132     Tuple(Vec<Type>),
3133     Struct(VariantStruct),
3134 }
3135
3136 impl Clean<VariantKind> for hir::VariantData {
3137     fn clean(&self, cx: &DocContext) -> VariantKind {
3138         if self.is_struct() {
3139             VariantKind::Struct(self.clean(cx))
3140         } else if self.is_unit() {
3141             VariantKind::CLike
3142         } else {
3143             VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect())
3144         }
3145     }
3146 }
3147
3148 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3149 pub struct Span {
3150     pub filename: FileName,
3151     pub loline: usize,
3152     pub locol: usize,
3153     pub hiline: usize,
3154     pub hicol: usize,
3155 }
3156
3157 impl Span {
3158     pub fn empty() -> Span {
3159         Span {
3160             filename: FileName::Anon(0),
3161             loline: 0, locol: 0,
3162             hiline: 0, hicol: 0,
3163         }
3164     }
3165 }
3166
3167 impl Clean<Span> for syntax_pos::Span {
3168     fn clean(&self, cx: &DocContext) -> Span {
3169         if self.is_dummy() {
3170             return Span::empty();
3171         }
3172
3173         let cm = cx.sess().source_map();
3174         let filename = cm.span_to_filename(*self);
3175         let lo = cm.lookup_char_pos(self.lo());
3176         let hi = cm.lookup_char_pos(self.hi());
3177         Span {
3178             filename,
3179             loline: lo.line,
3180             locol: lo.col.to_usize(),
3181             hiline: hi.line,
3182             hicol: hi.col.to_usize(),
3183         }
3184     }
3185 }
3186
3187 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3188 pub struct Path {
3189     pub global: bool,
3190     pub def: Def,
3191     pub segments: Vec<PathSegment>,
3192 }
3193
3194 impl Path {
3195     pub fn last_name(&self) -> &str {
3196         self.segments.last().expect("segments were empty").name.as_str()
3197     }
3198 }
3199
3200 impl Clean<Path> for hir::Path {
3201     fn clean(&self, cx: &DocContext) -> Path {
3202         Path {
3203             global: self.is_global(),
3204             def: self.def,
3205             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
3206         }
3207     }
3208 }
3209
3210 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3211 pub enum GenericArgs {
3212     AngleBracketed {
3213         lifetimes: Vec<Lifetime>,
3214         types: Vec<Type>,
3215         bindings: Vec<TypeBinding>,
3216     },
3217     Parenthesized {
3218         inputs: Vec<Type>,
3219         output: Option<Type>,
3220     }
3221 }
3222
3223 impl Clean<GenericArgs> for hir::GenericArgs {
3224     fn clean(&self, cx: &DocContext) -> GenericArgs {
3225         if self.parenthesized {
3226             let output = self.bindings[0].ty.clean(cx);
3227             GenericArgs::Parenthesized {
3228                 inputs: self.inputs().clean(cx),
3229                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
3230             }
3231         } else {
3232             let (mut lifetimes, mut types) = (vec![], vec![]);
3233             let mut elided_lifetimes = true;
3234             for arg in &self.args {
3235                 match arg {
3236                     GenericArg::Lifetime(lt) => {
3237                         if !lt.is_elided() {
3238                             elided_lifetimes = false;
3239                         }
3240                         lifetimes.push(lt.clean(cx));
3241                     }
3242                     GenericArg::Type(ty) => {
3243                         types.push(ty.clean(cx));
3244                     }
3245                     GenericArg::Const(..) => {
3246                         unimplemented!() // FIXME(const_generics)
3247                     }
3248                 }
3249             }
3250             GenericArgs::AngleBracketed {
3251                 lifetimes: if elided_lifetimes { vec![] } else { lifetimes },
3252                 types,
3253                 bindings: self.bindings.clean(cx),
3254             }
3255         }
3256     }
3257 }
3258
3259 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3260 pub struct PathSegment {
3261     pub name: String,
3262     pub args: GenericArgs,
3263 }
3264
3265 impl Clean<PathSegment> for hir::PathSegment {
3266     fn clean(&self, cx: &DocContext) -> PathSegment {
3267         PathSegment {
3268             name: self.ident.name.clean(cx),
3269             args: self.with_generic_args(|generic_args| generic_args.clean(cx))
3270         }
3271     }
3272 }
3273
3274 fn strip_type(ty: Type) -> Type {
3275     match ty {
3276         Type::ResolvedPath { path, typarams, did, is_generic } => {
3277             Type::ResolvedPath { path: strip_path(&path), typarams, did, is_generic }
3278         }
3279         Type::Tuple(inner_tys) => {
3280             Type::Tuple(inner_tys.iter().map(|t| strip_type(t.clone())).collect())
3281         }
3282         Type::Slice(inner_ty) => Type::Slice(Box::new(strip_type(*inner_ty))),
3283         Type::Array(inner_ty, s) => Type::Array(Box::new(strip_type(*inner_ty)), s),
3284         Type::Unique(inner_ty) => Type::Unique(Box::new(strip_type(*inner_ty))),
3285         Type::RawPointer(m, inner_ty) => Type::RawPointer(m, Box::new(strip_type(*inner_ty))),
3286         Type::BorrowedRef { lifetime, mutability, type_ } => {
3287             Type::BorrowedRef { lifetime, mutability, type_: Box::new(strip_type(*type_)) }
3288         }
3289         Type::QPath { name, self_type, trait_ } => {
3290             Type::QPath {
3291                 name,
3292                 self_type: Box::new(strip_type(*self_type)), trait_: Box::new(strip_type(*trait_))
3293             }
3294         }
3295         _ => ty
3296     }
3297 }
3298
3299 fn strip_path(path: &Path) -> Path {
3300     let segments = path.segments.iter().map(|s| {
3301         PathSegment {
3302             name: s.name.clone(),
3303             args: GenericArgs::AngleBracketed {
3304                 lifetimes: Vec::new(),
3305                 types: Vec::new(),
3306                 bindings: Vec::new(),
3307             }
3308         }
3309     }).collect();
3310
3311     Path {
3312         global: path.global,
3313         def: path.def.clone(),
3314         segments,
3315     }
3316 }
3317
3318 fn qpath_to_string(p: &hir::QPath) -> String {
3319     let segments = match *p {
3320         hir::QPath::Resolved(_, ref path) => &path.segments,
3321         hir::QPath::TypeRelative(_, ref segment) => return segment.ident.to_string(),
3322     };
3323
3324     let mut s = String::new();
3325     for (i, seg) in segments.iter().enumerate() {
3326         if i > 0 {
3327             s.push_str("::");
3328         }
3329         if seg.ident.name != keywords::PathRoot.name() {
3330             s.push_str(&*seg.ident.as_str());
3331         }
3332     }
3333     s
3334 }
3335
3336 impl Clean<String> for Ident {
3337     #[inline]
3338     fn clean(&self, cx: &DocContext) -> String {
3339         self.name.clean(cx)
3340     }
3341 }
3342
3343 impl Clean<String> for ast::Name {
3344     #[inline]
3345     fn clean(&self, _: &DocContext) -> String {
3346         self.to_string()
3347     }
3348 }
3349
3350 impl Clean<String> for InternedString {
3351     #[inline]
3352     fn clean(&self, _: &DocContext) -> String {
3353         self.to_string()
3354     }
3355 }
3356
3357 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3358 pub struct Typedef {
3359     pub type_: Type,
3360     pub generics: Generics,
3361 }
3362
3363 impl Clean<Item> for doctree::Typedef {
3364     fn clean(&self, cx: &DocContext) -> Item {
3365         Item {
3366             name: Some(self.name.clean(cx)),
3367             attrs: self.attrs.clean(cx),
3368             source: self.whence.clean(cx),
3369             def_id: cx.tcx.hir().local_def_id(self.id.clone()),
3370             visibility: self.vis.clean(cx),
3371             stability: self.stab.clean(cx),
3372             deprecation: self.depr.clean(cx),
3373             inner: TypedefItem(Typedef {
3374                 type_: self.ty.clean(cx),
3375                 generics: self.gen.clean(cx),
3376             }, false),
3377         }
3378     }
3379 }
3380
3381 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3382 pub struct Existential {
3383     pub bounds: Vec<GenericBound>,
3384     pub generics: Generics,
3385 }
3386
3387 impl Clean<Item> for doctree::Existential {
3388     fn clean(&self, cx: &DocContext) -> Item {
3389         Item {
3390             name: Some(self.name.clean(cx)),
3391             attrs: self.attrs.clean(cx),
3392             source: self.whence.clean(cx),
3393             def_id: cx.tcx.hir().local_def_id(self.id.clone()),
3394             visibility: self.vis.clean(cx),
3395             stability: self.stab.clean(cx),
3396             deprecation: self.depr.clean(cx),
3397             inner: ExistentialItem(Existential {
3398                 bounds: self.exist_ty.bounds.clean(cx),
3399                 generics: self.exist_ty.generics.clean(cx),
3400             }, false),
3401         }
3402     }
3403 }
3404
3405 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3406 pub struct BareFunctionDecl {
3407     pub unsafety: hir::Unsafety,
3408     pub generic_params: Vec<GenericParamDef>,
3409     pub decl: FnDecl,
3410     pub abi: Abi,
3411 }
3412
3413 impl Clean<BareFunctionDecl> for hir::BareFnTy {
3414     fn clean(&self, cx: &DocContext) -> BareFunctionDecl {
3415         let (generic_params, decl) = enter_impl_trait(cx, || {
3416             (self.generic_params.clean(cx), (&*self.decl, &self.arg_names[..]).clean(cx))
3417         });
3418         BareFunctionDecl {
3419             unsafety: self.unsafety,
3420             abi: self.abi,
3421             decl,
3422             generic_params,
3423         }
3424     }
3425 }
3426
3427 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3428 pub struct Static {
3429     pub type_: Type,
3430     pub mutability: Mutability,
3431     /// It's useful to have the value of a static documented, but I have no
3432     /// desire to represent expressions (that'd basically be all of the AST,
3433     /// which is huge!). So, have a string.
3434     pub expr: String,
3435 }
3436
3437 impl Clean<Item> for doctree::Static {
3438     fn clean(&self, cx: &DocContext) -> Item {
3439         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
3440         Item {
3441             name: Some(self.name.clean(cx)),
3442             attrs: self.attrs.clean(cx),
3443             source: self.whence.clean(cx),
3444             def_id: cx.tcx.hir().local_def_id(self.id),
3445             visibility: self.vis.clean(cx),
3446             stability: self.stab.clean(cx),
3447             deprecation: self.depr.clean(cx),
3448             inner: StaticItem(Static {
3449                 type_: self.type_.clean(cx),
3450                 mutability: self.mutability.clean(cx),
3451                 expr: print_const_expr(cx, self.expr),
3452             }),
3453         }
3454     }
3455 }
3456
3457 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3458 pub struct Constant {
3459     pub type_: Type,
3460     pub expr: String,
3461 }
3462
3463 impl Clean<Item> for doctree::Constant {
3464     fn clean(&self, cx: &DocContext) -> Item {
3465         Item {
3466             name: Some(self.name.clean(cx)),
3467             attrs: self.attrs.clean(cx),
3468             source: self.whence.clean(cx),
3469             def_id: cx.tcx.hir().local_def_id(self.id),
3470             visibility: self.vis.clean(cx),
3471             stability: self.stab.clean(cx),
3472             deprecation: self.depr.clean(cx),
3473             inner: ConstantItem(Constant {
3474                 type_: self.type_.clean(cx),
3475                 expr: print_const_expr(cx, self.expr),
3476             }),
3477         }
3478     }
3479 }
3480
3481 #[derive(Debug, Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Hash)]
3482 pub enum Mutability {
3483     Mutable,
3484     Immutable,
3485 }
3486
3487 impl Clean<Mutability> for hir::Mutability {
3488     fn clean(&self, _: &DocContext) -> Mutability {
3489         match self {
3490             &hir::MutMutable => Mutable,
3491             &hir::MutImmutable => Immutable,
3492         }
3493     }
3494 }
3495
3496 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Debug, Hash)]
3497 pub enum ImplPolarity {
3498     Positive,
3499     Negative,
3500 }
3501
3502 impl Clean<ImplPolarity> for hir::ImplPolarity {
3503     fn clean(&self, _: &DocContext) -> ImplPolarity {
3504         match self {
3505             &hir::ImplPolarity::Positive => ImplPolarity::Positive,
3506             &hir::ImplPolarity::Negative => ImplPolarity::Negative,
3507         }
3508     }
3509 }
3510
3511 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3512 pub struct Impl {
3513     pub unsafety: hir::Unsafety,
3514     pub generics: Generics,
3515     pub provided_trait_methods: FxHashSet<String>,
3516     pub trait_: Option<Type>,
3517     pub for_: Type,
3518     pub items: Vec<Item>,
3519     pub polarity: Option<ImplPolarity>,
3520     pub synthetic: bool,
3521     pub blanket_impl: Option<Type>,
3522 }
3523
3524 pub fn get_auto_traits_with_node_id(cx: &DocContext, id: ast::NodeId, name: String) -> Vec<Item> {
3525     let finder = AutoTraitFinder::new(cx);
3526     finder.get_with_node_id(id, name)
3527 }
3528
3529 pub fn get_auto_traits_with_def_id(cx: &DocContext, id: DefId) -> Vec<Item> {
3530     let finder = AutoTraitFinder::new(cx);
3531
3532     finder.get_with_def_id(id)
3533 }
3534
3535 pub fn get_blanket_impls_with_node_id(cx: &DocContext, id: ast::NodeId, name: String) -> Vec<Item> {
3536     let finder = BlanketImplFinder::new(cx);
3537     finder.get_with_node_id(id, name)
3538 }
3539
3540 pub fn get_blanket_impls_with_def_id(cx: &DocContext, id: DefId) -> Vec<Item> {
3541     let finder = BlanketImplFinder::new(cx);
3542
3543     finder.get_with_def_id(id)
3544 }
3545
3546 impl Clean<Vec<Item>> for doctree::Impl {
3547     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3548         let mut ret = Vec::new();
3549         let trait_ = self.trait_.clean(cx);
3550         let items = self.items.clean(cx);
3551
3552         // If this impl block is an implementation of the Deref trait, then we
3553         // need to try inlining the target's inherent impl blocks as well.
3554         if trait_.def_id() == cx.tcx.lang_items().deref_trait() {
3555             build_deref_target_impls(cx, &items, &mut ret);
3556         }
3557
3558         let provided = trait_.def_id().map(|did| {
3559             cx.tcx.provided_trait_methods(did)
3560                   .into_iter()
3561                   .map(|meth| meth.ident.to_string())
3562                   .collect()
3563         }).unwrap_or_default();
3564
3565         ret.push(Item {
3566             name: None,
3567             attrs: self.attrs.clean(cx),
3568             source: self.whence.clean(cx),
3569             def_id: cx.tcx.hir().local_def_id(self.id),
3570             visibility: self.vis.clean(cx),
3571             stability: self.stab.clean(cx),
3572             deprecation: self.depr.clean(cx),
3573             inner: ImplItem(Impl {
3574                 unsafety: self.unsafety,
3575                 generics: self.generics.clean(cx),
3576                 provided_trait_methods: provided,
3577                 trait_,
3578                 for_: self.for_.clean(cx),
3579                 items,
3580                 polarity: Some(self.polarity.clean(cx)),
3581                 synthetic: false,
3582                 blanket_impl: None,
3583             })
3584         });
3585         ret
3586     }
3587 }
3588
3589 fn build_deref_target_impls(cx: &DocContext,
3590                             items: &[Item],
3591                             ret: &mut Vec<Item>) {
3592     use self::PrimitiveType::*;
3593     let tcx = cx.tcx;
3594
3595     for item in items {
3596         let target = match item.inner {
3597             TypedefItem(ref t, true) => &t.type_,
3598             _ => continue,
3599         };
3600         let primitive = match *target {
3601             ResolvedPath { did, .. } if did.is_local() => continue,
3602             ResolvedPath { did, .. } => {
3603                 ret.extend(inline::build_impls(cx, did));
3604                 continue
3605             }
3606             _ => match target.primitive_type() {
3607                 Some(prim) => prim,
3608                 None => continue,
3609             }
3610         };
3611         let did = match primitive {
3612             Isize => tcx.lang_items().isize_impl(),
3613             I8 => tcx.lang_items().i8_impl(),
3614             I16 => tcx.lang_items().i16_impl(),
3615             I32 => tcx.lang_items().i32_impl(),
3616             I64 => tcx.lang_items().i64_impl(),
3617             I128 => tcx.lang_items().i128_impl(),
3618             Usize => tcx.lang_items().usize_impl(),
3619             U8 => tcx.lang_items().u8_impl(),
3620             U16 => tcx.lang_items().u16_impl(),
3621             U32 => tcx.lang_items().u32_impl(),
3622             U64 => tcx.lang_items().u64_impl(),
3623             U128 => tcx.lang_items().u128_impl(),
3624             F32 => tcx.lang_items().f32_impl(),
3625             F64 => tcx.lang_items().f64_impl(),
3626             Char => tcx.lang_items().char_impl(),
3627             Bool => None,
3628             Str => tcx.lang_items().str_impl(),
3629             Slice => tcx.lang_items().slice_impl(),
3630             Array => tcx.lang_items().slice_impl(),
3631             Tuple => None,
3632             Unit => None,
3633             RawPointer => tcx.lang_items().const_ptr_impl(),
3634             Reference => None,
3635             Fn => None,
3636             Never => None,
3637         };
3638         if let Some(did) = did {
3639             if !did.is_local() {
3640                 inline::build_impl(cx, did, ret);
3641             }
3642         }
3643     }
3644 }
3645
3646 impl Clean<Vec<Item>> for doctree::ExternCrate {
3647     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3648
3649         let please_inline = self.vis.node.is_pub() && self.attrs.iter().any(|a| {
3650             a.name() == "doc" && match a.meta_item_list() {
3651                 Some(l) => attr::list_contains_name(&l, "inline"),
3652                 None => false,
3653             }
3654         });
3655
3656         if please_inline {
3657             let mut visited = FxHashSet::default();
3658
3659             let def = Def::Mod(DefId {
3660                 krate: self.cnum,
3661                 index: CRATE_DEF_INDEX,
3662             });
3663
3664             if let Some(items) = inline::try_inline(cx, def, self.name, &mut visited) {
3665                 return items;
3666             }
3667         }
3668
3669         vec![Item {
3670             name: None,
3671             attrs: self.attrs.clean(cx),
3672             source: self.whence.clean(cx),
3673             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
3674             visibility: self.vis.clean(cx),
3675             stability: None,
3676             deprecation: None,
3677             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
3678         }]
3679     }
3680 }
3681
3682 impl Clean<Vec<Item>> for doctree::Import {
3683     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3684         // We consider inlining the documentation of `pub use` statements, but we
3685         // forcefully don't inline if this is not public or if the
3686         // #[doc(no_inline)] attribute is present.
3687         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
3688         let mut denied = !self.vis.node.is_pub() || self.attrs.iter().any(|a| {
3689             a.name() == "doc" && match a.meta_item_list() {
3690                 Some(l) => attr::list_contains_name(&l, "no_inline") ||
3691                            attr::list_contains_name(&l, "hidden"),
3692                 None => false,
3693             }
3694         });
3695         // Also check whether imports were asked to be inlined, in case we're trying to re-export a
3696         // crate in Rust 2018+
3697         let please_inline = self.attrs.lists("doc").has_word("inline");
3698         let path = self.path.clean(cx);
3699         let inner = if self.glob {
3700             if !denied {
3701                 let mut visited = FxHashSet::default();
3702                 if let Some(items) = inline::try_inline_glob(cx, path.def, &mut visited) {
3703                     return items;
3704                 }
3705             }
3706
3707             Import::Glob(resolve_use_source(cx, path))
3708         } else {
3709             let name = self.name;
3710             if !please_inline {
3711                 match path.def {
3712                     Def::Mod(did) => if !did.is_local() && did.index == CRATE_DEF_INDEX {
3713                         // if we're `pub use`ing an extern crate root, don't inline it unless we
3714                         // were specifically asked for it
3715                         denied = true;
3716                     }
3717                     _ => {}
3718                 }
3719             }
3720             if !denied {
3721                 let mut visited = FxHashSet::default();
3722                 if let Some(items) = inline::try_inline(cx, path.def, name, &mut visited) {
3723                     return items;
3724                 }
3725             }
3726             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
3727         };
3728
3729         vec![Item {
3730             name: None,
3731             attrs: self.attrs.clean(cx),
3732             source: self.whence.clean(cx),
3733             def_id: cx.tcx.hir().local_def_id(ast::CRATE_NODE_ID),
3734             visibility: self.vis.clean(cx),
3735             stability: None,
3736             deprecation: None,
3737             inner: ImportItem(inner)
3738         }]
3739     }
3740 }
3741
3742 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3743 pub enum Import {
3744     // use source as str;
3745     Simple(String, ImportSource),
3746     // use source::*;
3747     Glob(ImportSource)
3748 }
3749
3750 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3751 pub struct ImportSource {
3752     pub path: Path,
3753     pub did: Option<DefId>,
3754 }
3755
3756 impl Clean<Vec<Item>> for hir::ForeignMod {
3757     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3758         let mut items = self.items.clean(cx);
3759         for item in &mut items {
3760             if let ForeignFunctionItem(ref mut f) = item.inner {
3761                 f.header.abi = self.abi;
3762             }
3763         }
3764         items
3765     }
3766 }
3767
3768 impl Clean<Item> for hir::ForeignItem {
3769     fn clean(&self, cx: &DocContext) -> Item {
3770         let inner = match self.node {
3771             hir::ForeignItemKind::Fn(ref decl, ref names, ref generics) => {
3772                 let (generics, decl) = enter_impl_trait(cx, || {
3773                     (generics.clean(cx), (&**decl, &names[..]).clean(cx))
3774                 });
3775                 ForeignFunctionItem(Function {
3776                     decl,
3777                     generics,
3778                     header: hir::FnHeader {
3779                         unsafety: hir::Unsafety::Unsafe,
3780                         abi: Abi::Rust,
3781                         constness: hir::Constness::NotConst,
3782                         asyncness: hir::IsAsync::NotAsync,
3783                     },
3784                 })
3785             }
3786             hir::ForeignItemKind::Static(ref ty, mutbl) => {
3787                 ForeignStaticItem(Static {
3788                     type_: ty.clean(cx),
3789                     mutability: if mutbl {Mutable} else {Immutable},
3790                     expr: String::new(),
3791                 })
3792             }
3793             hir::ForeignItemKind::Type => {
3794                 ForeignTypeItem
3795             }
3796         };
3797
3798         Item {
3799             name: Some(self.ident.clean(cx)),
3800             attrs: self.attrs.clean(cx),
3801             source: self.span.clean(cx),
3802             def_id: cx.tcx.hir().local_def_id(self.id),
3803             visibility: self.vis.clean(cx),
3804             stability: get_stability(cx, cx.tcx.hir().local_def_id(self.id)),
3805             deprecation: get_deprecation(cx, cx.tcx.hir().local_def_id(self.id)),
3806             inner,
3807         }
3808     }
3809 }
3810
3811 // Utilities
3812
3813 pub trait ToSource {
3814     fn to_src(&self, cx: &DocContext) -> String;
3815 }
3816
3817 impl ToSource for syntax_pos::Span {
3818     fn to_src(&self, cx: &DocContext) -> String {
3819         debug!("converting span {:?} to snippet", self.clean(cx));
3820         let sn = match cx.sess().source_map().span_to_snippet(*self) {
3821             Ok(x) => x,
3822             Err(_) => String::new()
3823         };
3824         debug!("got snippet {}", sn);
3825         sn
3826     }
3827 }
3828
3829 fn name_from_pat(p: &hir::Pat) -> String {
3830     use rustc::hir::*;
3831     debug!("Trying to get a name from pattern: {:?}", p);
3832
3833     match p.node {
3834         PatKind::Wild => "_".to_string(),
3835         PatKind::Binding(_, _, _, ident, _) => ident.to_string(),
3836         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
3837         PatKind::Struct(ref name, ref fields, etc) => {
3838             format!("{} {{ {}{} }}", qpath_to_string(name),
3839                 fields.iter().map(|&Spanned { node: ref fp, .. }|
3840                                   format!("{}: {}", fp.ident, name_from_pat(&*fp.pat)))
3841                              .collect::<Vec<String>>().join(", "),
3842                 if etc { ", .." } else { "" }
3843             )
3844         }
3845         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
3846                                             .collect::<Vec<String>>().join(", ")),
3847         PatKind::Box(ref p) => name_from_pat(&**p),
3848         PatKind::Ref(ref p, _) => name_from_pat(&**p),
3849         PatKind::Lit(..) => {
3850             warn!("tried to get argument name from PatKind::Lit, \
3851                   which is silly in function arguments");
3852             "()".to_string()
3853         },
3854         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
3855                               which is not allowed in function arguments"),
3856         PatKind::Slice(ref begin, ref mid, ref end) => {
3857             let begin = begin.iter().map(|p| name_from_pat(&**p));
3858             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
3859             let end = end.iter().map(|p| name_from_pat(&**p));
3860             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
3861         },
3862     }
3863 }
3864
3865 fn print_const(cx: &DocContext, n: ty::LazyConst) -> String {
3866     match n {
3867         ty::LazyConst::Unevaluated(def_id, _) => {
3868             if let Some(node_id) = cx.tcx.hir().as_local_node_id(def_id) {
3869                 print_const_expr(cx, cx.tcx.hir().body_owned_by(node_id))
3870             } else {
3871                 inline::print_inlined_const(cx, def_id)
3872             }
3873         },
3874         ty::LazyConst::Evaluated(n) => {
3875             let mut s = String::new();
3876             ::rustc::mir::fmt_const_val(&mut s, n).expect("fmt_const_val failed");
3877             // array lengths are obviously usize
3878             if s.ends_with("usize") {
3879                 let n = s.len() - "usize".len();
3880                 s.truncate(n);
3881             }
3882             s
3883         },
3884     }
3885 }
3886
3887 fn print_const_expr(cx: &DocContext, body: hir::BodyId) -> String {
3888     cx.tcx.hir().hir_to_pretty_string(body.hir_id)
3889 }
3890
3891 /// Given a type Path, resolve it to a Type using the TyCtxt
3892 fn resolve_type(cx: &DocContext,
3893                 path: Path,
3894                 id: ast::NodeId) -> Type {
3895     if id == ast::DUMMY_NODE_ID {
3896         debug!("resolve_type({:?})", path);
3897     } else {
3898         debug!("resolve_type({:?},{:?})", path, id);
3899     }
3900
3901     let is_generic = match path.def {
3902         Def::PrimTy(p) => match p {
3903             hir::Str => return Primitive(PrimitiveType::Str),
3904             hir::Bool => return Primitive(PrimitiveType::Bool),
3905             hir::Char => return Primitive(PrimitiveType::Char),
3906             hir::Int(int_ty) => return Primitive(int_ty.into()),
3907             hir::Uint(uint_ty) => return Primitive(uint_ty.into()),
3908             hir::Float(float_ty) => return Primitive(float_ty.into()),
3909         },
3910         Def::SelfTy(..) if path.segments.len() == 1 => {
3911             return Generic(keywords::SelfUpper.name().to_string());
3912         }
3913         Def::TyParam(..) if path.segments.len() == 1 => {
3914             return Generic(format!("{:#}", path));
3915         }
3916         Def::SelfTy(..) | Def::TyParam(..) | Def::AssociatedTy(..) => true,
3917         _ => false,
3918     };
3919     let did = register_def(&*cx, path.def);
3920     ResolvedPath { path: path, typarams: None, did: did, is_generic: is_generic }
3921 }
3922
3923 pub fn register_def(cx: &DocContext, def: Def) -> DefId {
3924     debug!("register_def({:?})", def);
3925
3926     let (did, kind) = match def {
3927         Def::Fn(i) => (i, TypeKind::Function),
3928         Def::TyAlias(i) => (i, TypeKind::Typedef),
3929         Def::Enum(i) => (i, TypeKind::Enum),
3930         Def::Trait(i) => (i, TypeKind::Trait),
3931         Def::Struct(i) => (i, TypeKind::Struct),
3932         Def::Union(i) => (i, TypeKind::Union),
3933         Def::Mod(i) => (i, TypeKind::Module),
3934         Def::ForeignTy(i) => (i, TypeKind::Foreign),
3935         Def::Const(i) => (i, TypeKind::Const),
3936         Def::Static(i, _) => (i, TypeKind::Static),
3937         Def::Variant(i) => (cx.tcx.parent_def_id(i).expect("cannot get parent def id"),
3938                             TypeKind::Enum),
3939         Def::Macro(i, mac_kind) => match mac_kind {
3940             MacroKind::Bang => (i, TypeKind::Macro),
3941             MacroKind::Attr => (i, TypeKind::Attr),
3942             MacroKind::Derive => (i, TypeKind::Derive),
3943             MacroKind::ProcMacroStub => unreachable!(),
3944         },
3945         Def::TraitAlias(i) => (i, TypeKind::TraitAlias),
3946         Def::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
3947         Def::SelfTy(_, Some(impl_def_id)) => return impl_def_id,
3948         _ => return def.def_id()
3949     };
3950     if did.is_local() { return did }
3951     inline::record_extern_fqn(cx, did, kind);
3952     if let TypeKind::Trait = kind {
3953         inline::record_extern_trait(cx, did);
3954     }
3955     did
3956 }
3957
3958 fn resolve_use_source(cx: &DocContext, path: Path) -> ImportSource {
3959     ImportSource {
3960         did: if path.def.opt_def_id().is_none() {
3961             None
3962         } else {
3963             Some(register_def(cx, path.def))
3964         },
3965         path,
3966     }
3967 }
3968
3969 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3970 pub struct Macro {
3971     pub source: String,
3972     pub imported_from: Option<String>,
3973 }
3974
3975 impl Clean<Item> for doctree::Macro {
3976     fn clean(&self, cx: &DocContext) -> Item {
3977         let name = self.name.clean(cx);
3978         Item {
3979             name: Some(name.clone()),
3980             attrs: self.attrs.clean(cx),
3981             source: self.whence.clean(cx),
3982             visibility: Some(Public),
3983             stability: self.stab.clean(cx),
3984             deprecation: self.depr.clean(cx),
3985             def_id: self.def_id,
3986             inner: MacroItem(Macro {
3987                 source: format!("macro_rules! {} {{\n{}}}",
3988                                 name,
3989                                 self.matchers.iter().map(|span| {
3990                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
3991                                 }).collect::<String>()),
3992                 imported_from: self.imported_from.clean(cx),
3993             }),
3994         }
3995     }
3996 }
3997
3998 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3999 pub struct ProcMacro {
4000     pub kind: MacroKind,
4001     pub helpers: Vec<String>,
4002 }
4003
4004 impl Clean<Item> for doctree::ProcMacro {
4005     fn clean(&self, cx: &DocContext) -> Item {
4006         Item {
4007             name: Some(self.name.clean(cx)),
4008             attrs: self.attrs.clean(cx),
4009             source: self.whence.clean(cx),
4010             visibility: Some(Public),
4011             stability: self.stab.clean(cx),
4012             deprecation: self.depr.clean(cx),
4013             def_id: cx.tcx.hir().local_def_id(self.id),
4014             inner: ProcMacroItem(ProcMacro {
4015                 kind: self.kind,
4016                 helpers: self.helpers.clean(cx),
4017             }),
4018         }
4019     }
4020 }
4021
4022 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4023 pub struct Stability {
4024     pub level: stability::StabilityLevel,
4025     pub feature: Option<String>,
4026     pub since: String,
4027     pub deprecation: Option<Deprecation>,
4028     pub unstable_reason: Option<String>,
4029     pub issue: Option<u32>,
4030 }
4031
4032 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4033 pub struct Deprecation {
4034     pub since: Option<String>,
4035     pub note: Option<String>,
4036 }
4037
4038 impl Clean<Stability> for attr::Stability {
4039     fn clean(&self, _: &DocContext) -> Stability {
4040         Stability {
4041             level: stability::StabilityLevel::from_attr_level(&self.level),
4042             feature: Some(self.feature.to_string()).filter(|f| !f.is_empty()),
4043             since: match self.level {
4044                 attr::Stable {ref since} => since.to_string(),
4045                 _ => String::new(),
4046             },
4047             deprecation: self.rustc_depr.as_ref().map(|d| {
4048                 Deprecation {
4049                     note: Some(d.reason.to_string()).filter(|r| !r.is_empty()),
4050                     since: Some(d.since.to_string()).filter(|d| !d.is_empty()),
4051                 }
4052             }),
4053             unstable_reason: match self.level {
4054                 attr::Unstable { reason: Some(ref reason), .. } => Some(reason.to_string()),
4055                 _ => None,
4056             },
4057             issue: match self.level {
4058                 attr::Unstable {issue, ..} => Some(issue),
4059                 _ => None,
4060             }
4061         }
4062     }
4063 }
4064
4065 impl<'a> Clean<Stability> for &'a attr::Stability {
4066     fn clean(&self, dc: &DocContext) -> Stability {
4067         (**self).clean(dc)
4068     }
4069 }
4070
4071 impl Clean<Deprecation> for attr::Deprecation {
4072     fn clean(&self, _: &DocContext) -> Deprecation {
4073         Deprecation {
4074             since: self.since.map(|s| s.to_string()).filter(|s| !s.is_empty()),
4075             note: self.note.map(|n| n.to_string()).filter(|n| !n.is_empty()),
4076         }
4077     }
4078 }
4079
4080 /// An equality constraint on an associated type, e.g., `A = Bar` in `Foo<A = Bar>`
4081 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug, Hash)]
4082 pub struct TypeBinding {
4083     pub name: String,
4084     pub ty: Type
4085 }
4086
4087 impl Clean<TypeBinding> for hir::TypeBinding {
4088     fn clean(&self, cx: &DocContext) -> TypeBinding {
4089         TypeBinding {
4090             name: self.ident.name.clean(cx),
4091             ty: self.ty.clean(cx)
4092         }
4093     }
4094 }
4095
4096 pub fn def_id_to_path(cx: &DocContext, did: DefId, name: Option<String>) -> Vec<String> {
4097     let crate_name = name.unwrap_or_else(|| cx.tcx.crate_name(did.krate).to_string());
4098     let relative = cx.tcx.def_path(did).data.into_iter().filter_map(|elem| {
4099         // extern blocks have an empty name
4100         let s = elem.data.to_string();
4101         if !s.is_empty() {
4102             Some(s)
4103         } else {
4104             None
4105         }
4106     });
4107     once(crate_name).chain(relative).collect()
4108 }
4109
4110 pub fn enter_impl_trait<F, R>(cx: &DocContext, f: F) -> R
4111 where
4112     F: FnOnce() -> R,
4113 {
4114     let old_bounds = mem::replace(&mut *cx.impl_trait_bounds.borrow_mut(), Default::default());
4115     let r = f();
4116     assert!(cx.impl_trait_bounds.borrow().is_empty());
4117     *cx.impl_trait_bounds.borrow_mut() = old_bounds;
4118     r
4119 }
4120
4121 // Start of code copied from rust-clippy
4122
4123 pub fn path_to_def_local(tcx: &TyCtxt, path: &[&str]) -> Option<DefId> {
4124     let krate = tcx.hir().krate();
4125     let mut items = krate.module.item_ids.clone();
4126     let mut path_it = path.iter().peekable();
4127
4128     loop {
4129         let segment = path_it.next()?;
4130
4131         for item_id in mem::replace(&mut items, HirVec::new()).iter() {
4132             let item = tcx.hir().expect_item(item_id.id);
4133             if item.ident.name == *segment {
4134                 if path_it.peek().is_none() {
4135                     return Some(tcx.hir().local_def_id(item_id.id))
4136                 }
4137
4138                 items = match &item.node {
4139                     &hir::ItemKind::Mod(ref m) => m.item_ids.clone(),
4140                     _ => panic!("Unexpected item {:?} in path {:?} path")
4141                 };
4142                 break;
4143             }
4144         }
4145     }
4146 }
4147
4148 pub fn path_to_def(tcx: &TyCtxt, path: &[&str]) -> Option<DefId> {
4149     let crates = tcx.crates();
4150
4151     let krate = crates
4152         .iter()
4153         .find(|&&krate| tcx.crate_name(krate) == path[0]);
4154
4155     if let Some(krate) = krate {
4156         let krate = DefId {
4157             krate: *krate,
4158             index: CRATE_DEF_INDEX,
4159         };
4160         let mut items = tcx.item_children(krate);
4161         let mut path_it = path.iter().skip(1).peekable();
4162
4163         loop {
4164             let segment = path_it.next()?;
4165
4166             for item in mem::replace(&mut items, Lrc::new(vec![])).iter() {
4167                 if item.ident.name == *segment {
4168                     if path_it.peek().is_none() {
4169                         return match item.def {
4170                             def::Def::Trait(did) => Some(did),
4171                             _ => None,
4172                         }
4173                     }
4174
4175                     items = tcx.item_children(item.def.def_id());
4176                     break;
4177                 }
4178             }
4179         }
4180     } else {
4181         None
4182     }
4183 }
4184
4185 pub fn get_path_for_type<F>(tcx: TyCtxt, def_id: DefId, def_ctor: F) -> hir::Path
4186 where F: Fn(DefId) -> Def {
4187     #[derive(Debug)]
4188     struct AbsolutePathBuffer {
4189         names: Vec<String>,
4190     }
4191
4192     impl ty::item_path::ItemPathBuffer for AbsolutePathBuffer {
4193         fn root_mode(&self) -> &ty::item_path::RootMode {
4194             const ABSOLUTE: &'static ty::item_path::RootMode = &ty::item_path::RootMode::Absolute;
4195             ABSOLUTE
4196         }
4197
4198         fn push(&mut self, text: &str) {
4199             self.names.push(text.to_owned());
4200         }
4201     }
4202
4203     let mut apb = AbsolutePathBuffer { names: vec![] };
4204
4205     tcx.push_item_path(&mut apb, def_id, false);
4206
4207     hir::Path {
4208         span: DUMMY_SP,
4209         def: def_ctor(def_id),
4210         segments: hir::HirVec::from_vec(apb.names.iter().map(|s| hir::PathSegment {
4211             ident: ast::Ident::from_str(&s),
4212             id: None,
4213             hir_id: None,
4214             def: None,
4215             args: None,
4216             infer_types: false,
4217         }).collect())
4218     }
4219 }
4220
4221 // End of code copied from rust-clippy
4222
4223
4224 #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
4225 enum RegionTarget<'tcx> {
4226     Region(Region<'tcx>),
4227     RegionVid(RegionVid)
4228 }
4229
4230 #[derive(Default, Debug, Clone)]
4231 struct RegionDeps<'tcx> {
4232     larger: FxHashSet<RegionTarget<'tcx>>,
4233     smaller: FxHashSet<RegionTarget<'tcx>>
4234 }
4235
4236 #[derive(Eq, PartialEq, Hash, Debug)]
4237 enum SimpleBound {
4238     TraitBound(Vec<PathSegment>, Vec<SimpleBound>, Vec<GenericParamDef>, hir::TraitBoundModifier),
4239     Outlives(Lifetime),
4240 }
4241
4242 enum AutoTraitResult {
4243     ExplicitImpl,
4244     PositiveImpl(Generics),
4245     NegativeImpl,
4246 }
4247
4248 impl AutoTraitResult {
4249     fn is_auto(&self) -> bool {
4250         match *self {
4251             AutoTraitResult::PositiveImpl(_) | AutoTraitResult::NegativeImpl => true,
4252             _ => false,
4253         }
4254     }
4255 }
4256
4257 impl From<GenericBound> for SimpleBound {
4258     fn from(bound: GenericBound) -> Self {
4259         match bound.clone() {
4260             GenericBound::Outlives(l) => SimpleBound::Outlives(l),
4261             GenericBound::TraitBound(t, mod_) => match t.trait_ {
4262                 Type::ResolvedPath { path, typarams, .. } => {
4263                     SimpleBound::TraitBound(path.segments,
4264                                             typarams
4265                                                 .map_or_else(|| Vec::new(), |v| v.iter()
4266                                                         .map(|p| SimpleBound::from(p.clone()))
4267                                                         .collect()),
4268                                             t.generic_params,
4269                                             mod_)
4270                 }
4271                 _ => panic!("Unexpected bound {:?}", bound),
4272             }
4273         }
4274     }
4275 }