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