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