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