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(Ident::from_str("target_feature"),
 933                                                             dummy_spanned(feat));
 934                     if let Ok(feat_cfg) = Cfg::parse(&meta) {
 935                         cfg &= feat_cfg;
 936                     }
 937                 }
 938             }
 939         }
 940
 941         let inner_docs = attrs.iter()
 942                               .filter(|a| a.check_name(sym::doc))
 943                               .next()
 944                               .map_or(true, |a| a.style == AttrStyle::Inner);
 945
 946         Attributes {
 947             doc_strings,
 948             other_attrs,
 949             cfg: if cfg == Cfg::True { None } else { Some(Arc::new(cfg)) },
 950             span: sp,
 951             links: vec![],
 952             inner_docs,
 953         }
 954     }
 955
 956     /// Finds the `doc` attribute as a NameValue and returns the corresponding
 957     /// value found.
 958     pub fn doc_value<'a>(&'a self) -> Option<&'a str> {
 959         self.doc_strings.first().map(|s| s.as_str())
 960     }
 961
 962     /// Finds all `doc` attributes as NameValues and returns their corresponding values, joined
 963     /// with newlines.
 964     pub fn collapsed_doc_value(&self) -> Option<String> {
 965         if !self.doc_strings.is_empty() {
 966             Some(self.doc_strings.iter().collect())
 967         } else {
 968             None
 969         }
 970     }
 971
 972     /// Gets links as a vector
 973     ///
 974     /// Cache must be populated before call
 975     pub fn links(&self, krate: &CrateNum) -> Vec<(String, String)> {
 976         use crate::html::format::href;
 977
 978         self.links.iter().filter_map(|&(ref s, did, ref fragment)| {
 979             match did {
 980                 Some(did) => {
 981                     if let Some((mut href, ..)) = href(did) {
 982                         if let Some(ref fragment) = *fragment {
 983                             href.push_str("#");
 984                             href.push_str(fragment);
 985                         }
 986                         Some((s.clone(), href))
 987                     } else {
 988                         None
 989                     }
 990                 }
 991                 None => {
 992                     if let Some(ref fragment) = *fragment {
 993                         let cache = cache();
 994                         let url = match cache.extern_locations.get(krate) {
 995                             Some(&(_, ref src, ExternalLocation::Local)) =>
 996                                 src.to_str().expect("invalid file path"),
 997                             Some(&(_, _, ExternalLocation::Remote(ref s))) => s,
 998                             Some(&(_, _, ExternalLocation::Unknown)) | None =>
 999                                 "https://doc.rust-lang.org/nightly",
1000                         };
1001                         // This is a primitive so the url is done "by hand".
1002                         let tail = fragment.find('#').unwrap_or_else(|| fragment.len());
1003                         Some((s.clone(),
1004                               format!("{}{}std/primitive.{}.html{}",
1005                                       url,
1006                                       if !url.ends_with('/') { "/" } else { "" },
1007                                       &fragment[..tail],
1008                                       &fragment[tail..])))
1009                     } else {
1010                         panic!("This isn't a primitive?!");
1011                     }
1012                 }
1013             }
1014         }).collect()
1015     }
1016 }
1017
1018 impl PartialEq for Attributes {
1019     fn eq(&self, rhs: &Self) -> bool {
1020         self.doc_strings == rhs.doc_strings &&
1021         self.cfg == rhs.cfg &&
1022         self.span == rhs.span &&
1023         self.links == rhs.links &&
1024         self.other_attrs.iter().map(|attr| attr.id).eq(rhs.other_attrs.iter().map(|attr| attr.id))
1025     }
1026 }
1027
1028 impl Eq for Attributes {}
1029
1030 impl Hash for Attributes {
1031     fn hash<H: Hasher>(&self, hasher: &mut H) {
1032         self.doc_strings.hash(hasher);
1033         self.cfg.hash(hasher);
1034         self.span.hash(hasher);
1035         self.links.hash(hasher);
1036         for attr in &self.other_attrs {
1037             attr.id.hash(hasher);
1038         }
1039     }
1040 }
1041
1042 impl AttributesExt for Attributes {
1043     fn lists<'a>(&'a self, name: Symbol) -> ListAttributesIter<'a> {
1044         self.other_attrs.lists(name)
1045     }
1046 }
1047
1048 impl Clean<Attributes> for [ast::Attribute] {
1049     fn clean(&self, cx: &DocContext<'_>) -> Attributes {
1050         Attributes::from_ast(cx.sess().diagnostic(), self)
1051     }
1052 }
1053
1054 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1055 pub enum GenericBound {
1056     TraitBound(PolyTrait, hir::TraitBoundModifier),
1057     Outlives(Lifetime),
1058 }
1059
1060 impl GenericBound {
1061     fn maybe_sized(cx: &DocContext<'_>) -> GenericBound {
1062         let did = cx.tcx.require_lang_item(lang_items::SizedTraitLangItem);
1063         let empty = cx.tcx.intern_substs(&[]);
1064         let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
1065             Some(did), false, vec![], empty);
1066         inline::record_extern_fqn(cx, did, TypeKind::Trait);
1067         GenericBound::TraitBound(PolyTrait {
1068             trait_: ResolvedPath {
1069                 path,
1070                 param_names: None,
1071                 did,
1072                 is_generic: false,
1073             },
1074             generic_params: Vec::new(),
1075         }, hir::TraitBoundModifier::Maybe)
1076     }
1077
1078     fn is_sized_bound(&self, cx: &DocContext<'_>) -> bool {
1079         use rustc::hir::TraitBoundModifier as TBM;
1080         if let GenericBound::TraitBound(PolyTrait { ref trait_, .. }, TBM::None) = *self {
1081             if trait_.def_id() == cx.tcx.lang_items().sized_trait() {
1082                 return true;
1083             }
1084         }
1085         false
1086     }
1087
1088     fn get_poly_trait(&self) -> Option<PolyTrait> {
1089         if let GenericBound::TraitBound(ref p, _) = *self {
1090             return Some(p.clone())
1091         }
1092         None
1093     }
1094
1095     fn get_trait_type(&self) -> Option<Type> {
1096         if let GenericBound::TraitBound(PolyTrait { ref trait_, .. }, _) = *self {
1097             Some(trait_.clone())
1098         } else {
1099             None
1100         }
1101     }
1102 }
1103
1104 impl Clean<GenericBound> for hir::GenericBound {
1105     fn clean(&self, cx: &DocContext<'_>) -> GenericBound {
1106         match *self {
1107             hir::GenericBound::Outlives(lt) => GenericBound::Outlives(lt.clean(cx)),
1108             hir::GenericBound::Trait(ref t, modifier) => {
1109                 GenericBound::TraitBound(t.clean(cx), modifier)
1110             }
1111         }
1112     }
1113 }
1114
1115 fn external_generic_args(
1116     cx: &DocContext<'_>,
1117     trait_did: Option<DefId>,
1118     has_self: bool,
1119     bindings: Vec<TypeBinding>,
1120     substs: SubstsRef<'_>,
1121 ) -> GenericArgs {
1122     let mut skip_self = has_self;
1123     let mut ty_sty = None;
1124     let args: Vec<_> = substs.iter().filter_map(|kind| match kind.unpack() {
1125         UnpackedKind::Lifetime(lt) => {
1126             lt.clean(cx).and_then(|lt| Some(GenericArg::Lifetime(lt)))
1127         }
1128         UnpackedKind::Type(_) if skip_self => {
1129             skip_self = false;
1130             None
1131         }
1132         UnpackedKind::Type(ty) => {
1133             ty_sty = Some(&ty.sty);
1134             Some(GenericArg::Type(ty.clean(cx)))
1135         }
1136         UnpackedKind::Const(ct) => Some(GenericArg::Const(ct.clean(cx))),
1137     }).collect();
1138
1139     match trait_did {
1140         // Attempt to sugar an external path like Fn<(A, B,), C> to Fn(A, B) -> C
1141         Some(did) if cx.tcx.lang_items().fn_trait_kind(did).is_some() => {
1142             assert!(ty_sty.is_some());
1143             let inputs = match ty_sty {
1144                 Some(ty::Tuple(ref tys)) => tys.iter().map(|t| t.expect_ty().clean(cx)).collect(),
1145                 _ => return GenericArgs::AngleBracketed { args, bindings },
1146             };
1147             let output = None;
1148             // FIXME(#20299) return type comes from a projection now
1149             // match types[1].sty {
1150             //     ty::Tuple(ref v) if v.is_empty() => None, // -> ()
1151             //     _ => Some(types[1].clean(cx))
1152             // };
1153             GenericArgs::Parenthesized { inputs, output }
1154         },
1155         _ => {
1156             GenericArgs::AngleBracketed { args, bindings }
1157         }
1158     }
1159 }
1160
1161 // trait_did should be set to a trait's DefId if called on a TraitRef, in order to sugar
1162 // from Fn<(A, B,), C> to Fn(A, B) -> C
1163 fn external_path(cx: &DocContext<'_>, name: &str, trait_did: Option<DefId>, has_self: bool,
1164                  bindings: Vec<TypeBinding>, substs: SubstsRef<'_>) -> Path {
1165     Path {
1166         global: false,
1167         res: Res::Err,
1168         segments: vec![PathSegment {
1169             name: name.to_string(),
1170             args: external_generic_args(cx, trait_did, has_self, bindings, substs)
1171         }],
1172     }
1173 }
1174
1175 impl<'a, 'tcx> Clean<GenericBound> for (&'a ty::TraitRef<'tcx>, Vec<TypeBinding>) {
1176     fn clean(&self, cx: &DocContext<'_>) -> GenericBound {
1177         let (trait_ref, ref bounds) = *self;
1178         inline::record_extern_fqn(cx, trait_ref.def_id, TypeKind::Trait);
1179         let path = external_path(cx, &cx.tcx.item_name(trait_ref.def_id).as_str(),
1180                                  Some(trait_ref.def_id), true, bounds.clone(), trait_ref.substs);
1181
1182         debug!("ty::TraitRef\n  subst: {:?}\n", trait_ref.substs);
1183
1184         // collect any late bound regions
1185         let mut late_bounds = vec![];
1186         for ty_s in trait_ref.input_types().skip(1) {
1187             if let ty::Tuple(ts) = ty_s.sty {
1188                 for &ty_s in ts {
1189                     if let ty::Ref(ref reg, _, _) = ty_s.expect_ty().sty {
1190                         if let &ty::RegionKind::ReLateBound(..) = *reg {
1191                             debug!("  hit an ReLateBound {:?}", reg);
1192                             if let Some(Lifetime(name)) = reg.clean(cx) {
1193                                 late_bounds.push(GenericParamDef {
1194                                     name,
1195                                     kind: GenericParamDefKind::Lifetime,
1196                                 });
1197                             }
1198                         }
1199                     }
1200                 }
1201             }
1202         }
1203
1204         GenericBound::TraitBound(
1205             PolyTrait {
1206                 trait_: ResolvedPath {
1207                     path,
1208                     param_names: None,
1209                     did: trait_ref.def_id,
1210                     is_generic: false,
1211                 },
1212                 generic_params: late_bounds,
1213             },
1214             hir::TraitBoundModifier::None
1215         )
1216     }
1217 }
1218
1219 impl<'tcx> Clean<GenericBound> for ty::TraitRef<'tcx> {
1220     fn clean(&self, cx: &DocContext<'_>) -> GenericBound {
1221         (self, vec![]).clean(cx)
1222     }
1223 }
1224
1225 impl<'tcx> Clean<Option<Vec<GenericBound>>> for InternalSubsts<'tcx> {
1226     fn clean(&self, cx: &DocContext<'_>) -> Option<Vec<GenericBound>> {
1227         let mut v = Vec::new();
1228         v.extend(self.regions().filter_map(|r| r.clean(cx)).map(GenericBound::Outlives));
1229         v.extend(self.types().map(|t| GenericBound::TraitBound(PolyTrait {
1230             trait_: t.clean(cx),
1231             generic_params: Vec::new(),
1232         }, hir::TraitBoundModifier::None)));
1233         if !v.is_empty() {Some(v)} else {None}
1234     }
1235 }
1236
1237 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1238 pub struct Lifetime(String);
1239
1240 impl Lifetime {
1241     pub fn get_ref<'a>(&'a self) -> &'a str {
1242         let Lifetime(ref s) = *self;
1243         let s: &'a str = s;
1244         s
1245     }
1246
1247     pub fn statik() -> Lifetime {
1248         Lifetime("'static".to_string())
1249     }
1250 }
1251
1252 impl Clean<Lifetime> for hir::Lifetime {
1253     fn clean(&self, cx: &DocContext<'_>) -> Lifetime {
1254         if self.hir_id != hir::DUMMY_HIR_ID {
1255             let def = cx.tcx.named_region(self.hir_id);
1256             match def {
1257                 Some(rl::Region::EarlyBound(_, node_id, _)) |
1258                 Some(rl::Region::LateBound(_, node_id, _)) |
1259                 Some(rl::Region::Free(_, node_id)) => {
1260                     if let Some(lt) = cx.lt_substs.borrow().get(&node_id).cloned() {
1261                         return lt;
1262                     }
1263                 }
1264                 _ => {}
1265             }
1266         }
1267         Lifetime(self.name.ident().to_string())
1268     }
1269 }
1270
1271 impl Clean<Lifetime> for hir::GenericParam {
1272     fn clean(&self, _: &DocContext<'_>) -> Lifetime {
1273         match self.kind {
1274             hir::GenericParamKind::Lifetime { .. } => {
1275                 if self.bounds.len() > 0 {
1276                     let mut bounds = self.bounds.iter().map(|bound| match bound {
1277                         hir::GenericBound::Outlives(lt) => lt,
1278                         _ => panic!(),
1279                     });
1280                     let name = bounds.next().expect("no more bounds").name.ident();
1281                     let mut s = format!("{}: {}", self.name.ident(), name);
1282                     for bound in bounds {
1283                         s.push_str(&format!(" + {}", bound.name.ident()));
1284                     }
1285                     Lifetime(s)
1286                 } else {
1287                     Lifetime(self.name.ident().to_string())
1288                 }
1289             }
1290             _ => panic!(),
1291         }
1292     }
1293 }
1294
1295 impl Clean<Constant> for hir::ConstArg {
1296     fn clean(&self, cx: &DocContext<'_>) -> Constant {
1297         Constant {
1298             type_: cx.tcx.type_of(cx.tcx.hir().body_owner_def_id(self.value.body)).clean(cx),
1299             expr: print_const_expr(cx, self.value.body),
1300         }
1301     }
1302 }
1303
1304 impl<'tcx> Clean<Lifetime> for ty::GenericParamDef {
1305     fn clean(&self, _cx: &DocContext<'_>) -> Lifetime {
1306         Lifetime(self.name.to_string())
1307     }
1308 }
1309
1310 impl Clean<Option<Lifetime>> for ty::RegionKind {
1311     fn clean(&self, cx: &DocContext<'_>) -> Option<Lifetime> {
1312         match *self {
1313             ty::ReStatic => Some(Lifetime::statik()),
1314             ty::ReLateBound(_, ty::BrNamed(_, name)) => Some(Lifetime(name.to_string())),
1315             ty::ReEarlyBound(ref data) => Some(Lifetime(data.name.clean(cx))),
1316
1317             ty::ReLateBound(..) |
1318             ty::ReFree(..) |
1319             ty::ReScope(..) |
1320             ty::ReVar(..) |
1321             ty::RePlaceholder(..) |
1322             ty::ReEmpty |
1323             ty::ReClosureBound(_) |
1324             ty::ReErased => {
1325                 debug!("Cannot clean region {:?}", self);
1326                 None
1327             }
1328         }
1329     }
1330 }
1331
1332 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1333 pub enum WherePredicate {
1334     BoundPredicate { ty: Type, bounds: Vec<GenericBound> },
1335     RegionPredicate { lifetime: Lifetime, bounds: Vec<GenericBound> },
1336     EqPredicate { lhs: Type, rhs: Type },
1337 }
1338
1339 impl WherePredicate {
1340     pub fn get_bounds(&self) -> Option<&[GenericBound]> {
1341         match *self {
1342             WherePredicate::BoundPredicate { ref bounds, .. } => Some(bounds),
1343             WherePredicate::RegionPredicate { ref bounds, .. } => Some(bounds),
1344             _ => None,
1345         }
1346     }
1347 }
1348
1349 impl Clean<WherePredicate> for hir::WherePredicate {
1350     fn clean(&self, cx: &DocContext<'_>) -> WherePredicate {
1351         match *self {
1352             hir::WherePredicate::BoundPredicate(ref wbp) => {
1353                 WherePredicate::BoundPredicate {
1354                     ty: wbp.bounded_ty.clean(cx),
1355                     bounds: wbp.bounds.clean(cx)
1356                 }
1357             }
1358
1359             hir::WherePredicate::RegionPredicate(ref wrp) => {
1360                 WherePredicate::RegionPredicate {
1361                     lifetime: wrp.lifetime.clean(cx),
1362                     bounds: wrp.bounds.clean(cx)
1363                 }
1364             }
1365
1366             hir::WherePredicate::EqPredicate(ref wrp) => {
1367                 WherePredicate::EqPredicate {
1368                     lhs: wrp.lhs_ty.clean(cx),
1369                     rhs: wrp.rhs_ty.clean(cx)
1370                 }
1371             }
1372         }
1373     }
1374 }
1375
1376 impl<'a> Clean<Option<WherePredicate>> for ty::Predicate<'a> {
1377     fn clean(&self, cx: &DocContext<'_>) -> Option<WherePredicate> {
1378         use rustc::ty::Predicate;
1379
1380         match *self {
1381             Predicate::Trait(ref pred) => Some(pred.clean(cx)),
1382             Predicate::Subtype(ref pred) => Some(pred.clean(cx)),
1383             Predicate::RegionOutlives(ref pred) => pred.clean(cx),
1384             Predicate::TypeOutlives(ref pred) => pred.clean(cx),
1385             Predicate::Projection(ref pred) => Some(pred.clean(cx)),
1386
1387             Predicate::WellFormed(..) |
1388             Predicate::ObjectSafe(..) |
1389             Predicate::ClosureKind(..) |
1390             Predicate::ConstEvaluatable(..) => panic!("not user writable"),
1391         }
1392     }
1393 }
1394
1395 impl<'a> Clean<WherePredicate> for ty::TraitPredicate<'a> {
1396     fn clean(&self, cx: &DocContext<'_>) -> WherePredicate {
1397         WherePredicate::BoundPredicate {
1398             ty: self.trait_ref.self_ty().clean(cx),
1399             bounds: vec![self.trait_ref.clean(cx)]
1400         }
1401     }
1402 }
1403
1404 impl<'tcx> Clean<WherePredicate> for ty::SubtypePredicate<'tcx> {
1405     fn clean(&self, _cx: &DocContext<'_>) -> WherePredicate {
1406         panic!("subtype predicates are an internal rustc artifact \
1407                 and should not be seen by rustdoc")
1408     }
1409 }
1410
1411 impl<'tcx> Clean<Option<WherePredicate>> for
1412     ty::OutlivesPredicate<ty::Region<'tcx>,ty::Region<'tcx>> {
1413
1414     fn clean(&self, cx: &DocContext<'_>) -> Option<WherePredicate> {
1415         let ty::OutlivesPredicate(ref a, ref b) = *self;
1416
1417         match (a, b) {
1418             (ty::ReEmpty, ty::ReEmpty) => {
1419                 return None;
1420             },
1421             _ => {}
1422         }
1423
1424         Some(WherePredicate::RegionPredicate {
1425             lifetime: a.clean(cx).expect("failed to clean lifetime"),
1426             bounds: vec![GenericBound::Outlives(b.clean(cx).expect("failed to clean bounds"))]
1427         })
1428     }
1429 }
1430
1431 impl<'tcx> Clean<Option<WherePredicate>> for ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>> {
1432     fn clean(&self, cx: &DocContext<'_>) -> Option<WherePredicate> {
1433         let ty::OutlivesPredicate(ref ty, ref lt) = *self;
1434
1435         match lt {
1436             ty::ReEmpty => return None,
1437             _ => {}
1438         }
1439
1440         Some(WherePredicate::BoundPredicate {
1441             ty: ty.clean(cx),
1442             bounds: vec![GenericBound::Outlives(lt.clean(cx).expect("failed to clean lifetimes"))]
1443         })
1444     }
1445 }
1446
1447 impl<'tcx> Clean<WherePredicate> for ty::ProjectionPredicate<'tcx> {
1448     fn clean(&self, cx: &DocContext<'_>) -> WherePredicate {
1449         WherePredicate::EqPredicate {
1450             lhs: self.projection_ty.clean(cx),
1451             rhs: self.ty.clean(cx)
1452         }
1453     }
1454 }
1455
1456 impl<'tcx> Clean<Type> for ty::ProjectionTy<'tcx> {
1457     fn clean(&self, cx: &DocContext<'_>) -> Type {
1458         let trait_ = match self.trait_ref(cx.tcx).clean(cx) {
1459             GenericBound::TraitBound(t, _) => t.trait_,
1460             GenericBound::Outlives(_) => panic!("cleaning a trait got a lifetime"),
1461         };
1462         Type::QPath {
1463             name: cx.tcx.associated_item(self.item_def_id).ident.name.clean(cx),
1464             self_type: box self.self_ty().clean(cx),
1465             trait_: box trait_
1466         }
1467     }
1468 }
1469
1470 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1471 pub enum GenericParamDefKind {
1472     Lifetime,
1473     Type {
1474         did: DefId,
1475         bounds: Vec<GenericBound>,
1476         default: Option<Type>,
1477         synthetic: Option<hir::SyntheticTyParamKind>,
1478     },
1479     Const {
1480         did: DefId,
1481         ty: Type,
1482     },
1483 }
1484
1485 impl GenericParamDefKind {
1486     pub fn is_type(&self) -> bool {
1487         match *self {
1488             GenericParamDefKind::Type { .. } => true,
1489             _ => false,
1490         }
1491     }
1492
1493     pub fn get_type(&self, cx: &DocContext<'_>) -> Option<Type> {
1494         match *self {
1495             GenericParamDefKind::Type { did, .. } => {
1496                 rustc_typeck::checked_type_of(cx.tcx, did, false).map(|t| t.clean(cx))
1497             }
1498             GenericParamDefKind::Const { ref ty, .. } => Some(ty.clone()),
1499             GenericParamDefKind::Lifetime => None,
1500         }
1501     }
1502 }
1503
1504 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1505 pub struct GenericParamDef {
1506     pub name: String,
1507
1508     pub kind: GenericParamDefKind,
1509 }
1510
1511 impl GenericParamDef {
1512     pub fn is_synthetic_type_param(&self) -> bool {
1513         match self.kind {
1514             GenericParamDefKind::Lifetime |
1515             GenericParamDefKind::Const { .. } => false,
1516             GenericParamDefKind::Type { ref synthetic, .. } => synthetic.is_some(),
1517         }
1518     }
1519
1520     pub fn is_type(&self) -> bool {
1521         self.kind.is_type()
1522     }
1523
1524     pub fn get_type(&self, cx: &DocContext<'_>) -> Option<Type> {
1525         self.kind.get_type(cx)
1526     }
1527
1528     pub fn get_bounds(&self) -> Option<&[GenericBound]> {
1529         match self.kind {
1530             GenericParamDefKind::Type { ref bounds, .. } => Some(bounds),
1531             _ => None,
1532         }
1533     }
1534 }
1535
1536 impl Clean<GenericParamDef> for ty::GenericParamDef {
1537     fn clean(&self, cx: &DocContext<'_>) -> GenericParamDef {
1538         let (name, kind) = match self.kind {
1539             ty::GenericParamDefKind::Lifetime => {
1540                 (self.name.to_string(), GenericParamDefKind::Lifetime)
1541             }
1542             ty::GenericParamDefKind::Type { has_default, .. } => {
1543                 cx.renderinfo.borrow_mut().external_param_names
1544                              .insert(self.def_id, self.name.clean(cx));
1545                 let default = if has_default {
1546                     Some(cx.tcx.type_of(self.def_id).clean(cx))
1547                 } else {
1548                     None
1549                 };
1550                 (self.name.clean(cx), GenericParamDefKind::Type {
1551                     did: self.def_id,
1552                     bounds: vec![], // These are filled in from the where-clauses.
1553                     default,
1554                     synthetic: None,
1555                 })
1556             }
1557             ty::GenericParamDefKind::Const { .. } => {
1558                 (self.name.clean(cx), GenericParamDefKind::Const {
1559                     did: self.def_id,
1560                     ty: cx.tcx.type_of(self.def_id).clean(cx),
1561                 })
1562             }
1563         };
1564
1565         GenericParamDef {
1566             name,
1567             kind,
1568         }
1569     }
1570 }
1571
1572 impl Clean<GenericParamDef> for hir::GenericParam {
1573     fn clean(&self, cx: &DocContext<'_>) -> GenericParamDef {
1574         let (name, kind) = match self.kind {
1575             hir::GenericParamKind::Lifetime { .. } => {
1576                 let name = if self.bounds.len() > 0 {
1577                     let mut bounds = self.bounds.iter().map(|bound| match bound {
1578                         hir::GenericBound::Outlives(lt) => lt,
1579                         _ => panic!(),
1580                     });
1581                     let name = bounds.next().expect("no more bounds").name.ident();
1582                     let mut s = format!("{}: {}", self.name.ident(), name);
1583                     for bound in bounds {
1584                         s.push_str(&format!(" + {}", bound.name.ident()));
1585                     }
1586                     s
1587                 } else {
1588                     self.name.ident().to_string()
1589                 };
1590                 (name, GenericParamDefKind::Lifetime)
1591             }
1592             hir::GenericParamKind::Type { ref default, synthetic } => {
1593                 (self.name.ident().name.clean(cx), GenericParamDefKind::Type {
1594                     did: cx.tcx.hir().local_def_id_from_hir_id(self.hir_id),
1595                     bounds: self.bounds.clean(cx),
1596                     default: default.clean(cx),
1597                     synthetic: synthetic,
1598                 })
1599             }
1600             hir::GenericParamKind::Const { ref ty } => {
1601                 (self.name.ident().name.clean(cx), GenericParamDefKind::Const {
1602                     did: cx.tcx.hir().local_def_id_from_hir_id(self.hir_id),
1603                     ty: ty.clean(cx),
1604                 })
1605             }
1606         };
1607
1608         GenericParamDef {
1609             name,
1610             kind,
1611         }
1612     }
1613 }
1614
1615 // maybe use a Generic enum and use Vec<Generic>?
1616 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Default, Hash)]
1617 pub struct Generics {
1618     pub params: Vec<GenericParamDef>,
1619     pub where_predicates: Vec<WherePredicate>,
1620 }
1621
1622 impl Clean<Generics> for hir::Generics {
1623     fn clean(&self, cx: &DocContext<'_>) -> Generics {
1624         // Synthetic type-parameters are inserted after normal ones.
1625         // In order for normal parameters to be able to refer to synthetic ones,
1626         // scans them first.
1627         fn is_impl_trait(param: &hir::GenericParam) -> bool {
1628             match param.kind {
1629                 hir::GenericParamKind::Type { synthetic, .. } => {
1630                     synthetic == Some(hir::SyntheticTyParamKind::ImplTrait)
1631                 }
1632                 _ => false,
1633             }
1634         }
1635         let impl_trait_params = self.params
1636             .iter()
1637             .filter(|param| is_impl_trait(param))
1638             .map(|param| {
1639                 let param: GenericParamDef = param.clean(cx);
1640                 match param.kind {
1641                     GenericParamDefKind::Lifetime => unreachable!(),
1642                     GenericParamDefKind::Type { did, ref bounds, .. } => {
1643                         cx.impl_trait_bounds.borrow_mut().insert(did, bounds.clone());
1644                     }
1645                     GenericParamDefKind::Const { .. } => unreachable!(),
1646                 }
1647                 param
1648             })
1649             .collect::<Vec<_>>();
1650
1651         let mut params = Vec::with_capacity(self.params.len());
1652         for p in self.params.iter().filter(|p| !is_impl_trait(p)) {
1653             let p = p.clean(cx);
1654             params.push(p);
1655         }
1656         params.extend(impl_trait_params);
1657
1658         let mut generics = Generics {
1659             params,
1660             where_predicates: self.where_clause.predicates.clean(cx),
1661         };
1662
1663         // Some duplicates are generated for ?Sized bounds between type params and where
1664         // predicates. The point in here is to move the bounds definitions from type params
1665         // to where predicates when such cases occur.
1666         for where_pred in &mut generics.where_predicates {
1667             match *where_pred {
1668                 WherePredicate::BoundPredicate { ty: Generic(ref name), ref mut bounds } => {
1669                     if bounds.is_empty() {
1670                         for param in &mut generics.params {
1671                             match param.kind {
1672                                 GenericParamDefKind::Lifetime => {}
1673                                 GenericParamDefKind::Type { bounds: ref mut ty_bounds, .. } => {
1674                                     if &param.name == name {
1675                                         mem::swap(bounds, ty_bounds);
1676                                         break
1677                                     }
1678                                 }
1679                                 GenericParamDefKind::Const { .. } => {}
1680                             }
1681                         }
1682                     }
1683                 }
1684                 _ => continue,
1685             }
1686         }
1687         generics
1688     }
1689 }
1690
1691 impl<'a, 'tcx> Clean<Generics> for (&'a ty::Generics,
1692                                     &'a Lrc<ty::GenericPredicates<'tcx>>) {
1693     fn clean(&self, cx: &DocContext<'_>) -> Generics {
1694         use self::WherePredicate as WP;
1695
1696         let (gens, preds) = *self;
1697
1698         // Bounds in the type_params and lifetimes fields are repeated in the
1699         // predicates field (see rustc_typeck::collect::ty_generics), so remove
1700         // them.
1701         let stripped_typarams = gens.params.iter().filter_map(|param| match param.kind {
1702             ty::GenericParamDefKind::Lifetime => None,
1703             ty::GenericParamDefKind::Type { .. } => {
1704                 if param.name == keywords::SelfUpper.name().as_str() {
1705                     assert_eq!(param.index, 0);
1706                     return None;
1707                 }
1708                 Some(param.clean(cx))
1709             }
1710             ty::GenericParamDefKind::Const { .. } => None,
1711         }).collect::<Vec<GenericParamDef>>();
1712
1713         let mut where_predicates = preds.predicates.iter()
1714             .flat_map(|(p, _)| p.clean(cx))
1715             .collect::<Vec<_>>();
1716
1717         // Type parameters and have a Sized bound by default unless removed with
1718         // ?Sized. Scan through the predicates and mark any type parameter with
1719         // a Sized bound, removing the bounds as we find them.
1720         //
1721         // Note that associated types also have a sized bound by default, but we
1722         // don't actually know the set of associated types right here so that's
1723         // handled in cleaning associated types
1724         let mut sized_params = FxHashSet::default();
1725         where_predicates.retain(|pred| {
1726             match *pred {
1727                 WP::BoundPredicate { ty: Generic(ref g), ref bounds } => {
1728                     if bounds.iter().any(|b| b.is_sized_bound(cx)) {
1729                         sized_params.insert(g.clone());
1730                         false
1731                     } else {
1732                         true
1733                     }
1734                 }
1735                 _ => true,
1736             }
1737         });
1738
1739         // Run through the type parameters again and insert a ?Sized
1740         // unbound for any we didn't find to be Sized.
1741         for tp in &stripped_typarams {
1742             if !sized_params.contains(&tp.name) {
1743                 where_predicates.push(WP::BoundPredicate {
1744                     ty: Type::Generic(tp.name.clone()),
1745                     bounds: vec![GenericBound::maybe_sized(cx)],
1746                 })
1747             }
1748         }
1749
1750         // It would be nice to collect all of the bounds on a type and recombine
1751         // them if possible, to avoid e.g., `where T: Foo, T: Bar, T: Sized, T: 'a`
1752         // and instead see `where T: Foo + Bar + Sized + 'a`
1753
1754         Generics {
1755             params: gens.params
1756                         .iter()
1757                         .flat_map(|param| match param.kind {
1758                             ty::GenericParamDefKind::Lifetime => Some(param.clean(cx)),
1759                             ty::GenericParamDefKind::Type { .. } => None,
1760                             ty::GenericParamDefKind::Const { .. } => Some(param.clean(cx)),
1761                         }).chain(simplify::ty_params(stripped_typarams).into_iter())
1762                         .collect(),
1763             where_predicates: simplify::where_clauses(cx, where_predicates),
1764         }
1765     }
1766 }
1767
1768 /// The point of this function is to replace bounds with types.
1769 ///
1770 /// i.e. `[T, U]` when you have the following bounds: `T: Display, U: Option<T>` will return
1771 /// `[Display, Option]` (we just returns the list of the types, we don't care about the
1772 /// wrapped types in here).
1773 fn get_real_types(
1774     generics: &Generics,
1775     arg: &Type,
1776     cx: &DocContext<'_>,
1777     recurse: i32,
1778 ) -> FxHashSet<Type> {
1779     let arg_s = arg.to_string();
1780     let mut res = FxHashSet::default();
1781     if recurse >= 10 { // FIXME: remove this whole recurse thing when the recursion bug is fixed
1782         return res;
1783     }
1784     if arg.is_full_generic() {
1785         if let Some(where_pred) = generics.where_predicates.iter().find(|g| {
1786             match g {
1787                 &WherePredicate::BoundPredicate { ref ty, .. } => ty.def_id() == arg.def_id(),
1788                 _ => false,
1789             }
1790         }) {
1791             let bounds = where_pred.get_bounds().unwrap_or_else(|| &[]);
1792             for bound in bounds.iter() {
1793                 match *bound {
1794                     GenericBound::TraitBound(ref poly_trait, _) => {
1795                         for x in poly_trait.generic_params.iter() {
1796                             if !x.is_type() {
1797                                 continue
1798                             }
1799                             if let Some(ty) = x.get_type(cx) {
1800                                 let adds = get_real_types(generics, &ty, cx, recurse + 1);
1801                                 if !adds.is_empty() {
1802                                     res.extend(adds);
1803                                 } else if !ty.is_full_generic() {
1804                                     res.insert(ty);
1805                                 }
1806                             }
1807                         }
1808                     }
1809                     _ => {}
1810                 }
1811             }
1812         }
1813         if let Some(bound) = generics.params.iter().find(|g| {
1814             g.is_type() && g.name == arg_s
1815         }) {
1816             for bound in bound.get_bounds().unwrap_or_else(|| &[]) {
1817                 if let Some(ty) = bound.get_trait_type() {
1818                     let adds = get_real_types(generics, &ty, cx, recurse + 1);
1819                     if !adds.is_empty() {
1820                         res.extend(adds);
1821                     } else if !ty.is_full_generic() {
1822                         res.insert(ty.clone());
1823                     }
1824                 }
1825             }
1826         }
1827     } else {
1828         res.insert(arg.clone());
1829         if let Some(gens) = arg.generics() {
1830             for gen in gens.iter() {
1831                 if gen.is_full_generic() {
1832                     let adds = get_real_types(generics, gen, cx, recurse + 1);
1833                     if !adds.is_empty() {
1834                         res.extend(adds);
1835                     }
1836                 } else {
1837                     res.insert(gen.clone());
1838                 }
1839             }
1840         }
1841     }
1842     res
1843 }
1844
1845 /// Return the full list of types when bounds have been resolved.
1846 ///
1847 /// i.e. `fn foo<A: Display, B: Option<A>>(x: u32, y: B)` will return
1848 /// `[u32, Display, Option]`.
1849 pub fn get_all_types(
1850     generics: &Generics,
1851     decl: &FnDecl,
1852     cx: &DocContext<'_>,
1853 ) -> (Vec<Type>, Vec<Type>) {
1854     let mut all_types = FxHashSet::default();
1855     for arg in decl.inputs.values.iter() {
1856         if arg.type_.is_self_type() {
1857             continue;
1858         }
1859         let args = get_real_types(generics, &arg.type_, cx, 0);
1860         if !args.is_empty() {
1861             all_types.extend(args);
1862         } else {
1863             all_types.insert(arg.type_.clone());
1864         }
1865     }
1866
1867     let ret_types = match decl.output {
1868         FunctionRetTy::Return(ref return_type) => {
1869             let mut ret = get_real_types(generics, &return_type, cx, 0);
1870             if ret.is_empty() {
1871                 ret.insert(return_type.clone());
1872             }
1873             ret.into_iter().collect()
1874         }
1875         _ => Vec::new(),
1876     };
1877     (all_types.into_iter().collect(), ret_types)
1878 }
1879
1880 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1881 pub struct Method {
1882     pub generics: Generics,
1883     pub decl: FnDecl,
1884     pub header: hir::FnHeader,
1885     pub defaultness: Option<hir::Defaultness>,
1886     pub all_types: Vec<Type>,
1887     pub ret_types: Vec<Type>,
1888 }
1889
1890 impl<'a> Clean<Method> for (&'a hir::MethodSig, &'a hir::Generics, hir::BodyId,
1891                             Option<hir::Defaultness>) {
1892     fn clean(&self, cx: &DocContext<'_>) -> Method {
1893         let (generics, decl) = enter_impl_trait(cx, || {
1894             (self.1.clean(cx), (&*self.0.decl, self.2).clean(cx))
1895         });
1896         let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
1897         Method {
1898             decl,
1899             generics,
1900             header: self.0.header,
1901             defaultness: self.3,
1902             all_types,
1903             ret_types,
1904         }
1905     }
1906 }
1907
1908 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1909 pub struct TyMethod {
1910     pub header: hir::FnHeader,
1911     pub decl: FnDecl,
1912     pub generics: Generics,
1913     pub all_types: Vec<Type>,
1914     pub ret_types: Vec<Type>,
1915 }
1916
1917 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1918 pub struct Function {
1919     pub decl: FnDecl,
1920     pub generics: Generics,
1921     pub header: hir::FnHeader,
1922     pub all_types: Vec<Type>,
1923     pub ret_types: Vec<Type>,
1924 }
1925
1926 impl Clean<Item> for doctree::Function {
1927     fn clean(&self, cx: &DocContext<'_>) -> Item {
1928         let (generics, decl) = enter_impl_trait(cx, || {
1929             (self.generics.clean(cx), (&self.decl, self.body).clean(cx))
1930         });
1931
1932         let did = cx.tcx.hir().local_def_id_from_hir_id(self.id);
1933         let constness = if cx.tcx.is_min_const_fn(did) {
1934             hir::Constness::Const
1935         } else {
1936             hir::Constness::NotConst
1937         };
1938         let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
1939         Item {
1940             name: Some(self.name.clean(cx)),
1941             attrs: self.attrs.clean(cx),
1942             source: self.whence.clean(cx),
1943             visibility: self.vis.clean(cx),
1944             stability: self.stab.clean(cx),
1945             deprecation: self.depr.clean(cx),
1946             def_id: did,
1947             inner: FunctionItem(Function {
1948                 decl,
1949                 generics,
1950                 header: hir::FnHeader { constness, ..self.header },
1951                 all_types,
1952                 ret_types,
1953             }),
1954         }
1955     }
1956 }
1957
1958 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1959 pub struct FnDecl {
1960     pub inputs: Arguments,
1961     pub output: FunctionRetTy,
1962     pub attrs: Attributes,
1963 }
1964
1965 impl FnDecl {
1966     pub fn self_type(&self) -> Option<SelfTy> {
1967         self.inputs.values.get(0).and_then(|v| v.to_self())
1968     }
1969
1970     /// Returns the sugared return type for an async function.
1971     ///
1972     /// For example, if the return type is `impl std::future::Future<Output = i32>`, this function
1973     /// will return `i32`.
1974     ///
1975     /// # Panics
1976     ///
1977     /// This function will panic if the return type does not match the expected sugaring for async
1978     /// functions.
1979     pub fn sugared_async_return_type(&self) -> FunctionRetTy {
1980         match &self.output {
1981             FunctionRetTy::Return(Type::ImplTrait(bounds)) => {
1982                 match &bounds[0] {
1983                     GenericBound::TraitBound(PolyTrait { trait_, .. }, ..) => {
1984                         let bindings = trait_.bindings().unwrap();
1985                         FunctionRetTy::Return(bindings[0].ty.clone())
1986                     }
1987                     _ => panic!("unexpected desugaring of async function"),
1988                 }
1989             }
1990             _ => panic!("unexpected desugaring of async function"),
1991         }
1992     }
1993 }
1994
1995 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1996 pub struct Arguments {
1997     pub values: Vec<Argument>,
1998 }
1999
2000 impl<'a> Clean<Arguments> for (&'a [hir::Ty], &'a [ast::Ident]) {
2001     fn clean(&self, cx: &DocContext<'_>) -> Arguments {
2002         Arguments {
2003             values: self.0.iter().enumerate().map(|(i, ty)| {
2004                 let mut name = self.1.get(i).map(|ident| ident.to_string())
2005                                             .unwrap_or(String::new());
2006                 if name.is_empty() {
2007                     name = "_".to_string();
2008                 }
2009                 Argument {
2010                     name,
2011                     type_: ty.clean(cx),
2012                 }
2013             }).collect()
2014         }
2015     }
2016 }
2017
2018 impl<'a> Clean<Arguments> for (&'a [hir::Ty], hir::BodyId) {
2019     fn clean(&self, cx: &DocContext<'_>) -> Arguments {
2020         let body = cx.tcx.hir().body(self.1);
2021
2022         Arguments {
2023             values: self.0.iter().enumerate().map(|(i, ty)| {
2024                 Argument {
2025                     name: name_from_pat(&body.arguments[i].original_pat()),
2026                     type_: ty.clean(cx),
2027                 }
2028             }).collect()
2029         }
2030     }
2031 }
2032
2033 impl<'a, A: Copy> Clean<FnDecl> for (&'a hir::FnDecl, A)
2034     where (&'a [hir::Ty], A): Clean<Arguments>
2035 {
2036     fn clean(&self, cx: &DocContext<'_>) -> FnDecl {
2037         FnDecl {
2038             inputs: (&self.0.inputs[..], self.1).clean(cx),
2039             output: self.0.output.clean(cx),
2040             attrs: Attributes::default(),
2041         }
2042     }
2043 }
2044
2045 impl<'a, 'tcx> Clean<FnDecl> for (DefId, ty::PolyFnSig<'tcx>) {
2046     fn clean(&self, cx: &DocContext<'_>) -> FnDecl {
2047         let (did, sig) = *self;
2048         let mut names = if cx.tcx.hir().as_local_hir_id(did).is_some() {
2049             vec![].into_iter()
2050         } else {
2051             cx.tcx.fn_arg_names(did).into_iter()
2052         };
2053
2054         FnDecl {
2055             output: Return(sig.skip_binder().output().clean(cx)),
2056             attrs: Attributes::default(),
2057             inputs: Arguments {
2058                 values: sig.skip_binder().inputs().iter().map(|t| {
2059                     Argument {
2060                         type_: t.clean(cx),
2061                         name: names.next().map_or(String::new(), |name| name.to_string()),
2062                     }
2063                 }).collect(),
2064             },
2065         }
2066     }
2067 }
2068
2069 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2070 pub struct Argument {
2071     pub type_: Type,
2072     pub name: String,
2073 }
2074
2075 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2076 pub enum SelfTy {
2077     SelfValue,
2078     SelfBorrowed(Option<Lifetime>, Mutability),
2079     SelfExplicit(Type),
2080 }
2081
2082 impl Argument {
2083     pub fn to_self(&self) -> Option<SelfTy> {
2084         if self.name != "self" {
2085             return None;
2086         }
2087         if self.type_.is_self_type() {
2088             return Some(SelfValue);
2089         }
2090         match self.type_ {
2091             BorrowedRef{ref lifetime, mutability, ref type_} if type_.is_self_type() => {
2092                 Some(SelfBorrowed(lifetime.clone(), mutability))
2093             }
2094             _ => Some(SelfExplicit(self.type_.clone()))
2095         }
2096     }
2097 }
2098
2099 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2100 pub enum FunctionRetTy {
2101     Return(Type),
2102     DefaultReturn,
2103 }
2104
2105 impl Clean<FunctionRetTy> for hir::FunctionRetTy {
2106     fn clean(&self, cx: &DocContext<'_>) -> FunctionRetTy {
2107         match *self {
2108             hir::Return(ref typ) => Return(typ.clean(cx)),
2109             hir::DefaultReturn(..) => DefaultReturn,
2110         }
2111     }
2112 }
2113
2114 impl GetDefId for FunctionRetTy {
2115     fn def_id(&self) -> Option<DefId> {
2116         match *self {
2117             Return(ref ty) => ty.def_id(),
2118             DefaultReturn => None,
2119         }
2120     }
2121 }
2122
2123 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2124 pub struct Trait {
2125     pub auto: bool,
2126     pub unsafety: hir::Unsafety,
2127     pub items: Vec<Item>,
2128     pub generics: Generics,
2129     pub bounds: Vec<GenericBound>,
2130     pub is_spotlight: bool,
2131     pub is_auto: bool,
2132 }
2133
2134 impl Clean<Item> for doctree::Trait {
2135     fn clean(&self, cx: &DocContext<'_>) -> Item {
2136         let attrs = self.attrs.clean(cx);
2137         let is_spotlight = attrs.has_doc_flag(sym::spotlight);
2138         Item {
2139             name: Some(self.name.clean(cx)),
2140             attrs: attrs,
2141             source: self.whence.clean(cx),
2142             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
2143             visibility: self.vis.clean(cx),
2144             stability: self.stab.clean(cx),
2145             deprecation: self.depr.clean(cx),
2146             inner: TraitItem(Trait {
2147                 auto: self.is_auto.clean(cx),
2148                 unsafety: self.unsafety,
2149                 items: self.items.clean(cx),
2150                 generics: self.generics.clean(cx),
2151                 bounds: self.bounds.clean(cx),
2152                 is_spotlight,
2153                 is_auto: self.is_auto.clean(cx),
2154             }),
2155         }
2156     }
2157 }
2158
2159 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2160 pub struct TraitAlias {
2161     pub generics: Generics,
2162     pub bounds: Vec<GenericBound>,
2163 }
2164
2165 impl Clean<Item> for doctree::TraitAlias {
2166     fn clean(&self, cx: &DocContext<'_>) -> Item {
2167         let attrs = self.attrs.clean(cx);
2168         Item {
2169             name: Some(self.name.clean(cx)),
2170             attrs,
2171             source: self.whence.clean(cx),
2172             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
2173             visibility: self.vis.clean(cx),
2174             stability: self.stab.clean(cx),
2175             deprecation: self.depr.clean(cx),
2176             inner: TraitAliasItem(TraitAlias {
2177                 generics: self.generics.clean(cx),
2178                 bounds: self.bounds.clean(cx),
2179             }),
2180         }
2181     }
2182 }
2183
2184 impl Clean<bool> for hir::IsAuto {
2185     fn clean(&self, _: &DocContext<'_>) -> bool {
2186         match *self {
2187             hir::IsAuto::Yes => true,
2188             hir::IsAuto::No => false,
2189         }
2190     }
2191 }
2192
2193 impl Clean<Type> for hir::TraitRef {
2194     fn clean(&self, cx: &DocContext<'_>) -> Type {
2195         resolve_type(cx, self.path.clean(cx), self.hir_ref_id)
2196     }
2197 }
2198
2199 impl Clean<PolyTrait> for hir::PolyTraitRef {
2200     fn clean(&self, cx: &DocContext<'_>) -> PolyTrait {
2201         PolyTrait {
2202             trait_: self.trait_ref.clean(cx),
2203             generic_params: self.bound_generic_params.clean(cx)
2204         }
2205     }
2206 }
2207
2208 impl Clean<Item> for hir::TraitItem {
2209     fn clean(&self, cx: &DocContext<'_>) -> Item {
2210         let inner = match self.node {
2211             hir::TraitItemKind::Const(ref ty, default) => {
2212                 AssociatedConstItem(ty.clean(cx),
2213                                     default.map(|e| print_const_expr(cx, e)))
2214             }
2215             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Provided(body)) => {
2216                 MethodItem((sig, &self.generics, body, None).clean(cx))
2217             }
2218             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Required(ref names)) => {
2219                 let (generics, decl) = enter_impl_trait(cx, || {
2220                     (self.generics.clean(cx), (&*sig.decl, &names[..]).clean(cx))
2221                 });
2222                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
2223                 TyMethodItem(TyMethod {
2224                     header: sig.header,
2225                     decl,
2226                     generics,
2227                     all_types,
2228                     ret_types,
2229                 })
2230             }
2231             hir::TraitItemKind::Type(ref bounds, ref default) => {
2232                 AssociatedTypeItem(bounds.clean(cx), default.clean(cx))
2233             }
2234         };
2235         let local_did = cx.tcx.hir().local_def_id_from_hir_id(self.hir_id);
2236         Item {
2237             name: Some(self.ident.name.clean(cx)),
2238             attrs: self.attrs.clean(cx),
2239             source: self.span.clean(cx),
2240             def_id: local_did,
2241             visibility: None,
2242             stability: get_stability(cx, local_did),
2243             deprecation: get_deprecation(cx, local_did),
2244             inner,
2245         }
2246     }
2247 }
2248
2249 impl Clean<Item> for hir::ImplItem {
2250     fn clean(&self, cx: &DocContext<'_>) -> Item {
2251         let inner = match self.node {
2252             hir::ImplItemKind::Const(ref ty, expr) => {
2253                 AssociatedConstItem(ty.clean(cx),
2254                                     Some(print_const_expr(cx, expr)))
2255             }
2256             hir::ImplItemKind::Method(ref sig, body) => {
2257                 MethodItem((sig, &self.generics, body, Some(self.defaultness)).clean(cx))
2258             }
2259             hir::ImplItemKind::Type(ref ty) => TypedefItem(Typedef {
2260                 type_: ty.clean(cx),
2261                 generics: Generics::default(),
2262             }, true),
2263             hir::ImplItemKind::Existential(ref bounds) => ExistentialItem(Existential {
2264                 bounds: bounds.clean(cx),
2265                 generics: Generics::default(),
2266             }, true),
2267         };
2268         let local_did = cx.tcx.hir().local_def_id_from_hir_id(self.hir_id);
2269         Item {
2270             name: Some(self.ident.name.clean(cx)),
2271             source: self.span.clean(cx),
2272             attrs: self.attrs.clean(cx),
2273             def_id: local_did,
2274             visibility: self.vis.clean(cx),
2275             stability: get_stability(cx, local_did),
2276             deprecation: get_deprecation(cx, local_did),
2277             inner,
2278         }
2279     }
2280 }
2281
2282 impl<'tcx> Clean<Item> for ty::AssociatedItem {
2283     fn clean(&self, cx: &DocContext<'_>) -> Item {
2284         let inner = match self.kind {
2285             ty::AssociatedKind::Const => {
2286                 let ty = cx.tcx.type_of(self.def_id);
2287                 let default = if self.defaultness.has_value() {
2288                     Some(inline::print_inlined_const(cx, self.def_id))
2289                 } else {
2290                     None
2291                 };
2292                 AssociatedConstItem(ty.clean(cx), default)
2293             }
2294             ty::AssociatedKind::Method => {
2295                 let generics = (cx.tcx.generics_of(self.def_id),
2296                                 &cx.tcx.explicit_predicates_of(self.def_id)).clean(cx);
2297                 let sig = cx.tcx.fn_sig(self.def_id);
2298                 let mut decl = (self.def_id, sig).clean(cx);
2299
2300                 if self.method_has_self_argument {
2301                     let self_ty = match self.container {
2302                         ty::ImplContainer(def_id) => {
2303                             cx.tcx.type_of(def_id)
2304                         }
2305                         ty::TraitContainer(_) => cx.tcx.mk_self_type()
2306                     };
2307                     let self_arg_ty = *sig.input(0).skip_binder();
2308                     if self_arg_ty == self_ty {
2309                         decl.inputs.values[0].type_ = Generic(String::from("Self"));
2310                     } else if let ty::Ref(_, ty, _) = self_arg_ty.sty {
2311                         if ty == self_ty {
2312                             match decl.inputs.values[0].type_ {
2313                                 BorrowedRef{ref mut type_, ..} => {
2314                                     **type_ = Generic(String::from("Self"))
2315                                 }
2316                                 _ => unreachable!(),
2317                             }
2318                         }
2319                     }
2320                 }
2321
2322                 let provided = match self.container {
2323                     ty::ImplContainer(_) => true,
2324                     ty::TraitContainer(_) => self.defaultness.has_value()
2325                 };
2326                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
2327                 if provided {
2328                     let constness = if cx.tcx.is_min_const_fn(self.def_id) {
2329                         hir::Constness::Const
2330                     } else {
2331                         hir::Constness::NotConst
2332                     };
2333                     let defaultness = match self.container {
2334                         ty::ImplContainer(_) => Some(self.defaultness),
2335                         ty::TraitContainer(_) => None,
2336                     };
2337                     MethodItem(Method {
2338                         generics,
2339                         decl,
2340                         header: hir::FnHeader {
2341                             unsafety: sig.unsafety(),
2342                             abi: sig.abi(),
2343                             constness,
2344                             asyncness: hir::IsAsync::NotAsync,
2345                         },
2346                         defaultness,
2347                         all_types,
2348                         ret_types,
2349                     })
2350                 } else {
2351                     TyMethodItem(TyMethod {
2352                         generics,
2353                         decl,
2354                         header: hir::FnHeader {
2355                             unsafety: sig.unsafety(),
2356                             abi: sig.abi(),
2357                             constness: hir::Constness::NotConst,
2358                             asyncness: hir::IsAsync::NotAsync,
2359                         },
2360                         all_types,
2361                         ret_types,
2362                     })
2363                 }
2364             }
2365             ty::AssociatedKind::Type => {
2366                 let my_name = self.ident.name.clean(cx);
2367
2368                 if let ty::TraitContainer(did) = self.container {
2369                     // When loading a cross-crate associated type, the bounds for this type
2370                     // are actually located on the trait/impl itself, so we need to load
2371                     // all of the generics from there and then look for bounds that are
2372                     // applied to this associated type in question.
2373                     let predicates = cx.tcx.explicit_predicates_of(did);
2374                     let generics = (cx.tcx.generics_of(did), &predicates).clean(cx);
2375                     let mut bounds = generics.where_predicates.iter().filter_map(|pred| {
2376                         let (name, self_type, trait_, bounds) = match *pred {
2377                             WherePredicate::BoundPredicate {
2378                                 ty: QPath { ref name, ref self_type, ref trait_ },
2379                                 ref bounds
2380                             } => (name, self_type, trait_, bounds),
2381                             _ => return None,
2382                         };
2383                         if *name != my_name { return None }
2384                         match **trait_ {
2385                             ResolvedPath { did, .. } if did == self.container.id() => {}
2386                             _ => return None,
2387                         }
2388                         match **self_type {
2389                             Generic(ref s) if *s == "Self" => {}
2390                             _ => return None,
2391                         }
2392                         Some(bounds)
2393                     }).flat_map(|i| i.iter().cloned()).collect::<Vec<_>>();
2394                     // Our Sized/?Sized bound didn't get handled when creating the generics
2395                     // because we didn't actually get our whole set of bounds until just now
2396                     // (some of them may have come from the trait). If we do have a sized
2397                     // bound, we remove it, and if we don't then we add the `?Sized` bound
2398                     // at the end.
2399                     match bounds.iter().position(|b| b.is_sized_bound(cx)) {
2400                         Some(i) => { bounds.remove(i); }
2401                         None => bounds.push(GenericBound::maybe_sized(cx)),
2402                     }
2403
2404                     let ty = if self.defaultness.has_value() {
2405                         Some(cx.tcx.type_of(self.def_id))
2406                     } else {
2407                         None
2408                     };
2409
2410                     AssociatedTypeItem(bounds, ty.clean(cx))
2411                 } else {
2412                     TypedefItem(Typedef {
2413                         type_: cx.tcx.type_of(self.def_id).clean(cx),
2414                         generics: Generics {
2415                             params: Vec::new(),
2416                             where_predicates: Vec::new(),
2417                         },
2418                     }, true)
2419                 }
2420             }
2421             ty::AssociatedKind::Existential => unimplemented!(),
2422         };
2423
2424         let visibility = match self.container {
2425             ty::ImplContainer(_) => self.vis.clean(cx),
2426             ty::TraitContainer(_) => None,
2427         };
2428
2429         Item {
2430             name: Some(self.ident.name.clean(cx)),
2431             visibility,
2432             stability: get_stability(cx, self.def_id),
2433             deprecation: get_deprecation(cx, self.def_id),
2434             def_id: self.def_id,
2435             attrs: inline::load_attrs(cx, self.def_id),
2436             source: cx.tcx.def_span(self.def_id).clean(cx),
2437             inner,
2438         }
2439     }
2440 }
2441
2442 /// A trait reference, which may have higher ranked lifetimes.
2443 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2444 pub struct PolyTrait {
2445     pub trait_: Type,
2446     pub generic_params: Vec<GenericParamDef>,
2447 }
2448
2449 /// A representation of a Type suitable for hyperlinking purposes. Ideally one can get the original
2450 /// type out of the AST/TyCtxt given one of these, if more information is needed. Most importantly
2451 /// it does not preserve mutability or boxes.
2452 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2453 pub enum Type {
2454     /// Structs/enums/traits (most that'd be an `hir::TyKind::Path`).
2455     ResolvedPath {
2456         path: Path,
2457         param_names: Option<Vec<GenericBound>>,
2458         did: DefId,
2459         /// `true` if is a `T::Name` path for associated types.
2460         is_generic: bool,
2461     },
2462     /// For parameterized types, so the consumer of the JSON don't go
2463     /// looking for types which don't exist anywhere.
2464     Generic(String),
2465     /// Primitives are the fixed-size numeric types (plus int/usize/float), char,
2466     /// arrays, slices, and tuples.
2467     Primitive(PrimitiveType),
2468     /// extern "ABI" fn
2469     BareFunction(Box<BareFunctionDecl>),
2470     Tuple(Vec<Type>),
2471     Slice(Box<Type>),
2472     Array(Box<Type>, String),
2473     Never,
2474     CVarArgs,
2475     Unique(Box<Type>),
2476     RawPointer(Mutability, Box<Type>),
2477     BorrowedRef {
2478         lifetime: Option<Lifetime>,
2479         mutability: Mutability,
2480         type_: Box<Type>,
2481     },
2482
2483     // <Type as Trait>::Name
2484     QPath {
2485         name: String,
2486         self_type: Box<Type>,
2487         trait_: Box<Type>
2488     },
2489
2490     // _
2491     Infer,
2492
2493     // impl TraitA+TraitB
2494     ImplTrait(Vec<GenericBound>),
2495 }
2496
2497 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Copy, Debug)]
2498 pub enum PrimitiveType {
2499     Isize, I8, I16, I32, I64, I128,
2500     Usize, U8, U16, U32, U64, U128,
2501     F32, F64,
2502     Char,
2503     Bool,
2504     Str,
2505     Slice,
2506     Array,
2507     Tuple,
2508     Unit,
2509     RawPointer,
2510     Reference,
2511     Fn,
2512     Never,
2513     CVarArgs,
2514 }
2515
2516 #[derive(Clone, RustcEncodable, RustcDecodable, Copy, Debug)]
2517 pub enum TypeKind {
2518     Enum,
2519     Function,
2520     Module,
2521     Const,
2522     Static,
2523     Struct,
2524     Union,
2525     Trait,
2526     Variant,
2527     Typedef,
2528     Foreign,
2529     Macro,
2530     Attr,
2531     Derive,
2532     TraitAlias,
2533 }
2534
2535 pub trait GetDefId {
2536     fn def_id(&self) -> Option<DefId>;
2537 }
2538
2539 impl<T: GetDefId> GetDefId for Option<T> {
2540     fn def_id(&self) -> Option<DefId> {
2541         self.as_ref().and_then(|d| d.def_id())
2542     }
2543 }
2544
2545 impl Type {
2546     pub fn primitive_type(&self) -> Option<PrimitiveType> {
2547         match *self {
2548             Primitive(p) | BorrowedRef { type_: box Primitive(p), ..} => Some(p),
2549             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
2550             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
2551             Tuple(ref tys) => if tys.is_empty() {
2552                 Some(PrimitiveType::Unit)
2553             } else {
2554                 Some(PrimitiveType::Tuple)
2555             },
2556             RawPointer(..) => Some(PrimitiveType::RawPointer),
2557             BorrowedRef { type_: box Generic(..), .. } => Some(PrimitiveType::Reference),
2558             BareFunction(..) => Some(PrimitiveType::Fn),
2559             Never => Some(PrimitiveType::Never),
2560             _ => None,
2561         }
2562     }
2563
2564     pub fn is_generic(&self) -> bool {
2565         match *self {
2566             ResolvedPath { is_generic, .. } => is_generic,
2567             _ => false,
2568         }
2569     }
2570
2571     pub fn is_self_type(&self) -> bool {
2572         match *self {
2573             Generic(ref name) => name == "Self",
2574             _ => false
2575         }
2576     }
2577
2578     pub fn generics(&self) -> Option<Vec<Type>> {
2579         match *self {
2580             ResolvedPath { ref path, .. } => {
2581                 path.segments.last().and_then(|seg| {
2582                     if let GenericArgs::AngleBracketed { ref args, .. } = seg.args {
2583                         Some(args.iter().filter_map(|arg| match arg {
2584                             GenericArg::Type(ty) => Some(ty.clone()),
2585                             _ => None,
2586                         }).collect())
2587                     } else {
2588                         None
2589                     }
2590                 })
2591             }
2592             _ => None,
2593         }
2594     }
2595
2596     pub fn bindings(&self) -> Option<&[TypeBinding]> {
2597         match *self {
2598             ResolvedPath { ref path, .. } => {
2599                 path.segments.last().and_then(|seg| {
2600                     if let GenericArgs::AngleBracketed { ref bindings, .. } = seg.args {
2601                         Some(&**bindings)
2602                     } else {
2603                         None
2604                     }
2605                 })
2606             }
2607             _ => None
2608         }
2609     }
2610
2611     pub fn is_full_generic(&self) -> bool {
2612         match *self {
2613             Type::Generic(_) => true,
2614             _ => false,
2615         }
2616     }
2617 }
2618
2619 impl GetDefId for Type {
2620     fn def_id(&self) -> Option<DefId> {
2621         match *self {
2622             ResolvedPath { did, .. } => Some(did),
2623             Primitive(p) => crate::html::render::cache().primitive_locations.get(&p).cloned(),
2624             BorrowedRef { type_: box Generic(..), .. } =>
2625                 Primitive(PrimitiveType::Reference).def_id(),
2626             BorrowedRef { ref type_, .. } => type_.def_id(),
2627             Tuple(ref tys) => if tys.is_empty() {
2628                 Primitive(PrimitiveType::Unit).def_id()
2629             } else {
2630                 Primitive(PrimitiveType::Tuple).def_id()
2631             },
2632             BareFunction(..) => Primitive(PrimitiveType::Fn).def_id(),
2633             Never => Primitive(PrimitiveType::Never).def_id(),
2634             Slice(..) => Primitive(PrimitiveType::Slice).def_id(),
2635             Array(..) => Primitive(PrimitiveType::Array).def_id(),
2636             RawPointer(..) => Primitive(PrimitiveType::RawPointer).def_id(),
2637             QPath { ref self_type, .. } => self_type.def_id(),
2638             _ => None,
2639         }
2640     }
2641 }
2642
2643 impl PrimitiveType {
2644     fn from_str(s: &str) -> Option<PrimitiveType> {
2645         match s {
2646             "isize" => Some(PrimitiveType::Isize),
2647             "i8" => Some(PrimitiveType::I8),
2648             "i16" => Some(PrimitiveType::I16),
2649             "i32" => Some(PrimitiveType::I32),
2650             "i64" => Some(PrimitiveType::I64),
2651             "i128" => Some(PrimitiveType::I128),
2652             "usize" => Some(PrimitiveType::Usize),
2653             "u8" => Some(PrimitiveType::U8),
2654             "u16" => Some(PrimitiveType::U16),
2655             "u32" => Some(PrimitiveType::U32),
2656             "u64" => Some(PrimitiveType::U64),
2657             "u128" => Some(PrimitiveType::U128),
2658             "bool" => Some(PrimitiveType::Bool),
2659             "char" => Some(PrimitiveType::Char),
2660             "str" => Some(PrimitiveType::Str),
2661             "f32" => Some(PrimitiveType::F32),
2662             "f64" => Some(PrimitiveType::F64),
2663             "array" => Some(PrimitiveType::Array),
2664             "slice" => Some(PrimitiveType::Slice),
2665             "tuple" => Some(PrimitiveType::Tuple),
2666             "unit" => Some(PrimitiveType::Unit),
2667             "pointer" => Some(PrimitiveType::RawPointer),
2668             "reference" => Some(PrimitiveType::Reference),
2669             "fn" => Some(PrimitiveType::Fn),
2670             "never" => Some(PrimitiveType::Never),
2671             _ => None,
2672         }
2673     }
2674
2675     pub fn as_str(&self) -> &'static str {
2676         use self::PrimitiveType::*;
2677         match *self {
2678             Isize => "isize",
2679             I8 => "i8",
2680             I16 => "i16",
2681             I32 => "i32",
2682             I64 => "i64",
2683             I128 => "i128",
2684             Usize => "usize",
2685             U8 => "u8",
2686             U16 => "u16",
2687             U32 => "u32",
2688             U64 => "u64",
2689             U128 => "u128",
2690             F32 => "f32",
2691             F64 => "f64",
2692             Str => "str",
2693             Bool => "bool",
2694             Char => "char",
2695             Array => "array",
2696             Slice => "slice",
2697             Tuple => "tuple",
2698             Unit => "unit",
2699             RawPointer => "pointer",
2700             Reference => "reference",
2701             Fn => "fn",
2702             Never => "never",
2703             CVarArgs => "...",
2704         }
2705     }
2706
2707     pub fn to_url_str(&self) -> &'static str {
2708         self.as_str()
2709     }
2710 }
2711
2712 impl From<ast::IntTy> for PrimitiveType {
2713     fn from(int_ty: ast::IntTy) -> PrimitiveType {
2714         match int_ty {
2715             ast::IntTy::Isize => PrimitiveType::Isize,
2716             ast::IntTy::I8 => PrimitiveType::I8,
2717             ast::IntTy::I16 => PrimitiveType::I16,
2718             ast::IntTy::I32 => PrimitiveType::I32,
2719             ast::IntTy::I64 => PrimitiveType::I64,
2720             ast::IntTy::I128 => PrimitiveType::I128,
2721         }
2722     }
2723 }
2724
2725 impl From<ast::UintTy> for PrimitiveType {
2726     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
2727         match uint_ty {
2728             ast::UintTy::Usize => PrimitiveType::Usize,
2729             ast::UintTy::U8 => PrimitiveType::U8,
2730             ast::UintTy::U16 => PrimitiveType::U16,
2731             ast::UintTy::U32 => PrimitiveType::U32,
2732             ast::UintTy::U64 => PrimitiveType::U64,
2733             ast::UintTy::U128 => PrimitiveType::U128,
2734         }
2735     }
2736 }
2737
2738 impl From<ast::FloatTy> for PrimitiveType {
2739     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
2740         match float_ty {
2741             ast::FloatTy::F32 => PrimitiveType::F32,
2742             ast::FloatTy::F64 => PrimitiveType::F64,
2743         }
2744     }
2745 }
2746
2747 impl Clean<Type> for hir::Ty {
2748     fn clean(&self, cx: &DocContext<'_>) -> Type {
2749         use rustc::hir::*;
2750
2751         match self.node {
2752             TyKind::Never => Never,
2753             TyKind::CVarArgs(_) => CVarArgs,
2754             TyKind::Ptr(ref m) => RawPointer(m.mutbl.clean(cx), box m.ty.clean(cx)),
2755             TyKind::Rptr(ref l, ref m) => {
2756                 let lifetime = if l.is_elided() {
2757                     None
2758                 } else {
2759                     Some(l.clean(cx))
2760                 };
2761                 BorrowedRef {lifetime: lifetime, mutability: m.mutbl.clean(cx),
2762                              type_: box m.ty.clean(cx)}
2763             }
2764             TyKind::Slice(ref ty) => Slice(box ty.clean(cx)),
2765             TyKind::Array(ref ty, ref length) => {
2766                 let def_id = cx.tcx.hir().local_def_id_from_hir_id(length.hir_id);
2767                 let param_env = cx.tcx.param_env(def_id);
2768                 let substs = InternalSubsts::identity_for_item(cx.tcx, def_id);
2769                 let cid = GlobalId {
2770                     instance: ty::Instance::new(def_id, substs),
2771                     promoted: None
2772                 };
2773                 let length = match cx.tcx.const_eval(param_env.and(cid)) {
2774                     Ok(length) => print_const(cx, length),
2775                     Err(_) => "_".to_string(),
2776                 };
2777                 Array(box ty.clean(cx), length)
2778             },
2779             TyKind::Tup(ref tys) => Tuple(tys.clean(cx)),
2780             TyKind::Def(item_id, _) => {
2781                 let item = cx.tcx.hir().expect_item_by_hir_id(item_id.id);
2782                 if let hir::ItemKind::Existential(ref ty) = item.node {
2783                     ImplTrait(ty.bounds.clean(cx))
2784                 } else {
2785                     unreachable!()
2786                 }
2787             }
2788             TyKind::Path(hir::QPath::Resolved(None, ref path)) => {
2789                 if let Res::Def(DefKind::TyParam, did) = path.res {
2790                     if let Some(new_ty) = cx.ty_substs.borrow().get(&did).cloned() {
2791                         return new_ty;
2792                     }
2793                     if let Some(bounds) = cx.impl_trait_bounds.borrow_mut().remove(&did) {
2794                         return ImplTrait(bounds);
2795                     }
2796                 }
2797
2798                 let mut alias = None;
2799                 if let Res::Def(DefKind::TyAlias, def_id) = path.res {
2800                     // Substitute private type aliases
2801                     if let Some(hir_id) = cx.tcx.hir().as_local_hir_id(def_id) {
2802                         if !cx.renderinfo.borrow().access_levels.is_exported(def_id) {
2803                             alias = Some(&cx.tcx.hir().expect_item_by_hir_id(hir_id).node);
2804                         }
2805                     }
2806                 };
2807
2808                 if let Some(&hir::ItemKind::Ty(ref ty, ref generics)) = alias {
2809                     let provided_params = &path.segments.last().expect("segments were empty");
2810                     let mut ty_substs = FxHashMap::default();
2811                     let mut lt_substs = FxHashMap::default();
2812                     let mut ct_substs = FxHashMap::default();
2813                     provided_params.with_generic_args(|generic_args| {
2814                         let mut indices: GenericParamCount = Default::default();
2815                         for param in generics.params.iter() {
2816                             match param.kind {
2817                                 hir::GenericParamKind::Lifetime { .. } => {
2818                                     let mut j = 0;
2819                                     let lifetime = generic_args.args.iter().find_map(|arg| {
2820                                         match arg {
2821                                             hir::GenericArg::Lifetime(lt) => {
2822                                                 if indices.lifetimes == j {
2823                                                     return Some(lt);
2824                                                 }
2825                                                 j += 1;
2826                                                 None
2827                                             }
2828                                             _ => None,
2829                                         }
2830                                     });
2831                                     if let Some(lt) = lifetime.cloned() {
2832                                         if !lt.is_elided() {
2833                                             let lt_def_id =
2834                                                 cx.tcx.hir().local_def_id_from_hir_id(param.hir_id);
2835                                             lt_substs.insert(lt_def_id, lt.clean(cx));
2836                                         }
2837                                     }
2838                                     indices.lifetimes += 1;
2839                                 }
2840                                 hir::GenericParamKind::Type { ref default, .. } => {
2841                                     let ty_param_def_id =
2842                                         cx.tcx.hir().local_def_id_from_hir_id(param.hir_id);
2843                                     let mut j = 0;
2844                                     let type_ = generic_args.args.iter().find_map(|arg| {
2845                                         match arg {
2846                                             hir::GenericArg::Type(ty) => {
2847                                                 if indices.types == j {
2848                                                     return Some(ty);
2849                                                 }
2850                                                 j += 1;
2851                                                 None
2852                                             }
2853                                             _ => None,
2854                                         }
2855                                     });
2856                                     if let Some(ty) = type_.cloned() {
2857                                         ty_substs.insert(ty_param_def_id, ty.clean(cx));
2858                                     } else if let Some(default) = default.clone() {
2859                                         ty_substs.insert(ty_param_def_id,
2860                                                          default.into_inner().clean(cx));
2861                                     }
2862                                     indices.types += 1;
2863                                 }
2864                                 hir::GenericParamKind::Const { .. } => {
2865                                     let const_param_def_id =
2866                                         cx.tcx.hir().local_def_id_from_hir_id(param.hir_id);
2867                                     let mut j = 0;
2868                                     let const_ = generic_args.args.iter().find_map(|arg| {
2869                                         match arg {
2870                                             hir::GenericArg::Const(ct) => {
2871                                                 if indices.consts == j {
2872                                                     return Some(ct);
2873                                                 }
2874                                                 j += 1;
2875                                                 None
2876                                             }
2877                                             _ => None,
2878                                         }
2879                                     });
2880                                     if let Some(ct) = const_.cloned() {
2881                                         ct_substs.insert(const_param_def_id, ct.clean(cx));
2882                                     }
2883                                     // FIXME(const_generics:defaults)
2884                                     indices.consts += 1;
2885                                 }
2886                             }
2887                         }
2888                     });
2889                     return cx.enter_alias(ty_substs, lt_substs, ct_substs, || ty.clean(cx));
2890                 }
2891                 resolve_type(cx, path.clean(cx), self.hir_id)
2892             }
2893             TyKind::Path(hir::QPath::Resolved(Some(ref qself), ref p)) => {
2894                 let mut segments: Vec<_> = p.segments.clone().into();
2895                 segments.pop();
2896                 let trait_path = hir::Path {
2897                     span: p.span,
2898                     res: Res::Def(
2899                         DefKind::Trait,
2900                         cx.tcx.associated_item(p.res.def_id()).container.id(),
2901                     ),
2902                     segments: segments.into(),
2903                 };
2904                 Type::QPath {
2905                     name: p.segments.last().expect("segments were empty").ident.name.clean(cx),
2906                     self_type: box qself.clean(cx),
2907                     trait_: box resolve_type(cx, trait_path.clean(cx), self.hir_id)
2908                 }
2909             }
2910             TyKind::Path(hir::QPath::TypeRelative(ref qself, ref segment)) => {
2911                 let mut res = Res::Err;
2912                 let ty = hir_ty_to_ty(cx.tcx, self);
2913                 if let ty::Projection(proj) = ty.sty {
2914                     res = Res::Def(DefKind::Trait, proj.trait_ref(cx.tcx).def_id);
2915                 }
2916                 let trait_path = hir::Path {
2917                     span: self.span,
2918                     res,
2919                     segments: vec![].into(),
2920                 };
2921                 Type::QPath {
2922                     name: segment.ident.name.clean(cx),
2923                     self_type: box qself.clean(cx),
2924                     trait_: box resolve_type(cx, trait_path.clean(cx), self.hir_id)
2925                 }
2926             }
2927             TyKind::TraitObject(ref bounds, ref lifetime) => {
2928                 match bounds[0].clean(cx).trait_ {
2929                     ResolvedPath { path, param_names: None, did, is_generic } => {
2930                         let mut bounds: Vec<self::GenericBound> = bounds[1..].iter().map(|bound| {
2931                             self::GenericBound::TraitBound(bound.clean(cx),
2932                                                            hir::TraitBoundModifier::None)
2933                         }).collect();
2934                         if !lifetime.is_elided() {
2935                             bounds.push(self::GenericBound::Outlives(lifetime.clean(cx)));
2936                         }
2937                         ResolvedPath { path, param_names: Some(bounds), did, is_generic, }
2938                     }
2939                     _ => Infer // shouldn't happen
2940                 }
2941             }
2942             TyKind::BareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
2943             TyKind::Infer | TyKind::Err => Infer,
2944             TyKind::Typeof(..) => panic!("Unimplemented type {:?}", self.node),
2945         }
2946     }
2947 }
2948
2949 impl<'tcx> Clean<Type> for Ty<'tcx> {
2950     fn clean(&self, cx: &DocContext<'_>) -> Type {
2951         debug!("cleaning type: {:?}", self);
2952         match self.sty {
2953             ty::Never => Never,
2954             ty::Bool => Primitive(PrimitiveType::Bool),
2955             ty::Char => Primitive(PrimitiveType::Char),
2956             ty::Int(int_ty) => Primitive(int_ty.into()),
2957             ty::Uint(uint_ty) => Primitive(uint_ty.into()),
2958             ty::Float(float_ty) => Primitive(float_ty.into()),
2959             ty::Str => Primitive(PrimitiveType::Str),
2960             ty::Slice(ty) => Slice(box ty.clean(cx)),
2961             ty::Array(ty, n) => {
2962                 let mut n = *cx.tcx.lift(&n).expect("array lift failed");
2963                 if let ConstValue::Unevaluated(def_id, substs) = n.val {
2964                     let param_env = cx.tcx.param_env(def_id);
2965                     let cid = GlobalId {
2966                         instance: ty::Instance::new(def_id, substs),
2967                         promoted: None
2968                     };
2969                     if let Ok(new_n) = cx.tcx.const_eval(param_env.and(cid)) {
2970                         n = new_n;
2971                     }
2972                 };
2973                 let n = print_const(cx, n);
2974                 Array(box ty.clean(cx), n)
2975             }
2976             ty::RawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
2977             ty::Ref(r, ty, mutbl) => BorrowedRef {
2978                 lifetime: r.clean(cx),
2979                 mutability: mutbl.clean(cx),
2980                 type_: box ty.clean(cx),
2981             },
2982             ty::FnDef(..) |
2983             ty::FnPtr(_) => {
2984                 let ty = cx.tcx.lift(self).expect("FnPtr lift failed");
2985                 let sig = ty.fn_sig(cx.tcx);
2986                 BareFunction(box BareFunctionDecl {
2987                     unsafety: sig.unsafety(),
2988                     generic_params: Vec::new(),
2989                     decl: (cx.tcx.hir().local_def_id(ast::CRATE_NODE_ID), sig).clean(cx),
2990                     abi: sig.abi(),
2991                 })
2992             }
2993             ty::Adt(def, substs) => {
2994                 let did = def.did;
2995                 let kind = match def.adt_kind() {
2996                     AdtKind::Struct => TypeKind::Struct,
2997                     AdtKind::Union => TypeKind::Union,
2998                     AdtKind::Enum => TypeKind::Enum,
2999                 };
3000                 inline::record_extern_fqn(cx, did, kind);
3001                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
3002                                          None, false, vec![], substs);
3003                 ResolvedPath {
3004                     path,
3005                     param_names: None,
3006                     did,
3007                     is_generic: false,
3008                 }
3009             }
3010             ty::Foreign(did) => {
3011                 inline::record_extern_fqn(cx, did, TypeKind::Foreign);
3012                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
3013                                          None, false, vec![], InternalSubsts::empty());
3014                 ResolvedPath {
3015                     path: path,
3016                     param_names: None,
3017                     did: did,
3018                     is_generic: false,
3019                 }
3020             }
3021             ty::Dynamic(ref obj, ref reg) => {
3022                 // HACK: pick the first `did` as the `did` of the trait object. Someone
3023                 // might want to implement "native" support for marker-trait-only
3024                 // trait objects.
3025                 let mut dids = obj.principal_def_id().into_iter().chain(obj.auto_traits());
3026                 let did = dids.next().unwrap_or_else(|| {
3027                     panic!("found trait object `{:?}` with no traits?", self)
3028                 });
3029                 let substs = match obj.principal() {
3030                     Some(principal) => principal.skip_binder().substs,
3031                     // marker traits have no substs.
3032                     _ => cx.tcx.intern_substs(&[])
3033                 };
3034
3035                 inline::record_extern_fqn(cx, did, TypeKind::Trait);
3036
3037                 let mut param_names = vec![];
3038                 reg.clean(cx).map(|b| param_names.push(GenericBound::Outlives(b)));
3039                 for did in dids {
3040                     let empty = cx.tcx.intern_substs(&[]);
3041                     let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
3042                         Some(did), false, vec![], empty);
3043                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
3044                     let bound = GenericBound::TraitBound(PolyTrait {
3045                         trait_: ResolvedPath {
3046                             path,
3047                             param_names: None,
3048                             did,
3049                             is_generic: false,
3050                         },
3051                         generic_params: Vec::new(),
3052                     }, hir::TraitBoundModifier::None);
3053                     param_names.push(bound);
3054                 }
3055
3056                 let mut bindings = vec![];
3057                 for pb in obj.projection_bounds() {
3058                     bindings.push(TypeBinding {
3059                         name: cx.tcx.associated_item(pb.item_def_id()).ident.name.clean(cx),
3060                         ty: pb.skip_binder().ty.clean(cx)
3061                     });
3062                 }
3063
3064                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(), Some(did),
3065                     false, bindings, substs);
3066                 ResolvedPath {
3067                     path,
3068                     param_names: Some(param_names),
3069                     did,
3070                     is_generic: false,
3071                 }
3072             }
3073             ty::Tuple(ref t) => {
3074                 Tuple(t.iter().map(|t| t.expect_ty()).collect::<Vec<_>>().clean(cx))
3075             }
3076
3077             ty::Projection(ref data) => data.clean(cx),
3078
3079             ty::Param(ref p) => Generic(p.name.to_string()),
3080
3081             ty::Opaque(def_id, substs) => {
3082                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
3083                 // by looking up the projections associated with the def_id.
3084                 let predicates_of = cx.tcx.explicit_predicates_of(def_id);
3085                 let substs = cx.tcx.lift(&substs).expect("Opaque lift failed");
3086                 let bounds = predicates_of.instantiate(cx.tcx, substs);
3087                 let mut regions = vec![];
3088                 let mut has_sized = false;
3089                 let mut bounds = bounds.predicates.iter().filter_map(|predicate| {
3090                     let trait_ref = if let Some(tr) = predicate.to_opt_poly_trait_ref() {
3091                         tr
3092                     } else if let ty::Predicate::TypeOutlives(pred) = *predicate {
3093                         // these should turn up at the end
3094                         pred.skip_binder().1.clean(cx).map(|r| {
3095                             regions.push(GenericBound::Outlives(r))
3096                         });
3097                         return None;
3098                     } else {
3099                         return None;
3100                     };
3101
3102                     if let Some(sized) = cx.tcx.lang_items().sized_trait() {
3103                         if trait_ref.def_id() == sized {
3104                             has_sized = true;
3105                             return None;
3106                         }
3107                     }
3108
3109                     let bounds = bounds.predicates.iter().filter_map(|pred|
3110                         if let ty::Predicate::Projection(proj) = *pred {
3111                             let proj = proj.skip_binder();
3112                             if proj.projection_ty.trait_ref(cx.tcx) == *trait_ref.skip_binder() {
3113                                 Some(TypeBinding {
3114                                     name: cx.tcx.associated_item(proj.projection_ty.item_def_id)
3115                                                 .ident.name.clean(cx),
3116                                     ty: proj.ty.clean(cx),
3117                                 })
3118                             } else {
3119                                 None
3120                             }
3121                         } else {
3122                             None
3123                         }
3124                     ).collect();
3125
3126                     Some((trait_ref.skip_binder(), bounds).clean(cx))
3127                 }).collect::<Vec<_>>();
3128                 bounds.extend(regions);
3129                 if !has_sized && !bounds.is_empty() {
3130                     bounds.insert(0, GenericBound::maybe_sized(cx));
3131                 }
3132                 ImplTrait(bounds)
3133             }
3134
3135             ty::Closure(..) | ty::Generator(..) => Tuple(vec![]), // FIXME(pcwalton)
3136
3137             ty::Bound(..) => panic!("Bound"),
3138             ty::Placeholder(..) => panic!("Placeholder"),
3139             ty::UnnormalizedProjection(..) => panic!("UnnormalizedProjection"),
3140             ty::GeneratorWitness(..) => panic!("GeneratorWitness"),
3141             ty::Infer(..) => panic!("Infer"),
3142             ty::Error => panic!("Error"),
3143         }
3144     }
3145 }
3146
3147 impl<'tcx> Clean<Constant> for ty::Const<'tcx> {
3148     fn clean(&self, cx: &DocContext<'_>) -> Constant {
3149         Constant {
3150             type_: self.ty.clean(cx),
3151             expr: format!("{:?}", self.val), // FIXME(const_generics)
3152         }
3153     }
3154 }
3155
3156 impl Clean<Item> for hir::StructField {
3157     fn clean(&self, cx: &DocContext<'_>) -> Item {
3158         let local_did = cx.tcx.hir().local_def_id_from_hir_id(self.hir_id);
3159
3160         Item {
3161             name: Some(self.ident.name).clean(cx),
3162             attrs: self.attrs.clean(cx),
3163             source: self.span.clean(cx),
3164             visibility: self.vis.clean(cx),
3165             stability: get_stability(cx, local_did),
3166             deprecation: get_deprecation(cx, local_did),
3167             def_id: local_did,
3168             inner: StructFieldItem(self.ty.clean(cx)),
3169         }
3170     }
3171 }
3172
3173 impl<'tcx> Clean<Item> for ty::FieldDef {
3174     fn clean(&self, cx: &DocContext<'_>) -> Item {
3175         Item {
3176             name: Some(self.ident.name).clean(cx),
3177             attrs: cx.tcx.get_attrs(self.did).clean(cx),
3178             source: cx.tcx.def_span(self.did).clean(cx),
3179             visibility: self.vis.clean(cx),
3180             stability: get_stability(cx, self.did),
3181             deprecation: get_deprecation(cx, self.did),
3182             def_id: self.did,
3183             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
3184         }
3185     }
3186 }
3187
3188 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug)]
3189 pub enum Visibility {
3190     Public,
3191     Inherited,
3192     Crate,
3193     Restricted(DefId, Path),
3194 }
3195
3196 impl Clean<Option<Visibility>> for hir::Visibility {
3197     fn clean(&self, cx: &DocContext<'_>) -> Option<Visibility> {
3198         Some(match self.node {
3199             hir::VisibilityKind::Public => Visibility::Public,
3200             hir::VisibilityKind::Inherited => Visibility::Inherited,
3201             hir::VisibilityKind::Crate(_) => Visibility::Crate,
3202             hir::VisibilityKind::Restricted { ref path, .. } => {
3203                 let path = path.clean(cx);
3204                 let did = register_res(cx, path.res);
3205                 Visibility::Restricted(did, path)
3206             }
3207         })
3208     }
3209 }
3210
3211 impl Clean<Option<Visibility>> for ty::Visibility {
3212     fn clean(&self, _: &DocContext<'_>) -> Option<Visibility> {
3213         Some(if *self == ty::Visibility::Public { Public } else { Inherited })
3214     }
3215 }
3216
3217 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3218 pub struct Struct {
3219     pub struct_type: doctree::StructType,
3220     pub generics: Generics,
3221     pub fields: Vec<Item>,
3222     pub fields_stripped: bool,
3223 }
3224
3225 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3226 pub struct Union {
3227     pub struct_type: doctree::StructType,
3228     pub generics: Generics,
3229     pub fields: Vec<Item>,
3230     pub fields_stripped: bool,
3231 }
3232
3233 impl Clean<Item> for doctree::Struct {
3234     fn clean(&self, cx: &DocContext<'_>) -> Item {
3235         Item {
3236             name: Some(self.name.clean(cx)),
3237             attrs: self.attrs.clean(cx),
3238             source: self.whence.clean(cx),
3239             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3240             visibility: self.vis.clean(cx),
3241             stability: self.stab.clean(cx),
3242             deprecation: self.depr.clean(cx),
3243             inner: StructItem(Struct {
3244                 struct_type: self.struct_type,
3245                 generics: self.generics.clean(cx),
3246                 fields: self.fields.clean(cx),
3247                 fields_stripped: false,
3248             }),
3249         }
3250     }
3251 }
3252
3253 impl Clean<Item> for doctree::Union {
3254     fn clean(&self, cx: &DocContext<'_>) -> Item {
3255         Item {
3256             name: Some(self.name.clean(cx)),
3257             attrs: self.attrs.clean(cx),
3258             source: self.whence.clean(cx),
3259             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3260             visibility: self.vis.clean(cx),
3261             stability: self.stab.clean(cx),
3262             deprecation: self.depr.clean(cx),
3263             inner: UnionItem(Union {
3264                 struct_type: self.struct_type,
3265                 generics: self.generics.clean(cx),
3266                 fields: self.fields.clean(cx),
3267                 fields_stripped: false,
3268             }),
3269         }
3270     }
3271 }
3272
3273 /// This is a more limited form of the standard Struct, different in that
3274 /// it lacks the things most items have (name, id, parameterization). Found
3275 /// only as a variant in an enum.
3276 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3277 pub struct VariantStruct {
3278     pub struct_type: doctree::StructType,
3279     pub fields: Vec<Item>,
3280     pub fields_stripped: bool,
3281 }
3282
3283 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
3284     fn clean(&self, cx: &DocContext<'_>) -> VariantStruct {
3285         VariantStruct {
3286             struct_type: doctree::struct_type_from_def(self),
3287             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
3288             fields_stripped: false,
3289         }
3290     }
3291 }
3292
3293 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3294 pub struct Enum {
3295     pub variants: IndexVec<VariantIdx, Item>,
3296     pub generics: Generics,
3297     pub variants_stripped: bool,
3298 }
3299
3300 impl Clean<Item> for doctree::Enum {
3301     fn clean(&self, cx: &DocContext<'_>) -> Item {
3302         Item {
3303             name: Some(self.name.clean(cx)),
3304             attrs: self.attrs.clean(cx),
3305             source: self.whence.clean(cx),
3306             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3307             visibility: self.vis.clean(cx),
3308             stability: self.stab.clean(cx),
3309             deprecation: self.depr.clean(cx),
3310             inner: EnumItem(Enum {
3311                 variants: self.variants.iter().map(|v| v.clean(cx)).collect(),
3312                 generics: self.generics.clean(cx),
3313                 variants_stripped: false,
3314             }),
3315         }
3316     }
3317 }
3318
3319 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3320 pub struct Variant {
3321     pub kind: VariantKind,
3322 }
3323
3324 impl Clean<Item> for doctree::Variant {
3325     fn clean(&self, cx: &DocContext<'_>) -> Item {
3326         Item {
3327             name: Some(self.name.clean(cx)),
3328             attrs: self.attrs.clean(cx),
3329             source: self.whence.clean(cx),
3330             visibility: None,
3331             stability: self.stab.clean(cx),
3332             deprecation: self.depr.clean(cx),
3333             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3334             inner: VariantItem(Variant {
3335                 kind: self.def.clean(cx),
3336             }),
3337         }
3338     }
3339 }
3340
3341 impl<'tcx> Clean<Item> for ty::VariantDef {
3342     fn clean(&self, cx: &DocContext<'_>) -> Item {
3343         let kind = match self.ctor_kind {
3344             CtorKind::Const => VariantKind::CLike,
3345             CtorKind::Fn => {
3346                 VariantKind::Tuple(
3347                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
3348                 )
3349             }
3350             CtorKind::Fictive => {
3351                 VariantKind::Struct(VariantStruct {
3352                     struct_type: doctree::Plain,
3353                     fields_stripped: false,
3354                     fields: self.fields.iter().map(|field| {
3355                         Item {
3356                             source: cx.tcx.def_span(field.did).clean(cx),
3357                             name: Some(field.ident.name.clean(cx)),
3358                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
3359                             visibility: field.vis.clean(cx),
3360                             def_id: field.did,
3361                             stability: get_stability(cx, field.did),
3362                             deprecation: get_deprecation(cx, field.did),
3363                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
3364                         }
3365                     }).collect()
3366                 })
3367             }
3368         };
3369         Item {
3370             name: Some(self.ident.clean(cx)),
3371             attrs: inline::load_attrs(cx, self.def_id),
3372             source: cx.tcx.def_span(self.def_id).clean(cx),
3373             visibility: Some(Inherited),
3374             def_id: self.def_id,
3375             inner: VariantItem(Variant { kind }),
3376             stability: get_stability(cx, self.def_id),
3377             deprecation: get_deprecation(cx, self.def_id),
3378         }
3379     }
3380 }
3381
3382 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3383 pub enum VariantKind {
3384     CLike,
3385     Tuple(Vec<Type>),
3386     Struct(VariantStruct),
3387 }
3388
3389 impl Clean<VariantKind> for hir::VariantData {
3390     fn clean(&self, cx: &DocContext<'_>) -> VariantKind {
3391         match self {
3392             hir::VariantData::Struct(..) => VariantKind::Struct(self.clean(cx)),
3393             hir::VariantData::Tuple(..) =>
3394                 VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect()),
3395             hir::VariantData::Unit(..) => VariantKind::CLike,
3396         }
3397     }
3398 }
3399
3400 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3401 pub struct Span {
3402     pub filename: FileName,
3403     pub loline: usize,
3404     pub locol: usize,
3405     pub hiline: usize,
3406     pub hicol: usize,
3407 }
3408
3409 impl Span {
3410     pub fn empty() -> Span {
3411         Span {
3412             filename: FileName::Anon(0),
3413             loline: 0, locol: 0,
3414             hiline: 0, hicol: 0,
3415         }
3416     }
3417 }
3418
3419 impl Clean<Span> for syntax_pos::Span {
3420     fn clean(&self, cx: &DocContext<'_>) -> Span {
3421         if self.is_dummy() {
3422             return Span::empty();
3423         }
3424
3425         let cm = cx.sess().source_map();
3426         let filename = cm.span_to_filename(*self);
3427         let lo = cm.lookup_char_pos(self.lo());
3428         let hi = cm.lookup_char_pos(self.hi());
3429         Span {
3430             filename,
3431             loline: lo.line,
3432             locol: lo.col.to_usize(),
3433             hiline: hi.line,
3434             hicol: hi.col.to_usize(),
3435         }
3436     }
3437 }
3438
3439 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3440 pub struct Path {
3441     pub global: bool,
3442     pub res: Res,
3443     pub segments: Vec<PathSegment>,
3444 }
3445
3446 impl Path {
3447     pub fn last_name(&self) -> &str {
3448         self.segments.last().expect("segments were empty").name.as_str()
3449     }
3450 }
3451
3452 impl Clean<Path> for hir::Path {
3453     fn clean(&self, cx: &DocContext<'_>) -> Path {
3454         Path {
3455             global: self.is_global(),
3456             res: self.res,
3457             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
3458         }
3459     }
3460 }
3461
3462 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3463 pub enum GenericArg {
3464     Lifetime(Lifetime),
3465     Type(Type),
3466     Const(Constant),
3467 }
3468
3469 impl fmt::Display for GenericArg {
3470     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3471         match self {
3472             GenericArg::Lifetime(lt) => lt.fmt(f),
3473             GenericArg::Type(ty) => ty.fmt(f),
3474             GenericArg::Const(ct) => ct.fmt(f),
3475         }
3476     }
3477 }
3478
3479 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3480 pub enum GenericArgs {
3481     AngleBracketed {
3482         args: Vec<GenericArg>,
3483         bindings: Vec<TypeBinding>,
3484     },
3485     Parenthesized {
3486         inputs: Vec<Type>,
3487         output: Option<Type>,
3488     }
3489 }
3490
3491 impl Clean<GenericArgs> for hir::GenericArgs {
3492     fn clean(&self, cx: &DocContext<'_>) -> GenericArgs {
3493         if self.parenthesized {
3494             let output = self.bindings[0].ty.clean(cx);
3495             GenericArgs::Parenthesized {
3496                 inputs: self.inputs().clean(cx),
3497                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
3498             }
3499         } else {
3500             let elide_lifetimes = self.args.iter().all(|arg| match arg {
3501                 hir::GenericArg::Lifetime(lt) => lt.is_elided(),
3502                 _ => true,
3503             });
3504             GenericArgs::AngleBracketed {
3505                 args: self.args.iter().filter_map(|arg| match arg {
3506                     hir::GenericArg::Lifetime(lt) if !elide_lifetimes => {
3507                         Some(GenericArg::Lifetime(lt.clean(cx)))
3508                     }
3509                     hir::GenericArg::Lifetime(_) => None,
3510                     hir::GenericArg::Type(ty) => Some(GenericArg::Type(ty.clean(cx))),
3511                     hir::GenericArg::Const(ct) => Some(GenericArg::Const(ct.clean(cx))),
3512                 }).collect(),
3513                 bindings: self.bindings.clean(cx),
3514             }
3515         }
3516     }
3517 }
3518
3519 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3520 pub struct PathSegment {
3521     pub name: String,
3522     pub args: GenericArgs,
3523 }
3524
3525 impl Clean<PathSegment> for hir::PathSegment {
3526     fn clean(&self, cx: &DocContext<'_>) -> PathSegment {
3527         PathSegment {
3528             name: self.ident.name.clean(cx),
3529             args: self.with_generic_args(|generic_args| generic_args.clean(cx))
3530         }
3531     }
3532 }
3533
3534 fn strip_type(ty: Type) -> Type {
3535     match ty {
3536         Type::ResolvedPath { path, param_names, did, is_generic } => {
3537             Type::ResolvedPath { path: strip_path(&path), param_names, did, is_generic }
3538         }
3539         Type::Tuple(inner_tys) => {
3540             Type::Tuple(inner_tys.iter().map(|t| strip_type(t.clone())).collect())
3541         }
3542         Type::Slice(inner_ty) => Type::Slice(Box::new(strip_type(*inner_ty))),
3543         Type::Array(inner_ty, s) => Type::Array(Box::new(strip_type(*inner_ty)), s),
3544         Type::Unique(inner_ty) => Type::Unique(Box::new(strip_type(*inner_ty))),
3545         Type::RawPointer(m, inner_ty) => Type::RawPointer(m, Box::new(strip_type(*inner_ty))),
3546         Type::BorrowedRef { lifetime, mutability, type_ } => {
3547             Type::BorrowedRef { lifetime, mutability, type_: Box::new(strip_type(*type_)) }
3548         }
3549         Type::QPath { name, self_type, trait_ } => {
3550             Type::QPath {
3551                 name,
3552                 self_type: Box::new(strip_type(*self_type)), trait_: Box::new(strip_type(*trait_))
3553             }
3554         }
3555         _ => ty
3556     }
3557 }
3558
3559 fn strip_path(path: &Path) -> Path {
3560     let segments = path.segments.iter().map(|s| {
3561         PathSegment {
3562             name: s.name.clone(),
3563             args: GenericArgs::AngleBracketed {
3564                 args: vec![],
3565                 bindings: vec![],
3566             }
3567         }
3568     }).collect();
3569
3570     Path {
3571         global: path.global,
3572         res: path.res.clone(),
3573         segments,
3574     }
3575 }
3576
3577 fn qpath_to_string(p: &hir::QPath) -> String {
3578     let segments = match *p {
3579         hir::QPath::Resolved(_, ref path) => &path.segments,
3580         hir::QPath::TypeRelative(_, ref segment) => return segment.ident.to_string(),
3581     };
3582
3583     let mut s = String::new();
3584     for (i, seg) in segments.iter().enumerate() {
3585         if i > 0 {
3586             s.push_str("::");
3587         }
3588         if seg.ident.name != keywords::PathRoot.name() {
3589             s.push_str(&*seg.ident.as_str());
3590         }
3591     }
3592     s
3593 }
3594
3595 impl Clean<String> for Ident {
3596     #[inline]
3597     fn clean(&self, cx: &DocContext<'_>) -> String {
3598         self.name.clean(cx)
3599     }
3600 }
3601
3602 impl Clean<String> for ast::Name {
3603     #[inline]
3604     fn clean(&self, _: &DocContext<'_>) -> String {
3605         self.to_string()
3606     }
3607 }
3608
3609 impl Clean<String> for InternedString {
3610     #[inline]
3611     fn clean(&self, _: &DocContext<'_>) -> String {
3612         self.to_string()
3613     }
3614 }
3615
3616 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3617 pub struct Typedef {
3618     pub type_: Type,
3619     pub generics: Generics,
3620 }
3621
3622 impl Clean<Item> for doctree::Typedef {
3623     fn clean(&self, cx: &DocContext<'_>) -> Item {
3624         Item {
3625             name: Some(self.name.clean(cx)),
3626             attrs: self.attrs.clean(cx),
3627             source: self.whence.clean(cx),
3628             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3629             visibility: self.vis.clean(cx),
3630             stability: self.stab.clean(cx),
3631             deprecation: self.depr.clean(cx),
3632             inner: TypedefItem(Typedef {
3633                 type_: self.ty.clean(cx),
3634                 generics: self.gen.clean(cx),
3635             }, false),
3636         }
3637     }
3638 }
3639
3640 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3641 pub struct Existential {
3642     pub bounds: Vec<GenericBound>,
3643     pub generics: Generics,
3644 }
3645
3646 impl Clean<Item> for doctree::Existential {
3647     fn clean(&self, cx: &DocContext<'_>) -> Item {
3648         Item {
3649             name: Some(self.name.clean(cx)),
3650             attrs: self.attrs.clean(cx),
3651             source: self.whence.clean(cx),
3652             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3653             visibility: self.vis.clean(cx),
3654             stability: self.stab.clean(cx),
3655             deprecation: self.depr.clean(cx),
3656             inner: ExistentialItem(Existential {
3657                 bounds: self.exist_ty.bounds.clean(cx),
3658                 generics: self.exist_ty.generics.clean(cx),
3659             }, false),
3660         }
3661     }
3662 }
3663
3664 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3665 pub struct BareFunctionDecl {
3666     pub unsafety: hir::Unsafety,
3667     pub generic_params: Vec<GenericParamDef>,
3668     pub decl: FnDecl,
3669     pub abi: Abi,
3670 }
3671
3672 impl Clean<BareFunctionDecl> for hir::BareFnTy {
3673     fn clean(&self, cx: &DocContext<'_>) -> BareFunctionDecl {
3674         let (generic_params, decl) = enter_impl_trait(cx, || {
3675             (self.generic_params.clean(cx), (&*self.decl, &self.arg_names[..]).clean(cx))
3676         });
3677         BareFunctionDecl {
3678             unsafety: self.unsafety,
3679             abi: self.abi,
3680             decl,
3681             generic_params,
3682         }
3683     }
3684 }
3685
3686 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3687 pub struct Static {
3688     pub type_: Type,
3689     pub mutability: Mutability,
3690     /// It's useful to have the value of a static documented, but I have no
3691     /// desire to represent expressions (that'd basically be all of the AST,
3692     /// which is huge!). So, have a string.
3693     pub expr: String,
3694 }
3695
3696 impl Clean<Item> for doctree::Static {
3697     fn clean(&self, cx: &DocContext<'_>) -> Item {
3698         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
3699         Item {
3700             name: Some(self.name.clean(cx)),
3701             attrs: self.attrs.clean(cx),
3702             source: self.whence.clean(cx),
3703             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3704             visibility: self.vis.clean(cx),
3705             stability: self.stab.clean(cx),
3706             deprecation: self.depr.clean(cx),
3707             inner: StaticItem(Static {
3708                 type_: self.type_.clean(cx),
3709                 mutability: self.mutability.clean(cx),
3710                 expr: print_const_expr(cx, self.expr),
3711             }),
3712         }
3713     }
3714 }
3715
3716 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
3717 pub struct Constant {
3718     pub type_: Type,
3719     pub expr: String,
3720 }
3721
3722 impl Clean<Item> for doctree::Constant {
3723     fn clean(&self, cx: &DocContext<'_>) -> Item {
3724         Item {
3725             name: Some(self.name.clean(cx)),
3726             attrs: self.attrs.clean(cx),
3727             source: self.whence.clean(cx),
3728             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3729             visibility: self.vis.clean(cx),
3730             stability: self.stab.clean(cx),
3731             deprecation: self.depr.clean(cx),
3732             inner: ConstantItem(Constant {
3733                 type_: self.type_.clean(cx),
3734                 expr: print_const_expr(cx, self.expr),
3735             }),
3736         }
3737     }
3738 }
3739
3740 #[derive(Debug, Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Hash)]
3741 pub enum Mutability {
3742     Mutable,
3743     Immutable,
3744 }
3745
3746 impl Clean<Mutability> for hir::Mutability {
3747     fn clean(&self, _: &DocContext<'_>) -> Mutability {
3748         match self {
3749             &hir::MutMutable => Mutable,
3750             &hir::MutImmutable => Immutable,
3751         }
3752     }
3753 }
3754
3755 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Debug, Hash)]
3756 pub enum ImplPolarity {
3757     Positive,
3758     Negative,
3759 }
3760
3761 impl Clean<ImplPolarity> for hir::ImplPolarity {
3762     fn clean(&self, _: &DocContext<'_>) -> ImplPolarity {
3763         match self {
3764             &hir::ImplPolarity::Positive => ImplPolarity::Positive,
3765             &hir::ImplPolarity::Negative => ImplPolarity::Negative,
3766         }
3767     }
3768 }
3769
3770 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3771 pub struct Impl {
3772     pub unsafety: hir::Unsafety,
3773     pub generics: Generics,
3774     pub provided_trait_methods: FxHashSet<String>,
3775     pub trait_: Option<Type>,
3776     pub for_: Type,
3777     pub items: Vec<Item>,
3778     pub polarity: Option<ImplPolarity>,
3779     pub synthetic: bool,
3780     pub blanket_impl: Option<Type>,
3781 }
3782
3783 pub fn get_auto_trait_and_blanket_impls(
3784     cx: &DocContext<'tcx>,
3785     ty: Ty<'tcx>,
3786     param_env_def_id: DefId,
3787 ) -> impl Iterator<Item = Item> {
3788     AutoTraitFinder::new(cx).get_auto_trait_impls(ty, param_env_def_id).into_iter()
3789         .chain(BlanketImplFinder::new(cx).get_blanket_impls(ty, param_env_def_id))
3790 }
3791
3792 impl Clean<Vec<Item>> for doctree::Impl {
3793     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3794         let mut ret = Vec::new();
3795         let trait_ = self.trait_.clean(cx);
3796         let items = self.items.clean(cx);
3797
3798         // If this impl block is an implementation of the Deref trait, then we
3799         // need to try inlining the target's inherent impl blocks as well.
3800         if trait_.def_id() == cx.tcx.lang_items().deref_trait() {
3801             build_deref_target_impls(cx, &items, &mut ret);
3802         }
3803
3804         let provided = trait_.def_id().map(|did| {
3805             cx.tcx.provided_trait_methods(did)
3806                   .into_iter()
3807                   .map(|meth| meth.ident.to_string())
3808                   .collect()
3809         }).unwrap_or_default();
3810
3811         ret.push(Item {
3812             name: None,
3813             attrs: self.attrs.clean(cx),
3814             source: self.whence.clean(cx),
3815             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
3816             visibility: self.vis.clean(cx),
3817             stability: self.stab.clean(cx),
3818             deprecation: self.depr.clean(cx),
3819             inner: ImplItem(Impl {
3820                 unsafety: self.unsafety,
3821                 generics: self.generics.clean(cx),
3822                 provided_trait_methods: provided,
3823                 trait_,
3824                 for_: self.for_.clean(cx),
3825                 items,
3826                 polarity: Some(self.polarity.clean(cx)),
3827                 synthetic: false,
3828                 blanket_impl: None,
3829             })
3830         });
3831         ret
3832     }
3833 }
3834
3835 fn build_deref_target_impls(cx: &DocContext<'_>,
3836                             items: &[Item],
3837                             ret: &mut Vec<Item>) {
3838     use self::PrimitiveType::*;
3839     let tcx = cx.tcx;
3840
3841     for item in items {
3842         let target = match item.inner {
3843             TypedefItem(ref t, true) => &t.type_,
3844             _ => continue,
3845         };
3846         let primitive = match *target {
3847             ResolvedPath { did, .. } if did.is_local() => continue,
3848             ResolvedPath { did, .. } => {
3849                 ret.extend(inline::build_impls(cx, did));
3850                 continue
3851             }
3852             _ => match target.primitive_type() {
3853                 Some(prim) => prim,
3854                 None => continue,
3855             }
3856         };
3857         let did = match primitive {
3858             Isize => tcx.lang_items().isize_impl(),
3859             I8 => tcx.lang_items().i8_impl(),
3860             I16 => tcx.lang_items().i16_impl(),
3861             I32 => tcx.lang_items().i32_impl(),
3862             I64 => tcx.lang_items().i64_impl(),
3863             I128 => tcx.lang_items().i128_impl(),
3864             Usize => tcx.lang_items().usize_impl(),
3865             U8 => tcx.lang_items().u8_impl(),
3866             U16 => tcx.lang_items().u16_impl(),
3867             U32 => tcx.lang_items().u32_impl(),
3868             U64 => tcx.lang_items().u64_impl(),
3869             U128 => tcx.lang_items().u128_impl(),
3870             F32 => tcx.lang_items().f32_impl(),
3871             F64 => tcx.lang_items().f64_impl(),
3872             Char => tcx.lang_items().char_impl(),
3873             Bool => None,
3874             Str => tcx.lang_items().str_impl(),
3875             Slice => tcx.lang_items().slice_impl(),
3876             Array => tcx.lang_items().slice_impl(),
3877             Tuple => None,
3878             Unit => None,
3879             RawPointer => tcx.lang_items().const_ptr_impl(),
3880             Reference => None,
3881             Fn => None,
3882             Never => None,
3883             CVarArgs => tcx.lang_items().va_list(),
3884         };
3885         if let Some(did) = did {
3886             if !did.is_local() {
3887                 inline::build_impl(cx, did, ret);
3888             }
3889         }
3890     }
3891 }
3892
3893 impl Clean<Vec<Item>> for doctree::ExternCrate {
3894     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3895
3896         let please_inline = self.vis.node.is_pub() && self.attrs.iter().any(|a| {
3897             a.check_name(sym::doc) && match a.meta_item_list() {
3898                 Some(l) => attr::list_contains_name(&l, sym::inline),
3899                 None => false,
3900             }
3901         });
3902
3903         if please_inline {
3904             let mut visited = FxHashSet::default();
3905
3906             let res = Res::Def(
3907                 DefKind::Mod,
3908                 DefId {
3909                     krate: self.cnum,
3910                     index: CRATE_DEF_INDEX,
3911                 },
3912             );
3913
3914             if let Some(items) = inline::try_inline(cx, res, self.name, &mut visited) {
3915                 return items;
3916             }
3917         }
3918
3919         vec![Item {
3920             name: None,
3921             attrs: self.attrs.clean(cx),
3922             source: self.whence.clean(cx),
3923             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
3924             visibility: self.vis.clean(cx),
3925             stability: None,
3926             deprecation: None,
3927             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
3928         }]
3929     }
3930 }
3931
3932 impl Clean<Vec<Item>> for doctree::Import {
3933     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
3934         // We consider inlining the documentation of `pub use` statements, but we
3935         // forcefully don't inline if this is not public or if the
3936         // #[doc(no_inline)] attribute is present.
3937         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
3938         let mut denied = !self.vis.node.is_pub() || self.attrs.iter().any(|a| {
3939             a.check_name(sym::doc) && match a.meta_item_list() {
3940                 Some(l) => attr::list_contains_name(&l, sym::no_inline) ||
3941                            attr::list_contains_name(&l, sym::hidden),
3942                 None => false,
3943             }
3944         });
3945         // Also check whether imports were asked to be inlined, in case we're trying to re-export a
3946         // crate in Rust 2018+
3947         let please_inline = self.attrs.lists(sym::doc).has_word(sym::inline);
3948         let path = self.path.clean(cx);
3949         let inner = if self.glob {
3950             if !denied {
3951                 let mut visited = FxHashSet::default();
3952                 if let Some(items) = inline::try_inline_glob(cx, path.res, &mut visited) {
3953                     return items;
3954                 }
3955             }
3956
3957             Import::Glob(resolve_use_source(cx, path))
3958         } else {
3959             let name = self.name;
3960             if !please_inline {
3961                 match path.res {
3962                     Res::Def(DefKind::Mod, did) => {
3963                         if !did.is_local() && did.index == CRATE_DEF_INDEX {
3964                             // if we're `pub use`ing an extern crate root, don't inline it unless we
3965                             // were specifically asked for it
3966                             denied = true;
3967                         }
3968                     }
3969                     _ => {}
3970                 }
3971             }
3972             if !denied {
3973                 let mut visited = FxHashSet::default();
3974                 if let Some(items) = inline::try_inline(cx, path.res, name, &mut visited) {
3975                     return items;
3976                 }
3977             }
3978             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
3979         };
3980
3981         vec![Item {
3982             name: None,
3983             attrs: self.attrs.clean(cx),
3984             source: self.whence.clean(cx),
3985             def_id: cx.tcx.hir().local_def_id(ast::CRATE_NODE_ID),
3986             visibility: self.vis.clean(cx),
3987             stability: None,
3988             deprecation: None,
3989             inner: ImportItem(inner)
3990         }]
3991     }
3992 }
3993
3994 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3995 pub enum Import {
3996     // use source as str;
3997     Simple(String, ImportSource),
3998     // use source::*;
3999     Glob(ImportSource)
4000 }
4001
4002 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4003 pub struct ImportSource {
4004     pub path: Path,
4005     pub did: Option<DefId>,
4006 }
4007
4008 impl Clean<Vec<Item>> for hir::ForeignMod {
4009     fn clean(&self, cx: &DocContext<'_>) -> Vec<Item> {
4010         let mut items = self.items.clean(cx);
4011         for item in &mut items {
4012             if let ForeignFunctionItem(ref mut f) = item.inner {
4013                 f.header.abi = self.abi;
4014             }
4015         }
4016         items
4017     }
4018 }
4019
4020 impl Clean<Item> for hir::ForeignItem {
4021     fn clean(&self, cx: &DocContext<'_>) -> Item {
4022         let inner = match self.node {
4023             hir::ForeignItemKind::Fn(ref decl, ref names, ref generics) => {
4024                 let (generics, decl) = enter_impl_trait(cx, || {
4025                     (generics.clean(cx), (&**decl, &names[..]).clean(cx))
4026                 });
4027                 let (all_types, ret_types) = get_all_types(&generics, &decl, cx);
4028                 ForeignFunctionItem(Function {
4029                     decl,
4030                     generics,
4031                     header: hir::FnHeader {
4032                         unsafety: hir::Unsafety::Unsafe,
4033                         abi: Abi::Rust,
4034                         constness: hir::Constness::NotConst,
4035                         asyncness: hir::IsAsync::NotAsync,
4036                     },
4037                     all_types,
4038                     ret_types,
4039                 })
4040             }
4041             hir::ForeignItemKind::Static(ref ty, mutbl) => {
4042                 ForeignStaticItem(Static {
4043                     type_: ty.clean(cx),
4044                     mutability: mutbl.clean(cx),
4045                     expr: String::new(),
4046                 })
4047             }
4048             hir::ForeignItemKind::Type => {
4049                 ForeignTypeItem
4050             }
4051         };
4052
4053         let local_did = cx.tcx.hir().local_def_id_from_hir_id(self.hir_id);
4054
4055         Item {
4056             name: Some(self.ident.clean(cx)),
4057             attrs: self.attrs.clean(cx),
4058             source: self.span.clean(cx),
4059             def_id: local_did,
4060             visibility: self.vis.clean(cx),
4061             stability: get_stability(cx, local_did),
4062             deprecation: get_deprecation(cx, local_did),
4063             inner,
4064         }
4065     }
4066 }
4067
4068 // Utilities
4069
4070 pub trait ToSource {
4071     fn to_src(&self, cx: &DocContext<'_>) -> String;
4072 }
4073
4074 impl ToSource for syntax_pos::Span {
4075     fn to_src(&self, cx: &DocContext<'_>) -> String {
4076         debug!("converting span {:?} to snippet", self.clean(cx));
4077         let sn = match cx.sess().source_map().span_to_snippet(*self) {
4078             Ok(x) => x,
4079             Err(_) => String::new()
4080         };
4081         debug!("got snippet {}", sn);
4082         sn
4083     }
4084 }
4085
4086 fn name_from_pat(p: &hir::Pat) -> String {
4087     use rustc::hir::*;
4088     debug!("Trying to get a name from pattern: {:?}", p);
4089
4090     match p.node {
4091         PatKind::Wild => "_".to_string(),
4092         PatKind::Binding(_, _, ident, _) => ident.to_string(),
4093         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
4094         PatKind::Struct(ref name, ref fields, etc) => {
4095             format!("{} {{ {}{} }}", qpath_to_string(name),
4096                 fields.iter().map(|&Spanned { node: ref fp, .. }|
4097                                   format!("{}: {}", fp.ident, name_from_pat(&*fp.pat)))
4098                              .collect::<Vec<String>>().join(", "),
4099                 if etc { ", .." } else { "" }
4100             )
4101         }
4102         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
4103                                             .collect::<Vec<String>>().join(", ")),
4104         PatKind::Box(ref p) => name_from_pat(&**p),
4105         PatKind::Ref(ref p, _) => name_from_pat(&**p),
4106         PatKind::Lit(..) => {
4107             warn!("tried to get argument name from PatKind::Lit, \
4108                   which is silly in function arguments");
4109             "()".to_string()
4110         },
4111         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
4112                               which is not allowed in function arguments"),
4113         PatKind::Slice(ref begin, ref mid, ref end) => {
4114             let begin = begin.iter().map(|p| name_from_pat(&**p));
4115             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
4116             let end = end.iter().map(|p| name_from_pat(&**p));
4117             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
4118         },
4119     }
4120 }
4121
4122 fn print_const(cx: &DocContext<'_>, n: ty::Const<'_>) -> String {
4123     match n.val {
4124         ConstValue::Unevaluated(def_id, _) => {
4125             if let Some(hir_id) = cx.tcx.hir().as_local_hir_id(def_id) {
4126                 print_const_expr(cx, cx.tcx.hir().body_owned_by(hir_id))
4127             } else {
4128                 inline::print_inlined_const(cx, def_id)
4129             }
4130         },
4131         _ => {
4132             let mut s = String::new();
4133             ::rustc::mir::fmt_const_val(&mut s, n).expect("fmt_const_val failed");
4134             // array lengths are obviously usize
4135             if s.ends_with("usize") {
4136                 let n = s.len() - "usize".len();
4137                 s.truncate(n);
4138             }
4139             s
4140         },
4141     }
4142 }
4143
4144 fn print_const_expr(cx: &DocContext<'_>, body: hir::BodyId) -> String {
4145     cx.tcx.hir().hir_to_pretty_string(body.hir_id)
4146 }
4147
4148 /// Given a type Path, resolve it to a Type using the TyCtxt
4149 fn resolve_type(cx: &DocContext<'_>,
4150                 path: Path,
4151                 id: hir::HirId) -> Type {
4152     if id == hir::DUMMY_HIR_ID {
4153         debug!("resolve_type({:?})", path);
4154     } else {
4155         debug!("resolve_type({:?},{:?})", path, id);
4156     }
4157
4158     let is_generic = match path.res {
4159         Res::PrimTy(p) => match p {
4160             hir::Str => return Primitive(PrimitiveType::Str),
4161             hir::Bool => return Primitive(PrimitiveType::Bool),
4162             hir::Char => return Primitive(PrimitiveType::Char),
4163             hir::Int(int_ty) => return Primitive(int_ty.into()),
4164             hir::Uint(uint_ty) => return Primitive(uint_ty.into()),
4165             hir::Float(float_ty) => return Primitive(float_ty.into()),
4166         },
4167         Res::SelfTy(..) if path.segments.len() == 1 => {
4168             return Generic(keywords::SelfUpper.name().to_string());
4169         }
4170         Res::Def(DefKind::TyParam, _) if path.segments.len() == 1 => {
4171             return Generic(format!("{:#}", path));
4172         }
4173         Res::SelfTy(..)
4174         | Res::Def(DefKind::TyParam, _)
4175         | Res::Def(DefKind::AssociatedTy, _) => true,
4176         _ => false,
4177     };
4178     let did = register_res(&*cx, path.res);
4179     ResolvedPath { path: path, param_names: None, did: did, is_generic: is_generic }
4180 }
4181
4182 pub fn register_res(cx: &DocContext<'_>, res: Res) -> DefId {
4183     debug!("register_res({:?})", res);
4184
4185     let (did, kind) = match res {
4186         Res::Def(DefKind::Fn, i) => (i, TypeKind::Function),
4187         Res::Def(DefKind::TyAlias, i) => (i, TypeKind::Typedef),
4188         Res::Def(DefKind::Enum, i) => (i, TypeKind::Enum),
4189         Res::Def(DefKind::Trait, i) => (i, TypeKind::Trait),
4190         Res::Def(DefKind::Struct, i) => (i, TypeKind::Struct),
4191         Res::Def(DefKind::Union, i) => (i, TypeKind::Union),
4192         Res::Def(DefKind::Mod, i) => (i, TypeKind::Module),
4193         Res::Def(DefKind::ForeignTy, i) => (i, TypeKind::Foreign),
4194         Res::Def(DefKind::Const, i) => (i, TypeKind::Const),
4195         Res::Def(DefKind::Static, i) => (i, TypeKind::Static),
4196         Res::Def(DefKind::Variant, i) => (cx.tcx.parent(i).expect("cannot get parent def id"),
4197                             TypeKind::Enum),
4198         Res::Def(DefKind::Macro(mac_kind), i) => match mac_kind {
4199             MacroKind::Bang => (i, TypeKind::Macro),
4200             MacroKind::Attr => (i, TypeKind::Attr),
4201             MacroKind::Derive => (i, TypeKind::Derive),
4202             MacroKind::ProcMacroStub => unreachable!(),
4203         },
4204         Res::Def(DefKind::TraitAlias, i) => (i, TypeKind::TraitAlias),
4205         Res::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
4206         Res::SelfTy(_, Some(impl_def_id)) => return impl_def_id,
4207         _ => return res.def_id()
4208     };
4209     if did.is_local() { return did }
4210     inline::record_extern_fqn(cx, did, kind);
4211     if let TypeKind::Trait = kind {
4212         inline::record_extern_trait(cx, did);
4213     }
4214     did
4215 }
4216
4217 fn resolve_use_source(cx: &DocContext<'_>, path: Path) -> ImportSource {
4218     ImportSource {
4219         did: if path.res.opt_def_id().is_none() {
4220             None
4221         } else {
4222             Some(register_res(cx, path.res))
4223         },
4224         path,
4225     }
4226 }
4227
4228 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4229 pub struct Macro {
4230     pub source: String,
4231     pub imported_from: Option<String>,
4232 }
4233
4234 impl Clean<Item> for doctree::Macro {
4235     fn clean(&self, cx: &DocContext<'_>) -> Item {
4236         let name = self.name.clean(cx);
4237         Item {
4238             name: Some(name.clone()),
4239             attrs: self.attrs.clean(cx),
4240             source: self.whence.clean(cx),
4241             visibility: Some(Public),
4242             stability: self.stab.clean(cx),
4243             deprecation: self.depr.clean(cx),
4244             def_id: self.def_id,
4245             inner: MacroItem(Macro {
4246                 source: format!("macro_rules! {} {{\n{}}}",
4247                                 name,
4248                                 self.matchers.iter().map(|span| {
4249                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
4250                                 }).collect::<String>()),
4251                 imported_from: self.imported_from.clean(cx),
4252             }),
4253         }
4254     }
4255 }
4256
4257 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4258 pub struct ProcMacro {
4259     pub kind: MacroKind,
4260     pub helpers: Vec<String>,
4261 }
4262
4263 impl Clean<Item> for doctree::ProcMacro {
4264     fn clean(&self, cx: &DocContext<'_>) -> Item {
4265         Item {
4266             name: Some(self.name.clean(cx)),
4267             attrs: self.attrs.clean(cx),
4268             source: self.whence.clean(cx),
4269             visibility: Some(Public),
4270             stability: self.stab.clean(cx),
4271             deprecation: self.depr.clean(cx),
4272             def_id: cx.tcx.hir().local_def_id_from_hir_id(self.id),
4273             inner: ProcMacroItem(ProcMacro {
4274                 kind: self.kind,
4275                 helpers: self.helpers.clean(cx),
4276             }),
4277         }
4278     }
4279 }
4280
4281 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4282 pub struct Stability {
4283     pub level: stability::StabilityLevel,
4284     pub feature: Option<String>,
4285     pub since: String,
4286     pub deprecation: Option<Deprecation>,
4287     pub unstable_reason: Option<String>,
4288     pub issue: Option<u32>,
4289 }
4290
4291 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4292 pub struct Deprecation {
4293     pub since: Option<String>,
4294     pub note: Option<String>,
4295 }
4296
4297 impl Clean<Stability> for attr::Stability {
4298     fn clean(&self, _: &DocContext<'_>) -> Stability {
4299         Stability {
4300             level: stability::StabilityLevel::from_attr_level(&self.level),
4301             feature: Some(self.feature.to_string()).filter(|f| !f.is_empty()),
4302             since: match self.level {
4303                 attr::Stable {ref since} => since.to_string(),
4304                 _ => String::new(),
4305             },
4306             deprecation: self.rustc_depr.as_ref().map(|d| {
4307                 Deprecation {
4308                     note: Some(d.reason.to_string()).filter(|r| !r.is_empty()),
4309                     since: Some(d.since.to_string()).filter(|d| !d.is_empty()),
4310                 }
4311             }),
4312             unstable_reason: match self.level {
4313                 attr::Unstable { reason: Some(ref reason), .. } => Some(reason.to_string()),
4314                 _ => None,
4315             },
4316             issue: match self.level {
4317                 attr::Unstable {issue, ..} => Some(issue),
4318                 _ => None,
4319             }
4320         }
4321     }
4322 }
4323
4324 impl<'a> Clean<Stability> for &'a attr::Stability {
4325     fn clean(&self, dc: &DocContext<'_>) -> Stability {
4326         (**self).clean(dc)
4327     }
4328 }
4329
4330 impl Clean<Deprecation> for attr::Deprecation {
4331     fn clean(&self, _: &DocContext<'_>) -> Deprecation {
4332         Deprecation {
4333             since: self.since.map(|s| s.to_string()).filter(|s| !s.is_empty()),
4334             note: self.note.map(|n| n.to_string()).filter(|n| !n.is_empty()),
4335         }
4336     }
4337 }
4338
4339 /// An equality constraint on an associated type, e.g., `A = Bar` in `Foo<A = Bar>`
4340 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug, Hash)]
4341 pub struct TypeBinding {
4342     pub name: String,
4343     pub ty: Type
4344 }
4345
4346 impl Clean<TypeBinding> for hir::TypeBinding {
4347     fn clean(&self, cx: &DocContext<'_>) -> TypeBinding {
4348         TypeBinding {
4349             name: self.ident.name.clean(cx),
4350             ty: self.ty.clean(cx)
4351         }
4352     }
4353 }
4354
4355 pub fn def_id_to_path(
4356     cx: &DocContext<'_>,
4357     did: DefId,
4358     name: Option<String>
4359 ) -> Vec<String> {
4360     let crate_name = name.unwrap_or_else(|| cx.tcx.crate_name(did.krate).to_string());
4361     let relative = cx.tcx.def_path(did).data.into_iter().filter_map(|elem| {
4362         // extern blocks have an empty name
4363         let s = elem.data.to_string();
4364         if !s.is_empty() {
4365             Some(s)
4366         } else {
4367             None
4368         }
4369     });
4370     once(crate_name).chain(relative).collect()
4371 }
4372
4373 pub fn enter_impl_trait<F, R>(cx: &DocContext<'_>, f: F) -> R
4374 where
4375     F: FnOnce() -> R,
4376 {
4377     let old_bounds = mem::replace(&mut *cx.impl_trait_bounds.borrow_mut(), Default::default());
4378     let r = f();
4379     assert!(cx.impl_trait_bounds.borrow().is_empty());
4380     *cx.impl_trait_bounds.borrow_mut() = old_bounds;
4381     r
4382 }
4383
4384 // Start of code copied from rust-clippy
4385
4386 pub fn path_to_def_local(tcx: TyCtxt<'_, '_, '_>, path: &[Symbol]) -> Option<DefId> {
4387     let krate = tcx.hir().krate();
4388     let mut items = krate.module.item_ids.clone();
4389     let mut path_it = path.iter().peekable();
4390
4391     loop {
4392         let segment = path_it.next()?;
4393
4394         for item_id in mem::replace(&mut items, HirVec::new()).iter() {
4395             let item = tcx.hir().expect_item_by_hir_id(item_id.id);
4396             if item.ident.name == *segment {
4397                 if path_it.peek().is_none() {
4398                     return Some(tcx.hir().local_def_id_from_hir_id(item_id.id))
4399                 }
4400
4401                 items = match &item.node {
4402                     &hir::ItemKind::Mod(ref m) => m.item_ids.clone(),
4403                     _ => panic!("Unexpected item {:?} in path {:?} path")
4404                 };
4405                 break;
4406             }
4407         }
4408     }
4409 }
4410
4411 pub fn path_to_def(tcx: TyCtxt<'_, '_, '_>, path: &[Symbol]) -> Option<DefId> {
4412     let crates = tcx.crates();
4413
4414     let krate = crates
4415         .iter()
4416         .find(|&&krate| tcx.crate_name(krate) == path[0]);
4417
4418     if let Some(krate) = krate {
4419         let krate = DefId {
4420             krate: *krate,
4421             index: CRATE_DEF_INDEX,
4422         };
4423         let mut items = tcx.item_children(krate);
4424         let mut path_it = path.iter().skip(1).peekable();
4425
4426         loop {
4427             let segment = path_it.next()?;
4428
4429             for item in mem::replace(&mut items, Lrc::new(vec![])).iter() {
4430                 if item.ident.name == *segment {
4431                     if path_it.peek().is_none() {
4432                         return match item.res {
4433                             def::Res::Def(DefKind::Trait, did) => Some(did),
4434                             _ => None,
4435                         }
4436                     }
4437
4438                     items = tcx.item_children(item.res.def_id());
4439                     break;
4440                 }
4441             }
4442         }
4443     } else {
4444         None
4445     }
4446 }
4447
4448 // End of code copied from rust-clippy
4449
4450 #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
4451 enum RegionTarget<'tcx> {
4452     Region(Region<'tcx>),
4453     RegionVid(RegionVid)
4454 }
4455
4456 #[derive(Default, Debug, Clone)]
4457 struct RegionDeps<'tcx> {
4458     larger: FxHashSet<RegionTarget<'tcx>>,
4459     smaller: FxHashSet<RegionTarget<'tcx>>
4460 }
4461
4462 #[derive(Eq, PartialEq, Hash, Debug)]
4463 enum SimpleBound {
4464     TraitBound(Vec<PathSegment>, Vec<SimpleBound>, Vec<GenericParamDef>, hir::TraitBoundModifier),
4465     Outlives(Lifetime),
4466 }
4467
4468 impl From<GenericBound> for SimpleBound {
4469     fn from(bound: GenericBound) -> Self {
4470         match bound.clone() {
4471             GenericBound::Outlives(l) => SimpleBound::Outlives(l),
4472             GenericBound::TraitBound(t, mod_) => match t.trait_ {
4473                 Type::ResolvedPath { path, param_names, .. } => {
4474                     SimpleBound::TraitBound(path.segments,
4475                                             param_names
4476                                                 .map_or_else(|| Vec::new(), |v| v.iter()
4477                                                         .map(|p| SimpleBound::from(p.clone()))
4478                                                         .collect()),
4479                                             t.generic_params,
4480                                             mod_)
4481                 }
4482                 _ => panic!("Unexpected bound {:?}", bound),
4483             }
4484         }
4485     }
4486 }