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