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