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