src/librustdoc/clean/mod.rs

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