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