src/librustdoc/clean/mod.rs

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