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