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 use self::Type::*;
  15 pub use self::Mutability::*;
  16 pub use self::ItemEnum::*;
  17 pub use self::TyParamBound::*;
  18 pub use self::SelfTy::*;
  19 pub use self::FunctionRetTy::*;
  20 pub use self::Visibility::*;
  21
  22 use syntax::abi::Abi;
  23 use syntax::ast;
  24 use syntax::attr;
  25 use syntax::codemap::Spanned;
  26 use syntax::ptr::P;
  27 use syntax::symbol::keywords;
  28 use syntax_pos::{self, DUMMY_SP, Pos};
  29
  30 use rustc::middle::const_val::ConstVal;
  31 use rustc::middle::privacy::AccessLevels;
  32 use rustc::middle::resolve_lifetime as rl;
  33 use rustc::middle::lang_items;
  34 use rustc::hir::def::{Def, CtorKind};
  35 use rustc::hir::def_id::{CrateNum, DefId, CRATE_DEF_INDEX, LOCAL_CRATE};
  36 use rustc::traits::Reveal;
  37 use rustc::ty::subst::Substs;
  38 use rustc::ty::{self, Ty, AdtKind};
  39 use rustc::middle::stability;
  40 use rustc::util::nodemap::{FxHashMap, FxHashSet};
  41 use rustc_typeck::hir_ty_to_ty;
  42
  43 use rustc::hir;
  44
  45 use rustc_const_math::ConstInt;
  46 use std::{mem, slice, vec};
  47 use std::path::PathBuf;
  48 use std::rc::Rc;
  49 use std::sync::Arc;
  50 use std::u32;
  51
  52 use core::DocContext;
  53 use doctree;
  54 use visit_ast;
  55 use html::item_type::ItemType;
  56
  57 pub mod inline;
  58 pub mod cfg;
  59 mod simplify;
  60
  61 use self::cfg::Cfg;
  62
  63 // extract the stability index for a node from tcx, if possible
  64 fn get_stability(cx: &DocContext, def_id: DefId) -> Option<Stability> {
  65     cx.tcx.lookup_stability(def_id).clean(cx)
  66 }
  67
  68 fn get_deprecation(cx: &DocContext, def_id: DefId) -> Option<Deprecation> {
  69     cx.tcx.lookup_deprecation(def_id).clean(cx)
  70 }
  71
  72 pub trait Clean<T> {
  73     fn clean(&self, cx: &DocContext) -> T;
  74 }
  75
  76 impl<T: Clean<U>, U> Clean<Vec<U>> for [T] {
  77     fn clean(&self, cx: &DocContext) -> Vec<U> {
  78         self.iter().map(|x| x.clean(cx)).collect()
  79     }
  80 }
  81
  82 impl<T: Clean<U>, U> Clean<U> for P<T> {
  83     fn clean(&self, cx: &DocContext) -> U {
  84         (**self).clean(cx)
  85     }
  86 }
  87
  88 impl<T: Clean<U>, U> Clean<U> for Rc<T> {
  89     fn clean(&self, cx: &DocContext) -> U {
  90         (**self).clean(cx)
  91     }
  92 }
  93
  94 impl<T: Clean<U>, U> Clean<Option<U>> for Option<T> {
  95     fn clean(&self, cx: &DocContext) -> Option<U> {
  96         self.as_ref().map(|v| v.clean(cx))
  97     }
  98 }
  99
 100 impl<T, U> Clean<U> for ty::Binder<T> where T: Clean<U> {
 101     fn clean(&self, cx: &DocContext) -> U {
 102         self.0.clean(cx)
 103     }
 104 }
 105
 106 impl<T: Clean<U>, U> Clean<Vec<U>> for P<[T]> {
 107     fn clean(&self, cx: &DocContext) -> Vec<U> {
 108         self.iter().map(|x| x.clean(cx)).collect()
 109     }
 110 }
 111
 112 #[derive(Clone, Debug)]
 113 pub struct Crate {
 114     pub name: String,
 115     pub version: Option<String>,
 116     pub src: PathBuf,
 117     pub module: Option<Item>,
 118     pub externs: Vec<(CrateNum, ExternalCrate)>,
 119     pub primitives: Vec<(DefId, PrimitiveType, Attributes)>,
 120     pub access_levels: Arc<AccessLevels<DefId>>,
 121     // These are later on moved into `CACHEKEY`, leaving the map empty.
 122     // Only here so that they can be filtered through the rustdoc passes.
 123     pub external_traits: FxHashMap<DefId, Trait>,
 124     pub masked_crates: FxHashSet<CrateNum>,
 125 }
 126
 127 impl<'a, 'tcx> Clean<Crate> for visit_ast::RustdocVisitor<'a, 'tcx> {
 128     fn clean(&self, cx: &DocContext) -> Crate {
 129         use ::visit_lib::LibEmbargoVisitor;
 130
 131         {
 132             let mut r = cx.renderinfo.borrow_mut();
 133             r.deref_trait_did = cx.tcx.lang_items().deref_trait();
 134             r.deref_mut_trait_did = cx.tcx.lang_items().deref_mut_trait();
 135             r.owned_box_did = cx.tcx.lang_items().owned_box();
 136         }
 137
 138         let mut externs = Vec::new();
 139         for &cnum in cx.tcx.crates().iter() {
 140             externs.push((cnum, cnum.clean(cx)));
 141             // Analyze doc-reachability for extern items
 142             LibEmbargoVisitor::new(cx).visit_lib(cnum);
 143         }
 144         externs.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
 145
 146         // Clean the crate, translating the entire libsyntax AST to one that is
 147         // understood by rustdoc.
 148         let mut module = self.module.clean(cx);
 149         let mut masked_crates = FxHashSet();
 150
 151         match module.inner {
 152             ModuleItem(ref module) => {
 153                 for it in &module.items {
 154                     if it.is_extern_crate() && it.attrs.has_doc_masked() {
 155                         masked_crates.insert(it.def_id.krate);
 156                     }
 157                 }
 158             }
 159             _ => unreachable!(),
 160         }
 161
 162         let ExternalCrate { name, src, primitives, .. } = LOCAL_CRATE.clean(cx);
 163         {
 164             let m = match module.inner {
 165                 ModuleItem(ref mut m) => m,
 166                 _ => unreachable!(),
 167             };
 168             m.items.extend(primitives.iter().map(|&(def_id, prim, ref attrs)| {
 169                 Item {
 170                     source: Span::empty(),
 171                     name: Some(prim.to_url_str().to_string()),
 172                     attrs: attrs.clone(),
 173                     visibility: Some(Public),
 174                     stability: get_stability(cx, def_id),
 175                     deprecation: get_deprecation(cx, def_id),
 176                     def_id,
 177                     inner: PrimitiveItem(prim),
 178                 }
 179             }));
 180         }
 181
 182         let mut access_levels = cx.access_levels.borrow_mut();
 183         let mut external_traits = cx.external_traits.borrow_mut();
 184
 185         Crate {
 186             name,
 187             version: None,
 188             src,
 189             module: Some(module),
 190             externs,
 191             primitives,
 192             access_levels: Arc::new(mem::replace(&mut access_levels, Default::default())),
 193             external_traits: mem::replace(&mut external_traits, Default::default()),
 194             masked_crates,
 195         }
 196     }
 197 }
 198
 199 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
 200 pub struct ExternalCrate {
 201     pub name: String,
 202     pub src: PathBuf,
 203     pub attrs: Attributes,
 204     pub primitives: Vec<(DefId, PrimitiveType, Attributes)>,
 205 }
 206
 207 impl Clean<ExternalCrate> for CrateNum {
 208     fn clean(&self, cx: &DocContext) -> ExternalCrate {
 209         let root = DefId { krate: *self, index: CRATE_DEF_INDEX };
 210         let krate_span = cx.tcx.def_span(root);
 211         let krate_src = cx.sess().codemap().span_to_filename(krate_span);
 212
 213         // Collect all inner modules which are tagged as implementations of
 214         // primitives.
 215         //
 216         // Note that this loop only searches the top-level items of the crate,
 217         // and this is intentional. If we were to search the entire crate for an
 218         // item tagged with `#[doc(primitive)]` then we would also have to
 219         // search the entirety of external modules for items tagged
 220         // `#[doc(primitive)]`, which is a pretty inefficient process (decoding
 221         // all that metadata unconditionally).
 222         //
 223         // In order to keep the metadata load under control, the
 224         // `#[doc(primitive)]` feature is explicitly designed to only allow the
 225         // primitive tags to show up as the top level items in a crate.
 226         //
 227         // Also note that this does not attempt to deal with modules tagged
 228         // duplicately for the same primitive. This is handled later on when
 229         // rendering by delegating everything to a hash map.
 230         let as_primitive = |def: Def| {
 231             if let Def::Mod(def_id) = def {
 232                 let attrs = cx.tcx.get_attrs(def_id).clean(cx);
 233                 let mut prim = None;
 234                 for attr in attrs.lists("doc") {
 235                     if let Some(v) = attr.value_str() {
 236                         if attr.check_name("primitive") {
 237                             prim = PrimitiveType::from_str(&v.as_str());
 238                             if prim.is_some() {
 239                                 break;
 240                             }
 241                             // FIXME: should warn on unknown primitives?
 242                         }
 243                     }
 244                 }
 245                 return prim.map(|p| (def_id, p, attrs));
 246             }
 247             None
 248         };
 249         let primitives = if root.is_local() {
 250             cx.tcx.hir.krate().module.item_ids.iter().filter_map(|&id| {
 251                 let item = cx.tcx.hir.expect_item(id.id);
 252                 match item.node {
 253                     hir::ItemMod(_) => {
 254                         as_primitive(Def::Mod(cx.tcx.hir.local_def_id(id.id)))
 255                     }
 256                     hir::ItemUse(ref path, hir::UseKind::Single)
 257                     if item.vis == hir::Visibility::Public => {
 258                         as_primitive(path.def).map(|(_, prim, attrs)| {
 259                             // Pretend the primitive is local.
 260                             (cx.tcx.hir.local_def_id(id.id), prim, attrs)
 261                         })
 262                     }
 263                     _ => None
 264                 }
 265             }).collect()
 266         } else {
 267             cx.tcx.item_children(root).iter().map(|item| item.def)
 268               .filter_map(as_primitive).collect()
 269         };
 270
 271         ExternalCrate {
 272             name: cx.tcx.crate_name(*self).to_string(),
 273             src: PathBuf::from(krate_src),
 274             attrs: cx.tcx.get_attrs(root).clean(cx),
 275             primitives,
 276         }
 277     }
 278 }
 279
 280 /// Anything with a source location and set of attributes and, optionally, a
 281 /// name. That is, anything that can be documented. This doesn't correspond
 282 /// directly to the AST's concept of an item; it's a strict superset.
 283 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
 284 pub struct Item {
 285     /// Stringified span
 286     pub source: Span,
 287     /// Not everything has a name. E.g., impls
 288     pub name: Option<String>,
 289     pub attrs: Attributes,
 290     pub inner: ItemEnum,
 291     pub visibility: Option<Visibility>,
 292     pub def_id: DefId,
 293     pub stability: Option<Stability>,
 294     pub deprecation: Option<Deprecation>,
 295 }
 296
 297 impl Item {
 298     /// Finds the `doc` attribute as a NameValue and returns the corresponding
 299     /// value found.
 300     pub fn doc_value<'a>(&'a self) -> Option<&'a str> {
 301         self.attrs.doc_value()
 302     }
 303     pub fn is_crate(&self) -> bool {
 304         match self.inner {
 305             StrippedItem(box ModuleItem(Module { is_crate: true, ..})) |
 306             ModuleItem(Module { is_crate: true, ..}) => true,
 307             _ => false,
 308         }
 309     }
 310     pub fn is_mod(&self) -> bool {
 311         self.type_() == ItemType::Module
 312     }
 313     pub fn is_trait(&self) -> bool {
 314         self.type_() == ItemType::Trait
 315     }
 316     pub fn is_struct(&self) -> bool {
 317         self.type_() == ItemType::Struct
 318     }
 319     pub fn is_enum(&self) -> bool {
 320         self.type_() == ItemType::Enum
 321     }
 322     pub fn is_fn(&self) -> bool {
 323         self.type_() == ItemType::Function
 324     }
 325     pub fn is_associated_type(&self) -> bool {
 326         self.type_() == ItemType::AssociatedType
 327     }
 328     pub fn is_associated_const(&self) -> bool {
 329         self.type_() == ItemType::AssociatedConst
 330     }
 331     pub fn is_method(&self) -> bool {
 332         self.type_() == ItemType::Method
 333     }
 334     pub fn is_ty_method(&self) -> bool {
 335         self.type_() == ItemType::TyMethod
 336     }
 337     pub fn is_typedef(&self) -> bool {
 338         self.type_() == ItemType::Typedef
 339     }
 340     pub fn is_primitive(&self) -> bool {
 341         self.type_() == ItemType::Primitive
 342     }
 343     pub fn is_union(&self) -> bool {
 344         self.type_() == ItemType::Union
 345     }
 346     pub fn is_import(&self) -> bool {
 347         self.type_() == ItemType::Import
 348     }
 349     pub fn is_extern_crate(&self) -> bool {
 350         self.type_() == ItemType::ExternCrate
 351     }
 352
 353     pub fn is_stripped(&self) -> bool {
 354         match self.inner { StrippedItem(..) => true, _ => false }
 355     }
 356     pub fn has_stripped_fields(&self) -> Option<bool> {
 357         match self.inner {
 358             StructItem(ref _struct) => Some(_struct.fields_stripped),
 359             UnionItem(ref union) => Some(union.fields_stripped),
 360             VariantItem(Variant { kind: VariantKind::Struct(ref vstruct)} ) => {
 361                 Some(vstruct.fields_stripped)
 362             },
 363             _ => None,
 364         }
 365     }
 366
 367     pub fn stability_class(&self) -> Option<String> {
 368         self.stability.as_ref().and_then(|ref s| {
 369             let mut classes = Vec::with_capacity(2);
 370
 371             if s.level == stability::Unstable {
 372                 classes.push("unstable");
 373             }
 374
 375             if !s.deprecated_since.is_empty() {
 376                 classes.push("deprecated");
 377             }
 378
 379             if classes.len() != 0 {
 380                 Some(classes.join(" "))
 381             } else {
 382                 None
 383             }
 384         })
 385     }
 386
 387     pub fn stable_since(&self) -> Option<&str> {
 388         self.stability.as_ref().map(|s| &s.since[..])
 389     }
 390
 391     /// Returns a documentation-level item type from the item.
 392     pub fn type_(&self) -> ItemType {
 393         ItemType::from(self)
 394     }
 395 }
 396
 397 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
 398 pub enum ItemEnum {
 399     ExternCrateItem(String, Option<String>),
 400     ImportItem(Import),
 401     StructItem(Struct),
 402     UnionItem(Union),
 403     EnumItem(Enum),
 404     FunctionItem(Function),
 405     ModuleItem(Module),
 406     TypedefItem(Typedef, bool /* is associated type */),
 407     StaticItem(Static),
 408     ConstantItem(Constant),
 409     TraitItem(Trait),
 410     ImplItem(Impl),
 411     /// A method signature only. Used for required methods in traits (ie,
 412     /// non-default-methods).
 413     TyMethodItem(TyMethod),
 414     /// A method with a body.
 415     MethodItem(Method),
 416     StructFieldItem(Type),
 417     VariantItem(Variant),
 418     /// `fn`s from an extern block
 419     ForeignFunctionItem(Function),
 420     /// `static`s from an extern block
 421     ForeignStaticItem(Static),
 422     MacroItem(Macro),
 423     PrimitiveItem(PrimitiveType),
 424     AssociatedConstItem(Type, Option<String>),
 425     AssociatedTypeItem(Vec<TyParamBound>, Option<Type>),
 426     DefaultImplItem(DefaultImpl),
 427     /// An item that has been stripped by a rustdoc pass
 428     StrippedItem(Box<ItemEnum>),
 429 }
 430
 431 impl ItemEnum {
 432     pub fn generics(&self) -> Option<&Generics> {
 433         Some(match *self {
 434             ItemEnum::StructItem(ref s) => &s.generics,
 435             ItemEnum::EnumItem(ref e) => &e.generics,
 436             ItemEnum::FunctionItem(ref f) => &f.generics,
 437             ItemEnum::TypedefItem(ref t, _) => &t.generics,
 438             ItemEnum::TraitItem(ref t) => &t.generics,
 439             ItemEnum::ImplItem(ref i) => &i.generics,
 440             ItemEnum::TyMethodItem(ref i) => &i.generics,
 441             ItemEnum::MethodItem(ref i) => &i.generics,
 442             ItemEnum::ForeignFunctionItem(ref f) => &f.generics,
 443             _ => return None,
 444         })
 445     }
 446 }
 447
 448 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
 449 pub struct Module {
 450     pub items: Vec<Item>,
 451     pub is_crate: bool,
 452 }
 453
 454 impl Clean<Item> for doctree::Module {
 455     fn clean(&self, cx: &DocContext) -> Item {
 456         let name = if self.name.is_some() {
 457             self.name.unwrap().clean(cx)
 458         } else {
 459             "".to_string()
 460         };
 461
 462         let mut items: Vec<Item> = vec![];
 463         items.extend(self.extern_crates.iter().map(|x| x.clean(cx)));
 464         items.extend(self.imports.iter().flat_map(|x| x.clean(cx)));
 465         items.extend(self.structs.iter().map(|x| x.clean(cx)));
 466         items.extend(self.unions.iter().map(|x| x.clean(cx)));
 467         items.extend(self.enums.iter().map(|x| x.clean(cx)));
 468         items.extend(self.fns.iter().map(|x| x.clean(cx)));
 469         items.extend(self.foreigns.iter().flat_map(|x| x.clean(cx)));
 470         items.extend(self.mods.iter().map(|x| x.clean(cx)));
 471         items.extend(self.typedefs.iter().map(|x| x.clean(cx)));
 472         items.extend(self.statics.iter().map(|x| x.clean(cx)));
 473         items.extend(self.constants.iter().map(|x| x.clean(cx)));
 474         items.extend(self.traits.iter().map(|x| x.clean(cx)));
 475         items.extend(self.impls.iter().flat_map(|x| x.clean(cx)));
 476         items.extend(self.macros.iter().map(|x| x.clean(cx)));
 477         items.extend(self.def_traits.iter().map(|x| x.clean(cx)));
 478
 479         // determine if we should display the inner contents or
 480         // the outer `mod` item for the source code.
 481         let whence = {
 482             let cm = cx.sess().codemap();
 483             let outer = cm.lookup_char_pos(self.where_outer.lo());
 484             let inner = cm.lookup_char_pos(self.where_inner.lo());
 485             if outer.file.start_pos == inner.file.start_pos {
 486                 // mod foo { ... }
 487                 self.where_outer
 488             } else {
 489                 // mod foo; (and a separate FileMap for the contents)
 490                 self.where_inner
 491             }
 492         };
 493
 494         Item {
 495             name: Some(name),
 496             attrs: self.attrs.clean(cx),
 497             source: whence.clean(cx),
 498             visibility: self.vis.clean(cx),
 499             stability: self.stab.clean(cx),
 500             deprecation: self.depr.clean(cx),
 501             def_id: cx.tcx.hir.local_def_id(self.id),
 502             inner: ModuleItem(Module {
 503                is_crate: self.is_crate,
 504                items,
 505             })
 506         }
 507     }
 508 }
 509
 510 pub struct ListAttributesIter<'a> {
 511     attrs: slice::Iter<'a, ast::Attribute>,
 512     current_list: vec::IntoIter<ast::NestedMetaItem>,
 513     name: &'a str
 514 }
 515
 516 impl<'a> Iterator for ListAttributesIter<'a> {
 517     type Item = ast::NestedMetaItem;
 518
 519     fn next(&mut self) -> Option<Self::Item> {
 520         if let Some(nested) = self.current_list.next() {
 521             return Some(nested);
 522         }
 523
 524         for attr in &mut self.attrs {
 525             if let Some(list) = attr.meta_item_list() {
 526                 if attr.check_name(self.name) {
 527                     self.current_list = list.into_iter();
 528                     if let Some(nested) = self.current_list.next() {
 529                         return Some(nested);
 530                     }
 531                 }
 532             }
 533         }
 534
 535         None
 536     }
 537 }
 538
 539 pub trait AttributesExt {
 540     /// Finds an attribute as List and returns the list of attributes nested inside.
 541     fn lists<'a>(&'a self, name: &'a str) -> ListAttributesIter<'a>;
 542 }
 543
 544 impl AttributesExt for [ast::Attribute] {
 545     fn lists<'a>(&'a self, name: &'a str) -> ListAttributesIter<'a> {
 546         ListAttributesIter {
 547             attrs: self.iter(),
 548             current_list: Vec::new().into_iter(),
 549             name,
 550         }
 551     }
 552 }
 553
 554 pub trait NestedAttributesExt {
 555     /// Returns whether the attribute list contains a specific `Word`
 556     fn has_word(self, word: &str) -> bool;
 557 }
 558
 559 impl<I: IntoIterator<Item=ast::NestedMetaItem>> NestedAttributesExt for I {
 560     fn has_word(self, word: &str) -> bool {
 561         self.into_iter().any(|attr| attr.is_word() && attr.check_name(word))
 562     }
 563 }
 564
 565 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug, Default)]
 566 pub struct Attributes {
 567     pub doc_strings: Vec<String>,
 568     pub other_attrs: Vec<ast::Attribute>,
 569     pub cfg: Option<Rc<Cfg>>,
 570     pub span: Option<syntax_pos::Span>,
 571 }
 572
 573 impl Attributes {
 574     /// Extracts the content from an attribute `#[doc(cfg(content))]`.
 575     fn extract_cfg(mi: &ast::MetaItem) -> Option<&ast::MetaItem> {
 576         use syntax::ast::NestedMetaItemKind::MetaItem;
 577
 578         if let ast::MetaItemKind::List(ref nmis) = mi.node {
 579             if nmis.len() == 1 {
 580                 if let MetaItem(ref cfg_mi) = nmis[0].node {
 581                     if cfg_mi.check_name("cfg") {
 582                         if let ast::MetaItemKind::List(ref cfg_nmis) = cfg_mi.node {
 583                             if cfg_nmis.len() == 1 {
 584                                 if let MetaItem(ref content_mi) = cfg_nmis[0].node {
 585                                     return Some(content_mi);
 586                                 }
 587                             }
 588                         }
 589                     }
 590                 }
 591             }
 592         }
 593
 594         None
 595     }
 596
 597     pub fn has_doc_masked(&self) -> bool {
 598         for attr in &self.other_attrs {
 599             if !attr.check_name("doc") { continue; }
 600
 601             if let Some(items) = attr.meta_item_list() {
 602                 if items.iter().filter_map(|i| i.meta_item()).any(|it| it.check_name("masked")) {
 603                     return true;
 604                 }
 605             }
 606         }
 607
 608         false
 609     }
 610
 611     pub fn from_ast(diagnostic: &::errors::Handler, attrs: &[ast::Attribute]) -> Attributes {
 612         let mut doc_strings = vec![];
 613         let mut sp = None;
 614         let mut cfg = Cfg::True;
 615
 616         let other_attrs = attrs.iter().filter_map(|attr| {
 617             attr.with_desugared_doc(|attr| {
 618                 if attr.check_name("doc") {
 619                     if let Some(mi) = attr.meta() {
 620                         if let Some(value) = mi.value_str() {
 621                             // Extracted #[doc = "..."]
 622                             doc_strings.push(value.to_string());
 623                             if sp.is_none() {
 624                                 sp = Some(attr.span);
 625                             }
 626                             return None;
 627                         } else if let Some(cfg_mi) = Attributes::extract_cfg(&mi) {
 628                             // Extracted #[doc(cfg(...))]
 629                             match Cfg::parse(cfg_mi) {
 630                                 Ok(new_cfg) => cfg &= new_cfg,
 631                                 Err(e) => diagnostic.span_err(e.span, e.msg),
 632                             }
 633                             return None;
 634                         }
 635                     }
 636                 }
 637                 Some(attr.clone())
 638             })
 639         }).collect();
 640         Attributes {
 641             doc_strings,
 642             other_attrs,
 643             cfg: if cfg == Cfg::True { None } else { Some(Rc::new(cfg)) },
 644             span: sp,
 645         }
 646     }
 647
 648     /// Finds the `doc` attribute as a NameValue and returns the corresponding
 649     /// value found.
 650     pub fn doc_value<'a>(&'a self) -> Option<&'a str> {
 651         self.doc_strings.first().map(|s| &s[..])
 652     }
 653 }
 654
 655 impl AttributesExt for Attributes {
 656     fn lists<'a>(&'a self, name: &'a str) -> ListAttributesIter<'a> {
 657         self.other_attrs.lists(name)
 658     }
 659 }
 660
 661 impl Clean<Attributes> for [ast::Attribute] {
 662     fn clean(&self, cx: &DocContext) -> Attributes {
 663         Attributes::from_ast(cx.sess().diagnostic(), self)
 664     }
 665 }
 666
 667 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
 668 pub struct TyParam {
 669     pub name: String,
 670     pub did: DefId,
 671     pub bounds: Vec<TyParamBound>,
 672     pub default: Option<Type>,
 673 }
 674
 675 impl Clean<TyParam> for hir::TyParam {
 676     fn clean(&self, cx: &DocContext) -> TyParam {
 677         TyParam {
 678             name: self.name.clean(cx),
 679             did: cx.tcx.hir.local_def_id(self.id),
 680             bounds: self.bounds.clean(cx),
 681             default: self.default.clean(cx),
 682         }
 683     }
 684 }
 685
 686 impl<'tcx> Clean<TyParam> for ty::TypeParameterDef {
 687     fn clean(&self, cx: &DocContext) -> TyParam {
 688         cx.renderinfo.borrow_mut().external_typarams.insert(self.def_id, self.name.clean(cx));
 689         TyParam {
 690             name: self.name.clean(cx),
 691             did: self.def_id,
 692             bounds: vec![], // these are filled in from the where-clauses
 693             default: if self.has_default {
 694                 Some(cx.tcx.type_of(self.def_id).clean(cx))
 695             } else {
 696                 None
 697             }
 698         }
 699     }
 700 }
 701
 702 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
 703 pub enum TyParamBound {
 704     RegionBound(Lifetime),
 705     TraitBound(PolyTrait, hir::TraitBoundModifier)
 706 }
 707
 708 impl TyParamBound {
 709     fn maybe_sized(cx: &DocContext) -> TyParamBound {
 710         let did = cx.tcx.require_lang_item(lang_items::SizedTraitLangItem);
 711         let empty = cx.tcx.intern_substs(&[]);
 712         let path = external_path(cx, &cx.tcx.item_name(did),
 713             Some(did), false, vec![], empty);
 714         inline::record_extern_fqn(cx, did, TypeKind::Trait);
 715         TraitBound(PolyTrait {
 716             trait_: ResolvedPath {
 717                 path,
 718                 typarams: None,
 719                 did,
 720                 is_generic: false,
 721             },
 722             lifetimes: vec![]
 723         }, hir::TraitBoundModifier::Maybe)
 724     }
 725
 726     fn is_sized_bound(&self, cx: &DocContext) -> bool {
 727         use rustc::hir::TraitBoundModifier as TBM;
 728         if let TyParamBound::TraitBound(PolyTrait { ref trait_, .. }, TBM::None) = *self {
 729             if trait_.def_id() == cx.tcx.lang_items().sized_trait() {
 730                 return true;
 731             }
 732         }
 733         false
 734     }
 735 }
 736
 737 impl Clean<TyParamBound> for hir::TyParamBound {
 738     fn clean(&self, cx: &DocContext) -> TyParamBound {
 739         match *self {
 740             hir::RegionTyParamBound(lt) => RegionBound(lt.clean(cx)),
 741             hir::TraitTyParamBound(ref t, modifier) => TraitBound(t.clean(cx), modifier),
 742         }
 743     }
 744 }
 745
 746 fn external_path_params(cx: &DocContext, trait_did: Option<DefId>, has_self: bool,
 747                         bindings: Vec<TypeBinding>, substs: &Substs) -> PathParameters {
 748     let lifetimes = substs.regions().filter_map(|v| v.clean(cx)).collect();
 749     let types = substs.types().skip(has_self as usize).collect::<Vec<_>>();
 750
 751     match trait_did {
 752         // Attempt to sugar an external path like Fn<(A, B,), C> to Fn(A, B) -> C
 753         Some(did) if cx.tcx.lang_items().fn_trait_kind(did).is_some() => {
 754             assert_eq!(types.len(), 1);
 755             let inputs = match types[0].sty {
 756                 ty::TyTuple(ref tys, _) => tys.iter().map(|t| t.clean(cx)).collect(),
 757                 _ => {
 758                     return PathParameters::AngleBracketed {
 759                         lifetimes,
 760                         types: types.clean(cx),
 761                         bindings,
 762                     }
 763                 }
 764             };
 765             let output = None;
 766             // FIXME(#20299) return type comes from a projection now
 767             // match types[1].sty {
 768             //     ty::TyTuple(ref v, _) if v.is_empty() => None, // -> ()
 769             //     _ => Some(types[1].clean(cx))
 770             // };
 771             PathParameters::Parenthesized {
 772                 inputs,
 773                 output,
 774             }
 775         },
 776         _ => {
 777             PathParameters::AngleBracketed {
 778                 lifetimes,
 779                 types: types.clean(cx),
 780                 bindings,
 781             }
 782         }
 783     }
 784 }
 785
 786 // trait_did should be set to a trait's DefId if called on a TraitRef, in order to sugar
 787 // from Fn<(A, B,), C> to Fn(A, B) -> C
 788 fn external_path(cx: &DocContext, name: &str, trait_did: Option<DefId>, has_self: bool,
 789                  bindings: Vec<TypeBinding>, substs: &Substs) -> Path {
 790     Path {
 791         global: false,
 792         def: Def::Err,
 793         segments: vec![PathSegment {
 794             name: name.to_string(),
 795             params: external_path_params(cx, trait_did, has_self, bindings, substs)
 796         }],
 797     }
 798 }
 799
 800 impl<'tcx> Clean<TyParamBound> for ty::TraitRef<'tcx> {
 801     fn clean(&self, cx: &DocContext) -> TyParamBound {
 802         inline::record_extern_fqn(cx, self.def_id, TypeKind::Trait);
 803         let path = external_path(cx, &cx.tcx.item_name(self.def_id),
 804                                  Some(self.def_id), true, vec![], self.substs);
 805
 806         debug!("ty::TraitRef\n  subst: {:?}\n", self.substs);
 807
 808         // collect any late bound regions
 809         let mut late_bounds = vec![];
 810         for ty_s in self.input_types().skip(1) {
 811             if let ty::TyTuple(ts, _) = ty_s.sty {
 812                 for &ty_s in ts {
 813                     if let ty::TyRef(ref reg, _) = ty_s.sty {
 814                         if let &ty::RegionKind::ReLateBound(..) = *reg {
 815                             debug!("  hit an ReLateBound {:?}", reg);
 816                             if let Some(lt) = reg.clean(cx) {
 817                                 late_bounds.push(lt);
 818                             }
 819                         }
 820                     }
 821                 }
 822             }
 823         }
 824
 825         TraitBound(
 826             PolyTrait {
 827                 trait_: ResolvedPath {
 828                     path,
 829                     typarams: None,
 830                     did: self.def_id,
 831                     is_generic: false,
 832                 },
 833                 lifetimes: late_bounds,
 834             },
 835             hir::TraitBoundModifier::None
 836         )
 837     }
 838 }
 839
 840 impl<'tcx> Clean<Option<Vec<TyParamBound>>> for Substs<'tcx> {
 841     fn clean(&self, cx: &DocContext) -> Option<Vec<TyParamBound>> {
 842         let mut v = Vec::new();
 843         v.extend(self.regions().filter_map(|r| r.clean(cx))
 844                      .map(RegionBound));
 845         v.extend(self.types().map(|t| TraitBound(PolyTrait {
 846             trait_: t.clean(cx),
 847             lifetimes: vec![]
 848         }, hir::TraitBoundModifier::None)));
 849         if !v.is_empty() {Some(v)} else {None}
 850     }
 851 }
 852
 853 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
 854 pub struct Lifetime(String);
 855
 856 impl Lifetime {
 857     pub fn get_ref<'a>(&'a self) -> &'a str {
 858         let Lifetime(ref s) = *self;
 859         let s: &'a str = s;
 860         s
 861     }
 862
 863     pub fn statik() -> Lifetime {
 864         Lifetime("'static".to_string())
 865     }
 866 }
 867
 868 impl Clean<Lifetime> for hir::Lifetime {
 869     fn clean(&self, cx: &DocContext) -> Lifetime {
 870         let hir_id = cx.tcx.hir.node_to_hir_id(self.id);
 871         let def = cx.tcx.named_region(hir_id);
 872         match def {
 873             Some(rl::Region::EarlyBound(_, node_id)) |
 874             Some(rl::Region::LateBound(_, node_id)) |
 875             Some(rl::Region::Free(_, node_id)) => {
 876                 if let Some(lt) = cx.lt_substs.borrow().get(&node_id).cloned() {
 877                     return lt;
 878                 }
 879             }
 880             _ => {}
 881         }
 882         Lifetime(self.name.name().to_string())
 883     }
 884 }
 885
 886 impl Clean<Lifetime> for hir::LifetimeDef {
 887     fn clean(&self, _: &DocContext) -> Lifetime {
 888         if self.bounds.len() > 0 {
 889             let mut s = format!("{}: {}",
 890                                 self.lifetime.name.name(),
 891                                 self.bounds[0].name.name());
 892             for bound in self.bounds.iter().skip(1) {
 893                 s.push_str(&format!(" + {}", bound.name.name()));
 894             }
 895             Lifetime(s)
 896         } else {
 897             Lifetime(self.lifetime.name.name().to_string())
 898         }
 899     }
 900 }
 901
 902 impl Clean<Lifetime> for ty::RegionParameterDef {
 903     fn clean(&self, _: &DocContext) -> Lifetime {
 904         Lifetime(self.name.to_string())
 905     }
 906 }
 907
 908 impl Clean<Option<Lifetime>> for ty::RegionKind {
 909     fn clean(&self, cx: &DocContext) -> Option<Lifetime> {
 910         match *self {
 911             ty::ReStatic => Some(Lifetime::statik()),
 912             ty::ReLateBound(_, ty::BrNamed(_, name)) => Some(Lifetime(name.to_string())),
 913             ty::ReEarlyBound(ref data) => Some(Lifetime(data.name.clean(cx))),
 914
 915             ty::ReLateBound(..) |
 916             ty::ReFree(..) |
 917             ty::ReScope(..) |
 918             ty::ReVar(..) |
 919             ty::ReSkolemized(..) |
 920             ty::ReEmpty |
 921             ty::ReErased => None
 922         }
 923     }
 924 }
 925
 926 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
 927 pub enum WherePredicate {
 928     BoundPredicate { ty: Type, bounds: Vec<TyParamBound> },
 929     RegionPredicate { lifetime: Lifetime, bounds: Vec<Lifetime>},
 930     EqPredicate { lhs: Type, rhs: Type },
 931 }
 932
 933 impl Clean<WherePredicate> for hir::WherePredicate {
 934     fn clean(&self, cx: &DocContext) -> WherePredicate {
 935         match *self {
 936             hir::WherePredicate::BoundPredicate(ref wbp) => {
 937                 WherePredicate::BoundPredicate {
 938                     ty: wbp.bounded_ty.clean(cx),
 939                     bounds: wbp.bounds.clean(cx)
 940                 }
 941             }
 942
 943             hir::WherePredicate::RegionPredicate(ref wrp) => {
 944                 WherePredicate::RegionPredicate {
 945                     lifetime: wrp.lifetime.clean(cx),
 946                     bounds: wrp.bounds.clean(cx)
 947                 }
 948             }
 949
 950             hir::WherePredicate::EqPredicate(ref wrp) => {
 951                 WherePredicate::EqPredicate {
 952                     lhs: wrp.lhs_ty.clean(cx),
 953                     rhs: wrp.rhs_ty.clean(cx)
 954                 }
 955             }
 956         }
 957     }
 958 }
 959
 960 impl<'a> Clean<WherePredicate> for ty::Predicate<'a> {
 961     fn clean(&self, cx: &DocContext) -> WherePredicate {
 962         use rustc::ty::Predicate;
 963
 964         match *self {
 965             Predicate::Trait(ref pred) => pred.clean(cx),
 966             Predicate::Equate(ref pred) => pred.clean(cx),
 967             Predicate::Subtype(ref pred) => pred.clean(cx),
 968             Predicate::RegionOutlives(ref pred) => pred.clean(cx),
 969             Predicate::TypeOutlives(ref pred) => pred.clean(cx),
 970             Predicate::Projection(ref pred) => pred.clean(cx),
 971             Predicate::WellFormed(_) => panic!("not user writable"),
 972             Predicate::ObjectSafe(_) => panic!("not user writable"),
 973             Predicate::ClosureKind(..) => panic!("not user writable"),
 974             Predicate::ConstEvaluatable(..) => panic!("not user writable"),
 975         }
 976     }
 977 }
 978
 979 impl<'a> Clean<WherePredicate> for ty::TraitPredicate<'a> {
 980     fn clean(&self, cx: &DocContext) -> WherePredicate {
 981         WherePredicate::BoundPredicate {
 982             ty: self.trait_ref.self_ty().clean(cx),
 983             bounds: vec![self.trait_ref.clean(cx)]
 984         }
 985     }
 986 }
 987
 988 impl<'tcx> Clean<WherePredicate> for ty::EquatePredicate<'tcx> {
 989     fn clean(&self, cx: &DocContext) -> WherePredicate {
 990         let ty::EquatePredicate(ref lhs, ref rhs) = *self;
 991         WherePredicate::EqPredicate {
 992             lhs: lhs.clean(cx),
 993             rhs: rhs.clean(cx)
 994         }
 995     }
 996 }
 997
 998 impl<'tcx> Clean<WherePredicate> for ty::SubtypePredicate<'tcx> {
 999     fn clean(&self, _cx: &DocContext) -> WherePredicate {
1000         panic!("subtype predicates are an internal rustc artifact \
1001                 and should not be seen by rustdoc")
1002     }
1003 }
1004
1005 impl<'tcx> Clean<WherePredicate> for ty::OutlivesPredicate<ty::Region<'tcx>, ty::Region<'tcx>> {
1006     fn clean(&self, cx: &DocContext) -> WherePredicate {
1007         let ty::OutlivesPredicate(ref a, ref b) = *self;
1008         WherePredicate::RegionPredicate {
1009             lifetime: a.clean(cx).unwrap(),
1010             bounds: vec![b.clean(cx).unwrap()]
1011         }
1012     }
1013 }
1014
1015 impl<'tcx> Clean<WherePredicate> for ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>> {
1016     fn clean(&self, cx: &DocContext) -> WherePredicate {
1017         let ty::OutlivesPredicate(ref ty, ref lt) = *self;
1018
1019         WherePredicate::BoundPredicate {
1020             ty: ty.clean(cx),
1021             bounds: vec![TyParamBound::RegionBound(lt.clean(cx).unwrap())]
1022         }
1023     }
1024 }
1025
1026 impl<'tcx> Clean<WherePredicate> for ty::ProjectionPredicate<'tcx> {
1027     fn clean(&self, cx: &DocContext) -> WherePredicate {
1028         WherePredicate::EqPredicate {
1029             lhs: self.projection_ty.clean(cx),
1030             rhs: self.ty.clean(cx)
1031         }
1032     }
1033 }
1034
1035 impl<'tcx> Clean<Type> for ty::ProjectionTy<'tcx> {
1036     fn clean(&self, cx: &DocContext) -> Type {
1037         let trait_ = match self.trait_ref(cx.tcx).clean(cx) {
1038             TyParamBound::TraitBound(t, _) => t.trait_,
1039             TyParamBound::RegionBound(_) => {
1040                 panic!("cleaning a trait got a region")
1041             }
1042         };
1043         Type::QPath {
1044             name: cx.tcx.associated_item(self.item_def_id).name.clean(cx),
1045             self_type: box self.self_ty().clean(cx),
1046             trait_: box trait_
1047         }
1048     }
1049 }
1050
1051 // maybe use a Generic enum and use Vec<Generic>?
1052 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1053 pub struct Generics {
1054     pub lifetimes: Vec<Lifetime>,
1055     pub type_params: Vec<TyParam>,
1056     pub where_predicates: Vec<WherePredicate>
1057 }
1058
1059 impl Clean<Generics> for hir::Generics {
1060     fn clean(&self, cx: &DocContext) -> Generics {
1061         Generics {
1062             lifetimes: self.lifetimes.clean(cx),
1063             type_params: self.ty_params.clean(cx),
1064             where_predicates: self.where_clause.predicates.clean(cx)
1065         }
1066     }
1067 }
1068
1069 impl<'a, 'tcx> Clean<Generics> for (&'a ty::Generics,
1070                                     &'a ty::GenericPredicates<'tcx>) {
1071     fn clean(&self, cx: &DocContext) -> Generics {
1072         use self::WherePredicate as WP;
1073
1074         let (gens, preds) = *self;
1075
1076         // Bounds in the type_params and lifetimes fields are repeated in the
1077         // predicates field (see rustc_typeck::collect::ty_generics), so remove
1078         // them.
1079         let stripped_typarams = gens.types.iter().filter_map(|tp| {
1080             if tp.name == keywords::SelfType.name() {
1081                 assert_eq!(tp.index, 0);
1082                 None
1083             } else {
1084                 Some(tp.clean(cx))
1085             }
1086         }).collect::<Vec<_>>();
1087
1088         let mut where_predicates = preds.predicates.to_vec().clean(cx);
1089
1090         // Type parameters and have a Sized bound by default unless removed with
1091         // ?Sized.  Scan through the predicates and mark any type parameter with
1092         // a Sized bound, removing the bounds as we find them.
1093         //
1094         // Note that associated types also have a sized bound by default, but we
1095         // don't actually know the set of associated types right here so that's
1096         // handled in cleaning associated types
1097         let mut sized_params = FxHashSet();
1098         where_predicates.retain(|pred| {
1099             match *pred {
1100                 WP::BoundPredicate { ty: Generic(ref g), ref bounds } => {
1101                     if bounds.iter().any(|b| b.is_sized_bound(cx)) {
1102                         sized_params.insert(g.clone());
1103                         false
1104                     } else {
1105                         true
1106                     }
1107                 }
1108                 _ => true,
1109             }
1110         });
1111
1112         // Run through the type parameters again and insert a ?Sized
1113         // unbound for any we didn't find to be Sized.
1114         for tp in &stripped_typarams {
1115             if !sized_params.contains(&tp.name) {
1116                 where_predicates.push(WP::BoundPredicate {
1117                     ty: Type::Generic(tp.name.clone()),
1118                     bounds: vec![TyParamBound::maybe_sized(cx)],
1119                 })
1120             }
1121         }
1122
1123         // It would be nice to collect all of the bounds on a type and recombine
1124         // them if possible, to avoid e.g. `where T: Foo, T: Bar, T: Sized, T: 'a`
1125         // and instead see `where T: Foo + Bar + Sized + 'a`
1126
1127         Generics {
1128             type_params: simplify::ty_params(stripped_typarams),
1129             lifetimes: gens.regions.clean(cx),
1130             where_predicates: simplify::where_clauses(cx, where_predicates),
1131         }
1132     }
1133 }
1134
1135 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1136 pub struct Method {
1137     pub generics: Generics,
1138     pub unsafety: hir::Unsafety,
1139     pub constness: hir::Constness,
1140     pub decl: FnDecl,
1141     pub abi: Abi,
1142 }
1143
1144 impl<'a> Clean<Method> for (&'a hir::MethodSig, hir::BodyId) {
1145     fn clean(&self, cx: &DocContext) -> Method {
1146         Method {
1147             generics: self.0.generics.clean(cx),
1148             unsafety: self.0.unsafety,
1149             constness: self.0.constness,
1150             decl: (&*self.0.decl, self.1).clean(cx),
1151             abi: self.0.abi
1152         }
1153     }
1154 }
1155
1156 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1157 pub struct TyMethod {
1158     pub unsafety: hir::Unsafety,
1159     pub decl: FnDecl,
1160     pub generics: Generics,
1161     pub abi: Abi,
1162 }
1163
1164 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1165 pub struct Function {
1166     pub decl: FnDecl,
1167     pub generics: Generics,
1168     pub unsafety: hir::Unsafety,
1169     pub constness: hir::Constness,
1170     pub abi: Abi,
1171 }
1172
1173 impl Clean<Item> for doctree::Function {
1174     fn clean(&self, cx: &DocContext) -> Item {
1175         Item {
1176             name: Some(self.name.clean(cx)),
1177             attrs: self.attrs.clean(cx),
1178             source: self.whence.clean(cx),
1179             visibility: self.vis.clean(cx),
1180             stability: self.stab.clean(cx),
1181             deprecation: self.depr.clean(cx),
1182             def_id: cx.tcx.hir.local_def_id(self.id),
1183             inner: FunctionItem(Function {
1184                 decl: (&self.decl, self.body).clean(cx),
1185                 generics: self.generics.clean(cx),
1186                 unsafety: self.unsafety,
1187                 constness: self.constness,
1188                 abi: self.abi,
1189             }),
1190         }
1191     }
1192 }
1193
1194 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1195 pub struct FnDecl {
1196     pub inputs: Arguments,
1197     pub output: FunctionRetTy,
1198     pub variadic: bool,
1199     pub attrs: Attributes,
1200 }
1201
1202 impl FnDecl {
1203     pub fn has_self(&self) -> bool {
1204         self.inputs.values.len() > 0 && self.inputs.values[0].name == "self"
1205     }
1206
1207     pub fn self_type(&self) -> Option<SelfTy> {
1208         self.inputs.values.get(0).and_then(|v| v.to_self())
1209     }
1210 }
1211
1212 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1213 pub struct Arguments {
1214     pub values: Vec<Argument>,
1215 }
1216
1217 impl<'a> Clean<Arguments> for (&'a [P<hir::Ty>], &'a [Spanned<ast::Name>]) {
1218     fn clean(&self, cx: &DocContext) -> Arguments {
1219         Arguments {
1220             values: self.0.iter().enumerate().map(|(i, ty)| {
1221                 let mut name = self.1.get(i).map(|n| n.node.to_string())
1222                                             .unwrap_or(String::new());
1223                 if name.is_empty() {
1224                     name = "_".to_string();
1225                 }
1226                 Argument {
1227                     name,
1228                     type_: ty.clean(cx),
1229                 }
1230             }).collect()
1231         }
1232     }
1233 }
1234
1235 impl<'a> Clean<Arguments> for (&'a [P<hir::Ty>], hir::BodyId) {
1236     fn clean(&self, cx: &DocContext) -> Arguments {
1237         let body = cx.tcx.hir.body(self.1);
1238
1239         Arguments {
1240             values: self.0.iter().enumerate().map(|(i, ty)| {
1241                 Argument {
1242                     name: name_from_pat(&body.arguments[i].pat),
1243                     type_: ty.clean(cx),
1244                 }
1245             }).collect()
1246         }
1247     }
1248 }
1249
1250 impl<'a, A: Copy> Clean<FnDecl> for (&'a hir::FnDecl, A)
1251     where (&'a [P<hir::Ty>], A): Clean<Arguments>
1252 {
1253     fn clean(&self, cx: &DocContext) -> FnDecl {
1254         FnDecl {
1255             inputs: (&self.0.inputs[..], self.1).clean(cx),
1256             output: self.0.output.clean(cx),
1257             variadic: self.0.variadic,
1258             attrs: Attributes::default()
1259         }
1260     }
1261 }
1262
1263 impl<'a, 'tcx> Clean<FnDecl> for (DefId, ty::PolyFnSig<'tcx>) {
1264     fn clean(&self, cx: &DocContext) -> FnDecl {
1265         let (did, sig) = *self;
1266         let mut names = if cx.tcx.hir.as_local_node_id(did).is_some() {
1267             vec![].into_iter()
1268         } else {
1269             cx.tcx.fn_arg_names(did).into_iter()
1270         }.peekable();
1271         FnDecl {
1272             output: Return(sig.skip_binder().output().clean(cx)),
1273             attrs: Attributes::default(),
1274             variadic: sig.skip_binder().variadic,
1275             inputs: Arguments {
1276                 values: sig.skip_binder().inputs().iter().map(|t| {
1277                     Argument {
1278                         type_: t.clean(cx),
1279                         name: names.next().map_or("".to_string(), |name| name.to_string()),
1280                     }
1281                 }).collect(),
1282             },
1283         }
1284     }
1285 }
1286
1287 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1288 pub struct Argument {
1289     pub type_: Type,
1290     pub name: String,
1291 }
1292
1293 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1294 pub enum SelfTy {
1295     SelfValue,
1296     SelfBorrowed(Option<Lifetime>, Mutability),
1297     SelfExplicit(Type),
1298 }
1299
1300 impl Argument {
1301     pub fn to_self(&self) -> Option<SelfTy> {
1302         if self.name != "self" {
1303             return None;
1304         }
1305         if self.type_.is_self_type() {
1306             return Some(SelfValue);
1307         }
1308         match self.type_ {
1309             BorrowedRef{ref lifetime, mutability, ref type_} if type_.is_self_type() => {
1310                 Some(SelfBorrowed(lifetime.clone(), mutability))
1311             }
1312             _ => Some(SelfExplicit(self.type_.clone()))
1313         }
1314     }
1315 }
1316
1317 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1318 pub enum FunctionRetTy {
1319     Return(Type),
1320     DefaultReturn,
1321 }
1322
1323 impl Clean<FunctionRetTy> for hir::FunctionRetTy {
1324     fn clean(&self, cx: &DocContext) -> FunctionRetTy {
1325         match *self {
1326             hir::Return(ref typ) => Return(typ.clean(cx)),
1327             hir::DefaultReturn(..) => DefaultReturn,
1328         }
1329     }
1330 }
1331
1332 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1333 pub struct Trait {
1334     pub unsafety: hir::Unsafety,
1335     pub items: Vec<Item>,
1336     pub generics: Generics,
1337     pub bounds: Vec<TyParamBound>,
1338 }
1339
1340 impl Clean<Item> for doctree::Trait {
1341     fn clean(&self, cx: &DocContext) -> Item {
1342         Item {
1343             name: Some(self.name.clean(cx)),
1344             attrs: self.attrs.clean(cx),
1345             source: self.whence.clean(cx),
1346             def_id: cx.tcx.hir.local_def_id(self.id),
1347             visibility: self.vis.clean(cx),
1348             stability: self.stab.clean(cx),
1349             deprecation: self.depr.clean(cx),
1350             inner: TraitItem(Trait {
1351                 unsafety: self.unsafety,
1352                 items: self.items.clean(cx),
1353                 generics: self.generics.clean(cx),
1354                 bounds: self.bounds.clean(cx),
1355             }),
1356         }
1357     }
1358 }
1359
1360 impl Clean<Type> for hir::TraitRef {
1361     fn clean(&self, cx: &DocContext) -> Type {
1362         resolve_type(cx, self.path.clean(cx), self.ref_id)
1363     }
1364 }
1365
1366 impl Clean<PolyTrait> for hir::PolyTraitRef {
1367     fn clean(&self, cx: &DocContext) -> PolyTrait {
1368         PolyTrait {
1369             trait_: self.trait_ref.clean(cx),
1370             lifetimes: self.bound_lifetimes.clean(cx)
1371         }
1372     }
1373 }
1374
1375 impl Clean<Item> for hir::TraitItem {
1376     fn clean(&self, cx: &DocContext) -> Item {
1377         let inner = match self.node {
1378             hir::TraitItemKind::Const(ref ty, default) => {
1379                 AssociatedConstItem(ty.clean(cx),
1380                                     default.map(|e| print_const_expr(cx, e)))
1381             }
1382             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Provided(body)) => {
1383                 MethodItem((sig, body).clean(cx))
1384             }
1385             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Required(ref names)) => {
1386                 TyMethodItem(TyMethod {
1387                     unsafety: sig.unsafety.clone(),
1388                     decl: (&*sig.decl, &names[..]).clean(cx),
1389                     generics: sig.generics.clean(cx),
1390                     abi: sig.abi
1391                 })
1392             }
1393             hir::TraitItemKind::Type(ref bounds, ref default) => {
1394                 AssociatedTypeItem(bounds.clean(cx), default.clean(cx))
1395             }
1396         };
1397         Item {
1398             name: Some(self.name.clean(cx)),
1399             attrs: self.attrs.clean(cx),
1400             source: self.span.clean(cx),
1401             def_id: cx.tcx.hir.local_def_id(self.id),
1402             visibility: None,
1403             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
1404             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
1405             inner,
1406         }
1407     }
1408 }
1409
1410 impl Clean<Item> for hir::ImplItem {
1411     fn clean(&self, cx: &DocContext) -> Item {
1412         let inner = match self.node {
1413             hir::ImplItemKind::Const(ref ty, expr) => {
1414                 AssociatedConstItem(ty.clean(cx),
1415                                     Some(print_const_expr(cx, expr)))
1416             }
1417             hir::ImplItemKind::Method(ref sig, body) => {
1418                 MethodItem((sig, body).clean(cx))
1419             }
1420             hir::ImplItemKind::Type(ref ty) => TypedefItem(Typedef {
1421                 type_: ty.clean(cx),
1422                 generics: Generics {
1423                     lifetimes: Vec::new(),
1424                     type_params: Vec::new(),
1425                     where_predicates: Vec::new()
1426                 },
1427             }, true),
1428         };
1429         Item {
1430             name: Some(self.name.clean(cx)),
1431             source: self.span.clean(cx),
1432             attrs: self.attrs.clean(cx),
1433             def_id: cx.tcx.hir.local_def_id(self.id),
1434             visibility: self.vis.clean(cx),
1435             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
1436             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
1437             inner,
1438         }
1439     }
1440 }
1441
1442 impl<'tcx> Clean<Item> for ty::AssociatedItem {
1443     fn clean(&self, cx: &DocContext) -> Item {
1444         let inner = match self.kind {
1445             ty::AssociatedKind::Const => {
1446                 let ty = cx.tcx.type_of(self.def_id);
1447                 AssociatedConstItem(ty.clean(cx), None)
1448             }
1449             ty::AssociatedKind::Method => {
1450                 let generics = (cx.tcx.generics_of(self.def_id),
1451                                 &cx.tcx.predicates_of(self.def_id)).clean(cx);
1452                 let sig = cx.tcx.fn_sig(self.def_id);
1453                 let mut decl = (self.def_id, sig).clean(cx);
1454
1455                 if self.method_has_self_argument {
1456                     let self_ty = match self.container {
1457                         ty::ImplContainer(def_id) => {
1458                             cx.tcx.type_of(def_id)
1459                         }
1460                         ty::TraitContainer(_) => cx.tcx.mk_self_type()
1461                     };
1462                     let self_arg_ty = *sig.input(0).skip_binder();
1463                     if self_arg_ty == self_ty {
1464                         decl.inputs.values[0].type_ = Generic(String::from("Self"));
1465                     } else if let ty::TyRef(_, mt) = self_arg_ty.sty {
1466                         if mt.ty == self_ty {
1467                             match decl.inputs.values[0].type_ {
1468                                 BorrowedRef{ref mut type_, ..} => {
1469                                     **type_ = Generic(String::from("Self"))
1470                                 }
1471                                 _ => unreachable!(),
1472                             }
1473                         }
1474                     }
1475                 }
1476
1477                 let provided = match self.container {
1478                     ty::ImplContainer(_) => false,
1479                     ty::TraitContainer(_) => self.defaultness.has_value()
1480                 };
1481                 if provided {
1482                     MethodItem(Method {
1483                         unsafety: sig.unsafety(),
1484                         generics,
1485                         decl,
1486                         abi: sig.abi(),
1487
1488                         // trait methods cannot (currently, at least) be const
1489                         constness: hir::Constness::NotConst,
1490                     })
1491                 } else {
1492                     TyMethodItem(TyMethod {
1493                         unsafety: sig.unsafety(),
1494                         generics,
1495                         decl,
1496                         abi: sig.abi(),
1497                     })
1498                 }
1499             }
1500             ty::AssociatedKind::Type => {
1501                 let my_name = self.name.clean(cx);
1502
1503                 let mut bounds = if let ty::TraitContainer(did) = self.container {
1504                     // When loading a cross-crate associated type, the bounds for this type
1505                     // are actually located on the trait/impl itself, so we need to load
1506                     // all of the generics from there and then look for bounds that are
1507                     // applied to this associated type in question.
1508                     let predicates = cx.tcx.predicates_of(did);
1509                     let generics = (cx.tcx.generics_of(did), &predicates).clean(cx);
1510                     generics.where_predicates.iter().filter_map(|pred| {
1511                         let (name, self_type, trait_, bounds) = match *pred {
1512                             WherePredicate::BoundPredicate {
1513                                 ty: QPath { ref name, ref self_type, ref trait_ },
1514                                 ref bounds
1515                             } => (name, self_type, trait_, bounds),
1516                             _ => return None,
1517                         };
1518                         if *name != my_name { return None }
1519                         match **trait_ {
1520                             ResolvedPath { did, .. } if did == self.container.id() => {}
1521                             _ => return None,
1522                         }
1523                         match **self_type {
1524                             Generic(ref s) if *s == "Self" => {}
1525                             _ => return None,
1526                         }
1527                         Some(bounds)
1528                     }).flat_map(|i| i.iter().cloned()).collect::<Vec<_>>()
1529                 } else {
1530                     vec![]
1531                 };
1532
1533                 // Our Sized/?Sized bound didn't get handled when creating the generics
1534                 // because we didn't actually get our whole set of bounds until just now
1535                 // (some of them may have come from the trait). If we do have a sized
1536                 // bound, we remove it, and if we don't then we add the `?Sized` bound
1537                 // at the end.
1538                 match bounds.iter().position(|b| b.is_sized_bound(cx)) {
1539                     Some(i) => { bounds.remove(i); }
1540                     None => bounds.push(TyParamBound::maybe_sized(cx)),
1541                 }
1542
1543                 let ty = if self.defaultness.has_value() {
1544                     Some(cx.tcx.type_of(self.def_id))
1545                 } else {
1546                     None
1547                 };
1548
1549                 AssociatedTypeItem(bounds, ty.clean(cx))
1550             }
1551         };
1552
1553         Item {
1554             name: Some(self.name.clean(cx)),
1555             visibility: Some(Inherited),
1556             stability: get_stability(cx, self.def_id),
1557             deprecation: get_deprecation(cx, self.def_id),
1558             def_id: self.def_id,
1559             attrs: inline::load_attrs(cx, self.def_id),
1560             source: cx.tcx.def_span(self.def_id).clean(cx),
1561             inner,
1562         }
1563     }
1564 }
1565
1566 /// A trait reference, which may have higher ranked lifetimes.
1567 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1568 pub struct PolyTrait {
1569     pub trait_: Type,
1570     pub lifetimes: Vec<Lifetime>
1571 }
1572
1573 /// A representation of a Type suitable for hyperlinking purposes. Ideally one can get the original
1574 /// type out of the AST/TyCtxt given one of these, if more information is needed. Most importantly
1575 /// it does not preserve mutability or boxes.
1576 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1577 pub enum Type {
1578     /// structs/enums/traits (most that'd be an hir::TyPath)
1579     ResolvedPath {
1580         path: Path,
1581         typarams: Option<Vec<TyParamBound>>,
1582         did: DefId,
1583         /// true if is a `T::Name` path for associated types
1584         is_generic: bool,
1585     },
1586     /// For parameterized types, so the consumer of the JSON don't go
1587     /// looking for types which don't exist anywhere.
1588     Generic(String),
1589     /// Primitives are the fixed-size numeric types (plus int/usize/float), char,
1590     /// arrays, slices, and tuples.
1591     Primitive(PrimitiveType),
1592     /// extern "ABI" fn
1593     BareFunction(Box<BareFunctionDecl>),
1594     Tuple(Vec<Type>),
1595     Slice(Box<Type>),
1596     Array(Box<Type>, String),
1597     Never,
1598     Unique(Box<Type>),
1599     RawPointer(Mutability, Box<Type>),
1600     BorrowedRef {
1601         lifetime: Option<Lifetime>,
1602         mutability: Mutability,
1603         type_: Box<Type>,
1604     },
1605
1606     // <Type as Trait>::Name
1607     QPath {
1608         name: String,
1609         self_type: Box<Type>,
1610         trait_: Box<Type>
1611     },
1612
1613     // _
1614     Infer,
1615
1616     // impl TraitA+TraitB
1617     ImplTrait(Vec<TyParamBound>),
1618 }
1619
1620 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Copy, Debug)]
1621 pub enum PrimitiveType {
1622     Isize, I8, I16, I32, I64, I128,
1623     Usize, U8, U16, U32, U64, U128,
1624     F32, F64,
1625     Char,
1626     Bool,
1627     Str,
1628     Slice,
1629     Array,
1630     Tuple,
1631     Unit,
1632     RawPointer,
1633     Reference,
1634     Fn,
1635 }
1636
1637 #[derive(Clone, RustcEncodable, RustcDecodable, Copy, Debug)]
1638 pub enum TypeKind {
1639     Enum,
1640     Function,
1641     Module,
1642     Const,
1643     Static,
1644     Struct,
1645     Union,
1646     Trait,
1647     Variant,
1648     Typedef,
1649 }
1650
1651 pub trait GetDefId {
1652     fn def_id(&self) -> Option<DefId>;
1653 }
1654
1655 impl<T: GetDefId> GetDefId for Option<T> {
1656     fn def_id(&self) -> Option<DefId> {
1657         self.as_ref().and_then(|d| d.def_id())
1658     }
1659 }
1660
1661 impl Type {
1662     pub fn primitive_type(&self) -> Option<PrimitiveType> {
1663         match *self {
1664             Primitive(p) | BorrowedRef { type_: box Primitive(p), ..} => Some(p),
1665             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
1666             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
1667             Tuple(ref tys) => if tys.is_empty() {
1668                 Some(PrimitiveType::Unit)
1669             } else {
1670                 Some(PrimitiveType::Tuple)
1671             },
1672             RawPointer(..) => Some(PrimitiveType::RawPointer),
1673             BorrowedRef { type_: box Generic(..), .. } => Some(PrimitiveType::Reference),
1674             BareFunction(..) => Some(PrimitiveType::Fn),
1675             _ => None,
1676         }
1677     }
1678
1679     pub fn is_generic(&self) -> bool {
1680         match *self {
1681             ResolvedPath { is_generic, .. } => is_generic,
1682             _ => false,
1683         }
1684     }
1685
1686     pub fn is_self_type(&self) -> bool {
1687         match *self {
1688             Generic(ref name) => name == "Self",
1689             _ => false
1690         }
1691     }
1692
1693     pub fn generics(&self) -> Option<&[Type]> {
1694         match *self {
1695             ResolvedPath { ref path, .. } => {
1696                 path.segments.last().and_then(|seg| {
1697                     if let PathParameters::AngleBracketed { ref types, .. } = seg.params {
1698                         Some(&**types)
1699                     } else {
1700                         None
1701                     }
1702                 })
1703             }
1704             _ => None,
1705         }
1706     }
1707 }
1708
1709 impl GetDefId for Type {
1710     fn def_id(&self) -> Option<DefId> {
1711         match *self {
1712             ResolvedPath { did, .. } => Some(did),
1713             Primitive(p) => ::html::render::cache().primitive_locations.get(&p).cloned(),
1714             BorrowedRef { type_: box Generic(..), .. } =>
1715                 Primitive(PrimitiveType::Reference).def_id(),
1716             BorrowedRef { ref type_, .. } => type_.def_id(),
1717             Tuple(ref tys) => if tys.is_empty() {
1718                 Primitive(PrimitiveType::Unit).def_id()
1719             } else {
1720                 Primitive(PrimitiveType::Tuple).def_id()
1721             },
1722             BareFunction(..) => Primitive(PrimitiveType::Fn).def_id(),
1723             Slice(..) => Primitive(PrimitiveType::Slice).def_id(),
1724             Array(..) => Primitive(PrimitiveType::Array).def_id(),
1725             RawPointer(..) => Primitive(PrimitiveType::RawPointer).def_id(),
1726             QPath { ref self_type, .. } => self_type.def_id(),
1727             _ => None,
1728         }
1729     }
1730 }
1731
1732 impl PrimitiveType {
1733     fn from_str(s: &str) -> Option<PrimitiveType> {
1734         match s {
1735             "isize" => Some(PrimitiveType::Isize),
1736             "i8" => Some(PrimitiveType::I8),
1737             "i16" => Some(PrimitiveType::I16),
1738             "i32" => Some(PrimitiveType::I32),
1739             "i64" => Some(PrimitiveType::I64),
1740             "i128" => Some(PrimitiveType::I128),
1741             "usize" => Some(PrimitiveType::Usize),
1742             "u8" => Some(PrimitiveType::U8),
1743             "u16" => Some(PrimitiveType::U16),
1744             "u32" => Some(PrimitiveType::U32),
1745             "u64" => Some(PrimitiveType::U64),
1746             "u128" => Some(PrimitiveType::U128),
1747             "bool" => Some(PrimitiveType::Bool),
1748             "char" => Some(PrimitiveType::Char),
1749             "str" => Some(PrimitiveType::Str),
1750             "f32" => Some(PrimitiveType::F32),
1751             "f64" => Some(PrimitiveType::F64),
1752             "array" => Some(PrimitiveType::Array),
1753             "slice" => Some(PrimitiveType::Slice),
1754             "tuple" => Some(PrimitiveType::Tuple),
1755             "unit" => Some(PrimitiveType::Unit),
1756             "pointer" => Some(PrimitiveType::RawPointer),
1757             "reference" => Some(PrimitiveType::Reference),
1758             "fn" => Some(PrimitiveType::Fn),
1759             _ => None,
1760         }
1761     }
1762
1763     pub fn as_str(&self) -> &'static str {
1764         use self::PrimitiveType::*;
1765         match *self {
1766             Isize => "isize",
1767             I8 => "i8",
1768             I16 => "i16",
1769             I32 => "i32",
1770             I64 => "i64",
1771             I128 => "i128",
1772             Usize => "usize",
1773             U8 => "u8",
1774             U16 => "u16",
1775             U32 => "u32",
1776             U64 => "u64",
1777             U128 => "u128",
1778             F32 => "f32",
1779             F64 => "f64",
1780             Str => "str",
1781             Bool => "bool",
1782             Char => "char",
1783             Array => "array",
1784             Slice => "slice",
1785             Tuple => "tuple",
1786             Unit => "unit",
1787             RawPointer => "pointer",
1788             Reference => "reference",
1789             Fn => "fn",
1790         }
1791     }
1792
1793     pub fn to_url_str(&self) -> &'static str {
1794         self.as_str()
1795     }
1796 }
1797
1798 impl From<ast::IntTy> for PrimitiveType {
1799     fn from(int_ty: ast::IntTy) -> PrimitiveType {
1800         match int_ty {
1801             ast::IntTy::Is => PrimitiveType::Isize,
1802             ast::IntTy::I8 => PrimitiveType::I8,
1803             ast::IntTy::I16 => PrimitiveType::I16,
1804             ast::IntTy::I32 => PrimitiveType::I32,
1805             ast::IntTy::I64 => PrimitiveType::I64,
1806             ast::IntTy::I128 => PrimitiveType::I128,
1807         }
1808     }
1809 }
1810
1811 impl From<ast::UintTy> for PrimitiveType {
1812     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
1813         match uint_ty {
1814             ast::UintTy::Us => PrimitiveType::Usize,
1815             ast::UintTy::U8 => PrimitiveType::U8,
1816             ast::UintTy::U16 => PrimitiveType::U16,
1817             ast::UintTy::U32 => PrimitiveType::U32,
1818             ast::UintTy::U64 => PrimitiveType::U64,
1819             ast::UintTy::U128 => PrimitiveType::U128,
1820         }
1821     }
1822 }
1823
1824 impl From<ast::FloatTy> for PrimitiveType {
1825     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
1826         match float_ty {
1827             ast::FloatTy::F32 => PrimitiveType::F32,
1828             ast::FloatTy::F64 => PrimitiveType::F64,
1829         }
1830     }
1831 }
1832
1833 impl Clean<Type> for hir::Ty {
1834     fn clean(&self, cx: &DocContext) -> Type {
1835         use rustc::hir::*;
1836         match self.node {
1837             TyNever => Never,
1838             TyPtr(ref m) => RawPointer(m.mutbl.clean(cx), box m.ty.clean(cx)),
1839             TyRptr(ref l, ref m) => {
1840                 let lifetime = if l.is_elided() {
1841                     None
1842                 } else {
1843                     Some(l.clean(cx))
1844                 };
1845                 BorrowedRef {lifetime: lifetime, mutability: m.mutbl.clean(cx),
1846                              type_: box m.ty.clean(cx)}
1847             }
1848             TySlice(ref ty) => Slice(box ty.clean(cx)),
1849             TyArray(ref ty, n) => {
1850                 let def_id = cx.tcx.hir.body_owner_def_id(n);
1851                 let param_env = ty::ParamEnv::empty(Reveal::UserFacing);
1852                 let substs = Substs::identity_for_item(cx.tcx, def_id);
1853                 let n = cx.tcx.const_eval(param_env.and((def_id, substs))).unwrap();
1854                 let n = if let ConstVal::Integral(ConstInt::Usize(n)) = n.val {
1855                     n.to_string()
1856                 } else if let ConstVal::Unevaluated(def_id, _) = n.val {
1857                     if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
1858                         print_const_expr(cx, cx.tcx.hir.body_owned_by(node_id))
1859                     } else {
1860                         inline::print_inlined_const(cx, def_id)
1861                     }
1862                 } else {
1863                     format!("{:?}", n)
1864                 };
1865                 Array(box ty.clean(cx), n)
1866             },
1867             TyTup(ref tys) => Tuple(tys.clean(cx)),
1868             TyPath(hir::QPath::Resolved(None, ref path)) => {
1869                 if let Some(new_ty) = cx.ty_substs.borrow().get(&path.def).cloned() {
1870                     return new_ty;
1871                 }
1872
1873                 let mut alias = None;
1874                 if let Def::TyAlias(def_id) = path.def {
1875                     // Substitute private type aliases
1876                     if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
1877                         if !cx.access_levels.borrow().is_exported(def_id) {
1878                             alias = Some(&cx.tcx.hir.expect_item(node_id).node);
1879                         }
1880                     }
1881                 };
1882
1883                 if let Some(&hir::ItemTy(ref ty, ref generics)) = alias {
1884                     let provided_params = &path.segments.last().unwrap();
1885                     let mut ty_substs = FxHashMap();
1886                     let mut lt_substs = FxHashMap();
1887                     provided_params.with_parameters(|provided_params| {
1888                         for (i, ty_param) in generics.ty_params.iter().enumerate() {
1889                             let ty_param_def = Def::TyParam(cx.tcx.hir.local_def_id(ty_param.id));
1890                             if let Some(ty) = provided_params.types.get(i).cloned() {
1891                                 ty_substs.insert(ty_param_def, ty.unwrap().clean(cx));
1892                             } else if let Some(default) = ty_param.default.clone() {
1893                                 ty_substs.insert(ty_param_def, default.unwrap().clean(cx));
1894                             }
1895                         }
1896                         for (i, lt_param) in generics.lifetimes.iter().enumerate() {
1897                             if let Some(lt) = provided_params.lifetimes.get(i).cloned() {
1898                                 if !lt.is_elided() {
1899                                     let lt_def_id = cx.tcx.hir.local_def_id(lt_param.lifetime.id);
1900                                     lt_substs.insert(lt_def_id, lt.clean(cx));
1901                                 }
1902                             }
1903                         }
1904                     });
1905                     return cx.enter_alias(ty_substs, lt_substs, || ty.clean(cx));
1906                 }
1907                 resolve_type(cx, path.clean(cx), self.id)
1908             }
1909             TyPath(hir::QPath::Resolved(Some(ref qself), ref p)) => {
1910                 let mut segments: Vec<_> = p.segments.clone().into();
1911                 segments.pop();
1912                 let trait_path = hir::Path {
1913                     span: p.span,
1914                     def: Def::Trait(cx.tcx.associated_item(p.def.def_id()).container.id()),
1915                     segments: segments.into(),
1916                 };
1917                 Type::QPath {
1918                     name: p.segments.last().unwrap().name.clean(cx),
1919                     self_type: box qself.clean(cx),
1920                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
1921                 }
1922             }
1923             TyPath(hir::QPath::TypeRelative(ref qself, ref segment)) => {
1924                 let mut def = Def::Err;
1925                 let ty = hir_ty_to_ty(cx.tcx, self);
1926                 if let ty::TyProjection(proj) = ty.sty {
1927                     def = Def::Trait(proj.trait_ref(cx.tcx).def_id);
1928                 }
1929                 let trait_path = hir::Path {
1930                     span: self.span,
1931                     def,
1932                     segments: vec![].into(),
1933                 };
1934                 Type::QPath {
1935                     name: segment.name.clean(cx),
1936                     self_type: box qself.clean(cx),
1937                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
1938                 }
1939             }
1940             TyTraitObject(ref bounds, ref lifetime) => {
1941                 match bounds[0].clean(cx).trait_ {
1942                     ResolvedPath { path, typarams: None, did, is_generic } => {
1943                         let mut bounds: Vec<_> = bounds[1..].iter().map(|bound| {
1944                             TraitBound(bound.clean(cx), hir::TraitBoundModifier::None)
1945                         }).collect();
1946                         if !lifetime.is_elided() {
1947                             bounds.push(RegionBound(lifetime.clean(cx)));
1948                         }
1949                         ResolvedPath {
1950                             path,
1951                             typarams: Some(bounds),
1952                             did,
1953                             is_generic,
1954                         }
1955                     }
1956                     _ => Infer // shouldn't happen
1957                 }
1958             }
1959             TyBareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
1960             TyImplTrait(ref bounds) => ImplTrait(bounds.clean(cx)),
1961             TyInfer | TyErr => Infer,
1962             TyTypeof(..) => panic!("Unimplemented type {:?}", self.node),
1963         }
1964     }
1965 }
1966
1967 impl<'tcx> Clean<Type> for Ty<'tcx> {
1968     fn clean(&self, cx: &DocContext) -> Type {
1969         match self.sty {
1970             ty::TyNever => Never,
1971             ty::TyBool => Primitive(PrimitiveType::Bool),
1972             ty::TyChar => Primitive(PrimitiveType::Char),
1973             ty::TyInt(int_ty) => Primitive(int_ty.into()),
1974             ty::TyUint(uint_ty) => Primitive(uint_ty.into()),
1975             ty::TyFloat(float_ty) => Primitive(float_ty.into()),
1976             ty::TyStr => Primitive(PrimitiveType::Str),
1977             ty::TySlice(ty) => Slice(box ty.clean(cx)),
1978             ty::TyArray(ty, n) => {
1979                 let n = if let ConstVal::Integral(ConstInt::Usize(n)) = n.val {
1980                     n.to_string()
1981                 } else if let ConstVal::Unevaluated(def_id, _) = n.val {
1982                     if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
1983                         print_const_expr(cx, cx.tcx.hir.body_owned_by(node_id))
1984                     } else {
1985                         inline::print_inlined_const(cx, def_id)
1986                     }
1987                 } else {
1988                     format!("{:?}", n)
1989                 };
1990                 Array(box ty.clean(cx), n)
1991             }
1992             ty::TyRawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
1993             ty::TyRef(r, mt) => BorrowedRef {
1994                 lifetime: r.clean(cx),
1995                 mutability: mt.mutbl.clean(cx),
1996                 type_: box mt.ty.clean(cx),
1997             },
1998             ty::TyFnDef(..) |
1999             ty::TyFnPtr(_) => {
2000                 let ty = cx.tcx.lift(self).unwrap();
2001                 let sig = ty.fn_sig(cx.tcx);
2002                 BareFunction(box BareFunctionDecl {
2003                     unsafety: sig.unsafety(),
2004                     generics: Generics {
2005                         lifetimes: Vec::new(),
2006                         type_params: Vec::new(),
2007                         where_predicates: Vec::new()
2008                     },
2009                     decl: (cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID), sig).clean(cx),
2010                     abi: sig.abi(),
2011                 })
2012             }
2013             ty::TyAdt(def, substs) => {
2014                 let did = def.did;
2015                 let kind = match def.adt_kind() {
2016                     AdtKind::Struct => TypeKind::Struct,
2017                     AdtKind::Union => TypeKind::Union,
2018                     AdtKind::Enum => TypeKind::Enum,
2019                 };
2020                 inline::record_extern_fqn(cx, did, kind);
2021                 let path = external_path(cx, &cx.tcx.item_name(did),
2022                                          None, false, vec![], substs);
2023                 ResolvedPath {
2024                     path,
2025                     typarams: None,
2026                     did,
2027                     is_generic: false,
2028                 }
2029             }
2030             ty::TyDynamic(ref obj, ref reg) => {
2031                 if let Some(principal) = obj.principal() {
2032                     let did = principal.def_id();
2033                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
2034
2035                     let mut typarams = vec![];
2036                     reg.clean(cx).map(|b| typarams.push(RegionBound(b)));
2037                     for did in obj.auto_traits() {
2038                         let empty = cx.tcx.intern_substs(&[]);
2039                         let path = external_path(cx, &cx.tcx.item_name(did),
2040                             Some(did), false, vec![], empty);
2041                         inline::record_extern_fqn(cx, did, TypeKind::Trait);
2042                         let bound = TraitBound(PolyTrait {
2043                             trait_: ResolvedPath {
2044                                 path,
2045                                 typarams: None,
2046                                 did,
2047                                 is_generic: false,
2048                             },
2049                             lifetimes: vec![]
2050                         }, hir::TraitBoundModifier::None);
2051                         typarams.push(bound);
2052                     }
2053
2054                     let mut bindings = vec![];
2055                     for ty::Binder(ref pb) in obj.projection_bounds() {
2056                         bindings.push(TypeBinding {
2057                             name: cx.tcx.associated_item(pb.item_def_id).name.clean(cx),
2058                             ty: pb.ty.clean(cx)
2059                         });
2060                     }
2061
2062                     let path = external_path(cx, &cx.tcx.item_name(did), Some(did),
2063                         false, bindings, principal.0.substs);
2064                     ResolvedPath {
2065                         path,
2066                         typarams: Some(typarams),
2067                         did,
2068                         is_generic: false,
2069                     }
2070                 } else {
2071                     Never
2072                 }
2073             }
2074             ty::TyTuple(ref t, _) => Tuple(t.clean(cx)),
2075
2076             ty::TyProjection(ref data) => data.clean(cx),
2077
2078             ty::TyParam(ref p) => Generic(p.name.to_string()),
2079
2080             ty::TyAnon(def_id, substs) => {
2081                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
2082                 // by looking up the projections associated with the def_id.
2083                 let predicates_of = cx.tcx.predicates_of(def_id);
2084                 let substs = cx.tcx.lift(&substs).unwrap();
2085                 let bounds = predicates_of.instantiate(cx.tcx, substs);
2086                 ImplTrait(bounds.predicates.into_iter().filter_map(|predicate| {
2087                     predicate.to_opt_poly_trait_ref().clean(cx)
2088                 }).collect())
2089             }
2090
2091             ty::TyClosure(..) | ty::TyGenerator(..) => Tuple(vec![]), // FIXME(pcwalton)
2092
2093             ty::TyInfer(..) => panic!("TyInfer"),
2094             ty::TyError => panic!("TyError"),
2095         }
2096     }
2097 }
2098
2099 impl Clean<Item> for hir::StructField {
2100     fn clean(&self, cx: &DocContext) -> Item {
2101         Item {
2102             name: Some(self.name).clean(cx),
2103             attrs: self.attrs.clean(cx),
2104             source: self.span.clean(cx),
2105             visibility: self.vis.clean(cx),
2106             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2107             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2108             def_id: cx.tcx.hir.local_def_id(self.id),
2109             inner: StructFieldItem(self.ty.clean(cx)),
2110         }
2111     }
2112 }
2113
2114 impl<'tcx> Clean<Item> for ty::FieldDef {
2115     fn clean(&self, cx: &DocContext) -> Item {
2116         Item {
2117             name: Some(self.name).clean(cx),
2118             attrs: cx.tcx.get_attrs(self.did).clean(cx),
2119             source: cx.tcx.def_span(self.did).clean(cx),
2120             visibility: self.vis.clean(cx),
2121             stability: get_stability(cx, self.did),
2122             deprecation: get_deprecation(cx, self.did),
2123             def_id: self.did,
2124             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
2125         }
2126     }
2127 }
2128
2129 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug)]
2130 pub enum Visibility {
2131     Public,
2132     Inherited,
2133 }
2134
2135 impl Clean<Option<Visibility>> for hir::Visibility {
2136     fn clean(&self, _: &DocContext) -> Option<Visibility> {
2137         Some(if *self == hir::Visibility::Public { Public } else { Inherited })
2138     }
2139 }
2140
2141 impl Clean<Option<Visibility>> for ty::Visibility {
2142     fn clean(&self, _: &DocContext) -> Option<Visibility> {
2143         Some(if *self == ty::Visibility::Public { Public } else { Inherited })
2144     }
2145 }
2146
2147 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2148 pub struct Struct {
2149     pub struct_type: doctree::StructType,
2150     pub generics: Generics,
2151     pub fields: Vec<Item>,
2152     pub fields_stripped: bool,
2153 }
2154
2155 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2156 pub struct Union {
2157     pub struct_type: doctree::StructType,
2158     pub generics: Generics,
2159     pub fields: Vec<Item>,
2160     pub fields_stripped: bool,
2161 }
2162
2163 impl Clean<Item> for doctree::Struct {
2164     fn clean(&self, cx: &DocContext) -> Item {
2165         Item {
2166             name: Some(self.name.clean(cx)),
2167             attrs: self.attrs.clean(cx),
2168             source: self.whence.clean(cx),
2169             def_id: cx.tcx.hir.local_def_id(self.id),
2170             visibility: self.vis.clean(cx),
2171             stability: self.stab.clean(cx),
2172             deprecation: self.depr.clean(cx),
2173             inner: StructItem(Struct {
2174                 struct_type: self.struct_type,
2175                 generics: self.generics.clean(cx),
2176                 fields: self.fields.clean(cx),
2177                 fields_stripped: false,
2178             }),
2179         }
2180     }
2181 }
2182
2183 impl Clean<Item> for doctree::Union {
2184     fn clean(&self, cx: &DocContext) -> Item {
2185         Item {
2186             name: Some(self.name.clean(cx)),
2187             attrs: self.attrs.clean(cx),
2188             source: self.whence.clean(cx),
2189             def_id: cx.tcx.hir.local_def_id(self.id),
2190             visibility: self.vis.clean(cx),
2191             stability: self.stab.clean(cx),
2192             deprecation: self.depr.clean(cx),
2193             inner: UnionItem(Union {
2194                 struct_type: self.struct_type,
2195                 generics: self.generics.clean(cx),
2196                 fields: self.fields.clean(cx),
2197                 fields_stripped: false,
2198             }),
2199         }
2200     }
2201 }
2202
2203 /// This is a more limited form of the standard Struct, different in that
2204 /// it lacks the things most items have (name, id, parameterization). Found
2205 /// only as a variant in an enum.
2206 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2207 pub struct VariantStruct {
2208     pub struct_type: doctree::StructType,
2209     pub fields: Vec<Item>,
2210     pub fields_stripped: bool,
2211 }
2212
2213 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
2214     fn clean(&self, cx: &DocContext) -> VariantStruct {
2215         VariantStruct {
2216             struct_type: doctree::struct_type_from_def(self),
2217             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
2218             fields_stripped: false,
2219         }
2220     }
2221 }
2222
2223 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2224 pub struct Enum {
2225     pub variants: Vec<Item>,
2226     pub generics: Generics,
2227     pub variants_stripped: bool,
2228 }
2229
2230 impl Clean<Item> for doctree::Enum {
2231     fn clean(&self, cx: &DocContext) -> Item {
2232         Item {
2233             name: Some(self.name.clean(cx)),
2234             attrs: self.attrs.clean(cx),
2235             source: self.whence.clean(cx),
2236             def_id: cx.tcx.hir.local_def_id(self.id),
2237             visibility: self.vis.clean(cx),
2238             stability: self.stab.clean(cx),
2239             deprecation: self.depr.clean(cx),
2240             inner: EnumItem(Enum {
2241                 variants: self.variants.clean(cx),
2242                 generics: self.generics.clean(cx),
2243                 variants_stripped: false,
2244             }),
2245         }
2246     }
2247 }
2248
2249 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2250 pub struct Variant {
2251     pub kind: VariantKind,
2252 }
2253
2254 impl Clean<Item> for doctree::Variant {
2255     fn clean(&self, cx: &DocContext) -> Item {
2256         Item {
2257             name: Some(self.name.clean(cx)),
2258             attrs: self.attrs.clean(cx),
2259             source: self.whence.clean(cx),
2260             visibility: None,
2261             stability: self.stab.clean(cx),
2262             deprecation: self.depr.clean(cx),
2263             def_id: cx.tcx.hir.local_def_id(self.def.id()),
2264             inner: VariantItem(Variant {
2265                 kind: self.def.clean(cx),
2266             }),
2267         }
2268     }
2269 }
2270
2271 impl<'tcx> Clean<Item> for ty::VariantDef {
2272     fn clean(&self, cx: &DocContext) -> Item {
2273         let kind = match self.ctor_kind {
2274             CtorKind::Const => VariantKind::CLike,
2275             CtorKind::Fn => {
2276                 VariantKind::Tuple(
2277                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
2278                 )
2279             }
2280             CtorKind::Fictive => {
2281                 VariantKind::Struct(VariantStruct {
2282                     struct_type: doctree::Plain,
2283                     fields_stripped: false,
2284                     fields: self.fields.iter().map(|field| {
2285                         Item {
2286                             source: cx.tcx.def_span(field.did).clean(cx),
2287                             name: Some(field.name.clean(cx)),
2288                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
2289                             visibility: field.vis.clean(cx),
2290                             def_id: field.did,
2291                             stability: get_stability(cx, field.did),
2292                             deprecation: get_deprecation(cx, field.did),
2293                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
2294                         }
2295                     }).collect()
2296                 })
2297             }
2298         };
2299         Item {
2300             name: Some(self.name.clean(cx)),
2301             attrs: inline::load_attrs(cx, self.did),
2302             source: cx.tcx.def_span(self.did).clean(cx),
2303             visibility: Some(Inherited),
2304             def_id: self.did,
2305             inner: VariantItem(Variant { kind: kind }),
2306             stability: get_stability(cx, self.did),
2307             deprecation: get_deprecation(cx, self.did),
2308         }
2309     }
2310 }
2311
2312 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2313 pub enum VariantKind {
2314     CLike,
2315     Tuple(Vec<Type>),
2316     Struct(VariantStruct),
2317 }
2318
2319 impl Clean<VariantKind> for hir::VariantData {
2320     fn clean(&self, cx: &DocContext) -> VariantKind {
2321         if self.is_struct() {
2322             VariantKind::Struct(self.clean(cx))
2323         } else if self.is_unit() {
2324             VariantKind::CLike
2325         } else {
2326             VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect())
2327         }
2328     }
2329 }
2330
2331 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2332 pub struct Span {
2333     pub filename: String,
2334     pub loline: usize,
2335     pub locol: usize,
2336     pub hiline: usize,
2337     pub hicol: usize,
2338 }
2339
2340 impl Span {
2341     fn empty() -> Span {
2342         Span {
2343             filename: "".to_string(),
2344             loline: 0, locol: 0,
2345             hiline: 0, hicol: 0,
2346         }
2347     }
2348 }
2349
2350 impl Clean<Span> for syntax_pos::Span {
2351     fn clean(&self, cx: &DocContext) -> Span {
2352         if *self == DUMMY_SP {
2353             return Span::empty();
2354         }
2355
2356         let cm = cx.sess().codemap();
2357         let filename = cm.span_to_filename(*self);
2358         let lo = cm.lookup_char_pos(self.lo());
2359         let hi = cm.lookup_char_pos(self.hi());
2360         Span {
2361             filename: filename.to_string(),
2362             loline: lo.line,
2363             locol: lo.col.to_usize(),
2364             hiline: hi.line,
2365             hicol: hi.col.to_usize(),
2366         }
2367     }
2368 }
2369
2370 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2371 pub struct Path {
2372     pub global: bool,
2373     pub def: Def,
2374     pub segments: Vec<PathSegment>,
2375 }
2376
2377 impl Path {
2378     pub fn singleton(name: String) -> Path {
2379         Path {
2380             global: false,
2381             def: Def::Err,
2382             segments: vec![PathSegment {
2383                 name,
2384                 params: PathParameters::AngleBracketed {
2385                     lifetimes: Vec::new(),
2386                     types: Vec::new(),
2387                     bindings: Vec::new()
2388                 }
2389             }]
2390         }
2391     }
2392
2393     pub fn last_name(&self) -> &str {
2394         self.segments.last().unwrap().name.as_str()
2395     }
2396 }
2397
2398 impl Clean<Path> for hir::Path {
2399     fn clean(&self, cx: &DocContext) -> Path {
2400         Path {
2401             global: self.is_global(),
2402             def: self.def,
2403             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
2404         }
2405     }
2406 }
2407
2408 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2409 pub enum PathParameters {
2410     AngleBracketed {
2411         lifetimes: Vec<Lifetime>,
2412         types: Vec<Type>,
2413         bindings: Vec<TypeBinding>,
2414     },
2415     Parenthesized {
2416         inputs: Vec<Type>,
2417         output: Option<Type>,
2418     }
2419 }
2420
2421 impl Clean<PathParameters> for hir::PathParameters {
2422     fn clean(&self, cx: &DocContext) -> PathParameters {
2423         if self.parenthesized {
2424             let output = self.bindings[0].ty.clean(cx);
2425             PathParameters::Parenthesized {
2426                 inputs: self.inputs().clean(cx),
2427                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
2428             }
2429         } else {
2430             PathParameters::AngleBracketed {
2431                 lifetimes: if self.lifetimes.iter().all(|lt| lt.is_elided()) {
2432                     vec![]
2433                 } else {
2434                     self.lifetimes.clean(cx)
2435                 },
2436                 types: self.types.clean(cx),
2437                 bindings: self.bindings.clean(cx),
2438             }
2439         }
2440     }
2441 }
2442
2443 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2444 pub struct PathSegment {
2445     pub name: String,
2446     pub params: PathParameters,
2447 }
2448
2449 impl Clean<PathSegment> for hir::PathSegment {
2450     fn clean(&self, cx: &DocContext) -> PathSegment {
2451         PathSegment {
2452             name: self.name.clean(cx),
2453             params: self.with_parameters(|parameters| parameters.clean(cx))
2454         }
2455     }
2456 }
2457
2458 fn qpath_to_string(p: &hir::QPath) -> String {
2459     let segments = match *p {
2460         hir::QPath::Resolved(_, ref path) => &path.segments,
2461         hir::QPath::TypeRelative(_, ref segment) => return segment.name.to_string(),
2462     };
2463
2464     let mut s = String::new();
2465     for (i, seg) in segments.iter().enumerate() {
2466         if i > 0 {
2467             s.push_str("::");
2468         }
2469         if seg.name != keywords::CrateRoot.name() {
2470             s.push_str(&*seg.name.as_str());
2471         }
2472     }
2473     s
2474 }
2475
2476 impl Clean<String> for ast::Name {
2477     fn clean(&self, _: &DocContext) -> String {
2478         self.to_string()
2479     }
2480 }
2481
2482 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2483 pub struct Typedef {
2484     pub type_: Type,
2485     pub generics: Generics,
2486 }
2487
2488 impl Clean<Item> for doctree::Typedef {
2489     fn clean(&self, cx: &DocContext) -> Item {
2490         Item {
2491             name: Some(self.name.clean(cx)),
2492             attrs: self.attrs.clean(cx),
2493             source: self.whence.clean(cx),
2494             def_id: cx.tcx.hir.local_def_id(self.id.clone()),
2495             visibility: self.vis.clean(cx),
2496             stability: self.stab.clean(cx),
2497             deprecation: self.depr.clean(cx),
2498             inner: TypedefItem(Typedef {
2499                 type_: self.ty.clean(cx),
2500                 generics: self.gen.clean(cx),
2501             }, false),
2502         }
2503     }
2504 }
2505
2506 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2507 pub struct BareFunctionDecl {
2508     pub unsafety: hir::Unsafety,
2509     pub generics: Generics,
2510     pub decl: FnDecl,
2511     pub abi: Abi,
2512 }
2513
2514 impl Clean<BareFunctionDecl> for hir::BareFnTy {
2515     fn clean(&self, cx: &DocContext) -> BareFunctionDecl {
2516         BareFunctionDecl {
2517             unsafety: self.unsafety,
2518             generics: Generics {
2519                 lifetimes: self.lifetimes.clean(cx),
2520                 type_params: Vec::new(),
2521                 where_predicates: Vec::new()
2522             },
2523             decl: (&*self.decl, &self.arg_names[..]).clean(cx),
2524             abi: self.abi,
2525         }
2526     }
2527 }
2528
2529 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2530 pub struct Static {
2531     pub type_: Type,
2532     pub mutability: Mutability,
2533     /// It's useful to have the value of a static documented, but I have no
2534     /// desire to represent expressions (that'd basically be all of the AST,
2535     /// which is huge!). So, have a string.
2536     pub expr: String,
2537 }
2538
2539 impl Clean<Item> for doctree::Static {
2540     fn clean(&self, cx: &DocContext) -> Item {
2541         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
2542         Item {
2543             name: Some(self.name.clean(cx)),
2544             attrs: self.attrs.clean(cx),
2545             source: self.whence.clean(cx),
2546             def_id: cx.tcx.hir.local_def_id(self.id),
2547             visibility: self.vis.clean(cx),
2548             stability: self.stab.clean(cx),
2549             deprecation: self.depr.clean(cx),
2550             inner: StaticItem(Static {
2551                 type_: self.type_.clean(cx),
2552                 mutability: self.mutability.clean(cx),
2553                 expr: print_const_expr(cx, self.expr),
2554             }),
2555         }
2556     }
2557 }
2558
2559 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2560 pub struct Constant {
2561     pub type_: Type,
2562     pub expr: String,
2563 }
2564
2565 impl Clean<Item> for doctree::Constant {
2566     fn clean(&self, cx: &DocContext) -> Item {
2567         Item {
2568             name: Some(self.name.clean(cx)),
2569             attrs: self.attrs.clean(cx),
2570             source: self.whence.clean(cx),
2571             def_id: cx.tcx.hir.local_def_id(self.id),
2572             visibility: self.vis.clean(cx),
2573             stability: self.stab.clean(cx),
2574             deprecation: self.depr.clean(cx),
2575             inner: ConstantItem(Constant {
2576                 type_: self.type_.clean(cx),
2577                 expr: print_const_expr(cx, self.expr),
2578             }),
2579         }
2580     }
2581 }
2582
2583 #[derive(Debug, Clone, RustcEncodable, RustcDecodable, PartialEq, Copy)]
2584 pub enum Mutability {
2585     Mutable,
2586     Immutable,
2587 }
2588
2589 impl Clean<Mutability> for hir::Mutability {
2590     fn clean(&self, _: &DocContext) -> Mutability {
2591         match self {
2592             &hir::MutMutable => Mutable,
2593             &hir::MutImmutable => Immutable,
2594         }
2595     }
2596 }
2597
2598 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Copy, Debug)]
2599 pub enum ImplPolarity {
2600     Positive,
2601     Negative,
2602 }
2603
2604 impl Clean<ImplPolarity> for hir::ImplPolarity {
2605     fn clean(&self, _: &DocContext) -> ImplPolarity {
2606         match self {
2607             &hir::ImplPolarity::Positive => ImplPolarity::Positive,
2608             &hir::ImplPolarity::Negative => ImplPolarity::Negative,
2609         }
2610     }
2611 }
2612
2613 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2614 pub struct Impl {
2615     pub unsafety: hir::Unsafety,
2616     pub generics: Generics,
2617     pub provided_trait_methods: FxHashSet<String>,
2618     pub trait_: Option<Type>,
2619     pub for_: Type,
2620     pub items: Vec<Item>,
2621     pub polarity: Option<ImplPolarity>,
2622 }
2623
2624 impl Clean<Vec<Item>> for doctree::Impl {
2625     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2626         let mut ret = Vec::new();
2627         let trait_ = self.trait_.clean(cx);
2628         let items = self.items.clean(cx);
2629
2630         // If this impl block is an implementation of the Deref trait, then we
2631         // need to try inlining the target's inherent impl blocks as well.
2632         if trait_.def_id() == cx.tcx.lang_items().deref_trait() {
2633             build_deref_target_impls(cx, &items, &mut ret);
2634         }
2635
2636         let provided = trait_.def_id().map(|did| {
2637             cx.tcx.provided_trait_methods(did)
2638                   .into_iter()
2639                   .map(|meth| meth.name.to_string())
2640                   .collect()
2641         }).unwrap_or(FxHashSet());
2642
2643         ret.push(Item {
2644             name: None,
2645             attrs: self.attrs.clean(cx),
2646             source: self.whence.clean(cx),
2647             def_id: cx.tcx.hir.local_def_id(self.id),
2648             visibility: self.vis.clean(cx),
2649             stability: self.stab.clean(cx),
2650             deprecation: self.depr.clean(cx),
2651             inner: ImplItem(Impl {
2652                 unsafety: self.unsafety,
2653                 generics: self.generics.clean(cx),
2654                 provided_trait_methods: provided,
2655                 trait_,
2656                 for_: self.for_.clean(cx),
2657                 items,
2658                 polarity: Some(self.polarity.clean(cx)),
2659             }),
2660         });
2661         ret
2662     }
2663 }
2664
2665 fn build_deref_target_impls(cx: &DocContext,
2666                             items: &[Item],
2667                             ret: &mut Vec<Item>) {
2668     use self::PrimitiveType::*;
2669     let tcx = cx.tcx;
2670
2671     for item in items {
2672         let target = match item.inner {
2673             TypedefItem(ref t, true) => &t.type_,
2674             _ => continue,
2675         };
2676         let primitive = match *target {
2677             ResolvedPath { did, .. } if did.is_local() => continue,
2678             ResolvedPath { did, .. } => {
2679                 ret.extend(inline::build_impls(cx, did));
2680                 continue
2681             }
2682             _ => match target.primitive_type() {
2683                 Some(prim) => prim,
2684                 None => continue,
2685             }
2686         };
2687         let did = match primitive {
2688             Isize => tcx.lang_items().isize_impl(),
2689             I8 => tcx.lang_items().i8_impl(),
2690             I16 => tcx.lang_items().i16_impl(),
2691             I32 => tcx.lang_items().i32_impl(),
2692             I64 => tcx.lang_items().i64_impl(),
2693             I128 => tcx.lang_items().i128_impl(),
2694             Usize => tcx.lang_items().usize_impl(),
2695             U8 => tcx.lang_items().u8_impl(),
2696             U16 => tcx.lang_items().u16_impl(),
2697             U32 => tcx.lang_items().u32_impl(),
2698             U64 => tcx.lang_items().u64_impl(),
2699             U128 => tcx.lang_items().u128_impl(),
2700             F32 => tcx.lang_items().f32_impl(),
2701             F64 => tcx.lang_items().f64_impl(),
2702             Char => tcx.lang_items().char_impl(),
2703             Bool => None,
2704             Str => tcx.lang_items().str_impl(),
2705             Slice => tcx.lang_items().slice_impl(),
2706             Array => tcx.lang_items().slice_impl(),
2707             Tuple => None,
2708             Unit => None,
2709             RawPointer => tcx.lang_items().const_ptr_impl(),
2710             Reference => None,
2711             Fn => None,
2712         };
2713         if let Some(did) = did {
2714             if !did.is_local() {
2715                 inline::build_impl(cx, did, ret);
2716             }
2717         }
2718     }
2719 }
2720
2721 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2722 pub struct DefaultImpl {
2723     pub unsafety: hir::Unsafety,
2724     pub trait_: Type,
2725 }
2726
2727 impl Clean<Item> for doctree::DefaultImpl {
2728     fn clean(&self, cx: &DocContext) -> Item {
2729         Item {
2730             name: None,
2731             attrs: self.attrs.clean(cx),
2732             source: self.whence.clean(cx),
2733             def_id: cx.tcx.hir.local_def_id(self.id),
2734             visibility: Some(Public),
2735             stability: None,
2736             deprecation: None,
2737             inner: DefaultImplItem(DefaultImpl {
2738                 unsafety: self.unsafety,
2739                 trait_: self.trait_.clean(cx),
2740             }),
2741         }
2742     }
2743 }
2744
2745 impl Clean<Item> for doctree::ExternCrate {
2746     fn clean(&self, cx: &DocContext) -> Item {
2747         Item {
2748             name: None,
2749             attrs: self.attrs.clean(cx),
2750             source: self.whence.clean(cx),
2751             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
2752             visibility: self.vis.clean(cx),
2753             stability: None,
2754             deprecation: None,
2755             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
2756         }
2757     }
2758 }
2759
2760 impl Clean<Vec<Item>> for doctree::Import {
2761     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2762         // We consider inlining the documentation of `pub use` statements, but we
2763         // forcefully don't inline if this is not public or if the
2764         // #[doc(no_inline)] attribute is present.
2765         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
2766         let denied = self.vis != hir::Public || self.attrs.iter().any(|a| {
2767             a.name().unwrap() == "doc" && match a.meta_item_list() {
2768                 Some(l) => attr::list_contains_name(&l, "no_inline") ||
2769                            attr::list_contains_name(&l, "hidden"),
2770                 None => false,
2771             }
2772         });
2773         let path = self.path.clean(cx);
2774         let inner = if self.glob {
2775             Import::Glob(resolve_use_source(cx, path))
2776         } else {
2777             let name = self.name;
2778             if !denied {
2779                 if let Some(items) = inline::try_inline(cx, path.def, name) {
2780                     return items;
2781                 }
2782             }
2783             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
2784         };
2785         vec![Item {
2786             name: None,
2787             attrs: self.attrs.clean(cx),
2788             source: self.whence.clean(cx),
2789             def_id: cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID),
2790             visibility: self.vis.clean(cx),
2791             stability: None,
2792             deprecation: None,
2793             inner: ImportItem(inner)
2794         }]
2795     }
2796 }
2797
2798 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2799 pub enum Import {
2800     // use source as str;
2801     Simple(String, ImportSource),
2802     // use source::*;
2803     Glob(ImportSource)
2804 }
2805
2806 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2807 pub struct ImportSource {
2808     pub path: Path,
2809     pub did: Option<DefId>,
2810 }
2811
2812 impl Clean<Vec<Item>> for hir::ForeignMod {
2813     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2814         let mut items = self.items.clean(cx);
2815         for item in &mut items {
2816             if let ForeignFunctionItem(ref mut f) = item.inner {
2817                 f.abi = self.abi;
2818             }
2819         }
2820         items
2821     }
2822 }
2823
2824 impl Clean<Item> for hir::ForeignItem {
2825     fn clean(&self, cx: &DocContext) -> Item {
2826         let inner = match self.node {
2827             hir::ForeignItemFn(ref decl, ref names, ref generics) => {
2828                 ForeignFunctionItem(Function {
2829                     decl: (&**decl, &names[..]).clean(cx),
2830                     generics: generics.clean(cx),
2831                     unsafety: hir::Unsafety::Unsafe,
2832                     abi: Abi::Rust,
2833                     constness: hir::Constness::NotConst,
2834                 })
2835             }
2836             hir::ForeignItemStatic(ref ty, mutbl) => {
2837                 ForeignStaticItem(Static {
2838                     type_: ty.clean(cx),
2839                     mutability: if mutbl {Mutable} else {Immutable},
2840                     expr: "".to_string(),
2841                 })
2842             }
2843         };
2844         Item {
2845             name: Some(self.name.clean(cx)),
2846             attrs: self.attrs.clean(cx),
2847             source: self.span.clean(cx),
2848             def_id: cx.tcx.hir.local_def_id(self.id),
2849             visibility: self.vis.clean(cx),
2850             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2851             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2852             inner,
2853         }
2854     }
2855 }
2856
2857 // Utilities
2858
2859 trait ToSource {
2860     fn to_src(&self, cx: &DocContext) -> String;
2861 }
2862
2863 impl ToSource for syntax_pos::Span {
2864     fn to_src(&self, cx: &DocContext) -> String {
2865         debug!("converting span {:?} to snippet", self.clean(cx));
2866         let sn = match cx.sess().codemap().span_to_snippet(*self) {
2867             Ok(x) => x.to_string(),
2868             Err(_) => "".to_string()
2869         };
2870         debug!("got snippet {}", sn);
2871         sn
2872     }
2873 }
2874
2875 fn name_from_pat(p: &hir::Pat) -> String {
2876     use rustc::hir::*;
2877     debug!("Trying to get a name from pattern: {:?}", p);
2878
2879     match p.node {
2880         PatKind::Wild => "_".to_string(),
2881         PatKind::Binding(_, _, ref p, _) => p.node.to_string(),
2882         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
2883         PatKind::Struct(ref name, ref fields, etc) => {
2884             format!("{} {{ {}{} }}", qpath_to_string(name),
2885                 fields.iter().map(|&Spanned { node: ref fp, .. }|
2886                                   format!("{}: {}", fp.name, name_from_pat(&*fp.pat)))
2887                              .collect::<Vec<String>>().join(", "),
2888                 if etc { ", ..." } else { "" }
2889             )
2890         }
2891         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
2892                                             .collect::<Vec<String>>().join(", ")),
2893         PatKind::Box(ref p) => name_from_pat(&**p),
2894         PatKind::Ref(ref p, _) => name_from_pat(&**p),
2895         PatKind::Lit(..) => {
2896             warn!("tried to get argument name from PatKind::Lit, \
2897                   which is silly in function arguments");
2898             "()".to_string()
2899         },
2900         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
2901                               which is not allowed in function arguments"),
2902         PatKind::Slice(ref begin, ref mid, ref end) => {
2903             let begin = begin.iter().map(|p| name_from_pat(&**p));
2904             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
2905             let end = end.iter().map(|p| name_from_pat(&**p));
2906             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
2907         },
2908     }
2909 }
2910
2911 fn print_const_expr(cx: &DocContext, body: hir::BodyId) -> String {
2912     cx.tcx.hir.node_to_pretty_string(body.node_id)
2913 }
2914
2915 /// Given a type Path, resolve it to a Type using the TyCtxt
2916 fn resolve_type(cx: &DocContext,
2917                 path: Path,
2918                 id: ast::NodeId) -> Type {
2919     debug!("resolve_type({:?},{:?})", path, id);
2920
2921     let is_generic = match path.def {
2922         Def::PrimTy(p) => match p {
2923             hir::TyStr => return Primitive(PrimitiveType::Str),
2924             hir::TyBool => return Primitive(PrimitiveType::Bool),
2925             hir::TyChar => return Primitive(PrimitiveType::Char),
2926             hir::TyInt(int_ty) => return Primitive(int_ty.into()),
2927             hir::TyUint(uint_ty) => return Primitive(uint_ty.into()),
2928             hir::TyFloat(float_ty) => return Primitive(float_ty.into()),
2929         },
2930         Def::SelfTy(..) if path.segments.len() == 1 => {
2931             return Generic(keywords::SelfType.name().to_string());
2932         }
2933         Def::TyParam(..) if path.segments.len() == 1 => {
2934             return Generic(format!("{:#}", path));
2935         }
2936         Def::SelfTy(..) | Def::TyParam(..) | Def::AssociatedTy(..) => true,
2937         _ => false,
2938     };
2939     let did = register_def(&*cx, path.def);
2940     ResolvedPath { path: path, typarams: None, did: did, is_generic: is_generic }
2941 }
2942
2943 fn register_def(cx: &DocContext, def: Def) -> DefId {
2944     debug!("register_def({:?})", def);
2945
2946     let (did, kind) = match def {
2947         Def::Fn(i) => (i, TypeKind::Function),
2948         Def::TyAlias(i) => (i, TypeKind::Typedef),
2949         Def::Enum(i) => (i, TypeKind::Enum),
2950         Def::Trait(i) => (i, TypeKind::Trait),
2951         Def::Struct(i) => (i, TypeKind::Struct),
2952         Def::Union(i) => (i, TypeKind::Union),
2953         Def::Mod(i) => (i, TypeKind::Module),
2954         Def::Static(i, _) => (i, TypeKind::Static),
2955         Def::Variant(i) => (cx.tcx.parent_def_id(i).unwrap(), TypeKind::Enum),
2956         Def::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
2957         Def::SelfTy(_, Some(impl_def_id)) => {
2958             return impl_def_id
2959         }
2960         _ => return def.def_id()
2961     };
2962     if did.is_local() { return did }
2963     inline::record_extern_fqn(cx, did, kind);
2964     if let TypeKind::Trait = kind {
2965         let t = inline::build_external_trait(cx, did);
2966         cx.external_traits.borrow_mut().insert(did, t);
2967     }
2968     did
2969 }
2970
2971 fn resolve_use_source(cx: &DocContext, path: Path) -> ImportSource {
2972     ImportSource {
2973         did: if path.def == Def::Err {
2974             None
2975         } else {
2976             Some(register_def(cx, path.def))
2977         },
2978         path,
2979     }
2980 }
2981
2982 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2983 pub struct Macro {
2984     pub source: String,
2985     pub imported_from: Option<String>,
2986 }
2987
2988 impl Clean<Item> for doctree::Macro {
2989     fn clean(&self, cx: &DocContext) -> Item {
2990         let name = self.name.clean(cx);
2991         Item {
2992             name: Some(name.clone()),
2993             attrs: self.attrs.clean(cx),
2994             source: self.whence.clean(cx),
2995             visibility: Some(Public),
2996             stability: self.stab.clean(cx),
2997             deprecation: self.depr.clean(cx),
2998             def_id: self.def_id,
2999             inner: MacroItem(Macro {
3000                 source: format!("macro_rules! {} {{\n{}}}",
3001                                 name,
3002                                 self.matchers.iter().map(|span| {
3003                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
3004                                 }).collect::<String>()),
3005                 imported_from: self.imported_from.clean(cx),
3006             }),
3007         }
3008     }
3009 }
3010
3011 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3012 pub struct Stability {
3013     pub level: stability::StabilityLevel,
3014     pub feature: String,
3015     pub since: String,
3016     pub deprecated_since: String,
3017     pub deprecated_reason: String,
3018     pub unstable_reason: String,
3019     pub issue: Option<u32>
3020 }
3021
3022 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3023 pub struct Deprecation {
3024     pub since: String,
3025     pub note: String,
3026 }
3027
3028 impl Clean<Stability> for attr::Stability {
3029     fn clean(&self, _: &DocContext) -> Stability {
3030         Stability {
3031             level: stability::StabilityLevel::from_attr_level(&self.level),
3032             feature: self.feature.to_string(),
3033             since: match self.level {
3034                 attr::Stable {ref since} => since.to_string(),
3035                 _ => "".to_string(),
3036             },
3037             deprecated_since: match self.rustc_depr {
3038                 Some(attr::RustcDeprecation {ref since, ..}) => since.to_string(),
3039                 _=> "".to_string(),
3040             },
3041             deprecated_reason: match self.rustc_depr {
3042                 Some(ref depr) => depr.reason.to_string(),
3043                 _ => "".to_string(),
3044             },
3045             unstable_reason: match self.level {
3046                 attr::Unstable { reason: Some(ref reason), .. } => reason.to_string(),
3047                 _ => "".to_string(),
3048             },
3049             issue: match self.level {
3050                 attr::Unstable {issue, ..} => Some(issue),
3051                 _ => None,
3052             }
3053         }
3054     }
3055 }
3056
3057 impl<'a> Clean<Stability> for &'a attr::Stability {
3058     fn clean(&self, dc: &DocContext) -> Stability {
3059         (**self).clean(dc)
3060     }
3061 }
3062
3063 impl Clean<Deprecation> for attr::Deprecation {
3064     fn clean(&self, _: &DocContext) -> Deprecation {
3065         Deprecation {
3066             since: self.since.as_ref().map_or("".to_string(), |s| s.to_string()),
3067             note: self.note.as_ref().map_or("".to_string(), |s| s.to_string()),
3068         }
3069     }
3070 }
3071
3072 /// An equality constraint on an associated type, e.g. `A=Bar` in `Foo<A=Bar>`
3073 #[derive(Clone, PartialEq, RustcDecodable, RustcEncodable, Debug)]
3074 pub struct TypeBinding {
3075     pub name: String,
3076     pub ty: Type
3077 }
3078
3079 impl Clean<TypeBinding> for hir::TypeBinding {
3080     fn clean(&self, cx: &DocContext) -> TypeBinding {
3081         TypeBinding {
3082             name: self.name.clean(cx),
3083             ty: self.ty.clean(cx)
3084         }
3085     }
3086 }