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