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