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 params = Vec::with_capacity(self.params.len());
1759         for p in &self.params {
1760             let p = p.clean(cx);
1761             if let GenericParam::Type(ref tp) = p {
1762                 if tp.synthetic == Some(hir::SyntheticTyParamKind::ImplTrait) {
1763                     cx.impl_trait_bounds.borrow_mut().insert(tp.did, tp.bounds.clone());
1764                 }
1765             }
1766             params.push(p);
1767         }
1768         let mut g = Generics {
1769             params,
1770             where_predicates: self.where_clause.predicates.clean(cx)
1771         };
1772
1773         // Some duplicates are generated for ?Sized bounds between type params and where
1774         // predicates. The point in here is to move the bounds definitions from type params
1775         // to where predicates when such cases occur.
1776         for where_pred in &mut g.where_predicates {
1777             match *where_pred {
1778                 WherePredicate::BoundPredicate { ty: Generic(ref name), ref mut bounds } => {
1779                     if bounds.is_empty() {
1780                         for param in &mut g.params {
1781                             if let GenericParam::Type(ref mut type_param) = *param {
1782                                 if &type_param.name == name {
1783                                     mem::swap(bounds, &mut type_param.bounds);
1784                                     break
1785                                 }
1786                             }
1787                         }
1788                     }
1789                 }
1790                 _ => continue,
1791             }
1792         }
1793         g
1794     }
1795 }
1796
1797 impl<'a, 'tcx> Clean<Generics> for (&'a ty::Generics,
1798                                     &'a ty::GenericPredicates<'tcx>) {
1799     fn clean(&self, cx: &DocContext) -> Generics {
1800         use self::WherePredicate as WP;
1801
1802         let (gens, preds) = *self;
1803
1804         // Bounds in the type_params and lifetimes fields are repeated in the
1805         // predicates field (see rustc_typeck::collect::ty_generics), so remove
1806         // them.
1807         let stripped_typarams = gens.types.iter().filter_map(|tp| {
1808             if tp.name == keywords::SelfType.name().as_str() {
1809                 assert_eq!(tp.index, 0);
1810                 None
1811             } else {
1812                 Some(tp.clean(cx))
1813             }
1814         }).collect::<Vec<_>>();
1815
1816         let mut where_predicates = preds.predicates.to_vec().clean(cx);
1817
1818         // Type parameters and have a Sized bound by default unless removed with
1819         // ?Sized. Scan through the predicates and mark any type parameter with
1820         // a Sized bound, removing the bounds as we find them.
1821         //
1822         // Note that associated types also have a sized bound by default, but we
1823         // don't actually know the set of associated types right here so that's
1824         // handled in cleaning associated types
1825         let mut sized_params = FxHashSet();
1826         where_predicates.retain(|pred| {
1827             match *pred {
1828                 WP::BoundPredicate { ty: Generic(ref g), ref bounds } => {
1829                     if bounds.iter().any(|b| b.is_sized_bound(cx)) {
1830                         sized_params.insert(g.clone());
1831                         false
1832                     } else {
1833                         true
1834                     }
1835                 }
1836                 _ => true,
1837             }
1838         });
1839
1840         // Run through the type parameters again and insert a ?Sized
1841         // unbound for any we didn't find to be Sized.
1842         for tp in &stripped_typarams {
1843             if !sized_params.contains(&tp.name) {
1844                 where_predicates.push(WP::BoundPredicate {
1845                     ty: Type::Generic(tp.name.clone()),
1846                     bounds: vec![TyParamBound::maybe_sized(cx)],
1847                 })
1848             }
1849         }
1850
1851         // It would be nice to collect all of the bounds on a type and recombine
1852         // them if possible, to avoid e.g. `where T: Foo, T: Bar, T: Sized, T: 'a`
1853         // and instead see `where T: Foo + Bar + Sized + 'a`
1854
1855         Generics {
1856             params: gens.regions
1857                 .clean(cx)
1858                 .into_iter()
1859                 .map(|lp| GenericParam::Lifetime(lp))
1860                 .chain(
1861                     simplify::ty_params(stripped_typarams)
1862                         .into_iter()
1863                         .map(|tp| GenericParam::Type(tp))
1864                 )
1865                 .collect(),
1866             where_predicates: simplify::where_clauses(cx, where_predicates),
1867         }
1868     }
1869 }
1870
1871 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1872 pub struct Method {
1873     pub generics: Generics,
1874     pub unsafety: hir::Unsafety,
1875     pub constness: hir::Constness,
1876     pub decl: FnDecl,
1877     pub abi: Abi,
1878 }
1879
1880 impl<'a> Clean<Method> for (&'a hir::MethodSig, &'a hir::Generics, hir::BodyId) {
1881     fn clean(&self, cx: &DocContext) -> Method {
1882         let (generics, decl) = enter_impl_trait(cx, || {
1883             (self.1.clean(cx), (&*self.0.decl, self.2).clean(cx))
1884         });
1885         Method {
1886             decl,
1887             generics,
1888             unsafety: self.0.unsafety,
1889             constness: self.0.constness,
1890             abi: self.0.abi
1891         }
1892     }
1893 }
1894
1895 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1896 pub struct TyMethod {
1897     pub unsafety: hir::Unsafety,
1898     pub decl: FnDecl,
1899     pub generics: Generics,
1900     pub abi: Abi,
1901 }
1902
1903 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1904 pub struct Function {
1905     pub decl: FnDecl,
1906     pub generics: Generics,
1907     pub unsafety: hir::Unsafety,
1908     pub constness: hir::Constness,
1909     pub abi: Abi,
1910 }
1911
1912 impl Clean<Item> for doctree::Function {
1913     fn clean(&self, cx: &DocContext) -> Item {
1914         let (generics, decl) = enter_impl_trait(cx, || {
1915             (self.generics.clean(cx), (&self.decl, self.body).clean(cx))
1916         });
1917         Item {
1918             name: Some(self.name.clean(cx)),
1919             attrs: self.attrs.clean(cx),
1920             source: self.whence.clean(cx),
1921             visibility: self.vis.clean(cx),
1922             stability: self.stab.clean(cx),
1923             deprecation: self.depr.clean(cx),
1924             def_id: cx.tcx.hir.local_def_id(self.id),
1925             inner: FunctionItem(Function {
1926                 decl,
1927                 generics,
1928                 unsafety: self.unsafety,
1929                 constness: self.constness,
1930                 abi: self.abi,
1931             }),
1932         }
1933     }
1934 }
1935
1936 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1937 pub struct FnDecl {
1938     pub inputs: Arguments,
1939     pub output: FunctionRetTy,
1940     pub variadic: bool,
1941     pub attrs: Attributes,
1942 }
1943
1944 impl FnDecl {
1945     pub fn has_self(&self) -> bool {
1946         self.inputs.values.len() > 0 && self.inputs.values[0].name == "self"
1947     }
1948
1949     pub fn self_type(&self) -> Option<SelfTy> {
1950         self.inputs.values.get(0).and_then(|v| v.to_self())
1951     }
1952 }
1953
1954 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
1955 pub struct Arguments {
1956     pub values: Vec<Argument>,
1957 }
1958
1959 impl<'a> Clean<Arguments> for (&'a [P<hir::Ty>], &'a [Spanned<ast::Name>]) {
1960     fn clean(&self, cx: &DocContext) -> Arguments {
1961         Arguments {
1962             values: self.0.iter().enumerate().map(|(i, ty)| {
1963                 let mut name = self.1.get(i).map(|n| n.node.to_string())
1964                                             .unwrap_or(String::new());
1965                 if name.is_empty() {
1966                     name = "_".to_string();
1967                 }
1968                 Argument {
1969                     name,
1970                     type_: ty.clean(cx),
1971                 }
1972             }).collect()
1973         }
1974     }
1975 }
1976
1977 impl<'a> Clean<Arguments> for (&'a [P<hir::Ty>], hir::BodyId) {
1978     fn clean(&self, cx: &DocContext) -> Arguments {
1979         let body = cx.tcx.hir.body(self.1);
1980
1981         Arguments {
1982             values: self.0.iter().enumerate().map(|(i, ty)| {
1983                 Argument {
1984                     name: name_from_pat(&body.arguments[i].pat),
1985                     type_: ty.clean(cx),
1986                 }
1987             }).collect()
1988         }
1989     }
1990 }
1991
1992 impl<'a, A: Copy> Clean<FnDecl> for (&'a hir::FnDecl, A)
1993     where (&'a [P<hir::Ty>], A): Clean<Arguments>
1994 {
1995     fn clean(&self, cx: &DocContext) -> FnDecl {
1996         FnDecl {
1997             inputs: (&self.0.inputs[..], self.1).clean(cx),
1998             output: self.0.output.clean(cx),
1999             variadic: self.0.variadic,
2000             attrs: Attributes::default()
2001         }
2002     }
2003 }
2004
2005 impl<'a, 'tcx> Clean<FnDecl> for (DefId, ty::PolyFnSig<'tcx>) {
2006     fn clean(&self, cx: &DocContext) -> FnDecl {
2007         let (did, sig) = *self;
2008         let mut names = if cx.tcx.hir.as_local_node_id(did).is_some() {
2009             vec![].into_iter()
2010         } else {
2011             cx.tcx.fn_arg_names(did).into_iter()
2012         };
2013
2014         FnDecl {
2015             output: Return(sig.skip_binder().output().clean(cx)),
2016             attrs: Attributes::default(),
2017             variadic: sig.skip_binder().variadic,
2018             inputs: Arguments {
2019                 values: sig.skip_binder().inputs().iter().map(|t| {
2020                     Argument {
2021                         type_: t.clean(cx),
2022                         name: names.next().map_or("".to_string(), |name| name.to_string()),
2023                     }
2024                 }).collect(),
2025             },
2026         }
2027     }
2028 }
2029
2030 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2031 pub struct Argument {
2032     pub type_: Type,
2033     pub name: String,
2034 }
2035
2036 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2037 pub enum SelfTy {
2038     SelfValue,
2039     SelfBorrowed(Option<Lifetime>, Mutability),
2040     SelfExplicit(Type),
2041 }
2042
2043 impl Argument {
2044     pub fn to_self(&self) -> Option<SelfTy> {
2045         if self.name != "self" {
2046             return None;
2047         }
2048         if self.type_.is_self_type() {
2049             return Some(SelfValue);
2050         }
2051         match self.type_ {
2052             BorrowedRef{ref lifetime, mutability, ref type_} if type_.is_self_type() => {
2053                 Some(SelfBorrowed(lifetime.clone(), mutability))
2054             }
2055             _ => Some(SelfExplicit(self.type_.clone()))
2056         }
2057     }
2058 }
2059
2060 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2061 pub enum FunctionRetTy {
2062     Return(Type),
2063     DefaultReturn,
2064 }
2065
2066 impl Clean<FunctionRetTy> for hir::FunctionRetTy {
2067     fn clean(&self, cx: &DocContext) -> FunctionRetTy {
2068         match *self {
2069             hir::Return(ref typ) => Return(typ.clean(cx)),
2070             hir::DefaultReturn(..) => DefaultReturn,
2071         }
2072     }
2073 }
2074
2075 impl GetDefId for FunctionRetTy {
2076     fn def_id(&self) -> Option<DefId> {
2077         match *self {
2078             Return(ref ty) => ty.def_id(),
2079             DefaultReturn => None,
2080         }
2081     }
2082 }
2083
2084 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2085 pub struct Trait {
2086     pub auto: bool,
2087     pub unsafety: hir::Unsafety,
2088     pub items: Vec<Item>,
2089     pub generics: Generics,
2090     pub bounds: Vec<TyParamBound>,
2091     pub is_spotlight: bool,
2092     pub is_auto: bool,
2093 }
2094
2095 impl Clean<Item> for doctree::Trait {
2096     fn clean(&self, cx: &DocContext) -> Item {
2097         let attrs = self.attrs.clean(cx);
2098         let is_spotlight = attrs.has_doc_flag("spotlight");
2099         Item {
2100             name: Some(self.name.clean(cx)),
2101             attrs: attrs,
2102             source: self.whence.clean(cx),
2103             def_id: cx.tcx.hir.local_def_id(self.id),
2104             visibility: self.vis.clean(cx),
2105             stability: self.stab.clean(cx),
2106             deprecation: self.depr.clean(cx),
2107             inner: TraitItem(Trait {
2108                 auto: self.is_auto.clean(cx),
2109                 unsafety: self.unsafety,
2110                 items: self.items.clean(cx),
2111                 generics: self.generics.clean(cx),
2112                 bounds: self.bounds.clean(cx),
2113                 is_spotlight: is_spotlight,
2114                 is_auto: self.is_auto.clean(cx),
2115             }),
2116         }
2117     }
2118 }
2119
2120 impl Clean<bool> for hir::IsAuto {
2121     fn clean(&self, _: &DocContext) -> bool {
2122         match *self {
2123             hir::IsAuto::Yes => true,
2124             hir::IsAuto::No => false,
2125         }
2126     }
2127 }
2128
2129 impl Clean<Type> for hir::TraitRef {
2130     fn clean(&self, cx: &DocContext) -> Type {
2131         resolve_type(cx, self.path.clean(cx), self.ref_id)
2132     }
2133 }
2134
2135 impl Clean<PolyTrait> for hir::PolyTraitRef {
2136     fn clean(&self, cx: &DocContext) -> PolyTrait {
2137         PolyTrait {
2138             trait_: self.trait_ref.clean(cx),
2139             generic_params: self.bound_generic_params.clean(cx)
2140         }
2141     }
2142 }
2143
2144 impl Clean<Item> for hir::TraitItem {
2145     fn clean(&self, cx: &DocContext) -> Item {
2146         let inner = match self.node {
2147             hir::TraitItemKind::Const(ref ty, default) => {
2148                 AssociatedConstItem(ty.clean(cx),
2149                                     default.map(|e| print_const_expr(cx, e)))
2150             }
2151             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Provided(body)) => {
2152                 MethodItem((sig, &self.generics, body).clean(cx))
2153             }
2154             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Required(ref names)) => {
2155                 let (generics, decl) = enter_impl_trait(cx, || {
2156                     (self.generics.clean(cx), (&*sig.decl, &names[..]).clean(cx))
2157                 });
2158                 TyMethodItem(TyMethod {
2159                     unsafety: sig.unsafety.clone(),
2160                     decl,
2161                     generics,
2162                     abi: sig.abi
2163                 })
2164             }
2165             hir::TraitItemKind::Type(ref bounds, ref default) => {
2166                 AssociatedTypeItem(bounds.clean(cx), default.clean(cx))
2167             }
2168         };
2169         Item {
2170             name: Some(self.name.clean(cx)),
2171             attrs: self.attrs.clean(cx),
2172             source: self.span.clean(cx),
2173             def_id: cx.tcx.hir.local_def_id(self.id),
2174             visibility: None,
2175             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2176             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2177             inner,
2178         }
2179     }
2180 }
2181
2182 impl Clean<Item> for hir::ImplItem {
2183     fn clean(&self, cx: &DocContext) -> Item {
2184         let inner = match self.node {
2185             hir::ImplItemKind::Const(ref ty, expr) => {
2186                 AssociatedConstItem(ty.clean(cx),
2187                                     Some(print_const_expr(cx, expr)))
2188             }
2189             hir::ImplItemKind::Method(ref sig, body) => {
2190                 MethodItem((sig, &self.generics, body).clean(cx))
2191             }
2192             hir::ImplItemKind::Type(ref ty) => TypedefItem(Typedef {
2193                 type_: ty.clean(cx),
2194                 generics: Generics::default(),
2195             }, true),
2196         };
2197         Item {
2198             name: Some(self.name.clean(cx)),
2199             source: self.span.clean(cx),
2200             attrs: self.attrs.clean(cx),
2201             def_id: cx.tcx.hir.local_def_id(self.id),
2202             visibility: self.vis.clean(cx),
2203             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2204             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2205             inner,
2206         }
2207     }
2208 }
2209
2210 impl<'tcx> Clean<Item> for ty::AssociatedItem {
2211     fn clean(&self, cx: &DocContext) -> Item {
2212         let inner = match self.kind {
2213             ty::AssociatedKind::Const => {
2214                 let ty = cx.tcx.type_of(self.def_id);
2215                 let default = if self.defaultness.has_value() {
2216                     Some(inline::print_inlined_const(cx, self.def_id))
2217                 } else {
2218                     None
2219                 };
2220                 AssociatedConstItem(ty.clean(cx), default)
2221             }
2222             ty::AssociatedKind::Method => {
2223                 let generics = (cx.tcx.generics_of(self.def_id),
2224                                 &cx.tcx.predicates_of(self.def_id)).clean(cx);
2225                 let sig = cx.tcx.fn_sig(self.def_id);
2226                 let mut decl = (self.def_id, sig).clean(cx);
2227
2228                 if self.method_has_self_argument {
2229                     let self_ty = match self.container {
2230                         ty::ImplContainer(def_id) => {
2231                             cx.tcx.type_of(def_id)
2232                         }
2233                         ty::TraitContainer(_) => cx.tcx.mk_self_type()
2234                     };
2235                     let self_arg_ty = *sig.input(0).skip_binder();
2236                     if self_arg_ty == self_ty {
2237                         decl.inputs.values[0].type_ = Generic(String::from("Self"));
2238                     } else if let ty::TyRef(_, ty, _) = self_arg_ty.sty {
2239                         if ty == self_ty {
2240                             match decl.inputs.values[0].type_ {
2241                                 BorrowedRef{ref mut type_, ..} => {
2242                                     **type_ = Generic(String::from("Self"))
2243                                 }
2244                                 _ => unreachable!(),
2245                             }
2246                         }
2247                     }
2248                 }
2249
2250                 let provided = match self.container {
2251                     ty::ImplContainer(_) => true,
2252                     ty::TraitContainer(_) => self.defaultness.has_value()
2253                 };
2254                 if provided {
2255                     let constness = if cx.tcx.is_const_fn(self.def_id) {
2256                         hir::Constness::Const
2257                     } else {
2258                         hir::Constness::NotConst
2259                     };
2260                     MethodItem(Method {
2261                         unsafety: sig.unsafety(),
2262                         generics,
2263                         decl,
2264                         abi: sig.abi(),
2265                         constness,
2266                     })
2267                 } else {
2268                     TyMethodItem(TyMethod {
2269                         unsafety: sig.unsafety(),
2270                         generics,
2271                         decl,
2272                         abi: sig.abi(),
2273                     })
2274                 }
2275             }
2276             ty::AssociatedKind::Type => {
2277                 let my_name = self.name.clean(cx);
2278
2279                 if let ty::TraitContainer(did) = self.container {
2280                     // When loading a cross-crate associated type, the bounds for this type
2281                     // are actually located on the trait/impl itself, so we need to load
2282                     // all of the generics from there and then look for bounds that are
2283                     // applied to this associated type in question.
2284                     let predicates = cx.tcx.predicates_of(did);
2285                     let generics = (cx.tcx.generics_of(did), &predicates).clean(cx);
2286                     let mut bounds = generics.where_predicates.iter().filter_map(|pred| {
2287                         let (name, self_type, trait_, bounds) = match *pred {
2288                             WherePredicate::BoundPredicate {
2289                                 ty: QPath { ref name, ref self_type, ref trait_ },
2290                                 ref bounds
2291                             } => (name, self_type, trait_, bounds),
2292                             _ => return None,
2293                         };
2294                         if *name != my_name { return None }
2295                         match **trait_ {
2296                             ResolvedPath { did, .. } if did == self.container.id() => {}
2297                             _ => return None,
2298                         }
2299                         match **self_type {
2300                             Generic(ref s) if *s == "Self" => {}
2301                             _ => return None,
2302                         }
2303                         Some(bounds)
2304                     }).flat_map(|i| i.iter().cloned()).collect::<Vec<_>>();
2305                     // Our Sized/?Sized bound didn't get handled when creating the generics
2306                     // because we didn't actually get our whole set of bounds until just now
2307                     // (some of them may have come from the trait). If we do have a sized
2308                     // bound, we remove it, and if we don't then we add the `?Sized` bound
2309                     // at the end.
2310                     match bounds.iter().position(|b| b.is_sized_bound(cx)) {
2311                         Some(i) => { bounds.remove(i); }
2312                         None => bounds.push(TyParamBound::maybe_sized(cx)),
2313                     }
2314
2315                     let ty = if self.defaultness.has_value() {
2316                         Some(cx.tcx.type_of(self.def_id))
2317                     } else {
2318                         None
2319                     };
2320
2321                     AssociatedTypeItem(bounds, ty.clean(cx))
2322                 } else {
2323                     TypedefItem(Typedef {
2324                         type_: cx.tcx.type_of(self.def_id).clean(cx),
2325                         generics: Generics {
2326                             params: Vec::new(),
2327                             where_predicates: Vec::new(),
2328                         },
2329                     }, true)
2330                 }
2331             }
2332         };
2333
2334         let visibility = match self.container {
2335             ty::ImplContainer(_) => self.vis.clean(cx),
2336             ty::TraitContainer(_) => None,
2337         };
2338
2339         Item {
2340             name: Some(self.name.clean(cx)),
2341             visibility,
2342             stability: get_stability(cx, self.def_id),
2343             deprecation: get_deprecation(cx, self.def_id),
2344             def_id: self.def_id,
2345             attrs: inline::load_attrs(cx, self.def_id),
2346             source: cx.tcx.def_span(self.def_id).clean(cx),
2347             inner,
2348         }
2349     }
2350 }
2351
2352 /// A trait reference, which may have higher ranked lifetimes.
2353 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2354 pub struct PolyTrait {
2355     pub trait_: Type,
2356     pub generic_params: Vec<GenericParam>,
2357 }
2358
2359 /// A representation of a Type suitable for hyperlinking purposes. Ideally one can get the original
2360 /// type out of the AST/TyCtxt given one of these, if more information is needed. Most importantly
2361 /// it does not preserve mutability or boxes.
2362 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
2363 pub enum Type {
2364     /// structs/enums/traits (most that'd be an hir::TyPath)
2365     ResolvedPath {
2366         path: Path,
2367         typarams: Option<Vec<TyParamBound>>,
2368         did: DefId,
2369         /// true if is a `T::Name` path for associated types
2370         is_generic: bool,
2371     },
2372     /// For parameterized types, so the consumer of the JSON don't go
2373     /// looking for types which don't exist anywhere.
2374     Generic(String),
2375     /// Primitives are the fixed-size numeric types (plus int/usize/float), char,
2376     /// arrays, slices, and tuples.
2377     Primitive(PrimitiveType),
2378     /// extern "ABI" fn
2379     BareFunction(Box<BareFunctionDecl>),
2380     Tuple(Vec<Type>),
2381     Slice(Box<Type>),
2382     Array(Box<Type>, String),
2383     Never,
2384     Unique(Box<Type>),
2385     RawPointer(Mutability, Box<Type>),
2386     BorrowedRef {
2387         lifetime: Option<Lifetime>,
2388         mutability: Mutability,
2389         type_: Box<Type>,
2390     },
2391
2392     // <Type as Trait>::Name
2393     QPath {
2394         name: String,
2395         self_type: Box<Type>,
2396         trait_: Box<Type>
2397     },
2398
2399     // _
2400     Infer,
2401
2402     // impl TraitA+TraitB
2403     ImplTrait(Vec<TyParamBound>),
2404 }
2405
2406 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Copy, Debug)]
2407 pub enum PrimitiveType {
2408     Isize, I8, I16, I32, I64, I128,
2409     Usize, U8, U16, U32, U64, U128,
2410     F32, F64,
2411     Char,
2412     Bool,
2413     Str,
2414     Slice,
2415     Array,
2416     Tuple,
2417     Unit,
2418     RawPointer,
2419     Reference,
2420     Fn,
2421     Never,
2422 }
2423
2424 #[derive(Clone, RustcEncodable, RustcDecodable, Copy, Debug)]
2425 pub enum TypeKind {
2426     Enum,
2427     Function,
2428     Module,
2429     Const,
2430     Static,
2431     Struct,
2432     Union,
2433     Trait,
2434     Variant,
2435     Typedef,
2436     Foreign,
2437     Macro,
2438 }
2439
2440 pub trait GetDefId {
2441     fn def_id(&self) -> Option<DefId>;
2442 }
2443
2444 impl<T: GetDefId> GetDefId for Option<T> {
2445     fn def_id(&self) -> Option<DefId> {
2446         self.as_ref().and_then(|d| d.def_id())
2447     }
2448 }
2449
2450 impl Type {
2451     pub fn primitive_type(&self) -> Option<PrimitiveType> {
2452         match *self {
2453             Primitive(p) | BorrowedRef { type_: box Primitive(p), ..} => Some(p),
2454             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
2455             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
2456             Tuple(ref tys) => if tys.is_empty() {
2457                 Some(PrimitiveType::Unit)
2458             } else {
2459                 Some(PrimitiveType::Tuple)
2460             },
2461             RawPointer(..) => Some(PrimitiveType::RawPointer),
2462             BorrowedRef { type_: box Generic(..), .. } => Some(PrimitiveType::Reference),
2463             BareFunction(..) => Some(PrimitiveType::Fn),
2464             Never => Some(PrimitiveType::Never),
2465             _ => None,
2466         }
2467     }
2468
2469     pub fn is_generic(&self) -> bool {
2470         match *self {
2471             ResolvedPath { is_generic, .. } => is_generic,
2472             _ => false,
2473         }
2474     }
2475
2476     pub fn is_self_type(&self) -> bool {
2477         match *self {
2478             Generic(ref name) => name == "Self",
2479             _ => false
2480         }
2481     }
2482
2483     pub fn generics(&self) -> Option<&[Type]> {
2484         match *self {
2485             ResolvedPath { ref path, .. } => {
2486                 path.segments.last().and_then(|seg| {
2487                     if let PathParameters::AngleBracketed { ref types, .. } = seg.params {
2488                         Some(&**types)
2489                     } else {
2490                         None
2491                     }
2492                 })
2493             }
2494             _ => None,
2495         }
2496     }
2497 }
2498
2499 impl GetDefId for Type {
2500     fn def_id(&self) -> Option<DefId> {
2501         match *self {
2502             ResolvedPath { did, .. } => Some(did),
2503             Primitive(p) => ::html::render::cache().primitive_locations.get(&p).cloned(),
2504             BorrowedRef { type_: box Generic(..), .. } =>
2505                 Primitive(PrimitiveType::Reference).def_id(),
2506             BorrowedRef { ref type_, .. } => type_.def_id(),
2507             Tuple(ref tys) => if tys.is_empty() {
2508                 Primitive(PrimitiveType::Unit).def_id()
2509             } else {
2510                 Primitive(PrimitiveType::Tuple).def_id()
2511             },
2512             BareFunction(..) => Primitive(PrimitiveType::Fn).def_id(),
2513             Never => Primitive(PrimitiveType::Never).def_id(),
2514             Slice(..) => Primitive(PrimitiveType::Slice).def_id(),
2515             Array(..) => Primitive(PrimitiveType::Array).def_id(),
2516             RawPointer(..) => Primitive(PrimitiveType::RawPointer).def_id(),
2517             QPath { ref self_type, .. } => self_type.def_id(),
2518             _ => None,
2519         }
2520     }
2521 }
2522
2523 impl PrimitiveType {
2524     fn from_str(s: &str) -> Option<PrimitiveType> {
2525         match s {
2526             "isize" => Some(PrimitiveType::Isize),
2527             "i8" => Some(PrimitiveType::I8),
2528             "i16" => Some(PrimitiveType::I16),
2529             "i32" => Some(PrimitiveType::I32),
2530             "i64" => Some(PrimitiveType::I64),
2531             "i128" => Some(PrimitiveType::I128),
2532             "usize" => Some(PrimitiveType::Usize),
2533             "u8" => Some(PrimitiveType::U8),
2534             "u16" => Some(PrimitiveType::U16),
2535             "u32" => Some(PrimitiveType::U32),
2536             "u64" => Some(PrimitiveType::U64),
2537             "u128" => Some(PrimitiveType::U128),
2538             "bool" => Some(PrimitiveType::Bool),
2539             "char" => Some(PrimitiveType::Char),
2540             "str" => Some(PrimitiveType::Str),
2541             "f32" => Some(PrimitiveType::F32),
2542             "f64" => Some(PrimitiveType::F64),
2543             "array" => Some(PrimitiveType::Array),
2544             "slice" => Some(PrimitiveType::Slice),
2545             "tuple" => Some(PrimitiveType::Tuple),
2546             "unit" => Some(PrimitiveType::Unit),
2547             "pointer" => Some(PrimitiveType::RawPointer),
2548             "reference" => Some(PrimitiveType::Reference),
2549             "fn" => Some(PrimitiveType::Fn),
2550             "never" => Some(PrimitiveType::Never),
2551             _ => None,
2552         }
2553     }
2554
2555     pub fn as_str(&self) -> &'static str {
2556         use self::PrimitiveType::*;
2557         match *self {
2558             Isize => "isize",
2559             I8 => "i8",
2560             I16 => "i16",
2561             I32 => "i32",
2562             I64 => "i64",
2563             I128 => "i128",
2564             Usize => "usize",
2565             U8 => "u8",
2566             U16 => "u16",
2567             U32 => "u32",
2568             U64 => "u64",
2569             U128 => "u128",
2570             F32 => "f32",
2571             F64 => "f64",
2572             Str => "str",
2573             Bool => "bool",
2574             Char => "char",
2575             Array => "array",
2576             Slice => "slice",
2577             Tuple => "tuple",
2578             Unit => "unit",
2579             RawPointer => "pointer",
2580             Reference => "reference",
2581             Fn => "fn",
2582             Never => "never",
2583         }
2584     }
2585
2586     pub fn to_url_str(&self) -> &'static str {
2587         self.as_str()
2588     }
2589 }
2590
2591 impl From<ast::IntTy> for PrimitiveType {
2592     fn from(int_ty: ast::IntTy) -> PrimitiveType {
2593         match int_ty {
2594             ast::IntTy::Isize => PrimitiveType::Isize,
2595             ast::IntTy::I8 => PrimitiveType::I8,
2596             ast::IntTy::I16 => PrimitiveType::I16,
2597             ast::IntTy::I32 => PrimitiveType::I32,
2598             ast::IntTy::I64 => PrimitiveType::I64,
2599             ast::IntTy::I128 => PrimitiveType::I128,
2600         }
2601     }
2602 }
2603
2604 impl From<ast::UintTy> for PrimitiveType {
2605     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
2606         match uint_ty {
2607             ast::UintTy::Usize => PrimitiveType::Usize,
2608             ast::UintTy::U8 => PrimitiveType::U8,
2609             ast::UintTy::U16 => PrimitiveType::U16,
2610             ast::UintTy::U32 => PrimitiveType::U32,
2611             ast::UintTy::U64 => PrimitiveType::U64,
2612             ast::UintTy::U128 => PrimitiveType::U128,
2613         }
2614     }
2615 }
2616
2617 impl From<ast::FloatTy> for PrimitiveType {
2618     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
2619         match float_ty {
2620             ast::FloatTy::F32 => PrimitiveType::F32,
2621             ast::FloatTy::F64 => PrimitiveType::F64,
2622         }
2623     }
2624 }
2625
2626 impl Clean<Type> for hir::Ty {
2627     fn clean(&self, cx: &DocContext) -> Type {
2628         use rustc::hir::*;
2629         match self.node {
2630             TyNever => Never,
2631             TyPtr(ref m) => RawPointer(m.mutbl.clean(cx), box m.ty.clean(cx)),
2632             TyRptr(ref l, ref m) => {
2633                 let lifetime = if l.is_elided() {
2634                     None
2635                 } else {
2636                     Some(l.clean(cx))
2637                 };
2638                 BorrowedRef {lifetime: lifetime, mutability: m.mutbl.clean(cx),
2639                              type_: box m.ty.clean(cx)}
2640             }
2641             TySlice(ref ty) => Slice(box ty.clean(cx)),
2642             TyArray(ref ty, n) => {
2643                 let def_id = cx.tcx.hir.body_owner_def_id(n);
2644                 let param_env = cx.tcx.param_env(def_id);
2645                 let substs = Substs::identity_for_item(cx.tcx, def_id);
2646                 let cid = GlobalId {
2647                     instance: ty::Instance::new(def_id, substs),
2648                     promoted: None
2649                 };
2650                 let n = cx.tcx.const_eval(param_env.and(cid)).unwrap_or_else(|_| {
2651                     cx.tcx.mk_const(ty::Const {
2652                         val: ConstVal::Unevaluated(def_id, substs),
2653                         ty: cx.tcx.types.usize
2654                     })
2655                 });
2656                 let n = print_const(cx, n);
2657                 Array(box ty.clean(cx), n)
2658             },
2659             TyTup(ref tys) => Tuple(tys.clean(cx)),
2660             TyPath(hir::QPath::Resolved(None, ref path)) => {
2661                 if let Some(new_ty) = cx.ty_substs.borrow().get(&path.def).cloned() {
2662                     return new_ty;
2663                 }
2664
2665                 if let Def::TyParam(did) = path.def {
2666                     if let Some(bounds) = cx.impl_trait_bounds.borrow_mut().remove(&did) {
2667                         return ImplTrait(bounds);
2668                     }
2669                 }
2670
2671                 let mut alias = None;
2672                 if let Def::TyAlias(def_id) = path.def {
2673                     // Substitute private type aliases
2674                     if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
2675                         if !cx.access_levels.borrow().is_exported(def_id) {
2676                             alias = Some(&cx.tcx.hir.expect_item(node_id).node);
2677                         }
2678                     }
2679                 };
2680
2681                 if let Some(&hir::ItemTy(ref ty, ref generics)) = alias {
2682                     let provided_params = &path.segments.last().unwrap();
2683                     let mut ty_substs = FxHashMap();
2684                     let mut lt_substs = FxHashMap();
2685                     provided_params.with_parameters(|provided_params| {
2686                         for (i, ty_param) in generics.ty_params().enumerate() {
2687                             let ty_param_def = Def::TyParam(cx.tcx.hir.local_def_id(ty_param.id));
2688                             if let Some(ty) = provided_params.types.get(i).cloned() {
2689                                 ty_substs.insert(ty_param_def, ty.into_inner().clean(cx));
2690                             } else if let Some(default) = ty_param.default.clone() {
2691                                 ty_substs.insert(ty_param_def, default.into_inner().clean(cx));
2692                             }
2693                         }
2694
2695                         for (i, lt_param) in generics.lifetimes().enumerate() {
2696                             if let Some(lt) = provided_params.lifetimes.get(i).cloned() {
2697                                 if !lt.is_elided() {
2698                                     let lt_def_id = cx.tcx.hir.local_def_id(lt_param.lifetime.id);
2699                                     lt_substs.insert(lt_def_id, lt.clean(cx));
2700                                 }
2701                             }
2702                         }
2703                     });
2704                     return cx.enter_alias(ty_substs, lt_substs, || ty.clean(cx));
2705                 }
2706                 resolve_type(cx, path.clean(cx), self.id)
2707             }
2708             TyPath(hir::QPath::Resolved(Some(ref qself), ref p)) => {
2709                 let mut segments: Vec<_> = p.segments.clone().into();
2710                 segments.pop();
2711                 let trait_path = hir::Path {
2712                     span: p.span,
2713                     def: Def::Trait(cx.tcx.associated_item(p.def.def_id()).container.id()),
2714                     segments: segments.into(),
2715                 };
2716                 Type::QPath {
2717                     name: p.segments.last().unwrap().name.clean(cx),
2718                     self_type: box qself.clean(cx),
2719                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
2720                 }
2721             }
2722             TyPath(hir::QPath::TypeRelative(ref qself, ref segment)) => {
2723                 let mut def = Def::Err;
2724                 let ty = hir_ty_to_ty(cx.tcx, self);
2725                 if let ty::TyProjection(proj) = ty.sty {
2726                     def = Def::Trait(proj.trait_ref(cx.tcx).def_id);
2727                 }
2728                 let trait_path = hir::Path {
2729                     span: self.span,
2730                     def,
2731                     segments: vec![].into(),
2732                 };
2733                 Type::QPath {
2734                     name: segment.name.clean(cx),
2735                     self_type: box qself.clean(cx),
2736                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
2737                 }
2738             }
2739             TyTraitObject(ref bounds, ref lifetime) => {
2740                 match bounds[0].clean(cx).trait_ {
2741                     ResolvedPath { path, typarams: None, did, is_generic } => {
2742                         let mut bounds: Vec<_> = bounds[1..].iter().map(|bound| {
2743                             TraitBound(bound.clean(cx), hir::TraitBoundModifier::None)
2744                         }).collect();
2745                         if !lifetime.is_elided() {
2746                             bounds.push(RegionBound(lifetime.clean(cx)));
2747                         }
2748                         ResolvedPath {
2749                             path,
2750                             typarams: Some(bounds),
2751                             did,
2752                             is_generic,
2753                         }
2754                     }
2755                     _ => Infer // shouldn't happen
2756                 }
2757             }
2758             TyBareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
2759             TyImplTraitExistential(ref exist_ty, ref _lts) => ImplTrait(exist_ty.bounds.clean(cx)),
2760             TyInfer | TyErr => Infer,
2761             TyTypeof(..) => panic!("Unimplemented type {:?}", self.node),
2762         }
2763     }
2764 }
2765
2766 impl<'tcx> Clean<Type> for Ty<'tcx> {
2767     fn clean(&self, cx: &DocContext) -> Type {
2768         match self.sty {
2769             ty::TyNever => Never,
2770             ty::TyBool => Primitive(PrimitiveType::Bool),
2771             ty::TyChar => Primitive(PrimitiveType::Char),
2772             ty::TyInt(int_ty) => Primitive(int_ty.into()),
2773             ty::TyUint(uint_ty) => Primitive(uint_ty.into()),
2774             ty::TyFloat(float_ty) => Primitive(float_ty.into()),
2775             ty::TyStr => Primitive(PrimitiveType::Str),
2776             ty::TySlice(ty) => Slice(box ty.clean(cx)),
2777             ty::TyArray(ty, n) => {
2778                 let mut n = cx.tcx.lift(&n).unwrap();
2779                 if let ConstVal::Unevaluated(def_id, substs) = n.val {
2780                     let param_env = cx.tcx.param_env(def_id);
2781                     let cid = GlobalId {
2782                         instance: ty::Instance::new(def_id, substs),
2783                         promoted: None
2784                     };
2785                     if let Ok(new_n) = cx.tcx.const_eval(param_env.and(cid)) {
2786                         n = new_n;
2787                     }
2788                 };
2789                 let n = print_const(cx, n);
2790                 Array(box ty.clean(cx), n)
2791             }
2792             ty::TyRawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
2793             ty::TyRef(r, ty, mutbl) => BorrowedRef {
2794                 lifetime: r.clean(cx),
2795                 mutability: mutbl.clean(cx),
2796                 type_: box ty.clean(cx),
2797             },
2798             ty::TyFnDef(..) |
2799             ty::TyFnPtr(_) => {
2800                 let ty = cx.tcx.lift(self).unwrap();
2801                 let sig = ty.fn_sig(cx.tcx);
2802                 BareFunction(box BareFunctionDecl {
2803                     unsafety: sig.unsafety(),
2804                     generic_params: Vec::new(),
2805                     decl: (cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID), sig).clean(cx),
2806                     abi: sig.abi(),
2807                 })
2808             }
2809             ty::TyAdt(def, substs) => {
2810                 let did = def.did;
2811                 let kind = match def.adt_kind() {
2812                     AdtKind::Struct => TypeKind::Struct,
2813                     AdtKind::Union => TypeKind::Union,
2814                     AdtKind::Enum => TypeKind::Enum,
2815                 };
2816                 inline::record_extern_fqn(cx, did, kind);
2817                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
2818                                          None, false, vec![], substs);
2819                 ResolvedPath {
2820                     path,
2821                     typarams: None,
2822                     did,
2823                     is_generic: false,
2824                 }
2825             }
2826             ty::TyForeign(did) => {
2827                 inline::record_extern_fqn(cx, did, TypeKind::Foreign);
2828                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
2829                                          None, false, vec![], Substs::empty());
2830                 ResolvedPath {
2831                     path: path,
2832                     typarams: None,
2833                     did: did,
2834                     is_generic: false,
2835                 }
2836             }
2837             ty::TyDynamic(ref obj, ref reg) => {
2838                 if let Some(principal) = obj.principal() {
2839                     let did = principal.def_id();
2840                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
2841
2842                     let mut typarams = vec![];
2843                     reg.clean(cx).map(|b| typarams.push(RegionBound(b)));
2844                     for did in obj.auto_traits() {
2845                         let empty = cx.tcx.intern_substs(&[]);
2846                         let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
2847                             Some(did), false, vec![], empty);
2848                         inline::record_extern_fqn(cx, did, TypeKind::Trait);
2849                         let bound = TraitBound(PolyTrait {
2850                             trait_: ResolvedPath {
2851                                 path,
2852                                 typarams: None,
2853                                 did,
2854                                 is_generic: false,
2855                             },
2856                             generic_params: Vec::new(),
2857                         }, hir::TraitBoundModifier::None);
2858                         typarams.push(bound);
2859                     }
2860
2861                     let mut bindings = vec![];
2862                     for pb in obj.projection_bounds() {
2863                         bindings.push(TypeBinding {
2864                             name: cx.tcx.associated_item(pb.item_def_id()).name.clean(cx),
2865                             ty: pb.skip_binder().ty.clean(cx)
2866                         });
2867                     }
2868
2869                     let path = external_path(cx, &cx.tcx.item_name(did).as_str(), Some(did),
2870                         false, bindings, principal.skip_binder().substs);
2871                     ResolvedPath {
2872                         path,
2873                         typarams: Some(typarams),
2874                         did,
2875                         is_generic: false,
2876                     }
2877                 } else {
2878                     Never
2879                 }
2880             }
2881             ty::TyTuple(ref t) => Tuple(t.clean(cx)),
2882
2883             ty::TyProjection(ref data) => data.clean(cx),
2884
2885             ty::TyParam(ref p) => Generic(p.name.to_string()),
2886
2887             ty::TyAnon(def_id, substs) => {
2888                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
2889                 // by looking up the projections associated with the def_id.
2890                 let predicates_of = cx.tcx.predicates_of(def_id);
2891                 let substs = cx.tcx.lift(&substs).unwrap();
2892                 let bounds = predicates_of.instantiate(cx.tcx, substs);
2893                 let mut regions = vec![];
2894                 let mut has_sized = false;
2895                 let mut bounds = bounds.predicates.iter().filter_map(|predicate| {
2896                     let trait_ref = if let Some(tr) = predicate.to_opt_poly_trait_ref() {
2897                         tr
2898                     } else if let ty::Predicate::TypeOutlives(pred) = *predicate {
2899                         // these should turn up at the end
2900                         pred.skip_binder().1.clean(cx).map(|r| regions.push(RegionBound(r)));
2901                         return None;
2902                     } else {
2903                         return None;
2904                     };
2905
2906                     if let Some(sized) = cx.tcx.lang_items().sized_trait() {
2907                         if trait_ref.def_id() == sized {
2908                             has_sized = true;
2909                             return None;
2910                         }
2911                     }
2912
2913
2914                     let bounds = bounds.predicates.iter().filter_map(|pred|
2915                         if let ty::Predicate::Projection(proj) = *pred {
2916                             let proj = proj.skip_binder();
2917                             if proj.projection_ty.trait_ref(cx.tcx) == *trait_ref.skip_binder() {
2918                                 Some(TypeBinding {
2919                                     name: cx.tcx.associated_item(proj.projection_ty.item_def_id)
2920                                                 .name.clean(cx),
2921                                     ty: proj.ty.clean(cx),
2922                                 })
2923                             } else {
2924                                 None
2925                             }
2926                         } else {
2927                             None
2928                         }
2929                     ).collect();
2930
2931                     Some((trait_ref.skip_binder(), bounds).clean(cx))
2932                 }).collect::<Vec<_>>();
2933                 bounds.extend(regions);
2934                 if !has_sized && !bounds.is_empty() {
2935                     bounds.insert(0, TyParamBound::maybe_sized(cx));
2936                 }
2937                 ImplTrait(bounds)
2938             }
2939
2940             ty::TyClosure(..) | ty::TyGenerator(..) => Tuple(vec![]), // FIXME(pcwalton)
2941
2942             ty::TyGeneratorWitness(..) => panic!("TyGeneratorWitness"),
2943             ty::TyInfer(..) => panic!("TyInfer"),
2944             ty::TyError => panic!("TyError"),
2945         }
2946     }
2947 }
2948
2949 impl Clean<Item> for hir::StructField {
2950     fn clean(&self, cx: &DocContext) -> Item {
2951         Item {
2952             name: Some(self.name).clean(cx),
2953             attrs: self.attrs.clean(cx),
2954             source: self.span.clean(cx),
2955             visibility: self.vis.clean(cx),
2956             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2957             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2958             def_id: cx.tcx.hir.local_def_id(self.id),
2959             inner: StructFieldItem(self.ty.clean(cx)),
2960         }
2961     }
2962 }
2963
2964 impl<'tcx> Clean<Item> for ty::FieldDef {
2965     fn clean(&self, cx: &DocContext) -> Item {
2966         Item {
2967             name: Some(self.name).clean(cx),
2968             attrs: cx.tcx.get_attrs(self.did).clean(cx),
2969             source: cx.tcx.def_span(self.did).clean(cx),
2970             visibility: self.vis.clean(cx),
2971             stability: get_stability(cx, self.did),
2972             deprecation: get_deprecation(cx, self.did),
2973             def_id: self.did,
2974             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
2975         }
2976     }
2977 }
2978
2979 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug)]
2980 pub enum Visibility {
2981     Public,
2982     Inherited,
2983 }
2984
2985 impl Clean<Option<Visibility>> for hir::Visibility {
2986     fn clean(&self, _: &DocContext) -> Option<Visibility> {
2987         Some(if *self == hir::Visibility::Public { Public } else { Inherited })
2988     }
2989 }
2990
2991 impl Clean<Option<Visibility>> for ty::Visibility {
2992     fn clean(&self, _: &DocContext) -> Option<Visibility> {
2993         Some(if *self == ty::Visibility::Public { Public } else { Inherited })
2994     }
2995 }
2996
2997 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2998 pub struct Struct {
2999     pub struct_type: doctree::StructType,
3000     pub generics: Generics,
3001     pub fields: Vec<Item>,
3002     pub fields_stripped: bool,
3003 }
3004
3005 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3006 pub struct Union {
3007     pub struct_type: doctree::StructType,
3008     pub generics: Generics,
3009     pub fields: Vec<Item>,
3010     pub fields_stripped: bool,
3011 }
3012
3013 impl Clean<Vec<Item>> for doctree::Struct {
3014     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3015         let name = self.name.clean(cx);
3016         let mut ret = get_auto_traits_with_node_id(cx, self.id, name.clone());
3017
3018         ret.push(Item {
3019             name: Some(name),
3020             attrs: self.attrs.clean(cx),
3021             source: self.whence.clean(cx),
3022             def_id: cx.tcx.hir.local_def_id(self.id),
3023             visibility: self.vis.clean(cx),
3024             stability: self.stab.clean(cx),
3025             deprecation: self.depr.clean(cx),
3026             inner: StructItem(Struct {
3027                 struct_type: self.struct_type,
3028                 generics: self.generics.clean(cx),
3029                 fields: self.fields.clean(cx),
3030                 fields_stripped: false,
3031             }),
3032         });
3033
3034         ret
3035     }
3036 }
3037
3038 impl Clean<Vec<Item>> for doctree::Union {
3039     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3040         let name = self.name.clean(cx);
3041         let mut ret = get_auto_traits_with_node_id(cx, self.id, name.clone());
3042
3043         ret.push(Item {
3044             name: Some(name),
3045             attrs: self.attrs.clean(cx),
3046             source: self.whence.clean(cx),
3047             def_id: cx.tcx.hir.local_def_id(self.id),
3048             visibility: self.vis.clean(cx),
3049             stability: self.stab.clean(cx),
3050             deprecation: self.depr.clean(cx),
3051             inner: UnionItem(Union {
3052                 struct_type: self.struct_type,
3053                 generics: self.generics.clean(cx),
3054                 fields: self.fields.clean(cx),
3055                 fields_stripped: false,
3056             }),
3057         });
3058
3059         ret
3060     }
3061 }
3062
3063 /// This is a more limited form of the standard Struct, different in that
3064 /// it lacks the things most items have (name, id, parameterization). Found
3065 /// only as a variant in an enum.
3066 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3067 pub struct VariantStruct {
3068     pub struct_type: doctree::StructType,
3069     pub fields: Vec<Item>,
3070     pub fields_stripped: bool,
3071 }
3072
3073 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
3074     fn clean(&self, cx: &DocContext) -> VariantStruct {
3075         VariantStruct {
3076             struct_type: doctree::struct_type_from_def(self),
3077             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
3078             fields_stripped: false,
3079         }
3080     }
3081 }
3082
3083 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3084 pub struct Enum {
3085     pub variants: Vec<Item>,
3086     pub generics: Generics,
3087     pub variants_stripped: bool,
3088 }
3089
3090 impl Clean<Vec<Item>> for doctree::Enum {
3091     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3092         let name = self.name.clean(cx);
3093         let mut ret = get_auto_traits_with_node_id(cx, self.id, name.clone());
3094
3095         ret.push(Item {
3096             name: Some(name),
3097             attrs: self.attrs.clean(cx),
3098             source: self.whence.clean(cx),
3099             def_id: cx.tcx.hir.local_def_id(self.id),
3100             visibility: self.vis.clean(cx),
3101             stability: self.stab.clean(cx),
3102             deprecation: self.depr.clean(cx),
3103             inner: EnumItem(Enum {
3104                 variants: self.variants.clean(cx),
3105                 generics: self.generics.clean(cx),
3106                 variants_stripped: false,
3107             }),
3108         });
3109
3110         ret
3111     }
3112 }
3113
3114 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3115 pub struct Variant {
3116     pub kind: VariantKind,
3117 }
3118
3119 impl Clean<Item> for doctree::Variant {
3120     fn clean(&self, cx: &DocContext) -> Item {
3121         Item {
3122             name: Some(self.name.clean(cx)),
3123             attrs: self.attrs.clean(cx),
3124             source: self.whence.clean(cx),
3125             visibility: None,
3126             stability: self.stab.clean(cx),
3127             deprecation: self.depr.clean(cx),
3128             def_id: cx.tcx.hir.local_def_id(self.def.id()),
3129             inner: VariantItem(Variant {
3130                 kind: self.def.clean(cx),
3131             }),
3132         }
3133     }
3134 }
3135
3136 impl<'tcx> Clean<Item> for ty::VariantDef {
3137     fn clean(&self, cx: &DocContext) -> Item {
3138         let kind = match self.ctor_kind {
3139             CtorKind::Const => VariantKind::CLike,
3140             CtorKind::Fn => {
3141                 VariantKind::Tuple(
3142                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
3143                 )
3144             }
3145             CtorKind::Fictive => {
3146                 VariantKind::Struct(VariantStruct {
3147                     struct_type: doctree::Plain,
3148                     fields_stripped: false,
3149                     fields: self.fields.iter().map(|field| {
3150                         Item {
3151                             source: cx.tcx.def_span(field.did).clean(cx),
3152                             name: Some(field.name.clean(cx)),
3153                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
3154                             visibility: field.vis.clean(cx),
3155                             def_id: field.did,
3156                             stability: get_stability(cx, field.did),
3157                             deprecation: get_deprecation(cx, field.did),
3158                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
3159                         }
3160                     }).collect()
3161                 })
3162             }
3163         };
3164         Item {
3165             name: Some(self.name.clean(cx)),
3166             attrs: inline::load_attrs(cx, self.did),
3167             source: cx.tcx.def_span(self.did).clean(cx),
3168             visibility: Some(Inherited),
3169             def_id: self.did,
3170             inner: VariantItem(Variant { kind: kind }),
3171             stability: get_stability(cx, self.did),
3172             deprecation: get_deprecation(cx, self.did),
3173         }
3174     }
3175 }
3176
3177 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3178 pub enum VariantKind {
3179     CLike,
3180     Tuple(Vec<Type>),
3181     Struct(VariantStruct),
3182 }
3183
3184 impl Clean<VariantKind> for hir::VariantData {
3185     fn clean(&self, cx: &DocContext) -> VariantKind {
3186         if self.is_struct() {
3187             VariantKind::Struct(self.clean(cx))
3188         } else if self.is_unit() {
3189             VariantKind::CLike
3190         } else {
3191             VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect())
3192         }
3193     }
3194 }
3195
3196 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3197 pub struct Span {
3198     pub filename: FileName,
3199     pub loline: usize,
3200     pub locol: usize,
3201     pub hiline: usize,
3202     pub hicol: usize,
3203 }
3204
3205 impl Span {
3206     pub fn empty() -> Span {
3207         Span {
3208             filename: FileName::Anon,
3209             loline: 0, locol: 0,
3210             hiline: 0, hicol: 0,
3211         }
3212     }
3213 }
3214
3215 impl Clean<Span> for syntax_pos::Span {
3216     fn clean(&self, cx: &DocContext) -> Span {
3217         if *self == DUMMY_SP {
3218             return Span::empty();
3219         }
3220
3221         let cm = cx.sess().codemap();
3222         let filename = cm.span_to_filename(*self);
3223         let lo = cm.lookup_char_pos(self.lo());
3224         let hi = cm.lookup_char_pos(self.hi());
3225         Span {
3226             filename,
3227             loline: lo.line,
3228             locol: lo.col.to_usize(),
3229             hiline: hi.line,
3230             hicol: hi.col.to_usize(),
3231         }
3232     }
3233 }
3234
3235 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3236 pub struct Path {
3237     pub global: bool,
3238     pub def: Def,
3239     pub segments: Vec<PathSegment>,
3240 }
3241
3242 impl Path {
3243     pub fn singleton(name: String) -> Path {
3244         Path {
3245             global: false,
3246             def: Def::Err,
3247             segments: vec![PathSegment {
3248                 name,
3249                 params: PathParameters::AngleBracketed {
3250                     lifetimes: Vec::new(),
3251                     types: Vec::new(),
3252                     bindings: Vec::new(),
3253                 }
3254             }]
3255         }
3256     }
3257
3258     pub fn last_name(&self) -> &str {
3259         self.segments.last().unwrap().name.as_str()
3260     }
3261 }
3262
3263 impl Clean<Path> for hir::Path {
3264     fn clean(&self, cx: &DocContext) -> Path {
3265         Path {
3266             global: self.is_global(),
3267             def: self.def,
3268             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
3269         }
3270     }
3271 }
3272
3273 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3274 pub enum PathParameters {
3275     AngleBracketed {
3276         lifetimes: Vec<Lifetime>,
3277         types: Vec<Type>,
3278         bindings: Vec<TypeBinding>,
3279     },
3280     Parenthesized {
3281         inputs: Vec<Type>,
3282         output: Option<Type>,
3283     }
3284 }
3285
3286 impl Clean<PathParameters> for hir::PathParameters {
3287     fn clean(&self, cx: &DocContext) -> PathParameters {
3288         if self.parenthesized {
3289             let output = self.bindings[0].ty.clean(cx);
3290             PathParameters::Parenthesized {
3291                 inputs: self.inputs().clean(cx),
3292                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
3293             }
3294         } else {
3295             PathParameters::AngleBracketed {
3296                 lifetimes: if self.lifetimes.iter().all(|lt| lt.is_elided()) {
3297                     vec![]
3298                 } else {
3299                     self.lifetimes.clean(cx)
3300                 },
3301                 types: self.types.clean(cx),
3302                 bindings: self.bindings.clean(cx),
3303             }
3304         }
3305     }
3306 }
3307
3308 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3309 pub struct PathSegment {
3310     pub name: String,
3311     pub params: PathParameters,
3312 }
3313
3314 impl Clean<PathSegment> for hir::PathSegment {
3315     fn clean(&self, cx: &DocContext) -> PathSegment {
3316         PathSegment {
3317             name: self.name.clean(cx),
3318             params: self.with_parameters(|parameters| parameters.clean(cx))
3319         }
3320     }
3321 }
3322
3323 fn strip_type(ty: Type) -> Type {
3324     match ty {
3325         Type::ResolvedPath { path, typarams, did, is_generic } => {
3326             Type::ResolvedPath { path: strip_path(&path), typarams, did, is_generic }
3327         }
3328         Type::Tuple(inner_tys) => {
3329             Type::Tuple(inner_tys.iter().map(|t| strip_type(t.clone())).collect())
3330         }
3331         Type::Slice(inner_ty) => Type::Slice(Box::new(strip_type(*inner_ty))),
3332         Type::Array(inner_ty, s) => Type::Array(Box::new(strip_type(*inner_ty)), s),
3333         Type::Unique(inner_ty) => Type::Unique(Box::new(strip_type(*inner_ty))),
3334         Type::RawPointer(m, inner_ty) => Type::RawPointer(m, Box::new(strip_type(*inner_ty))),
3335         Type::BorrowedRef { lifetime, mutability, type_ } => {
3336             Type::BorrowedRef { lifetime, mutability, type_: Box::new(strip_type(*type_)) }
3337         }
3338         Type::QPath { name, self_type, trait_ } => {
3339             Type::QPath {
3340                 name,
3341                 self_type: Box::new(strip_type(*self_type)), trait_: Box::new(strip_type(*trait_))
3342             }
3343         }
3344         _ => ty
3345     }
3346 }
3347
3348 fn strip_path(path: &Path) -> Path {
3349     let segments = path.segments.iter().map(|s| {
3350         PathSegment {
3351             name: s.name.clone(),
3352             params: PathParameters::AngleBracketed {
3353                 lifetimes: Vec::new(),
3354                 types: Vec::new(),
3355                 bindings: Vec::new(),
3356             }
3357         }
3358     }).collect();
3359
3360     Path {
3361         global: path.global,
3362         def: path.def.clone(),
3363         segments,
3364     }
3365 }
3366
3367 fn qpath_to_string(p: &hir::QPath) -> String {
3368     let segments = match *p {
3369         hir::QPath::Resolved(_, ref path) => &path.segments,
3370         hir::QPath::TypeRelative(_, ref segment) => return segment.name.to_string(),
3371     };
3372
3373     let mut s = String::new();
3374     for (i, seg) in segments.iter().enumerate() {
3375         if i > 0 {
3376             s.push_str("::");
3377         }
3378         if seg.name != keywords::CrateRoot.name() {
3379             s.push_str(&*seg.name.as_str());
3380         }
3381     }
3382     s
3383 }
3384
3385 impl Clean<String> for ast::Name {
3386     fn clean(&self, _: &DocContext) -> String {
3387         self.to_string()
3388     }
3389 }
3390
3391 impl Clean<String> for InternedString {
3392     fn clean(&self, _: &DocContext) -> String {
3393         self.to_string()
3394     }
3395 }
3396
3397 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3398 pub struct Typedef {
3399     pub type_: Type,
3400     pub generics: Generics,
3401 }
3402
3403 impl Clean<Item> for doctree::Typedef {
3404     fn clean(&self, cx: &DocContext) -> Item {
3405         Item {
3406             name: Some(self.name.clean(cx)),
3407             attrs: self.attrs.clean(cx),
3408             source: self.whence.clean(cx),
3409             def_id: cx.tcx.hir.local_def_id(self.id.clone()),
3410             visibility: self.vis.clean(cx),
3411             stability: self.stab.clean(cx),
3412             deprecation: self.depr.clean(cx),
3413             inner: TypedefItem(Typedef {
3414                 type_: self.ty.clean(cx),
3415                 generics: self.gen.clean(cx),
3416             }, false),
3417         }
3418     }
3419 }
3420
3421 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3422 pub struct BareFunctionDecl {
3423     pub unsafety: hir::Unsafety,
3424     pub generic_params: Vec<GenericParam>,
3425     pub decl: FnDecl,
3426     pub abi: Abi,
3427 }
3428
3429 impl Clean<BareFunctionDecl> for hir::BareFnTy {
3430     fn clean(&self, cx: &DocContext) -> BareFunctionDecl {
3431         let (generic_params, decl) = enter_impl_trait(cx, || {
3432             (self.generic_params.clean(cx), (&*self.decl, &self.arg_names[..]).clean(cx))
3433         });
3434         BareFunctionDecl {
3435             unsafety: self.unsafety,
3436             decl,
3437             generic_params,
3438             abi: self.abi,
3439         }
3440     }
3441 }
3442
3443 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3444 pub struct Static {
3445     pub type_: Type,
3446     pub mutability: Mutability,
3447     /// It's useful to have the value of a static documented, but I have no
3448     /// desire to represent expressions (that'd basically be all of the AST,
3449     /// which is huge!). So, have a string.
3450     pub expr: String,
3451 }
3452
3453 impl Clean<Item> for doctree::Static {
3454     fn clean(&self, cx: &DocContext) -> Item {
3455         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
3456         Item {
3457             name: Some(self.name.clean(cx)),
3458             attrs: self.attrs.clean(cx),
3459             source: self.whence.clean(cx),
3460             def_id: cx.tcx.hir.local_def_id(self.id),
3461             visibility: self.vis.clean(cx),
3462             stability: self.stab.clean(cx),
3463             deprecation: self.depr.clean(cx),
3464             inner: StaticItem(Static {
3465                 type_: self.type_.clean(cx),
3466                 mutability: self.mutability.clean(cx),
3467                 expr: print_const_expr(cx, self.expr),
3468             }),
3469         }
3470     }
3471 }
3472
3473 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3474 pub struct Constant {
3475     pub type_: Type,
3476     pub expr: String,
3477 }
3478
3479 impl Clean<Item> for doctree::Constant {
3480     fn clean(&self, cx: &DocContext) -> Item {
3481         Item {
3482             name: Some(self.name.clean(cx)),
3483             attrs: self.attrs.clean(cx),
3484             source: self.whence.clean(cx),
3485             def_id: cx.tcx.hir.local_def_id(self.id),
3486             visibility: self.vis.clean(cx),
3487             stability: self.stab.clean(cx),
3488             deprecation: self.depr.clean(cx),
3489             inner: ConstantItem(Constant {
3490                 type_: self.type_.clean(cx),
3491                 expr: print_const_expr(cx, self.expr),
3492             }),
3493         }
3494     }
3495 }
3496
3497 #[derive(Debug, Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Hash)]
3498 pub enum Mutability {
3499     Mutable,
3500     Immutable,
3501 }
3502
3503 impl Clean<Mutability> for hir::Mutability {
3504     fn clean(&self, _: &DocContext) -> Mutability {
3505         match self {
3506             &hir::MutMutable => Mutable,
3507             &hir::MutImmutable => Immutable,
3508         }
3509     }
3510 }
3511
3512 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Debug, Hash)]
3513 pub enum ImplPolarity {
3514     Positive,
3515     Negative,
3516 }
3517
3518 impl Clean<ImplPolarity> for hir::ImplPolarity {
3519     fn clean(&self, _: &DocContext) -> ImplPolarity {
3520         match self {
3521             &hir::ImplPolarity::Positive => ImplPolarity::Positive,
3522             &hir::ImplPolarity::Negative => ImplPolarity::Negative,
3523         }
3524     }
3525 }
3526
3527 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3528 pub struct Impl {
3529     pub unsafety: hir::Unsafety,
3530     pub generics: Generics,
3531     pub provided_trait_methods: FxHashSet<String>,
3532     pub trait_: Option<Type>,
3533     pub for_: Type,
3534     pub items: Vec<Item>,
3535     pub polarity: Option<ImplPolarity>,
3536     pub synthetic: bool,
3537 }
3538
3539 pub fn get_auto_traits_with_node_id(cx: &DocContext, id: ast::NodeId, name: String) -> Vec<Item> {
3540     let finder = AutoTraitFinder { cx };
3541     finder.get_with_node_id(id, name)
3542 }
3543
3544 pub fn get_auto_traits_with_def_id(cx: &DocContext, id: DefId) -> Vec<Item> {
3545     let finder = AutoTraitFinder {
3546         cx,
3547     };
3548
3549     finder.get_with_def_id(id)
3550 }
3551
3552 impl Clean<Vec<Item>> for doctree::Impl {
3553     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3554         let mut ret = Vec::new();
3555         let trait_ = self.trait_.clean(cx);
3556         let items = self.items.clean(cx);
3557
3558         // If this impl block is an implementation of the Deref trait, then we
3559         // need to try inlining the target's inherent impl blocks as well.
3560         if trait_.def_id() == cx.tcx.lang_items().deref_trait() {
3561             build_deref_target_impls(cx, &items, &mut ret);
3562         }
3563
3564         let provided = trait_.def_id().map(|did| {
3565             cx.tcx.provided_trait_methods(did)
3566                   .into_iter()
3567                   .map(|meth| meth.name.to_string())
3568                   .collect()
3569         }).unwrap_or(FxHashSet());
3570
3571         ret.push(Item {
3572             name: None,
3573             attrs: self.attrs.clean(cx),
3574             source: self.whence.clean(cx),
3575             def_id: cx.tcx.hir.local_def_id(self.id),
3576             visibility: self.vis.clean(cx),
3577             stability: self.stab.clean(cx),
3578             deprecation: self.depr.clean(cx),
3579             inner: ImplItem(Impl {
3580                 unsafety: self.unsafety,
3581                 generics: self.generics.clean(cx),
3582                 provided_trait_methods: provided,
3583                 trait_,
3584                 for_: self.for_.clean(cx),
3585                 items,
3586                 polarity: Some(self.polarity.clean(cx)),
3587                 synthetic: false,
3588             })
3589         });
3590         ret
3591     }
3592 }
3593
3594 fn build_deref_target_impls(cx: &DocContext,
3595                             items: &[Item],
3596                             ret: &mut Vec<Item>) {
3597     use self::PrimitiveType::*;
3598     let tcx = cx.tcx;
3599
3600     for item in items {
3601         let target = match item.inner {
3602             TypedefItem(ref t, true) => &t.type_,
3603             _ => continue,
3604         };
3605         let primitive = match *target {
3606             ResolvedPath { did, .. } if did.is_local() => continue,
3607             ResolvedPath { did, .. } => {
3608                 // We set the last parameter to false to avoid looking for auto-impls for traits
3609                 // and therefore avoid an ICE.
3610                 // The reason behind this is that auto-traits don't propagate through Deref so
3611                 // we're not supposed to synthesise impls for them.
3612                 ret.extend(inline::build_impls(cx, did, false));
3613                 continue
3614             }
3615             _ => match target.primitive_type() {
3616                 Some(prim) => prim,
3617                 None => continue,
3618             }
3619         };
3620         let did = match primitive {
3621             Isize => tcx.lang_items().isize_impl(),
3622             I8 => tcx.lang_items().i8_impl(),
3623             I16 => tcx.lang_items().i16_impl(),
3624             I32 => tcx.lang_items().i32_impl(),
3625             I64 => tcx.lang_items().i64_impl(),
3626             I128 => tcx.lang_items().i128_impl(),
3627             Usize => tcx.lang_items().usize_impl(),
3628             U8 => tcx.lang_items().u8_impl(),
3629             U16 => tcx.lang_items().u16_impl(),
3630             U32 => tcx.lang_items().u32_impl(),
3631             U64 => tcx.lang_items().u64_impl(),
3632             U128 => tcx.lang_items().u128_impl(),
3633             F32 => tcx.lang_items().f32_impl(),
3634             F64 => tcx.lang_items().f64_impl(),
3635             Char => tcx.lang_items().char_impl(),
3636             Bool => None,
3637             Str => tcx.lang_items().str_impl(),
3638             Slice => tcx.lang_items().slice_impl(),
3639             Array => tcx.lang_items().slice_impl(),
3640             Tuple => None,
3641             Unit => None,
3642             RawPointer => tcx.lang_items().const_ptr_impl(),
3643             Reference => None,
3644             Fn => None,
3645             Never => None,
3646         };
3647         if let Some(did) = did {
3648             if !did.is_local() {
3649                 inline::build_impl(cx, did, ret);
3650             }
3651         }
3652     }
3653 }
3654
3655 impl Clean<Item> for doctree::ExternCrate {
3656     fn clean(&self, cx: &DocContext) -> Item {
3657         Item {
3658             name: None,
3659             attrs: self.attrs.clean(cx),
3660             source: self.whence.clean(cx),
3661             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
3662             visibility: self.vis.clean(cx),
3663             stability: None,
3664             deprecation: None,
3665             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
3666         }
3667     }
3668 }
3669
3670 impl Clean<Vec<Item>> for doctree::Import {
3671     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3672         // We consider inlining the documentation of `pub use` statements, but we
3673         // forcefully don't inline if this is not public or if the
3674         // #[doc(no_inline)] attribute is present.
3675         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
3676         let denied = self.vis != hir::Public || self.attrs.iter().any(|a| {
3677             a.name() == "doc" && match a.meta_item_list() {
3678                 Some(l) => attr::list_contains_name(&l, "no_inline") ||
3679                            attr::list_contains_name(&l, "hidden"),
3680                 None => false,
3681             }
3682         });
3683         let path = self.path.clean(cx);
3684         let inner = if self.glob {
3685             Import::Glob(resolve_use_source(cx, path))
3686         } else {
3687             let name = self.name;
3688             if !denied {
3689                 let mut visited = FxHashSet();
3690                 if let Some(items) = inline::try_inline(cx, path.def, name, &mut visited) {
3691                     return items;
3692                 }
3693             }
3694             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
3695         };
3696         vec![Item {
3697             name: None,
3698             attrs: self.attrs.clean(cx),
3699             source: self.whence.clean(cx),
3700             def_id: cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID),
3701             visibility: self.vis.clean(cx),
3702             stability: None,
3703             deprecation: None,
3704             inner: ImportItem(inner)
3705         }]
3706     }
3707 }
3708
3709 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3710 pub enum Import {
3711     // use source as str;
3712     Simple(String, ImportSource),
3713     // use source::*;
3714     Glob(ImportSource)
3715 }
3716
3717 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3718 pub struct ImportSource {
3719     pub path: Path,
3720     pub did: Option<DefId>,
3721 }
3722
3723 impl Clean<Vec<Item>> for hir::ForeignMod {
3724     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3725         let mut items = self.items.clean(cx);
3726         for item in &mut items {
3727             if let ForeignFunctionItem(ref mut f) = item.inner {
3728                 f.abi = self.abi;
3729             }
3730         }
3731         items
3732     }
3733 }
3734
3735 impl Clean<Item> for hir::ForeignItem {
3736     fn clean(&self, cx: &DocContext) -> Item {
3737         let inner = match self.node {
3738             hir::ForeignItemFn(ref decl, ref names, ref generics) => {
3739                 let (generics, decl) = enter_impl_trait(cx, || {
3740                     (generics.clean(cx), (&**decl, &names[..]).clean(cx))
3741                 });
3742                 ForeignFunctionItem(Function {
3743                     decl,
3744                     generics,
3745                     unsafety: hir::Unsafety::Unsafe,
3746                     abi: Abi::Rust,
3747                     constness: hir::Constness::NotConst,
3748                 })
3749             }
3750             hir::ForeignItemStatic(ref ty, mutbl) => {
3751                 ForeignStaticItem(Static {
3752                     type_: ty.clean(cx),
3753                     mutability: if mutbl {Mutable} else {Immutable},
3754                     expr: "".to_string(),
3755                 })
3756             }
3757             hir::ForeignItemType => {
3758                 ForeignTypeItem
3759             }
3760         };
3761         Item {
3762             name: Some(self.name.clean(cx)),
3763             attrs: self.attrs.clean(cx),
3764             source: self.span.clean(cx),
3765             def_id: cx.tcx.hir.local_def_id(self.id),
3766             visibility: self.vis.clean(cx),
3767             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
3768             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
3769             inner,
3770         }
3771     }
3772 }
3773
3774 // Utilities
3775
3776 trait ToSource {
3777     fn to_src(&self, cx: &DocContext) -> String;
3778 }
3779
3780 impl ToSource for syntax_pos::Span {
3781     fn to_src(&self, cx: &DocContext) -> String {
3782         debug!("converting span {:?} to snippet", self.clean(cx));
3783         let sn = match cx.sess().codemap().span_to_snippet(*self) {
3784             Ok(x) => x.to_string(),
3785             Err(_) => "".to_string()
3786         };
3787         debug!("got snippet {}", sn);
3788         sn
3789     }
3790 }
3791
3792 fn name_from_pat(p: &hir::Pat) -> String {
3793     use rustc::hir::*;
3794     debug!("Trying to get a name from pattern: {:?}", p);
3795
3796     match p.node {
3797         PatKind::Wild => "_".to_string(),
3798         PatKind::Binding(_, _, ref p, _) => p.node.to_string(),
3799         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
3800         PatKind::Struct(ref name, ref fields, etc) => {
3801             format!("{} {{ {}{} }}", qpath_to_string(name),
3802                 fields.iter().map(|&Spanned { node: ref fp, .. }|
3803                                   format!("{}: {}", fp.name, name_from_pat(&*fp.pat)))
3804                              .collect::<Vec<String>>().join(", "),
3805                 if etc { ", ..." } else { "" }
3806             )
3807         }
3808         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
3809                                             .collect::<Vec<String>>().join(", ")),
3810         PatKind::Box(ref p) => name_from_pat(&**p),
3811         PatKind::Ref(ref p, _) => name_from_pat(&**p),
3812         PatKind::Lit(..) => {
3813             warn!("tried to get argument name from PatKind::Lit, \
3814                   which is silly in function arguments");
3815             "()".to_string()
3816         },
3817         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
3818                               which is not allowed in function arguments"),
3819         PatKind::Slice(ref begin, ref mid, ref end) => {
3820             let begin = begin.iter().map(|p| name_from_pat(&**p));
3821             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
3822             let end = end.iter().map(|p| name_from_pat(&**p));
3823             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
3824         },
3825     }
3826 }
3827
3828 fn print_const(cx: &DocContext, n: &ty::Const) -> String {
3829     match n.val {
3830         ConstVal::Unevaluated(def_id, _) => {
3831             if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
3832                 print_const_expr(cx, cx.tcx.hir.body_owned_by(node_id))
3833             } else {
3834                 inline::print_inlined_const(cx, def_id)
3835             }
3836         },
3837         ConstVal::Value(val) => {
3838             let mut s = String::new();
3839             ::rustc::mir::print_miri_value(val, n.ty, &mut s).unwrap();
3840             // array lengths are obviously usize
3841             if s.ends_with("usize") {
3842                 let n = s.len() - "usize".len();
3843                 s.truncate(n);
3844             }
3845             s
3846         },
3847     }
3848 }
3849
3850 fn print_const_expr(cx: &DocContext, body: hir::BodyId) -> String {
3851     cx.tcx.hir.node_to_pretty_string(body.node_id)
3852 }
3853
3854 /// Given a type Path, resolve it to a Type using the TyCtxt
3855 fn resolve_type(cx: &DocContext,
3856                 path: Path,
3857                 id: ast::NodeId) -> Type {
3858     if id == ast::DUMMY_NODE_ID {
3859         debug!("resolve_type({:?})", path);
3860     } else {
3861         debug!("resolve_type({:?},{:?})", path, id);
3862     }
3863
3864     let is_generic = match path.def {
3865         Def::PrimTy(p) => match p {
3866             hir::TyStr => return Primitive(PrimitiveType::Str),
3867             hir::TyBool => return Primitive(PrimitiveType::Bool),
3868             hir::TyChar => return Primitive(PrimitiveType::Char),
3869             hir::TyInt(int_ty) => return Primitive(int_ty.into()),
3870             hir::TyUint(uint_ty) => return Primitive(uint_ty.into()),
3871             hir::TyFloat(float_ty) => return Primitive(float_ty.into()),
3872         },
3873         Def::SelfTy(..) if path.segments.len() == 1 => {
3874             return Generic(keywords::SelfType.name().to_string());
3875         }
3876         Def::TyParam(..) if path.segments.len() == 1 => {
3877             return Generic(format!("{:#}", path));
3878         }
3879         Def::SelfTy(..) | Def::TyParam(..) | Def::AssociatedTy(..) => true,
3880         _ => false,
3881     };
3882     let did = register_def(&*cx, path.def);
3883     ResolvedPath { path: path, typarams: None, did: did, is_generic: is_generic }
3884 }
3885
3886 fn register_def(cx: &DocContext, def: Def) -> DefId {
3887     debug!("register_def({:?})", def);
3888
3889     let (did, kind) = match def {
3890         Def::Fn(i) => (i, TypeKind::Function),
3891         Def::TyAlias(i) => (i, TypeKind::Typedef),
3892         Def::Enum(i) => (i, TypeKind::Enum),
3893         Def::Trait(i) => (i, TypeKind::Trait),
3894         Def::Struct(i) => (i, TypeKind::Struct),
3895         Def::Union(i) => (i, TypeKind::Union),
3896         Def::Mod(i) => (i, TypeKind::Module),
3897         Def::TyForeign(i) => (i, TypeKind::Foreign),
3898         Def::Const(i) => (i, TypeKind::Const),
3899         Def::Static(i, _) => (i, TypeKind::Static),
3900         Def::Variant(i) => (cx.tcx.parent_def_id(i).unwrap(), TypeKind::Enum),
3901         Def::Macro(i, _) => (i, TypeKind::Macro),
3902         Def::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
3903         Def::SelfTy(_, Some(impl_def_id)) => {
3904             return impl_def_id
3905         }
3906         _ => return def.def_id()
3907     };
3908     if did.is_local() { return did }
3909     inline::record_extern_fqn(cx, did, kind);
3910     if let TypeKind::Trait = kind {
3911         inline::record_extern_trait(cx, did);
3912     }
3913     did
3914 }
3915
3916 fn resolve_use_source(cx: &DocContext, path: Path) -> ImportSource {
3917     ImportSource {
3918         did: if path.def == Def::Err {
3919             None
3920         } else {
3921             Some(register_def(cx, path.def))
3922         },
3923         path,
3924     }
3925 }
3926
3927 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3928 pub struct Macro {
3929     pub source: String,
3930     pub imported_from: Option<String>,
3931 }
3932
3933 impl Clean<Item> for doctree::Macro {
3934     fn clean(&self, cx: &DocContext) -> Item {
3935         let name = self.name.clean(cx);
3936         Item {
3937             name: Some(name.clone()),
3938             attrs: self.attrs.clean(cx),
3939             source: self.whence.clean(cx),
3940             visibility: Some(Public),
3941             stability: self.stab.clean(cx),
3942             deprecation: self.depr.clean(cx),
3943             def_id: self.def_id,
3944             inner: MacroItem(Macro {
3945                 source: format!("macro_rules! {} {{\n{}}}",
3946                                 name,
3947                                 self.matchers.iter().map(|span| {
3948                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
3949                                 }).collect::<String>()),
3950                 imported_from: self.imported_from.clean(cx),
3951             }),
3952         }
3953     }
3954 }
3955
3956 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3957 pub struct Stability {
3958     pub level: stability::StabilityLevel,
3959     pub feature: String,
3960     pub since: String,
3961     pub deprecated_since: String,
3962     pub deprecated_reason: String,
3963     pub unstable_reason: String,
3964     pub issue: Option<u32>
3965 }
3966
3967 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3968 pub struct Deprecation {
3969     pub since: String,
3970     pub note: String,
3971 }
3972
3973 impl Clean<Stability> for attr::Stability {
3974     fn clean(&self, _: &DocContext) -> Stability {
3975         Stability {
3976             level: stability::StabilityLevel::from_attr_level(&self.level),
3977             feature: self.feature.to_string(),
3978             since: match self.level {
3979                 attr::Stable {ref since} => since.to_string(),
3980                 _ => "".to_string(),
3981             },
3982             deprecated_since: match self.rustc_depr {
3983                 Some(attr::RustcDeprecation {ref since, ..}) => since.to_string(),
3984                 _=> "".to_string(),
3985             },
3986             deprecated_reason: match self.rustc_depr {
3987                 Some(ref depr) => depr.reason.to_string(),
3988                 _ => "".to_string(),
3989             },
3990             unstable_reason: match self.level {
3991                 attr::Unstable { reason: Some(ref reason), .. } => reason.to_string(),
3992                 _ => "".to_string(),
3993             },
3994             issue: match self.level {
3995                 attr::Unstable {issue, ..} => Some(issue),
3996                 _ => None,
3997             }
3998         }
3999     }
4000 }
4001
4002 impl<'a> Clean<Stability> for &'a attr::Stability {
4003     fn clean(&self, dc: &DocContext) -> Stability {
4004         (**self).clean(dc)
4005     }
4006 }
4007
4008 impl Clean<Deprecation> for attr::Deprecation {
4009     fn clean(&self, _: &DocContext) -> Deprecation {
4010         Deprecation {
4011             since: self.since.as_ref().map_or("".to_string(), |s| s.to_string()),
4012             note: self.note.as_ref().map_or("".to_string(), |s| s.to_string()),
4013         }
4014     }
4015 }
4016
4017 /// An equality constraint on an associated type, e.g. `A=Bar` in `Foo<A=Bar>`
4018 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug, Hash)]
4019 pub struct TypeBinding {
4020     pub name: String,
4021     pub ty: Type
4022 }
4023
4024 impl Clean<TypeBinding> for hir::TypeBinding {
4025     fn clean(&self, cx: &DocContext) -> TypeBinding {
4026         TypeBinding {
4027             name: self.name.clean(cx),
4028             ty: self.ty.clean(cx)
4029         }
4030     }
4031 }
4032
4033 pub fn def_id_to_path(cx: &DocContext, did: DefId, name: Option<String>) -> Vec<String> {
4034     let crate_name = name.unwrap_or_else(|| cx.tcx.crate_name(did.krate).to_string());
4035     let relative = cx.tcx.def_path(did).data.into_iter().filter_map(|elem| {
4036         // extern blocks have an empty name
4037         let s = elem.data.to_string();
4038         if !s.is_empty() {
4039             Some(s)
4040         } else {
4041             None
4042         }
4043     });
4044     once(crate_name).chain(relative).collect()
4045 }
4046
4047 pub fn enter_impl_trait<F, R>(cx: &DocContext, f: F) -> R
4048 where
4049     F: FnOnce() -> R,
4050 {
4051     let old_bounds = mem::replace(&mut *cx.impl_trait_bounds.borrow_mut(), Default::default());
4052     let r = f();
4053     assert!(cx.impl_trait_bounds.borrow().is_empty());
4054     *cx.impl_trait_bounds.borrow_mut() = old_bounds;
4055     r
4056 }
4057
4058 // Start of code copied from rust-clippy
4059
4060 pub fn get_trait_def_id(tcx: &TyCtxt, path: &[&str], use_local: bool) -> Option<DefId> {
4061     if use_local {
4062         path_to_def_local(tcx, path)
4063     } else {
4064         path_to_def(tcx, path)
4065     }
4066 }
4067
4068 pub fn path_to_def_local(tcx: &TyCtxt, path: &[&str]) -> Option<DefId> {
4069     let krate = tcx.hir.krate();
4070     let mut items = krate.module.item_ids.clone();
4071     let mut path_it = path.iter().peekable();
4072
4073     loop {
4074         let segment = match path_it.next() {
4075             Some(segment) => segment,
4076             None => return None,
4077         };
4078
4079         for item_id in mem::replace(&mut items, HirVec::new()).iter() {
4080             let item = tcx.hir.expect_item(item_id.id);
4081             if item.name == *segment {
4082                 if path_it.peek().is_none() {
4083                     return Some(tcx.hir.local_def_id(item_id.id))
4084                 }
4085
4086                 items = match &item.node {
4087                     &hir::ItemMod(ref m) => m.item_ids.clone(),
4088                     _ => panic!("Unexpected item {:?} in path {:?} path")
4089                 };
4090                 break;
4091             }
4092         }
4093     }
4094 }
4095
4096 pub fn path_to_def(tcx: &TyCtxt, path: &[&str]) -> Option<DefId> {
4097     let crates = tcx.crates();
4098
4099     let krate = crates
4100         .iter()
4101         .find(|&&krate| tcx.crate_name(krate) == path[0]);
4102
4103     if let Some(krate) = krate {
4104         let krate = DefId {
4105             krate: *krate,
4106             index: CRATE_DEF_INDEX,
4107         };
4108         let mut items = tcx.item_children(krate);
4109         let mut path_it = path.iter().skip(1).peekable();
4110
4111         loop {
4112             let segment = match path_it.next() {
4113                 Some(segment) => segment,
4114                 None => return None,
4115             };
4116
4117             for item in mem::replace(&mut items, Lrc::new(vec![])).iter() {
4118                 if item.ident.name == *segment {
4119                     if path_it.peek().is_none() {
4120                         return match item.def {
4121                             def::Def::Trait(did) => Some(did),
4122                             _ => None,
4123                         }
4124                     }
4125
4126                     items = tcx.item_children(item.def.def_id());
4127                     break;
4128                 }
4129             }
4130         }
4131     } else {
4132         None
4133     }
4134 }
4135
4136 fn get_path_for_type(tcx: TyCtxt, def_id: DefId, def_ctor: fn(DefId) -> Def) -> hir::Path {
4137     struct AbsolutePathBuffer {
4138         names: Vec<String>,
4139     }
4140
4141     impl ty::item_path::ItemPathBuffer for AbsolutePathBuffer {
4142         fn root_mode(&self) -> &ty::item_path::RootMode {
4143             const ABSOLUTE: &'static ty::item_path::RootMode = &ty::item_path::RootMode::Absolute;
4144             ABSOLUTE
4145         }
4146
4147         fn push(&mut self, text: &str) {
4148             self.names.push(text.to_owned());
4149         }
4150     }
4151
4152     let mut apb = AbsolutePathBuffer { names: vec![] };
4153
4154     tcx.push_item_path(&mut apb, def_id);
4155
4156     hir::Path {
4157         span: DUMMY_SP,
4158         def: def_ctor(def_id),
4159         segments: hir::HirVec::from_vec(apb.names.iter().map(|s| hir::PathSegment {
4160             name: ast::Name::intern(&s),
4161             parameters: None,
4162             infer_types: false,
4163         }).collect())
4164     }
4165 }
4166
4167 // End of code copied from rust-clippy
4168
4169
4170 #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
4171 enum RegionTarget<'tcx> {
4172     Region(Region<'tcx>),
4173     RegionVid(RegionVid)
4174 }
4175
4176 #[derive(Default, Debug, Clone)]
4177 struct RegionDeps<'tcx> {
4178     larger: FxHashSet<RegionTarget<'tcx>>,
4179     smaller: FxHashSet<RegionTarget<'tcx>>
4180 }
4181
4182 #[derive(Eq, PartialEq, Hash, Debug)]
4183 enum SimpleBound {
4184     RegionBound(Lifetime),
4185     TraitBound(Vec<PathSegment>, Vec<SimpleBound>, Vec<GenericParam>, hir::TraitBoundModifier)
4186 }
4187
4188 enum AutoTraitResult {
4189     ExplicitImpl,
4190     PositiveImpl(Generics),
4191     NegativeImpl,
4192 }
4193
4194 impl AutoTraitResult {
4195     fn is_auto(&self) -> bool {
4196         match *self {
4197             AutoTraitResult::PositiveImpl(_) | AutoTraitResult::NegativeImpl => true,
4198             _ => false,
4199         }
4200     }
4201 }
4202
4203 impl From<TyParamBound> for SimpleBound {
4204     fn from(bound: TyParamBound) -> Self {
4205         match bound.clone() {
4206             TyParamBound::RegionBound(l) => SimpleBound::RegionBound(l),
4207             TyParamBound::TraitBound(t, mod_) => match t.trait_ {
4208                 Type::ResolvedPath { path, typarams, .. } => {
4209                     SimpleBound::TraitBound(path.segments,
4210                                             typarams
4211                                                 .map_or_else(|| Vec::new(), |v| v.iter()
4212                                                         .map(|p| SimpleBound::from(p.clone()))
4213                                                         .collect()),
4214                                             t.generic_params,
4215                                             mod_)
4216                 }
4217                 _ => panic!("Unexpected bound {:?}", bound),
4218             }
4219         }
4220     }
4221 }