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