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: match self.val {
3149                 ConstValue::Param(ty::ParamConst { name, .. }) => format!("{}", name),
3150                 e => format!("{:?}", e), // FIXME generic consts with expressions
3151             },
3152         }
3153     }
3154 }
3155
3156 impl Clean<Item> for hir::StructField {
3157     fn clean(&self, cx: &DocContext<'_>) -> Item {
3158         let local_did = cx.tcx.hir().local_def_id_from_hir_id(self.hir_id);
3159
3160         Item {
3161             name: Some(self.ident.name).clean(cx),
3162             attrs: self.attrs.clean(cx),
3163             source: self.span.clean(cx),
3164             visibility: self.vis.clean(cx),
3165             stability: get_stability(cx, local_did),
3166             deprecation: get_deprecation(cx, local_did),
3167             def_id: local_did,
3168             inner: StructFieldItem(self.ty.clean(cx)),
3169         }
3170     }
3171 }
3172
3173 impl<'tcx> Clean<Item> for ty::FieldDef {
3174     fn clean(&self, cx: &DocContext<'_>) -> Item {
3175         Item {
3176             name: Some(self.ident.name).clean(cx),
3177             attrs: cx.tcx.get_attrs(self.did).clean(cx),
3178             source: cx.tcx.def_span(self.did).clean(cx),
3179             visibility: self.vis.clean(cx),
3180             stability: get_stability(cx, self.did),
3181             deprecation: get_deprecation(cx, self.did),
3182             def_id: self.did,
3183             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
3184         }
3185     }
3186 }
3187
3188 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug)]
3189 pub enum Visibility {
3190     Public,
3191     Inherited,
3192     Crate,
3193     Restricted(DefId, Path),
3194 }
3195
3196 impl Clean<Option<Visibility>> for hir::Visibility {
3197     fn clean(&self, cx: &DocContext<'_>) -> Option<Visibility> {
3198         Some(match self.node {
3199             hir::VisibilityKind::Public => Visibility::Public,
3200             hir::VisibilityKind::Inherited => Visibility::Inherited,
3201             hir::VisibilityKind::Crate(_) => Visibility::Crate,
3202             hir::VisibilityKind::Restricted { ref path, .. } => {
3203                 let path = path.clean(cx);
3204                 let did = register_res(cx, path.res);
3205                 Visibility::Restricted(did, path)
3206             }
3207         })
3208     }
3209 }
3210
3211 impl Clean<Option<Visibility>> for ty::Visibility {
3212     fn clean(&self, _: &DocContext<'_>) -> Option<Visibility> {
3213         Some(if *self == ty::Visibility::Public { Public } else { Inherited })
3214     }
3215 }
3216
3217 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3218 pub struct Struct {
3219     pub struct_type: doctree::StructType,
3220     pub generics: Generics,
3221     pub fields: Vec<Item>,
3222     pub fields_stripped: bool,
3223 }
3224
3225 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3226 pub struct Union {
3227     pub struct_type: doctree::StructType,
3228     pub generics: Generics,
3229     pub fields: Vec<Item>,
3230     pub fields_stripped: bool,
3231 }
3232
3233 impl Clean<Item> for doctree::Struct {
3234     fn clean(&self, cx: &DocContext<'_>) -> Item {
3235         Item {
3236             name: Some(self.name.clean(cx)),
3237             attrs: self.attrs.clean(cx),
3238             source: self.whence.clean(cx),
3239             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3240             visibility: self.vis.clean(cx),
3241             stability: self.stab.clean(cx),
3242             deprecation: self.depr.clean(cx),
3243             inner: StructItem(Struct {
3244                 struct_type: self.struct_type,
3245                 generics: self.generics.clean(cx),
3246                 fields: self.fields.clean(cx),
3247                 fields_stripped: false,
3248             }),
3249         }
3250     }
3251 }
3252
3253 impl Clean<Item> for doctree::Union {
3254     fn clean(&self, cx: &DocContext<'_>) -> Item {
3255         Item {
3256             name: Some(self.name.clean(cx)),
3257             attrs: self.attrs.clean(cx),
3258             source: self.whence.clean(cx),
3259             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3260             visibility: self.vis.clean(cx),
3261             stability: self.stab.clean(cx),
3262             deprecation: self.depr.clean(cx),
3263             inner: UnionItem(Union {
3264                 struct_type: self.struct_type,
3265                 generics: self.generics.clean(cx),
3266                 fields: self.fields.clean(cx),
3267                 fields_stripped: false,
3268             }),
3269         }
3270     }
3271 }
3272
3273 /// This is a more limited form of the standard Struct, different in that
3274 /// it lacks the things most items have (name, id, parameterization). Found
3275 /// only as a variant in an enum.
3276 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3277 pub struct VariantStruct {
3278     pub struct_type: doctree::StructType,
3279     pub fields: Vec<Item>,
3280     pub fields_stripped: bool,
3281 }
3282
3283 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
3284     fn clean(&self, cx: &DocContext<'_>) -> VariantStruct {
3285         VariantStruct {
3286             struct_type: doctree::struct_type_from_def(self),
3287             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
3288             fields_stripped: false,
3289         }
3290     }
3291 }
3292
3293 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3294 pub struct Enum {
3295     pub variants: IndexVec<VariantIdx, Item>,
3296     pub generics: Generics,
3297     pub variants_stripped: bool,
3298 }
3299
3300 impl Clean<Item> for doctree::Enum {
3301     fn clean(&self, cx: &DocContext<'_>) -> Item {
3302         Item {
3303             name: Some(self.name.clean(cx)),
3304             attrs: self.attrs.clean(cx),
3305             source: self.whence.clean(cx),
3306             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3307             visibility: self.vis.clean(cx),
3308             stability: self.stab.clean(cx),
3309             deprecation: self.depr.clean(cx),
3310             inner: EnumItem(Enum {
3311                 variants: self.variants.iter().map(|v| v.clean(cx)).collect(),
3312                 generics: self.generics.clean(cx),
3313                 variants_stripped: false,
3314             }),
3315         }
3316     }
3317 }
3318
3319 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3320 pub struct Variant {
3321     pub kind: VariantKind,
3322 }
3323
3324 impl Clean<Item> for doctree::Variant {
3325     fn clean(&self, cx: &DocContext<'_>) -> Item {
3326         Item {
3327             name: Some(self.name.clean(cx)),
3328             attrs: self.attrs.clean(cx),
3329             source: self.whence.clean(cx),
3330             visibility: None,
3331             stability: self.stab.clean(cx),
3332             deprecation: self.depr.clean(cx),
3333             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3334             inner: VariantItem(Variant {
3335                 kind: self.def.clean(cx),
3336             }),
3337         }
3338     }
3339 }
3340
3341 impl<'tcx> Clean<Item> for ty::VariantDef {
3342     fn clean(&self, cx: &DocContext<'_>) -> Item {
3343         let kind = match self.ctor_kind {
3344             CtorKind::Const => VariantKind::CLike,
3345             CtorKind::Fn => {
3346                 VariantKind::Tuple(
3347                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
3348                 )
3349             }
3350             CtorKind::Fictive => {
3351                 VariantKind::Struct(VariantStruct {
3352                     struct_type: doctree::Plain,
3353                     fields_stripped: false,
3354                     fields: self.fields.iter().map(|field| {
3355                         Item {
3356                             source: cx.tcx.def_span(field.did).clean(cx),
3357                             name: Some(field.ident.name.clean(cx)),
3358                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
3359                             visibility: field.vis.clean(cx),
3360                             def_id: field.did,
3361                             stability: get_stability(cx, field.did),
3362                             deprecation: get_deprecation(cx, field.did),
3363                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
3364                         }
3365                     }).collect()
3366                 })
3367             }
3368         };
3369         Item {
3370             name: Some(self.ident.clean(cx)),
3371             attrs: inline::load_attrs(cx, self.def_id),
3372             source: cx.tcx.def_span(self.def_id).clean(cx),
3373             visibility: Some(Inherited),
3374             def_id: self.def_id,
3375             inner: VariantItem(Variant { kind }),
3376             stability: get_stability(cx, self.def_id),
3377             deprecation: get_deprecation(cx, self.def_id),
3378         }
3379     }
3380 }
3381
3382 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3383 pub enum VariantKind {
3384     CLike,
3385     Tuple(Vec<Type>),
3386     Struct(VariantStruct),
3387 }
3388
3389 impl Clean<VariantKind> for hir::VariantData {
3390     fn clean(&self, cx: &DocContext<'_>) -> VariantKind {
3391         match self {
3392             hir::VariantData::Struct(..) => VariantKind::Struct(self.clean(cx)),
3393             hir::VariantData::Tuple(..) =>
3394                 VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect()),
3395             hir::VariantData::Unit(..) => VariantKind::CLike,
3396         }
3397     }
3398 }
3399
3400 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3401 pub struct Span {
3402     pub filename: FileName,
3403     pub loline: usize,
3404     pub locol: usize,
3405     pub hiline: usize,
3406     pub hicol: usize,
3407     pub original: syntax_pos::Span,
3408 }
3409
3410 impl Span {
3411     pub fn empty() -> Span {
3412         Span {
3413             filename: FileName::Anon(0),
3414             loline: 0, locol: 0,
3415             hiline: 0, hicol: 0,
3416             original: syntax_pos::DUMMY_SP,
3417         }
3418     }
3419
3420     pub fn span(&self) -> syntax_pos::Span {
3421         self.original
3422     }
3423 }
3424
3425 impl Clean<Span> for syntax_pos::Span {
3426     fn clean(&self, cx: &DocContext<'_>) -> Span {
3427         if self.is_dummy() {
3428             return Span::empty();
3429         }
3430
3431         let cm = cx.sess().source_map();
3432         let filename = cm.span_to_filename(*self);
3433         let lo = cm.lookup_char_pos(self.lo());
3434         let hi = cm.lookup_char_pos(self.hi());
3435         Span {
3436             filename,
3437             loline: lo.line,
3438             locol: lo.col.to_usize(),
3439             hiline: hi.line,
3440             hicol: hi.col.to_usize(),
3441             original: *self,
3442         }
3443     }
3444 }
3445
3446 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3447 pub struct Path {
3448     pub global: bool,
3449     pub res: Res,
3450     pub segments: Vec<PathSegment>,
3451 }
3452
3453 impl Path {
3454     pub fn last_name(&self) -> &str {
3455         self.segments.last().expect("segments were empty").name.as_str()
3456     }
3457 }
3458
3459 impl Clean<Path> for hir::Path {
3460     fn clean(&self, cx: &DocContext<'_>) -> Path {
3461         Path {
3462             global: self.is_global(),
3463             res: self.res,
3464             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
3465         }
3466     }
3467 }
3468
3469 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3470 pub enum GenericArg {
3471     Lifetime(Lifetime),
3472     Type(Type),
3473     Const(Constant),
3474 }
3475
3476 impl fmt::Display for GenericArg {
3477     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3478         match self {
3479             GenericArg::Lifetime(lt) => lt.fmt(f),
3480             GenericArg::Type(ty) => ty.fmt(f),
3481             GenericArg::Const(ct) => ct.fmt(f),
3482         }
3483     }
3484 }
3485
3486 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3487 pub enum GenericArgs {
3488     AngleBracketed {
3489         args: Vec<GenericArg>,
3490         bindings: Vec<TypeBinding>,
3491     },
3492     Parenthesized {
3493         inputs: Vec<Type>,
3494         output: Option<Type>,
3495     }
3496 }
3497
3498 impl Clean<GenericArgs> for hir::GenericArgs {
3499     fn clean(&self, cx: &DocContext<'_>) -> GenericArgs {
3500         if self.parenthesized {
3501             let output = self.bindings[0].ty.clean(cx);
3502             GenericArgs::Parenthesized {
3503                 inputs: self.inputs().clean(cx),
3504                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
3505             }
3506         } else {
3507             let elide_lifetimes = self.args.iter().all(|arg| match arg {
3508                 hir::GenericArg::Lifetime(lt) => lt.is_elided(),
3509                 _ => true,
3510             });
3511             GenericArgs::AngleBracketed {
3512                 args: self.args.iter().filter_map(|arg| match arg {
3513                     hir::GenericArg::Lifetime(lt) if !elide_lifetimes => {
3514                         Some(GenericArg::Lifetime(lt.clean(cx)))
3515                     }
3516                     hir::GenericArg::Lifetime(_) => None,
3517                     hir::GenericArg::Type(ty) => Some(GenericArg::Type(ty.clean(cx))),
3518                     hir::GenericArg::Const(ct) => Some(GenericArg::Const(ct.clean(cx))),
3519                 }).collect(),
3520                 bindings: self.bindings.clean(cx),
3521             }
3522         }
3523     }
3524 }
3525
3526 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3527 pub struct PathSegment {
3528     pub name: String,
3529     pub args: GenericArgs,
3530 }
3531
3532 impl Clean<PathSegment> for hir::PathSegment {
3533     fn clean(&self, cx: &DocContext<'_>) -> PathSegment {
3534         PathSegment {
3535             name: self.ident.name.clean(cx),
3536             args: self.with_generic_args(|generic_args| generic_args.clean(cx))
3537         }
3538     }
3539 }
3540
3541 fn strip_type(ty: Type) -> Type {
3542     match ty {
3543         Type::ResolvedPath { path, param_names, did, is_generic } => {
3544             Type::ResolvedPath { path: strip_path(&path), param_names, did, is_generic }
3545         }
3546         Type::Tuple(inner_tys) => {
3547             Type::Tuple(inner_tys.iter().map(|t| strip_type(t.clone())).collect())
3548         }
3549         Type::Slice(inner_ty) => Type::Slice(Box::new(strip_type(*inner_ty))),
3550         Type::Array(inner_ty, s) => Type::Array(Box::new(strip_type(*inner_ty)), s),
3551         Type::Unique(inner_ty) => Type::Unique(Box::new(strip_type(*inner_ty))),
3552         Type::RawPointer(m, inner_ty) => Type::RawPointer(m, Box::new(strip_type(*inner_ty))),
3553         Type::BorrowedRef { lifetime, mutability, type_ } => {
3554             Type::BorrowedRef { lifetime, mutability, type_: Box::new(strip_type(*type_)) }
3555         }
3556         Type::QPath { name, self_type, trait_ } => {
3557             Type::QPath {
3558                 name,
3559                 self_type: Box::new(strip_type(*self_type)), trait_: Box::new(strip_type(*trait_))
3560             }
3561         }
3562         _ => ty
3563     }
3564 }
3565
3566 fn strip_path(path: &Path) -> Path {
3567     let segments = path.segments.iter().map(|s| {
3568         PathSegment {
3569             name: s.name.clone(),
3570             args: GenericArgs::AngleBracketed {
3571                 args: vec![],
3572                 bindings: vec![],
3573             }
3574         }
3575     }).collect();
3576
3577     Path {
3578         global: path.global,
3579         res: path.res.clone(),
3580         segments,
3581     }
3582 }
3583
3584 fn qpath_to_string(p: &hir::QPath) -> String {
3585     let segments = match *p {
3586         hir::QPath::Resolved(_, ref path) => &path.segments,
3587         hir::QPath::TypeRelative(_, ref segment) => return segment.ident.to_string(),
3588     };
3589
3590     let mut s = String::new();
3591     for (i, seg) in segments.iter().enumerate() {
3592         if i > 0 {
3593             s.push_str("::");
3594         }
3595         if seg.ident.name != kw::PathRoot {
3596             s.push_str(&*seg.ident.as_str());
3597         }
3598     }
3599     s
3600 }
3601
3602 impl Clean<String> for Ident {
3603     #[inline]
3604     fn clean(&self, cx: &DocContext<'_>) -> String {
3605         self.name.clean(cx)
3606     }
3607 }
3608
3609 impl Clean<String> for ast::Name {
3610     #[inline]
3611     fn clean(&self, _: &DocContext<'_>) -> String {
3612         self.to_string()
3613     }
3614 }
3615
3616 impl Clean<String> for InternedString {
3617     #[inline]
3618     fn clean(&self, _: &DocContext<'_>) -> String {
3619         self.to_string()
3620     }
3621 }
3622
3623 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3624 pub struct Typedef {
3625     pub type_: Type,
3626     pub generics: Generics,
3627 }
3628
3629 impl Clean<Item> for doctree::Typedef {
3630     fn clean(&self, cx: &DocContext<'_>) -> Item {
3631         Item {
3632             name: Some(self.name.clean(cx)),
3633             attrs: self.attrs.clean(cx),
3634             source: self.whence.clean(cx),
3635             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3636             visibility: self.vis.clean(cx),
3637             stability: self.stab.clean(cx),
3638             deprecation: self.depr.clean(cx),
3639             inner: TypedefItem(Typedef {
3640                 type_: self.ty.clean(cx),
3641                 generics: self.gen.clean(cx),
3642             }, false),
3643         }
3644     }
3645 }
3646
3647 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3648 pub struct Existential {
3649     pub bounds: Vec<GenericBound>,
3650     pub generics: Generics,
3651 }
3652
3653 impl Clean<Item> for doctree::Existential {
3654     fn clean(&self, cx: &DocContext<'_>) -> Item {
3655         Item {
3656             name: Some(self.name.clean(cx)),
3657             attrs: self.attrs.clean(cx),
3658             source: self.whence.clean(cx),
3659             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3660             visibility: self.vis.clean(cx),
3661             stability: self.stab.clean(cx),
3662             deprecation: self.depr.clean(cx),
3663             inner: ExistentialItem(Existential {
3664                 bounds: self.exist_ty.bounds.clean(cx),
3665                 generics: self.exist_ty.generics.clean(cx),
3666             }, false),
3667         }
3668     }
3669 }
3670
3671 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3672 pub struct BareFunctionDecl {
3673     pub unsafety: hir::Unsafety,
3674     pub generic_params: Vec<GenericParamDef>,
3675     pub decl: FnDecl,
3676     pub abi: Abi,
3677 }
3678
3679 impl Clean<BareFunctionDecl> for hir::BareFnTy {
3680     fn clean(&self, cx: &DocContext<'_>) -> BareFunctionDecl {
3681         let (generic_params, decl) = enter_impl_trait(cx, || {
3682             (self.generic_params.clean(cx), (&*self.decl, &self.arg_names[..]).clean(cx))
3683         });
3684         BareFunctionDecl {
3685             unsafety: self.unsafety,
3686             abi: self.abi,
3687             decl,
3688             generic_params,
3689         }
3690     }
3691 }
3692
3693 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3694 pub struct Static {
3695     pub type_: Type,
3696     pub mutability: Mutability,
3697     /// It's useful to have the value of a static documented, but I have no
3698     /// desire to represent expressions (that'd basically be all of the AST,
3699     /// which is huge!). So, have a string.
3700     pub expr: String,
3701 }
3702
3703 impl Clean<Item> for doctree::Static {
3704     fn clean(&self, cx: &DocContext<'_>) -> Item {
3705         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
3706         Item {
3707             name: Some(self.name.clean(cx)),
3708             attrs: self.attrs.clean(cx),
3709             source: self.whence.clean(cx),
3710             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3711             visibility: self.vis.clean(cx),
3712             stability: self.stab.clean(cx),
3713             deprecation: self.depr.clean(cx),
3714             inner: StaticItem(Static {
3715                 type_: self.type_.clean(cx),
3716                 mutability: self.mutability.clean(cx),
3717                 expr: print_const_expr(cx, self.expr),
3718             }),
3719         }
3720     }
3721 }
3722
3723 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
3724 pub struct Constant {
3725     pub type_: Type,
3726     pub expr: String,
3727 }
3728
3729 impl Clean<Item> for doctree::Constant {
3730     fn clean(&self, cx: &DocContext<'_>) -> Item {
3731         Item {
3732             name: Some(self.name.clean(cx)),
3733             attrs: self.attrs.clean(cx),
3734             source: self.whence.clean(cx),
3735             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3736             visibility: self.vis.clean(cx),
3737             stability: self.stab.clean(cx),
3738             deprecation: self.depr.clean(cx),
3739             inner: ConstantItem(Constant {
3740                 type_: self.type_.clean(cx),
3741                 expr: print_const_expr(cx, self.expr),
3742             }),
3743         }
3744     }
3745 }
3746
3747 #[derive(Debug, Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Hash)]
3748 pub enum Mutability {
3749     Mutable,
3750     Immutable,
3751 }
3752
3753 impl Clean<Mutability> for hir::Mutability {
3754     fn clean(&self, _: &DocContext<'_>) -> Mutability {
3755         match self {
3756             &hir::MutMutable => Mutable,
3757             &hir::MutImmutable => Immutable,
3758         }
3759     }
3760 }
3761
3762 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Debug, Hash)]
3763 pub enum ImplPolarity {
3764     Positive,
3765     Negative,
3766 }
3767
3768 impl Clean<ImplPolarity> for hir::ImplPolarity {
3769     fn clean(&self, _: &DocContext<'_>) -> ImplPolarity {
3770         match self {
3771             &hir::ImplPolarity::Positive => ImplPolarity::Positive,
3772             &hir::ImplPolarity::Negative => ImplPolarity::Negative,
3773         }
3774     }
3775 }
3776
3777 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3778 pub struct Impl {
3779     pub unsafety: hir::Unsafety,
3780     pub generics: Generics,
3781     pub provided_trait_methods: FxHashSet<String>,
3782     pub trait_: Option<Type>,
3783     pub for_: Type,
3784     pub items: Vec<Item>,
3785     pub polarity: Option<ImplPolarity>,
3786     pub synthetic: bool,
3787     pub blanket_impl: Option<Type>,
3788 }
3789
3790 pub fn get_auto_trait_and_blanket_impls(
3791     cx: &DocContext<'tcx>,
3792     ty: Ty<'tcx>,
3793     param_env_def_id: DefId,
3794 ) -> impl Iterator<Item = Item> {
3795     AutoTraitFinder::new(cx).get_auto_trait_impls(ty, param_env_def_id).into_iter()
3796         .chain(BlanketImplFinder::new(cx).get_blanket_impls(ty, param_env_def_id))
3797 }
3798
3799 impl Clean<Vec<Item>> for doctree::Impl {
3800     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3801         let mut ret = Vec::new();
3802         let trait_ = self.trait_.clean(cx);
3803         let items = self.items.clean(cx);
3804
3805         // If this impl block is an implementation of the Deref trait, then we
3806         // need to try inlining the target's inherent impl blocks as well.
3807         if trait_.def_id() == cx.tcx.lang_items().deref_trait() {
3808             build_deref_target_impls(cx, &items, &mut ret);
3809         }
3810
3811         let provided = trait_.def_id().map(|did| {
3812             cx.tcx.provided_trait_methods(did)
3813                   .into_iter()
3814                   .map(|meth| meth.ident.to_string())
3815                   .collect()
3816         }).unwrap_or_default();
3817
3818         ret.push(Item {
3819             name: None,
3820             attrs: self.attrs.clean(cx),
3821             source: self.whence.clean(cx),
3822             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3823             visibility: self.vis.clean(cx),
3824             stability: self.stab.clean(cx),
3825             deprecation: self.depr.clean(cx),
3826             inner: ImplItem(Impl {
3827                 unsafety: self.unsafety,
3828                 generics: self.generics.clean(cx),
3829                 provided_trait_methods: provided,
3830                 trait_,
3831                 for_: self.for_.clean(cx),
3832                 items,
3833                 polarity: Some(self.polarity.clean(cx)),
3834                 synthetic: false,
3835                 blanket_impl: None,
3836             })
3837         });
3838         ret
3839     }
3840 }
3841
3842 fn build_deref_target_impls(cx: &DocContext<'_>,
3843                             items: &[Item],
3844                             ret: &mut Vec<Item>) {
3845     use self::PrimitiveType::*;
3846     let tcx = cx.tcx;
3847
3848     for item in items {
3849         let target = match item.inner {
3850             TypedefItem(ref t, true) => &t.type_,
3851             _ => continue,
3852         };
3853         let primitive = match *target {
3854             ResolvedPath { did, .. } if did.is_local() => continue,
3855             ResolvedPath { did, .. } => {
3856                 ret.extend(inline::build_impls(cx, did));
3857                 continue
3858             }
3859             _ => match target.primitive_type() {
3860                 Some(prim) => prim,
3861                 None => continue,
3862             }
3863         };
3864         let did = match primitive {
3865             Isize => tcx.lang_items().isize_impl(),
3866             I8 => tcx.lang_items().i8_impl(),
3867             I16 => tcx.lang_items().i16_impl(),
3868             I32 => tcx.lang_items().i32_impl(),
3869             I64 => tcx.lang_items().i64_impl(),
3870             I128 => tcx.lang_items().i128_impl(),
3871             Usize => tcx.lang_items().usize_impl(),
3872             U8 => tcx.lang_items().u8_impl(),
3873             U16 => tcx.lang_items().u16_impl(),
3874             U32 => tcx.lang_items().u32_impl(),
3875             U64 => tcx.lang_items().u64_impl(),
3876             U128 => tcx.lang_items().u128_impl(),
3877             F32 => tcx.lang_items().f32_impl(),
3878             F64 => tcx.lang_items().f64_impl(),
3879             Char => tcx.lang_items().char_impl(),
3880             Bool => None,
3881             Str => tcx.lang_items().str_impl(),
3882             Slice => tcx.lang_items().slice_impl(),
3883             Array => tcx.lang_items().slice_impl(),
3884             Tuple => None,
3885             Unit => None,
3886             RawPointer => tcx.lang_items().const_ptr_impl(),
3887             Reference => None,
3888             Fn => None,
3889             Never => None,
3890             CVarArgs => tcx.lang_items().va_list(),
3891         };
3892         if let Some(did) = did {
3893             if !did.is_local() {
3894                 inline::build_impl(cx, did, ret);
3895             }
3896         }
3897     }
3898 }
3899
3900 impl Clean<Vec<Item>> for doctree::ExternCrate {
3901     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3902
3903         let please_inline = self.vis.node.is_pub() && self.attrs.iter().any(|a| {
3904             a.check_name(sym::doc) && match a.meta_item_list() {
3905                 Some(l) => attr::list_contains_name(&l, sym::inline),
3906                 None => false,
3907             }
3908         });
3909
3910         if please_inline {
3911             let mut visited = FxHashSet::default();
3912
3913             let res = Res::Def(
3914                 DefKind::Mod,
3915                 DefId {
3916                     krate: self.cnum,
3917                     index: CRATE_DEF_INDEX,
3918                 },
3919             );
3920
3921             if let Some(items) = inline::try_inline(cx, res, self.name, &mut visited) {
3922                 return items;
3923             }
3924         }
3925
3926         vec![Item {
3927             name: None,
3928             attrs: self.attrs.clean(cx),
3929             source: self.whence.clean(cx),
3930             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
3931             visibility: self.vis.clean(cx),
3932             stability: None,
3933             deprecation: None,
3934             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
3935         }]
3936     }
3937 }
3938
3939 impl Clean<Vec<Item>> for doctree::Import {
3940     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3941         // We consider inlining the documentation of `pub use` statements, but we
3942         // forcefully don't inline if this is not public or if the
3943         // #[doc(no_inline)] attribute is present.
3944         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
3945         let mut denied = !self.vis.node.is_pub() || self.attrs.iter().any(|a| {
3946             a.check_name(sym::doc) && match a.meta_item_list() {
3947                 Some(l) => attr::list_contains_name(&l, sym::no_inline) ||
3948                            attr::list_contains_name(&l, sym::hidden),
3949                 None => false,
3950             }
3951         });
3952         // Also check whether imports were asked to be inlined, in case we're trying to re-export a
3953         // crate in Rust 2018+
3954         let please_inline = self.attrs.lists(sym::doc).has_word(sym::inline);
3955         let path = self.path.clean(cx);
3956         let inner = if self.glob {
3957             if !denied {
3958                 let mut visited = FxHashSet::default();
3959                 if let Some(items) = inline::try_inline_glob(cx, path.res, &mut visited) {
3960                     return items;
3961                 }
3962             }
3963
3964             Import::Glob(resolve_use_source(cx, path))
3965         } else {
3966             let name = self.name;
3967             if !please_inline {
3968                 match path.res {
3969                     Res::Def(DefKind::Mod, did) => {
3970                         if !did.is_local() && did.index == CRATE_DEF_INDEX {
3971                             // if we're `pub use`ing an extern crate root, don't inline it unless we
3972                             // were specifically asked for it
3973                             denied = true;
3974                         }
3975                     }
3976                     _ => {}
3977                 }
3978             }
3979             if !denied {
3980                 let mut visited = FxHashSet::default();
3981                 if let Some(items) = inline::try_inline(cx, path.res, name, &mut visited) {
3982                     return items;
3983                 }
3984             }
3985             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
3986         };
3987
3988         vec![Item {
3989             name: None,
3990             attrs: self.attrs.clean(cx),
3991             source: self.whence.clean(cx),
3992             def_id: cx.tcx.hir().local_def_id(ast::CRATE_NODE_ID),
3993             visibility: self.vis.clean(cx),
3994             stability: None,
3995             deprecation: None,
3996             inner: ImportItem(inner)
3997         }]
3998     }
3999 }
4000
4001 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4002 pub enum Import {
4003     // use source as str;
4004     Simple(String, ImportSource),
4005     // use source::*;
4006     Glob(ImportSource)
4007 }
4008
4009 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4010 pub struct ImportSource {
4011     pub path: Path,
4012     pub did: Option<DefId>,
4013 }
4014
4015 impl Clean<Vec<Item>> for hir::ForeignMod {
4016     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
4017         let mut items = self.items.clean(cx);
4018         for item in &mut items {
4019             if let ForeignFunctionItem(ref mut f) = item.inner {
4020                 f.header.abi = self.abi;
4021             }
4022         }
4023         items
4024     }
4025 }
4026
4027 impl Clean<Item> for hir::ForeignItem {
4028     fn clean(&self, cx: &DocContext<'_>) -> Item {
4029         let inner = match self.node {
4030             hir::ForeignItemKind::Fn(ref decl, ref names, ref generics) => {
4031                 let (generics, decl) = enter_impl_trait(cx, || {
4032                     (generics.clean(cx), (&**decl, &names[..]).clean(cx))
4033                 });
4034                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
4035                 ForeignFunctionItem(Function {
4036                     decl,
4037                     generics,
4038                     header: hir::FnHeader {
4039                         unsafety: hir::Unsafety::Unsafe,
4040                         abi: Abi::Rust,
4041                         constness: hir::Constness::NotConst,
4042                         asyncness: hir::IsAsync::NotAsync,
4043                     },
4044                     all_types,
4045                     ret_types,
4046                 })
4047             }
4048             hir::ForeignItemKind::Static(ref ty, mutbl) => {
4049                 ForeignStaticItem(Static {
4050                     type_: ty.clean(cx),
4051                     mutability: mutbl.clean(cx),
4052                     expr: String::new(),
4053                 })
4054             }
4055             hir::ForeignItemKind::Type => {
4056                 ForeignTypeItem
4057             }
4058         };
4059
4060         let local_did = cx.tcx.hir().local_def_id_from_hir_id(self.hir_id);
4061
4062         Item {
4063             name: Some(self.ident.clean(cx)),
4064             attrs: self.attrs.clean(cx),
4065             source: self.span.clean(cx),
4066             def_id: local_did,
4067             visibility: self.vis.clean(cx),
4068             stability: get_stability(cx, local_did),
4069             deprecation: get_deprecation(cx, local_did),
4070             inner,
4071         }
4072     }
4073 }
4074
4075 // Utilities
4076
4077 pub trait ToSource {
4078     fn to_src(&self, cx: &DocContext<'_>) -> String;
4079 }
4080
4081 impl ToSource for syntax_pos::Span {
4082     fn to_src(&self, cx: &DocContext<'_>) -> String {
4083         debug!("converting span {:?} to snippet", self.clean(cx));
4084         let sn = match cx.sess().source_map().span_to_snippet(*self) {
4085             Ok(x) => x,
4086             Err(_) => String::new()
4087         };
4088         debug!("got snippet {}", sn);
4089         sn
4090     }
4091 }
4092
4093 fn name_from_pat(p: &hir::Pat) -> String {
4094     use rustc::hir::*;
4095     debug!("Trying to get a name from pattern: {:?}", p);
4096
4097     match p.node {
4098         PatKind::Wild => "_".to_string(),
4099         PatKind::Binding(_, _, ident, _) => ident.to_string(),
4100         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
4101         PatKind::Struct(ref name, ref fields, etc) => {
4102             format!("{} {{ {}{} }}", qpath_to_string(name),
4103                 fields.iter().map(|&Spanned { node: ref fp, .. }|
4104                                   format!("{}: {}", fp.ident, name_from_pat(&*fp.pat)))
4105                              .collect::<Vec<String>>().join(", "),
4106                 if etc { ", .." } else { "" }
4107             )
4108         }
4109         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
4110                                             .collect::<Vec<String>>().join(", ")),
4111         PatKind::Box(ref p) => name_from_pat(&**p),
4112         PatKind::Ref(ref p, _) => name_from_pat(&**p),
4113         PatKind::Lit(..) => {
4114             warn!("tried to get argument name from PatKind::Lit, \
4115                   which is silly in function arguments");
4116             "()".to_string()
4117         },
4118         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
4119                               which is not allowed in function arguments"),
4120         PatKind::Slice(ref begin, ref mid, ref end) => {
4121             let begin = begin.iter().map(|p| name_from_pat(&**p));
4122             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
4123             let end = end.iter().map(|p| name_from_pat(&**p));
4124             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
4125         },
4126     }
4127 }
4128
4129 fn print_const(cx: &DocContext<'_>, n: &ty::Const<'_>) -> String {
4130     match n.val {
4131         ConstValue::Unevaluated(def_id, _) => {
4132             if let Some(hir_id) = cx.tcx.hir().as_local_hir_id(def_id) {
4133                 print_const_expr(cx, cx.tcx.hir().body_owned_by(hir_id))
4134             } else {
4135                 inline::print_inlined_const(cx, def_id)
4136             }
4137         },
4138         _ => {
4139             let mut s = n.to_string();
4140             // array lengths are obviously usize
4141             if s.ends_with("usize") {
4142                 let n = s.len() - "usize".len();
4143                 s.truncate(n);
4144                 if s.ends_with(": ") {
4145                     let n = s.len() - ": ".len();
4146                     s.truncate(n);
4147                 }
4148             }
4149             s
4150         },
4151     }
4152 }
4153
4154 fn print_const_expr(cx: &DocContext<'_>, body: hir::BodyId) -> String {
4155     cx.tcx.hir().hir_to_pretty_string(body.hir_id)
4156 }
4157
4158 /// Given a type Path, resolve it to a Type using the TyCtxt
4159 fn resolve_type(cx: &DocContext<'_>,
4160                 path: Path,
4161                 id: hir::HirId) -> Type {
4162     if id == hir::DUMMY_HIR_ID {
4163         debug!("resolve_type({:?})", path);
4164     } else {
4165         debug!("resolve_type({:?},{:?})", path, id);
4166     }
4167
4168     let is_generic = match path.res {
4169         Res::PrimTy(p) => match p {
4170             hir::Str => return Primitive(PrimitiveType::Str),
4171             hir::Bool => return Primitive(PrimitiveType::Bool),
4172             hir::Char => return Primitive(PrimitiveType::Char),
4173             hir::Int(int_ty) => return Primitive(int_ty.into()),
4174             hir::Uint(uint_ty) => return Primitive(uint_ty.into()),
4175             hir::Float(float_ty) => return Primitive(float_ty.into()),
4176         },
4177         Res::SelfTy(..) if path.segments.len() == 1 => {
4178             return Generic(kw::SelfUpper.to_string());
4179         }
4180         Res::Def(DefKind::TyParam, _) if path.segments.len() == 1 => {
4181             return Generic(format!("{:#}", path));
4182         }
4183         Res::SelfTy(..)
4184         | Res::Def(DefKind::TyParam, _)
4185         | Res::Def(DefKind::AssocTy, _) => true,
4186         _ => false,
4187     };
4188     let did = register_res(&*cx, path.res);
4189     ResolvedPath { path: path, param_names: None, did: did, is_generic: is_generic }
4190 }
4191
4192 pub fn register_res(cx: &DocContext<'_>, res: Res) -> DefId {
4193     debug!("register_res({:?})", res);
4194
4195     let (did, kind) = match res {
4196         Res::Def(DefKind::Fn, i) => (i, TypeKind::Function),
4197         Res::Def(DefKind::TyAlias, i) => (i, TypeKind::Typedef),
4198         Res::Def(DefKind::Enum, i) => (i, TypeKind::Enum),
4199         Res::Def(DefKind::Trait, i) => (i, TypeKind::Trait),
4200         Res::Def(DefKind::Struct, i) => (i, TypeKind::Struct),
4201         Res::Def(DefKind::Union, i) => (i, TypeKind::Union),
4202         Res::Def(DefKind::Mod, i) => (i, TypeKind::Module),
4203         Res::Def(DefKind::ForeignTy, i) => (i, TypeKind::Foreign),
4204         Res::Def(DefKind::Const, i) => (i, TypeKind::Const),
4205         Res::Def(DefKind::Static, i) => (i, TypeKind::Static),
4206         Res::Def(DefKind::Variant, i) => (cx.tcx.parent(i).expect("cannot get parent def id"),
4207                             TypeKind::Enum),
4208         Res::Def(DefKind::Macro(mac_kind), i) => match mac_kind {
4209             MacroKind::Bang => (i, TypeKind::Macro),
4210             MacroKind::Attr => (i, TypeKind::Attr),
4211             MacroKind::Derive => (i, TypeKind::Derive),
4212             MacroKind::ProcMacroStub => unreachable!(),
4213         },
4214         Res::Def(DefKind::TraitAlias, i) => (i, TypeKind::TraitAlias),
4215         Res::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
4216         Res::SelfTy(_, Some(impl_def_id)) => return impl_def_id,
4217         _ => return res.def_id()
4218     };
4219     if did.is_local() { return did }
4220     inline::record_extern_fqn(cx, did, kind);
4221     if let TypeKind::Trait = kind {
4222         inline::record_extern_trait(cx, did);
4223     }
4224     did
4225 }
4226
4227 fn resolve_use_source(cx: &DocContext<'_>, path: Path) -> ImportSource {
4228     ImportSource {
4229         did: if path.res.opt_def_id().is_none() {
4230             None
4231         } else {
4232             Some(register_res(cx, path.res))
4233         },
4234         path,
4235     }
4236 }
4237
4238 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4239 pub struct Macro {
4240     pub source: String,
4241     pub imported_from: Option<String>,
4242 }
4243
4244 impl Clean<Item> for doctree::Macro {
4245     fn clean(&self, cx: &DocContext<'_>) -> Item {
4246         let name = self.name.clean(cx);
4247         Item {
4248             name: Some(name.clone()),
4249             attrs: self.attrs.clean(cx),
4250             source: self.whence.clean(cx),
4251             visibility: Some(Public),
4252             stability: self.stab.clean(cx),
4253             deprecation: self.depr.clean(cx),
4254             def_id: self.def_id,
4255             inner: MacroItem(Macro {
4256                 source: format!("macro_rules! {} {{\n{}}}",
4257                                 name,
4258                                 self.matchers.iter().map(|span| {
4259                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
4260                                 }).collect::<String>()),
4261                 imported_from: self.imported_from.clean(cx),
4262             }),
4263         }
4264     }
4265 }
4266
4267 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4268 pub struct ProcMacro {
4269     pub kind: MacroKind,
4270     pub helpers: Vec<String>,
4271 }
4272
4273 impl Clean<Item> for doctree::ProcMacro {
4274     fn clean(&self, cx: &DocContext<'_>) -> Item {
4275         Item {
4276             name: Some(self.name.clean(cx)),
4277             attrs: self.attrs.clean(cx),
4278             source: self.whence.clean(cx),
4279             visibility: Some(Public),
4280             stability: self.stab.clean(cx),
4281             deprecation: self.depr.clean(cx),
4282             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
4283             inner: ProcMacroItem(ProcMacro {
4284                 kind: self.kind,
4285                 helpers: self.helpers.clean(cx),
4286             }),
4287         }
4288     }
4289 }
4290
4291 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4292 pub struct Stability {
4293     pub level: stability::StabilityLevel,
4294     pub feature: Option<String>,
4295     pub since: String,
4296     pub deprecation: Option<Deprecation>,
4297     pub unstable_reason: Option<String>,
4298     pub issue: Option<u32>,
4299 }
4300
4301 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4302 pub struct Deprecation {
4303     pub since: Option<String>,
4304     pub note: Option<String>,
4305 }
4306
4307 impl Clean<Stability> for attr::Stability {
4308     fn clean(&self, _: &DocContext<'_>) -> Stability {
4309         Stability {
4310             level: stability::StabilityLevel::from_attr_level(&self.level),
4311             feature: Some(self.feature.to_string()).filter(|f| !f.is_empty()),
4312             since: match self.level {
4313                 attr::Stable {ref since} => since.to_string(),
4314                 _ => String::new(),
4315             },
4316             deprecation: self.rustc_depr.as_ref().map(|d| {
4317                 Deprecation {
4318                     note: Some(d.reason.to_string()).filter(|r| !r.is_empty()),
4319                     since: Some(d.since.to_string()).filter(|d| !d.is_empty()),
4320                 }
4321             }),
4322             unstable_reason: match self.level {
4323                 attr::Unstable { reason: Some(ref reason), .. } => Some(reason.to_string()),
4324                 _ => None,
4325             },
4326             issue: match self.level {
4327                 attr::Unstable {issue, ..} => Some(issue),
4328                 _ => None,
4329             }
4330         }
4331     }
4332 }
4333
4334 impl<'a> Clean<Stability> for &'a attr::Stability {
4335     fn clean(&self, dc: &DocContext<'_>) -> Stability {
4336         (**self).clean(dc)
4337     }
4338 }
4339
4340 impl Clean<Deprecation> for attr::Deprecation {
4341     fn clean(&self, _: &DocContext<'_>) -> Deprecation {
4342         Deprecation {
4343             since: self.since.map(|s| s.to_string()).filter(|s| !s.is_empty()),
4344             note: self.note.map(|n| n.to_string()).filter(|n| !n.is_empty()),
4345         }
4346     }
4347 }
4348
4349 /// An equality constraint on an associated type, e.g., `A = Bar` in `Foo<A = Bar>`
4350 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug, Hash)]
4351 pub struct TypeBinding {
4352     pub name: String,
4353     pub ty: Type
4354 }
4355
4356 impl Clean<TypeBinding> for hir::TypeBinding {
4357     fn clean(&self, cx: &DocContext<'_>) -> TypeBinding {
4358         TypeBinding {
4359             name: self.ident.name.clean(cx),
4360             ty: self.ty.clean(cx)
4361         }
4362     }
4363 }
4364
4365 pub fn def_id_to_path(
4366     cx: &DocContext<'_>,
4367     did: DefId,
4368     name: Option<String>
4369 ) -> Vec<String> {
4370     let crate_name = name.unwrap_or_else(|| cx.tcx.crate_name(did.krate).to_string());
4371     let relative = cx.tcx.def_path(did).data.into_iter().filter_map(|elem| {
4372         // extern blocks have an empty name
4373         let s = elem.data.to_string();
4374         if !s.is_empty() {
4375             Some(s)
4376         } else {
4377             None
4378         }
4379     });
4380     once(crate_name).chain(relative).collect()
4381 }
4382
4383 pub fn enter_impl_trait<F, R>(cx: &DocContext<'_>, f: F) -> R
4384 where
4385     F: FnOnce() -> R,
4386 {
4387     let old_bounds = mem::replace(&mut *cx.impl_trait_bounds.borrow_mut(), Default::default());
4388     let r = f();
4389     assert!(cx.impl_trait_bounds.borrow().is_empty());
4390     *cx.impl_trait_bounds.borrow_mut() = old_bounds;
4391     r
4392 }
4393
4394 // Start of code copied from rust-clippy
4395
4396 pub fn path_to_def_local(tcx: TyCtxt<'_, '_, '_>, path: &[Symbol]) -> Option<DefId> {
4397     let krate = tcx.hir().krate();
4398     let mut items = krate.module.item_ids.clone();
4399     let mut path_it = path.iter().peekable();
4400
4401     loop {
4402         let segment = path_it.next()?;
4403
4404         for item_id in mem::replace(&mut items, HirVec::new()).iter() {
4405             let item = tcx.hir().expect_item_by_hir_id(item_id.id);
4406             if item.ident.name == *segment {
4407                 if path_it.peek().is_none() {
4408                     return Some(tcx.hir().local_def_id_from_hir_id(item_id.id))
4409                 }
4410
4411                 items = match &item.node {
4412                     &hir::ItemKind::Mod(ref m) => m.item_ids.clone(),
4413                     _ => panic!("Unexpected item {:?} in path {:?} path")
4414                 };
4415                 break;
4416             }
4417         }
4418     }
4419 }
4420
4421 pub fn path_to_def(tcx: TyCtxt<'_, '_, '_>, path: &[Symbol]) -> Option<DefId> {
4422     let crates = tcx.crates();
4423
4424     let krate = crates
4425         .iter()
4426         .find(|&&krate| tcx.crate_name(krate) == path[0]);
4427
4428     if let Some(krate) = krate {
4429         let krate = DefId {
4430             krate: *krate,
4431             index: CRATE_DEF_INDEX,
4432         };
4433         let mut items = tcx.item_children(krate);
4434         let mut path_it = path.iter().skip(1).peekable();
4435
4436         loop {
4437             let segment = path_it.next()?;
4438
4439             for item in mem::replace(&mut items, &[]).iter() {
4440                 if item.ident.name == *segment {
4441                     if path_it.peek().is_none() {
4442                         return match item.res {
4443                             def::Res::Def(DefKind::Trait, did) => Some(did),
4444                             _ => None,
4445                         }
4446                     }
4447
4448                     items = tcx.item_children(item.res.def_id());
4449                     break;
4450                 }
4451             }
4452         }
4453     } else {
4454         None
4455     }
4456 }
4457
4458 // End of code copied from rust-clippy
4459
4460 #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
4461 enum RegionTarget<'tcx> {
4462     Region(Region<'tcx>),
4463     RegionVid(RegionVid)
4464 }
4465
4466 #[derive(Default, Debug, Clone)]
4467 struct RegionDeps<'tcx> {
4468     larger: FxHashSet<RegionTarget<'tcx>>,
4469     smaller: FxHashSet<RegionTarget<'tcx>>
4470 }
4471
4472 #[derive(Eq, PartialEq, Hash, Debug)]
4473 enum SimpleBound {
4474     TraitBound(Vec<PathSegment>, Vec<SimpleBound>, Vec<GenericParamDef>, hir::TraitBoundModifier),
4475     Outlives(Lifetime),
4476 }
4477
4478 impl From<GenericBound> for SimpleBound {
4479     fn from(bound: GenericBound) -> Self {
4480         match bound.clone() {
4481             GenericBound::Outlives(l) => SimpleBound::Outlives(l),
4482             GenericBound::TraitBound(t, mod_) => match t.trait_ {
4483                 Type::ResolvedPath { path, param_names, .. } => {
4484                     SimpleBound::TraitBound(path.segments,
4485                                             param_names
4486                                                 .map_or_else(|| Vec::new(), |v| v.iter()
4487                                                         .map(|p| SimpleBound::from(p.clone()))
4488                                                         .collect()),
4489                                             t.generic_params,
4490                                             mod_)
4491                 }
4492                 _ => panic!("Unexpected bound {:?}", bound),
4493             }
4494         }
4495     }
4496 }