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