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