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