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