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