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