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