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