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                 Argument {
2022                     name: name_from_pat(&body.arguments[i].original_pat()),
2023                     type_: ty.clean(cx),
2024                 }
2025             }).collect()
2026         }
2027     }
2028 }
2029
2030 impl<'a, A: Copy> Clean<FnDecl> for (&'a hir::FnDecl, A)
2031     where (&'a [hir::Ty], A): Clean<Arguments>
2032 {
2033     fn clean(&self, cx: &DocContext<'_>) -> FnDecl {
2034         FnDecl {
2035             inputs: (&self.0.inputs[..], self.1).clean(cx),
2036             output: self.0.output.clean(cx),
2037             attrs: Attributes::default(),
2038         }
2039     }
2040 }
2041
2042 impl<'a, 'tcx> Clean<FnDecl> for (DefId, ty::PolyFnSig<'tcx>) {
2043     fn clean(&self, cx: &DocContext<'_>) -> FnDecl {
2044         let (did, sig) = *self;
2045         let mut names = if cx.tcx.hir().as_local_hir_id(did).is_some() {
2046             vec![].into_iter()
2047         } else {
2048             cx.tcx.fn_arg_names(did).into_iter()
2049         };
2050
2051         FnDecl {
2052             output: Return(sig.skip_binder().output().clean(cx)),
2053             attrs: Attributes::default(),
2054             inputs: Arguments {
2055                 values: sig.skip_binder().inputs().iter().map(|t| {
2056                     Argument {
2057                         type_: t.clean(cx),
2058                         name: names.next().map_or(String::new(), |name| name.to_string()),
2059                     }
2060                 }).collect(),
2061             },
2062         }
2063     }
2064 }
2065
2066 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2067 pub struct Argument {
2068     pub type_: Type,
2069     pub name: String,
2070 }
2071
2072 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2073 pub enum SelfTy {
2074     SelfValue,
2075     SelfBorrowed(Option<Lifetime>, Mutability),
2076     SelfExplicit(Type),
2077 }
2078
2079 impl Argument {
2080     pub fn to_self(&self) -> Option<SelfTy> {
2081         if self.name != "self" {
2082             return None;
2083         }
2084         if self.type_.is_self_type() {
2085             return Some(SelfValue);
2086         }
2087         match self.type_ {
2088             BorrowedRef{ref lifetime, mutability, ref type_} if type_.is_self_type() => {
2089                 Some(SelfBorrowed(lifetime.clone(), mutability))
2090             }
2091             _ => Some(SelfExplicit(self.type_.clone()))
2092         }
2093     }
2094 }
2095
2096 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2097 pub enum FunctionRetTy {
2098     Return(Type),
2099     DefaultReturn,
2100 }
2101
2102 impl Clean<FunctionRetTy> for hir::FunctionRetTy {
2103     fn clean(&self, cx: &DocContext<'_>) -> FunctionRetTy {
2104         match *self {
2105             hir::Return(ref typ) => Return(typ.clean(cx)),
2106             hir::DefaultReturn(..) => DefaultReturn,
2107         }
2108     }
2109 }
2110
2111 impl GetDefId for FunctionRetTy {
2112     fn def_id(&self) -> Option<DefId> {
2113         match *self {
2114             Return(ref ty) => ty.def_id(),
2115             DefaultReturn => None,
2116         }
2117     }
2118 }
2119
2120 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2121 pub struct Trait {
2122     pub auto: bool,
2123     pub unsafety: hir::Unsafety,
2124     pub items: Vec<Item>,
2125     pub generics: Generics,
2126     pub bounds: Vec<GenericBound>,
2127     pub is_spotlight: bool,
2128     pub is_auto: bool,
2129 }
2130
2131 impl Clean<Item> for doctree::Trait {
2132     fn clean(&self, cx: &DocContext<'_>) -> Item {
2133         let attrs = self.attrs.clean(cx);
2134         let is_spotlight = attrs.has_doc_flag(sym::spotlight);
2135         Item {
2136             name: Some(self.name.clean(cx)),
2137             attrs: attrs,
2138             source: self.whence.clean(cx),
2139             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
2140             visibility: self.vis.clean(cx),
2141             stability: self.stab.clean(cx),
2142             deprecation: self.depr.clean(cx),
2143             inner: TraitItem(Trait {
2144                 auto: self.is_auto.clean(cx),
2145                 unsafety: self.unsafety,
2146                 items: self.items.clean(cx),
2147                 generics: self.generics.clean(cx),
2148                 bounds: self.bounds.clean(cx),
2149                 is_spotlight,
2150                 is_auto: self.is_auto.clean(cx),
2151             }),
2152         }
2153     }
2154 }
2155
2156 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2157 pub struct TraitAlias {
2158     pub generics: Generics,
2159     pub bounds: Vec<GenericBound>,
2160 }
2161
2162 impl Clean<Item> for doctree::TraitAlias {
2163     fn clean(&self, cx: &DocContext<'_>) -> Item {
2164         let attrs = self.attrs.clean(cx);
2165         Item {
2166             name: Some(self.name.clean(cx)),
2167             attrs,
2168             source: self.whence.clean(cx),
2169             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
2170             visibility: self.vis.clean(cx),
2171             stability: self.stab.clean(cx),
2172             deprecation: self.depr.clean(cx),
2173             inner: TraitAliasItem(TraitAlias {
2174                 generics: self.generics.clean(cx),
2175                 bounds: self.bounds.clean(cx),
2176             }),
2177         }
2178     }
2179 }
2180
2181 impl Clean<bool> for hir::IsAuto {
2182     fn clean(&self, _: &DocContext<'_>) -> bool {
2183         match *self {
2184             hir::IsAuto::Yes => true,
2185             hir::IsAuto::No => false,
2186         }
2187     }
2188 }
2189
2190 impl Clean<Type> for hir::TraitRef {
2191     fn clean(&self, cx: &DocContext<'_>) -> Type {
2192         resolve_type(cx, self.path.clean(cx), self.hir_ref_id)
2193     }
2194 }
2195
2196 impl Clean<PolyTrait> for hir::PolyTraitRef {
2197     fn clean(&self, cx: &DocContext<'_>) -> PolyTrait {
2198         PolyTrait {
2199             trait_: self.trait_ref.clean(cx),
2200             generic_params: self.bound_generic_params.clean(cx)
2201         }
2202     }
2203 }
2204
2205 impl Clean<Item> for hir::TraitItem {
2206     fn clean(&self, cx: &DocContext<'_>) -> Item {
2207         let inner = match self.node {
2208             hir::TraitItemKind::Const(ref ty, default) => {
2209                 AssocConstItem(ty.clean(cx),
2210                                     default.map(|e| print_const_expr(cx, e)))
2211             }
2212             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Provided(body)) => {
2213                 MethodItem((sig, &self.generics, body, None).clean(cx))
2214             }
2215             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Required(ref names)) => {
2216                 let (generics, decl) = enter_impl_trait(cx, || {
2217                     (self.generics.clean(cx), (&*sig.decl, &names[..]).clean(cx))
2218                 });
2219                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
2220                 TyMethodItem(TyMethod {
2221                     header: sig.header,
2222                     decl,
2223                     generics,
2224                     all_types,
2225                     ret_types,
2226                 })
2227             }
2228             hir::TraitItemKind::Type(ref bounds, ref default) => {
2229                 AssocTypeItem(bounds.clean(cx), default.clean(cx))
2230             }
2231         };
2232         let local_did = cx.tcx.hir().local_def_id_from_hir_id(self.hir_id);
2233         Item {
2234             name: Some(self.ident.name.clean(cx)),
2235             attrs: self.attrs.clean(cx),
2236             source: self.span.clean(cx),
2237             def_id: local_did,
2238             visibility: None,
2239             stability: get_stability(cx, local_did),
2240             deprecation: get_deprecation(cx, local_did),
2241             inner,
2242         }
2243     }
2244 }
2245
2246 impl Clean<Item> for hir::ImplItem {
2247     fn clean(&self, cx: &DocContext<'_>) -> Item {
2248         let inner = match self.node {
2249             hir::ImplItemKind::Const(ref ty, expr) => {
2250                 AssocConstItem(ty.clean(cx),
2251                                     Some(print_const_expr(cx, expr)))
2252             }
2253             hir::ImplItemKind::Method(ref sig, body) => {
2254                 MethodItem((sig, &self.generics, body, Some(self.defaultness)).clean(cx))
2255             }
2256             hir::ImplItemKind::Type(ref ty) => TypedefItem(Typedef {
2257                 type_: ty.clean(cx),
2258                 generics: Generics::default(),
2259             }, true),
2260             hir::ImplItemKind::Existential(ref bounds) => ExistentialItem(Existential {
2261                 bounds: bounds.clean(cx),
2262                 generics: Generics::default(),
2263             }, true),
2264         };
2265         let local_did = cx.tcx.hir().local_def_id_from_hir_id(self.hir_id);
2266         Item {
2267             name: Some(self.ident.name.clean(cx)),
2268             source: self.span.clean(cx),
2269             attrs: self.attrs.clean(cx),
2270             def_id: local_did,
2271             visibility: self.vis.clean(cx),
2272             stability: get_stability(cx, local_did),
2273             deprecation: get_deprecation(cx, local_did),
2274             inner,
2275         }
2276     }
2277 }
2278
2279 impl<'tcx> Clean<Item> for ty::AssocItem {
2280     fn clean(&self, cx: &DocContext<'_>) -> Item {
2281         let inner = match self.kind {
2282             ty::AssocKind::Const => {
2283                 let ty = cx.tcx.type_of(self.def_id);
2284                 let default = if self.defaultness.has_value() {
2285                     Some(inline::print_inlined_const(cx, self.def_id))
2286                 } else {
2287                     None
2288                 };
2289                 AssocConstItem(ty.clean(cx), default)
2290             }
2291             ty::AssocKind::Method => {
2292                 let generics = (cx.tcx.generics_of(self.def_id),
2293                                 &cx.tcx.explicit_predicates_of(self.def_id)).clean(cx);
2294                 let sig = cx.tcx.fn_sig(self.def_id);
2295                 let mut decl = (self.def_id, sig).clean(cx);
2296
2297                 if self.method_has_self_argument {
2298                     let self_ty = match self.container {
2299                         ty::ImplContainer(def_id) => {
2300                             cx.tcx.type_of(def_id)
2301                         }
2302                         ty::TraitContainer(_) => cx.tcx.mk_self_type()
2303                     };
2304                     let self_arg_ty = *sig.input(0).skip_binder();
2305                     if self_arg_ty == self_ty {
2306                         decl.inputs.values[0].type_ = Generic(String::from("Self"));
2307                     } else if let ty::Ref(_, ty, _) = self_arg_ty.sty {
2308                         if ty == self_ty {
2309                             match decl.inputs.values[0].type_ {
2310                                 BorrowedRef{ref mut type_, ..} => {
2311                                     **type_ = Generic(String::from("Self"))
2312                                 }
2313                                 _ => unreachable!(),
2314                             }
2315                         }
2316                     }
2317                 }
2318
2319                 let provided = match self.container {
2320                     ty::ImplContainer(_) => true,
2321                     ty::TraitContainer(_) => self.defaultness.has_value()
2322                 };
2323                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
2324                 if provided {
2325                     let constness = if cx.tcx.is_min_const_fn(self.def_id) {
2326                         hir::Constness::Const
2327                     } else {
2328                         hir::Constness::NotConst
2329                     };
2330                     let defaultness = match self.container {
2331                         ty::ImplContainer(_) => Some(self.defaultness),
2332                         ty::TraitContainer(_) => None,
2333                     };
2334                     MethodItem(Method {
2335                         generics,
2336                         decl,
2337                         header: hir::FnHeader {
2338                             unsafety: sig.unsafety(),
2339                             abi: sig.abi(),
2340                             constness,
2341                             asyncness: hir::IsAsync::NotAsync,
2342                         },
2343                         defaultness,
2344                         all_types,
2345                         ret_types,
2346                     })
2347                 } else {
2348                     TyMethodItem(TyMethod {
2349                         generics,
2350                         decl,
2351                         header: hir::FnHeader {
2352                             unsafety: sig.unsafety(),
2353                             abi: sig.abi(),
2354                             constness: hir::Constness::NotConst,
2355                             asyncness: hir::IsAsync::NotAsync,
2356                         },
2357                         all_types,
2358                         ret_types,
2359                     })
2360                 }
2361             }
2362             ty::AssocKind::Type => {
2363                 let my_name = self.ident.name.clean(cx);
2364
2365                 if let ty::TraitContainer(did) = self.container {
2366                     // When loading a cross-crate associated type, the bounds for this type
2367                     // are actually located on the trait/impl itself, so we need to load
2368                     // all of the generics from there and then look for bounds that are
2369                     // applied to this associated type in question.
2370                     let predicates = cx.tcx.explicit_predicates_of(did);
2371                     let generics = (cx.tcx.generics_of(did), &predicates).clean(cx);
2372                     let mut bounds = generics.where_predicates.iter().filter_map(|pred| {
2373                         let (name, self_type, trait_, bounds) = match *pred {
2374                             WherePredicate::BoundPredicate {
2375                                 ty: QPath { ref name, ref self_type, ref trait_ },
2376                                 ref bounds
2377                             } => (name, self_type, trait_, bounds),
2378                             _ => return None,
2379                         };
2380                         if *name != my_name { return None }
2381                         match **trait_ {
2382                             ResolvedPath { did, .. } if did == self.container.id() => {}
2383                             _ => return None,
2384                         }
2385                         match **self_type {
2386                             Generic(ref s) if *s == "Self" => {}
2387                             _ => return None,
2388                         }
2389                         Some(bounds)
2390                     }).flat_map(|i| i.iter().cloned()).collect::<Vec<_>>();
2391                     // Our Sized/?Sized bound didn't get handled when creating the generics
2392                     // because we didn't actually get our whole set of bounds until just now
2393                     // (some of them may have come from the trait). If we do have a sized
2394                     // bound, we remove it, and if we don't then we add the `?Sized` bound
2395                     // at the end.
2396                     match bounds.iter().position(|b| b.is_sized_bound(cx)) {
2397                         Some(i) => { bounds.remove(i); }
2398                         None => bounds.push(GenericBound::maybe_sized(cx)),
2399                     }
2400
2401                     let ty = if self.defaultness.has_value() {
2402                         Some(cx.tcx.type_of(self.def_id))
2403                     } else {
2404                         None
2405                     };
2406
2407                     AssocTypeItem(bounds, ty.clean(cx))
2408                 } else {
2409                     TypedefItem(Typedef {
2410                         type_: cx.tcx.type_of(self.def_id).clean(cx),
2411                         generics: Generics {
2412                             params: Vec::new(),
2413                             where_predicates: Vec::new(),
2414                         },
2415                     }, true)
2416                 }
2417             }
2418             ty::AssocKind::Existential => unimplemented!(),
2419         };
2420
2421         let visibility = match self.container {
2422             ty::ImplContainer(_) => self.vis.clean(cx),
2423             ty::TraitContainer(_) => None,
2424         };
2425
2426         Item {
2427             name: Some(self.ident.name.clean(cx)),
2428             visibility,
2429             stability: get_stability(cx, self.def_id),
2430             deprecation: get_deprecation(cx, self.def_id),
2431             def_id: self.def_id,
2432             attrs: inline::load_attrs(cx, self.def_id),
2433             source: cx.tcx.def_span(self.def_id).clean(cx),
2434             inner,
2435         }
2436     }
2437 }
2438
2439 /// A trait reference, which may have higher ranked lifetimes.
2440 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2441 pub struct PolyTrait {
2442     pub trait_: Type,
2443     pub generic_params: Vec<GenericParamDef>,
2444 }
2445
2446 /// A representation of a Type suitable for hyperlinking purposes. Ideally one can get the original
2447 /// type out of the AST/TyCtxt given one of these, if more information is needed. Most importantly
2448 /// it does not preserve mutability or boxes.
2449 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2450 pub enum Type {
2451     /// Structs/enums/traits (most that'd be an `hir::TyKind::Path`).
2452     ResolvedPath {
2453         path: Path,
2454         param_names: Option<Vec<GenericBound>>,
2455         did: DefId,
2456         /// `true` if is a `T::Name` path for associated types.
2457         is_generic: bool,
2458     },
2459     /// For parameterized types, so the consumer of the JSON don't go
2460     /// looking for types which don't exist anywhere.
2461     Generic(String),
2462     /// Primitives are the fixed-size numeric types (plus int/usize/float), char,
2463     /// arrays, slices, and tuples.
2464     Primitive(PrimitiveType),
2465     /// extern "ABI" fn
2466     BareFunction(Box<BareFunctionDecl>),
2467     Tuple(Vec<Type>),
2468     Slice(Box<Type>),
2469     Array(Box<Type>, String),
2470     Never,
2471     CVarArgs,
2472     Unique(Box<Type>),
2473     RawPointer(Mutability, Box<Type>),
2474     BorrowedRef {
2475         lifetime: Option<Lifetime>,
2476         mutability: Mutability,
2477         type_: Box<Type>,
2478     },
2479
2480     // <Type as Trait>::Name
2481     QPath {
2482         name: String,
2483         self_type: Box<Type>,
2484         trait_: Box<Type>
2485     },
2486
2487     // _
2488     Infer,
2489
2490     // impl TraitA+TraitB
2491     ImplTrait(Vec<GenericBound>),
2492 }
2493
2494 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Copy, Debug)]
2495 pub enum PrimitiveType {
2496     Isize, I8, I16, I32, I64, I128,
2497     Usize, U8, U16, U32, U64, U128,
2498     F32, F64,
2499     Char,
2500     Bool,
2501     Str,
2502     Slice,
2503     Array,
2504     Tuple,
2505     Unit,
2506     RawPointer,
2507     Reference,
2508     Fn,
2509     Never,
2510     CVarArgs,
2511 }
2512
2513 #[derive(Clone, RustcEncodable, RustcDecodable, Copy, Debug)]
2514 pub enum TypeKind {
2515     Enum,
2516     Function,
2517     Module,
2518     Const,
2519     Static,
2520     Struct,
2521     Union,
2522     Trait,
2523     Variant,
2524     Typedef,
2525     Foreign,
2526     Macro,
2527     Attr,
2528     Derive,
2529     TraitAlias,
2530 }
2531
2532 pub trait GetDefId {
2533     fn def_id(&self) -> Option<DefId>;
2534 }
2535
2536 impl<T: GetDefId> GetDefId for Option<T> {
2537     fn def_id(&self) -> Option<DefId> {
2538         self.as_ref().and_then(|d| d.def_id())
2539     }
2540 }
2541
2542 impl Type {
2543     pub fn primitive_type(&self) -> Option<PrimitiveType> {
2544         match *self {
2545             Primitive(p) | BorrowedRef { type_: box Primitive(p), ..} => Some(p),
2546             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
2547             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
2548             Tuple(ref tys) => if tys.is_empty() {
2549                 Some(PrimitiveType::Unit)
2550             } else {
2551                 Some(PrimitiveType::Tuple)
2552             },
2553             RawPointer(..) => Some(PrimitiveType::RawPointer),
2554             BorrowedRef { type_: box Generic(..), .. } => Some(PrimitiveType::Reference),
2555             BareFunction(..) => Some(PrimitiveType::Fn),
2556             Never => Some(PrimitiveType::Never),
2557             _ => None,
2558         }
2559     }
2560
2561     pub fn is_generic(&self) -> bool {
2562         match *self {
2563             ResolvedPath { is_generic, .. } => is_generic,
2564             _ => false,
2565         }
2566     }
2567
2568     pub fn is_self_type(&self) -> bool {
2569         match *self {
2570             Generic(ref name) => name == "Self",
2571             _ => false
2572         }
2573     }
2574
2575     pub fn generics(&self) -> Option<Vec<Type>> {
2576         match *self {
2577             ResolvedPath { ref path, .. } => {
2578                 path.segments.last().and_then(|seg| {
2579                     if let GenericArgs::AngleBracketed { ref args, .. } = seg.args {
2580                         Some(args.iter().filter_map(|arg| match arg {
2581                             GenericArg::Type(ty) => Some(ty.clone()),
2582                             _ => None,
2583                         }).collect())
2584                     } else {
2585                         None
2586                     }
2587                 })
2588             }
2589             _ => None,
2590         }
2591     }
2592
2593     pub fn bindings(&self) -> Option<&[TypeBinding]> {
2594         match *self {
2595             ResolvedPath { ref path, .. } => {
2596                 path.segments.last().and_then(|seg| {
2597                     if let GenericArgs::AngleBracketed { ref bindings, .. } = seg.args {
2598                         Some(&**bindings)
2599                     } else {
2600                         None
2601                     }
2602                 })
2603             }
2604             _ => None
2605         }
2606     }
2607
2608     pub fn is_full_generic(&self) -> bool {
2609         match *self {
2610             Type::Generic(_) => true,
2611             _ => false,
2612         }
2613     }
2614 }
2615
2616 impl GetDefId for Type {
2617     fn def_id(&self) -> Option<DefId> {
2618         match *self {
2619             ResolvedPath { did, .. } => Some(did),
2620             Primitive(p) => crate::html::render::cache().primitive_locations.get(&p).cloned(),
2621             BorrowedRef { type_: box Generic(..), .. } =>
2622                 Primitive(PrimitiveType::Reference).def_id(),
2623             BorrowedRef { ref type_, .. } => type_.def_id(),
2624             Tuple(ref tys) => if tys.is_empty() {
2625                 Primitive(PrimitiveType::Unit).def_id()
2626             } else {
2627                 Primitive(PrimitiveType::Tuple).def_id()
2628             },
2629             BareFunction(..) => Primitive(PrimitiveType::Fn).def_id(),
2630             Never => Primitive(PrimitiveType::Never).def_id(),
2631             Slice(..) => Primitive(PrimitiveType::Slice).def_id(),
2632             Array(..) => Primitive(PrimitiveType::Array).def_id(),
2633             RawPointer(..) => Primitive(PrimitiveType::RawPointer).def_id(),
2634             QPath { ref self_type, .. } => self_type.def_id(),
2635             _ => None,
2636         }
2637     }
2638 }
2639
2640 impl PrimitiveType {
2641     fn from_str(s: &str) -> Option<PrimitiveType> {
2642         match s {
2643             "isize" => Some(PrimitiveType::Isize),
2644             "i8" => Some(PrimitiveType::I8),
2645             "i16" => Some(PrimitiveType::I16),
2646             "i32" => Some(PrimitiveType::I32),
2647             "i64" => Some(PrimitiveType::I64),
2648             "i128" => Some(PrimitiveType::I128),
2649             "usize" => Some(PrimitiveType::Usize),
2650             "u8" => Some(PrimitiveType::U8),
2651             "u16" => Some(PrimitiveType::U16),
2652             "u32" => Some(PrimitiveType::U32),
2653             "u64" => Some(PrimitiveType::U64),
2654             "u128" => Some(PrimitiveType::U128),
2655             "bool" => Some(PrimitiveType::Bool),
2656             "char" => Some(PrimitiveType::Char),
2657             "str" => Some(PrimitiveType::Str),
2658             "f32" => Some(PrimitiveType::F32),
2659             "f64" => Some(PrimitiveType::F64),
2660             "array" => Some(PrimitiveType::Array),
2661             "slice" => Some(PrimitiveType::Slice),
2662             "tuple" => Some(PrimitiveType::Tuple),
2663             "unit" => Some(PrimitiveType::Unit),
2664             "pointer" => Some(PrimitiveType::RawPointer),
2665             "reference" => Some(PrimitiveType::Reference),
2666             "fn" => Some(PrimitiveType::Fn),
2667             "never" => Some(PrimitiveType::Never),
2668             _ => None,
2669         }
2670     }
2671
2672     pub fn as_str(&self) -> &'static str {
2673         use self::PrimitiveType::*;
2674         match *self {
2675             Isize => "isize",
2676             I8 => "i8",
2677             I16 => "i16",
2678             I32 => "i32",
2679             I64 => "i64",
2680             I128 => "i128",
2681             Usize => "usize",
2682             U8 => "u8",
2683             U16 => "u16",
2684             U32 => "u32",
2685             U64 => "u64",
2686             U128 => "u128",
2687             F32 => "f32",
2688             F64 => "f64",
2689             Str => "str",
2690             Bool => "bool",
2691             Char => "char",
2692             Array => "array",
2693             Slice => "slice",
2694             Tuple => "tuple",
2695             Unit => "unit",
2696             RawPointer => "pointer",
2697             Reference => "reference",
2698             Fn => "fn",
2699             Never => "never",
2700             CVarArgs => "...",
2701         }
2702     }
2703
2704     pub fn to_url_str(&self) -> &'static str {
2705         self.as_str()
2706     }
2707 }
2708
2709 impl From<ast::IntTy> for PrimitiveType {
2710     fn from(int_ty: ast::IntTy) -> PrimitiveType {
2711         match int_ty {
2712             ast::IntTy::Isize => PrimitiveType::Isize,
2713             ast::IntTy::I8 => PrimitiveType::I8,
2714             ast::IntTy::I16 => PrimitiveType::I16,
2715             ast::IntTy::I32 => PrimitiveType::I32,
2716             ast::IntTy::I64 => PrimitiveType::I64,
2717             ast::IntTy::I128 => PrimitiveType::I128,
2718         }
2719     }
2720 }
2721
2722 impl From<ast::UintTy> for PrimitiveType {
2723     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
2724         match uint_ty {
2725             ast::UintTy::Usize => PrimitiveType::Usize,
2726             ast::UintTy::U8 => PrimitiveType::U8,
2727             ast::UintTy::U16 => PrimitiveType::U16,
2728             ast::UintTy::U32 => PrimitiveType::U32,
2729             ast::UintTy::U64 => PrimitiveType::U64,
2730             ast::UintTy::U128 => PrimitiveType::U128,
2731         }
2732     }
2733 }
2734
2735 impl From<ast::FloatTy> for PrimitiveType {
2736     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
2737         match float_ty {
2738             ast::FloatTy::F32 => PrimitiveType::F32,
2739             ast::FloatTy::F64 => PrimitiveType::F64,
2740         }
2741     }
2742 }
2743
2744 impl Clean<Type> for hir::Ty {
2745     fn clean(&self, cx: &DocContext<'_>) -> Type {
2746         use rustc::hir::*;
2747
2748         match self.node {
2749             TyKind::Never => Never,
2750             TyKind::CVarArgs(_) => CVarArgs,
2751             TyKind::Ptr(ref m) => RawPointer(m.mutbl.clean(cx), box m.ty.clean(cx)),
2752             TyKind::Rptr(ref l, ref m) => {
2753                 let lifetime = if l.is_elided() {
2754                     None
2755                 } else {
2756                     Some(l.clean(cx))
2757                 };
2758                 BorrowedRef {lifetime: lifetime, mutability: m.mutbl.clean(cx),
2759                              type_: box m.ty.clean(cx)}
2760             }
2761             TyKind::Slice(ref ty) => Slice(box ty.clean(cx)),
2762             TyKind::Array(ref ty, ref length) => {
2763                 let def_id = cx.tcx.hir().local_def_id_from_hir_id(length.hir_id);
2764                 let param_env = cx.tcx.param_env(def_id);
2765                 let substs = InternalSubsts::identity_for_item(cx.tcx, def_id);
2766                 let cid = GlobalId {
2767                     instance: ty::Instance::new(def_id, substs),
2768                     promoted: None
2769                 };
2770                 let length = match cx.tcx.const_eval(param_env.and(cid)) {
2771                     Ok(length) => print_const(cx, length),
2772                     Err(_) => "_".to_string(),
2773                 };
2774                 Array(box ty.clean(cx), length)
2775             },
2776             TyKind::Tup(ref tys) => Tuple(tys.clean(cx)),
2777             TyKind::Def(item_id, _) => {
2778                 let item = cx.tcx.hir().expect_item_by_hir_id(item_id.id);
2779                 if let hir::ItemKind::Existential(ref ty) = item.node {
2780                     ImplTrait(ty.bounds.clean(cx))
2781                 } else {
2782                     unreachable!()
2783                 }
2784             }
2785             TyKind::Path(hir::QPath::Resolved(None, ref path)) => {
2786                 if let Res::Def(DefKind::TyParam, did) = path.res {
2787                     if let Some(new_ty) = cx.ty_substs.borrow().get(&did).cloned() {
2788                         return new_ty;
2789                     }
2790                     if let Some(bounds) = cx.impl_trait_bounds.borrow_mut().remove(&did) {
2791                         return ImplTrait(bounds);
2792                     }
2793                 }
2794
2795                 let mut alias = None;
2796                 if let Res::Def(DefKind::TyAlias, def_id) = path.res {
2797                     // Substitute private type aliases
2798                     if let Some(hir_id) = cx.tcx.hir().as_local_hir_id(def_id) {
2799                         if !cx.renderinfo.borrow().access_levels.is_exported(def_id) {
2800                             alias = Some(&cx.tcx.hir().expect_item_by_hir_id(hir_id).node);
2801                         }
2802                     }
2803                 };
2804
2805                 if let Some(&hir::ItemKind::Ty(ref ty, ref generics)) = alias {
2806                     let provided_params = &path.segments.last().expect("segments were empty");
2807                     let mut ty_substs = FxHashMap::default();
2808                     let mut lt_substs = FxHashMap::default();
2809                     let mut ct_substs = FxHashMap::default();
2810                     provided_params.with_generic_args(|generic_args| {
2811                         let mut indices: GenericParamCount = Default::default();
2812                         for param in generics.params.iter() {
2813                             match param.kind {
2814                                 hir::GenericParamKind::Lifetime { .. } => {
2815                                     let mut j = 0;
2816                                     let lifetime = generic_args.args.iter().find_map(|arg| {
2817                                         match arg {
2818                                             hir::GenericArg::Lifetime(lt) => {
2819                                                 if indices.lifetimes == j {
2820                                                     return Some(lt);
2821                                                 }
2822                                                 j += 1;
2823                                                 None
2824                                             }
2825                                             _ => None,
2826                                         }
2827                                     });
2828                                     if let Some(lt) = lifetime.cloned() {
2829                                         if !lt.is_elided() {
2830                                             let lt_def_id =
2831                                                 cx.tcx.hir().local_def_id_from_hir_id(param.hir_id);
2832                                             lt_substs.insert(lt_def_id, lt.clean(cx));
2833                                         }
2834                                     }
2835                                     indices.lifetimes += 1;
2836                                 }
2837                                 hir::GenericParamKind::Type { ref default, .. } => {
2838                                     let ty_param_def_id =
2839                                         cx.tcx.hir().local_def_id_from_hir_id(param.hir_id);
2840                                     let mut j = 0;
2841                                     let type_ = generic_args.args.iter().find_map(|arg| {
2842                                         match arg {
2843                                             hir::GenericArg::Type(ty) => {
2844                                                 if indices.types == j {
2845                                                     return Some(ty);
2846                                                 }
2847                                                 j += 1;
2848                                                 None
2849                                             }
2850                                             _ => None,
2851                                         }
2852                                     });
2853                                     if let Some(ty) = type_.cloned() {
2854                                         ty_substs.insert(ty_param_def_id, ty.clean(cx));
2855                                     } else if let Some(default) = default.clone() {
2856                                         ty_substs.insert(ty_param_def_id,
2857                                                          default.into_inner().clean(cx));
2858                                     }
2859                                     indices.types += 1;
2860                                 }
2861                                 hir::GenericParamKind::Const { .. } => {
2862                                     let const_param_def_id =
2863                                         cx.tcx.hir().local_def_id_from_hir_id(param.hir_id);
2864                                     let mut j = 0;
2865                                     let const_ = generic_args.args.iter().find_map(|arg| {
2866                                         match arg {
2867                                             hir::GenericArg::Const(ct) => {
2868                                                 if indices.consts == j {
2869                                                     return Some(ct);
2870                                                 }
2871                                                 j += 1;
2872                                                 None
2873                                             }
2874                                             _ => None,
2875                                         }
2876                                     });
2877                                     if let Some(ct) = const_.cloned() {
2878                                         ct_substs.insert(const_param_def_id, ct.clean(cx));
2879                                     }
2880                                     // FIXME(const_generics:defaults)
2881                                     indices.consts += 1;
2882                                 }
2883                             }
2884                         }
2885                     });
2886                     return cx.enter_alias(ty_substs, lt_substs, ct_substs, || ty.clean(cx));
2887                 }
2888                 resolve_type(cx, path.clean(cx), self.hir_id)
2889             }
2890             TyKind::Path(hir::QPath::Resolved(Some(ref qself), ref p)) => {
2891                 let mut segments: Vec<_> = p.segments.clone().into();
2892                 segments.pop();
2893                 let trait_path = hir::Path {
2894                     span: p.span,
2895                     res: Res::Def(
2896                         DefKind::Trait,
2897                         cx.tcx.associated_item(p.res.def_id()).container.id(),
2898                     ),
2899                     segments: segments.into(),
2900                 };
2901                 Type::QPath {
2902                     name: p.segments.last().expect("segments were empty").ident.name.clean(cx),
2903                     self_type: box qself.clean(cx),
2904                     trait_: box resolve_type(cx, trait_path.clean(cx), self.hir_id)
2905                 }
2906             }
2907             TyKind::Path(hir::QPath::TypeRelative(ref qself, ref segment)) => {
2908                 let mut res = Res::Err;
2909                 let ty = hir_ty_to_ty(cx.tcx, self);
2910                 if let ty::Projection(proj) = ty.sty {
2911                     res = Res::Def(DefKind::Trait, proj.trait_ref(cx.tcx).def_id);
2912                 }
2913                 let trait_path = hir::Path {
2914                     span: self.span,
2915                     res,
2916                     segments: vec![].into(),
2917                 };
2918                 Type::QPath {
2919                     name: segment.ident.name.clean(cx),
2920                     self_type: box qself.clean(cx),
2921                     trait_: box resolve_type(cx, trait_path.clean(cx), self.hir_id)
2922                 }
2923             }
2924             TyKind::TraitObject(ref bounds, ref lifetime) => {
2925                 match bounds[0].clean(cx).trait_ {
2926                     ResolvedPath { path, param_names: None, did, is_generic } => {
2927                         let mut bounds: Vec<self::GenericBound> = bounds[1..].iter().map(|bound| {
2928                             self::GenericBound::TraitBound(bound.clean(cx),
2929                                                            hir::TraitBoundModifier::None)
2930                         }).collect();
2931                         if !lifetime.is_elided() {
2932                             bounds.push(self::GenericBound::Outlives(lifetime.clean(cx)));
2933                         }
2934                         ResolvedPath { path, param_names: Some(bounds), did, is_generic, }
2935                     }
2936                     _ => Infer // shouldn't happen
2937                 }
2938             }
2939             TyKind::BareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
2940             TyKind::Infer | TyKind::Err => Infer,
2941             TyKind::Typeof(..) => panic!("Unimplemented type {:?}", self.node),
2942         }
2943     }
2944 }
2945
2946 impl<'tcx> Clean<Type> for Ty<'tcx> {
2947     fn clean(&self, cx: &DocContext<'_>) -> Type {
2948         debug!("cleaning type: {:?}", self);
2949         match self.sty {
2950             ty::Never => Never,
2951             ty::Bool => Primitive(PrimitiveType::Bool),
2952             ty::Char => Primitive(PrimitiveType::Char),
2953             ty::Int(int_ty) => Primitive(int_ty.into()),
2954             ty::Uint(uint_ty) => Primitive(uint_ty.into()),
2955             ty::Float(float_ty) => Primitive(float_ty.into()),
2956             ty::Str => Primitive(PrimitiveType::Str),
2957             ty::Slice(ty) => Slice(box ty.clean(cx)),
2958             ty::Array(ty, n) => {
2959                 let mut n = cx.tcx.lift(&n).expect("array lift failed");
2960                 if let ConstValue::Unevaluated(def_id, substs) = n.val {
2961                     let param_env = cx.tcx.param_env(def_id);
2962                     let cid = GlobalId {
2963                         instance: ty::Instance::new(def_id, substs),
2964                         promoted: None
2965                     };
2966                     if let Ok(new_n) = cx.tcx.const_eval(param_env.and(cid)) {
2967                         n = new_n;
2968                     }
2969                 };
2970                 let n = print_const(cx, n);
2971                 Array(box ty.clean(cx), n)
2972             }
2973             ty::RawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
2974             ty::Ref(r, ty, mutbl) => BorrowedRef {
2975                 lifetime: r.clean(cx),
2976                 mutability: mutbl.clean(cx),
2977                 type_: box ty.clean(cx),
2978             },
2979             ty::FnDef(..) |
2980             ty::FnPtr(_) => {
2981                 let ty = cx.tcx.lift(self).expect("FnPtr lift failed");
2982                 let sig = ty.fn_sig(cx.tcx);
2983                 BareFunction(box BareFunctionDecl {
2984                     unsafety: sig.unsafety(),
2985                     generic_params: Vec::new(),
2986                     decl: (cx.tcx.hir().local_def_id(ast::CRATE_NODE_ID), sig).clean(cx),
2987                     abi: sig.abi(),
2988                 })
2989             }
2990             ty::Adt(def, substs) => {
2991                 let did = def.did;
2992                 let kind = match def.adt_kind() {
2993                     AdtKind::Struct => TypeKind::Struct,
2994                     AdtKind::Union => TypeKind::Union,
2995                     AdtKind::Enum => TypeKind::Enum,
2996                 };
2997                 inline::record_extern_fqn(cx, did, kind);
2998                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
2999                                          None, false, vec![], substs);
3000                 ResolvedPath {
3001                     path,
3002                     param_names: None,
3003                     did,
3004                     is_generic: false,
3005                 }
3006             }
3007             ty::Foreign(did) => {
3008                 inline::record_extern_fqn(cx, did, TypeKind::Foreign);
3009                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
3010                                          None, false, vec![], InternalSubsts::empty());
3011                 ResolvedPath {
3012                     path: path,
3013                     param_names: None,
3014                     did: did,
3015                     is_generic: false,
3016                 }
3017             }
3018             ty::Dynamic(ref obj, ref reg) => {
3019                 // HACK: pick the first `did` as the `did` of the trait object. Someone
3020                 // might want to implement "native" support for marker-trait-only
3021                 // trait objects.
3022                 let mut dids = obj.principal_def_id().into_iter().chain(obj.auto_traits());
3023                 let did = dids.next().unwrap_or_else(|| {
3024                     panic!("found trait object `{:?}` with no traits?", self)
3025                 });
3026                 let substs = match obj.principal() {
3027                     Some(principal) => principal.skip_binder().substs,
3028                     // marker traits have no substs.
3029                     _ => cx.tcx.intern_substs(&[])
3030                 };
3031
3032                 inline::record_extern_fqn(cx, did, TypeKind::Trait);
3033
3034                 let mut param_names = vec![];
3035                 reg.clean(cx).map(|b| param_names.push(GenericBound::Outlives(b)));
3036                 for did in dids {
3037                     let empty = cx.tcx.intern_substs(&[]);
3038                     let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
3039                         Some(did), false, vec![], empty);
3040                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
3041                     let bound = GenericBound::TraitBound(PolyTrait {
3042                         trait_: ResolvedPath {
3043                             path,
3044                             param_names: None,
3045                             did,
3046                             is_generic: false,
3047                         },
3048                         generic_params: Vec::new(),
3049                     }, hir::TraitBoundModifier::None);
3050                     param_names.push(bound);
3051                 }
3052
3053                 let mut bindings = vec![];
3054                 for pb in obj.projection_bounds() {
3055                     bindings.push(TypeBinding {
3056                         name: cx.tcx.associated_item(pb.item_def_id()).ident.name.clean(cx),
3057                         ty: pb.skip_binder().ty.clean(cx)
3058                     });
3059                 }
3060
3061                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(), Some(did),
3062                     false, bindings, substs);
3063                 ResolvedPath {
3064                     path,
3065                     param_names: Some(param_names),
3066                     did,
3067                     is_generic: false,
3068                 }
3069             }
3070             ty::Tuple(ref t) => {
3071                 Tuple(t.iter().map(|t| t.expect_ty()).collect::<Vec<_>>().clean(cx))
3072             }
3073
3074             ty::Projection(ref data) => data.clean(cx),
3075
3076             ty::Param(ref p) => Generic(p.name.to_string()),
3077
3078             ty::Opaque(def_id, substs) => {
3079                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
3080                 // by looking up the projections associated with the def_id.
3081                 let predicates_of = cx.tcx.explicit_predicates_of(def_id);
3082                 let substs = cx.tcx.lift(&substs).expect("Opaque lift failed");
3083                 let bounds = predicates_of.instantiate(cx.tcx, substs);
3084                 let mut regions = vec![];
3085                 let mut has_sized = false;
3086                 let mut bounds = bounds.predicates.iter().filter_map(|predicate| {
3087                     let trait_ref = if let Some(tr) = predicate.to_opt_poly_trait_ref() {
3088                         tr
3089                     } else if let ty::Predicate::TypeOutlives(pred) = *predicate {
3090                         // these should turn up at the end
3091                         pred.skip_binder().1.clean(cx).map(|r| {
3092                             regions.push(GenericBound::Outlives(r))
3093                         });
3094                         return None;
3095                     } else {
3096                         return None;
3097                     };
3098
3099                     if let Some(sized) = cx.tcx.lang_items().sized_trait() {
3100                         if trait_ref.def_id() == sized {
3101                             has_sized = true;
3102                             return None;
3103                         }
3104                     }
3105
3106                     let bounds = bounds.predicates.iter().filter_map(|pred|
3107                         if let ty::Predicate::Projection(proj) = *pred {
3108                             let proj = proj.skip_binder();
3109                             if proj.projection_ty.trait_ref(cx.tcx) == *trait_ref.skip_binder() {
3110                                 Some(TypeBinding {
3111                                     name: cx.tcx.associated_item(proj.projection_ty.item_def_id)
3112                                                 .ident.name.clean(cx),
3113                                     ty: proj.ty.clean(cx),
3114                                 })
3115                             } else {
3116                                 None
3117                             }
3118                         } else {
3119                             None
3120                         }
3121                     ).collect();
3122
3123                     Some((trait_ref.skip_binder(), bounds).clean(cx))
3124                 }).collect::<Vec<_>>();
3125                 bounds.extend(regions);
3126                 if !has_sized && !bounds.is_empty() {
3127                     bounds.insert(0, GenericBound::maybe_sized(cx));
3128                 }
3129                 ImplTrait(bounds)
3130             }
3131
3132             ty::Closure(..) | ty::Generator(..) => Tuple(vec![]), // FIXME(pcwalton)
3133
3134             ty::Bound(..) => panic!("Bound"),
3135             ty::Placeholder(..) => panic!("Placeholder"),
3136             ty::UnnormalizedProjection(..) => panic!("UnnormalizedProjection"),
3137             ty::GeneratorWitness(..) => panic!("GeneratorWitness"),
3138             ty::Infer(..) => panic!("Infer"),
3139             ty::Error => panic!("Error"),
3140         }
3141     }
3142 }
3143
3144 impl<'tcx> Clean<Constant> for ty::Const<'tcx> {
3145     fn clean(&self, cx: &DocContext<'_>) -> Constant {
3146         Constant {
3147             type_: self.ty.clean(cx),
3148             expr: format!("{}", self),
3149         }
3150     }
3151 }
3152
3153 impl Clean<Item> for hir::StructField {
3154     fn clean(&self, cx: &DocContext<'_>) -> Item {
3155         let local_did = cx.tcx.hir().local_def_id_from_hir_id(self.hir_id);
3156
3157         Item {
3158             name: Some(self.ident.name).clean(cx),
3159             attrs: self.attrs.clean(cx),
3160             source: self.span.clean(cx),
3161             visibility: self.vis.clean(cx),
3162             stability: get_stability(cx, local_did),
3163             deprecation: get_deprecation(cx, local_did),
3164             def_id: local_did,
3165             inner: StructFieldItem(self.ty.clean(cx)),
3166         }
3167     }
3168 }
3169
3170 impl<'tcx> Clean<Item> for ty::FieldDef {
3171     fn clean(&self, cx: &DocContext<'_>) -> Item {
3172         Item {
3173             name: Some(self.ident.name).clean(cx),
3174             attrs: cx.tcx.get_attrs(self.did).clean(cx),
3175             source: cx.tcx.def_span(self.did).clean(cx),
3176             visibility: self.vis.clean(cx),
3177             stability: get_stability(cx, self.did),
3178             deprecation: get_deprecation(cx, self.did),
3179             def_id: self.did,
3180             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
3181         }
3182     }
3183 }
3184
3185 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug)]
3186 pub enum Visibility {
3187     Public,
3188     Inherited,
3189     Crate,
3190     Restricted(DefId, Path),
3191 }
3192
3193 impl Clean<Option<Visibility>> for hir::Visibility {
3194     fn clean(&self, cx: &DocContext<'_>) -> Option<Visibility> {
3195         Some(match self.node {
3196             hir::VisibilityKind::Public => Visibility::Public,
3197             hir::VisibilityKind::Inherited => Visibility::Inherited,
3198             hir::VisibilityKind::Crate(_) => Visibility::Crate,
3199             hir::VisibilityKind::Restricted { ref path, .. } => {
3200                 let path = path.clean(cx);
3201                 let did = register_res(cx, path.res);
3202                 Visibility::Restricted(did, path)
3203             }
3204         })
3205     }
3206 }
3207
3208 impl Clean<Option<Visibility>> for ty::Visibility {
3209     fn clean(&self, _: &DocContext<'_>) -> Option<Visibility> {
3210         Some(if *self == ty::Visibility::Public { Public } else { Inherited })
3211     }
3212 }
3213
3214 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3215 pub struct Struct {
3216     pub struct_type: doctree::StructType,
3217     pub generics: Generics,
3218     pub fields: Vec<Item>,
3219     pub fields_stripped: bool,
3220 }
3221
3222 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3223 pub struct Union {
3224     pub struct_type: doctree::StructType,
3225     pub generics: Generics,
3226     pub fields: Vec<Item>,
3227     pub fields_stripped: bool,
3228 }
3229
3230 impl Clean<Item> for doctree::Struct {
3231     fn clean(&self, cx: &DocContext<'_>) -> Item {
3232         Item {
3233             name: Some(self.name.clean(cx)),
3234             attrs: self.attrs.clean(cx),
3235             source: self.whence.clean(cx),
3236             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3237             visibility: self.vis.clean(cx),
3238             stability: self.stab.clean(cx),
3239             deprecation: self.depr.clean(cx),
3240             inner: StructItem(Struct {
3241                 struct_type: self.struct_type,
3242                 generics: self.generics.clean(cx),
3243                 fields: self.fields.clean(cx),
3244                 fields_stripped: false,
3245             }),
3246         }
3247     }
3248 }
3249
3250 impl Clean<Item> for doctree::Union {
3251     fn clean(&self, cx: &DocContext<'_>) -> Item {
3252         Item {
3253             name: Some(self.name.clean(cx)),
3254             attrs: self.attrs.clean(cx),
3255             source: self.whence.clean(cx),
3256             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3257             visibility: self.vis.clean(cx),
3258             stability: self.stab.clean(cx),
3259             deprecation: self.depr.clean(cx),
3260             inner: UnionItem(Union {
3261                 struct_type: self.struct_type,
3262                 generics: self.generics.clean(cx),
3263                 fields: self.fields.clean(cx),
3264                 fields_stripped: false,
3265             }),
3266         }
3267     }
3268 }
3269
3270 /// This is a more limited form of the standard Struct, different in that
3271 /// it lacks the things most items have (name, id, parameterization). Found
3272 /// only as a variant in an enum.
3273 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3274 pub struct VariantStruct {
3275     pub struct_type: doctree::StructType,
3276     pub fields: Vec<Item>,
3277     pub fields_stripped: bool,
3278 }
3279
3280 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
3281     fn clean(&self, cx: &DocContext<'_>) -> VariantStruct {
3282         VariantStruct {
3283             struct_type: doctree::struct_type_from_def(self),
3284             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
3285             fields_stripped: false,
3286         }
3287     }
3288 }
3289
3290 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3291 pub struct Enum {
3292     pub variants: IndexVec<VariantIdx, Item>,
3293     pub generics: Generics,
3294     pub variants_stripped: bool,
3295 }
3296
3297 impl Clean<Item> for doctree::Enum {
3298     fn clean(&self, cx: &DocContext<'_>) -> Item {
3299         Item {
3300             name: Some(self.name.clean(cx)),
3301             attrs: self.attrs.clean(cx),
3302             source: self.whence.clean(cx),
3303             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3304             visibility: self.vis.clean(cx),
3305             stability: self.stab.clean(cx),
3306             deprecation: self.depr.clean(cx),
3307             inner: EnumItem(Enum {
3308                 variants: self.variants.iter().map(|v| v.clean(cx)).collect(),
3309                 generics: self.generics.clean(cx),
3310                 variants_stripped: false,
3311             }),
3312         }
3313     }
3314 }
3315
3316 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3317 pub struct Variant {
3318     pub kind: VariantKind,
3319 }
3320
3321 impl Clean<Item> for doctree::Variant {
3322     fn clean(&self, cx: &DocContext<'_>) -> Item {
3323         Item {
3324             name: Some(self.name.clean(cx)),
3325             attrs: self.attrs.clean(cx),
3326             source: self.whence.clean(cx),
3327             visibility: None,
3328             stability: self.stab.clean(cx),
3329             deprecation: self.depr.clean(cx),
3330             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3331             inner: VariantItem(Variant {
3332                 kind: self.def.clean(cx),
3333             }),
3334         }
3335     }
3336 }
3337
3338 impl<'tcx> Clean<Item> for ty::VariantDef {
3339     fn clean(&self, cx: &DocContext<'_>) -> Item {
3340         let kind = match self.ctor_kind {
3341             CtorKind::Const => VariantKind::CLike,
3342             CtorKind::Fn => {
3343                 VariantKind::Tuple(
3344                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
3345                 )
3346             }
3347             CtorKind::Fictive => {
3348                 VariantKind::Struct(VariantStruct {
3349                     struct_type: doctree::Plain,
3350                     fields_stripped: false,
3351                     fields: self.fields.iter().map(|field| {
3352                         Item {
3353                             source: cx.tcx.def_span(field.did).clean(cx),
3354                             name: Some(field.ident.name.clean(cx)),
3355                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
3356                             visibility: field.vis.clean(cx),
3357                             def_id: field.did,
3358                             stability: get_stability(cx, field.did),
3359                             deprecation: get_deprecation(cx, field.did),
3360                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
3361                         }
3362                     }).collect()
3363                 })
3364             }
3365         };
3366         Item {
3367             name: Some(self.ident.clean(cx)),
3368             attrs: inline::load_attrs(cx, self.def_id),
3369             source: cx.tcx.def_span(self.def_id).clean(cx),
3370             visibility: Some(Inherited),
3371             def_id: self.def_id,
3372             inner: VariantItem(Variant { kind }),
3373             stability: get_stability(cx, self.def_id),
3374             deprecation: get_deprecation(cx, self.def_id),
3375         }
3376     }
3377 }
3378
3379 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3380 pub enum VariantKind {
3381     CLike,
3382     Tuple(Vec<Type>),
3383     Struct(VariantStruct),
3384 }
3385
3386 impl Clean<VariantKind> for hir::VariantData {
3387     fn clean(&self, cx: &DocContext<'_>) -> VariantKind {
3388         match self {
3389             hir::VariantData::Struct(..) => VariantKind::Struct(self.clean(cx)),
3390             hir::VariantData::Tuple(..) =>
3391                 VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect()),
3392             hir::VariantData::Unit(..) => VariantKind::CLike,
3393         }
3394     }
3395 }
3396
3397 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3398 pub struct Span {
3399     pub filename: FileName,
3400     pub loline: usize,
3401     pub locol: usize,
3402     pub hiline: usize,
3403     pub hicol: usize,
3404     pub original: syntax_pos::Span,
3405 }
3406
3407 impl Span {
3408     pub fn empty() -> Span {
3409         Span {
3410             filename: FileName::Anon(0),
3411             loline: 0, locol: 0,
3412             hiline: 0, hicol: 0,
3413             original: syntax_pos::DUMMY_SP,
3414         }
3415     }
3416
3417     pub fn span(&self) -> syntax_pos::Span {
3418         self.original
3419     }
3420 }
3421
3422 impl Clean<Span> for syntax_pos::Span {
3423     fn clean(&self, cx: &DocContext<'_>) -> Span {
3424         if self.is_dummy() {
3425             return Span::empty();
3426         }
3427
3428         let cm = cx.sess().source_map();
3429         let filename = cm.span_to_filename(*self);
3430         let lo = cm.lookup_char_pos(self.lo());
3431         let hi = cm.lookup_char_pos(self.hi());
3432         Span {
3433             filename,
3434             loline: lo.line,
3435             locol: lo.col.to_usize(),
3436             hiline: hi.line,
3437             hicol: hi.col.to_usize(),
3438             original: *self,
3439         }
3440     }
3441 }
3442
3443 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3444 pub struct Path {
3445     pub global: bool,
3446     pub res: Res,
3447     pub segments: Vec<PathSegment>,
3448 }
3449
3450 impl Path {
3451     pub fn last_name(&self) -> &str {
3452         self.segments.last().expect("segments were empty").name.as_str()
3453     }
3454 }
3455
3456 impl Clean<Path> for hir::Path {
3457     fn clean(&self, cx: &DocContext<'_>) -> Path {
3458         Path {
3459             global: self.is_global(),
3460             res: self.res,
3461             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
3462         }
3463     }
3464 }
3465
3466 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3467 pub enum GenericArg {
3468     Lifetime(Lifetime),
3469     Type(Type),
3470     Const(Constant),
3471 }
3472
3473 impl fmt::Display for GenericArg {
3474     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3475         match self {
3476             GenericArg::Lifetime(lt) => lt.fmt(f),
3477             GenericArg::Type(ty) => ty.fmt(f),
3478             GenericArg::Const(ct) => ct.fmt(f),
3479         }
3480     }
3481 }
3482
3483 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3484 pub enum GenericArgs {
3485     AngleBracketed {
3486         args: Vec<GenericArg>,
3487         bindings: Vec<TypeBinding>,
3488     },
3489     Parenthesized {
3490         inputs: Vec<Type>,
3491         output: Option<Type>,
3492     }
3493 }
3494
3495 impl Clean<GenericArgs> for hir::GenericArgs {
3496     fn clean(&self, cx: &DocContext<'_>) -> GenericArgs {
3497         if self.parenthesized {
3498             let output = self.bindings[0].ty.clean(cx);
3499             GenericArgs::Parenthesized {
3500                 inputs: self.inputs().clean(cx),
3501                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
3502             }
3503         } else {
3504             let elide_lifetimes = self.args.iter().all(|arg| match arg {
3505                 hir::GenericArg::Lifetime(lt) => lt.is_elided(),
3506                 _ => true,
3507             });
3508             GenericArgs::AngleBracketed {
3509                 args: self.args.iter().filter_map(|arg| match arg {
3510                     hir::GenericArg::Lifetime(lt) if !elide_lifetimes => {
3511                         Some(GenericArg::Lifetime(lt.clean(cx)))
3512                     }
3513                     hir::GenericArg::Lifetime(_) => None,
3514                     hir::GenericArg::Type(ty) => Some(GenericArg::Type(ty.clean(cx))),
3515                     hir::GenericArg::Const(ct) => Some(GenericArg::Const(ct.clean(cx))),
3516                 }).collect(),
3517                 bindings: self.bindings.clean(cx),
3518             }
3519         }
3520     }
3521 }
3522
3523 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3524 pub struct PathSegment {
3525     pub name: String,
3526     pub args: GenericArgs,
3527 }
3528
3529 impl Clean<PathSegment> for hir::PathSegment {
3530     fn clean(&self, cx: &DocContext<'_>) -> PathSegment {
3531         PathSegment {
3532             name: self.ident.name.clean(cx),
3533             args: self.with_generic_args(|generic_args| generic_args.clean(cx))
3534         }
3535     }
3536 }
3537
3538 fn strip_type(ty: Type) -> Type {
3539     match ty {
3540         Type::ResolvedPath { path, param_names, did, is_generic } => {
3541             Type::ResolvedPath { path: strip_path(&path), param_names, did, is_generic }
3542         }
3543         Type::Tuple(inner_tys) => {
3544             Type::Tuple(inner_tys.iter().map(|t| strip_type(t.clone())).collect())
3545         }
3546         Type::Slice(inner_ty) => Type::Slice(Box::new(strip_type(*inner_ty))),
3547         Type::Array(inner_ty, s) => Type::Array(Box::new(strip_type(*inner_ty)), s),
3548         Type::Unique(inner_ty) => Type::Unique(Box::new(strip_type(*inner_ty))),
3549         Type::RawPointer(m, inner_ty) => Type::RawPointer(m, Box::new(strip_type(*inner_ty))),
3550         Type::BorrowedRef { lifetime, mutability, type_ } => {
3551             Type::BorrowedRef { lifetime, mutability, type_: Box::new(strip_type(*type_)) }
3552         }
3553         Type::QPath { name, self_type, trait_ } => {
3554             Type::QPath {
3555                 name,
3556                 self_type: Box::new(strip_type(*self_type)), trait_: Box::new(strip_type(*trait_))
3557             }
3558         }
3559         _ => ty
3560     }
3561 }
3562
3563 fn strip_path(path: &Path) -> Path {
3564     let segments = path.segments.iter().map(|s| {
3565         PathSegment {
3566             name: s.name.clone(),
3567             args: GenericArgs::AngleBracketed {
3568                 args: vec![],
3569                 bindings: vec![],
3570             }
3571         }
3572     }).collect();
3573
3574     Path {
3575         global: path.global,
3576         res: path.res.clone(),
3577         segments,
3578     }
3579 }
3580
3581 fn qpath_to_string(p: &hir::QPath) -> String {
3582     let segments = match *p {
3583         hir::QPath::Resolved(_, ref path) => &path.segments,
3584         hir::QPath::TypeRelative(_, ref segment) => return segment.ident.to_string(),
3585     };
3586
3587     let mut s = String::new();
3588     for (i, seg) in segments.iter().enumerate() {
3589         if i > 0 {
3590             s.push_str("::");
3591         }
3592         if seg.ident.name != kw::PathRoot {
3593             s.push_str(&*seg.ident.as_str());
3594         }
3595     }
3596     s
3597 }
3598
3599 impl Clean<String> for Ident {
3600     #[inline]
3601     fn clean(&self, cx: &DocContext<'_>) -> String {
3602         self.name.clean(cx)
3603     }
3604 }
3605
3606 impl Clean<String> for ast::Name {
3607     #[inline]
3608     fn clean(&self, _: &DocContext<'_>) -> String {
3609         self.to_string()
3610     }
3611 }
3612
3613 impl Clean<String> for InternedString {
3614     #[inline]
3615     fn clean(&self, _: &DocContext<'_>) -> String {
3616         self.to_string()
3617     }
3618 }
3619
3620 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3621 pub struct Typedef {
3622     pub type_: Type,
3623     pub generics: Generics,
3624 }
3625
3626 impl Clean<Item> for doctree::Typedef {
3627     fn clean(&self, cx: &DocContext<'_>) -> Item {
3628         Item {
3629             name: Some(self.name.clean(cx)),
3630             attrs: self.attrs.clean(cx),
3631             source: self.whence.clean(cx),
3632             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3633             visibility: self.vis.clean(cx),
3634             stability: self.stab.clean(cx),
3635             deprecation: self.depr.clean(cx),
3636             inner: TypedefItem(Typedef {
3637                 type_: self.ty.clean(cx),
3638                 generics: self.gen.clean(cx),
3639             }, false),
3640         }
3641     }
3642 }
3643
3644 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3645 pub struct Existential {
3646     pub bounds: Vec<GenericBound>,
3647     pub generics: Generics,
3648 }
3649
3650 impl Clean<Item> for doctree::Existential {
3651     fn clean(&self, cx: &DocContext<'_>) -> Item {
3652         Item {
3653             name: Some(self.name.clean(cx)),
3654             attrs: self.attrs.clean(cx),
3655             source: self.whence.clean(cx),
3656             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3657             visibility: self.vis.clean(cx),
3658             stability: self.stab.clean(cx),
3659             deprecation: self.depr.clean(cx),
3660             inner: ExistentialItem(Existential {
3661                 bounds: self.exist_ty.bounds.clean(cx),
3662                 generics: self.exist_ty.generics.clean(cx),
3663             }, false),
3664         }
3665     }
3666 }
3667
3668 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3669 pub struct BareFunctionDecl {
3670     pub unsafety: hir::Unsafety,
3671     pub generic_params: Vec<GenericParamDef>,
3672     pub decl: FnDecl,
3673     pub abi: Abi,
3674 }
3675
3676 impl Clean<BareFunctionDecl> for hir::BareFnTy {
3677     fn clean(&self, cx: &DocContext<'_>) -> BareFunctionDecl {
3678         let (generic_params, decl) = enter_impl_trait(cx, || {
3679             (self.generic_params.clean(cx), (&*self.decl, &self.arg_names[..]).clean(cx))
3680         });
3681         BareFunctionDecl {
3682             unsafety: self.unsafety,
3683             abi: self.abi,
3684             decl,
3685             generic_params,
3686         }
3687     }
3688 }
3689
3690 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3691 pub struct Static {
3692     pub type_: Type,
3693     pub mutability: Mutability,
3694     /// It's useful to have the value of a static documented, but I have no
3695     /// desire to represent expressions (that'd basically be all of the AST,
3696     /// which is huge!). So, have a string.
3697     pub expr: String,
3698 }
3699
3700 impl Clean<Item> for doctree::Static {
3701     fn clean(&self, cx: &DocContext<'_>) -> Item {
3702         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
3703         Item {
3704             name: Some(self.name.clean(cx)),
3705             attrs: self.attrs.clean(cx),
3706             source: self.whence.clean(cx),
3707             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3708             visibility: self.vis.clean(cx),
3709             stability: self.stab.clean(cx),
3710             deprecation: self.depr.clean(cx),
3711             inner: StaticItem(Static {
3712                 type_: self.type_.clean(cx),
3713                 mutability: self.mutability.clean(cx),
3714                 expr: print_const_expr(cx, self.expr),
3715             }),
3716         }
3717     }
3718 }
3719
3720 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
3721 pub struct Constant {
3722     pub type_: Type,
3723     pub expr: String,
3724 }
3725
3726 impl Clean<Item> for doctree::Constant {
3727     fn clean(&self, cx: &DocContext<'_>) -> Item {
3728         Item {
3729             name: Some(self.name.clean(cx)),
3730             attrs: self.attrs.clean(cx),
3731             source: self.whence.clean(cx),
3732             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3733             visibility: self.vis.clean(cx),
3734             stability: self.stab.clean(cx),
3735             deprecation: self.depr.clean(cx),
3736             inner: ConstantItem(Constant {
3737                 type_: self.type_.clean(cx),
3738                 expr: print_const_expr(cx, self.expr),
3739             }),
3740         }
3741     }
3742 }
3743
3744 #[derive(Debug, Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Hash)]
3745 pub enum Mutability {
3746     Mutable,
3747     Immutable,
3748 }
3749
3750 impl Clean<Mutability> for hir::Mutability {
3751     fn clean(&self, _: &DocContext<'_>) -> Mutability {
3752         match self {
3753             &hir::MutMutable => Mutable,
3754             &hir::MutImmutable => Immutable,
3755         }
3756     }
3757 }
3758
3759 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Debug, Hash)]
3760 pub enum ImplPolarity {
3761     Positive,
3762     Negative,
3763 }
3764
3765 impl Clean<ImplPolarity> for hir::ImplPolarity {
3766     fn clean(&self, _: &DocContext<'_>) -> ImplPolarity {
3767         match self {
3768             &hir::ImplPolarity::Positive => ImplPolarity::Positive,
3769             &hir::ImplPolarity::Negative => ImplPolarity::Negative,
3770         }
3771     }
3772 }
3773
3774 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3775 pub struct Impl {
3776     pub unsafety: hir::Unsafety,
3777     pub generics: Generics,
3778     pub provided_trait_methods: FxHashSet<String>,
3779     pub trait_: Option<Type>,
3780     pub for_: Type,
3781     pub items: Vec<Item>,
3782     pub polarity: Option<ImplPolarity>,
3783     pub synthetic: bool,
3784     pub blanket_impl: Option<Type>,
3785 }
3786
3787 pub fn get_auto_trait_and_blanket_impls(
3788     cx: &DocContext<'tcx>,
3789     ty: Ty<'tcx>,
3790     param_env_def_id: DefId,
3791 ) -> impl Iterator<Item = Item> {
3792     AutoTraitFinder::new(cx).get_auto_trait_impls(ty, param_env_def_id).into_iter()
3793         .chain(BlanketImplFinder::new(cx).get_blanket_impls(ty, param_env_def_id))
3794 }
3795
3796 impl Clean<Vec<Item>> for doctree::Impl {
3797     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3798         let mut ret = Vec::new();
3799         let trait_ = self.trait_.clean(cx);
3800         let items = self.items.clean(cx);
3801
3802         // If this impl block is an implementation of the Deref trait, then we
3803         // need to try inlining the target's inherent impl blocks as well.
3804         if trait_.def_id() == cx.tcx.lang_items().deref_trait() {
3805             build_deref_target_impls(cx, &items, &mut ret);
3806         }
3807
3808         let provided = trait_.def_id().map(|did| {
3809             cx.tcx.provided_trait_methods(did)
3810                   .into_iter()
3811                   .map(|meth| meth.ident.to_string())
3812                   .collect()
3813         }).unwrap_or_default();
3814
3815         ret.push(Item {
3816             name: None,
3817             attrs: self.attrs.clean(cx),
3818             source: self.whence.clean(cx),
3819             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3820             visibility: self.vis.clean(cx),
3821             stability: self.stab.clean(cx),
3822             deprecation: self.depr.clean(cx),
3823             inner: ImplItem(Impl {
3824                 unsafety: self.unsafety,
3825                 generics: self.generics.clean(cx),
3826                 provided_trait_methods: provided,
3827                 trait_,
3828                 for_: self.for_.clean(cx),
3829                 items,
3830                 polarity: Some(self.polarity.clean(cx)),
3831                 synthetic: false,
3832                 blanket_impl: None,
3833             })
3834         });
3835         ret
3836     }
3837 }
3838
3839 fn build_deref_target_impls(cx: &DocContext<'_>,
3840                             items: &[Item],
3841                             ret: &mut Vec<Item>) {
3842     use self::PrimitiveType::*;
3843     let tcx = cx.tcx;
3844
3845     for item in items {
3846         let target = match item.inner {
3847             TypedefItem(ref t, true) => &t.type_,
3848             _ => continue,
3849         };
3850         let primitive = match *target {
3851             ResolvedPath { did, .. } if did.is_local() => continue,
3852             ResolvedPath { did, .. } => {
3853                 ret.extend(inline::build_impls(cx, did));
3854                 continue
3855             }
3856             _ => match target.primitive_type() {
3857                 Some(prim) => prim,
3858                 None => continue,
3859             }
3860         };
3861         let did = match primitive {
3862             Isize => tcx.lang_items().isize_impl(),
3863             I8 => tcx.lang_items().i8_impl(),
3864             I16 => tcx.lang_items().i16_impl(),
3865             I32 => tcx.lang_items().i32_impl(),
3866             I64 => tcx.lang_items().i64_impl(),
3867             I128 => tcx.lang_items().i128_impl(),
3868             Usize => tcx.lang_items().usize_impl(),
3869             U8 => tcx.lang_items().u8_impl(),
3870             U16 => tcx.lang_items().u16_impl(),
3871             U32 => tcx.lang_items().u32_impl(),
3872             U64 => tcx.lang_items().u64_impl(),
3873             U128 => tcx.lang_items().u128_impl(),
3874             F32 => tcx.lang_items().f32_impl(),
3875             F64 => tcx.lang_items().f64_impl(),
3876             Char => tcx.lang_items().char_impl(),
3877             Bool => None,
3878             Str => tcx.lang_items().str_impl(),
3879             Slice => tcx.lang_items().slice_impl(),
3880             Array => tcx.lang_items().slice_impl(),
3881             Tuple => None,
3882             Unit => None,
3883             RawPointer => tcx.lang_items().const_ptr_impl(),
3884             Reference => None,
3885             Fn => None,
3886             Never => None,
3887             CVarArgs => tcx.lang_items().va_list(),
3888         };
3889         if let Some(did) = did {
3890             if !did.is_local() {
3891                 inline::build_impl(cx, did, ret);
3892             }
3893         }
3894     }
3895 }
3896
3897 impl Clean<Vec<Item>> for doctree::ExternCrate {
3898     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3899
3900         let please_inline = self.vis.node.is_pub() && self.attrs.iter().any(|a| {
3901             a.check_name(sym::doc) && match a.meta_item_list() {
3902                 Some(l) => attr::list_contains_name(&l, sym::inline),
3903                 None => false,
3904             }
3905         });
3906
3907         if please_inline {
3908             let mut visited = FxHashSet::default();
3909
3910             let res = Res::Def(
3911                 DefKind::Mod,
3912                 DefId {
3913                     krate: self.cnum,
3914                     index: CRATE_DEF_INDEX,
3915                 },
3916             );
3917
3918             if let Some(items) = inline::try_inline(cx, res, self.name, &mut visited) {
3919                 return items;
3920             }
3921         }
3922
3923         vec![Item {
3924             name: None,
3925             attrs: self.attrs.clean(cx),
3926             source: self.whence.clean(cx),
3927             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
3928             visibility: self.vis.clean(cx),
3929             stability: None,
3930             deprecation: None,
3931             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
3932         }]
3933     }
3934 }
3935
3936 impl Clean<Vec<Item>> for doctree::Import {
3937     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3938         // We consider inlining the documentation of `pub use` statements, but we
3939         // forcefully don't inline if this is not public or if the
3940         // #[doc(no_inline)] attribute is present.
3941         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
3942         let mut denied = !self.vis.node.is_pub() || self.attrs.iter().any(|a| {
3943             a.check_name(sym::doc) && match a.meta_item_list() {
3944                 Some(l) => attr::list_contains_name(&l, sym::no_inline) ||
3945                            attr::list_contains_name(&l, sym::hidden),
3946                 None => false,
3947             }
3948         });
3949         // Also check whether imports were asked to be inlined, in case we're trying to re-export a
3950         // crate in Rust 2018+
3951         let please_inline = self.attrs.lists(sym::doc).has_word(sym::inline);
3952         let path = self.path.clean(cx);
3953         let inner = if self.glob {
3954             if !denied {
3955                 let mut visited = FxHashSet::default();
3956                 if let Some(items) = inline::try_inline_glob(cx, path.res, &mut visited) {
3957                     return items;
3958                 }
3959             }
3960
3961             Import::Glob(resolve_use_source(cx, path))
3962         } else {
3963             let name = self.name;
3964             if !please_inline {
3965                 match path.res {
3966                     Res::Def(DefKind::Mod, did) => {
3967                         if !did.is_local() && did.index == CRATE_DEF_INDEX {
3968                             // if we're `pub use`ing an extern crate root, don't inline it unless we
3969                             // were specifically asked for it
3970                             denied = true;
3971                         }
3972                     }
3973                     _ => {}
3974                 }
3975             }
3976             if !denied {
3977                 let mut visited = FxHashSet::default();
3978                 if let Some(items) = inline::try_inline(cx, path.res, name, &mut visited) {
3979                     return items;
3980                 }
3981             }
3982             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
3983         };
3984
3985         vec![Item {
3986             name: None,
3987             attrs: self.attrs.clean(cx),
3988             source: self.whence.clean(cx),
3989             def_id: cx.tcx.hir().local_def_id(ast::CRATE_NODE_ID),
3990             visibility: self.vis.clean(cx),
3991             stability: None,
3992             deprecation: None,
3993             inner: ImportItem(inner)
3994         }]
3995     }
3996 }
3997
3998 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3999 pub enum Import {
4000     // use source as str;
4001     Simple(String, ImportSource),
4002     // use source::*;
4003     Glob(ImportSource)
4004 }
4005
4006 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4007 pub struct ImportSource {
4008     pub path: Path,
4009     pub did: Option<DefId>,
4010 }
4011
4012 impl Clean<Vec<Item>> for hir::ForeignMod {
4013     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
4014         let mut items = self.items.clean(cx);
4015         for item in &mut items {
4016             if let ForeignFunctionItem(ref mut f) = item.inner {
4017                 f.header.abi = self.abi;
4018             }
4019         }
4020         items
4021     }
4022 }
4023
4024 impl Clean<Item> for hir::ForeignItem {
4025     fn clean(&self, cx: &DocContext<'_>) -> Item {
4026         let inner = match self.node {
4027             hir::ForeignItemKind::Fn(ref decl, ref names, ref generics) => {
4028                 let (generics, decl) = enter_impl_trait(cx, || {
4029                     (generics.clean(cx), (&**decl, &names[..]).clean(cx))
4030                 });
4031                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
4032                 ForeignFunctionItem(Function {
4033                     decl,
4034                     generics,
4035                     header: hir::FnHeader {
4036                         unsafety: hir::Unsafety::Unsafe,
4037                         abi: Abi::Rust,
4038                         constness: hir::Constness::NotConst,
4039                         asyncness: hir::IsAsync::NotAsync,
4040                     },
4041                     all_types,
4042                     ret_types,
4043                 })
4044             }
4045             hir::ForeignItemKind::Static(ref ty, mutbl) => {
4046                 ForeignStaticItem(Static {
4047                     type_: ty.clean(cx),
4048                     mutability: mutbl.clean(cx),
4049                     expr: String::new(),
4050                 })
4051             }
4052             hir::ForeignItemKind::Type => {
4053                 ForeignTypeItem
4054             }
4055         };
4056
4057         let local_did = cx.tcx.hir().local_def_id_from_hir_id(self.hir_id);
4058
4059         Item {
4060             name: Some(self.ident.clean(cx)),
4061             attrs: self.attrs.clean(cx),
4062             source: self.span.clean(cx),
4063             def_id: local_did,
4064             visibility: self.vis.clean(cx),
4065             stability: get_stability(cx, local_did),
4066             deprecation: get_deprecation(cx, local_did),
4067             inner,
4068         }
4069     }
4070 }
4071
4072 // Utilities
4073
4074 pub trait ToSource {
4075     fn to_src(&self, cx: &DocContext<'_>) -> String;
4076 }
4077
4078 impl ToSource for syntax_pos::Span {
4079     fn to_src(&self, cx: &DocContext<'_>) -> String {
4080         debug!("converting span {:?} to snippet", self.clean(cx));
4081         let sn = match cx.sess().source_map().span_to_snippet(*self) {
4082             Ok(x) => x,
4083             Err(_) => String::new()
4084         };
4085         debug!("got snippet {}", sn);
4086         sn
4087     }
4088 }
4089
4090 fn name_from_pat(p: &hir::Pat) -> String {
4091     use rustc::hir::*;
4092     debug!("Trying to get a name from pattern: {:?}", p);
4093
4094     match p.node {
4095         PatKind::Wild => "_".to_string(),
4096         PatKind::Binding(_, _, ident, _) => ident.to_string(),
4097         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
4098         PatKind::Struct(ref name, ref fields, etc) => {
4099             format!("{} {{ {}{} }}", qpath_to_string(name),
4100                 fields.iter().map(|&Spanned { node: ref fp, .. }|
4101                                   format!("{}: {}", fp.ident, name_from_pat(&*fp.pat)))
4102                              .collect::<Vec<String>>().join(", "),
4103                 if etc { ", .." } else { "" }
4104             )
4105         }
4106         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
4107                                             .collect::<Vec<String>>().join(", ")),
4108         PatKind::Box(ref p) => name_from_pat(&**p),
4109         PatKind::Ref(ref p, _) => name_from_pat(&**p),
4110         PatKind::Lit(..) => {
4111             warn!("tried to get argument name from PatKind::Lit, \
4112                   which is silly in function arguments");
4113             "()".to_string()
4114         },
4115         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
4116                               which is not allowed in function arguments"),
4117         PatKind::Slice(ref begin, ref mid, ref end) => {
4118             let begin = begin.iter().map(|p| name_from_pat(&**p));
4119             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
4120             let end = end.iter().map(|p| name_from_pat(&**p));
4121             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
4122         },
4123     }
4124 }
4125
4126 fn print_const(cx: &DocContext<'_>, n: &ty::Const<'_>) -> String {
4127     match n.val {
4128         ConstValue::Unevaluated(def_id, _) => {
4129             if let Some(hir_id) = cx.tcx.hir().as_local_hir_id(def_id) {
4130                 print_const_expr(cx, cx.tcx.hir().body_owned_by(hir_id))
4131             } else {
4132                 inline::print_inlined_const(cx, def_id)
4133             }
4134         },
4135         _ => {
4136             let mut s = n.to_string();
4137             // array lengths are obviously usize
4138             if s.ends_with("usize") {
4139                 let n = s.len() - "usize".len();
4140                 s.truncate(n);
4141                 if s.ends_with(": ") {
4142                     let n = s.len() - ": ".len();
4143                     s.truncate(n);
4144                 }
4145             }
4146             s
4147         },
4148     }
4149 }
4150
4151 fn print_const_expr(cx: &DocContext<'_>, body: hir::BodyId) -> String {
4152     cx.tcx.hir().hir_to_pretty_string(body.hir_id)
4153 }
4154
4155 /// Given a type Path, resolve it to a Type using the TyCtxt
4156 fn resolve_type(cx: &DocContext<'_>,
4157                 path: Path,
4158                 id: hir::HirId) -> Type {
4159     if id == hir::DUMMY_HIR_ID {
4160         debug!("resolve_type({:?})", path);
4161     } else {
4162         debug!("resolve_type({:?},{:?})", path, id);
4163     }
4164
4165     let is_generic = match path.res {
4166         Res::PrimTy(p) => match p {
4167             hir::Str => return Primitive(PrimitiveType::Str),
4168             hir::Bool => return Primitive(PrimitiveType::Bool),
4169             hir::Char => return Primitive(PrimitiveType::Char),
4170             hir::Int(int_ty) => return Primitive(int_ty.into()),
4171             hir::Uint(uint_ty) => return Primitive(uint_ty.into()),
4172             hir::Float(float_ty) => return Primitive(float_ty.into()),
4173         },
4174         Res::SelfTy(..) if path.segments.len() == 1 => {
4175             return Generic(kw::SelfUpper.to_string());
4176         }
4177         Res::Def(DefKind::TyParam, _) if path.segments.len() == 1 => {
4178             return Generic(format!("{:#}", path));
4179         }
4180         Res::SelfTy(..)
4181         | Res::Def(DefKind::TyParam, _)
4182         | Res::Def(DefKind::AssocTy, _) => true,
4183         _ => false,
4184     };
4185     let did = register_res(&*cx, path.res);
4186     ResolvedPath { path: path, param_names: None, did: did, is_generic: is_generic }
4187 }
4188
4189 pub fn register_res(cx: &DocContext<'_>, res: Res) -> DefId {
4190     debug!("register_res({:?})", res);
4191
4192     let (did, kind) = match res {
4193         Res::Def(DefKind::Fn, i) => (i, TypeKind::Function),
4194         Res::Def(DefKind::TyAlias, i) => (i, TypeKind::Typedef),
4195         Res::Def(DefKind::Enum, i) => (i, TypeKind::Enum),
4196         Res::Def(DefKind::Trait, i) => (i, TypeKind::Trait),
4197         Res::Def(DefKind::Struct, i) => (i, TypeKind::Struct),
4198         Res::Def(DefKind::Union, i) => (i, TypeKind::Union),
4199         Res::Def(DefKind::Mod, i) => (i, TypeKind::Module),
4200         Res::Def(DefKind::ForeignTy, i) => (i, TypeKind::Foreign),
4201         Res::Def(DefKind::Const, i) => (i, TypeKind::Const),
4202         Res::Def(DefKind::Static, i) => (i, TypeKind::Static),
4203         Res::Def(DefKind::Variant, i) => (cx.tcx.parent(i).expect("cannot get parent def id"),
4204                             TypeKind::Enum),
4205         Res::Def(DefKind::Macro(mac_kind), i) => match mac_kind {
4206             MacroKind::Bang => (i, TypeKind::Macro),
4207             MacroKind::Attr => (i, TypeKind::Attr),
4208             MacroKind::Derive => (i, TypeKind::Derive),
4209             MacroKind::ProcMacroStub => unreachable!(),
4210         },
4211         Res::Def(DefKind::TraitAlias, i) => (i, TypeKind::TraitAlias),
4212         Res::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
4213         Res::SelfTy(_, Some(impl_def_id)) => return impl_def_id,
4214         _ => return res.def_id()
4215     };
4216     if did.is_local() { return did }
4217     inline::record_extern_fqn(cx, did, kind);
4218     if let TypeKind::Trait = kind {
4219         inline::record_extern_trait(cx, did);
4220     }
4221     did
4222 }
4223
4224 fn resolve_use_source(cx: &DocContext<'_>, path: Path) -> ImportSource {
4225     ImportSource {
4226         did: if path.res.opt_def_id().is_none() {
4227             None
4228         } else {
4229             Some(register_res(cx, path.res))
4230         },
4231         path,
4232     }
4233 }
4234
4235 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4236 pub struct Macro {
4237     pub source: String,
4238     pub imported_from: Option<String>,
4239 }
4240
4241 impl Clean<Item> for doctree::Macro {
4242     fn clean(&self, cx: &DocContext<'_>) -> Item {
4243         let name = self.name.clean(cx);
4244         Item {
4245             name: Some(name.clone()),
4246             attrs: self.attrs.clean(cx),
4247             source: self.whence.clean(cx),
4248             visibility: Some(Public),
4249             stability: self.stab.clean(cx),
4250             deprecation: self.depr.clean(cx),
4251             def_id: self.def_id,
4252             inner: MacroItem(Macro {
4253                 source: format!("macro_rules! {} {{\n{}}}",
4254                                 name,
4255                                 self.matchers.iter().map(|span| {
4256                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
4257                                 }).collect::<String>()),
4258                 imported_from: self.imported_from.clean(cx),
4259             }),
4260         }
4261     }
4262 }
4263
4264 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4265 pub struct ProcMacro {
4266     pub kind: MacroKind,
4267     pub helpers: Vec<String>,
4268 }
4269
4270 impl Clean<Item> for doctree::ProcMacro {
4271     fn clean(&self, cx: &DocContext<'_>) -> Item {
4272         Item {
4273             name: Some(self.name.clean(cx)),
4274             attrs: self.attrs.clean(cx),
4275             source: self.whence.clean(cx),
4276             visibility: Some(Public),
4277             stability: self.stab.clean(cx),
4278             deprecation: self.depr.clean(cx),
4279             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
4280             inner: ProcMacroItem(ProcMacro {
4281                 kind: self.kind,
4282                 helpers: self.helpers.clean(cx),
4283             }),
4284         }
4285     }
4286 }
4287
4288 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4289 pub struct Stability {
4290     pub level: stability::StabilityLevel,
4291     pub feature: Option<String>,
4292     pub since: String,
4293     pub deprecation: Option<Deprecation>,
4294     pub unstable_reason: Option<String>,
4295     pub issue: Option<u32>,
4296 }
4297
4298 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4299 pub struct Deprecation {
4300     pub since: Option<String>,
4301     pub note: Option<String>,
4302 }
4303
4304 impl Clean<Stability> for attr::Stability {
4305     fn clean(&self, _: &DocContext<'_>) -> Stability {
4306         Stability {
4307             level: stability::StabilityLevel::from_attr_level(&self.level),
4308             feature: Some(self.feature.to_string()).filter(|f| !f.is_empty()),
4309             since: match self.level {
4310                 attr::Stable {ref since} => since.to_string(),
4311                 _ => String::new(),
4312             },
4313             deprecation: self.rustc_depr.as_ref().map(|d| {
4314                 Deprecation {
4315                     note: Some(d.reason.to_string()).filter(|r| !r.is_empty()),
4316                     since: Some(d.since.to_string()).filter(|d| !d.is_empty()),
4317                 }
4318             }),
4319             unstable_reason: match self.level {
4320                 attr::Unstable { reason: Some(ref reason), .. } => Some(reason.to_string()),
4321                 _ => None,
4322             },
4323             issue: match self.level {
4324                 attr::Unstable {issue, ..} => Some(issue),
4325                 _ => None,
4326             }
4327         }
4328     }
4329 }
4330
4331 impl<'a> Clean<Stability> for &'a attr::Stability {
4332     fn clean(&self, dc: &DocContext<'_>) -> Stability {
4333         (**self).clean(dc)
4334     }
4335 }
4336
4337 impl Clean<Deprecation> for attr::Deprecation {
4338     fn clean(&self, _: &DocContext<'_>) -> Deprecation {
4339         Deprecation {
4340             since: self.since.map(|s| s.to_string()).filter(|s| !s.is_empty()),
4341             note: self.note.map(|n| n.to_string()).filter(|n| !n.is_empty()),
4342         }
4343     }
4344 }
4345
4346 /// An equality constraint on an associated type, e.g., `A = Bar` in `Foo<A = Bar>`
4347 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug, Hash)]
4348 pub struct TypeBinding {
4349     pub name: String,
4350     pub ty: Type
4351 }
4352
4353 impl Clean<TypeBinding> for hir::TypeBinding {
4354     fn clean(&self, cx: &DocContext<'_>) -> TypeBinding {
4355         TypeBinding {
4356             name: self.ident.name.clean(cx),
4357             ty: self.ty.clean(cx)
4358         }
4359     }
4360 }
4361
4362 pub fn def_id_to_path(
4363     cx: &DocContext<'_>,
4364     did: DefId,
4365     name: Option<String>
4366 ) -> Vec<String> {
4367     let crate_name = name.unwrap_or_else(|| cx.tcx.crate_name(did.krate).to_string());
4368     let relative = cx.tcx.def_path(did).data.into_iter().filter_map(|elem| {
4369         // extern blocks have an empty name
4370         let s = elem.data.to_string();
4371         if !s.is_empty() {
4372             Some(s)
4373         } else {
4374             None
4375         }
4376     });
4377     once(crate_name).chain(relative).collect()
4378 }
4379
4380 pub fn enter_impl_trait<F, R>(cx: &DocContext<'_>, f: F) -> R
4381 where
4382     F: FnOnce() -> R,
4383 {
4384     let old_bounds = mem::replace(&mut *cx.impl_trait_bounds.borrow_mut(), Default::default());
4385     let r = f();
4386     assert!(cx.impl_trait_bounds.borrow().is_empty());
4387     *cx.impl_trait_bounds.borrow_mut() = old_bounds;
4388     r
4389 }
4390
4391 // Start of code copied from rust-clippy
4392
4393 pub fn path_to_def_local(tcx: TyCtxt<'_, '_, '_>, path: &[Symbol]) -> Option<DefId> {
4394     let krate = tcx.hir().krate();
4395     let mut items = krate.module.item_ids.clone();
4396     let mut path_it = path.iter().peekable();
4397
4398     loop {
4399         let segment = path_it.next()?;
4400
4401         for item_id in mem::replace(&mut items, HirVec::new()).iter() {
4402             let item = tcx.hir().expect_item_by_hir_id(item_id.id);
4403             if item.ident.name == *segment {
4404                 if path_it.peek().is_none() {
4405                     return Some(tcx.hir().local_def_id_from_hir_id(item_id.id))
4406                 }
4407
4408                 items = match &item.node {
4409                     &hir::ItemKind::Mod(ref m) => m.item_ids.clone(),
4410                     _ => panic!("Unexpected item {:?} in path {:?} path")
4411                 };
4412                 break;
4413             }
4414         }
4415     }
4416 }
4417
4418 pub fn path_to_def(tcx: TyCtxt<'_, '_, '_>, path: &[Symbol]) -> Option<DefId> {
4419     let crates = tcx.crates();
4420
4421     let krate = crates
4422         .iter()
4423         .find(|&&krate| tcx.crate_name(krate) == path[0]);
4424
4425     if let Some(krate) = krate {
4426         let krate = DefId {
4427             krate: *krate,
4428             index: CRATE_DEF_INDEX,
4429         };
4430         let mut items = tcx.item_children(krate);
4431         let mut path_it = path.iter().skip(1).peekable();
4432
4433         loop {
4434             let segment = path_it.next()?;
4435
4436             for item in mem::replace(&mut items, &[]).iter() {
4437                 if item.ident.name == *segment {
4438                     if path_it.peek().is_none() {
4439                         return match item.res {
4440                             def::Res::Def(DefKind::Trait, did) => Some(did),
4441                             _ => None,
4442                         }
4443                     }
4444
4445                     items = tcx.item_children(item.res.def_id());
4446                     break;
4447                 }
4448             }
4449         }
4450     } else {
4451         None
4452     }
4453 }
4454
4455 // End of code copied from rust-clippy
4456
4457 #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
4458 enum RegionTarget<'tcx> {
4459     Region(Region<'tcx>),
4460     RegionVid(RegionVid)
4461 }
4462
4463 #[derive(Default, Debug, Clone)]
4464 struct RegionDeps<'tcx> {
4465     larger: FxHashSet<RegionTarget<'tcx>>,
4466     smaller: FxHashSet<RegionTarget<'tcx>>
4467 }
4468
4469 #[derive(Eq, PartialEq, Hash, Debug)]
4470 enum SimpleBound {
4471     TraitBound(Vec<PathSegment>, Vec<SimpleBound>, Vec<GenericParamDef>, hir::TraitBoundModifier),
4472     Outlives(Lifetime),
4473 }
4474
4475 impl From<GenericBound> for SimpleBound {
4476     fn from(bound: GenericBound) -> Self {
4477         match bound.clone() {
4478             GenericBound::Outlives(l) => SimpleBound::Outlives(l),
4479             GenericBound::TraitBound(t, mod_) => match t.trait_ {
4480                 Type::ResolvedPath { path, param_names, .. } => {
4481                     SimpleBound::TraitBound(path.segments,
4482                                             param_names
4483                                                 .map_or_else(|| Vec::new(), |v| v.iter()
4484                                                         .map(|p| SimpleBound::from(p.clone()))
4485                                                         .collect()),
4486                                             t.generic_params,
4487                                             mod_)
4488                 }
4489                 _ => panic!("Unexpected bound {:?}", bound),
4490             }
4491         }
4492     }
4493 }