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