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