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::{self, AttrStyle};
  24 use syntax::attr;
  25 use syntax::codemap::Spanned;
  26 use syntax::feature_gate::UnstableFeatures;
  27 use syntax::ptr::P;
  28 use syntax::symbol::keywords;
  29 use syntax::symbol::Symbol;
  30 use syntax_pos::{self, DUMMY_SP, Pos, FileName};
  31
  32 use rustc::middle::const_val::ConstVal;
  33 use rustc::middle::privacy::AccessLevels;
  34 use rustc::middle::resolve_lifetime as rl;
  35 use rustc::ty::fold::TypeFolder;
  36 use rustc::middle::lang_items;
  37 use rustc::mir::interpret::GlobalId;
  38 use rustc::hir::{self, HirVec};
  39 use rustc::hir::def::{self, Def, CtorKind};
  40 use rustc::hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX, LOCAL_CRATE};
  41 use rustc::hir::def_id::DefIndexAddressSpace;
  42 use rustc::traits;
  43 use rustc::ty::subst::Substs;
  44 use rustc::ty::{self, TyCtxt, Region, RegionVid, Ty, AdtKind};
  45 use rustc::middle::stability;
  46 use rustc::util::nodemap::{FxHashMap, FxHashSet};
  47 use rustc_typeck::hir_ty_to_ty;
  48 use rustc::infer::{InferCtxt, RegionObligation};
  49 use rustc::infer::region_constraints::{RegionConstraintData, Constraint};
  50 use rustc::traits::*;
  51 use std::collections::hash_map::Entry;
  52 use std::collections::VecDeque;
  53 use std::fmt;
  54
  55 use std::default::Default;
  56 use std::{mem, slice, vec};
  57 use std::iter::{FromIterator, once};
  58 use rustc_data_structures::sync::Lrc;
  59 use std::rc::Rc;
  60 use std::cell::RefCell;
  61 use std::sync::Arc;
  62 use std::u32;
  63
  64 use core::{self, DocContext};
  65 use doctree;
  66 use visit_ast;
  67 use html::item_type::ItemType;
  68 use html::markdown::markdown_links;
  69
  70 pub mod inline;
  71 pub mod cfg;
  72 mod simplify;
  73 mod auto_trait;
  74
  75 use self::cfg::Cfg;
  76 use self::auto_trait::AutoTraitFinder;
  77
  78 thread_local!(static MAX_DEF_ID: RefCell<FxHashMap<CrateNum, DefId>> = RefCell::new(FxHashMap()));
  79
  80 const FN_OUTPUT_NAME: &'static str = "Output";
  81
  82 // extract the stability index for a node from tcx, if possible
  83 fn get_stability(cx: &DocContext, def_id: DefId) -> Option<Stability> {
  84     cx.tcx.lookup_stability(def_id).clean(cx)
  85 }
  86
  87 fn get_deprecation(cx: &DocContext, def_id: DefId) -> Option<Deprecation> {
  88     cx.tcx.lookup_deprecation(def_id).clean(cx)
  89 }
  90
  91 pub trait Clean<T> {
  92     fn clean(&self, cx: &DocContext) -> T;
  93 }
  94
  95 impl<T: Clean<U>, U> Clean<Vec<U>> for [T] {
  96     fn clean(&self, cx: &DocContext) -> Vec<U> {
  97         self.iter().map(|x| x.clean(cx)).collect()
  98     }
  99 }
 100
 101 impl<T: Clean<U>, U> Clean<U> for P<T> {
 102     fn clean(&self, cx: &DocContext) -> U {
 103         (**self).clean(cx)
 104     }
 105 }
 106
 107 impl<T: Clean<U>, U> Clean<U> for Rc<T> {
 108     fn clean(&self, cx: &DocContext) -> U {
 109         (**self).clean(cx)
 110     }
 111 }
 112
 113 impl<T: Clean<U>, U> Clean<Option<U>> for Option<T> {
 114     fn clean(&self, cx: &DocContext) -> Option<U> {
 115         self.as_ref().map(|v| v.clean(cx))
 116     }
 117 }
 118
 119 impl<T, U> Clean<U> for ty::Binder<T> where T: Clean<U> {
 120     fn clean(&self, cx: &DocContext) -> U {
 121         self.0.clean(cx)
 122     }
 123 }
 124
 125 impl<T: Clean<U>, U> Clean<Vec<U>> for P<[T]> {
 126     fn clean(&self, cx: &DocContext) -> Vec<U> {
 127         self.iter().map(|x| x.clean(cx)).collect()
 128     }
 129 }
 130
 131 #[derive(Clone, Debug)]
 132 pub struct Crate {
 133     pub name: String,
 134     pub version: Option<String>,
 135     pub src: FileName,
 136     pub module: Option<Item>,
 137     pub externs: Vec<(CrateNum, ExternalCrate)>,
 138     pub primitives: Vec<(DefId, PrimitiveType, Attributes)>,
 139     pub access_levels: Arc<AccessLevels<DefId>>,
 140     // These are later on moved into `CACHEKEY`, leaving the map empty.
 141     // Only here so that they can be filtered through the rustdoc passes.
 142     pub external_traits: FxHashMap<DefId, Trait>,
 143     pub masked_crates: FxHashSet<CrateNum>,
 144 }
 145
 146 impl<'a, 'tcx, 'rcx> Clean<Crate> for visit_ast::RustdocVisitor<'a, 'tcx, 'rcx> {
 147     fn clean(&self, cx: &DocContext) -> Crate {
 148         use ::visit_lib::LibEmbargoVisitor;
 149
 150         {
 151             let mut r = cx.renderinfo.borrow_mut();
 152             r.deref_trait_did = cx.tcx.lang_items().deref_trait();
 153             r.deref_mut_trait_did = cx.tcx.lang_items().deref_mut_trait();
 154             r.owned_box_did = cx.tcx.lang_items().owned_box();
 155         }
 156
 157         let mut externs = Vec::new();
 158         for &cnum in cx.tcx.crates().iter() {
 159             externs.push((cnum, cnum.clean(cx)));
 160             // Analyze doc-reachability for extern items
 161             LibEmbargoVisitor::new(cx).visit_lib(cnum);
 162         }
 163         externs.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
 164
 165         // Clean the crate, translating the entire libsyntax AST to one that is
 166         // understood by rustdoc.
 167         let mut module = self.module.clean(cx);
 168         let mut masked_crates = FxHashSet();
 169
 170         match module.inner {
 171             ModuleItem(ref module) => {
 172                 for it in &module.items {
 173                     if it.is_extern_crate() && it.attrs.has_doc_flag("masked") {
 174                         masked_crates.insert(it.def_id.krate);
 175                     }
 176                 }
 177             }
 178             _ => unreachable!(),
 179         }
 180
 181         let ExternalCrate { name, src, primitives, .. } = LOCAL_CRATE.clean(cx);
 182         {
 183             let m = match module.inner {
 184                 ModuleItem(ref mut m) => m,
 185                 _ => unreachable!(),
 186             };
 187             m.items.extend(primitives.iter().map(|&(def_id, prim, ref attrs)| {
 188                 Item {
 189                     source: Span::empty(),
 190                     name: Some(prim.to_url_str().to_string()),
 191                     attrs: attrs.clone(),
 192                     visibility: Some(Public),
 193                     stability: get_stability(cx, def_id),
 194                     deprecation: get_deprecation(cx, def_id),
 195                     def_id,
 196                     inner: PrimitiveItem(prim),
 197                 }
 198             }));
 199         }
 200
 201         let mut access_levels = cx.access_levels.borrow_mut();
 202         let mut external_traits = cx.external_traits.borrow_mut();
 203
 204         Crate {
 205             name,
 206             version: None,
 207             src,
 208             module: Some(module),
 209             externs,
 210             primitives,
 211             access_levels: Arc::new(mem::replace(&mut access_levels, Default::default())),
 212             external_traits: mem::replace(&mut external_traits, Default::default()),
 213             masked_crates,
 214         }
 215     }
 216 }
 217
 218 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
 219 pub struct ExternalCrate {
 220     pub name: String,
 221     pub src: FileName,
 222     pub attrs: Attributes,
 223     pub primitives: Vec<(DefId, PrimitiveType, Attributes)>,
 224 }
 225
 226 impl Clean<ExternalCrate> for CrateNum {
 227     fn clean(&self, cx: &DocContext) -> ExternalCrate {
 228         let root = DefId { krate: *self, index: CRATE_DEF_INDEX };
 229         let krate_span = cx.tcx.def_span(root);
 230         let krate_src = cx.sess().codemap().span_to_filename(krate_span);
 231
 232         // Collect all inner modules which are tagged as implementations of
 233         // primitives.
 234         //
 235         // Note that this loop only searches the top-level items of the crate,
 236         // and this is intentional. If we were to search the entire crate for an
 237         // item tagged with `#[doc(primitive)]` then we would also have to
 238         // search the entirety of external modules for items tagged
 239         // `#[doc(primitive)]`, which is a pretty inefficient process (decoding
 240         // all that metadata unconditionally).
 241         //
 242         // In order to keep the metadata load under control, the
 243         // `#[doc(primitive)]` feature is explicitly designed to only allow the
 244         // primitive tags to show up as the top level items in a crate.
 245         //
 246         // Also note that this does not attempt to deal with modules tagged
 247         // duplicately for the same primitive. This is handled later on when
 248         // rendering by delegating everything to a hash map.
 249         let as_primitive = |def: Def| {
 250             if let Def::Mod(def_id) = def {
 251                 let attrs = cx.tcx.get_attrs(def_id).clean(cx);
 252                 let mut prim = None;
 253                 for attr in attrs.lists("doc") {
 254                     if let Some(v) = attr.value_str() {
 255                         if attr.check_name("primitive") {
 256                             prim = PrimitiveType::from_str(&v.as_str());
 257                             if prim.is_some() {
 258                                 break;
 259                             }
 260                             // FIXME: should warn on unknown primitives?
 261                         }
 262                     }
 263                 }
 264                 return prim.map(|p| (def_id, p, attrs));
 265             }
 266             None
 267         };
 268         let primitives = if root.is_local() {
 269             cx.tcx.hir.krate().module.item_ids.iter().filter_map(|&id| {
 270                 let item = cx.tcx.hir.expect_item(id.id);
 271                 match item.node {
 272                     hir::ItemMod(_) => {
 273                         as_primitive(Def::Mod(cx.tcx.hir.local_def_id(id.id)))
 274                     }
 275                     hir::ItemUse(ref path, hir::UseKind::Single)
 276                     if item.vis == hir::Visibility::Public => {
 277                         as_primitive(path.def).map(|(_, prim, attrs)| {
 278                             // Pretend the primitive is local.
 279                             (cx.tcx.hir.local_def_id(id.id), prim, attrs)
 280                         })
 281                     }
 282                     _ => None
 283                 }
 284             }).collect()
 285         } else {
 286             cx.tcx.item_children(root).iter().map(|item| item.def)
 287               .filter_map(as_primitive).collect()
 288         };
 289
 290         ExternalCrate {
 291             name: cx.tcx.crate_name(*self).to_string(),
 292             src: krate_src,
 293             attrs: cx.tcx.get_attrs(root).clean(cx),
 294             primitives,
 295         }
 296     }
 297 }
 298
 299 /// Anything with a source location and set of attributes and, optionally, a
 300 /// name. That is, anything that can be documented. This doesn't correspond
 301 /// directly to the AST's concept of an item; it's a strict superset.
 302 #[derive(Clone, RustcEncodable, RustcDecodable)]
 303 pub struct Item {
 304     /// Stringified span
 305     pub source: Span,
 306     /// Not everything has a name. E.g., impls
 307     pub name: Option<String>,
 308     pub attrs: Attributes,
 309     pub inner: ItemEnum,
 310     pub visibility: Option<Visibility>,
 311     pub def_id: DefId,
 312     pub stability: Option<Stability>,
 313     pub deprecation: Option<Deprecation>,
 314 }
 315
 316 impl fmt::Debug for Item {
 317     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 318
 319         let fake = MAX_DEF_ID.with(|m| m.borrow().get(&self.def_id.krate)
 320                                    .map(|id| self.def_id >= *id).unwrap_or(false));
 321         let def_id: &fmt::Debug = if fake { &"**FAKE**" } else { &self.def_id };
 322
 323         fmt.debug_struct("Item")
 324             .field("source", &self.source)
 325             .field("name", &self.name)
 326             .field("attrs", &self.attrs)
 327             .field("inner", &self.inner)
 328             .field("visibility", &self.visibility)
 329             .field("def_id", def_id)
 330             .field("stability", &self.stability)
 331             .field("deprecation", &self.deprecation)
 332             .finish()
 333     }
 334 }
 335
 336 impl Item {
 337     /// Finds the `doc` attribute as a NameValue and returns the corresponding
 338     /// value found.
 339     pub fn doc_value<'a>(&'a self) -> Option<&'a str> {
 340         self.attrs.doc_value()
 341     }
 342     /// Finds all `doc` attributes as NameValues and returns their corresponding values, joined
 343     /// with newlines.
 344     pub fn collapsed_doc_value(&self) -> Option<String> {
 345         self.attrs.collapsed_doc_value()
 346     }
 347
 348     pub fn links(&self) -> Vec<(String, String)> {
 349         self.attrs.links()
 350     }
 351
 352     pub fn is_crate(&self) -> bool {
 353         match self.inner {
 354             StrippedItem(box ModuleItem(Module { is_crate: true, ..})) |
 355             ModuleItem(Module { is_crate: true, ..}) => true,
 356             _ => false,
 357         }
 358     }
 359     pub fn is_mod(&self) -> bool {
 360         self.type_() == ItemType::Module
 361     }
 362     pub fn is_trait(&self) -> bool {
 363         self.type_() == ItemType::Trait
 364     }
 365     pub fn is_struct(&self) -> bool {
 366         self.type_() == ItemType::Struct
 367     }
 368     pub fn is_enum(&self) -> bool {
 369         self.type_() == ItemType::Enum
 370     }
 371     pub fn is_fn(&self) -> bool {
 372         self.type_() == ItemType::Function
 373     }
 374     pub fn is_associated_type(&self) -> bool {
 375         self.type_() == ItemType::AssociatedType
 376     }
 377     pub fn is_associated_const(&self) -> bool {
 378         self.type_() == ItemType::AssociatedConst
 379     }
 380     pub fn is_method(&self) -> bool {
 381         self.type_() == ItemType::Method
 382     }
 383     pub fn is_ty_method(&self) -> bool {
 384         self.type_() == ItemType::TyMethod
 385     }
 386     pub fn is_typedef(&self) -> bool {
 387         self.type_() == ItemType::Typedef
 388     }
 389     pub fn is_primitive(&self) -> bool {
 390         self.type_() == ItemType::Primitive
 391     }
 392     pub fn is_union(&self) -> bool {
 393         self.type_() == ItemType::Union
 394     }
 395     pub fn is_import(&self) -> bool {
 396         self.type_() == ItemType::Import
 397     }
 398     pub fn is_extern_crate(&self) -> bool {
 399         self.type_() == ItemType::ExternCrate
 400     }
 401
 402     pub fn is_stripped(&self) -> bool {
 403         match self.inner { StrippedItem(..) => true, _ => false }
 404     }
 405     pub fn has_stripped_fields(&self) -> Option<bool> {
 406         match self.inner {
 407             StructItem(ref _struct) => Some(_struct.fields_stripped),
 408             UnionItem(ref union) => Some(union.fields_stripped),
 409             VariantItem(Variant { kind: VariantKind::Struct(ref vstruct)} ) => {
 410                 Some(vstruct.fields_stripped)
 411             },
 412             _ => None,
 413         }
 414     }
 415
 416     pub fn stability_class(&self) -> Option<String> {
 417         self.stability.as_ref().and_then(|ref s| {
 418             let mut classes = Vec::with_capacity(2);
 419
 420             if s.level == stability::Unstable {
 421                 classes.push("unstable");
 422             }
 423
 424             if !s.deprecated_since.is_empty() {
 425                 classes.push("deprecated");
 426             }
 427
 428             if classes.len() != 0 {
 429                 Some(classes.join(" "))
 430             } else {
 431                 None
 432             }
 433         })
 434     }
 435
 436     pub fn stable_since(&self) -> Option<&str> {
 437         self.stability.as_ref().map(|s| &s.since[..])
 438     }
 439
 440     /// Returns a documentation-level item type from the item.
 441     pub fn type_(&self) -> ItemType {
 442         ItemType::from(self)
 443     }
 444 }
 445
 446 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
 447 pub enum ItemEnum {
 448     ExternCrateItem(String, Option<String>),
 449     ImportItem(Import),
 450     StructItem(Struct),
 451     UnionItem(Union),
 452     EnumItem(Enum),
 453     FunctionItem(Function),
 454     ModuleItem(Module),
 455     TypedefItem(Typedef, bool /* is associated type */),
 456     StaticItem(Static),
 457     ConstantItem(Constant),
 458     TraitItem(Trait),
 459     ImplItem(Impl),
 460     /// A method signature only. Used for required methods in traits (ie,
 461     /// non-default-methods).
 462     TyMethodItem(TyMethod),
 463     /// A method with a body.
 464     MethodItem(Method),
 465     StructFieldItem(Type),
 466     VariantItem(Variant),
 467     /// `fn`s from an extern block
 468     ForeignFunctionItem(Function),
 469     /// `static`s from an extern block
 470     ForeignStaticItem(Static),
 471     /// `type`s from an extern block
 472     ForeignTypeItem,
 473     MacroItem(Macro),
 474     PrimitiveItem(PrimitiveType),
 475     AssociatedConstItem(Type, Option<String>),
 476     AssociatedTypeItem(Vec<TyParamBound>, Option<Type>),
 477     /// An item that has been stripped by a rustdoc pass
 478     StrippedItem(Box<ItemEnum>),
 479 }
 480
 481 impl ItemEnum {
 482     pub fn generics(&self) -> Option<&Generics> {
 483         Some(match *self {
 484             ItemEnum::StructItem(ref s) => &s.generics,
 485             ItemEnum::EnumItem(ref e) => &e.generics,
 486             ItemEnum::FunctionItem(ref f) => &f.generics,
 487             ItemEnum::TypedefItem(ref t, _) => &t.generics,
 488             ItemEnum::TraitItem(ref t) => &t.generics,
 489             ItemEnum::ImplItem(ref i) => &i.generics,
 490             ItemEnum::TyMethodItem(ref i) => &i.generics,
 491             ItemEnum::MethodItem(ref i) => &i.generics,
 492             ItemEnum::ForeignFunctionItem(ref f) => &f.generics,
 493             _ => return None,
 494         })
 495     }
 496 }
 497
 498 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
 499 pub struct Module {
 500     pub items: Vec<Item>,
 501     pub is_crate: bool,
 502 }
 503
 504 impl Clean<Item> for doctree::Module {
 505     fn clean(&self, cx: &DocContext) -> Item {
 506         let name = if self.name.is_some() {
 507             self.name.unwrap().clean(cx)
 508         } else {
 509             "".to_string()
 510         };
 511
 512         // maintain a stack of mod ids, for doc comment path resolution
 513         // but we also need to resolve the module's own docs based on whether its docs were written
 514         // inside or outside the module, so check for that
 515         let attrs = if self.attrs.iter()
 516                                  .filter(|a| a.check_name("doc"))
 517                                  .next()
 518                                  .map_or(true, |a| a.style == AttrStyle::Inner) {
 519             // inner doc comment, use the module's own scope for resolution
 520             cx.mod_ids.borrow_mut().push(self.id);
 521             self.attrs.clean(cx)
 522         } else {
 523             // outer doc comment, use its parent's scope
 524             let attrs = self.attrs.clean(cx);
 525             cx.mod_ids.borrow_mut().push(self.id);
 526             attrs
 527         };
 528
 529         let mut items: Vec<Item> = vec![];
 530         items.extend(self.extern_crates.iter().map(|x| x.clean(cx)));
 531         items.extend(self.imports.iter().flat_map(|x| x.clean(cx)));
 532         items.extend(self.structs.iter().flat_map(|x| x.clean(cx)));
 533         items.extend(self.unions.iter().flat_map(|x| x.clean(cx)));
 534         items.extend(self.enums.iter().flat_map(|x| x.clean(cx)));
 535         items.extend(self.fns.iter().map(|x| x.clean(cx)));
 536         items.extend(self.foreigns.iter().flat_map(|x| x.clean(cx)));
 537         items.extend(self.mods.iter().map(|x| x.clean(cx)));
 538         items.extend(self.typedefs.iter().map(|x| x.clean(cx)));
 539         items.extend(self.statics.iter().map(|x| x.clean(cx)));
 540         items.extend(self.constants.iter().map(|x| x.clean(cx)));
 541         items.extend(self.traits.iter().map(|x| x.clean(cx)));
 542         items.extend(self.impls.iter().flat_map(|x| x.clean(cx)));
 543         items.extend(self.macros.iter().map(|x| x.clean(cx)));
 544
 545         cx.mod_ids.borrow_mut().pop();
 546
 547         // determine if we should display the inner contents or
 548         // the outer `mod` item for the source code.
 549         let whence = {
 550             let cm = cx.sess().codemap();
 551             let outer = cm.lookup_char_pos(self.where_outer.lo());
 552             let inner = cm.lookup_char_pos(self.where_inner.lo());
 553             if outer.file.start_pos == inner.file.start_pos {
 554                 // mod foo { ... }
 555                 self.where_outer
 556             } else {
 557                 // mod foo; (and a separate FileMap for the contents)
 558                 self.where_inner
 559             }
 560         };
 561
 562         Item {
 563             name: Some(name),
 564             attrs,
 565             source: whence.clean(cx),
 566             visibility: self.vis.clean(cx),
 567             stability: self.stab.clean(cx),
 568             deprecation: self.depr.clean(cx),
 569             def_id: cx.tcx.hir.local_def_id(self.id),
 570             inner: ModuleItem(Module {
 571                is_crate: self.is_crate,
 572                items,
 573             })
 574         }
 575     }
 576 }
 577
 578 pub struct ListAttributesIter<'a> {
 579     attrs: slice::Iter<'a, ast::Attribute>,
 580     current_list: vec::IntoIter<ast::NestedMetaItem>,
 581     name: &'a str
 582 }
 583
 584 impl<'a> Iterator for ListAttributesIter<'a> {
 585     type Item = ast::NestedMetaItem;
 586
 587     fn next(&mut self) -> Option<Self::Item> {
 588         if let Some(nested) = self.current_list.next() {
 589             return Some(nested);
 590         }
 591
 592         for attr in &mut self.attrs {
 593             if let Some(list) = attr.meta_item_list() {
 594                 if attr.check_name(self.name) {
 595                     self.current_list = list.into_iter();
 596                     if let Some(nested) = self.current_list.next() {
 597                         return Some(nested);
 598                     }
 599                 }
 600             }
 601         }
 602
 603         None
 604     }
 605 }
 606
 607 pub trait AttributesExt {
 608     /// Finds an attribute as List and returns the list of attributes nested inside.
 609     fn lists<'a>(&'a self, name: &'a str) -> ListAttributesIter<'a>;
 610 }
 611
 612 impl AttributesExt for [ast::Attribute] {
 613     fn lists<'a>(&'a self, name: &'a str) -> ListAttributesIter<'a> {
 614         ListAttributesIter {
 615             attrs: self.iter(),
 616             current_list: Vec::new().into_iter(),
 617             name,
 618         }
 619     }
 620 }
 621
 622 pub trait NestedAttributesExt {
 623     /// Returns whether the attribute list contains a specific `Word`
 624     fn has_word(self, word: &str) -> bool;
 625 }
 626
 627 impl<I: IntoIterator<Item=ast::NestedMetaItem>> NestedAttributesExt for I {
 628     fn has_word(self, word: &str) -> bool {
 629         self.into_iter().any(|attr| attr.is_word() && attr.check_name(word))
 630     }
 631 }
 632
 633 /// A portion of documentation, extracted from a `#[doc]` attribute.
 634 ///
 635 /// Each variant contains the line number within the complete doc-comment where the fragment
 636 /// starts, as well as the Span where the corresponding doc comment or attribute is located.
 637 ///
 638 /// Included files are kept separate from inline doc comments so that proper line-number
 639 /// information can be given when a doctest fails. Sugared doc comments and "raw" doc comments are
 640 /// kept separate because of issue #42760.
 641 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
 642 pub enum DocFragment {
 643     // FIXME #44229 (misdreavus): sugared and raw doc comments can be brought back together once
 644     // hoedown is completely removed from rustdoc.
 645     /// A doc fragment created from a `///` or `//!` doc comment.
 646     SugaredDoc(usize, syntax_pos::Span, String),
 647     /// A doc fragment created from a "raw" `#[doc=""]` attribute.
 648     RawDoc(usize, syntax_pos::Span, String),
 649     /// A doc fragment created from a `#[doc(include="filename")]` attribute. Contains both the
 650     /// given filename and the file contents.
 651     Include(usize, syntax_pos::Span, String, String),
 652 }
 653
 654 impl DocFragment {
 655     pub fn as_str(&self) -> &str {
 656         match *self {
 657             DocFragment::SugaredDoc(_, _, ref s) => &s[..],
 658             DocFragment::RawDoc(_, _, ref s) => &s[..],
 659             DocFragment::Include(_, _, _, ref s) => &s[..],
 660         }
 661     }
 662
 663     pub fn span(&self) -> syntax_pos::Span {
 664         match *self {
 665             DocFragment::SugaredDoc(_, span, _) |
 666                 DocFragment::RawDoc(_, span, _) |
 667                 DocFragment::Include(_, span, _, _) => span,
 668         }
 669     }
 670 }
 671
 672 impl<'a> FromIterator<&'a DocFragment> for String {
 673     fn from_iter<T>(iter: T) -> Self
 674     where
 675         T: IntoIterator<Item = &'a DocFragment>
 676     {
 677         iter.into_iter().fold(String::new(), |mut acc, frag| {
 678             if !acc.is_empty() {
 679                 acc.push('\n');
 680             }
 681             match *frag {
 682                 DocFragment::SugaredDoc(_, _, ref docs)
 683                     | DocFragment::RawDoc(_, _, ref docs)
 684                     | DocFragment::Include(_, _, _, ref docs) =>
 685                     acc.push_str(docs),
 686             }
 687
 688             acc
 689         })
 690     }
 691 }
 692
 693 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Default, Hash)]
 694 pub struct Attributes {
 695     pub doc_strings: Vec<DocFragment>,
 696     pub other_attrs: Vec<ast::Attribute>,
 697     pub cfg: Option<Rc<Cfg>>,
 698     pub span: Option<syntax_pos::Span>,
 699     /// map from Rust paths to resolved defs and potential URL fragments
 700     pub links: Vec<(String, DefId, Option<String>)>,
 701 }
 702
 703 impl Attributes {
 704     /// Extracts the content from an attribute `#[doc(cfg(content))]`.
 705     fn extract_cfg(mi: &ast::MetaItem) -> Option<&ast::MetaItem> {
 706         use syntax::ast::NestedMetaItemKind::MetaItem;
 707
 708         if let ast::MetaItemKind::List(ref nmis) = mi.node {
 709             if nmis.len() == 1 {
 710                 if let MetaItem(ref cfg_mi) = nmis[0].node {
 711                     if cfg_mi.check_name("cfg") {
 712                         if let ast::MetaItemKind::List(ref cfg_nmis) = cfg_mi.node {
 713                             if cfg_nmis.len() == 1 {
 714                                 if let MetaItem(ref content_mi) = cfg_nmis[0].node {
 715                                     return Some(content_mi);
 716                                 }
 717                             }
 718                         }
 719                     }
 720                 }
 721             }
 722         }
 723
 724         None
 725     }
 726
 727     /// Reads a `MetaItem` from within an attribute, looks for whether it is a
 728     /// `#[doc(include="file")]`, and returns the filename and contents of the file as loaded from
 729     /// its expansion.
 730     fn extract_include(mi: &ast::MetaItem)
 731         -> Option<(String, String)>
 732     {
 733         mi.meta_item_list().and_then(|list| {
 734             for meta in list {
 735                 if meta.check_name("include") {
 736                     // the actual compiled `#[doc(include="filename")]` gets expanded to
 737                     // `#[doc(include(file="filename", contents="file contents")]` so we need to
 738                     // look for that instead
 739                     return meta.meta_item_list().and_then(|list| {
 740                         let mut filename: Option<String> = None;
 741                         let mut contents: Option<String> = None;
 742
 743                         for it in list {
 744                             if it.check_name("file") {
 745                                 if let Some(name) = it.value_str() {
 746                                     filename = Some(name.to_string());
 747                                 }
 748                             } else if it.check_name("contents") {
 749                                 if let Some(docs) = it.value_str() {
 750                                     contents = Some(docs.to_string());
 751                                 }
 752                             }
 753                         }
 754
 755                         if let (Some(filename), Some(contents)) = (filename, contents) {
 756                             Some((filename, contents))
 757                         } else {
 758                             None
 759                         }
 760                     });
 761                 }
 762             }
 763
 764             None
 765         })
 766     }
 767
 768     pub fn has_doc_flag(&self, flag: &str) -> bool {
 769         for attr in &self.other_attrs {
 770             if !attr.check_name("doc") { continue; }
 771
 772             if let Some(items) = attr.meta_item_list() {
 773                 if items.iter().filter_map(|i| i.meta_item()).any(|it| it.check_name(flag)) {
 774                     return true;
 775                 }
 776             }
 777         }
 778
 779         false
 780     }
 781
 782     pub fn from_ast(diagnostic: &::errors::Handler,
 783                     attrs: &[ast::Attribute]) -> Attributes {
 784         let mut doc_strings = vec![];
 785         let mut sp = None;
 786         let mut cfg = Cfg::True;
 787         let mut doc_line = 0;
 788
 789         let other_attrs = attrs.iter().filter_map(|attr| {
 790             attr.with_desugared_doc(|attr| {
 791                 if attr.check_name("doc") {
 792                     if let Some(mi) = attr.meta() {
 793                         if let Some(value) = mi.value_str() {
 794                             // Extracted #[doc = "..."]
 795                             let value = value.to_string();
 796                             let line = doc_line;
 797                             doc_line += value.lines().count();
 798
 799                             if attr.is_sugared_doc {
 800                                 doc_strings.push(DocFragment::SugaredDoc(line, attr.span, value));
 801                             } else {
 802                                 doc_strings.push(DocFragment::RawDoc(line, attr.span, value));
 803                             }
 804
 805                             if sp.is_none() {
 806                                 sp = Some(attr.span);
 807                             }
 808                             return None;
 809                         } else if let Some(cfg_mi) = Attributes::extract_cfg(&mi) {
 810                             // Extracted #[doc(cfg(...))]
 811                             match Cfg::parse(cfg_mi) {
 812                                 Ok(new_cfg) => cfg &= new_cfg,
 813                                 Err(e) => diagnostic.span_err(e.span, e.msg),
 814                             }
 815                             return None;
 816                         } else if let Some((filename, contents)) = Attributes::extract_include(&mi)
 817                         {
 818                             let line = doc_line;
 819                             doc_line += contents.lines().count();
 820                             doc_strings.push(DocFragment::Include(line,
 821                                                                   attr.span,
 822                                                                   filename,
 823                                                                   contents));
 824                         }
 825                     }
 826                 }
 827                 Some(attr.clone())
 828             })
 829         }).collect();
 830
 831         // treat #[target_feature(enable = "feat")] attributes as if they were
 832         // #[doc(cfg(target_feature = "feat"))] attributes as well
 833         for attr in attrs.lists("target_feature") {
 834             if attr.check_name("enable") {
 835                 if let Some(feat) = attr.value_str() {
 836                     let meta = attr::mk_name_value_item_str("target_feature".into(), feat);
 837                     if let Ok(feat_cfg) = Cfg::parse(&meta) {
 838                         cfg &= feat_cfg;
 839                     }
 840                 }
 841             }
 842         }
 843
 844         Attributes {
 845             doc_strings,
 846             other_attrs,
 847             cfg: if cfg == Cfg::True { None } else { Some(Rc::new(cfg)) },
 848             span: sp,
 849             links: vec![],
 850         }
 851     }
 852
 853     /// Finds the `doc` attribute as a NameValue and returns the corresponding
 854     /// value found.
 855     pub fn doc_value<'a>(&'a self) -> Option<&'a str> {
 856         self.doc_strings.first().map(|s| s.as_str())
 857     }
 858
 859     /// Finds all `doc` attributes as NameValues and returns their corresponding values, joined
 860     /// with newlines.
 861     pub fn collapsed_doc_value(&self) -> Option<String> {
 862         if !self.doc_strings.is_empty() {
 863             Some(self.doc_strings.iter().collect())
 864         } else {
 865             None
 866         }
 867     }
 868
 869     /// Get links as a vector
 870     ///
 871     /// Cache must be populated before call
 872     pub fn links(&self) -> Vec<(String, String)> {
 873         use html::format::href;
 874         self.links.iter().filter_map(|&(ref s, did, ref fragment)| {
 875             if let Some((mut href, ..)) = href(did) {
 876                 if let Some(ref fragment) = *fragment {
 877                     href.push_str("#");
 878                     href.push_str(fragment);
 879                 }
 880                 Some((s.clone(), href))
 881             } else {
 882                 None
 883             }
 884         }).collect()
 885     }
 886 }
 887
 888 impl AttributesExt for Attributes {
 889     fn lists<'a>(&'a self, name: &'a str) -> ListAttributesIter<'a> {
 890         self.other_attrs.lists(name)
 891     }
 892 }
 893
 894 /// Given a def, returns its name and disambiguator
 895 /// for a value namespace
 896 ///
 897 /// Returns None for things which cannot be ambiguous since
 898 /// they exist in both namespaces (structs and modules)
 899 fn value_ns_kind(def: Def, path_str: &str) -> Option<(&'static str, String)> {
 900     match def {
 901         // structs, variants, and mods exist in both namespaces. skip them
 902         Def::StructCtor(..) | Def::Mod(..) | Def::Variant(..) | Def::VariantCtor(..) => None,
 903         Def::Fn(..)
 904             => Some(("function", format!("{}()", path_str))),
 905         Def::Method(..)
 906             => Some(("method", format!("{}()", path_str))),
 907         Def::Const(..)
 908             => Some(("const", format!("const@{}", path_str))),
 909         Def::Static(..)
 910             => Some(("static", format!("static@{}", path_str))),
 911         _ => Some(("value", format!("value@{}", path_str))),
 912     }
 913 }
 914
 915 /// Given a def, returns its name, the article to be used, and a disambiguator
 916 /// for the type namespace
 917 fn type_ns_kind(def: Def, path_str: &str) -> (&'static str, &'static str, String) {
 918     let (kind, article) = match def {
 919         // we can still have non-tuple structs
 920         Def::Struct(..) => ("struct", "a"),
 921         Def::Enum(..) => ("enum", "an"),
 922         Def::Trait(..) => ("trait", "a"),
 923         Def::Union(..) => ("union", "a"),
 924         _ => ("type", "a"),
 925     };
 926     (kind, article, format!("{}@{}", kind, path_str))
 927 }
 928
 929 fn ambiguity_error(cx: &DocContext, attrs: &Attributes,
 930                    path_str: &str,
 931                    article1: &str, kind1: &str, disambig1: &str,
 932                    article2: &str, kind2: &str, disambig2: &str) {
 933     let sp = attrs.doc_strings.first()
 934                   .map_or(DUMMY_SP, |a| a.span());
 935     cx.sess()
 936       .struct_span_warn(sp,
 937                         &format!("`{}` is both {} {} and {} {}",
 938                                  path_str, article1, kind1,
 939                                  article2, kind2))
 940       .help(&format!("try `{}` if you want to select the {}, \
 941                       or `{}` if you want to \
 942                       select the {}",
 943                       disambig1, kind1, disambig2,
 944                       kind2))
 945       .emit();
 946 }
 947
 948 /// Given an enum variant's def, return the def of its enum and the associated fragment
 949 fn handle_variant(cx: &DocContext, def: Def) -> Result<(Def, Option<String>), ()> {
 950     use rustc::ty::DefIdTree;
 951
 952     let parent = if let Some(parent) = cx.tcx.parent(def.def_id()) {
 953         parent
 954     } else {
 955         return Err(())
 956     };
 957     let parent_def = Def::Enum(parent);
 958     let variant = cx.tcx.expect_variant_def(def);
 959     Ok((parent_def, Some(format!("{}.v", variant.name))))
 960 }
 961
 962 /// Resolve a given string as a path, along with whether or not it is
 963 /// in the value namespace. Also returns an optional URL fragment in the case
 964 /// of variants and methods
 965 fn resolve(cx: &DocContext, path_str: &str, is_val: bool) -> Result<(Def, Option<String>), ()> {
 966     // In case we're in a module, try to resolve the relative
 967     // path
 968     if let Some(id) = cx.mod_ids.borrow().last() {
 969         let result = cx.resolver.borrow_mut()
 970                                 .with_scope(*id,
 971             |resolver| {
 972                 resolver.resolve_str_path_error(DUMMY_SP,
 973                                                 &path_str, is_val)
 974         });
 975
 976         if let Ok(result) = result {
 977             // In case this is a trait item, skip the
 978             // early return and try looking for the trait
 979             let value = match result.def {
 980                 Def::Method(_) | Def::AssociatedConst(_) => true,
 981                 Def::AssociatedTy(_)  => false,
 982                 Def::Variant(_) => return handle_variant(cx, result.def),
 983                 // not a trait item, just return what we found
 984                 _ => return Ok((result.def, None))
 985             };
 986
 987             if value != is_val {
 988                 return Err(())
 989             }
 990         } else {
 991             // If resolution failed, it may still be a method
 992             // because methods are not handled by the resolver
 993             // If so, bail when we're not looking for a value
 994             if !is_val {
 995                 return Err(())
 996             }
 997         }
 998
 999         // Try looking for methods and associated items
1000         let mut split = path_str.rsplitn(2, "::");
1001         let mut item_name = if let Some(first) = split.next() {
1002             first
1003         } else {
1004             return Err(())
1005         };
1006
1007         let mut path = if let Some(second) = split.next() {
1008             second
1009         } else {
1010             return Err(())
1011         };
1012
1013         let ty = cx.resolver.borrow_mut()
1014                             .with_scope(*id,
1015             |resolver| {
1016                 resolver.resolve_str_path_error(DUMMY_SP,
1017                                                 &path, false)
1018         })?;
1019         match ty.def {
1020             Def::Struct(did) | Def::Union(did) | Def::Enum(did) | Def::TyAlias(did) => {
1021                 let item = cx.tcx.inherent_impls(did).iter()
1022                                  .flat_map(|imp| cx.tcx.associated_items(*imp))
1023                                  .find(|item| item.name == item_name);
1024                 if let Some(item) = item {
1025                     if item.kind == ty::AssociatedKind::Method && is_val {
1026                         Ok((ty.def, Some(format!("method.{}", item_name))))
1027                     } else {
1028                         Err(())
1029                     }
1030                 } else {
1031                     Err(())
1032                 }
1033             }
1034             Def::Trait(did) => {
1035                 let item = cx.tcx.associated_item_def_ids(did).iter()
1036                              .map(|item| cx.tcx.associated_item(*item))
1037                              .find(|item| item.name == item_name);
1038                 if let Some(item) = item {
1039                     let kind = match item.kind {
1040                         ty::AssociatedKind::Const if is_val => "associatedconstant",
1041                         ty::AssociatedKind::Type if !is_val => "associatedtype",
1042                         ty::AssociatedKind::Method if is_val => "tymethod",
1043                         _ => return Err(())
1044                     };
1045
1046                     Ok((ty.def, Some(format!("{}.{}", kind, item_name))))
1047                 } else {
1048                     Err(())
1049                 }
1050             }
1051             _ => Err(())
1052         }
1053
1054     } else {
1055         Err(())
1056     }
1057 }
1058
1059 /// Resolve a string as a macro
1060 fn macro_resolve(cx: &DocContext, path_str: &str) -> Option<Def> {
1061     use syntax::ext::base::{MacroKind, SyntaxExtension};
1062     use syntax::ext::hygiene::Mark;
1063     let segment = ast::PathSegment {
1064         identifier: ast::Ident::from_str(path_str),
1065         span: DUMMY_SP,
1066         parameters: None,
1067     };
1068     let path = ast::Path {
1069         span: DUMMY_SP,
1070         segments: vec![segment],
1071     };
1072
1073     let mut resolver = cx.resolver.borrow_mut();
1074     let mark = Mark::root();
1075     let res = resolver
1076         .resolve_macro_to_def_inner(mark, &path, MacroKind::Bang, false);
1077     if let Ok(def) = res {
1078         if let SyntaxExtension::DeclMacro(..) = *resolver.get_macro(def) {
1079             Some(def)
1080         } else {
1081             None
1082         }
1083     } else if let Some(def) = resolver.all_macros.get(&path_str.into()) {
1084         Some(*def)
1085     } else {
1086         None
1087     }
1088 }
1089
1090 #[derive(Debug)]
1091 enum PathKind {
1092     /// can be either value or type, not a macro
1093     Unknown,
1094     /// macro
1095     Macro,
1096     /// values, functions, consts, statics, everything in the value namespace
1097     Value,
1098     /// types, traits, everything in the type namespace
1099     Type,
1100 }
1101
1102 impl Clean<Attributes> for [ast::Attribute] {
1103     fn clean(&self, cx: &DocContext) -> Attributes {
1104         let mut attrs = Attributes::from_ast(cx.sess().diagnostic(), self);
1105
1106         if UnstableFeatures::from_environment().is_nightly_build() {
1107             let dox = attrs.collapsed_doc_value().unwrap_or_else(String::new);
1108             for ori_link in markdown_links(&dox) {
1109                 // bail early for real links
1110                 if ori_link.contains('/') {
1111                     continue;
1112                 }
1113                 let link = ori_link.replace("`", "");
1114                 let (def, fragment) = {
1115                     let mut kind = PathKind::Unknown;
1116                     let path_str = if let Some(prefix) =
1117                         ["struct@", "enum@", "type@",
1118                          "trait@", "union@"].iter()
1119                                           .find(|p| link.starts_with(**p)) {
1120                         kind = PathKind::Type;
1121                         link.trim_left_matches(prefix)
1122                     } else if let Some(prefix) =
1123                         ["const@", "static@",
1124                          "value@", "function@", "mod@",
1125                          "fn@", "module@", "method@"]
1126                             .iter().find(|p| link.starts_with(**p)) {
1127                         kind = PathKind::Value;
1128                         link.trim_left_matches(prefix)
1129                     } else if link.ends_with("()") {
1130                         kind = PathKind::Value;
1131                         link.trim_right_matches("()")
1132                     } else if link.starts_with("macro@") {
1133                         kind = PathKind::Macro;
1134                         link.trim_left_matches("macro@")
1135                     } else if link.ends_with('!') {
1136                         kind = PathKind::Macro;
1137                         link.trim_right_matches('!')
1138                     } else {
1139                         &link[..]
1140                     }.trim();
1141
1142                     // avoid resolving things (i.e. regular links) which aren't like paths
1143                     // FIXME(Manishearth) given that most links have slashes in them might be worth
1144                     // doing a check for slashes first
1145                     if path_str.contains(|ch: char| !(ch.is_alphanumeric() ||
1146                                                       ch == ':' || ch == '_')) {
1147                         continue;
1148                     }
1149
1150                     match kind {
1151                         PathKind::Value => {
1152                             if let Ok(def) = resolve(cx, path_str, true) {
1153                                 def
1154                             } else {
1155                                 // this could just be a normal link or a broken link
1156                                 // we could potentially check if something is
1157                                 // "intra-doc-link-like" and warn in that case
1158                                 continue;
1159                             }
1160                         }
1161                         PathKind::Type => {
1162                             if let Ok(def) = resolve(cx, path_str, false) {
1163                                 def
1164                             } else {
1165                                 // this could just be a normal link
1166                                 continue;
1167                             }
1168                         }
1169                         PathKind::Unknown => {
1170                             // try everything!
1171                             if let Some(macro_def) = macro_resolve(cx, path_str) {
1172                                 if let Ok(type_def) = resolve(cx, path_str, false) {
1173                                     let (type_kind, article, type_disambig)
1174                                         = type_ns_kind(type_def.0, path_str);
1175                                     ambiguity_error(cx, &attrs, path_str,
1176                                                     article, type_kind, &type_disambig,
1177                                                     "a", "macro", &format!("macro@{}", path_str));
1178                                     continue;
1179                                 } else if let Ok(value_def) = resolve(cx, path_str, true) {
1180                                     let (value_kind, value_disambig)
1181                                         = value_ns_kind(value_def.0, path_str)
1182                                             .expect("struct and mod cases should have been \
1183                                                      caught in previous branch");
1184                                     ambiguity_error(cx, &attrs, path_str,
1185                                                     "a", value_kind, &value_disambig,
1186                                                     "a", "macro", &format!("macro@{}", path_str));
1187                                 }
1188                                 (macro_def, None)
1189                             } else if let Ok(type_def) = resolve(cx, path_str, false) {
1190                                 // It is imperative we search for not-a-value first
1191                                 // Otherwise we will find struct ctors for when we are looking
1192                                 // for structs, and the link won't work.
1193                                 // if there is something in both namespaces
1194                                 if let Ok(value_def) = resolve(cx, path_str, true) {
1195                                     let kind = value_ns_kind(value_def.0, path_str);
1196                                     if let Some((value_kind, value_disambig)) = kind {
1197                                         let (type_kind, article, type_disambig)
1198                                             = type_ns_kind(type_def.0, path_str);
1199                                         ambiguity_error(cx, &attrs, path_str,
1200                                                         article, type_kind, &type_disambig,
1201                                                         "a", value_kind, &value_disambig);
1202                                         continue;
1203                                     }
1204                                 }
1205                                 type_def
1206                             } else if let Ok(value_def) = resolve(cx, path_str, true) {
1207                                 value_def
1208                             } else {
1209                                 // this could just be a normal link
1210                                 continue;
1211                             }
1212                         }
1213                         PathKind::Macro => {
1214                             if let Some(def) = macro_resolve(cx, path_str) {
1215                                 (def, None)
1216                             } else {
1217                                 continue
1218                             }
1219                         }
1220                     }
1221                 };
1222
1223                 let id = register_def(cx, def);
1224                 attrs.links.push((ori_link, id, fragment));
1225             }
1226
1227             cx.sess().abort_if_errors();
1228         }
1229
1230         attrs
1231     }
1232 }
1233
1234 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1235 pub struct TyParam {
1236     pub name: String,
1237     pub did: DefId,
1238     pub bounds: Vec<TyParamBound>,
1239     pub default: Option<Type>,
1240 }
1241
1242 impl Clean<TyParam> for hir::TyParam {
1243     fn clean(&self, cx: &DocContext) -> TyParam {
1244         TyParam {
1245             name: self.name.clean(cx),
1246             did: cx.tcx.hir.local_def_id(self.id),
1247             bounds: self.bounds.clean(cx),
1248             default: self.default.clean(cx),
1249         }
1250     }
1251 }
1252
1253 impl<'tcx> Clean<TyParam> for ty::TypeParameterDef {
1254     fn clean(&self, cx: &DocContext) -> TyParam {
1255         cx.renderinfo.borrow_mut().external_typarams.insert(self.def_id, self.name.clean(cx));
1256         TyParam {
1257             name: self.name.clean(cx),
1258             did: self.def_id,
1259             bounds: vec![], // these are filled in from the where-clauses
1260             default: if self.has_default {
1261                 Some(cx.tcx.type_of(self.def_id).clean(cx))
1262             } else {
1263                 None
1264             }
1265         }
1266     }
1267 }
1268
1269 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1270 pub enum TyParamBound {
1271     RegionBound(Lifetime),
1272     TraitBound(PolyTrait, hir::TraitBoundModifier)
1273 }
1274
1275 impl TyParamBound {
1276     fn maybe_sized(cx: &DocContext) -> TyParamBound {
1277         let did = cx.tcx.require_lang_item(lang_items::SizedTraitLangItem);
1278         let empty = cx.tcx.intern_substs(&[]);
1279         let path = external_path(cx, &cx.tcx.item_name(did),
1280             Some(did), false, vec![], empty);
1281         inline::record_extern_fqn(cx, did, TypeKind::Trait);
1282         TraitBound(PolyTrait {
1283             trait_: ResolvedPath {
1284                 path,
1285                 typarams: None,
1286                 did,
1287                 is_generic: false,
1288             },
1289             generic_params: Vec::new(),
1290         }, hir::TraitBoundModifier::Maybe)
1291     }
1292
1293     fn is_sized_bound(&self, cx: &DocContext) -> bool {
1294         use rustc::hir::TraitBoundModifier as TBM;
1295         if let TyParamBound::TraitBound(PolyTrait { ref trait_, .. }, TBM::None) = *self {
1296             if trait_.def_id() == cx.tcx.lang_items().sized_trait() {
1297                 return true;
1298             }
1299         }
1300         false
1301     }
1302
1303     fn get_poly_trait(&self) -> Option<PolyTrait> {
1304         if let TyParamBound::TraitBound(ref p, _) = *self {
1305             return Some(p.clone())
1306         }
1307         None
1308     }
1309
1310     fn get_trait_type(&self) -> Option<Type> {
1311
1312         if let TyParamBound::TraitBound(PolyTrait { ref trait_, .. }, _) = *self {
1313             return Some(trait_.clone());
1314         }
1315         None
1316     }
1317 }
1318
1319 impl Clean<TyParamBound> for hir::TyParamBound {
1320     fn clean(&self, cx: &DocContext) -> TyParamBound {
1321         match *self {
1322             hir::RegionTyParamBound(lt) => RegionBound(lt.clean(cx)),
1323             hir::TraitTyParamBound(ref t, modifier) => TraitBound(t.clean(cx), modifier),
1324         }
1325     }
1326 }
1327
1328 fn external_path_params(cx: &DocContext, trait_did: Option<DefId>, has_self: bool,
1329                         bindings: Vec<TypeBinding>, substs: &Substs) -> PathParameters {
1330     let lifetimes = substs.regions().filter_map(|v| v.clean(cx)).collect();
1331     let types = substs.types().skip(has_self as usize).collect::<Vec<_>>();
1332
1333     match trait_did {
1334         // Attempt to sugar an external path like Fn<(A, B,), C> to Fn(A, B) -> C
1335         Some(did) if cx.tcx.lang_items().fn_trait_kind(did).is_some() => {
1336             assert_eq!(types.len(), 1);
1337             let inputs = match types[0].sty {
1338                 ty::TyTuple(ref tys) => tys.iter().map(|t| t.clean(cx)).collect(),
1339                 _ => {
1340                     return PathParameters::AngleBracketed {
1341                         lifetimes,
1342                         types: types.clean(cx),
1343                         bindings,
1344                     }
1345                 }
1346             };
1347             let output = None;
1348             // FIXME(#20299) return type comes from a projection now
1349             // match types[1].sty {
1350             //     ty::TyTuple(ref v) if v.is_empty() => None, // -> ()
1351             //     _ => Some(types[1].clean(cx))
1352             // };
1353             PathParameters::Parenthesized {
1354                 inputs,
1355                 output,
1356             }
1357         },
1358         _ => {
1359             PathParameters::AngleBracketed {
1360                 lifetimes,
1361                 types: types.clean(cx),
1362                 bindings,
1363             }
1364         }
1365     }
1366 }
1367
1368 // trait_did should be set to a trait's DefId if called on a TraitRef, in order to sugar
1369 // from Fn<(A, B,), C> to Fn(A, B) -> C
1370 fn external_path(cx: &DocContext, name: &str, trait_did: Option<DefId>, has_self: bool,
1371                  bindings: Vec<TypeBinding>, substs: &Substs) -> Path {
1372     Path {
1373         global: false,
1374         def: Def::Err,
1375         segments: vec![PathSegment {
1376             name: name.to_string(),
1377             params: external_path_params(cx, trait_did, has_self, bindings, substs)
1378         }],
1379     }
1380 }
1381
1382 impl<'tcx> Clean<TyParamBound> for ty::TraitRef<'tcx> {
1383     fn clean(&self, cx: &DocContext) -> TyParamBound {
1384         inline::record_extern_fqn(cx, self.def_id, TypeKind::Trait);
1385         let path = external_path(cx, &cx.tcx.item_name(self.def_id),
1386                                  Some(self.def_id), true, vec![], self.substs);
1387
1388         debug!("ty::TraitRef\n  subst: {:?}\n", self.substs);
1389
1390         // collect any late bound regions
1391         let mut late_bounds = vec![];
1392         for ty_s in self.input_types().skip(1) {
1393             if let ty::TyTuple(ts) = ty_s.sty {
1394                 for &ty_s in ts {
1395                     if let ty::TyRef(ref reg, _) = ty_s.sty {
1396                         if let &ty::RegionKind::ReLateBound(..) = *reg {
1397                             debug!("  hit an ReLateBound {:?}", reg);
1398                             if let Some(lt) = reg.clean(cx) {
1399                                 late_bounds.push(GenericParam::Lifetime(lt));
1400                             }
1401                         }
1402                     }
1403                 }
1404             }
1405         }
1406
1407         TraitBound(
1408             PolyTrait {
1409                 trait_: ResolvedPath {
1410                     path,
1411                     typarams: None,
1412                     did: self.def_id,
1413                     is_generic: false,
1414                 },
1415                 generic_params: late_bounds,
1416             },
1417             hir::TraitBoundModifier::None
1418         )
1419     }
1420 }
1421
1422 impl<'tcx> Clean<Option<Vec<TyParamBound>>> for Substs<'tcx> {
1423     fn clean(&self, cx: &DocContext) -> Option<Vec<TyParamBound>> {
1424         let mut v = Vec::new();
1425         v.extend(self.regions().filter_map(|r| r.clean(cx))
1426                      .map(RegionBound));
1427         v.extend(self.types().map(|t| TraitBound(PolyTrait {
1428             trait_: t.clean(cx),
1429             generic_params: Vec::new(),
1430         }, hir::TraitBoundModifier::None)));
1431         if !v.is_empty() {Some(v)} else {None}
1432     }
1433 }
1434
1435 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1436 pub struct Lifetime(String);
1437
1438 impl Lifetime {
1439     pub fn get_ref<'a>(&'a self) -> &'a str {
1440         let Lifetime(ref s) = *self;
1441         let s: &'a str = s;
1442         s
1443     }
1444
1445     pub fn statik() -> Lifetime {
1446         Lifetime("'static".to_string())
1447     }
1448 }
1449
1450 impl Clean<Lifetime> for hir::Lifetime {
1451     fn clean(&self, cx: &DocContext) -> Lifetime {
1452         if self.id != ast::DUMMY_NODE_ID {
1453             let hir_id = cx.tcx.hir.node_to_hir_id(self.id);
1454             let def = cx.tcx.named_region(hir_id);
1455             match def {
1456                 Some(rl::Region::EarlyBound(_, node_id, _)) |
1457                 Some(rl::Region::LateBound(_, node_id, _)) |
1458                 Some(rl::Region::Free(_, node_id)) => {
1459                     if let Some(lt) = cx.lt_substs.borrow().get(&node_id).cloned() {
1460                         return lt;
1461                     }
1462                 }
1463                 _ => {}
1464             }
1465         }
1466         Lifetime(self.name.name().to_string())
1467     }
1468 }
1469
1470 impl Clean<Lifetime> for hir::LifetimeDef {
1471     fn clean(&self, _: &DocContext) -> Lifetime {
1472         if self.bounds.len() > 0 {
1473             let mut s = format!("{}: {}",
1474                                 self.lifetime.name.name(),
1475                                 self.bounds[0].name.name());
1476             for bound in self.bounds.iter().skip(1) {
1477                 s.push_str(&format!(" + {}", bound.name.name()));
1478             }
1479             Lifetime(s)
1480         } else {
1481             Lifetime(self.lifetime.name.name().to_string())
1482         }
1483     }
1484 }
1485
1486 impl Clean<Lifetime> for ty::RegionParameterDef {
1487     fn clean(&self, _: &DocContext) -> Lifetime {
1488         Lifetime(self.name.to_string())
1489     }
1490 }
1491
1492 impl Clean<Option<Lifetime>> for ty::RegionKind {
1493     fn clean(&self, cx: &DocContext) -> Option<Lifetime> {
1494         match *self {
1495             ty::ReStatic => Some(Lifetime::statik()),
1496             ty::ReLateBound(_, ty::BrNamed(_, name)) => Some(Lifetime(name.to_string())),
1497             ty::ReEarlyBound(ref data) => Some(Lifetime(data.name.clean(cx))),
1498
1499             ty::ReLateBound(..) |
1500             ty::ReFree(..) |
1501             ty::ReScope(..) |
1502             ty::ReVar(..) |
1503             ty::ReSkolemized(..) |
1504             ty::ReEmpty |
1505             ty::ReClosureBound(_) |
1506             ty::ReCanonical(_) |
1507             ty::ReErased => None
1508         }
1509     }
1510 }
1511
1512 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1513 pub enum WherePredicate {
1514     BoundPredicate { ty: Type, bounds: Vec<TyParamBound> },
1515     RegionPredicate { lifetime: Lifetime, bounds: Vec<Lifetime>},
1516     EqPredicate { lhs: Type, rhs: Type },
1517 }
1518
1519 impl Clean<WherePredicate> for hir::WherePredicate {
1520     fn clean(&self, cx: &DocContext) -> WherePredicate {
1521         match *self {
1522             hir::WherePredicate::BoundPredicate(ref wbp) => {
1523                 WherePredicate::BoundPredicate {
1524                     ty: wbp.bounded_ty.clean(cx),
1525                     bounds: wbp.bounds.clean(cx)
1526                 }
1527             }
1528
1529             hir::WherePredicate::RegionPredicate(ref wrp) => {
1530                 WherePredicate::RegionPredicate {
1531                     lifetime: wrp.lifetime.clean(cx),
1532                     bounds: wrp.bounds.clean(cx)
1533                 }
1534             }
1535
1536             hir::WherePredicate::EqPredicate(ref wrp) => {
1537                 WherePredicate::EqPredicate {
1538                     lhs: wrp.lhs_ty.clean(cx),
1539                     rhs: wrp.rhs_ty.clean(cx)
1540                 }
1541             }
1542         }
1543     }
1544 }
1545
1546 impl<'a> Clean<WherePredicate> for ty::Predicate<'a> {
1547     fn clean(&self, cx: &DocContext) -> WherePredicate {
1548         use rustc::ty::Predicate;
1549
1550         match *self {
1551             Predicate::Trait(ref pred) => pred.clean(cx),
1552             Predicate::Subtype(ref pred) => pred.clean(cx),
1553             Predicate::RegionOutlives(ref pred) => pred.clean(cx),
1554             Predicate::TypeOutlives(ref pred) => pred.clean(cx),
1555             Predicate::Projection(ref pred) => pred.clean(cx),
1556             Predicate::WellFormed(_) => panic!("not user writable"),
1557             Predicate::ObjectSafe(_) => panic!("not user writable"),
1558             Predicate::ClosureKind(..) => panic!("not user writable"),
1559             Predicate::ConstEvaluatable(..) => panic!("not user writable"),
1560         }
1561     }
1562 }
1563
1564 impl<'a> Clean<WherePredicate> for ty::TraitPredicate<'a> {
1565     fn clean(&self, cx: &DocContext) -> WherePredicate {
1566         WherePredicate::BoundPredicate {
1567             ty: self.trait_ref.self_ty().clean(cx),
1568             bounds: vec![self.trait_ref.clean(cx)]
1569         }
1570     }
1571 }
1572
1573 impl<'tcx> Clean<WherePredicate> for ty::SubtypePredicate<'tcx> {
1574     fn clean(&self, _cx: &DocContext) -> WherePredicate {
1575         panic!("subtype predicates are an internal rustc artifact \
1576                 and should not be seen by rustdoc")
1577     }
1578 }
1579
1580 impl<'tcx> Clean<WherePredicate> for ty::OutlivesPredicate<ty::Region<'tcx>, ty::Region<'tcx>> {
1581     fn clean(&self, cx: &DocContext) -> WherePredicate {
1582         let ty::OutlivesPredicate(ref a, ref b) = *self;
1583         WherePredicate::RegionPredicate {
1584             lifetime: a.clean(cx).unwrap(),
1585             bounds: vec![b.clean(cx).unwrap()]
1586         }
1587     }
1588 }
1589
1590 impl<'tcx> Clean<WherePredicate> for ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>> {
1591     fn clean(&self, cx: &DocContext) -> WherePredicate {
1592         let ty::OutlivesPredicate(ref ty, ref lt) = *self;
1593
1594         WherePredicate::BoundPredicate {
1595             ty: ty.clean(cx),
1596             bounds: vec![TyParamBound::RegionBound(lt.clean(cx).unwrap())]
1597         }
1598     }
1599 }
1600
1601 impl<'tcx> Clean<WherePredicate> for ty::ProjectionPredicate<'tcx> {
1602     fn clean(&self, cx: &DocContext) -> WherePredicate {
1603         WherePredicate::EqPredicate {
1604             lhs: self.projection_ty.clean(cx),
1605             rhs: self.ty.clean(cx)
1606         }
1607     }
1608 }
1609
1610 impl<'tcx> Clean<Type> for ty::ProjectionTy<'tcx> {
1611     fn clean(&self, cx: &DocContext) -> Type {
1612         let trait_ = match self.trait_ref(cx.tcx).clean(cx) {
1613             TyParamBound::TraitBound(t, _) => t.trait_,
1614             TyParamBound::RegionBound(_) => {
1615                 panic!("cleaning a trait got a region")
1616             }
1617         };
1618         Type::QPath {
1619             name: cx.tcx.associated_item(self.item_def_id).name.clean(cx),
1620             self_type: box self.self_ty().clean(cx),
1621             trait_: box trait_
1622         }
1623     }
1624 }
1625
1626 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1627 pub enum GenericParam {
1628     Lifetime(Lifetime),
1629     Type(TyParam),
1630 }
1631
1632 impl Clean<GenericParam> for hir::GenericParam {
1633     fn clean(&self, cx: &DocContext) -> GenericParam {
1634         match *self {
1635             hir::GenericParam::Lifetime(ref l) => GenericParam::Lifetime(l.clean(cx)),
1636             hir::GenericParam::Type(ref t) => GenericParam::Type(t.clean(cx)),
1637         }
1638     }
1639 }
1640
1641 // maybe use a Generic enum and use Vec<Generic>?
1642 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Default, Hash)]
1643 pub struct Generics {
1644     pub params: Vec<GenericParam>,
1645     pub where_predicates: Vec<WherePredicate>,
1646 }
1647
1648 impl Clean<Generics> for hir::Generics {
1649     fn clean(&self, cx: &DocContext) -> Generics {
1650         let mut g = Generics {
1651             params: self.params.clean(cx),
1652             where_predicates: self.where_clause.predicates.clean(cx)
1653         };
1654
1655         // Some duplicates are generated for ?Sized bounds between type params and where
1656         // predicates. The point in here is to move the bounds definitions from type params
1657         // to where predicates when such cases occur.
1658         for where_pred in &mut g.where_predicates {
1659             match *where_pred {
1660                 WherePredicate::BoundPredicate { ty: Generic(ref name), ref mut bounds } => {
1661                     if bounds.is_empty() {
1662                         for param in &mut g.params {
1663                             if let GenericParam::Type(ref mut type_param) = *param {
1664                                 if &type_param.name == name {
1665                                     mem::swap(bounds, &mut type_param.bounds);
1666                                     break
1667                                 }
1668                             }
1669                         }
1670                     }
1671                 }
1672                 _ => continue,
1673             }
1674         }
1675         g
1676     }
1677 }
1678
1679 impl<'a, 'tcx> Clean<Generics> for (&'a ty::Generics,
1680                                     &'a ty::GenericPredicates<'tcx>) {
1681     fn clean(&self, cx: &DocContext) -> Generics {
1682         use self::WherePredicate as WP;
1683
1684         let (gens, preds) = *self;
1685
1686         // Bounds in the type_params and lifetimes fields are repeated in the
1687         // predicates field (see rustc_typeck::collect::ty_generics), so remove
1688         // them.
1689         let stripped_typarams = gens.types.iter().filter_map(|tp| {
1690             if tp.name == keywords::SelfType.name() {
1691                 assert_eq!(tp.index, 0);
1692                 None
1693             } else {
1694                 Some(tp.clean(cx))
1695             }
1696         }).collect::<Vec<_>>();
1697
1698         let mut where_predicates = preds.predicates.to_vec().clean(cx);
1699
1700         // Type parameters and have a Sized bound by default unless removed with
1701         // ?Sized. Scan through the predicates and mark any type parameter with
1702         // a Sized bound, removing the bounds as we find them.
1703         //
1704         // Note that associated types also have a sized bound by default, but we
1705         // don't actually know the set of associated types right here so that's
1706         // handled in cleaning associated types
1707         let mut sized_params = FxHashSet();
1708         where_predicates.retain(|pred| {
1709             match *pred {
1710                 WP::BoundPredicate { ty: Generic(ref g), ref bounds } => {
1711                     if bounds.iter().any(|b| b.is_sized_bound(cx)) {
1712                         sized_params.insert(g.clone());
1713                         false
1714                     } else {
1715                         true
1716                     }
1717                 }
1718                 _ => true,
1719             }
1720         });
1721
1722         // Run through the type parameters again and insert a ?Sized
1723         // unbound for any we didn't find to be Sized.
1724         for tp in &stripped_typarams {
1725             if !sized_params.contains(&tp.name) {
1726                 where_predicates.push(WP::BoundPredicate {
1727                     ty: Type::Generic(tp.name.clone()),
1728                     bounds: vec![TyParamBound::maybe_sized(cx)],
1729                 })
1730             }
1731         }
1732
1733         // It would be nice to collect all of the bounds on a type and recombine
1734         // them if possible, to avoid e.g. `where T: Foo, T: Bar, T: Sized, T: 'a`
1735         // and instead see `where T: Foo + Bar + Sized + 'a`
1736
1737         Generics {
1738             params: gens.regions
1739                 .clean(cx)
1740                 .into_iter()
1741                 .map(|lp| GenericParam::Lifetime(lp))
1742                 .chain(
1743                     simplify::ty_params(stripped_typarams)
1744                         .into_iter()
1745                         .map(|tp| GenericParam::Type(tp))
1746                 )
1747                 .collect(),
1748             where_predicates: simplify::where_clauses(cx, where_predicates),
1749         }
1750     }
1751 }
1752
1753 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1754 pub struct Method {
1755     pub generics: Generics,
1756     pub unsafety: hir::Unsafety,
1757     pub constness: hir::Constness,
1758     pub decl: FnDecl,
1759     pub abi: Abi,
1760 }
1761
1762 impl<'a> Clean<Method> for (&'a hir::MethodSig, &'a hir::Generics, hir::BodyId) {
1763     fn clean(&self, cx: &DocContext) -> Method {
1764         Method {
1765             generics: self.1.clean(cx),
1766             unsafety: self.0.unsafety,
1767             constness: self.0.constness,
1768             decl: (&*self.0.decl, self.2).clean(cx),
1769             abi: self.0.abi
1770         }
1771     }
1772 }
1773
1774 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1775 pub struct TyMethod {
1776     pub unsafety: hir::Unsafety,
1777     pub decl: FnDecl,
1778     pub generics: Generics,
1779     pub abi: Abi,
1780 }
1781
1782 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1783 pub struct Function {
1784     pub decl: FnDecl,
1785     pub generics: Generics,
1786     pub unsafety: hir::Unsafety,
1787     pub constness: hir::Constness,
1788     pub abi: Abi,
1789 }
1790
1791 impl Clean<Item> for doctree::Function {
1792     fn clean(&self, cx: &DocContext) -> Item {
1793         Item {
1794             name: Some(self.name.clean(cx)),
1795             attrs: self.attrs.clean(cx),
1796             source: self.whence.clean(cx),
1797             visibility: self.vis.clean(cx),
1798             stability: self.stab.clean(cx),
1799             deprecation: self.depr.clean(cx),
1800             def_id: cx.tcx.hir.local_def_id(self.id),
1801             inner: FunctionItem(Function {
1802                 decl: (&self.decl, self.body).clean(cx),
1803                 generics: self.generics.clean(cx),
1804                 unsafety: self.unsafety,
1805                 constness: self.constness,
1806                 abi: self.abi,
1807             }),
1808         }
1809     }
1810 }
1811
1812 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1813 pub struct FnDecl {
1814     pub inputs: Arguments,
1815     pub output: FunctionRetTy,
1816     pub variadic: bool,
1817     pub attrs: Attributes,
1818 }
1819
1820 impl FnDecl {
1821     pub fn has_self(&self) -> bool {
1822         self.inputs.values.len() > 0 && self.inputs.values[0].name == "self"
1823     }
1824
1825     pub fn self_type(&self) -> Option<SelfTy> {
1826         self.inputs.values.get(0).and_then(|v| v.to_self())
1827     }
1828 }
1829
1830 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1831 pub struct Arguments {
1832     pub values: Vec<Argument>,
1833 }
1834
1835 impl<'a> Clean<Arguments> for (&'a [P<hir::Ty>], &'a [Spanned<ast::Name>]) {
1836     fn clean(&self, cx: &DocContext) -> Arguments {
1837         Arguments {
1838             values: self.0.iter().enumerate().map(|(i, ty)| {
1839                 let mut name = self.1.get(i).map(|n| n.node.to_string())
1840                                             .unwrap_or(String::new());
1841                 if name.is_empty() {
1842                     name = "_".to_string();
1843                 }
1844                 Argument {
1845                     name,
1846                     type_: ty.clean(cx),
1847                 }
1848             }).collect()
1849         }
1850     }
1851 }
1852
1853 impl<'a> Clean<Arguments> for (&'a [P<hir::Ty>], hir::BodyId) {
1854     fn clean(&self, cx: &DocContext) -> Arguments {
1855         let body = cx.tcx.hir.body(self.1);
1856
1857         Arguments {
1858             values: self.0.iter().enumerate().map(|(i, ty)| {
1859                 Argument {
1860                     name: name_from_pat(&body.arguments[i].pat),
1861                     type_: ty.clean(cx),
1862                 }
1863             }).collect()
1864         }
1865     }
1866 }
1867
1868 impl<'a, A: Copy> Clean<FnDecl> for (&'a hir::FnDecl, A)
1869     where (&'a [P<hir::Ty>], A): Clean<Arguments>
1870 {
1871     fn clean(&self, cx: &DocContext) -> FnDecl {
1872         FnDecl {
1873             inputs: (&self.0.inputs[..], self.1).clean(cx),
1874             output: self.0.output.clean(cx),
1875             variadic: self.0.variadic,
1876             attrs: Attributes::default()
1877         }
1878     }
1879 }
1880
1881 impl<'a, 'tcx> Clean<FnDecl> for (DefId, ty::PolyFnSig<'tcx>) {
1882     fn clean(&self, cx: &DocContext) -> FnDecl {
1883         let (did, sig) = *self;
1884         let mut names = if cx.tcx.hir.as_local_node_id(did).is_some() {
1885             vec![].into_iter()
1886         } else {
1887             cx.tcx.fn_arg_names(did).into_iter()
1888         }.peekable();
1889         FnDecl {
1890             output: Return(sig.skip_binder().output().clean(cx)),
1891             attrs: Attributes::default(),
1892             variadic: sig.skip_binder().variadic,
1893             inputs: Arguments {
1894                 values: sig.skip_binder().inputs().iter().map(|t| {
1895                     Argument {
1896                         type_: t.clean(cx),
1897                         name: names.next().map_or("".to_string(), |name| name.to_string()),
1898                     }
1899                 }).collect(),
1900             },
1901         }
1902     }
1903 }
1904
1905 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1906 pub struct Argument {
1907     pub type_: Type,
1908     pub name: String,
1909 }
1910
1911 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1912 pub enum SelfTy {
1913     SelfValue,
1914     SelfBorrowed(Option<Lifetime>, Mutability),
1915     SelfExplicit(Type),
1916 }
1917
1918 impl Argument {
1919     pub fn to_self(&self) -> Option<SelfTy> {
1920         if self.name != "self" {
1921             return None;
1922         }
1923         if self.type_.is_self_type() {
1924             return Some(SelfValue);
1925         }
1926         match self.type_ {
1927             BorrowedRef{ref lifetime, mutability, ref type_} if type_.is_self_type() => {
1928                 Some(SelfBorrowed(lifetime.clone(), mutability))
1929             }
1930             _ => Some(SelfExplicit(self.type_.clone()))
1931         }
1932     }
1933 }
1934
1935 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1936 pub enum FunctionRetTy {
1937     Return(Type),
1938     DefaultReturn,
1939 }
1940
1941 impl Clean<FunctionRetTy> for hir::FunctionRetTy {
1942     fn clean(&self, cx: &DocContext) -> FunctionRetTy {
1943         match *self {
1944             hir::Return(ref typ) => Return(typ.clean(cx)),
1945             hir::DefaultReturn(..) => DefaultReturn,
1946         }
1947     }
1948 }
1949
1950 impl GetDefId for FunctionRetTy {
1951     fn def_id(&self) -> Option<DefId> {
1952         match *self {
1953             Return(ref ty) => ty.def_id(),
1954             DefaultReturn => None,
1955         }
1956     }
1957 }
1958
1959 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1960 pub struct Trait {
1961     pub auto: bool,
1962     pub unsafety: hir::Unsafety,
1963     pub items: Vec<Item>,
1964     pub generics: Generics,
1965     pub bounds: Vec<TyParamBound>,
1966     pub is_spotlight: bool,
1967     pub is_auto: bool,
1968 }
1969
1970 impl Clean<Item> for doctree::Trait {
1971     fn clean(&self, cx: &DocContext) -> Item {
1972         let attrs = self.attrs.clean(cx);
1973         let is_spotlight = attrs.has_doc_flag("spotlight");
1974         Item {
1975             name: Some(self.name.clean(cx)),
1976             attrs: attrs,
1977             source: self.whence.clean(cx),
1978             def_id: cx.tcx.hir.local_def_id(self.id),
1979             visibility: self.vis.clean(cx),
1980             stability: self.stab.clean(cx),
1981             deprecation: self.depr.clean(cx),
1982             inner: TraitItem(Trait {
1983                 auto: self.is_auto.clean(cx),
1984                 unsafety: self.unsafety,
1985                 items: self.items.clean(cx),
1986                 generics: self.generics.clean(cx),
1987                 bounds: self.bounds.clean(cx),
1988                 is_spotlight: is_spotlight,
1989                 is_auto: self.is_auto.clean(cx),
1990             }),
1991         }
1992     }
1993 }
1994
1995 impl Clean<bool> for hir::IsAuto {
1996     fn clean(&self, _: &DocContext) -> bool {
1997         match *self {
1998             hir::IsAuto::Yes => true,
1999             hir::IsAuto::No => false,
2000         }
2001     }
2002 }
2003
2004 impl Clean<Type> for hir::TraitRef {
2005     fn clean(&self, cx: &DocContext) -> Type {
2006         resolve_type(cx, self.path.clean(cx), self.ref_id)
2007     }
2008 }
2009
2010 impl Clean<PolyTrait> for hir::PolyTraitRef {
2011     fn clean(&self, cx: &DocContext) -> PolyTrait {
2012         PolyTrait {
2013             trait_: self.trait_ref.clean(cx),
2014             generic_params: self.bound_generic_params.clean(cx)
2015         }
2016     }
2017 }
2018
2019 impl Clean<Item> for hir::TraitItem {
2020     fn clean(&self, cx: &DocContext) -> Item {
2021         let inner = match self.node {
2022             hir::TraitItemKind::Const(ref ty, default) => {
2023                 AssociatedConstItem(ty.clean(cx),
2024                                     default.map(|e| print_const_expr(cx, e)))
2025             }
2026             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Provided(body)) => {
2027                 MethodItem((sig, &self.generics, body).clean(cx))
2028             }
2029             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Required(ref names)) => {
2030                 TyMethodItem(TyMethod {
2031                     unsafety: sig.unsafety.clone(),
2032                     decl: (&*sig.decl, &names[..]).clean(cx),
2033                     generics: self.generics.clean(cx),
2034                     abi: sig.abi
2035                 })
2036             }
2037             hir::TraitItemKind::Type(ref bounds, ref default) => {
2038                 AssociatedTypeItem(bounds.clean(cx), default.clean(cx))
2039             }
2040         };
2041         Item {
2042             name: Some(self.name.clean(cx)),
2043             attrs: self.attrs.clean(cx),
2044             source: self.span.clean(cx),
2045             def_id: cx.tcx.hir.local_def_id(self.id),
2046             visibility: None,
2047             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2048             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2049             inner,
2050         }
2051     }
2052 }
2053
2054 impl Clean<Item> for hir::ImplItem {
2055     fn clean(&self, cx: &DocContext) -> Item {
2056         let inner = match self.node {
2057             hir::ImplItemKind::Const(ref ty, expr) => {
2058                 AssociatedConstItem(ty.clean(cx),
2059                                     Some(print_const_expr(cx, expr)))
2060             }
2061             hir::ImplItemKind::Method(ref sig, body) => {
2062                 MethodItem((sig, &self.generics, body).clean(cx))
2063             }
2064             hir::ImplItemKind::Type(ref ty) => TypedefItem(Typedef {
2065                 type_: ty.clean(cx),
2066                 generics: Generics::default(),
2067             }, true),
2068         };
2069         Item {
2070             name: Some(self.name.clean(cx)),
2071             source: self.span.clean(cx),
2072             attrs: self.attrs.clean(cx),
2073             def_id: cx.tcx.hir.local_def_id(self.id),
2074             visibility: self.vis.clean(cx),
2075             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2076             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2077             inner,
2078         }
2079     }
2080 }
2081
2082 impl<'tcx> Clean<Item> for ty::AssociatedItem {
2083     fn clean(&self, cx: &DocContext) -> Item {
2084         let inner = match self.kind {
2085             ty::AssociatedKind::Const => {
2086                 let ty = cx.tcx.type_of(self.def_id);
2087                 let default = if self.defaultness.has_value() {
2088                     Some(inline::print_inlined_const(cx, self.def_id))
2089                 } else {
2090                     None
2091                 };
2092                 AssociatedConstItem(ty.clean(cx), default)
2093             }
2094             ty::AssociatedKind::Method => {
2095                 let generics = (cx.tcx.generics_of(self.def_id),
2096                                 &cx.tcx.predicates_of(self.def_id)).clean(cx);
2097                 let sig = cx.tcx.fn_sig(self.def_id);
2098                 let mut decl = (self.def_id, sig).clean(cx);
2099
2100                 if self.method_has_self_argument {
2101                     let self_ty = match self.container {
2102                         ty::ImplContainer(def_id) => {
2103                             cx.tcx.type_of(def_id)
2104                         }
2105                         ty::TraitContainer(_) => cx.tcx.mk_self_type()
2106                     };
2107                     let self_arg_ty = *sig.input(0).skip_binder();
2108                     if self_arg_ty == self_ty {
2109                         decl.inputs.values[0].type_ = Generic(String::from("Self"));
2110                     } else if let ty::TyRef(_, mt) = self_arg_ty.sty {
2111                         if mt.ty == self_ty {
2112                             match decl.inputs.values[0].type_ {
2113                                 BorrowedRef{ref mut type_, ..} => {
2114                                     **type_ = Generic(String::from("Self"))
2115                                 }
2116                                 _ => unreachable!(),
2117                             }
2118                         }
2119                     }
2120                 }
2121
2122                 let provided = match self.container {
2123                     ty::ImplContainer(_) => true,
2124                     ty::TraitContainer(_) => self.defaultness.has_value()
2125                 };
2126                 if provided {
2127                     let constness = if cx.tcx.is_const_fn(self.def_id) {
2128                         hir::Constness::Const
2129                     } else {
2130                         hir::Constness::NotConst
2131                     };
2132                     MethodItem(Method {
2133                         unsafety: sig.unsafety(),
2134                         generics,
2135                         decl,
2136                         abi: sig.abi(),
2137                         constness,
2138                     })
2139                 } else {
2140                     TyMethodItem(TyMethod {
2141                         unsafety: sig.unsafety(),
2142                         generics,
2143                         decl,
2144                         abi: sig.abi(),
2145                     })
2146                 }
2147             }
2148             ty::AssociatedKind::Type => {
2149                 let my_name = self.name.clean(cx);
2150
2151                 if let ty::TraitContainer(did) = self.container {
2152                     // When loading a cross-crate associated type, the bounds for this type
2153                     // are actually located on the trait/impl itself, so we need to load
2154                     // all of the generics from there and then look for bounds that are
2155                     // applied to this associated type in question.
2156                     let predicates = cx.tcx.predicates_of(did);
2157                     let generics = (cx.tcx.generics_of(did), &predicates).clean(cx);
2158                     let mut bounds = generics.where_predicates.iter().filter_map(|pred| {
2159                         let (name, self_type, trait_, bounds) = match *pred {
2160                             WherePredicate::BoundPredicate {
2161                                 ty: QPath { ref name, ref self_type, ref trait_ },
2162                                 ref bounds
2163                             } => (name, self_type, trait_, bounds),
2164                             _ => return None,
2165                         };
2166                         if *name != my_name { return None }
2167                         match **trait_ {
2168                             ResolvedPath { did, .. } if did == self.container.id() => {}
2169                             _ => return None,
2170                         }
2171                         match **self_type {
2172                             Generic(ref s) if *s == "Self" => {}
2173                             _ => return None,
2174                         }
2175                         Some(bounds)
2176                     }).flat_map(|i| i.iter().cloned()).collect::<Vec<_>>();
2177                     // Our Sized/?Sized bound didn't get handled when creating the generics
2178                     // because we didn't actually get our whole set of bounds until just now
2179                     // (some of them may have come from the trait). If we do have a sized
2180                     // bound, we remove it, and if we don't then we add the `?Sized` bound
2181                     // at the end.
2182                     match bounds.iter().position(|b| b.is_sized_bound(cx)) {
2183                         Some(i) => { bounds.remove(i); }
2184                         None => bounds.push(TyParamBound::maybe_sized(cx)),
2185                     }
2186
2187                     let ty = if self.defaultness.has_value() {
2188                         Some(cx.tcx.type_of(self.def_id))
2189                     } else {
2190                         None
2191                     };
2192
2193                     AssociatedTypeItem(bounds, ty.clean(cx))
2194                 } else {
2195                     TypedefItem(Typedef {
2196                         type_: cx.tcx.type_of(self.def_id).clean(cx),
2197                         generics: Generics {
2198                             params: Vec::new(),
2199                             where_predicates: Vec::new(),
2200                         },
2201                     }, true)
2202                 }
2203             }
2204         };
2205
2206         let visibility = match self.container {
2207             ty::ImplContainer(_) => self.vis.clean(cx),
2208             ty::TraitContainer(_) => None,
2209         };
2210
2211         Item {
2212             name: Some(self.name.clean(cx)),
2213             visibility,
2214             stability: get_stability(cx, self.def_id),
2215             deprecation: get_deprecation(cx, self.def_id),
2216             def_id: self.def_id,
2217             attrs: inline::load_attrs(cx, self.def_id),
2218             source: cx.tcx.def_span(self.def_id).clean(cx),
2219             inner,
2220         }
2221     }
2222 }
2223
2224 /// A trait reference, which may have higher ranked lifetimes.
2225 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2226 pub struct PolyTrait {
2227     pub trait_: Type,
2228     pub generic_params: Vec<GenericParam>,
2229 }
2230
2231 /// A representation of a Type suitable for hyperlinking purposes. Ideally one can get the original
2232 /// type out of the AST/TyCtxt given one of these, if more information is needed. Most importantly
2233 /// it does not preserve mutability or boxes.
2234 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2235 pub enum Type {
2236     /// structs/enums/traits (most that'd be an hir::TyPath)
2237     ResolvedPath {
2238         path: Path,
2239         typarams: Option<Vec<TyParamBound>>,
2240         did: DefId,
2241         /// true if is a `T::Name` path for associated types
2242         is_generic: bool,
2243     },
2244     /// For parameterized types, so the consumer of the JSON don't go
2245     /// looking for types which don't exist anywhere.
2246     Generic(String),
2247     /// Primitives are the fixed-size numeric types (plus int/usize/float), char,
2248     /// arrays, slices, and tuples.
2249     Primitive(PrimitiveType),
2250     /// extern "ABI" fn
2251     BareFunction(Box<BareFunctionDecl>),
2252     Tuple(Vec<Type>),
2253     Slice(Box<Type>),
2254     Array(Box<Type>, String),
2255     Never,
2256     Unique(Box<Type>),
2257     RawPointer(Mutability, Box<Type>),
2258     BorrowedRef {
2259         lifetime: Option<Lifetime>,
2260         mutability: Mutability,
2261         type_: Box<Type>,
2262     },
2263
2264     // <Type as Trait>::Name
2265     QPath {
2266         name: String,
2267         self_type: Box<Type>,
2268         trait_: Box<Type>
2269     },
2270
2271     // _
2272     Infer,
2273
2274     // impl TraitA+TraitB
2275     ImplTrait(Vec<TyParamBound>),
2276 }
2277
2278 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Copy, Debug)]
2279 pub enum PrimitiveType {
2280     Isize, I8, I16, I32, I64, I128,
2281     Usize, U8, U16, U32, U64, U128,
2282     F32, F64,
2283     Char,
2284     Bool,
2285     Str,
2286     Slice,
2287     Array,
2288     Tuple,
2289     Unit,
2290     RawPointer,
2291     Reference,
2292     Fn,
2293     Never,
2294 }
2295
2296 #[derive(Clone, RustcEncodable, RustcDecodable, Copy, Debug)]
2297 pub enum TypeKind {
2298     Enum,
2299     Function,
2300     Module,
2301     Const,
2302     Static,
2303     Struct,
2304     Union,
2305     Trait,
2306     Variant,
2307     Typedef,
2308     Foreign,
2309     Macro,
2310 }
2311
2312 pub trait GetDefId {
2313     fn def_id(&self) -> Option<DefId>;
2314 }
2315
2316 impl<T: GetDefId> GetDefId for Option<T> {
2317     fn def_id(&self) -> Option<DefId> {
2318         self.as_ref().and_then(|d| d.def_id())
2319     }
2320 }
2321
2322 impl Type {
2323     pub fn primitive_type(&self) -> Option<PrimitiveType> {
2324         match *self {
2325             Primitive(p) | BorrowedRef { type_: box Primitive(p), ..} => Some(p),
2326             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
2327             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
2328             Tuple(ref tys) => if tys.is_empty() {
2329                 Some(PrimitiveType::Unit)
2330             } else {
2331                 Some(PrimitiveType::Tuple)
2332             },
2333             RawPointer(..) => Some(PrimitiveType::RawPointer),
2334             BorrowedRef { type_: box Generic(..), .. } => Some(PrimitiveType::Reference),
2335             BareFunction(..) => Some(PrimitiveType::Fn),
2336             Never => Some(PrimitiveType::Never),
2337             _ => None,
2338         }
2339     }
2340
2341     pub fn is_generic(&self) -> bool {
2342         match *self {
2343             ResolvedPath { is_generic, .. } => is_generic,
2344             _ => false,
2345         }
2346     }
2347
2348     pub fn is_self_type(&self) -> bool {
2349         match *self {
2350             Generic(ref name) => name == "Self",
2351             _ => false
2352         }
2353     }
2354
2355     pub fn generics(&self) -> Option<&[Type]> {
2356         match *self {
2357             ResolvedPath { ref path, .. } => {
2358                 path.segments.last().and_then(|seg| {
2359                     if let PathParameters::AngleBracketed { ref types, .. } = seg.params {
2360                         Some(&**types)
2361                     } else {
2362                         None
2363                     }
2364                 })
2365             }
2366             _ => None,
2367         }
2368     }
2369 }
2370
2371 impl GetDefId for Type {
2372     fn def_id(&self) -> Option<DefId> {
2373         match *self {
2374             ResolvedPath { did, .. } => Some(did),
2375             Primitive(p) => ::html::render::cache().primitive_locations.get(&p).cloned(),
2376             BorrowedRef { type_: box Generic(..), .. } =>
2377                 Primitive(PrimitiveType::Reference).def_id(),
2378             BorrowedRef { ref type_, .. } => type_.def_id(),
2379             Tuple(ref tys) => if tys.is_empty() {
2380                 Primitive(PrimitiveType::Unit).def_id()
2381             } else {
2382                 Primitive(PrimitiveType::Tuple).def_id()
2383             },
2384             BareFunction(..) => Primitive(PrimitiveType::Fn).def_id(),
2385             Never => Primitive(PrimitiveType::Never).def_id(),
2386             Slice(..) => Primitive(PrimitiveType::Slice).def_id(),
2387             Array(..) => Primitive(PrimitiveType::Array).def_id(),
2388             RawPointer(..) => Primitive(PrimitiveType::RawPointer).def_id(),
2389             QPath { ref self_type, .. } => self_type.def_id(),
2390             _ => None,
2391         }
2392     }
2393 }
2394
2395 impl PrimitiveType {
2396     fn from_str(s: &str) -> Option<PrimitiveType> {
2397         match s {
2398             "isize" => Some(PrimitiveType::Isize),
2399             "i8" => Some(PrimitiveType::I8),
2400             "i16" => Some(PrimitiveType::I16),
2401             "i32" => Some(PrimitiveType::I32),
2402             "i64" => Some(PrimitiveType::I64),
2403             "i128" => Some(PrimitiveType::I128),
2404             "usize" => Some(PrimitiveType::Usize),
2405             "u8" => Some(PrimitiveType::U8),
2406             "u16" => Some(PrimitiveType::U16),
2407             "u32" => Some(PrimitiveType::U32),
2408             "u64" => Some(PrimitiveType::U64),
2409             "u128" => Some(PrimitiveType::U128),
2410             "bool" => Some(PrimitiveType::Bool),
2411             "char" => Some(PrimitiveType::Char),
2412             "str" => Some(PrimitiveType::Str),
2413             "f32" => Some(PrimitiveType::F32),
2414             "f64" => Some(PrimitiveType::F64),
2415             "array" => Some(PrimitiveType::Array),
2416             "slice" => Some(PrimitiveType::Slice),
2417             "tuple" => Some(PrimitiveType::Tuple),
2418             "unit" => Some(PrimitiveType::Unit),
2419             "pointer" => Some(PrimitiveType::RawPointer),
2420             "reference" => Some(PrimitiveType::Reference),
2421             "fn" => Some(PrimitiveType::Fn),
2422             "never" => Some(PrimitiveType::Never),
2423             _ => None,
2424         }
2425     }
2426
2427     pub fn as_str(&self) -> &'static str {
2428         use self::PrimitiveType::*;
2429         match *self {
2430             Isize => "isize",
2431             I8 => "i8",
2432             I16 => "i16",
2433             I32 => "i32",
2434             I64 => "i64",
2435             I128 => "i128",
2436             Usize => "usize",
2437             U8 => "u8",
2438             U16 => "u16",
2439             U32 => "u32",
2440             U64 => "u64",
2441             U128 => "u128",
2442             F32 => "f32",
2443             F64 => "f64",
2444             Str => "str",
2445             Bool => "bool",
2446             Char => "char",
2447             Array => "array",
2448             Slice => "slice",
2449             Tuple => "tuple",
2450             Unit => "unit",
2451             RawPointer => "pointer",
2452             Reference => "reference",
2453             Fn => "fn",
2454             Never => "never",
2455         }
2456     }
2457
2458     pub fn to_url_str(&self) -> &'static str {
2459         self.as_str()
2460     }
2461 }
2462
2463 impl From<ast::IntTy> for PrimitiveType {
2464     fn from(int_ty: ast::IntTy) -> PrimitiveType {
2465         match int_ty {
2466             ast::IntTy::Isize => PrimitiveType::Isize,
2467             ast::IntTy::I8 => PrimitiveType::I8,
2468             ast::IntTy::I16 => PrimitiveType::I16,
2469             ast::IntTy::I32 => PrimitiveType::I32,
2470             ast::IntTy::I64 => PrimitiveType::I64,
2471             ast::IntTy::I128 => PrimitiveType::I128,
2472         }
2473     }
2474 }
2475
2476 impl From<ast::UintTy> for PrimitiveType {
2477     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
2478         match uint_ty {
2479             ast::UintTy::Usize => PrimitiveType::Usize,
2480             ast::UintTy::U8 => PrimitiveType::U8,
2481             ast::UintTy::U16 => PrimitiveType::U16,
2482             ast::UintTy::U32 => PrimitiveType::U32,
2483             ast::UintTy::U64 => PrimitiveType::U64,
2484             ast::UintTy::U128 => PrimitiveType::U128,
2485         }
2486     }
2487 }
2488
2489 impl From<ast::FloatTy> for PrimitiveType {
2490     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
2491         match float_ty {
2492             ast::FloatTy::F32 => PrimitiveType::F32,
2493             ast::FloatTy::F64 => PrimitiveType::F64,
2494         }
2495     }
2496 }
2497
2498 impl Clean<Type> for hir::Ty {
2499     fn clean(&self, cx: &DocContext) -> Type {
2500         use rustc::hir::*;
2501         match self.node {
2502             TyNever => Never,
2503             TyPtr(ref m) => RawPointer(m.mutbl.clean(cx), box m.ty.clean(cx)),
2504             TyRptr(ref l, ref m) => {
2505                 let lifetime = if l.is_elided() {
2506                     None
2507                 } else {
2508                     Some(l.clean(cx))
2509                 };
2510                 BorrowedRef {lifetime: lifetime, mutability: m.mutbl.clean(cx),
2511                              type_: box m.ty.clean(cx)}
2512             }
2513             TySlice(ref ty) => Slice(box ty.clean(cx)),
2514             TyArray(ref ty, n) => {
2515                 let def_id = cx.tcx.hir.body_owner_def_id(n);
2516                 let param_env = cx.tcx.param_env(def_id);
2517                 let substs = Substs::identity_for_item(cx.tcx, def_id);
2518                 let cid = GlobalId {
2519                     instance: ty::Instance::new(def_id, substs),
2520                     promoted: None
2521                 };
2522                 let n = cx.tcx.const_eval(param_env.and(cid)).unwrap_or_else(|_| {
2523                     cx.tcx.mk_const(ty::Const {
2524                         val: ConstVal::Unevaluated(def_id, substs),
2525                         ty: cx.tcx.types.usize
2526                     })
2527                 });
2528                 let n = print_const(cx, n);
2529                 Array(box ty.clean(cx), n)
2530             },
2531             TyTup(ref tys) => Tuple(tys.clean(cx)),
2532             TyPath(hir::QPath::Resolved(None, ref path)) => {
2533                 if let Some(new_ty) = cx.ty_substs.borrow().get(&path.def).cloned() {
2534                     return new_ty;
2535                 }
2536
2537                 let mut alias = None;
2538                 if let Def::TyAlias(def_id) = path.def {
2539                     // Substitute private type aliases
2540                     if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
2541                         if !cx.access_levels.borrow().is_exported(def_id) {
2542                             alias = Some(&cx.tcx.hir.expect_item(node_id).node);
2543                         }
2544                     }
2545                 };
2546
2547                 if let Some(&hir::ItemTy(ref ty, ref generics)) = alias {
2548                     let provided_params = &path.segments.last().unwrap();
2549                     let mut ty_substs = FxHashMap();
2550                     let mut lt_substs = FxHashMap();
2551                     provided_params.with_parameters(|provided_params| {
2552                         for (i, ty_param) in generics.ty_params().enumerate() {
2553                             let ty_param_def = Def::TyParam(cx.tcx.hir.local_def_id(ty_param.id));
2554                             if let Some(ty) = provided_params.types.get(i).cloned() {
2555                                 ty_substs.insert(ty_param_def, ty.into_inner().clean(cx));
2556                             } else if let Some(default) = ty_param.default.clone() {
2557                                 ty_substs.insert(ty_param_def, default.into_inner().clean(cx));
2558                             }
2559                         }
2560
2561                         for (i, lt_param) in generics.lifetimes().enumerate() {
2562                             if let Some(lt) = provided_params.lifetimes.get(i).cloned() {
2563                                 if !lt.is_elided() {
2564                                     let lt_def_id = cx.tcx.hir.local_def_id(lt_param.lifetime.id);
2565                                     lt_substs.insert(lt_def_id, lt.clean(cx));
2566                                 }
2567                             }
2568                         }
2569                     });
2570                     return cx.enter_alias(ty_substs, lt_substs, || ty.clean(cx));
2571                 }
2572                 resolve_type(cx, path.clean(cx), self.id)
2573             }
2574             TyPath(hir::QPath::Resolved(Some(ref qself), ref p)) => {
2575                 let mut segments: Vec<_> = p.segments.clone().into();
2576                 segments.pop();
2577                 let trait_path = hir::Path {
2578                     span: p.span,
2579                     def: Def::Trait(cx.tcx.associated_item(p.def.def_id()).container.id()),
2580                     segments: segments.into(),
2581                 };
2582                 Type::QPath {
2583                     name: p.segments.last().unwrap().name.clean(cx),
2584                     self_type: box qself.clean(cx),
2585                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
2586                 }
2587             }
2588             TyPath(hir::QPath::TypeRelative(ref qself, ref segment)) => {
2589                 let mut def = Def::Err;
2590                 let ty = hir_ty_to_ty(cx.tcx, self);
2591                 if let ty::TyProjection(proj) = ty.sty {
2592                     def = Def::Trait(proj.trait_ref(cx.tcx).def_id);
2593                 }
2594                 let trait_path = hir::Path {
2595                     span: self.span,
2596                     def,
2597                     segments: vec![].into(),
2598                 };
2599                 Type::QPath {
2600                     name: segment.name.clean(cx),
2601                     self_type: box qself.clean(cx),
2602                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
2603                 }
2604             }
2605             TyTraitObject(ref bounds, ref lifetime) => {
2606                 match bounds[0].clean(cx).trait_ {
2607                     ResolvedPath { path, typarams: None, did, is_generic } => {
2608                         let mut bounds: Vec<_> = bounds[1..].iter().map(|bound| {
2609                             TraitBound(bound.clean(cx), hir::TraitBoundModifier::None)
2610                         }).collect();
2611                         if !lifetime.is_elided() {
2612                             bounds.push(RegionBound(lifetime.clean(cx)));
2613                         }
2614                         ResolvedPath {
2615                             path,
2616                             typarams: Some(bounds),
2617                             did,
2618                             is_generic,
2619                         }
2620                     }
2621                     _ => Infer // shouldn't happen
2622                 }
2623             }
2624             TyBareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
2625             TyImplTraitExistential(ref exist_ty, ref _lts) => ImplTrait(exist_ty.bounds.clean(cx)),
2626             TyInfer | TyErr => Infer,
2627             TyTypeof(..) => panic!("Unimplemented type {:?}", self.node),
2628         }
2629     }
2630 }
2631
2632 impl<'tcx> Clean<Type> for Ty<'tcx> {
2633     fn clean(&self, cx: &DocContext) -> Type {
2634         match self.sty {
2635             ty::TyNever => Never,
2636             ty::TyBool => Primitive(PrimitiveType::Bool),
2637             ty::TyChar => Primitive(PrimitiveType::Char),
2638             ty::TyInt(int_ty) => Primitive(int_ty.into()),
2639             ty::TyUint(uint_ty) => Primitive(uint_ty.into()),
2640             ty::TyFloat(float_ty) => Primitive(float_ty.into()),
2641             ty::TyStr => Primitive(PrimitiveType::Str),
2642             ty::TySlice(ty) => Slice(box ty.clean(cx)),
2643             ty::TyArray(ty, n) => {
2644                 let mut n = cx.tcx.lift(&n).unwrap();
2645                 if let ConstVal::Unevaluated(def_id, substs) = n.val {
2646                     let param_env = cx.tcx.param_env(def_id);
2647                     let cid = GlobalId {
2648                         instance: ty::Instance::new(def_id, substs),
2649                         promoted: None
2650                     };
2651                     if let Ok(new_n) = cx.tcx.const_eval(param_env.and(cid)) {
2652                         n = new_n;
2653                     }
2654                 };
2655                 let n = print_const(cx, n);
2656                 Array(box ty.clean(cx), n)
2657             }
2658             ty::TyRawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
2659             ty::TyRef(r, mt) => BorrowedRef {
2660                 lifetime: r.clean(cx),
2661                 mutability: mt.mutbl.clean(cx),
2662                 type_: box mt.ty.clean(cx),
2663             },
2664             ty::TyFnDef(..) |
2665             ty::TyFnPtr(_) => {
2666                 let ty = cx.tcx.lift(self).unwrap();
2667                 let sig = ty.fn_sig(cx.tcx);
2668                 BareFunction(box BareFunctionDecl {
2669                     unsafety: sig.unsafety(),
2670                     generic_params: Vec::new(),
2671                     decl: (cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID), sig).clean(cx),
2672                     abi: sig.abi(),
2673                 })
2674             }
2675             ty::TyAdt(def, substs) => {
2676                 let did = def.did;
2677                 let kind = match def.adt_kind() {
2678                     AdtKind::Struct => TypeKind::Struct,
2679                     AdtKind::Union => TypeKind::Union,
2680                     AdtKind::Enum => TypeKind::Enum,
2681                 };
2682                 inline::record_extern_fqn(cx, did, kind);
2683                 let path = external_path(cx, &cx.tcx.item_name(did),
2684                                          None, false, vec![], substs);
2685                 ResolvedPath {
2686                     path,
2687                     typarams: None,
2688                     did,
2689                     is_generic: false,
2690                 }
2691             }
2692             ty::TyForeign(did) => {
2693                 inline::record_extern_fqn(cx, did, TypeKind::Foreign);
2694                 let path = external_path(cx, &cx.tcx.item_name(did),
2695                                          None, false, vec![], Substs::empty());
2696                 ResolvedPath {
2697                     path: path,
2698                     typarams: None,
2699                     did: did,
2700                     is_generic: false,
2701                 }
2702             }
2703             ty::TyDynamic(ref obj, ref reg) => {
2704                 if let Some(principal) = obj.principal() {
2705                     let did = principal.def_id();
2706                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
2707
2708                     let mut typarams = vec![];
2709                     reg.clean(cx).map(|b| typarams.push(RegionBound(b)));
2710                     for did in obj.auto_traits() {
2711                         let empty = cx.tcx.intern_substs(&[]);
2712                         let path = external_path(cx, &cx.tcx.item_name(did),
2713                             Some(did), false, vec![], empty);
2714                         inline::record_extern_fqn(cx, did, TypeKind::Trait);
2715                         let bound = TraitBound(PolyTrait {
2716                             trait_: ResolvedPath {
2717                                 path,
2718                                 typarams: None,
2719                                 did,
2720                                 is_generic: false,
2721                             },
2722                             generic_params: Vec::new(),
2723                         }, hir::TraitBoundModifier::None);
2724                         typarams.push(bound);
2725                     }
2726
2727                     let mut bindings = vec![];
2728                     for ty::Binder(ref pb) in obj.projection_bounds() {
2729                         bindings.push(TypeBinding {
2730                             name: cx.tcx.associated_item(pb.item_def_id).name.clean(cx),
2731                             ty: pb.ty.clean(cx)
2732                         });
2733                     }
2734
2735                     let path = external_path(cx, &cx.tcx.item_name(did), Some(did),
2736                         false, bindings, principal.0.substs);
2737                     ResolvedPath {
2738                         path,
2739                         typarams: Some(typarams),
2740                         did,
2741                         is_generic: false,
2742                     }
2743                 } else {
2744                     Never
2745                 }
2746             }
2747             ty::TyTuple(ref t) => Tuple(t.clean(cx)),
2748
2749             ty::TyProjection(ref data) => data.clean(cx),
2750
2751             ty::TyParam(ref p) => Generic(p.name.to_string()),
2752
2753             ty::TyAnon(def_id, substs) => {
2754                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
2755                 // by looking up the projections associated with the def_id.
2756                 let predicates_of = cx.tcx.predicates_of(def_id);
2757                 let substs = cx.tcx.lift(&substs).unwrap();
2758                 let bounds = predicates_of.instantiate(cx.tcx, substs);
2759                 ImplTrait(bounds.predicates.into_iter().filter_map(|predicate| {
2760                     predicate.to_opt_poly_trait_ref().clean(cx)
2761                 }).collect())
2762             }
2763
2764             ty::TyClosure(..) | ty::TyGenerator(..) => Tuple(vec![]), // FIXME(pcwalton)
2765
2766             ty::TyGeneratorWitness(..) => panic!("TyGeneratorWitness"),
2767             ty::TyInfer(..) => panic!("TyInfer"),
2768             ty::TyError => panic!("TyError"),
2769         }
2770     }
2771 }
2772
2773 impl Clean<Item> for hir::StructField {
2774     fn clean(&self, cx: &DocContext) -> Item {
2775         Item {
2776             name: Some(self.name).clean(cx),
2777             attrs: self.attrs.clean(cx),
2778             source: self.span.clean(cx),
2779             visibility: self.vis.clean(cx),
2780             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2781             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2782             def_id: cx.tcx.hir.local_def_id(self.id),
2783             inner: StructFieldItem(self.ty.clean(cx)),
2784         }
2785     }
2786 }
2787
2788 impl<'tcx> Clean<Item> for ty::FieldDef {
2789     fn clean(&self, cx: &DocContext) -> Item {
2790         Item {
2791             name: Some(self.name).clean(cx),
2792             attrs: cx.tcx.get_attrs(self.did).clean(cx),
2793             source: cx.tcx.def_span(self.did).clean(cx),
2794             visibility: self.vis.clean(cx),
2795             stability: get_stability(cx, self.did),
2796             deprecation: get_deprecation(cx, self.did),
2797             def_id: self.did,
2798             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
2799         }
2800     }
2801 }
2802
2803 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug)]
2804 pub enum Visibility {
2805     Public,
2806     Inherited,
2807 }
2808
2809 impl Clean<Option<Visibility>> for hir::Visibility {
2810     fn clean(&self, _: &DocContext) -> Option<Visibility> {
2811         Some(if *self == hir::Visibility::Public { Public } else { Inherited })
2812     }
2813 }
2814
2815 impl Clean<Option<Visibility>> for ty::Visibility {
2816     fn clean(&self, _: &DocContext) -> Option<Visibility> {
2817         Some(if *self == ty::Visibility::Public { Public } else { Inherited })
2818     }
2819 }
2820
2821 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2822 pub struct Struct {
2823     pub struct_type: doctree::StructType,
2824     pub generics: Generics,
2825     pub fields: Vec<Item>,
2826     pub fields_stripped: bool,
2827 }
2828
2829 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2830 pub struct Union {
2831     pub struct_type: doctree::StructType,
2832     pub generics: Generics,
2833     pub fields: Vec<Item>,
2834     pub fields_stripped: bool,
2835 }
2836
2837 impl Clean<Vec<Item>> for doctree::Struct {
2838     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2839         let name = self.name.clean(cx);
2840         let mut ret = get_auto_traits_with_node_id(cx, self.id, name.clone());
2841
2842         ret.push(Item {
2843             name: Some(name),
2844             attrs: self.attrs.clean(cx),
2845             source: self.whence.clean(cx),
2846             def_id: cx.tcx.hir.local_def_id(self.id),
2847             visibility: self.vis.clean(cx),
2848             stability: self.stab.clean(cx),
2849             deprecation: self.depr.clean(cx),
2850             inner: StructItem(Struct {
2851                 struct_type: self.struct_type,
2852                 generics: self.generics.clean(cx),
2853                 fields: self.fields.clean(cx),
2854                 fields_stripped: false,
2855             }),
2856         });
2857
2858         ret
2859     }
2860 }
2861
2862 impl Clean<Vec<Item>> for doctree::Union {
2863     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2864         let name = self.name.clean(cx);
2865         let mut ret = get_auto_traits_with_node_id(cx, self.id, name.clone());
2866
2867         ret.push(Item {
2868             name: Some(name),
2869             attrs: self.attrs.clean(cx),
2870             source: self.whence.clean(cx),
2871             def_id: cx.tcx.hir.local_def_id(self.id),
2872             visibility: self.vis.clean(cx),
2873             stability: self.stab.clean(cx),
2874             deprecation: self.depr.clean(cx),
2875             inner: UnionItem(Union {
2876                 struct_type: self.struct_type,
2877                 generics: self.generics.clean(cx),
2878                 fields: self.fields.clean(cx),
2879                 fields_stripped: false,
2880             }),
2881         });
2882
2883         ret
2884     }
2885 }
2886
2887 /// This is a more limited form of the standard Struct, different in that
2888 /// it lacks the things most items have (name, id, parameterization). Found
2889 /// only as a variant in an enum.
2890 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2891 pub struct VariantStruct {
2892     pub struct_type: doctree::StructType,
2893     pub fields: Vec<Item>,
2894     pub fields_stripped: bool,
2895 }
2896
2897 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
2898     fn clean(&self, cx: &DocContext) -> VariantStruct {
2899         VariantStruct {
2900             struct_type: doctree::struct_type_from_def(self),
2901             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
2902             fields_stripped: false,
2903         }
2904     }
2905 }
2906
2907 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2908 pub struct Enum {
2909     pub variants: Vec<Item>,
2910     pub generics: Generics,
2911     pub variants_stripped: bool,
2912 }
2913
2914 impl Clean<Vec<Item>> for doctree::Enum {
2915     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2916         let name = self.name.clean(cx);
2917         let mut ret = get_auto_traits_with_node_id(cx, self.id, name.clone());
2918
2919         ret.push(Item {
2920             name: Some(name),
2921             attrs: self.attrs.clean(cx),
2922             source: self.whence.clean(cx),
2923             def_id: cx.tcx.hir.local_def_id(self.id),
2924             visibility: self.vis.clean(cx),
2925             stability: self.stab.clean(cx),
2926             deprecation: self.depr.clean(cx),
2927             inner: EnumItem(Enum {
2928                 variants: self.variants.clean(cx),
2929                 generics: self.generics.clean(cx),
2930                 variants_stripped: false,
2931             }),
2932         });
2933
2934         ret
2935     }
2936 }
2937
2938 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2939 pub struct Variant {
2940     pub kind: VariantKind,
2941 }
2942
2943 impl Clean<Item> for doctree::Variant {
2944     fn clean(&self, cx: &DocContext) -> Item {
2945         Item {
2946             name: Some(self.name.clean(cx)),
2947             attrs: self.attrs.clean(cx),
2948             source: self.whence.clean(cx),
2949             visibility: None,
2950             stability: self.stab.clean(cx),
2951             deprecation: self.depr.clean(cx),
2952             def_id: cx.tcx.hir.local_def_id(self.def.id()),
2953             inner: VariantItem(Variant {
2954                 kind: self.def.clean(cx),
2955             }),
2956         }
2957     }
2958 }
2959
2960 impl<'tcx> Clean<Item> for ty::VariantDef {
2961     fn clean(&self, cx: &DocContext) -> Item {
2962         let kind = match self.ctor_kind {
2963             CtorKind::Const => VariantKind::CLike,
2964             CtorKind::Fn => {
2965                 VariantKind::Tuple(
2966                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
2967                 )
2968             }
2969             CtorKind::Fictive => {
2970                 VariantKind::Struct(VariantStruct {
2971                     struct_type: doctree::Plain,
2972                     fields_stripped: false,
2973                     fields: self.fields.iter().map(|field| {
2974                         Item {
2975                             source: cx.tcx.def_span(field.did).clean(cx),
2976                             name: Some(field.name.clean(cx)),
2977                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
2978                             visibility: field.vis.clean(cx),
2979                             def_id: field.did,
2980                             stability: get_stability(cx, field.did),
2981                             deprecation: get_deprecation(cx, field.did),
2982                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
2983                         }
2984                     }).collect()
2985                 })
2986             }
2987         };
2988         Item {
2989             name: Some(self.name.clean(cx)),
2990             attrs: inline::load_attrs(cx, self.did),
2991             source: cx.tcx.def_span(self.did).clean(cx),
2992             visibility: Some(Inherited),
2993             def_id: self.did,
2994             inner: VariantItem(Variant { kind: kind }),
2995             stability: get_stability(cx, self.did),
2996             deprecation: get_deprecation(cx, self.did),
2997         }
2998     }
2999 }
3000
3001 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3002 pub enum VariantKind {
3003     CLike,
3004     Tuple(Vec<Type>),
3005     Struct(VariantStruct),
3006 }
3007
3008 impl Clean<VariantKind> for hir::VariantData {
3009     fn clean(&self, cx: &DocContext) -> VariantKind {
3010         if self.is_struct() {
3011             VariantKind::Struct(self.clean(cx))
3012         } else if self.is_unit() {
3013             VariantKind::CLike
3014         } else {
3015             VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect())
3016         }
3017     }
3018 }
3019
3020 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3021 pub struct Span {
3022     pub filename: FileName,
3023     pub loline: usize,
3024     pub locol: usize,
3025     pub hiline: usize,
3026     pub hicol: usize,
3027 }
3028
3029 impl Span {
3030     pub fn empty() -> Span {
3031         Span {
3032             filename: FileName::Anon,
3033             loline: 0, locol: 0,
3034             hiline: 0, hicol: 0,
3035         }
3036     }
3037 }
3038
3039 impl Clean<Span> for syntax_pos::Span {
3040     fn clean(&self, cx: &DocContext) -> Span {
3041         if *self == DUMMY_SP {
3042             return Span::empty();
3043         }
3044
3045         let cm = cx.sess().codemap();
3046         let filename = cm.span_to_filename(*self);
3047         let lo = cm.lookup_char_pos(self.lo());
3048         let hi = cm.lookup_char_pos(self.hi());
3049         Span {
3050             filename,
3051             loline: lo.line,
3052             locol: lo.col.to_usize(),
3053             hiline: hi.line,
3054             hicol: hi.col.to_usize(),
3055         }
3056     }
3057 }
3058
3059 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3060 pub struct Path {
3061     pub global: bool,
3062     pub def: Def,
3063     pub segments: Vec<PathSegment>,
3064 }
3065
3066 impl Path {
3067     pub fn singleton(name: String) -> Path {
3068         Path {
3069             global: false,
3070             def: Def::Err,
3071             segments: vec![PathSegment {
3072                 name,
3073                 params: PathParameters::AngleBracketed {
3074                     lifetimes: Vec::new(),
3075                     types: Vec::new(),
3076                     bindings: Vec::new(),
3077                 }
3078             }]
3079         }
3080     }
3081
3082     pub fn last_name(&self) -> &str {
3083         self.segments.last().unwrap().name.as_str()
3084     }
3085 }
3086
3087 impl Clean<Path> for hir::Path {
3088     fn clean(&self, cx: &DocContext) -> Path {
3089         Path {
3090             global: self.is_global(),
3091             def: self.def,
3092             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
3093         }
3094     }
3095 }
3096
3097 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3098 pub enum PathParameters {
3099     AngleBracketed {
3100         lifetimes: Vec<Lifetime>,
3101         types: Vec<Type>,
3102         bindings: Vec<TypeBinding>,
3103     },
3104     Parenthesized {
3105         inputs: Vec<Type>,
3106         output: Option<Type>,
3107     }
3108 }
3109
3110 impl Clean<PathParameters> for hir::PathParameters {
3111     fn clean(&self, cx: &DocContext) -> PathParameters {
3112         if self.parenthesized {
3113             let output = self.bindings[0].ty.clean(cx);
3114             PathParameters::Parenthesized {
3115                 inputs: self.inputs().clean(cx),
3116                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
3117             }
3118         } else {
3119             PathParameters::AngleBracketed {
3120                 lifetimes: if self.lifetimes.iter().all(|lt| lt.is_elided()) {
3121                     vec![]
3122                 } else {
3123                     self.lifetimes.clean(cx)
3124                 },
3125                 types: self.types.clean(cx),
3126                 bindings: self.bindings.clean(cx),
3127             }
3128         }
3129     }
3130 }
3131
3132 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3133 pub struct PathSegment {
3134     pub name: String,
3135     pub params: PathParameters,
3136 }
3137
3138 impl Clean<PathSegment> for hir::PathSegment {
3139     fn clean(&self, cx: &DocContext) -> PathSegment {
3140         PathSegment {
3141             name: self.name.clean(cx),
3142             params: self.with_parameters(|parameters| parameters.clean(cx))
3143         }
3144     }
3145 }
3146
3147 fn strip_type(ty: Type) -> Type {
3148     match ty {
3149         Type::ResolvedPath { path, typarams, did, is_generic } => {
3150             Type::ResolvedPath { path: strip_path(&path), typarams, did, is_generic }
3151         }
3152         Type::Tuple(inner_tys) => {
3153             Type::Tuple(inner_tys.iter().map(|t| strip_type(t.clone())).collect())
3154         }
3155         Type::Slice(inner_ty) => Type::Slice(Box::new(strip_type(*inner_ty))),
3156         Type::Array(inner_ty, s) => Type::Array(Box::new(strip_type(*inner_ty)), s),
3157         Type::Unique(inner_ty) => Type::Unique(Box::new(strip_type(*inner_ty))),
3158         Type::RawPointer(m, inner_ty) => Type::RawPointer(m, Box::new(strip_type(*inner_ty))),
3159         Type::BorrowedRef { lifetime, mutability, type_ } => {
3160             Type::BorrowedRef { lifetime, mutability, type_: Box::new(strip_type(*type_)) }
3161         }
3162         Type::QPath { name, self_type, trait_ } => {
3163             Type::QPath {
3164                 name,
3165                 self_type: Box::new(strip_type(*self_type)), trait_: Box::new(strip_type(*trait_))
3166             }
3167         }
3168         _ => ty
3169     }
3170 }
3171
3172 fn strip_path(path: &Path) -> Path {
3173     let segments = path.segments.iter().map(|s| {
3174         PathSegment {
3175             name: s.name.clone(),
3176             params: PathParameters::AngleBracketed {
3177                 lifetimes: Vec::new(),
3178                 types: Vec::new(),
3179                 bindings: Vec::new(),
3180             }
3181         }
3182     }).collect();
3183
3184     Path {
3185         global: path.global,
3186         def: path.def.clone(),
3187         segments,
3188     }
3189 }
3190
3191 fn qpath_to_string(p: &hir::QPath) -> String {
3192     let segments = match *p {
3193         hir::QPath::Resolved(_, ref path) => &path.segments,
3194         hir::QPath::TypeRelative(_, ref segment) => return segment.name.to_string(),
3195     };
3196
3197     let mut s = String::new();
3198     for (i, seg) in segments.iter().enumerate() {
3199         if i > 0 {
3200             s.push_str("::");
3201         }
3202         if seg.name != keywords::CrateRoot.name() {
3203             s.push_str(&*seg.name.as_str());
3204         }
3205     }
3206     s
3207 }
3208
3209 impl Clean<String> for ast::Name {
3210     fn clean(&self, _: &DocContext) -> String {
3211         self.to_string()
3212     }
3213 }
3214
3215 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3216 pub struct Typedef {
3217     pub type_: Type,
3218     pub generics: Generics,
3219 }
3220
3221 impl Clean<Item> for doctree::Typedef {
3222     fn clean(&self, cx: &DocContext) -> Item {
3223         Item {
3224             name: Some(self.name.clean(cx)),
3225             attrs: self.attrs.clean(cx),
3226             source: self.whence.clean(cx),
3227             def_id: cx.tcx.hir.local_def_id(self.id.clone()),
3228             visibility: self.vis.clean(cx),
3229             stability: self.stab.clean(cx),
3230             deprecation: self.depr.clean(cx),
3231             inner: TypedefItem(Typedef {
3232                 type_: self.ty.clean(cx),
3233                 generics: self.gen.clean(cx),
3234             }, false),
3235         }
3236     }
3237 }
3238
3239 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3240 pub struct BareFunctionDecl {
3241     pub unsafety: hir::Unsafety,
3242     pub generic_params: Vec<GenericParam>,
3243     pub decl: FnDecl,
3244     pub abi: Abi,
3245 }
3246
3247 impl Clean<BareFunctionDecl> for hir::BareFnTy {
3248     fn clean(&self, cx: &DocContext) -> BareFunctionDecl {
3249         BareFunctionDecl {
3250             unsafety: self.unsafety,
3251             generic_params: self.generic_params.clean(cx),
3252             decl: (&*self.decl, &self.arg_names[..]).clean(cx),
3253             abi: self.abi,
3254         }
3255     }
3256 }
3257
3258 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3259 pub struct Static {
3260     pub type_: Type,
3261     pub mutability: Mutability,
3262     /// It's useful to have the value of a static documented, but I have no
3263     /// desire to represent expressions (that'd basically be all of the AST,
3264     /// which is huge!). So, have a string.
3265     pub expr: String,
3266 }
3267
3268 impl Clean<Item> for doctree::Static {
3269     fn clean(&self, cx: &DocContext) -> Item {
3270         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
3271         Item {
3272             name: Some(self.name.clean(cx)),
3273             attrs: self.attrs.clean(cx),
3274             source: self.whence.clean(cx),
3275             def_id: cx.tcx.hir.local_def_id(self.id),
3276             visibility: self.vis.clean(cx),
3277             stability: self.stab.clean(cx),
3278             deprecation: self.depr.clean(cx),
3279             inner: StaticItem(Static {
3280                 type_: self.type_.clean(cx),
3281                 mutability: self.mutability.clean(cx),
3282                 expr: print_const_expr(cx, self.expr),
3283             }),
3284         }
3285     }
3286 }
3287
3288 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3289 pub struct Constant {
3290     pub type_: Type,
3291     pub expr: String,
3292 }
3293
3294 impl Clean<Item> for doctree::Constant {
3295     fn clean(&self, cx: &DocContext) -> Item {
3296         Item {
3297             name: Some(self.name.clean(cx)),
3298             attrs: self.attrs.clean(cx),
3299             source: self.whence.clean(cx),
3300             def_id: cx.tcx.hir.local_def_id(self.id),
3301             visibility: self.vis.clean(cx),
3302             stability: self.stab.clean(cx),
3303             deprecation: self.depr.clean(cx),
3304             inner: ConstantItem(Constant {
3305                 type_: self.type_.clean(cx),
3306                 expr: print_const_expr(cx, self.expr),
3307             }),
3308         }
3309     }
3310 }
3311
3312 #[derive(Debug, Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Hash)]
3313 pub enum Mutability {
3314     Mutable,
3315     Immutable,
3316 }
3317
3318 impl Clean<Mutability> for hir::Mutability {
3319     fn clean(&self, _: &DocContext) -> Mutability {
3320         match self {
3321             &hir::MutMutable => Mutable,
3322             &hir::MutImmutable => Immutable,
3323         }
3324     }
3325 }
3326
3327 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Debug, Hash)]
3328 pub enum ImplPolarity {
3329     Positive,
3330     Negative,
3331 }
3332
3333 impl Clean<ImplPolarity> for hir::ImplPolarity {
3334     fn clean(&self, _: &DocContext) -> ImplPolarity {
3335         match self {
3336             &hir::ImplPolarity::Positive => ImplPolarity::Positive,
3337             &hir::ImplPolarity::Negative => ImplPolarity::Negative,
3338         }
3339     }
3340 }
3341
3342 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3343 pub struct Impl {
3344     pub unsafety: hir::Unsafety,
3345     pub generics: Generics,
3346     pub provided_trait_methods: FxHashSet<String>,
3347     pub trait_: Option<Type>,
3348     pub for_: Type,
3349     pub items: Vec<Item>,
3350     pub polarity: Option<ImplPolarity>,
3351     pub synthetic: bool,
3352 }
3353
3354 pub fn get_auto_traits_with_node_id(cx: &DocContext, id: ast::NodeId, name: String) -> Vec<Item> {
3355     let finder = AutoTraitFinder { cx };
3356     finder.get_with_node_id(id, name)
3357 }
3358
3359 pub fn get_auto_traits_with_def_id(cx: &DocContext, id: DefId) -> Vec<Item> {
3360     let finder = AutoTraitFinder {
3361         cx,
3362     };
3363
3364     finder.get_with_def_id(id)
3365 }
3366
3367 impl Clean<Vec<Item>> for doctree::Impl {
3368     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3369         let mut ret = Vec::new();
3370         let trait_ = self.trait_.clean(cx);
3371         let items = self.items.clean(cx);
3372
3373         // If this impl block is an implementation of the Deref trait, then we
3374         // need to try inlining the target's inherent impl blocks as well.
3375         if trait_.def_id() == cx.tcx.lang_items().deref_trait() {
3376             build_deref_target_impls(cx, &items, &mut ret);
3377         }
3378
3379         let provided = trait_.def_id().map(|did| {
3380             cx.tcx.provided_trait_methods(did)
3381                   .into_iter()
3382                   .map(|meth| meth.name.to_string())
3383                   .collect()
3384         }).unwrap_or(FxHashSet());
3385
3386         ret.push(Item {
3387             name: None,
3388             attrs: self.attrs.clean(cx),
3389             source: self.whence.clean(cx),
3390             def_id: cx.tcx.hir.local_def_id(self.id),
3391             visibility: self.vis.clean(cx),
3392             stability: self.stab.clean(cx),
3393             deprecation: self.depr.clean(cx),
3394             inner: ImplItem(Impl {
3395                 unsafety: self.unsafety,
3396                 generics: self.generics.clean(cx),
3397                 provided_trait_methods: provided,
3398                 trait_,
3399                 for_: self.for_.clean(cx),
3400                 items,
3401                 polarity: Some(self.polarity.clean(cx)),
3402                 synthetic: false,
3403             })
3404         });
3405         ret
3406     }
3407 }
3408
3409 fn build_deref_target_impls(cx: &DocContext,
3410                             items: &[Item],
3411                             ret: &mut Vec<Item>) {
3412     use self::PrimitiveType::*;
3413     let tcx = cx.tcx;
3414
3415     for item in items {
3416         let target = match item.inner {
3417             TypedefItem(ref t, true) => &t.type_,
3418             _ => continue,
3419         };
3420         let primitive = match *target {
3421             ResolvedPath { did, .. } if did.is_local() => continue,
3422             ResolvedPath { did, .. } => {
3423                 // We set the last parameter to false to avoid looking for auto-impls for traits
3424                 // and therefore avoid an ICE.
3425                 // The reason behind this is that auto-traits don't propagate through Deref so
3426                 // we're not supposed to synthesise impls for them.
3427                 ret.extend(inline::build_impls(cx, did, false));
3428                 continue
3429             }
3430             _ => match target.primitive_type() {
3431                 Some(prim) => prim,
3432                 None => continue,
3433             }
3434         };
3435         let did = match primitive {
3436             Isize => tcx.lang_items().isize_impl(),
3437             I8 => tcx.lang_items().i8_impl(),
3438             I16 => tcx.lang_items().i16_impl(),
3439             I32 => tcx.lang_items().i32_impl(),
3440             I64 => tcx.lang_items().i64_impl(),
3441             I128 => tcx.lang_items().i128_impl(),
3442             Usize => tcx.lang_items().usize_impl(),
3443             U8 => tcx.lang_items().u8_impl(),
3444             U16 => tcx.lang_items().u16_impl(),
3445             U32 => tcx.lang_items().u32_impl(),
3446             U64 => tcx.lang_items().u64_impl(),
3447             U128 => tcx.lang_items().u128_impl(),
3448             F32 => tcx.lang_items().f32_impl(),
3449             F64 => tcx.lang_items().f64_impl(),
3450             Char => tcx.lang_items().char_impl(),
3451             Bool => None,
3452             Str => tcx.lang_items().str_impl(),
3453             Slice => tcx.lang_items().slice_impl(),
3454             Array => tcx.lang_items().slice_impl(),
3455             Tuple => None,
3456             Unit => None,
3457             RawPointer => tcx.lang_items().const_ptr_impl(),
3458             Reference => None,
3459             Fn => None,
3460             Never => None,
3461         };
3462         if let Some(did) = did {
3463             if !did.is_local() {
3464                 inline::build_impl(cx, did, ret);
3465             }
3466         }
3467     }
3468 }
3469
3470 impl Clean<Item> for doctree::ExternCrate {
3471     fn clean(&self, cx: &DocContext) -> Item {
3472         Item {
3473             name: None,
3474             attrs: self.attrs.clean(cx),
3475             source: self.whence.clean(cx),
3476             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
3477             visibility: self.vis.clean(cx),
3478             stability: None,
3479             deprecation: None,
3480             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
3481         }
3482     }
3483 }
3484
3485 impl Clean<Vec<Item>> for doctree::Import {
3486     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3487         // We consider inlining the documentation of `pub use` statements, but we
3488         // forcefully don't inline if this is not public or if the
3489         // #[doc(no_inline)] attribute is present.
3490         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
3491         let denied = self.vis != hir::Public || self.attrs.iter().any(|a| {
3492             a.name().unwrap() == "doc" && match a.meta_item_list() {
3493                 Some(l) => attr::list_contains_name(&l, "no_inline") ||
3494                            attr::list_contains_name(&l, "hidden"),
3495                 None => false,
3496             }
3497         });
3498         let path = self.path.clean(cx);
3499         let inner = if self.glob {
3500             Import::Glob(resolve_use_source(cx, path))
3501         } else {
3502             let name = self.name;
3503             if !denied {
3504                 if let Some(items) = inline::try_inline(cx, path.def, name) {
3505                     return items;
3506                 }
3507             }
3508             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
3509         };
3510         vec![Item {
3511             name: None,
3512             attrs: self.attrs.clean(cx),
3513             source: self.whence.clean(cx),
3514             def_id: cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID),
3515             visibility: self.vis.clean(cx),
3516             stability: None,
3517             deprecation: None,
3518             inner: ImportItem(inner)
3519         }]
3520     }
3521 }
3522
3523 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3524 pub enum Import {
3525     // use source as str;
3526     Simple(String, ImportSource),
3527     // use source::*;
3528     Glob(ImportSource)
3529 }
3530
3531 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3532 pub struct ImportSource {
3533     pub path: Path,
3534     pub did: Option<DefId>,
3535 }
3536
3537 impl Clean<Vec<Item>> for hir::ForeignMod {
3538     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3539         let mut items = self.items.clean(cx);
3540         for item in &mut items {
3541             if let ForeignFunctionItem(ref mut f) = item.inner {
3542                 f.abi = self.abi;
3543             }
3544         }
3545         items
3546     }
3547 }
3548
3549 impl Clean<Item> for hir::ForeignItem {
3550     fn clean(&self, cx: &DocContext) -> Item {
3551         let inner = match self.node {
3552             hir::ForeignItemFn(ref decl, ref names, ref generics) => {
3553                 ForeignFunctionItem(Function {
3554                     decl: (&**decl, &names[..]).clean(cx),
3555                     generics: generics.clean(cx),
3556                     unsafety: hir::Unsafety::Unsafe,
3557                     abi: Abi::Rust,
3558                     constness: hir::Constness::NotConst,
3559                 })
3560             }
3561             hir::ForeignItemStatic(ref ty, mutbl) => {
3562                 ForeignStaticItem(Static {
3563                     type_: ty.clean(cx),
3564                     mutability: if mutbl {Mutable} else {Immutable},
3565                     expr: "".to_string(),
3566                 })
3567             }
3568             hir::ForeignItemType => {
3569                 ForeignTypeItem
3570             }
3571         };
3572         Item {
3573             name: Some(self.name.clean(cx)),
3574             attrs: self.attrs.clean(cx),
3575             source: self.span.clean(cx),
3576             def_id: cx.tcx.hir.local_def_id(self.id),
3577             visibility: self.vis.clean(cx),
3578             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
3579             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
3580             inner,
3581         }
3582     }
3583 }
3584
3585 // Utilities
3586
3587 trait ToSource {
3588     fn to_src(&self, cx: &DocContext) -> String;
3589 }
3590
3591 impl ToSource for syntax_pos::Span {
3592     fn to_src(&self, cx: &DocContext) -> String {
3593         debug!("converting span {:?} to snippet", self.clean(cx));
3594         let sn = match cx.sess().codemap().span_to_snippet(*self) {
3595             Ok(x) => x.to_string(),
3596             Err(_) => "".to_string()
3597         };
3598         debug!("got snippet {}", sn);
3599         sn
3600     }
3601 }
3602
3603 fn name_from_pat(p: &hir::Pat) -> String {
3604     use rustc::hir::*;
3605     debug!("Trying to get a name from pattern: {:?}", p);
3606
3607     match p.node {
3608         PatKind::Wild => "_".to_string(),
3609         PatKind::Binding(_, _, ref p, _) => p.node.to_string(),
3610         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
3611         PatKind::Struct(ref name, ref fields, etc) => {
3612             format!("{} {{ {}{} }}", qpath_to_string(name),
3613                 fields.iter().map(|&Spanned { node: ref fp, .. }|
3614                                   format!("{}: {}", fp.name, name_from_pat(&*fp.pat)))
3615                              .collect::<Vec<String>>().join(", "),
3616                 if etc { ", ..." } else { "" }
3617             )
3618         }
3619         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
3620                                             .collect::<Vec<String>>().join(", ")),
3621         PatKind::Box(ref p) => name_from_pat(&**p),
3622         PatKind::Ref(ref p, _) => name_from_pat(&**p),
3623         PatKind::Lit(..) => {
3624             warn!("tried to get argument name from PatKind::Lit, \
3625                   which is silly in function arguments");
3626             "()".to_string()
3627         },
3628         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
3629                               which is not allowed in function arguments"),
3630         PatKind::Slice(ref begin, ref mid, ref end) => {
3631             let begin = begin.iter().map(|p| name_from_pat(&**p));
3632             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
3633             let end = end.iter().map(|p| name_from_pat(&**p));
3634             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
3635         },
3636     }
3637 }
3638
3639 fn print_const(cx: &DocContext, n: &ty::Const) -> String {
3640     match n.val {
3641         ConstVal::Unevaluated(def_id, _) => {
3642             if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
3643                 print_const_expr(cx, cx.tcx.hir.body_owned_by(node_id))
3644             } else {
3645                 inline::print_inlined_const(cx, def_id)
3646             }
3647         },
3648         ConstVal::Value(val) => {
3649             let mut s = String::new();
3650             ::rustc::mir::print_miri_value(val, n.ty, &mut s).unwrap();
3651             // array lengths are obviously usize
3652             if s.ends_with("usize") {
3653                 let n = s.len() - "usize".len();
3654                 s.truncate(n);
3655             }
3656             s
3657         },
3658     }
3659 }
3660
3661 fn print_const_expr(cx: &DocContext, body: hir::BodyId) -> String {
3662     cx.tcx.hir.node_to_pretty_string(body.node_id)
3663 }
3664
3665 /// Given a type Path, resolve it to a Type using the TyCtxt
3666 fn resolve_type(cx: &DocContext,
3667                 path: Path,
3668                 id: ast::NodeId) -> Type {
3669     if id == ast::DUMMY_NODE_ID {
3670         debug!("resolve_type({:?})", path);
3671     } else {
3672         debug!("resolve_type({:?},{:?})", path, id);
3673     }
3674
3675     let is_generic = match path.def {
3676         Def::PrimTy(p) => match p {
3677             hir::TyStr => return Primitive(PrimitiveType::Str),
3678             hir::TyBool => return Primitive(PrimitiveType::Bool),
3679             hir::TyChar => return Primitive(PrimitiveType::Char),
3680             hir::TyInt(int_ty) => return Primitive(int_ty.into()),
3681             hir::TyUint(uint_ty) => return Primitive(uint_ty.into()),
3682             hir::TyFloat(float_ty) => return Primitive(float_ty.into()),
3683         },
3684         Def::SelfTy(..) if path.segments.len() == 1 => {
3685             return Generic(keywords::SelfType.name().to_string());
3686         }
3687         Def::TyParam(..) if path.segments.len() == 1 => {
3688             return Generic(format!("{:#}", path));
3689         }
3690         Def::SelfTy(..) | Def::TyParam(..) | Def::AssociatedTy(..) => true,
3691         _ => false,
3692     };
3693     let did = register_def(&*cx, path.def);
3694     ResolvedPath { path: path, typarams: None, did: did, is_generic: is_generic }
3695 }
3696
3697 fn register_def(cx: &DocContext, def: Def) -> DefId {
3698     debug!("register_def({:?})", def);
3699
3700     let (did, kind) = match def {
3701         Def::Fn(i) => (i, TypeKind::Function),
3702         Def::TyAlias(i) => (i, TypeKind::Typedef),
3703         Def::Enum(i) => (i, TypeKind::Enum),
3704         Def::Trait(i) => (i, TypeKind::Trait),
3705         Def::Struct(i) => (i, TypeKind::Struct),
3706         Def::Union(i) => (i, TypeKind::Union),
3707         Def::Mod(i) => (i, TypeKind::Module),
3708         Def::TyForeign(i) => (i, TypeKind::Foreign),
3709         Def::Static(i, _) => (i, TypeKind::Static),
3710         Def::Variant(i) => (cx.tcx.parent_def_id(i).unwrap(), TypeKind::Enum),
3711         Def::Macro(i, _) => (i, TypeKind::Macro),
3712         Def::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
3713         Def::SelfTy(_, Some(impl_def_id)) => {
3714             return impl_def_id
3715         }
3716         _ => return def.def_id()
3717     };
3718     if did.is_local() { return did }
3719     inline::record_extern_fqn(cx, did, kind);
3720     if let TypeKind::Trait = kind {
3721         inline::record_extern_trait(cx, did);
3722     }
3723     did
3724 }
3725
3726 fn resolve_use_source(cx: &DocContext, path: Path) -> ImportSource {
3727     ImportSource {
3728         did: if path.def == Def::Err {
3729             None
3730         } else {
3731             Some(register_def(cx, path.def))
3732         },
3733         path,
3734     }
3735 }
3736
3737 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3738 pub struct Macro {
3739     pub source: String,
3740     pub imported_from: Option<String>,
3741 }
3742
3743 impl Clean<Item> for doctree::Macro {
3744     fn clean(&self, cx: &DocContext) -> Item {
3745         let name = self.name.clean(cx);
3746         Item {
3747             name: Some(name.clone()),
3748             attrs: self.attrs.clean(cx),
3749             source: self.whence.clean(cx),
3750             visibility: Some(Public),
3751             stability: self.stab.clean(cx),
3752             deprecation: self.depr.clean(cx),
3753             def_id: self.def_id,
3754             inner: MacroItem(Macro {
3755                 source: format!("macro_rules! {} {{\n{}}}",
3756                                 name,
3757                                 self.matchers.iter().map(|span| {
3758                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
3759                                 }).collect::<String>()),
3760                 imported_from: self.imported_from.clean(cx),
3761             }),
3762         }
3763     }
3764 }
3765
3766 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3767 pub struct Stability {
3768     pub level: stability::StabilityLevel,
3769     pub feature: String,
3770     pub since: String,
3771     pub deprecated_since: String,
3772     pub deprecated_reason: String,
3773     pub unstable_reason: String,
3774     pub issue: Option<u32>
3775 }
3776
3777 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3778 pub struct Deprecation {
3779     pub since: String,
3780     pub note: String,
3781 }
3782
3783 impl Clean<Stability> for attr::Stability {
3784     fn clean(&self, _: &DocContext) -> Stability {
3785         Stability {
3786             level: stability::StabilityLevel::from_attr_level(&self.level),
3787             feature: self.feature.to_string(),
3788             since: match self.level {
3789                 attr::Stable {ref since} => since.to_string(),
3790                 _ => "".to_string(),
3791             },
3792             deprecated_since: match self.rustc_depr {
3793                 Some(attr::RustcDeprecation {ref since, ..}) => since.to_string(),
3794                 _=> "".to_string(),
3795             },
3796             deprecated_reason: match self.rustc_depr {
3797                 Some(ref depr) => depr.reason.to_string(),
3798                 _ => "".to_string(),
3799             },
3800             unstable_reason: match self.level {
3801                 attr::Unstable { reason: Some(ref reason), .. } => reason.to_string(),
3802                 _ => "".to_string(),
3803             },
3804             issue: match self.level {
3805                 attr::Unstable {issue, ..} => Some(issue),
3806                 _ => None,
3807             }
3808         }
3809     }
3810 }
3811
3812 impl<'a> Clean<Stability> for &'a attr::Stability {
3813     fn clean(&self, dc: &DocContext) -> Stability {
3814         (**self).clean(dc)
3815     }
3816 }
3817
3818 impl Clean<Deprecation> for attr::Deprecation {
3819     fn clean(&self, _: &DocContext) -> Deprecation {
3820         Deprecation {
3821             since: self.since.as_ref().map_or("".to_string(), |s| s.to_string()),
3822             note: self.note.as_ref().map_or("".to_string(), |s| s.to_string()),
3823         }
3824     }
3825 }
3826
3827 /// An equality constraint on an associated type, e.g. `A=Bar` in `Foo<A=Bar>`
3828 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug, Hash)]
3829 pub struct TypeBinding {
3830     pub name: String,
3831     pub ty: Type
3832 }
3833
3834 impl Clean<TypeBinding> for hir::TypeBinding {
3835     fn clean(&self, cx: &DocContext) -> TypeBinding {
3836         TypeBinding {
3837             name: self.name.clean(cx),
3838             ty: self.ty.clean(cx)
3839         }
3840     }
3841 }
3842
3843 pub fn def_id_to_path(cx: &DocContext, did: DefId, name: Option<String>) -> Vec<String> {
3844     let crate_name = name.unwrap_or_else(|| cx.tcx.crate_name(did.krate).to_string());
3845     let relative = cx.tcx.def_path(did).data.into_iter().filter_map(|elem| {
3846         // extern blocks have an empty name
3847         let s = elem.data.to_string();
3848         if !s.is_empty() {
3849             Some(s)
3850         } else {
3851             None
3852         }
3853     });
3854     once(crate_name).chain(relative).collect()
3855 }
3856
3857 // Start of code copied from rust-clippy
3858
3859 pub fn get_trait_def_id(tcx: &TyCtxt, path: &[&str], use_local: bool) -> Option<DefId> {
3860     if use_local {
3861         path_to_def_local(tcx, path)
3862     } else {
3863         path_to_def(tcx, path)
3864     }
3865 }
3866
3867 pub fn path_to_def_local(tcx: &TyCtxt, path: &[&str]) -> Option<DefId> {
3868     let krate = tcx.hir.krate();
3869     let mut items = krate.module.item_ids.clone();
3870     let mut path_it = path.iter().peekable();
3871
3872     loop {
3873         let segment = match path_it.next() {
3874             Some(segment) => segment,
3875             None => return None,
3876         };
3877
3878         for item_id in mem::replace(&mut items, HirVec::new()).iter() {
3879             let item = tcx.hir.expect_item(item_id.id);
3880             if item.name == *segment {
3881                 if path_it.peek().is_none() {
3882                     return Some(tcx.hir.local_def_id(item_id.id))
3883                 }
3884
3885                 items = match &item.node {
3886                     &hir::ItemMod(ref m) => m.item_ids.clone(),
3887                     _ => panic!("Unexpected item {:?} in path {:?} path")
3888                 };
3889                 break;
3890             }
3891         }
3892     }
3893 }
3894
3895 pub fn path_to_def(tcx: &TyCtxt, path: &[&str]) -> Option<DefId> {
3896     let crates = tcx.crates();
3897
3898     let krate = crates
3899         .iter()
3900         .find(|&&krate| tcx.crate_name(krate) == path[0]);
3901
3902     if let Some(krate) = krate {
3903         let krate = DefId {
3904             krate: *krate,
3905             index: CRATE_DEF_INDEX,
3906         };
3907         let mut items = tcx.item_children(krate);
3908         let mut path_it = path.iter().skip(1).peekable();
3909
3910         loop {
3911             let segment = match path_it.next() {
3912                 Some(segment) => segment,
3913                 None => return None,
3914             };
3915
3916             for item in mem::replace(&mut items, Lrc::new(vec![])).iter() {
3917                 if item.ident.name == *segment {
3918                     if path_it.peek().is_none() {
3919                         return match item.def {
3920                             def::Def::Trait(did) => Some(did),
3921                             _ => None,
3922                         }
3923                     }
3924
3925                     items = tcx.item_children(item.def.def_id());
3926                     break;
3927                 }
3928             }
3929         }
3930     } else {
3931         None
3932     }
3933 }
3934
3935 fn get_path_for_type(tcx: TyCtxt, def_id: DefId, def_ctor: fn(DefId) -> Def) -> hir::Path {
3936     struct AbsolutePathBuffer {
3937         names: Vec<String>,
3938     }
3939
3940     impl ty::item_path::ItemPathBuffer for AbsolutePathBuffer {
3941         fn root_mode(&self) -> &ty::item_path::RootMode {
3942             const ABSOLUTE: &'static ty::item_path::RootMode = &ty::item_path::RootMode::Absolute;
3943             ABSOLUTE
3944         }
3945
3946         fn push(&mut self, text: &str) {
3947             self.names.push(text.to_owned());
3948         }
3949     }
3950
3951     let mut apb = AbsolutePathBuffer { names: vec![] };
3952
3953     tcx.push_item_path(&mut apb, def_id);
3954
3955     hir::Path {
3956         span: DUMMY_SP,
3957         def: def_ctor(def_id),
3958         segments: hir::HirVec::from_vec(apb.names.iter().map(|s| hir::PathSegment {
3959             name: ast::Name::intern(&s),
3960             parameters: None,
3961             infer_types: false,
3962         }).collect())
3963     }
3964 }
3965
3966 // End of code copied from rust-clippy
3967
3968
3969 #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
3970 enum RegionTarget<'tcx> {
3971     Region(Region<'tcx>),
3972     RegionVid(RegionVid)
3973 }
3974
3975 #[derive(Default, Debug, Clone)]
3976 struct RegionDeps<'tcx> {
3977     larger: FxHashSet<RegionTarget<'tcx>>,
3978     smaller: FxHashSet<RegionTarget<'tcx>>
3979 }
3980
3981 #[derive(Eq, PartialEq, Hash, Debug)]
3982 enum SimpleBound {
3983     RegionBound(Lifetime),
3984     TraitBound(Vec<PathSegment>, Vec<SimpleBound>, Vec<GenericParam>, hir::TraitBoundModifier)
3985 }
3986
3987 enum AutoTraitResult {
3988     ExplicitImpl,
3989     PositiveImpl(Generics),
3990     NegativeImpl,
3991 }
3992
3993 impl AutoTraitResult {
3994     fn is_auto(&self) -> bool {
3995         match *self {
3996             AutoTraitResult::PositiveImpl(_) | AutoTraitResult::NegativeImpl => true,
3997             _ => false,
3998         }
3999     }
4000 }
4001
4002 impl From<TyParamBound> for SimpleBound {
4003     fn from(bound: TyParamBound) -> Self {
4004         match bound.clone() {
4005             TyParamBound::RegionBound(l) => SimpleBound::RegionBound(l),
4006             TyParamBound::TraitBound(t, mod_) => match t.trait_ {
4007                 Type::ResolvedPath { path, typarams, .. } => {
4008                     SimpleBound::TraitBound(path.segments,
4009                                             typarams
4010                                                 .map_or_else(|| Vec::new(), |v| v.iter()
4011                                                         .map(|p| SimpleBound::from(p.clone()))
4012                                                         .collect()),
4013                                             t.generic_params,
4014                                             mod_)
4015                 }
4016                 _ => panic!("Unexpected bound {:?}", bound),
4017             }
4018         }
4019     }
4020 }