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