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