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