src/librustdoc/clean/mod.rs

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