src/librustdoc/clean/mod.rs

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