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