src/librustdoc/clean/mod.rs

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