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::Subtype(ref pred) => pred.clean(cx),
1539             Predicate::RegionOutlives(ref pred) => pred.clean(cx),
1540             Predicate::TypeOutlives(ref pred) => pred.clean(cx),
1541             Predicate::Projection(ref pred) => pred.clean(cx),
1542             Predicate::WellFormed(_) => panic!("not user writable"),
1543             Predicate::ObjectSafe(_) => panic!("not user writable"),
1544             Predicate::ClosureKind(..) => panic!("not user writable"),
1545             Predicate::ConstEvaluatable(..) => panic!("not user writable"),
1546         }
1547     }
1548 }
1549
1550 impl<'a> Clean<WherePredicate> for ty::TraitPredicate<'a> {
1551     fn clean(&self, cx: &DocContext) -> WherePredicate {
1552         WherePredicate::BoundPredicate {
1553             ty: self.trait_ref.self_ty().clean(cx),
1554             bounds: vec![self.trait_ref.clean(cx)]
1555         }
1556     }
1557 }
1558
1559 impl<'tcx> Clean<WherePredicate> for ty::SubtypePredicate<'tcx> {
1560     fn clean(&self, _cx: &DocContext) -> WherePredicate {
1561         panic!("subtype predicates are an internal rustc artifact \
1562                 and should not be seen by rustdoc")
1563     }
1564 }
1565
1566 impl<'tcx> Clean<WherePredicate> for ty::OutlivesPredicate<ty::Region<'tcx>, ty::Region<'tcx>> {
1567     fn clean(&self, cx: &DocContext) -> WherePredicate {
1568         let ty::OutlivesPredicate(ref a, ref b) = *self;
1569         WherePredicate::RegionPredicate {
1570             lifetime: a.clean(cx).unwrap(),
1571             bounds: vec![b.clean(cx).unwrap()]
1572         }
1573     }
1574 }
1575
1576 impl<'tcx> Clean<WherePredicate> for ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>> {
1577     fn clean(&self, cx: &DocContext) -> WherePredicate {
1578         let ty::OutlivesPredicate(ref ty, ref lt) = *self;
1579
1580         WherePredicate::BoundPredicate {
1581             ty: ty.clean(cx),
1582             bounds: vec![TyParamBound::RegionBound(lt.clean(cx).unwrap())]
1583         }
1584     }
1585 }
1586
1587 impl<'tcx> Clean<WherePredicate> for ty::ProjectionPredicate<'tcx> {
1588     fn clean(&self, cx: &DocContext) -> WherePredicate {
1589         WherePredicate::EqPredicate {
1590             lhs: self.projection_ty.clean(cx),
1591             rhs: self.ty.clean(cx)
1592         }
1593     }
1594 }
1595
1596 impl<'tcx> Clean<Type> for ty::ProjectionTy<'tcx> {
1597     fn clean(&self, cx: &DocContext) -> Type {
1598         let trait_ = match self.trait_ref(cx.tcx).clean(cx) {
1599             TyParamBound::TraitBound(t, _) => t.trait_,
1600             TyParamBound::RegionBound(_) => {
1601                 panic!("cleaning a trait got a region")
1602             }
1603         };
1604         Type::QPath {
1605             name: cx.tcx.associated_item(self.item_def_id).name.clean(cx),
1606             self_type: box self.self_ty().clean(cx),
1607             trait_: box trait_
1608         }
1609     }
1610 }
1611
1612 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1613 pub enum GenericParam {
1614     Lifetime(Lifetime),
1615     Type(TyParam),
1616 }
1617
1618 impl Clean<GenericParam> for hir::GenericParam {
1619     fn clean(&self, cx: &DocContext) -> GenericParam {
1620         match *self {
1621             hir::GenericParam::Lifetime(ref l) => GenericParam::Lifetime(l.clean(cx)),
1622             hir::GenericParam::Type(ref t) => GenericParam::Type(t.clean(cx)),
1623         }
1624     }
1625 }
1626
1627 // maybe use a Generic enum and use Vec<Generic>?
1628 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Default, Hash)]
1629 pub struct Generics {
1630     pub params: Vec<GenericParam>,
1631     pub where_predicates: Vec<WherePredicate>,
1632 }
1633
1634 impl Clean<Generics> for hir::Generics {
1635     fn clean(&self, cx: &DocContext) -> Generics {
1636         let mut g = Generics {
1637             params: self.params.clean(cx),
1638             where_predicates: self.where_clause.predicates.clean(cx)
1639         };
1640
1641         // Some duplicates are generated for ?Sized bounds between type params and where
1642         // predicates. The point in here is to move the bounds definitions from type params
1643         // to where predicates when such cases occur.
1644         for where_pred in &mut g.where_predicates {
1645             match *where_pred {
1646                 WherePredicate::BoundPredicate { ty: Generic(ref name), ref mut bounds } => {
1647                     if bounds.is_empty() {
1648                         for param in &mut g.params {
1649                             if let GenericParam::Type(ref mut type_param) = *param {
1650                                 if &type_param.name == name {
1651                                     mem::swap(bounds, &mut type_param.bounds);
1652                                     break
1653                                 }
1654                             }
1655                         }
1656                     }
1657                 }
1658                 _ => continue,
1659             }
1660         }
1661         g
1662     }
1663 }
1664
1665 impl<'a, 'tcx> Clean<Generics> for (&'a ty::Generics,
1666                                     &'a ty::GenericPredicates<'tcx>) {
1667     fn clean(&self, cx: &DocContext) -> Generics {
1668         use self::WherePredicate as WP;
1669
1670         let (gens, preds) = *self;
1671
1672         // Bounds in the type_params and lifetimes fields are repeated in the
1673         // predicates field (see rustc_typeck::collect::ty_generics), so remove
1674         // them.
1675         let stripped_typarams = gens.types.iter().filter_map(|tp| {
1676             if tp.name == keywords::SelfType.name() {
1677                 assert_eq!(tp.index, 0);
1678                 None
1679             } else {
1680                 Some(tp.clean(cx))
1681             }
1682         }).collect::<Vec<_>>();
1683
1684         let mut where_predicates = preds.predicates.to_vec().clean(cx);
1685
1686         // Type parameters and have a Sized bound by default unless removed with
1687         // ?Sized. Scan through the predicates and mark any type parameter with
1688         // a Sized bound, removing the bounds as we find them.
1689         //
1690         // Note that associated types also have a sized bound by default, but we
1691         // don't actually know the set of associated types right here so that's
1692         // handled in cleaning associated types
1693         let mut sized_params = FxHashSet();
1694         where_predicates.retain(|pred| {
1695             match *pred {
1696                 WP::BoundPredicate { ty: Generic(ref g), ref bounds } => {
1697                     if bounds.iter().any(|b| b.is_sized_bound(cx)) {
1698                         sized_params.insert(g.clone());
1699                         false
1700                     } else {
1701                         true
1702                     }
1703                 }
1704                 _ => true,
1705             }
1706         });
1707
1708         // Run through the type parameters again and insert a ?Sized
1709         // unbound for any we didn't find to be Sized.
1710         for tp in &stripped_typarams {
1711             if !sized_params.contains(&tp.name) {
1712                 where_predicates.push(WP::BoundPredicate {
1713                     ty: Type::Generic(tp.name.clone()),
1714                     bounds: vec![TyParamBound::maybe_sized(cx)],
1715                 })
1716             }
1717         }
1718
1719         // It would be nice to collect all of the bounds on a type and recombine
1720         // them if possible, to avoid e.g. `where T: Foo, T: Bar, T: Sized, T: 'a`
1721         // and instead see `where T: Foo + Bar + Sized + 'a`
1722
1723         Generics {
1724             params: gens.regions
1725                 .clean(cx)
1726                 .into_iter()
1727                 .map(|lp| GenericParam::Lifetime(lp))
1728                 .chain(
1729                     simplify::ty_params(stripped_typarams)
1730                         .into_iter()
1731                         .map(|tp| GenericParam::Type(tp))
1732                 )
1733                 .collect(),
1734             where_predicates: simplify::where_clauses(cx, where_predicates),
1735         }
1736     }
1737 }
1738
1739 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1740 pub struct Method {
1741     pub generics: Generics,
1742     pub unsafety: hir::Unsafety,
1743     pub constness: hir::Constness,
1744     pub decl: FnDecl,
1745     pub abi: Abi,
1746 }
1747
1748 impl<'a> Clean<Method> for (&'a hir::MethodSig, &'a hir::Generics, hir::BodyId) {
1749     fn clean(&self, cx: &DocContext) -> Method {
1750         Method {
1751             generics: self.1.clean(cx),
1752             unsafety: self.0.unsafety,
1753             constness: self.0.constness,
1754             decl: (&*self.0.decl, self.2).clean(cx),
1755             abi: self.0.abi
1756         }
1757     }
1758 }
1759
1760 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1761 pub struct TyMethod {
1762     pub unsafety: hir::Unsafety,
1763     pub decl: FnDecl,
1764     pub generics: Generics,
1765     pub abi: Abi,
1766 }
1767
1768 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1769 pub struct Function {
1770     pub decl: FnDecl,
1771     pub generics: Generics,
1772     pub unsafety: hir::Unsafety,
1773     pub constness: hir::Constness,
1774     pub abi: Abi,
1775 }
1776
1777 impl Clean<Item> for doctree::Function {
1778     fn clean(&self, cx: &DocContext) -> Item {
1779         Item {
1780             name: Some(self.name.clean(cx)),
1781             attrs: self.attrs.clean(cx),
1782             source: self.whence.clean(cx),
1783             visibility: self.vis.clean(cx),
1784             stability: self.stab.clean(cx),
1785             deprecation: self.depr.clean(cx),
1786             def_id: cx.tcx.hir.local_def_id(self.id),
1787             inner: FunctionItem(Function {
1788                 decl: (&self.decl, self.body).clean(cx),
1789                 generics: self.generics.clean(cx),
1790                 unsafety: self.unsafety,
1791                 constness: self.constness,
1792                 abi: self.abi,
1793             }),
1794         }
1795     }
1796 }
1797
1798 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1799 pub struct FnDecl {
1800     pub inputs: Arguments,
1801     pub output: FunctionRetTy,
1802     pub variadic: bool,
1803     pub attrs: Attributes,
1804 }
1805
1806 impl FnDecl {
1807     pub fn has_self(&self) -> bool {
1808         self.inputs.values.len() > 0 && self.inputs.values[0].name == "self"
1809     }
1810
1811     pub fn self_type(&self) -> Option<SelfTy> {
1812         self.inputs.values.get(0).and_then(|v| v.to_self())
1813     }
1814 }
1815
1816 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1817 pub struct Arguments {
1818     pub values: Vec<Argument>,
1819 }
1820
1821 impl<'a> Clean<Arguments> for (&'a [P<hir::Ty>], &'a [Spanned<ast::Name>]) {
1822     fn clean(&self, cx: &DocContext) -> Arguments {
1823         Arguments {
1824             values: self.0.iter().enumerate().map(|(i, ty)| {
1825                 let mut name = self.1.get(i).map(|n| n.node.to_string())
1826                                             .unwrap_or(String::new());
1827                 if name.is_empty() {
1828                     name = "_".to_string();
1829                 }
1830                 Argument {
1831                     name,
1832                     type_: ty.clean(cx),
1833                 }
1834             }).collect()
1835         }
1836     }
1837 }
1838
1839 impl<'a> Clean<Arguments> for (&'a [P<hir::Ty>], hir::BodyId) {
1840     fn clean(&self, cx: &DocContext) -> Arguments {
1841         let body = cx.tcx.hir.body(self.1);
1842
1843         Arguments {
1844             values: self.0.iter().enumerate().map(|(i, ty)| {
1845                 Argument {
1846                     name: name_from_pat(&body.arguments[i].pat),
1847                     type_: ty.clean(cx),
1848                 }
1849             }).collect()
1850         }
1851     }
1852 }
1853
1854 impl<'a, A: Copy> Clean<FnDecl> for (&'a hir::FnDecl, A)
1855     where (&'a [P<hir::Ty>], A): Clean<Arguments>
1856 {
1857     fn clean(&self, cx: &DocContext) -> FnDecl {
1858         FnDecl {
1859             inputs: (&self.0.inputs[..], self.1).clean(cx),
1860             output: self.0.output.clean(cx),
1861             variadic: self.0.variadic,
1862             attrs: Attributes::default()
1863         }
1864     }
1865 }
1866
1867 impl<'a, 'tcx> Clean<FnDecl> for (DefId, ty::PolyFnSig<'tcx>) {
1868     fn clean(&self, cx: &DocContext) -> FnDecl {
1869         let (did, sig) = *self;
1870         let mut names = if cx.tcx.hir.as_local_node_id(did).is_some() {
1871             vec![].into_iter()
1872         } else {
1873             cx.tcx.fn_arg_names(did).into_iter()
1874         }.peekable();
1875         FnDecl {
1876             output: Return(sig.skip_binder().output().clean(cx)),
1877             attrs: Attributes::default(),
1878             variadic: sig.skip_binder().variadic,
1879             inputs: Arguments {
1880                 values: sig.skip_binder().inputs().iter().map(|t| {
1881                     Argument {
1882                         type_: t.clean(cx),
1883                         name: names.next().map_or("".to_string(), |name| name.to_string()),
1884                     }
1885                 }).collect(),
1886             },
1887         }
1888     }
1889 }
1890
1891 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1892 pub struct Argument {
1893     pub type_: Type,
1894     pub name: String,
1895 }
1896
1897 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1898 pub enum SelfTy {
1899     SelfValue,
1900     SelfBorrowed(Option<Lifetime>, Mutability),
1901     SelfExplicit(Type),
1902 }
1903
1904 impl Argument {
1905     pub fn to_self(&self) -> Option<SelfTy> {
1906         if self.name != "self" {
1907             return None;
1908         }
1909         if self.type_.is_self_type() {
1910             return Some(SelfValue);
1911         }
1912         match self.type_ {
1913             BorrowedRef{ref lifetime, mutability, ref type_} if type_.is_self_type() => {
1914                 Some(SelfBorrowed(lifetime.clone(), mutability))
1915             }
1916             _ => Some(SelfExplicit(self.type_.clone()))
1917         }
1918     }
1919 }
1920
1921 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1922 pub enum FunctionRetTy {
1923     Return(Type),
1924     DefaultReturn,
1925 }
1926
1927 impl Clean<FunctionRetTy> for hir::FunctionRetTy {
1928     fn clean(&self, cx: &DocContext) -> FunctionRetTy {
1929         match *self {
1930             hir::Return(ref typ) => Return(typ.clean(cx)),
1931             hir::DefaultReturn(..) => DefaultReturn,
1932         }
1933     }
1934 }
1935
1936 impl GetDefId for FunctionRetTy {
1937     fn def_id(&self) -> Option<DefId> {
1938         match *self {
1939             Return(ref ty) => ty.def_id(),
1940             DefaultReturn => None,
1941         }
1942     }
1943 }
1944
1945 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1946 pub struct Trait {
1947     pub auto: bool,
1948     pub unsafety: hir::Unsafety,
1949     pub items: Vec<Item>,
1950     pub generics: Generics,
1951     pub bounds: Vec<TyParamBound>,
1952     pub is_spotlight: bool,
1953     pub is_auto: bool,
1954 }
1955
1956 impl Clean<Item> for doctree::Trait {
1957     fn clean(&self, cx: &DocContext) -> Item {
1958         let attrs = self.attrs.clean(cx);
1959         let is_spotlight = attrs.has_doc_flag("spotlight");
1960         Item {
1961             name: Some(self.name.clean(cx)),
1962             attrs: attrs,
1963             source: self.whence.clean(cx),
1964             def_id: cx.tcx.hir.local_def_id(self.id),
1965             visibility: self.vis.clean(cx),
1966             stability: self.stab.clean(cx),
1967             deprecation: self.depr.clean(cx),
1968             inner: TraitItem(Trait {
1969                 auto: self.is_auto.clean(cx),
1970                 unsafety: self.unsafety,
1971                 items: self.items.clean(cx),
1972                 generics: self.generics.clean(cx),
1973                 bounds: self.bounds.clean(cx),
1974                 is_spotlight: is_spotlight,
1975                 is_auto: self.is_auto.clean(cx),
1976             }),
1977         }
1978     }
1979 }
1980
1981 impl Clean<bool> for hir::IsAuto {
1982     fn clean(&self, _: &DocContext) -> bool {
1983         match *self {
1984             hir::IsAuto::Yes => true,
1985             hir::IsAuto::No => false,
1986         }
1987     }
1988 }
1989
1990 impl Clean<Type> for hir::TraitRef {
1991     fn clean(&self, cx: &DocContext) -> Type {
1992         resolve_type(cx, self.path.clean(cx), self.ref_id)
1993     }
1994 }
1995
1996 impl Clean<PolyTrait> for hir::PolyTraitRef {
1997     fn clean(&self, cx: &DocContext) -> PolyTrait {
1998         PolyTrait {
1999             trait_: self.trait_ref.clean(cx),
2000             generic_params: self.bound_generic_params.clean(cx)
2001         }
2002     }
2003 }
2004
2005 impl Clean<Item> for hir::TraitItem {
2006     fn clean(&self, cx: &DocContext) -> Item {
2007         let inner = match self.node {
2008             hir::TraitItemKind::Const(ref ty, default) => {
2009                 AssociatedConstItem(ty.clean(cx),
2010                                     default.map(|e| print_const_expr(cx, e)))
2011             }
2012             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Provided(body)) => {
2013                 MethodItem((sig, &self.generics, body).clean(cx))
2014             }
2015             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Required(ref names)) => {
2016                 TyMethodItem(TyMethod {
2017                     unsafety: sig.unsafety.clone(),
2018                     decl: (&*sig.decl, &names[..]).clean(cx),
2019                     generics: self.generics.clean(cx),
2020                     abi: sig.abi
2021                 })
2022             }
2023             hir::TraitItemKind::Type(ref bounds, ref default) => {
2024                 AssociatedTypeItem(bounds.clean(cx), default.clean(cx))
2025             }
2026         };
2027         Item {
2028             name: Some(self.name.clean(cx)),
2029             attrs: self.attrs.clean(cx),
2030             source: self.span.clean(cx),
2031             def_id: cx.tcx.hir.local_def_id(self.id),
2032             visibility: None,
2033             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2034             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2035             inner,
2036         }
2037     }
2038 }
2039
2040 impl Clean<Item> for hir::ImplItem {
2041     fn clean(&self, cx: &DocContext) -> Item {
2042         let inner = match self.node {
2043             hir::ImplItemKind::Const(ref ty, expr) => {
2044                 AssociatedConstItem(ty.clean(cx),
2045                                     Some(print_const_expr(cx, expr)))
2046             }
2047             hir::ImplItemKind::Method(ref sig, body) => {
2048                 MethodItem((sig, &self.generics, body).clean(cx))
2049             }
2050             hir::ImplItemKind::Type(ref ty) => TypedefItem(Typedef {
2051                 type_: ty.clean(cx),
2052                 generics: Generics::default(),
2053             }, true),
2054         };
2055         Item {
2056             name: Some(self.name.clean(cx)),
2057             source: self.span.clean(cx),
2058             attrs: self.attrs.clean(cx),
2059             def_id: cx.tcx.hir.local_def_id(self.id),
2060             visibility: self.vis.clean(cx),
2061             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2062             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2063             inner,
2064         }
2065     }
2066 }
2067
2068 impl<'tcx> Clean<Item> for ty::AssociatedItem {
2069     fn clean(&self, cx: &DocContext) -> Item {
2070         let inner = match self.kind {
2071             ty::AssociatedKind::Const => {
2072                 let ty = cx.tcx.type_of(self.def_id);
2073                 let default = if self.defaultness.has_value() {
2074                     Some(inline::print_inlined_const(cx, self.def_id))
2075                 } else {
2076                     None
2077                 };
2078                 AssociatedConstItem(ty.clean(cx), default)
2079             }
2080             ty::AssociatedKind::Method => {
2081                 let generics = (cx.tcx.generics_of(self.def_id),
2082                                 &cx.tcx.predicates_of(self.def_id)).clean(cx);
2083                 let sig = cx.tcx.fn_sig(self.def_id);
2084                 let mut decl = (self.def_id, sig).clean(cx);
2085
2086                 if self.method_has_self_argument {
2087                     let self_ty = match self.container {
2088                         ty::ImplContainer(def_id) => {
2089                             cx.tcx.type_of(def_id)
2090                         }
2091                         ty::TraitContainer(_) => cx.tcx.mk_self_type()
2092                     };
2093                     let self_arg_ty = *sig.input(0).skip_binder();
2094                     if self_arg_ty == self_ty {
2095                         decl.inputs.values[0].type_ = Generic(String::from("Self"));
2096                     } else if let ty::TyRef(_, mt) = self_arg_ty.sty {
2097                         if mt.ty == self_ty {
2098                             match decl.inputs.values[0].type_ {
2099                                 BorrowedRef{ref mut type_, ..} => {
2100                                     **type_ = Generic(String::from("Self"))
2101                                 }
2102                                 _ => unreachable!(),
2103                             }
2104                         }
2105                     }
2106                 }
2107
2108                 let provided = match self.container {
2109                     ty::ImplContainer(_) => true,
2110                     ty::TraitContainer(_) => self.defaultness.has_value()
2111                 };
2112                 if provided {
2113                     let constness = if cx.tcx.is_const_fn(self.def_id) {
2114                         hir::Constness::Const
2115                     } else {
2116                         hir::Constness::NotConst
2117                     };
2118                     MethodItem(Method {
2119                         unsafety: sig.unsafety(),
2120                         generics,
2121                         decl,
2122                         abi: sig.abi(),
2123                         constness,
2124                     })
2125                 } else {
2126                     TyMethodItem(TyMethod {
2127                         unsafety: sig.unsafety(),
2128                         generics,
2129                         decl,
2130                         abi: sig.abi(),
2131                     })
2132                 }
2133             }
2134             ty::AssociatedKind::Type => {
2135                 let my_name = self.name.clean(cx);
2136
2137                 if let ty::TraitContainer(did) = self.container {
2138                     // When loading a cross-crate associated type, the bounds for this type
2139                     // are actually located on the trait/impl itself, so we need to load
2140                     // all of the generics from there and then look for bounds that are
2141                     // applied to this associated type in question.
2142                     let predicates = cx.tcx.predicates_of(did);
2143                     let generics = (cx.tcx.generics_of(did), &predicates).clean(cx);
2144                     let mut bounds = generics.where_predicates.iter().filter_map(|pred| {
2145                         let (name, self_type, trait_, bounds) = match *pred {
2146                             WherePredicate::BoundPredicate {
2147                                 ty: QPath { ref name, ref self_type, ref trait_ },
2148                                 ref bounds
2149                             } => (name, self_type, trait_, bounds),
2150                             _ => return None,
2151                         };
2152                         if *name != my_name { return None }
2153                         match **trait_ {
2154                             ResolvedPath { did, .. } if did == self.container.id() => {}
2155                             _ => return None,
2156                         }
2157                         match **self_type {
2158                             Generic(ref s) if *s == "Self" => {}
2159                             _ => return None,
2160                         }
2161                         Some(bounds)
2162                     }).flat_map(|i| i.iter().cloned()).collect::<Vec<_>>();
2163                     // Our Sized/?Sized bound didn't get handled when creating the generics
2164                     // because we didn't actually get our whole set of bounds until just now
2165                     // (some of them may have come from the trait). If we do have a sized
2166                     // bound, we remove it, and if we don't then we add the `?Sized` bound
2167                     // at the end.
2168                     match bounds.iter().position(|b| b.is_sized_bound(cx)) {
2169                         Some(i) => { bounds.remove(i); }
2170                         None => bounds.push(TyParamBound::maybe_sized(cx)),
2171                     }
2172
2173                     let ty = if self.defaultness.has_value() {
2174                         Some(cx.tcx.type_of(self.def_id))
2175                     } else {
2176                         None
2177                     };
2178
2179                     AssociatedTypeItem(bounds, ty.clean(cx))
2180                 } else {
2181                     TypedefItem(Typedef {
2182                         type_: cx.tcx.type_of(self.def_id).clean(cx),
2183                         generics: Generics {
2184                             params: Vec::new(),
2185                             where_predicates: Vec::new(),
2186                         },
2187                     }, true)
2188                 }
2189             }
2190         };
2191
2192         let visibility = match self.container {
2193             ty::ImplContainer(_) => self.vis.clean(cx),
2194             ty::TraitContainer(_) => None,
2195         };
2196
2197         Item {
2198             name: Some(self.name.clean(cx)),
2199             visibility,
2200             stability: get_stability(cx, self.def_id),
2201             deprecation: get_deprecation(cx, self.def_id),
2202             def_id: self.def_id,
2203             attrs: inline::load_attrs(cx, self.def_id),
2204             source: cx.tcx.def_span(self.def_id).clean(cx),
2205             inner,
2206         }
2207     }
2208 }
2209
2210 /// A trait reference, which may have higher ranked lifetimes.
2211 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2212 pub struct PolyTrait {
2213     pub trait_: Type,
2214     pub generic_params: Vec<GenericParam>,
2215 }
2216
2217 /// A representation of a Type suitable for hyperlinking purposes. Ideally one can get the original
2218 /// type out of the AST/TyCtxt given one of these, if more information is needed. Most importantly
2219 /// it does not preserve mutability or boxes.
2220 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2221 pub enum Type {
2222     /// structs/enums/traits (most that'd be an hir::TyPath)
2223     ResolvedPath {
2224         path: Path,
2225         typarams: Option<Vec<TyParamBound>>,
2226         did: DefId,
2227         /// true if is a `T::Name` path for associated types
2228         is_generic: bool,
2229     },
2230     /// For parameterized types, so the consumer of the JSON don't go
2231     /// looking for types which don't exist anywhere.
2232     Generic(String),
2233     /// Primitives are the fixed-size numeric types (plus int/usize/float), char,
2234     /// arrays, slices, and tuples.
2235     Primitive(PrimitiveType),
2236     /// extern "ABI" fn
2237     BareFunction(Box<BareFunctionDecl>),
2238     Tuple(Vec<Type>),
2239     Slice(Box<Type>),
2240     Array(Box<Type>, String),
2241     Never,
2242     Unique(Box<Type>),
2243     RawPointer(Mutability, Box<Type>),
2244     BorrowedRef {
2245         lifetime: Option<Lifetime>,
2246         mutability: Mutability,
2247         type_: Box<Type>,
2248     },
2249
2250     // <Type as Trait>::Name
2251     QPath {
2252         name: String,
2253         self_type: Box<Type>,
2254         trait_: Box<Type>
2255     },
2256
2257     // _
2258     Infer,
2259
2260     // impl TraitA+TraitB
2261     ImplTrait(Vec<TyParamBound>),
2262 }
2263
2264 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Copy, Debug)]
2265 pub enum PrimitiveType {
2266     Isize, I8, I16, I32, I64, I128,
2267     Usize, U8, U16, U32, U64, U128,
2268     F32, F64,
2269     Char,
2270     Bool,
2271     Str,
2272     Slice,
2273     Array,
2274     Tuple,
2275     Unit,
2276     RawPointer,
2277     Reference,
2278     Fn,
2279     Never,
2280 }
2281
2282 #[derive(Clone, RustcEncodable, RustcDecodable, Copy, Debug)]
2283 pub enum TypeKind {
2284     Enum,
2285     Function,
2286     Module,
2287     Const,
2288     Static,
2289     Struct,
2290     Union,
2291     Trait,
2292     Variant,
2293     Typedef,
2294     Foreign,
2295     Macro,
2296 }
2297
2298 pub trait GetDefId {
2299     fn def_id(&self) -> Option<DefId>;
2300 }
2301
2302 impl<T: GetDefId> GetDefId for Option<T> {
2303     fn def_id(&self) -> Option<DefId> {
2304         self.as_ref().and_then(|d| d.def_id())
2305     }
2306 }
2307
2308 impl Type {
2309     pub fn primitive_type(&self) -> Option<PrimitiveType> {
2310         match *self {
2311             Primitive(p) | BorrowedRef { type_: box Primitive(p), ..} => Some(p),
2312             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
2313             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
2314             Tuple(ref tys) => if tys.is_empty() {
2315                 Some(PrimitiveType::Unit)
2316             } else {
2317                 Some(PrimitiveType::Tuple)
2318             },
2319             RawPointer(..) => Some(PrimitiveType::RawPointer),
2320             BorrowedRef { type_: box Generic(..), .. } => Some(PrimitiveType::Reference),
2321             BareFunction(..) => Some(PrimitiveType::Fn),
2322             Never => Some(PrimitiveType::Never),
2323             _ => None,
2324         }
2325     }
2326
2327     pub fn is_generic(&self) -> bool {
2328         match *self {
2329             ResolvedPath { is_generic, .. } => is_generic,
2330             _ => false,
2331         }
2332     }
2333
2334     pub fn is_self_type(&self) -> bool {
2335         match *self {
2336             Generic(ref name) => name == "Self",
2337             _ => false
2338         }
2339     }
2340
2341     pub fn generics(&self) -> Option<&[Type]> {
2342         match *self {
2343             ResolvedPath { ref path, .. } => {
2344                 path.segments.last().and_then(|seg| {
2345                     if let PathParameters::AngleBracketed { ref types, .. } = seg.params {
2346                         Some(&**types)
2347                     } else {
2348                         None
2349                     }
2350                 })
2351             }
2352             _ => None,
2353         }
2354     }
2355 }
2356
2357 impl GetDefId for Type {
2358     fn def_id(&self) -> Option<DefId> {
2359         match *self {
2360             ResolvedPath { did, .. } => Some(did),
2361             Primitive(p) => ::html::render::cache().primitive_locations.get(&p).cloned(),
2362             BorrowedRef { type_: box Generic(..), .. } =>
2363                 Primitive(PrimitiveType::Reference).def_id(),
2364             BorrowedRef { ref type_, .. } => type_.def_id(),
2365             Tuple(ref tys) => if tys.is_empty() {
2366                 Primitive(PrimitiveType::Unit).def_id()
2367             } else {
2368                 Primitive(PrimitiveType::Tuple).def_id()
2369             },
2370             BareFunction(..) => Primitive(PrimitiveType::Fn).def_id(),
2371             Never => Primitive(PrimitiveType::Never).def_id(),
2372             Slice(..) => Primitive(PrimitiveType::Slice).def_id(),
2373             Array(..) => Primitive(PrimitiveType::Array).def_id(),
2374             RawPointer(..) => Primitive(PrimitiveType::RawPointer).def_id(),
2375             QPath { ref self_type, .. } => self_type.def_id(),
2376             _ => None,
2377         }
2378     }
2379 }
2380
2381 impl PrimitiveType {
2382     fn from_str(s: &str) -> Option<PrimitiveType> {
2383         match s {
2384             "isize" => Some(PrimitiveType::Isize),
2385             "i8" => Some(PrimitiveType::I8),
2386             "i16" => Some(PrimitiveType::I16),
2387             "i32" => Some(PrimitiveType::I32),
2388             "i64" => Some(PrimitiveType::I64),
2389             "i128" => Some(PrimitiveType::I128),
2390             "usize" => Some(PrimitiveType::Usize),
2391             "u8" => Some(PrimitiveType::U8),
2392             "u16" => Some(PrimitiveType::U16),
2393             "u32" => Some(PrimitiveType::U32),
2394             "u64" => Some(PrimitiveType::U64),
2395             "u128" => Some(PrimitiveType::U128),
2396             "bool" => Some(PrimitiveType::Bool),
2397             "char" => Some(PrimitiveType::Char),
2398             "str" => Some(PrimitiveType::Str),
2399             "f32" => Some(PrimitiveType::F32),
2400             "f64" => Some(PrimitiveType::F64),
2401             "array" => Some(PrimitiveType::Array),
2402             "slice" => Some(PrimitiveType::Slice),
2403             "tuple" => Some(PrimitiveType::Tuple),
2404             "unit" => Some(PrimitiveType::Unit),
2405             "pointer" => Some(PrimitiveType::RawPointer),
2406             "reference" => Some(PrimitiveType::Reference),
2407             "fn" => Some(PrimitiveType::Fn),
2408             "never" => Some(PrimitiveType::Never),
2409             _ => None,
2410         }
2411     }
2412
2413     pub fn as_str(&self) -> &'static str {
2414         use self::PrimitiveType::*;
2415         match *self {
2416             Isize => "isize",
2417             I8 => "i8",
2418             I16 => "i16",
2419             I32 => "i32",
2420             I64 => "i64",
2421             I128 => "i128",
2422             Usize => "usize",
2423             U8 => "u8",
2424             U16 => "u16",
2425             U32 => "u32",
2426             U64 => "u64",
2427             U128 => "u128",
2428             F32 => "f32",
2429             F64 => "f64",
2430             Str => "str",
2431             Bool => "bool",
2432             Char => "char",
2433             Array => "array",
2434             Slice => "slice",
2435             Tuple => "tuple",
2436             Unit => "unit",
2437             RawPointer => "pointer",
2438             Reference => "reference",
2439             Fn => "fn",
2440             Never => "never",
2441         }
2442     }
2443
2444     pub fn to_url_str(&self) -> &'static str {
2445         self.as_str()
2446     }
2447 }
2448
2449 impl From<ast::IntTy> for PrimitiveType {
2450     fn from(int_ty: ast::IntTy) -> PrimitiveType {
2451         match int_ty {
2452             ast::IntTy::Isize => PrimitiveType::Isize,
2453             ast::IntTy::I8 => PrimitiveType::I8,
2454             ast::IntTy::I16 => PrimitiveType::I16,
2455             ast::IntTy::I32 => PrimitiveType::I32,
2456             ast::IntTy::I64 => PrimitiveType::I64,
2457             ast::IntTy::I128 => PrimitiveType::I128,
2458         }
2459     }
2460 }
2461
2462 impl From<ast::UintTy> for PrimitiveType {
2463     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
2464         match uint_ty {
2465             ast::UintTy::Usize => PrimitiveType::Usize,
2466             ast::UintTy::U8 => PrimitiveType::U8,
2467             ast::UintTy::U16 => PrimitiveType::U16,
2468             ast::UintTy::U32 => PrimitiveType::U32,
2469             ast::UintTy::U64 => PrimitiveType::U64,
2470             ast::UintTy::U128 => PrimitiveType::U128,
2471         }
2472     }
2473 }
2474
2475 impl From<ast::FloatTy> for PrimitiveType {
2476     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
2477         match float_ty {
2478             ast::FloatTy::F32 => PrimitiveType::F32,
2479             ast::FloatTy::F64 => PrimitiveType::F64,
2480         }
2481     }
2482 }
2483
2484 impl Clean<Type> for hir::Ty {
2485     fn clean(&self, cx: &DocContext) -> Type {
2486         use rustc::hir::*;
2487         match self.node {
2488             TyNever => Never,
2489             TyPtr(ref m) => RawPointer(m.mutbl.clean(cx), box m.ty.clean(cx)),
2490             TyRptr(ref l, ref m) => {
2491                 let lifetime = if l.is_elided() {
2492                     None
2493                 } else {
2494                     Some(l.clean(cx))
2495                 };
2496                 BorrowedRef {lifetime: lifetime, mutability: m.mutbl.clean(cx),
2497                              type_: box m.ty.clean(cx)}
2498             }
2499             TySlice(ref ty) => Slice(box ty.clean(cx)),
2500             TyArray(ref ty, n) => {
2501                 let def_id = cx.tcx.hir.body_owner_def_id(n);
2502                 let param_env = cx.tcx.param_env(def_id);
2503                 let substs = Substs::identity_for_item(cx.tcx, def_id);
2504                 let n = cx.tcx.const_eval(param_env.and((def_id, substs))).unwrap_or_else(|_| {
2505                     cx.tcx.mk_const(ty::Const {
2506                         val: ConstVal::Unevaluated(def_id, substs),
2507                         ty: cx.tcx.types.usize
2508                     })
2509                 });
2510                 let n = if let ConstVal::Integral(ConstInt::Usize(n)) = n.val {
2511                     n.to_string()
2512                 } else if let ConstVal::Unevaluated(def_id, _) = n.val {
2513                     if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
2514                         print_const_expr(cx, cx.tcx.hir.body_owned_by(node_id))
2515                     } else {
2516                         inline::print_inlined_const(cx, def_id)
2517                     }
2518                 } else {
2519                     format!("{:?}", n)
2520                 };
2521                 Array(box ty.clean(cx), n)
2522             },
2523             TyTup(ref tys) => Tuple(tys.clean(cx)),
2524             TyPath(hir::QPath::Resolved(None, ref path)) => {
2525                 if let Some(new_ty) = cx.ty_substs.borrow().get(&path.def).cloned() {
2526                     return new_ty;
2527                 }
2528
2529                 let mut alias = None;
2530                 if let Def::TyAlias(def_id) = path.def {
2531                     // Substitute private type aliases
2532                     if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
2533                         if !cx.access_levels.borrow().is_exported(def_id) {
2534                             alias = Some(&cx.tcx.hir.expect_item(node_id).node);
2535                         }
2536                     }
2537                 };
2538
2539                 if let Some(&hir::ItemTy(ref ty, ref generics)) = alias {
2540                     let provided_params = &path.segments.last().unwrap();
2541                     let mut ty_substs = FxHashMap();
2542                     let mut lt_substs = FxHashMap();
2543                     provided_params.with_parameters(|provided_params| {
2544                         for (i, ty_param) in generics.ty_params().enumerate() {
2545                             let ty_param_def = Def::TyParam(cx.tcx.hir.local_def_id(ty_param.id));
2546                             if let Some(ty) = provided_params.types.get(i).cloned() {
2547                                 ty_substs.insert(ty_param_def, ty.into_inner().clean(cx));
2548                             } else if let Some(default) = ty_param.default.clone() {
2549                                 ty_substs.insert(ty_param_def, default.into_inner().clean(cx));
2550                             }
2551                         }
2552
2553                         for (i, lt_param) in generics.lifetimes().enumerate() {
2554                             if let Some(lt) = provided_params.lifetimes.get(i).cloned() {
2555                                 if !lt.is_elided() {
2556                                     let lt_def_id = cx.tcx.hir.local_def_id(lt_param.lifetime.id);
2557                                     lt_substs.insert(lt_def_id, lt.clean(cx));
2558                                 }
2559                             }
2560                         }
2561                     });
2562                     return cx.enter_alias(ty_substs, lt_substs, || ty.clean(cx));
2563                 }
2564                 resolve_type(cx, path.clean(cx), self.id)
2565             }
2566             TyPath(hir::QPath::Resolved(Some(ref qself), ref p)) => {
2567                 let mut segments: Vec<_> = p.segments.clone().into();
2568                 segments.pop();
2569                 let trait_path = hir::Path {
2570                     span: p.span,
2571                     def: Def::Trait(cx.tcx.associated_item(p.def.def_id()).container.id()),
2572                     segments: segments.into(),
2573                 };
2574                 Type::QPath {
2575                     name: p.segments.last().unwrap().name.clean(cx),
2576                     self_type: box qself.clean(cx),
2577                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
2578                 }
2579             }
2580             TyPath(hir::QPath::TypeRelative(ref qself, ref segment)) => {
2581                 let mut def = Def::Err;
2582                 let ty = hir_ty_to_ty(cx.tcx, self);
2583                 if let ty::TyProjection(proj) = ty.sty {
2584                     def = Def::Trait(proj.trait_ref(cx.tcx).def_id);
2585                 }
2586                 let trait_path = hir::Path {
2587                     span: self.span,
2588                     def,
2589                     segments: vec![].into(),
2590                 };
2591                 Type::QPath {
2592                     name: segment.name.clean(cx),
2593                     self_type: box qself.clean(cx),
2594                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
2595                 }
2596             }
2597             TyTraitObject(ref bounds, ref lifetime) => {
2598                 match bounds[0].clean(cx).trait_ {
2599                     ResolvedPath { path, typarams: None, did, is_generic } => {
2600                         let mut bounds: Vec<_> = bounds[1..].iter().map(|bound| {
2601                             TraitBound(bound.clean(cx), hir::TraitBoundModifier::None)
2602                         }).collect();
2603                         if !lifetime.is_elided() {
2604                             bounds.push(RegionBound(lifetime.clean(cx)));
2605                         }
2606                         ResolvedPath {
2607                             path,
2608                             typarams: Some(bounds),
2609                             did,
2610                             is_generic,
2611                         }
2612                     }
2613                     _ => Infer // shouldn't happen
2614                 }
2615             }
2616             TyBareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
2617             TyImplTraitExistential(ref exist_ty, ref _lts) => ImplTrait(exist_ty.bounds.clean(cx)),
2618             TyInfer | TyErr => Infer,
2619             TyTypeof(..) => panic!("Unimplemented type {:?}", self.node),
2620         }
2621     }
2622 }
2623
2624 impl<'tcx> Clean<Type> for Ty<'tcx> {
2625     fn clean(&self, cx: &DocContext) -> Type {
2626         match self.sty {
2627             ty::TyNever => Never,
2628             ty::TyBool => Primitive(PrimitiveType::Bool),
2629             ty::TyChar => Primitive(PrimitiveType::Char),
2630             ty::TyInt(int_ty) => Primitive(int_ty.into()),
2631             ty::TyUint(uint_ty) => Primitive(uint_ty.into()),
2632             ty::TyFloat(float_ty) => Primitive(float_ty.into()),
2633             ty::TyStr => Primitive(PrimitiveType::Str),
2634             ty::TySlice(ty) => Slice(box ty.clean(cx)),
2635             ty::TyArray(ty, n) => {
2636                 let mut n = cx.tcx.lift(&n).unwrap();
2637                 if let ConstVal::Unevaluated(def_id, substs) = n.val {
2638                     let param_env = cx.tcx.param_env(def_id);
2639                     if let Ok(new_n) = cx.tcx.const_eval(param_env.and((def_id, substs))) {
2640                         n = new_n;
2641                     }
2642                 };
2643                 let n = if let ConstVal::Integral(ConstInt::Usize(n)) = n.val {
2644                     n.to_string()
2645                 } else if let ConstVal::Unevaluated(def_id, _) = n.val {
2646                     if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
2647                         print_const_expr(cx, cx.tcx.hir.body_owned_by(node_id))
2648                     } else {
2649                         inline::print_inlined_const(cx, def_id)
2650                     }
2651                 } else {
2652                     format!("{:?}", n)
2653                 };
2654                 Array(box ty.clean(cx), n)
2655             }
2656             ty::TyRawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
2657             ty::TyRef(r, mt) => BorrowedRef {
2658                 lifetime: r.clean(cx),
2659                 mutability: mt.mutbl.clean(cx),
2660                 type_: box mt.ty.clean(cx),
2661             },
2662             ty::TyFnDef(..) |
2663             ty::TyFnPtr(_) => {
2664                 let ty = cx.tcx.lift(self).unwrap();
2665                 let sig = ty.fn_sig(cx.tcx);
2666                 BareFunction(box BareFunctionDecl {
2667                     unsafety: sig.unsafety(),
2668                     generic_params: Vec::new(),
2669                     decl: (cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID), sig).clean(cx),
2670                     abi: sig.abi(),
2671                 })
2672             }
2673             ty::TyAdt(def, substs) => {
2674                 let did = def.did;
2675                 let kind = match def.adt_kind() {
2676                     AdtKind::Struct => TypeKind::Struct,
2677                     AdtKind::Union => TypeKind::Union,
2678                     AdtKind::Enum => TypeKind::Enum,
2679                 };
2680                 inline::record_extern_fqn(cx, did, kind);
2681                 let path = external_path(cx, &cx.tcx.item_name(did),
2682                                          None, false, vec![], substs);
2683                 ResolvedPath {
2684                     path,
2685                     typarams: None,
2686                     did,
2687                     is_generic: false,
2688                 }
2689             }
2690             ty::TyForeign(did) => {
2691                 inline::record_extern_fqn(cx, did, TypeKind::Foreign);
2692                 let path = external_path(cx, &cx.tcx.item_name(did),
2693                                          None, false, vec![], Substs::empty());
2694                 ResolvedPath {
2695                     path: path,
2696                     typarams: None,
2697                     did: did,
2698                     is_generic: false,
2699                 }
2700             }
2701             ty::TyDynamic(ref obj, ref reg) => {
2702                 if let Some(principal) = obj.principal() {
2703                     let did = principal.def_id();
2704                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
2705
2706                     let mut typarams = vec![];
2707                     reg.clean(cx).map(|b| typarams.push(RegionBound(b)));
2708                     for did in obj.auto_traits() {
2709                         let empty = cx.tcx.intern_substs(&[]);
2710                         let path = external_path(cx, &cx.tcx.item_name(did),
2711                             Some(did), false, vec![], empty);
2712                         inline::record_extern_fqn(cx, did, TypeKind::Trait);
2713                         let bound = TraitBound(PolyTrait {
2714                             trait_: ResolvedPath {
2715                                 path,
2716                                 typarams: None,
2717                                 did,
2718                                 is_generic: false,
2719                             },
2720                             generic_params: Vec::new(),
2721                         }, hir::TraitBoundModifier::None);
2722                         typarams.push(bound);
2723                     }
2724
2725                     let mut bindings = vec![];
2726                     for ty::Binder(ref pb) in obj.projection_bounds() {
2727                         bindings.push(TypeBinding {
2728                             name: cx.tcx.associated_item(pb.item_def_id).name.clean(cx),
2729                             ty: pb.ty.clean(cx)
2730                         });
2731                     }
2732
2733                     let path = external_path(cx, &cx.tcx.item_name(did), Some(did),
2734                         false, bindings, principal.0.substs);
2735                     ResolvedPath {
2736                         path,
2737                         typarams: Some(typarams),
2738                         did,
2739                         is_generic: false,
2740                     }
2741                 } else {
2742                     Never
2743                 }
2744             }
2745             ty::TyTuple(ref t, _) => Tuple(t.clean(cx)),
2746
2747             ty::TyProjection(ref data) => data.clean(cx),
2748
2749             ty::TyParam(ref p) => Generic(p.name.to_string()),
2750
2751             ty::TyAnon(def_id, substs) => {
2752                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
2753                 // by looking up the projections associated with the def_id.
2754                 let predicates_of = cx.tcx.predicates_of(def_id);
2755                 let substs = cx.tcx.lift(&substs).unwrap();
2756                 let bounds = predicates_of.instantiate(cx.tcx, substs);
2757                 ImplTrait(bounds.predicates.into_iter().filter_map(|predicate| {
2758                     predicate.to_opt_poly_trait_ref().clean(cx)
2759                 }).collect())
2760             }
2761
2762             ty::TyClosure(..) | ty::TyGenerator(..) => Tuple(vec![]), // FIXME(pcwalton)
2763
2764             ty::TyGeneratorWitness(..) => panic!("TyGeneratorWitness"),
2765             ty::TyInfer(..) => panic!("TyInfer"),
2766             ty::TyError => panic!("TyError"),
2767         }
2768     }
2769 }
2770
2771 impl Clean<Item> for hir::StructField {
2772     fn clean(&self, cx: &DocContext) -> Item {
2773         Item {
2774             name: Some(self.name).clean(cx),
2775             attrs: self.attrs.clean(cx),
2776             source: self.span.clean(cx),
2777             visibility: self.vis.clean(cx),
2778             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2779             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2780             def_id: cx.tcx.hir.local_def_id(self.id),
2781             inner: StructFieldItem(self.ty.clean(cx)),
2782         }
2783     }
2784 }
2785
2786 impl<'tcx> Clean<Item> for ty::FieldDef {
2787     fn clean(&self, cx: &DocContext) -> Item {
2788         Item {
2789             name: Some(self.name).clean(cx),
2790             attrs: cx.tcx.get_attrs(self.did).clean(cx),
2791             source: cx.tcx.def_span(self.did).clean(cx),
2792             visibility: self.vis.clean(cx),
2793             stability: get_stability(cx, self.did),
2794             deprecation: get_deprecation(cx, self.did),
2795             def_id: self.did,
2796             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
2797         }
2798     }
2799 }
2800
2801 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug)]
2802 pub enum Visibility {
2803     Public,
2804     Inherited,
2805 }
2806
2807 impl Clean<Option<Visibility>> for hir::Visibility {
2808     fn clean(&self, _: &DocContext) -> Option<Visibility> {
2809         Some(if *self == hir::Visibility::Public { Public } else { Inherited })
2810     }
2811 }
2812
2813 impl Clean<Option<Visibility>> for ty::Visibility {
2814     fn clean(&self, _: &DocContext) -> Option<Visibility> {
2815         Some(if *self == ty::Visibility::Public { Public } else { Inherited })
2816     }
2817 }
2818
2819 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2820 pub struct Struct {
2821     pub struct_type: doctree::StructType,
2822     pub generics: Generics,
2823     pub fields: Vec<Item>,
2824     pub fields_stripped: bool,
2825 }
2826
2827 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2828 pub struct Union {
2829     pub struct_type: doctree::StructType,
2830     pub generics: Generics,
2831     pub fields: Vec<Item>,
2832     pub fields_stripped: bool,
2833 }
2834
2835 impl Clean<Vec<Item>> for doctree::Struct {
2836     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2837         let name = self.name.clean(cx);
2838         let mut ret = get_auto_traits_with_node_id(cx, self.id, name.clone());
2839
2840         ret.push(Item {
2841             name: Some(name),
2842             attrs: self.attrs.clean(cx),
2843             source: self.whence.clean(cx),
2844             def_id: cx.tcx.hir.local_def_id(self.id),
2845             visibility: self.vis.clean(cx),
2846             stability: self.stab.clean(cx),
2847             deprecation: self.depr.clean(cx),
2848             inner: StructItem(Struct {
2849                 struct_type: self.struct_type,
2850                 generics: self.generics.clean(cx),
2851                 fields: self.fields.clean(cx),
2852                 fields_stripped: false,
2853             }),
2854         });
2855
2856         ret
2857     }
2858 }
2859
2860 impl Clean<Vec<Item>> for doctree::Union {
2861     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2862         let name = self.name.clean(cx);
2863         let mut ret = get_auto_traits_with_node_id(cx, self.id, name.clone());
2864
2865         ret.push(Item {
2866             name: Some(name),
2867             attrs: self.attrs.clean(cx),
2868             source: self.whence.clean(cx),
2869             def_id: cx.tcx.hir.local_def_id(self.id),
2870             visibility: self.vis.clean(cx),
2871             stability: self.stab.clean(cx),
2872             deprecation: self.depr.clean(cx),
2873             inner: UnionItem(Union {
2874                 struct_type: self.struct_type,
2875                 generics: self.generics.clean(cx),
2876                 fields: self.fields.clean(cx),
2877                 fields_stripped: false,
2878             }),
2879         });
2880
2881         ret
2882     }
2883 }
2884
2885 /// This is a more limited form of the standard Struct, different in that
2886 /// it lacks the things most items have (name, id, parameterization). Found
2887 /// only as a variant in an enum.
2888 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2889 pub struct VariantStruct {
2890     pub struct_type: doctree::StructType,
2891     pub fields: Vec<Item>,
2892     pub fields_stripped: bool,
2893 }
2894
2895 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
2896     fn clean(&self, cx: &DocContext) -> VariantStruct {
2897         VariantStruct {
2898             struct_type: doctree::struct_type_from_def(self),
2899             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
2900             fields_stripped: false,
2901         }
2902     }
2903 }
2904
2905 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2906 pub struct Enum {
2907     pub variants: Vec<Item>,
2908     pub generics: Generics,
2909     pub variants_stripped: bool,
2910 }
2911
2912 impl Clean<Vec<Item>> for doctree::Enum {
2913     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2914         let name = self.name.clean(cx);
2915         let mut ret = get_auto_traits_with_node_id(cx, self.id, name.clone());
2916
2917         ret.push(Item {
2918             name: Some(name),
2919             attrs: self.attrs.clean(cx),
2920             source: self.whence.clean(cx),
2921             def_id: cx.tcx.hir.local_def_id(self.id),
2922             visibility: self.vis.clean(cx),
2923             stability: self.stab.clean(cx),
2924             deprecation: self.depr.clean(cx),
2925             inner: EnumItem(Enum {
2926                 variants: self.variants.clean(cx),
2927                 generics: self.generics.clean(cx),
2928                 variants_stripped: false,
2929             }),
2930         });
2931
2932         ret
2933     }
2934 }
2935
2936 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2937 pub struct Variant {
2938     pub kind: VariantKind,
2939 }
2940
2941 impl Clean<Item> for doctree::Variant {
2942     fn clean(&self, cx: &DocContext) -> Item {
2943         Item {
2944             name: Some(self.name.clean(cx)),
2945             attrs: self.attrs.clean(cx),
2946             source: self.whence.clean(cx),
2947             visibility: None,
2948             stability: self.stab.clean(cx),
2949             deprecation: self.depr.clean(cx),
2950             def_id: cx.tcx.hir.local_def_id(self.def.id()),
2951             inner: VariantItem(Variant {
2952                 kind: self.def.clean(cx),
2953             }),
2954         }
2955     }
2956 }
2957
2958 impl<'tcx> Clean<Item> for ty::VariantDef {
2959     fn clean(&self, cx: &DocContext) -> Item {
2960         let kind = match self.ctor_kind {
2961             CtorKind::Const => VariantKind::CLike,
2962             CtorKind::Fn => {
2963                 VariantKind::Tuple(
2964                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
2965                 )
2966             }
2967             CtorKind::Fictive => {
2968                 VariantKind::Struct(VariantStruct {
2969                     struct_type: doctree::Plain,
2970                     fields_stripped: false,
2971                     fields: self.fields.iter().map(|field| {
2972                         Item {
2973                             source: cx.tcx.def_span(field.did).clean(cx),
2974                             name: Some(field.name.clean(cx)),
2975                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
2976                             visibility: field.vis.clean(cx),
2977                             def_id: field.did,
2978                             stability: get_stability(cx, field.did),
2979                             deprecation: get_deprecation(cx, field.did),
2980                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
2981                         }
2982                     }).collect()
2983                 })
2984             }
2985         };
2986         Item {
2987             name: Some(self.name.clean(cx)),
2988             attrs: inline::load_attrs(cx, self.did),
2989             source: cx.tcx.def_span(self.did).clean(cx),
2990             visibility: Some(Inherited),
2991             def_id: self.did,
2992             inner: VariantItem(Variant { kind: kind }),
2993             stability: get_stability(cx, self.did),
2994             deprecation: get_deprecation(cx, self.did),
2995         }
2996     }
2997 }
2998
2999 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3000 pub enum VariantKind {
3001     CLike,
3002     Tuple(Vec<Type>),
3003     Struct(VariantStruct),
3004 }
3005
3006 impl Clean<VariantKind> for hir::VariantData {
3007     fn clean(&self, cx: &DocContext) -> VariantKind {
3008         if self.is_struct() {
3009             VariantKind::Struct(self.clean(cx))
3010         } else if self.is_unit() {
3011             VariantKind::CLike
3012         } else {
3013             VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect())
3014         }
3015     }
3016 }
3017
3018 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3019 pub struct Span {
3020     pub filename: FileName,
3021     pub loline: usize,
3022     pub locol: usize,
3023     pub hiline: usize,
3024     pub hicol: usize,
3025 }
3026
3027 impl Span {
3028     pub fn empty() -> Span {
3029         Span {
3030             filename: FileName::Anon,
3031             loline: 0, locol: 0,
3032             hiline: 0, hicol: 0,
3033         }
3034     }
3035 }
3036
3037 impl Clean<Span> for syntax_pos::Span {
3038     fn clean(&self, cx: &DocContext) -> Span {
3039         if *self == DUMMY_SP {
3040             return Span::empty();
3041         }
3042
3043         let cm = cx.sess().codemap();
3044         let filename = cm.span_to_filename(*self);
3045         let lo = cm.lookup_char_pos(self.lo());
3046         let hi = cm.lookup_char_pos(self.hi());
3047         Span {
3048             filename,
3049             loline: lo.line,
3050             locol: lo.col.to_usize(),
3051             hiline: hi.line,
3052             hicol: hi.col.to_usize(),
3053         }
3054     }
3055 }
3056
3057 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3058 pub struct Path {
3059     pub global: bool,
3060     pub def: Def,
3061     pub segments: Vec<PathSegment>,
3062 }
3063
3064 impl Path {
3065     pub fn singleton(name: String) -> Path {
3066         Path {
3067             global: false,
3068             def: Def::Err,
3069             segments: vec![PathSegment {
3070                 name,
3071                 params: PathParameters::AngleBracketed {
3072                     lifetimes: Vec::new(),
3073                     types: Vec::new(),
3074                     bindings: Vec::new(),
3075                 }
3076             }]
3077         }
3078     }
3079
3080     pub fn last_name(&self) -> &str {
3081         self.segments.last().unwrap().name.as_str()
3082     }
3083 }
3084
3085 impl Clean<Path> for hir::Path {
3086     fn clean(&self, cx: &DocContext) -> Path {
3087         Path {
3088             global: self.is_global(),
3089             def: self.def,
3090             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
3091         }
3092     }
3093 }
3094
3095 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3096 pub enum PathParameters {
3097     AngleBracketed {
3098         lifetimes: Vec<Lifetime>,
3099         types: Vec<Type>,
3100         bindings: Vec<TypeBinding>,
3101     },
3102     Parenthesized {
3103         inputs: Vec<Type>,
3104         output: Option<Type>,
3105     }
3106 }
3107
3108 impl Clean<PathParameters> for hir::PathParameters {
3109     fn clean(&self, cx: &DocContext) -> PathParameters {
3110         if self.parenthesized {
3111             let output = self.bindings[0].ty.clean(cx);
3112             PathParameters::Parenthesized {
3113                 inputs: self.inputs().clean(cx),
3114                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
3115             }
3116         } else {
3117             PathParameters::AngleBracketed {
3118                 lifetimes: if self.lifetimes.iter().all(|lt| lt.is_elided()) {
3119                     vec![]
3120                 } else {
3121                     self.lifetimes.clean(cx)
3122                 },
3123                 types: self.types.clean(cx),
3124                 bindings: self.bindings.clean(cx),
3125             }
3126         }
3127     }
3128 }
3129
3130 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3131 pub struct PathSegment {
3132     pub name: String,
3133     pub params: PathParameters,
3134 }
3135
3136 impl Clean<PathSegment> for hir::PathSegment {
3137     fn clean(&self, cx: &DocContext) -> PathSegment {
3138         PathSegment {
3139             name: self.name.clean(cx),
3140             params: self.with_parameters(|parameters| parameters.clean(cx))
3141         }
3142     }
3143 }
3144
3145 fn strip_type(ty: Type) -> Type {
3146     match ty {
3147         Type::ResolvedPath { path, typarams, did, is_generic } => {
3148             Type::ResolvedPath { path: strip_path(&path), typarams, did, is_generic }
3149         }
3150         Type::Tuple(inner_tys) => {
3151             Type::Tuple(inner_tys.iter().map(|t| strip_type(t.clone())).collect())
3152         }
3153         Type::Slice(inner_ty) => Type::Slice(Box::new(strip_type(*inner_ty))),
3154         Type::Array(inner_ty, s) => Type::Array(Box::new(strip_type(*inner_ty)), s),
3155         Type::Unique(inner_ty) => Type::Unique(Box::new(strip_type(*inner_ty))),
3156         Type::RawPointer(m, inner_ty) => Type::RawPointer(m, Box::new(strip_type(*inner_ty))),
3157         Type::BorrowedRef { lifetime, mutability, type_ } => {
3158             Type::BorrowedRef { lifetime, mutability, type_: Box::new(strip_type(*type_)) }
3159         }
3160         Type::QPath { name, self_type, trait_ } => {
3161             Type::QPath {
3162                 name,
3163                 self_type: Box::new(strip_type(*self_type)), trait_: Box::new(strip_type(*trait_))
3164             }
3165         }
3166         _ => ty
3167     }
3168 }
3169
3170 fn strip_path(path: &Path) -> Path {
3171     let segments = path.segments.iter().map(|s| {
3172         PathSegment {
3173             name: s.name.clone(),
3174             params: PathParameters::AngleBracketed {
3175                 lifetimes: Vec::new(),
3176                 types: Vec::new(),
3177                 bindings: Vec::new(),
3178             }
3179         }
3180     }).collect();
3181
3182     Path {
3183         global: path.global,
3184         def: path.def.clone(),
3185         segments,
3186     }
3187 }
3188
3189 fn qpath_to_string(p: &hir::QPath) -> String {
3190     let segments = match *p {
3191         hir::QPath::Resolved(_, ref path) => &path.segments,
3192         hir::QPath::TypeRelative(_, ref segment) => return segment.name.to_string(),
3193     };
3194
3195     let mut s = String::new();
3196     for (i, seg) in segments.iter().enumerate() {
3197         if i > 0 {
3198             s.push_str("::");
3199         }
3200         if seg.name != keywords::CrateRoot.name() {
3201             s.push_str(&*seg.name.as_str());
3202         }
3203     }
3204     s
3205 }
3206
3207 impl Clean<String> for ast::Name {
3208     fn clean(&self, _: &DocContext) -> String {
3209         self.to_string()
3210     }
3211 }
3212
3213 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3214 pub struct Typedef {
3215     pub type_: Type,
3216     pub generics: Generics,
3217 }
3218
3219 impl Clean<Item> for doctree::Typedef {
3220     fn clean(&self, cx: &DocContext) -> Item {
3221         Item {
3222             name: Some(self.name.clean(cx)),
3223             attrs: self.attrs.clean(cx),
3224             source: self.whence.clean(cx),
3225             def_id: cx.tcx.hir.local_def_id(self.id.clone()),
3226             visibility: self.vis.clean(cx),
3227             stability: self.stab.clean(cx),
3228             deprecation: self.depr.clean(cx),
3229             inner: TypedefItem(Typedef {
3230                 type_: self.ty.clean(cx),
3231                 generics: self.gen.clean(cx),
3232             }, false),
3233         }
3234     }
3235 }
3236
3237 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3238 pub struct BareFunctionDecl {
3239     pub unsafety: hir::Unsafety,
3240     pub generic_params: Vec<GenericParam>,
3241     pub decl: FnDecl,
3242     pub abi: Abi,
3243 }
3244
3245 impl Clean<BareFunctionDecl> for hir::BareFnTy {
3246     fn clean(&self, cx: &DocContext) -> BareFunctionDecl {
3247         BareFunctionDecl {
3248             unsafety: self.unsafety,
3249             generic_params: self.generic_params.clean(cx),
3250             decl: (&*self.decl, &self.arg_names[..]).clean(cx),
3251             abi: self.abi,
3252         }
3253     }
3254 }
3255
3256 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3257 pub struct Static {
3258     pub type_: Type,
3259     pub mutability: Mutability,
3260     /// It's useful to have the value of a static documented, but I have no
3261     /// desire to represent expressions (that'd basically be all of the AST,
3262     /// which is huge!). So, have a string.
3263     pub expr: String,
3264 }
3265
3266 impl Clean<Item> for doctree::Static {
3267     fn clean(&self, cx: &DocContext) -> Item {
3268         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
3269         Item {
3270             name: Some(self.name.clean(cx)),
3271             attrs: self.attrs.clean(cx),
3272             source: self.whence.clean(cx),
3273             def_id: cx.tcx.hir.local_def_id(self.id),
3274             visibility: self.vis.clean(cx),
3275             stability: self.stab.clean(cx),
3276             deprecation: self.depr.clean(cx),
3277             inner: StaticItem(Static {
3278                 type_: self.type_.clean(cx),
3279                 mutability: self.mutability.clean(cx),
3280                 expr: print_const_expr(cx, self.expr),
3281             }),
3282         }
3283     }
3284 }
3285
3286 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3287 pub struct Constant {
3288     pub type_: Type,
3289     pub expr: String,
3290 }
3291
3292 impl Clean<Item> for doctree::Constant {
3293     fn clean(&self, cx: &DocContext) -> Item {
3294         Item {
3295             name: Some(self.name.clean(cx)),
3296             attrs: self.attrs.clean(cx),
3297             source: self.whence.clean(cx),
3298             def_id: cx.tcx.hir.local_def_id(self.id),
3299             visibility: self.vis.clean(cx),
3300             stability: self.stab.clean(cx),
3301             deprecation: self.depr.clean(cx),
3302             inner: ConstantItem(Constant {
3303                 type_: self.type_.clean(cx),
3304                 expr: print_const_expr(cx, self.expr),
3305             }),
3306         }
3307     }
3308 }
3309
3310 #[derive(Debug, Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Hash)]
3311 pub enum Mutability {
3312     Mutable,
3313     Immutable,
3314 }
3315
3316 impl Clean<Mutability> for hir::Mutability {
3317     fn clean(&self, _: &DocContext) -> Mutability {
3318         match self {
3319             &hir::MutMutable => Mutable,
3320             &hir::MutImmutable => Immutable,
3321         }
3322     }
3323 }
3324
3325 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Debug, Hash)]
3326 pub enum ImplPolarity {
3327     Positive,
3328     Negative,
3329 }
3330
3331 impl Clean<ImplPolarity> for hir::ImplPolarity {
3332     fn clean(&self, _: &DocContext) -> ImplPolarity {
3333         match self {
3334             &hir::ImplPolarity::Positive => ImplPolarity::Positive,
3335             &hir::ImplPolarity::Negative => ImplPolarity::Negative,
3336         }
3337     }
3338 }
3339
3340 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3341 pub struct Impl {
3342     pub unsafety: hir::Unsafety,
3343     pub generics: Generics,
3344     pub provided_trait_methods: FxHashSet<String>,
3345     pub trait_: Option<Type>,
3346     pub for_: Type,
3347     pub items: Vec<Item>,
3348     pub polarity: Option<ImplPolarity>,
3349     pub synthetic: bool,
3350 }
3351
3352 pub fn get_auto_traits_with_node_id(cx: &DocContext, id: ast::NodeId, name: String) -> Vec<Item> {
3353     let finder = AutoTraitFinder { cx };
3354     finder.get_with_node_id(id, name)
3355 }
3356
3357 pub fn get_auto_traits_with_def_id(cx: &DocContext, id: DefId) -> Vec<Item> {
3358     let finder = AutoTraitFinder {
3359         cx,
3360     };
3361
3362     finder.get_with_def_id(id)
3363 }
3364
3365 impl Clean<Vec<Item>> for doctree::Impl {
3366     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3367         let mut ret = Vec::new();
3368         let trait_ = self.trait_.clean(cx);
3369         let items = self.items.clean(cx);
3370
3371         // If this impl block is an implementation of the Deref trait, then we
3372         // need to try inlining the target's inherent impl blocks as well.
3373         if trait_.def_id() == cx.tcx.lang_items().deref_trait() {
3374             build_deref_target_impls(cx, &items, &mut ret);
3375         }
3376
3377         let provided = trait_.def_id().map(|did| {
3378             cx.tcx.provided_trait_methods(did)
3379                   .into_iter()
3380                   .map(|meth| meth.name.to_string())
3381                   .collect()
3382         }).unwrap_or(FxHashSet());
3383
3384         ret.push(Item {
3385             name: None,
3386             attrs: self.attrs.clean(cx),
3387             source: self.whence.clean(cx),
3388             def_id: cx.tcx.hir.local_def_id(self.id),
3389             visibility: self.vis.clean(cx),
3390             stability: self.stab.clean(cx),
3391             deprecation: self.depr.clean(cx),
3392             inner: ImplItem(Impl {
3393                 unsafety: self.unsafety,
3394                 generics: self.generics.clean(cx),
3395                 provided_trait_methods: provided,
3396                 trait_,
3397                 for_: self.for_.clean(cx),
3398                 items,
3399                 polarity: Some(self.polarity.clean(cx)),
3400                 synthetic: false,
3401             })
3402         });
3403         ret
3404     }
3405 }
3406
3407 fn build_deref_target_impls(cx: &DocContext,
3408                             items: &[Item],
3409                             ret: &mut Vec<Item>) {
3410     use self::PrimitiveType::*;
3411     let tcx = cx.tcx;
3412
3413     for item in items {
3414         let target = match item.inner {
3415             TypedefItem(ref t, true) => &t.type_,
3416             _ => continue,
3417         };
3418         let primitive = match *target {
3419             ResolvedPath { did, .. } if did.is_local() => continue,
3420             ResolvedPath { did, .. } => {
3421                 // We set the last parameter to false to avoid looking for auto-impls for traits
3422                 // and therefore avoid an ICE.
3423                 // The reason behind this is that auto-traits don't propagate through Deref so
3424                 // we're not supposed to synthesise impls for them.
3425                 ret.extend(inline::build_impls(cx, did, false));
3426                 continue
3427             }
3428             _ => match target.primitive_type() {
3429                 Some(prim) => prim,
3430                 None => continue,
3431             }
3432         };
3433         let did = match primitive {
3434             Isize => tcx.lang_items().isize_impl(),
3435             I8 => tcx.lang_items().i8_impl(),
3436             I16 => tcx.lang_items().i16_impl(),
3437             I32 => tcx.lang_items().i32_impl(),
3438             I64 => tcx.lang_items().i64_impl(),
3439             I128 => tcx.lang_items().i128_impl(),
3440             Usize => tcx.lang_items().usize_impl(),
3441             U8 => tcx.lang_items().u8_impl(),
3442             U16 => tcx.lang_items().u16_impl(),
3443             U32 => tcx.lang_items().u32_impl(),
3444             U64 => tcx.lang_items().u64_impl(),
3445             U128 => tcx.lang_items().u128_impl(),
3446             F32 => tcx.lang_items().f32_impl(),
3447             F64 => tcx.lang_items().f64_impl(),
3448             Char => tcx.lang_items().char_impl(),
3449             Bool => None,
3450             Str => tcx.lang_items().str_impl(),
3451             Slice => tcx.lang_items().slice_impl(),
3452             Array => tcx.lang_items().slice_impl(),
3453             Tuple => None,
3454             Unit => None,
3455             RawPointer => tcx.lang_items().const_ptr_impl(),
3456             Reference => None,
3457             Fn => None,
3458             Never => None,
3459         };
3460         if let Some(did) = did {
3461             if !did.is_local() {
3462                 inline::build_impl(cx, did, ret);
3463             }
3464         }
3465     }
3466 }
3467
3468 impl Clean<Item> for doctree::ExternCrate {
3469     fn clean(&self, cx: &DocContext) -> Item {
3470         Item {
3471             name: None,
3472             attrs: self.attrs.clean(cx),
3473             source: self.whence.clean(cx),
3474             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
3475             visibility: self.vis.clean(cx),
3476             stability: None,
3477             deprecation: None,
3478             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
3479         }
3480     }
3481 }
3482
3483 impl Clean<Vec<Item>> for doctree::Import {
3484     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3485         // We consider inlining the documentation of `pub use` statements, but we
3486         // forcefully don't inline if this is not public or if the
3487         // #[doc(no_inline)] attribute is present.
3488         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
3489         let denied = self.vis != hir::Public || self.attrs.iter().any(|a| {
3490             a.name().unwrap() == "doc" && match a.meta_item_list() {
3491                 Some(l) => attr::list_contains_name(&l, "no_inline") ||
3492                            attr::list_contains_name(&l, "hidden"),
3493                 None => false,
3494             }
3495         });
3496         let path = self.path.clean(cx);
3497         let inner = if self.glob {
3498             Import::Glob(resolve_use_source(cx, path))
3499         } else {
3500             let name = self.name;
3501             if !denied {
3502                 if let Some(items) = inline::try_inline(cx, path.def, name) {
3503                     return items;
3504                 }
3505             }
3506             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
3507         };
3508         vec![Item {
3509             name: None,
3510             attrs: self.attrs.clean(cx),
3511             source: self.whence.clean(cx),
3512             def_id: cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID),
3513             visibility: self.vis.clean(cx),
3514             stability: None,
3515             deprecation: None,
3516             inner: ImportItem(inner)
3517         }]
3518     }
3519 }
3520
3521 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3522 pub enum Import {
3523     // use source as str;
3524     Simple(String, ImportSource),
3525     // use source::*;
3526     Glob(ImportSource)
3527 }
3528
3529 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3530 pub struct ImportSource {
3531     pub path: Path,
3532     pub did: Option<DefId>,
3533 }
3534
3535 impl Clean<Vec<Item>> for hir::ForeignMod {
3536     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3537         let mut items = self.items.clean(cx);
3538         for item in &mut items {
3539             if let ForeignFunctionItem(ref mut f) = item.inner {
3540                 f.abi = self.abi;
3541             }
3542         }
3543         items
3544     }
3545 }
3546
3547 impl Clean<Item> for hir::ForeignItem {
3548     fn clean(&self, cx: &DocContext) -> Item {
3549         let inner = match self.node {
3550             hir::ForeignItemFn(ref decl, ref names, ref generics) => {
3551                 ForeignFunctionItem(Function {
3552                     decl: (&**decl, &names[..]).clean(cx),
3553                     generics: generics.clean(cx),
3554                     unsafety: hir::Unsafety::Unsafe,
3555                     abi: Abi::Rust,
3556                     constness: hir::Constness::NotConst,
3557                 })
3558             }
3559             hir::ForeignItemStatic(ref ty, mutbl) => {
3560                 ForeignStaticItem(Static {
3561                     type_: ty.clean(cx),
3562                     mutability: if mutbl {Mutable} else {Immutable},
3563                     expr: "".to_string(),
3564                 })
3565             }
3566             hir::ForeignItemType => {
3567                 ForeignTypeItem
3568             }
3569         };
3570         Item {
3571             name: Some(self.name.clean(cx)),
3572             attrs: self.attrs.clean(cx),
3573             source: self.span.clean(cx),
3574             def_id: cx.tcx.hir.local_def_id(self.id),
3575             visibility: self.vis.clean(cx),
3576             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
3577             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
3578             inner,
3579         }
3580     }
3581 }
3582
3583 // Utilities
3584
3585 trait ToSource {
3586     fn to_src(&self, cx: &DocContext) -> String;
3587 }
3588
3589 impl ToSource for syntax_pos::Span {
3590     fn to_src(&self, cx: &DocContext) -> String {
3591         debug!("converting span {:?} to snippet", self.clean(cx));
3592         let sn = match cx.sess().codemap().span_to_snippet(*self) {
3593             Ok(x) => x.to_string(),
3594             Err(_) => "".to_string()
3595         };
3596         debug!("got snippet {}", sn);
3597         sn
3598     }
3599 }
3600
3601 fn name_from_pat(p: &hir::Pat) -> String {
3602     use rustc::hir::*;
3603     debug!("Trying to get a name from pattern: {:?}", p);
3604
3605     match p.node {
3606         PatKind::Wild => "_".to_string(),
3607         PatKind::Binding(_, _, ref p, _) => p.node.to_string(),
3608         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
3609         PatKind::Struct(ref name, ref fields, etc) => {
3610             format!("{} {{ {}{} }}", qpath_to_string(name),
3611                 fields.iter().map(|&Spanned { node: ref fp, .. }|
3612                                   format!("{}: {}", fp.name, name_from_pat(&*fp.pat)))
3613                              .collect::<Vec<String>>().join(", "),
3614                 if etc { ", ..." } else { "" }
3615             )
3616         }
3617         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
3618                                             .collect::<Vec<String>>().join(", ")),
3619         PatKind::Box(ref p) => name_from_pat(&**p),
3620         PatKind::Ref(ref p, _) => name_from_pat(&**p),
3621         PatKind::Lit(..) => {
3622             warn!("tried to get argument name from PatKind::Lit, \
3623                   which is silly in function arguments");
3624             "()".to_string()
3625         },
3626         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
3627                               which is not allowed in function arguments"),
3628         PatKind::Slice(ref begin, ref mid, ref end) => {
3629             let begin = begin.iter().map(|p| name_from_pat(&**p));
3630             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
3631             let end = end.iter().map(|p| name_from_pat(&**p));
3632             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
3633         },
3634     }
3635 }
3636
3637 fn print_const_expr(cx: &DocContext, body: hir::BodyId) -> String {
3638     cx.tcx.hir.node_to_pretty_string(body.node_id)
3639 }
3640
3641 /// Given a type Path, resolve it to a Type using the TyCtxt
3642 fn resolve_type(cx: &DocContext,
3643                 path: Path,
3644                 id: ast::NodeId) -> Type {
3645     if id == ast::DUMMY_NODE_ID {
3646         debug!("resolve_type({:?})", path);
3647     } else {
3648         debug!("resolve_type({:?},{:?})", path, id);
3649     }
3650
3651     let is_generic = match path.def {
3652         Def::PrimTy(p) => match p {
3653             hir::TyStr => return Primitive(PrimitiveType::Str),
3654             hir::TyBool => return Primitive(PrimitiveType::Bool),
3655             hir::TyChar => return Primitive(PrimitiveType::Char),
3656             hir::TyInt(int_ty) => return Primitive(int_ty.into()),
3657             hir::TyUint(uint_ty) => return Primitive(uint_ty.into()),
3658             hir::TyFloat(float_ty) => return Primitive(float_ty.into()),
3659         },
3660         Def::SelfTy(..) if path.segments.len() == 1 => {
3661             return Generic(keywords::SelfType.name().to_string());
3662         }
3663         Def::TyParam(..) if path.segments.len() == 1 => {
3664             return Generic(format!("{:#}", path));
3665         }
3666         Def::SelfTy(..) | Def::TyParam(..) | Def::AssociatedTy(..) => true,
3667         _ => false,
3668     };
3669     let did = register_def(&*cx, path.def);
3670     ResolvedPath { path: path, typarams: None, did: did, is_generic: is_generic }
3671 }
3672
3673 fn register_def(cx: &DocContext, def: Def) -> DefId {
3674     debug!("register_def({:?})", def);
3675
3676     let (did, kind) = match def {
3677         Def::Fn(i) => (i, TypeKind::Function),
3678         Def::TyAlias(i) => (i, TypeKind::Typedef),
3679         Def::Enum(i) => (i, TypeKind::Enum),
3680         Def::Trait(i) => (i, TypeKind::Trait),
3681         Def::Struct(i) => (i, TypeKind::Struct),
3682         Def::Union(i) => (i, TypeKind::Union),
3683         Def::Mod(i) => (i, TypeKind::Module),
3684         Def::TyForeign(i) => (i, TypeKind::Foreign),
3685         Def::Static(i, _) => (i, TypeKind::Static),
3686         Def::Variant(i) => (cx.tcx.parent_def_id(i).unwrap(), TypeKind::Enum),
3687         Def::Macro(i, _) => (i, TypeKind::Macro),
3688         Def::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
3689         Def::SelfTy(_, Some(impl_def_id)) => {
3690             return impl_def_id
3691         }
3692         _ => return def.def_id()
3693     };
3694     if did.is_local() { return did }
3695     inline::record_extern_fqn(cx, did, kind);
3696     if let TypeKind::Trait = kind {
3697         inline::record_extern_trait(cx, did);
3698     }
3699     did
3700 }
3701
3702 fn resolve_use_source(cx: &DocContext, path: Path) -> ImportSource {
3703     ImportSource {
3704         did: if path.def == Def::Err {
3705             None
3706         } else {
3707             Some(register_def(cx, path.def))
3708         },
3709         path,
3710     }
3711 }
3712
3713 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3714 pub struct Macro {
3715     pub source: String,
3716     pub imported_from: Option<String>,
3717 }
3718
3719 impl Clean<Item> for doctree::Macro {
3720     fn clean(&self, cx: &DocContext) -> Item {
3721         let name = self.name.clean(cx);
3722         Item {
3723             name: Some(name.clone()),
3724             attrs: self.attrs.clean(cx),
3725             source: self.whence.clean(cx),
3726             visibility: Some(Public),
3727             stability: self.stab.clean(cx),
3728             deprecation: self.depr.clean(cx),
3729             def_id: self.def_id,
3730             inner: MacroItem(Macro {
3731                 source: format!("macro_rules! {} {{\n{}}}",
3732                                 name,
3733                                 self.matchers.iter().map(|span| {
3734                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
3735                                 }).collect::<String>()),
3736                 imported_from: self.imported_from.clean(cx),
3737             }),
3738         }
3739     }
3740 }
3741
3742 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3743 pub struct Stability {
3744     pub level: stability::StabilityLevel,
3745     pub feature: String,
3746     pub since: String,
3747     pub deprecated_since: String,
3748     pub deprecated_reason: String,
3749     pub unstable_reason: String,
3750     pub issue: Option<u32>
3751 }
3752
3753 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3754 pub struct Deprecation {
3755     pub since: String,
3756     pub note: String,
3757 }
3758
3759 impl Clean<Stability> for attr::Stability {
3760     fn clean(&self, _: &DocContext) -> Stability {
3761         Stability {
3762             level: stability::StabilityLevel::from_attr_level(&self.level),
3763             feature: self.feature.to_string(),
3764             since: match self.level {
3765                 attr::Stable {ref since} => since.to_string(),
3766                 _ => "".to_string(),
3767             },
3768             deprecated_since: match self.rustc_depr {
3769                 Some(attr::RustcDeprecation {ref since, ..}) => since.to_string(),
3770                 _=> "".to_string(),
3771             },
3772             deprecated_reason: match self.rustc_depr {
3773                 Some(ref depr) => depr.reason.to_string(),
3774                 _ => "".to_string(),
3775             },
3776             unstable_reason: match self.level {
3777                 attr::Unstable { reason: Some(ref reason), .. } => reason.to_string(),
3778                 _ => "".to_string(),
3779             },
3780             issue: match self.level {
3781                 attr::Unstable {issue, ..} => Some(issue),
3782                 _ => None,
3783             }
3784         }
3785     }
3786 }
3787
3788 impl<'a> Clean<Stability> for &'a attr::Stability {
3789     fn clean(&self, dc: &DocContext) -> Stability {
3790         (**self).clean(dc)
3791     }
3792 }
3793
3794 impl Clean<Deprecation> for attr::Deprecation {
3795     fn clean(&self, _: &DocContext) -> Deprecation {
3796         Deprecation {
3797             since: self.since.as_ref().map_or("".to_string(), |s| s.to_string()),
3798             note: self.note.as_ref().map_or("".to_string(), |s| s.to_string()),
3799         }
3800     }
3801 }
3802
3803 /// An equality constraint on an associated type, e.g. `A=Bar` in `Foo<A=Bar>`
3804 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug, Hash)]
3805 pub struct TypeBinding {
3806     pub name: String,
3807     pub ty: Type
3808 }
3809
3810 impl Clean<TypeBinding> for hir::TypeBinding {
3811     fn clean(&self, cx: &DocContext) -> TypeBinding {
3812         TypeBinding {
3813             name: self.name.clean(cx),
3814             ty: self.ty.clean(cx)
3815         }
3816     }
3817 }
3818
3819 pub fn def_id_to_path(cx: &DocContext, did: DefId, name: Option<String>) -> Vec<String> {
3820     let crate_name = name.unwrap_or_else(|| cx.tcx.crate_name(did.krate).to_string());
3821     let relative = cx.tcx.def_path(did).data.into_iter().filter_map(|elem| {
3822         // extern blocks have an empty name
3823         let s = elem.data.to_string();
3824         if !s.is_empty() {
3825             Some(s)
3826         } else {
3827             None
3828         }
3829     });
3830     once(crate_name).chain(relative).collect()
3831 }
3832
3833 // Start of code copied from rust-clippy
3834
3835 pub fn get_trait_def_id(tcx: &TyCtxt, path: &[&str], use_local: bool) -> Option<DefId> {
3836     if use_local {
3837         path_to_def_local(tcx, path)
3838     } else {
3839         path_to_def(tcx, path)
3840     }
3841 }
3842
3843 pub fn path_to_def_local(tcx: &TyCtxt, path: &[&str]) -> Option<DefId> {
3844     let krate = tcx.hir.krate();
3845     let mut items = krate.module.item_ids.clone();
3846     let mut path_it = path.iter().peekable();
3847
3848     loop {
3849         let segment = match path_it.next() {
3850             Some(segment) => segment,
3851             None => return None,
3852         };
3853
3854         for item_id in mem::replace(&mut items, HirVec::new()).iter() {
3855             let item = tcx.hir.expect_item(item_id.id);
3856             if item.name == *segment {
3857                 if path_it.peek().is_none() {
3858                     return Some(tcx.hir.local_def_id(item_id.id))
3859                 }
3860
3861                 items = match &item.node {
3862                     &hir::ItemMod(ref m) => m.item_ids.clone(),
3863                     _ => panic!("Unexpected item {:?} in path {:?} path")
3864                 };
3865                 break;
3866             }
3867         }
3868     }
3869 }
3870
3871 pub fn path_to_def(tcx: &TyCtxt, path: &[&str]) -> Option<DefId> {
3872     let crates = tcx.crates();
3873
3874     let krate = crates
3875         .iter()
3876         .find(|&&krate| tcx.crate_name(krate) == path[0]);
3877
3878     if let Some(krate) = krate {
3879         let krate = DefId {
3880             krate: *krate,
3881             index: CRATE_DEF_INDEX,
3882         };
3883         let mut items = tcx.item_children(krate);
3884         let mut path_it = path.iter().skip(1).peekable();
3885
3886         loop {
3887             let segment = match path_it.next() {
3888                 Some(segment) => segment,
3889                 None => return None,
3890             };
3891
3892             for item in mem::replace(&mut items, Lrc::new(vec![])).iter() {
3893                 if item.ident.name == *segment {
3894                     if path_it.peek().is_none() {
3895                         return match item.def {
3896                             def::Def::Trait(did) => Some(did),
3897                             _ => None,
3898                         }
3899                     }
3900
3901                     items = tcx.item_children(item.def.def_id());
3902                     break;
3903                 }
3904             }
3905         }
3906     } else {
3907         None
3908     }
3909 }
3910
3911 fn get_path_for_type(tcx: TyCtxt, def_id: DefId, def_ctor: fn(DefId) -> Def) -> hir::Path {
3912     struct AbsolutePathBuffer {
3913         names: Vec<String>,
3914     }
3915
3916     impl ty::item_path::ItemPathBuffer for AbsolutePathBuffer {
3917         fn root_mode(&self) -> &ty::item_path::RootMode {
3918             const ABSOLUTE: &'static ty::item_path::RootMode = &ty::item_path::RootMode::Absolute;
3919             ABSOLUTE
3920         }
3921
3922         fn push(&mut self, text: &str) {
3923             self.names.push(text.to_owned());
3924         }
3925     }
3926
3927     let mut apb = AbsolutePathBuffer { names: vec![] };
3928
3929     tcx.push_item_path(&mut apb, def_id);
3930
3931     hir::Path {
3932         span: DUMMY_SP,
3933         def: def_ctor(def_id),
3934         segments: hir::HirVec::from_vec(apb.names.iter().map(|s| hir::PathSegment {
3935             name: ast::Name::intern(&s),
3936             parameters: None,
3937             infer_types: false,
3938         }).collect())
3939     }
3940 }
3941
3942 // End of code copied from rust-clippy
3943
3944
3945 #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
3946 enum RegionTarget<'tcx> {
3947     Region(Region<'tcx>),
3948     RegionVid(RegionVid)
3949 }
3950
3951 #[derive(Default, Debug, Clone)]
3952 struct RegionDeps<'tcx> {
3953     larger: FxHashSet<RegionTarget<'tcx>>,
3954     smaller: FxHashSet<RegionTarget<'tcx>>
3955 }
3956
3957 #[derive(Eq, PartialEq, Hash, Debug)]
3958 enum SimpleBound {
3959     RegionBound(Lifetime),
3960     TraitBound(Vec<PathSegment>, Vec<SimpleBound>, Vec<GenericParam>, hir::TraitBoundModifier)
3961 }
3962
3963 enum AutoTraitResult {
3964     ExplicitImpl,
3965     PositiveImpl(Generics),
3966     NegativeImpl,
3967 }
3968
3969 impl AutoTraitResult {
3970     fn is_auto(&self) -> bool {
3971         match *self {
3972             AutoTraitResult::PositiveImpl(_) | AutoTraitResult::NegativeImpl => true,
3973             _ => false,
3974         }
3975     }
3976 }
3977
3978 impl From<TyParamBound> for SimpleBound {
3979     fn from(bound: TyParamBound) -> Self {
3980         match bound.clone() {
3981             TyParamBound::RegionBound(l) => SimpleBound::RegionBound(l),
3982             TyParamBound::TraitBound(t, mod_) => match t.trait_ {
3983                 Type::ResolvedPath { path, typarams, .. } => {
3984                     SimpleBound::TraitBound(path.segments,
3985                                             typarams
3986                                                 .map_or_else(|| Vec::new(), |v| v.iter()
3987                                                         .map(|p| SimpleBound::from(p.clone()))
3988                                                         .collect()),
3989                                             t.generic_params,
3990                                             mod_)
3991                 }
3992                 _ => panic!("Unexpected bound {:?}", bound),
3993             }
3994         }
3995     }
3996 }