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     Slice(Box<Type>),
1510     Array(Box<Type>, usize),
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             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
1577             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
1578             Tuple(..) => Some(PrimitiveType::Tuple),
1579             RawPointer(..) => Some(PrimitiveType::RawPointer),
1580             _ => None,
1581         }
1582     }
1583
1584     pub fn is_generic(&self) -> bool {
1585         match *self {
1586             ResolvedPath { is_generic, .. } => is_generic,
1587             _ => false,
1588         }
1589     }
1590
1591     pub fn is_self_type(&self) -> bool {
1592         match *self {
1593             Generic(ref name) => name == "Self",
1594             _ => false
1595         }
1596     }
1597 }
1598
1599 impl GetDefId for Type {
1600     fn def_id(&self) -> Option<DefId> {
1601         match *self {
1602             ResolvedPath { did, .. } => Some(did),
1603             _ => None,
1604         }
1605     }
1606 }
1607
1608 impl PrimitiveType {
1609     fn from_str(s: &str) -> Option<PrimitiveType> {
1610         match s {
1611             "isize" => Some(PrimitiveType::Isize),
1612             "i8" => Some(PrimitiveType::I8),
1613             "i16" => Some(PrimitiveType::I16),
1614             "i32" => Some(PrimitiveType::I32),
1615             "i64" => Some(PrimitiveType::I64),
1616             "i128" => Some(PrimitiveType::I128),
1617             "usize" => Some(PrimitiveType::Usize),
1618             "u8" => Some(PrimitiveType::U8),
1619             "u16" => Some(PrimitiveType::U16),
1620             "u32" => Some(PrimitiveType::U32),
1621             "u64" => Some(PrimitiveType::U64),
1622             "u128" => Some(PrimitiveType::U128),
1623             "bool" => Some(PrimitiveType::Bool),
1624             "char" => Some(PrimitiveType::Char),
1625             "str" => Some(PrimitiveType::Str),
1626             "f32" => Some(PrimitiveType::F32),
1627             "f64" => Some(PrimitiveType::F64),
1628             "array" => Some(PrimitiveType::Array),
1629             "slice" => Some(PrimitiveType::Slice),
1630             "tuple" => Some(PrimitiveType::Tuple),
1631             "pointer" => Some(PrimitiveType::RawPointer),
1632             _ => None,
1633         }
1634     }
1635
1636     pub fn as_str(&self) -> &'static str {
1637         use self::PrimitiveType::*;
1638         match *self {
1639             Isize => "isize",
1640             I8 => "i8",
1641             I16 => "i16",
1642             I32 => "i32",
1643             I64 => "i64",
1644             I128 => "i128",
1645             Usize => "usize",
1646             U8 => "u8",
1647             U16 => "u16",
1648             U32 => "u32",
1649             U64 => "u64",
1650             U128 => "u128",
1651             F32 => "f32",
1652             F64 => "f64",
1653             Str => "str",
1654             Bool => "bool",
1655             Char => "char",
1656             Array => "array",
1657             Slice => "slice",
1658             Tuple => "tuple",
1659             RawPointer => "pointer",
1660         }
1661     }
1662
1663     pub fn to_url_str(&self) -> &'static str {
1664         self.as_str()
1665     }
1666 }
1667
1668 impl From<ast::IntTy> for PrimitiveType {
1669     fn from(int_ty: ast::IntTy) -> PrimitiveType {
1670         match int_ty {
1671             ast::IntTy::Is => PrimitiveType::Isize,
1672             ast::IntTy::I8 => PrimitiveType::I8,
1673             ast::IntTy::I16 => PrimitiveType::I16,
1674             ast::IntTy::I32 => PrimitiveType::I32,
1675             ast::IntTy::I64 => PrimitiveType::I64,
1676             ast::IntTy::I128 => PrimitiveType::I128,
1677         }
1678     }
1679 }
1680
1681 impl From<ast::UintTy> for PrimitiveType {
1682     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
1683         match uint_ty {
1684             ast::UintTy::Us => PrimitiveType::Usize,
1685             ast::UintTy::U8 => PrimitiveType::U8,
1686             ast::UintTy::U16 => PrimitiveType::U16,
1687             ast::UintTy::U32 => PrimitiveType::U32,
1688             ast::UintTy::U64 => PrimitiveType::U64,
1689             ast::UintTy::U128 => PrimitiveType::U128,
1690         }
1691     }
1692 }
1693
1694 impl From<ast::FloatTy> for PrimitiveType {
1695     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
1696         match float_ty {
1697             ast::FloatTy::F32 => PrimitiveType::F32,
1698             ast::FloatTy::F64 => PrimitiveType::F64,
1699         }
1700     }
1701 }
1702
1703 impl Clean<Type> for hir::Ty {
1704     fn clean(&self, cx: &DocContext) -> Type {
1705         use rustc::hir::*;
1706         match self.node {
1707             TyNever => Never,
1708             TyPtr(ref m) => RawPointer(m.mutbl.clean(cx), box m.ty.clean(cx)),
1709             TyRptr(ref l, ref m) => {
1710                 let lifetime = if l.is_elided() {
1711                     None
1712                 } else {
1713                     Some(l.clean(cx))
1714                 };
1715                 BorrowedRef {lifetime: lifetime, mutability: m.mutbl.clean(cx),
1716                              type_: box m.ty.clean(cx)}
1717             }
1718             TySlice(ref ty) => Slice(box ty.clean(cx)),
1719             TyArray(ref ty, length) => {
1720                 use rustc::middle::const_val::eval_length;
1721                 let n = eval_length(cx.tcx, length, "array length").unwrap();
1722                 Array(box ty.clean(cx), n)
1723             },
1724             TyTup(ref tys) => Tuple(tys.clean(cx)),
1725             TyPath(hir::QPath::Resolved(None, ref path)) => {
1726                 if let Some(new_ty) = cx.ty_substs.borrow().get(&path.def).cloned() {
1727                     return new_ty;
1728                 }
1729
1730                 let mut alias = None;
1731                 if let Def::TyAlias(def_id) = path.def {
1732                     // Substitute private type aliases
1733                     if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
1734                         if !cx.access_levels.borrow().is_exported(def_id) {
1735                             alias = Some(&cx.tcx.hir.expect_item(node_id).node);
1736                         }
1737                     }
1738                 };
1739
1740                 if let Some(&hir::ItemTy(ref ty, ref generics)) = alias {
1741                     let provided_params = &path.segments.last().unwrap().parameters;
1742                     let mut ty_substs = FxHashMap();
1743                     let mut lt_substs = FxHashMap();
1744                     for (i, ty_param) in generics.ty_params.iter().enumerate() {
1745                         let ty_param_def = Def::TyParam(cx.tcx.hir.local_def_id(ty_param.id));
1746                         if let Some(ty) = provided_params.types().get(i).cloned()
1747                                                                         .cloned() {
1748                             ty_substs.insert(ty_param_def, ty.unwrap().clean(cx));
1749                         } else if let Some(default) = ty_param.default.clone() {
1750                             ty_substs.insert(ty_param_def, default.unwrap().clean(cx));
1751                         }
1752                     }
1753                     for (i, lt_param) in generics.lifetimes.iter().enumerate() {
1754                         if let Some(lt) = provided_params.lifetimes().get(i).cloned()
1755                                                                             .cloned() {
1756                             if !lt.is_elided() {
1757                                 lt_substs.insert(lt_param.lifetime.id, lt.clean(cx));
1758                             }
1759                         }
1760                     }
1761                     return cx.enter_alias(ty_substs, lt_substs, || ty.clean(cx));
1762                 }
1763                 resolve_type(cx, path.clean(cx), self.id)
1764             }
1765             TyPath(hir::QPath::Resolved(Some(ref qself), ref p)) => {
1766                 let mut segments: Vec<_> = p.segments.clone().into();
1767                 segments.pop();
1768                 let trait_path = hir::Path {
1769                     span: p.span,
1770                     def: Def::Trait(cx.tcx.associated_item(p.def.def_id()).container.id()),
1771                     segments: segments.into(),
1772                 };
1773                 Type::QPath {
1774                     name: p.segments.last().unwrap().name.clean(cx),
1775                     self_type: box qself.clean(cx),
1776                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
1777                 }
1778             }
1779             TyPath(hir::QPath::TypeRelative(ref qself, ref segment)) => {
1780                 let mut def = Def::Err;
1781                 let ty = hir_ty_to_ty(cx.tcx, self);
1782                 if let ty::TyProjection(proj) = ty.sty {
1783                     def = Def::Trait(proj.trait_ref.def_id);
1784                 }
1785                 let trait_path = hir::Path {
1786                     span: self.span,
1787                     def: def,
1788                     segments: vec![].into(),
1789                 };
1790                 Type::QPath {
1791                     name: segment.name.clean(cx),
1792                     self_type: box qself.clean(cx),
1793                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
1794                 }
1795             }
1796             TyTraitObject(ref bounds, ref lifetime) => {
1797                 match bounds[0].clean(cx).trait_ {
1798                     ResolvedPath { path, typarams: None, did, is_generic } => {
1799                         let mut bounds: Vec<_> = bounds[1..].iter().map(|bound| {
1800                             TraitBound(bound.clean(cx), hir::TraitBoundModifier::None)
1801                         }).collect();
1802                         if !lifetime.is_elided() {
1803                             bounds.push(RegionBound(lifetime.clean(cx)));
1804                         }
1805                         ResolvedPath {
1806                             path: path,
1807                             typarams: Some(bounds),
1808                             did: did,
1809                             is_generic: is_generic,
1810                         }
1811                     }
1812                     _ => Infer // shouldn't happen
1813                 }
1814             }
1815             TyBareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
1816             TyImplTrait(ref bounds) => ImplTrait(bounds.clean(cx)),
1817             TyInfer | TyErr => Infer,
1818             TyTypeof(..) => panic!("Unimplemented type {:?}", self.node),
1819         }
1820     }
1821 }
1822
1823 impl<'tcx> Clean<Type> for ty::Ty<'tcx> {
1824     fn clean(&self, cx: &DocContext) -> Type {
1825         match self.sty {
1826             ty::TyNever => Never,
1827             ty::TyBool => Primitive(PrimitiveType::Bool),
1828             ty::TyChar => Primitive(PrimitiveType::Char),
1829             ty::TyInt(int_ty) => Primitive(int_ty.into()),
1830             ty::TyUint(uint_ty) => Primitive(uint_ty.into()),
1831             ty::TyFloat(float_ty) => Primitive(float_ty.into()),
1832             ty::TyStr => Primitive(PrimitiveType::Str),
1833             ty::TySlice(ty) => Slice(box ty.clean(cx)),
1834             ty::TyArray(ty, n) => Array(box ty.clean(cx), n),
1835             ty::TyRawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
1836             ty::TyRef(r, mt) => BorrowedRef {
1837                 lifetime: r.clean(cx),
1838                 mutability: mt.mutbl.clean(cx),
1839                 type_: box mt.ty.clean(cx),
1840             },
1841             ty::TyFnDef(.., sig) |
1842             ty::TyFnPtr(sig) => BareFunction(box BareFunctionDecl {
1843                 unsafety: sig.unsafety(),
1844                 generics: Generics {
1845                     lifetimes: Vec::new(),
1846                     type_params: Vec::new(),
1847                     where_predicates: Vec::new()
1848                 },
1849                 decl: (cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID), sig).clean(cx),
1850                 abi: sig.abi(),
1851             }),
1852             ty::TyAdt(def, substs) => {
1853                 let did = def.did;
1854                 let kind = match def.adt_kind() {
1855                     AdtKind::Struct => TypeKind::Struct,
1856                     AdtKind::Union => TypeKind::Union,
1857                     AdtKind::Enum => TypeKind::Enum,
1858                 };
1859                 inline::record_extern_fqn(cx, did, kind);
1860                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
1861                                          None, false, vec![], substs);
1862                 ResolvedPath {
1863                     path: path,
1864                     typarams: None,
1865                     did: did,
1866                     is_generic: false,
1867                 }
1868             }
1869             ty::TyDynamic(ref obj, ref reg) => {
1870                 if let Some(principal) = obj.principal() {
1871                     let did = principal.def_id();
1872                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
1873
1874                     let mut typarams = vec![];
1875                     reg.clean(cx).map(|b| typarams.push(RegionBound(b)));
1876                     for did in obj.auto_traits() {
1877                         let empty = cx.tcx.intern_substs(&[]);
1878                         let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
1879                             Some(did), false, vec![], empty);
1880                         inline::record_extern_fqn(cx, did, TypeKind::Trait);
1881                         let bound = TraitBound(PolyTrait {
1882                             trait_: ResolvedPath {
1883                                 path: path,
1884                                 typarams: None,
1885                                 did: did,
1886                                 is_generic: false,
1887                             },
1888                             lifetimes: vec![]
1889                         }, hir::TraitBoundModifier::None);
1890                         typarams.push(bound);
1891                     }
1892
1893                     let mut bindings = vec![];
1894                     for ty::Binder(ref pb) in obj.projection_bounds() {
1895                         bindings.push(TypeBinding {
1896                             name: pb.item_name.clean(cx),
1897                             ty: pb.ty.clean(cx)
1898                         });
1899                     }
1900
1901                     let path = external_path(cx, &cx.tcx.item_name(did).as_str(), Some(did),
1902                         false, bindings, principal.0.substs);
1903                     ResolvedPath {
1904                         path: path,
1905                         typarams: Some(typarams),
1906                         did: did,
1907                         is_generic: false,
1908                     }
1909                 } else {
1910                     Never
1911                 }
1912             }
1913             ty::TyTuple(ref t, _) => Tuple(t.clean(cx)),
1914
1915             ty::TyProjection(ref data) => data.clean(cx),
1916
1917             ty::TyParam(ref p) => Generic(p.name.to_string()),
1918
1919             ty::TyAnon(def_id, substs) => {
1920                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
1921                 // by looking up the projections associated with the def_id.
1922                 let predicates_of = cx.tcx.predicates_of(def_id);
1923                 let substs = cx.tcx.lift(&substs).unwrap();
1924                 let bounds = predicates_of.instantiate(cx.tcx, substs);
1925                 ImplTrait(bounds.predicates.into_iter().filter_map(|predicate| {
1926                     predicate.to_opt_poly_trait_ref().clean(cx)
1927                 }).collect())
1928             }
1929
1930             ty::TyClosure(..) => Tuple(vec![]), // FIXME(pcwalton)
1931
1932             ty::TyInfer(..) => panic!("TyInfer"),
1933             ty::TyError => panic!("TyError"),
1934         }
1935     }
1936 }
1937
1938 impl Clean<Item> for hir::StructField {
1939     fn clean(&self, cx: &DocContext) -> Item {
1940         Item {
1941             name: Some(self.name).clean(cx),
1942             attrs: self.attrs.clean(cx),
1943             source: self.span.clean(cx),
1944             visibility: self.vis.clean(cx),
1945             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
1946             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
1947             def_id: cx.tcx.hir.local_def_id(self.id),
1948             inner: StructFieldItem(self.ty.clean(cx)),
1949         }
1950     }
1951 }
1952
1953 impl<'tcx> Clean<Item> for ty::FieldDef {
1954     fn clean(&self, cx: &DocContext) -> Item {
1955         Item {
1956             name: Some(self.name).clean(cx),
1957             attrs: cx.tcx.get_attrs(self.did).clean(cx),
1958             source: cx.tcx.def_span(self.did).clean(cx),
1959             visibility: self.vis.clean(cx),
1960             stability: get_stability(cx, self.did),
1961             deprecation: get_deprecation(cx, self.did),
1962             def_id: self.did,
1963             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
1964         }
1965     }
1966 }
1967
1968 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug)]
1969 pub enum Visibility {
1970     Public,
1971     Inherited,
1972 }
1973
1974 impl Clean<Option<Visibility>> for hir::Visibility {
1975     fn clean(&self, _: &DocContext) -> Option<Visibility> {
1976         Some(if *self == hir::Visibility::Public { Public } else { Inherited })
1977     }
1978 }
1979
1980 impl Clean<Option<Visibility>> for ty::Visibility {
1981     fn clean(&self, _: &DocContext) -> Option<Visibility> {
1982         Some(if *self == ty::Visibility::Public { Public } else { Inherited })
1983     }
1984 }
1985
1986 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1987 pub struct Struct {
1988     pub struct_type: doctree::StructType,
1989     pub generics: Generics,
1990     pub fields: Vec<Item>,
1991     pub fields_stripped: bool,
1992 }
1993
1994 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1995 pub struct Union {
1996     pub struct_type: doctree::StructType,
1997     pub generics: Generics,
1998     pub fields: Vec<Item>,
1999     pub fields_stripped: bool,
2000 }
2001
2002 impl Clean<Item> for doctree::Struct {
2003     fn clean(&self, cx: &DocContext) -> Item {
2004         Item {
2005             name: Some(self.name.clean(cx)),
2006             attrs: self.attrs.clean(cx),
2007             source: self.whence.clean(cx),
2008             def_id: cx.tcx.hir.local_def_id(self.id),
2009             visibility: self.vis.clean(cx),
2010             stability: self.stab.clean(cx),
2011             deprecation: self.depr.clean(cx),
2012             inner: StructItem(Struct {
2013                 struct_type: self.struct_type,
2014                 generics: self.generics.clean(cx),
2015                 fields: self.fields.clean(cx),
2016                 fields_stripped: false,
2017             }),
2018         }
2019     }
2020 }
2021
2022 impl Clean<Item> for doctree::Union {
2023     fn clean(&self, cx: &DocContext) -> Item {
2024         Item {
2025             name: Some(self.name.clean(cx)),
2026             attrs: self.attrs.clean(cx),
2027             source: self.whence.clean(cx),
2028             def_id: cx.tcx.hir.local_def_id(self.id),
2029             visibility: self.vis.clean(cx),
2030             stability: self.stab.clean(cx),
2031             deprecation: self.depr.clean(cx),
2032             inner: UnionItem(Union {
2033                 struct_type: self.struct_type,
2034                 generics: self.generics.clean(cx),
2035                 fields: self.fields.clean(cx),
2036                 fields_stripped: false,
2037             }),
2038         }
2039     }
2040 }
2041
2042 /// This is a more limited form of the standard Struct, different in that
2043 /// it lacks the things most items have (name, id, parameterization). Found
2044 /// only as a variant in an enum.
2045 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2046 pub struct VariantStruct {
2047     pub struct_type: doctree::StructType,
2048     pub fields: Vec<Item>,
2049     pub fields_stripped: bool,
2050 }
2051
2052 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
2053     fn clean(&self, cx: &DocContext) -> VariantStruct {
2054         VariantStruct {
2055             struct_type: doctree::struct_type_from_def(self),
2056             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
2057             fields_stripped: false,
2058         }
2059     }
2060 }
2061
2062 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2063 pub struct Enum {
2064     pub variants: Vec<Item>,
2065     pub generics: Generics,
2066     pub variants_stripped: bool,
2067 }
2068
2069 impl Clean<Item> for doctree::Enum {
2070     fn clean(&self, cx: &DocContext) -> Item {
2071         Item {
2072             name: Some(self.name.clean(cx)),
2073             attrs: self.attrs.clean(cx),
2074             source: self.whence.clean(cx),
2075             def_id: cx.tcx.hir.local_def_id(self.id),
2076             visibility: self.vis.clean(cx),
2077             stability: self.stab.clean(cx),
2078             deprecation: self.depr.clean(cx),
2079             inner: EnumItem(Enum {
2080                 variants: self.variants.clean(cx),
2081                 generics: self.generics.clean(cx),
2082                 variants_stripped: false,
2083             }),
2084         }
2085     }
2086 }
2087
2088 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2089 pub struct Variant {
2090     pub kind: VariantKind,
2091 }
2092
2093 impl Clean<Item> for doctree::Variant {
2094     fn clean(&self, cx: &DocContext) -> Item {
2095         Item {
2096             name: Some(self.name.clean(cx)),
2097             attrs: self.attrs.clean(cx),
2098             source: self.whence.clean(cx),
2099             visibility: None,
2100             stability: self.stab.clean(cx),
2101             deprecation: self.depr.clean(cx),
2102             def_id: cx.tcx.hir.local_def_id(self.def.id()),
2103             inner: VariantItem(Variant {
2104                 kind: self.def.clean(cx),
2105             }),
2106         }
2107     }
2108 }
2109
2110 impl<'tcx> Clean<Item> for ty::VariantDef {
2111     fn clean(&self, cx: &DocContext) -> Item {
2112         let kind = match self.ctor_kind {
2113             CtorKind::Const => VariantKind::CLike,
2114             CtorKind::Fn => {
2115                 VariantKind::Tuple(
2116                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
2117                 )
2118             }
2119             CtorKind::Fictive => {
2120                 VariantKind::Struct(VariantStruct {
2121                     struct_type: doctree::Plain,
2122                     fields_stripped: false,
2123                     fields: self.fields.iter().map(|field| {
2124                         Item {
2125                             source: cx.tcx.def_span(field.did).clean(cx),
2126                             name: Some(field.name.clean(cx)),
2127                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
2128                             visibility: field.vis.clean(cx),
2129                             def_id: field.did,
2130                             stability: get_stability(cx, field.did),
2131                             deprecation: get_deprecation(cx, field.did),
2132                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
2133                         }
2134                     }).collect()
2135                 })
2136             }
2137         };
2138         Item {
2139             name: Some(self.name.clean(cx)),
2140             attrs: inline::load_attrs(cx, self.did),
2141             source: cx.tcx.def_span(self.did).clean(cx),
2142             visibility: Some(Inherited),
2143             def_id: self.did,
2144             inner: VariantItem(Variant { kind: kind }),
2145             stability: get_stability(cx, self.did),
2146             deprecation: get_deprecation(cx, self.did),
2147         }
2148     }
2149 }
2150
2151 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2152 pub enum VariantKind {
2153     CLike,
2154     Tuple(Vec<Type>),
2155     Struct(VariantStruct),
2156 }
2157
2158 impl Clean<VariantKind> for hir::VariantData {
2159     fn clean(&self, cx: &DocContext) -> VariantKind {
2160         if self.is_struct() {
2161             VariantKind::Struct(self.clean(cx))
2162         } else if self.is_unit() {
2163             VariantKind::CLike
2164         } else {
2165             VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect())
2166         }
2167     }
2168 }
2169
2170 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2171 pub struct Span {
2172     pub filename: String,
2173     pub loline: usize,
2174     pub locol: usize,
2175     pub hiline: usize,
2176     pub hicol: usize,
2177 }
2178
2179 impl Span {
2180     fn empty() -> Span {
2181         Span {
2182             filename: "".to_string(),
2183             loline: 0, locol: 0,
2184             hiline: 0, hicol: 0,
2185         }
2186     }
2187 }
2188
2189 impl Clean<Span> for syntax_pos::Span {
2190     fn clean(&self, cx: &DocContext) -> Span {
2191         if *self == DUMMY_SP {
2192             return Span::empty();
2193         }
2194
2195         let cm = cx.sess().codemap();
2196         let filename = cm.span_to_filename(*self);
2197         let lo = cm.lookup_char_pos(self.lo);
2198         let hi = cm.lookup_char_pos(self.hi);
2199         Span {
2200             filename: filename.to_string(),
2201             loline: lo.line,
2202             locol: lo.col.to_usize(),
2203             hiline: hi.line,
2204             hicol: hi.col.to_usize(),
2205         }
2206     }
2207 }
2208
2209 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2210 pub struct Path {
2211     pub global: bool,
2212     pub def: Def,
2213     pub segments: Vec<PathSegment>,
2214 }
2215
2216 impl Path {
2217     pub fn singleton(name: String) -> Path {
2218         Path {
2219             global: false,
2220             def: Def::Err,
2221             segments: vec![PathSegment {
2222                 name: name,
2223                 params: PathParameters::AngleBracketed {
2224                     lifetimes: Vec::new(),
2225                     types: Vec::new(),
2226                     bindings: Vec::new()
2227                 }
2228             }]
2229         }
2230     }
2231
2232     pub fn last_name(&self) -> &str {
2233         self.segments.last().unwrap().name.as_str()
2234     }
2235 }
2236
2237 impl Clean<Path> for hir::Path {
2238     fn clean(&self, cx: &DocContext) -> Path {
2239         Path {
2240             global: self.is_global(),
2241             def: self.def,
2242             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
2243         }
2244     }
2245 }
2246
2247 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2248 pub enum PathParameters {
2249     AngleBracketed {
2250         lifetimes: Vec<Lifetime>,
2251         types: Vec<Type>,
2252         bindings: Vec<TypeBinding>,
2253     },
2254     Parenthesized {
2255         inputs: Vec<Type>,
2256         output: Option<Type>,
2257     }
2258 }
2259
2260 impl Clean<PathParameters> for hir::PathParameters {
2261     fn clean(&self, cx: &DocContext) -> PathParameters {
2262         match *self {
2263             hir::AngleBracketedParameters(ref data) => {
2264                 PathParameters::AngleBracketed {
2265                     lifetimes: if data.lifetimes.iter().all(|lt| lt.is_elided()) {
2266                         vec![]
2267                     } else {
2268                         data.lifetimes.clean(cx)
2269                     },
2270                     types: data.types.clean(cx),
2271                     bindings: data.bindings.clean(cx),
2272                 }
2273             }
2274
2275             hir::ParenthesizedParameters(ref data) => {
2276                 PathParameters::Parenthesized {
2277                     inputs: data.inputs.clean(cx),
2278                     output: data.output.clean(cx),
2279                 }
2280             }
2281         }
2282     }
2283 }
2284
2285 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2286 pub struct PathSegment {
2287     pub name: String,
2288     pub params: PathParameters,
2289 }
2290
2291 impl Clean<PathSegment> for hir::PathSegment {
2292     fn clean(&self, cx: &DocContext) -> PathSegment {
2293         PathSegment {
2294             name: self.name.clean(cx),
2295             params: self.parameters.clean(cx)
2296         }
2297     }
2298 }
2299
2300 fn qpath_to_string(p: &hir::QPath) -> String {
2301     let segments = match *p {
2302         hir::QPath::Resolved(_, ref path) => &path.segments,
2303         hir::QPath::TypeRelative(_, ref segment) => return segment.name.to_string(),
2304     };
2305
2306     let mut s = String::new();
2307     for (i, seg) in segments.iter().enumerate() {
2308         if i > 0 {
2309             s.push_str("::");
2310         }
2311         if seg.name != keywords::CrateRoot.name() {
2312             s.push_str(&*seg.name.as_str());
2313         }
2314     }
2315     s
2316 }
2317
2318 impl Clean<String> for ast::Name {
2319     fn clean(&self, _: &DocContext) -> String {
2320         self.to_string()
2321     }
2322 }
2323
2324 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2325 pub struct Typedef {
2326     pub type_: Type,
2327     pub generics: Generics,
2328 }
2329
2330 impl Clean<Item> for doctree::Typedef {
2331     fn clean(&self, cx: &DocContext) -> Item {
2332         Item {
2333             name: Some(self.name.clean(cx)),
2334             attrs: self.attrs.clean(cx),
2335             source: self.whence.clean(cx),
2336             def_id: cx.tcx.hir.local_def_id(self.id.clone()),
2337             visibility: self.vis.clean(cx),
2338             stability: self.stab.clean(cx),
2339             deprecation: self.depr.clean(cx),
2340             inner: TypedefItem(Typedef {
2341                 type_: self.ty.clean(cx),
2342                 generics: self.gen.clean(cx),
2343             }, false),
2344         }
2345     }
2346 }
2347
2348 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2349 pub struct BareFunctionDecl {
2350     pub unsafety: hir::Unsafety,
2351     pub generics: Generics,
2352     pub decl: FnDecl,
2353     pub abi: Abi,
2354 }
2355
2356 impl Clean<BareFunctionDecl> for hir::BareFnTy {
2357     fn clean(&self, cx: &DocContext) -> BareFunctionDecl {
2358         BareFunctionDecl {
2359             unsafety: self.unsafety,
2360             generics: Generics {
2361                 lifetimes: self.lifetimes.clean(cx),
2362                 type_params: Vec::new(),
2363                 where_predicates: Vec::new()
2364             },
2365             decl: (&*self.decl, &[][..]).clean(cx),
2366             abi: self.abi,
2367         }
2368     }
2369 }
2370
2371 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2372 pub struct Static {
2373     pub type_: Type,
2374     pub mutability: Mutability,
2375     /// It's useful to have the value of a static documented, but I have no
2376     /// desire to represent expressions (that'd basically be all of the AST,
2377     /// which is huge!). So, have a string.
2378     pub expr: String,
2379 }
2380
2381 impl Clean<Item> for doctree::Static {
2382     fn clean(&self, cx: &DocContext) -> Item {
2383         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
2384         Item {
2385             name: Some(self.name.clean(cx)),
2386             attrs: self.attrs.clean(cx),
2387             source: self.whence.clean(cx),
2388             def_id: cx.tcx.hir.local_def_id(self.id),
2389             visibility: self.vis.clean(cx),
2390             stability: self.stab.clean(cx),
2391             deprecation: self.depr.clean(cx),
2392             inner: StaticItem(Static {
2393                 type_: self.type_.clean(cx),
2394                 mutability: self.mutability.clean(cx),
2395                 expr: print_const_expr(cx, self.expr),
2396             }),
2397         }
2398     }
2399 }
2400
2401 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2402 pub struct Constant {
2403     pub type_: Type,
2404     pub expr: String,
2405 }
2406
2407 impl Clean<Item> for doctree::Constant {
2408     fn clean(&self, cx: &DocContext) -> Item {
2409         Item {
2410             name: Some(self.name.clean(cx)),
2411             attrs: self.attrs.clean(cx),
2412             source: self.whence.clean(cx),
2413             def_id: cx.tcx.hir.local_def_id(self.id),
2414             visibility: self.vis.clean(cx),
2415             stability: self.stab.clean(cx),
2416             deprecation: self.depr.clean(cx),
2417             inner: ConstantItem(Constant {
2418                 type_: self.type_.clean(cx),
2419                 expr: print_const_expr(cx, self.expr),
2420             }),
2421         }
2422     }
2423 }
2424
2425 #[derive(Debug, Clone, RustcEncodable, RustcDecodable, PartialEq, Copy)]
2426 pub enum Mutability {
2427     Mutable,
2428     Immutable,
2429 }
2430
2431 impl Clean<Mutability> for hir::Mutability {
2432     fn clean(&self, _: &DocContext) -> Mutability {
2433         match self {
2434             &hir::MutMutable => Mutable,
2435             &hir::MutImmutable => Immutable,
2436         }
2437     }
2438 }
2439
2440 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Copy, Debug)]
2441 pub enum ImplPolarity {
2442     Positive,
2443     Negative,
2444 }
2445
2446 impl Clean<ImplPolarity> for hir::ImplPolarity {
2447     fn clean(&self, _: &DocContext) -> ImplPolarity {
2448         match self {
2449             &hir::ImplPolarity::Positive => ImplPolarity::Positive,
2450             &hir::ImplPolarity::Negative => ImplPolarity::Negative,
2451         }
2452     }
2453 }
2454
2455 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2456 pub struct Impl {
2457     pub unsafety: hir::Unsafety,
2458     pub generics: Generics,
2459     pub provided_trait_methods: FxHashSet<String>,
2460     pub trait_: Option<Type>,
2461     pub for_: Type,
2462     pub items: Vec<Item>,
2463     pub polarity: Option<ImplPolarity>,
2464 }
2465
2466 impl Clean<Vec<Item>> for doctree::Impl {
2467     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2468         let mut ret = Vec::new();
2469         let trait_ = self.trait_.clean(cx);
2470         let items = self.items.clean(cx);
2471
2472         // If this impl block is an implementation of the Deref trait, then we
2473         // need to try inlining the target's inherent impl blocks as well.
2474         if trait_.def_id() == cx.tcx.lang_items.deref_trait() {
2475             build_deref_target_impls(cx, &items, &mut ret);
2476         }
2477
2478         let provided = trait_.def_id().map(|did| {
2479             cx.tcx.provided_trait_methods(did)
2480                   .into_iter()
2481                   .map(|meth| meth.name.to_string())
2482                   .collect()
2483         }).unwrap_or(FxHashSet());
2484
2485         ret.push(Item {
2486             name: None,
2487             attrs: self.attrs.clean(cx),
2488             source: self.whence.clean(cx),
2489             def_id: cx.tcx.hir.local_def_id(self.id),
2490             visibility: self.vis.clean(cx),
2491             stability: self.stab.clean(cx),
2492             deprecation: self.depr.clean(cx),
2493             inner: ImplItem(Impl {
2494                 unsafety: self.unsafety,
2495                 generics: self.generics.clean(cx),
2496                 provided_trait_methods: provided,
2497                 trait_: trait_,
2498                 for_: self.for_.clean(cx),
2499                 items: items,
2500                 polarity: Some(self.polarity.clean(cx)),
2501             }),
2502         });
2503         ret
2504     }
2505 }
2506
2507 fn build_deref_target_impls(cx: &DocContext,
2508                             items: &[Item],
2509                             ret: &mut Vec<Item>) {
2510     use self::PrimitiveType::*;
2511     let tcx = cx.tcx;
2512
2513     for item in items {
2514         let target = match item.inner {
2515             TypedefItem(ref t, true) => &t.type_,
2516             _ => continue,
2517         };
2518         let primitive = match *target {
2519             ResolvedPath { did, .. } if did.is_local() => continue,
2520             ResolvedPath { did, .. } => {
2521                 ret.extend(inline::build_impls(cx, did));
2522                 continue
2523             }
2524             _ => match target.primitive_type() {
2525                 Some(prim) => prim,
2526                 None => continue,
2527             }
2528         };
2529         let did = match primitive {
2530             Isize => tcx.lang_items.isize_impl(),
2531             I8 => tcx.lang_items.i8_impl(),
2532             I16 => tcx.lang_items.i16_impl(),
2533             I32 => tcx.lang_items.i32_impl(),
2534             I64 => tcx.lang_items.i64_impl(),
2535             I128 => tcx.lang_items.i128_impl(),
2536             Usize => tcx.lang_items.usize_impl(),
2537             U8 => tcx.lang_items.u8_impl(),
2538             U16 => tcx.lang_items.u16_impl(),
2539             U32 => tcx.lang_items.u32_impl(),
2540             U64 => tcx.lang_items.u64_impl(),
2541             U128 => tcx.lang_items.u128_impl(),
2542             F32 => tcx.lang_items.f32_impl(),
2543             F64 => tcx.lang_items.f64_impl(),
2544             Char => tcx.lang_items.char_impl(),
2545             Bool => None,
2546             Str => tcx.lang_items.str_impl(),
2547             Slice => tcx.lang_items.slice_impl(),
2548             Array => tcx.lang_items.slice_impl(),
2549             Tuple => None,
2550             RawPointer => tcx.lang_items.const_ptr_impl(),
2551         };
2552         if let Some(did) = did {
2553             if !did.is_local() {
2554                 inline::build_impl(cx, did, ret);
2555             }
2556         }
2557     }
2558 }
2559
2560 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2561 pub struct DefaultImpl {
2562     pub unsafety: hir::Unsafety,
2563     pub trait_: Type,
2564 }
2565
2566 impl Clean<Item> for doctree::DefaultImpl {
2567     fn clean(&self, cx: &DocContext) -> Item {
2568         Item {
2569             name: None,
2570             attrs: self.attrs.clean(cx),
2571             source: self.whence.clean(cx),
2572             def_id: cx.tcx.hir.local_def_id(self.id),
2573             visibility: Some(Public),
2574             stability: None,
2575             deprecation: None,
2576             inner: DefaultImplItem(DefaultImpl {
2577                 unsafety: self.unsafety,
2578                 trait_: self.trait_.clean(cx),
2579             }),
2580         }
2581     }
2582 }
2583
2584 impl Clean<Item> for doctree::ExternCrate {
2585     fn clean(&self, cx: &DocContext) -> Item {
2586         Item {
2587             name: None,
2588             attrs: self.attrs.clean(cx),
2589             source: self.whence.clean(cx),
2590             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
2591             visibility: self.vis.clean(cx),
2592             stability: None,
2593             deprecation: None,
2594             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
2595         }
2596     }
2597 }
2598
2599 impl Clean<Vec<Item>> for doctree::Import {
2600     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2601         // We consider inlining the documentation of `pub use` statements, but we
2602         // forcefully don't inline if this is not public or if the
2603         // #[doc(no_inline)] attribute is present.
2604         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
2605         let denied = self.vis != hir::Public || self.attrs.iter().any(|a| {
2606             a.name().unwrap() == "doc" && match a.meta_item_list() {
2607                 Some(l) => attr::list_contains_name(&l, "no_inline") ||
2608                            attr::list_contains_name(&l, "hidden"),
2609                 None => false,
2610             }
2611         });
2612         let path = self.path.clean(cx);
2613         let inner = if self.glob {
2614             Import::Glob(resolve_use_source(cx, path))
2615         } else {
2616             let name = self.name;
2617             if !denied {
2618                 if let Some(items) = inline::try_inline(cx, path.def, name) {
2619                     return items;
2620                 }
2621             }
2622             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
2623         };
2624         vec![Item {
2625             name: None,
2626             attrs: self.attrs.clean(cx),
2627             source: self.whence.clean(cx),
2628             def_id: cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID),
2629             visibility: self.vis.clean(cx),
2630             stability: None,
2631             deprecation: None,
2632             inner: ImportItem(inner)
2633         }]
2634     }
2635 }
2636
2637 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2638 pub enum Import {
2639     // use source as str;
2640     Simple(String, ImportSource),
2641     // use source::*;
2642     Glob(ImportSource)
2643 }
2644
2645 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2646 pub struct ImportSource {
2647     pub path: Path,
2648     pub did: Option<DefId>,
2649 }
2650
2651 impl Clean<Vec<Item>> for hir::ForeignMod {
2652     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2653         let mut items = self.items.clean(cx);
2654         for item in &mut items {
2655             if let ForeignFunctionItem(ref mut f) = item.inner {
2656                 f.abi = self.abi;
2657             }
2658         }
2659         items
2660     }
2661 }
2662
2663 impl Clean<Item> for hir::ForeignItem {
2664     fn clean(&self, cx: &DocContext) -> Item {
2665         let inner = match self.node {
2666             hir::ForeignItemFn(ref decl, ref names, ref generics) => {
2667                 ForeignFunctionItem(Function {
2668                     decl: (&**decl, &names[..]).clean(cx),
2669                     generics: generics.clean(cx),
2670                     unsafety: hir::Unsafety::Unsafe,
2671                     abi: Abi::Rust,
2672                     constness: hir::Constness::NotConst,
2673                 })
2674             }
2675             hir::ForeignItemStatic(ref ty, mutbl) => {
2676                 ForeignStaticItem(Static {
2677                     type_: ty.clean(cx),
2678                     mutability: if mutbl {Mutable} else {Immutable},
2679                     expr: "".to_string(),
2680                 })
2681             }
2682         };
2683         Item {
2684             name: Some(self.name.clean(cx)),
2685             attrs: self.attrs.clean(cx),
2686             source: self.span.clean(cx),
2687             def_id: cx.tcx.hir.local_def_id(self.id),
2688             visibility: self.vis.clean(cx),
2689             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2690             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2691             inner: inner,
2692         }
2693     }
2694 }
2695
2696 // Utilities
2697
2698 trait ToSource {
2699     fn to_src(&self, cx: &DocContext) -> String;
2700 }
2701
2702 impl ToSource for syntax_pos::Span {
2703     fn to_src(&self, cx: &DocContext) -> String {
2704         debug!("converting span {:?} to snippet", self.clean(cx));
2705         let sn = match cx.sess().codemap().span_to_snippet(*self) {
2706             Ok(x) => x.to_string(),
2707             Err(_) => "".to_string()
2708         };
2709         debug!("got snippet {}", sn);
2710         sn
2711     }
2712 }
2713
2714 fn name_from_pat(p: &hir::Pat) -> String {
2715     use rustc::hir::*;
2716     debug!("Trying to get a name from pattern: {:?}", p);
2717
2718     match p.node {
2719         PatKind::Wild => "_".to_string(),
2720         PatKind::Binding(_, _, ref p, _) => p.node.to_string(),
2721         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
2722         PatKind::Struct(ref name, ref fields, etc) => {
2723             format!("{} {{ {}{} }}", qpath_to_string(name),
2724                 fields.iter().map(|&Spanned { node: ref fp, .. }|
2725                                   format!("{}: {}", fp.name, name_from_pat(&*fp.pat)))
2726                              .collect::<Vec<String>>().join(", "),
2727                 if etc { ", ..." } else { "" }
2728             )
2729         }
2730         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
2731                                             .collect::<Vec<String>>().join(", ")),
2732         PatKind::Box(ref p) => name_from_pat(&**p),
2733         PatKind::Ref(ref p, _) => name_from_pat(&**p),
2734         PatKind::Lit(..) => {
2735             warn!("tried to get argument name from PatKind::Lit, \
2736                   which is silly in function arguments");
2737             "()".to_string()
2738         },
2739         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
2740                               which is not allowed in function arguments"),
2741         PatKind::Slice(ref begin, ref mid, ref end) => {
2742             let begin = begin.iter().map(|p| name_from_pat(&**p));
2743             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
2744             let end = end.iter().map(|p| name_from_pat(&**p));
2745             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
2746         },
2747     }
2748 }
2749
2750 fn print_const_expr(cx: &DocContext, body: hir::BodyId) -> String {
2751     cx.tcx.hir.node_to_pretty_string(body.node_id)
2752 }
2753
2754 /// Given a type Path, resolve it to a Type using the TyCtxt
2755 fn resolve_type(cx: &DocContext,
2756                 path: Path,
2757                 id: ast::NodeId) -> Type {
2758     debug!("resolve_type({:?},{:?})", path, id);
2759
2760     let is_generic = match path.def {
2761         Def::PrimTy(p) => match p {
2762             hir::TyStr => return Primitive(PrimitiveType::Str),
2763             hir::TyBool => return Primitive(PrimitiveType::Bool),
2764             hir::TyChar => return Primitive(PrimitiveType::Char),
2765             hir::TyInt(int_ty) => return Primitive(int_ty.into()),
2766             hir::TyUint(uint_ty) => return Primitive(uint_ty.into()),
2767             hir::TyFloat(float_ty) => return Primitive(float_ty.into()),
2768         },
2769         Def::SelfTy(..) if path.segments.len() == 1 => {
2770             return Generic(keywords::SelfType.name().to_string());
2771         }
2772         Def::SelfTy(..) | Def::TyParam(..) | Def::AssociatedTy(..) => true,
2773         _ => false,
2774     };
2775     let did = register_def(&*cx, path.def);
2776     ResolvedPath { path: path, typarams: None, did: did, is_generic: is_generic }
2777 }
2778
2779 fn register_def(cx: &DocContext, def: Def) -> DefId {
2780     debug!("register_def({:?})", def);
2781
2782     let (did, kind) = match def {
2783         Def::Fn(i) => (i, TypeKind::Function),
2784         Def::TyAlias(i) => (i, TypeKind::Typedef),
2785         Def::Enum(i) => (i, TypeKind::Enum),
2786         Def::Trait(i) => (i, TypeKind::Trait),
2787         Def::Struct(i) => (i, TypeKind::Struct),
2788         Def::Union(i) => (i, TypeKind::Union),
2789         Def::Mod(i) => (i, TypeKind::Module),
2790         Def::Static(i, _) => (i, TypeKind::Static),
2791         Def::Variant(i) => (cx.tcx.parent_def_id(i).unwrap(), TypeKind::Enum),
2792         Def::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
2793         Def::SelfTy(_, Some(impl_def_id)) => {
2794             return impl_def_id
2795         }
2796         _ => return def.def_id()
2797     };
2798     if did.is_local() { return did }
2799     inline::record_extern_fqn(cx, did, kind);
2800     if let TypeKind::Trait = kind {
2801         let t = inline::build_external_trait(cx, did);
2802         cx.external_traits.borrow_mut().insert(did, t);
2803     }
2804     did
2805 }
2806
2807 fn resolve_use_source(cx: &DocContext, path: Path) -> ImportSource {
2808     ImportSource {
2809         did: if path.def == Def::Err {
2810             None
2811         } else {
2812             Some(register_def(cx, path.def))
2813         },
2814         path: path,
2815     }
2816 }
2817
2818 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2819 pub struct Macro {
2820     pub source: String,
2821     pub imported_from: Option<String>,
2822 }
2823
2824 impl Clean<Item> for doctree::Macro {
2825     fn clean(&self, cx: &DocContext) -> Item {
2826         let name = self.name.clean(cx);
2827         Item {
2828             name: Some(name.clone()),
2829             attrs: self.attrs.clean(cx),
2830             source: self.whence.clean(cx),
2831             visibility: Some(Public),
2832             stability: self.stab.clean(cx),
2833             deprecation: self.depr.clean(cx),
2834             def_id: self.def_id,
2835             inner: MacroItem(Macro {
2836                 source: format!("macro_rules! {} {{\n{}}}",
2837                                 name,
2838                                 self.matchers.iter().map(|span| {
2839                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
2840                                 }).collect::<String>()),
2841                 imported_from: self.imported_from.clean(cx),
2842             }),
2843         }
2844     }
2845 }
2846
2847 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2848 pub struct Stability {
2849     pub level: stability::StabilityLevel,
2850     pub feature: String,
2851     pub since: String,
2852     pub deprecated_since: String,
2853     pub deprecated_reason: String,
2854     pub unstable_reason: String,
2855     pub issue: Option<u32>
2856 }
2857
2858 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2859 pub struct Deprecation {
2860     pub since: String,
2861     pub note: String,
2862 }
2863
2864 impl Clean<Stability> for attr::Stability {
2865     fn clean(&self, _: &DocContext) -> Stability {
2866         Stability {
2867             level: stability::StabilityLevel::from_attr_level(&self.level),
2868             feature: self.feature.to_string(),
2869             since: match self.level {
2870                 attr::Stable {ref since} => since.to_string(),
2871                 _ => "".to_string(),
2872             },
2873             deprecated_since: match self.rustc_depr {
2874                 Some(attr::RustcDeprecation {ref since, ..}) => since.to_string(),
2875                 _=> "".to_string(),
2876             },
2877             deprecated_reason: match self.rustc_depr {
2878                 Some(ref depr) => depr.reason.to_string(),
2879                 _ => "".to_string(),
2880             },
2881             unstable_reason: match self.level {
2882                 attr::Unstable { reason: Some(ref reason), .. } => reason.to_string(),
2883                 _ => "".to_string(),
2884             },
2885             issue: match self.level {
2886                 attr::Unstable {issue, ..} => Some(issue),
2887                 _ => None,
2888             }
2889         }
2890     }
2891 }
2892
2893 impl<'a> Clean<Stability> for &'a attr::Stability {
2894     fn clean(&self, dc: &DocContext) -> Stability {
2895         (**self).clean(dc)
2896     }
2897 }
2898
2899 impl Clean<Deprecation> for attr::Deprecation {
2900     fn clean(&self, _: &DocContext) -> Deprecation {
2901         Deprecation {
2902             since: self.since.as_ref().map_or("".to_string(), |s| s.to_string()),
2903             note: self.note.as_ref().map_or("".to_string(), |s| s.to_string()),
2904         }
2905     }
2906 }
2907
2908 /// An equality constraint on an associated type, e.g. `A=Bar` in `Foo<A=Bar>`
2909 #[derive(Clone, PartialEq, RustcDecodable, RustcEncodable, Debug)]
2910 pub struct TypeBinding {
2911     pub name: String,
2912     pub ty: Type
2913 }
2914
2915 impl Clean<TypeBinding> for hir::TypeBinding {
2916     fn clean(&self, cx: &DocContext) -> TypeBinding {
2917         TypeBinding {
2918             name: self.name.clean(cx),
2919             ty: self.ty.clean(cx)
2920         }
2921     }
2922 }