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