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