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