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