src/librustdoc/clean/mod.rs

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