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