src/librustdoc/clean/mod.rs

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