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.node.is_pub() => {
 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.node.is_pub() => {
 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             TyInfer | TyErr => Infer,
2991             TyTypeof(..) => panic!("Unimplemented type {:?}", self.node),
2992         }
2993     }
2994 }
2995
2996 impl<'tcx> Clean<Type> for Ty<'tcx> {
2997     fn clean(&self, cx: &DocContext) -> Type {
2998         match self.sty {
2999             ty::TyNever => Never,
3000             ty::TyBool => Primitive(PrimitiveType::Bool),
3001             ty::TyChar => Primitive(PrimitiveType::Char),
3002             ty::TyInt(int_ty) => Primitive(int_ty.into()),
3003             ty::TyUint(uint_ty) => Primitive(uint_ty.into()),
3004             ty::TyFloat(float_ty) => Primitive(float_ty.into()),
3005             ty::TyStr => Primitive(PrimitiveType::Str),
3006             ty::TySlice(ty) => Slice(box ty.clean(cx)),
3007             ty::TyArray(ty, n) => {
3008                 let mut n = cx.tcx.lift(&n).unwrap();
3009                 if let ConstValue::Unevaluated(def_id, substs) = n.val {
3010                     let param_env = cx.tcx.param_env(def_id);
3011                     let cid = GlobalId {
3012                         instance: ty::Instance::new(def_id, substs),
3013                         promoted: None
3014                     };
3015                     if let Ok(new_n) = cx.tcx.const_eval(param_env.and(cid)) {
3016                         n = new_n;
3017                     }
3018                 };
3019                 let n = print_const(cx, n);
3020                 Array(box ty.clean(cx), n)
3021             }
3022             ty::TyRawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
3023             ty::TyRef(r, ty, mutbl) => BorrowedRef {
3024                 lifetime: r.clean(cx),
3025                 mutability: mutbl.clean(cx),
3026                 type_: box ty.clean(cx),
3027             },
3028             ty::TyFnDef(..) |
3029             ty::TyFnPtr(_) => {
3030                 let ty = cx.tcx.lift(self).unwrap();
3031                 let sig = ty.fn_sig(cx.tcx);
3032                 BareFunction(box BareFunctionDecl {
3033                     unsafety: sig.unsafety(),
3034                     generic_params: Vec::new(),
3035                     decl: (cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID), sig).clean(cx),
3036                     abi: sig.abi(),
3037                 })
3038             }
3039             ty::TyAdt(def, substs) => {
3040                 let did = def.did;
3041                 let kind = match def.adt_kind() {
3042                     AdtKind::Struct => TypeKind::Struct,
3043                     AdtKind::Union => TypeKind::Union,
3044                     AdtKind::Enum => TypeKind::Enum,
3045                 };
3046                 inline::record_extern_fqn(cx, did, kind);
3047                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
3048                                          None, false, vec![], substs);
3049                 ResolvedPath {
3050                     path,
3051                     typarams: None,
3052                     did,
3053                     is_generic: false,
3054                 }
3055             }
3056             ty::TyForeign(did) => {
3057                 inline::record_extern_fqn(cx, did, TypeKind::Foreign);
3058                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
3059                                          None, false, vec![], Substs::empty());
3060                 ResolvedPath {
3061                     path: path,
3062                     typarams: None,
3063                     did: did,
3064                     is_generic: false,
3065                 }
3066             }
3067             ty::TyDynamic(ref obj, ref reg) => {
3068                 if let Some(principal) = obj.principal() {
3069                     let did = principal.def_id();
3070                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
3071
3072                     let mut typarams = vec![];
3073                     reg.clean(cx).map(|b| typarams.push(GenericBound::Outlives(b)));
3074                     for did in obj.auto_traits() {
3075                         let empty = cx.tcx.intern_substs(&[]);
3076                         let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
3077                             Some(did), false, vec![], empty);
3078                         inline::record_extern_fqn(cx, did, TypeKind::Trait);
3079                         let bound = GenericBound::TraitBound(PolyTrait {
3080                             trait_: ResolvedPath {
3081                                 path,
3082                                 typarams: None,
3083                                 did,
3084                                 is_generic: false,
3085                             },
3086                             generic_params: Vec::new(),
3087                         }, hir::TraitBoundModifier::None);
3088                         typarams.push(bound);
3089                     }
3090
3091                     let mut bindings = vec![];
3092                     for pb in obj.projection_bounds() {
3093                         bindings.push(TypeBinding {
3094                             name: cx.tcx.associated_item(pb.item_def_id()).ident.name.clean(cx),
3095                             ty: pb.skip_binder().ty.clean(cx)
3096                         });
3097                     }
3098
3099                     let path = external_path(cx, &cx.tcx.item_name(did).as_str(), Some(did),
3100                         false, bindings, principal.skip_binder().substs);
3101                     ResolvedPath {
3102                         path,
3103                         typarams: Some(typarams),
3104                         did,
3105                         is_generic: false,
3106                     }
3107                 } else {
3108                     Never
3109                 }
3110             }
3111             ty::TyTuple(ref t) => Tuple(t.clean(cx)),
3112
3113             ty::TyProjection(ref data) => data.clean(cx),
3114
3115             ty::TyParam(ref p) => Generic(p.name.to_string()),
3116
3117             ty::TyAnon(def_id, substs) => {
3118                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
3119                 // by looking up the projections associated with the def_id.
3120                 let predicates_of = cx.tcx.predicates_of(def_id);
3121                 let substs = cx.tcx.lift(&substs).unwrap();
3122                 let bounds = predicates_of.instantiate(cx.tcx, substs);
3123                 let mut regions = vec![];
3124                 let mut has_sized = false;
3125                 let mut bounds = bounds.predicates.iter().filter_map(|predicate| {
3126                     let trait_ref = if let Some(tr) = predicate.to_opt_poly_trait_ref() {
3127                         tr
3128                     } else if let ty::Predicate::TypeOutlives(pred) = *predicate {
3129                         // these should turn up at the end
3130                         pred.skip_binder().1.clean(cx).map(|r| {
3131                             regions.push(GenericBound::Outlives(r))
3132                         });
3133                         return None;
3134                     } else {
3135                         return None;
3136                     };
3137
3138                     if let Some(sized) = cx.tcx.lang_items().sized_trait() {
3139                         if trait_ref.def_id() == sized {
3140                             has_sized = true;
3141                             return None;
3142                         }
3143                     }
3144
3145                     let bounds = bounds.predicates.iter().filter_map(|pred|
3146                         if let ty::Predicate::Projection(proj) = *pred {
3147                             let proj = proj.skip_binder();
3148                             if proj.projection_ty.trait_ref(cx.tcx) == *trait_ref.skip_binder() {
3149                                 Some(TypeBinding {
3150                                     name: cx.tcx.associated_item(proj.projection_ty.item_def_id)
3151                                                 .ident.name.clean(cx),
3152                                     ty: proj.ty.clean(cx),
3153                                 })
3154                             } else {
3155                                 None
3156                             }
3157                         } else {
3158                             None
3159                         }
3160                     ).collect();
3161
3162                     Some((trait_ref.skip_binder(), bounds).clean(cx))
3163                 }).collect::<Vec<_>>();
3164                 bounds.extend(regions);
3165                 if !has_sized && !bounds.is_empty() {
3166                     bounds.insert(0, GenericBound::maybe_sized(cx));
3167                 }
3168                 ImplTrait(bounds)
3169             }
3170
3171             ty::TyClosure(..) | ty::TyGenerator(..) => Tuple(vec![]), // FIXME(pcwalton)
3172
3173             ty::TyGeneratorWitness(..) => panic!("TyGeneratorWitness"),
3174             ty::TyInfer(..) => panic!("TyInfer"),
3175             ty::TyError => panic!("TyError"),
3176         }
3177     }
3178 }
3179
3180 impl Clean<Item> for hir::StructField {
3181     fn clean(&self, cx: &DocContext) -> Item {
3182         Item {
3183             name: Some(self.ident.name).clean(cx),
3184             attrs: self.attrs.clean(cx),
3185             source: self.span.clean(cx),
3186             visibility: self.vis.clean(cx),
3187             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
3188             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
3189             def_id: cx.tcx.hir.local_def_id(self.id),
3190             inner: StructFieldItem(self.ty.clean(cx)),
3191         }
3192     }
3193 }
3194
3195 impl<'tcx> Clean<Item> for ty::FieldDef {
3196     fn clean(&self, cx: &DocContext) -> Item {
3197         Item {
3198             name: Some(self.ident.name).clean(cx),
3199             attrs: cx.tcx.get_attrs(self.did).clean(cx),
3200             source: cx.tcx.def_span(self.did).clean(cx),
3201             visibility: self.vis.clean(cx),
3202             stability: get_stability(cx, self.did),
3203             deprecation: get_deprecation(cx, self.did),
3204             def_id: self.did,
3205             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
3206         }
3207     }
3208 }
3209
3210 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug)]
3211 pub enum Visibility {
3212     Public,
3213     Inherited,
3214     Crate,
3215     Restricted(DefId, Path),
3216 }
3217
3218 impl Clean<Option<Visibility>> for hir::Visibility {
3219     fn clean(&self, cx: &DocContext) -> Option<Visibility> {
3220         Some(match self.node {
3221             hir::VisibilityKind::Public => Visibility::Public,
3222             hir::VisibilityKind::Inherited => Visibility::Inherited,
3223             hir::VisibilityKind::Crate(_) => Visibility::Crate,
3224             hir::VisibilityKind::Restricted { ref path, .. } => {
3225                 let path = path.clean(cx);
3226                 let did = register_def(cx, path.def);
3227                 Visibility::Restricted(did, path)
3228             }
3229         })
3230     }
3231 }
3232
3233 impl Clean<Option<Visibility>> for ty::Visibility {
3234     fn clean(&self, _: &DocContext) -> Option<Visibility> {
3235         Some(if *self == ty::Visibility::Public { Public } else { Inherited })
3236     }
3237 }
3238
3239 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3240 pub struct Struct {
3241     pub struct_type: doctree::StructType,
3242     pub generics: Generics,
3243     pub fields: Vec<Item>,
3244     pub fields_stripped: bool,
3245 }
3246
3247 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3248 pub struct Union {
3249     pub struct_type: doctree::StructType,
3250     pub generics: Generics,
3251     pub fields: Vec<Item>,
3252     pub fields_stripped: bool,
3253 }
3254
3255 impl Clean<Vec<Item>> for doctree::Struct {
3256     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3257         let name = self.name.clean(cx);
3258         let mut ret = get_auto_traits_with_node_id(cx, self.id, name.clone());
3259
3260         ret.push(Item {
3261             name: Some(name),
3262             attrs: self.attrs.clean(cx),
3263             source: self.whence.clean(cx),
3264             def_id: cx.tcx.hir.local_def_id(self.id),
3265             visibility: self.vis.clean(cx),
3266             stability: self.stab.clean(cx),
3267             deprecation: self.depr.clean(cx),
3268             inner: StructItem(Struct {
3269                 struct_type: self.struct_type,
3270                 generics: self.generics.clean(cx),
3271                 fields: self.fields.clean(cx),
3272                 fields_stripped: false,
3273             }),
3274         });
3275
3276         ret
3277     }
3278 }
3279
3280 impl Clean<Vec<Item>> for doctree::Union {
3281     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3282         let name = self.name.clean(cx);
3283         let mut ret = get_auto_traits_with_node_id(cx, self.id, name.clone());
3284
3285         ret.push(Item {
3286             name: Some(name),
3287             attrs: self.attrs.clean(cx),
3288             source: self.whence.clean(cx),
3289             def_id: cx.tcx.hir.local_def_id(self.id),
3290             visibility: self.vis.clean(cx),
3291             stability: self.stab.clean(cx),
3292             deprecation: self.depr.clean(cx),
3293             inner: UnionItem(Union {
3294                 struct_type: self.struct_type,
3295                 generics: self.generics.clean(cx),
3296                 fields: self.fields.clean(cx),
3297                 fields_stripped: false,
3298             }),
3299         });
3300
3301         ret
3302     }
3303 }
3304
3305 /// This is a more limited form of the standard Struct, different in that
3306 /// it lacks the things most items have (name, id, parameterization). Found
3307 /// only as a variant in an enum.
3308 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3309 pub struct VariantStruct {
3310     pub struct_type: doctree::StructType,
3311     pub fields: Vec<Item>,
3312     pub fields_stripped: bool,
3313 }
3314
3315 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
3316     fn clean(&self, cx: &DocContext) -> VariantStruct {
3317         VariantStruct {
3318             struct_type: doctree::struct_type_from_def(self),
3319             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
3320             fields_stripped: false,
3321         }
3322     }
3323 }
3324
3325 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3326 pub struct Enum {
3327     pub variants: Vec<Item>,
3328     pub generics: Generics,
3329     pub variants_stripped: bool,
3330 }
3331
3332 impl Clean<Vec<Item>> for doctree::Enum {
3333     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3334         let name = self.name.clean(cx);
3335         let mut ret = get_auto_traits_with_node_id(cx, self.id, name.clone());
3336
3337         ret.push(Item {
3338             name: Some(name),
3339             attrs: self.attrs.clean(cx),
3340             source: self.whence.clean(cx),
3341             def_id: cx.tcx.hir.local_def_id(self.id),
3342             visibility: self.vis.clean(cx),
3343             stability: self.stab.clean(cx),
3344             deprecation: self.depr.clean(cx),
3345             inner: EnumItem(Enum {
3346                 variants: self.variants.clean(cx),
3347                 generics: self.generics.clean(cx),
3348                 variants_stripped: false,
3349             }),
3350         });
3351
3352         ret
3353     }
3354 }
3355
3356 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3357 pub struct Variant {
3358     pub kind: VariantKind,
3359 }
3360
3361 impl Clean<Item> for doctree::Variant {
3362     fn clean(&self, cx: &DocContext) -> Item {
3363         Item {
3364             name: Some(self.name.clean(cx)),
3365             attrs: self.attrs.clean(cx),
3366             source: self.whence.clean(cx),
3367             visibility: None,
3368             stability: self.stab.clean(cx),
3369             deprecation: self.depr.clean(cx),
3370             def_id: cx.tcx.hir.local_def_id(self.def.id()),
3371             inner: VariantItem(Variant {
3372                 kind: self.def.clean(cx),
3373             }),
3374         }
3375     }
3376 }
3377
3378 impl<'tcx> Clean<Item> for ty::VariantDef {
3379     fn clean(&self, cx: &DocContext) -> Item {
3380         let kind = match self.ctor_kind {
3381             CtorKind::Const => VariantKind::CLike,
3382             CtorKind::Fn => {
3383                 VariantKind::Tuple(
3384                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
3385                 )
3386             }
3387             CtorKind::Fictive => {
3388                 VariantKind::Struct(VariantStruct {
3389                     struct_type: doctree::Plain,
3390                     fields_stripped: false,
3391                     fields: self.fields.iter().map(|field| {
3392                         Item {
3393                             source: cx.tcx.def_span(field.did).clean(cx),
3394                             name: Some(field.ident.name.clean(cx)),
3395                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
3396                             visibility: field.vis.clean(cx),
3397                             def_id: field.did,
3398                             stability: get_stability(cx, field.did),
3399                             deprecation: get_deprecation(cx, field.did),
3400                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
3401                         }
3402                     }).collect()
3403                 })
3404             }
3405         };
3406         Item {
3407             name: Some(self.name.clean(cx)),
3408             attrs: inline::load_attrs(cx, self.did),
3409             source: cx.tcx.def_span(self.did).clean(cx),
3410             visibility: Some(Inherited),
3411             def_id: self.did,
3412             inner: VariantItem(Variant { kind: kind }),
3413             stability: get_stability(cx, self.did),
3414             deprecation: get_deprecation(cx, self.did),
3415         }
3416     }
3417 }
3418
3419 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3420 pub enum VariantKind {
3421     CLike,
3422     Tuple(Vec<Type>),
3423     Struct(VariantStruct),
3424 }
3425
3426 impl Clean<VariantKind> for hir::VariantData {
3427     fn clean(&self, cx: &DocContext) -> VariantKind {
3428         if self.is_struct() {
3429             VariantKind::Struct(self.clean(cx))
3430         } else if self.is_unit() {
3431             VariantKind::CLike
3432         } else {
3433             VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect())
3434         }
3435     }
3436 }
3437
3438 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3439 pub struct Span {
3440     pub filename: FileName,
3441     pub loline: usize,
3442     pub locol: usize,
3443     pub hiline: usize,
3444     pub hicol: usize,
3445 }
3446
3447 impl Span {
3448     pub fn empty() -> Span {
3449         Span {
3450             filename: FileName::Anon,
3451             loline: 0, locol: 0,
3452             hiline: 0, hicol: 0,
3453         }
3454     }
3455 }
3456
3457 impl Clean<Span> for syntax_pos::Span {
3458     fn clean(&self, cx: &DocContext) -> Span {
3459         if self.is_dummy() {
3460             return Span::empty();
3461         }
3462
3463         let cm = cx.sess().codemap();
3464         let filename = cm.span_to_filename(*self);
3465         let lo = cm.lookup_char_pos(self.lo());
3466         let hi = cm.lookup_char_pos(self.hi());
3467         Span {
3468             filename,
3469             loline: lo.line,
3470             locol: lo.col.to_usize(),
3471             hiline: hi.line,
3472             hicol: hi.col.to_usize(),
3473         }
3474     }
3475 }
3476
3477 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3478 pub struct Path {
3479     pub global: bool,
3480     pub def: Def,
3481     pub segments: Vec<PathSegment>,
3482 }
3483
3484 impl Path {
3485     pub fn singleton(name: String) -> Path {
3486         Path {
3487             global: false,
3488             def: Def::Err,
3489             segments: vec![PathSegment {
3490                 name,
3491                 args: GenericArgs::AngleBracketed {
3492                     lifetimes: Vec::new(),
3493                     types: Vec::new(),
3494                     bindings: Vec::new(),
3495                 }
3496             }]
3497         }
3498     }
3499
3500     pub fn last_name(&self) -> &str {
3501         self.segments.last().unwrap().name.as_str()
3502     }
3503 }
3504
3505 impl Clean<Path> for hir::Path {
3506     fn clean(&self, cx: &DocContext) -> Path {
3507         Path {
3508             global: self.is_global(),
3509             def: self.def,
3510             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
3511         }
3512     }
3513 }
3514
3515 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3516 pub enum GenericArgs {
3517     AngleBracketed {
3518         lifetimes: Vec<Lifetime>,
3519         types: Vec<Type>,
3520         bindings: Vec<TypeBinding>,
3521     },
3522     Parenthesized {
3523         inputs: Vec<Type>,
3524         output: Option<Type>,
3525     }
3526 }
3527
3528 impl Clean<GenericArgs> for hir::GenericArgs {
3529     fn clean(&self, cx: &DocContext) -> GenericArgs {
3530         if self.parenthesized {
3531             let output = self.bindings[0].ty.clean(cx);
3532             GenericArgs::Parenthesized {
3533                 inputs: self.inputs().clean(cx),
3534                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
3535             }
3536         } else {
3537             let (mut lifetimes, mut types) = (vec![], vec![]);
3538             let mut elided_lifetimes = true;
3539             for arg in &self.args {
3540                 match arg {
3541                     GenericArg::Lifetime(lt) => {
3542                         if !lt.is_elided() {
3543                             elided_lifetimes = false;
3544                         }
3545                         lifetimes.push(lt.clean(cx));
3546                     }
3547                     GenericArg::Type(ty) => {
3548                         types.push(ty.clean(cx));
3549                     }
3550                 }
3551             }
3552             GenericArgs::AngleBracketed {
3553                 lifetimes: if elided_lifetimes { vec![] } else { lifetimes },
3554                 types,
3555                 bindings: self.bindings.clean(cx),
3556             }
3557         }
3558     }
3559 }
3560
3561 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3562 pub struct PathSegment {
3563     pub name: String,
3564     pub args: GenericArgs,
3565 }
3566
3567 impl Clean<PathSegment> for hir::PathSegment {
3568     fn clean(&self, cx: &DocContext) -> PathSegment {
3569         PathSegment {
3570             name: self.ident.name.clean(cx),
3571             args: self.with_generic_args(|generic_args| generic_args.clean(cx))
3572         }
3573     }
3574 }
3575
3576 fn strip_type(ty: Type) -> Type {
3577     match ty {
3578         Type::ResolvedPath { path, typarams, did, is_generic } => {
3579             Type::ResolvedPath { path: strip_path(&path), typarams, did, is_generic }
3580         }
3581         Type::Tuple(inner_tys) => {
3582             Type::Tuple(inner_tys.iter().map(|t| strip_type(t.clone())).collect())
3583         }
3584         Type::Slice(inner_ty) => Type::Slice(Box::new(strip_type(*inner_ty))),
3585         Type::Array(inner_ty, s) => Type::Array(Box::new(strip_type(*inner_ty)), s),
3586         Type::Unique(inner_ty) => Type::Unique(Box::new(strip_type(*inner_ty))),
3587         Type::RawPointer(m, inner_ty) => Type::RawPointer(m, Box::new(strip_type(*inner_ty))),
3588         Type::BorrowedRef { lifetime, mutability, type_ } => {
3589             Type::BorrowedRef { lifetime, mutability, type_: Box::new(strip_type(*type_)) }
3590         }
3591         Type::QPath { name, self_type, trait_ } => {
3592             Type::QPath {
3593                 name,
3594                 self_type: Box::new(strip_type(*self_type)), trait_: Box::new(strip_type(*trait_))
3595             }
3596         }
3597         _ => ty
3598     }
3599 }
3600
3601 fn strip_path(path: &Path) -> Path {
3602     let segments = path.segments.iter().map(|s| {
3603         PathSegment {
3604             name: s.name.clone(),
3605             args: GenericArgs::AngleBracketed {
3606                 lifetimes: Vec::new(),
3607                 types: Vec::new(),
3608                 bindings: Vec::new(),
3609             }
3610         }
3611     }).collect();
3612
3613     Path {
3614         global: path.global,
3615         def: path.def.clone(),
3616         segments,
3617     }
3618 }
3619
3620 fn qpath_to_string(p: &hir::QPath) -> String {
3621     let segments = match *p {
3622         hir::QPath::Resolved(_, ref path) => &path.segments,
3623         hir::QPath::TypeRelative(_, ref segment) => return segment.ident.to_string(),
3624     };
3625
3626     let mut s = String::new();
3627     for (i, seg) in segments.iter().enumerate() {
3628         if i > 0 {
3629             s.push_str("::");
3630         }
3631         if seg.ident.name != keywords::CrateRoot.name() {
3632             s.push_str(&*seg.ident.as_str());
3633         }
3634     }
3635     s
3636 }
3637
3638 impl Clean<String> for ast::Name {
3639     fn clean(&self, _: &DocContext) -> String {
3640         self.to_string()
3641     }
3642 }
3643
3644 impl Clean<String> for InternedString {
3645     fn clean(&self, _: &DocContext) -> String {
3646         self.to_string()
3647     }
3648 }
3649
3650 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3651 pub struct Typedef {
3652     pub type_: Type,
3653     pub generics: Generics,
3654 }
3655
3656 impl Clean<Item> for doctree::Typedef {
3657     fn clean(&self, cx: &DocContext) -> Item {
3658         Item {
3659             name: Some(self.name.clean(cx)),
3660             attrs: self.attrs.clean(cx),
3661             source: self.whence.clean(cx),
3662             def_id: cx.tcx.hir.local_def_id(self.id.clone()),
3663             visibility: self.vis.clean(cx),
3664             stability: self.stab.clean(cx),
3665             deprecation: self.depr.clean(cx),
3666             inner: TypedefItem(Typedef {
3667                 type_: self.ty.clean(cx),
3668                 generics: self.gen.clean(cx),
3669             }, false),
3670         }
3671     }
3672 }
3673
3674 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
3675 pub struct BareFunctionDecl {
3676     pub unsafety: hir::Unsafety,
3677     pub generic_params: Vec<GenericParamDef>,
3678     pub decl: FnDecl,
3679     pub abi: Abi,
3680 }
3681
3682 impl Clean<BareFunctionDecl> for hir::BareFnTy {
3683     fn clean(&self, cx: &DocContext) -> BareFunctionDecl {
3684         let (generic_params, decl) = enter_impl_trait(cx, || {
3685             (self.generic_params.clean(cx), (&*self.decl, &self.arg_names[..]).clean(cx))
3686         });
3687         BareFunctionDecl {
3688             unsafety: self.unsafety,
3689             abi: self.abi,
3690             decl,
3691             generic_params,
3692         }
3693     }
3694 }
3695
3696 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3697 pub struct Static {
3698     pub type_: Type,
3699     pub mutability: Mutability,
3700     /// It's useful to have the value of a static documented, but I have no
3701     /// desire to represent expressions (that'd basically be all of the AST,
3702     /// which is huge!). So, have a string.
3703     pub expr: String,
3704 }
3705
3706 impl Clean<Item> for doctree::Static {
3707     fn clean(&self, cx: &DocContext) -> Item {
3708         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
3709         Item {
3710             name: Some(self.name.clean(cx)),
3711             attrs: self.attrs.clean(cx),
3712             source: self.whence.clean(cx),
3713             def_id: cx.tcx.hir.local_def_id(self.id),
3714             visibility: self.vis.clean(cx),
3715             stability: self.stab.clean(cx),
3716             deprecation: self.depr.clean(cx),
3717             inner: StaticItem(Static {
3718                 type_: self.type_.clean(cx),
3719                 mutability: self.mutability.clean(cx),
3720                 expr: print_const_expr(cx, self.expr),
3721             }),
3722         }
3723     }
3724 }
3725
3726 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3727 pub struct Constant {
3728     pub type_: Type,
3729     pub expr: String,
3730 }
3731
3732 impl Clean<Item> for doctree::Constant {
3733     fn clean(&self, cx: &DocContext) -> Item {
3734         Item {
3735             name: Some(self.name.clean(cx)),
3736             attrs: self.attrs.clean(cx),
3737             source: self.whence.clean(cx),
3738             def_id: cx.tcx.hir.local_def_id(self.id),
3739             visibility: self.vis.clean(cx),
3740             stability: self.stab.clean(cx),
3741             deprecation: self.depr.clean(cx),
3742             inner: ConstantItem(Constant {
3743                 type_: self.type_.clean(cx),
3744                 expr: print_const_expr(cx, self.expr),
3745             }),
3746         }
3747     }
3748 }
3749
3750 #[derive(Debug, Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Hash)]
3751 pub enum Mutability {
3752     Mutable,
3753     Immutable,
3754 }
3755
3756 impl Clean<Mutability> for hir::Mutability {
3757     fn clean(&self, _: &DocContext) -> Mutability {
3758         match self {
3759             &hir::MutMutable => Mutable,
3760             &hir::MutImmutable => Immutable,
3761         }
3762     }
3763 }
3764
3765 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Copy, Debug, Hash)]
3766 pub enum ImplPolarity {
3767     Positive,
3768     Negative,
3769 }
3770
3771 impl Clean<ImplPolarity> for hir::ImplPolarity {
3772     fn clean(&self, _: &DocContext) -> ImplPolarity {
3773         match self {
3774             &hir::ImplPolarity::Positive => ImplPolarity::Positive,
3775             &hir::ImplPolarity::Negative => ImplPolarity::Negative,
3776         }
3777     }
3778 }
3779
3780 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3781 pub struct Impl {
3782     pub unsafety: hir::Unsafety,
3783     pub generics: Generics,
3784     pub provided_trait_methods: FxHashSet<String>,
3785     pub trait_: Option<Type>,
3786     pub for_: Type,
3787     pub items: Vec<Item>,
3788     pub polarity: Option<ImplPolarity>,
3789     pub synthetic: bool,
3790 }
3791
3792 pub fn get_auto_traits_with_node_id(cx: &DocContext, id: ast::NodeId, name: String) -> Vec<Item> {
3793     let finder = AutoTraitFinder::new(cx);
3794     finder.get_with_node_id(id, name)
3795 }
3796
3797 pub fn get_auto_traits_with_def_id(cx: &DocContext, id: DefId) -> Vec<Item> {
3798     let finder = AutoTraitFinder::new(cx);
3799
3800     finder.get_with_def_id(id)
3801 }
3802
3803 impl Clean<Vec<Item>> for doctree::Impl {
3804     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3805         let mut ret = Vec::new();
3806         let trait_ = self.trait_.clean(cx);
3807         let items = self.items.clean(cx);
3808
3809         // If this impl block is an implementation of the Deref trait, then we
3810         // need to try inlining the target's inherent impl blocks as well.
3811         if trait_.def_id() == cx.tcx.lang_items().deref_trait() {
3812             build_deref_target_impls(cx, &items, &mut ret);
3813         }
3814
3815         let provided = trait_.def_id().map(|did| {
3816             cx.tcx.provided_trait_methods(did)
3817                   .into_iter()
3818                   .map(|meth| meth.ident.to_string())
3819                   .collect()
3820         }).unwrap_or(FxHashSet());
3821
3822         ret.push(Item {
3823             name: None,
3824             attrs: self.attrs.clean(cx),
3825             source: self.whence.clean(cx),
3826             def_id: cx.tcx.hir.local_def_id(self.id),
3827             visibility: self.vis.clean(cx),
3828             stability: self.stab.clean(cx),
3829             deprecation: self.depr.clean(cx),
3830             inner: ImplItem(Impl {
3831                 unsafety: self.unsafety,
3832                 generics: self.generics.clean(cx),
3833                 provided_trait_methods: provided,
3834                 trait_,
3835                 for_: self.for_.clean(cx),
3836                 items,
3837                 polarity: Some(self.polarity.clean(cx)),
3838                 synthetic: false,
3839             })
3840         });
3841         ret
3842     }
3843 }
3844
3845 fn build_deref_target_impls(cx: &DocContext,
3846                             items: &[Item],
3847                             ret: &mut Vec<Item>) {
3848     use self::PrimitiveType::*;
3849     let tcx = cx.tcx;
3850
3851     for item in items {
3852         let target = match item.inner {
3853             TypedefItem(ref t, true) => &t.type_,
3854             _ => continue,
3855         };
3856         let primitive = match *target {
3857             ResolvedPath { did, .. } if did.is_local() => continue,
3858             ResolvedPath { did, .. } => {
3859                 // We set the last parameter to false to avoid looking for auto-impls for traits
3860                 // and therefore avoid an ICE.
3861                 // The reason behind this is that auto-traits don't propagate through Deref so
3862                 // we're not supposed to synthesise impls for them.
3863                 ret.extend(inline::build_impls(cx, did, false));
3864                 continue
3865             }
3866             _ => match target.primitive_type() {
3867                 Some(prim) => prim,
3868                 None => continue,
3869             }
3870         };
3871         let did = match primitive {
3872             Isize => tcx.lang_items().isize_impl(),
3873             I8 => tcx.lang_items().i8_impl(),
3874             I16 => tcx.lang_items().i16_impl(),
3875             I32 => tcx.lang_items().i32_impl(),
3876             I64 => tcx.lang_items().i64_impl(),
3877             I128 => tcx.lang_items().i128_impl(),
3878             Usize => tcx.lang_items().usize_impl(),
3879             U8 => tcx.lang_items().u8_impl(),
3880             U16 => tcx.lang_items().u16_impl(),
3881             U32 => tcx.lang_items().u32_impl(),
3882             U64 => tcx.lang_items().u64_impl(),
3883             U128 => tcx.lang_items().u128_impl(),
3884             F32 => tcx.lang_items().f32_impl(),
3885             F64 => tcx.lang_items().f64_impl(),
3886             Char => tcx.lang_items().char_impl(),
3887             Bool => None,
3888             Str => tcx.lang_items().str_impl(),
3889             Slice => tcx.lang_items().slice_impl(),
3890             Array => tcx.lang_items().slice_impl(),
3891             Tuple => None,
3892             Unit => None,
3893             RawPointer => tcx.lang_items().const_ptr_impl(),
3894             Reference => None,
3895             Fn => None,
3896             Never => None,
3897         };
3898         if let Some(did) = did {
3899             if !did.is_local() {
3900                 inline::build_impl(cx, did, ret);
3901             }
3902         }
3903     }
3904 }
3905
3906 impl Clean<Item> for doctree::ExternCrate {
3907     fn clean(&self, cx: &DocContext) -> Item {
3908         Item {
3909             name: None,
3910             attrs: self.attrs.clean(cx),
3911             source: self.whence.clean(cx),
3912             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
3913             visibility: self.vis.clean(cx),
3914             stability: None,
3915             deprecation: None,
3916             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
3917         }
3918     }
3919 }
3920
3921 impl Clean<Vec<Item>> for doctree::Import {
3922     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3923         // We consider inlining the documentation of `pub use` statements, but we
3924         // forcefully don't inline if this is not public or if the
3925         // #[doc(no_inline)] attribute is present.
3926         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
3927         let denied = !self.vis.node.is_pub() || self.attrs.iter().any(|a| {
3928             a.name() == "doc" && match a.meta_item_list() {
3929                 Some(l) => attr::list_contains_name(&l, "no_inline") ||
3930                            attr::list_contains_name(&l, "hidden"),
3931                 None => false,
3932             }
3933         });
3934         let path = self.path.clean(cx);
3935         let inner = if self.glob {
3936             if !denied {
3937                 let mut visited = FxHashSet();
3938                 if let Some(items) = inline::try_inline_glob(cx, path.def, &mut visited) {
3939                     return items;
3940                 }
3941             }
3942
3943             Import::Glob(resolve_use_source(cx, path))
3944         } else {
3945             let name = self.name;
3946             if !denied {
3947                 let mut visited = FxHashSet();
3948                 if let Some(items) = inline::try_inline(cx, path.def, name, &mut visited) {
3949                     return items;
3950                 }
3951             }
3952             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
3953         };
3954         vec![Item {
3955             name: None,
3956             attrs: self.attrs.clean(cx),
3957             source: self.whence.clean(cx),
3958             def_id: cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID),
3959             visibility: self.vis.clean(cx),
3960             stability: None,
3961             deprecation: None,
3962             inner: ImportItem(inner)
3963         }]
3964     }
3965 }
3966
3967 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3968 pub enum Import {
3969     // use source as str;
3970     Simple(String, ImportSource),
3971     // use source::*;
3972     Glob(ImportSource)
3973 }
3974
3975 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
3976 pub struct ImportSource {
3977     pub path: Path,
3978     pub did: Option<DefId>,
3979 }
3980
3981 impl Clean<Vec<Item>> for hir::ForeignMod {
3982     fn clean(&self, cx: &DocContext) -> Vec<Item> {
3983         let mut items = self.items.clean(cx);
3984         for item in &mut items {
3985             if let ForeignFunctionItem(ref mut f) = item.inner {
3986                 f.header.abi = self.abi;
3987             }
3988         }
3989         items
3990     }
3991 }
3992
3993 impl Clean<Item> for hir::ForeignItem {
3994     fn clean(&self, cx: &DocContext) -> Item {
3995         let inner = match self.node {
3996             hir::ForeignItemFn(ref decl, ref names, ref generics) => {
3997                 let (generics, decl) = enter_impl_trait(cx, || {
3998                     (generics.clean(cx), (&**decl, &names[..]).clean(cx))
3999                 });
4000                 ForeignFunctionItem(Function {
4001                     decl,
4002                     generics,
4003                     header: hir::FnHeader {
4004                         unsafety: hir::Unsafety::Unsafe,
4005                         abi: Abi::Rust,
4006                         constness: hir::Constness::NotConst,
4007                         asyncness: hir::IsAsync::NotAsync,
4008                     },
4009                 })
4010             }
4011             hir::ForeignItemStatic(ref ty, mutbl) => {
4012                 ForeignStaticItem(Static {
4013                     type_: ty.clean(cx),
4014                     mutability: if mutbl {Mutable} else {Immutable},
4015                     expr: "".to_string(),
4016                 })
4017             }
4018             hir::ForeignItemType => {
4019                 ForeignTypeItem
4020             }
4021         };
4022         Item {
4023             name: Some(self.name.clean(cx)),
4024             attrs: self.attrs.clean(cx),
4025             source: self.span.clean(cx),
4026             def_id: cx.tcx.hir.local_def_id(self.id),
4027             visibility: self.vis.clean(cx),
4028             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
4029             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
4030             inner,
4031         }
4032     }
4033 }
4034
4035 // Utilities
4036
4037 trait ToSource {
4038     fn to_src(&self, cx: &DocContext) -> String;
4039 }
4040
4041 impl ToSource for syntax_pos::Span {
4042     fn to_src(&self, cx: &DocContext) -> String {
4043         debug!("converting span {:?} to snippet", self.clean(cx));
4044         let sn = match cx.sess().codemap().span_to_snippet(*self) {
4045             Ok(x) => x.to_string(),
4046             Err(_) => "".to_string()
4047         };
4048         debug!("got snippet {}", sn);
4049         sn
4050     }
4051 }
4052
4053 fn name_from_pat(p: &hir::Pat) -> String {
4054     use rustc::hir::*;
4055     debug!("Trying to get a name from pattern: {:?}", p);
4056
4057     match p.node {
4058         PatKind::Wild => "_".to_string(),
4059         PatKind::Binding(_, _, ident, _) => ident.to_string(),
4060         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
4061         PatKind::Struct(ref name, ref fields, etc) => {
4062             format!("{} {{ {}{} }}", qpath_to_string(name),
4063                 fields.iter().map(|&Spanned { node: ref fp, .. }|
4064                                   format!("{}: {}", fp.ident, name_from_pat(&*fp.pat)))
4065                              .collect::<Vec<String>>().join(", "),
4066                 if etc { ", ..." } else { "" }
4067             )
4068         }
4069         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
4070                                             .collect::<Vec<String>>().join(", ")),
4071         PatKind::Box(ref p) => name_from_pat(&**p),
4072         PatKind::Ref(ref p, _) => name_from_pat(&**p),
4073         PatKind::Lit(..) => {
4074             warn!("tried to get argument name from PatKind::Lit, \
4075                   which is silly in function arguments");
4076             "()".to_string()
4077         },
4078         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
4079                               which is not allowed in function arguments"),
4080         PatKind::Slice(ref begin, ref mid, ref end) => {
4081             let begin = begin.iter().map(|p| name_from_pat(&**p));
4082             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
4083             let end = end.iter().map(|p| name_from_pat(&**p));
4084             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
4085         },
4086     }
4087 }
4088
4089 fn print_const(cx: &DocContext, n: &ty::Const) -> String {
4090     match n.val {
4091         ConstValue::Unevaluated(def_id, _) => {
4092             if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
4093                 print_const_expr(cx, cx.tcx.hir.body_owned_by(node_id))
4094             } else {
4095                 inline::print_inlined_const(cx, def_id)
4096             }
4097         },
4098         _ => {
4099             let mut s = String::new();
4100             ::rustc::mir::fmt_const_val(&mut s, n).unwrap();
4101             // array lengths are obviously usize
4102             if s.ends_with("usize") {
4103                 let n = s.len() - "usize".len();
4104                 s.truncate(n);
4105             }
4106             s
4107         },
4108     }
4109 }
4110
4111 fn print_const_expr(cx: &DocContext, body: hir::BodyId) -> String {
4112     cx.tcx.hir.node_to_pretty_string(body.node_id)
4113 }
4114
4115 /// Given a type Path, resolve it to a Type using the TyCtxt
4116 fn resolve_type(cx: &DocContext,
4117                 path: Path,
4118                 id: ast::NodeId) -> Type {
4119     if id == ast::DUMMY_NODE_ID {
4120         debug!("resolve_type({:?})", path);
4121     } else {
4122         debug!("resolve_type({:?},{:?})", path, id);
4123     }
4124
4125     let is_generic = match path.def {
4126         Def::PrimTy(p) => match p {
4127             hir::TyStr => return Primitive(PrimitiveType::Str),
4128             hir::TyBool => return Primitive(PrimitiveType::Bool),
4129             hir::TyChar => return Primitive(PrimitiveType::Char),
4130             hir::TyInt(int_ty) => return Primitive(int_ty.into()),
4131             hir::TyUint(uint_ty) => return Primitive(uint_ty.into()),
4132             hir::TyFloat(float_ty) => return Primitive(float_ty.into()),
4133         },
4134         Def::SelfTy(..) if path.segments.len() == 1 => {
4135             return Generic(keywords::SelfType.name().to_string());
4136         }
4137         Def::TyParam(..) if path.segments.len() == 1 => {
4138             return Generic(format!("{:#}", path));
4139         }
4140         Def::SelfTy(..) | Def::TyParam(..) | Def::AssociatedTy(..) => true,
4141         _ => false,
4142     };
4143     let did = register_def(&*cx, path.def);
4144     ResolvedPath { path: path, typarams: None, did: did, is_generic: is_generic }
4145 }
4146
4147 fn register_def(cx: &DocContext, def: Def) -> DefId {
4148     debug!("register_def({:?})", def);
4149
4150     let (did, kind) = match def {
4151         Def::Fn(i) => (i, TypeKind::Function),
4152         Def::TyAlias(i) => (i, TypeKind::Typedef),
4153         Def::Enum(i) => (i, TypeKind::Enum),
4154         Def::Trait(i) => (i, TypeKind::Trait),
4155         Def::Struct(i) => (i, TypeKind::Struct),
4156         Def::Union(i) => (i, TypeKind::Union),
4157         Def::Mod(i) => (i, TypeKind::Module),
4158         Def::TyForeign(i) => (i, TypeKind::Foreign),
4159         Def::Const(i) => (i, TypeKind::Const),
4160         Def::Static(i, _) => (i, TypeKind::Static),
4161         Def::Variant(i) => (cx.tcx.parent_def_id(i).unwrap(), TypeKind::Enum),
4162         Def::Macro(i, _) => (i, TypeKind::Macro),
4163         Def::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
4164         Def::SelfTy(_, Some(impl_def_id)) => {
4165             return impl_def_id
4166         }
4167         _ => return def.def_id()
4168     };
4169     if did.is_local() { return did }
4170     inline::record_extern_fqn(cx, did, kind);
4171     if let TypeKind::Trait = kind {
4172         inline::record_extern_trait(cx, did);
4173     }
4174     did
4175 }
4176
4177 fn resolve_use_source(cx: &DocContext, path: Path) -> ImportSource {
4178     ImportSource {
4179         did: if path.def == Def::Err {
4180             None
4181         } else {
4182             Some(register_def(cx, path.def))
4183         },
4184         path,
4185     }
4186 }
4187
4188 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4189 pub struct Macro {
4190     pub source: String,
4191     pub imported_from: Option<String>,
4192 }
4193
4194 impl Clean<Item> for doctree::Macro {
4195     fn clean(&self, cx: &DocContext) -> Item {
4196         let name = self.name.clean(cx);
4197         Item {
4198             name: Some(name.clone()),
4199             attrs: self.attrs.clean(cx),
4200             source: self.whence.clean(cx),
4201             visibility: Some(Public),
4202             stability: self.stab.clean(cx),
4203             deprecation: self.depr.clean(cx),
4204             def_id: self.def_id,
4205             inner: MacroItem(Macro {
4206                 source: format!("macro_rules! {} {{\n{}}}",
4207                                 name,
4208                                 self.matchers.iter().map(|span| {
4209                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
4210                                 }).collect::<String>()),
4211                 imported_from: self.imported_from.clean(cx),
4212             }),
4213         }
4214     }
4215 }
4216
4217 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4218 pub struct Stability {
4219     pub level: stability::StabilityLevel,
4220     pub feature: String,
4221     pub since: String,
4222     pub deprecated_since: String,
4223     pub deprecated_reason: String,
4224     pub unstable_reason: String,
4225     pub issue: Option<u32>
4226 }
4227
4228 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
4229 pub struct Deprecation {
4230     pub since: String,
4231     pub note: String,
4232 }
4233
4234 impl Clean<Stability> for attr::Stability {
4235     fn clean(&self, _: &DocContext) -> Stability {
4236         Stability {
4237             level: stability::StabilityLevel::from_attr_level(&self.level),
4238             feature: self.feature.to_string(),
4239             since: match self.level {
4240                 attr::Stable {ref since} => since.to_string(),
4241                 _ => "".to_string(),
4242             },
4243             deprecated_since: match self.rustc_depr {
4244                 Some(attr::RustcDeprecation {ref since, ..}) => since.to_string(),
4245                 _=> "".to_string(),
4246             },
4247             deprecated_reason: match self.rustc_depr {
4248                 Some(ref depr) => depr.reason.to_string(),
4249                 _ => "".to_string(),
4250             },
4251             unstable_reason: match self.level {
4252                 attr::Unstable { reason: Some(ref reason), .. } => reason.to_string(),
4253                 _ => "".to_string(),
4254             },
4255             issue: match self.level {
4256                 attr::Unstable {issue, ..} => Some(issue),
4257                 _ => None,
4258             }
4259         }
4260     }
4261 }
4262
4263 impl<'a> Clean<Stability> for &'a attr::Stability {
4264     fn clean(&self, dc: &DocContext) -> Stability {
4265         (**self).clean(dc)
4266     }
4267 }
4268
4269 impl Clean<Deprecation> for attr::Deprecation {
4270     fn clean(&self, _: &DocContext) -> Deprecation {
4271         Deprecation {
4272             since: self.since.as_ref().map_or("".to_string(), |s| s.to_string()),
4273             note: self.note.as_ref().map_or("".to_string(), |s| s.to_string()),
4274         }
4275     }
4276 }
4277
4278 /// An equality constraint on an associated type, e.g. `A=Bar` in `Foo<A=Bar>`
4279 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug, Hash)]
4280 pub struct TypeBinding {
4281     pub name: String,
4282     pub ty: Type
4283 }
4284
4285 impl Clean<TypeBinding> for hir::TypeBinding {
4286     fn clean(&self, cx: &DocContext) -> TypeBinding {
4287         TypeBinding {
4288             name: self.ident.name.clean(cx),
4289             ty: self.ty.clean(cx)
4290         }
4291     }
4292 }
4293
4294 pub fn def_id_to_path(cx: &DocContext, did: DefId, name: Option<String>) -> Vec<String> {
4295     let crate_name = name.unwrap_or_else(|| cx.tcx.crate_name(did.krate).to_string());
4296     let relative = cx.tcx.def_path(did).data.into_iter().filter_map(|elem| {
4297         // extern blocks have an empty name
4298         let s = elem.data.to_string();
4299         if !s.is_empty() {
4300             Some(s)
4301         } else {
4302             None
4303         }
4304     });
4305     once(crate_name).chain(relative).collect()
4306 }
4307
4308 pub fn enter_impl_trait<F, R>(cx: &DocContext, f: F) -> R
4309 where
4310     F: FnOnce() -> R,
4311 {
4312     let old_bounds = mem::replace(&mut *cx.impl_trait_bounds.borrow_mut(), Default::default());
4313     let r = f();
4314     assert!(cx.impl_trait_bounds.borrow().is_empty());
4315     *cx.impl_trait_bounds.borrow_mut() = old_bounds;
4316     r
4317 }
4318
4319 // Start of code copied from rust-clippy
4320
4321 pub fn get_trait_def_id(tcx: &TyCtxt, path: &[&str], use_local: bool) -> Option<DefId> {
4322     if use_local {
4323         path_to_def_local(tcx, path)
4324     } else {
4325         path_to_def(tcx, path)
4326     }
4327 }
4328
4329 pub fn path_to_def_local(tcx: &TyCtxt, path: &[&str]) -> Option<DefId> {
4330     let krate = tcx.hir.krate();
4331     let mut items = krate.module.item_ids.clone();
4332     let mut path_it = path.iter().peekable();
4333
4334     loop {
4335         let segment = match path_it.next() {
4336             Some(segment) => segment,
4337             None => return None,
4338         };
4339
4340         for item_id in mem::replace(&mut items, HirVec::new()).iter() {
4341             let item = tcx.hir.expect_item(item_id.id);
4342             if item.name == *segment {
4343                 if path_it.peek().is_none() {
4344                     return Some(tcx.hir.local_def_id(item_id.id))
4345                 }
4346
4347                 items = match &item.node {
4348                     &hir::ItemMod(ref m) => m.item_ids.clone(),
4349                     _ => panic!("Unexpected item {:?} in path {:?} path")
4350                 };
4351                 break;
4352             }
4353         }
4354     }
4355 }
4356
4357 pub fn path_to_def(tcx: &TyCtxt, path: &[&str]) -> Option<DefId> {
4358     let crates = tcx.crates();
4359
4360     let krate = crates
4361         .iter()
4362         .find(|&&krate| tcx.crate_name(krate) == path[0]);
4363
4364     if let Some(krate) = krate {
4365         let krate = DefId {
4366             krate: *krate,
4367             index: CRATE_DEF_INDEX,
4368         };
4369         let mut items = tcx.item_children(krate);
4370         let mut path_it = path.iter().skip(1).peekable();
4371
4372         loop {
4373             let segment = match path_it.next() {
4374                 Some(segment) => segment,
4375                 None => return None,
4376             };
4377
4378             for item in mem::replace(&mut items, Lrc::new(vec![])).iter() {
4379                 if item.ident.name == *segment {
4380                     if path_it.peek().is_none() {
4381                         return match item.def {
4382                             def::Def::Trait(did) => Some(did),
4383                             _ => None,
4384                         }
4385                     }
4386
4387                     items = tcx.item_children(item.def.def_id());
4388                     break;
4389                 }
4390             }
4391         }
4392     } else {
4393         None
4394     }
4395 }
4396
4397 fn get_path_for_type<F>(tcx: TyCtxt, def_id: DefId, def_ctor: F) -> hir::Path
4398 where F: Fn(DefId) -> Def {
4399     struct AbsolutePathBuffer {
4400         names: Vec<String>,
4401     }
4402
4403     impl ty::item_path::ItemPathBuffer for AbsolutePathBuffer {
4404         fn root_mode(&self) -> &ty::item_path::RootMode {
4405             const ABSOLUTE: &'static ty::item_path::RootMode = &ty::item_path::RootMode::Absolute;
4406             ABSOLUTE
4407         }
4408
4409         fn push(&mut self, text: &str) {
4410             self.names.push(text.to_owned());
4411         }
4412     }
4413
4414     let mut apb = AbsolutePathBuffer { names: vec![] };
4415
4416     tcx.push_item_path(&mut apb, def_id);
4417
4418     hir::Path {
4419         span: DUMMY_SP,
4420         def: def_ctor(def_id),
4421         segments: hir::HirVec::from_vec(apb.names.iter().map(|s| hir::PathSegment {
4422             ident: ast::Ident::from_str(&s),
4423             args: None,
4424             infer_types: false,
4425         }).collect())
4426     }
4427 }
4428
4429 // End of code copied from rust-clippy
4430
4431
4432 #[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
4433 enum RegionTarget<'tcx> {
4434     Region(Region<'tcx>),
4435     RegionVid(RegionVid)
4436 }
4437
4438 #[derive(Default, Debug, Clone)]
4439 struct RegionDeps<'tcx> {
4440     larger: FxHashSet<RegionTarget<'tcx>>,
4441     smaller: FxHashSet<RegionTarget<'tcx>>
4442 }
4443
4444 #[derive(Eq, PartialEq, Hash, Debug)]
4445 enum SimpleBound {
4446     TraitBound(Vec<PathSegment>, Vec<SimpleBound>, Vec<GenericParamDef>, hir::TraitBoundModifier),
4447     Outlives(Lifetime),
4448 }
4449
4450 enum AutoTraitResult {
4451     ExplicitImpl,
4452     PositiveImpl(Generics),
4453     NegativeImpl,
4454 }
4455
4456 impl AutoTraitResult {
4457     fn is_auto(&self) -> bool {
4458         match *self {
4459             AutoTraitResult::PositiveImpl(_) | AutoTraitResult::NegativeImpl => true,
4460             _ => false,
4461         }
4462     }
4463 }
4464
4465 impl From<GenericBound> for SimpleBound {
4466     fn from(bound: GenericBound) -> Self {
4467         match bound.clone() {
4468             GenericBound::Outlives(l) => SimpleBound::Outlives(l),
4469             GenericBound::TraitBound(t, mod_) => match t.trait_ {
4470                 Type::ResolvedPath { path, typarams, .. } => {
4471                     SimpleBound::TraitBound(path.segments,
4472                                             typarams
4473                                                 .map_or_else(|| Vec::new(), |v| v.iter()
4474                                                         .map(|p| SimpleBound::from(p.clone()))
4475                                                         .collect()),
4476                                             t.generic_params,
4477                                             mod_)
4478                 }
4479                 _ => panic!("Unexpected bound {:?}", bound),
4480             }
4481         }
4482     }
4483 }